重访带压缩通信的分布式在线凸优化

# 重温带压缩通信的分布式在线凸优化 来源：https://arxiv.org/html/2607.01665 周昊1王笑语1姚畅1，2宋明利1，2万园宇1，2 1浙江大学软件学院，宁波，中国 2浙江大学区块链与数据安全全国重点实验室，杭州，中国 \{juhao, xiaoyuw, brooksong, changy, wanyy\}@zju\.edu\.cn ###### 摘要 分布式在线凸优化（D-OCO）是一个流行的框架，适用于具有流式数据的分布式应用。为了解决通信瓶颈，先前的研究已经探索了带压缩通信的D-OCO，并提出了几种基于在线梯度下降（OGD）的变体算法。然而，对于使用精确通信的D-OCO，目前最好的现有算法是基于跟随正则化领导者（FTRL）的变体。在本文中，我们首次提出了两种用于带压缩通信的D-OCO的FTRL型算法。与OGD型算法相比，我们的算法在算法设计和理论分析上都更加简洁。关键洞察在于，FTRL的对偶更新机制使得我们可以简单地应用带通信压缩的平均共识技术。具体而言，我们的第一个算法考虑了全信息设置，能够匹配现有的遗憾界。我们的第二个算法专为赌博机设置设计，能够显著改进现有算法的遗憾界和通信成本。 ## 1 引言 本文研究分布式在线凸优化（D-OCO）问题，特别关注仅使用压缩通信的算法。通常，D-OCO被建模为一个重复博弈：在一个网络中，有n个学习者和一个对手。在每个轮次t，每个学习者i∈[n]从凸集K⊆Rd中选择一个决策xi(t)，然后接收由对手选择的凸损失函数ft,i(·):K↦R。令ft(·)=∑j=1nft,j(·)表示第t轮的全局函数。在总共T轮后，每个学习者i∈[n]的目标是最小化关于全局函数的遗憾，即RT,i=∑t=1Tft(xi(t))-minx∈K∑t=1Tft(x)。为此，这些学习者在每轮允许与其直接邻居通信一次。在精确通信情况下，D-OCO在过去十年中得到了广泛研究（Yan et al., 2013 (https://arxiv.org/html/2607.01665#bib.bib35); Hosseini et al., 2013 (https://arxiv.org/html/2607.01665#bib.bib14); Zhang et al., 2017 (https://arxiv.org/html/2607.01665#bib.bib37); Wan et al., 2020 (https://arxiv.org/html/2607.01665#bib.bib24), 2022 (https://arxiv.org/html/2607.01665#bib.bib25); Wang et al., 2023 (https://arxiv.org/html/2607.01665#bib.bib30); Wan et al., 2024 (https://arxiv.org/html/2607.01665#bib.bib26), 2025 (https://arxiv.org/html/2607.01665#bib.bib27)）。众所周知，大多数用于非分布式设置的算法，包括在线梯度下降（OGD）（Zinkevich, 2003 (https://arxiv.org/html/2607.01665#bib.bib38)）和跟随正则化领导者（FTRL）（Shalev-Shwartz and Singer, 2007 (https://arxiv.org/html/2607.01665#bib.bib20); Xiao, 2009 (https://arxiv.org/html/2607.01665#bib.bib33)），都可以通过结合基于八卦的平均共识技术（Xiao and Boyd, 2004 (https://arxiv.org/html/2607.01665#bib.bib34); Liu and Morse, 2011 (https://arxiv.org/html/2607.01665#bib.bib18)）扩展到D-OCO中。值得注意的是，通过扩展FTRL，Wan等人（2024 (https://arxiv.org/html/2607.01665#bib.bib26), 2025 (https://arxiv.org/html/2607.01665#bib.bib27)）在精确通信的D-OCO中取得了近乎最优的遗憾界。相比之下，之前只有少数研究考虑了带压缩通信的D-OCO。具体来说，两项同期研究（Tu et al., 2022 (https://arxiv.org/html/2607.01665#bib.bib23); Cao and Başar, 2023 (https://arxiv.org/html/2607.01665#bib.bib7)）提出将OGD的分布式变体（D-OGD）（Yan et al., 2013 (https://arxiv.org/html/2607.01665#bib.bib35)）与Choco-Gossip（Koloskova et al., 2019 (https://arxiv.org/html/2607.01665#bib.bib15)）——标准八卦技术的一种压缩变体（Xiao and Boyd, 2004 (https://arxiv.org/html/2607.01665#bib.bib34)）——相结合。不幸的是，所提出的算法并不令人满意，因为其遗憾对八卦矩阵的谱间隙ρ∈(0,1]、压缩比ω∈(0,1]以及n有较大的依赖。为了解决这个问题，Yang等人（2026 (https://arxiv.org/html/2607.01665#bib.bib36)）提出了一种改进算法，对凸函数和强凸函数分别达到了O~(ω−1/2ρ−1nT)和O~(ω−1ρ−2nlogT)的遗憾界。111O~(·)符号隐藏了常数因子以及与n相关的多对数因子，但不隐藏与T相关的因子。该算法仍然是D-OGD与Choco-Gossip的结合，但引入了一个两级阻塞更新机制和一个重复压缩器以进一步减小共识误差。 表1：我们的赌博机算法与先前最佳算法的比较。缩写：凸函数→cvx，强凸函数→scvx。 | 假设 | 参考 | 遗憾界 | 通信轮数 |
|------|------|--------|----------|
| ft,i(·): cvx | Yang et al. (2026 (https://arxiv.org/html/2607.01665#bib.bib36)) | O~(ω−1/4ρ−1/2nT3/4) | O(T) |
| | 推论3.13 (https://arxiv.org/html/2607.01665#S3.Thmtheorem13) | O(nT3/4) | O~(ω−1ρ−2√T) |
| ft,i(·): scvx | Yang et al. (2026 (https://arxiv.org/html/2607.01665#bib.bib36)) | O~(ω−1/3ρ−2/3nT2/3(logT)1/3) | O(T) |
| | 推论3.14 (https://arxiv.org/html/2607.01665#S3.Thmtheorem14) | O(nT2/3(logT)1/3) | O~(ω−1ρ−2T1/3(logT)2/3) |

因此，目前尚不清楚用于D-OCO的FTRL型算法是否也能扩展到带压缩通信的场景，以及这种扩展相对于现有算法是否具有任何优势。在本文中，我们对这两个问题给出了肯定的答案。具体而言，我们首先提出了一种FTRL型算法的压缩变体，并证明其享有与Yang等人（2026 (https://arxiv.org/html/2607.01665#bib.bib36)）算法相同的遗憾界。尽管在界上没有改进，但我们的算法和分析都比Yang等人（2026 (https://arxiv.org/html/2607.01665#bib.bib36)）的简单得多。关键洞察在于，对于FTRL型算法，决策由局部累积平均梯度的近似（即所谓的对偶变量）决定。尽管从对偶变量到决策的映射等价于到集合K上的投影，但这些对偶变量的共识误差并不受投影的影响。因此，可以通过简单地应用Choco-Gossip来控制。此外，我们将第一个算法扩展到更具挑战性的赌博机设置，其中每个学习者i只获得损失值ft,i(xi(t))。注意，先前的研究（Tu et al., 2022 (https://arxiv.org/html/2607.01665#bib.bib23); Yang et al., 2026 (https://arxiv.org/html/2607.01665#bib.bib36)）也考虑过这种设置。Yang等人（2026 (https://arxiv.org/html/2607.01665#bib.bib36)）的赌博机算法达到了现有最佳遗憾界，即对凸函数和强凸函数分别为O~(ω−1/4ρ−1/2nT3/4)和O~(ω−1/3ρ−2/3nT2/3(logT)1/3)。我们证明我们的赌博机算法不仅比Yang等人（2026 (https://arxiv.org/html/2607.01665#bib.bib36)）的算法更简单，而且将其两个界分别改进为O(nT3/4)和O(nT2/3(logT)1/3)。此外，与Yang等人（2026 (https://arxiv.org/html/2607.01665#bib.bib36)）的算法总共需要T轮通信不同，我们的赌博机算法仅需O~(ω−1ρ−2√T)和O~(ω−1ρ−2T1/3(logT)2/3)轮通信即可达到这两个界。我们的赌博机算法与Yang等人（2026 (https://arxiv.org/html/2607.01665#bib.bib36)）算法的详细比较见表1 (https://arxiv.org/html/2607.01665#S1.T1)。 ## 2 相关工作 现在，我们简要回顾标准D-OCO以及压缩通信的相关工作。 ### 2.1 标准D-OCO D-OCO的研究可以追溯到Yan等人（2013 (https://arxiv.org/html/2607.01665#bib.bib35)）的开创性工作，他们提出了D-OGD，对凸函数和强凸函数分别达到了O(n5/4ρ−1/2√T)和O(n3/2ρ−1logT)的遗憾界。D-OGD的关键思想是先对这些局部决策应用标准八卦步骤（Xiao and Boyd, 2004 (https://arxiv.org/html/2607.01665#bib.bib34)），然后仅根据局部函数执行投影梯度下降步骤。注意，八卦步骤的本质是计算这些局部变量的加权平均，这需要通过一轮通信来实现，权重由八卦矩阵指定。与此同时，Hosseini等人（2013 (https://arxiv.org/html/2607.01665#bib.bib14)）提出了FTRL（Shalev-Shwartz and Singer, 2007 (https://arxiv.org/html/2607.01665#bib.bib20); Xiao, 2009 (https://arxiv.org/html/2607.01665#bib.bib33)）的分布式变体（D-FTRL），并对凸函数达到了相同的O(n5/4ρ−1/2√T)遗憾界。与D-OGD不同，该算法使用标准八卦步骤来更新局部决策的对偶变量。此后，越来越多的研究关注于开发无投影的D-OCO算法（Zhang et al., 2017 (https://arxiv.org/html/2607.01665#bib.bib37); Wan et al., 2020 (https://arxiv.org/html/2607.01665#bib.bib24), 2022 (https://arxiv.org/html/2607.01665#bib.bib25); Wang et al., 2023 (https://arxiv.org/html/2607.01665#bib.bib30)）。这些算法的动机在于，D-OGD和D-FTRL都需要投影来确保每个决策的可行性，这在具有复杂集合K的应用中可能耗时。尽管无投影算法的设计超出了本文的范围，但Wan等人（2022 (https://arxiv.org/html/2607.01665#bib.bib25)）也提出了一种用于赌博机设置的无投影且一般化的D-FTRL变体。对于凸函数和强凸函数，它分别达到了O(n5/4ρ−1/2T3/4)和O(n3/2ρ−1T2/3(logT)1/3)的遗憾界。更有趣的是，在处理这两类函数时，它仅需O(√T)和O(T1/3(logT)2/3)轮通信。这些改进主要归功于阻塞更新机制，即将总T轮划分为多个块，每块只更新一次决策。最近，Wan等人（2024 (https://arxiv.org/html/2607.01665#bib.bib26), 2025 (https://arxiv.org/html/2607.01665#bib.bib27)）提出了一种新颖的全信息算法——加速分布式跟随广义领导者（AD-FTGL），对凸函数和强凸函数分别达到了O~(nρ−1/4√T)和O~(nρ−1/2logT)的遗憾界。该算法也是D-FTRL的一个变体，关键变化在于利用了加速八卦策略（Liu and Morse, 2011 (https://arxiv.org/html/2607.01665#bib.bib18)）。他们提供了几乎匹配的下界以证明其最优性。此外，Wan等人（2025 (https://arxiv.org/html/2607.01665#bib.bib27)）还提出了AD-FTGL的无投影变体，对凸函数和强凸函数分别达到了O(nT3/4)和O(nT2/3(logT)1/3)的遗憾界，同时分别通信O~(ρ−1/2√T)和O~(ρ−1/2T1/3(logT)2/3)轮。尽管该变体是为全信息设置开发的，但实际上可以简单地扩展到赌博机设置，同时保持相同的遗憾界和通信成本。与Wan等人（2022 (https://arxiv.org/html/2607.01665#bib.bib25)）中的无投影赌博机算法相比，这些遗憾界的改进得益于加速八卦策略以及部分通信成本的牺牲。 ### 2.2 压缩通信 压缩通信是一种流行策略，用于减少分布式优化中每次迭代必须发送的数据量。对于集中式分布式离线优化，众所周知有许多压缩通信技术（也称为压缩器），可分为量化（Alistarh et al., 2017 (https://arxiv.org/html/2607.01665#bib.bib2); Wen et al., 2017 (https://arxiv.org/html/2607.01665#bib.bib32); Bernstein et al., 2018 (https://arxiv.org/html/2607.01665#bib.bib5); Seide et al., 2014 (https://arxiv.org/html/2607.01665#bib.bib19)）、稀疏化（Alistarh et al., 2018 (https://arxiv.org/html/2607.01665#bib.bib3); Stich et al., 2018 (https://arxiv.org/html/2607.01665#bib.bib21); Wangni et al., 2018 (https://arxiv.org/html/2607.01665#bib.bib31); Aji and Heafield, 2017 (https://arxiv.org/html/2607.01665#bib.bib1); Lin et al., 2018 (https://arxiv.org/html/2607.01665#bib.bib17)）以及它们的混合组合（Basu et al., 2019 (https://arxiv.org/html/2607.01665#bib.bib4); Wang et al., 2018 (https://arxiv.org/html/2607.01665#bib.bib28)）。对于分布式离线优化，Tang等人（2018 (https://arxiv.org/html/2607.01665#bib.bib22)）是第一个应用压缩通信思想的工作，但只关注具有高精度约束的无偏压缩器。为了解决这个问题，Koloskova等人（2019 (https://arxiv.org/html/2607.01665#bib.bib15)）提出了一种新颖且统一的方法，称为Choco-Gossip，用于在分布式设置中与不同压缩器进行平均共识，并提出了相应的Choco-SGD算法用于分布式离线优化。带压缩通信的D-OCO的研究实际上可以追溯到Li等人（2021 (https://arxiv.org/html/2607.01665#bib.bib16)）。然而，他们只提出了一种启发式方法，没有任何理论保证。通过将D-OGD（Yan et al., 2013 (https://arxiv.org/html/2607.01665#bib.bib35)）与Choco-Gossip（Koloskova et al., 2019 (https://arxiv.org/html/2607.01665#bib.bib15)）相结合，T