We show that with probability exponentially close to , all near-maximizers of any mean-field mixed -spin glass Hamiltonian on the hypercube are near a corner. This confirms a recent conjecture of Gamarnik and Jagannath. The proof is elementary and extends to arbitrary polytopes with faces.
Revised:
Accepted:
Published online:
Mark Sellke 1
@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}, }
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/
[1] Optimization of Mean-field Spin Glasses (2021) (https://arxiv.org/abs/2001.00904, to appear in Annals of Probability)
[2] An introduction to random matrices, Cambridge Studies in Advanced Mathematics, 118, Cambridge University Press, 2010 | MR | Zbl
[3] 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] The landscape of the spiked tensor model, Commun. Pure Appl. Math., Volume 72 (2019) no. 11, pp. 2282-2330 | DOI | MR | Zbl
[5] 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] Complexity of random smooth functions on the high-dimensional sphere, Ann. Probab., Volume 41 (2013) no. 6, pp. 4214-4247 | MR | Zbl
[7] Random matrices and complexity of spin glasses, Commun. Pure Appl. Math., Volume 66 (2013) no. 2, pp. 165-201 | DOI | MR | Zbl
[8] Disorder chaos and multiple valleys in spin glasses (2009) (https://arxiv.org/abs/0907.3381)
[9] Average Gromov hyperbolicity and the Parisi ansatz, Adv. Math., Volume 376 (2021), 107417 | MR | Zbl
[10] 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] The generalized TAP free energy (2021) (https://arxiv.org/abs/1812.05066, to appear in Communications on Pure and Applied Mathematics) | Zbl
[12] The generalized TAP free energy. II, Commun. Math. Phys., Volume 381 (2021) no. 1, pp. 257-291 | DOI | MR | Zbl
[13] 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] The overlap gap property and approximate message passing algorithms for -spin models, Ann. Probab., Volume 49 (2021) no. 1, pp. 180-205 | DOI | MR | Zbl
[15] The thermodynamic limit in mean field spin glass models, Commun. Math. Phys., Volume 230 (2002) no. 1, pp. 71-79 | DOI | MR | Zbl
[16] 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] 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] Optimization of the Sherrington-Kirkpatrick Hamiltonian, 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) (2019), pp. 1417-1433 | DOI | Zbl
[19] 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] The Parisi ultrametricity conjecture, Ann. Math., Volume 177 (2013) no. 1, pp. 383-393 | DOI | MR | Zbl
[21] Infinite number of order parameters for spin-glasses, Phys. Rev. Lett., Volume 43 (1979) no. 23, p. 1754 | DOI
[22] The complexity of spherical -spin models: a second moment approach, Ann. Probab., Volume 45 (2017) no. 5, pp. 3385-3450 | MR | Zbl
[23] Free energy landscapes in spherical spin glasses (2018) (https://arxiv.org/abs/1804.10576)
[24] 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] The Parisi formula, Ann. Math. (2006), pp. 221-263 | DOI | MR | Zbl
Cited by Sources:
Comments - Policy