Fast Rates from Bernstein Conditions for Kernel Scores

Why Variance Near the Optimum Matters

A uniform-deviation argument controls empirical risk error equally across a whole score class. That is safe, but it can be wasteful: a score with large excess risk need not be estimated as precisely as one that is nearly optimal. A Bernstein condition formalizes a useful form of localization. It says that the variance of an excess loss decreases as its mean excess decreases. For empirical risk minimization, this makes the stochastic error smaller precisely where the selected score must be compared with an optimum.

We develop the argument for a finite set of kernel scores, where the complexity contribution can be stated explicitly. The same variance calculation is the core of more general localized empirical-process bounds, in which a local complexity measure replaces the logarithm of the number of candidates. The finite-class setting also makes clear which assumptions produce the fast rate and which do not.

Kernel Scores and Excess Losses

Let \(Z=(X,Y)\) be an observation, and let \(Z_1,\ldots,Z_n\) be independent observations with the same distribution as \(Z\). Let \(\mathcal F\) be a finite set of real-valued scores from a reproducing kernel Hilbert space (RKHS), with \(|\mathcal F|=M\). For a kernel satisfying \(K(x,x)\leq \kappa^2\), every score with \(\|f\|_{\mathcal H}\leq R\) obeys \(|f(x)|\leq \kappa R\). We use a loss \(\ell(y,f(x))\) taking values in \([0,1]\), and write \(P\ell_f=E[\ell(Y,f(X))]\) and \(P_n\ell_f=n^{-1}\sum_{i=1}^n\ell(Y_i,f(X_i))\).

Assume that some \(f_0\in\mathcal F\) minimizes population risk over \(\mathcal F\). For each \(f\), its excess loss relative to \(f_0\) is the random variable \(g_f(Z)=\ell(Y,f(X))-\ell(Y,f_0(X))\). Its mean is the excess risk \(\mu_f=Pg_f=P\ell_f-P\ell_{f_0}\), which is nonnegative. An empirical risk minimizer is any \(\hat f\in\mathcal F\) satisfying \(P_n\ell_{\hat f}=\min_{f\in\mathcal F}P_n\ell_f\).

Here \(g_f\in[-1,1]\), because each loss is in \([0,1]\). The condition says that when a score has small excess risk, its excess loss also has small second moment. The case \(\beta=1\) is especially consequential: the variance is at most proportional to the excess risk, rather than merely being bounded by a constant.

A Localized Excess-Risk Bound

The key concentration step is Bernstein's inequality. In the form needed here, if \(W_1,\ldots,W_n\) are independent copies of a random variable \(W\) with finite variance and \(|W-EW|\leq 2\), then for \(t>0\), $$ P\left(\frac{1}{n}\sum_{i=1}^n W_i<EW-\sqrt{\frac{2\operatorname{Var}(W)t}{n}}-\frac{4t}{3n}\right)\leq e^{-t}. $$ For an excess loss \(g_f\), the centered variable has absolute value at most \(2\), so the stated version applies. Taking \(t=\log(M/\delta)\) and using a union bound over the \(M\) candidates gives, with probability at least \(1-\delta\), the lower inequality below simultaneously for all \(f\). The variance term can then be bounded using the Bernstein condition.

Proof. Set \(t=\log(M/\delta)\). For each \(f\), apply the one-sided Bernstein inequality to \(g_f(Z_i)\), whose mean is \(\mu_f\). A union bound shows that, with probability at least \(1-\delta\), every \(f\in\mathcal F\) satisfies $$ P_ng_f\geq \mu_f-\sqrt{\frac{2\operatorname{Var}(g_f)t}{n}}-\frac{4t}{3n} \geq \mu_f-\sqrt{2Bs\,\mu_f^\beta}-\frac{4}{3}s. $$ On this event, empirical minimization gives \(P_ng_{\hat f}\leq0\), since \(f_0\in\mathcal F\). Write \(\mu=\mu_{\hat f}\). Combining the two inequalities yields $$ \mu\leq \sqrt{2Bs}\,\mu^{\beta/2}+\frac{4}{3}s. $$ Set \(a=\sqrt{2Bs}\), \(c=4s/3\), and \(\alpha=\beta/2<1\). If \(\mu\leq2c\), then \(\mu\leq2c+a^{1/(1-\alpha)}2^{1/(1-\alpha)}\) immediately. If \(\mu>2c\), then \(\mu-c>\mu/2\); the displayed inequality implies \(\mu/2<a\mu^\alpha\). Dividing by \(\mu^\alpha>0\) and raising both sides to the power \(1/(1-\alpha)\) gives $$ \mu<(2a)^{1/(1-\alpha)}=(8Bs)^{1/(2-\beta)}. $$ In either case, \(\mu\leq (8Bs)^{1/(2-\beta)}+2c\), and \(2c=8s/3\). Finally \(0\leq\mu\leq1\) because both risks lie in \([0,1]\), so we may also take the minimum with \(1\). \(\square\)

Why This Improves on Global Uniform Deviation

For comparison, Hoeffding's inequality and a union bound give a global deviation statement: with probability at least \(1-\delta\), every candidate satisfies $$ |P_ng_f-Pg_f|\leq\sqrt{\frac{2\log(2M/\delta)}{n}}. $$ On that event, \(P_ng_{\hat f}\leq0\) implies \(\mu_{\hat f}\leq2\sqrt{2\log(2M/\delta)/n}\). This rate is proportional to \(n^{-1/2}\), regardless of how little variance the excess losses have near the optimum. Under the Bernstein condition, the theorem instead has leading order \(s^{1/(2-\beta)}\). For \(\beta=1\), this is order \(n^{-1}\), up to the logarithm of the class size; for \(\beta=0\), it is order \(n^{-1/2}\). The improvement comes from controlling fluctuations at the scale of the excess risk, not from changing the empirical minimization rule.

Reading the Bound Correctly

The theorem is finite-class and compares the empirical minimizer with the best population-risk score in that class. It does not by itself control the gap between that best score and the Bayes classifier. Nor does it establish the Bernstein condition from the RKHS norm constraint. For an infinite score class, a corresponding result needs a uniform localized deviation bound; the class-size term must be replaced by an appropriate local complexity or entropy control. A finite candidate dictionary avoids that additional step while retaining the variance-based rate mechanism.

The earlier material on margin conditions gives one route for understanding when low-noise assumptions can lead to variance control for classification losses. But the implication depends on the chosen surrogate and on how its excess loss relates to classification risk. In an application, verify the relevant condition for the actual loss and comparator rather than inferring it solely from the presence of a margin assumption.