Gradient Descent Algorithm

Every neural network you've ever used—from the language model generating this text to the image classifier in your phone—learned its parameters through gradient descent. This simple yet profound algorithm is the beating heart of modern machine learning, transforming random initial weights into intelligent systems that recognize speech, translate languages, and diagnose diseases.

Gradient descent is elegantly simple in concept: to minimize a function, repeatedly take small steps in the direction that decreases it most steeply. Yet this simplicity belies remarkable depth. Understanding gradient descent deeply—its geometry, its dynamics, its failure modes, and its variants—is essential for any serious practitioner of machine learning.

Before diving into the algorithm, let's establish precisely what problem we're solving. In supervised machine learning, we have:

• A dataset $\mathcal{D} = {(\mathbf{x}_1, y_1), (\mathbf{x}_2, y_2), \ldots, (\mathbf{x}_n, y_n)}$ of input-output pairs
• A model $f(\mathbf{x}; \boldsymbol{\theta})$ parameterized by weights $\boldsymbol{\theta} \in \mathbb{R}^d$
• A loss function $\mathcal{L}(\hat{y}, y)$ measuring prediction error

Our goal is to find the parameters $\boldsymbol{\theta}^*$ that minimize the empirical risk—the average loss over our training data:

$$\boldsymbol{\theta}^* = \arg\min_{\boldsymbol{\theta}} J(\boldsymbol{\theta}) = \arg\min_{\boldsymbol{\theta}} \frac{1}{n} \sum_{i=1}^{n} \mathcal{L}(f(\mathbf{x}_i; \boldsymbol{\theta}), y_i)$$

Here, $J(\boldsymbol{\theta})$ is the cost function or objective function—a scalar-valued function of potentially millions of parameters that we must minimize.

Why can't we solve this analytically?

For simple linear regression, we can derive the optimal weights in closed form using the normal equations:

$$\boldsymbol{\theta}^* = (\mathbf{X}^T \mathbf{X})^{-1} \mathbf{X}^T \mathbf{y}$$

But this approach fails for most practical ML models because:

1. Non-linear models: Neural networks compose non-linear activations, making $J(\boldsymbol{\theta})$ non-convex with no closed-form minimum
2. Computational cost: Inverting an $n \times n$ matrix costs $O(n^3)$, prohibitive for large datasets
3. Memory: Storing the full matrix $\mathbf{X}^T \mathbf{X}$ may be impossible for big data

Iterative optimization algorithms like gradient descent overcome all these limitations.

Imagine standing on a mountainous terrain in thick fog—you can feel the local slope beneath your feet but can't see the overall landscape. Your goal is to reach the lowest valley. What strategy would you use?

The most natural approach: at each step, feel which direction goes downhill most steeply, take a step in that direction, and repeat. This is exactly gradient descent.

The loss landscape is a high-dimensional surface where:

• Each axis represents a model parameter $\theta_i$
• The height at any point represents the loss $J(\boldsymbol{\theta})$
• Valleys represent low-loss configurations (good models)
• Peaks represent high-loss configurations (bad models)

The gradient $ abla J(\boldsymbol{\theta})$ is a vector pointing in the direction of steepest ascent. To descend, we move in the opposite direction: $- abla J(\boldsymbol{\theta})$.

Why the negative gradient?

The gradient $ abla J(\boldsymbol{\theta})$ at point $\boldsymbol{\theta}$ is the vector of partial derivatives:

$$ abla J(\boldsymbol{\theta}) = \begin{bmatrix} \frac{\partial J}{\partial \theta_1} \ \frac{\partial J}{\partial \theta_2} \ \vdots \ \frac{\partial J}{\partial \theta_d} \end{bmatrix}$$

This vector points in the direction where $J$ increases most rapidly. By moving in the opposite direction, we descend the surface.

Key insight: Among all possible directions we could step, the negative gradient direction decreases the function value fastest (for infinitesimally small steps). This is provable from first-order Taylor expansion.

Now let's formalize the algorithm precisely. Gradient descent is an iterative optimization algorithm that updates parameters according to:

$$\boldsymbol{\theta}^{(t+1)} = \boldsymbol{\theta}^{(t)} - \alpha abla J(\boldsymbol{\theta}^{(t)})$$

where:

• $\boldsymbol{\theta}^{(t)}$ is the parameter vector at iteration $t$
• $\alpha > 0$ is the learning rate (also called step size)
• $ abla J(\boldsymbol{\theta}^{(t)})$ is the gradient evaluated at the current point

The algorithm terminates when convergence criteria are met (typically when the gradient norm falls below a threshold, or the loss stops decreasing significantly).

Algorithm Pseudocode (Formal)

Algorithm: Gradient Descent
Input: J(θ) - objective function
        ∇J(θ) - gradient function
        θ₀ - initial parameters
        α - learning rate
        ε - convergence threshold
        T - maximum iterations

1. t ← 0
2. while t < T and ||∇J(θₜ)|| > ε do
3.     gₜ ← ∇J(θₜ)           // Compute gradient
4.     θₜ₊₁ ← θₜ - α · gₜ    // Update parameters
5.     t ← t + 1
6. end while
7. return θₜ

This is the complete algorithm. Despite its simplicity, gradient descent (and its variants) trains everything from logistic regression to GPT-4.

Let's trace through gradient descent manually on a concrete example to build intuition.

Problem: Minimize $J(\theta) = \theta^2 + 4\theta + 5$

Step 1: Find the gradient $$\frac{dJ}{d\theta} = 2\theta + 4$$

Step 2: Initialize

• Initial guess: $\theta_0 = 3$
• Learning rate: $\alpha = 0.1$

Step 3: Iterate

Verification: The true minimum is at $\theta^* = -2$ (where $ abla J = 0$), and $J(-2) = 4 - 8 + 5 = 1$.

After 20 iterations, gradient descent found $\theta \approx -2.00$ with $J \approx 1.00$. Success!

Key observations from this example:

1. Initial loss was high (26), but decreased monotonically each iteration
2. Gradient magnitude decreased as we approached the minimum
3. Steps got smaller near the optimum because the gradient shrinks
4. The algorithm never overshoots the minimum with this learning rate

Now let's apply gradient descent to a real ML problem: linear regression.

Model: $\hat{y} = \mathbf{w}^T \mathbf{x} + b$

Loss function: Mean Squared Error (MSE) $$J(\mathbf{w}, b) = \frac{1}{2n} \sum_{i=1}^{n} (\mathbf{w}^T \mathbf{x}_i + b - y_i)^2$$

The factor of $\frac{1}{2}$ is conventional—it cancels with the exponent when differentiating.

Computing the gradients:

Let $\hat{y}_i = \mathbf{w}^T \mathbf{x}_i + b$ be the prediction for sample $i$.

$$\frac{\partial J}{\partial w_j} = \frac{1}{n} \sum_{i=1}^{n} (\hat{y}i - y_i) x{ij}$$

$$\frac{\partial J}{\partial b} = \frac{1}{n} \sum_{i=1}^{n} (\hat{y}_i - y_i)$$

In vector form: $$ abla_{\mathbf{w}} J = \frac{1}{n} \mathbf{X}^T (\mathbf{X}\mathbf{w} + b\mathbf{1} - \mathbf{y})$$ $$ abla_b J = \frac{1}{n} \mathbf{1}^T (\mathbf{X}\mathbf{w} + b\mathbf{1} - \mathbf{y})$$

Let's rigorously prove that gradient descent decreases the objective function (under appropriate conditions).

Theorem (Sufficient Decrease)

Let $J: \mathbb{R}^d \to \mathbb{R}$ be continuously differentiable with $L$-Lipschitz continuous gradient: $$| abla J(\mathbf{x}) - abla J(\mathbf{y})| \leq L |\mathbf{x} - \mathbf{y}| \quad \forall \mathbf{x}, \mathbf{y}$$

Then for learning rate $\alpha \leq \frac{1}{L}$, gradient descent satisfies: $$J(\boldsymbol{\theta}^{(t+1)}) \leq J(\boldsymbol{\theta}^{(t)}) - \frac{\alpha}{2} | abla J(\boldsymbol{\theta}^{(t)})|^2$$

Proof Sketch:

Using Taylor expansion with Lipschitz smoothness: $$J(\boldsymbol{\theta} - \alpha abla J) \leq J(\boldsymbol{\theta}) - \alpha | abla J|^2 + \frac{L \alpha^2}{2} | abla J|^2$$ $$= J(\boldsymbol{\theta}) - \alpha \left(1 - \frac{L\alpha}{2}\right) | abla J|^2$$

For $\alpha \leq \frac{1}{L}$, we have $1 - \frac{L\alpha}{2} \geq \frac{1}{2}$, giving: $$J(\boldsymbol{\theta}^{(t+1)}) \leq J(\boldsymbol{\theta}^{(t)}) - \frac{\alpha}{2} | abla J(\boldsymbol{\theta}^{(t)})|^2$$

Corollary (Guaranteed Progress)

As long as $| abla J(\boldsymbol{\theta})| > 0$ (we haven't reached a critical point), the loss decreases by at least $\frac{\alpha}{2} | abla J|^2$ per step.

Implications:

1. The loss monotonically decreases (with appropriate $\alpha$)
2. Larger gradients → larger decrease — far from optima, we make fast progress
3. Near local minima, gradients shrink — progress slows but convergence happens
4. The learning rate upper bound $1/L$ — too large $\alpha$ violates the bound and can cause divergence

This theorem is the theoretical foundation for gradient descent's reliability on smooth functions.

The loss surface (or loss landscape) is the graph of $J(\boldsymbol{\theta})$ over parameter space. Understanding its topology is crucial for optimization.

Types of Critical Points:

The Hessian matrix $\mathbf{H} = abla^2 J$ captures local curvature. Its eigenvalues determine the nature of critical points.

Convex vs Non-Convex Landscapes

Convex functions (like MSE loss for linear regression) have a bowl-shaped landscape:

• Single global minimum
• No local minima or saddle points
• Gradient descent converges to optimal solution from any starting point

Non-convex functions (like neural network losses) have complex landscapes:

• Multiple local minima
• Saddle points (very common in high dimensions)
• Plateaus with near-zero gradient
• Gradient descent behavior depends heavily on initialization

Modern insight: In high-dimensional neural networks, local minima are often nearly as good as the global minimum. The real challenge is escaping saddle points and plateaus.