Divide and Conquer Kernel Ridge Regression: A Distributed Algorithm with Minimax Optimal Rates

Abstract

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.

References in corpus (4)

• Early stopping and non-parametric regression: An optimal data-dependent stopping rule
• The Big Data Bootstrap
• Optimal learning rates for Kernel Conjugate Gradient regression
• Randomized sketches for kernels: Fast and optimal non-parametric regression

Cited by in corpus (89)

• On the Convergence of FedAvg on Non-IID Data
• Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates
• Quantile Regression Under Memory Constraint
• Distributed Statistical Machine Learning in Adversarial Settings: Byzantine Gradient Descent
• Loss minimization and parameter estimation with heavy tails
• Generalisation error in learning with random features and the hidden manifold model
• Distributed ARIMA Models for Ultra-long Time Series
• Distributed Estimation and Inference with Statistical Guarantees
• A review of distributed statistical inference
• Double Trouble in Double Descent : Bias and Variance(s) in the Lazy Regime
• Sketched Ridge Regression: Optimization Perspective, Statistical Perspective, and Model Averaging
• First-order Newton-type Estimator for Distributed Estimation and Inference
• Efficient Distributed Learning with Sparsity
• Intuitionistic Fuzzy Broad Learning System: Enhancing Robustness Against Noise and Outliers
• Distributed Simultaneous Inference in Generalized Linear Models via Confidence Distribution
• Learning Theory for Distribution Regression
• Distributed Inference for Linear Support Vector Machine
• Communication-Efficient Local Decentralized SGD Methods
• Random Vector Functional Link Neural Network based Ensemble Deep Learning
• A Divide-and-Conquer Bayesian Approach to Large-Scale Kriging
• Federated Accelerated Stochastic Gradient Descent
• A Distributed and Integrated Method of Moments for High-Dimensional Correlated Data Analysis
• Federated Data Analytics: A Study on Linear Models
• Distributed Kernel Ridge Regression with Communications
• LOCO: Distributing Ridge Regression with Random Projections
• Distributed linear regression by averaging
• Computational Limits of A Distributed Algorithm For Smoothing Spline
• GP-select: Accelerating EM using adaptive subspace preselection
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces
• Distributed inference for quantile regression processes
• Variance Reduced Median-of-Means Estimator for Byzantine-Robust Distributed Inference
• Debiased distributed learning for sparse partial linear models in high dimensions
• Doubly Distributed Supervised Learning and Inference with High-Dimensional Correlated Outcomes
• Randomized maximum-contrast selection: subagging for large-scale regression
• Fast Polynomial Kernel Classification for Massive Data
• Optimal Rates of Distributed Regression with Imperfect Kernels
• Optimal Statistical Rates for Decentralised Non-Parametric Regression with Linear Speed-Up
• Scalable and Efficient Statistical Inference with Estimating Functions in the MapReduce Paradigm for Big Data
• Generalized Leverage Score Sampling for Neural Networks
• Distributed Bayesian Learning with Stochastic Natural-gradient Expectation Propagation and the Posterior Server
• Preserving Differential Privacy Between Features in Distributed Estimation
• On the Estimation of Derivatives Using Plug-in Kernel Ridge Regression Estimators
• WONDER: Weighted one-shot distributed ridge regression in high dimensions
• Estimation of an Order Book Dependent Hawkes Process for Large Datasets
• Distributed Estimation for Principal Component Analysis: an Enlarged Eigenspace Analysis
• Distributed Estimation and Inference for Semi-parametric Binary Response Models
• DUAL-LOCO: Distributing Statistical Estimation Using Random Projections
• Simple and Almost Assumption-Free Out-of-Sample Bound for Random Feature Mapping
• Towards A Unified Analysis of Random Fourier Features
• Learning over inherently distributed data
• Greedy metrics in orthogonal greedy learning
• Efficient online learning with kernels for adversarial large scale problems
• Total Stability of SVMs and Localized SVMs
• Randomized incomplete $U$-statistics in high dimensions
• Constructive neural network learning
• A Computationally Efficient Classification Algorithm in Posterior Drift Model: Phase Transition and Minimax Adaptivity
• Manifold regularization based on Nystr{ö}m type subsampling
• Minimax Error of Interpolation and Optimal Design of Experiments for Variable Fidelity Data
• Nyström Regularization for Time Series Forecasting
• Divide-and-conquer methods for big data analysis
• Towards Sharp Analysis for Distributed Learning with Random Features
• Revisiting minimum description length complexity in overparameterized models
• Learning Theory of Distributed Regression with Bias Corrected Regularization Kernel Network
• Histogram Transform Ensembles for Large-scale Regression
• Analysis of Nystrom method with sequential ridge leverage scores
• Meta Clustering for Collaborative Learning
• Semiparametric Bayesian Inference for Local Extrema of Functions in the Presence of Noise
• Communication-efficient Byzantine-robust distributed learning with statistical guarantee
• Construction of neural networks for realization of localized deep learning
• Equivalence of Convergence Rates of Posterior Distributions and Bayes Estimators for Functions and Nonparametric Functionals
• Partitioned Cross-Validation for Divide-and-Conquer Density Estimation
• Divide and Conquer Local Average Regression
• Hypothesis Testing of One-Sample Mean Vector in Distributed Frameworks
• Adaptive Stopping Rule for Kernel-based Gradient Descent Algorithms
• A Global Bias-Correction DC Method for Biased Estimation under Memory Constraint
• Scaling up Kernel Ridge Regression via Locality Sensitive Hashing
• Distributed Adaptive Nearest Neighbor Classifier: Algorithm and Theory
• ParK: Sound and Efficient Kernel Ridge Regression by Feature Space Partitions
• Oversampling Divide-and-conquer for Response-skewed Kernel Ridge Regression
• Smoothing splines approximation using Hilbert curve basis selection
• Dynamic Regret for Strongly Adaptive Methods and Optimality of Online KRR
• Grid Point Approximation for Distributed Nonparametric Smoothing and Prediction
• Distributed Adaptive Huber Regression
• Data splitting improves statistical performance in overparametrized regimes
• Greedy Criterion in Orthogonal Greedy Learning
• Theoretical Analysis of Divide-and-Conquer ERM: Beyond Square Loss and RKHS
• $D{C}^2$: A Divide-and-conquer Algorithm for Large-scale Kernel Learning with Application to Clustering
• Two-stage Best-scored Random Forest for Large-scale Regression
• Distributed Networked Learning with Correlated Data