Markov Chains Approximate Message Passing

Amit Rajaraman; David X. Wu

REVIEW 4 major objections 4 minor 5 references

Markov Chains Approximate Message Passing

T0 review · 4 major / 4 minor · reviewed 2026-08-03 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper proves that Glauber dynamics on the spiked Wigner posterior recovers the spike with correlation pinned to the largest fixed point of an AMP-like recursion, and that this correlation is positive exactly when β>1/λ, recovering the

desk verdict The fixed-point bridge from RGD to AMP is real and the RGD analysis is strong; the Glauber half is honestly conditional on SK mixing, and the paper's own runtime statements don't line up, but this deserves a serious referee. read the letter →

arxiv 2512.02384 v3 pith:3SISVXRE submitted 2025-12-02 cs.DS math.PR

Amit Rajaraman , David X. Wu This is my paper · ORCID

classification cs.DSmath.PR MSC 60J1082B4460K3568W20

keywords spikedWignerGlauberdynamicsapproximatemessagepassingstateevolutionrestrictedGaussianSherrington–Kirkpatrickmodelphasetransitionlocallystationarydistributions

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper establishes a formal equivalence between the short-term behavior of two very different algorithms on the spiked Wigner inference problem: Glauber dynamics, a Markov chain that attempts to sample a high-dimensional posterior, and Approximate Message Passing (AMP), an iterative estimator known to be Bayes-optimal. The bridge is an auxiliary chain, restricted Gaussian dynamics (RGD), whose correlation with the true spike is shown to follow a one-dimensional recursion identical to AMP's state evolution. Using that recursion, the paper proves that after polynomially many steps, Glauber iterates have correlation within N^{-1/2+ε} of the AMP fixed-point value OPT_{β,λ}, with OPT_{β,λ}>0 exactly when β>1/λ. A reader should care because this supplies a sharp, rigorous characterization of what a slow-mixing Markov chain achieves long before it equilibrates, and recovers the BBP transition as a byproduct.

What carries the argument

The central object is restricted Gaussian dynamics (RGD), an auxiliary Markov chain whose transition from σ samples a Gaussian field z = βλ⟨σ,x⟩/N + sqrt(βλ/N)g and then redraws σ from the SK Gibbs measure with that field. The paper reduces RGD to the one-dimensional map z ↦ E tanh(βg√q_{β,βλz} + βλz) using new high-precision mean-magnetization estimates for the SK model under weak external field (Lemma 6.1). That map has fixed-point equations identical to AMP's state evolution, and its stable fixed point controls the correlation reached by both RGD and—via transfer of local stationarity—Glauber dynamics.

What would settle it

For a fixed λ>1 and β just above 1/λ, numerically compute OPT_{β,λ} from the fixed-point equations, then run RGD from a warm start for T=log²N steps on a planted spiked Wigner instance and measure the mean absolute correlation; if it fails to approach OPT_{β,λ} within N^{-1/2+ε} as N grows, the one-dimensional reduction is wrong.

Watch

Extended reading notes

Core claim

The central claim is that the correlation between a Glauber iterate and the planted spike is asymptotically pinned to a constant OPT_{β,λ} defined as the largest fixed point of the scalar recursion z = E tanh(βg√q + βλz) and q = E tanh²(βg√q + βλz), where g is a standard Gaussian and q is the SK overlap parameter. The same equations are the state-evolution fixed points of mismatched AMP, so the paper proves that Glauber dynamics—run only for polynomial time, far before mixing—achieves the same recovery performance as AMP. The phase transition is sharp: OPT_{β,λ} is zero for β<1/λ and strictly positive for β>1/λ, recovering the BBP threshold λ=1 when the posterior temperature β=λ is used. The

Load-bearing premise

The Glauber-dynamics theorem assumes the Sherrington–Kirkpatrick model at β<1 with any uniform external field satisfies a modified log-Sobolev inequality with constant Ω(1/N), a condition currently proven only for β<0.295 and merely conjectured for all β<1.

Editorial extensions

If this is right

If the MLSI condition holds for all β<1, Glauber dynamics from any initialization has correlation within O(N^{-1/2+ε}) of OPT_{β,λ} after exp(O(N^{4-2ε})) steps.
The threshold for nontrivial recovery by Glauber is β=1/λ, matching the BBP phase transition λ=1 in the Bayes-optimal case β=λ.
RGD from a warm start reaches the stable fixed point in O(log N) steps, implying fast convergence of the correlation process before mixing.
At the posterior temperature β=λ, the RGD fixed point exactly equals the AMP state-evolution fixed point, so a sampling-based estimator can reach AMP-level correlation without waiting for full mixing.
The paper's high-precision magnetization estimates pin the mean magnetization of the SK model under weak field to order N^{-1/2+ε} for all β<1, a spin-glass result with independent uses.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

If the MLSI condition is eventually established for all β<1, the Glauber statement becomes unconditional and the technique would likely transfer to a broader class of spiked matrix priors, since the RGD reduction does not use the Boolean prior in an essential way.
The one-dimensional recursion suggests a testable prediction: annealed Glauber dynamics should trace the branch of stable fixed points OPT_{β,λ} as β increases past 1/λ, yielding the same threshold with a slow-heating schedule—going beyond the fixed-temperature result in the paper.
Because OPT_{β,λ} can increase beyond β=λ, samples from the posterior at β>λ may have larger correlation with the spike than the posterior mean, inverting the usual Bayes-optimality intuition; the authors flag this as a subtle consequence.
A direct numerical test of the recursion is feasible: simulate RGD at small N, measure the empirical correlation distribution at T=log²N steps, and compare to the numerically computed fixed point; a mismatch would pinpoint exactly where the one-dimensional reduction breaks.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Bottom line first: the paper has a genuinely new result — an exact fixed-point characterization of the correlation achieved by restricted Gaussian dynamics (RGD) on the spiked Wigner posterior, shown to match the AMP state evolution fixed points. The one-dimensional recursion in (4) is the right object, and the identification with AMP comes from algebra and standard state evolution, not from fitting; the circularity burden is genuinely low. The escape-from-the-unstable-fixed-point analysis (Lemma 5.6) and the high-precision SK magnetization estimates (Lemma 6.1) are real technical value, and the magnetization bounds are of independent interest. The paper is also honest about its limits: it states plainly that the Glauber-to-RGD transfer breaks for β>1 and that Condition 1 (SK MLSI) is only proved for β<0.295.

The soft spots, in proportion. The biggest: the Glauber theorem (5.2) is conditional on MLSI for β∈(0.295,1), and that conjecture is load-bearing — δ in Lemma 4.8 is exactly the MLSI constant, so if the constant is not polynomial the transfer is empty. The paper discloses this, so it is not a hidden flaw, but the abstract's 'we recover the phase transition' is stronger than what is conditional. Disclosed-but-oversold.

Second, the runtime claim and Theorem 5.2 don't agree. The introduction asks whether polynomial-time Glauber matches AMP; Theorem 5.2 requires T ≥ e^{Ω(N^{4−2ε})}, which is exponential. The proof sketch in Section 5 looks like it gives a bound on the order of (C log N)√(N^3/T), which would make polynomial T enough. So something is off — either the statement or the proof — and it needs fixing.

Third, Theorem 1.7 ("one step of RGD ≈ one step of AMP") is informal, deferred to a numerical condition. The algebra behind it is solid, but the headline version overstates the formal content.

Minor: RS-AT and AT-fixed-pt for β∈(1,λ) rest on numerical checks; the authors should ship verifiable code. And since the acknowledgments disclose AI-assisted proofs of several lemmas, a referee should check those lemmas especially carefully — the disclosure is fine, but it raises the verification bar, not lowers it.

If the central RGD analysis holds up — and it looks like it does — this is a serious paper for a serious referee. I'd send it out; I'd expect a revision that reconciles the runtime statement and tightens the informal claims.

Referee Report

4 major / 4 minor

Summary. The paper studies the spiked Wigner inference problem and proposes a formal connection between the correlation dynamics of Markov chains and Approximate Message Passing (AMP). The main object is an auxiliary chain, Restricted Gaussian Dynamics (RGD), whose one-step update is shown (informally in Section 2.2) to mirror the AMP state-evolution recursion. The paper derives a one-dimensional recursion for the RGD correlation, proves under certain conditions that RGD reaches the largest fixed point OPT_{β,λ} from a warm start, and then transfers this to Glauber dynamics using locally stationary distributions, conditional on a modified log-Sobolev inequality for the Sherrington-Kirkpatrick model. It also proves high-precision mean-magnetization estimates for the SK model under weak external fields and analyzes the qualitative fixed-point structure of the recursion.

Significance. If the main theorems are correct, this is a substantial step toward a rigorous explanation of the empirical success of MCMC in Bayesian inference: it identifies the exact fixed-point correlation of RGD/Glauber with the AMP state-evolution fixed point and recovers the BBP transition. The RGD analysis is technically rich, particularly the weak-field magnetization estimates (Lemma 6.1 and Lemma 6.3) and the fixed-point analysis of the scalar recursion. The paper is commendably explicit about its conditional dependencies: Theorem 5.2 is stated only under the MLSI conjecture for the SK model, and the RGD-AMP comparison is presented as informal with a deferred numerical condition. These caveats are real and limit the current certainty of the headline Glauber claim, but the underlying RGD fixed-point analysis appears to be a serious contribution.

major comments (4)

[§5.2, Theorem 5.2, Condition 1] The proof of Theorem 5.2 transfers local stationarity from Glauber to RGD via Lemma 4.8, whose denominator δ is exactly the MLSI constant of the SK model with external field. The paper uses δ=Ω(1/N), which is Condition 1. As noted in the paper, this is proved only for β<0.295 (via AKV24) and is conjectured for all β<1. Thus the statement that Glauber recovers the BBP transition for all β>1/λ is conditional on an unproved conjecture in exactly the regime where it would extend beyond prior work. If the MLSI constant is not polynomial, the bound E_RGD ≤ O(N^3/T) cannot be made small enough to yield the claimed o(N^{-1/2+ε}) error with the stated exponential T. The paper is transparent about this, but the abstract and introduction should present the Glauber result as explicitly conditional on a conjecture, not as a settled recovery theorem.
[§2.2, Theorem 1.7] The claimed comparison 'one step of RGD ≈ one step of AMP' is never formalized. Theorem 1.7 is marked 'Informal, see Section 2.2', but Section 2.2 contains only algebra and a reference to a numerical condition; there is no formal theorem statement or proof. This is one of the paper's three advertised main contributions and it is the conceptual bridge that justifies the AMP fixed-point identification. Please state a precise formal theorem (with the required numerical condition clearly isolated) or explicitly demote this to a conjecture. As written, the reader cannot verify the central conceptual claim.
[§7.1, Lemma 7.5(ii), proof] The proof of monotonicity states f'_β(h) ≥ βλ( E[S^4] − E[S^2 T]^2 / E[S^2 T^2] ) ≥ 0, with the final step attributed to Cauchy–Schwarz. This inequality is not justified as written: Cauchy–Schwarz gives E[S^2] E[S^2 T^2] ≥ E[S^2 T]^2, not E[S^4] E[S^2 T^2] ≥ E[S^2 T]^2. The displayed term should likely be E[S^2] instead of E[S^4]. Since Lemma 7.5(ii) is used in Lemma 5.3 and hence in the convergence proof (Lemma 5.4) and Proposition 7.1, this is a load-bearing proof step and must be corrected. If the intended argument uses the AT condition in the form β^2 E[S^4]<1, the proof needs to be written out carefully.
[§1, Question 1.2; §5.2, Theorem 5.2] The introduction frames Question 1.2 around polynomial-time Glauber dynamics, but Theorem 5.2 requires T ≥ e^{Ω(N^4)} (and e^{Ω(N^3)} for the o(1) version in Remark 1.6). These are exponential runtimes, not polynomial. The paper should not imply that it resolves the polynomial-time question; it proves a characterization at super-polynomial time. If the intended message is 'progress' toward Question 1.2, that is fair, but the abstract and introduction should avoid giving the impression that polynomial-time Glauber success has been established. This is a framing issue, but it affects how the contribution is received.

minor comments (4)

[Abstract / §1] The term 'annealed posterior' is used without definition. The distribution μ_{βM} for β≠λ is not the true posterior; clarify the temperature parameterization early.
[§5, Lemma 5.6] The statement says 'max_{0≤t≤T} 1/N |⟨x_T,1⟩| ≤ ε' but the subscript of x should be t, not T. Please fix the typo.
[§6, Lemma 6.4 proof] The proof uses the symbol '(∗)' before it is defined. Define the expression explicitly or introduce a numbered equation.
[§2, Figure 2] The four panels are not accompanied by explicit parameter values or the fixed-point locations. Add axis labels and a short caption explaining the 'AT region' boundary.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the fixed-point recursion is derived from independent SK magnetization and AMP state-evolution results, not from fitting the target correlation.

full rationale

The paper's central reduction is a genuine derivation: RGD is expressed as a one-dimensional recursion (Eq. 5) using the SK mean-magnetization estimates (Lemma 6.1) plus standard overlap concentration, and the resulting fixed points are then shown to match AMP state evolution. The Glauber assertion in Theorem 5.2 is conditional on explicitly stated assumptions (MLSI, RS-AT, AT-fixed-pt) and on the prior local-stationarity transfer lemma Lemma 4.8 from [LMR+24]. None of these assumptions defines the conclusion: OPT is not fitted to Glauber data, the recursion is not obtained from the theorem it is used to prove, and the AT/MLSI conditions are crisply identified as conjectural or imported rather than silently assumed. The self-citation of [LMR+24] is load-bearing for the Glauber-to-RGD transfer, but it is a general lemma about measure decompositions and not a restatement of the spiked-Wigner correlation result; overlapping authorship alone does not make the derivation circular. The paper is transparent about the unproven mixing conditions, and the RGD/AMP fixed-point analysis stands independently of those conditions.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The central claims rely on SK mixing/overlap conditions from prior literature and one known Gaussian identity. No free parameters are fitted to data, and RGD is an auxiliary Markov chain defined in prior work, not a new physical entity.

assumptions (3)

domain assumption Condition 1 (MLSI): for β<1 and all h, the SK Glauber dynamics satisfies a modified log-Sobolev inequality with constant Ω(1/N).
Used in Theorem 5.2 to transfer local stationarity from Glauber to RGD via Lemma 4.8. Proven only for β<0.295; conjectured for all β<1.
domain assumption Condition 2 (RS-AT): above the AT line, the SK model satisfies exponential overlap concentration; for β<1 this follows from known results cited in Remark 4.15.
Needed to concentrate the magnetization and justify the scalar recursion for RGD. The paper relies on Talagrand's theorem and subsequent refinements for β<1.
standard math Lemma 7.6 requires the identity E[tanh^{2k}(γ+g√γ)] = E[tanh^{2k-1}(γ+g√γ)] from DAM16 to show AT-fixed-pt at β=λ.
This is a known Gaussian identity imported from the AMP literature; it is used to prove that the posterior temperature fixed point lies in the AT region.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Markov Chains Approximate Message Passing." pith.science (2026). https://pith.science/paper/3SISVXRE

@misc{pith2026251202384,
  author       = {Pith},
  title        = {Pith review of: Markov Chains Approximate Message Passing},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/3SISVXRE}},
  note         = {Machine review of arXiv:2512.02384}
}

read the original abstract

Markov chain Monte Carlo algorithms have long been observed to obtain near-optimal performance in various Bayesian inference settings. However, developing a supporting theory that makes these studies rigorous has proved challenging. In this paper, we study the classical spiked Wigner inference problem, where one aims to recover a planted Boolean spike from a noisy matrix measurement. We relate the recovery performance of Glauber dynamics on the annealed posterior to the performance of Approximate Message Passing (AMP), which is known to achieve Bayes-optimal performance. Our main results rely on the analysis of an auxiliary Markov chain called restricted Gaussian dynamics (RGD). Concretely, we establish the following results: 1. RGD can be reduced to an effective one-dimensional recursion which mirrors the evolution of the AMP iterates. 2. From a warm start, RGD rapidly converges to a fixed point in correlation space, which recovers Bayes-optimal performance when run on the posterior. 3. Conditioned on widely believed mixing results for the SK model, we recover the phase transition for non-trivial inference.

Figures

Figures reproduced from arXiv: 2512.02384 by the authors.

**Figure 2.** Behavior of the RGD recursion for different values of [PITH_FULL_IMAGE:figures/full_fig_p014_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

5 extracted references · 5 linked inside Pith

[1978]

Sequential dynamics in ising spin glasses.arXiv preprint arXiv:2506.09877, 2025

9 [DGPZ25] Yatin Dandi, David Gamarnik, Francisco Pernice, and Lenka Zdeborov´a. Sequential dynamics in ising spin glasses.arXiv preprint arXiv:2506.09877, 2025. 6, 13 [DKMZ11] Aurelien Decelle, Florent Krzakala, Cristopher Moore, and Lenka Zdeborov´a. Asymp- totic analysis of the stochastic block model for modular networks and its algorithmic application...

arXiv 2025
[2018]

The threshold energy of low temperature langevin dynamics for pure spherical spin glasses.Communications on Pure and Applied Mathematics, 77(11):4065– 4099, 2024

6 [Sel24] Mark Sellke. The threshold energy of low temperature langevin dynamics for pure spherical spin glasses.Communications on Pure and Applied Mathematics, 77(11):4065– 4099, 2024. 6, 13 [STL20] Ruoqi Shen, Kevin Tian, and Yin Tat Lee. Composite Logconcave Sampling with a Restricted Gaussian Oracle.arXiv preprint arXiv:2006.05976, 2020. 2 [Str57] RL ...

arXiv 2024
[2021]

A non-asymptotic framework for approximate message passing in spiked models.arXiv preprint arXiv:2208.03313, 2022

2 [LW22] Gen Li and Yuting Wei. A non-asymptotic framework for approximate message passing in spiked models.arXiv preprint arXiv:2208.03313, 2022. 6 [Mio17] L´eo Miolane. Fundamental limits of low-rank matrix estimation: the non-symmetric case.arXiv preprint arXiv:1702.00473, 2017. 6 [MPV87] Marc M´ezard, Giorgio Parisi, and Miguel Angel Virasoro.Spin gla...

arXiv 2022
[2022]

A spectral condition for spectral gap: fast mixing in high-temperature Ising models.Probability theory and related fields, 182(3):1035–1051, 2022

1 [EKZ22] Ronen Eldan, Frederic Koehler, and Ofer Zeitouni. A spectral condition for spectral gap: fast mixing in high-temperature Ising models.Probability theory and related fields, 182(3):1035–1051, 2022. 3 [Gue01] Francesco Guerra. Sum rules for the free energy in the mean field spin glass.Math- ematical Physics in Mathematics and Physics: Quantum and ...

arXiv 2022
[2025]

Cugliandolo-Kurchan equations for dynamics of spin-glasses.Probability theory and related fields, 136(4):619–660, 2006

7, 15 [BDG06] G´erard Ben Arous, Amir Dembo, and Alice Guionnet. Cugliandolo-Kurchan equations for dynamics of spin-glasses.Probability theory and related fields, 136(4):619–660, 2006. 6 [BDH16] Anton Bovier and Frank Den Hollander.Metastability: a potential-theoretic approach, volume 351. Springer, 2016. 6 [BGJ20] Gerard Ben Arous, Reza Gheissari, and Au...

arXiv 2006

Pith tools

Reviewed August 3, 2026 · model on record in the stance chip above.

[1] [1978]

Sequential dynamics in ising spin glasses.arXiv preprint arXiv:2506.09877, 2025

9 [DGPZ25] Yatin Dandi, David Gamarnik, Francisco Pernice, and Lenka Zdeborov´a. Sequential dynamics in ising spin glasses.arXiv preprint arXiv:2506.09877, 2025. 6, 13 [DKMZ11] Aurelien Decelle, Florent Krzakala, Cristopher Moore, and Lenka Zdeborov´a. Asymp- totic analysis of the stochastic block model for modular networks and its algorithmic application...

arXiv 2025

[2] [2018]

The threshold energy of low temperature langevin dynamics for pure spherical spin glasses.Communications on Pure and Applied Mathematics, 77(11):4065– 4099, 2024

6 [Sel24] Mark Sellke. The threshold energy of low temperature langevin dynamics for pure spherical spin glasses.Communications on Pure and Applied Mathematics, 77(11):4065– 4099, 2024. 6, 13 [STL20] Ruoqi Shen, Kevin Tian, and Yin Tat Lee. Composite Logconcave Sampling with a Restricted Gaussian Oracle.arXiv preprint arXiv:2006.05976, 2020. 2 [Str57] RL ...

arXiv 2024

[3] [2021]

A non-asymptotic framework for approximate message passing in spiked models.arXiv preprint arXiv:2208.03313, 2022

2 [LW22] Gen Li and Yuting Wei. A non-asymptotic framework for approximate message passing in spiked models.arXiv preprint arXiv:2208.03313, 2022. 6 [Mio17] L´eo Miolane. Fundamental limits of low-rank matrix estimation: the non-symmetric case.arXiv preprint arXiv:1702.00473, 2017. 6 [MPV87] Marc M´ezard, Giorgio Parisi, and Miguel Angel Virasoro.Spin gla...

arXiv 2022

[4] [2022]

A spectral condition for spectral gap: fast mixing in high-temperature Ising models.Probability theory and related fields, 182(3):1035–1051, 2022

1 [EKZ22] Ronen Eldan, Frederic Koehler, and Ofer Zeitouni. A spectral condition for spectral gap: fast mixing in high-temperature Ising models.Probability theory and related fields, 182(3):1035–1051, 2022. 3 [Gue01] Francesco Guerra. Sum rules for the free energy in the mean field spin glass.Math- ematical Physics in Mathematics and Physics: Quantum and ...

arXiv 2022

[5] [2025]

Cugliandolo-Kurchan equations for dynamics of spin-glasses.Probability theory and related fields, 136(4):619–660, 2006

7, 15 [BDG06] G´erard Ben Arous, Amir Dembo, and Alice Guionnet. Cugliandolo-Kurchan equations for dynamics of spin-glasses.Probability theory and related fields, 136(4):619–660, 2006. 6 [BDH16] Anton Bovier and Frank Den Hollander.Metastability: a potential-theoretic approach, volume 351. Springer, 2016. 6 [BGJ20] Gerard Ben Arous, Reza Gheissari, and Au...

arXiv 2006