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 1rm st-order or both 0rm th- and 1rm st-order information. Our results show that algorithms for this task provably benefit by incorporating either randomness or 0rm th-order information. Our results also show that, for every dimension d ≥ 1, gradient descent is optimal among deterministic algorithms using 1rm st-order queries only.