Thu, 3-Feb-2022 / 4:00pm / Packard 101
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.
This is joint work with Mathieu Even, Francis Bach, Nicolas Flammarion, Pierre Gaillard, Hadrien Hendrikx, Laurent Massoulié and Adrien Taylor that obtained a NeurIPS outstanding paper award this year.
Raphael Berthier is a postdoc at EPFL, working with Emmanuel Abbe and Andrea Montanari. He earned his PhD last year, at Inria Paris, under the supervision of Francis Bach and Pierre Gaillard. His research studies the dynamics of (stochastic) optimization algorithms and of gossip algorithms.
Packard Building
Electrical Engineering Department
350 Jane Stanford Way
Stanford, CA 94305-9515
Thursdays, 4pm, Packard 202
