Central Limit Theorem

If $X_1, X_2, \ldots$ are iid with mean $\mu$ and variance $\sigma^2 \in (0, \infty)$, then

$\frac{\sqrt{n}(\bar{X}_n - \mu)}{\sigma} \xrightarrow{d} \mathcal{N}(0, 1).$

Equivalently, $\sqrt{n}(\bar{X}_n - \mu) \xrightarrow{d} \mathcal{N}(0, \sigma^2)$, and at the working level $\bar{X}_n \approx \mathcal{N}(\mu, \sigma^2/n)$ for large $n$.

Each $X_i$ contributes a random kick to the sum. For large $n$ the aggregate of many small independent kicks is Gaussian, and the only properties of the kicks that survive the limit are the mean and the variance. The $\sqrt{n}$ scaling is the right zoom: the sum $\sum X_i$ grows as $n\mu$, the standard deviation grows as $\sigma\sqrt{n}$, and standardizing leaves a quantity of order $1$ whose distribution converges.

The classical CLT is the single most-used theorem in applied statistics. Every Wald confidence interval, $z$-test, and plug-in standard error invokes it. In ML theory it is the asymptotic half of every generalization argument that uses a normal approximation in place of a tail bound, and it is the result behind the $1/\sqrt{n}$ baseline rate that concentration inequalities try to match non-asymptotically.

Three failure modes worth naming. (1) Infinite variance: stable distributions with index $\alpha < 2$ (Cauchy, fat-tailed financial returns) have $S_n/n^{1/\alpha}$ converging to a non-Gaussian stable limit, not a Gaussian. (2) Strong dependence: long-range-dependent processes can have CLT-like statements with non-Gaussian limits or non-$\sqrt{n}$ rates. (3) High dimension: the iid CLT is one-dimensional; operator-norm CLTs for sample covariances in dimensions $d \asymp n$ require additional structure and the limits are not Gaussian.

Let $\{X_{n,i}\}$ be a triangular array of independent random variables in row $n$, with $\mathbb{E}[X_{n,i}] = 0$ and $\sigma_{n,i}^2 = \mathrm{Var}(X_{n,i}) < \infty$. Set $s_n^2 = \sum_{i=1}^{k_n} \sigma_{n,i}^2$. The Lindeberg condition is

$L_n(\epsilon) := \frac{1}{s_n^2} \sum_{i=1}^{k_n} \mathbb{E}\!\left[X_{n,i}^2 \, \mathbf{1}\{|X_{n,i}| > \epsilon\, s_n\}\right] \to 0 \quad \text{for every } \epsilon > 0.$

If $L_n(\epsilon) \to 0$ for every $\epsilon > 0$, then

$\frac{1}{s_n} \sum_{i=1}^{k_n} X_{n,i} \xrightarrow{d} \mathcal{N}(0, 1).$

The condition is essentially necessary: under the uniform asymptotic negligibility condition $\max_i \sigma_{n,i}^2 / s_n^2 \to 0$, the Lindeberg condition is equivalent to the CLT plus uniform negligibility.

$L_n(\epsilon)$ is the fraction of the total variance carried by the "big" parts of summands (the parts above $\epsilon\,s_n$ in absolute value). Lindeberg says: at every threshold $\epsilon$, the big parts contribute a vanishing share of the variance. No single summand, and no constant fraction of summands, is allowed to dominate.

The Lindeberg condition is harder to verify directly than the simpler Lyapunov condition: there exists $\delta > 0$ such that

$\frac{1}{s_n^{2+\delta}} \sum_{i=1}^{k_n} \mathbb{E}\!\left[|X_{n,i}|^{2+\delta}\right] \to 0.$

Lyapunov implies Lindeberg by Markov's inequality, and is the form most often used in applied work because $(2+\delta)$-th moments are easier to bound than truncated second moments.

This is the right form of the CLT for theory. Whenever you read "by the CLT" in a learning-theory or asymptotic-statistics paper that does not have iid data, the unstated assumption is almost always Lindeberg or Lyapunov on a triangular array. Specific places it shows up:

• OLS asymptotics with non-random covariates: the score sum $\sum_i x_i \epsilon_i$ is independent but not identically distributed. Lyapunov on $|\epsilon_i|^{2+\delta}$ plus a balanced design ($\max_i \|x_i\|^2 / \sum_i \|x_i\|^2 \to 0$) gives asymptotic normality of $\hat\beta$.
• Influence-function-based asymptotics: in semiparametric efficiency theory, estimators are linearized as sample averages of an influence function, but with finite-sample plug-in errors that make the summands non-iid. Lindeberg controls the error term.
• Non-iid generalization analyses: when training data come from heterogeneous sources or active-learning streams, Lindeberg-style conditions are what permit Gaussian limits of empirical risks.

The Lindeberg condition fails when one or a few summands carry a non-vanishing share of the variance. Canonical example: $X_{n,n} = n$ with probability $1/n^2$ and $0$ otherwise, with $X_{n,i}$ tiny for $i < n$, makes $\sigma_{n,n}^2 = 1$ a constant fraction of $s_n^2$. The sum does not converge to a Gaussian.

A subtle case: with $X_{n,i} = \pm c$ each with probability $1/2$ for fixed constant $c$, the Lindeberg condition holds, but with $X_{n,1} = \pm \sqrt{n}$ and $X_{n,i}$ tiny for $i \geq 2$, the variance budget is dominated by a single Bernoulli-like term. The standardized sum stays approximately $\pm 1$ with probability $1/2$ each, not Gaussian.

If $X_1, \ldots, X_n$ are iid with $\mathbb{E}[X_i] = 0$, $\mathrm{Var}(X_i) = \sigma^2$, and $\mathbb{E}[|X_i|^3] = \rho < \infty$, then

$\sup_t \left| \Pr\!\left[\frac{\bar{X}_n}{\sigma/\sqrt{n}} \leq t\right] - \Phi(t) \right| \leq \frac{C\,\rho}{\sigma^3 \sqrt{n}},$

where $\Phi$ is the standard-normal CDF and $C$ is a universal constant. The best known constant is $C \leq 0.4748$ (Shevtsova, 2011); a lower bound of $C \geq 0.4097$ (Esseen, 1956) shows the optimal $C$ lies in this narrow range.

The CLT rate of convergence is $O(1/\sqrt{n})$, with the constant set by the third absolute moment of the centered summand.

The bound has two factors. $1/\sqrt{n}$ is the universal rate. The non-Gaussianity factor $\rho/\sigma^3$ measures how skewed and heavy-tailed the centered $X$ is, relative to a Gaussian baseline. A $\mathcal{N}(0,1)$ has $\rho = \mathbb{E}|Z|^3 = \sqrt{8/\pi} \approx 1.595$ and $\sigma^3 = 1$, so the ratio is $\approx 1.6$. Heavier tails or larger skewness make the constant blow up and you need more samples before the Gaussian approximation lands.

Berry-Esseen tells you when the CLT approximation is good enough to trust. For Bernoulli$(1/2)$: $\rho = 1/8$, $\sigma^3 = 1/8$, so $\rho/\sigma^3 = 1$ and the bound is $0.4748/\sqrt{n}$. At $n=100$ the worst-case CDF error is $\leq 0.0475$; at $n=10\,000$ it is $\leq 0.00475$.

Practical consequence: for CLT-based confidence intervals to be reliable to within $1\%$ uniformly across the CDF, you need $n \sim 10^4$ in the worst case. This is the back-of-envelope number behind why CLT-based critical values are usually fine for $n \geq 100$ for symmetric data and require $n \geq 1000$ for skewed data.

In ML theory, Berry-Esseen is the right reference point when comparing CLT-based confidence intervals against concentration inequalities. For sub-Gaussian data, Hoeffding gives a non-asymptotic Gaussian-type tail at every $n$; Berry-Esseen is what tells you the asymptotic statement is accurate to $O(1/\sqrt{n})$, which can be stronger or weaker than Hoeffding's constant depending on the regime.

Berry-Esseen requires a finite third moment. Without it the rate can be slower than $1/\sqrt{n}$; under finite $(2+\delta)$-th moments only, the rate is $1/n^{\delta/2}$. The bound is uniform over $t$, so it controls the central CDF well but is loose deep in the tails: at $t$ where $\Phi(t)$ itself is exponentially small, the relative error of the Gaussian approximation can be much larger than the absolute Berry-Esseen budget suggests. Edgeworth expansions give sharper rates inside the bulk and the Cramér large-deviation regime gives sharper tail rates under exponential-moment conditions.

If $X_1, \ldots, X_n \in \mathbb{R}^d$ are iid with mean $\mu$ and covariance matrix $\Sigma$, then

$\sqrt{n}(\bar{X}_n - \mu) \xrightarrow{d} \mathcal{N}_d(0, \Sigma).$

The full covariance structure is preserved in the limit: the joint distribution of the standardized sample-mean vector converges to a multivariate Gaussian with the same covariance as a single $X_i$.

The Cramér-Wold device reduces multivariate weak convergence to all one-dimensional projections. For every $a \in \mathbb{R}^d$, the projected sample $a^\top X_i$ is a one-dimensional iid sequence with variance $a^\top \Sigma a$, and the classical CLT gives $a^\top \sqrt{n}(\bar X_n - \mu) \xrightarrow{d} \mathcal{N}(0, a^\top \Sigma a)$. Since this characterizes a multivariate Gaussian uniquely, the joint limit is $\mathcal{N}_d(0, \Sigma)$.

Multivariate CLT is the workhorse for vector-valued estimators. The MLE in a $d$-dimensional regular parametric family is asymptotically $\mathcal{N}_d(\theta_0, I(\theta_0)^{-1}/n)$, which comes from the multivariate CLT applied to the $d$-vector score $\nabla_\theta \log p(X; \theta_0)$. OLS asymptotic normality, GMM asymptotics, and the joint distribution of estimated regression coefficients all follow the same template: write the estimator as a sum of iid random vectors plus negligible remainder, then apply the multivariate CLT.

The covariance $\Sigma$ matters: scalar tests of single coefficients use the diagonal entries, joint tests (chi-squared statistics, F-tests) use the inverse of $\Sigma$ to whiten the vector. Misreporting $\Sigma$ by ignoring off-diagonal correlations is the most common practical error in multivariate inference.

Singular $\Sigma$ collapses the limit to a degenerate Gaussian on a lower-dimensional subspace. The marginal CLT still holds in each direction, but inverting $\Sigma$ in a Wald or Mahalanobis statistic requires care. In high dimensions ($d$ growing with $n$), the multivariate CLT in operator norm fails outright: the sample covariance $\hat\Sigma_n$ has eigenvalues that do not converge to those of $\Sigma$ unless $d/n \to 0$. The Marchenko-Pastur law replaces the multivariate CLT in the regime $d/n \to c \in (0, \infty)$.

Let $T_n \in \mathbb{R}^k$ satisfy $\sqrt{n}(T_n - \mu) \xrightarrow{d} \mathcal{N}_k(0, \Sigma)$, and let $g : \mathbb{R}^k \to \mathbb{R}^m$ be differentiable at $\mu$ with Jacobian $G(\mu) = \nabla g(\mu) \in \mathbb{R}^{m \times k}$. Then

$\sqrt{n}(g(T_n) - g(\mu)) \xrightarrow{d} \mathcal{N}_m\!\left(0, G(\mu)\, \Sigma\, G(\mu)^\top\right).$

In the scalar case $g'(\mu) \neq 0$ and the asymptotic variance is $[g'(\mu)]^2 \sigma^2$. When $g'(\mu) = 0$ the second-order delta method gives $n(g(T_n) - g(\mu)) \xrightarrow{d} \tfrac{1}{2} g''(\mu) \sigma^2 \chi^2_1$.

A first-order Taylor expansion of $g$ at $\mu$ gives $g(T_n) - g(\mu) = G(\mu)(T_n - \mu) + R_n$ with the remainder $R_n = o_p(|T_n - \mu|) = o_p(1/\sqrt{n})$. Multiplying by $\sqrt{n}$ gives $\sqrt{n}(g(T_n) - g(\mu)) = G(\mu) \sqrt{n}(T_n - \mu) + o_p(1)$, and the lead term pushes the Gaussian forward by the linear map $G(\mu)$.

The delta method is how every asymptotic standard error in applied statistics is computed beyond simple sample means.

• Asymptotic variance of $\log \hat p$ for $\hat p = \bar X_n$, $X_i \sim \mathrm{Bern}(p)$: $g(p) = \log p$, $g'(p) = 1/p$, asymptotic variance $(1/p)^2 \cdot p(1-p) = (1-p)/p$.
• Variance of the log-odds $\log(\hat p/(1-\hat p))$: $g'(p) = 1/(p(1-p))$, asymptotic variance $1/(p(1-p))$. This is the basis of logit-scale Wald intervals, which often have better coverage than untransformed Wald intervals.
• Variance of a ratio $\hat\mu_1/\hat\mu_2$: standard delta-method exercise giving the variance of the ratio in terms of variances and covariance of the components.
• Sandwich variance for misspecified MLE: the delta method through the score-equation expansion produces the $V^{-1} A V^{-\top}$ sandwich form, with $V$ the expected score derivative and $A$ the score covariance.

Three failure modes. (1) $g'(\mu) = 0$: use the second-order delta method, in which the rate jumps from $\sqrt{n}$ to $n$ and the limit is $\chi^2_1$, not normal. (2) $g$ not differentiable at $\mu$: e.g. $g(x) = |x|$ at $\mu = 0$ gives a folded-normal limit. (3) $T_n$ converges at a rate other than $\sqrt{n}$ (e.g. extreme-value problems with rate $n$): the delta method must use the actual rate, not $\sqrt{n}$.

Let $\{X_t\}_{t=1}^n$ be a martingale difference sequence with respect to a filtration $\{\mathcal{F}_t\}$, meaning $\mathbb{E}[X_t \mid \mathcal{F}_{t-1}] = 0$ and $\mathbb{E}[X_t^2] < \infty$ for every $t$. Suppose

$V_n := \frac{1}{n} \sum_{t=1}^n \mathbb{E}\!\left[X_t^2 \mid \mathcal{F}_{t-1}\right] \xrightarrow{p} \sigma^2 > 0,$

and the conditional Lindeberg condition holds: for every $\epsilon > 0$,

$\frac{1}{n} \sum_{t=1}^n \mathbb{E}\!\left[X_t^2 \, \mathbf{1}\{|X_t| > \epsilon \sqrt{n}\} \,\Big|\, \mathcal{F}_{t-1}\right] \xrightarrow{p} 0.$

Then

$\frac{1}{\sqrt{n}} \sum_{t=1}^n X_t \xrightarrow{d} \mathcal{N}(0, \sigma^2).$

The conditional variance condition replaces "identically distributed", the conditional Lindeberg replaces the unconditional Lindeberg, and the martingale-difference property replaces independence.

A martingale difference is "locally mean-zero": each term has mean zero given the past, even though it can depend on the past in arbitrary nonlinear ways. The conditional variance condition fixes a long-run average level of conditional variance; the conditional Lindeberg condition forbids any single term from dominating the variance budget at scale $\sqrt{n}$. Together these are exactly the right replacements for iid: predictable second moments stand in for identical distribution, and conditional negligibility stands in for genuine independence.

The martingale CLT is the asymptotic backbone of modern stochastic-process theory and underwrites several core ML applications.

• SGD as approximate Gaussian noise: at step $t$ the stochastic gradient $g_t = \nabla \ell(\theta_t; \xi_t)$ for random batch $\xi_t$ has $\mathbb{E}[g_t \mid \mathcal{F}_{t-1}] = \nabla L(\theta_t)$ where $L$ is the population loss. The noise $\eta_t = g_t - \nabla L(\theta_t)$ is a martingale difference, and under bounded-variance assumptions the martingale CLT gives $\sum_t \eta_t / \sqrt{n} \to \mathcal{N}(0, \Sigma_{\text{noise}})$. This is what licenses the SGD-as-SDE approximation $d\theta_t = -\nabla L(\theta_t)\, dt + \sqrt{\eta\, \Sigma_{\text{noise}}}\, dW_t$ used in stochastic-modified-equation analyses (Li, Tai, E, 2017).
• Time-series asymptotics: an AR$(1)$ process $X_t = \rho X_{t-1} + \epsilon_t$ with $|\rho| < 1$ has scaled partial sums whose Gaussian limit comes from a martingale CLT applied to the innovation sequence $\epsilon_t$.
• Online learning regret bounds: the regret of an online algorithm is a sum of martingale differences (current loss minus its conditional expectation given the past). Martingale CLT gives the asymptotic Gaussian distribution of regret around its mean, which is the basis of asymptotic confidence intervals for online estimators.
• Stochastic-approximation iterates: Robbins-Monro and Polyak-Ruppert averaging produce iterates whose asymptotic normality $\sqrt{n}(\bar\theta_n - \theta^*) \xrightarrow{d} \mathcal{N}(0, \Sigma)$ is a martingale CLT statement on the noise sequence at the stationary point.

The martingale CLT can fail when the conditional variance does not stabilize. Heteroscedastic SGD with a non-stationary step size has $V_n$ that does not converge to a deterministic limit, and the conclusion has to be modified: $S_n / \sqrt{V_n}$ converges to $\mathcal{N}(0,1)$ in stable convergence, with $V_n$ itself random in the limit. This is the LAMN (locally asymptotically mixed normal) regime, and it shows up in unit-root time series and in some non-stationary stochastic-approximation problems.

Strong dependence breaks the conclusion: if the conditional variance $\mathbb{E}[X_t^2 \mid \mathcal{F}_{t-1}]$ has long-range dependence, the limit can be fractional Brownian motion at a non-$\sqrt{n}$ rate, not Gaussian.