TY - JOUR
T1 - Solving a class of non-convex min-max games using iterative first order methods
AU - Nouiehed, Maher
AU - Sanjabi, Maziar
AU - Huang, Tianjian
AU - Lee, Jason D.
AU - Razaviyayn, Meisam
N1 - Publisher Copyright:
© 2019 Neural information processing systems foundation. All rights reserved.
PY - 2019
Y1 - 2019
N2 - 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 e-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-Lojasiewicz (PL) condition. For such a game, we show that a simple multi-step gradient descent-ascent algorithm finds an e-first order stationary point of the problem in Oe(e-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 e-first order stationary point of the game in Oe(e-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.
AB - 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 e-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-Lojasiewicz (PL) condition. For such a game, we show that a simple multi-step gradient descent-ascent algorithm finds an e-first order stationary point of the problem in Oe(e-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 e-first order stationary point of the game in Oe(e-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.
UR - http://www.scopus.com/inward/record.url?scp=85087518282&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85087518282&partnerID=8YFLogxK
M3 - Conference article
AN - SCOPUS:85087518282
SN - 1049-5258
VL - 32
JO - Advances in Neural Information Processing Systems
JF - Advances in Neural Information Processing Systems
T2 - 33rd Annual Conference on Neural Information Processing Systems, NeurIPS 2019
Y2 - 8 December 2019 through 14 December 2019
ER -