The ℓp-Subspace Sketch Problem in Small Dimensions with Applications to Support Vector Machines

In the ℓp-subspace sketch problem, we are given an n× d matrix A with n>d, and asked to build a small memory data structure Q(A,ε) so that, for any query vector x∈ℝd, we can output a number in (1±ε)|Ax|pp given only Q(A,ε). This problem is known to require tildeOmega(dε-2) bits of memory for d=Omega(log(1/ε)). However, for d=o(log(1/ε)), no data structure lower bounds were known. We resolve the memory required to solve the ℓp-subspace sketch problem for any constant d and integer p, showing that it is Omega(ε-2(d-1)/(d+2p)) bits and tildeO (ε-2(d-1)/(d+2p)) words. This shows that one can beat the Omega(ε-2) lower bound, which holds for d = Omega(log(1/ε)), for any constant d. We also show how to implement the upper bound in a single pass stream, with an additional multiplicative operatornamepoly(log log n) factor and an additive operatornamepoly(log n) cost in the memory. Our bounds can be applied to point queries for SVMs with additive error, yielding an optimal bound of tildeTheta(ε-2d/(d+3)) for every constant d. This is a near-quadratic improvement over the Omega(ε-(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.