Fast Approximation and Estimation Bounds of Kernel Quadrature for Infinitely Wide Models
This work provides a new complexity measure for infinitely wide models, which is incremental as it builds on kernel quadrature techniques to improve theoretical bounds in deep learning.
The authors tackled the problem of approximating expectations in infinitely wide models by developing a general kernel quadrature method for parameter distributions, achieving a fast approximation rate of O(e^{-p}) with parameter number p and an estimation rate of ̃O(1/n) with sample size n.
An infinitely wide model is a weighted integration $\int \varphi(x,v) d μ(v)$ of feature maps. This model excels at handling an infinite number of features, and thus it has been adopted to the theoretical study of deep learning. Kernel quadrature is a kernel-based numerical integration scheme developed for fast approximation of expectations $\int f(x) d p(x)$. In this study, regarding the weight $μ$ as a signed (or complex/vector-valued) distribution of parameters, we develop the general kernel quadrature (GKQ) for parameter distributions. The proposed method can achieve a fast approximation rate $O(e^{-p})$ with parameter number $p$, which is faster than the traditional Barron's rate, and a fast estimation rate $\widetilde{O}(1/n)$ with sample size $n$. As a result, we have obtained a new norm-based complexity measure for infinitely wide models. Since the GKQ implicitly conducts the empirical risk minimization, we can understand that the complexity measure also reflects the generalization performance in the gradient learning setup.