Breaking reversibility accelerates Langevin Dynamics for non-convex optimization
Refereed conference paper presented and published in conference proceedings
Full Text
There are no full text file(s) associated with this record. |
Other information
AbstractLangevin dynamics (LD) has been proven to be a powerful technique for optimizing a non-convex objective as an efficient algorithm to find local minima while eventually visiting a global minimum on longer time-scales. LD is based on the first-order Langevin diffusion which is reversible in time. We study two variants that are based on non-reversible Langevin diffusions: the underdamped Langevin dynamics (ULD) and the Langevin dynamics with a non-symmetric drift (NLD). Adopting the techniques of Tzen et al. (2018) for LD to non-reversible diffusions, we show that for a given local minimum that is within an arbitrary distance from the initialization, with high probability, either the ULD trajectory ends up somewhere outside a small neighborhood of this local minimum within a recurrence time which depends on the smallest eigenvalue of the Hessian at the local minimum or they enter this neighborhood by the recurrence time and stay there for a potentially exponentially long escape time. The ULD algorithm improves upon the recurrence time obtained for LD in Tzen et al. (2018) with respect to the dependency on the smallest eigenvalue of the Hessian at the local minimum. Similar results and improvements are obtained for the NLD algorithm. We also show that non-reversible variants can exit the basin of attraction of a local minimum faster in discrete time when the objective has two local minima separated by a saddle point and quantify the amount of improvement. Our analysis suggests that non-reversible Langevin algorithms are more efficient to locate a local minimum as well as exploring the state space.
Acceptance Date06/12/2020
All Author(s) ListXuefeng Gao, Mert Gürbüzbalaban, Lingjiong Zhu
Name of Conference34th Conference on Neural Information Processing Systems (NeurIPS 2020)
Start Date of Conference06/12/2020
End Date of Conference12/12/2020
Place of ConferenceVancouver
Country/Region of ConferenceCanada
Proceedings TitleAdvances in Neural Information Processing Systems
Year2020
ISSN1049-5258
LanguagesEnglish-United States