Open Problem: The Oracle Complexity of Convex Optimization with Limited Memory

Blake Woodworth, Nathan Srebro
Proceedings of the Thirty-Second Conference on Learning Theory, PMLR 99:3202-3210, 2019.

Abstract

We note that known methods achieving the optimal oracle complexity for first order convex optimization require quadratic memory, and ask whether this is necessary, and more broadly seek to characterize the minimax number of first order queries required to optimize a convex Lipschitz function subject to a memory constraint.

Cite this Paper

BibTeX
@InProceedings{pmlr-v99-woodworth19a, title = {Open Problem: The Oracle Complexity of Convex Optimization with Limited Memory}, author = {Woodworth, Blake and Srebro, Nathan}, booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory}, pages = {3202--3210}, 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/woodworth19a/woodworth19a.pdf}, url = {https://proceedings.mlr.press/v99/woodworth19a.html}, abstract = {We note that known methods achieving the optimal oracle complexity for first order convex optimization require quadratic memory, and ask whether this is necessary, and more broadly seek to characterize the minimax number of first order queries required to optimize a convex Lipschitz function subject to a memory constraint.} }
Endnote
%0 Conference Paper %T Open Problem: The Oracle Complexity of Convex Optimization with Limited Memory %A Blake Woodworth %A Nathan Srebro %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-woodworth19a %I PMLR %P 3202--3210 %U https://proceedings.mlr.press/v99/woodworth19a.html %V 99 %X We note that known methods achieving the optimal oracle complexity for first order convex optimization require quadratic memory, and ask whether this is necessary, and more broadly seek to characterize the minimax number of first order queries required to optimize a convex Lipschitz function subject to a memory constraint.
APA
Woodworth, B. & Srebro, N.. (2019). Open Problem: The Oracle Complexity of Convex Optimization with Limited Memory. Proceedings of the Thirty-Second Conference on Learning Theory, in Proceedings of Machine Learning Research 99:3202-3210 Available from https://proceedings.mlr.press/v99/woodworth19a.html.

Related Material