The Monotonicity of the Franz–Parisi Potential Is Equivalent to Low-Degree MMSE Lower Bounds: Extended Abstract

Konstantinos Tsirkas, Leda Wang, Ilias Zadik
Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:6406-6409, 2026.

Abstract

Over the last decades, two distinct approaches have been instrumental to our understanding of the computational complexity of statistical estimation. The statistical physics literature predicts algorithmic hardness through local stability and monotonicity properties of the Franz–Parisi potential, while the rigorous average-case complexity literature characterizes hardness via the limitations of restricted algorithmic classes, most notably low-degree polynomial estimators. In this work, we show that for estimation problems the power of low-degree polynomials is governed by the monotonicity of the annealed Franz–Parisi potential for a broad family of Gaussian additive models. Subject to the low-degree conjecture for these Gaussian additive models, this identifies the polynomial-time estimation threshold with the monotonicity threshold of the annealed Franz–Parisi potential.

Cite this Paper

BibTeX
@InProceedings{pmlr-v336-tsirkas26a, title = {The Monotonicity of the Franz–Parisi Potential Is Equivalent to Low-Degree {MMSE} Lower Bounds: Extended Abstract}, author = {Tsirkas, Konstantinos and Wang, Leda and Zadik, Ilias}, booktitle = {Proceedings of Thirty Ninth Conference on Learning Theory}, pages = {6406--6409}, year = {2026}, editor = {Hanneke, Steve and Lattimore, Tor}, volume = {336}, series = {Proceedings of Machine Learning Research}, month = {29 Jun--03 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v336/main/assets/tsirkas26a/tsirkas26a.pdf}, url = {https://proceedings.mlr.press/v336/tsirkas26a.html}, abstract = {Over the last decades, two distinct approaches have been instrumental to our understanding of the computational complexity of statistical estimation. The statistical physics literature predicts algorithmic hardness through local stability and monotonicity properties of the Franz–Parisi potential, while the rigorous average-case complexity literature characterizes hardness via the limitations of restricted algorithmic classes, most notably low-degree polynomial estimators. In this work, we show that for estimation problems the power of low-degree polynomials is governed by the monotonicity of the annealed Franz–Parisi potential for a broad family of Gaussian additive models. Subject to the low-degree conjecture for these Gaussian additive models, this identifies the polynomial-time estimation threshold with the monotonicity threshold of the annealed Franz–Parisi potential.} }
Endnote
%0 Conference Paper %T The Monotonicity of the Franz–Parisi Potential Is Equivalent to Low-Degree MMSE Lower Bounds: Extended Abstract %A Konstantinos Tsirkas %A Leda Wang %A Ilias Zadik %B Proceedings of Thirty Ninth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2026 %E Steve Hanneke %E Tor Lattimore %F pmlr-v336-tsirkas26a %I PMLR %P 6406--6409 %U https://proceedings.mlr.press/v336/tsirkas26a.html %V 336 %X Over the last decades, two distinct approaches have been instrumental to our understanding of the computational complexity of statistical estimation. The statistical physics literature predicts algorithmic hardness through local stability and monotonicity properties of the Franz–Parisi potential, while the rigorous average-case complexity literature characterizes hardness via the limitations of restricted algorithmic classes, most notably low-degree polynomial estimators. In this work, we show that for estimation problems the power of low-degree polynomials is governed by the monotonicity of the annealed Franz–Parisi potential for a broad family of Gaussian additive models. Subject to the low-degree conjecture for these Gaussian additive models, this identifies the polynomial-time estimation threshold with the monotonicity threshold of the annealed Franz–Parisi potential.
APA
Tsirkas, K., Wang, L. & Zadik, I.. (2026). The Monotonicity of the Franz–Parisi Potential Is Equivalent to Low-Degree MMSE Lower Bounds: Extended Abstract. Proceedings of Thirty Ninth Conference on Learning Theory, in Proceedings of Machine Learning Research 336:6406-6409 Available from https://proceedings.mlr.press/v336/tsirkas26a.html.

Related Material