Error bounds for deep ReLU networks using the Kolmogorov--Arnold superposition theorem
Hadrien Montanelli Haizhao Yang






HM]Hadrien Montanellicor1
hadrien.montanelli@gmail.com

HY]Haizhao Yang
haizhao@nus.edu.sg

[cor1]Corresponding author
[HM]Department of Applied Physics and Applied Mathematics, Columbia University, New York, United States
[HY]Department of Mathematics, National University of Singapore, Singapore


We prove a theorem concerning the approximation of multivariate functions by deep ReLU networks, for which the curse of the dimensionality is lessened. Our theorem is based on a constructive proof of the Kolmogorov–Arnold superposition theorem, and on a subset of multivariate continuous functions whose outer superposition functions can be efficiently approximated by deep ReLU networks.



deep ReLU networks curse of dimensionality approximation theory Kolmogorov–Arnold superposition theorem







§ INTRODUCTION


At the second International Congress of Mathematicians in Paris 1900, Hilbert presented ten of his 23 problems, including the 13th problem about equations of degree seven. He considered the following equation,

    x^7 + ax^3 + bx^2 + cx + 1 = 0,

and asked whether its solution x(a,b,c), seen as a function of the three parameters a, b and c, could be written as the composition of functions of only two variables.

Hilbert's 13th problem was solved by Kolmogorov and his 19 years old student Arnold in a series of papers in the 1950s. Kolmogorov first proved in 1956 that any continuous function of several variables could be expressed as the composition of functions of three variables <cit.>. His student Arnold extended his theorem in 1957; three variables were reduced to two <cit.>. Kolmogorov finally showed later that year that functions of only one variable were needed <cit.>. The latter result is known as the Kolmogorov–Arnold superposition theorem, and states that any continuous functions f:[0,1]^n→ can be decomposed as

    f(x_1,…,x_n) = ∑_j=0^2nϕ_j(∑_i=1^nψ_i,j(x_i)),

with 2n+1 continuous outer functions ϕ_j:→ (dependent of f) and 2n^2+n continuous inner functions ψ_i,j:[0,1]→ (independent of f). 

The Kolmogorov–Arnold superposition theorem was further improved in the 1960s and the 1970s. Lorentz showed in 1962 that the outer functions ϕ_j might be chosen to be the same function ϕ, and replaced the inner functions ψ_i,j by λ_iψ_j, for some positive rationally independent constants λ_i≤ 1 <cit.>, while Sprecher replaced the inner functions ψ_i,j by Hölder continuous functions x_i↦λ^ijψ(x_i+jϵ) in 1965 <cit.>. Two years later, Fridman demonstrated that the inner functions could be chosen to be Lipschitz continuous, but his decomposition used 2n+1 outer functions and 2n^2+n inner functions <cit.>. Finally, Sprecher provided in 1972 a decomposition with Lipschitz continuous functions x_i↦λ^i-1ψ(x_i+jϵ) <cit.>.

Theoretical connections with neural networks started with the work of Hecht–Nielsen in 1987 <cit.>. He interpreted the Kolmogorov–Arnold superposition theorem as a neural network, whose activation functions were the inner and outer functions. Girosi and Poggio claimed in 1989 that his interpretation was irrelevant for two reasons; first, the inner and outer functions were highly nonsmooth (i.e., these were at least as difficult to approximate as f); second, the outer functions depended on f (i.e., the network architecture could not be parametrized). Kůrková weakened the statement of Girosi and Poggio, in the early 1990s, by giving a direct proof of the universal approximation theorem of multilayer neural networks using the Kolmogorov–Arnold superposition theorem, and by showing that the weight selection reduced to a linear regression problem <cit.>.

Numerical implementations originated with the work of Sprecher in the mid 1990s <cit.>, which was followed, in 2003, by the Kolmogorov's spline network of Igelnik and Parikh <cit.>. Braun and Griebel proposed an algorithm to implement a constructive proof of the Kolmogorov–Arnold theorem in 2009 <cit.>, using Köppen's Hölder continuous inner function <cit.>. 

Approximation theory for neural networks started with shallow networks and the 1989 universal approximation theorems of Cybenko <cit.> and Hornik <cit.>. In the last few years, the attention has shifted to the approximation properties of deep ReLU networks <cit.>. In particular, one of the most important theoretical problems is to determine why and when deep networks lessen or break the curse of dimensionality, characterized by the (ϵ^-n) growth of the network size W as the error ϵ→0, in dimension n.[We recall that W=(ϵ^-n) means that there exists c_1(n)>0, such that W≤ c_1(n)ϵ^-n, for sufficiently small values of ϵ. Alternatively, we shall write ϵ=(W^-1/n) when there exists c_2(n)>0, such that ϵ≤ c_2(n)W^-1/n, for sufficiently large values of W.] We recommend the review <cit.> for a discussion about the curse of dimensionality in the context of deep network approximation.

In this paper, we introduce a set of multivariate continuous functions for which the approximation of the outer functions by deep ReLU networks is appealing to lessen the curse of the dimensionality. 
We show that any function f:[0,1]^n→ in this set can be approximated with error ϵ by a very deep ReLU network of depth and size[Following Yarotsky <cit.>, we define the depth L of a network as the number of layers, the size W as the total number of weights, and we allow connections between units in non-neighboring layers.] (ϵ^-log n); the curse of dimensionality is lessened.

Before the exposition of our main result in Section <ref>, we will review a specific version of the Kolmogorov–Arnold superposition theorem in Section <ref>, and show in Section <ref> how to approximate the inner and outer functions by very deep ReLU networks.




§ CONSTRUCTIVE VERSION OF THE KOLMOGOROV–ARNOLD SUPERPOSITION THEOREM


We review in this section a constructive version of the Kolmogorov–Arnold superposition theorem that goes back to Sprecher in 1996 and 1997 <cit.>. The proof he provided at the time was not fully correct; minor modifications were made by Braun and Griebel in 2009 to complete his proof <cit.>, using the inner function suggested by Köppen <cit.>.

For any integer n≥2, m≥ 2n and γ≥ m+2, let 

    a = 1/γ(γ-1),


    λ_1=1,   λ_i = ∑_ℓ=1^∞γ^-(i-1)β_n(ℓ),    2≤ i≤ n,

with 

    β_n(ℓ) = 1-n^ℓ/1-n = 1 + n + … + n^ℓ-1,

and

    ν = 2^-α(γ+3),   α = log_γ2.


We recall that a function f:[a,b]→ is said to be (ν,α)-Hölder continuous if and only if there exist scalars ν>0 and 0<α≤1, such that | f(x)-f(y)|≤ν| x-y|^α, for all x,y∈[a,b]. (The value α=1 yields ν-Lipschitz continuous functions.)


Let n≥2, m≥2n and γ≥ m+2 be given integers, and let a, λ_i (1≤ i≤ n), ν and α be defined as in Equations (<ref>)–(<ref>). Then, there exists a (ν,α)-Hölder continuous inner function ψ:[0,2)→[0,2), such that for any continuous function f:[0,1]^n→, there exist m+1 continuous outer function ϕ_j:[0,2γ-1/γ-2)→, such that

    f(x_1,…,x_n) = ∑_j=0^mϕ_j(∑_i=1^nλ_iψ(x_i+ja)).




Let us now go through the main two steps of the proof of Theorem <ref>; for details, see <cit.>.

The first step is the building of the inner function ψ, which involves uniform grids D_k with step sizes γ^-k,

    D_k = {iγ^-k, 0≤ i≤γ^k-1}⊂[0,1).

There are γ^k different points 0≤ d≤1-γ^-k<1 on each grid D_k, and each point d on D_k is represented in base γ as follows,

    d = ∑_ℓ=1^k i_ℓγ^-ℓ,    i_ℓ∈{0,1,…,γ-1}.







The inner function ψ is first defined at grid points d∈ D_k via ψ(d)=ψ_k(d) for all integers k≥1, where the functions ψ_k are recursively defined by

    ψ_k(d) =
    {[                    d,               d∈ D_1,;    ψ_k-1(d-i_kγ^-k) +;         i_kγ^-β_n(k), d∈ D_k, k>1, i_k<γ-1,;     1/2[ψ_k(d-γ^-k) +;       ψ_k-1(d+γ^-k)], d∈ D_k, k>1, i_k=γ-1. ].


The function ψ is then defined at any x∈[0,1) via[The existence of the limit is based on a suitably defined Cauchy sequence; see <cit.> for details.]

    ψ(x) = lim_k→∞ψ_k(∑_ℓ=1^ki_ℓγ^-ℓ),

since each x∈[0,1) has the representation

    x = ∑_ℓ=1^∞ i_ℓγ^-ℓ = lim_k→∞∑_ℓ=1^ki_ℓγ^-ℓ.

Finally, the inner function is extended to x∈[1,2) by

    ψ(x) = ψ(x-1) + 1.

The resulting function has domain and range [0,2).


For points d=∑_ℓ=1^ki_ℓγ^-ℓ∈ D_k whose indices i_ℓ are all strictly smaller than γ-1, it is easy to show, by induction, that

    ψ(d) = ∑_ℓ=1^ki_ℓγ^-β_n(ℓ).

For other points, the right-hand side in the equation above is only a lower bound.

The inner function constructed in Proposition <ref> was introduced by Köppen in 2002 <cit.>. It is Hölder continuous, a result that can be proved using the techniques introduced by Sprecher in his 1965 paper <cit.>.



The inner function ψ of Proposition <ref> is (ν,α)-Hölder continuous with ν=2^-α(γ+3) and α=log_γ2.



See <cit.>.


We plot in Figure <ref> the graph of the function ψ evaluated on the grid D_3 for n=2 and γ=10. As k→∞, the graph of ψ exhibits self-similarity, which is expected since ψ is merely Hölder continuous.





The second step of the proof is the iterative construction of the outer functions ϕ_j. For each 0≤ j≤ m, let D^j_k denote the shifted grid defined by

    D_k^j     = D_k + j∑_ℓ=2^kγ^-ℓ,    0≤ j≤ m.

Let (D_k)^n and (D_k^j)^n denote the Cartesian products of n copies of D_k and D_k^j, and let

    ξ(d) = ∑_i=1^nλ_iψ(d_i),   d=(d_1,…,d_n)∈(D_k^j)^n,

and

    b_k = (∑_ℓ=k+1^∞γ^-β_n(ℓ))(∑_i=1^nλ_i).


Finally, for each d∈(D_k^j)^n, let θ:x↦θ(d;x) denote the function defined by

    θ(d;x) = σ(γ^β_n(k+1)[x - ξ(d)] + 1) 
                - σ(γ^β_n(k+1)[x - ξ(d) - (γ - 2)b_k]),

where σ:→[0,1] is the piecewise linear function satisfying σ(x)=0 for x≤0, σ(x)=x for 0≤ x≤1, and σ(x)=1 for x≥1. For given k≥ 1 and 0≤ j≤ m, the γ^nk functions θ(d;·) have disjoint supports, and are ν-Lipschitz with ν=γ^β_n(k+1); see Figure <ref>.



Let δ and η be two scalars that verify

    0<δ<1-n/n-m+1

and

    0<m-n+1/n+1δ + 2n/m+1≤η<1,

and f:[0,1]^n→ be a continuous function.

Starting with f_0=0 and e_0=f-f_0=f, the approximate outer function ϕ_j^r at iteration r≥1 are defined, for each 0≤ j≤ m, as

    ϕ_j^r(x) = 1/m+1∑_ℓ=1^r∑_d∈ (D_k_ℓ)^n e_ℓ-1(d)θ(d+j∑_i=2^k_ℓγ^-i;x),

for some k_r=k_r(f) chosen such that ‖x-x'‖_∞≤γ^-k_r implies | e_r-1(x) - e_r-1(x')|≤δ‖ e_r-1‖_L^∞([0,1]^n).

This yields an approximate function f_r,

    f_r(x_1,…,x_n) = ∑_j=0^mϕ_j^r(∑_i=1^nλ_iψ(x_i+ja)),

and its error e_r = f - f_r, with

    ‖ e_r‖_L^∞([0,1]^n)≤η^r‖ f‖_L^∞([0,1]^n).


Taking the limit r→∞ yields

    f(x_1,…,x_n) = ∑_j=0^mϕ_j(∑_i=1^nλ_iψ(x_i+ja)),

where ϕ_j = lim_r→∞ϕ_j^r.[The existence of the limits as r→∞ relies on ϕ_j^r being bounded and Equation (<ref>); see <cit.> for details.]


The approximate outer functions ϕ_j^r of Proposition <ref> are Lipschitz continuous, as we shall prove next.



For all r≥1 and 0≤ j≤ m, the outer functions ϕ_j^r of Proposition <ref> have domain [0,2γ-1/γ-2), and are ν_r(f)-Lipschitz continuous with

    ν_r(f) = ‖ f‖_L^∞([0,1]^n)/m+1∑_ℓ=1^rη^ℓ-1γ^β_n(k_ℓ(f)+1).




To prove that the domain is [0,2γ-1/γ-2), we use the fact that |ψ(x)|<2 for all x∈[0,2), and

    ∑_i=1^nλ_i     < 1 + 1/γ-1 + 1/γ^1+n-1 + 1/γ^1+n+n^2-1 + …, 
        < γ-1/γ-2.


For the Lipschitz constant, we recall that, for given k_ℓ(f) and j, the functions x↦θ(d;x), d∈(D_k_ℓ^j)^n, have disjoint supports, and are ν(f)-Lipschitz continuous with ν(f)=γ^β_n(k_ℓ(f)+1). Using Equation (<ref>), summing over ℓ and multiplying by 1/(m+1) yields the desired result.


Let us emphasize that the Lipschitz constants ν_r(f) in Proposition <ref> depend on f via the integers k_ℓ(f). 
This motivates us to introduce a set of continuous functions based on the growth of k_ℓ(f) with ℓ as follows,

    K_C([0,1]^n; ) = {f∈ C([0,1]^n; ), k_r(f)≤ C, r≥1},

for some constant C>0, where C([0,1]^n; ) denotes the set of multivariate continuous functions, and for given n≥ 2, m≥ n, γ≥ m+2, δ and η.
A direct calculation shows that functions in this set have outer functions whose Lipschitz constants (<ref>) satisfy

    ν_r(f) ≤‖ f‖_L^∞([0,1]^n)/m+1rγ^2n^C.





§ APPROXIMATION OF THE INNER AND OUTER FUNCTIONS BY VERY DEEP RELU NETWORKS


Let ω:[0,∞)→[0,∞) be a function that is vanishing and continuous at 0, i.e., 
lim_δ→0+ω(δ)=ω(0)=0, and B⊂^d be a compact domain.
We say that an uniformly continuous function f:B→ has modulus of continuity ω if and only if

    | f(x)-f(x')|≤ω(‖x-x'‖_2),  ∀x,x'∈ B.


Many classical estimates in approximation theory are based on moduli of continuity. For example, best degree-d polynomial approximation of continuous functions of one variable with modulus of continuity ω yields 𝒪(ω(d^-1)) errors <cit.>. The 𝒪(ω(d^-1/n)) errors in dimension n suffers from the curse of dimensionality, but matches the lower bound obtained by nonlinear widths <cit.>.

In neural network approximation, moduli of continuity appear in the work of Yarotsky. In 2018, he proved that very deep ReLU networks of depth L=(W) and size W generate 𝒪(ω((W^-2/n))) errors <cit.>. This result matches the lower bound based on VC dimension of Anthony and Barlett <cit.> (see also <cit.>), and improves the 𝒪(W^-1/nlog_2^1/nW) errors he obtained for Lipschitz functions in 2017 <cit.>. 

Let us stress that Yarotsky's theorems provide upper bounds for the errors when the same network architecture is used to approximate all functions in a given function space. In other words, the network architecture does not depend on the function being approximated in that space; only the weights do. Moreover, the networks he utilizes are said to be very deep because the depth L satisfies L=(W). We recall his 2018 result below.



For any continuous function f:[0,1]^n→ with modulus of continuity ω_f,
there is a deep ReLU network  depth L≤ c_0(n)W and size W, such that

    ‖ f - ‖_L^∞([0,1]^n)≤ c_1(n)ω_f(c_2(n)W^-2/n),

for some c_0(n),c_1(n),c_2(n)>0.
 

We extend Yarotsky's result to domains [0,M]^n.



For any continuous function f:[0,M]^n→ with modulus of continuity ω_f,
there is a deep ReLU network  of depth L≤ c_0(n)W and size W, such that

    ‖ f - ‖_L^∞([0,M]^n)≤ c_1(n)ω_f(c_2(n)M W^-2/n),

with c_0(n),c_1(n),c_2(n) as in Theorem <ref>.
 


We use Theorem <ref> with g(x)=f(x/M) on [0,1]^n. Note that ω_g(δ)=ω_f(Mδ). Therefore, there is a deep ReLU network  of depth L≤ c_0(n)W and size W, such that

    ‖ g - ‖_L^∞([0,1]^n)   ≤ c_1(n)ω_g(c_2(n)W^-2/n), 
        = c_1(n)ω_f(c_2(n)M W^-2/n),

with c_0(n),c_1(n),c_2(n) as in Theorem <ref>. Since g(Mx) - (Mx) = f(x) - (Mx), the network (x)=(Mx) satisfies all requirements in this corollary.


We shall now apply Corollary <ref> to the inner and outer functions of Propositions <ref> and <ref>. For simplicity, we shall assume, throughout the rest of the paper, that m=2n and γ=2n+2.



Let n≥ 2 be an integer and ψ be the inner function defined in Proposition <ref>.
Then, for any scalar 0<ϵ<1, there is a deep ReLU network  that has depth L≤ c_0(1)W and size

    W≤ c_3(n)ϵ^-[1+log_2(n+1)]/2,

such that ‖ψ - ‖_L^∞([0,2])≤ϵ, with

    c_3(n) = [(2n+5)c_1(1)]^[1+log_2(n+1)]/2c_2(1)^1/2,

and c_0(1),c_1(1),c_2(1) as in Theorem <ref>.
 


We use Corollary <ref> with M=2 and the modulus of continuity of Proposition <ref>, i.e.,

    ω_ψ(δ) = νδ^α,

with ν=2^-α(2n+5) and α=log_2n+22.




Let n≥ 2 be an integer, f:[0,1]^n→ be a continuous function in K_C([0,1]^n; ) that satisfies ‖ f‖_L^∞([0,1]^n)≤1, and ϕ_j^r be the (2n+1) outer functions defined in Proposition <ref> at iteration r, for some r≥1. Then, for any scalar 0<ϵ<1, there are (2n+1) deep ReLU networks _j^r that have depth L≤ c_0(1)W and size

    W≤ c_4(n,r)ϵ^-1/2,

such that ‖ϕ_j^r - _j^r‖_L^∞([0,2γ-1/γ-2])≤ϵ, with

    c_4(n,r) = [c_1(1)c_2(1)/nr (2n+2)^2n^C]^1/2,

and c_0(1),c_1(1),c_2(1) as in Theorem <ref>.
 


We use Corollary <ref> with M=2γ-1/γ-2 and the modulus of continuity corresponding to the Lipschitz continuity described in Proposition <ref>, i.e.,

    ω_ϕ_j^r(δ) = ν_r(f)δ,

with ν_r(f) as in Equation (<ref>). This yields

    ‖ϕ_j^r - _j^r‖_L^∞([0,2γ-1/γ-2])   ≤ 2c_1(1)c_2(1)ν_r(f)γ-1/γ-2W^-2, 
       ≤c_1(1)c_2(1)/nr(2n+2)^2n^CW^-2,

where _j^r is a very deep neural network with size W and depth L≤ c_0(1)W, and c_0(1),c_1(1),c_2(1) as in Theorem <ref>.
To achieve the ϵ approximation error, W can be as small as c_4(n,r) ϵ^-1/2, where

    c_4(n,r) = [c_1(1)c_2(1)/nr (2n+2)^2n^Cr]^1/2.






§ MAIN THEOREM


We present in this section our main theorem about the approximation of multivariate continuous functions by very deep ReLU networks. Our proof is based on the Kolmogorov–Arnold superposition theorem (Theorem <ref>), and on the approximation of the inner and outer functions by very deep ReLU networks (Propositions <ref> and <ref>).



Let n≥ 2 be an integer and f be a continuous function in K_C([0,1]^n; ) that satisfies ‖ f‖_L^∞([0,1]^n)≤1. Then, for any scalar 0<ϵ<1, there is a deep ReLU network _r that has depth

    L≤    c_0(1)c̃_3(n,r(ϵ))ϵ^-[1+log_2(n+1)]/2
        + c_0(1)c̃_4(n,r(ϵ))ϵ^-1/2,

and size

    W≤    n(2n+1)c̃_3(n,r(ϵ))ϵ^-[1+log_2(n+1)]/2
        + (2n+1)c̃_4(n,r(ϵ))ϵ^-1/2,

such that ‖ f - _r‖_L^∞([0,1]^n)≤ϵ, with c_0(1) as in Theorem <ref>,

    c̃_3(n,r(ϵ))    =[4n+2/nr(ϵ)(2n+2)^2n^C]^[1+log_2(n+1)]/2c_3(n), 
    c̃_4(n,r(ϵ))    =[8n+4]^1/2c_4(n,r(ϵ)),

c_3(n) as in Equation (<ref>), c_4(n,r) as in Equation (<ref>), and r(ϵ)=log 2ϵ^-1/logη^-1.



Let 0<ϵ<1 be a scalar. Let f:[0,1]^n→ be a continuous function in K_C([0,1]^n; ) that satisfies ‖ f‖_L^∞([0,1]^n)≤1. 
Using Equation (<ref>) in Theorem <ref>, we write f as

    f(x_1,…,x_n) = ∑_j=0^2nϕ_j(∑_i=1^nλ_iψ(x_i+ja)).

We first approximate f by f_r defined in Equation (<ref>) using the error bound in Proposition <ref>, i.e.,

    f_r(x_1,…,x_n) = ∑_j=0^2nϕ_j^r(∑_i=1^nλ_iψ(x_i+ja)).

If we choose r(ϵ)=log 2ϵ^-1/logη^-1, then using Equation (<ref>), we get ‖ f - f_r‖_L^∞([0,1]^n)≤ϵ/2.

We now approximate f_r by a deep ReLU network _r defined by

    _r(x_1,…,x_n) = ∑_j=0^2n_j^r(∑_i=1^nλ_i(x_i+ja)),

where  and _j^r approximate ψ and ϕ_j^r to some accuracies 0<ϵ_ψ<1 and 0<ϵ_ϕ<1 to be determined later. We plot the subnetwork _j^r in Figure <ref>.

Using Propositions <ref> and <ref>, the network  has depth L_ψ≤ c_0(n)W_ψ and size

    W_ψ≤ c_3(n)ϵ_ψ^-[1+log_2(n+1)]/2,

while the networks _j^r have depth L_ϕ≤ c_0(n)W_ϕ and size

    W_ϕ≤ c_4(n,r)ϵ_ϕ^-1/2.




Using the triangle inequality, we compute the accuracy of the network _r as follows,

    | f_r(x_1,…,x_n) - _r(x_1,…,x_n)|, 
    ≤   |∑_j=0^2nϕ_j^r(∑_p=1^nλ_iψ(x_i+ja))-∑_j=0^2nϕ_j^r(∑_i=1^nλ_i(x_i+ja))|
     
    +    |∑_j=0^2nϕ_j^r(∑_i=1^nλ_i(x_i+ja))-∑_j=0^2n_j^r(∑_i=1^nλ_i(x_i+ja))|, 
    ≤   (2n+1)^2/2nν_r(f)ϵ_ψ + (2n+1)ϵ_ϕ.

We must choose

    ϵ_ψ = nϵ/2(2n+1)^2ν_r(f),   ϵ_ϕ = ϵ/4(2n+1),

to obtain ‖ f_r - _r‖_L^∞([0,1]^n)≤ϵ/2 and ‖ f - _r‖_L^∞([0,1]^n)≤ϵ.

Therefore, the network  has depth L_ψ≤ c_0(n)W_ψ and size

    W_ψ≤c̃_3(n,ϵ)ϵ^-[1+log_2(n+1)]/2,

with

    c̃_3(n,r(ϵ)) =[4n+2/nr(ϵ)(2n+2)^2n^C]^[1+log_2(n+1)]/2c_3(n),

while the networks _j^r have depth L_ϕ≤ c_0(n)W_ϕ and size

    W_ϕ≤c̃_4(n,r(ϵ))ϵ^-1/2,

with

    c̃_4(n,r(ϵ))     = [8n+4]^1/2c_4(n,r(ϵ)).

Lastly, the network _r has depth L≤ c_0(1)(W_ψ+W_ϕ) and size W≤ n(2n+1)W_ψ+(2n+1)W_ϕ.


The upper bounds in Theorem <ref> show that, for a given dimension n, the depth and the size of the network grow like (ϵ^-log n); the curse of dimensionality is lessened asymptotically when ϵ approaches 0.

Let us end this section with a comment about smoothness. Yarotsky proved in 2017 that deep ReLU networks of depth and size (ϵ^-n/m) can approximate functions with m weak and bounded derivatives in [0,1]^n to accuracy ϵ <cit.> (we omitted a logarithmic factor for simplicity). For given n and large enough m, (ϵ^-n/m) may be smaller than (ϵ^-log n). Conversely, however, for given m and large enough n, (ϵ^-n/m) may be greater than (ϵ^-log n).




§ DISCUSSION


We have proven upper bounds for the approximation of multivariate functions f:[0,1]^n→ by deep ReLU networks, for which the curse of dimensionality is lessened. The depth and the size of the networks to approximate such functions f grow like (ϵ^-log n), as opposed to (ϵ^-n). The proof is based on the ability of very deep ReLU networks to implement the Kolmogorov–Arnold superposition theorem.

There are many ways in which this work could be fruitfully continued. If we were able to construct a Lipschitz continuous inner function, we would be able to obtain (ϵ^-1) estimates. Actor and Knepley designed in 2017 an algorithm to compute a Lipschitz continuous inner function, but they did not provide a method to compute the outer functions <cit.>.

From a theoretical point of view, it would be interesting to investigate error bounds for deep networks with other activation functions (e.g., sigmoid and tanh). Some results about approximation by deep networks using smooth activation functions can be found in <cit.> and the references therein. Using these results, it would be possible to derive an analogue of Theorem <ref>. Let us highlight that, from a numerical point of view, only the ReLU activation function (combined with other tricks) can avoid the gradient degeneracy during network training.






§ ACKNOWLEDGEMENTS


The research of the second author is supported by the start-up grant of the Department of Mathematics at the National University of Singapore and by the Ministry of Education in Singapore under the grant MOE2018-T2-2-147.






