Replica Exchange for Non-Convex Optimization
arXiv:2001.08356
Abstract
Gradient descent (GD) is known to converge quickly for convex objective functions, but it can be trapped at local minima. On the other hand, Langevin dynamics (LD) can explore the state space and find global minima, but in order to give accurate estimates, LD needs to run with a small discretization step size and weak stochastic force, which in general slow down its convergence. This paper shows that these two algorithms and their non-swapping variants. can ``collaborate" through a simple exchange mechanism, in which they swap their current positions if LD yields a lower objective function. This idea can be seen as the singular limit of the replica-exchange technique from the sampling literature. We show that this new algorithm converges to the global minimum linearly with high probability, assuming the objective function is strongly convex in a neighborhood of the unique global minimum. By replacing gradients with stochastic gradients, and adding a proper threshold to the exchange mechanism, our algorithm can also be used in online settings. We also study non-swapping variants of the algorithm, which achieve similar performance. We further verify our theoretical results through some numerical experiments and observe superior performance of the proposed algorithm over running GD or LD alone.
arXiv comment70 pages, 15 figures
References in corpus (17)
- Simulated Tempering: A New Monte Carlo Scheme
- Global Optimality of Local Search for Low Rank Matrix Recovery
- No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis
- User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient
- Likelihood-informed dimension reduction for nonlinear inverse problems
- Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysis
- Sampling Can Be Faster Than Optimization
- Underdamped Langevin MCMC: A non-asymptotic analysis
- Non-asymptotic convergence analysis for the Unadjusted Langevin Algorithm
- Escaping Saddles with Stochastic Gradients
- Poincaré and logarithmic Sobolev inequalities by decomposition of the energy landscape
- On Nonconvex Optimization for Machine Learning: Gradients, Stochasticity, and Saddle Points
- Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent
- Accelerating Nonconvex Learning via Replica Exchange Langevin Diffusion
- On Stationary-Point Hitting Time and Ergodicity of Stochastic Gradient Langevin Dynamics
- Beyond Log-concavity: Provable Guarantees for Sampling Multi-modal Distributions using Simulated Tempering Langevin Monte Carlo
- Convex Optimization with Unbounded Nonconvex Oracles using Simulated Annealing