# On Mixing Times of Metropolized Algorithm With Optimization Step (MAO) : A New Framework

arXiv: https://arxiv.org/abs/2112.00565 · HTML: https://mlsanity.com/paper/2112.00565/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 26 references that are in the map.
- First posted on arXiv 1 Dec 2021.

## Builds on (most cited first, 9 of 9)

- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Theoretical guarantees for approximate sampling from smooth and log-concave densities](https://mlsanity.com/paper/1412.7392/) (2014)
- [Log-concave sampling: Metropolis-Hastings algorithms are fast](https://mlsanity.com/paper/1801.02309/) (2018)
- [Relatively-Smooth Convex Optimization by First-Order Methods, and Applications](https://mlsanity.com/paper/1610.05708/) (2016)
- [Convergence of Langevin MCMC in KL-divergence](https://mlsanity.com/paper/1705.09048/) (2017)
- [Sampling Can Be Faster Than Optimization](https://mlsanity.com/paper/1811.08413/) (2018)
- [Optimal dimension dependence of the Metropolis-Adjusted Langevin Algorithm](https://mlsanity.com/paper/2012.12810/) (2020)
- [Fast mixing of Metropolized Hamiltonian Monte Carlo: Benefits of multi-step gradients](https://mlsanity.com/paper/1905.12247/) (2019)
- [Dual Space Preconditioning for Gradient Descent](https://mlsanity.com/paper/1902.02257/) (2019)

## Abstract (arXiv)

In this paper, we consider sampling from a class of distributions with thin tails supported on ℝd and make two primary contributions. First, we propose a new Metropolized Algorithm With Optimization Step (MAO), which is well suited for such targets. Our algorithm is capable of sampling from distributions where the Metropolis-adjusted Langevin algorithm (MALA) is not converging or lacking in theoretical guarantees. Second, we derive upper bounds on the mixing time of MAO. Our results are supported by simulations on multiple target distributions.