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

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{s}\mathrm{t}}$-order or both $0^{\mathrm{t}\mathrm{h}}$- and $1^{\mathrm{s}\mathrm{t}}$-order information. Our results show that algorithms for this task provably benefit by incorporating either randomness or $0^{\mathrm{t}\mathrm{h}}$-order information. Our results also show that, for every dimension $d\ge 1$, gradient descent is optimal among deterministic algorithms using $1^{\mathrm{s}\mathrm{t}}$-order queries only.