Gradient Descent is Pareto-Optimal in the Oracle Complexity and Memory Tradeoff for Feasibility Problems

In this paper we provide oracle complexity lower bounds for finding a point in a given set using a memory-constrained algorithm that has access to a separation oracle. We assume that the set is contained within the unit d-dimensional ball and contains a ball of known radius ε>0. This setup is commonly referred to as the feasibility problem. We show that to solve feasibility problems with accuracy ε ≥ e^-dᵒ⁽¹⁾, any deterministic algorithm either uses d1+δ bits of memory or must make at least 1/(d0.01δε21-δ/1+1.01 δ-o(1)) oracle queries, for any δ∈[0,1]. Additionally, we show that randomized algorithms either use d1+δ memory or make at least 1/(d2δ ε2(1-4δ)-o(1)) queries for any δ∈[0,1/4]. Because gradient descent only uses linear memory O(dln 1/ε) but makes Ω(1/ε²) queries, our results imply that it is Pareto-optimal in the oracle complexity/memory tradeoff. Further, our results show that the oracle complexity for deterministic algorithms is always polynomial in 1/ε if the algorithm has less than quadratic memory in d. This reveals a sharp phase transition since with quadratic O(d² ln1/ε) memory, cutting plane methods only require O(dln 1/ε) queries.