Gradient Descent

⚡ Key Takeaways

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 - \alpha \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.

💡 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.

DefinitionGradient Descent Iteration

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

1

\quad x_{k+1} = x_k - \alpha_k \,\nabla f(x_k)

Derivation hint: subtract a multiple of the gradient because $-\nabla f$ is the steepest-descent direction; $\alpha_k > 0$ scales how far to move. where:

$x_k \in \mathbb{R}^n$ is the iterate (current estimate of the minimizer) at step $k$ ,
$\alpha_k > 0$ is the step size (learning rate); it may be constant ( $\alpha_k = \alpha$ ) or vary with $k$ ,
$\nabla f(x_k) = \left(\dfrac{\partial f}{\partial x_1}, \dots, \dfrac{\partial f}{\partial x_n}\right)^\top$ evaluated at $x_k$ is the gradient vector.

The iteration stops when a convergence criterion is met, e.g. $\|\nabla f(x_k)\| < \varepsilon$ for a small tolerance $\varepsilon$ .

TheoremDescent Lemma and Convergence (L-smooth case)

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

3

\quad \|\nabla f(x) - \nabla f(y)\| \le L\,\|x - y\| \quad \text{for all } x,y.

Derivation hint: this is the definition of an $L$ -Lipschitz gradient; it bounds how fast the gradient can change. Then for the constant step size $\alpha = 1/L$ , the iterates satisfy the sufficient decrease property:

4

\quad f(x_{k+1}) \le f(x_k) - \frac{1}{2L}\,\|\nabla f(x_k)\|^2.

Derivation hint: apply the quadratic upper bound (descent lemma) at $x_{k+1}=x_k-\alpha\nabla f(x_k)$ and minimize the right side over $\alpha$ . Consequently $f(x_k)$ is monotonically non-increasing, and the gradients vanish: $\min_{k \le K} \|\nabla f(x_k)\|^2 \to 0$ at rate $O(1/K)$ . If, in addition, $f$ is convex, then $f(x_k) - f^\star = O(1/k)$ ; if $f$ is $\mu$ -strongly convex, convergence is linear (geometric):

5

\quad f(x_k) - f^\star \le \left(1 - \tfrac{\mu}{L}\right)^k \big(f(x_0) - f^\star\big).

Derivation hint: combine strong convexity (a lower quadratic bound) with the descent lemma to get a contraction factor $1-\mu/L$ per step.

ProofDescent Lemma → Sufficient Decrease

Step 1 — Quadratic upper bound. If $f$ is $L$ -smooth, then for any $x, y$ :

6

\quad f(y) \le f(x) + \nabla f(x)\cdot(y-x) + \frac{L}{2}\|y - x\|^2.

Derivation hint: integrate $\nabla f$ along the segment from $x$ to $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 - \alpha\nabla f(x_k)$ . Then $y - x = -\alpha\nabla f(x_k)$ , and:

7

\quad f(x_{k+1}) \le f(x_k) - \alpha\|\nabla f(x_k)\|^2 + \frac{L\alpha^2}{2}\|\nabla f(x_k)\|^2.

Derivation hint: plug $y-x=-\alpha\nabla f(x_k)$ into $[6]$ ; the dot product $\nabla f(x_k)\cdot(-\alpha\nabla f(x_k))=-\alpha\|\nabla f(x_k)\|^2$ .

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

8

\quad f(x_{k+1}) \le f(x_k) - \alpha\left(1 - \frac{L\alpha}{2}\right)\|\nabla f(x_k)\|^2.

Derivation hint: factor $\|\nabla f(x_k)\|^2$ out of the last two terms of $[7]$ . The coefficient $\alpha(1 - L\alpha/2)$ is positive for $0 < \alpha < 2/L$ and is maximized at $\alpha = 1/L$ , giving the factor $\tfrac{1}{2L}$ and recovering $[4]$ . Whenever $\nabla f(x_k) \ne 0$ , the function strictly decreases. $\blacksquare$

Step 4 — Telescoping for the rate. Sum $[4]$ over $k = 0,\dots,K-1$ :

9

\quad \sum_{k=0}^{K-1} \|\nabla f(x_k)\|^2 \le 2L\big(f(x_0) - f^\star\big),

Derivation hint: rearrange $[4]$ to $\|\nabla f(x_k)\|^2 \le 2L(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 \le \frac{2L(f(x_0)-f^\star)}{K}$ , the $O(1/K)$ rate.

∎

AC

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.

🧠 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/\mu$ — controls convergence speed in $[5]$ .

Figure

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

ExampleMinimizing a 1-D quadratic by hand

Given: $f(x) = x^2$ , so $f'(x) = 2x$ . Use step size $\alpha = 0.1$ , start at $x_0 = 5$ .

Update rule: $x_{k+1} = x_k - \alpha f'(x_k) = x_k - 0.1(2x_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$
$\vdots$
$x_k = 5 \times (0.8)^k$

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

\boxed{x_k \to x^\star = 0,\quad f(x^\star) = 0 \ \text{(dimensionless)}}

Check the limit on $\alpha$ : here $L = f'' = 2$ , so we need $\alpha < 2/L = 1$ . With $\alpha = 0.1$ we are safely inside, and the contraction factor is $|1 - \alpha L| = |1 - 0.2| = 0.8$ , matching the computation.

ExampleLinear regression via gradient descent — one step with numbers

Given: Fit $y = wx$ to two data points $(x,y) = (1, 2)$ and $(2, 5)$ . Mean-squared loss:

J(w) = \tfrac{1}{2}\sum_{i}(wx_i - y_i)^2 = \tfrac12\big[(w\cdot1 - 2)^2 + (w\cdot2 - 5)^2\big].

Gradient:

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

Start $w_0 = 0$ , step size $\alpha = 0.1$ .

Step 1: $J'(0) = 5(0) - 12 = -12$ .

w_1 = w_0 - \alpha 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^\star = 12/5 = 2.4$ . The iterates $0, 1.2, 1.8, 2.1, 2.25, \dots$ climb steadily toward it.

\boxed{w^\star = 2.4 \ \text{(slope, dimensionless)};\quad w_3 = 2.1 \text{ after 3 steps}}

Note: $L = J'' = 5$ , so the stable range is $\alpha < 2/5 = 0.4$ ; our $\alpha = 0.1$ converges.

⚠️ Larger step size is NOT always faster

A bigger learning rate can speed early progress, but past the stability threshold $\alpha < 2/L$ the iteration diverges. In Example 1, taking $\alpha = 1.5$ gives contraction factor $|1 - \alpha L| = |1 - 3| = 2$ , so $|x_k| = 5\cdot 2^k$ blows up. Choosing $\alpha$ 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$ .

CounterexampleA non-convex function trapping gradient descent

Consider $f(x) = x^4 - 4x^2 + x$ (a double-well shape). Its derivative $f'(x) = 4x^3 - 8x + 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 $\alpha$ 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.

connection

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 $\dot{x} = -\nabla f(x)$ .

🔬 Where this appears

⏳ History

- 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.

open-problem

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.

Formal Statement

Why It Holds / Derivation

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also