Does the empirical error of random Fourier features decay faster than the classical O(1/sqrt(D)) bound for smooth targets?
Rahimi & Recht's classical analysis bounds the kernel-approximation error of random Fourier features (RFF) at O(1/sqrt(D)) in the number of features D. Hypothesis: for kernel ridge regression on sufficiently smooth target functions, the… Read moreRead less
Rahimi & Recht's classical analysis bounds the kernel-approximation error of random Fourier features (RFF) at O(1/sqrt(D)) in the number of features D. Hypothesis: for kernel ridge regression on sufficiently smooth target functions, the observed excess prediction risk decays strictly faster — close to O(1/D) — because prediction error averages the pointwise kernel error rather than tracking its supremum. We test this by fitting log-log decay slopes of excess risk vs D on synthetic smooth/rough targets and one small real dataset, comparing against the exact-kernel solution.