Adaptive Stochastic Gradient Langevin Dynamics: Taming Convergence and Saddle Point Escape Time
This work addresses faster convergence and saddle point escape for non-convex optimization, which is incremental but improves upon prior methods with specific gains.
The authors tackled non-convex optimization by proposing adaptive stochastic gradient Langevin dynamics (ASGLD) algorithms, achieving saddle point escape in O(log d) iterations and convergence to a local minimum in O(log d/ε^4) or O(log d/ε^2) iterations, outperforming existing first-order methods.
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/ε^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/ε^2)$, which outperforms existing first-order methods.