Less is More: Nyström Computational Regularization

By Alessandro Rudi, Raffaello Camoriano, Lorenzo Rosasco. 2015

299 citations recorded by the source corpus.

We study Nystrom type subsampling approaches to large scale kernel methods, and prove learning bounds in the statistical learning setting, where random sampling and high probability estimates are considered. In particular, we prove that these approaches can achieve optimal learning bounds, provided the subsampling level is suitably chosen. These results suggest a simple incremental variant of Nystrom Kernel Regularized Least Squares, where the subsampling level implements a form of computational regularization, in the sense that it controls at the same time regularization and computations. Extensive experimental analysis shows that the considered approach achieves state of the art performances on benchmark large scale datasets.

Subfields: Computational Mechanics, Mathematical Physics, Statistical and Nonlinear Physics

How researchers see this paper

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

In Computational Mechanics

In Mathematical Physics

In Statistical and Nonlinear Physics

Citations in the corpus

To understand deep learning we need to understand kernel learning (2018, neutral): “, (Steinwart & Christmann, 2008; Rudi et al., 2015)) are of the following (general) form: ∣∣∣∣ 1 n∑ i l(f(xi), yi)− EP [l(f(x), y)] ∣∣∣∣ ≤”
Generalization Properties of Learning with Random Features (2016, methodology): “For this latter case, we borrow and extend ideas from [22, 16] and inspired from the theory of statical leverage scores [23].”
Distributed Learning with Regularized Least Squares (2016, background): “These include the localized learning (Meister and Steinwart, 2016), Nyström regularization (Bach, 2013; Rudi et al., 2015), and online learning (Dekel et al.”
Quantum machine learning: a classical perspective (2017, methodology): “regularization methods for kernel-regularized least squares [22,29,76] (see §3) achieve the optimal learning rate of =O(N−1/2) while requiring only Õ(N2) operations.”
Convergence rates for a class of estimators based on Stein’s method (2016, methodology): “aylor and Cristianini, 2004). In addition there is an active research eort to obtain computationally ecient approximations to kernel matrix inverses, with extremely promising results emerging (e.g. Rudi et al., 2015). All of these methods can be used in combination with control functionals and could”
Learning with SGD and Random Features (2018, methodology): “Using Assumption 3 (see also Remark 1), we derive Lemma 5 in [26]).”
Globally Convergent Newton Methods for Ill-conditioned Generalized Self-concordant Losses (2019, methodology): “With probability 1− δ the following methods output an element in LinApprox(Hλ(x), b, ρ), inO(Q(2)d+Q(3) +c) time, O(Q(2) +d) space: (a) Subsampling with uniform sampling (see [27, 28]), where Q = O(ρ−2a/λ log 1 λδ ) and c = O(1).”
Hybrid Random Features (2021, methodology): “Several other techniques such as Nyström method (Yang et al., 2012; Williams & Seeger, 2000; Rudi et al., 2015) were proposed to construct data-dependent feature representations.”