Simulated annealing and Weak Poincar\'e inequalities with inverse-polynomial accuracy for the Sherrington-Kirkpatrick model

1.1. Our results.

• n^-M total-variation error is achieved in polynomial time for every fixed β<1, with success probability at least 1−n^-D over the interaction matrix.The stated WPI applies simultaneously to every ε∈[n^-M0,1/2] and every function; the results also include an estimate of Z_A(0) with runtime n^Oβ,M,D(1) log(1/η).Source: §1.1 · pp. 2–3

1.2. Related work.

• Prior algorithmic stochastic localization sampling achieves vanishing normalized 2-Wasserstein error throughout β<1, whereas this paper targets total-variation distance.The passage distinguishes the metrics by the coupling quantity each measures: expected fraction of disagreeing coordinates versus probability of any disagreement.Source: §1.2.1 · p. 3

1.2.1. Algorithmic stochastic localization.

• Potential Hessian ascent uses TAP-corrected Hessians for near-optimal configurations, while a later sampling adaptation uses inverse TAP Hessians with Jarzynski reweighting and rejection sampling.The cited sampling approach is reported to achieve polynomial-time sampling with vanishing TV error.Source: §1.2.1 · p. 3

1.2.2. Rapid mixing of Glauber dynamics.

• Polynomial mixing from every initial configuration had reached β≤1/2+c for an absolute c>0, while a separate result covers any fixed β with a sufficiently strong constant external field.The strong-field result is an exception to the high-temperature setting and includes a field whose strength is independent of n.Source: §1.2.2 · p. 3

1.2.3. Glauber dynamics from a warm start.

• Earlier weak-Poincaré work for SK covered β<1/2 and analyzed Glauber dynamics from a warm start, but its inequality was not strong enough for simple simulated annealing.Source: §1.2.3 · p. 4

1.2.4. Zero-free methods.

• A zero-free method gives deterministic quasipolynomial-time partition-function approximation throughout β<1; Table 1 compares guarantees across four approaches.The table caption specifies typical SK interaction matrices and notes that the strong-field result includes an external field.Source: §1.2.4 · p. 4, Table 1 · p. 4

1.3. Concurrent work.

• Concurrent work reports polynomial-time sampling throughout β<1 with o_n(1) TV error using potential Hessian ascent; the paper contrasts this with its WPI-based annealing sampler.Other concurrent preprints report a spectral-gap bound and worst-case TV cutoff throughout β<1, as well as critical-temperature mixing-time results.Source: §1.3 · p. 4

1.4. AI Disclosure.

• The authors report using AI in proof-strategy exploration and heavy calculations, then verifying AI-produced proofs and taking responsibility for correctness.They also state that AI suggested proof ideas later selected for concentration control and interpolation arguments.Source: §1.4 · pp. 4–5

2. Technical overview

• The simulated-annealing algorithm follows from [HMRW25] and the weak Poincaré inequality, whose improved defect dependence supports the algorithm.Source: §2 · p. 5

2.1. Variance decomposition.

• The variance decomposition controls its first term using a Poincaré inequality under strong external fields and its second through Gaussian isoperimetry on exact localization paths.The latter avoids the exponential loss from transferring probability masses between approximate and exact paths using only KL divergence.Source: §2.1 · p. 5

2.2. The idealized Lipschitz case.

• In the globally Lipschitz case, quantile comparison and Gaussian isoperimetry reduce the bound to nearby Brownian paths and yield a weak Poincaré inequality with defect ε.The comparison uses the Lipschitz posterior mean to relate nearby paths to nearby fields and posterior distributions.Source: §2.2 · pp. 6–7

2.3. A locally Lipschitz approximation to the posterior mean.

• Because global Lipschitzness is not known across β < 1, the method uses a locally Lipschitz approximation and a cost function to bound cumulative failures along paths and at the endpoint.This gives the same polynomial-in-1/ε weak Poincaré inequality as the idealized case, with additional polynomial factors in n.Source: §2.3 · pp. 7–9

2.4. TAP stationary points are locally Lipschitz.

• AMP locates a locally strongly convex TAP region whose stationary point is locally Lipschitz; bounding the TAP residual at the posterior mean yields O(log n) approximation error with time-uniform constants.The method uses AMP to locate the region, while the posterior-mean residual controls approximation to the stationary point.Source: §2.4 · pp. 9–10

2.5. From post-AMP geometry to the TAP residual bound.

• Once the posterior mean and TAP stationary point lie in a common strongly convex region, strong monotonicity bounds their distance by the TAP residual at the posterior mean.The residual is analyzed using the exact Bayesian structure of the posterior mean.Source: §2.5 · p. 11

2.5.1. The TAP residual.

• The prescribed TAP residual has norm O(log n) except with probability n^-H for every fixed H, uniformly for fixed beta and t.Overlap concentration transfers the bound from the empirical-overlap residual to the prescribed-overlap residual.Source: §2.5.1 · pp. 11, 13

2.5.2. Stability under deletion of one coordinate.

• Deletion stability controls residual changes by O(n^-1/4) in Lp, while integrated drift and recombination errors are O(n^-1/2) in Lp.The proof uses Gaussian smoothing and a stochastic-localization interpolation; deleted-system residuals make the tail event conditionally measurable, enabling moment bounds and an iterated tail recursion.Source: §2.5.1 · p. 12, §2.5.2 · p. 13

2.5.3. Probability boosting for geometric properties.

• Gaussian concentration boosts the first two AMP geometric properties to exponentially small failure probability, while overlap and Gaussian concentration control posterior-mean closeness to AMP.A fixed AMP depth makes the expected squared distance small relative to the convex-basin radius, after which Markov's inequality gives the probability bound; the posterior mean's Lipschitzness is difficult to establish.Source: §2.5.3 · p. 14

2.6. From WPI to simulated annealing.

• The weak Poincaré inequality supports polynomial-time simulated annealing [HMRW25], whereas Davies et al.'s inequality for beta < 1/2 does not suffice for that guarantee [DLSS26b].Davies et al. instead construct an approximate warm start using Langevin dynamics with a TAP-based drift, followed by Glauber dynamics for the localized distribution.Source: §2.6 · p. 14

3. Preliminaries

• For β<1, μ_A,y is the Gibbs law with weights exp(β⟨x,Ax⟩/2 + ⟨y,x⟩), normalized by Z_A(y).Source: §3.1 · p. 14

3.1. The planted model.

• The original model draws a zero-diagonal symmetric A with independent N(0,1/n) off-diagonal entries; the planted model adds βXX⊤/n to GOE W and observes Y_t=tX+B_t.Source: §3.1 · p. 15

3.2. Wiener space and Gaussian estimates.

• Gaussian isoperimetry bounds the Cameron–Martin shift needed to connect two Wiener-measurable sets of measure greater than v/4 by 2√(2 log(4/v)).The Cameron–Martin space consists of absolutely continuous paths starting at zero with square-integrable derivative.Source: §3.2 · pp. 15–16

3.3. Stochastic localization.

• In stochastic localization, the posterior mean is a bounded martingale, the innovation is Brownian, and the observed field has the same path distribution as the Wiener-driven construction.Source: §3.3 · p. 17

3.4. Scalar overlap, TAP free energy, and AMP.

• For β<1, the scalar-overlap fixed point q_β(t) is unique, satisfies q_β(0)=0 and q_β(t)≤t/(1−β²), and the TAP free-energy gradient equals its prescribed-overlap residual.Source: §3.4 · pp. 17–18

4. TAP residual bounds

• The unnormalized squared TAP residual is O(log n) with failure probability at most n^-H for every fixed H>0, for inverse temperatures bounded by β*<1.The section proves Theorem 2.2 under a fixed common upper bound β* on inverse temperature.Source: §4 · p. 18
• The empirical-versus-prescribed-overlap correction to the TAP residual is small with high probability.The correction is defined using the difference between the empirical overlap Q_n(m) and the prescribed overlap q_β(t).Source: §4 · p. 18

4.1. Overlap concentration and covariance bounds.

• Lemma 4.2 establishes finite-dimensional overlap exponential-moment and moment bounds, including versions for replica–plant overlaps and the posterior mean.The constants depend only on β*, and the result holds for all n, β≤β*, and t≥0.Source: §4.1 · pp. 20, 24, 25
• The covariance subsection relates Tr Σ² to a four-replica observable and states posterior covariance moment bounds.The covariance moment results are stated for the planted model with nℓ≤β*² and t≥0.Source: §4.1 · p. 25
• Overlap concentration yields covariance trace-moment bounds used to control TAP residuals.The supplied passage states this consequence but does not show the moment orders or their quantitative bounds.Source: §4.1 · p. 25

4.2. Conditional residual moments.

• For p≥2, conditioning on observations outside a row controls its residual in Lp by exploiting cancellation between the row contribution and Onsager correction.The row-residual estimate is applied to conditional residual moments; the residual also decomposes into the row residual and cubic and diagonal terms.Source: §4.2 · p. 26
• Linear-in-p moment bounds for each conditional second moment imply an exponential moment for their sum.The resulting exponential-moment constants depend only on β* under Lemma 4.5's assumptions.Source: §4.2 · p. 27

4.3. From conditional moments to residual tails.

• Deleting one coordinate changes the residual norm by O(n^-1/4) in each fixed L4p norm, enabling conditional tail bounds to transfer to the full residual.The argument uses an event measurable with respect to surviving observations, controls the deletion error, then restores the prescribed overlap; it obtains failure probability at most n^-H with constants uniform over β and t in the stated ranges.Source: §4.3 · pp. 28, 30

5. Lipschitz property with cost functions

• AMP locates locally strongly convex TAP regions containing both the posterior mean and a local stationary point, whose distance is controlled by the TAP residual.For each fixed β and t>0, the stated geometric conditions hold except with probability at most C_H n^-H.Source: §5 · pp. 30–31
• At fixed AMP depth, the AMP center is Lipschitz in the external field, with a constant depending only on the depth.The proof compares AMP recursions inductively and uses the one-Lipschitz property of tanh.Source: §5 · pp. 31–32
• Small TAP residual and local strong convexity give a unique stationary point near the AMP center; strong monotonicity then controls how it changes across fields.The point lies within r√n/32 of the center, and the comparison yields a 4κ-scaled bound when the fields’ centers are sufficiently close.Source: §5 · pp. 32–33

5.1. Local stationary points and their path and terminal costs.

• The local stationary-point construction is used to compare posterior means at certified fields, while uncertified fields receive a bounded fallback cost.The cost is defined from the posterior-mean approximation error on the certified domain and set to 4n otherwise; averaging over an auxiliary diagonal gives a field-comparison bound.Source: §5.1 · pp. 34–35
• The path cost integrates the posterior-mean approximation error along localization, and the terminal cost is that error at time T.The local stationary-point map is Borel on its certified domain, supporting the path-cost construction.Source: §5.1 · pp. 33, 35
• For every fixed R>0, each cost is at most C_R log n except with probability at most n^-R.The path bound integrates fixed-time control while allowing occasional large errors; the terminal bound uses the fixed-time estimate at T.Source: §5.1 · pp. 35–36

6.1. Establishing a weak Poincar´e inequality.

• Gaussian isoperimetry selects nearby lower- and upper-quantile localization paths, while path-cost control bounds the accumulated errors in comparing their posterior expectations.The argument also uses a bound on averaged terminal posterior variance, established uniformly over β∈[β0,β1] with exponentially high probability.Source: §6.1 · pp. 39, 41
• For every ε∈[n^-M0,1/2], the WPI holds with probability at least 1−n^-D and coefficient at most C′n^(7+b)ε^-Γ, for sufficiently large n.The constants C, B, and N depend only on (β, D, M0).Source: §6.1 · p. 41

6.2. Simulated annealing.

• For any deterministic set B_n⊆[0,β*] of at most n^Csch temperatures, a single event of probability at least 1−n^-D gives the WPI uniformly over β∈B_n, ε, and functions.The common constants depend on β*, D, M0, and Csch.Source: §6.2 · p. 42
• The annealing analysis uses at most n stages, with consecutive inverse temperatures differing by at most 1/n, and applies the schedule-wide WPI to those stage temperatures.The section invokes discrete-time warm-start and simulated-annealing bounds of Huang, Mohanty, Rajaraman, and Wu [HMRW25, Theorems 4.6 and 4.13].Source: §6.2 · pp. 42–44

6.2. Simulated annealing

• The sampler achieves total-variation error at most n^-M with probability at least 1-n^-D and runs in polynomial time for fixed β, M, and D.Its total running time is n^O_{β,M,D}(1).Source: §6.2 · p. 44
• With probability at least 1-η, the partition-function estimate has relative error at most n^-M.It estimates consecutive partition-function ratios along the schedule using independent sampler runs, with total running time n^O_{β,M,D}(1) log(1/η).Source: §6.2 · pp. 44–45

Appendix A. Contiguity of the planted model

• The planted-model density is L_n(A)=exp(log Z_A(0)−n log 2−β^2(n−1)/4), and its mutual contiguity with the original model for β<1 follows from [EAKJ20, Theorem 2 and Corollary 3].The likelihood-ratio formula is identified as the Rademacher specialization of [EAKJ20, Eq. (3)].Source: Appendix A · p. 47
• A second-moment bound for the density also bounds its inverse moment, enabling probability comparisons in both directions.The appendix applies Cauchy–Schwarz to the density and reciprocal density to transfer event probabilities.Source: Appendix A · p. 48
• These comparisons transfer matrix-norm tail bounds to the planted law and fixed-time cost bounds back to the original augmented law.The comparisons use the forward and reverse directions of Lemma 3.3, respectively.Source: Appendix A · p. 48

Appendix B. Omitted proofs of TAP residual bounds

• Appendix B restates deferred main-section results and supplies auxiliary estimates used in their proofs.The appendix fixes the common upper bound β*<1 used in Section 4.Source: Appendix B · p. 48
• The first subsection proves Lemma 4.4.The passage identifies this as the first of the appendix’s two proof subsections.Source: Appendix B · p. 48
• The second subsection proves Lemma 4.7, with M_ℓ bounded above by β*.The appendix uses β* as the fixed upper bound for the inverse temperature.Source: Appendix B · p. 48

B.1. Gaussian estimates for cavity interpolation.

• Gaussian Poincaré bounds control smooth-function fluctuations, with constant C_2 = 1 at p = 2, while Meyer’s inequality controls Gaussian divergence.The estimates apply to smooth functions whose values and Jacobians are in Lp(G).Source: §B.1 · p. 49
• Conditioning on (F\i,U) leaves the covariance determined by surviving observations, and the proof averages over G before averaging over U.The covariance is not recomputed after revealing U.Source: §B.1 · p. 49
• Lemma 4.4 bounds the cavity-interpolation residual for any [−1, 1]-valued x, including x that depends on G and additional randomness.The proof separates two errors and combines their estimates using |x| ≤ 1 and Mℓ ≤ 1.Source: §B.1 · pp. 51–53

B.2. Stability under deletion of one coordinate.

• The proof decomposes the residual difference into an entropic remainder and a quadratic remainder, then identifies their combined contribution as Δ_Q.The algebra expands m_b = m_av + b m_dif.Source: §B.2 · p. 54
• In the planted model, the pinned and cavity residuals differ by at most C_p n^-1/4 in Lp, while the unconditional remainder terms are bounded by C_p n^-1/2.The bounds hold under the stated nℓ ≤ β*^2 condition, for fixed integer p and t in [0,T].Source: §4.3 · p. 28, §B.2 · pp. 53–54
• A localization path connects the cavity field y_-i to the pinned field y_-i + b a_i, enabling comparison of the residual laws.The comparison concerns the joint law of the initial residual and the path residual against the cavity and pinned residuals.Source: §B.2.1 · p. 55

B.2.1. From the cavity law to the pinned law.

• Conditioned on (F\i, X_i=b), the localization field a_ℓ and the interaction vector bJ_-i,i have the same distribution.Both are Gaussian mixtures over the same cavity law μ_-i.Source: §B.2.1 · p. 55
• Lemma B.4 derives an SDE for the residual along the field path y_s=y+sξ+eB_s.The path starts with ξ sampled from the Gibbs law at the initial field and an independent Brownian motion.Source: §B.2.1 · p. 55
• Under nℓ≤β_*^2, Lemma B.5 provides moment bounds for pinned-mean differences for each fixed p≥2.Source: §B.2.1 · pp. 57–58
• When Mℓ≤β_*^2, Lemma B.6 bounds the residual, covariance matrix, and drift along the localization path.The bounds apply for fixed p≥2.Source: §B.2.1 · pp. 58–59
• The residual Jacobian bound grows at most as C_p M^1/4 under the stated planted-model assumptions.The argument uses the path estimates and holds for fixed p≥2.Source: §B.2.1 · pp. 59–61
• Conditioning on X_i=b preserves the planted law for the deleted-coordinate system, allowing cavity-path estimates to transfer to pinned means.The argument matches the cavity observations to a planted model in dimension n−1 and uses stochastic-integral and moment bounds; it also justifies the differentiations and integrations used to establish the identities.Source: §B.2.1 · pp. 63, 65
• Substituting the preceding bounds into equation (36) yields the entropy-error bound ∥Δent∥_Lp ≤ C_p n^-1/2.Source: §B.2.1 · p. 67

Appendix C. Probability boosting for AMP good events

• Appendix C combines AMP stability and Gaussian concentration for exponentially reliable residual and local-convexity conditions, then uses overlap concentration and fixed-depth AMP estimates for posterior-mean proximity.The stated failure bounds are C e^-cn for the first conditions and C_H n^-H for every fixed H>0 for posterior-mean proximity.Source: Appendix C · p. 68

C.1. Useful lemmas.

• Lemma C.1 adapts and to establish small TAP residual, local strong convexity, and posterior-mean approximation at sufficiently large fixed AMP depth.The passage also introduces an operator-norm tail bound under the planted law, without giving its value here.Source: §C.1 · pp. 68–69
• The scalar fixed points vary Lipschitzly with the channel parameters and inverse temperature.The bounds apply over a fixed inverse-temperature interval [β0, β1].Source: §C.1 · pp. 69–70
• AMP centers and their TAP residuals vary Lipschitzly under perturbations to the matrix, field, time, and inverse temperature.The proof extends a fixed-depth recursion argument to these perturbations.Source: §C.1 · pp. 69–72
• The TAP Hessian changes in operator norm are bounded under perturbations of the inputs and inverse temperature.The comparison separates changes in the diagonal terms and bounds their contribution alongside the other perturbations.Source: §C.1 · pp. 69, 72

C.2. Convexity for small times.

• For 0 < β ≤ β1 < 1 and t ≤ t0, the TAP free-energy Hessian is at least (1 − β1)^2 I_n/2.The time threshold t0 is specified in Lemma C.4.Source: §C.2 · p. 72
• With probability at least 1 − C e^-cn, the interaction matrix satisfies the operator-norm control used in the convexity proof.The proof bounds ∥A_full∥op by 2 + εop ≤ 5/2 < 4.Source: §C.2 · p. 72

C.3. Handling large times.

• In an open parameter rectangle around the reference pair, the AMP center retains small TAP residual and local strong convexity with failure probability at most Ce^−cn.The transferred bounds are κr/16-small residual and (4r, 4κ)-local strong convexity.Source: §C.3 · pp. 73, 76
• The exponential failure bound is obtained by applying Gaussian concentration to distance from a good event and using stability under perturbations of the Gaussian input.The event is defined by the residual and local-convexity properties, which persist under sufficiently small perturbations.Source: §C.3 · pp. 74–76
• With probability at least 1 − Ce^−cn, the planted instance has both a small TAP residual and local strong convexity at fixed parameters and AMP depth.The residual is at most κr/32, and the local strong convexity parameters are (7r, 7κ).Source: §C.3 · p. 74
• Posterior-mean proximity holds throughout a nearby parameter rectangle with failure probability at most Cβ1,s,p n^−p for each fixed p ≥ 1.The proof combines a mean-square estimate with concentration.Source: §C.3 · p. 76

2. When both matrix norms

• The AMP squared norm and its overlap with the planted spin are O(1/√n)-Lipschitz in the standard Gaussian input when the matrix norm is at most 4.The extensions preserve this Lipschitz constant on the cutoff set.Source: §2 · p. 77
• The AMP squared norm and planted-spin overlap have concentration and stability bounds on compact parameter rectangles.The proof couples inputs using the same planted spin, GOE matrix, and Gaussian field; the second-part conclusion follows by taking expectations.Source: §2 · pp. 78–79
• For parameters near the reference pair, the mean-square error quantity a_n(β, t) is bounded by r²/4 for all sufficiently large n.At the reference pair it is at most r²/8; stability extends the bound to a sufficiently small rectangle.Source: §2 · p. 80
• A finite collection of parameter rectangles covers the compact temperature-time domain, with a fixed AMP depth and constants chosen for each rectangle.For a target exponent H, the argument sets p = max(1, ⌈H⌉) before combining the probability bounds.Source: §2 · pp. 80–81

Appendix D. WPI under a strong enough field

• A sufficiently strong field keeps the correlation-matrix operator norm at most 6 for large m, even with a field perturbation of order √m.The bound applies under the stated interaction-norm and small-submatrix assumptions.Source: Appendix D · p. 81
• For fixed δ∈(0,1) and sufficiently large n, Lemma D.2 assumes every nonempty pinning has conditional correlation-matrix operator norm at most 6 when |I|≥δn, and spectral width at most 2/5 when |I|<δn.Source: Appendix D · p. 81
• A conditioning argument iterates variance bounds after revealing coordinates, reducing the remaining variance to a bound on a uniformly chosen subset.For m remaining coordinates, the text gives Var_{ν_m}[f] ≤ (5m/3) E_{ν_m}(f,f), then combines the bounds using m ≤ n.Source: Appendix D · p. 82

D.1. Application to the SK model.

• A matrix event established by concentration and a union bound lets the proof apply Lemmas D.1 and D.2 to obtain the terminal-field Poincaré inequality.The event controls the full matrix and its small principal submatrices.Source: §D.1 · p. 82
• Lemma D.4 provides constants T0,C,N>0 depending only on (β0,β1), for n≥N, in the regime β∈[β0,β1] and |||y|−T0 1_n||2≤2√(T0n).Here μA,y denotes the Gibbs distribution at inverse temperature β and external field y.Source: §D.1 · p. 82
• The proof verifies the pinned-distribution conditions by bounding correlations for large coordinate sets and using the small-submatrix condition for small sets.It first changes spin signs to make the field nonnegative, which preserves variance and the Dirichlet form.Source: §D.1 · p. 83

• The proof splits the terminal posterior-variance expectation according to whether the terminal field satisfies Lemma D.4’s condition.Source: §D.2 · pp. 83–84
• To bound the bad-event probability, the proof represents Y_T0 as T0X + sqrt(T0)G and invokes Markov’s inequality and the Gaussian moment-generating function.Source: §D.2 · p. 83
• On the good event, Lemma D.4 bounds posterior variance by C n^7 times the expected Dirichlet form.Source: §D.2 · p. 84
• On the complement, variance is at most osc(f)^2/4; the proof combines this with the bad-event probability and the averaged Dirichlet-form inequality.Source: §D.2 · p. 84