Skip to Main content Skip to Navigation
Conference papers

A Continuized View on Nesterov Acceleration for Stochastic Gradient Descent and Randomized Gossip

Mathieu Even 1, 2 Raphaël Berthier 3 Francis Bach 3 Nicolas Flammarion 4 Pierre Gaillard 5 Hadrien Hendrikx 2, 3 Laurent Massoulié 2, 6 Adrien Taylor 3
2 DYOGENE - Dynamics of Geometric Networks
DI-ENS - Département d'informatique de l'École normale supérieure, CNRS - Centre National de la Recherche Scientifique : UMR 8548, Inria de Paris
3 SIERRA - Statistical Machine Learning and Parsimony
DI-ENS - Département d'informatique de l'École normale supérieure, CNRS - Centre National de la Recherche Scientifique, Inria de Paris
5 Thoth - Apprentissage de modèles à partir de données massives
Inria Grenoble - Rhône-Alpes, LJK - Laboratoire Jean Kuntzmann
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; and 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.
Complete list of metadata

https://hal.archives-ouvertes.fr/hal-03405165
Contributor : Mathieu Even Connect in order to contact the contributor
Submitted on : Wednesday, October 27, 2021 - 9:54:57 AM
Last modification on : Wednesday, November 17, 2021 - 12:33:30 PM

File

continuized_is_bach (6).pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-03405165, version 1

Citation

Mathieu Even, Raphaël Berthier, Francis Bach, Nicolas Flammarion, Pierre Gaillard, et al.. A Continuized View on Nesterov Acceleration for Stochastic Gradient Descent and Randomized Gossip. NeurIPS 2021 - Thirty-fifth Conference on Neural Information Processing Systems, Dec 2021, Sydney / Virtual, Australia. pp.1-32. ⟨hal-03405165⟩

Share

Metrics

Record views

56

Files downloads

39