论文标题
第一种最佳算法，用于平滑且强烈的convex-rong-Concave minimax优化
The First Optimal Algorithm for Smooth and Strongly-Convex-Strongly-Concave Minimax Optimization
论文作者
论文摘要
在本文中，我们重新审视平滑且强烈的convex-Concave minimax优化问题。张等。 （2021）和Ibrahim等。 (2020) established the lower bound $Ω\left(\sqrt{κ_xκ_y} \log \frac{1}ε\right)$ on the number of gradient evaluations required to find an $ε$-accurate solution, where $κ_x$ and $κ_y$ are condition numbers for the strong convexity and strong concavity assumptions.但是，现有的最新方法与Lin等人的算法不匹配。 （2020）以及Wang and Li（2020）具有梯度评估复杂性$ \ Mathcal {o} \ left（\ sqrt {\ sqrt {κ_xκ_Y} \ log^3 \ frac {1}ε\ right）$和$ \ \ \ \ \ \ \ {o} （κ_xκ_Y）\ log \ frac {1}ε\ right）$。我们通过为第一个算法提供$ \ mathcal {o} \ left（\ sqrt {κ_xκ_y} \ log \ frac {1}ε\ right）$梯度评估复杂性来解决这个基本问题。我们分为三个步骤设计算法：（i）我们将原始问题重新制定为最小化的问题，这是通过点式轭函数的最小化问题； （ii）我们将近端算法的特定变体应用于完整的问题； （iii）我们使用最佳算法来计算近端算子，用于单调夹杂物中的算子规范降低。
In this paper, we revisit the smooth and strongly-convex-strongly-concave minimax optimization problem. Zhang et al. (2021) and Ibrahim et al. (2020) established the lower bound $Ω\left(\sqrt{κ_xκ_y} \log \frac{1}ε\right)$ on the number of gradient evaluations required to find an $ε$-accurate solution, where $κ_x$ and $κ_y$ are condition numbers for the strong convexity and strong concavity assumptions. However, the existing state-of-the-art methods do not match this lower bound: algorithms of Lin et al. (2020) and Wang and Li (2020) have gradient evaluation complexity $\mathcal{O}\left( \sqrt{κ_xκ_y}\log^3\frac{1}ε\right)$ and $\mathcal{O}\left( \sqrt{κ_xκ_y}\log^3 (κ_xκ_y)\log\frac{1}ε\right)$, respectively. We fix this fundamental issue by providing the first algorithm with $\mathcal{O}\left(\sqrt{κ_xκ_y}\log\frac{1}ε\right)$ gradient evaluation complexity. We design our algorithm in three steps: (i) we reformulate the original problem as a minimization problem via the pointwise conjugate function; (ii) we apply a specific variant of the proximal point algorithm to the reformulated problem; (iii) we compute the proximal operator inexactly using the optimal algorithm for operator norm reduction in monotone inclusions.
