Batch & Minibatch Algorithms · Challenges in Optimization · Ill-Conditioning

§8.1.3 Batch and minibatch algorithms

The cost function and its gradient are expectations over the training set — so instead of touching every example each step, estimate them from a random subset:

Term by term

\boldsymbol{g} = \nabla_\theta J = \mathbb{E}_{(x,y)\sim\hat p}\big[\nabla_\theta L\big] \;\;\approx\;\; \hat{\boldsymbol{g}} = \frac{1}{m}\sum_{i=1}^{m} \nabla_\theta L\big(f(x^{(i)};\theta), y^{(i)}\big)

$\mathbb{E}_{\hat p}[\nabla_\theta L]$	the exact (full-batch) gradient — an average over the WHOLE training set, expensive because it evaluates every example	exact, costly
$\hat{\boldsymbol{g}} = \frac{1}{m}\sum \nabla_\theta L$	the minibatch estimate: average the gradient over m randomly-sampled examples — UNBIASED if they are drawn independently	cheap estimate
$\text{std. error } \sigma/\sqrt{m}$	the estimate error falls only as 1/√m, and (on the first epoch) ĝ is an unbiased estimate of the TRUE generalization gradient	the payoff

Why not just use a huge batch? Because of the $\sigma/\sqrt{n}$ standard error of the mean — the returns to larger batches are sublinear. Slide the batch size and watch a 100× compute increase buy only a 10× smaller error:

The minibatch gradient error is σ/√n: it shrinks only with the square root of the batch size, so tiny fast batches beat huge exact ones per unit of computation

n = 64

error σ/√n = 0.125

compute ∝ n = 64×

100× the compute buys only 10× less error

Because the estimate error shrinks like 1/√n, huge batches are wasteful — a fast, noisy gradient from a small batch usually converges faster per unit of computation than a slow, exact one.

The vocabulary is slippery, so pin it down:

Batch, stochastic, minibatch — the terminology
	examples per update	notes
Batch / deterministic	the ENTIRE training set	"batch gradient descent" means full-set — but confusingly "batch size" means the MINIBATCH size
Stochastic / online	a single example	"online" is reserved for a continual stream of never-repeated examples
Minibatch (stochastic)	more than one, fewer than all (32–256, powers of 2)	the default in deep learning; now often just called "stochastic". SGD is the canonical case

Dotted-underlined cells have explanations — click one.

Choosing the minibatch size

Larger batches give more accurate gradients (with sublinear returns) but cost memory that scales with the batch. Very small batches underutilize multicore hardware; GPUs like powers of 2 (32–256). Small batches also regularize via gradient noise — generalization error is often best at batch size 1, though that needs a small learning rate and many steps. Crucially, minibatches must be drawn randomly: if the dataset is ordered (e.g. all of patient A, then patient B…), shuffle it once and store it shuffled, or every minibatch is biased. On the first epoch each minibatch is an unbiased estimate of the true generalization gradient; later epochs re-sample seen data and become biased.

§8.2 Challenges in neural network optimization

Traditionally, machine learning sidestepped the difficulty of general optimization by carefully designing convex objectives. Neural networks force us into the general non-convex case — and even convex optimization has its own traps. The next sections catalog the obstacles, starting with one that appears even in convex problems.

§8.2.1 Ill-conditioning

The most prominent convex-and-beyond obstacle is ill-conditioning of the Hessian. A second-order Taylor expansion predicts what a gradient step of $-\epsilon\boldsymbol{g}$ does to the cost:

Term by term

\Delta J \;\approx\; \frac{1}{2}\epsilon^2\, \boldsymbol{g}^\top \boldsymbol{H}\boldsymbol{g} \;-\; \epsilon\, \boldsymbol{g}^\top\boldsymbol{g}

$-\epsilon\,\boldsymbol{g}^\top\boldsymbol{g}$	the first-order GAIN: moving along −g should reduce the cost by this much	the win
$\tfrac12\epsilon^2\,\boldsymbol{g}^\top\boldsymbol{H}\boldsymbol{g}$	the second-order CURVATURE penalty: it grows with how sharply the cost curves along g (the Hessian)	the tax
$\tfrac12\epsilon^2 \boldsymbol{g}^\top\boldsymbol{H}\boldsymbol{g} > \epsilon\boldsymbol{g}^\top\boldsymbol{g}$	when the curvature term overwhelms the gain, even a tiny step RAISES the cost — so ε must shrink and learning stalls despite a strong gradient	ill-conditioned

The tell-tale sign: the gradient norm $\boldsymbol{g}^\top\boldsymbol{g}$ stays large while $\boldsymbol{g}^\top\boldsymbol{H}\boldsymbol{g}$ grows by an order of magnitude. In fact the gradient norm can increase throughout a perfectly successful training run (fig 8.1) — learning succeeds not by reaching a small gradient, but despite a growing one:

Newton’s method handles ill-conditioning well in convex problems, but — as later sections argue — needs significant modification before it is safe for neural networks. Next: local minima, the saddle points that actually dominate, cliffs, and vanishing/exploding gradients — the landscape of obstacles.

Check yourself — minibatches and ill-conditioning

1.Why do larger minibatches give diminishing returns for estimating the gradient?

2.In BatchSizeLab, going from n = 64 to n = 256 (4× the batch) does what to the gradient error?

3.The terminology is confusing. What does 'batch gradient descent' mean, versus 'batch size'?

4.A gradient step of −εg changes the cost by ≈ ½ε²gᵀHg − εgᵀg. When is ill-conditioning a problem?

5.Figure 8.1 shows the gradient norm INCREASING throughout a successful training run. What does this illustrate?

5 questions