Poor Local–Global Correspondence · Theoretical Limits · Stochastic Gradient Descent

§8.2.7 When local structure misleads

All the obstacles so far were properties of a single point. But you can solve every one of them locally and still fail — if the direction of most local improvement does not point toward the distant regions of low cost. Much of the runtime of training is just the length of the trajectory needed to reach a solution: a learning curve often traces a wide arc around a mountain-shaped structure. In fact, neural networks usually do not reach a critical point of any kind — such points may not even exist. The loss $-\log p(y\mid x;\theta)$ can have no global minimum: a softmax approaches probability 1 only asymptotically, so training keeps improving it forever. Even with no local minima or saddles at all, local descent can get stuck on the wrong side of a hill (fig 8.4):

Because gradient descent (and every effective neural-net learning algorithm) makes only small local moves, much research targets finding a good initial point — a region connected to a solution by a path local descent can follow — rather than inventing non-local moves.

§8.2.8 Theoretical limits

Several results bound what any optimization algorithm can do for neural nets, but they rarely bite in practice.

Why the worst-case theory rarely applies

Some hardness results apply only to units with discrete outputs — but real units output smoothly, making local search feasible. Others show that finding a solution for a network of a given size is intractable — but in practice we just use a larger network, for which many more parameter settings are acceptable. And we never need the exact global minimum: reducing the cost enough for good generalization suffices. Realistic performance bounds remain an open research goal.

§8.3.1 Stochastic gradient descent

SGD and its variants are the most-used optimizers in all of deep learning. Each step follows an unbiased minibatch estimate of the gradient downhill:

Algorithm 8.1 — stochastic gradient descent (click lines)

1Require: a learning-rate schedule $\epsilon_1, \epsilon_2, \dots$ ; initial parameters $\boldsymbol{\theta}$ ⓘ
2while stopping criterion not met doⓘ
3sample a minibatch $\{\boldsymbol{x}^{(1)},\dots,\boldsymbol{x}^{(m)}\}$ with targets $\boldsymbol{y}^{(i)}$ ⓘ
4compute gradient estimate: $\hat{\boldsymbol{g}} \leftarrow \frac{1}{m}\nabla_{\boldsymbol{\theta}} \sum_i L(f(\boldsymbol{x}^{(i)};\boldsymbol{\theta}), \boldsymbol{y}^{(i)})$ ⓘ
5apply update: $\boldsymbol{\theta} \leftarrow \boldsymbol{\theta} - \epsilon_k\,\hat{\boldsymbol{g}}$ ⓘ

The crucial parameter is the learning rate — and unlike batch gradient descent, SGD must decay it over time. Why? The minibatch sampling introduces noise that does not vanish at the minimum (the true gradient goes to zero there, but a random minibatch’s does not). A fixed rate would leave the cost bouncing around forever. Convergence requires:

Term by term

\sum_{k=1}^{\infty} \epsilon_k = \infty \qquad\text{and}\qquad \sum_{k=1}^{\infty} \epsilon_k^2 < \infty

$\sum \epsilon_k = \infty$	the steps must sum to infinity — so you can always travel far enough to reach the minimum, however far the start	go far enough
$\sum \epsilon_k^2 < \infty$	but the SQUARED steps must be finite — the rate must shrink fast enough to damp the never-vanishing sampling noise	settle down
$\epsilon_k = (1-\alpha)\epsilon_0 + \alpha\epsilon_\tau$	the common practical schedule: decay LINEARLY (α = k/τ) until iteration τ, then hold constant; typically ε_τ ≈ 1% ε₀	in practice

Tune $\epsilon_0$ by watching the loss curve — too large and the cost oscillates violently; too small and learning crawls. Slide it:

SGD on a noisy quadratic with a linear-decay schedule: a decaying ε lets the cost settle despite sampling noise; too large an ε₀ makes it oscillate

cost f(θ) learning rate εₖ

ε₀ = 0.60τ = 70

ε_τ = 1% ε₀ = 0.006

converges (settling as ε decays)

The sampling noise never vanishes, so a fixed rate would leave the cost bouncing forever. Decaying ε (Σε=∞ but Σε²<∞) lets it settle. Too large an ε₀ and the cost oscillates violently instead.

Why SGD scales — and why fast convergence is not the point

SGD’s key property: the computation per update is independent of the training-set size $m$ — so it can converge even on enormous datasets, sometimes before even one full pass. Its excess error is only $O(1/\sqrt{k})$ (convex) — worse than batch gradient descent in theory. But the Cramér–Rao bound says generalization error cannot fall faster than $O(1/k)$ anyway, so chasing a faster optimizer would just mean overfitting. SGD’s real advantage is rapid initial progress from very few examples.

Next: accelerating SGD with momentum and Nesterov momentum — momentum & Nesterov momentum.

Check yourself — local vs global structure and SGD

1.What does 'poor correspondence between local and global structure' mean for optimization?

2.The loss −log p(y|x;θ) can lack a global minimum entirely. Why?

3.Why must SGD decay its learning rate over time, unlike batch gradient descent?

4.SGD convergence requires Σεₖ = ∞ and Σεₖ² < ∞. What do these two conditions ensure?

5.In LRScheduleLab, set ε₀ above ~2. What happens, and what is SGD's most important scaling property?

5 questions