Mini-Batch Gradient Descent

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).

Mini-batch gradient descent minimizes an objective $L (θ) = \frac{1}{N} \sum_{i = 1}^{N} ℓ_{i} (θ)$ (an average over $N$ training examples) by repeatedly stepping in the direction of the negative gradient — but estimating that gradient from a random subset of $m ≪ N$ examples rather than all $N$ . It matters because computing the exact gradient over millions of examples per step is prohibitively expensive, while using a single example yields gradients too noisy to converge smoothly. The surprising fact: the noise introduced by mini-batching is not merely a tolerated cost but a feature — it helps escape saddle points and shallow local minima, and acts as an implicit regularizer. Mini-batching also maps perfectly onto the parallel arithmetic of GPUs, where a batch of $m$ examples is processed as one matrix multiplication. It is the workhorse beneath nearly every modern trained neural network.

The Core Insight

The true gradient $\nabla L (θ)$ 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.

Formal Statement

Empirical Risk and Mini-Batch Estimate

Let the training set be ${(x_{i}, y_{i})}_{i = 1}^{N}$ with per-example loss $ℓ_{i} (θ) = ℓ (f_{θ} (x_{i}), y_{i})$ . The empirical risk (full objective) is

L (θ) = \frac{1}{N} i = 1 \sum N ℓ_{i} (θ) .

⟳this is the sample average of per-example losses; it estimates the true risk

E_{(x, y)} [ℓ]

A mini-batch $B \subset {1, \dots, N}$ of size $m = ∣ B ∣$ is drawn (usually without replacement) from the training indices. The mini-batch gradient estimate is

g_{B} (θ) = \frac{1}{m} i \in B \sum \nabla_{θ} ℓ_{i} (θ) .

⟳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 $η_{t} > 0$ , is

θ_{t + 1} = θ_{t} - η_{t} g_{B_{t}} (θ_{t}) .

⟳standard gradient-descent step but with the noisy estimate

g_{B_{t}}

substituted for the exact gradient

\nabla L

Symbols:

θ \in R^{d}

parameters;

N

total examples;

m

batch size;

B_{t}

the batch at step

t

;

η_{t}

learning rate (step size);

g_{B}

mini-batch gradient. Special cases:

m = N

is full-batch gradient descent;

m = 1

is stochastic gradient descent (SGD).

Unbiasedness 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:

E_{B} [g_{B} (θ)] = \nabla L (θ) .

⟳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

Var [g_{B} (θ)] = \frac{1}{m} σ^{2} (θ),

where $σ^{2} (θ) = Var_{i} [\nabla ℓ_{i} (θ)]$ is the variance of a single example's gradient.

⟳variance of the mean of

m

i.i.d. samples is the single-sample variance divided by

m

Why It Holds / Derivation

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

Step 1 — Setup. Let

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

E [\nabla ℓ_{I} (θ)] = i = 1 \sum N \frac{1}{N} \nabla ℓ_{i} (θ) = \nabla L (θ) .

Step 3 — Expectation of the average. By linearity,

E [g_{B}] = \frac{1}{m} j = 1 \sum m E [\nabla ℓ_{I_{j}}] = \frac{1}{m} \cdot m \nabla L (θ) = \nabla L (θ),

establishing Eq. [4]. Step 4 — Variance. Since the

m

draws are i.i.d. with single-draw variance

σ^{2} (θ) = Var [\nabla ℓ_{I}]

Var [g_{B}] = Var [\frac{1}{m} j \sum \nabla ℓ_{I_{j}}] = \frac{1}{m ^{2}} j = 1 \sum m Var [\nabla ℓ_{I_{j}}] = \frac{σ ^{2} ( θ )}{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 ≪ N

this is

\approx 1

, recovering the

1/ m

law.

■

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 $η_{t}$ satisfy $\sum_{t} η_{t} = \infty$ and $\sum_{t} η_{t}^{2} < \infty$ . This established that noisy gradient updates can converge — the licence under which all of SGD and mini-batch GD operate.

Building 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/ 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.

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

Worked Examples

Linear regression, one mini-batch step

Given: Model

f_{θ} (x) = θ x

(single weight, no bias). Squared loss

ℓ_{i} = \frac{1}{2} (θ x_{i} - y_{i})^{2}

, so

\nabla_{θ} ℓ_{i} = (θ x_{i} - y_{i}) x_{i}

. Current

θ_{0} = 1.0

, learning rate

η = 0.1

. A mini-batch of

m = 2

(x_{1}, y_{1}) = (2, 3), (x_{2}, y_{2}) = (4, 5) .

Steps:

Per-example gradients at $θ_{0} = 1$ :

g_{1} = (1 \cdot 2 - 3) \cdot 2 = (- 1) (2) = - 2.

g_{2} = (1 \cdot 4 - 5) \cdot 4 = (- 1) (4) = - 4.

Mini-batch gradient (Eq. 2): $g_{B} = \frac{1}{2} (- 2 + - 4) = - 3.$
Update (Eq. 3): $θ_{1} = θ_{0} - η g_{B} = 1.0 - 0.1 (- 3) = 1.0 + 0.3.$

Answer:

θ_{1} = 1.3 (dimensionless weight)

The weight increased because both predictions were too low (residuals negative), so the negative gradient pushes

θ

up.

Variance reduction by batch size

Given: Suppose the single-example gradient (a scalar) has standard deviation

σ = 8.0

at the current

θ

. Compare the standard deviation of the gradient estimate for

m = 1

m = 64

m = 256

(sampling with replacement,

N

large). Steps:

From Eq. [5], $Var [g_{B}] = σ^{2} / m$ , so $std = σ / m$ .
$m = 1 : 8.0/ 1 = 8.00.$
$m = 64 : 8.0/ 64 = 8.0/8 = 1.00.$
$m = 256 : 8.0/ 256 = 8.0/16 = 0.50.$

Answer:

std = 8.00, 1.00, 0.50 (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/ m

law motivates moderate batch sizes.

Common Misconceptions

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 $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: $η \propto m$ ). Forgetting this makes large-batch training diverge or stall.

There is no universally optimal

m

; common choices are 32–512, tuned empirically.

Mini-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 (θ) = \frac{1}{2} (ℓ_{A} + ℓ_{B})$ with gradients $\nabla ℓ_{A} = (+ 10, 0)$ and $\nabla ℓ_{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.

Connections

Mini-batch GD sits at the center of a family of methods. It generalizes Stochastic Gradient Descent ( $m = 1$ ) and Gradient Descent|Full-Batch Gradient Descent ( $m = N$ ). Its noisy updates are analyzed through Stochastic Approximation (Robbins–Monro) and modeled as a Stochastic Differential Equation|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 ℓ_{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.

Real-World Applications

Deep neural network training (vision): Convolutional networks like ResNet are trained on ImageNet with mini-batches (commonly $m = 256$ ) distributed across GPUs.
Large language models: Transformers (GPT, BERT) are trained with massive effective batch sizes (thousands to millions of tokens) assembled by gradient accumulation across many devices.
Recommender systems: Matrix-factorization and deep recommenders (e.g., YouTube, Netflix) use mini-batch updates over user–item interaction logs that are far too large to fit in memory at once.
Reinforcement learning: Deep Q-Networks (DQN) sample mini-batches from an experience replay buffer to stabilize and decorrelate updates.
Speech recognition: End-to-end acoustic models (e.g., DeepSpeech) train on mini-batches of variable-length audio utterances.
Generative models: GANs and diffusion models alternate mini-batch updates for generator/discriminator or denoiser networks.
On-device / federated learning: Mobile keyboards train local mini-batch updates on user data, aggregating gradients centrally.

Historical Development

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 ℓ_{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 $η$ with $m$ .

Subtleties & Limits

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.