Source-linked AI summary
Deep Network Approximation for Smooth Functions
Jianfeng Lu, Zuowei Shen, Haizhao Yang, Shijun Zhang
TL;DR
The paper addresses how smoothly target functions improve deep ReLU approximation when width and depth are controlled simultaneously. It constructs polynomial and local Taylor approximations, obtaining nearly optimal non-asymptotic error bounds for smooth functions. The analysis supplies an approximation component for deep-learning error bounds while remaining scoped to fully connected feed-forward ReLU networks.
Problem
Existing approximation results did not fully characterize deep ReLU networks in terms of width and depth simultaneously, although these are the architecture parameters used in practice.
Method
The paper constructs ReLU approximators using polynomial approximation, local Taylor expansions, and a technique that extends accurate approximation outside a small region to uniform approximation on the whole domain.
Results
O(∥f∥_{C^s([0,1]^d)}N^-2s/dL^-2s/d) bounds the approximation component for smooth functions with network width O(N ln N) and depth O(L ln L).
Takeaways & Limitations
The width-and-depth characterization provides an upper bound for the approximation error component relevant to analyzing the expected inference error of learned networks.
Takeaways & Limitations
The analysis covers fully connected feed-forward ReLU networks; generalization to other architectures and activation functions remains future work.
Abstract
from arXiv · showhide
This paper establishes the (nearly) optimal approximation error characterization of deep rectified linear unit (ReLU) networks for smooth functions in terms of both width and depth simultaneously. To that end, we first prove that multivariate polynomials can be approximated by deep ReLU networks of width $\mathcal{O}(N)$ and depth $\mathcal{O}(L)$ with an approximation error $\mathcal{O}(N^{-L})$. Through local Taylor expansions and their deep ReLU network approximations, we show that deep ReLU networks of width $\mathcal{O}(N\ln N)$ and depth $\mathcal{O}(L\ln L)$ can approximate $f\in C^s([0,1]^d)$ with a nearly optimal approximation error $\mathcal{O}(\|f\|_{C^s([0,1]^d)}N^{-2s/d}L^{-2s/d})$. Our estimate is non-asymptotic in the sense that it is valid for arbitrary width and depth specified by $N\in\mathbb{N}^+$ and $L\in\mathbb{N}^+$, respectively.
1 Introduction
The paper characterizes deep ReLU approximation of smooth functions using width and depth simultaneously, improving error rates through constructive polynomial and local Taylor approximations. It provides nearly optimal, non-asymptotic bounds and discusses their practical scope and limitations.
- 1.1 Main result: O(N^-2s/d L^-2s/d) approximation error is achieved for C^s([0,1]^d) functions using ReLU networks of width O(N ln N) and depth O(L ln L).The theorem is valid for arbitrary positive integers N and L, with explicit width and depth constructions.
- 1.1 Main result: Smoothness improves the N and L rates; for s ≥ d, N^-2s/d L^-2s/d ≤ N^-2 L^-2.The improved rate comes with a substantially larger prefactor when s ≥ d.
- 1.2 Contributions and related work: The construction targets width and depth separately, unlike parameter-count bounds that do not determine which widths and depths realize a given network size.This directly addresses width and depth as practical architecture hyperparameters and covers wide fixed-depth and deep fixed-width regimes.
- 1.2 Contributions and related work: Nearly optimal error O(N^-2s/d L^-2s/d) is supported by a VC-dimension-based lower bound for the unit ball of C^s([0,1]^d).The upper and lower bounds together establish asymptotic near-tightness for this function class.
- 1.2 Contributions and related work: O(N^-L) error approximates multivariate polynomials with ReLU networks of width O(N) and depth O(L).This extends the fixed-width depth rate O(2^-L) reported in prior work.
- 1.3 Discussion: The analysis is limited to fully connected feed-forward ReLU networks, leaving other architectures and activation functions for future work.The paper also notes that its constructive weight-selection map is not continuous under the stated approximation regime.
2 Approximation of smooth functions
The section proves Theorem 1.1 by constructing deep ReLU networks whose width- and depth-dependent approximation error for smooth functions is nearly optimal, then establishes tightness using VC-dimension.
- Proof strategy: The trifling region addresses the inability of continuous ReLU networks to uniformly approximate step functions, which complicates L∞ approximation.The technique enables separate control outside the region and recovery of a global uniform bound after modest network enlargement.
- Proof strategy: Theorem 2.1 and Theorem 2.2 combine to prove Theorem 1.1 by controlling approximation inside and outside the trifling region.The proof first extends approximation across the trifling region, then constructs a network approximating smooth functions away from it.
- Optimality: VC-dimension bounds yield matching lower bounds, showing the Theorem 1.1 and Corollary 1.2 approximation rates are nearly optimal.The argument connects approximation error for C^s functions to VCDim(F)^-s/d and applies ReLU-network VC-dimension estimates.
3 Proof of Theorem 2.1
The proof of Theorem 2.1 converts approximation outside a small trifling region into uniform approximation on the entire domain by composing coordinatewise middle-value operations.
- One-dimensional construction: The one-dimensional construction evaluates g(x − δ), g(x), and g(x + δ), then applies the middle-value function to bypass the trifling intervals.The argument partitions [0,1] into K intervals and handles boundary cases separately.
- One-dimensional construction: A middle-value ReLU network maps three inputs to their median with width 14 and depth 2.The construction uses ReLU representations of max and min to implement mid(x1,x2,x3).
- One-dimensional construction: If at least two inputs lie within ε of a target value, their middle value also lies within ε of that target.This property prevents a single inaccurate input from spoiling the output.
- Multidimensional extension: In d dimensions, functions φ_i are defined recursively by φ_i+1(x) = mid(φ_i(x − δe_i+1), φ_i(x), φ_i(x + δe_i+1)).Each recursion step removes the trifling-region restriction in one coordinate.
- Multidimensional extension: After d coordinatewise steps, φ_d uniformly approximates f on [0,1]^d within ε + d·ω_f(δ).The induction proceeds from E_0, the domain outside the trifling region, to E_d, the full cube.
- Network size: The resulting ReLU FNN has width 3d(N + 4) and depth L + 2d when the original approximation network has width N and depth L.Each coordinatewise middle-value composition adds two layers and expands width by a factor controlled by d.
4 Proof of Theorem 2.2
The proof partitions the domain, approximates local Taylor data with ReLU subnetworks, and combines these components to achieve the target width–depth error rate.
- Domain partition: K = O(N^(2/d)L^(2/d)) partitions [0,1]^d into cubes, while approximation is required only outside the trifling region.The cube vertices x_β provide local expansion centers.
- Error estimate: The Taylor remainder is O(K^(-s)) = O(N^(-2s/d)L^(-2s/d)), matching the target approximation scale.The final construction combines the remainder and network approximation errors, with a dimension-dependent prefactor.
- Local Taylor approximation: The construction approximates local Taylor coefficients ∂^αf at every cube vertex with error O(N^(-2s/d)L^(-2s/d)).Each approximant φ_α is obtained by solving a point-fitting problem over the vertices.
- Polynomial subnetworks: O(N) width and O(L) depth suffice for polynomial approximation with error O(N^(-L)).This proposition supplies the polynomial subnetwork used in the Taylor construction.
- Localization map: O(N) width and O(L) depth approximate the one-dimensional step functions needed to implement the multidimensional localization map Ψ.The construction uses O(K) steps with K determined by N and L.
- Point fitting: O(sN ln N) width and O(L ln L) depth fit the required point values with error N^(-2s)L^(-2s).This point-fitting result supplies the subnetworks for the Taylor coefficients.
5 Proofs of Propositions in Section 4.1
The propositions are proved constructively through sawtooth-based square approximation, polarization for multiplication, induction for products, and bit-extraction-based point fitting.
- Multiplication: The square approximator yields xy through xy = 2((x+y)/2)^2 − (x/2)^2 − (y/2)^2.The resulting multiplication network has width 9N and depth L, with error bounded by 6N^(-L) on [0,1]^2.
- General polynomials: General monomials are represented as products with constant entries and affine-transformed inputs, extending the product construction to multivariate polynomials.The polynomial approximation proposition then follows by combining monomial subnetworks.
- Approximation rate: The construction generalizes earlier sawtooth results from fixed width and O(2^(-L)) error to arbitrary width O(N), depth O(L), and O(N^(-L)) error.The improvement is attributed to function composition and the resulting polynomial approximation accuracy.
- Square approximation: ReLU FNNs with width 3N and depth L approximate x^2, using compositions of piecewise-linear sawtooth functions.Identity-activation layers can be merged, preserving the stated depth interpretation.
- Rescaled multiplication: On [a,b]^2, rescaling the multiplication construction gives width 9N + 1, depth L, and error 6N^(-L).The architecture includes identity-activation layers that reduce the interpreted depth.
- Multivariate products: Products of k variables are approximated by induction with width 9(N + 1) + k − 1 and depth 7kL(k − 1).Each induction step composes the previous product approximator with a two-variable multiplication network.
- Point fitting: Point fitting uses bit extraction and composition to fit many points with substantially fewer parameters than a one-hidden-layer network.A one-hidden-layer ReLU network can fit n points with O(n) parameters, whereas Proposition 4.4 targets O(n) points with fewer parameters.
6 Conclusions
The paper establishes nearly optimal width–depth approximation rates for smooth functions with fully connected ReLU networks, while identifying architectural and dimensional scope boundaries.
- Main conclusion: Width O(N ln N) and depth O(L ln L) achieve error O(N^(-2s/d)L^(-2s/d)) for the unit ball of C^s([0,1]^d).The rate is asymptotically nearly tight by a VC-dimension argument.
- Scope: The analysis applies to fully connected feed-forward networks with ReLU activation and does not yet cover other architectures or activation functions.Convolutional networks, ResNets, tanh, and sigmoid are identified as future directions.