Gradient DescentWalking Downhill in Mathematics

A model is a rule with knobs. A line \(y = mx + b\) has two knobs, \(m\) and \(b\). An error function such as

scores any knob setting with one number: how wrong the predictions are. Optimization is the process of finding the best parameters for our function by minimizing errors. Gradient descent is a general optimization algorithm from calculus, and it is not private to one model. Linear regression, logistic regression, neural networks, SVMs, all of them hand their cost function to this same walker and ask it to find the bottom.

It minimizes a function by moving in the direction of steepest decrease. To do that it first needs to know which way is steep, and that is the job of the gradient.

In one variable the gradient is just the derivative, the slope of the curve at a point. Take \(f(x) = x^2\), so \( \frac{df}{dx} = 2x \):

Read the sign as a compass. At \(x = 3\) the gradient is +6: moving right increases the cost, moving left decreases it. At \(x = -3\) it is −6: the exact mirror. The gradient always points uphill, so the negative gradient points downhill, toward the minimum at \(x = 0\). A larger magnitude means a steeper slope.

With two or more variables the gradient becomes the vector of all partial derivatives, one slope per direction. For a cost \(J(m, c)\):

\(\partial J / \partial m\) says how sensitive the cost is to the slope \(m\); \(\partial J / \partial c\) says how sensitive it is to the intercept \(c\). In one phrase: how much the cost changes if we change that parameter slightly. Example, \( f(x, y) = x^2 + y^2 \):

At the point \((1,2)\) the surface (a 3D bowl) rises with slope 2 along the x-direction and slope 4 along the y-direction. The vector \([2, 4]\) packs two answers at once: direction, which way is steepest uphill, and magnitude, how steep that climb is.

If the gradient points uphill, learning is one line: step the other way. For any parameter collection \(\theta\) (linear regression's note calls the same collection \(\beta\); it's a naming choice, not a different idea):

Component by component, for linear regression:

The recipe in full:

A lovely built-in behaviour: the step size is \( \alpha \times \text{slope} \), and the slope shrinks as you approach the bottom. So gradient descent naturally takes big steps when far away and baby steps when close, even with a fixed \(\alpha\).

The learning rate is a hyperparameter, a setting we choose rather than learn. It controls how much the parameters are updated per iteration based on the gradient, and it determines how fast and how stable gradient descent learns:

Don't take the table's word for it. Break it yourself. The cost curve below is \( J(\theta_0) = (\theta_0 - 25)^2 \), the exam-score example from the linear regression note. Try \(\alpha = 0.1\), then 0.5, then exactly 1.0, then 1.05:

To trust the machine, do one example on paper. Training data \((1,1), (2,2), (3,3)\), model \( h_\theta(x) = \theta_0 + \theta_1 x \) with \(\theta_0\) pinned at 0, and the halved cost

When \(\theta_1 = 1\): predictions 1, 2, 3 match the actuals exactly, every error is \((1-1)^2 = 0\), so

When \(\theta_1 = 0.5\): predictions 0.5, 1, 1.5 against actuals 1, 2, 3:

When \(\theta_1 = 0\): the model predicts 0 everywhere, \( J(0,0) = \frac{1+4+9}{6} = \frac{14}{6} \approx 2.33 \). And by the same arithmetic, \( J(0, 1.5) \approx 0.58 \) and \( J(0, 2) \approx 2.33 \). Plotting the five values:

A perfect U with its global minimum at \(\theta_1 = 1\), which is exactly the true line \(y = x\). The minimum is the point where any small change in the parameters increases the error. Gradient descent is nothing more than an automated way of sliding down this table.

Where do the update formulas come from? Differentiate the cost of a single example, \( \tfrac{1}{2}(h_\theta(x) - y)^2 \), with respect to one parameter \(\theta_j\). Chain rule, outside first, then inside:

Every other \(\theta_i x_i\) is a constant with respect to \(\theta_j\), so it differentiates to zero. Summing over the dataset gives the batch gradients used in the linear regression note:

The same computation without the \(\tfrac12\) convention leaves a factor of 2 in front, \( \frac{\partial E}{\partial m} = -\frac{2}{n}\sum x_i\big(y_i - (mx_i + b)\big) \) and \( \frac{\partial E}{\partial b} = -\frac{2}{n}\sum \big(y_i - (mx_i + b)\big) \). Identical direction, only the scale differs, and the learning rate absorbs scale.

Historically this per-example update rule, \( \theta_j := \theta_j - \alpha\,\big(h_\theta(x^{(i)}) - y^{(i)}\big) x_j^{(i)} \), is called the Least Mean Squares (LMS) rule: initialize \(\theta\) randomly, then for each training example compute the prediction \(h_\theta(x) = \theta^{\mathsf T}x\), compute the error, update each parameter, and stop when \(J(\theta)\) becomes sufficiently small or the changes in \(\theta\) are very small.

The gradients above contain a sum over all \(m\) examples. When to compute that sum is a real design choice.

Stochastic descent repeats for multiple epochs, full passes over the shuffled dataset: for each training example, compute the prediction, compute the gradients from that single point, update. In practice most modern training uses the compromise, mini-batch gradient descent, small batches of 32 or 64 examples, blending batch's stability with stochastic's speed.

Where you can get to depends on the shape of the landscape. Two definitions first. A global minimum is a point where the function value is lower than at all other points in the entire domain; it is the lowest possible value the cost can attain, the best possible parameters. Local minima are points where the function value is lower than their nearby points, but not the lowest overall.

A function \(f\) is convex if for any two points \(x_1, x_2\) in its domain and any \(\lambda \in [0, 1]\):

Geometrically, any straight line connecting two points on the curve stays on or above the curve everywhere in between. Convex means curving upward, and a convex function has exactly one minimum, the global one. If we optimize a convex function we're sure we will always find the global minimum. A function is non-convex if at least one straight chord dips below the curve somewhere. Non-convex surfaces have multiple peaks and valleys, and an optimizer can settle into a local valley and miss the global bottom.

In linear regression the cost function is a parabola in one parameter and a bowl in two, always convex, one global minimum and no local minima to worry about, so gradient descent is guaranteed to find the best coefficients. There is even a clean theorem behind the guarantee:

If the cost function \(J(\theta)\) is convex and differentiable with L-Lipschitz continuous gradients, and the learning rate satisfies \( 0 < \alpha \le \tfrac{1}{L} \), then gradient descent converges to the global minimum of \(J(\theta)\). convergence theorem of gradient descent

L-Lipschitz gradients simply means the slope can't change faster than some constant \(L\), the curvature is bounded, so a step of size \(1/L\) can never overshoot badly. That is figure 02's lesson wearing formal clothes.

In non-linear models (deep networks especially) the loss surface is non-convex and the cost surface changes shape, so no such guarantee exists. That is why initialization, learning-rate schedules, and stochastic noise, which can shake a walker out of shallow local dips, matter so much in deep learning.

# batch gradient descent for y = w*x + b, data: exam scores
import numpy as np
x = np.array([1, 2, 3]);  y = np.array([35, 45, 55])
w, b, alpha = 0.0, 0.0, 0.1

for step in range(1000):
    y_hat = w * x + b                      # predictions
    error = y_hat - y                      # how wrong, per point
    g_w = (error * x).mean()               # ∂J/∂w
    g_b = error.mean()                     # ∂J/∂b
    w -= alpha * g_w                       # step downhill
    b -= alpha * g_b
    if abs(g_w) < 1e-9 and abs(g_b) < 1e-9: # gradient ≈ 0 → converged
        break

print(round(w, 3), round(b, 3))            # → 10.0 25.0, marks = 10·hours + 25

Change alpha to 1.5 and watch the numbers explode, figure 02 again, this time in your terminal.

• Andrew Ng · CS229 Lecture Notes, Stanford · Part I, LMS algorithm, batch & stochastic gradient descent
• Stephen Boyd, Lieven Vandenberghe · Convex Optimization · convexity and descent methods
• Ian Goodfellow, Yoshua Bengio, Aaron Courville · Deep Learning · chapter 4.3, gradient-based optimization
• Companion notes in this series: Linear Regression · Logistic Regression