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

Part of Advances in Neural Information Processing Systems 31 (NeurIPS 2018)

Authors

Yitong Sun, Anna Gilbert, Ambuj Tewari

Abstract

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.