Online Convex Optimization and Integral Quadratic Constraints: An automated approach to regret analysis
Fabian Jakob, Andrea Iannelli · 2025
Read Online Convex Optimization and Integral Quadratic Constraints: An automated approach to regret analysis by Fabian Jakob, Andrea Iannelli (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-23600.txt.
Introduction
Fabian Jakob and Andrea Iannelli published this paper in 2025. It automates the proof work behind online learning methods, which make decisions one step at a time as data stream in. The quality measure is regret: how much worse the running choices were than the best fixed choice seen in hindsight.
Their framework treats a broad family of first-order methods as a feedback loop between a linear system and a step rule. A tool from control theory, integral quadratic constraints, then converts performance questions into a computer-checkable program. When the program has a solution, a regret bound follows automatically. The bounds track how fast the best answer itself moves over time. Unlike older results, theirs need no cap on step sizes or on the size of the choice set. Numerical tests show the bounds react sensibly to problem difficulty.
Catalog record
| CREATOR | Fabian Jakob, Andrea Iannelli |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 40 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-23600
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Online Convex Optimization and Integral Quadratic Constraints: An automated approach to regret analysis Fabian Jakob, Andrea Iannelli Abstract We propose a novel approach for analyzing dynamic regret of first-order online convex optimization (OCO) 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 neither 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. I INTRODUCTION OCO ( OCO ) has emerged as a powerful framework for tackling real-time decision-making problems under uncertainty. Traditionally, the study of OCO has focused on proposing online algorithms whose performance is assessed in terms of their static or dynamic regret [ 1 , 2 ] . In recent years, this framework has raised interest in the control community both for the design of OCO-inspired controllers [ 3 ] and for using the concept of regret as a performance metric to evaluate controllers dealing with uncertainty [ 4 ] . OCO algorithms aim to make a sequence of decisions in real-time minimizing a cumulative loss function that is revealed sequentially. Several algorithms have emerged, among which first-order algorithms represent a fundamental subclass. Each algorithm comes with its individual regret guarantees and proof techniques to verify them [ 5 ] . For the particular case of strongly convex and smooth objective functions, also accelerated methods [ 6 ] and multi-step methods with regret guarantees have been proposed [ 7 ] . However, a general methodology to approach their analysis does not exist. In contrast, for static convex optimization, an automated approach to analyze first-order algorithms based on systems theory has been thoroughly investigated in the last years, see e.g. [ 8 , 9 , 10 ] and references therein. The idea is to model the first-order algorithm as a Lur’e system, i.e. an interconnection of a linear dynamical system in feedback with a first-order oracle . Integral Quadratic Constraints (IQCs) can then be leveraged to formulate analysis conditions based on Semi-Definite Programs (SDPs). Recently, this framework has also been extended to time-varying optimization [ 11 ] . Time-varying optimization and OCO are in fact inherently related [ 12 ] . In this paper, we take up tools from [ 11 ] to propose an automated approach to dynamic regret analysis for first-order algorithms in OCO. By leveraging a system theoretic view on algorithms, we model an OCO algorithm as a dynamical system interconnected with a time-varying first-order oracle. We consider strongly-convex and smooth objective functions. To handle the time-varying nature of the oracle, we leverage variational Integral Quadratic Constraints (vIQCs), which in contrast to conventional IQCs depend on different measures of temporal variation of the problem. In line with the OCO literature we obtain a bound on the dynamic regret that accounts for the path length of the time-varying optimal solution, the objective function variation, and the gradient variation . In contrast to the common analysis approaches in OCO, our proofs are algorithm-agnostic and thus, applicable to a large number of first-order algorithms . The regret upper bound depends on decision variables of the SDP, leaving the possibility to tune the bound by trading off their magnitude. We show the implicit dependence of the regret on the function class condition ratio via a numeric case study. The main contributions can be summarized as follows. We provide a general modeling framework for OCO algorithms and a new proof technique for bounding dynamic regret. Notably, our approach does neither require the typical bounded gradient assumption, nor does it require the bounded feasible set assumption with the use of vIQCs. A numerical study demonstrates the versatility of the general algorithm formulation and provides a comparative study of commonly used OCO-algorithms. We believe the strengths of this new approach consist of: weaker assumptions required for the analysis; generality; and insights provided by comparing the analysis results of different algorithms. The paper is structured as follows. We state the preliminaries in section II , introducing the notion of regret and our algorithm formulation. In section III , we introduce the IQC formulation needed to establish our regret bounds and illustrate them with numerical examples. In section IV , we derive our regret bounds as main results. We conclude the paper in section VI . Notation. Let \mathrm{vec}(v_{1},v_{2}) denote the vertical stack of the vectors v_{1},v_{2} . We denote 1_{p} a column vector of ones of length p and \mathbb{I}_{p} the index set of integers from 1 to p . We indicate by I_{d} a d\times d identity matrix. For positive definite P , we define the norm \|v\|_{P}:=\sqrt{v^{\top}Pv} . The Kronecker product between two matrices is written as A\otimes B . Let \mathrm{diag}(v) denote the diagonal matrix with the elements of a vector v and \mathrm{blkdiag}(P_{1},P_{2}) a blockdiagonal matrix of P_{1} , P_{2} . We write f(T)=\mathcal{O}(g(T)) if \lim_{T\rightarrow\infty}\frac{f(T)}{g(T)}<\infty . A linear dynamic mapping x_{t+1}=Ax_{t}+Bu_{t},\,y_{t}=Cx_{t}+Du_{t} is compactly expressed as y_{t}=Gu_{t}, G= \left[\begin{array}[]{@{\hskip 0.1em}c@{\hskip 0.1em}|@{\hskip 0.1em}c@{\hskip 0.1em}}85005pt\lx@intercol\hfil A\hfil\hskip 0.85005pt\vrule\hskip 0.85005pt&B\hfil\hskip 0.85005pt\\ \hline\cr 85005pt\lx@intercol\hfil C\hfil\hskip 0.85005pt\vrule\hskip 0.85005pt&D\hfil\hskip 0.85005pt\end{array}\right] . II Problem Setup II-A Online Convex Optimization In OCO , an algorithm sequentially selects an action x_{t}\in\mathcal{X} from a closed convex decision set \mathcal{X} at each time step t , based solely on the information available up to time t-1 . Upon choosing x_{t} , a convex objective function f_{t} is revealed, and the algorithm incurs a loss f_{t}(x_{t}) . Throughout this work we assume the objective functions f_{t} are m -strongly convex and L -smooth, and that \mathcal{X}\subseteq\mathbb{R}^{d} . The goal is to minimize the cumulative loss over T rounds, and the performance of an OCO algorithm is typically assessed in terms of regret, which represents the cumulative suboptimality w.r.t. the best possible decisions in hindsight [ 13 ] . In this work, we define the best hindsight decision as the pointwise-in-time minimizer x_{t}^{\star}=\arg\min_{x\in\mathcal{X}}f_{t}(x),\quad t\in\mathbb{N}_{+}, (1) leading to the notion of dynamic regret [ 2 ] \mathcal{R}_{T}=\sum_{t=1}^{T}f_{t}(x_{t})-\sum_{t=1}^{T}f_{t}(x_{t}^{\star}). (2) Classical analyses of OCO primarily focus on deriving upper bounds on the regret. Typically, dynamic regret bounds are characterized in terms of regularity measures, which quantify the temporal change of the problem [ 14 , 15 ] . Notable regularity measures commonly employed in the literature include the path length and squared path length, respectively defined as \mathcal{P}_{T}=\sum_{t=1}^{T}\|x_{t}^{\star}-x_{t+1}^{\star}\|,\quad\mathcal{S}_{T}=\sum_{t=1}^{T}\|x_{t}^{\star}-x_{t+1}^{\star}\|^{2}, (3) and the function and gradient variation \displaystyle\mathcal{V}_{T} \displaystyle=\sum_{t=2}^{T}\sup_{x\in\mathcal{X}}|f_{t-1}(x)-f_{t}(x)|, (4) \displaystyle{\color[rgb]{0,0,0}\mathcal{G}_{T}} \displaystyle={\color[rgb]{0,0,0}\sum_{t=2}^{T}\sup_{x\in\mathcal{X}}\|\nabla f_{t-1}(x)-\nabla f_{t}(x)\|^{2}}. (5) Table I provides a comparative overview of existing regret bounds for strongly convex and smooth objectives, alongside the bounds established in this work. TABLE I : Regret bounds for