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

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.

arXiv commentAccepted by NeurIPS2018

Cited by in corpus (16)

• Learnable Fourier Features for Multi-Dimensional Spatial Positional Encoding
• Kernel methods through the roof: handling billions of points efficiently
• Random Features for Kernel Approximation: A Survey on Algorithms, Theory, and Beyond
• On Sampling Random Features From Empirical Leverage Scores: Implementation and Theoretical Guarantees
• On Kernel Derivative Approximation with Random Fourier Features
• No-Trick (Treat) Kernel Adaptive Filtering using Deterministic Features
• Fast Learning in Reproducing Kernel Krein Spaces via Signed Measures
• Towards A Unified Analysis of Random Fourier Features
• Towards a Unified Quadrature Framework for Large-Scale Kernel Machines
• Exponential Error Convergence in Data Classification with Optimized Random Features: Acceleration by Quantum Machine Learning
• On Learning the Transformer Kernel
• ORCCA: Optimal Randomized Canonical Correlation Analysis
• Additive function approximation in the brain
• Quantization Algorithms for Random Fourier Features
• Regularized ERM on random subspaces
• Random Fourier Features via Fast Surrogate Leverage Weighted Sampling