Memory-Query Tradeoffs for Randomized Convex Optimization
This provides foundational theoretical limits for convex optimization algorithms, impacting algorithm design in machine learning and optimization.
The paper tackles the problem of memory-query tradeoffs in randomized first-order convex optimization, showing that any algorithm must use either Ω(d^{2-δ}) bits of memory or make Ω(d^{1+δ/6-o(1)}) queries for high precision, implying cutting plane methods are Pareto-optimal.
We show that any randomized first-order algorithm which minimizes a $d$-dimensional, $1$-Lipschitz convex function over the unit ball must either use $Ω(d^{2-δ})$ bits of memory or make $Ω(d^{1+δ/6-o(1)})$ queries, for any constant $δ\in (0,1)$ and when the precision $ε$ is quasipolynomially small in $d$. Our result implies that cutting plane methods, which use $\tilde{O}(d^2)$ bits of memory and $\tilde{O}(d)$ queries, are Pareto-optimal among randomized first-order algorithms, and quadratic memory is required to achieve optimal query complexity for convex optimization.