ReLU deep neural networks from the hierarchical basis perspective

Juncai He, Lin Li, Jinchao Xu

TL;DR

This paper bridges the gap between deep neural networks (DNNs) with ReLU activation and the hierarchical basis method from finite element methods (FEM). The authors demonstrate that ReLU DNNs approximating quadratic functions like $x^2$ and $xy$ are essentially compositions of hierarchical basis approximations, offering a new geometric interpretation and simplifying proofs for existing results. This connection leads to tighter error bounds for polynomial approximation and an elegant method to represent linear finite element functions using shallow ReLU DNNs.

What Problem Does This Paper Address?

Deep neural networks (DNNs), particularly those using the Rectified Linear Unit (ReLU) activation, have shown remarkable success in various fields. While their universal approximation ability is known, a deep theoretical understanding of their structure and approximation capabilities, especially concerning the role of depth, is still an active area of research. Specifically, existing work has established that ReLU DNNs can approximate complex functions, but the underlying mechanisms and the precise relationship between network architecture and approximation power are not fully understood. This paper aims to shed light on this by connecting ReLU DNNs to the well-established hierarchical basis method in finite element analysis, a field known for its rigorous approximation theory. The authors seek to provide a new perspective on why and how ReLU DNNs achieve their approximation power, particularly for polynomial functions.

Methods

The core of this paper lies in establishing a connection between ReLU DNNs and the hierarchical basis method. The authors achieve this by:

  • Decomposing ReLU DNNs: They show that the approximation of functions like $x^2$ and $xy$ by specific ReLU DNN architectures can be viewed as a composition of hierarchical basis approximations.
  • Geometric Interpretation: This connection provides a geometric interpretation for how ReLU DNNs approximate these functions, moving beyond purely algebraic derivations.
  • Finite Element Interpolation: They leverage concepts from finite element methods, specifically nodal basis functions and piecewise linear interpolation, to construct and analyze ReLU DNNs.
  • Hierarchical Basis Functions: The paper utilizes and analyzes specific hierarchical basis functions, particularly the non-local basis function $g_l(x)$, which plays a crucial role in bridging the gap.
  • Network Architectures: They analyze both standard ReLU DNNs and a ResNet-type architecture with skip connections, exploring how these structures relate to the hierarchical basis.
  • Explicit Construction: A significant contribution is the explicit construction of ReLU DNNs that can represent linear finite element functions, demonstrating a powerful capability of shallow networks.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and approximation properties of functions, not on training or evaluating on specific datasets.

Key Insights and Ideas

  • ReLU DNNs as Compositions of Hierarchical Basis Approximations: The most significant insight is that ReLU DNNs approximating $x^2$ and $xy$ are not just arbitrary function approximators but are, in essence, compositions of hierarchical basis approximations. This provides a powerful new lens through which to understand their behavior.
  • Geometric Understanding of Approximation: The hierarchical basis perspective offers a geometric intuition for how ReLU DNNs achieve their approximation capabilities, particularly for quadratic functions.
  • Limited Scope for Exponential Approximation: The paper suggests that this specific ReLU DNN structure, when connected to hierarchical basis, is particularly well-suited for approximating quadratic functions exponentially, implying limitations for approximating higher-order polynomials with the same efficiency.
  • Shallow Networks for Finite Element Functions: A surprising and important result is the demonstration that linear finite element functions on a uniform mesh can be represented by ReLU DNNs with just two hidden layers. This is a significant finding as it provides an explicit and concise construction for a class of functions that are typically considered complex to represent.
  • Bridging Theory and Practice: The work establishes a concrete link between theoretical approximation theory (FEM) and the practical architecture of deep learning models (ReLU DNNs), potentially paving the way for more principled network design and analysis.

Key Results

  • Approximation of $x^2$ and $xy$: The paper shows that ReLU DNN approximations for $s(x) = x^2$ and $m(x, y) = xy$ are composition versions of hierarchical basis approximations.
  • Tighter Error Bounds: By leveraging the hierarchical basis perspective, the authors derive more accurate and tighter error estimations for approximating polynomials with multi-variable ReLU DNNs compared to previous results.
  • Explicit Representation of Linear FEM Functions: An explicit and concise formula is provided to represent any linear finite element function on a 2D uniform mesh using ReLU DNNs with only two hidden layers.
  • Exponential Approximation for Quadratics: The study demonstrates that ReLU DNNs with a specific structure can achieve exponential approximation rates for quadratic functions.

Limitations and Future Work

  • Focus on Specific Functions: The current work primarily focuses on the approximation of $x^2$ and $xy$. While these are foundational for polynomial approximation, extending the results to more general polynomials and functions remains a direction for future work.
  • Specific Network Architectures: The analysis is tied to specific ReLU DNN architectures. Investigating how the hierarchical basis connection extends to other DNN architectures or variations could be fruitful.
  • High-Dimensional and Unstructured Meshes: The paper highlights the potential for extending the representation of finite element functions to high-dimensional and unstructured meshes, which is a challenging but promising area for future research.
  • Applications in PDEs: The authors suggest that the connections established could be valuable for applying ReLU DNNs to numerical solutions of partial differential equations, indicating a significant avenue for future exploration.
  • Curse of Dimensionality: While the paper shows efficient representation of 2D linear finite element functions with shallow networks, the general problem of overcoming the curse of dimensionality for higher-dimensional finite element functions using DNNs is still an open challenge.

Summary updated

Abstract

We study ReLU deep neural networks (DNNs) by investigating their connections with the hierarchical basis method in finite element methods. First, we show that the approximation schemes of ReLU DNNs for $x^2$ and $xy$ are composition versions of the hierarchical basis approximation for these two functions. Based on this fact, we obtain a geometric interpretation and systematic proof for the approximation result of ReLU DNNs for polynomials, which plays an important role in a series of recent exponential approximation results of ReLU DNNs. Through our investigation of connections between ReLU DNNs and the hierarchical basis approximation for $x^2$ and $xy$, we show that ReLU DNNs with this special structure can be applied only to approximate quadratic functions. Furthermore, we obtain a concise representation to explicitly reproduce any linear finite element function on a two-dimensional uniform mesh by using ReLU DNNs with only two hidden layers.
BibTeX
@inproceedings{he2022relu,
  author = {Juncai He and Lin Li and Jinchao Xu},
  title = {{ReLU deep neural networks from the hierarchical basis perspective}},
  booktitle = {Comput. Math. Appl},
  year = {2022},
  url = {https://openreview.net/forum?id=GyPkXg4Sp_},
}
Figure