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 o(1) , any deterministic algorithm either uses d 1+δ bits of memory or must make at least 1/(d 0.01δ ǫ 2 1-δ 1+1.01δ -o(1) ) oracle queries, for any δ ∈ [0, 1]. Additionally, we show that randomized algorithms either use d 1+δ memory or make at least 1/(d 2δ ǫ 2(1-4δ)-o(1) ) queries for any δ ∈ [0, 1 4 ]. Because gradient descent only uses linear memory O(d ln 1/ǫ) but makes Ω(1/ǫ 2 ) 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 2 ln 1/ǫ) memory, cutting plane methods only require O(d ln 1/ǫ) queries.

1 ω < 2.373 denotes the exponent of matrix multiplication 1 of Vaidya's method and showed that cutting planes can be implemented with O(d 3 ln 1/ǫ) time complexity.

In practice, however, cutting planes are seldom used for large-dimensional applications and are rather viewed as impractical. While they achieve the optimal oracle complexity, these typically require storing all previous oracle responses, or at the very least, a summary matrix that uses Ω(d 2 ln 1/ǫ) bits of memory and needs to be updated at each iteration (amortized Ω(d 2 ) runtime per iteration). Instead, gradient-descent-based methods are often preferred for their practicality. These only keep in memory a few vectors, hence use only O(d ln 1/ǫ) bits and O(d ln 1/ǫ) runtime per iteration, but require O(1/ǫ 2 ) oracle queries which is largely suboptimal for ǫ ≪ 1/ √ d. These observations, as well as other practical implementation concerns, motivated the study of tradeoffs between the oracle complexity and other resources such as memory usage [7