Floor-Exponential-Step Activation Function, Continuous Function.

This paper studies the approximation power of neural networks and shows that three hidden layers are enough for neural networks to achieve super approximation capacity. In particular, leveraging the power of advanced yet simple activation functions, we will introduce new theories and network architectures with only three hidden layers achieving exponential convergence and avoiding the curse of dimensionality simultaneously for (Hölder) continuous functions with an explicit approximation bound. The theories established in this paper would provide new insights to explain why deeper neural networks are better than one-hidden-layer neural networks for large-scale and high-dimensional problems. The approximation theories here are constructive (i.e., with explicit formulas to specify network parameters) and quantitative (i.e., results valid for essentially arbitrary width and/or depth without lower bound constraints) with explicit error bounds working for three-hiddenlayer networks with arbitrary width.

Constructive approximation with quantitative results and explicit error bounds would provide important guides for deciding the network sizes in deep learning. For example, the (nearly) optimal approximation rates of deep ReLU networks with width O(N ) and depth O(L) for a Lipschitz continuous function and a C s function f on [0, 1] Shen et al. (2020); Lu et al. (2020), respectively. For results in terms of the number of nonzero parameters, the reader is referred to Yarotsky (2017); Schmidt-Hieber (2020); Petersen and Voigtlaender (2018); Yarotsky (2018); Gühring et al. (2019); Yarotsky and Zhevnerchuk (2020) and the reference therein. Obviously, the curse of dimensionality exists in ReLU networks for these generic functions and, therefore, ReLU networks would need to be exponentially large in d to maintain a reasonably good approximation accuracy. The curse could be lessened when target function spaces are smaller. To name a few, Poggio et al. (2017); Barron and Klusowski (2018);E et al. (2019); Montanelli et al. (2020); Chen et al. (2019a); Hutzenthaler et al. (2020) and the reference therein for ReLU networks. The limitation of ReLU networks motivated the work in Shen et al. (2021) to introduce Floor-ReLU networks built with either a Floor (⌊x⌋) or ReLU (max{0, x}) activation function in each neuron. It was shown by construction in Shen et al. (2021) that Floor-ReLU networks with width max{d, 5N + 13} and depth 64dL + 3 can uniformly approximate a Hölder continuous function f on [0, 1] d with a root-exponential approximation rate 3λd α 2 N -α √ L without the curse of dimensionality, where α ∈ (0, 1] and λ > 0 are the Hölder order and constant, respectively.

The most important message of Shen et al. (2021) (and probably also of Yarotsky and Zhevnerchuk (2020)) is that the combination of simple activation functions can create super approximation power. In the Floor-ReLU networks mentioned above, the power of depth is fully reflected in the approximation rate 3λd α 2 N -α √ L that is root-exponential in depth. However, the power of width is much weaker and the approximation rate is polynomial in width if depth is fixed. This seems to be inconsistent with recent development of network optimization theory Jacot et al. (2018); Du et al. (2019); Mei et al. (2018); Wu et al. (2018); Chen et al. (2019b); Lu et al. (2020); Luo and Yang (2020), where larger width instead of depth can ease the challenge of highly noncovex optimization. The mystery of the power of width and depth remains and it motivates us to demonstrate that width can also enable super approximation power when armed with appropriate activation functions.

In particular, we explore the floor function, the exponential function (2 x ), the step function (1 x≥0 ), or their compositions as activation functions to build fully-connected feed-forward neural networks. These networks are called Floor-Exponential-Step (FLES) networks. As we shall prove by construction, Theorem 1.1 below shows that FLES networks with width max{d, N } and three hidden layers can uniformly approximate a continuous function f on [0, 1] d with an exponential approximation rate 2ω f (2 √ d)2 -N +ω f (2 √ d 2 -N ), where ω f (⋅) is the modulus of continuity defined as ω f (r) ∶= sup f (x) -f (y) ∶ xy 2 ≤ r, x, y ∈ [0, 1] d , for any r ≥ 0.

In particular, there are three kinds of activation functions denoted as σ 1 , σ 2 , and σ 3 in FLES networks (see Figure 1 for an illustration): σ 1 (x) ∶= ⌊x⌋, σ 2 (x) ∶= 2 x , and σ 3 (x) ∶= T (x -⌊x⌋ -1 2 ), for any x ∈ R, where

Theorem 1.1. Given an arbitrary continuous function f defined on [0, 1] d , for any

, where φ is defined by a formula in a 1 , a 2 , ⋯, a N as follows.

We remark that φ in Theorem 1.1 is essentially determined by N parameters a 1 , a 2 , ⋯, a N , which can be trained by a (σ 1 , σ 2 , σ 3 )-activated network with width max{d, N }, three hidden layers, and 2(d + N + 1) nonzero parameters. See Figure 1 for an illustration.

x 1 x 2 . . .

Figure 1: An illustration of the desired three-hidden-layer network in Theorem 1.1 for any x = (x 1 , x 2 , ⋯, x d ) ∈ R. Each of the red functions "σ 1 ", "σ 2 ", and "σ 3 " above the network is the activation function of the corresponding hidden layer. The number of neurons in each hidden layer is indicated by the red number below it.

The rate in ω f (2 √ d 2 -N ) implicitly depends on N through the modulus of continuity of f , while the rate in 2ω f (2 √ d)2 -N is explicit in N . Simplifying the implicit approximation rate to make it explicitly depend on N is challenging in general. However, if f is a Hölder continuous function on [0, 1] d of order α ∈ (0, 1] with a Hölder constant λ > 0, i.e., f (x) satisfying

then ω f (r) ≤ λr α for any r ≥ 0. Therefore, in the case of Hölder continuous functions, the approximation rate is simplified to 3λ(2 √ d) α 2 -αN as shown in the following corollary. In the special case of Lipschitz continuous functions with a Lipschitz constant λ > 0, the approximation rate is simplified to 6λ √ d 2 -N .

Corollary 1.2. Given any Hölder continuous function f on [0, 1] d of order α ∈ (0, 1] with a Hölder constant λ > 0, for any N ∈ N + , there exists a 1 , a 2 , ⋯, a N such that

where φ is defined by a formula in a 1 , a 2 , ⋯, a N as follows.

First, Theorem 1.1 and Corollary 1.2 show that the approximation capacity of three-hidden-layer neural networks with simple activation functions for continuous functions can be exponentially improved by increasing the network width, and the approximation error can be explicitly characterized in terms of the width O(N ). Second, this new class of networks overcomes the curse of dimensionality in the approximation power when the modulus of continuity is moderate, since the approximation order is essentially √ d times a function of N independent of d within the modulus of continuity. Therefore, three hidden layers are enough for neural networks to achieve exponential convergence and avoid the curse of dimensionality for generic functions. The width is also powerful in network approximation.

The rest of this paper is organized as follows. In Section 2, we discuss the application scope of our theory, study the connection between the approximation error and the Vapnik-Chervonenkis (VC) dimension, establish Corollary 2.3 to extend our analysis to general bounded continuous functions on a bounded set, and compare related works in the literature. We will prove Theorem 1.1 and Corollary 2.3 in Section 3. In Section 4, we explore alternative continuous activation functions other than σ 1 , σ 2 , and σ 3 for super approximation power. Finally, we conclude this paper in Section 5.

In this section, we will further interpret our results and discuss related research in the field of neural network approximation.

Let φ(x; θ) denote a function computed by a (fully-connected) network with θ as the set of parameters. Given a target function f , consider the expected error/risk of φ(x; θ)

with a loss function typically taken as (y, y ′ ) = 1 2 yy ′ 2 , where U (X ) is an unknown data distribution over X . For example, when (y,

The expected risk minimizer θ D is defined as

It is unachievable in practice since f and U (X ) are not available. Instead, we only have samples of f . Given samples {(x i , f (x i ))} n i=1 , the empirical risk is defined as

And we usually use it to approximate/model the expected risk R D (θ). The goal of supervised learning is to identify the empirical risk minimizer

to obtain φ(x; θ S ) ≈ f (x). When a numerical optimization method is applied to solve (2), it may result in a numerical solution (denoted as θ N ) that is not a global minimizer. Hence, the actually learned function generated by a neural network is φ(x; θ N ). The discrepancy between the target function f and the actually learned function φ(x; θ N ) is measured by an inference error

where the second equality holds when (y, y ′ ) = 1 2 yy ′ 2 and U is a uniform distribution over X = [0, 1] d .

Since R D (θ N ) is the expected inference error over all possible data samples, it can quantify how good the learned function φ(x; θ N ) is. Note that

≤ 0 by Eq. ( 2)

Approximation error (AE)

Optimization error (OE)

where the inequality comes from the fact that [R S (θ S ) -R S (θ D )] ≤ 0 since θ S is a global minimizer of R S (θ). Constructive approximation provides an upper bound of R D (θ D ) in terms of the network size, e.g., in terms of the network width and depth, or in terms of the number of parameters.

The second term of Equation ( 3) is bounded by the optimization error of the numerical algorithm applied to solve the empirical loss minimization problem in Equation ( 2). Note that one only needs to make R S (θ N ) -R S (θ S ) small, but not θ N -θ S . The study of the bounds for the third and fourth terms is referred to as the generalization error analysis of neural networks. See Figure 2 for the intuitions of these three errors. One of the key targets in the area of deep learning is to develop algorithms to reduce R D (θ N ). The constructive approximation established in this paper and in the literature provides upper bounds of the approximation error R D (θ D ) for several function spaces, which is crucial to estimate an upper bound of R D (θ N ). Instead of deriving an approximator to attain the approximation error bound, deep learning algorithms aim to identify a solution φ(x; θ N ) reducing the generalization and optimization errors in Equation (3). Solutions minimizing both generalization and optimization errors will lead to a good solution only if we also have a good upper bound estimate of R D (θ D ) as shown in Equation (3). Independent of whether our analysis here leads to a good approximator, which is an interesting topic to pursue, the theory here does provide a key ingredient in the error analysis of deep learning algorithms.

Theorem 1.1 and Corollary 1.2 provide an upper bound of R D (θ D ). This bound only depends on the given budget of neurons and layers of FLES networks. Hence, this bound is independent of the empirical loss minimization in Equation (2) and the optimization algorithm used to compute the numerical solution of Equation (2). In other words, Theorem 1.1 and Corollary 1.2 quantify the approximation power of FLES networks with a given size. Designing efficient optimization algorithms and analyzing the generalization

The intuitions of the approximation error (AE), the optimization error (OE), and the generalization error (GE). DL is short of deep learning. One needs to control AE, OE, and GE in order to bound the discrepancy between the target function f and the numerical solution φ(x; θ N ) (what we can get in practice), measured by

bounds for FLES networks are two other separate future directions.

The approximation error and the Vapnik-Chervonenkis (VC) dimension are two important measures of the capacity (complexity) of a set of functions. In this section, we discuss the connection between them.

Let us first present the definitions of VC-dimension and related concepts. Assume H is a class of functions mapping from a general domain X to {0, 1}. We say H shatters a set of points

where ⋅ means the size of a set. The above equation means, given any

For a general function set F with its elements mapping from X to R, we say

where

For any m ∈ N + , the growth function of H is defined as

Definition 2.1 (VC-dimension). Assume H is a class of functions from X to {0, 1}. The VC-dimension of H, denoted by VCDim(H), is the size of the largest shattered set, namely,

Let F be a class of functions from X to R. The VC-dimension of F , denoted by VCDim(F ), is defined by VCDim(F ) ∶= VCDim(T ○F ),foot_0 where

In particular, the expression "the VC-dimension of a network (architecture)" means the VC-dimension of the function set that consists of all functions computed by this network (architecture).

As shown in Yarotsky (2018Yarotsky ( , 2017)); Shen et al. (2019Shen et al. ( , 2020)); Lu et al. (2020); Shen et al. (2021); Zhang (2020); Shen et al. (to appear), VC-dimension essentially determines the lower bound of the approximation errors of networks. For simplicity, we use Hölder([0, 1] d , α, λ) as an example, where Hölder([0, 1] d , α, λ) denotes the space of Hölder continuous functions of order α ∈ (0, 1] and a Hölder constant λ > 0. Without loss of generality, we assume λ = 1. Theorem 2.2 below shows that the best possible approximation error of functions in Hölder([0, 1] d , α, 1) approximated by functions in F is bounded by a formula characterized by VCDim(F ).

Theorem 2.2 (Theorem 2.4 of Shen et al. (to appear) or Theorem 4.17 of Zhang ( 2020) ). Assume F is a function set with all elements defined on

This theorem investigates the connection between VC-dimension of F and the approximation errors of functions in Hölder([0, 1] d , α, 1) approximated by elements of F . Denote the best approximation error of functions in Hölder([0, 1] d , α, 1) approximated by the elements of F as

Then, Theorem 2.2 implies that

which means that the best possible approximation error is controlled by VCDim(F ) -α d 9. A typical application of this theorem is to prove the optimality of approximation errors when using ReLU networks to approximate functions in Hölder([0, 1] d , α, 1). It is shown in Harvey et al. (2017) that the VC-dimension of F N,L is bounded by

where F N,L is the space consisting of all functions implemented by ReLU networks with width N and depth L. It is shown in Section 4.4.1 of Zhang (2020) that

where C 1 (α, d) and C 2 (α, d) are two positive constants determined by α and d.

Finally, we would like to point out that a large VC-dimension of the hypothesis space F is a necessary condition of a good approximation error, but cannot guarantee a good approximation error, which also relies on other properties of the hypothesis space F . For example, it is easy to check by Proposition 4.2 that

However, φ ∶ φ(x) = cos(ax), a ∈ R cannot achieve a good approximation error when approximating Hölder continuous functions. Designing a hypothesis space with a large VC-dimension is the first step for a good approximation toll, but to realize the desired approximation power requires refined design of the hypothesise space, which is also the philosophy we followed in this paper. Our initial goal is to design a network architecture with a fixed depth (e.g., three hidden layers) to generate a hypothesis space with a sufficiently large VC-dimension (∞). As we shall see later, Proposition 3.2 implies that the VC-dimension of FLES networks is infinity, which is a necessary condition for our FLES networks to attain super approximation power.

In the interpretation of our theory, three more aspects are important to discuss. The first one is whether it is possible to extend our theory to functions on a more general domain, e.g, E ⊆ [-R, R] d for any R > 0, because R > 1 may cause an implicit curse of dimensionality in some existing theory. The second one is how bad the modulus of continuity would be since it is related to a high-dimensional function f that may lead to an implicit curse of dimensionality in our approximation rate. The last one is the discussion of overcoming the zero derivative in training FLES networks.

First, we can generalize Theorem 1.1 to the function space C(E) with E ⊆ [-R, R] d for any R > 0 in the following corollary with the modulus of continuity ω E f (⋅) defined as follows. For an arbitrary set

As defined earlier, in the case

The proof of this corollary will be presented in Section 3.2.

Corollary 2.3. Given an arbitrary bounded continuous function f on E ⊆ [-R, R] d where R is an arbitrary positive real number, for any

where C f is a constant determined by f .

Hence, the volume of the function domain E ⊆ [-R, R] d only has a mild influence on the approximation rate of our FLES networks. FLES networks can still avoid the curse of dimensionality and achieve exponential convergence for continuous functions on E ⊆ [-R, R] d when R > 1. For example, in the case of Hölder continuous functions of order α ∈ (0, 1] with a constant

Second, most interesting continuous functions in practice have a good modulus of continuity such that there is no implicit curse of dimensionality hidden in ω f (⋅). For example, we have discussed the case of Hölder continuous functions previously. We would like to remark that the class of Hölder continuous functions implicitly depends on d through its definition in Equation (1), but this dependence is moderate since the 2 -norm in Equation ( 1) is the square root of a sum with d terms. Let us now discuss several cases of ω f (⋅) when we cannot achieve exponential convergence or cannot avoid the curse of dimensionality. The first example is ω f (r) = 1 ln(1 r) for small r > 0, which leads to an approximation rate

Apparently, the above approximation rate still avoids the curse of dimensionality but there is no exponential convergence, which has been canceled out by "ln" in ω f (⋅). The second example is ω f (r) = 1 ln 1 d (1 r) for small r > 0, which leads to an approximation rate

The power 1 d further weakens the approximation rate and hence the curse of dimensionality exists. The last example we would like to discuss is ω f (r) = r α d for small r > 0, which results in the approximation rate

which achieves the exponential convergence and avoids the curse of dimensionality when we use very wide networks. Though we have provided several examples of immoderate ω f (⋅), to the best of our knowledge, we are not aware of useful continuous functions with ω f (⋅) that is immoderate. Finally, we would like to point out that the training of FLES networks in practice may encounter two issues. First, network weights in our main theorems require high-precision computation that might not be available in existing computer systems when the dimension d and the network size parameter N are large. But there is no theoretical evidence to exclude the possibility that similar approximation results can be achieved with reasonable weights in practical computation. Second, the vanishing gradient of piecewise constant activation functions makes standard SGD infeasible. There are two possible directions to solve the optimization problem for FLES networks: 1) gradient-free optimization methods, e.g., Nelder-Mead method Nelder and Mead (1965), genetic algorithm Holland (1992), simulated annealing Kirkpatrick et al. (1983), particle swarm optimization Kennedy and Eberhart (1995) et al. (2019). For example, an empirical way is to use a straight-through estimator (STE) by setting the incoming gradients to the activation function (e.g., Floor) equal to its outgoing gradients, disregarding the derivative of the activation function itself. It would be interesting future work to explore efficient learning algorithms based on the FLES network.

A closely related research topic is the Kolmogorov-Arnold representation theorem (KST) Kolmogorov (1956); Arnold (1957); Kolmogorov (1957) and its approximation in a form of modern neural networks. Our FLES networks admit super approximation power with a fixed number of layers for continuous functions and the KST exactly represent continuous functions using two hidden layers and O(d) neurons. More specifically, given any f ∈ C([0, 1] d ), the KST shows that there exist continuous functions

Note that the activation functions {φ q } (also called outer functions) of the neural network in Equation ( 4) have to depend on the target function f , though {ψ q,p } (also called inner functions) can be independent of f . The modulus of continuity of {ψ q,p } can be constructed such that they moderately depend on d, but the modulus of continuity of {φ q } would be exponentially bad in d. In sum, the outer functions are too pathological such that there is no existing numerical algorithms to evaluate these activation functions, even though they are shown to exist by iterative construction Braun and Griebel (2009).

There has been an active research line to develop more practical network approximation based on KST Kůrková (1991, 1992); Maiorov and Pinkus (1999); Guliyev and Ismailov (2018); Montanelli and Yang (2020); Igelnik and Parikh (2003); Schmidt-Hieber (2021) by relaxing the exact representation to network approximation with an ε-error. The key issue these KST-related networks attempting to address is the f -dependency of the activation functions and the main goal is to construct neural networks conquering the curse of dimensionality in a more practical way computationally. The main idea of these variants is to apply computable activation functions independent of f to construct neural networks to approximate the outer and inner functions of the KST, resulting in a larger network that can approximate a continuous function with the desired accuracy. Using this idea, the seminal work in Kůrková (1992) applied sigmoid activation functions and constructed twohidden-layer networks to approximate f ∈ C([0, 1] d ). Though the activation functions are independent of f , the number of neurons scales exponentially in d and the curse of dimensionality exists. Cubic-splines and piecewise linear functions have also been used to approximate the outer and inner functions of KST in Igelnik and Parikh (2003); Montanelli and Yang (2020); Schmidt-Hieber (2021), resulting in cubic-spline networks or deep ReLU networks to approximate f ∈ C([0, 1] d ). But the approximation bounds in these works still suffer from the curse of dimensionality unless f has simple outer functions in the KST. It is still an open problem to characterize the class of functions with a moderate outer function in KST.

To the best of our knowledge, the most successful construction of neural networks with f -independent activation functions conquering the curse of dimensionality is in Maiorov and Pinkus (1999); Guliyev and Ismailov (2018), where a two-hidden-layer network with O(d) neurons can approximate f ∈ C([0, 1] d ) within an arbitrary error ε. Let us briefly summerize their main ideas to obtain such an exciting result here. 1) Identify a dense and countable subset

), e.g., polynomials with rational coefficients. 2) Construct an activation function to "store" all u k (x) for x ∈ [-1, 1]. For example, divide the domain of (x) into countable pieces and each piece is a connected interval of length 2 associated with a u k . In particular, let

for any x ∈ [-1, 1] with carefully chosen constants a k , b k , and c k such that (x) can be a sigmoid function. 3) By construction, there exists a one-hidden-layer network with width 3 and (x) as the activation function to approximate any outer or inner function in KST with an arbitrary accuracy parameter δ. Only the parameters of the onehidden-layer network depend on the target function and accuracy. 4) Replace the inner and outer function in KST with these one-hidden-layer networks to achieve a two-hidden-layer network with (x) as the activation function and width O(d) to approximate an arbitrary f ∈ C([0, 1] d ) within an arbitrary error ε. Unfortunately, the construction of the parameters of this magic network relies on the evaluation of the outer and inner functions of KST, which is not computationally feasible even if computation with arbitrary precision is allowed.

We would like to remark that, though the approximation rate of FLES networks in this paper is relatively worse than the approximation rate in Maiorov and Pinkus (1999); Guliyev and Ismailov (2018), our activation functions are much simpler and there are explicit formulas to specify the parameters of FLES networks. If computation with an arbitrary precision is allowed and the target function f can be arbitrarily sampled, we can specify all the weights in FLES networks. Besides, our approximation rate is sufficiently attractive since it is exponential and avoids the curse of dimensionality. For a large dimension d, the width parameter of our FLES network can be chosen as N = d, which leads to a FLES network of size O(d) with an approximation accuracy O(2 -d ) for Lipschitz continuous functions. O(2 -d ) is sufficiently attractive. In practice, when d is very large, N could be much smaller than d and our approximation rate is still attractive.

Finally, we list several KST-related results in Table 1 for a quick comparison.foot_1 As shown in Table 1, there exists a trade-off between the complexity of activation functions and the network size when the approximation error is fixed. A key advantage of our FLES networks is to use simple and explicit activation functions to attain an exponential convergence rate.

In this section, we will discuss other recent development of neural network approximation. Our discussion will be divided into mainly three parts according to the analysis methodology in the references: 1) functions admitting integral representations; 2) linear approximation; 3) bit extraction. In the seminal work of Barron (1993), its variants or generalization Barron and Klusowski ( 2018); E et al. ( 2019); Chen and Wu (2019); Montanelli et al. (2020), and related references therein, d-dimensional functions of the following form were considered:

where Ω ⊆ R d , µ(w) is a Lebesgue measure in w, and x ∈ Ω ⊆ R d . The above integral representation is equivalent to the expectation of a high-dimensional random function when w is treated as a random variable. By the law of large number theory, the average of N samples of the integrand leads to an approximation of f (x) with an approximation error bounded by Barron (1993)), where O(N ) is the total number of parameters in the network, C f is a d-dimensional integral with an integrand related to f , and µ(Ω) is the Lebesgue measure of Ω.

As discussed in Barron (1993), µ(Ω) and C f would be exponential in d and standard smoothness properties of f alone are not enough to remove the exponential dependence of C f on d. Therefore, the curse of dimensionality exists in the whole approximation error while the curse does not exist in the approximation rate in N . Linear approximation is an efficient approximation tool for smooth functions that computes the approximant of a target function via a linear projection to a Hilbert space or a Banach space as the approximant space. Typical examples include approximation via orthogonal polynomials, Fourier series expansion, etc. Inspired by the seminal work in Yarotsky (2017), where deep ReLU networks were constructed to approximate polynomials with exponential convergence, subsequent works in E and Wang (2018); Opschoor et al. (2019); Montanelli and Du (2019); Chen and Wu (2019); Montanelli et al. (2020); Yarotsky and Zhevnerchuk (2020); Lu et al. (2020); Montanelli and Yang (2020); Yang and Wang (2020) have constructed deep ReLU networks to approximate various smooth function spaces. The main idea of these works is to approximate smooth functions via (piecewise) polynomial approximation first and then construct deep ReLU networks to approximate the ensemble of polynomials. But the curse of dimensionality exists since polynomial approximation cannot avoid the curse. Finally, a different approach is used in Li et al. (to appear). The authors of Li et al. (to appear) use a dynamic system based approach to obtain a universal approximation property of residual neural networks.

The bit extraction proposed in Bartlett et al. (1998) has been a very important technique to develop nearly optimal approximation rates of deep ReLU neural networks Yarotsky (2018); Shen et al. (2020); Lu et al. (2020); Yang and Wang (2020); Zhang (2020); Shen et al. (to appear) and the optimality is based on the nearly optimal VC-dimension bound of ReLU networks in Harvey et al. (2017). The bit extraction was also applied in Shen et al. (2021);Schmidt-Hieber (2021) and this paper to develop network approximation theories. In the first step, an efficient projection map in a form of a ReLU, or a Floor-ReLU, or a FLES network is constructed to project highdimensional points to one-dimensional points such that the high-dimensional approximation problem is reduced to a one-dimensional approximation problem. In the second step, the one-dimensional approximation problem is solved by constructing a ReLU, or a Floor-ReLU, or a FLES network, which can be efficiently compressed via the bit extraction. Although shallower neural networks can also carry out the above two steps, bit extraction can take full advantage of the power of depth and construct deep neural networks with a nearly optimal number of parameters or neurons to fulfill the above two steps.

In this section, we first introduce basic notations in this paper in Section 3.1. Then we prove Theorem 1.1 and Corollary 2.3 in Section 3.2 based on Theorem 3.1, which is proved in Section 3.3.

The main notations of this paper are listed as follows.

• Vectors and matrices are denoted in a bold font. Standard vectorization is adopted in the matrix and vector computation. For example, adding a scalar and a vector means adding the scalar to each entry of the vector.

• Let R denote the set of real numbers.

• Let Z, N, and N + denote the set of integers, natural numbers, all positive integers, respectively, i.e., Z = {0, 1, 2, ⋯} ∪ {-1, -2, -3, ⋯}, N = {0, 1, 2, ⋯}, and N + = {1, 2, 3, ⋯}.

• The floor function (Floor) is defined as ⌊x⌋ ∶= max{n ∶ n ≤ x, n ∈ Z} for any x ∈ R.

• For θ ∈ [0, 1), suppose its binary representation is θ = ∑ ∞ =1 θ 2 -with θ ∈ {0, 1}, we introduce a special notation bin0.θ 1 θ 2 ⋯θ L to denote the L-term binary representation of θ, i.e., bin0.θ

• The expression "a network with width N and depth L" means -The maximum width of this network for all hidden layers is no more than N .

-The number of hidden layers of this network is no more than L.

In this section, we will prove Theorem 1.1 and Corollary 2.3. To this end, we first introduce Theorem 3.1 that works only for [0, 1) d , regraded as a weaker variant of Theorem 1.1. Theorem 3.1. Given an arbitrary continuous function f on [0, 1] d , for any

, where φ is defined by a formula in a 1 , a 2 , ⋯, a N as follows.

We will prove Theorem 1.1 and Corollary 2.3 based on Theorem 3.1, the proof of which can be found in Section 3.3.

where

Define φ(x) ∶= φ(2x) for any x ∈ R d . Then by Equation ( 5), for any x ∈

where φ(x) ∶= φ( x 2 ) can be represented by

With the discussion above, we have proved Theorem 1.1.

Next, we present the proof of Corollary 2.3 below.

By applying Theorem 3.

where

= ω E f (3Rr), for any r ≥ 0.

Define φ(x) ∶= φ( x+R 3R ) for any x ∈ R d . Then by Equation ( 6), for any

where

) is a constant essentially determined by f . With the discussion above, we have proved Corollary 2.3.

To prove Theorem 3.1, we first present the proof sketch. Shortly speaking, we construct piecewise constant functions to approximate continuous functions. There are five key steps in our construction.

x β as the vertex of Q β with minimum ⋅ 1 norm, where J is an integer determined later. See Figure 3 for the illustrations of Q β and x β .

2. Construct a vector-valued function

. Finally, re-scale and shift φ to obtain the final function φ approximating f well.

Recall that

Step 1 and 5 are straightforward. To implement Step 2, we introduce σ 1 since it can help to significantly simplify the construction of the vector-valued projecting function Φ 1 . The implementation of Step 3 is based on the J-ary representation, namely, define Yarotsky (2018). To extract sufficient many bits with a limited neuron budget, we introduce two powerful activation functions σ 2 and σ 3 , as shown in the proposition below.

Proposition 3.2. Given any K ∈ N + and arbitrary θ 1 , θ 2 , ⋯, θ K ∈ {0, 1}, it holds that

Proof. Since θ j ∈ {0, 1} for j ∈ {1, 2, ⋯, K}, we have

.foot_2 (7)

Clearly, the first term in Equation ( 7) ∑ k-1 j=1 2 k-j-1 ⋅θ j is a non-negative integer since θ j ∈ {0, 1} for any j ∈ {1, 2, ⋯, K}. As for the third term in Equation ( 7), we have

Therefore, by Equation ( 7), we have

If θ k = 0, by Equation ( 8), we have

Similarly, if θ k = 1, by Equation ( 8), we have

So we finish the proof.

We would like to point out that Proposition 3.2 indicates that the VCdimension of the function space {f ∶ f (x) = σ 3 (a ⋅ x), for a ∈ R} is infinity, which implies that the VC-dimension of FLES networks is also infinity. As discussed previously in Section 2.2, having an infinite VCdimension is a necessary condition for FLES networks to attain super approximation power.

With Proposition 3.2 in hand, we are ready to prove Theorem 3.1.

Proof of Theorem 3.1. The proof consists of five steps.

Step 1∶ Set up. Assume f is not a constant function since it is a trivial case. Then ω f (r) > 0 for any r > 0. Clearly,

To be exact, defined x β ∶= β J and

x β for β ∈ {0, 1, 2, 3}

(a) Step

for any x = (x 1 , x 2 , ⋯, x d ) ∈ R d . Then, for any x ∈ Q β and each β ∈ {0, 1, ⋯, J -1} d , we have

Step 3∶ Construct φ 2 bijectively mapping β ∈ {0, 1, ⋯, J -

Inspired by the J-ary representation, we define a linear function

Then φ 2 is a bijection from {0, 1, ⋯, J -1} d to {1, 2, ⋯, J d }.

Step 4∶ Construct φ 3 mapping φ 2 (β) ∈ {1, 2, ⋯, J d } approximately to f (x β ).

For each k ∈ {1, 2, ⋯, J d }, there exists a unique β ∈ {0, 1, ⋯, J -1} d such that φ 2 (β) = k. Thus, define

For each k ∈ {1, 2, ⋯, J d }, there exist θ k,1 , θ k,2 , ⋯, θ k,N ∈ {0, 1} such that

For each j ∈ {1, 2, ⋯, N }, by Proposition 3.2 (set K = J d therein), there exists

Then, for any k ∈ {1, 2, ⋯, J d }, we have

Step 5∶ Define φ ∶= φ 3 ○ φ 2 ○ Φ 1 approximating f well, and re-scale and shift φ to obtain φ approximating f well.

Define φ ∶= φ 3 ○ φ 2 ○ Φ 1 , by Equation ( 10), ( 11), (12), and (13), we have, for any x ∈ Q β and each β ∈ {0, 1, ⋯, J -

It follows from J = 2 N and the definitions of Φ 1 , φ 2 , and φ 3 that

So we finish the proof.

As discussed previously, our FLES networks can attain super approximation power. However, two activation functions in FLES networks are piecewise constant functions that would lead to challenges in numerical algorithm design. It is interesting to explore continuous activation functions achieving similar results. To this end, we introduce three new activation functions as follows. First, for any δ ∈ (0, 1), we define

for any n ∈ Z.

In fact, 1,δ can be regarded as a "continuous version" of the floor function.

Next, we define 2 (x) ∶= 3 x , and 3 (x) ∶= T cos(2πx) , for any x ∈ R, where

is a continuous piecewise linear function. 2 plays the same role of σ 2 (x) = 2 x and 3 is essentially a "continuous version" of σ 3 in FLES networks. With these three activation functions in hand, we have the following theorem.

Theorem 4.1. Let f be an arbitrary continuous function defined on [0, 1] d . For any δ ∈ (0, 1), N ∈ N + , and p

where φ is defined by a formula in a 1 , a 2 , ⋯, a N as follows

The approximation error in Theorem 4.1 is characterized by L p -norm for p ∈ [1, ∞) instead of a pointwise error estimate in Theorem 1.1. By using ideas in Lu et al. (2020); Zhang (2020), we can extend this result to L ∞ -norm. However, this extension requires 2d + 3 hidden layers instead of 3 hidden layers. Since our focus here is the approximation using three hidden layers, we will leave this extension as future work.

To prove Theorem 4.1, we need the following proposition.

Proposition 4.2. Given any K ∈ N + and arbitrary θ 1 , θ 2 , ⋯, θ K ∈ {0, 1}, it holds that

Proof. Since θ j ∈ {0, 1} for j ∈ {1, 2, ⋯, K}, we have 0 Proof of Theorem 4.1. The proof consists of five steps.

Step 1∶ Set up.

Assume f is not a constant function since it is a trivial case. Then

It follows that f (x) ∈ [0, 1] for any x ∈ [0, 1] d . Set J = 2 N and divide [0, 1] d into J d cubes {Q β } β and a small region Λ([0, 1] d , J, δ). To be exact, define x β ∶= β J and 5 for illustrations.

Step

0.00 0.25 0.50 0.75 1.00

Λ([0, 1] d , J, δ) for J = 4, d = 2

Q β for β ∈ {0, 1, 2, 3} 2

x β for β ∈ {0, 1, 2, 3} 2 (b) Step 3∶ Construct φ 2 bijectively mapping β ∈ {0, 1, ⋯, J -1} d to φ 2 (β) ∈ {1, 2, ⋯, J d }.

Inspired by the J-ary representation, we define an affine linear map φ 2 (x) ∶= 1 + d i=1 J i-1 x i , for each x = (x 1 , x 2 , ⋯, x d ) ∈ R d .

Then φ 2 is a bijection from {0, 1, ⋯, J -1} d to {1, 2, ⋯, J d }.

Step 4∶ Construct φ 3 mapping φ 2 (β) ∈ {1, 2, ⋯, J d } approximately to f (x β ).

For each k ∈ {1, 2, ⋯, J d }, there exists a unique β ∈ {0, 1, ⋯, J -1} d such that φ 2 (β) = k. Thus, define

For each k ∈ {1, 2, ⋯, J d }, there exist θ k,1 , θ k,2 , ⋯, θ k,N ∈ {0, 1} such that

For each j ∈ {1, 2, ⋯, N }, by Proposition 4.2 (set K = J d therein), there exists a j ∈ [0, and

for any k ∈ {1, 2, ⋯, J d }.

Step 5∶ Define φ ∶= φ 3 ○ φ 2 ○ Φ 1 approximating f well, and re-scale and shift φ to obtain φ approximating f well. Define φ ∶= φ 3 ○ φ 2 ○ Φ 1 , by Equation ( 16), ( 17), ( 18), and (20), we have, for any x ∈ Q β and each β ∈ {0, 1, ⋯, J -

Finally, define φ ∶= 2ω f ( √ d) φ + f (0) -ω f ( √ d). Equation ( 15) implies ω f (r) = 2ω f ( √ d)ω f (r) for any r ≥ 0, deducing

for any x ∈ ⋃ β∈{0,1,⋯,J-1} d Q β . By Equation ( 19) and the definition of

By the definitions of Φ 1 , φ 2 , and φ 3 , we have

So we finish the proof.

This paper has introduced a theoretical framework to show that three hidden layers are enough for neural network approximation to achieve exponential convergence and avoid the curse of dimensionality for approximating functions as general as (Hölder) continuous functions. The key idea is to leverage the power of multiple simple activation functions: the floor function (⌊x⌋), the exponential function (2 x ), the step function (1 x≥0 ), or their compositions. This new class of networks is called the FLES network. Given a Lipschitz continuous function f on [0, 1] d , it was shown by construction that FLES networks with width max{d, N } and three hidden layers admit a uniform approximation rate 6λ √ d 2 -N , where λ is the Lipschitz constant of f . More generally for an arbitrary continuous function f on [0, 1] d with a modulus of continuity ω f (⋅), the constructive approximation rate is 2ω

We also extend such a result to general bounded continuous functions on a bounded set E ⊆ R d . The results in this paper provide a theoretical lower bound of the power of FLES networks. Whether or not this bound is achievable in actual computation relies on advanced algorithm design as a separate line of research. Finally, we have also derived similar approximation results in the L p -norm for p ∈ [1, ∞) using continuous activation functions.