Provably effective algorithms for min-max optimization




Lei, Qi

Journal Title

Journal ISSN

Volume Title



Many fundamental machine learning tasks can be formulated as min-max optimization. This motivates us to design effective and efficient first-order methods that provably converge to the global min-max points. For this purpose, this thesis focuses on designing practical algorithms for several specific machine learning tasks. We considered some different settings: unconstrained or constrained strongly-convex (strongly-)concave, constrained convex-concave, and nonconvex-concave problems. We tackle the following concrete questions by studying the above problems:

  1. Can we reformulate a single minimization problem to two-player games to help reduce the computational complexity of finding global optimal points?
  2. Can projection-free algorithms achieve last-iterate convergence for constrained min-max optimization problems with the convex-concave landscape?
  3. Can we show that stochastic gradient descent-ascent, a method commonly used in practice for GAN training, actually finds global optima and can learn a target distribution? We make progress on these questions by proposing practical algorithms with theoretical guarantees. We also present extensive empirical studies to verify the effectiveness of our proposed methods.


LCSH Subject Headings