Provably effective algorithms for min-max optimization
Access full-text files
Date
2020-05-14
Authors
Lei, Qi
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
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:
- Can we reformulate a single minimization problem to two-player games to help reduce the computational complexity of finding global optimal points?
- Can projection-free algorithms achieve last-iterate convergence for constrained min-max optimization problems with the convex-concave landscape?
- 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.