PaperlayerView exact revision on arXiv

Source-linked AI summary

Potential Hessian Ascent IV: Sampling the Sherrington-Kirkpatrick model at $\beta < 1$

Holden Lee, Juspreet Singh Sandhu, Jonathan Shi

arXiv:2609.30590v1math.PRcs.DSmath-phmath.MP

TL;DR

Sampling the SK Gibbs measure efficiently throughout β < 1 is the paper’s target, beyond the authors’ earlier β < 1/2 result. The paper uses stochastic localization with local TAP regularity and proves a polynomial-time sampler with o(1) TVD error; its stated regime stops at β < 1.

  • Problem

    The prior sampling framework used global regularity, which fails for some TAP-based quantities in the regime 1/2 ≤ β < 1.

    Source: §1.1 · p. 2, §2 · p. 5

  • Method

    The analysis restricts regularity requirements to a safe set around likely paths, where the TAP free energy is locally strongly convex, and adapts SDE and Jarzynski-equality analysis.

    Source: §1.1 · p. 2, §2 · p. 5

  • Results

    For fixed 0 < β < 1, Algorithm 2 runs in polynomial time and achieves o(1) TVD error with probability at least 1 − δ over A ∼ GOE(n), for sufficiently large n.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The result extends the authors’ sampling guarantee to the full β < 1 regime, which characterizes the high-temperature regime without an external field.

    Source: §1 · p. 2

    The approach is scoped to β < 1; above β = 1, no stable algorithm can sample with small W2-distance error.

    Source: Functional inequalities and fast mixing · p. 4

Abstract

from arXiv · show

We give a polynomial-time algorithm to sample from the Gibbs measure of the Sherrington-Kirkpatrick (SK) model with $o_n(1)$ error in total-variation distance (TVD) at any inverse-temperature $\beta < 1$. The algorithm combines algorithmic stochastic localization (ASL) with rejection sampling over path-space via Jarzynski's equality (JE). The analysis extends the authors' prior $\beta < 1/2$ result [arXiv:2605.03718] by replacing all global regularity requirements in the stochastic differential equation (SDE) error analysis with local regularity around likely trajectories. The relaxed regularity is established using Celentano's proof of the local strong convexity of the TAP free energy [arXiv:2208.09550]. The analysis utilizes the cavity interpolation theory and free probability toolkit developed in the authors' previous result, where the former applies nearly verbatim and the latter applies supplemented with Lipschitz and $C^2$ extensions of various functions. The ASL and JE analysis arises from using the TAP free energy as an efficiently computable proxy for the actual free energy of the stochastically localized Gibbs measure [$ \S $ 3, arXiv:2605.03718]. We give a list of \vocab{desiderata} encapsulating the approximation and regularity properties required of the TAP free energy, relaxing those of [$ \S $ 2.5, arXiv:2605.03718] to only require local regularity. These generic desiderata are potentially applicable in other settings where a free energy surrogate exists, giving algorithmic sampling guarantees while bypassing the usual functional inequalities based approach.

1. Introduction

The paper gives a polynomial-time sampler for the SK Gibbs measure at every fixed β < 1 with o(1) total-variation error. It extends local-regularity analysis along likely stochastic-localization paths and combines it with existing sampling and spin-glass tools.

1. Introduction

  • With probability at least 1 − δ over A ∼ GOE(n), Algorithm 2 samples a distribution with o(1) TVD error from μβA in polynomial time for fixed 0 < β < 1.The guarantee holds for all sufficiently large n, with the threshold depending on β and δ.Source: §1 · p. 2

1.1. Technical overview.

  • The analysis relaxes the prior β < 1/2 framework’s global regularity requirements to local regularity around likely stochastic-localization paths.It formulates relaxed desiderata and extends SDE error analysis, covariance-diagonal control, and regularity proofs to non-convex sets.Source: §1.1 · p. 2
  • The algorithm rejects trajectories that leave the safe set and uses a modified sampler for the localized distribution [KSTZ26].Its informal path-space step computes Jarzynski weights, restarts after safe-set exits, and accepts trajectories probabilistically.Source: §1.1 · pp. 2–3
  • Uniform local strong convexity along the stochastic-localization process is established by combining local TAP convexity with process stability.The proof uses small neighborhoods around late-stage AMP iterates and the established characterization of stochastic-localization stability [Cel24, Theorem 2; AMS22, Lemma 4.9].Source: Analysis · p. 3

1.2. Related work.

2. Sampling via ASL-JE under local regularity

The section adapts ASL-JE sampling to β < 1 by requiring regularity only near likely stochastic-localization paths. It defines a safe set and desiderata for the TAP free energy, then uses rejection sampling and a localized sampler.

2. Sampling via ASL-JE under local regularity

  • Local convexity around likely SL paths, established up to β < 1, replaces global regularity requirements; the analysis handles paths that escape the safe set with extensions and bounds.The proof uses Lipschitz or C^2 extensions, short paths within the safe set, and resolvent-identity bounds.Source: §2 · p. 5

2.1. TAP free energy and the safe set.

  • The safe set consists of points near which the TAP free energy is sufficiently strongly convex, with a unique associated y solving the TAP equation.The map from m to y need not be injective across the safe set, though it is locally injective.Source: §2.1 · pp. 5–6

2.2. Desiderata.

  • The desiderata formalize TAP free energy approximation and regularity requirements, including covariance accuracy, local Hessian convexity and regularity, drift error, and Lipschitz controls.They are stated over SL paths or points in the safe set on a high-probability event.Source: §2.2 · p. 6
  • For sufficiently small wedges, the desiderata also require an efficient sampler for the localized distribution, with a stated TV-distance guarantee.The wedge is a Hamming ball around a sign vector.Source: §2.2 · p. 7

2.3. Algorithm.

  • The algorithm first uses ASL-TAP-JE and rejection sampling to obtain an approximate sample, then samples from the localized distribution using it as a warm start.The localized sampler is restricted to a Hamming ball around the initial sign vector.Source: §2.3 · p. 7

3. Quantitative SDE analysis

This section analyzes TAP-based stochastic localization using regularity on a safe set rather than global regularity, establishing local SDE comparison bounds and well-posedness up to safe-set exit. It also derives survival-restricted Jarzynski and concentration results for the extended dynamics, then uses survival-aware rejection sampling to prove the final TVD guarantee.

3. Quantitative SDE analysis

  • TAP-based processes are defined on a safe set, with drift and diffusion extended outside it; the estimated magnetization can depend on the path because TAP solutions are only locally unique.The analysis tracks the magnetization associated with the ideal stochastic-localization path rather than treating it as a globally defined function of the tilt.Source: §3 · p. 8

3.1. O(1) Wasserstein and KL bounds.

  • With locally Lipschitz coefficients and bounded drift and diffusion errors, synchronous coupling gives O(1) expected Wasserstein error and o(1) bad-event probability when the ideal path stays safe with high probability.The stated regime takes coefficient errors and Lipschitz constants as O(1), the safe-path failure probability as o(1), and the safe-set expansion radius as omega_n(1).Source: §3.1 · p. 9
  • Under desiderata (d1), (d2a), (d2b), (d3), and (d4), ASL-TAP has O(1) KL error relative to stochastic localization.Source: §3.1 · p. 13

3.2. Jarzynski’s equality with survival.

  • A survival-restricted Jarzynski equality compares SL-TAP and ASL-TAP path measures and final magnetization marginals, enabling rejection sampling with o(1) error when survival has probability 1-o(1).Under the stated desiderata, the ideal SL magnetization path survives with high probability.Source: §3.2 · pp. 13–15

3.3. Well-posedness.

  • Under (d3), dual SDE coefficients are bounded on the safe domain; if ||A||op <= 3 and 0 is in the safe set, the equations have pathwise-unique strong solutions up to exit, with stopped solutions defined for all t.Source: §3.3 · p. 15
  • The process stays in (-1,1)^n up to safe-set exit, where its ASL tilt and Jarzynski weight have finite limits and can be stopped.At a finite exit, the dual process reaches the boundary of its domain.Source: §3.3 · pp. 15–16

3.4. Pathwise concentration.

  • Under the stated assumptions, a globally extended ASL-TAP process agrees with the original until safe-set exit and yields pathwise concentration and sub-Gaussian Jarzynski weights.The path law satisfies a T2 transport inequality, which gives sub-Gaussian concentration for Lipschitz path functionals and the stopped Jarzynski weights.Source: §3.4 · pp. 16–17

3.5. Algorithmic error analysis and proof of main theorem.

  • o_n(1) total-variation error is achieved in poly(n) time by sampling the tilt path and then sampling from its localized Gibbs measure.The error analysis combines survival, drift, log-weight, path, and ratio errors; with constant parameters and vanishing failure probabilities, the total error remains o_n(1).Source: §3.5 · pp. 18–19

4. Uniform TAP Hessian positivity over the stochastic localization process

The section establishes local strong convexity of the TAP Hessian around AMP iterates, then extends it uniformly along the stochastic-localization path and derives a Löwner-order sandwich on the safe set.

4.1. “Hybrid” local strong convexity.

  • With high probability, the TAP Hessian is uniformly positive in an ℓ2-ball of radius Ωβ,t(√n) around a sufficiently late AMP iterate.This holds for fixed β,t > 0 and sufficiently many AMP iterations.Source: §4.1 · p. 21
  • The hybrid argument tests the TAP Hessian on AMP iterates from [AMS22], adapting Celentano’s local-convexity proof [Cel24].Its low-dimensional reduction yields a negative Schur complement, which gives the strict upper bound needed for local convexity.Source: §4.1 · pp. 20–22

4.2. Covering the entire SL path via ℓ2-balls centered at posterior means.

  • With probability 1 − o_n(1), balls of radius ρ√n around the posterior means lie in the safe set for every t ∈ [0,T].The proof combines fixed-time convexity balls with control of SL fluctuations over small time intervals and a finite subcover of the time interval.Source: §4.2 · pp. 22–23

4.3. Löwner order sandwich on the safe set.

  • On the safe set, the TAP Hessian and the inverse covariance satisfy a Löwner-order sandwich.The Hessian lower bound follows from path-wide local convexity; the sandwich is obtained by inverting the Hessian and combining positive-definiteness with an upper bound.Source: §4.3 · pp. 24–25

5. Resolvent analysis: Regularization, uniform concentration and interpolation

This section regularizes the resolvent outside the safe set and develops fluctuation, free-probability, and uniform diagonal-resolvent estimates, with the extension agreeing with the original resolvent on the safe set and enabling comparison with the ideal free limit. For $0<\beta<1$, it controls the diagonal of the squared resolvent with high probability on the safe set.

5. Resolvent analysis: Regularization, uniform concentration and interpolation

  • Regularizing the resolvent over the full domain avoids conditioning on an A-dependent safe set, while preserving agreement on that set and enabling comparison with the ideal free limit.Uniform concentration and control of the expected squared-resolvent diagonal are combined by a triangle inequality before restricting to the safe set to obtain the spectral cutoff.Source: §5 · p. 25

5.1. Bounded extension of matrix inverse.

  • For 1/2 < β < 1, a bounded C2 extension of the reciprocal handles potentially singular matrices and agrees with the original weighted squared inverse when the safe-set spectral cutoff holds.Its block representation depends affinely on A, providing the structure used for the later interpolation and chaining arguments.Source: §5.1 · pp. 25, 27

5.2. Chaining argument for fluctuations around expected value.

  • Theorem 5.4 establishes a chaining bound for fluctuations of the regularized resolvent functional under GOE randomness, using mixed-Lipschitz estimates and sub-Gaussian concentration.The extension is defined over the full domain and matches the original quantity on the safe set.Source: §5.2 · pp. 29–31
  • Chaining bounds fluctuations around the expected value, while GOE Herbst concentration gives a high-probability bound for the supremum of the centered functionals.The supremum is βκT-Lipschitz, which permits the concentration step.Source: §5.2 · p. 32

5.3. Expected value from free probability.

  • Under the free-limit spectral-gap condition, smooth envelopes transfer resolvent comparisons to an expectation bound for the reciprocal extension.The proof sandwiches the reciprocal extension with smooth functions, applies the smooth-test comparison, and uses the common free limit.Source: §5.3 · pp. 35–36

5.4. Uniform estimate for the diagonal.

  • The diagonal squared-resolvent estimate holds uniformly over valid D and diagonal T with ∥T∥L2 = 1, with probability at least 1 − 4e^(−n/4), for n ≥ n0(β,γY).Source: §5.4 · p. 37

6. Properties of the algorithmic stochastic process

This section establishes the local regularity properties needed for the algorithmic stochastic process on a good set, rather than requiring global bounds. It combines resolvent and diagonal estimates with a path construction to obtain the algorithmic desiderata.

6.1. High-probability events.

  • With high probability, the analysis obtains uniform diagonal control on the good set under the stated operator-norm and event assumptions.The event intersection has probability at least 1 − 4e^(−n/4).Source: §6.1 · p. 38

6.2. Basic resolvent and Lipschitzness bounds.

  • On the good set, the resolvents are positive definite and satisfy bounds and Lipschitz estimates used in the subsequent analysis.The input uses Euclidean distance and the output uses normalized Schatten 2-norm.Source: §6.2 · p. 38

6.3. Diagonal error from rank-1 term of TAP Hessian.

  • The analysis bounds the diagonal error between the resolvent Q and the version with the rank-one TAP-Hessian term.The difference is controlled on the good set by comparing the two resolvents.Source: §6.3 · p. 39

6.4. Control of the diagonal.

  • On the good set, the section establishes basic diagonal properties and uniform diagonal control under the high-probability event.Source: §6.4 · pp. 39–40

6.5. Error between ASL-TAP and PHD is small.

  • The drift discrepancy between ASL-TAP and PHD is small on the good set.The discrepancy is the term Q(m)(m − f(m)).Source: §6.5 · p. 40

6.6. Lipschitz extension of the JE weight integrand.

  • To control the Jarzynski-weight integrand on the nonconvex good set, the analysis constructs short paths preserving the resolvent spectral gap and proves the integrand is Lipschitz.The path length is bounded in terms of the endpoint distance.Source: §6.6 · pp. 40–41

6.7. Implications for the sampling algorithm.

  • The resulting desiderata give the algorithm local regularity bounds for its coefficients, drift, and Jarzynski-weight integrand.The coefficient bounds apply on the good set, and the JE integrand bound follows from Lemma 6.9.Source: §6.7 · p. 42

7. Sampling from the time-T localized distribution

The section uses a thresholding time to make the ASL-TAP-JE procedure a warm start for an annealing sampler on a small wedge. It establishes polynomial-time sampling from that localized distribution with vanishing TVD error.

7. Sampling from the time-T localized distribution

  • The localized distribution can be sampled in polynomial time with o_n(1) TVD error by combining an ASL-TAP-JE warm start with annealing on a small wedge.The annealing sampler is run around a fixed tilt, with thresholding time T(β) determining how long the warm-start procedure runs.Source: §7 · p. 43
  • The approach replaces the prior polarized-walk sampler, whose shift and union-bound argument imposed β < 1/2, with a Dobrushin-type condition on the wedge.The localized measure concentrates on a sufficiently small wedge with high probability.Source: §7 · p. 43
  • For 0 < β′ < β, the wedge sampler uses 2log(16/ε²(β′)) annealing levels and poly(n)log(1/ε) Markov-chain steps per level to obtain ε TV error.The guarantee holds uniformly over the tilt y, with the wedge centered at sign(y).Source: §7 · p. 43

A. Resolvent product regularity and subordination at the TAP value

This section has two goals: finite-difference bounds for resolvent-product matrices and a spectral-gap proof for a free convolution at the TAP value.

A. Resolvent product regularity and subordination at the TAP value

A.1. Regularity estimates for resolvent products.

This subsection develops finite-difference regularity estimates for resolvent products, using discrete matrix identities under a positive spectral-gap condition.

A.1. Regularity estimates for resolvent products.

  • The estimates extend the earlier resolvent-product bounds to finite differences when the resolvent spectrum has a positive lower bound.The text identifies them as analogues of [DLSS26a, Lemma B.4].Source: §A.1 · p. 46
  • The setup defines inverse, shifted-inverse, and resolvent maps for invertible symmetric W and matrices M, assuming a positive spectral gap and bounded operator norm.Under these assumptions, the resolvent and its products have operator-norm bounds.Source: §A.1 · p. 46
  • The proof derives the bounds through discrete noncommutative sum, product, power, and inverse rules, including the resolvent identity.The resulting estimates control finite differences of resolvent products.Source: §A.1 · p. 46

A.2. Free analysis at the TAP value of a = β2 trn[D−1(m)].

For 0 < β < 1, the TAP value a = β^2 tr_n(D^-1) lies below the free spectrum, and the free resolvent expression yields an explicit target.

The TAP free limit

  • For 0 < β < 1, the free expectation is I_n / (1 − β^2 tr_n(D^-2)).The identity is stated for D ⪰ I_n and a = β^2 tr_n(D^-1).Source: §A.2 · p. 47

The free gap

  • The TAP value a = β^2 tr_n(D^-1) is separated from the free spectrum by a positive gap.The proof uses the exterior branch of the inverse-subordination map and its range to establish the gap.Source: §A.2 · pp. 47–48

The product cutoff and the target

  • The free product is at least (1 − β)^4(1 + 2β^2)^−2 I_n, providing the required buffer.The passage states that this bound and (A.2) imply the buffer.Source: §A.2 · p. 48
  • Subordination gives F(a) = 0 and F′(a) = 1 / (1 − β^2 tr_n(D^-2)), yielding the free target.The derivative is evaluated at a outside the free spectrum.Source: §A.2 · p. 48

B. Self-stability for the cavity interpolation of [DLSS26a, §5] at β < 1

The section extends key cavity-interpolation estimates to β < 1 by establishing Nishimori, concentration, and spectral self-stability conditions across that range.

Extension of cavity interpolation theory

  • The cavity-interpolation desideratum (1) holds for the full range β < 1, rather than the prior stated β < 1/2 range.The passage says only two statements in the prior arguments need strengthening.Source: B. Self-stability for the cavity… · p. 48

Nishimori condition up to β < 1

Spectral self-stability for M up to β < 1

  • For every β < 1, the self-stability operator satisfies β^2ρ(M) < 1.The argument replaces a lossy Frobenius-norm bound with the Nishimori identity and a similar matrix whose largest singular value is bounded by 1.Source: B. Self-stability for the cavity… · pp. 48–49

Overlap and magnetization concentration

  • For 0 < β < 1 and fixed finite t ≤ T(β), overlap and magnetization concentration hold.The extension uses uniqueness of the fixed-point solution and the validity of the overlap-concentration argument in this range.Source: B. Self-stability for the cavity… · p. 48

Covariance estimate for β < 1

  • Under overlap and magnetization concentration and the spectral-radius bound, the covariance estimate extends to 0 < β < 1.The theorem states the estimate for every t in [0,T(β)] when sup_t ε(β,t) is finite.Source: B. Self-stability for the cavity… · p. 49

C. Algorithmic error analysis

This section gives an approximate rejection sampler for an unknown normalizing constant and analyzes its sampling error using path-space comparisons.

Approximate rejection sampling with unknown normalization

  • The approximate rejection sampler uses samples from an approximate proposal and an approximate ratio function to produce an output distribution.The algorithm draws initial samples to estimate a quantile cutoff, then repeatedly proposes a sample and a uniform random variable.Source: C. Algorithmic error analysis · p. 50
  • The sampler’s guarantee depends on proposal-sampling error, ratio tails and error, and bounded weights on good events.The lemma states conditions involving ε_sample, ε_weight, ε_ratio, failure probabilities, and cutoff parameters C1 and C2.Source: C. Algorithmic error analysis · pp. 50–51

Algorithmic error analysis

  • The path-space analysis compares stopped and approximate processes, then transfers the resulting guarantee to the time-T marginal.The proof uses Girsanov’s theorem and applies the rejection-sampling lemma to the path measures.Source: C. Algorithmic error analysis · pp. 51–52
  • The stated final total-variation error bound is 5ε + δ + δ′ + 768C′_1√δ̂.The proof presents this bound after combining the component errors.Source: C. Algorithmic error analysis · p. 52

Related papers

Loading 2609.30590v1…