Sharp analysis of low-rank kernel matrix approximations

Abstract

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.

References in corpus (6)

• Statistical performance of support vector machines
• Randomized algorithms for matrices and data
• Testing for Homogeneity with Kernel Fisher Discriminant Analysis
• The spectral norm error of the naive Nystrom extension
• Online Learning as Stochastic Approximation of Regularization Paths
• A Risk Comparison of Ordinary Least Squares vs Ridge Regression

Cited by in corpus (15)

• Kernel Mean Embedding of Distributions: A Review and Beyond
• Learning Decentralized Controllers for Robot Swarms with Graph Neural Networks
• Distributed learning with regularized least squares
• Improved Fixed-Rank Nyström Approximation via QR Decomposition: Practical and Theoretical Aspects
• Optimal mini-batch and step sizes for SAGA
• Randomized co-training: from cortical neurons to machine learning and back again
• Efficient Data-Driven Geologic Feature Detection from Pre-stack Seismic Measurements using Randomized Machine-Learning Algorithm
• Learning the kernel matrix via predictive low-rank approximations
• A Partially Linear Framework for Massive Heterogeneous Data
• Sketch In, Sketch Out: Accelerating both Learning and Inference for Structured Prediction with Kernels
• Towards Sharp Analysis for Distributed Learning with Random Features
• Manifold regularization based on Nystr{ö}m type subsampling
• One-shot Distibuted Algorithm for PCA with RBF Kernels
• Large-scale Kernel-based Feature Extraction via Budgeted Nonlinear Subspace Tracking
• New efficient algorithms for multiple change-point detection with kernels