Mathematical physics, Probability theory
Approximate Ground States of Hypercube Spin Glasses are Near Corners
Comptes Rendus. Mathématique, Volume 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(N 2 ) faces.

Received:
Revised:
Accepted:
Published online:
DOI: 10.5802/crmath.240
Sellke, Mark 1

1 Stanford University, Department of Mathematics, USA.
@article{CRMATH_2021__359_9_1097_0,
     author = {Sellke, Mark},
     title = {Approximate {Ground} {States} of {Hypercube} {Spin} {Glasses} are {Near} {Corners}},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {1097--1105},
     publisher = {Acad\'emie des sciences, Paris},
     volume = {359},
     number = {9},
     year = {2021},
     doi = {10.5802/crmath.240},
     language = {en},
     url = {http://www.numdam.org/articles/10.5802/crmath.240/}
}
TY  - JOUR
AU  - Sellke, Mark
TI  - Approximate Ground States of Hypercube Spin Glasses are Near Corners
JO  - Comptes Rendus. Mathématique
PY  - 2021
SP  - 1097
EP  - 1105
VL  - 359
IS  - 9
PB  - Académie des sciences, Paris
UR  - http://www.numdam.org/articles/10.5802/crmath.240/
DO  - 10.5802/crmath.240
LA  - en
ID  - CRMATH_2021__359_9_1097_0
ER  - 
%0 Journal Article
%A Sellke, Mark
%T Approximate Ground States of Hypercube Spin Glasses are Near Corners
%J Comptes Rendus. Mathématique
%D 2021
%P 1097-1105
%V 359
%N 9
%I Académie des sciences, Paris
%U http://www.numdam.org/articles/10.5802/crmath.240/
%R 10.5802/crmath.240
%G en
%F CRMATH_2021__359_9_1097_0
Sellke, Mark. Approximate Ground States of Hypercube Spin Glasses are Near Corners. Comptes Rendus. Mathématique, Volume 359 (2021) no. 9, pp. 1097-1105. doi : 10.5802/crmath.240. http://www.numdam.org/articles/10.5802/crmath.240/

[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

Cited by Sources: