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

Jonas Wacker, Ruben Ohana, Maurizio Filippone

Research output: Contribution to conferencePaperpeer-review

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(3p) 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(2p) 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.

Original languageEnglish (US)
Pages5181-5212
Number of pages32
StatePublished - 2023
Event26th International Conference on Artificial Intelligence and Statistics, AISTATS 2023 - Valencia, Spain
Duration: Apr 25 2023Apr 27 2023

Conference

Conference26th International Conference on Artificial Intelligence and Statistics, AISTATS 2023
Country/TerritorySpain
CityValencia
Period04/25/2304/27/23

ASJC Scopus subject areas

  • Artificial Intelligence
  • Software
  • Control and Systems Engineering
  • Statistics and Probability

Fingerprint

Dive into the research topics of 'Complex-to-Real Sketches for Tensor Products with Applications to the Polynomial Kernel'. Together they form a unique fingerprint.

Cite this