Uniform Deviation Bounds for Norm-Constrained Kernel Scores

Why Uniform Deviation Matters

A small empirical surrogate risk does not by itself guarantee a small population risk: the training sample is only one draw from the data distribution. For kernel scores, a useful guarantee controls this discrepancy simultaneously for every score in a specified norm ball. That uniformity lets a later analysis apply the bound to a data-dependent score without assuming that the score was fixed before seeing the sample.

The central ingredients are the reproducing property of an RKHS and Rademacher complexity. A bound on the kernel diagonal limits how large any norm-constrained score can be at an observed input. Rademacher complexity then measures how much the whole score class can fluctuate over a sample.

Setup and Definitions

Let \(Z=(X,Y)\) have distribution \(P\), with \(Y\in\{-1,1\}\), and let \(Z_1,\ldots,Z_n\) be independent draws from \(P\). Write \(P_n\) for their empirical distribution: \(P_n g=n^{-1}\sum_{i=1}^n g(Z_i)\), while \(Pg=E[g(Z)]\). Let \(\mathcal H\) be a reproducing-kernel Hilbert space with measurable kernel \(k\), and write \(k_x=k(x,\cdot)\). The reproducing property is \(f(x)=\langle f,k_x\rangle_{\mathcal H}\).

Assume \(k(x,x)\leq\kappa^2\) on the input support, for a finite \(\kappa\). Assume \(\ell\) is measurable, nonnegative, and uniformly \(L\)-Lipschitz in its score argument: \(\left|\ell(y,t)-\ell(y,s)\right|\leq L|t-s|\) for all \(y,s,t\). Also assume \(\ell(y,0)\leq B_0\) for every \(y\). We take the suprema below to be measurable; for example, it is enough to impose the usual pointwise measurability condition on the function classes.

By the reproducing property and Cauchy–Schwarz, \(|f(x)|\leq\|f\|_{\mathcal H}\sqrt{k(x,x)}\leq R\kappa\) for every \(f\in\mathcal F_R\). Consequently every loss in the class takes values in \([0,M]\), where \(M=B_0+LR\kappa\). This boundedness will be needed for the probability statement.

Rademacher Complexity of the Score Ball

For fixed inputs \(x_1,\ldots,x_n\), let \(\sigma_1,\ldots,\sigma_n\) be independent signs, each equal to \(1\) or \(-1\) with probability \(1/2\). The empirical Rademacher complexity of the score class is \(\widehat{\mathfrak R}_S(\mathcal F_R)=E_\sigma[\sup_{f\in\mathcal F_R}n^{-1}\sum_{i=1}^n\sigma_i f(x_i)]\). The ball is symmetric about zero, so this supremum also equals the supremum of the absolute value of the signed sum.

To verify the equality, maximize \(\langle f,\sum_i\sigma_i k_{x_i}\rangle_{\mathcal H}\) over \(\|f\|_{\mathcal H}\leq R\). Its supremum is \(R\|\sum_i\sigma_i k_{x_i}\|_{\mathcal H}\), by Cauchy–Schwarz, with equality in the direction of the sum when it is nonzero. For the first inequality, Jensen’s inequality gives \(E_\sigma\|V\|_{\mathcal H}\leq\sqrt{E_\sigma\|V\|_{\mathcal H}^2}\), with \(V=\sum_i\sigma_i k_{x_i}\). Expanding the squared norm, the cross terms have expectation zero because \(E[\sigma_i\sigma_j]=0\) for \(i\ne j\), while \(E[\sigma_i^2]=1\). Thus \(E_\sigma\|V\|_{\mathcal H}^2=\sum_i\|k_{x_i}\|_{\mathcal H}^2=\sum_i k(x_i,x_i)\). The diagonal bound gives the final inequality. This calculation is the source of the \(R\kappa/\sqrt n\) rate.

Uniform Deviation Bound

The Rademacher bound for scores must be transferred to losses. The standard Rademacher contraction inequality says that if a set \(T\subset\mathbb R^n\) contains the zero vector and each map \(\psi_i:\mathbb R\to\mathbb R\) is \(L\)-Lipschitz with \(\psi_i(0)=0\), then \(E_\sigma\sup_{t\in T}|\sum_i\sigma_i\psi_i(t_i)|\leq 2L E_\sigma\sup_{t\in T}|\sum_i\sigma_i t_i|\). The zero-at-zero condition is important: it applies to the centered loss \(\ell(y,t)-\ell(y,0)\), not automatically to the original loss.

Proof. Split the loss into a baseline and a score-dependent increment: \(\ell(Y,f(X))=\ell(Y,0)+h_f(X,Y)\), where \(h_f(x,y)=\ell(y,f(x))-\ell(y,0)\). The baseline has \(0\leq\ell(Y,0)\leq B_0\). Independence and the variance bound \(\operatorname{Var}(\ell(Y,0))\leq E[\ell(Y,0)^2]\leq B_0^2\) imply \(E|P_n\ell(\cdot,0)-P\ell(\cdot,0)|\leq B_0/\sqrt n\), by Cauchy–Schwarz.

For the increments, symmetrization with an independent sample \(Z'_1,\ldots,Z'_n\) gives \(E\sup_f|P_nh_f-Ph_f|\leq 2E_{S,\sigma}\sup_f|n^{-1}\sum_i\sigma_i h_f(Z_i)|\). This follows by replacing \(Ph_f\) with the conditional expectation of \(n^{-1}\sum_i h_f(Z'_i)\), applying Jensen’s inequality to the supremum, and then using the symmetry of each pair \((Z_i,Z'_i)\) to introduce the signs. The triangle inequality yields the factor \(2\).

For a fixed sample, apply the contraction inequality to \(T=\{(f(X_1),\ldots,f(X_n)):f\in\mathcal F_R\}\), which contains zero, using \(\psi_i(t)=\ell(Y_i,t)-\ell(Y_i,0)\). These maps vanish at zero and are \(L\)-Lipschitz. Thus the expected absolute signed sum for the increments is at most \(2L\) times that for the score class. The score calculation above bounds the latter, after division by \(n\), by \(R\kappa/\sqrt n\). The increment deviation is therefore at most \(4LR\kappa/\sqrt n\). Adding the baseline deviation proves the expectation bound.

Finally, let \(Z_S=\sup_f|P_n\ell_f-P\ell_f|\). Replacing one observation changes \(Z_S\) by at most \(M/n\), because every loss lies in \([0,M]\). McDiarmid’s bounded-differences inequality therefore gives \(P(Z_S-EZ_S\geq t)\leq\exp(-2nt^2/M^2)\). Taking \(t=M\sqrt{\log(1/\delta)/(2n)}\) and using the expectation bound proves the probability statement. \(\square\)

Interpreting the Bound and Avoiding a Common Error

The bound separates several influences. Increasing \(n\) reduces both terms at the usual \(n^{-1/2}\) rate. Increasing the norm radius \(R\) or the diagonal bound \(\kappa\) enlarges the score class’s possible fluctuations. A larger Lipschitz constant \(L\) makes changes in score translate into larger changes in loss. The result controls only the empirical-to-population discrepancy; it does not say that either risk is small, nor does it measure approximation error.

Common mistake: applying contraction to the uncentered loss without checking its value at zero. The contraction inequality stated above requires \(\psi_i(0)=0\). For hinge loss, for instance, \(\ell(y,0)=1\), not zero. Applying the zero-at-zero form directly to \(\ell(y,t)\) skips a required condition. Centering gives \(\psi_i(t)=\ell(y,t)-\ell(y,0)\); the remaining baseline is handled separately, which is why the theorem includes the \(B_0/\sqrt n\) term.

Uniformity is what makes the guarantee useful for scores selected from the data: on the event in the theorem, it holds for every \(f\in\mathcal F_R\), and hence also for any data-dependent choice that lies in that ball. The bound does not require that choice to be independent of the sample.