Distributed Learning with Regularized Least Squares

By Shaobo Lin, Xin Guo, Ding-Xuan Zhou. 2016

218 citations recorded by the source corpus.

We study distributed learning with the least squares regularization scheme in a reproducing kernel Hilbert space (RKHS). By a divide-and-conquer approach, the algorithm partitions a data set into disjoint data subsets, applies the least squares regularization scheme to each data subset to produce an output function, and then takes an average of the individual output functions as a final global estimator or predictor. We show with error bounds in expectation in both the $L^2$-metric and RKHS-metric that the global output function of this distributed learning is a good approximation to the algorithm processing the whole data in one single machine. Our error bounds are sharp and stated in a general setting without any eigenfunction assumption. The analysis is achieved by a novel second order decomposition of operator differences in our integral operator approach. Even for the classical least squares regularization scheme in the RKHS associated with a general kernel, we give the best learning rate in the literature.

Subfields: Artificial Intelligence, Computational Mechanics, Computer Vision and Pattern Recognition

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

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].”
Universality of Deep Convolutional Neural Networks (2018, methodology): “Our method can be applied to distributed learning algorithms [18,10].”
A Sharper Generalization Bound for Divide-and-Conquer Ridge Regression (2019, methodology): “The prior works (Zhang, Duchi, and Wainwright 2015; Lin, Guo, and Zhou 2017) established generalization bounds for the divide-and-conquer (DC) ridge regression.”
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”
Kernel ridge vs. principal component regression: Minimax bounds and the qualification of regularization operators (2017, methodology): “Moreover, it is well-known that KRR is minimax in many of the settings considered in this paper, such as those described in Corollaries 1–3 (Caponnetto and De Vito, 2007; Zhang, 2005; Zhang et al., 2013; Lin et al., 2016).”
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].”