Abstract
Random Fourier features provide a way to tackle large-scale machine learningproblems with kernel methods. Their slow Monte Carlo convergence rate hasmotivated the research of deterministic Fourier features whose approximationerror can decrease exponentially in the number of basis functions. However, dueto their tensor product extension to multiple dimensions, these methods sufferheavily from the curse of dimensionality, limiting their applicability to one,two or three-dimensional scenarios. In our approach we overcome said curse ofdimensionality by exploiting the tensor product structure of deterministicFourier features, which enables us to represent the model parameters as alow-rank tensor decomposition. We derive a monotonically converging blockcoordinate descent algorithm with linear complexity in both the sample size andthe dimensionality of the inputs for a regularized squared loss function,allowing to learn a parsimonious model in decomposed form using deterministicFourier features. We demonstrate by means of numerical experiments how ourlow-rank tensor approach obtains the same performance of the correspondingnonparametric model, consistently outperforming random Fourier features.