Deep Network with Approximation Error Being Reciprocal of Width to Power of Square Root of Depth

A new network with super approximation power is introduced. This network is built with Floor (lfloor xrfloor) or ReLU (max0,x) activation function in each neuron and hence we call such networks Floor-ReLU networks. For any hyper-parameters N∈mathbbN^+ and L∈mathbbN^+, it is shown that Floor-ReLU networks with width maxd,, 5N+13 and depth 64dL+3 can uniformly approximate a H"older function f on [0,1]d with an approximation error 3λ dα/2N^-α√L, where α ∈(0,1] and λ are the H"older order and constant, respectively. More generally for an arbitrary continuous function f on [0,1]d with a modulus of continuity ωf(·), the constructive approximation rate is ωf(√d,N^-√L)+2ωf(√d)N^-√L. As a consequence, this new class of networks overcomes the curse of dimensionality in approximation power when the variation of ωf(r) as r→ 0 is moderate (e.g., ωf(r) lesssim rα for H"older continuous functions), since the major term to be considered in our approximation rate is essentially √d times a function of N and L independent of d within the modulus of continuity.