Source-linked AI summary
Deep vs. shallow networks : An approximation theory perspective
Hrushikesh Mhaskar, Tomaso Poggio
TL;DR
The paper asks when deep networks approximate functions more efficiently than shallow networks and develops a compositional approximation framework based on directed acyclic graphs. It extends this analysis to ReLU and Gaussian networks, and introduces relative dimension to quantify exploitable sparsity, with Gaussian-network results tied to smoothness and center separation.
Problem
The paper addresses the missing theory explaining which function classes deep convolutional networks approximate well and why their approximation complexity can differ from shallow networks.
Method
It models deep architectures as directed acyclic graphs, analyzes compositional and scalable functions, studies ReLU and Gaussian approximation, and defines relative dimension for sparsity.
Results
The paper reports that hierarchical compositional targets can achieve approximation accuracy ϵ with O(ϵ−2/r) deep-network parameters instead of O(ϵ−q/r) for general shallow approximation, and introduces new ReLU and Gaussian results.
Takeaways & Limitations
Deep architectures can exploit compositional, scalable, and other sparse representations that shallow networks may not capture as efficiently; relative dimension formalizes this difference.
Takeaways & Limitations
The Gaussian-network smoothness framework requires conditions on derivative decay at infinity, not only a derivative count.
Abstract
from arXiv · showhide
The paper briefy reviews several recent results on hierarchical architectures for learning from examples, that may formally explain the conditions under which Deep Convolutional Neural Networks perform much better in function approximation problems than shallow, one-hidden layer architectures. The paper announces new results for a non-smooth activation function - the ReLU function - used in present-day neural networks, as well as for the Gaussian networks. We propose a new definition of relative dimension to encapsulate different notions of sparsity of a function class that can possibly be exploited by deep networks but not by shallow ones to drastically reduce the complexity required for approximation and learning.
1 Introduction
The paper addresses why deep convolutional networks can outperform shallow networks in approximation, focusing on compositional structure, ReLU and Gaussian networks, and relative dimension.
- The paper identifies which functions deep convolutional networks approximate well and why deep networks can outperform shallow architectures as central theoretical questions.
- The framework models deep networks as directed acyclic graphs and analyzes approximation for compositional functions with small maximal node indegree.Such structures can bypass the curse of dimensionality through compositionality.
- The paper reviews earlier sigmoidal-network results and announces new approximation results for ReLU and Gaussian activation functions.
- Relative dimension is proposed to quantify sparsity notions that deep networks may exploit but shallow networks may not.The goal is to characterize when this structure can reduce approximation and learning complexity.
2 Compositional functions
Compositional and scalable shift-invariant functions naturally admit hierarchical representations, allowing deep networks to approximate them more efficiently than unstructured shallow networks under suitable smoothness assumptions.
- 2.1 Motivation: Image locality, shift invariance, and scale-related invariances motivate repeated local processors and hierarchical visual computations.
- 2.1 Motivation: Scalable visual algorithms can adapt to changing image size by adding or removing reusable parts without changing their basic computational form.
- 2.1 Motivation: Scalable, shift-invariant functions on R2m have a multilayer composition of local functions, with repeated blocks across each layer.Each block maps R2 to R, as illustrated by Figure 1.
- 2.2 An example: A binary-tree compositional function combines pairs of inputs recursively through constituent functions such as h11, h12, h13, h14, h21, h22, and h3.
- 2.2 An example: The approximation argument uses local shallow subnetworks for constituent functions and propagates their errors through the hierarchical composition.
- 2.2 An example: For smooth target functions without assumed hierarchy, achieving accuracy ϵ requires O(ϵ−q/r) shallow-network parameters, whereas hierarchical targets require O(ϵ−2/r) deep-network parameters.The contrast reflects the reduced input dimension of the constituent functions.
3 Shallow networks
This section develops shallow ReLU and Gaussian approximation on Euclidean spaces, with smoothness and complexity measured beyond parameter counts. It presents approximation theorems, data-dependent Gaussian constructions, and limitations of width-based guarantees.
- 3.1 ReLU networks: The paper studies shallow ReLU networks on R^q using weighted spaces because these networks are unbounded on the whole Euclidean space.The target space and smoothness classes incorporate behavior at infinity, not only derivative counts.
- 3.1 ReLU networks: The ReLU results extend approximation theory to the nonsmooth activation |·| and to approximation over the entire Euclidean space.These are identified as technical novelties relative to the earlier theorem.
- 3.2 Gaussian networks: Gaussian networks are constructed with centers selected from finite sets, while their coefficients can be obtained as linear combinations of sampled function values.The centers need not be trained under the theorem’s stated conditions.
- 3.2 Gaussian networks: O(m^2q) trainable coefficients and approximately ϵ^-2q/γ samples guarantee accuracy ϵ for the stated Gaussian smoothness class.The theorem also gives the width rate d_n(B_γ,q) ∼ n^-γ/(2q), described as best possible in terms of widths.
- 3.2 Gaussian networks: Width estimates for an entire function class guarantee only that a possibly pathological function prevents improvement, so they do not characterize every individual function.The paper raises this distinction before presenting a converse theorem for Gaussian approximation.
- 3.2 Gaussian networks: Minimal separation among Gaussian centers, rather than the number of nonlinear units, is identified as the appropriate complexity measure for matching direct and converse results.The paper expects a similar result for ReLU networks.
4 Deep networks
This section generalizes approximation results to deep networks whose architecture follows a directed acyclic graph (DAG). For compositional functions with small maximal indegree, the resulting complexity can be substantially lower than for shallow networks when d ≪ q.
- General DAG functions: A G-function is represented by a DAG whose nodes evaluate constituent real-valued functions, with one sink producing the overall output.Source and other nodes receive Euclidean inputs, while outgoing edges propagate evaluated results.
- General DAG functions: The analysis treats a G-function as a collection of constituent functions rather than only as a single function on R^q.This avoids ambiguity because different DAGs or constituent-function choices can represent the same function on R^q.
- General DAG functions: Deep-network function classes are defined by requiring each constituent function at a DAG node to belong to a specified class.The notation GX denotes G-functions whose constituents lie in X(R^d).
- ReLU networks: Theorem 4.1 provides a deep-network approximation result for functions in GW_w,γ using networks conforming to the DAG G.The theorem assumes 1 ≤ γ ≤ 2 and uses n as an integer network-complexity parameter.
- Approximation bounds: O(|V|n) trainable parameters suffice for the deep network, equivalent to O((ϵ/|V|)^−d/γ) units for accuracy at most ϵ.The corresponding shallow-network requirement is O(ϵ^−q/γ) units when compositional structure is ignored.
- Approximation bounds: Deep networks yield a substantial improvement over shallow networks when the constituent dimension d is much smaller than the ambient source dimension q.The paper also announces corresponding results for deep Gaussian networks, including constructive and converse theorems.
5 Ideas behind the proofs
The proofs derive shallow ReLU and Gaussian approximation results and transfer them to DAG-structured deep networks. The Gaussian analysis uses spherical transformations, reproducing formulas, smoothness classes, and approximation-theoretic inequalities, while a good-error-propagation property connects constituent bounds to whole-network bounds.
- Spherical transformation: The Gaussian proof begins by wrapping a target function on R^q into an even function on the unit sphere S^q.The transformed function is continuous, well defined, and vanishes on the equator under the stated decay condition.
- Reproducing formulas: The spherical construction uses ultraspherical polynomials, spherical harmonics, and reproducing-kernel properties to build approximation formulas.Evenness removes the odd spherical-harmonic coefficients.
- Gaussian approximation: Discretizing the reproducing formula with polynomial approximations produces a zonal Gaussian network approximation.The resulting estimate yields the relevant approximation bound for functions satisfying the required smoothness conditions.
- Smoothness classes: The smoothness class is defined through a K-functional involving an operator D and functions whose D-derivative belongs to the base function space.The resulting estimate leads to the shallow-network bound (3.1).
- Gaussian-network proof: Hermite functions and the Mehler formula support the analysis of multivariate Gaussian networks.Approximation and quadrature results are combined to complete the proof of Theorem 3.2.
- Deep-network transfer: A Bernstein-type inequality is used to prove Theorem 3.3 for Gaussian networks, followed by standard approximation-theory arguments.Theorem 4.2(b) is then obtained from Theorem 3.3 through the deep-network framework.
- Deep-network transfer: The deep-network theorems follow from constituent approximation results through a good-error-propagation property.The norms for DAG-associated function spaces ensure each constituent bound implies the required whole-network bound.
6 Blessed representations
Deep networks can exploit compositional and other sparse representations to approximate certain functions with substantially fewer parameters than shallow networks. These examples motivate relative dimension as a way to formalize when deep representations are parsimonious.
- Compositional representations: Compositional functions on binary-like trees can be approximated well by deep convolutional networks with weight sharing but not by shallow networks.Shift-invariant scalable functions have layered structures of identical local blocks, matching the compositional form exploited by deep convolutional architectures.
- Compositional representations: Repeated composition turns low-dimensional polynomial approximations into nominally high-degree polynomials, reducing the parameter burden relative to shallow approximation.For the highlighted construction, each coefficient depends on only 18 parameters, and the relevant form is g(g(g())).
- Spline-wavelet representations: Deep networks with activation (x+)^2 can represent n tensor-product cubic spline wavelets, whereas shallow sigmoidal networks cannot implement them using O(n) neurons.The spline-wavelet representation provides local and multi-scale approximation through compact supports with shrinking supports, although it does not generally avoid the curse of dimensionality.
- Relative dimension: The examples exhibit three kinds of sparsity that can yield deep representations with far fewer parameters than shallow representations.The paper also cites recent examples of functions that cannot be represented efficiently by shallow networks.
- Relative dimension: Relative dimension compares the asymptotic n-width decay of two compact function classes, and V is parsimonious with respect to W when D(V, W) ≪1.For the cited classes, D(GBγ, Bγ,q) ≤ d/q.
7 Conclusion
The conclusion argues that approximation theory needs suitable smoothness classes and complexity measures for neural approximation. The paper reports satisfactory ReLU and Gaussian approximation results and introduces sparsity concepts beyond parameter counting.
- Conclusion: Approximation theory must identify smoothness classes and complexity measures that support matching direct and converse theorems.The paper frames these as central problems for approximation spaces.
- Conclusion: The paper demonstrates satisfactory approximation results for ReLU and Gaussian networks on the entire Euclidean space.A converse theorem is proved for Gaussian networks, while prior results suggest an analogous statement for ReLU networks.
- Conclusion: Network complexity is not necessarily measured correctly by the number of parameters alone.The paper initiates a discussion of sparsity notions intended to deepen understanding of approximation by neural networks.