技术摘要：具有高效通信的分布式在线凸优化

1. 问题定义

本文研究了在压缩通信约束下的分布式在线凸优化 (D-OCO)。在这种设定下，$n$ 个学习者通过一个无向图 $G = ([n], E)$ 连接。在每个轮次 $t \in [T]$ 中，每个学习者从凸集 $X \subseteq \mathbb{R}^d$ 中选择一个决策 $x_i(t)$，并承受局部损失 $f_{t,i}(x_i(t))$。其集体目标是最小化全局累积损失，定义为 $f_t(x) = \sum_{j=1}^n f_{t,j}(x)$。

主要挑战在于通信瓶颈。当 $n$ 较大时，学习者之间传输完整的梯度或决策向量的成本非常高。为了缓解这一问题，学习者使用压缩算子 $C(\cdot)$ 来传输压缩后的数据。压缩的质量由因子 $\omega \in (0, 1]$ 表征，其中 $\omega=1$ 表示无压缩，$\omega$ 越小表示压缩率越高（且可能产生更高的误差）。通信网络由一个双随机矩阵 $P$ 表征，其谱间隙为 $\rho = 1 - \sigma_2(P) \in (0, 1]$。

性能指标是遗憾值 (Regret)：
$$R(T, i) = \sum_{t=1}^T \sum_{j=1}^n f_{t,j}(x_i(t)) - \min_{x \in X} \sum_{t=1}^T \sum_{j=1}^n f_{t,j}(x)$$

先前的工作（特别是 Tu 等人，2022 年）针对凸函数建立了 $\tilde{O}(\max\{\omega^{-2}\rho^{-4}n^{1/2}, \omega^{-4}\rho^{-8}\}n\sqrt{T})$ 的遗憾界限。作者指出，这些界限对 $\omega^{-1}$ 存在二次或四次依赖，并且对 $n$ 存在超线性依赖，这对于大规模、高压缩系统是不理想的。

2. 方法论：Top-DOGD

作者提出了一种名为两层压缩去中心化在线梯度下降 (Top-DOGD) 的新算法。其核心技术贡献是一个两层分块更新框架，该框架整合了两种特定的策略，用以控制共识误差、压缩误差和投影误差。

2.1. 两层分块框架

算法并不在每一轮都更新决策，而是将总的 $T$ 轮划分为大小为 $L = L_1 + L_2$ 的块。在每个块内，决策 $x_i(b)$ 保持不变，仅在块结束时进行更新。这种结构允许算法在块内的轮次中分布多次通信轮次，从而在满足每轮仅一次通信约束的同时，实现更复杂的误差修正。

2.2. 策略 1：在线压缩 Gossip（$L_1$ 轮）

为了解决共识误差（学习者之间的分歧）和压缩误差，算法在每个块的前 $L_1$ 轮中采用了多步 Gossip 协议。

• 学习者执行多步 Choco-gossip 协议（Koloskova 等人，2019），该协议使用差分压缩来追踪邻居的状态。
• 通过设置 $L_1 = \lceil 2 \ln(14n) / (\gamma \rho) \rceil$，算法确保共识误差和压缩误差呈指数级衰减，从而实现比单步 Gossip 更紧密的界限。

2.3. 策略 2：投影误差补偿（$L_2$ 轮）

在 D-OCO 中，学习者必须在每一步将决策投影到可行域 $X$ 上。这种投影会引入投影误差，而在以往的方法中，这会导致遗憾界限中出现 $O(n)$ 的依赖项。

• 作者提出了一个投影误差补偿方案。学习者递归地压缩投影误差的残差（$r_i = \Pi_X(y) - y$），并将这些残差传输给邻居。
• 通过在 $L_2 = \lceil \ln(8n) / \omega \rceil$ 轮中使用重复压缩器（Huang 等人，2022），投影残差的压缩误差被降低到 $O(1/n)$。
• 这有效地消除了由投影误差引起的对 $n$ 的线性依赖，这是先前工作的一个关键局限。

3. 核心贡献与结果

3.1. 改进的遗憾界限

本文为凸函数和强凸损失函数建立了显著改进的遗憾界限，展示了对压缩率 $\omega$、谱间隙 $\rho$ 和学习者数量 $n$ 的更优依赖关系。

• 凸函数：
  • 先前工作 (Tu et al., 2022)： $O(\max\{\omega^{-2}\rho^{-4}n^{1/2}, \omega^{-4}\rho^{-8}\}n\sqrt{T})$
  • 本研究： $\tilde{O}(\omega^{-1/2}\rho^{-1}n\sqrt{T})$
• 强凸函数：
  • 先前工作 (Tu et al., 2022)： $O(\max\{\omega^{-2}\rho^{-4}n^{1/2}, \omega^{-4}\rho^{-8}\}n \ln T)$
  • 本研究： $\tilde{O}(\omega^{-1}\rho^{-2}n \ln T)$

符号 $\tilde{O}$ 隐藏了常数因子以及关于 $n$ 的多项式对数因子。这种改进在将 $\omega$ 的依赖从二次/四次降低到平方根/线性，以及降低对 $n$ 的依赖方面尤为显著。

3.2. 下界

作者建立了压缩通信下 D-OCO 的首次下界，证明了其结果的近乎最优性：

• 凸函数： $\Omega(\omega^{-1/2}\rho^{-1/4}n\sqrt{T})$
• 强凸函数： $\Omega(\omega^{-1}\rho^{-1/2}n \ln T)$

这些下界在 $\rho$ 和 $n$ 的多项式对数项方面与 Top-DOGD 的上界相匹配，证实了该算法对 $\omega$ 和 $T$ 的依赖本质上是接近最优的。

3.3. 向 Bandit 反馈的扩展

该方法通过经典的梯度估计器扩展到了 Bandit 反馈设置（即仅可获得损失值而非梯度）：

• 单点反馈 (One-point feedback)： 对于凸函数实现 $\tilde{O}(\omega^{-1/4}\rho^{-1/2}d^{1/2}n T^{3/4})$，对于强凸函数实现 $\tilde{O}(\omega^{-1/3}\rho^{-2/3}d^{2/3}n T^{2/3}(\ln T)^{1/3})$。
• 两点反馈 (Two-point feedback)： 对于凸函数实现 $\tilde{O}(\omega^{-1/2}\rho^{-1}dn\sqrt{T})$，对于强凸函数实现 $\tilde{O}(\omega^{-1}\rho^{-2}d^2n \ln T)$。
  这些结果同样改进了 Bandit 设置下的现有界限。

4. 意义与主张

本文声称，所提出的 Top-DOGD 算法通过显式地处理去中心化、压缩和投影之间的相互作用，克服了以往通信高效方法的局限性。

• 最优性： 建立下界为改进后的 $\omega$ 和 $T$ 的依赖关系提供了理论依据，表明在不改变问题设定前提下，无法进一步显著改进这些依赖关系。
• 可扩展性： 降低对 $n$ 和 $\omega$ 的依赖，使得该算法更适用于通信带宽受限且代理数量庞大的大规模分布式系统。
• 统一框架： 两层分块更新结构被呈现为一个统一的框架，它成功地整合了在线压缩 Gossip 和误差补偿，解决了需要在更新过程中进行多次通信轮次，却又要维持整体时间线上单轮一次通信的矛盾。

作者强调，其研究结果代表了在通信受限的分布式在线学习领域，对理论理解的一次进步，为更高效的分布式算法在流式数据环境中的应用奠定了基础。