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

本文针对具有耦合线性约束的非凸极小极大问题，提出了两种单循环零阶算法（ZO-PDAPG 和 ZO-RMPDPG），并在确定性和随机设定下分别证明了其达到$\varepsilon$-平稳点的迭代复杂度，填补了该领域零阶算法理论分析的空白，其中 ZO-RMPDPG 在无约束随机设定下还刷新了现有零阶算法的最优复杂度记录。

要点

这篇论文主要讲的是如何在一个充满“黑盒”和“限制”的复杂游戏中，找到最佳策略。

为了让你更容易理解，我们可以把这篇论文里的数学概念想象成一场**“黑客与防御者”的博弈游戏**。

1. 核心场景：一场受限的博弈

想象一下，有两个玩家：

• 玩家 A（攻击者/最小化者）：他想把某种“成本”降到最低（比如让网络流量最便宜，或者让模型预测最准）。
• 玩家 B（防御者/最大化者）：他想把“成本”推到最高（比如制造混乱，或者让模型出错）。

这就是所谓的**“极小极大问题”（Minimax Problem）**：A 想最小化，B 想最大化，两人互相博弈。

难点在于：

1. 黑盒世界（零阶优化）：A 和 B 都不知道对方的“内部公式”（梯度/导数）。他们就像在黑暗中摸索，只能看到“结果”（比如：我这么做了，成本变成了多少），却看不到“原因”（为什么变了？）。这就像蒙眼走迷宫，只能靠碰运气和试探。
2. 复杂的规则（耦合线性约束）：游戏不是想怎么玩就怎么玩，必须遵守严格的规则。比如，“总流量不能超过管道容量”或者“攻击预算不能超过 100 块”。这些规则把两个玩家紧紧绑在一起，牵一发而动全身。

2. 论文做了什么？

以前的算法大多需要知道“内部公式”（一阶方法），或者在没有规则的黑盒里乱撞。这篇论文提出了两种新的**“蒙眼探路”算法**，专门用来解决这种既不知道内部公式、又有严格规则的复杂博弈。

算法一：ZO-PDAPG（稳健的“试探 - 调整”法）

• 适用场景：确定性环境（比如规则很明确，没有随机噪音）。
• 工作原理：
  想象你在一个有很多路障的迷宫里找出口。你每走一步，就向四周轻轻推一下（这是“零阶”试探，只问结果），看看哪边路更宽。
  • 交替：A 走一步，B 走一步，轮流来。
  • 投影：如果不小心撞到了墙（违反了规则），算法会把你“弹”回规则允许的范围内（投影）。
  • 效果：它像是一个经验丰富的盲人向导，虽然看不见，但通过不断的微调，能比较快地找到那个“最坏情况下的最好结果”。
• 成就：在数学上证明了，只要给足够的时间（迭代次数），它一定能找到那个接近完美的平衡点。

算法二：ZO-RMPDPG（带“动量”的加速法）

• 适用场景：随机环境（比如数据里有噪音，或者规则是概率性的，像“数据投毒”攻击）。
• 工作原理：
  这个算法在“试探 - 调整”的基础上，加上了**“动量”（Momentum）和“方差缩减”（Variance Reduction）**。
  • 动量：就像骑自行车下坡，如果前面路顺，就借着惯性冲得更快，而不是每步都停下来重新起步。这大大加快了速度。
  • 方差缩减：因为环境有噪音（比如随机干扰），有时候试探的结果不准。这个技巧就像是用“平均值”来过滤噪音，让方向更清晰。
• 成就：这是目前最快的蒙眼探路算法之一。特别是在没有规则限制的随机博弈中，它打破了之前的记录，跑得比所有现有的同类算法都快。

3. 为什么要研究这个？（现实应用）

这篇论文不仅仅是玩数学游戏，它解决的是现实世界中非常棘手的问题：

• 网络流攻击：想象黑客想通过注入虚假流量，让物流公司的运输成本飙升。物流公司要防御，黑客要攻击。双方都不知道对方的具体算法（黑盒），但必须遵守物理管道的限制。这篇论文的方法能帮物流公司找到最坚固的防御策略。
• 数据投毒（Data Poisoning）：想象有人想往训练 AI 的数据里掺假，让 AI 学坏。AI 训练者要抵抗这种攻击。因为攻击者的手段是未知的（黑盒），这篇论文的方法能帮助训练者设计出更鲁棒的模型，防止被“下毒”。

4. 总结：这篇论文的“超能力”

简单来说，这篇论文发明了两把新的“蒙眼探路”工具：

1. 一把是稳扎稳打型（ZO-PDAPG），适合规则清晰但看不清内部的情况。
2. 一把是加速冲刺型（ZO-RMPDPG），适合充满噪音和随机性的复杂环境，而且是目前速度最快的。

它的最大贡献是：以前大家认为在“既看不见内部公式，又有复杂规则”的博弈中，很难保证找到最优解。但这篇论文证明了，用他们的新方法，不仅能找到，而且还能算出需要走多少步（复杂度分析），这在数学上是一个巨大的突破，为人工智能的安全防御提供了更强大的理论武器。

技术摘要

这篇论文提出并分析了两类用于求解带有耦合线性约束的非凸极小极大（Minimax）问题的零阶（Zeroth-order）算法。这类问题在机器学习（如对抗攻击、数据投毒）、信号处理和资源分配等领域具有重要应用，且由于目标函数可能是黑盒（Black-box）或梯度不可用，传统的基于梯度的方法难以直接应用。

以下是对该论文的详细技术总结：

1. 研究问题 (Problem)

论文主要研究以下两类带有耦合线性约束 $Ax + By \leq c$ (或 $=$) 的极小极大优化问题：

• 确定性设置 (Deterministic Setting):
  $$\min_{x \in X} \max_{y \in Y, Ax+By \leq c} f(x, y)$$
• 随机性设置 (Stochastic Setting):
  $$\min_{x \in X} \max_{y \in Y, Ax+By \leq c} g(x, y) = \mathbb{E}_{\zeta \sim D}[G(x, y, \zeta)]$$

关键特征与挑战：

• 非凸 - 凹/强凹 (Nonconvex-(Strongly) Concave): 目标函数 $f(x, y)$ 关于 $x$ 是非凸的，关于 $y$ 是凹的或强凹的。
• 耦合线性约束 (Coupled Linear Constraints): 变量 $x$ 和 $y$ 通过线性约束 $Ax + By \leq c$ 相互耦合，这增加了问题的难度，使得传统的分解方法失效。
• 零阶信息 (Zeroth-order): 算法仅能获取函数值，无法获取梯度信息（$\nabla f$ 不可用），必须通过有限差分（Finite Difference）等技术估计梯度。
• 现有空白： 在提出本文之前，尚无针对此类带有耦合约束的非凸极小极大问题的具有理论迭代复杂度保证的零阶算法。

2. 方法论 (Methodology)

作者提出了两种单循环（Single-loop）零阶算法，分别针对确定性和随机性场景：

2.1 确定性算法：ZO-PDAPG

名称： 零阶原对偶交替投影梯度算法 (Zeroth-order Primal-Dual Alternating Projected Gradient, ZO-PDAPG)。

• 核心思想： 基于拉格朗日对偶理论，将原问题转化为无约束的鞍点问题。利用原对偶交替策略更新变量。
• 梯度估计： 使用基于坐标方向的有限差分估计器（Finite Difference Estimators）来近似梯度 $\nabla_x f$ 和 $\nla_y f$。
• 更新步骤：
  1. $y$ 更新： 在 $Y$ 上执行投影梯度上升步（最大化 $y$）。
  2. $x$ 更新： 在 $X$ 上执行投影梯度下降步（最小化 $x$）。
  3. $\lambda$ 更新： 对偶变量（拉格朗日乘子）的投影梯度上升步，用于处理耦合约束。
• 正则化： 在分析中引入正则化项 $\tilde{L}_k = L - \frac{\rho_k}{2}\|y\|^2$ 以处理非强凹情况，确保收敛性。

2.2 随机性算法：ZO-RMPDPG

名称： 零阶正则化动量原对偶投影梯度算法 (Zeroth-order Regularized Momentum Primal-Dual Projected Gradient, ZO-RMPDPG)。

• 核心思想： 针对随机设置，结合了方差缩减 (Variance Reduction) 和 动量 (Momentum) 技术，以加速收敛并降低噪声影响。
• 梯度估计： 使用小批量（Mini-batch）采样结合有限差分估计随机梯度。
• 更新步骤：
  1. 方差缩减： 维护梯度估计的动量项（类似 STORM 或 Spider 算法），利用当前和上一轮的梯度差来减少方差。
  2. 动量更新： 在 $x, y, \lambda$ 的更新中引入动量项，加速收敛。
  3. 正则化： 同样引入正则化参数 $\rho_k$ 处理非强凹情形。
• 区别： 与现有的零阶算法（如 ZO-AGDA）相比，ZO-RMPDPG 不仅使用了方差缩减，还引入了动量加速，且专门针对耦合约束设计。

3. 主要贡献与理论结果 (Key Contributions & Results)

论文在迭代复杂度（Iteration Complexity）方面取得了突破性进展，即为了达到 $\epsilon$-平稳点（$\epsilon$-stationary point）所需的迭代次数。

3.1 确定性设置下的复杂度

• 非凸 - 强凹 (Nonconvex-Strongly Concave):
  • ZO-PDAPG 的复杂度为 $O(\epsilon^{-2})$（具体为 $O(\kappa^2 \epsilon^{-2})$，其中 $\kappa$ 为条件数）。
  • 这是该类问题首个具有理论保证的零阶算法。
• 非凸 - 凹 (Nonconvex-Concave):
  • ZO-PDAPG 的复杂度为 $O(\epsilon^{-4})$。

3.2 随机性设置下的复杂度

• 非凸 - 强凹 (Nonconvex-Strongly Concave):
  • ZO-RMPDPG 的复杂度为 $\tilde{O}(\kappa^{4.5} \epsilon^{-3})$。
  • 优于现有的零阶算法（如 ZO-Min-Max 的 $O(\kappa^6 \epsilon^{-6})$ 和 ZO-SGDMSA 的 $\tilde{O}(\kappa^2 \epsilon^{-4})$ 等）。
• 非凸 - 凹 (Nonconvex-Concave):
  • ZO-RMPDPG 的复杂度为 $\tilde{O}(\epsilon^{-6.5})$。
  • 显著优势： 当去掉耦合约束（退化为标准非凸 - 凹极小极大问题）时，该算法的复杂度 $\tilde{O}(\epsilon^{-6.5})$ 优于现有最好的零阶算法 ZO-GDEGA 的 $O(\epsilon^{-8})$，创造了新的最先进（State-of-the-art）水平。

3.3 理论创新

• 势函数构造： 由于对偶变量 $\lambda$ 的定义域 $\Lambda$ 可能无界（非紧集），传统的收敛分析工具失效。作者构造了新的势函数（Potential Function）来克服这一困难，证明了算法的收敛性。
• KKT 点保证： 证明了算法生成的序列不仅收敛到平稳点，而且满足约束违反度在 $\epsilon$ 范围内，即 $\epsilon$-KKT 点。

4. 数值实验 (Numerical Results)

论文在两个实际应用场景中验证了算法的有效性：

1. 网络流问题中的对抗攻击 (Adversarial attacks in network flow):
   • 模拟攻击者通过注入流量增加网络传输成本。
   • 结果：ZO-PDAPG 的性能与现有的最优一阶算法（PDAPG, MGD, PGmsAD）相当，证明了零阶方法在梯度不可用时的有效性。
2. 逻辑回归的数据投毒 (Data poisoning against logistic regression):
   • 模拟攻击者通过污染训练数据来破坏模型预测。
   • 结果：ZO-PDAPG 和 ZO-RMPDPG 在平稳性间隙（Stationary Gap）和测试准确率上均与一阶算法表现相当，且 ZO-RMPDPG 在随机设置下展现了良好的收敛性。

5. 意义与总结 (Significance)

• 填补理论空白： 首次为带有耦合线性约束的非凸极小极大问题提供了具有严格理论复杂度保证的零阶算法。
• 实用性强： 解决了机器学习中常见的黑盒优化问题（如对抗攻击、超参数调优），在这些场景中梯度往往不可获取。
• 性能提升： 提出的 ZO-RMPDPG 算法在随机非凸 - 凹设置下，即使在没有耦合约束的情况下，也刷新了零阶算法的复杂度记录，展示了动量和方差缩减技术结合的巨大潜力。
• 通用性： 算法框架灵活，能够处理不等式和等式混合的耦合约束。

综上所述，这篇论文通过创新的算法设计和严谨的数学分析，推动了零阶优化在复杂约束极小极大问题领域的发展，为黑盒环境下的机器学习对抗与防御提供了强有力的理论工具。