Perturbed gradient descent with occupation time

Xin Guo, Jiequn Han, Wenpin TangarXiv 2020 · OpenReview

Abstract: Motivated by the super-diffusivity of self-repelling random walk, which has roots in statistical physics, this paper develops a new perturbation mechanism for optimization algorithms. In this mechanism, perturbations are adapted to the history of states via the notion of occupation time. After integrating this mechanism into the framework of perturbed gradient descent (PGD) and perturbed accelerated gradient descent (PAGD), two new algorithms are proposed: perturbed gradient descent adapted to occupation time (PGDOT) and its accelerated version (PAGDOT). PGDOT and PAGDOT are shown to converge to second-order stationary points at least as fast as PGD and PAGD, respectively, and thus they are guaranteed to avoid getting stuck at non-degenerate saddle points. The theoretical analysis is corroborated by empirical studies in which the new algorithms consistently escape saddle points and outperform not only their counterparts, PGD and PAGD, but also other popular alternatives including stochastic gradient descent, Adam, AMSGrad, and RMSProp.

Introduction

In the world of non-convex optimization, which underpins most deep learning, Gradient Descent (GD) faces a significant hurdle: saddle points. These are regions where the gradient is zero, but the point is neither a local minimum nor a maximum. While GD is efficient in convex settings, it can get "stuck" near these saddle points for an exponentially long time, especially in high-dimensional spaces.

Existing solutions, such as Perturbed Gradient Descent (PGD), attempt to escape these traps by adding uniform random noise. However, uniform noise is "blind" to the algorithm's trajectory. If the algorithm has already spent a lot of time exploring one side of a saddle point, adding noise that pushes it back into that same region is inefficient. This paper proposes a "smarter" way to perturb the state to ensure faster exploration and escape.

Occupation-Time-Adapted Perturbations

The authors introduce a mechanism based on Occupation-Time-Adapted Perturbations, a concept borrowed from the "vertex-repelling random walk" in statistical physics. This process tends to move away from sites it has visited frequently in the past.

  1. Occupation Time ($L_t$ and $R_t$): For each dimension, the algorithm tracks how many previous iterations were spent to the "left" ($L_t$) or "right" ($R_t$) of the current position.
  2. Adaptive Perturbation: Instead of uniform noise, the algorithm uses a weighted probability. If the iterate has spent more time to the right, the perturbation is biased to push it to the left, and vice versa.
  3. New Algorithms: This mechanism is integrated into PGD and its accelerated version (PAGD) to create PGDOT and PAGDOT.
The 1D staircase function and 3D non-convex landscape illustrate the challenges of saddle points, while the loss plot shows how occupation-time methods efficiently navigate these plateaus.

Key Insights and Results

The primary innovation is applying super-diffusivity to optimization. Self-repelling walks explore space much faster ($t^{4/3}$) than simple random walks ($t$), making them ideal for finding the "exit" of a flat saddle region. The authors prove that their vertex-repelling mechanism will never get localized in a finite set of points, ensuring the algorithm keeps moving until it finds a true local minimum.

Empirically, the authors evaluated their algorithms across synthetic benchmarks (like the "staircase" function) and standard tasks like training MLPs on MNIST and CIFAR-10.

Performance comparison on a nonlinear regression task. PGDOT and PAGDOT (purple/red) escape plateaus significantly faster than standard PGD (orange) and GD (blue).

In practice, the "occupation-time" versions were consistently faster. In nonlinear regression, PGDOT escaped plateaus in roughly half the iterations required by standard PGD. Furthermore, on CIFAR-10, PGDOT and PAGDOT successfully escaped saddle regions where standard optimizers like Adam and SGD remained stuck at high loss values.

Conclusion

PGDOT and PAGDOT offer a robust and efficient alternative to standard first-order optimizers in non-convex landscapes. By leveraging the history of the optimization path, these algorithms provide an explicit direction for escaping saddle points, leading to faster convergence and greater robustness to initialization. Future work may address the memory overhead of tracking history in extremely large models and the sensitivity to new hyperparameters introduced by the occupation-time mechanism.

Summary updated

Abstract

Motivated by the super-diffusivity of self-repelling random walk, which has roots in statistical physics, this paper develops a new perturbation mechanism for optimization algorithms. In this mechanism, perturbations are adapted to the history of states via the notion of occupation time. After integrating this mechanism into the framework of perturbed gradient descent (PGD) and perturbed accelerated gradient descent (PAGD), two new algorithms are proposed: perturbed gradient descent adapted to occupation time (PGDOT) and its accelerated version (PAGDOT). PGDOT and PAGDOT are shown to converge to second-order stationary points at least as fast as PGD and PAGD, respectively, and thus they are guaranteed to avoid getting stuck at non-degenerate saddle points. The theoretical analysis is corroborated by empirical studies in which the new algorithms consistently escape saddle points and outperform not only their counterparts, PGD and PAGD, but also other popular alternatives including stochastic gradient descent, Adam, AMSGrad, and RMSProp.
BibTeX
@misc{guo2020perturbed,
  author = {Xin Guo and Jiequn Han and Wenpin Tang},
  title = {{Perturbed gradient descent with occupation time}},
  year = {2020},
  eprint = {2005.04507},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2005.04507},
}
Figure