Research map / Learning theory and algorithms / Kernels and regression theory
Variance-Reducing Couplings for Random Features
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Frames variance reduction for random features as optimal transport, proposing pairwise norm-coupled RFs for Fourier/Laplace features and sigma-coupled graph random walks via permutation-based matching, showing variance reduction does not always improve downstream performance.
Problem
Random features for kernel approximation converge slowly under i.i.d. sampling; existing variance reduction (QMC, orthogonal frequencies, antithetic termination) is suboptimal or ad hoc, and reducing pointwise kernel variance does not always translate into downstream gains.
Approach
Casts coupling of random frequencies as a multi-marginal optimal transport problem; solves it exactly for m=2 (negative monotone norm coupling), extends it to pairwise norm-coupled ensembles, and for graph random walks optimises length couplings via a permutation-density/bipartite matching approximation.
Key results
- On UCI RFF kernel estimation, orthogonal + PNC reduces RMSE to about 0.43-0.61 of i.i.d. (e.g. Abalone 0.433 vs 1.000).
- For Performers on ImageNet, positively coupled norms (maximising pointwise variance) raise test accuracy from 0.625 to 0.633, while PNC gives 0.620.
- Sigma-coupled GRFs often substantially outperform antithetic termination and yield better graph GP predictions, sometimes by a factor above 2.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add pairwise negative monotone coupling of orthogonal frequency norms | RFF · UCI Concrete, Abalone, CPU, Power, Airfoil, Boston | normalized RMSE: Concrete: 0.627 ± 0.019 -> 0.563 ± 0.019; Abalone: 0.535 ± 0.023 -> 0.433 ± 0.019; CPU: 0.617 ± 0.070 -> 0.544 ± 0.071; | Helped |
| add pairwise negative monotone coupling and antiparallel features | RLF · UCI Concrete, Abalone, Power, Airfoil, Boston | normalized RMSE: Concrete: 0.418 ± 0.041 -> 0.367 ± 0.043; Abalone: 0.546 ± 0.026 -> 0.486 ± 0.027; Power: 0.527 ± 0.013 -> 0.438 ± 0.013 | Helped |
| add pairwise negative monotone coupling and antiparallel features | RLF · UCI CPU | normalized RMSE: 0.614 ± 0.098 -> 0.618 ± 0.119 | Hurt |
| use positive monotone coupling of frequency norms | Performer · ImageNet | test accuracy: +0.8% | Helped |
| use pairwise negative monotone coupling of frequency norms | Performer · ImageNet | test accuracy: 0.625 ± 0.003 -> 0.620 ± 0.003 | No clear effect |
| use pairwise negative monotone coupling of orthogonal frequency norms | graph random features · Cora Gram matrix approximation | relative Frobenius norm error | Helped |
| couple random-walk lengths with an optimized quantile matching (σ-coupling) | graph random features · real-world graphs; graph-based GP mesh interpolation and San Jose traffic | test RMSE and posterior KL divergence | Helped |
Surprising findings
- Maximising pointwise kernel estimator variance via positive monotone norm coupling improves Performer attention accuracy after row normalisation.
- Variance reduction of pointwise RFF/RLF kernel estimates does not improve downstream sparse spectrum GP performance.
Limitations
- RFF optimality of negative monotone coupling is proven only for sufficiently small z.
- Multi-marginal OT for m>2 is unsolved; copula learning shows PNC may be near optimal but no analytic proof.
- Pointwise variance reduction does not guarantee downstream gains (e.g. sparse spectrum GPs, PNC on Performers).
Experimental setup
Datasets: UCI datasets (Concrete, Abalone, CPU, Power, Airfoil, Boston) cora mesh graphs (up to 8700 nodes) San Jose traffic graph (1016 nodes) ImageNet Erdos-Renyi graph (N=100)
Benchmarks: UCI kernel approximation RMSE ImageNet Performer test accuracy cora Gram matrix error graph GP test RMSE and KL divergence traffic interpolation
Metrics: RMSE relative Frobenius norm error test accuracy test RMSE KL divergence
Baselines: i.i.d. random features Halton sequences orthogonal random features antithetic termination Performer (orthogonal)
Builds on: orthogonal random features antithetic termination graph random features Performers Halton sequences
Closest papers by meaning
- Simplex Random Features (ICML 2023 · similarity 0.87)
- Implicit Regularization of Random Feature Models (ICML 2020 · similarity 0.86)
- Manifold Random Features (NeurIPS 2026 · similarity 0.86)
- Towards Theoretical Understanding of Learning Large-scale Dependent Data via Random Features (ICML 2024 · similarity 0.85)
- Optimal Kernel Quantile Learning with Random Features (ICML 2024 · similarity 0.85)
- Leveraging Data Symmetries to Select an Optimal Subset of Training Data under Label Noise (NeurIPS 2026 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.