Depth separation beyond radial functions

Abstract

High-dimensional depth separation results for neural networks show that certain functions can be efficiently approximated by two-hidden-layer networks but not by one-hidden-layer ones in high-dimensions $d$. Existing results of this type mainly focus on functions with an underlying radial or one-dimensional structure, which are usually not encountered in practice. The first contribution of this paper is to extend such results to a more general class of functions, namely functions with piece-wise oscillatory structure, by building on the proof strategy of (Eldan and Shamir, 2016). We complement these results by showing that, if the domain radius and the rate of oscillation of the objective function are constant, then approximation by one-hidden-layer networks holds at a $\mathrm{poly}(d)$ rate for any fixed error threshold. A common theme in the proofs of depth-separation results is the fact that one-hidden-layer networks fail to approximate high-energy functions whose Fourier representation is spread in the domain. On the other hand, existing approximation results of a function by one-hidden-layer neural networks rely on the function having a sparse Fourier representation. The choice of the domain also represents a source of gaps between upper and lower approximation bounds. Focusing on a fixed approximation domain, namely the sphere ${\mathbb{S}}^{d-1}$ in dimension $d$, we provide a characterisation of both functions which are efficiently approximable by one-hidden-layer networks and of functions which are provably not, in terms of their Fourier expansion.

References in corpus (21)

• On the Number of Linear Regions of Deep Neural Networks
• Exponential expressivity in deep neural networks through transient chaos
• On the Spectral Bias of Neural Networks
• Understanding Deep Neural Networks with Rectified Linear Units
• On the number of response regions of deep feed forward networks with piece-wise linear activations
• The power of deeper networks for expressing natural functions
• Deep ReLU Networks Have Surprisingly Few Activation Patterns
• Depth-Width Tradeoffs in Approximating Natural Functions with Neural Networks
• Benefits of depth in neural networks
• Complexity of Linear Regions in Deep Networks
• Depth Separation for Neural Networks
• A Function Space View of Bounded Norm Infinite Width ReLU Nets: The Multivariate Case
• Depth-Width Trade-offs for ReLU Networks via Sharkovsky's Theorem
• Depth separation for reduced deep networks in nonlinear model reduction: Distilling shock waves in nonlinear hyperbolic problems
• Depth-Width Trade-offs for Neural Networks via Topological Entropy
• Sharp Representation Theorems for ReLU Networks with Precise Dependence on Depth
• Neural Networks with Small Weights and Depth-Separation Barriers
• Size and Depth Separation in Approximating Benign Functions with Neural Networks
• The Connection Between Approximation, Depth Separation and Learnability in Neural Networks
• On the Approximation Power of Two-Layer Networks of Random ReLUs
• Efficient Deep Learning of GMMs

Cited by in corpus (2)

• On the Optimal Memorization Power of ReLU Neural Networks
• Separation Results between Fixed-Kernel and Feature-Learning Probability Metrics