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:

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.