Greedy Adversarial Equilibrium: An Efficient Alternative to Nonconvex–Nonconcave Min-Max Optimization
Oren Mangoubi, Nisheeth K. Vishnoi · Mathematics of Operations Research · 2021
Min-max optimization of a function f from [Formula: see text] to [Formula: see text] is an important framework for modeling robustness in adversarial settings with applications to optimization, economics, and deep learning. Oftentimes, f is nonconvex–nonconcave, and finding a global min-max point is computationally intractable. There is a long line of work that seeks computationally tractable algorithms for alternatives to the min-max optimization formulation. However, many of these alternative solution concepts guarantee the existence of solution points only under strong assumptions on f, such as convexity or monotonicity of its gradient. We propose a new solution concept, the [Formula: see text]-greedy adversarial equilibrium, and show that it can serve as a computationally tractable alternative to min-max optimization. We prove the existence of such a point for any smooth bounded function with Lipschitz Hessian and give an algorithm that converges to an [Formula: see text]-greedy adversarial equilibrium in a number of evaluations of f, [Formula: see text], and [Formula: see text] that is polynomial in d, [Formula: see text], and the bounds of f and its Lipschitz constant. Funding: This work was supported by the National Science Foundation [Grant CCF-1908347]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/moor.2023.0262 .