The Book

Inspired by Paul Erdős’ description of beautiful proofs, this website highlights deep and elegant insights that, in my humble opinion, deserve their own pages in The Book. I planned, AI drafted, and I edited: the decide-execute-deliver sandwich.

The Even–Odd Decomposition

Shapley Values

Variance Reduction

Sampling

Pairing groups of players offers a way to estimate individual contributions more accurately.

Exponential Minimum Sampling

Sampling

Language Models

Shared randomness lets a provider recognize generated text without changing its sampling distribution.

Tilting at Rare Events

Sampling

Variance Reduction

Language Models

When a thousand tries give no successes, change where you sample without changing the probability you want to measure.

Aliasing on Purpose

Shapley Values

An experiment can estimate an average without measuring every effect separately.

The Infinite Gaussian Vector

Probability

Numerical Linear Algebra

A prediction between measurements should come with some idea of how uncertain it is.

Why Sums Become Gaussian

Probability

Adding independent Gaussian noise gives more Gaussian noise. A rotation explains why.

Hutch++ and the Split Spectrum

Numerical Linear Algebra

Variance Reduction

Estimating a matrix’s diagonal sum using only a few matrix-vector products.

Implicit Control Variate

Sampling

Variance Reduction

Fixing the number of samples removes the same variance as a constant adjustment tuned to the unknown population average.

Iterative Hessian Mixing

Differential Privacy

Numerical Linear Algebra

Randomness introduced to make least squares fast can also help protect the people whose data went into the fit.

Three Faces of Leverage Scores

Numerical Linear Algebra

Sampling

Why an observation’s influence on a fitted model also tells us which graph edges to keep.

A Determinant Counts Spanning Trees

Numerical Linear Algebra

A graph can have too many spanning trees to list, yet one determinant counts them all.

One Data Shapley Vector Is Not Enough

Shapley Values

Optimization

Choosing the most useful training points individually can give us a poor training set.

Three Noises for the Argmax

Sampling

Differential Privacy

Different kinds of noise give lower-scoring choices different chances of being selected.

Shapley Values for Piecewise-Constant Games

Shapley Values

Assigning credit to individuals can be cheaper when many groups produce the same value.

Prune and Clone

Sampling

Variance Reduction

Language Models

Redirecting computation toward promising generations while estimating the original chance of success.

Rotate, Round, and Debias

Numerical Linear Algebra

Variance Reduction

Language Models

Compressing embeddings to preserve the scores used for ranking their matches.

A PSA on Shapley Values

Shapley Values

Assigning credit requires choosing what to measure, even when the rule for sharing credit is fixed.

Speculative Decoding Is a Maximal Coupling

Language Models

Sampling

A small model can help a large model write faster without changing the distribution of its text.

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

Optimization

Why choosing whatever helps most right now guarantees at least 63% of the best possible coverage.

The Tournament Is a Distribution Update

Language Models

Sampling

A tournament helps mark generated text, but we can compute its outcome without playing the matches.

Volume Sampling Keeps Leverage and Rejects Redundancy

Numerical Linear Algebra

Sampling

Two important rows can carry the same information. Volume sampling chooses them as part of a set.