# Transient growth of accelerated optimization algorithms

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 40 references that are in the map.
- First posted on arXiv 14 Mar 2021.

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

- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints](https://mlsanity.com/paper/1408.3595/) (2014)
- [On the Linear Convergence of the ADMM in Decentralized Consensus Optimization](https://mlsanity.com/paper/1307.5561/) (2013)
- [Dissipativity Theory for Nesterov's Accelerated Method](https://mlsanity.com/paper/1706.04381/) (2017)
- [Analysis of Optimization Algorithms via Integral Quadratic Constraints: Nonstrongly Convex Problems](https://mlsanity.com/paper/1705.03615/) (2017)
- [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)
- [The proximal augmented Lagrangian method for nonsmooth composite optimization](https://mlsanity.com/paper/1610.04514/) (2016)
- [Robustness of accelerated first-order algorithms for strongly convex optimization problems](https://mlsanity.com/paper/1905.11011/) (2019)
- [Robust and structure exploiting optimization algorithms: An integral quadratic constraint approach](https://mlsanity.com/paper/1905.00279/) (2019)
- [From bypass transition to flow control and data-driven turbulence modeling: An input-output viewpoint](https://mlsanity.com/paper/2003.10104/) (2020)
- [Topology design for stochastically-forced consensus networks](https://mlsanity.com/paper/1506.03437/) (2015)
- [Proximal algorithms for large-scale statistical modeling and sensor/actuator selection](https://mlsanity.com/paper/1807.01739/) (2018)

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

- [A Control Theoretic Framework for Adaptive Gradient Optimizers in Machine Learning](https://mlsanity.com/paper/2206.02034/) (2022)
- [Tradeoffs between convergence rate and noise amplification for momentum-based accelerated optimization algorithms](https://mlsanity.com/paper/2209.11920/) (2022)

## Abstract (arXiv)

Optimization algorithms are increasingly being used in applications with limited time budgets. In many real-time and embedded scenarios, only a few iterations can be performed and traditional convergence metrics cannot be used to evaluate performance in these non-asymptotic regimes. In this paper, we examine the transient behavior of accelerated first-order optimization algorithms. For convex quadratic problems, we employ tools from linear systems theory to show that transient growth arises from the presence of non-normal dynamics. We identify the existence of modes that yield an algebraic growth in early iterations and quantify the transient excursion from the optimal solution caused by these modes. For strongly convex smooth optimization problems, we utilize the theory of integral quadratic constraints (IQCs) to establish an upper bound on the magnitude of the transient response of Nesterov's accelerated algorithm. We show that both the Euclidean distance between the optimization variable and the global minimizer and the rise time to the transient peak are proportional to the square root of the condition number of the problem. Finally, for problems with large condition numbers, we demonstrate tightness of the bounds that we derive up to constant factors.