Divide and Conquer Kernel Ridge Regression

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

216 citations recorded by the source corpus.

How researchers see this paper

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

Citations in the corpus

Is Local SGD Better than Minibatch SGD? (2020, background): “Finally, there is a literature on “one-shot-averaging” for quadratic objectives, which corresponds to an extreme where the outputs of an algorithm applied to several diﬀerent training sets are averaged, (e.g. Zhang et al., 2013a,b).”
Distributed Robust Learning (2014, methodology): “Previous divide-and-conquer distributed learning works [18, 17, 13] commonly merge the k separate estimations by taking their average, i.e. , However, the above average is fragile to outliers [11] with zero breakdown point.”
Fundamental Limits of Online and Distributed Algorithms for Statistical Learning and Estimation (2013, background): “Similar kind of gaps can be shown using Thm. 3 for general ( b, n, m ) protocols, which apply to any special case such as non-interactive distributed learning.”
Randomized sketches for kernels: Fast and optimal non-parametric regression (2015, methodology): “[35] analyze a distributed implementation of KRR, in which a set of t machines each compute a separate estimate based on a random t-way partition of the full data set, and combine it into a global estimate by averaging.”
Communication-efficient algorithms for statistical optimization (2012, methodology): “Our own recent work has addressed aspects of this challenge in the context of kernel methods for non-parametric regression (Zhang et al., 2013).”
Distributed Statistical Estimation and Rates of Convergence in Normal Approximation (2017, unknown): “More generally, it has been shown by Battey et al. (2015); Zhang et al. (2013) that in many problems (for instance, linear regression), k can be taken as large as O ( √ N ) without negatively aﬀecting the estimation rates; similar guarantees hold for a variety of M-estimators (see Rosenblatt and…”
Generalization Properties of Learning with Random Features (2016, methodology): “The experiment shows that the predictions by Thm. 5 are quite accurate, since the probabilistic estimations are within one standard deviation from the values measured in the simulation.”
Decoding the Deep: Exploring Class Hierarchies of Deep Representations Using Multiresolution Matrix Factorization (2017, background): “Devising such block-structured kernels was the original motivation for several local low-rank and hierarchical factorizations [27, 4, 20, 38].”
Additive Approximations in High Dimensional Nonparametric Regression via the SALSA (2016, methodology): “Finally, by Markov’s inequality, Once again, we follow Zhang et al. (2013).”
Less is More: Nyström Computational Regularization (2015, methodology): “Relevant results are given in [8] for a different approach, based on averaging KRLS solutions obtained splitting the data in m groups (divide and conquer RLS).”
Memory Efficient Kernel Approximation (2014, methodology): “Besides kernel approximation algorithms, we compare our method with another divide-and-conquer based kernel ridge regression method (denoted DC-KRR)(Zhang et al., 2013).”
Quantum machine learning: a classical perspective (2017, methodology): “This strategy benefits computationally from both the parallelization and reduced dimension of distributed datasets and it has been shown to achieve the same statistical guarantees of classical methods under suitable partitions of the training data [25].”
Fast Randomized Kernel Ridge Regression with Statistical Guarantees (2015, methodology): “As an example of this, we can directly compare the Nyström sampling method to a related divide-and-conquer approach, thereby answering an open problem of Zhang et al. [9].”
Fast Randomized Kernel Methods With Statistical Guarantees (2014, methodology): “The quantity d eﬀ is called the eﬀective dimensionality of the learning problem, and it can be interpreted as the implicit number of parameters in this nonparametric setting [7, 8].”
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).”
Divide and conquer in nonstandard problems and the super-efficiency phenomenon (2016, background): “, [20, 29, 30] – with an emphasis on function estimation under monotonicity constraints which constitutes an important genre of non-standard problems of the above type.”