Nonlinear approximation via compositions

DOI10.1016/J.NEUNET.2019.07.011MaRDI QIDQ2185653zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Zuowei Shen, Haizhao Yang, Shijun Zhang

Publication date 5 June 2020

Published in Neural Networks (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1902.10170

zbMATH Keywords

deep neural networksfunction compositionHölder continuitynonlinear approximationparallel computingReLU activation function

Mathematics Subject Classification ID

Functional equations in the complex plane, iteration and composition of analytic functions of one complex variable (30D05) Special approximation methods (nonlinear Galerkin, etc.) for infinite-dimensional dissipative dynamical systems (37L65) Rate of convergence, degree of approximation (41A25) Multidimensional problems (41A63) Artificial neural networks and deep learning (68T07)

Abstract: Given a function dictionary $calD$ and an approximation budget $Ninmathbb{N}^{+}$, nonlinear approximation seeks the linear combination of the best $N$ terms ${T_n}_{1lenleN}subseteqcalD$ 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)}circcdotscirc T^{(1)}(x)]for all $TincalD$, 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 $varepsilo{n}_{L,f}=calO(N^{-eta})$, we show that dictionaries with $L=2$ can improve the best $N$-term approximation rate to $varepsilo{n}_{L,f}=calO(N^{-2eta})$. We also show that for H"older 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 $varepsilo{n}_{L,f}=calO(N^{-2alpha/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.

Review text

Given a function dictionary 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 D\) to approximate a given function \(f\) with the minimum approximation error. Motivated by recent success of deep learning, authors propose dictionaries with functions in a form of compositions, and implement T using ReLU feed-forward neural networks (FNNs) with L hidden layers. They further quantify the improvement of the best \(N\)-term approximation rate in terms of \(N\) when \(L\). Finally, they 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.

Recommendations

• Nonlinear approximation and (deep) ReLU networks
• Nonlinear methods of approximation
• Function approximation by deep networks
• Deep network approximation characterized by number of neurons
• Function approximation by deep neural networks with parameters \(\{0, \pm \frac{1}{2}, \pm 1,2\}\)

Cites work

• Adaptive subgradient methods for online learning and stochastic optimization
• Almost optimal estimates for approximation and learning by radial basis function networks
• Approximation by superpositions of a sigmoidal function
• Approximation of functions of finite variation by superpositions of a sigmoidal function.
• Approximation results in Orlicz spaces for sequences of Kantorovich MAX-product neural network operators
• Approximation using scattered shifts of a multivariate function
• Compressed sensing
• Constructive approximate interpolation by neural networks
• Convergence for a family of neural network operators in Orlicz spaces
• Efficient distribution-free learning of probabilistic concepts
• Error bounds for approximations with deep ReLU networks
• Exponential convergence of the deep neural network approximation for analytic functions
• scientific article; zbMATH DE number 1215245 (Why is no real title available?)
• Matching pursuits with time-frequency dictionaries
• Multilayer feedforward networks are universal approximators
• Multivariate n-term rational and piecewise polynomial approximation
• Neocognition: A self-organizing neural network model for a mechanism of pattern recognition unaffected by shift in position
• Nonlinear approximation using Gaussian kernels
• Optimal approximation of piecewise smooth functions using deep ReLU neural networks
• Saturation classes for MAX-product neural network operators activated by sigmoidal functions
• Ten Lectures on Wavelets
• The rate of approximation of Gaussian radial basis neural networks in continuous function space
• Universal approximation bounds for superpositions of a sigmoidal function

Cited in

(43)

• Chebyshev approximation of multivariable functions by the exponential expression
• Optimal approximation rate of ReLU networks in terms of width and depth
• Int-Deep: a deep learning initialized iterative method for nonlinear problems
• SelectNet: self-paced learning for high-dimensional partial differential equations
• Approximation properties of deep ReLU CNNs
• A review on deep learning in medical image reconstruction
• Can dictionary-based computational models outperform the best linear ones?
• Deep network with approximation error being reciprocal of width to power of square root of depth
• Finite-Sample Two-Group Composite Hypothesis Testing via Machine Learning
• Convergence rate analysis for deep Ritz method
• Deep ReLU Networks Overcome the Curse of Dimensionality for Generalized Bandlimited Functions
• Full error analysis for the training of deep neural networks
• Deep Network Approximation for Smooth Functions
• Deep network approximation characterized by number of neurons
• Neural network approximation
• Simultaneous neural network approximation for smooth functions
• Deep Neural Networks for Solving Large Linear Systems Arising from High-Dimensional Problems
• Neural network approximation: three hidden layers are enough
• A deep network construction that adapts to intrinsic dimensionality beyond the domain
• Overall error analysis for the training of deep neural networks via stochastic gradient descent with random initialisation
• Just least squares: binary compressive sampling with low generative intrinsic dimension
• Deep nonparametric regression on approximate manifolds: nonasymptotic error bounds with polynomial prefactors
• Deep learning via dynamical systems: an approximation perspective
• Approximation in shift-invariant spaces with deep ReLU neural networks
• Approximation properties of Gaussian-binary restricted Boltzmann machines and Gaussian-binary deep belief networks
• An efficient numerical method for solving dynamical systems with multiple time scales
• Learning the Hodgkin-Huxley model with operator learning techniques
• Approximation results for gradient flow trained shallow neural networks in \(1d\)
• Factor Augmented Sparse Throughput Deep ReLU Neural Networks for High Dimensional Regression
• Approximation and gradient descent training with neural networks
• Why shallow networks struggle to approximate and learn high frequencies
• Structured and balanced multicomponent and multilayer neural networks
• Neural networks meet random forests
• On the optimal approximation of Sobolev and Besov functions using deep ReLU neural networks
• Are two hidden layers still enough for the physics-informed neural networks?
• Local manifold approximation of dynamical system based on neural ordinary differential equation
• Approximation results for gradient flow trained neural networks
• Deep approximate policy iteration
• Finite-difference least square methods for solving Hamilton-Jacobi equations using neural networks
• Spectral neural networks: approximation theory and optimization landscape
• Neural base-N encoding for solving massive nonlinear systems
• Some super-approximation rates of ReLU neural networks for Korobov functions
• Universal dynamical system for brain modeling

Describes a project that uses

Uses Software

• AdaGrad

This page was built for publication: Nonlinear approximation via compositions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2185653)