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 examines how ReLU DNNs represent linear finite element functions and how DNN and adaptive finite element Galerkin methods compare for PDE approximation. It studies these representations and discretizations, establishing that ReLU DNNs with at least two hidden layers can reproduce all linear finite element functions.

  • Problem

    The paper examines the relationship between ReLU DNN representations and linear finite element functions, alongside their comparison for PDE approximation.

    Source: §8 · pp. 36–37

  • Method

    It studies ReLU DNN representations of linear finite element functions and compares DNN and adaptive finite element Galerkin discretizations for PDE approximation.

    Source: §8 · pp. 36–37

  • Results

    At least two hidden layers allow ReLU DNNs to reproduce all linear finite element functions.

    Source: §8 · p. 36

  • Takeaways & Limitations

    The results provide a theoretical explanation of DNN expressive power and the necessity of deep layers.

    Source: §8 · p. 36

    The neuron-count estimate is rough, and network size may be extremely large depending on the numbers of subdomains and distinct pieces.

    Source: §5.2 · p. 26

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 ReLU DNN representations of continuous piecewise linear functions, especially linear finite element functions, establishing layer and neuron bounds and discussing quantized networks and PDE applications.

1 Introduction

  • Every CPWL function in R^d has a ReLU DNN representation with at most ⌈log2(d + 1)⌉ hidden layers [14], and the paper gives explicit neuron-count estimates for m subdomains.The stated upper bound on the neuron count is O(d^2 m m!).Source: §1 · p. 3
  • Representing a linear finite element function with N degrees of freedom requires at most O(dκ^dN) neurons and O(d) hidden layers, with κ≥2 depending on shape regularity.The construction reduces the task to representing nodal basis functions and avoids the more complicated lattice-related domain partition used for general piecewise linear functions.Source: §1 · pp. 3–4
  • At least two hidden layers are necessary to represent any linear finite element function when d≥2; the bound is optimal for d=2,3, while optimality for d>3 remains open.The result applies on a bounded domain Ω⊂R^d or on R^d.Source: §1 · p. 4
  • Using the CPWL representation structure, the authors provide theoretical justification for ternary CNNs and propose modified models with rigorous mathematical justification.The introduction notes prior reports of ternary CNNs matching original CNN accuracy on small datasets such as MNIST and CIFAR-10.Source: §1 · p. 4
  • In a one-dimensional example, a Galerkin method using ReLU DNNs achieves better approximation than adaptive finite elements with the same number of degrees of freedom.This application is motivated by the paper’s FEM–ReLU DNN relationship and discussion of convergence properties.Source: §1 · p. 4

2 Deep neural network (DNN) generated by ReLU

The section defines ReLU DNNs as compositions of affine maps and componentwise activations, establishing that they produce continuous piecewise-linear functions. It also introduces the shallow DNN1 case and notes its universal approximation property as width grows.

2.1 General DNN

  • A general DNN from R^d to R^c composes affine maps Θ_i, where Θ(x) = Wx + b, with a nonlinear activation σ applied componentwise, yielding f(x) = Θ_k ◦ σ ◦ Θ_{k−1} ◦ σ · · · ◦ Θ_1 ◦ σ ◦ Θ_0(x).Source: §2.1 · pp. 5–6
  • Every ReLU DNN is continuous and piecewise linear, with a polyhedral decomposition of its input domain on which it is linear.The paper defines CPWL functions as globally continuous and locally linear on each polyhedron of a finite polyhedral decomposition.Source: §2.1 · p. 6
  • DNNJ denotes ReLU networks with J hidden layers and arbitrary positive widths; DNN0 consists of global linear functions.The paper identifies DNN0 with the function space used in linear regression.Source: §2.1 · p. 7, §2.2 · p. 7

2.2 A shallow neural network DNN1

  • For the shallow DNN1 case, the neuron parameters include αi, bi, β, and wi, with m denoting the number of neurons.The paper notes that DNNm functions generated by these ReLU basis functions have the universal approximation property: they approximate C0(Ω) as m → ∞ and.Source: §2.2 · pp. 7–8

3 Linear finite element (LFE) function as a DNN

This section develops ReLU DNN representations for linear simplicial finite element functions and compares their approximation properties with shallow networks and adaptive FEM. It discusses representation bounds based on mesh-neighborhood size or, for shape-regular grids, dimension, and argues that a special deep ReLU DNN structure can be at least as good as adaptive FEM.

3.1 Linear finite element spaces

  • The finite element space considered consists of continuous piecewise-linear functions on simplicial meshes of a bounded domain, with locally convex grids requiring each nodal basis support to be convex.The representation analysis first focuses on locally convex grids; non-convex supports can require more complicated max-min forms depending on their shape.Source: §3.1 · pp. 9, 11, §3.2 · p. 13

3.2 DNN representation of finite element functions

  • On locally convex grids, any linear finite element function with N degrees of freedom has a ReLU representation with at most ⌈log2 kh⌉+1 hidden layers and O(khN) neurons.The construction represents basis functions through minima of affine pieces, combined using a binary-tree procedure.Source: §3.2 · pp. 13–14
  • For locally convex, shape-regular grids, linear finite element functions admit ReLU representations with O(d) hidden layers, O(κ^dN) neurons, and O(dκ^dN) non-zero parameters.The constant κ ≥ 2 depends on the grid’s shape regularity; the approach also yields O(N) weights for N degrees of freedom.Source: §3.2 · p. 15

3.3 Comparison of error estimates in adaptive finite element and DNN methods

  • Although one-hidden-layer networks cannot generally recover linear finite element functions, they may offer better asymptotic accuracy as dimension grows; the FEM connection yields deep models of depth O(d).For O(N) degrees of freedom, the described deep models use O(dκ^dN) parameters.Source: §3.3 · p. 16
  • A special deep ReLU DNN structure with O(N) degrees of freedom and k_d = O(κ^d) is at least as good as adaptive FEM.Source: §3.3 · p. 16

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

The section proves that one-hidden-layer ReLU DNNs cannot recover all linear finite element functions in dimensions d ≥ 2. It distinguishes approximation from exact representation and notes that the resulting layer bound is optimal for d = 2, 3.

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

  • For bounded Ω or Ω = R^d, one-hidden-layer ReLU DNNs cannot recover all linear finite element functions when d ≥ 2.The proof uses a compactly supported FEM basis function: the gradient of a one-layer ReLU representation changes across finitely many affine hyperplanes, leaving an unbounded set that contradicts compact support.Source: §4 · pp. 17, 18, 20
  • Shallow ReLU DNNs can approximate any CPWL function to arbitrary accuracy but cannot represent some exactly, including certain compactly supported FEM basis functions in dimensions greater than 2.Source: §4 · p. 20
  • The stated upper bound ⌈log2(d + 1)⌉ is optimal for d = 2, 3, given the one-hidden-layer lower bound.Source: §4 · pp. 20–21

5 General CPWL as a ReLU DNN

The section presents a ReLU DNN representation for general CPWL functions with at most ⌈log2(d+1)⌉ hidden layers and estimates its size. It also applies the approach to linear finite element functions, where the shallower representation has many more neurons than the alternative.

5 General CPWL as a ReLU DNN

  • Compared with the special finite-element approach, the general approach yields fewer layers but significantly more neurons.The section introduces the general approach as one previously introduced in [14].Source: §5 · p. 21

5.1 The main result

  • Any CPWL function on R^d can be represented by a ReLU DNN with at most ⌈log2(d+1)⌉ hidden layers, with an estimate of the required network size.The theorem’s depth result is cited as known from [14]; the paper adds a neuron-count estimate, which it describes as rough and potentially extremely large depending on the number of subdomains and distinct pieces.Source: §5.1 · p. 23, §5.2 · p. 26

5.2 On the proof of Theorem 5.2

  • The proof expresses a CPWL function through a lattice representation, then reduces maxima to at most d+1 linear functions to obtain the shallow network.The reduction uses linear transformations; the resulting size can be extremely large as the numbers of subdomains and distinct pieces grow.Source: §5.2 · pp. 24–26

5.3 Linear finite element functions as DNN with ⌈log2(d+1)⌉ hidden layers

  • For a locally convex finite element grid, functions with N degrees of freedom have a representation with at most ⌈log2(d+1)⌉ hidden layers, but many more neurons than the alternative.The comparison representation uses ⌈log2 k_h⌉+1 hidden layers; the section also gives a size bound for the shallower network.Source: §5.3 · p. 28

6 Low bit-width DNN models

The section argues that low-bit-width ReLU DNNs retain representation power: a model with Q0,3 parameters after its initial layer can represent every continuous piecewise function at depth J≥⌈log2(d+1)⌉.

6 Low bit-width DNN models

  • In [17], incremental quantization constrains trained CNN parameters to zeros or powers of two, and a 6-bit model reportedly worked almost the same as the classical model.[17] also describes a projected-gradient method for training an R-FCN model for object detection using a closed-form weight approximation.Source: §6 · pp. 28–29
  • The result identifies a ReLU DNN family with at most one general layer and all other layers low-bit, offering a theoretical explanation and modification of existing low-bit models.The authors connect this family to why low-bit models can work to some extent on classification problems.Source: §6 · p. 29
  • Any continuous piecewise function can be represented by a ReLU DNN whose parameters in layers ℓ≥1 lie in Q0,3, provided J≥⌈log2(d+1)⌉.The initial layer is not subject to the Q0,3 restriction.Source: §6 · p. 29

7 Application to Numerical PDEs

The section compares DNN-based numerical PDE methods with finite element approaches and presents a one-dimensional boundary-value example. It discusses mesh-based methods, a point-free DNN-Galerkin method, and limitations in approximation theory.

7.1 The finite element method

  • Adaptive FEM refines or coarsens meshes and can achieve error estimates with O(N) degrees of freedom, but its convergence rate worsens as dimension increases.The estimate depends on the Sobolev or Besov class containing the solution.Source: §7.1 · pp. 31–32
  • Moving-grid FEM changes grid-point locations while preserving grid topology and point count; it is effective in applications, but few error-estimate theories are available.The section also notes that H1 approximation properties remain unclear for DNN1, and the corresponding question for general activations or ReLU is open.Source: §7.1 · p. 32
  • For DNN1, H1 approximation properties remain unclear, and the question is open for general activations and ReLU.The section contrasts this with a similar H1 error result for DNNm using the activation σ(x) = cos(x).Source: §7.1 · p. 32

7.2 DNN-Galerkin method

  • Unlike meshless methods that still use discretization points, DNN-Galerkin requires neither a grid nor discretization points.The section describes it as the Galerkin version of the DNN-element method.Source: §7.2 · p. 32
  • A Fourier-based DNN error estimate has dimension-dependent constants, and improve this dependence, with making the constant polynomial in d.The estimate concerns one-hidden-layer DNNs and depends on the Fourier transform of an extension of the solution to R^d.Source: §7.2 · pp. 32–33

7.3 An 1D example: a two point-boundary value problem

  • The DNN solution has smaller energy and H1 semi-norm error than both the AFEM and uniform-grid FEM solutions in the one-dimensional example.The experiment starts from an AFEM-adapted grid and uses the same degrees of freedom for the DNN solution; its optimization alternates between grid points and slopes.Source: §7.3 · pp. 34, 36, Table 1 · p. 35

8 Conclusion

The paper relates ReLU DNNs to linear finite element functions to study representational power and layer requirements, compares two CPWL representation approaches, and briefly examines DNNs for PDE approximation. It also identifies open questions about balanced representations and layer optimality in higher dimensions.

8 Conclusion

  • ReLU DNNs with at least two hidden layers can reproduce all linear finite element functions.This connection is presented as a theoretical explanation of DNN expressive power and the need for deep layers.Source: §8 · p. 36
  • The [14] approach yields ⌈log2(d + 1)⌉ hidden layers with more neurons, while this paper's approach yields ⌈log2 kh⌉ + 1 hidden layers.The paper identifies combining the approaches into a more balanced representation as future work.Source: §8 · p. 36
  • The linear finite element representation may help explain and improve quantized-weight applications in convolutional neural networks [17].Source: §8 · p. 36
  • The layer lower bound is 2, making ⌈log2(d + 1)⌉ optimal for 1 ≤ d ≤ 3; its optimality for d ≥ 4 remains open.Source: §8 · pp. 36–37
  • For d = 1 and equal degrees of freedom, DNNs yield a more accurate Galerkin approximation than adaptive finite elements.The comparison excludes computational costs; the preliminary study also compares asymptotic approximation properties for large d and flags computational cost as a serious issue.Source: §8 · p. 37

A Lattice representation

The section constructs lattice representations of continuous piecewise-linear functions by partitioning the domain into regions where the ordering of local linear functions is fixed. It then improves the representation by using convex regions, addressing the potentially large number of unique-order regions.

A Lattice representation

  • The unique-order partition divides the domain into subdomains where the arrangement of the local functions is fixed.Source: A Lattice representation · p. 38
  • The proof constructs functions Φ_k that equal f on their corresponding unique-order regions and satisfy Φ_k(x) ≤ f(x) everywhere; taking their maximum recovers f.The number of Φ_k depends on the domain partition, and each associated subset s_k has size at most m.Source: A Lattice representation · pp. 40–41
  • In a unique-order region, the ordering of local linear functions is fixed, so their order can be compared using a single point in that region.The proof parameterizes a path between points as (x + θ(x′ − x), f(x + θ(x′ − x))) for θ ∈ [0, 1], then invokes Lemma A.1.Source: A Lattice representation · p. 40
  • Because the number of unique-order regions may be too large, the improved theorem partitions the domain into convex regions on which f is described by the same local linear function.When a convex region contains multiple unique-order subsets, its contribution is the maximum of the corresponding Φ_i functions; combining contributions across regions recovers f.Source: A Lattice representation · pp. 41–42

B Proof of Lemmas

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

B Proof of Lemmas

B.1 Proof of Lemma 5.2

The proof verifies identity (5.4) for α < 1 and states a case-based identity (B.2) expressing a maximum as a signed sum of three maxima.

B.1 Proof of Lemma 5.2

  • For α < 1, identity (5.4) always holds.The proof also states that the identity holds for the cases α > 1, 0 < α < 1, and α < 0.Source: §B.1 · p. 43
  • Identity (B.2) writes max{f, g, αg + h} as a signed sum of three maxima, with each σk equal to 1 or −1.The third term uses max{f, ḡ}, where ḡ is one of g, αg + h, or ᾱh.Source: §B.1 · p. 43

B.2 Proof of Lemma 5.3 · B.3 Proof of Lemma 5.4

The proofs reduce maxima of linear functions by eliminating terms, then use an inductive divide-and-conquer construction to represent maxima of multiple functions with ReLU DNNs.

B.2 Proof of Lemma 5.3

  • The Lemma 5.3 proof uses linear independence among at most n coefficient vectors to transform the maximum and eliminate terms recursively.It continues until the final expression contains only a constant.Source: §B.2 · pp. 43, 45
  • The reduction reaches the desired form by taking a maximum over L − 1 linear functions and one constant.The proof identifies this form as (B.7).Source: §B.2 · p. 44
  • Each elimination produces three terms; two are further reduced until constant, and the proof notes η ≤ n.The remaining term is already in the desired form.Source: §B.2 · pp. 45–46

B.3 Proof of Lemma 5.4

  • The Lemma 5.4 proof divides the functions into two groups, represents each group maximum inductively, and combines them as a two-output function.The induction starts with the trivial case m = 1.Source: §B.3 · p. 46
  • A ReLU DNN represents max{x, y} with two layers and size 4, enabling the final maximum operation.The proof applies this construction to the two group maxima.Source: §B.3 · p. 46
  • The passage states a term of ⌈log(m)⌉ + 1 and gives the size bound s1 + ··· + sm + 4(2m − 1).Source: §B.3 · p. 46

Related papers

This paper cites

Loading 1807.03973v2…