Fast Approximation and Estimation Bounds of Kernel Quadrature for Infinitely Wide Models

Sho Sonoda

TL;DR

This paper introduces a novel "General Kernel Quadrature" (GKQ) method to efficiently approximate and estimate parameters in infinitely wide neural networks. GKQ offers faster convergence rates than existing methods, leading to a new, more refined complexity measure for these models that better reflects their generalization performance.

What Problem Does This Paper Address?

Deep learning models, particularly in the over-parameterized regime, achieve impressive generalization performance. However, understanding why they generalize so well, especially in the context of infinitely wide networks, remains a theoretical challenge. These infinitely wide models can be viewed as weighted integrations of feature maps, where the weights form a distribution. Traditional methods for approximating these integrals and estimating the parameter distribution have limitations, either in their convergence speed or their ability to capture the model's complexity effectively. This paper aims to bridge this gap by developing a more efficient kernel quadrature method for these infinite-dimensional models.

Methods

The core contribution is the General Kernel Quadrature (GKQ). This method extends existing kernel quadrature techniques to handle signed, complex, or vector-valued parameter distributions, which are more general than simple probability measures. GKQ leverages the Kernel Mean Embedding (KME) and Maximum Mean Discrepancy (MMD) to define a metric on these parameter distributions. The approximation problem is then framed as a convex optimization problem solved using a Conditional Gradient (CG) algorithm.

The paper also proposes two practical implementations:

  • Empirical KME (EKQ): This approach uses an empirical estimate of the KME, connecting GKQ to empirical risk minimization (ERM).
  • Unitary Kernel Quadrature (UKQ): This method uses a "unitary kernel" that induces a geometry on the parameter space, making it robust to the non-injectivity of the model's mapping from parameter distributions to functions. This is particularly relevant for neural networks where multiple parameter distributions can map to the same function.

Datasets

Not discussed in the paper. The experiments are conducted using synthetic data generated from a sinusoidal curve with Gaussian noise.

Key Insights and Ideas

  • Parameter Distributions as the Core: The paper frames infinitely wide models not just as having many parameters, but as being defined by a distribution of parameters, allowing for a more principled theoretical treatment.
  • GKQ for Faster Convergence: By adapting kernel quadrature to vector-valued measures and using a CG approach, GKQ achieves faster approximation rates (e.g., $O(e^{-p})$) than traditional methods like Barron's rate ($O(1/\sqrt{p})$).
  • New Complexity Measure: The KME of the parameter distribution, $||K[\mu^0]||_K$, serves as a novel and sharper complexity measure for infinitely wide models compared to existing measures like the total variation norm. This measure is shown to be more directly related to generalization performance.
  • Unitary Kernel for Non-Injectivity: The introduction of the unitary kernel is a clever way to handle the inherent non-injectivity of many infinite-width models (like neural networks), ensuring that the metric space accurately reflects the function space.

Key Results

  • Approximation Rate: GKQ achieves an approximation rate of $O(e^{-p})$ with respect to the number of parameters $p$, which is faster than the traditional $O(1/\sqrt{p})$ rate.
  • Estimation Rate: The method achieves an estimation rate of $O(1/n)$ with respect to the sample size $n$.
  • Complexity Measure: A new norm-based complexity measure, $||K[\mu^0]||_K$, is introduced, which is shown to be sharper than previous measures and directly relates to generalization error.
  • Empirical Validation: Experiments show that the UKQ method (a practical implementation of GKQ) achieves faster error decay than a baseline method (SIR), aligning with the theoretical $O(1/p)$ rate compared to $O(1/\sqrt{p})$.

Limitations and Future Work

  • Theoretical Focus: The paper is primarily theoretical, with experimental validation on synthetic data. Applying the methods to real-world, complex datasets would be a natural next step.
  • Assumptions: The theoretical results rely on certain assumptions about the feature map and the parameter distribution (e.g., kernel moment conditions). Investigating the impact of violating these assumptions would be valuable.
  • Choice of Kernels: The performance of GKQ and its variants depends on the choice of kernels. Exploring optimal kernel selection strategies for different model architectures and data distributions is an open area.
  • Broader Impact: The authors state that the "Broader Impact" section is not applicable due to the theoretical nature of the study, suggesting that direct societal implications are not the primary focus.

Summary updated

Abstract

An infinitely wide model is a weighted integration ∫φ(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 ∫f(x)dp(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 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.
BibTeX
@misc{sonoda2019fast,
  author = {Sho Sonoda},
  title = {{Fast Approximation and Estimation Bounds of Kernel Quadrature for Infinitely Wide Models}},
  year = {2019},
  eprint = {1902.00648},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1902.00648},
}
Figure