Adaptation to Unknown Source Smoothness

Why Compare Fits Along a Regularization Path?

A regularization parameter chosen for a known source exponent can balance approximation bias against stochastic error. When the exponent is unknown, that balance is not directly available: a choice that is suitable for a rough target can be unnecessarily conservative for a smooth one. Lepski's method replaces the unknown exponent with observable comparisons among fits at different regularization levels.

The idea is to prefer a less variable fit unless comparisons with more flexible fits reveal a discrepancy too large to be explained by stochastic error. To make that principle precise, the path must be ordered, the comparison thresholds must reflect the growth of variance, and a simultaneous error event must hold across the path. The conclusion is an oracle inequality: the selected fit performs, up to a constant, as well as a candidate chosen with knowledge of the smoothness.

Path, Error Bounds, and Selector

Let \(\hat f_j\), \(j=0,\ldots,M\), be kernel ridge regression (KRR) fits computed from the same data, with regularization parameters \(\lambda_0>\lambda_1>\cdots>\lambda_M>0\). Increasing \(j\) means decreasing regularization and, in the setting considered here, increasing variance. Measure prediction error in a fixed norm \(\|\cdot\|\). Let \(f\) denote the target, and let \(f_j^0\) be a deterministic centering for the \(j\)th fit; the centering may depend on the target and the design distribution, but not on the realized response noise.

The first inequality controls approximation error, and the second controls the random deviation of the fitted path. For a KRR source condition with exponent \(s>0\) and source radius \(R\), a standard bias bound has \(B_j=R\lambda_j^s\) over the range of exponents for which that bound applies. We do not require a particular formula for \(V_j\) in the pathwise result below; it must be a valid variance proxy and must be nondecreasing along the chosen path.

The comparison uses \(V_k\), the proxy for the more variable fit in each pair. A fit at a smaller index is retained if its differences from all finer fits are consistent with the error scale of those finer fits. The selector needs the ordered path, the proxies, and the threshold, but it does not use the source exponent.

A Pathwise Oracle Inequality

Here is the central guarantee. It applies to any index whose bias is no larger than the scale of its stochastic error, and so can be used with the index that would be attractive if the smoothness were known.

Proof. First, \(j_*\) passes all its comparisons. For any \(k>j_*\), use the triangle inequality, the bias bounds, and the stochastic bounds on \(\mathcal E\): \[ \|\hat f_{j_*}-\hat f_k\| \le \|\hat f_{j_*}-f_{j_*}^0\|+\|f_{j_*}^0-f\| +\|f-f_k^0\|+\|f_k^0-\hat f_k\|. \] The two stochastic terms are at most \(c\sqrt{V_{j_*}}\) and \(c\sqrt{V_k}\). The bias terms are at most \(B_{j_*}\) and \(B_k\). Since \(B_k\le B_{j_*}\le\sqrt{V_{j_*}}\), and \(V_{j_*}\le V_k\), this gives \[ \|\hat f_{j_*}-\hat f_k\|\le2(1+c)\sqrt{V_k}\le A\sqrt{V_k}. \] Therefore \(j_*\) is admissible, so the minimum admissible index satisfies \(\hat j\le j_*\).

If \(\hat j<j_*\), admissibility of \(\hat j\), applied to \(k=j_*\), gives \(\|\hat f_{\hat j}-\hat f_{j_*}\|\le A\sqrt{V_{j_*}}\). If \(\hat j=j_*\), this difference is zero, so the same bound holds. Also, \[ \|\hat f_{j_*}-f\|\le\|\hat f_{j_*}-f_{j_*}^0\|+\|f_{j_*}^0-f\| \le(c+1)\sqrt{V_{j_*}}. \] A final triangle inequality yields the claimed bound. Squaring both nonnegative sides gives the squared-error conclusion. \(\square\)

This result is pathwise: its proof is deterministic once the simultaneous event holds. If the event has probability at least \(1-\delta\), the oracle inequality has that same probability. It does not, by itself, assert an expectation bound; such a bound would require additional control of the error on the complement of \(\mathcal E\).

Source Smoothness and a Geometric Grid

To connect the pathwise result to source smoothness, use the bias bound \(B_j=R\lambda_j^s\), where \(R>0\) and \(s>0\). Suppose the grid is geometric, \(\lambda_j=\lambda_0\rho^j\) for \(0<\rho<1\), and \(V_j\) is nondecreasing with \(V_{j+1}\le qV_j\) for some \(q\ge1\). The latter is a one-step condition: it limits the variance increase between adjacent candidates, not between arbitrary candidates.

Assume there is a crossing index \(j_s\): it is the smallest index with \(R^2\lambda_{j_s}^{2s}\le V_{j_s}\). If there is no such index, the path never reaches the bias-variance balance, and the interior crossing argument below does not apply. If \(j_s=0\), the first candidate already balances. For an interior crossing \(j_s\ge1\), the next result shows that the balance candidate is within a constant factor of the best grid objective.

Proof. At \(j_s\), the crossing condition gives \(R^2\lambda_{j_s}^{2s}\le V_{j_s}\), so the left-hand objective is at most \(2V_{j_s}\). For every \(j\ge j_s\), monotonicity of the variance proxies gives \(R^2\lambda_j^{2s}+V_j\ge V_j\ge V_{j_s}\).

Now take \(j<j_s\). Minimality of \(j_s\) gives \(R^2\lambda_{j_s-1}^{2s}>V_{j_s-1}\). Since \(j\le j_s-1\), \(\lambda_j\ge\lambda_{j_s-1}\), and \(s>0\), so \[ R^2\lambda_j^{2s}\ge R^2\lambda_{j_s-1}^{2s}>V_{j_s-1}. \] The one-step grid condition then gives \[ V_{j_s}\le qV_{j_s-1}<qR^2\lambda_j^{2s} \le q\bigl(R^2\lambda_j^{2s}+V_j\bigr). \] Thus every candidate objective is at least \(V_{j_s}/q\): for indices at or beyond \(j_s\) it is at least \(V_{j_s}\), and before \(j_s\) the displayed inequality gives the claim. Its minimum is therefore at least \(V_{j_s}/q\). Combining this lower bound with the upper bound \(2V_{j_s}\) proves the result. \(\square\)

What the Adaptation Guarantee Does—and Does Not—Say

Suppose the source exponents of interest lie in a range where \(R\lambda_j^s\) is a valid bias bound and a crossing candidate is available. For each such \(s\), the crossing index \(j_s\) satisfies \(B_{j_s}\le\sqrt{V_{j_s}}\), so the pathwise theorem applies. The selector is the same rule for all those exponents: it compares the observed fits and does not need to know which \(j_s\) is appropriate. The grid result then compares the corresponding oracle objective with the best objective on the grid. Together these statements yield adaptation over the stated range, on the simultaneous event.

This is an oracle inequality over the candidates, not an unconditional claim that every KRR implementation attains a particular rate. The result depends on valid simultaneous stochastic bounds, monotone bias and variance envelopes, and adequate coverage of the relevant balance by the path. Constants, confidence levels, endpoint effects, and the assumptions behind the KRR bounds remain important. A range of source exponents cannot be claimed beyond the range where the bias bound and crossing assumptions hold.

Common mistake: From \(V_{j+1}\le qV_j\), it is incorrect to infer \(V_k\le qV_j\) whenever \(j<k\). Iterating the condition gives only \(V_k\le q^{k-j}V_j\). The correction in the grid proof is to use the immediately preceding candidate \(j_s-1\), where the crossing has not yet occurred, and apply the one-step condition only to \(V_{j_s}\) and \(V_{j_s-1}\). This is exactly what permits a comparison with the earlier candidate's bias term without imposing a false bound on a multi-step variance increase.