Concentration inequalities turn random empirical quantities into deterministic error bars. They are the finite-sample engine behind learning bounds.
Hoeffding inequality
Bounded independent variables concentrate at a sub-Gaussian scale.
Theorem. If \(X_1,\ldots,X_n\) are independent, \(a_i\le X_i\le b_i\), and \(S_n=\sum_i(X_i-\mathbb E X_i)\), then \[ P(S_n\ge t)\le \exp\left\{-\frac{2t^2}{\sum_{i=1}^n(b_i-a_i)^2}\right\}. \]
Proof. For each \(\lambda>0\), Hoeffding's lemma gives \[ \mathbb E e^{\lambda(X_i-\mathbb E X_i)} \le \exp\{\lambda^2(b_i-a_i)^2/8\}. \] Independence multiplies moment generating functions. Chernoff's bound gives \[ P(S_n\ge t)\le \exp\{-\lambda t+\lambda^2\sum_i(b_i-a_i)^2/8\}. \] Optimizing over \(\lambda\) yields the displayed bound.
Bernstein inequality
Variance-sensitive inequalities improve Hoeffding when the variance is small.
Theorem. If \(X_i\) are independent, centered, \(|X_i|\le B\), and \(\sum_i\mathbb E X_i^2\le v\), then \[ P\left(\sum_iX_i\ge t\right) \le \exp\left\{-\frac{t^2}{2(v+Bt/3)}\right\}. \]
Proof. The exponential-moment estimate \[ \log\mathbb E e^{\lambda X_i}\le \frac{\lambda^2\mathbb E X_i^2}{2(1-\lambda B/3)} \] holds for \(0<\lambda<3/B\). Summing over \(i\), applying Chernoff's method, and optimizing \(\lambda=t/(v+Bt/3)\) gives the inequality.
Bounded differences
Many learning statistics are not simple sums, but they are stable under replacing one observation.
Theorem. Let \(F(Z_1,\ldots,Z_n)\) satisfy \[ \sup_{z_1,\ldots,z_n,z_i'}|F(z_1,\ldots,z_i,\ldots,z_n)-F(z_1,\ldots,z_i',\ldots,z_n)|\le c_i. \] Then \[ P(F-\mathbb EF\ge t)\le \exp\left\{-\frac{2t^2}{\sum_i c_i^2}\right\}. \]
Proof. Let \(M_i=\mathbb E(F\mid Z_1,\ldots,Z_i)\). The martingale increments satisfy \(|M_i-M_{i-1}|\le c_i\). Applying Azuma-Hoeffding to this Doob martingale gives the displayed inequality.
From fixed functions to classes
A fixed-function concentration bound becomes a learning bound only after controlling the size of the class.
Proposition. If a tail bound \(P(|P_ng-Pg|>t)\le a(t)\) holds for every \(g\in\mathcal G\), and \(\mathcal G\) is finite, then \[ P\left(\sup_{g\in\mathcal G}|P_ng-Pg|>t\right)\le |\mathcal G|a(t). \]
Proof. The event that the supremum exceeds \(t\) is contained in the union of the events \(\{|P_ng-Pg|>t\}\) over \(g\in\mathcal G\). Apply the union bound.
Sub-Gaussian and sub-exponential variables
Definition. A centered random variable \(X\) is sub-Gaussian with variance proxy \(\sigma^2\) if \[ \mathbb E e^{\lambda X}\le e^{\sigma^2\lambda^2/2} \quad\text{for every }\lambda\in\mathbb R. \] It is sub-exponential with parameters \((\nu^2,b)\) if the same inequality holds for \(|\lambda|<1/b\), with \(\sigma^2\) replaced by \(\nu^2\).
Proposition. If independent centered \(X_i\) are sub-Gaussian with proxies \(\sigma_i^2\), then \[ P\!\left(\left|\sum_{i=1}^nX_i\right|\ge t\right) \le2\exp\!\left(-\frac{t^2}{2\sum_i\sigma_i^2}\right). \] If they are sub-exponential with common scale bound \(b\) and total variance proxy \(\nu^2=\sum_i\nu_i^2\), then \[ P\!\left(\left|\sum_iX_i\right|\ge t\right) \le2\exp\!\left[-\frac12\min\!\left\{\frac{t^2}{\nu^2},\frac{t}{b}\right\}\right]. \]
Proof. Independence multiplies moment generating functions. Chernoff's inequality then gives \(\exp(-\lambda t+\lambda^2\sum_i\sigma_i^2/2)\); optimizing over unrestricted \(\lambda\) proves the sub-Gaussian claim. In the sub-exponential case the unconstrained optimum is valid only when \(t/\nu^2<1/b\). Otherwise take \(\lambda\) of order \(1/b\), producing the linear tail regime.
Orlicz norms and moment growth
Definition. For \(\alpha\ge1\), define \[ \|X\|_{\psi_\alpha} =\inf\{c>0:\mathbb E\exp(|X|^\alpha/c^\alpha)\le2\}. \] Finite \(\psi_2\)-norm is equivalent, up to universal constants, to sub-Gaussian tails; finite \(\psi_1\)-norm is equivalent to sub-exponential tails.
Proposition. The following are equivalent up to universal constants: \[ P(|X|>t)\le2e^{-t^2/K^2},\qquad (\mathbb E|X|^p)^{1/p}\le CK\sqrt p,\qquad \|X\|_{\psi_2}\le C'K. \]
Proof outline. Tail integration, \(\mathbb E|X|^p=p\int_0^\infty t^{p-1}P(|X|>t)\,\mathrm{d}t\), turns the Gaussian tail into a Gamma integral of order \(K^p p^{p/2}\). Moment growth implies exponential integrability by expanding \(\mathbb E\exp(X^2/c^2)\) into a power series. Markov's inequality applied to the exponential moment recovers the tail bound.
Variance-adaptive empirical means
Corollary. If \(0\le X_i\le1\), \(\mu=\mathbb EX_i\), and \(\widehat\mu=n^{-1}\sum_iX_i\), then with probability at least \(1-\delta\), \[ |\widehat\mu-\mu| \le \sqrt{\frac{2\operatorname{Var}(X_1)\log(2/\delta)}{n}} +\frac{2\log(2/\delta)}{3n}. \]
Proof. Apply Bernstein's inequality to \(X_i-\mu\) in both directions, set the exponent equal to \(\log(2/\delta)\), and use the elementary implication \(t^2/\{2(v+t/3)\}\ge u\) whenever \(t\ge\sqrt{2vu}+2u/3\).
Efron-Stein variance control
Theorem. Let \(Z_1',\ldots,Z_n'\) be an independent copy of \(Z_1,\ldots,Z_n\), and let \(F_i'=F(Z_1,\ldots,Z_{i-1},Z_i',Z_{i+1},\ldots,Z_n)\). Then \[ \operatorname{Var}(F)\le\frac12\sum_{i=1}^n \mathbb E(F-F_i')^2. \]
Proof. Let \(M_i=\mathbb E(F\mid Z_1,\ldots,Z_i)\). Orthogonality of martingale differences gives \(\operatorname{Var}(F)=\sum_i\mathbb E(M_i-M_{i-1})^2\). Conditional Jensen's inequality bounds the \(i\)th term by \(\tfrac12\mathbb E(F-F_i')^2\). Summation completes the proof.
Self-normalized concentration
Theorem. Let \((X_t,\mathcal F_t)\) be a martingale-difference sequence that is conditionally \(R\)-sub-Gaussian, and let \(v_t\in\mathbb R^d\) be \(\mathcal F_{t-1}\)-measurable. Put \[ S_t=\sum_{s=1}^t v_sX_s,\qquad V_t=\lambda I+\sum_{s=1}^t v_sv_s^\top. \] Then, with probability at least \(1-\delta\), simultaneously for all \(t\), \[ \|S_t\|_{V_t^{-1}}^2 \le 2R^2\log\!\left( \frac{\det(V_t)^{1/2}}{\det(\lambda I)^{1/2}\delta} \right). \]
Proof outline. For fixed \(\theta\), conditional sub-Gaussianity makes \[ \exp\!\left\{\theta^\top S_t-\frac{R^2}{2} \theta^\top(V_t-\lambda I)\theta\right\} \] a nonnegative supermartingale. Mix this process over a centered Gaussian distribution for \(\theta\), evaluate the Gaussian integral by completing the square, and apply Ville's inequality. The determinant is the normalization constant of the mixed Gaussian process.
This self-normalized form is the basic confidence-ellipsoid tool for linear bandits and adaptive least squares. Ordinary iid concentration is insufficient there because the design vectors depend on past observations.
Matrix Bernstein inequality
Theorem. Let \(X_1,\ldots,X_n\) be independent, centered, self-adjoint \(d\times d\) random matrices with \(\|X_i\|_{\mathrm{op}}\le L\) almost surely. Set \(v=\|\sum_i\mathbb EX_i^2\|_{\mathrm{op}}\). Then \[ P\!\left(\left\|\sum_iX_i\right\|_{\mathrm{op}}\ge t\right) \le2d\exp\!\left\{-\frac{t^2}{2(v+Lt/3)}\right\}. \]
Proof outline. The scalar exponential-moment argument is replaced by the trace Laplace transform: \(P(\lambda_{\max}(S)\ge t)\le e^{-\theta t}\mathbb E\operatorname{tr}e^{\theta S}\). Lieb's concavity theorem and the matrix mgf bound control this trace by \(d\exp\{v\theta^2/[2(1-L\theta/3)]\}\). Optimization gives the upper-tail bound; apply the same argument to \(-S\) for the lower tail.
Example. For isotropic sub-Gaussian vectors \(X_i\in\mathbb R^d\), matrix concentration applied to \(X_iX_i^\top-I\), after truncation or a sub-exponential refinement, yields \[ \left\|\frac1n\sum_{i=1}^nX_iX_i^\top-I\right\|_{\mathrm{op}} =O_P\!\left(\sqrt{\frac dn}+\frac dn\right). \] This controls empirical curvature in linear regression and generalized linear models.
Concentration controls fluctuations for a fixed object or a finite net. The pages on Rademacher complexity and metric entropy explain how to pass from such nets to infinite function classes.