Bernstein Conditions and Fast ERM Rates

Why Variance Can Improve an ERM Rate

For bounded losses, a uniform deviation bound typically controls empirical risks at a square-root scale in sample size. But the same amount of random fluctuation need not occur for every candidate: a hypothesis close to the best one in risk may also have an excess loss with small variance. A Bernstein condition formalizes this link. When it holds, Bernstein’s concentration inequality can give empirical risk minimization (ERM) a faster excess-risk rate than a generic bounded-loss argument.

We give a finite-class result. The key distinction is that the condition concerns the variance of the loss difference from a risk minimizer, not merely the variance of each loss separately. Throughout, observations $X_1,\ldots,X_n$ are independent and identically distributed from a distribution $P$. A hypothesis $h$ has measurable loss $\ell_h(X)$, population risk $R(h)=E[\ell_h(X)]$, and empirical risk $P_n\ell_h=n^{-1}\sum_{i=1}^n\ell_h(X_i)$.

Definition: Let $\mathcal H$ be a finite hypothesis class and suppose a risk minimizer $h^*\in\mathcal H$ exists, so $R(h^*)=\min_{h\in\mathcal H}R(h)$. The excess loss and excess risk of $h$ are $$ Z_h(X)=\ell_h(X)-\ell_{h^*}(X),\qquad r(h)=E[Z_h(X)]=R(h)-R(h^*)\geq 0. $$ A Bernstein condition with exponent $\beta\in[0,1]$ and constant $v>0$ is $$ \operatorname{Var}(Z_h(X))\leq v\,r(h)^\beta\qquad\text{for every }h\in\mathcal H. $$ When $\beta=0$, we interpret $r(h)^0=1$. We also assume a uniform bound $\lvert Z_h(X)-E[Z_h(X)]\rvert\leq B$ almost surely, for some $B>0$ and every $h\in\mathcal H$.

The centered bound is the form needed for Bernstein’s inequality. If each loss lies in $[0,1]$, then each difference $Z_h$ lies in $[-1,1]$, and hence $\lvert Z_h-E[Z_h]\rvert\leq 2$; one may take $B=2$. The Bernstein condition says more than boundedness: for $\beta>0$, smaller excess risk forces smaller variance. The case $\beta=1$ is especially useful because it will give a rate proportional to $1/n$, up to a logarithmic factor.

Worked Example: Verifying a Bernstein Condition

Suppose the excess loss $Z_h$ for one candidate takes value $1$ with probability $0.4$ and value $-1/3$ with probability $0.6$. Calculate its excess risk and variance, and check a Bernstein condition with $\beta=1$ and $v=3$.

The mean is $$ r(h)=E[Z_h]=0.4(1)+0.6(-1/3)=0.4-0.2=0.2. $$ The second moment is $$ E[Z_h^2]=0.4(1)^2+0.6(1/9)=0.4+0.066\overline{6}=0.466\overline{6}. $$ Thus $$ \operatorname{Var}(Z_h)=E[Z_h^2]-E[Z_h]^2 =0.466\overline{6}-(0.2)^2=0.426\overline{6}. $$ The proposed right-hand side is $v r(h)=3(0.2)=0.6$, and $0.426\overline{6}\leq 0.6$, so the condition holds for this candidate. Its centered values are $1-0.2=0.8$ and $-1/3-0.2=-0.533\overline{3}$, so the centered bound holds with $B=0.8$.

These numbers can arise from nonnegative losses: let $h^*$ have constant loss $1/3$, and let $h$ have loss $4/3$ when $Z_h=1$ and loss $0$ when $Z_h=-1/3$. Then the difference of the two losses is exactly $Z_h$. The risks are $R(h^*)=1/3$ and $R(h)=0.4(4/3)=8/15$, whose difference is $8/15-1/3=1/5=0.2$.

The Concentration Inequality Behind the Rate

We first state and derive the one-sided Bernstein inequality in the form used below. Suppose $W_1,\ldots,W_n$ are independent, have mean zero, satisfy $\lvert W_i\rvert\leq B$, and have variances at most $\sigma^2$. Then for every $t>0$,

P\!\left(\frac{1}{n}\sum_{i=1}^n W_i\leq -t\right) \leq \exp\!\left\{-\frac{nt^2}{2(\sigma^2+Bt/3)}\right\}.

Here is a derivation. For $0\leq\lambda<3/B$, expand the exponential. Since $E[W_i]=0$, $\lvert W_i\rvert\leq B$, and $E[W_i^2]\leq\sigma^2$, for every integer $k\geq2$ we have $E[\lvert W_i\rvert^k]\leq B^{k-2}\sigma^2$. Also $k!\geq 2\cdot 3^{k-2}$ for $k\geq2$. Consequently,

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

Independence multiplies these moment-generating-function bounds for the sum. Applying Markov’s inequality to $\exp(-\lambda\sum_i W_i)$, with the same bound valid for $-W_i$, and choosing $\lambda=t/(\sigma^2+Bt/3)$ gives the displayed tail inequality. If $\sigma^2=0$, each centered $W_i$ is zero almost surely, and the inequality holds directly. This proves the form of Bernstein’s inequality we need. $\square$

Worked Example: From the Condition to a Tail Bound

For a fixed candidate, suppose $r(h)=0.2$, $\beta=1$, $v=3$, and $B=0.8$, as in the preceding calculation. The centered excess losses from $n$ observations are independent, each with variance at most $v r(h)=0.6$, and absolute value at most $0.8$. The event that the candidate’s empirical excess risk is nonpositive is $$ P_n Z_h\leq 0 \quad\Longleftrightarrow\quad P_n Z_h-r(h)\leq -0.2. $$ Taking $t=0.2$ and $\sigma^2=0.6$ in Bernstein’s inequality gives $$ P(P_nZ_h\leq 0) \leq \exp\!\left\{-\frac{n(0.2)^2}{2(0.6+0.8(0.2)/3)}\right\} =\exp\!\left\{-\frac{0.04n}{2(0.653\overline{3})}\right\} =\exp\{-(3/98)n\}. $$ The empirical risk is unlikely to make this candidate appear at least as good as $h^*$ once $n$ is moderately large. The next result makes this argument uniform over the finite class.

A Fast Excess-Risk Bound for Finite-Class ERM

Theorem: Let $\mathcal H$ be finite, with $M=\lvert\mathcal H\rvert$, and let $\hat h$ be any empirical risk minimizer over $\mathcal H$. Suppose $h^*\in\mathcal H$ minimizes population risk, the centered excess losses satisfy $\lvert Z_h-E[Z_h]\rvert\leq B$ almost surely, and the Bernstein condition holds with $v>0$ and $\beta\in[0,1]$. For $0<\delta<1$, set $L=\log(M/\delta)$ and $$ s=\left(\frac{4vL}{n}\right)^{1/(2-\beta)}+\frac{4BL}{3n}. $$ Then $$ P\big(r(\hat h)\leq s\big)\geq 1-\delta. $$

Proof. Fix $h\in\mathcal H$. The variables $Z_h(X_i)-r(h)$ are independent and mean zero. Their variance is at most $v r(h)^\beta$, and their absolute values are at most $B$. If $r(h)>0$, Bernstein’s inequality with $t=r(h)$ gives

P(P_nZ_h\leq0) \leq \exp\!\left\{-\frac{n r(h)^2} {2\left(vr(h)^\beta+B r(h)/3\right)}\right\}.

The exponent’s positive fraction is nondecreasing as a function of $r(h)>0$: its reciprocal, apart from the constant factor $2/n$, is $v r(h)^{\beta-2}+B/(3r(h))$, which is nonincreasing because $\beta\leq1$. For $r(h)\geq s$, it follows that the probability above is at most

\exp\!\left\{-\frac{n s^2}{2(vs^\beta+Bs/3)}\right\}.

The definition of $s$ implies $s^{2-\beta}\geq 4vL/n$ and $s\geq 4BL/(3n)$. Therefore $vs^\beta\leq ns^2/(4L)$ and $Bs/3\leq ns^2/(4L)$. Adding these inequalities shows $2(vs^\beta+Bs/3)\leq ns^2/L$, so the last probability is at most $e^{-L}$.

If $r(\hat h)>s$, ERM’s defining property gives $P_n\ell_{\hat h}\leq P_n\ell_{h^*}$, or equivalently $P_nZ_{\hat h}\leq0$. Thus the event $r(\hat h)>s$ is contained in the union, over hypotheses with $r(h)>s$, of the events $P_nZ_h\leq0$. By the union bound its probability is at most $M e^{-L}=M e^{-\log(M/\delta)}=\delta$. Hence $P(r(\hat h)\leq s)\geq1-\delta$, as claimed. $\square$

Worked Example: A Numerical Fast-Rate Bound

Suppose $M=40$, $n=2000$, $\delta=0.05$, $\beta=1$, $v=0.25$, and $B=2$. These constants are assumed to hold uniformly over the class. First, $$ L=\log(40/0.05)=\log(800)\approx6.684612. $$ For $\beta=1$, the theorem’s threshold is $$ s=\frac{4vL}{n}+\frac{4BL}{3n} =\frac{4(0.25)(6.684612)}{2000} +\frac{4(2)(6.684612)}{3(2000)}. $$ The first term is $6.684612/2000\approx0.0033423$. The second is $8(6.684612)/6000\approx0.0089128$. Thus $s\approx0.0122551$, and the theorem gives $$ P\big(r(\hat h)\leq0.0122551\big)\geq0.95. $$ The numerical bound is conservative, as finite-class concentration bounds often are, but it displays the rate: when $\beta=1$, both terms scale as $\log(M/\delta)/n$, rather than as a square root of $1/n$.

What Different Bernstein Exponents Imply

The theorem separates the rate into a variance-driven term and a bounded-increment term. For $0\leq\beta<1$, the first term scales as $(vL/n)^{1/(2-\beta)}$, while the second scales as $BL/n$. For $\beta=0$, the first term has the familiar square-root scale $(vL/n)^{1/2}$. For $\beta=1$, it is $4vL/n$, so the full bound is of order $L/n$. Stronger variance decay as excess risk shrinks is what allows this improvement.

Worked Example: An Intermediate Bernstein Exponent

Take $M=10$, $n=1000$, $\delta=0.1$, $\beta=1/2$, $v=0.5$, and $B=1$. Then $L=\log(10/0.1)=\log(100)\approx4.605170$, and $1/(2-\beta)=2/3$. The two terms in the threshold are $$ \left(\frac{4(0.5)(4.605170)}{1000}\right)^{2/3} =(0.00921034)^{2/3}\approx0.043939, $$ and $$ \frac{4(1)(4.605170)}{3(1000)}\approx0.006140. $$ Consequently $s\approx0.05008$, giving $P(r(\hat h)\leq0.05008)\geq0.9$. In this case the variance-driven term has order $(L/n)^{2/3}$, between the square-root and $1/n$ scales.

Common Pitfall and Practical Meaning

A frequent mistake is to infer a fast rate from small variances of the individual losses alone. The theorem needs a bound on $\operatorname{Var}(\ell_h(X)-\ell_{h^*}(X))$ in terms of the corresponding excess risk, for every candidate. Separate loss variances do not establish that relationship: the difference can fluctuate even when each loss is individually well behaved. The centered boundedness assumption is also separate from the Bernstein condition; it controls large deviations, while the condition controls how variance changes with excess risk.

The bound concerns excess risk, not the distance between $\hat h$ and $h^*$, nor an error in an underlying parameter. A small risk gap need not imply that two hypotheses or parameter values are close without additional assumptions. The result is useful when the prediction or decision target is risk itself and a variance-to-excess-risk condition can be justified. Checking that condition for a particular loss and model is a separate task.

Key takeaway: For finite-class ERM, a Bernstein condition $\operatorname{Var}(Z_h)\leq v r(h)^\beta$ changes the deviation penalty because candidates with small excess risk also have controlled fluctuations. The resulting high-probability threshold is $$ \left(\frac{4v\log(M/\delta)}{n}\right)^{1/(2-\beta)} +\frac{4B\log(M/\delta)}{3n}, $$ which gives an order-$\log(M/\delta)/n$ rate when $\beta=1$.

Check Your Understanding

Answer these questions using the definitions and theorem above.

Why is the Bernstein condition stated for the excess loss $Z_h$, rather than for $\ell_h$ alone?
For $\beta=0$, what is the order in $n$ of the variance-driven term in the theorem?
Which assumptions allow the finite-class union bound in the proof, and where does the factor $M$ enter?
If losses lie in $[0,1]$, what value of $B$ always bounds the centered excess loss?
Does the theorem by itself imply that $\hat h$ is close to $h^*$ in parameter distance? Explain.