# On Acceleration with Noise-Corrupted Gradients

arXiv: https://arxiv.org/abs/1805.12591 · HTML: https://mlsanity.com/paper/1805.12591/

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 May 2018.

## Built on by (most cited first, 20 of 20)

- [Stochastic Bias-Reduced Gradient Methods](https://mlsanity.com/paper/2106.09481/) (2021)
- [Reproducibility in Optimization: Theoretical Framework and Limits](https://mlsanity.com/paper/2202.04598/) (2022)
- [Distributed Learning Systems with First-order Methods](https://mlsanity.com/paper/2104.05245/) (2021)
- [Towards Noise-adaptive, Problem-adaptive (Accelerated) Stochastic Gradient Descent](https://mlsanity.com/paper/2110.11442/) (2021)
- [A Continuized View on Nesterov Acceleration for Stochastic Gradient Descent and Randomized Gossip](https://mlsanity.com/paper/2106.07644/) (2021)
- [Robust Regression Revisited: Acceleration and Improved Estimation Rates](https://mlsanity.com/paper/2106.11938/) (2021)
- [Semi-Discrete Optimal Transport: Hardness, Regularization and Numerical Solution](https://mlsanity.com/paper/2103.06263/) (2021)
- [Complementary Composite Minimization, Small Gradients in General Norms, and Applications](https://mlsanity.com/paper/2101.11041/) (2021)
- [Training Deep Neural Networks with Adaptive Momentum Inspired by the Quadratic Optimization](https://mlsanity.com/paper/2110.09057/) (2021)
- [Random-reshuffled SARAH does not need a full gradient computations](https://mlsanity.com/paper/2111.13322/) (2021)
- [Parameter-free Locally Accelerated Conditional Gradients](https://mlsanity.com/paper/2102.06806/) (2021)
- [First-Order Methods for Convex Optimization](https://mlsanity.com/paper/2101.00935/) (2021)
- [Accelerated Cyclic Coordinate Dual Averaging with Extrapolation for Composite Convex Optimization](https://mlsanity.com/paper/2303.16279/) (2023)
- [On the Identification and Optimization of Nonsmooth Superposition Operators in Semilinear Elliptic PDEs](https://mlsanity.com/paper/2306.05185/) (2023)
- [A Mirror Descent-Based Algorithm for Corruption-Tolerant Distributed Gradient Descent](https://mlsanity.com/paper/2407.14111/) (2024)
- [Tradeoffs between convergence rate and noise amplification for momentum-based accelerated optimization algorithms](https://mlsanity.com/paper/2209.11920/) (2022)
- [BSAC-CoEx: Coexistence of URLLC and Distributed Learning Services via Device Selection](https://mlsanity.com/paper/2212.11805/) (2022)
- [Optimization on a Finer Scale: Bounded Local Subgradient Variation Perspective](https://mlsanity.com/paper/2403.16317/) (2024)
- [A High-order Tuner for Accelerated Learning and Control](https://mlsanity.com/paper/2103.12868/) (2021)
- [Faster Convergence of Stochastic Accelerated Gradient Descent under Interpolation](https://mlsanity.com/paper/2404.02378/) (2024)

## Abstract (arXiv)

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.