Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations
This work addresses the complexity of stochastic optimization for non-convex functions, providing fundamental limits for researchers in optimization and machine learning, though it is incremental in refining existing theoretical bounds.
The paper tackles the problem of non-convex stochastic optimization by designing an algorithm that finds an ε-approximate stationary point using O(ε^{-3}) stochastic gradient and Hessian-vector products, matching prior guarantees under weaker assumptions, and proves a lower bound showing this rate is optimal and cannot be improved with higher-order methods.
We design an algorithm which finds an $ε$-approximate stationary point (with $\|\nabla F(x)\|\le ε$) using $O(ε^{-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 $(ε,γ)$-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.