Complex-to-real random features for polynomial Kernels

Wacker, Jonas; Ohana, Ruben; Filippone, Maurizio
Submitted to ArXiV, 10 February 2022

Kernel methods are ubiquitous in statistical modeling due to their theoretical guarantees as well as their competitive empirical performance. Polynomial kernels are of particular importance as their feature maps model the interactions between the dimensions of the input data. However, the construction time of explicit feature maps scales exponentially with the polynomial degree and a naive application of the kernel trick does not scale to large datasets. In this work, we propose Complexto-Real (CtR) random features for polynomial kernels that leverage intermediate complex random projections and can yield kernel estimates with much lower variances than their real-valued analogs. The resulting features are real-valued, simple to construct and have the following advantages over the state-of-the-art: 1) shorter construction times, 2) lower kernel approximation errors for commonly used degrees, 3) they enable us to obtain a closed-form expression for their variance.


Type:
Conférence
Date:
2022-02-10
Department:
Data Science
Eurecom Ref:
6813
Copyright:
© EURECOM. Personal use of this material is permitted. The definitive version of this paper was published in Submitted to ArXiV, 10 February 2022 and is available at :

PERMALINK : https://www.eurecom.fr/publication/6813