On the Impact of Kernel Approximation on Learning Accuracy

By Corinna Cortes, Mehryar Mohri, Ameet Talwalkar. 2010

159 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

On the Error of Random Fourier Features (2015, background): “2 of Cortes et al. (2010). In particular, we will use ‖w‖ ≤ √ κC0 and their (16-17): Φ(xi) = K 1/2 x ei ‖ŵ − w‖(2) ≤ 2C(2) 0 √ κ‖K̂ x −K x ‖,”
Scalable Kernel Methods via Doubly Stochastic Gradients (2014, methodology): “In fact, without further assumption on the regularity of the kernel matrix, the generalization ability after low-rank approximation is typically of the order O(1/ √ r + 1/ √ n) [4, 5], which implies that the rank needs to be nearly linear in the number of data points! Thus, in order for kernel metho”
Revisiting the Nystrom Method for Improved Large-scale Machine Learning (2013, methodology): “A weaker relation of this type was used by Drineas and Mahoney (2005), but the stronger form that we use here in Equation (10) was first proved in (Gittens, 2012).”
The ZipML Framework for Training Models with End-to-End Low Precision: The Cans, the Cannots, and a Little Bit of Deep Learning (2016, background): “6 Related Work There has been significant work on “low-precision SGD” De Sa et al. (2015); Alistarh et al.”
Algorithms for Learning Kernels Based on Centered Alignment (2012, methodology): “Stronger margin-based generalization guarantees based on an analysis of the Rademacher complexity, with only a square-root logarithmic dependency on the number of base kernels were given by Cortes et al. (2010b) for convex combinations of kernels with an L 1 constraint.”
Sampling Methods for the Nyström Method (2012, unknown): “…has been studied theoretically using a variety of sampling schemes (Smola and Schölkopf, 2000; Drineas and Mahoney, 2005; Zhang et al., 2008; Zhang and Kwok, 2009; Kumar et al., 2009a,b,c; Belabbas and Wolfe, 2009; Belabbas and Wolfe, 2009; Cortes et al., 2010; Talwalkar and Rostamizadeh, 2010).”
A Survey of Modern Questions and Challenges in Feature Extraction (2015, methodology): “These methods include approximating the kernel matrix, for example with Nyström method (Drineas and Mahoney, 2005; Cortes et al., 2010c), or approximating the kernel function with random Fourier features (Rahimi and Recht, 2007; Pham and Pagh, 2013; Hamid et al., 2013).”
Generalization Properties of Learning with Random Features (2016, background): “[20, 21, 22], essentially confirm these considerations, albeit the analysis in [22] suggests that fewer random features could suffice if sampled in a problem dependent way.”
Nyström Method vs Random Fourier Features: A Theoretical and Empirical Comparison (2012, methodology): “We choose the bound based on spectral norm according to the discussion in [6].”
Improved Bounds for the Nyström Method With Application to Kernel Classification (2011, unknown): “…examples in D , which signiﬁcantly reduces the complexity of the kernel classiﬁer compared to the approach suggested in (Williams and Seeger, 2001; Cortes et al., 2010). b We also note that the proposed approach is equivalent to learning a linear classiﬁer by representing each instance x with…”
Predicting speech recognition confidence using deep learning with word identity and score features (2013, methodology): “Equation (2) can be computed efficiently by using the Nyström-Woodbury approximation [11, 15, 16].”
Random features for Kernel Deep Convex Network (2013, methodology): “Nyström methods sample a subset columns of the original kernel matrix [10, 11, 13].”
Less is More: Nyström Computational Regularization (2015, background): “Results in this direction, albeit suboptimal, were first derived in [20] (see also [21,22]), and more recently in [23,24].”
Learning Semantic Image Representations at a Large Scale (2014, methodology): “Such a sampling perspective have been shown to be very effective in kernel machines [123, 23, 67].”
ZipML: Training Linear Models with End-to-End Low Precision, and a Little Bit of Deep Learning (2017, background): “For SVM the straw man approach can also be seen as a very simple case of kernel approximation (Cortes et al., 2010).”
Efficient Hyperparameter Optimization and Infinitely Many Armed Bandits (2016, background): “Although there exist theoretical bounds that relate the performance of configurations trained on a subsample to that on the whole dataset (Smale & Zhou, 2003; Steinwart & Scovel, 2007; Cortes et al., 2010; Bach, 2013), as Krueger et al. (2015) notes, “existing theoretical results are not able to bou”