论文标题
加速的单呼叫方法，用于受约束的最低最大优化
Accelerated Single-Call Methods for Constrained Min-Max Optimization
论文作者
论文摘要
我们研究了约束最低最大优化的一阶方法。现有方法要么需要两个梯度调用，要么在每次迭代中进行两个预测，在某些应用中可能是昂贵的。 In this paper, we first show that a variant of the Optimistic Gradient (OG) method, a single-call single-projection algorithm, has $O(\frac{1}{\sqrt{T}})$ best-iterate convergence rate for inclusion problems with operators that satisfy the weak Minty variation inequality (MVI).我们的第二个结果是第一个单键单次反应算法 - 加速反射梯度（ARG）方法，它可以实现最佳的$ O（\ frac {1} {t} {t}）$ last-Ilt-Ilter-ter-Ilter-ter-et-ter-Ilt-Ilter-题收敛速率，用于满足负共共谐性的包含问题。弱MVI和负共元性都是经过充分研究的假设，并捕获了丰富的非convex非concave non-Concave Min-Max优化问题。最后，我们表明，另一种单次单次反射算法的反射梯度（RG）方法具有$ O（\ frac {1} {\ sqrt {t}}）$ last-Ilt-Ilt-Ilt-Ilt-Inter-互联网收敛速率，用于受约束的convex-conconcave min-max优化，回答了[Heish et Al，2019]的开放问题。我们的收敛速率适用于标准措施，例如切线残差和自然残留。
We study first-order methods for constrained min-max optimization. Existing methods either require two gradient calls or two projections in each iteration, which may be costly in some applications. In this paper, we first show that a variant of the Optimistic Gradient (OG) method, a single-call single-projection algorithm, has $O(\frac{1}{\sqrt{T}})$ best-iterate convergence rate for inclusion problems with operators that satisfy the weak Minty variation inequality (MVI). Our second result is the first single-call single-projection algorithm -- the Accelerated Reflected Gradient (ARG) method that achieves the optimal $O(\frac{1}{T})$ last-iterate convergence rate for inclusion problems that satisfy negative comonotonicity. Both the weak MVI and negative comonotonicity are well-studied assumptions and capture a rich set of non-convex non-concave min-max optimization problems. Finally, we show that the Reflected Gradient (RG) method, another single-call single-projection algorithm, has $O(\frac{1}{\sqrt{T}})$ last-iterate convergence rate for constrained convex-concave min-max optimization, answering an open problem of [Heish et al, 2019]. Our convergence rates hold for standard measures such as the tangent residual and the natural residual.
