Nonlinear Approximation via Compositions

Abstract

Given a function dictionary $\mathcal{D}$ and an approximation budget $N\in {\mathbb{N}}^{+}$, nonlinear approximation seeks the linear combination of the best $N$ terms $\{T_n{\}}_{1\le n\le N}\subseteq \mathcal{D}$ to approximate a given function $f$ with the minimum approximation error\[\varepsilon_{L,f}:=\min_{\{g_n\}\subseteq{\mathbb{R}},\{T_n\}\subseteq{\cal D}}\|f(x)-\sum_{n=1}^N g_n T_n(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)}\circ\cdots\circ T^{(1)}(x)\]for all $T\in \mathcal{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 ${\epsilon }_{L,f}=\mathcal{O}(N^{-\eta })$, we show that dictionaries with $L=2$ can improve the best $N$-term approximation rate to ${\epsilon }_{L,f}=\mathcal{O}(N^{-2\eta })$. We also show that for Hölder continuous functions of order $\alpha$ 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 ${\epsilon }_{L,f}=\mathcal{O}(N^{-2\alpha /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.

References in corpus (16)

• Adam: A Method for Stochastic Optimization
• Wide Residual Networks
• On the Number of Linear Regions of Deep Neural Networks
• Identifying and attacking the saddle point problem in high-dimensional non-convex optimization
• Aggregated Residual Transformations for Deep Neural Networks
• The loss surface of deep and wide neural networks
• Optimal approximation of continuous functions by very deep ReLU networks
• Approximating Continuous Functions by ReLU Nets of Minimal Width
• The Expressive Power of Neural Networks: A View from the Width
• The power of deeper networks for expressing natural functions
• Adaptivity of deep ReLU network for learning in Besov and mixed smooth Besov spaces: optimal rate and curse of dimensionality
• Depth with Nonlinearity Creates No Bad Local Minima in ResNets
• Approximation results in Orlicz spaces for sequences of Kantorovich max-product neural network operators
• Nonlinear Approximation Using Gaussian Kernels
• Greedy Deep Dictionary Learning
• Exponential Convergence of the Deep Neural Network Approximation for Analytic Functions

Cited by in corpus (29)

• Variational Physics-Informed Neural Networks For Solving Partial Differential Equations
• A Review on Deep Learning in Medical Image Reconstruction
• Deep Network Approximation for Smooth Functions
• Neural Network Approximation: Three Hidden Layers Are Enough
• Optimal Approximation Rate of ReLU Networks in terms of Width and Depth
• SelectNet: Self-paced Learning for High-dimensional Partial Differential Equations
• Int-Deep: A Deep Learning Initialized Iterative Method for Nonlinear Problems
• Deep Network with Approximation Error Being Reciprocal of Width to Power of Square Root of Depth
• Two-Layer Neural Networks for Partial Differential Equations: Optimization and Generalization Theory
• Full error analysis for the training of deep neural networks
• AdaSwarm: Augmenting Gradient-Based optimizers in Deep Learning with Swarm Intelligence
• Approximation Properties of Deep ReLU CNNs
• Factor Augmented Sparse Throughput Deep ReLU Neural Networks for High Dimensional Regression
• An error analysis of generative adversarial networks for learning distributions
• Approximation in shift-invariant spaces with deep ReLU neural networks
• Deep Nonparametric Regression on Approximate Manifolds: Non-Asymptotic Error Bounds with Polynomial Prefactors
• Deep Quantile Regression: Mitigating the Curse of Dimensionality Through Composition
• Power Series Expansion Neural Network
• Classification Logit Two-sample Testing by Neural Networks
• Are Two Hidden Layers Still Enough for the Physics-Informed Neural Networks?
• Robust Nonparametric Regression with Deep Neural Networks
• Finite-Sample Two-Group Composite Hypothesis Testing via Machine Learning
• Why Shallow Networks Struggle to Approximate and Learn High Frequencies
• Error bounds for PDE-regularized learning
• Non-asymptotic Excess Risk Bounds for Classification with Deep Convolutional Neural Networks
• A class of robust numerical methods for solving dynamical systems with multiple time scales
• On the optimal approximation of Sobolev and Besov functions using deep ReLU neural networks
• Structured and Balanced Multi-Component and Multi-Layer Neural Networks
• Just Least Squares: Binary Compressive Sampling with Low Generative Intrinsic Dimension