2019/02/28 by Zuowei Shen, Haizhao Yang, Shijun Zhang · 1 citation
Computer Science · Mathematics · #cs.LG #stat.ML
paper · pdf · doi:10.1016/j.neunet.2019.07.011
published as Neural Networks, Volume 119, November 2019, Pages 74-84
arxiv created 2020/11/05 · arxiv updated 2020/11/06
Given a function dictionary \cal D and an approximation budget N∈ℕ+, nonlinear approximation seeks the linear combination of the best N terms \Tn\1≤ n≤ N⊆\cal D to approximate a given function f with the minimum approximation errorεL,f:=min_\gn\⊆ℝ,\Tn\⊆\cal D‖f(x)-∑n=1N gn Tn(x)‖.Motivated by recent success of deep learning, we propose dictionaries with functions in a form of compositions, i.e.,T(x)=T(L)∘ T(L-1)∘⋯∘ T(1)(x)for all T∈\cal D, and implement T using ReLU feed-forward neural networks (FNNs) with L hidden layers. We further quantify the improvement of the best N-term approximation rate in terms of N when L is increased from 1 to 2 or 3 to show the power of compositions. In the case when L>3, our analysis shows that increasing L cannot improve the approximation rate in terms of N. In particular, for any function f on [0,1], regardless of its smoothness and even the continuity, if f can be approximated using a dictionary when L=1 with the best N-term approximation rate εL,f=\cal O(N-η), we show that dictionaries with L=2 can improve the best N-term approximation rate to εL,f=\cal O(N-2η). We also show that for Hölder continuous functions of order α on [0,1]d, the application of a dictionary with L=3 in nonlinear approximation can achieve an essentially tight best N-term approximation rate εL,f=\cal O(N-2α/d). Finally, we show that dictionaries consisting of wide FNNs with a few hidden layers are more attractive in terms of computational efficiency than dictionaries with narrow and very deep FNNs for approximating Hölder continuous functions if the number of computer cores is larger than N in parallel computing.