Deriving Fast Rates from Bernstein Curvature

From Curvature to a Fast Excess-Risk Rate

A uniform estimation bound often controls risk error at a square-root scale. That scale need not be the final rate for learning: near a risk minimizer, the loss differences may have much less variance than they do across the whole class. A Bernstein condition expresses this reduction. Combined with a localized complexity bound, it makes the estimation error smaller precisely where a competitive predictor must lie.

The goal here is to derive that rate transformation. The key balance is between a deviation term that depends on the excess risk itself and the excess risk being bounded. Stronger variance decay makes the balance more favorable, changing a square-root rate into a faster one.

Excess Loss and the Bernstein Condition

Let $Z_1,\ldots,Z_n$ be independent observations from a distribution $P$, and let $P_n g=n^{-1}\sum_{i=1}^n g(Z_i)$ denote the empirical average of a function $g$. For a predictor $h$, write its loss at observation $z$ as $\ell_h(z)$, and its risk as $R(h)=P\ell_h$. Suppose a risk minimizer $h^*$ exists in the class under study. Define the excess-loss function $g_h=\ell_h-\ell_{h^*}$ and its mean $r(h)=Pg_h=R(h)-R(h^*)$, which is nonnegative.

Definition: A class of excess losses satisfies a Bernstein condition with parameters $B>0$ and $\beta\in[0,1]$ if $$ \operatorname{Var}(g_h(Z))\le B\{Pg_h\}^{\beta} $$ for every $h$ in the class. The exponent $\beta$ describes how quickly the variance can decrease as excess risk approaches zero. For $\beta=0$, the condition only requires a uniform variance bound; larger $\beta$ imposes stronger variance decay near the minimizer.

The condition is about the variance of the excess loss, not necessarily the variance of the original loss. This distinction matters: subtracting the comparator loss can reveal that predictors close in risk also have more concentrated loss differences.

To make the rate derivation precise, we state the localized complexity input in a form that can be used directly. It is typically obtained by controlling the empirical process on classes restricted to small excess risk, with the Bernstein condition supplying the variance scale. The quantity $q_n$ below summarizes that complexity and the desired confidence level; it is dimensionless and is assumed to satisfy $0<q_n\le1$.

Localized deviation bound: Suppose that, with probability at least $1-\delta$, simultaneously for every $h$ in the class, $$ \left|(P-P_n)g_h\right| \le 2\left\{\sqrt{q_n\{Pg_h\}^{\beta}}+q_n\right\}. $$ Here $P$ and $P_n$ act on the excess-loss function $g_h$. This is the empirical-process input for the derivation: the stochastic term decreases with the excess risk, while $q_n$ records the localized complexity and confidence cost.

In applications, the constants in such a deviation bound can depend on the loss bound, the Bernstein constant, and the chosen complexity estimate. We use the displayed constants to keep the algebra visible. The rate exponent does not depend on these particular numerical constants.

Worked Example: Reading the Localized Deviation Scale

Suppose a localized analysis gives $q_n=0.01$, and consider a candidate with excess risk $r=Pg_h=0.04$. Under a Bernstein exponent $\beta=1$, the displayed deviation bound is $$ 2\left\{\sqrt{0.01(0.04)}+0.01\right\} =2\{0.02+0.01\}=0.06. $$ Thus the absolute difference between empirical and population excess loss is at most $0.06$ on the event in the bound. The variance-sensitive part is $0.02$; the additional $0.01$ term remains even at very small risk and cannot be dropped from the general inequality.

The ERM Rate: A Complete Derivation

Assume an empirical risk minimizer $\hat h$ exists, so $P_n\ell_{\hat h}\le P_n\ell_{h^*}$, equivalently $P_ng_{\hat h}\le0$. The following result converts the localized deviation bound into a population excess-risk guarantee. The conclusion is on the same event of probability at least $1-\delta$.

Theorem: Under the localized deviation bound above, an empirical risk minimizer satisfies $$ R(\hat h)-R(h^*)\le 16^{1/(2-\beta)}q_n^{1/(2-\beta)}. $$

Proof. Let $r=Pg_{\hat h}\ge0$. Since $P_ng_{\hat h}\le0$, $$ r=P g_{\hat h} =P_ng_{\hat h}+(P-P_n)g_{\hat h} \le \left|(P-P_n)g_{\hat h}\right| \le 2\sqrt{q_n r^\beta}+2q_n. $$ If $r<4q_n$, then $r<4q_n\le4q_n^{1/(2-\beta)}$, because $q_n\le1$ and $1/(2-\beta)\le1$. This is at most $16^{1/(2-\beta)}q_n^{1/(2-\beta)}$.

Otherwise $r\ge4q_n$, so $2q_n\le r/2$. Substituting this into the inequality for $r$ gives $$ \frac{r}{2}\le2\sqrt{q_n r^\beta}. $$ Both sides are nonnegative. Squaring and dividing by $r^\beta>0$ yields $$ r^{2-\beta}\le16q_n, \qquad r\le16^{1/(2-\beta)}q_n^{1/(2-\beta)}. $$ The two cases establish the claimed bound. $\square$

The exponent follows from balancing the risk against the risk-dependent part of the deviation. Ignoring the additive $q_n$ term momentarily, the balance is $r\asymp\sqrt{q_n r^\beta}$. Squaring gives $r^{2-\beta}\asymp q_n$, and hence $r\asymp q_n^{1/(2-\beta)}$. The proof above verifies that the additive term does not spoil that rate when $q_n\le1$.

Worked Example: No Curvature Improvement

Take $\beta=0$ and $q_n=0.01$. The theorem gives $$ r\le16^{1/2}(0.01)^{1/2} =4(0.1)=0.4. $$ The rate is proportional to $q_n^{1/2}$. This is the square-root regime: a uniform variance bound alone does not make the deviation shrink further as excess risk becomes small. If $q_n$ is proportional to an effective complexity divided by $n$, this is the familiar square-root dependence on that ratio.

Worked Example: Intermediate Bernstein Curvature

Take $\beta=1/2$ and $q_n=0.01$. Now $1/(2-\beta)=2/3$, so $$ r\le16^{2/3}(0.01)^{2/3} \approx 6.3496(0.046416) \approx0.2947. $$ The rate has exponent $2/3$ in $q_n$, rather than $1/2$. For a small complexity scale $q_n$, this exponent gives a smaller power-law bound. The numerical guarantee is conservative because it retains the constants in the stated deviation inequality.

Worked Example: Linear Variance Decay

Take $\beta=1$ and $q_n=0.01$. The theorem gives $$ r\le16^{1/(2-1)}(0.01)^{1/(2-1)} =16(0.01)=0.16. $$ Here the deviation term that depends on risk is proportional to $\sqrt{q_n r}$. Balancing $r$ with this term gives $r$ of order $q_n$, a fast rate. In particular, if $q_n$ is proportional to an effective complexity divided by $n$, the resulting dependence on sample size is of order $1/n$, up to the complexity and confidence factors.

How the Curvature Changes the Rate

The rate exponent is $p(\beta)=1/(2-\beta)$. As $\beta$ increases from zero to one, $p(\beta)$ increases from $1/2$ to $1$. For $0<q_n\le1$, increasing the exponent decreases $q_n^{p(\beta)}$; this is why stronger variance decay leads to a sharper guarantee.

Rate comparison: If the localized complexity scale is $q_n$, the excess-risk rate is $q_n^{1/(2-\beta)}$. At $\beta=0$ it is $q_n^{1/2}$; at $\beta=1/2$ it is $q_n^{2/3}$; and at $\beta=1$ it is $q_n$, up to constants.

This comparison is about the exponent, not a promise that every problem with a larger $\beta$ has a smaller bound at every sample size: constants and the actual value of $q_n$ also matter. Nor does the derivation say that a Bernstein condition alone supplies a good rate. The localized complexity bound is still needed to control empirical fluctuations; curvature improves the conversion from that control to excess risk.

Why Localization Matters—and a Common Pitfall

A global deviation bound treats every candidate as though its loss difference were equally variable. It can therefore stop at a square-root rate even when the excess losses near the minimizer have much smaller variance. Localization makes the complexity calculation sensitive to the risk region in which a competitive empirical minimizer must lie. The Bernstein condition then links that region's risk radius to its fluctuation size.

Common mistake: From the fact that $\hat h$ minimizes empirical risk, one might reason that its excess risk is at most the uniform deviation bound evaluated at the largest possible risk. That discards the dependence on $Pg_h$, so it cannot yield the fast-rate improvement. The correction is to keep $r=Pg_{\hat h}$ inside the localized deviation term and solve the resulting inequality $r\le2\sqrt{q_n r^\beta}+2q_n$. The risk-dependent term is exactly what produces the exponent $1/(2-\beta)$.

A second caution is that a rate statement must retain its assumptions. The derivation uses an existing population minimizer in the class, an empirical minimizer, and a simultaneous localized deviation event. If optimization is approximate, or if the target is a minimizer outside the class, additional terms and assumptions are needed; those changes should not be hidden inside the curvature exponent.

Check Your Understanding

Use the localized deviation inequality and the proof to answer the following questions.

What does the Bernstein exponent $\beta$ say about the variance of excess losses as their mean approaches zero?
Starting from $r\le2\sqrt{q_n r^\beta}+2q_n$, how does the balance of the risk-dependent term give the exponent $1/(2-\beta)$?
For $\beta=3/4$, what is the exponent of $q_n$ in the resulting rate?
Why does an ERM satisfy $P_ng_{\hat h}\le0$, and where is that fact used in the theorem proof?
Why can a global deviation bound fail to show the improvement associated with $\beta>0$?