Same Start, Same Stride

The chapter raced plain descent against momentum and watched the paths. Here you run that race yourself, over several different landscapes, and count how long each optimizer takes to settle.

Two weights $(x, y)$ are trained on the loss

$L(x, y) = p\,x^2 + 2q\,xy + r\,y^2$

which is passed in as the symmetric matrix M = [[p, q], [q, r]]. Every M you will be given is a bowl whose single lowest point is $(0, 0)$, where $L = 0$. When $q = 0$ the bowl's axes line up with $x$ and $y$. When $q \ne 0$ the valley runs diagonally. The gradient is

$\frac{\partial L}{\partial x} = 2(p\,x + q\,y), \qquad \frac{\partial L}{\partial y} = 2(q\,x + r\,y)$

Plain descent. Measure both partial derivatives at the current point, then move both weights:

$x \leftarrow x - \text{lr}\,\frac{\partial L}{\partial x}, \qquad y \leftarrow y - \text{lr}\,\frac{\partial L}{\partial y}$

Momentum. Keep a velocity $(v_x, v_y)$ that starts at $(0, 0)$. On every update, measure the gradient at the current point, then

$v_x \leftarrow \beta\,v_x - \text{lr}\,\frac{\partial L}{\partial x}, \qquad v_y \leftarrow \beta\,v_y - \text{lr}\,\frac{\partial L}{\partial y}$

$x \leftarrow x + v_x, \qquad y \leftarrow y + v_y$

Here $\beta$ (beta) is how much of the previous motion is kept. At $\beta = 0$ this is exactly plain descent.

Both runs start from the same point start = [x, y], use the same lr, and last exactly 1000 updates. The two runs are independent: momentum starts from start with zero velocity.

When has a run settled? A falling loss is not enough, because momentum's loss can dip below a threshold and then climb back over it. A run's settling count is the smallest number of updates $t$ such that the loss after $t$ updates, and after every later update up to the 1000th, is strictly below tol. The loss after $0$ updates is the loss at start, so a run that begins below tol and stays there has a settling count of $0$. If the loss after the 1000th update is not below tol, the run never settled, and its count is None.

For example, suppose a run's losses after $0, 1, 2, 3, 4, 5, \dots$ updates were $5.0,\ 0.8,\ 0.03,\ 0.2,\ 0.04,\ 0.009, \dots$ and every later loss stayed below $0.05$. With tol = 0.05, its settling count is $4$, not $2$: update 2 dipped under, but update 3 climbed back out.

Task: write race_to_settle(M, start, lr, beta, tol), returning [plain_count, momentum_count]. Each entry is a whole number or None.

You can rely on lr $> 0$, $0 \le$ beta $< 1$ and tol $> 0$.

Nothing in these rules favours either optimizer. Which one wins, and by how much, depends entirely on the landscape and the settings, and that is the reason to race them.