Expressivity of Neural Networks via Chaotic Itineraries beyond Sharkovsky's Theorem
arXiv:2110.10295
Abstract
Given a target function , how large must a neural network be in order to approximate ? Recent works examine this basic question on neural network \textit{expressivity} from the lens of dynamical systems and provide novel ``depth-vs-width'' tradeoffs for a large family of functions . They suggest that such tradeoffs are governed by the existence of \textit{periodic} points or \emph{cycles} in . Our work, by further deploying dynamical systems concepts, illuminates a more subtle connection between periodicity and expressivity: we prove that periodic points alone lead to suboptimal depth-width tradeoffs and we improve upon them by demonstrating that certain ``chaotic itineraries'' give stronger exponential tradeoffs, even in regimes where previous analyses only imply polynomial gaps. Contrary to prior works, our bounds are nearly-optimal, tighten as the period increases, and handle strong notions of inapproximability (e.g., constant error). More broadly, we identify a phase transition to the \textit{chaotic regime} that exactly coincides with an abrupt shift in other notions of function complexity, including VC-dimension and topological entropy.
arXiv comment47 pages, 19 figures
References in corpus (8)
- On the Number of Linear Regions of Deep Neural Networks
- Representation Benefits of Deep Feedforward Networks
- Understanding Deep Neural Networks with Rectified Linear Units
- Deep ReLU Networks Have Surprisingly Few Activation Patterns
- Is Deeper Better only when Shallow is Good?
- Depth Separation for Neural Networks
- Depth-Width Trade-offs for ReLU Networks via Sharkovsky's Theorem
- Sharp Representation Theorems for ReLU Networks with Precise Dependence on Depth