Gradient Descent

Definition

Gradient descent is the rule that turns "which way is downhill" into an actual change to a model's numbers. Every parameter gets the same one-line treatment — subtract a small multiple of its own gradient:

w ← w − η · ∂L/∂w

That is the whole algorithm. ∂L/∂w says how much the loss rises if this parameter rises, so subtracting it moves the parameter the other way; η (eta) is the learning rate, the fraction of the gradient you actually take. It is the only knob, and it is the entire subject.

The ball-rolling-downhill picture everyone is taught hides exactly that. A ball has mass and inertia and cannot leave the hill; gradient descent takes discrete jumps of a size you choose, and a bad choice does not make it roll slowly — it makes it fly off. There is an exact threshold, and on the simplest possible bowl, f(x) = x² starting from x = 1, you can watch it: with η = 0.1 you creep inward, with η = 0.5 you land on the minimum in a single step, with η = 1 you bounce between +1 and −1 forever without ever getting closer, and with η = 1.1 you are at −2.49 after five steps and heading for infinity. Same algorithm, same function, same starting point. Only the step size changed.

Gradient descent does not compute the gradient — backpropagation does, in one reverse sweep through the network. Backpropagation measures; gradient descent moves. This page is about the move.

What breaks if you get it wrong is not subtle. A learning rate above the threshold produces a loss that grows geometrically and overflows to NaN within a few hundred steps, and the usual response is to go looking for a bug in the model. There is no bug. A rate below it but badly chosen produces the other failure: a run that trains for a week and lands somewhere a correctly tuned run reached in an afternoon.

How It Works

One step needs three things: a current position (the parameter values), a gradient at that position, and a step size. Multiply, subtract, repeat. Nothing in the rule refers to where the minimum is or how far away it is — gradient descent is blind beyond the point it is standing on, which is why it needs so many steps and why the step size carries so much of the outcome.

Take f(x) = x², whose gradient is f'(x) = 2x and whose minimum is at x = 0. Substituting into the update rule gives something exact:

x_{t+1} = x_t − η · 2x_t = x_t · (1 − 2η)

Every step multiplies the position by the same constant (1 − 2η). So the whole behaviour of gradient descent on this function is decided by one number, and you can read off the answer without simulating anything: the iterates shrink if |1 − 2η| < 1, which is exactly 0 < η < 1. Here are the actual iterates from x₀ = 1:

Three things in that table are worth more than any amount of prose about "tuning the learning rate". First, bigger is not slower-or-faster — it is a different regime. Second, η = 0.9 and η = 0.1 converge at identical speed, because |−0.8| = |0.8|; the loss values are the same to the last digit even though one sequence is positive throughout and the other flips sign every step. Overshooting is not automatically a problem. Third, the transition from "converges" to "explodes" is not gradual: at η = 1.0 the algorithm is in perfect balance, doing nothing forever, and 10% more step size turns every iteration into a 20% increase in distance from the answer.

That threshold generalizes. A function is called L-smooth when its gradient changes no faster than L per unit of distance — for a twice-differentiable function, L is the largest curvature, the biggest eigenvalue of the Hessian. The classical guarantee is that gradient descent converges on such a function whenever

η < 2/L

For f(x) = x², the second derivative is 2 everywhere, so L = 2 and 2/L = 1. That is precisely the boundary the table shows: converging below η = 1, stalled at exactly 1, diverging above. The toy example and the general theorem are the same statement.

The catch is that nobody can look up L for a real neural network. The loss surface has a different curvature at every point, and the largest one changes as training proceeds — so the ceiling moves while you are trying to stay under it. Worse, the network moves toward it: Cohen et al. showed in "Gradient Descent on Neural Networks Typically Occurs at the Edge of Stability" (ICLR 2021) that during full-batch training the sharpness rises until it sits just above 2/η and then hovers there, so the loss stops falling monotonically and instead wobbles downward on the boundary of blowing up. Real training does not run safely inside the stable region; it runs on the edge of it, which is why learning rate is found by experiment rather than calculation and why a rate that was fine for 10,000 steps can still detonate at step 10,001.

The other half of the story is that the gradient you use does not have to be the exact one. Estimating it from a handful of examples instead of the whole dataset changes the economics completely, and that is what the next section is about.

Types

The three named variants differ in exactly one thing: how many training examples the gradient is estimated from before a step is taken. Everything else — the update rule, the learning rate, the stability threshold — is identical.

Batch gradient descent uses the entire training set for every step. The gradient is the true gradient of the true objective, the descent direction is exact, and on a convex problem the convergence theory applies cleanly. It is also, at scale, absurd: over a dataset of 1,000,000 examples, one parameter update costs 1,000,000 gradient evaluations. A run of 100 updates — nowhere near enough to train anything — costs 100 million.

Stochastic gradient descent (SGD) goes to the opposite extreme: estimate the gradient from a single randomly chosen example and step immediately. The same 1,000,000 evaluations now buy 1,000,000 updates instead of one. Each direction is badly wrong, but wrong in a way that averages out, and the algorithm makes a million corrections in the time full-batch made one. Robbins and Monro proved in "A Stochastic Approximation Method" (1951) that this converges provided the step sizes satisfy two conditions: Σηₜ = ∞, so the steps can still travel an unbounded distance, and Σηₜ² < ∞, so the noise is eventually damped. ηₜ = 1/t satisfies both — the harmonic series diverges while Σ1/t² = π²/6 ≈ 1.645 converges. ηₜ = 1/√t fails the second and does not settle.

Mini-batch gradient descent takes a group — typically 32 to a few thousand examples — and is what essentially every real system runs. It wins for two independent reasons. The practical one is hardware: a batch of 32 is a matrix multiplication a GPU executes at nearly the same wall-clock cost as a single example, so batching is almost free until the batch is large. The statistical one is the reason the trade is lopsided in the first place. The standard error of a gradient averaged over B independent samples falls as 1/√B, while its cost rises as B. Going from batch 32 to batch 1,024 is 32× the compute for a gradient only √32 ≈ 5.7× more accurate. That square root is why bigger batches stop paying: over the same 1,000,000 evaluations, batch 32 gets 31,250 updates and batch 1,024 gets 976, and the second run's gradients are not 32 times better.

The noise is not merely tolerated, either. It is often the reason mini-batch training generalizes better than full-batch training on the identical data — see Challenges below.

Real-World Applications

Learning-rate warmup in large language model training is the stability condition made operational. Curvature at random initialization is high and erratic, so the safe step size is small; after a few thousand steps the surface flattens and a larger rate becomes both safe and necessary. GPT-3 (Brown et al., 2020) accordingly ramped the rate linearly over the first 375 million tokens up to 6 × 10⁻⁵ for the 175B model, then cosine-decayed it to 10% of that over 260 billion tokens — those specific figures are from that paper and are not a universal recipe, but the shape, ramp then decay, is near-universal in LLM pretraining and is a direct consequence of 2/L being small at the start and larger later.

Scaling a batch across many machines is the same arithmetic in the other direction. "Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour" (Goyal et al., 2017) trained ResNet-50 to full accuracy at batch size 8,192 on 256 GPUs by applying a linear scaling rule — multiply the learning rate by the same factor as the batch — with a warmup period to survive the early steps where that rate would otherwise diverge. That single rule is what makes distributed training a throughput problem rather than an accuracy problem, and it is why data-parallel scaling works at all.

Outside deep learning, SGD is the default estimator for large linear models. scikit-learn's SGDClassifier and SGDRegressor exist specifically for datasets where a closed-form or full-batch solve will not fit in memory, and they fit logistic regression and linear SVMs on millions of rows in a single streaming pass. Matrix-factorization recommendation systems are trained the same way, one observed rating at a time. And gradient descent generalizes past parameters entirely: gradient boosting performs the identical downhill step in the space of functions, adding a new tree that points along the negative gradient instead of subtracting a number from a weight.

Key Concepts

• Learning rate η: the fraction of the gradient actually applied. It has a hard ceiling of 2/L set by the curvature, no useful floor, and no closed-form optimum outside quadratics — which is why it is the first hyperparameter anyone tunes and the one that wastes the most compute when wrong.
• Condition number κ = λ_max / λ_min: the ratio between the sharpest and flattest curvature directions. It, not the number of parameters, sets how many steps convergence takes — plain gradient descent needs on the order of κ iterations, momentum on the order of √κ.
• Momentum: accumulate a running average of past gradients and step along that instead. It cancels the oscillation across a narrow valley while the consistent component down the valley accumulates, which is the specific defect it was invented for (Polyak, 1964).
• Adaptive methods (Adam, AdamW): keep a per-parameter estimate of recent gradient magnitude and divide by it, giving every parameter its own effective step size. This exists because one global η must satisfy the sharpest direction in the entire model, which starves every flatter one.
• Saddle point: somewhere the gradient vanishes but the surface still curves upward in some directions and downward in others. In high dimensions these vastly outnumber local minima, and their surrounding plateaus are where training appears to stall.
• Convergence: not "the gradient reached zero" but "the gradient norm got small and the loss stopped improving enough to be worth more compute". In stochastic training the gradient never reaches zero — the noise floor is set by the batch size and the current learning rate.

Challenges

There is no L to look up. The convergence theory gives a clean answer, η < 2/L, for a quantity nobody can measure on a real network cheaply. In practice the ceiling is found by bisection — raise the rate until the loss diverges, back off, and add warmup so the early high-curvature phase survives. Every large training run budgets for this, and a mis-set rate is the single most common cause of a wasted run.

Ill-conditioning costs more than dimensionality does. Consider f(x, y) = x² + 100y², a two-dimensional bowl with curvature 2 in one direction and 200 in the other, so κ = 100. Stability is governed by the sharp direction: η must stay under 2/200 = 0.01, but progress along the flat direction is then governed by that same tiny rate. At the optimal η = 2/(λ_min + λ_max) ≈ 0.0099, each step multiplies the error by (κ−1)/(κ+1) = 99/101 ≈ 0.980, so reducing the distance to the minimum by 100× takes 231 iterations — for a problem with two variables and a known closed-form answer. Momentum with its optimal setting improves the rate to (√κ−1)/(√κ+1) = 9/11 ≈ 0.818, needing 23 steps instead. That 10× gap, exactly √κ, is the whole reason momentum and adaptive methods exist; real loss surfaces have condition numbers in the thousands.

Local minima are the wrong thing to worry about. The standard fear — gradient descent settles into a bad valley and stops — is mostly an artifact of drawing the loss surface in two dimensions. A critical point in a model with N parameters is a local minimum only if the curvature is positive in all N directions. If the signs behaved like independent coin flips, the odds of that at N = 10⁹ would be 2^(−10⁹); the real analysis is subtler but points the same way. Dauphin et al., "Identifying and attacking the saddle point problem in high-dimensional non-convex optimization" (NeurIPS 2014), argued from random matrix theory that critical points with high loss are overwhelmingly saddle points, and that the ones which genuinely are local minima have loss close to the global minimum. So the practical hazard is not being trapped somewhere terrible, it is crawling across the plateau around a saddle — and that is the failure the noise in mini-batch gradients happens to fix, by kicking the iterate off the flat spot.

Bigger batches stop helping, and then start hurting. Past a critical batch size the 1/√B return on accuracy no longer buys fewer steps, and the extra compute is simply wasted. Keskar et al., "On Large-Batch Training for Deep Learning" (ICLR 2017), showed the sharper problem: large-batch training converges to sharper minima and generalizes measurably worse than small-batch training on the same data and the same number of epochs. Gradient noise is functioning as regularization, and removing it costs test accuracy — the opposite of the intuition that a more accurate gradient must be better.

Nothing about the update rule knows about generalization. Gradient descent minimizes the training loss and only that. It will happily walk the parameters to a point that fits the training set perfectly and the test set poorly; overfitting is not a failure of the optimizer doing its job, it is the optimizer doing its job on the wrong objective.

Future Trends

The most useful recent movement is toward removing the learning rate schedule as a thing that has to be chosen in advance. Schedule-free and learning-rate-free methods aim to get cosine-decay-quality results without committing to a total step count up front — which matters because the standard schedule requires you to decide the length of the run before it starts, and a run cut short lands at a high learning rate having never annealed.

The second is transferring hyperparameters instead of re-tuning them. Maximal-update parameterization (μP) reparameterizes a network so that the optimal learning rate found on a small proxy model remains optimal at full width, letting a sweep be run on a model orders of magnitude cheaper than the one being trained. Given that a single frontier pretraining run cannot be tuned by trial and error, this is not an optimization nicety but a prerequisite, and it interacts directly with scaling laws.

The third is curvature. Second-order and matrix-aware optimizers — Shampoo, Muon and their descendants — attack the condition number directly rather than papering over it with per-parameter scaling, which is what the κ versus √κ arithmetic above says is available in principle. The obstacle is cost: any method that stores or inverts curvature information pays memory and compute that plain SGD does not, and whether the step-count saving beats that overhead is decided per workload, not in general.

Underneath all three, the theory is still catching up. Edge-of-stability behaviour means real training routinely violates the assumptions of the convergence proofs and works anyway, and understanding why remains open.

Code Example

The stability threshold made undeniable: five learning rates, one function, the same starting point.

def descend(eta, steps=5, x=1.0):
    """f(x) = x**2, so f'(x) = 2x and the update is x <- x * (1 - 2*eta)."""
    path = [x]
    for _ in range(steps):
        grad = 2 * x           # the gradient; backprop's job in a real model
        x = x - eta * grad     # the gradient DESCENT step; the whole algorithm
        path.append(x)
    return path

L = 2.0                        # f''(x) = 2 everywhere, so the ceiling is 2/L = 1.0
print(f"stability ceiling: eta < 2/L = {2 / L}\n")

for eta in (0.1, 0.5, 0.9, 1.0, 1.1):
    path = descend(eta)
    r = abs(1 - 2 * eta)
    verdict = "converges" if r < 1 else ("stalls" if r == 1 else "DIVERGES")
    print(f"eta={eta:<4} factor={1 - 2 * eta:+.1f}  "
          + "  ".join(f"{v:+.3f}" for v in path)
          + f"   loss={path[-1] ** 2:.4f}  {verdict}")

Output:

stability ceiling: eta < 2/L = 1.0

eta=0.1  factor=+0.8  +1.000  +0.800  +0.640  +0.512  +0.410  +0.328   loss=0.1074  converges
eta=0.5  factor=+0.0  +1.000  +0.000  +0.000  +0.000  +0.000  +0.000   loss=0.0000  converges
eta=0.9  factor=-0.8  +1.000  -0.800  +0.640  -0.512  +0.410  -0.328   loss=0.1074  converges
eta=1.0  factor=-1.0  +1.000  -1.000  +1.000  -1.000  +1.000  -1.000   loss=1.0000  stalls
eta=1.1  factor=-1.2  +1.000  -1.200  +1.440  -1.728  +2.074  -2.488   loss=6.1917  DIVERGES

Read the last column. η = 0.1 and η = 0.9 reach the same loss of 0.1074 after five steps — identical progress from step sizes nine times apart, because convergence depends on |1 − 2η| and not on η. η = 1.0 has taken five steps and gone nowhere, its loss unchanged at 1.0000 from where it started. η = 1.1, only 10% larger, has already made the loss six times worse and will keep multiplying it by 1.44 forever. Change nothing but the step size, and the same algorithm on the same function solves it exactly, solves it slowly, stalls permanently, or explodes.