Stronger Memory-Query Tradeoffs for Convex Optimization: The Limitations of Subquadratic Memory

Michael Menart, Aleksandar Nikolov, Ohad Shamir

We prove two lower bounds for the first order oracle complexity of minimizing a $d$-dimensional $1$-Lipschitz convex function over the unit ball with $m$ bits of memory. We first s…