Towards Tight Communication Lower Bounds for Distributed Optimisation
Authors: Janne H. Korhonen
Dan Alistarh
Venue: NeurIPS 2021 Poster (2021)
Keywords: distributed optimization
lower bounds
algorithms
communication complexity
hardness of learning

Abstract: We consider a standard distributed optimisation setting where $N$ machines, each holding a $d$-dimensional function $f_i$, aim to jointly minimise the sum of the functions $\sum_{i = 1}^N f_i (x)$.  This problem arises naturally in  large-scale distributed optimisation, where a standard solution is to apply variants of (stochastic) gradient descent. We focus on the communication complexity of this problem: our main result provides the first fully unconditional bounds on total number of bits which need to be sent and received by the $N$ machines to solve this problem under point-to-point communication, within a given error-tolerance. Specifically, we show that $\Omega( Nd \log d / N\varepsilon)$ total bits need to be communicated between the machines to find an additive $\epsilon$-approximation to the minimum of $\sum_{i = 1}^N f_i (x)$. The result holds for both deterministic and randomised algorithms, and, importantly, requires no assumptions on the algorithm structure. The lower bound is tight under certain restrictions on parameter values, and is matched within constant factors for quadratic objectives by a new variant of quantised gradient descent, which we describe and analyse. Our results bring over tools from communication complexity to distributed optimisation, which has potential for further  applications.

Towards Tight Communication Lower Bounds for Distributed Optimisation
Dan Alistarh
Janne H. Korhonen
IST Austria & Neural Magic, Inc. dan. alistarh@ist. ac.at
IST Austria janne www.kkkoooonnnsscc.e.eee
Abstract
We consider a standard distributed optimisation setting where N machines, each holding a d-dimensional function fi. aim jointly minimise the sum of the functions Ee f((x)). This problem arises naturally in large-scale distributed optimisation, where a standard solution is to apply variants of (stochastic) gra- dient descent. We focus on the communication complexity this problem: our main result provides the first fully unconditional bounds total number of bits which need to be sent and received by the N machines to solve this problem under point-to-point communication, within given error-tolerance. Specifically, we show that C(Ndlogg d/Ne) total bits need to be communicated between the machines to find an additive e-approximation to the minimum of Σiz fi(x). The result holds for both deterministic and randomised algorithms, and, importantly, requires no assumptions on the algorithm structure. The lower bound is tight under certain restrictions on parameter values, and matched within constant factors for quadratic objectives by new variant of quantised gradient descent, which we describe and analyse. Our results bring over tools from communication complexity to distributed optimisation, which has potential for further applications.
Introduction
The ability to efficiently distribute large-scale optimisation over several computing nodes has been one of the key enablers of recent progress in machine learning, and the last decade has significant attention dedicated to efficient distributed optimisation. One specific area of focus has been on reducing the communication received by machines in order to jointly optimise an objective function. To this end, communication. efficient variants known for most classical optimisation algorithms, and in fact entire families of coamunication-compress
of distributed machine learning, i.e. the total number of bits sent and
methods have been introduced in the last decade.
We consider standard setting in which N machines communicate by sending point-to-pons binary messages to each other. Given dimension d, and domain RRd, each machine i given an input function f:: D R, corresponding to subset of the data, and the machines need to jointly minimise the empirical risk ΣN f((x) with either deterministic probabilistic guarantees on the output, within additive error tolerance. That is, at least one node needs to output z [0, 1]d such that
f((z) inf ZE 1
Σ f(())
This setting models data-parallel optimisation, and covers virtually all practical settings, from large- scale regression, to the training of deep neural networks.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

The key parameters governing communication complexity are the problem dimension d, the solution accuracy E, and the number of machines N. Most commumication- efficient approaches can be methods, such as the
linked to (at least) one of the following strategies: dimensiinality- sparsification of model updates [3, 14, 15, 17, 18), or projection [10, 34, 35], which attempt to reduce the dependency on the parameter d, quantisation methods [2, 27, 27, 31], whose rough goal is to improve the dependency on the accuracy E, and communiiation--reduciiii reducing the frequency of communication [5, 30, 36] relative to the number of optimisation steps, or communicating via point-to-poing messages via, e.g., gossiping [19, 24).
methods such as
Although these methods use diverse range of algorithmic ideas, upon close inspection, they all appear to have a worst-case total communication cost of at least Nd lolo/(d/E) bits, even for simple convex d- d-dimensional problems, and even for variations of the above standard setting. For instance, even though dimensionnliit--eddeeii
or quantisation methods might send asymptotically less than d bits per algorithm iteration, they have to compensate for this in the worst case by running for asymptotically more iterations. (See e.g. [2] for simple example of this trade-off.) It therefore natural to ask whether this complexity threshold is inherent, or whether it can be circumvented via improved algorithmic techniques. This is our motivating question.
A partial answer is given by the foundational work of Tsitsiklis and Luo [32], who gave a lower bound of ((dlog(d/E)) in the case where two nodes communicate optimise over quadratic functions. Their argument works by counting the total number of possible e-approximate solutions in the input volume: communication has to be at least the logarithm of this number. Subsequent work has considered more complex input functions, e.g. [41], or stronger notions of approximation [33]. The original argument generalises directly to N nodes under the strong assumption that each node has to return the correct output: in this case, communication complexity is asymptotically N times the 2-node cost [11].
In this context, it is surprisingly still unknown whether the ([Nd log(d/s)) communication threshold actually inherent for distributed optimisation in the standard case where only single node needs to return the output. This question is not just of theoretical interest, since there are many practical settings in large-scale optimisation, such as federated learning [20] or the parameter server setting [23]. where only single node coordinates the optimisation, and knows the final answer. This raises the question whether more communication-effiicee
algorithms are possible such settings, in which communication cost is key concern. At the same time, it is also not clear under which conditions algorithms achieving this asymptotic complexity exist.
1.1 Contribution
In this paper, we take a significant step towards addressing these questions. Our main result is the first unconditional lower bound on the communication complexity of distributed optimisation in the setting discussed above, showing that it is impossible to obtain significant improvement in communication cost even if only one node (the "coordinator") learns the final output. Specifically, even if the input functions f; the nodes promised to be quadratic functions + fall= x= for some constant Be > 0, then any deterministic or randomised algorithm where at least one node learns solution to (1) requires
2 ((Ndlog
3d Ne
total bits to be communicated
for 3 = N, as long as parameters satisfy Ad/N2s = 2(1). We emphasise that the lower bound requires no assumptions on the structure of the algorithm or amount of local computation. We also note that in most practical settings, the parameter dependency requirement is satisfied, as the number of parameters d is significantly larger than the number of machines N multiplied by the error tolerance e - moreover, a non- non-trivial dependence between 3, d, N and E is required for the lower bound to hold. We discuss this in detail below.
Our results start from the classic idea of linking communication complexity with the number of quadratic functions with distinct minima in the domain [32]. To extend this approach to randomised (stochastic) algorithms and to the multi-node case N' >> 2, we build new connections to results and techniques from communication complexity [21]. Such connections have not to our knowledge been explored in the context of (real-valued) optimisation tasks. Our work thus provides a template and basic toolkit for applying communication complexity results to distributed optimisation. As

---

further applications, we improve the main lower bound to 22 log(///)))))) for the deterministic case if some node required ouiput both the approximate minimiser & and the value of the sum E fi(z), as well as prove stronger lower bounds in the more challenging non-convex case (see Section 5 and Appendices A and B.)
To complement this lower bound, we show that for strongly convex and strongly smooth functions, distributed optimisation can be done using deterministic quantised gradient descent with
o Nd log log
3d total bits communicated,
where Ei=1 Ji is a-strongly convex and 3-strongly smooth, and ς. = BB/cx is the condition number. This is, to knowledge, the first tight upper bound for communication cost of quantised gradient descent on quadratic functions, as well as the first upper bound that does not require all-to-all broadcast. In particular, for constant condition number K, this matches our main lower bound when d >> N, e.g. d = ((N++)) for constant > 0.
Our algorithm builds on prior quantised gradient descent implementations [2, 25], however, to achieve a tight bound, we need to (a) ensure that our gradient quantisation is sufficiently parsimonious, using Old log x) bits per gradient, and (b) avoid all-to-all exchange of gradients. For (a), we specialise a recent lattice-based quantisation scheme which allows arbitrary centring of iterates [11], and for (b), we use two-stage quantisation approach, where the nodes first send their quantised gradients to the coordinator, and the coordinator then broadcasts the carefully quantised sum back to nodes. In Appendix D, we further show that this running time can be improved using randomisation when 3d/Ne is small, using a simple sub-sampling approach.
1.2 Discussion
Implications. While the focus of our work is theoretical, our results show that current practical algorithmic approaches are already close to worst-case optimal. Specifically, we show that it impossible to obtain algorithms with communication cost e.g. O(Nd + d log d/e) by "pipelining" communication costs across algorithm iterations, performing additional local optimisation steps, or by introducing entirely new algorithmic techniques.
At the same time, our upper bound conceptually shows that, for quadratic functions, carefully quantised gradient descent can cost asymptotically the same as broadcasting the solution, while the lower bound shows that this cost is inherent. Specifically, broadcasting a single d-dimensional point from [0, 1]d within accuracy 1)/3)1/2, as required for E-approximation of the sum Σ f((z). to N nodes costs Q(N di log(Sd/ bits [11], and thus the communication cost of our algorithm is tight. The lower bound shows that little can be gained by avoiding this broadcast.
Extensions. Following Tsitsiklis and Luo [32] and Magnússon et al. [25], we have assumed above that the range of the input functions is [0, 1jd, and the global objective the sum of input functions. However, the results apply even with some modifications to the setting.
First, we can consider case where the global objective is the average I/NE fi instead of sum. In this case, the lower bound holds with f = So. and the upper bound holds as stated, with being the smoothness parameter of the average. Second, the results can be extended for any compact convex domain of input functions, with the precise bounds depending on the volume and diameter of the domain for the lower and upper bound, respectively. For example, one can easily verify that, for inputs defined over the unit sphere, the bounds still hold, but without the factor inside the logarithm.
Limitations. We note that there still remains small gap between our upper and lower bounds. To illustrate this, consider optimisation of the average of quadratie functions x + ||x -ar-a x²1 11 defined over the unit hypereube [0, 1]d;
; in this case, the bounds take the form
d 2 Nd Ne
and ONd 2
Moreover, the lower bound requires the parameter dependency 3d/N2 = 12(1) to hold. We note that we cannot fully get rid of this requirement: specifically, we show in Appendix D, we can use a simple input sub- sampling approach to show that, if we have 3d/= = O(N)) for 8 < 1, then problem (1) can be solved with O N log Bd/e) total bits communicated using a randomised
algorithm, asymptotically less than dictated by the general lower bound.
3

---

Table I: Comparison of existing upper and lower bounds total communication required to solve (1). The label 'BC' denotes results for broadcast model, where each sent message seen by all nodes, and 'MP' denotes results for passage-passing model, where only the recipient of the message sees it.
Output
Model
Guarantee
Reference
Lower bound, quadratic inputs
log Ad
all nodes
2-node Det.
[32]
log =
5d
all nodes
BC
Rand.
[13]
(N dd
all nodes
MP
Rand.
[11]
dd
(NNllog No
single node
MP
Rand.
this work, $4
Upper bound, constant
O(Ndlog Ad)
all nodes
BC
Rand.
[2. 22]
Upper bound, general inputs
O O(ddlog(md) log Ad
all nodes
2-node
Det.
[32]
O log(noo(dd)) log Sd
all nodes
BC
Det
[25]
O(Ndx dx log log Ad)
all nodes
MP
Det.
this work, $6
second question our current techniques do address is the precise dependency on the condition number Our lower bound techniques do no benefit from large so new ideas would be required to address this question.
On the upper bound side, the linear dependency on x appears to be inherent for our quantised gradient descent algorithm. However, very recent progress on quantised second-orde methods [1, 15] shows that it is possible to improve this dependency in general, by leveraging second-order information together with quantisation. Specifically, Alimisis al. [1], Islamov et al. [15] provide complex quantised variants of Newton-type algorithms, which can achieve linear-in-d communication cost per iteration, under certain assumptions. Thus, these algorithms can asymptotically reach the optimal Nd Nologg( ddc) complexity threshold implied by our lower bounds, within logarithmic factors in и and other terms, for wider range of inputs. This comes at the relative cost more complex algorithm, and significant additional local computation.
2 Related work
Optimisation lower bounds. The first communication lower bounds for variant of (1) were given in the seminal work Tsitsiklis and Luo [32], who study optimising sums convex functions in two-machine setting. For deterministic algorithms, they prove that R(d (og(d///)))) bits necessary. Extensions are given by Zhang et al. [41] and Davies et al. [11]. Please see Table 1.
The basic intuition behind these lower bounds is that node without information about the input needs to receive (2d log((dd/))) bits, as otherwise the node cannot produce sufficiently many different output distributions to cover all possible locations of the minimum (cf. Lemma 2.) It worth emphasising that their bound is on the received bits of the output node, and does not directly imply anything for other nodes; for example, algorithm where each node transmits O(d (ougogd/e))) (Sud/e)//N) bits is not ruled out by these previous results. Generalising their approach to match results seems challenging, the solution, and (b) ensure that no node can use their local input as a source of extra information.
would have to (a) explicitly require that all nodes output
The recent work of Vempala et al. [33] focuses on the communication complexity of solving linear systems, linear regression and related problems. The results are based on communication complexity arguments, similarly to lower bound. The main technical differences are that (a) linear regression instances over bounded integer weight matrices have a natural binary encoding, and (b) importantly, the approximation ratio for linear regression is defined multiplicativelyy not additively; the main consequence is that the hard instance in their case is the exact solution of the linear system.
Statistical estimation lower bounds. In statistical estimation, nodes receive random samples from some input distribution, and must infer properties of the input distribution, e.g. its mean. Specifically, for mean estimation, there are statistical limits on how good an estimate one can obtain from limited number of samples, although inputs are drawn from a distribution instead of adversarially. Concretely, the results of Shamir [29] and Suresh et al. [31] apply only to restricted types of protocols. Garg

---

et al. [13] and Braverman et al. [7] give lower bounds for Gaussian mean estimation, where each node receives s samples from a d-dimensional Gaussian distribution with variance σ². The latter reference shows that to achieve the minimax rate o² d/Ns s on mean squared error requires (2(Nd) total communication. These results do not imply optimal lower bounds for our setting.
Lower bounds on round and oracle complexity. Beyond bit complexity, one previous setting assumes that nodes can transmit vectors of real numbers, while restricting the types of computation allowed for the nodes. This is useful to establish bounds for the number of iterations required for convergence of distributed optimisation algorithms [4, 28], but does not address the communication cost of a single iteration. A second related but different setting assumes the nodes can access their local functions only via specific oracle queries, such as gradient or proximal queries, and bound the number of such queries required to solve an optimisation problem [38, 39].
Upper bounds. There has been a tremendous amount of work recently communication--efiiieen optimisation algorithms in the distributed setting. Due to space constraints, we focus on a small selection of closely-related work. One critical difference relative to practical references, e.g. [2], is that they usually assume gradients are provided as 32-bit inputs, and focus on reducing the amount of communication by constant factors, which is reasonable in practice. One exception is [31], who present series of quantisation methods for mean estimation on real-valued input vectors. Recently, [11] studied the same problem, focusing on replacing the dependence on input norm with a variance dependence. We adapt their quantisation scheme for our upper bound.
Tsitsiklis and Luo [32] gave deterministic upper bound in two-node setting, with O (nd log(rd)) (og//)/e)) total communication cost. Recently, Magnússon et al. [25] extended this to N-node case in the broadcast model, with O (Nnd log([)) log(šd/E)) total communication cost. For randomised algorithms and constant condition number, better upper bound of O(Nd log log(Sd/e)) total communication cost in the broadcast model follows by using QSGD stochastic quantisation [2] plugged into stochastic variance-reduced gradient descent (SVRG) [16]. See Künstner [22] for detailed treatment. While these algorithms are for the broadcast model, they can likely be imple- mented in the message-passing model without overhead by using two-stage quantisation; however, our algorithm also obtains optimal dependence on deterministically.
3 Preliminaries and background
Coordinator model. For technical convenience, we work in the classic coordinator model [6, 12, 26]. equivalent to the message- -aagggggassinggggg setting. In this model, we have N nodes as well as a separate coordinator node. The task is to compute the value of function I: BN + A, where B and A are arbitrary input and output domains; each node i = 1.2,..... N receives an input b; E B. There is a communication channel between each of the nodes and the coordinator, and nodes can communicate with the coordinator by exchanging binary messages. The coordinator has to output the value [b,, bg...., .., by). Furthermore, all nodes, including the coordinator, have access to a stream of private random bits.
More precisely, we assume without loss of generality that computation is performed as follows:
(1) Initially, each node .., N receives the input 6,. The coordinator and nodes i
1, ,.,.....N N receive independent and uniformly random binary strings r, r E {0, 13, respectively, where e is a constant.
(2) The computation then proceeds in sequential rounds, where in each round, (a) the coordinator first takes action by either outputting an answer, or sending a message to a single node i, and (b) the node that received message from the coordinator responds by sending a message the coordinator.
A transcript for node is list of the messages it has sent and received. A protocol 11 is mapping giving the actions of the coordinator and the nodes; for the coordinator, the next action a function of its transcript far and the private random bits and for node i, the next action is function of its input 6, its transcript so far and the private random bits r;. The protocol II also determines the number of random bits the nodes receive.
We say that a protocol IT computes r: B. + A with error p for all (b,, b2,.b,..., .,) E BN the output of II is [(bb, b2....,br) bb) with probability at least p. The communication complexity of
5

---

protocol II is the maximum number of total bits transmitted by all nodes, i.e. the total length of the transcripts, on any input (b), ,2....,byy .b) E BN and any private random bits of the nodes.
While the model definition may appear restrictive, the protocol restrictions do not matter when the complexity measure is the total number of bits exchanged. Parallel computation he sequentialised, and direct messages between non-coordinator nodes can be relayed via the coordinator, with at most constant factor overhead. Furthermore, note that the model is nonaniform, i.c. each protocol is defined only for specific functions I:: B. + A and specific input and output sets B and A. Any uniform algorithm working for range of parameters induces series of nonuniform protocols, regardless of the computational cost, so lower bounds for coordinator model translate to uniform algorithms.
Communication complexity. We now recall some basic definitions and results from communication complexity. In the following, we assume that sets B and A are finite, as this the standard setting of communication complexity.
For a function : BN A, the deterministic communication complexity CC(T) is the minimum com- munication complexity of deterministic protocol computing I'. Likewise, the 8-error randomised communication complexity RCC (T) is the minimum communication complexity of protocol that computes with error probability 8.
For distribution over BN, we define the ò-error y--istributional communication complexity of r. denoted by (T') as the minimum communication complexity of a deterministie protocol that computes r with error probability 5 when the input is drawn from μr. Similarly, the 5-error y-distributional expected communication complexity of r, denoted by ED (T), is the minimum expected communication cost protocol that computes I with error probability ó, where the expectation is taken over input drawn from and the random bits of the protocol.
Yao's Lemma [40] relates the distributional communication complexity the randomised communi- cation complexity; see Woodruff and Zhang [37] for a proof in the coordinator model.
Lemma (Yao's Lemma). For For function I' and
we have RCC* (T') Z max, DfT(T).
Properties of convex functions. Recall that continuously differentiable function f is B-(strongly) smooth if [x) Vf(v)lle S B1 y/|2. and a-strongly convex if (V.(()) [ff()))V[(())) (a (x-y)
f(v))) alIx pll- E. for all æ and y in the domain of f. For a-strongly convex and 3-strongly smooth function f. we say that f has condition number x B a... If fi is a1 ot-stlyyyly convex and 31 Strooryy smooth and f2 is -g-strongly convex and 32-strongly smooth, then fi + fz is (a1 + a: --stssooolly convex and (31 + Bttonlyy smooth.
quadratic function fxx = B||xr - 111x--113 + B-strongly convex and f3-strongly smooth. For > if ((x) < E, then |x- - x² 12 S (e/B)1/2. A sum of quadratics F(x) Σ Vy Rdd and aj for j ... is quadratic function F(x) Aliz x=1 + C, where C
1 aj || -vsll, where
is a constant and x² = Σ5= ayy; /A is the minimum of F.
Point packing, We will make use of the following elementary result, which bounds the number of points we can pack into [o, 1 while maintaining minimum distance between all points.
Lemma 2 (Tsitsiklis and Luo 32). For 8 > 0 and d 2 1, there is a of points S C [0, such that (1) || vll2 8 for all distinct x. y E S, and (2) |S| 2 /C5y,, where C (me (tee223/22 is constant.
4 Main lower bound
We now prove our main result, by giving a lower bound for communication complexity of any algorithm solving (1) that holds for both deterministic and randomised protocols.
Theorem 3. Given parameters N, d, E, Bg and 3 SoN satisfying d3 2B/N22 2211, any pro-
tocol solving (1) for quadratic input functions x + Bullæ zull3 has communication complexity 2 Nd 1og(3d/3
To formally apply communication complexity tools, we will prove a lower bound for a discretised version of (1) where both the input and output sets finite which will imply Theorem 3. Let N,

---

d, E. and 3 be fixed, assume d3 4 = 9I(1.. Furthermore, let S be the set given by Lemma 2 with 5 = (3/ and let T _ [0, 1 be an arbitrary finite set of points such that for any x E [O, 1]² there is a point E T with || t|| < (E/48) By assumption d3/N2 = 2Q11, the set S has size [log [ = (5d/)e)) Again, for convenience, assume 2 |S]. and
least Let
identify each binary string b E {0, 1} with an element T(b) E S.
Definition 4. Given parameters N, d, E, B, we define the problem MEAN d.N as follows:
The node inputs are from {0, and
Valid outputs for input (b1, b2.... bN) are points t E T that satisfy the condition 1|x t|la (2/ where x" Ei= T(b.)/ is the average over inputs.
First, we observe that any algorithm for solving (1) can be used to solve MEAN 5.8 d.N'
Lemma 5. For fixed N, d, E, So and B SoN, any randomised protocol solving (1) for quadratic functions x + Bu || zoll2 with error probability 1/3 has communication complexity at least 5.844)
RCC (MEANT.N d.N
Proof. Let II be protocol solving (1) with communication complexity C and error probability 1/3. We show that we can use solve MEAN with total communication cost C' and error probability 1/3, implying the claim. Given input (b,, bg...., by) for MEAN
N.N nodes can simulate the protocol with input functions f((x) 8 x - (1:)] By the properties of quadratic functions, have F F(x) Ex= fix) B1[ x= 1 + C, where x" Σm= N Thus, the output y of satisfies |y x= 1|2 - (E/B)1/2. 1/2 The coordinator now outputs the closest point t T to y. We
z(be),
therefore have
||~" l|12 = |
1112 - ||=" v112 + llv 4l2 s 2(e/8) =A47/31122
n
The next step is to prove a lower bound on the communication complexity of MEAN d,N- We do this by using a symmetrisation technique of Phillips et al. [26]. via reduction the expected communication complexity of a two-party communication problem where one player has to learn the complete input of the other player. Specifically, (Alice) receives a binary string b E {0, 13 of length d, and the task is for player 2 (Bob) to output b. Let Cp be a distribution over binary strings b E {0, 1}4d where each bit is set to with probability and with probability with public randomness, i.e. when Alice and Bob have access to the same string of random bits:
the two-player problem called 2-BITS,, player
p. The following lower bound for 2- 2-BITS, holds even for protocols
Lemma 6 ([26)). ED 1/3 (2-BITS.) = (ddp log
We now show that solving MEAN d.N requires roughly N times the expected communication com- plexity of solving 2-BITSa for d = D and p 1/2. Lemma 7, For N, d, E, and B satisfying d3/N2 2(1), we have
(MEANT 2(N ED G,/2
(2-BITSp) = =((Ndlog(B//Ne))
Proof. Let μ denote distribution on IT, {0, where each D-bit string is selected uniformly random, and let ( be uniformly random 1), D. We will prove that
D (MEAN d, 2(N ED / (2-BITSp))
Since ED 1/3 (2-BITSp) = Q(D) by Lemma 6, the claim follows by Yao's Lemma.
Suppose now that we have a deterministic protocol II, for MEAN d.v with worst-case communication cost C and error probability 1/3 on input distribution μ. Given Th, we define 2-player protocol T2 with public randomness for 2-BITSp as follows; assume that Alice is given b E {0, 1] input.
7

---

(1) Alice and Bob pick a random index E [N] uniformly at to select random node using the shared randomness. Without loss of generality, we can assume that they picked node i 1.
(2) Alice and Bob simulate protocol II,, with Alice simulating node 1 and Bob simulating the coordinator and nodes 2.3..... .N. For the inputs b1, b2, ...., ...,,,, bN to II, Alice sets b₁ and Bob selects the inputs b2, b,, Messages II, sends between the coordinator and node 1 communicated between Alice and Bob, and all other communication simulated by Bob internally.
...,,, nn uniformly at random by using the public randomness.
(3) Once the simulation is complete, Bob knows the output t E T of II which satisfies ||t - 2*112 S (2/ where 2" = Ei= r(b:)/N.
As the final step, we show that Bob can now recover Alice's input from t. Let EE (bb:)/(N-1) be the weighted average of points r(b2), r(bs),....... ...b) r(bx). We now have that N2 (N 1)y r(b;) by simple calculation.
Since ||t - = 211 & (e/3))/2, it follows that
[|(NL - (N - 1)y) - ((b))112 = ||Ni - (N - 1)y NN + N= - -b(bill2
|| N=* + Nz* (N- 1)y -(b1)ll2
= ||Nt - N22 = -Nit - 20112 S ((E
Since the distance between any two points in S is least 3EN we have that r(b1) is the only point from S within distance (E/3) from N (N 1)y. As Bob knows both and T(62), (bs)...,
after the simulation, he can recover the point x and thus infer Alice's 's input.
Now let us analyse the expected cost of II2 under input distribution Ç. First, observe that since the simulation runs II, on input distribution μu, the output y is correct with probability 2/3, and thus the output of II is correct with probability 2/3. Now let CTT, be the worst-case communication cost of I1 and let Cn,, (bi,.... by) and CT,,.(bi,.... bx) denote the total communication cost and the communication used by node in IT, input b1, .... dv. respectively. Finally, let Cri, (b, r) be random variable giving the communication cost of πl on input b and random bits r.
Now have that
N
Cl,,abbi,.... bN)
E [C,, (b1,T)]
Σ
20th
20
(Cn, (b1,r)] = Σ
2D
Σ
N2
61E011130
ba ba.nn i=1
1
Σ
CT (b...,, bN)
N
2ND
b1.b2.....by by
2=1
1
Σ
On (bi,b,,...,bu 5
2ND On, Cn b1.b2...,by
Σ
N
2ND
by. by
Since MEANS. with error probability 1/3, we have that (MEEN d.N. 2 N N. (2-BITS))) completing the proof.
BS,,,,(Cn,,bn r)] 2 / (2-BITSp), and the argument holds for any protocol 11, solving
Theorem 3 now follows immediately from Lemmas and 7. The result can be generalised for arbitrary convex domains ID C Rd as Q(N log s), given point packing bound s for ID as in Lemma 2.
5 Deterministic lower bound
While there remains small gap between our main lower bound of Theorem 3 and the deterministic quantised gradient descent Section 6, we can show that the gap cannot be closed by deterministic algorithms where the coordinator learns the value of objective function in addition the minimiser

---

I. That is, our quantised gradient descent is the communication-opiimal deterministic algorithm for problem (1) for objectives with constant condition number.
The exact result, whose proof can be found in the Appendix A, is as follows.
Theorem Given parameters N, Bg and B N satisfying dB/e Q11), any deterministic protocol solving for quadratic input functions æ + Bullz - zoll has communication complexity
e)), if the coordinator is also required to output estimate r E IR. for the minimum
function value such that Σ f((z) S E f((z) +
6 Communication-optinal quantised gradient descent
We now describe in detail our deterministic upper bound. Our algorithm uses quantised gradient descent, loosely following the outline of Magnússon et al. [25]. However, there are two crucial differences. First, we use carefully-calibrated instance of the quantisation scheme of Davies al. [11] to remove log factor from the communication cost, and second, we use use two-step quantisation to avoid all-to-all communication.
Preliminaries on gradient descent. We will assume that the input functions f:: [0, R are oo-Strongly convex and -t-strongly smooth. This implies that F Σ Si a-strongly convex and B-strongly smooth for No and / = No. Consequently, the functions ʃ; and F have condition number bounded by K = B/a.
Gradient descent optimises the sum Σ fz) by starting from an arbitrary point x(() E [0, 1j4, and applying the update rule
N
(1+1) 10))
Vi(("!))
where y > 0 is parameter. It is well-known, e.g. [8], that GD converges at exponential rate in (R 10-1) 1)/(( for step size = 2/(a: (a+ + (3).
Preliminaries on quantisation. For compressing the gradients the nodes will send to coordinator, we use the recent quantisation scheme Davies et al. [11]. Whereas the original uses randomised selection of the quantisation point to obtain unbiased estimator, we can use a deterministic version that picks an arbitrary feasible quantisation point (e.g. the closest one). This gives the following guarantees:
Corollary 9 ([11]). Let R and e be fixed positive parameters, and q E Rd be an estimate vector, and B E N be the number of bits used by the quantisation scheme. Then, there exists determin- istic quantisation scheme, specified by function Qe, Rd x Rd + Rdd, an encoding function enc,,R: : TRd + 1 and a decoding function dec,, TRd x {0. - Rd, with the following properties:
(1) (Validity.) dec;, R(g, enc, (x)) = Q2 for all x, E IRd with || - 4ll2 S R.
(2) (Accuracy.) (1Q,,n(z, 4) x1I2 S e for all a. E Rdd with || - دala S R.
(3) (Cost.) If== XR for any 1, the bit cost of the scheme satisfies B Oddlog='))
Algorithm description. We now describe the algorithm, and overview its guarantees. The full description and analysis are available in Appendix C.
We assume that the constants a and are known all nodes, so the parameters of the quantised gradient descent can be computed locally, and use W to be an upper bound on the diameter on the convex domain D. e.g. W d'//2 if D = [0, 1]d. We assume that the initial iterate 2:(0) is arbitrary, but the same all nodes, and set the initial quantisation estimate ( each i the origin.
We define the following parameters for the algorithm. Let = 2/(a + B3 and & = k-1 be the step
x+1
size and convergence rate of gradient descent, and let W such that [,, x² S W. We define
R = 2
8 = E(1 f)4
w'
+

---

where will be the convergence rate of our quantised gradient descent, and ó and R will be parameters controlling the quantisation at each step. For the purposes of analysis, we assume that 2 2. Note that this implies that 1/3 S & < 1, / 1, and 0 < 8 <<1 1.
The algorithm proceeds in rounds t 1, ...,, T. At the beginning of round t 1, each node i knows the values of the iterate 2;(*) the global quantisation estimate (()), and its local quantisation estimate q;" (t) for 1,2...., N. At step i, nodes perform the following steps:
(1) Each node i updates its iterate x((+1) 20)) -1
(2) Each node i computes its local gradient over x((+1), and transmits it in quantised form to the coordinator as follows. Let E 8R(++))22 /2N and P1 R(+1)/A /N.
(a) Node computes (((((++1)) locally, and sends message my enC (Vi(((())))) to
the coordinator.
(b) The coordinator receives messages m, for i = 1, ..., N, and decodes them as q
(t+1)
(t) m,,). (,)). The coordinator then computes n((+1) Σ 0 (t+1)
1e
(3) The coordinator sends the quantised sum of gradients to all other nodes as follows. Let 62 (1(++)) 2 and p2 = (
(a) The coordinator sends the message m = e2: (r((+22) to each node i. (b) Each node decodes the coordinator's message as (1+11 dec (9 m).
After round T, all nodes know the final iterate x(())
Guarantees. The key technical trick behind the algorithm is the extremely careful choice of parameters for quantisation at every step. This balances the fact that the quantisation has to be fine enough to ensure optimal GD convergence, but coarse enough to ensure optimal communication cost. Overall, the algorithm ensures the following guarantees, whose proof is provided in Appendix C. Theorem 10. Let > O, dimension d, and convex domain D C R& of diameter W be fixed. Given N nodes, each assigned a function f;: D > R such that F = EN and B-smooth, the above algorithm converges point x(T) with F(a(T) F(x*) + using
i=l fe is c-sttrongly convex
o dr log ko log
3W ) bits of communication.
Discussion and future work
We have provided the first tight bounds on the communication complexity of optimising sums of quadratic functions in the N N-party model with coordinator. Our results are potoritmm-ineppeeeeen and immediately imply the same lower bound for the practical parameter server and decentralised models of distributed optimisation.
In terms of future work, we expect that the randomised lower bound could be improved to match the deterministic even for small d, possibly via reduction from suitable gap problem in communication complexity (e.g. Chakrabarti and Regev [9]). Another avenue for future work is to investigate tight upper and lower bounds in the case where the functions being optimised are not quadratics, as isolating the "right" dependency on the condition number does not appear immediate. The recent results of [1, 15] suggest that the dependency on the condition number may be quite small, and therefore hard to capture without explicit limitations on the algorithm. Finally, understanding the exact complexity of optimisation in the broadcast model, where each message sent is seen by all nodes, and the complexity is measured by the number of bits sent, remains open.
Acknowledgments and Disclosure of Funding
We thank the NeurIPS reviewers for insightful comments that helped us improve the positioning of our results, as well as for pointing out the subsampling approach for complementing the randomised lower bound. We also thank Foivos Alimisis and Peter Davies for useful discussions.
This project has received funding from the European Research Council (ERC) under the European Union's 's Horizon 2020 research and innovation programme (grant agreement No 805223 ScaleML).
10

---

References
[1] Foivos Alimisis, Peter Davies, and Dan Alistarh. Communication-effcieenn distributed optimiza- tion with quantized preconditioners. arXiv preprint arXiv:2102.07214, 2021.
[2] Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovie. QSGD: Communication--ffiieenn SGD via gradient quantization and encoding. In Advances Neural Information Processing Systems (NIPS 2017), 2017.
[3] Dan Alistarh, Torsten Hoefler, Mikael Johansson, Nikola Konstantinov, Sarit Khirirat, and Cedric Renggli. The convergence of sparsified gradient methods. Advances in Neural Information Processing Systems (NeurIPS 2018), volume 31, 2018.
[4] Yossi Arjevani and Ohad Shamir. Communication complexity of distributed convex learning and optimization. In Advances in Neural Information Processing Systems 28 (NIPS 2015), pages 1764, 2015.
[5] Debraj Basu, Deepesh Data, Can Karakus, and Suhas Diggavi. Qsparse-local-SGH Dis- tributed SGD with quantization, sparsification, and local computations. In Advances Neural Information Processing Systems (NeurIPS 20/9), volume 32, 2019.
[6] Mark Braverman, Faith Ellen, Rotem Oshman, Toniann Pitassi, and Vinod Vaikuntanathan. A tight bound for set disjointness in the posssage-passing model. In Proc. 54th Annual Symposium on Foundations of Computer Science (FOCS 2013), pages 668-677. IEEE, 2013.
[7] Mark Braverman, Ankit Garg, Tengyu Ma, Huy L Nguyen, and David P Woodruff. Communica- tion lower bounds for statistical estimation problems via a distributed data processing inequality. In Proceedings of the 48th Annual ACM symposium on Theory of Computing (STOC 2016), pages 101 1011- 2016.
[8] Sébastien Bubeck. Convex Optimization: Algorithms and Complexity. Now Publishers, 2015,
[9] Amit Chakrabarti and Oded Regev. An optimal lower bound the communication complexity of Han---aammmitttannne In Proc. 43rd ACM Symposium on Theory of Computing (STOC 2011), 2011. 161:00.145/1199366.199333 1994444444
[10] Trishul Chilimbi, Yutaka Suzue, Johnson Apacible, and Karthik Kalyanaraman. Project Adam: Building an efficient and scalable deep learning training system. In / 1/th USENIX Symposium on Operating Systems Design and Implementation (OSDI 2014), pages 571-582, 2014.
[11] Peter Davies, Vijaykrishna Gurunanthan, Niusha Moshrefi, Saleh Ashkboos, and Dan Alistarh. New bounds for distributed mean estimation and variance reduction. In Proc. 9th International Conference on Learning Representations (ICLR 2021), 2021.
[12] Danny Dolev and Tomás Feder. Determinism nondeterminism in multiparty communication complexity. SIAM Journal on Computing, 21(5):889-89) 1992.
[13] Ankit Garg, Tengyu Ma, and Huy Nguyen. On communication cost of distributed statistical estimation and dimensionality. In Advances in Neural Information Processing Systems 27 (NIPS 2014). 2014.
[14] Eduard Gorbunov, Dmitry Kovalev, Dmitry Makarenko, and Peter Richtárik. Linearly converg- ing error compensated sgd. In Advances in Neural Information Processing Systems (NeurIPS 2020), 2020.
[15] Rustem Islamov, Xun Qian, and Peter Richtárik. Distributed second order methods with fast rates and compressed communication. arXiv preprint (arXiv:2102.07755) 2021. Accepted to ICML 2021.
[16] Ric Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In Advances in neural information processing systems (NIPS 2013), 2013.
[17] 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-3261. PMLR, 2019.
11

---

[18] Sarit Khirirat, Mikael Johansson, and Dan Alistarh. Gradient compression for communication limited convex optimization. In 2018 IEEE Conference on Decision and Control (CDC), pages 166-171, 2018. 1oi: 101.01009/CC. 8.811965....
[19] Anastasia Koloskova, Sebastian Stich, and Martin Jaggi. Decentralized stochastic optimization and gossip algorithms with compressed communication. In International Conference on Machine Learning, pages 1478-3487, PMLR, 2019.
[20] Jakub Konečný, H. Brendan McMahan, Felix X. Yu, Peter Richtarik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. In NIPS Workshop on Private Multi-Party Machine Learning, 2016.
[21] Eyal Kushilevitz and Noam Nisan. Communication Complexity. Cambridge University Press, 1996. 1011100.017/CB8978800 1574948.
[22] Frederik Künstner. Fully quantized distributed gradient descent. Master's thesis, École polytech- nique fédérale de Lausanne, 2017. URL httt::///nfosccennnce epfl (reeoord/345444
[23] Mu Li, David G Andersen, Jun Woo Park, Alexander Smola, Amr Ahmed, Vanja Josifovski, James Long, Eugene J Shekita, and Bor- Bor-Yiing Su. Scaling distributed machine learning with the parameter server. In Proc. 1/th USENIX Symposium on Operating Systems Design and Implementation (OSDI 2014), pages 583-598, 2014.
[24) Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsieh, Wei Zhang, and Ji Liu. Can decentralized algorithms outperform centralized algorithms? A case study for decentralized parallel stochastic gradient descent. In Advances in Neural Information Processing Systems (NIPS 20/7), 2017.
[25] S. Magnússon, H. gence of distributed learning and optimization under limited communication. In Proc. 53rd Asilomar Conference on Signals, Systems, and Computers (ACSSC 2019), 2019. doi: 10::10.11000 1001111EECTTTT444442000000 201.99990..
and N. Li. On maintaining linear conver-
[26] Jeff M Phillips, Elad Verbin, and Qin Zhang. Lower bounds for number-in-hand multiparty communication complexity, made easy. In Proc. 23rd Annual ACM-SIAM symposium on Discrete Algorithms (SODA 2012), pages 486-501, 2012.
[27] Ali Ramezani Kebrya, Fartash Faghri, Ilya Markov, Vitalii Aksenov, Dan Alistarh, and Daniel M Roy. Nuqsgd: Provably communication-effici data-parallel sgd via nonuniform quantization. Journal of Machine Leurning Research, 22 (2(114):1-4 14):1-43, 2021.
[28] Kevin Scaman, Francis Bach, Sébastien Bubeck, Yin Tat Lee, and Laurent Massoulié. Optimal algorithms for smooth and strongly convex distributed optimization in networks. In Proceedings of the 34th International Conference on Machine Learning (ICML 2017), pages 3027-3036, 2017.
[29] Ohad Shamir. Fundamental limits of online and distributed algorithms for statistical learning and estimation. Advances in Neural Information Processing Systems 27 (NIPS' 2014), pages 171- 2014.
[30] Sebastian Urban Stich. Local SGD converges fast and communicates little. In International Conference Learning Representations (ICLR 2019), 2019.
[31] Ananda Theertha Suresh, Felix Yu, Sanjiv Kumar, and H Brendan McMahan. Distributed mean estimation with limited communication. In Proceedings of the 34th International Confer- ence on Machine Learning (ICML 2017), pages 3329-3337. JMLR. org, 2017.
[32] John N. Tsitsiklis and Zhi-Quan Luo. Communication complexity of convex optimization. Journal of Complexity, 3(3):231-243, 1987.
[33] Santosh S. Vempala, Ruosong Wang, and David P. Woodruff. The communication complexity of optimization. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA 2020), pages 1733-1752, 2020. doi: 1111.111777799811111119999999999
12

---

[34] Thijs Vogels, Sai Praneeth Karimireddy, and Martin Jaggi. PowerSGD: Practical low-rank gra- dient compression for distributed optimization. In Advances Neural Information Processing Systems (NeurIPS 2019). 2019.
[35] Hongyi Wang, Scott Sievert, Zachary Charles, Shengchao Liu, Stephen Wright, and Dimitris Papailiopoulos. ATOMO: communicationn-eficieet learning via atomic sparsification. In Advances in Neural Information Processing Systems 32 (NeurIPS 2018), 2018.
[36] Jianyu Wang. Hao Liang, and Gauri Joshi. Overlap local-SGD: An algorithmic approach to hide communication delays in distributed SGD. In ICASSP 2020-2020 IEEE International Conference Acoustics, Speech and Signal Processing (ICASSP), pages 8871 8871-8875, IEEE, 2020.
[37] David P. Woodruff and Qin Zhang. When distributed computation is communication expensive. Distributed Computing, 30(5):309-322 2017. doi:10. 10010077/00446---14-01138333
[38] Blake E Woodworth and Nati Srebro. Tight complexity bounds for optimizing composite objectives. In Advances in Neural Information Processing Systems 29 (NIPS 2016), pages 3639-3647, 2016.
[39] Blake E Woodworth, Jialei Wang, Adam Smith, Brendan McMahan, and Nati Srebro. Graph oracle models, lower bounds, and gaps for parallel stochastic optimization. In Advances in Neural Information Processing Systems 31 (NIPS 2018), pages 3496-8506, 2018.
[40] Andrew Chi-Chin Yao. Probabilistic computations: Toward a unified measure of complexity. In Proc, 18th Annual Symposium on Foundations of Computer Science (FOCS 1977), page 222-227, 1977. doi: 10. 10900.1119//FCC.99....
[41] Yuchen Zhang, John Duchi, Michael Jordan, and Martin Wainwright. Information-theoree lower bounds for distributed statistical estimation with communication constraints. In Advances in Neural Information Processing Systems 26 (NIPS 2013), pages 2328-2336 2013.
13


Reviews:
[{"review_id": "tOHUlmhjUaL", "reviewer": "Reviewer_coZz", "summary": "The submission studies the theoretical coordinator model communication complexity of multiple parties, each holding a strongly convex f_i, for the task of approximately minimizing the sum f_i. The main result is a communication lower bound, which basically follows by picking the approximation parameter so restrictive that each party has to send the minimum of its f_i, to appropriate precision, in all dimensions.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Communication complexity is an important bottleneck for optimization. I am not excited by the lower bound. I am less of an expert about the algorithm side – to me their approach seems natural but not trivial. This work already inspired an ICML’21 paper that develops a more interesting algorithm. \n\n\nLower bound parameters: the lower bound is based on the sum of quadratics || x – x_i ||^2_2, where each party holds one x_i. The lower bound holds for approximation \\epsilon = O(d / N), where d = dimension, N = # of parties. The dependence on d is the natural one and is technically dealt with an off-the-shelf packing bound (any good binary error correcting code would do). The dependence on N is what makes the lower bound not exciting IMHO: with \\epsilon ~ 1/N^2 per dimension and party, this obviously forces all the parties to communicate. This result may be tight in this regime, but it’s probably not so natural – on say a random input the value of the function would be on the order of magnitude of d*N, so in comparison this is a really small \\epsilon. In practice, for the sum of quadratics considered in the lower bound, taking a sub-sample of the parties’ functions would probably be good enough for most applications where N is so large that we’re actually concerned about an asymptotic factor of N in the communication.\n\n\nTypos: \nLine 241: “will prove” -> “we will prove”\nLine 242: \\ref -> \\eqref\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "NA", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "omUNSyrELaY", "reviewer": "Reviewer_aPic", "summary": "This paper studies the problem of distributed convex optimization, where each of $N$ machines holds a local function $f_i$, and a coordinator aims to minimize the global objective $\\sum_i f_i$ by using a limited amount of communication with local machines. The main contribution of this paper is a $\\tilde{\\Omega}(Nd)$ bits lower bound on the total communication cost. The lower bound is constructed by considering quadratic local functions and reducing the minimization problem to mean estimation and two-party communication problems. Finally, the authors show that the lower bound can be attained when $f_i$'s are strongly convex and smooth. ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Though the lower bound $\\tilde{\\Omega}(Nd)$ may be expected and not too surprising given previous works on the two-node settings, the result can still be useful in related directions such as federated learning. In general, the paper is well-written and the proofs are clear and easy to follow.  I have the following questions and suggestions:\n\n1. The paper considers the private randomness model, but I wonder whether the same bound holds for the shared randomness settings (given that the problem is ultimately reduced to 2-BITS and the lower bound for 2-BITS holds for the shared randomness model).\n\n\n2. In many distributed/federated learning scenarios, the communication is asymmetric; that is, the uplink communication (i.e. from each machine to the coordinator) is usually more expensive than the downlink communication.  Is there a lower bound for only the uplink communication cost (with an assumption that the downlink bandwidth is infinite)?\n\n\n3. The authors may want to add some comments on whether the lower bound is tight for functions without strong convexity or smoothness assumptions.\n\n\n4. Finally, it would be better to include some references and comparisons with the line of research that study the communication complexity under gradient oracle settings. See [1] and its references for example.\n\n\n[1] Acharya et al. \"Information-constrained optimization: can adaptive processing of gradients help?\"", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have listed the limitations as part of future works. This work does not present any foreseeable societal consequences due to its theoretical nature.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "NZuw26hIwLv", "reviewer": "Reviewer_JTxy", "summary": "In this paper, authors propose the communication complexity lower and upper bound for the sum of quadratic functions minimization in the distributed setup.", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "In this paper, author consider the communication bottleneck problem in distributed optimization algorithms. \nThe main result of this paper is the lower-bound on the communication complexity for the quadratic functions minimization. \n\nThis paper is pure theoretical and consider only the quadratic functions with additive error tolerance stopping criteria. \nTo proof the main result, authors consider discrete model with finite input and output sets. \nThen they move from the initial problem to the problem of finding of the mean of the parameters that is necessary due to the explicit form of the sum of quadratic functions. This bound is sufficiently get from the complexity of the two-player game 2-BITS_d.\nAs a result, I find this theory quite nice but I am hesitating if this bound is useful in practice. Since the considered set up is quadratic functions, I would expect this minimization problem be easy enough to not talk about the communication bottle-neck and complexity.\nHowever, the future plans to extend the theory to some other classes of inputs sounds nice. I would be interested to see the result for LASSO problem, where we have an additional $\\ell_1$ regularizer that enforces some structure to the solution. I am wondering if this structure can somehow appear in this bound (if a-priori it is known that the solution is 1% dense). \n Moreover, as far as I understand, the lower bound is not tight at all, so I would say that the discussion about its tightness is missing here.\n\nAccording to the upper-bound, I am wondering, why exactly this method is selected for it. (at least we should talk about the projected gradient descent to have $x^k\\in [0,1]^d$). \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1 hour"}, "extra_text": {}}, {"review_id": "IznEOWbvGDA", "reviewer": "Reviewer_WQv3", "summary": "The paper shows lower bounds for distribution optimization. For the standard distributed optimization setting with N machines each of which holds a d-dimensional function f_i and the goal is to minimize \\sum_{i=1}^N f_i(x), the paper shows that \\Omega(Nd log(d/N\\eps)) bits of communication are necessary to obtain an \\eps sub-optimal solution. The result holds both for randomized and deterministic algorithms. \n\nThe paper also shows a new upper bound derived using a variant of quantized gradient descent. The upper bound nearly matches the lower bound for well-conditioned problems (when the overall problem has a constant condition number).\n\nThe lower bounds are shown via interesting applications of standard communication complexity machinery. The upper bound follows via relatively simple modifications to existing quantization techniques.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The contributions here lean more towards conceptual than technical. On a technical level, the lower bound follows once the right problem has been setup, and most of the work is to frame the problem in a way such that existing machinery from communication complexity can be leveraged. I do not view this as a drawback, rather, it is nice that the proof is clean and is leveraging connections to well-established techniques. The lower bound also gets close to the right answer to the problem, and shows that vanilla distributed gradient descent is close to optimal (at least for well-conditioned problems).\n\nThe paper is quite related to the work of Vempala et al. who also show lower bounds for distributed optimization problems using communication complexity techniques. However, Vempala et al. show a lower bound to obtain an eps multiplicative approximation for the solution, which follows from the lower bound for the realizable case for linear systems. The current paper instead shows a lower bound for an eps additive approximation, which is also more directly comparable to known upper bounds.\n\nThe paper also points to an interesting problem to resolve the gap between the upper and lower bounds in terms of the condition number of the problem, resolving which would likely lead to the development of new techniques.\n\nThe paper is extremely well-written. It provides adequate context for the problem and the techniques with respect to prior work, provides sufficient intuition for the results, and outlines several future directions.\n\nOverall, I think this is a good paper which proves a solid theoretical result for an important and practically-relevant problem, and could lead to interesting future work.\n\nSome suggested edits:\n\n1. tau in the proof of Lemma 5 should probably be replaced by sigma.\n2. It may be worth mentioning in the beginning that there is not restriction on the sequence/topology of communication between the machines.\n3. The work of Steinhardt et al. on \"Memory, communication and statistical queries\" seems relevant since it also proves a lower bound for distributed optimization, though I don't think it implies the result in the current paper.\n4. Line 242, parenthesis around 1.\n\n----after author response----\n\nIn light of the other reviewers' comments, it seems that the bound is not as interesting as I thought earlier. Before, I thought the paper is making the qualitative message that all machines have to communicate their entire data (in the worst case), which seems like a very interesting point to make. However, the regime when epsilon is 1/N does not seem to be right to prove such a message and does seem a bit artificial. In particular, any lower bound should be able to handle simple strategies such as subsampling, and as pointed out by another reviewer the bound only works in the current setting because with such a small error requirement, there is no other way to estimate the overall mean except by communicating the entire data. While this result could be regarded as some sort of first step towards the right lower bound without this additional factor of N, it makes it a bit less interesting. The main contribution in the paper was the conceptual message instead of technical machinery, but since the conceptual message isn't what I thought before, I am lowering my score to 6 from 7. In short, the paper is making a decent contribution and could be accepted, but I can't argue as strongly for it.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations And societal impact are adequately addressed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors consider the communication complexity of minimizing a convex function defined on a $d$-dimensional box and distributed over $N$ machines. They show a lower bound that says the machines need to communicate roughly $Nd \log (1/\epsilon)$ bits of information to find an $\epsilon$-accurate solution. Despite raising some concerns on the validity of the problem setting, the reviewers appreciated the topic of the paper and the communication-complexity view.

Consequently, I am recommending acceptance of the paper, but urge the authors to take the feedback of the reviewers into account when revising the paper. In particular, the non-standard choice of domain (box rather than ball) should be explained, the objective should be modified to the average of the functions rather than their sum, and the case of constant $\epsilon$ should be thoroughly discussed.
Decision: Accept (Poster)