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