Show simple item record

dc.contributor.author
Anagnostides, Ioannis
dc.contributor.author
Penna, Paolo
dc.date.accessioned
2020-12-18T05:39:57Z
dc.date.available
2020-12-17T20:43:27Z
dc.date.available
2020-12-18T05:39:57Z
dc.date.issued
2020-10
dc.identifier.uri
http://hdl.handle.net/20.500.11850/456977
dc.identifier.doi
10.3929/ethz-b-000456977
dc.description.abstract
In this work, we establish a frequency-domain framework for analyzing gradient-based algorithms in linear minimax optimization problems; specifically, our approach is based on the Z-transform, a powerful tool applied in Control Theory and Signal Processing in order to characterize linear discrete-time systems. We employ our framework to obtain the first tight analysis of stability of Optimistic Gradient Descent/Ascent (OGDA), a natural variant of Gradient Descent/Ascent that was shown to exhibit last-iterate convergence in bilinear games by Daskalakis et al. (ICLR 2018). Importantly, our analysis is considerably simpler and more concise than the existing ones.Moreover, building on the intuition of OGDA, we consider a general family of gradient-based algorithms that augment the memory of the optimization through multiple historical steps. We reduce the convergence – to a saddle-point – of the dynamics in bilinear games to the stability of a polynomial, for which efficient algorithmic schemes are well-established.As an immediate corollary, we obtain a broad class of algorithms – that contains OGDA asa special case – with a last-iterate convergence guarantee to the space of Nash equilibria of the game.
en_US
dc.format
application/pdf
en_US
dc.language.iso
en
en_US
dc.publisher
Cornell University
en_US
dc.rights.uri
http://rightsstatements.org/page/InC-NC/1.0/
dc.title
A Robust Framework for Analyzing Gradient-Based Dynamics in Bilinear Games
en_US
dc.type
Working Paper
dc.rights.license
In Copyright - Non-Commercial Use Permitted
ethz.journal.title
arXiv
ethz.pages.start
2010.03211
en_US
ethz.size
18 p.
en_US
ethz.identifier.arxiv
2010.03211
ethz.publication.place
Ithaca, NY
en_US
ethz.publication.status
published
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02661 - Institut für Maschinelles Lernen / Institute for Machine Learning::03659 - Buhmann, Joachim M. / Buhmann, Joachim M.
en_US
ethz.leitzahl.certified
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02661 - Institut für Maschinelles Lernen / Institute for Machine Learning::03659 - Buhmann, Joachim M. / Buhmann, Joachim M.
en_US
ethz.date.deposited
2020-12-17T20:43:53Z
ethz.source
FORM
ethz.eth
yes
en_US
ethz.availability
Open access
en_US
ethz.rosetta.installDate
2020-12-18T05:40:05Z
ethz.rosetta.lastUpdated
2021-02-15T22:41:09Z
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=A%20Robust%20Framework%20for%20Analyzing%20Gradient-Based%20Dynamics%20in%20Bilinear%20Games&rft.jtitle=arXiv&rft.date=2020-10&rft.spage=2010.03211&rft.au=Anagnostides,%20Ioannis&Penna,%20Paolo&rft.genre=preprint&
 Search print copy at ETH Library

Files in this item

Thumbnail

Publication type

Show simple item record