An official website of the United States government
We propose a sampling method based on an ensemble approximation of second order Langevin dynamics. The log target density is appended with a quadratic term in an auxiliary momentum variable and damped-driven Hamiltonian dynamics introduced; the resulting stochastic differential equation is invariant to the Gibbs measure, with marginal on the position coordinates given by the target. A preconditioner based on covariance under the law of position coordinates under the dynamics does not change this invariance property, and is introduced to accelerate convergence to the Gibbs measure. The resulting mean-field dynamics may be approximated by an ensemble method; this results in a gradient-free and affine-invariant stochastic dynamical system with desirable provably uniform convergence properties across the class of all Gaussian targets. Numerical results demonstrate the potential of the method as the basis for a numerical sampler in Bayesian inverse problems, beyond the Gaussian setting.
more »
« less
Free Energy, Gibbs Measures, and Glauber Dynamics for Nearest-Neighbor Interactions
We extend results of Richard Holley beyond the integer lattice to a large class of countable groups which includes free groups and all amenable groups: for nearest-neighbor interactions on the Cayley graphs of such groups, we show that a shift-invariant measure is Gibbs if and only if it is Glauber-invariant. Moreover, any shift-invariant measure converges weakly to the set of Gibbs measures when evolved under the corresponding Glauber dynamics. These results are proven using a notion of free energy density relative to a sofic approximation by homomorphisms, which avoids the boundary problems which appear when applying a standard free energy method in a nonamenable setting. We also show that any measure which minimizes this free energy density is Gibbs.
more »
« less
- Award ID(s):
- 1855694
- PAR ID:
- 10398485
- Date Published:
- Journal Name:
- Communications in Mathematical Physics
- ISSN:
- 0010-3616
- Page Range / eLocation ID:
- 1 - 24
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract Recent work of Barbieri and Meyerovitch has shown that, for very general spin systems indexed by sofic groups, equilibrium (i.e. pressure-maximizing) states are Gibbs. The main goal of this paper is to show that the converse fails in an interesting way: for the Ising model on a free group, the free-boundary state typically fails to be equilibrium as long as it is not theonlyGibbs state. For every temperature between the uniqueness and reconstruction thresholds a typical sofic approximation gives this state finite but non-maximal pressure, and for every lower temperature the pressure is non-maximal overeverysofic approximation. We also show that, for more general interactions on sofic groups, the local on average limit of Gibbs states over a sofic approximation Σ, if it exists, is a mixture of Σ-equilibrium states. We use this to show that the plus- and minus-boundary-condition Ising states are Σ-equilibrium if Σ is any sofic approximation to a free group. Combined with a result of Dembo and Montanari, this implies that these states have the same entropy over every sofic approximation.more » « less
-
Bessani, Alysson; Défago, Xavier; Nakamura, Junya; Wada, Koichi; Yamauchi, Yukiko (Ed.)Markov Chain Monte Carlo (MCMC) algorithms are a widely-used algorithmic tool for sampling from high-dimensional distributions, a notable example is the equilibirum distribution of graphical models. The Glauber dynamics, also known as the Gibbs sampler, is the simplest example of an MCMC algorithm; the transitions of the chain update the configuration at a randomly chosen coordinate at each step. Several works have studied distributed versions of the Glauber dynamics and we extend these efforts to a more general family of Markov chains. An important combinatorial problem in the study of MCMC algorithms is random colorings. Given a graph G of maximum degree Δ and an integer k ≥ Δ+1, the goal is to generate a random proper vertex k-coloring of G. Jerrum (1995) proved that the Glauber dynamics has O(nlog{n}) mixing time when k > 2Δ. Fischer and Ghaffari (2018), and independently Feng, Hayes, and Yin (2018), presented a parallel and distributed version of the Glauber dynamics which converges in O(log{n}) rounds for k > (2+ε)Δ for any ε > 0. We improve this result to k > (11/6-δ)Δ for a fixed δ > 0. This matches the state of the art for randomly sampling colorings of general graphs in the sequential setting. Whereas previous works focused on distributed variants of the Glauber dynamics, our work presents a parallel and distributed version of the more general flip dynamics presented by Vigoda (2000) (and refined by Chen, Delcourt, Moitra, Perarnau, and Postle (2019)), which recolors local maximal two-colored components in each step.more » « less
-
Abstract We consider the discrete defocusing nonlinear Schrödinger equation in its integrable version, which is called defocusing Ablowitz–Ladik lattice. We consider periodic boundary conditions with period N and initial data sampled according to the Generalized Gibbs ensemble. In this setting, the Lax matrix of the Ablowitz–Ladik lattice is a random CMV-periodic matrix and it is related to the Killip-Nenciu Circular $$\beta $$ β -ensemble at high-temperature. We obtain the generalized free energy of the Ablowitz–Ladik lattice and the density of states of the random Lax matrix by establishing a mapping to the one-dimensional log-gas. For the Gibbs measure related to the Hamiltonian of the Ablowitz–Ladik flow, we obtain the density of states via a particular solution of the double-confluent Heun equation.more » « less
-
For general spin systems, we prove that a contractive coupling for an arbitrary local Markov chain implies optimal bounds on the mixing time and the modified log-Sobolev constant for a large class of Markov chains including the Glauber dynamics, arbitrary heat-bath block dynamics, and the Swendsen-Wang dynamics. This reveals a novel connection between probabilistic techniques for bounding the convergence to stationarity and analytic tools for analyzing the decay of relative entropy. As a corollary of our general results, we obtain O(n log n) mixing time and Ω(1/n) modified log-Sobolev constant of the Glauber dynamics for sampling random q-colorings of an n-vertex graph with constant maximum degree Δ when q > (11/6–∊0)Δ for some fixed ∊0 > 0. We also obtain O(log n) mixing time and Ω(1) modified log-Sobolev constant of the Swendsen-Wang dynamics for the ferromagnetic Ising model on an n-vertex graph of constant maximum degree when the parameters of the system lie in the tree uniqueness region. At the heart of our results are new techniques for establishing spectral independence of the spin system and block factorization of the relative entropy. On one hand we prove that a contractive coupling of any local Markov chain implies spectral independence of the Gibbs distribution. On the other hand we show that spectral independence implies factorization of entropy for arbitrary blocks, establishing optimal bounds on the modified log-Sobolev constant of the corresponding block dynamics.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1007/s00220-022-04537-0
