logo CRAS
Comptes Rendus. Mathématique
Physique mathématique, Probabilités
Approximate Ground States of Hypercube Spin Glasses are Near Corners
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(N 2 ) faces.

Reçu le :
Révisé le :
Accepté le :
Publié le :
DOI : https://doi.org/10.5802/crmath.240
Mark Sellke 1

1. Stanford University, Department of Mathematics, USA.
@article{CRMATH_2021__359_9_1097_0,
     author = {Mark Sellke},
     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},
}
TY  - JOUR
AU  - Mark Sellke
TI  - Approximate Ground States of Hypercube Spin Glasses are Near Corners
JO  - Comptes Rendus. Mathématique
PY  - 2021
DA  - 2021///
SP  - 1097
EP  - 1105
VL  - 359
IS  - 9
PB  - Académie des sciences, Paris
UR  - https://doi.org/10.5802/crmath.240
DO  - 10.5802/crmath.240
LA  - en
ID  - CRMATH_2021__359_9_1097_0
ER  - 
%0 Journal Article
%A Mark Sellke
%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 https://doi.org/10.5802/crmath.240
%R 10.5802/crmath.240
%G en
%F CRMATH_2021__359_9_1097_0
Mark Sellke. Approximate Ground States of Hypercube Spin Glasses are Near Corners. Comptes Rendus. Mathématique, Tome 359 (2021) no. 9, pp. 1097-1105. doi : 10.5802/crmath.240. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.5802/crmath.240/

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

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

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

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

[5] Gérard B. Arous; Eliran Subag; Ofer Zeitouni 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 | Article | MR 4113545 | Zbl 1454.82089

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

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

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

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

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

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

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

[13] Jian Ding; Ronen Eldan; Alex Zhai 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 3433585 | Zbl 1344.60039

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

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

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

[17] Aukosh Jagannath; Subhabrata Sen 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 4228619 | Zbl 07357089

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

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

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

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

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

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

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

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

Cité par Sources :