Revisiting random Fourier features based on PAC-Bayesian learning via interest points.

Summary This paper summarizes and extends our recent work published at AISTATS 2019, in which we revisited the Random Fourier Features (RFF) method of Rahimi et al. (2007) through PAC-Bayesian theory. Although the main objective of RFFs is to approximate a kernel function, here we consider the Fourier transform as a distribution \emph{a priori} on a set of trigonometric assumptions. This naturally suggests learning an a posteriori distribution on this set of assumptions. We derive bounds in generalizations that are optimized by learning a pseudo-posterior distribution obtained from a closed form expression. From this study, we propose two learning strategies based on points of interest: (i) the two-step procedure proposed in our previous paper, where a compact representation of the data is learned and then used to learn a linear model, (ii) a new procedure, where the representation and the model are learned in a single step following a Boosting type approach