通过复用海森矩阵，显著降低极小极大优化的计算成本。
Second-Order Min-Max Optimization with Lazy Hessians
- 复用海森矩阵，减少重复计算
- 计算复杂度降低约 $d^{1/3}$ 倍
- 适合大规模极小极大优化任务
本文研究凸-凹极小极大优化的二阶方法。Monteiro 和 Svaiter（2012）提出的方法在找到 $ε$-鞍点时具有最优迭代复杂度 $\mathcal{O}(ε^{-3/2})$，但其计算复杂度为 $\mathcal{O}((N+ d^2) d ε^{-2/3})$ 是否可改进尚不明确。本文沿用 Doikov 等人（2023）的设定：一阶信息获取复杂度为 $N$，二阶信息为 $dN$。我们通过跨迭代复用海森矩阵，将整体计算复杂度降至 $\tilde{\mathcal{O}}( (N+d^2)(d+ d^{2/3}ε^{-2/3}))$，相较之前方法提升 $d^{1/3}$ 倍。进一步推广至强凸-强凹情形，当问题条件数为 $κ$ 时，复杂度为 $\tilde{\mathcal{O}}((N+d^2) (d + d^{2/3} κ^{2/3}) )$，同样实现对当前最优方法的加速。真实与合成数据集上的数值实验验证了方法效率。
原文摘要 · Abstract (English)
This paper studies second-order methods for convex-concave minimax optimization. Monteiro and Svaiter (2012) proposed a method to solve the problem with an optimal iteration complexity of $\mathcal{O}(ε^{-3/2})$ to find an $ε$-saddle point. However, it is unclear whether the computational complexity, $\mathcal{O}((N+ d^2) d ε^{-2/3})$, can be improved. In the above, we follow Doikov et al. (2023) and assume the complexity of obtaining a first-order oracle as $N$ and the complexity of obtaining a second-order oracle as $dN$. In this paper, we show that the computation cost can be reduced by reusing Hessian across iterations. Our methods take the overall computational complexity of $ \tilde{\mathcal{O}}( (N+d^2)(d+ d^{2/3}ε^{-2/3}))$, which improves those of previous methods by a factor of $d^{1/3}$. Furthermore, we generalize our method to strongly-convex-strongly-concave minimax problems and establish the complexity of $\tilde{\mathcal{O}}((N+d^2) (d + d^{2/3} κ^{2/3}) )$ when the condition number of the problem is $κ$, enjoying a similar speedup upon the state-of-the-art method. Numerical experiments on both real and synthetic datasets also verify the efficiency of our method.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。