Localized Complexity for Neural Network Excess Risk

Why Localize Complexity?

A global complexity bound treats every predictor in a neural-network class as equally relevant, whether its risk is nearly optimal or far worse than the best available risk. For excess-risk analysis, that can be wasteful: empirical risk minimization is competing with predictors that have low population risk, and the stochastic fluctuations of their excess losses may be smaller than those of the entire class.

Localization measures the richness of predictors near a risk benchmark. When the predictors in that region have smaller second moments of excess loss, or when there are fewer of them, their empirical fluctuations can be smaller too. A fixed-point bound balances this local fluctuation against the excess risk itself.

Definition: Let $Z_1,\ldots,Z_n$ be independent observations from a distribution $P$, and let $P_n h=n^{-1}\sum_{i=1}^n h(Z_i)$. Let $\mathcal F$ be a finite class of predictors, with loss $\ell_f(Z)$, and choose a risk minimizer $f^*\in\arg\min_{f\in\mathcal F}P\ell_f$. The excess loss and excess risk of $f$ are $$ g_f(Z)=\ell_f(Z)-\ell_{f^*}(Z), \qquad \Delta_f=Pg_f=P\ell_f-P\ell_{f^*}. $$ For $r\geq 0$, the localized excess-loss class is $\mathcal G(r)=\{g_f:f\in\mathcal F,\ \Delta_f\leq r\}$. Its expected localized Rademacher complexity is $$ \mathfrak R_n(r)=E\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 Rademacher variables, independent of the observations, with probabilities $1/2$ on $1$ and $-1$.

The benchmark $f^*$ need not be a neural network of a particular architecture; it is the risk minimizer in the candidate class being analyzed. The class can, for example, be a finite network sieve, or a finite collection of neural predictors. We assume below that the losses are bounded so that the excess losses satisfy $|g_f|\leq 1$. Since $f^*$ minimizes risk, $\Delta_f\geq 0$.

A Localized Rademacher Bound

For a finite localized class, its size and its population second moments control its expected Rademacher complexity. The important detail is to take the exponential-moment bound over both the observations and the signs before bounding the supremum. This avoids replacing a maximum of empirical second moments by a maximum of population second moments, which is not generally valid.

Proposition: Suppose $\mathcal G(r)$ contains at most $M(r)$ functions and $|g|\leq 1$ for every $g\in\mathcal G(r)$. Write $H(r)=\log M(r)$, and suppose $v(r)=\max_{g\in\mathcal G(r)}Pg^2$. Then $$ \mathfrak R_n(r)\leq \sqrt{\frac{2v(r)H(r)}{n}}+\frac{H(r)}{3n}. $$ If $M(r)=1$, the complexity is zero.

Proof. For any one $g$, let $W=\varepsilon g(Z)$, where $Z\sim P$ and $\varepsilon$ is an independent Rademacher variable. Then $EW=0$, $EW^2=Pg^2$, and $|W|\leq 1$. The Bernstein exponential-moment inequality for a centered random variable bounded in absolute value by $1$ gives, for $0\leq t<3$, $$ E e^{tW}\leq \exp\left(\frac{t^2 Pg^2}{2(1-t/3)}\right). $$ Independence across observations therefore gives $$ E\exp\left(\frac{\lambda}{n}\sum_{i=1}^n\varepsilon_i g(Z_i)\right) \leq \exp\left(\frac{\lambda^2 Pg^2}{2n(1-\lambda/(3n))}\right), \qquad 0\leq\lambda<3n. $$ For the maximum over the finite class, the log-sum-exp inequality and Jensen's inequality for the logarithm imply $$ E\sup_{g\in\mathcal G(r)}\frac{1}{n}\sum_{i=1}^n\varepsilon_i g(Z_i) \leq \frac{H(r)}{\lambda} +\frac{\lambda v(r)}{2n(1-\lambda/(3n))}. $$ This bound is unconditional: the second-moment term is the population quantity $Pg^2$, bounded by $v(r)$, rather than a maximum empirical second moment. Optimizing the Bernstein-form bound over $\lambda$ yields $\sqrt{2v(r)H(r)/n}+H(r)/(3n)$. If the class contains one function, the expectation of its signed sum is zero, proving the final claim. $\square$

Worked Example: Bounding Complexity in a Small Risk Region

Suppose a localized neural predictor class contains four excess-loss functions, $n=100$, and $Pg^2\leq 0.04$ for each one. Here $H(r)=\log 4$, so the proposition gives $$ \mathfrak R_n(r) \leq \sqrt{\frac{2(0.04)\log 4}{100}}+\frac{\log 4}{300}. $$ Using $\log 4\approx 1.3863$, the square-root term is $\sqrt{0.001109}\approx 0.0333$, and the second term is $1.3863/300\approx 0.00462$. Thus $\mathfrak R_n(r)\leq 0.0379$. This is an upper bound on the expected signed supremum, not a claim that every empirical Rademacher average in the region is at most $0.0379$.

Worked Example: Local Versus Global Neural Complexity

Consider a finite neural-network sieve with $2^{20}$ candidate predictors. Suppose only eight predictors have excess risk at most $r=0.05$, and assume $Pg_f^2\leq 0.2r=0.01$ for those eight. With $n=500$, the local bound is $$ \mathfrak R_n(0.05) \leq \sqrt{\frac{2(0.01)\log 8}{500}}+\frac{\log 8}{1500} \approx 0.00912+0.00139=0.01051. $$ For comparison, use the coarse global values $M=2^{20}$ and $Pg^2\leq 0.2$. They give $$ \mathfrak R_n(1) \leq \sqrt{\frac{2(0.2)\log(2^{20})}{500}} +\frac{\log(2^{20})}{1500} \approx 0.1053+0.00924=0.1145. $$ The local upper bound is about one tenth as large. The comparison depends on the stated local size and second-moment assumptions; it is not guaranteed merely because the predictors are neural networks.

A Fixed-Point Excess-Risk Bound

A smaller local complexity is useful when it yields a risk bound that is self-consistent: the excess risk is no larger than a scale at which the predictors already have sufficiently small complexity. The result below makes this idea precise for a finite class. Its proof uses a variance condition, a local count of predictors, and a peeling argument that handles predictors at every risk scale.

Theorem: Suppose $\mathcal F$ is finite, $|g_f|\leq 1$, and the excess losses satisfy the Bernstein condition $$ Pg_f^2\leq\kappa\Delta_f \quad\text{for every }f\in\mathcal F $$ for some $\kappa\geq 0$. Let $M(u)=|\{f\in\mathcal F:\Delta_f\leq u\}|$ and $H(u)=\log M(u)$. Assume $H(u)/u$ is nonincreasing for $0<u\leq 1$. Let $\hat f$ be an empirical risk minimizer over $\mathcal F$. For $0<\delta<1$, if $0<r\leq 1$ satisfies $$ \frac{nr}{2(\kappa+2/3)} \geq H(2r)+\log(2/\delta)+1, $$ then $$ P\{\Delta_{\hat f}\leq r\}\geq 1-\delta. $$ The left side grows linearly in $r$, while the right side is determined by the local count of predictors. Thus the smallest admissible $r$ is a fixed point of a local-complexity requirement.

Proof. Since $\hat f$ minimizes empirical risk and $f^*\in\mathcal F$, $P_n g_{\hat f}\leq 0$. For any $f$ with $\Delta_f>0$, the centered variable $g_f-\Delta_f$ has variance at most $Pg_f^2\leq\kappa\Delta_f$, and its absolute value is at most $2$. Bernstein's lower-tail inequality consequently gives $$ P\{P_n g_f\leq 0\} \leq \exp\left(-\frac{n\Delta_f^2} {2(\kappa\Delta_f+2\Delta_f/3)}\right) = \exp\left(-\frac{n\Delta_f}{2(\kappa+2/3)}\right). $$ Set $r_j=2^j r$, for integers $j\geq 0$, and use the shells $r_j<\Delta_f\leq 2r_j$ up to and including the first $j$ for which $2r_j>1$; these cover every $f$ with $\Delta_f>r$, since $\Delta_f\leq 1$. If $r=1$, there are no such predictors. For shells with $2r_j\leq 1$, the log-count is at most $H(2r_j)\leq 2^jH(2r)$, by the assumed monotonicity. The terminal shell has at most $M(1)$ predictors. If $2r\leq1$, then $H(1)\leq H(2r)/(2r)\leq 2^jH(2r)$, since at the first crossing $2^j>1/(2r)$. If $2r>1$, the only shell needed is $j=0$, and $M(1)=M(2r)$. Thus every shell's log-count is at most $2^jH(2r)$, and a union bound gives a shell probability at most $$ \exp\left(2^jH(2r)-\frac{n r_j}{2(\kappa+2/3)}\right). $$ The fixed-point condition and the elementary inequality $\log(2(j+1)^2/\delta)\leq 2^j[\log(2/\delta)+1]$ therefore bound the shell probability by $\delta/[2(j+1)^2]$. Summing over shells gives a total failure probability at most $\delta$, since $\sum_{j\geq 0}1/[2(j+1)^2]<1$. If $\Delta_{\hat f}>r$, then $\hat f$ lies in one of these shells and also has $P_n g_{\hat f}\leq 0$, an event covered by the union bound. Hence $P\{\Delta_{\hat f}>r\}\leq\delta$. $\square$

The local Rademacher bound gives a useful way to read the theorem's local-count term. For the region $\Delta_f\leq u$, the Bernstein condition gives $v(u)\leq\kappa u$, so $$ \mathfrak R_n(u)\leq \sqrt{\frac{2\kappa uH(u)}{n}}+\frac{H(u)}{3n}. $$ In particular, the fixed-point condition controls $H(2r)$, the same local entropy that appears in this Rademacher bound. When the local count grows slowly with $r$, the resulting risk guarantee can be substantially smaller than one obtained by substituting the size of the entire class at every scale. The theorem's assumptions are substantive: bounded loss alone does not imply the Bernstein condition, and a local complexity calculation alone does not establish the stated high-probability guarantee.

Worked Example: Checking a Fixed-Point Risk Radius

Suppose a finite neural sieve satisfies $\kappa=1$, and its local entropy obeys $H(u)\leq 10u$ over the relevant range. Take $n=1000$, $\delta=0.05$, and test $r=0.017$. Then $H(2r)\leq 10(0.034)=0.34$, and $$ \frac{nr}{2(\kappa+2/3)} =\frac{17}{2(1+2/3)} =\frac{17}{10/3}=5.1. $$ The right side of the theorem's condition is at most $$ 0.34+\log(40)+1\approx 0.34+3.6889+1=5.0289. $$ Since $5.1\geq 5.0289$, the condition holds, and the empirical risk minimizer has excess risk at most $0.017$ with probability at least $0.95$. At $r=0.016$, the left side is $4.8$, while the corresponding right side is at most $0.32+\log(40)+1\approx 5.0089$. Since this upper bound exceeds $4.8$, the stated entropy upper bound alone does not certify that smaller radius.

What the Bound Says About Neural Predictors

For neural predictors, the candidate class may be restricted by architecture, norm constraints, or an explicit finite sieve. The local count $M(u)$ then asks how many candidates in that class have excess risk no greater than $u$. Norm-based or covering arguments can help bound the number of distinguishable predictors; the localized analysis uses the resulting count only near the risk levels that matter.

The theorem also separates two sources of improvement. A small $H(u)$ means few predictors lie near the optimum. A small $\kappa$ means the excess losses in that region have small second moments relative to their mean excess risk. Either can help, but they are different assumptions. The local Rademacher calculation records both through $H(u)$ and $v(u)$; the fixed-point theorem uses the variance condition to turn that local information into a risk guarantee.

Common Mistake: Maximizing Before Taking Expectations

A tempting but invalid argument is to condition on the observations, bound a signed sum using the largest empirical second moment among the localized predictors, and then claim its expectation is controlled by $n\max_g Pg^2$. In general, $$ E\left[\max_g\sum_{i=1}^n g(Z_i)^2\right] \not\leq n\max_g Pg^2. $$ For a simple counterexample with $n=1$, let two predictors have squared excess losses equal to $1/4$ on disjoint events, each of probability $1/4$, and zero otherwise. Each has population second moment $1/16$, so $n\max_g Pg^2=1/16$. But the maximum of the two squared losses is $1/4$ on an event of probability $1/2$, giving expectation $1/8$, which is larger. The correction is to bound the exponential moment jointly over observations and signs for each fixed predictor, then use log-sum-exp over the finite class, as in the proposition's proof.

Key takeaway: Localized Rademacher complexity measures fluctuations among predictors near a risk benchmark. A fixed-point excess-risk guarantee requires more than localization: it also needs conditions controlling second moments, class size across risk scales, and empirical minimization.

Check Your Understanding

Work through these questions to check the role of localization and the assumptions behind the bound.

Why is the local class defined using population excess risk rather than empirical excess risk?
In the localized Rademacher proposition, where does finiteness of the class enter the proof?
Under the Bernstein condition $Pg_f^2\leq\kappa\Delta_f$, what upper bound does it give for the second moments in $\mathcal G(r)$?
Why does an empirical risk minimizer satisfy $P_n g_{\hat f}\leq 0$?
Explain why the fixed-point theorem does not follow from bounded losses alone.
Identify the invalid step in replacing a maximum empirical second moment by the maximum population second moment, and describe the unconditional exponential-moment correction.