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

arXiv:2607.24827v1 Announce Type: cross Abstract: 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 show that any such (possibly randomized) algorithm must make ilde{Omega}(frac{d^2}{sqrt{m}}) oracle queries. For deterministic optimization algorithms, we show that ilde{Omega}(min{d^{1.6},frac{d^{8/3}}{m^{2/3}}}) queries are required. For all memory regimes of interest, these improves upon the previous best known lower bounds of ilde{Omega}(max{frac{d^{8/3}}{m^{4/3}},frac{d^{4/3}}{m^{1/6}}}) and ilde{Omega}(frac{d^{5/3}}{m^{1/3}}) for randomized and deterministic algorithms respectively. Notably, due to existing upper bounds, our lower bound for deterministic algorithms is the first to show a sharp oracle complexity phase transition around mapprox d^2, where a polylogarithmic change in memory leads to a mathsf{poly}(d) change in the number of required oracle calls. Further, when the suboptimality is polynomially small in d, our lower bound randomized algorithms is the first to show that ilde{Omega}(d^2) memory is necessary to nearly match the optimal query complexity among algorithms without memory constraints. Previously, such a result was only known for the regime where the suboptimality is quasipolynomially small in d.

Source: arXiv cs.LG | 2026-07-29