Timezone: »
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.
Author Information
Mathieu Even (INRIA)
Raphaël Berthier (INRIA, ENS)
Francis Bach (INRIA - Ecole Normale Superieure)
Nicolas Flammarion (EPFL)
Hadrien Hendrikx (EPFL)
Pierre Gaillard (Inria)
Laurent Massoulié (Inria)
Adrien Taylor (Inria)
Related Events (a corresponding poster, oral, or spotlight)
-
2021 Poster: Continuized Accelerations of Deterministic and Stochastic Gradient Descents, and of Gossip Algorithms »
Wed. Dec 8th 08:30 -- 10:00 AM Room
More from the Same Authors
-
2021 Spotlight: Mixability made efficient: Fast online multiclass logistic regression »
Rémi Jézéquel · Pierre Gaillard · Alessandro Rudi -
2021 Spotlight: Batch Normalization Orthogonalizes Representations in Deep Random Networks »
Hadi Daneshmand · Amir Joudaki · Francis Bach -
2021 Spotlight: Sequential Algorithms for Testing Closeness of Distributions »
Aadil Oufkir · Omar Fawzi · Nicolas Flammarion · Aurélien Garivier -
2021 : RobustBench: a standardized adversarial robustness benchmark »
Francesco Croce · Maksym Andriushchenko · Vikash Sehwag · Edoardo Debenedetti · Nicolas Flammarion · Mung Chiang · Prateek Mittal · Matthias Hein -
2022 : Quadratic minimization: from conjugate gradients to an adaptive heavy-ball method with Polyak step-sizes »
Baptiste Goujaud · Adrien Taylor · Aymeric Dieuleveut -
2022 : Asynchronous speedup in decentralized optimization »
Mathieu Even · Hadrien Hendrikx · Laurent Massoulié -
2022 Poster: Asynchronous SGD Beats Minibatch SGD Under Arbitrary Delays »
Konstantin Mishchenko · Francis Bach · Mathieu Even · Blake Woodworth -
2022 Poster: Fast Stochastic Composite Minimization and an Accelerated Frank-Wolfe Algorithm under Parallelization »
Benjamin Dubois-Taine · Francis Bach · Quentin Berthet · Adrien Taylor -
2022 Poster: On Sample Optimality in Personalized Collaborative and Federated Learning »
Mathieu Even · Laurent Massoulié · Kevin Scaman -
2022 Poster: Last-Iterate Convergence of Optimistic Gradient Method for Monotone Variational Inequalities »
Eduard Gorbunov · Adrien Taylor · Gauthier Gidel -
2022 Poster: Muffliato: Peer-to-Peer Privacy Amplification for Decentralized Optimization and Averaging »
Edwige Cyffers · Mathieu Even · Aurélien Bellet · Laurent Massoulié -
2021 Test Of Time: Online Learning for Latent Dirichlet Allocation »
Matthew Hoffman · Francis Bach · David Blei -
2021 Poster: Implicit Bias of SGD for Diagonal Linear Networks: a Provable Benefit of Stochasticity »
Scott Pesme · Loucas Pillaud-Vivien · Nicolas Flammarion -
2021 Poster: Last iterate convergence of SGD for Least-Squares in the Interpolation regime. »
Aditya Vardhan Varre · Loucas Pillaud-Vivien · Nicolas Flammarion -
2021 Poster: Sequential Algorithms for Testing Closeness of Distributions »
Aadil Oufkir · Omar Fawzi · Nicolas Flammarion · Aurélien Garivier -
2021 Poster: Mixability made efficient: Fast online multiclass logistic regression »
Rémi Jézéquel · Pierre Gaillard · Alessandro Rudi -
2021 Poster: Overcoming the curse of dimensionality with Laplacian regularization in semi-supervised learning »
Vivien Cabannes · Loucas Pillaud-Vivien · Francis Bach · Alessandro Rudi -
2021 Poster: Batch Normalization Orthogonalizes Representations in Deep Random Networks »
Hadi Daneshmand · Amir Joudaki · Francis Bach -
2021 Poster: Dueling Bandits with Adversarial Sleeping »
Aadirupa Saha · Pierre Gaillard -
2020 Poster: Tight Nonparametric Convergence Rates for Stochastic Gradient Descent under the Noiseless Linear Model »
Raphaël Berthier · Francis Bach · Pierre Gaillard -
2020 Poster: Dual-Free Stochastic Decentralized Optimization with Variance Reduction »
Hadrien Hendrikx · Francis Bach · Laurent Massoulié -
2019 Poster: An Accelerated Decentralized Stochastic Proximal Algorithm for Finite Sums »
Hadrien Hendrikx · Francis Bach · Laurent Massoulié -
2019 Poster: Efficient online learning with kernels for adversarial large scale problems »
Rémi Jézéquel · Pierre Gaillard · Alessandro Rudi -
2018 Poster: Optimal Algorithms for Non-Smooth Distributed Optimization in Networks »
Kevin Scaman · Francis Bach · Sebastien Bubeck · Laurent Massoulié · Yin Tat Lee -
2018 Poster: Gen-Oja: Simple & Efficient Algorithm for Streaming Generalized Eigenvector Computation »
Kush Bhatia · Aldo Pacchiano · Nicolas Flammarion · Peter Bartlett · Michael Jordan -
2018 Poster: Efficient online algorithms for fast-rate regret bounds under sparsity »
Pierre Gaillard · Olivier Wintenberger -
2018 Oral: Optimal Algorithms for Non-Smooth Distributed Optimization in Networks »
Kevin Scaman · Francis Bach · Sebastien Bubeck · Laurent Massoulié · Yin Tat Lee -
2017 : Dynamic Safe Interruptibility for Decentralized Multi-Agent Reinforcement Learning »
Hadrien Hendrikx -
2017 Poster: Dynamic Safe Interruptibility for Decentralized Multi-Agent Reinforcement Learning »
El Mahdi El-Mhamdi · Rachid Guerraoui · Hadrien Hendrikx · Alexandre Maurer -
2017 Spotlight: Dynamic Safe Interruptibility for Decentralized Multi-Agent Reinforcement Learning »
El Mahdi El-Mhamdi · Rachid Guerraoui · Hadrien Hendrikx · Alexandre Maurer -
2015 Poster: Rethinking LDA: Moment Matching for Discrete ICA »
Anastasia Podosinnikova · Francis Bach · Simon Lacoste-Julien -
2015 Poster: Spectral Norm Regularization of Orthonormal Representations for Graph Transduction »
Rakesh Shivanna · Bibaswan K Chatterjee · Raman Sankaran · Chiranjib Bhattacharyya · Francis Bach