# But How Does It Work in Theory? Linear SVM with Random Features

arXiv: https://arxiv.org/abs/1809.04481 · HTML: https://mlsanity.com/paper/1809.04481/

## Key facts

- Cited by 28 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Sep 2018.

## Built on by (most cited first, 28 of 28)

- [Learnable Fourier Features for Multi-Dimensional Spatial Positional Encoding](https://mlsanity.com/paper/2106.02795/) (2021)
- [Error Bounds for Learning with Vector-Valued Random Features](https://mlsanity.com/paper/2305.17170/) (2023)
- [Learning new physics efficiently with nonparametric methods](https://mlsanity.com/paper/2204.02317/) (2022)
- [Chefs' Random Tables: Non-Trigonometric Random Features](https://mlsanity.com/paper/2205.15317/) (2022)
- [Operator Learning Using Random Features: A Tool for Scientific Computing](https://mlsanity.com/paper/2408.06526/) (2024)
- [Learning with Density Matrices and Random Features](https://mlsanity.com/paper/2102.04394/) (2021)
- [On Learning the Transformer Kernel](https://mlsanity.com/paper/2110.08323/) (2021)
- [Random Fourier Signature Features](https://mlsanity.com/paper/2311.12214/) (2023)
- [Quantization Algorithms for Random Fourier Features](https://mlsanity.com/paper/2102.13079/) (2021)
- [Solving Partial Differential Equations with Random Feature Models](https://mlsanity.com/paper/2501.00288/) (2024)
- [Exponential Error Convergence in Data Classification with Optimized Random Features: Acceleration by Quantum Machine Learning](https://mlsanity.com/paper/2106.09028/) (2021)
- [FAVOR#: Sharp Attention Kernel Approximations via New Classes of Positive Random Features](https://mlsanity.com/paper/2302.00787/) (2023)
- [Optimal Kernel Quantile Learning with Random Features](https://mlsanity.com/paper/2408.13591/) (2024)
- [Random Feature Representation Boosting](https://mlsanity.com/paper/2501.18283/) (2025)
- [Tensor Sketch: Fast and Scalable Polynomial Kernel Approximation](https://mlsanity.com/paper/2505.08146/) (2025)
- [Computational Efficiency under Covariate Shift in Kernel Ridge Regression](https://mlsanity.com/paper/2505.14083/) (2025)
- [Sharp Analysis of Random Fourier Features in Classification](https://mlsanity.com/paper/2109.10623/) (2021)
- [On Average-Case Error Bounds for Kernel-Based Bayesian Quadrature](https://mlsanity.com/paper/2202.10615/) (2022)
- [RandNet-Parareal: a time-parallel PDE solver using Random Neural Networks](https://mlsanity.com/paper/2411.06225/) (2024)
- [On The Relative Error of Random Fourier Features for Preserving Kernel Distance](https://mlsanity.com/paper/2210.00244/) (2022)
- [Differentially Private Random Feature Model](https://mlsanity.com/paper/2412.04785/) (2024)
- [Error Estimation for Random Fourier Features](https://mlsanity.com/paper/2302.11174/) (2023)
- [Learning Expressive Random Feature Models via Parametrized Activations](https://mlsanity.com/paper/2411.19468/) (2024)
- [On the Generalization Properties of Learning the Random Feature Models with Learnable Activation Functions](https://mlsanity.com/paper/2510.15327/) (2025)
- [Manifold Random Features](https://mlsanity.com/paper/2602.03797/) (2026)
- [Snacks: a fast large-scale kernel SVM solver](https://mlsanity.com/paper/2304.07983/) (2023)
- [Kernel Approximation using Analog In-Memory Computing](https://mlsanity.com/paper/2411.03375/) (2024)
- [Improving TensorSketch Using Complex Random Variables](https://mlsanity.com/paper/2608.10523/) (2026)

## Abstract (arXiv)

We prove that, under low noise assumptions, the support vector machine with Nll m random features (RFSVM) can achieve the learning rate faster than O(1/√m) on a training set with m samples when an optimized feature map is used. Our work extends the previous fast rate analysis of random features method from least square loss to 0-1 loss. We also show that the reweighted feature selection method, which approximates the optimized feature map, helps improve the performance of RFSVM in experiments on a synthetic data set.