A Random Matrix Analysis of Random Fourier Features: Beyond the Gaussian\n Kernel, a Precise Phase Transition, and the Corresponding Double Descent

Abstract

This article characterizes the exact asymptotics of random Fourier feature\n(RFF) regression, in the realistic setting where the number of data samples\n$n$, their dimension $p$, and the dimension of feature space $N$ are all large\nand comparable. In this regime, the random RFF Gram matrix no longer converges\nto the well-known limiting Gaussian kernel matrix (as it does when $N \\to\n\\infty$ alone), but it still has a tractable behavior that is captured by our\nanalysis. This analysis also provides accurate estimates of training and test\nregression errors for large $n,p,N$. Based on these estimates, a precise\ncharacterization of two qualitatively different phases of learning, including\nthe phase transition between them, is provided; and the corresponding double\ndescent test error curve is derived from this phase transition behavior. These\nresults do not depend on strong assumptions on the data distribution, and they\nperfectly match empirical results on real-world data sets.\n