Acceleration and Averaging in Stochastic Descent Dynamics

Walid Krichene, Peter L. BartlettNeurIPS 2017 · OpenReview

Abstract

This paper provides a rigorous continuous-time framework for understanding how acceleration and stochastic noise interact in convex optimization. By formulating "Stochastic Accelerated Mirror Descent" (SAMD) as a stochastic differential equation, the authors prove that acceleration can still provide a significant speedup in the "vanishing noise" regime and establish conditions for almost sure convergence even when noise persists.

Introduction

In large-scale machine learning, we rarely have access to the "true" gradient of a loss function. Instead, we use stochastic estimates, such as those derived from mini-batches. While we have a deep understanding of how to accelerate deterministic gradient methods (e.g., Nesterov’s Acceleration), the marriage of acceleration and stochastic noise is notoriously tricky.

In discrete time, noise can easily disrupt accelerated sequences, causing them to diverge or fail to provide any benefit over simpler methods. This paper moves the conversation to continuous time. By modeling the optimization process as a Stochastic Differential Equation (SDE), the authors aim to clarify how parameters like learning rates and averaging rates should be tuned to maintain the benefits of acceleration in the presence of noise.

Methods: Stochastic Accelerated Mirror Descent

The authors introduce SAMD (Stochastic Accelerated Mirror Descent). Their approach relies on three main pillars:

  1. Averaging Formulation: Instead of the standard second-order ODE used to describe Nesterov’s method, they use a system of two coupled first-order ODEs. Here, the primal variable is a weighted average of the "mirror" trajectory, which naturally helps smooth out gradient noise.
  2. Stochastic Differential Equations (SDEs): They replace the deterministic gradient with a noisy version: $dZ(t) = -\eta(t)[\nabla f(X(t))dt + \sigma(X(t), t)dB(t)]$. This allows them to use the tools of Itô calculus to track the system's evolution.
  3. Lyapunov Analysis: To prove convergence, they define an "energy function" (a Lyapunov function) that combines the current optimality gap with a Bregman divergence term. By bounding the rate of change of this energy, they derive convergence rates.

The method is parameterized by a learning rate $\eta(t)$, an averaging rate $a(t)$, and an "inverse sensitivity" parameter $s(t)$ that scales how much the dual variable $Z(t)$ affects the primal variable $X(t)$.

Mapping between primal and dual trajectories in SAMD

Key Insights and Ideas

  • The Power of Averaging: The paper highlights that the "averaging" view of acceleration is particularly robust to noise. Because the primal variable is an integral (average) of the dual variable, high-frequency noise in the gradient is naturally dampened.
  • Acceleration in the Vanishing Noise Regime: A major finding is the proof that if the noise level $\sigma(t)$ decreases over time (e.g., by gradually increasing the mini-batch size), acceleration provides a provable speedup over standard stochastic mirror descent. Specifically, it improves the convergence rate from $O(t^{-1})$ to $O(t^{\alpha - 1/2})$ for certain noise profiles.
  • Convergence Despite Persistent Noise: Surprisingly, the authors show that you can achieve "almost sure" convergence to the minimum even if the noise is persistent (constant) or even slightly increasing over time, provided the learning rate $\eta(t)$ is decayed appropriately.
  • Sensitivity Tuning: The parameter $s(t)$ acts as a knob to control the impact of accumulated noise. By increasing $s(t)$ over time, the algorithm becomes less sensitive to the "old" noise stored in the dual variable.

Key Results

  • Almost Sure Convergence: The authors provide the first sufficient conditions for the trajectory to converge to the set of minimizers with probability 1, even when the noise volatility grows as $o(\sqrt{t})$.
  • Expected Convergence Rates: For noise that scales as $O(t^\alpha)$, they derive an expected convergence rate of $O(t^{\alpha - 1/2})$.
  • In the persistent noise regime ($\alpha = 0$), they recover the standard $O(1/\sqrt{t})$ rate.
  • In the vanishing noise regime ($\alpha < -1/2$), acceleration yields a faster rate than non-accelerated methods.
  • Sample Trajectory Rates: They provide bounds for individual sample paths, showing they converge at nearly the same rate as the expectation, up to a small logarithmic factor ($\sqrt{\log \log t}$).

Limitations and Future Work

  • Continuous vs. Discrete: The most significant limitation is that the analysis is entirely in continuous time. While this provides elegant insights, the authors acknowledge that discretizing these SDEs into actual algorithms can be difficult and doesn't always preserve the theoretical convergence rates.
  • Smoothness Assumptions: The analysis assumes the objective function $f$ is smooth (Lipschitz gradient). Extending these results to non-smooth convex functions or strongly convex functions remains an open area for future research.
  • Noise Structure: The noise is assumed to be an Itô process. Exploring how different types of noise (e.g., heavy-tailed noise common in deep learning) affect these dynamics would be a valuable next step.

Summary updated

Abstract

We formulate and study a general family of (continuous-time) stochastic dynamics for accelerated first-order minimization of smooth convex functions. Building on an averaging formulation of accelerated mirror descent, we propose a stochastic variant in which the gradient is contaminated by noise, and study the resulting stochastic differential equation. We prove a bound on the rate of change of an energy function associated with the problem, then use it to derive estimates of convergence rates of the function values (almost surely and in expectation), both for persistent and asymptotically vanishing noise. We discuss the interaction between the parameters of the dynamics (learning rate and averaging rates) and the covariation of the noise process. In particular, we show how the asymptotic rate of covariation affects the choice of parameters and, ultimately, the convergence rate.
BibTeX
@inproceedings{krichene2017acceleration,
  author = {Walid Krichene and Peter L. Bartlett},
  title = {{Acceleration and Averaging in Stochastic Descent Dynamics}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2017},
  url = {https://openreview.net/forum?id=S1bRAv-ubB},
}
Figure