Gradient Descent

Table of Contents

1. Learning Objectives
2. Prerequisites
3. Notation
4. Core Intuition
5. First-Order Taylor Expansion
6. The Steepest Descent Direction
7. The Gradient Descent Update Rule
8. Smoothness and the Sufficient Decrease Lemma
9. Convergence for Convex Functions
10. Strong Convexity and Linear Convergence
11. Stochastic Gradient Descent
12. Momentum and Nesterov Acceleration
13. Adam: Adaptive Moment Estimation
14. Learning Rate Schedules
15. Connection to the Eigenbasis
16. Common Pitfalls and Misconceptions
17. Research Perspective
18. Summary of Takeaways
19. Exercises

---

Learning Objectives

After reading this chapter, you should be able to:

1. Derive the gradient descent update from the first-order Taylor approximation and the Cauchy–Schwarz inequality.
2. State the $L$-smoothness condition and prove the sufficient decrease lemma.
3. Prove $O(1/T)$ convergence for convex objectives and linear convergence for strongly convex objectives.
4. Derive SGD as an unbiased gradient estimator and state its variance properties.
5. Derive momentum as an exponential moving average of gradients and explain its effect on ravines.
6. Derive Adam including bias correction, and interpret per-parameter adaptive learning rates.
7. Analyze gradient descent convergence in the eigenbasis of a quadratic objective.

---

Prerequisites

• Eigenvalues & Eigenvectors: eigendecomposition, condition number, gradient descent on quadratics.
• Positive Definite Matrices: convexity via the Hessian, quadratic forms.
• Vectors, Spans & Linear Independence: inner products, Cauchy–Schwarz inequality.

---

Notation

• $f: \mathbb{R}^n \to \mathbb{R}$ — Objective function
• $\nabla f(\mathbf{x})$ — Gradient vector
• $\mathbf{H} = \nabla^2 f(\mathbf{x})$ — Hessian matrix
• $\alpha, \alpha_t$ — Learning rate (step size)
• $\mathbf{x}_t$ — Parameter iterate at step $t$
• $\kappa(\mathbf{H})$ — Hessian condition number

---

Core Intuition

Training a machine learning model means finding parameters $\boldsymbol\theta \in \mathbb{R}^p$ that minimize a loss function $J(\boldsymbol\theta)$. For differentiable $J$, the gradient $\nabla J(\boldsymbol\theta)$ points in the direction of steepest increase. Moving in the opposite direction — gradient descent — is the locally optimal first-order strategy for decreasing the loss.

This chapter derives gradient descent from the Taylor expansion, proves convergence under smoothness and convexity, and extends the basic algorithm to stochastic variants (SGD), momentum, and Adam. The condition number of the Hessian — developed in Eigenvalues & Eigenvectors — governs how difficult the optimization landscape is for first-order methods.

Series context. This opens Chapter 2 (Calculus & Optimization) in Volume I. It connects to Linear Regression in Volume II and Backpropagation in Volume II, Part III.

---

First-Order Taylor Expansion

Definition 1. A function $J: \mathbb{R}^d \to \mathbb{R}$ is differentiable at $\boldsymbol\theta$ if there exists $\nabla J(\boldsymbol\theta) \in \mathbb{R}^d$ such that

$$J(\boldsymbol\theta + \boldsymbol\delta) = J(\boldsymbol\theta) + \nabla J(\boldsymbol\theta)^T \boldsymbol\delta + o(\|\boldsymbol\delta\|). \tag{1}$$

The first-order Taylor approximation (linearization) is:

$$J(\boldsymbol\theta + \boldsymbol\delta) \approx J(\boldsymbol\theta) + \nabla J(\boldsymbol\theta)^T \boldsymbol\delta. \tag{2}$$

This approximation is accurate for small $\|\boldsymbol\delta\|$ and captures the local linear behavior of $J$.

Multivariate chain rule preview. When $J$ depends on parameters through a computational graph, $\nabla J$ is computed via backpropagation (Chapter 8). Here we treat $\nabla J$ as given.

---

The Steepest Descent Direction

Problem. Find $\boldsymbol\delta^*$ with $\|\boldsymbol\delta\| = \epsilon$ that minimizes the linear approximation:

$$\boldsymbol\delta^* = \arg\min_{\|\boldsymbol\delta\| = \epsilon} \left[J(\boldsymbol\theta) + \nabla J(\boldsymbol\theta)^T \boldsymbol\delta\right]. \tag{3}$$

Since $J(\boldsymbol\theta)$ is constant in $\boldsymbol\delta$, this minimizes $\nabla J^T \boldsymbol\delta$.

Theorem 1 (Steepest Descent Direction). The unit vector minimizing $\nabla J^T \boldsymbol\delta$ is

$$\boldsymbol\delta^* = -\epsilon \frac{\nabla J(\boldsymbol\theta)}{\|\nabla J(\boldsymbol\theta)\|}. \tag{4}$$

Proof. By the Cauchy–Schwarz inequality:

$$\nabla J^T \boldsymbol\delta \geq -\|\nabla J\| \cdot \|\boldsymbol\delta\| = -\epsilon \|\nabla J\|, \tag{5}$$

with equality when $\boldsymbol\delta = -\epsilon \nabla J / \|\nabla J\|$. $\blacksquare$

Important equation. Equation (4) proves that the negative gradient is the direction of steepest descent — the geometric foundation of all first-order optimization.

---

The Gradient Descent Update Rule

Rescaling the step size, define the learning rate $\alpha > 0$ and the gradient descent update:

$$\boxed{\boldsymbol\theta_{t+1} = \boldsymbol\theta_t - \alpha \nabla J(\boldsymbol\theta_t).} \tag{6}$$

At each iteration:

1. Compute the gradient $\mathbf{g}_t = \nabla J(\boldsymbol\theta_t)$.
2. Update parameters in the negative gradient direction: $\boldsymbol\theta_{t+1} = \boldsymbol\theta_t - \alpha \mathbf{g}_t$.
3. Repeat until a stopping criterion is met (e.g., $\|\mathbf{g}_t\| < \epsilon$ or fixed iteration budget).

Visual description. Imagine standing on a hilly surface (the loss landscape). The gradient points uphill along the steepest slope. Taking a step downhill (opposite to the gradient) decreases elevation locally. Repeating this process traces a path toward a valley (local minimum), though the path may zigzag in narrow ravines.

---

Smoothness and the Sufficient Decrease Lemma

Definition 2 ($L$-Smoothness). $J$ has $L$-Lipschitz continuous gradients (is $L$-smooth) if

$$\|\nabla J(\boldsymbol\theta_1) - \nabla J(\boldsymbol\theta_2)\| \leq L \|\boldsymbol\theta_1 - \boldsymbol\theta_2\|, \quad \forall \boldsymbol\theta_1, \boldsymbol\theta_2. \tag{7}$$

Lemma 1 (Quadratic Upper Bound). If $J$ is $L$-smooth, then for all $\boldsymbol\theta, \boldsymbol\delta$:

$$J(\boldsymbol\theta + \boldsymbol\delta) \leq J(\boldsymbol\theta) + \nabla J(\boldsymbol\theta)^T \boldsymbol\delta + \frac{L}{2}\|\boldsymbol\delta\|^2. \tag{8}$$

Proof. Integrate the gradient along the line from $\boldsymbol\theta$ to $\boldsymbol\theta + \boldsymbol\delta$ and bound using (7). $\blacksquare$

Theorem 2 (Sufficient Decrease). Under $L$-smoothness, gradient descent with step size $\alpha$ satisfies

$$J(\boldsymbol\theta_{t+1}) \leq J(\boldsymbol\theta_t) - \alpha\left(1 - \frac{L\alpha}{2}\right)\|\nabla J(\boldsymbol\theta_t)\|^2. \tag{9}$$

Proof. Apply (8) with $\boldsymbol\delta = -\alpha \nabla J(\boldsymbol\theta_t)$:

$$J(\boldsymbol\theta_{t+1}) \leq J(\boldsymbol\theta_t) - \alpha\|\nabla J(\boldsymbol\theta_t)\|^2 + \frac{L\alpha^2}{2}\|\nabla J(\boldsymbol\theta_t)\|^2 = J(\boldsymbol\theta_t) - \alpha\left(1 - \frac{L\alpha}{2}\right)\|\nabla J(\boldsymbol\theta_t)\|^2. \quad \blacksquare \tag{10}$$

Descent condition. The factor $(1 - L\alpha/2) > 0$ requires $\alpha < 2/L$.

Optimal fixed step size. Maximizing the guaranteed decrease per step:

$$\frac{d}{d\alpha}\left[\alpha - \frac{L\alpha^2}{2}\right] = 0 \implies \alpha^* = \frac{1}{L}. \tag{11}$$

Substituting into (9):

$$J(\boldsymbol\theta_{t+1}) \leq J(\boldsymbol\theta_t) - \frac{1}{2L}\|\nabla J(\boldsymbol\theta_t)\|^2. \tag{12}$$

Important equation. Equation (12) guarantees progress proportional to the squared gradient norm. When $\|\nabla J\| \to 0$, progress slows — characteristic of convergence to a stationary point.

---

Convergence for Convex Functions

Definition 3 (Convexity). $J$ is convex if for all $\boldsymbol\theta, \boldsymbol\phi$ and $\lambda \in [0,1]$:

$$J(\lambda\boldsymbol\theta + (1-\lambda)\boldsymbol\phi) \leq \lambda J(\boldsymbol\theta) + (1-\lambda)J(\boldsymbol\phi). \tag{13}$$

Equivalently (first-order condition): $J(\boldsymbol\phi) \geq J(\boldsymbol\theta) + \nabla J(\boldsymbol\theta)^T(\boldsymbol\phi - \boldsymbol\theta)$.

Theorem 3 ($O(1/T)$ Convergence). If $J$ is convex and $L$-smooth, gradient descent with $\alpha = 1/L$ satisfies

$$J(\boldsymbol\theta_T) - J(\boldsymbol\theta^*) \leq \frac{L\|\boldsymbol\theta_0 - \boldsymbol\theta^*\|^2}{2T}, \tag{14}$$

where $\boldsymbol\theta^* \in \arg\min J$.

Proof sketch. Define the Lyapunov function $\Delta_t = \|\boldsymbol\theta_t - \boldsymbol\theta^*\|^2$. Using convexity and smoothness:

$$\Delta_{t+1} = \|\boldsymbol\theta_t - \alpha\nabla J(\boldsymbol\theta_t) - \boldsymbol\theta^*\|^2 \leq \Delta_t - \frac{2\alpha}{L}(J(\boldsymbol\theta_t) - J(\boldsymbol\theta^*)). \tag{15}$$

Telescoping over $t = 0, \ldots, T-1$ and using $\Delta_T \geq 0$ gives (14). $\blacksquare$

Interpretation. Halving the optimality gap requires doubling the iteration count — sublinear convergence.

---

Strong Convexity and Linear Convergence

Definition 4 (Strong Convexity). $J$ is $\mu$-strongly convex if

$$J(\boldsymbol\phi) \geq J(\boldsymbol\theta) + \nabla J(\boldsymbol\theta)^T(\boldsymbol\phi - \boldsymbol\theta) + \frac{\mu}{2}\|\boldsymbol\phi - \boldsymbol\theta\|^2. \tag{16}$$

Equivalently, $\nabla^2 J(\boldsymbol\theta) \succeq \mu \mathbf{I}$ when twice differentiable.

Theorem 4 (Linear Convergence). If $J$ is $\mu$-strongly convex and $L$-smooth, gradient descent with $\alpha = 1/L$ satisfies

$$J(\boldsymbol\theta_T) - J(\boldsymbol\theta^*) \leq \left(1 - \frac{\mu}{L}\right)^T \left[J(\boldsymbol\theta_0) - J(\boldsymbol\theta^*)\right]. \tag{17}$$

Proof sketch. Strong convexity gives $\|\boldsymbol\theta_{t+1} - \boldsymbol\theta^*\|^2 \leq (1 - \mu/L)\|\boldsymbol\theta_t - \boldsymbol\theta^*\|^2$. Apply to the function value gap via smoothness. $\blacksquare$

The ratio $\kappa = L/\mu$ is the condition number. Large $\kappa$ means slow convergence — the loss landscape is a long narrow valley. This connects directly to the eigenvalue analysis in Eigenvalues & Eigenvectors.

---

Stochastic Gradient Descent

For empirical risk $J(\boldsymbol\theta) = \frac{1}{N}\sum_{i=1}^{N} L_i(\boldsymbol\theta)$, computing $\nabla J$ requires all $N$ samples.

Definition 5 (Mini-batch SGD). Given a mini-batch $\mathcal{B}_t \subset \{1, \ldots, N\}$:

$$\boldsymbol\theta_{t+1} = \boldsymbol\theta_t - \alpha_t \cdot \frac{1}{|\mathcal{B}_t|}\sum_{i \in \mathcal{B}_t} \nabla L_i(\boldsymbol\theta_t). \tag{18}$$

Proposition 1 (Unbiasedness). The mini-batch gradient is an unbiased estimator of the full gradient:

$$\mathbb{E}_{\mathcal{B}_t}\left[\frac{1}{|\mathcal{B}_t|}\sum_{i \in \mathcal{B}_t} \nabla L_i(\boldsymbol\theta)\right] = \nabla J(\boldsymbol\theta). \tag{19}$$

Proposition 2 (Variance). If samples are i.i.d. and batch size is $B$,

$$\text{Var}\left(\frac{1}{B}\sum_{i \in \mathcal{B}} \nabla L_i(\boldsymbol\theta)\right) = \frac{1}{B}\text{Var}(\nabla L_i(\boldsymbol\theta)). \tag{20}$$

Variance decreases linearly with batch size, trading compute for gradient stability.

Convergence requirement. For SGD to converge, the learning rate must satisfy $\sum_t \alpha_t = \infty$ and $\sum_t \alpha_t^2 < \infty$ (Robbins–Monro conditions), typically $\alpha_t = O(1/t)$.

---

Momentum and Nesterov Acceleration

Problem. In ravines (elongated level sets), gradient descent oscillates across the narrow direction while making slow progress along the valley.

Polyak Momentum. Maintain a velocity vector:

$$\mathbf{v}_t = \beta \mathbf{v}_{t-1} + \nabla J(\boldsymbol\theta_t), \qquad \boldsymbol\theta_{t+1} = \boldsymbol\theta_t - \alpha \mathbf{v}_t, \tag{21}$$

where $\beta \in [0, 1)$ (typically $\beta = 0.9$).

Derivation as exponential moving average. Unrolling (21):

$$\mathbf{v}_t = \sum_{k=0}^{t} \beta^{t-k} \nabla J(\boldsymbol\theta_k). \tag{22}$$

Recent gradients receive weight $\sim 1$; gradients from $k$ steps ago receive weight $\sim \beta^k$. The effective memory window is $\sim 1/(1-\beta)$ steps.

Effect. Consistent gradient directions accumulate (acceleration along the valley); oscillating directions partially cancel (damping across the ravine).

Nesterov Accelerated Gradient (NAG). Look ahead before computing the gradient:

$$\mathbf{v}_t = \beta \mathbf{v}_{t-1} + \nabla J(\boldsymbol\theta_t - \beta \mathbf{v}_{t-1}), \qquad \boldsymbol\theta_{t+1} = \boldsymbol\theta_t - \alpha \mathbf{v}_t. \tag{23}$$

For convex $L$-smooth functions, NAG achieves $O(1/T^2)$ convergence — optimal among first-order methods.

---

Adam: Adaptive Moment Estimation

Adam (Kingma & Ba, 2015) combines momentum with per-parameter adaptive learning rates.

Step 1 — Gradient:

$$\mathbf{g}_t = \nabla J(\boldsymbol\theta_t). \tag{24}$$

Step 2 — First moment (momentum):

$$\mathbf{m}_t = \beta_1 \mathbf{m}_{t-1} + (1 - \beta_1)\mathbf{g}_t. \tag{25}$$

Step 3 — Second moment (squared gradient EMA):

$$\mathbf{v}_t = \beta_2 \mathbf{v}_{t-1} + (1 - \beta_2)\mathbf{g}_t^2, \tag{26}$$

where $\mathbf{g}_t^2$ denotes element-wise squaring.

Step 4 — Bias correction. Since $\mathbf{m}_0 = \mathbf{v}_0 = \mathbf{0}$, early estimates are biased toward zero:

$$\hat{\mathbf{m}}_t = \frac{\mathbf{m}_t}{1 - \beta_1^t}, \qquad \hat{\mathbf{v}}_t = \frac{\mathbf{v}_t}{1 - \beta_2^t}. \tag{27}$$

Derivation of bias correction. Taking expectations (assuming stationary $\mathbb{E}[\mathbf{g}_t] = \mathbf{g}$):

$$\mathbb{E}[\mathbf{m}_t] = (1-\beta_1)\mathbf{g}\sum_{i=0}^{t-1}\beta_1^i = (1-\beta_1^t)\mathbf{g}. \tag{28}$$

Dividing by $(1-\beta_1^t)$ yields an unbiased first-moment estimate.

Step 5 — Parameter update:

$$\boldsymbol\theta_{t+1} = \boldsymbol\theta_t - \frac{\alpha}{\sqrt{\hat{\mathbf{v}}_t} + \epsilon} \odot \hat{\mathbf{m}}_t. \tag{29}$$

Interpretation. The denominator $\sqrt{\hat{\mathbf{v}}_t} \approx \mathbb{E}[|\mathbf{g}|^2]^{1/2}$ per parameter. Dividing by it normalizes step sizes — parameters with large historical gradients receive smaller steps. This is diagonal preconditioning that adapts to local curvature estimates.

Default hyperparameters: $\beta_1 = 0.9$, $\beta_2 = 0.999$, $\epsilon \approx 10^{-8}$, $\alpha = 10^{-3}$.

---

Learning Rate Schedules

Fixed learning rates may be too large near convergence (oscillation) or too small early (slow progress). Schedules modulate $\alpha_t$ over training.

Step decay:

$$\alpha_t = \alpha_0 \cdot \gamma^{\lfloor t / T_0 \rfloor}, \tag{30}$$

where $\gamma \in (0,1)$ and $T_0$ is the period.

Cosine annealing:

$$\alpha_t = \alpha_{\min} + \frac{1}{2}(\alpha_{\max} - \alpha_{\min})\left(1 + \cos\left(\frac{t}{T}\pi\right)\right). \tag{31}$$

Warmup. Linear increase from 0 to $\alpha_{\max}$ over the first $T_w$ steps:

$$\alpha_t = \alpha_{\max} \cdot \min\left(1, \frac{t}{T_w}\right). \tag{32}$$

Warmup stabilizes early training for large models where initial gradients may be large and Adam's bias correction is active.

Visual description. Learning rate schedules modulate step size over time: warmup gently ramps up to avoid early instability; step decay or cosine annealing gradually shrink steps for fine-grained convergence near the minimum.

---

Connection to the Eigenbasis

For quadratic $J(\boldsymbol\theta) = \frac{1}{2}\boldsymbol\theta^T \mathbf{H}\boldsymbol\theta$ with $\mathbf{H} \succ 0$, write $\mathbf{H} = \mathbf{Q}\boldsymbol{\Lambda}\mathbf{Q}^T$. In coordinates $\mathbf{y}_t = \mathbf{Q}^T \boldsymbol\theta_t$:

$$y_{t+1,i} = (1 - \alpha\lambda_i) y_{t,i}. \tag{33}$$

Each eigen-direction decouples with contraction rate $|1 - \alpha\lambda_i|$.

Optimal step size: $\alpha^* = 2/(\lambda_{\min} + \lambda_{\max})$.

Convergence rate:

$$\rho = \frac{\kappa - 1}{\kappa + 1}, \quad \kappa = \frac{\lambda_{\max}}{\lambda_{\min}}. \tag{34}$$

Adam and other adaptive methods attempt to reduce effective $\kappa$ by per-coordinate scaling — approximating Newton's method, which uses the full Hessian $\mathbf{H}^{-1}$ for optimal preconditioning.

---

Common Pitfalls and Misconceptions

Pitfall 1: Using $\alpha > 2/L$. The sufficient decrease lemma fails; gradient descent may diverge.

Pitfall 2: Expecting global convergence for non-convex $J$. GD converges to stationary points ($\nabla J = \mathbf{0}$), which may be saddles or local maxima, not global minima.

Pitfall 3: Ignoring batch size effects in SGD. Small batches add noise (regularization benefit) but require smaller learning rates or warmup.

Pitfall 4: Treating Adam as always superior to SGD. For some tasks (especially with careful tuning), SGD with momentum matches or exceeds Adam. Adam's adaptive rates can generalize differently.

Pitfall 5: Confusing learning rate with momentum. Momentum ($\beta$) controls velocity accumulation; learning rate ($\alpha$) controls step magnitude. Both affect convergence but serve different roles.

---

Research Perspective

Gradient descent dates to Cauchy (1847) and was systematized in convex optimization by Nesterov (1983), who proved the optimal $O(1/T^2)$ rate for accelerated methods. Stochastic approximation (Robbins & Monro, 1951) laid foundations for SGD.

In deep learning, SGD with momentum dominated until Adam (2015) became the default for transformer pretraining. Recent research revisits SGD with careful learning rate schedules (large-batch training, warmup-decay) and questions whether adaptive methods' generalization properties match their optimization speed.

Gradient flow (continuous-time limit $\alpha \to 0$) connects to neural tangent kernel theory and Bayesian inference — developed in the RBC Borealis series on machine learning from multiple viewpoints. Second-order methods (natural gradient, K-FAC) use curvature information beyond diagonal Adam approximations.

---

Summary of Takeaways

• Steepest descent — $\boldsymbol\delta^* = -\epsilon \nabla J / \ — \nabla J\ —$ — Negative gradient is optimal direction
• GD update — $\boldsymbol\theta_{t+1} = \boldsymbol\theta_t - \alpha \nabla J$ — Basic optimization step
• Descent condition — $\alpha < 2/L$ — Step size bound for smooth $J$
• Optimal fixed rate — $\alpha^* = 1/L$ — Maximizes guaranteed decrease
• Convex rate — $O(1/T)$ — Sublinear convergence
• Strongly convex rate — $(1 - \mu/L)^T$ — Linear convergence, $\kappa = L/\mu$
• SGD — Unbiased mini-batch gradient — Scalable to large data
• Momentum — EMA of past gradients — Ravine acceleration
• Adam — Per-parameter adaptive rates — Diagonal preconditioning

Next article: Bayes' Theorem — Chapter 3: probability foundations for statistical learning.

---

Exercises

Exercise 1. Prove Lemma 1 (quadratic upper bound) from $L$-smoothness by integrating $\nabla J(\boldsymbol\theta + t\boldsymbol\delta)^T \boldsymbol\delta$ from $t=0$ to $t=1$.

Exercise 2. For $J(\boldsymbol\theta) = \frac{1}{2}\boldsymbol\theta^T \mathbf{H}\boldsymbol\theta$ with $\mathbf{H} = \text{diag}(1, 100)$, find the optimal learning rate and the convergence rate per iteration.

Exercise 3. Derive equation (28) for the bias in Adam's first moment estimate.

Exercise 4 (SGD). Show that with batch size $B=1$ and learning rate $\alpha_t = c/\sqrt{t}$, the Robbins–Monro conditions for convergence are satisfied.

Exercise 5 (NAG). Explain intuitively why evaluating the gradient at $\boldsymbol\theta_t - \beta\mathbf{v}_{t-1}$ (look-ahead) improves over standard momentum in ravines.

Exercise 6 (Convexity). Prove that $J(\boldsymbol\theta) = \|\mathbf{A}\boldsymbol\theta - \mathbf{b}\|^2$ is convex and compute its gradient and Hessian. When is it strongly convex?

Exercise 7 (Conceptual). Compare the per-iteration cost and convergence rate of gradient descent with exact line search versus fixed $\alpha = 1/L$ for a quadratic objective.