Asynchronous Stochastic Quasi-Newton MCMC for Non-Convex Optimization

Umut Simsekli, Cagatay Yildiz, Than Huy Nguyen, Taylan Cemgil, Gael Richard
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:4674-4683, 2018.

Abstract

Recent studies have illustrated that stochastic gradient Markov Chain Monte Carlo techniques have a strong potential in non-convex optimization, where local and global convergence guarantees can be shown under certain conditions. By building up on this recent theory, in this study, we develop an asynchronous-parallel stochastic L-BFGS algorithm for non-convex optimization. The proposed algorithm is suitable for both distributed and shared-memory settings. We provide formal theoretical analysis and show that the proposed method achieves an ergodic convergence rate of ${\cal O}(1/\sqrt{N})$ ($N$ being the total number of iterations) and it can achieve a linear speedup under certain conditions. We perform several experiments on both synthetic and real datasets. The results support our theory and show that the proposed algorithm provides a significant speedup over the recently proposed synchronous distributed L-BFGS algorithm.

Cite this Paper

BibTeX
@InProceedings{pmlr-v80-simsekli18a, title = {Asynchronous Stochastic Quasi-{N}ewton {MCMC} for Non-Convex Optimization}, author = {Simsekli, Umut and Yildiz, Cagatay and Nguyen, Than Huy and Cemgil, Taylan and Richard, Gael}, booktitle = {Proceedings of the 35th International Conference on Machine Learning}, pages = {4674--4683}, year = {2018}, editor = {Dy, Jennifer and Krause, Andreas}, volume = {80}, series = {Proceedings of Machine Learning Research}, month = {10--15 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v80/simsekli18a/simsekli18a.pdf}, url = {https://proceedings.mlr.press/v80/simsekli18a.html}, abstract = {Recent studies have illustrated that stochastic gradient Markov Chain Monte Carlo techniques have a strong potential in non-convex optimization, where local and global convergence guarantees can be shown under certain conditions. By building up on this recent theory, in this study, we develop an asynchronous-parallel stochastic L-BFGS algorithm for non-convex optimization. The proposed algorithm is suitable for both distributed and shared-memory settings. We provide formal theoretical analysis and show that the proposed method achieves an ergodic convergence rate of ${\cal O}(1/\sqrt{N})$ ($N$ being the total number of iterations) and it can achieve a linear speedup under certain conditions. We perform several experiments on both synthetic and real datasets. The results support our theory and show that the proposed algorithm provides a significant speedup over the recently proposed synchronous distributed L-BFGS algorithm.} }
Endnote
%0 Conference Paper %T Asynchronous Stochastic Quasi-Newton MCMC for Non-Convex Optimization %A Umut Simsekli %A Cagatay Yildiz %A Than Huy Nguyen %A Taylan Cemgil %A Gael Richard %B Proceedings of the 35th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2018 %E Jennifer Dy %E Andreas Krause %F pmlr-v80-simsekli18a %I PMLR %P 4674--4683 %U https://proceedings.mlr.press/v80/simsekli18a.html %V 80 %X Recent studies have illustrated that stochastic gradient Markov Chain Monte Carlo techniques have a strong potential in non-convex optimization, where local and global convergence guarantees can be shown under certain conditions. By building up on this recent theory, in this study, we develop an asynchronous-parallel stochastic L-BFGS algorithm for non-convex optimization. The proposed algorithm is suitable for both distributed and shared-memory settings. We provide formal theoretical analysis and show that the proposed method achieves an ergodic convergence rate of ${\cal O}(1/\sqrt{N})$ ($N$ being the total number of iterations) and it can achieve a linear speedup under certain conditions. We perform several experiments on both synthetic and real datasets. The results support our theory and show that the proposed algorithm provides a significant speedup over the recently proposed synchronous distributed L-BFGS algorithm.
APA
Simsekli, U., Yildiz, C., Nguyen, T.H., Cemgil, T. & Richard, G.. (2018). Asynchronous Stochastic Quasi-Newton MCMC for Non-Convex Optimization. Proceedings of the 35th International Conference on Machine Learning, in Proceedings of Machine Learning Research 80:4674-4683 Available from https://proceedings.mlr.press/v80/simsekli18a.html.

Related Material