Optimization Methods: Gradient Descent and Variants

⚡ Key Takeaways

Gradient descent is a first-order iterative algorithm that minimizes a differentiable function by repeatedly stepping in the direction of steepest decrease, $-\nabla f$ . Key result: for a convex function with Lipschitz-continuous gradient, gradient descent with a suitable step size converges to the global minimum at rate $O(1/k)$ . Where it applies: machine learning (neural network training), statistics (logistic/linear regression), control theory, and any large-scale continuous optimization. Who/when: introduced by Augustin-Louis Cauchy (1847); modern variants (momentum, Adam) developed 1964–2015.

💡 The Core Insight

A differentiable function locally looks like a tilted plane. The gradient $\nabla f(x)$ points in the direction of steepest ascent; therefore $-\nabla f(x)$ points downhill most steeply. By taking small steps downhill and re-measuring the slope each time, we "flow" toward a minimum — like a marble rolling on a landscape, except we move in discrete jumps whose length we control through $\eta$ .

DefinitionGradient and Descent Direction

For $f : \mathbb{R}^n \to \mathbb{R}$ differentiable, the gradient is the vector of partial derivatives:

1

\quad \nabla f(x) = \left( \frac{\partial f}{\partial x_1}, \frac{\partial f}{\partial x_2}, \dots, \frac{\partial f}{\partial x_n} \right)^{\!\top}

Derivation hint: The gradient is defined so that the directional derivative satisfies $D_u f(x) = \nabla f(x)^\top u$ ; stack the partials measured along each coordinate axis $e_i$ . A vector $d$ is a descent direction at $x$ if $\nabla f(x)^\top d < 0$ , guaranteeing $f$ decreases along $d$ for small steps.

DefinitionThe Gradient Descent Iteration

Given an initial point $x_0$ and step sizes $\eta_k > 0$ , gradient descent produces:

2

\quad x_{k+1} = x_k - \eta_k \, \nabla f(x_k), \qquad k = 0, 1, 2, \dots

Derivation hint: Choose the descent direction $d = -\nabla f(x)$ , which minimizes the linear (first-order Taylor) approximation $f(x) + \nabla f(x)^\top d$ subject to $\|d\|_2 = 1$ by Cauchy–Schwarz. Here $\eta_k$ may be fixed ( $\eta_k = \eta$ ), diminishing ( $\eta_k \to 0$ with $\sum \eta_k = \infty$ ), or chosen by line search.

DefinitionSteepest-Descent Property

The negative gradient is the steepest descent direction in the Euclidean norm. Among all unit vectors $d$ :

3

\quad \arg\min_{\|d\|_2 = 1} \nabla f(x)^\top d = -\frac{\nabla f(x)}{\|\nabla f(x)\|_2}

Derivation hint: Apply Cauchy–Schwarz, $\nabla f(x)^\top d \ge -\|\nabla f(x)\|_2\|d\|_2$ , with equality iff $d$ is anti-parallel to $\nabla f(x)$ .

TheoremConvergence for L-Smooth Convex Functions

Let $f$ be convex and L-smooth, meaning $\|\nabla f(x) - \nabla f(y)\|_2 \le L\|x - y\|_2$ for all $x,y$ . With fixed step size $\eta = 1/L$ , gradient descent satisfies:

4

\quad f(x_k) - f(x^\star) \le \frac{\|x_0 - x^\star\|_2^2}{2\eta k} = \frac{L\,\|x_0 - x^\star\|_2^2}{2k}

Derivation hint: Combine the descent lemma $f(x_{k+1}) \le f(x_k) - \tfrac{\eta}{2}\|\nabla f(x_k)\|^2$ with convexity $f(x_k) - f(x^\star) \le \nabla f(x_k)^\top(x_k - x^\star)$ , then telescope the bound on $\|x_k - x^\star\|^2$ . If additionally $f$ is $\mu$ -strongly convex ( $\mu > 0$ ), convergence is linear (geometric):

5

\quad \|x_k - x^\star\|_2^2 \le \left(1 - \frac{\mu}{L}\right)^{k} \|x_0 - x^\star\|_2^2

Derivation hint: Show the gradient step is a contraction; expand $\|x_{k+1}-x^\star\|^2$ and use co-coercivity of $\nabla f$ together with strong convexity to bound the inner-product term.

ProofDescent Lemma and O(1/k) Rate

Step 1 — Quadratic upper bound (descent lemma). L-smoothness implies, by integrating the gradient along the segment from $x$ to $y$ :

6

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

Derivation hint: Write $f(y) - f(x) = \int_0^1 \nabla f(x + t(y-x))^\top(y-x)\,dt$ , add and subtract $\nabla f(x)^\top(y-x)$ , and bound the remainder using the Lipschitz property.

Step 2 — Guaranteed decrease. Substitute $y = x_{k+1} = x_k - \eta\nabla f(x_k)$ into [6] with $\eta = 1/L$ :

7

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

Derivation hint: Plug $y - x = -\eta\nabla f(x_k)$ into [6], collect the $\|\nabla f\|^2$ terms; the choice $\eta = 1/L$ makes the coefficient $-\tfrac{1}{2L}$ .

Step 3 — Bound progress toward optimum. Expand the squared distance:

8

\quad \|x_{k+1} - x^\star\|_2^2 = \|x_k - x^\star\|_2^2 - 2\eta\,\nabla f(x_k)^\top(x_k - x^\star) + \eta^2\|\nabla f(x_k)\|_2^2

Derivation hint: Substitute $x_{k+1} = x_k - \eta\nabla f(x_k)$ and expand the binomial $\|a - b\|^2 = \|a\|^2 - 2a^\top b + \|b\|^2$ .

Step 4 — Apply convexity. Using $\nabla f(x_k)^\top(x_k - x^\star) \ge f(x_k) - f(x^\star)$ and [7], one shows the per-step decrease in function value telescopes. Summing over $j = 0, \dots, k-1$ and using monotonicity of $f(x_j)$ yields the averaged bound, then convexity collapses it to [4]. $\blacksquare$

∎

mathematician · Augustin-Louis Cauchy | 1789–1857

The French mathematician Cauchy introduced the method of steepest descent in an 1847 note to the Comptes Rendus, "Méthode générale pour la résolution des systèmes d'équations simultanées." His motivation was astronomical: solving systems of nonlinear equations arising in orbit computations. Cauchy proposed minimizing the sum of squared residuals by repeatedly moving in the direction that most rapidly decreased it — the negative gradient. Though he lacked the modern convergence theory (and computers to exploit it), his insight that a local linear approximation dictates the best search direction remains the conceptual seed of every first-order method used today.

🧠 Intuition

Imagine you are blindfolded on a hillside in dense fog and want to reach the valley. You cannot see the destination, but you can feel the slope under your feet. The strategy: feel which way is steepest downhill, take a step that way, then re-feel and repeat. The step size $\eta$ is your stride length. Too small, and you inch along forever (slow convergence). Too large, and you overshoot the valley, perhaps bouncing up the opposite slope or diverging entirely. The valley floor — where the ground is flat in every direction — is where $\nabla f = 0$ , a stationary point. For a single convex valley this is the global minimum; for a rugged landscape (non-convex $f$ ) you may settle into a local valley or pause on a flat saddle.

Figure

Gradient descent trajectory on contour lines of a convex quadratic. Steps follow the negative gradient, perpendicular to contours, zig-zagging toward the minimum.

ExampleQuadratic in One Variable

Given: Minimize $f(x) = \tfrac{1}{2}(x - 3)^2$ starting from $x_0 = 0$ with fixed $\eta = 0.5$ .

Step 1 — Gradient. $\nabla f(x) = f'(x) = x - 3$ .

Step 2 — Iterate using $x_{k+1} = x_k - \eta(x_k - 3) = x_k - 0.5(x_k - 3)$ :

$x_1 = 0 - 0.5(0 - 3) = 1.5$
$x_2 = 1.5 - 0.5(1.5 - 3) = 1.5 + 0.75 = 2.25$
$x_3 = 2.25 - 0.5(2.25 - 3) = 2.25 + 0.375 = 2.625$
$x_4 = 2.8125$ , $x_5 = 2.90625, \dots$

Step 3 — Closed form. The error obeys $x_{k+1} - 3 = (1 - \eta)(x_k - 3) = 0.5(x_k - 3)$ , so $x_k - 3 = (0.5)^k(0 - 3) = -3(0.5)^k$ . Here $L = 1$ (since $f'' = 1$ ) and $\eta = 0.5 < 2/L = 2$ , so convergence is geometric.

\boxed{x_k = 3 - 3(0.5)^k \;\to\; x^\star = 3 \text{ (dimensionless units)}}

ExampleTwo-Variable Quadratic with Conditioning

Given: Minimize $f(x,y) = \tfrac{1}{2}(10x^2 + y^2)$ , starting from $(x_0,y_0) = (1,1)$ , $\eta = 0.1$ .

Step 1 — Gradient. $\nabla f = (10x,\; y)^\top$ . The Hessian is $\mathrm{diag}(10, 1)$ , so $L = 10$ , $\mu = 1$ , condition number $\kappa = L/\mu = 10$ .

Step 2 — Decoupled updates (the two coordinates evolve independently):

$x_{k+1} = x_k - 0.1(10 x_k) = x_k(1 - 1) = 0$ — so $x$ reaches $0$ in one step.
$y_{k+1} = y_k - 0.1(y_k) = 0.9\, y_k$ — so $y_k = (0.9)^k$ , decaying slowly.

Step 3 — Observe the imbalance. After 1 step: $(0, 0.9)$ . After 10 steps: $(0, 0.349)$ . After 50: $(0, 0.0052)$ . The poorly-scaled $y$ -direction limits overall speed — illustrating that the condition number $\kappa$ governs convergence per [5]: rate factor $\approx (1 - \mu/L) = 0.9$ .

\boxed{(x_k, y_k) = \big(0,\; (0.9)^k\big) \to (0,0); \text{ slow due to } \kappa = 10}

⚠️ Common mistake

A larger step size is not always faster. If $\eta > 2/L$ , gradient descent on a convex quadratic diverges — the iterates oscillate with growing amplitude. The safe range for a fixed step on an $L$ -smooth convex function is $0 < \eta < 2/L$ , with $\eta = 1/L$ optimal for the $O(1/k)$ guarantee. Practitioners who "crank up the learning rate" to speed training often trigger instability or NaNs.

⚠️ Common mistake

$\nabla f = 0$ does not mean you have found a minimum. A zero gradient identifies any stationary point: a minimum, maximum, or saddle. In high-dimensional non-convex problems, saddle points vastly outnumber local minima, and naive GD can crawl very slowly near them. Verifying a minimum requires second-order information (a positive-semidefinite Hessian).

Counterexample

GD can fail to converge with a constant step on a non-smooth function. Consider $f(x) = |x|$ , which is convex but not differentiable at $0$ and has no finite Lipschitz constant for its (sub)gradient slope behavior near the kink. With $\eta$ fixed and $x_k$ near $0$ , the subgradient is $\pm 1$ , so the iterate jumps by $\pm\eta$ and oscillates forever around $0$ in steps of size $\eta$ , never settling. The remedy is a diminishing step size $\eta_k \to 0$ with $\sum\eta_k = \infty$ , which the standard $O(1/L)$ smooth theory does not cover — this is the domain of Subgradient Methods.

connection

Gradient descent sits at the center of a web of methods. Replacing the full gradient by a noisy estimate from a data minibatch gives Stochastic Gradient Descent, the workhorse of deep learning. Incorporating a velocity term yields Momentum Methods and Nesterov acceleration, improving the rate from $O(1/k)$ to $O(1/k^2)$ for smooth convex problems. Using the Hessian to rescale steps connects to Newton's Method and quasi-Newton (BFGS) methods, trading per-step cost for fewer iterations. The choice of geometry/norm in the steepest-descent definition [3] generalizes to Mirror Descent and the natural gradient. Finally, the convergence analysis rests squarely on Convex Analysis and the notion of Lipschitz Continuity of the gradient.

🔬 Where this appears

⏳ History

- 1847 — Augustin-Louis Cauchy proposes the method of steepest descent for solving simultaneous equations in celestial mechanics.

- 1907 — Jacques Hadamard independently studies gradient flows and the continuous-time descent dynamics

\dot x = -\nabla f(x)

.

- 1944 — Haskell Curry analyzes the method of steepest descent rigorously, establishing step-size conditions for convergence.

- 1951 — Herbert Robbins and Sutton Monro introduce stochastic approximation, the theoretical foundation of Stochastic Gradient Descent.

- 1964 — Boris Polyak introduces the heavy-ball (momentum) method, accelerating convergence on ill-conditioned problems.

- 1983 — Yurii Nesterov publishes accelerated gradient descent, 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 — Duchi, Hazan, and Singer introduce AdaGrad, the first widely used adaptive per-coordinate learning rate.

- 2015 — Kingma and Ba introduce Adam, combining momentum and adaptive rates; it becomes the default optimizer for deep learning.

open-problem

For non-convex objectives — the regime of essentially all modern deep learning — gradient descent comes with no guarantee of reaching a global minimum, yet it works astonishingly well in practice. Why? Several deep questions remain only partially answered: (1) the loss landscape geometry of overparameterized networks appears to have many connected, nearly-global minima and few "bad" local minima, but a complete theory is missing; (2) implicit regularization — why SGD's noise biases solutions toward those that generalize well — is an active research frontier; (3) escaping saddle points efficiently requires careful step-size or noise schedules, and the sharpest rates are still being established; (4) the edge of stability phenomenon, where networks train stably at learning rates exceeding the classical $2/L$ bound, defies the smooth-convex theory entirely. Bridging optimization guarantees with generalization remains one of the central open problems in machine learning theory.

Optimization Methods: Gradient Descent and Variants

Formal Statement

Why It Holds / Derivation

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also