Simulate and compare convergence rates

CodingIntermediate⏱ 1 hourAdvanced Optimizationsimulationmomentumnesterovrates

Theory: Momentum and Nesterov Acceleration →

Problem

Implement gradient descent, heavy ball, Nesterov and conjugate gradient on a quadratic with controllable $\kappa$ .

Verify each method's predicted rate by fitting the slope of $\log(f(x_t)-f^\star)$ .
Confirm that the advantage of momentum grows as $\sqrt\kappa$ versus $\kappa$ .
Show heavy ball diverging when $\eta$ is set too large, and identify the threshold.

Implement it, then check the implementation against something you can verify independently.

Write it

Solve it here8 tests · Python runs in your browser

import numpy as np

# The test problem, fixed so that measured rates can be compared with theory:
#   f(x) = 0.5 * x^T A x,  A = diag(np.linspace(1, kappa, d)),  x0 = ones(d).
# So mu = 1, L = kappa, the condition number is kappa and f* = 0.

def quadratic_descent(kappa, method, iters=400, d=20, eta=None, beta=None):
    """Run one first-order method on that quadratic and return the f values.

Return an array of length iters + 1 holding f(x_0) ... f(x_iters).

`method` is one of, with these default parameters:

'gd'          x_{t+1} = x_t - eta grad,           eta = 2 / (L + mu)
      'heavy-ball'  x_{t+1} = x_t - eta grad + beta (x_t - x_{t-1}),
                    eta = 4 / (sqrt(L) + sqrt(mu))**2,
                    beta = ((sqrt(kappa) - 1) / (sqrt(kappa) + 1))**2
      'nesterov'    y_t = x_t + beta (x_t - x_{t-1}) with the gradient taken
                    at y_t,  eta = 1 / L,
                    beta = (sqrt(kappa) - 1) / (sqrt(kappa) + 1)

`eta` and `beta`, when given, override those defaults — that is how you
    push heavy ball past its stability threshold.
    """
    raise NotImplementedError

def asymptotic_rate(values):
    """The geometric factor by which f shrinks per step, once transients die.

Fit a straight line to log(f_t) over the second half of `values`, ignoring
    any entries that have underflowed to zero, and return exp(slope).
    """
    raise NotImplementedError

⌘/Ctrl + ↵ to run · limit 90s · draft saved in this browser

8 tests will run against your code. The first run downloads the Python runtime — several megabytes, once per browser.

Solution

Opening this before you have a real attempt on paper is the fastest way to feel like you understand something you cannot reproduce.

Problem	Field	Type	Difficulty	Time
Simulate distance contrast run	Classical ML	Coding	Beginner	30 min
Balls into bins, with one choice and with two run	AI Systems	Coding	Intermediate	1 hour
Cache hit rates under Zipf popularity run	AI Systems	Coding	Intermediate	1 hour
Measure anisotropy in an embedding space run	RAG	Coding	Intermediate	1 hour
Measure fan-out amplification and the value of hedging run	AI Systems	Coding	Intermediate	1 hour

Problem

Write it

Solution

Related problems