Gradient Descent is Pareto-Optimal in the Oracle Complexity and Memory Tradeoff for Feasibility Problems
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909165275840512 |
|---|---|
| author | Blanchard, Moise |
| author_facet | Blanchard, Moise |
| contents | 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 $ε\geq e^{-d^{o(1)}}$, any deterministic algorithm either uses $d^{1+δ}$ bits of memory or must make at least $1/(d^{0.01δ}ε^{2\frac{1-δ}{1+1.01 δ}-o(1)})$ oracle queries, for any $δ\in[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 $δ\in[0,\frac{1}{4}]$. Because gradient descent only uses linear memory $\mathcal 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 $\mathcal O(d^2 \ln1/ε)$ memory, cutting plane methods only require $\mathcal O(d\ln 1/ε)$ queries. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_06720 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Gradient Descent is Pareto-Optimal in the Oracle Complexity and Memory Tradeoff for Feasibility Problems Blanchard, Moise Optimization and Control Computational Complexity Data Structures and Algorithms Machine Learning 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 $ε\geq e^{-d^{o(1)}}$, any deterministic algorithm either uses $d^{1+δ}$ bits of memory or must make at least $1/(d^{0.01δ}ε^{2\frac{1-δ}{1+1.01 δ}-o(1)})$ oracle queries, for any $δ\in[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 $δ\in[0,\frac{1}{4}]$. Because gradient descent only uses linear memory $\mathcal 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 $\mathcal O(d^2 \ln1/ε)$ memory, cutting plane methods only require $\mathcal O(d\ln 1/ε)$ queries. |
| title | Gradient Descent is Pareto-Optimal in the Oracle Complexity and Memory Tradeoff for Feasibility Problems |
| topic | Optimization and Control Computational Complexity Data Structures and Algorithms Machine Learning |
| url | https://arxiv.org/abs/2404.06720 |