# Depth-Width Trade-offs for ReLU Networks via Sharkovsky's Theorem

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Dec 2019.

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

- [Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers](https://mlsanity.com/paper/2107.13163/) (2021)
- [On the Optimal Memorization Power of ReLU Neural Networks](https://mlsanity.com/paper/2110.03187/) (2021)
- [A Primer on Bayesian Neural Networks: Review and Debates](https://mlsanity.com/paper/2309.16314/) (2023)
- [The Connection Between Approximation, Depth Separation and Learnability in Neural Networks](https://mlsanity.com/paper/2102.00434/) (2021)
- [Depth separation beyond radial functions](https://mlsanity.com/paper/2102.01621/) (2021)
- [Width is Less Important than Depth in ReLU Neural Networks](https://mlsanity.com/paper/2202.03841/) (2022)
- [On the Benefits of Rank in Attention Layers](https://mlsanity.com/paper/2407.16153/) (2024)
- [On Scrambling Phenomena for Randomly Initialized Recurrent Networks](https://mlsanity.com/paper/2210.05212/) (2022)
- [Expressivity of Neural Networks via Chaotic Itineraries beyond Sharkovsky's Theorem](https://mlsanity.com/paper/2110.10295/) (2021)
- [The Disharmony between BN and ReLU Causes Gradient Explosion, but is Offset by the Correlation between Activations](https://mlsanity.com/paper/2304.11692/) (2023)
- [Designing ReLU Generative Networks to Enumerate Trees with a Given Tree Edit Distance](https://mlsanity.com/paper/2510.10706/) (2025)
- [Constants of Motion: The Antidote to Chaos in Optimization and Game Dynamics](https://mlsanity.com/paper/2109.03974/) (2021)
- [Transformer Vs. MLP-Mixer: Exponential Expressive Gap For NLP Problems](https://mlsanity.com/paper/2208.08191/) (2022)
- [Memorization capacity of deep ReLU neural networks characterized by width and depth](https://mlsanity.com/paper/2603.09589/) (2026)
- [ReLU Networks for Exact Generation of Similar Graphs](https://mlsanity.com/paper/2604.05929/) (2026)

## Abstract (arXiv)

Understanding the representational power of Deep Neural Networks (DNNs) and how their structural properties (e.g., depth, width, type of activation unit) affect the functions they can compute, has been an important yet challenging question in deep learning and approximation theory. In a seminal paper, Telgarsky highlighted the benefits of depth by presenting a family of functions (based on simple triangular waves) for which DNNs achieve zero classification error, whereas shallow networks with fewer than exponentially many nodes incur constant error. Even though Telgarsky's work reveals the limitations of shallow neural networks, it does not inform us on why these functions are difficult to represent and in fact he states it as a tantalizing open question to characterize those functions that cannot be well-approximated by smaller depths. In this work, we point to a new connection between DNNs expressivity and Sharkovsky's Theorem from dynamical systems, that enables us to characterize the depth-width trade-offs of ReLU networks for representing functions based on the presence of generalized notion of fixed points, called periodic points (a fixed point is a point of period 1). Motivated by our observation that the triangle waves used in Telgarsky's work contain points of period 3 - a period that is special in that it implies chaotic behavior based on the celebrated result by Li-Yorke - we proceed to give general lower bounds for the width needed to represent periodic functions as a function of the depth. Technically, the crux of our approach is based on an eigenvalue analysis of the dynamical system associated with such functions.