Gradient descent

Gradient descent is the algorithm that trains most machine learning models, from linear regression to the largest neural networks. The idea is simple: measure which direction makes the cost go up, and step the other way. Repeat until the steps stop helping.

The intuition

Imagine standing on a hillside in fog. You cannot see the valley, but you can feel the slope under your feet. Take a step downhill, feel the slope again, step again. Eventually you reach the bottom.

The hillside is the cost function $J(w, b)$. Your position is the current values of $w$ and $b$. The slope is the gradient.

The gradient

The gradient is the vector of partial derivatives of the cost with respect to each parameter. For mean squared error with the model $\hat{y} = wx + b$:

Each says how much the cost would change if you nudged that parameter up a tiny bit. A positive gradient means "increasing this makes things worse", so you decrease it.

The update rule

$\alpha$ (alpha) is the learning rate: how big a step to take. Both parameters are updated together using gradients computed at the old values.

Implementing it from scratch

import numpy as np

x = np.array([1, 2, 3, 4, 5], dtype=float)
y = np.array([3, 5, 7, 9, 11], dtype=float)   # true line: y = 2x + 1

w, b = 0.0, 0.0
alpha = 0.05
m = len(x)

for step in range(1, 201):
    y_hat = w * x + b
    error = y_hat - y
    dw = (2 / m) * (error * x).sum()
    db = (2 / m) * error.sum()
    w -= alpha * dw
    b -= alpha * db
    if step in (1, 10, 50, 200):
        cost = (error ** 2).mean()
        print(f"step {step:3d}: w={w:.3f} b={b:.3f} cost={cost:.4f}")

Watch the cost fall and the parameters approach 2 and 1.

Choosing the learning rate

• Too small: it works, but takes thousands of steps.
• Too large: each step overshoots the bottom and the cost grows, eventually to infinity.

import numpy as np

x = np.array([1, 2, 3, 4, 5], dtype=float)
y = np.array([3, 5, 7, 9, 11], dtype=float)

def run(alpha, steps=30):
    w, b = 0.0, 0.0
    for _ in range(steps):
        error = w * x + b - y
        w -= alpha * (2 / len(x)) * (error * x).sum()
        b -= alpha * (2 / len(x)) * error.sum()
    return ((w * x + b - y) ** 2).mean()

for alpha in (0.001, 0.01, 0.05, 0.1):
    print(f"alpha={alpha}: cost after 30 steps = {run(alpha):.3g}")

Try 0.15 and watch it diverge. Feature scaling helps enormously here: when features are on similar ranges, one learning rate works for all of them.

Variants

• Batch gradient descent uses every example for each step. Accurate but slow on big data.
• Stochastic gradient descent (SGD) uses one example per step. Noisy but fast, and the noise can help escape shallow local minima.
• Mini-batch uses a small group (32 to 512 examples) per step. This is the default in deep learning; it balances speed and stability and suits GPUs.

Improvements such as momentum, RMSProp and Adam adapt the step size per parameter and remember previous directions. Adam is the usual default for neural networks.

Convergence

Stop when the cost changes by less than a tiny threshold between steps, or after a fixed number of epochs (full passes over the data). Plotting cost against step count is the standard diagnostic: it should fall quickly then flatten.

In scikit-learn

SGDRegressor and SGDClassifier train linear models with stochastic gradient descent. They need scaled features.

import numpy as np
from sklearn.linear_model import SGDRegressor
from sklearn.preprocessing import StandardScaler
from sklearn.pipeline import make_pipeline

X = np.array([[1], [2], [3], [4], [5]], dtype=float)
y = np.array([3, 5, 7, 9, 11], dtype=float)

model = make_pipeline(StandardScaler(), SGDRegressor(max_iter=1000, tol=1e-6, random_state=0)).fit(X, y)
print(model.predict([[6]]).round(2))

Practice

1. Modify the from scratch loop to stop automatically when the cost improves by less than 1e-8 between steps, and print how many steps it took.
2. Rerun it with x scaled up by 100 and no other changes. What happens, and why does scaling fix it?
3. Implement mini-batch gradient descent with a batch size of 2.