The Generalization Performance of the Random Fourier Features Method

Anna Gilbert
University of Michigan
Friday, March 10, 2017 -
3:35pm to 4:35pm
Vincent 311

We investigate the risk bounds of support vector machines (SVM) that use the random Fourier features method as an approximate model in classification tasks under three different problem setups: (i) in the soft-margin formulation, using the same regularization parameter in the approximate and the accurate models, (ii) using the same upper bound on the 2-norm of the normal vectors, and (iii) choosing freely the 2-norm of the normal vectors in the approximate model. We also provide a series of simulation results using synthetic data to exhibit a large gap in the performance between the accurate and the
approximate models that can occur when we fail to control the regularization parameter appropriately.

Our work shows the importance of the effect of the regularization parameters when comparing the generalization performance of random Fourier features method with the accurate model and provides guidance for numerical experimentation, as well as a rigorous interpretation of the intuition that the expected risk of the kernel SVM with random
Fourier features method may be no more than $O(1/\sqrt(N))$ compared with the hypothesis learned by the accurate model.

Joint work with Yitong Sun

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 the Herman H. Goldstine Collegiate
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), the EURASIP Signal Processing Best Paper award (2010), a National
Academy of Sciences Kavli Fellow (2012), and the SIAM Ralph E. Kleinman Prize (2013).

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.