Optimization of mean-field spin glasses
The Annals of Probability · 01.11.2021 · 49 (6) · 2922-2960
DOI: 10.1214/21-aop1519 ↗Kurz gefasst
Fachartikel in der Zeitschrift The Annals of Probability, erschienen am 01.11.2021. Verfasst von Ahmed El Alaoui und 2 weiteren Autor:innen. Die Arbeit wurde bisher 56-mal zitiert (Crossref) und nennt 49 Literaturangaben.
Abstract (Originalsprache)
Mean-field spin glasses are families of random energy functions (Hamiltonians) on high-dimensional product spaces. In this paper, we consider the case of Ising mixed p-spin models,; namely, Hamiltonians HN:ΣN→R on the Hamming hypercube ΣN={±1}N, which are defined by the property that {HN(σ)}σ∈ΣN is a centered Gaussian process with covariance E{HN(σ1)HN(σ2)} depending only on the scalar product ⟨σ1,σ2⟩. The asymptotic value of the optimum maxσ∈ΣNHN(σ) was characterized in terms of a variational principle known as the Parisi formula, first proved by Talagrand and, in a more general setting, by Panchenko. The structure of superlevel sets is extremely rich and has been studied by a number of authors. Here, we ask whether a near optimal configuration σ can be computed in polynomial time. We develop a message passing algorithm whose complexity per-iteration is of the same order as the complexity of evaluating the gradient of HN, and characterize the typical energy value it achieves. When the p-spin model HN satisfies a certain no-overlap gap assumption, for any ε>0, the algorithm outputs σ∈ΣN such that HN(σ)≥(1−ε)maxσ′HN(σ′), with high probability. The number of iterations is bounded in N and depends uniquely on ε. More generally, regardless of whether the no-overlap gap assumption holds, the energy achieved is given by an extended variational principle, which generalizes the Parisi formula.
Zitieren
APA
Alaoui, A. E., Montanari, A., & Sellke, M. (2021). Optimization of mean-field spin glasses. The Annals of Probability, 49(6), 2922-2960. https://doi.org/10.1214/21-aop1519
Vancouver
Alaoui AE, Montanari A, Sellke M. Optimization of mean-field spin glasses. The Annals of Probability. 2021;49(6):2922-2960. doi:10.1214/21-aop1519
BibTeX
@article{Alaoui2021,
author = {Alaoui, Ahmed El and Montanari, Andrea and Sellke, Mark},
title = {Optimization of mean-field spin glasses},
journal = {The Annals of Probability},
year = {2021},
volume = {49},
number = {6},
pages = {2922--2960},
doi = {10.1214/21-aop1519}
}
EUVIMED