Distributed Online Convex Optimization with Compressed Communication
Authors: Zhipeng Tu
Xi Wang
Yiguang Hong
Lei Wang
Deming Yuan
Guodong Shi
Venue: NeurIPS 2022 Accept (2022)
Keywords: distributed online optimization
compressed communication
no-regret algorithm

Abstract: We consider a distributed online convex optimization problem when streaming data are distributed among computing agents over a connected communication network. Since the data are high-dimensional or the network is large-scale, communication load can be a bottleneck for the efficiency of distributed algorithms. To tackle this bottleneck, we apply the state-of-art data compression scheme to the fundamental GD-based distributed online algorithms. Three algorithms with difference-compressed communication are proposed for full information feedback (DC-DOGD), one-point bandit feedback (DC-DOBD), and two-point bandit feedback (DC-DO2BD), respectively. We obtain regret bounds explicitly in terms of time horizon, compression ratio, decision dimension, agent number, and network parameters. Our algorithms are proved to be no-regret and match the same regret bounds, w.r.t. time horizon, with their uncompressed versions for both convex and strongly convex losses. Numerical experiments are given to validate the theoretical findings and illustrate that the proposed algorithms can effectively reduce the total transmitted bits for distributed online training compared with the uncompressed baseline.

Distributed Online Convex Optimization with Compressed Communication
Zhipeng Tul:2, Xi Wang! Yiguang Hong* Lei Wang", Deming Yuan", Guodong Shi?
AAaddemy of Mathematics and Systems Science, Chinese Academy of Sciences, China
Australian Center for Field Robotics, School of AMME, The University of Sydney, Australia
Department of Control Science and Engineering, Tongji University, China *College of Control Science and Engineering, Zhejiang University, China School of Automation, Nanjing University of Science and Technology, China tuzhipeng@amss.cm ac. cn, vangxi14@maile 140miil ucas. cn.cn, yghong@iss ac cn lei. wangzjuezju. edu. en, dmyuan10120gmail com, guodong shi @sydney edu, au
Abstract
We consider a distributed online convex optimization problem when streaming data are distributed among computing agents over connected communication network. Since the data are high- nigh-dimensional the network is large-scale, com- munication load can be bottleneck for the efficiency of distributed algorithms. To tackle this bottleneck, we apply the state-of-art data compression scheme the fundamental GD-based distributed online algorithms. Three algorithms with difference- compeessed communication are proposed for full information feedback (DC-DOGD), one-point bandit feedback (DC-DOBD), and two-point bandit feed- back (DC-DO2BD), respectively. We obtain regret bounds explicitly in terms time horizon, compression ratio, decision dimension, agent number, and network parameters. Our algorithms are proved to be no-regret and match the same regret bounds, w.r.t. time horizon, with their uncompressed versions for both convex and strongly convex losses. Numerical experiments are given to validate the theoretical findings and illustrate that the proposed algorithms effectively reduce the total transmitted bits for distributed online training compared with the uncompressed baseline.
Introduction
Online optimization has attracted considerable attention in recent decades, for its remarkable applica- tions in machine learning tasks such spam filtering, dictionary learning, advertising selection, and so on 2 3 In such online tasks, data are revealed incrementally. and decisions must be made before all data available. When the streaming data collected multiple agents, the distributed online optimization over a multi-agent network is considered, where data storage and processing are performed in the agents [4] (5. It is often impractical communicate data among different agents from multiple concerns such as privacy and bandwidth utilization. Also, there is no central agent for global coordination. In such settings, each agent relies on its own data to run an algorithm while communicating decisions with its immediate neighbors.
To be specific, this paper considers the distributed online convex optimization (DOCO) prob- lem over an N-agent network. The objective to minimize the accumulated system-wide loss minzek 2TE (z), where the local convex loss function fī is formed by the data arriving
"Corresponding author
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

at time in agent i, and K C R is a convex feasible set. Note that the loss information is revealed to agent i after its decision xf is made. Generally, there are two basic types of information feedback that agents can possess. One is the full information feedback, where agents have access to the loss functions. The other the bandit feedback, where agents can only possess the values of the loss function at points around the decision. At each time step, agents choose the decisions based on their local feedback and neighbors' information. To measure the performance of an algorithm, the (static) regret is frequently used, which compares the cumulative loss of online decisions and the loss of the best decision chosen in hindsight through all the time horizons. The regret of node j E V is defined as
N ΣΣ i=
R(JT)-
fl(
min Ee
ΣΣ fl(2).
(1)
An algorithm called no-regret [6] if the average regret over T goes to zero, which means that the online decision updated by the streaming data is not far from the best decision chosen in hindsight.
Distributed no-regret online algorithms have been widely studied in recent years
8 10
Although distributed algorithms are theoretically feasible, most of them are not practical as the model size gets large, since communication cost can be a bottleneck for efficiency. In distributed training tasks, agents can be powful microcomputers, while their communication network may be with low bandwidth. The information exchange over the network is pretty slow compared with the computation taking place in agents [12 Thus, communication compression techniques of significance for practical implementations.
There have been many attempts to combine distributed optimization algorithms with compressors. straightforward idea the direct compression scheme, while algorithms with this simple scheme fail to converge even for the distributed average consensus problem [13 [4]. As an improvement, extrapolation compression scheme and difference compression scheme are proposed [55] Along this line, quite number of studies successfully extend the distributed optimization algorithms with
compressors and meanwhile maintain the convergence rate [16 17 18 19). However, distributed online optimization with compression is still area that has not been fully exploited. [20] proposed
algorithm that extended the AMSGrad to the distributed online setting with extrapo- lation compression, while only empirical results were given without theoretical analysis. The key open problem in this area is
whether is possible to design provably no-regret distributed online algorithms that work with compressors.
Contributions In this work, we answer the above question in the affirmative. We apply the difference compression scheme to the fundamental GD-based distributed online algorithms. Although the idea of such combination is simple, the underlying algorithm design and theoretical principle challenging since the compression error, projection error, and consensus error will be coupled. Our contributions are summarized as follows:
We propose communication-efficienn distributed online algorithms, which consist of difference compression, 7-gossip consensus, gradient descent, and projection, for the cases of full infor- mation feedback (DC-DOGD), one-point bandit feedback (DC-DOBD), and two-point bandit feedback (DC-DO2BD), respectively. We make the technical advance to combine the difference compression scheme with the projection scheme. Through proper design, the errors can be estimated and controlled with the consensus stepsize and the gradient descent stepsizes.
We analyze the regret bounds of the proposed algorithms for convex and strongly convex losses, respectively, which are established explicitly in terms of time horizon T, compression ratio w, decision dimension d, agent number N, and parameters of the communication graph G, as simplified and summarized in Table [ The obtained regret bounds are in accordance with those of [11 w.r.t T, N.d. d. Our algorithms are no-regret with theoretical guarantees.
We give exhaustive experiments to illustrate the performance of the proposed algorithms. Com- pared with the uncompressed algorithm DAOL (8), the proposed algorithms can reduce the total transmitted bits for distributed online training. Moreover, DC-DOGD and DC-DO2BD significantly outperform the algorithm ECD-AMSGrad 20)

---

Table 1: Regret bounds in different settings
Settings
convex losses
strongly convex losses
Full information
0 (w-2 (1 2N + w 9)²h 10 Nd.
NVT)
O O(ww-2N' + w NIn(T))
([ 2 +u + N Ne ())))))))))))))))))))))))))))))) ((()) 0 O + Na Lm())
One-point bandit
0
Two-point bandit
0 (w-2N + w NdVT)
Related Work Distributed online convex optimization has received numerous attention in recent years. Many basic algorithms have been extended to distributed settings, referring to 7 and references therein. For instance, [8] proposed a distributed online subgradient algorithm over a static directed network and achieved the regrets (VVT) and (In(T)) for convex and strongly convex losses, which are in line with those centralized online algorithms (21 22]. In the bandit feedback setting, by modifying the gradient to a randomized estimator, (9] proposed a distributed online bandit algorithm with one-point sampling over an undirected network and achieved ( In 1/ regret for strongly convex losses. Better bound could be achieved by two-point sampling. as obtained (VVT) regret for convex quadratic losses in case of bounded decision set. Also, [T0 investigated
the distributed online two-point bandit algorithm in dynamic environments and achieved O ((VT) and (In(T) regrets for convex and strongly convex losses, which match those of centralized two-bandit algorithms (23). [1]] comprehensively studied DOCO over Erdös-Rén Rényi random networks in full gradient feedback, one-point bandit feedback, and two-point bandit feedback, and gave regret bounds. Along the line of [1]] this paper aims to further introduce compressed communication strategies, while preserving the regret bounds arder-wisely.
Recently, combining distributed optimization algorithms with compressors has seen a dramatic rise in interest. Traditional compressors include the quantization [24 25 26), sparsification 2 28 29, and hybrid combining of them [30 31 32). The way to apply compressors is called a compression scheme. The most widely used compression schemes in distributed optimization are extrapolation compression and difference compression [[5]. Extrapolation compression allows agents to compress the extrapolation between the last two local states. Decentralized PSGD with extrapolation compression (ECD-PSGD) [15 was proved to converge sublinearly and match the rate of its uncompressed case (D-PSGD). Difference compression (DC), which is also called CHOCO [16] or innovation compression 19 allows agents to add replicas of neighboring states and compress the state-difference. There have been extensive successful designs combining distribute optimization algorithms with DC, to name few, DCD-PSGD [15] (based on PSGD), CHOCO-SGD [16] (based on gossip SGD), SPARQ-SGD 17 (based on event-trigger), C-GT 18 and COLD [9
(based on gradient tracking),
(based on NIDS), etc.
The difference compression scheme is different from the error-feedback scheme (EF) 24 33 in what to be compressed, which results in different application fields. DC compresses the difference between the current variable and the replica variable, which is widely used in distributed optimization where nodes tend to exchange state information whose limit is nonzero in general. EF compresses the sum of the gradient and the residual error, which is widely used in federated learning where nodes tend to exchange gradient information whose limit is expected to be zero. The insight is that successful designs have to compress something that goes to zero, otherwise the noise introduced by the compression will not vanish, which leads to the algorithm oscillation or even divergence. It is worth noting that the idea of DC can also be applied to federated learning, such as EF21 [34] and FedPAQ [35), which is another line of research. In this paper, we focus applying DC to distributed online optimization.
The results about the distributed online optimization with compression are quite limited. 20 poposed the ECD-AMSGrad algorithm that combined AMSGrad with extrapolation compression. Actually, the AMSGrad algorithm may not be good choice for DOCO problem since although AMSGrad itself is proved no-regret (36). a considerable performance gap still exists between AMSGrad and SGD 37 Besides, the introduction of compression errors will further worsen the algorithm such that ECD-AMSGrad will lose the no-regret performance (see Section 5 This paper focuses on the fundamental GD-based algorithms and will give no-regret guarantees.
3

---

2 Full Information Feedback
In this section, we first introduce the multi-agent network and the compressor we use, and then propose communication-efiin distributed online algorithm for DOCO with full information feedback. Expected regret bounds will be given for both convex and strongly convex losses.
Graph The multi-agent network is described by an undirected graph 9(V,E), where V (1....,]) NJ is the set nodes, representing the set of agents, and V x V is the set of edges. Let A [ay] E N be the connectivity matrix of G such that dzj = aji. If (et 2,) E, then and Vj can exchange information, and as = otherwise. It is worth noting that the communication is node-to-node in distributed setting, and there is no central node. The graph in this paper satisfies the following assumption.
Assumption 1. A E [0, 1] xN is symmetric doubly stochastic matrix.
The communication graph undirected and connected. Its connectivity matrix
Compressor A compressor Q(-) IR + IR is mapping whose output can be usually encoded with fewer bits than its input. In this paper, we consider broad class of compressors with the following general property, which has been widely considered in distributed optimization with compression [6 19)
Assumption 2. For some (0, 1]. Q satisfies
Eq x11² s (1 - |x|1, Vo R2d
where Eg denotes the expectation over the internal randomness of Q.
Compressors satisfy the above assumption are called w-contracted, which include many important biased or unbiased compressors, such as sparsification (Rand, and Top;) (28), random quantization (QSGD.) [26), random gossip (RGossip,,) [16), etc.
2.1 Algorithm design
the full information feedback, the loss function S revealed to node at time after the decision of is made. Then node has access to the gradient value f.( and can use of = = to make the next decision 2; ++1 We propose the DC-DOGD algorithm shown in Algorithm I which is
based on DAOL [8] and memory-efficient CHOCO-SGD [16). The DC-DOGD algorithm consists of two main parts: difference compressed communication (steps 2 and 3) and local decision update (steps and 5).
Algorithm Distributed Online Gradient Descent with Difference Compression (DC-DOGD)
Input: consensus stepsize 7, GD) stepsizes {m ) time T Initialize: set x! = 0, !! = 0, x = 0, for each node E V.
1: for t= 1 to T do in parallel for each node i V
2: Compress the difference vector of = Q(x² a:{) and update the replica at+1 = of + of.
3: Send of its neighbors and receive of from all its neighbors Aç. Update the estimate of
the consensus decision by f+1 = of + ΣjEN, aijgf.
4: Receive the full information feedback and calculate of (z())
5: Update decision variable as follows
Pk (of + + - -xt1) n(g?)
(3)
where Pk denotes the Euclidean projection, i.e., Px(x) = argmin yex ||x yll-
Output: {x11T_
The insight of introducing the variable éद and the difference compression are as below. Assume that
x² & 0 without loss of generality. Then, if node transmits the directly compressed information Q(x() to its neighbors, the compression error Q(x{) - ot will not vanish for -+ oc. The accumulation of compression errors makes the algorithm fail to converge. Instead, we compress something that

---

goes to zero. Let node i and all its neighbors keep an auxiliary variable i locally, which acts as replica of zf. Whenever node updates its decision variable z;, node calculates the difference of it. compresses the difference of (a df), and sends the compressed information of to its neighbors. After that, node and all its neighbors update the local replica 2/+1 2 + q/- When all nodes are reaching a consensus optimal decision, the updates of local decisions are small, and the differences between the replica variables and the true decision variables are also small. Then the compression errors are expected to vanish.
Local decision variables update through gradient descent. Y-gossip, and projection, in order to minimize the local loss function, keep consensus with neighbors, and remain in the feasible set, respectively. For each node i, s is initialized to O, and thus, of = Σ asjæy. Recall that 4 tracks rtf, then sf acts as node i's estimate of the consensus decision at time t. The y-gossip protocol is adopted to renovate the decision variable towards the consensus decision. The consensus stepsize E (0, 1] is tunable to control the consensus speed, and will also play crucial role in controlling the compression error.
If there is compression, i.e., using exact communication, then a/t turns out to be uq. and o5+1 becomes Σド= aszzt. Besides, take y 1, and then (3) reduces
N
= Pk a + E
JEN, aty(a) - x no V. = PK (Ejev. anja - Vf((a)
which is the DAOL algorithm in 88.
Remark 1. of is introduced for the memory-efficinncy Eq. (3) is equivalent to the update rule
= Pk 22) +
E ats (1)(t))) - alt1) m19g
we adopt the update rule together with 24tt = 2 df for j No (i) instead of steps 3 and then each node have store deg(i) + 2 vectors, namely, It, it and kz. NN which is memory-consumite
Remark 2. is potential to extend our algorithm from a fixed graph to a time-varying graph G. EV) We give the following two settings.
Random switching undirected networks. Our algorithm can be directly applied to the classic vareing FrdöösRééye random networks [38), where Gr is generated over the prescribed graph G and {i E & with a probability 0 < p < 1 for all {i,j} ) E &. This setting is equivalent to performing random gossip compressor over the fixed graph G, that is, transmiting information with the probability p, which satisfies Assumption 2 with w
Deterministic switching undirected networks. Our algorithm can be applied to this setting by modifying the connectivity matrix from A to A(f). With further assumptions networks such as Bounded Intercommunication Interval assumption (39), one can analyze the regret interval-wisely. This is interesting but out of this paper's 's focus, and we leave it for future study.
the switching
2.2 Regret bounds
We consider following assumptions, which are widely used in the studies of distributed online optimization [T]00
Assumption 3. The convex set K. bounded with diameter D, i.e. || yll $ D, Vz,y E K. ...,,, the loss function ft is convex with bounded gradient over KC, i.e., max,,1, [ < G.
Assumption 4. For each V and
Assumption 5. For each E V and t 1.2..... ...,.. T, the loss function ft is ptstoongly convex over K.C with the parameter > 0, i.e., (z) - (v) 2 (x y. (v)) + 1| 2112, Vx, y E K.
Suppose that the eigenvalues of the symmetric doubly stochastic connectivity matrix A are [A)] > (x2(A)] 2 ... > [A). Define the spectral gap 5 = [^a(A)] E (0, 1] and the spectral radius of the Laplacian matrix / : V - All2 E [0, 2). Then we give the expected regret bounds of Algorithm I for convex and strongly convex losses, respectively.
5

---

Theorem 1. Let Assumptions 7 3 and 4 hold. Consider Algorithm 7 with the consensus stepsize
(w++
48(62 1863² (6 + 2)(1-w) w) + 232 + B)( 2) w)w + 66 (5)
(i) (Convex case) Take the gradient descent stepsize np GvFFe a constant c 2 370 each j E and 2 1,
D
8
Then for
1 Ee [R( < + 8V3 (VN+ 21-+2V33---- (1+7-)0- NGDVT+C.
(6)
(ii) (Strongly convex case) With additional Assumption 5 take the gradient descent stepsize tp: M[++o for constant c 2 375.
16
Then for each j E V and T
EQ R(j,T) S pcD2 +4V3 VVN+2 18-1 + +1) (1+ + t) 1ot--ot-+---
The proof ideas are as follows. Firstly, we estimate the general regret bounds for each node, which depend on the consensus error, the projection error, the compression error, and the gradient descent stepsize. Then comes the key point that we analyze the coupled relationship between the errors, and bound them with the consensus stepsize 7 and the GD stepsize l/-- Finally, we choose proper y and M to obtain Theorem Complete proofs are attached to Appendix B
The consensus stepsize y chosen in 5 depends the compression ratio and the communicaiton graph paremeters 6 and B. Notice that is an increasing function with respect to w. and v|w=0- = 0, 1.71w= |= 1. Thus, 7 E (0, 1] for w (0, 1]. If there no compression (w 1), then y and Algorithm exactly reduces to DAOL 8 as mentioned in the algorithm design.
Theorem shows that Algorithm achieves the regret bounds O( 2 + w N)T and O ((w-2 V/ + () N In(T)) for convex losses and strongly convex losses, respectively. The
results suggest that
Algorithm iis no-regret in both convex case and strongly convex case, since the time averaged regret Be (RGTT)//2 - for T + co. The obtained regret bounds O ((VT) and (II are in accordance with those of the centralized online algorithms in the respective cases (21 22
The node averaged regret 3g (R(.T))/N increases with N, which in line with the result in
As the compression ratio w decreases, fewer bits are needed for node-to-node communication in each iteration, while more iteration rounds needed reach the desired regret. can be used to balance the iteration rounds and the transmitted bits in each iteration from multiple concerns such as the bandwidth and agent computation capability. practice, we can choose proper w to minimize the total transmitted bits or minimize the overall training time.
3 One-point Bandit Feedback
In this section, we apply difference compression to DOCO with one-point bandit feedback. We propose DC-DOBD algorithm, which basically follows DC-DOGD, except for the gradient estimation.
In the one-point bandit feedback, after making the decision of time t, agent can query the loss function value at one point around z and use the feedback to construct the gradient estimator gf. Like the procedure in [41), let agent choose a unit-norm vector uf < Rd uniformly at random, query the value of f at the point of = xf + euf, and calculate of = - (vf) Since the loss function ff is defined in the set IC, we slightly modify the projection in (3) as P(I-cix: to ensure the query point y E K. Algorithm 2 actually performs the gradient descent on the function (x) = EvEB [f]] (x + cu)] restricted to the convex set (1 C)C. It has been shown by [1 that E. L v f! (xr)). In the bandit setting, Assumptions and 4 are modified follows, which
common in online bandit optimization 21
Assumption The convex set contains the ball of radius r centered at the origin, and is contained in the ball of radius R, i.e. rB C K. S RB, B {ue Rd ||w||| < 1}.

---

Algorithm Distributed Online One-point Bandit Gradient Descent with Difference Compression (DC-DOBD)
Input: consensus stepsize 7, GD stepsizes (ne)=1 time T, exploration parameter shrinkage parameter Ç
Initialize: set 2 0, ! 0, s O, for each node i E V.
1: for t= T do in parallel for each node i V
2: Compress the difference vector of
Q( = and update a of gi-
3: Spread of and receive 9j.j E Nr. Update s s EjeN, a:g9;-
4: Receive the one-point bandit feedback and construct of = a f/ + euf)u4.
5: Update the decision variable xf+1 P()-))x (2) 7(8,t) aftl) -
Output: {a/
....., T, the loss function fi is convex and I-Lipschitz continuous in K., i.e., (x) (1) S <||--
Assumption 7. For each E V and t = 1,2, .... y|l, Vx, y K.
Assumptions Jand 7 lead to an uniform upper bound on the function value, i.e., there exists constant B > such that max [ff (z)] S B. Then we establish the expected regret bounds of Algorithm for convex and strongly convex losses, respectively.
Theorem 2.
Let common Assumptions
7 and hold. Consider Algorithm 2 with the consensus
stepsize y chosen in (5). Denote
H ==4/3 (VN + 2/3 18-1 +1)
+1) (1+77 101--18111 + w
(i) (Convex case) Take the gradient descent stepsize ni dB.ete for constant
28e
8
3-6"
(1+4H)BB 2(1
(T+)) and Ç = 5. Then for each j E E and T 12,,
T2
E [R(GTT)) S 2NT (T c)+ /2 + 4H) (1+ BB-) dBR.
(9)
(ii) (Strongly convex case) With additional Assumption 5 take the gradient descent stepsize tle
M(++e for a constant e 2
16
(Hdd In(T+c)
and Ç +. Then each j E V and T 2 1,
378'
(1+ t ")pT
E [R(j,T)] < 4ucR2 3N (HO (1+ B/) T In (T c).
(10)
Theorem 2 shows that Algorithmmiis also no-regret, and it achieves the regret bounds N/ and Od N//or// In (T)) for convex losses and strongly convex losses, respectively, which scaled with (w~2 + w- w-1) and
match the bounds obtained by [1I. The regrets
(w N/'2 + -)) 1/a for convex and strongly convex losses, which indicates that the influence of the compression ratio w on the regret bounds in the one moint bandit setting is less than that in the full information setting.
Two-point Bandit Feedback
In the two-point bandit feedback, agent i can query the loss function values two points around af. Like the procedure in (23) let agent i pick unit-norm vector uf E R uniformly at random, query the values of f yf
x + euf and vf,2 = of cut, and estimate the gradient as of = 24 (f)()),)) - ff (v(,2) uf. Then we obtain DC-DO2BD as a variant of DC-DOBD. In the two-point bandit setting, the regret of node j E V is modified
d
N MV + (1
N
R2(i,T)
ΣΣ M(x))
(1))
2
7

---

Algorithm Distributed Online Two-point Bandit Gradient Descent with Difference Compression (DC-DO2BD)
Input: consensus stepsize 7, GD stepsizes (ne)=1 time T, exploration parameter shrinkage parameter Ç
Initialize: set 2 = 0, ! 0, s O, for each node i E V.
1: for t= T do in parallel for each node i E V
2: Compress the difference vector of Q= = and update a o qi
3: Spread of and receive 9f.j E Nr. Update si+ s EjEN; a:j9; d
4: Receive the two-point feedback and construct of = 26 (J](a) +eu.) - 1/ - -euf)) ut.
5: Update the decision variable xf+1 P()-)) (2) 7(8 altl) -
Output: {a/
Theorem 3. Let common Assumptions 7 2 and holld Consider Algorithm with the consensus stepsize chosen in (5) and H defined in
(i) (Convex case) Take the gradient descent stepsize mpp dlvFFe for constant 2 and = S. Then for each j E V and T 221, 1,
2R
8 1
375
/T
E (R2(i,T) S (1 4H) (3 20/,) / NdIVT.
(12)
(ii) (Strongly convex case) With additional Assumption 5 take the gradient descent stepsize 1/: u(t+oj for a constant c 2
=
16
In(T) and Ç 5. Then for each E V and T 2 1,
375'
E [R22j, < RurR² + i N +) (3 + 28/r) (T))
(13)
Theorem 3 shows that Algorithm achieves O( + w - Ndv'T and 2
w= IT)) regret bounds for convex and strongly convex losses, respectively, which recovers the regret bounds O(vT) (convex) and ((n(T)) (strongly convex) in the full information case, while the constants are larger than those of Theorem
Numerical Experiments
In this section, we evaluate the three proposed algorithms on a real-world online problem. A prominent example is the diabetes prediction task, which aims to diagnose diabetes through several risk factors. Consider the distributed online regularized logistic regression with the local loss function
(xx) = Σ log (1 + exp (-b (ai.) x)))
/ 2 ||
(14)
where y is the regularization parameter, and a batch data samples {(as.j. b are revealed to agent i time I. We adopt dicbbree-binur---RFS2225
dataset with 70692 instances, 21 features, and 2 labels from [ Here, 0i,j E Rd with d 21, and b.j E (-1.1). 1). We standardize the data samples and distribute them evenly among N agents under the sorted setting, i.e., each agent only gets data samples from one class. The connected communication network (NN, M) with N nodes and M edges is generated randomly by tool NetworkX (42), and then we use the Metropolis rule [43] to construct the connectivity matrix A to satisfy Assumption [ We repeat each experiment ten times and depict the mean curve The parameters selection details are given in Appendix
Comparison experiment We run our algorithms DC-DOGD, DC-DOBD, DC-DO2BD, and make comparisons with ECD-AMSGrad (20), for the convex case (p = 0) and strongly convex case (u 1). The compressor type, the compression ratio, and the communication network are kept the same. Take the setting of compressor QSGD, with w 0.3 over (9, 18) as an example. We plot the time averaged maximum regret S RTT) man, R(jTT /TT versus the time horizon T and versus
andironn--n-------- wactors-evaluudeee evaluation. All experiments are performed on bit Windows platform with the Intel(R) Core(TM) 17-68500 3.6Ghz CPU. The codes are provided in the supplementary materials.
TTh data set is from https://ww.kkaggh https///wwkkegg...oo///eeeeeeoe coms/codeencooee/ddiaatteeeeeeee

---

the total number of transmitted bits in Fig. D where the best solution in the hindsight x" is obtained by Legistiiceerresionn optimizer from scikit-learn 44
Fig. [ shows that the time averaged regrets of DC-DOGD, DC-DOBD, and DC-DO2BD go to zero T goes infinity, which is in agreement with the theoretical results that our algorithms no-regret. Among the three proposed algorithms, the one-bandit feedback has the worst performance, while using two-bandit information can improve the performance and even reach that of the full information feedback. ECD-AMSGrad gets deteriorated in the first few steps because the inverse of the second raw moment estimation large and this algorithm does not have projection to restrict variables. Then, ECD-AMSGry declines fast, while its time-average regret can not reach zero. Clearly, DC-DOGD and DC-DO2BD significantly outperform ECD-AMSGrad.
DOGD
DC DC-D
DC DOCD
10
DC-OOG
BC-0000
BC-0000
DC-0080
BCO000
DC-000B0
DC-D0280
DC-P0280
BC-0008O
30-
20-
100 200
cin 500 950 Time 1pr con
100 zie 303 stc Time not am
Thananited to
Thanamitedd t.
(a) Convex case
(b) Strongly convex case
Figure 1: Comparison algorithms DC-DOGD, DC-DOBD, DC-DO2BD, and ECD-AMSGrad with QSGD2. = 0.3, ( 18).
Impacts of compression ratio and compressor type Fixing the compressor type (Top;)) and the graph (9, 18), we run DC-DOGD with different compression ratios (w = 0.05, 0.1, 0.5) for strongly convex losses We consider DAOL S as the baseline, which is with exact communication and is the special case of DC-DOGD with w 1. Fig. 2 shows that the greater the compression degree is (less w), the more iteration rounds are needed reach certain average regret, while the total transmitted bits are actually the fewer. DC-DOGD with w = 0.05 have approximately 8x reduction on transmitted bits reach a certain average regret compared with DAOL.
Then, we fix the compression ratio (w = 0.3) and the graph (9,, 18), and run DC-DOGD with different compressors (Top Randg, RGossip,, GSGD.,) for strongly convex losses. Fig. 2h shows that Rand, and RGossip, have almost the same performance. It is expected, since Rand; allows each element of the vector to has the probability s = k/d to be chosen to be transmitted, which is equivalent to randomly transmitting the whole vector with the probability p = w. Besides, Figs. 2b shows that Top, has better performance than Rands, which is in line with the intuition that the largest It coordinates contain more useful information than arbitrary & coordinates. In addition, quantization GSGD, performs better in reducing the total transmitted bits than sparsification under the same compression ratio.
10
30"
30-
Tunel: Thp.
Durel + Tay
wwd.
10p
10P
T0P
119 de ide 450 100 Time Rarioon
110
10
110 803 Sie 430 R0C
10
Time 200
(a) Compression ratio
(b) Compressor type
Figure 2: The impacts of compression ratio and compressor type for DC-DOGD over ( 18) in the strongly convex case.
"Since the trajectories in the convex case and strongly convex case share similar trends, here we only present the experiment results in the strongly convex case, for space limitation.

---

Impacts of topology and node number The communication network topology affects the parame- ters ó and 3. which affect the choice of the stepsizes 77, and y as well the algorithm performance. We take DC-DOGD in the strongly convex case as an example. Fixing the compressor (Top,) and the compression ratio (w = 0.05), we assess DC-DOGD over three basic topologies, namely ring, (NN, 2N), and full connected. Fig. 3a shows that full connected topology exhibits the best regret with respect to the time horizon, while (N,, 2N) performs slightly better in the sense of tranmitted bits. A sparser topology with fewer edges uses fewer bits to transmit information in each iteration, while more iteration rounds are needed for decision consensus. Thus, there will be a tradeoff case by case.
Finally, we let the node number N vary from to 10 to 50, and run DC-DOGD, DC-DOBD, DC- DO2BD with the same compressor Top2, the same compression ratio w = 0.1, over the full connected graph, for convex losses and strongly convex losses. We plot the node averaged regret AR(T) = moz, R(jTT/N versus the node number N in Fig. 3b
De Rodi De noAn
10
DOAD
DK DO380
100
10P
100
Time not orn
Node
Mode 12mb
(a) Different topologies
(b) Node number(left: convex, right: strongly convex)
Figure 3: The impacts of topology and node number.
Conclusions
In this paper, we considered DOCO with the full information feedback, one-point and two-points bandit feedback. We designed provably no-regret distributed online algorithms that work with w-- contracted compressors. The obtained regret bounds for both convex and strongly convex losses matched those of uncompressed algorithms in the literature. We further assessed the influence of the compressor type and the compression ratio on the regrets, and showed that w can be used to balance the iteration rounds and the transmitted bits according to the bandwidth.
A limitation of this work is that the obtained regret bounds show high order inverse dependence on the compression ratio, which are pretty conservative and may be further improved. Besides, the impact of topology sparsity is worth further investigation. We believe this paper is an important step in this direction. Future research includes extensions from fixed graphs to time-narying graphs and combinations with other compression schemes such as extrapolation compression.
Acknowledgments and Disclosure of Funding
This work is supported in part by Shanghai Municipal Science and Technology Major Project under Grant 2021SHZDDZX0100 and the National Natural Science Foundation of China under Grant 62173250, and in part by Australian Research Council under Grant DP190103615 and LP210200473.
References
[1] Elad Hazan et al. Introduction to online convex optimization. Foundations and Trends in Optimization, 2(3-4):157-333 325, 2016.
[2] David Sculley and Gabriel M Wachman. Relaxed online syms for spam filtering. In Proceedings of the 30th Annual International ACM SIGIR Conference Research and Development Information Retrieval, pages 415-422, 2007.
[3] Julien Mairal, Francis Bach, Jean Ponce, and Guillermo Sapiro. Online dictionary learning for sparse coding. In Proceedings of the 26th Annual International Conference on Machine Learning, pages 689 696. 2009.
10

---

[4] Deming Yuan. Alexandre Proutiere, and Guodong Shi. Distributed online linear regressions. JEEE Transactions Information Theory. 67666666666,, 2020.
[5] Wenpeng Zhang, Peilin Zhao, Wenwu Zhu, Steven CH Hoi, and Tong Zhang. Projection free distributed online learning in networks. In International Conference on Machine Learning, pages 4054 4062. PMLR. 2017.
[6] Niranjan Srinivas, Andreas Krause, Sham Kakade, and Matthias Seeger. Gaussian process optimization the bandit setting: No regret and experimental design. In Proceedings of the 27th International Conference on Machine Learning, number CONF. Omnipress, 2010.
[7] Xiuxian Li, Lihua Xie. and Na Li. A survey of decentralized online learning. arXiv preprint arXiv:2205.00473 2022.
[8] Feng Yan, Shreyas Sundaram, SVN Vishwanathan, and Yuan Qi. Distributed autonomous online learn- ing: Regrets and intrinsic privacy-preserving properties. IEEE Transactions Knowledge and Data Engineeringg 25(1 (2:4)334222223 2012.
[9] Deming Yuan, Daniel WC Ho, Yiguang Hong, and Guoping Jiang. Online bandit convex optimization over network. In 35th Chinese Control Conference, pages 8090-8095, 8095. IEEE, 2016.
[10] Jueyou Li, Chaojie Li, Wenwu Yu, Xiaomei Zhu, and Xinghuo Yu. Distributed online bandit learning in dynamic environments over unbalanced digraphs. IEEE Transactions on Network Science and Engineering, 344)33334-3047 2021.
[11] Jinlong Lei. Peng Yi, Yiguang Hong, Jie Chen, and Guodong Shi. Online convex optimization over Erdös-Rényi random networks. Advances in Neural Information Processing Systems, 13:15591-1 2020.
[12] Dan Alistarh. brief tutorial distributed and concurrent machine learning. In Proceedings of the 2018 ACM Sympoxium on Principles of Distributed Computing, pages 487-488, 2018.
[13] Tuncer Can Aysal, Mark J Coates, and Michael Rabbat. Distributed average consensus with dithered quantization. IEEE Transactions on Signal Processing, 36(10):495544918 2008.
[14] Ruggero Carli, Fabio Fagnani, Paolo Frasca, Tom Taylor, and Sandro Zampieri. Average consensus on networks with transmission noise or quantization. In 2007 European Control Conference, pages 1852-1857. TEFF, 2007.
[15] Hanlin Tang, Shaoduo Gan, Ce Zhang, Tong Zhang, and Ji Liu. Communication compression for decentralized training. Advances in Neural Information Processing Systems, 31, 2018.
[16] Anastasia Koloskova, Sebastian Stich, and Martin Jaggi. Decentralized stochastic optimization and gossip algorithms with compressed communication. In International Conference on Machine Learning, pages 3478-3487. PMLR, 2019.
[17] Navjot Singh, Deepesh Data, Jemin George, and Suhas Diggavi. Sparq-sgd: Event-triggered and com- pressed communication in decentralized optimization. IEEE Transactions on Automatic Control, 2022.
[18] Yiwei Liao, Zhuorui Li, Kun Huang, and Shi Pu. Compressed gradient tracking methods for decentralized optimization with linear convergence. arXiv preprint 10Xiv:2103.1177 13748, 2021.
[19] Jiaqi Zhang, Keyou You, and Lihua Xie. Innovation compression for communication-cfficcenn distributed optimization with linear convergence. arXiv preprint arXiv:2105.0660 2021.
[20] 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-29) 2021.
[21] Martin Zinkevich. Online convex programming generalized infinitesimal gradient ascent. Proceed- ings of the 20th International Conference on Machine Learning, pages 928-936, 2003.
[22] Elad Hazan, Amit Agarwal, and Satyen Kale. Logarithmic regret algorithms for online convex optimization. Machine Learning, 1992))169-192 2007.
[23] Alekh Agarwal, Ofer Dekel, and Lin Xiao. Optimal algorithms for online convex optimization with multi-point bandit feedback. In Proceedings of the 23rd Annual Conference on Learning Theory, pages 28 40. Citeseer, 2010.

---

[24] Frank Seide, Hao Fu, Jasha Droppo, Gang Li, and Dong Yu. 1-bit stochastic gradient descent and its application to data-pate data-parallel distributed training of speech dans. In Fifteenth Annual Conference of the International Speech Communication Association. Citeseer, 2014.
[25] 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. PMLR, 2018.
[26] Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. Qsgd: Communication- efficient sgd via gradient quantization and encoding. Advances in Neural Information Processing Systems, 30, 2017.
[27] 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.
[28] Sebastian U Stich, Jean- Jean-Baptiste Cordoanier, and Martin Jaggi. Sparsified sgd with memory. Advances in Neural Information Processing Systems, 31, 2018.
[29] Aritra Dutta, EI Houcine Bergou, Ahmed M Abdelmoniem, Chen Yu Ho, Atal Narayan Sahu, Marco Canini, and Panos Kalnis. On the discrepancy between the theoretical analysis and practical implementations of compressed communication for distributed deep learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 3817-3824, 2020.
[30] Jiawei Jiang, Fangcheng Fu, Tong Yang, and Bin Cui. Sketchml: Accelerating distributed machine learning with data sketches. In Proceedings of the 2018 International Conference Management of Data, pages
1269 1284, 2018.
[31] Hycontack Lim, David G Andersen, and Michael Kaminsky. 31e: Lightweight and effective traffic compression for distributed machine learning. Proceedings of Machine Learning and Systems, 1:53-64, 2019.
[32] Debraj Basu, Deepesh Data, Can Karakus, and Suhas Diggavi. Qsparsc-Incal-sgd: Distributed sgd with quantization, sparsification and local computations. Advances in Neural Information Processing Systems, 32, 2019.
[33] Sai Praneeth Karimireddy, Quentin Rebjock, Sebastian Stich, and Martin Jaggi. Error feedback fixes signsgd and other gradient compression schemes. In International Conference on Machine Learning, pages 3252-322 1221. PMLR, 2019.
[34] Peter Richtárík, Igor Sokolov, and Ilyas Fatkhullin. Ef21: A new, simpler, thcoretically better, and practically faster error feedback. Advances in Neural Information Processing Systems, 34, 2021.
[35] Amirhossein Reisizadeh, Aryan Mokhtari, Hamed Hassani, Ali Jadbahaic, and Ramtin Pedarsani. Fedpaq:
A communication-effiicenn federated learning method with periodic averaging and quantization. In International Conference on Artificial Intelligence and Statistics, pages 2021-2031. PMLR, 2020.
[36] Sashank Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. In International Conference on Learning Representations, 2018.
[37] Nitish Shirish Keskar and Richard Socher. Improving generalization performance by switching from adam to sgd. arXiv preprint
2017.
[38] Paul Erdōs, Alfréd Rényi, et al. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci, 5(1):17-60,, 1960.
[39] Angelia Nedié and Asuman Ozdaglar. Distributed subgradient methods for multi-agent optimization. JEEE Transactions on Automatic Control, 54(1):48-65 2009.
[40] Elad Hazan, Alexander Rakhlin, and Peter Bartlett. Adaptive online gradient descent. Advances in Neural Information Processing Systems, 20, 2007.
[41] 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 Algorithmss, pages 385-394, 2005.
[42] Aric Hagberg, Pieter Swart, and Daniel S Chult. Exploring network structure, dynamics, and function using networkx. Technical report, Los Alamos National Lab,LLANL), Los Alamos, NM (United States), 2008.
12

---

[43] Lin Xiao and Stephen Boyd. Fast linear iterations for distributed averaging. Systems & Control Letters. 53(1):65-78, 2004.
[44] Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathicu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, et al. Scikit-lcarn: Machine learning in python. the Journal of Machine Learning Research, 12:2825-28300 2011.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section DrriionoCnnncnsioooss
(c) Did you discuss any potential negative societal impacts of your work? [No] This work is theoretical finding to solve the communication bottleneck of the distributed algorithms. Therefore, this work does not present foreseeable societal impacts.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions of all theoretical results? [Yes] See Assump- tions I 2
and 7
(b) Did you include complete proofs of all theoretical results? [Yes] We present the proof ideas in the paper and put the complete proofs in supplemental materials due to space limitation.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes] Codes link is in the supplemental material. Data are from Kaggle with URL. Instructions are included in S5
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section and Appendix
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [No] We repeat each experiment ten times and only depict the mean curves to make the figures easier to read. Actually, our experiment results with different random seeds similar.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Section 5 3
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] We use the tools NetworkX and scikit-learn with citation. We use the open dateset from Kaggle with URL.
(b) Did you mention the license of the assets? [Yes] See Appendix
(c) Did you include any new assets either the supplemental material or as URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you'l 're using/curating? [No]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [No]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "wsPvMeQXqLu", "reviewer": "Reviewer_rpWg", "summary": "The paper applies the data compression scheme to the GD-based distributed online algorithms. Three algorithms are proposed and analyzed with difference-compressed communication schemes. Explicit regret bounds are derived in closed form. ", "questions": "1. Distributed convex optimization with compressed communication has been recently studied. What is the key difference/novelty in algorithm design for online optimization problems when compressed communication is applied?\n\n2. Without compressed communication, distributed convex online optimization has been well studied for time-varying graphs. Is it hard to extend from a fixed graph to a time-varying graph for the current algorithms?\n\n3. Stepsizes in the paper are designed with constant parameters given in the assumptions. It is usually not needed for standard single agent cases, nor distributed convex (online) optimization without compressed communication. Such parameter involvement requires the machines know more about the underlying problem, which is sometimes unavailable. Is this because of the purpose of analysis? ", "limitations": "NA", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The idea of the paper is simple, while the algorithm design and analysis are complicated. The paper is well written. \n\nThe paper claims that \"algorithm design and theoretical principle are challenging since the compression error, projection error, and consensus error will be coupled\", which is not very clear yet. For example, distributed convex optimization with compressed communication has been studied recent years; what is the challenge when moving from convex optimization to convex online optimization with compressed communication? ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "QzGHVb8jPcK", "reviewer": "Reviewer_wakL", "summary": "This work is an augmentation of distributed online gradient descent that uses an update-difference based compression scheme to reduce the communications load. Sublinear regret is proved for the case that objective functions are convex and strongly convex. Numerical evaluations establish the practicalities of the proposed approach.", "questions": "How do the developed regret bounds here compare against the tightest possible bounds in the literature? How is the compression ratio related to error in the gradient estimation error of the Lagrangian of the consensus-constrained optimization problem? How is it related to the error bound condition that is well-known in the mathematical programming literature (see many of Paul Tseng's works)? \n\nLuo, Z. Q., & Tseng, P. (1993). Error bounds and convergence analysis of feasible descent methods: a general approach. Annals of Operations Research, 46(1), 157-178.\n\nNedic, A., Ozdaglar, A., & Parrilo, P. A. (2010). Constrained consensus and optimization in multi-agent networks. IEEE Transactions on Automatic Control, 55(4), 922-938.", "limitations": "\nThe authors propose to employ difference compression together with DGD in order to come up with a communication-efficient algorithm. What I do not see is any technical novelty beyond applying this compression technique to a previously existing setting. Put more succinctly, there is no specific algorithmic innovation beyond applying a previously compression technique to a previously existing setting, and analyzing the error incurred by compression. For this reason, I do not believe this paper meets the bar for technical creativity/novelty required for NeurIPS.\n", "rating": 3, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\nThe numerical experiments only consider weak baselines, in the sense that they do not compare against ADMM or primal-dual method. Perhaps this is not the point, as the authors would like to underscore that the difference based compression is the best among a collection of alternatives. However, ECD-AMSGrad is a weak comparator, and many communication-efficient versions of ADMM or primal-dual method are available in the literature. See, for instance:\n\nLing, Qing, Yaohua Liu, Wei Shi, and Zhi Tian. \"Weighted ADMM for fast decentralized network optimization.\" IEEE Transactions on Signal Processing 64, no. 22 (2016): 5930-5942.\n\nBedi, A. S., Koppel, A., & Rajawat, K. (2019). Asynchronous saddle point algorithm for stochastic optimization in heterogeneous networks. IEEE Transactions on Signal Processing, 67(7), 1742-1757.\n\nLines 29-38: The authors only talk about local and global regret. However, in this setting, one should also talk about the tradeoff between global regret and constraint violation in the sense of consensus error, so as to make the link with primal-dual method and ADMM, which have rigorous and extensive theoretical support that they are superior to distributed gradient descent-based techniques. That this line of literature is overlooked completely so that a DOGD based development can be pursued is evidence to me that the paper exhibits some substantial gaps between the proposed algorithm and the state of the art. \n\nKoppel, A., Jakubiec, F. Y., & Ribeiro, A. (2015). A saddle point algorithm for networked online convex optimization. IEEE Transactions on Signal Processing, 63(19), 5149-5164.\n\nBoyd, S., Parikh, N., Chu, E., Peleato, B., & Eckstein, J. (2011). Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends® in Machine learning, 3(1), 1-122.\n\nMoreover, there are specific corrections of DGD that close the gap between it and approaches based on duality, which are also overlooked:\n\nShi, Wei, et al. \"Extra: An exact first-order algorithm for decentralized consensus optimization.\" SIAM Journal on Optimization 25.2 (2015): 944-966.\n\n\nLine 41: There are much more related works than [7]-[9] in the study of decentralized online convex optimization. Moreover, references [8] and [9] appear to be about constrained settings which are not particularly pertinent here. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "OhdYzuiizlz", "reviewer": "Reviewer_FBzg", "summary": "Paper considers distributed online convex optimization over an N-agent network. In particular, the authors consider three settings: full-feedback, where agents have access to the loss function, and (single- and two-point) bandit feedback, where agents only possess the values of the loss at points around the decision.\n\nThis work extends the DAOL method to accommodate compressed communication, and provides the first no-regret guarantees for w-contracted compressed distributed online optimization.\n\nGossip occurs over undirected networks with doubly-stochastic mixing. Numerical results provided for the diabetes detection dataset, using a simple online logistic-regressor with l2-regularization. ", "questions": "* Should certainly cite [1] when discussing difference compression schemes for distributed optimization. Also note that randomized gossip is typically used to refer to the classic pair-wise averaging with random edge activation of Boyd et al. [2].\n\n* The numerical results are interesting, but do not directly convey the advantage of decentralized learning, since fully-connected topologies still achieve the best regret with respect to the number of transmitted bits. It was shown in [3] that time-varying directed graphs can be used to improve the mixing speed of decentralized optimization algorithms over undirected graphs. Please discuss extensions to this setting, and I would be curious if push-sum based gossip (column stochastic) could be used instead of the doubly stochastic mixing to improve the numerical results in Figure 3.\n\n[1] Karimireddy et al., Error Feedback Fixes SignSGD and other Gradient Compression Schemes, ICML 2019.\n[2] Boyd et al., Randomized gossip algorithms, IEEE transactions on information theory 2006.\n[3] Assran et al., Stochastic Gradient Push for Distributed Deep Learning, ICML 2019.", "limitations": "Limitations are addressed in the conclusion (namely the dependence on the compression ratio in the regret bounds).", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nOriginality & Significance: while the proposed method is highly incremental, the analysis in this work is sufficiently original, and to the best of my knowledge, provides the first no-regret guarantees for w-contracted compressed distributed online optimizers.\n\nClarity & Quality: the work is clear, well written, and technically sound. Additionally, numerical results support theoretical intuition (i.e., that full-feedback and double-point bandit feedback have similar regrets, which are significantly better than single-point banding feedback). Additionally, advantage of proposed method compared to exact communication DAOL is well-established, improved convergence with respect to transmitted bits, at the cost of slightly worse time-horizon convergence.\n\nWeaknesses:\nIncremental algorithm: Method is an extension of DAOL to allow for compressed communication using standard compression schemes. Moreover, the method for dealing with compression is directly borrowed from the error-feedback framework.\n\nAssumptions: For the full-feedback setting: requires the bounded gradient assumption in the convex setting (however this can be eliminated it for strongly-convex objectives).\n\nUnfortunately, the experiments do not directly demonstrate the advantage of sparse communication topologies on the convergence speed, as the fully-connected network in Figure 3 still exhibits the best regret with respect to the transmitted bits.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "OZbFukqVOY2", "reviewer": "Reviewer_d9SB", "summary": "The paper proposes compressed distributed online convex optimization algorithms with full information feedback, one-point, and two-points bandit feedback.", "questions": "Unfortunately, the paper is out of my area of research and expertise. ", "limitations": "No limitations are found.", "rating": 5, "confidence": 1, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper proves the convergence of the proposed methods and provides computational evidence for the methods. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept