Empirical Bernstein Bounds from Sample Variance

Why Use the Sample Variance?

A concentration bound for a bounded sample mean can use only the range of the observations, or it can also use information about their variability. Bernstein’s inequality uses the population variance, which is usually unknown. An empirical Bernstein bound replaces that unknown quantity with the sample variance, plus a correction that accounts for the uncertainty in estimating variance.

This replacement is useful when the observations vary little compared with their full possible range. It is not a license to treat the observed variance as the true variance: the correction is essential, especially for small samples or samples that happen to be unusually uniform.

Definition: Let $X_1,\ldots,X_n$ be iid observations with $X_i\in[a,b]$ almost surely, where $a<b$, and write $R=b-a$, $\mu=E[X_i]$, and $\bar X=n^{-1}\sum_{i=1}^n X_i$. Define the empirical variance with divisor $n$ by $$ \hat V_n=\frac{1}{n}\sum_{i=1}^n(X_i-\bar X)^2. $$ The divisor matters: this tutorial’s bound is written using $\hat V_n$, not the unbiased sample variance with divisor $n-1$.

It is convenient to rescale to $Z_i=(X_i-a)/R\in[0,1]$. Let $\bar Z=n^{-1}\sum_i Z_i$, and let $\hat v_n=n^{-1}\sum_i(Z_i-\bar Z)^2$. Then $\bar X=a+R\bar Z$ and $\hat V_n=R^2\hat v_n$. We first establish an upper bound on the population variance of $Z_i$.

Estimating the Variance from the Data

Write $m=E[Z_i]$, $q=E[Z_i^2]$, and $\sigma^2=\operatorname{Var}(Z_i)=q-m^2$. The empirical variance has the matching identity $\hat v_n=\overline{Z^2}-\bar Z^2$, where $\overline{Z^2}=n^{-1}\sum_i Z_i^2$. Both $Z_i$ and $Z_i^2$ lie in $[0,1]$, so Hoeffding’s inequality controls the errors in their sample averages.

Lemma: For any $\eta\in(0,1)$, with probability at least $1-2\eta$, $$ \sigma^2\leq \hat v_n+3\sqrt{\frac{\log(2/\eta)}{2n}}. $$

The correction in this lemma is not a claim that the population variance is close to the observed variance in every sample. Rather, it is a one-sided confidence allowance: with the stated probability, the observed variance plus the correction is large enough to cover the population variance.

Control the second moment.
Hoeffding’s inequality gives $P(|\overline{Z^2}-q|>t)\leq 2e^{-2nt^2}$, because $Z_i^2\in[0,1]$.

Control the mean.
The same inequality gives $P(|\bar Z-m|>t)\leq 2e^{-2nt^2}$, because $Z_i\in[0,1]$.

Combine the events.
Set $t=\sqrt{\log(2/\eta)/(2n)}$. Each deviation probability is at most $\eta$, so the union bound says both deviations are at most $t$ with probability at least $1-2\eta$.

On that joint event, since $\bar Z,m\in[0,1]$, $$ \sigma^2-\hat v_n=(q-\overline{Z^2})+(\bar Z^2-m^2) \leq t+|\bar Z-m|\,|\bar Z+m| \leq t+2t=3t. $$ This proves the lemma. The argument requires no independence between $\overline{Z^2}$ and $\bar Z$; the union bound combines their separate guarantees. $\square$

The Empirical Bernstein Confidence Bound

We use the one-sided Bernstein inequality for iid variables $Z_i\in[0,1]$: for $x>0$, if $m=E[Z_i]$ and $\sigma^2=\operatorname{Var}(Z_i)$, then $$ P\left(\bar Z-m>\sqrt{\frac{2\sigma^2 x}{n}}+\frac{x}{3n}\right)\leq e^{-x}. $$ This is the bounded-variable Bernstein inequality. Its range term uses $Z_i-m\leq1$; Bernstein bounds for fixed predictors were treated earlier in the course.

Theorem: Suppose $X_1,\ldots,X_n$ are iid and $X_i\in[a,b]$ almost surely. Choose $\alpha,\eta\in(0,1)$. With probability at least $1-\alpha-2\eta$, $$ E[X_i]\leq \bar X+ R\left[ \sqrt{\frac{2\left(\hat v_n+3\sqrt{\frac{\log(2/\eta)}{2n}}\right)\log(1/\alpha)}{n}} +\frac{\log(1/\alpha)}{3n} \right], $$ where $R=b-a$ and $\hat v_n=n^{-1}\sum_{i=1}^n(Z_i-\bar Z)^2$ for $Z_i=(X_i-a)/R$.

To prove the theorem, apply the variance lemma with failure probability $2\eta$, and apply Bernstein’s inequality with $x=\log(1/\alpha)$, so its failure probability is at most $\alpha$. By the union bound, both statements hold with probability at least $1-\alpha-2\eta$. On that event, substitute the variance upper bound from the lemma into Bernstein’s mean bound. The square root is increasing in the variance, so this substitution preserves the inequality. Finally, multiply the resulting bound for $E[Z_i]$ by $R$ and add $a$, using $X_i=a+RZ_i$. This gives the displayed result. $\square$

The theorem is an upper confidence bound for the mean. Applying the same result to $-X_i$ gives a lower confidence bound. Notice that the variance-estimation failures and the mean-deviation failure all count toward the total error probability; choosing $\alpha=\eta$ does not give total error $\alpha$, but $3\alpha$.

Worked Calculations

Worked Example: Rescaling a Bounded Risk

Suppose losses lie in $[2,5]$. In a sample of $n=1{,}000$, the normalized observations $Z_i=(X_i-2)/3$ have $\bar Z=0.52$ and empirical variance $\hat v_n=0.04$. Choose $\alpha=\eta=0.01$. The theorem’s total failure probability is $0.01+2(0.01)=0.03$, so the confidence level is at least $0.97$.

First, the variance correction is $$ 3\sqrt{\frac{\log(200)}{2(1{,}000)}}= 3\sqrt{\frac{5.298317}{2{,}000}} \approx 0.15441. $$ Thus the variance used in the mean bound is at most $0.04+0.15441=0.19441$. The normalized upper limit is $$ 0.52+\sqrt{\frac{2(0.19441)(4.605170)}{1{,}000}}+\frac{4.605170}{3{,}000} \approx 0.56385. $$ Since $X_i=2+3Z_i$, the upper limit on the original mean is $2+3(0.56385)\approx 3.69155$. With probability at least $0.97$, the population mean loss is no larger than this value.

Worked Example: Zero Observed Variance Is Not Zero Population Variance

Let $Z_i\in[0,1]$, and suppose $n=100$, $\bar Z=0.40$, and $\hat v_n=0$. Choose $\eta=0.01$ and $\alpha=0.05$, giving total failure probability $0.02+0.05=0.07$. The variance correction is $$ 3\sqrt{\frac{\log(200)}{2(100)}}= 3\sqrt{\frac{5.298317}{200}}\approx 0.48829. $$ The sample itself has zero empirical variance, but the theorem only bounds the population variance above by $0.48829$ on its variance event.

For the mean bound, $\log(1/\alpha)=\log(20)\approx2.995732$, so $$ 0.40+\sqrt{\frac{2(0.48829)(2.995732)}{100}}+\frac{2.995732}{300} \approx 0.58103. $$ The one-sided upper limit is approximately $0.5810$, with confidence at least $0.93$. A small or constant-looking sample should not be mistaken for proof that the population has no variation.

Worked Example: A Large Sample with Modest Variation

Consider $n=10{,}000$ normalized observations: 5,000 are $0.4$ and 5,000 are $0.6$. Their mean is $\bar Z=(5{,}000(0.4)+5{,}000(0.6))/10{,}000=0.5$. Their empirical variance is $$ \hat v_n=\frac{5{,}000(0.1)^2+5{,}000(0.1)^2}{10{,}000}=0.01. $$ Choose $\eta=0.01$ and $\alpha=0.05$, again giving confidence at least $0.93$. The variance correction is $$ 3\sqrt{\frac{\log(200)}{20{,}000}}\approx 0.04883, $$ so a conservative rounded-up variance upper bound is $0.05884$. The mean limit is $$ 0.5+\sqrt{\frac{2(0.05884)(2.995732)}{10{,}000}}+\frac{2.995732}{30{,}000} \approx 0.50604. $$ The sample’s empirical variance is appreciably below the maximum possible variance for data in $[0,1]$. The bound reflects that, while still allowing for estimation uncertainty.

Interpretation and Common Pitfalls

The empirical Bernstein bound combines two sources of uncertainty. The square-root term reflects the estimated spread of the observations, while the variance correction protects against underestimating that spread from the sample. Both terms depend on the sample size and the chosen confidence levels. When the sample is small, the variance correction can be large enough to make the bound uninformative; that is a feature of the guarantee, not an algebraic defect.

Ignoring the variance correction. Replacing the population variance directly by $\hat v_n$ is not justified by the theorem. A sample can have unusually small variance by chance.
Dropping the range scale. The formula is applied to $Z_i=(X_i-a)/(b-a)$. Returning to the original units requires multiplying the deviation terms by $R=b-a$.
Using the wrong divisor without adjustment. Here $\hat v_n$ has divisor $n$. If the reported sample variance is $S^2=(n-1)^{-1}\sum_i(X_i-\bar X)^2$ in the original units, then the normalized variance in the theorem is $(n-1)S^2/(nR^2)$.
Miscounting confidence error. The variance lemma uses two deviation events, each with error at most $\eta$, and the mean inequality contributes another error $\alpha$. The total failure probability is therefore at most $\alpha+2\eta$.

Key takeaway: A sample variance can sharpen a bounded-mean confidence bound, but only after adding a finite-sample correction for variance estimation and accounting for every failure probability used in the argument.

Check Your Understanding

Use the definitions and confidence accounting above to answer these questions.

Why does the variance lemma control both $\overline{Z^2}$ and $\bar Z$, rather than only the sample mean?
For $\alpha=0.02$ and $\eta=0.01$, what lower bound on the theorem’s confidence level is guaranteed?
What is the relationship between $\hat v_n$ and the unbiased sample variance when observations are normalized to $[0,1]$?
Why is it invalid to set the population variance equal to zero merely because the observed empirical variance is zero?
If the observations lie in $[a,b]$, what factor converts a deviation bound for the normalized mean back to the original units?