Deep Neural Network Approximation of Composition Functions: with application to PINNs

xiliang luarXiv 2023 · DOI · arXiv

TL;DR

This paper introduces a new theoretical framework for approximating functions that are compositions of simpler functions using deep neural networks (DNNs). They demonstrate that these "composition functions" possess an "intrinsic sparse structure" which allows DNNs to overcome the curse of dimensionality, leading to improved approximation accuracy and efficiency, particularly for solving partial differential equations (PDEs) with Physics-Informed Neural Networks (PINNs).

What Problem Does This Paper Address?

Deep neural networks (DNNs) have shown remarkable success in approximating complex functions, but their performance can degrade significantly in high-dimensional spaces, a phenomenon known as the "curse of dimensionality." This is particularly problematic when dealing with functions that are compositions of multiple simpler functions, a common scenario in scientific modeling. Existing approximation theories for DNNs often struggle with these compositional structures, leading to convergence rates that depend unfavorably on the input dimension. This paper aims to bridge this gap by developing a theoretical understanding of how DNNs can efficiently approximate compositional functions, leveraging their inherent structure to mitigate the curse of dimensionality.

Methods

The core of this paper lies in its theoretical analysis of DNN approximation for compositional functions. The authors extend existing DNN approximation theory by employing mathematical induction and the multivariate Faa di Bruno formula. They hypothesize that if each layer in a composition has a "small degree of freedom" (related to its intrinsic dimension), the overall composition function exhibits a sparse structure. This sparsity allows DNNs to achieve approximation rates that depend on this intrinsic dimension rather than the full input dimension.

Specifically, they:

  • Develop an approximation theorem for compositional functions: This theorem establishes that a ReLU-based DNN can approximate a composition of $q$ functions $h_q \circ \dots \circ h_0$ with a convergence rate that depends on the intrinsic dimensions of each $h_i$, rather than the total input dimension $d_0$. The required network width is shown to be related to the maximum intrinsic dimension across layers, and the depth is related to the number of layers and the logarithm of the intrinsic dimensions.
  • Analyze PINNs for compositional solutions: They apply their approximation results to the problem of solving elliptic PDEs using PINNs. By combining their theoretical findings with existing work on the statistical error of PINNs, they derive a convergence rate analysis for PINNs when the exact solution is a compositional function. This analysis shows that PINNs can achieve better convergence rates when the solution has a low intrinsic dimensional structure.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and provides illustrative numerical examples rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Intrinsic Sparsity of Compositional Functions: The key insight is that functions formed by composing simpler functions can possess an "intrinsic sparse structure" if each component function has a low intrinsic dimension. This structure is crucial for efficient approximation.
  • Alleviating the Curse of Dimensionality: By exploiting this intrinsic sparsity, DNNs can achieve approximation rates that are independent of the full input dimension, effectively mitigating the curse of dimensionality. This is a significant theoretical advancement for high-dimensional function approximation.
  • PINNs Benefit from Compositional Structure: The paper demonstrates that PINNs, when applied to PDEs with compositional solutions, can also benefit from this low-dimensional structure, leading to improved convergence rates and reduced computational complexity.
  • Width vs. Intrinsic Dimension: The required network width for accurate approximation is shown to be dependent on the intrinsic dimension of the composition layers, not the full input dimension. This suggests that networks can be more efficiently designed for such problems.

Key Results

  • Approximation Theorem (Theorem 3.1): For a composition of $q$ functions $h_q \circ \dots \circ h_0$, where each $h_i$ is a $t_i$-variate function, a ReLU network can approximate it with $C^{s-1}$ norm error $\epsilon$ using a width dependent on $\max_i [d_{i+1} C_1(t_i, s, \|h_i\|)]$ and a depth dependent on $\sum_{i=0}^q (\log_2 t_i + 2) - q$. This rate is independent of the total input dimension $d_0$.
  • PINNs Convergence Rate (Theorem 4.1): For solving elliptic PDEs with compositional solutions, the expected error of PINNs converges to $\epsilon$ with a sampling size of $O((1/\epsilon)^{4+2t+2\delta})$, a DNN width of $O(1/\epsilon)$, and a depth of $O(\log_2 t)$. This is a significant improvement over methods whose complexity depends on the full dimension $d$.
  • Numerical Examples: The paper includes illustrative examples showing that networks with smaller intrinsic dimensions achieve better convergence and require less width for the same precision, supporting the theoretical findings.

Limitations and Future Work

  • Theoretical Focus: The paper is primarily theoretical, with numerical examples serving to illustrate the concepts rather than provide extensive empirical validation.
  • Assumptions on Smoothness and Norms: The theoretical results rely on specific assumptions about the smoothness of the component functions and their norms. The practical implications of these assumptions in real-world scenarios might require further investigation.
  • Practical Implementation: While the theory suggests efficient network designs, the practical training of such networks and the precise observation of the theoretical relationships (e.g., between width and error) can be influenced by optimization algorithms and sampling strategies, as noted in the paper.
  • Future Work: The authors suggest that their findings can be extended to other types of neural network architectures and to more complex PDE problems. Further exploration of the practical implications of intrinsic sparsity in various scientific domains is also a promising direction.

Summary updated

Abstract

In this paper, we focus on approximating a natural class of functions that are compositions of smooth functions. Unlike the low-dimensional support assumption on the covariate, we demonstrate that composition functions have an intrinsic sparse structure if we assume each layer in the composition has a small degree of freedom. This fact can alleviate the curse of dimensionality in approximation errors by neural networks. Specifically, by using mathematical induction and the multivariate Faa di Bruno formula, we extend the approximation theory of deep neural networks to the composition functions case. Furthermore, combining recent results on the statistical error of deep learning, we provide a general convergence rate analysis for the PINNs method in solving elliptic equations with compositional solutions. We also present two simple illustrative numerical examples to demonstrate the effect of the intrinsic sparse structure in regression and solving PDEs.
BibTeX
@misc{lu2023deep,
  author = {xiliang lu},
  title = {{Deep Neural Network Approximation of Composition Functions: with application to PINNs}},
  year = {2023},
  eprint = {2304.07947},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2304.07947},
}
Figure