
Open access
Date
2021Type
- Conference Paper
ETH Bibliography
yes
Altmetrics
Abstract
This paper treats the task of designing optimization algorithms as an optimal control problem. Using regret as a metric for an algorithm’s performance, we study the existence, uniqueness and consistency of regret-optimal algorithms. By providing first-order optimality conditions for the control problem, we show that regret-optimal algorithms must satisfy a specific structure in their dynamics which we show is equivalent to performing \emph{dual-preconditioned gradient descent} on the value function generated by its regret. Using these optimal dynamics, we provide bounds on their rates of convergence to solutions of convex optimization problems. Though closed-form optimal dynamics cannot be obtained in general, we present fast numerical methods for approximating them, generating optimization algorithms which directly optimize their long-term regret. These are benchmarked against commonly used optimization algorithms to demonstrate their effectiveness. Show more
Permanent link
https://doi.org/10.3929/ethz-b-000490896Publication status
publishedExternal links
Book title
Proceedings of Thirty Fourth Conference on Learning TheoryJournal / series
Proceedings of Machine Learning ResearchVolume
Pages / Article No.
Publisher
PMLREvent
Subject
Meta-Optimization; non-convex optimization; optimal control; Variational optimization; Algorithm generation; Hyperparameter optimization; convex optimization; regretOrganisational unit
03845 - Teichmann, Josef / Teichmann, Josef
Notes
Conference lecture held at the poster session on August 16, 2021More
Show all metadata
ETH Bibliography
yes
Altmetrics