Source-linked AI summary
Learning Functions: When Is Deep Better Than Shallow
Hrushikesh Mhaskar, Qianli Liao, Tomaso Poggio
TL;DR
The paper asks when depth provides an advantage over shallow networks despite universal approximation by both. It analyzes compositional functions with hierarchical networks and shows equal approximation accuracy with substantially lower complexity, while identifying scalability and shift invariance as motivations for deep convolutional architectures.
Problem
The paper addresses why and under which conditions multilayer networks are better than one-hidden-layer networks, especially for compositional functions.
Method
It models deep networks as hierarchical compositions, analyzes approximation and complexity bounds, and develops a framework for scalable, shift-invariant compositional algorithms.
Results
Deep networks approximate compositional functions with the same accuracy as shallow networks but with far fewer trainable parameters and smaller capacity measures.
Takeaways & Limitations
The results support depth when the target has compositional structure and motivate deep convolutional networks for scalable, shift-invariant signals.
Takeaways & Limitations
For functions without compositional structure, the paper does not expect an advantage from deep convolutional networks, and some approximation questions remain unresolved for neural networks.
Abstract
from arXiv · showhide
While the universal approximation property holds both for hierarchical and shallow networks, we prove that deep (hierarchical) networks can approximate the class of compositional functions with the same accuracy as shallow networks but with exponentially lower number of training parameters as well as VC-dimension. This theorem settles an old conjecture by Bengio on the role of depth in networks. We then define a general class of scalable, shift-invariant algorithms to show a simple and natural set of requirements that justify deep convolutional networks.
1 Introduction
The paper asks when deep networks are better than shallow ones and compares their approximation power, complexity, and suitability for compositional signals. It argues that compositional functions can be approximated equally accurately with far fewer resources by deep networks, especially when scalability and shift invariance matter.
- The paper studies why deep architectures can be better than shallow ones and under which conditions this advantage appears.
- Deep and shallow networks are both universal approximators of continuous functions on compact domains.
- Compositional functions can be approximated with the same accuracy by deep and shallow networks, while deep networks use far fewer parameters and have smaller capacity measures.The comparison concerns trainable parameters, VC-dimension, and fat-shattering dimension.
- Scalability and shift invariance in natural signals such as images and text motivate compositional algorithms that deep convolutional networks can approximate.The stated motivation applies to signals with these properties, not to all functions.
2 Previous work
Previous work framed depth as a possible source of representational efficiency, drawing on hierarchical models, circuit trade-offs, and approximation theory. Figure 1 contrasts a generic shallow network with a binary-tree network structured around compositional functions.
- The paper’s broader context is the recurring question of why multilayer networks can outperform one-hidden-layer networks and when that advantage occurs.
- Prior studies analyzed hierarchical quadratic and sum-product networks, ReLU linear regions, and functions that are inefficiently represented by shallow networks.
- Figure 1 contrasts a shallow universal network for generic functions with a binary-tree network whose nodes compute compositional ridge-function approximations.
- The hierarchical example uses ReLU ridge-function units at its nodes, while both shallow and deep networks retain universal approximation ability.
3 Compositional functions
The paper focuses on targets with hierarchical compositional structure and assumes the shallow comparator lacks that structural information. It argues that matching the target’s structure makes deep approximation more efficient, while invariance is deliberately not assumed.
- The shallow networks are assumed not to encode the target’s compositional structure, whereas standard deep architectures represent and adapt to that structure.
- Hierarchical compositions are conjectured to be approximated more efficiently by deep than by shallow networks.
- The comparison treats the generic case without assuming invariance to group transformations, even though shallow and deep representations may or may not have such invariance.
- The target functions are approximated with smoothened ReLU activations, and each deep-network node is a ridge function reflecting the compositional architecture.
- The compositional setup is connected to deep convolutional architectures whose receptive fields grow across layers, including ResNet-type networks discussed elsewhere in the paper.
4 Main results
The paper compares approximation by shallow and hierarchical networks under smoothness and compositional-structure assumptions. Its main results show that deep networks can retain approximation accuracy while using far fewer trainable parameters, with corresponding VC-dimension bounds, although these gains require the prescribed hierarchy.
- 4.1 Deep and shallow neural networks: The approximation guarantees depend on smoothness assumptions, and their constants depend on derivative norms and the activation function.Thus, specifying only the number of derivatives does not fully determine the constants in the error bounds.
- 4.1 Deep and shallow neural networks: O(ϵ−2/r) trainable parameters suffice for hierarchical targets, versus O(ϵ−d/r) for shallow networks at accuracy ϵ.The comparison assumes the target has the binary-tree compositional structure and the stated smoothness conditions.
- 4.1 Deep and shallow neural networks: The shallow-network rate O(ϵ−d/r) is optimal among reasonable robust approximation methods for arbitrary functions in WNN_r,d.The lower bound is expressed through the nonlinear n-width, while the estimate itself does not guarantee robustness.
- 4.2 Deep and shallow Gaussian networks: The Gaussian-network analysis models a hierarchical target as constituent functions indexed by the binary tree's non-leaf nodes.Each constituent function is approximated by a Gaussian network, and the deep network preserves the target's prescribed structure.
- 4.2 Deep and shallow Gaussian networks: For Gaussian networks, a shallow model requires O(ϵ−2L/γ) trainable parameters, whereas the corresponding binary-tree deep model requires O(Lϵ−4/γ).Here L is the number of leaves, and the comparison applies to targets satisfying the hierarchical structure and both smoothness conditions.
- 4.2 Deep and shallow Gaussian networks: The Gaussian results are restricted to targets with the binary-tree hierarchy, although the authors note that more general directed acyclic graphs could be handled.The binary-tree assumption is retained for simplicity in the presented comparison.
- 4.2 Deep and shallow Gaussian networks: For individual functions, the Gaussian converse links approximation behavior under center-separation conditions back to membership in the corresponding smoothness classes.The result is stated for both shallow and hierarchically structured Gaussian networks.
- 4 Main results: The VC-dimension is bounded by (d + 2)N 2 for shallow networks and 4n2(d −1)2 for binary-tree networks with n(d −1) units.These bounds quantify a complexity advantage for the hierarchical architecture under the paper's parameterization.
5 A general framework for hierarchical, compositional computations
The framework characterizes scalable, shift-invariant operators as hierarchical compositions of identical two-input blocks, motivating deep convolutional approximators.
- Scalable shift-invariant operators are structured as compositions of operators applied across increasing input scales.
- Each layer contains identical blocks, with each block implementing a two-input operator H: R^2 7→R.
- Mirror symmetry can replace shift invariance as a weaker constraint on the highest-level operator.
- A nonlinear node with enough channels can approximate each two-input block, making deep convolutional networks natural approximators of these operators.
6 Discussion
The discussion connects hierarchical approximation to sparse polynomial structure and Boolean-function depth advantages, while illustrating the parameter savings with a high-degree example.
- A polynomial of nominal degree 2^11 can be approximated arbitrarily well using 11 hierarchical layers and 39 units, versus 2^11 + 1 units for a shallow network.The hierarchical construction uses 9 units for the quadratic expression and 10 further layers with 3 units each.
- Hierarchical networks can efficiently learn functions approximated by sparse polynomials when their tree or graph structure matches the polynomial.
- The trigonometric experiment compares 1-, 2-, and 3-hidden-layer networks across unit and parameter counts using repeated regression trials.
- The paper argues that its theorem connects Boolean-function depth advantages with real-valued neural networks and supports Bengio’s conjecture about depth.
A Boolean functions
The Boolean-functions discussion uses Fourier expansions to relate network structure to sparse or low-order polynomial representations and corresponding learning strategies.
- Boolean Fourier representations are multilinear polynomial expansions, allowing Fourier and polynomial descriptions to be treated interchangeably.
- The framework relates deep-network tree structure to sparse polynomials, whereas generic degree-k polynomials can require exponentially many terms and parameters in d.
- Prior circuit results show that deep circuits represent certain Boolean functions more efficiently than shallow circuits, motivating the paper’s neural-network connection.
- The low-order algorithm uses low-order Fourier coefficients, while the sparse algorithm learns significant coefficients that need not be low-order.
- Sparse-coefficient learning is presented as more general than shallow Tikhonov-style low-frequency learning, subject to computational and sample-complexity considerations.