Optimization Methods: Gradient Descent and Variants

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.

Gradient descent (GD) solves $min_{x \in R^{n}} f (x)$ for a differentiable objective $f$ by generating a sequence $x_{k + 1} = x_{k} - η \nabla f (x_{k})$ , where $η > 0$ is the step size (learning rate) and $\nabla f$ is the gradient. The method matters because it scales to enormous problems where second-order methods (requiring the Hessian) are infeasible — including the training of models with billions of parameters. Its appeal is that each iteration costs only one gradient evaluation, yet it provably converges for convex problems and works remarkably well in practice for non-convex ones. A surprising fact: the direction of steepest descent depends on the choice of norm, so the "natural" descent direction is not unique — this insight gives rise to entire families of algorithms (natural gradient, mirror descent). The art of optimization lies largely in choosing the step size and accelerating convergence.

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

Formal Statement

Gradient and Descent Direction

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

\nabla f (x) = (\frac{\partial f}{\partial x _{1}}, \frac{\partial f}{\partial x _{2}}, \dots, \frac{\partial f}{\partial x _{n}})^{⊤}

⟳The gradient is defined so that the directional derivative satisfies

D_{u} f (x) = \nabla f (x)^{⊤} u

; stack the partials measured along each coordinate axis

e_{i}

A vector $d$ is a descent direction at $x$ if $\nabla f (x)^{⊤} d < 0$ , guaranteeing $f$ decreases along $d$ for small steps.

The Gradient Descent Iteration

Given an initial point $x_{0}$ and step sizes $η_{k} > 0$ , gradient descent produces:

x_{k + 1} = x_{k} - η_{k} \nabla f (x_{k}), k = 0, 1, 2, \dots

⟳Choose the descent direction

d = - \nabla f (x)

, which minimizes the linear (first-order Taylor) approximation

f (x) + \nabla f (x)^{⊤} d

subject to

∥ d ∥_{2} = 1

by Cauchy–Schwarz.

Here $η_{k}$ may be fixed ( $η_{k} = η$ ), diminishing ( $η_{k} \to 0$ with $\sum η_{k} = \infty$ ), or chosen by line search.

Steepest-Descent Property

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

ar g ∥ d ∥_{2} = 1 min \nabla f (x)^{⊤} d = - \frac{\nabla f ( x )}{∥\nabla f ( x ) ∥ _{2}}

⟳Apply Cauchy–Schwarz,

\nabla f (x)^{⊤} d \geq - ∥\nabla f (x) ∥_{2} ∥ d ∥_{2}

, with equality iff

d

is anti-parallel to

\nabla f (x)

Convergence for L-Smooth Convex Functions

Let $f$ be convex and L-smooth, meaning $∥\nabla f (x) - \nabla f (y) ∥_{2} \leq L ∥ x - y ∥_{2}$ for all $x, y$ . With fixed step size $η = 1/ L$ , gradient descent satisfies:

f (x_{k}) - f (x^{⋆}) \leq \frac{∥ x _{0} - x ^{⋆} ∥ _{2}^{2}}{2 η k} = \frac{L ∥ x _{0} - x ^{⋆} ∥ _{2}^{2}}{2 k}

⟳Combine the descent lemma

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

with convexity

f (x_{k}) - f (x^{⋆}) \leq \nabla f (x_{k})^{⊤} (x_{k} - x^{⋆})

, then telescope the bound on

∥ x_{k} - x^{⋆} ∥^{2}

If additionally $f$ is $μ$ -strongly convex ( $μ > 0$ ), convergence is linear (geometric):

∥ x_{k} - x^{⋆} ∥_{2}^{2} \leq (1 - \frac{μ}{L})^{k} ∥ x_{0} - x^{⋆} ∥_{2}^{2}

⟳Show the gradient step is a contraction; expand

∥ x_{k + 1} - x^{⋆} ∥^{2}

and use co-coercivity of

\nabla f

together with strong convexity to bound the inner-product term.

Why It Holds / Derivation

Descent 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

y

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

⟳Write

f (y) - f (x) = \int_{0}^{1} \nabla f (x + t (y - x))^{⊤} (y - x) d t

, add and subtract

\nabla f (x)^{⊤} (y - x)

, and bound the remainder using the Lipschitz property.

Step 2 — Guaranteed decrease. Substitute

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

into [6] with

η = 1/ L

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

⟳Plug

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

into [6], collect the

∥\nabla f ∥^{2}

terms; the choice

η = 1/ L

makes the coefficient

- \frac{1}{2 L}

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

∥ x_{k + 1} - x^{⋆} ∥_{2}^{2} = ∥ x_{k} - x^{⋆} ∥_{2}^{2} - 2 η \nabla f (x_{k})^{⊤} (x_{k} - x^{⋆}) + η^{2} ∥\nabla f (x_{k}) ∥_{2}^{2}

⟳Substitute

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

and expand the binomial

∥ a - b ∥^{2} = ∥ a ∥^{2} - 2 a^{⊤} b + ∥ b ∥^{2}

Step 4 — Apply convexity. Using

\nabla f (x_{k})^{⊤} (x_{k} - x^{⋆}) \geq f (x_{k}) - f (x^{⋆})

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

■

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.

Building 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 $η$ 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.

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

Worked Examples

Quadratic in One Variable

Given: Minimize

f (x) = \frac{1}{2} (x - 3)^{2}

starting from

x_{0} = 0

with fixed

η = 0.5

. Step 1 — Gradient.

\nabla f (x) = f^{'} (x) = x - 3

. Step 2 — Iterate using

x_{k + 1} = x_{k} - η (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 - η) (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 $η = 0.5 < 2/ L = 2$ , so convergence is geometric.

x_{k} = 3 - 3 (0.5)^{k} \to x^{⋆} = 3 (dimensionless units)

Two-Variable Quadratic with Conditioning

Given: Minimize

f (x, y) = \frac{1}{2} (10 x^{2} + y^{2})

, starting from

(x_{0}, y_{0}) = (1, 1)

η = 0.1

. Step 1 — Gradient.

\nabla f = (10 x, y)^{⊤}

. The Hessian is

diag (10, 1)

, so

L = 10

μ = 1

, condition number

κ = L / μ = 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 $κ$ governs convergence per [5]: rate factor $\approx (1 - μ / L) = 0.9$ .

(x_{k}, y_{k}) = (0, (0.9)^{k}) \to (0, 0); slow due to κ = 10

Common Misconceptions

A larger step size is not always faster. If

η > 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 < η < 2/ L

, with

η = 1/ L

optimal for the

O (1/ k)

guarantee. Practitioners who "crank up the learning rate" to speed training often trigger instability or NaNs. $\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). 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

η

fixed and

x_{k}

near

0

, the subgradient is

\pm 1

, so the iterate jumps by

\pm η

and oscillates forever around

0

in steps of size

η

, never settling. The remedy is a diminishing step size

η_{k} \to 0

with

\sum η_{k} = \infty

, which the standard

O (1/ L)

smooth theory does not cover — this is the domain of Subgradient Methods.

Connections

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.

Real-World Applications

Neural network training (deep learning): Stochastic gradient descent with Adam or momentum optimizers trains models from image classifiers (ResNet) to large language models (GPT), computing gradients via Backpropagation.
Logistic regression (statistics/ML): The log-likelihood is concave; gradient ascent (descent on the negative log-likelihood) fits classifiers in scikit-learn and statsmodels.
Recommender systems: Matrix factorization for Netflix/Amazon recommendations minimizes reconstruction error over latent factors using SGD.
Inverse problems & imaging: CT and MRI reconstruction, and seismic inversion in geophysics, minimize data-misfit functionals by (often regularized) gradient methods.
Robotics & optimal control: Trajectory optimization and reinforcement-learning policy gradients (e.g., for locomotion controllers) ascend a reward gradient.
Portfolio optimization (finance): Minimizing risk subject to return constraints uses projected gradient descent over the simplex of asset weights.
Hyperparameter tuning & meta-learning: Bilevel and gradient-based hyperparameter optimization differentiate through training to tune learning rates and regularizers.

Historical Development

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 $\overset{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.

Subtleties & Limits

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.