Source-linked AI summary
Rank-1-perturbed trickledown theorems: Mixing time of Glauber dynamics for the Sherrington-Kirkpatrick model up to $\beta\leq \frac{1}{2}+\varepsilon$
Mathews Boban, Anqi Li, Shayan Oveis Gharan
TL;DR
Efficient sampling motivates spectral-gap criteria for multi-state spin systems, while classical trickledown approaches use worst-case influence bounds. The paper introduces a rank-1-perturbed condition using average-bounded shifts and derives a spectral inequality under that condition.
Problem
For multi-state spin systems, the paper seeks a local-to-global spectral-gap criterion using average rather than worst-case influence, since efficient Glauber mixing supports sampling.
Source: §1 · pp. 1–2Method
The rank-1-perturbed condition shifts part of the pairwise correlation into a rank-1 matrix and bounds the shift loss on average.
Source: §1 · pp. 2, 4Results
Under the rank-1-perturbed condition, the framework yields ⟨Lf, Lf⟩ ≥ ε·E(f).
Source: §1 · p. 4Takeaways & Limitations
Polynomial-time mixing of a chain with stationary distribution μ allows samples to be generated from μ.
Source: §1 · p. 1The proof does not optimize the β range, and the authors expect the techniques may yield a spectral gap for L over a larger range.
Source: §1.3 · p. 10
Abstract
from arXiv · showhide
We introduce a new family of trickledown theorems, a.k.a., local to global technique to bound the spectral gap of the Glauber dynamics for multi-state spin systems. In this technique instead of upper-bounding the influence matrix of a link of co-dimension 2 by $\lambda I$ (where $\lambda$ is the second eigenvalue of the link), we upper-bound the influence matrix after a carefully chosen rank-1 shift. The rank-1 shift allows for a significantly smaller upper-bound but it comes at the cost of bounding the average loss due to rank-1 perturbations. As an application we use this method to show that the natural Glauber dynamics mixes in polynomial time to generate samples from the Sherrington-Kirkpatrick model for $\beta\leq \tfrac{1}{2}+\varepsilon$, for an absolute constant $\varepsilon>0$. At the heart of the proof we manage to bound the loss due to rank-1 perturbations by averaging over all links of co-dimension 2.
1 Introduction
The introduction presents rank-1-perturbed trickledown as a local-to-global approach to spectral-gap bounds, replacing worst-case influence control with an average-bounded rank-1 shift. Its SK application establishes polynomial-time Glauber mixing in the stated high-probability regime.
1 Introduction
- Glauber dynamics updates a uniformly chosen site by resampling its spin conditionally on the other sites, and efficient mixing enables sampling from the target distribution.Polynomial mixing is the stated efficiency goal for using MCMC to generate samples.Source: §1 · p. 1
- Classical trickledown methods bound worst-case pairwise interactions, including spectral influence conditioned on the other particles’ spins.The introduction describes local-to-global theorems and defines spectral influence through conditional correlations.Source: §1 · p. 2
- The rank-1-perturbed trickledown theorem replaces worst-case pairwise influence bounds with a rank-1 shift whose average loss is bounded.The shift moves part of the correlation between particles into a common rank-1 matrix, with the shifts bounded on average for every particle.Source: §1 · pp. 2, 4
- Proposition 1.4 turns the rank-1-perturbed condition and coefficient bounds into the inequality ⟨Lf, Lf⟩ ≥ ε·E(f).The stated proposition provides the spectral estimate used by the technique.Source: §1 · p. 4
1.1 Application: The Sherrington-Kirkpatrick (SK) model
- The SK application concerns a two-state Ising model whose interaction matrix has independent Gaussian off-diagonal entries and zero diagonal.The paper frames this model as a canonical average-case sampling problem.Source: §1.1 · pp. 4–5
- With ε ≥ 5·10^-5, β < 1/2 + ε gives, for sufficiently large n and with high probability over J, SK Glauber dynamics a spectral gap Ω(1/n) and mixing time O(n^2).The corollary states the absolute-constant ε regime and the gap and mixing-time bounds.Source: §1.1 · p. 5
1.2 Previous Work
Earlier work established rapid-mixing results for the SK model in more restricted regimes and developed sampling and functional-inequality approaches. The proof overview combines rank-1 perturbations with GOE-specific properties to obtain a spectral-gap result through β ≤ 1/2 + 5·10^-5.
1.2 Previous Work
- Earlier work obtained an optimal O(n log n) mixing time for the SK model when β < 1/4, using a modified log-Sobolev inequality.The passage also notes earlier O(n^2)-step mixing results in that regime.Source: §1.2 · p. 6
- Other approaches proved functional inequalities for PSD interaction matrices, including a modified log-Sobolev result for β up to approximately 0.295.A separate weak-Poincaré result covered β < 1.Source: §1.2 · pp. 6–7
- Sampling algorithms reached β < 1 in Wasserstein distance, later extended to the full β < 1 regime.These results concern Wasserstein distance rather than total-variation distance.Source: §1.2 · p. 6
1.3 Proof overview
- For β < 1/2 − ε, the passage concludes from λmax(J) → 2β + o(1) that L has a spectral gap of at least ε.Source: §1.3 · p. 7
- The proof uses a rank-1 perturbation; in Lemma 3.1, it takes m_i(x) = x_i + s x_i for some s < 1, rather than x_i + x_i as earlier computations suggested.The (1−s)x_i difference is used to compensate for the aforementioned error terms; the quadratic error contributes a non-negligible constant order term.Source: §1.3 · pp. 8–9
- For β near 1/2, the proof uses GOE eigenvector delocalization and the fact that most sites have large |X_i|, then splits into two cases based on B and the size of L_i f.When B is small, delocalization implies the L_i f values are roughly equal in magnitude; when L_i f is small on the high-|X_i| sites, the vector w concentrates elsewhere and cannot correlate well with the top eigenvector.Source: §1.3 · p. 10
- For β ≤ 1/2 + 5·10^-5, the proof overview establishes a spectral gap for the SK Glauber dynamics; the authors say this range is unoptimized.They expect the techniques may extend the range further.Source: §1.3 · p. 10
2 Preliminaries
The preliminaries set notation and develop the two-spin Ising and GOE facts used later. They also establish a small-interaction Taylor expansion and explain how GOE eigenvectors spread their mass across coordinates.
2.1 Notation and basic facts
- Capital letters denote random variables, bold letters denote vectors, and a β-GOE matrix has independent Gaussian off-diagonal entries with variance β^2/n and zero diagonal.Source: §2.1 · p. 11
2.2 Ising measure
- The two-spin Ising measure factors into a product measure at zero interaction, with means tanh a and tanh b for its spins.The section also defines conditional means X(y) and Y(x).Source: §2.2 · p. 11
2.3 Taylor expansion of two-state Ising model around zero interaction
- For small interaction J, the paper expands two-spin quantities around J=0, with a second-order Taylor formula and a remainder controlled by a bound on the second derivative.The expansion is used later to prove a rank-1 perturbed trickledown condition for a conditioned two-spin system.Source: §2.3 · pp. 12–13
2.4 GOE random matrices
- A β-GOE matrix has operator norm converging in probability to 2β, while its top-eigenvalue eigenvectors have mass spread across every subset of δn coordinates.The latter is the stated interpretation of the eigenvector delocalization result.Source: §2.4 · pp. 14–15
3 Proof of Theorem 1.5
The proof establishes Theorem 1.5 through β ≤ 1/2 + ε by combining a local rank-1 perturbation inequality with an average bound on its loss. Its key local estimate does not depend on the external fields of the two-spin measure.
Proof of Theorem 1.5
- The main technical lemma bounds the local inequality uniformly in the two external fields a and b.Its statement supplies a threshold j(d, λ, s) for the interaction magnitude.Source: §3 · p. 19
- The proof averages the rank-1 matrix contribution over pinned configurations and sums over spin pairs to control the perturbation loss.The construction uses that the matrix with entries (x_i + sX_i)(x_j + sX_j) is rank one.Source: §3 · pp. 19–20
- In Case 2, the proof claims that for every β ≤ 1/2 + ε, the stated property holds with high probability; Case 2 is stated for 1/2 − ε ≤ β ≤ 1/2 + ε.Source: §3 · p. 21
4 Proof of the local inequality
This section proves the local inequality by representing two-spin functions in a product-measure basis and showing the associated quadratic-form matrix is positive semidefinite for sufficiently small interaction.
Proof of the local inequality
- At zero interaction, 1, φ(X), φ(Y), and φ(X)φ(Y) form an orthonormal basis, allowing any two-spin function to be decomposed in these terms.Source: §4 · p. 23
- The inequality is encoded by a 3-by-3 matrix A, whose leading-order part A0 is positive definite when the parameters satisfy the stated condition.The remaining error matrix has operator norm O(|J|), so sufficiently small |J| preserves positive semidefiniteness.Source: §4 · pp. 23–24
- The proof computes the actions of LX and LY on the basis functions, then uses them to express the local quadratic form through its matrix entries.Source: §4 · p. 25
5 Proof of Lemma 4.2
The proof of Lemma 4.2 applies the master Taylor expansion to several functions of the two spins and their local operators. It combines constant and linear terms to obtain the stated estimates.
Proof of Lemma 4.2
- The proof applies the master Taylor expansion to functions built from RX, RY, φ(X), φ(Y), and M, using boundedness conditions to control the remainder.Source: §5 · pp. 29–30
- Under the J=0 measure µ0,a,b, E[φ(X)^2]=1 and the factorized product E[φ(X)^2]E[φ(Y)^2]=1, so both second moments equal 1.Source: §5 · pp. 30–31
- For MRXRYφ(X)φ(Y), the proof computes the constant term and the term linear in J, then combines them to establish the assertion and its symmetric counterpart.Source: §5 · p. 31