Skip to yearly menu bar Skip to main content


Poster

Tight Dimensionality Reduction for Sketching Low Degree Polynomial Kernels

Michela Meister · Tamas Sarlos · David Woodruff

East Exhibition Hall B, C #10

Keywords: [ Algorithms ] [ Kernel Methods ]


Abstract: We revisit the classic randomized sketch of a tensor product of q vectors xiRn. The i-th coordinate (Sx)i of the sketch is equal to j=1qui,j,xj/m, where ui,j are independent random sign vectors. Kar and Karnick (JMLR, 2012) show that if the sketching dimension m=Ω(ϵ2CΩ2log(1/δ)), where CΩ is a certain property of the point set Ω one wants to sketch, then with probability 1δ, Sx2=(1±ϵ)x2 for all xΩ. However, in their analysis CΩ2 can be as large as Θ(n2q), even for a set Ω of O(1) vectors x. We give a new analysis of this sketch, providing nearly optimal bounds. Namely, we show an upper bound of m=Θ(ϵ2log(n/δ)+ϵ1logq(n/δ)), which by composing with CountSketch, can be improved to Θ(ϵ2log(1/(δϵ))+ϵ1logq(1/(δϵ)). For the important case of q=2 and δ=1/\poly(n), this shows that m=Θ(ϵ2log(n)+ϵ1log2(n)), demonstrating that the ϵ2 and log2(n) terms do not multiply each other. We also show a nearly matching lower bound of m=Ω(\eps2log(1/(δ))+\eps1logq(1/(δ))). In a number of applications, one has |Ω|=\poly(n) and in this case our bounds are optimal up to a constant factor. This is the first high probability sketch for tensor products that has optimal sketch size and can be implemented in mi=1qnnz(xi) time, where nnz(xi) is the number of non-zero entries of xi. Lastly, we empirically compare our sketch to other sketches for tensor products, and give a novel application to compressing neural networks.

Live content is unavailable. Log in and register to view live content