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 previously proposed method BVR-L-SGD (using bias-variance reduced gradient estimator) is claimed to be one of the best first-order optimality methods for nonconvex distributed learning. This paper integrates the parameter perturbation into the existed BVR-L-SGD, named BVR-L-PSGD, to give it second-order optimality.
strengths_and_weaknesses: Strengths：
It’s a second-order optimality upgraded version of the existed BVR-L-SGD. This is a nice extension. It will be better if the author can add more contents to show this work is the state-of-the-art second-order method.

Combining the parameter perturbation, which is an easy-installed approach that has been validated by previous works. So, it is intuitive and totally makes sense.

Weaknesses：
There is only one second-order method mentioned in the theoretical baseline. 

For the experiment side, it only compares the BVR-L-SGD and BVR-L-PSGD proposed.


questions: I think the author should clarify and emphasize the significance of such a second-order up-gradation. 
limitations: No potential negative societal impact.
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: This paper proposes a new algorithm called Bias-variacne reduced local perturbed SGD for nonconvex distributed learning to efficiently find second-order optimal points, and furthermore, it is proved in this paper that this new algorithm escapes saddle points, which implies the convergence to approximate second-order stationarity. 

This result is built on the former 1st-order convergence guarantee of BVR-L-SGD, the main techniques of the approximate second order convergence/escaping saddle points come from the well-known work of Ge. Et al and other related works since 2015. The novelty is clear.

strengths_and_weaknesses: Strength: The main strength is the theoretical contribution, it is good to see the idea of [10] on perturbed SGD can be extended to other settings.

Weaknesses: Considering the complexity of the algorithm itself, it is better if the authors can provide more guidance on the setting of parameters. 

It is not clear whether current algorithm really outperforms BVR-L-SGD (without perturbation) in the following sense: Combined with the result of “On the almost sure convergence of stochastic gradient descent in non-convex problems, 2020”, it is not hard to believe that BVR-L-SGD likely avoids saddle points.

 Is it possible to compare the quality of the second order information of the outputs by using these two algorithms, BVR-L-SGD and BVR-L-PSGD?  

The authors could have done a better survey on “escaping saddle points” literature, e.g. 

Escaping saddle points with adaptive gradient methods, Staib et al. 

questions: One question I am interested in is presented above. 
Additionally, can the authors discuss a bit on the main challenge comparing to the work of [10]? 
Is it possible to get rate of escaping saddle points without perturbation for BVR-L-SGD?
limitations: The limitation of the result in this paper might be the dependence on the parameters, how to set these parameters in real applications? From theoretical perspective, assuming the Hessian to be Lipschitz is reasonable but this constrains the application of perturbed GD in contrast to the gradient descent which only requires Lipschitz gradient to get saddle avoidance result.
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: This work proposes a new local algorithm called Bias-Variance Reduced Local Perturbed SGD (BVR-L-PSGD), via a simple combination of the existing bias and variance reduced gradient estimator and parameter perturbation. BVR-L-PSGD converges to second-order stationary point of non-convex federated optimization problem with nearly the same communication complexity as the best known one of BVR-L-SGD to find first-order stationary point, which is smaller than non-local minibatch SGD when the local datasets heterogeneity is smaller than the smoothness of the local loss. The communication efficiency over BVR-L-SGD is demonstrated via experiments. 
strengths_and_weaknesses: Originality: This work simply combines BVR-L-PSGD and parameter perturbation in algorithm design, but it has better complexity in achieving second-order stationary point for nonconvex federated optimization. Technical novelty is also explicitly expressed. Lit review looks good to me. Therefore, I think the originality is sufficient for Neurips. 
	
Quality: The claims are well supported by theoretical results on communication complexity and partially supported by experiments which have some flaws as I mentioned in my final question. 
	
Clarity: This paper is clearly written and well organized. 
	
Significance: The results are important to me since BVR-L-PSGD converges to second-order stationary point of non-convex federated optimization problem with nearly the same communication complexity as the best known one of BVR-L-SGD to find first-order stationary point, which is smaller than non-local minibatch SGD when the local datasets heterogeneity is smaller than the smoothness of the local loss. The strong gradient norm assumption and flaws in experiment kind of undermines significance, as elaborated in my questions. 
questions: (1) Could you explain what is a local method in introduction? (i.e., the difference between local and non-local methods) Which methods in Table 1 are non-local? Why are local methods in related work not listed in Table 1? 
	
(2) The first sentence in "**Open question**" in the introduction has grammar mistake that hinders understanding. Do you mean "it is not well-studied how to find second-order optimal points with **low communication cost** and **thus** we have the following research question**s**"?
	
(3) At the beginning of "**Main Contributions**", you might mention something like "which positively answered the above research questions". 
	
(4) Gradient norm bound $G$ is very strong. There are some works that did not use this assumption, like [13,14] cited in your paper. Is it possible use a weaker assumption instead? (e.g. $\frac{1}{P}\sum_{p=1}^{P}\|f_p(x)\|^2\le G^2+B^2\|\nabla f(x)\|^2$ in [13]) Also, do all the works in Table 1 use Assumptions 2-5? This relates to fairness of comparison. 
	
(5) From Table 1, it seems that to let your commmunication complexity is smaller than non-local minibatch SGD, we not only require small $\zeta$, but also small $n$ relative to $\epsilon$, right? 
	
(6) (Minor) In line 136, I think it sufficient to write #supp$(D_p)=n/P$ for every $p\in[P]$. 

(7) In Algorithm 1, $x_0=\widetilde{x} _ 0+\eta\xi_{-1}$ seems equivalent to directly initializing $x_0$. How about removing this line and replacing input $\widetilde{x}_0$ with $x_0$? 
	
(8) In Algorithm 1, lines 8-13 can be put in the block "if $t\ge 1$" as we do not need to do these when $t=0$. Acccordingly, line 11 can be simplified. Similarly, lines 16-18 can be put in "if $k\ge 1$" and line 18 can be simplified. 
	
(9) STORM variance reduction does not need large batchsize (you may see Appendix B of [1] for the complexity result that does not need assumption on gradient norm bound), but both achieves the same near-optimal sample complexity as SARAH/SPIDER. They may further reduce complexity and might be a future direction. 

[1] Cutkosky, Ashok, and Francesco Orabona. "Momentum-based variance reduction in non-convex sgd." Advances in neural information processing systems 32 (2019). 

(10) (Grammar) In line 251, you may use "poly-logarithmic factors **that** depend on". 
	
(11) In line 264, should the total number of communication rounds be $2TS+1$? 
	
(12) The hyperparameter choices in the propostions, theorems and corollaries are expressed using $\widetilde{\Theta}$. It is highly recommended to express their full form either in the main text, or in the appendix and tell the locations right after $\widetilde{\Theta}$. 
	
(13) In Figs. 1-3, the gradient norms of both algorithms increase and converge to 1 (looks very large) instead of 0. How to explain? Also, you may add plot of $-\lambda_{\min} \big(\nabla^2 f(x_t)\big)$ to demonstrate convergence of your proposed algorithm to second-order stationary point. In addition, you have made the claim that your communication complexity is lower than non-local minibatch SGD for $\zeta\ll L$, yes? If so, you would better demonstrate that by comparing with non-local minibatch SGD.
limitations: I only found the limitation mentioned in the footnote in page 8. Is that correct? Just make sure. 
That limitation is also in existing studies and thus I think it fine that this work has not addressed this limitation.
review_title: null

Meta-review: metareview: The reviewers have reached a consensus of accepting the paper.
confidence: Certain
Decision: Accept