Source-linked AI summary
Neural Network Approximation: Three Hidden Layers Are Enough
Zuowei Shen, Haizhao Yang, Shijun Zhang
TL;DR
The paper addresses how neural networks can achieve strong approximation with fixed shallow depth while controlling dimensional dependence. It constructs three-hidden-layer FLES networks from simple activation functions and proves exponential approximation rates for continuous and Hölder functions. It also extends the analysis to bounded domains and to L^p approximation using continuous activations, while noting scope limitations for L∞ extensions with three layers.
Problem
The paper studies whether fixed-depth neural networks can achieve super approximation power and avoid the curse of dimensionality for broad continuous-function classes.
Method
The paper constructs three-hidden-layer FLES networks using floor, exponential, step, or composed activation functions, and replaces them with continuous activations for L^p analysis.
Results
FLES networks with width max{d,N} achieve constructive exponential approximation for continuous functions, including the Lipschitz rate 6λ√d2^-N, and the results extend to bounded sets.
Takeaways & Limitations
Three hidden layers suffice within this construction to obtain exponential convergence and avoid the curse of dimensionality when the modulus of continuity is moderate.
Takeaways & Limitations
The continuous-activation analysis gives L^p error for p∈[1,∞), while extending it to L∞ requires 2d+3 hidden layers and is left for future work.
Abstract
from arXiv · showhide
A three-hidden-layer neural network with super approximation power is introduced. This network is built with the floor function ($\lfloor x\rfloor$), the exponential function ($2^x$), the step function ($1_{x\geq 0}$), or their compositions as the activation function in each neuron and hence we call such networks as Floor-Exponential-Step (FLES) networks. For any width hyper-parameter $N\in\mathbb{N}^+$, it is shown that FLES networks with width $\max\{d,N\}$ and three hidden layers can uniformly approximate a Hölder continuous function $f$ on $[0,1]^d$ with an exponential approximation rate $3λ(2\sqrt{d})^α 2^{-αN}$, where $α\in(0,1]$ and $λ>0$ are the Hölder order and constant, respectively. More generally for an arbitrary continuous function $f$ on $[0,1]^d$ with a modulus of continuity $ω_f(\cdot)$, the constructive approximation rate is $2ω_f(2\sqrt{d}){2^{-N}}+ω_f(2\sqrt{d}\,2^{-N})$. Moreover, we extend such a result to general bounded continuous functions on a bounded set $E\subseteq\mathbb{R}^d$. As a consequence, this new class of networks overcomes the curse of dimensionality in approximation power when the variation of $ω_f(r)$ as $r\rightarrow 0$ is moderate (e.g., $ω_f(r)\lesssim r^α$ for Hölder continuous functions), since the major term to be concerned in our approximation rate is essentially $\sqrt{d}$ times a function of $N$ independent of $d$ within the modulus of continuity. Finally, we extend our analysis to derive similar approximation results in the $L^p$-norm for $p\in[1,\infty)$ via replacing Floor-Exponential-Step activation functions by continuous activation functions.
1. Introduction
The paper introduces FLES networks that use three hidden layers and suitable simple activation functions to obtain constructive, quantitative approximation results with exponential convergence and reduced dimensional dependence.
- Motivation: The paper targets super approximation capacity with three-hidden-layer neural networks, using explicit formulas and error bounds for arbitrary widths.The stated framework is constructive and quantitative, with network parameters specified explicitly.
- FLES networks: FLES networks combine the floor, exponential, step, or composed activation functions in fully connected feed-forward architectures.The three activation functions are denoted σ1, σ2, and σ3; the paper identifies σ1(x)=⌊x⌋ and σ2(x)=2^x.
- Main construction: Theorem 1.1 uses width max{d,N} and three hidden layers to approximate continuous functions on [0,1]^d, with the construction determined by N parameters.The parameters can be trained by a network with 2(d+N+1) nonzero parameters.
- Approximation rates: 3λ(2√d)^α2^-αN is the stated Hölder approximation rate for order α∈(0,1] and constant λ>0.For Lipschitz functions, the paper further specializes the rate to 6λ√d2^-N.
- Implications: Increasing width yields exponential improvement, while the dimensional dependence is essentially √d multiplied by a function of N within the modulus of continuity.The paper presents this behavior as avoiding the curse of dimensionality when the modulus of continuity varies moderately.
- Scope and context: The theory extends to general bounded continuous functions on bounded sets and connects approximation bounds with network size and VC-dimension.The introduction also notes that the paper compares its rates with prior ReLU and Floor-ReLU approximation results.
2. Discussion
The discussion positions FLES approximation bounds as size-dependent guarantees distinct from optimization and generalization analysis, while examining dimensionality, VC-dimension, domain extensions, and practical limitations. It also identifies trade-offs between simple activations, explicit parameters, and approximation performance.
- Application scope: Constructive approximation bounds depend on FLES network size rather than empirical-loss minimization or the optimization algorithm.These bounds quantify approximation power for a given number of neurons and layers, while optimization and generalization require separate analyses.
- VC-dimension: Large VC-dimension is necessary but insufficient for good approximation, because the hypothesis space must also have suitable properties.The cosine family provides a counterexample: despite its flexibility, it cannot achieve good approximation error for Hölder continuous functions.
- Domain extension: FLES networks extend the approximation theory to bounded continuous functions on E ⊆ [−R,R]^d, where domain volume has only a mild influence on the rate.For Hölder functions on such domains, the paper reports continued avoidance of the curse of dimensionality and exponential convergence when R > 1.
- Modulus of continuity: The modulus of continuity determines whether exponential convergence and dimensionality control persist; moderate moduli support both, whereas immoderate examples can cancel exponential convergence.The paper gives logarithmic moduli as examples where dimensionality may still be controlled but exponential convergence is lost, while another constructed case retains both only for very wide networks.
- Practical limitations: Practical use is constrained by high-precision weight requirements and vanishing gradients from piecewise-constant activations.The paper suggests gradient-free, quantized-network, or straight-through-estimator approaches as possible directions for optimization.
- Comparison with KST-related methods: FLES networks trade some approximation-rate performance for simpler activation functions and explicit parameter formulas.The paper frames this as a trade-off between activation complexity and network size at fixed approximation error.
3. Theoretical Analysis
The theoretical analysis constructs a three-hidden-layer approximation by partitioning the domain, encoding cube indices, fitting sampled function values, and composing the resulting maps. The construction uses Floor-Exponential-Step activations and establishes approximation through a five-step proof strategy.
- Proof construction: The proof reduces approximation to five steps: normalize the function, partition the domain, encode cube indices, fit sampled values, and compose the maps.The resulting piecewise-constant approximation is finally rescaled and shifted to approximate the original function.
- Proof construction: A vector-valued map Φ1 projects every point in cube Qβ to its index β, while φ2 bijectively maps β to an integer in {1,2,⋯,J^d}.This converts spatial locations into discrete indices that can be processed by the subsequent scalar map.
- Activation mechanism: The activation functions are σ1(x)=⌊x⌋, σ2(x)=2^x, and a step-based σ3, whose combination supports the bit-extraction construction.Proposition 3.2 states that σ3(a·σ2(k)) can recover arbitrary binary values θk, and the resulting function space has infinite VC-dimension.
- Proof construction: The domain [0,1)^d is divided into J^d non-overlapping cubes, with J=2^N and each cube indexed by its lower vertex.The cube partition supplies the local representatives used to approximate the target function.
- Proof construction: The scalar map φ3 sends each encoded cube index approximately to the normalized sampled value f̃(xβ), producing a piecewise-constant approximation through φ3○φ2○Φ1.The construction then rescales and shifts this approximation to obtain the final function.
4. Approximation with continuous activation functions
The paper replaces piecewise-constant FLES activations with continuous activation functions and constructs three-hidden-layer networks with Lp approximation guarantees. The construction partitions the domain into cubes, encodes cube indices, and combines continuous modules to approximate the target.
- Motivation: The paper introduces continuous activation functions to address numerical challenges caused by piecewise-constant FLES activations.The continuous-activation analysis targets similar approximation results while retaining three hidden layers.
- Activation functions: The function ϱ1,δ is a continuous version of the floor function, while ϱ2(x)=3^x and ϱ3(x)=T̃(cos(2πx)) provide the remaining activation roles.The paper states that ϱ2 plays the same role as σ2(x)=2^x.
- Result: Theorem 4.1 establishes approximation in the Lp-norm for p∈[1,∞) using the continuous activation construction.The theorem applies to arbitrary continuous functions on [0,1]^d and permits any δ∈(0,1) and N∈N+.
- Limitation: Unlike Theorem 1.1’s pointwise estimate, this result is stated in Lp-norm; extending it to L∞ would require 2d+3 hidden layers.The paper leaves the L∞ extension for future work because its focus is three-hidden-layer approximation.
- Construction: The construction divides [0,1]^d into J^d cubes, associates each cube with a vertex xβ, and maps points in each cube to its index β.This indexing is implemented through the first construction module and an affine encoding map.
- Construction: The network assigns sampled target values ξk=f̃(xβ) to encoded cube indices and composes three modules to form an approximation.The final composition is f̃φ=φ3○φ2○Φ1, followed by rescaling and shifting to approximate f.
5. Conclusion
The paper argues that three-hidden-layer FLES networks can achieve exponential approximation and avoid the curse of dimensionality for broad continuous-function classes. It also extends the analysis to bounded domains and Lp approximation with continuous activations, while noting computational achievability remains open.
- Conclusion: Three-hidden-layer FLES networks use floor, exponential, step, or composed activations to obtain super approximation power.The framework targets functions as general as Hölder-continuous functions.
- Conclusion: For Lipschitz functions, the networks achieve a uniform approximation rate proportional to 6λ√d2^-N with width max{d,N}.Here λ is the Lipschitz constant of f.
- Conclusion: For arbitrary continuous functions, the constructive rate is expressed through the modulus of continuity ωf and extends to bounded continuous functions on bounded sets E⊆R^d.The conclusion states the modulus-based rate and the bounded-domain extension together.
- Conclusion: The paper also derives analogous approximation results in the Lp-norm for p∈[1,∞) using continuous activation functions.This complements the pointwise FLES approximation framework with a continuous-activation variant.
- Limitation: Whether the theoretical approximation bound is achievable in actual computation depends on advanced algorithm design outside this analysis.The paper identifies computational achievability as a separate research direction.