Minimax Optimization with Smooth Algorithmic Adversaries

Abstract

This paper considers minimax optimization ${\min }_x{\max }_{y}f(x,y)$ in the challenging setting where $f$ can be both nonconvex in $x$ and nonconcave in $y$. Though such optimization problems arise in many machine learning paradigms including training generative adversarial networks (GANs) and adversarially robust models, many fundamental issues remain in theory, such as the absence of efficiently computable optimality notions, and cyclic or diverging behavior of existing algorithms. Our framework sprouts from the practical consideration that under a computational budget, the max-player can not fully maximize $f(x,\cdot )$ since nonconcave maximization is NP-hard in general. So, we propose a new algorithm for the min-player to play against smooth algorithms deployed by the adversary (i.e., the max-player) instead of against full maximization. Our algorithm is guaranteed to make monotonic progress (thus having no limit cycles), and to find an appropriate "stationary point" in a polynomial number of iterations. Our framework covers practical settings where the smooth algorithms deployed by the adversary are multi-step stochastic gradient ascent, and its accelerated version. We further provide complementing experiments that confirm our theoretical findings and demonstrate the effectiveness of the proposed approach in practice.

References in corpus (15)

• Which Training Methods for GANs do actually Converge?
• Unrolled Generative Adversarial Networks
• The Numerics of GANs
• Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods
• Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applications
• Generalized Inner Loop Meta-Learning
• On Finding Local Nash Equilibria (and Only Local Nash Equilibria) in Zero-Sum Games
• Stochastic subgradient method converges at the rate $O(k^{-1/4})$ on weakly convex functions
• Torchmeta: A Meta-Learning library for PyTorch
• The limits of min-max optimization algorithms: convergence to spurious non-critical sets
• Newton-type Methods for Minimax Optimization
• Simple and optimal high-probability bounds for strongly-convex stochastic gradient descent
• The Complexity of Nonconvex-Strongly-Concave Minimax Optimization
• Complexity Lower Bounds for Nonconvex-Strongly-Concave Min-Max Optimization
• A Primal-Dual Smoothing Framework for Max-Structured Non-Convex Optimization

Cited by in corpus (1)

• Nonconvex-Nonconcave Min-Max Optimization with a Small Maximization Domain