The Error Probability of Random Fourier Features is Dimensionality Independent

Jean Honorio, Yu-Jun Li

We show that the error probability of reconstructing kernel matrices from Random Fourier Features for the Gaussian kernel function is at most $\mathcal{O}(R^{2/3}\exp (-D))$, where…