Towards Tight Communication Lower Bounds for Distributed Optimisation
Year: 2021

Abstract:
We consider a standard distributed optimisation setting where N machines, each holding a d-dimensional function fi, aim to jointly minimise the sum of the functions PN i=1 fi(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 ⌦(Nd log d/N") total bits need to be communicated between the machines to find an additive ✏-approximation to the minimum of PN i=1 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 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.

text: PN i=1 fi(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 ⌦(Nd log d/N") total bits need to be communicated between the machines to find an additive ✏-approximation to the minimum of PN i=1 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 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.

heading: 1 Introduction
text: 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 seen significant attention dedicated to efficient distributed optimisation. One specific area of focus has been on reducing the communication cost of distributed machine learning, i.e. the total number of bits sent and received by machines in order to jointly optimise an objective function. To this end, communicationefficient variants are known for most classical optimisation algorithms, and in fact entire families of communication-compression methods have been introduced in the last decade.
We consider a standard setting in which N machines communicate by sending point-to-point binary messages to each other. Given dimension d, and a domain D ✓ Rd, each machine i is given an input function fi : D ! R, corresponding to a subset of the data, and the machines need to jointly minimise the empirical risk PN i=1 fi(x) with either deterministic or probabilistic guarantees on the output, within " additive error tolerance. That is, at least one node needs to output z 2 [0, 1]d such that
NX
i=1
fi(z)  inf x2[0,1]d
NX
i=1
fi(x) + " . (1)
This setting models data-parallel optimisation, and covers virtually all practical settings, from largescale regression, to the training of deep neural networks.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
The key parameters governing communication complexity are the problem dimension d, the solution accuracy ", and the number of machines N . Most communication-efficient approaches can be linked to (at least) one of the following strategies: dimensionality-reduction methods, such as the 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, 11, 27, 31], whose rough goal is to improve the dependency on the accuracy ", and communication-reduction methods such as reducing the frequency of communication [5, 30, 36] relative to the number of optimisation steps, or communicating via point-to-point messages via, e.g., gossiping [19, 24].
Although these methods use a diverse range of algorithmic ideas, upon close inspection, they all appear to have a worst-case total communication cost of at least Nd log(d/") bits, even for simple convex d-dimensional problems, and even for variations of the above standard setting. For instance, even though dimensionality-reduction 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 a simple example of this trade-off.) It is 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 ⌦(d log(d/")) in the case where two nodes communicate to optimise over quadratic functions. Their argument works by counting the total number of possible "-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/")) communication threshold is actually inherent for distributed optimisation in the standard case where only a 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 a single node coordinates the optimisation, and knows the final answer. This raises the question whether more communication-efficient algorithms are possible in such settings, in which communication cost is a key concern. At the same time, it is also not clear under which conditions algorithms achieving this asymptotic complexity exist.

heading: 1.1 Contribution
text: 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 a significant improvement in communication cost even if only one node (the “coordinator”) learns the final output. Specifically, even if the input functions fi at the nodes are promised to be quadratic functions x 7! 0kx x⇤k22 for some constant 0 > 0, then any deterministic or randomised algorithm where at least one node learns a solution to (1) requires
⌦ ⇣ Nd log d
N"
⌘ total bits to be communicated
for = 0N , as long as parameters satisfy d/N2" = ⌦(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 " – moreover, a non-trivial dependence between , d, N and " 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 a basic toolkit for applying communication complexity results to distributed optimisation. As
further applications, we improve the main lower bound to ⌦(Nd log( d/")) for the deterministic case if some node is required to output both the approximate minimiser z and the value of the sumPN
i=1 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 d
"
⌘ total bits communicated,
where PN
i=1 fi is ↵-strongly convex and -strongly smooth, and  = /↵ is the condition number. This is, to our 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 , this matches our main lower bound when d N , e.g. d = ⌦(N2+ ) 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 O(d log ) 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 d/N" is small, using a simple sub-sampling approach.

heading: 1.2 Discussion
text: 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 is impossible to obtain algorithms with communication cost e.g. O(Nd+ d log d/") 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/2, as required for "-approximation of the sum PN i=1 fi(z), to N nodes costs ⌦(Nd log( d/")) 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 Magnússon et al. [25], we have assumed above that the range of the input functions is [0, 1]d, and the global objective is the sum of input functions. However, the results apply even with some modifications to the setting. First, we can consider a case where the global objective is the average 1/N PN
i=1 fi instead of sum. In this case, the lower bound holds with = 0, 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 d inside the logarithm.
Limitations. We note that there still remains a small gap between our upper and lower bounds. To illustrate this, consider optimisation of the average of quadratic functions x 7! kx x⇤k22 defined over the unit hypercube [0, 1]d; in this case, the bounds take the form
⌦ ⇣ Nd log d
N"
⌘ and O ⇣ Nd log d
"
⌘ .
Moreover, the lower bound requires the parameter dependency d/N2" = ⌦(1) to hold. We note that we cannot fully get rid of this requirement: specifically, as we show in Appendix D, we can use a simple input sub-sampling approach to show that, if we have d/" = O(N ) for < 1, then problem (1) can be solved with O(N d log d/") total bits communicated using a randomised algorithm, asymptotically less than dictated by the general lower bound.
A second question our current techniques do not 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  appears to be inherent for our quantised gradient descent algorithm. However, very recent progress on quantised second-order methods [1, 15] shows that it is possible to improve this dependency in general, by leveraging second-order information together with quantisation. Specifically, Alimisis et 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 log(d/✏) complexity threshold implied by our lower bounds, within logarithmic factors in  and other terms, for a wider range of inputs. This comes at the relative cost of a more complex algorithm, and significant additional local computation.

heading: 2 Related work
text: Optimisation lower bounds. The first communication lower bounds for a variant of (1) were given in the seminal work of Tsitsiklis and Luo [32], who study optimising sums of convex functions in a two-machine setting. For deterministic algorithms, they prove that ⌦(d log( 0d/")) bits are 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 a node without information about the input needs to receive ⌦(d log( 0d/")) bits, as otherwise the node cannot produce sufficiently many different output distributions to cover all possible locations of the minimum (cf. Lemma 2.) It is 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, an algorithm where each node transmits O (d log( 0d/"))/N 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.
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 our 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 multiplicatively, 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 2. The latter reference shows that to achieve the minimax rate 2d/Ns on mean squared error requires ⌦(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 on communication-efficient 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 a 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 a deterministic upper bound in a two-node setting, with O d log(d) log( d/") total communication cost. Recently, Magnússon et al. [25] extended this
to N -node case in the broadcast model, with O Nd log(d) log( d/") total communication cost.
For randomised algorithms and constant condition number, better upper bound of O(Nd log( d/")) total communication cost in the broadcast model follows by using QSGD stochastic quantisation [2] plugged into stochastic variance-reduced gradient descent (SVRG) [16]. See Künstner [22] for a detailed treatment. While these algorithms are for the broadcast model, they can likely be implemented in the message-passing model without overhead by using two-stage quantisation; however, our algorithm also obtains optimal dependence on d deterministically.

heading: 3 Preliminaries and background
text: Coordinator model. For technical convenience, we work in the classic coordinator model [6, 12, 26], equivalent to the message-passing setting. In this model, we have N nodes as well as a separate coordinator node. The task is to compute the value of a function : BN ! A, where B and A are arbitrary input and output domains; each node i = 1, 2, . . . , N receives an input bi 2 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 (b1, b2, . . . , bN ). 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 i = 1, 2, . . . , N receives the input bi. The coordinator and nodes i = 1, 2, . . . , N receive independent and uniformly random binary strings r, ri 2 {0, 1}c, respectively, where c 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 i that received a message from the coordinator responds by sending a a message to the coordinator.
A transcript ⌧ for a node is a list of the messages it has sent and received. A protocol ⇧ is a mapping giving the actions of the coordinator and the nodes; for the coordinator, the next action is a function of its transcript so far and the private random bits r, and for node i, the next action is a function of its input bi, its transcript so far and the private random bits ri. The protocol ⇧ also determines the number of random bits the nodes receive.
We say that a protocol ⇧ computes : BN ! A with error p if for all (b1, b2, . . . , bN ) 2 BN , the output of ⇧ is (b1, b2, . . . , bN ) with probability at least 1 p. The communication complexity of a
protocol ⇧ is the maximum number of total bits transmitted by all nodes, i.e. the total length of the transcripts, on any input (b1, b2, . . . , bN ) 2 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 can be 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 nonuniform, i.e. each protocol is defined only for specific functions : BN ! A and specific input and output sets B and A. Any uniform algorithm working for a range of parameters induces a 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 is the standard setting of communication complexity.
For a function : BN ! A, the deterministic communication complexity CC( ) is the minimum communication complexity of a deterministic protocol computing . Likewise, the -error randomised communication complexity RCC ( ) is the minimum communication complexity of a protocol that computes with error probability .
For a distribution µ over BN , we define the -error µ-distributional communication complexity of , denoted by Dµ ( ), as the minimum communication complexity of a deterministic protocol that computes with error probability when the input is drawn from µ. Similarly, the -error µ-distributional expected communication complexity of , denoted by ED µ( ), is the minimum expected communication cost of a protocol that computes 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 to the randomised communication complexity; see Woodruff and Zhang [37] for a proof in the coordinator model.
Lemma 1 (Yao’s Lemma). For function and > 0, we have RCC ( ) maxµ D µ( ).
Properties of convex functions. Recall that a continuously differentiable function f is -(strongly) smooth if krf(x) rf(y)k2  kx yk2, and ↵-strongly convex if rf(x) rf(y) T (x y) ↵kx yk22, for all x and y in the domain of f . For ↵-strongly convex and -strongly smooth function f , we say that f has condition number  = /↵. If f1 is ↵1-strongly convex and 1-strongly smooth and f2 is ↵2-strongly convex and 2-strongly smooth, then f1 + f2 is (↵1 + ↵2)-strongly convex and ( 1 + 2)-strongly smooth.
A quadratic function f(x) = kx yk22 +C is -strongly convex and -strongly smooth. For " > 0, if f(x)  ", then kx x⇤k2  ("/ )1/2. A sum of quadratics F (x) = Pk j=1 ajkx yjk22, where yj 2 Rd and aj 0 for j = 1, 2, . . . , k, is a quadratic function F (x) = Akx x⇤k22 + C, where C is a constant and x⇤ = Pk j=1 ajyj/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 [0, 1]d while maintaining a minimum distance between all points.
Lemma 2 (Tsitsiklis and Luo 32). For > 0 and d 1, there is a set of points S ✓ [0, 1]d such that (1) kx yk2 > for all distinct x, y 2 S, and (2) |S| (d1/2/C )d, where C = (⇡e/2)1/2 is a constant.

heading: 4 Main lower bound
text: 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, ", 0 and = 0N satisfying d /N2" = ⌦(1), any protocol solving (1) for quadratic input functions x 7! 0kx x0k22 has communication complexity ⌦ Nd log( d/N") .
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 are finite – which will imply Theorem 3. Let N ,
d, ", and be fixed, assume d /N2" = ⌦(1). Furthermore, let S be the set given by Lemma 2 with = 3N("/ )1/2, and let T ✓ [0, 1]d be an arbitrary finite set of points such that for any x 2 [0, 1]d, there is a point t 2 T with kx tk  ("/4 )1/2. By assumption d /N2" = ⌦(1), the set S has size at least 2. Let D = dlog |S|e = ⇥(d log( d/N")). Again, for convenience, assume 2D = |S|, and identify each binary string b 2 {0, 1}D with an element ⌧(b) 2 S.
Definition 4. Given parameters N, d, ", , we define the problem MEAN", d,N as follows:
– The node inputs are from {0, 1}D, and
– Valid outputs for input (b1, b2, . . . , bN ) are points t 2 T that satisfy the condition kx⇤ tk2  ("/ )1/2, where x⇤ = PN i=1 ⌧(bi)/N is the average over inputs.
First, we observe that any algorithm for solving (1) can be used to solve MEAN", d,N .
Lemma 5. For fixed N , d, ", 0 and = 0N , any randomised protocol solving (1) for quadratic functions x 7! 0kx x0k22 with error probability 1/3 has communication complexity at least RCC1/3
MEAN", /4d,N .
Proof. Let ⇧ be protocol solving (1) with communication complexity C and error probability 1/3. We show that we can use it to solve MEAN", /4d,N with total communication cost C and error probability 1/3, implying the claim. Given input (b1, b2, . . . , bN ) for MEAN ", /4 d,N , nodes can simulate the protocol ⇧ with input functions fi(x) = 0kx ⌧(bi)k22. By the properties of quadratic functions, we have F (x) = PN i=1 fi(x) = kx x⇤k22 + C, where x⇤ = PN i=1 ⌧(bi) N . Thus, the output y of ⇧ satisfies ky x⇤k2  ("/ )1/2. The coordinator now outputs the closest point t 2 T to y. We therefore have
kx⇤ tk2 = kx⇤ y + y tk2  kx⇤ yk2 + ky tk2  2("/ )1/2 = (4"/ )1/2 .
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 to the expected communication complexity of a two-party communication problem where one player has to learn the complete input of the other player. Specifically, in the two-player problem called 2-BITSd, player 1 (Alice) receives a binary string b 2 {0, 1}d, of length d, and the task is for player 2 (Bob) to output b. Let ⇣p be a distribution over binary strings b 2 {0, 1}d where each bit is set to 1 with probability p and to 0 with probability 1 p. The following lower bound for 2-BITSd holds even for protocols with public randomness, i.e. when Alice and Bob have access to the same string of random bits:
Lemma 6 ([26]). ED1/3⇣p (2-BITSd) = ⌦(dp log p 1).
We now show that solving MEAN", d,N requires roughly N times the expected communication complexity of solving 2-BITSd for d = D and p = 1/2. Lemma 7. For N , d, ", and satisfying d /N2" = ⌦(1), we have
RCC1/3(MEAN", d,N ) = ⌦ N · ED1/3⇣1/2(2-BITSD) = ⌦(Nd log( d/N")) .
Proof. Let µ denote a distribution on QN
i=1{0, 1}D, where each D-bit string is selected uniformly at random, and let ⇣ be uniformly random on {0, 1}D. We will prove that
D1/3µ (MEAN ", d,N ) = ⌦ N · ED1/3⇣ (2-BITSD) .
Since ED1/3⇣ (2-BITSD) = ⌦(D) by Lemma 6, the claim follows by Yao’s Lemma.
Suppose now that we have a deterministic protocol ⇧1 for MEAN", d,N with worst-case communication cost C and error probability 1/3 on input distribution µ. Given ⇧1, we define a 2-player protocol ⇧2 with public randomness for 2-BITSD as follows; assume that Alice is given b 2 {0, 1}D as input.
(1) Alice and Bob pick a random index i 2 [N ] uniformly at to select a random i node using the shared randomness. Without loss of generality, we can assume that they picked node i = 1.
(2) Alice and Bob simulate protocol ⇧1, with Alice simulating node 1 and Bob simulating the coordinator and nodes 2, 3, . . . , N . For the inputs b1, b2, . . . , bN to ⇧1, Alice sets b1 = x, and Bob selects the inputs b2, b3, . . . , bN uniformly at random by using the public randomness. Messages ⇧1 sends between the coordinator and node 1 are communicated between Alice and Bob, and all other communication is simulated by Bob internally.
(3) Once the simulation is complete, Bob knows the output t 2 T of ⇧1 which satisfies kt z⇤k2  ("/ )1/2, where z⇤ = PN i=1 ⌧(bi)/N .
As the final step, we show that Bob can now recover Alice’s input from t. Let y = PN
i=2 ⌧(bi)/(N 1) be the weighted average of points ⌧(b2), ⌧(b3), . . . , ⌧(bN ). We now have that Nz⇤ (N 1)y = ⌧(b1) by simple calculation.
Since kt z⇤k2  ("/ )1/2, it follows that
k(Nt (N 1)y) ⌧(b1)k2 = kNt (N 1)y Nz⇤ +Nz⇤ ⌧(b1)k2 = kNt Nz⇤ +Nz⇤ (N 1)y ⌧(b1)k2 = kNt Nz⇤k2 = Nkt z⇤k2  N("/ )1/2 .
Since the distance between any two points in S is at least 3N("/ )1/2, we have that ⌧(b1) is the only point from S within distance ("/ )1/2 from Nz (N 1)y. As Bob knows both z and ⌧(b2), ⌧(b3), . . . , ⌧(bN ) after the simulation, he can recover the point x1 and thus infer Alice’s input.
Now let us analyse the expected cost of ⇧2 under input distribution ⇣. First, observe that since the simulation runs ⇧1 on input distribution µ, the output y is correct with probability 2/3, and thus the output of ⇧2 is correct with probability 2/3. Now let C⇧1 be the worst-case communication cost of ⇧1 and let C⇧1(b1, . . . , bN ) and C⇧1,i(b1, . . . , bN ) denote the total communication cost and the communication used by node i in ⇧1 on input b1, . . . , bN , respectively. Finally, let C⇧2(b, r) be a random variable giving the communication cost of ⇧2 on input b and random bits r.
Now we have that
Eb1,r[C⇧2(b1, r)] = X
b12{0,1}D
1
2D Er[C⇧2(b1, r)] =
X
b12{0,1}D
1
2D
X
b2,...,bN
NX
i=1
C⇧1,i(b1, . . . , bN )
N2(N 1)D
= 1
N
X
b1,b2,...,bN
1
2ND
NX
i=1
C⇧1,i(b1, . . . , bN )
= 1
N
X
b1,b2,...,bN
1
2ND C⇧1(b1, b2, . . . , bN ) 
1
N
X
b1,b2,...,bN
1
2ND C⇧1 =
C⇧1
N .
Since Eb1, [C⇧2(b1, r)] ED 1/3 ⇣ (2-BITSD), and the argument holds for any protocol ⇧1 solving MEAN", d,N with error probability 1/3, we have that D 1/3 µ (MEAN ", d,N ) N · ED 1/3 ⇣ (2-BITSD), completing the proof.
Theorem 3 now follows immediately from Lemmas 5 and 7. The result can be generalised for arbitrary convex domains D ✓ Rd as ⌦(N log s), given a point packing bound s for D as in Lemma 2.

heading: 5 Deterministic lower bound
text: While there remains a small gap between our main lower bound of Theorem 3 and the deterministic quantised gradient descent of 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 to the minimiser
x. That is, our quantised gradient descent is the communication-optimal 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 8. Given parameters N , d, ", 0 and = 0N satisfying d /" = ⌦(1), any deterministic protocol solving (1) for quadratic input functions x 7! 0kx x0k22 has communication complexity ⌦ Nd log( d/") , if the coordinator is also required to output estimate r 2 R for the minimum function value such that PN i=1 fi(z)  r  PN i=1 fi(z) + ".

heading: 6 Communication-optimal quantised gradient descent
text: We now describe in detail our deterministic upper bound. Our algorithm uses quantised gradient descent, loosely following the outline of Magnússon et al. [25]. However, there are two crucial differences. First, we use a carefully-calibrated instance of the quantisation scheme of Davies et al. [11] to remove a log d 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 fi : [0, 1]d ! R are ↵0-strongly convex and 0-strongly smooth. This implies that F = PN i=1 fi is ↵-strongly convex and -strongly smooth for ↵ = N↵0 and = N 0. Consequently, the functions fi and F have condition number bounded by  = /↵. Gradient descent optimises the sum PN
i=1 fi(x) by starting from an arbitrary point x (0) 2 [0, 1]d,
and applying the update rule
x (t+1) = x(t)
NX
i=1
rfi(x(t)) ,
where > 0 is a parameter. It is well-known, e.g. [8], that GD converges at an exponential rate in ( 1)/(+ 1) for step size = 2/(↵+ ). Preliminaries on quantisation. For compressing the gradients the nodes will send to coordinator, we use the recent quantisation scheme of Davies et al. [11]. Whereas the original uses randomised selection of the quantisation point to obtain a 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 " be fixed positive parameters, and q 2 Rd be an estimate vector, and B 2 N be the number of bits used by the quantisation scheme. Then, there exists a deterministic quantisation scheme, specified by a function Q",R : Rd ⇥ Rd ! Rd, an encoding function enc",R : Rd ! {0, 1}B , and a decoding function dec",R : Rd ⇥ {0, 1}B ! Rd, with the following properties:
(1) (Validity.) dec",R(q, enc",R(x)) = Q",R(x, q) for all x, q 2 Rd with kx qk2  R.
(2) (Accuracy.) kQ",R(x, q) xk2  " for all x, q 2 Rd with kx qk2  R.
(3) (Cost.) If " = R for any < 1, the bit cost of the scheme satisfies B = O(d log 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 ↵ 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 = d1/2 if D = [0, 1]d. We assume that the initial iterate x(0) is arbitrary, but the same at all nodes, and set the initial quantisation estimate q(0)i at each i as the origin.
We define the following parameters for the algorithm. Let = 2/(↵+ ) and ⇠ =  1+1 be the step size and convergence rate of gradient descent, and let W be such that kx(0) x⇤k  W . We define
µ = 1 1 + 1 , = ⇠(1 ⇠)/4 , R(t) = 2 ⇠ µ t W ,
where µ will be the convergence rate of our quantised gradient descent, and and R(t) will be parameters controlling the quantisation at each step. For the purposes of analysis, we assume that  2. Note that this implies that 1/3  ⇠ < 1, µ < 1, and 0 < < 1. 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 x(t), the global quantisation estimate q(t), and its local quantisation estimate q(t)i for i = 1, 2, . . . , N . At step t, nodes perform the following steps:
(1) Each node i updates its iterate as x(t+1) = x(t) q(t). (2) Each node i computes its local gradient over x(t+1), and transmits it in quantised form to the
coordinator as follows. Let "1 = R(t+1)/2N and ⇢1 = R(t+1)/N . (a) Node i computes rfi(x(t+1)) locally, and sends message mi = enc"1,⇢1(rfi(x(t+1))) to
the coordinator. (b) The coordinator receives messages mi for i = 1, 2, . . . , N , and decodes them as q (t+1) i =
dec"1,⇢1(q (t) i ,mi). The coordinator then computes r
(t+1) = PN
i=1 q (t+1) i .
(3) The coordinator sends the quantised sum of gradients to all other nodes as follows. Let "2 = R (t+1) /2 and ⇢2 = 2R(t+1).
(a) The coordinator sends the message m = enc"2,⇢2(r(t+1)) to each node i. (b) Each node decodes the coordinator’s message as q(t+1) = dec"2,⇢2(q(t),m).
After round T , all nodes know the final iterate x(T ).
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 " > 0, a dimension d, and a convex domain D ✓ Rd of diameter W be fixed. Given N nodes, each assigned a function fi : D ! R such that F = PN i=1 fi is ↵-strongly convex and -smooth, the above algorithm converges to a point x (T ) with F (x(T ))  F (x⇤) + " using
O ⇣ Nd log  log W
"
⌘ bits of communication.

heading: 7 Discussion and future work
text: We have provided the first tight bounds on the communication complexity of optimising sums of quadratic functions in the N -party model with a coordinator. Our results are algorithm-independent, 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 one even for small d, possibly via reduction from a 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 Horizon 2020 research and innovation programme (grant agreement No 805223 ScaleML).

Review summaries:
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.   The 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).  The lower bounds are shown via interesting applications of standard communication complexity machinery. The upper bound follows via relatively simple modifications to existing quantization techniques.

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.