Department of Computer Science, University of Toronto, Vector Institute · Department of Computer Science, University of Toronto · Weizmann Institute of Science and University of Toronto · University of Toronto
We prove two lower bounds for the first order oracle complexity of minimizing a
d d d -dimensional
1 1 1 -Lipschitz convex function over the unit ball with
m m m bits of memory. We first show that any such (possibly randomized) algorithm must make
Ω ~ ( d 2 m ) \tildeΩ(\frac{d^2}{\sqrt{m}}) Ω ~ ( m d 2 ) oracle queries. For deterministic optimization algorithms, we show that
Ω ~ ( min { d 1.6 , d 8 / 3 m 2 / 3 } ) \tildeΩ(\min\{d^{1.6},\frac{d^{8/3}}{m^{2/3}}\}) Ω ~ ( min { d 1.6 , m 2/3 d 8/3 }) queries are required. For all memory regimes of interest, these improves upon the previous best known lower bounds of
Ω ~ ( max { d 8 / 3 m 4 / 3 , d 4 / 3 m 1 / 6 } ) \tildeΩ(\max\{\frac{d^{8/3}}{m^{4/3}},\frac{d^{4/3}}{m^{1/6}}\}) Ω ~ ( max { m 4/3 d 8/3 , m 1/6 d 4/3 }) and
Ω ~ ( d 5 / 3 m 1 / 3 ) \tildeΩ(\frac{d^{5/3}}{m^{1/3}}) Ω ~ ( m 1/3 d 5/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
m ≈ d 2 m\approx d^2 m ≈ d 2 , where a polylogarithmic change in memory leads to a
p o l y ( d ) \mathsf{poly}(d) poly ( d ) change in the number of required oracle calls. Further, when the suboptimality is polynomially small in
d d d , our lower bound randomized algorithms is the first to show that
Ω ~ ( d 2 ) \tildeΩ(d^2) Ω ~ ( 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 d d .