Memory-Constrained Algorithms for Convex Optimization via Recursive Cutting-Planes

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 ε with a separation oracle in dimension d -- or to minimize 1-Lipschitz convex functions to accuracy ε over the unit ball -- our algorithms use mathcal O(fracd2pln frac1ε) bits of memory, and make mathcal O((Cfracdpln frac1ε)p) oracle calls, for some universal constant C ≥ 1. The family is parametrized by p∈[d] and provides an oracle-complexity/memory trade-off in the sub-polynomial regime lnfrac1εggln d. While several works gave lower-bound trade-offs (impossibility results) -- we explicit here their dependence with lnfrac1ε, 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 ε≤ 1/√ 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 ε ≤ d-Omega(d), our algorithm with p=d achieves the information-theoretic optimal memory usage and improves the oracle-complexity of gradient descent.