Complexity Penalties For Finite Predictor Classes

Why Finite Classes Need a Complexity Penalty

Suppose a learner chooses among several finite collections of predictors by comparing their empirical risks. A larger collection has more opportunities to contain a predictor whose observed risk is unusually small just by chance. Minimizing empirical risk alone does not account for that multiplicity. A logarithmic penalty for the number of candidates can control this effect while allowing smaller collections to pay less.

The fast, order-$\log(m)/n$ penalty studied here requires more than bounded losses: it uses a Bernstein condition on excess losses. Without such a condition, concentration often leads to a slower square-root dependence on the logarithm of the number of candidates. The finite-class calculation below makes the assumptions and the resulting comparison explicit.

Definition: Let $\mathcal F_1,\ldots,\mathcal F_J$ be nonempty finite predictor classes, with $m_j=|\mathcal F_j|$, and let $\mathcal F=\bigcup_{j=1}^J\mathcal F_j$. For independent, identically distributed observations $Z_1,\ldots,Z_n$, let $\ell_f(Z_i)\in[0,1]$ be the loss of predictor $f$. Define its risk and empirical risk by $R(f)=E[\ell_f(Z)]$ and $\widehat R_n(f)=n^{-1}\sum_{i=1}^n\ell_f(Z_i)$. Let $f^*$ minimize $R(f)$ over $\mathcal F$, and write $\Delta(f)=R(f)-R(f^*)$.

For the fast bound, assume there is a finite constant $C\geq0$ such that every $f\in\mathcal F$ satisfies $\operatorname{Var}(\ell_f(Z)-\ell_{f^*}(Z))\leq C\Delta(f)$. This condition says that the variance of the excess-loss comparison decreases with its expected excess risk. It is an assumption about the problem, not a consequence of having a finite class.

A Penalty and Its Oracle Guarantee

Choose a confidence level $0<\delta<1$, and define $c=2C+2/3$. Give class $j$ the penalty $p_j=c\log(2Jm_j/\delta)/n$, and select a predictor minimizing empirical risk plus its class penalty. The factor $Jm_j$ accounts for the candidates across classes, while $\delta$ determines the requested confidence.

Theorem: Under the conditions above, let $\hat f$ minimize $\widehat R_n(f)+p_j$ over all $f\in\mathcal F_j$, $1\leq j\leq J$. If $f^*\in\mathcal F_{j^*}$, then with probability at least $1-\delta$, $$ R(\hat f)-R(f^*)\leq \frac{4c}{3n}\log\!\left(\frac{2Jm_{j^*}}{\delta}\right). $$

The bound depends on the size of the class containing the best predictor, not on the size of the largest class. This is the oracle feature of the result: the selected predictor's risk is compared with the best risk available in the union, with a complexity cost determined by that comparator's class.

Proof of the Finite-Class Bound

For each fixed $f$, let $W(Z)=\ell_f(Z)-\ell_{f^*}(Z)$. Then $E[W]=\Delta(f)$, and $W\in[-1,1]$, so $|W-E[W]|\leq2$. Bernstein's inequality for independent bounded variables gives, for $a>0$, except on an event of probability at most $e^{-na}$, $$ \widehat R_n(f)-\widehat R_n(f^*)\geq \Delta(f)-\sqrt{2C\Delta(f)a}-\frac{2a}{3}. $$ Here the variance term is bounded by $C\Delta(f)$, and the centered summands are bounded in absolute value by $2$.

For any $\Delta\geq0$, the inequality $\sqrt{2C\Delta a}\leq\Delta/4+2Ca$ follows by squaring the nonnegative sides, or by the arithmetic-geometric mean inequality. Substituting it above and rearranging yields $$ \Delta(f)\leq\frac{4}{3}\left\{\widehat R_n(f)-\widehat R_n(f^*)+ca\right\}, \qquad c=2C+\frac{2}{3}. $$

Apply this inequality to every predictor $f\in\mathcal F_j$, with $a_j=\log(2Jm_j/\delta)/n$. For each such predictor, the exceptional probability is at most $e^{-na_j}=\delta/(2Jm_j)$. Summing these probabilities over all $J$ classes and their $m_j$ predictors gives a total at most $\delta/2$, hence at most $\delta$. Therefore, with probability at least $1-\delta$, the displayed inequality holds simultaneously for all $f$, using its own $a_j$.

On this simultaneous event, apply the inequality to $\hat f\in\mathcal F_{\hat j}$. By the definition of $\hat f$, its penalized empirical risk is no larger than that of $f^*$, so $\widehat R_n(\hat f)-\widehat R_n(f^*)\leq p_{j^*}-p_{\hat j}$. Since $p_j=ca_j$, it follows that $$ \begin{aligned} R(\hat f)-R(f^*) &\leq\frac{4}{3}\left\{\widehat R_n(\hat f)-\widehat R_n(f^*)+ca_{\hat j}\right\}\\ &\leq\frac{4}{3}\left\{p_{j^*}-p_{\hat j}+p_{\hat j}\right\} =\frac{4}{3}p_{j^*}. \end{aligned} $$ Substituting the definition of $p_{j^*}$ proves the result. $\square$

Worked Penalty Calculations

Worked Example: Comparing Two Class Sizes

Suppose there are $J=2$ classes, $n=2000$, and $\delta=0.05$. Let $C=1/2$, so $c=2C+2/3=5/3$. Suppose every predictor in class 1 has risk $0.120$, every predictor in class 2 has risk $0.116$, and the class sizes are $m_1=2$ and $m_2=128$. These constant losses have zero variance, so the stated Bernstein condition holds.

For class 1 the penalty is $p_1=(5/3)\log(2\cdot2\cdot2/0.05)/2000=(5/3)\log(160)/2000\approx0.004229$. Its penalized risk is $0.120+0.004229=0.124229$.

For class 2 the penalty is $p_2=(5/3)\log(2\cdot2\cdot128/0.05)/2000=(5/3)\log(10240)/2000\approx0.007695$. Its penalized risk is $0.116+0.007695=0.123695$. Thus the penalized rule selects class 2, whose risk is lower. The larger class pays more, but its $0.004$ risk advantage exceeds the penalty increase, which is approximately $0.003466$.

Here $f^*$ is in class 2. The theorem's excess-risk bound is $(20/9)\log(10240)/2000\approx0.01026$, while the actual excess risk of the selected predictor is zero. A bound is a guarantee, not a claim that the realized excess risk attains its upper limit.

Worked Example: The Incremental Cost of a Larger Class

Use $c=5/3$ and $n=1000$, and compare classes of sizes $320$ and $1280$. If the confidence and number-of-classes factors are held fixed, they contribute the same additive term to both log penalties and cancel in the difference. The size-dependent penalty increment is $$ \frac{5}{3n}\{\log(1280)-\log(320)\} =\frac{5}{3000}\log(4) \approx 0.00231049. $$

Thus the larger class pays about $0.00231$ more on the empirical-risk scale. The calculation uses $\log(1280)-\log(320)=\log(4)\approx1.386294$; the penalty increment is not $0.00232$ to five significant decimal places. This comparison can help assess whether a reduction in empirical risk is large enough to offset the extra multiplicity cost.

Worked Example: Three Singleton Classes

Suppose $J=3$, each class contains one predictor, $n=500$, $\delta=0.10$, and $C=1/2$. The classes have equal penalties because their sizes are equal. For each class, $p_j=(5/3)\log(2\cdot3\cdot1/0.10)/500=(5/3)\log(60)/500$. Using $\log(60)\approx4.094345$, this gives $p_j\approx0.013648$.

Because the penalties are identical, minimizing penalized empirical risk chooses exactly the same predictor as minimizing empirical risk in this example. The penalty still appears in the guarantee: whichever class contains $f^*$, the theorem bounds excess risk by $(4/3)p_j\approx0.018197$, with probability at least $0.90$. Equal penalties do not change the selection, but the simultaneous comparison across three candidates still affects the bound through the factor $J$ inside the logarithm.

What Unpenalized Selection Pays

Let $M=|\mathcal F|$, which is at most $\sum_{j=1}^Jm_j$ and equals that sum when the classes are disjoint. For the unpenalized empirical risk minimizer $\tilde f$, the same simultaneous deviation argument gives $$ R(\tilde f)-R(f^*)\leq\frac{4c}{3n}\log\!\left(\frac{2M}{\delta}\right) $$ with probability at least $1-\delta$. Indeed, apply the proved deviation inequality with $a=\log(2M/\delta)/n$ to every predictor in the union. Since $\widehat R_n(\tilde f)\leq\widehat R_n(f^*)$, its empirical-risk difference in that inequality is nonpositive, leaving the stated bound.

This bound pays for the entire candidate set. Penalized selection instead gives a bound involving $m_{j^*}$, the size of the class containing the best predictor. When $m_{j^*}$ is much smaller than $M$, this can materially reduce the complexity term. The penalty itself is part of the selection rule; the oracle bound explains why paying it can be preferable to choosing solely by empirical fit.

Common Pitfalls and Scope

Ignoring multiplicity. Treating the empirical risk of the selected predictor as if that predictor had been fixed in advance overlooks the search across candidates. The logarithmic term controls simultaneous deviations.
Dropping the class-count or confidence factor. For the displayed guarantee, the penalty uses $\log(2Jm_j/\delta)$, not just $\log(m_j)$. Changing a logarithm's argument changes the bound and its stated confidence calibration.
Claiming a fast rate without its condition. The order-$\log(m)/n$ result here relies on the excess-loss Bernstein condition. Bounded losses and finiteness alone do not imply that condition.
Interpreting a penalty as a guarantee of selecting the oracle class. The theorem bounds the risk of the selected predictor; it does not say the selected class must contain $f^*$.
Mixing risk and empirical risk. The selection rule minimizes empirical risk plus penalty. The oracle inequality is a statement about population risk, and its proof needs a deviation argument to connect the two.

Key takeaway: For a finite collection of bounded-loss predictors satisfying an excess-loss Bernstein condition, a penalty proportional to $\log(Jm_j/\delta)/n$ yields a fast high-probability oracle bound. Its advantage over unpenalized empirical selection is adaptivity to the size of the comparator's class rather than the full candidate set.

Check Your Understanding

Use the assumptions and notation stated above.

Why does a finite class of size $m_j$ contribute a logarithm of $m_j$, rather than a term proportional to $m_j$, in the penalty?
Which assumption in the theorem supports a penalty of order $\log(m_j)/n$, and what is its role in the proof?
If all classes have the same size, when does adding the class penalty leave the empirical-risk selection unchanged?
What quantity determines the complexity term in the penalized oracle bound, and what quantity determines it for unpenalized empirical selection?
For $C=1/2$, compute $c$ and explain how increasing the confidence requirement (decreasing $\delta$) changes the penalty.