跳转至

Faster Rates for Federated Variational Inequalities

会议: NeurIPS 2026
arXiv: 2602.09164
OpenReview: https://openreview.net/forum?id=RmzepfWb3R
领域: 优化/理论
关键词: 联邦学习, 变分不等式, 客户端漂移, 近端点算法, 收敛速率

一句话总结

针对光滑单调变分不等式在联邦优化中收敛界弱于凸优化的问题，本文通过改进客户端漂移平方项分析收紧了经典 Local Extra SGD 的收敛速率，并提出基于近似近端点迭代与外推步的新算法 LIPPAX（及高斯平滑版 SLIPPAX），在多种设定下首次达成了匹配凸优化 LSGD-optimal 的快速收敛边界。

研究背景与动机

联邦学习通过允许多个边缘客户端在本地执行多步随机梯度下降（Local SGD / FedAvg）并在周期间隔聚合模型，极大降低了通信轮数并保护了本地数据隐私。在传统的光滑凸优化中，Local SGD 能够达到通信轮次 \(R\)、本地步数 \(K\) 与客户端数量 \(M\) 下的经典最优收敛速率 \(\mathcal{O}(\frac{1}{KR} + \frac{\sigma}{\sqrt{MKR}} + \frac{\sigma^{2/3}}{K^{1/3}R^{2/3}})\)。然而，现代机器学习中的诸多前沿问题——如生成对抗网络（GAN）训练、鲁棒强化学习以及多分布学习——本质上都超出了凸优化范畴，必须建模为光滑单调变分不等式（Variational Inequalities, VIs）或凸-凹鞍点问题。

在变分不等式设定下，普通 SGD 极易发散，必须依赖外推梯度法（Extra Gradient / Mirror-Prox）。此前针对联邦变分不等式适配的 Local Extra SGD（LESGD）算法虽然保证了渐近收敛，但现有理论分析给出的上界中存在不可被本地步数 \(K\) 或客户端数 \(M\) 加速的次优项 \(\mathcal{O}(\frac{\sigma}{\sqrt{R}})\)，以及初始项中的 \(\frac{1}{\sqrt{K}R}\) 膨胀，使研究界对变分不等式下本地多步更新的通信加速价值产生了根本性怀疑。造成这一理论鸿沟的核心矛盾在于：凸优化天然满足梯度算子的余强单调性（co-coercivity），使得本地迭代天然具备收缩性；但一般光滑单调变分不等式的算子不仅缺乏余强单调性，其外推更新步在最坏情况下甚至具有扩张性（anti-cocoercivity），以往理论在推导客户端漂移（client drift）时不得不引入一阶范数与二阶范数混杂的松弛上界，导致控制客户端漂移所需的学习率极其保守。

本文的切入角度是：重新审视变分不等式对偶间隙势函数的代数展开，证明客户端漂移对最终收敛误差的负面影响仅取决于差值二阶方差项，进而通过改进分析压制 LESGD 的次优项；更进一步，引入具备内在收缩特性的近端点算子（Proximal Point Algorithm）来彻底克服外推步的漂移扩张。核心 idea：证明变分不等式下仅需二阶方差级客户端漂移即可闭合对偶间隙分析，并设计结合强单调正则化子问题近似求解与全局外推步的 LIPPAX 算法，从根本上克服外推算子扩张导致的漂移积累，首次在一般联邦单调变分不等式中实现匹配凸优化 LSGD-optimal 的快速收敛率。

方法详解

整体框架

本文针对由 \(M\) 个客户端构成的联邦变分不等式系统 \(\sup_{\mathbf{z}\in\mathcal{Z}_D}\langle V(\mathbf{z}), \mathbf{x}_o - \mathbf{z}\rangle \le 0\)。针对经典 LESGD 算法，本文提出精细化对偶间隙与漂移解耦分析；针对外推步本质上的扩张缺陷，本文提出了结合局部强单调正则化内循环与外部单步外推的 LIPPAX 架构，以及免除二阶 Hessian 有界假定的高斯平滑变体 SLIPPAX。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["输入: 客户端本地状态 z_(t-1)^m 与步长参数"] --> B["精细化客户端漂移分析<br/>消除 LESGD 的 O(σ/√R) 误差项"]
    B --> C["近似近端点子问题求解<br/>H 步内循环逼近强单调算子零点"]
    C --> D["单步外推更新与周期同步<br/>用近似点导引外推并按模 K 聚合"]
    D --> E["高斯平滑摄动机制<br/>注入高斯噪声消除 Hessian 有界假设"]
    E --> F["输出: 遍历平均解 x_o 并达成 LSGD-optimal 界"]

关键设计

1. 精细化客户端漂移分析：消除漂移一阶范数松弛以收紧收敛界 以往联邦变分不等式文献在估计对偶间隙误差时，因变分算子非单调凸函数，往往在客户端外推点与全局虚拟平均点的内积交叉项中引入 Cauchy-Schwarz 放缩，从而产生形如 \(\mathcal{O}(\|\mathbf{z}_t^m - \bar{\mathbf{z}}_t\|)\) 的一阶漂移项。一阶漂移项无法通过方差项的标准鞅差技巧求和抵消，迫使以往界中残留不可消除的 \(\mathcal{O}(\frac{\sigma}{\sqrt{R}})\) 膨胀项。本文通过构造影子虚拟序列 \(\bar{\mathbf{x}}_t = \frac{1}{M}\sum_{m=1}^M \mathbf{x}_t^m\) 和 \(\bar{\mathbf{z}}_t = \frac{1}{M}\sum_{m=1}^M \mathbf{z}_t^m\)，将所有客户端交叉内积项严格分解为虚拟均值单调项、算子 Lipschitz 光滑误差项与二阶无偏方差项。由此证明收敛界仅依赖于客户端漂移平方项 \(\mathbb{E}[\|\mathbf{z}_t^m - \bar{\mathbf{z}}_t\|^2]\) 和 \(\mathbb{E}[\|\mathbf{x}_t^m - \bar{\mathbf{x}}_t\|^2]\)，在步长 \(\eta \le \frac{1}{\sqrt{14K}L}\) 下利用递推紧致控制漂移上界为 \(936eL\eta^2\sigma^2 K\)。这使 LESGD 速率直接收紧至： $\(\mathbb{E}\left[\sup_{\mathbf{z}\in\mathcal{Z}_D}\langle V(\mathbf{z}), \mathbf{x}_o - \mathbf{z}\rangle\right] \le \frac{12LD^2}{\sqrt{K}R} + \frac{6D\sigma}{\sqrt{MKR}} + \frac{26D^{4/3}\sigma^{2/3}L^{1/3}}{K^{1/3}R^{2/3}}\)$ 当噪声方差满足 \(\sigma = \Omega(\frac{DL}{R^{1/2}K^{1/4}})\) 时，首项直接被主导，从而天然达到 LSGD-optimal 速率。

2. 近似近端点子问题求解：构造局部强单调正则化避免外推扩张 虽然 LESGD 在较大方差下可达最优率，但在低方差或确定性设置（\(\sigma \to 0\)）下，由于外推算子非余强单调甚至扩张，步长必须限制在 \(\mathcal{O}(\frac{1}{\sqrt{K}L})\)，导致首项保留了次优的 \(\frac{1}{\sqrt{K}R}\)。为从根源上克服算子扩张，本文提出 LIPPAX。其核心在于利用近端点（Proximal Point）算子的绝对非扩张收缩性。精确近端点满足 \(\mathbf{x}_t^{*,m} = \mathbf{z}_{t-1}^m - \eta V(\mathbf{x}_t^{*,m})\)，对应求解正则化强单调变分不等式： $\(F(\mathbf{x}) = V(\mathbf{x}) + \frac{1}{\eta}(\mathbf{x} - \mathbf{z}_{t-1}^m) = 0\)$ 算子 \(F(\mathbf{x})\) 具备严格的 \(\frac{1}{\eta}\)-强单调性与 \((L + \frac{1}{\eta})\)-光滑性。每个客户端在本地无需通信即可独立执行 \(H\) 步内部梯度迭代 \(\mathbf{x}_{t,\ell}^m = \mathbf{x}_{t,\ell-1}^m - \gamma (\widetilde{V}(\mathbf{x}_{t,\ell-1}^m) + \frac{1}{\eta}(\mathbf{x}_{t,\ell-1}^m - \mathbf{z}_{t-1}^m))\)，其中步长取 \(\gamma = \frac{1}{\eta(L + 1/\eta)^2}\)。通过设定 \(H = \mathcal{O}(\ln(KR))\)，几何级收敛将近端点近似误差衰减至 \(4^{-H}\) 的高阶小量，从而彻底摆脱外推算子的扩张瓶颈，将确定性收敛率首项提升为与凸优化完全一致的 \(\mathcal{O}(\frac{L}{KR})\)。

3. 单步外推更新与周期同步：以偏差-方差正交分解消除多机不可约方差 在内循环完成 \(H\) 步逼近并得到 \(\mathbf{x}_t^m = \mathbf{x}_{t,H}^m\) 后，LIPPAX 执行一次外推梯度更新：\(\mathbf{z}_t^m = \mathbf{z}_{t-1}^m - \eta \widetilde{V}(\mathbf{x}_t^m)\)。当 \(t\) 为通信周期 \(K\) 的倍数时，中心服务器汇总所有客户端参数并做平均重置。直观分析下，内循环多步随机逼近会导致不可被多机数量 \(M\) 削减的方差残留 \(\mathcal{O}(\frac{\sigma}{\sqrt{KR}})\)。为了克服该限制，本文在算子二阶导数有界（Hessian 有界常数 \(\Lambda\)）假设下，对误差做偏差-方差正交解耦： $\(\mathbb{E}[\|\bar{\mathbf{x}}_t - \bar{\mathbf{x}}_t^*\|^2] \le \|\mathbb{E}[\bar{\mathbf{x}}_t] - \bar{\mathbf{x}}_t^*\|^2 + \frac{1}{M^2}\sum_{m=1}^M \text{Var}(\mathbf{x}_t^m - \mathbf{x}_t^{*,m}) \le 6\Lambda^2\eta^6\sigma^4 + \frac{\eta^2\sigma^2}{M} + \mathcal{O}(4^{-H})\)$ 方差项被多机数 \(M\) 完整平摊，而一阶偏差项被收缩至超高阶量 \(\mathcal{O}(\eta^6\sigma^4)\)，从而证明在二阶平滑下单步外推可完全消除 \(\frac{\sigma}{\sqrt{KR}}\) 障碍，全面达成 LSGD-optimal 收敛率。

4. 高斯平滑摄动机制：以零阶扰动消除二阶导数有界限制 针对二阶导数（Jacobian 的 Lipschitz 连续性）可能在一般算子中不成立的情形，本文进一步提出 SLIPPAX。其在 LIPPAX 内循环计算算子值时引入维度为 \(d\) 的高斯随机微扰向量 \(\mathbf{s}_{t,\ell}^m \sim \mathcal{N}(\mathbf{0}, I_d)\)，通过评估 \(\widetilde{V}(\mathbf{x}_{t,\ell-1}^m + \delta \mathbf{s}_{t,\ell}^m; \xi)\) 隐式构造光滑化算子 \(\mathring{V}(\mathbf{x}) = \mathbb{E}[V(\mathbf{x} + \delta \mathbf{s})]\)。本文证明了微扰平滑算子的 Jacobian 天然具备 \(\frac{2L\sqrt{d}}{\delta}\)-Lipschitz 连续性。通过精确设定微扰半径 \(\delta = \frac{\eta\sigma}{\sqrt{d}}\)，SLIPPAX 仅凭算子有界性 \(\|V(\mathbf{x})\|\le G\) 与一阶 Lipschitz 光滑性，即成功控制各阶余项，在对数因子下达到 LSGD-optimal 速率。

损失函数 / 训练策略

算法以对偶间隙误差（Dual Gap Error / Restricted Merit Function）作为收敛衡量标准： $\(\text{err}(\mathbf{x}_o) = \sup_{\mathbf{z}\in\mathcal{Z}_D} \langle V(\mathbf{z}), \mathbf{x}_o - \mathbf{z}\rangle, \quad \mathcal{Z}_D = \left\{\mathbf{z} \in \mathbb{R}^d \;\middle|\; \left\|\mathbf{z} - \frac{1}{M}\sum_{m=1}^M \mathbf{z}_0^m\right\| \le D\right\}\)$ 在复合变分不等式（Composite VI, 带有非光滑凸正则项 \(\phi(\mathbf{z})\)）中，目标推广为 \(\text{err}_c(\mathbf{v}_o) = \sup_{\mathbf{u}} [\langle V(\mathbf{u}), \mathbf{v}_o - \mathbf{u}\rangle + \phi(\mathbf{v}_o) - \phi(\mathbf{u})]\)。优化策略采用两阶段学习率最小化配置：由确定性光滑步长上限、方差加速项与漂移控制项三者取 \(\min\) 动态决定。

实验关键数据

主实验

论文通过严格的理论推导建立了各类变分不等式设置下的最紧收敛速率，与已有前沿工作相比取得了显著的阶数突破。

算法 / 理论设定 适用问题 假设条件 理论收敛边界 (Convergence Bound) 相比已有 SOTA 理论改进
LESGD (Beznosikov et al., 2022) 一般光滑单调 FVI 单调, \(L\)-光滑 \(\mathcal{O}(\frac{1}{\sqrt{K}R} + \frac{\sigma}{\sqrt{MKR}} + \sqrt{\frac{\sigma}{\sqrt{K}R} + \frac{\sigma^2}{R}})\) 基线 (存在不随 \(M, K\) 衰减的 \(\frac{\sigma}{\sqrt{R}}\) 项)
LESGD (本文 Theorem 1) 一般光滑单调 FVI 单调, \(L\)-光滑 \(\mathcal{O}(\frac{1}{\sqrt{K}R} + \frac{\sigma}{\sqrt{MKR}} + \frac{\sigma^{2/3}}{K^{1/3}R^{2/3}})\) 彻底消除不可约项 \(\frac{\sigma}{\sqrt{R}}\)，方差足时达最优
LESGD (本文 Theorem 2) 仿射算子 FVI 仿射, \(L\)-光滑 \(\mathcal{O}(\frac{1}{KR} + \frac{\sigma}{\sqrt{MKR}} + \frac{\sigma^{2/3}}{K^{1/3}R^{2/3}})\) 首项由 \(\frac{1}{\sqrt{K}R}\) 提速至 \(\frac{1}{KR}\)，完全匹配 LSGD 最优界
LIPPAX (本文 Theorem 4) 一般光滑单调 FVI 有界算子 + Hessian 有界 \(\mathcal{O}(\frac{1}{KR} + \frac{\sigma}{\sqrt{MKR}} + \frac{\sigma^{2/3}}{K^{1/3}R^{2/3}})\) 任意方差下首项为 \(\frac{1}{KR}\)，消除算子扩张缺陷
SLIPPAX (本文 Theorem 5) 一般光滑单调 FVI 仅需有界算子 \(\widetilde{\mathcal{O}}(\frac{1}{KR} + \frac{\sigma}{\sqrt{MKR}} + \frac{\sigma^{2/3}}{K^{1/3}R^{2/3}})\) 无需二阶有界，对数因子下实现 LSGD 最优界
LSGD (本文 Theorem 6) 余强单调 FVI \(\beta\)-余强单调 \(\mathcal{O}(\frac{1}{KR} + \frac{\sigma}{\sqrt{MKR}} + \frac{\sigma^{2/3}}{K^{1/3}R^{2/3}})\) 首次证明普通本地 SGD 在余强单调变分不等式中即达最优
Local Dual Averaging (Bai & Bullins, 2024) 复合变分不等式 (FCVI) 有界算子, 非光滑 \(\phi\) \(\mathcal{O}(\frac{1}{KR} + \frac{1}{\sqrt{R}} + \frac{\sigma}{\sqrt{MKR}} + \frac{1}{K^{1/4}R^{3/4}})\) 存在次优阶 \(\frac{1}{\sqrt{R}}\) 与 \(\frac{1}{K^{1/4}R^{3/4}}\)
Local Dual Averaging (本文 Theorem 7) 复合变分不等式 (FCVI) 有界算子, 非光滑 \(\phi\) \(\mathcal{O}(\frac{1}{KR} + \frac{1}{R^{2/3}} + \frac{\sigma}{\sqrt{MKR}})\) 由 \(\frac{1}{\sqrt{R}}\) 提升至 \(\frac{1}{R^{2/3}}\)，匹配复合凸优化最优界

消融实验

为明确不同机制与假设条件对消除各类缺陷项的贡献，下表分解了算法设计中关键组件对边界各阶段误差项的消融影响：

配置 / 机制组合 首项速率 (加速比) 方差混合项 次优障碍项 机制说明
原始 LESGD 分析 \(\mathcal{O}(\frac{1}{\sqrt{K}R})\) \(\mathcal{O}(\frac{\sigma}{\sqrt{MKR}})\) 存在 \(\mathcal{O}(\frac{\sigma}{\sqrt{R}})\) 因一阶漂移松弛产生非加速方差项
本文纯平方漂移分析 (Theorem 1) \(\mathcal{O}(\frac{1}{\sqrt{K}R})\) \(\mathcal{O}(\frac{\sigma^{2/3}}{K^{1/3}R^{2/3}} + \frac{\sigma}{\sqrt{MKR}})\) 无 消除一阶范数松弛，但外推算子扩张仍限制首项步长
仿射算子特性 (Theorem 2) \(\mathcal{O}(\frac{1}{KR})\) \(\mathcal{O}(\frac{\sigma^{2/3}}{K^{1/3}R^{2/3}} + \frac{\sigma}{\sqrt{MKR}})\) 无 仿射结构赋予外推算子非扩张性，步长恢复 \(\mathcal{O}(1/L)\)
LIPPAX 基础版 (Theorem 3) \(\mathcal{O}(\frac{1}{KR})\) \(\mathcal{O}(\frac{\sigma^{2/3}}{K^{1/3}R^{2/3}} + \frac{\sigma}{\sqrt{MKR}})\) 残留 \(\mathcal{O}(\frac{\sigma}{\sqrt{KR}})\) 近端点消除首项扩张，但内循环方差未经 \(M\) 平均
LIPPAX + Hessian 有界分解 (Theorem 4) \(\mathcal{O}(\frac{1}{KR})\) \(\mathcal{O}(\frac{\sigma^{2/3}}{K^{1/3}R^{2/3}} + \frac{\sigma}{\sqrt{MKR}})\) 无 (完全消除) 偏差-方差正交解耦，多机平均消除残留方差
SLIPPAX + 高斯微扰平滑 (Theorem 5) \(\widetilde{\mathcal{O}}(\frac{1}{KR})\) \(\widetilde{\mathcal{O}}(\frac{\sigma^{2/3}}{K^{1/3}R^{2/3}} + \frac{\sigma}{\sqrt{MKR}})\) 无 (完全消除) 高斯扰动隐式构造二阶平滑，弱化为一阶有界假设

关键发现

  • 客户端漂移的二阶本质：在变分不等式中，阻碍获得快速收敛速率的并非变分不等式结构本身，而是以往分析中不必要的绝对值放缩。当仅将漂移约束在二阶方差范数时，LESGD 即可消除长期困扰理论界的 \(\mathcal{O}(\sigma/\sqrt{R})\) 瓶颈。
  • 外推步扩张 vs 近端点收缩：外推步非余强单调所带来的最坏反向扩张因子 \((1+\eta^4)\) 迫使步长必须缩减为 \(\eta = \mathcal{O}(1/(\sqrt{K}L))\)，而基于强单调辅助子问题的近似近端点仅需 \(\mathcal{O}(\ln(KR))\) 步即可将不精确误差压制为几何高阶小项，恢复与经典凸优化一致的 \(\eta = \mathcal{O}(1/L)\) 步长。
  • 异构拓展的一致性：在数据异构（Bounded Heterogeneity: \(\|V_m(\mathbf{x}) - V(\mathbf{x})\| \le \xi\)）拓展中，改进后的漂移递推分析能够精准推导出依赖 \(\mathcal{O}(\frac{\xi^{2/3}}{R^{2/3}} + \frac{\sqrt{\xi}}{\sqrt{R}})\) 的平滑退化边界，与同类凸优化异构分析保持高度理论自洽。

亮点与洞察

  • 从技术分析上统一凸优化与变分不等式的收敛边界：长期以来学术界普遍认为由于凸-凹鞍点问题等变分不等式缺乏余强单调性，其分布式收敛速率必然在阶数上弱于凸优化。本文首次证明对于光滑单调变分不等式，在多种核心体制下其加速边界与经典的凸优化 LSGD-optimal 速率完全一致。
  • 巧妙利用正则化子问题化解非单调扩张：巧妙地将计算困难的隐式近端点方程转换为一个具有 \(1/\eta\)-强单调性的局部优化子问题，使客户端可以在完全不与服务器及其他节点通信的前提下，仅依靠本地多步迭代在极快时间（对数收敛）内获取高精度近端点。
  • 高斯平滑化算子技巧的迁移价值：通过高斯微扰将非光滑算子的二阶导数进行解析平滑，并严格控制微扰方差引入的偏差项，该技巧可广泛迁移至缺乏高阶平滑保证的非凸非凹分布式博弈与强化学习理论分析中。

局限与展望

  • 算子有界性假设的依赖：LIPPAX 和 SLIPPAX 的收敛分析依赖于算子有界性条件 \(\|V(\mathbf{x})\| \le G\)；在无界定义域且算子无界的极端设定下，理论保证需要进一步发展无界近端截断技巧。
  • 复合变分不等式中的确定性下界项：在复合非光滑正则化变分不等式（FCVI）中，收敛率仍包含与方差无关的 \(\mathcal{O}(G/R^{2/3})\) 误差项，即使在完全无噪的确定性设置（\(\sigma = 0\)）下也无法降至 \(\mathcal{O}(1/(KR))\)，能否彻底消除此项仍是开放难题。
  • 非 IID 异构数据的深入收紧：目前的主要优化下界集中在同分布同构场景（Homogeneous Setting），附录中的异构扩展仍依赖于较为严格的一阶梯度差异有界假设，有待结合方差缩减（如 SCAFFOLD 机制）做进一步优化。

相关工作与启发

  • vs Beznosikov et al. (NeurIPS 2022) [LESGD]: 早期工作因漂移放缩不够紧凑，得出了包含 \(\mathcal{O}(\sqrt{\frac{\sigma}{\sqrt{K}R} + \frac{\sigma^2}{R}})\) 的次优界，导致无法展现本地更新步数 \(K\) 的显著加速效应；本文通过消除一阶漂移松弛，证明了 LESGD 本身即享有更紧致的理论性质，并在大方差时直接达最优。
  • vs Bai & Bullins (ICLR 2024) [Local Dual Averaging]: Bai 等人对复合鞍点问题的速率为 \(\mathcal{O}(\frac{1}{\sqrt{R}} + \frac{1}{K^{1/4}R^{3/4}})\)；本文 Theorem 7 将通信轮次依赖由 \(\mathcal{O}(1/\sqrt{R})\) 提速至 \(\mathcal{O}(1/R^{2/3})\)，完全对齐了 Yuan et al. (ICML 2021) 在复合凸优化中取得的最佳纪录。
  • vs Gorbunov et al. (AISTATS 2022) [Extragradient Cocoercivity]: Gorbunov 等人指出一般单调变分不等式中外推算子具有内在反余强单调扩张；本文以此为理论基石，深刻指明了 LESGD 存在 \(\frac{1}{\sqrt{K}R}\) 瓶颈的本质诱因，从而导向了近端点收缩算法 LIPPAX 的全新设计。

评分

  • 新颖性: ⭐⭐⭐⭐⭐ 首次从理论上突破联邦单调变分不等式的收敛瓶颈，提出消除扩张漂移的近端点外推混合架构。
  • 实验充分度: ⭐⭐⭐⭐ 理论推导完备缜密，涵盖仿射、低方差、高阶导数有界、高斯平滑及非光滑复合等多种场景，唯缺少数值仿真实验验证。
  • 写作质量: ⭐⭐⭐⭐⭐ 论文结构严谨，数学推导逻辑自洽，问题痛点与创新突破点陈述极其清晰有力。
  • 价值: ⭐⭐⭐⭐⭐ 为分布式对抗训练、多智能体博弈与联邦鞍点优化奠定了坚实的基础理论边界。

相关论文