But How Does It Work in Theory? Linear SVM with Random Features
This work provides theoretical insights into random feature methods for SVMs, which is incremental as it extends prior analysis from least square to 0-1 loss.
The paper tackles the problem of achieving faster learning rates for linear SVMs with random features under low noise assumptions, proving a rate faster than O(1/√m) with an optimized feature map and showing experimental improvement using a reweighted feature selection method on synthetic data.
We prove that, under low noise assumptions, the support vector machine with $N\ll m$ random features (RFSVM) can achieve the learning rate faster than $O(1/\sqrt{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.