On the complexity of finding stationary points of smooth functions in one dimension

Abstract

We characterize the query complexity of finding stationary points of one-dimensional non-convex but smooth functions. We consider four settings, based on whether the algorithms under consideration are deterministic or randomized, and whether the oracle outputs $1^{\mathrm{st}}$-order or both $0^{\mathrm{th}}$- and $1^{\mathrm{st}}$-order information. Our results show that algorithms for this task provably benefit by incorporating either randomness or $0^{\mathrm{th}}$-order information. Our results also show that, for every dimension $d\ge 1$, gradient descent is optimal among deterministic algorithms using $1^{\mathrm{st}}$-order queries only.

17 pages, 3 figures