Poster
But How Does It Work in Theory? Linear SVM with Random Features
Yitong Sun · Anna Gilbert · Ambuj Tewari

Thu Dec 6th 10:45 AM -- 12:45 PM @ Room 517 AB #128
in Thu Poster Session A »
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.
Keywords: Kernel Methods · Learning Theory · Regularization · Spaces of Functions and Kernels

Author Information

Yitong Sun (University of Michigan)
Anna Gilbert (University of Michigan)

Anna Gilbert received an S.B. degree from the University of Chicago and a Ph.D. from Princeton University, both in mathematics. In 1997, she was a postdoctoral fellow at Yale University and AT&T Labs-Research. From 1998 to 2004, she was a member of technical staff at AT&T Labs-Research in Florham Park, NJ. Since then she has been with the Department of Mathematics at the University of Michigan, where she is now a Professor. She has received several awards, including a Sloan Research Fellowship (2006), an NSF CAREER award (2006), the National Academy of Sciences Award for Initiatives in Research (2008), the Association of Computing Machinery (ACM) Douglas Engelbart Best Paper award (2008), and the EURASIP Signal Processing Best Paper award (2010). Her research interests include analysis, probability, networking, and algorithms. She is especially interested in randomized algorithms with applications to harmonic analysis, signal and image processing, networking, and massive datasets.

Ambuj Tewari (University of Michigan)

More from the Same Authors