The Cost Of Searching Across Many Models

Why Searching Changes a Risk Bound

A risk estimate can be reliable for a particular candidate and still be misleading after searching among many candidates. If each candidate is assessed using the same data, the one with the most favorable empirical result may owe some of that advantage to random fluctuation. Simultaneous risk control accounts for this search: it asks for a guarantee that holds for every candidate at once, not just for one candidate chosen in advance.

The cost of this guarantee depends on how many candidates are considered. Under common concentration bounds, it grows with the logarithm of the number of candidates, rather than in direct proportion to that number. The distinction is useful: a large search can matter, but its cost need not grow as fast as the collection itself.

Per-Candidate and Simultaneous Risk Control

Let $m\in\{1,\ldots,M\}$ index a finite collection of candidate models or predictors. Write $R_m$ for the risk of candidate $m$, and $\hat R_m$ for its risk estimate. These quantities may be random if the candidates or estimates depend on data. Suppose that for each fixed candidate and every $t\geq 0$, a one-sided bound holds:

P(R_m-\hat R_m>t)\leq \exp(-c n t^2),

where $c>0$ is a constant and $n$ is the sample size relevant to this concentration bound. The event $R_m-\hat R_m>t$ means that the estimated risk is too optimistic by more than $t$. A simultaneous guarantee controls the largest such optimism across the collection.

Definition: A simultaneous one-sided risk bound at level $1-\delta$ is a number $\epsilon$ such that $P(R_m\leq \hat R_m+\epsilon\text{ for every }m=1,\ldots,M)\geq 1-\delta$. Here $0<\delta<1$ is the allowed probability of failure.

A bound for each fixed candidate does not automatically give this simultaneous guarantee at the same threshold. The probability that at least one candidate fails must also be controlled.

The Finite-Collection Search Penalty

Theorem: Suppose $M$ is finite and each candidate satisfies $P(R_m-\hat R_m>t)\leq \exp(-c n t^2)$ for every $t\geq0$. Then, for $0<\delta<1$, with probability at least $1-\delta$, $$ R_m\leq \hat R_m+\sqrt{\frac{\log(M/\delta)}{c n}} \quad\text{for every }m=1,\ldots,M. $$

Proof. For a fixed threshold $t$, let $A_m=\{R_m-\hat R_m>t\}$. The event that simultaneous control fails is the union $\bigcup_{m=1}^M A_m$. The union bound gives

P\!\left(\bigcup_{m=1}^M A_m\right) \leq \sum_{m=1}^M P(A_m) \leq M\exp(-c n t^2).

Choose $t=\sqrt{\log(M/\delta)/(c n)}$. Then $c n t^2=\log(M/\delta)$, so

M\exp(-c n t^2) =M\exp\{-\log(M/\delta)\} =\delta.

Thus the probability that any candidate violates the stated bound is at most $\delta$. No independence among the candidate-specific failure events is required. $\square$

This derivation displays the search cost directly. For one candidate, the threshold is $\sqrt{\log(1/\delta)/(cn)}$. For $M$ equally treated candidates, it becomes $\sqrt{\log(M/\delta)/(cn)}$. Searching adds $\log M$ inside the square root. The added amount is not a fixed constant: it depends on the confidence level, the sample size, and the concentration rate.

Equal Weighting and Bounded Losses

The same calculation can be read as assigning each of the $M$ candidates a failure allowance of $\delta/M$. Substituting $\delta/M$ for the per-candidate failure probability gives the logarithm $\log\{1/(\delta/M)\}=\log(M/\delta)$. This is the equally weighted case: every candidate receives the same share of the total error allowance.

A common setting gives an explicit value for $c$. Suppose a candidate predictor $f_m$ is fixed independently of an evaluation sample $Z_1,\ldots,Z_n$, the observations are independent and identically distributed, and its loss satisfies $0\leq \ell(f_m,Z_i)\leq1$. Define

R_m=E[\ell(f_m,Z)],\qquad \hat R_m=\frac{1}{n}\sum_{i=1}^n\ell(f_m,Z_i).

Hoeffding's inequality for independent bounded variables gives $P(R_m-\hat R_m>t)\leq \exp(-2nt^2)$. Thus $c=2$, and equal weighting yields

R_m\leq\hat R_m+\sqrt{\frac{\log(M/\delta)}{2n}} \quad\text{for every }m

with probability at least $1-\delta$. This one-sided form controls empirical underestimation of risk, which is the direction relevant when an apparently low empirical risk might have been selected by searching.

If candidates are trained on the same observations used to calculate $\hat R_m$, the fixed-predictor version of Hoeffding's inequality cannot simply be applied as though each fitted predictor were fixed in advance. One must have a valid per-candidate bound that accounts for the fitting procedure, or use an independent evaluation sample under appropriate conditions. The collection-level calculation adds a search correction to a valid per-candidate bound; it does not repair an invalid one.

Worked Example: Checking a Sample Size at a Target Margin

Suppose there are $M=10$ fixed predictors, the loss is between 0 and 1, and the desired simultaneous one-sided confidence level is $1-\delta=0.95$. Find the margin when $n=264$, and determine whether it is at most $0.1$.

Here $\delta=0.05$, and the equally weighted Hoeffding margin is $\sqrt{\log(M/\delta)/(2n)}$. Since $M/\delta=10/0.05=200$, at $n=264$ the margin is

\sqrt{\frac{\log(200)}{528}} =\sqrt{\frac{5.2983173665\ldots}{528}} \approx 0.10017331.

Rounded to six decimal places, the margin is $0.100173$, which is greater than $0.1$. Therefore, $n=264$ does not suffice for the requested margin. To check the next integer, at $n=265$,

\sqrt{\frac{\log(200)}{530}} =\sqrt{\frac{5.2983173665\ldots}{530}} \approx 0.09998413<0.1.

Thus 265 observations suffice under these assumptions. The calculation checks the threshold itself, rather than relying on a rounded value close to the target.

Worked Example: Controlling Risk Across Four Candidates

Four fixed predictors have losses in $[0,1]$, and each is evaluated on the same independent sample of $n=100$ observations. The observed empirical risks are $0.31, 0.24, 0.20,$ and $0.27$. Find a simultaneous one-sided margin for confidence level $0.9$, then give the resulting risk bound for the empirical-risk minimizer.

Here $M=4$, $\delta=0.1$, and $c=2$. The margin is

\epsilon =\sqrt{\frac{\log(4/0.1)}{2(100)}} =\sqrt{\frac{\log(40)}{200}} =\sqrt{\frac{3.688879454\ldots}{200}} \approx 0.13581.

The smallest empirical risk is $0.20$, attained by the third predictor. Simultaneous control says that, with probability at least $0.9$, every candidate's risk is at most its empirical risk plus $0.13581$. In particular, the selected predictor's risk is at most $0.20+0.13581=0.33581$. This bound is not a claim that the selected predictor's actual risk equals $0.33581$; it is a high-probability upper bound supplied by the simultaneous guarantee.

Why Selection Can Require More Than One-Sided Control

Simultaneous one-sided control is enough to upper-bound the risk of whichever candidate is selected: on the event in the theorem, its risk is at most its empirical risk plus the margin. To compare that selected risk directly with the best candidate's true risk, one also needs to control empirical overestimation. The following derivation makes the extra requirement explicit.

Result: Suppose that with probability at least $1-\delta$, every candidate satisfies $|R_m-\hat R_m|\leq\epsilon$. If $\hat m$ minimizes $\hat R_m$ over $m=1,\ldots,M$, then on that event $$ R_{\hat m}\leq \min_{1\leq m\leq M}R_m+2\epsilon. $$

Proof. Let $m^\star$ be an index attaining the smallest true risk; it exists because the collection is finite. On the simultaneous event, first use the bound for the selected candidate, then the empirical minimization property, and then the bound for $m^\star$:

R_{\hat m} \leq \hat R_{\hat m}+\epsilon \leq \hat R_{m^\star}+\epsilon \leq R_{m^\star}+2\epsilon =\min_{1\leq m\leq M}R_m+2\epsilon.

This is a deterministic implication once the simultaneous event holds. For bounded losses, Hoeffding's inequality applied to both tails and a union bound over all candidates give such an event with $\epsilon=\sqrt{\log(2M/\delta)/(2n)}$: there are $2M$ one-sided tail events, one for each direction and candidate. The factor of two inside the logarithm comes from controlling both directions, not from the number of candidate models alone. $\square$

Worked Example: How Doubling the Search Changes the Margin

For bounded losses, let $n=500$ and $\delta=0.05$. Compare the equally weighted one-sided margins for $M=5$ and $M=10$.

For five candidates, $M/\delta=100$, so

\epsilon_5 =\sqrt{\frac{\log(100)}{1000}} =\sqrt{\frac{4.605170186\ldots}{1000}} \approx 0.06786.

For ten candidates, $M/\delta=200$, so

\epsilon_{10} =\sqrt{\frac{\log(200)}{1000}} =\sqrt{\frac{5.298317367\ldots}{1000}} \approx 0.07279.

Doubling the candidates increases the margin by about $0.07279-0.06786=0.00493$. It does not double the margin: the candidate count enters through a logarithm. The larger collection nevertheless requires a wider simultaneous bound at the same sample size and confidence level.

Common Mistakes and Practical Meaning

Using a per-candidate guarantee after searching. A probability statement for a candidate fixed in advance need not hold for the candidate chosen because its empirical risk looked best. The union-bound calculation protects all indexed candidates together.
Assuming independence is needed for the union bound. It is not. The inequality $P(\bigcup_m A_m)\leq\sum_mP(A_m)$ holds whether the candidate-specific events are independent, dependent, or identical.
Dropping the logarithm's arguments. With equal allocation, the one-sided expression is $\log(M/\delta)$. For two-sided control under Hoeffding's inequality it is $\log(2M/\delta)$. These correspond to different events being controlled.
Applying concentration without checking its conditions. Bounded independent evaluation losses support the stated Hoeffding bound for fixed predictors. Fitting and evaluating on the same data may require a different argument.
Treating the penalty as a universal numerical constant. Its value changes with $M$, $n$, $\delta$, and the per-candidate concentration rate $c$.

The practical point is that a model-search procedure should be judged by the risk control available for the whole search, not just by a bound for one candidate considered in isolation. Equal weighting gives a transparent benchmark: divide the allowed failure probability evenly, which produces the $\log(M/\delta)$ term. This is the statistical cost of asking many candidates to compete on the same evidence.

Check Your Understanding

Try these questions using the assumptions and derivations above.

Starting from $P(R_m-\hat R_m>t)\leq \exp(-cnt^2)$, derive the equally weighted simultaneous margin at failure probability $\delta$.
Why does the union-bound result not require independence among candidate-specific failure events?
For $M=20$, $n=400$, $\delta=0.1$, and losses in $[0,1]$, write the expression for the one-sided simultaneous Hoeffding margin.
Why does a one-sided risk bound alone not establish the $2\epsilon$ comparison between the selected risk and the best true risk?
What additional concern arises if each candidate is fitted using the same observations on which its empirical risk is calculated?