# Nonlinear Approximation via Compositions

arXiv: https://arxiv.org/abs/1902.10170 · HTML: https://mlsanity.com/paper/1902.10170/

## Key facts

- Cited by 38 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Feb 2019.

## Built on by (most cited first, 30 of 38)

- [Optimal Approximation Rate of ReLU Networks in terms of Width and Depth](https://mlsanity.com/paper/2103.00502/) (2021)
- [Operator Learning: Algorithms and Analysis](https://mlsanity.com/paper/2402.15715/) (2024)
- [An error analysis of generative adversarial networks for learning distributions](https://mlsanity.com/paper/2105.13010/) (2021)
- [Deep Network Approximation: Beyond ReLU to Diverse Activation Functions](https://mlsanity.com/paper/2307.06555/) (2023)
- [Nearly Optimal VC-Dimension and Pseudo-Dimension Bounds for Deep Neural Network Derivatives](https://mlsanity.com/paper/2305.08466/) (2023)
- [Wasserstein Generative Learning of Conditional Distribution](https://mlsanity.com/paper/2112.10039/) (2021)
- [Neural Network Architecture Beyond Width and Depth](https://mlsanity.com/paper/2205.09459/) (2022)
- [Approximation Properties of Deep ReLU CNNs](https://mlsanity.com/paper/2109.00190/) (2021)
- [Deeper or Wider: A Perspective from Optimal Generalization Error with Sobolev Loss](https://mlsanity.com/paper/2402.00152/) (2024)
- [On the Optimal Expressive Power of ReLU DNNs and Its Application in Approximation with Kolmogorov Superposition Theorem](https://mlsanity.com/paper/2308.05509/) (2023)
- [On the optimal approximation of Sobolev and Besov functions using deep ReLU neural networks](https://mlsanity.com/paper/2409.00901/) (2024)
- [Deep Network Approximation in Terms of Intrinsic Parameters](https://mlsanity.com/paper/2111.07964/) (2021)
- [Learning the Hodgkin-Huxley Model with Operator Learning Techniques](https://mlsanity.com/paper/2406.02173/) (2024)
- [Differentiable Neural Networks with RePU Activation: with Applications to Score Estimation and Isotonic Regression](https://mlsanity.com/paper/2305.00608/) (2023)
- [Approximation results for Gradient Descent trained Shallow Neural Networks in 1d](https://mlsanity.com/paper/2209.08399/) (2022)
- [On Enhancing Expressive Power via Compositions of Single Fixed-Size ReLU Network](https://mlsanity.com/paper/2301.12353/) (2023)
- [Deep Neural Networks with General Activations: Super-Convergence in Sobolev Norms](https://mlsanity.com/paper/2508.05141/) (2025)
- [Non-asymptotic Excess Risk Bounds for Classification with Deep Convolutional Neural Networks](https://mlsanity.com/paper/2105.00292/) (2021)
- [Higher Order Approximation Rates for ReLU CNNs in Korobov Spaces](https://mlsanity.com/paper/2501.11275/) (2025)
- [Fourier Multi-Component and Multi-Layer Neural Networks: Unlocking High-Frequency Potential](https://mlsanity.com/paper/2502.18959/) (2025)
- [Estimation of Non-Crossing Quantile Regression Process with Deep ReQU Neural Networks](https://mlsanity.com/paper/2207.10442/) (2022)
- [Structured and Balanced Multi-Component and Multi-Layer Neural Networks](https://mlsanity.com/paper/2407.00765/) (2024)
- [Are Two Hidden Layers Still Enough for the Physics-Informed Neural Networks?](https://mlsanity.com/paper/2412.19235/) (2024)
- [Inference for Deep Neural Network Estimators in Generalized Nonparametric Models](https://mlsanity.com/paper/2504.09347/) (2025)
- [Deep learning with missing data](https://mlsanity.com/paper/2504.15388/) (2025)
- [Some Super-approximation Rates of ReLU Neural Networks for Korobov Functions](https://mlsanity.com/paper/2507.10345/) (2025)
- [Just Least Squares: Binary Compressive Sampling with Low Generative Intrinsic Dimension](https://mlsanity.com/paper/2111.14486/) (2021)
- [Approximation Results for Gradient Descent trained Neural Networks](https://mlsanity.com/paper/2309.04860/) (2023)
- [Spectral Neural Networks: Approximation Theory and Optimization Landscape](https://mlsanity.com/paper/2310.00729/) (2023)
- [Layer-wise Geometric Approximation Rates for Deep Networks](https://mlsanity.com/paper/2604.20219/) (2026)

## Abstract (arXiv)

Given a function dictionary cal D and an approximation budget N∈mathbbN^+, nonlinear approximation seeks the linear combination of the best N terms Tn1≤ n≤ Nsubseteqcal D to approximate a given function f with the minimum approximation error[varepsilonL,f:=min_gnsubseteqℝ,Tnsubseteqcal D|f(x)-sumn=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)circ T(L-1)circcdotscirc 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 varepsilonL,f=cal O(N-η), we show that dictionaries with L=2 can improve the best N-term approximation rate to varepsilonL,f=cal O(N-2η). We also show that for H"older 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 varepsilonL,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"older continuous functions if the number of computer cores is larger than N in parallel computing.