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

arXiv: https://arxiv.org/abs/1305.5029 · HTML: https://mlsanity.com/paper/1305.5029/

## Key facts

- Cited by 65 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 May 2013.

## Built on by (most cited first, 30 of 65)

- [Fast Sketching of Polynomial Kernels of Polynomial Degree](https://mlsanity.com/paper/2108.09420/) (2021)
- [On the Optimality of Misspecified Spectral Algorithms](https://mlsanity.com/paper/2303.14942/) (2023)
- [An Analysis of Attention via the Lens of Exchangeability and Latent Variable Models](https://mlsanity.com/paper/2212.14852/) (2022)
- [Achieving Fairness with a Simple Ridge Penalty](https://mlsanity.com/paper/2105.13817/) (2021)
- [Intuitionistic Fuzzy Broad Learning System: Enhancing Robustness Against Noise and Outliers](https://mlsanity.com/paper/2307.08713/) (2023)
- [Variance Reduced Median-of-Means Estimator for Byzantine-Robust Distributed Inference](https://mlsanity.com/paper/2103.02860/) (2021)
- [Quantifying Epistemic Uncertainty in Deep Learning](https://mlsanity.com/paper/2110.12122/) (2021)
- [Accelerating Heterogeneous Federated Learning with Closed-form Classifiers](https://mlsanity.com/paper/2406.01116/) (2024)
- [Federated Data Analytics: A Study on Linear Models](https://mlsanity.com/paper/2206.07786/) (2022)
- [Communication-Constrained Distributed Quantile Regression with Optimal Statistical Guarantees](https://mlsanity.com/paper/2110.13113/) (2021)
- [Statistical Optimality of Divide and Conquer Kernel-based Functional Linear Regression](https://mlsanity.com/paper/2211.10968/) (2022)
- [Nonlinear Meta-Learning Can Guarantee Faster Rates](https://mlsanity.com/paper/2307.10870/) (2023)
- [Federated Online and Bandit Convex Optimization](https://mlsanity.com/paper/2311.17586/) (2023)
- [ParK: Sound and Efficient Kernel Ridge Regression by Feature Space Partitions](https://mlsanity.com/paper/2106.12231/) (2021)
- [Data splitting improves statistical performance in overparametrized regimes](https://mlsanity.com/paper/2110.10956/) (2021)
- [Radial Basis Function Approximation with Distributively Stored Data on Spheres](https://mlsanity.com/paper/2112.02499/) (2021)
- [Total Stability of SVMs and Localized SVMs](https://mlsanity.com/paper/2101.12678/) (2021)
- [From inexact optimization to learning via gradient concentration](https://mlsanity.com/paper/2106.05397/) (2021)
- [Dynamic Regret for Strongly Adaptive Methods and Optimality of Online KRR](https://mlsanity.com/paper/2111.11550/) (2021)
- [ROTI-GCV: Generalized Cross-Validation for right-ROTationally Invariant Data](https://mlsanity.com/paper/2406.11666/) (2024)
- [Optimal Kernel Quantile Learning with Random Features](https://mlsanity.com/paper/2408.13591/) (2024)
- [Sharp Analysis of Random Fourier Features in Classification](https://mlsanity.com/paper/2109.10623/) (2021)
- [Nystr"om Regularization for Time Series Forecasting](https://mlsanity.com/paper/2111.07109/) (2021)
- [Adaptive Parameter Selection for Kernel Ridge Regression](https://mlsanity.com/paper/2312.05885/) (2023)
- [Supervised Kernel Thinning](https://mlsanity.com/paper/2410.13749/) (2024)
- [Distributed Gradient Descent for Functional Learning](https://mlsanity.com/paper/2305.07408/) (2023)
- [Locally Adaptive and Differentiable Regression](https://mlsanity.com/paper/2308.07418/) (2023)
- [Adaptive Distributed Kernel Ridge Regression: A Feasible Distributed Learning Scheme for Data Silos](https://mlsanity.com/paper/2309.04236/) (2023)
- [Distributed Uncertainty Quantification of Kernel Interpolation on Spheres](https://mlsanity.com/paper/2310.16384/) (2023)
- [Distributed High-Dimensional Quantile Regression: Estimation Efficiency and Support Recovery](https://mlsanity.com/paper/2405.07552/) (2024)

## Abstract (arXiv)

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.