Tutorials › Statistical Learning (Graduate) › Optimization Tolerance in Kernel Classification Guarantees

Home  /  Tutorials  /  Kernel Classification Guarantees

Kernel Classification Guarantees · Tutorial 784 of 989

Optimization Tolerance in Kernel Classification Guarantees

Derive a finite-sample guarantee for an approximately optimized kernel classifier and see when its optimization tolerance is small enough to retain the desired risk rate.

Advanced 11 min read

What You'll Learn

  • Define an approximate minimizer for a regularized empirical hinge-risk objective
  • Derive an oracle bound that includes optimization error explicitly
  • Relate hinge-risk excess to classification-risk excess using the unrestricted hinge-risk infimum
  • Separate approximation, regularization, statistical, and optimization contributions
  • Choose an optimization tolerance that does not dominate the target risk rate

Why Optimization Accuracy Belongs in a Risk Bound

A statistical guarantee for a kernel classifier usually compares its risk with that of a suitable competitor in the reproducing kernel Hilbert space (RKHS). In computation, however, the fitted score may not minimize the empirical objective exactly. An optimization algorithm may stop when the objective is close enough to its infimum, or may return a point whose optimality gap is known only to be small.

That gap is part of the guarantee. If it is larger than the statistical and approximation errors, it can determine the final risk rate, regardless of how well the statistical procedure is otherwise tuned. We make this contribution explicit for the regularized empirical hinge-risk objective.

Definition: Let \((X_i,Y_i)_{i=1}^n\) be independent observations from the distribution of \((X,Y)\), where \(Y\in\{-1,+1\}\). Let \(\mathcal H\) be an RKHS with norm \(\|\cdot\|_{\mathcal H}\), and define the hinge loss \(\phi_f(x,y)=(1-yf(x))_+\), where \(a_+=\max(a,0)\). Write \(P\phi_f=E[\phi_f(X,Y)]\) and \(P_n\phi_f=n^{-1}\sum_{i=1}^n\phi_f(X_i,Y_i)\). For \(\lambda>0\), the regularized empirical objective is \(J_{n,\lambda}(f)=P_n\phi_f+\lambda\|f\|_{\mathcal H}^2\). A score \(\hat f\) is an \(\varepsilon\)-approximate minimizer if \(J_{n,\lambda}(\hat f)\le\inf_{f\in\mathcal H}J_{n,\lambda}(f)+\varepsilon\), for \(\varepsilon\ge0\).

The empirical loss here is an average, not a sum. Thus \(\varepsilon\) is measured on the same scale as risk. Define the classifier \(h_f(x)=+1\) when \(f(x)\ge0\), and \(h_f(x)=-1\) otherwise. Its classification risk is \(R(h_f)=P\{h_f(X)\ne Y\}\), and the Bayes risk is \(R^*=\inf_h P\{h(X)\ne Y\}\), where the infimum is over measurable classifiers \(h\) taking values in \(\{-1,+1\}\). This definition counts a zero score as a \(+1\) prediction, so ties are treated consistently in the risk.

The Approximate-Optimizer Oracle Bound

The bound below is a deterministic transfer from a uniform empirical-to-population deviation statement. It does not require the optimizer to be unique. Suppose the kernel is bounded: \(k(x,x)\le\kappa^2\) for all \(x\). The reproducing property then gives \(|f(x)|\le\kappa\|f\|_{\mathcal H}\). In particular, on the ball \(\{f:\|f\|_{\mathcal H}\le B\}\), the hinge loss lies between 0 and \(1+\kappa B\).

Theorem: Fix \(B>0\), and suppose an event holds on which \(\sup_{\|f\|_{\mathcal H}\le B}|P_n\phi_f-P\phi_f|\le\delta\). Let \(\hat f\) be an \(\varepsilon\)-approximate minimizer, and let \(g\in\mathcal H\) satisfy \(\|g\|_{\mathcal H}\le B\) and \(P_n\phi_g+\lambda\|g\|_{\mathcal H}^2+\varepsilon\le\lambda B^2\). Then \(\|\hat f\|_{\mathcal H}\le B\), and $$ P\phi_{\hat f}\le P\phi_g+\lambda\|g\|_{\mathcal H}^2+\varepsilon+2\delta. $$

Proof. Since hinge loss is nonnegative, \(J_{n,\lambda}(\hat f)\ge\lambda\|\hat f\|_{\mathcal H}^2\). Approximate optimality, followed by comparison with \(g\), gives

$$ \lambda\|\hat f\|_{\mathcal H}^2 \le J_{n,\lambda}(\hat f) \le J_{n,\lambda}(g)+\varepsilon =P_n\phi_g+\lambda\|g\|_{\mathcal H}^2+\varepsilon \le\lambda B^2. $$

Thus \(\hat f\) is in the ball where the deviation bound applies. Apply that bound first to \(\hat f\), then use approximate optimality and discard the nonpositive term \(-\lambda\|\hat f\|_{\mathcal H}^2\):

$$ \begin{aligned} P\phi_{\hat f} &\le P_n\phi_{\hat f}+\delta\\ &=J_{n,\lambda}(\hat f)-\lambda\|\hat f\|_{\mathcal H}^2+\delta\\ &\le J_{n,\lambda}(g)+\varepsilon+\delta\\ &=P_n\phi_g+\lambda\|g\|_{\mathcal H}^2+\varepsilon+\delta\\ &\le P\phi_g+\lambda\|g\|_{\mathcal H}^2+\varepsilon+2\delta. \end{aligned} $$ The last inequality uses the deviation bound for \(g\). This proves the claim. \(\square\)

The radius condition in the theorem is a real condition, not an automatic consequence of choosing a comparator with small population risk. It ensures the approximate minimizer stays in the ball on which the deviation bound is known. In applications, one chooses \(B\) and verifies that the displayed empirical-objective condition holds, often on the same high-probability event used to control deviations.

From Hinge Risk to Classification Risk

To turn the theorem into a classification guarantee, the hinge-risk benchmark must be chosen correctly. Let \(\eta(x)=P(Y=+1\mid X=x)\), and let \(H^*=\inf_q P\phi_q\), where the infimum is over measurable real-valued score functions \(q\), not only scores in \(\mathcal H\). Conditional on \(X=x\), the hinge risk at score \(t\) is

$$ C_x(t)=\eta(x)(1-t)_+ +(1-\eta(x))(1+t)_+. $$

Its infimum over \(t\in\mathbb R\) is \(2\min(\eta(x),1-\eta(x))\): if \(\eta(x)\ge1/2\), \(t=1\) attains \(2(1-\eta(x))\); if \(\eta(x)<1/2\), \(t=-1\) attains \(2\eta(x)\). These choices are measurable as functions of \(x\), so \(H^*=2R^*\).

Result: For every measurable real-valued score \(f\), with \(h_f(x)=+1\) for \(f(x)\ge0\), one has \(R(h_f)-R^*\le P\phi_f-H^*\).

Proof. It is enough to check the conditional excess risks. At a fixed \(x\), abbreviate \(\eta=\eta(x)\). If \(\eta\ge1/2\), the Bayes label is \(+1\). A score \(t\ge0\) predicts that label and has nonnegative conditional hinge excess. If \(t<0\), it predicts \(-1\), so its conditional classification excess is \(2\eta-1\). Its conditional hinge risk is \(1+(1-2\eta)t\), and therefore its hinge excess over \(2(1-\eta)\) is

$$ 1+(1-2\eta)t-2(1-\eta)=(2\eta-1)(1-t)\ge2\eta-1. $$

If \(\eta<1/2\), the Bayes label is \(-1\). A score \(t<0\) predicts that label and has nonnegative hinge excess. For \(t\ge0\), the conditional classification excess is \(1-2\eta\), while the hinge excess over \(2\eta\) is

$$ 1+(1-2\eta)t-2\eta=(1-2\eta)(1+t)\ge1-2\eta. $$

When \(\eta=1/2\), the conditional classification excess is zero for either prediction, and the hinge excess is nonnegative. Integrating these pointwise inequalities over \(X\) proves the result. \(\square\)

Combining this result with the oracle bound gives, under the theorem's conditions,

$$ R(h_{\hat f})-R^* \le (P\phi_g-H^*)+\lambda\|g\|_{\mathcal H}^2+\varepsilon+2\delta. $$

The first term includes the cost of restricting the score to the chosen comparator. More explicitly, if \(\inf_{u\in\mathcal H}P\phi_u\) is finite, then

$$ P\phi_g-H^* =\left(P\phi_g-\inf_{u\in\mathcal H}P\phi_u\right) +\left(\inf_{u\in\mathcal H}P\phi_u-H^*\right). $$

The second parenthesis is the hinge-risk approximation gap of the RKHS. It cannot in general be omitted: the unrestricted hinge benchmark \(H^*\) is the one justified by the calibration argument.

Worked Examples

Worked Example: Checking a Finite-Sample Bound

Suppose \(\lambda=0.05\), and a comparator \(g\) has \(\|g\|_{\mathcal H}=2\) and empirical hinge risk \(P_n\phi_g=0.30\). An algorithm returns \(\hat f\) with \(\varepsilon=0.02\). Assume that, for \(B=3.3\), the uniform deviation event holds with \(\delta=0.05\).

First check the radius condition. The comparator objective plus tolerance is \(0.30+0.05(2^2)+0.02=0.52\), while \(\lambda B^2=0.05(3.3^2)=0.5445\). Thus the condition holds and \(\|\hat f\|_{\mathcal H}\le3.3\).

Suppose also that the deviation for this comparator is \(P\phi_g=0.34\), consistent with the assumed bound since \(0.34-0.30=0.04\le0.05\). The oracle inequality gives \(P\phi_{\hat f}\le0.34+0.05(4)+0.02+2(0.05)=0.66\). If \(H^*=0.18\), calibration then gives \(R(h_{\hat f})-R^*\le0.66-0.18=0.48\). This is a valid, though potentially loose, upper bound; it does not assert that the classifier's actual excess risk equals \(0.48\).

Worked Example: Choosing Tolerance for a Target Rate

Suppose a sequence of comparators \(g_n\) yields approximation error at most \(0.03n^{-1/3}\), regularization contribution \(\lambda_n\|g_n\|_{\mathcal H}^2\le0.02n^{-1/3}\), and the deviation term \(2\delta_n\le0.04n^{-1/3}\). The bound is then

\(R(h_{\hat f_n})-R^*\le0.09n^{-1/3}+\varepsilon_n.\)

If \(\varepsilon_n\le0.01n^{-1/3}\), the total is at most \(0.10n^{-1/3}\), so the target order \(n^{-1/3}\) is preserved. If instead \(\varepsilon_n=0.2n^{-1/4}\), the optimization term decays more slowly: \(n^{-1/4}/n^{-1/3}=n^{1/12}\), which grows with \(n\). The bound is then dominated by optimization error and does not establish the target rate. For the same leading statistical and approximation terms, taking \(\varepsilon_n=o(n^{-1/3})\) makes optimization negligible at that scale.

Worked Example: Why the Unrestricted Benchmark Matters

Let \(X\) be equally likely to equal \(+1\) or \(-1\), let \(Y=+1\) always, and take the RKHS to consist of linear scores \(f_a(x)=ax\). For \(f_1(x)=x\), the classifier predicts \(+1\) at \(x=+1\) and \(-1\) at \(x=-1\), so \(R(h_{f_1})=1/2\), whereas \(R^*=0\).

Its hinge risk is \(\{(1-1)_+ +(1-(-1))_+\}/2=(0+2)/2=1\). For any \(a\), the hinge risk is \(\{(1-a)_+ +(1+a)_+\}/2\). When \(|a|\le1\), this equals \(1\); when \(a>1\), it equals \((1+a)/2>1\); and when \(a<-1\), it equals \((1-a)/2>1\). Thus \(\inf_{u\in\mathcal H}P\phi_u=1\), and the hinge excess over the RKHS infimum is zero, despite the classification excess being \(1/2\).

By contrast, the unrestricted constant score \(q(x)=1\) has hinge risk zero, so \(H^*=0\). The valid calibration bound uses \(P\phi_{f_1}-H^*=1\), which does control the classification excess. The difference between the restricted and unrestricted infima is the approximation gap and must remain in a risk bound.

How to Read the Tolerance and Common Pitfalls

The bound separates four contributions: the comparator's excess hinge risk over the unrestricted benchmark, its regularization cost, the empirical-to-population deviation, and the optimization tolerance. The first two describe approximation and penalty trade-offs; the deviation describes statistical error; and \(\varepsilon\) describes computation. To preserve a target risk order \(q_n\), choose a comparator and deviation bound of order at most \(q_n\), and require \(\varepsilon_n=O(q_n)\). If optimization should not affect the leading order, use \(\varepsilon_n=o(q_n)\). This comparison is meaningful because the objective uses average loss; for an objective defined with a sum of losses, its numerical tolerance would need to be rescaled by \(n\).

  • Using the restricted hinge infimum in calibration. A pointwise calibration argument compares with the unrestricted score benchmark \(H^*\). If the comparator is restricted to \(\mathcal H\), include the gap \(\inf_{u\in\mathcal H}P\phi_u-H^*\).
  • Counting zero scores inconsistently. With the convention \(h_f(x)=+1\) for \(f(x)=0\), define classification risk as \(P\{h_f(X)\ne Y\}\). A strict-margin event that treats ties as automatically correct is a different convention.
  • Ignoring the radius needed for uniform deviation. The deviation bound must cover both the returned score and the comparator. Verify the radius condition rather than applying a ball-based bound to an uncontrolled optimizer.
  • Comparing tolerances to the wrong scale. Here \(\varepsilon\) is an objective gap for average empirical loss. A tolerance larger than the target risk order can erase the statistical rate in the final guarantee.
Key takeaway: Approximate optimization adds its objective gap directly to the regularized-risk oracle bound. A classification guarantee then uses the unrestricted hinge-risk benchmark, retaining any RKHS approximation gap. To preserve a target risk rate, the optimization tolerance must be no larger in order than that target.

Check Your Understanding

Use the definitions and bounds above to answer these questions.

  1. Why does nonnegativity of hinge loss help bound \(\|\hat f\|_{\mathcal H}\) from an approximate objective inequality?
  2. In the oracle inequality, where do the two copies of the uniform deviation \(\delta\) enter?
  3. Why can \(\inf_{u\in\mathcal H}P\phi_u-H^*\) not be discarded when converting a hinge-risk bound to a classification-risk bound?
  4. If the statistical and approximation terms are both \(O(n^{-2/5})\), what order of optimization tolerance is sufficient to preserve that rate? What order makes optimization negligible?
  5. Under the stated classifier convention, what label does a zero score predict, and how should its classification error be counted?

Previous

Next

Back to Tutorials
Clinical Biostats