Why Index a Collection of Candidate Models?
Risk minimization is often carried out over a collection of candidate predictor classes rather than one fixed class. The classes may represent different functional forms, restrictions, or numbers of adjustable parameters. To discuss their comparison precisely, it helps to keep four ideas separate: the index used to name a class, its approximation quality for the prediction problem, its structural complexity, and the statistical difficulty of learning from finite data.
These ideas are related, but they are not interchangeable. A larger class may contain a predictor with lower risk, while also presenting more possibilities to distinguish from data. Yet a numeric label does not itself say that a class is larger, fits better, or is harder to estimate. Those claims require definitions and assumptions about how the classes are organized.
Fix a joint distribution of covariates and responses, and a nonnegative measurable loss function \(\ell\). For a measurable predictor \(f\), its risk is \(R(f)=E[\ell(Y,f(X))]\), interpreted as an extended nonnegative real number. The best-in-class risk of model \(m\) is the infimum of the risks over predictors in that class. An infimum need not be attained, so “best-in-class” does not automatically mean that some predictor achieves it.
Nesting and What It Guarantees
A family is nested if its index set has an order and the classes respect that order: whenever \(m_1\preceq m_2\), \(\mathcal F_{m_1}\subseteq\mathcal F_{m_2}\). The order could be the usual order on integers, but it need not be. Nesting is a statement about set inclusion, not about labels alone.
Proof. Every predictor in \(\mathcal F_{m_1}\) also belongs to \(\mathcal F_{m_2}\). Thus the set of risk values attained in \(\mathcal F_{m_1}\) is a subset of the set of risk values attained in \(\mathcal F_{m_2}\). The infimum of the larger set cannot exceed the infimum of the smaller set. This proves the inequality, including cases in which a class is empty or its infimal risk is infinite. \(\square\)
The result says only that enlarging a class cannot worsen its infimal risk. It does not say that the risk decreases strictly, that the infimum is attained, or that a procedure using finite data will perform better after enlargement. Those are separate questions.
Worked Example: Constants Compared with Affine Predictors
Let \(X\) take values \(0\) and \(1\) with probability \(1/2\) each, and let \(Y=X\). Use squared-error loss, \(\ell(y,t)=(y-t)^2\). Compare the class \(\mathcal F_0\) of constant predictors \(f_c(x)=c\), \(c\in\mathbb R\), with the class \(\mathcal F_1\) of affine predictors \(f_{a,b}(x)=a+bx\), \(a,b\in\mathbb R\).
Every constant predictor is affine by setting \(b=0\), so \(\mathcal F_0\subseteq\mathcal F_1\). For a constant \(c\), the risk is \(R(f_c)=\frac12(0-c)^2+\frac12(1-c)^2\). Expanding and completing the square gives \(R(f_c)=c^2-c+\frac12=(c-\frac12)^2+\frac14\). The minimum over \(c\in\mathbb R\) is therefore \(1/4\), attained at \(c=1/2\), so \(R_0^*=1/4\).
The affine predictor \(f(x)=x\), corresponding to \(a=0\) and \(b=1\), has risk \(\frac12(0-0)^2+\frac12(1-1)^2=0\). Because squared-error risk is nonnegative, no predictor can have risk below zero. Hence \(R_1^*=0\). The larger class improves the infimal risk in this example, consistently with nesting.
Under the usual parameter-count description, the constant class has one free parameter and the affine class has two. Parameter count is one possible structural descriptor here; it is not the reason the risk inequality holds. Inclusion is the reason.
Approximation Quality and Its Gap
The family-wide infimal risk describes the best risk available anywhere in the union. To compare one class with that benchmark, define its approximation gap. This quantity is well-defined as a nonnegative extended real number when the family-wide infimal risk is finite. That condition matters: subtracting two infinite risks would not define a gap.
The finiteness condition is automatic if at least one predictor in the union has finite risk. It is also necessary for this particular subtraction: if every predictor has infinite risk, then both infimal risks may equal \(+\infty\), and their difference is undefined. In that situation, one should not claim that this formula defines a nonnegative gap.
Proof. The union consists exactly of the predictors that belong to at least one indexed class. Taking the infimum of risk over this union is therefore the same as first taking the infimum within each class and then taking the infimum over the indices: \(R_{\mathcal F}^*=\inf_{m\in\mathcal I}\inf_{f\in\mathcal F_m}R(f)=\inf_{m\in\mathcal I}R_m^*\). In particular, \(R_m^*\geq R_{\mathcal F}^*\) for every \(m\). Since the family-wide infimum is finite, subtracting it from \(R_m^*\), including when \(R_m^*=+\infty\), is well-defined and gives \(A_m\geq0\). Finally, \(\inf_m A_m=\inf_m(R_m^*-R_{\mathcal F}^*)=\inf_mR_m^*-R_{\mathcal F}^*=0\); subtracting a finite constant commutes with this infimum. \(\square\)
The theorem does not say that any particular index has a small gap, or that some class attains the family-wide infimum. It says that the infimum of the gaps is zero. A sequence of classes might approach that benchmark without any one class reaching it.
Worked Example: An Index Is Not a Ranking of Fit
Let \(X\) be constant, let \(Y=0\) with probability one, and use squared-error loss. Consider three indexed classes: \(\mathcal F_1=\{f_0\}\), \(\mathcal F_2=\{f_2\}\), and \(\mathcal F_3=\{f_1\}\), where \(f_t\) is the constant predictor with value \(t\).
For a constant prediction \(t\), the risk is \(E[(Y-t)^2]=(0-t)^2=t^2\). Consequently, \(R_1^*=0^2=0\), \(R_2^*=2^2=4\), and \(R_3^*=1^2=1\). The numerical order of the labels \(1,2,3\) does not give an order of risks: risk first rises from \(0\) to \(4\), then falls to \(1\).
Each class contains exactly one predictor, so each has the same cardinality. The example separates three things: the labels, the class sizes under this simple measure, and the risks. Reassigning the labels would change none of the predictors or risks. Without a stipulated inclusion or other organization, the index alone carries no mathematical guarantee about fit.
Structural Complexity Is Not Approximation Quality
There is no single scalar called “the complexity” that applies to every problem independently of its structure. Common descriptors include the number of predictors in a finite class, the number of free parameters in a parametrization, and capacity measures such as VC dimension or covering numbers. Each answers a different question and may be appropriate under different assumptions. A parameter count can be misleading when parameters are redundant or constrained; cardinality does not describe the geometry of a continuous class.
Approximation quality is measured by risk relative to a target or benchmark. Structural complexity describes features of the set of candidates. Statistical difficulty concerns how reliably a procedure can select or estimate predictors using a finite sample. It depends not only on the class but also on the loss, the distribution of the observations, and the estimation procedure. Thus neither a class's index nor one complexity descriptor alone determines its risk or the difficulty of learning it.
Worked Example: A Larger Finite Class Can Improve Approximation
Let \(X\) take values \(a\) and \(b\) with probability \(1/2\) each, and let \(Y(a)=0\) and \(Y(b)=1\) deterministically. Predictors take values in \(\{0,1\}\), and the loss is squared error. Let \(\mathcal G_0\) contain the two constant predictors, while \(\mathcal G_1\) contain all four maps from \(\{a,b\}\) to \(\{0,1\}\).
For the constant-zero predictor, the squared errors at \(a,b\) are \(0,1\), so its risk is \(\frac12(0)+\frac12(1)=1/2\). For the constant-one predictor, the errors are \(1,0\), and the risk is also \(1/2\). Therefore \(R_{\mathcal G_0}^*=1/2\).
The four predictors in \(\mathcal G_1\) are the constant-zero map, the constant-one map, the map with values \((0,1)\) at \((a,b)\), and the map with values \((1,0)\). The predictor with values \((0,1)\) agrees with \(Y\) at both covariate values, so its risk is \(\frac12(0)^2+\frac12(0)^2=0\). Nonnegativity of squared error implies \(R_{\mathcal G_1}^*=0\). The approximation gap of \(\mathcal G_0\) relative to the union is \(1/2-0=1/2\); the gap of \(\mathcal G_1\) is zero.
By cardinality, the classes have sizes \(2\) and \(4\), respectively. This example shows a larger class improving approximation for this particular distribution. It does not establish a universal rule that every increase in cardinality yields a useful risk reduction, nor does it quantify the finite-sample cost of searching that class.
What Nesting Says About Complexity
Some complexity descriptors are monotone under inclusion, while others require more care. For finite classes, cardinality is monotone: if \(\mathcal F_1\subseteq\mathcal F_2\), then \(|\mathcal F_1|\leq|\mathcal F_2|\). Capacity notions based on subsets of predictors also often respect inclusion. But parameter counts attached to two different representations need not compare the underlying classes reliably.
Even where a chosen complexity measure increases with inclusion, approximation and statistical difficulty remain distinct. A larger class may include a predictor that better matches the risk target, as in the finite example. It also offers more candidates, but the actual statistical consequence depends on the sampling and loss assumptions. A class can have excess structural complexity without reducing its best achievable risk; conversely, a small class can be poorly matched to the target.
Worked Example: Complexity Can Change Without Improving the Best Risk
Keep the two covariate values \(a,b\), binary-valued predictors, and squared-error loss from the preceding example, but now let \(Y=0\) with probability one at both covariate values. The class \(\mathcal G_0\) of two constant binary predictors still has best risk zero, because the constant-zero predictor has risk \(0\).
The larger class \(\mathcal G_1\), containing all four binary maps, also has best risk zero: it contains that same constant-zero predictor, and all risks are nonnegative. Thus \(R_{\mathcal G_0}^*=R_{\mathcal G_1}^*=0\), even though their cardinalities are \(2\) and \(4\).
The larger class has more candidates under cardinality, but adds no improvement to the infimal risk in this distribution. The example does not assert that a particular estimator has identical behavior over the two classes; it shows specifically that class size and approximation quality are separate properties.
Common Mistakes
- Treating the index as an ordered complexity scale. The labels \(m=1,2,3\) have no ordering implication unless inclusion or another explicit structure is imposed.
- Assuming nesting implies strict improvement. Inclusion gives a weak inequality for best-in-class risk. Equality is possible when the added predictors do not lower the infimum.
- Calling a larger class automatically better for estimation. A larger class can improve the best available risk while making finite-sample selection more demanding. These are distinct claims.
- Subtracting infinite risks to define approximation gaps. If \(R_{\mathcal F}^*=+\infty\), the expression \(R_m^*-R_{\mathcal F}^*\) can be undefined. Assume \(R_{\mathcal F}^*<\infty\) before using this gap definition.
Check Your Understanding
Answer each question by distinguishing class structure from risk or complexity claims.
- What additional condition turns an indexed family into a nested family?
- If \(\mathcal F_1\subseteq\mathcal F_2\), what inequality must hold between their best-in-class risks, and why?
- Why is the approximation gap \(R_m^*-R_{\mathcal F}^*\) not defined by this formula when both terms are \(+\infty\)?
- Can two nested classes have equal best-in-class risk despite different cardinalities? Explain.
- Name two structural complexity descriptors and explain why neither is the same thing as approximation quality.