On Acceleration with Noise-Corrupted Gradients

By Michael Cohen, Jelena Diakonikolas, Lorenzo Orecchia. 2018

90 citations recorded by the source corpus.

Accelerated algorithms have broad applications in large-scale optimization, due to their generality and fast convergence. However, their stability in the practical setting of noise-corrupted gradient oracles is not well-understood. This paper provides two main technical contributions: (i) a new accelerated method AGDP that generalizes Nesterov's AGD and improves on the recent method AXGD (Diakonikolas & Orecchia, 2018), and (ii) a theoretical study of accelerated algorithms under noisy and inexact gradient oracles, which is supported by numerical experiments. This study leverages the simplicity of AGDP and its analysis to clarify the interaction between noise and acceleration and to suggest modifications to the algorithm that reduce the mean and variance of the error incurred due to the gradient noise.

Subfields: Artificial Intelligence, Computational Mechanics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

Citations in the corpus

Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron (2018, background): “Recently, there has been some theoretical analysis for the use of such acceleration in the stochastic setting [7].”
Accelerated Linear Convergence of Stochastic Momentum Methods in Wasserstein Distances (2019, methodology): “Such additive gradient noise arises also naturally when gradients are estimated from noisy data (Cohen et al., 2018; Birand et al., 2013) or the true gradient is estimated from a subset of its components as in (mini-batch) stochastic gradient descent (SGD) methods and their variants.”
On the Convergence of Nesterov's Accelerated Gradient Method in Stochastic Settings (2020, background): “The lack of general convergence guarantees for existing momentum schemes, such as Polyak’s and Nesterov’s, have led many authors to develop alternative accelerated methods specifically for use with stochastic gradients (Lan, 2012; Ghadimi & Lan, 2012; 2013; Allen-Zhu, 2017; Kidambi et al., 2018; Coh”
Online Adaptive Methods, Universality and Acceleration (2018, background): “An extension of acceleration to handle stochastic feedback was developed in, (Lan, 2012; Hu et al., 2009; Xiao, 2010; Cohen et al., 2018).”