Mini-Batch Gradient Descent

⚡ Key Takeaways

Mini-Batch Gradient Descent is an optimization algorithm that updates model parameters using the gradient of a loss function estimated on small, randomly selected subsets ("mini-batches") of the training data. Key result: it combines the low-variance updates of full-batch gradient descent with the computational efficiency and noise-driven exploration of stochastic gradient descent, making it the de facto training method for deep neural networks. Applies to large-scale machine learning, deep learning, and any empirical-risk-minimization problem. Who/when: crystallized in the 2000s–2010s deep learning era, building on Robbins–Monro stochastic approximation (1951).

💡 The Core Insight

The true gradient $\nabla L(\theta)$ is an average over all training examples. Any unbiased random subset gives an unbiased estimate of that average whose variance shrinks like $1/m$ . Mini-batch gradient descent exploits this: pick a batch size $m$ large enough to tame variance and saturate hardware parallelism, but small enough that you take many cheap, frequent steps per pass through the data. You trade a little gradient accuracy for vastly more updates — and the leftover noise often helps.

DefinitionEmpirical Risk and Mini-Batch Estimate

Let the training set be $\{(x_i, y_i)\}_{i=1}^N$ with per-example loss $\ell_i(\theta) = \ell(f_\theta(x_i), y_i)$ . The empirical risk (full objective) is

1

\quad L(\theta) = \frac{1}{N}\sum_{i=1}^{N} \ell_i(\theta).

Derivation hint: this is the sample average of per-example losses; it estimates the true risk $\mathbb{E}_{(x,y)}[\ell]$ . A mini-batch $\mathcal{B} \subset \{1,\dots,N\}$ of size $m = |\mathcal{B}|$ is drawn (usually without replacement) from the training indices. The mini-batch gradient estimate is

2

\quad g_{\mathcal{B}}(\theta) = \frac{1}{m}\sum_{i \in \mathcal{B}} \nabla_\theta \ell_i(\theta).

Derivation hint: replace the average over all $N$ examples in $\nabla L$ with an average over the $m$ sampled examples. The update rule at iteration $t$ , with learning rate $\eta_t > 0$ , is

3

\quad \theta_{t+1} = \theta_t - \eta_t \, g_{\mathcal{B}_t}(\theta_t).

Derivation hint: standard gradient-descent step but with the noisy estimate $g_{\mathcal{B}_t}$ substituted for the exact gradient $\nabla L$ .

Symbols: $\theta \in \mathbb{R}^d$ parameters; $N$ total examples; $m$ batch size; $\mathcal{B}_t$ the batch at step $t$ ; $\eta_t$ learning rate (step size); $g_{\mathcal{B}}$ mini-batch gradient. Special cases: $m = N$ is full-batch gradient descent; $m = 1$ is stochastic gradient descent (SGD).

TheoremUnbiasedness and Variance Reduction

If the batch indices are drawn uniformly at random, then the mini-batch gradient is an unbiased estimator of the full gradient:

4

\quad \mathbb{E}_{\mathcal{B}}\big[g_{\mathcal{B}}(\theta)\big] = \nabla L(\theta).

Derivation hint: linearity of expectation; each index has equal probability of inclusion, so its average loss-gradient equals the population average. Moreover, for sampling with replacement (or large- $N$ approximation), the per-coordinate variance scales as

5

\quad \operatorname{Var}\big[g_{\mathcal{B}}(\theta)\big] = \frac{1}{m}\,\sigma^2(\theta),

where $\sigma^2(\theta) = \operatorname{Var}_{i}[\nabla \ell_i(\theta)]$ is the variance of a single example's gradient. Derivation hint: variance of the mean of $m$ i.i.d. samples is the single-sample variance divided by $m$ .

ProofUnbiasedness (Eq. 4) and Variance (Eq. 5)

Step 1 — Setup. Let $\mathcal{B}$ contain $m$ indices each drawn uniformly from $\{1,\dots,N\}$ (with replacement for simplicity). For a single draw $I$ , the probability $P(I=i) = 1/N$ .

Step 2 — Expectation of one term. For any single sampled index $I$ ,

\mathbb{E}\big[\nabla \ell_I(\theta)\big] = \sum_{i=1}^N \frac{1}{N}\nabla \ell_i(\theta) = \nabla L(\theta).

Step 3 — Expectation of the average. By linearity,

\mathbb{E}[g_{\mathcal{B}}] = \frac{1}{m}\sum_{j=1}^m \mathbb{E}[\nabla \ell_{I_j}] = \frac{1}{m}\cdot m\,\nabla L(\theta) = \nabla L(\theta),

establishing Eq. [4].

Step 4 — Variance. Since the $m$ draws are i.i.d. with single-draw variance $\sigma^2(\theta) = \operatorname{Var}[\nabla \ell_I]$ ,

\operatorname{Var}[g_{\mathcal{B}}] = \operatorname{Var}\!\Big[\tfrac{1}{m}\sum_j \nabla\ell_{I_j}\Big] = \frac{1}{m^2}\sum_{j=1}^m \operatorname{Var}[\nabla\ell_{I_j}] = \frac{\sigma^2(\theta)}{m},

giving Eq. [5].

Step 5 — Without-replacement correction. When sampling without replacement from a finite set of size $N$ , multiply by the finite-population correction factor $\frac{N-m}{N-1}$ . For $m \ll N$ this is $\approx 1$ , recovering the $1/m$ law. $\blacksquare$

∎

HR

Herbert Robbins & Sutton Monro

1951

Although mini-batch GD is a 21st-century computational staple, its theoretical bedrock is the Robbins–Monro stochastic approximation scheme. Robbins (a statistician and topologist) and Monro showed that you can find the root of an unknown function using only noisy measurements, provided the step sizes $\eta_t$ satisfy $\sum_t \eta_t = \infty$ and $\sum_t \eta_t^2 < \infty$ . This established that noisy gradient updates can converge — the licence under which all of SGD and mini-batch GD operate.

🧠 Intuition

Imagine you want the average opinion of a city of $N=1{,}000{,}000$ people, but polling everyone takes a day. Polling one person (SGD) is instant but wildly unrepresentative; polling everyone (full-batch) is accurate but glacial. Polling a random $m=256$ people (mini-batch) gives an answer that's almost as accurate as the full poll — its error shrinks like $1/\sqrt{m}$ — but costs almost nothing. You can re-poll every few minutes and steadily refine your estimate of where to move. Now picture the loss landscape as a foggy mountain. Full-batch descent walks downhill perfectly but pauses forever at every flat ledge (saddle point) and small dip (local minimum). Mini-batch's gradient jitter is like an occasional gust of wind: it knocks you off ledges and out of shallow dips, helping you find deeper valleys — while still trending downhill on average.

Figure

Loss vs. iterations: full-batch (smooth), SGD (very noisy), mini-batch (a balanced compromise).

ExampleLinear regression, one mini-batch step

Given: Model $f_\theta(x) = \theta x$ (single weight, no bias). Squared loss $\ell_i = \tfrac{1}{2}(\theta x_i - y_i)^2$ , so $\nabla_\theta \ell_i = (\theta x_i - y_i)\,x_i$ . Current $\theta_0 = 1.0$ , learning rate $\eta = 0.1$ . A mini-batch of $m=2$ :

(x_1,y_1)=(2,3), \quad (x_2,y_2)=(4,5).

Steps: 1. Per-example gradients at $\theta_0=1$ :

$g_1 = (1\cdot 2 - 3)\cdot 2 = (-1)(2) = -2.$
$g_2 = (1\cdot 4 - 5)\cdot 4 = (-1)(4) = -4.$

2. Mini-batch gradient (Eq. 2): $g_{\mathcal{B}} = \tfrac{1}{2}(-2 + -4) = -3.$ 3. Update (Eq. 3): $\theta_1 = \theta_0 - \eta\, g_{\mathcal{B}} = 1.0 - 0.1(-3) = 1.0 + 0.3.$

Answer:

\boxed{\theta_1 = 1.3 \ \text{(dimensionless weight)}}

The weight increased because both predictions were too low (residuals negative), so the negative gradient pushes $\theta$ up.

ExampleVariance reduction by batch size

Given: Suppose the single-example gradient (a scalar) has standard deviation $\sigma = 8.0$ at the current $\theta$ . Compare the standard deviation of the gradient estimate for $m=1$ , $m=64$ , $m=256$ (sampling with replacement, $N$ large).

Steps: 1. From Eq. [5], $\operatorname{Var}[g_{\mathcal{B}}] = \sigma^2/m$ , so $\operatorname{std} = \sigma/\sqrt{m}$ . 2. $m=1:\ \ 8.0/\sqrt{1} = 8.00.$ 3. $m=64:\ 8.0/\sqrt{64} = 8.0/8 = 1.00.$ 4. $m=256:\ 8.0/\sqrt{256} = 8.0/16 = 0.50.$

Answer:

\boxed{\text{std} = 8.00,\ 1.00,\ 0.50 \ \text{(gradient units)}}

Note the diminishing return: going from $m=1\!\to\!64$ cuts noise 8×; going $64\!\to\!256$ (4× the compute) only halves it. This $1/\sqrt{m}$ law motivates moderate batch sizes.

⚠️ Bigger batches are not always better

A common belief is "larger $m$ → better, since the gradient is more accurate." But:

Variance only falls like $1/m$ , so doubling $m$ doubles compute for a $\sqrt{2}$ noise reduction — diminishing returns.
Very large batches lose the beneficial noise that helps escape saddle points and shallow minima, often converging to sharper minima that generalize worse (the "large-batch generalization gap").
The learning rate must usually be rescaled with batch size (e.g., the linear scaling rule: $\eta \propto m$ ). Forgetting this makes large-batch training diverge or stall.

There is no universally optimal $m$ ; common choices are 32–512, tuned empirically.

CounterexampleMini-batch gradient ≠ exact gradient direction

It is tempting to treat each mini-batch step as "downhill on $L$ ." It is only downhill in expectation. Consider $L(\theta)=\tfrac{1}{2}(\ell_A + \ell_B)$ with gradients $\nabla\ell_A = (+10, 0)$ and $\nabla\ell_B = (-10, +2)$ at some point. The true gradient is $\nabla L = (0, +1)$ — pointing in $+y$ . But a mini-batch of just $\{A\}$ gives $g=(+10,0)$ , moving the parameters in the $+x$ direction, completely orthogonal to (and uncorrelated with) the true descent direction. Individual mini-batch steps can temporarily increase the full loss; only their average trends downward.

connection

Mini-batch GD sits at the center of a family of methods. It generalizes Stochastic Gradient Descent ( $m=1$ ) and Full-Batch Gradient Descent ( $m=N$ ). Its noisy updates are analyzed through Stochastic Approximation (Robbins–Monro) and modeled as a continuous-time SGD diffusion. Practically, it is the base on which Momentum (Optimization), Adam Optimizer, and RMSProp build adaptive or accelerated variants. Its computation relies on Backpropagation to obtain $\nabla \ell_i$ efficiently, and its objective is the Empirical Risk Minimization framework. The implicit regularization it provides connects to Generalization (Machine Learning) and the flat-vs-sharp-minima debate.

🔬 Where this appears

⏳ History

- 1847 — Cauchy proposes the method of steepest (gradient) descent for solving systems of equations.

- 1951 — Robbins & Monro publish A Stochastic Approximation Method, proving convergence of root-finding with noisy measurements; the theoretical foundation for SGD.

- 1952 — Kiefer & Wolfowitz extend stochastic approximation to gradient-free optimization of noisy objectives.

- 1960s–1980s — Stochastic gradient methods used in adaptive filtering (Widrow–Hoff LMS) and early neural network learning.

- 1986 — Rumelhart, Hinton & Williams popularize Backpropagation, enabling efficient per-example gradients

\nabla \ell_i

in multilayer networks.

- 1998 — LeCun et al.'s Efficient BackProp gives practical advice on stochastic/mini-batch training and learning-rate schedules.

- 2010 — Bottou's work on large-scale learning argues SGD/mini-batch methods are optimal for big data given fixed compute budgets.

- 2012 — AlexNet trains on GPUs with mini-batches, igniting the deep learning era and cementing mini-batch GD as standard practice.

- 2017 — Goyal et al. demonstrate the linear scaling rule, training ImageNet in 1 hour with batch size 8192, clarifying how to scale

\eta

with

m

.

open-problem

Several questions about mini-batch GD remain active research:

Optimal batch size theory: Why moderate batches generalize better than huge ones — the precise mechanism linking gradient noise to flat minima and generalization — is not fully understood.
SGD as approximate inference: Whether mini-batch noise can be rigorously characterized as sampling from a Bayesian posterior (the "SGD-as-MCMC" view) is only partially resolved.
Adaptive batch sizing: Principled, automatic schedules that grow $m$ during training (to reduce noise as you approach a minimum) lack a complete theory.
Non-convex convergence rates: Tight, instance-dependent bounds for mini-batch GD on the highly non-convex, over-parameterized landscapes of deep nets remain open.
Heavy-tailed gradient noise: Empirically, mini-batch gradient noise is often heavy-tailed (non-Gaussian), challenging the standard finite-variance assumption behind Eq. [5] and its diffusion approximations.

Formal Statement

Why It Holds / Derivation

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also