论文标题
最小值优化的近乎最佳算法
Near-Optimal Algorithms for Minimax Optimization
论文作者
论文摘要
本文解决了一个长期以来的开放问题，该问题与近乎最佳的一阶算法的设计有关，以平滑且强烈的convex-Concove minimax问题。使用$ \ tilde {o}（κ_ {\ Mathbf X}+κ_ {\ MathBf y}）$或$ \ tilde {O}（O}（O}（O}（\ Min \ {κ\ {κ\ {κ{κ{\ MathBf）） x} \ sqrt {κ{\ MathBf y}}，\ sqrt {κ_ {\ MathBf X}}κ\κ_ {\ MathBf y} \} \} \}）$渐变评估，其中$κ_ _ \ trement ymand ymand ymand ymand y Inverimand y Inmumend y y y y y y y y y y y y y y \ act强率和强烈的假设。这些结果与最佳现有下限$ \tildeΩ（\ sqrt {κ_ {\ Mathbf x}κ_ {\ MathBf y}}）$之间仍然存在差距。本文以$ \ tilde {o}（\ sqrt {κ_ {\ Mathbf X}κ_ {\ Mathbf y}}）$梯度复杂性提出了第一种算法。我们的算法是基于加速近端方法和最小近端步骤的加速求解器设计的。它可以很容易地扩展到强 - convex-concave，convex-concave，noncovex-strongly-concave和nonconvex-concove函数的设置。本文还提出了算法，这些算法就梯度复杂性（直到对数因素）而言，在这些设置中匹配或胜过所有现有方法。
This paper resolves a longstanding open question pertaining to the design of near-optimal first-order algorithms for smooth and strongly-convex-strongly-concave minimax problems. Current state-of-the-art first-order algorithms find an approximate Nash equilibrium using $\tilde{O}(κ_{\mathbf x}+κ_{\mathbf y})$ or $\tilde{O}(\min\{κ_{\mathbf x}\sqrt{κ_{\mathbf y}}, \sqrt{κ_{\mathbf x}}κ_{\mathbf y}\})$ gradient evaluations, where $κ_{\mathbf x}$ and $κ_{\mathbf y}$ are the condition numbers for the strong-convexity and strong-concavity assumptions. A gap still remains between these results and the best existing lower bound $\tildeΩ(\sqrt{κ_{\mathbf x}κ_{\mathbf y}})$. This paper presents the first algorithm with $\tilde{O}(\sqrt{κ_{\mathbf x}κ_{\mathbf y}})$ gradient complexity, matching the lower bound up to logarithmic factors. Our algorithm is designed based on an accelerated proximal point method and an accelerated solver for minimax proximal steps. It can be easily extended to the settings of strongly-convex-concave, convex-concave, nonconvex-strongly-concave, and nonconvex-concave functions. This paper also presents algorithms that match or outperform all existing methods in these settings in terms of gradient complexity, up to logarithmic factors.
