Gradient Descent

Gradient descent is an iterative first-order optimization algorithm that minimizes a differentiable function by repeatedly stepping in the direction of the negative gradient. Key result: for a step size small enough, each iteration

x_{k + 1} = x_{k} - α \nabla f (x_{k})

decreases the function value, and for convex functions it converges to a global minimum. Where it applies: machine learning, deep neural networks, logistic/linear regression, numerical optimization, signal processing, and any large-scale problem where computing a Hessian is too expensive. Who/when: the method traces to Augustin-Louis Cauchy (1847), with modern stochastic and accelerated variants developed through the 20th and 21st centuries.

Gradient descent finds a local minimum of a differentiable function $f : R^{n} \to R$ by exploiting the fact that the gradient $\nabla f (x)$ points in the direction of steepest increase; moving in the opposite direction therefore decreases $f$ most rapidly (locally). At each step the algorithm updates the current estimate $x_{k}$ by a fraction $α$ (the learning rate or step size) of the negative gradient. It matters because it is the computational workhorse behind nearly all of modern machine learning: training a billion-parameter neural network is, at heart, gradient descent on a loss function. A surprising fact is that despite being a "greedy" local method that only ever looks one step ahead, on convex problems it provably reaches the global optimum, and even on the wildly non-convex landscapes of deep learning it reliably finds solutions that generalize well.

The Core Insight

The gradient $\nabla f (x)$ is the direction of fastest increase of $f$ at $x$ . Therefore $- \nabla f (x)$ is the direction of fastest decrease. By taking small steps "downhill" along $- \nabla f$ , we slide toward a minimum — just as a ball rolls down the steepest slope of a valley. The only tuning knob is how big a step to take: too small and we crawl; too large and we overshoot or diverge.

Formal Statement

Gradient Descent Iteration

Let $f : R^{n} \to R$ be differentiable. Starting from an initial point $x_{0} \in R^{n}$ , gradient descent generates a sequence ${x_{k}}$ by the update rule:

x_{k + 1} = x_{k} - α_{k} \nabla f (x_{k})

⟳subtract a multiple of the gradient because

- \nabla f

is the steepest-descent direction;

α_{k} > 0

scales how far to move.

where:

$x_{k} \in R^{n}$ is the iterate (current estimate of the minimizer) at step $k$ ,
$α_{k} > 0$ is the step size (learning rate); it may be constant ( $α_{k} = α$ ) or vary with $k$ ,
$\nabla f (x_{k}) = (\frac{\partial f}{\partial x _{1}}, \dots, \frac{\partial f}{\partial x _{n}})^{⊤}$ evaluated at $x_{k}$ is the gradient vector.

The iteration stops when a convergence criterion is met, e.g. $∥\nabla f (x_{k}) ∥ < ε$ for a small tolerance $ε$ .

The justification that $- \nabla f$ is "best" comes from the directional derivative. For a unit vector $u$ , the rate of change of $f$ at $x$ in direction $u$ is:

D_{u} f (x) = \nabla f (x) \cdot u = ∥\nabla f (x) ∥ cos θ

⟳the directional derivative is the dot product of the gradient with the direction; expand the dot product using the angle

θ

between them.

This is minimized (most negative) when $cos θ = - 1$ , i.e. when $u = - \nabla f (x) /∥\nabla f (x) ∥$ .

Descent Lemma and Convergence (L-smooth case)

Suppose $f$ is $L$ -smooth, meaning its gradient is Lipschitz continuous:

∥\nabla f (x) - \nabla f (y) ∥ \leq L ∥ x - y ∥ for all x, y .

⟳this is the definition of an

L

-Lipschitz gradient; it bounds how fast the gradient can change.

Then for the constant step size $α = 1/ L$ , the iterates satisfy the sufficient decrease property:

f (x_{k + 1}) \leq f (x_{k}) - \frac{1}{2 L} ∥\nabla f (x_{k}) ∥^{2} .

⟳apply the quadratic upper bound (descent lemma) at

x_{k + 1} = x_{k} - α \nabla f (x_{k})

and minimize the right side over

α

Consequently $f (x_{k})$ is monotonically non-increasing, and the gradients vanish: $min_{k \leq K} ∥\nabla f (x_{k}) ∥^{2} \to 0$ at rate $O (1/ K)$ . If, in addition, $f$ is convex, then $f (x_{k}) - f^{⋆} = O (1/ k)$ ; if $f$ is $μ$ -strongly convex, convergence is linear (geometric):

f (x_{k}) - f^{⋆} \leq (1 - \frac{μ}{L})^{k} (f (x_{0}) - f^{⋆}) .

⟳combine strong convexity (a lower quadratic bound) with the descent lemma to get a contraction factor

1 - μ / L

per step.

Why It Holds / Derivation

Descent Lemma → Sufficient Decrease

Step 1 — Quadratic upper bound. If

f

L

-smooth, then for any

x, y

f (y) \leq f (x) + \nabla f (x) \cdot (y - x) + \frac{L}{2} ∥ y - x ∥^{2} .

⟳integrate

\nabla f

along the segment from

x

y

, then bound the gradient difference using the Lipschitz condition

[3]

Step 2 — Substitute the update. Put

x = x_{k}

and

y = x_{k + 1} = x_{k} - α \nabla f (x_{k})

. Then

y - x = - α \nabla f (x_{k})

, and:

f (x_{k + 1}) \leq f (x_{k}) - α ∥\nabla f (x_{k}) ∥^{2} + \frac{L α ^{2}}{2} ∥\nabla f (x_{k}) ∥^{2} .

⟳plug

y - x = - α \nabla f (x_{k})

into

[6]

; the dot product

\nabla f (x_{k}) \cdot (- α \nabla f (x_{k})) = - α ∥\nabla f (x_{k}) ∥^{2}

Step 3 — Choose the step size. Collect the gradient-norm terms:

f (x_{k + 1}) \leq f (x_{k}) - α (1 - \frac{Lα}{2}) ∥\nabla f (x_{k}) ∥^{2} .

⟳factor

∥\nabla f (x_{k}) ∥^{2}

out of the last two terms of

[7]

The coefficient $α (1 - Lα /2)$ is positive for $0 < α < 2/ L$ and is maximized at $α = 1/ L$ , giving the factor $\frac{1}{2 L}$ and recovering $[4]$ . Whenever $\nabla f (x_{k}) \neq = 0$ , the function strictly decreases. $■$

Step 4 — Telescoping for the rate. Sum

[4]

over

k = 0, \dots, K - 1

k = 0 \sum K - 1 ∥\nabla f (x_{k}) ∥^{2} \leq 2 L (f (x_{0}) - f^{⋆}),

⟳rearrange

[4]

∥\nabla f (x_{k}) ∥^{2} \leq 2 L (f (x_{k}) - f (x_{k + 1}))

, then sum; the right side telescopes.

so the smallest gradient norm satisfies $min_{k} ∥\nabla f (x_{k}) ∥^{2} \leq \frac{2 L ( f ( x _{0} ) - f ^{⋆} )}{K}$ , the $O (1/ K)$ rate.

Augustin-Louis Cauchy | 1789–1857

The French mathematician Cauchy introduced the method of steepest descent in an 1847 note to the Académie des Sciences, "Méthode générale pour la résolution des systèmes d'équations simultanées." His motivation was astronomical: solving large systems of equations arising in orbit computations, where direct elimination was impractical. Cauchy proposed minimizing a sum of squares by repeatedly moving along the direction of greatest decrease — precisely $[1]$ . He worked without the modern vocabulary of vector calculus, but the geometric idea (follow the steepest slope) was fully present. The method lay relatively dormant until the rise of numerical computing in the mid-20th century revived it as the foundation of large-scale optimization.

Building Intuition

Imagine you are standing on a foggy mountainside and want to reach the valley bottom, but you can only see the ground directly at your feet. The sensible strategy: feel which way the slope goes down most steeply, take a step that way, and repeat. The gradient is your "feel for the slope," and the step size is your stride length.

Two things can go wrong. If your stride is tiny, you'll reach the valley eventually but it takes forever. If your stride is huge, you might leap clear across the valley and end up higher on the opposite slope, then leap back even higher — oscillating and diverging. The "just right" stride depends on how curved the terrain is (encoded by $L$ , the smoothness constant).

In a long, narrow valley (an ill-conditioned problem where the function is much steeper in one direction than another), gradient descent zig-zags inefficiently across the valley walls instead of running straight down its length. This is why conditioning — the ratio $L / μ$ — controls convergence speed in $[5]$ .

Gradient descent zig-zagging down an elliptical bowl toward the minimum

Worked Examples

Minimizing a 1-D quadratic by hand

Given:

f (x) = x^{2}

, so

f^{'} (x) = 2 x

. Use step size

α = 0.1

, start at

x_{0} = 5

. Update rule:

x_{k + 1} = x_{k} - α f^{'} (x_{k}) = x_{k} - 0.1 (2 x_{k}) = 0.8 x_{k}

. Steps:

$x_{0} = 5$
$x_{1} = 0.8 \times 5 = 4.0$
$x_{2} = 0.8 \times 4.0 = 3.2$
$x_{3} = 0.8 \times 3.2 = 2.56$
$x_{4} = 0.8 \times 2.56 = 2.048$
$⋮$
$x_{k} = 5 \times (0.8)^{k}$

Since $∣0.8∣ < 1$ , the sequence converges geometrically to the true minimizer.

x_{k} \to x^{⋆} = 0, f (x^{⋆}) = 0 (dimensionless)

Check the limit on $α$ : here

L = f^{''} = 2

, so we need

α < 2/ L = 1

. With

α = 0.1

we are safely inside, and the contraction factor is

∣1 - α L ∣ = ∣1 - 0.2∣ = 0.8

, matching the computation.

Linear regression via gradient descent — one step with numbers

Given: Fit

y = w x

to two data points

(x, y) = (1, 2)

and

(2, 5)

. Mean-squared loss:

J (w) = \frac{1}{2} i \sum (w x_{i} - y_{i})^{2} = \frac{1}{2} [(w \cdot 1 - 2)^{2} + (w \cdot 2 - 5)^{2}] .

Gradient:

J^{'} (w) = (w - 2) (1) + (2 w - 5) (2) = w - 2 + 4 w - 10 = 5 w - 12.

Start

w_{0} = 0

, step size

α = 0.1

. Step 1:

J^{'} (0) = 5 (0) - 12 = - 12

w_{1} = w_{0} - α J^{'} (w_{0}) = 0 - 0.1 (- 12) = 1.2.

Step 2:

J^{'} (1.2) = 5 (1.2) - 12 = - 6

w_{2} = 1.2 - 0.1 (- 6) = 1.8.

Step 3:

J^{'} (1.8) = 5 (1.8) - 12 = - 3

w_{3} = 1.8 - 0.1 (- 3) = 2.1.

Setting $J^{'} (w) = 0$ gives the exact least-squares solution $w^{⋆} = 12/5 = 2.4$ . The iterates $0, 1.2, 1.8, 2.1, 2.25, \dots$ climb steadily toward it.

w^{⋆} = 2.4 (slope, dimensionless); w_{3} = 2.1 after 3 steps

Note:

L = J^{''} = 5

, so the stable range is

α < 2/5 = 0.4

; our

α = 0.1

converges.

Common Misconceptions

Larger step size is NOT always faster

A bigger learning rate can speed early progress, but past the stability threshold $α < 2/ L$ the iteration diverges. In Example 1, taking $α = 1.5$ gives contraction factor $∣1 - α L ∣ = ∣1 - 3∣ = 2$ , so $∣ x_{k} ∣ = 5 \cdot 2^{k}$ blows up. Choosing $α$ is a genuine trade-off, not "the bigger the better." Practical schemes use line search, adaptive rates (Adam, AdaGrad), or learning-rate decay.

Gradient descent finds local, not global, minima

For a non-convex $f$ , gradient descent converges only to a stationary point ( $\nabla f = 0$ ), which may be a local minimum, a saddle point, or a plateau — not necessarily the global minimum. Convexity is what upgrades the guarantee from "local" to "global." Where the algorithm ends up depends on the starting point $x_{0}$ .

A non-convex function trapping gradient descent

Consider $f (x) = x^{4} - 4 x^{2} + x$ (a double-well shape). Its derivative $f^{'} (x) = 4 x^{3} - 8 x + 1$ has three roots; two are local minima of differing depth and one is a local maximum. Starting at $x_{0} = 1.8$ , gradient descent slides into the right well (the shallower local minimum near $x \approx 1.36$ ), never discovering the deeper left well near $x \approx - 1.45$ that is the true global minimum. No amount of tuning $α$ escapes this — only a different initialization (or a global method) reaches the global optimum. This illustrates why initialization and restarts matter in non-convex optimization.

Connections

Gradient descent is one node in a dense web of optimization ideas. It is the first-order cousin of Newton's Method, which additionally uses the Hessian Matrix to capture curvature and converges quadratically near the optimum (at the cost of inverting an $n \times n$ matrix each step). The directional-derivative justification in $[2]$ rests on the Gradient and Directional Derivative from multivariable calculus. The convergence guarantees rely on Convex Functions and the notion of Lipschitz Continuity. When the full gradient is too expensive, one replaces it with a noisy estimate to obtain Stochastic Gradient Descent, the engine of deep learning. Acceleration techniques connect it to Momentum Methods and Nesterov Acceleration, which improve the convex rate from $O (1/ k)$ to $O (1/ k^{2})$ . The continuous-time limit of gradient descent is the Gradient Flow ordinary differential equation $\overset{x}{˙} = - \nabla f (x)$ .

Real-World Applications

Training neural networks — Backpropagation computes gradients of a loss over millions of weights; (stochastic) gradient descent updates them. This underlies GPT-style language models, image classifiers (ResNet), and AlphaGo's policy networks.
Logistic & linear regression — Standard statistical models in econometrics, epidemiology, and credit scoring are routinely fit by gradient descent when datasets are too large for closed-form normal equations.
Recommender systems — Matrix-factorization models at Netflix and Amazon learn user/item latent factors by minimizing reconstruction error with SGD.
Inverse problems in imaging — CT/MRI reconstruction and seismic imaging minimize a data-fidelity-plus-regularization objective via (proximal) gradient methods.
Robotics & optimal control — Trajectory optimization and reinforcement-learning policy gradients descend a cost surface to plan motions.
Portfolio optimization — Large-scale convex risk-minimization in quantitative finance uses gradient and projected-gradient methods.
Natural-language and speech models — Transformers and recurrent networks for translation and transcription are trained almost exclusively with gradient-based optimizers (Adam, a gradient-descent descendant).

Historical Development

1847 — Augustin-Louis Cauchy publishes the method of steepest descent for solving systems of equations arising in astronomy.
1907 — Jacques Hadamard independently studies the steepest-descent approach in the context of integral approximation.
1944 — Haskell Curry analyzes the method of steepest descent for nonlinear minimization, providing convergence conditions.
1951 — Herbert Robbins and Sutton Monro introduce the stochastic approximation method, the theoretical seed of stochastic gradient descent.
1952 — Magnus Hestenes and Eduard Stiefel publish conjugate gradients, an acceleration over plain steepest descent for quadratic problems.
1964 — Boris Polyak introduces the heavy-ball (momentum) method, accelerating gradient descent.
1983 — Yurii Nesterov publishes his accelerated gradient method, achieving the optimal $O (1/ k^{2})$ rate for smooth convex functions.
1986 — Rumelhart, Hinton, and Williams popularize backpropagation, making gradient descent practical for multilayer neural networks.
2011–2015 — Adaptive learning-rate methods (AdaGrad 2011, RMSProp 2012, Adam 2014/15) become the de-facto optimizers for deep learning.

Subtleties & Limits

Several deep questions remain active research:

Why does SGD generalize? In over-parameterized deep networks the loss surface has infinitely many global minima of zero training error, yet SGD tends to find ones that generalize well to unseen data. The precise mechanism (implicit regularization, flat-minima preference) is not fully understood.
Saddle points vs. minima. High-dimensional non-convex landscapes are dominated by saddle points rather than poor local minima. How quickly (and reliably) does gradient descent — possibly with noise — escape saddles? Sharp characterizations are still being developed.
Optimal step-size schedules. The theoretically optimal learning-rate schedule for non-convex problems is unknown; practitioners rely on heuristics (warmup, cosine decay).
Lower bounds and acceleration limits. Nesterov's $O (1/ k^{2})$ is optimal for first-order methods on smooth convex functions, but the landscape of optimal rates under different assumptions (non-smooth, stochastic, distributed) is incompletely mapped.