Convergence in min-max optimization

Optimization;Zero-sum game;Game theory;Fictitious play;Generative adversarial networks;Last-iterate;Min-max;Saddle point

Lai, Kevin A. ; Abernethy, Jacob Computer Science Cummings, Rachel Morgenstern, Jamie Pokutta, Sebastian Singh, Mohit ; Abernethy, Jacob

University:Georgia Institute of Technology

Department:Computer Science

关键词: Optimization;    Zero-sum game;    Game theory;    Fictitious play;    Generative adversarial networks;    Last-iterate;    Min-max;    Saddle point;   

Others  :  https://smartech.gatech.edu/bitstream/1853/62809/1/LAI-DISSERTATION-2020.pdf

美国|英语

来源: SMARTech Repository

【 摘 要 】

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.