Sharp analysis of low-rank kernel matrix approximations

By Francis R. Bach. 2012

305 citations recorded by the source corpus.

We consider supervised learning problems within the positive-definite kernel framework, such as kernel ridge regression, kernel logistic regression or the support vector machine. With kernels leading to infinite-dimensional feature spaces, a common practical limiting difficulty is the necessity of computing the kernel matrix, which most frequently leads to algorithms with running time at least quadratic in the number of observations n, i.e., O(n^2). Low-rank approximations of the kernel matrix are often considered as they allow the reduction of running time complexities to O(p^2 n), where p is the rank of the approximation. The practicality of such methods thus depends on the required rank p. In this paper, we show that in the context of kernel ridge regression, for approximations based on a random subset of columns of the original kernel matrix, the rank p may be chosen to be linear in the degrees of freedom associated with the problem, a quantity which is classically used in the statistical analysis of such methods, and is often seen as the implicit number of parameters of non-parametric estimators. This result enables simple algorithms that have sub-quadratic running time complexity, but provably exhibit the same predictive performance than existing algorithms, for any given problem instance, and not only for worst-case situations.

Subfields: Artificial Intelligence, Computational Mechanics, Computer Vision and Pattern Recognition, Probabilistic & Bayesian Methods, Pure Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

  1. Bernhard Schölkopf
  2. Yoshua Bengio
  3. Francis R. Bach
  4. Sergey Levine
  5. Michael I. Jordan
  6. Ruslan Salakhutdinov
  7. Percy Liang
  8. Michael W. Mahoney

In Computational Mechanics

  1. Francis R. Bach
  2. Michael W. Mahoney
  3. Alessandro Rudi
  4. Lorenzo Rosasco
  5. Peter Richtárik
  6. Martin J. Wainwright
  7. A. Alaoui
  8. Joel A. Tropp

In Computer Vision and Pattern Recognition

  1. Luc Van Gool
  2. Dacheng Tao
  3. Trevor Darrell
  4. Ming-Hsuan Yang
  5. Jitendra Malik
  6. Xiaogang Wang
  7. Bernt Schiele
  8. Alan L. Yuille

In Probabilistic & Bayesian Methods

  1. Bernhard Schölkopf
  2. Kenji Fukumizu
  3. Krikamol Muandet
  4. Bharath K. Sriperumbudur
  5. Arthur Gretton
  6. Francis R. Bach
  7. Byron Boots
  8. Michael W. Mahoney

In Pure Mathematics

  1. Michael W. Mahoney
  2. Kenji Fukumizu
  3. Bharath K. Sriperumbudur
  4. Bernhard Schölkopf
  5. A. Alaoui
  6. Alessandro Rudi
  7. Lorenzo Rosasco
  8. Martin J. Wainwright

Citations in the corpus