Why and When Can Deep -- but Not Shallow -- Networks Avoid the Curse of Dimensionality: a Review

Tomaso Poggio; Hrushikesh Mhaskar; Lorenzo Rosasco; Brando Miranda; Qianli Liao

Source-linked AI summary

Why and When Can Deep -- but Not Shallow -- Networks Avoid the Curse of Dimensionality: a Review

Tomaso Poggio, Hrushikesh Mhaskar, Lorenzo Rosasco, Brando Miranda, Qianli Liao

arXiv:1611.00740v5Nov 2, 2016cs.LG

TL;DR

The paper addresses which functions deep networks can approximate efficiently when shallow networks cannot, focusing on compositional structure. It synthesizes theoretical results on compositional and hierarchically local functions, showing that matched deep architectures avoid the curse of dimensionality while shallow complexity can be exponential in input dimension. The conclusions include convolutional networks as a special case, with locality—not weight sharing—providing the key advantage.

Problem
The paper asks which function classes deep networks can approximate without the curse of dimensionality, unlike shallow networks.
Method
The paper summarizes theorems and formulates compositional functions through directed acyclic graphs whose nodes compute constituent functions.
Results
Deep networks matched to compositional graphs avoid the curse of dimensionality, whereas the best approximating shallow network has complexity exponential in n.
Takeaways & Limitations
For hierarchically local compositional problems, locality at each hierarchy level is more important to the exponential advantage than weight sharing.
Takeaways & Limitations
The main binary-tree architecture is idealized, with one output and single-value nodes rather than the multiple channels and top-level outputs common in deep convolutional networks.

Abstract

from arXiv · show

The paper characterizes classes of functions for which deep learning can be exponentially better than shallow learning. Deep convolutional networks are a special case of these conditions, though weight sharing is not the main reason for their exponential advantage.

1 A theory of deep learning

The paper focuses on when deep networks can theoretically outperform shallow networks, especially for compositional functions. Hierarchical locality, rather than weight sharing, is identified as the key source of convolutional networks’ exponential advantage.

1 A theory of deep learning: Deep networks can avoid the curse of dimensionality for compositional functions, whereas shallow networks lack this theoretical guarantee.The relevant functions are built from functions of functions, including hierarchically local compositions.
1 A theory of deep learning: Certain deep convolutional architectures have a theoretical guarantee of substantially better performance than one-layer architectures such as kernel machines.
1 A theory of deep learning: Hierarchically local compositions use constituent functions with bounded small dimensionality at each level.The example decomposes an eight-variable function into constituent functions of dimension 2.
1 A theory of deep learning: Locality at each hierarchical level, not weight sharing, is the key aspect that can provide convolutional networks with an exponential advantage.

2 Previous theoretical work

Earlier work established approximation results for shallow networks, while later theory developed bounds showing that deep networks can efficiently approximate important compositional function classes. The paper reviews this shift and the resulting separation between deep and shallow approximation.

2 Previous theoretical work: Shallow networks were extensively studied for approximation, while multilayer networks received comparatively little theoretical attention.Historically, one-hidden-layer networks often performed empirically as well as deeper networks.
2 Previous theoretical work: Deep-network results derive upper bounds for approximating important function classes that avoid the curse of dimensionality.
2 Previous theoretical work: The general shallow-network approximation bound is exponential, motivating the expectation that shallow networks may also require exponential complexity for compositional functions.

3 Function approximation by deep networks

The paper compares approximation by shallow and deep networks, showing that deep architectures can exploit compositional structure to avoid dimensionality-dependent complexity for important function classes.

Approximation framework: Theorems compare shallow one-hidden-layer networks with deep networks using related operations and complexity measured by total units or parameters.Approximation guarantees target an unknown function f to accuracy ϵ under assumptions defining a function class.
Compositional structure: Compositional functions organize computations through constituent functions of fixed, often low, dimension, such as binary-tree compositions with d = 2.The binary-tree example has n inputs but constituent functions operate locally on pairs of variables.
Compositional structure: Deep networks can exploit compositional structure, whereas shallow networks are blind to it.This architectural match yields smaller deep networks for equivalent approximation accuracy.
Scope and assumptions: The theoretical activation assumptions exclude ReLU directly, although smoothing ReLU in an arbitrarily small interval suggests the result should also hold for nonsmooth ReLU.The paper also notes stronger results for Gaussian nonlinearities.
Shallow networks: For general smooth functions, shallow approximation requires O(ϵ^-n/m) trainable parameters, and this exponential dependence on input dimension is the curse of dimensionality.The estimate is stated to be best possible when the only prior information is smoothness.
Deep networks: Under a hierarchical compositional assumption, a deep network guarantees accuracy ϵ with O(ϵ^-2/m) trainable parameters, and the result extends to fixed constituent dimension d.The main deep-network theorem is formulated for binary trees and extends to compositions whose constituent functions have a fixed number of variables.

4 General compositionality results: functions composed by a hierarchy of functions with bounded effective dimensionality

The paper generalizes compositionality results to functions organized by directed acyclic graphs whose constituent functions have bounded effective dimensionality. Deep networks can then avoid the curse of dimensionality, whereas shallow networks generally require exponential complexity.

Polynomial examples: A nominally degree-2^11 polynomial can be approximated with 2^11 + 1 shallow units or 39 units across an 11-layer hierarchical network.The hierarchical construction uses 9 units for the quadratic expression and 10 additional layers with 3 units each.
General compositionality: A compositional function is represented by a directed acyclic graph whose nodes compute functions of their incoming variables.Ignoring the composition, the function depends on n source variables.
General compositionality: Theorem 3 states that graph-aligned deep networks avoid the curse of dimensionality as n grows, while the best shallow approximation is exponential in n.The result applies when constituent functions belong to suitable smoothness classes.
Effective dimensionality: Deep networks avoid the curse when constituent functions have small effective dimension, meaning fixed small dimensionality or fixed small roughness.Proposition 1 connects effective dimension below n/m with compositional structure consistent with Theorem 3.
Polynomial examples: For full binary-tree polynomials with 2^n leaves, shallow complexity is O(k^(2^n)) units, whereas deep complexity is O(nk^2) units.The comparison illustrates an exponential-versus-linear-in-n gap for the same compositional polynomial class.
Scope and limitations: Shallow networks remain dense in continuous-function spaces, but this universality does not provide a comparable compositionality guarantee.The paper also notes that deep networks with exponentially many units can approximate any function, while compositional structure can reduce required complexity.

5 Connections with the theory of Boolean functions

The paper connects deep-versus-shallow approximation results to Boolean-function theory, especially Fourier structure, parity, and sparse representations.

Circuit-depth results similarly show that highly variable Boolean functions, including parity, resist decent approximation by small constant-depth circuits.
Deep networks represent parity functions with exponentially fewer units than shallow networks.
AC0 functions concentrate Fourier power in low-order coefficients and can therefore be approximated by low-degree polynomials.
The low-order algorithm uses low-order Fourier coefficients, whereas the sparse algorithm learns from significant coefficients regardless of their order.

6 Notes on a theory of compositional computation

The theory attributes deep networks’ advantage to compositional structure with small effective dimension, while discussing extensions, practical implications, and unresolved assumptions.

Certain deep networks avoid the curse of dimensionality for compositional functions because composition creates a small effective dimension.
The theory’s approximation results are supported by polynomial constructions, while SGD need not synthesize polynomials for every activation and target.
Weight sharing reduces network complexity, but the deep-versus-shallow comparison considers generic networks without assuming invariance.
The results are robust across nonlinearities such as rectifiers, sigmoids, and Gaussians, as well as pooling.
Binary sparsity supports non-exponential deep-network learning through binarization, and compositionality implies Boolean sparsity but not conversely.
Multitask compositional structure can reduce generalization error by roughly the square root of the number of tasks, estimated at about 30-fold for 1,000 tasks.

7 Why are compositional functions so common?

Compositionality alone does not guarantee a deep-network advantage: the useful cases require particular subclasses, while their prevalence in practical problems remains conjectural.

Linear operators and addition are compositional but gain no approximation advantage from being decomposed across layers.
Multiplication and Boolean AND are prototypical compositional functions that provide a deep-network advantage.
Avoiding the curse of dimensionality requires subclasses such as hierarchically local compositional functions, not compositionality alone.
The paper does not rigorously establish why practical problems should match the characterized function class, offering physics and neuroscience as conjectured explanations.

1 Boolean Functions

Boolean Fourier analysis represents Boolean functions as multilinear real polynomials, making Fourier and polynomial representations interchangeable in this setting.

Fourier analysis over the Boolean cube studies functions of n Boolean variables using the Fourier transform over the Abelian group Z_2^n.
For Boolean variables, the Fourier expansion is a multilinear polynomial representation, so the paper uses Fourier and polynomial representations interchangeably.

2 Does Physics or Neuroscience imply compositionality?

The review questions whether physical or neural evidence implies compositionality, especially hierarchical locality, while noting that locality alone does not ensure efficient simulation or match the paper’s definition.

Images are argued to exhibit compositionality because objects contain smaller, self-similar clusters of surfaces across scales.The passage distinguishes image compositionality from the stronger claim that a function on an image is compositional in the paper’s technical sense.
Hierarchical locality requires local constituent computations at successive levels, a condition weaker than requiring the same Hamiltonian at every scale.The paper relates this possibility to local interactions across physical scales but does not identify it with full renormalizability.
The review asks whether coarse graining produces local Hamiltonians and whether image computation hierarchies correspond to hierarchies of local physical processes.
Local, iterated functions can be Turing universal, so locality by itself does not imply efficient simulation or establish the paper’s desired physical explanation.

3 Splines: some notes

This section reviews spline-based approximation and develops hierarchical additive splines, which recover multivariate interactions through layered one-dimensional components while preserving universality.

3 Splines: some notes: Tensor-product and additive splines arise from regularization theory as alternatives to radial-kernel approximation and correspond to one-hidden-layer networks.Additive models use one-dimensional components and therefore have low complexity, while tensor products directly represent multidimensional structure.
3 Splines: some notes: Tensor-product bases use products of one-dimensional functions, whereas additive models sum one-dimensional functions or functions of linear combinations of inputs.
3.2 Hierarchical Splines: Hierarchical additive splines recover interactions such as xy by composing one-dimensional transformations across layers.The stated intuition is that terms such as elog(x)+log(y) can generate multivariate interaction structure.
3.2 Hierarchical Splines: Absolute-value nonlinearities represent piecewise-linear splines, and a second layer remains a piecewise-linear spline or hyperplane-based kernel-machine output.
3.2 Hierarchical Splines: Additive splines on individual variables are not universal, but hierarchical additive splines are universal.The paper states universality for tensor-product splines, additive splines on linear combinations, and hierarchical additive splines, but not ordinary coordinate-wise additive splines.

4 On multivariate function approximation

The section explains why direct tensor-product approximation is exponentially costly in dimension and shows how deep networks approximate compositional functions by building multivariate structure from low-dimensional components.

4 On multivariate function approximation: Tensor-product discretization uses a number of basis functions that scales exponentially with input dimension d.The total basis count is written as N = Qd, with the passage also noting scaling as d^m for fixed smoothness notation.
4 On multivariate function approximation: Neural networks lack a direct product operation, so equivalent multivariate approximations must be constructed using available nonlinearities such as ReLU.The paper introduces polynomial- and spline-basis constructions using univariate ReLU operations.
4 On multivariate function approximation: A polynomial of degree k in n variables can be represented exactly by a network with r = kn units, linking effective width to tensor separation rank.
4 On multivariate function approximation: For smooth nonpolynomial activations, the closure of ridge-function networks contains algebraic polynomials up to a specified degree.
4.3 Non-smooth ReLUs: how deep nets may work in reality: The ReLU construction guarantees L2 approximation rather than sup-norm approximation, and higher smoothness beyond bounded first derivatives cannot be exploited.The paper presents this as a weakness relative to other results and attributes the smoothness limitation to the nonsmooth activation.
4.3 Non-smooth ReLUs: how deep nets may work in reality: Deep ReLU networks approximate binary-tree compositional functions with Lipschitz constituents in L2 using O((n −1)Lϵ−2) units.Here L is the maximum Lipschitz constant among constituent functions.

5 Vector Quantization and Hierarchical Vector Quantization

The section contrasts flat vector quantization with hierarchical vector quantization, showing how compositional reuse can reduce memory requirements in multilayer architectures.

5 Vector Quantization and Hierarchical Vector Quantization: As Gaussian-like kernels become delta-like, a radial-basis network approaches a lookup table, while hierarchical vector quantization can reduce storage.
5 Vector Quantization and Hierarchical Vector Quantization: A hierarchical quantizer decomposes input vectors into reusable parts and recombines those parts across layers to represent multiple quantized inputs.
5 Vector Quantization and Hierarchical Vector Quantization: For ReLU interpolation, approximation accuracy improves with smoother functions only up to a saturation point; still higher smoothness does not help.
5 Vector Quantization and Hierarchical Vector Quantization: Memory compression increases with the number of reusable parts, making hierarchical architectures attractive for compositional data such as text and images.
5 Vector Quantization and Hierarchical Vector Quantization: Multilayer networks may have a memory-efficiency advantage over one-hidden-layer networks, which can matter for large datasets and relate to generalization rates.

6 Approximating compositional functions with shallow and deep networks: numerical experiments

The paper reports numerical experiments comparing shallow and deep binary-tree networks, including experiments on compositional functions and related settings.

The experiments compare shallow networks with binary-tree networks on learning tasks.
The reported experiments concern the paper’s analysis of deep and shallow network behavior.

7 Compositional functions and scalable algorithms

The paper formalizes scalable, shift-invariant computations as hierarchical compositions of repeated local operators and relates them to deep convolutional networks. Its bounds and comparisons indicate exponential advantages for deep networks on compositional problems, while the analysis is mainly about approximation and assumes ideal optimization in key conclusions.

Compositional functions and scalable algorithms: Scalable shift-invariant operators are compositions of layers containing identical two-input, one-output blocks.Each block maps R^2 to R, and combining inputs corresponds to coarse-graining in an Ising model.
Compositional functions and scalable algorithms: Deep convolutional networks naturally approximate scalable, shift-invariant operators when nonlinear nodes can approximate their local blocks.
Generalization bounds: For equal approximation error, the shallow network may require much larger sample size than the deep network to achieve the same generalization error.
Generalization bounds: For n ≈ 10^4 and ϵ ≈ 0.1, the comparison yields mshallow ≈ 10^104 mdeep, creating a range where deep networks avoid overfitting but shallow networks do not.
Scope and assumptions: The paper’s main focus is approximation theory, while its generalization-bound conclusions assume training finds optimum parameters for both architectures.
Numerical comparison: When compositionality is absent, the binary-tree network does not outperform the shallow network, and depth can worsen performance.