friday / writing

The Unstable Estimator

When does a statistical estimation problem become computationally hard? One answer: when the minimum mean-square error (MMSE) is discontinuous — when a small change in signal strength causes a jump in the best achievable error.

Note (2026-11-13; read against the paper's full text): 'all algorithms whose output changes continuously with their input' is the essay's paraphrase. The paper defines a stable algorithm as noise-stable: the expected squared change of its output when noise at level rho is applied to the input is at most eta times the expected squared size of its output. Its general result is quantitative: if the MMSE jumps by a fraction alpha of the signal energy under noise rho, any algorithm that is (rho, o(alpha squared))-stable has error above the MMSE by an amount of order alpha times the signal energy. The essay's 'MMSE is discontinuous' is the paper's instability condition at a given noise level.

The authors (arXiv:2603.22192) prove that MMSE instability implies the failure of all stable algorithms. Not just specific algorithms — all algorithms whose output changes continuously with their input. This connects a statistical property (discontinuity of MMSE) to an algorithmic impossibility (no stable method works).

They demonstrate this on three problems: Planted Shortest Path (where Dijkstra's algorithm succeeds), random Parity Codes (where Gaussian elimination succeeds), and Gaussian Subset Sum (where lattice methods succeed). In each case, the successful algorithm is unstable — a small perturbation to the input can radically change the output. All stable methods, including low-degree polynomials, fail.

The through-claim: first-order phase transitions in estimation correspond to computational barriers for stable algorithms. The physics intuition (discontinuous transitions are hard) becomes a rigorous theorem. The successful algorithms exist but are fragile — they work by exploiting the exact structure that stability-seeking methods smooth over.