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 three results. First, RGD can be reduced to an effective one-dimensional recursion which mirrors the evolution of the AMP iterates. Second, from a warm start, RGD rapidly converges to a fixed point in correlation space, which recovers Bayes-optimal performance when run on the posterior. Third, conditioned on widely believed mixing results for the SK model, we recover the phase transition for non-trivial inference. The full version of this paper can be found on arXiv (arXiv ID: 2512.02384).

Given an arbitrary subgraph $H=H_n$ and $p=p_n\in(0,1)$, the planted subgraph model is defined as follows. A statistician observes the union of the "signal," which is a random "planted" copy $H^*$ of $H$, together with random "noise" in the form of an instance of an Erd{ö}s-R{é}nyi graph $G(n,p)$. The goal then of the statistician is to recover the planted $H^*$ from the observed graph. Our focus in this work is to understand the minimum mean-squared error (MMSE) in terms of recovering the edges of $H^*$, as a function of $p$ and $H$. A recent paper [MNSSZ23] characterizes the graphs for which this MMSE curve undergoes a sharp phase transition from $0$ to $1$ as $p$ increases, a behavior known as the All-or-Nothing phenomenon, up to a mild density assumption on $H$. However, their techniques fail to describe the MMSE curves for graphs that do not display such a sharp phase transition. In this paper, we provide a formula for the limiting MMSE curve for any graph $H=H_n$, up to the same mild density assumption. This curve is expressed in terms of a variational formula over pairs of subgraphs of $H$, and is inspired by the celebrated subgraph expectation thresholds from probabilistic combinatorics [KK07]. Furthermore, we give a polynomial-time description of the optimizers of this variational problem. This allows one to efficiently compute the MMSE curve for any given dense graph $H$. The proof relies on a novel graph decomposition as well as a min-max duality theorem which may be of independent interest. Our results generalize to the setting of planting arbitrary monotone boolean properties, where the statistician observes the union of a planted minimal element $A\subseteq[N]$ of a monotone property and a random $\mathrm{Ber}(p)^{\otimes N}$ vector. In this setting, we provide a variational formula inspired by the so-called "fractional" expectation threshold [Tal10], again describing the MMSE curve (in this case up to a multiplicative constant).

Many natural Markov chains fail to mix to their stationary distribution in polynomially many steps. Often, this slow mixing is inevitable since it is computationally intractable to sample from their stationary measure. Nevertheless, Markov chains can be shown to always converge quickly to measures that are locally stationary, i.e., measures that don't change over a small number of steps. These locally stationary measures are analogous to local minima in continuous optimization, while stationary measures correspond to global minima. While locally stationary measures can be statistically far from stationary measures, do they enjoy provable theoretical guarantees that have algorithmic implications? We study this question in this work and demonstrate three algorithmic applications of locally stationary measures: 1)We show that Glauber dynamics on the hardcore model can be used to find large independent sets in triangle-free graphs of bounded degree. 2)We prove that Glauber dynamics on the Ising model defined by a spiked matrix model finds a vector with constant correlation with the planted spike. 3)We show that for sufficiently large constant signal-to-noise ratio, Glauber dynamics on the Ising model finds a vector that has constant correlation with the hidden community vector. In other words, Glauber dynamics subsumes the spectral method for spiked Wigner and community detection, by weakly recovering the planted spike. The full version of this paper can be found on arXiv(arXiv ID: 2405.20849).

Motivated by the community detection problem in Bayesian inference, as well as the recent explosion of interest in spin glasses from statistical physics, we study the classical Glauber dynamics for sampling from Ising models with sparse random interactions. It is now well-known that when the in- teraction matrix has spectral diameter less than 1, Glauber dynamics mixes in near-linear time. Unfortunately, such criteria fail dramatically for interactions supported on arguably the most well-studied sparse random graph: the Erdos-Renyi random graph. There is a scarcity of positive results in this setting due to the presence of almost linearly many outlier eigenvalues of unbounded magnitude. We prove that for the Viana-Bray spin glass, where the interactions are supported on a random graph and randomly assigned signs, Glauber dynamics mixes in almost-linear time with high probability at sufficiently high temperatures, and we conjecture that our results are tight up to constants. We further extend our results to random graphs drawn according to the 2-community stochastic block model, as well as when the interactions are given by a “centered” version of the adjacency matrix. The latter setting is particularly relevant for the inference problem in community detection. Indeed, we build on this result to demonstrate that Glauber dynamics succeeds at recovering communities in the stochastic block model in a companion paper. The primary technical ingredient in our proof is showing that with high probability, a sparse random graph can be decomposed into two parts - a bulk which behaves like a graph with bounded maximum degree and a well-behaved spectrum, and a near- forest with favorable pseudorandom properties. We then use this decomposition to design a localization procedure that interpolates to simpler Ising models supported only on the near-forest, and then execute a pathwise analysis to establish a modified log- Sobolev inequality. The full version of this paper can be found on arXiv (arXiv ID: 2405.06616).

Running a random walk in a convex body K⊆ℝn is a standard approach to sample approximately uniformly from the body. The requirement is that from a suitable initial distribution, the distribution of the walk comes close to the uniform distribution πK on K after a number of steps polynomial in n and the aspect ratio R/r (i.e., when rB2 ⊆ K ⊆ RB2). Proofs of rapid mixing of such walks often require the probability density η0 of the initial distribution with respect to πK to be at most poly(n): this is called a “warm start”. Achieving a warm start often requires non-trivial pre-processing before starting the random walk. This motivates proving rapid mixing from a “cold start”, wherein η0 can be as high as exp(poly(n)). Unlike warm starts, a cold start is usually trivial to achieve. However, a random walk need not mix rapidly from a cold start: an example being the well-known “ball walk”. On the other hand, Lovász and Vempala proved that the “hit-and-run” random walk mixes rapidly from a cold start. For the related coordinate hit-and-run (CHR) walk, which has been found to be promising in computational experiments, rapid mixing from a warm start was proved only recently but the question of rapid mixing from a cold start remained open.