SRM With Growing Model Collections

Why growth changes the SRM guarantee

Structural risk minimization (SRM) compares models of different complexity using empirical fit and a complexity penalty. When the collection of candidate models is fixed, a penalty can account for the search over that collection. When the collection itself grows with sample size, the penalty must also account for that growth. A penalty adequate for ten candidates may be too small when the procedure searches over exponentially many.

The key issue is uniformity: the selected model is chosen using the same data used to assess its empirical risk. A guarantee for one prespecified model does not automatically hold for a data-selected model. We will give an explicit finite-sample condition that handles this search and then translate it into growth conditions.

Setup and finite-sample guarantee

Definition: For sample size \(n\), let \(\mathcal{M}_n=\{1,\ldots,M_n\}\) index the candidate models. Model \(m\) contains a finite set \(\mathcal{F}_{n,m}\) of predictors, of size \(K_{n,m}\). The observations \(Z_1,\ldots,Z_n\) are independent and identically distributed, and each predictor \(f\) has a measurable loss \(\ell_f(Z)\) satisfying \(0\leq \ell_f(Z)\leq 1\). Write \(R(f)=E[\ell_f(Z)]\), \(P_n\ell_f=n^{-1}\sum_{i=1}^n\ell_f(Z_i)\), and \(R^*_{n,m}=\min_{f\in\mathcal{F}_{n,m}}R(f)\).

The bounded-loss assumption gives a simple concentration inequality. For a fixed predictor, Hoeffding's inequality bounds the chance that empirical and population risks differ by more than \(t\). A union bound then makes the bound simultaneous over all predictors in all models. The resulting penalty depends on both the number of models and the richness of each model.

Theorem: Fix \(0<\delta<1\). Define

t_{n,m}(\delta)= \sqrt{\frac{\log\!\left(2M_nK_{n,m}/\delta\right)}{2n}}.

For each model, choose an empirical risk minimizer \(\hat f_{n,m}\) in \(\mathcal{F}_{n,m}\). Let \(\hat m\) minimize \(P_n\ell_{\hat f_{n,m}}+t_{n,m}(\delta)\) over \(m\), with ties resolved by a fixed rule, and set \(\hat f=\hat f_{n,\hat m}\). Then, with probability at least \(1-\delta\), simultaneously for every \(m\in\mathcal{M}_n\),

R(\hat f)\leq R^*_{n,m}+2t_{n,m}(\delta).

Equivalently, on this event, \(R(\hat f)\leq \min_{m\in\mathcal{M}_n}\{R^*_{n,m}+2t_{n,m}(\delta)\}\).

Here the penalty is applied to the selected model's empirical risk, not to its population risk, so the simultaneous deviation event is essential to the argument.

Proof of the oracle inequality

Control all empirical risks.
For fixed \(m\) and \(f\in\mathcal{F}_{n,m}\), Hoeffding's inequality gives \(P(|P_n\ell_f-R(f)|>t)\leq 2e^{-2nt^2}\). At \(t=t_{n,m}(\delta)\), this is \(\delta/(M_nK_{n,m})\). Summing these probabilities over the \(K_{n,m}\) predictors in model \(m\), and then over all \(M_n\) models, gives a total at most \(\delta\).

Use the event from Step 1.
With probability at least \(1-\delta\), every \(f\in\mathcal{F}_{n,m}\) satisfies \(|P_n\ell_f-R(f)|\leq t_{n,m}(\delta)\), for every \(m\).

Compare selection with any model.
On that event, fix \(m\) and let \(f_m^*\) attain \(R^*_{n,m}\); it exists because the class is finite. The deviation bound for the selected predictor, the selection rule, and the deviation bound for \(f_m^*\) give the desired inequality.

In detail, on the event in Step 2,

\begin{aligned} R(\hat f) &\leq P_n\ell_{\hat f}+t_{n,\hat m}(\delta)\\ &\leq P_n\ell_{f_m^*}+t_{n,m}(\delta)\\ &\leq R(f_m^*)+2t_{n,m}(\delta)\\ &=R^*_{n,m}+2t_{n,m}(\delta). \end{aligned}

The middle inequality is exactly the defining minimization of empirical risk plus penalty. Since the same event controls every model, the argument applies to every \(m\) at once. Taking the minimum over \(m\) proves the oracle form. \(\square\)

What growth conditions make the penalty small?

The theorem gives a direct sufficient condition. To make the bound useful for a particular comparator \(m_n\), it is enough that

\frac{\log(2M_nK_{n,m_n}/\delta_n)}{n}\longrightarrow 0.

Then \(t_{n,m_n}(\delta_n)\to0\). This condition says that the logarithm of the search size, including the confidence cost, must be small compared with the sample size. To make the penalty vanish uniformly over all candidate models, a convenient sufficient condition is

\frac{\log(2M_nK_{n,\max}/\delta_n)}{n}\longrightarrow 0, \qquad K_{n,\max}=\max_{m\in\mathcal{M}_n}K_{n,m}.

These are sufficient conditions for this bound, not necessary conditions for every SRM procedure or every data distribution. Other complexity controls may give sharper results for structured classes, but they must still control the data-dependent search.

Worked Example: Exponentially Many Models, but a Vanishing Penalty

Suppose \(M_n=\lceil \exp(n^{1/3})\rceil\), each model has \(K_{n,m}\leq 5\) predictors, and choose \(\delta_n=n^{-2}\). The largest penalty is bounded by

\max_m t_{n,m}(\delta_n) \leq \sqrt{\frac{\log(10M_n n^2)}{2n}}.

Because \(\log M_n=n^{1/3}+o(1)\), the numerator is \(n^{1/3}+2\log n+O(1)\). Therefore

\max_m t_{n,m}(\delta_n) \leq \sqrt{\frac{n^{1/3}+2\log n+O(1)}{2n}} =O(n^{-1/3}).

The penalty vanishes, and the theorem's event has probability at least \(1-n^{-2}\), which tends to one. The oracle remainder \(2t_{n,m}\) is at most \(O(n^{-1/3})\) uniformly over the models.

Worked Example: A Model Whose Number of Candidates Grows

Suppose \(M_n=n\), and model \(m\) has at most \(\exp(3m\log n)\) predictors. Consider a comparator \(m_n=\lfloor n^{1/2}\rfloor\) and again let \(\delta_n=n^{-2}\). Its penalty satisfies

t_{n,m_n}(\delta_n) \leq \sqrt{\frac{\log(2n)+3m_n\log n+2\log n}{2n}}.

Since \(m_n\leq n^{1/2}\), the numerator is at most \(3n^{1/2}\log n+3\log n+\log 2\). Thus

t_{n,m_n}(\delta_n) \leq \sqrt{\frac{3n^{1/2}\log n+3\log n+\log 2}{2n}} =O(n^{-1/4}\sqrt{\log n}).

This tends to zero: \(n^{-1/4}\sqrt{\log n}\to0\). Accordingly, with probability at least \(1-n^{-2}\), the selected risk is no more than the best risk in this comparator model plus a remainder of order \(n^{-1/4}\sqrt{\log n}\). This calculation is an upper bound; the actual number of candidates could be much smaller than the stated maximum.

Risk comparison and confidence are separate

A shrinking remainder and a probability tending to one are distinct claims. The theorem always states a probability of at least \(1-\delta_n\). A condition such as \(\log(1/\delta_n)=o(n)\) can keep the penalty small, but by itself it does not force \(\delta_n\to0\). To obtain a guarantee whose probability tends to one, require both a vanishing penalty for the comparator of interest and \(\delta_n\to0\).

For example, if \(\delta_n=1-1/n\), then \(\log(1/\delta_n)\to0\), but the stated probability lower bound is only \(1/n\). It does not tend to one. The inequality remains a valid finite-sample statement; it simply does not give an asymptotically high-confidence guarantee.

If a comparator sequence has \(R^*_{n,m_n}\to R_0\), then the theorem gives an upper bound \(R(\hat f)\leq R^*_{n,m_n}+o(1)\) on events with the stated confidence, provided its penalty vanishes. This is an upper comparison, not by itself a two-sided convergence claim. A conclusion that the selected risk converges to \(R_0\) also needs a suitable lower bound on the risks under consideration.

Worked Example: Exponential Growth Can Leave a Constant Penalty

Now take \(M_n=\lfloor\exp(n/4)\rfloor\), one predictor per model, and fixed \(\delta=0.05\). For sufficiently large \(n\), \(\log M_n=n/4+o(1)\), so the common penalty obeys

t_{n,m}(0.05) = \sqrt{\frac{\log(2M_n/0.05)}{2n}} \longrightarrow \sqrt{\frac{1}{8}} \approx 0.354.

This union-bound penalty does not vanish. Thus this particular guarantee does not establish a shrinking oracle remainder for that collection. It does not prove that every procedure must fail with exponentially many models; it shows that the stated uniform finite-class bound no longer supplies a vanishing remainder under this growth rate.

Richer classes and a common pitfall

The finite-cardinality quantity \(K_{n,m}\) measures richness in the results above. If a model contains infinitely many predictors, one cannot insert an infinite \(K_{n,m}\) into the formula and obtain a useful bound. Instead, one needs a valid uniform deviation bound for that class, such as a bound based on an appropriate complexity measure or finite approximation. In general, if for each model a deterministic \(b_{n,m}\) satisfies

P\!\left( \sup_{f\in\mathcal{F}_{n,m}} |P_n\ell_f-R(f)|>b_{n,m} \right)\leq \frac{\delta}{M_n},

then the same union-bound and selection argument gives \(R(\hat f)\leq R^*_{n,m}+2b_{n,m}\) simultaneously for all \(m\), when the selector minimizes empirical risk plus \(b_{n,m}\). This statement requires the displayed deviation guarantee to hold for the class in question; it does not assert such a bound for every infinite class.

Pitfall: counting only the number of models. The mistaken argument is that \(M_n\) is small enough, so searching is harmless. But a single model can itself contain many candidates. In the finite-class bound, both \(M_n\) and \(K_{n,m}\) enter through \(\log(M_nK_{n,m})\).
Correction: Account for the total search, or establish a suitable class-level deviation bound. Then check that its complexity divided by \(n\) tends to zero for the comparator being used.
Pitfall: saying “high probability” without checking confidence. A vanishing penalty does not imply the event probability tends to one if \(\delta_n\) stays away from zero.
Correction: Report the guarantee as probability at least \(1-\delta_n\), and add \(\delta_n\to0\) when claiming probability tending to one.

Key takeaway: For finite candidate classes with bounded loss, SRM's oracle remainder is controlled by the logarithm of the search size divided by sample size. A growing collection is compatible with a vanishing remainder when that ratio vanishes for the relevant comparator; confidence tending to one additionally requires \(\delta_n\to0\).

Check Your Understanding

Use the theorem and growth conditions to answer the following.

If \(M_n=n^2\), \(K_{n,m}\leq n^3\), and \(\delta_n=n^{-1}\), does the uniform penalty vanish? Show the order of its logarithmic numerator.
Why does the theorem require a bound that holds simultaneously over predictors, rather than only for a fixed predictor chosen before observing the data?
If the complexity ratio tends to zero but \(\delta_n=0.2\) for every \(n\), what does the probability guarantee say, and what does it not say?
Suppose \(M_n=\exp(n^{1/2})\) and \(K_{n,m}\leq \exp(n^{1/3})\). For fixed \(\delta\), does the finite-class penalty vanish? Justify using the ratio in the theorem.
Why is an infinite predictor class not handled by substituting \(K_{n,m}=\infty\) into the finite-class penalty?