The Slow-Rate Oracle Bound For Finite Selection

Why Selection Needs a Uniform Risk Bound

An empirical risk selector compares several candidate predictors using the same observed sample, then chooses the one with the smallest empirical loss. Even if each candidate’s empirical risk is close to its population risk with high probability, the selected candidate is random: it depends on the sample. A guarantee for one fixed candidate alone therefore does not directly control the risk of the selected one.

For a finite dictionary, a union bound resolves this issue by controlling the empirical risks of all candidates at once. When the losses are bounded, the resulting excess-risk guarantee has a characteristic slow rate: its leading order is the square root of the logarithm of the dictionary size divided by the sample size.

Setup and Assumptions

The dictionary is fixed independently of the observations. The result concerns comparison with the best member of this dictionary, not with an unrestricted ideal predictor. The bound \([0,1]\) is a normalization: if all losses lie in \([0,B]\) for a known \(B>0\), the bounds below are multiplied by \(B\).

From Bounded Losses to Uniform Concentration

The needed concentration result is Hoeffding’s inequality. In the bounded case, it says that for an average of \(n\) independent observations, each lying in an interval of length one, the probability of a deviation of at least \(t>0\) from its expectation is at most \(2e^{-2nt^2}\). Applying this separately to every candidate and taking a union bound yields a simultaneous guarantee.

To see why the bound has this form, fix a candidate \(j\). Its losses \(\ell_j(Z_i)\) are independent, lie in \([0,1]\), and have expectation \(R_j\). Hoeffding’s inequality gives \(P(|\widehat R_j-R_j|>t)\leq2e^{-2nt^2}\). The event that at least one candidate deviates by more than \(t\) is the union of the \(M\) individual deviation events. The union bound adds their probabilities, giving \(2Me^{-2nt^2}\). No independence between different candidates’ empirical risks is needed.

The Slow-Rate Oracle Bound

Proof. Apply the uniform concentration result with \(t=\sqrt{\log(2M/\delta)/(2n)}\). Its failure probability is at most \(2M e^{-2nt^2}=2M e^{-\log(2M/\delta)}=\delta\). On the resulting event, every candidate satisfies \(|\widehat R_j-R_j|\leq t\). In particular, this holds for the oracle index \(j^*\) and for the selected index \(\widehat j\). Since \(\widehat j\) minimizes empirical risk, \(\widehat R_{\widehat j}\leq\widehat R_{j^*}\). Therefore,

The middle term in the first line is nonpositive because of the empirical minimization. The other two terms are each bounded by \(t\) on the simultaneous event. This proves the claim. \(\square\)

The bound is an oracle inequality because it compares the selected predictor’s risk with the minimum risk available in the finite dictionary. Its dependence on \(M\) is logarithmic, while its dependence on \(n\) is \(n^{-1/2}\). Thus adding candidates increases the bound slowly, but more observations shrink it. The confidence parameter enters through \(\log(1/\delta)\).

An Expected Excess-Risk Guarantee

The same bounded-loss assumption also yields a bound on the expected excess risk. This version follows by controlling the expected largest absolute empirical-risk deviation over the dictionary. A moment-generating-function argument makes the logarithmic dependence on \(M\) explicit.

Proof. Hoeffding’s lemma states that if a random variable \(W\) lies in an interval of length \(b-a\), then \(E[e^{\lambda(W-E[W])}]\leq e^{\lambda^2(b-a)^2/8}\) for every real \(\lambda\). For completeness, when \(W\in[0,1]\), convexity gives \(e^{\lambda W}\leq 1-W+We^\lambda\). Writing \(q=E[W]\), it follows that \(E[e^{\lambda(W-q)}]\leq e^{-\lambda q}(1-q+qe^\lambda)\). The logarithm of the right-hand side has value and first derivative zero at \(\lambda=0\); its second derivative is \(r(1-r)\leq1/4\), where \(r=qe^\lambda/(1-q+qe^\lambda)\). Integrating this second-derivative bound gives a logarithm no greater than \(\lambda^2/8\), for positive or negative \(\lambda\). The endpoint cases \(q=0\) and \(q=1\) are immediate. Rescaling proves the stated interval-length form.

Set \(D_j=\widehat R_j-R_j\). Independence across observations and Hoeffding’s lemma imply \(E[e^{\lambda D_j}]\leq e^{\lambda^2/(8n)}\); the same holds for \(-D_j\). For any \(\lambda>0\), Jensen’s inequality and the sum of the \(2M\) exponentials give

Choosing \(\lambda=\sqrt{8n\log(2M)}\) makes the right-hand side \(\sqrt{\log(2M)/(2n)}\). The oracle comparison used in the high-probability proof holds pointwise, so \(R_{\widehat j}-R_{j^*}\leq2\max_j|D_j|\). Taking expectations proves the result. \(\square\)

What the Slow Rate Does—and Does Not—Say

The square-root rate arises because the argument controls estimation error uniformly and then pays for two deviations: one for the selected candidate and one for the oracle candidate. Bounded losses provide concentration, and the union bound accounts for searching across the dictionary. No assumption about a special relationship between the candidates’ losses is required.

A common mistake is to apply a concentration bound to the selected predictor as though its index had been fixed before observing the data. The selector’s index is data-dependent, so that single-candidate argument does not justify a guarantee for the selected risk. The correction is to establish a simultaneous deviation bound for every candidate, as above. A different mistake is to infer a bound proportional to \(\log(M)/n\) from boundedness alone. The argument here gives a square-root rate; a faster rate requires additional assumptions and a different analysis.