Back to search

Georgia Institute of Technology

Convergence in min-max optimization

Abstract

dc:description.abstract

Min-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 × 8

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1853/62809

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Lai, Kevin A.. Convergence in min-max optimization. Doctoral thesis, Georgia Institute of Technology, 2020. http://hdl.handle.net/1853/62809