Complex-to-Real Sketches for Tensor Products with Applications to the Polynomial Kernel

Jonas Wacker, Ruben Ohana, Maurizio Filippone
Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, PMLR 206:5181-5212, 2023.

Abstract

Randomized sketches of a tensor product of $p$ vectors follow a tradeoff between statistical efficiency and computational acceleration. Commonly used approaches avoid computing the high-dimensional tensor product explicitly, resulting in a suboptimal dependence of $O(3^p)$ in the embedding dimension. We propose a simple Complex-to-Real (CtR) modification of well-known sketches that replaces real random projections by complex ones, incurring a lower $O(2^p)$ factor in the embedding dimension. The output of our sketches is real-valued, which renders their downstream use straightforward. In particular, we apply our sketches to $p$-fold self-tensored inputs corresponding to the feature maps of the polynomial kernel. We show that our method achieves state-of-the-art performance in terms of accuracy and speed compared to other randomized approximations from the literature.

Cite this Paper

BibTeX
@InProceedings{pmlr-v206-wacker23a, title = {Complex-to-Real Sketches for Tensor Products with Applications to the Polynomial Kernel}, author = {Wacker, Jonas and Ohana, Ruben and Filippone, Maurizio}, booktitle = {Proceedings of The 26th International Conference on Artificial Intelligence and Statistics}, pages = {5181--5212}, year = {2023}, editor = {Ruiz, Francisco and Dy, Jennifer and van de Meent, Jan-Willem}, volume = {206}, series = {Proceedings of Machine Learning Research}, month = {25--27 Apr}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v206/wacker23a/wacker23a.pdf}, url = {https://proceedings.mlr.press/v206/wacker23a.html}, abstract = {Randomized sketches of a tensor product of $p$ vectors follow a tradeoff between statistical efficiency and computational acceleration. Commonly used approaches avoid computing the high-dimensional tensor product explicitly, resulting in a suboptimal dependence of $O(3^p)$ in the embedding dimension. We propose a simple Complex-to-Real (CtR) modification of well-known sketches that replaces real random projections by complex ones, incurring a lower $O(2^p)$ factor in the embedding dimension. The output of our sketches is real-valued, which renders their downstream use straightforward. In particular, we apply our sketches to $p$-fold self-tensored inputs corresponding to the feature maps of the polynomial kernel. We show that our method achieves state-of-the-art performance in terms of accuracy and speed compared to other randomized approximations from the literature.} }
Endnote
%0 Conference Paper %T Complex-to-Real Sketches for Tensor Products with Applications to the Polynomial Kernel %A Jonas Wacker %A Ruben Ohana %A Maurizio Filippone %B Proceedings of The 26th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2023 %E Francisco Ruiz %E Jennifer Dy %E Jan-Willem van de Meent %F pmlr-v206-wacker23a %I PMLR %P 5181--5212 %U https://proceedings.mlr.press/v206/wacker23a.html %V 206 %X Randomized sketches of a tensor product of $p$ vectors follow a tradeoff between statistical efficiency and computational acceleration. Commonly used approaches avoid computing the high-dimensional tensor product explicitly, resulting in a suboptimal dependence of $O(3^p)$ in the embedding dimension. We propose a simple Complex-to-Real (CtR) modification of well-known sketches that replaces real random projections by complex ones, incurring a lower $O(2^p)$ factor in the embedding dimension. The output of our sketches is real-valued, which renders their downstream use straightforward. In particular, we apply our sketches to $p$-fold self-tensored inputs corresponding to the feature maps of the polynomial kernel. We show that our method achieves state-of-the-art performance in terms of accuracy and speed compared to other randomized approximations from the literature.
APA
Wacker, J., Ohana, R. & Filippone, M.. (2023). Complex-to-Real Sketches for Tensor Products with Applications to the Polynomial Kernel. Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 206:5181-5212 Available from https://proceedings.mlr.press/v206/wacker23a.html.

Related Material