Fast Randomized Kernel Ridge Regression with Statistical Guarantees

By A. Alaoui, Michael W. Mahoney. 2015

326 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.

In Statistical Learning Theory

Citations in the corpus

Optimal Rates for Random Fourier Features (2015, positive): “In this paper, we provide the first detailed theoretical analysis about the approximation quality of RFFs by establishing optimal (in terms of the RFF dimension) performance guarantees in uniform and Lr (1 ≤ r ∞) norms.”
Learning Theory for Distribution Regression (2014, methodology): “We studied a ridge regression scheme defined on embeddings of the input distributions to a reproducing kernel Hilbert space, which has a simple analytical solution, as well as theoretically sound, efficient methods for approximation (Zhang et al., 2015; Richtárik and Takác̆, 2016; Alaoui and Mahoney”
Continual Deep Learning by Functional Regularisation of Memorable Past (2020, background): “These ideas are widely used in the theory of leverage-score sampling (Alaoui & Mahoney, 2015; Ma et al., 2015), where datapoints are picked proportional to the leverage score.”
Graph Neural Networks for Intelligent Transportation Systems: A Survey (2023, methodology): “The baseline models used in this study include linear regression, Ridge regression [200], Gaussian Process, Bayesian Automatic Relevance Determination [201], Multilayer Perceptron, W&D [202], LSTM, and GRU.”
Generalization Properties of Learning with Random Features (2016, methodology): “For Nyström methods, partial results in this direction were derived for example in [14] and improved in [15], but only for a simplified setting where the input points are fixed.”
Globally Convergent Newton Methods for Ill-conditioned Generalized Self-concordant Losses (2019, unknown): “(b) Subsampling with approximate leverage scores [27, 3, 28]), whereQ = O(ρ−2 ̄ dfλ log 1/λδ), c = O(min(n, a/λ) ̄ dfλ 2 ) and ̄ dfλ = Tr(W>W (W>W + λ/aI)−1) [30].”
Learning with SGD and Random Features (2018, methodology): “This idea can be used within a penalized empirical risk minimization framework [26, 27, 28] but also considering gradient [29, 30] and stochastic gradient [31] techniques.”
Limitations of Lazy Training of Two-layers Neural Networks (2019, unknown): “An incomplete list of references includes [4, 2, 5, 6, 22].”
Randomized numerical linear algebra: Foundations and algorithms (2020, background): “Likewise, Rudi et al. (2018) report empirical evidence that ridge leverage score sampling is more efficient than uniform sampling for KRR. 19.3.”
The Geometry of Random Features (2018, background): “In (Alaoui and Mahoney, 2015; Bach, 2013) it was proven that: R(fKRR) = λ 2 N (f )(K+λNIN ) −2f∗+ σ(2) N Tr(K (2)(K + λNIN ) −2), where λ stands for the regularization parameter, and K and IN are as above.”