Approximate Ground States of Hypercube Spin Glasses are Near Corners

Mark Sellke

doi:10.5802/crmath.240

Physique mathématique, Probabilités

Approximate Ground States of Hypercube Spin Glasses are Near Corners

Mark Sellke ¹

¹ Stanford University, Department of Mathematics, USA.

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

Résumé

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 : 2021-03-06
Révisé le : 2021-05-03
Accepté le : 2021-06-19
Publié le : 2021-11-03

DOI : 10.5802/crmath.240

Affiliations des auteurs :

Mark Sellke ¹

¹ Stanford University, Department of Mathematics, USA.

Licence :

CC-BY 4.0

Droits d'auteur : Les auteurs conservent leurs droits

@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
SP  - 1097
EP  - 1105
VL  - 359
IS  - 9
PB  - Académie des sciences, Paris
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
%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, Volume 359 (2021) no. 9, pp. 1097-1105. doi : 10.5802/crmath.240. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.5802/crmath.240/

Bibliographie
Cité par

[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 | Zbl

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[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 | Zbl

[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 | DOI | MR | Zbl

[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 | Zbl

[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 | DOI | MR | Zbl

[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

[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 | DOI | MR | Zbl

[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 | Zbl

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[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 | Zbl

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

[19] Dmitry Panchenko 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] Dmitry Panchenko The Parisi ultrametricity conjecture, Ann. Math., Volume 177 (2013) no. 1, pp. 383-393 | DOI | MR | Zbl

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

[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 | Zbl

[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 | DOI | MR | Zbl

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

Cité par Sources :

Commentaires - Politique