The $\ell_p$-Subspace Sketch Problem in Small Dimensions with Applications to Support Vector Machines
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2022
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916127118983168 |
|---|---|
| author | Li, Yi Lin, Honghao Woodruff, David P. |
| author_facet | Li, Yi Lin, Honghao Woodruff, David P. |
| contents | In the $\ell_p$-subspace sketch problem, we are given an $n\times d$ matrix $A$ with $n>d$, and asked to build a small memory data structure $Q(A,ε)$ so that, for any query vector $x\in\mathbb{R}^d$, we can output a number in $(1\pmε)\|Ax\|_p^p$ given only $Q(A,ε)$. This problem is known to require $\tildeΩ(dε^{-2})$ bits of memory for $d=Ω(\log(1/ε))$. However, for $d=o(\log(1/ε))$, no data structure lower bounds were known.
We resolve the memory required to solve the $\ell_p$-subspace sketch problem for any constant $d$ and integer $p$, showing that it is $Ω(ε^{-2(d-1)/(d+2p)})$ bits and $\tilde{O} (ε^{-2(d-1)/(d+2p)})$ words. This shows that one can beat the $Ω(ε^{-2})$ lower bound, which holds for $d = Ω(\log(1/ε))$, for any constant $d$. We also show how to implement the upper bound in a single pass stream, with an additional multiplicative $\operatorname{poly}(\log \log n)$ factor and an additive $\operatorname{poly}(\log n)$ cost in the memory. Our bounds can be applied to point queries for SVMs with additive error, yielding an optimal bound of $\tildeΘ(ε^{-2d/(d+3)})$ for every constant $d$. This is a near-quadratic improvement over the $Ω(ε^{-(d+1)/(d+3)})$ lower bound of (Andoni et al. 2020). Our techniques rely on a novel connection to low dimensional techniques from geometric functional analysis. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2211_07132 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | The $\ell_p$-Subspace Sketch Problem in Small Dimensions with Applications to Support Vector Machines Li, Yi Lin, Honghao Woodruff, David P. Data Structures and Algorithms In the $\ell_p$-subspace sketch problem, we are given an $n\times d$ matrix $A$ with $n>d$, and asked to build a small memory data structure $Q(A,ε)$ so that, for any query vector $x\in\mathbb{R}^d$, we can output a number in $(1\pmε)\|Ax\|_p^p$ given only $Q(A,ε)$. This problem is known to require $\tildeΩ(dε^{-2})$ bits of memory for $d=Ω(\log(1/ε))$. However, for $d=o(\log(1/ε))$, no data structure lower bounds were known. We resolve the memory required to solve the $\ell_p$-subspace sketch problem for any constant $d$ and integer $p$, showing that it is $Ω(ε^{-2(d-1)/(d+2p)})$ bits and $\tilde{O} (ε^{-2(d-1)/(d+2p)})$ words. This shows that one can beat the $Ω(ε^{-2})$ lower bound, which holds for $d = Ω(\log(1/ε))$, for any constant $d$. We also show how to implement the upper bound in a single pass stream, with an additional multiplicative $\operatorname{poly}(\log \log n)$ factor and an additive $\operatorname{poly}(\log n)$ cost in the memory. Our bounds can be applied to point queries for SVMs with additive error, yielding an optimal bound of $\tildeΘ(ε^{-2d/(d+3)})$ for every constant $d$. This is a near-quadratic improvement over the $Ω(ε^{-(d+1)/(d+3)})$ lower bound of (Andoni et al. 2020). Our techniques rely on a novel connection to low dimensional techniques from geometric functional analysis. |
| title | The $\ell_p$-Subspace Sketch Problem in Small Dimensions with Applications to Support Vector Machines |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2211.07132 |