Show simple item record

dc.contributor.author
Casgrain, Philippe
dc.contributor.author
Kratsios, Anastasis
dc.contributor.editor
Belkin, Mikhail
dc.contributor.editor
Kpotufe, Samory
dc.date.accessioned
2021-11-19T08:17:51Z
dc.date.available
2021-11-19T08:17:51Z
dc.date.issued
2021
dc.identifier.issn
2640-3498
dc.identifier.uri
http://hdl.handle.net/20.500.11850/516028
dc.identifier.doi
10.3929/ethz-b-000490896
dc.description.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.
en_US
dc.format
application/pdf
en_US
dc.language.iso
en
en_US
dc.publisher
PMLR
en_US
dc.rights.uri
http://rightsstatements.org/page/InC-NC/1.0/
dc.subject
Meta-Optimization
en_US
dc.subject
non-convex optimization
en_US
dc.subject
optimal control
en_US
dc.subject
Variational optimization
en_US
dc.subject
Algorithm generation
en_US
dc.subject
Hyperparameter optimization
en_US
dc.subject
convex optimization
en_US
dc.subject
regret
en_US
dc.title
Optimizing Optimizers
en_US
dc.type
Conference Paper
dc.rights.license
In Copyright - Non-Commercial Use Permitted
ethz.title.subtitle
Regret-optimal gradient descent algorithms
en_US
ethz.book.title
Proceedings of Thirty Fourth Conference on Learning Theory
en_US
ethz.journal.title
Proceedings of Machine Learning Research
ethz.journal.volume
134
en_US
ethz.pages.start
883
en_US
ethz.pages.end
926
en_US
ethz.size
44 p.
en_US
ethz.version.deposit
publishedVersion
en_US
ethz.event
34th Annual Conference on Learning Theory (COLT 2021)
en_US
ethz.event.location
Boulder, CO, USA
en_US
ethz.event.date
August 15–19, 2021
en_US
ethz.notes
Conference lecture held at the poster session on August 16, 2021
en_US
ethz.publication.place
s.l.
en_US
ethz.publication.status
published
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02000 - Dep. Mathematik / Dep. of Mathematics::02003 - Mathematik Selbständige Professuren::03845 - Teichmann, Josef / Teichmann, Josef
en_US
ethz.leitzahl.certified
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02000 - Dep. Mathematik / Dep. of Mathematics::02003 - Mathematik Selbständige Professuren::03845 - Teichmann, Josef / Teichmann, Josef
en_US
ethz.tag
meta-optimization
en_US
ethz.tag
Non-Convex Optimization
en_US
ethz.tag
Optimal Control
en_US
ethz.tag
variational optimization
en_US
ethz.tag
algorithm generation
en_US
ethz.tag
hyperparameter optimization
en_US
ethz.tag
convex optimization
en_US
ethz.tag
regret
en_US
ethz.identifier.url
https://proceedings.mlr.press/v134/casgrain21a.html
ethz.date.deposited
2021-06-23T06:52:44Z
ethz.source
FORM
ethz.eth
yes
en_US
ethz.availability
Open access
en_US
ethz.rosetta.installDate
2021-11-19T08:18:07Z
ethz.rosetta.lastUpdated
2022-03-29T16:04:26Z
ethz.rosetta.versionExported
true
dc.identifier.olduri
http://hdl.handle.net/20.500.11850/515652
dc.identifier.olduri
http://hdl.handle.net/20.500.11850/490896
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=Optimizing%20Optimizers&rft.jtitle=Proceedings%20of%20Machine%20Learning%20Research&rft.date=2021&rft.volume=134&rft.spage=883&rft.epage=926&rft.issn=2640-3498&rft.au=Casgrain,%20Philippe&Kratsios,%20Anastasis&rft.genre=proceeding&rft.btitle=Proceedings%20of%20Thirty%20Fourth%20Conference%20on%20Learning%20Theory
 Search print copy at ETH Library

Files in this item

Thumbnail

Publication type

Show simple item record