ICML 2019oral162 citations
Towards a Unified Analysis of Random Fourier Features
Zhu Li, Jean-Francois Ton, Dino Oglic, Dino Sejdinovic
Abstract
Random Fourier features is a widely used, simple, and effective technique for scaling up kernel methods. The existing theoretical analysis of the approach, however, remains focused on specific learning tasks and typically gives pessimistic bounds which are at odds with the empirical results. We tackle these problems and provide the first unified risk analysis of learning with random Fourier features using the squared error and Lipschitz continuous loss functions. In our bounds, the trade-off between the computational cost and the expected risk convergence rate is problem specific and expressed in terms of the regularization parameter and the
BibTeX
@InProceedings{pmlr-v97-li19k,
title = {Towards a Unified Analysis of Random {F}ourier Features},
author = {Li, Zhu and Ton, Jean-Francois and Oglic, Dino and Sejdinovic, Dino},
booktitle = {Proceedings of the 36th International Conference on Machine Learning},
pages = {3905--3914},
year = {2019},
editor = {Chaudhuri, Kamalika and Salakhutdinov, Ruslan},
volume = {97},
series = {Proceedings of Machine Learning Research},
month = {09--15 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v97/li19k/li19k.pdf},
url = {https://proceedings.mlr.press/v97/li19k.html},
abstract = {Random Fourier features is a widely used, simple, and effective technique for scaling up kernel methods. The existing theoretical analysis of the approach, however, remains focused on specific learning tasks and typically gives pessimistic bounds which are at odds with the empirical results. We tackle these problems and provide the first unified risk analysis of learning with random Fourier features using the squared error and Lipschitz continuous loss functions. In our bounds, the trade-off between the computational cost and the expected risk convergence rate is problem specific and expressed in terms of the regularization parameter and the