Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints

By Laurent Lessard, B. Recht, A. Packard. 2014

709 citations recorded by the source corpus.

This manuscript develops a new framework to analyze and design iterative optimization algorithms built on the notion of Integral Quadratic Constraints (IQC) from robust control theory. IQCs provide sufficient conditions for the stability of complicated interconnected systems, and these conditions can be checked by semidefinite programming. We discuss how to adapt IQC theory to study optimization algorithms, proving new inequalities about convex functions and providing a version of IQC theory adapted for use by optimization researchers. Using these inequalities, we derive numerical upper bounds on convergence rates for the gradient method, the heavy-ball method, Nesterov's accelerated method, and related variants by solving small, simple semidefinite programming problems. We also briefly show how these techniques can be used to search for optimization algorithms with desired performance characteristics, establishing a new methodology for algorithm design.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Numerical Analysis, Optimization & Training

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 Theory and Mathematics

In Numerical Analysis

In Optimization & Training

Citations in the corpus

Negative Momentum for Improved Game Dynamics (2018, methodology): “Among the recent works, using robust control theory, Lessard et al. (2016) studies optimization procedures from a dynamical system perspective and adopt Integral (2)Optimistic Mirror Descent (OMD), Consensus Optimization (CO) and Predictive Method (PM)”
Train faster, generalize better: Stability of stochastic gradient descent (2015, methodology): “ achieve low-training error [34,38]. However, it is not clear that momentum adds stability. Indeed, in the case of convex optimization, momentum methods are less robust to noise than gradient methods [7,23]. Thus, it is possible that momentum speeds up training but adversely impacts generalization. ”
Lookahead Optimizer: k steps forward, 1 step back (2019, methodology): “After computing the appropriate product of these matrices, we can use standard solvers to compute the eigenvalues which bound the convergence of the linear dynamical system (see e.g. Lessard et al. [19] for a recent exposition).”
YellowFin and the Art of Momentum Tuning (2017, background): “This guarantee does not generalize to arbitrary strongly convex smooth functions (Lessard et al., 2016).”
A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights (2014, methodology): “…by linearized Bregman iteration algorithm (Osher et al., 2014), a continuous-time Nesterov-like algorithm in the context of control design (D¨urr and Ebenbauer, 2012; D¨urr et al., 2012), and modeling design iterative optimization algorithms as nonlinear dynamical systems (Lessard et al., 2014).”
A General Analysis of the Convergence of ADMM (2015, positive): “Our work builds on the integral quadratic constraint framework introduced in Lessard et al. (2014), which uses ideas from robust control to analyze optimization algorithms that can be cast as discrete-time linear dynamical systems.”
Optimal Black-Box Reductions Between Optimization Objectives (2016, methodology): “Many subsequent works in this line of research also satisfy HOOD, including [3, 7, 16, 17].”
A regularization interpretation of the proximal point method for weakly convex functions (2020, methodology): “This interpretation was further studied in the quadratic case in [17] and [14] as well as [28], using linear stability analysis.”
On the Convergence of Nesterov's Accelerated Gradient Method in Stochastic Settings (2020, methodology): “Lessard et al. (2016) and Hu & Lessard (2017) frame the ag method and other popular ﬁrst-order optimization methods as linear dynamical systems with feedback and characterize their convergence rate using a control-theoretic stability framework.”
Online Adaptive Methods, Universality and Acceleration (2018, background): “And the connection between acceleration and ODEs is investigated in, [30, 32, 13, 19, 5, 4].”
On the Convergence Rate of Incremental Aggregated Gradient Algorithms (2015, background): “There has also been much interest in understanding its global convergence properties [10, 14].”
On the influence of momentum acceleration on online learning (2016, methodology): “rongly convex andhasLipschitz continuous gradients, theNesterov construction reducesto what is presented above, with a constant momentum parameter. This type of construction has also been studied in (Lessard et al., 2016; Dieuleveut et al., 2016) and applied in deep learning implementations (Sutskev”
Randomized Iterative Methods for Linear Systems: Momentum, Inexactness and Gossip (2019, background): “Heavy Ball (mGD) Polyak, 1964 [156] accelerated linear F(2,1) μ,L local Ghadimi et al, 2014 [62] sublinear F(1,1) 0,L global Ghadimi et al, 2014 [62] linear F(1,1) μ,L global Lessard et al, 2016 [103] accelerated linear F(1,1) μ,L + quadratic global, asymptotic Stochastic Heavy Ball (mSGD) Yang et a”
On Lower and Upper Bounds in Smooth and Strongly Convex Optimization (2016, background): “, Polyak (1987) and more recently Lessard et al. (2014). However, whereas previous works were primarily concerned with deriving upper bounds on the magnitude of the corresponding eigenvalues, in this work our reference point is lower bounds.”
From Local SGD to Local Fixed Point Methods for Federated Learning (2020, methodology): “Nesterov’s acceleration techniques, to a fixed point, can be established (Lessard et al., 2016).”
Accelerated Linear Convergence of Stochastic Momentum Methods in Wasserstein Distances (2019, background): “so that the asymptotic linear convergence rate in distance to the optimality becomes ρAG := 1− 2 3κ+1 , which translates into the rate (ρAG) 2 in function values that is (smaller) faster than ρAG (Lessard et al., 2016); improving the iteration complexity by a factor of 4/ √ 3 ≈ 2.”