2023/06/16 by Blanchard, Moïse, Zhang, Junhui, Jaillet, Patrick · 1 citation
#Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC)
paper · doi:10.48550/arxiv.2306.10096
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((d2)/(p)ln \frac1ε) bits of memory, and make \mathcal O((C(d)/(p)ln \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 ln\frac1ε≫ln d. While several works gave lower-bound trade-offs (impossibility results) -- we explicit here their dependence with ln\frac1ε, 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.