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
- Bernhard Schölkopf
- Yoshua Bengio
- Francis R. Bach
- Sergey Levine
- Michael I. Jordan
- Ruslan Salakhutdinov
- Percy Liang
- Michael W. Mahoney
In Computational Mechanics
- Francis R. Bach
- Michael W. Mahoney
- Alessandro Rudi
- Lorenzo Rosasco
- Peter Richtárik
- Martin J. Wainwright
- A. Alaoui
- Joel A. Tropp
In Computer Vision and Pattern Recognition
- Luc Van Gool
- Dacheng Tao
- Trevor Darrell
- Ming-Hsuan Yang
- Jitendra Malik
- Xiaogang Wang
- Bernt Schiele
- Alan L. Yuille
In Probabilistic & Bayesian Methods
- Bernhard Schölkopf
- Kenji Fukumizu
- Krikamol Muandet
- Bharath K. Sriperumbudur
- Arthur Gretton
- Francis R. Bach
- Byron Boots
- Michael W. Mahoney
In Pure Mathematics
- Michael W. Mahoney
- Kenji Fukumizu
- Bharath K. Sriperumbudur
- Bernhard Schölkopf
- A. Alaoui
- Alessandro Rudi
- Lorenzo Rosasco
- Martin J. Wainwright
Citations in the corpus
- Kernel Mean Embedding of Distributions: A Review and Beyonds (2016, methodology): “Bach et al. (2012) also pointed out that the fast convergence rate is not guaranteed in an infinite dimensional Hilbert space. To alleviate this issue, Bach et al. (2012) shows that the herding procedure of Welling (2009a) takes the form of a convex optimization algorithm in which convergence result”
- On the Equivalence between Kernel Quadrature Rules and Random Feature Expansions (2015, methodology): “Then, Bernstein concentration inequalities for operators ( Minsker, 2011) can be used in a way similar to the work of Bach (2013); El Alaoui and Mahoney (2014) on column sampling, to provide a bound on all desired quantities.”
- Quasi-Monte Carlo Feature Maps for Shift-Invariant Kernels (2014, methodology): “Indeed, Bach et al. (2012) recently shown that these restrictions never hold for infinite-dimensional RKHS, as long as the domain is compact.”
- Divide and conquer kernel ridge regression: a distributed algorithm with minimax optimal rates (2013, methodology): “Concurrent work by Bach [1] establishes conditions on the maintained rank that still guarantee optimal convergence rates; see the discussion for more detail.”
- Stat260/cs294: Randomized Algorithms for Matrices and Data (methodology): “…Today, we will use the concentration results of the last few classes to go back and make statements about approximating the product of two matrices; and we will also describe an important topic we will spend a great deal more time on, i.e., random projections and Johnson-Lindenstrauss lemmas.”
- On the Effectiveness of Richardson Extrapolation in Machine Learning (2020, unknown): “Following Bach (2013), we assume for simplicity that Φ is deterministic and that y = z + ε , where ε has zero mean and covariance matrix σ 2 I .”
- Constant Step Size Stochastic Gradient Descent for Probabilistic Modeling (2018, background): “In theory and practice, m can be chosen small (Bach, 2013; Rudi et al., 2017).”
- Distributed Learning with Regularized Least Squares (2016, background): “…introduced in the literature such as low-rank approximations of kernel matrices for kernel principal component analysis (Sch¨olkopf et al., 1998; Bach, 2013), incomplete Cholesky decomposition (Fine, 2002), early-stopping of iterative optimization algorithms for gradient descent methods (Yao et…”
- Less is More: Nyström Computational Regularization (2015, background): “As already mentioned, results close to those in Theorem 1 are given in [23, 24] in a fixed design setting.”
- Generalization Properties of Learning with Random Features (2016, methodology): “For Nyström methods, partial results in this direction were derived for example in [14] and improved in [15], but only for a simplified setting where the input points are fixed.”
- Randomized sketches for kernels: Fast and optimal non-parametric regression (2015, methodology): “Bach [5] analyzed the prediction error of the Nyström approximation to KRR based on uniformly sampling a subset of p-columns of the kernel matrix K , leading to an overall computational complexity of O(np2).”
- Non-parametric Stochastic Approximation with Large Step sizes (2014, methodology): “data in Rd, d > 1, and so-called Mercer kernels (continuous kernels over a compact set) that lead to dense subspaces of the space of square-integrable functions and non parametric estimation [4], has been widely studied in the last decade starting with the works of Smale and Cucker [5, 6] and being ”
- Initialization matters: Orthogonal Predictive State Recurrent Neural Networks (2018, background): “It is a well known result (Alaoui & Mahoney, 2015; Bach, 2013) that the empirical risk of fKRR is given by the formula: R(fKRR) = N−1λ2(f∗vec)>(K + λNIN )−2f∗vec +N−1σ2Tr(K2(K + λNIN )−2), (5) where λ > 0 stands for the regularization parameter and IN ∈ RN×N is an identity matrix.”
- On the Equivalence between Quadrature Rules and Random Features (2015, methodology): “Then, Bernstein concentration inequalities for operators (Minsker, 2011) can be used in a way similar to the work of Bach (2013); El Alaoui and Mahoney (2014) on column sampling.”
- Neural Operator: Learning Maps Between Function Spaces (2021, methodology): “Low-rank decomposition is a popular method used in kernel methods and Gaussian process (Kulis et al., 2006; Bach, 2013; Lan et al., 2017; Gardner et al., 2018).”