论文标题
贪婪的对抗平衡：一种有效的替代非convex-nonconcave min-max优化的替代品
Greedy Adversarial Equilibrium: An Efficient Alternative to Nonconvex-Nonconcave Min-Max Optimization
论文作者
论文摘要
目标函数的最小值优化$ f：\ mathbb {r}^d \ times \ mathbb {r}^d \ rightarrow \ rightarrow \ mathbb {r} $是在对抗性环境中鲁棒性的重要模型，在许多领域的适用性，包括优化，经济学，经济学和深度学习。在许多应用程序中，$ f $可能是非convex-nonconcave，并且在计算上找到一个全局最低点可能是棘手的。有一系列的工作，寻求计算上可拖动的算法，以替代Min-Max优化模型。但是，许多替代模型都具有解决方案点，仅在$ f $的强烈假设下仅存在，例如凸度，单调性或起点的特殊属性。我们提出了一个优化模型，即$ \ varepsilon $ - 绿色对抗平衡，并表明它可以用作Min-Max优化模型的计算替代方案。粗略地，我们说一个点$（x^\ star，y^\ star）$是$ \ varepsilon $ - gredy tovery verversarial平衡，如果$ y^\ star $是$ \ varepsilon $ -appro-approximate-approximate $ for $ f（x^\ star，\ cdot）$ x^$ x^$ x^$ x^$ x^$ x^$ x^$ x^$ x^$ x^$ x^$ x^$ x^$ x^$ x^\ sater $ \ s Star $ \ s Star，函数$ \ max_z f（x，z）$的“贪婪近似”，可以使用二阶优化算法进行有效估计。我们证明了任何具有界限并具有Lipschitz Hessian的平滑函数的点。 To prove existence, we introduce an algorithm that converges from any starting point to an $\varepsilon$-greedy adversarial equilibrium in a number of evaluations of the function $f$, the max-player's gradient $\nabla_y f(x,y)$, and its Hessian $\nabla^2_y f(x,y)$, that is polynomial in the dimension $ d $，$ 1/\ varepsilon $，以及$ f $的边界及其Lipschitz常数。
Min-max optimization of an objective function $f: \mathbb{R}^d \times \mathbb{R}^d \rightarrow \mathbb{R}$ is an important model for robustness in an adversarial setting, with applications to many areas including optimization, economics, and deep learning. In many applications $f$ may be nonconvex-nonconcave, and finding a global min-max point may be computationally intractable. There is a long line of work that seeks computationally tractable algorithms for alternatives to the min-max optimization model. However, many of the alternative models have solution points which are only guaranteed to exist under strong assumptions on $f$, such as convexity, monotonicity, or special properties of the starting point. We propose an optimization model, the $\varepsilon$-greedy adversarial equilibrium, and show that it can serve as a computationally tractable alternative to the min-max optimization model. Roughly, we say that a point $(x^\star, y^\star)$ is an $\varepsilon$-greedy adversarial equilibrium if $y^\star$ is an $\varepsilon$-approximate local maximum for $f(x^\star,\cdot)$, and $x^\star$ is an $\varepsilon$-approximate local minimum for a "greedy approximation" to the function $\max_z f(x, z)$ which can be efficiently estimated using second-order optimization algorithms. We prove the existence of such a point for any smooth function which is bounded and has Lipschitz Hessian. To prove existence, we introduce an algorithm that converges from any starting point to an $\varepsilon$-greedy adversarial equilibrium in a number of evaluations of the function $f$, the max-player's gradient $\nabla_y f(x,y)$, and its Hessian $\nabla^2_y f(x,y)$, that is polynomial in the dimension $d$, $1/\varepsilon$, and the bounds on $f$ and its Lipschitz constant.
