Memory-Query Tradeoffs for Randomized Convex Optimization

06/21/2023
by   Xi Chen, et al.
0

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 δ∈ (0,1) and when the precision ϵ is quasipolynomially small in d. Our result implies that cutting plane methods, which use Õ(d^2) bits of memory and Õ(d) queries, are Pareto-optimal among randomized first-order algorithms, and quadratic memory is required to achieve optimal query complexity for convex optimization.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset