Revisiting Decentralized Online Convex Optimization with Compressed Communication

# Revisiting Decentralized Online Convex Optimization with Compressed Communication
Source: [https://arxiv.org/html/2607.01665](https://arxiv.org/html/2607.01665)
Hao Zhou1Xiaoyu Wang1Chang Yao1,2Mingli Song1,2Yuanyu Wan1,2 1School of Software Technology, Zhejiang University, Ningbo, China 2State Key Laboratory of Blockchain and Data Security, Zhejiang University, Hangzhou, China \{juhao, xiaoyuw, brooksong, changy, wanyy\}@zju\.edu\.cn

###### Abstract

Decentralized online convex optimization \(D\-OCO\) is a popular framework for distributed applications with streaming data\. To tackle the communication bottleneck, previous studies have investigated D\-OCO with compressed communication and proposed several algorithms that are variants of online gradient descent \(OGD\)\. However, for D\-OCO with exact communication, the best existing algorithms are variants of follow\-the\-regularized\-leader \(FTRL\)\. In this paper, for the first time, we propose two FTRL\-type algorithms for D\-OCO with compressed communication\. Compared with OGD\-type algorithms, our algorithms are more elegant in both algorithmic design and theoretical analysis\. The key insight is that the dual update mechanism of FTRL allows us to make a simple application of the technique for average consensus with communication compression\. More specifically, our first algorithm considers the full\-information setting, and can match the existing regret bounds\. Our second algorithm is designed for the bandit setting, and can significantly improve both the regret bounds and communication costs of existing algorithms\.

## 1Introduction

This paper investigates the decentralized online convex optimization \(D\-OCO\) problem with a particular focus on algorithms that only use compressed communication\. In general, D\-OCO is formulated as a repeated game betweennnlearners in a network and an adversary\. At each roundtt, each learneri∈\[n\]i\\in\[n\]selects a decision𝐱i​\(t\)\\mathbf\{x\}\_\{i\}\(t\)from a convex set𝒦⊆ℝd\\mathcal\{K\}\\subseteq\\mathbb\{R\}^\{d\}, and then receives a convex loss functionft,i​\(⋅\):𝒦↦ℝf\_\{t,i\}\(\\cdot\):\\mathcal\{K\}\\mapsto\\mathbb\{R\}chosen by the adversary\. Letft​\(⋅\)=∑j=1nft,j​\(⋅\)f\_\{t\}\(\\cdot\)=\\sum\_\{j=1\}^\{n\}f\_\{t,j\}\(\\cdot\)denote the global function of roundtt\. For totalTTrounds, the goal of each learneri∈\[n\]i\\in\[n\]is to minimize the regret in terms of the global function, i\.e\.,RT,i=∑t=1Tft​\(𝐱i​\(t\)\)−min𝐱∈𝒦​∑t=1Tft​\(𝐱\)R\_\{T,i\}=\\sum\_\{t=1\}^\{T\}f\_\{t\}\(\\mathbf\{x\}\_\{i\}\(t\)\)\-\\min\_\{\\mathbf\{x\}\\in\\mathcal\{K\}\}\\sum\_\{t=1\}^\{T\}f\_\{t\}\(\\mathbf\{x\}\)\. To this end, these learners are allowed to communicate with their immediate neighbors once per round\.

In the case with exact communication, D\-OCO has been extensively studied over the past decade\(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)\)\. It is well known that most algorithms for the non\-distributed setting, including online gradient descent \(OGD\)\(Zinkevich,[2003](https://arxiv.org/html/2607.01665#bib.bib38)\)and follow\-the\-regularized\-leader \(FTRL\)\(Shalev\-Shwartz and Singer,[2007](https://arxiv.org/html/2607.01665#bib.bib20); Xiao,[2009](https://arxiv.org/html/2607.01665#bib.bib33)\), can be extended into D\-OCO by combining with the gossip\-based average consensus technique\(Xiao and Boyd,[2004](https://arxiv.org/html/2607.01665#bib.bib34); Liu and Morse,[2011](https://arxiv.org/html/2607.01665#bib.bib18)\)\. Notably, by extending FTRL,Wan et al\. \([2024](https://arxiv.org/html/2607.01665#bib.bib26),[2025](https://arxiv.org/html/2607.01665#bib.bib27)\)have achieved nearly optimal regret bounds for D\-OCO with exact communication\. In contrast, only a few previous studies have considered D\-OCO with compressed communication\.

To be precise, two concurrent studies\(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)\)propose to combine a decentralized variant of OGD \(D\-OGD\)\(Yan et al\.,[2013](https://arxiv.org/html/2607.01665#bib.bib35)\)with Choco\-Gossip\(Koloskova et al\.,[2019](https://arxiv.org/html/2607.01665#bib.bib15)\)—a compressed variant of the standard gossip technique\(Xiao and Boyd,[2004](https://arxiv.org/html/2607.01665#bib.bib34)\)\. Unfortunately, the proposed algorithm is unsatisfactory, because its regret has a large dependence on the spectral gapρ∈\(0,1\]\\rho\\in\(0,1\]of the gossip matrix, the compression ratioω∈\(0,1\]\\omega\\in\(0,1\], andnn\. To address this issue,Yang et al\. \([2026](https://arxiv.org/html/2607.01665#bib.bib36)\)propose an improved algorithm withO~​\(ω−1/2​ρ−1​n​T\)\\tilde\{O\}\(\\omega^\{\-1/2\}\\rho^\{\-1\}n\\sqrt\{T\}\)andO~​\(ω−1​ρ−2​n​log⁡T\)\\tilde\{O\}\(\\omega^\{\-1\}\\rho^\{\-2\}n\\log T\)regret bounds for convex and strongly convex functions, respectively\.111TheO~​\(⋅\)\\tilde\{O\}\(\\cdot\)notation hides constant factors as well as polylogarithmic factors innn, but not inTT\.This algorithm is still a combination of D\-OGD and Choco\-Gossip, though it introduces a two\-level blocking update mechanism and a repeated compressor to further reduce the consensus error\.

Table 1:Comparison of our bandit algorithm and the previous best one\. Abbreviations: convex→\\rightarrowcvx, strongly convex→\\rightarrowscvx\.AssumptionReferenceRegret BoundCommunication Roundsft,i​\(⋅\)f\_\{t,i\}\(\\cdot\): cvxYang et al\. \([2026](https://arxiv.org/html/2607.01665#bib.bib36)\)O~​\(ω−1/4​ρ−1/2​n​T3/4\)\\tilde\{O\}\(\\omega^\{\-1/4\}\\rho^\{\-1/2\}nT^\{3/4\}\)O​\(T\)O\(T\)Corollary[3\.13](https://arxiv.org/html/2607.01665#S3.Thmtheorem13)O​\(n​T3/4\)\{O\}\(nT^\{3/4\}\)O~​\(ω−1​ρ−2​T\)\\tilde\{O\}\(\\omega^\{\-1\}\\rho^\{\-2\}\\sqrt\{T\}\)ft,i​\(⋅\)f\_\{t,i\}\(\\cdot\): scvxYang et al\. \([2026](https://arxiv.org/html/2607.01665#bib.bib36)\)O~​\(ω−1/3​ρ−2/3​n​T2/3​\(log⁡T\)1/3\)\\tilde\{O\}\(\\omega^\{\-1/3\}\\rho^\{\-2/3\}nT^\{2/3\}\(\\log T\)^\{1/3\}\)O​\(T\)O\(T\)Corollary[3\.14](https://arxiv.org/html/2607.01665#S3.Thmtheorem14)O​\(n​T2/3​\(log⁡T\)1/3\)\{O\}\(nT^\{2/3\}\(\\log T\)^\{1/3\}\)O~​\(ω−1​ρ−2​T1/3​\(log⁡T\)2/3\)\\tilde\{O\}\(\\omega^\{\-1\}\\rho^\{\-2\}T^\{1/3\}\(\\log T\)^\{2/3\}\)Thus, it remains unclear whether the FTRL\-type algorithm for D\-OCO can also be extended into the case with compressed communication, and whether such an extension provides any benefits relative to existing algorithms\. In this paper, we provide an affirmative answer to both questions\. Specifically, we first propose a compressed variant of the FTRL\-type algorithm, and show that it enjoys the same regret bounds as the algorithm ofYang et al\. \([2026](https://arxiv.org/html/2607.01665#bib.bib36)\)\. Despite no improvement in the bounds, both our algorithm and analysis are much simpler than those ofYang et al\. \([2026](https://arxiv.org/html/2607.01665#bib.bib36)\)\. The key insight is that for the FTRL\-type algorithm, the decision is determined by a local approximation of the cumulative average gradient, i\.e\., the so\-called dual variable\. Although the mapping from the dual variable to the decision is equivalent to a projection onto the set𝒦\\mathcal\{K\}, the consensus error of these dual variables is not affected by the projection\. For this reason, it can be controlled by a simple application of Choco\-Gossip\.

Furthermore, we extend our first algorithm into a more challenging bandit setting, where only the loss valueft,i​\(𝐱i​\(t\)\)f\_\{t,i\}\(\\mathbf\{x\}\_\{i\}\(t\)\)is revealed to each learnerii\. Note that previous studies\(Tu et al\.,[2022](https://arxiv.org/html/2607.01665#bib.bib23); Yang et al\.,[2026](https://arxiv.org/html/2607.01665#bib.bib36)\)have also considered this setting\. The bandit algorithm ofYang et al\. \([2026](https://arxiv.org/html/2607.01665#bib.bib36)\)achieves the best existing regret bounds, i\.e\.,O~​\(ω−1/4​ρ−1/2​n​T3/4\)\\tilde\{O\}\(\\omega^\{\-1/4\}\\rho^\{\-1/2\}nT^\{3/4\}\)andO~​\(ω−1/3​ρ−2/3​n​T2/3​\(log⁡T\)1/3\)\\tilde\{O\}\(\\omega^\{\-1/3\}\\rho^\{\-2/3\}nT^\{2/3\}\(\\log T\)^\{1/3\}\)for convex and strongly convex functions, respectively\. We demonstrate that our bandit algorithm is not only simpler than that ofYang et al\. \([2026](https://arxiv.org/html/2607.01665#bib.bib36)\), but also improves their two bounds toO​\(n​T3/4\)\{O\}\(nT^\{3/4\}\)andO​\(n​T2/3​\(log⁡T\)1/3\)\{O\}\(nT^\{2/3\}\(\\log T\)^\{1/3\}\), respectively\. Moreover, different from the algorithm ofYang et al\. \([2026](https://arxiv.org/html/2607.01665#bib.bib36)\)that requiresTTcommunication rounds in total, our bandit algorithm only requiresO~​\(ω−1​ρ−2​T\)\\tilde\{O\}\(\\omega^\{\-1\}\\rho^\{\-2\}\\sqrt\{T\}\)andO~​\(ω−1​ρ−2​T1/3​\(log⁡T\)2/3\)\\tilde\{O\}\(\\omega^\{\-1\}\\rho^\{\-2\}T^\{1/3\}\(\\log T\)^\{2/3\}\)communication rounds to achieve these two bounds\. A detailed comparison of our bandit algorithm and that ofYang et al\. \([2026](https://arxiv.org/html/2607.01665#bib.bib36)\)is presented in Table[1](https://arxiv.org/html/2607.01665#S1.T1)\.

## 2Related work

Now, we briefly review related work on the standard D\-OCO, and compressed communication\.

### 2\.1The standard D\-OCO

The study of D\-OCO dates back to the pioneering work ofYan et al\. \([2013](https://arxiv.org/html/2607.01665#bib.bib35)\), in which D\-OGD is proposed to achieveO​\(n5/4​ρ−1/2​T\)O\(n^\{5/4\}\\rho^\{\-1/2\}\\sqrt\{T\}\)andO​\(n3/2​ρ−1​log⁡T\)O\(n^\{3/2\}\\rho^\{\-1\}\\log T\)regret bounds for convex and strongly convex functions, respectively\. The key idea of D\-OGD is to first apply a standard gossip step\(Xiao and Boyd,[2004](https://arxiv.org/html/2607.01665#bib.bib34)\)over these local decisions, and then perform a projected gradient descent step according to only the local function\. Note that the essence of the gossip step is to compute a weighted average of these local variables, which needs to be implemented via a communication round, and the weights are specified by the gossip matrix\. Concurrently,Hosseini et al\. \([2013](https://arxiv.org/html/2607.01665#bib.bib14)\)propose a decentralized variant of FTRL \(D\-FTRL\)\(Shalev\-Shwartz and Singer,[2007](https://arxiv.org/html/2607.01665#bib.bib20); Xiao,[2009](https://arxiv.org/html/2607.01665#bib.bib33)\), and achieve the sameO​\(n5/4​ρ−1/2​T\)O\(n^\{5/4\}\\rho^\{\-1/2\}\\sqrt\{T\}\)regret bound for convex functions\. Different from D\-OGD, this algorithm uses the standard gossip step to update the dual variables of local decisions\.

After that, there has been a growing research interest in developing projection\-free algorithms for 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)\)\. These algorithms are motivated by the fact that both D\-OGD and D\-FTRL require a projection to ensure the feasibility of each decision, which can be time\-consuming in applications with a complex set𝒦\\mathcal\{K\}\. Although the design of projection\-free algorithms is beyond the scope of this paper,Wan et al\. \([2022](https://arxiv.org/html/2607.01665#bib.bib25)\)have also proposed a projection\-free and generalized variant of D\-FTRL for the bandit setting\. For convex and strongly convex functions, it achievesO​\(n5/4​ρ−1/2​T3/4\)O\(n^\{5/4\}\\rho^\{\-1/2\}T^\{3/4\}\)andO​\(n3/2​ρ−1​T2/3​\(log⁡T\)1/3\)O\(n^\{3/2\}\\rho^\{\-1\}T^\{2/3\}\(\\log T\)^\{1/3\}\)regret bounds, respectively\. More interestingly, it only requiresO​\(T\)O\(\\sqrt\{T\}\)andO​\(T1/3​\(log⁡T\)2/3\)O\(T^\{1/3\}\(\\log T\)^\{2/3\}\)communication rounds, when handling these two types of functions\. Such improvements mainly owe to a blocking update mechanism, i\.e\., dividing totalTTrounds into several blocks and only updating the decision once per block\.

Recently,Wan et al\. \([2024](https://arxiv.org/html/2607.01665#bib.bib26),[2025](https://arxiv.org/html/2607.01665#bib.bib27)\)propose a novel full\-information algorithm called accelerated decentralized follow\-the\-generalized\-leader \(AD\-FTGL\), which enjoysO~​\(n​ρ−1/4​T\)\\tilde\{O\}\(n\\rho^\{\-1/4\}\\sqrt\{T\}\)andO~​\(n​ρ−1/2​log⁡T\)\\tilde\{O\}\(n\\rho^\{\-1/2\}\\log T\)regret bounds for convex and strongly convex functions, respectively\. This algorithm is also a variant of D\-FTRL, and the critical change is to exploit an accelerated gossip strategy\(Liu and Morse,[2011](https://arxiv.org/html/2607.01665#bib.bib18)\)\. They have provided nearly matching lower bounds to demonstrate its optimality\. Moreover,Wan et al\. \([2025](https://arxiv.org/html/2607.01665#bib.bib27)\)have also proposed a projection\-free variant of AD\-FTGL withO​\(n​T3/4\)\{O\}\(nT^\{3/4\}\)andO​\(n​T2/3​\(log⁡T\)1/3\)\{O\}\(nT^\{2/3\}\(\\log T\)^\{1/3\}\)regret bounds for convex and strongly convex functions, while communicatingO~​\(ρ−1/2​T\)\\tilde\{O\}\(\\rho^\{\-1/2\}\\sqrt\{T\}\)andO~​\(ρ−1/2​T1/3​\(log⁡T\)2/3\)\\tilde\{O\}\(\\rho^\{\-1/2\}T^\{1/3\}\(\\log T\)^\{2/3\}\)rounds, respectively\. Although this variant is developed for the full\-information setting, it actually can be simply extended into the bandit setting while keeping the same regret bounds and communication costs\. Compared with the projection\-free bandit algorithm inWan et al\. \([2022](https://arxiv.org/html/2607.01665#bib.bib25)\), the improvements on these regret bounds benefit from the accelerated gossip strategy and some sacrifices of communication costs\.

### 2\.2Compressed communication

Compressed communication is a popular strategy for reducing the amount of data that has to be sent during each iteration of distributed optimization\. For the centralized distributed offline optimization, it is well\-known that there are many techniques for compressed communication \(also known as compressors\), which can be divided into quantization\(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)\), sparsification\(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)\), and their hybrid combination\(Basu et al\.,[2019](https://arxiv.org/html/2607.01665#bib.bib4); Wang et al\.,[2018](https://arxiv.org/html/2607.01665#bib.bib28)\)\. For the decentralized offline optimization,Tang et al\. \([2018](https://arxiv.org/html/2607.01665#bib.bib22)\)is the first work to apply the idea of compressed communication, but only focus on unbiased compressors with high accuracy constraints\. To tackle this issue,Koloskova et al\. \([2019](https://arxiv.org/html/2607.01665#bib.bib15)\)propose a novel and unified method called Choco\-Gossip for average consensus with different compressors in the decentralized setting, as well as a corresponding Choco\-SGD algorithm for the decentralized offline optimization\.

The study of D\-OCO with compressed communication actually can be dated back toLi et al\. \([2021](https://arxiv.org/html/2607.01665#bib.bib16)\)\. However, they only propose a heuristic approach without any theoretical guarantee\. By combining D\-OGD\(Yan et al\.,[2013](https://arxiv.org/html/2607.01665#bib.bib35)\)with Choco\-Gossip\(Koloskova et al\.,[2019](https://arxiv.org/html/2607.01665#bib.bib15)\),Tu et al\. \([2022](https://arxiv.org/html/2607.01665#bib.bib23)\)andCao and Başar \([2023](https://arxiv.org/html/2607.01665#bib.bib7)\)concurrently propose the first algorithm to establish rigorous regret bounds for D\-OCO with compressed communication\. Specifically, it can respectively achieveO​\(C1​T\)O\(C\_\{1\}\\sqrt\{T\}\)andO​\(C1​log⁡T\)O\(C\_\{1\}\\log T\)regret bounds for convex and strongly convex functions, whereC1=max⁡\{ω−2​ρ−4​n3/2,ω−4​ρ−8​n\}C\_\{1\}=\\max\\\{\\omega^\{\-2\}\\rho^\{\-4\}n^\{3/2\},\\omega^\{\-4\}\\rho^\{\-8\}n\\\}\. Additionally,Tu et al\. \([2022](https://arxiv.org/html/2607.01665#bib.bib23)\)have also extended this algorithm into the bandit setting, and the previous two bounds respectively degrade toO​\(C2​T3/4\)O\(C\_\{2\}T^\{3/4\}\)andO​\(C3​T2/3​\(log⁡T\)1/3\)O\(C\_\{3\}T^\{2/3\}\(\\log T\)^\{1/3\}\), whereC2=max⁡\{ω−1​ρ−2​n5/4,ω−2​ρ−4​n\}C\_\{2\}=\\max\\\{\\omega^\{\-1\}\\rho^\{\-2\}n^\{5/4\},\\omega^\{\-2\}\\rho^\{\-4\}n\\\}andC3=max⁡\{ω−2/3​ρ−4/3​n7/6,ω−8/3​ρ−4​n\}C\_\{3\}=\\max\\\{\\omega^\{\-2/3\}\\rho^\{\-4/3\}n^\{7/6\},\\omega^\{\-8/3\}\\rho^\{\-4\}n\\\}\.

Very recently,Yang et al\. \([2026](https://arxiv.org/html/2607.01665#bib.bib36)\)further improve these two algorithms ofTu et al\. \([2022](https://arxiv.org/html/2607.01665#bib.bib23)\)\. In the full\-information setting, their algorithm enjoysO~​\(ω−1/2​ρ−1​n​T\)\\tilde\{O\}\(\\omega^\{\-1/2\}\\rho^\{\-1\}n\\sqrt\{T\}\)andO~​\(ω−1​ρ−2​n​log⁡T\)\\tilde\{O\}\(\\omega^\{\-1\}\\rho^\{\-2\}n\\log T\)regret bounds for convex and strongly convex functions, respectively\. In the bandit setting, their improved algorithm can achieveO~​\(ω−1/4​ρ−1/2​n​T3/4\)\\tilde\{O\}\(\\omega^\{\-1/4\}\\rho^\{\-1/2\}nT^\{3/4\}\)andO~​\(ω−1/3​ρ−2/3​n​T2/3​\(log⁡T\)1/3\)\\tilde\{O\}\(\\omega^\{\-1/3\}\\rho^\{\-2/3\}nT^\{2/3\}\(\\log T\)^\{1/3\}\)regret bounds for convex and strongly convex functions, respectively\. Despite such improvements, their algorithms introduce a complicated scheme that combines a two\-level blocking update mechanism with Choco\-Gossip and a repeated compressor\.

## 3Main results

In this section, we first introduce necessary assumptions, and then present our two FTRL\-type algorithms for D\-OCO with compressed communication\. The proofs of all theoretical results can be found in the appendix\.

### 3\.1Assumptions

Similar to previous studies on D\-OCO with compressed communication\(Tu et al\.,[2022](https://arxiv.org/html/2607.01665#bib.bib23); Yang et al\.,[2026](https://arxiv.org/html/2607.01665#bib.bib36)\), we first introduce the following assumptions\.

###### Assumption 3\.1\.

LetA∈ℝn×nA\\in\\mathbb\{R\}^\{n\\times n\}denote the gossip matrix\. Define the network by an undirected graph𝒢=\(\[n\],E\)\\mathcal\{G\}=\(\[n\],E\), whereE⊆\[n\]×\[n\]E\\subseteq\[n\]\\times\[n\]denotes the edge set\. The matrixAAis supported on the graph𝒢\\mathcal\{G\}and doubly stochastic, i\.e\.,

- •Ai​j\>0A\_\{ij\}\>0only if\(i,j\)∈E\(i,j\)\\in Eori=ji=j;
- •∑j=1nAi​j=1,∀i∈\[n\]\\sum\_\{j=1\}^\{n\}A\_\{ij\}=1,\\forall i\\in\[n\]and∑i=1nAi​j=1,∀j∈\[n\]\\sum\_\{i=1\}^\{n\}A\_\{ij\}=1,\\forall j\\in\[n\]\.

Moreover,AAis symmetric and positive semidefinite\.

###### Assumption 3\.2\.

LetQ​\(⋅\)Q\(\\cdot\):ℝd→ℝd\\mathbb\{R\}^\{d\}\\rightarrow\\mathbb\{R\}^\{d\}denote a compressor, whose output can be encoded with fewer bits than the original input\. For someω∈\(0,1\]\\omega\\in\(0,1\], it satisfies

𝔼Q​\[‖Q​\(𝐱\)−𝐱‖22\]≤\(1−ω\)​‖𝐱‖22,∀𝐱∈ℝd,\\mathbb\{E\}\_\{Q\}\[\\\|Q\(\\mathbf\{x\}\)\-\\mathbf\{x\}\\\|\_\{2\}^\{2\}\]\\leq\(1\-\\omega\)\\\|\\mathbf\{x\}\\\|\_\{2\}^\{2\},\\quad\\forall\\mathbf\{x\}\\in\\mathbb\{R\}^\{d\},where𝔼Q\\mathbb\{E\}\_\{Q\}denotes the expectation over the possible randomness ofQQ\.

###### Assumption 3\.3\.

The convex set𝒦\\mathcal\{K\}is full dimensional, and there exist two constantsr,R\>0r,R\>0such thatr​ℬd⊆𝒦⊆R​ℬdr\\mathcal\{B\}^\{d\}\\subseteq\\mathcal\{K\}\\subseteq R\\mathcal\{B\}^\{d\}, whereℬd\\mathcal\{B\}^\{d\}denotes the unit Euclidean ball centered at the origin inℝd\\mathbb\{R\}^\{d\}\.

###### Assumption 3\.4\.

At each roundt∈\[T\]t\\in\[T\], the loss functionft,i​\(𝐱\)f\_\{t,i\}\(\\mathbf\{x\}\)of each learneri∈\[n\]i\\in\[n\]isGG\-Lipschitz over𝒦\\mathcal\{K\}, i\.e\., it holds that\|ft,i​\(𝐱\)−ft,i​\(𝐲\)\|≤G​‖𝐱−𝐲‖2,∀𝐱,𝐲∈𝒦\|f\_\{t,i\}\(\\mathbf\{x\}\)\-f\_\{t,i\}\(\\mathbf\{y\}\)\|\\leq G\\\|\\mathbf\{x\}\-\\mathbf\{y\}\\\|\_\{2\},~\\forall\\mathbf\{x\},\\mathbf\{y\}\\in\\mathcal\{K\}\.

###### Assumption 3\.5\.

At each roundt∈\[T\]t\\in\[T\], the loss functionft,i​\(𝐱\)f\_\{t,i\}\(\\mathbf\{x\}\)of each learneri∈\[n\]i\\in\[n\]isα\\alpha\-strongly convex over𝒦\\mathcal\{K\}, i\.e\., it holds thatft,i​\(𝐲\)≥ft,i​\(𝐱\)\+⟨∇ft,i​\(𝐱\),𝐲−𝐱⟩\+α2​‖𝐲−𝐱‖22,∀𝐱,𝐲∈𝒦\.f\_\{t,i\}\(\\mathbf\{y\}\)\\geq f\_\{t,i\}\(\\mathbf\{x\}\)\+\\langle\\nabla f\_\{t,i\}\(\\mathbf\{x\}\),\\mathbf\{y\}\-\\mathbf\{x\}\\rangle\+\\frac\{\\alpha\}\{2\}\\\|\\mathbf\{y\}\-\\mathbf\{x\}\\\|\_\{2\}^\{2\},~\\forall\\mathbf\{x\},\\mathbf\{y\}\\in\\mathcal\{K\}\.

###### Assumption 3\.6\.

At each roundtt, the loss functionft,i​\(𝐱\)f\_\{t,i\}\(\\mathbf\{x\}\)of each learneri∈\[n\]i\\in\[n\]is bounded over𝒦\\mathcal\{K\}, i\.e\.,\|ft,i​\(𝐱\)\|≤M\|f\_\{t,i\}\(\\mathbf\{x\}\)\|\\leq Mfor any𝐱∈𝒦\\mathbf\{x\}\\in\\mathcal\{K\}\. Moreover, all loss functions are chosen beforehand, i\.e\., the adversary is oblivious\.

Remark\.First, from Assumption[3\.1](https://arxiv.org/html/2607.01665#S3.Thmtheorem1), the eigenvalues ofAAcan be denoted as1=λ1​\(A\)\>λ2​\(A\)≥⋯≥λn​\(A\)1=\\lambda\_\{1\}\(A\)\>\\lambda\_\{2\}\(A\)\\geq\\cdots\\geq\\lambda\_\{n\}\(A\), and the spectral gap isρ=1−λ2​\(A\)\\rho=1\-\\lambda\_\{2\}\(A\)\. Second, as discussed inKoloskova et al\. \([2019](https://arxiv.org/html/2607.01665#bib.bib15)\), Assumption[3\.2](https://arxiv.org/html/2607.01665#S3.Thmtheorem2)captures a broad class of both biased and unbiased compressors \(see Appendix[I](https://arxiv.org/html/2607.01665#A9)for detailed discussions\)\. Third, Assumption[3\.5](https://arxiv.org/html/2607.01665#S3.Thmtheorem5)withα=0\\alpha=0reduces to the case with general convex functions, which are also considered in this paper\. Finally, Assumptions[3\.3](https://arxiv.org/html/2607.01665#S3.Thmtheorem3)and[3\.6](https://arxiv.org/html/2607.01665#S3.Thmtheorem6)are mainly required by the bandit setting\. One can verify that in the full\-information setting, the former can be simplified to‖𝐱‖2≤R,∀𝐱∈𝒦\\\|\\mathbf\{x\}\\\|\_\{2\}\\leq R,\\forall\\mathbf\{x\}\\in\\mathcal\{K\}, and the latter can be removed\.

### 3\.2Algorithm for full\-information setting

Before introducing our algorithms, we first briefly recall the best existing algorithm for D\-OCO with exact communication, i\.e\., AD\-FTGL\(Wan et al\.,[2024](https://arxiv.org/html/2607.01665#bib.bib26),[2025](https://arxiv.org/html/2607.01665#bib.bib27)\)\. Specifically, it adopts a blocking update mechanism with block sizeLL, i\.e\., dividing the totalTTrounds intoT/LT/Lblocks,222Without loss of generality,T/LT/Lis assumed to be an integer\.and only maintaining a decision𝐱i​\(z\)\\mathbf\{x\}\_\{i\}\(z\)for all rounds in each blockzz\. The initial decision is simply set as𝐱i​\(1\)=𝟎\\mathbf\{x\}\_\{i\}\(1\)=\\mathbf\{0\}\. To update the decision, it exploits an accelerated gossip strategy\(Liu and Morse,[2011](https://arxiv.org/html/2607.01665#bib.bib18)\)to maintain a dual variable𝐳i​\(z\)≈∑τ=1z−1\(1/n\)​∑i=1n𝐝i​\(τ\)\\mathbf\{z\}\_\{i\}\(z\)\\approx\\sum\_\{\\tau=1\}^\{z\-1\}\(1/n\)\\sum\_\{i=1\}^\{n\}\\mathbf\{d\}\_\{i\}\(\\tau\), where𝐝i​\(τ\)=∑t∈𝒯τ\(∇ft,i​\(𝐱i​\(τ\)\)−α​𝐱i​\(τ\)\)\\mathbf\{d\}\_\{i\}\(\\tau\)=\\sum\_\{t\\in\\mathcal\{T\}\_\{\\tau\}\}\(\\nabla f\_\{t,i\}\(\\mathbf\{x\}\_\{i\}\(\\tau\)\)\-\\alpha\\mathbf\{x\}\_\{i\}\(\\tau\)\)and𝒯τ=\{\(τ−1\)​L\+1,…,τ​L\}\\mathcal\{T\}\_\{\\tau\}=\\\{\(\\tau\-1\)L\+1,\\ldots,\\tau L\\\}\. Based on𝐳i​\(z\)\\mathbf\{z\}\_\{i\}\(z\), it computes

𝐱i​\(z\+1\)=argmin𝐱∈𝒦⟨𝐳i​\(z\),𝐱⟩\+\(z−1\)​L​α\+2​h2​‖𝐱‖22,\\mathbf\{x\}\_\{i\}\(z\+1\)=\\operatorname\*\{argmin\}\_\{\\mathbf\{x\}\\in\\mathcal\{K\}\}\\langle\\mathbf\{z\}\_\{i\}\(z\),\\mathbf\{x\}\\rangle\+\\frac\{\(z\-1\)L\\alpha\+2h\}\{2\}\\\|\\mathbf\{x\}\\\|\_\{2\}^\{2\},\(1\)wherehhis a parameter\. Let𝐝¯​\(z\)=\(1/n\)​∑i=1n𝐝i​\(z\)\\bar\{\\mathbf\{d\}\}\(z\)=\(1/n\)\\sum\_\{i=1\}^\{n\}\\mathbf\{\\mathbf\{d\}\}\_\{i\}\(z\)and𝐳¯​\(z\)=∑τ=1z−1𝐝¯​\(τ\)\\bar\{\\mathbf\{z\}\}\(z\)=\\sum\_\{\\tau=1\}^\{z\-1\}\\bar\{\\mathbf\{d\}\}\(\\tau\)\. According to their analysis, the regret of AD\-FTGL can be decomposed into two parts: one about the cumulative consensus error of‖𝐳i​\(z\)−𝐳¯​\(z\)‖2\\\|\\mathbf\{z\}\_\{i\}\(z\)\-\\bar\{\\mathbf\{z\}\}\(z\)\\\|\_\{2\}and the other about the regret of a virtual update based on𝐳¯​\(z\)\\bar\{\\mathbf\{z\}\}\(z\)\.

Therefore, the critical challenge for extending AD\-FTGL into D\-OCO with compressed communication becomes how to maintain𝐳i​\(z\)\\mathbf\{z\}\_\{i\}\(z\)with a small consensus error in this case\. To this end, we introduce Choco\-Gossip\(Koloskova et al\.,[2019](https://arxiv.org/html/2607.01665#bib.bib15)\), whose detailed procedure is outlined in Algorithm[1](https://arxiv.org/html/2607.01665#alg1), and the following lemma\.

###### Lemma 3\.7\.

Letβ:=‖I−A‖2\\beta:=\\\|I\-A\\\|\_\{2\},𝐳¯k=\(1/n\)​∑i=1n𝐳ik\\bar\{\\mathbf\{z\}\}^\{k\}=\(1/n\)\\sum\_\{i=1\}^\{n\}\\mathbf\{z\}\_\{i\}^\{k\}andek=𝔼​\[∑i=1n‖𝐳ik−𝐳¯k‖22\]\+𝔼​\[∑i=1n‖𝐳ik−𝐳^ik‖22\]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\}\], whereIIis the identity matrix\. Under Assumptions[3\.1](https://arxiv.org/html/2607.01665#S3.Thmtheorem1)and[3\.2](https://arxiv.org/html/2607.01665#S3.Thmtheorem2), Algorithm[1](https://arxiv.org/html/2607.01665#alg1)with𝐬i0=∑j=1nAi​j​𝐳^j0,∀i∈\[n\]\\mathbf\{s\}\_\{i\}^\{0\}=\\sum\_\{j=1\}^\{n\}A\_\{ij\}\\hat\{\\mathbf\{z\}\}\_\{j\}^\{0\},\\forall i\\in\[n\]and

γ=ρ​ω2​\(1−ω\)​\(ρ\+2\)​β2\+16​ρ−8​ρ​ω\+ρ2,\\gamma=\\frac\{\\rho\\omega\}\{2\(1\-\\omega\)\(\\rho\+2\)\\beta^\{2\}\+16\\rho\-8\\rho\\omega\+\\rho^\{2\}\},\(2\)ensuresek≤\(1−γ​ρ/2\)k​e0e^\{k\}\\leq\(1\-\\gamma\\rho/2\)^\{k\}e^\{0\}for anyk∈\[K\]k\\in\[K\]\.

Givennnlocal vectors\{𝐳i0\}i∈\[n\]\\\{\\mathbf\{z\}\_\{i\}^\{0\}\\\}\_\{i\\in\[n\]\}in a decentralized network, the role of Choco\-Gossip is to approximately compute their average𝐳¯=\(1/n\)​∑i=1n𝐳i0\\bar\{\\mathbf\{z\}\}=\(1/n\)\\sum\_\{i=1\}^\{n\}\\mathbf\{z\}\_\{i\}^\{0\}via only compressed communication, which is known as the average consensus problem\. Since it is easy to verify that𝐳¯k=𝐳¯\\bar\{\\mathbf\{z\}\}^\{k\}=\\bar\{\\mathbf\{z\}\}, Lemma[3\.7](https://arxiv.org/html/2607.01665#S3.Thmtheorem7)is sufficient to provide an upper bound on the consensus error\.

Remark\.Note that Algorithm[1](https://arxiv.org/html/2607.01665#alg1)follows a memory\-efficient implementation of Choco\-Gossip, which can be found in the appendix ofKoloskova et al\. \([2019](https://arxiv.org/html/2607.01665#bib.bib15)\)\. Moreover, our Lemma[3\.7](https://arxiv.org/html/2607.01665#S3.Thmtheorem7)actually is a generalized and refined version of the original guarantee on Choco\-Gossip\. To be precise, Theorem 2 ofKoloskova et al\. \([2019](https://arxiv.org/html/2607.01665#bib.bib15)\)only showsek≤\(1−ω​ρ2/82\)k​e0e^\{k\}\\leq\(1\-\\omega\\rho^\{2\}/82\)^\{k\}e^\{0\}with the initialization𝐳^i0=𝟎\\hat\{\\mathbf\{z\}\}\_\{i\}^\{0\}=\\mathbf\{0\}\(and𝐬i0=𝟎\\mathbf\{s\}\_\{i\}^\{0\}=\\mathbf\{0\}for the memory\-efficient implementation\), which cannot recover the classicalO​\(\(1−ρ\)k\)O\(\(1\-\\rho\)^\{k\}\)consensus error bound of the standard gossip\(Xiao and Boyd,[2004](https://arxiv.org/html/2607.01665#bib.bib34)\)even ifω=1\\omega=1\. In contrast, our lemma holds for more flexible initialization with a worst\-case bound ofO​\(\(1−ω​ρ2\)k\)O\(\(1\-\\omega\\rho^\{2\}\)^\{k\}\)and an improved bound ofO​\(\(1−ω​ρ\)k\)O\(\(1\-\\omega\\rho\)^\{k\}\)ifω=1\\omega=1\. Such initialization makes Choco\-Gossip plug\-and\-play in our algorithms, and the improvement may be also of independent interest\.

Algorithm 1Choco\-Gossip \(CG\)1:Input:Original vectors

\{𝐳i0\}i∈\[n\]\\\{\\mathbf\{z\}\_\{i\}^\{0\}\\\}\_\{i\\in\[n\]\}, initial compressed vectors

\{𝐳^i0\}i∈\[n\]\\\{\\hat\{\\mathbf\{z\}\}\_\{i\}^\{0\}\\\}\_\{i\\in\[n\]\}, initial intermediate vectors

\{𝐬i0\}i∈\[n\]\\\{\\mathbf\{s\}\_\{i\}^\{0\}\\\}\_\{i\\in\[n\]\}, step size

γ\\gamma, number of iterations

KK
2:for

k=0​…​K−1k=0\\dots K\-1in parallelfor each

i∈\[n\]i\\in\[n\]do

3:Compress the difference as

𝐪ik=Q​\(𝐳ik−𝐳^ik\)\\mathbf\{q\}\_\{i\}^\{k\}=Q\(\\mathbf\{z\}\_\{i\}^\{k\}\-\\hat\{\\mathbf\{z\}\}\_\{i\}^\{k\}\)
4:Send

𝐪ik\\mathbf\{q\}\_\{i\}^\{k\}to neighbors and receive

𝐪jk\\mathbf\{q\}\_\{j\}^\{k\}
5:

𝐳^ik\+1=𝐳^ik\+𝐪ik\\hat\{\\mathbf\{z\}\}\_\{i\}^\{k\+1\}=\\hat\{\\mathbf\{z\}\}\_\{i\}^\{k\}\+\\mathbf\{q\}\_\{i\}^\{k\},

𝐬ik\+1=𝐬ik\+∑j=1nAi​j​𝐪jk\\mathbf\{s\}\_\{i\}^\{k\+1\}=\\mathbf\{s\}\_\{i\}^\{k\}\+\\sum\_\{j=1\}^\{n\}A\_\{ij\}\\mathbf\{q\}\_\{j\}^\{k\}
6:

𝐳ik\+1=𝐳ik\+γ​\(𝐬ik\+1−𝐳^ik\+1\)\\mathbf\{z\}\_\{i\}^\{k\+1\}=\\mathbf\{z\}\_\{i\}^\{k\}\+\\gamma\(\\mathbf\{s\}\_\{i\}^\{k\+1\}\-\\hat\{\\mathbf\{z\}\}\_\{i\}^\{k\+1\}\)
7:endfor

Now, we are ready to combine AD\-FTGL with only compressed communication\. For brevity, letCG\(⋅,⋅,⋅,⋅,⋅\)\\operatorname\*\{CG\}\(\\cdot,\\cdot,\\cdot,\\cdot,\\cdot\)denote Choco\-Gossip in Algorithm[1](https://arxiv.org/html/2607.01665#alg1)\. A natural idea is to applying Choco\-Gossip over\{𝐝i​\(z−1\)\}i∈\[n\]\\\{\\mathbf\{d\}\_\{i\}\(z\-1\)\\\}\_\{i\\in\[n\]\}during each blockzzto generate

\{𝐝iK​\(z−1\)\}i∈\[n\]=CG\(\{𝐝i​\(z−1\)\}i∈\[n\],\{𝟎\}i∈\[n\],\{𝟎\}i∈\[n\],γ,K\),\\\{\\mathbf\{d\}^\{K\}\_\{i\}\(z\-1\)\\\}\_\{i\\in\[n\]\}=\\operatorname\*\{CG\}\(\\\{\\mathbf\{d\}\_\{i\}\(z\-1\)\\\}\_\{i\\in\[n\]\},\\\{\\mathbf\{0\}\\\}\_\{i\\in\[n\]\},\\\{\\mathbf\{0\}\\\}\_\{i\\in\[n\]\},\\gamma,K\),and then setting𝐳i​\(z\)=∑τ=1z−1𝐝iK​\(z−1\)\\mathbf\{z\}\_\{i\}\(z\)=\\sum\_\{\\tau=1\}^\{z\-1\}\\mathbf\{d\}^\{K\}\_\{i\}\(z\-1\)\. However, in this way, we need to setKKproportional toO​\(log⁡T\)O\(\\log T\)for making the cumulative consensus error sufficiently small\. To address this issue, we exploit Choco\-Gossip in a more careful way\. Specifically, we simply set𝐳i​\(1\)=𝐳^i​\(1\)=𝐬i​\(z\)=𝟎\\mathbf\{z\}\_\{i\}\(1\)\\\!=\\hat\{\\mathbf\{z\}\}\_\{i\}\(1\)\\\!=\\mathbf\{s\}\_\{i\}\(z\)=\\mathbf\{0\}for anyi∈\[n\]i\\in\[n\]\. For each blockz≥2z\\geq 2, we first set𝐳i0​\(z\)=𝐳i​\(z−1\)\+𝐝i​\(z−1\)\\mathbf\{z\}\_\{i\}^\{0\}\(z\)=\\mathbf\{z\}\_\{i\}\(z\-1\)\+\\mathbf\{d\}\_\{i\}\(z\-1\),𝐳^i0​\(z\)=𝐳^i​\(z−1\)\\hat\{\\mathbf\{z\}\}\_\{i\}^\{0\}\(z\)=\\hat\{\\mathbf\{z\}\}\_\{i\}\(z\-1\), and𝐬i0​\(z\)=𝐬i​\(z−1\)\\mathbf\{s\}\_\{i\}^\{0\}\(z\)=\\mathbf\{s\}\_\{i\}\(z\-1\)\. Then, we apply Choco\-Gossip as

\(\{𝐳iK​\(z\)\}i∈\[n\],\{𝐳^iK​\(z\)\}i∈\[n\],\{𝐬iK​\(z\)\}i∈\[n\]\)=CG\(\{𝐳i0​\(z\)\}i∈\[n\],\{𝐳^i0​\(z\)\}i∈\[n\],\{𝐬i0​\(z\)\}i∈\[n\],γ,K\),\\begin\{split\}&\\left\(\\\{\\mathbf\{z\}^\{K\}\_\{i\}\(z\)\\\}\_\{i\\in\[n\]\},\\\{\\hat\{\\mathbf\{z\}\}^\{K\}\_\{i\}\(z\)\\\}\_\{i\\in\[n\]\},\\\{\\mathbf\{s\}^\{K\}\_\{i\}\(z\)\\\}\_\{i\\in\[n\]\}\\right\)\\\\ =&\\operatorname\*\{CG\}\(\\\{\\mathbf\{z\}\_\{i\}^\{0\}\(z\)\\\}\_\{i\\in\[n\]\},\\\{\\hat\{\\mathbf\{z\}\}^\{0\}\_\{i\}\(z\)\\\}\_\{i\\in\[n\]\},\\\{\\mathbf\{s\}^\{0\}\_\{i\}\(z\)\\\}\_\{i\\in\[n\]\},\\gamma,K\),\\end\{split\}\(3\)and set𝐳i​\(z\)=𝐳iK​\(z\)\\mathbf\{z\}\_\{i\}\(z\)=\\mathbf\{z\}\_\{i\}^\{K\}\(z\),𝐳^i​\(z\)=𝐳^iK​\(z\)\\hat\{\\mathbf\{z\}\}\_\{i\}\(z\)=\\hat\{\\mathbf\{z\}\}^\{K\}\_\{i\}\(z\), and𝐬i​\(z\)=𝐬iK​\(z\)\\mathbf\{s\}\_\{i\}\(z\)=\\mathbf\{s\}\_\{i\}^\{K\}\(z\)\. In this way, once𝐝i​\(z−1\)\\mathbf\{d\}\_\{i\}\(z\-1\)is incorporated into𝐳i​\(z\)\\mathbf\{z\}\_\{i\}\(z\), it will also be affected by the subsequent Choco\-Gossip\. Thus,KKcan be independent ofTT\.

Algorithm 2CD\-FTGL1:Input:strongly convex factor

α\\alpha, regularization parameter

hh, block size

LL, consensus step size

γ\\gamma
2:

𝐱i​\(1\)=𝐳i​\(1\)=𝐳^i​\(1\)=𝐬i​\(1\)=𝟎,∀i∈\[n\]\\mathbf\{x\}\_\{i\}\(1\)\\\!=\\mathbf\{z\}\_\{i\}\(1\)\\\!=\\hat\{\\mathbf\{z\}\}\_\{i\}\(1\)\\\!=\\mathbf\{s\}\_\{i\}\(1\)\\\!=\\mathbf\{0\},\\forall i\\in\[n\]
3:for

z=1,…,T/Lz=1,\\dots,T/Lin parallelfor each

i∈\[n\]i\\in\[n\]do

4:for

t=\(z−1\)​L\+1,…,z​Lt=\(z\-1\)L\+1,\\dots,zLdo

5:Play

𝐱i​\(z\)\\mathbf\{x\}\_\{i\}\(z\)and observe

∇ft,i​\(𝐱i​\(z\)\)\\nabla f\_\{t,i\}\(\\mathbf\{x\}\_\{i\}\(z\)\)
6:endfor

7:if

z≥2z\\geq 2then

8:

𝐳i0​\(z\)=𝐳i​\(z−1\)\+𝐝i​\(z−1\)\\mathbf\{z\}\_\{i\}^\{0\}\(z\)=\\mathbf\{z\}\_\{i\}\(z\-1\)\+\\mathbf\{d\}\_\{i\}\(z\-1\),

𝐳^i0​\(z\)=𝐳^i​\(z−1\)\\hat\{\\mathbf\{z\}\}\_\{i\}^\{0\}\(z\)=\\hat\{\\mathbf\{z\}\}\_\{i\}\(z\-1\), and

𝐬i0​\(z\)=𝐬i​\(z−1\)\\mathbf\{s\}\_\{i\}^\{0\}\(z\)=\\mathbf\{s\}\_\{i\}\(z\-1\)
9:Set

K=LK=Land compute

𝐳iK​\(z\),𝐳^iK​\(z\),𝐬iK​\(z\)\\mathbf\{z\}^\{K\}\_\{i\}\(z\),\\hat\{\\mathbf\{z\}\}^\{K\}\_\{i\}\(z\),\\mathbf\{s\}^\{K\}\_\{i\}\(z\)by invoking Algorithm[1](https://arxiv.org/html/2607.01665#alg1)as in \([3](https://arxiv.org/html/2607.01665#S3.E3)\)

10:

𝐳i​\(z\)=𝐳iK​\(z\)\\mathbf\{z\}\_\{i\}\(z\)=\\mathbf\{z\}\_\{i\}^\{K\}\(z\),

𝐳^i​\(z\)=𝐳^iK​\(z\)\\hat\{\\mathbf\{z\}\}\_\{i\}\(z\)=\\hat\{\\mathbf\{z\}\}\_\{i\}^\{K\}\(z\),

𝐬i​\(z\)=𝐬iK​\(z\)\\mathbf\{s\}\_\{i\}\(z\)=\\mathbf\{s\}\_\{i\}^\{K\}\(z\)
11:endif

12:

𝐝i​\(z\)=∑t∈𝒯z\(∇ft,i​\(𝐱i​\(z\)\)−α​𝐱i​\(z\)\)\\mathbf\{d\}\_\{i\}\(z\)=\\sum\_\{t\\in\\mathcal\{T\}\_\{z\}\}\(\\nabla f\_\{t,i\}\(\\mathbf\{x\}\_\{i\}\(z\)\)\-\\alpha\\mathbf\{x\}\_\{i\}\(z\)\)
13:Compute

𝐱i​\(z\+1\)\\mathbf\{x\}\_\{i\}\(z\+1\)via \([1](https://arxiv.org/html/2607.01665#S3.E1)\)

14:endfor

From the above discussions, we propose our first algorithm called compressed decentralized follow\-the\-generalized\-leader \(CD\-FTGL\)\. The detailed procedure is summarized in Algorithm[2](https://arxiv.org/html/2607.01665#alg2)\.

Remark\.First, we want to emphasize that in step 9 of Algorithm[2](https://arxiv.org/html/2607.01665#alg2), the invocation of Algorithm[1](https://arxiv.org/html/2607.01665#alg1)can be implemented in parallel to the*for*loop from steps 4 to 6, which implies that both the computation and communication costs can be allocated to each round in blockzz\. Second, we notice thatYang et al\. \([2026](https://arxiv.org/html/2607.01665#bib.bib36)\)also exploit Choco\-Gossip in a similar way, but to control the consensus error among decisions\. Moreover, according to the OGD\-type update of decision, they need to use a more complicated blocking mechanism and a repeated compressor to eliminate the effect of a projection operation on the consensus error\. In contrast, in our algorithm, the consensus error can be controlled independent of the projection\.

By combining the existing analysis of AD\-FTGL\(Wan et al\.,[2024](https://arxiv.org/html/2607.01665#bib.bib26),[2025](https://arxiv.org/html/2607.01665#bib.bib27)\)and Lemma[3\.7](https://arxiv.org/html/2607.01665#S3.Thmtheorem7), we first establish a general guarantee on the regret of Algorithm[2](https://arxiv.org/html/2607.01665#alg2)\.

###### Theorem 3\.8\.

Under Assumptions[3\.1](https://arxiv.org/html/2607.01665#S3.Thmtheorem1),[3\.2](https://arxiv.org/html/2607.01665#S3.Thmtheorem2),[3\.3](https://arxiv.org/html/2607.01665#S3.Thmtheorem3),[3\.4](https://arxiv.org/html/2607.01665#S3.Thmtheorem4), and[3\.5](https://arxiv.org/html/2607.01665#S3.Thmtheorem5), for anyi∈\[n\]i\\in\[n\], Algorithm[2](https://arxiv.org/html/2607.01665#alg2)withL=⌈2​ln⁡\(n\+2\)/\(γ​ρ\)⌉L=\\left\\lceil 2\\ln\(n\+2\)/\(\\gamma\\rho\)\\right\\rceil, whereγ\\gammais defined in \([2](https://arxiv.org/html/2607.01665#S3.E2)\), ensures

𝔼​\[RT,i\]≤n​h​R2\+∑z=2T/L6​n​L2​G​\(G\+α​R\)\(z−2\)​L​α\+2​h\+∑z=1T/L12​n​L2​G​\(G\+2​α​R\)z​L​α\+2​h\.\\mathbb\{E\}\[R\_\{T,i\}\]\\leq nhR^\{2\}\+\\sum\_\{z=2\}^\{T/L\}\\frac\{6nL^\{2\}G\(G\+\\alpha R\)\}\{\(z\-2\)L\\alpha\+2h\}\+\\sum\_\{z=1\}^\{T/L\}\\frac\{12nL^\{2\}G\(G\+2\\alpha R\)\}\{zL\\alpha\+2h\}\.\(4\)

By further tuninghh, we obtain the following regret bounds for convex and strongly convex functions\.

###### Corollary 3\.9\.

Under Assumptions[3\.1](https://arxiv.org/html/2607.01665#S3.Thmtheorem1),[3\.2](https://arxiv.org/html/2607.01665#S3.Thmtheorem2),[3\.3](https://arxiv.org/html/2607.01665#S3.Thmtheorem3),[3\.4](https://arxiv.org/html/2607.01665#S3.Thmtheorem4), and[3\.5](https://arxiv.org/html/2607.01665#S3.Thmtheorem5)withα=0\\alpha=0, for anyi∈\[n\]i\\in\[n\], Algorithm[2](https://arxiv.org/html/2607.01665#alg2)withh=3​L​T​G/Rh=3\\sqrt\{LT\}G/RandL=⌈2​ln⁡\(n\+2\)/\(γ​ρ\)⌉L=\\left\\lceil 2\\ln\(n\+2\)/\(\\gamma\\rho\)\\right\\rceilensures

𝔼​\[RT,i\]≤6​n​G​R​L​T\.\\mathbb\{E\}\[R\_\{T,i\}\]\\leq 6nGR\\sqrt\{LT\}\.

###### Corollary 3\.10\.

Under Assumptions[3\.1](https://arxiv.org/html/2607.01665#S3.Thmtheorem1),[3\.2](https://arxiv.org/html/2607.01665#S3.Thmtheorem2),[3\.3](https://arxiv.org/html/2607.01665#S3.Thmtheorem3),[3\.4](https://arxiv.org/html/2607.01665#S3.Thmtheorem4), and[3\.5](https://arxiv.org/html/2607.01665#S3.Thmtheorem5)withα\>0\\alpha\>0, for anyi∈\[n\]i\\in\[n\], Algorithm[2](https://arxiv.org/html/2607.01665#alg2)withh=α​Lh=\\alpha LandL=⌈2​ln⁡\(n\+2\)/\(γ​ρ\)⌉L=\\left\\lceil 2\\ln\(n\+2\)/\(\\gamma\\rho\)\\right\\rceilensures

𝔼​\[RT,i\]≤n​α​R2​L\+3​n​G​\(5​G\+9​α​R\)​Lα​ln⁡\(T/L\)\.\\mathbb\{E\}\[R\_\{T,i\}\]\\leq n\\alpha R^\{2\}L\+\\frac\{3nG\(5G\+9\\alpha R\)L\}\{\\alpha\}\\ln\\left\(T/L\\right\)\.

Remark\.From these two corollaries and the definition ofγ\\gammain \([2](https://arxiv.org/html/2607.01665#S3.E2)\), our CD\-FTGL achievesO~​\(ω−1/2​ρ−1​n​T\)\\tilde\{O\}\(\\omega^\{\-1/2\}\\rho^\{\-1\}n\\sqrt\{T\}\)andO~​\(ω−1​ρ−2​n​log⁡T\)\\tilde\{O\}\(\\omega^\{\-1\}\\rho^\{\-2\}n\\log T\)regret bounds for convex and strongly convex functions, respectively\. Notably, our results match the current best upper bounds achieved byYang et al\. \([2026](https://arxiv.org/html/2607.01665#bib.bib36)\)\. Moreover,Yang et al\. \([2026](https://arxiv.org/html/2607.01665#bib.bib36)\)also establishedΩ​\(ω−1/2​ρ−1/4​n​T\)\\Omega\(\\omega^\{\-1/2\}\\rho^\{\-1/4\}n\\sqrt\{T\}\)andΩ​\(ω−1​ρ−1/2​n​log⁡T\)\\Omega\(\\omega^\{\-1\}\\rho^\{\-1/2\}n\\log T\)lower bounds for these two settings\. This indicates that our dependencies onω,n\\omega,nandTTare already nearly optimal\. Furthermore, based on the discussions about the consensus error in Lemma[3\.7](https://arxiv.org/html/2607.01665#S3.Thmtheorem7), ifω=1\\omega=1, our two regret bounds improve toO~​\(ρ−1/2​n​T\)\\tilde\{O\}\(\\rho^\{\-1/2\}n\\sqrt\{T\}\)andO~​\(ρ−1​n​log⁡T\)\\tilde\{O\}\(\\rho^\{\-1\}n\\log T\), which recovers the best existing results for D\-OCO algorithms with standard gossip\(Xiao and Boyd,[2004](https://arxiv.org/html/2607.01665#bib.bib34)\)\.333Actually, the original analysis of both D\-OGD and D\-FTRL does not provide these results, which are first achieved byWan et al\. \([2025](https://arxiv.org/html/2607.01665#bib.bib27)\)with a refined analysis on the consensus error\.In contrast, even ifω=1\\omega=1, the regret bounds ofYang et al\. \([2026](https://arxiv.org/html/2607.01665#bib.bib36)\)will only becomeO~​\(ρ−1​n​T\)\\tilde\{O\}\(\\rho^\{\-1\}n\\sqrt\{T\}\)andO~​\(ρ−2​n​log⁡T\)\\tilde\{O\}\(\\rho^\{\-2\}n\\log T\)\.

### 3\.3Algorithm for bandit setting

Compared with the full\-information setting, the critical challenge of the bandit setting is that only the value of each local function at the played decision can be observed\. Fortunately, in the literature, there exists a well\-known technique called the one\-point estimator\(Flaxman et al\.,[2005](https://arxiv.org/html/2607.01665#bib.bib10)\)that can generate an approximate gradient by using a single loss value\. It can be formalized as the following lemma, whereℬd\\mathcal\{B\}^\{d\}and𝒮d\\mathcal\{S\}^\{d\}denotes the unit ball and sphere centered at the origin inℝd\\mathbb\{R\}^\{d\}, respectively\.

###### Lemma 3\.11\.

\(Lemma 1 inFlaxman et al\. \([2005](https://arxiv.org/html/2607.01665#bib.bib10)\)\) For any functionf​\(𝐱\):𝒦↦ℝf\(\\mathbf\{x\}\):\\mathcal\{K\}\\mapsto\\mathbb\{R\}andϵ\>0\\epsilon\>0, we define itsϵ\\epsilon\-smoothed version asf^ϵ​\(𝐱\)=𝔼𝐮∼ℬd​\[f​\(𝐱\+ϵ​𝐮\)\]\\hat\{f\}\_\{\\epsilon\}\(\\mathbf\{x\}\)=\\mathbb\{E\}\_\{\\mathbf\{u\}\\sim\\mathcal\{B\}^\{d\}\}\[f\(\\mathbf\{x\}\+\\epsilon\\mathbf\{u\}\)\]\. Then, it holds that

∇f^ϵ​\(𝐱\)=𝔼𝐮∼𝒮d​\[dϵ​f​\(𝐱\+ϵ​𝐮\)​𝐮\]\.\\nabla\\hat\{f\}\_\{\\epsilon\}\(\\mathbf\{x\}\)=\\mathbb\{E\}\_\{\\mathbf\{u\}\\sim\\mathcal\{S\}^\{d\}\}\\left\[\\frac\{d\}\{\\epsilon\}f\(\\mathbf\{x\}\+\\epsilon\\mathbf\{u\}\)\\mathbf\{u\}\\right\]\.

By combining our CD\-FTGL with this technique, our bandit algorithm is outlined in Algorithm[3](https://arxiv.org/html/2607.01665#alg3), and named as compressed decentralized follow\-the\-bandit\-leader \(CD\-FTBL\)\.

Specifically, compared with CD\-FTGL, there exist some critical differences\. First, to apply the one\-point estimator, in step 5 of Algorithm[3](https://arxiv.org/html/2607.01665#alg3), we play𝐲i​\(t\)=𝐱i​\(z\)\+ϵ​𝐮i​\(t\)\\mathbf\{y\}\_\{i\}\(t\)=\\mathbf\{x\}\_\{i\}\(z\)\+\\epsilon\\mathbf\{u\}\_\{i\}\(t\), which consists of𝐱i​\(z\)\\mathbf\{x\}\_\{i\}\(z\)computed by using historical information and a random pointϵ​𝐮i​\(t\)\\epsilon\\mathbf\{u\}\_\{i\}\(t\)\. Due to𝐮i​\(t\)∼𝒮d\\mathbf\{u\}\_\{i\}\(t\)\\sim\\mathcal\{S\}^\{d\}and Assumption[3\.3](https://arxiv.org/html/2607.01665#S3.Thmtheorem3),𝐱i​\(z\)∈𝒦ϵ=\(1−ϵ/r\)​𝒦=\{\(1−ϵ/r\)​𝐱∣𝐱∈𝒦\}\\mathbf\{x\}\_\{i\}\(z\)\\in\\mathcal\{K\}\_\{\\epsilon\}=\(1\-\\epsilon/r\)\\mathcal\{K\}=\\\{\(1\-\\epsilon/r\)\\mathbf\{x\}\\mid\\mathbf\{x\}\\in\\mathcal\{K\}\\\}is a sufficient condition for𝐲i​\(t\)∈𝒦\\mathbf\{y\}\_\{i\}\(t\)\\in\\mathcal\{K\}\. Therefore, the second difference is that𝐱i​\(z\+1\)\\mathbf\{x\}\_\{i\}\(z\+1\)in step 14 of Algorithm[3](https://arxiv.org/html/2607.01665#alg3)should be computed over the shrunk set𝒦ϵ\\mathcal\{K\}\_\{\\epsilon\}, i\.e\.,

𝐱i​\(z\+1\)=argmin𝐱∈𝒦ϵ⟨𝐳i​\(z\),𝐱⟩\+\(z−1\)​L​α\+2​h2​‖𝐱‖22\.\\mathbf\{x\}\_\{i\}\(z\+1\)=\\operatorname\*\{argmin\}\_\{\\mathbf\{x\}\\in\\mathcal\{K\}\_\{\\epsilon\}\}\\langle\\mathbf\{z\}\_\{i\}\(z\),\\mathbf\{x\}\\rangle\+\\frac\{\(z\-1\)L\\alpha\+2h\}\{2\}\\\|\\mathbf\{x\}\\\|\_\{2\}^\{2\}\.\(5\)Third, instead of querying∇ft,i​\(𝐲i​\(t\)\)\\nabla f\_\{t,i\}\(\\mathbf\{y\}\_\{i\}\(t\)\), in step 6 of Algorithm[3](https://arxiv.org/html/2607.01665#alg3), we compute an approximate one as𝐠i​\(t\)=dϵ​ft,i​\(𝐲i​\(t\)\)​𝐮i​\(t\)\\mathbf\{g\}\_\{i\}\(t\)=\\frac\{d\}\{\\epsilon\}f\_\{t,i\}\(\\mathbf\{y\}\_\{i\}\(t\)\)\\mathbf\{u\}\_\{i\}\(t\), which is also used to replace the gradient originally required by𝐝i​\(z\)\\mathbf\{d\}\_\{i\}\(z\)in step 13 of Algorithm[3](https://arxiv.org/html/2607.01665#alg3)\. Finally, inspired byWan et al\. \([2022](https://arxiv.org/html/2607.01665#bib.bib25)\), we notice that a much larger block size may be used to reduce the number of communication rounds\. As a result, in step 10 of Algorithm[3](https://arxiv.org/html/2607.01665#alg3), we no longer setK=LK=Lwhen invoking Choco\-Gossip\.

Algorithm 3CD\-FTBL1:Input:strongly convex factor

α\\alpha, regularization parameter

hh, block size

LL, communication rounds

KK, consensus step size

γ\\gamma, exploration radius

ϵ\\epsilon
2:

𝐱i​\(1\)=𝐳i​\(1\)=𝐳^i​\(1\)=𝐬i​\(1\)=𝟎,∀i∈\[n\]\\mathbf\{x\}\_\{i\}\(1\)\\\!=\\mathbf\{z\}\_\{i\}\(1\)\\\!=\\hat\{\\mathbf\{z\}\}\_\{i\}\(1\)\\\!=\\mathbf\{s\}\_\{i\}\(1\)\\\!=\\mathbf\{0\},\\forall i\\in\[n\]
3:for

z=1,…,T/Lz=1,\\dots,T/Lin parallelfor each node

iido

4:for

t=\(z−1\)​L\+1,…,z​Lt=\(z\-1\)L\+1,\\dots,zLdo

5:Play

𝐲i​\(t\)=𝐱i​\(z\)\+ϵ​𝐮i​\(t\)\\mathbf\{y\}\_\{i\}\(t\)=\\mathbf\{x\}\_\{i\}\(z\)\+\\epsilon\\mathbf\{u\}\_\{i\}\(t\), where

𝐮i​\(t\)∼𝒮d\\mathbf\{u\}\_\{i\}\(t\)\\sim\\mathcal\{S\}^\{d\}
6:Compute

𝐠i​\(t\)=dϵ​ft,i​\(𝐲i​\(t\)\)​𝐮i​\(t\)\\mathbf\{g\}\_\{i\}\(t\)=\\frac\{d\}\{\\epsilon\}f\_\{t,i\}\(\\mathbf\{y\}\_\{i\}\(t\)\)\\mathbf\{u\}\_\{i\}\(t\)
7:endfor

8:if

z≥2z\\geq 2then

9:

𝐳i0​\(z\)=𝐳i​\(z−1\)\+𝐝i​\(z−1\)\\mathbf\{z\}\_\{i\}^\{0\}\(z\)=\\mathbf\{z\}\_\{i\}\(z\-1\)\+\\mathbf\{d\}\_\{i\}\(z\-1\),

𝐳^i0​\(z\)=𝐳^i​\(z−1\)\\hat\{\\mathbf\{z\}\}\_\{i\}^\{0\}\(z\)=\\hat\{\\mathbf\{z\}\}\_\{i\}\(z\-1\), and

𝐬i0​\(z\)=𝐬i​\(z−1\)\\mathbf\{s\}\_\{i\}^\{0\}\(z\)=\\mathbf\{s\}\_\{i\}\(z\-1\)
10:Compute

𝐳iK​\(z\),𝐳^iK​\(z\),𝐬iK​\(z\)\\mathbf\{z\}^\{K\}\_\{i\}\(z\),\\hat\{\\mathbf\{z\}\}^\{K\}\_\{i\}\(z\),\\mathbf\{s\}^\{K\}\_\{i\}\(z\)by invoking Algorithm[1](https://arxiv.org/html/2607.01665#alg1)as in \([3](https://arxiv.org/html/2607.01665#S3.E3)\)

11:

𝐳i​\(z\)=𝐳iK​\(z\)\\mathbf\{z\}\_\{i\}\(z\)=\\mathbf\{z\}\_\{i\}^\{K\}\(z\),

𝐳^i​\(z\)=𝐳^iK​\(z\)\\hat\{\\mathbf\{z\}\}\_\{i\}\(z\)=\\hat\{\\mathbf\{z\}\}\_\{i\}^\{K\}\(z\),

𝐬i​\(z\)=𝐬iK​\(z\)\\mathbf\{s\}\_\{i\}\(z\)=\\mathbf\{s\}\_\{i\}^\{K\}\(z\)
12:endif

13:

𝐝i​\(z\)=∑t∈𝒯z\(𝐠i​\(t\)−α​𝐱i​\(z\)\)\\mathbf\{d\}\_\{i\}\(z\)=\\sum\_\{t\\in\\mathcal\{T\}\_\{z\}\}\(\\mathbf\{g\}\_\{i\}\(t\)\-\\alpha\\mathbf\{x\}\_\{i\}\(z\)\)
14:Compute

𝐱i​\(z\+1\)\\mathbf\{x\}\_\{i\}\(z\+1\)via \([5](https://arxiv.org/html/2607.01665#S3.E5)\)

15:endfor

Moreover, we have the following guarantee regarding the regret of Algorithm[3](https://arxiv.org/html/2607.01665#alg3)\.

###### Theorem 3\.12\.

Under Assumptions[3\.1](https://arxiv.org/html/2607.01665#S3.Thmtheorem1),[3\.2](https://arxiv.org/html/2607.01665#S3.Thmtheorem2),[3\.3](https://arxiv.org/html/2607.01665#S3.Thmtheorem3),[3\.4](https://arxiv.org/html/2607.01665#S3.Thmtheorem4),[3\.5](https://arxiv.org/html/2607.01665#S3.Thmtheorem5), and[3\.6](https://arxiv.org/html/2607.01665#S3.Thmtheorem6), for anyi∈\[n\]i\\in\[n\], Algorithm[3](https://arxiv.org/html/2607.01665#alg3)withL≥K=⌈2​ln⁡\(n\+2\)/\(γ​ρ\)⌉L\\geq K=\\left\\lceil 2\\ln\(n\+2\)/\(\\gamma\\rho\)\\right\\rceilandϵ<r\\epsilon<r, ensures

𝔼​\[RT,i\]≤n​h​R2\+3​ϵ​n​G​T\+ϵ​n​G​R​Tr\+∑z=1T/L2​n​B12z​L​α\+2​h\\displaystyle\\mathbb\{E\}\[R\_\{T,i\}\]\\leq nhR^\{2\}\+3\\epsilon nGT\+\\frac\{\\epsilon nGRT\}\{r\}\+\\sum\_\{z=1\}^\{T/L\}\\frac\{2nB\_\{1\}^\{2\}\}\{zL\\alpha\+2h\}\(6\)\+∑z=1T/L6​n​L​G​B1\(z−1\)​L​α\+2​h\+∑z=2T/L6​n​L​G​B2\(z−2\)​L​α\+2​h,\\displaystyle\\quad\+\\sum\_\{z=1\}^\{T/L\}\\frac\{6nLGB\_\{1\}\}\{\(z\-1\)L\\alpha\+2h\}\+\\sum\_\{z=2\}^\{T/L\}\\frac\{6nLGB\_\{2\}\}\{\(z\-2\)L\\alpha\+2h\},whereB1=2​L​d​M/ϵ\+2​L​G\+3​α​L​RB\_\{1\}=2\\sqrt\{L\}dM/\\epsilon\+2LG\+3\\alpha LRandB2=2​L​d2​M2/ϵ2\+2​L2​G2\+2​α2​L2​R2B\_\{2\}=\\sqrt\{2Ld^\{2\}M^\{2\}/\\epsilon^\{2\}\+2L^\{2\}G^\{2\}\+2\\alpha^\{2\}L^\{2\}R^\{2\}\}\.

By further tuninghhandϵ\\epsilon, we obtain specific regret bounds for convex and strongly convex functions\.

###### Corollary 3\.13\.

Under Assumptions[3\.1](https://arxiv.org/html/2607.01665#S3.Thmtheorem1),[3\.2](https://arxiv.org/html/2607.01665#S3.Thmtheorem2),[3\.3](https://arxiv.org/html/2607.01665#S3.Thmtheorem3),[3\.4](https://arxiv.org/html/2607.01665#S3.Thmtheorem4),[3\.5](https://arxiv.org/html/2607.01665#S3.Thmtheorem5)withα=0\\alpha=0, and[3\.6](https://arxiv.org/html/2607.01665#S3.Thmtheorem6), for anyi∈\[n\]i\\in\[n\], Algorithm[3](https://arxiv.org/html/2607.01665#alg3)withK=⌈2​ln⁡\(n\+2\)/\(γ​ρ\)⌉K=\\left\\lceil 2\\ln\(n\+2\)/\(\\gamma\\rho\)\\right\\rceil,L=max⁡\{K,T\}L=\\max\\\{K,\\sqrt\{T\}\\\},h=d​L​T​M/Rh=\\sqrt\{dLT\}M/R, andϵ=c​d​T−1/4\\epsilon=c\\sqrt\{d\}\\,T^\{\-1/4\}, whereccis a constant such thatϵ<r\\epsilon<r, ensures

𝔼​\[RT,i\]=O​\(n​T3/4\+n​K​T\)\.\\mathbb\{E\}\[R\_\{T,i\}\]=O\(nT^\{3/4\}\+n\\sqrt\{KT\}\)\.

###### Corollary 3\.14\.

Under Assumptions[3\.1](https://arxiv.org/html/2607.01665#S3.Thmtheorem1),[3\.2](https://arxiv.org/html/2607.01665#S3.Thmtheorem2),[3\.3](https://arxiv.org/html/2607.01665#S3.Thmtheorem3),[3\.4](https://arxiv.org/html/2607.01665#S3.Thmtheorem4),[3\.5](https://arxiv.org/html/2607.01665#S3.Thmtheorem5)withα\>0\\alpha\>0, and[3\.6](https://arxiv.org/html/2607.01665#S3.Thmtheorem6), for anyi∈\[n\]i\\in\[n\], Algorithm[3](https://arxiv.org/html/2607.01665#alg3)withK=⌈2​ln⁡\(n\+2\)/\(γ​ρ\)⌉K=\\left\\lceil 2\\ln\(n\+2\)/\(\\gamma\\rho\)\\right\\rceil,L=max⁡\{K,T2/3​\(ln⁡T\)−2/3\}L=\\max\\\{K,T^\{2/3\}\(\\ln T\)^\{\-2/3\}\\\},h=α​Lh=\\alpha L, andϵ=c​d2/3​T−1/3​\(ln⁡T\)1/3\\epsilon=cd^\{2/3\}T^\{\-1/3\}\(\\ln T\)^\{1/3\}, whereccis a constant such thatϵ<r\\epsilon<r, ensures

𝔼​\[RT,i\]=O​\(n​T2/3​\(ln⁡T\)1/3\+n​K​log⁡T\)\.\\mathbb\{E\}\[R\_\{T,i\}\]=O\\left\(nT^\{2/3\}\(\\ln T\)^\{1/3\}\+nK\\log T\\right\)\.

Remark\.We first notice that in the above two regret bounds, only the non\-dominant term depends onρ\\rhoandω\\omegavia the definition ofKK\. This implies that our CD\-FTBL enjoys a nice ability to decouple the joint effect of the bandit feedback and the decentralized compressed communication\. Moreover, as discussed in previous studies\(Wan et al\.,[2025](https://arxiv.org/html/2607.01665#bib.bib27); Wang et al\.,[2025](https://arxiv.org/html/2607.01665#bib.bib29)\), the total number of roundsTTis commonly much larger than other problem constants\. By combining Corollaries[3\.13](https://arxiv.org/html/2607.01665#S3.Thmtheorem13)and[3\.14](https://arxiv.org/html/2607.01665#S3.Thmtheorem14)with this assumption, the two regret bounds can be simplified toO​\(n​T3/4\)O\(nT^\{3/4\}\)andO​\(n​T2/3​\(log⁡T\)1/3\)O\(nT^\{2/3\}\(\\log T\)^\{1/3\}\), which are much tighter than the best existingO~​\(ω−1/4​ρ−1/2​n​T3/4\)\\tilde\{O\}\(\\omega^\{\-1/4\}\\rho^\{\-1/2\}nT^\{3/4\}\)andO~​\(ω−1/3​ρ−2/3​n​T2/3​\(log⁡T\)1/3\)\\tilde\{O\}\(\\omega^\{\-1/3\}\\rho^\{\-2/3\}nT^\{2/3\}\(\\log T\)^\{1/3\}\)regret bounds for convex and strongly convex functions\(Yang et al\.,[2026](https://arxiv.org/html/2607.01665#bib.bib36)\)\. Finally, it is worth noting that the number of communication rounds of our CD\-FTBL isT​K/LTK/L\. Under the same assumption, Corollaries[3\.13](https://arxiv.org/html/2607.01665#S3.Thmtheorem13)and[3\.14](https://arxiv.org/html/2607.01665#S3.Thmtheorem14)only requireO~​\(ω−1​ρ−2​T\)\\tilde\{O\}\(\\omega^\{\-1\}\\rho^\{\-2\}\\sqrt\{T\}\)andO~​\(ω−1​ρ−2​T1/3​\(log⁡T\)2/3\)\\tilde\{O\}\(\\omega^\{\-1\}\\rho^\{\-2\}T^\{1/3\}\(\\log T\)^\{2/3\}\)communication rounds, respectively\. To the best of our knowledge, this is the first D\-OCO algorithm that can reduce the number of communication rounds and the bits of each communication simultaneously\.

## 4Experiments

![Refer to caption](https://arxiv.org/html/2607.01665v1/x1.png)\(a\)ijcnn1: Loss vs Rounds
![Refer to caption](https://arxiv.org/html/2607.01665v1/x2.png)\(b\)ijcnn1: Loss vs Bits
![Refer to caption](https://arxiv.org/html/2607.01665v1/x3.png)\(c\)a9a: Loss vs Rounds
![Refer to caption](https://arxiv.org/html/2607.01665v1/x4.png)\(d\)a9a: Loss vs Bits

Figure 1:Experimental results on a small random graph \(99nodes and 18 edges\) withω=0\.1\\omega=0\.1\.To verify the performance of our algorithms, we conduct experiments on the decentralized online logistic regression problem with two datasets: ijcnn1 and a9a from the LIBSVM repository\(Chang and Lin,[2011](https://arxiv.org/html/2607.01665#bib.bib8)\)\. The loss function for learneriiat roundttis given byft,i​\(𝐱\)=ln⁡\(1\+exp⁡\(−bt,i​⟨at,i,𝐱⟩\)\)f\_\{t,i\}\(\\mathbf\{x\}\)=\\ln\(1\+\\exp\(\-b\_\{t,i\}\\langle\\textbf\{a\}\_\{t,i\},\\mathbf\{x\}\\rangle\)\), whereat,i∈ℝd\\textbf\{a\}\_\{t,i\}\\in\\mathbb\{R\}^\{d\}is the feature vector andbt,i∈\{−1,1\}b\_\{t,i\}\\in\\\{\-1,1\\\}is the class label\. The decision set is defined as a bounded Euclidean ball𝒦=\{𝐱∈ℝd∣‖𝐱‖2≤τ\}\\mathcal\{K\}=\\\{\\mathbf\{x\}\\in\\mathbb\{R\}^\{d\}\\mid\\\|\\mathbf\{x\}\\\|\_\{2\}\\leq\\tau\\\}, whereτ=10\\tau=10\. We adopt the average cumulative loss, defined asA​L​\(t,i\)=1t​n​∑τ=1t∑j=1nfτ,j​\(𝐱i​\(τ\)\)AL\(t,i\)=\\frac\{1\}\{tn\}\\sum\_\{\\tau=1\}^\{t\}\\sum\_\{j=1\}^\{n\}f\_\{\\tau,j\}\(\\mathbf\{x\}\_\{i\}\(\\tau\)\), as the performance metric\. Moreover, the original ijcnn1 and a9a datasets consist of 49990 and 32561 examples, respectively\. To ensureT=10000T=10000, we first make a random permutation of these examples, and then allocate 10000 examples to each local learner cyclically\.

The simulation involvesn=9n=9learners connected via a𝒢​\(n,2​n\)\\mathcal\{G\}\(n,2n\)random graph, which is generated by a tool called NetworkX\(Hagberg et al\.,[2008](https://arxiv.org/html/2607.01665#bib.bib12)\)\. Based on this graph topology, the gossip matrixAAsatisfying Assumption[3\.1](https://arxiv.org/html/2607.01665#S3.Thmtheorem1)is constructed using the local\-degree weights\(Xiao and Boyd,[2004](https://arxiv.org/html/2607.01665#bib.bib34)\), whereAi​j=1/max⁡\{di,dj\}A\_\{ij\}=1/\\max\\\{d\_\{i\},d\_\{j\}\\\}for connected nodesiiandjj, andAi​i=1−∑j≠iAi​jA\_\{ii\}=1\-\\sum\_\{j\\neq i\}A\_\{ij\}\. We choose Top\-DOGD\(Yang et al\.,[2026](https://arxiv.org/html/2607.01665#bib.bib36)\)and DC\-DOGD\(Tu et al\.,[2022](https://arxiv.org/html/2607.01665#bib.bib23)\)as the full\-information baselines, and Top\-DOBD\-1\(Yang et al\.,[2026](https://arxiv.org/html/2607.01665#bib.bib36)\)and DC\-DOBD\(Tu et al\.,[2022](https://arxiv.org/html/2607.01665#bib.bib23)\)as the bandit baselines\. In all experiments, we use the Top\-kkcompressor to reduce communication overhead, and each algorithm is run 5 times, and the mean performance with shaded regions indicating the min\-max range is reported\.

To ensure a fair comparison, we tune hyper\-parameters via grid search\. Specifically, the theoretical values of regularization parameterhhand learning rateη\\etaare multiplied by the scaling coefficients, which are selected from\{10−5,10−4,…,105\}\\\{10^\{\-5\},10^\{\-4\},\\dots,10^\{5\}\\\}\. The exploration radiusϵ\\epsilonis chosen from\{0\.1,1,10\}\\\{0\.1,1,10\\\}, while the block sizeLL\(andL1L\_\{1\}for Top\-DOGD and Top\-DOBD\-1\) is tuned over\{10,100,1000\}\\\{10,100,1000\\\}\. The compression ratio is uniformly set toω=0\.1\\omega=0\.1across both datasets\. Other parameters remain at their suggested theoretical values\.

Figure[1](https://arxiv.org/html/2607.01665#S4.F1)plots the average loss against the number of communication rounds and transmitted bits for both datasets\. In both the full\-information and bandit settings, our algorithms achieve a lower average loss compared to their respective baselines\. More significantly, our CD\-FTBL requires only about 2,000 communication rounds, whereas the bandit baselines require at least 10,000 rounds\. To further evaluate the actual communication cost, Figures[1\(b\)](https://arxiv.org/html/2607.01665#S4.F1.sf2)and[1\(d\)](https://arxiv.org/html/2607.01665#S4.F1.sf4)illustrate the average loss with respect to the total transmitted bits\. In these plots, the loss curves for our algorithms visibly shift to the left compared to their baselines\. This indicates that our algorithms require fewer communication bits to reach the same average loss, and thus verifies their communication efficiency again\. Additional experimental results can be found in Appendix[A](https://arxiv.org/html/2607.01665#A1)\.

## 5Conclusion and future work

This paper revisits the problem of D\-OCO with compressed communication\. Unlike previous studies that focus on OGD\-type algorithms, we propose two FTRL\-type algorithms, namely CD\-FTGL and CD\-FTBL, which simplify the existing analysis and even achieve improved results\. Specifically, our CD\-FTGL is developed for the full\-information setting, and can match the existingO~​\(ω−1/2​ρ−1​n​T\)\\tilde\{O\}\(\\omega^\{\-1/2\}\\rho^\{\-1\}n\\sqrt\{T\}\)andO~​\(ω−1​ρ−2​n​log⁡T\)\\tilde\{O\}\(\\omega^\{\-1\}\\rho^\{\-2\}n\\log T\)regret bounds for convex and strongly convex functions, respectively\. Our CD\-FTBL can handle the bandit setting, and significantly improves the regret for convex and strongly convex functions toO​\(n​T3/4\)\{O\}\(nT^\{3/4\}\)andO​\(n​T2/3​\(log⁡T\)1/3\)\{O\}\(nT^\{2/3\}\(\\log T\)^\{1/3\}\), respectively\. Interestingly, it only requires sublinear communication rounds to achieve these results\.

Nonetheless, there are still some open problems\. For example, as previously discussed, CD\-FTGL withω=1\\omega=1can recover the best existing results of full\-information D\-OCO algorithms with the standard gossip\. However, there still exist gaps in terms ofρ\\rhofrom the regret bounds of AD\-FTGL\(Wan et al\.,[2024](https://arxiv.org/html/2607.01665#bib.bib26),[2025](https://arxiv.org/html/2607.01665#bib.bib27)\), which is based on the accelerated gossip strategy\. Thus, it is appealing to investigate whether this accelerated technique can also be combined with compressed communication\. Moreover, we notice that in the full\-information setting, the blocking update mechanism is not necessary for the application of the standard gossip\(Wan et al\.,[2025](https://arxiv.org/html/2607.01665#bib.bib27)\)\. Thus, it is also interesting to study whether the same results achieved by our CD\-FTGL can be obtained withL=1L=1\.

## References

- Aji and Heafield \[2017\]Alham Fikri Aji and Kenneth Heafield\.Sparse communication for distributed gradient descent\.In*Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing*, pages 440–445, 2017\.
- Alistarh et al\. \[2017\]Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic\.QSGD: Communication\-efficient sgd via gradient quantization and encoding\.In*Advances in neural information processing systems 30*, page 1709–1720, 2017\.
- Alistarh et al\. \[2018\]Dan Alistarh, Torsten Hoefler, Mikael Johansson, Nikola Konstantinov, Sarit Khirirat, and Cédric Renggli\.The convergence of sparsified gradient methods\.In*Advances in Neural Information Processing Systems 31*, pages 5977–5987, 2018\.
- Basu et al\. \[2019\]Debraj Basu, Deepesh Data, Can Karakus, and Suhas Diggavi\.Qsparse\-local\-SGD: Distributed SGD with quantization, sparsification and local computations\.In*Advances in Neural Information Processing Systems 32*, pages 14695–14706, 2019\.
- Bernstein et al\. \[2018\]Jeremy Bernstein, Yu\-Xiang Wang, Kamyar Azizzadenesheli, and Animashree Anandkumar\.signSGD: Compressed optimisation for non\-convex problems\.In*International conference on machine learning*, pages 560–569, 2018\.
- Beznosikov et al\. \[2020\]Aleksandr Beznosikov, Samuel Horvath, Peter Richtárik, and Mher Safaryan\.On biased compression for distributed learning\.*J\. Mach\. Learn\. Res\.*, 24:276:1–276:50, 2020\.
- Cao and Başar \[2023\]Xuanyu Cao and Tamer Başar\.Decentralized online convex optimization with compressed communications\.*Automatica*, 156:111186, 2023\.
- Chang and Lin \[2011\]Chih\-Chung Chang and Chih\-Jen Lin\.LIBSVM: A library for support vector machines\.*ACM Transactions on Intelligent Systems and Technology*, 2\(27\):1–27, 2011\.
- Duchi et al\. \[2011\]John Duchi, Elad Hazan, and Yoram Singer\.Adaptive subgradient methods for online learning and stochastic optimization\.*Journal of Machine Learning Research*, 12:2121–2159, 2011\.
- Flaxman et al\. \[2005\]Abraham D\. Flaxman, Adam Tauman Kalai, and H\. Brendan McMahan\.Online convex optimization in the bandit setting: Gradient descent without a gradient\.In*Proceedings of the 16th Annual ACM\-SIAM Symposium on Discrete Algorithms*, pages 385–394, 2005\.
- Garber and Hazan \[2016\]Dan Garber and Elad Hazan\.A linearly convergent conditional gradient algorithm with applications to online and stochastic optimization\.*SIAM Journal on Optimization*, 26\(3\):1493–1528, 2016\.
- Hagberg et al\. \[2008\]Aric Hagberg, Pieter J Swart, and Daniel A Schult\.Exploring network structure, dynamics, and function using networkx\.Technical report, Los Alamos National Laboratory \(LANL\), Los Alamos, NM \(United States\), 2008\.
- Hazan \[2016\]Elad Hazan\.Introduction to online convex optimization\.*Foundations and Trends in Optimization*, 2\(3–4\):157–325, 2016\.
- Hosseini et al\. \[2013\]Saghar Hosseini, Airlie Chapman, and Mehran Mesbahi\.Online distributed optimization via dual averaging\.In*52nd IEEE Conference on Decision and Control*, pages 1484–1489\. IEEE, 2013\.
- Koloskova et al\. \[2019\]Anastasia Koloskova, Sebastian U\. Stich, and Martin Jaggi\.Decentralized stochastic optimization and gossip algorithms with compressed communication\.In*Proceedings of the 36th International Conference on Machine Learning*, pages 3478–3487, 2019\.
- Li et al\. \[2021\]Guangxia Li, Jia Liu, Xiao Lu, Peilin Zhao, Yulong Shen, and Dusit Niyato\.Decentralized online learning with compressed communication for near\-sensor data analytics\.*IEEE Communications Letters*, 25\(9\):2958–2962, 2021\.
- Lin et al\. \[2018\]Yujun Lin, Song Han, Huizi Mao, Yu Wang, and Bill Dally\.Deep Gradient Compression: Reducing the communication bandwidth for distributed training\.In*International Conference on Learning Representations*, 2018\.
- Liu and Morse \[2011\]Ji Liu and A\. Stephen Morse\.Accelerated linear iterations for distributed averaging\.*Annual Reviews in Control*, 35\(2\):160–165, 2011\.
- Seide et al\. \[2014\]Frank Seide, Hao Fu, Jasha Droppo, Gang Li, and Dong Yu\.1\-bit stochastic gradient descent and its application to data\-parallel distributed training of speech dnns\.In*Proceedings of the 15th Annual Conference of the International Speech Communication Association*, pages 1058–1062, 2014\.
- Shalev\-Shwartz and Singer \[2007\]Shai Shalev\-Shwartz and Yoram Singer\.A primal\-dual perspective of online learning algorithm\.*Machine Learning*, 69\(2–3\):115–142, 2007\.
- Stich et al\. \[2018\]Sebastian U Stich, Jean\-Baptiste Cordonnier, and Martin Jaggi\.Sparsified SGD with memory\.In*Advances in Neural Information Processing Systems 31*, pages 4452–4463, 2018\.
- Tang et al\. \[2018\]Hanlin Tang, Shaoduo Gan, Ce Zhang, Tong Zhang, and Ji Liu\.Communication compression for decentralized training\.*Advances in Neural Information Processing Systems 31*, pages 7663–7673, 2018\.
- Tu et al\. \[2022\]Zhipeng Tu, Xi Wang, Yiguang Hong, Lei Wang, Deming Yuan, and Guodong Shi\.Distributed online convex optimization with compressed communication\.*Advances in Neural Information Processing Systems 35*, pages 34492–34504, 2022\.
- Wan et al\. \[2020\]Yuanyu Wan, Wei\-Wei Tu, and Lijun Zhang\.Projection\-free distributed online convex optimization withO​\(T\)\{O\}\(\\sqrt\{T\}\)communication complexity\.In*Proceedings of the 37th International Conference on Machine Learning*, pages 9818–9828, 2020\.
- Wan et al\. \[2022\]Yuanyu Wan, Guanghui Wang, Wei\-Wei Tu, and Lijun Zhang\.Projection\-free distributed online learning with sublinear communication complexity\.*Journal of Machine Learning Research*, 23\(172\):1–53, 2022\.
- Wan et al\. \[2024\]Yuanyu Wan, Tong Wei, Mingli Song, and Lijun Zhang\.Nearly optimal regret for decentralized online convex optimization\.In*Proceedings of the 37th Annual Conference on Learning Theory*, pages 4862–4888, 2024\.
- Wan et al\. \[2025\]Yuanyu Wan, Tong Wei, Bo Xue, Mingli Song, and Lijun Zhang\.Optimal and efficient algorithms for decentralized online convex optimization\.*Journal of Machine Learning Research*, 26\(135\):1–43, 2025\.
- Wang et al\. \[2018\]Hongyi Wang, Scott Sievert, Shengchao Liu, Zachary Charles, Dimitris Papailiopoulos, and Stephen Wright\.Atomo: Communication\-efficient learning via atomic sparsification\.*Advances in neural information processing systems 31*, pages 9872–9883, 2018\.
- Wang et al\. \[2025\]Xiaoyu Wang, Wenhao Yang, Chang Yao, Mingli Song, and Yuanyu Wan\.Revisiting differentially private algorithms for decentralized online learning\.In*Proceedings of the 42nd International Conference on Machine Learning \(ICML\)*, pages 65213–65235, 2025\.
- Wang et al\. \[2023\]Yibo Wang, Yuanyu Wan, Shimao Zhang, and Lijun Zhang\.Distributed projection\-free online learning for smooth and convex losses\.In*Proceedings of the 37th AAAI Conference on Artificial Intelligence*, pages 10226–10234, 2023\.
- Wangni et al\. \[2018\]Jiawei Wangni, Jun Wang, Ji Liu, and Tong Zhang\.Gradient sparsification for communication\-efficient distributed optimization\.In*Advances in Neural Information Processing Systems*, volume 31, 2018\.
- Wen et al\. \[2017\]Wei Wen, Cong Xu, Feng Yan, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li\.Terngrad: Ternary gradients to reduce communication in distributed deep learning\.*Advances in neural information processing systems*, 30, 2017\.
- Xiao \[2009\]Lin Xiao\.Dual averaging method for regularized stochastic learning and online optimization\.In*Advances in Neural Information Processing Systems 22*, pages 2116–2124, 2009\.
- Xiao and Boyd \[2004\]Lin Xiao and Stephen Boyd\.Fast linear iterations for distributed averaging\.*Systems and Control Letters*, 53\(1\):65–78, 2004\.
- Yan et al\. \[2013\]Feng Yan, Shreyas Sundaram, S\.V\.N\. Vishwanathan, and Yuan Qi\.Distributed autonomous online learning: Regrets and intrinsic privacy\-preserving properties\.*IEEE Transactions on Knowledge and Data Engineering*, 25\(11\):2483–2493, 2013\.
- Yang et al\. \[2026\]Sifan Yang, Wenhao Yang, Wei Jiang, and Lijun Zhang\.Distributed online convex optimization with efficient communication: Improved algorithm and lower bounds\.*arXiv preprint arXiv:2601\.04907*, 2026\.
- Zhang et al\. \[2017\]Wenpeng Zhang, Peilin Zhao, Wenwu Zhu, Steven C\. H\. Hoi, and Tong Zhang\.Projection\-free distributed online learning in networks\.In*Proceedings of the 34th International Conference on Machine Learning*, pages 4054–4062, 2017\.
- Zinkevich \[2003\]Martin Zinkevich\.Online convex programming and generalized infinitesimal gradient ascent\.In*Proceedings of the 20th International Conference on Machine Learning*, pages 928–936, 2003\.

![Refer to caption](https://arxiv.org/html/2607.01665v1/x5.png)\(a\)ijcnn1: Loss vs Rounds
![Refer to caption](https://arxiv.org/html/2607.01665v1/x6.png)\(b\)ijcnn1: Loss vs Bits
![Refer to caption](https://arxiv.org/html/2607.01665v1/x7.png)\(c\)a9a: Loss vs Rounds
![Refer to caption](https://arxiv.org/html/2607.01665v1/x8.png)\(d\)a9a: Loss vs Bits

Figure 2:Experimental results on a small random graph \(99nodes and 18 edges\) withω=0\.5\\omega=0\.5\.![Refer to caption](https://arxiv.org/html/2607.01665v1/x9.png)\(a\)ijcnn1: Loss vs Rounds
![Refer to caption](https://arxiv.org/html/2607.01665v1/x10.png)\(b\)ijcnn1: Loss vs Bits
![Refer to caption](https://arxiv.org/html/2607.01665v1/x11.png)\(c\)a9a: Loss vs Rounds
![Refer to caption](https://arxiv.org/html/2607.01665v1/x12.png)\(d\)a9a: Loss vs Bits

Figure 3:Experimental results on a small random graph \(99nodes and 18 edges\) withω=0\.05\\omega=0\.05\.![Refer to caption](https://arxiv.org/html/2607.01665v1/x13.png)\(a\)ijcnn1: Loss vs Rounds
![Refer to caption](https://arxiv.org/html/2607.01665v1/x14.png)\(b\)ijcnn1: Loss vs Bits
![Refer to caption](https://arxiv.org/html/2607.01665v1/x15.png)\(c\)a9a: Loss vs Rounds
![Refer to caption](https://arxiv.org/html/2607.01665v1/x16.png)\(d\)a9a: Loss vs Bits

Figure 4:Experimental results on a larger random graph \(5050nodes and 100 edges\) withω=0\.5\\omega=0\.5\.![Refer to caption](https://arxiv.org/html/2607.01665v1/x17.png)\(a\)ijcnn1: Loss vs Rounds
![Refer to caption](https://arxiv.org/html/2607.01665v1/x18.png)\(b\)ijcnn1: Loss vs Bits
![Refer to caption](https://arxiv.org/html/2607.01665v1/x19.png)\(c\)a9a: Loss vs Rounds
![Refer to caption](https://arxiv.org/html/2607.01665v1/x20.png)\(d\)a9a: Loss vs Bits

Figure 5:Experimental results on a larger random graph \(5050nodes and 100 edges\) withω=0\.1\\omega=0\.1\.![Refer to caption](https://arxiv.org/html/2607.01665v1/x21.png)\(a\)ijcnn1: Loss vs Rounds
![Refer to caption](https://arxiv.org/html/2607.01665v1/x22.png)\(b\)ijcnn1: Loss vs Bits
![Refer to caption](https://arxiv.org/html/2607.01665v1/x23.png)\(c\)a9a: Loss vs Rounds
![Refer to caption](https://arxiv.org/html/2607.01665v1/x24.png)\(d\)a9a: Loss vs Bits

Figure 6:Experimental results on a larger random graph \(5050nodes and 100 edges\) withω=0\.05\\omega=0\.05\.![Refer to caption](https://arxiv.org/html/2607.01665v1/x25.png)\(a\)ijcnn1: Loss vs Rounds
![Refer to caption](https://arxiv.org/html/2607.01665v1/x26.png)\(b\)ijcnn1: Loss vs Bits
![Refer to caption](https://arxiv.org/html/2607.01665v1/x27.png)\(c\)a9a: Loss vs Rounds
![Refer to caption](https://arxiv.org/html/2607.01665v1/x28.png)\(d\)a9a: Loss vs Bits

Figure 7:Experimental results of CD\-FTBL with varying communication roundsKKon a small random graph \(9 nodes and 18 edges\) withω=0\.5\\omega=0\.5and fixed block sizeL=100L=100\.![Refer to caption](https://arxiv.org/html/2607.01665v1/x29.png)\(a\)ijcnn1: Loss vs Rounds
![Refer to caption](https://arxiv.org/html/2607.01665v1/x30.png)\(b\)ijcnn1: Loss vs Bits
![Refer to caption](https://arxiv.org/html/2607.01665v1/x31.png)\(c\)a9a: Loss vs Rounds
![Refer to caption](https://arxiv.org/html/2607.01665v1/x32.png)\(d\)a9a: Loss vs Bits

Figure 8:Experimental results of CD\-FTBL with varying communication roundsKKon a small random graph \(9 nodes and 18 edges\) withω=0\.1\\omega=0\.1and fixed block sizeL=100L=100\.![Refer to caption](https://arxiv.org/html/2607.01665v1/x33.png)\(a\)ijcnn1: Loss vs Rounds
![Refer to caption](https://arxiv.org/html/2607.01665v1/x34.png)\(b\)ijcnn1: Loss vs Bits
![Refer to caption](https://arxiv.org/html/2607.01665v1/x35.png)\(c\)a9a: Loss vs Rounds
![Refer to caption](https://arxiv.org/html/2607.01665v1/x36.png)\(d\)a9a: Loss vs Bits

Figure 9:Experimental results of CD\-FTBL with varying communication roundsKKon a small random graph \(9 nodes and 18 edges\) withω=0\.05\\omega=0\.05and fixed block sizeL=100L=100\.## Appendix AAdditional experimental results

In this section, we provide additional experimental results with different network sizes, varying compression ratios, and the sensitivity of the communication frequency parameter\.

First, Figures[2](https://arxiv.org/html/2607.01665#A0.F2)and[3](https://arxiv.org/html/2607.01665#A0.F3)present the convergence behavior on the small random graph \(99nodes and1818edges\) under compression ratios ofω=0\.5\\omega=0\.5andω=0\.05\\omega=0\.05, respectively\. To further investigate the scalability of our methods in larger networks, we conduct additional experiments on a larger random graph consisting of5050nodes and100100edges\. The corresponding results forω∈\{0\.5,0\.1,0\.05\}\\omega\\in\\\{0\.5,0\.1,0\.05\\\}are illustrated in Figures[4](https://arxiv.org/html/2607.01665#A0.F4),[5](https://arxiv.org/html/2607.01665#A0.F5)and[6](https://arxiv.org/html/2607.01665#A0.F6)\. Consistent with the main findings, these additional results further validate the superior efficacy and communication efficiency of our proposed algorithms across both full\-information and bandit settings, regardless of network scales and compression levels\.

Furthermore, to empirically investigate the trade\-off between consensus accuracy and communication efficiency, we conduct a sensitivity analysis on the communication frequencyKKfor our CD\-FTBL algorithm\. Note that in the preceding experiments, the default number of communication rounds per block is set toK=⌈L/5⌉K=\\lceil L/5\\rceil\. Specifically, we fix the block size atL=100L=100and vary the number of communication rounds per blockKK\. The results under compression ratios ofω∈\{0\.5,0\.1,0\.05\}\\omega\\in\\\{0\.5,0\.1,0\.05\\\}are presented in Figures[7](https://arxiv.org/html/2607.01665#A0.F7),[8](https://arxiv.org/html/2607.01665#A0.F8), and[9](https://arxiv.org/html/2607.01665#A0.F9)\. As depicted in the figures, configurations with a smallerKKexhibit a significantly faster decay in average loss with respect to both communication rounds and transmitted bits\. However, the final loss achieved by smallerKKvalues is slightly higher\. This phenomenon highlights a clear trade\-off: decreasingKKaggressively reduces communication overhead while slightly compromising the final accuracy\. Nevertheless, this observation supports our theoretical analysis that a reducedKKis sufficient to control the consensus error within a reasonable tolerance\.

## Appendix BProof of Theorem[3\.8](https://arxiv.org/html/2607.01665#S3.Thmtheorem8)

Recall that𝐝¯​\(z\)=\(1/n\)​∑i=1n𝐝i​\(z\)\\bar\{\\mathbf\{d\}\}\(z\)=\(1/n\)\\sum\_\{i=1\}^\{n\}\\mathbf\{\\mathbf\{d\}\}\_\{i\}\(z\)\. Forz∈\[T/L\]z\\in\[T/L\], we define the virtual leader sequence as

𝐱¯​\(z\)=argmin𝐱∈𝒦⟨𝐱,𝐳¯​\(z\)⟩\+\(z−1\)​L​α\+2​h2​‖𝐱‖22,\\bar\{\\mathbf\{x\}\}\(z\)=\\operatorname\*\{argmin\}\_\{\\mathbf\{x\}\\in\\mathcal\{K\}\}\\left\\langle\\mathbf\{x\},\\bar\{\\mathbf\{z\}\}\(z\)\\right\\rangle\+\\frac\{\(z\-1\)L\\alpha\+2h\}\{2\}\\\|\\mathbf\{x\}\\\|\_\{2\}^\{2\},where𝐳¯​\(z\)=∑τ=1z−1𝐝¯​\(τ\)\\bar\{\\mathbf\{z\}\}\(z\)=\\sum\_\{\\tau=1\}^\{z\-1\}\\bar\{\\mathbf\{d\}\}\(\\tau\)\. Following the analysis ofWan et al\. \[[2025](https://arxiv.org/html/2607.01665#bib.bib27)\], the total regret can be decomposed into the regret of the virtual leader and a deviation term\. To be precise, forz∈\[T/L\]z\\in\[T/L\], letℓz​\(𝐱\)=⟨𝐝¯​\(z\),𝐱⟩\+\(L​α/2\)​‖𝐱‖22\\ell\_\{z\}\(\\mathbf\{x\}\)=\\langle\\bar\{\\mathbf\{d\}\}\(z\),\\mathbf\{x\}\\rangle\+\(L\\alpha/2\)\\\|\\mathbf\{x\}\\\|\_\{2\}^\{2\}and𝐱∗∈min𝐱∈𝒦​∑t=1Tft​\(𝐱\)\\mathbf\{x\}^\{\\ast\}\\in\\min\_\{\\mathbf\{x\}\\in\\mathcal\{K\}\}\\sum\_\{t=1\}^\{T\}f\_\{t\}\(\\mathbf\{x\}\)\. According to \(41\) and \(42\) in the proof of Theorem 1 ofWan et al\. \[[2025](https://arxiv.org/html/2607.01665#bib.bib27)\], we have

RT,i≤n​∑z=1T/L\(ℓz​\(𝐱¯​\(z\+1\)\)−ℓz​\(𝐱∗\)\)\+n​G​∑z=1T/L\(L​Δi​\(z\)\+2​∑j=1nΔj​\(z\)\),\\begin\{split\}R\_\{T,i\}\\leq&n\\sum\_\{z=1\}^\{T/L\}\\left\(\\ell\_\{z\}\(\\bar\{\\mathbf\{x\}\}\(z\+1\)\)\-\\ell\_\{z\}\(\\mathbf\{x\}^\{\\ast\}\)\\right\)\+nG\\sum\_\{z=1\}^\{T/L\}\\left\(L\\Delta\_\{i\}\(z\)\+2\\sum\_\{j=1\}^\{n\}\\Delta\_\{j\}\(z\)\\right\),\\end\{split\}\(7\)whereΔi​\(z\)=‖𝐱i​\(z\)−𝐱¯​\(z\+1\)‖2\\Delta\_\{i\}\(z\)=\\\|\\mathbf\{x\}\_\{i\}\(z\)\-\\bar\{\\mathbf\{x\}\}\(z\+1\)\\\|\_\{2\}\.

To analyze the regret of the virtual leader, we introduce a classical lemma\.

###### Lemma B\.1\(Lemma 6\.6 inGarber and Hazan \[[2016](https://arxiv.org/html/2607.01665#bib.bib11)\]\)\.

Let\{ℓt​\(𝐱\)\}t=1T\\\{\\ell\_\{t\}\(\\mathbf\{x\}\)\\\}\_\{t=1\}^\{T\}be a sequence of convex functions and𝐱t∗∈argmin𝐱∈𝒦​∑τ=1tℓτ​\(𝐱\)\\mathbf\{x\}\_\{t\}^\{\*\}\\in\\operatorname\*\{argmin\}\_\{\\mathbf\{x\}\\in\\mathcal\{K\}\}\\sum\_\{\\tau=1\}^\{t\}\\ell\_\{\\tau\}\(\\mathbf\{x\}\)for anyt∈\[T\]t\\in\[T\]\. Then, it holds that∑t=1Tℓt​\(𝐱t∗\)−min𝐱∈𝒦​∑t=1Tℓt​\(𝐱\)≤0\.\\sum\_\{t=1\}^\{T\}\\ell\_\{t\}\(\\mathbf\{x\}\_\{t\}^\{\*\}\)\-\\min\_\{\\mathbf\{x\}\\in\\mathcal\{K\}\}\\sum\_\{t=1\}^\{T\}\\ell\_\{t\}\(\\mathbf\{x\}\)\\leq 0\.

By further definingℓ0​\(𝐱\)=h​‖𝐱‖22\\ell\_\{0\}\(\\mathbf\{x\}\)=h\\\|\\mathbf\{x\}\\\|\_\{2\}^\{2\}and then applying Lemma[B\.1](https://arxiv.org/html/2607.01665#A2.Thmtheorem1), it is easy to verify that the first term in the right side of \([7](https://arxiv.org/html/2607.01665#A2.E7)\) can be bounded byn​h​R2nhR^\{2\}\. By combining this result and taking expectation over two sides of \([7](https://arxiv.org/html/2607.01665#A2.E7)\), we have

𝔼​\[RT,i\]≤\\displaystyle\\mathbb\{E\}\[R\_\{T,i\}\]\\leqn​G​∑z=1T/L\(L​𝔼​\[Δi​\(z\)\]\+2​∑j=1n𝔼​\[Δj​\(z\)\]\)\+n​h​R2\.\\displaystyle nG\\sum\_\{z=1\}^\{T/L\}\\left\(L\\mathbb\{E\}\[\\Delta\_\{i\}\(z\)\]\+2\\sum\_\{j=1\}^\{n\}\\mathbb\{E\}\[\\Delta\_\{j\}\(z\)\]\\right\)\+nhR^\{2\}\.\(8\)Then, we proceed to analyze𝔼​\[Δi​\(z\)\]\\mathbb\{E\}\[\\Delta\_\{i\}\(z\)\], which now is affected by compressed communication\. However, similar to analysis ofWan et al\. \[[2025](https://arxiv.org/html/2607.01665#bib.bib27)\], for anyz≥2z\\geq 2, we still split𝔼​\[Δi​\(z\)\]\\mathbb\{E\}\[\\Delta\_\{i\}\(z\)\]into a consensus error term and a leader stability term, i\.e\.,

𝔼​\[Δi​\(z\)\]≤\\displaystyle\\mathbb\{E\}\[\\Delta\_\{i\}\(z\)\]\\leq𝔼​\[‖𝐱i​\(z\)−𝐱¯​\(z−1\)‖2\]\+𝔼​\[‖𝐱¯​\(z−1\)−𝐱¯​\(z\+1\)‖2\]\.\\displaystyle\\mathbb\{E\}\\left\[\\\|\\mathbf\{x\}\_\{i\}\(z\)\-\\bar\{\\mathbf\{x\}\}\(z\-1\)\\\|\_\{2\}\\right\]\+\\mathbb\{E\}\[\\\|\\bar\{\\mathbf\{x\}\}\(z\-1\)\-\\bar\{\\mathbf\{x\}\}\(z\+1\)\\\|\_\{2\}\]\.\(9\)To bound the consensus error in \([9](https://arxiv.org/html/2607.01665#A2.E9)\), we introduce two useful lemmas, where the latter one is derived by using Lemma[3\.7](https://arxiv.org/html/2607.01665#S3.Thmtheorem7)\.

###### Lemma B\.2\(Lemma 5 inDuchi et al\. \[[2011](https://arxiv.org/html/2607.01665#bib.bib9)\]\)\.

LetΠ𝒦​\(𝐮,η\)=argmin𝐱∈𝒦⟨𝐮,𝐱⟩\+1η​‖𝐱‖22\\Pi\_\{\\mathcal\{K\}\}\(\\mathbf\{u\},\\eta\)=\\operatorname\*\{argmin\}\_\{\\mathbf\{x\}\\in\\mathcal\{K\}\}\\left\\langle\\mathbf\{u\},\\mathbf\{x\}\\right\\rangle\+\\frac\{1\}\{\\eta\}\\\|\\mathbf\{x\}\\\|\_\{2\}^\{2\}\. For any𝐮,𝐯∈ℝd\\mathbf\{u\},\\mathbf\{v\}\\in\\mathbb\{R\}^\{d\}, we have‖Π𝒦​\(𝐮,η\)−Π𝒦​\(𝐯,η\)‖2≤η2​‖𝐮−𝐯‖2\\\|\\Pi\_\{\\mathcal\{K\}\}\(\\mathbf\{u\},\\eta\)\-\\Pi\_\{\\mathcal\{K\}\}\(\\mathbf\{v\},\\eta\)\\\|\_\{2\}\\leq\\frac\{\\eta\}\{2\}\\\|\\mathbf\{u\}\-\\mathbf\{v\}\\\|\_\{2\}\.

###### Lemma B\.3\.

Suppose Assumption[3\.1](https://arxiv.org/html/2607.01665#S3.Thmtheorem1),[3\.2](https://arxiv.org/html/2607.01665#S3.Thmtheorem2)and[3\.4](https://arxiv.org/html/2607.01665#S3.Thmtheorem4)hold\. Consider Algorithm[2](https://arxiv.org/html/2607.01665#alg2)and[3](https://arxiv.org/html/2607.01665#alg3)with the consensus step sizeγ\\gammaand the communication roundsKKin Theorem[3\.8](https://arxiv.org/html/2607.01665#S3.Thmtheorem8)and[3\.12](https://arxiv.org/html/2607.01665#S3.Thmtheorem12), then for allz∈\[T/L\]z\\in\[T/L\], it holds that

𝔼​\[‖𝐳i​\(z\)−𝐳¯​\(z\)‖2\]<2​𝔼​\[‖D​\(z−1\)‖F\]n,\\displaystyle\\mathbb\{E\}\\left\[\\left\\\|\\mathbf\{z\}\_\{i\}\(z\)\-\\bar\{\\mathbf\{z\}\}\(z\)\\right\\\|\_\{2\}\\right\]<\\frac\{2\\mathbb\{E\}\[\\left\\\|D\(z\-1\)\\right\\\|\_\{F\}\]\}\{\\sqrt\{n\}\},whereD​\(z\)=\[𝐝1​\(z\),…,𝐝n​\(z\)\]∈ℝd×nD\(z\)=\[\\mathbf\{d\}\_\{1\}\(z\),\\dots,\\mathbf\{d\}\_\{n\}\(z\)\]\\in\\mathbb\{R\}^\{d\\times n\}for anyz≥1z\\geq 1andD​\(0\)=𝟎d×nD\(0\)=\\mathbf\{0\}^\{d\\times n\}\.

Under Assumptions[3\.3](https://arxiv.org/html/2607.01665#S3.Thmtheorem3)and[3\.4](https://arxiv.org/html/2607.01665#S3.Thmtheorem4), for anyz∈\[T/L\]z\\in\[T/L\], we have

‖D​\(z\)‖F=∑i=1n‖𝐝i​\(z\)‖22=∑i=1n‖∑t∈𝒯z\(∇ft,i​\(𝐱i​\(t\)\)−α​𝐱i​\(t\)\)‖22≤n​L​\(G\+α​R\)\.\\displaystyle\\\|D\(z\)\\\|\_\{F\}=\\sqrt\{\\sum\_\{i=1\}^\{n\}\\\|\\mathbf\{d\}\_\{i\}\(z\)\\\|\_\{2\}^\{2\}\}=\\sqrt\{\\sum\_\{i=1\}^\{n\}\\left\\\|\\sum\_\{t\\in\\mathcal\{T\}\_\{z\}\}\\left\(\\nabla f\_\{t,i\}\(\\mathbf\{x\}\_\{i\}\(t\)\)\-\\alpha\\mathbf\{x\}\_\{i\}\(t\)\\right\)\\right\\\|\_\{2\}^\{2\}\}\\leq\\sqrt\{n\}L\(G\+\\alpha R\)\.\(10\)By combining Lemma[B\.3](https://arxiv.org/html/2607.01665#A2.Thmtheorem3)with \([10](https://arxiv.org/html/2607.01665#A2.E10)\), we have

𝔼​\[‖𝐳i​\(z\)−𝐳¯​\(z\)‖2\]<2​L​\(G\+α​R\)\\mathbb\{E\}\\left\[\\left\\\|\\mathbf\{z\}\_\{i\}\(z\)\-\\bar\{\\mathbf\{z\}\}\(z\)\\right\\\|\_\{2\}\\right\]<2L\\left\(G\+\\alpha R\\right\)for anyz∈\[T/L\]z\\in\[T/L\]\. Then, by applying Lemma[B\.2](https://arxiv.org/html/2607.01665#A2.Thmtheorem2)and the above inequality, for anyz≥2z\\geq 2, we have

𝔼​\[‖𝐱i​\(z\)−𝐱¯​\(z−1\)‖2\]≤\\displaystyle\\mathbb\{E\}\\left\[\\left\\\|\\mathbf\{x\}\_\{i\}\(z\)\-\\bar\{\\mathbf\{x\}\}\(z\-1\)\\right\\\|\_\{2\}\\right\]\\leq𝔼​\[‖𝐳i​\(z−1\)−𝐳¯​\(z−1\)‖2\]\(z−2\)​L​α\+2​h≤2​L​\(G\+α​R\)\(z−2\)​L​α\+2​h\.\\displaystyle\\frac\{\\mathbb\{E\}\\left\[\\left\\\|\\mathbf\{z\}\_\{i\}\(z\-1\)\-\\bar\{\\mathbf\{z\}\}\(z\-1\)\\right\\\|\_\{2\}\\right\]\}\{\(z\-2\)L\\alpha\+2h\}\\leq\\frac\{2L\(G\+\\alpha R\)\}\{\(z\-2\)L\\alpha\+2h\}\.\(11\)
For the leader stability in \([9](https://arxiv.org/html/2607.01665#A2.E9)\), according to \(38\) in the proof of Theorem 1 inWan et al\. \[[2025](https://arxiv.org/html/2607.01665#bib.bib27)\], for anyz≥2z\\geq 2, we have

‖𝐱¯​\(z−1\)−𝐱¯​\(z\+1\)‖2≤4​L​\(G\+2​α​R\)z​L​α\+2​h\.\\\|\\bar\{\\mathbf\{x\}\}\(z\-1\)\-\\bar\{\\mathbf\{x\}\}\(z\+1\)\\\|\_\{2\}\\leq\\frac\{4L\(G\+2\\alpha R\)\}\{zL\\alpha\+2h\}\.\(12\)
Finally, note thatΔi​\(1\)=‖𝐱i​\(1\)−𝐱¯​\(2\)‖2≤\(2​L​\(G\+2​α​R\)\)/\(L​α\+2​h\)\\Delta\_\{i\}\(1\)=\\\|\\mathbf\{x\}\_\{i\}\(1\)\-\\bar\{\\mathbf\{x\}\}\(2\)\\\|\_\{2\}\\leq\(2L\(G\+2\\alpha R\)\)/\(L\\alpha\+2h\), which is also due to \(38\) in the proof of Theorem 1 inWan et al\. \[[2025](https://arxiv.org/html/2607.01665#bib.bib27)\]\. Therefore, this proof can be completed by substituting \([11](https://arxiv.org/html/2607.01665#A2.E11)\) and \([12](https://arxiv.org/html/2607.01665#A2.E12)\) into \([9](https://arxiv.org/html/2607.01665#A2.E9)\), and combining with \([8](https://arxiv.org/html/2607.01665#A2.E8)\) and the upper bound ofΔi​\(1\)\\Delta\_\{i\}\(1\)\.

## Appendix CProof of Theorem[3\.12](https://arxiv.org/html/2607.01665#S3.Thmtheorem12)

Forz∈\[T/L\]z\\in\[T/L\], we define the virtual leader sequence as

𝐱¯​\(z\+1\)=argmin𝐱∈𝒦ϵ⟨𝐱,𝐳¯​\(z\)⟩\+\(z−1\)​L​α\+2​h2​‖𝐱‖22\\displaystyle\\bar\{\\mathbf\{x\}\}\(z\+1\)=\\operatorname\*\{argmin\}\_\{\\mathbf\{x\}\\in\\mathcal\{K\}\_\{\\epsilon\}\}\\left\\langle\\mathbf\{x\},\\bar\{\\mathbf\{z\}\}\(z\)\\right\\rangle\+\\frac\{\(z\-1\)L\\alpha\+2h\}\{2\}\\\|\\mathbf\{x\}\\\|\_\{2\}^\{2\}where𝐳¯​\(z\)=∑τ=1z−1𝐝¯​\(τ\)\\bar\{\\mathbf\{z\}\}\(z\)=\\sum\_\{\\tau=1\}^\{z\-1\}\\bar\{\\mathbf\{d\}\}\(\\tau\), but𝐝¯​\(z\)\\bar\{\\mathbf\{d\}\}\(z\)is defined as

𝐝¯​\(z\)\\displaystyle\\bar\{\\mathbf\{d\}\}\(z\)=1n​∑i=1n𝐝i​\(z\)=1n​∑i=1n∑t∈𝒯z\(𝐠i​\(t\)−α​𝐱i​\(z\)\)\.\\displaystyle=\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}\\mathbf\{d\}\_\{i\}\(z\)=\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}\\sum\_\{t\\in\\mathcal\{T\}\_\{z\}\}\\left\(\\mathbf\{g\}\_\{i\}\(t\)\-\\alpha\\mathbf\{x\}\_\{i\}\(z\)\\right\)\.Moreover, let𝐱~∗=\(1−ϵ/r\)​𝐱∗∈𝒦ϵ\\tilde\{\\mathbf\{x\}\}^\{\*\}=\(1\-\\epsilon/r\)\\mathbf\{x\}^\{\*\}\\in\\mathcal\{K\}\_\{\\epsilon\}\. Following the proof of Theorems 5 and 6 inWan et al\. \[[2022](https://arxiv.org/html/2607.01665#bib.bib25)\], the total regret can be bounded as

𝔼​\[RT,i\]≤𝔼​\[∑z=1T/L∑t∈𝒯z∑j=1n\(f^t,j,ϵ​\(𝐱i​\(z\)\)−f^t,j,ϵ​\(𝐱~∗\)\)\]⏟:=R^T,i\+3​ϵ​n​G​T\+ϵ​n​G​R​Tr,\\mathbb\{E\}\[R\_\{T,i\}\]\\leq\\underbrace\{\\mathbb\{E\}\\left\[\\sum\_\{z=1\}^\{T/L\}\\sum\_\{t\\in\\mathcal\{T\}\_\{z\}\}\\sum\_\{j=1\}^\{n\}\\left\(\\hat\{f\}\_\{t,j,\\epsilon\}\(\\mathbf\{x\}\_\{i\}\(z\)\)\-\\hat\{f\}\_\{t,j,\\epsilon\}\(\\tilde\{\\mathbf\{x\}\}^\{\*\}\)\\right\)\\right\]\}\_\{:=\\hat\{R\}\_\{T,i\}\}\+3\\epsilon nGT\+\\frac\{\\epsilon nGRT\}\{r\},\(13\)wheref^t,j,ϵ​\(⋅\)\\hat\{f\}\_\{t,j,\\epsilon\}\(\\cdot\)is theϵ\\epsilon\-smoothed version offt,j​\(⋅\)f\_\{t,j\}\(\\cdot\)\.

Note that according to Lemma 2\.6 inHazan \[[2016](https://arxiv.org/html/2607.01665#bib.bib13)\], over the shrunk set𝒦ϵ\\mathcal\{K\}\_\{\\epsilon\}, theϵ\\epsilon\-smoothed functionf^t,j,ϵ​\(⋅\)\\hat\{f\}\_\{t,j,\\epsilon\}\(\\cdot\)shares the same strong convexity and Lipschitz property asft,j​\(⋅\)f\_\{t,j\}\(\\cdot\)\. Therefore, following \([7](https://arxiv.org/html/2607.01665#A2.E7)\) and using Lemma[3\.11](https://arxiv.org/html/2607.01665#S3.Thmtheorem11), it is not hard to verify that

R^T,i≤n​∑z=1T/L𝔼​\[ℓz​\(𝐱¯​\(z\+1\)\)−ℓz​\(𝐱~∗\)\]⏟:=R¯z\+n​G​∑z=1T/L\(L​𝔼​\[Δi​\(z\)\]\+2​∑j=1n𝔼​\[Δj​\(z\)\]\),\\hat\{R\}\_\{T,i\}\\leq\\underbrace\{n\\sum\_\{z=1\}^\{T/L\}\\mathbb\{E\}\\left\[\\ell\_\{z\}\(\\bar\{\\mathbf\{x\}\}\(z\+1\)\)\-\\ell\_\{z\}\(\\tilde\{\\mathbf\{x\}\}^\{\*\}\)\\right\]\}\_\{:=\\bar\{R\}\_\{z\}\}\+nG\\sum\_\{z=1\}^\{T/L\}\\left\(L\\mathbb\{E\}\[\\Delta\_\{i\}\(z\)\]\+2\\sum\_\{j=1\}^\{n\}\\mathbb\{E\}\[\\Delta\_\{j\}\(z\)\]\\right\),\(14\)whereℓz​\(𝐱\)=⟨𝐱,𝐝¯​\(z\)⟩\+\(L​α/2\)​‖𝐱‖22\\ell\_\{z\}\(\\mathbf\{x\}\)=\\langle\\mathbf\{x\},\\bar\{\\mathbf\{d\}\}\(z\)\\rangle\+\(L\\alpha/2\)\\\|\\mathbf\{x\}\\\|\_\{2\}^\{2\}andΔi​\(z\)=‖𝐱i​\(z\)−𝐱¯​\(z\+1\)‖2\\Delta\_\{i\}\(z\)=\\\|\\mathbf\{x\}\_\{i\}\(z\)\-\\bar\{\\mathbf\{x\}\}\(z\+1\)\\\|\_\{2\}\.

Unlike the full\-information setting, we need to introduce a new lemma to bound𝔼​\[‖𝐝¯​\(z\)‖22\]\\mathbb\{E\}\[\\\|\\bar\{\\mathbf\{d\}\}\(z\)\\\|\_\{2\}^\{2\}\]\.

###### Lemma C\.1\(Derived from Lemma 6 inWan et al\. \[[2022](https://arxiv.org/html/2607.01665#bib.bib25)\]\)\.

Under Assumptions[3\.3](https://arxiv.org/html/2607.01665#S3.Thmtheorem3),[3\.4](https://arxiv.org/html/2607.01665#S3.Thmtheorem4), and[3\.6](https://arxiv.org/html/2607.01665#S3.Thmtheorem6), for anyi∈\[n\]i\\in\[n\]andz∈\[T/L\]z\\in\[T/L\], let𝐝¯​\(z\)=1n​∑i=1n𝐝i​\(z\)\\bar\{\\mathbf\{d\}\}\(z\)=\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}\\mathbf\{d\}\_\{i\}\(z\), Algorithm[3](https://arxiv.org/html/2607.01665#alg3)ensures

𝔼​\[‖𝐝i​\(z\)‖22\]≤2​L​d2​M2ϵ2\+2​L2​G2\+2​α2​L2​R2\.\\mathbb\{E\}\[\\\|\\mathbf\{d\}\_\{i\}\(z\)\\\|\_\{2\}^\{2\}\]\\leq 2L\\frac\{d^\{2\}M^\{2\}\}\{\\epsilon^\{2\}\}\+2L^\{2\}G^\{2\}\+2\\alpha^\{2\}L^\{2\}R^\{2\}\.

For brevity, let

B1:=2​L​d​Mϵ\+2​L​G\+3​α​L​R,B2:=2​L​d2​M2ϵ2\+2​L2​G2\+2​α2​L2​R2\.\\displaystyle B\_\{1\}:=2\\frac\{\\sqrt\{L\}dM\}\{\\epsilon\}\+2LG\+3\\alpha LR,\\qquad B\_\{2\}:=\\sqrt\{2L\\frac\{d^\{2\}M^\{2\}\}\{\\epsilon^\{2\}\}\+2L^\{2\}G^\{2\}\+2\\alpha^\{2\}L^\{2\}R^\{2\}\}\.Due to Lemma[C\.1](https://arxiv.org/html/2607.01665#A3.Thmtheorem1)and the definition of𝐝¯​\(z\)\\bar\{\\mathbf\{d\}\}\(z\), we have

𝔼​\[‖𝐝¯​\(z\)‖22\]≤1n​∑i=1n𝔼​\[‖𝐝i​\(z\)‖22\]≤B2\.\\displaystyle\\mathbb\{E\}\\left\[\\\|\\bar\{\\mathbf\{d\}\}\(z\)\\\|\_\{2\}^\{2\}\\right\]\\leq\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}\\mathbb\{E\}\[\\\|\\mathbf\{d\}\_\{i\}\(z\)\\\|\_\{2\}^\{2\}\]\\leq B\_\{2\}\.By combining the above inequality with Jensen’s inequality, we have

𝔼​\[‖∇ℓz​\(𝐱\)‖2\]=𝔼​\[‖𝐝¯​\(z\)\+L​α​𝐱‖2\]≤𝔼​\[‖𝐝¯​\(z\)‖22\]\+L​α​R≤B1\.\\mathbb\{E\}\[\\\|\\nabla\\ell\_\{z\}\(\\mathbf\{x\}\)\\\|\_\{2\}\]=\\mathbb\{E\}\[\\left\\\|\\bar\{\\mathbf\{d\}\}\(z\)\+L\\alpha\\mathbf\{x\}\\right\\\|\_\{2\}\]\\leq\\sqrt\{\\mathbb\{E\}\\left\[\\\|\\bar\{\\mathbf\{d\}\}\(z\)\\\|\_\{2\}^\{2\}\\right\]\}\+L\\alpha R\\leq B\_\{1\}\.Then, to bound the first term in the right side of \([14](https://arxiv.org/html/2607.01665#A3.E14)\), we notice that

R¯z≤n​∑z=1T/L𝔼​\[ℓz​\(𝐱¯​\(z\+2\)\)−ℓz​\(𝐱~∗\)\]\+n​B1​∑z=1T/L𝔼​\[‖𝐱¯​\(z\+2\)−𝐱¯​\(z\+1\)‖2\]≤n​h​R2\+n​B1​∑z=1T/L𝔼​\[‖𝐱¯​\(z\+2\)−𝐱¯​\(z\+1\)‖2\],\\begin\{split\}\\bar\{R\}\_\{z\}\\leq&n\\sum\_\{z=1\}^\{T/L\}\\mathbb\{E\}\[\\ell\_\{z\}\(\\bar\{\\mathbf\{x\}\}\(z\+2\)\)\-\\ell\_\{z\}\(\\tilde\{\\mathbf\{x\}\}^\{\*\}\)\]\+nB\_\{1\}\\sum\_\{z=1\}^\{T/L\}\\mathbb\{E\}\[\\\|\\bar\{\\mathbf\{x\}\}\(z\+2\)\-\\bar\{\\mathbf\{x\}\}\(z\+1\)\\\|\_\{2\}\]\\\\ \\leq&nhR^\{2\}\+nB\_\{1\}\\sum\_\{z=1\}^\{T/L\}\\mathbb\{E\}\[\\\|\\bar\{\\mathbf\{x\}\}\(z\+2\)\-\\bar\{\\mathbf\{x\}\}\(z\+1\)\\\|\_\{2\}\],\\end\{split\}\(15\)where the second inequality is derived by using Lemma[B\.1](https://arxiv.org/html/2607.01665#A2.Thmtheorem1)\.

Following \(38\) in the proof of Theorem 1 inWan et al\. \[[2025](https://arxiv.org/html/2607.01665#bib.bib27)\], for anyz≥1z\\geq 1, we have

𝔼​\[‖𝐱¯​\(z\+1\)−𝐱¯​\(z\+2\)‖2\]≤2​B1z​L​α\+2​h\.\\mathbb\{E\}\\left\[\\left\\\|\\bar\{\\mathbf\{x\}\}\(z\+1\)\-\\bar\{\\mathbf\{x\}\}\(z\+2\)\\right\\\|\_\{2\}\\right\]\\leq\\frac\{2B\_\{1\}\}\{zL\\alpha\+2h\}\.\(16\)
Moreover, similar to the full\-information setting, for anyz≥2z\\geq 2, we split𝔼​\[Δi​\(z\)\]\\mathbb\{E\}\[\\Delta\_\{i\}\(z\)\]into a consensus error term and a leader stability term as follows

𝔼​\[Δi​\(z\)\]≤𝔼​\[‖𝐱i​\(z\)−𝐱¯​\(z\)‖2\]\+‖𝐱¯​\(z\)−𝐱¯​\(z\+1\)‖2\.\\displaystyle\\mathbb\{E\}\[\\Delta\_\{i\}\(z\)\]\\leq\\mathbb\{E\}\\left\[\\left\\\|\\mathbf\{x\}\_\{i\}\(z\)\-\\bar\{\\mathbf\{x\}\}\(z\)\\right\\\|\_\{2\}\\right\]\+\\left\\\|\\bar\{\\mathbf\{x\}\}\(z\)\-\\bar\{\\mathbf\{x\}\}\(z\+1\)\\right\\\|\_\{2\}\.\(17\)By applying Lemmas[B\.2](https://arxiv.org/html/2607.01665#A2.Thmtheorem2)and[B\.3](https://arxiv.org/html/2607.01665#A2.Thmtheorem3), for anyz≥2z\\geq 2, we have

𝔼​\[‖𝐱i​\(z\)−𝐱¯​\(z\)‖2\]≤2​B2\(z−2\)​L​α\+2​h\.\\displaystyle\\mathbb\{E\}\\left\[\\left\\\|\\mathbf\{x\}\_\{i\}\(z\)\-\\bar\{\\mathbf\{x\}\}\(z\)\\right\\\|\_\{2\}\\right\]\\leq\\frac\{2B\_\{2\}\}\{\(z\-2\)L\\alpha\+2h\}\.\(18\)By substituting \([18](https://arxiv.org/html/2607.01665#A3.E18)\) and \([16](https://arxiv.org/html/2607.01665#A3.E16)\) into \([17](https://arxiv.org/html/2607.01665#A3.E17)\), for anyz≥2z\\geq 2, we have

𝔼​\[Δi​\(z\)\]≤2​B2\(z−2\)​L​α\+2​h\+2​B1\(z−1\)​L​α\+2​h\.\\displaystyle\\mathbb\{E\}\[\\Delta\_\{i\}\(z\)\]\\leq\\frac\{2B\_\{2\}\}\{\(z\-2\)L\\alpha\+2h\}\+\\frac\{2B\_\{1\}\}\{\(z\-1\)L\\alpha\+2h\}\.\(19\)Finally, this proof can be completed by substituting \([16](https://arxiv.org/html/2607.01665#A3.E16)\) into \([15](https://arxiv.org/html/2607.01665#A3.E15)\), and then combining with \([13](https://arxiv.org/html/2607.01665#A3.E13)\), \([14](https://arxiv.org/html/2607.01665#A3.E14)\), \([19](https://arxiv.org/html/2607.01665#A3.E19)\) andΔi​\(1\)=‖𝐱i​\(1\)−𝐱¯​\(2\)‖2=0\\Delta\_\{i\}\(1\)=\\\|\\mathbf\{x\}\_\{i\}\(1\)\-\\bar\{\\mathbf\{x\}\}\(2\)\\\|\_\{2\}=0\.

## Appendix DProof of Lemma[3\.7](https://arxiv.org/html/2607.01665#S3.Thmtheorem7)

To facilitate the analysis, we first rewrite the error definition in matrix notation\. LetZk=\[𝐳1k,…,𝐳nk\]∈ℝd×nZ^\{k\}=\[\\mathbf\{z\}\_\{1\}^\{k\},\\dots,\\mathbf\{z\}\_\{n\}^\{k\}\]\\in\\mathbb\{R\}^\{d\\times n\}andZ^k=\[𝐳^1k,…,𝐳^nk\]∈ℝd×n\\hat\{Z\}^\{k\}=\[\\hat\{\\mathbf\{z\}\}\_\{1\}^\{k\},\\dots,\\hat\{\\mathbf\{z\}\}\_\{n\}^\{k\}\]\\in\\mathbb\{R\}^\{d\\times n\}be the concatenated matrices of local variables and their replicas at iterationkk\. The average is denoted byZ¯k=Zk​ℳ\\bar\{Z\}^\{k\}=Z^\{k\}\\mathcal\{M\}, whereℳ=1n​𝟏n​𝟏n⊤\\mathcal\{M\}=\\frac\{1\}\{n\}\\mathbf\{1\}\_\{n\}\\mathbf\{1\}\_\{n\}^\{\\top\}\. Consequently, the total erroreke^\{k\}defined in Lemma[3\.7](https://arxiv.org/html/2607.01665#S3.Thmtheorem7)can be equivalently written using the Frobenius norm, which is

ek=𝔼​\[‖Zk−Z¯k‖F2\]\+𝔼​\[‖Zk−Z^k‖F2\]\.e^\{k\}=\\mathbb\{E\}\[\\\|Z^\{k\}\-\\bar\{Z\}^\{k\}\\\|\_\{F\}^\{2\}\]\+\\mathbb\{E\}\[\\\|Z^\{k\}\-\\hat\{Z\}^\{k\}\\\|\_\{F\}^\{2\}\]\.
The proof relies on establishing a recursive bound for these consensus and compression errors\. We first state a lemma that characterizes the one\-step error dynamics\.

###### Lemma D\.1\.

Suppose Assumptions[3\.1](https://arxiv.org/html/2607.01665#S3.Thmtheorem1),[3\.2](https://arxiv.org/html/2607.01665#S3.Thmtheorem2), and[3\.4](https://arxiv.org/html/2607.01665#S3.Thmtheorem4)hold, and letγ∈\(0,1\]\\gamma\\in\(0,1\]\. LetE1​\(k\):=𝔼Q​\[‖Zk−Z¯k‖F2\]E\_\{1\}\(k\):=\\mathbb\{E\}\_\{Q\}\[\\\|Z^\{k\}\-\\bar\{Z\}^\{k\}\\\|\_\{F\}^\{2\}\]andE2​\(k\):=𝔼Q​\[‖Zk−Z^k‖F2\]E\_\{2\}\(k\):=\\mathbb\{E\}\_\{Q\}\[\\\|Z^\{k\}\-\\hat\{Z\}^\{k\}\\\|\_\{F\}^\{2\}\]\. For any iterationk≥0k\\geq 0, the errors satisfy:

E1​\(k\+1\)\\displaystyle E\_\{1\}\(k\+1\)≤\(1−γ​ρ2\)2​E1​\(k\)\+\(γ\+2​γρ\)​\(1−ω\)​β2​E2​\(k\),\\displaystyle\\leq\\left\(1\-\\frac\{\\gamma\\rho\}\{2\}\\right\)^\{2\}E\_\{1\}\(k\)\+\\left\(\\gamma\+\\frac\{2\\gamma\}\{\\rho\}\\right\)\(1\-\\omega\)\\beta^\{2\}E\_\{2\}\(k\),\(20\)E2​\(k\+1\)\\displaystyle E\_\{2\}\(k\+1\)≤\(1\+2ω\)​γ2​β2​E1​\(k\)\+\(1−ω2\)​\(1\+8​γ\)​E2​\(k\)\.\\displaystyle\\leq\\left\(1\+\\frac\{2\}\{\\omega\}\\right\)\\gamma^\{2\}\\beta^\{2\}E\_\{1\}\(k\)\+\\left\(1\-\\frac\{\\omega\}\{2\}\\right\)\(1\+8\\gamma\)E\_\{2\}\(k\)\.\(21\)

Recall the total errorek=E1​\(k\)\+E2​\(k\)e^\{k\}=E\_\{1\}\(k\)\+E\_\{2\}\(k\)\. Summing \([20](https://arxiv.org/html/2607.01665#A4.E20)\) and \([21](https://arxiv.org/html/2607.01665#A4.E21)\), we obtain the linear recurrence, i\.e\.,

ek\+1≤η​\(γ\)​E1​\(k\)\+ξ​\(γ\)​E2​\(k\)≤max⁡\{η​\(γ\),ξ​\(γ\)\}⋅ek,e^\{k\+1\}\\leq\\eta\(\\gamma\)E\_\{1\}\(k\)\+\\xi\(\\gamma\)E\_\{2\}\(k\)\\leq\\max\\\{\\eta\(\\gamma\),\\xi\(\\gamma\)\\\}\\cdot e^\{k\},where the coefficients are defined as

η​\(γ\)\\displaystyle\\eta\(\\gamma\):=\(1−γ​ρ2\)2\+\(1\+2ω\)​γ2​β2,\\displaystyle:=\\left\(1\-\\frac\{\\gamma\\rho\}\{2\}\\right\)^\{2\}\+\\left\(1\+\\frac\{2\}\{\\omega\}\\right\)\\gamma^\{2\}\\beta^\{2\},ξ​\(γ\)\\displaystyle\\xi\(\\gamma\):=\(γ\+2​γρ\)​\(1−ω\)​β2\+\(1−ω2\)​\(1\+8​γ\)\.\\displaystyle:=\\left\(\\gamma\+\\frac\{2\\gamma\}\{\\rho\}\\right\)\(1\-\\omega\)\\beta^\{2\}\+\\left\(1\-\\frac\{\\omega\}\{2\}\\right\)\(1\+8\\gamma\)\.It is not hard to establish a valid upper bound formax⁡\{η​\(γ\),ξ​\(γ\)\}\\max\\\{\\eta\(\\gamma\),\\xi\(\\gamma\)\\\}by following the proof of Theorem 2 inKoloskova et al\. \[[2019](https://arxiv.org/html/2607.01665#bib.bib15)\]\. For completeness, we provide the detailed proof here\.

First, we observe thatη​\(γ\)\\eta\(\\gamma\)is a convex quadratic function with respect toγ\\gamma\. Its minimum occurs atγ′=2​ρ​ω4​\(ω\+2\)​β2\+ρ2​ω\\gamma^\{\\prime\}=\\frac\{2\\rho\\omega\}\{4\(\\omega\+2\)\\beta^\{2\}\+\\rho^\{2\}\\omega\}, with valueη​\(γ′\)=4​\(ω\+2\)​β24​\(ω\+2\)​β2\+ρ2​ω<1\\eta\(\\gamma^\{\\prime\}\)=\\frac\{4\(\\omega\+2\)\\beta^\{2\}\}\{4\(\\omega\+2\)\\beta^\{2\}\+\\rho^\{2\}\\omega\}<1\. Thus, by Jensen’s inequality, for anyλ∈\[0,1\]\\lambda\\in\[0,1\], we have

η​\(λ​γ′\)\\displaystyle\\eta\(\\lambda\\gamma^\{\\prime\}\)≤\(1−λ\)​η​\(0\)\+λ​η​\(γ′\)=1−λ​\(1−η​\(γ′\)\)=1−λ​ρ2​ω4​\(ω\+2\)​β2\+ρ2​ω\.\\displaystyle\\leq\(1\-\\lambda\)\\eta\(0\)\+\\lambda\\eta\(\\gamma^\{\\prime\}\)=1\-\\lambda\(1\-\\eta\(\\gamma^\{\\prime\}\)\)=1\-\\lambda\\frac\{\\rho^\{2\}\\omega\}\{4\(\\omega\+2\)\\beta^\{2\}\+\\rho^\{2\}\\omega\}\.\(22\)For the specific choiceλ′=4​\(ω\+2\)​β2\+ρ2​ω4​\(1−ω\)​\(ρ\+2\)​β2\+32​ρ−16​ρ​ω\+2​ρ2\\lambda^\{\\prime\}=\\frac\{4\(\\omega\+2\)\\beta^\{2\}\+\\rho^\{2\}\\omega\}\{4\(1\-\\omega\)\(\\rho\+2\)\\beta^\{2\}\+32\\rho\-16\\rho\\omega\+2\\rho^\{2\}\}, we obtain the step sizeγ∗=λ′​γ′\\gamma^\{\*\}=\\lambda^\{\\prime\}\\gamma^\{\\prime\}as given in \([2](https://arxiv.org/html/2607.01665#S3.E2)\)

γ∗=ρ​ω2​\(1−ω\)​\(ρ\+2\)​β2\+16​ρ−8​ρ​ω\+ρ2\.\\gamma^\{\*\}=\\frac\{\\rho\\omega\}\{2\(1\-\\omega\)\(\\rho\+2\)\\beta^\{2\}\+16\\rho\-8\\rho\\omega\+\\rho^\{2\}\}\.Substituting thisλ′\\lambda^\{\\prime\}back into the inequality \([22](https://arxiv.org/html/2607.01665#A4.E22)\), we verify that

η​\(γ∗\)≤1−ρ2​ω4​\(1−ω\)​\(ρ\+2\)​β2\+32​ρ−16​ρ​ω\+2​ρ2=1−γ∗​ρ2\.\\eta\(\\gamma^\{\*\}\)\\leq 1\-\\frac\{\\rho^\{2\}\\omega\}\{4\(1\-\\omega\)\(\\rho\+2\)\\beta^\{2\}\+32\\rho\-16\\rho\\omega\+2\\rho^\{2\}\}=1\-\\frac\{\\gamma^\{\*\}\\rho\}\{2\}\.Similarly, substitutingγ∗\\gamma^\{\*\}intoξ​\(γ\)\\xi\(\\gamma\), it holds that

ξ​\(γ∗\)=\(γ∗\+2​γ∗ρ\)​\(1−ω\)​β2\+\(1−ω2\)​\(1\+8​γ∗\)=1−γ∗​ρ2\.\\xi\(\\gamma^\{\*\}\)=\\left\(\\gamma^\{\*\}\+\\frac\{2\\gamma^\{\*\}\}\{\\rho\}\\right\)\(1\-\\omega\)\\beta^\{2\}\+\\left\(1\-\\frac\{\\omega\}\{2\}\\right\)\(1\+8\\gamma^\{\*\}\)=1\-\\frac\{\\gamma^\{\*\}\\rho\}\{2\}\.Thus, we conclude thatmax⁡\{η​\(γ∗\),ξ​\(γ∗\)\}≤1−γ∗​ρ2\\max\\\{\\eta\(\\gamma^\{\*\}\),\\xi\(\\gamma^\{\*\}\)\\\}\\leq 1\-\\frac\{\\gamma^\{\*\}\\rho\}\{2\}and the contraction factor is bounded byθ:=1−γ∗​ρ2\\theta:=1\-\\frac\{\\gamma^\{\*\}\\rho\}\{2\}\. Applying the recursion iteratively yields

ek≤θ​ek−1≤⋯≤θk​e0\.e^\{k\}\\leq\\theta e^\{k\-1\}\\leq\\dots\\leq\\theta^\{k\}e^\{0\}\.This completes the proof of Lemma[3\.7](https://arxiv.org/html/2607.01665#S3.Thmtheorem7)\.

## Appendix EProof of Lemma[D\.1](https://arxiv.org/html/2607.01665#A4.Thmtheorem1)

We analyze the evolution of the consensus and compression errors using the matrix\-form updates\. SinceAAis doubly stochastic, we haveZ¯k=Zk​ℳ\\bar\{Z\}^\{k\}=Z^\{k\}\\mathcal\{M\}andZ¯k​A=Z¯k\\bar\{Z\}^\{k\}A=\\bar\{Z\}^\{k\}\. The update rules in Algorithm[1](https://arxiv.org/html/2607.01665#alg1)imply the following dynamics, i\.e\.,

Z^k\+1\\displaystyle\\hat\{Z\}^\{k\+1\}=Z^k\+Q​\(Zk−Z^k\),\\displaystyle=\\hat\{Z\}^\{k\}\+Q\\left\(Z^\{k\}\-\\hat\{Z\}^\{k\}\\right\),\(23\)Zk\+1\\displaystyle Z^\{k\+1\}=Zk\+γ​Z^k\+1​\(A−I\)=Zk−γ​Z^k\+1​ℒ\.\\displaystyle=Z^\{k\}\+\\gamma\\hat\{Z\}^\{k\+1\}\(A\-I\)=Z^\{k\}\-\\gamma\\hat\{Z\}^\{k\+1\}\\mathcal\{L\}\.\(24\)Assumption[3\.2](https://arxiv.org/html/2607.01665#S3.Thmtheorem2)combined with \([23](https://arxiv.org/html/2607.01665#A5.E23)\) yields the contraction property of

𝔼Q​\[‖Zk−Z^k\+1‖F2\]≤\(1−ω\)​‖Zk−Z^k‖F2\.\\mathbb\{E\}\_\{Q\}\\left\[\\left\\\|Z^\{k\}\-\\hat\{Z\}^\{k\+1\}\\right\\\|\_\{F\}^\{2\}\\right\]\\leq\(1\-\\omega\)\\left\\\|Z^\{k\}\-\\hat\{Z\}^\{k\}\\right\\\|\_\{F\}^\{2\}\.\(25\)
#### Part 1: Consensus error analysis\.

Recall thatZ¯k​ℒ=0\\bar\{Z\}^\{k\}\\mathcal\{L\}=0andℳ​ℒ=0\\mathcal\{M\}\\mathcal\{L\}=0\. Multiplying \([24](https://arxiv.org/html/2607.01665#A5.E24)\) by\(I−ℳ\)\(I\-\\mathcal\{M\}\), we isolate the consensus deviation by

Zk\+1−Z¯k\+1\\displaystyle Z^\{k\+1\}\-\\bar\{Z\}^\{k\+1\}=\(Zk−γ​Z^k\+1​ℒ\)​\(I−ℳ\)\\displaystyle=\\left\(Z^\{k\}\-\\gamma\\hat\{Z\}^\{k\+1\}\\mathcal\{L\}\\right\)\(I\-\\mathcal\{M\}\)=\(Zk−Z¯k\)​\(I−γ​ℒ\)−γ​\(Z^k\+1−Zk\)​ℒ\.\\displaystyle=\(Z^\{k\}\-\\bar\{Z\}^\{k\}\)\(I\-\\gamma\\mathcal\{L\}\)\-\\gamma\(\\hat\{Z\}^\{k\+1\}\-Z^\{k\}\)\\mathcal\{L\}\.Using Young’s inequality‖X\+Y‖F2≤\(1\+α\)​‖X‖F2\+\(1\+α−1\)​‖Y‖F2\\\|X\+Y\\\|\_\{F\}^\{2\}\\leq\(1\+\\alpha\)\\\|X\\\|\_\{F\}^\{2\}\+\(1\+\\alpha^\{\-1\}\)\\\|Y\\\|\_\{F\}^\{2\}withα=γ​ρ2\\alpha=\\frac\{\\gamma\\rho\}\{2\}, we have

‖Zk\+1−Z¯k\+1‖F2≤\(1\+γ​ρ2\)​‖\(Zk−Z¯k\)​\(I−γ​ℒ\)‖F2⏟T1\+\(1\+2γ​ρ\)​‖γ​\(Z^k\+1−Zk\)​ℒ‖F2⏟T2\.\\displaystyle\\\|Z^\{k\+1\}\-\\bar\{Z\}^\{k\+1\}\\\|\_\{F\}^\{2\}\\leq\\left\(1\+\\frac\{\\gamma\\rho\}\{2\}\\right\)\\underbrace\{\\\|\(Z^\{k\}\-\\bar\{Z\}^\{k\}\)\(I\-\\gamma\\mathcal\{L\}\)\\\|\_\{F\}^\{2\}\}\_\{T\_\{1\}\}\+\\left\(1\+\\frac\{2\}\{\\gamma\\rho\}\\right\)\\underbrace\{\\\|\\gamma\(\\hat\{Z\}^\{k\+1\}\-Z^\{k\}\)\\mathcal\{L\}\\\|\_\{F\}^\{2\}\}\_\{T\_\{2\}\}\.\(26\)ForT1T\_\{1\}, utilizing the property\(Zk−Z¯k\)​ℳ=0\(Z^\{k\}\-\\bar\{Z\}^\{k\}\)\\mathcal\{M\}=0and the spectral bound‖I−γ​ℒ−ℳ‖2≤1−γ​ρ\\\|I\-\\gamma\\mathcal\{L\}\-\\mathcal\{M\}\\\|\_\{2\}\\leq 1\-\\gamma\\rhoforγ​ρ≤1\\gamma\\rho\\leq 1, we obtain that

T1=‖\(Zk−Z¯k\)​\(I−γ​ℒ−ℳ\)‖F2≤\(1−γ​ρ\)2​‖Zk−Z¯k‖F2\.T\_\{1\}=\\\|\(Z^\{k\}\-\\bar\{Z\}^\{k\}\)\(I\-\\gamma\\mathcal\{L\}\-\\mathcal\{M\}\)\\\|\_\{F\}^\{2\}\\leq\(1\-\\gamma\\rho\)^\{2\}\\\|Z^\{k\}\-\\bar\{Z\}^\{k\}\\\|\_\{F\}^\{2\}\.ForT2T\_\{2\}, using‖ℒ‖2=β\\\|\\mathcal\{L\}\\\|\_\{2\}=\\beta, we have𝔼Q​\[T2\]≤γ2​β2​\(1−ω\)​𝔼Q​\[‖Zk−Z^k‖F2\]\\mathbb\{E\}\_\{Q\}\[T\_\{2\}\]\\leq\\gamma^\{2\}\\beta^\{2\}\(1\-\\omega\)\\mathbb\{E\}\_\{Q\}\[\\\|Z^\{k\}\-\\hat\{Z\}^\{k\}\\\|\_\{F\}^\{2\}\]\. LetE1​\(k\):=𝔼Q​\[‖Zk−Z¯k‖F2\]E\_\{1\}\(k\):=\\mathbb\{E\}\_\{Q\}\[\\\|Z^\{k\}\-\\bar\{Z\}^\{k\}\\\|\_\{F\}^\{2\}\]andE2​\(k\):=𝔼Q​\[‖Zk−Z^k‖F2\]E\_\{2\}\(k\):=\\mathbb\{E\}\_\{Q\}\[\\\|Z^\{k\}\-\\hat\{Z\}^\{k\}\\\|\_\{F\}^\{2\}\]\. Substituting these bounds into \([26](https://arxiv.org/html/2607.01665#A5.E26)\) and observing that\(1\+γ​ρ2\)​\(1−γ​ρ\)2≤\(1−γ​ρ2\)2\(1\+\\frac\{\\gamma\\rho\}\{2\}\)\(1\-\\gamma\\rho\)^\{2\}\\leq\(1\-\\frac\{\\gamma\\rho\}\{2\}\)^\{2\}forγ​ρ≤1\\gamma\\rho\\leq 1, we derive that

E1​\(k\+1\)≤\(1−γ​ρ2\)2​E1​\(k\)\+\(γ\+2​γρ\)​\(1−ω\)​β2​E2​\(k\)\.E\_\{1\}\(k\+1\)\\leq\\left\(1\-\\frac\{\\gamma\\rho\}\{2\}\\right\)^\{2\}E\_\{1\}\(k\)\+\\left\(\\gamma\+\\frac\{2\\gamma\}\{\\rho\}\\right\)\(1\-\\omega\)\\beta^\{2\}E\_\{2\}\(k\)\.

#### Part 2: Compression error analysis\.

Rearranging \([24](https://arxiv.org/html/2607.01665#A5.E24)\) allows us to express the compression update as

Zk\+1−Z^k\+1\\displaystyle Z^\{k\+1\}\-\\hat\{Z\}^\{k\+1\}=Zk−γ​Z^k\+1​ℒ−Z^k\+1=\(Zk−Z^k\+1\)​\(I\+γ​ℒ\)−γ​\(Zk−Z¯k\)​ℒ\.\\displaystyle=Z^\{k\}\-\\gamma\\hat\{Z\}^\{k\+1\}\\mathcal\{L\}\-\\hat\{Z\}^\{k\+1\}=\(Z^\{k\}\-\\hat\{Z\}^\{k\+1\}\)\(I\+\\gamma\\mathcal\{L\}\)\-\\gamma\(Z^\{k\}\-\\bar\{Z\}^\{k\}\)\\mathcal\{L\}\.By using Young’s inequality again withα=ω2\\alpha=\\frac\{\\omega\}\{2\}, we have

‖Zk\+1−Z^k\+1‖F2≤\(1\+ω2\)​‖\(Zk−Z^k\+1\)​\(I\+γ​ℒ\)‖F2\+\(1\+2ω\)​‖γ​\(Zk−Z¯k\)​ℒ‖F2\.\\\|Z^\{k\+1\}\-\\hat\{Z\}^\{k\+1\}\\\|\_\{F\}^\{2\}\\leq\\left\(1\+\\frac\{\\omega\}\{2\}\\right\)\\\|\(Z^\{k\}\-\\hat\{Z\}^\{k\+1\}\)\(I\+\\gamma\\mathcal\{L\}\)\\\|\_\{F\}^\{2\}\+\\left\(1\+\\frac\{2\}\{\\omega\}\\right\)\\\|\\gamma\(Z^\{k\}\-\\bar\{Z\}^\{k\}\)\\mathcal\{L\}\\\|\_\{F\}^\{2\}\.By applying \([25](https://arxiv.org/html/2607.01665#A5.E25)\) and the above inequality, we obtain

E2​\(k\+1\)\\displaystyle E\_\{2\}\(k\+1\)≤\(1\+ω2\)​‖I\+γ​ℒ‖22​\(1−ω\)​E2​\(k\)\+\(1\+2ω\)​γ2​β2​E1​\(k\)\.\\displaystyle\\leq\\left\(1\+\\frac\{\\omega\}\{2\}\\right\)\\\|I\+\\gamma\\mathcal\{L\}\\\|\_\{2\}^\{2\}\(1\-\\omega\)E\_\{2\}\(k\)\+\\left\(1\+\\frac\{2\}\{\\omega\}\\right\)\\gamma^\{2\}\\beta^\{2\}E\_\{1\}\(k\)\.Using‖I\+γ​ℒ‖2≤1\+γ​β\\\|I\+\\gamma\\mathcal\{L\}\\\|\_\{2\}\\leq 1\+\\gamma\\betaand the inequality\(1\+ω2\)​\(1−ω\)​\(1\+γ​β\)2≤\(1−ω2\)​\(1\+8​γ\)\(1\+\\frac\{\\omega\}\{2\}\)\(1\-\\omega\)\(1\+\\gamma\\beta\)^\{2\}\\leq\(1\-\\frac\{\\omega\}\{2\}\)\(1\+8\\gamma\)forβ≤2,γ≤1\\beta\\leq 2,\\gamma\\leq 1, we conclude

E2​\(k\+1\)≤\(1\+2ω\)​γ2​β2​E1​\(k\)\+\(1−ω2\)​\(1\+8​γ\)​E2​\(k\)\.E\_\{2\}\(k\+1\)\\leq\\left\(1\+\\frac\{2\}\{\\omega\}\\right\)\\gamma^\{2\}\\beta^\{2\}E\_\{1\}\(k\)\+\\left\(1\-\\frac\{\\omega\}\{2\}\\right\)\(1\+8\\gamma\)E\_\{2\}\(k\)\.This completes the proof of Lemma[D\.1](https://arxiv.org/html/2607.01665#A4.Thmtheorem1)\.

## Appendix FProof of Lemma[B\.3](https://arxiv.org/html/2607.01665#A2.Thmtheorem3)

The proof relies on the recursive error bound established in Lemma[3\.7](https://arxiv.org/html/2607.01665#S3.Thmtheorem7)\. We proceed the proof in three steps: analyzing the error propagation, determining the number of iterationsKK, and deriving the final bound\.

#### Step 1: Error propagation analysis\.

At the beginning of blockzz\(i\.e\.,k=0k=0\), the states are initialized based on the output of the previous block and the gradient update

𝐳i0​\(z\)=𝐳iK​\(z−1\)\+𝐝i​\(z−1\),𝐳^i0​\(z\)=𝐳^iK​\(z−1\)\.\\mathbf\{z\}\_\{i\}^\{0\}\(z\)=\\mathbf\{z\}\_\{i\}^\{K\}\(z\-1\)\+\\mathbf\{d\}\_\{i\}\(z\-1\),\\quad\\hat\{\\mathbf\{z\}\}\_\{i\}^\{0\}\(z\)=\\hat\{\\mathbf\{z\}\}\_\{i\}^\{K\}\(z\-1\)\.Consequently, the initial errorez0e\_\{z\}^\{0\}is bounded by the error at the end of the previous block,ez−1Ke\_\{z\-1\}^\{K\}\. Applying the inequality‖a\+b‖22≤2​‖a‖22\+2​‖b‖22\\\|a\+b\\\|\_\{2\}^\{2\}\\leq 2\\\|a\\\|\_\{2\}^\{2\}\+2\\\|b\\\|\_\{2\}^\{2\}and the variance decomposition, we derive

ez0\\displaystyle e\_\{z\}^\{0\}=𝔼​∑i=1n\(‖𝐳i0​\(z\)−𝐳¯0​\(z\)‖22\+‖𝐳i0​\(z\)−𝐳^i0​\(z\)‖22\)\\displaystyle=\\mathbb\{E\}\\sum\_\{i=1\}^\{n\}\\left\(\\\|\\mathbf\{z\}\_\{i\}^\{0\}\(z\)\-\\bar\{\\mathbf\{z\}\}^\{0\}\(z\)\\\|\_\{2\}^\{2\}\+\\\|\\mathbf\{z\}\_\{i\}^\{0\}\(z\)\-\\hat\{\\mathbf\{z\}\}\_\{i\}^\{0\}\(z\)\\\|\_\{2\}^\{2\}\\right\)\(27\)≤2​ez−1K\+2​∑i=1n\(‖𝐝i​\(z−1\)−𝐝¯​\(z−1\)‖22\+‖𝐝i​\(z−1\)‖22\)\\displaystyle\\leq 2e\_\{z\-1\}^\{K\}\+2\\sum\_\{i=1\}^\{n\}\\left\(\\\|\\mathbf\{d\}\_\{i\}\(z\-1\)\-\\bar\{\\mathbf\{d\}\}\(z\-1\)\\\|\_\{2\}^\{2\}\+\\\|\\mathbf\{d\}\_\{i\}\(z\-1\)\\\|\_\{2\}^\{2\}\\right\)≤2​ez−1K\+4​‖D​\(z−1\)‖F2\.\\displaystyle\\leq 2e\_\{z\-1\}^\{K\}\+4\\\|D\(z\-1\)\\\|\_\{F\}^\{2\}\.Now, we invoke Lemma[3\.7](https://arxiv.org/html/2607.01665#S3.Thmtheorem7)\. By setting the step sizeγ\\gammaas specified, the algorithm ensures the contraction propertyezK≤θ​ez0e\_\{z\}^\{K\}\\leq\\theta e\_\{z\}^\{0\}, where the contraction factor is defined asθ:=\(1−γ​ρ2\)K\\theta:=\(1\-\\frac\{\\gamma\\rho\}\{2\}\)^\{K\}\. LetCz:=4​‖D​\(z−1\)‖F2C\_\{z\}:=4\\\|D\(z\-1\)\\\|\_\{F\}^\{2\}\. Combining this with \([27](https://arxiv.org/html/2607.01665#A6.E27)\), we obtain the recursion

ezK≤θ​ez0≤2​θ​ez−1K\+θ​Cz\.e\_\{z\}^\{K\}\\leq\\theta e\_\{z\}^\{0\}\\leq 2\\theta e\_\{z\-1\}^\{K\}\+\\theta C\_\{z\}\.Denotingez:=ezKe\_\{z\}:=e\_\{z\}^\{K\}and noting the initializatione1=0e\_\{1\}=0\(since𝐳i​\(1\)=𝟎\\mathbf\{z\}\_\{i\}\(1\)=\\mathbf\{0\}\), we solve this recursion forz≥2z\\geq 2\. Assuming2​θ<12\\theta<1, summing the geometric series yields

ez≤θ​Cz​∑j=0z−2\(2​θ\)j<θ​Cz1−2​θ\.e\_\{z\}\\leq\\theta C\_\{z\}\\sum\_\{j=0\}^\{z\-2\}\(2\\theta\)^\{j\}<\\frac\{\\theta C\_\{z\}\}\{1\-2\\theta\}\.\(28\)

#### Step 2: Choosing number of iterationsKK\.

Next, we determine the condition onKKto ensure the error coefficient scales with1/n1/\\sqrt\{n\}\. Specifically, we require

θ1−2​θ≤1n⇔θ≤1n\+2\.\\sqrt\{\\frac\{\\theta\}\{1\-2\\theta\}\}\\leq\\frac\{1\}\{\\sqrt\{n\}\}\\iff\\theta\\leq\\frac\{1\}\{n\+2\}\.Using the inequalityln⁡\(1−x\)≤−x\\ln\(1\-x\)\\leq\-xforx∈\(0,1\)x\\in\(0,1\), it suffices to chooseKKsuch that

K≥ln⁡\(n\+2\)−ln⁡\(1−γ​ρ2\)≥2​ln⁡\(n\+2\)γ​ρ\.K\\geq\\frac\{\\ln\(n\+2\)\}\{\-\\ln\(1\-\\frac\{\\gamma\\rho\}\{2\}\)\}\\geq\\frac\{2\\ln\(n\+2\)\}\{\\gamma\\rho\}\.Under this condition, we haveθ≤1/\(n\+2\)<1/2\\theta\\leq 1/\(n\+2\)<1/2, which validates the convergence of the geometric series in \([28](https://arxiv.org/html/2607.01665#A6.E28)\)\.

#### Step 3: Final bound\.

Combining the results from Step 1 and Step 2, we obtain the final bound on the consensus error

𝔼​\[‖𝐳i​\(z\)−𝐳¯​\(z\)‖2\]≤ez​<θ1−2​θ​Cz≤1n⋅2∥​D​\(z−1\)∥F\.\\mathbb\{E\}\\left\[\\left\\\|\\mathbf\{z\}\_\{i\}\(z\)\-\\bar\{\\mathbf\{z\}\}\(z\)\\right\\\|\_\{2\}\\right\]\\leq\\sqrt\{e\_\{z\}\}<\\sqrt\{\\frac\{\\theta\}\{1\-2\\theta\}\}\\sqrt\{C\_\{z\}\}\\leq\\frac\{1\}\{\\sqrt\{n\}\}\\cdot 2\\\|D\(z\-1\)\\\|\_\{F\}\.This concludes the proof of Lemma[B\.3](https://arxiv.org/html/2607.01665#A2.Thmtheorem3)\.

## Appendix GProof of Corollaries[3\.9](https://arxiv.org/html/2607.01665#S3.Thmtheorem9)and[3\.10](https://arxiv.org/html/2607.01665#S3.Thmtheorem10)

#### Convex case\.

In the following, we first consider the case with convex losses, by substitutingα=0\\alpha=0,h=3​L​T​G/Rh=3\\sqrt\{LT\}G/RandL=⌈2​ln⁡\(n\+2\)/γ​ρ⌉L=\\left\\lceil 2\\ln\(n\+2\)/\\gamma\\rho\\right\\rceilinto \([4](https://arxiv.org/html/2607.01665#S3.E4)\), we have

𝔼​\[RT,i\]\\displaystyle\\mathbb\{E\}\[R\_\{T,i\}\]≤3​n​L​G​\(∑z=2T/LL​Gh\+∑z=1T/L2​L​Gh\)\+n​h​R2≤9​n​L​G2​Th\+n​h​R2\\displaystyle\\leq 3nLG\\left\(\\sum\_\{z=2\}^\{T/L\}\\frac\{LG\}\{h\}\+\\sum\_\{z=1\}^\{T/L\}\\frac\{2LG\}\{h\}\\right\)\+nhR^\{2\}\\leq\\frac\{9nLG^\{2\}T\}\{h\}\+nhR^\{2\}≤6​n​G​R​L​T=O​\(n​log⁡n​T⋅\(γ​ρ\)−1/2\)=O​\(n​log⁡n⋅ρ−1​ω−1/2⋅T\)\.\\displaystyle\\leq 6nGR\\sqrt\{LT\}=O\\left\(n\\sqrt\{\\log n\}\\sqrt\{T\}\\cdot\(\\gamma\\rho\)^\{\-1/2\}\\right\)=O\\left\(n\\sqrt\{\\log n\}\\cdot\\rho^\{\-1\}\\omega^\{\-1/2\}\\cdot\\sqrt\{T\}\\right\)\.Whenω=1\\omega=1, we have\(γ​ρ\)−1/2=\(8\+ρ\)/ρ=O​\(ρ−1/2\)\(\\gamma\\rho\)^\{\-1/2\}=\\sqrt\{\(8\+\\rho\)/\\rho\}=O\(\\rho^\{\-1/2\}\)\. Thus, the regret bound can be improved to

𝔼​\[RT,i\]\\displaystyle\\mathbb\{E\}\[R\_\{T,i\}\]=O​\(n​log⁡n⋅ρ−1/2⋅T\)\.\\displaystyle=O\\left\(n\\sqrt\{\\log n\}\\cdot\\rho^\{\-1/2\}\\cdot\\sqrt\{T\}\\right\)\.

#### Strongly convex case\.

We continue to consider the case with the strongly convex losses, by substitutingh=α​L,L=⌈2​ln⁡\(n\+2\)/γ​ρ⌉h=\\alpha L,L=\\left\\lceil 2\\ln\(n\+2\)/\\gamma\\rho\\right\\rceilinto \([4](https://arxiv.org/html/2607.01665#S3.E4)\), we have

𝔼​\[RT,i\]\\displaystyle\\mathbb\{E\}\[R\_\{T,i\}\]≤n​α​L​R2\+6​n​L​Gα​\(\(G\+α​R\)​ln⁡\(T/L\)\+2​\(G\+2​α​R\)​ln⁡\(T/L\)\)\\displaystyle\\leq n\\alpha LR^\{2\}\+\\frac\{6nLG\}\{\\alpha\}\\left\(\(G\+\\alpha R\)\\ln\(T/L\)\+2\(G\+2\\alpha R\)\\ln\(T/L\)\\right\)=n​α​L​R2\+6​n​L​G​\(3​G\+5​α​R\)​ln⁡\(T/L\)α\\displaystyle=n\\alpha LR^\{2\}\+\\frac\{6nLG\\left\(3G\+5\\alpha R\\right\)\\ln\(T/L\)\}\{\\alpha\}=O​\(n​log⁡n⋅γ−1​ρ−1⋅log⁡T\)=O​\(n​log⁡n⋅ρ−2​ω−1⋅log⁡T\)\.\\displaystyle=O\\left\(n\\log n\\cdot\\gamma^\{\-1\}\\rho^\{\-1\}\\cdot\\log T\\right\)=O\\left\(n\\log n\\cdot\\rho^\{\-2\}\\omega^\{\-1\}\\cdot\\log T\\right\)\.Whenω=1\\omega=1, we have\(γ​ρ\)−1/2=\(8\+ρ\)/ρ=O​\(ρ−1/2\)\(\\gamma\\rho\)^\{\-1/2\}=\\sqrt\{\(8\+\\rho\)/\\rho\}=O\(\\rho^\{\-1/2\}\)\. Thus, the regret bound can be improved to

𝔼​\[RT,i\]=O​\(n​log⁡n⋅ρ−1⋅log⁡T\)\.\\displaystyle\\mathbb\{E\}\[R\_\{T,i\}\]=O\\left\(n\\log n\\cdot\\rho^\{\-1\}\\cdot\\log T\\right\)\.

## Appendix HProof of Corollaries[3\.13](https://arxiv.org/html/2607.01665#S3.Thmtheorem13)and[3\.14](https://arxiv.org/html/2607.01665#S3.Thmtheorem14)

#### Convex case\.

In the following, we first consider the case with convex losses, in which the parameters of our Algorithm[3](https://arxiv.org/html/2607.01665#alg3)are set toα=0\\alpha=0,L=max⁡\{K,T\}L=\\max\\\{K,\\sqrt\{T\}\\\},K=⌈2​ln⁡\(n\+2\)/γ​ρ⌉K=\\left\\lceil 2\\ln\(n\+2\)/\\gamma\\rho\\right\\rceil,h=d​L​T​M/Rh=\\sqrt\{dLT\}M/Randϵ=c​d1/2​T−1/4\\epsilon=c\\,d^\{1/2\}T^\{\-1/4\}\. Because ofα=0\\alpha=0we have

𝔼​\[RT,i\]\\displaystyle\\mathbb\{E\}\[R\_\{T,i\}\]≤6​n​L​G​∑z=2T/L2​L​d2​M2ϵ2\+2​L2​G22​h\+6​n​L​G​∑z=1T/L2​L​d​Mϵ\+2​L​G2​h\\displaystyle\\leq 6nLG\\sum\_\{z=2\}^\{T/L\}\\frac\{\\sqrt\{2L\\frac\{d^\{2\}M^\{2\}\}\{\\epsilon^\{2\}\}\+2L^\{2\}G^\{2\}\}\}\{2h\}\+6nLG\\sum\_\{z=1\}^\{T/L\}\\frac\{2\\frac\{\\sqrt\{L\}dM\}\{\\epsilon\}\+2LG\}\{2h\}\(29\)\+2​n​∑z=1T/L\(2​L​d​Mϵ\+2​L​G\)22​h\+n​h​R2\+3​ϵ​n​G​T\+ϵ​n​G​R​Tr\.\\displaystyle\\quad\+2n\\sum\_\{z=1\}^\{T/L\}\\frac\{\\left\(2\\frac\{\\sqrt\{L\}dM\}\{\\epsilon\}\+2LG\\right\)^\{2\}\}\{2h\}\+nhR^\{2\}\+3\\epsilon nGT\+\\frac\{\\epsilon nGRT\}\{r\}\.Becauseϵ=c​d1/2​T−1/4\\epsilon=c\\,d^\{1/2\}T^\{\-1/4\}andh=d​L​T​M/Rh=\\sqrt\{dLT\}M/R, we can bound the first term on the R\.H\.S of \([29](https://arxiv.org/html/2607.01665#A8.E29)\) by

6​n​L​G​∑z=2T/L2​L​d2​M2ϵ2\+2​L2​G22​h≤6​n​L​G⋅TL​\(L​d​Mh​ϵ\+L​Gh\)=O​\(n​T3/4\)\+O​\(n​L​T\)\.\\displaystyle 6nLG\\sum\_\{z=2\}^\{T/L\}\\frac\{\\sqrt\{2L\\frac\{d^\{2\}M^\{2\}\}\{\\epsilon^\{2\}\}\+2L^\{2\}G^\{2\}\}\}\{2h\}\\leq 6nLG\\cdot\\frac\{T\}\{L\}\\left\(\\frac\{\\sqrt\{L\}dM\}\{h\\epsilon\}\+\\frac\{LG\}\{h\}\\right\)=O\(nT^\{3/4\}\)\+O\(n\\sqrt\{LT\}\)\.\(30\)Similarly, the second term can be bounded by

6​n​L​G​∑z=1T/L2​L​d​Mϵ\+2​L​G2​h=6​n​L​G⋅TL​\(L​d​Mh​ϵ\+L​Gh\)=O​\(n​T3/4\)\+O​\(n​L​T\)\.6nLG\\sum\_\{z=1\}^\{T/L\}\\frac\{2\\frac\{\\sqrt\{L\}dM\}\{\\epsilon\}\+2LG\}\{2h\}=6nLG\\cdot\\frac\{T\}\{L\}\\left\(\\frac\{\\sqrt\{L\}dM\}\{h\\epsilon\}\+\\frac\{LG\}\{h\}\\right\)=O\(nT^\{3/4\}\)\+O\(n\\sqrt\{LT\}\)\.\(31\)And the third term can be bounded by

2​n​∑z=1T/L\(2​L​d​Mϵ\+2​L​G\)22​h≤4​n⋅TL​\(L​d2​M2h​ϵ2\+L2​G2h\)=O​\(n​T3/4\)\+O​\(n​L​T\)\.\\displaystyle 2n\\sum\_\{z=1\}^\{T/L\}\\frac\{\\left\(2\\frac\{\\sqrt\{L\}dM\}\{\\epsilon\}\+2LG\\right\)^\{2\}\}\{2h\}\\leq 4n\\cdot\\frac\{T\}\{L\}\\left\(\\frac\{Ld^\{2\}M^\{2\}\}\{h\\epsilon^\{2\}\}\+\\frac\{L^\{2\}G^\{2\}\}\{h\}\\right\)=O\(nT^\{3/4\}\)\+O\(n\\sqrt\{LT\}\)\.\(32\)Moreover, the remaining terms on the R\.H\.S of \([29](https://arxiv.org/html/2607.01665#A8.E29)\) have the bound of

n​h​R2\+\(3\+Rr\)​ϵ​n​G​T=n​M​d​L​T​R\+\(3\+Rr\)​c​d1/2​n​G​T3/4\\displaystyle nhR^\{2\}\+\\left\(3\+\\frac\{R\}\{r\}\\right\)\\epsilon nGT=nM\\sqrt\{dLT\}R\+\\left\(3\+\\frac\{R\}\{r\}\\right\)cd^\{1/2\}nGT^\{3/4\}\(33\)=O​\(n​L​T\)\+O​\(n​T3/4\)\.\\displaystyle=O\(n\\sqrt\{LT\}\)\+O\(nT^\{3/4\}\)\.Finally, by combining \([29](https://arxiv.org/html/2607.01665#A8.E29)\), \([30](https://arxiv.org/html/2607.01665#A8.E30)\), \([31](https://arxiv.org/html/2607.01665#A8.E31)\), \([32](https://arxiv.org/html/2607.01665#A8.E32)\) and \([33](https://arxiv.org/html/2607.01665#A8.E33)\), we can obtain

𝔼​\[RT,i\]=O​\(n​T3/4\)\+O​\(n​L​T\)≤O​\(n​T3/4\+n​K​T\)\.\\displaystyle\\mathbb\{E\}\[R\_\{T,i\}\]=O\(nT^\{3/4\}\)\+O\(n\\sqrt\{LT\}\)\\leq O\(nT^\{3/4\}\+n\\sqrt\{KT\}\)\.

#### Strongly convex case\.

We continue to consider the case with the strongly convex losses, in which the parameters of our Algorithm[3](https://arxiv.org/html/2607.01665#alg3)are set toα\>0\\alpha\>0,L=max⁡\{K,T2/3​\(ln⁡T\)−2/3\}L=\\max\\\{K,T^\{2/3\}\(\\ln T\)^\{\-2/3\}\\\},K=⌈2​ln⁡\(n\+2\)/γ​ρ⌉K=\\left\\lceil 2\\ln\(n\+2\)/\\gamma\\rho\\right\\rceil,ϵ=c​d2/3​T−1/3​\(ln⁡T\)1/3\\epsilon=c\\,d^\{2/3\}T^\{\-1/3\}\(\\ln T\)^\{1/3\}andh=α​Lh=\\alpha L\. Becauseα\>0\\alpha\>0,ϵ=c​d2/3​T−1/3​\(ln⁡T\)1/3\\epsilon=c\\,d^\{2/3\}T^\{\-1/3\}\(\\ln T\)^\{1/3\}andh=α​Lh=\\alpha L, we can bound the first term on the R\.H\.S of \([29](https://arxiv.org/html/2607.01665#A8.E29)\) by

6​n​L​G​∑z=2T/L2​L​d2​M2ϵ2\+2​L2​G2\+2​α2​L2​R2\(z−2\)​L​α\+2​h=6​n​L​G​∑z=2T/L2​L​d2​M2ϵ2\+2​L2​G2\+2​α2​L2​R2α​L​z\\displaystyle 6nLG\\sum\_\{z=2\}^\{T/L\}\\frac\{\\sqrt\{2L\\frac\{d^\{2\}M^\{2\}\}\{\\epsilon^\{2\}\}\+2L^\{2\}G^\{2\}\+2\\alpha^\{2\}L^\{2\}R^\{2\}\}\}\{\(z\-2\)L\\alpha\+2h\}=6nLG\\sum\_\{z=2\}^\{T/L\}\\frac\{\\sqrt\{2L\\frac\{d^\{2\}M^\{2\}\}\{\\epsilon^\{2\}\}\+2L^\{2\}G^\{2\}\+2\\alpha^\{2\}L^\{2\}R^\{2\}\}\}\{\\alpha Lz\}\(34\)≤6​n​G​\(1\+ln⁡\(T/L\)\)​\(2​L​d​Mα​ϵ\+2​L​G2\+α2​R2α\)\\displaystyle\\leq 6nG\(1\+\\ln\(T/L\)\)\\left\(\\frac\{2\\sqrt\{L\}dM\}\{\\alpha\\epsilon\}\+\\frac\{2L\\sqrt\{G^\{2\}\+\\alpha^\{2\}R^\{2\}\}\}\{\\alpha\}\\right\)=O​\(n​L​T1/3​\(log⁡T\)2/3\)\+O​\(n​L​log⁡T\)\.\\displaystyle=O\\left\(n\\sqrt\{L\}\\,T^\{1/3\}\(\\log T\)^\{2/3\}\\right\)\+O\\left\(nL\\log T\\right\)\.Then, we can bound the second term by

6​n​L​G​∑z=1T/L2​L​d​Mϵ\+2​L​G\+3​α​L​R\(z−1\)​L​α\+2​h=6​n​L​G​∑z=1T/L2​L​d​Mϵ\+2​L​G\+3​α​L​Rα​L​\(z\+1\)\\displaystyle 6nLG\\sum\_\{z=1\}^\{T/L\}\\frac\{2\\frac\{\\sqrt\{L\}dM\}\{\\epsilon\}\+2LG\+3\\alpha LR\}\{\(z\-1\)L\\alpha\+2h\}=6nLG\\sum\_\{z=1\}^\{T/L\}\\frac\{2\\frac\{\\sqrt\{L\}dM\}\{\\epsilon\}\+2LG\+3\\alpha LR\}\{\\alpha L\(z\+1\)\}\(35\)≤6​n​G​\(1\+ln⁡T/L\)​\(2​L​d​Mα​ϵ\+L​\(2​G\+3​α​R\)α\)\\displaystyle\\leq 6nG\(1\+\\ln T/L\)\\left\(\\frac\{2\\sqrt\{L\}dM\}\{\\alpha\\epsilon\}\+\\frac\{L\(2G\+3\\alpha R\)\}\{\\alpha\}\\right\)=O​\(n​L​T1/3​\(log⁡T\)2/3\)\+O​\(n​L​log⁡T\)\.\\displaystyle=O\\left\(n\\sqrt\{L\}T^\{1/3\}\(\\log T\)^\{2/3\}\\right\)\+O\\left\(nL\\log T\\right\)\.Similarly, the third term can be bounded by

2​n​∑z=1T/L\(2​L​d​Mϵ\+2​L​G\+3​α​L​R\)2z​L​α\+2​h=2​n​∑z=1T/L\(2​L​d​Mϵ\+2​L​G\+3​α​L​R\)2α​L​\(z\+2\)\\displaystyle 2n\\sum\_\{z=1\}^\{T/L\}\\frac\{\\left\(2\\frac\{\\sqrt\{L\}dM\}\{\\epsilon\}\+2LG\+3\\alpha LR\\right\)^\{2\}\}\{zL\\alpha\+2h\}=2n\\sum\_\{z=1\}^\{T/L\}\\frac\{\\left\(2\\frac\{\\sqrt\{L\}dM\}\{\\epsilon\}\+2LG\+3\\alpha LR\\right\)^\{2\}\}\{\\alpha L\(z\+2\)\}\(36\)≤4​n​\(1\+ln⁡\(T/L\)\)​\(4​d2​M2α​ϵ2\+L​\(2​G\+3​α​R\)2α\)=O​\(n​T2/3​\(log⁡T\)1/3\)\+O​\(n​L​log⁡T\)\.\\displaystyle\\leq 4n\(1\+\\ln\(T/L\)\)\\left\(\\frac\{4d^\{2\}M^\{2\}\}\{\\alpha\\epsilon^\{2\}\}\+\\frac\{L\(2G\+3\\alpha R\)^\{2\}\}\{\\alpha\}\\right\)=O\\left\(nT^\{2/3\}\(\\log T\)^\{1/3\}\\right\)\+O\\left\(nL\\log T\\right\)\.The remaining terms on the R\.H\.S of \([29](https://arxiv.org/html/2607.01665#A8.E29)\) can be bounded by

n​h​R2\+3​ϵ​n​G​T\+ϵ​n​G​R​Tr=n​α​L​R2\+\(3\+Rr\)​c​n​G​d2/3​T2/3​\(ln⁡T\)1/3\\displaystyle nhR^\{2\}\+3\\epsilon nGT\+\\frac\{\\epsilon nGRT\}\{r\}=n\\alpha LR^\{2\}\+\\left\(3\+\\frac\{R\}\{r\}\\right\)cnGd^\{2/3\}T^\{2/3\}\(\\ln T\)^\{1/3\}\(37\)=O​\(n​T2/3​\(log⁡T\)1/3\)\.\\displaystyle=O\(nT^\{2/3\}\(\\log T\)^\{1/3\}\)\.
Finally, by combining \([6](https://arxiv.org/html/2607.01665#S3.E6)\), \([34](https://arxiv.org/html/2607.01665#A8.E34)\), \([35](https://arxiv.org/html/2607.01665#A8.E35)\), \([36](https://arxiv.org/html/2607.01665#A8.E36)\) and \([37](https://arxiv.org/html/2607.01665#A8.E37)\), we can obtain

𝔼​\[RT,i\]\\displaystyle\\mathbb\{E\}\[R\_\{T,i\}\]=O​\(n​T2/3​\(log⁡T\)1/3\)\+O​\(n​L​log⁡T\)≤O​\(n​T2/3​\(log⁡T\)1/3\+n​K​log⁡T\)\.\\displaystyle=O\\left\(nT^\{2/3\}\(\\log T\)^\{1/3\}\\right\)\+O\\left\(nL\\log T\\right\)\\leq O\\left\(nT^\{2/3\}\(\\log T\)^\{1/3\}\+nK\\log T\\right\)\.

## Appendix ICompatibility with both biased and unbiased compressors

At first glance, Assumption[3\.2](https://arxiv.org/html/2607.01665#S3.Thmtheorem2)might seem designed specifically for biased compressors\. However, it is actually a general framework that can easily capture both biased and unbiased compressors\. We explain this below\.

Biased compressors\.Compressors like Top\-kksparsification are inherently biased \(𝔼​\[𝒬​\(x\)\]≠x\\mathbb\{E\}\[\\mathcal\{Q\}\(x\)\]\\neq x\)\. They directly fit Assumption[3\.2](https://arxiv.org/html/2607.01665#S3.Thmtheorem2)because they are defined by bounding the compression error\. For example, the Top\-kkoperator preserves thekkcomponents with the largest magnitudes\. Since the discardedd−kd\-kcomponents are the smallest, their sum of squares is at mostd−kd​‖x‖22\\frac\{d\-k\}\{d\}\\\|x\\\|\_\{2\}^\{2\}\. This guarantees‖𝒬​\(x\)−x‖22≤\(1−kd\)​‖x‖22\\\|\\mathcal\{Q\}\(x\)\-x\\\|\_\{2\}^\{2\}\\leq\(1\-\\frac\{k\}\{d\}\)\\\|x\\\|\_\{2\}^\{2\}\. Therefore, it naturally satisfies Assumption[3\.2](https://arxiv.org/html/2607.01665#S3.Thmtheorem2)withω=k/d\\omega=k/d\.

Unbiased compressors\.Unbiased compressors, such as QSGD or Rand\-kk, are usually defined by a bounded variance as follow

𝔼​\[𝒞​\(x\)\]\\displaystyle\\mathbb\{E\}\[\\mathcal\{C\}\(x\)\]=x,\\displaystyle=x,𝔼​\[‖𝒞​\(x\)‖22\]\\displaystyle\\mathbb\{E\}\[\\\|\\mathcal\{C\}\(x\)\\\|\_\{2\}^\{2\}\]≤ζ​‖x‖22,\\displaystyle\\leq\\zeta\\\|x\\\|\_\{2\}^\{2\},whereζ≥1\\zeta\\geq 1\. Directly calculating the compression error gives𝔼​\[‖𝒞​\(x\)−x‖22\]≤\(ζ−1\)​‖x‖22\\mathbb\{E\}\[\\\|\\mathcal\{C\}\(x\)\-x\\\|\_\{2\}^\{2\}\]\\leq\(\\zeta\-1\)\\\|x\\\|\_\{2\}^\{2\}\. Sinceζ−1\\zeta\-1can be greater than11, this does not immediately match the\(1−ω\)​‖x‖22\(1\-\\omega\)\\\|x\\\|\_\{2\}^\{2\}format in Assumption[3\.2](https://arxiv.org/html/2607.01665#S3.Thmtheorem2)\.

However, we can make unbiased compressor fit our framework perfectly by applying a simple scaling factor\[Beznosikov et al\.,[2020](https://arxiv.org/html/2607.01665#bib.bib6)\]\. We define a scaled compressor𝒬′​\(x\)=1ζ​𝒞​\(x\)\\mathcal\{Q\}^\{\\prime\}\(x\)=\\frac\{1\}\{\\zeta\}\\mathcal\{C\}\(x\)\. By calculating its expected squared error, we have

𝔼​\[‖𝒬′​\(x\)−x‖22\]\\displaystyle\\mathbb\{E\}\[\\\|\\mathcal\{Q\}^\{\\prime\}\(x\)\-x\\\|\_\{2\}^\{2\}\]=𝔼​\[‖1ζ​𝒞​\(x\)−x‖22\]\\displaystyle=\\mathbb\{E\}\\left\[\\left\\\|\\frac\{1\}\{\\zeta\}\\mathcal\{C\}\(x\)\-x\\right\\\|\_\{2\}^\{2\}\\right\]=1ζ2​𝔼​\[‖𝒞​\(x\)‖22\]−2ζ​‖x‖22\+‖x‖22\\displaystyle=\\frac\{1\}\{\\zeta^\{2\}\}\\mathbb\{E\}\[\\\|\\mathcal\{C\}\(x\)\\\|\_\{2\}^\{2\}\]\-\\frac\{2\}\{\\zeta\}\\\|x\\\|\_\{2\}^\{2\}\+\\\|x\\\|\_\{2\}^\{2\}≤\(1ζ\+1−2ζ\)​‖x‖22=\(1−1ζ\)​‖x‖22\.\\displaystyle\\leq\\left\(\\frac\{1\}\{\\zeta\}\+1\-\\frac\{2\}\{\\zeta\}\\right\)\\\|x\\\|\_\{2\}^\{2\}=\\left\(1\-\\frac\{1\}\{\\zeta\}\\right\)\\\|x\\\|\_\{2\}^\{2\}\.
This shows that the scaled compressor𝒬′​\(x\)\\mathcal\{Q\}^\{\\prime\}\(x\)perfectly satisfies Assumption[3\.2](https://arxiv.org/html/2607.01665#S3.Thmtheorem2)with a compression ratio ofω=1/ζ\\omega=1/\\zeta\. Therefore, all the theoretical results in this paper apply to unbiased compressors simply by replacingω\\omegawith1/ζ1/\\zeta\.