Improved Communication Lower Bounds for Distributed Optimisation
Authors: Janne H. Korhonen
Dan Alistarh
Venue:  (2021)
Keywords: distributed optimization
lower bounds
upper bounds
communication complexity

Abstract: Motivated by the interest in communication-efficient methods for distributed machine learning, we consider the communication complexity of minimising a sum of $d$-dimensional functions $\sum_{i = 1}^N f_i (x)$, where each function $f_i$ is held by one of the $N$ different machines. Such tasks arise naturally in  large-scale optimisation, where a standard solution is to apply variants of  (stochastic) gradient descent.  As our main result, we show that $\Omega( Nd \log d / \varepsilon)$ bits in total 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 results holds for deterministic algorithms, and randomised algorithms under some restrictions on the parameter values. Importantly, our lower bounds require no assumptions on the structure of the algorithm, and are matched within constant factors for strongly convex objectives by a new variant of quantised gradient descent. The lower bounds are obtained by bringing over tools from communication complexity to distributed optimisation, an approach we hope will find further use in future.


Under review as a conference paper at ICLR 2021
IMPROVED COMMUNICATION LOWER BOUNDS FOR DISTRIBUTED OPTIMISATION
Anonymous authors Paper under double-blind review
ABSTRACT
Motivated by the interest in cummunication-efficee methods for distributed ma- chine learning, we consider the communication complexity of minimising a sum of d-dimensional functions Σi= f((z), where each function fi is held by one of the N different machines. Such tasks arise naturally in large-scale optimisation, where a standard solution is to apply variants of (stochastic) gradient descent. As our main result, we show that St D(Ndlogg doogd/// d/E) bits in total need to be communicated between the machines to find an additive e-approximation to the minimum of E fa(x). The result holds for deterministic algorithms, and randomised algorithms under some restrictions on the parameter values. Importantly, our lower bounds require no assumptions on the structure of the algorithm, and are matched within constant factors for strongly convex objectives by a new variant of quantised gradient de- scent. The lower bounds are obtained by bringing over tools from communication complexity to distributed optimisation, an approach we hope will find further use in future.
INTRODUCTION
The ability to distribute the processing of large-scale data across several computing nodes has been one of the main technical enablers of recent progress in machine learning, and the last decade has seen significant research effort dedicated to efficient distributed optimisation. One specific area of interest is communication reduction for distributed machine learning. Recently, several algorithms have been proposed to reduce the communication footprint of popular methods in machine learning and optimisation, in particular gradient descent and stochastic gradient descent; see e.g. Arjevani Shamir (2015); Alistarh et al. (2017); Suresh et al. (2017); Tang et al. (2019) for recent work, and Ben-Nun & Hoefler (2019) for a survey. Despite this extensive work, less is known about theoretical limits of communication complexity of optimisation, especially in terms of lower bounds on the minimal number of bits which machines need to transmit to jointly solve an optimisation problem.
In this paper, we study this question in a classical distributed optimisation setting, where data is split among N which that can communicate by sending point-to-point messages to cach other. Given input dimension d, and domain ID d each machine i is given an input function f:: D - R. and the machines need to jointly minimise the sum Σ f((),, e.g. the empirical risk, with either deterministic or probabilistic guarantees on the output. The setting is standard way to model the distributed training of machine learning models. For instance, if the individual loss functions are assumed to be (strongly) convex, we can model a classic regression setting, whereas if the function is non-convex, we can model distributed training of deep neural networks.
In this context, the key question is: what is the minimal number of bits which need to be exchanged for this optimisation procedure to be successful, and how does this number depend on the properties of the functions fi, and the parameters N and d?
1.1 OUR RESULTS
Setting. We consider this question in the classic peessage-passing model, where N nodes commu- nicate by sending messages to each other; specifically, each message is sent to a single receiver and not seen by the other nodes. Our complexity measure is the total number of bits sent by all the nodes.

---

Under review as a conference paper at ICLR 2021
Given this complexity measure, the model is equivalent (up to a constant factor) to model where all messages are relayed via a special coordinator node, known in communication complexity as the coordinator model and in machine learning the parameter server model (Li et al., 2014).
For convenience of presentation, we set ID = [0, 1]", and consider a problem where each node i is given an input function f:: [0, 1] + R, and the task is to approximate the minimum of the sum of the functions. That is, the coordinator needs to output & E [0, 1] and an estimate r E IR for the minimum function value such that
E (())
E1(() +e and E((()) ( 2E|0,1]
inf
E((()) 11(2)
Specifically, this models standard distributed machine learning setting where we require one of the nodes to return the optimised final model, as well as the final value of the loss function. When proving lower bounds, allow the nodes compute arbitrary values that depend on the input functions and operate on real numbers; only the amount of communicated bits is limited. The precise definition is somewhat subtle, so we defer the details of the model to Section 2.
Lower bounds for convex functions. We show that, even if the input functions ft at the nodes promised be quadratic functions satisfying (1) deterministically requires
Bullar x=' x12 for constant Bo > 0, finding solution
3d 2 Nd =
total bits to be communicated,
where 3 = N is the smoothness parameter Σx= fi, for parameters satisfying' 3d/s = 22(1). For randomised algorithms, we give lower bound of
2( (dddlog
3d Ne
total bits to be communicated.
for parameters satisfying 3d/N2 = 2(1). While this lower bound is slightly weaker due to the additional dependence in N, in most practical settings the number of parameters d will be significantly larger than the number of machines N, multiplied by the error tolerance E. (Specifically, in most practical settings N < 1000, whereas s 10-3 More generally, it is sufficient that d ((N2+6) for constant > 0, for the randomised lower bound to match the deterministic one asymptotically.)
At a very high level, our results generalise the Tsitsiklis & Luo (1987) idea of linking the communica- tion complexity with the number of quadratic functions with distinct minima in the domain. To extend this approach the multi-node case > 2 and randomised (stochastic) algorithms, nections to results and techniques from communication complexity. Such connections have not to our knowledge been explored in the context of (real-valued) optimisation tasks, despite reductions from communication complexity being a standard lower bound technique e.g. in distributed computing (Das Sarma et al., 2012; Abboud et al., 2016; Drucker al., 2014). Our work thus provides a model and basic toolkit for applying communication complexity results to distributed optimisation, which should also be useful for understanding other optimisation tasks.
build con-
Extensions. While, for convenience, we work with functions over [0. 1]d our bounds immediately extend to arbitrary convex domains, as long as we can bound the number of functions with distinct minima in the domain. Beyond strongly convex and smooth functions, we also show that for non-convex X-Lipschitz functions, solving (1) requires
N exp ( ) total bits communicated.
The main takeaway from this result is that for non-convex objectives, one can induce exponentially higher communication cost by building convoluted input families where the coordinator is required to essentially learn all local input functions of the nodes.
'The constant hidden by 2(1) in the parameter dependency is at most 8.6 in all lower bounds.
2

---

Under review as a conference paper at ICLR 2021
Optimal upper bound. To complement our lower bound, we show that for strongly convex and strongly smooth functions, finding a solution to (1) can be done deterministically with
o( (Ndri log x log
3d E
total bits communicated.
where Ei=1 ft is a-strongly convex and 3-strongly smooth, and к = B/aa is the condition number. This algorithm matches our lower bound for constant condition number. It is a variant of deterministic quantised gradient descent (Magnússon et al., 2019). However, to achieve a tight bound, we need to (a) ensure that our gradient quantisation is sufficiently parsimonious, using Od k) bits per gradient, and (b) avoid all-to-all exchange of gradients. For (a), we specialise a recent aatice-based quantisation scheme which allows arbitrary centering of iterates (Alistarh et al., 2020), 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.
1.2 RELATED WORK
Message-passing versus broadcast. There are two communication models frequently used in both communication complexity and distributed optimisation: the first is the message- paasssggg model we focus on, and the second is the broadcast or blackboard model, where each message sent by node is seen by all nodes. The broadcast model is more powerful than the message- messagg-passing model: lower bounds for broadcast model apply also for message- message-passing, but upper bounds for broadcast do not directly translate to message passing. Arguably, message-passing model is closer to reality, as constant-cost, high-bandwidth broadcast mechanisms do not exist in real systems.
Optimisation lower bounds. The first communication lower bounds for a variant of (1) were given in the seminal work of Tsitsiklis & Luo (1987). who study optimising sums of convex functions in a two-machine setting. For deterministic algorithms, they prove that ([glg((gd/))) bits are necessary. Zhang et al. (2013) use nearly identical argument to give a Rid (og(/g/// (Bod/e)) lower bound for randomised algorithms in the broadcast model. (See also Table the Appendix.)
The basic intuition behind these lower bounds is that a node without information about the input needs to receive (2d log(g//))/ 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 (( (oud)///)))/// bits is not ruled out by these previous results. Generalising their approach to match our results seems challenging, as we would have to (a) explicitly require that all nodes output the solution, and (b) ensure that no node can use their local input as a source of extra information.
Our study was inspired in part by the recent work of Vempala al. (2020), who characterised the communication complexity of solving linear systems, linear regression, and related problems, over bounded integer matrices. The results to our lower bound. However, there are some notable technical differences: first, the arbitrary real functions we consider do not have a natural binary encoding, and therefore their approach would not directly extend to our setting. Second, the approximation ratio for linear regression is defined multiplicatively their work, whereas we consider additive approximations. Both formulations are popular in terms of upper bounds, with the additive error formulation being arguably more popular in the context of machine learning applications. Overall, our results complement theirs, enriching the landscape of lower bounds for distributed optimisation.
based on communication complexity arguments, similarly
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 adversarially. Concretely, the results of Shamir (2014) and Suresh et al. (2017) apply only to restricted types of protocols. Garg et al. (2014) and Braverman et al. (2016) give lower bounds for Gaussian mean estimation, where each node receives samples from d dddiiensional Gaussian distribution with variance o². The latter reference shows that to achieve the minimax rate o² d/ on mean squared error requires ((Nd) total communication. These results do not imply optimal lower bounds for our setting.
3

---

Under review as a conference paper at ICLR 2021
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 (Arjevani & Shamir, 2015; Scaman et al., 2017), but does not address the communication cost of 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 solve an optimisation problem (Woodworth & Srebro, 2016; Woodworth et al., 2018).
Upper bounds. There has been tremendous amount of work recently on communication-efficinn optimisation algorithms in the distributed setting. Due to space constraints, we focus on small selection of closely-related related work. One critical difference relative to practical references, e.g. Alistarh et al. (2017), 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 Suresh et al. (2017), who present a series of quantisation methods for mean estimation on real-valued input vectors. Recently, Alistarh et al. (2020) studied the same problem, focusing on replacing the dependence on input norm with a variance dependence. We adapt their scheme for our upper bound.
Tsitsiklis & Luo (1987) gave deterministic upper bound in two-node setting, with O (od (og( log(3d/e)) total communication cost. Recently, Magnússon et al. (2019) extended this to --node case in the broadcast model, with ( (Ndd log(rdd (og)))))) total communication cost. For randomised algorithms and constant condition number, better upper bound of O(Nd log (gd(/)))) total communication cost the broadcast model follows by using QSGD stochastic quantisation (Al- istarh et al., 2017) plugged into stochastic variance-reduced gradient descent (SVRG) (Johnson & Zhang, 2013). See Künstner (2017) for detailed treatment. (See also Table 2 in the Appendix.)
2 PRELIMINARIES AND BACKGROUND
Coordinator model. We consider communication protocols in the classic coordinator model (Dolev Feder, 1992; Phillips et al., 2012; Braverman al., 2013). this model, we have N nodes as well as separate coordinator node. The task is to compute the value of a function I: B - A, where B and are arbitrary input and output domains; each node = 1, 1.2...., NN receives an input b, B. There is 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 b2............... .., bx). Furthermore, all nodes, including the coordinator, have access to stream of private random bits.
More precisely, we assume without loss of generality that computation is performed as follows:
(1) Initially, each node = 1,2, N receives the input by. The coordinator and nodes .,,,..., N receive independent and uniformly random binary strings 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 single node i, and (b) the node i that received a message from the coordinator responds by sending message to the coordinator.
A transcript for node is list of the messages it has sent and received. A protocol II is mapping giving the actions 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 II computes I': BN + A with error p if for all (2..b,...., by) E B% the output of II is [(b,, b bx) with probability at least p. The communication complexity of protocol IT is the maximum number of total bits transmitted by all nodes, i.e. the total length of the transcripts, on any input (b,, by.... .2..... bn) E N 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. Any algorithm using parallel synchronous
4

---

Under review as a conference paper at ICLR 2021
even asynchronous communication can be transformed into sequential protocol by sequentialising the communication steps to occur one after the other. Likewise, algorithms using all-to-all message- passing be transformed the coordinator model, by routing all messages via the coordinator. The transformation incur at most constant factor overhead.
Finally; observe that the model is nonuniform, i.e. each protocol is defined only for specific functions T: B. - and specific input and output sets B and A. As such, we do not need to impose any requirements on the computability of the protocol actions, rather these can be arbitrary functions. Any uniform algorithm working for a range of parameters induces a series of nonuniform protocols, so lower bounds for coordinator model translate uniform algorithms.
Communication complexity. We now recall some basic definitions and results from communica- tion complexity. In the following, we assume that sets B and A are finite, as this is 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 Т. Likewise, the 8-error randomised communication complexity RCC (T') is the minimum communication complexity of protocol that computes I with error probability 8.
For distribution y over B>, define the ô-error p-distributional communication complexity of denoted by D (I). as the minimum communication complexity of deterministic protocol that computes I' with error probability when the input is drawn from μ. Similarly, the ò-error y-distributional expected communication complexity of T, denoted by ED (T), is the minimum expected communication cost of protocol that computes I' with error probability 6, where the expectation is taken over input drawn from ja and the random bits of the protocol.
Yao's ss Lemma (Yao, 1977) relates the distributional communication complexity to the randomised communication complexity; see Woodruff & Zhang (2017) for proof in the coordinator model.
Lemma (Yao's Lemma). For function I' and > 0, we have RCC (T) 2 max, (T').
Properties of convex functions.
Recall that a continuously differentiable function f is
3-(strongly) smooth a-strongly convex if
[V(()) - // S B| - =
VV)(z) ((()))((>>>) -) al| vll
for all and y in the domain of f. For a-strongly convex and 3-strongly smooth function f, say that if has condition number x = B/a. If fi is a1 -i-strongly convex and 81 $1-strongly smooth and fo ag-strongly convex and 82-strongly smooth, then f1 + f2 is (01 + (eg)-strongl convex and (B1 + -f2)-strnngly smooth.
quadratic function fxx) B|| - 1113 + B-strongly convex and f-strongly smooth, For > ((x) < e, then |x - x² x²1|2 S (e/8)1/2, A sum of quadratics F(x) = Σ5= aj || -ysll, where Vj Rd and aj for 1,2.... is quadratic function F(x) Aliz x² + C, where C is a constant and x= = Σド= a,y,/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 & Luo (1987)). For ō 0 and d 1, there is set of points S _ [0, 1]4 with ||æ vll2 for all distinct x. y S, and [S| /C where C (m2 is constant.
LOWER BOUNDS
3.1
DETERMINISTIC LOWER BOUND FOR QUADRATIC FUNCTIONS
We start with warm-up result, proving lower bound against deterministic protocols. Essentially, show that even recognising all the nodes have the same input function is hard. Recall that in the N- player equality universe of size d, denoted by EQa,N, each player i is given an input by (0, 1)d.
5

---

Under review as a conference paper at ICLR 2021
and the task is to decide if all players have the same input. That is, EQN.N (bI.....br) = 1 if all inputs are equal, and O otherwise. It is known (Vempala et al., 2020) that the deterministic communication complexity of N is CC(EQu,N)
((Nd).
Theorem 3. Given parameters N, d, E, 30 and B Bo satisfying d3/s 2(1), any deterministic protocol solving (1) for quadratic input functions x + Bollæ - zoll2 has communication complexity
((Ndlog(Bd/e))
Proof. Assume II is a deterministic protocol solving (1) with communication complexity Cn. We show that Il can then solve N N-party equality over universe of size D ([d implying
Cn = D(DD) 10000:0(N000 (Bddog(()))))
More specifically, let S be the set given by Lemma 2 with 6 = (=/28)1/2, and let D [log |S|] (dd/)))) Note that since we assume d3/e = (2(1), the set S has at least two elements and D 2 1. For technical convenience, assume |S| = 2", and identify each binary string E {0, 1) with an element rb)) E S.
Next, assumee that each node i is given binary string 6; E {0, input, and we want compute EQD,N (b1, (2....,bb)] The nodes simulate protocol IT with input function fi for node i, where [((x)= Bollz - ((b)) Let denote F =>>= Js. Upon termination of the protocol, the coordinator learns a point y [0, 1] satisfying F(y) S F(x*) + and an estimate E R satisfying r S F() + E, where x" is the true global minimum. The coordinator can now adjudicate equality based on Fyy) as follows:
(1) If all inputs b; are equal, then the functions S; are also equal, and F(x*) = 0. In this case, we have F(y)= < 2s, and the coordinator outputs 1.
(2) If there are nodes and j such that i + j. then for all points [0, 1]d, we have fx) [x(x) > 2s by the definition of S, and thus F(x*)= >> 28. In this case, we have r >> 2s, and the coordinator outputs O.
Since communication is only used for the simulation of IT, this computes EQD, b2................ with On total communication, completing the proof.
bx)
3.2 RANDOMISED LOWER BOUND FOR QUADRATIC FUNCTIONS
We now prove our main result, by giving a lower bound for communication complexity of any algorithm solving (1) that holds even for randomised protocols, albeit with a slightly weaker bound.
Theorem 4. Given parameters N, d, So and 3 Bo.N satisfying d3/ d3/N2 = 9(1), any protocol solving (1) for quadratic input functions x + Bollx roll2 2222 has communication complexity
2 (dddlog(3d/Ne))
Discussion. As this our main result, we pause to discuss its implications. First, this result is more general than Theorem 3, as it applies to stochastic algorithms such as SGD or SVRG Johnson & Zhang (2013), which are arguably more popular in practice. The price for the increased generality is the additional N factor in the denominator of the log, which appears due to technical requirements in the reduction. Finally, we note that the constant lower bound on d the relatively small < 8.6, and that this lower bound is likely to hold in most practical settings of interest, d is usually quite large, and E is usually quite small.
Proof overview. To formally apply communication complexity tools, will prove a lower bound for a discretised version of (1) where both the input and output sets are finite which will imply Theorem 4. Let N, d, e, and B be fixed, assume d33 d / = 2(1), and
(1) let S be the given by Lemma 2 with 5 (N and
(2) let T C [0, 1]d be an arbitrary finite set of points such that for any [0, 114, there is point L. T with ||x Ill 12/4

---

Under review as a conference paper at ICLR 2021
By assumption d 92(),, the set S has size at least 2. Let D log ||] O(dlog(dd/Ne)) Again, for convenience, assume 2n = |S], and identify each binary string Ee 10, with an element r(6) S.
Definition 5. Given parameters N,d,e, L, B, we define the problem MEAN N.N as follows:
The node imputs are from {0, 1P.1 and
Valid outputs for input (b), b2.... by) are points t E T that satisfy the condition 1|x t|l2 (=/ where x" Ei= (b,)/N is the average over inputs.
First, we observe that any algorithm for solving (1) can be used to solve MEAN d,N'
Lemma 6. For fixed N, d, E. Bo and 3 = 9, any randomised protocol solving (1) for quadratic functions + So l| zoll2 with error probability 1/3 has communication complexity at least RCC1/3 (MEAN..)/) 9/44)
The natural step is to prove lower bound the communication complexity of MEAN We d.N- do this by using instance of the symmetrisation technique of Phillips al. (2012), via reduction to the expected communication complexity a rwo-party communication problem where one player has to learn the complete input of the other player. Specifically, 2- player (Alice) receives binary string b E {0, 1jdd of length d, and the task is for player (Bob) output Let Gp be a distribution over binary strings E {0. [0,1] 1] where each bit set to 1 with probability p and to 0 with probability 1 1-p. The following lower bound for 2-BITS, is known, and holds even for protocols with public randomness, i.c. when Alice and Bob have access the same string of random bits:
the two-player problem called
E [2pdp logp-1). Lemma (Phillips et al. (2012)). S.
Lemma 8. For N, d, E, and B satisfying d3/N2 Q(1), we have
2(N ED 1/3 (2-BITSp)) = -2(Ndlog(Sd/Ne))
C1/2
Due to space constraints, we defer the proofs of Lemmas 6 and 8 to Appendix A.1. Theorem now follows immediately from Lemmas 6 and 8. The result be generalised for arbitrary convex domains D C IR as (2N log s), given point packing bound for D as in Lemma 2.
3.3 LOWER BOUND FOR NON-CONVEX FUNCTIONS
We now show a simple lower bound for optimisation over non-convex objective functions. Specifically, we construct set of hard input functions as follows. Let E, d and B be constant satisfying dB/e 2(1), and consider the set S given by Lemma 2 with 5 28/ (. This gives set S with size least (Bdl/2/2Ce))
(xp log (3)))))))) Let us identify the points S with elements of (1. [S]. For a binary string E (0, 11l define the function fo by
x E
s||2
if || s||2 < E/3 for with b, = otherwise.
fo(x)
Since the distance between points in S is at least 2s/8, the functions fr are well-defined, continuous and [8-iihshi The proof works by reduction from N-player set disjointness (Braverman al., 2013); we defer the details to Appendix B.
Theorem 9. Given parameters N, d, and 3 satisfying d3/s = S2(1) and /2Ce)d wlog N), any protocol solving (I) with error probability > 0 when the inputs are guaranteed be functions fo b {0, 13181 has communication complexity N cxp((((llo(Bdd))e)
TIGHT DETERMINISTIC UPPER BOUND
We now present deterministic algorithm which matches our lower bound for constant condition number, in the coordinator model. We follow the general structure of communication-reen algo- rithms, e.g. Magnússon al. (2019): the nodes collectively execute instance of gradient descent
7

---

Under review as a conference paper at ICLR 2021
(GD), where they carefully quantise their updates, accumulated a coordinator. The algorithm relies on two new technical ingredients to achieve optimality: 1) we use two-step quantisation to avoid (inherently suboptimal) all-to-all communication; 2) we remove superfluous log d factor in the communication by employing a lattice-based quantisation scheme allowing for arbitrary centring of the gradient estimates to be averaged (Alistarh et al., 2020). The second step causes non-trivial complications, as this scheme may fail if inputs are too far apart.
Preliminaries. We assume that the input functions of each node i is fr: [0, + R. which is og-Strongly convex and So-strongly smooth. This implies that F F=Σ= is a-strongly convex and 3-strongly smooth for Na and B = 3o- Consequently, the functions fi and F have condition number bounded by 8/a. Furthermore, we assume that the local functions f; all have minimum value inf jo.1j (xx)
and thus range [0, [nd].
We aim to reach the global minimum xt of the sum Σ fi(z)) by starting from an arbitrary point a: E [0. 1j6, and applying surrogate of the GD update
N
(1+1) = x11)
Vi(((())) where > 0 is the learning rate parameter.
It is well-known, e.g. Bubeck (2015), that GD converges at an exponential rate in (1 - 1/m²)
The algorithm has each node generate gradients of its local function fi, and quantise them in way. Specifically, the quantisation we use works in a setting where the nodes all know a point q [0, 1] and the points to be quantised are in the vicinity of q - in the algorithm, the point q will be the previous quantised gradient. The quantisation is parametrised by Rt the maximum distance between the input point and q, and by E, the maximum quantisation error we wish to tolerate.
Corollary 10 (Alistarh et al. (2020)). Let R and E be fixed positive parameters, and q E I be an estimate vector, and B E N be the number of bits used by the quantisation scheme. Then, there exists a deterministic quantisation scheme, specified by a function Qe,R: Bd x IRd + Rd an encoding function enc,,n: TRd - {0, 1]B, and a decoding function dec,, Rdd x {0, 10 + Rd, with the following properties:
(1) (Validity.) dec,,,(9, enc, enc;,R(x)) (x)) = Qe, 4) for all x, E IR with 1 - alla S R.
(2) (Accuracy.) ( q) =112 S for all 2,q q Rd with 1| 4ll2 S R.
(3) (Cost.) I = XR for any X < 1, the bit cost of the scheme satisfies B = O log X 1
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 to 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 if D = [o, 1]d We assume that the initial iterate (0()) is arbitrary, but the same at all nodes, and set the initial quantisation estimates (0) and T. at each i as the origin.
The algorithm proceeds in rounds t 1,2, .......777 T. At the beginning of round t 1, each node i knows the values of the iterate (f)), the previous global quantised gradient g(), and its local quantised gradient qi the coordination knows all these values. We define the following parameters for the algorithm. Let y 8-1 and { = (1 -=1 be the step size and convergence rate of gradient descent, and let W be such that ||>"" x²1] < W. We define
K = ==2/5,
8 = { - E44
== ōK + E
R = 3KW
Assuming k 2 2, we have μ 1, 2 1/2 and K 2 1. At step nodes perform the following steps:
(1) Each node i updates its iterate as (1+1) (1) (9)
(2) Each node computes its local gradient over xf (+++1), and transmits it in quantised form to the coordinator as follows. Let 61 ( /2N) and p1 (((++)/N.
8

---

Under review as a conference paper at ICLR 2021
(a) Node computes fz(lt+1)) locally, and sends message m, e1 p1 (V (v((((()))))
to the coordinator.
(b) The coordinator receives messages my for i = 1, ,.,,, NN, and decodes them as [(+1) decci.P: (g: m:). The coordinator then computes y(++1) N
9; (I+1)
li
(3) The coordinator sends the quantised sum of gradients to all other nodes follows. Let = 5 /2 and P2 (1 8/2)
(a) The coordinator sends the message m e2 (r(++2) each node i.
(b) Each node decodes the coordinator's message q ((+1) dec (g m).
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 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 provided in Appendix C.
Guarantees.
Theorem 11. Let
dimension d, and convex domain T C RRd of diameter W be fixed. Given N nodes, each assigned a function f:: - such that F EN is a-strongly convex and B-smooth, the above algorithm converges to point x(T) with [F F(x")ll2 S using
o( N log is log
3W )
bits of communication.
E
DISCUSSION AND FUTURE WORK
We have provided the first tight bounds the communication complexity of optimising of quadratic functions in the N --party model with a coordinator. Our results are llgorithm-independee 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 match the deterministic one even for small d, possibly via reduction from a suitable gap problem in communication complexity (e.g. Chakrabarti & Regev (2011)). 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. Finally, understanding the exact complexity of optimisation in the broadcast model remains open.
REFERENCES
Amir Abboud, Keren Censor-Hillel, and Seri Khoury. Near-linear lower bounds for distributed distance computations, even in sparse networks. Proc. 30th International Symposium on Distributed Computing (DISC 2016), pp. 29 42. Springer, 2016. dbo::00.0007998833-66--53333
7_3.
Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. QSGD: Communication- efficient SGD via gradient quantization and encoding. In Advances Neural Information Process- ing Systems, pp. 1709-1720, 2017.
Dan Alistarh, Salch Ashkboos, and Peter Davies. Distributed mean estimation with optimal error bounds, 2020. arXiv:2002.09268 [cs.LG].
Yossi Arjevani and Ohad Shamir. Communication complexity of distributed convex learning and optimization. In Advances in Neural Information Processing Systems 28 (NIPS 2015), pp. 1756- 1764, 2015.
Tal Ben-Nun and Torsten Hoefler. Demystifying parallel and distributed deep learning: An in-depth concurrency analysis. ACM Computing Surveys (CSUR), 52(4): 2019.
Mark Braverman, Faith Ellen, Rotem Oshman, Toniann Pitassi, and Vinod Vaikuntanathan. A tight bound for set disjointness in the message-passingg model. In Proc. 54th Annual Symposium on Foundations of Computer Science (FOCS 2013), pp. 668-677. IEEE, 2013.

---

Under review as a conference paper at ICLR 2021
Mark Braverman, Ankit Garg, Tengyu Ma, Huy L Nguyen, and David P Woodruff. Communication lower bounds for statistical estimation problems via a distributed data processing inequality. In Proceedings of the 48th Annual ACM symposium Theory of Computing (STOC 2016), pp. 1011-1020, 2016.
Sébastien Bubeck. Convex Optimization: Algorithms and Complexity. now Publishers, 2015.
Amit Chakrabarti and Oded Regev. An optimal lower bound on the communication complexity of sap-hamming-distanee In Proc. 43rd ACM Symposium on Theory of Computing (STOC 2011), New York, NY, USA, 2011. Association for Computing Machinery. ISBN 9781450306911. doi: doi:1001145/1992666.110 1993644.
Atish Das Sarma, Stephan Holzer, Liah Kor, Amos Korman, Danupon Nanongkai, Gopal Panduran- gan, David Peleg. and Roger Wattenhofer. Distributed verification and hardness of distributed approximation. SIAM Journal on Computing, 11112255-265, 2012. doi: N0::10.1137/110855188
Danny Dolev and Tomás Feder. Determinism vs. nondeterminism in multiparty communication complexity. SIAM Journal on Computing, 21(5):889-88) 895, 1992.
Andrew Drucker, Fabian Kuhn, and Rotem Oshman. On the power of the congested clique model. In Proc. 33rd ACM Symposium on Principles of Distributed Computing (PODC 2014), pp. 367-376, 2014. doi: 10. 110.1144/26116622261111
Ankit Garg, Tengyu Ma, and Huy Nguyen. On communication cost of distributed statistical estimation and dimensionality. In 7. Ghahramani, M. Welling, C. Cortes, N. D. Lawrence, and K. Q. Weinberger (eds.), Advances Neural Information Processing Systems 27 (NIPS 2014), pp- 2726-2734. Curran Associates, Inc., 2014.
Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In Advances in neural information processing systems, pp. 315-323, 2013.
Frederik Künstnnr. Fully quantized distributed gradient descent. Master's thesis, École polytechnique epfl ch http://eeee/////e/ 234504.//22344.... whw...ccceecoor///2222
fédérale de Lausanne, 2017. URL htttt:://nnfosiiieee
Mu Li, David G Andersen, Jun Woo Park, Alexander Smola, Amr Ahmed, Vanja Josifovski, James Long, Eugene Shekita, and Bor- Bor-Yinng Su. Scaling distributed machine learning with the parameter server. In Proc. 11th USENIX Symposium on Operating Systems Design and Implementation (OSDI 2014), pp. 583-598, 2014.
S. Magnússon, H. Shoori-Ghadikeee learning and optimization under limited communication. In Proc. 53rd Asilomar Conference Sig- nals, Systems, and Computers (ACSSC 2019), 2019, doi: 109/E/CCNNT44446 2019,9049052.
Ghadikolaei, and N. Li. On maintaining linear convergence of distributed
Jeff M Phillips, Elad Verbin, and Qin Zhang. Lower bounds for number-in-hand multiparty com- munication complexity, made easy. In Proc. 23rd Annual ACM-SIAM symposium on Discrete Algorithms (SODA 2012), pp. 486-501, 2012.
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), pp. 3027-3036, 2017.
Ohad Shamir. Fundamental limits of online and distributed algorithms for statistical learning and estimation. In Advances in Neural Information Processing Systems 27 (NIPS 2014), pp. 163-171, 2014.
Ananda Theertha Suresh, Felix X Yu, Sanjiv Kumar, and H Brendan McMahan. Distributed mean estimation with limited communication. In Proceedings of the 34th International Conference on Machine Learning (ICMI 2027), pp. 3329-3337. JMLR. org, 2017.
Hanlin Tang, Chen Yu, Xiangru Lian, Tong Zhang, and Ji Liu. DoubleSqueeze: Parallel stochastic gradient descent with double- -assl compensmmee compression. In Proc. 36th International Conference Machine Learning (ICMI. 2019), volume 97, pp. 6155-6165, 2019.
10

---

Under review as a conference paper at ICLR 2021
John N Tsitsiklis and Zhi- Quan Luo. Communication complexity of convex optimization. Journal of Complexiry, 3(3):231-22 143,, 1987.
Santosh S. Vempala, Ruosong Wang, and David P. Woodruff. The communication complexity of optimization. In Proceedings the 2020 ACM-SIAM Symposium Discrete Algorithms (SODA 2020), pp. 1733-1752, 2020. doi: 10. 11..111/1.9911881 1117/11.7866111 1975994.106
David P. Woodruff and Qin Zhang. When distributed computation is communication expensive. Distributed Computing, 30(5):309-322 2017. doi: 10.11000//00444400444400000
Blake Woodworth and Nati Srebro. Tight complexity bounds for optimizing composite objectives. In Advances in Neural Information Processing Systems 29 (NIPS 20/6), pp. 3639-3647, 2016.
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). pp. 8496-8506, 2018.
Andrew Chi-Chin Yao. Probabilistic computations: Toward a unified measure of complexity. In Proc. 18th Annual Symposium Foundations of Computer Science (FOCS 1977), pp. 222-227, 1977. doi: 10. 100//S/S 1977.24.
Science
Yuchen Zhang. John Duchi, Michael Jordan, and Martin J Wainwright. Information -theorett lower bounds for distributed statistical estimation with communication constraints. In Advances in Neural Information Processing Systems 26 (NIPS 2013), pp. 2328-2334 2013.

---

Under review as a conference paper at ICLR 2021
Table I: Comparison of existing lower bounds total communication required to solve (1). 'BC' denotes results for broadcast model, and 'MP' denotes results for passage-passing model. Note that lower bounds for the broadcast model also apply to the message-passing model.
Problem
Lower bound
Model
Quadratic optimisation
!idlog 3d
2-node
Det.
Tsitsiklis & Luo (1987)
O(dlog 3d
BC
Rand.
Garg et al. (2014)
SoNNlog Ad
MP
Det.
83.1
lNNNlog
MP
Rand.
33.2
No
Gaussian mean estimation
9(Nd/ log N)
BC
Rand.
Garg et al. (2014)
((Nd)
BC
Rand.
Braverman et (2016)
Table 2: Upper bounds for distributed optimisation over 3-smooth, a-strongly convex input functions with condition number 'BC' denotes results for broadcast model, and 'MP' denotes results for message-passing model. Note that upper bounds for the message- message-passing model also apply to the broadcast model, but not vice versa.
Input functions
Upper bound
Model
Constant
24) O(Ndlog
BC
Rand.
Alistarh et al. (2017); Künstner (2017)
General
O (Id log(ke) log Bd
2-node
Det.
Tsitsiklis & Luo (1987)
O (NRdlog (ogd) log 3d)
BC
Det
Magnússon et al. (2019)
O( log log 3d
MP
Det.
64
A OMITTED PROOFS, SECTION 3.2
A. PROOF OF LEMMA 6
Proof of Lemma 6. 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 d,N
and error probability 1/3, implying claim. Given input (b,, b2,................. by) for MEAN can simulate the protocol II with input functions f((x) = Bollæ (b.))l. By the properties of quadratic functions,
A,N nodes
have F(x) Σnn fe(x)) B|| x²1 113 + C, where x² Σ' z(b.)
N
Thus, the output y of II satisfies |y - x 221 I (e/ The coordinator now outputs the closest point E T to y. We therefore have
||x-" t||2 || y y t||2 -| 2112 + 1ly +||2 = 2(E/8) 122
A.2 PROOF OF LEMMA 8
Proof of Lemma 8. Let μ denote a distribution on II (0, D, where each D-bit string is selected uniformly at random, and let ( be uniformly random on {0, P... We will prove that
D (MEAN 9 N.N) 2(N ED (2-BITSp))
Since ED! 1/3 (2-BI(S Q(D) by Lemma 7, the claim follows by Yao's Lemma.
12

---

Under review as a conference paper at ICLR 2021
Suppose that we have deterministic protocol II, for MEAN d.N with worst-case communication cost C and error probability 1/3 on input distribution y.. Given IT, define 2-player protocol I2₂ with public randomness for 2-BITS as follows; assume that Alice is given b E {0, 1] as input.
(1) Alice and Bob pick random index i [N] uniformly at select random i node using the shared randomness. Without loss of generality, we can assume that the picked node was node 1.
Alice and Bob simulate protocol II, with Alice simulating node and Bob simulating the coordinator and nodes 3.3.....M For the inputs b,, 12, by to II, Alice sets bj = z, and Bob selects the inputs b2, bg.............................. by uniformly at random by using the public randomness. Messages II, sends between the coordinator and node are communicated between Alice and Bob, and all other communication simulated by Bob internally.
(3) Once the simulation complete, Bob knows the output t T of II which satisfies |t - x 12 & (E/3)1/2 where x- = ='E T(b,)/N.
As the final step, we show that Bob can now recover Alice's 's input from f. Lety -i (b:)((N)N be the weighted average of points rbb2), r(bs),... T (bx)). We now have that N: (N 1)y rbb)) by simple calculation.
Since ||t - 2 21 S (=/ it follows that
[|(Nt - (N - 1)y) - r(b1)ll2 = ||Nt (N - 1)y - N2 + NN - 7(b1)ll2
||Nt N₂* + No - -NN =(b1)llz
= =I|Nt - N 122 = NNI - =='112 S ((E33)//2
Since the distance between any two points in S is at least (EE we have that T(22) is the only point from S within distance (5/3) from Nz (N 1)y. As Bob knows both and r(b2), 7 (bs))..... T(bx) after the simulation, he can recover the point 21 and thus infer Alice's 's input.
Now let us analyse the expected cost of II under input distribution Ç. First, observe that since the simulation runs II, on input distribution μu, the output y correct with probability 2/3, and thus the output of Iī2 is correct with probability 2/3. Now let Cn, be the worst-case communication cost of TT, and let CnT, (b,..... ..)) and (bb........ bx) denote the total communication cost and the communication used by node in II, on input b1. ..... by, respectively. Finally, let Cna, (b, r) be random variable giving the communication cost of 1l2 on input b and random bits r.
Now we have that
Es, Er (C
Σ
E, (CI1,,61,,)))
=
2D
(b, bN) N2(D
Σ
2D
b,E(0,1)
biumbb t=1
1
Σ
N
Cn, (bi...r.... bN)
2ND
by bx
Σ
2ND CT, (bi, b bn)
by b2.b,....,b bx
Cn N
2ND Cn,
by bx
Since Es, Bos,,[CC,, (b1,r)) ED! /3 (2-BITSp), and the argument holds for any protocol 11, solving
MEAN..9 d.N with error probability 1/3, we have that D (MEAN 8 d,N) 2 N ED (2-BITSp).
completing the proof.
13

---

Under review as a conference paper at ICLR 2021
B LOWER BOUND FOR NON-CONVEX FUNCTIONS, FULL VERSION
We now show simple lower bound for optimisation over non-convex objective functions. We reduce from the N- N-player set disjointness over universe of size d, denoted by DISJa,N: each player is given an input b; E {0, 13d and the coordinator needs to output 0 if there is coordinate & E [d] such that (f) = 1 for all i E [N]. and otherwise.
Theorem 12 (Braverman et al. (2013)). For å 0, N 2 and d wlog N), the randomised communication complexity of set disjointness RCC (DISJa,N) = ((Nd).
Again consider for fixed e, d and 3 the set S given by Lemma 2 with 8 = 2 /. This gives set $ with size at least (3d /3d'/2/2Ce) in [[S']. For binary string b E {0, 1) S1 define the function So by
exp(A((log(Bd))) Let identify the points in S with indices
f((x) = B s|12
if || s||2 < E/B B for with b, otherwise.
Since the distance between points in S is at least B, the functions fu are well-defined, continuous and L-iischitz
Theorem 9. Given parameters N, d, and satisfying d3/s 2(1) and (3d / wlog N), any protocol solving (I) with error probability 8 > 0 when the inputs are guaranteed to be functions for b E {0, 1311 has communication complexity N (oggo(d))g((
Proof. Assume there a protocol with the properties stated in the claim, and worst-case commu- nication cost Cn- We now show that we can use II to solve set disjointness over universe of size [S] with Cn total communication, which implies
On 2 RCC² (DISJ)ss)) = Q(N (x)()(
yielding the claim.
First, we observe that for b1, by... .2....bb by E {0, 10.1) that all contain in some position s, then we have EM (z) = 0. Otherwise, for any point x E [0, 1] consider the closest point E S to there least one b; with b, = O, and for that function fo. (x) by definition. Thus, if by, b ... by are a YES-instance for set disjointness, then inf i Σ Jo, (x) 2 e, and if b,, b2,.. by are NO-instance, then z Σ fr. (I)
By definition, II can be used to distinguish between the two cases, and thus to solve set disjointness.
C DESCRIPTION AND ANALYSIS OF THE UPPER BOUND, FULL VERSION
We now describe in detail our deterministic upper bound. Our algorithm uses quantised gradient descent, loosely following the outline of Magnússon et al. (2019). However, there are two crucial differences. First, we use carefully-calibratee instance of the quantisation scheme of Alistarh et al. (2020) to remove log d factor from the communication cost, and second, we use use two-step quantisation avoid all-to-all communication.
Preliminaries on gradient descent. We will assume that the input functions f:: 10 - TR are oo-strongly convex and fn-strongly smooth. This implies that F Σn Si a-strongly convex and [B-strongly smooth for a = Nog and / = N Bo Consequently, the functions S1 and F have condition number bounded by B/a. a. Furthermore. we assume that the local functions f, all have minimum value inf f((x) O, and thus range [0, Bod].
Gradient descent optimises the sum Σn" [x( by starting from an arbitrary point (()) E [0, 1j4. and applying the update rule
N
(1+1) = (1)
Vf(()!0),
14

---

Under review as a conference paper at ICLR 2021
where y > 0 is parameter.
Let x= denote the global minimum of F. We use the following standard result on the convergence of gradient descent; e.g. Bubeck (2015).
Theorem 13. For =3-1, we have that [|a[(+1]) 2 S (1 - -1- -=> - x= 12112-
Preliminaries on quantisation. For compressing the gradients the nodes will send to coordinator, we use the recent quantisation scheme of Alistarh et al. (2020). Whereas the original uses randomised selection of the quantisation point to obtain a unbiased estimator, we can use a deterministic version that picks arbitrary feasible quantisation point (e.g. the closest one). This gives the following guarantees:
Corollary 10 (Alistarh al. (2020)). Let R and be fixed positive parameters, and q R& be an estimate vector, and B E N be the number of bits used by the quantisation scheme. Then, there exists deterministic quantisation scheme, specified by a function Qe.R: Fd R² + Rd, an encoding function enc,, R: Rdd + {0, 1) and a decoding function dec Rd {0, 1 Rd, with the following properties:
(1) (Validity.) dec,,n enc,, (2)) Qe,1elz, q) for all x, 2. IRd with |x - 4|12 S R.
(2) (Accuracy.) [[,, 9) x1|2 S for all a, Ha with I| 4ll2 s R.
(3) (Cost.) I for any X 1, the bit cost of the scheme satisfies B O (d log X 1
C.1 ALGORITHM DESCRIPTION
We now describe the algorithm, and overview its guarantees. We assume that the constants a and are known to all nodes, so the parameters of the quantised gradient descent can be computed locally, and use W be an upper bound the diameter the convex domain ID, e.g. W d if D 00, 1]
We assume that the initial iterate z0()) is arbitrary, but the same all nodes, and set the
initial quantisation estimate g;
(0) at each i as the origin.
The algorithm proceeds in rounds t = 1,2,... .... T. At the beginning of round t + 1, each node i knows the values of the iterate 1z(*), the global quantisation estimate (()), and its local quantisation estimate qi for i = 1, 2, . N. We define the following parameters for the algorithm. Let = 8-1
and (1 k=!) 1) be the step size and convergence rate of gradient descent, and let W be such that [|z((0) x²1 S W. We define
K = 2/5,
ô = --1-
- E)/4,
/ = ôK +
R 3KW n²:
Assuming k 2 2, we have
< 1, 1/2 and K 2 1. At step f, nodes perform the following steps:
(1) Each node i updates its iterate as (++1) = (*) - ())
Each node i computes its local gradient over (1+1), and transmits it in quantised form to the coordinator as follows. Let E1 ( /(NN and p1 = R(++1) /N.
(a) Node computes V [z((((+1)) locally, and sends message m, enc .1 (V (z((((())) the coordinator.
(b) The coordinator receives messages m, for i 1, N, and decodes them as
((+1) = dec. p. (q.") ,m,). The coordinator then computes (1+1)) = -; (1+1)
(3) The coordinator sends the quantised sum of gradients to all other nodes as follows. Let
E2 8 /2 and p2 (1 + 8/2)
(a) The coordinator sends the message m enCr,,pp (I(++1) to each node
(b) Each node decodes the coordinator's message (1++)) dec p2 (t) m))
After round T, all nodes know the final iterate (T). The nodes compute their local value fz (x()))) and send an approximate value to the coordinator; specifically, each node computes a partition of the range [0, Bod] into segments of length e/N, and sends the index of the smallest segment endpoint satisfying (((x(T)) the coordinator.
15

---

Under review as a conference paper at ICLR 2021
C.2 ANALYSIS
For simplicity, we will split the analysis into two parts. The first describes and analyses the algorithm in an abstract way; the second part describes the details of implementing it in the coordinator model. For technical convenience, assume K 2 2; for smaller condition numbers, we can run the algorithm with x 2.
Convergence. = B-1, let x E (0) E Bd and qi E Rd for i 1, N be arbitrary initial values. From the algorithm description, we see that the update rule for our quantised gradient descent is
())
x (1+1) 21 - 77) (*),
(1+1)
9.9"" R((+1) /N, (, ((N))
N n(42)= Σ
qi (+11)
9 ((+1) Q .0th (1) (1+ 8/2) (8((t1)) (p(tt1//2).
Lemma 14. The inequalities
(1x(0) x"112 S n'W: [V - -9: 112 S (R(0) ((2N)
(Q1)
1/'12
(Q2)
IVF(('0)) - -q 12 S RR())
(Q3)
hold for all i, assuming that they hold for 100), (0) and (0) for i = 1 1.2....,NN
Proof. We apply induction over I; we assume that all the inequalities hold for I, and prove that they also hold for 4+1 1. Since we assume the inequalities hold for L 0, the base case is trivial.
Convergence (Q1): We have
[|o x= 1|2 = || (0 + ( -
+ x0112
S ()) - 1((0))
- x 112
S ()) - - =
I 0-' +
8-188K W Ep''
(8K + E)p' = W
Local quantisation (Q2): First, let us observe that to prove that (Q2) holds for t 1, it is sufficient to show (2(((())) - df l|2 S R(++)/N as the claim then follows from the definition of g;
((+1)
and Corollary 10. We have
11 1|2 = [[/((((())) - V/((=(0)) + V))(((0)) V)) - (9) l|2
W (x V.fi((('))
(z:(t) - (. 1011
< (0 _111/2 + OR /N
I 8 (l(((((+))) - x1 + ||x(10)
x 112) RR /N
I 20p'' W + +8R(2) /N
2/y/W/N + 688K/W/N
= (2/K + K//NNN
= (E - (C-8)K3p'W//
< (E - - RR(+1)NN
16

---

Under review as a conference paper at ICLR 2021
Global quantisation (23): To prove (Q3), start by giving two auxiliary inequalities. First, prove that [VF - r((++1)) 12 S 8 /2:
N
N
[VF(z(())) - 11(t1))222
f((xx(111)
Σ 112
(++1)
1=1
V fi
(1+1) 12
S (6 88(++1) /2.
Next, we want to prove ||(((]) ((++1))|p S 8 /2. Again, it sufficient to show [|r((+])
100122 & (1 + 8/2) (((+1), as the claim then follows from the definition of q ((+1) and Corollary 10.
We have
li 2 ||(((t1) VF(x((+)) VF(x(++)) VFF())))))((())))))))))))))))))) VF(x()) - / s 68((+1) /2 / 31(x((+1) - 2111 112 + &RR())
11
< [|((tt1)
(VF(<( - -0
I (8((+1) /22 R(++1) (1 + 8/2)
where the last inequality follows from the argument used in the proof of (Q2).
Finally, putting things together, we have
g (1+2)) 2
(VF(x(()))) - ((+1)) + (((+1) ( 1| (VF(a((t)) ) (((t1) 1|2 + ||[tt])
- (
S 8R(+1)/2 + 88((+1)( /2 8R((+1),
completing the proof.
Lemma 15. For any E 0 and 2 2x log W. we have || -x01 S s.
Proof. By Lemma 14, we have [|x((t) - x=112 S n = (1- (11-(1-w)) S (e-(w-
Assuming
t t I-# log we have
e -1--) (1- log w/e W loge// W=
= WW//W =s.
The claim follows by observing that 1 2x by definition.
Communication cost. Finally, analyse the distributed implementation described the be- ginning of this section, and analyse its total communication cost. Recall that we assume that the parameters and 3 are known to all nodes, so the parameters of the quantised gradient descent can be computed locally, and use W = d2/2, Note that W is the only parameter depending the input domain, so the algorithm also applies for arbitrary convex domain DD C Rd, setting W to be the diameter of DD.
Since < 1, we have by Lemma 10 that the each of the messages sent by the nodes has length at most Od 8-1) bits. Assuming 2, we have
2x --k-r I log 8k
log 8-1 log
Since the nodes send total of 2N messages of log k) bits each, the total communication cost of single round is O(Nd log x) bits.
To get (Tx))) - F F(x*)22 S we need [T=:(T) - x²1 S (E/3)2. By Lemma 15, selecting T = O2 SW is sufficient. Finally, using W (2) we have that the total communication cost of the optimisation is O(N log k log Ad) For the transmission of the local function values fa(x") there are at most (3nd + 1)N/E possible values, so each node needs to send Olog 3d/s) bits.
17


Reviews:
[{"review_id": "w1vrzpTRsSn", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies the minimum number of bits that need to be communicated between N machines that jointly seek to minimize \\sum_{i=1}^N f_i(x) where each function f_i is held by one of the machines, and the domain D of each f_i is a subset of R^d. The motivation for this is large optimization tasks that have to be solved often in machine-learning problems: the hope is to learn the limits to which the number of bits communicated in popular machine learning tasks can be optimized. \n\nWhile the problem studied in the rest of the paper is cast purely in theoretical terms in the classical Message-Passing setting in distributed optimization, and therefore a conference with more theoretical bent seems more appropriate, given the many prior works that have appeared in machine learning conferences I am not too worried on this count. \n\nAs the main result, the paper shows that for quadratic optimization (i.e., even if all the f_i's are guaranteed to be quadratic functions),  to obtain an additive epsilon approximation (to the minimum of \\sum_i f_i(x)) deterministically requires \\Omega(Nd*log(beta*d/epsilon)) bits and the same for randomized approximation is \\Omega(Nd*log(beta*d (N*epsilon))) bits. Here beta is the smoothness parameter of \\sum_i f_i. The closest related earlier work showed that in the 2-node setting one requires \\Omega(d*log(beta*d/epsilon)) bits. The generalization to N machines of this earlier result is a natural extension to study. \n\nA couple of concerns:\n\n1) Given the result for the two machine setting, what would one expect to be the lower bound in the N machine setting? Perhaps the proof maybe involved, but are there reasons to expect the lower bound to take any other form? If there are, they don't seem to be present in the paper. \n\n2) Even if the result is not unexpected, proving it could well be complicated. So if there are clear technical innovations compared to prior work that would be a good plus. However the degree of technical advance is not quite clear to me --- I have not worked in this area to say for sure. The authors point out that the innovation is here is the connection built to communication complexity in the context of real-valued optimization-tasks, but I am not so sure if there is enough to clear the ICLR bar.\n\nOverall this is a problem whose answer is good to know. The paper is written quite well, and is situated well in the landscape of related work. I am not sure if it clears the ICLR bar, perhaps accept if room.", "extra_scores": {}, "extra_text": {}}, {"review_id": "sbBvBzAYYYw", "reviewer": "AnonReviewer4", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies the problem of optimizing a sum of $\\beta$-strongly convex and $\\alpha$-strongly smooth functions in the distributed point-to-point communication setting. It provides deterministic and randomized lower-bounds on the communication bit complexity and a quantized-based algorithm with asymptotic matching upper-bounds (for constant $\\beta/\\alpha$).\n\nOn the positive side, the paper contributes to a line of work which has significant practical relevance -- performing optimization over a set of functions distributed across many independent computing devices. It studies a specific task in this context from the point of minimizing the communication cost.\n\n\nRegarding the model: I don't understand why the paper makes a setup about \"message-passing model\" just to say that their setup is equivalent to \"coordinator model\". Why not from the beginning say that it uses the \"coordinator model\"?\n\nTheorem 4 seems to assume a (rather strict) regime where $d > O(N)$. That is, for $d \\beta / (N^2 \\varepsilon)$ to be a constant, and where $\\beta = \\beta_0 N$, we have $d > O(N \\varepsilon / \\beta_0)$. Is it justified to assume that the input dimension is at least as large as the number of devices? I would expect the situation to be the opposite.\n\nThis is a mainly theoretical work, but it still would be nice to motivate why the setup/task considered in this work (e.g., minimizing $\\sum_i f_i(x)$ where each machine/device holds potentially different functions) is practically relevant. If it is mainly of theoretical relevance, then it would be nice to give reasons why this optimization task is an important one. This is not necessarily a critic on the relevance of the problem, but rather a comment that having more background would enable a reader to put the results into a broader perspective.\n\nRegarding related work, what are other optimization tasks on a set of functions that would \"make sense\" to consider next? What are the ones that are important to understand, either theoretically or practically?\n\nThe appendix has a substantial amount of typos; not all of them are noted below.\n\n\n\nTypos and suggestions:\n\nPage 2: \"... is somewhat subtle, so defer the details...\" -> \"... is somewhat subtle, so we defer the details...\"\n\nPage 2: \"... which allows arbitrary centring of iterates...\" -> \"... which allows arbitrary centering of iterates...\"\n\nPage 6 (Definition of $D$, between Theorem 4 and Definition 5): Do you mean \"$D = \\Omega(...)$?\" instead of \"$\\Theta(...)$\"?\n\nPage 7: \"... we use it works in...\" -> \"... we use works in...\"\n\nPage 11, Line 3 of Lemma 6 proof: MEAN^{\\varepsilon, \\beta}_{d,N} should be MEAN^{\\varepsilon, 4 \\beta}_{d,N}\n\nPage 11, Line 5 of Lemma 6 proof: Should \"$F(x) = ... = 4 \\beta \\| x-x^* \\| + C$\" be \"$F(x) = ... = 4 \\beta \\| x-x^* \\|^2$\"?\n\nPage 11, Line 2 of Lemma 8 proof: From what I understand, we need zeta to be in the packing set S so that we can \"infer Alice's input\" (first paragraph after the chunk of equations on Page 12). Why is it enough to be uniformly random on {0,1}^D?\n\nPage 11, last line of Lemma 8 proof: Should $\\zeta$ be $\\zeta_{1/2}$?\n\nPage 12, first line of (2) in Lemma 8 proof: Would be nice to explicitly state that \"node 1\" is where the \"WLOG i=1\" is used.\n\nPage 13, definition of $f_b(x)$: I had a bit of difficulty understanding the definition of $f_b(x)$ as it is. Maybe define a mapping function $g$ from $S$ to $[|S|]$, then use $g(s)$ when indexing the bit-string $\\{0,1\\}^{|S|}$?\n\nPage 13, line before Theorem 9: In paper: \"... the functions $f_T$ are well-defined...\" Do you mean: \"... the functions $f_b$ are well-defined...\"?\n\nPage 15, line 1 in proof of Q1: \"... + x^*||_2\" -> \"... - x^*||_2\"\n\nPage 15, line 2 to 3 in proof of Q1: It seems that the proof from lines 2 to 3 assumes that $x^{(t+1)} = x^{(t)} - \\gamma \\nabla F(x^{(t)})$. While this is true for performing gradient descent directly, why is it still true after the quantization stuff?\n\nPage 15 (last text line) and Page 16 (4th text line): There are references to \"definition of $q^{(t+1)}$ and Lemma 10\". There is no Lemma 10 but only Corollary 10, which refers to the prior quantization result from Alistarh et al.\nWhat is this definition referring to and why does it suffice to only show what is shown in the proofs?\n\nPage 16, first 2 lines in the first chunk of equations: should $f_i(x^{(t+1)})$ have $\\nabla$'s in front of them?\n\nPage 16, 4th text line: \"$\\ldots \\le (1 + \\delta/2) R^{(t)}$\" -> \"$\\ldots \\le (1 + \\delta/2) R^{(t+1)}$\"\n\nPage 16, line 1 in second chunk of equations: \"$... - q^{(t+1)}\\|_2$\" -> \"$... - q^{(t)}\\|_2$\"\n\nPage 16, line 2 in second chunk of equations: \"$\\le \\|R^{(t+1)} ... - r^{(t+1)}\\|_2$\" -> \"$\\le \\|r^{(t+1)} ... - q^{(t)}\\|_2$\"", "extra_scores": {}, "extra_text": {}}, {"review_id": "m9ldXoeUkfJ", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\nThe 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.\n*******************************************\nCommunication complexity is an important bottleneck for optimization. The theoretical developments in this paper are not particularly exciting and the writing is not great. This may still be of interest to ICLR community.\n*********************************************\n\nAbstract typo: “held by a one”\n\nThe comparison to the very recent paper of Vempala et al. (2020) is a little unfair IMHO. The authors say that the main differences are (i) that Vempala et al.’s problem has natural combinatorial encoding, but that is also true for the current paper; (ii) Vempala et al. use multiplicative vs additive approximation, but the approximation requirements in this paper are also very strong. \n\n\\sigma used as a standard deviation in the introduction, and something confusing in technical sections\n\nProof of Theorem 3: how do you get the factor of N in log|S|?\n\nProof of Theorem 3: “Since communication is only used for the simulation of Π” \nYour reduction also needs communication to decide whether F(y)=0 or not. \n\nED not formally defined\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This work presents an improved lower bound on the communciation complexity of distributed optimization in some settings. While reviewers agree that the paper is addressing a challenging and important question, all reviewers questioned the significance of the contributions of this work. In particular, two reviewers felt that the novelty of this work is limited. Unfortunately, the author response was unable to adequately address these concerns.
Decision: Reject