Convergence of the Riemannian Langevin Algorithm
- URL: http://arxiv.org/abs/2204.10818v1
- Date: Fri, 22 Apr 2022 16:56:00 GMT
- Title: Convergence of the Riemannian Langevin Algorithm
- Authors: Khashayar Gatmiry and Santosh S. Vempala
- Abstract summary: We study the problem of sampling from a distribution with density $nu$ with respect to the natural measure on a manifold with metric $g$.
A special case of our approach is sampling isoperimetric densities restricted to polytopes defined by the logarithmic barrier.
- Score: 10.279748604797911
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the Riemannian Langevin Algorithm for the problem of sampling from a
distribution with density $\nu$ with respect to the natural measure on a
manifold with metric $g$. We assume that the target density satisfies a
log-Sobolev inequality with respect to the metric and prove that the manifold
generalization of the Unadjusted Langevin Algorithm converges rapidly to $\nu$
for Hessian manifolds. This allows us to reduce the problem of sampling
non-smooth (constrained) densities in ${\bf R}^n$ to sampling smooth densities
over appropriate manifolds, while needing access only to the gradient of the
log-density, and this, in turn, to sampling from the natural Brownian motion on
the manifold. Our main analytic tools are (1) an extension of self-concordance
to manifolds, and (2) a stochastic approach to bounding smoothness on
manifolds. A special case of our approach is sampling isoperimetric densities
restricted to polytopes by using the metric defined by the logarithmic barrier.
Related papers
- Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
Recent studies show that a reproducing kernel Hilbert space (RKHS) is not a suitable space to model functions by neural networks.
In this paper, we study a suitable function space for over- parameterized two-layer neural networks with bounded norms.
arXiv Detail & Related papers (2024-04-29T15:04:07Z) - Sampling and estimation on manifolds using the Langevin diffusion [45.57801520690309]
Two estimators of linear functionals of $mu_phi $ based on the discretized Markov process are considered.
Error bounds are derived for sampling and estimation using a discretization of an intrinsically defined Langevin diffusion.
arXiv Detail & Related papers (2023-12-22T18:01:11Z) - Symmetric Mean-field Langevin Dynamics for Distributional Minimax
Problems [78.96969465641024]
We extend mean-field Langevin dynamics to minimax optimization over probability distributions for the first time with symmetric and provably convergent updates.
We also study time and particle discretization regimes and prove a new uniform-in-time propagation of chaos result.
arXiv Detail & Related papers (2023-12-02T13:01:29Z) - Curvature-Independent Last-Iterate Convergence for Games on Riemannian
Manifolds [77.4346324549323]
We show that a step size agnostic to the curvature of the manifold achieves a curvature-independent and linear last-iterate convergence rate.
To the best of our knowledge, the possibility of curvature-independent rates and/or last-iterate convergence has not been considered before.
arXiv Detail & Related papers (2023-06-29T01:20:44Z) - Resolving the Mixing Time of the Langevin Algorithm to its Stationary
Distribution for Log-Concave Sampling [34.66940399825547]
This paper characterizes the mixing time of the Langevin Algorithm to its stationary distribution.
We introduce a technique from the differential privacy literature to the sampling literature.
arXiv Detail & Related papers (2022-10-16T05:11:16Z) - Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and
Beyond [63.59034509960994]
We study shuffling-based variants: minibatch and local Random Reshuffling, which draw gradients without replacement.
For smooth functions satisfying the Polyak-Lojasiewicz condition, we obtain convergence bounds which show that these shuffling-based variants converge faster than their with-replacement counterparts.
We propose an algorithmic modification called synchronized shuffling that leads to convergence rates faster than our lower bounds in near-homogeneous settings.
arXiv Detail & Related papers (2021-10-20T02:25:25Z) - Mean-Square Analysis with An Application to Optimal Dimension Dependence
of Langevin Monte Carlo [60.785586069299356]
This work provides a general framework for the non-asymotic analysis of sampling error in 2-Wasserstein distance.
Our theoretical analysis is further validated by numerical experiments.
arXiv Detail & Related papers (2021-09-08T18:00:05Z) - Intrinsic persistent homology via density-based metric learning [1.0499611180329804]
We prove that the metric space defined by the sample endowed with a computable metric known as sample Fermat distance converges a.s.
The limiting object is the manifold itself endowed with the population Fermat distance, an intrinsic metric that accounts for both the geometry of the manifold and the density that produces the sample.
arXiv Detail & Related papers (2020-12-11T18:54:36Z) - Wasserstein Control of Mirror Langevin Monte Carlo [2.7145834528620236]
Discretized Langevin diffusions are efficient Monte Carlo methods for sampling from high dimensional target densities.
We consider Langevin diffusions on a Hessian-type manifold and study a discretization that is closely related to the mirror-descent scheme.
arXiv Detail & Related papers (2020-02-11T13:16:31Z) - Oracle Lower Bounds for Stochastic Gradient Sampling Algorithms [39.746670539407084]
We consider the problem of sampling from a strongly log-concave density in $bbRd$.
We prove an information theoretic lower bound on the number of gradient queries of the log density needed.
arXiv Detail & Related papers (2020-02-01T23:46:35Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.