Optimisation: gradient descent, momentum and Adam

Fitting a model means minimising a loss, and for anything beyond a closed form that means gradient descent. The variants all address the same two problems: the gradient is expensive to compute exactly, and the loss surface is badly scaled in different directions.

Equation 6.1

Stochastic gradient descent

Step downhill using the gradient computed on a small batch rather than on the whole dataset.

\theta_{t+1} = \theta_t - \eta\,\nabla_\theta L(\theta_t; \mathcal{B}_t)

$\eta$: Learning rate — the single most important hyperparameter.
$\mathcal{B}_t$: A mini-batch. Its size trades gradient noise against computational efficiency.

Why the noisy gradient is better. The obvious objection is that a batch gradient is an approximation, so it must be worse. It is worse per step and far better per unit of computation: you can take a hundred noisy steps for the cost of one exact one, and a hundred noisy steps make much more progress. The noise also helps — it lets the iterate escape shallow local minima and saddle points, which full-batch descent would sit in forever. Approximation is the feature, not a compromise.

Method	Problem it addresses	Mechanism
Momentum	Oscillation across a narrow valley	Accumulate an exponentially weighted velocity
Nesterov	Momentum overshooting	Evaluate the gradient at the look-ahead point
AdaGrad	Parameters needing different step sizes	Divide by the accumulated squared gradient
RMSProp	AdaGrad’s step size decaying to zero	Use an exponentially weighted average instead
Adam	Both at once	Momentum plus RMSProp, with bias correction

Table 6.2 · What each variant fixes. Adam is the default because it needs the least tuning, not because it always converges to the best solution — plain SGD with a well-chosen schedule often generalises slightly better.

Proposition 6.3

What convexity buys

On a convex loss, any local minimum is global and gradient descent converges to it from any starting point — the problem is solved, and only the speed is in question. Ridge, lasso, logistic regression and SVMs are all convex. Neural networks are not, so the solution depends on initialisation and on the path taken, and "converged" means only that it stopped moving.

Holds when

Convexity is why classical statistical models have reproducible answers and deep models do not.
On a non-convex loss, different random seeds give genuinely different models — which is an argument for ensembling them.

Figure 6.4 · What momentum actually buys. On a quadratic with condition number

100

, plain descent contracts by

0.980

a step and momentum by

0.818

. The improvement is from

\kappa

\sqrt{\kappa}

, which is why badly scaled features are worth fixing before the optimiser is.

Optimisation: gradient descent, momentum and Adam

After this lesson you should be able to

Stochastic gradient descent

What convexity buys

The rest of this lesson is in Premium