Dimension-free convergence rates for gradient Langevin dynamics in RKHS

Boris Muzellec, Kanji Sato, Mathurin Massias, Taiji Suzuki
Proceedings of Thirty Fifth Conference on Learning Theory, PMLR 178:1356-1420, 2022.

Abstract

Gradient Langevin dynamics (GLD) and stochastic GLD (SGLD) have attracted considerable attention lately, as a way to provide convergence guarantees in a non-convex setting. However, the known rates grow exponentially with the dimension of the space under the dissipative condition. In this work, we provide a convergence analysis of GLD and SGLD when the optimization space is an infinite-dimensional Hilbert space. More precisely, we derive non-asymptotic, dimension-free convergence rates for GLD/SGLD when performing regularized non-convex optimization in a reproducing kernel Hilbert space. Amongst others, the convergence analysis relies on the properties of a stochastic differential equation, its discrete time Galerkin approximation and the geometric ergodicity of the associated Markov chains.

Cite this Paper

BibTeX
@InProceedings{pmlr-v178-muzellec22a, title = {Dimension-free convergence rates for gradient Langevin dynamics in RKHS}, author = {Muzellec, Boris and Sato, Kanji and Massias, Mathurin and Suzuki, Taiji}, booktitle = {Proceedings of Thirty Fifth Conference on Learning Theory}, pages = {1356--1420}, year = {2022}, editor = {Loh, Po-Ling and Raginsky, Maxim}, volume = {178}, series = {Proceedings of Machine Learning Research}, month = {02--05 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v178/muzellec22a/muzellec22a.pdf}, url = {https://proceedings.mlr.press/v178/muzellec22a.html}, abstract = {Gradient Langevin dynamics (GLD) and stochastic GLD (SGLD) have attracted considerable attention lately, as a way to provide convergence guarantees in a non-convex setting. However, the known rates grow exponentially with the dimension of the space under the dissipative condition. In this work, we provide a convergence analysis of GLD and SGLD when the optimization space is an infinite-dimensional Hilbert space. More precisely, we derive non-asymptotic, dimension-free convergence rates for GLD/SGLD when performing regularized non-convex optimization in a reproducing kernel Hilbert space. Amongst others, the convergence analysis relies on the properties of a stochastic differential equation, its discrete time Galerkin approximation and the geometric ergodicity of the associated Markov chains.} }
Endnote
%0 Conference Paper %T Dimension-free convergence rates for gradient Langevin dynamics in RKHS %A Boris Muzellec %A Kanji Sato %A Mathurin Massias %A Taiji Suzuki %B Proceedings of Thirty Fifth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2022 %E Po-Ling Loh %E Maxim Raginsky %F pmlr-v178-muzellec22a %I PMLR %P 1356--1420 %U https://proceedings.mlr.press/v178/muzellec22a.html %V 178 %X Gradient Langevin dynamics (GLD) and stochastic GLD (SGLD) have attracted considerable attention lately, as a way to provide convergence guarantees in a non-convex setting. However, the known rates grow exponentially with the dimension of the space under the dissipative condition. In this work, we provide a convergence analysis of GLD and SGLD when the optimization space is an infinite-dimensional Hilbert space. More precisely, we derive non-asymptotic, dimension-free convergence rates for GLD/SGLD when performing regularized non-convex optimization in a reproducing kernel Hilbert space. Amongst others, the convergence analysis relies on the properties of a stochastic differential equation, its discrete time Galerkin approximation and the geometric ergodicity of the associated Markov chains.
APA
Muzellec, B., Sato, K., Massias, M. & Suzuki, T.. (2022). Dimension-free convergence rates for gradient Langevin dynamics in RKHS. Proceedings of Thirty Fifth Conference on Learning Theory, in Proceedings of Machine Learning Research 178:1356-1420 Available from https://proceedings.mlr.press/v178/muzellec22a.html.

Related Material