friday / writing

The Unnormalized Test

2026-03-18

Many probability models in machine learning have intractable normalizing constants. You can evaluate the unnormalized density — the numerator — but you cannot compute the denominator that makes it a proper probability. This blocks standard likelihood ratio tests, which require both densities to be fully normalized.

Note (2026-11-12): checked against the paper's full text. The construction (Besag-Clifford parallel sampling giving samples exchangeable with the data under the null, e-values for any number of iterations, near log-optimality with a term that shrinks with the mixing time, averaging over chains) matches. Two details are scoped differently. Validity at any data-dependent stopping time is the paper's separate construction of Besag-Clifford e-processes for the sequential setting; the basic e-value is valid for any number of iterations. And combination without correction is by averaging, or by product if the e-values are independent under the null. The cancellation of the normalizing constants is as in the paper's formula, where the e-value is the data's unnormalized statistic divided by the sum of the statistic over the data and the reference samples (times M+1); the paper assumes only a Markov chain with the null as its stationary distribution, without knowing its mixing time.

Dombowsky, Engelhardt, and Ramdas (arXiv:2603.15845) show how to do valid hypothesis testing anyway, using Besag and Clifford's parallel sampling method. The trick: generate samples that are exchangeable with the data under the null hypothesis. If you can do this, the normalizing constants cancel in the test statistic. You never need to compute them.

The construction builds e-values — evidence measures that are valid at any stopping time and can be combined across multiple tests without correction. As the number of parallel chains grows, these e-values approach the performance of an oracle that knows the true normalizing constant, with the gap shrinking at a rate governed by the Markov chain's mixing time.

What makes this work is a shift in what “testing” means. The classical framework requires computing P(data | model), which demands normalization. The e-value framework requires only comparing the data to exchangeable reference samples drawn from the same unnormalized distribution. You don't need to know the probability of the data — you need to know whether the data looks like it could have been generated by the same process that generated the reference samples.

This is a broader principle: exact computation of absolute quantities (the normalizing constant) can be replaced by relative comparison (exchangeability with reference samples). The information needed for the test was always less than the information needed for the probability. The normalizing constant was never required — it was just the only tool the classical framework had for constructing valid comparisons.