Large Numbers and the Central Limit Theorem

A minibatch gradient is an average of noisy per-example gradients. Larger batches reduce sampling noise, but with diminishing returns. Mean and covariance calculations explain that tradeoff before we appeal to a bell curve.

Start with the exact mean and variance

For independent identically distributed X_i with mean μ and finite variance σ², let $\bar X_n=n^{-1}\sum_iX_i$. Linearity and vanishing cross-covariances give

$\mathbb E\bar X_n=\mu,\qquad \operatorname{Var}(\bar X_n)=\sigma^2/n.$

The standard error is $\sigma/\sqrt n$. It describes fluctuations of the estimator across repeated samples. The population standard deviation σ describes the spread of individual observations. Four times as many observations halve the standard error.

The weak law of large numbers

Apply Chebyshev to the average:

$P(|\bar X_n-\mu|\ge\varepsilon)\le\frac{\sigma^2}{n\varepsilon^2}\longrightarrow0.$

For every fixed positive error tolerance, the probability of exceeding it tends to zero. That is convergence in probability. It does not promise monotonic improvement after every new sample, nor exact equality at a finite n. More general laws relax these assumptions; this proof establishes the finite-variance iid version.

The central limit theorem

Under the same iid assumptions with $0<\sigma^2<\infty$,

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

The unscaled average concentrates at μ. The centred, rescaled error approaches a nondegenerate normal distribution. These are compatible statements about different quantities.

The theorem supplies an asymptotic shape, not an exact finite-sample guarantee. Strong skewness or rare events can require much larger samples than a familiar rule such as “thirty is enough”. A Cauchy population has neither a finite mean nor variance; its sample average remains Cauchy, so this theorem does not apply. Dependence also changes the variance and may require a different limit theorem.

Minibatches and Monte Carlo

For independently sampled per-example gradients g_i with mean G and covariance Σ, a batch average has covariance Σ/B. This is an exact covariance identity; normality is unnecessary. Sampling B examples without replacement from a finite dataset of N reduces covariance further by a finite-population factor. Define $\Sigma=N^{-1}\sum_i(g_i-G)(g_i-G)^T$; then the batch covariance is $\frac{N-B}{B(N-1)}\Sigma$ for N>1.

Correlated observations do not give the usual benefit. If scalar errors have common variance σ² and pairwise correlation ρ, the average variance is $\sigma^2[\rho+(1-\rho)/n]$, when such a joint covariance is valid. The shared component remains as n grows.

Monte Carlo estimates obey the same averaging rules. Report an uncertainty estimate alongside the numerical answer, and preserve independence at the correct unit: repeated frames from the same subject are not equivalent to new subjects.

Read beyond

Read the equation in context

The paper studies batch sizes through gradient noise and training efficiency. This ratio compares total gradient variance with squared mean-gradient size. It is undefined when the mean gradient is zero and does not by itself prescribe a universally optimal batch size.

Your turn

Compare the distribution of individual draws with the distribution of standardised averages. Increase the batch size for three skewed populations and inspect both the histogram and the remaining skewness.

Coding problems