Near-optimal shattering in the Ising pure p p -spin and rarity of solutions returned by stable algorithms
Ahmed El Alaoui · 2024
Read Near-optimal shattering in the Ising pure p p -spin and rarity of solutions returned by stable algorithms by Ahmed El Alaoui (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-03511.txt.
Introduction
Spin glasses are magnets with frozen, disordered spins, and their energy landscape breaks into many far-apart clusters at low temperature, a phenomenon called shattering. Ahmed El Alaoui studies shattering in the Ising pure p-spin model. He shows it occurs at all inverse temperatures in a stated range once p is large enough as a function of temperature. The lower edge of that range matches the asymptotic mark of the dynamical transition predicted by physicists.
The proof runs through a soft version of the overlap gap property, which places a distance gap between points of typical energy and a typical sample from the Gibbs measure. He then shows this property confines stable algorithms to an exponentially rare slice of the high-energy set, provided their success chance is not vanishingly small. The work tightens what theory can say about where algorithms can and cannot reach in spin glass landscapes.
Catalog record
| CREATOR | Ahmed El Alaoui |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 53 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-03511
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Near-optimal shattering in the Ising pure p p -spin and rarity of solutions returned by stable algorithms Ahmed El Alaoui Abstract We show that in the Ising pure p p -spin model of spin glasses, shattering takes place at all inverse temperatures β ∈ ( ( 2 log p ) / p , 2 log 2 ) \beta\in(\sqrt{(2\log p)/p},\sqrt{2\log 2}) when p p is sufficiently large as a function of β \beta . Of special interest is the lower boundary of this interval which matches the large p p -asymptotics of the inverse temperature marking the hypothetical dynamical transition predicted in statistical physics. We show this as a consequence of a ‘soft’ version of the overlap gap property which asserts the existence of a distance gap of points of typical energy from a typical sample from the Gibbs measure. We further show that this latter property implies that stable algorithms seeking to return a point of at least typical energy are confined to an exponentially rare subset of that super-level set, provided that their success probability is not vanishingly small. 1 Introduction and main result We consider the mixed p -spin model on the binary hypercube. Let (g_{i_{1},\cdots,i_{k}})_{1\leq i_{1},\cdots,i_{k}\leq N,k\geq 2} be a collection of i.i.d. N(0,1) random variables which we denote by \bm{G} , and fix a collection of scalars (\gamma_{k})_{k=2}^{P} . We consider the random Hamiltonian \displaystyle H_{N}(\bm{\sigma})=\sum_{k=2}^{P}\frac{\gamma_{k}}{N^{(k-1)/2}}\sum_{1\leq i_{1},\cdots,i_{k}\leq N}g_{i_{1},\cdots,i_{k}}\sigma_{i_{1}}\cdots\sigma_{i_{k}}\,,~~~\bm{\sigma}\in\{-1,+1\}^{N}\,. (1.1) Let \xi(x):=\sum_{k=2}^{P}\gamma_{k}^{2}x^{k} be the mixture function of H_{N} ; we have \operatorname{\mathbb{E}}[H_{N}(\bm{\sigma})H_{N}(\bm{\sigma}^{\prime})]=N\xi(\langle\bm{\sigma},\bm{\sigma}^{\prime}\rangle/N) . We define the corresponding Gibbs measure at inverse temperature \beta\geq 0 : \displaystyle\mu_{\beta,\bm{G}}(\bm{\sigma})=\frac{1}{Z_{N}(\beta)}e^{\beta H_{N}(\bm{\sigma})}\,,~~~\bm{\sigma}\in\{-1,+1\}^{N}\,. (1.2) The Gibbs measure \mu_{\beta,\bm{G}} is known to undergo a ‘static’ replica symmetry breaking transition at an inverse temperature \beta_{c} defined as the largest \beta at which the free energy \operatorname{\mathbb{E}}\log Z_{N}(\beta)/N converges to its annealed value \beta^{2}\xi(1)/2+\log 2 in the large N limit [ Tal00 ] . For some mixtures \xi a second ‘dynamical’ transition is expected at a lower inverse temperature \beta_{d} where the Gibbs measure is expected to exhibit shattering between \beta_{d} and \beta_{c} : a clustering of the mass of the measure into small and well separated subsets, each of exponentially small mass, and which together carry all but an exponentially small fraction of the mass. This transition is also expected to mark the slowdown of natural relaxation dynamics. In the case of the pure p -spin model \xi(x)=x^{p} , p\geq 3 this dynamical transition was predicted in the statistical physics literature to occur at the value \beta_{d}=\inf\left\{\beta>0:\exists\,q\in(0,1]~\mbox{s.t.}~q=\frac{\operatorname{\mathbb{E}}\big[\cosh(\beta\sqrt{\xi^{\prime}(q)}Z)\tanh^{2}(\beta\sqrt{\xi^{\prime}(q)}Z)\big]}{\operatorname{\mathbb{E}}\big[\cosh(\beta\sqrt{\xi^{\prime}(q)}Z)\big]}\right\}\,, (1.3) where Z\sim N(0,1) via the formalism of the replica method [ MRT03 , FLPR12 ] . For large values of p , \beta_{d} is asymptotic to (1+o_{p}(1))\sqrt{(2\log p)/p} where o_{p}(1)\to 0 as p\to\infty ; see [ FLPR12 , AMS23a ] . In contrast it is known that (1-2^{-p})\sqrt{2\log 2}\leq\beta_{c}\leq\sqrt{2\log 2} [ Tal00 ] so the “shattered phase” is conjectured to occupy a dominant share of the replica-symmetric regime. Shattering in the Ising p -spin. Shattering in the Ising pure p -spin model was recently established in [ GJK23 ] for all \sqrt{\log 2}<\beta<\sqrt{2\log 2} and all p sufficiently large. This was shown via first and second moment methods tracking the occurrence of a certain overlap gap property . In this paper we provide a simple argument showing that shattering occurs for the pure p -spin model for all \beta\in(\sqrt{(2\log p)/p},\sqrt{2\log 2}) when p is sufficiently large, matching the first order term in the asymptotic expansion of \beta_{d} marking the conjectural dynamical transition: Theorem 1.1 . Consider the pure p -spin case \xi(x)=x^{p} . For all \varepsilon>0 , there exists an integer p_{0}=p_{0}(\varepsilon) such that for all p\geq p_{0} and all (1+\varepsilon)\sqrt{(2\log p)/p}\leq\beta\leq(1-\varepsilon)\sqrt{2\log 2} , there exits a random collection of subsets \mathcal{C}_{1},\cdots,\mathcal{C}_{m}\subset\{-1,+1\}^{N} (measurable with respect to \bm{G} ) with the following properties: 1. Small diameter: \max_{\bm{\sigma}_{1},\bm{\sigma}_{2}\in\mathcal{C}_{i}}d_{H}(\bm{\sigma}_{1},\bm{\sigma}_{2})\leq rN for all i\leq m . 2. Pairwise separation: \min_{1\leq i\neq j\leq m}d_{H}(\mathcal{C}_{i},\mathcal{C}_{j})\geq RN . 3. Small Gibbs mass: \operatorname{\mathbb{E}}\max_{1\leq i\leq m}\mu_{\beta,\bm{G}}(\mathcal{C}_{i})\leq e^{-cN} . 4. Collective coverage of the Gibbs measure: \operatorname{\mathbb{E}}\mu_{\beta,\bm{G}}\big(\bigcup_{i=1}^{m}\mathcal{C}_{i}\big)\geq 1-e^{-cN} . In the above, d_{H} is the Hamming distance, c=c(\varepsilon)>0 and there exists \delta=\delta(\varepsilon)>0 such that one can take r=1/p^{1+\delta} and R=\delta/p . We remark that the scaling of the radii r and R are such that the clusters \mathcal{C}_{i} are almost “point-like” and are at a much larger distance apart than their diameter for large p . The above theorem is a consequence of a soft overlap gap property that appears in a general mixture \xi above an inverse temperature \bar{\beta}_{d} defined as follows: Let \varphi and \Phi be respectively the density and cumulative function of the standard normal distribution, and define \bar{\beta}_{d}=\inf_{q\in(0,1)}\frac{2\sqrt{\xi^{\prime}(1)}\varphi\big(\Phi^{-1}\big(\frac{1+q}{2}\big)\big)}{\xi(1)-\xi(q)}\,. (1.4) In the special case of the pure p -spin, \bar{\beta}_{d}\leq(1+o_{p}(1))\sqrt{(2\log p)/p} (see Eq. ( 3.11 )). We mention that for the spherical p -spin model, the available proofs of shattering rely on different techniques based on the analysis of the stationary points of the TAP free energy [ BAJ24 ] or the monotonicity of the Franz–Parisi potential [ AMS23b ] . We show in Section 6 that the argument used to prove Theorem 1.1 can also be used in the spherical case. This would provide an alternative proof of the shattering result of [ AMS23b ] with an explicit lower bound on \beta . In contrast with the Ising case however, the spherical analogue of \bar{\beta}_{d} is asymptotic to 2.216>\sqrt{e} , the latter being the conjectural value of the inverse temperature marking the dynamical transition for large p in the spherical case. Rarity of solutions found by Lipschitz algorithms. As mentioned earlier, shattering has algorithmic consequences pertaining to hardness of approximate sampling: Glauber dynamics (or Langevin dynamics in the spherical case) slow down exponentially and stable algorithms are not able to approximately sample from the Gibbs measure when shattering occurs. This is because shattering implies transport disorder chaos of the Gibbs measure–a notion of instability of \mu_{\beta,\bm{G}} in the Wasserstein-2 metric under small perturbations of the disorder \bm{G} –which in turn implies that stable algorithms cannot approximate \mu_{\beta,\bm{G}} in this same metric; see [ AMS23a , Section 3] and [ AMS23b , Section 5] for more detail on this implication. A second aim of this paper is to investigate the behavior of optimization or search algorithms in the shattered phase. Suppose we are interested in efficiently finding a point \bm{\sigma} whose energy is approximately typical under \mu_{\beta,\bm{G}} . More precisely, for \beta<\beta_{c} we consider the problem of efficiently returning a point in the super-level set S_{\beta}(\bm{G})=\Big\{\bm{\sigma}\in\{-1,+1\}^{N}:H_{N}(\bm{\sigma})\geq\beta\xi(1)N\Big\}\,, (1.5) on input \bm{G} , \beta and \xi . The right-hand side of the inequality in the above definition is the typical energy for a configuration at inverse temperature \beta , given by the derivative in \beta of the limiting free energy \beta^{2}\xi(1)/2+\log 2 for \beta<\beta_{c} . It is not difficult to show that \mu_{\beta,\bm{G}} is exponentially concentrated on S_{(1-\varepsilon)\beta}(\bm{G}) for any \varepsilon>0 : \operatorname{\mathbb{E}}\mu_{\beta,\bm{G}}\big(S_{(1-\varepsilon)\beta}(\bm{G})\big)\geq 1-e^{-cN}\,,~~~c=c(\beta,\varepsilon)>0\,, (1.6) heuristically suggesting that shattering of the Gibbs measure must impact the behavior of search algorithms on S_{(1-\varepsilon)\beta}(\bm{G}) (in fact the shattering clusters (\mathcal{C}_{i})_{1\leq i\leq m} for \mu_{\beta,\bm{G}} of Theorem 1.1 in the pure p -spin case all belong to S_{(1-\varepsilon)\beta}(\bm{G}) for some \varepsilon>0 small enough, see Section 4 ). Our main result is this direction is