## Background Random Fourier features (Rahimi & Recht, 2007) approximate a shift-invariant kernel k(x,y) by an inner product of D-dimensional random cosine features. The uniform approximation guarantee is O(1/sqrt(D)). Practitioners consistently observe that downstream prediction quality saturates much earlier than this bound suggests, and later theory (e.g. Rudi & Rosasco, 2017) hints that far fewer features suffice for optimal learning rates. This project measures the *empirical* decay exponent directly. ## Hypothesis For kernel ridge regression (KRR) with an RBF kernel on smooth target functions, the excess prediction risk of the RFF approximation relative to exact KRR decays as O(D^-a) with a close to 1 (a >= 0.8), i.e. strictly faster than the a = 0.5 uniform bound. For rough (low-smoothness) targets, the exponent degrades toward 0.5. ## Experimental plan 1. Synthetic regression targets on [0,1]^d (d in {1, 5}) with controlled smoothness: (a) a band-limited…Read more
Read less
## Background Random Fourier features (Rahimi & Recht, 2007) approximate a shift-invariant kernel k(x,y) by an inner product of D-dimensional random cosine features. The uniform approximation guarantee is O(1/sqrt(D)). Practitioners consistently observe that downstream prediction quality saturates much earlier than this bound suggests, and later theory (e.g. Rudi & Rosasco, 2017) hints that far fewer features suffice for optimal learning rates. This project measures the *empirical* decay exponent directly. ## Hypothesis For kernel ridge regression (KRR) with an RBF kernel on smooth target functions, the excess prediction risk of the RFF approximation relative to exact KRR decays as O(D^-a) with a close to 1 (a >= 0.8), i.e. strictly faster than the a = 0.5 uniform bound. For rough (low-smoothness) targets, the exponent degrades toward 0.5. ## Experimental plan 1. Synthetic regression targets on [0,1]^d (d in {1, 5}) with controlled smoothness: (a) a band-limited smooth function (sum of low-frequency sinusoids), (b) a Sobolev-rough function (random Fourier series with slowly decaying coefficients), (c) a non-smooth piecewise function. 2. Fixed sample size n = 2000 train / 2000 test, Gaussian noise sigma = 0.1. Exact-kernel KRR (RBF, ridge lambda tuned once by CV on the exact model) as the reference predictor. 3. Sweep D in {16, 32, 64, 128, 256, 512, 1024, 2048}; for each D average excess risk over >= 20 random feature draws. Excess risk = MSE(RFF model) - MSE(exact model) on the test set (clipped below at 0 before averaging is NOT allowed; report raw differences and their CIs). 4. Fit the log-log slope of mean excess risk vs D over the pre-asymptotic-flat region; report slope with bootstrap 95% CI per target. 5. One real dataset: California Housing (scikit-learn built-in, subsampled to n = 2000) with the same protocol. ## Success criteria / evaluation - Primary: for the band-limited smooth target, the fitted decay exponent a satisfies a >= 0.8 with the 95% CI excluding 0.5. - Secondary: monotone relationship between target smoothness and fitted exponent across the three synthetic targets. - Report negative results honestly if the data contradicts the hypothesis; a clean refutation is an acceptable outcome. ## Constraints - CPU-only, numpy + scikit-learn; no GPU, no deep learning, no external data downloads beyond scikit-learn built-ins. - Each experiment cell must run in under 10 minutes; the full sweep under 2 hours. - All randomness seeded; the paper must include the exact seeds and a reproduction script. ## Deliverables - Paper with the measured exponents (table + log-log figures with CIs), methods, and an honest limitations section (finite-D crossover, lambda coupling, noise floor). - Code producing every figure from a single entry point.