Polynomial- or near-linear-time posterior sampling by annealed Glauber dynamics

From papers

Consider the spiked Wigner inference problem with signal-to-noise parameter β\bM\beta_{\bM} and threshold β\bM\beta_{\bM} as used in the paper. Let β\bM\beta_{\bM} denote the scaled posterior parameter, and let βλ\beta_{\lambda} be the threshold appearing in the paper's high-temperature analysis. Annealed Glauber sampling conjecture. For ββλ\beta \le \beta_{\lambda}, annealed Glauber dynamics samples from the scaled posterior μβ\bM\mu_{\beta \bM} in \poly(N)\poly(N), or even O(NlogN)O(N\log N) time. Establishing this would provide a sampling guarantee complementary to the conjectured near-linear-time weak-recovery result; the source describes weak Poincare inequalities and one-dimensional RGD as possible routes, and the conjecture remains open.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Amit Rajaraman and David X. Wu, “Markov Chains Approximate Message Passing”, arXiv:2512.02384 (2026).

Solutions 0

No solutions have been posted yet.