the general Hoeffding inequality for sub-Gaussians
/ HUF-ding /
The general Hoeffding inequality lifts the classical bounded-variable Hoeffding bound (Vol I) to the entire sub-Gaussian class. In a first course Hoeffding's inequality says: a sum of independent variables each confined to an interval [a_i, b_i] deviates from its mean by t with probability at most exp(-2t^2 / sum (b_i - a_i)^2). The general version replaces 'bounded' by 'sub-Gaussian', which is the right level of generality because the proof never used boundedness for anything except to produce a variance proxy.
The statement: if X_1, ..., X_n are independent, centered, and sub-Gaussian with variance proxies sigma_1^2, ..., sigma_n^2 (equivalently psi_2 norms K_i), then for every t > 0, P(sum_i X_i >= t) <= exp(-t^2 / (2 sum_i sigma_i^2)), and the two-sided version carries a factor 2. The proof is the same three steps as in Vol I but with the class doing the work: Chernoff (Markov on the exponential, P(sum >= t) <= e^(-lambda t) E[exp(lambda sum)]); independence (the MGF factorizes, E[exp(lambda sum)] = product E[exp(lambda X_i)]); the sub-Gaussian definition (each factor <= exp(sigma_i^2 lambda^2 / 2), so the product is <= exp(lambda^2 sum sigma_i^2 / 2)); and then optimize over lambda by choosing lambda = t / sum sigma_i^2. In Orlicz-norm form there is an equivalent statement P(|sum a_i X_i| >= t) <= 2 exp(-c t^2 / (||X||_psi2^2 sum a_i^2)) for weighted sums, which is the form used in random-projection and high-dimensional arguments.
This single bound is the foundation of almost every concentration estimate in machine learning theory: it gives the deviation of empirical averages, the accuracy of Monte Carlo, the error of a Rademacher random projection, and the building block for union bounds over finitely many events. Its limitation, and the reason Bernstein and Bennett exist, is that it depends only on the variance PROXY, not the true variance. When the variables are bounded but have small variance, the proxy (b-a)^2/4 is pessimistic and Hoeffding leaves a Gaussian-versus-Poisson gap on the table; for that small-variance, large-range regime one must use a variance-aware inequality.
Estimate the mean mu of a sub-Gaussian variable with proxy sigma^2 from n iid samples. With X_i - mu having proxy sigma^2, the sum (1/n) sum (X_i - mu) has proxy sigma^2/n, so P(|empirical mean - mu| >= t) <= 2 exp(-n t^2 / (2 sigma^2)). To get error t with confidence 1 - delta you need n >= 2 sigma^2 log(2/delta) / t^2 samples.
Sample size scales like sigma^2 log(1/delta) / t^2 — the basic learning-theory rate.
Hoeffding ignores the true variance and uses only the proxy, so for bounded variables with small variance it is loose by the Gaussian/Bernstein factor. It also needs independence; for dependent sums use Azuma/McDiarmid instead.