Generalization Properties of Learning with Random Features

By Alessandro Rudi, Lorenzo Rosasco. 2016

382 citations recorded by the source corpus.

We study the generalization properties of ridge regression with random features in the statistical learning framework. We show for the first time that $O(1/\sqrt{n})$ learning bounds can be achieved with only $O(\sqrt{n}\log n)$ random features rather than $O({n})$ as suggested by previous results. Further, we prove faster learning rates and show that they might require more random features, unless they are sampled according to a possibly problem dependent distribution. Our results shed light on the statistical computational trade-offs in large scale kernelized learning, showing the potential effectiveness of random features in reducing the computational complexity while keeping optimal generalization properties.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Statistical Learning Theory

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 Computer Vision and Pattern Recognition

In Statistical Learning Theory

Citations in the corpus

Orthogonal Random Features (2016, methodology): “In this paper, we focus on approximating Gaussian kernels following the seminal Random Fourier Features (RFF) framework [19], which has been extensively studied both theoretically and empirically [26, 20, 23].”
Randomness in neural networks: an overview (2017, background): “in 2016.(54) The latter work also puts forth the idea that randomization can serve as a form of ‘computational regularization’ during the training process.”
Asymptotic learning curves of kernel methods: empirical data versus teacher–student paradigm (2020, background): “With this assumption β does not depend on d (for instance in [8] β = 1/2 is guaranteed).”
Randomized numerical linear algebra: Foundations and algorithms (2020, background): “For example, see (Sriperumbudur and Szabo 2015, Rudi and Rosasco 2017, Ullah, Mianjy, Marinov and Arora 2018, Szabo and Sriperumbudur 2019, Wang 2019).”
Beyond Least-Squares: Fast Rates for Regularized Empirical Risk Minimization through Self-Concordance (2019, positive): “Use Proposition 3 of [28] and proceed as in the proof of Proposition 6 of [28] except that we bound Tr(Q−1 λ Q) 6 F∞(λ) instead of bounding Tr(Q−1 λ Q) 6 Tr(Q) λ , we find this result.”
Asymptotic learning curves of kernel methods: empirical data v.s. Teacher-Student paradigm (2019, background): “With this assumption β does not depend on d (for instance in [Rudi and Rosasco, 2017] β = 1 / 2 is guaranteed).”
Domain Generalization by Marginal Transfer Learning (2017, methodology): “We have not presented a generalization error bound for the learning algorithm using random Fourier features (Rudi and Rosasco, 2017).”
Learning with SGD and Random Features (2018, methodology): “A ridge regression framework is considered in [8], where it is shown that it is possible to achieve optimal statistical guarantees with a number of random features in the order of p n.”
Exponential convergence of testing error for stochastic gradient methods (2017, neutral): “…but we have experimented with unregularized recursions, which do exhibit fast convergence, but for which proofs are usually harder (Dieuleveut and Bach, 2016); ﬁnally, (d) in order to avoid the O ( n 2 ) complexity, extending the results of Rudi et al. (2017); Rudi and Rosasco (2017)”
Reconciling modern machine learning and the bias-variance trade-off (2018, neutral): “Some statistical analyses of RFF suggest choosing N ∝ √ n log n to obtain good test risk guarantees [19].”
On the Inductive Bias of Neural Tangent Kernels (2019, background): “We note that while such smoothness properties apply to the functions in the RKHS of the studied limiting kernels, the neural network functions obtained at finite width and their linearizations around initialization are not in the RKHS and thus may not preserve such smoothness properties, despite pre”
Limitations of Lazy Training of Two-layers Neural Networks (2019, neutral): “An incomplete list of references includes [4, 2, 5, 6, 22].”