Adaptive Stochastic Gradient Langevin Dynamics: Taming Convergence and Saddle Point Escape Time

Abstract

In this paper, we propose a new adaptive stochastic gradient Langevin dynamics (ASGLD) algorithmic framework and its two specialized versions, namely adaptive stochastic gradient (ASG) and adaptive gradient Langevin dynamics(AGLD), for non-convex optimization problems. All proposed algorithms can escape from saddle points with at most $O(\log d)$ iterations, which is nearly dimension-free. Further, we show that ASGLD and ASG converge to a local minimum with at most $O(\log d/{\epsilon }^4)$ iterations. Also, ASGLD with full gradients or ASGLD with a slowly linearly increasing batch size converge to a local minimum with iterations bounded by $O(\log d/{\epsilon }^2)$, which outperforms existing first-order methods.

arXiv comment24 pages, 13 figures

References in corpus (12)

• Adding Gradient Noise Improves Learning for Very Deep Networks
• How to Escape Saddle Points Efficiently
• Neural GPUs Learn Algorithms
• Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees
• Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysis
• Depth Creates No Bad Local Minima
• The Power of Normalization: Faster Evasion of Saddle Points
• A Hitting Time Analysis of Stochastic Gradient Langevin Dynamics
• Accelerated Methods for Non-Convex Optimization
• Global Convergence of Langevin Dynamics Based Algorithms for Nonconvex Optimization
• First-order Stochastic Algorithms for Escaping From Saddle Points in Almost Linear Time
• Deep linear neural networks with arbitrary loss: All local minima are global

Cited by in corpus (1)

• Efficiently escaping saddle points on manifolds