Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper presents a perturbed stochastic gradient framework for solving the stochastic optimization problem and finding local minimum. 
main_review: This paper proposed a novel method of perturbed gradient descent and tackled the challenges of finding local minimum for general (nonconvex) optimization problems. The literature review, comparison with existing methods along with the limitations, motivation of the proposed method, and theoretical analysis were very well written and the thought process was very clear. There are a few questions and concerns, and I am listing them here:
1. As authors were trying to answer the question if PGD can get to local minimum with theoretical guarantee, I am wondering what are the most significant contributor to such guarantee. What is the interplay between the Pullback and two phase design? 
2. I am not sure if the pullback was fully justified in the theoretical analysis. For example, could you be more specific on the step-size?
3. I was expecting further justification of the proposed method with empirical study. 

Overall, I think it would be better to justify pullback with more details in the theory and with empirical study on both the step-size mechanism and the two phase design. 
 
limitations_and_societal_impact: I don't see any potential issue related to societal impact. Regarding the limitation of the work, I have already stated it in the main review section.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies the perturbed gradient methods for stochastic optimization to escap from saddle points and find local minimum. New complexity is proved, which is sharper than the previous results.
main_review: Originality: This paper studies the perturbed gradient methods for stochastic optimization to escap from saddle points and find local minimum. The new $O(\epsilon^{-3})$ complexity is proved, which is sharper than the revious $O(\epsilon^{-3.5})$ one of SSRGD, and maches the $O(\epsilon^{-3})$ one of SPIDER+DFO$^+$, which is achieved by a more complex negative curvature search. I think this is a novel contribution.

Quality: The theory is technically solid. It is supported by proofs. This is a complete work.

Clarity: This paper is written well. The proof is organized well. The main resutls are proved in only three pages.

Significance: This paper proposes a new technique and achieves the state-of-the-art result by a simpler method. It address a difficult task in a better way than previous work. I think it is a significant job. Other researchers may be likely to follow this work.

I am not familar with the topic of escaping from saddle points in nonconvex stochastic optimization. No comment and criticism for this paper.
limitations_and_societal_impact: The limitation is discussed in Remark 5.2.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This papers looks into stochastic gradient methods with the goal of avoiding saddle points in nonconvex optimization. The main contribution of this work is a *perturbed* stochastic gradient framework (called "Pullback") which, by using a particular normalization scheme, finds an $(\epsilon, \epsilon_H)$-approximate local minimum (that is, an $x$ s.t. $||\nabla F(x)|| \leq \epsilon$ and $\lambda_{\textrm{min}}(\nabla^2 F(x)) \geq -\epsilon_H$) in $\tilde{O}(\epsilon^{-3} + \epsilon_H^{-6})$ stochastic gradient evaluations. When $\epsilon_H = \sqrt{\epsilon}$ (referred to as the "classic setting" in the paper), their method results in a total of $\tilde{O}(\epsilon^{-3})$ stochastic gradient evaluations, which improves upon all previous perturbed methods. This rate also matches (in the classic setting) the rate previously attained by SPIDER-SFO+ (+Neon2) (though this previous method requires an additional negative curvature search routine).
main_review: ________  Major Comments  ________

While it is written decently well, there is a key discussion missing from the paper that, in my opinion, is crucial to better placing the work in the right context. To elaborate, the main claim of novelty in the paper is that (focusing on the "classic setting" for the moment) it achieves a $\tilde{O}(\epsilon^{-3})$ rate for reaching an approximate local minimum using a *perturbed* SGD-type method (and so, crucially, *without* needing to rely on a (black-box) negative curvature search routine). This distinction is made because (as mentioned in the summary above), this rate has previously been achieved through a combination of SPIDER-SFO+ with Neon2. This type of simplification---particularly in the absence of improved convergence rates---certainly deserves a justification that goes beyond what is now found in the paper ("In contrast to this line of works, our algorithm is simpler since it does not need to use the negative curvature search routine."). For example, exactly how much more costly is it to run the negative curvature search routine? What additional operations would it entail? Is there a (perhaps empirically motivated) setting in which perturbation really does help?

That said, I do feel this sort of improved understanding is important, in part due to earlier work in finding approximate local minima via perturbed methods (e.g., Ge et al. (2015)), and more generally as a means of validating these (intuitively appealing) perturbation schemes. These methods have also been important in the deterministic setting, e.g. Jin et al. (2017) (as the paper cites), and see also Jin et al. (2018) [3]. Admittedly this work still does not match previous methods in the general $\epsilon_H$ setting (more on that below), but its contributions are a step in the right direction.


________  Minor Comments  ________

- Title: Should be "Finding Approximate Local Minima", rather than "Finding Local Minima"


- p.1: "which matches the number of gradient evaluations for gradient descent to find $\epsilon$-stationary points" 

	- It should be clarified that this is true when only smoothness (i.e., Lipschitz continuous gradient) is assumed. With higher-order smoothness (e.g., Lipschitz continuous Hessian), better gradient evaluation complexities are possible. In fact, it would generally be helpful to mention earlier on in the paper what smoothness assumptions are made.


- p.1: "perturbed Stochastic gradient" => "perturbed stochastic gradient"


- p.1: The paper mentions "$\epsilon$-stationary points" without first defining it or contrasting it with approximate local minima.


- p.2: "Besides, we show" => "{Furthermore/In addition/etc.}, we show"


- p.2: "To compare with, we summarized related results" => "To compare with previous methods, we summarize related results"


- p.2: "Comparison of of different optimization algorithm for find approximate local minima of non convex online problems." => "Comparison of different optimization algorithms for finding approximate local minima of nonconvex stochastic problems."


- p.2: "In specific" -> "Specifically"


- p.3: "Assumption 3.2 is standard in online/stochastic optimization for finding second-order stationary points"

	- It would be better to stick to either "approximate local minima" (as defined in the introduction), or "second-order stationary point" (though this is only later defined).

	- In fact, the assumption is standard for settings outside of searching for approximate local minima; perhaps a better phrasing would be: "Assumption 3.2 is standard in online/stochastic optimization, including for finding approximate local minima, and immediately..."


- p.4: "which is in the same order as GD for finding $\epsilon$-stationary points."

	- Again, it depends on the level of smoothness assumed, and so this should be clarified.

"in the same order" => "of the same order"


- p.4: "competative" => "competitive"


- p.4: "big batch of stochastic gradient" => "big batch of stochastic gradients"


- p.4: "is that, it" => "is that it"


- p.5: In Algorithm 1, it would be nicer to e.g. have {"PullBack"} as a (right-aligned) comment (or something similar).


- p.5: "which starts at m_s-th step" => "which starts at the m_s-th step"


- p.5: "well-control" => "carefully control"


- p.6: Regarding the reference in Remark 5.2 to the lower bound of Arjevani et al. (2020): as stated, the remark is misleading, as the lower bound is for stochastic first- and second-order methods. (In contrast, SPIDER and SPIDER-based methods rely on multi-point queries). Arjevani et al. also give a stochastic first- and second-order method (Algorithm 5) which achieves (ignoring Lipschitz and variance parameters) a rate of $\tilde{O}(\epsilon^{-3} + \epsilon^{-2}\epsilon_H^{-2}+\epsilon_H^{-5})$, though it also relies on a negative curvature estimation.


- p.9: "Our results show that simple perturbed gradient methods can be as efficient as more sophisticated algorithms for finding local minima."

	- The authors should clarify here that they are as efficient *in the classic setting*, and are only nearly as efficient in the more general setting.


- It would be useful to mention the following works, given the way they also highlight, in the deterministic setting, the distinction between pertubation-based and non-perturbation-based methods for finding approximate local minima: 
	- Agarwal et al. (2017) [1]
	- Carmon et al. (2018) [2]
	- Jin et al. (2018) [3]


[1] Naman Agarwal, Zeyuan Allen-Zhu, Brian Bullins, Elad Hazan, and Tengyu Ma. "Finding approximate local minima faster than gradient descent." In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 1195-1199. 2017.

[2] Yair Carmon, John C. Duchi, Oliver Hinder, and Aaron Sidford. "Accelerated methods for nonconvex optimization." SIAM Journal on Optimization 28, no. 2 (2018): 1751-1772.

[3] Chi Jin, Praneeth Netrapalli, and Michael I. Jordan. "Accelerated gradient descent escapes saddle points faster than gradient descent." In Conference On Learning Theory, pp. 1042-1085. PMLR, 2018.
limitations_and_societal_impact: The authors study the theoretical aspect of optimization algorithms, which they have adequately addressed.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper proposes a new approach called "Pullback" for escaping saddle points and finding local minimum that matches the same complexity as SGD. The approach perturbs a stochastic gradient estimators (SARAH/SPIDER) and STORM by an element uniformly on the ball of radius $r$. The proposed method is able to find an $(\varepsilon, \sqrt{\varepsilon})$-approximate local minima within $\mathcal{O}(\varepsilon^{-3.5})$ stochastic gradient evaluations. This is the fastest known algorithm achieving the optimal rate of $\mathcal{O}(\varepsilon^{-3})$. The proof techniques appear to be similar to previous works and the gradient estimator used to achieve this result is known. 
main_review: The paper is well-written and the introduction provides a sufficient background to understand the question of interest: "Can perturbed SGD methods find local minima efficiently?" Most of the paper is devoted to explaining the algorithm, which is done quite clearly, and a sketch of the proof. While I did not check all the details of the proof, the proof does appear correct and I appreciated that all the assumptions were clearly stated. 

While I appreciate the theoretical question of finding fastest known algorithm for escaping saddle points under the stochastic setting, I would like the author to elucidate why this question is of broader importance to the ML community. While I understand there is a line of research in this area, it is not clear to me that saddle points are even a problem when one uses a stochastic algorithm. Would the author be able to point to literature which shows that saddle points appear in large-scale problems and in particular, stochastic algorithms would get stuck in them? Or more broadly why finding a local minima in the stochastic setting is hard? I would highly suggest that the author add some experiments (simulated and/or real data) which (1). shows that the proposed algorithm is implementable and (2). if possible, generate a problem that has saddle points and run the proposed algorithm on such a problem. 
limitations_and_societal_impact: The authors have addressed the limitations and potential negative societal impact their work. This work is purely theoretically and mainly combining known algorithms.
review_title: null

Meta-review: The paper proposes and analyzes a stochastic first-order optimization method called “Pullback,” proving that it achieves the optimal rate of convergence to $(\epsilon,\sqrt{\epsilon})$-approximate local minima under appropriate assumptions. 

After reading the paper and discussing it with the reviewers, I concur with reviewer ADFY’s major concern, that the complexity bound proved in the paper was known under identical assumptions. It is true that prior results on perturbed SGD/AGD also did not strictly innovate on oracle complexity, but I believe the significance of those papers was mostly due to them considering very minor changes to classical algorithms. In contrast, the proposed algorithm seems like a fairly intricate modification of SPIDER and STORM.

Since the proposed theoretical guarantee does not innovate on oracle complexity and does not pertain to a well-known method, its remaining pathway to significance is through showing that the proposed algorithm performs better in practice than existing ones. In their replies, the authors suggest that this is indeed the case, and report some preliminary empirical findings backing these claims. However, the submission itself has no experiments and the information in the authors’ reply is not sufficient for getting a clear picture of the practical performance of the proposed method. For example, the authors do not indicate how the different algorithms are initialized, and whether the poor performance of SGD and SPIDER are related to a pathological initialization. Moreover, a single optimization problem would not make a convincing case for the performance of any optimization method.

With these observations in mind, I encourage the authors to revise and resubmit their paper, placing a much greater emphasis on the practical performance of the algorithm. 
Decision: Reject