Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: 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. 

While 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. 

As 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. 

A couple of concerns:

1) 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. 

2) 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.

Overall 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.
review_title: Degree of advance or surprise over prior work is not clear.

final_score: rating: 5: Marginally below acceptance threshold
review_content: The submission studies the theoretical coordinator model communication complexity of multiple parties, each holding a strongly convex f_i, for the task of approximately minimizing the sum f_i.
The main result is a communication lower bound, which basically follows by picking the approximation parameter so restrictive that each party has to send the minimum of its f_i, to appropriate precision, in all dimensions.
*******************************************
Communication 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.
*********************************************

Abstract typo: “held by a one”

The 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. 

\sigma used as a standard deviation in the introduction, and something confusing in technical sections

Proof of Theorem 3: how do you get the factor of N in log|S|?

Proof of Theorem 3: “Since communication is only used for the simulation of Π” 
Your reduction also needs communication to decide whether F(y)=0 or not. 

ED not formally defined

review_title: Theoretical results on communication of convex (and non-convex) optimization; may be of interest?

final_score: rating: 6: Marginally above acceptance threshold
review_content: 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$).

On 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.


Regarding 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"?

Theorem 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.

This 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.

Regarding 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?

The appendix has a substantial amount of typos; not all of them are noted below.



Typos and suggestions:

Page 2: "... is somewhat subtle, so defer the details..." -> "... is somewhat subtle, so we defer the details..."

Page 2: "... which allows arbitrary centring of iterates..." -> "... which allows arbitrary centering of iterates..."

Page 6 (Definition of $D$, between Theorem 4 and Definition 5): Do you mean "$D = \Omega(...)$?" instead of "$\Theta(...)$"?

Page 7: "... we use it works in..." -> "... we use works in..."

Page 11, Line 3 of Lemma 6 proof: MEAN^{\varepsilon, \beta}_{d,N} should be MEAN^{\varepsilon, 4 \beta}_{d,N}

Page 11, Line 5 of Lemma 6 proof: Should "$F(x) = ... = 4 \beta \| x-x^* \| + C$" be "$F(x) = ... = 4 \beta \| x-x^* \|^2$"?

Page 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?

Page 11, last line of Lemma 8 proof: Should $\zeta$ be $\zeta_{1/2}$?

Page 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.

Page 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|}$?

Page 13, line before Theorem 9: In paper: "... the functions $f_T$ are well-defined..." Do you mean: "... the functions $f_b$ are well-defined..."?

Page 15, line 1 in proof of Q1: "... + x^*||_2" -> "... - x^*||_2"

Page 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?

Page 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.
What is this definition referring to and why does it suffice to only show what is shown in the proofs?

Page 16, first 2 lines in the first chunk of equations: should $f_i(x^{(t+1)})$ have $\nabla$'s in front of them?

Page 16, 4th text line: "$\ldots \le (1 + \delta/2) R^{(t)}$" -> "$\ldots \le (1 + \delta/2) R^{(t+1)}$"

Page 16, line 1 in second chunk of equations: "$... - q^{(t+1)}\|_2$" -> "$... - q^{(t)}\|_2$"

Page 16, line 2 in second chunk of equations: "$\le \|R^{(t+1)} ... - r^{(t+1)}\|_2$" -> "$\le \|r^{(t+1)} ... - q^{(t)}\|_2$"
review_title: An interesting theoretical work with a lack of background and motivation

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