Min-Max Optimization in Large-Scale Machine Learning: Provable Algorithms with Fast Non-asymptotic Convergence

Mingrui Liu, Iowa State

Abstract: Min-max optimization receives increasing attention in machine learning, in settings such as stochastic AUC maximization and Generative Adversarial Nets (GANs). However, the de facto optimization algorithms people usually use for solving these min-max games in practice either suffer from slow convergence rate or lack theoretical guarantees. A natural question is proposed---how to design provable algorithms with fast non-asymptotic convergence for machine learning problems with min-max formulation?

To answer this question, I will focus on the following four concrete and fundamental questions:

1. In stochastic AUC maximization with linear model, is it possible to design a provably faster algorithm than the traditional the stochastic primal-dual gradient method? 

2. In stochastic AUC maximization with deep neural network, how to design a novel algorithm with state-of-the-art convergence rate? 

3. Although adaptive gradient methods with alternate update empirically work well in training GANs, it requires expensive tuning efforts, lacks theoretical convergence guarantees and might diverge in practice. Is it possible to design adaptive gradient algorithms for training GANs with provably faster convergence than its non-adaptive counterpart? 

4. Decentralized parallel algorithms are robust to network bandwidth and latency compared with its centralized counterpart. Is it possible to train GANs in decentralized distributed manner with provable guarantees?  

In this talk, I will present my recent work to provide all positive answers to these questions.

Bio: Mingrui Liu is currently a 4th year Ph.D. candidate in the Department of Computer Science at the University of Iowa, under the supervision of Prof. Tianbao Yang. He has board interests in machine learning and has focused on several research topics, including large-scale optimization in machine learning and learning theory. His recent research focus is to design provably efficient algorithms for nonconvex min-max problems in machine learning.