Uniform approximation of functions with random bases

By Ali Rahimi, B. Recht. 2008

305 citations recorded by the source corpus.

Random networks of nonlinear functions have a long history of empirical success in function fitting but few theoretical guarantees. In this paper, using techniques from probability on Banach Spaces, we analyze a specific architecture of random nonlinearities, provide Linfin and L2 error bounds for approximating functions in Reproducing Kernel Hilbert Spaces, and discuss scenarios when these expansions are dense in the continuous functions. We discuss connections between these random nonlinear networks and popular machine learning algorithms and show experimentally that these networks provide competitive performance at far lower computational cost on large-scale pattern recognition tasks.

Subfields: Artificial Intelligence, Computational Mechanics, Numerical Analysis

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 Computational Mechanics

In Numerical Analysis

Citations in the corpus

Optimal Rates for Random Fourier Features (2015, background): “We also propose a RFF approximation to derivatives of a kernel with a theoretical study on its approximation quality.”
Differentially Private Empirical Risk Minimization (2009, neutral): “The paper of Rahimi and Recht (2008a) has more examples of transforms for other kernel functions.”
Stein Variational Gradient Descent as Moment Matching (2018, background): “In fact, one can show that F ∞ is a dense subset of H p (Rahimi & Recht, 2008) and is hence quite rich if k ( x , x (cid:48) ) is set to be universal.”
Local Group Invariant Representations via Orbit Embeddings (2016, result): “Similar to [29], for C > 0, we define Fp an infinite dimensional space to approximate HK (see [33] for a motivation for this approximation):”
On the Power and Limitations of Random Features for Understanding Neural Networks (2019, methodology): “The technique of random features was proposed and formally analyzed in [27, 28, 29], originally as a computationally-efficient alternative to kernel methods (although as a heuristic, it can be traced back to the “random connections” feature of Rosenblatt’s Perceptron machine in the 1950’s).”
Local Receptive Fields Based Extreme Learning Machine (2015, background): “…arrive the lowest level, Hidden nodes can be generated according to some continuous probability distributions which are denser around some input nodes while sparser farther away, which naturally results in local receptive fields. may 2015 | IEEE ComputatIonal IntEllIgEnCE magazInE 23 primary…”
Explicit Approximations of the Gaussian Kernel (2011, methodology): “We are not aware of any comparison of the Fourier features with the Taylor features, beyond a passing mention by Rahimi and Recht [2008] that the number of Taylor features required for good approximation grows rapidly.”
Computational Science and Engineering (2019, unknown): “Extreme learning machines and random feature models are examples of such approaches [ 19 , 10 ].”
Neural Operator: Learning Maps Between Function Spaces (2021, background): “, 1989) and related results for random feature methods (Rahimi and Recht, 2008); empirically, they have been used to speed up convolutional neural networks (Mathieu et al.”
Proving the Lottery Ticket Hypothesis: Pruning is All You Need (2020, unknown): “Here we show that the answer is negative, and in fact pruning entire neurons is equivalent to the well known random features model (e.g. [25], [26]).”
A comparative analysis of optimization and generalization properties of two-layer neural network and random feature models under gradient descent dynamics (2019, result): “As shown in [23], Hπ is exactly the RKHS with the kernel defined by k(x,x′) = Eπ[σ(wx)σ(wx)].”
Coded Computing for Federated Learning at the Edge (2020, methodology): “RFF was proposed in (Rahimi & Recht, 2008a) to address this problem by explicitly constructing finite-dimensional random features from the data such that inner products between the random features approximate the kernel functions.”
Convergence of Adversarial Training in Overparametrized Neural Networks (2019, unknown): “C Proof of Gradient Descent Finding Robust Classiﬁer in Section 5 C.1 Proof of Theorem 5.2 As discussed in Section 5, we will use the idea of random feature [37] to approximate g ∈ H ( K σ ) on the unit sphere.”