Optimal Approximation Rate of ReLU Networks in terms of Width and Depth

This paper concentrates on the approximation power of deep feed-forward neural networks in terms of width and depth. It is proved by construction that ReLU networks with width Obig(maxdlfloor N1/drfloor,, N+2big) and depth O(L) can approximate a H"older continuous function on [0,1]d with an approximation rate Obig(λ√d (N2L2ln N)-α/dbig), where α∈ (0,1] and λ>0 are H"older order and constant, respectively. Such a rate is optimal up to a constant in terms of width and depth separately, while existing results are only nearly optimal without the logarithmic factor in the approximation rate. More generally, for an arbitrary continuous function f on [0,1]d, the approximation rate becomes Obig(,√d,ωfbig( (N2L2ln N)-1/dbig),big), where ωf(·) is the modulus of continuity. We also extend our analysis to any continuous function f on a bounded set. Particularly, if ReLU networks with depth 31 and width O(N) are used to approximate one-dimensional Lipschitz continuous functions on [0,1] with a Lipschitz constant λ>0, the approximation rate in terms of the total number of parameters, W=O(N2), becomes O(tfracλWln W), which has not been discovered in the literature for fixed-depth ReLU networks.