Asynchronous Stochastic Quasi-Newton MCMC for Non-Convex Optimization

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 $\mathcal{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.

arXiv commentPublished in the International Conference on Machine Learning (ICML 2018)

Cited by in corpus (4)

• Global Convergence of Stochastic Gradient Hamiltonian Monte Carlo for Non-Convex Stochastic Optimization: Non-Asymptotic Performance Bounds and Momentum-Based Acceleration
• Bayesian Pose Graph Optimization via Bingham Distributions and Tempered Geodesic MCMC
• Global Convergence of Langevin Dynamics Based Algorithms for Nonconvex Optimization
• Sliced-Wasserstein Flows: Nonparametric Generative Modeling via Optimal Transport and Diffusions