Bernstein Conditions And Self-Bounding Excess Risk

Why Excess Risk Can Have Smaller Fluctuations

A predictor with risk close to the best achievable risk is often easier to compare statistically with that best predictor than a poor predictor is. The reason can be quantified: the random difference in their losses may have a variance that decreases as the predictor’s excess risk decreases. This link between variance and risk is called a Bernstein condition. It is useful because concentration bounds then become more favorable near the risk minimizer, which can lead to faster rates than a generic square-root rate.

We work with a random observation $O$ and a predictor $f$ in a class $\mathcal F$. Write $\ell_f(O)$ for its loss, $R(f)=E[\ell_f(O)]$ for its risk, and suppose a risk minimizer $f^*$ exists. Define the excess-loss random variable $Z_f=\ell_f(O)-\ell_{f^*}(O)$ and the excess risk $r_f=R(f)-R(f^*)=E[Z_f]$. Thus $r_f\geq 0$. The variance in the condition below is over a fresh observation $O$, not over the observed sample.

Definition: The loss class satisfies a Bernstein condition with constants $B>0$ and $\beta\in[0,1]$ if, for every $f\in\mathcal F$, $$ \operatorname{Var}(Z_f)\leq B r_f^\beta . $$ For $\beta=0$, interpret $r_f^0=1$, including when $r_f=0$. The exponent $\beta$ describes how rapidly the variance bound improves as excess risk approaches zero. This is a condition on the loss differences relative to $f^*$, not on the variance of each loss separately.

The terminology self-bounding refers to the way the random fluctuation is controlled by the quantity being bounded. The standard deviation of the empirical average of $Z_f$ is on the order of $\sqrt{\operatorname{Var}(Z_f)/n}$, so the condition makes it at most $\sqrt{B r_f^\beta/n}$. When $r_f$ is small, this fluctuation can be substantially smaller than a bound that is uniform over all predictors.

Worked Examples of Bernstein Conditions

Worked Example: Binary Classification With a Margin Gap

Let $X$ be a feature, $Y\in\{0,1\}$ a label, and let a classifier $f$ take values in $\{0,1\}$. The loss is $\ell_f(X,Y)=\mathbf 1\{f(X)\ne Y\}$. Suppose $f^*(x)=\mathbf 1\{\eta(x)\geq 1/2\}$, where $\eta(x)=P(Y=1\mid X=x)$, is among the classifiers being considered. Assume a margin gap: for some $\kappa>0$, $|2\eta(X)-1|\geq\kappa$ almost surely.

The excess-loss variable $Z_f=\ell_f-\ell_{f^*}$ is zero whenever $f(X)=f^*(X)$. On disagreement, it is either $1$ or $-1$, so $Z_f^2=\mathbf 1\{f(X)\ne f^*(X)\}$. Conditional on $X=x$ where the classifiers disagree, choosing the non-Bayes label increases the conditional error probability by $|2\eta(x)-1|$. Therefore $$ r_f=E\!\left[|2\eta(X)-1|\mathbf 1\{f(X)\ne f^*(X)\}\right] \geq \kappa P(f(X)\ne f^*(X)). $$ It follows that $E[Z_f^2]\leq r_f/\kappa$. Since $\operatorname{Var}(Z_f)\leq E[Z_f^2]$, we obtain $\operatorname{Var}(Z_f)\leq r_f/\kappa$: the condition holds with $\beta=1$ and $B=1/\kappa$. For example, if $\kappa=0.4$ and $r_f=0.02$, then $\operatorname{Var}(Z_f)\leq 0.02/0.4=0.05$.

Worked Example: Bounded Squared-Error Regression

Suppose $0\leq Y\leq1$, predictors take values in $[0,1]$, and $f^*(X)=E[Y\mid X]$ belongs to the class. Use squared-error loss $\ell_f(X,Y)=(f(X)-Y)^2$. The excess-loss variable factors as $$ Z_f=(f(X)-Y)^2-(f^*(X)-Y)^2 =(f(X)-f^*(X))(f(X)+f^*(X)-2Y). $$

All three quantities $f(X)$, $f^*(X)$, and $Y$ lie in $[0,1]$, so $|f(X)+f^*(X)-2Y|\leq2$. Consequently $Z_f^2\leq4(f(X)-f^*(X))^2$. Also, conditioning on $X$ and using $E[Y\mid X]=f^*(X)$ gives $$ r_f=E[Z_f]=E[(f(X)-f^*(X))^2]. $$ Combining these facts yields $\operatorname{Var}(Z_f)\leq E[Z_f^2]\leq4r_f$. Thus this model satisfies the condition with $\beta=1$ and $B=4$. The bound depends on the regression identity and bounded range; it should not be assumed for arbitrary squared-error problems without checking those conditions.

Worked Example: Reading the Exponent as a Rate

Consider a finite class of $M=20$ predictors, with a risk minimizer in the class. Suppose losses lie in $[0,1]$, the Bernstein condition holds with $B=0.25$ and $\beta=1$, the sample size is $n=2000$, and the desired failure probability is $\delta=0.05$. The finite-class bound proved below uses $q=\log(M/\delta)=\log(400)\approx5.991$. Its excess-risk bound is $$ \left(\frac{8Bq}{n}\right)+\frac{8q}{3n} =\frac{8(0.25)(5.991)}{2000}+\frac{8(5.991)}{3(2000)} \approx0.00599+0.00799=0.01398. $$

The leading term is proportional to $1/n$, rather than $1/\sqrt n$. For comparison, if the same condition had $\beta=0$ and $B=1$, the bound would be $(8q/n)^{1/2}+8q/(3n)\approx0.1548+0.0080=0.1628$. The constants matter in finite samples, but the exponents reveal the asymptotic distinction.

From the Condition to a Finite-Class Rate

We first record the concentration inequality used in the derivation. If $W_1,\ldots,W_n$ are independent copies of $W$, $E[W]=\mu$, $\operatorname{Var}(W)=\sigma^2$, and $|W-\mu|\leq b$ almost surely, scalar Bernstein concentration gives, for $t>0$, $$ P\!\left(\frac1n\sum_{i=1}^n W_i-\mu <-\sqrt{\frac{2\sigma^2t}{n}}-\frac{2bt}{3n}\right)\leq e^{-t}. $$ The bounded-variable Bernstein inequality follows by applying the exponential Markov inequality to the centered sum and using, for $0<\lambda<3/b$, the moment-generating-function bound $E[e^{\lambda(W-\mu)}]\leq\exp\{\lambda^2\sigma^2/[2(1-\lambda b/3)]\}$; optimizing the resulting exponential bound gives the displayed inequality. We use its one-sided form because empirical risk minimization compares a predictor with $f^*$.

Theorem: Suppose $\mathcal F$ is finite with $|\mathcal F|=M$, $f^*\in\mathcal F$ minimizes $R$ over $\mathcal F$, and $0\leq\ell_f(O)\leq1$ for every $f\in\mathcal F$ almost surely. Assume the Bernstein condition holds over $\mathcal F$. Let $\hat f$ be an empirical risk minimizer based on $n$ independent observations. Then, with probability at least $1-\delta$, $$ R(\hat f)-R(f^*)\leq \left(\frac{8B\log(M/\delta)}{n}\right)^{1/(2-\beta)} +\frac{8\log(M/\delta)}{3n}. $$

Proof. For each $f$, let $Z_{f,i}=\ell_f(O_i)-\ell_{f^*}(O_i)$, and let $P_nZ_f=n^{-1}\sum_{i=1}^n Z_{f,i}$. Because both losses lie in $[0,1]$, $Z_f\in[-1,1]$, and hence $|Z_f-E[Z_f]|\leq2$. Apply the one-sided Bernstein inequality with $b=2$, $\sigma^2=\operatorname{Var}(Z_f)$, and $t=q=\log(M/\delta)$. The Bernstein condition and a union bound over $M$ predictors imply that, with probability at least $1-\delta$, every $f\in\mathcal F$ satisfies $$ P_n Z_f\geq r_f-\sqrt{\frac{2B r_f^\beta q}{n}}-\frac{4q}{3n}. $$

Since $\hat f$ minimizes empirical risk over a class containing $f^*$, $P_nZ_{\hat f}\leq0$. On the simultaneous event just obtained, write $r=R(\hat f)-R(f^*)\geq0$ and $a=4q/(3n)$. Then $r\leq\sqrt{2B r^\beta q/n}+a$. If $r\leq2a$, it is already bounded by $2a$. If $r>2a$, then $r-a>r/2$, so $$ \frac r2<\sqrt{\frac{2B r^\beta q}{n}} \quad\Longrightarrow\quad r^{2-\beta}<\frac{8Bq}{n} \quad\Longrightarrow\quad r<\left(\frac{8Bq}{n}\right)^{1/(2-\beta)}. $$ In either case $r\leq(8Bq/n)^{1/(2-\beta)}+2a$. Substituting $2a=8q/(3n)$ proves the claim. $\square$

When the Rate Is Faster

For fixed $B$ and a fixed finite class, the leading term has order $(\log(M/\delta)/n)^{1/(2-\beta)}$. At $\beta=0$, this is a square-root rate. At $\beta=1$, it is a $1/n$ rate, up to the class-size and confidence factors. Intermediate exponents interpolate between these cases. This is the main payoff of the condition: the variance decreases with excess risk, and the resulting concentration inequality can be solved at a faster scale.

The theorem requires the minimizer to be in the class and the losses to be bounded as stated. It does not itself establish a Bernstein condition; that must come from the prediction problem or be assumed and justified separately. Nor does the finite-class argument automatically prove a corresponding result for an infinite class. Such extensions require suitable uniform or localized control of empirical fluctuations.

Common Mistake: Confusing a Variance Bound With a Fast Rate

A tempting but incomplete argument is: “The excess-loss variance is small near the minimizer, so empirical risk minimization must have a $1/n$ rate.” Small variance alone does not give that conclusion. The power $\beta$ matters: a bound proportional to $r_f^\beta$ yields the exponent $1/(2-\beta)$, and only $\beta=1$ gives the $1/n$ leading rate in this calculation. In addition, the condition must hold uniformly over the relevant predictors, and the empirical comparison must be controlled, as it is by the finite-class union bound above.

A second error is to substitute the variance of $\ell_f$ for the variance of $Z_f=\ell_f-\ell_{f^*}$. The theorem uses the latter. The two quantities need not have the same behavior: subtracting the reference loss can remove shared randomness, while separate loss variances need not describe the fluctuation of the comparison that determines excess risk.

Key takeaway: A Bernstein condition states that excess-loss variance is at most $B$ times excess risk to the power $\beta$. Combined with concentration and empirical comparison, it gives a finite-class rate of order $(\log M/n)^{1/(2-\beta)}$, with a faster rate when the variance shrinks more strongly near the minimizer.

Check Your Understanding

Use the definitions and finite-class bound to answer the following.

In the definition, what random variable has its variance bounded, and what quantity is its expectation?
For which value of $\beta$ does the theorem give a leading $1/n$ rate, and what rate does $\beta=0$ give?
In the classification example, explain how the margin-gap assumption bounds the probability that $f$ disagrees with $f^*$.
Why does bounded loss in the theorem imply $|Z_f-E[Z_f]|\leq2$?
Why is it not enough to know that the variance of each individual loss $\ell_f$ is small?