Open Problem: Do Good Algorithms Necessarily Query Bad Points?

Rong Ge, Prateek Jain, Sham M. Kakade, Rahul Kidambi, Dheeraj M. Nagaraj, Praneeth Netrapalli
Proceedings of the Thirty-Second Conference on Learning Theory, PMLR 99:3190-3193, 2019.

Abstract

Folklore results in the theory of Stochastic Approximation indicates the (minimax) optimality of Stochastic Gradient Descent (SGD) (Robbins and Monro, 1951) with polynomially decaying stepsizes and iterate averaging (Ruppert, 1988; Polyak and Juditsky, 1992) for classes of stochastic convex optimization. Basing of these folkore results and some recent developments, this manuscript considers a more subtle question: does any algorithm necessarily (information theoretically) have to query iterates that are sub-optimal infinitely often?

Cite this Paper

BibTeX
@InProceedings{pmlr-v99-ge19b, title = {Open Problem: Do Good Algorithms Necessarily Query Bad Points?}, author = {Ge, Rong and Jain, Prateek and Kakade, Sham M. and Kidambi, Rahul and Nagaraj, Dheeraj M. and Netrapalli, Praneeth}, booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory}, pages = {3190--3193}, year = {2019}, editor = {Beygelzimer, Alina and Hsu, Daniel}, volume = {99}, series = {Proceedings of Machine Learning Research}, month = {25--28 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v99/ge19b/ge19b.pdf}, url = {https://proceedings.mlr.press/v99/ge19b.html}, abstract = {Folklore results in the theory of Stochastic Approximation indicates the (minimax) optimality of Stochastic Gradient Descent (SGD) (Robbins and Monro, 1951) with polynomially decaying stepsizes and iterate averaging (Ruppert, 1988; Polyak and Juditsky, 1992) for classes of stochastic convex optimization. Basing of these folkore results and some recent developments, this manuscript considers a more subtle question: does any algorithm necessarily (information theoretically) have to query iterates that are sub-optimal infinitely often?} }
Endnote
%0 Conference Paper %T Open Problem: Do Good Algorithms Necessarily Query Bad Points? %A Rong Ge %A Prateek Jain %A Sham M. Kakade %A Rahul Kidambi %A Dheeraj M. Nagaraj %A Praneeth Netrapalli %B Proceedings of the Thirty-Second Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2019 %E Alina Beygelzimer %E Daniel Hsu %F pmlr-v99-ge19b %I PMLR %P 3190--3193 %U https://proceedings.mlr.press/v99/ge19b.html %V 99 %X Folklore results in the theory of Stochastic Approximation indicates the (minimax) optimality of Stochastic Gradient Descent (SGD) (Robbins and Monro, 1951) with polynomially decaying stepsizes and iterate averaging (Ruppert, 1988; Polyak and Juditsky, 1992) for classes of stochastic convex optimization. Basing of these folkore results and some recent developments, this manuscript considers a more subtle question: does any algorithm necessarily (information theoretically) have to query iterates that are sub-optimal infinitely often?
APA
Ge, R., Jain, P., Kakade, S.M., Kidambi, R., Nagaraj, D.M. & Netrapalli, P.. (2019). Open Problem: Do Good Algorithms Necessarily Query Bad Points?. Proceedings of the Thirty-Second Conference on Learning Theory, in Proceedings of Machine Learning Research 99:3190-3193 Available from https://proceedings.mlr.press/v99/ge19b.html.

Related Material