Revisiting Decentralized Online Convex Optimization with Compressed Communication¶

会议: NeurIPS 2026
arXiv: 2607.01665
论文: https://arxiv.org/abs/2607.01665
领域: 优化/理论
关键词: 分布式在线凸优化、通信压缩、FTRL、Bandit反馈、平均共识

一句话总结¶

针对分布式在线凸优化中的通信瓶颈与复杂投影耦合难题，首次提出基于正则化跟随领导者（FTRL）的压缩通信算法，利用对偶变量共识天然解耦约束集投影，并在Bandit设定下同时实现更优遗憾界与次线性通信轮数。

研究背景与动机¶

分布式在线凸优化（Decentralized Online Convex Optimization, D-OCO）是流式数据环境下多智能体协同学习的核心理论框架。在传统无中心网络中，各个节点仅能与即时邻居交换信息，且需在对抗环境下逐轮做出决策并承受未知凸损失。随着模型维度和网络规模膨胀，高频传输全精度稠密梯度的通信开销成为制约系统吞吐的核心瓶颈。为缓解这一矛盾，引入量化或稀疏化等有损压缩算子的通信压缩 D-OCO 应运而生。然而，现有压缩通信算法无一例外均沿袭在线梯度下降（OGD）范式，即在原始决策空间中结合 Choco-Gossip 等压缩共识机制推进迭代。

这种基于 OGD 范式的算法架构面临着根本性的理论与设计困境：在受限凸集决策场景中，每次梯度下降后必须执行非线性投影算子以保证可行性。当网络通信存在压缩误差时，非线性投影会恶化局部决策之间的共识偏差（consensus error），使得共识误差分析极其繁复。近期 SOTA 工作（如 Yang et al., 2026）不得不引入复杂的双层分块更新机制和重复压缩器来强行抑制投影导致的误差发散。而在精确通信领域，早已证明基于正则化跟随领导者（FTRL）的双对偶更新具备更优的理论性质与稳定性。这就引出一个关键理论悬念：FTRL 范式能否推广至压缩通信环境？这种推广能否打破 OGD 的设计桎梏？

本文的切入视角正是利用 FTRL 的对偶更新机制彻底绕开投影困境。在 FTRL 框架下，节点间通信与共识维护的对象不是受约束的原始决策，而是对应累积平均梯度的无约束对偶变量；原始决策仅是对偶变量映射到可行域上的确定性解，非线性投影发生在共识之后而非共识环路之内。核心 idea：将 FTRL 对偶变量平均共识与带灵活初始化的 Choco-Gossip 紧密结合，从根源上消除凸集投影对压缩共识误差的病态放大，并在 Bandit 设定下利用大块更新解耦探索噪声与网络拓扑，首次同时实现更优遗憾界与次线性通信轮数。

方法详解¶

整体框架¶

算法面向包含 \(n\) 个节点的无向网络 \(\mathcal{G}=([n], E)\)，网络拓扑由双随机对称打乱矩阵 \(A \in \mathbb{R}^{n\times n}\) 描述，谱间隙为 \(\rho = 1 - \lambda_2(A)\)。有损压缩算子 \(Q(\cdot)\) 满足压缩比参数 \(\omega \in (0, 1]\) 的标准压缩约束 \(\mathbb{E}[\|Q(\mathbf{x})-\mathbf{x}\|_2^2] \le (1-\omega)\|\mathbf{x}\|_2^2\)。论文设计了两套算法：面向全信息反馈的 CD-FTGL（Compressed Decentralized Follow-The-Generalized-Leader）与面向单点观测的 CD-FTBL（Compressed Decentralized Follow-The-Bandit-Leader）。

在宏观流程上，系统将总轮数 \(T\) 划分为若干长度为 \(L\) 的时间块（block）。在每个块内，节点保持决策 \(\mathbf{x}_i(z)\) 不变并执行在线决策；同时收集块内梯度或 Bandit 梯度估计并累加为局部代理梯度 \(\mathbf{d}_i(z)\)。在块交替阶段，节点无需在原始决策空间做带投影的邻域加权，而是将历史对偶变量 \(\mathbf{z}_i(z)\) 注入改进的 Choco-Gossip 通信协议，通过多轮压缩差分传输实现对偶变量的邻居平均。最后，各节点在本地独立求解关于对偶变量的正则化优化问题，生成下一块的决策向量。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["环境输入：在线凸损失序列与网络拓扑"] --> B["时间分块与局部采样决策"]
    B --> C["对偶变量热启动与历史状态保持"]
    C --> D["改进 Choco-Gossip 差分压缩共识"]
    D --> E["无投影干扰的对偶变量收敛更新"]
    E --> F["本地 FTRL 正则化映射与缩放约束投影"]
    F --> G["输出下一块决策并达成次线性遗憾"]

关键设计¶

1. 任意初始化的精细化 Choco-Gossip：突破历史渐近收敛瓶颈 针对分布式平均共识在压缩通信下的收敛问题，论文重构并强化了 Choco-Gossip 的收敛性理论保证。经典 Choco-Gossip 理论严格绑定于全零初值，得到的单步收缩率无法退化到精确通信下的标准 Gossip 界 \(O((1-\rho)^k)\)。本文证明对于任意初始向量和相容的辅助压缩状态，只要设计特定的步长参数 \(\gamma = \frac{\rho\omega}{2(1-\omega)(\rho+2)\beta^2 + 16\rho - 8\rho\omega + \rho^2}\)（其中 \(\beta = \|I-A\|_2\)），总共识误差 \(e^k = \mathbb{E}[\sum_{i=1}^n \|\mathbf{z}_i^k - \bar{\mathbf{z}}^k\|_2^2] + \mathbb{E}[\sum_{i=1}^n \|\mathbf{z}_i^k - \hat{\mathbf{z}}_i^k\|_2^2]\) 就能严格满足线性收缩关系：

\[e^k \le \left(1 - \frac{\gamma\rho}{2}\right)^k e^0\]

该设计使得 Choco-Gossip 在整个在线流式优化过程中支持即插即用的热启动，且当 \(\omega=1\) 时可完美恢复出 \(O((1-\omega\rho)^k)\) 的标准无压缩共识速率，为后续对偶变量跨块连续追踪奠定了数学基石。

2. 对偶变量共识与热启动机制：将约束投影彻底剥离通信环路 在 OGD 范式中，局部决策更新与投影算子交替进行，非线性投影导致压缩误差在网络中逐轮累积放大，必须借助复杂的多级重复压缩策略去控制。CD-FTGL 独辟蹊径，将通信共识的对象完全限定在无约束对偶空间。在第 \(z\) 个时间块开始时，各节点将上一块累积的局部代理梯度 \(\mathbf{d}_i(z-1) = \sum_{t\in\mathcal{T}_{z-1}} (\nabla f_{t,i}(\mathbf{x}_i(z-1)) - \alpha\mathbf{x}_i(z-1))\) 直接注入对偶变量初值：

\[\mathbf{z}_i^0(z) = \mathbf{z}_i(z-1) + \mathbf{d}_i(z-1)\]

同时保留上一块末尾的压缩副本 \(\hat{\mathbf{z}}_i(z-1)\) 和邻居聚合状态 \(\mathbf{s}_i(z-1)\) 作为 Choco-Gossip 的热启动输入。由于对偶变量处于全空间 \(\mathbb{R}^d\)，压缩共识的迭代过程完全不受可行域 \(\mathcal{K}\) 几何结构与投影算子的任何干扰。通信收敛后，本地决策仅需执行一次标准 FTRL 映射：

\[\mathbf{x}_i(z+1) = \arg\min_{\mathbf{x}\in\mathcal{K}} \left\langle \mathbf{z}_i(z), \mathbf{x} \right\rangle + \frac{(z-1)L\alpha + 2h}{2}\|\mathbf{x}\|_2^2\]

这种机制将投影降级为本地后处理步骤，从而使理论分析中的共识误差界与约束投影误差界完全解耦。

3. 尺度缩放可行域与大块更新解耦：Bandit 设定下的次线性通信飞跃 在更严苛的 Bandit 设定下，节点仅能探测标量损失值 \(f_{t,i}(\mathbf{y}_i(t))\)。传统做法受限于高方差的单点梯度估计，被迫每轮都进行网络通信。CD-FTBL 引入球面扰动探索 \(\mathbf{y}_i(t) = \mathbf{x}_i(z) + \epsilon \mathbf{u}_i(t)\)（其中 \(\mathbf{u}_i(t) \sim \mathcal{S}^d\)），并创新性地将基准决策 \(\mathbf{x}_i\) 约束在向内收缩的可行域 \(\mathcal{K}_\epsilon = (1-\epsilon/r)\mathcal{K}\) 内，严格保障了扰动探索点 \(\mathbf{y}_i(t) \in \mathcal{K}\)。更关键的是，作者打破了通信轮数 \(K\) 与时间块大小 \(L\) 强制相等的直觉束缚：令 Choco-Gossip 通信轮数仅取决于网络拓扑与压缩比 \(K = \lceil 2\ln(n+2)/(\gamma\rho) \rceil\)，而将决策更新块长大幅放宽至 \(L = \max\{K, \sqrt{T}\}\)（凸函数）或 \(L = \max\{K, T^{2/3}(\ln T)^{-2/3}\}\)（强凸函数）。由于每个块内仅在块切换时通信 \(K\) 轮，算法成功将总通信轮数从 \(O(T)\) 大幅削减至次线性的 \(\tilde{O}(\omega^{-1}\rho^{-2}\sqrt{T})\)，并让网络拓扑谱间隙与压缩比仅进入遗憾界的非主导阶次。

损失函数 / 训练策略¶

算法针对凸函数（\(\alpha=0\)）与 \(\alpha\)-强凸函数给出了精确的闭式参数调优策略： - 全信息 CD-FTGL：设置块长 \(L = K = \lceil 2\ln(n+2)/(\gamma\rho) \rceil\)。对一般凸问题选取正则化参数 \(h = 3\sqrt{LT}G/R\)，达到 \(\mathbb{E}[R_{T,i}] \le 6nGR\sqrt{LT} = \tilde{O}(\omega^{-1/2}\rho^{-1}n\sqrt{T})\)；对强凸问题选取 \(h = \alpha L\)，达到 \(\tilde{O}(\omega^{-1}\rho^{-2}n\log T)\)，全面对齐已有下界。 - Bandit CD-FTBL：在一般凸问题下设置探索半径 \(\epsilon = c\sqrt{d}T^{-1/4}\)，块长 \(L = \max\{K, \sqrt{T}\}\)，正则化参数 \(h = \sqrt{dLT}M/R\)，实现 \(\mathbb{E}[R_{T,i}] = O(nT^{3/4} + n\sqrt{KT})\)，当 \(T\) 充分大时遗憾严格收敛为 \(O(nT^{3/4})\)，且总通信轮数仅为 \(TK/L = \tilde{O}(\omega^{-1}\rho^{-2}\sqrt{T})\)。

实验关键数据¶

主实验¶

实验基于 LIBSVM 的两个标准基准数据集 ijcnn1（\(d=22\)）与 a9a（\(d=123\)）开展分布式在线逻辑回归评估，总轮数 \(T=10,000\)。默认网络拓扑为包含 \(n=9\) 个节点、18 条边的随机图 \(\mathcal{G}(n, 2n)\)，压缩算子采用 Top-\(k\) 稀疏压缩（默认压缩比 \(\omega=0.1\)）。对比基线涵盖全信息算法 Top-DOGD（Yang et al., 2026）、DC-DOGD（Tu et al., 2022）以及 Bandit 算法 Top-DOBD-1（Yang et al., 2026）、DC-DOBD（Tu et al., 2022）。评估指标采用时均累积损失（Average Cumulative Loss, AL）。

算法设定	算法名称	理论遗憾界（凸损失）	理论通信轮数（凸损失）	ijcnn1 最终损失 (\(\omega=0.1\))	a9a 最终损失 (\(\omega=0.1\))	实际传输比特效率
全信息	DC-DOGD (Tu et al., 2022)	\(O(\omega^{-2}\rho^{-4}n^{3/2}\sqrt{T})\)	\(O(T)\)	约 0.285	约 0.380	较慢收敛
全信息	Top-DOGD (Yang et al., 2026)	\(\tilde{O}(\omega^{-1/2}\rho^{-1}n\sqrt{T})\)	\(O(T)\)	约 0.245	约 0.362	中等收敛
全信息	CD-FTGL (本文)	\(\tilde{O}(\omega^{-1/2}\rho^{-1}n\sqrt{T})\)	\(O(T)\)	约 0.228	约 0.354	最优（左移明显）
Bandit	DC-DOBD (Tu et al., 2022)	\(O(\omega^{-1}\rho^{-2}n^{5/4}T^{3/4})\)	\(O(T)\)	约 0.440	约 0.475	开销巨大
Bandit	Top-DOBD-1 (Yang et al., 2026)	\(\tilde{O}(\omega^{-1/4}\rho^{-1/2}nT^{3/4})\)	\(O(T)\)	约 0.350	约 0.420	需完整 10,000 轮
Bandit	CD-FTBL (本文)	\(O(nT^{3/4})\)	\(\tilde{O}(\omega^{-1}\rho^{-2}\sqrt{T})\)	约 0.315	约 0.395	仅约 2,000 轮通信

消融实验¶

在固定时间块大小 \(L=100\) 的条件下，针对 Bandit 算法 CD-FTBL 检验每个块内通信轮数 \(K\) 对最终收敛性能与传输代价的权衡敏感度（基于 ijcnn1 与 a9a 数据集，评估不同压缩比 \(\omega \in \{0.5, 0.1, 0.05\}\) 下的表现）：

配置 (\(L=100, \omega=0.1\))	块内通信轮数 \(K\)	总通信轮数 (\(TK/L\))	ijcnn1 收敛阶段相对速率	最终时均损失表现	特性说明
极低频通信配置	\(K = \lceil L/20 \rceil = 5\)	约 500 轮	极快（极少轮数即显著下降）	略有上升（约 0.332）	激进压缩传输，适合通信强受限网络
标准推荐配置	\(K = \lceil L/5 \rceil = 20\)	约 2,000 轮	快速且稳定	优异（约 0.315）	理论与实践的最佳折中平衡点
密集通信配置	\(K = \lceil L/2 \rceil = 50\)	约 5,000 轮	前期轮数开销偏高	接近全通（约 0.311）	精度提升微弱，通信收益边际递减
全通信基准	\(K = L = 100\)	10,000 轮	吞吐受制于网络通信	0.310	丧失次线性轮数优势

关键发现¶

通信轮数与比特数的双重节约：CD-FTBL 在仅消耗约 2,000 轮通信（相比基线的 10,000 轮降低 80%）的情况下，平均累积损失仍显著优于需要全轮次通信的 Top-DOBD-1 和 DC-DOBD，验证了次线性通信理论的成立。
对偶解耦带来的经验加速：在全信息场景下，虽然 CD-FTGL 与 Top-DOGD 具有相同的理论上界，但由于消除了投影对共识环路的扰动，CD-FTGL 在两种数据集下的 Loss-vs-Bits 曲线均明显左移，表明更低的瞬时通信量即可换取更平稳的模型收敛。
网络规模扩展性完备：在包含 \(n=50\) 节点、100 条边的大规模图网络拓展实验中，CD-FTGL 与 CD-FTBL 依然全面保持对 OGD 类基线的精度与传输效率优势。

亮点与洞察¶

对偶空间共识的四两拨千斤：传统 D-OCO 陷入“在决策空间做共识就要承受投影扭曲”的思维定势，本文改在累积梯度对应的对偶变量空间执行 Choco-Gossip，使复杂的非线性约束投影退化为纯本地求解，从底层结构上化解了理论分析阻碍。
理论边界从有偏到解耦：在 Bandit 场景中，以往算法的遗憾界主导项中深度交织着网络谱间隙 \(\rho\) 与压缩比 \(\omega\)。CD-FTBL 巧妙通过块长解耦，使得 \(\rho\) 和 \(\omega\) 仅停留在低阶非主导项中，当 \(T\) 增大时实现了通信拓扑效应与强化探索噪声的彻底分离。
通信压缩与轮数跳跃的共生：这是首个在 D-OCO 领域同时做到“单次通信传输比特压缩”与“总通信发生轮数次线性缩减”的算法框架，为未来边缘多智能体系统的通信能效优化提供了重要理论范式。

局限与展望¶

加速 Gossip（Accelerated Gossip）尚未融合：CD-FTGL 在 \(\omega=1\) 时可恢复标准 Gossip 的最优点，但与基于切比雪夫多项式加速机制的 AD-FTGL 相比在谱间隙 \(\rho\) 的依赖上仍存在差距。如何在压缩通信下结合多步记忆加速机制是明确的理论悬念。
块大小下界的理论约束：算法在全信息下依赖块长 \(L \ge 1\) 的分块结构以协调通信与计算。未来仍需进一步探究在不分块（即 \(L=1\) 单步更新）情形下能否维持相同的紧致界。

评分¶

新颖性: ⭐⭐⭐⭐⭐ [首次将 FTRL 范式引入压缩通信分布式在线优化，对偶共识解耦投影极具启发性]
实验充分度: ⭐⭐⭐⭐☆ [覆盖全信息与Bandit双场景，跨越不同网络规模与压缩比，理论与经验吻合度高]
写作质量: ⭐⭐⭐⭐⭐ [理论推导脉络严密清晰，动机自然流畅，问题定位极其尖锐精准]
价值: ⭐⭐⭐⭐⭐ [在理论上刷新了 D-OCO Bandit 界的 SOTA，同时在工程层面给出了极致节省带宽的优雅实现]