Open Problem: The Oracle Complexity of Convex Optimization with Limited Memory
arXiv:1907.00762v113 citations
Originality Synthesis-oriented
AI Analysis
This is an incremental theoretical analysis for the optimization research community, focusing on memory efficiency in convex optimization algorithms.
The paper addresses the necessity of quadratic memory for achieving optimal oracle complexity in first-order convex optimization, aiming to characterize the minimax number of queries under memory constraints.
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.