# Analysis of Optimization Algorithms via Integral Quadratic Constraints: Nonstrongly Convex Problems

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 May 2017.

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

- [PEPit: computer-assisted worst-case analyses of first-order optimization methods in Python](https://mlsanity.com/paper/2201.04040/) (2022)
- [Wasserstein distance estimates for the distributions of numerical approximations to ergodic stochastic differential equations](https://mlsanity.com/paper/2104.12384/) (2021)
- [Lipschitz constant estimation for general neural network architectures using control tools](https://mlsanity.com/paper/2405.01125/) (2024)
- [Revisiting the Role of Euler Numerical Integration on Acceleration and Stability in Convex Optimization](https://mlsanity.com/paper/2102.11537/) (2021)
- [Data-Driven Performance Guarantees for Classical and Learned Optimizers](https://mlsanity.com/paper/2404.13831/) (2024)
- [Dissipative Gradient Descent Ascent Method: A Control Theory Inspired Algorithm for Min-max Optimization](https://mlsanity.com/paper/2403.09090/) (2024)
- [Convex Programs and Lyapunov Functions for Reinforcement Learning: A Unified Perspective on the Analysis of Value-Based Methods](https://mlsanity.com/paper/2202.06922/) (2022)
- [Randomised Splitting Methods and Stochastic Gradient Descent](https://mlsanity.com/paper/2504.04274/) (2025)
- [Transient growth of accelerated optimization algorithms](https://mlsanity.com/paper/2103.08017/) (2021)
- [On Centralized and Distributed Mirror Descent: Convergence Analysis Using Quadratic Constraints](https://mlsanity.com/paper/2105.14385/) (2021)
- [On the connections between optimization algorithms, Lyapunov functions, and differential equations: theory and insights](https://mlsanity.com/paper/2305.08658/) (2023)
- [A Variational Perspective on High-Resolution ODEs](https://mlsanity.com/paper/2311.02002/) (2023)
- [Fast symplectic integrator for Nesterov-type acceleration method](https://mlsanity.com/paper/2106.07620/) (2021)
- [Tradeoffs between convergence rate and noise amplification for momentum-based accelerated optimization algorithms](https://mlsanity.com/paper/2209.11920/) (2022)
- [On the Stability Connection Between Discrete-Time Algorithms and Their Resolution ODEs: Applications to Min-Max Optimisation](https://mlsanity.com/paper/2603.01430/) (2026)
- [Exact Formulas for Finite-Time Estimation Errors of Decentralized Temporal Difference Learning with Linear Function Approximation](https://mlsanity.com/paper/2204.09801/) (2022)
- [A Nonlocal Graph-PDE and Higher-Order Geometric Integration for Image Labeling](https://mlsanity.com/paper/2205.03991/) (2022)
- [Multilevel Geometric Optimization for Regularised Constrained Linear Inverse Problems](https://mlsanity.com/paper/2207.04934/) (2022)
- [Generalized Continuous-Time Models for Nesterov's Accelerated Gradient Methods](https://mlsanity.com/paper/2409.00913/) (2024)

## Abstract (arXiv)

In this paper, we develop a unified framework able to certify both exponential and subexponential convergence rates for a wide range of iterative first-order optimization algorithms. To this end, we construct a family of parameter-dependent nonquadratic Lyapunov functions that can generate convergence rates in addition to proving asymptotic convergence. Using Integral Quadratic Constraints (IQCs) from robust control theory, we propose a Linear Matrix Inequality (LMI) to guide the search for the parameters of the Lyapunov function in order to establish a rate bound. Based on this result, we formulate a Semidefinite Programming (SDP) whose solution yields the best convergence rate that can be certified by the class of Lyapunov functions under consideration. We illustrate the utility of our results by analyzing the gradient method, proximal algorithms and their accelerated variants for (strongly) convex problems. We also develop the continuous-time counterpart, whereby we analyze the gradient flow and the continuous-time limit of Nesterov's accelerated method.