Greedy Adversarial Equilibrium: An Efficient Alternative to Nonconvex-Nonconcave Min-Max Optimization

• 成果类型: Article; Early Access
• 署名作者: Mangoubi, Oren; Vishnoi, Nisheeth K.
• 署名单位: Worcester Polytechnic Institute; Yale University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X; 1526-5471
• DOI: 10.1287/moor.2023.0262
• 发表日期: 2025-12-22
• 关键词: min-max optimization; Nonconvex Optimization; EXPLOITING NEGATIVE CURVATURE; DIRECTIONS; complexity

摘要

Min-max optimization of a function f from Rd x Rd to R 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 epsilon-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 epsilon-greedy adversarial equilibrium in a number of evaluations of f, del y f (x, y), and del 2y f(x, y) that is polynomial in d, 1=epsilon, and the bounds off and its Lipschitz constant.