Kernel methods through the roof: handling billions of points efficiently

Abstract

Kernel methods provide an elegant and principled approach to nonparametric learning, but so far could hardly be used in large scale problems, since naïve implementations scale poorly with data size. Recent advances have shown the benefits of a number of algorithmic ideas, for example combining optimization, numerical linear algebra and random projections. Here, we push these efforts further to develop and test a solver that takes full advantage of GPU hardware. Towards this end, we designed a preconditioned gradient solver for kernel methods exploiting both GPU acceleration and parallelization with multiple GPUs, implementing out-of-core variants of common linear algebra operations to guarantee optimal hardware utilization. Further, we optimize the numerical precision of different operations and maximize efficiency of matrix-vector multiplications. As a result we can experimentally show dramatic speedups on datasets with billions of points, while still guaranteeing state of the art performance. Additionally, we make our software available as an easy to use library.

arXiv comment33 pages, 7 figures, NeurIPS 2020

References in corpus (19)

• PyTorch: An Imperative Style, High-Performance Deep Learning Library
• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• Gaussian Processes for Big Data
• Scalable Variational Gaussian Process Classification
• Kernel Interpolation for Scalable Structured Gaussian Processes (KISS-GP)
• Generalization Properties of Learning with Random Features
• Stochastic Variational Deep Kernel Learning
• Random Feature Expansions for Deep Gaussian Processes
• Variational Fourier features for Gaussian processes
• A Framework for Interdomain and Multioutput Gaussian Processes
• Product Kernel Interpolation for Scalable Gaussian Processes
• Diving into the shallows: a computational perspective on large-scale shallow learning
• But How Does It Work in Theory? Linear SVM with Random Features
• Large Scale Kernel Learning using Block Coordinate Descent
• Statistical and Computational Trade-Offs in Kernel K-Means
• Scalable Gaussian Processes with Billions of Inducing Inputs via Tensor Train Decomposition
• Kernel machines that adapt to GPUs for effective large batch training
• Beyond Least-Squares: Fast Rates for Regularized Empirical Risk Minimization through Self-Concordance
• Gain with no Pain: Efficient Kernel-PCA by Nyström Sampling

Cited by in corpus (6)

• Simple, Fast, and Flexible Framework for Matrix Completion with Infinite Width Neural Networks
• Generalized vec trick for fast learning of pairwise kernel models
• Weakly-Supervised Object Detection Learning through Human-Robot Interaction
• Snacks: a fast large-scale kernel SVM solver
• Sketch In, Sketch Out: Accelerating both Learning and Inference for Structured Prediction with Kernels
• Faster Kernel Interpolation for Gaussian Processes