mlsanityData to 7 Oct 2026

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

arXiv 1809.04481 ↗First posted 12 Sep 2018cs.LG stat.MLcited by 28

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 6; 2022: 4; 2023: 5; 2024: 7; 2025: 4; 2026: 2.

28 papers.

Sort:

  1. 2021Learnable Fourier Features for Multi-Dimensional Spatial Positional Encodingcited by 93
  2. 2023Error Bounds for Learning with Vector-Valued Random Featurescited by 23
  3. 2024Operator Learning Using Random Features: A Tool for Scientific Computingcited by 21
  4. 2022Learning new physics efficiently with nonparametric methodscited by 20
  5. 2022Chefs' Random Tables: Non-Trigonometric Random Featurescited by 20
  6. 2021Learning with Density Matrices and Random Featurescited by 17
  7. 2021On Learning the Transformer Kernelcited by 14
  8. 2023Random Fourier Signature Featurescited by 9
  9. 2021Quantization Algorithms for Random Fourier Featurescited by 7
  10. 2024Solving Partial Differential Equations with Random Feature Modelscited by 6
  11. 2021Exponential Error Convergence in Data Classification with Optimized Random Features: Acceleration by Quantum Machine Learningcited by 4
  12. 2023FAVOR#: Sharp Attention Kernel Approximations via New Classes of Positive Random Featurescited by 4
16 more
  1. 2024Optimal Kernel Quantile Learning with Random Featurescited by 4
  2. 2025Random Feature Representation Boostingcited by 4
  3. 2025Tensor Sketch: Fast and Scalable Polynomial Kernel Approximationcited by 4
  4. 2025Computational Efficiency under Covariate Shift in Kernel Ridge Regressioncited by 4
  5. 2021Sharp Analysis of Random Fourier Features in Classificationcited by 3
  6. 2022On Average-Case Error Bounds for Kernel-Based Bayesian Quadraturecited by 3
  7. 2024RandNet-Parareal: a time-parallel PDE solver using Random Neural Networkscited by 3
  8. 2022On The Relative Error of Random Fourier Features for Preserving Kernel Distancecited by 2
  9. 2024Differentially Private Random Feature Modelcited by 2
  10. 2023Error Estimation for Random Fourier Featurescited by 1
  11. 2024Learning Expressive Random Feature Models via Parametrized Activationscited by 1
  12. 2025On the Generalization Properties of Learning the Random Feature Models with Learnable Activation Functionscited by 1
  13. 2026Manifold Random Featurescited by 1
  14. 2023Snacks: a fast large-scale kernel SVM solvercited by 0
  15. 2024Kernel Approximation using Analog In-Memory Computingcited by 0
  16. 2026Improving TensorSketch Using Complex Random Variablescited by 0