Seminar Details
2025-11-04 (14:00) : Automated algorithm analysis for time-varying optimization: tracking and regret bounds
At Euler building (room A.002)
Organized by Mathematical Engineering
Speaker :
Fabian Jakob (University of Stuttgart)
Abstract :
Time-varying optimization problems arise across many disciplines from engineering to online learning. The development of efficient algorithms can be quite impactful, as application domains include e.g. power grid systems, mobile robotics, and portfolio optimization. The performance of such algorithms is typically assessed in two ways: (1) how well they track time-varying minima, and (2) how large their accumulated suboptimality is when the objective functions are not known in advance, also known as regret. However, deriving tracking or regret guarantees is often tedious and highly problem-specific, requiring involved and ad-hoc analyses.
This talk addresses this issue. We present a novel framework for computer-aided analysis of first-order optimization algorithms for strongly convex and smooth objectives. The framework builds on casting first-order algorithms as dynamical systems and using Integral Quadratic Constraints (IQCs) for their analysis. We recap the concept of IQCs and present an extension to the time-varying setting, which allows us to model temporal variations as disturbances acting on the algorithm dynamics. Based on this, we show how tracking and regret certificates of an algorithm can be obtained as the solution of a semidefinite program and demonstrate numerically how the choice of algorithm affects the performance and sensitivity to time-variations.