Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper shows lower bounds for distribution optimization. For the standard distributed optimization setting with N machines each of which holds a d-dimensional function f_i and the goal is to minimize \sum_{i=1}^N f_i(x), the paper shows that \Omega(Nd log(d/N\eps)) bits of communication are necessary to obtain an \eps sub-optimal solution. The result holds both for randomized and deterministic algorithms. 

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.
main_review: The contributions here lean more towards conceptual than technical. On a technical level, the lower bound follows once the right problem has been setup, and most of the work is to frame the problem in a way such that existing machinery from communication complexity can be leveraged. I do not view this as a drawback, rather, it is nice that the proof is clean and is leveraging connections to well-established techniques. The lower bound also gets close to the right answer to the problem, and shows that vanilla distributed gradient descent is close to optimal (at least for well-conditioned problems).

The paper is quite related to the work of Vempala et al. who also show lower bounds for distributed optimization problems using communication complexity techniques. However, Vempala et al. show a lower bound to obtain an eps multiplicative approximation for the solution, which follows from the lower bound for the realizable case for linear systems. The current paper instead shows a lower bound for an eps additive approximation, which is also more directly comparable to known upper bounds.

The paper also points to an interesting problem to resolve the gap between the upper and lower bounds in terms of the condition number of the problem, resolving which would likely lead to the development of new techniques.

The paper is extremely well-written. It provides adequate context for the problem and the techniques with respect to prior work, provides sufficient intuition for the results, and outlines several future directions.

Overall, I think this is a good paper which proves a solid theoretical result for an important and practically-relevant problem, and could lead to interesting future work.

Some suggested edits:

1. tau in the proof of Lemma 5 should probably be replaced by sigma.
2. It may be worth mentioning in the beginning that there is not restriction on the sequence/topology of communication between the machines.
3. The work of Steinhardt et al. on "Memory, communication and statistical queries" seems relevant since it also proves a lower bound for distributed optimization, though I don't think it implies the result in the current paper.
4. Line 242, parenthesis around 1.

----after author response----

In light of the other reviewers' comments, it seems that the bound is not as interesting as I thought earlier. Before, I thought the paper is making the qualitative message that all machines have to communicate their entire data (in the worst case), which seems like a very interesting point to make. However, the regime when epsilon is 1/N does not seem to be right to prove such a message and does seem a bit artificial. In particular, any lower bound should be able to handle simple strategies such as subsampling, and as pointed out by another reviewer the bound only works in the current setting because with such a small error requirement, there is no other way to estimate the overall mean except by communicating the entire data. While this result could be regarded as some sort of first step towards the right lower bound without this additional factor of N, it makes it a bit less interesting. The main contribution in the paper was the conceptual message instead of technical machinery, but since the conceptual message isn't what I thought before, I am lowering my score to 6 from 7. In short, the paper is making a decent contribution and could be accepted, but I can't argue as strongly for it.
limitations_and_societal_impact: Limitations And societal impact are adequately addressed.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: In this paper, authors propose the communication complexity lower and upper bound for the sum of quadratic functions minimization in the distributed setup.
main_review: In this paper, author consider the communication bottleneck problem in distributed optimization algorithms. 
The main result of this paper is the lower-bound on the communication complexity for the quadratic functions minimization. 

This paper is pure theoretical and consider only the quadratic functions with additive error tolerance stopping criteria. 
To proof the main result, authors consider discrete model with finite input and output sets. 
Then they move from the initial problem to the problem of finding of the mean of the parameters that is necessary due to the explicit form of the sum of quadratic functions. This bound is sufficiently get from the complexity of the two-player game 2-BITS_d.
As a result, I find this theory quite nice but I am hesitating if this bound is useful in practice. Since the considered set up is quadratic functions, I would expect this minimization problem be easy enough to not talk about the communication bottle-neck and complexity.
However, the future plans to extend the theory to some other classes of inputs sounds nice. I would be interested to see the result for LASSO problem, where we have an additional $\ell_1$ regularizer that enforces some structure to the solution. I am wondering if this structure can somehow appear in this bound (if a-priori it is known that the solution is 1% dense). 
 Moreover, as far as I understand, the lower bound is not tight at all, so I would say that the discussion about its tightness is missing here.

According to the upper-bound, I am wondering, why exactly this method is selected for it. (at least we should talk about the projected gradient descent to have $x^k\in [0,1]^d$). 

limitations_and_societal_impact: yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies the problem of distributed convex optimization, where each of $N$ machines holds a local function $f_i$, and a coordinator aims to minimize the global objective $\sum_i f_i$ by using a limited amount of communication with local machines. The main contribution of this paper is a $\tilde{\Omega}(Nd)$ bits lower bound on the total communication cost. The lower bound is constructed by considering quadratic local functions and reducing the minimization problem to mean estimation and two-party communication problems. Finally, the authors show that the lower bound can be attained when $f_i$'s are strongly convex and smooth. 
main_review: Though the lower bound $\tilde{\Omega}(Nd)$ may be expected and not too surprising given previous works on the two-node settings, the result can still be useful in related directions such as federated learning. In general, the paper is well-written and the proofs are clear and easy to follow.  I have the following questions and suggestions:

1. The paper considers the private randomness model, but I wonder whether the same bound holds for the shared randomness settings (given that the problem is ultimately reduced to 2-BITS and the lower bound for 2-BITS holds for the shared randomness model).


2. In many distributed/federated learning scenarios, the communication is asymmetric; that is, the uplink communication (i.e. from each machine to the coordinator) is usually more expensive than the downlink communication.  Is there a lower bound for only the uplink communication cost (with an assumption that the downlink bandwidth is infinite)?


3. The authors may want to add some comments on whether the lower bound is tight for functions without strong convexity or smoothness assumptions.


4. Finally, it would be better to include some references and comparisons with the line of research that study the communication complexity under gradient oracle settings. See [1] and its references for example.


[1] Acharya et al. "Information-constrained optimization: can adaptive processing of gradients help?"
limitations_and_societal_impact: The authors have listed the limitations as part of future works. This work does not present any foreseeable societal consequences due to its theoretical nature.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The submission studies the theoretical coordinator model communication complexity of multiple parties, each holding a strongly convex f_i, for the task of approximately minimizing the sum f_i. The main result is a communication lower bound, which basically follows by picking the approximation parameter so restrictive that each party has to send the minimum of its f_i, to appropriate precision, in all dimensions.
main_review: Communication complexity is an important bottleneck for optimization. I am not excited by the lower bound. I am less of an expert about the algorithm side – to me their approach seems natural but not trivial. This work already inspired an ICML’21 paper that develops a more interesting algorithm. 


Lower bound parameters: the lower bound is based on the sum of quadratics || x – x_i ||^2_2, where each party holds one x_i. The lower bound holds for approximation \epsilon = O(d / N), where d = dimension, N = # of parties. The dependence on d is the natural one and is technically dealt with an off-the-shelf packing bound (any good binary error correcting code would do). The dependence on N is what makes the lower bound not exciting IMHO: with \epsilon ~ 1/N^2 per dimension and party, this obviously forces all the parties to communicate. This result may be tight in this regime, but it’s probably not so natural – on say a random input the value of the function would be on the order of magnitude of d*N, so in comparison this is a really small \epsilon. In practice, for the sum of quadratics considered in the lower bound, taking a sub-sample of the parties’ functions would probably be good enough for most applications where N is so large that we’re actually concerned about an asymptotic factor of N in the communication.


Typos: 
Line 241: “will prove” -> “we will prove”
Line 242: \ref -> \eqref

limitations_and_societal_impact: NA
review_title: null

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

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