{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T16:43:46Z","timestamp":1787330626327,"version":"build-2736575974"},"reference-count":94,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"name":"TwoSigma"},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1122374"],"award-info":[{"award-number":["1122374"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006732","name":"New York University","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100006732","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM Journal on Mathematics of Data Science"],"published-print":{"date-parts":[[2025,9,30]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>Sampling from a high-dimensional distribution is a fundamental task in statistics, engineering, and the sciences. A canonical approach is the Langevin algorithm, i.e., the Markov chain for the discretized Langevin diffusion. This is the sampling analog of gradient descent. Despite being studied for several decades in multiple communities, tight mixing bounds for this algorithm remain unresolved even in the seemingly simple setting of log-concave distributions over a bounded domain. This paper characterizes the mixing time of the Langevin algorithm to its stationary distribution in this setting (and others). This mixing result can be combined with any bound on the discretization bias in order to sample from the stationary distribution of the continuous Langevin diffusion. In this way, we disentangle the study of the mixing and bias of the Langevin algorithm. Our key insight is to introduce a technique from the differential privacy literature to the sampling literature. This technique, called privacy amplification by iteration, uses as a potential a variant of R\u00e9nyi divergence that is made geometrically aware via optimal transport smoothing. This gives a short, simple proof of optimal mixing bounds and has several additional appealing properties. First, our approach removes all unnecessary assumptions required by other sampling analyses. Second, our approach unifies many settings: it extends unchanged if the Langevin algorithm uses projections, stochastic minibatch gradients, or strongly convex potentials (whereby our mixing time improves exponentially). Third, our approach exploits convexity only through the contractivity of a gradient step\u2014reminiscent of how convexity is used in textbook proofs of gradient descent. In this way, we offer a new approach towards further unifying the analyses of optimization and sampling algorithms.<\/jats:p>","DOI":"10.1137\/24m1638689","type":"journal-article","created":{"date-parts":[[2025,7,9]],"date-time":"2025-07-09T12:00:32Z","timestamp":1752062432000},"page":"993-1020","source":"Crossref","is-referenced-by-count":2,"title":["Resolving the Mixing Time of the Langevin Algorithm to Its Stationary Distribution for Log-Concave Sampling"],"prefix":"10.1137","volume":"7","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7367-0097","authenticated-orcid":true,"given":"Jason M.","family":"Altschuler","sequence":"first","affiliation":[{"name":"Department of Statistics and Data Science, University of Pennsylvania, Philadelphia, PA, USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kunal","family":"Talwar","sequence":"additional","affiliation":[{"name":"Apple, One Apple Park Way, Cupertino, CA, USA."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2025,7,9]]},"reference":[{"key":"ref1","first-page":"28405","volume":"34","author":"Ahn K.","year":"2021","journal-title":"Advances in Neural Information Processing Systems"},{"key":"ref2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3653446","volume":"71","author":"Altschuler J. M.","year":"2024","journal-title":"J. ACM"},{"key":"ref3","doi-asserted-by":"crossref","first-page":"90","DOI":"10.1109\/TIT.2024.3475290","volume":"71","author":"Altschuler J. M.","year":"2025","journal-title":"IEEE Trans. Inform. Theory"},{"key":"ref4","unstructured":"J. M. Altschuler and K. Talwar, Concentration of the Langevin Algorithm\u2019s Stationary Distribution, preprint, arXiv:2212.12629, 2022."},{"key":"ref5","first-page":"3788","volume-title":"Advances in Neural Information Processing Systems","volume":"35","author":"Altschuler J. M.","year":"2022"},{"key":"ref6","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1023\/A:1020281327116","volume":"50","author":"Andrieu C.","year":"2003","journal-title":"Mach. Learn."},{"key":"ref7","doi-asserted-by":"crossref","unstructured":"S. Asoodeh, M. D\u00edaz, and F. du Pin Calmon, Privacy amplification of iterative algorithms via contraction coefficients, in 2020 IEEE International Symposium on Information Theory, IEEE, Piscataway, NJ, 2020, pp. 896\u2013901.","DOI":"10.1109\/ISIT44484.2020.9174133"},{"key":"ref8","unstructured":"K. Balasubramanian, S. Chewi, M. A. Erdogdu, A. Salim, and S. Zhang, Towards a theory of non-log-concave sampling: First-order stationarity guarantees for Langevin Monte Carlo, Proc. Mach. Learn. Res.\u00a0(PMLR), 178 (2022), pp. 2896\u20132923."},{"key":"ref9","volume-title":"Privacy Amplification by Mixing and Diffusion Mechanisms","author":"Balle B.","year":"2019"},{"key":"ref10","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1287\/moor.18.2.255","volume":"18","author":"B\u00e9lisle C. J.","year":"1993","journal-title":"Math. Oper. Res."},{"key":"ref11","unstructured":"E. Bernton, Langevin Monte Carlo and JKO splitting, Proc. Mach. Learn. Res. (PMLR), 75 (2018), pp. 1777\u20131798."},{"key":"ref12","doi-asserted-by":"crossref","first-page":"541","DOI":"10.1214\/aop\/1176995476","volume":"6","author":"Bhattacharya R.","year":"1978","journal-title":"Ann. Probab."},{"key":"ref13","series-title":"Inform. Sci. Statist. 4","volume-title":"Pattern Recognition and Machine Learning","author":"Bishop C. M.","year":"2006"},{"key":"ref14","unstructured":"N. Brosse, A. Durmus, \u00c9. Moulines, and M. Pereyra, Sampling from a log-concave distribution with compact support with proximal Langevin Monte Carlo, Proc. Mach. Learn. Res. (PMLR), 65 (2017), pp. 319\u2013342."},{"key":"ref15","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1561\/2200000050","volume":"8","author":"Bubeck S.","year":"2015","journal-title":"Found. Trends Mach. Learn."},{"key":"ref16","doi-asserted-by":"crossref","first-page":"757","DOI":"10.1007\/s00454-018-9992-1","volume":"59","author":"Bubeck S.","year":"2018","journal-title":"Discrete Comput. Geom."},{"key":"ref17","doi-asserted-by":"crossref","first-page":"1827","DOI":"10.4310\/CMS.2021.v19.n7.a4","volume":"19","author":"Cao Y.","year":"2021","journal-title":"Commun. Math. Sci."},{"key":"ref18","unstructured":"N. Chatterji, J. Diakonikolas, M. I. Jordan, and P. Bartlett, Langevin Monte Carlo without smoothness, Proc. Mach. Learn. Res. (PMLR), 108 (2020), pp. 1716\u20131726."},{"key":"ref19","unstructured":"X. Cheng, N. S. Chatterji, Y. Abbasi-Yadkori, P. L. Bartlett, and M. I. Jordan, Sharp Convergence Rates for Langevin Dynamics in the Nonconvex Setting, preprint, arXiv:1805.01648, 2018."},{"key":"ref20","unstructured":"X. Cheng, N. S. Chatterji, P. L. Bartlett, and M. I. Jordan, Underdamped Langevin MCMC: A non-asymptotic analysis, Proc. Mach. Learn. Res. (PMLR), 75 (2018), pp. 300\u2013323."},{"key":"ref21","unstructured":"X. Cheng, J. Zhang, and S. Sra, Theory and Algorithms for Diffusion Processes on Riemannian Manifolds, preprint, arXiv:2204.13665, 2022."},{"key":"ref22","unstructured":"S. Chewi, Log-Concave Sampling, manuscript."},{"key":"ref23","first-page":"1","volume":"178","author":"Chewi S.","year":"2022","journal-title":"Proc. Mach. Learn. Res. (PMLR)"},{"key":"ref24","first-page":"1","volume":"201","author":"Chewi S.","year":"2023","journal-title":"Proc. Mach. Learn. Res. (PMLR)"},{"key":"ref25","unstructured":"S. Chewi, P. R. Gerber, C. Lu, T. Le Gouic, and P. Rigollet, The query complexity of sampling from strongly log-concave distributions in one dimension, Proc. Mach. Learn. Res. (PMLR), 178 (2022), pp. 2041\u20132059."},{"key":"ref26","unstructured":"S. Chewi, C. Lu, K. Ahn, X. Cheng, T. Le Gouic, and P. Rigollet, Optimal dimension dependence of the Metropolis-adjusted Langevin algorithm, Proc. Mach. Learn. Res. (PMLR), 134 (2021), pp. 1260\u20131300."},{"key":"ref27","doi-asserted-by":"crossref","unstructured":"S. Chewi, J. d. D. Pont, J. Li, C. Lu, and S. Narayanan, Query lower bounds for log-concave sampling, J. ACM, 71 (2024), 29.","DOI":"10.1145\/3673651"},{"key":"ref28","first-page":"14771","volume-title":"Advances in Neural Information Processing Systems","volume":"34","author":"Chourasia R.","year":"2021"},{"key":"ref29","unstructured":"A. Dalalyan, Further and stronger analogy between sampling and optimization: Langevin Monte Carlo and gradient descent, Proc. Mach. Learn. Res. (PMLR), 65 (2017), pp. 678\u2013689."},{"key":"ref30","doi-asserted-by":"crossref","first-page":"651","DOI":"10.1111\/rssb.12183","volume":"79","author":"Dalalyan A.","year":"2017","journal-title":"J. R. Stat. Soc. Ser. B Stat. Methodol."},{"key":"ref31","doi-asserted-by":"crossref","first-page":"5278","DOI":"10.1016\/j.spa.2019.02.016","volume":"129","author":"Dalalyan A. S.","year":"2019","journal-title":"Stochastic Process. Appl."},{"key":"ref32","first-page":"235","volume":"23","author":"Dalalyan A. S.","year":"2022","journal-title":"J. Mach. Learn. Res."},{"key":"ref33","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1016\/0370-2693(87)91197-X","volume":"195","author":"Duane S.","year":"1987","journal-title":"Phys. Lett. B"},{"key":"ref34","first-page":"2666","volume":"20","author":"Durmus A.","year":"2019","journal-title":"J. Mach. Learn. Res."},{"key":"ref35","unstructured":"A. Durmus and E. Moulines, Sampling from Strongly Log-Concave Distributions with the Unadjusted Langevin Algorithm, preprint, arXiv:1605.01559, 2016."},{"key":"ref36","first-page":"1551","volume":"27","author":"Durmus A.","year":"2017","journal-title":"Ann. Appl. Probab."},{"key":"ref37","doi-asserted-by":"crossref","first-page":"2854","DOI":"10.3150\/18-BEJ1073","volume":"25","author":"Durmus A.","year":"2019","journal-title":"Bernoulli"},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1137\/16M1108340"},{"key":"ref39","unstructured":"R. Dwivedi, Y. Chen, M. J. Wainwright, and B. Yu, Log-concave sampling: Metropolis-Hastings algorithms are fast!, Proc. Mach. Learn. Res. (PMLR), 75 (2018), pp. 793\u2013797."},{"key":"ref40","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1561\/0400000042","volume":"9","author":"Dwork C.","year":"2014","journal-title":"Found. Trends Theoret. Comput. Sci."},{"key":"ref41","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/102782.102783","volume":"38","author":"Dyer M.","year":"1991","journal-title":"J. ACM"},{"key":"ref42","doi-asserted-by":"crossref","first-page":"1982","DOI":"10.1214\/18-AOP1299","volume":"47","author":"Eberle A.","year":"2019","journal-title":"Ann. Probab."},{"key":"ref43","unstructured":"M. A. Erdogdu and R. Hosseinzadeh, On the convergence of Langevin Monte Carlo: The interplay between tail growth and smoothness, Proc. Mach. Learn. Res. (PMLR), 134 (2021), pp. 1776\u20131822."},{"key":"ref44","unstructured":"M. A. Erdogdu, R. Hosseinzadeh, and S. Zhang, Convergence of Langevin Monte Carlo in chi-squared and R\u00e9nyi divergence, Proc. Mach. Learn. Res. (PMLR), 151 (2022), pp. 8151\u20138175."},{"key":"ref45","first-page":"9694","volume":"31","author":"Erdogdu M. A.","year":"2018","journal-title":"Advances in Neural Information Processing Systems"},{"key":"ref46","doi-asserted-by":"crossref","unstructured":"V. Feldman, T. Koren, and K. Talwar, Private stochastic convex optimization: Optimal rates in linear time, in Symposium on the Theory of Computing, ACM, New York, 2020, pp. 439\u2013449.","DOI":"10.1145\/3357713.3384335"},{"key":"ref47","doi-asserted-by":"crossref","unstructured":"V. Feldman, I. Mironov, K. Talwar, and A. Thakurta, Privacy amplification by iteration, in Symposium on Foundations of Computer Science, IEEE Computer Society, Los Alamitos, CA, 2018, pp. 521\u2013532.","DOI":"10.1109\/FOCS.2018.00056"},{"key":"ref48","first-page":"7222","volume-title":"Advances in Neural Information Processing Systems","volume":"33","author":"Ganesh A.","year":"2020"},{"key":"ref49","unstructured":"K. Gatmiry and S. S. Vempala, Convergence of the Riemannian Langevin Algorithm, preprint, arXiv:2204.10818, 2022."},{"key":"ref50","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1111\/j.1467-9868.2010.00765.x","volume":"73","author":"Girolami M.","year":"2011","journal-title":"J. R. Stat. Soc. Ser. B Stat. Methodol."},{"key":"ref51","first-page":"1593","volume":"15","author":"Hoffman M. D.","year":"2014","journal-title":"J. Mach. Learn. Res."},{"key":"ref52","first-page":"2883","volume":"31","author":"Hsieh Y.-P.","year":"2018","journal-title":"Advances in Neural Information Processing Systems"},{"key":"ref53","doi-asserted-by":"crossref","first-page":"1145","DOI":"10.1088\/0034-4885\/43\/9\/002","volume":"43","author":"James F.","year":"1980","journal-title":"Rep. Progr. Phys."},{"key":"ref54","unstructured":"M. Jerrum and A. Sinclair, The Markov chain Monte Carlo method: An approach to approximate counting and integration, in Approximation Algorithms for NP-Hard Problems, PWS Publishing, Boston, MA, 1996, pp. 482\u2013520."},{"key":"ref55","doi-asserted-by":"publisher","DOI":"10.1137\/S0036141096303359"},{"key":"ref56","doi-asserted-by":"crossref","first-page":"541","DOI":"10.1007\/BF02574061","volume":"13","author":"Kannan R.","year":"1995","journal-title":"Discrete Comput. Geom."},{"key":"ref57","doi-asserted-by":"crossref","first-page":"31684","DOI":"10.52202\/068431-2297","volume":"35","author":"Kook Y.","year":"2022","journal-title":"Advances in Neural Information Processing Systems"},{"key":"ref58","first-page":"18812","volume":"34","author":"Lee Y. T.","year":"2021","journal-title":"Advances in Neural Information Processing Systems"},{"key":"ref59","doi-asserted-by":"crossref","unstructured":"Y. T. Lee and S. S. Vempala, Convergence rate of Riemannian Hamiltonian Monte Carlo and faster polytope volume computation, in Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, ACM, New York, 2018, pp. 1115\u20131121.","DOI":"10.1145\/3188745.3188774"},{"key":"ref60","doi-asserted-by":"crossref","first-page":"4858","DOI":"10.1214\/23-AAP1935","volume":"33","author":"Lehec J.","year":"2023","journal-title":"Ann. Appl. Probab."},{"key":"ref61","doi-asserted-by":"crossref","DOI":"10.1090\/mbk\/107","volume-title":"Markov Chains and Mixing Times","volume":"107","author":"Levin D. A.","year":"2017","edition":"2"},{"key":"ref62","first-page":"3093","volume":"29","author":"Li M. B.","year":"2023","journal-title":"Bernoulli"},{"key":"ref63","first-page":"3229","author":"Liang J.","year":"2023","journal-title":"Winter Simulation Conference"},{"key":"ref64","series-title":"Springer Ser. Statist. 10","volume-title":"Monte Carlo Strategies in Scientific Computing","author":"Liu J. S.","year":"2001"},{"key":"ref65","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1007\/s101070050099","volume":"86","author":"Lov\u00e1sz L.","year":"1999","journal-title":"Math. Program."},{"key":"ref66","doi-asserted-by":"crossref","unstructured":"L. Lov\u00e1sz and M. Simonovits, The mixing rate of Markov chains, an isoperimetric inequality, and computing the volume, in Foundations of Computer Science, IEEE Computer Society, Los Alamitos, CA, 1990, pp. 346\u2013354.","DOI":"10.1109\/FSCS.1990.89553"},{"key":"ref67","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1002\/rsa.3240040402","volume":"4","author":"Lov\u00e1sz L.","year":"1993","journal-title":"Random Structures Algorithms"},{"key":"ref68","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970544727X"},{"key":"ref69","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1002\/rsa.20135","volume":"30","author":"Lov\u00e1sz L.","year":"2007","journal-title":"Random Structures Algorithms"},{"key":"ref70","first-page":"1942","volume":"27","author":"Ma Y.-A.","year":"2021","journal-title":"Bernoulli"},{"key":"ref71","doi-asserted-by":"crossref","unstructured":"F. McSherry and K. Talwar, Mechanism design via differential privacy, in Symposium on Foundations of Computer Science, IEEE, 2007, pp. 94\u2013103.","DOI":"10.1109\/FOCS.2007.66"},{"key":"ref72","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1214\/aos\/1033066201","volume":"24","author":"Mengersen K. L.","year":"1996","journal-title":"Ann. Statist."},{"key":"ref73","first-page":"1577","volume":"28","author":"Mou W.","year":"2022","journal-title":"Bernoulli"},{"key":"ref74","first-page":"2","volume-title":"Handbook of Markov Chain Monte Carlo","author":"Neal R. M.","year":"2011"},{"key":"ref75","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4419-8853-9","volume-title":"Introductory Lectures on Convex Optimization: A Basic Course","volume":"87","author":"Nesterov Y.","year":"2004"},{"key":"ref76","first-page":"1","author":"Nguyen D.","year":"2023","journal-title":"Commun. Math. Stat."},{"key":"ref77","doi-asserted-by":"crossref","first-page":"378","DOI":"10.1016\/0550-3213(81)90056-0","volume":"180","author":"Parisi G.","year":"1981","journal-title":"Nucl. Phys. B"},{"key":"ref78","unstructured":"M. Raginsky, A. Rakhlin, and M. Telgarsky, Non-convex learning via stochastic gradient Langevin dynamics: A nonasymptotic analysis, Proc. Mach. Learn. Res. (PMLR), 65 (2017), pp. 1674\u20131703."},{"key":"ref79","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-3071-5","volume-title":"Monte Carlo Statistical Methods","volume":"2","author":"Robert C. P.","year":"1999"},{"key":"ref80","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1214\/154957804100000024","volume":"1","author":"Roberts G. O.","year":"2004","journal-title":"Probab. Surv."},{"key":"ref81","doi-asserted-by":"crossref","first-page":"341","DOI":"10.2307\/3318418","volume":"2","author":"Roberts G. O.","year":"1996","journal-title":"Bernoulli"},{"key":"ref82","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1093\/biomet\/83.1.95","volume":"83","author":"Roberts G. O.","year":"1996","journal-title":"Biometrika"},{"key":"ref83","unstructured":"T. Ryffel, F. Bach, and D. Pointcheval, Differential Privacy Guarantees for Stochastic Gradient Langevin Dynamics, arXiv:2201.11980, 2022."},{"key":"ref84","first-page":"3786","volume":"33","author":"Salim A.","year":"2020","journal-title":"Advances in Neural Information Processing Systems"},{"key":"ref85","series-title":"Encyclopedia Math. Appl. 151","volume-title":"Convex Bodies: The Brunn\u2013Minkowski Theory","author":"Schneider R.","year":"2014"},{"key":"ref86","first-page":"2100","volume":"32","author":"Shen R.","year":"2019","journal-title":"Advances in Neural Information Processing Systems"},{"key":"ref87","volume-title":"Machine Learning and Knowledge Discovery in Databases","author":"Sordello M.","year":"2021"},{"key":"ref88","doi-asserted-by":"crossref","first-page":"3797","DOI":"10.1109\/TIT.2014.2320500","volume":"60","author":"Van Erven T.","year":"2014","journal-title":"IEEE Trans. Inform. Theory"},{"key":"ref89","first-page":"2","volume":"52","author":"Vempala S.","year":"2005","journal-title":"Combin. Comput. Geom."},{"key":"ref90","first-page":"8092","volume-title":"Advances in Neural Information Processing Systems","volume":"32","author":"Vempala S.","year":"2019"},{"key":"ref91","unstructured":"A. Wibisono, Sampling as optimization in the space of measures: The Langevin dynamics as a composite optimization problem, in Conference on Learning Theory, PMLR, 75 (2018), pp. 2093\u20133027."},{"key":"ref92","first-page":"12348","volume":"23","author":"Wu K.","year":"2022","journal-title":"J. Mach. Learn, Res."},{"key":"ref93","doi-asserted-by":"crossref","first-page":"703","DOI":"10.52202\/068431-0051","volume":"35","author":"Ye J.","year":"2022","journal-title":"Advances in Neural Information Processing Systems"},{"key":"ref94","unstructured":"K. S. Zhang, G. Peyr\u00e9, J. Fadili, and M. Pereyra, Wasserstein control of mirror Langevin Monte Carlo, Proc. Mach. Learn. Res. (PMLR), 125 (2020), pp. 3814\u20133841."}],"container-title":["SIAM Journal on Mathematics of Data Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/24M1638689","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T16:16:55Z","timestamp":1787329015000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/24M1638689"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,9]]},"references-count":94,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,9,30]]}},"alternative-id":["10.1137\/24M1638689"],"URL":"https:\/\/doi.org\/10.1137\/24m1638689","relation":{},"ISSN":["2577-0187"],"issn-type":[{"value":"2577-0187","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,7,9]]}}}