Theory Demos

Twelve noisy samples of sin(2πx) are fit with p random cosine features. Classical intuition says error should keep rising once the model can fit the noise. Instead it spikes at p = n = 12 and then falls again. The whole effect lives in which solution the fit returns once there are more features than points (Belkin, Hsu, Ma & Mandal, 2019).

Whether the second descent ends below the first minimum depends on the noise level and the feature bandwidth. Here it does (0.0108 against 0.0138), but that isn't a universal law. The noise slider in the browser demo lets you see this move.

Three facts that surprise people the first time, each checked by sampling. The basic tool is a uniformly random direction: draw a Gaussian vector and divide by its length. The cosine between two such directions is then just a dot product, and its spread should be exactly 1/√d.

How many directions fit with every pairwise |cos| below 0.1? Only d can be exactly orthogonal, but near-orthogonal sets grow exponentially. The squared cosine of two random directions follows a known Beta law, so the chance that one pair breaks the rule has an exact formula and no simulation is needed:

A search does better than a random set. The greedy search draws 20,000 random directions and keeps each one that is within |cos| < 0.1 of every direction kept so far. At d = 800 it keeps 972, already more than d. The growth is exponential, but it starts late.

The third fact needs no sampling at all: the share of a ball's volume within ε of its surface is 1 − (1 − ε)^d. At d = 100, 99.997% of the volume is in the outer 10% of the radius. The script checks the formula by Monte Carlo for d ≤ 8, where rejection sampling from the cube still works.

A diffusion model learns the score, the gradient of log-density, of noised data. For a finite training set the noised distribution is a mixture of Gaussians centred on the training points, and its score has a closed form. So the demo can skip training and ask: what does the ideal model generate? A sampler with that exact score reproduces the training points. A perfect model memorises, which is the effect behind training-data extraction from real diffusion models (Carlini et al., 2023).

Two imperfect scores generalise instead. The blurred score uses the exact score at a larger noise level, √(σ² + τ²), which makes it a kernel density estimate with bandwidth τ. The MLP has 64-unit layers, is trained for 4,000 Adam steps in numpy, and its limited capacity spreads mass along the circle. Full numbers, 20 training points and 2,000 samples per row:

The MLP's samples stay on the circle and are mostly not copies. The blur generalises by smearing samples off the circle, which isn't the same as learning the shape. A bigger network trained much longer would drift back toward the memorising exact score.

Warner's 1965 survey trick: each person secretly answers either the real question (with probability p) or its opposite. No single “yes” reveals anything for sure, but the mixing is known, so the population rate can be solved for. Each answer is ε-locally differentially private with ε = ln(p / (1 − p)).

The price is precision: you need more respondents. Simulated with a true rate of 0.3:

An attack can show a classifier is fragile; it can never show it is safe. A certificate can. If the score f changes by at most L per unit of input distance, then no change smaller than |f(x)| / L can flip its sign. The demo builds this two ways on the two-moons dataset, with networks written in numpy: a wiggly unconstrained net, and one with every weight matrix projected to spectral norm ≤ 1, so L ≤ 1. Both are also attacked with PGD.

The certified radius is then just np.abs(net(X)) / net.lipschitz_bound(). For the wiggly net that radius is useless, so the demo certifies it a second way: randomized smoothing (Cohen, Rosenfeld & Kolter, 2019) classifies by majority vote over Gaussian-noised copies of the input, and the margin of that vote gives a radius.

Certified accuracy on 200 test points, σ = 0.25 for smoothing. PGD found 0 violations inside the Lipschitz net's 197 certified radii, as it must. The wiggly net is fairly robust in practice, but its Lipschitz bound of about 2,000 certifies nothing. Smoothing turns the same network into a certifiable classifier. Strictly, it certifies the smoothed classifier, not the original network.

A demo of a theorem is only convincing if the code is right, so each claim is also a test: the cosine spread matches 1/√d, the double-descent peak exists and ridge removes it, the Warner estimator is unbiased, the exact score matches finite differences. The strongest ones try to break a guarantee and must fail.

The project page runs all five experiments live, with no server. web/lib.js holds the maths, one function per Python function, and names the function it ports. web/worker.js runs anything slow in a Web Worker so the page never freezes, and web/demos.js draws the plots on canvas. There are no libraries: the SVD, the Beta and normal quantiles that scipy provides, and the small neural network are written out by hand.

The setups are the scripts' own: 12 points, cosine features with frequency scale 15 and a 500-point test grid for double descent; 20 points on a circle, 2,000 samples and 500 steps from σ = 3 to 0.01 for diffusion; n0 = 100, n = 10,000 and α = 0.001 for smoothing. Two inputs are copied straight from Python into web/data.json by web/export_data.py: the 12 training points of double descent (with their noise draws, so the noise slider just rescales them), and the weights of both trained robustness networks. The browser therefore certifies the very networks in the reference figure.

Double descent needs 100 fits at each of 29 values of p, up to 2,000 features, so recomputing on every slider move would be slow. The trick is that a fit depends on the ridge penalty λ and on the targets y only through the singular values of the feature matrix. Each fit is reduced once to a few small arrays, and every later λ or noise change costs microseconds:

The heavy part, building A and bv, runs in workers. The page splits the 100 draws into rounds of 10 and runs up to four workers at once. Each worker posts its results one p at a time, so the curve appears within a second and sharpens as draws arrive:

Randomized smoothing is a direct port of smoothed_certify. The only change is that it handles one point at a time, so a click certifies the point under the cursor in about a tenth of a second:

The rest is ported line by line: the reverse-diffusion sampler and exact score, the score MLP with its hand-written backward pass and Adam, the Warner estimator and its interval, the CSV reader of the poll tool, the greedy packing, and the Beta tail behind the birthday estimate. Random numbers come from a small seeded generator (sfc32 with Box–Muller normals), not numpy's, so draws differ from the scripts while the distributions are the same.

Where both sides use the same inputs, the numbers agree to every printed digit. Where the browser draws its own random numbers, they agree within sampling noise.

The peak is heavy-tailed: a few draws give a nearly singular feature matrix, so even Python's own median at p = 12 swings between 0.34 and 0.59 from seed to seed, and the reference 0.3165 is at the low end. The diffusion rows differ more because the browser also draws its own 20 training points, so the circle is covered differently. The wiggly net's outputs differ in the sixth digit because its weights are stored to 8 decimals in data.json. In 300,000 simulated polls, the browser's exact intervals covered the true rate 95.03–95.07% of the time, against an exact 95.11%.

• Each demo is the smallest case that shows its effect: 12 points, 2-D data, one feature map. It shows that the effect exists, not how large it is in real models.
• Double descent's second descent ending below the first minimum depends on noise and feature bandwidth here. It isn't a law.
• The diffusion MLP generalises partly because it is small and briefly trained. A bigger network trained longer would drift back toward the memorising exact score.
• Smoothing certifies the smoothed classifier, a majority vote over noisy copies, not the network itself. The certificate holds with probability 1 − α = 99.9%, not with certainty.
• The poll tool's exact interval is conservative: it maps a Clopper–Pearson interval through the linear Warner transform and clips it to [0, 1]. Without --column, the command-line tool reads the first column; for the example poll that is the respondent number, so pass --column answer. The browser version uses a column named "answer" when the file has one.
• The browser draws its own random numbers, so its curves and counts differ slightly from the reference figures. The shading for the smoothed classifier uses 64 votes per cell, which is for display only, as in the script's figure. The cosine histogram uses 5,000 pairs (the script's --quick setting) to stay responsive. The greedy search is offered only up to d = 1,000.

Install the requirements, then run everything at quick settings (about 70 s) or full settings (about 3 minutes). Any script also runs on its own, and most accept --quick.

To rebuild the browser data file from the scripts (about 20 s, retrains both robustness networks):

• Belkin, Hsu, Ma & Mandal (2019). Reconciling modern machine-learning practice and the classical bias–variance trade-off. PNAS.
• Carlini et al. (2023). Extracting training data from diffusion models. USENIX Security.
• Warner (1965). Randomized response: a survey technique for eliminating evasive answer bias. Journal of the American Statistical Association.
• Cohen, Rosenfeld & Kolter (2019). Certified adversarial robustness via randomized smoothing. ICML.