High-accuracy sampling from constrained spaces with the Metropolis-adjusted Preconditioned Langevin Algorithm

Vishwak Srinivasan, Andre Wibisono, Ashia Wilson
Proceedings of The 36th International Conference on Algorithmic Learning Theory, PMLR 272:1169-1220, 2025.

Abstract

We propose a first-order sampling method called the Metropolis-adjusted Preconditioned Langevin Algorithm for approximate sampling from a target distribution whose support is a proper convex subset of Rd. Our proposed method is the result of applying a Metropolis-Hastings filter to the Markov chain formed by a single step of the preconditioned Langevin algorithm with a metric G, and is motivated by the natural gradient descent algorithm for optimisation. We derive non-asymptotic upper bounds for the mixing time of this method for sampling from target distributions whose potentials are bounded relative to G, and for exponential distributions restricted to the support. Our analysis suggests that if G satisfies stronger notions of self-concordance introduced in \citet{kook2024gaussian}, then these mixing time upper bounds have a strictly better dependence on the dimension than when G is merely self-concordant. Our method is a high-accuracy sampler due to the polylogarithmic dependence on the error tolerance in our mixing time upper bounds.

Cite this Paper

BibTeX
@InProceedings{pmlr-v272-srinivasan25a, title = {High-accuracy sampling from constrained spaces with the Metropolis-adjusted Preconditioned Langevin Algorithm}, author = {Srinivasan, Vishwak and Wibisono, Andre and Wilson, Ashia}, booktitle = {Proceedings of The 36th International Conference on Algorithmic Learning Theory}, pages = {1169--1220}, year = {2025}, editor = {Kamath, Gautam and Loh, Po-Ling}, volume = {272}, series = {Proceedings of Machine Learning Research}, month = {24--27 Feb}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v272/main/assets/srinivasan25a/srinivasan25a.pdf}, url = {https://proceedings.mlr.press/v272/srinivasan25a.html}, abstract = {We propose a first-order sampling method called the Metropolis-adjusted Preconditioned Langevin Algorithm for approximate sampling from a target distribution whose support is a proper convex subset of $\mathbb{R}^{d}$. Our proposed method is the result of applying a Metropolis-Hastings filter to the Markov chain formed by a single step of the preconditioned Langevin algorithm with a metric $\mathscr{G}$, and is motivated by the natural gradient descent algorithm for optimisation. We derive non-asymptotic upper bounds for the mixing time of this method for sampling from target distributions whose potentials are bounded relative to $\mathscr{G}$, and for exponential distributions restricted to the support. Our analysis suggests that if $\mathscr{G}$ satisfies stronger notions of self-concordance introduced in \citet{kook2024gaussian}, then these mixing time upper bounds have a strictly better dependence on the dimension than when $\mathscr{G}$ is merely self-concordant. Our method is a high-accuracy sampler due to the polylogarithmic dependence on the error tolerance in our mixing time upper bounds. } }
Endnote
%0 Conference Paper %T High-accuracy sampling from constrained spaces with the Metropolis-adjusted Preconditioned Langevin Algorithm %A Vishwak Srinivasan %A Andre Wibisono %A Ashia Wilson %B Proceedings of The 36th International Conference on Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2025 %E Gautam Kamath %E Po-Ling Loh %F pmlr-v272-srinivasan25a %I PMLR %P 1169--1220 %U https://proceedings.mlr.press/v272/srinivasan25a.html %V 272 %X We propose a first-order sampling method called the Metropolis-adjusted Preconditioned Langevin Algorithm for approximate sampling from a target distribution whose support is a proper convex subset of $\mathbb{R}^{d}$. Our proposed method is the result of applying a Metropolis-Hastings filter to the Markov chain formed by a single step of the preconditioned Langevin algorithm with a metric $\mathscr{G}$, and is motivated by the natural gradient descent algorithm for optimisation. We derive non-asymptotic upper bounds for the mixing time of this method for sampling from target distributions whose potentials are bounded relative to $\mathscr{G}$, and for exponential distributions restricted to the support. Our analysis suggests that if $\mathscr{G}$ satisfies stronger notions of self-concordance introduced in \citet{kook2024gaussian}, then these mixing time upper bounds have a strictly better dependence on the dimension than when $\mathscr{G}$ is merely self-concordant. Our method is a high-accuracy sampler due to the polylogarithmic dependence on the error tolerance in our mixing time upper bounds.
APA
Srinivasan, V., Wibisono, A. & Wilson, A.. (2025). High-accuracy sampling from constrained spaces with the Metropolis-adjusted Preconditioned Langevin Algorithm. Proceedings of The 36th International Conference on Algorithmic Learning Theory, in Proceedings of Machine Learning Research 272:1169-1220 Available from https://proceedings.mlr.press/v272/srinivasan25a.html.

Related Material