Choosing Models When the Noise Exponent Is Unknown

Why Unknown Noise Changes Model Selection

A classifier trained in a simple model may have modest estimation error but substantial approximation error; a richer model may reduce approximation error while becoming more variable. Under low-noise conditions, the balance can favor substantially richer models than it would under a generic slow-rate bound. But the appropriate balance depends on the noise exponent, which is rarely known. A useful goal is therefore not to estimate that exponent first, but to select among candidate classifiers without putting it into the selection rule.

We study a finite list of fitted classifiers, one for each candidate complexity level, and select among them using an independent validation sample. The result is an oracle comparison: the selected classifier performs nearly as well as the best candidate on the population, with a remainder whose rate is fast when the margin condition is strong. The result concerns selection among the candidates actually supplied; it does not guarantee that any candidate has good approximation or training error.

Margin Condition and Disagreement

Let \(X\) be a covariate, \(Y\in\{0,1\}\) a label, and \(\eta(x)=P(Y=1\mid X=x)\). A Bayes classifier is \(h^*(x)=\mathbf{1}\{\eta(x)\geq 1/2\}\). Define the margin variable \(M(X)=|2\eta(X)-1|\). For a classifier \(h\), write \(R(h)=P(h(X)\neq Y)\) and \(r(h)=R(h)-R(h^*)\) for its excess risk. The standard classification identity is \(r(h)=E[M(X)\mathbf{1}\{h(X)\neq h^*(X)\}]\).

The condition controls how often the covariate lies close to the decision boundary. That control bounds the probability that a classifier disagrees with the Bayes rule, even when its excess risk is small. For \(q>0\), let \(D(h)=P(h(X)\neq h^*(X))\). For any \(t\in(0,1]\), \(D(h)\leq P(M(X)\leq t)+P(h(X)\neq h^*(X),\,M(X)>t)\leq C_0t^q+r(h)/t\). If \(0<r(h)\leq1\), choose \(t=r(h)^{1/(q+1)}\); the resulting bound is \(D(h)\leq(C_0+1)r(h)^\beta\). If \(r(h)=0\), the risk identity implies disagreement can occur only at zero margin, which has probability zero when \(q>0\). For \(q=0\), simply use \(D(h)\leq1\). Thus, with a finite constant \(C_1\) depending only on \(C_0,q\), we have \(D(h)\leq C_1r(h)^\beta\), interpreting \(r^0\) as \(1\) in the \(q=0\) case.

Validation Selection and the Oracle Bound

Suppose training data have produced \(M\) classifiers \(h_1,\ldots,h_M\), possibly from models of different complexity. Assume they are fixed independently of a validation sample \((X_i,Y_i)_{i=1}^m\) of independent observations from the same distribution. Select a classifier with the smallest validation error: \(\hat j\in\arg\min_{1\leq j\leq M} m^{-1}\sum_{i=1}^m\mathbf{1}\{h_j(X_i)\neq Y_i\}\), breaking ties by any fixed rule, and set \(\hat h=h_{\hat j}\). Let \(j^*\) be an index minimizing population risk among these candidates.

Here and below the probability statement can be read conditional on the training data: once the candidates are fixed, the only randomness is in validation. If training and validation observations are sampled independently, the conditional bound also gives the corresponding unconditional guarantee.

Proof. Fix a candidate \(h_j\) and the population-best candidate \(h_{j^*}\). Define \(W=\mathbf{1}\{h_j(X)\neq Y\}-\mathbf{1}\{h_{j^*}(X)\neq Y\}\). Then \(W\in[-1,1]\), \(E[W]=r(h_j)-r(h_{j^*})\), and \(\operatorname{Var}(W)\leq E[W^2]=P(h_j(X)\neq h_{j^*}(X))\). By the triangle inequality for disagreement events and the bound just derived, \[ \operatorname{Var}(W)\leq D(h_j)+D(h_{j^*}) \leq C_1\big(r(h_j)^\beta+r(h_{j^*})^\beta\big) \leq 2C_1\big(r(h_j)+r(h_{j^*})\big)^\beta \] when \(q>0\). The last inequality uses \(u^\beta+v^\beta\leq2(u+v)^\beta\). When \(q=0\), the same display holds with a suitably chosen constant and exponent zero.

Bernstein’s inequality for independent bounded variables states that, for \(m\) independent copies of \(W\) and \(x>0\), their empirical mean is less than its expectation by at most \(\sqrt{2\operatorname{Var}(W)x/m}+2x/(3m)\), except on an event of probability at most \(e^{-x}\). Apply this inequality to each of the \(M\) candidates against \(h_{j^*}\), and take \(x=\log(M/\delta)\). A union bound makes all these comparisons hold simultaneously with probability at least \(1-\delta\). The empirical risk of \(\hat h\) is no greater than that of \(h_{j^*}\), so on this event, writing \(r_{\hat h}=r(\hat h)\) and \(r_*=r(h_{j^*})\), \[ r_{\hat h}-r_* \leq 2\sqrt{C_1a}\,(r_{\hat h}+r_*)^{\beta/2}+\frac{2a}{3}. \]

For \(0\leq\beta<1\), there is a finite constant \(C_2\), depending only on \(C_1,\beta\), such that \(2\sqrt{C_1a}\,s^{\beta/2}\leq s/2+C_2a^{1/(2-\beta)}\) for all \(s\geq0\). This follows by maximizing \(2\sqrt{C_1a}\,s^{\beta/2}-s/2\); its maximum is a constant times \(a^{1/(2-\beta)}\). Use this inequality with \(s=r_{\hat h}+r_*\). Since \(s=(r_{\hat h}-r_*)+2r_*\), we obtain \(r_{\hat h}-r_*\leq(r_{\hat h}-r_*)/2+r_*+C_2a^{1/(2-\beta)}+2a/3\). For \(a\leq1\) and \(1/(2-\beta)\leq1\), \(a\leq a^{1/(2-\beta)}\). Rearranging proves the theorem, after increasing the constant \(C\). \(\square\)

What Complexity Adaptation Does—and Does Not—Mean

The theorem applies when each complexity level supplies a classifier trained without using the validation observations. Its oracle term is the risk of the best supplied candidate, while the remainder pays for searching across \(M\) candidates through \(\log M\). Complexity affects the oracle term through how well each candidate’s model can represent the decision rule and how well its training procedure estimates a useful classifier. The validation theorem does not by itself bound either contribution.

The guarantee is especially useful when candidate training already yields a fast oracle risk and the validation remainder is of no larger order. For example, if the number of candidates is controlled so that \(\log(M/\delta)/m\) is small, the selection cost has the same fast exponent as the margin-driven rate. If the candidate list grows too rapidly, or the validation sample is too small, the remainder can dominate. A fast selection bound cannot repair poor candidate models or an inadequate split.

Common Pitfall: Treating an Unknown Exponent as Known

A tempting approach is to choose the model minimizing empirical error plus a complexity penalty calibrated to a particular value of \(q\), then interpret the resulting guarantee as adaptive. That conclusion does not follow: if the assumed exponent is wrong, the penalty may not control the relevant estimation error. The validation selector avoids this particular dependence because its decision rule only compares observed errors. The exponent remains in the proof, where it determines the rate justified by the distribution.

This distinction is important. “The rule does not need the exponent” is not the same as “the guarantee has no assumptions.” The oracle result still requires a margin condition, independent validation data, and a finite candidate list. Without a useful margin condition, \(q=0\) yields only the usual square-root remainder. Nor does the result automatically establish adaptation over every possible model class or every possible training procedure.