arXiv (Cornell University) · 2020 · 40 citations · 45 references
ComputingComputer ScienceData MiningMachine LearningStatistical LearningDimensionality ReductionFourier AnalysisKernel MethodsPattern RecognitionRepresentation LearningData DistributionFourier FeaturesFourier Transform FeaturesKernel LearningRandom Fourier FeaturesRandom Matrix TheoryStatistical Learning Theory
This article characterizes the exact asymptotics of random Fourier feature (RFF) regression, in the realistic setting where the number of data samples $n$, their dimension $p$, and the dimension of feature space $N$ are all large and comparable. In this regime, the random RFF Gram matrix no longer converges to the well-known limiting Gaussian kernel matrix (as it does when $N \to \infty$ alone), but it still has a tractable behavior that is captured by our analysis. This analysis also provides accurate estimates of training and test regression errors for large $n,p,N$. Based on these estimates, a precise characterization of two qualitatively different phases of learning, including the phase transition between them, is provided; and the corresponding double descent test error curve is derived from this phase transition behavior. These results do not depend on strong assumptions on the data distribution, and they perfectly match empirical results on real-world data sets.
45
Gradient-based learning applied to document recognition
Yann LeCun, Léon Bottou, Yoshua Bengio et al. · Proceedings of the IEEE · 1998 · 58.2K citations · Full text
Yuhai Wu, Vladimir Vapnik · Technometrics · 1999 · 27K citations
Random Features for Large-Scale Kernel Machines
Ali Rahimi, Benjamin Recht · 2007 · 2.7K citations