Distributed Online Convex Optimization with Compressed Communication: Optimal Regret and Applications
arXiv:2604.09276v1 [cs.LG] 10 Apr 2026
1
Sifan Yang1,2 , Dan-Yue Li1,2 , Lijun Zhang1,2 National Key Laboratory for Novel Software Technology, Nanjing University, Nanjing, China 2 School of Artificial Intelligence, Nanjing University, Nanjing, China {yangsf, lidy, zhanglj}@lamda.nju.edu.cn
Abstract Distributed online convex optimization (D-OCO) is a powerful paradigm for modeling distributed scenarios with streaming data. However, the communication cost between local learners and the central server is substantial in large-scale applications. To alleviate this bottleneck, we initiate the study of D-OCO with compressed communication. Firstly, to quantify the compression impact, we establish the √ Ω(δ −1/2 T ) and Ω(δ −1 log T ) lower bounds for convex and strongly convex loss functions, respectively, where δ ∈ (0, 1] is the compression ratio. Secondly, we √ propose an optimal algorithm, which enjoys regret bounds of O(δ −1/2 T ) and O(δ −1 log T ) for convex and strongly convex loss functions, respectively. Our method incorporates the error feedback mechanism into the Follow-the-RegularizedLeader framework to address the coupling between the compression error and the projection error. Furthermore, we employ the online compression strategy to mitigate the accumulated error arising from the bidirectional compression. Our online method has great generality, and can be extended to the offline stochastic setting via online-to-batch conversion. We establish convergence rates of O(δ −1/2 T −1/2 ) and O(δ −1 T −1 ) for convex and strongly convex loss functions, respectively, providing the first guarantees for distributed non-smooth optimization with compressed communication and domain constraints.
1
Introduction
Distributed online convex optimization (D-OCO) [Patel et al., 2023] is a fundamental paradigm for modeling distributed sequential decision-making problems, such as mobile keyboard predictions [Hard et al., 2018, Chen et al., 2019], self-driving vehicles [Elbir et al., 2020], recommendation systems [Shi et al., 2021, Liang et al., 2021, Khan et al., 2021], among others. Specifically, it is formulated as a repeated game between an adversary and a set of n local learners connected to a central server. At each round t ∈ [T ], each online learner plays a global decision wt from a convex set W ⊆ Rd . After the decision wt is committed, learner i suffers a local loss fit (wt ), where fit (·) : W → R is a convex function. Subsequently, learner i sends its local information to the central server, which aggregates the received data and broadcasts the global information back to all learners. Upon receiving this message, local learners synchronously update the decision wt+1 . To measure the performance of learners, we select the standard regret: T n 1 XX t t fi (w ) − fit (w⋆ ) , n t=1 i=1 P P T n where w⋆ = arg minw∈W n1 t=1 i=1 fit (w) is the best decision chosen in hindsight.
RT =
Preprint.
(1)
It is straightforward to verify that if each learner transmits its local gradient to the central server and updates the decision with the aggregated gradient from the server, the distributed setting reduces to the single-node case, and the procedure attains the optimal regret bound for single-node OCO [Shalev-Shwartz, 2012, Hazan, 2016]. In practice, however, transmitting full gradients between the learners and the server may incur substantial communication overhead, limiting the applicability of this approach in large-scale distributed problems. To alleviate this bottleneck in D-OCO, we conduct the first investigation of communication-efficient D-OCO, where learners and the server exchange compressed messages. We note that prior works have explored compressed communication in decentralized online convex optimization [Tu et al., 2022, Cao and Bacsar, 2023, Yang et al., 2026], but their methods are tailored for peer-to-peer topologies. Consequently, they are incompatible with our distributed setting due to the fundamental differences in network architecture. Naively using the compressed gradients, e.g., updating with the sign of the gradients, may result in the unbounded accumulation of the compression error, which prevents convergence even in the offline optimization [Karimireddy et al., 2019]. To address this issue, the error feedback (EF) mechanism [Seide et al., 2014] is widely adopted to control the compression error in unconstrained settings [Alistarh et al., 2018, Karimireddy et al., 2019, Stich and Karimireddy, 2020, Richtárik et al., 2021, Huang et al., 2022]. At each round, EF records the accumulated error of the past compression steps and compresses the sum of the error and gradient, effectively bounding the total compression error over time. However, a critical challenge arises when extending the existing EF-based optimization methods to the distributed settings with domain constraints. Since each learner must project its decision onto the feasible domain per update, it results in an additional projection error, which couples with the compression error and leads to unbounded error accumulation. Unlike unconstrained optimization where EF alone suffices to control the compression error, the coupled error in constrained settings necessitates novel techniques for effective handling. In this paper, we first develop Distributed Follow-the-Compressed-Leader (D-FTCL), which applies EF on both learner and server sides to enable bidirectional compressed communication. More importantly, D-FTCL adapts EF to the Follow-the-Regularized-Leader (FTRL) framework [Hazan, 2016, Orabona, 2019], which ensures that the projection error does not propagate to subsequent compression steps, thereby decoupling the projection error from the compression error. D-FTCL enjoys regret √ bounds of O(δ −1 T ) and O(δ −2 log T ) for convex and strongly convex loss functions, respectively, where δ ∈ (0, 1] denotes the compression ratio that characterizes the quality of compression and δ = 1 means√no compression. Furthermore, to quantify the impact of compression, we establish the Ω(δ −1/2 T ) and Ω(δ −1 log T ) lower bounds for convex and strongly convex loss functions, respectively. Thus, while D-FTCL successfully achieves efficient communication, there exists a gap between its regret guarantees and the lower bounds. This prompts a natural question: is it possible to further improve the regret bound of D-FTCL? Through careful analysis, we find that the bidirectional compression in D-FTCL introduces the amplified compression error, which results in suboptimal regret bounds. Motivated by previous work [Huang et al., 2022, Yang et al., 2026], we employ the online compression strategy to reduce the compression error, which recursively compresses the residual for multiple rounds. However, since the online compression strategy leverages the blocking update mechanism to ensure the communication round remains 1 per update, the communication between the local learners and the server becomes asynchronous due to transmission latency. To tackle this issue, we rigorously characterize the deviation caused by the delayed updates in the analysis. Our method, named √ Distributed Follow-theFast-Compressed-Leader (D-FTFCL), enhances the regret bounds to O(δ −1/2 T ) and O(δ −1 log T ) for convex and strongly convex loss functions, respectively, thereby achieving optimal regret bounds for D-OCO with compressed communication. Our online methods have broad applicability, and thus can be extended to the distributed offline stochastic convex optimization with domain constraints. Previous work on distributed offline optimization with compressed communication typically assumes either smooth loss functions or an unconstrained optimization domain [Karimireddy et al., 2019, Richtárik et al., 2021, Huang et al., 2022, Gao et al., 2024, Islamov et al., 2025]. Consequently, the problem of distributed convex non-smooth optimization under domain constraints remains unsolved. To bridge this gap, we develop a distributed variant of anytime online-to-batch conversion [Cutkosky, 2019] and integrate our online method into this framework. Our proposed algorithm obtains a last-iterate convergence rate of O(δ −1/2 T −1/2 ) for convex loss functions, matching the lower bound established by Islamov et al.
2
[2025]. For strongly convex loss functions, we establish a faster rate of O δ −1 T −1 , which is optimal with respect to T [Agarwal et al., 2012]. To the best of our knowledge, these are the first guarantees for distributed convex non-smooth optimization with compressed communication and domain constraints.
2
Related Work
In this section, we briefly review the related work on distributed offline optimization and distributed online convex optimization. 2.1
Distributed Offline Optimization
Distributed offline optimization has attracted significant attention in the past decades due to its wide applicability in distributed machine learning tasks [Nedić and Ozdaglar, 2009, Dean et al., 2012, Yuan et al., 2016, Tang et al., 2018, Swenson et al., 2022]. Although prior distributed algorithms have established solid theoretical guarantees, the massive information exchange between local learners and the central server may result in a critical communication bottleneck, particularly in high-dimensional and large-scale scenarios. To alleviate communication overhead, extensive research has integrated compression mechanisms into distributed offline optimization algorithms [Seide et al., 2014, Stich et al., 2018, Bernstein et al., 2018, Karimireddy et al., 2019, Huang et al., 2022, Islamov et al., 2025]. Rather than broadcasting the full vector x ∈ Rd , they transmit compressed data C(x), where C(·) : Rd → Rd is an operator designed for efficient transmission. A quintessential example is the sign operator, which outputs the sign of each coordinate, thereby significantly reducing the communication cost. To mitigate errors induced by the sign compressor, Seide et al. [2014] pioneer the error feedback (EF) mechanism, which tracks the past compression error and compresses the sum of the error and the gradient, though they do not provide theoretical guarantees. Subsequently, Karimireddy et al. [2019] provide a unified theoretical framework for EF with general compressors. However, their analysis is limited to unidirectional compression. To achieve bidirectional compression, Stich [2020] and Beznosikov et al. [2023] provide the analysis for EF under the distributed setting. In recent years, Richtárik et al. [2021] introduce a novel error feedback technique, termed EF21, which compresses the residual of the transmitted data and the gradient. To further mitigate the compression error, Huang et al. [2022] design the fast compressed communication (FCC), which recursively applies the standard compressor for multiple rounds. By utilizing FCC, they establish the nearly optimal convergence rates for non-convex smooth loss functions. Despite the extensive research on incorporating EF into the offline optimization, existing methods typically require the loss function to be smooth or the feasible domain to be unconstrained [Seide et al., 2014, Stich et al., 2018, Karimireddy et al., 2019, Richtárik et al., 2021, Huang et al., 2022]. The only work that addresses offline distributed convex non-smooth optimization is Islamov et al. [2025], which investigates the safe constraint setting. They establish a convergence rate of O(δ −1 T −1/2 ), and a lower bound of Ω(δ −1/2 T −1/2 ) for unconstrained optimization. However, their method relies on the specific structure of safe constraints and fails to cover domain constraints. Although Islamov et al. [2025] further provide an analysis for EF21 in the convex smooth setting with domain constraints, they assume smooth loss functions and are restricted to unidirectional compression. It still remains an open problem whether EF is effective for convex non-smooth optimization with domain constraints. 2.2
Distributed Online Convex Optimization
To address the distributed optimization with streaming data, Patel et al. [2023] investigate distributed online convex optimization (D-OCO), where the loss function is time-varying and the learners have to continuously update decisions to minimize the cumulative regret. They con Pn PT 1 ′ t t t ⋆ ⋆ sider a different regret defined as RT = n i=1 = t=1 fi (wi ) − fi (w ) , where w P P T n 1 t ′ arg minw∈W n t=1 i=1 fi (w). RT measures the performance of each learner by using the local loss functions. As noted by Patel et al. [2023], communication offers no benefit because learners can independently execute OGD [Zinkevich, 2003] to achieve the optimal regret bound without any information exchange. In contrast, the regret defined in (1) evaluates the performance of the decision 3
against the global loss. This regret is more realistic for distributed learning tasks, where the ultimate goal is to train a consensus model. Moreover, when loss functions are fixed over rounds, our regret coincides with the offline optimization objective. Furthermore, they pivot to the bandit feedback setting, where the local learners can only access values of the loss functions [Agarwal et al., 2010, Shamir, 2017]. In this regime, they demonstrate that collaboration helps to achieve tighter regret bounds. We also notice a parallel line of research investigating decentralized online convex optimization, where local learners interact over a network modeled by an undirected graph [Yan et al., 2012, Hosseini et al., 2013, Zhang et al., 2017b, Wan et al., 2020, 2022, Wang et al., 2023, Wan et al., 2024, 2025, Wan, 2025]. To reduce the communication cost among learners, recent efforts have further explored compressed communication within this setting [Tu et al., 2022, Cao and Bacsar, 2023, Yang et al., 2026]. However, in decentralized settings, each learner maintains an individual local decision and communicates in a peer-to-peer scheme without a central server for aggregation. This architecture fundamentally differs from the distributed setting we consider. Consequently, algorithms tailored for peer-to-peer topologies cannot be directly extended to our setting due to intrinsic differences in communication protocols and network structures.
3
Preliminaries
In this section, we present necessary preliminaries including assumptions, definitions, and techniques used in this paper. Similar to previous studies on single-node OCO, we introduce the following standard assumptions [Hazan, 2016, Orabona, 2019]. Assumption 3.1 (convexity). The loss function fit (·) of each learner i ∈ [n] is convex over the feasible domain W. Assumption 3.2 (strong convexity). The loss function fit (·) of each learner i ∈ [n] is µ-strongly convex over the domain W, i.e., it holds that fit (y) ≥ fit (x) + ⟨∇fit (x), y − x⟩ + µ2 ∥y − x∥2 , for ∀x, y ∈ W. Assumption 3.3 (bounded gradient norm). The gradient of function fit (·) of each learner i ∈ is bounded by G over the domain W, i.e., it holds that ∥∇fit (w)∥ ≤ G, for ∀w ∈ W and [n] P n 1 t i=1 ∇fi (w) ≤ G, for ∀w ∈ W n Assumption 3.4 (bounded domain). The convex set W contains the origin 0, i.e., 0 ∈ W, and it is bounded by D, i.e., it holds that ∥x − y∥ ≤ D, for ∀x, y ∈ W. Next, we introduce a common assumption governing the communication process in our distributed setting. Assumption 3.5 (communication protocol). At each round, each learner i and the central server are allowed to communicate with each other exactly once. A compressor C(·) : Rd → Rd is a mapping whose output can be efficiently transmitted. In this paper, we consider a general class of compressors with the following definition [Koloskova et al., 2019]. Definition 3.6 (compressor). A compressor C(·) : Rd → Rd is called δ-contractive if the following holds h i 2 2 EC ∥C(x) − x∥ ≤ (1 − δ) ∥x∥ , ∀x ∈ Rd , for some δ ∈ (0, 1], where the expectation EC [·] is taken over the randomness of the compressor. To mitigate the error of compressors, Huang et al. [2022] design the fast compressed communication (FCC), as summarized in Algorithm 1. The core idea is to recursively apply the standard compressor for L rounds and transmit the compressed data at each round, which involves L rounds of communication. When L = 1, FCC degenerates to the standard compressor. We state the following lemma to provide the guarantee of FCC. Lemma 3.7 (Lemma 2 in Huang et al. [2022]). Given a δ-contractive compressor C(·) and for any compression rounds L ≥ 1, Algorithm 1 ensures h i 2 2 EC rL+1 − x ≤ (1 − δ)L ∥x∥ , ∀x ∈ Rd . 4
Algorithm 1 FCC(x, C(·), L, receiver) 1: Input: data x, compressor C(·), compression round L, receiver 2: Initialize r1 = 0 3: for k = 1 to L do 4: Send ck = C(x − rk ) to the receiver 5: Calculate rk+1 = rk + ck 6: end for 7: Return rL+1
Lemma 3.7 demonstrates that the error in FCC decreases exponentially as L grows, but such a result is achieved at the expense of L communication rounds..
4
Main Results
In this section, we first present an efficient algorithm for D-OCO with compressed communication, as well as the corresponding theoretical guarantees. Then, we derive the lower bounds for D-OCO with compressed communication. Finally, we develop an improved method that achieves the optimal regret bounds. 4.1
Follow-the-Compressed-Leader
Before presenting our algorithms, we briefly highlight the key challenges in applying EF mechanism to optimization problems with constrained domains. In the single-node unconstrained setting, the learner initializes e1 = 0 to track compression errors across iterations and performs the update under the gradient descent framework: et+1 = et + gt − C(et + gt ) wt+1 = wt − ηC(et + gt ), where gt is the gradient at round t and η is the learning rate. Let ŵt+1 denote the sequence obtained using the exact gradient, i.e., ŵt+1 = ŵt − ηgt . EF ensures the deviation remains bounded: EC wt − ŵt ≤ EC η et ≤ O(δ −1 η). (2) Consequently, by selecting an appropriate learning rate η, the compression error can be effectively controlled, ensuring that the algorithm converges despite the effect induced by compression. However, applying EF to D-OCO encounters a critical issue due to the coupling of the compression error and the projection error. Specifically, since each learner has to project its decision onto the feasible domain, i.e., wt+1 = ΠW wt − ηC(et + gt ) , (3) it incurs an additional projection error and the projection error will propagate to all subsequent compression steps, thereby invalidating the guarantee in (2). This interaction between projection and compression causes the total error to become uncontrollable. To address the aforementioned limitation, we develop D-FTCL by integrating EF into the Follow-TheRegularized-Leader (FTRL) framework [Hazan et al., 2007, Hazan, 2016] to decouple the projection error from the compression error, as summarized in Algorithm 2. Additionally, we employ the EF mechanism on both learner and server sides to achieve bidirectional compression. Specifically, at each round t, the learner i plays the global decision wt and observes the gradient git . Then it broadcasts the compressed message vit = C(eti + git ) to the server and updates et+1 = eti + git − C(eti + git ). i Upon receiving all messages from the learners, the server computes the aggregate information Pn vt = n1 i=1 vit . Next, it transmits st = C(êt +vt ) back to learners and updates êt+1 = êt +vt −st . In contrast to previous methods that update within the gradient descent framework, each learner updates the decision as follows: * t + X 1 2 t+1 k w = arg min s , w + ∥w∥ . (4) w∈W η k=1
5
Algorithm 2 Distributed Follow-the-Compressed-Leader (D-FTCL) Require: learning rate η, compressor C(·) 1: Initialize w1 = 0, ê1 = 0 and e1i = 0, ∀i ∈ [n] 2: for t = 1, . . . , T do 3: for each learner i = 1, . . . , n in parallel 4: Play the decision wt and receive gradient git 5: Send vit = C(eti + git ) to server and compute et+1 = eti + git − vit i 6: for server do Pn 7: Compute vt = n1 i=1 vit and send st = C(êt + vt ) to all learners 8: Compute êt+1 = êt + vt − st 9: for each learner i = 1, . . . , n in parallel 10: Update the decision wt+1 according to (4) or (5) 11: end for
Since the decision wt+1 is updated with the historical compressed information, the projection error is confined to the current update step. Thus, we can prevent the error from accumulating across rounds, thereby successfully avoiding the coupling between the compression error and the projection error. If the loss function is µ-strongly convex, each learner updates the decision according to: * t + t X µX 2 w − wk . wt+1 = arg min sk , w + (5) w∈W 2 k=1
k=1
In the following, we establish the guarantees for D-FTCL. √ , Theorem 4.1. Under the Assumptions 3.1, 3.3 and 3.4, by setting the learning rate η = GδD T Algorithm 2 ensures √ EC [RT ] ≤ O(δ −1 DG T ).
Theorem 4.2. Under the Assumptions 3.2, 3.3 and 3.4, Algorithm 2 ensures EC [RT ] ≤ O µ−1 δ −2 (G + µD)2 log T . √ Remark 4.3. Our algorithm achieves the O(δ −1 T ) and O δ −2 log T regret bounds for convex and µ-strongly convex loss functions, respectively, which are the first theoretical guarantees for D-OCO with compressed communication and domain constraints. 4.2
Lower Bounds
To verify the optimality of our proposed method, we establish the lower bounds for D-OCO with compressed communication. To derive lower bounds for D-OCO with compressed communication, the key challenge is characterizing the effect of compression. Inspired by Huang et al. [2022], we model the compressor as probabilistic communication failure, where transmitted information may not reach its destination at some rounds. We assume learners communicate exclusively with the central server and operate synchronously, ensuring all learners maintain identical decision. Since we focus on the online setting, distinct from the construction in Huang et al. [2022], we adopt the randomized gossip compressor C(·) : Rd → Rd [Koloskova et al., 2019], which outputs C(x) = x with probability δ and C(x) = 0 otherwise. Thus, each learner successfully transmits information to the server with probability δ per round, implying that the expected number of rounds for a successful transmission is ⌈1/δ⌉. In this way, we can characterize the effect of compression by analyzing the regret degradation caused by the intermittent communication. We formally state the lower bounds in the following theorems. √ , D √ ]d For any D-OCO algorithm, if T ≥ Theorem 4.4. Given the feasible domain W = [ 2−D d 2 d (1 − δ)/δ, there exists a sequence of convex loss functions satisfying Assumption 3.3 and a compressor satisfying Definition 3.6 such that √ DG T √ . EC [RT ] ≥ 23 δ
6
Algorithm 3 Distributed Follow-the-Fast-Compressed-Leader (D-FTFCL) Require: learning rate η, compressor C(·), block size L 1: Initialize w1 = 0, ê1 = 0 and e1i = 0, ∀i ∈ [n] 2: for b = 1, . . . , T /L do 3: for each learner i = 1, . . . , n in parallel 4: for t = (b − 1)L + 1, . . . , bL do 5: Play the decision wb and receive gradient git 6: end for PbL 7: Compute zbi = t=(b−1)L+1 git 8: if b ≥ 2 do 9: vib−1 = FCC(eb−1 + zb−1 , C(·), L, server) ▷ Transmission distributed over L rounds i i b−1 b 10: Compute ei = ei + zb−1 − vib−1 i 11: for server and if b ≥ 3 P do n 12: Compute vb−2 = n1 i=1 vib−2 ▷ Only receive gradients of block b − 2 b−2 b−2 b−2 13: s =FCC(v + ê , C(·), L, learner) ▷ Transmission distributed over L rounds 14: Compute êb−1 = êb−2 + vb−2 − sb−2 15: for each learner i = 1, . . . , n in parallel and if b ≥ 3 do 16: Update the decision wb+1 according to (6) or (7) 17: end for Theorem 4.5. Given the feasible domain W = [0, √Dd ]d For any D-OCO algorithm, if T ≥ (16+δ)/δ, there exists a sequence of µ-strongly convex loss functions satisfying Assumption 3.3 and a compressor satisfying Definition 3.6 such that EC [RT ] ≥
µD2 (log16 (15δT ) − 2) . 218 δ
√ Remark 4.6. We establish Ω(δ −1/2 T ) and Ω(δ −1 log T ) lower bounds for convex and strongly convex loss functions, respectively. When there is no compression (δ = 1), our results recover the classical lower bounds for single-node OCO [Abernethy et al., 2008, Hazan and Kale, 2014]. Remark 4.7. One might notice that the dependence on the compression ratio δ of upper bounds in Theorems 4.1 and 4.2 does not match the lower bounds. Therefore, a natural question arises: is it possible to further improve the upper bounds? We provide an affirmative answer by developing an improved algorithm in the next section. 4.3
Our Improved Algorithm
Through careful analysis, we find that the suboptimal regret bounds are primarily caused by the bidirectional compression scheme. The server re-compresses the aggregated messages that have already been compressed by learners, leading to an amplification of the compression error. In fact, if we apply the unidirectional compression, D-FTCL can obtain the optimal regret bounds with the detailed proof provided in Appendix B.9. Thus, to reduce the regret of D-FTCL, we need to control the error caused by compression. In offline optimization, Huang et al. [2022] design the fast compressed communication (FCC) to reduce the compression error, which recursively compresses the residual over L rounds. This multi-round approach is not allowed in the online setting, where learners must update their decisions instantaneously to cope with streaming data. To resolve this dilemma, we utilize the online compression strategy [Yang et al., 2026]. By dividing the total T rounds into blocks of size L and updating the decision only at the end of each block, we can effectively distribute the communication cost of each update over the entire block. At round t ∈ [(b − 1)L + 1, bL] within the b-th block, each learner i plays the fixed decision wb and receives gradient git . Simultaneously, it transmits the compressed information to the server by performing FCC. Then it updates the local error ebi . The server collects the aggregated information at the end of block b. In the subsequent block, server applies the EF and employs online compression strategy to disseminate the compressed information back to the learners. However, the block-wise transmission mechanism inherently introduces new challenges: since transmitting information between learners and the server requires L rounds, the communication 7
inevitably becomes asynchronous due to transmission latency. In particular, after learners send compressed information to the server through L rounds, it takes another L rounds for transmitting back the aggregated message. As a result, learner i only receives the compressed information sb−2 of block b − 2 at the end of block b. Reflecting the information lag, the learners update the decision using only the available information up to block b − 2: * b−2 + X 1 2 b+1 k w = arg min s , w + ∥w∥ . (6) w∈W η k=1
If the loss is µ-strongly convex, learners update as follows: * b−2 + b X µL X 2 b+1 k w − wk . w = arg min s ,w + w∈W 2 k=1
(7)
k=1
For the sake of clarity, we present a simplified version of our algorithm, termed Distributed Followthe-Fast-Compressed-Leader (D-FTFCL), in Algorithm 3, with the comprehensive details provided in Appendix B.5. The asynchronous updates pose challenges to the theoretical analysis. To address this, we explicitly characterize the impact of the delayed updates. In the following, we establish the guarantees for D-FTFCL. Theorem 4.8. Under the Assumptions 3.1, 3.3 and 3.4, by setting the learning rate η = G√DLT and the block size L = ⌈ 1δ ⌉, Algorithm 3 can ensure √ EC [RT ] ≤ O(δ −1/2 DG T ). Theorem 4.9. Under the Assumptions 3.2, 3.3 and 3.4, by setting the block size L = ⌈ 1δ ⌉, Algorithm 3 can ensure EC [RT ] ≤ O µ−1 δ −1 (G + µD)2 log T . √ Remark 4.10. Our improved algorithm enjoys O(δ −1/2 T ) and O δ −1 log T regret bounds for convex and strongly convex loss functions, which match the lower bounds in Theorems 4.4 and 4.5. Remark 4.11. Our theoretical guarantees require setting the block size to L = ⌈1/δ⌉ to adequately suppress the compression error. It is worth noting that this choice is derived from the worst-case analysis. In practice, we can employ a smaller L in real-world implementations.
5
Application to Distributed Stochastic Convex Optimization
In this section, we extend our online algorithm to distributed stochastic convex non-smooth optimization with domain constraints. Formally, we consider the following offline distributed optimization problem [Nedić and Ozdaglar, 2009] n
min f (x) =
x∈W
1X fi (x), n i=1
(8)
where fi (·) : W → R is the loss function of the learner i. Here, learners are assumed to have access solely to stochastic estimates of the function value fi (·; ξi ) and the local subgradient with sample ξi from distribution Di . Following the previous work [Cutkosky, 2019], we introduce the standard assumption outlined below. Assumption 5.1 (stochastic subgradient). The stochastic subgradient git of function fi (·) with 2 random sample ξit at point xt satisfies E[git ] ∈ ∂fi (xt ) and ∥git ∥ ≤ G2 . As discussed in Section 2.1, existing studies on distributed optimization typically assume either smooth loss functions or an unconstrained optimization domain. There still remains a critical gap: no work has addressed distributed non-smooth optimization with compressed communication and domain constraints, despite its extensive applications in machine learning tasks [Agarwal et al., 2006, Hazan, 2016]. While a recent work by Islamov et al. [2025] investigates convex non-smooth optimization, it is limited to the specific setting of safe constraints. Crucially, their methods cannot handle standard domain constraints. Hence, a fundamental question arises: is it possible to design an algorithm for distributed optimization with compressed communication and domain constraints? 8
Algorithm 4 Distributed O2B Conversion with Compressed Communication Require: Online method A, weights α1 , . . . , αT /L , compression round L, communication round T 1: Initialize w1 = 0, A as Algorithm 2, compressor as Algorithm 1 2: for t = 1 to T /L do 3: for each learner i = 1, ..., n inPparallel do t αk wk 4: Compute the decision xt = k=1 α1:t 5: Query subgradient git at xt 6: Construct the surrogate loss ℓ̂ti (w) according to (9) or (10) 7: Send ℓ̂ti (w) to A as t-th loss 8: Receive the updated decision wt+1 from A 9: end for 10: end for We provide an affirmative answer for this question by extending our online methods to offline stochastic optimization. An effective approach to solving the stochastic convex optimization problem is to leverage online learning algorithms through the anytime online-to-batch (O2B) conversion [Cesa-Bianchi et al., 2004, Shalev-Shwartz, 2012, Cutkosky, 2019], which constructs a sequence of surrogate loss functions using stochastic gradients and applies online learning algorithms to generate decisions. By minimizing the regret, we can achieve the optimal convergence rates for stochastic convex optimization problem. In this work, we propose a distributed variant of the anytime O2B conversion [Cutkosky, 2019], as summarized in Algorithm 41 . To mitigate the compression error in bidirectional compression, we again adopt the FCC technique [Huang et al., 2022]. A key distinction from the online setting is that local learners can communicate with the central server multiple times per update in the offline setting, it eliminates the need for the blocking update technique. Consequently, in the anytime O2B conversion, we can employ our D-FTCL (Algorithm 2) as the online method A and directly replace the standard compressor C(·) with the FCC mechanism (Algorithm 1). At each round t, each learner P t
α wk
k computes a weighted average decision xt = k=1 α1:t Then, it constructs the surrogate loss according to:
and queries the local subgradient git at xt .
ℓ̂ti (w) = ⟨αt git , w⟩,
(9)
and feeds it to D-FTCL as the t-th loss function. Then, the online method updates the decision according to (4). Let T denote the total number of communication rounds. Since the FCC mechanism requires L rounds per update, each learner only performs K = T /L updates. We now establish the last-iterate convergence rates for Algorithm 4. Theorem 5.2. Under the Assumptions 3.1, 3.4 and 5.1, configured with the online method A as Algorithm 2, the compression method as Algorithm 1, αt = 1, ℓ̂ti (w) according to (9), wt+1 according D and compression round L = ⌈1/δ⌉, for all x ∈ W, Algorithm 4 can ensure to (4), η = G√ K DG EC f (xK ) − f (x) ≤ O √ , δT where T = KL is the total communication round. It is not hard to verify that applying the uniform weighting scheme (αt = 1) to strongly convex functions only yields a convergence rate of O(δ −1 T −1 log T ), which is suboptimal with respect to T . Benefiting from the flexibility of the anytime O2B conversion, we can employ time-varying weights with αt = t and construct the surrogate loss as: µαt 2 ℓ̂ti (w) = ⟨αt git , w⟩ + w − xt . (10) 2 Online method receives the subgradient αt git and updates the decision according to: * t + t X µX 2 αk w − xk . (11) wt+1 = arg min sk , w + w∈W 2 k=1
1 Given sequences of weights {α } , we use α t t 1:t =
k=1
Pt
k=1 αk to represent their summation.
9
Theorem 5.3. Under the Assumptions 3.2, 3.4 and 5.1, configured with the online method A as Algorithm 2, the compression method as Algorithm 1, αt = t, ℓ̂ti (w) according to (10), wt+1 according to (11) and compression round L = ⌈1/δ⌉, for all x ∈ W, Algorithm 4 can ensure (µD + G)2 EC f (xK ) − f (x) ≤ O , µδT where T = KL is the total communication round. Remark 5.4. Islamov et al. [2025] establish a lower bound of Ω(δ −1/2 T −1/2 ) for distributed convex non-smooth optimization in the unconstrained setting, where T is the communication round. Our rate of O(δ −1/2 T −1/2 ) for convex objectives matches this lower bound. Furthermore, in the absence of domain and safety constraints, our method still achieves a more favorable rate than that of Islamov et al. [2025], demonstrating the inherent efficiency of our algorithmic design. For µ-strongly convex functions, our method achieves a convergence rate of O(δ −1 T −1 ), which is optimal with respect to T Agarwal et al. [2012]. Crucially, our results fill a significant gap in the literature by establishing the first convergence guarantees for distributed convex non-smooth optimization with compressed communication under domain constraints. Remark 5.5. In recent years, there have been interests of investigating the sign-based methods Seide et al. [2014], Koloskova et al. [2019], Jiang et al. [2024], which are advantageous in distributed settings for low communication overhead. If we adopt the (scaled) sign compressor (δ = 1/d) Karimireddy et al. [2019], our method achieves rates of O(d1/2 T −1/2 ) and O(dT −1 ) for convex and strongly convex functions, respectively.
6
Conclusion and Future Work
In this paper, we study distributed online convex optimization (D-OCO) with compressed communication.√ Firstly, we propose a communication-efficient method that achieves the regret bounds of O(δ −1/2 T ) and O(δ −1 log T ) for convex and strongly convex loss functions, respectively. √ Sec−1/2 ondly, to certify the optimality of our algorithm, we establish lower bounds of Ω(δ T ) and Ω(δ −1 log T ) for convex and strongly convex loss functions, respectively. Finally, we extend our online methods to distributed offline stochastic optimization with domain constraints. We obtain the first convergence rates for both convex and strongly convex non-smooth objectives by developing a distributed anytime online-to-batch conversion. A promising direction for future work is to investigate whether our method can achieve tighter results for smooth loss functions. It is well-known that optimistic online learning methods [Rakhlin and Sridharan, 2013, Mohri and Yang, 2016] can leverage prior knowledge to construct optimistic terms and exploit smoothness to obtain better bounds. However, achieving such improvements in D-OCO with compressed communication presents significant technical challenges. Since each learner receives only compressed information at each round, the compressed gradients alone are insufficient to construct effective optimistic terms.
References Jacob Abernethy, Peter L. Bartlett, Alexander Rakhlin, and Ambuj Tewari. Optimal strategies and minimax lower bounds for online convex games. In Proceedings of the 21st Annual Conference on Learning Theory (COLT), pages 415–423, 2008. Alekh Agarwal, Ofer Dekel, and Lin Xiao. Optimal algorithms for online convex optimization with multi-point bandit feedback. In Proceedings of the 23rd Conference on Learning Theory (COLT), pages 28–40, 2010. Alekh Agarwal, Peter L. Bartlett, Pradeep D. Ravikumar, and Martin J. Wainwright. Informationtheoretic lower bounds on the oracle complexity of stochastic convex optimization. IEEE Transactions on Information Theory, 58(5):3235–3249, 2012. Amit Agarwal, Elad Hazan, Satyen Kale, and Robert E. Schapire. Algorithms for portfolio management based on the newton method. In Proceedings of the 23rd International Conference on Machine Learning (ICML), 2006. 10
Dan Alistarh, Torsten Hoefler, Mikael Johansson, Nikola Konstantinov, Sarit Khirirat, and Cedric Renggli. The convergence of sparsified gradient methods. In Advances in Neural Information Processing Systems 31 (NeurIPS), 2018. Jeremy Bernstein, Yu-Xiang Wang, Kamyar Azizzadenesheli, and Animashree Anandkumar. signSGD: Compressed optimisation for non-convex problems. In Proceedings of the 35th International Conference on Machine Learning (ICML), pages 560–569, 2018. Aleksandr Beznosikov, Samuel Horváth, Peter Richtárik, and Mher Safaryan. On biased compression for distributed learning. Journal of Machine Learning Research, pages 1–50, 2023. Xuanyu Cao and Tamer Bacsar. Decentralized online convex optimization with compressed communications. Automatica, 156:111186, 2023. Nicolò Cesa-Bianchi, Alex Conconi, and Claudio Gentile. On the generalization ability of on-line learning algorithms. IEEE Transactions on Information Theory, 50(9):2050–2057, 2004. Mingqing Chen, Rajiv Mathews, Tom Ouyang, and Francoise Beaufays. Federated learning of out-of-vocabulary words. arXiv preprint arXiv:1903.10635, 2019. Ashok Cutkosky. Anytime online-to-batch, optimism and acceleration. In Proceedings of the 36th International Conference on Machine Learning (ICML), pages 1446–1454, 2019. Jeffrey Dean, Greg S. Corrado, Rajat Monga, Kai Chen, Matthieu Devin, Quoc V. Le, Mark Z. Mao, Marc’Aurelio Ranzato, Andrew W. Senior, Paul A. Tucker, Ke Yang, and Andrew Y. Ng. Large scale distributed deep networks. In Advances in Neural Information Processing Systems 25 (NIPS), 2012. John C. Duchi, Alekh Agarwal, and Martin J. Wainwright. Dual averaging for distributed optimization: Convergence analysis and network scaling. IEEE Transactions on Automatic Control, pages 592– 606, 2011. Ahmet M. Elbir, Burak Soner, and Sinem Coleri. Federated learning in vehicular networks. arXiv preprint arXiv:2006.01412, 2020. Yuan Gao, Rustem Islamov, and Sebastian U. Stich. Econtrol: Fast distributed optimization with compression and error control. In Proceedings of the 12nd International Conference on Learning Representations (ICLR), 2024. Dan Garber and Elad Hazan. A linearly convergent conditional gradient algorithm with applications to online and stochastic optimization. SIAM Journal on Optimization, pages 1493–1528, 2016. Andrew Hard, Kanishka Rao, Rajiv Mathews, Swaroop Ramaswamy, Francoise Beaufays, Sean Augenstein, Hubert Eichner, Chloé Kiddon, and Daniel Ramage. Federated learning for mobile keyboard prediction. arXiv preprint arXiv:1811.03604, 2018. Elad Hazan. Introduction to online convex optimization. Foundations and Trends in Optimization, 2 (3-4):157–325, 2016. Elad Hazan and Satyen Kale. Projection-free online learning. In Proceedings of the 29th International Conference on Machine Learning (ICML), pages 1843–1850, 2012. Elad Hazan and Satyen Kale. Beyond the regret minimization barrier: Optimal algorithms for stochastic strongly-convex optimization. Journal of Machine Learning Research, 15(71):2489– 2512, 2014. Elad Hazan, Amit Agarwal, and Satyen Kale. Logarithmic regret algorithms for online convex optimization. Machine Learning, 69(2):169–192, 2007. 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. Xinmeng Huang, Yiming Chen, Wotao Yin, and Kun Yuan. Lower bounds and nearly optimal algorithms in distributed learning with communication compression. Advances in Neural Information Processing Systems 35 (NeurIPS), 35:18955–18969, 2022. 11
Rustem Islamov, Yarden As, and Ilyas Fatkhullin. Safe-ef: Error feedback for nonsmooth constrained optimization. In Proceedings of the 42nd International Conference on Machine Learning (ICML), pages 26542–26585, 2025. Peng Jiang and Gagan Agrawal. A linear speedup analysis of distributed deep learning with sparse and quantized communication. Advances in neural information processing systems 31 (NeurIPS), 2018. Wei Jiang, Sifan Yang, Wenhao Yang, and Lijun Zhang. Efficient sign-based optimization: Accelerating convergence via variance reduction. In Advances in Neural Information Processing Systems 37 (NeurIPS), pages 33891–33932, 2024. Sai Praneeth Karimireddy, Quentin Rebjock, Sebastian Stich, and Martin Jaggi. Error feedback fixes signsgd and other gradient compression schemes. In Proceedings of the 36th International Conference on Machine Learning (ICML), pages 3252–3261, 2019. Farwa K. Khan, Adrian Flanagan, Kuan Eeik Tan, Zareen Alamgir, and Muhammad Ammad-Ud-Din. A payload optimization method for federated recommender systems. In Proceedings of the 15th ACM Conference on Recommender Systems, pages 432–442, 2021. Anastasia Koloskova, Sebastian Stich, and Martin Jaggi. Decentralized stochastic optimization and gossip algorithms with compressed communication. In Proceedings of the 36th International Conference on Machine Learning (ICML), pages 3478–3487, 2019. Feng Liang, Weike Pan, and Zhong Ming. Fedrec++: Lossless federated recommendation with explicit feedback. In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI), pages 4224–4231, 2021. Mehryar Mohri and Scott Yang. Accelerating online convex optimization via adaptive prediction. In Proceedings of the 19th International Conference on Artificial Intelligence and Statistics (AISTATS), pages 848–856, 2016. Angelia Nedić and Asuman Ozdaglar. Distributed subgradient methods for multi-agent optimization. IEEE Transactions on Automatic Control, 54(1):48–61, 2009. Francesco Orabona. A modern introduction to online learning. arXiv preprint arXiv:1912.13213, 2019. Kumar Kshitij Patel, Lingxiao Wang, Aadirupa Saha, and Nathan Srebro. Federated online and bandit convex optimization. In Proceedings of the 40th International Conference on Machine Learning (ICML), pages 27439–27460, 2023. Alexander Rakhlin and Karthik Sridharan. Online learning with predictable sequences. In Proceedings of the 26th Conference on Learning Theory (COLT), pages 993–1019, 2013. Peter Richtárik, Igor Sokolov, and Ilyas Fatkhullin. Ef21: A new, simpler, theoretically better, and practically faster error feedback. In Advances in Neural Information Processing Systems 34 (NeurIPS), pages 4384–4396, 2021. Peter Richtárik, Igor Sokolov, Elnur Gasanov, Ilyas Fatkhullin, Zhize Li, and Eduard Gorbunov. 3pc: Three point compressors for communication-efficient distributed training and a better theory for lazy aggregation. In Proceedings of the 39th International Conference on Machine Learning (ICML), pages 18596–18648, 2022. 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 Conference of the International Speech Communication Association, pages 1058–1062, 2014. Shai Shalev-Shwartz. Online learning and online convex optimization. Foundations and Trends in Machine Learning, 4(2):107–194, 2012. Ohad Shamir. An optimal algorithm for bandit and zero-order convex optimization with two-point feedback. Journal of Machine Learning Research, 18(52):1703–1713, 2017. 12
Chengshuai Shi, Cong Shen, and Jing Yang. Federated multi-armed bandits with personalization. In Proceedings of the 24th International Conference on Artificial Intelligence and Statistics (AISTATS), pages 2917–2925, 2021. Sebastian U. Stich. On communication compression for distributed optimization on heterogeneous data. arXiv preprint arXiv:2009.02388, 2020. Sebastian U. Stich and Sai Praneeth Karimireddy. The error-feedback framework: Better rates for sgd with delayed gradients and compressed updates. Journal of Machine Learning Research, pages 1–36, 2020. Sebastian U. Stich, Jean-Baptiste Cordonnier, and Martin Jaggi. Sparsified sgd with memory. Advances in Neural Information Processing Systems 31 (NeurIPS), pages 4447–4458, 2018. Brian Swenson, Ryan Murray, H. Vincent Poor, and Soummya Kar. Distributed stochastic gradient descent: Nonconvexity, nonsmoothness, and convergence to local minima. Journal of Machine Learning Research, 23(328):1–62, 2022. Hanlin Tang, Shaoduo Gan, Ce Zhang, Tong Zhang, and Ji Liu. Communication compression for decentralized training. Advances in Neural Information Processing Systems 31 (NeurIPS), 2018. Zhipeng Tu, Xi Wang, Yiguang Hong, Lei Wang, Deming Yuan, and Guodong Shi. Distributed online convex optimization with compressed communication. In Advances in Neural Information Processing Systems 35 (NeurIPS), pages 34492–34504, 2022. Yuanyu Wan. Black-box reductions for decentralized online convex optimization in changing environments. In Proceedings of the 38th Annual Conference on Learning Theory (COLT), pages 5605–5631, 2025. Yuanyu Wan, √ Wei-Wei Tu, and Lijun Zhang. Projection-free distributed online convex optimization with O( T ) communication complexity. In Proceedings of the 37th International Conference on Machine Learning (ICML), pages 9818–9828, 2020. 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. 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 (COLT), pages 4862–4888, 2024. 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. 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 (AAAI), pages 10226–10234, 2023. Feng Yan, Shreyas Sundaram, SVN Vishwanathan, and Yuan Qi. Distributed autonomous online learning: Regrets and intrinsic privacy-preserving properties. IEEE Transactions on Knowledge and Data Engineering, pages 2483–2493, 2012. 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. Kun Yuan, Qing Ling, and Wotao Yin. On the convergence of decentralized gradient descent. SIAM Journal on Optimization, 26(3):1835–1854, 2016. Hantian Zhang, Jerry Li, Kaan Kara, Dan Alistarh, Ji Liu, and Ce Zhang. ZipML: Training linear models with end-to-end low precision, and a little bit of deep learning. In Proceedings of the 34th International Conference on Machine Learning (ICML), pages 4035–4043, 2017a. 13
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 (ICML), pages 4054–4062, 2017b. Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th International Conference on Machine Learning (ICML), pages 928–936, 2003.
14
A
Additional Discussions on Related Work
A.1
Compressor
Generally, compressors can be categorized into two classes: unbiased compressors [Jiang and Agrawal, 2018, Tang et al., 2018, Zhang et al., 2017a] and contractive compressors [Seide et al., 2014, Stich et al., 2018, Richtárik et al., 2022, h i Beznosikov et al., 2023]. An unbiased compressor satisfies 2 E[C(x)] = x and EC ∥C(x) − x∥ ≤ ω ∥x∥ for any input x ∈ Rd and ω ≥ 0. The contractive h i 2 compressor satisfies EC ∥C(x) − x∥ ≤ (1 − δ) ∥x∥ and δ ∈ (0, 1]. We provide two examples of compressor. • Rand-K. Randomly selecting k out of d coordinates yields compressor with the compression ratio of δ = kd . • (Scaled) sign. Let Sign(x) denote the sign of a vector x ∈ Rd . Outputting C(x) = ∥x∥1 1 d Sign(x) leads to a compression ratio of δ = d .
B
Proof of Theorems
B.1
Proof of Theorem 4.1
Pn Pn First, we introduce several notations. We denote ft (w) = n1 i=1 fit (w), vt = n1 i=1 vit and P n gt = n1 i=1 git . For êk and et , by summing up from k = 1 to t, we have
et =
t−1 X
vk − gk ,
t−1 X
êt =
k=1
sk − v k .
k=1
Then, we define several virtual decisions
ŵ
t+1
= arg min
w∈W
* t X
+ k
g ,w
k=1
1 2 + ∥w∥ , η
y
t+1
= arg min
* t X
y∈W
k=1
+ k
v ,y
+
1 2 ∥y∥ . η
Note that ŵt+1 represents the decision updated with the exact gradient, whereas yt+1 represents the decision updated with information that learners transmit to the server. Then we introduce some useful lemmas. Lemma B.1 (Lemma 6.6 in Garber and Hazan [2016]). Let {ℓt (w)}Tt=1 be a sequence of functions Pt and wt⋆ ∈ arg minw∈W k=1 ℓk (w) for any t ∈ [T ]. Then, it holds that T X t=1
ℓt (wt⋆ ) − min
w∈W
T X
ℓt (w) ≤ 0.
t=1
Lemma B.2 (Lemma 5 in Duchi et al. [2011]). Let ΠW (u, η) = arg minw∈W ⟨u, w⟩ + η1 ∥w∥2 . For any u, v ∈ Rd , we have ∥ΠW (u, η) − ΠW (v, η)∥ ≤ 15
η ∥u − v∥. 2
Now, we are ready to derive the regret bound. " T n # T n 1 XX t t 1 XX t EC [RT ] = EC f (w ) − f (w) n t=1 i=1 i n t=1 i=1 i ≤
=
T n 1 XX EC ⟨git , wt − w⟩ n t=1 i=1 T X
EC ⟨gt , wt − w⟩
t=1
≤
T X
EC ⟨gt , wt − ŵt + ŵt − w⟩
t=1
=
T X
EC ⟨gt , ŵt − w⟩ + ⟨gt , wt − ŵt ⟩
t=1
≤
T X
T t t X GEC wt − ŵt , EC ⟨g , ŵ − w⟩ + t=1
t=1
{z
|
}
TERM-A
{z
|
}
TERM-B
Pn where the last inequality is due to ⟨x, y⟩ ≤ ∥x∥ ∥y∥ and ∥gt ∥ = n1 i=1 git ≤ G. Remarkably, TERM-A is the regret bound of the decisions updated by using the uncompressed gradients and TERM-B is the error of the compression. In the following, we give the bound of this two term, respectively. As for TERM-A, we have T X
⟨gt , ŵt − w⟩ =
t=1
T X ⟨gt , ŵt − ŵt+1 + ŵt+1 − w⟩ t=1
=
T T X X ⟨gt , ŵt − ŵt+1 ⟩ + ⟨gt , ŵt+1 − w⟩ t=1
≤
T X
t=1
G ŵt − ŵt+1 +
t=1
T X
⟨gt , ŵt+1 − w⟩.
t=1
2
We define ℓ1 (w) = ⟨g1 , w⟩ + η1 ∥w∥ and ℓt (w) = ⟨gt , w⟩. We can verify that ŵt+1 = Pt arg minw∈W k=1 ℓk (w). By using Lemma B.1, we can derive 2 T T 2 X X ŵ2 − ∥w∥ ⟨gt , ŵt+1 − w⟩ + ≤ ℓt (ŵt+1 ) − ℓt (w) ≤ 0. η t=1 t=1
(12)
Therefore, we can obtain T X
⟨gt , ŵt − w⟩ =
t=1
T X
⟨gt , ŵt − ŵt+1 ⟩ +
t=1
≤
T X
T X
⟨gt , ŵt+1 − w⟩
t=1
gt
ŵt − ŵt+1 +
t=1
ηG2 T D2 ≤ + , 2 η where the first inequality is due to (12). 16
ŵ2
2
− ∥w∥ η
2
(13)
In the following, we give the bound of TERM-B. EC wt − ŵt = EC wt − yt + yt − ŵt ≤ EC wt − yt + EC yt − ŵt #! # " t−1 " t−1 X X η k k k k + EC v −g ≤ EC s −v 2 k=1 k=1 η = EC et + EC êt , 2 where the second inequality is due to Lemma B.2. To give the bound of errors, we introduce the following lemma. Lemma B.3. Under the Assumptions 3.3 and 3.4, at any round t of D-FTCL, the norm of the errors is bounded by i 160(1 − δ)G2 h i 4(1 − δ)G2 h 2 t+1 2 ≤ , E ê . EC et+1 ≤ C δ2 δ4
By using Lemma B.3, we have η EC wt − ŵt ≤ EC êt−1 + EC et−1 2 √ √ η 13 1 − δG 2 1 − δG 15ηG ≤ + ≤ . 2 δ2 δ 2δ 2 √ , the final regret bound is By setting the learning rate η = GδD T
EC [RT ] ≤
T X
EC ⟨gt , ŵt − w⟩ + EC G wt − ŵt
t=1
ηG2 T D2 15ηG2 + + 2 η 2δ 2 √ √ √ DG T 15DG T DGδ T + + ≤ 2 δ 2δ √ ≤ O(δ −1 DG T ). ≤
B.2
Proof of Theorem 4.2
Similar to the previous proof, we define two decisions.
y
t+1
* t X
+
t
µX 2 y − wk y∈W 2 k=1 k=1 * t + X µt 2 k k = arg min v − µw , y + ∥y∥ . y∈W 2
= arg min
k
v ,y
+
k=1
ŵ
t+1
* t X
+
t
µX 2 w − wk = arg min g ,w + w∈W 2 k=1 k=1 * t + X µt 2 k k = arg min g − µw , w + ∥w∥ . w∈W 2 k
k=1
17
We begin to derive the regret bound, where the key difference is to utilize the strong convexity to improve the dependence on T . " EC [RT ] = EC
# T n 1 XX t t f (w ) − fit (w) n t=1 i=1 i
T
≤
=
=
=
≤
n
i h 1 XX µ wt − w EC ⟨git , wt − w⟩ − n t=1 i=1 2 T X
h i µ EC ⟨gt , wt − w⟩ − wt − w 2 t=1
T X
i h µ EC ⟨gt , wt − ŵt + ŵt − w⟩ − wt − w 2 t=1
T X
i h µ wt − w EC ⟨gt , wt − ŵt ⟩ + E ⟨gt , ŵt − w⟩ − 2 t=1
T T h i X X µ E ⟨gt , ŵt − w⟩ − wt − w + G wt − ŵt , 2 t=1 t=1 | {z } | {z } TERM-A
TERM-B
where the first inequality is due to Assumption 3.2 and the last inequality is due to ⟨x, y⟩ ≤ ∥x∥ ∥y∥ . 2
We first give the bound of TERM-A. We define ℓt (w) = ⟨gt , w⟩ + µ2 ∥w − wt ∥ and ŵt+1 = Pt arg minw∈W k=1 ℓk (w) in the strongly convex case. Then, it is not hard to verify that T X µ wt − w ⟨gt , ŵt − w⟩ − 2 t=1
=
≤
T X µ ⟨gt , ŵt − ŵt+1 + ŵt+1 − w⟩ − wt − w 2 t=1 T X
ℓt (ŵ
t+1
t
) − ℓt (w) + G ŵ − ŵ
(14)
t+1
t=1
≤
T X
G ŵt − ŵt+1 .
t=1
Pt Next, we bound the term G ŵt − ŵt+1 . We define Ft (w) = k=1 ℓk (w), and Ft (w) is a (tµ)strongly convex function and ŵt+1 = arg minw∈W Ft (w). We introduce the following lemma from Hazan and Kale [2012]. Lemma B.4. For any µ-strongly convex function f (x) : W → R and any x ∈ W, it holds that µ ∥x − x⋆ ∥2 ≤ f (x) − f (x⋆ ), 2 where x⋆ = arg minx∈W f (x). For any x, y ∈ W, we have |ℓt (x) − ℓt (y)| ≤ ⟨∇ℓt (x), x − y⟩ ≤ ∥∇ℓt (x)∥ ∥x − y∥ ≤ (G + µD) ∥x − y∥ . 18
(15)
By using Lemma B.4, we can derive G ŵt+1 − ŵt
2
2G (Ft (ŵt ) − Ft (ŵt+1 )) tµ 2G ≤ (Ft−1 (ŵt ) − Ft−1 (ŵt+1 ) + ℓt (ŵt ) − ℓt (ŵt+1 )) tµ 2G (ℓt (ŵt ) − ℓt (ŵt+1 )) ≤ tµ 2G ≤ (G + µD) ŵt+1 − ŵt , tµ ≤
which means G ŵt+1 − ŵt ≤
2G (G + µD). tµ
(16)
By using Lemma B.2 and Lemma B.3, we have EC
wt − ŵt
1 EC êt−1 + EC et−1 tµ √ √ 1 13 1 − δG 2 1 − δG 15G ≤ + ≤ . tµ δ2 δ tµδ 2 ≤
Finally, we can derive the regret bound EC [RT ] ≤
T X 2G t=1
B.3
tµ
(G + µD) +
15G 15(G + µD)2 ≤ log T = O(δ −2 log T ). tµδ 2 µδ 2
Proof of Theorem 4.4
In this section, we present the proof of the lower bound for D-OCO with compressed communication. We follow Huang et al. [2022] and assume two protocols: (i) all learners can only communication with the central server and cannot exchange information with one another; (ii) all updates are synchronized, which means all learners update their decisions using the same information received from the central server, ensuring that the decisions across all learners are consistent. To characterize the effect of the compressor, we employ the idea of maximizing communication delay by using a specific compressor [Huang et al., 2022]. In our construction, we consider the Random Gossip compressor C(·) [Koloskova et al., 2019], which outputs Q(x) = x with probability δ ∈ (0, 1] and Q(x) = 0 otherwise. Under this scheme, the expected number of communication rounds required for a learner to successfully transmit information to the central server is ⌈1/δ⌉. We assume the server does not use the compressor, which is unidirectional compression. As pointed out by Huang et al. [2022], the lower bound for algorithms that admit bidirectional compression is greater than or equal to that with unidirectional compression. Therefore, we do not employ the compressor on the server. As noted by Huang et al. [2022], lower bounds for bidirectional compression are at least as large as those for unidirectional compression. To simplify the analysis, we consider unidirectional compression where only learners compress their communications, while the server transmits without compression. Let K = ⌈1/δ⌉, Z = ⌊(T − 1)/K⌋, c0 = 0 and cZ+1 = T . The total T rounds can be divided into the following Z + 1 intervals [c0 + 1, c1 ], [c1 + 1, c2 ], . . . , [cZ + 1, cZ+1 ]. To maximize the impact of the communication on the regret, we set the losses of each learner i is same in each interval. Specifically, we assume m = ⌊n/2⌋ and set the loss functions as t f1t (w) = · · · = fm (w) = 0, t for t ∈ [ci + 1, ci+1 ], i ∈ {0, ..., Z}, while the other loss functions are set fm+1 (w) = · · · = t fn (w) = hi (w). In this way, the global loss function is
ft (w) =
n−m hi (w). n 19
We independently select hi (w) = ⟨zi , w⟩ for any i ∈ {0, ..., Z}, √ where the √ √ coordinates of zi are ±G/ d with probability 0.5 and the feasible domain X = [−D/2 d, D/2 d]d . According to the above discussion, the decisions xt for any t ∈ [ci + 1, ci+1 ], i ∈ {0, ..., Z} are made before the function hi (w) can be revealed to the local learner. Then we can derive " T n # T n 1 XX t t 1 XX t EC [RT ] =EC f (w ) − min fi (w) w∈W n n t=1 i=1 i t=1 i=1 # " Z ci+1 ci+1 Z X X X X n−m t EC hi (w ) − min = hi (w) w∈W n i=0 t=ci +1 i=0 t=ci +1 " Z ci+1 # ci+1 Z X X X X n−m t EC = ⟨zi , w ⟩ − min ⟨zi , w⟩ (17) w∈W n i=0 t=ci +1 i=0 t=ci +1 " # ci+1 Z X X n−m EC min ⟨zi , w⟩ =− w∈W n i=0 t=ci +1 " # Z X n−m EC min ⟨ (ci+1 − ci )zi , w⟩ , =− w∈W n i=0 where the fourth equality is due to E[⟨zi , wt ⟩] = 0 for ∀t ∈ [ci + 1, ci+1 ]. Then, we denote ϵ01 , ..., ϵ0d , ..., ϵZ1 , ..., ϵZd be the coordinates of z1 , ..., zZ , which are identically distributed variables with P(ϵij = ±1) = 1/2 for i ∈ {0, ..., Z} and j ∈ {1, ..., d}. By using the Khintchine inequality on (17), we have d Z X X D ϵij G n−m Eϵ01 ,...,ϵZd − √ (ci+1 − ci ) √ EC [RT ] = − n 2 d d j=1 i=1 # " Z X n − m DG (ci+1 − ci )ϵi1 Eϵ01 ,...,ϵZd = n 2 i=0 v u Z X n − m DG u √ t (ci+1 − ci )2 ≥ (18) n 2 2 i=0 r n − m DG (cZ+1 − c0 )2 √ ≥ n 2 2 Z +1 DGT ≥ √ 4 2Z + 2 DGT ≥ √ , 4 2δT + 2 − 2δ where the second inequality is due to the Cauchy-Schwarz inequality. If 2 − 2δ ≤ 2δT , we can obtain √ DGT DG T √ . EC [RT ] ≥ √ ≥ 4 2δT + 2 − 2δ 8 δ B.4
(19)
Proof of Theorem 4.5
This proof is similar to the proof of Theorem 4.5. The key modification is to construct loss √ new d functions to utilize the strong convexity and we choose the feasible domain W = [0, D/ d] Specifically, we set the loss functions as t f1t (w) = · · · = fm (w) =
20
µ 2 ∥w∥ , 2
for t ∈ [ci + 1, ci+1 ], i ∈ {0, ..., Z}, while the other loss functions are set Dzi µ w− √ 2 d
t fm+1 (w) = · · · = fnt (w) =
2
,
where zi is sampled from the distribution: Pr(zi = 1) = p, Pr(zi = 0) = 1 − p and p ∈ [0, 1]. In this way, the global loss function in round t ∈ [ci + 1, ci+1 ], i ∈ {0, ..., Z} is
2
µm Dzi µ(n − m) 2 w− √ ∥w∥ + 2n 2n d 2 µ µ(n − m)D µ(n − m)D 2 2 √ = ∥w∥ + ∥zi ∥ − ⟨w, zi ⟩. 2 2nd d
ft (w) =
By taking the expectation on zi , we have µ µ(n − m)D2 µ(n − m)D 2 √ ∥w∥ + ⟨1, p⟩ − ⟨w, p⟩ 2 2nd d (n − m)Dp µ(n − m)D2 n−m µ √ w− + 1− p, p , = 2 2nd n n d
Ezi [ft (w)] =
where p = [p, ..., p]⊤ ∈ Rd . We denote H(w) = Ezi [fi (w)] and w⋆ = arg minw∈W F (w) = (n−m)Dp √ ∈ W, which implies H(w) − H(w⋆ ) ≥ 0. Then we derive the lower bound for strongly n d convex loss functions.
"
# n n T T 1 XX i t 1 XX i f (w ) − min ft (w) EC [RT ] =EC w∈W n n t=1 i=1 t t=1 i=1 # " Z ci+1 ci+1 Z X X X X hi (w) =EC hi (wt ) − min w∈W
i=0 t=ci +1
=EC
" Z ci+1 X X
H(wt ) − min
w∈W
i=0 t=ci +1
≥EC
" Z ci+1 X X
H(wt ) −
i=0 t=ci +1
where the last inequality h i PZ Pci+1 E minw∈W i=0 t=ci +1 H(w) .
is
i=0 t=ci +1 ci+1 Z X X
(20)
# H(w)
i=0 t=ci +1
ci+1 Z X X
# H(w⋆ ) ,
i=0 t=ci +1
due
to
E
hP
Z Pci+1 ⋆ i=0 t=ci +1 H(w )
i
≥
Now, our goal is to derive a lower bound of the right term of (20). We introduce a lemma from the proof of Theorem 4 in Wan et al. [2025], which establish the lower bound for decentralized online convex optimization. √ Lemma B.5 (Wan et al. [2025]). For an online convex optimization with the domain W = [0, D/ d]d , the length of interval is K and the interval number Z = ⌊(T −1)/K⌋, M = ⌊log16 (15Z +16)−1⌋ ≥ 1, the lower bound of (20) is ci+1 Z X X i=0 t=ci +1
H(wt ) −
ci+1 Z X X
H(w⋆ ) ≥
i=0 t=ci +1
21
µM K(n − m)2 D2 . 164 n2
Algorithm 5 Distributed Follow-the-Fast-Compressed-Leader (D-FTFCL) Require: w1 = 0, e1i = 0, ê1 = 0, learning rate η, compressor C(·), block size L 1: for b = 1, . . . , T /L do 2: for each learner i = 1, . . . , n in parallel 3: If b ≥ 2, set rki,b−1 = 0, k = 1 4: for t = (b − 1)L + 1, . . . , bL do 5: Play the decision wb and receive gradient git 6: If b ≥ 2 7: Compute C(zb−1 − rki,b−1 ) and send to the central server i b−1 k 8: Update rk+1 − rki,b−1 ) and set k = k + 1 i,b−1 = ri,b−1 + C(zi 9: end if 10: end for PbL 11: Compute zbi = t=(b−1)L+1 git and vib−1 = rL+1 i,b−1 b−1 b−1 12: Compute ebi = eb−1 + z − v i i i 13: for server and if b ≥ 3 P do n ▷ Only receive gradients of block b − 2 at block b 14: Compute vb−2 = n1 i=1 vib−2 15: Set rkb−2 = 0, k = 1 16: for t = (b − 1)L + 1, . . . , bL do 17: Compute C(vb−2 + êb−2 − rkb−2 ) and send to all local learners k b−2 18: Update rk+1 + êb−2 − rkb−2 ) and set k = k + 1 b−2 = rb−2 + C(v 19: end for 20: Compute sb−2 = rL+1 b−2 21: Update êb−1 = êb−2 + vb−2 − sb−2 22: for each learner i = 1, . . . , n in parallel and if b ≥ 3 do 23: Receive total information sb−2 and update the decision wb+1 according to (6) or (7) 24: end for By using lemma B.5 and setting 16δ −1 + 1 ≤ T , we can obtain the following lower bound µM K(n − m)2 D2 164 n2 2 µD (log16 (15Z + 16) − 2) ≥ 4 · 164 · δ 2 µD (log16 (15δ(T − 1) + 16) − 2) ≥ 4 · 164 · δ µD2 (log16 (15δT ) − 2) . ≥ 4 · 164 · δ
EC [RT ] ≥
Additional discussion. Note that the upper regret bounds of D-OCO algorithms generally hold for all compressors satisfying Definition 3.6. Therefore, although lower bounds in Theorems 4.4 and 4.5 are constructed based on a specific compressor instantiation, they are sufficient to prove the tightness of the upper bounds in general. B.5
Proof of Theorem 4.8
We first provide a more detailed version of D-FTFCL in Algorithm 5. Due to the asynchronous communication between the learners and the server, each learner experiences a two-block delay during aggregation. Specifically, for the gradient computed in block b, it takes one block for the learner to transmit the information to the server, and another block for the server to aggregate and broadcast the updated information back to the learners. Consequently, at the end of block b, each learner updates its model using the gradient information from block b − 2. We first define several decisions. ŵ
b+1
= arg min
w∈W
* b X k=1
22
+ k
z ,w
+
1 2 ∥w∥ , η
Pn where zb = n1 i=1 zbi . It is not hard to verify that ŵb+1 is the decision with the exact gradient when there is no delay in transmission. * b−2 + * b−2 + X X 1 1 2 2 b+1 k b+1 k y = arg min v , y + ∥y∥ , w̃ = arg min z , w + ∥w∥ . y∈W w∈W η η k=1
k=1
We also have b+1
e
=
b X
k
k
b+1
v −z ,
ê
=
k=1
b X
sk − vk .
k=1
In the following, we begin to derive the regret T
EC [RT ] ≤
n
1 XX EC ⟨git , wt − w⟩ n t=1 i=1 K
=
bL X
1X n
n X
EC ⟨git , wb − w⟩
b=1 t=(b−1)L i=1
=
K X
bL X
EC ⟨gt , wb − w⟩
b=1 t=(b−1)L
≤
K X
EC ⟨zb , wb − ŵb + ŵb − w⟩
b=1
=
K X
EC ⟨zb , ŵb − w⟩ + EC ⟨zb , wb − ŵb
b=1
≤
K X
K X GLEC wb − ŵb . EC ⟨zb , ŵb − w⟩ + b=1
b=1
{z
|
}
TERM-A
|
{z
}
TERM-B 2
We first give the bound of TERM-A. We define ℓ1 (w) = ⟨z1 , w⟩ + η1 ∥w∥ and ℓb (w) = ⟨zb , w⟩. By using Lemma B.1, we have K X
b
⟨z , ŵ
b+1
ŵ2
− w⟩ +
2
2
K
X − ∥w∥ ≤ ℓb (ŵb+1 ) − ℓb (w) ≤ 0. η
(21)
b=1
b=1
Therefore, we can derive K K K X X X ⟨zb , ŵb − w⟩ = ⟨zb , ŵb − ŵb+1 ⟩ + ⟨zb , ŵb+1 − w⟩ b=1
b=1
≤
K X
b=1
z
b
b
ŵ − ŵ
b=1 2
≤
b+1
+
ŵ2
2
− ∥w∥ η
2
ηG LT D2 + , 2 η
where the last inequality is due to zb ≤ LG. The key difference in the proof is the bound of the norm of the errors. We introduce the following lemma. Lemma B.6. Under the Assumptions 3.3 and 3.4, at any block b of D-FTFCL, the norm of the errors is bounded by h i h i 2 2 EC eb+1 ≤ 4e2 L2 G2 , EC êb+1 ≤ 120e2 L2 G2 .
23
In the following, we explicitly characterize the impact of the delayed updates and can get wb − ŵb = wb − yb + yb − w̃b + w̃b − ŵb ≤ wb − yb + w̃b − yb + w̃b − ŵb b−2 b−2 X X η ≤ vk − zk + zb−2 + zb−1 sk − vk + 2 k=1 k=1 η b−1 b−1 = + zb−2 + zb−1 + e ê 2 √ η ≤ 2eLG + 120eLG + 2LG ≤ 20ηLG, 2
!
where the second inequality is due to Lemma B.2 and the last inequality is due to Lemma B.6. By setting the learning rate η = G√DLT , the final regret bound is
EC [RT ] ≤
K X
⟨EC zb , ŵb − w⟩ + GLEC wb − ŵb
b=1
ηG2 LT D2 + + 20ηLT G2 2 η √ √ ≤ O(DG LT ) = O(DGδ −1/2 T ). ≤
B.6
Proof of Theorem 4.9
We first give some virtual decisions.
ŵ
b+1
* b X
+
z ,w
k=1
y
b+1
* b−2 X
w̃
+
k=1
+
b
µL X 2 y − wk y∈W 2 k=1 k=1 * b−2 + b X X µbL 2 k k = arg min v − µLw , y + ∥y∥ . y∈W 2
= arg min
k
v ,y
+
k=1
b+1
b
µL X 2 w − wk w∈W 2 k=1 k=1 * b + b X X µbL 2 k k = arg min z − µLw , w + ∥w∥ . w∈W 2 = arg min
k
* b−2 X
k=1
+
b
µL X 2 w − wk w∈W 2 k=1 k=1 * b−2 + b X X µbL 2 k k µLw , w + ∥w∥ . = arg min z − w∈W 2
= arg min
k=1
k
z ,w
+
k=1
24
(22)
In the following, we begin to derive the regret bound EC [RT ] = ≤
=
T n 1 XX EC fit (wt ) − fit (w) n t=1 i=1 T
n
K X
bL X
i h 1 XX µ wt − w EC ⟨git , wt − w⟩ − n t=1 i=1 2
b=1 t=(b−1)L
i h µ wb − w EC ⟨gt , wb − w⟩ − 2
K X
µL b b b b b w −w = EC ⟨z , w − ŵ + ŵ − w⟩ − 2 b=1 K X b b µL b b b b = w −w EC ⟨z , w − ŵ ⟩ + E ⟨z , ŵ − w⟩ − 2 b=1 X K K X µL b b b w −w + ≤ EC ⟨z , ŵ − w⟩ − GLEC wb − ŵb , 2 b=1 b=1 | {z } | {z } TERM-A
TERM-B
where the first inequality is due to Assumption 3.2 and the last inequality is due to zb ≤ GL. w − wb We first give the bound of TERM-A. We define ℓb (w) = ⟨zb , w⟩ + µL 2 Pb arg minw∈W k=1 ℓk (w) in the strongly convex case. Then, we have
2
and ŵb+1 =
K X µL ⟨zb , ŵb − w⟩ − wb − w 2 b=1
=
K X µL wb − w ⟨zb , ŵb − ŵb+1 + ŵb+1 − w⟩ − 2 b=1
≤
K X
(23) ℓb (ŵ
b+1
b
) − ℓb (w) + GL ŵ − ŵ
b+1
b=1
≤
K X
GL ŵb − ŵb+1 .
b=1
Pb Next, we give the bound of GL ŵb − ŵb+1 . We define Fb (w) = k=1 ℓk (w). It is not hard to verify that Fb (w) is (bLµ)-strongly convex function and ŵb+1 = arg minw∈W Fb (w). By using Lemma B.4, for any x, y ∈ W, we have |ℓb (x) − ℓb (y)| ≤ ⟨∇ℓb (x), x − y⟩ ≤ ∥∇ℓb (x)∥ ∥x − y∥ ≤ (GL + µLD) ∥x − y∥ . Therefore, we can derive GL ŵb+1 − ŵb
2
2GL (Fb (ŵb ) − Fb (ŵb+1 )) bLµ 2GL ≤ (Fb−1 (ŵb ) − Fb−1 (ŵb+1 ) + ℓb (ŵb ) − ℓb (ŵb+1 )) bLµ 2GL ≤ (ℓb (ŵb ) − ℓb (ŵb+1 )) bLµ 2GL ≤ (GL + µDL) ŵb+1 − ŵb , bLµ ≤
25
which means GL ŵb+1 − ŵb ≤
2GL (GL + µDL). bLµ
(24)
Moreover, according to (22), we have wb − ŵb = wb − yb + yb − w̃b + w̃b − ŵb ≤ wb − yb + w̃b − yb + w̃b − ŵb 1 ≤ êb−1 + eb−1 + zb−2 + zb−1 µbL 40LG √ 1 ≤ 2eLG + 120eLG + 2LG ≤ . µbL µbL
(25)
Therefore, by using Lemma B.6, (23) and (24), we have EC [RT ] ≤
K X 2GL b=1
bLµ
(GL + µDL) +
K X 2G
GL (40LG) µbL
40G2 bµ µb b=1 2 (G + µD) log T , ≤O L µ PT /L where the last inequality is due to b=1 1b ≤ log(T /L) + 1. =L
B.7
(G + µD) +
Proof of Theorem 5.2
We first recall the property of the subgradient. For a subgradient gi ∈ ∂fi (x) of a convex function fi (·) at x, we have fi (y) ≥ fi (x) + ⟨gi , y − x⟩. Then, we first give the theoretical guarantee of the anytime online-to-batch conversion. Lemma B.7. (Theorem 2 in Cutkosky [2019]) We assumeP ℓ̂t (x) is convex and satisfies f (xt )−f (x) ≤ T
α wt
t E[ℓ̂t (xt ) − ℓ̂t (x)]. Then for all x ∈ W and xT = t=1 , the online-to-batch conversion α1:T guarantees: "P # T t t t ℓ̂ (w ) − ℓ̂ (x) t=1 EC [f (xT ) − f (x)] ≤ EC α1:T
Pn By setting αt = 1, ℓ̂ti (w) = ⟨git , w⟩, ℓ̂t (w) = ⟨gt , w⟩ and gt = n1 i=1 git , we can obtain # " n 1X RK K ⋆ K ⋆ EC [f (x ) − f (x )] = EC fi (x ) − fi (x ) ≤ EC . n i=1 K We further have EC [RK ] =
K X
EC ⟨gt , wt − w⟩
t=1
≤
K X
⟨gt , wt − ŵt + ŵt − w⟩
t=1
=
K X
⟨gt , ŵt − w⟩ + ⟨gt , wt − ŵt ⟩
t=1
≤
K X
⟨gt , ŵt − w⟩ + G wt − ŵt .
t=1
Similar to the previous proof, we give the bound of the compression error. 26
Lemma B.8. Under the Assumptions 3.4 and 5.1, at any round t of D-O2B with compression communication, the norm of the errors is bounded by h i h i 2 2 EC et+1 ≤ 4e2 αt2 G2 , EC êt+1 ≤ 120e2 αt2 G2 .
According to the previous proof of Theorem 4.1, by using (13), Lemma B.2 and B.8, and setting αt = 1, we can obtain the following K X ⟨gt , ŵt − w⟩ + G wt − ŵt
EC [RK ] ≤
t=1
ηG2 K D2 η êt−1 + et−1 + + 2 η 2 √ ηG2 K D2 13eηG ≤ + + ≤ O(DG K), 2 η 2
≤
D where the last inequality due to η = G√ . K
Furthermore, we can obtain √ # O(DG DG K) K ⋆ EC [f (x ) − f (x )] ≤ E =O √ , K δT "
where the last equality is due to T = KL. B.8
Proof of Theorem 5.3
t t Following Cutkosky [2019], we set αt = t, ℓ̂ti (w) = ⟨tgit , w⟩ + µt 2 ∥w − x ∥, ℓ̂ (w) = Pn t 1 i=1 ℓ̂i (w), we can obtain n 2RK EC [f (xK ) − f (x⋆ )] ≤ EC . K(K + 1)
In each round t, each learner updates its decision as follows: * t + t X µX 2 t+1 k k w − xk w = arg min s ,w + w∈W 2 k=1 k=1 * t + t X X µt(t + 1) 2 k k = arg min s − kµx , w + ∥w∥ , w∈W 4 k=1
k=1
and we define two variables: y
ŵ
t+1
t+1
* t X
+
t
µX 2 k y − xk y∈W 2 k=1 k=1 * t + t X X µt(t + 1) 2 k k = arg min v − kµx , y + ∥y∥ , y∈W 4 = arg min
k
v ,y
+
k=1
k=1
* t X
+
t
µX 2 = arg min kg , w + k w − xk w∈W 2 k=1 k=1 * t + t X X µt(t + 1) 2 k k = arg min kg − kµx , w + ∥w∥ . w∈W 4 k=1
k
k=1
27
Next, we give the regret bound on the loss function ℓ̂t (w). RK =
K X
ℓ̂t (wt ) − ℓ̂t (w)
t=1
≤
K X
ℓ̂t (ŵt ) − ℓ̂t (w) + ℓ̂t (wt ) − ℓ̂t (ŵt )
t=1
≤
K X
ℓ̂t (ŵt ) − ℓ̂t (w) + (tG + µtD) ŵt − wt .
t=1
To bound the term
PK
t t t t=1 ℓ̂ (ŵ ) − ℓ̂ (w), we introduce a lemma.
Lemma B.9 (Corollary 5 in Cutkosky [2019]). Under the Assumptions 3.2, 3.4 and 5.1, by setting Pt t+1 t 2 t = arg minw∈W k=1 ℓ̂t (w), the weight αt = t, ℓ̂t (w) = ⟨αt gt , w⟩ + µα 2 ∥w − x ∥ and ŵ for any w ∈ W anytime O2B can ensure K X
ℓ̂t (ŵt ) − ℓ̂t (w) ≤
t=1
K(µD + G)2 . µ
Then we bound the term ∥wt − ŵt ∥. By using Lemma B.2 and B.8, and setting αt = t, we have EC
wt − ŵt
2 EC êt−1 + EC et−1 µt(t + 1) 30eG . ≤ µ(t + 1) ≤
(26)
Finally, by using Lemma B.9 and (26), we can derive the regret bound EC [RK ] ≤ ≤
K K(µD + G)2 X 30(G + µD)2 et + µ µt t=1
2K(G + µD)2 30eK(G + µD)2 + =O µ µ
K(G + µD)2 µ
.
The final convergence rate is EC [f (xK ) − f (x⋆ )] ≤ EC
2RK (G + µD)2 (G + µD)2 ≤O =O . K(K + 1) µK δµT
Additional discussion. It is worth noting that our method involves only K updates, with the total communication rounds amounting to T = ⌈ 1δ ⌉K. In contrast, standard compression-based methods (e.g., O2B with Algorithm 2 and standard compressor) typically perform T updates over T communication rounds, yielding a convergence rate for convex loss functions of: DG RT = √ . E[f (xT ) − f (x⋆ )] ≤ E T δ T Compared to these methods, our approach achieves not only a faster convergence rate but also lower sample complexity under the same communication budget (i.e., the same number of communication rounds T ). From a high-level perspective, although our algorithm performs fewer updates, the information incorporated in each update exhibits significantly lower bias compared to standard compression, thereby resulting in faster convergence. Although using Algorithm 3 achieves the same convergence rate, it incurs redundant gradient queries. 28
B.9
Proof of the Unidirectional Compression
It is worth noting that under the unidirectional compression, learner i updates the decision according to * t + X 1 2 t+1 t+1 k w =y = arg min v , y + ∥y∥ . y∈W η k=1
Therefore, we can obtain the regret bound " T n # T n 1 XX t t 1 XX t EC [RT ] = EC f (w ) − f (w) n t=1 i=1 i n t=1 i=1 i ≤
T X
EC ⟨gt , ŵt − w⟩ + GEC yt − ŵt .
t=1
According to the proof of Theorem 4.1, we have
EC
yt − ŵt
≤
ηG η EC et ≤ . 2 δ
√
By using (13) and setting η = DG δ , the final regret bound is " EC [RT ] = EC ≤
# n n T T 1 XX t 1 XX t t f (w ) − f (w) n t=1 i=1 i n t=1 i=1 i
√ ηG2 T D2 ηG + + ≤ O(DG δ −1 T ). 2 η δ
Notably, the regret bound of O(δ −1 log T ) for strongly convex loss functions can be derived using an analogous proof under unidirectional compression.
C
Proof of Supporting Lemmas
C.1
Proof of Lemma B.3
We first give the bound of the compression error of each learner. Following the proof in Karimireddy et al. [2019], we have 2 n n X t+1 2 1 1 X t+1 2 EC ∥e ∥ = EC et+1 EC ∥ei ∥ ≤ n i=1 i n i=1 n
=
1X t EC ∥ei + git − C(eti + git )∥2 n i=1
≤
n 1−δ X EC ∥eti + git ∥2 n i=1
≤ (1 − δ)(1 + α1 )
n n 1 X t 2 1X t 2 EC ∥ei ∥ + (1 − δ)(1 + α1−1 ) g n i=1 n i=1 i
≤ (1 − δ)(1 + α1 )
1 X t 2 EC ∥ei ∥ + (1 − δ)(1 + α1−1 )G2 , n i=1
n
29
2
2
2
where the third inequality is due to ∥x + y∥ ≤ (1 + α1 ) ∥x∥ + (1 + α1−1 ) ∥y∥ . By setting δ and summing up, we can derive α1 = 2−2δ n t−1 1X X t−k 2 EC ∥et+1 ∥2 ≤ EC ∥et+1 ∥ ≤ ((1 − δ)(1 + α1 )) (1 − δ)(1 + α1−1 )G2 i n i=1 k=0
≤
(1 − δ)(1 + α1−1 )G2
1 − (1 − δ)(1 + α1 ) 4(1 − δ)G2 . ≤ δ2 As for the upper bound of EC h EC
êt+1
i 2
= EC
h
êt+1
t X
2
=
(1 − δ)(1 + α1−1 )G2 δ − α1 + α1 δ
(27)
i , we have the following 2
v k − sk
= EC
t X
vk −
k=1
k=1
t−1 X
2
sk − C êt + v
t
k=1
2i vt + êt − C êt + vt ≤ (1 − δ)EC vt + êt h i h i 2 2 ≤ (1 − δ)(1 + α2 )EC êt + (1 − δ)(1 + α2−1 )EC vt . = EC
h
(28)
h i 2 As for the second term EC ∥vt ∥ , we have h EC
vt
2
i
n n h h i i 1X 1X 2 2 EC vit EC vit − (eti + git ) + (eti + git ) = n i=1 n i=1 " # n n X 2 2X 2 2 EC C(eti + git )) − (eti + git ) + et + git ≤ n i=1 n i=1 i " n # n h i 2(1 − δ) X 2X t t t 2 t 2 EC ei + gi e + gi ≤ + EC n n i=1 i i=1
≤
n
=
h i 2(2 − δ) X 2 EC eti + git n i=1
(29)
n 4(2 − δ) X h t 2 i 2 EC ei + git n i=1 4(1 − δ)G2 2 ≤ 4(2 − δ) +G δ2 2 4G 1 2 40G2 ≤8 + G ≤ . δ2 δ2 δ2
≤
δ By setting α2 = 2−2δ and plugging (29) into (28), we can derive
h EC
êt+1
2
i
≤(1 − δ)(1 + α2 )EC ≤
t−1 X
h
êt
((1 − δ)(1 + α2 ))
2
t−k
i
+ (1 − δ)(1 + α2−1 )
(1 − δ)(1 + α2−1 )
k=0 2
≤
(1 − δ)(1 + α2−1 ) 40G 160(1 − δ)G2 δ2 ≤ . 1 − (1 − δ)(1 + α2 ) δ4 30
40G2 δ2
40G2 δ2
C.2
Proof of Lemma B.6
According to Lemma 1, by choosing the compression round L = ⌈1/δ⌉, we can ensure h i 2 2 1 L+1 EC r −x ≤ e ∥x∥ , where rL+1 is the output of Algorithm 1. Therefore, we have
h EC
eb−1 + zb−1 − vib−1 i i
2
i
= EC
h
eb−1 + zb−1 − FCC(eb−1 + zb−1 , C(·), L) i i i i
2
i
≤
1 b−1 2 ei + zb−1 . i e (30)
Therefore, we can derive
2 n n X X b+1 2 1 ≤ 1 eb+1 EC ∥eb+1 ∥2 EC ∥e ∥ = EC i i n i=1 n i=1 =
n 1X b EC ∥ei + zbi − vib−1 ∥2 n i=1
≤
n 1 X EC ∥ebi + zbi ∥2 en i=1
≤ (1 + α1 )
n n 1 X b 2 1 X b 2 EC ∥ei ∥ + (1 + α1−1 ) z en i=1 en i=1 i
n 1 X b 2 1 + α1−1 2 2 ≤ (1 + α1 ) L G , EC ∥ei ∥ + en i=1 e
where the second equality is due to (30). By setting α1 = e−1 2 and summing up, we can derive
n
b−1
X 1X EC ∥eb+1 ∥2 ≤ i n i=1
k=0
≤
As for the term EC
h
êb+1
h EC
2
êb+1
i
1 + α1 e
b−k
(1 + α1−1 )
L2 G2 e
4L2 G2 (1 + α1−1 )L2 G2 ≤ ≤ 4e2 L2 G2 . e − (1 + α1 ) e(1 − 1/e)2
, we have the following
2
i
2i êb + vb − FCC êb + vb , C(·), L i 1 h 2 ≤ EC êb + vb e h i 1 + α−1 h i 1 + α2 2 2 2 ≤ EC êb + EC vb , e e = EC
h
31
(31)
where the first equality is due to (30). To bound the term EC h EC
2
vb
i
h
vb+1
2
i
, we have
n
≤
i h 1X 2 EC vib n i=1
n h i 1X 2 EC vib − (ebi + zbi ) + (ebi + zbi ) n i=1 # " n n h i 2X 2X b b b b 2 b 2 ≤ EC vi − (ei + zi ) e + zi + EC n i=1 n i=1 i " n # n i h 2X b 2/e X b b 2 b 2 + EC ≤ EC ei + zi e + zi n i=1 n i=1 i
=
(32)
n
=
i h 2 + 2/e X 2 EC ebi + zbi n i=1
n 4 + 4/e X h b 2 i 2 EC ei + zbi n i=1 ≤ (4 + 4/e) 4e2 L2 G2 + L2 G2 = 30e2 L2 G2 .
≤
By setting α2 = e−1 2 and plugging (32) into (31), we can derive h EC
êb+1
2
i
h i 1 + α−1 h i 1 2 2 2 EC vb + ≤ (1 + α2 )EC êb e e h i 1 + α2−1 1 2 30e2 L2 G2 ≤ (1 + α2 )EC êb + e e t−k t−1 X 1 + α2−1 1 ≤ (1 + α2 ) 30e2 L2 G2 e e k=0
(1 + α2−1 )30e2 L2 G2 ≤ ≤ 120e2 L2 G2 , e − (1 + α2 ) 1+e where the last inequality is due to (e−1) 2 ≤ 2.
C.3
Proof of Lemma B.8
We first give the bound of the compression error of each learner. Following the proof in Karimireddy et al. [2019], we have n 1 X t+1 2 EC ∥et+1 ∥2 ≤ EC ∥ei ∥ n i=1 n
=
1X t EC ∥ei + αt git − FCC(eti + αt git , C(·), L)∥2 n i=1
≤
n 1 X EC ∥eti + αt git ∥2 en i=1
≤ (1 + β1 )
n n 1 X t 2 1 X 2 EC ∥ei ∥ + (1 + β1−1 ) αt git en i=1 en i=1
≤ (1 + β1 )
1 X t 2 EC ∥ei ∥ + (1 + β1−1 )αt2 G2 . en i=1
n
32
By setting β1 = e−1 2 and summing up, we can derive n t−1 X 1X 2 2 EC ∥et+1 ∥2 ≤ EC ∥et+1 ∥ ≤ α t i n i=1
k=0
≤
αt2 (1 + β −1 )G2 e − (1 + β1 )
1 (1 + β1 ) e
t−k
1 (1 + β −1 )G2 e
(33)
≤ 4e2 αt2 G2 ,
where the third inequality is due to αt ≥ αt−1 . h i 2 As for the upper bound of EC êt+1 , we similar inequality ! 2 2 t t t t t i h X X X X X 2 vk − sk − FCC = EC vk − sk = EC vk − EC êt+1 sk , C(·), L k=1
k=1
≤
1 EC e
As for the second term EC h EC
v
t 2
i
k=1
k=1
k=1
h i 1 h i 1 2 2 vt + êt ≤ (1 + β2 )EC êt + (1 + β2−1 )EC vt . e e h
(34)
i ∥v ∥ , we have t 2 n
h i 1X 2 EC vit − (eti + αt git ) + (eti + αt git ) ≤ n i=1 # " n n 2X t 2X t 2 t t t 2 e + α t gi ≤ EC vi − (ei + αt gi ) + n i=1 n i=1 i # " n n h i X 2/e X 2 2 2 ≤ EC eti + αt git et + αt git + EC n i=1 n i=1 i n
h i 2 + 2/e X 2 EC eti + αt git = n i=1 n
4 + 4/e X h t 2 i 2 EC ei + αt git n i=1 2 ≤ (4 + 4/e) 4e2 αt−1 G2 + αt2 G2 ≤ (4 + 4/e) 4e2 αt2 G + αt2 G2 ≤ 30e2 αt2 G2 .
≤
By setting β2 = e−1 2 and plugging (35) into (34), we can derive h h i 1 i 1 2 2 EC êt+1 + (1 + β2−1 )30e2 αt2 G2 ≤ (1 + β2 )EC êt e e t−k t−1 X 1 1 ≤αt2 (1 + β2 ) (1 + β2−1 )30e2 G2 e e k=0
≤
(1 + β2−1 )30e2 αt2 G2 ≤ 120e2 αt2 G2 . e − (1 + β2 )
33
(35)