Divide and conquer kernel ridge regression: a distributed algorithm with minimax optimal rates

By Yuchen Zhang, John C. Duchi, Martin J. Wainwright. 2013

410 citations recorded by the source corpus.

We study a decomposition-based scalable approach to kernel ridge regression, and show that it achieves minimax optimal convergence rates under relatively mild conditions. 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 using a careful choice of the regularization parameter, 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 subsets m may grow nearly linearly for finite-rank or 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.

Subfields: Artificial Intelligence, Computational Mechanics, Computer Vision and Pattern Recognition, Optimization & Training, Statistical Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Computer Vision and Pattern Recognition

In Optimization & Training

In Statistical Learning Theory

Citations in the corpus

Communication Efficient Decentralized Training with Multiple Local Updates (2019, background): “An orthogonal one is to pay more local computation for less communication, e.g., one-shot aggregation [53, 54, 16, 21, 46], primal-dual algorithms [37, 38, 7] and distributed Newton methods [33, 52, 29, 35, 25].”
On the Convergence of FedAvg on Non-IID Data (2019, methodology): “If the data are iid distributed, distributed optimization can be efﬁciently solved by the second-order algorithms [15, 19, 23, 25, 36] and the one-shot methods [12, 13, 32, 37, 38].”
Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates (2018, methodology): “An important class of algorithms are based on one-round aggregation methods (Rosenblatt and Nadler, 2016, Zhang et al., 2012, 2015).”
Distributed Statistical Machine Learning in Adversarial Settings (2017, methodology): “One-Shot Aggregation: On the other end of the spectrum, using a One-Short Aggregation method, each working machine computes an estimate of the model parameter using only its local data and reports it to the server, which then aggregates all the estimates reported to obtain a final estimate [33, 32].”
Federated Learning: Challenges, Methods, and Future Directions (2019, background): “n tolerate a lack of precision; this error can in fact help with generalization [129]. While oneshot or divide-and-conquer communication schemes have been explored in traditional data center settings [73, 137], the behavior of these methods is not well-understood in massive or statistical heterogene”
Learning Theory for Distribution Regression (2014, methodology): “Beyond its simple analytical formula, kernel ridge regression also allows efficient distributed (Zhang et al., 2015; Richtárik and Takác̆, 2016), sketch (Alaoui and Mahoney, 2015; Yang et al.”
Preserving privacy between features in distributed estimation (2017, background): “Distributed estimation and optimization when the data are horizontally partitioned has been a popular topic in recent years (Jaggi et al., 2014; Zhang et al., 2015).”
Two-stage sampled learning theory on distributions (2014, methodology): “(7)Recently, [36] has constructed theoretically sound parallelization algorithms for kernel ridge regression.”
Loss Minimization and Parameter Estimation with Heavy Tails (2013, methodology): “For instance, in Zhang et al. (2013), faster parallel kernel ridge regression is achieved by performing loss minimizations on independent samples and then averaging the resulting estimators.”
Efficient Distributed Learning with Sparsity (2016, methodology): “The bounded second and third order derivative for `p , q is true for popular loss functions used in statistical learning, such as squared loss for regression and logistic loss for classification (Zhang et al., 2013b).”
Parallelizing Stochastic Gradient Descent for Least Squares Regression: Mini-batching, Averaging, and Model Misspecification (2016, background): “Finally, parameter mixing in the stochastic approximation context (Rosenblatt and Nadler, 2014; Zhang et al., 2015) offers linear parallelization speedups on the variance error while not improving the bias (Rosenblatt and Nadler, 2014).”
Parallelizing Stochastic Approximation Through Mini-Batching and Tail-Averaging (2016, methodology): “Indeed, model averaging results are known to be minimax optimal [25, 26], however, the bias term is unimprovable using these schemes, as noted by [26].”
Distributed Learning with Regularized Least Squares (2016, methodology): “…of equal size, under the assumption that for some constants k > 2 and A < ∞ , the eigenfunctions { ϕ i } i satisfy that f ρ ∈ H K and λ i ≤ ai − 2 α for some α > 1 / 2 and a > 0, it was proved in (Zhang et al., 2015) that for λ = N 2 α 2 α +1 and m satisfying the restriction i (cid:16) (cid:17) .”
DUAL-LOCO: Distributing Statistical Estimation Using Random Projections (2015, background): “Other recent work considers solving statistical estimation tasks using a single round of communication [6, 7].”
A Split-and-Conquer Approach for Analysis of Extraordinarily Large Data (2014, methodology): “Zhang, Duchi, and Wainwright (2013) provide a divide-and-combine method for kernel ridge regression, that divides a dataset into several subsets.”
Efficient Water Quality Prediction Using Supervised Machine Learning (2019, background): “It uses entropy to select the root variable, and, based on this, it looks towards the other parameters’ values.”
Communication-Efficient Local Decentralized SGD Methods (2019, methodology): “, one-shot aggregation [47, 48, 14, 19, 41], primal-dual algorithms [32, 33, 6] and distributed Newton methods [29, 46, 26, 30, 23].”
The Geometry of Random Features (2018, background): “The KRR algorithm is a subject of intense research since ridge regression is one of the most fundamental machine learning methods that can be kernelized (Avron et al., 2016; Zhang et al., 2015).”
Optimal Statistical Rates for Decentralised Non-Parametric Regression with Linear Speed-Up (2019, background): “While statistical similarities of local objective functions and the statistics/communication trade-off have been investigated and exploited in centralised server-clients setup, typically in the analysis and design of divide-and-conquer schemes [60, 28, 20, 32, 26, 1, 62, 46, 45, 61, 2], only recentl”