Gradient Descent is Pareto-Optimal in the Oracle Complexity and Memory Tradeoff for Feasibility Problems
Not on the map. Why?
Abstract (arXiv)
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^-do(1), any deterministic algorithm either uses d1+δ bits of memory or must make at least 1/(d0.01δ ε^2frac1-δ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,frac14]. Because gradient descent only uses linear memory mathcal O(dln 1/ε) but makes Omega(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 mathcal O(d2 ln1/ε) memory, cutting plane methods only require mathcal O(dln 1/ε) queries.
Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 29 of its 66 references that are in the map. First posted on arXiv 10 Apr 2024.
Builds on
29 of 66 references.
References · 29
- 2017Gradient Sparsification for Communication-Efficient Distributed Optimizationcited by 201
- 2013Communication Efficient Distributed Optimization using an Approximate Newton-type Methodcited by 132
- 2020When is Memorization of Irrelevant Training Data Necessary for High-Accuracy Learning?cited by 104
- 2015Newton Sketch: A Linear-time Optimization Algorithm with Linear-Quadratic Convergencecited by 72
- 2016CoCoA: A General Framework for Communication-Efficient Distributed Optimizationcited by 69
- 2020An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games and its Applicationscited by 57
- 2015A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimizationcited by 50
- 2016AIDE: Fast and Communication Efficient Distributed Optimizationcited by 43
- 2017Communication-Efficient Algorithms for Decentralized and Stochastic Optimizationcited by 43
- 2016Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learningcited by 33
- 2019Memory-Sample Tradeoffs for Linear Regression with Small Errorcited by 22
- 2019Complexity of Highly Parallel Non-Smooth Convex Optimizationcited by 22
17 more
- 2013Memory Limited, Streaming PCAcited by 21
- 2022Memory Bounds for the Experts Problemcited by 20
- 2017Extractor-Based Time-Space Lower Bounds for Learningcited by 19
- 2023Acceleration by Stepsize Hedging I: Multi-Step Descent and the Silver Stepsize Schedulecited by 19
- 2022Branch-and-Bound Performance Estimation Programming: A Unified Methodology for Constructing Optimal Optimization Methodscited by 16
- 2022Online Prediction in Sub-linear Spacecited by 16
- 2023Near Optimal Memory-Regret Tradeoff for Online Learningcited by 15
- 2022Efficient Convex Optimization Requires Superlinear Memorycited by 14
- 2017Memory and Communication Efficient Distributed Stochastic Optimization with Minibatch-Proxcited by 12
- 2018Parallelization does not Accelerate Convex Optimization: Adaptivity Lower Bounds for Non-smooth Convex Minimizationcited by 12
- 2022Strong Memory Lower Bounds for Learning Natural Modelscited by 11
- 2021Memory-Sample Lower Bounds for Learning Parity with Noisecited by 10
- 2019Open Problem: The Oracle Complexity of Convex Optimization with Limited Memorycited by 8
- 2023Quadratic Memory is Necessary for Optimal Query Complexity in Convex Optimization: Center-of-Mass is Pareto-Optimalcited by 5
- 2023Memory-Query Tradeoffs for Randomized Convex Optimizationcited by 4
- 2023Memory-Constrained Algorithms for Convex Optimization via Recursive Cutting-Planescited by 3
- 2013Singular values of Gaussian matrices and permanent estimatorscited by 2
Built on by
Citing papers per year: 2026: 1.
1 paper.