Optimal approximation of piecewise smooth functions using deep ReLU\n neural networks

2017/09/15 by Philipp Petersen, Petersen, Philipp, Felix Voigtlaender +1 · 27 citations
Computer Science · Engineering · Mathematics · #41A10 #41A25 #41A46 #68T05 #82C32 #Advanced Numerical Analysis Techniques #Artificial intelligence #Artificial neural network #Combinatorics #Computer science #Dimension (graph theory) #Discrete mathematics #Enhanced Oil Recovery Techniques #FOS: Computer and information sciences #FOS: Mathematics #Function (biology) #Functional Analysis (math.FA) #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Mathematical analysis #Mathematics #Multiplicative function #Piecewise #cs.LG #math.FA #msc:41A10 #msc:41A25 #msc:41A46 #msc:68T05 #msc:82C32 #stat.ML

paper · pdf · doi:10.48550/arxiv.1709.05289

published in arXiv (Cornell University) (Cornell University) · Generalized some estimates to $L^p$ norms for $0<p<\infty$

openalex publication_date 2017/09/15 · arxiv created 2018/05/22 · arxiv updated 2018/05/23 · openalex created_date 2022/09/24 · openalex updated_date 2026/08/06

Abstract

We study the necessary and sufficient complexity of ReLU neural networks---in\nterms of depth and number of weights---which is required for approximating\nclassifier functions in L². As a model class, we consider the set\n\E^\β ( mathbb R^d) of possibly discontinuous piecewise C^\β\nfunctions f : [-1/2, 1/2]^d \→ mathbb R, where the different smooth regions\nof f are separated by C^\β hypersurfaces. For dimension d \≥ 2,\nregularity \β &gt; 0, and accuracy \ε &gt; 0, we construct artificial\nneural networks with ReLU activation function that approximate functions from\n\E^\β( mathbb R^d) up to L² error of \ε. The\nconstructed networks have a fixed number of layers, depending only on d and\n\β, and they have O(\ε^-2(d-1)/\β) many nonzero weights,\nwhich we prove to be optimal. In addition to the optimality in terms of the\nnumber of weights, we show that in order to achieve the optimal approximation\nrate, one needs ReLU networks of a certain depth. Precisely, for piecewise\nC^\β( mathbb R^d) functions, this minimal depth is given---up to a\nmultiplicative constant---by \β/d. Up to a log factor, our constructed\nnetworks match this bound. This partly explains the benefits of depth for ReLU\nnetworks by showing that deep networks are necessary to achieve efficient\napproximation of (piecewise) smooth functions. Finally, we analyze\napproximation in high-dimensional spaces where the function f to be\napproximated can be factorized into a smooth dimension reducing feature map\n\τ and classifier function g---defined on a low-dimensional feature\nspace---as f = g \∘ \τ. We show that in this case the approximation rate\ndepends only on the dimension of the feature space and not the input dimension.\n

Cited by

• Approximation bounds for norm constrained deep neural networks
• Time-Frequency Analysis for Neural Networks
• Approximation with SiLU Networks: Constant Depth and Exponential Rates for Basic Operations
• Incremental Generation is Necessary and Sufficient for Universality in Flow-Based Modelling
• Learning Low Rank Neural Representations of Hyperbolic Wave Dynamics from Data
• General transformation neural networks: A class of parametrized functions for high-dimensional function approximation
• Neural Network approximation power on homogeneous and heterogeneous reaction-diffusion equations
• Average Kernel Sizes -- Computable Sharp Accuracy Bounds for Inverse Problems
• A signal separation view of classification
• A convergence framework for energy minimisation of linear self-adjoint elliptic PDEs in nonlinear approximation spaces
• Error analysis for the deep Kolmogorov method
• Barycentric Neural Networks and Length-Weighted Persistent Entropy Loss: A Green Geometric and Topological Framework for Function Approximation
• Beyond Universal Approximation Theorems: Algorithmic Uniform Approximation by Neural Networks Trained with Noisy Data
• Physics Matters in PnP: Recovery Guarantees with the MMSE and NN Denoisers
• Neural Measures for learning distributions of Random PDEs
• On the algorithmic construction of deep ReLU networks
• Strategic Classification with Non-Linear Classifiers
• Time to Spike? Understanding the Representational Power of Spiking Neural Networks in Discrete Time
• Residual Feature Integration is Sufficient to Prevent Negative Transfer
• SAD Neural Networks: Divergent Gradient Flows and Asymptotic Optimality via o-minimal Structures
• Super-fast rates of convergence for Neural Networks Classifiers under the Hard Margin Condition
• Extended Fiducial Inference for Individual Treatment Effects via Deep Neural Networks
• Universal Approximation Theorem of Deep Q-Networks
• Adaptivity Under Realizability Constraints: Comparing In-Context and Agentic Learning
• Stochastic Neural Networks for Causal Inference with Missing Confounders
• Generative Market Equilibrium Models with Stable Adversarial Learning via Reinforcement
• Follow the MEP: Scalable Neural Representations for Minimum-Energy Path Discovery in Molecular Systems

Related

• Optimal Approximation Complexity of High-Dimensional Functions with Neural Networks
• ReLU neural network approximation to piecewise constant functions
• Deep ReLU neural networks in high-dimensional approximation
• Approximation in L^p(μ) with deep ReLU neural networks
• Sharp Representation Theorems for ReLU Networks with Precise Dependence on Depth