Bernstein Bounds and Fast Rates

Hoeffding's inequality bounds how far a sample average can be from its true mean using only the range of the data — it doesn't care whether your observations are tightly clustered or wildly spread out within that range, which throws away useful information. Bernstein's inequality fixes this by also using the variance $\sigma^2$ of the underlying random variable, and the payoff is large: when the true variance is small, Bernstein bounds shrink much faster than Hoeffding's as you add data — a "fast rate" instead of the generic "slow rate."

Concretely, for $n$ i.i.d. bounded observations with variance $\sigma^2$ and range bound $b$, Bernstein's inequality gives, with high probability:

$$|\bar{X} - \mu| \leq \sqrt{\frac{2\sigma^2 \log(1/\delta)}{n}} + \frac{2b\log(1/\delta)}{3n} .$$

In plain English: the first term behaves like the usual $1/\sqrt{n}$ shrinkage but scaled by the actual variance instead of the worst-case range, and the second term is a smaller correction that shrinks faster, at rate $1/n$. When $\sigma^2$ is small relative to $b^2$ (low-noise settings, like a classifier that's usually confident and correct), the first term is tiny and the bound tightens dramatically faster than Hoeffding's generic $b\sqrt{\log(1/\delta)/n}$ bound would predict.

This is why learning-theory results for well-separated classification problems or low-noise regression can prove convergence rates faster than the classical $1/\sqrt{n}$ — the "fast rates" literature — by plugging problem-specific variance bounds into a Bernstein-type inequality instead of a range-only one.