The Book

Inspired by Paul Erdős’ description of beautiful proofs, this website highlights deep and elegant insights that, in my opinion, deserve their own pages in the Book. Claude drafted and I edited.

Hutch++ and the Split Spectrum

Numerical Linear Algebra

Variance Reduction

Deflate the heavy top of the spectrum and run Hutchinson on the flat rest: the error falls like \(1/m\) instead of \(1/\sqrt{m}\), and no algorithm does better.

Private Selection by Noisy Argmax

Sampling

Differential Privacy

Perturb every score with independent noise and take the argmax: Gumbel draws an exact softmax, exponential noise beats its regret, and Laplace gets away with half the noise of either.

Prune and Clone

Sampling

Variance Reduction

Language Models

Run rollouts as a population: prune the hopeless, clone the promising, and give every clone a weight of one over its chance of being picked. The estimate stays unbiased no matter how bad the guide is.

The Infinite Gaussian Vector

Probability

Numerical Linear Algebra

A Gaussian process is one Gaussian vector stretched over every input you might ask about; conditioning it on data is the textbook Gaussian-conditioning formula, and fitting its kernel is maximizing a likelihood.

Iterative Hessian Mixing

Differential Privacy

Numerical Linear Algebra

Both moving parts of the iterative Hessian sketch were privacy mechanisms all along, and the better conditioned the data, the less noise the sketch needs.

Rotate, Round, Debias

Numerical Linear Algebra

Language Models

A random rotation makes every input direction look the same; whatever quantizer rounds the result can be made exactly unbiased for free, by dividing out its own alignment with the original vector, or, at one extra bit, by sketching away what it leaves behind.

Tilting at Rare Events

Sampling

Probability

Language Models

The best proposal for a rare event is the conditional distribution given the event, and its normalizer is the number we wanted. Exponential tilting softens the constraint.

A PSA on Shapley Values

Shapley Values

The game and the value are different objects, and once you separate them, every modern SHAP method is the same algorithm.

The Even–Odd Decomposition

Shapley Values

Variance Reduction

Sampling

The Shapley value is blind to half of every game, and paired sampling is the estimator that never looks at that half.

Exponential Minimum Sampling

Sampling

Language Models

The fastest exponential clock is an exact sample, and if a verifier holds the clocks, every sample is also a distortion-free watermark.

Aliasing on Purpose

Experimental Design

Evaluating a fraction of a factorial experiment merges effects into sums. Classical design treats the merging as damage to manage; when the target is itself a sum of interactions, the right fraction computes it exactly.

Why Sums Become Gaussian

Probability

The joint density of two independent Gaussians is perfectly round, so sums of Gaussians stay Gaussian; and addition preserves only mean and variance, so sums of everything else drift Gaussian too.

Implicit Control Variate

Sampling

Variance Reduction

Fix the sample size and the best constant baseline subtracts itself.

Three Faces of Leverage Scores

Numerical Linear Algebra

Sampling

One number per row of a matrix (self-influence, minimum energy, effective resistance), and it is exactly the right rate to sample the row at.

One Data Shapley Vector Is Not Enough

Shapley Values

Optimization

Shapley linearity hands you a Data Shapley value vector per validation point for free, and averaging them discards exactly what data selection needs.

Shapley Values for Piecewise-Constant Games

Shapley Values

When a game takes the same value on whole blocks of coalitions, the Shapley sum collapses to one term per block: exact Shapley values in time linear in the number of distinct values, not the number of coalitions. Trees and causal models are two instances.

Speculative Decoding Is a Maximal Coupling

Language Models

Sampling

The accept/reject rule of speculative decoding is a maximal coupling of draft and target, so the output is exactly the big model’s distribution, and no exact scheme can accept more often.

The Greedy \(1-1/e\) Guarantee

Optimization

Repeatedly take the largest marginal gain and you land within \(1-1/e\) of the best possible set, for any monotone submodular objective, and no efficient algorithm does better.