An SDE Perspective on Stochastic Inertial Gradient Dynamics with Time-Dependent Viscosity and Geometric Damping

Rodrigo Maulen-Soto, Jalal Fadili, Hédy Attouch, Peter OchsarXiv 2024 · DOI · arXiv

TL;DR

This paper provides a rigorous mathematical framework using Stochastic Differential Equations (SDEs) to analyze accelerated optimization algorithms under noise. By incorporating both time-dependent viscosity (friction) and Hessian-driven damping (geometric friction), the authors prove that these stochastic systems can achieve fast convergence rates—matching the $O(1/t^2)$ rate of Nesterov’s acceleration—provided the gradient noise vanishes sufficiently fast over time.

What Problem Does This Paper Address?

In the quest for faster optimization, researchers often turn to "inertial" methods (like Nesterov’s Accelerated Gradient or Heavy Ball), which add a momentum term to standard gradient descent. In continuous time, these are modeled as second-order Ordinary Differential Equations (ODEs). However, real-world optimization (like training neural networks) relies on stochastic gradients, which introduce noise.

While the deterministic versions of these systems are well-studied, analyzing them in a stochastic setting is much harder. Specifically, inertial systems can oscillate wildly. To fix this, researchers use "Hessian-driven damping" to smooth out the trajectory. The challenge this paper tackles is: How do we guarantee convergence and specific speed rates when both momentum and Hessian-based smoothing are subjected to stochastic noise?

Methods

The authors model the optimization process as a Stochastic Inertial System with Implicit Hessian-driven Damping (S-ISIHD).

Key methodological components include:

  • SDE Modeling: They represent the noisy gradient as a continuous Itô martingale.
  • Implicit Damping: Because martingales are almost surely non-differentiable, the authors use an "implicit" formulation of Hessian damping. This avoids the need to take derivatives of the noise, which would be mathematically undefined.
  • Stochastic Lyapunov Analysis: The core of the proof relies on constructing "energy functions" (Lyapunov functions). By applying Itô’s formula, they show that this energy decreases over time in expectation, allowing them to derive convergence rates.
  • Reformulation: They use a first-order Hamiltonian reformulation of the second-order SDE to make the analysis of the trajectory and the objective value more tractable.

Datasets

Not discussed in the paper. This is a theoretical mathematical study focused on proving convergence guarantees and rates. No empirical experiments on specific datasets were conducted.

Key Insights and Ideas

  • The "Implicit" Necessity: In deterministic settings, you can use explicit Hessian damping. In stochastic settings, you must use the implicit form because you cannot differentiate the noise term $\sigma(t, X)dW(t)$. This paper justifies the SDE as a "better proxy" for discrete stochastic algorithms.
  • Vanishing Noise Requirement: For the system to actually reach the minimum (rather than just bouncing around it), the noise $\sigma$ must vanish as $t \to \infty$. The paper quantifies exactly how fast this noise must decay to maintain acceleration.
  • Bridging the Gap: The authors show that their continuous-time SDE is a "consistent discretization" of common stochastic algorithms. This means that any convergence rate proved for the SDE can be directly translated back to the discrete algorithms used by engineers.
  • Oscillation Control: Hessian-driven damping is shown to be a powerful tool for reducing the "high-frequency" oscillations common in inertial methods, even when the gradient input is noisy.

Key Results

The paper establishes several "fast" convergence rates for the objective function value $f(X(t)) - \min f$:

  • General Convex Case: Under specific conditions on the damping coefficients, the objective value converges at a rate of $O(1/t^2)$ in expectation. This matches the optimal rate for first-order methods in the deterministic setting.
  • Strongly Convex Case: If the objective function is strongly convex, the system achieves exponential (linear) convergence rates.
  • Almost Sure Convergence: When the Hessian damping is zero, the authors prove not just that the average error goes to zero, but that the specific trajectory converges "almost surely" to a minimizer.
  • Viscous Damping: For damping of the form $\gamma(t) = \alpha/t^r$, they establish a comprehensive complexity analysis for different values of $r \in [0, 1]$.

Limitations and Future Work

  • Vanishing Noise Assumption: The results rely on the assumption that the noise in the gradient vanishes over time. In many practical machine learning scenarios (like constant-step-size SGD), noise remains constant, leading to a "noise floor."
  • Convexity: The analysis is strictly for convex and strongly convex functions. Extending these stochastic inertial guarantees to non-convex landscapes (like deep neural networks) remains an open challenge.
  • Parameter Tuning: While the paper provides the theoretical framework, finding the "optimal" damping parameters $\gamma(t)$ and $\beta(t)$ for a specific practical problem still requires manual tuning or heuristics.

Summary updated

Abstract

Our approach is part of the close link between continuous dissipative dynamical systems and optimization algorithms. We aim to solve convex minimization problems by means of stochastic inertial differential equations which are driven by the gradient of the objective function. This will provide a general mathematical framework for analyzing fast optimization algorithms with stochastic gradient input. Our study is a natural extension of our previous work devoted to the first-order in time stochastic steepest descent. Our goal is to develop these results further by considering second-order stochastic differential equations in time, incorporating a viscous time-dependent damping and a Hessian-driven damping. To develop this program, we rely on stochastic Lyapunov analysis. Assuming a square-integrability condition on the diffusion term times a function dependant on the viscous damping, and that the Hessian-driven damping is a positive constant, our first main result shows that almost surely, there is convergence of the values, and states fast convergence of the values in expectation. Besides, in the case where the Hessian-driven damping is zero, we conclude with the fast convergence of the values in expectation and in almost sure sense, we also managed to prove almost sure weak convergence of the trajectory. We provide a comprehensive complexity analysis by establishing several new pointwise and ergodic convergence rates in expectation for the convex and strongly convex case.
BibTeX
@misc{maulensoto2024sde,
  author = {Rodrigo Maulen-Soto and Jalal Fadili and Hédy Attouch and Peter Ochs},
  title = {{An SDE Perspective on Stochastic Inertial Gradient Dynamics with Time-Dependent Viscosity and Geometric Damping}},
  year = {2024},
  eprint = {2407.04562},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2407.04562},
}
Figure