Breaking Reversibility Accelerates Langevin Dynamics for Non-Convex Optimization

Xuefeng Gao, Mert Gürbüzbalaban, Lingjiong ZhuNeurIPS 2020 · OpenReview

In the realm of non-convex optimization—the mathematical engine powering deep learning—practitioners constantly face a dual challenge: finding a local minimum quickly and eventually escaping it to discover better, potentially global, solutions. Standard Langevin Dynamics (LD) has long been a foundational tool for this task, but it suffers from a hidden "speed limit" imposed by its inherent mathematical symmetry.

In this NeurIPS 2020 paper, researchers from the Chinese University of Hong Kong, Rutgers, and Florida State University demonstrate that by deliberately "breaking" the time-reversibility of these algorithms, we can achieve significant acceleration in both locating and exploring local minima.

The Problem: Reversibility and Metastability

When optimizing a non-convex function, such as a neural network's loss landscape, algorithms frequently get trapped in local minima. Langevin Dynamics addresses this by injecting Gaussian noise into standard gradient descent, transforming it into a stochastic process capable of "jumping" out of sub-optimal valleys.

However, standard LD is reversible. In physical terms, if you recorded the particles moving under these dynamics and played the tape backward, the statistical behavior would be indistinguishable from the forward trajectory. While mathematically elegant, this symmetry is practically inefficient. It leads to a phenomenon known as "metastability," where the algorithm spends an agonizingly long time (the recurrence time) just to find the neighborhood of a local minimum, and an exponentially longer time (the escape time) to leave it. The algorithm effectively wastes time retracing its own steps.

Methodology: Breaking Symmetry

To overcome this bottleneck, the authors analyze two specific non-reversible variants of Langevin Dynamics:

  1. Underdamped Langevin Dynamics (ULD): This variant introduces a "velocity" or momentum term to the position updates, resulting in a second-order differential equation. Because the particle now possesses inertia, it does not merely follow the steepest gradient; it retains a "memory" of its trajectory, which inherently breaks time-reversibility.
  2. Langevin Dynamics with Non-Symmetric Drift (NLD): This version maintains the first-order structure of standard LD but adds an anti-symmetric matrix ($J$) to the gradient. If the gradient pulls the optimization process down a hill, the $J$ term adds a "curl" or lateral step to that pull. This keeps the algorithm searching the target area while preventing it from being reversible.

By utilizing a technique called linearization—analyzing how these algorithms behave in the immediate, bowl-like vicinity of a local minimum—the researchers were able to calculate the exact recurrence times needed to reach these minima.

Key Theoretical Insights

The Square Root Speedup

The most profound theoretical breakthrough in the paper involves the algorithm's dependency on the Hessian matrix. The smallest eigenvalue of the Hessian ($m$) represents the flattest, most difficult direction of a local minimum.

Standard LD has a recurrence time proportional to $O(1/m)$. The authors prove that ULD improves this recurrence time to $O(1/\sqrt{m})$. In deep learning landscapes, where $m$ is often near zero (indicating very flat valleys), transitioning from a linear to a square-root dependency represents a massive practical acceleration.

Faster Escapes

Using the Eyring-Kramers formula, the paper demonstrates that non-reversible dynamics significantly reduce the "mean exit time." By adding a curl (NLD) or momentum (ULD), the algorithm is far less likely to immediately fall back into the exact same local minimum it just climbed out of.

Preserving the Target Distribution

Crucially, these modifications do not alter the "stationary distribution" of the process. This guarantees that even though the non-reversible algorithms move and explore much faster, they will still eventually converge to the same global minima as the slower, standard LD.

Empirical Validation

While primarily a theoretical paper, the authors ground their mathematical models in two key ways:

  • Double-Well Potential: Using a classic 1D non-convex function featuring two valleys separated by a saddle point, they mathematically prove that non-reversible methods exit the sub-optimal valley faster in discrete time.
  • MNIST Experiments: The authors trained a fully-connected neural network on the MNIST handwritten digit dataset to compare wall-clock performance. ULD outperformed both NLD and standard LD, confirming that the theoretical momentum advantage translates to faster training in actual neural networks.

Limitations and Future Directions

Despite the clear advantages of breaking reversibility, the paper highlights several open challenges:

  • The $J$ Matrix Overhead: For the NLD algorithm, the optimal way to break reversibility depends on knowing the Hessian of the objective function. In high-dimensional machine learning, calculating the Hessian is often more computationally expensive than the optimization itself. Discovering a computationally "cheap" yet effective way to approximate this matrix remains an open problem.
  • Discrete vs. Continuous Time: The core proofs rely on continuous-time Stochastic Differential Equations (SDEs). While the authors provide bounds for discrete-time versions, the practical gap between a smooth theoretical curve and a jumpy discrete step size can introduce algorithmic instability.
  • Complex Landscapes: The current analysis focuses heavily on behavior near a single local minimum or a simple double-well potential. Real-world neural network loss landscapes are vastly more complex, often resembling long, winding canyons. Extending this rigorous analysis to accommodate highly complex geometries is the next logical frontier for this research.

Summary updated

Abstract

Langevin 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.
BibTeX
@inproceedings{gao2020breaking,
  author = {Xuefeng Gao and Mert Gürbüzbalaban and Lingjiong Zhu},
  title = {{Breaking Reversibility Accelerates Langevin Dynamics for Non-Convex Optimization}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=DVqp4M63Lt},
}
Figure