Gradient Descent

in progressThis lesson is still being built - content, demos, and checkpoints may change before release.

Gradient descent

Loading interactive demo…

A ball on a bowl, seen from above. Each iteration measures the height and the slope where the ball stands, then steps against the slope scaled by the learning rate. The run halts when the slope is nearly flat or the height has blown up. Take the tour, or press and explore. Legend:

The panel beside the stage is the real GradientDescent class from the published library executing in your browser, with the current line highlighted.

Contour rings of the bowl, each one a constant height.
The path so far, with the finished path faint ahead of it.
The ball; green once converged, red once diverged.
The start ring and, while the slope is on show, the proposed step.

loss is the height at the current position, slope the magnitude of the gradient, steps how many of the budget are taken, status whether the last step went down or up. The strip below the plot is the loss over the run. Drag the ring to move the start.

The code panel shows bare executable code by default. The bar above it names the file (hover the name for the full published path); options holds the toggles: comments, the tracer instrumentation that produces this visualization, and verbose names for the terse identifiers (display only: the default is the byte-exact published file). The view switch adds plain-English narration: both interleaves it with the code, pseudo shows only the pseudocode. hide code collapses the panel; the rail it leaves behind brings it back.

Keys: Space play/pause · ←/→ step · Home/End jump · R reset · F fullscreen · G guided tour

The rule. From a position $p_k$ , one iteration is

p_{k+1} = p_k - \eta\, \nabla f(p_k),

where $\nabla f$ is the gradient, the vector of partial derivatives, and $\eta$ the learning rate. The gradient points uphill and its length is the steepness, so the step goes downhill, further where it is steeper.

This bowl. The stage minimises $f(x, y) = \tfrac12 (a x^2 + b y^2)$ with $a = 1$ and $b$ the curvature chip, so $\nabla f = (a x, b y)$ and one step multiplies each coordinate by a constant:

x_{k+1} = (1 - \eta a)\, x_k, \qquad y_{k+1} = (1 - \eta b)\, y_k.

Every claim about the rate is now a claim about a factor. With $|1 - \eta b| < 1$ the $y$ coordinate shrinks; at $\eta = 1/b$ it lands on the axis in one step; at $\eta = 2/b$ the factor is $-1$ and $y$ flips sign forever without shrinking; past that it grows and the run diverges. The descent converges exactly when

\eta < \frac{2}{\max(a, b)},

so the steepest axis sets the ceiling on the rate.

Zigzag. Meanwhile the flat axis shrinks by $1 - \eta a$ , close to 1 when $\eta$ is small enough for the steep axis. The ratio $b / a$ is the condition number of the bowl: a large one means the rate that is safe along $y$ is a crawl along $x$ , and the path zigzags across the valley before creeping along it. That is why the narrow bowl takes the whole budget. Edge cases: a start exactly at the bottom halts at once; the halt on a flat slope can miss a run that is still creeping along the flat axis, and the budget ends it instead.

Choices worth reading closely in the implementation (the code panel's comments and tracer checkboxes reveal the full published file):

The objective is an interface, a height and a slope at every point, so the same descent runs on any bowl; QuadraticBowl is one instance whose slope is a product per axis.
Loss and gradient are emitted before the halt test, so a run that halts still shows where it stood and how steep it was, and the halt carries the reason: a flat slope or a blown-up loss.
The step is p - rate * g, nothing more. No momentum, no memory: each iteration reads only the current point, which is what makes the per-axis factor rule exact.
The path keeps the start, so it has one more entry than the steps taken, and the losses match it one to one unless the run halted, in which case the last position was never stepped from.
A non-positive rate is rejected rather than climbing silently.

The idea is older than the computer: if you can measure how a quantity changes with each input, the steepest way down is the negative of those changes, so step that way and measure again. Cauchy suggested it in 1847; Hadamard found it independently sixty years later; Curry worked out when it converges in 1944. It became the workhorse of machine learning because a network's loss is exactly such a quantity, and its gradient can be computed for millions of weights at once. Every training method today is this loop with refinements.

1847Augustin-Louis Cauchy - First suggests descending along the negative gradient, the method this stage runs step by step.source
1907Jacques Hadamard - Independently proposes a similar method.source
1944Haskell Curry - First studies the method's convergence for non-linear problems: when the steps actually reach the bottom.source
1951Herbert Robbins and Sutton Monro - Introduce the earliest stochastic approximation methods, the ancestor of stochastic gradient descent, which steps on noisy estimates of the slope.source
1980sYurii Nesterov - Modifies the momentum method to use the gradient predicted at the next point; Nesterov accelerated gradient reaches machine learning in the 2010s.source
2014Adam is published, applying RMSProp's adaptive per-parameter rates to momentum; the default optimizer of most deep learning code since.source

Used today

Training neural networks - Backpropagation computes the gradient of the loss with respect to every weight; this loop is what then moves the weights.
Fitting curves - Least squares, logistic regression, and most model fitting minimise a loss by exactly this loop when no closed form exists.
Engineering and physics - Minimising an energy or a cost over many parameters, from circuit layout to protein folding, is a gradient descent with a different bowl.

rate0.20

bowl

budget20

loss: 0.000
slope: 0.023
steps: 20 of 20
status: descending

gradient-descent.ts

import type { Tracer } from "../trace";/** Something with a height and a slope at every point. */export interface Differentiable {  value(point: readonly number[]): number;  gradient(point: readonly number[]): number[];}/** * The bowl f(p) = ½ Σ aᵢ pᵢ²: a different curvature per axis, so the * minimum is at the origin and every descent step is a plain product * per axis (pᵢ becomes (1 − η aᵢ) pᵢ). Closed form makes every claim * about the rate checkable by hand. */export class QuadraticBowl implements Differentiable {  constructor(readonly curvatures: readonly number[]) {    if (curvatures.length === 0 || curvatures.some((a) => !(a > 0)))      throw new RangeError("every curvature must be positive");  }  value(point: readonly number[]): number {    let sum = 0;    for (let i = 0; i < this.curvatures.length; i++)      sum += this.curvatures[i]! * (point[i] ?? 0) ** 2;    return sum / 2;  }  gradient(point: readonly number[]): number[] {    return this.curvatures.map((a, i) => a * (point[i] ?? 0));  }}export type HaltReason = "converged" | "diverged";export interface DescentResult {  /** Every position visited, the start first. */  path: number[][];  /** The height at each position of the path. */  losses: number[];  halted: HaltReason | null;  /** Steps actually taken. */  iterations: number;}/** * Gradient descent: from a start, repeat "measure the slope, step * against it" with a fixed learning rate. The slope points uphill, so * p ← p − η ∇f(p) walks down; too small a rate crawls, too large a rate * overshoots and climbs. Halts early when the slope is nearly flat or * the loss has blown up. * * Time: O(k) gradient evaluations for k iterations. Space: O(k) for the path. */export class GradientDescent {  constructor(    readonly objective: Differentiable,    readonly learningRate: number,    private readonly tracer?: Tracer,  ) {    if (!(learningRate > 0)) throw new RangeError("the learning rate must be positive");  }  run(start: readonly number[], iterations: number, tolerance = 1e-4, blowUp = 1e6): DescentResult {    if (!Number.isInteger(iterations) || iterations < 0) throw new RangeError("iterations must be a whole number");    let p = [...start];    let position = [...start];    const path = [p];    const path = [position];    const losses: number[] = [];    let halted: HaltReason | null = null;    let iteration = 0;    for (; iteration < iterations; iteration++) {      const loss = this.objective.value(p);      const loss = this.objective.value(position);      losses.push(loss);      // ▸ measure how high the bowl is here      this.tracer?.emit("loss", { iteration, position: [...p], loss });      this.tracer?.emit("loss", { iteration, position: [...position], loss });      const g = this.objective.gradient(p);      const slope = this.objective.gradient(position);      const norm = Math.hypot(...g);      const norm = Math.hypot(...slope);      // ▸ measure which way is uphill, and how steep      this.tracer?.emit("gradient", { iteration, gradient: [...g], norm });      this.tracer?.emit("gradient", { iteration, gradient: [...slope], norm });      if (norm < tolerance || loss > blowUp) {        halted = norm < tolerance ? "converged" : "diverged";        // ▸ flat enough to stop, or so high the run has blown up        this.tracer?.emit("halt", { iteration, reason: halted, loss });        break;      }      const to = p.map((x, i) => x - this.learningRate * g[i]!);      const nextPosition = position.map((x, i) => x - this.learningRate * slope[i]!);      const stepSize = Math.hypot(...to.map((x, i) => x - p[i]!));      const stepSize = Math.hypot(...nextPosition.map((x, i) => x - position[i]!));      // ▸ walk against the slope, scaled by the learning rate      this.tracer?.emit("step", { iteration, from: [...p], to: [...to], stepSize });      this.tracer?.emit("step", { iteration, from: [...position], nextPosition: [...nextPosition], stepSize });      p = to;      position = nextPosition;      path.push(p);      path.push(position);    }    if (halted === null) losses.push(this.objective.value(p));    if (halted === null) losses.push(this.objective.value(position));    return { path, losses, halted, iterations: path.length - 1 };  }}

loss =: 0.000

20 steps taken; the budget ran out with the loss at 0.000.

import type { Tracer } from "../trace";/** Something with a height and a slope at every point. */export interface Differentiable { value(point: readonly number[]): number; gradient(point: readonly number[]): number[];}/** * The bowl f(p) = ½ Σ aᵢ pᵢ²: a different curvature per axis, so the * minimum is at the origin and every descent step is a plain product * per axis (pᵢ becomes (1 − η aᵢ) pᵢ). Closed form makes every claim * about the rate checkable by hand. */export class QuadraticBowl implements Differentiable { constructor(readonly curvatures: readonly number[]) { if (curvatures.length === 0 || curvatures.some((a) => !(a > 0))) throw new RangeError("every curvature must be positive"); } value(point: readonly number[]): number { let sum = 0; for (let i = 0; i < this.curvatures.length; i++) sum += this.curvatures[i]! * (point[i] ?? 0) ** 2; return sum / 2; } gradient(point: readonly number[]): number[] { return this.curvatures.map((a, i) => a * (point[i] ?? 0)); }}export type HaltReason = "converged" | "diverged";export interface DescentResult { /** Every position visited, the start first. */ path: number[][]; /** The height at each position of the path. */ losses: number[]; halted: HaltReason | null; /** Steps actually taken. */ iterations: number;}/** * Gradient descent: from a start, repeat "measure the slope, step * against it" with a fixed learning rate. The slope points uphill, so * p ← p − η ∇f(p) walks down; too small a rate crawls, too large a rate * overshoots and climbs. Halts early when the slope is nearly flat or * the loss has blown up. * * Time: O(k) gradient evaluations for k iterations. Space: O(k) for the path. */export class GradientDescent { constructor( readonly objective: Differentiable, readonly learningRate: number, private readonly tracer?: Tracer, ) { if (!(learningRate > 0)) throw new RangeError("the learning rate must be positive"); } run(start: readonly number[], iterations: number, tolerance = 1e-4, blowUp = 1e6): DescentResult { if (!Number.isInteger(iterations) || iterations < 0) throw new RangeError("iterations must be a whole number"); let p = [...start]; let position = [...start]; const path = [p]; const path = [position]; const losses: number[] = []; let halted: HaltReason | null = null; let iteration = 0; for (; iteration < iterations; iteration++) { const loss = this.objective.value(p); const loss = this.objective.value(position); losses.push(loss); // ▸ measure how high the bowl is here this.tracer?.emit("loss", { iteration, position: [...p], loss }); this.tracer?.emit("loss", { iteration, position: [...position], loss }); const g = this.objective.gradient(p); const slope = this.objective.gradient(position); const norm = Math.hypot(...g); const norm = Math.hypot(...slope); // ▸ measure which way is uphill, and how steep this.tracer?.emit("gradient", { iteration, gradient: [...g], norm }); this.tracer?.emit("gradient", { iteration, gradient: [...slope], norm }); if (norm < tolerance || loss > blowUp) { halted = norm < tolerance ? "converged" : "diverged"; // ▸ flat enough to stop, or so high the run has blown up this.tracer?.emit("halt", { iteration, reason: halted, loss }); break; } const to = p.map((x, i) => x - this.learningRate * g[i]!); const nextPosition = position.map((x, i) => x - this.learningRate * slope[i]!); const stepSize = Math.hypot(...to.map((x, i) => x - p[i]!)); const stepSize = Math.hypot(...nextPosition.map((x, i) => x - position[i]!)); // ▸ walk against the slope, scaled by the learning rate this.tracer?.emit("step", { iteration, from: [...p], to: [...to], stepSize }); this.tracer?.emit("step", { iteration, from: [...position], nextPosition: [...nextPosition], stepSize }); p = to; position = nextPosition; path.push(p); path.push(position); } if (halted === null) losses.push(this.objective.value(p)); if (halted === null) losses.push(this.objective.value(position)); return { path, losses, halted, iterations: path.length - 1 }; }}