Reproduce double descent

CodingAdvanced⏱ 3 hoursLearning Theorydouble descentsimulationrandom featuresminimum norm

Theory: Bias–Variance, Interpolation and Double Descent →

Problem

Reproduce the double-descent risk curve for random-feature regression.

Generate data from a linear model in $\R^{d}$ , map through $N$ random ReLU features, and fit the minimum-norm least-squares solution as $N$ varies through $n$ .
Plot test risk against $N/n$ and identify the peak.
Show that adding ridge regularisation with a well-chosen $\lambda$ removes the peak entirely.
Show that the peak grows with label noise and vanishes as noise $\to0$ .

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

Write it

Solve it here9 tests · Python runs in your browser

import numpy as np

def rf_test_risk(n, d, N, noise, seed=0, ridge=0.0, n_test=2000, target='linear'):
    """Test risk of random-feature regression, as the feature count N sweeps
    through the sample size n.

Build everything from one generator seeded with `seed`:

* random features W of shape (N, d) with entries N(0, 1/d), and the
        feature map phi(x) = relu(x @ W.T);
      * n training inputs and n_test test inputs, all iid N(0, I_d);
      * a clean target f(x), then noisy training labels y = f(x) + noise*eps
        with eps standard normal. The test labels stay clean, so what you
        measure is risk against the truth, not against noise.

`target` picks the truth:
      'linear'          f(x) = x @ beta for a unit beta — the random features
                        can only approximate it, so there is an approximation
                        error floor.
      'random-feature'  f(x) = phi(x) @ c for a random c, so the model class
                        contains the truth exactly.

Fit c_hat from the training features: with ridge = 0 take the
    *minimum-norm* least-squares solution (a pseudo-inverse or lstsq, not a
    normal-equation solve, which is singular once N > n); with ridge > 0
    solve (Phi^T Phi + ridge I) c = Phi^T y.

Return the mean squared error of phi(x) @ c_hat against the clean test
    target.
    """
    raise NotImplementedError

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

9 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
The bias–variance decomposition is an identity	Learning Theory	Proof	Beginner	15 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
Gradient descent finds the minimum-norm interpolator	Learning Theory	Proof	Intermediate	30 min

Problem

Write it

Solution

Related problems