Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: It has been proven in previous works that SGD can escape saddle points existing in non-convex objective functions and find local minima. This paper considers non-convex optimization problems in the distributed setting where the gradients communicating between workers and the parameter server are compressed to reduce the communication cost. It shows that when the compression technique is either \mu-compression or Random-K compression then SGD can still escape from saddle points. Their analysis shows that under some reasonable assumptions the compressed SGD can reach \epsilon-SOSP after O(\epsilon^{-4}) iterations. 
main_review: This work is an incremental work that is based on the analysis of compressed SGD and saddle point avoidance properties of SGD that have been shown in previous works. However, since in practice training big models using distributed settings is essential, this work provides some guarantee about finding second-order stationary points while SGD is used. 

It is easy to follow the main text and also the proofs. They considered various scenarios and analyzed them carefully to improve the quality of their work. 



My questions 

- I was wondering how hard it is to generalize this analysis for applying a general random function to a stochastic gradient. For example, should this function be an unbiased estimator?   

- In Fig 2 it is not clear why you claim that SGD encountered and then escaped from a saddle point. Since the x-axis is based on the epoch, SGD has the ability to escape from a saddle point even after a few iterations. Also for the graph in the 2nd row, it would be more informative to depict the gradient norm at the current iteration, not the averaged one. 

limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper is concerned with finding local minima, or second order stationary points of a function $\mathbb{R}^d \to \mathbb{R}$. The key contribution of the paper is to combine the ideas of stochastic gradient descent (SGD) and compressed gradient descent (CGD). This leads to an algorithm which takes care of both the convergence rate and communication complexity, and is favorable for distributed computing. Theoretical results of the convergence and communication complexity are rigorously established, and some empirical studies are conducted. 
main_review: The idea of combining SGD and CGD might not be too novel, since there are works using these two ingredients to find the first order stationary points. However, this paper is the first instance to study rigorously finding the second order stationary points, a.k.a. escaping the saddle points, using the compressed SGD. This is important for learning problems, since the main obstacle is saddle points not the local extrema. The paper is well-written, and the results seem to be scientifically correct. However, there are still a few unclear points to me (see below), and I am not sure what is exactly the technical contribution of this paper (i.e. compare to previous works of compressed SGD applied to the first order optimization). I would consider to raise my score if the following points are addressed. 

Unclear points and suggestions:
1. l.72 and elsewhere: there is the notation $\tilde{\mathcal{O}}$ which is not explained. I understand that in other previous papers this notation is also used to hide log term, but it might be better to explain for ease of reading. 

2. l.79-83: It is unclear to me what it means "RANDOMK preserves k random coordinates", does it mean $\mathcal{C}(x)$ is $k$-dimensional? This way, how to make sense of $x - \mathcal{C}(x)$? ($x$ is $d$-dimension, while $\mathcal{C}(x)$ is $k$-dimension). The authors should explain this in a clear way.

3. Theorem 1.1: the rate of convergence is $\tilde{\mathcal{O}}(\varepsilon^{-4})$ which is slower than $\tilde{\mathcal{O}}(\varepsilon^{-2})$ established in [24, 25]. The authors may comment on this fact. Any explanation?

4. l.130-133: do you mean $\theta_i \sim \mathcal{D}_i$ in the definition of $f_i(x)$? Otherwise, the authors should make clear the definitions of $f_i, F_i, \theta_i$ and connections.

5. l.188: I guess the authors mean Line 6 of Algorithm 1 instead of Line 1 of Algorithm 6.

6. Theorem 3.1: I am a bit confused with the notations. It seems to me that $\mathcal{R}$ is a positive number as the distance in Euclidian space. But in the theorem, $t \in \mathcal{R}$ is used as an index set for the time $t$. 

7. Theorem 3.1 and 3.2: in both theorems, there is a claim that at least half of visited points are $\varepsilon$-SOSP. I wonder if this set is finite or infinite. My understanding is that this set would be infinite, so the authors may be a bit careful about what "at least half" mean (there is possibly a limiting frequency involved).

8. l.239: (JACM) should be removed.

9. What is the technical contribution of this paper in comparison with the previous ones on the first order optimization?

10. There is also some work on the perturbed gradient descent, with non-uniform perturbation, see e.g. Perturbed gradient descent with occupation time (https://arxiv.org/abs/2005.04507v1). Theoretically the proposed algorithm achieves at least the same convergence rate as in [24, 25]. They also showed in practice, the carefully chosen perturbation is efficient in escaping saddle points even with some bad initializations.
limitations_and_societal_impact: The authors have adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper presents the compressed stochastic gradient descent with random perturbations and the convergence analysis.  The results show that the proposed algorithm enjoys the same rate as the GD with random perturbations but can reduce communications.
main_review: Strengths:  
1. The authors extended the gradient descent with random perturbations to the compressed version and applied it to the distributed setting. As far as I know, this is novel.

2.The algorithm scheme uses error feedback and random noise perturbation, which is more complicated than the previous scheme. The paper combines previous techniques and develops several novel ones. 

3. The writing of this paper is very clear. The "sketch of the proof" helps a lot to get the difficulty in the analysis.

4. A very interesting is that the authors also present numerical results to demonstrate the efficiency after adding noise.  This is few in previous papers about random perturbations to escape saddle points.

Weakness: 1. Although the proof of the proposed algorithm is not obvious,   previous works (including [Chi Jin,Sai Praneeth Karimireddy]) have provided many methods. This paper should be more specific on the point, i.e., the novelty of the technique in the proof.  From my view, it seems not very difficult to get proof.  Thus, I hope the authors could answer this comment.

2.  In RANDOMK compressor, the total communication is dependent on the sparsity level. If $k=\epsilon^{\tau}$, the total communication is then$O(1/\epsilon^{4-\tau})$. Is this true？If it is true, why just set $\tau=3/4$?

I will raise the score if my concerns are addressed.
limitations_and_societal_impact: Yes.
review_title: null

Meta-review: The paper generated a fair bit of discussion, and the reviewers agree that the paper has interesting approach and combination of arguments of escaping saddle point with compressed gradient is very elegant. 
Decision: Accept (Poster)