2020 · 13 citations · 26 references
ComputingComputer EngineeringComputer ScienceMachine LearningParallel AlgorithmsParallel ComputingData ParallelismKernel MethodsMatrix ComputationMemory HierarchyScalable Algorithm DesignScalable Machine LearningBenchmark DatasetsDistributed MemoryKernel ApproximationKernel RegressionKernel Ridge RegressionLow-rank ApproximationParallel Matrix ComputationRidge Regression
We present a scalable and memory-efficient framework for kernel ridge regression. We exploit the inherent rank deficiency of the kernel ridge regression matrix by constructing an approximation that relies on a hierarchy of low-rank factorizations of tunable accuracy, rather than leverage scores or other subsampling techniques. Without ever decompressing the kernel matrix approximation, we propose factorization and solve methods to compute the weight(s) for a given set of training and test data. We show that our method performs an optimal number of operations $\mathcal{O}\left( {{r^2}n} \right)$ with respect to the number of training samples (n) due to the underlying numerical low-rank (r) structure of the kernel matrix. Furthermore, each algorithm is also presented in the context of a massively parallel computer system, exploiting two levels of concurrency that take into account both shared-memory and distributed-memory inter-node parallelism. In addition, we present a variety of experiments using popular datasets – small, and large – to show that our approach provides sufficient accuracy in comparison with state-of-the-art methods and with the exact (i.e. non-approximated) kernel ridge regression method. For datasets, in the order of 10 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">6</sup> data points, we show that our framework strong-scales to 10 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">3</sup> cores. Finally, we provide a Python interface to the scikit-learn library so that scikit-learn can leverage our high-performance solver library to achieve much-improved performance and memory footprint.
26
Scikit-learn: Machine Learning in Python
Fabián Pedregosa, Gaël Varoquaux, Alexandre Gramfort et al. · arXiv (Cornell University) · 2012 · 63.7K citations · Full text
Random Features for Large-Scale Kernel Machines
Ali Rahimi, Benjamin Recht · 2007 · 2.7K citations
Kernel methods in machine learning
The Annals of Statistics · 2008 · 1.6K citations · Full text
Using the Nyström Method to Speed Up Kernel Machines
Christopher K. I. Williams, Matthias Seeger · 2000 · 1.5K citations