arXiv research

Improves sampling, rounding, and integration of logconcave functions.

Unified complexity bound for sampling logconcave distributions

Faster algorithm for sampling logconcave densities in high dimensions.

New algorithms sample structured logconcave families with improved efficiency.

New method improves sampling from logconcave distributions truncated on polytopes.

Improved Metropolized HMC runtime for logconcave distributions.

Algorithm samples composite logconcave densities efficiently.

We study Hamiltonian Monte Carlo (HMC) for sampling from a strongly logconcave density proportional to $e^{-f}$ where $f:\mathbb{R}^d \to \mathbb{R}$ is $μ$-strongly convex and $L$-smooth (the condition number is $κ= L/μ$). We show that the relaxation time (inverse of the spectral gap) of ideal HMC is $O(κ)$, improving…

Polynomial-time algorithm learns high-dimensional halfspaces without labels.

Sampling logconcave functions arising in statistics and machine learning has been a subject of intensive study. Recent developments include analyses for Langevin dynamics and Hamiltonian Monte Carlo (HMC). While both approaches have dimension-independent bounds for the underlying $\mathit{continuous}$ processes under s…

We consider the problem of sampling from a target distribution, which is \emph {not necessarily logconcave}, in the context of empirical risk minimization and stochastic optimization as presented in Raginsky et al. (2017). Non-asymptotic analysis results are established in the $L^1$-Wasserstein distance for the behavio…

In this paper, we provide new insights on the Unadjusted Langevin Algorithm. We show that this method can be formulated as a first order optimization algorithm of an objective functional defined on the Wasserstein space of order $2$. Using this interpretation and techniques borrowed from convex optimization, we give a …

New Langevin algorithm works well even for rough distributions.

MALA mixes efficiently under smoothness and isoperimetry assumptions.

We study the problem of sampling from a probability distribution $π$ on $\rset^d$ which has a density \wrt\ the Lebesgue measure known up to a normalization factor $x \mapsto \rme^{-U(x)} / \int_{\rset^d} \rme^{-U(y)} \rmd y$. We analyze a sampling method based on the Euler discretization of the Langevin stochastic dif…

Paper tackles sampling from non-log-concave distributions using denoising diffusion.

New schemes improve error estimates for sampling from non-log-concave distributions.

The Langevin Markov chain algorithms are widely deployed methods to sample from distributions in challenging high-dimensional and non-convex statistics and machine learning applications. Despite this, current bounds for the Langevin algorithms are slower than those of competing algorithms in many important situations, …