# Expressivity of Neural Networks via Chaotic Itineraries beyond Sharkovsky's Theorem

arXiv: https://arxiv.org/abs/2110.10295 · HTML: https://mlsanity.com/paper/2110.10295/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 49 references that are in the map.
- First posted on arXiv 19 Oct 2021.

## Builds on (most cited first, 21 of 21)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [On the Number of Linear Regions of Deep Neural Networks](https://mlsanity.com/paper/1402.1869/) (2014)
- [On the Expressive Power of Deep Neural Networks](https://mlsanity.com/paper/1606.05336/) (2016)
- [Exponential expressivity in deep neural networks through transient chaos](https://mlsanity.com/paper/1606.05340/) (2016)
- [Understanding Deep Neural Networks with Rectified Linear Units](https://mlsanity.com/paper/1611.01491/) (2016)
- [Benefits of depth in neural networks](https://mlsanity.com/paper/1602.04485/) (2016)
- [The Power of Depth for Feedforward Neural Networks](https://mlsanity.com/paper/1512.03965/) (2015)
- [Deep ReLU Networks Have Surprisingly Few Activation Patterns](https://mlsanity.com/paper/1906.00904/) (2019)
- [Representation Benefits of Deep Feedforward Networks](https://mlsanity.com/paper/1509.08101/) (2015)
- [On the Expressive Power of Deep Polynomial Neural Networks](https://mlsanity.com/paper/1905.12207/) (2019)
- [Depth Separation for Neural Networks](https://mlsanity.com/paper/1702.08489/) (2017)
- [Multiplicative Weights Update with Constant Step-Size in Congestion Games: Convergence, Limit Cycles and Chaos](https://mlsanity.com/paper/1703.01138/) (2017)
- [On the Approximation Power of Two-Layer Networks of Random ReLUs](https://mlsanity.com/paper/2102.02336/) (2021)
- [Depth Separations in Neural Networks: What is Actually Being Separated?](https://mlsanity.com/paper/1904.06984/) (2019)
- [On the ability of neural nets to express distributions](https://mlsanity.com/paper/1702.07028/) (2017)
- [Is Deeper Better only when Shallow is Good?](https://mlsanity.com/paper/1903.03488/) (2019)
- [Depth-Width Trade-offs for ReLU Networks via Sharkovsky's Theorem](https://mlsanity.com/paper/1912.04378/) (2019)
- [Sharp Representation Theorems for ReLU Networks with Precise Dependence on Depth](https://mlsanity.com/paper/2006.04048/) (2020)
- [Better Depth-Width Trade-offs for Neural Networks through the lens of Dynamical Systems](https://mlsanity.com/paper/2003.00777/) (2020)
- [Depth-Width Trade-offs for Neural Networks via Topological Entropy](https://mlsanity.com/paper/2010.07587/) (2020)

## Built on by (most cited first, 2 of 2)

- [On Scrambling Phenomena for Randomly Initialized Recurrent Networks](https://mlsanity.com/paper/2210.05212/) (2022)
- [A Dynamical Systems Perspective on the Analysis of Neural Networks](https://mlsanity.com/paper/2507.05164/) (2025)

## Abstract (arXiv)

Given a target function f, how large must a neural network be in order to approximate f? Recent works examine this basic question on neural network textitexpressivity from the lens of dynamical systems and provide novel ``depth-vs-width'' tradeoffs for a large family of functions f. They suggest that such tradeoffs are governed by the existence of textitperiodic points or cycles in f. 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 L1 error). More broadly, we identify a phase transition to the textitchaotic regime that exactly coincides with an abrupt shift in other notions of function complexity, including VC-dimension and topological entropy.