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
]
Abstract:
We revisit the classic randomized sketch of a tensor product of q vectors xi∈Rn. The i-th coordinate (Sx)i of the sketch is equal to
∏qj=1⟨ui,j,xj⟩/√m, where ui,j are independent random sign vectors. Kar and Karnick (JMLR, 2012) show that
if the sketching dimension m=Ω(ϵ−2C2Ωlog(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 C2Ω 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=Ω(\eps−2log(1/(δ))+\eps−1logq(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 m⋅∑qi=1nnz(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