Abstract: 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.
Introduction
A fundamental question in deep learning is why depth is so effective. While it is known that deep networks can represent functions that shallow networks cannot (unless they have exponential width), the underlying reason for this "expressivity gap" has remained elusive. Previous research, notably by Matus Telgarsky, utilized specific "triangular wave" functions to demonstrate this gap. However, these examples were somewhat specialized. This work establishes a general framework for understanding these trade-offs by linking neural network expressivity to the mathematical field of dynamical systems and chaos theory.
The Dynamical Systems Connection
The core idea is to treat the layers of a neural network as repeated applications (compositions) of a function. If we consider a function $f(x)$, a deep network can naturally represent $f(f(f(x)))$ by stacking layers that each compute $f$. In the language of dynamical systems, this is an iterated map.
The complexity of such maps is governed by Sharkovsky’s Theorem. This theorem provides a specific ordering of natural numbers based on the periods of cycles they "force" in a continuous function. Crucially, "Period 3" is at the top of this ordering; if a function has a point of period 3, it is guaranteed to have points of every other period, a phenomenon famously described as "Period 3 implies chaos."
Representing Iterated Functions
ReLU networks are particularly well-suited for representing piecewise linear functions like the "tent map." A simple two-layer hidden network can represent a single "tent" or triangular wave.
As shown in the figure above, by adjusting weights and biases, a small ReLU network can represent the basic building block of these chaotic functions. When these networks are stacked (increasing depth), they effectively compute higher-order iterations of the map, mimicking the compositional nature of dynamical systems.
The Emergence of Chaos
The difficulty for shallow networks arises because each iteration of a chaotic map (like the tent map with $\mu=2$) exponentially increases the number of "crossings" or oscillations. After $k$ iterations, the function's complexity grows dramatically.
A deep network with $k$ layers can represent this $2^k$-oscillation function using only $O(k)$ neurons. In contrast, a shallow network with few layers must use "brute-force" width to track every single oscillation, requiring $\Omega(2^k)$ neurons. The authors use eigenvalue analysis of transition matrices to prove that functions with any odd period (except 1) exhibit this exponential growth in complexity, creating a hard trade-off for shallow architectures.
Key Results and Empirical Validation
The theoretical analysis yields rigorous lower bounds: for a function $f$ with an odd period $p$, a neural network with $l$ layers requires a width $u$ of at least $\Omega(\rho^{k/l})$ to approximate $k$ compositions of $f$, where $\rho > 1$ is a constant determined by the function's dynamics. If a shallow network fails to meet this exponential width requirement, its classification error is bounded below by at least $1/4$.
Empirically, the authors tested these ideas on a "smoothed" alternating point problem—a classification task with 8,000 points. They found that a 5-layer network could achieve over 99% accuracy, while shallower networks with the same total number of parameters plateaued at much higher error rates, confirming that width is a poor substitute for depth when representing chaotic patterns.
Conclusion
By connecting expressivity to Sharkovsky's Theorem, this work provides a "natural" property—the presence of periodic points—that necessitates depth in neural networks. While identifying these periodic points in high-dimensional real-world data remains a challenge, this framework offers a powerful new lens through which to view the success of deep architectures. Future work will look to extend these results beyond one-dimensional maps to the high-dimensional spaces typical of modern machine learning.
Summary updated