Optimal Mixing Time for Log-Concave Sampling
§ Problem Statement
Setup
Unsolved Problem
§ Discussion
§ Significance & Implications
§ Known Partial Results
§ References
Optimal convergence rate of the proximal point algorithm for strongly log-concave distributions
Yongxin Chen, Sinho Chewi, Adil Salim, Andre Wibisono (2022)
Annals of Applied Probability
📍 Section 4.2 (Applications of the convergence results), item 2 in the numbered comparison list (“it is currently not known how to perform a discretization analysis … with linear dependence on $\kappa$ under $\alpha$-LSI or $\alpha$-PI”), p. 8
Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Suffices
Santosh Vempala, Andre Wibisono (2019)
Underdamped Langevin MCMC: A non-asymptotic analysis
Xiang Cheng, Niladri S. Chatterji, Peter L. Bartlett, Michael I. Jordan (2018)
A random polynomial-time algorithm for approximating the volume of convex bodies
Martin Dyer, Alan Frieze, Ravi Kannan (1991)
Journal of the ACM
📍 Section 3 (Random walks on convex bodies), Theorem 3.1 (rapid mixing of the ball walk via conductance), pp. 8–10.
Theoretical guarantees for approximate sampling from smooth and log-concave density
Arnak S. Dalalyan (2017)
Journal of the Royal Statistical Society Series B
📍 Section 3 (Main results), Theorem 1 (non-asymptotic convergence bound for unadjusted Langevin algorithm in TV distance), p. 658.