In this paper, we show that applying adaptive methods directly to distributed
minimax problems can result in non-convergence due to inconsistency in locally
computed adaptive stepsizes. To address this challenge, we propose D-AdaST, a
Distributed Adaptive minimax method with Stepsize Tracking. The key strategy is
to employ an adaptive stepsize tracking protocol involving the transmission of
two extra (scalar) variables. This protocol ensures the consistency among
stepsizes of nodes, eliminating the steady-state error due to the lack of
coordination of stepsizes among nodes that commonly exists in vanilla
distributed adaptive methods, and thus guarantees exact convergence. For
nonconvex-strongly-concave distributed minimax problems, we characterize the
specific transient times that ensure time-scale separation of stepsizes and
quasi-independence of networks, leading to a near-optimal convergence rate of
$\tilde{\mathcal{O}} \left( \epsilon ^{-\left( 4+\delta \right)} \right)$ for
any small $\delta > 0$, matching that of the centralized counterpart. To our
best knowledge, D-AdaST is the first distributed adaptive method achieving
near-optimal convergence without knowing any problem-dependent parameters for
nonconvex minimax problems. Extensive experiments are conducted to validate our
theoretical results.

提出一种名为 D-AdaST 的分布式自适应极小 - 极大方法，通过步长跟踪协议解决节点之间步长不一致的问题，从而实现最优收敛率，适用于非凸极小 - 极大问题，并在实验中验证了理论结果。

自适应步长的分布式极小 - 最优优化实现近乎最优收敛

Achieving Near-Optimal Convergence for Distributed Minimax Optimization  with Adaptive Stepsizes

In this paper, we study zeroth-order algorithms for nonconvex minimax
problems with coupled linear constraints under the deterministic and stochastic
settings, which have attracted wide attention in machine learning, signal
processing and many other fields in recent years, e.g., adversarial attacks in
resource allocation problems and network flow problems etc. We propose two
single-loop algorithms, namely the zero-order primal-dual alternating projected
gradient (ZO-PDAPG) algorithm and the zero-order regularized momentum
primal-dual projected gradient algorithm (ZO-RMPDPG), for solving deterministic
and stochastic nonconvex-(strongly) concave minimax problems with coupled
linear constraints. The iteration complexity of the two proposed algorithms to
obtain an $\varepsilon$-stationary point are proved to be
$\mathcal{O}(\varepsilon ^{-2})$ (resp. $\mathcal{O}(\varepsilon ^{-4})$) for
solving nonconvex-strongly concave (resp. nonconvex-concave) minimax problems
with coupled linear constraints under deterministic settings and
$\tilde{\mathcal{O}}(\varepsilon ^{-3})$ (resp.
$\tilde{\mathcal{O}}(\varepsilon ^{-6.5})$) under stochastic settings
respectively. To the best of our knowledge, they are the first two zeroth-order
algorithms with iterative complexity guarantees for solving
nonconvex-(strongly) concave minimax problems with coupled linear constraints
under the deterministic and stochastic settings.

研究零阶算法求解非凸最小最大问题在确定性和随机设置下的紧密线性约束，为确定性和随机设置下求解非凸凹最小最大问题提出两种单环算法，即零阶原始 -- 对偶交替投影梯度（ZO-PDAPG）算法和零阶正则化动量原始 -- 对偶投影梯度算法（ZO-RMPDPG），其迭代复杂度被证明为 Ο(ε^(-2))（非凸凹最小最大问题）和 Ο(ε^(-4))（非凸凹最小最大问题），在确定性设置下，持有 ε- 稳定点，并且在随机设置下，迭代复杂度分别为 Ο̃(ε^(-3)) 和 Ο̃(ε^(-6.5))。据我们所知，它们是第一个能够解决确定性和随机设置下的非凸凹最小最大问题的零阶算法，并具有迭代复杂度保证。

零阶原始 - 对偶交替投影梯度算法用于带有耦合线性约束的非凸极小极大问题

Zeroth-Order primal-dual Alternating Projection Gradient Algorithms for  Nonconvex Minimax Problems with Coupled linear Constraints

Nonconvex minimax problems appear frequently in emerging machine learning
applications, such as generative adversarial networks and adversarial learning.
Simple algorithms such as the gradient descent ascent (GDA) are the common
practice for solving these nonconvex games and receive lots of empirical
success. Yet, it is known that these vanilla GDA algorithms with constant step
size can potentially diverge even in the convex setting. In this work, we show
that for a subclass of nonconvex-nonconcave objectives satisfying a so-called
two-sided Polyak-{\L}ojasiewicz inequality, the alternating gradient descent
ascent (AGDA) algorithm converges globally at a linear rate and the stochastic
AGDA achieves a sublinear rate. We further develop a variance reduced algorithm
that attains a provably faster rate than AGDA when the problem has the
finite-sum structure.

研究非凸极小问题的解决方案，提出两种算法 AGDA 和随机 AGDA，以及一种方差缩减算法，可以应用于类似生成对抗网络和对抗学习等新兴机器学习应用。