PaperlayerView exact revision on arXiv

Source-linked AI summary

ReLU Deep Neural Networks and Linear Finite Elements

Juncai He, Lin Li, Jinchao Xu, Chunyue Zheng

arXiv:1807.03973v2math.NA

TL;DR

The paper asks how ReLU DNNs represent CPWL and finite element functions, including the neurons and depth required. It develops FEM-based and general constructions, proves depth bounds, and illustrates PDE use; the general neuron estimate can nevertheless be extremely large.

  • Problem

    The paper studies how many neurons and hidden layers are needed for ReLU DNNs to represent given CPWL functions, including finite element functions.

  • Method

    The paper analyzes nodal-basis representations for simplicial finite elements, general CPWL constructions, and ReLU-based Galerkin discretizations for PDEs.

  • Results

    ⌈log2(d + 1)⌉ hidden layers are optimal for 1 ≤ d ≤ 3, while sufficiently deep ReLU DNNs reproduce all linear finite element functions.

  • Takeaways & Limitations

    The FEM–ReLU relationship supports ReLU DNN representation of finite element functions and motivates their use in numerical PDE approximation.

  • Takeaways & Limitations

    The general representation estimate is rough and may yield extremely large networks; optimality of the depth bound for d > 3 remains open.

Abstract

from arXiv · show

In this paper, we investigate the relationship between deep neural networks (DNN) with rectified linear unit (ReLU) function as the activation function and continuous piecewise linear (CPWL) functions, especially CPWL functions from the simplicial linear finite element method (FEM). We first consider the special case of FEM. By exploring the DNN representation of its nodal basis functions, we present a ReLU DNN representation of CPWL in FEM. We theoretically establish that at least $2$ hidden layers are needed in a ReLU DNN to represent any linear finite element functions in $Ω\subseteq \mathbb{R}^d$ when $d\ge2$. Consequently, for $d=2,3$ which are often encountered in scientific and engineering computing, the minimal number of two hidden layers are necessary and sufficient for any CPWL function to be represented by a ReLU DNN. Then we include a detailed account on how a general CPWL in $\mathbb R^d$ can be represented by a ReLU DNN with at most $\lceil\log_2(d+1)\rceil$ hidden layers and we also give an estimation of the number of neurons in DNN that are needed in such a representation. Furthermore, using the relationship between DNN and FEM, we theoretically argue that a special class of DNN models with low bit-width are still expected to have an adequate representation power in applications. Finally, as a proof of concept, we present some numerical results for using ReLU DNNs to solve a two point boundary problem to demonstrate the potential of applying DNN for numerical solution of partial differential equations.

1 Introduction

The paper analyzes how ReLU DNNs represent CPWL functions, focusing on simplicial finite element functions, neuron counts, and minimal depth. It also connects these representations to quantized networks and numerical PDE approximation.

  • Motivation: ReLU DNNs represent continuous piecewise linear functions on polyhedral subdomains, and the paper studies the converse representation problem.The analysis focuses on mathematical properties of ReLU-based DNN models.
  • Research questions: At most ⌈log2(d + 1)⌉ hidden layers suffice to represent every CPWL function in R^d.This result motivates the paper’s questions about required neurons and minimal depth.
  • General CPWL representation: O(d^2m m!) neurons may be required to represent a CPWL function on m subdomains.The paper derives explicit neuron estimates by examining the general representation proof.
  • Finite element functions: Linear finite element functions can be represented with at most O(dκ^dN) neurons and O(d) hidden layers, where κ ≥ 2 depends on mesh shape regularity.The construction exploits nodal basis functions on simplicial partitions rather than the more complicated lattice-based partition.
  • Minimal depth: At least 2 hidden layers are needed for arbitrary linear finite element functions in Ω⊂R^d when d ≥ 2.The paper shows that the bound ⌈log2(d + 1)⌉ is optimal for d = 2, 3.
  • Applications: Ternary CNNs receive theoretical justification from the special CPWL representation structure, while ReLU DNN Galerkin methods are applied to numerical PDEs.A one-dimensional boundary-value example compares a ReLU DNN Galerkin method with an adaptive finite element method using the same degrees of freedom.

2 Deep neural network (DNN) generated by ReLU

This section defines ReLU DNNs as compositions of affine maps and componentwise activations, then establishes that their outputs are CPWL functions. It introduces depth-indexed DNN classes and the shallow-network setting.

  • DNN definition: A DNN is built from compositions of linear or affine maps and a nonlinear activation function.The paper represents affine maps as Θ(x) = Wx + b and applies activations componentwise.
  • ReLU architecture: A ReLU DNN with k hidden layers has the form f(x) = Θk ◦ ReLU ◦ Θk−1 ◦ ReLU · · · ◦ Θ1 ◦ ReLU ◦ Θ0(x).The network maps input dimension n0 = d through hidden widths n1, …, nk to the output dimension.
  • CPWL structure: ReLU DNN outputs are continuous piecewise linear functions that are linear on each region of a polyhedral decomposition.This follows because ReLU is CPWL and compositions of CPWL functions remain CPWL.
  • Network classes: DNNJ denotes ReLU networks with J hidden layers and arbitrary positive hidden-layer widths, with size n1 + ··· + nJ.The notation fixes n0 = d and nJ+1 = 1 for scalar-output models.
  • Depth and shallow networks: For J = 0, DNN0 consists of global linear functions, whereas increasing J produces more structured piecewise-linear models.The paper contrasts this space with the one-hidden-layer class generated by ReLU ridge functions.

3 Linear finite element (LFE) function as a DNN

The paper constructs ReLU DNN representations for linear simplicial finite element functions by representing nodal basis functions and combining them. For locally convex grids, the construction gives explicit depth and neuron-count bounds, with extensions and scope conditions for nonconvex supports and shape-regular meshes.

  • Linear simplicial finite element functions are continuous piecewise linear functions defined over a simplicial partition of a bounded domain.
  • Every finite element function is uniquely represented as a linear combination of nodal basis functions, reducing the construction to representing each basis function.The basis function associated with each node is uniquely defined, and finite element functions have one coefficient per degree of freedom.
  • For a locally convex grid, a nodal basis function is constructed from the neighboring elementwise linear functions and represented using ReLU-based minimum operations.The support G(i) of the basis function is assumed convex; the proof treats points inside and outside this support separately.
  • Theorem 3.1 gives a ReLU DNN with at most k = ⌈log2 kh⌉ + 1 hidden layers and O(khN) neurons for N degrees of freedom.The depth follows from recursively splitting minimum operations into a binary-tree structure.
  • For locally convex, shape-regular grids, the construction uses at most O(d) hidden layers, O(κ^dN) neurons, and O(dκ^dN) nonzero parameters.Here κ ≥ 2 depends on the mesh shape-regularity.
  • The representation has O(N) weights and is identified as potentially useful for adaptive mesh-less or vertex-less PDE discretizations.

4 LFE can not be recovered by DNN1 for d ≥2

The paper proves that one-hidden-layer ReLU networks cannot recover all linear finite element functions in dimensions d ≥ 2. Thus, shallow networks may approximate CPWL functions but cannot exactly represent every such function.

  • Theorem 4.1 states that DNN1 cannot recover all linear finite element functions on a bounded domain or on R^d.
  • The proof analyzes discontinuities of gradients for compactly supported finite element basis functions and shows that one-layer ReLU combinations cannot reproduce the required structure.The contradiction arises because the resulting discontinuity set is incompatible with local support.
  • For d ≥ 2, DNN1 cannot recover any piecewise linear function in the stated finite element setting.
  • Shallow ReLU networks remain CPWL and can approximate any CPWL function arbitrarily accurately, but some CPWL functions cannot be represented exactly.A compactly supported local FEM basis function is given as an example for dimensions greater than two.
  • The paper notes that ⌈log2(d + 1)⌉ is optimal for d = 2, 3.

5 General CPWL as a ReLU DNN

The paper presents a general ReLU DNN construction for continuous piecewise linear functions, combining lattice representations with max-function networks. It bounds depth and estimates network size, while noting a depth–width trade-off.

  • Depth–width trade-off: Compared with the special finite-element construction, the general approach has shallower depth but significantly more neurons.The comparison is between ⌈log2(d + 1)⌉ hidden layers and ⌈log2 κ_h⌉ + 1 hidden layers.
  • Construction: M subdomains satisfy m ≤ M ≤ m!, reflecting the possible ascending-order rearrangements of m local linear functions.Each subdomain is associated with an ordering pattern, and there are at most m! such patterns.
  • General representation: A general CPWL function on m subdomains can be represented by a ReLU DNN using a lattice representation of local linear pieces.The construction partitions subdomains by the ordering of local linear functions and combines max operations.
  • Depth bound: ⌈log2(d + 1)⌉ hidden layers suffice to represent any CPWL function in R^d.The construction reduces max operations to groups involving at most d + 1 linear functions before assembling the network.
  • Size estimate: p ≤ (2m − 1)M(2^(d+1) − 1)^(m−d−1) bounds the number of max terms after reducing groups to cardinality at most d + 1.Each reduction can expand one max term into at most 2^(d+1) − 1 terms.
  • Depth–width trade-off: The shallow construction may require extremely many neurons because its size depends on the numbers of subdomains and distinct pieces.The authors characterize the estimate as rough but informative.

6 Low bit-width DNN models

The paper studies whether low bit-width ReLU DNNs retain sufficient representation power. It argues that a special architecture with quantized parameters can represent continuous piecewise linear functions.

  • Motivation: The paper investigates why low bit-width DNNs can work for classification and detection despite parameter quantization.The discussion connects representation theory with existing low bit-width models.
  • Quantization context: The paper relates its result to quantization strategies that restrict parameters to zeros or powers of two.The set Q_k,l is defined as a finite collection of quantized parameter values.
  • Observed behavior: 6-bit models work almost the same as classical models in the reported discussion.The passage presents this as an empirical observation motivating the theoretical analysis.
  • Architecture: The construction uses at most one general layer, while the remaining layers have low bit-width parameters.This provides the stated theoretical explanation for the representation capacity of the special low bit-width class.
  • Representation result: Any continuous piecewise linear function can be represented by a ReLU DNN whose layers after the first use parameters from Q_0,3.The architecture requires J ≥ ⌈log2(d + 1)⌉ and leaves the initial fully connected layer unrestricted.

7 Application to Numerical PDEs

The paper examines DNNs for numerical PDE solution and compares their grid-based and point-free formulations with finite element approaches. A one-dimensional experiment demonstrates potential advantages over uniform and adaptive FEM solutions.

  • DNN formulations: The DNN-Galerkin method formulates PDE solution through a Galerkin energy-minimization problem over a DNN function class.This contrasts with collocation, which minimizes a least-squares objective at collocation points.
  • Finite element baselines: Adaptive finite element methods refine or coarsen grids, whereas moving-grid methods relocate points while preserving grid topology and point count.Both approaches optimize the underlying finite element mesh rather than eliminating it.
  • Limitations: Theoretical error estimates for DNN methods remain incomplete, including unclear H1 approximation properties for DNN1 and an open question for general activations or ReLU.The cited discussion also notes dimension dependence in some constants and limited asymptotic theory for moving-grid methods.
  • Method comparison: DNN-based numerical methods require no grids, unlike adaptive and moving-grid finite element methods.The DNN-Galerkin formulation goes further than meshless methods by requiring no discretization points.
  • Numerical example: The experiment compares uniform-grid, AFEM, and DNN solutions using energy and H1 semi-norm error.Figure 7.1 visualizes the AFEM and DNN grid points on the same graph and shows their movement.
  • Numerical example: In the one-dimensional experiment, DNN energy and H1 semi-norm values are reported as smaller than those of AFEM and uniform FEM solutions.The experiment uses the same degrees of freedom after constructing the DNN solution from an adaptively generated grid.

8 Conclusion

The paper relates ReLU DNNs to CPWL and linear finite element functions, giving two representation approaches with different depth–width trade-offs. It also establishes layer-count results, discusses low-bit-width models, and reports preliminary PDE evidence.

  • ReLU DNNs with sufficiently many layers, at least two, can reproduce all linear finite element functions.
  • Two approaches represent CPWL functions: one yields ⌈log2(d + 1)⌉ hidden layers with more neurons, while the other uses ⌈log2 kh⌉ + 1 hidden layers.
  • Further work is needed to combine the two CPWL representation approaches.
  • The paper discusses low-bit-width ReLU DNNs and their potential use in numerical PDE solution, while identifying computational cost as a serious issue.
  • ⌈log2(d + 1)⌉ hidden layers is optimal for 1 ≤ d ≤ 3, while optimality for d ≥ 4 remains open.

A Lattice representation

The lattice representation constructs a CPWL function from local linear pieces over domain partitions, using maxima of auxiliary functions. A convex-region formulation reduces reliance on unique-order partitions but the number of regions can still be large.

  • A unique-order region partition fixes the ordering of local linear functions within each subdomain, enabling pointwise comparisons through a path parameter.
  • For each subdomain, auxiliary functions are constructed to equal the target linear piece there and remain below the CPWL function elsewhere.
  • Taking the maximum over the auxiliary functions recovers the target CPWL function.
  • The representation uses subsets s_k with |s_k| ≤ m, and the number of auxiliary functions depends on the domain partition.
  • The unique-order representation may require too many regions, motivating partitions into convex regions as an improvement.

B Proof of Lemmas

This section presents proofs of the lemmas used in the preceding sections.

  • The section contains proofs of lemmas used in previous sections.

B.1 Proof of Lemma 5.2

The proof establishes an identity for combining maxima of piecewise linear expressions across parameter regimes. This identity supports the lattice-based representation arguments.

  • The proof considers the parameter regimes α > 1, 0 < α < 1, and α < 0 when establishing the key identity.
  • The key identity rewrites max{f, g, αg + h} as a signed combination of three maxima involving f, g, h, and related expressions.
  • The coefficients σ_k in the identity take values in {1, −1}, and the barred term is selected from the listed expressions.

B.2 Proof of Lemma 5.3

The proof reduces maxima of affine functions by eliminating one linear term at a time, then applies an inductive construction to represent maxima with ReLU DNNs. The resulting representation uses at most 2n+1−1 terms, while combining m subnetworks adds logarithmic depth and controlled size.

  • Term reduction: The proof assumes at most n linearly independent coefficient vectors among the affine functions and selects an independent subset without loss of generality.The independent vectors are denoted ā1,…,ān̄ with n̄≤n.
  • Term reduction: Each elimination produces three expressions, one already in the desired form and two requiring the same reduction procedure recursively.The recursion continues until the remaining expression contains only a constant, which is then combined with c0.
  • Term reduction: 2n+1−1 terms are gained at most because the proof has η≤n and repeatedly reduces the maximum expression.The desired form takes the maximum over L−1 linear functions and one constant.
  • ReLU DNN construction: The inductive DNN construction splits m functions into two groups, represents each group recursively, and combines their outputs through a two-layer ReLU realization of max{x,y}.The resulting depth is at most max{k1,…,km}+⌈log(m)⌉+1, with size at most s1+···+sm+4(2m−1).
  • ReLU DNN construction: Because max{x,y} has a two-layer ReLU DNN representation of size 4, the construction yields depth at most max{k1,…,km}+⌈log(m)⌉+1.Its size bound is s1+···+sm+4(2m−1).
Loading 1807.03973v2…