On Kernel Derivative Approximation with Random Fourier Features

2018-10-11 · Zoltan Szabo, Bharath K. Sriperumbudur

Random Fourier features (RFF) represent one of the most popular and wide-spread techniques in machine learning to scale up kernel algorithms. Despite the numerous successful applications of RFFs, unfortunately, quite little is understood theoretically on their optimality and limitations of their performance. Only recently, precise statistical-computational trade-offs have been established for RFFs in the approximation of kernel values, kernel ridge regression, kernel PCA and SVM classification. Our goal is to spark the investigation of optimality of RFF-based approximations in tasks involving not only function values but derivatives, which naturally lead to optimization problems with kernel derivatives. Particularly, in this paper, we focus on the approximation quality of RFFs for kernel derivatives and prove that the existing finite-sample guarantees can be improved exponentially in terms of the domain where they hold, using recent tools from unbounded empirical process theory. Our result implies that the same approximation guarantee is attainable for kernel derivatives using RFF as achieved for kernel values.

📄 PDF Abstract BibTeX arXiv:1810.05207

Code (0)

등록된 구현이 없습니다.

Methods 이 논문이 사용한 방법론

SVM A Support Vector Machine, or SVM, is a non-parametric supervised learning model. For non-linear classification and regression, they utilise the kernel trick to map inputs…

PCA Principle Components Analysis (PCA) is an unsupervised method primary used for dimensionality reduction within machine learning. PCA is calculated via a singular value…

Optimal Rates for Random Fourier Features

2015-06-06 · NeurIPS 2015 12 · Bharath K. Sriperumbudur, Zoltan Szabo

Kernel methods represent one of the most powerful tools in machine learning to tackle problems expressed in terms of function values and derivatives due to their capability to represent and model complex relations. While…

Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees

2018-04-26 · ICML 2017 8 · Haim Avron, Michael Kapralov, Cameron Musco, Christopher Musco 외

Random Fourier features is one of the most popular techniques for scaling up kernel methods, such as kernel ridge regression. However, despite impressive empirical results, the statistical properties of random Fourier fe…

regression

Random Fourier Features for Operator-Valued Kernels

2016-05-09 · Romain Brault, Florence d'Alché-Buc, Markus Heinonen

Devoted to multi-task learning and structured output learning, operator-valued kernels provide a flexible tool to build vector-valued functions in the context of Reproducing Kernel Hilbert Spaces. To scale up these metho…

Multi-Task Learning Translation

Orthogonal Random Features: Explicit Forms and Sharp Inequalities

2023-10-11 · Nizar Demni, Hachem Kadri

Random features have been introduced to scale up kernel methods via randomization techniques. In particular, random Fourier features and orthogonal random features were used to approximate the popular Gaussian kernel. Ra…

Data Dependent Kernel Approximation using Pseudo Random Fourier Features

2017-11-27 · Bharath Bhushan Damodaran, Nicolas Courty, Philippe-Henri Gosselin

Kernel methods are powerful and flexible approach to solve many problems in machine learning. Due to the pairwise evaluations in kernel methods, the complexity of kernel computation grows as the data size increases; thus…