홈 › Papers

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

2021-06-10 · Mathieu Even, Raphaël Berthier, Francis Bach, Nicolas Flammarion, Pierre Gaillard, Hadrien Hendrikx, Laurent Massoulié, Adrien Taylor

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.

📄 PDF Abstract BibTeX arXiv:2106.07644

Code (1)

adelnabli/dadao pytorch

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

2021-12-01 · NeurIPS 2021 12 · Mathieu Even, Raphaël Berthier, Francis Bach, Nicolas Flammarion 외

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 …

Continuized Acceleration for Quasar Convex Functions in Non-Convex Optimization

2023-02-15 · Jun-Kun Wang, Andre Wibisono

Quasar convexity is a condition that allows some first-order methods to efficiently minimize a function even when the optimization landscape is non-convex. Previous works develop near-optimal accelerated algorithms for m…

Accelerated Reinforcement Learning

2017-10-23 · K. Lakshmanan

Policy gradient methods are widely used in reinforcement learning algorithms to search for better policies in the parameterized policy space. They do gradient search in the policy space and are known to converge very slo…

Policy Gradient Methods reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)+2

Poor starting points in machine learning

2016-02-09 · Mark Tygert

Poor (even random) starting points for learning/training/optimization are common in machine learning. In many settings, the method of Robbins and Monro (online stochastic gradient descent) is known to be optimal for good…

BIG-bench Machine Learning

On the Convergence of Nesterov's Accelerated Gradient Method in Stochastic Settings

2020-02-27 · ICML 2020 1 · Mahmoud Assran, Michael Rabbat

We study Nesterov's accelerated gradient method with constant step-size and momentum parameters in the stochastic approximation setting (unbiased gradients with bounded variance) and the finite-sum setting (where randomn…