Part of Advances in Neural Information Processing Systems 36 (NeurIPS 2023) Main Conference Track
Moise 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 ϵ with a separation oracle in dimension d---or to minimize 1-Lipschitz convex functions to accuracy ϵ over the unit ball---our algorithms use O(d2pln1ϵ) bits of memory, and make O((Cdpln1ϵ)p) oracle calls. The family is parametrized by p∈[d] and provides an oracle-complexity/memory trade-off in the sub-polynomial regime ln1ϵ≫lnd. While several works gave lower-bound trade-offs (impossibility results)---we explicit here their dependence with ln1ϵ, 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−Ω(d), our algorithm with p=d achieves the information-theoretic optimal memory usage and improves the oracle-complexity of gradient descent.