[edit]
Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations
Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:242-299, 2020.
Abstract
We design an algorithm which finds an ϵ-approximate stationary point (with ‖) 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 pth 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.