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

[edit]

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.

Related Material