Gradient Descent Variants

At the heart of virtually every machine learning algorithm lies a deceptively simple idea: find the parameters that minimize a loss function by iteratively moving in the direction of steepest descent. This is gradient descent—the workhorse algorithm that powers everything from logistic regression to transformers with billions of parameters.

Batch gradient descent, also known as full-batch gradient descent or simply vanilla gradient descent, represents the purest form of this optimization paradigm. Before we can appreciate the sophistication of modern optimizers like Adam or understand why stochastic methods work, we must first master this foundational algorithm in its complete, unmodified form.

This page provides an exhaustive treatment of batch gradient descent: its mathematical foundations, geometric intuitions, convergence guarantees, implementation considerations, and the fundamental limitations that motivated all subsequent innovations in optimization.

To understand batch gradient descent rigorously, we must first establish the precise mathematical setting. Consider a supervised learning problem where we have a dataset of N training examples:

$$\mathcal{D} = {(\mathbf{x}^{(1)}, y^{(1)}), (\mathbf{x}^{(2)}, y^{(2)}), \ldots, (\mathbf{x}^{(N)}, y^{(N)})}$$

Our goal is to find parameters $\boldsymbol{\theta} \in \mathbb{R}^d$ that minimize the empirical risk—the average loss over all training examples:

$$J(\boldsymbol{\theta}) = \frac{1}{N} \sum_{i=1}^{N} \mathcal{L}(f_{\boldsymbol{\theta}}(\mathbf{x}^{(i)}), y^{(i)})$$

Here, $f_{\boldsymbol{\theta}}$ is our model parameterized by $\boldsymbol{\theta}$, and $\mathcal{L}$ is a loss function measuring the discrepancy between predictions and targets.

The Gradient Descent Update Rule

Batch gradient descent updates parameters by moving in the opposite direction of the gradient:

$$\boldsymbol{\theta}^{(t+1)} = \boldsymbol{\theta}^{(t)} - \eta \nabla_{\boldsymbol{\theta}} J(\boldsymbol{\theta}^{(t)})$$

where:

• $\boldsymbol{\theta}^{(t)}$ denotes the parameters at iteration $t$
• $\eta > 0$ is the learning rate (also called step size)
• $\nabla_{\boldsymbol{\theta}} J(\boldsymbol{\theta}^{(t)})$ is the gradient computed over the entire dataset

Expanding the gradient explicitly:

$$\nabla_{\boldsymbol{\theta}} J(\boldsymbol{\theta}) = \frac{1}{N} \sum_{i=1}^{N} \nabla_{\boldsymbol{\theta}} \mathcal{L}(f_{\boldsymbol{\theta}}(\mathbf{x}^{(i)}), y^{(i)})$$

This is the defining characteristic of batch gradient descent: at each iteration, we compute gradients with respect to every single training example and average them before making a parameter update.

Understanding gradient descent geometrically provides crucial intuition for debugging optimization problems and selecting hyperparameters. Let's build this understanding from first principles.

The Loss Surface

The objective function $J(\boldsymbol{\theta})$ defines a loss surface (or loss landscape) over the parameter space. For a model with $d$ parameters, this is a surface in $(d+1)$-dimensional space—$d$ dimensions for parameters and one for the loss value.

• Valleys represent regions of low loss (good parameters)
• Peaks and ridges represent regions of high loss (bad parameters)
• Saddle points are flat regions that are neither minima nor maxima

The gradient $\nabla J(\boldsymbol{\theta})$ at any point is a vector that:

1. Points in the direction of steepest ascent on the loss surface
2. Has magnitude equal to the rate of steepest ascent

By moving in the negative gradient direction, we descend the loss surface toward lower values.

Why Negative Gradient Works

Consider the first-order Taylor expansion of $J$ around the current point $\boldsymbol{\theta}^{(t)}$:

$$J(\boldsymbol{\theta}^{(t)} + \boldsymbol{\delta}) \approx J(\boldsymbol{\theta}^{(t)}) + \nabla J(\boldsymbol{\theta}^{(t)})^\top \boldsymbol{\delta}$$

To minimize $J$, we want to choose $\boldsymbol{\delta}$ such that $J(\boldsymbol{\theta}^{(t)} + \boldsymbol{\delta}) < J(\boldsymbol{\theta}^{(t)})$. This requires:

$$\nabla J(\boldsymbol{\theta}^{(t)})^\top \boldsymbol{\delta} < 0$$

The most negative this inner product can be (for a fixed $|\boldsymbol{\delta}|$) is achieved when $\boldsymbol{\delta}$ points exactly opposite to the gradient:

$$\boldsymbol{\delta} = -\eta \nabla J(\boldsymbol{\theta}^{(t)})$$

This is precisely the gradient descent update! The negative gradient is the direction of steepest local descent.

Visualizing Different Landscapes

The behavior of gradient descent varies dramatically depending on the loss landscape:

1. Convex quadratic: The ideal case. Contours are ellipsoids, and gradient descent moves directly toward the minimum (if the Hessian is isotropic) or follows a zig-zag path if contours are elongated.

2. Convex non-quadratic: Guaranteed to converge to the global minimum, but the path may be more complex.

3. Non-convex: The typical case in deep learning. Multiple local minima, saddle points, and flat regions make optimization challenging.

4. Ravines and narrow valleys: Causes oscillation across the valley walls while slow progress along the valley floor—a major motivation for momentum methods.

5. Plateau regions: Gradient nearly vanishes, causing extremely slow progress despite being far from any minimum.

Let's formalize the batch gradient descent algorithm and examine a rigorous implementation. Understanding the precise algorithmic steps is essential before we can appreciate the modifications introduced by more sophisticated optimizers.

Algorithm: Batch Gradient Descent

Input: Initial parameters θ₀, learning rate η, dataset D, max iterations T, tolerance ε
Output: Optimized parameters θ*

1. t ← 0
2. while t < T and ||∇J(θᵗ)|| > ε:
      a. Compute gradient: g ← (1/N) Σᵢ ∇L(f_θᵗ(xⁱ), yⁱ)  // Over ALL N examples
      b. Update parameters: θᵗ⁺¹ ← θᵗ - η·g
      c. t ← t + 1
3. return θᵗ

Notice that step 2a requires a full pass through the entire dataset for each parameter update. This is the computational signature of batch gradient descent.

Understanding when and how fast gradient descent converges is crucial for both theoretical guarantees and practical hyperparameter tuning. The convergence properties depend critically on the properties of the objective function.

Key Definitions

Before stating convergence results, we need several important definitions:

Lipschitz Continuity of the Gradient: The gradient $\nabla J$ is $L$-Lipschitz if: $$|\nabla J(\boldsymbol{\theta}) - \nabla J(\boldsymbol{\phi})| \leq L |\boldsymbol{\theta} - \boldsymbol{\phi}|$$ for all $\boldsymbol{\theta}, \boldsymbol{\phi}$. The constant $L$ is called the smoothness parameter.

Strong Convexity: The function $J$ is $\mu$-strongly convex if: $$J(\boldsymbol{\phi}) \geq J(\boldsymbol{\theta}) + \nabla J(\boldsymbol{\theta})^\top(\boldsymbol{\phi} - \boldsymbol{\theta}) + \frac{\mu}{2}|\boldsymbol{\phi} - \boldsymbol{\theta}|^2$$ Strong convexity ensures a unique global minimum and prevents 'flat' regions.

Condition Number: For a strongly convex function with $L$-Lipschitz gradient, the condition number is: $$\kappa = \frac{L}{\mu}$$ This ratio fundamentally governs convergence speed—higher $\kappa$ means slower convergence.

Convergence Theorems

Theorem 1 (Convergence for Smooth Functions)

If $J$ has $L$-Lipschitz continuous gradient and $\eta \leq \frac{1}{L}$, then batch gradient descent satisfies:

$$J(\boldsymbol{\theta}^{(T)}) - J(\boldsymbol{\theta}^) \leq \frac{|\boldsymbol{\theta}^{(0)} - \boldsymbol{\theta}^|^2}{2\eta T}$$

This is a sublinear convergence rate of $O(1/T)$—to reduce the error by a factor of 10, we need 10× more iterations.

Theorem 2 (Convergence for Strongly Convex Functions)

If $J$ is $\mu$-strongly convex with $L$-Lipschitz gradient and $\eta = \frac{1}{L}$, then:

$$|\boldsymbol{\theta}^{(T)} - \boldsymbol{\theta}^|^2 \leq \left(1 - \frac{\mu}{L}\right)^T |\boldsymbol{\theta}^{(0)} - \boldsymbol{\theta}^|^2$$

This is linear convergence (also called geometric or exponential convergence). The error decreases by a constant factor $(1 - 1/\kappa)$ at each step.

Practical Implications

1. Learning rate bounds: The convergence theorems provide concrete guidance: $\eta \leq 1/L$ ensures convergence. If you see divergence (loss exploding), your learning rate likely violates this bound.

2. Condition number determines difficulty: Problems with $\kappa \approx 1$ (isotropic) converge quickly. Problems with $\kappa >> 1$ (ill-conditioned) converge slowly and may require preconditioning or adaptive methods.

3. Non-convex reality: Deep learning loss surfaces are non-convex. We can't guarantee finding global minima, but gradient descent still finds stationary points (where $\nabla J \approx 0$).

The learning rate $\eta$ is the single most critical hyperparameter in gradient descent. Its value determines whether optimization succeeds, fails spectacularly, or crawls painfully slowly. Let's develop a deep understanding of learning rate dynamics.

The Stability Analysis

Consider optimizing a simple quadratic: $J(\theta) = \frac{1}{2}a\theta^2$ where $a > 0$. The gradient is $\nabla J = a\theta$, so the update becomes:

$$\theta^{(t+1)} = \theta^{(t)} - \eta \cdot a \cdot \theta^{(t)} = (1 - \eta a)\theta^{(t)}$$

For convergence to $\theta^* = 0$, we need $|1 - \eta a| < 1$, which requires:

$$0 < \eta < \frac{2}{a}$$

This is the stability condition. When $\eta > 2/a$, the updates overshoot and oscillate with increasing magnitude—the optimization diverges.

The Three Regimes of Learning Rate

1. Too Large ($\eta > 2/L$): Divergence

• Updates overshoot the minimum
• Loss increases instead of decreasing
• Parameters may become NaN
• Symptom: Loss explodes or oscillates wildly

2. Too Small ($\eta << 1/L$): Slow Convergence

• Each update makes minimal progress
• May take millions of iterations to converge
• Gets stuck in noisy regions for a long time
• Symptom: Loss decreases but painfully slowly

3. Just Right ($\eta \approx 1/L$): Optimal Convergence

• Near-optimal convergence rate
• Stable and efficient
• Makes meaningful progress each iteration
• Symptom: Loss decreases steadily and reasonably quickly

Finding the Right Learning Rate

In practice, since we don't know $L$ exactly, we use empirical strategies:

1. Grid search: Try values ${10^{-5}, 10^{-4}, 10^{-3}, 10^{-2}, 10^{-1}}$ and pick the largest that converges

2. Learning rate finder: Exponentially increase $\eta$ during a short training run and plot loss vs. learning rate. Choose $\eta$ just before loss starts increasing.

3. Backtracking line search: Start with large $\eta$ and halve it until $J(\theta - \eta \nabla J) < J(\theta)$ (Armijo condition).

4. Adaptive methods: Use algorithms like Adam that automatically adjust per-parameter learning rates (covered later in this module).

Understanding the computational cost of batch gradient descent is essential for determining its applicability to different problem scales. Let's analyze the time and space complexity rigorously.

Time Complexity per Iteration

For a dataset with $N$ examples and a model with $d$ parameters:

• Forward pass: Computing $f_\theta(\mathbf{x}^{(i)})$ for all $N$ examples: $O(N \cdot C_f)$ where $C_f$ is the cost of one forward pass

• Gradient computation: Computing $\nabla_\theta \mathcal{L}$ for all $N$ examples via backpropagation: $O(N \cdot C_b)$ where $C_b \approx C_f$ (backward pass is similar cost)

• Gradient averaging: Summing $N$ gradients: $O(N \cdot d)$

• Parameter update: One vector subtraction: $O(d)$

For neural networks, $C_f$ and $C_b$ are proportional to the number of parameters $d$, giving:

$$\text{Time per iteration} = O(N \cdot d)$$

The Scalability Problem

Let's make this concrete with real numbers:

For a modern dataset with millions of examples, a single iteration of batch gradient descent can take hours or days. Since training typically requires thousands of iterations, batch gradient descent becomes completely impractical.

This is the fundamental problem that stochastic gradient descent solves: instead of using all $N$ examples per update, use a small subset. We trade gradient accuracy for computational speed—and as we'll see, this trade-off is extremely favorable.

While batch gradient descent has strong theoretical properties, it suffers from several practical limitations that severely restrict its usefulness in modern machine learning.

Limitation 1: Computational Expense

As analyzed above, the $O(N \cdot d)$ cost per iteration becomes prohibitive for large datasets. But it's worse than just slow—the cost is unavoidable for each update. Even if the first 100 examples would give you a 'good enough' gradient direction, you still must process all $N$ examples before making any progress.

Limitation 2: Memory Requirements

Batch gradient descent requires either:

• Loading entire dataset into memory (often impossible for large datasets)
• Making $N$ disk reads per iteration (extremely slow)

Modern datasets can be terabytes in size. Holding them in RAM is simply not feasible.

Limitation 3: No Implicit Regularization

Stochastic methods benefit from noise in the gradient estimates, which acts as a form of regularization. Batch gradient descent, with its exact gradients, lacks this beneficial noise. This often leads to finding sharper minima that generalize worse.

Limitation 4: Sensitivity to Curvature

A single learning rate must work for all parameters. But different parameters may need different step sizes:

• Some parameters have high curvature (steep loss) → need small steps
• Other parameters have low curvature (flat loss) → need large steps

Using one fixed $\eta$ for all parameters is fundamentally suboptimal. This motivates adaptive learning rate methods like AdaGrad, RMSprop, and Adam, which we'll cover later.

Limitation 5: Deterministic Path

Batch gradient descent follows a completely deterministic path given the initial parameters. This means:

• No chance to 'jump out' of poor local regions via gradient noise
• No implicit exploration of the loss landscape
• The minimum found depends entirely on initialization

Despite its limitations, batch gradient descent remains the right choice in certain scenarios. Understanding these use cases helps you make informed optimizer choices.

Appropriate Use Cases

1. Very small datasets ($N < 1000$): When the entire dataset fits easily in memory and gradient computation is fast, the simplicity and stability of batch GD is advantageous.

2. Convex optimization problems: For convex losses (logistic regression, linear regression, SVMs), batch GD provides reliable convergence with well-understood behavior.

3. When exact gradients are required: Some scenarios require precise gradients, such as second-order optimization methods that depend on accurate Hessian-vector products.

4. Debugging and prototyping: When developing new models, batch GD's deterministic behavior makes debugging easier. You can reproduce exact training trajectories.

5. Fine-tuning with stability requirements: When stability matters more than speed (e.g., fine-tuning a nearly-converged model), exact gradients prevent the noise-induced oscillation of stochastic methods.

Historical and Pedagogical Importance

Even if you never use pure batch gradient descent in practice, understanding it deeply is valuable:

• Foundation for theory: Convergence theorems, learning rate analysis, and stability conditions extend (with modifications) to all gradient-based methods.

• Baseline for comparison: When evaluating new optimizers, batch GD provides a clear baseline. Any new method should outperform it on relevant metrics.

• Building intuition: The geometric and mathematical understanding developed here applies directly to understanding more sophisticated methods.

In the next pages, we'll see how stochastic gradient descent addresses the major limitations of batch GD while preserving the core gradient descent paradigm.

We've completed a thorough examination of batch gradient descent—the foundational optimization algorithm. Let's consolidate the key insights:

What's Next

The next page introduces Stochastic Gradient Descent (SGD)—the revolutionary modification that makes gradient-based optimization practical for large-scale machine learning. We'll see how using a single example (or small batch) instead of the full dataset dramatically changes the optimization dynamics while still converging to good solutions.