Oracle Regularization for Known Smoothness

Why an Oracle Regularization Level?

Kernel ridge regression balances two effects of regularization. A larger \(\lambda\) generally increases approximation bias, while a smaller \(\lambda\) allows more noisy directions to contribute to variance. When the target’s source smoothness and the spectrum’s effective-dimension growth are known, this tradeoff gives a specific regularization level that minimizes a stated risk bound. This is an oracle choice: it uses properties of the data-generating problem that would not usually be known in practice.

The object optimized here is the bound, not necessarily the exact finite-sample prediction risk. That distinction matters: constants in the bound may be conservative, and the bound may not capture every detail of the risk. Nevertheless, its minimizer identifies the right scale of regularization under the stated assumptions.

The Source-and-Spectrum Bound

Let \(T\) be the covariance operator associated with the kernel features, and let \(f_\lambda\) denote the population target approximant induced by regularization level \(\lambda>0\). Under a source condition, the target lies in a smoothness class controlled by an exponent \(r>0\) and radius \(R\). In the range where the bias result applies, the squared prediction bias is bounded by a constant times \(R^2\lambda^{2r}\). Separately, suppose the effective dimension satisfies \(\mathcal{N}(\lambda)\le Q\lambda^{-\alpha}\), for constants \(Q>0\) and \(\alpha>0\), over the regularization range of interest. The effective-dimension variance bound is then of order \(\sigma^2\mathcal{N}(\lambda)/n\).

For example, if the bias result gives \(C_b R^2\lambda^{2r}\), and the variance result gives \(C_v\sigma^2 Q\lambda^{-\alpha}/n\), then \(A=C_bR^2\) and \(D=C_v\sigma^2Q\). In a high-probability result, the constants may also depend on the specified confidence level; the optimization below applies once those constants are fixed. If a source condition has greater smoothness than the bias bound can use, \(r\) here must be the exponent in the applicable bias bound, not an unsupported larger exponent.

We optimize over positive \(\lambda\) for which the bound is valid. If the method imposes an interval of admissible regularization levels, the unconstrained minimizer is used when it lies in the interval; otherwise the minimum over that interval occurs at the nearer endpoint in log scale.

Deriving the Oracle Level

The oracle level follows by minimizing \(B_n(\lambda)\). The derivative is

The first term is positive and the second negative. Setting the derivative to zero equates the marginal increase in bias to the marginal decrease in variance.

Proof. Differentiating and multiplying the stationary-point equation by the positive quantity \(\lambda^{\alpha+1}\) shows that \(B_n'(\lambda)=0\) exactly when

The left side is strictly increasing from zero to infinity as \(\lambda\) increases from zero to infinity. There is therefore exactly one positive solution, namely \(\lambda_{\mathrm{or}}\). Also, \(B_n'(\lambda)<0\) below that solution and \(B_n'(\lambda)>0\) above it, so it is the unique global minimum. At the stationary point,

Substituting this relationship into the bound gives \(B_n(\lambda_{\mathrm{or}})=(1+2r/\alpha)A\lambda_{\mathrm{or}}^{2r}\). Inserting the expression for \(\lambda_{\mathrm{or}}\) proves the displayed minimum. \(\square\)

The oracle level decreases with sample size at rate \(n^{-1/(2r+\alpha)}\). Substitution into the bound gives rate \(n^{-2r/(2r+\alpha)}\), with constants depending on \(A,D,r,\alpha\). Greater usable smoothness \(r\) permits a smaller bias at a given \(\lambda\); stronger effective-dimension growth \(\alpha\) makes the variance penalty increase more rapidly as \(\lambda\) shrinks.

How Much Does a Tuning Error Cost?

A useful sensitivity calculation compares a chosen level \(\lambda=c\lambda_{\mathrm{or}}\) with the oracle, where \(c>0\) is a multiplicative error. At the oracle, the variance term is \(2r/\alpha\) times the bias term. Scaling \(\lambda\) by \(c\) multiplies the bias by \(c^{2r}\), and the variance by \(c^{-\alpha}\). Consequently the ratio of bounds is exactly

This ratio equals one at \(c=1\), decreases before the oracle and increases after it. A simple bound, useful when only the size of the error is known, is

Indeed, the ratio is a weighted average of \(c^{2r}\) and \(c^{-\alpha}\), with positive weights that sum to one. The exact expression is sharper and also shows the asymmetry: under-regularization can be more costly when \(\alpha\) is large, while over-regularization can be more costly when \(2r\) is large.

Sensitivity is also important when the regularization sequence has the wrong power of \(n\). If \(\lambda_n=n^{-a}\) for a fixed \(a>0\), then the two terms have orders \(n^{-2ra}\) and \(n^{-1+\alpha a}\). When both terms decay, their sum has order \(n^{-q(a)}\), where

The first exponent increases with \(a\), while the second decreases. Their minimum is largest when they are equal, at \(a=1/(2r+\alpha)\), exactly the oracle scaling. This gives a rate-level way to assess tuning error: a fixed multiplicative error in the oracle level changes constants, whereas using the wrong power of \(n\) can worsen the convergence rate.

Common Pitfall and Practical Meaning

• Confusing a bound minimizer with an exact-risk minimizer. The derivative calculation establishes the minimum of \(B_n(\lambda)\), not of the unknown finite-sample risk. The oracle is defined relative to the bound.
• Balancing the two terms as if they must be equal. The correct stationary condition is \(2r\) times the bias term equals \(\alpha\) times the variance term. They are equal only when \(2r=\alpha\).
• Ignoring the exponent convention. If the bias term is \(\lambda^{2r}\), its exponent in the tuning formula is \(2r\), not \(r\). Substituting \(r\) in its place changes both the oracle scale and the risk rate.
• Using smoothness that the bias result does not support. The optimization cannot create a stronger bias bound than the source-condition result provides. Use the applicable bias exponent and constants.

When \(A,D,r,\alpha\) are known, the formula gives a transparent benchmark for the scale and rate of regularization. When they are not known, the oracle calculation remains useful for understanding what an ideal choice would achieve, but selecting a data-dependent level is a separate problem. In particular, this calculation alone does not provide a method for adapting to unknown smoothness.