Research map / Learning theory and algorithms / Kernels and regression theory
Random feature approximation
Approximate kernels with random Fourier and orthogonal features, with error bounds.
36 accepted papers at ICML, NeurIPS, ICLR, CVPR and AAAI (2016–2026) · an approach in Kernels and regression theory, keyword cluster “kernels · hilbert · reproducing”
State History Tried Baselines Preprints Who Export
Where it stands
Not enough benchmark data Fewer than four papers report the same benchmark, so there is no record to follow.
7 papers in 2023–24 and 6 in 2025–26 (at ICML, NeurIPS, ICLR, CVPR and AAAI); its share of the topic shrank, from 2.8% to 2.4%.
Open questions the data points to
- Papers report FAVOR+ on GLUE Dev CoLA (MCC) anywhere from 53.17 to 58.85: comparisons against it depend on whose number you take.
How this is decided
A benchmark is tracked when at least four papers of this approach report their own method on the same dataset and metric in at least two different years. Its record is the best number reported up to 2024 compared with the best reported in 2025–26: still improving means at least 1% better, flat means at most 0.2% better with at least two papers from 2025–26 trying. Numbers on a different scale from the rest (a fraction among percentages) and far outliers are left out. Results come from different papers with different setups, so they are signals, not head-to-head comparisons. The share of papers is counted at ICML, NeurIPS, ICLR, CVPR and AAAI.
How it got here
Most cited paper of each year
- 2016 · Orthogonal Random Features (NeurIPS 2016 · 93 citations)
- 2017 · Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees (ICML 2017 · 82 citations)
- 2018 · Quadrature-based features for kernel approximation (NeurIPS 2018 · 30 citations)
- 2019 · Learning Adaptive Random Features (AAAI 2019 · 12 citations)
- 2020 · Random Fourier Features via Fast Surrogate Leverage Weighted Sampling (AAAI 2020 · 16 citations)
- 2021 · Quantization Algorithms for Random Fourier Features (ICML 2021 · 2 citations)
- 2022 · Chefs' Random Tables: Non-Trigonometric Random Features (NeurIPS 2022 · 2 citations)
- 2023 · Tanimoto Random Features for Scalable Molecular Machine Learning (NeurIPS 2023 · 2 citations)
- 2024 · Optimal Kernel Quantile Learning with Random Features (ICML 2024 · 0 citations)
- 2025 · Variance-Reducing Couplings for Random Features (ICLR 2025 · 0 citations)
- 2026 · Scalable Random Wavelet Features: Efficient Non-Stationary Kernel Approximation with Convergence Guarantees (ICLR 2026 · 0 citations)
Earliest papers here
- Orthogonal Random Features (NeurIPS 2016 · 93 citations)
- Learning Kernels with Random Features (NeurIPS 2016 · 62 citations)
- Random Features for Sparse Signal Classification (CVPR 2016 · 6 citations)
What has been tried
31 papers here report 279 measured changes (a component added, removed or swapped, compared with a baseline): helped 68%, no clear effect 16%, hurt 13%, mixed 3%. Papers mostly publish changes that helped, so "helped" is over-represented.
Ablations in recent papers
| What was changed | Measured on | Result | Effect | Paper |
|---|---|---|---|---|
| Use LFHSIC-M rather than LFHSIC-G (optimize per-dimension scales instead of global bandwidth) | ISA, higher-dimensional setting · test power | Helped | Efficiently Learning Significant Fourier Feature Pairs for Statistical Independence Testing (NeurIPS 2024 · 0 citations) |
Baseline numbers that disagree
The same baseline on the same benchmark and metric, reported more than 5% apart by different papers here. Training budgets, data splits and reimplementations differ, so state which number you compare with.
| Baseline | Benchmark | Metric | Reported | Papers |
|---|---|---|---|---|
| FAVOR+ | GLUE Dev CoLA | MCC | 53.17 – 58.85 | 2 papers, e.g. NeurIPS 2022 and NeurIPS 2023 |
Recent preprints
Loading recent arXiv preprints…
Who publishes on it
Institutions on the most papers of this approach since 2023 (of 13 papers; from OpenAlex and the papers' affiliations).
- University of Cambridge · 3 papers
- Google · 2 papers
- Waymo · 2 papers
- Columbia University · 2 papers
Use it
Download BibTeX of 29 key papersOpen the topic in the interactive map
Get alerts. Describe your idea in scime atlas and save it (free scime account): you get a weekly email when new preprints land close to it.
Related approaches
Same keyword cluster
- RKHS kernel methods (127 papers)
- Neural tangent kernel analysis (109 papers)
- Kernel regression under shift (89 papers)
- Kernel two-sample testing (30 papers)
Elsewhere in the topic
- Statistical perspectives on generalization (99 papers)
- Information-theoretic generalization bounds (94 papers)
- High-dimensional asymptotic generalization (82 papers)
- Generalization theory of deep networks (67 papers)
- Empirical generalization measures (61 papers)
- High-dimensional linear regression theory (61 papers)
- Kernel ridge regression analysis (57 papers)
- Double descent and overfitting (53 papers)
Benchmark numbers, ablations and baseline numbers are extracted by AI from each paper's full text and can be wrong; the paper is the authority. Data: results index of 2026-11-02, citation counts from OpenAlex (2026-10-09).