On the Equivalence between Kernel Quadrature Rules and Random Feature Expansions

By Francis R. Bach. 2015

325 citations recorded by the source corpus.

We show that kernel-based quadrature rules for computing integrals can be seen as a special case of random feature expansions for positive definite kernels, for a particular decomposition that always exists for such kernels. We provide a theoretical analysis of the number of required samples for a given approximation error, leading to both upper and lower bounds that are based solely on the eigenvalues of the associated integral operator and match up to logarithmic terms. In particular, we show that the upper bound may be obtained from independent and identically distributed samples from a specific non-uniform distribution, while the lower bound if valid for any set of points. Applying our results to kernel-based quadrature, while our results are fairly general, we recover known upper and lower bounds for the special cases of Sobolev spaces. Moreover, our results extend to the more general problem of full function approximations (beyond simply computing an integral), with results in L2- and L$\infty$-norm that match known results for special cases. Applying our results to random features, we show an improvement of the number of random features needed to preserve the generalization guarantees for learning with Lipschitz-continuous losses.

Subfields: Artificial Intelligence, Numerical Analysis, 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 Numerical Analysis

In Statistical Learning Theory

Citations in the corpus

Kernel Mean Embedding of Distributions: A Review and Beyonds (2016, background): “A detailed exposition on this connection is also given in Section 2.1 of Bach (2015).”
The hardness of conditional independence testing and the generalised covariance measure (2018, background): “For example, taking the first-order Sobolev kernel shows that it is enough that the conditional expectations are Lipschitz when dZ = 1, P(Z ∈ [0,1]) = 1 and the marginal density of Z is bounded above [1].”
Convergence guarantees for kernel-based quadrature rules in misspecified settings (2016, methodology): “Because of this nice property, kernel quadratures have been studied extensively in recent years [7, 3, 5, 2, 17] and have started to find applications in machine learning and statistics [23, 14, 12, 6].”
SGD Learns the Conjugate Kernel Class of the Network (2017, background): “Several previous papers [24, 10, 28, 27, 25, 32, 18, 26, 6, 5, 16, 2] investigated such associations, but in a more restricted settings (i.”
Implicit Bias of Gradient Descent for Wide Two-layer Neural Networks Trained with the Logistic Loss (2020, unknown): “This assumption is satisﬁed by ReLU and S-ReLU networks (Bach, 2017a) as soon as x i (cid:54) = x i (cid:48) , ∀ i (cid:54) = i (cid:48) .”
Learning with SGD and Random Features (2018, background): “1 (see also [8, 20] and references therein).”
Spectral-Pruning: Compressing deep neural network via spectral analysis (2018, methodology): “It is basically proven using the techniques developed by [46] in which theories of the kernel quadrature rule developed by [3] are used for deep learning analysis.”
Gaussian Processes and Kernel Methods: A Review on Connections and Equivalences (2018, background): “(77) Kernel quadrature with quadratic weight regularization has also been studied by Bach [2017], who pointed out such regularization is equivalent to assuming the existence of additive noises in the function values.”
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”
Randomized numerical linear algebra: Foundations and algorithms (2020, background): “6.5); see also Bach (2017).”
Convergence of Adversarial Training in Overparametrized Neural Networks (2019, unknown): “Following the previous work [5, 4], we consider the initialization of each w r with the uniform distribution on the surface of the sphere of radius √ d in this section.”
Spurious Valleys in One-hidden-layer Neural Network Optimization Landscapes (2019, methodology): “The proof is then concluded by applying an Hoeffding’stype inequality to get property 2. if it holds ρ ∈ L∞(Sn dτ) or by applying Proposition 1 in (Bach, 2017b) to obtain property 1.”
Group Invariance, Stability to Deformations, and Complexity of Deep Convolutional Representations (2017, unknown): “In contrast, other kernel approximations such as random Fourier features (Rahimi and Recht, 2007) do not provide points in the RKHS (see Bach, 2017), and their eﬀect on the functional space derived from the multilayer construction is unclear.”
A Theoretical Analysis of Deep Q-Learning (2019, unknown): “d ω∼N(Id/d) be two independent random variables and let µdenote their joint distribution. Then the random feature φ(·,·;β,ω) induces a reproducing kernel Hilbert space H(Rahimi and Recht, 2008, 2009; Bach, 2017) with kernel K: (S×A)×(S×A) →Rgiven by K (s,a),(s′,a′) = Eµ φ(s,a;β,ω)⊤φ(s,a;β,ω) = Eω 1{”