Approximate Ground States of Hypercube Spin Glasses are Near Corners

Sellke, Mark

Comptes Rendus. Mathématique, Tome 359 (2021) no. 9, pp. 1097-1105.

We show that with probability exponentially close to $1$, all near-maximizers of any mean-field mixed $p$-spin glass Hamiltonian on the hypercube ${[-1,1]}^N$ are near a corner. This confirms a recent conjecture of Gamarnik and Jagannath. The proof is elementary and extends to arbitrary polytopes with $e^{o\left(N^2\right)}$ faces.

[1] Alaoui, Ahmed El; Montanari, Andrea; Sellke, Mark Optimization of Mean-field Spin Glasses (2021) (https://arxiv.org/abs/2001.00904, to appear in Annals of Probability)

[2] Anderson, Greg W.; Guionnet, Alice; Zeitouni, Ofer An introduction to random matrices, Cambridge Studies in Advanced Mathematics, 118, Cambridge University Press, 2010 | MR | Zbl

[3] Arous, Gérard B.; Guionnet, Alice Large deviations for Wigner’s law and Voiculescu’s non-commutative entropy, Probab. Theory Relat. Fields, Volume 108 (1997) no. 4, pp. 517-542 | DOI | MR | Zbl

[4] Arous, Gérard B.; Mei, Song; Montanari, Andrea; Nica, Mihai The landscape of the spiked tensor model, Commun. Pure Appl. Math., Volume 72 (2019) no. 11, pp. 2282-2330 | DOI | MR | Zbl

[5] Arous, Gérard B.; Subag, Eliran; Zeitouni, Ofer Geometry and temperature chaos in mixed spherical spin glasses at low temperature: the perturbative regime, Commun. Pure Appl. Math., Volume 73 (2020) no. 8, pp. 1732-1828 | DOI | MR | Zbl

[6] Auffinger, Antonio; Ben Arous, Gérard B. Complexity of random smooth functions on the high-dimensional sphere, Ann. Probab., Volume 41 (2013) no. 6, pp. 4214-4247 | MR | Zbl

[7] Auffinger, Antonio; Ben Arous, Gérard B.; Černý, Jiří Random matrices and complexity of spin glasses, Commun. Pure Appl. Math., Volume 66 (2013) no. 2, pp. 165-201 | DOI | MR | Zbl

[8] Chatterjee, Sourav Disorder chaos and multiple valleys in spin glasses (2009) (https://arxiv.org/abs/0907.3381)

[9] Chatterjee, Sourav; Sloman, Leila Average Gromov hyperbolicity and the Parisi ansatz, Adv. Math., Volume 376 (2021), 107417 | MR | Zbl

[10] Chen, Wei-Kuo; Handschy, Madeline; Lerman, Gilad On the energy landscape of the mixed even p-spin model, Probab. Theory Relat. Fields, Volume 171 (2018) no. 1-2, pp. 53-95 | DOI | MR | Zbl

[11] Chen, Wei-Kuo; Panchenko, Dmitry; Subag, Eliran The generalized TAP free energy (2021) (https://arxiv.org/abs/1812.05066, to appear in Communications on Pure and Applied Mathematics) | Zbl

[12] Chen, Wei-Kuo; Panchenko, Dmitry; Subag, Eliran The generalized TAP free energy. II, Commun. Math. Phys., Volume 381 (2021) no. 1, pp. 257-291 | DOI | MR | Zbl

[13] Ding, Jian; Eldan, Ronen; Zhai, Alex et al. On multiple peaks and moderate deviations for the supremum of a Gaussian field, Ann. Probab., Volume 43 (2015) no. 6, pp. 3468-3493 | MR | Zbl

[14] Gamarnik, David; Jagannath, Aukosh The overlap gap property and approximate message passing algorithms for $p$-spin models, Ann. Probab., Volume 49 (2021) no. 1, pp. 180-205 | DOI | MR | Zbl

[15] Guerra, Francesco; Toninelli, Fabio L. The thermodynamic limit in mean field spin glass models, Commun. Math. Phys., Volume 230 (2002) no. 1, pp. 71-79 | DOI | MR | Zbl

[16] Jagannath, Aukosh Approximate ultrametricity for random measures and applications to spin glasses, Commun. Pure Appl. Math., Volume 70 (2017) no. 4, pp. 611-664 | DOI | MR | Zbl

[17] Jagannath, Aukosh; Sen, Subhabrata On the unbalanced cut problem and the generalized Sherrington–Kirkpatrick model, Ann. Inst. Henri Poincaré D, Comb. Phys. Interact. (AIHPD), Volume 8 (2021) no. 1, pp. 15-88 | MR | Zbl

[18] Montanari, Andrea Optimization of the Sherrington-Kirkpatrick Hamiltonian, 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) (2019), pp. 1417-1433 | DOI | Zbl

[19] Panchenko, Dmitry Free energy in the generalized Sherrington–Kirkpatrick mean field model, Rev. Math. Phys., Volume 17 (2005) no. 7, pp. 793-857 | DOI | MR | Zbl

[20] Panchenko, Dmitry The Parisi ultrametricity conjecture, Ann. Math., Volume 177 (2013) no. 1, pp. 383-393 | DOI | MR | Zbl

[21] Parisi, Giorgio Infinite number of order parameters for spin-glasses, Phys. Rev. Lett., Volume 43 (1979) no. 23, p. 1754 | DOI

[22] Subag, Eliran The complexity of spherical $p$-spin models: a second moment approach, Ann. Probab., Volume 45 (2017) no. 5, pp. 3385-3450 | MR | Zbl

[23] Subag, Eliran Free energy landscapes in spherical spin glasses (2018) (https://arxiv.org/abs/1804.10576)

[24] Subag, Eliran Following the Ground States of Full-RSB Spherical Spin Glasses, Commun. Pure Appl. Math., Volume 74 (2021) no. 5, pp. 1021-1044 | DOI | MR | Zbl

[25] Talagrand, Michel The Parisi formula, Ann. Math. (2006), pp. 221-263 | DOI | MR | Zbl