Timezone: »

 
Poster
Nystr{ö}m Method vs Random Fourier Features: A Theoretical and Empirical Comparison
Tianbao Yang · Yu-Feng Li · Mehrdad Mahdavi · Rong Jin · Zhi-Hua Zhou

Thu Dec 06 02:00 PM -- 12:00 AM (PST) @ Harrah’s Special Events Center 2nd Floor
in Poster Session »

Both random Fourier features and the Nystr{ö}m method have been successfully applied to efficient kernel learning. In this work, we investigate the fundamental difference between these two approaches, and how the difference could affect their generalization performances. Unlike approaches based on random Fourier features where the basis functions (i.e., cosine and sine functions) are sampled from a distribution {\it independent} from the training data, basis functions used by the Nystr{ö}m method are randomly sampled from the training examples and are therefore {\it data dependent}. By exploring this difference, we show that when there is a large gap in the eigen-spectrum of the kernel matrix, approaches based the Nystr{ö}m method can yield impressively better generalization error bound than random Fourier features based approach. We empirically verify our theoretical findings on a wide range of large data sets.

[ PDF] 

Author Information

Tianbao Yang (NEC Labs America)
Yu-Feng Li (Nanjing University)
Mehrdad Mahdavi (Michigan State University (MSU))
Rong Jin (Michigan State University (MSU))
Zhi-Hua Zhou (Nanjing University)

More from the Same Authors