Open Problem: The Oracle Complexity of Convex Optimization with Limited Memory
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
Text
Woodworth and Srebro. "Open Problem: The Oracle Complexity of Convex Optimization with Limited Memory." Conference on Learning Theory, 2019.Markdown
[Woodworth and Srebro. "Open Problem: The Oracle Complexity of Convex Optimization with Limited Memory." Conference on Learning Theory, 2019.](https://mlanthology.org/colt/2019/woodworth2019colt-open/)BibTeX
@inproceedings{woodworth2019colt-open,
title = {{Open Problem: The Oracle Complexity of Convex Optimization with Limited Memory}},
author = {Woodworth, Blake and Srebro, Nathan},
booktitle = {Conference on Learning Theory},
year = {2019},
pages = {3202-3210},
volume = {99},
url = {https://mlanthology.org/colt/2019/woodworth2019colt-open/}
}