Lower-bound analyses for nonconvex strongly-concave minimax optimization
problems have shown that stochastic first-order algorithms require at least
$\mathcal{O}(\varepsilon^{-4})$ oracle complexity to find an
$\varepsilon$-stationary point. Some works indicate that this complexity can be
improved to $\mathcal{O}(\varepsilon^{-3})$ when the loss gradient is Lipschitz
continuous. The question of achieving enhanced convergence rates under distinct
conditions, remains unresolved. In this work, we address this question for
optimization problems that are nonconvex in the minimization variable and
strongly concave or Polyak-Lojasiewicz (PL) in the maximization variable. We
introduce novel bias-corrected momentum algorithms utilizing efficient
Hessian-vector products. We establish convergence conditions and demonstrate a
lower iteration complexity of $\mathcal{O}(\varepsilon^{-3})$ for the proposed
algorithms. The effectiveness of the method is validated through applications
to robust logistic regression using real-world datasets.

针对非凸优化中最小最大优化问题，本研究提出了利用高效的 Hessian - 向量乘积的新型修正动量算法，建立了收敛条件并证明了所提算法的迭代复杂度为 O (ε^{-3})。通过在实际数据集上进行鲁棒的逻辑回归的应用验证了该方法的有效性。

基于修正偏置动量的加速随机极小 - 极大优化

Accelerated Stochastic Min-Max Optimization Based on Bias-corrected  Momentum

This paper considers stochastic first-order algorithms for minimax
optimization under Polyak--{\L}ojasiewicz (PL) conditions. We propose
SPIDER-GDA for solving the finite-sum problem of the form $\min_x \max_y
f(x,y)\triangleq \frac{1}{n} \sum_{i=1}^n f_i(x,y)$, where the objective
function $f(x,y)$ is $\mu_x$-PL in $x$ and $\mu_y$-PL in $y$; and each
$f_i(x,y)$ is $L$-smooth. We prove SPIDER-GDA could find an $\epsilon$-optimal
solution within ${\mathcal O}\left((n + \sqrt{n}\,\kappa_x\kappa_y^2)\log
(1/\epsilon)\right)$ stochastic first-order oracle (SFO) complexity, which is
better than the state-of-the-art method whose SFO upper bound is ${\mathcal
O}\big((n + n^{2/3}\kappa_x\kappa_y^2)\log (1/\epsilon)\big)$, where
$\kappa_x\triangleq L/\mu_x$ and $\kappa_y\triangleq L/\mu_y$. For the
ill-conditioned case, we provide an accelerated algorithm to reduce the
computational cost further. It achieves $\tilde{{\mathcal
O}}\big((n+\sqrt{n}\,\kappa_x\kappa_y)\log^2 (1/\epsilon)\big)$ SFO upper bound
when $\kappa_y \gtrsim \sqrt{n}$. Our ideas also can be applied to the more
general setting that the objective function only satisfies PL condition for one
variable. Numerical experiments validate the superiority of proposed methods.

基于 Polyak-Lojasiewicz 条件，本文提出了用于解决 minimax 优化问题的随机一阶算法 SPIDER-GDA，该算法在有限和的情况下达到了更好的优化效果，并降低了计算成本。