提出新算法，显著降低求解凸凹极小极大问题的计算复杂度。
Solving Convex-Concave Problems with $\tilde{\mathcal{O}}(ε^{-4/7})$ Second-Order Oracle Complexity
- 将凸优化最优二阶方法推广至凸凹极小极大问题
- 将复杂度从 $\mathcal{O}(ε^{-2/3})$ 降至 $\tilde{\mathcal{O}}(ε^{-4/7})$
- 可作为通用加速框架，提升各类收敛算法效率
以往算法使用牛顿类方法求解凸凹极小极大问题 $\min_{x \in \mathcal{X}} \max_{y \in \mathcal{Y}} f(x,y)$ 时，需 $\mathcal{O}(ε^{-2/3})$ 次二阶信息查询。这一结果曾被认为最优，因其与最优一阶方法的自然推广一致。本文通过将最优二阶方法推广至该类问题，实现了更优的上界 $\tilde{\mathcal{O}}(ε^{-4/7})$。进一步地，将类似技术应用于懒惰海森算法，证明所提算法可视为一种二阶「Catalyst」框架（Lin et al., JMLR 2018），能加速任意全局收敛的极小极大求解算法。
原文摘要 · Abstract (English)
Previous algorithms can solve convex-concave minimax problems $\min_{x \in \mathcal{X}} \max_{y \in \mathcal{Y}} f(x,y)$ with $\mathcal{O}(ε^{-2/3})$ second-order oracle calls using Newton-type methods. This result has been speculated to be optimal because the upper bound is achieved by a natural generalization of the optimal first-order method. In this work, we show an improved upper bound of $\tilde{\mathcal{O}}(ε^{-4/7})$ by generalizing the optimal second-order method for convex optimization to solve the convex-concave minimax problem. We further apply a similar technique to lazy Hessian algorithms and show that our proposed algorithm can also be seen as a second-order ``Catalyst'' framework (Lin et al., JMLR 2018) that could accelerate any globally convergent algorithms for solving minimax problems.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。