Depth Separation for Neural Networks

Abstract

Let $f:{\mathbb{S}}^{d-1}\times {\mathbb{S}}^{d-1}\to \mathbb{S}$ be a function of the form $f(\mathbf{x},{\mathbf{x}}^{\prime })=g(⟨\mathbf{x},{\mathbf{x}}^{\prime }⟩)$ for $g:[-1,1]\to \mathbb{R}$. We give a simple proof that shows that poly-size depth two neural networks with (exponentially) bounded weights cannot approximate $f$ whenever $g$ cannot be approximated by a low degree polynomial. Moreover, for many $g$'s, such as $g(x)=\sin (\pi d^{3}x)$, the number of neurons must be $2^{\Omega \left(d\log (d)\right)}$. Furthermore, the result holds w.r.t.\ the uniform distribution on ${\mathbb{S}}^{d-1}\times {\mathbb{S}}^{d-1}$. As many functions of the above form can be well approximated by poly-size depth three networks with poly-bounded weights, this establishes a separation between depth two and depth three networks w.r.t.\ the uniform distribution on ${\mathbb{S}}^{d-1}\times {\mathbb{S}}^{d-1}$.

Cited by in corpus (14)

• Efficient approximation of high-dimensional functions with neural networks
• Deep Equals Shallow for ReLU Networks in Kernel Regimes
• Deep ReLU Networks Preserve Expected Length
• Sharp Representation Theorems for ReLU Networks with Precise Dependence on Depth
• Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers
• Layer Folding: Neural Network Depth Reduction using Activation Linearization
• The Connection Between Approximation, Depth Separation and Learnability in Neural Networks
• A Deep Conditioning Treatment of Neural Networks
• On the Optimal Memorization Power of ReLU Neural Networks
• Depth separation beyond radial functions
• On the Approximation Power of Two-Layer Networks of Random ReLUs
• A lattice-based approach to the expressivity of deep ReLU neural networks
• Theoretical Guarantees for Model Auditing with Finite Adversaries
• Expressivity of Neural Networks via Chaotic Itineraries beyond Sharkovsky's Theorem