Distributed Online Convex Optimization with Compressed Communication: Optimal Regret and Applications¶

会议: NeurIPS 2026
arXiv: 2604.09276
领域: 优化/理论
关键词: 分布式在线凸优化, 压缩通信, 误差反馈, FTRL, 匹配下界

一句话总结¶

针对带约束域的分布式在线凸优化中压缩误差与投影误差相互耦合导致发散的难题，本文通过将误差反馈机制融合进 FTRL 框架解耦投影误差，并结合块化在线压缩策略消除双向压缩放大效应，首次达成了凸与强凸损失下的最优后悔界及离线随机非光滑收敛率。

研究背景与动机¶

分布式在线凸优化（Distributed Online Convex Optimization, D-OCO）是处理流式数据环境下大规模序列决策与分布式学习任务（如移动端预测、车联网自主决策、在线推荐系统等）的基础数学范式。在典型的星型参数服务器拓扑中，各本地节点同步作出全局决策并遭受损失后，需将本地梯度或梯度信息上传至中心服务器，由服务器聚合全局梯度后再广播下发给各节点更新决策。然而，随着决策变量维度急剧扩张与流式轮数累积，节点与中心服务器之间频繁交换高维全精度梯度的通信开销已成为最严峻的系统瓶颈。

在非分布式或去中心化优化中，引入梯度压缩算子（如 Sign 算子、Rand-K 压缩）是降低传输带宽的常用手段，但简单使用有偏压缩会导致累积压缩误差无界发散。传统非约束优化常采用误差反馈（Error Feedback, EF）机制，通过维护历史未传输残差并将其叠加至下一轮压缩输入来控制累积误差。然而，当面临实际场景中不可或缺的凸闭可行域约束 \(\mathcal{W}\) 时，各节点每轮必须进行欧氏投影更新 \(\mathbf{w}^{t+1} = \Pi_{\mathcal{W}}[\mathbf{w}^t - \eta \mathcal{C}(\cdot)]\)。投影操作的非线性直接将投影截断误差与内部压缩误差深度耦合在一起，使得经典基于 OGD 的误差界分析失效，导致误差沿迭代路径呈雪崩式传播积累。此外，上下行双向通信压缩会进一步放大这一残差扩散过程。

面对上述理论瓶颈，本文的核心突破口在于：从根本上摒弃梯度下降的迭代递推更新形式，转向直接对历史聚合信息施加正则化优化的 FTRL 范式，从而把单步投影误差彻底约束在当前轮次内部，避免误差向后续通信轮次反向渗透。核心 idea：将双向误差反馈机制嵌入 FTRL 框架实现投影误差与压缩误差的严格解耦，并设计块化在线多轮残差压缩与异步更新补偿策略，消除双向通信压缩误差的阶数放大，一举达成理论匹配的最优后悔界。

方法详解¶

整体框架¶

本文针对带域约束的分布式在线凸优化，提出了从基础解耦到最优加速递进的算法体系。基础方法 D-FTCL 在节点端与服务器端部署对称的双向误差反馈，并将更新机制由传统的带投影在线梯度下降切换为跟随正则化领导者（FTRL），切断投影误差的时间传播链；随后，针对双向压缩导致的误差放大，改进算法 D-FTFCL 引入时间分块机制，在每个大小为 \(L=\lceil 1/\delta \rceil\) 的时间块内冻结决策，将原本需要单轮完成的多轮快速残差递归压缩（FCC）分摊平铺到整个块内各轮次，同时精确控制信息传输延迟引入的异步更新偏差。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["流式输入：节点决策 w 与环境凸损失 f"] --> B["FTRL 与误差反馈解耦架构<br/>双向通信分别追踪累积压缩残差"]
    B --> C["分块在线快速压缩调度<br/>块长 L 内分摊 FCC 递归传输"]
    C --> D["双向时延与异步决策更新<br/>使用延迟 b-2 聚合信息完成 FTRL 投影"]
    D --> E["分布式在线-离线 Anytime 转换<br/>输出离线随机非光滑最优收敛解"]

关键设计¶

1. FTRL 与误差反馈解耦架构：从机制上斩断投影截断与压缩残差的时间耦合

在经典 OGD 框架下，节点每轮状态依赖前一轮投影后的决策点，投影算子 \(\Pi_{\mathcal{W}}\) 的非线性导致过去累积的压缩误差被投影非线性扭曲，无法通过线性误差抵消机制予以消除。D-FTCL 将更新改写为 FTRL 形式，使每个决策点直接基于全部历史接收到的压缩信息总和来求解正则化极小值问题：

\[\mathbf{w}^{t+1} = \arg\min_{\mathbf{w}\in\mathcal{W}} \left\langle \sum_{k=1}^t \mathbf{s}^k, \mathbf{w} \right\rangle + \frac{1}{\eta} \|\mathbf{w}\|^2\]

在强凸损失场景下，正则化项自适应替换为 \(\frac{\mu}{2}\sum_{k=1}^t \|\mathbf{w}-\mathbf{w}^k\|^2\)。通过这一构造，任何轮次产生的可行域投影边界截断都被直接限制在该轮求解的极值点上，而不再作为下一轮压缩算子的输入基底。节点与服务器各自维护误差累积向量 \(\mathbf{e}_i^{t+1} = \mathbf{e}_i^t + \mathbf{g}_i^t - \mathbf{v}_i^t\) 以及 \(\hat{\mathbf{e}}^{t+1} = \hat{\mathbf{e}}^t + \mathbf{v}^t - \mathbf{s}^t\)，使得压缩误差的总和在望远求和中完全对消，成功保证了对任意收缩压缩算子满足 \(\mathbb{E}[\|\mathbf{w}^t - \hat{\mathbf{w}}^t\|] \leq O(\eta \delta^{-1})\)，首次在带约束流式凸优化中获得了可控的误差上界。

2. 分块在线快速压缩调度：化解双向压缩误差累积放大的通信瓶颈

虽然 D-FTCL 解决了约束域发散问题，但其上行（节点 \(\to\) 服务器）与下行（服务器 \(\to\) 节点）双向二次压缩会导致残差上界出现 \(\delta^{-2}\) 级别的恶化，未能达到理论下界。为了压制压缩噪声，离线领域常采用快速压缩通信（FCC）进行多轮残差迭代，但在线优化要求每一轮必须实时作出动作，不能暂停通信等待多轮迭代。D-FTFCL 创造性地设计了分块机制，将整个时间轴划分为若干长度为 \(L=\lceil 1/\delta \rceil\) 的时间块 \(b\)。在块 \(b\) 内的各个时间步 \(t \in [(b-1)L+1, bL]\) 中，节点固定执行决策 \(\mathbf{w}^b\)，并将块内梯度之和 \(\mathbf{z}_i^b = \sum_{t} \mathbf{g}_i^t\) 的 FCC 压缩切片均匀分布在块内的 \(L\) 个通信轮次中逐步传输。通过 \(L\) 次残差连续逼近，单次有效传输的方差收缩因子由 \(1-\delta\) 指数级锐减至 \((1-\delta)^L \leq 1/e\)，从而彻底消除了误差对压缩率 \(\delta\) 的高阶依赖。

3. 双向时延与异步决策更新：严格量化与补偿通信延迟引发的虚拟决策偏差

分块传输机制使得节点向服务器上传梯度需要耗费一个块（\(L\) 步），服务器聚合后再下发至节点又需要耗费一个块（\(L\) 步）。这使得节点在块 \(b\) 结束、准备计算块 \(b+1\) 的决策时，实际只能获取到截止于块 \(b-2\) 的历史聚合梯度信息 \(\mathbf{s}^{b-2}\)。D-FTFCL 显式地基于信息可达性构造了延迟更新法则：

\[\mathbf{w}^{b+1} = \arg\min_{\mathbf{w}\in\mathcal{W}} \left\langle \sum_{k=1}^{b-2} \mathbf{s}^k, \mathbf{w} \right\rangle + \frac{1}{\eta} \|\mathbf{w}\|^2\]

在理论证明中，作者通过构造带延迟的虚拟理想决策轨迹 \(\tilde{\mathbf{w}}^{b+1}\)（仅含时滞、无压缩）和完全无延迟无压缩的理想轨迹 \(\hat{\mathbf{w}}^{b+1}\)，运用三点分离法将总后悔精确拆解为“理想 FTRL 后悔项”、“残差截断噪声项”以及“块内时滞漂移项 \(\sum_{b} GL \|\mathbf{w}^b - \hat{\mathbf{w}}^b\|\)”。分析严格证明当时滞固定为 \(2L\) 步时，由漂移带来的后悔惩罚恰好与学习率乘积相平衡，在强凸情况下额外产生的后悔仅为 \(O(\mu^{-1} \delta^{-1} (G+\mu D)^2 \log T)\)，成功以常数时延代价换取了压缩方差的最优阶数。

4. 分布式在线-离线 Anytime 转换：填补带约束非光滑随机优化收敛率理论空白

该在线设计具备出色的通用性，论文进一步将其外推至离线分布式随机凸优化（Stochastic Convex Optimization）中。针对以往文献在非光滑与闭凸集约束下缺乏压缩通信理论的空缺，设计了分布式 Anytime 在线到批（Online-to-Batch, O2B）转换协议。在离线场景下，由于无需严格遵循流式单步决策，节点在每轮参数更新前可直接利用 \(L\) 次 FCC 迭代完成精确通信，节点在第 \(t\) 步利用当前历史加权平均点 \(\mathbf{x}^t = \frac{\sum_{k=1}^t \alpha_k \mathbf{w}^k}{\sum_{k=1}^t \alpha_k}\) 处采样的随机次梯度构造代理损失函数 \(\hat{\ell}_i^t(\mathbf{w}) = \langle \alpha_t \mathbf{g}_i^t, \mathbf{w} \rangle\) 输入 D-FTCL 求解。对于强凸目标，设置非均匀时变权重 \(\alpha_t = t\) 并叠加二阶中心近似，直接将在线界推导为离线末次迭代收敛界。

损失函数 / 训练策略¶

优化目标：最小化全局累积对抗后悔 \(R_T = \frac{1}{n} \sum_{t=1}^T \sum_{i=1}^n (f_i^t(\mathbf{w}^t) - f_i^t(\mathbf{w}^\star))\)。
凸损失学习率配置：D-FTCL 设置 \(\eta = \frac{\delta D}{G\sqrt{T}}\)；改进算法 D-FTFCL 设置 \(\eta = \frac{D}{G\sqrt{LT}} = \frac{D\sqrt{\delta}}{G\sqrt{T}}\)。
压缩超参数：块长度及 FCC 递归迭代轮数统一设置为 \(L = \lceil 1/\delta \rceil\)。

实验关键数据¶

主实验¶

论文通过严格的理论推导给出了各类算法在带域约束分布式在线凸优化中的期望后悔界，并与构造的对抗下界进行匹配对比：

算法 / 理论界	凸损失后悔界 (Convex)	强凸损失后悔界 (Strongly Convex)	通信类型	适用约束域
D-FTCL (本文基础)	\(O(\delta^{-1} DG \sqrt{T})\)	\(O(\mu^{-1} \delta^{-2} (G+\mu D)^2 \log T)\)	双向单轮压缩	任意闭凸集 \(\mathcal{W}\)
D-FTFCL (本文最优)	\(\mathcal{O}(\delta^{-1/2} DG \sqrt{T})\)	\(\mathcal{O}(\mu^{-1} \delta^{-1} (G+\mu D)^2 \log T)\)	双向块化压缩	任意闭凸集 \(\mathcal{W}\)
理论匹配下界 (本文建立)	\(\mathbf{\Omega}(\delta^{-1/2} DG \sqrt{T})\)	\(\mathbf{\Omega}(\mu^{-1} \delta^{-1} D^2 \log T)\)	分布式星型架构	任意闭凸集 \(\mathcal{W}\)
经典未压缩下界 (\(\delta=1\))	\(\Omega(DG\sqrt{T})\)	\(\Omega(\mu^{-1} G^2 \log T)\)	无压缩基准	凸域

消融实验：离线随机非光滑优化拓展对比¶

通过分布式 Anytime 在线到批转换（Distributed O2B），论文首次建立了带约束域和非光滑条件下的收敛率保障，并在不同权重与压缩算子下进行了理论对比：

算法方案	损失函数类型	权重策略 \(\alpha_t\)	迭代收敛率 (Last-Iterate)	算子示例 (Sign 算子 \(\delta=1/d\))
Distributed O2B (本文)	一般凸 (Convex)	均匀权重 \(\alpha_t = 1\)	\(O(\delta^{-1/2} T^{-1/2})\)	\(O(d^{1/2} T^{-1/2})\)
Distributed O2B (本文)	强凸 (Strongly Convex)	均匀权重 \(\alpha_t = 1\)	\(O(\delta^{-1} T^{-1} \log T)\) (次优)	\(O(d T^{-1} \log T)\)
Distributed O2B (本文)	强凸 (Strongly Convex)	递增权重 \(\alpha_t = t\)	\(\mathcal{O}(\delta^{-1} T^{-1})\) (最优)	\(\mathcal{O}(d T^{-1})\)
Islamov et al. (2025)	一般凸 (Convex)	-	\(O(\delta^{-1} T^{-1/2})\)	仅限于 Safe-Constraint

关键发现¶

双向压缩的阶数代价：在双向压缩结构中，若直接应用经典单轮误差反馈（D-FTCL），通信压缩比 \(\delta\) 在凸损失与强凸损失下的影响分别退化至 \(\delta^{-1}\) 和 \(\delta^{-2}\)；只有通过引入在线分块与 FCC 多轮逼近（D-FTFCL），方可将依赖恢复至最优的 \(\delta^{-1/2}\) 与 \(\delta^{-1}\)。
下界的构造根源：通过将收缩压缩算子退化建模为概率为 \(\delta\) 的随机 Gossip 通信丢包，可推得单次有效信息同步的期望间隔为 \(\lceil 1/\delta \rceil\)。在信息受阻期内对手构造的正交扰动，奠定了凸情形 \(\delta^{-1/2}\) 与强凸情形 \(\delta^{-1}\) 的不可逾越下界。
权重策略对强凸收敛的决定性影响：在在线到批转换中，采用经典均匀权重平均只能获得带 \(\log T\) 因子的次优收敛率；引入与时间线性增长的时变加权 \(\alpha_t = t\)，能精确平衡前期历史偏差，取得与无约束一阶随机黑盒下界完美匹配的 \(O(T^{-1})\) 极速收敛。

亮点与洞察¶

投影与压缩的解耦哲学：指出 OGD 依赖递推导致投影非线性阻断误差回传的内在缺陷，选用 FTRL 架构以全局累加的形式天然将投影收束于单步边界，为所有带约束域的压缩通信算法设计提供了标准的范式参考。
通信分摊与时延容忍的置换艺术：在线算法通常视“延迟”为有害因素，而本文主动引入大小为 \(L\) 的时间块和 \(2L\) 步时滞，换取多轮残差逼近通信空间，成功用可控的低阶时延后悔换取了对恶劣压缩率 \(\delta\) 的高精度鲁棒性。
闭合非光滑带约束理论鸿沟：过去文献要么假定目标函数全局光滑，要么退化为全空间无约束；本文通过在线凸优化的分析视角，一举补齐了分布式非光滑带约束优化中压缩通信的理论空白。

局限与展望¶

光滑性加速潜力的缺失：当前界主要针对 Lipschitz 连续的非光滑凸损失；在具有 \(L\)-光滑性质的损失函数下，能否利用乐观在线学习（Optimistic OCO）构造梯度预测项以达成 \(O(\text{poly}(\delta)\log T)\) 或常数级后悔仍属未决难题，核心障碍在于粗糙的压缩梯度难以提供高质量的单步预测信息。
拓扑结构的局限性：理论深度依赖中心服务器的星型收集广播拓扑（Parameter Server），对于拓扑随时间变化、无中心聚合器的任意去中心化图网络（P2P Topology），时延与残差累积的收敛性有待进一步探索。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次系统建立带约束域分布式在线凸优化的压缩通信框架与匹配下界。
实验充分度: ⭐⭐⭐⭐⭐ 纯理论突破，完备证明了凸/强凸下的上下界以及离线转换收敛率。
写作质量: ⭐⭐⭐⭐⭐ 逻辑主线极为清晰，痛点识别、解耦机制与渐进改进层层推进。
价值: ⭐⭐⭐⭐⭐ 彻底解决带约束非光滑凸优化中压缩误差与投影耦合的长期理论瓶颈。