{"id":"arxiv/2607.24827","url":"https://arxiv.org/abs/2607.24827","tags":["cs.DS","cs.CC","cs.LG","math.OC"],"score":0,"title":"Stronger Memory-Query Tradeoffs for Convex Optimization: The Limitations of Subquadratic Memory","domain":"cs.DS","source":"arxiv","authors":["Michael Menart","Aleksandar Nikolov","Ohad Shamir"],"reviews":0,"subject":"cs.DS","summary":"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 $\\tildeΩ(\\frac{d^2}{\\sqrt{m}})$ oracle queries. For deterministic optimization algorithms, we show that $\\tildeΩ(\\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 $\\tildeΩ(\\max\\{\\frac{d^{8/3}}{m^{4/3}},\\frac{d^{4/3}}{m^{1/6}}\\})$ and…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-07-21","reactions":{}}