Decentralized Stochastic Nonconvex Optimization under the $(L_0,L_1)$-Smoothness

技术摘要：$(L_0, L_1)$-光滑性下的去中心化随机非凸优化

问题表述
本文研究了在由 $n$ 个智能体组成的连通网络上的去中心化随机优化问题。目标是最小化全局函数 $f(x) = \frac{1}{m} \sum_{i=1}^m f_i(x)$，其中每个局部函数 $f_i(x) = \mathbb{E}[F_i(x; \xi_i)]$ 由局部分布 $\mathcal{D}_i$ 定义。该设定假设：

1. 非凸性： 局部函数可能是非凸的。
2. $(L_0, L_1)$-光滑性（松弛光滑性）： 不同于假设梯度满足 Lipschitz 连续性的标准光滑性，局部函数满足条件 $\|\nabla f_i(x) - \nabla f_i(y)\| \leq (L_0 + L_1 \|\nabla f_i(x)\|) \|x - y\|$。这一由 Zhang 等人引入的条件更好地刻画了神经网络的训练动态，因为在这些场景中，梯度可能会出现无界或非 Lipschitz 连续的情况。
3. 异质性： 局部函数是异质的，这意味着随机变量 $\xi_i$ 遵循不同的分布 $\mathcal{D}_i$。
4. 去中心化约束： 智能体只能通过混合矩阵 $W$ 与其直接邻居进行通信，这导致了局部变量之间的共识误差（consensus errors）。

方法论：去中心化归一化随机梯度下降 (DNSGD)
作者提出了 DNSGD（算法 2），这是一种旨在处理梯度缺乏 Lipschitz 连续性的新型算法。其核心组件包括：

• 归一化梯度： 算法不使用标准的梯度步，而是使用归一化随机梯度（$v_{i,t} / \|v_{i,t}\|$）进行变量更新。这避免了需要梯度裁剪（gradient clipping）的问题，因为梯度裁剪可能会由于共识误差而在不同智能体之间引入更新模式的不一致。
• 梯度追踪（Gradient Tracking）： 算法采用梯度追踪机制来估计全局梯度方向，利用混合矩阵从邻居处聚合信息。
• 切比雪夫加速（Chebyshev Acceleration）： 为了提高通信效率，算法结合了使用切比雪夫加速的多步共识步骤（算法 1），以减少局部变量与其平均值之间的共识误差。
• 初始化： 使用包含 $K$ 个共识步骤的特定初始化阶段，以确保初始梯度估计器具有足够的对齐性，从而限制初始共识误差。

理论分析与主要贡献
主要的理论挑战在于，现有的去中心化收敛分析依赖于局部梯度的 Lipschitz 连续性或有界性，而这些在 $(L_0, L_1)$-光滑性下并不成立。为了克服这一点，作者做出了以下贡献：

• 新型 Lyapunov 函数： 他们构建了一个新的 Lyapunov 函数 $\Phi_t$，该函数包含了梯度范数与共识误差的乘积：$\Phi_t = f(\bar{x}_t) + C_1 (M_0 + M_1 \|\nabla f(\bar{x}_t)\|) \|X_t - \mathbf{1}\bar{x}_t\| + C_2 \|V_t - \mathbf{1}\bar{v}_t\|$。这种设计专门与松弛光滑条件的测量单位相匹配，使得即使在梯度无界且非 Lipschitz 的情况下也能进行收敛分析。
• 收敛保证： 在标准假设（梯度差异有界、随机梯度方差有界以及网络连通性）下，证明了 DNSGD 可以达到 $\epsilon$-驻点。
• 复杂度界限：
  • 样本复杂度： 每个智能体的样本复杂度为 $O(m^{-1}(L_f \sigma^2 \Delta_f \epsilon^{-4} + \sigma^2 \epsilon^{-2} + L_f^{-2} L_1^3 \sigma^2 \Delta_f \epsilon^{-1} + L_f^{-2} L_1^2 \sigma^2))$，其中 $L_f = L_0 + L_1 \zeta$。
  • 通信复杂度： 通信复杂度为 $\tilde{O}((L_f \epsilon^{-2} + L_1 \epsilon^{-1}) \gamma^{-1/2} \Delta_f)$，其中 $\gamma$ 是网络的谱间隙。
• 特殊情况：
  • 当 $L_1 = 0$（标准光滑性）时，结果与已知的去中心化随机非凸优化的下界相匹配。
  • 当 $m=1$（单机）时，其界限比现有针对松弛光滑性的梯度裁剪方法更紧凑。
  • 该方法实现了相对于智能体数量 $m$ 的线性加速。

实验结果
作者通过在图像分类（MNIST, Fashion-MNIST）和大型语言模型微调（基于 Shakespeare 数据集的 nanoGPT）上的数值实验验证了 DNSGD。

• 基准测试： 与去中心化 SGD (D-SGD)、带有梯度追踪的去中心化 SGD (D-SGT) 以及去中心化归一化平均随机逼近 (D-NASA) 进行了对比。
• 性能： 在 Erdös–Rényi 和环形网络拓扑结构下，DNSGD 在测试准确率相对于样本复杂度和通信轮数的表现上，始终优于基准方法。
• 可扩展性： 通过改变智能体数量（$m=2, 4, 8, 16$）的实验，展示了所提方法的线性加速效应。

意义与主张
本文声称 DNSGD 是第一个在无需依赖梯度裁剪或假设梯度有界的情况下，成功解决 $(L_0, L_1)$-光滑性设定下去中心化随机非凸优化问题的算法。

• 理论新颖性： 引入一个涉及梯度范数与共识误差乘积的 Lyapunov 函数被视为处理去中心化环境下非 Lipschitz 性质的松弛光滑性的必要创新。
• 实际相关性： 通过避免梯度裁剪，该方法避免了因共识误差而产生的更新模式不一致问题，使其在神经网络的实际去中心化训练中更加鲁棒。
• 最优性： 作者指出，在 $L_1=0$ 的特殊情况下，其复杂度界限与理论下界相匹配，这表明其结果在标准光滑情况下接近最优，并且代表了松弛光滑情况下的重大进展。

作者承认，目前的分析依赖于梯度差异有界的假设，将结果扩展到不具备此假设的设定或松弛光滑性下的凸优化问题仍是未来工作的开放课题。