Local Complexity of Finite Hypothesis Classes

Why Local Complexity Can Be Small

A finite hypothesis class may contain many candidate predictors, but only a few may have excess risk close to zero. Local complexity measures the random fluctuations of the candidates in this near-optimal region rather than paying for the entire class at every risk scale. For a finite class, the calculation is explicit: class size contributes a logarithm, while a Bernstein condition makes the fluctuation scale depend on the localization radius.

There is an important qualification. A second-moment bound does not, by itself, give a purely square-root finite-class bound at every sample size. A correct bound also has a term proportional to the logarithm of the class size divided by sample size. That term matters especially when the sample is small or the radius is very small.

Excess Losses and Radius-Restricted Complexity

Let $Z_1,\ldots,Z_n$ be independent observations from a distribution $P$, and let $\mathcal H$ be a finite hypothesis class. Suppose the loss $\ell_h(Z)$ lies in $[0,1]$ for each $h\in\mathcal H$. Assume a risk minimizer $h^\star\in\mathcal H$ exists, and define the excess-loss function $g_h(Z)=\ell_h(Z)-\ell_{h^\star}(Z)$. Write $Pg=E[g(Z)]$. Then $Pg_h\geq 0$, although $g_h(Z)$ may be negative for individual observations.

Definition: For a radius $r\geq 0$, the population-localized excess-loss class is $\mathcal G(r)=\{g_h:h\in\mathcal H,\ Pg_h\leq r\}$. Its expected radius-restricted Rademacher complexity is $$ \mathcal R_n(r)=E_{Z_1,\ldots,Z_n,\varepsilon_1,\ldots,\varepsilon_n} \left[\sup_{g\in\mathcal G(r)}\frac{1}{n}\sum_{i=1}^n\varepsilon_i g(Z_i)\right], $$ where the $\varepsilon_i$ are independent of the data and of one another, with $P(\varepsilon_i=1)=P(\varepsilon_i=-1)=1/2$. The zero function belongs to the excess-loss class, so the supremum is nonnegative.

The localization is by population excess risk: membership in $\mathcal G(r)$ means $Pg\leq r$. This is a deterministic restriction on functions, not a restriction chosen after observing the sample.

Bernstein condition: For a constant $B>0$, the excess-loss class satisfies the Bernstein condition with constant $B$ if $P g_h^2\leq B\,P g_h$ for every $h\in\mathcal H$. Consequently, $Pg^2\leq Br$ for every $g\in\mathcal G(r)$.

Worked Example: Localizing a Rare-Event Loss

Let $Z$ be uniform on $\{1,\ldots,100\}$, and consider the zero function and the 100 indicators $g_j(z)=1_{\{z=j\}}$. For each indicator, $Pg_j=1/100=0.01$ and $Pg_j^2=0.01$. Thus at radius $r=0.01$, all 101 functions are localized, and the Bernstein condition holds with $B=1$.

Take $n=1$. If the Rademacher sign is $+1$, the observed point $Z$ identifies an indicator with value 1, so the supremum over the class is 1. If the sign is $-1$, every signed indicator is at most 0, and the zero function gives supremum 0. Therefore

\mathcal R_1(0.01)=\frac{1}{2}(1)+\frac{1}{2}(0)=0.5.

This example will also show why omitting the linear term in the finite-class bound can make the claimed inequality false.

A Finite-Class Bound

The following result applies to any deterministic finite class of functions bounded in absolute value by 1. The second-moment bound controls the variance of each signed summand. A moment-generating-function bound and a maximum over the finite class then give the complexity estimate.

Theorem: Let $\mathcal G$ be a finite class of at most $M$ measurable functions satisfying $|g(Z)|\leq 1$ almost surely and $Pg^2\leq v$ for every $g\in\mathcal G$, where $v\geq 0$. Then $$ E\sup_{g\in\mathcal G}\frac{1}{n}\sum_{i=1}^n\varepsilon_i g(Z_i) \leq \sqrt{\frac{2v\log M}{n}}+\frac{\log M}{3n}. $$ In particular, under the Bernstein condition, for $M_r=|\mathcal G(r)|$, $$ \mathcal R_n(r)\leq \sqrt{\frac{2Br\log M_r}{n}}+\frac{\log M_r}{3n}. $$

Proof. Fix $g\in\mathcal G$ and put $W_i=\varepsilon_i g(Z_i)$. The $W_i$ are independent, $E[W_i]=0$, $|W_i|\leq 1$, and $E[W_i^2]=Pg^2\leq v$. For $0\leq\lambda<3$, expand the exponential. Since $E[W_i]=0$, $|W_i|^k\leq W_i^2$ for integers $k\geq 2$, and $k!\geq 2\cdot 3^{k-2}$,

E[e^{\lambda W_i}] \leq 1+E[W_i^2]\sum_{k=2}^{\infty}\frac{\lambda^k}{k!} \leq 1+\frac{v\lambda^2}{2(1-\lambda/3)} \leq \exp\left(\frac{v\lambda^2}{2(1-\lambda/3)}\right).

Independence gives the corresponding bound for the sum. With $S_g=n^{-1}\sum_i W_i$, it follows, for $0\leq\lambda<3n$, that

\log E[e^{\lambda S_g}] \leq \frac{(v/n)\lambda^2}{2\{1-\lambda/(3n)\}}.

For the maximum, $e^{\lambda\max_g S_g}\leq\sum_{g\in\mathcal G}e^{\lambda S_g}$. Jensen's inequality applied to the concave logarithm therefore yields

E[\max_g S_g] \leq \frac{\log M}{\lambda} +\frac{(v/n)\lambda}{2\{1-\lambda/(3n)\}}.

For $v>0$ and $M>1$, set $x=\log M$, $c=1/(3n)$, and $q=\sqrt{2x/(v/n)}$, and choose $\lambda=q/(1+cq)$. This is positive and less than $1/c=3n$. Substitution gives

\frac{x}{\lambda}+\frac{(v/n)\lambda}{2(1-c\lambda)} =\frac{x}{q}+cx+\frac{(v/n)q}{2} =\sqrt{\frac{2vx}{n}}+cx.

This proves the claimed bound. If $v=0$, every $g(Z_i)=0$ almost surely; if $M=1$, the expected signed sum is zero. These cases also satisfy the result. Finally, for $g\in\mathcal G(r)$, the Bernstein condition gives $Pg^2\leq B Pg\leq Br$; applying the first bound with $v=Br$ proves the localized version. $\square$

Worked Example: Checking the Necessary Linear Term

Return to the 101-function class in the rare-event example. The bound without a linear term would give

\sqrt{2Br\log M} =\sqrt{0.02\log(101)} \approx 0.3038.

But the exact complexity is $0.5$, so that proposed bound is too small. The theorem instead gives

\sqrt{0.02\log(101)}+\frac{\log(101)}{3} \approx 0.3038+1.5384 =1.8422.

This is a valid, though loose, upper bound. The additional term is not a detail that can be dropped: it is what makes this general finite-class guarantee applicable in the example.

Worked Example: An Exact Complexity for a Singleton

Let $\mathcal G=\{0,g\}$, where $g(z)=1$ for every $z$, and take $n=2$. The signed average for $g$ is $(\varepsilon_1+\varepsilon_2)/2$. Its positive value is 1 when both signs are positive, an event of probability $1/4$; otherwise its maximum with the zero function is 0. Hence

\mathcal R_2=\frac{1}{4}.

Here $Pg=Pg^2=1$, so the Bernstein condition holds with $B=1$, and $M=2$. The theorem gives

\mathcal R_2 \leq \sqrt{\frac{2\log 2}{2}}+\frac{\log 2}{6} \approx 0.8326+0.1155=0.9481.

The bound is conservative, but it is consistent with the exact value $0.25$. Its purpose is a general guarantee, not an exact evaluation for every class.

A Fixed Point for Excess Risk

The localized complexity bound suggests a scale at which the fluctuation size is no larger than the risk radius. For a high-probability ERM guarantee, a direct finite-class concentration argument gives a fixed point with the same square-root dependence on radius and an explicit confidence term. This derivation states its assumptions and does not require treating an expected Rademacher bound as though it were itself a high-probability deviation bound.

Theorem: Suppose $\mathcal H$ has $M$ elements, each loss lies in $[0,1]$, a risk minimizer $h^\star\in\mathcal H$ exists, and $P g_h^2\leq B\,P g_h$ for every excess loss $g_h=\ell_h-\ell_{h^\star}$. Let $\hat h$ be an empirical risk minimizer, and let $0<\delta<1$. Define $$ L=\log(M/\delta),\qquad \psi_\delta(r)=\sqrt{\frac{2BrL}{n}}+\frac{2L}{3n}. $$ Let $r_\delta$ be the unique nonnegative solution of $r=\psi_\delta(r)$. Then $$ P g_{\hat h}\leq r_\delta $$ with probability at least $1-\delta$.

Proof. Fix $h$ and write $g=g_h$. The centered variable $g(Z)-Pg$ has variance at most $Pg^2\leq B Pg$, and its absolute value is at most 2 because $|g|\leq1$. Bernstein's one-sided inequality gives, for $t>0$,

P\left(Pg-P_ng> \sqrt{\frac{2B(Pg)t}{n}}+\frac{2t}{3n}\right)\leq e^{-t},

where $P_ng=n^{-1}\sum_{i=1}^n g(Z_i)$. Apply this inequality to all $M$ excess losses and use the union bound with $t=L=\log(M/\delta)$. With probability at least $1-\delta$, every $h\in\mathcal H$ simultaneously satisfies $Pg_h-P_ng_h\leq\psi_\delta(Pg_h)$. On this event, empirical risk minimization implies $P_ng_{\hat h}\leq0$, since $h^\star$ is a candidate. Thus $x=Pg_{\hat h}\geq0$ satisfies $x\leq\psi_\delta(x)$.

To solve this inequality, put $a=\sqrt{2BL/n}$ and $c=2L/(3n)$. The equation $x=a\sqrt{x}+c$, after setting $u=\sqrt{x}$, becomes $u^2-au-c=0$. Its nonnegative solution is $u=(a+\sqrt{a^2+4c})/2$. Since $x-\psi_\delta(x)$ is increasing after its unique nonnegative zero, $x\leq\psi_\delta(x)$ implies

Pg_{\hat h}\leq r_\delta =\left(\frac{a+\sqrt{a^2+4c}}{2}\right)^2.

This proves the result. $\square$

Worked Example: Solving the Confidence Fixed Point

Suppose $M=20$, $n=1000$, $B=1$, and $\delta=0.05$. Then $L=\log(20/0.05)=\log(400)\approx5.991$, so

a=\sqrt{\frac{2L}{n}}\approx0.10947, \qquad c=\frac{2L}{3n}\approx0.003994.

The nonnegative root is

r_\delta =\left(\frac{0.10947+\sqrt{0.10947^2+4(0.003994)}}{2}\right)^2 \approx (0.1383)^2 \approx0.0191.

Under the stated loss and Bernstein assumptions, the ERM excess risk is therefore at most about $0.0191$ with probability at least $0.95$. The confidence fixed point uses $\log(M/\delta)$, while the expected localized complexity bound uses $\log M_r$; these are related finite-class calculations, not interchangeable probability statements.

Interpretation and a Common Pitfall

The localized complexity bound has two distinct contributions. The square-root term, $\sqrt{2Br\log M_r/n}$, shrinks as the localization radius shrinks and as the sample size grows. The linear term, $\log M_r/(3n)$, records the finite-class concentration cost that remains in this general bound. In fast-rate settings, balancing a radius against these fluctuation terms leads to a scale of order $(B+1)\log M/n$, up to constants, rather than the global square-root scale one obtains without localization.

Pitfall: dropping the linear term. It is tempting to infer a pure square-root bound from $Pg^2\leq Br$. The rare-event example verifies that this can fail: its exact complexity is $0.5$, larger than the proposed pure square-root value $0.3038$.
Pitfall: applying Jensen's inequality in the wrong direction. For a convex exponential, $E[e^U]\geq e^{E[U]}$, not the reverse. The proof above instead uses a bounded-variable moment-generating-function inequality, with its range restriction explicit.
Pitfall: confusing expected complexity and a high-probability risk bound. The expected Rademacher bound is not automatically a confidence guarantee. The fixed-point theorem uses a separate concentration argument and includes $\delta$ in its logarithmic factor.

The calculation is useful because it makes the roles of sample size, class size, localization, and curvature visible at once. Its guarantees are only as appropriate as their assumptions: the class must be finite, the loss bounded as stated, and the Bernstein condition must hold for the excess losses under consideration.

Check Your Understanding

Use the definitions and bounds above to answer the following.

Why does the population-localized class use $Pg\leq r$, rather than a condition involving the observed sample?
Which step in the finite-class complexity proof requires $|g(Z)|\leq1$?
For the 101-function rare-event class, what is the exact $n=1$ complexity, and why does it refute the pure square-root bound?
How does the Bernstein condition turn a risk-radius bound $Pg\leq r$ into a second-moment bound?
In the fixed-point theorem, why does empirical risk minimization imply $P_ng_{\hat h}\leq0$?