技术摘要：用于鲁棒且非平滑去中心化学习的快速高效 gossip 算法

1. 问题表述

本文解决了资源受限边缘设备上去中心化学习的挑战。在此设定下，通过图 $G=(V, E)$ 连接的 $n$ 个智能体协作求解如下形式的极小化问题：
$$\arg\min_{x \in \mathbb{R}^d} \sum_{i=1}^n f_i(x)$$
其中每个局部目标函数 $f_i$ 是闭的、真凸的，并且可能是非平滑的。

具体的动机源于对抗数据篡改（例如异常值或故障传感器）的鲁棒性需求。鲁棒统计量，如中位数、分位数和几何中位数，能有效抵抗篡改，但需要最小化非平滑损失函数（例如用于分位数的分位数损失）。虽然标准的 gossip 算法具有通信效率，但它们主要针对平滑损失设计。现有的非平滑目标方法，如基于异步 ADMM 的方法（例如 AsyncADMM、DAPD），通常需要存储与节点度（$d_k$）成比例的辅助变量。具体而言，先前的方法要求每个节点存储 $2d_k + 1$ 个变量，这对于稠密图或内存受限的设备来说变得不切实际。

2. 方法论：AsylADMM

作者提出了AsylADMM（异步轻量级 ADMM），这是一种新颖的 gossip 算法，旨在以最小的内存开销处理非平滑凸去中心化优化问题。

核心设计原则

1. 内存效率：与先前存储特定边对偶变量和邻居状态的异步 ADMM 方法不同，AsylADMM 要求每个节点仅存储两个变量：

   • 原始变量 $x_k$。
   • 单个聚合对偶变量 $\hat{\mu}_k$。
     这将内存占用从 $O(d_k)$ 降低到 $O(1)$，且独立于节点度。

2. 算法结构：

   • 重参数化：该算法通过聚合对偶变量重新表述了标准 ADMM 更新。节点不再为每条入射边维护单独的对偶变量，而是维护一个单一的聚合量 $\hat{\mu}_k = \sum_{e \in N_k} y_{e,k} / d_k$。
   • 启发式更新：在异步设定中，当边 $e=(i, j)$ 被激活时：
     • 节点计算新的成对平均值 $z_e = (x_i + x_j)/2$。
     • 它们利用当前边约束更新局部对偶聚合量：$\hat{\mu}_k \leftarrow \hat{\mu}_k + \rho(z_e - x_k)/d_k$。
     • 它们执行近端更新：$x_k \leftarrow \text{prox}_{f_k/(\rho d_k)}(z_e + \hat{\mu}_k/\rho)$。
   • 关键区别：该算法使用被激活边的两个端点的当前信息进行原始更新，而不是依赖存储在辅助状态中的过时邻居平均值。

3. 同步变体：作者还定义了该算法的同步版本，其中所有节点同时更新，作为理论基线。

3. 理论贡献

本文提供了两个主要理论结果：

1. 同步变体的收敛性：

   • 作者为其重排序 ADMM 变体（更新顺序为 $z \to y \to x$）的同步版本建立了新的收敛性分析。
   • 使用修正的 Lyapunov 函数 $V^t = \|\tilde{y}^t - \rho M \tilde{x}^t\|^2$，他们证明了原始残差收敛至零（$\|r^t\| \to 0$），且目标值收敛至最优值（$f(x^t) \to f(x^*)$）。

2. AsylADMM 的简化分析：

   • 由于近端算子的非线性和启发式方法的使用，异步非平滑情况的完整收敛性证明被指出是非平凡的。
   • 相反，作者使用平方损失（均值估计）和步长 $\rho \le 1$，提供了简化设定下的收敛性分析。
   • 他们证明了对于 $\rho \le 1$，该算法几乎必然收敛。
   • 特例（$\rho = 1$）：他们证明了当 $\rho = 1$ 时，AsylADMM 精确恢复了经典的成对平均gossip 算法，从而建立了与广泛研究的共识协议的形式化联系。

4. 实证结果

在各种非平滑问题上进行了广泛的实验，包括中位数估计、分位数估计、几何中位数、Lasso 回归和鲁棒回归（最小截断平方和）。

• 性能：AsylADMM 在各种网络拓扑（几何图、Watts-Strogatz 图、环图）和数据分布（包括受污染的高斯数据）中，始终比现有基线（AsyncADMM、DAPD 和次梯度下降）收敛得更快。
• 稳定性：与基线相比，所提出的方法在试验中表现出更低的方差，而基线通常难以在使用过时信息和内存约束之间取得平衡。
• 内存效率：该算法在仅存储每个节点两个变量的情况下保持了高性能，验证了其适用于资源受限环境。
• 步长敏感性：实证结果表明，对于几何图上的均值估计，选择 $\rho > 1$（具体为 $\rho = 2$）可以显著加速收敛，尽管提供的理论保证仅针对 $\rho \le 1$。
• 鲁棒性：在鲁棒回归任务（最小截断平方和）中，AsylADMM 有效地识别并剔除异常值，在最终参数误差方面优于标准 OLS 和 Huber 回归。

5. 意义与主张

本文主张 AsylADMM 开启了通往鲁棒且非平滑去中心化学习的实用路径。其主要意义在于：

• 弥合差距：它成功地将非平滑优化的鲁棒性（通过近端方法）与 gossip 算法的通信效率相结合，同时避免了先前异步 ADMM 方法中 prohibitive 的内存成本。
• 可扩展性：通过将每个节点的内存需求降低为常数，它使得在大规模、稠密的边缘设备网络上部署鲁棒学习算法成为可能，而先前的方法在这些场景中是不切实际的。
• 理论基础：它提供了针对该特定重排序 ADMM 结构的同步变体的首个收敛性分析，并通过平方损失简化提供了对异步情况的理论见解。

作者指出，虽然实证结果很强，但针对一般非平滑异步情况的完整理论收敛性分析仍然是未来工作的一个开放问题。