Adapting to Mixing Time in Stochastic Optimization with Markovian Data

Ron Dorfman, Kfir Yehuda Levy
Proceedings of the 39th International Conference on Machine Learning, PMLR 162:5429-5446, 2022.

Abstract

We consider stochastic optimization problems where data is drawn from a Markov chain. Existing methods for this setting crucially rely on knowing the mixing time of the chain, which in real-world applications is usually unknown. We propose the first optimization method that does not require the knowledge of the mixing time, yet obtains the optimal asymptotic convergence rate when applied to convex problems. We further show that our approach can be extended to: (i) finding stationary points in non-convex optimization with Markovian data, and (ii) obtaining better dependence on the mixing time in temporal difference (TD) learning; in both cases, our method is completely oblivious to the mixing time. Our method relies on a novel combination of multi-level Monte Carlo (MLMC) gradient estimation together with an adaptive learning method.

Cite this Paper

BibTeX
@InProceedings{pmlr-v162-dorfman22a, title = {Adapting to Mixing Time in Stochastic Optimization with {M}arkovian Data}, author = {Dorfman, Ron and Levy, Kfir Yehuda}, booktitle = {Proceedings of the 39th International Conference on Machine Learning}, pages = {5429--5446}, year = {2022}, editor = {Chaudhuri, Kamalika and Jegelka, Stefanie and Song, Le and Szepesvari, Csaba and Niu, Gang and Sabato, Sivan}, volume = {162}, series = {Proceedings of Machine Learning Research}, month = {17--23 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v162/dorfman22a/dorfman22a.pdf}, url = {https://proceedings.mlr.press/v162/dorfman22a.html}, abstract = {We consider stochastic optimization problems where data is drawn from a Markov chain. Existing methods for this setting crucially rely on knowing the mixing time of the chain, which in real-world applications is usually unknown. We propose the first optimization method that does not require the knowledge of the mixing time, yet obtains the optimal asymptotic convergence rate when applied to convex problems. We further show that our approach can be extended to: (i) finding stationary points in non-convex optimization with Markovian data, and (ii) obtaining better dependence on the mixing time in temporal difference (TD) learning; in both cases, our method is completely oblivious to the mixing time. Our method relies on a novel combination of multi-level Monte Carlo (MLMC) gradient estimation together with an adaptive learning method.} }
Endnote
%0 Conference Paper %T Adapting to Mixing Time in Stochastic Optimization with Markovian Data %A Ron Dorfman %A Kfir Yehuda Levy %B Proceedings of the 39th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2022 %E Kamalika Chaudhuri %E Stefanie Jegelka %E Le Song %E Csaba Szepesvari %E Gang Niu %E Sivan Sabato %F pmlr-v162-dorfman22a %I PMLR %P 5429--5446 %U https://proceedings.mlr.press/v162/dorfman22a.html %V 162 %X We consider stochastic optimization problems where data is drawn from a Markov chain. Existing methods for this setting crucially rely on knowing the mixing time of the chain, which in real-world applications is usually unknown. We propose the first optimization method that does not require the knowledge of the mixing time, yet obtains the optimal asymptotic convergence rate when applied to convex problems. We further show that our approach can be extended to: (i) finding stationary points in non-convex optimization with Markovian data, and (ii) obtaining better dependence on the mixing time in temporal difference (TD) learning; in both cases, our method is completely oblivious to the mixing time. Our method relies on a novel combination of multi-level Monte Carlo (MLMC) gradient estimation together with an adaptive learning method.
APA
Dorfman, R. & Levy, K.Y.. (2022). Adapting to Mixing Time in Stochastic Optimization with Markovian Data. Proceedings of the 39th International Conference on Machine Learning, in Proceedings of Machine Learning Research 162:5429-5446 Available from https://proceedings.mlr.press/v162/dorfman22a.html.

Related Material