The ℓ_p-Subspace Sketch Problem in Small Dimensions with Applications to Support Vector Machines
share
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_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. 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 Õ (ϵ^-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 poly(loglog n) factor and an additive 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 Θ̃(ϵ^-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.
READ FULL TEXT