The staircase property: How hierarchical structure can guide deep learning
arXiv:2108.10573
Abstract
This paper identifies a structural property of data distributions that enables deep neural networks to learn hierarchically. We define the "staircase" property for functions over the Boolean hypercube, which posits that high-order Fourier coefficients are reachable from lower-order Fourier coefficients along increasing chains. We prove that functions satisfying this property can be learned in polynomial time using layerwise stochastic coordinate descent on regular neural networks -- a class of network architectures and initializations that have homogeneity properties. Our analysis shows that for such staircase functions and neural networks, the gradient-based algorithm learns high-level features by greedily combining lower-level features along the depth of the network. We further back our theoretical results with experiments showing that staircase functions are also learnable by more standard ResNet architectures with stochastic gradient descent. Both the theoretical and experimental results support the fact that staircase properties have a role to play in understanding the capabilities of gradient-based learning on regular networks, in contrast to general polynomial-size networks that can emulate any SQ or PAC algorithms as recently shown.
arXiv comment60 pages, accepted to NeurIPS '21
References in corpus (16)
- Exact solutions to the nonlinear dynamics of learning in deep linear neural networks
- Hierarchical Deep Reinforcement Learning: Integrating Temporal Abstraction and Intrinsic Motivation
- Learning both Weights and Connections for Efficient Neural Networks
- Training Neural Networks with Local Error Signals
- The Convergence Rate of Neural Networks for Learned Functions of Different Frequencies
- Learning Functions: When Is Deep Better Than Shallow
- What Can ResNet Learn Efficiently, Going Beyond Kernels?
- A Probabilistic Theory of Deep Learning
- Is Deeper Better only when Shallow is Good?
- A Provably Correct Algorithm for Deep Learning that Actually Works
- A Corrective View of Neural Networks: Representation, Memorization and Learning
- The Implicit Bias of Depth: How Incremental Learning Drives Generalization
- Decoupled Greedy Learning of CNNs
- Deep Equals Shallow for ReLU Networks in Kernel Regimes
- Deep Learning and Hierarchal Generative Models
- Quantifying the Benefit of Using Differentiable Learning over Tangent Kernels