Bernstein Conditions for Fast Rates

Why Excess-Loss Variance Matters

A risk minimizer is useful not only because it has the smallest expected loss, but also because losses of near-minimizers may fluctuate less. A condition relating fluctuation to excess risk captures this behavior. When the variance becomes small as excess risk approaches zero, empirical comparisons can be more informative near the optimum than a uniform bound based only on the largest possible loss would suggest.

Let $Z$ have distribution $P$, let $f$ denote a predictor or candidate, and let $\ell_f(Z)$ be its loss. Write $R(f)=E[\ell_f(Z)]$, and choose a risk minimizer $f^*$ from the class under consideration. The excess loss is the random variable $g_f(Z)=\ell_f(Z)-\ell_{f^*}(Z)$. Its mean is the excess risk, $E[g_f]=R(f)-R(f^*)$, which is nonnegative by the minimizing property of $f^*$. The excess loss itself need not be nonnegative at every observation.

Definition: A class of excess losses satisfies a Bernstein condition with constants $B>0$ and $\beta\in(0,1]$ if, for every candidate $f$ in the specified class, $$ \operatorname{Var}(g_f)\leq B\{E[g_f]\}^{\beta}. $$ Here $g_f=\ell_f-\ell_{f^*}$, and the condition is required only where the stated assumptions apply. The case $\beta=1$ is called a linear Bernstein condition. The constant and exponent describe how quickly variance can decrease as excess risk becomes small.

The variance is centered at the mean: $\operatorname{Var}(g_f)=E[(g_f-E[g_f])^2]$. It is always bounded above by the second moment $E[g_f^2]$, since $\operatorname{Var}(g_f)=E[g_f^2]-\{E[g_f]\}^2$. Thus, a proof that controls the second moment also proves a Bernstein condition. A condition may be global over the whole class or local to candidates with small excess risk; the scope must be stated rather than assumed.

A Basic Result for Bounded Excess Losses

A particularly transparent sufficient condition is pointwise nonnegativity together with boundedness. This requirement is stronger than merely saying that $f^*$ minimizes expected risk.

Theorem: Suppose $0\leq g_f(Z)\leq M$ almost surely for every $f$ in a class, where $M$ is a fixed finite constant. Then that class satisfies a linear Bernstein condition with $B=M$: $$ \operatorname{Var}(g_f)\leq M E[g_f]. $$

Proof. Since $0\leq g_f\leq M$, multiplication by the nonnegative quantity $g_f$ gives $g_f^2\leq M g_f$ almost surely. Taking expectations yields $E[g_f^2]\leq M E[g_f]$. Centering can only reduce the second moment, so $$ \operatorname{Var}(g_f)=E[g_f^2]-\{E[g_f]\}^2 \leq E[g_f^2]\leq M E[g_f]. $$ This is the claimed condition. $\square$

Worked Example: A Bounded Classification Excess Loss

Suppose the label is a deterministic function of the input, and $f^*$ predicts that label correctly at every input. A candidate classifier $f$ has zero-one loss, so its excess loss relative to $f^*$ is $g_f(Z)=1$ when $f$ makes an error and $g_f(Z)=0$ otherwise. If the probability of an error is $p=0.2$, then

E[g_f]=0.2,\qquad \operatorname{Var}(g_f)=0.2(1-0.2)=0.16.

The excess loss lies between zero and one, so the theorem gives $\operatorname{Var}(g_f)\leq E[g_f]=0.2$, which the calculation verifies. The key feature is not just that the loss is bounded: the comparator is correct pointwise, making the excess loss nonnegative at every observation.

Squared-Error Regression

For squared-error regression, a linear Bernstein condition follows under a useful combination of bounded prediction deviation and controlled conditional noise variance. Let $X$ be the input, suppose $E[Y\mid X]=m(X)$, and compare a predictor $f$ with the regression function $m$. Define $\varepsilon=Y-m(X)$ and $d=f(X)-m(X)$. The conditional mean-zero property is $E[\varepsilon\mid X]=0$.

Result: Suppose $|f(X)-m(X)|\leq D$ almost surely and $E[\varepsilon^2\mid X]\leq v$ almost surely, for finite constants $D,v$. For squared loss $\ell_f(X,Y)=(Y-f(X))^2$, the excess loss $g_f=\ell_f-\ell_m$ satisfies $$ \operatorname{Var}(g_f)\leq (D^2+4v)\{R(f)-R(m)\}. $$

Derivation. Expanding the squared losses gives $$ g_f=(\varepsilon-d)^2-\varepsilon^2=d^2-2\varepsilon d. $$ Conditioning on $X$ and using $E[\varepsilon\mid X]=0$, we obtain $E[g_f\mid X]=d^2$. Consequently, $$ E[g_f]=E[d^2]=R(f)-R(m). $$ For the second moment, expand the square and again condition on $X$: $$ E[g_f^2\mid X] =d^4-4d^3 E[\varepsilon\mid X]+4d^2 E[\varepsilon^2\mid X] =d^4+4d^2 E[\varepsilon^2\mid X]. $$ The assumed bounds imply $d^4\leq D^2d^2$ and $4d^2 E[\varepsilon^2\mid X]\leq4vd^2$. Taking expectations therefore yields $$ \operatorname{Var}(g_f)\leq E[g_f^2]\leq(D^2+4v)E[d^2] =(D^2+4v)\{R(f)-R(m)\}. $$ This proves the result. The bound uses both the conditional mean and the conditional variance assumptions; a bounded response or a squared loss by itself does not establish it.

Worked Example: Checking the Regression Bound Numerically

Let $X$ be constant, let $m(X)=0$, and let the noise $\varepsilon=Y$ equal $1$ or $-1$ with probability $1/2$ each. Take the constant predictor $f(X)=0.5$. Here $D=0.5$, $v=1$, and the excess loss is

$$ g_f=(Y-0.5)^2-Y^2=0.25-Y. $$

Thus $g_f=-0.75$ when $Y=1$ and $g_f=1.25$ when $Y=-1$, each with probability $1/2$. Its mean is $E[g_f]=(-0.75+1.25)/2=0.25$, equal to the excess risk $E[(f-m)^2]=0.25$. Its variance is $$ \operatorname{Var}(g_f)=\tfrac12(-0.75-0.25)^2+\tfrac12(1.25-0.25)^2=1. $$ The derived upper bound is $(D^2+4v)E[g_f]=(0.25+4)(0.25)=1.0625$, so $1\leq1.0625$, as required. Notice that the excess loss can be negative for an individual observation even though its mean is positive.

Curvature and Lipschitz Losses

Another route to a linear condition connects risk curvature to the size of observation-level loss changes. Let $f_\theta$ be indexed by a parameter $\theta$ in a normed space, and let $\theta^*$ minimize the risk. Suppose the risk has quadratic growth around its minimizer, while individual losses change at most linearly with parameter distance.

Theorem: Suppose, for all parameters $\theta$ under consideration, $$ R(f_\theta)-R(f_{\theta^*})\geq \frac{\lambda}{2}\|\theta-\theta^*\|^2 $$ for some $\lambda>0$, and suppose $$ |\ell_{f_\theta}(Z)-\ell_{f_{\theta^*}}(Z)| \leq G\|\theta-\theta^*\| $$ almost surely for some $G<\infty$. Then the excess loss satisfies $$ \operatorname{Var}(g_\theta) \leq \frac{2G^2}{\lambda}\{R(f_\theta)-R(f_{\theta^*})\}. $$

Proof. Squaring the pointwise loss bound and taking expectations gives $E[g_\theta^2]\leq G^2\|\theta-\theta^*\|^2$. Since variance is at most the second moment, $\operatorname{Var}(g_\theta)\leq G^2\|\theta-\theta^*\|^2$. The quadratic-growth assumption rearranges to $\|\theta-\theta^*\|^2\leq 2\{R(f_\theta)-R(f_{\theta^*})\}/\lambda$. Combining the two inequalities proves the claim. $\square$

Strong convexity of a differentiable risk on a convex parameter set, with an interior minimizer, is one standard sufficient condition for this quadratic growth. The theorem also makes an important qualification visible: curvature alone does not bound the random loss difference. A pointwise Lipschitz or comparable fluctuation assumption is needed as well.

Worked Example: A Curved Risk with a Linear Bernstein Condition

Let $A$ equal $1$ or $-1$ with equal probability, let $\theta\in[-1,1]$, and define the loss $\ell_\theta(A)=1+\theta^2/2+A\theta$. This loss is nonnegative on the stated parameter range: its minimum over $A$ is $1+\theta^2/2-|\theta|$, which is at least $1/2$. The risk and its minimizer are $$ R(\theta)=E[\ell_\theta(A)]=1+\theta^2/2,\qquad \theta^*=0. $$ The excess risk is $\theta^2/2$, so the risk has quadratic growth with $\lambda=1$. The excess loss is $g_\theta=\theta^2/2+A\theta$; because $A$ has mean zero and variance one, $$ E[g_\theta]=\theta^2/2,\qquad \operatorname{Var}(g_\theta)=\operatorname{Var}(A\theta)=\theta^2 =2\{R(\theta)-R(0)\}. $$ Thus the condition holds with $B=2$. The loss difference also satisfies $|g_\theta|\leq|\theta|+\theta^2/2\leq1.5|\theta|$ for $|\theta|\leq1$. The curvature-and-Lipschitz theorem therefore supplies a valid, though looser, upper bound with $G=1.5$: its constant is $2G^2/\lambda=4.5$. Direct calculation gives the sharper constant $2$.

What Boundedness Does—and Does Not—Give

Bounded losses are often useful for concentration arguments, but boundedness alone does not imply a Bernstein condition. If $g_f$ can take both signs, a small mean may result from cancellation while the second moment stays large. For example, if $g_f$ equals $1$ and $-1$ with equal probability, then $E[g_f]=0$ but $\operatorname{Var}(g_f)=1$. No finite $B$ can make $\operatorname{Var}(g_f)\leq B E[g_f]$ hold in this case.

Such a variable can arise as a difference between two bounded losses for candidates with equal risk. For instance, on two equally likely outcomes, let the losses of two candidates be $(1,0)$ and $(0,1)$. Their risks are both $1/2$, but their loss difference takes values $1$ and $-1$. Both losses are bounded; the difference is not pointwise nonnegative. This is why the bounded-excess theorem required $0\leq g_f$, not merely bounded losses.

Bernstein conditions matter because they describe how much random variation remains when a candidate is close to optimal in risk. Combined with suitable empirical-process control, smaller variance near the optimum can support sharper generalization guarantees than bounds that use only a global loss range. The condition is an assumption or a consequence of additional structure; it is not automatic, and it does not by itself provide a risk bound.

Common pitfall: “The losses are bounded, so the excess-loss variance is at most a constant times excess risk.” This reasoning skips the sign of the excess loss. The implication follows directly when the excess loss is pointwise nonnegative and bounded, or when a separate argument—such as the regression calculation or the curvature-and-Lipschitz theorem—controls its second moment. Risk minimization alone guarantees only a nonnegative mean.

Check Your Understanding

Use the definitions and conditions above to answer the following questions.

State the Bernstein condition and explain the difference between the mean excess risk and the random excess loss.
Why does $0\leq g_f\leq M$ imply $\operatorname{Var}(g_f)\leq M E[g_f]$? Identify the inequality that uses nonnegativity.
In squared-error regression, where does the conditional mean-zero assumption enter the derivation of the excess risk and the second-moment bound?
Why does quadratic growth of the risk not establish the curvature-based Bernstein result without a bound on observation-level loss differences?
Give a bounded excess-loss distribution for which a linear Bernstein condition fails, and explain why boundedness alone does not prevent the failure.