Tight Dimensionality Reduction for Sketching Low Degree Polynomial Kernels

Abstract

We revisit the classic randomized sketch of a tensor product of q vectors x_iR^n. The i-th coordinate (Sx)_i of the sketch is equal to _j = 1^q u^i, j, x^j / m, where u^i,j are independent random sign vectors. Kar and Karnick (JMLR, 2012) show that if the sketching dimension m = (^-2 C_^2 (1/)), where C_ is a certain property of the point set one wants to sketch, then with probability 1-, \|Sx\|_2 = (1 )\|x\|_2 for all x. However, in their analysis C_^2 can be as large as (n^2q), 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 = (^-2 (n/) + ^-1 ^q(n/) ), which by composing with CountSketch, can be improved to (^-2(1/( )) + ^-1 ^q (1/( )). For the important case of q = 2 and = 1/(n), this shows that m = (^-2 (n) + ^-1 ^2(n)), demonstrating that the ^-2 and ^2(n) terms do not multiply each other. We also show a nearly matching lower bound of m = (^-2 (1/()) + ^-1 ^q(1/())). In a number of applications, one has || = (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 m _i=1^q nnz(x_i) time, where nnz(x_i) is the number of non-zero entries of x_i. Lastly, we empirically compare our sketch to other sketches for tensor products, and give a novel application to compressing neural networks.

Tasks

Reproductions