技术摘要：用于凸及非凸问题的去中心化 Frank-Wolfe 算法

问题表述

本文解决了在去中心化网络设置下解决约束优化问题的挑战，特别针对传统基于投影的方法在计算上变得难以处理的高维场景。该问题定义为最小化全局目标函数 $F(\theta)$，其中 $F(\theta)$ 是由 $N$ 个代理持有的局部函数 $f_i(\theta)$ 的平均值组成，并受限于解 $\theta$ 位于闭、有界、凸集 $C$ 之内的约束：

$$\min_{\theta \in \mathbb{R}^d} F(\theta) := \frac{1}{N} \sum_{i=1}^N f_i(\theta) \quad \text{s.t.} \quad \theta \in C$$

代理通过图 $G=(V, E)$ 进行通信，其中 $V$ 代表代理，$E$ 定义了连通性。所解决的主要困难在于，传统的基于投影梯度下降（PGD）的去中心化算法在每次迭代中都需要执行对 $C$ 的投影步骤。对于高维问题（例如矩阵补全或稀疏学习），这种投影步骤通常在计算上是极其昂贵的（例如需要进行完整的奇异值分解或排序操作）。

方法论：去中心化 Frank-Wolfe (DeFW) 算法

为了克服计算瓶颈，作者提出了去中心化 Frank-Wolfe (DeFW) 算法。该方法将经典的 Frank-Wolfe (FW) 或条件梯度算法扩展到了去中心化设置中。其核心创新在于使用受限线性优化（LO）步骤取代了代价高昂的投影步骤，而线性优化对于特定的约束集（如 $\ell_1$ 球或迹范数球）通常是非常高效的。

算法结构

DeFW 算法在迭代 $t$ 中运行。在每一步中，代理执行三个主要动作：

1. 共识（迭代近似）： 代理使用近邻信息交换（平均共识）来近似全局平均迭代值 $\bar{\theta}_t$。令 $\bar{\theta}_i^t$ 表示代理 $i$ 的局部近似值。
2. 聚合（梯度近似）： 代理近似全局梯度 $\nabla F(\bar{\theta}_t)$。由于代理只能访问局部梯度 $\nabla f_i(\bar{\theta}_i^t)$，他们计算一个局部梯度近似 $\nabla_i^t F$。为了高效实现这一点而不增加多次通信轮数，作者采用了梯度追踪机制（受 SAGA 启发）。代理维护一个代理梯度 $\nabla_i^t F$，其更新方式为：
   $$\nabla_i^t F = \nabla_i^{t-1} F + \nabla f_i(\bar{\theta}_i^t) - \nabla f_i(\bar{\theta}_i^{t-1})$$
   随后，该代理梯度通过一轮共识在网络中进行平均。
3. Frank-Wolfe 步骤： 每个代理利用其局部梯度近似在 $C$ 上求解一个线性优化问题，以找到方向 $a_i^t$：
   $$a_i^t \in \arg\min_{a \in C} \langle \nabla_i^t F, a \rangle$$
   随后迭代按凸组合进行更新：
   $$\theta_i^{t+1} = (1 - \gamma_t)\bar{\theta}_i^t + \gamma_t a_i^t$$
   其中 $\gamma_t$ 是递减步长。

收敛分析框架

作者通过将 DeFW 视为一种不精确的 FW 算法来分析其收敛性。他们针对局部近似的准确性建立了两个关键假设：

• 假设 1： 迭代值的共识误差衰减为 $\max_i \|\bar{\theta}_i^t - \bar{\theta}_t\| \leq \Delta_{p,t}$。
• 假设 2： 梯度的共识误差衰减为 $\max_i \|\nabla_i^t F - \nabla_t F\| \leq \Delta_{d,t}$。

论文证明，使用固定通信轮数（具体为一轮迭代和一轮梯度代理）的基于共识的实现满足这些假设，且 $\Delta_{p,t}, \Delta_{d,t} = O(1/t^\alpha)$。

核心贡献与理论结果

1. 收敛速率

论文为不同目标函数性质下的 DeFW 提供了严谨的收敛保证：

• 凸目标函数： 使用步长 $\gamma_t = 2/(t+1)$ 时，目标值的次优性以 $O(1/t)$ 的速率收敛。
• 强凸目标函数： 如果最优解位于约束集 $C$ 的内部，收敛速率提升至 $O(1/t^2)$。
• 非凸目标函数： 对于光滑但非凸的目标函数，算法收敛至一个驻点。当步长设为 $\gamma_t = 1/\sqrt{t}$ 时，FW 间隙（衡量驻点的度量）以 $O(1/\sqrt{t})$ 的速率衰减。作者指出，该速率与中心化投影梯度方法在处理非凸问题时的速率相当。

2. 基于共识的实现

一个重要的贡献是证明了这些理论保证可以通过常数次通信轮数（具体为两轮：一轮用于迭代，一轮用于梯度代理）来实现。这是通过特定的梯度追踪更新规则实现的，该规则避免了在去中心化设置中为了达到高精度共识通常需要的对数级通信轮数。

3. 用于通信效率的稀疏化 DeFW

针对 LASSO 等通信带宽成为瓶颈的应用场景，作者提出了稀疏化 DeFW 变体。在该版本中，代理仅交换梯度代理的一个子集坐标（可以是随机选择的，也可以是模长最大的坐标）。理论分析表明，通过适当选择坐标数量，该算法可以在保持标准 DeFW 收敛保证的同时，显著降低通信成本。

应用与数值结果

论文在两个特定应用中验证了 DeFW 算法：

1. 去中心化矩阵补全：

   • 问题： 从分布在各代理处的残缺、含噪声的观测中恢复低秩矩阵。
   • 约束： 迹范数球（促进低秩性）。
   • 结果： DeFW 成功恢复了矩阵，其收敛速率符合理论预测。由于避免了完整的 SVD 投影，它在单次迭代的计算时间上优于去中心化投影梯度（DPG）方法。在使用非凸负高斯损失函数时，该算法还展示了对稀疏噪声的鲁棒性。

2. 通信高效的稀疏学习 (LASSO)：

   • 问题： 带有 $\ell_1$ 约束的分布式稀疏线性回归。
   • 约束： $\ell_1$ 球（促进稀疏性）。
   • 结果： 稀疏化 DeFW 算法在通信成本与准确度之间取得了良好的平衡。实验表明，在低精度区间内，其通信效率优于 DPG 和 PG-EXTRA，并能匹配迭代硬阈值（BHT）的表现，同时提供了更好的通信与计算复杂度平衡。

意义与主张

论文声称提出了第一个去中心化 Frank-Wolfe 算法。其意义在于：

• 可扩展性： 通过消除投影步骤，DeFW 使去中心化优化能够应用于高维问题（如大规模矩阵补全或高维稀疏学习），这些问题在这些场景下投影成本过高。
• 非凸保证： 它提供了最早针对非凸目标函数的去中心化无投影方法的收敛分析之一，建立了与中心化方法相当的驻点收敛速率。
• 通信效率： 基于共识的实现通过极少的、常数次的通信轮数即可实现这些保证，使其适用于带宽受限的网络。
• 实际效用： 在合成数据和真实世界数据（MovieLens）上的数值实验证实，该算法不仅在理论上成立，而且在实践中也非常高效，在运行时和鲁棒性方面通常优于最先进的去中心化梯度方法。

作者总结道，虽然目前的工作侧重于同步、静态网络，但未来的研究方向包括开发 DeFW 算法的异步版本。