The ${\ell }_p$-Subspace Sketch Problem in Small Dimensions with Applications to Support Vector Machines

Abstract

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,\hat{I}\mu )$ so that, for any query vector $x\in {\mathbb{R}}^d$, we can output a number in $(1\pm \hat{I}\mu )\Vert Ax{\Vert }_p^p$ given only $Q(A,\hat{I}\mu )$. This problem is known to require $\tilde{\hat{I}}\text{c◯}(d\hat{I}{\mu }^{-2})$ bits of memory for $d=\hat{I}\text{c◯}(\log (1/\hat{I}\mu ))$. However, for $d=o(\log (1/\hat{I}\mu ))$, 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 $\hat{I}\text{c◯}(\hat{I}{\mu }^{-2(d-1)/(d+2p)})$ bits and $\tilde{O}(\hat{I}{\mu }^{-2(d-1)/(d+2p)})$ words. This shows that one can beat the $\hat{I}\text{c◯}(\hat{I}{\mu }^{-2})$ lower bound, which holds for $d=\hat{I}\text{c◯}(\log (1/\hat{I}\mu ))$, for any constant $d$. We also show how to implement the upper bound in a single pass stream, with an additional multiplicative $\mathrm{poly}(\log \log n)$ factor and an additive $\mathrm{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{\hat{I}}˜(\hat{I}{\mu }^{-2d/(d+3)})$ for every constant $d$. This is a near-quadratic improvement over the $\hat{I}\text{c◯}(\hat{I}{\mu }^{-(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.

Corrected the citation for Lemma 3.3 and adjusted the constants in the proof accordingly