Memory-Constrained Algorithms for Convex Optimization via Recursive
  Cutting-Planes
Moïse Blanchard Junhui Zhang Patrick Jaillet
We propose a family of recursive cutting-plane algorithms to solve
feasibility problems with constrained memory, which can also be used for
first-order convex optimization. Precisely, in order to find a point within a
ball of radius $\epsilon$ with a separation oracle in dimension $d$ -- or to
minimize $1$-Lipschitz convex functions to accuracy $\epsilon$ over the unit
ball -- our algorithms use $\mathcal O(\frac{d^2}{p}\ln \frac{1}{\epsilon})$
bits of memory, and make $\mathcal O((C\frac{d}{p}\ln \frac{1}{\epsilon})^p)$
oracle calls, for some universal constant $C \geq 1$. The family is
parametrized by $p\in[d]$ and provides an oracle-complexity/memory trade-off in
the sub-polynomial regime $\ln\frac{1}{\epsilon}\gg\ln d$. While several works
gave lower-bound trade-offs (impossibility results) -- we explicit here their
dependence with $\ln\frac{1}{\epsilon}$, showing that these also hold in any
sub-polynomial regime -- to the best of our knowledge this is the first class
of algorithms that provides a positive trade-off between gradient descent and
cutting-plane methods in any regime with $\epsilon\leq 1/\sqrt d$. The
algorithms divide the $d$ variables into $p$ blocks and optimize over blocks
sequentially, with approximate separation vectors constructed using a variant
of Vaidya's method. In the regime $\epsilon \leq d^{-\Omega(d)}$, our algorithm
with $p=d$ achieves the information-theoretic optimal memory usage and improves
the oracle-complexity of gradient descent.