Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods

By Maher Nouiehed, Maziar Sanjabi, Tianjian Huang, Jason D. Lee, Meisam Razaviyayn. Neural Information Processing Systems, 2019

397 citations recorded by the source corpus.

Recent applications that arise in machine learning have surged significant interest in solving min-max saddle point games. This problem has been extensively studied in the convex-concave regime for which a global equilibrium solution can be computed efficiently. In this paper, we study the problem in the non-convex regime and show that an \varepsilon--first order stationary point of the game can be computed when one of the player's objective can be optimized to global optimality efficiently. In particular, we first consider the case where the objective of one of the players satisfies the Polyak-Łojasiewicz (PL) condition. For such a game, we show that a simple multi-step gradient descent-ascent algorithm finds an \varepsilon--first order stationary point of the problem in \widetilde{\mathcal{O}}(\varepsilon^{-2}) iterations. Then we show that our framework can also be applied to the case where the objective of the "max-player" is concave. In this case, we propose a multi-step gradient descent-ascent algorithm that finds an \varepsilon--first order stationary point of the game in \widetilde{\cal O}(\varepsilon^{-3.5}) iterations, which is the best known rate in the literature. We applied our algorithm to a fair classification problem of Fashion-MNIST dataset and observed that the proposed algorithm results in smoother training and better generalization.

Subfields: Artificial Intelligence, Management Science and Operations Research

View Paper: https://www.semanticscholar.org/paper/1015a4f67358527ffb66a8cf37ff215a88ac073f

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

Citations in the corpus

Improved OOD Generalization via Adversarial Training and Pre-training (2021, methodology): “5 in (Nouiehed et al., 2019) implies g(w,x) has L11 + L12L21 μx -Lipschitz continuous gradient with respect to w for any specific x.”
On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems (2019, methodology): “In this sense, our notion of stationarity is stronger than the notion based on ∇f in the literature (Lu et al., 2019; Nouiehed et al., 2019).”
Optimistic Dual Extrapolation for Coherent Non-monotone Variational Inequalities (2021, methodology): “Then solving (1) is equivalent to finding a first-order Nash equilibrium of the minimax problem (2) [32].”
Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms (2019, background): “Under a stronger assumption of gradient dominance, [313, 314] have shown that nested gradient descent methods converge to the stationary points of the outer-loop, i.”
On Solving Minimax Optimization Locally: A Follow-the-Ridge Approach (2019, background): “Beyond the convex-concave setting, Rafique et al. (2018); Lu et al. (2019); Lin et al. (2019); Nouiehed et al. (2019) consider nonconvexconcave problems, i.e., where f is nonconvex in x but concave in y.”
Global Convergence and Variance-Reduced Optimization for a Class of Nonconvex-Nonconcave Minimax Problems (2020, methodology): “Recently, Nouiehed et al. [2019] studied a class of minimax problems where the objective only satisﬁes a one-sided PL condition and introduced the GDmax algorithm, which takes multiple ascent steps at every iteration.”
Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization (2020, background): “This work has focused on attaining improved rates [3, 4,19,21,26,29–31,41,45,48] and/or obtaining last-iterate convergence guarantees [1,2,13–15,20,22,28,35,37,38,43].”
Tilted Empirical Risk Minimization (2020, methodology): “While minimizing the k-loss is more desirable than ERM in many applications, the k-loss (or the VaR) is non-smooth (and generally non-convex), and hence requires the use of non-smooth or difference-of-convex optimization techniques [27, 44, 45].”