arXiv (Cornell University) · 2013 · 301 citations · 28 references
ComputingComputer ScienceAlgorithmsMachine LearningOptimizationDimension ReductionKernel MethodsMatrix ComputationMaximum Likelihood EstimationOptimization For Machine LearningDecomposition-based OptimizationKernel RegressionKernel Ridge RegressionMinimax RatesMinimax TheoremOptimal Convergence RatesRidge RegressionSobolev Spaces
We establish optimal convergence rates for a decomposition-based scalable approach to kernel ridge regression. The method is simple to describe: it randomly partitions a dataset of size N into m subsets of equal size, computes an independent kernel ridge regression estimator for each subset, then averages the local solutions into a global predictor. This partitioning leads to a substantial reduction in computation time versus the standard approach of performing kernel ridge regression on all N samples. Our two main theorems establish that despite the computational speed-up, statistical optimality is retained: as long as m is not too large, the partition-based estimator achieves the statistical minimax rate over all estimators using the set of N samples. As concrete examples, our theory guarantees that the number of processors m may grow nearly linearly for finite-rank kernels and Gaussian kernels and polynomially in N for Sobolev spaces, which in turn allows for substantial reductions in computational cost. We conclude with experiments on both simulated data and a music-prediction task that complement our theoretical results, exhibiting the computational and statistical benefits of our approach.
28
Ridge Regression: Biased Estimation for Nonorthogonal Problems
Arthur E. Hoerl, Robert W. Kennard · Technometrics · 2000 · 6.6K citations
Optimization by Vector Space Methods
Students Quarterly Journal · 1970 · 6.1K citations
Natural Sciences, Industrial Engineering, Design Optimization +6
Random Features for Large-Scale Kernel Machines
Ali Rahimi, Benjamin Recht · 2007 · 2.7K citations