Logarithmic Costs of Adaptation Across Smoothness

Why Adaptation Can Cost a Logarithm

If source smoothness is known, a regularization parameter can be tuned to balance approximation bias and variance. When smoothness is unknown, one can fit candidates at several regularization levels and select among them. The selection step has its own statistical cost: a procedure that compares many candidates must control the chance that one looks good just by noise. A union bound commonly makes this cost proportional to the logarithm of the number of candidates.

That logarithm does not always worsen the final rate. If the candidate count grows only logarithmically with sample size, the selection remainder may be much smaller than the nonparametric risk. But if the target rate is already of order \(1/n\), the same remainder can change the rate by a logarithmic factor. The distinction depends both on the smoothness range and on how the candidates are compared.

Known-Smoothness Rates and a Smoothness Grid

Work with prediction risk and suppose, over the source-exponent range under consideration, that a kernel ridge estimator with regularization parameter \(\lambda\) satisfies a bound of the form

Here \(f_\rho\) is the regression function, \(r\) is the source exponent, \(q>0\) describes the effective-dimension growth, and \(C\) is independent of \(n\) and \(\lambda\) over the stated range. This is a rate premise: it requires the source-bias and variance conditions that justify the two terms, and the range of \(r\) must not exceed the estimator's qualification. The argument below concerns the cost of selecting \(\lambda\), not a derivation of those KRR bounds.

For a fixed \(r\), balancing the two terms gives

Substitution yields the known-smoothness rate \(n^{-2r/(2r+q)}\). If \(r\) ranges over a fixed interval \([r_{\min},r_{\max}]\), use a geometric grid of regularization parameters covering the corresponding interval from \(n^{-1/(2r_{\min}+q)}\) to \(n^{-1/(2r_{\max}+q)}\). A factor-of-two grid has \(M=O(\log n)\) candidates, since the logarithm of the ratio of these endpoints is a constant times \(\log n\).

A grid approximates the ideal choice without requiring the exact \(r\). If a grid point \(\lambda_j\) is within a factor of two of \(\lambda_r\), then \(\lambda_j^{2r}\le 2^{2r}\lambda_r^{2r}\) and \(\lambda_j^{-q}/n\le 2^q\lambda_r^{-q}/n\). Consequently, the best grid candidate has the known-smoothness rate up to a constant uniform over a bounded range of \(r\).

A Finite-Candidate Selection Bound

The following result isolates the candidate-selection cost. It applies conditionally on a training sample: the candidate predictors are then fixed, and a separate validation sample of size \(m\) is used to choose one. Write \(R_j\) for the population risk of candidate \(j\), and let \(j_*\) minimize \(R_j\) among the \(M\) candidates. Define the excess \(\Delta_j=R_j-R_{j_*}\), which is nonnegative, and let \(Z_{j,i}\) be the validation loss of candidate \(j\) minus that of candidate \(j_*\) on observation \(i\). Assume the validation observations are independent and identically distributed, and, for every \(j\),

for constants \(v,b>0\). The variance condition is a Bernstein condition on these risk differences; it is an assumption, not a consequence of bounded losses alone. Select \(\hat j\) to minimize the average validation loss.

Proof. For each candidate \(j\), apply the one-sided lower-tail Bernstein inequality to the centered variables \(Z_{j,i}-\Delta_j\). For \(t>0\), the probability that the empirical mean falls below its expectation by more than \(\sqrt{2v\Delta_jt/m}+2bt/(3m)\) is at most \(e^{-t}\). A union bound over the \(M\) candidates makes all these lower-tail bounds hold at once with probability at least \(1-Me^{-t}\). Set \(t=\log(M/\delta)\), so this probability is at least \(1-\delta\).

On this simultaneous event, write \(\hat\Delta=R_{\hat j}-R_{j_*}\). Because \(\hat j\) minimizes validation loss and the comparator \(j_*\) is itself a candidate, the empirical mean of \(Z_{\hat j,i}\) is at most zero. The lower-tail bound for the selected candidate therefore implies

For \(x\ge0\), \(\sqrt{2vxt/m}\le x/2+vt/m\), as follows by squaring the equivalent inequality \(\sqrt{2vxt/m}-x/2\le vt/m\), or from \(2\sqrt{ab}\le a+b\) with \(a=x/2\) and \(b=vt/m\). Applying this bound gives

Substituting \(t=\log(M/\delta)\) proves the claim. \(\square\)

The one-sided argument is important. The selected candidate is known to have empirical risk no greater than the comparator's, so only a lower-tail deviation is needed. A two-sided Bernstein bound would carry an extra factor of two in its exceptional probability; using it as though the probability were \(e^{-t}\) would not justify the same union-bound event.

When the Logarithm Changes the Rate

For a grid with \(M=O(\log n)\), the selection bound involves \(\log(M/\delta)=O(\log\log n+\log(1/\delta))\). If a fixed fraction of the data is reserved for validation, then both training and validation sample sizes remain proportional to the total sample size. Combining the best grid candidate's KRR bound with the selection theorem gives, schematically,

This conclusion requires the risk bound for the trained candidates and the validation Bernstein condition; it is not automatic for arbitrary KRR fits. When \(q>0\) and \(r\) is finite, the exponent \(2r/(2r+q)\) is strictly less than one. Hence the nonparametric term decays more slowly than \((\log\log n)/n\), and the validation remainder does not change that rate. It may still matter for finite samples or for a detailed bound.

If the oracle risk is of order \(1/n\), an additive \((\log\log n)/n\) remainder is not negligible relative to it. More generally, a union bound over \(M\) candidates contributes \(\log M\): if \(M\) grows like a power of \(n\), this becomes a \(\log n\) factor in the remainder. The count of candidates matters; “adaptation costs a logarithm” is incomplete unless it specifies which logarithm and how it compares with the oracle rate.

When the Penalty Can Be Avoided

A union-bound penalty is a feature of this proof strategy, not a universal law that every adaptive procedure must pay. Several distinctions are useful:

• Fixed candidate sets. If \(M\) is bounded independently of \(n\), then \(\log M\) is a constant. This removes growth in the candidate-count term, though it only adapts over the fixed set.
• A direct uniform bound. If the KRR family admits a concentration or oracle inequality uniform over the regularization parameter, with complexity controlled independently of the grid cardinality, a separate union bound over grid points is unnecessary. Such a result must be proved under its own assumptions; one cannot infer it merely by writing down a continuum of tuning parameters.
• Stronger structure for selection. A selector may avoid the generic finite-class remainder when the candidate risks have additional structure that permits sharper comparison. This requires a theorem for that selector and structure; the finite-candidate result above does not supply it.
• Restrictions on the adaptation goal. If smoothness is known, or the task is only to choose among a fixed number of prespecified smoothness values, there is no growing grid to pay for. This is a smaller adaptation problem, not a free solution to unrestricted adaptation.

In particular, a simultaneous high-probability KRR bound over many \(\lambda\)'s sometimes appears with \(\log(M/\delta)\) because the proof controls \(M\) separate events. Removing that factor requires a valid uniform argument, or a different selection guarantee; simply omitting the union bound does not establish a log-free result. Conversely, the presence of a logarithm in one bound does not by itself prove that the logarithm is necessary for every method or every source class.

Common Pitfall

A tempting argument is: “There are \(M\) candidates, so the adaptive KRR rate must be the oracle rate multiplied by \(\log M\).” That conclusion does not follow. The finite-candidate theorem gives an additive remainder of order \(\log(M/\delta)/m\) under a Bernstein condition. To decide whether this changes the rate, compare that remainder with the oracle rate. With \(M=O(\log n)\) and a strictly subparametric oracle rate, the remainder can be asymptotically smaller. With an oracle rate \(1/n\), it need not be.

A second error is to use a two-sided deviation inequality with a one-sided exceptional probability. The correction is to use the lower-tail inequality for the selected candidate: empirical risk minimization guarantees its empirical risk is no larger than the comparator's, so the lower tail alone yields the bound. The resulting probability and constants must still be carried through the union bound and the final algebra.