Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations

Abstract

We design an algorithm which finds an $\epsilon$-approximate stationary point (with $\Vert \nabla F(x)\Vert \le \epsilon$) using $O({\epsilon }^{-3})$ stochastic gradient and Hessian-vector products, matching guarantees that were previously available only under a stronger assumption of access to multiple queries with the same random seed. We prove a lower bound which establishes that this rate is optimal and---surprisingly---that it cannot be improved using stochastic $p$th order methods for any $p\ge 2$, even when the first $p$ derivatives of the objective are Lipschitz. Together, these results characterize the complexity of non-convex stochastic optimization with second-order methods and beyond. Expanding our scope to the oracle complexity of finding $(\epsilon ,\gamma )$-approximate second-order stationary points, we establish nearly matching upper and lower bounds for stochastic second-order methods. Our lower bounds here are novel even in the noiseless case.

Accepted to CONFERENCE ON LEARNING THEORY (COLT) 2020

References in corpus (9)

• Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
• Stochastic Nested Variance Reduction for Nonconvex Optimization
• Natasha 2: Faster Non-Convex Optimization Than SGD
• How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD
• "Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient Descent on Non-Convex Functions
• SpiderBoost and Momentum: Faster Stochastic Variance Reduction Algorithms
• Improved second-order evaluation complexity for unconstrained nonlinear optimization using high-order regularized models
• On the Randomized Complexity of Minimizing a Convex Quadratic Function
• Oracle Complexity of Second-Order Methods for Finite-Sum Problems

Cited by in corpus (1)

• Sample complexity of variance-reduced policy gradient: weaker assumptions and lower bounds