Gradient Descent

At its core, gradient descent is an iterative method for finding local minima of differentiable functions. The intuition is beautifully simple: if you are standing on a mountain in thick fog and want to reach the valley, feel the slope under your feet and take a step downhill. Repeat until you reach the bottom. Despite this simplicity, the algorithm's interplay with learning rate choice, batch size, and loss landscape geometry creates deep and rich behavior that demands careful study.

The Algorithm

Learning Rate

Choosing the Learning Rate

Batch Gradient Descent

Batch gradient descent computes the exact gradient using all training samples before each update. This guarantees the gradient direction is accurate but becomes prohibitively expensive for large datasets. Computing the full gradient requires forward and backward passes per iteration, which is infeasible when is in the millions.

Stochastic and Mini-batch Variants

Variant	Batch Size	Gradient Noise	Use Case
Batch GD	All	None	Small datasets, convex problems
Stochastic GD	1	High	Online learning, large-scale
Mini-batch GD		Moderate	Deep learning (default)

Convergence Analysis

Line Search Methods

Momentum

Why momentum helps: In narrow valleys, vanilla gradient descent oscillates wildly because the gradient alternates direction. Momentum averages these oscillations, smoothing the trajectory. On flat plateaus, momentum accumulates velocity and accelerates through regions where vanilla GD stalls. The effective learning rate is amplified by in consistent directions — with , this is a 10x speedup along persistent gradient directions.

Nesterov Accelerated Gradient

Nesterov momentum evaluates the gradient not at the current position but at the position we would arrive at if we continued with the current velocity. This "look-ahead" correction provides better convergence guarantees: for convex functions compared to for standard gradient descent. It is the theoretical foundation behind many practical accelerations.

Learning Rate Schedules

Warm restarts periodically reset the learning rate to a high value. The high learning rate helps escape sharp minima and saddle points, while the annealing within each cycle allows fine-grained convergence to flat, generalizable minima.

Schedule	Formula	Key Benefit
Constant		Simple baseline
Step decay		Adapts to progress
Exponential decay		Smooth, monotonic decrease
Cosine annealing		Smooth, periodic
Warm restart	Periodic cosine reset	Escapes local minima
Linear warmup	for	Stabilizes early training

Python Implementation

import numpy as np
import matplotlib.pyplot as plt


def gradient_descent(f, grad_f, x0, lr=0.01, n_iters=1000, tol=1e-6):
    """Vanilla gradient descent with convergence check."""
    x = x0.copy()
    history = [x.copy()]
    losses = [f(x)]

    for i in range(n_iters):
        grad = grad_f(x)
        x = x - lr * grad
        history.append(x.copy())
        losses.append(f(x))

        if np.linalg.norm(grad) < tol:
            break

    return x, np.array(history), losses


def momentum_gd(f, grad_f, x0, lr=0.01, beta=0.9, n_iters=1000, tol=1e-6):
    """Gradient descent with momentum."""
    x = x0.copy()
    v = np.zeros_like(x)
    history = [x.copy()]
    losses = [f(x)]

    for i in range(n_iters):
        grad = grad_f(x)
        v = beta * v + grad
        x = x - lr * v
        history.append(x.copy())
        losses.append(f(x))

        if np.linalg.norm(grad) < tol:
            break

    return x, np.array(history), losses


def nesterov_gd(f, grad_f, x0, lr=0.01, beta=0.9, n_iters=1000, tol=1e-6):
    """Gradient descent with Nesterov momentum."""
    x = x0.copy()
    v = np.zeros_like(x)
    history = [x.copy()]
    losses = [f(x)]

    for i in range(n_iters):
        grad = grad_f(x + lr * beta * (-v))
        v = beta * v + grad
        x = x - lr * v
        history.append(x.copy())
        losses.append(f(x))

        if np.linalg.norm(grad) < tol:
            break

    return x, np.array(history), losses


def cosine_annealing_lr(epoch, lr_min, lr_max, T):
    """Cosine annealing learning rate schedule."""
    return lr_min + 0.5 * (lr_max - lr_min) * (1 + np.cos(np.pi * epoch / T))


def step_decay_lr(epoch, lr_0, gamma, step_size):
    """Step decay learning rate schedule."""
    return lr_0 * (gamma ** (epoch // step_size))


# --- Example usage ---
f = lambda x: (x[0] - 2) ** 2 + (x[1] - 3) ** 2
grad_f = lambda x: np.array([2 * (x[0] - 2), 2 * (x[1] - 3)])

x0 = np.array([0.0, 0.0])

x_vanilla, hist_vanilla, losses_vanilla = gradient_descent(
    f, grad_f, x0, lr=0.1, n_iters=100
)
x_mom, hist_mom, losses_mom = momentum_gd(
    f, grad_f, x0, lr=0.1, beta=0.9, n_iters=100
)
x_nest, hist_nest, losses_nest = nesterov_gd(
    f, grad_f, x0, lr=0.1, beta=0.9, n_iters=100
)

print(f"Vanilla GD optimum: {x_vanilla}, iterations: {len(losses_vanilla)}")
print(f"Momentum GD optimum: {x_mom}, iterations: {len(losses_mom)}")
print(f"Nesterov GD optimum: {x_nest}, iterations: {len(losses_nest)}")

# Learning rate schedule visualization
epochs = range(200)
lr_cosine = [cosine_annealing_lr(e, 1e-4, 1e-1, 200) for e in epochs]
lr_step = [step_decay_lr(e, 1e-1, 0.5, 50) for e in epochs]

plt.figure(figsize=(10, 4))
plt.subplot(1, 2, 1)
plt.plot(epochs, lr_cosine, label="Cosine Annealing")
plt.plot(epochs, lr_step, label="Step Decay")
plt.xlabel("Epoch")
plt.ylabel("Learning Rate")
plt.legend()
plt.title("Learning Rate Schedules")

plt.subplot(1, 2, 2)
plt.plot(losses_vanilla, label="Vanilla GD")
plt.plot(losses_mom, label="Momentum GD")
plt.plot(losses_nest, label="Nesterov GD")
plt.xlabel("Iteration")
plt.ylabel("Loss")
plt.legend()
plt.title("Convergence Comparison")
plt.tight_layout()
plt.savefig("gd_comparison.png", dpi=150)
plt.show()

Applications in AI/ML

Neural Network Training

In practice, deep learning uses mini-batch SGD with momentum or Adam because:

Full-batch gradients are too expensive to compute for large datasets.
The noise in mini-batch gradients acts as implicit regularization.
Momentum accelerates convergence through consistent gradient directions.
Adam's per-parameter adaptive learning rates handle sparse features and varying curvatures.

Convex Optimization Connection

For convex problems like linear regression and SVMs, gradient descent has strong theoretical guarantees. The objective function has no local minima that are not global minima, and the convergence rate depends on the condition number . Gradient descent with exact line search achieves linear convergence for strongly convex functions.

Regularized Optimization

Gradient descent naturally handles regularized objectives. The gradient becomes . For L2 regularization (), the update becomes , which shrinks weights toward zero at every step — a phenomenon called weight decay.

Online Learning

Common Mistakes

Mistake	Why It's Wrong	Correct Approach
Using a constant high learning rate	Causes divergence and oscillation around the minimum	Use a learning rate schedule (cosine, step decay)
Ignoring gradient magnitude	A gradient norm of 0.001 and 100 require very different step sizes	Use adaptive methods (Adam) or gradient clipping
Not shuffling training data	Creates systematic bias in mini-batch gradients	Shuffle the dataset at each epoch
Setting batch size too small	Excessive gradient noise prevents convergence	Use batch sizes of 32–512 for stable training
Training without momentum	Slow convergence in ill-conditioned loss landscapes	Add momentum () as a default
Using vanilla GD for deep learning	Full-batch computation is prohibitively expensive	Use mini-batch SGD or Adam
Skipping learning rate warmup	Large initial gradients can destabilize early training	Warm up learning rate over the first few epochs
Not monitoring loss curves	Missing divergence, plateaus, or overfitting	Plot training and validation loss every epoch
Assuming convergence to global minimum	Non-convex problems may have many local minima and saddle points	Use multiple restarts or annealing to escape poor minima
Confusing gradient descent with Newton's method	GD uses first-order information only; Newton uses second-order curvature	Use Newton/BFGS for small problems, GD for large-scale

Interview Questions

Q1: Why is the learning rate the most important hyperparameter in gradient descent?

Q2: What is the difference between batch gradient descent, SGD, and mini-batch GD?

Q3: How does momentum improve gradient descent?

Q4: Explain the convergence guarantees of gradient descent for convex functions.

Q5: When would you choose SGD over Adam?

Second-Order Effects: Condition Number

Practice Problems

Problem 1: Manual Gradient Descent Step

Problem 2: Learning Rate Divergence

Problem 3: Momentum vs Vanilla GD

Problem 4: Cosine Annealing Schedule

Quick Reference

Cross-References

Stochastic Gradient Descent: Adam, RMSProp, and adaptive learning rate methods -> SGD
Newton's Method: Second-order optimization with Hessian information -> Newton's Method
Constrained Optimization: KKT conditions, penalty methods, and interior-point methods -> Constrained Optimization
Convex Optimization: Global optimality guarantees and convex function properties -> Convex Optimization
Hyperparameter Optimization: Learning rate tuning via grid search, Bayesian optimization -> Hyperparameter Optimization
Calculus Optimization: First and second derivative tests, unconstrained optimization -> Calculus Optimization
Partial Derivatives: Gradients and Jacobians needed for computing -> Partial Derivatives
Linear Algebra Norms: Vector norms used in convergence analysis -> Linear Algebra Norms

Gradient Descent