arXiv research

NUTS mixing time scales as d^(1/4) for Gaussian distributions.

We prove that the ordinary least-squares (OLS) estimator attains nearly minimax optimal performance for the identification of linear dynamical systems from a single observed trajectory. Our upper bound relies on a generalization of Mendelson's small-ball method to dependent data, eschewing the use of standard mixing-ti…

New method learns nonlinear systems from single finite trajectory samples.

New method adapts to unknown mixing time in stochastic optimization.

Lower bound on BART's mixing time increases with data points.

The study examines mixing times of data-augmentation Gibbs samplers for high-dimensional probit regression.

MALA mixes optimally in κ√d steps for log-concave sampling.

New algorithm for sampling from distributions with thin tails.

This paper compares two NUTS variants and analyzes their convergence and mixing times.

uHMC achieves fast mixing in high dimensions with gradient evaluations.

New bounds for mixing time and privacy in projected Langevin algorithm and noisy SGD.

The paper develops new inequalities for Markov chain sums, linking them to mixing time.

The paper analyzes convergence rates of Langevin dynamics and Proximal Sampler using $Φ$-divergence.

We derive and analyze learning algorithms for apprenticeship learning, policy evaluation, and policy gradient for average reward criteria. Existing algorithms explicitly require an upper bound on the mixing time. In contrast, we build on ideas from Markov chain theory and derive sampling algorithms that do not require …

This work analyzes Gibbs samplers for Bayesian hierarchical models without dimensionality constraints.

We give a simple optimistic algorithm for which it is easy to derive regret bounds of $\tilde{O}(\sqrt{t_{\rm mix} SAT})$ after $T$ steps in uniformly ergodic Markov decision processes with $S$ states, $A$ actions, and mixing time parameter $t_{\rm mix}$. These bounds are the first regret bounds in the general, non-epi…

We address the problem of estimating the mixing time of a Markov chain from a single trajectory of observations. Unlike most previous works which employed Hilbert space methods to estimate spectral gaps, we opt for an approach based on contraction with respect to total variation. Specifically, we estimate the contracti…

Improved lower bound for parallel tempering's mixing time.

New RL method MAC improves performance in sparse reward settings.

MALA mixes efficiently under smoothness and isoperimetry assumptions.

TD(0) with Polyak-Ruppert averaging achieves robust and fast convergence rates

Hamiltonian Monte Carlo (HMC) is a state-of-the-art Markov chain Monte Carlo sampling algorithm for drawing samples from smooth probability densities over continuous spaces. We study the variant most widely used in practice, Metropolized HMC with the Störmer-Verlet or leapfrog integrator, and make two primary contribut…

We propose and analyze two new MCMC sampling algorithms, the Vaidya walk and the John walk, for generating samples from the uniform distribution over a polytope. Both random walks are sampling algorithms derived from interior point methods. The former is based on volumetric-logarithmic barrier introduced by Vaidya wher…

We analyze mixing times of three DA algorithms for regression models.

This paper resolves the Langevin Algorithm's mixing time for log-concave distributions.

MixML unifies analysis of weakly consistent parallel learning.

This article provides the first procedure for computing a fully data-dependent interval that traps the mixing time $t_{\text{mix}}$ of a finite reversible ergodic Markov chain at a prescribed confidence level. The interval is computed from a single finite-length sample path from the Markov chain, and does not require t…

New method improves sampling from logconcave distributions truncated on polytopes.

We introduce a novel multivariate random process producing Bernoulli outputs per dimension, that can possibly formalize binary interactions in various graphical structures and can be used to model opinion dynamics, epidemics, financial and biological time series data, etc. We call this a Bernoulli Autoregressive Proces…

Rapid mixing of Langevin dynamics on Riemannian manifolds

We consider the problem of sampling from a strongly log-concave density in $\mathbb{R}^d$, and prove a non-asymptotic upper bound on the mixing time of the Metropolis-adjusted Langevin algorithm (MALA). The method draws samples by simulating a Markov chain obtained from the discretization of an appropriate Langevin dif…

Non-negative curvature affects Markov chains' mixing and expansion properties.

New sampling method improves accuracy for constrained spaces.

Stochastic Gradient Langevin Dynamics (SGLD) is a sampling scheme for Bayesian modeling adapted to large datasets and models. SGLD relies on the injection of Gaussian Noise at each step of a Stochastic Gradient Descent (SGD) update. In this scheme, every component in the noise vector is independent and has the same sca…

Improved Metropolized HMC runtime for logconcave distributions.

Graph curvature measured by inverse resistance distance.

Study non-parametric value function estimation from a single path.

Gibbs sampling is a Markov Chain Monte Carlo sampling technique that iteratively samples variables from their conditional distributions. There are two common scan orders for the variables: random scan and systematic scan. Due to the benefits of locality in hardware, systematic scan is commonly used, even though most st…

Paper analyzes Nyström regularization for time series forecasting with sequential sub-sampling.

Paper analyzes Hit-and-Run's convergence rates and applies similar methods to randomized Kaczmarz.

Develops a functional generalization of Eldan's stochastic localization for optimization and privacy.

We study the problem of sampling from the power posterior distribution in Bayesian Gaussian mixture models, a robust version of the classical posterior. This power posterior is known to be non-log-concave and multi-modal, which leads to exponential mixing times for some standard MCMC algorithms. We introduce and study …

The spectral gap $γ$ of a finite, ergodic, and reversible Markov chain is an important parameter measuring the asymptotic rate of convergence. In applications, the transition matrix $P$ may be unknown, yet one sample of the chain up to a fixed time $n$ may be observed. We consider here the problem of estimating $γ$ fro…

New algorithm improves mixing in Bayesian mixture models.

We introduce a Markov chain for sampling from the uniform distribution on a Riemannian manifold $\mathcal{M}$, which we call the $\textit{geodesic walk}$. We prove that the mixing time of this walk on any manifold with positive sectional curvature $C_{x}(u,v)$ bounded both above and below by $0 < \mathfrak{m}_{2} \leq …

We study probability measures induced by set functions with constraints. Such measures arise in a variety of real-world settings, where prior knowledge, resource limitations, or other pragmatic considerations impose constraints. We consider the task of rapidly sampling from such constrained measures, and develop fast M…

We address the problem of estimating the mixing time $t_{\mathsf{mix}}$ of an arbitrary ergodic finite-state Markov chain from a single trajectory of length $m$. The reversible case was addressed by Hsu et al. [2019], who left the general case as an open problem. In the reversible case, the analysis is greatly facilita…

Polynomial mixing times for simulated tempering in mixture sampling problems.