Abstract
dc:description.abstractMin-max optimization is a classic problem with applications in constrained optimization, robust optimization, and game theory. This dissertation covers new convergence rate results in min-max optimization. We show that the classic fictitious play dynamic with lexicographic tiebreaking converges quickly for diagonal payoff matrices, partly answering a conjecture by Karlin from 1959. We also show that linear last-iterate convergence rates are possible for the Hamiltonian Gradient Descent algorithm for the class of “sufficiently bilinear” min-max problems. Finally, we explore higher-order methods for min-max optimization and monotone variational inequalities, showing improved iteration complexity compared to first-order methods such as Mirror Prox.
Degree
thesis:*- Level thesis:degree_level
- Doctoral
- Department dc:contributor.department
- Computer Science
- Grantor dc:publisher
- Georgia Institute of Technology
- Year dc:date.issued
- 2020
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Lai, Kevin A.
- Advisor dc:contributor.advisor
-
- Abernethy, Jacob
- Committee members dc:contributor.committeemember
-
- Cummings, Rachel
- Morgenstern, Jamie
- Pokutta, Sebastian
- Singh, Mohit
Subjects
dc:subject × 8Rights
- Language dc:language.iso
- en_US
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- http://hdl.handle.net/1853/62809