Transient Growth of Accelerated Optimization Algorithms

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 nonasymptotic regimes. In this article,...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on automatic control 2023-03, Vol.68 (3), p.1823-1830
Main Authors: Mohammadi, Hesameddin, Samuelson, Samantha, Jovanovic, Mihailo R.
Format: Article
Language:English
Subjects:
Algorithms
Convergence
Convex optimization
Eigenvalues and eigenfunctions
Euclidean geometry
first-order optimization algorithms
heavy-ball method
Heuristic algorithms
integral quadratic constraints (IQCs)
Linear systems
Mathematical analysis
Nesterov’s accelerated method
nonasymptotic behavior
nonnormal matrices
Optimization
Optimization algorithms
System theory
Systems theory
Tightness
Transient analysis
transient growth
Transient response
Upper bounds
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 nonasymptotic regimes. In this article, 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 nonnormal 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 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.
ISSN:0018-9286
1558-2523
DOI:10.1109/TAC.2022.3162154