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 ∈ R d , we can output a number in (1 ± ε) Ax p p given only Q(A, ε). This problem is known to require Ω(dε -2 ) bits of memory for d = Ω(log(1/ε)). However, for d = o(log(1/ε)), no data structure lower bounds were known. Small constant values of d are particularly important for estimating point queries for support vector machines (SVMs) in a stream (Andoni et al. 2020), where only tight bounds for d = 1 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 Ω ε -2(d-1) d+2p bits and O ε -2(d-1) d+2p words, where the O(•) notation hides poly(log(1/ε)) factors. This shows that one can beat the Ω(ε -2 ) lower bound, which holds for d = Ω(log(1/ε)), for any constant d. Further, we show how to implement the upper bound in a single pass stream, with an additional multiplicative poly(log log n) factor and an additive poly(log n) cost in the memory. Our bounds extend to loss functions other than the ℓ p -norm, and notably they apply to point queries for SVMs with additive error, where we show an optimal bound of Θ ε -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. Further, previous upper bounds for SVM point query were noticeably lacking: for d = 1 the bound was O(ε -1/2 ) and for d = 2 the bound was O(ε -4/5 ), but all existing techniques failed to give any upper bound better than O(ε -2 ) for any other value of d. Our techniques, which rely on a novel connection to low dimensional techniques from geometric functional analysis, completely close this gap.