{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:51:57Z","timestamp":1781077917375,"version":"3.54.1"},"reference-count":81,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2024,8,8]],"date-time":"2024-08-08T00:00:00Z","timestamp":1723075200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF TRIPODS","award":["DMS-2022448"],"award-info":[{"award-number":["DMS-2022448"]}]},{"name":"UCLA"},{"DOI":"10.13039\/100013114","name":"Broad Institute of MIT and Harvard","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100013114","id-type":"DOI","asserted-by":"crossref"}]},{"name":"NSF TRIPODS","award":["DMS-2022448"],"award-info":[{"award-number":["DMS-2022448"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2024,8,31]]},"abstract":"<jats:p>\n            Log-concave sampling has witnessed remarkable algorithmic advances in recent years, but the corresponding problem of proving\n            <jats:italic>lower bounds<\/jats:italic>\n            for this task has remained elusive, with lower bounds previously known only in dimension one. In this work, we establish the following query lower bounds: (1) sampling from strongly log-concave and log-smooth distributions in dimension\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(d\\ge 2\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            requires\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\Omega (\\log \\kappa)\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            queries, which is sharp in any constant dimension, and (2) sampling from Gaussians in dimension\n            <jats:italic>d<\/jats:italic>\n            (hence also from general log-concave and log-smooth distributions in dimension\n            <jats:italic>d<\/jats:italic>\n            ) requires\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\widetilde{\\Omega }(\\min (\\sqrt \\kappa \\log d, d))\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            queries, which is nearly sharp for the class of Gaussians. Here,\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\kappa\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            denotes the condition number of the target distribution. Our proofs rely upon (1) a multiscale construction inspired by work on the Kakeya conjecture in geometric measure theory, and (2) a novel reduction that demonstrates that block Krylov algorithms are optimal for this problem, as well as connections to lower bound techniques based on Wishart matrices developed in the matrix-vector query literature.\n          <\/jats:p>","DOI":"10.1145\/3673651","type":"journal-article","created":{"date-parts":[[2024,6,21]],"date-time":"2024-06-21T11:16:39Z","timestamp":1718968599000},"page":"1-42","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Query Lower Bounds for Log-concave Sampling"],"prefix":"10.1145","volume":"71","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2701-0703","authenticated-orcid":false,"given":"Sinho","family":"Chewi","sequence":"first","affiliation":[{"name":"Institute for Advanced Study, Princeton, United States"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2921-960X","authenticated-orcid":false,"given":"Jaume","family":"de Dios Pont","sequence":"additional","affiliation":[{"name":"ETH Z\u00fcrich, Z\u00fcrich, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-5035-3728","authenticated-orcid":false,"given":"Jerry","family":"Li","sequence":"additional","affiliation":[{"name":"Microsoft Research, Redmond, United States"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0006-1567-1722","authenticated-orcid":false,"given":"Chen","family":"Lu","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, United States"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2325-8923","authenticated-orcid":false,"given":"Shyam","family":"Narayanan","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, United States"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,8,8]]},"reference":[{"key":"e_1_3_3_2_1","first-page":"28405","volume-title":"Advances in Neural Information Processing Systems","author":"Ahn Kwangjun","year":"2021","unstructured":"Kwangjun Ahn and Sinho Chewi. 2021. Efficient constrained sampling via the mirror-Langevin algorithm. In Advances in Neural Information Processing Systems, M. Ranzato, A. Beygelzimer, K. Nguyen, P. S. Liang, J. W. Vaughan, and Y. Dauphin (Eds.), Vol. 34. Curran Associates, Inc., 28405\u201328418."},{"key":"e_1_3_3_3_1","doi-asserted-by":"crossref","DOI":"10.1145\/3653446","article-title":"Faster high-accuracy log-concave sampling via algorithmic warm starts","author":"Altschuler Jason M.","year":"2024","unstructured":"Jason M. Altschuler and Sinho Chewi. 2024. Faster high-accuracy log-concave sampling via algorithmic warm starts. Journal of the ACM 71, 3 (2024), 1\u201355.","journal-title":"Journal of the ACM"},{"key":"e_1_3_3_4_1","series-title":"Proceedings of Machine Learning Research","first-page":"2509","volume-title":"Proceedings of the 36th Conference on Learning Theory","volume":"195","author":"Altschuler Jason M.","year":"2023","unstructured":"Jason M. Altschuler and Kunal Talwar. 2023. Resolving the mixing time of the Langevin algorithm to its stationary distribution for log-concave sampling. In Proceedings of the 36th Conference on Learning Theory(Proceedings of Machine Learning Research, Vol. 195), Gergely Neu and Lorenzo Rosasco (Eds.). PMLR, 2509\u20132510."},{"key":"e_1_3_3_5_1","first-page":"71","article-title":"Some large-scale matrix computation problems","volume":"7","author":"Bai Zhaojun","year":"1996","unstructured":"Zhaojun Bai, Gark Fahey, and Gene Golub. 1996. Some large-scale matrix computation problems. Journal of Computational and Applied Mathematics 7, 1-2 (1996), 71\u201389.","journal-title":"Journal of Computational and Applied Mathematics"},{"key":"e_1_3_3_6_1","doi-asserted-by":"crossref","first-page":"1130","DOI":"10.1145\/3519935.3519988","volume-title":"Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing","author":"Bakshi Ainesh","year":"2022","unstructured":"Ainesh Bakshi, Kenneth L. Clarkson, and David P. Woodruff. 2022. Low-rank approximation with \\(1\/\\epsilon ^{1\/3}\\) matrix-vector products. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing. ACM, 1130\u20131143."},{"key":"e_1_3_3_7_1","first-page":"2896","volume-title":"Proceedings of the Conference on Learning Theory","author":"Balasubramanian Krishnakumar","year":"2022","unstructured":"Krishnakumar Balasubramanian, Sinho Chewi, Murat A. Erdogdu, Adil Salim, and Matthew S. Zhang. 2022. Towards a theory of non-log-concave sampling: First-order stationarity guarantees for Langevin Monte Carlo. In Proceedings of the Conference on Learning Theory. PMLR, 2896\u20132923."},{"key":"e_1_3_3_8_1","first-page":"1777","volume-title":"Proceedings of the Conference on Learning Theory","author":"Bernton Espen","year":"2018","unstructured":"Espen Bernton. 2018. Langevin Monte Carlo and JKO splitting. In Proceedings of the Conference on Learning Theory. PMLR, 1777\u20131798."},{"key":"e_1_3_3_9_1","series-title":"Proceedings of Machine Learning Research","first-page":"627","volume-title":"Proceedings of the Conference on Learning Theory, (COLT)","volume":"125","author":"Braverman Mark","year":"2020","unstructured":"Mark Braverman, Elad Hazan, Max Simchowitz, and Blake E. Woodworth. 2020. The gradient complexity of linear regression. In Proceedings of the Conference on Learning Theory, (COLT)(Proceedings of Machine Learning Research, Vol. 125). PMLR, 627\u2013647."},{"key":"e_1_3_3_10_1","doi-asserted-by":"crossref","first-page":"1144","DOI":"10.1145\/3519935.3520009","volume-title":"Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing","author":"Braverman Vladimir","year":"2022","unstructured":"Vladimir Braverman, Aditya Krishnan, and Christopher Musco. 2022. Sublinear time spectral density estimation. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing. ACM, 1144\u20131157."},{"key":"e_1_3_3_11_1","unstructured":"Matthew Brennan Guy Bresler and Brice Huang. 2021. De Finetti-style results for Wishart matrices: Combinatorial structure and phase transitions. arXiv:2103.14011. Retrieved from https:\/\/arxiv.org\/abs\/2103.14011"},{"issue":"3","key":"e_1_3_3_12_1","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1561\/2200000050","article-title":"Convex optimization: Algorithms and complexity","volume":"8","author":"Bubeck S\u00e9bastien","year":"2015","unstructured":"S\u00e9bastien Bubeck. 2015. Convex optimization: Algorithms and complexity. Foundations and Trends\u00ae in Machine Learning 8, 3-4 (2015), 231\u2013357.","journal-title":"Foundations and Trends\u00ae in Machine Learning"},{"issue":"3","key":"e_1_3_3_13_1","doi-asserted-by":"crossref","first-page":"503","DOI":"10.1002\/rsa.20633","article-title":"Testing for high-dimensional geometry in random graphs","volume":"49","author":"Bubeck S\u00e9bastien","year":"2016","unstructured":"S\u00e9bastien Bubeck, Jian Ding, Ronen Eldan, and Mikl\u00f3s Z. R\u00e1cz. 2016. Testing for high-dimensional geometry in random graphs. Random Structures Algorithms 49, 3 (2016), 503\u2013532.","journal-title":"Random Structures Algorithms"},{"issue":"2","key":"e_1_3_3_14_1","first-page":"588","article-title":"Entropic CLT and phase transition in high-dimensional Wishart matrices","author":"Bubeck S\u00e9bastien","year":"2018","unstructured":"S\u00e9bastien Bubeck and Shirshendu Ganguly. 2018. Entropic CLT and phase transition in high-dimensional Wishart matrices. International Mathematics Research Notices IMRN 2018, 2 (2018), 588\u2013606.","journal-title":"International Mathematics Research Notices IMRN"},{"issue":"7","key":"e_1_3_3_15_1","doi-asserted-by":"crossref","first-page":"1827","DOI":"10.4310\/CMS.2021.v19.n7.a4","article-title":"Complexity of randomized algorithms for underdamped Langevin dynamics","volume":"19","author":"Cao Yu","year":"2021","unstructured":"Yu Cao, Jianfeng Lu, and Lihan Wang. 2021. Complexity of randomized algorithms for underdamped Langevin dynamics. Communications in Mathematical Sciences 19, 7 (2021), 1827\u20131853.","journal-title":"Communications in Mathematical Sciences"},{"issue":"2","key":"e_1_3_3_16_1","first-page":"1074","article-title":"Oracle lower bounds for stochastic gradient sampling algorithms","volume":"28","author":"Chatterji Niladri S.","year":"2022","unstructured":"Niladri S. Chatterji, Peter L. Bartlett, and Philip M. Long. 2022. Oracle lower bounds for stochastic gradient sampling algorithms. Bernoulli 28, 2 (2022), 1074\u20131092.","journal-title":"Bernoulli"},{"key":"e_1_3_3_17_1","series-title":"Proceedings of Machine Learning Research","first-page":"2984","volume-title":"Proceedings of the 35th Conference on Learning Theory","volume":"178","author":"Chen Yongxin","year":"2022","unstructured":"Yongxin Chen, Sinho Chewi, Adil Salim, and Andre Wibisono. 2022. Improved analysis for a proximal algorithm for sampling. In Proceedings of the 35th Conference on Learning Theory(Proceedings of Machine Learning Research, Vol. 178), Po-Ling Loh and Maxim Raginsky (Eds.). PMLR, 2984\u20133014."},{"key":"e_1_3_3_18_1","article-title":"Fast mixing of Metropolized Hamiltonian Monte Carlo: Benefits of multi-step gradients","author":"Chen Yuansi","year":"2020","unstructured":"Yuansi Chen, Raaz Dwivedi, Martin J. Wainwright, and Bin Yu. 2020. Fast mixing of Metropolized Hamiltonian Monte Carlo: Benefits of multi-step gradients. The Journal of Machine Learning Research 21, 92 (2020), 1\u201372.","journal-title":"The Journal of Machine Learning Research"},{"key":"e_1_3_3_19_1","doi-asserted-by":"crossref","first-page":"110","DOI":"10.1109\/FOCS54457.2022.00018","volume-title":"Proceedings of the 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science","author":"Chen Yuansi","year":"2022","unstructured":"Yuansi Chen and Ronen Eldan. 2022. Localization schemes: A framework for proving mixing bounds for Markov chains (extended abstract). In Proceedings of the 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science. 110\u2013122."},{"key":"e_1_3_3_20_1","series-title":"Proceedings of Machine Learning Research","first-page":"300","volume-title":"Proceedings of the 31st Conference on Learning Theory","volume":"75","author":"Cheng Xiang","year":"2018","unstructured":"Xiang Cheng, Niladri S. Chatterji, Peter L. Bartlett, and Michael I. Jordan. 2018. Underdamped Langevin MCMC: A non-asymptotic analysis. In Proceedings of the 31st Conference on Learning Theory(Proceedings of Machine Learning Research, Vol. 75), S\u00e9bastien Bubeck, Vianney Perchet, and Philippe Rigollet (Eds.). PMLR, 300\u2013323."},{"key":"e_1_3_3_21_1","unstructured":"Sinho Chewi. 2024. Log-concave Sampling. (2024). Book draft available at Retrieved fromhttps:\/\/chewisinho.github.io\/"},{"key":"e_1_3_3_22_1","series-title":"Proceedings of Machine Learning Research","first-page":"1","volume-title":"Proceedings of the 35th Conference on Learning Theory","volume":"178","author":"Chewi Sinho","year":"2022","unstructured":"Sinho Chewi, Murat A. Erdogdu, Mufan B. Li, Ruoqi Shen, and Matthew S. Zhang. 2022a. Analysis of Langevin Monte Carlo from Poincar\u00e9 to log-Sobolev. In Proceedings of the 35th Conference on Learning Theory(Proceedings of Machine Learning Research, Vol. 178), Po-Ling Loh and Maxim Raginsky (Eds.). PMLR, 1\u20132."},{"key":"e_1_3_3_23_1","series-title":"Proceedings of Machine Learning Research","first-page":"375","volume-title":"Proceedings of the 34th International Conference on Algorithmic Learning Theory","volume":"201","author":"Chewi Sinho","year":"2023","unstructured":"Sinho Chewi, Patrik R. Gerber, Holden Lee, and Chen Lu. 2023. Fisher information lower bounds for sampling. In Proceedings of the 34th International Conference on Algorithmic Learning Theory(Proceedings of Machine Learning Research, Vol. 201), Shipra Agrawal and Francesco Orabona (Eds.). PMLR, 375\u2013410."},{"key":"e_1_3_3_24_1","series-title":"Proceedings of Machine Learning Research","first-page":"2041","volume-title":"Proceedings of the 35th Conference on Learning Theory","volume":"178","author":"Chewi Sinho","year":"2022","unstructured":"Sinho Chewi, Patrik R. Gerber, Chen Lu, Thibaut Le Gouic, and Philippe Rigollet. 2022b. The query complexity of sampling from strongly log-concave distributions in one dimension. In Proceedings of the 35th Conference on Learning Theory(Proceedings of Machine Learning Research, Vol. 178), Po-Ling Loh and Maxim Raginsky (Eds.). PMLR, 2041\u20132059."},{"key":"e_1_3_3_25_1","first-page":"19573","article-title":"Exponential ergodicity of mirror-Langevin diffusions","volume":"33","author":"Chewi Sinho","year":"2020","unstructured":"Sinho Chewi, Thibaut Le Gouic, Chen Lu, Tyler Maunu, Philippe Rigollet, and Austin J. Stromme. 2020. Exponential ergodicity of mirror-Langevin diffusions. Advances in Neural Information Processing Systems 33 (2020), 19573\u201319585.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_3_26_1","first-page":"1260","volume-title":"Proceedings of the Conference on Learning Theory","author":"Chewi Sinho","year":"2021","unstructured":"Sinho Chewi, Chen Lu, Kwangjun Ahn, Xiang Cheng, Thibaut Le Gouic, and Philippe Rigollet. 2021. Optimal dimension dependence of the Metropolis-adjusted Langevin algorithm. In Proceedings of the Conference on Learning Theory. PMLR, 1260\u20131300."},{"key":"e_1_3_3_27_1","doi-asserted-by":"crossref","first-page":"1263","DOI":"10.1145\/3219819.3220119","volume-title":"Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining,","author":"Cohen-Steiner David","year":"2018","unstructured":"David Cohen-Steiner, Weihao Kong, Christian Sohler, and Gregory Valiant. 2018. Approximating the spectrum of a graph. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining,. ACM, 1263\u20131271."},{"key":"e_1_3_3_28_1","volume-title":"Elements of Information Theory (second ed.)","author":"Cover Thomas M.","year":"2006","unstructured":"Thomas M. Cover and Joy A. Thomas. 2006. Elements of Information Theory (second ed.). Wiley-Interscience [John Wiley & Sons], Hoboken, NJ. xxiv+748 pages."},{"issue":"3","key":"e_1_3_3_29_1","doi-asserted-by":"crossref","first-page":"651","DOI":"10.1111\/rssb.12183","article-title":"Theoretical guarantees for approximate sampling from smooth and log-concave densities","volume":"79","author":"Dalalyan Arnak S.","year":"2017","unstructured":"Arnak S. Dalalyan. 2017. Theoretical guarantees for approximate sampling from smooth and log-concave densities. Journal of the Royal Statistical Society: Series B (Statistical Methodology) 79, 3 (2017), 651\u2013676.","journal-title":"Journal of the Royal Statistical Society: Series B (Statistical Methodology)"},{"issue":"12","key":"e_1_3_3_30_1","doi-asserted-by":"crossref","first-page":"5278","DOI":"10.1016\/j.spa.2019.02.016","article-title":"User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient","volume":"129","author":"Dalalyan Arnak S.","year":"2019","unstructured":"Arnak S. Dalalyan and Avetik Karagulyan. 2019. User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient. Stochastic Processes and their Applications 129, 12 (2019), 5278\u20135311.","journal-title":"Stochastic Processes and their Applications"},{"issue":"3","key":"e_1_3_3_31_1","first-page":"1956","article-title":"On sampling from a log-concave density using kinetic Langevin diffusions","volume":"26","author":"Dalalyan Arnak S.","year":"2020","unstructured":"Arnak S. Dalalyan and Lionel Riou-Durand. 2020. On sampling from a log-concave density using kinetic Langevin diffusions. Bernoulli 26, 3 (2020), 1956\u20131988.","journal-title":"Bernoulli"},{"issue":"5","key":"e_1_3_3_32_1","doi-asserted-by":"crossref","first-page":"1423","DOI":"10.1016\/j.jcss.2011.12.023","article-title":"Sparse regression learning by aggregation and Langevin Monte-Carlo","volume":"78","author":"Dalalyan Arnak S.","year":"2012","unstructured":"Arnak S. Dalalyan and Alexandre B. Tsybakov. 2012. Sparse regression learning by aggregation and Langevin Monte-Carlo. Journal of Computer and System Sciences 78, 5 (2012), 1423\u20131443.","journal-title":"Journal of Computer and System Sciences"},{"key":"e_1_3_3_33_1","first-page":"30088","volume-title":"Advances in Neural Information Processing Systems 34","author":"Dharangutte Prathamesh","year":"2021","unstructured":"Prathamesh Dharangutte and Christopher Musco. 2021. Dynamic trace estimation. In Advances in Neural Information Processing Systems 34. 30088\u201330099."},{"key":"e_1_3_3_34_1","first-page":"1683","volume-title":"Proceedings of the Conference on Learning Theory","author":"Ding Zhiyan","year":"2021","unstructured":"Zhiyan Ding, Qin Li, Jianfeng Lu, and Stephen J. Wright. 2021. Random coordinate Langevin Monte Carlo. In Proceedings of the Conference on Learning Theory. PMLR, 1683\u20131710."},{"key":"e_1_3_3_35_1","first-page":"Paper No. 73, 4","article-title":"Analysis of Langevin Monte Carlo via convex optimization","volume":"20","author":"Durmus Alain","year":"2019","unstructured":"Alain Durmus, Szymon Majewski, and B\u0142a\u017cej Miasojedow. 2019. Analysis of Langevin Monte Carlo via convex optimization. Journal of Machine Learning Research 20 (2019), Paper No. 73, 46.","journal-title":"Journal of Machine Learning Research"},{"issue":"3","key":"e_1_3_3_36_1","first-page":"1551","article-title":"Nonasymptotic convergence analysis for the unadjusted Langevin algorithm","volume":"27","author":"Durmus Alain","year":"2017","unstructured":"Alain Durmus and Eric Moulines. 2017. Nonasymptotic convergence analysis for the unadjusted Langevin algorithm. The Annals of Applied Probability 27, 3 (2017), 1551\u20131587.","journal-title":"The Annals of Applied Probability"},{"issue":"4","key":"e_1_3_3_37_1","doi-asserted-by":"crossref","first-page":"1093","DOI":"10.1090\/S0894-0347-08-00607-3","article-title":"On the size of Kakeya sets in finite fields","volume":"22","author":"Dvir Zeev","year":"2009","unstructured":"Zeev Dvir. 2009. On the size of Kakeya sets in finite fields. Journal of the American Mathematical Society 22, 4 (2009), 1093\u20131097.","journal-title":"Journal of the American Mathematical Society"},{"key":"e_1_3_3_38_1","first-page":"793","volume-title":"Proceedings of the Conference on Learning Theory","author":"Dwivedi Raaz","year":"2018","unstructured":"Raaz Dwivedi, Yuansi Chen, Martin J. Wainwright, and Bin Yu. 2018. Log-concave sampling: Metropolis\u2013Hastings algorithms are fast!. In Proceedings of the Conference on Learning Theory. PMLR, 793\u2013797."},{"key":"e_1_3_3_39_1","volume-title":"Eigenvalues and condition numbers of random matrices","author":"Edelman Alan","year":"1989","unstructured":"Alan Edelman. 1989. Eigenvalues and condition numbers of random matrices. Ph. D. Dissertation. Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA."},{"key":"e_1_3_3_40_1","series-title":"Proceedings of Machine Learning Research","first-page":"1473","volume-title":"Proceedings of the 36th Conference on Learning Theory","volume":"195","author":"Fan Jiaojiao","year":"2023","unstructured":"Jiaojiao Fan, Bo Yuan, and Yongxin Chen. 2023. Improved dimension dependence of a proximal algorithm for sampling. In Proceedings of the 36th Conference on Learning Theory(Proceedings of Machine Learning Research, Vol. 195), Gergely Neu and Lorenzo Rosasco (Eds.). PMLR, 1473\u20131521."},{"key":"e_1_3_3_41_1","unstructured":"Khashayar Gatmiry and Santosh S. Vempala. 2022. Convergence of the Riemannian Langevin algorithm. arXiv:2204.10818. Retrieved from https:\/\/arxiv.org\/abs\/2204.10818"},{"key":"e_1_3_3_42_1","first-page":"579","volume-title":"Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing","author":"Ge Rong","year":"2020","unstructured":"Rong Ge, Holden Lee, and Jianfeng Lu. 2020. Estimating normalizing constants for log-concave distributions: algorithms and lower bounds. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. 579\u2013586."},{"key":"e_1_3_3_43_1","series-title":"Proceedings of Machine Learning Research","first-page":"1948","volume-title":"Proceedings of the 35th Conference on Learning Theory","volume":"178","author":"Gopi Sivakanth","year":"2022","unstructured":"Sivakanth Gopi, Yin Tat Lee, and Daogao Liu. 2022. Private convex optimization via exponential mechanism. In Proceedings of the 35th Conference on Learning Theory(Proceedings of Machine Learning Research, Vol. 178), Po-Ling Loh and Maxim Raginsky (Eds.). PMLR, 1948\u20131989."},{"key":"e_1_3_3_44_1","doi-asserted-by":"crossref","first-page":"433","DOI":"10.1080\/03610919008812866","article-title":"A stochastic estimator of the trace of the influence matrix for Laplacian smoothing splines","volume":"19","author":"Hutchinson Michael F.","year":"1990","unstructured":"Michael F. Hutchinson. 1990. A stochastic estimator of the trace of the influence matrix for Laplacian smoothing splines. Communications in Statistics-Simulation and Computation 19, 2 (1990), 433\u2013450.","journal-title":"Communications in Statistics-Simulation and Computation"},{"key":"e_1_3_3_45_1","first-page":"715","volume-title":"Advances in Neural Information Processing Systems","author":"Jiang Qijia","year":"2021","unstructured":"Qijia Jiang. 2021. Mirror Langevin Monte Carlo: The case under isoperimetry. In Advances in Neural Information Processing Systems, M. Ranzato, A. Beygelzimer, Y. Dauphin, P. S. Liang, and J. Wortman Vaughan (Eds.), Vol. 34. Curran Associates, Inc., 715\u2013725."},{"issue":"3","key":"e_1_3_3_46_1","doi-asserted-by":"crossref","first-page":"804","DOI":"10.1007\/s10959-013-0519-7","article-title":"Approximation of rectangular beta-Laguerre ensembles and large deviations","volume":"28","author":"Jiang Tiefeng","year":"2015","unstructured":"Tiefeng Jiang and Danning Li. 2015. Approximation of rectangular beta-Laguerre ensembles and large deviations. Journal of Theoretical Probability 28, 3 (2015), 804\u2013847.","journal-title":"Journal of Theoretical Probability"},{"issue":"1","key":"e_1_3_3_47_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/S0036141096303359","article-title":"The variational formulation of the Fokker\u2013Planck equation","volume":"29","author":"Jordan Richard","year":"1998","unstructured":"Richard Jordan, David Kinderlehrer, and Felix Otto. 1998. The variational formulation of the Fokker\u2013Planck equation. SIAM Journal on Mathematical Analysis 29, 1 (1998), 1\u201317.","journal-title":"SIAM Journal on Mathematical Analysis"},{"key":"e_1_3_3_48_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-17364-6","volume-title":"Extremal Combinatorics: With Applications in Computer Science","author":"Jukna Stasys","year":"2011","unstructured":"Stasys Jukna. 2011. Extremal Combinatorics: With Applications in Computer Science. Vol. 571. Springer."},{"key":"e_1_3_3_49_1","first-page":"2565","volume-title":"Proceedings of the Conference on Learning Theory","author":"Lee Yin Tat","year":"2020","unstructured":"Yin Tat Lee, Ruoqi Shen, and Kevin Tian. 2020. Logsmooth gradient concentration and tighter runtimes for Metropolized Hamiltonian Monte Carlo. In Proceedings of the Conference on Learning Theory. PMLR, 2565\u20132597."},{"key":"e_1_3_3_50_1","first-page":"18812","article-title":"Lower bounds on Metropolized sampling methods for well-conditioned distributions","volume":"34","author":"Lee Yin Tat","year":"2021","unstructured":"Yin Tat Lee, Ruoqi Shen, and Kevin Tian. 2021a. Lower bounds on Metropolized sampling methods for well-conditioned distributions. Advances in Neural Information Processing Systems 34 (2021), 18812\u201318824.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_3_51_1","first-page":"2993","volume-title":"Proceedings of the Conference on Learning Theory","author":"Lee Yin Tat","year":"2021","unstructured":"Yin Tat Lee, Ruoqi Shen, and Kevin Tian. 2021b. Structured logconcave sampling with a restricted Gaussian oracle. In Proceedings of the Conference on Learning Theory. PMLR, 2993\u20133050."},{"key":"e_1_3_3_52_1","series-title":"Proceedings of Machine Learning Research","first-page":"718","volume-title":"Proceedings of the 33rd International Conference on Algorithmic Learning Theory","volume":"167","author":"Li Ruilin","year":"2022","unstructured":"Ruilin Li, Molei Tao, Santosh S. Vempala, and Andre Wibisono. 2022. The mirror Langevin algorithm converges with vanishing bias. In Proceedings of the 33rd International Conference on Algorithmic Learning Theory(Proceedings of Machine Learning Research, Vol. 167), Sanjoy Dasgupta and Nika Haghtalab (Eds.). PMLR, 718\u2013742."},{"issue":"2","key":"e_1_3_3_53_1","doi-asserted-by":"crossref","first-page":"392","DOI":"10.1016\/j.jcss.2005.08.004","article-title":"Simulated annealing in convex bodies and an  \\(O^*(n^4)\\)  volume algorithm","volume":"72","author":"Lov\u00e1sz L\u00e1szl\u00f3","year":"2006","unstructured":"L\u00e1szl\u00f3 Lov\u00e1sz and Santosh Vempala. 2006. Simulated annealing in convex bodies and an \\(O^*(n^4)\\) volume algorithm. Journal of Computer and System Sciences 72, 2 (2006), 392\u2013417.","journal-title":"Journal of Computer and System Sciences"},{"issue":"3","key":"e_1_3_3_54_1","first-page":"1942","article-title":"Is there an analog of Nesterov acceleration for gradient-based MCMC?","volume":"27","author":"Ma Yi-An","year":"2021","unstructured":"Yi-An Ma, Niladri S. Chatterji, Xiang Cheng, Nicolas Flammarion, Peter L. Bartlett, and Michael I. Jordan. 2021. Is there an analog of Nesterov acceleration for gradient-based MCMC? Bernoulli 27, 3 (2021), 1942\u20131992.","journal-title":"Bernoulli"},{"key":"e_1_3_3_55_1","doi-asserted-by":"crossref","first-page":"142","DOI":"10.1137\/1.9781611976496.16","volume-title":"Proceedings of the 4th Symposium on Simplicity in Algorithms","author":"Meyer Raphael A.","year":"2021","unstructured":"Raphael A. Meyer, Cameron Musco, Christopher Musco, and David P. Woodruff. 2021. Hutch++: Optimal stochastic trace estimation. In Proceedings of the 4th Symposium on Simplicity in Algorithms. SIAM, 142\u2013155."},{"issue":"10","key":"e_1_3_3_56_1","doi-asserted-by":"crossref","first-page":"7839","DOI":"10.1093\/imrn\/rnaa336","article-title":"A CLT in Stein\u2019s distance for generalized Wishart matrices and higher-order tensors","author":"Mikulincer Dan","year":"2022","unstructured":"Dan Mikulincer. 2022. A CLT in Stein\u2019s distance for generalized Wishart matrices and higher-order tensors. International Mathematics Research Notices IMRN10 (2022), 7839\u20137872.","journal-title":"International Mathematics Research Notices IMRN"},{"key":"e_1_3_3_57_1","first-page":"1396","volume-title":"Advances in Neural Information Processing Systems 28","author":"Musco Cameron","year":"2015","unstructured":"Cameron Musco and Christopher Musco. 2015. Randomized block Krylov methods for stronger and faster approximate singular value decomposition. In Advances in Neural Information Processing Systems 28. 1396\u20131404."},{"key":"e_1_3_3_58_1","unstructured":"Arkadij S. Nemirovskij and David B. Yudin. 1983. Problem complexity and method efficiency in optimization. (1983)."},{"key":"e_1_3_3_59_1","series-title":"Springer Optimization and Its Applications","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-91578-4","volume-title":"Lectures on Convex Optimization","author":"Nesterov Yurii","year":"2018","unstructured":"Yurii Nesterov. 2018. Lectures on Convex Optimization. Springer Optimization and Its Applications, Vol. 137. Springer, Cham. xxiii+589 pages."},{"issue":"0","key":"e_1_3_3_60_1","first-page":"1","article-title":"Prior-preconditioned conjugate gradient method for accelerated Gibbs sampling in \u201clarge n, large p\u201d Bayesian sparse regression","volume":"0","author":"Nishimura Akihiko","year":"2022","unstructured":"Akihiko Nishimura and Marc A. Suchard. 2022. Prior-preconditioned conjugate gradient method for accelerated Gibbs sampling in \u201clarge n, large p\u201d Bayesian sparse regression. Journal of the American Statistical Association 0, 0 (2022), 1\u201314.","journal-title":"Journal of the American Statistical Association"},{"issue":"1","key":"e_1_3_3_61_1","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1007\/BF01181172","article-title":"\u00dcber einen Satz von Besicovitsch","volume":"28","author":"Perron Oskar","year":"1928","unstructured":"Oskar Perron. 1928. \u00dcber einen Satz von Besicovitsch. Mathematische Zeitschrift 28, 1 (1928), 383\u2013386.","journal-title":"Mathematische Zeitschrift"},{"issue":"2","key":"e_1_3_3_62_1","doi-asserted-by":"crossref","first-page":"898","DOI":"10.1007\/s10959-018-0808-2","article-title":"A smooth transition from Wishart to GOE","volume":"32","author":"R\u00e1cz Mikl\u00f3s Z.","year":"2019","unstructured":"Mikl\u00f3s Z. R\u00e1cz and Jacob Richey. 2019. A smooth transition from Wishart to GOE. Journal of Theoretical Probability 32, 2 (2019), 898\u2013906.","journal-title":"Journal of Theoretical Probability"},{"issue":"3","key":"e_1_3_3_63_1","doi-asserted-by":"crossref","first-page":"1037","DOI":"10.1016\/j.aim.2008.06.004","article-title":"Dispersion of mass and the complexity of randomized geometric algorithms","volume":"219","author":"Rademacher Luis","year":"2008","unstructured":"Luis Rademacher and Santosh Vempala. 2008. Dispersion of mass and the complexity of randomized geometric algorithms. Advances in Mathematics 219, 3 (2008), 1037\u20131069.","journal-title":"Advances in Mathematics"},{"key":"e_1_3_3_64_1","series-title":"LIPIcs","first-page":"26:1\u201326:20","volume-title":"Proceedings of the International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","volume":"176","author":"Rashtchian Cyrus","year":"2020","unstructured":"Cyrus Rashtchian, David P. Woodruff, and Hanlin Zhu. 2020. Vector-matrix-vector queries for solving linear algebra, statistics, and graph problems. In Proceedings of the International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques(LIPIcs, Vol. 176). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 26:1\u201326:20."},{"key":"e_1_3_3_65_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-4145-2","volume-title":"Monte Carlo Statistical Methods (second ed.)","author":"Robert Christian P.","year":"2004","unstructured":"Christian P. Robert and George Casella. 2004. Monte Carlo Statistical Methods (second ed.). Springer-Verlag, New York. xxx+645 pages."},{"issue":"2","key":"e_1_3_3_66_1","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1561\/0400000065","article-title":"Faster algorithms via approximation theory","volume":"9","author":"Sachdeva Sushant","year":"2014","unstructured":"Sushant Sachdeva and Nisheeth K. Vishnoi. 2014. Faster algorithms via approximation theory. Foundations and Trends in Theoretical Computer Science 9, 2 (2014), 125\u2013210.","journal-title":"Foundations and Trends in Theoretical Computer Science"},{"key":"e_1_3_3_67_1","first-page":"3786","volume-title":"Advances in Neural Information Processing Systems","author":"Salim Adil","year":"2020","unstructured":"Adil Salim and Peter Richtarik. 2020. Primal dual interpretation of the proximal stochastic gradient Langevin algorithm. In Advances in Neural Information Processing Systems, H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (Eds.), Vol. 33. Curran Associates, Inc., 3786\u20133796."},{"issue":"3","key":"e_1_3_3_68_1","doi-asserted-by":"crossref","first-page":"375","DOI":"10.2140\/apde.2008.1.375","article-title":"An improved lower bound on the size of Kakeya sets over finite fields","volume":"1","author":"Saraf Shubhangi","year":"2008","unstructured":"Shubhangi Saraf and Madhu Sudan. 2008. An improved lower bound on the size of Kakeya sets over finite fields. Analysis & PDE 1, 3 (2008), 375\u2013379.","journal-title":"Analysis & PDE"},{"key":"e_1_3_3_69_1","article-title":"The randomized midpoint method for log-concave sampling","volume":"32","author":"Shen Ruoqi","year":"2019","unstructured":"Ruoqi Shen and Yin Tat Lee. 2019. The randomized midpoint method for log-concave sampling. Advances in Neural Information Processing Systems 32 (2019).","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_3_70_1","doi-asserted-by":"crossref","first-page":"1249","DOI":"10.1145\/3188745.3188796","volume-title":"Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing","author":"Simchowitz Max","year":"2018","unstructured":"Max Simchowitz, Ahmed El Alaoui, and Benjamin Recht. 2018. Tight query complexity lower bounds for PCA via finite sample deformed Wigner law. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. ACM, 1249\u20131259."},{"key":"e_1_3_3_71_1","series-title":"LIPIcs","first-page":"94:1\u201394:16","volume-title":"Proceedings of the 46th International Colloquium on Automata, Languages, and Programming","volume":"132","author":"Sun Xiaoming","year":"2019","unstructured":"Xiaoming Sun, David P. Woodruff, Guang Yang, and Jialin Zhang. 2019. Querying a matrix through matrix-vector products. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming(LIPIcs, Vol. 132). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 94:1\u201394:16."},{"issue":"2","key":"e_1_3_3_72_1","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1016\/0885-064X(91)90002-F","article-title":"Condition numbers of random matrices","volume":"7","author":"Szarek Stanis\u0142aw J.","year":"1991","unstructured":"Stanis\u0142aw J. Szarek. 1991. Condition numbers of random matrices. Journal of Complexity 7, 2 (1991), 131\u2013149.","journal-title":"Journal of Complexity"},{"key":"e_1_3_3_73_1","volume-title":"Advances in Neural Information Processing Systems","author":"Talwar Kunal","year":"2019","unstructured":"Kunal Talwar. 2019. Computational separations between sampling and optimization. In Advances in Neural Information Processing Systems, H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alch\u00e9-Buc, E. Fox, and R. Garnett (Eds.), Vol. 32. Curran Associates, Inc."},{"key":"e_1_3_3_74_1","first-page":"8094","volume-title":"Advances in Neural Information Processing Systems 32","author":"Vempala Santosh S.","year":"2019","unstructured":"Santosh S. Vempala and Andre Wibisono. 2019. Rapid convergence of the unadjusted Langevin algorithm: Isoperimetry suffices. In Advances in Neural Information Processing Systems 32, H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alch\u00e9-Buc, E. Fox, and R. Garnett (Eds.). Curran Associates, Inc., 8094\u20138106."},{"key":"e_1_3_3_75_1","series-title":"Cambridge Series in Statistical and Probabilistic Mathematics","volume-title":"High-dimensional Probability","author":"Vershynin Roman","year":"2018","unstructured":"Roman Vershynin. 2018. High-dimensional Probability. Cambridge Series in Statistical and Probabilistic Mathematics, Vol. 47. Cambridge University Press, Cambridge. xiv+284 pages. An introduction with applications in data science, With a foreword by Sara van de Geer."},{"key":"e_1_3_3_76_1","first-page":"2093","volume-title":"Proceedings of the Conference on Learning Theory","author":"Wibisono Andre","year":"2018","unstructured":"Andre Wibisono. 2018. Sampling as optimization in the space of measures: The Langevin dynamics as a composite optimization problem. In Proceedings of the Conference on Learning Theory. PMLR, 2093\u20133027."},{"key":"e_1_3_3_77_1","article-title":"Proximal Langevin algorithm: Rapid convergence under isoperimetry","author":"Wibisono Andre","year":"2019","unstructured":"Andre Wibisono. 2019. Proximal Langevin algorithm: Rapid convergence under isoperimetry. arXiv:1911.01469. Retrieved from https:\/\/arxiv.org\/abs\/1911.01469","journal-title":"arXiv:1911.01469"},{"key":"e_1_3_3_78_1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"1051","DOI":"10.1007\/978-3-662-43948-7_87","volume-title":"Proceedings of the 41st International Colloquium on Automata, Languages, and Programming","volume":"8572","author":"Wimmer Karl","year":"2014","unstructured":"Karl Wimmer, Yi Wu, and Peng Zhang. 2014. Optimal query complexity for estimating the trace of a matrix. In Proceedings of the 41st International Colloquium on Automata, Languages, and Programming(Lecture Notes in Computer Science, Vol. 8572). Springer, 1051\u20131062."},{"issue":"1","key":"e_1_3_3_79_1","first-page":"1","article-title":"Sketching as a tool for numerical linear algebra","volume":"10","author":"Woodruff David P.","year":"2014","unstructured":"David P. Woodruff. 2014. Sketching as a tool for numerical linear algebra. Foundations and Trends in Theoretical Computer Science 10, 1-2 (2014), 1\u2013157.","journal-title":"Foundations and Trends in Theoretical Computer Science"},{"key":"e_1_3_3_80_1","unstructured":"Blake Woodworth and Nathan Srebro. 2017. Lower bound for randomized first order convex optimization. arXiv:1709.03594. Retrieved from https:\/\/arxiv.org\/abs\/1709.03594"},{"issue":"270","key":"e_1_3_3_81_1","first-page":"1","article-title":"Minimax mixing time of the Metropolis-adjusted Langevin algorithm for log-concave sampling","volume":"23","author":"Wu Keru","year":"2022","unstructured":"Keru Wu, Scott Schmidler, and Yuansi Chen. 2022. Minimax mixing time of the Metropolis-adjusted Langevin algorithm for log-concave sampling. Journal of Machine Learning Research 23, 270 (2022), 1\u201363.","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_3_3_82_1","series-title":"Proceedings of Machine Learning Research","first-page":"3814","volume-title":"Proceedings of the 33rd Conference on Learning Theory","volume":"125","author":"Zhang Kelvin S.","year":"2020","unstructured":"Kelvin S. Zhang, Gabriel Peyr\u00e9, Jalal Fadili, and Marcelo Pereyra. 2020. Wasserstein control of mirror Langevin Monte Carlo. In Proceedings of the 33rd Conference on Learning Theory(Proceedings of Machine Learning Research, Vol. 125), Jacob Abernethy and Shivani Agarwal (Eds.). PMLR, 3814\u20133841."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3673651","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3673651","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:06:07Z","timestamp":1750291567000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3673651"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8,8]]},"references-count":81,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,8,31]]}},"alternative-id":["10.1145\/3673651"],"URL":"https:\/\/doi.org\/10.1145\/3673651","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,8,8]]},"assertion":[{"value":"2023-12-23","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-06-11","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-08-08","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}