Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The authors provide a communication-efficient algorithm under centralized stochastic setting. They prove both upper bound of convergence of the algorithm and the lower bound for a class of the algorithm. Together with the upper bound and lower bound, the algorithm is min-max optimal algorithm under full participation setting and near optimal for partial participation setting.
strengths_and_weaknesses: strengths:

1. The authors provide a new algorithm that meets the min-max optimal bounds.  

2. For Herterogenety, the author does not only consider the first order but the second-order heterogeneity.

Weaknesses see the questions part.
questions: 1.  Table 1 seems to be confusing because it seems that the lower bound is larger than the upper bounds.

2. [33] also claims that they give algorithms with the optimal rates, what is the difference between the lower bounds and the algorithms?

3. There are lots of definitions missing in the main text, it would be better to move those algorithm definitions and some main technical difficulties in the main text, by compressing Table 1 and Table 2.
limitations: Yes
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper proposes a new algorithm for non-convex optimization -- CE-LSGD, which is optimal under certain heterogeneity assumptions. The authors show the algorithm optimality via matching upper-bound (convergence rate of CE-LSGD) and lower-bound (on the discussed problem class). The algorithm is analyzed for different regimes: full and partial client participation and full and stochastic gradients. Experiments on two-layer NNs support the theory.
strengths_and_weaknesses: Strengths:
- the paper presents a good survey of existing algorithms (table 1&2);
- a lower bound for the class of functions is derived;
- the proposed algorithm matches the lower bound, thus, proving optimality;

Weaknesses:
- As far as I understood, Theorems 2.1&3.1&3.2 establish generalization bounds (in Definition 3, when defining oracles, samples $z$ are derived from the distribution ${\cal D}$). Meanwhile, experiments depict the train losses only.
- Theorem 2.1. requires $\tau \leq L$, although the question regarding how often this condition is satisfied is not discussed. The only guaranteed inequality is $\tau \leq 2L$. The paper says that $\tau$ can be much smaller but, for example, in the case of convex functions (what is a subclass of non-convex functions) $\tau \geq \frac{M-1}{M} L$.

Typos/suggestions:
- line 59: usually, the optimization problem is ${\mathbb{E}} \|\nabla F(x)\|^2 \leq \varepsilon^2$;
- page 4: I would suggest adding the definition of class ${\cal F}(\Delta, L)$ in the environment of “definition” in the text so that the reader does not search for it in the text;
- Definition 3 presumable contains two typos: on line 73, $x$ is not defined; on line 74 $\sup_{x, y}$ is redundant (otherwise, the last sentence does not make sense);
- line 100: in ${\cal O}^{2, l, \sigma^2}_{F_m}$ $l$ must be capital
- Algorithm 1, line 3: what is $b_0$? (defined only later, in Theorem 3.1)
- Algorithm 1, line 12: $x_t \longrightarrow x_r$
- Algorithm 1: I would suggest leaving a tilde out over $\widetilde{m}_r$; the tilde makes the full of different notations (e.g. line 14) algorithm even more complicated; 
- Theorem 3.1: $b_0$ is an integer, rounding in the theorem is absent;
- Theorem 3.1: $1/L$ is always larger $1/\sqrt{K}L$
questions: Questions naturally arise from weaknesses:
- Do you mean generalization losses in the theorems mentioned? If yes, then vital, in my opinion, test loss comparison experiments are missing. If not, what is the role of multi-point oracles? It seems the paper lacks clarity on this question.
- Is the case when $\tau$ is much smaller than $L$ is interesting, and why? Is it practical, and why?
limitations: The second weakness ("$\tau$ is much smaller than $L$") can be considered a limitation.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper considers the nonconvex optimization problem in the centralized distributed setting and in the partial participation setting. The paper provides a new method CE-LSGD that improves previous methods by performing lighter batch stochastic gradient computations. Moreover, the paper provides the lower bounds under two heterogeneous assumptions.
strengths_and_weaknesses: 1. The first contributions **(C.1)** of the paper are the lower bounds. For simplicity, I consider Definition 2 only. Under this definition, in Theorem B.3, the authors show that $E ||\nabla f||^2 \geq \frac{\Delta \tau}{R} + ...,$ where $\tau$ is the parameters from Definition 2, while the centralized algorithm have the lower bound $E ||\nabla f||^2 \geq \frac{\Delta L}{R} + ....,$ where $L$ is Lipschitz constant such that $L \geq \tau$. I believe that these results have the following weaknesses:

    1. **Theorem B.1 (or Theorem B.3) doesn't show that $\tau$ is significantly smaller than L.** It is not clear from the example in the lower bound theorem. It means that $\tau$ and $L$ can be equal, and the author reproved the previous results. In Theorem B.3, the authors don't show that $L$ is a **tight** Lipschitz constant. In their example, the **tight** Lipschitz constant can be equal to $\tau,$ then, obviously, every constant $L \geq \tau$ is also a Lipschitz constant.
    2. The author copy-pasted the proof from Lower Bounds for Finding Stationary Points I Carmon et al., and in the proofs substituted $L$ with $\tau.$ Do not misunderstand me; there is nothing wrong with reusing (copy-pasting) the previous results and making tiny changes, but only if it leads to new results.

2. The other contributions are related to the CE-LSGD algorithm. At its core, the method is STORM (MVR) method from Momentum-based variance reduction in non-convex SGD Cutkosky el al (see also An Optimal Hybrid Variance-Reduced Algorithm for Stochastic Composite Nonconvex Optimization Liu et al.) that is extended to distributed optimization setting. As the author noted in line 117, **CE-LSGD is a mini-batch STORM, where the mini-batches are formed from the mini-batches calculated on clients**. And mini-batch STORM gets the same convergence rate as CE-LSGD. I would admit that the analysis of STORM in the distributed setting is an impactful contribution if it was not analyzed previously in the following papers:
    1. **STEM: A Stochastic Two-Sided Momentum Algorithm Achieving Near-Optimal Sample and Communication Complexities for Federated Learning Khanduri et al.** This method does not have an issue with large batch sizes, but it gets slightly worse rates due to adaptivity. 
    2. **Distributed stochastic non-convex optimization: Momentum-based variance reduction. Khanduri et al.** This method does not have an issue with large batch sizes, but it gets slightly worse rates due to adaptivity.
    3. **DASHA: Distributed Nonconvex Optimization with Communication Compression, Optimal Oracle Complexity, and No Client Synchronization Tyurin et al.** This method does not have an issue with large batch sizes and gets the same rate as CE-LSGD or BVR-L-SGD.

    At least 3 papers analyzed STORM in the distributed setting. All in all, CE-LSGD improved the analysis of the previous method by considering Definition 1 and Definition 2. 

3. In the partial participation setting, the oracle complexity of CE-LSGD is suboptimal w.r.t. $\epsilon.$ (see Table 2) and equals to $O(\frac{1}{\epsilon^2})$. For this method and Mini-batch STORM I would expect to get $O(\frac{1}{\epsilon^{3/2}})$ as in the full participation setting. (see Questions below)

I think that the authors are on the right way, and it is possible to improve the lower bounds by considering Definition 2 and Definition 3, but the current lower bounds theorems are not strong enough and can be misleading in the community. Moreover, a new method, CE-LSGD, doesn't provide a significant novelty that would be helpful in future research.
questions: Can the authors get more details on why the oracle complexity of CE-LSGD is suboptimal in the partial participation setting? It is not clear how they obtained $N = O(\frac{1}{\epsilon^2}).$ Moreover, how do the authors calculate the oracle complexity of Mini-batch STORM in the partial participation setting?
limitations: ,
review_title: null

Meta-review: metareview: This paper studied the problem of distributed stochastic non-convex optimization with intermittent communication, and considered both the full participation setting and the partial participation setting. In particular, the paper proposed a new algorithm and showed that it can improve existing methods. The weakness is in that the lower and upper bounds in the stochastic case do not match well, but I think it is ok. 
confidence: Certain
Decision: Accept