SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator
In this paper, we propose a new technique named Stochastic Path-Integrated Differential EstimatoR (SPIDER), which can be used to track many deterministic quantities of interests with significantly reduced computational cost. Combining SPIDER with the method of normalized gradient descent, we propose SPIDER-SFO that solve non-convex stochastic optimization problems using stochastic gradients only. We provide a few error-bound results on its convergence rates. Specially, we prove that the SPIDER-SFO algorithm achieves a gradient computation cost of O min(n 1/2 −2 , −3 ) to find an -approximate first-order stationary point. In addition, we prove that SPIDER-SFO nearly matches the algorithmic lower bound for finding stationary point under the gradient Lipschitz assumption in the finite-sum setting. Our SPIDER technique can be further applied to find an ( , O( 0.5 ))-approximate second-order stationary point at a gradient computation cost ofÕ min(n 1/2 −2 + −2.5 , −3 ) .
Update: I have read the reviewer's response and I believe their proposed corrections makes the main result correct. Therefore, I now strongly support accepting this paper. I would be quite interested in seeing high-probability analysis that shows  how (with subgaussian assumptions) to avoid the need to randomly pick a past iterate, which seems to be something no sane method would do.  ---  The paper proposes a stochastic optimization scheme for smooth nonconvex functions. The scheme combines fixed-norm stochastic gradient steps with a novel approach to unbiased gradient estimation, based on summing estimates of the increments in the gradient and periodically resetting the summation using an accurate gradient estimate. The paper provides an analysis of this scheme, claiming rates of convergence to stationarity that improve upon the best known rates for both the fully stochastic and the finite-sum settings. Additionally, the algorithm is extended to guarantee convergence to approximate second-order stationary points, and a matching lower bound is given in the finite-sum setting.  In my opinion the proposed algorithm is original and elegant, and --- if the claimed rates of convergence were proven --- would make an excellent contribution to the active line of work on efficient scalable algorithms for nonconvex optimization. Unfortunately, I believe that the proof of the main result in the paper has fairly significant gaps, and cannot be accepted in its current state.  The above-mentioned gaps stem from incorrect statements on conditional expectations. In Lemma 6, everything is conditional on the event \|v^k\| \ge 2\epsilon. Hence, the transition from Eq. (25) to Eq. (26) is based on the claim \E [ \|v^k - \nabla f(x^k) \|^2 | \|v^k\| \ge 2\epsilon ] \le \epsilon^2. However, Lemma 2 does not, and in all likelihood cannot, establish such bound on the above conditional expectation. This issue repeats in Lemma 7, where in Eq. (28) the authors (implicitly) assert that  \E [ \|v^k - \nabla f(x^k) \|^2 | \|v^k\| \le 2\epsilon ] \le \epsilon^2, which is just as problematic. Worse, when Lemma 6 is applied in the proof of Theorem 1, the expectation bound is actually stated conditional on the event {\|v^i\| \ge 2\epsilon for every i \in [K]}, so a valid proof of Lemma 6 would need to show \E [ \|v^k - \nabla f(x^k) \|^2 | \|v^i\| \ge 2\epsilon, i=1,...,K ] \le \epsilon^2, which is very unlikely to be true or provable. A similar problem exists with the application of Lemma 7.  I encourage the authors to try and fix their analysis: in my opinion doing so will be challenging but by no means a lost cause. However, some structural changes in the algorithm are likely necessary. Namely, the algorithm in its current form promises small gradient (in expectation) at its last iterate, while all other comparable methods only give a guarantee on a randomly sampled iterate --- it is likely that a correct  version of the proposed method will have to do that as well. One possible approach to sidestepping difficulties with conditioning would be to add a sub-Gaussianity assumption on the noise and appeal to martingale concentration results.   Below are two additional comments: - What about the important special case where f is convex? Does the method attain the optimal eps^{-2} convergence rate to eps-approximate global minimia? What happens when f is non-smooth? - The parameter n_0 doesn't represent a batch size, and so its name is somewhat confusing. I think it would be better to leave \mc{S}_2 as a free parameter (ranging from 1 to 2\sigma/\epsilon or n^{1/2} in the stochastic and finite-sum cases respectively). Then we have q = \mc{S}_1 / \mc{S}_2 which I think is much clearer and more intuitive.