Non-Nested Families And Complexity Indexing

Why Non-Nested Classes Need Their Own Complexity Accounting

Structural risk minimization (SRM) balances empirical fit against the cost of using a more complex candidate. A familiar setting has a nested sequence: every function in one class also belongs to the next. But useful candidate collections need not have that structure. A class of linear rules using one group of features, for example, may have little or no overlap with a class using a different group. There need not be a meaningful ordering by inclusion.

The selection principle still works. What changes is how complexity is recorded: each candidate class needs a bound on estimation error within that class, and the search across classes needs its own accounting. The result is an oracle comparison with every candidate class, without requiring that one class contain another.

For precision, suppose the observations \(Z_1,\ldots,Z_n\) are independent and identically distributed, the loss \(\ell(f,Z)\) is measurable and lies in \([0,1]\), and \(R(f)=E[\ell(f,Z)]\) and \(\widehat R_n(f)=n^{-1}\sum_{i=1}^n\ell(f,Z_i)\). In the finite-class construction below, assume \(\mathcal J\) is finite or countable and every \(\mathcal F_j\) is finite and nonempty. Write \(M_j=|\mathcal F_j|\). These assumptions make the selector and the probability bounds explicit; more general classes can use other valid uniform deviation bounds in place of the finite-class bound.

Constructing the Penalty

Within a finite class, a larger \(M_j\) requires a stronger uniform deviation allowance because more functions are being compared. Across classes, a small weight \(w_j\) means a small share of the overall error probability, and therefore a larger allowance for that class. For a chosen error probability \(\delta\in(0,1)\), define

The logarithm contains two distinct costs: \(\log M_j\) for searching within class \(j\), and \(\log(1/w_j)\) for searching across the indexed collection. The penalty is not determined by whether classes are nested. It is determined by the deviation control available for each class and the chosen allocation of probability across indices.

A Simultaneous Deviation Bound

The penalty is justified by controlling every function in every class at once. The finite-class result below uses Hoeffding's inequality for a bounded loss and a union bound. No inclusion relationship between the classes is needed.

Proof. Fix a class \(j\) and a function \(f\in\mathcal F_j\). The \(n\) losses are independent and bounded in \([0,1]\), so Hoeffding's inequality gives \(P(|\widehat R_n(f)-R(f)|>r_j)\leq 2\exp(-2nr_j^2)\). Substituting the definition of \(r_j\) yields \(2\exp[-\log(2M_j/(\delta w_j))]=\delta w_j/M_j\). There are \(M_j\) functions in \(\mathcal F_j\), so the union bound makes the probability of any violation in class \(j\) at most \(\delta w_j\). Applying the union bound across the indices gives a total probability at most \(\sum_j\delta w_j\leq\delta\). Therefore the asserted simultaneous event has probability at least \(1-\delta\). \(\square\)

The weights are the step that pays for searching across classes. For \(J\) classes, equal weights \(w_j=1/J\) are valid and put a \(\log J\) term into each penalty. For a countable family, equal positive weights cannot sum to at most one; one must use a summable allocation, such as weights that decrease with the index. Assigning a very small weight to a class increases its penalty, as it should when that class receives a smaller share of the probability budget.

The Penalized Selector and Its Oracle Guarantee

Choose a function and index by minimizing empirical risk plus the class-specific penalty: \(\widehat f\in\mathcal F_{\widehat j}\), where \((\widehat j,\widehat f)\) minimizes \(\widehat R_n(f)+r_j(n,\delta)\) over all indexed candidates. For finite index sets and finite classes, a minimizer exists. For countable collections, a minimizing sequence can instead be used, with an arbitrarily small optimization tolerance.

Proof. Work on the simultaneous event from the preceding theorem. For any \(j\) and \(f\in\mathcal F_j\), the deviation bound for the selected function gives \(R(\widehat f)\leq\widehat R_n(\widehat f)+r_{\widehat j}\). By the definition of the selector, \(\widehat R_n(\widehat f)+r_{\widehat j}\leq\widehat R_n(f)+r_j\). The deviation bound for \(f\) then gives \(\widehat R_n(f)\leq R(f)+r_j\). Combining these inequalities yields \(R(\widehat f)\leq R(f)+2r_j\). This holds for every \(j\) and every \(f\in\mathcal F_j\), so taking the infimum over \(f\) and then over \(j\) proves the claim. If the selector's objective is within \(\varepsilon\) of its infimum, the selection inequality gains an additive \(\varepsilon\), which carries through unchanged. \(\square\)

This is an oracle inequality: its right-hand side compares the selected rule with the best population-risk rule available in each candidate class, while charging that class for its complexity. The statement is about the risk of the selected rule, not about identifying a uniquely correct class. The minimum over classes need not be attained for the inequality to be meaningful.

How This Relates to Nested Sieves

A nested sieve is a special case of an indexed family: its classes happen to satisfy \(\mathcal F_1\subseteq\mathcal F_2\subseteq\cdots\). The finite-class guarantee above still applies, with penalties calibrated to the sizes or other deviation bounds of those classes and weights for the indices. Nesting can help describe how approximation opportunities change as classes grow, but it is not needed for the selection proof.

For non-nested classes, the same oracle form remains available, but it is important not to mistake an index for a universal scale. Index 3 need not mean “more complex” than index 2 unless the analyst has established that interpretation. The complexity assigned to each candidate should reflect its own deviation control; the weights should reflect the cost of searching the chosen collection. A large or hard-to-control class can receive a larger penalty, while a class with a strong bound can remain competitive even if it is not part of a nested sequence.

Common Mistakes and Practical Interpretation

• Assuming an inclusion order is necessary. The proof compares each candidate directly through its empirical objective and deviation allowance. At no point does it require one class to contain another.
• Using only within-class complexity. A bound for each class separately does not automatically cover selecting among many classes. The index weights (or an equivalent search-cost term) are what make the simultaneous statement valid.
• Giving every class the same penalty without justification. Equal penalties can ignore differences in class size or deviation behavior. They are justified only when the available bounds support them.
• Reading the oracle inequality as class recovery. It controls risk relative to candidate classes; it does not guarantee that the selected index is the best index in population or that it identifies a true model.