Which one escapes local minima better? SGD vs full-batch GD

In this article

1. Before you start
2. Why interviewers ask this
3. Escaping local minima from first principles
4. The Staff-level answer
5. The rubric
6. Three variants of this question
7. Common mistakes
8. Follow-up questions
9. Sources

Before you start

This page sits in the machine learning algorithms path. It reads the question as the usual interview comparison, minibatch SGD against full-batch gradient descent. Momentum and Adam are a separate comparison, touched on only in the follow-up questions.

Why interviewers ask this

The question separates a candidate who repeats a slogan ("SGD escapes local minima, GD gets stuck") from one who can say what actually happens. The slogan is partly true, so a weak answer stops there and the follow-up exposes it: what is a local minimum in a network with millions of parameters, and does the global minimum even matter?

A weak answer names SGD as the winner and gives no reason. A strong answer says why: each minibatch gradient is a noisy estimate, and noise moves the parameters off flat spots. A Staff-level answer adds the limits. Neither method is certain to find the global minimum, saddle points and plateaus matter more than bad local minima in large networks, and noise costs a smaller learning rate and slower settling. This page gives you those pieces in order, with a small experiment you can reproduce.

Escaping local minima from first principles

Local minimum

A local minimum is a point where the loss is lower than at every nearby point, so the slope is zero and every small step in any direction raises the loss or leaves it unchanged, even though a lower point may exist elsewhere on the loss surface.

Saddle point

A saddle point is a point where the slope is zero but the loss curves up in some directions and down in others, so it is not a minimum and a small push in the right direction lets descent continue.

Gradient noise

Gradient noise is the random error in a gradient estimated from a small random sample of the training data instead of all of it, so each estimate differs from the true gradient while being right on average.

In plain words

Picture a marble rolling over a bumpy field in fog. It stops in any dip, and a dip can be a shallow puddle or the deepest valley. Full-batch gradient descent rolls the marble with a perfectly smooth, exact push every step. Minibatch SGD adds small random shakes to every push. The shakes can rattle the marble out of a shallow puddle. The analogy breaks in one place: in a real network the field has millions of dimensions, and most flat spots are not dips at all, as Step 2 shows.

In precise terms, full-batch GD follows the exact gradient of the whole training loss. SGD follows a random, unbiased estimate of it, and that randomness lets it leave some regions that the exact path would settle in.

Step 1: Training stalls where the slope is near zero

Training stalls where the slope of the loss is near zero. Gradient descent steps against the slope, so a slope of zero means a step of zero. That happens at a local minimum, at a saddle point and on a flat plateau alike.

A convex loss is one with a single bowl, and there every local minimum is also a global minimum, so "escaping" is a non-issue (Goodfellow et al., 2016, §8.2). The question only matters for non-convex losses such as neural networks. The same chapter notes that training algorithms do not usually halt at a local minimum; training normally ends by early stopping, when a held-out score stops improving. You now know when "stuck" can happen at all, and the next step asks where it actually does.

The figure below uses a toy loss with two minima, a deeper one near x = -1.30 and a shallower one near x = 1.13, which Steps 3 and 4 explain.¹ Its four steps show the zero-slope points, the barrier between the basins, the full-batch path and the noisy path.

1 · Zero slope2 · The barrier3 · Full batch4 · MinibatchReplay

Step-by-step description

1. The slope is zero at both minima and the hump.
2. The shallow basin sits 1.15 below the hump.
3. From x = 2 the exact path ends at the shallow minimum, 1.13.
4. Noise can carry a run over the hump.

• The loss has a deeper minimum near x = -1.30 and a shallower one near x = 1.13.
• The climb out of the shallow basin is about 1.15.
• Full-batch gradient descent from x = 2 ends at x = 1.13.
• The noise is what lets a run cross the hump near x = 0.17.

Step 2: Saddle points and flat regions are the usual trap, not bad local minima

Saddle points and flat regions are more common obstacles than bad local minima in large networks. Goodfellow et al. (2016, §8.2) say that in high dimensions it is very hard to establish that local minima are the problem, and that many other structures also have small gradients.

Choromanska et al. (2015) analyze a simplified model and conjecture that SGD converges to a band of low critical points, where "all critical points found there are local minima of high quality measured by the test error". They also argue that finding the global minimum is in practice irrelevant, because it often overfits. Their result rests on assumptions, so treat it as evidence rather than proof.

Escaping saddles has strong theory. Jin et al. (2017) show that gradient descent with a small random kick when the gradient is small converges to a second-order stationary point in a number of iterations that depends only poly-logarithmically on dimension. For non-degenerate saddles such points are local minima, so escape comes "almost for free". The lesson: random perturbation is provably enough, which is why noise helps.

Step 3: Full batch follows one deterministic path

Full-batch gradient descent follows the same path every time from the same start. It uses the whole training set for every update, which is why Goodfellow et al. (2016) call such methods batch or deterministic gradient methods.

Take the illustrative loss $f(x)=x^4-3x^2+x$ in one dimension. It has a deeper minimum near x = -1.30 (loss -3.51) and a shallower one near x = 1.13 (loss -1.07), separated by a hump near x = 0.17 (loss 0.08), so the climb out of the shallow basin is about 1.15 (illustrative loss).¹ Start at x = 2 with a learning rate of 0.01 (illustrative). The learning rate is the number that scales how far each step moves. After 2,000 steps the run ends at x = 1.13, and 0 of 1,000 repeated runs reach the deeper basin.¹

GD is not stuck forever in general. At a saddle point it can be slow, because the gradient is tiny, but Lee et al. (2016) show that gradient descent from a random start almost surely avoids strict saddle points. Step 4 adds the noise.

Step 4: Minibatch SGD adds noise to every update

Minibatch SGD adds gradient noise to every update. A minibatch is a small random subset of the training examples, and stochastic gradient descent is gradient descent that computes each step from one minibatch instead of the whole set. Training minimizes a loss such as cross-entropy averaged over the examples in the minibatch. Typical minibatches hold 32 to 512 examples (Keskar et al., 2017).

Rerun the toy loss with Gaussian noise of standard deviation 5, 10 and 20 (illustrative) added to the gradient. The script counts the share of 1,000 seeded runs that end in the deeper basin: the share is 0 at zero noise, and the saved output lists it for 5, 10 and 20. The script keeps x between -6 and 6. The noise is what lets a run cross the hump near x = 0.17.¹ The result depends on the noise scale, step size and basin shape, so it shows the mechanism and does not rank the methods. At the largest level the final position also jitters rather than settling, which is the cost of noise.

How much does a bigger batch reduce gradient noise?

Noise has a price in compute too. A gradient from 10,000 examples needs 100 times the computation of one from 100 but cuts the standard error only by a factor of 10 (Goodfellow et al., 2016).

For examples drawn independently, gradient noise falls as one over the square root of the batch size; at the full dataset the noise is zero, because the gradient is exact.¹ A batch of 512 has about 0.0442 times the noise of a batch of 1.¹ With an illustrative 60,000 examples, a full-batch update evaluates 60,000 per-example gradients, a minibatch of 64 evaluates 64, and one pass is 938 SGD updates against one full-batch update.¹

Text description of the diagram

• Gradient noise falls as one over the square root of the batch size.
• A batch of 512 has about 0.0442 times the noise of a batch of 1.

Does a smaller batch really find better minima?

Part of the evidence says yes, and it is contested. Kleinberg et al. (2018) take "an alternative view that SGD is working on the convolved (thus smoothed) version of the loss function", so narrow dips get averaged away. Keskar et al. (2017) report that large-batch methods tend to converge to sharp minimizers, which generalize worse, while small batches land in flatter ones.

The other side is Dinh et al. (2017). They show that reparameterizing a network can make a flat minimum arbitrarily sharp without changing the function it computes, so sharpness measured in the weights alone cannot explain generalization. Treat the sharp-versus-flat story as a tendency, not a rule.

The Staff-level answer

What makes it Staff-level is the three caveats: they question the premise and name the cost of the mechanism instead of crowning a winner.

The rubric

Three variants of this question

Does full-batch gradient descent get stuck in local minima?

It can settle in one, because its path is fixed by the start, but "stuck" overstates it. In large networks the bigger obstacles are saddles and plateaus, where it is slow rather than permanently stuck.

Does a smaller batch size help escape local minima?

Usually, because a smaller batch means more gradient noise (the noise scales with one over the square root of the batch size). Small batches also cost less per update but need more updates and a controlled learning rate.

Does SGD find the global minimum?

No. The theory for SGD and perturbed GD covers reaching a local minimum or a second-order stationary point, not the global minimum, and the global minimum of the training loss often overfits anyway.

Common mistakes

• "SGD finds the global minimum." (wrong) It has no such result; noise only helps leave some regions. (right) "Noise helps SGD leave shallow or sharp basins and saddles, with no global promise."
• "Full-batch GD always gets stuck in local minima." (wrong) In high dimensions saddles and flat regions dominate, and GD often leaves them slowly. (right) "Full-batch GD is deterministic and can be slow at saddles."
• "Local minima are the main problem in deep networks." (wrong) Large networks have many roughly equivalent minima. (right) "Saddles and plateaus are the more common trouble."
• "More noise is always better." (wrong) Noise needs learning-rate control and stops the run from settling. (right) "I balance noise against convergence with batch size and a decaying learning rate."
• "Small batch means flat minima, settled science." (wrong) The effect is reported by Keskar et al. (2017) but contested by Dinh et al. (2017). (right) "Small batches tend to reach flatter minima, though the explanation is debated."

Follow-up questions

Do momentum and Adam escape local minima better?

Not clearly. Wilson et al. (2017) report that adaptive methods such as Adam often generalize worse than SGD on several tasks. Zhou et al. (2020) argue that SGD's heavier-tailed noise lets it leave sharp minima more readily.

Why does a larger learning rate act like more noise?

Smith and Le (2018) give the noise scale as roughly the learning rate times the number of training examples divided by the batch size. A smaller batch and a larger learning rate therefore push the same way. See the gradient descent overview for the update rule.

Is a sharp minimum always worse than a flat one?

No. Keskar et al. (2017) report that sharp minima tend to generalize worse, but Dinh et al. (2017) show that sharpness can be changed by reparameterization alone, so present the link as a tendency. It ties to the bias-variance trade-off and to regularization, which also limits overfitting.

How do you tell a saddle point from a minimum?

Both have zero gradient. The Hessian, the matrix of second derivatives, tells them apart: eigenvalues of both signs mean a saddle, all positive means a minimum, and zero eigenvalues leave the test inconclusive.

Sources

1. Deep Learning, chapter 8: Optimization for Training Deep Models — MIT Press (Goodfellow, Bengio, Courville), 1 Jan 2016
2. The Loss Surfaces of Multilayer Networks — AISTATS 2015 (Choromanska et al.), 21 Feb 2015
3. How to Escape Saddle Points Efficiently (arXiv 1703.00887) — arXiv (Jin et al.), 2 Mar 2017
4. An Alternative View: When Does SGD Escape Local Minima? — ICML 2018 (Kleinberg, Li, Yuan), 1 Jul 2018
5. On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima (arXiv 1609.04836) — ICLR 2017 (Keskar et al.), 15 Sep 2016
6. Sharp Minima Can Generalize For Deep Nets (arXiv 1703.04933) — ICML 2017 (Dinh et al.), 14 Mar 2017
7. A Bayesian Perspective on Generalization and Stochastic Gradient Descent (arXiv 1710.06451) — arXiv (Smith and Le), 17 Oct 2017
8. The Marginal Value of Adaptive Gradient Methods in Machine Learning (arXiv 1705.08292) — arXiv (Wilson et al.), 23 May 2017
9. Towards Theoretically Understanding Why SGD Generalizes Better Than Adam in Deep Learning (arXiv 2010.05627) — NeurIPS 2020 (Zhou et al.), 12 Oct 2020
10. Gradient Descent Converges to Minimizers (arXiv 1602.04915) — arXiv (Lee et al.), 12 Feb 2016