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

Sinho Chewi, Sébastien Bubeck, Adil Salim
Proceedings of The 34th International Conference on Algorithmic Learning Theory, PMLR 201:358-374, 2023.

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^{\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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v201-chewi23a, title = {On the complexity of finding stationary points of smooth functions in one dimension}, author = {Chewi, Sinho and Bubeck, S\'ebastien and Salim, Adil}, booktitle = {Proceedings of The 34th International Conference on Algorithmic Learning Theory}, pages = {358--374}, year = {2023}, editor = {Agrawal, Shipra and Orabona, Francesco}, volume = {201}, series = {Proceedings of Machine Learning Research}, month = {20 Feb--23 Feb}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v201/chewi23a/chewi23a.pdf}, url = {https://proceedings.mlr.press/v201/chewi23a.html}, 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^{\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.} }
Endnote
%0 Conference Paper %T On the complexity of finding stationary points of smooth functions in one dimension %A Sinho Chewi %A Sébastien Bubeck %A Adil Salim %B Proceedings of The 34th International Conference on Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2023 %E Shipra Agrawal %E Francesco Orabona %F pmlr-v201-chewi23a %I PMLR %P 358--374 %U https://proceedings.mlr.press/v201/chewi23a.html %V 201 %X 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.
APA
Chewi, S., Bubeck, S. & Salim, A.. (2023). On the complexity of finding stationary points of smooth functions in one dimension. Proceedings of The 34th International Conference on Algorithmic Learning Theory, in Proceedings of Machine Learning Research 201:358-374 Available from https://proceedings.mlr.press/v201/chewi23a.html.

Related Material