Week 1: Optimization for Learning

What is optimization for learning#

Every machine learning model, whether a linear regressor, a decision tree, or a transformer with billions of parameters, starts from the same template: choose a model $f_\theta$ parameterised by a vector $\theta$, measure how wrong it is with a loss $\ell(\hat y, y)$, and average that loss over a dataset of $n$ examples. The result is the objective function (also called the cost or the empirical risk):

$J(\theta) = \frac{1}{n} \sum_{i=1}^n \ell(f_\theta(x_i), y_i)$

"Training" the model means finding the $\theta$ that makes $J(\theta)$ as small as possible:

$\theta^* = \arg\min_\theta J(\theta)$

This is exactly an optimization problem. The machinery of this course, covering convexity, gradient methods, and convergence rates, exists to solve equation $(\ast)$ efficiently and reliably for machine learning objectives.

Setting the derivative to zero yields a closed-form solution for a linear model with squared error loss (Week 4). For most modern models, such as deep nets, tree ensembles, and generative models, $J(\theta)$ is a nonconvex function of millions of parameters without a closed form. The practical route is to start somewhere and take small steps downhill.

Empirical risk minimization#

The name ERMEmpirical Risk Minimization captures the idea: we empirically measure risk on the data we have, then minimise it. Two things matter:

1. The loss $\ell(\hat y, y)$ encodes what "wrong" means. For regression, $\ell(\hat y, y) = (\hat y - y)^2$ (squared error). For classification, $\ell$ is cross-entropy (Week 5).
2. The data $\{(x_i, y_i)\}$ is a finite sample from some unknown distribution. ERM minimises the average on this sample, hoping it generalises to the distribution.

The rest of this course focuses on the minimisation part. The generalisation part (why minimising training loss also minimises test loss) belongs to statistical learning theory, though we will touch it when we discuss overparameterisation in Week 13.

Worked example: linear regression as ERM.

Take $\theta = w \in \mathbb{R}^d$, model $f_w(x) = w^T x$, and squared error loss $\ell(\hat y, y) = (\hat y - y)^2$. Then

$J(w) = \frac{1}{n}\sum_{i=1}^n (w^T x_i - y_i)^2 = \frac{1}{n}\|Xw - y\|_2^2$

where $X \in \mathbb{R}^{n \times d}$ stacks the $x_i$ as rows and $y \in \mathbb{R}^n$ stacks the labels. This is a convex quadratic in $w$, one of the simplest ERM problems. Weeks 3 and 4 build on this form.

Gradients and the chain rule#

To take steps downhill, we need to know which direction is down. For a scalar-valued function $f: \mathbb{R}^d \to \mathbb{R}$, the gradient $\nabla f(x)$ is the vector of partial derivatives:

$\nabla f(x) = \begin{pmatrix} \frac{\partial f}{\partial x_1}(x) \\ \vdots \\ \frac{\partial f}{\partial x_d}(x) \end{pmatrix}$

At any point $x$, $\nabla f(x)$ points in the direction of steepest ascent. So $-\nabla f(x)$ points downhill.

The chain rule for vector functions is the workhorse of modern ML. Suppose $f(x) = g(h(x))$ where $h: \mathbb{R}^d \to \mathbb{R}^p$ and $g: \mathbb{R}^p \to \mathbb{R}$. Then

$\nabla f(x) = \nabla h(x)^T \, \nabla g(h(x))$

where $\nabla h(x)$ is the $p \times d$ Jacobian of $h$ (row $i$ holds the gradient of the $i$-th output component).

Worked numeric example: quadratic gradient.

Let $f(w) = \frac{1}{2}(w_1^2 + 2 w_2^2)$. The gradient is

$\nabla f(w) = \begin{pmatrix} \frac{\partial f}{\partial w_1} \\ \frac{\partial f}{\partial w_2} \end{pmatrix} = \begin{pmatrix} w_1 \\ 2 w_2 \end{pmatrix}$

At $w = (4, 4)$, we have $\nabla f(4,4) = (4, 8)$. The function is steeper in the $w_2$ direction.

Chain rule worked example: linear regression gradient.

With $f(w) = \frac{1}{2}\|Xw - y\|_2^2$, let $r = Xw - y$ (the residual). Then $f = \frac{1}{2}\|r\|_2^2 = \frac{1}{2}r^T r$. By the chain rule:

$\nabla f(w) = X^T(Xw - y)$

For a single data point $f_i(w) = \frac{1}{2}(w^T x_i - y_i)^2$, we get $\nabla f_i(w) = (w^T x_i - y_i) x_i$, which is a scalar times the feature vector. This simple form makes SGD (Week 6) cheap per example.

Gradient descent#

The gradient descent algorithm is wonderfully simple: start at $x_0$, then repeatedly move a small step in the negative gradient direction:

$x_{k+1} = x_k - \eta \nabla f(x_k)$

where $\eta > 0$ is the step size (also called the learning rate).

Choosing $\eta$ is the central tuning problem. Too small and you crawl toward the minimum (underfitting in training-budget terms). Too large and you overshoot, possibly diverging.

Worked manual iteration: 2D quadratic.

Take $f(w_1, w_2) = \frac{1}{2}(w_1^2 + 2 w_2^2)$ with gradient $\nabla f(w) = (w_1, 2w_2)$. Start at $w^{(0)} = (4, 4)$ with $\eta = 0.3$.

• $k = 0$: $w^{(0)} = (4, 4)$, gradient $= (4, 8)$
• Step: $w^{(1)} = (4, 4) - 0.3 \cdot (4, 8) = (2.8, 1.6)$
• $k = 1$: gradient at $(2.8, 1.6)$ is $(2.8, 3.2)$
• Step: $w^{(2)} = (2.8, 1.6) - 0.3 \cdot (2.8, 3.2) = (1.96, 0.64)$

The objective values: $f(4,4) = 24$, $f(2.8, 1.6) = 6.48$, $f(1.96, 0.64) = 2.33$. The minimum is $f(0,0) = 0$, and we're getting closer every step.

Notice that $w_2$ shrinks faster than $w_1$ because its gradient component is twice as large. This direction-dependent convergence speed is a preview of the condition-number story in Week 4.

Reading loss curves#

Plot $f(x_k)$ against iteration $k$. A healthy GD run shows a smooth, monotonically decreasing curve that flattens as it approaches the minimum:

• Smooth decrease: The step size is working; the gradient is driving consistent progress.
• Plateau: The curve is nearly flat. Either the gradient is very small (you're near the minimum) or the step size is too conservative.
• Oscillation: The curve bounces up and down. The step size may be too large, overshooting the valley floor each iteration.
• Divergence: The curve rises steadily. $\eta$ is far too large; the descent lemma (Week 3) is violated.

A useful diagnostic: if the loss drops quickly for the first few iterations then plateaus far from zero, you may be stuck in a shallow region. Try increasing $\eta$ slightly or adding momentum (Week 7).

Knowledge Check#

Browser lab: gradient descent on a 2D quadratic#

Perform gradient descent on a 2D quadratic $f(x,y) = x^2 + 2y^2$ and visualise the iterate trajectory overlaid on the loss contour.

import numpy as np
import matplotlib.pyplot as plt

def f(x, y):
    return 0.5 * (x**2 + 2 * y**2)

def grad(x, y):
    return np.array([x, 2 * y])

eta = 0.3
n_steps = 12
xy = np.array([4.0, 4.0])
path = [xy.copy()]

for _ in range(n_steps):
    xy = xy - eta * grad(*xy)
    path.append(xy.copy())

path = np.array(path)

xs = np.linspace(-5, 5, 200)
ys = np.linspace(-5, 5, 200)
X, Y = np.meshgrid(xs, ys)
Z = f(X, Y)

fig, ax = plt.subplots(figsize=(6, 5))
ax.contour(X, Y, Z, levels=20, cmap="viridis", alpha=0.7)
ax.plot(path[:, 0], path[:, 1], "o-", color="tab:red", markersize=4, label="GD iterates")
ax.plot(0, 0, "x", color="black", markersize=10, label="optimum (0,0)")
ax.set_xlabel("x")
ax.set_ylabel("y")
ax.set_title(f"GD with η={eta} on f(x,y) = ½(x² + 2y²)")
ax.legend()
ax.set_aspect("equal")
plt.show()

print("Final position:", path[-1])
print("Final loss:", f(*path[-1]))
print("Notice: the iterates march downhill and settle at the optimum (0, 0) — final loss ≈ 0.")

Key takeaways#

• Supervised learning is empirical risk minimization: pick a model, pick a loss, minimize the average loss over the sample.
• The gradient points uphill; gradient descent steps opposite it, $x_{k+1} = x_k - \eta \nabla f(x_k)$.
• The chain rule makes this practical: for $f(w) = \frac{1}{2}\|Xw - y\|_2^2$ the gradient is $X^T(Xw - y)$, and for one example it is a scalar error times the feature vector, making SGD cheap.
• The step size is the central tuning knob: too small and you crawl, too large and you overshoot or diverge.
• The loss curve is a live diagnostic: smooth decrease is healthy, oscillation means $\eta$ is too large, a steady rise means it is far too large, and a plateau can mean either a shallow region or a step size that is too conservative.
• Faster shrinkage in one coordinate than another is the first sign of ill-conditioning, which Week 4 makes precise.

Further reading#

• Stephen Boyd & Lieven Vandenberghe, Convex Optimization (Cambridge University Press, 2004). Chapter 1 frames the optimisation problem and §9.1 covers descent methods. Freely available at stanford.edu/~boyd/cvxbook.
• Ian Goodfellow, Yoshua Bengio & Aaron Courville, Deep Learning (MIT Press, 2016). Chapter 4 reviews the calculus and Chapter 8 develops optimisation for training deep models.
• Jorge Nocedal & Stephen Wright, Numerical Optimization (2nd ed., Springer, 2006). Chapter 3 covers line search and steepest-descent methods.