Bernstein Conditions And Fast Finite-Class Rates

Why a Variance Condition Changes the Rate

Selecting the empirically best candidate from a finite dictionary requires controlling random differences between empirical and population risks. Without further structure, a candidate's excess loss can fluctuate substantially even when its excess risk is small, leading to a square-root dependence on sample size. A Bernstein condition rules out some of that fluctuation near the oracle: it bounds the second moment of excess loss by a constant times its mean. Concentration can then be sharper precisely for candidates whose risk is close to optimal.

The result concerns hard selection: choose one candidate with the smallest empirical risk. It does not assert that every loss satisfies a Bernstein condition. The condition is an additional property of the candidate losses and the distribution of the data, and its constant matters.

Setup and the Bernstein Condition

Let $Z_1,\ldots,Z_n$ be independent and identically distributed observations with common distribution $P$. Consider a fixed finite dictionary $\mathcal F=\{f_1,\ldots,f_M\}$, where $M\geq 1$. For a measurable loss $\ell_f(Z)$, assume each candidate has finite risk $R(f)=E[\ell_f(Z)]$. Choose an oracle candidate $f^*\in\mathcal F$ minimizing this risk, and define

\Delta_f(Z)=\ell_f(Z)-\ell_{f^*}(Z), \qquad \mu_f=E[\Delta_f(Z)]=R(f)-R(f^*)\geq 0.

The empirical risk is $P_n\ell_f=n^{-1}\sum_{i=1}^n\ell_f(Z_i)$. Let $\hat f$ be any empirical risk minimizer over $\mathcal F$; ties may be resolved by any fixed rule. Since the dictionary is finite, an oracle and an empirical minimizer exist.

Definition: The dictionary satisfies a Bernstein condition relative to $f^*$ with constant $V\geq 0$ if, for every $f\in\mathcal F$, $$ E[\Delta_f(Z)^2]\leq V E[\Delta_f(Z)]=V\mu_f. $$ A bounded-excess-loss condition with constant $b\geq 0$ additionally requires $|\Delta_f(Z)|\leq b$ almost surely for every $f\in\mathcal F$. These are distributional assumptions on the excess losses; neither is automatic for an arbitrary loss and dictionary.

The Bernstein condition is informative near the oracle. If $\mu_f$ is small, it forces the second moment of $\Delta_f$ to be small as well. In particular, if $V=0$, then $E[\Delta_f^2]=0$ for every $f$, so every candidate has zero excess risk. When $b=0$, the boundedness condition itself implies $\Delta_f=0$ almost surely for every candidate.

Worked Example: A Nonnegative Excess Loss

Let $Z\sim\operatorname{Bernoulli}(0.1)$, and consider two candidates with losses $\ell_{f_0}(Z)=0$ and $\ell_{f_1}(Z)=Z$. The oracle is $f^*=f_0$. For $f_1$, the excess loss is $\Delta_{f_1}=Z$, so

\mu_{f_1}=E[Z]=0.1, \qquad E[\Delta_{f_1}^2]=E[Z^2]=E[Z]=0.1.

Thus the Bernstein condition holds with $V=1$, and $|\Delta_{f_1}|\leq 1$, so $b=1$ works. This is a particularly transparent case: excess risk and excess-loss second moment are equal. It shows how the condition can hold even though the excess loss is random.

The Concentration Bound Behind the Fast Rate

We first give the concentration result needed in the selection proof. The boundedness constant below applies to centered variables. The excess-loss application will use $2b$, since centering a variable bounded in absolute value by $b$ can increase its absolute bound.

Lemma: Let $W_1,\ldots,W_n$ be independent, mean-zero random variables satisfying $|W_i|\leq c$ almost surely, with $\operatorname{Var}(W_i)\leq \sigma^2$. For $t>0$, $$ P\left(\frac{1}{n}\sum_{i=1}^n W_i\geq t\right) \leq \exp\left\{-\frac{nt^2}{2(\sigma^2+ct/3)}\right\}. $$ The same bound applies to the lower tail by replacing each $W_i$ with $-W_i$.

Proof. For $0\leq\lambda<3/c$, expand the exponential. Since $E[W_i]=0$, $|W_i|\leq c$, and $k!\geq 2\cdot 3^{k-2}$ for every integer $k\geq 2$,

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

The middle inequality uses $E[|W_i|^k]\leq c^{k-2}E[W_i^2]$ and sums a geometric series. Independence and Markov's inequality therefore give

P\left(\sum_{i=1}^nW_i\geq nt\right) \leq \exp\left\{-\lambda nt+ \frac{n\lambda^2\sigma^2}{2(1-\lambda c/3)}\right\}.

Taking $\lambda=t/(\sigma^2+ct/3)$ (or taking a limit if $\sigma^2=0$) yields the stated exponent. If $\sigma^2=0$, each mean-zero $W_i$ is zero almost surely, so the probability is zero and the inequality holds directly. Applying the same argument to $-W_i$ proves the lower-tail version. $\square$

For a candidate $f$ with $\mu_f>0$, apply the lower-tail inequality to $W_i=\mu_f-\Delta_f(Z_i)$. These variables have mean zero, satisfy $|W_i|\leq 2b$, and have variance $\operatorname{Var}(\Delta_f)\leq E[\Delta_f^2]\leq V\mu_f$. Thus

P(P_n\Delta_f\leq 0) \leq \exp\left\{-\frac{n\mu_f^2}{2(V\mu_f+2b\mu_f/3)}\right\} = \exp\left\{-\frac{n\mu_f}{2(V+2b/3)}\right\}.

Fast Finite-Class Selection Theorem

Theorem: Suppose the dictionary is fixed and finite, the observations are iid, all candidate risks are finite, and the bounded-excess-loss and Bernstein conditions hold relative to an oracle $f^*$. For any $0<\delta<1$, every empirical risk minimizer $\hat f$ satisfies, with probability at least $1-\delta$, $$ R(\hat f)-R(f^*) \leq \frac{2(V+2b/3)\log(M/\delta)}{n}. $$ If $b=0$, the conclusion holds because all candidates have zero excess risk.

Proof. First suppose $b>0$. Set $r=2(V+2b/3)\log(M/\delta)/n$, which is positive. If $R(\hat f)-R(f^*)>r$, then $\hat f$ is one of the candidates with $\mu_f>r$. Because $\hat f$ minimizes empirical risk, $P_n\ell_{\hat f}\leq P_n\ell_{f^*}$, and hence $P_n\Delta_{\hat f}\leq 0$. For any fixed candidate with $\mu_f>r$, the concentration bound gives

P(P_n\Delta_f\leq 0) \leq \exp\left\{-\frac{n\mu_f}{2(V+2b/3)}\right\} \leq \exp\left\{-\frac{nr}{2(V+2b/3)}\right\} =\frac{\delta}{M}.

A union bound over at most $M$ candidates shows that the probability of any such candidate having empirical excess loss at most zero is at most $\delta$. This proves the claim when $b>0$, including the case $V=0$. If $b=0$, then $|\Delta_f|\leq0$ implies $\Delta_f=0$ almost surely for every candidate. Since the dictionary is finite, all candidates have excess risk zero, and the theorem holds directly; no division by a zero denominator is needed. $\square$

For fixed $V$, $b$, and confidence level, the bound scales as $\log(M)/n$, rather than as a square root of $\log(M)/n$. The improvement comes from using a variance bound proportional to the candidate's own excess risk, not from the union bound itself. The union bound still accounts for searching among $M$ candidates.

Worked Example: Signed Excess Loss

Suppose a candidate's excess loss equals $1$ with probability $0.75$ and $-1$ with probability $0.25$. Its mean and second moment are

\mu=0.75(1)+0.25(-1)=0.5, \qquad E[\Delta^2]=0.75(1)^2+0.25(-1)^2=1.

Thus $E[\Delta^2]\leq 2\mu$, so $V=2$ is valid, and $b=1$. With $M=2$, $n=100$, and $\delta=0.05$, the theorem's bound is

\frac{2(2+2/3)\log(2/0.05)}{100} = \frac{16}{3}\frac{\log(40)}{100} \approx \frac{16}{3}\frac{3.689}{100} \approx 0.197.

The candidate's actual excess risk is $0.5$. If an empirical minimizer selects it, its empirical excess loss must be at most zero. The concentration exponent for that event is $100(0.5)/(2(2+2/3))=9.375$, giving probability at most $e^{-9.375}\approx0.000085$. The theorem's uniform guarantee is more conservative, but the calculation displays the mechanism: even signed fluctuations are controlled when their second moment is tied to the mean.

Worked Example: Calculating a Dictionary-Wide Rate

Suppose $M=20$, $n=1000$, $\delta=0.05$, and the assumptions hold with $V=1$ and $b=1$. Then

\log(M/\delta)=\log(20/0.05)=\log(400)\approx5.991, \qquad 2(V+2b/3)=2(1+2/3)=\frac{10}{3}.

The excess-risk bound is therefore

R(\hat f)-R(f^*) \leq \frac{(10/3)(5.991)}{1000} \approx 0.01997

with probability at least $0.95$. For the same fixed $M,V,b,\delta$, doubling the sample size to $2000$ halves this bound to about $0.00999$. This inverse-sample-size behavior is the fast-rate feature; it is conditional on the stated Bernstein and boundedness assumptions.

When the Condition Is Weak, and a Common Pitfall

A small mean excess risk alone does not guarantee a fast rate. For example, let $\Delta$ equal $1$ with probability $(1+\varepsilon)/2$ and $-1$ with probability $(1-\varepsilon)/2$, where $0<\varepsilon<1$. Then

E[\Delta]=\varepsilon, \qquad E[\Delta^2]=1.

For the Bernstein inequality $E[\Delta^2]\leq V E[\Delta]$ to hold, one needs $V\geq1/\varepsilon$. As the mean approaches zero, the required constant diverges. The fast-rate formula then loses its advantage unless the problem supplies a uniform, useful value of $V$. This is why checking the condition is part of the analysis, not a detail that can be skipped.

Common mistake: treating boundedness as the Bernstein condition. A bound $|\Delta_f|\leq b$ alone does not imply $E[\Delta_f^2]\leq V E[\Delta_f]$ with a fixed useful $V$. The signed example shows why: its second moment remains one while its mean can be arbitrarily small.
Common mistake: forgetting the empirical-minimizer event. The proof does not claim every candidate with large risk has a poor empirical risk. It bounds the probability that any such candidate has empirical excess loss at most zero, which is necessary if it is to beat the oracle empirically.
Common mistake: using a zero denominator. If $b=0$, handle the case directly: all excess losses vanish almost surely. For $b>0$, the denominator $2(V+2b/3)$ is positive even when $V=0$.

Key takeaway: A Bernstein condition makes the variance of each candidate's excess loss shrink with its excess risk. Combined with bounded excess losses, this converts concentration for finite-class empirical selection into a high-probability excess-risk rate proportional to $(V+b)\log(M/\delta)/n$, provided the condition holds with constants that remain controlled.

Check Your Understanding

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

Why is the variance of $\Delta_f$ bounded by $V\mu_f$ under the stated Bernstein condition?
Why does centering an excess loss bounded by $b$ lead to the bound $2b$ for the centered variable?
Which event involving $P_n\Delta_f$ must occur if an empirical risk minimizer has excess risk greater than the theorem's threshold?
For $b=0$, explain why the theorem's conclusion holds without applying the concentration inequality.
In the signed example with mean $\varepsilon$ and second moment $1$, what is the smallest possible Bernstein constant $V$?