# Tradeoffs between convergence rate and noise amplification for momentum-based accelerated optimization algorithms

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 69 references that are in the map.
- First posted on arXiv 24 Sep 2022.

## Builds on (most cited first, 27 of 27)

- [Gradient-based Hyperparameter Optimization through Reversible Learning](https://mlsanity.com/paper/1502.03492/) (2015)
- [Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysis](https://mlsanity.com/paper/1702.03849/) (2017)
- [Parametric Noise Injection: Trainable Randomness to Improve Deep Neural Network Robustness against Adversarial Attack](https://mlsanity.com/paper/1811.09310/) (2018)
- [Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints](https://mlsanity.com/paper/1408.3595/) (2014)
- [A Hitting Time Analysis of Stochastic Gradient Langevin Dynamics](https://mlsanity.com/paper/1702.05575/) (2017)
- [Understanding the Role of Momentum in Stochastic Gradient Methods](https://mlsanity.com/paper/1910.13962/) (2019)
- [A Dynamical Systems Perspective on Nesterov Acceleration](https://mlsanity.com/paper/1905.07436/) (2019)
- [On the Influence of Momentum Acceleration on Online Learning](https://mlsanity.com/paper/1603.04136/) (2016)
- [Dissipativity Theory for Nesterov's Accelerated Method](https://mlsanity.com/paper/1706.04381/) (2017)
- [On Acceleration with Noise-Corrupted Gradients](https://mlsanity.com/paper/1805.12591/) (2018)
- [Analysis of Optimization Algorithms via Integral Quadratic Constraints: Nonstrongly Convex Problems](https://mlsanity.com/paper/1705.03615/) (2017)
- [A Universally Optimal Multistage Accelerated Stochastic Gradient Method](https://mlsanity.com/paper/1901.08022/) (2019)
- [Accelerated Linear Convergence of Stochastic Momentum Methods in Wasserstein Distances](https://mlsanity.com/paper/1901.07445/) (2019)
- [A Unified Algorithmic Framework for Block-Structured Optimization Involving Big Data](https://mlsanity.com/paper/1511.02746/) (2015)
- [An Accelerated Linearized Alternating Direction Method of Multipliers](https://mlsanity.com/paper/1401.6607/) (2014)
- [A Robust Accelerated Optimization Algorithm for Strongly Convex Functions](https://mlsanity.com/paper/1710.04753/) (2017)
- [Differentially Private Accelerated Optimization Algorithms](https://mlsanity.com/paper/2008.01989/) (2020)
- [On Optimal Generalizability in Parametric Learning](https://mlsanity.com/paper/1711.05323/) (2017)
- [Robust Accelerated Gradient Methods for Smooth Strongly Convex Functions](https://mlsanity.com/paper/1805.10579/) (2018)
- [Analysis of Biased Stochastic Gradient Descent Using Sequential Semidefinite Programs](https://mlsanity.com/paper/1711.00987/) (2017)
- [A Unified Analysis of Stochastic Optimization Methods Using Jump System Theory and Quadratic Constraints](https://mlsanity.com/paper/1706.08141/) (2017)
- [Robustness of accelerated first-order algorithms for strongly convex optimization problems](https://mlsanity.com/paper/1905.11011/) (2019)
- [Generalizing the optimized gradient method for smooth convex minimization](https://mlsanity.com/paper/1607.06764/) (2016)
- [An Inexact Accelerated Stochastic ADMM for Separable Convex Optimization](https://mlsanity.com/paper/2010.12765/) (2020)
- [Robust and structure exploiting optimization algorithms: An integral quadratic constraint approach](https://mlsanity.com/paper/1905.00279/) (2019)
- [The Speed-Robustness Trade-Off for First-Order Methods with Additive Gradient Noise](https://mlsanity.com/paper/2109.05059/) (2021)
- [Transient growth of accelerated optimization algorithms](https://mlsanity.com/paper/2103.08017/) (2021)

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

- [DiSK: Differentially Private Optimizer with Simplified Kalman Filter for Noise Reduction](https://mlsanity.com/paper/2410.03883/) (2024)

## Abstract (arXiv)

We study momentum-based first-order optimization algorithms in which the iterations utilize information from the two previous steps and are subject to an additive white noise. This setup uses noise to account for uncertainty in either gradient evaluation or iteration updates, and it includes Polyak's heavy-ball and Nesterov's accelerated methods as special cases. For strongly convex quadratic problems, we use the steady-state variance of the error in the optimization variable to quantify noise amplification and identify fundamental stochastic performance tradeoffs. Our approach utilizes the Jury stability criterion to provide a novel geometric characterization of conditions for linear convergence, and it reveals the relation between the noise amplification and convergence rate as well as their dependence on the condition number and the constant algorithmic parameters. This geometric insight leads to simple alternative proofs of standard convergence results and allows us to establish ``uncertainty principle'' of strongly convex optimization: for the two-step momentum method with linear convergence rate, the lower bound on the product between the settling time and noise amplification scales quadratically with the condition number. Our analysis also identifies a key difference between the gradient and iterate noise models: while the amplification of gradient noise can be made arbitrarily small by sufficiently decelerating the algorithm, the best achievable variance for the iterate noise model increases linearly with the settling time in the decelerating regime. Finally, we introduce two parameterized families of algorithms that strike a balance between noise amplification and settling time while preserving order-wise Pareto optimality for both noise models.