Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper studies the communication complexity (bits communicated) of distributed optimization problems where the client objectives: 
1. satisfy the PL condition, or 
2. are overparameterized generalized quadratic functions.  

It provides lower bounds for these problems and first-order algorithms with appropriate compression/decompression. The proposed algorithm for PL objectives has optimal communication complexity up to logarithmic terms in the dimension of the problem. Similarly, for quadratic overparameterized objectives, it attains optimal communication complexity (up to logarithmic terms) with high probability. It can also be "decentralized" by using the CHOCO estimator proposed by Kolsokova et al. Finally, the paper also studies a stylized feed-forward neural network and shows that in a particular regime, their algorithm also attains optimal communication complexity for it. 
strengths_and_weaknesses: The paper is well-written and clearly describes the problem and results. The results for PL functions and overparameterized quadratics are tight, which is excellent. The pyramidal neural model seemed a bit stylized, and for the usual widths used in practice, the upper bound shows no savings in communication. Overall, I like the paper but have some questions/concerns, due to which I have currently weakly accepted the paper.  

   
questions: 1. I am nitpicking, but what leads to the extra $\log(D)$ factor? Is it coming from initialization and unavoidable?

2. Can the authors show a better upper bound for the neural networks? In practice, one doesn't use such a dramatic pyramidal structure. If not, do the authors expect a better lower bound for this specific class? Or a more specialized quantization is required? It would be good to discuss this aspect, even if the authors can't provide better results. 

3. Can the overparameterized class be extended to overparameterized generalized linear models? 

4. Can the authors comment on why they need the second inequality in (2)? My intuition is that this is not necessary for smooth functions. What's unique to the overparameterized setting? 

5. What are the significant differences in the quadratic setting from the analysis of Korhonen and Alistarh, 2021?  

6. I agree that understanding the bit communication complexity is very important but in practice, reducing communication rounds is as much or often more important than lowering the bit complexity. It is because of the overheads involved in each communication between the (edge) device and the server. The communication model authors use in this paper can't capture this because each round transmits a single bit. What are the challenges to extending the current lower bound results to the [intermittent communication](https://arxiv.org/abs/1805.10222) setting to reconcile with existing results such by Arjevani and Shamir, etc.? Are there other communication models that make more sense and can better capture these aspects of communication? It is worth discussing in the paper in more detail.

7. On the lines of the previous point, I'd like to see how the quantization schemes presented here work with local update algorithms commonly used to reduce communication rounds? The moonshot goal is to come up with an algorithm that can attain optimal bit and round complexity at the same time.   

8. I would like to see more large-scale experiments. It would be even better if the authors could identify a regime where bit complexity is more critical than communication rounds and capture that in their experiments.    
limitations: N/A
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper studies an important problem in the distributed optimization:  To train an overparameterized model over a set of distributed nodes, what is the minimum number of bits required to reach zero loss. The paper gives lower bounds in two cases: PL and overparameterized case. Then it further gives multiple algorithm examples that can achieve the lower bound under certain conditions: the model is in general close to the structure of linear regression, and the quantization algorithm should be carefully designed.
strengths_and_weaknesses: This paper addresses the gap of bits complexity in distributed optimization, as many of the related papers focus on lower bounds on the communication rounds, especially in the decentralized case. The theoretical results in the paper look promising, since the paper finds the *(near) optimal* rates in two cases and two settings (with a central coordinator and fully decentralized). In terms of theory, this paper gives strong and new (to my knowledge) results. I did not check the proof line-by-line, but the asymptotic rates seem reasonable.

One concern about the theory is that I believe a discussion in terms of the Lipschitz constants should be included. In this paper, the main objective is the sum over all the local functions (not average). This implies the Lipschitz constants between local and global function might be implicitly related by a $N$ factor. I'm not sure if this would make the final bound hide an extra $N$, this should be clarified in the main paper.

My other concerns are on the settings and experiments. More specifically, I'd be interested in seeing how the bounds and tightness would adapt if we are dealing with general convex or non-convex functions (not necessarily PL or least square). On the other hand, this paper is clearly theory-driven, but more experimental results on different applications (models, datasets) would definitely be beneficial, as in small-scale applications, we wouldn't need communication compression or very large models in general.
questions: 1. How will the current bounds adapt if we include the Lipschitz constants $L_k$ and $L$, will it lose tightness if the global function is  the average over all the local functions?

2. Is it immediately clear if the tightness will still hold when the proposed algorithms are solving general convex/non-convex functions?
limitations: Please refer to the previous reviews.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This paper considers distributed (centralized and decentralized) smooth nonconvex (PL) minimization problems in the general case and in the special (quadratic) overparameterized case. The authors give lower bounds on the amount of information transferred in terms of dimension, number of agents, amount of data, and solution accuracy. Then the authors give an algorithm by which these lower bounds can be achieved. The algorithm uses an unusual but not new quantization. In general case (Section 4.1), the algorithm is no different from those already encountered in the community. In the quadratic-overparameterized case, the key is the use of an additional transformation $F$ and an inverse $\tilde F$. The authors also give a decentralized version of the algorithm using a gossip protocol with compression.
strengths_and_weaknesses: I was generally interested in dealing with this work. I was left with a mixed impression of the work. Below I will outline my thoughts, questions, and comments in the order of the paper. 

0) The paper is fairly easy to read, in some cases the presentation could have been improved (see below), but overall I had no problem getting into the results.

1) Literature review: it seemed to me that a literature review could be more complete. In particular, one of the most active authors in the field of compressed optimization is P Richtarik. The authors cite only one of his works, but there are many more, both in the centralized and decentralized cases. This is important not only to note Richtarik's contributions, but also to compare your results with those available in the literature (see below, point 3).

2) Lower bounds: I think it is important here to clarify which factors are important to us when deriving lower bounds: $N$, $K$, $D$, $e$, $L$, $\mu$ and $B$, where $B$ is the number of bits used in the current data type (e.g. 32 or 64 bits). If I understand correctly, the bounds take into account the presence of $B$, but do not depend on it. I think it is important to reflect this. 

3) For me, the compressor from Definition 4 turned out to be new. It is not an invention of the authors, but I read the original paper about it. Thanks for this experience!

4) Upper bounds in the $C_{pl}$ case: my feeling is that these are not good bounds. The authors' estimate (in terms of $L$, $M$, $\mu$) is equal to $\mathcal{O}\left( \frac{L^2 M^2}{\mu^4}\right)$, this is a very large number. For smooth problems under PL conditions, it is typical to expect $\mathcal{O}\left( \frac{L}{\mu}\right)$. For example, the compression method from [1] has such results. If we remember about communications, then the estimate (in bits) from the work [1]  looks like 
$$
\mathcal{O}\left( \frac{BD}{\sqrt{K}} \cdot \frac{L}{\mu}\right),
$$
where $K$ is a number of agents, $B$ is the number of bits used in the current data type (e.g. 32 or 64 bits). This is the square root of $K$ times better than for the uncompressed method. The authors' estimate is
$$
\mathcal{O}\left( D \log_2 D \cdot \frac{L^2 M^2}{\mu^4}\right)
$$
Even if we forget about $L$,$\mu$ and $M$, it is not obvious to me which is smaller $\log_2 D$ or $\frac{B}{\sqrt{K}}$. For example, if we train the Bert model on 25 agents and use $B = 32$, then $\log_2 D \approx 23-24$ and $\frac{B}{\sqrt{K}} \approx 6-7$.That's why I stress that comparison with other results is very important! There are many works, not only [1].

5) The overparameterized case: this is the first time I met such an overparameterized assumption (Definition 2), although I saw many papers where simpler things are introduced as overparameterization. Therefore, Definition 2 is very specific and in the literature it occurred only 1 time. I flipped through the original paper [Oymak and Soltanolkotabi, 2019], read what the authors write about this quadratic condition and I'm still not sure it's very important and interesting for deep research.  My concerns are related to the fact that despite the improvements in convergence in terms of $N$ and $D$, in terms of $L$ and $\mu$ we are far from good convergence estimates, namely $\mathcal{O}\left( \frac{L^4}{\mu^4}\right)$. And this effect is noticeable both in the original paper and in the one under review.
At the moment the most important point of this paper is to understand how interesting this condition and the results around it: how wide a class of problems satisfies it (perhaps the authors will be able to add something here besides what is written in the work), what order of gain can be obtained for certain problems (due to the fact that we change $D$ to $N$, but lose significantly in $L/\mu$) and so on. Now it seems to me that the game is not worth the candle.

6) Decentralized results seemed to me bonus and not particularly interesting, it uses a multistep gossip protocol with compression, and the authors uses the classic sign compression, not special from Definition 4. The essence of this method is that it is a centralized method, but with a slight inexactness in averaging. It is obvious to me that this can be done.

**Conclusion:**

I am looking forward to the discussion process with the authors and fellow reviewers to discuss this work. This is important to me because so far I have mixed feelings, many questions, and have not taken a clear view of the paper. At this point, I will give a borderline reject to motivate  the authors to take an active part in the discussion.

[1] Gorbunov E. et al. MARINA: Faster non-convex distributed learning with compression //International Conference on Machine Learning. – PMLR, 2021. – С. 3788-3798.
questions: Please, see section "Strengths And Weaknesses"
limitations: No limitations and potential negative societal impact
review_title: null

Meta-review: metareview: This paper considers the following problem in distributed optimization: To train an overparameterized model over a set of distributed nodes, what is the minimum number of bits required to reach zero loss. The paper gives lower bounds on the bit complexity for two settings: non-convex functions satisfying a PL condition and overparameterized quadratics. The authors then give an algorithm that (1) for PL objectives, has optimal communication complexity (up to logarithmic terms in the dimension of the problem) and (2) for quadratic overparameterized objectives, attains optimal communication complexity (up to logarithmic terms) with high probability.

This paper generated significant discussion in the initial author-reviewer discussion period. Most of the reviewers were quite positive on the paper, and found the results to be interesting and relevant to the community, and found the paper to be well-written. They found the results, which provide near-optimal sample complexity for two settings (PL functions and overparameterized quadratics) to be technically strong, and were impressed by the tightness of the results. One reviewer took issue with certain limitations of the paper, including:
- A limitation of the lower bounds in the paper is that they concern only deterministic methods.
- The results are only tight with respect to the parameters $D$, $N$, and $\epsilon$, and are not necessarily tight with respect to $L$ and $\mu$.
- Some related work can be discussed in more detail.

These limitations do not seem to take away from the novelty, and neither I nor the other reviewers were convinced by the other issues raised in the discussion. As a result, I believe the paper is worth accepting as a starting point for future research in this direction. Nonetheless, the authors are encouraged to expand the discussion around these issues and limitations in the final version of the paper, as well as expand the comparison to related work.
confidence: Less certain
Decision: Accept