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

Jia (Kevin) Liu, Hejian Sang, Jia Liu 0002arXiv 2018 · arXiv

Abstract

This paper presents Adaptive Stochastic Gradient Langevin Dynamics (ASGLD), a novel optimization framework designed to navigate high-dimensional non-convex landscapes. By integrating adaptive gradient scaling with Langevin noise, ASGLD achieves a nearly dimension-free saddle point escape time of $O(\log d)$. This represents a significant improvement over traditional first-order methods that scale polynomially with dimensionality, offering a scalable solution for modern deep learning optimization.

Introduction

Non-convex optimization in high-dimensional spaces is a fundamental challenge in deep learning. While finding a global minimum is often intractable, the primary hurdle for first-order methods like Stochastic Gradient Descent (SGD) is escaping saddle points—regions where the gradient vanishes but the point is not a local minimum. Existing methods like Stochastic Gradient Langevin Dynamics (SGLD) use isotropic noise to escape these traps, but they suffer from the "curse of dimensionality," where escape time grows rapidly with the number of dimensions $d$. This paper aims to reconcile efficient convergence to local minima with rapid, dimension-independent saddle point escape.

The ASGLD Framework

The proposed ASGLD framework adaptively adjusts both the search direction and the injected noise using historical gradient information. The core update rule is defined as: $$x_{k+1} = x_k - \eta D_{k-1}^{-\alpha/2} G(x_k) + \sqrt{2\eta} D_{k-1}^{-\beta/2} e_k$$ where $D_{k-1}$ is a diagonal matrix of squared historical gradients (similar to AdaGrad), and $\alpha, \beta$ are control parameters. This preconditioning allows the algorithm to incorporate the geometry of the objective function, giving frequently occurring features lower learning rates and infrequent features higher rates, effectively "stretching" the landscape to make escape directions more accessible.

Convergence rates of ASGLD across different regimes of the control parameters $\alpha$ and $\beta$.

As illustrated in the parameter regime diagram, the choice of $\alpha$ and $\beta$ allows for a tunable trade-off between convergence speed and escape capability. For instance, setting $\alpha = \beta = 1$ creates a "Balanced ASGLD" that harmonizes the magnitudes of the stochastic gradient and the injected noise.

Theoretical Results and Comparisons

The most significant theoretical contribution is the $O(\log d)$ escape time from $\gamma$-strict saddle points. This "nearly dimension-free" property is achieved by shaping the noise according to the geometry of the objective function rather than treating all directions equally.

Comparison of ASGLD variants against existing first- and second-order optimization methods.

As shown in the comparison table, ASGLD variants achieve competitive convergence rates to local minima while maintaining superior scalability in terms of dimensionality $d$. Specifically, the batch version of ASGLD (ASGLD-batch) converges in $\tilde{O}(\log d / \epsilon^2)$ iterations, outperforming previous first-order methods that scaled as $O(\log^4 d)$ or polynomially with $d$.

Experimental Validation

To verify these theoretical claims, the authors conducted simulations on synthetic non-convex objectives. These functions were designed with high variance disparity across dimensions (e.g., 0.1 vs 10) to test the efficacy of adaptive scaling. The results demonstrated that ASGLD reaches the objective's true value faster and with greater stability than traditional SGLD, which struggled with convergence issues in these heterogeneous landscapes.

Conclusion and Future Work

ASGLD provides a robust theoretical framework for high-dimensional non-convex optimization. While the current analysis assumes Lipschitz smoothness, future work aims to extend these results to non-smooth functions, such as those involving ReLU activations. Additionally, while the $O(\log d)$ escape time is theoretically superior, large-scale empirical testing on standard deep learning benchmarks like ImageNet remains necessary to validate its practical advantage over highly tuned variants of Adam or SGD.

Summary updated

BibTeX
@misc{liu2018adaptive,
  author = {Jia (Kevin) Liu and Hejian Sang and Jia Liu},
  title = {{Adaptive Stochastic Gradient Langevin Dynamics: Taming Convergence and Saddle Point Escape Time}},
  year = {2018},
  eprint = {1805.09416},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1805.09416},
}
Figure