Gradient Descent and Optimization

You are on a mountainside in fog so thick you can see about a metre. You need to get to the bottom of the valley. You cannot see the valley, you cannot see the peaks, and you have no map. What you can do is feel the ground under your feet and work out which way is downhill from exactly where you stand.

So you take a step that way. Then you feel the ground again, because after moving, the downhill direction has changed. Step, re-measure, step, re-measure. If the slope is gentle you can afford a long stride; if it is steep and you overstride, you will overshoot the bottom and end up climbing the far side.

That is gradient descent in full. It is not an approximation to something cleverer — for a model with a million parameters, the fog is the honest situation. You cannot see the loss surface, you can only evaluate the loss and its slope at the point you currently occupy. Everything interesting in optimisation is about how to take good steps given only that local information.

The update rule, and why there is a minus sign

Reading it piece by piece. $\theta_t$ is the full set of parameters at step $t$. $L(\theta_t)$ is the loss at those parameters — one number saying how badly the model is doing. $\nabla_\theta L$ is the gradient: a vector with one entry per parameter, each entry saying how much the loss would increase if you increased that parameter slightly. And $\eta$ (eta) is the learning rate, a small positive number controlling how far you move.

The minus sign is the whole point. The gradient points in the direction of steepest increase in the loss. You want the loss to go down. So you move in the opposite direction. Flip that sign and your model will reliably and confidently get worse, which is one of the more embarrassing bugs to find after an hour of watching a loss curve climb.

The gradient tells you where uphill is. Subtracting it is how you go downhill.

Watching it work, one number at a time

Minimise $f(\theta) = (\theta - 3)^2$, whose minimum is obviously at $\theta = 3$, starting from $\theta_0 = 0$ with $\eta = 0.1$. The gradient is $f'(\theta) = 2(\theta - 3)$, so the update becomes $\theta \leftarrow \theta - 0.2(\theta - 3)$.

Look at the last column. Each step multiplies the remaining distance by exactly $0.8$. The gradient is negative throughout — the loss decreases as $\theta$ increases — so subtracting it moves $\theta$ up, towards 3. And as you get closer, the gradient shrinks, so the steps shrink automatically. Gradient descent slows down near the bottom without being told to.

The learning rate is the parameter that decides everything

That factor of $0.8$ was not arbitrary. For this function, the error multiplier per step is $|1 - 2\eta|$. Three regimes follow directly.

Too large: divergence

Set $\eta = 1.1$. Now the multiplier is $|1 - 2.2| = 1.2$, which is greater than 1, so the error grows and flips sign each step:

The step overshoots the minimum, lands further away on the other side, and the next gradient is therefore even bigger. In a real model this reaches floating-point infinity within a handful of steps and the loss prints as nan.

There is a formula for when this happens. If the largest curvature of the loss surface is $L$ — the biggest eigenvalue of the Hessian, the matrix of second derivatives — then gradient descent is stable only when

Here $f''(\theta) = 2$, so $L = 2$ and the threshold is $\eta < 1$. Our $\eta = 0.1$ was comfortably inside it; $\eta = 1.1$ was outside. This is worth internalising: divergence is not bad luck, it is a predictable consequence of the step size exceeding twice the reciprocal of the sharpest curvature.

Too small: crawling

Set $\eta = 0.001$. The multiplier is $0.998$, so after 100 steps the error has only fallen to $0.998^{100} \approx 0.82$ of its original value — from a distance of 3 down to 2.46. You will get there eventually, but "eventually" may be a hundred thousand epochs. Worse, on a real non-convex surface a tiny learning rate lets the model settle into the first shallow dip it finds instead of passing through it.

Just right, and how you find it

The honest method is to run a few hundred steps at each of $10^{-1}, 10^{-2}, 10^{-3}, 10^{-4}$ and look at the loss curves. Too large diverges or oscillates wildly. Too small produces a nearly flat line. The right one drops fast and then bends. Pick the largest rate that still descends smoothly, since that gets you the most progress per step.

Schedules: change it as you go

Early in training you are far from anywhere good and want to cover ground. Late in training you are near a minimum and want to fine-tune. One fixed rate cannot do both, which is why almost every serious training run varies $\eta$ over time.

How much data goes into each step

The gradient of the loss over the whole training set is the average of the per-example gradients. You do not have to use all of them.

Mini-batching wins for two independent reasons. The practical one is hardware: a GPU computing 128 examples at once is barely slower than computing one, so you get 128 times the information for almost free. The subtler one is that the noise helps. An exact gradient will walk you straight into the nearest dip and stop. A noisy gradient rattles the parameters around enough to escape shallow dips and keep looking. Noise is not merely tolerated here — it is doing useful work.

Batch size is not just a memory setting. It controls how much noise is in every step, and that noise is part of how the model generalises.

Where plain gradient descent struggles

Consider a loss surface shaped like a long narrow valley — steep across, nearly flat along. Concretely, $f(x,y) = x^2 + 20y^2$, where the $y$ direction is twenty times more curved than the $x$ direction.

The gradient at any point is dominated by the steep direction, so descent takes a big step across the valley, overshoots, comes back, overshoots again. It zig-zags violently while making almost no progress along the valley floor, which is where the minimum actually is. Your learning rate is capped by the steep direction ($\eta < 2/40 = 0.05$ here) but the shallow direction needs a much larger step to move at all.

This is ill-conditioning, and it is the normal state of affairs for real models, not a pathological case. The ratio of largest to smallest curvature in a deep network is routinely thousands. Alongside it sit two more problems: plateaus, where the gradient is near zero over a wide region so progress stalls, and saddle points, where the gradient is exactly zero but the point is a minimum in some directions and a maximum in others. In high dimensions saddles hugely outnumber true local minima, because requiring all million directions to curve the same way is astronomically unlikely.

Momentum: remember where you were going

The zig-zag has a structure worth exploiting. The across-valley component of the gradient flips sign every step; the along-valley component keeps pointing the same way. If you accumulate a running average of recent gradients, the alternating components cancel and the consistent one builds up.

The vector $v_t$ is a velocity. Each step it decays by a factor $\beta$ (usually 0.9) and has the current gradient added. The physical picture is a heavy ball rolling downhill rather than a hiker taking discrete steps: it carries inertia through flat patches and does not get thrown sideways by every local wobble.

If the gradient stays roughly constant at $g$, the velocity converges to a geometric series:

With $\beta = 0.9$ that is $10g$. So in a consistent direction, momentum eventually takes steps ten times larger than plain descent would. That is where the speed-up comes from — and also the warning: momentum can overshoot a sharp minimum and need several steps to settle, which is why raising $\beta$ towards 0.99 sometimes destabilises training that was fine at 0.9.

Adaptive rates: one learning rate per parameter

Momentum fixes the direction. It does not fix the fact that different parameters need wildly different step sizes. RMSprop addresses that by tracking a running average of each parameter's squared gradient and dividing by its square root:

Everything here is element-wise, so each parameter gets its own scaling. A parameter that has been receiving large gradients gets a large $s$, so its effective step is divided down. A parameter with consistently small gradients gets a small $s$ and its step is boosted. The tiny $\epsilon$ (about $10^{-8}$) exists only to stop division by zero.

The effect on the narrow valley is direct: the steep direction gets damped, the shallow direction gets amplified, and the zig-zag largely disappears.

Adam combines both

$m_t$ is momentum (an average of gradients) and $v_t$ is the RMSprop term (an average of squared gradients). The interesting part is the bias correction in the middle line, which people often skip over.

Both averages start at zero. At the very first step with $\beta_1 = 0.9$, you get $m_1 = 0.1\,g_1$ — a tenth of the true gradient, purely because the average has not had time to fill up. Dividing by $1 - \beta_1^1 = 0.1$ recovers exactly $g_1$. The second moment is worse: with $\beta_2 = 0.999$, $v_1 = 0.001\,g_1^2$, and dividing by $1 - 0.999 = 0.001$ recovers $g_1^2$. Without the correction, $\sqrt{v_1}$ would be about 32 times too small while $m_1$ is only 10 times too small, so the first step would come out about three times larger than intended — at exactly the moment the parameters are furthest from anywhere sensible. The correction factors shrink towards 1 as $t$ grows and become irrelevant after a few hundred steps, but they matter enormously at the start.

Practical advice: start with Adam at $\eta = 10^{-3}$. It is forgiving and gets you a working baseline fast. If you are chasing the last fraction of a percent on a well-understood task, switch to SGD with momentum and a cosine schedule and tune it properly.

Knowing when to stop

For a convex surface — a single bowl, one minimum — convergence means the gradient norm has gone to zero and you are provably at the global best. Linear and logistic regression are like this.

Deep networks are not. Their surfaces have vast numbers of critical points, and no optimiser gives you a guarantee about which one you reached. "Converged" honestly means "the loss stopped improving and I stopped paying for compute". Reasonable stopping criteria:

• Small gradient: $\|\nabla L\| < 10^{-6}$. Sound in theory, but on a plateau or saddle it fires early.
• Loss plateau: the change in loss stays under a threshold for several consecutive epochs.
• Iteration budget: a hard cap, so a bad run cannot burn the cluster.
• Early stopping: track loss on a held-out validation set, keep a copy of the best weights, and stop after $p$ epochs with no improvement.

Early stopping is the one that matters most, because it targets the right quantity. Training loss goes down forever — that is what you are optimising. Validation loss goes down, bottoms out, and then rises as the model starts memorising. The bottom of that curve is the model you want, and you will only find it if you were watching.

Implementing it

1import numpy as np23# An ill-conditioned quadratic: 20x more curved in y than in x.4def f(p):     return p[0]**2 + 20 * p[1]**25def grad(p):  return np.array([2 * p[0], 40 * p[1]])67def sgd(grad, theta, lr=0.04, steps=60, beta=0.0):8    v = np.zeros_like(theta)9    path = [theta.copy()]10    for _ in range(steps):11        g = grad(theta)12        v = beta * v + g              # beta = 0 gives plain gradient descent13        theta = theta - lr * v14        path.append(theta.copy())15    return np.array(path)1617def adam(grad, theta, lr=0.1, steps=60, b1=0.9, b2=0.999, eps=1e-8):18    m = np.zeros_like(theta)19    v = np.zeros_like(theta)20    path = [theta.copy()]21    for t in range(1, steps + 1):22        g = grad(theta)23        m = b1 * m + (1 - b1) * g24        v = b2 * v + (1 - b2) * g**225        m_hat = m / (1 - b1**t)       # bias correction: vital at small t26        v_hat = v / (1 - b2**t)27        theta = theta - lr * m_hat / (np.sqrt(v_hat) + eps)28        path.append(theta.copy())29    return np.array(path)3031start = np.array([5.0, 1.0])32for name, path in [("plain   ", sgd(grad, start)),33                   ("momentum", sgd(grad, start, beta=0.9)),34                   ("adam    ", adam(grad, start))]:35    print(name, "final f =", round(float(f(path[-1])), 6))

Run it and the ordering is probably not the one you expected: plain descent finishes lowest (about 0.0011), momentum second (about 0.042) and Adam last (about 0.26). Each result is a caveat from this lesson made visible. The valley is only mildly stretched, with a curvature ratio of 20, and plain descent at a learning rate close to its $2/40$ limit shrinks the $x$ distance by a steady factor of 0.92 per step. Momentum at $\beta = 0.9$ overshoots: by step 10 it has swung past the minimum to $x \approx -2.8$, and it is still spiralling in at step 60. Change it to beta=0.5 and it finishes near $5 \times 10^{-12}$, far ahead of the others. Adam does what the RMSprop section promised — $y$ settles without a zig-zag — but each of its steps is roughly $\eta = 0.1$ long whatever the gradient, so covering the five units along $x$ takes it most of the sixty steps.

The lesson is not that one optimiser is best. Each has settings, and the right settings depend on the shape of the surface.

Reading a training run when it goes wrong

Almost every training failure has a signature in the loss curve, and almost every signature points at the optimiser.

What to do on a real training run

Before anything else, overfit a tiny subset. Take twenty examples and train until the loss is essentially zero. If a model cannot memorise twenty examples, the problem is a bug — a wrong loss, a broken gradient, a label mismatch — and no amount of learning-rate tuning will help. This one check catches most real failures in minutes.

Then set a baseline: Adam at $10^{-3}$, a mini-batch that fills your device, a cosine schedule, and early stopping on a validation split. Log the loss every few hundred steps and log the gradient norm alongside it, because the gradient norm tells you why the loss is doing what it is doing. A norm that climbs towards infinity and a norm that collapses to zero produce identically flat loss curves but need opposite fixes.

Finally, when a step size feels arbitrary, remember it is not. The bound $\eta < 2/L$ says the largest usable step is set by the sharpest curvature in the loss surface. Every technique in this area — normalisation layers, careful initialisation, momentum, per-parameter scaling — is ultimately a way of reshaping that surface so a single learning rate can work for every parameter at once.