Gradient Descent

Gradient descent (also known as steepest descent) is a first-order iterative optimization algorithm in computation and algorithms designed to find local or global minima of a differentiable scalar objective function L(θ) defined over a parameter space θ ∈ R^d. Introduced by French mathematician Augustin-Louis Cauchy in 1847 to solve nonlinear equations governing astronomical orbital mechanics, the method exploits the geometric property that the gradient vector ∇L(θ) points in the direction of greatest local rate of increase of L. By stepping in the opposite direction—along the negative gradient −∇L(θ)—each iteration reduces the objective value whenever the learning rate η is appropriately bounded. In contemporary scientific computing, stochastic and adaptive variants of gradient descent serve as the primary parameter-fitting engines for high-dimensional statistical models, inverse problems, and deep neural networks such as AlphaFold.

Directional Derivatives and Cauchy's Update Rule

Let L: R^d → R be a continuously differentiable objective (or loss) function parameterized by θ = (θ₁, ..., θ_d)^T. For any unit displacement direction u ∈ R^d satisfying ‖u‖₂ = 1, the first-order Taylor expansion around the current iterate θ_t gives the directional derivative:

D_uL(θ_t) = ∇L(θ_t)^T u = ‖∇L(θ_t)‖₂ cos φ

where ∇L(θ_t) = (∂L/∂θ₁, ..., ∂L/∂θ_d)^T is the gradient vector and φ is the angle between ∇L(θ_t) and u. By the Cauchy–Schwarz inequality, D_uL(θ_t) is minimized when cos φ = −1, meaning u = −∇L(θ_t)/‖∇L(θ_t)‖₂. Starting from an initial guess θ₀ ∈ R^d, gradient descent generates a sequence of iterates {θ_t}_t≥0 via:

θ_t+1 = θ_t − η_t ∇L(θ_t)

where η_t > 0 is the step size or learning rate. Iteration proceeds until the gradient norm satisfies ‖∇L(θ_t)‖₂ ≤ ε, indicating proximity to a first-order stationary point where ∇L(θ^*) = 0.

Lipschitz Smoothness and Step-Size Bounds

To establish convergence without overshooting the valley of the objective surface, L is assumed to have an L_lip-Lipschitz continuous gradient (L_lip-smoothness):

‖∇L(θ) − ∇L(φ)‖₂ ≤ L_lip ‖θ − φ‖₂, for all θ, φ ∈ R^d

When L is twice differentiable, L_lip bounds the largest eigenvalue λ_max of the Hessian matrix H(θ) = ∇²L(θ). Integrating along the segment connecting θ_t and θ_t+1 yields the Descent Lemma:

L(θ_t+1) ≤ L(θ_t) + ∇L(θ_t)^T(θ_t+1 − θ_t) + (L_lip / 2) ‖θ_t+1 − θ_t‖₂²

Substituting θ_t+1 − θ_t = −η∇L(θ_t) simplifies the upper bound to:

L(θ_t+1) ≤ L(θ_t) − η (1 − L_lipη / 2) ‖∇L(θ_t)‖₂²

Ensuring L(θ_t+1) < L(θ_t) whenever ∇L(θ_t) ≠ 0 requires 0 < η < 2/L_lip. The optimal fixed step size under worst-case smoothness is η = 1/L_lip, which decreases L by at least ‖∇L(θ_t)‖₂²/(2L_lip) per step. For convex L_lip-smooth objectives, the suboptimality gap decays at sublinear rate L(θ_T) − L(θ^*) ≤ L_lip‖θ₀ − θ^*‖₂²/(2T) = O(1/T). When L is μ-strongly convex (0 < μ ≤ λ_i(H) ≤ L_lip) with spectral condition number κ = L_lip/μ, setting η = 2/(μ + L_lip) yields geometric contraction:

‖θ_t − θ^*‖₂ ≤ [ (κ − 1) / (κ + 1) ]^t ‖θ₀ − θ^*‖₂

When κ ≫ 1, the level sets of L(θ) form elongated ellipsoidal ravines. Because −∇L is perpendicular to contour lines, standard gradient descent oscillates across the narrow canyon walls while advancing slowly along the valley floor—a pathology alleviated by momentum or the Conjugate Gradient Method.

Polyak Heavy-Ball Momentum and Nesterov Acceleration

To damp cross-valley oscillations in ill-conditioned ravines, Soviet mathematician Boris T. Polyak introduced the heavy-ball method in 1964. By analogy with an inertial particle moving through a viscous potential field, the update accumulates a velocity vector v_t with damping coefficient β ∈ [0, 1):

• v_t+1 = β v_t − η ∇L(θ_t)
• θ_t+1 = θ_t + v_t+1 = θ_t − η ∇L(θ_t) + β (θ_t − θ_t−1)

Along high-curvature axes where the gradient reverses sign each step, oscillations cancel; along low-curvature axes, velocity builds up by 1/(1 − β), improving quadratic contraction from (κ − 1)/(κ + 1) to (√κ − 1)/(√κ + 1).

In 1983, Yurii Nesterov formulated Nesterov Accelerated Gradient (NAG), which evaluates the gradient at the extrapolated lookahead position θ̃_t = θ_t + β_tv_t:

• v_t+1 = β_t v_t − η ∇L(θ_t + β_t v_t), with θ_t+1 = θ_t + v_t+1

With schedule β_t = (t − 1)/(t + 2), NAG achieves the optimal first-order smooth convex rate L(θ_T) − L(θ^*) = O(1/T²).

Robbins–Monro Stochastic Gradient Descent (SGD)

In empirical risk minimization over n observations, L(θ) = (1/n) ∑_i=1ⁿ ℓ_i(θ). Evaluating the full gradient costs O(nd) operations per step. Building on Herbert Robbins and Sutton Monro's 1951 stochastic approximation framework, Stochastic Gradient Descent (SGD) draws a uniform mini-batch B_t ⊂ {1, ..., n} of size b ≪ n and computes an unbiased estimator:

g_t = (1 / b) ∑_i∈Bt ∇ℓ_i(θ_t), with E[g_t | θ_t] = ∇L(θ_t)

reducing per-step cost to O(bd). Convergence to θ^* under mini-batch variance Var(g_t) = O(σ²/b) holds under the Robbins–Monro schedules ∑_t=1^∞ η_t = ∞ and ∑_t=1^∞ η_t² < ∞.

AdaGrad, RMSProp, and Adam Adaptive Moment Estimation

To adapt learning rates across parameters with disparate gradient scales, AdaGrad (Duchi et al., 2011) scales each coordinate j inversely by √(∑_τ=1^t g_τ,j²), while RMSProp replaces the cumulative sum with a geometrically decaying average governed by exp(−λt) decay dynamics. Adam (Adaptive Moment Estimation, Kingma and Ba, 2015) combines momentum with per-coordinate scaling by tracking decaying averages of the first moment m_t and uncentered second moment v_t:

• m_t = β₁ m_t−1 + (1 − β₁) g_t, and v_t = β₂ v_t−1 + (1 − β₂) (g_t ⊙ g_t)
• m̂_t = m_t / (1 − β₁^t), and v̂_t = v_t / (1 − β₂^t)
• θ_t+1 = θ_t − η m̂_t / (√v̂_t + ε_stab)

where β₁ = 0.9, β₂ = 0.999, and ε_stab = 10⁻⁸, correcting for zero-initialization bias in early iterations.

Why does gradient descent zig-zag in elongated valleys?

The gradient ∇L(θ) is perpendicular to the contour surfaces of L(θ). When the Hessian matrix has a large condition number κ = λ_max/λ_min ≫ 1, the contours form narrow ellipses whose perpendiculars point across the short axis rather than along the valley floor toward the minimum.

Why is mini-batch SGD often preferred over full-batch gradient descent in deep learning?

Beyond cutting per-step cost from O(nd) to O(bd), mini-batch gradient noise destabilizes sharp, high-curvature local minima and helps trajectories settle into broad, flat basins that generalize better on unseen data.

How does gradient descent differ from Newton's method?

Gradient descent is a first-order method using only ∇L(θ_t) in O(d) memory. Newton's method is a second-order method that multiplies by the inverse Hessian [H(θ_t)]⁻¹∇L(θ_t), achieving quadratic local convergence at the expense of O(d²) memory and O(d³) linear solver operations per step.

1. Cauchy, A.-L. (1847). Méthode générale pour la résolution des systèmes d'équations simultanées. Comptes Rendus Hebdomadaires des Séances de l'Académie des Sciences, 25, 536–538. https://doi.org/10.1017/CBO9780511702396.091
2. Robbins, H., & Monro, S. (1951). A stochastic approximation method. The Annals of Mathematical Statistics, 22(3), 400–407. https://doi.org/10.1214/aoms/1177729586
3. Polyak, B. T. (1964). Some methods of speeding up the convergence of iteration methods. USSR Computational Mathematics and Mathematical Physics, 4(5), 1–17. https://doi.org/10.1016/0041-5553(64)90137-590137-5)
4. Nesterov, Y. (1983). A method for solving the convex programming problem with convergence rate O(1/k²). Soviet Mathematics Doklady, 27(2), 372–376. https://doi.org/10.1007/978-1-4419-8853-9
5. Duchi, J., Hazan, E., & Singer, Y. (2011). Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12, 2121–2159. https://doi.org/10.5555/1953048.2021068