Timezone: »
Spotlight
Stochastic Runge-Kutta Accelerates Langevin Monte Carlo and Beyond
Xuechen (Chen) Li · Denny Wu · Lester Mackey · Murat Erdogdu
Sampling with Markov chain Monte Carlo methods typically amounts to discretizing some continuous-time dynamics with numerical integration. In this paper, we establish the convergence rate of sampling algorithms obtained by discretizing smooth It\^o diffusions exhibiting fast $2$-Wasserstein contraction, based on local deviation properties of the integration scheme. In particular, we study a sampling algorithm constructed by discretizing the overdamped Langevin diffusion with the method of stochastic Runge-Kutta. For strongly convex potentials that are smooth up to a certain order, its iterates
converge to the target distribution in $2$-Wasserstein distance in $\tilde{\mathcal{O}}(d\epsilon^{-2/3})$ iterations. This improves upon the best-known rate for strongly log-concave sampling based on the overdamped Langevin equation using only the gradient oracle without adjustment. Additionally, we extend our analysis of stochastic Runge-Kutta methods to uniformly dissipative diffusions with possibly non-convex potentials and
show they achieve better rates compared to the Euler-Maruyama scheme on the dependence on tolerance $\epsilon$. Numerical studies show that these algorithms lead to better stability and lower asymptotic errors.
Author Information
Xuechen (Chen) Li (UToronto, Google)
Denny Wu (University of Toronto & Vector Institute)
Lester Mackey (Microsoft Research)
Murat Erdogdu (University of Toronto)
Related Events (a corresponding poster, oral, or spotlight)
-
2019 Poster: Stochastic Runge-Kutta Accelerates Langevin Monte Carlo and Beyond »
Wed. Dec 11th 01:30 -- 03:30 AM Room East Exhibition Hall B + C #162
More from the Same Authors
-
2021 Spotlight: Fractal Structure and Generalization Properties of Stochastic Optimization Algorithms »
Alexander Camuto · George Deligiannidis · Murat Erdogdu · Mert Gurbuzbalaban · Umut Simsekli · Lingjiong Zhu -
2021 : Simple Baselines Are Strong Performers for Differentially Private Natural Language Processing »
Xuechen (Chen) Li · Florian Tramer · Percy Liang · Tatsunori Hashimoto -
2021 : Bounding Wasserstein distance with couplings »
Niloy Biswas · Lester Mackey -
2021 : Learned Benchmarks for Subseasonal Forecasting »
Soukayna Mouatadid · Paulo Orenstein · Genevieve Flaspohler · Miruna Oprescu · Judah Cohen · Franklyn Wang · Sean Knight · Maria Geogdzhayeva · Sam Levang · Ernest Fraenkel · Lester Mackey -
2022 : A Finite-Particle Convergence Rate for Stein Variational Gradient Descent »
Jiaxin Shi · Lester Mackey -
2022 : Neural Networks Efficiently Learn Low-Dimensional Representations with SGD »
Alireza Mousavi-Hosseini · Sejun Park · Manuela Girotti · Ioannis Mitliagkas · Murat Erdogdu -
2022 : Adaptive Bias Correction for Improved Subseasonal Forecast »
Soukayna Mouatadid · Paulo Orenstein · Genevieve Flaspohler · Judah Cohen · Miruna Oprescu · Ernest Fraenkel · Lester Mackey -
2022 : A Closer Look at the Calibration of Differential Private Learners »
Hanlin Zhang · Xuechen (Chen) Li · Prithviraj Sen · Salim Roukos · Tatsunori Hashimoto -
2022 : Adaptive Bias Correction for Improved Subseasonal Forecast »
Soukayna Mouatadid · Paulo Orenstein · Genevieve Flaspohler · Judah Cohen · Miruna Oprescu · Ernest Fraenkel · Lester Mackey -
2022 : Targeted Separation and Convergence with Kernel Discrepancies »
Alessandro Barp · Carl-Johann Simon-Gabriel · Mark Girolami · Lester Mackey -
2023 : Self-Taught Optimizer (STOP): Recursively Self-Improving Code Generation »
Eric Zelikman · Eliana Lorch · Lester Mackey · Adam Tauman Kalai -
2023 : Do Language Models Know When They're Hallucinating References? »
Ayush Agrawal · Mirac Suzgun · Lester Mackey · Adam Tauman Kalai -
2023 : Towards Global, General-Purpose Pretrained Geographic Location Encoders »
Konstantin Klemmer · Esther Rolf · Caleb Robinson · Lester Mackey · Marc Rußwurm -
2023 : Towards Global, General-Purpose Pretrained Geographic Location Encoders »
Konstantin Klemmer · Esther Rolf · Caleb Robinson · Lester Mackey · Marc Rußwurm -
2023 Poster: Distributional Model Equivalence for Risk-Sensitive Reinforcement Learning »
Tyler Kastner · Murat Erdogdu · Amir-massoud Farahmand -
2023 Poster: Learning in the Presence of Low-dimensional Structure: A Spiked Random Matrix Perspective »
Jimmy Ba · Murat Erdogdu · Taiji Suzuki · Zhichao Wang · Denny Wu -
2023 Poster: Gradient-Based Feature Learning under Structured Data »
Alireza Mousavi-Hosseini · Denny Wu · Taiji Suzuki · Murat Erdogdu -
2023 Poster: Optimal Excess Risk Bounds for Empirical Risk Minimization on $p$-Norm Linear Regression »
Ayoub El Hanchi · Murat Erdogdu -
2023 Poster: Should I Stop or Should I Go: Early Stopping with Heterogeneous Populations »
Hammaad Adam · Fan Yin · Huibin Hu · Neil Tenenholtz · Lorin Crawford · Lester Mackey · Allison Koenecke -
2023 Poster: A Finite-Particle Convergence Rate for Stein Variational Gradient Descent »
Jiaxin Shi · Lester Mackey -
2023 Poster: Learning Rate Free Bayesian Inference in Constrained Domains »
Louis Sharrock · Lester Mackey · Christopher Nemeth -
2023 Poster: SubseasonalClimateUSA: A Dataset for Subseasonal Forecasting and Benchmarking »
Soukayna Mouatadid · Paulo Orenstein · Genevieve Flaspohler · Miruna Oprescu · Judah Cohen · Franklyn Wang · Sean Knight · Maria Geogdzhayeva · Sam Levang · Ernest Fraenkel · Lester Mackey -
2022 : Adaptive Bias Correction for Improved Subseasonal Forecast »
Soukayna Mouatadid · Paulo Orenstein · Genevieve Flaspohler · Judah Cohen · Miruna Oprescu · Ernest Fraenkel · Lester Mackey -
2022 Spotlight: Lightning Talks 1B-4 »
Andrei Atanov · Shiqi Yang · Wanshan Li · Yongchang Hao · Ziquan Liu · Jiaxin Shi · Anton Plaksin · Jiaxiang Chen · Ziqi Pan · yaxing wang · Yuxin Liu · Stepan Martyanov · Alessandro Rinaldo · Yuhao Zhou · Li Niu · Qingyuan Yang · Andrei Filatov · Yi Xu · Liqing Zhang · Lili Mou · Ruomin Huang · Teresa Yeo · kai wang · Daren Wang · Jessica Hwang · Yuanhong Xu · Qi Qian · Hu Ding · Michalis Titsias · Shangling Jui · Ajay Sohmshetty · Lester Mackey · Joost van de Weijer · Hao Li · Amir Zamir · Xiangyang Ji · Antoni Chan · Rong Jin -
2022 Spotlight: Gradient Estimation with Discrete Stein Operators »
Jiaxin Shi · Yuhao Zhou · Jessica Hwang · Michalis Titsias · Lester Mackey -
2022 Poster: When Does Differentially Private Learning Not Suffer in High Dimensions? »
Xuechen Li · Daogao Liu · Tatsunori Hashimoto · Huseyin A. Inan · Janardhan Kulkarni · Yin-Tat Lee · Abhradeep Guha Thakurta -
2022 Poster: High-dimensional Asymptotics of Feature Learning: How One Gradient Step Improves the Representation »
Jimmy Ba · Murat Erdogdu · Taiji Suzuki · Zhichao Wang · Denny Wu · Greg Yang -
2022 Poster: Two-layer neural network on infinite dimensional data: global optimization guarantee in the mean-field regime »
Naoki Nishikawa · Taiji Suzuki · Atsushi Nitanda · Denny Wu -
2022 Poster: Generalization Bounds for Stochastic Gradient Descent via Localized $\varepsilon$-Covers »
Sejun Park · Umut Simsekli · Murat Erdogdu -
2022 Poster: Gradient Estimation with Discrete Stein Operators »
Jiaxin Shi · Yuhao Zhou · Jessica Hwang · Michalis Titsias · Lester Mackey -
2021 : Invited Talk 5 Q&A »
Lester Mackey -
2021 : Your Model is Wrong (but Might Still Be Useful) »
Lester Mackey -
2021 : Simple Baselines Are Strong Performers for Differentially Private Natural Language Processing »
Xuechen (Chen) Li · Florian Tramer · Percy Liang · Tatsunori Hashimoto -
2021 : Learned Benchmarks for Subseasonal Forecasting »
Soukayna Mouatadid · Paulo Orenstein · Genevieve Flaspohler · Miruna Oprescu · Judah Cohen · Franklyn Wang · Sean Knight · Maria Geogdzhayeva · Sam Levang · Ernest Fraenkel · Lester Mackey -
2021 Poster: Heavy Tails in SGD and Compressibility of Overparametrized Neural Networks »
Melih Barsbey · Milad Sefidgaran · Murat Erdogdu · Gaël Richard · Umut Simsekli -
2021 Poster: An Analysis of Constant Step Size SGD in the Non-convex Regime: Asymptotic Normality and Bias »
Lu Yu · Krishnakumar Balasubramanian · Stanislav Volgushev · Murat Erdogdu -
2021 Poster: Particle Dual Averaging: Optimization of Mean Field Neural Network with Global Convergence Rate Analysis »
Atsushi Nitanda · Denny Wu · Taiji Suzuki -
2021 Poster: Manipulating SGD with Data Ordering Attacks »
I Shumailov · Zakhar Shumaylov · Dmitry Kazhdan · Yiren Zhao · Nicolas Papernot · Murat Erdogdu · Ross J Anderson -
2021 Poster: On Empirical Risk Minimization with Dependent and Heavy-Tailed Data »
Abhishek Roy · Krishnakumar Balasubramanian · Murat Erdogdu -
2021 Poster: Efficient and Accurate Gradients for Neural SDEs »
Patrick Kidger · James Foster · Xuechen (Chen) Li · Terry Lyons -
2021 Poster: Convergence Rates of Stochastic Gradient Descent under Infinite Noise Variance »
Hongjian Wang · Mert Gurbuzbalaban · Lingjiong Zhu · Umut Simsekli · Murat Erdogdu -
2021 Poster: Fractal Structure and Generalization Properties of Stochastic Optimization Algorithms »
Alexander Camuto · George Deligiannidis · Murat Erdogdu · Mert Gurbuzbalaban · Umut Simsekli · Lingjiong Zhu -
2020 : Poster Session 3 (gather.town) »
Denny Wu · Chengrun Yang · Tolga Ergen · sanae lotfi · Charles Guille-Escuret · Boris Ginsburg · Hanbake Lyu · Cong Xie · David Newton · Debraj Basu · Yewen Wang · James Lucas · MAOJIA LI · Lijun Ding · Jose Javier Gonzalez Ortiz · Reyhane Askari Hemmat · Zhiqi Bu · Neal Lawton · Kiran Thekumparampil · Jiaming Liang · Lindon Roberts · Jingyi Zhu · Dongruo Zhou -
2020 : Contributed talks in Session 3 (Zoom) »
Mark Schmidt · Zhan Gao · Wenjie Li · Preetum Nakkiran · Denny Wu · Chengrun Yang -
2020 : Contributed Video: When Does Preconditioning Help or Hurt Generalization?, Denny Wu »
Denny Wu -
2020 Poster: On the Optimal Weighted $\ell_2$ Regularization in Overparameterized Linear Regression »
Denny Wu · Ji Xu -
2020 Poster: Stochastic Stein Discrepancies »
Jackson Gorham · Anant Raj · Lester Mackey -
2020 Poster: On the Ergodicity, Bias and Asymptotic Normality of Randomized Midpoint Sampling Method »
Ye He · Krishnakumar Balasubramanian · Murat Erdogdu -
2020 Poster: Minimax Estimation of Conditional Moment Models »
Nishanth Dikkala · Greg Lewis · Lester Mackey · Vasilis Syrgkanis -
2020 Poster: Hausdorff Dimension, Heavy Tails, and Generalization in Neural Networks »
Umut Simsekli · Ozan Sener · George Deligiannidis · Murat Erdogdu -
2020 Poster: Cross-validation Confidence Intervals for Test Error »
Pierre Bayle · Alexandre Bayle · Lucas Janson · Lester Mackey -
2020 Spotlight: Hausdorff Dimension, Heavy Tails, and Generalization in Neural Networks »
Umut Simsekli · Ozan Sener · George Deligiannidis · Murat Erdogdu -
2019 : Lester Mackey (Microsoft Research and Stanford) »
Lester Mackey -
2019 : Climate Change: A Grand Challenge for ML »
Yoshua Bengio · Carla Gomes · Andrew Ng · Jeff Dean · Lester Mackey -
2019 Poster: Minimum Stein Discrepancy Estimators »
Alessandro Barp · Francois-Xavier Briol · Andrew Duncan · Mark Girolami · Lester Mackey -
2019 Poster: Accelerating Rescaled Gradient Descent: Fast Optimization of Smooth Functions »
Ashia Wilson · Lester Mackey · Andre Wibisono -
2018 : Poster Session I »
Aniruddh Raghu · Daniel Jarrett · Kathleen Lewis · Elias Chaibub Neto · Nicholas Mastronarde · Shazia Akbar · Chun-Hung Chao · Henghui Zhu · Seth Stafford · Luna Zhang · Jen-Tang Lu · Changhee Lee · Adityanarayanan Radhakrishnan · Fabian Falck · Liyue Shen · Daniel Neil · Yusuf Roohani · Aparna Balagopalan · Brett Marinelli · Hagai Rossman · Sven Giesselbach · Jose Javier Gonzalez Ortiz · Edward De Brouwer · Byung-Hoon Kim · Rafid Mahmood · Tzu Ming Hsu · Antonio Ribeiro · Rumi Chunara · Agni Orfanoudaki · Kristen Severson · Mingjie Mai · Sonali Parbhoo · Albert Haque · Viraj Prabhu · Di Jin · Alena Harley · Geoffroy Dubourg-Felonneau · Xiaodan Hu · Maithra Raghu · Jonathan Warrell · Nelson Johansen · Wenyuan Li · Marko Järvenpää · Satya Narayan Shukla · Sarah Tan · Vincent Fortuin · Beau Norgeot · Yi-Te Hsu · Joel H Saltz · Veronica Tozzo · Andrew Miller · Guillaume Ausset · Azin Asgarian · Francesco Paolo Casale · Antoine Neuraz · Bhanu Pratap Singh Rawat · Turgay Ayer · Xinyu Li · Mehul Motani · Nathaniel Braman · Laetitia M Shao · Adrian Dalca · Hyunkwang Lee · Emma Pierson · Sandesh Ghimire · Yuji Kawai · Owen Lahav · Anna Goldenberg · Denny Wu · Pavitra Krishnaswamy · Colin Pawlowski · Arijit Ukil · Yuhui Zhang -
2018 Poster: Random Feature Stein Discrepancies »
Jonathan Huggins · Lester Mackey -
2018 Poster: Isolating Sources of Disentanglement in Variational Autoencoders »
Tian Qi Chen · Xuechen (Chen) Li · Roger Grosse · David Duvenaud -
2018 Oral: Isolating Sources of Disentanglement in Variational Autoencoders »
Tian Qi Chen · Xuechen (Chen) Li · Roger Grosse · David Duvenaud -
2018 Poster: Global Non-convex Optimization with Discretized Diffusions »
Murat Erdogdu · Lester Mackey · Ohad Shamir -
2017 Poster: Robust Estimation of Neural Signals in Calcium Imaging »
Hakan Inan · Murat Erdogdu · Mark Schnitzer -
2017 Poster: Inference in Graphical Models via Semidefinite Programming Hierarchies »
Murat Erdogdu · Yash Deshpande · Andrea Montanari -
2016 Poster: Scaled Least Squares Estimator for GLMs in Large-Scale Problems »
Murat Erdogdu · Lee H Dicker · Mohsen Bayati -
2015 Poster: Convergence rates of sub-sampled Newton methods »
Murat Erdogdu · Andrea Montanari -
2015 Poster: Measuring Sample Quality with Stein's Method »
Jackson Gorham · Lester Mackey -
2015 Poster: Newton-Stein Method: A Second Order Method for GLMs via Stein's Lemma »
Murat Erdogdu -
2015 Spotlight: Measuring Sample Quality with Stein's Method »
Jackson Gorham · Lester Mackey -
2015 Spotlight: Newton-Stein Method: A Second Order Method for GLMs via Stein's Lemma »
Murat Erdogdu -
2014 Workshop: High-energy particle physics, machine learning, and the HiggsML data challenge (HEPML) »
Glen Cowan · Balázs Kégl · Kyle Cranmer · Gábor Melis · Tim Salimans · Vladimir Vava Gligorov · Daniel Whiteson · Lester Mackey · Wojciech Kotlowski · Roberto Díaz Morales · Pierre Baldi · Cecile Germain · David Rousseau · Isabelle Guyon · Tianqi Chen -
2013 Poster: Estimating LASSO Risk and Noise Level »
Mohsen Bayati · Murat Erdogdu · Andrea Montanari