# Online Convex Optimization and Integral Quadratic Constraints: An automated approach to regret analysis

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 29 references that are in the map.
- First posted on arXiv 30 Mar 2025.

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

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints](https://mlsanity.com/paper/1408.3595/) (2014)
- [Online Optimization : Competing with Dynamic Comparators](https://mlsanity.com/paper/1501.06225/) (2015)
- [Dynamic Regret of Convex and Smooth Functions](https://mlsanity.com/paper/2007.03479/) (2020)
- [Online Optimal Control with Linear Dynamics and Predictions: Algorithms and Regret Analysis](https://mlsanity.com/paper/1906.11378/) (2019)
- [Improved Analysis for Dynamic Regret of Strongly Convex and Smooth Functions](https://mlsanity.com/paper/2006.05876/) (2020)
- [Gradient-Variation Online Learning under Generalized Smoothness](https://mlsanity.com/paper/2408.09074/) (2024)
- [Online Primal-Dual Methods with Measurement Feedback for Time-Varying Convex Optimization](https://mlsanity.com/paper/1804.05159/) (2018)
- [Automated tight Lyapunov analysis for first-order methods](https://mlsanity.com/paper/2302.06713/) (2023)
- [On the Regret of H∞ Control](https://mlsanity.com/paper/2203.16237/) (2022)
- [Robust and structure exploiting optimization algorithms: An integral quadratic constraint approach](https://mlsanity.com/paper/1905.00279/) (2019)
- [Convex Synthesis of Accelerated Gradient Algorithms](https://mlsanity.com/paper/2102.06520/) (2021)
- [An online convex optimization algorithm for controlling linear systems with state and input constraints](https://mlsanity.com/paper/2005.11308/) (2020)
- [On the Guarantees of Minimizing Regret in Receding Horizon](https://mlsanity.com/paper/2306.14561/) (2023)
- [Robust Regret Optimal Control](https://mlsanity.com/paper/2307.14297/) (2023)
- [Exponential Convergence Bounds using Integral Quadratic Constraints](https://mlsanity.com/paper/1503.07222/) (2015)
- [A Linear Parameter-Varying Framework for the Analysis of Time-Varying Optimization Algorithms](https://mlsanity.com/paper/2501.07461/) (2025)

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

- [Several Performance Bounds on Decentralized Online Optimization are Highly Conservative and Potentially Misleading](https://mlsanity.com/paper/2509.06466/) (2025)

## Abstract (arXiv)

We propose a novel approach for analyzing dynamic regret of first-order constrained online convex optimization algorithms for strongly convex and Lipschitz-smooth objectives. Crucially, we provide a general analysis that is applicable to a wide range of first-order algorithms that can be expressed as an interconnection of a linear dynamical system in feedback with a first-order oracle. By leveraging Integral Quadratic Constraints (IQCs), we derive a semi-definite program which, when feasible, provides a regret guarantee for the online algorithm. For this, the concept of variational IQCs is introduced as the generalization of IQCs to time-varying monotone operators. Our bounds capture the temporal rate of change of the problem in the form of the path length of the time-varying minimizer and the objective function variation. In contrast to standard results in OCO, our results do not require nerither the assumption of gradient boundedness, nor that of a bounded feasible set. Numerical analyses showcase the ability of the approach to capture the dependence of the regret on the function class condition number.