Stable Algorithms Lower Bounds for Estimation
This work provides rigorous algorithmic foundations for the physics belief that first-order phase transitions impose fundamental limits on efficient algorithms, addressing a long-standing problem in theoretical computer science and statistical estimation.
The paper tackles the problem of establishing lower bounds for stable algorithms in statistical estimation by showing that a natural MMSE instability condition implies their failure, and demonstrates separations between stable and polynomial-time algorithms for three specific tasks: Planted Shortest Path, random Parity Codes, and Gaussian Subset Sum, with results showing that all low-degree polynomials are stable in these cases.
In this work, we show that for all statistical estimation problems, a natural MMSE instability (discontinuity) condition implies the failure of stable algorithms, serving as a version of OGP for estimation tasks. Using this criterion, we establish separations between stable and polynomial-time algorithms for the following MMSE-unstable tasks (i) Planted Shortest Path, where Dijkstra's algorithm succeeds, (ii) random Parity Codes, where Gaussian elimination succeeds, and (iii) Gaussian Subset Sum, where lattice-based methods succeed. For all three, we further show that all low-degree polynomials are stable, yielding separations against low-degree methods and a new method to bound the low-degree MMSE. In particular, our technique highlights that MMSE instability is a common feature for Shortest Path and the noiseless Parity Codes and Gaussian subset sum. Last, we highlight that our work places rigorous algorithmic footing on the long-standing physics belief that first-order phase transitions--which in this setting translates to MMSE-instability impose fundamental limits on classes of efficient algorithms.