Large-scale Minimax Optimization Problems

Minimax optimization has long been an important subject in optimization with widespread applications in robust optimization, game theory, and, more recently, in reinforcement learning and Generative Adversarial Networks (GANs). The recent applications of minimax optimization often involve objective functions that are neither convex in the minimization variable nor concave in the maximization variable which makes the convergence of algorithms harder to attain. Moreover, the huge scale of these problems renders first-order methods, i.e. methods that only use the gradient information, the only class of methods that are computationally viable in practice. In this Thesis, we study first-order methods and their convergence to the solutions of nonconvex-nonconcave minimax optimization problems. We also show the properties of the minimax generalization of the Moreau Envelope in the constrained setting which, we believe, can be of independent interest in future research endeavors in this field.