Continuized Accelerations of Deterministic and Stochastic Gradient Descents, and of Gossip Algorithms

Mathieu Even, Raphaël Berthier, Francis Bach, Nicolas Flammarion, Hadrien Hendrikx, Pierre Gaillard, Laurent Massoulié, Adrien TaylorNeurIPS 2021 · OpenReview

Nesterov’s accelerated gradient descent is a cornerstone of modern first-order optimization, yet its mathematical analysis and adaptation to decentralized settings remain notoriously complex. Presented at NeurIPS 2021, this paper introduces a novel framework called "continuized" Nesterov acceleration. By blending continuous-time differential equations with discrete-time random jumps, the authors provide a powerful new tool for accelerating stochastic gradient descent and decentralized algorithms—particularly asynchronous distributed systems like randomized gossip.

The Challenge: Discretization and Asynchrony

Standard Nesterov acceleration requires a global iteration counter. In decentralized networks where nodes act independently and asynchronously, maintaining this global "step number" is often impossible, making traditional acceleration difficult to implement.

To gain intuition and simplify analysis, researchers frequently use continuous-time limits (ODEs). However, these limits typically assume "vanishing stepsizes." When attempting to discretize these ODEs back into practical algorithms, the acceleration is often lost, or approximation errors are introduced. The optimization community has long needed a bridge that offers the analytical simplicity of continuous time without sacrificing the exactness and performance of discrete steps.

The Continuized Process

The authors overcome these hurdles through a "continuized process." Instead of taking steps at fixed intervals ($k=1, 2, 3, \dots$), the algorithm maintains two variables ($x_t, z_t$) that operate in tandem:

  1. Continuous Mixing: Between steps, the variables evolve according to a linear ordinary differential equation (ODE).
  2. Random Jumps: The variables take gradient steps at random times $T_k$, determined by a Poisson process.

Because the timing is random, stochastic calculus can be used to differentiate the expected value of the objective function. This yields simple, analytical expressions for optimal parameters (like momentum and step size) as functions of time $t$, bypassing complex recurrence relations.

Crucially, this continuous process can be discretized exactly. By observing the states of the variables only at the jump times, the result is a discrete algorithm structurally identical to Nesterov's, but utilizing randomized parameters.

Key Insights and Breakthroughs

  • The Best of Both Worlds: The framework offers the analytical elegance of continuous-time calculus without the approximation errors typically associated with discretizing ODEs.
  • A Natural Fit for Asynchrony: Because the algorithm depends on a continuous time parameter $t$ rather than a discrete counter $k$, it is perfectly suited for asynchronous systems. Nodes only need a synchronized clock, not a shared count of total network steps.
  • Statistical Condition Number: For stochastic gradients with multiplicative noise (common in least-squares problems), the authors demonstrate that acceleration depends on a "statistical condition number" ($\tilde{\kappa}$), offering a more refined analysis than previous discrete-time attempts.
  • First Accelerated Asynchronous Gossip: By framing the "gossip problem" (nodes attempting to reach a consensus average) as a stochastic optimization task, the authors provide the first rigorous proof of acceleration for asynchronous gossip algorithms.

Performance and Evaluation

As a theoretical optimization paper, the evaluation focuses on mathematical proofs, synthetic simulations, and graph topologies rather than standard machine learning datasets.

  • Theoretical Convergence: The method matches Nesterov’s optimal rates: $O(1/t^2)$ for convex functions and an exponential rate $O(\exp(-\sqrt{\mu/L}t))$ for strongly convex functions.
  • Gossip Speedup: On a line graph with $m$ nodes, standard randomized gossip converges at a rate of $O(1/m^3)$. The continuized accelerated version improves this dramatically to $O(1/m^2)$, representing a massive practical speedup for large networks.
  • Robustness: The framework is proven robust to both additive and multiplicative noise in the gradients.

Limitations and Future Work

While continuized acceleration represents a significant theoretical leap, a few limitations remain:

  • Clock Synchronization: While the method removes the need for a global iteration counter, it assumes nodes share a common continuous time $t$. In very large or high-latency systems, clock drift could pose practical challenges.
  • Quadratic Assumptions: Much of the specific analysis for multiplicative noise and gossip assumes a quadratic objective function (least squares). Extending these pure multiplicative noise results to general smooth convex functions remains an open challenge.
  • Non-Convexity: The paper focuses strictly on convex optimization. Applying continuized acceleration to the non-convex landscapes typical of deep learning is a promising, unexplored direction.

Summary updated

Abstract

We introduce the ``continuized'' Nesterov acceleration, a close variant of Nesterov acceleration whose variables are indexed by a continuous time parameter. The two variables continuously mix following a linear ordinary differential equation and take gradient steps at random times. This continuized variant benefits from the best of the continuous and the discrete frameworks: as a continuous process, one can use differential calculus to analyze convergence and obtain analytical expressions for the parameters; but a discretization of the continuized process can be computed exactly with convergence rates similar to those of Nesterov original acceleration. We show that the discretization has the same structure as Nesterov acceleration, but with random parameters. We provide continuized Nesterov acceleration under deterministic as well as stochastic gradients, with either additive or multiplicative noise. Finally, using our continuized framework and expressing the gossip averaging problem as the stochastic minimization of a certain energy function, we provide the first rigorous acceleration of asynchronous gossip algorithms.
BibTeX
@inproceedings{even2021continuized,
  author = {Mathieu Even and Raphaël Berthier and Francis Bach and Nicolas Flammarion and Hadrien Hendrikx and Pierre Gaillard and Laurent Massoulié and Adrien Taylor},
  title = {{Continuized Accelerations of Deterministic and Stochastic Gradient Descents, and of Gossip Algorithms}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=bGfDnD7xo-v},
}
Figure