提出新型二阶算法，高效求解非凸强凹极小极大问题。
Gradient Norm Regularization Second-Order Algorithms for Solving Nonconvex-Strongly Concave Minimax Problems
- 通过梯度范数正则化改进信任区域子问题，自适应调整参数。
- 达到最优迭代复杂度 $\tilde{O}(\ell^{1.5}ρ^{0.5}μ^{-1.5}ε^{-1.5})$，收敛至二阶驻点。
- 算法适用于机器学习中的对抗训练与鲁棒优化场景。
本文研究用于求解非凸-强凹极小极大问题的二阶算法，该类问题在机器学习等领域备受关注。提出梯度范数正则化信任区域（GRTR）算法，其每轮迭代中信任区域子问题的目标函数使用了正则化版海森矩阵，正则化系数与球形约束半径均与梯度范数平方根成比例。证明了该算法获得 $O(ε,\sqrt{ε})$-二阶驻点的迭代复杂度上界为 $\tilde{O}(\ell^{1.5}ρ^{0.5}μ^{-1.5}ε^{-1.5})$，与现有最优二阶方法一致。进一步提出带梯度范数正则化的Levenberg-Marquardt算法（LMNegCur），无需每步求解信任区域子问题，并利用负曲率方向修正迭代方向。同样证明其可在 $\tilde{O}(\ell^{1.5}ρ^{0.5}μ^{-1.5}ε^{-1.5})$ 次迭代内达到目标。两种算法的近似变体仍以高概率获得 $O(ε,\sqrt{ε})$-二阶驻点，且仅需 $\tilde{O}(\ell^{2.25}ρ^{0.25}μ^{-1.75}ε^{-1.75})$ 次海森-向量乘积和 $\tilde{O}(\ell^{2}ρ^{0.5}μ^{-2}ε^{-1.5})$ 次梯度上升步。
原文摘要 · Abstract (English)
In this paper, we study second-order algorithms for solving nonconvex-strongly concave minimax problems, which have attracted much attention in recent years in many fields, especially in machine learning.We propose a gradient norm regularized trust-region (GRTR) algorithm to solve nonconvex-strongly concave minimax problems, where the objective function of the trust-region subproblem in each iteration uses a regularized version of the Hessian matrix, and the regularization coefficient and the radius of the ball constraint are proportional to the square root of the gradient norm. The iteration complexity of the proposed GRTR algorithm to obtain an $O(ε,\sqrtε)$-second-order stationary point is proved to be upper bounded by $\tilde{O}(\ell^{1.5}ρ^{0.5}μ^{-1.5}ε^{-1.5})$, where $μ$ is the strong concave coefficient, $\ell$ and $ρ$ are the Lipschitz constant of the gradient and Jacobian matrix respectively, which matches the best known iteration complexity of second-order methods for solving nonconvex-strongly concave minimax problems. We further propose a Levenberg-Marquardt algorithm with a gradient norm regularization coefficient and use the negative curvature direction to correct the iteration direction (LMNegCur), which does not need to solve the trust-region subproblem at each iteration. We also prove that the LMNegCur algorithm achieves an $O(ε,\sqrtε)$-second-order stationary point within $\tilde{O}(\ell^{1.5}ρ^{0.5}μ^{-1.5}ε^{-1.5})$ number of iterations.The inexact variants of both algorithms can still obtain $O(ε,\sqrtε)$-second-order stationary points with high probability, but only require $\tilde{O}(\ell^{2.25}ρ^{0.25}μ^{-1.75}ε^{-1.75})$ Hessian-vector products and $\tilde{O}(\ell^{2}ρ^{0.5}μ^{-2}ε^{-1.5})$ gradient ascent steps.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。