Open Problem: The Oracle Complexity of Convex Optimization with Limited Memory
[edit]
Proceedings of the ThirtySecond Conference on Learning Theory, PMLR 99:32023210, 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.
Related Material


