Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper studies convergence of compressed SGD to a first-order stationary point. The paper considers unbiased compressors and improves state-of-the-art convergence rate and communication complexity for both finite-sum and stochastic settings. The algorithms presented in the paper differ in update rules and their requirement for periodical synchronization. The paper uses unbiased RandK compressor with the proper K to avoid synchronization.

strength_and_weaknesses: I have the following suggestions about the paper:
-- I think the paper would benefit from outlining the proofs
-- The proofs look similar to that of MARINA. Can you please elaborate on the differences between the techniques in these two papers?

clarity,_quality,_novelty_and_reproducibility: I would suggest the following changes:
-- I believe it would be better to extract Line 8 of Algorithm 1 into a separate equation.
-- I think it’s better to just follow footnote 2, and  replace all smoothness constants with L.

summary_of_the_review: Solid paper, accept.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The goal of the paper is to solve, to $\epsilon$-additive accuracy, finite-sum non-convex optimization under the coordinator model of distributed computation, with as small a communication cost as possible. Each server (there are $n$ of them) has access to an oracle: the paper studies three natural variants, the gradient, the mini-batch gradient, and stochastic gradient.
strength_and_weaknesses: STRENGTHS - I think the paper studies an important problem, is very clearly written, and seems to have done a reasonable job of comparing against prior work. 

WEAKNESSES - This isn't really a weakness, rather a question I have (perhaps the authors can address this in their rebuttal) --- Is the proposed algorithm a "distributed version" of SVRG (or some algorithm in that family)? Again, even if it is, I don't think that's a problem, I just think (if it is), it would help contextualize the paper better by discussing this connection.
clarity,_quality,_novelty_and_reproducibility: I think the paper is very nicely written! 
summary_of_the_review: I recommend acceptance of this paper: the problem is interesting in its own right and of great practical importance to modern machine learning where functions are potentially nonconvex and dimensions large, and the algorithms make intuitive sense. I also appreciate the effort put into keeping the paper clear and easy-to-understand.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The focus of this paper is on distributed nonconvex smooth optimization in a setting where there is synchronization among the $n$ workers and there is a central server that is coordinating communications among the workers. The authors are interested in obtaining an $\varepsilon$-approximate first-order stationary point as a solution to three variants of the finite-sum distributed optimization problem in which the objective function $f$ is respectively:

- $f(x) = \frac{1}{n} \sum_{i=1}^n f_i(x)$ (Gradient Setting)
- Each local function $f_i(x)$ has a further finite-sum form (Finite-Sum Setting)
- Each local function is expectation of a stochastic function (Stochastic Setting)

The authors aim to reduce the number of communications rounds needed in these three settings to achieve optimal oracle complexity, and this is accomplished through the use of independent, unbiased compressors at each worker. The resulting algorithms are respectively termed DASHA, DASHA-PAGE, DASHA-MVR, and DASHA-SYNC-MVR, where DASHA-SYNC-MVR is a variant of DASHA-MVR in which workers synchronize with each other every once in a while using uncompressed messages.
strength_and_weaknesses: **Strengths**
- The authors provide rigorous theoretical guarantees for the four different variants of DASHA for distributed nonconvex optimization. The results show that DASHA and DASHA-PAGE improve on the SOTA communications complexity without requiring any uncompressed synchronization steps. The variant DASHA-SYNC-MVR also improves on the SOTA communications complexity while requiring communications of uncompressed messages.
- Results of a substantial number of numerical experiments are provided in the paper to showcase the superiority of DASHA over the SOTA algorithm MARINA.

**Weaknesses**
- DASHA is a mash-up between MARINA and existing distributed nonconvex optimization methods. Other than the fact that three variants of DASHA get rid of the uncompressed synchronization in MARINA, this reviewer could not pinpoint a difference between MARINA and DASHA. As such, the main novelty of this work seems to be in terms of theoretical analysis of MARINA when the uncompressed synchronization step is removed. The authors could have done a better job of clarifying where does this novelty lie in the analysis (e.g., pinpointing the key analytical approaches in the lemma that helped improve the analysis).
- The experimental results are not described clearly in my opinion. It is not clear from reading the description how did the authors count the number of bits. Additionally, how exactly was the fine tuning done for the step sizes in the experiments? The results for stochastic setting don't seem as convincing for the case of $K = 2000$ and the choice of $B=1$ also seems strange.

**Some Additional Feedback**
- The mathematical expressions in the abstract have symbols that are not defined in the abstract and one has to guess about them till one gets to the later part of the paper.
- Section 1.1: Might be useful to clarify what is the expectation going to be over.
- Equation (2): We have $\frac{1}{n}$ in both this equation and in (1). Is this right?
- Definition 1.1: Does $\omega$ really belong to $\mathbb{R}$? Can it be negative?
- Section 4, Third paragraph: Why does it say that it provides a "suboptimal oracle complexity w.r.t. $\omega$"? Are not the additional factors not a function of $\omega$?
clarity,_quality,_novelty_and_reproducibility: **Clarity and Quality**
- The paper is very well written and it was a pleasure to read it.

**Novelty**
- As noted above under weaknesses, the novelty of this paper in terms of algorithmic development is minimal. One might even argue if the class of algorithms in this paper should be given a new name or should the name be a variant of MARINA. The main novelty of this work is in terms of theoretical developments, but the authors need to do a better job of clarifying the novelty of that part of the work.

**Reproducibility**
- The paper follows the narrow definition of reproducibility in the sense that a GitHub repo is present for this paper. However, the ReadMe for the repo is extremely minimal and does not satisfy the requirements for full reproducibility in my opinion.
summary_of_the_review: Overall, it is a very nicely written paper and was a real pleasure to read. The algorithmic novelty of this work seems to be overstated. The theoretical novelty of the work needs to clarified better so that the reader can appreciate it. The experiment results also need to be described in a better fashion, rather than simply being presented.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a novel propose novel methods improving the theoretical oracle and communication complexity of the previous state-of-the-art method. New methods can compress vectors, which makes them more useful in federated learning
strength_and_weaknesses: Strength: This paper proposes a novel propose novel methods improving the theoretical oracle and communication complexity of the previous state-of-the-art method. This paper is theoretically sound in general

Weaknesses: Some experiments on federated learning should be done to verify the performance.
clarity,_quality,_novelty_and_reproducibility: This paper is presented clearly,  only minor flaws.
summary_of_the_review: This paper proposes a novel propose novel methods improving the theoretical oracle and communication complexity of the previous state-of-the-art method. New methods can compress vectors, which makes them more useful in federated learning
The paper is theoretically sound, and the current version can be significantly improved in the following aspects:
1.	Page 21, 1/n^2  ∑_(i=1)^nE_C[...] should be  1/n  ∑_(i=1)^nE_C[...].
2.   Page 29,   E_h [‖h^(t+1)-∇f(x^(t+1) )‖^2 ]≤  ((1-p))/(n^2 B^2 )..... should be E_h [‖h^(t+1)-∇f(x^(t+1) )‖^2 ]≤  ((1-p))/(n B^2 )..... 
3.  Finally, some experiments on federated learning should be done to verify the performance.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper studies the problem of distributed optimization and proposes a faily of algorithms DASHA which improve upon the best known guarantees for the particular settings of interest such as every worker having access to a finite sum or a stochastic oracle. The algorithm further makes other contributions in order to make it more practical than the current SOTA (MARINA) as in it only sends compressed vectors and removes the need for sync across all clients. The reviewers are overall very positive about the method and the paper presentation and unanimously recommended an accept. 
justification_for_why_not_higher_score: The paper is not a breakthrough commensurate with an Oral accept. The reviewer scores also suggest that with most reviewers opting for a 'solid paper accept' rating.   
justification_for_why_not_lower_score: The paper is clearly a solid contribution as highlighted by the reviewers. The consistent scores across the reviewers vouches for the solidity of the paper and some reviewers have suggested a high score as well.
Decision: Accept: notable-top-25%