320. A Linear Parameter-Varying framework for the analysis of time-varying optimization algorithms.
Invited abstract in session TB-8: Systematic and computer-aided analyses IV: Online & distributed gradient methods, stream Systematic and computer-aided analyses of optimization algorithms.
Tuesday, 10:30-12:30Room: B100/7007
Authors (first author is the speaker)
| 1. | Fabian Jakob
|
| Institute for Systems Theory and Automatic Control, University of Stuttgart | |
| 2. | Andrea Iannelli
|
| Universität Stuttgart |
Abstract
We present a framework to analyze general first-order optimization algorithms for time-varying convex optimization using robust control tools. We assume that the temporal variability of the objective is caused by time-varying parameters, and only past knowledge is available. We consider the case of strongly convex objective functions with Lipschitz continuous gradients. We model the first-order algorithms as discrete-time linear parameter varying (LPV) systems in feedback with a time-varying (sub)gradient. We leverage the approach of analyzing algorithms as uncertain control interconnections with integral quadratic constraints and generalize that framework to the time-varying case. We propose novel IQCs that capture the behavior of time-varying nonlinearities and leverage techniques from LPV control to establish upper bounds on the tracking error. These bounds can be computed offline by solving a semi-definite program and can be interpreted as input-to-state stability with respect to a disturbance signal related to the problem’s temporal variability. An important benefit of our analysis framework is the ability to capture how convergence rates and robustness of general first-order algorithms depend on specific properties of the problem and the parameters rate of variation, yielding for example new insights on the role of acceleration in sequential decision-making problems.
Keywords
- First-order optimization
Status: accepted
Back to the list of papers