Key Concepts of Gradient Descent Algorithms

Why This Matters

Gradient descent is the engine behind nearly every machine learning model you'll encounter—from simple linear regression to deep neural networks with millions of parameters. Understanding how these algorithms navigate the loss landscape isn't just academic; it's the difference between a model that converges efficiently and one that stalls, oscillates, or settles into a poor local minimum. You're being tested on your ability to analyze convergence behavior, compare computational trade-offs, and select appropriate optimizers for different problem structures.

The algorithms in this guide demonstrate core numerical principles: iterative optimization, adaptive step sizes, momentum dynamics, and the trade-off between computational cost and convergence stability. Don't just memorize which algorithm uses which update rule—know why each modification improves performance and when each approach is most appropriate. FRQs often ask you to justify optimizer selection or analyze convergence properties, so focus on the underlying mechanisms.

---

First-Order Methods: Basic Gradient Updates

These foundational algorithms compute gradients directly from data and update parameters proportionally. The key trade-off is between gradient accuracy (using more data) and computational efficiency (using less).

Batch Gradient Descent

• Computes gradients over the entire dataset—provides the true gradient direction at each iteration, ensuring deterministic updates
• Stable convergence path with no noise in updates, making it ideal for convex optimization problems with smooth loss surfaces
• Computational cost scales linearly with dataset size, making it impractical for large-scale problems where $n$ exceeds memory limits

Stochastic Gradient Descent (SGD)

• Updates parameters using a single data point—each iteration costs $O(1)$ in terms of data access, enabling rapid iteration
• Inherent noise acts as regularization and can help escape shallow local minima in non-convex landscapes
• High variance in updates causes the loss function to fluctuate, requiring careful learning rate scheduling for convergence

Mini-Batch Gradient Descent

• Uses a subset of $b$ samples per update—balances gradient accuracy against computational efficiency with typical batch sizes of 32–256
• Enables vectorized computation on GPUs, achieving better hardware utilization than pure SGD while maintaining stochastic benefits
• Standard choice in practice for deep learning, offering the best trade-off between convergence speed and stability

---

Momentum Methods: Accelerating Convergence

Momentum-based approaches accumulate velocity from past gradients to smooth updates and accelerate progress. The core insight is that gradient history provides information about the loss surface's curvature.

Momentum-based Gradient Descent

• Accumulates a velocity term $v_t = \gamma v_{t-1} + \eta \nabla L(\theta)$ where $\gamma$ (typically 0.9) controls how much history to retain
• Dampens oscillations in narrow valleys by averaging out perpendicular gradient components while reinforcing consistent directions
• Accelerates convergence from $O(1/t)$ to $O(1/t^2)$ for convex functions under appropriate conditions

Nesterov Accelerated Gradient (NAG)

• Evaluates gradient at the "lookahead" position $\theta - \gamma v_{t-1}$ rather than current parameters—a subtle but powerful correction
• Provides anticipatory updates that reduce overshooting by incorporating where momentum is already taking you
• Achieves optimal convergence rate of $O(1/k^2)$ for smooth convex functions, provably faster than standard momentum

---

Adaptive Learning Rate Methods: Per-Parameter Scaling

These algorithms automatically adjust learning rates for each parameter based on gradient history. The key principle is that parameters with large historical gradients should take smaller steps, and vice versa.

Adagrad

• Accumulates squared gradients in a diagonal matrix $G_t = \sum_{\tau=1}^{t} g_\tau \odot g_\tau$, scaling updates by $1/\sqrt{G_t + \epsilon}$
• Excels with sparse features by giving infrequent parameters larger effective learning rates—critical for NLP and recommendation systems
• Learning rate monotonically decreases and can become vanishingly small, causing premature convergence before reaching the optimum

RMSprop

• Uses exponential moving average of squared gradients: $E[g^2]_t = \rho E[g^2]_{t-1} + (1-\rho)g_t^2$ with typical $\rho = 0.9$
• Prevents learning rate decay by "forgetting" old gradients, maintaining effective updates throughout training
• Designed for non-stationary objectives where the loss surface changes during training—standard for recurrent neural networks

Adam (Adaptive Moment Estimation)

• Combines momentum and RMSprop by tracking both first moment $m_t$ (mean) and second moment $v_t$ (uncentered variance) of gradients
• Includes bias correction terms $\hat{m}_t = m_t/(1-\beta_1^t)$ and $\hat{v}_t = v_t/(1-\beta_2^t)$ to account for initialization at zero
• Default optimizer for deep learning due to robust performance across architectures with minimal hyperparameter tuning ($\beta_1=0.9$, $\beta_2=0.999$)

---

Second-Order and Quasi-Newton Methods: Curvature Information

These methods incorporate or approximate second-derivative information to achieve faster convergence. The trade-off is between the superior convergence rate and the cost of computing or storing curvature information.

L-BFGS (Limited-memory BFGS)

• Approximates the inverse Hessian using only the most recent $m$ gradient pairs (typically $m = 10$), requiring $O(mn)$ storage instead of $O(n^2)$
• Achieves superlinear convergence near the optimum by incorporating curvature information without explicit Hessian computation
• Preferred for convex optimization in statistics and classical ML (logistic regression, CRFs) where exact convergence matters more than mini-batch compatibility

Conjugate Gradient

• Generates search directions that are conjugate with respect to the Hessian, meaning $d_i^T H d_j = 0$ for $i \neq j$
• Solves $n$-dimensional quadratic problems in exactly $n$ iterations—optimal for least squares and linear systems $Ax = b$
• Memory efficient at $O(n)$ storage, making it ideal for large-scale problems where even L-BFGS's limited memory is too expensive

---

Quick Reference Table

---

Self-Check Questions

1. Which two algorithms both use momentum, and how does NAG's "lookahead" modification improve upon standard momentum?

2. Compare Adagrad and RMSprop: what problem does RMSprop solve, and why does this matter for training deep networks over many epochs?

3. You're training a model on a dataset with 10 million samples. Rank Batch GD, SGD, and Mini-batch GD in terms of (a) per-iteration cost and (b) convergence stability. Which would you choose and why?

4. Adam combines ideas from which two algorithms? Explain why bias correction is necessary in the early iterations of training.

5. An FRQ asks you to select an optimizer for fitting a logistic regression model to a moderately-sized convex problem where you need high precision. Would you choose Adam or L-BFGS? Justify your answer using convergence properties.