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 doesn't 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 a 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 behaviour 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 systems associated with such functions.
In tackling a curious construction by Telgarsky regarding a certain class of functions that can be represented by deep networks (but not shallow networks (unless those shallow networks have exponentially many units)), the authors derive depth-width tradeoff conditions for when relu networks are able to represent periodic functions using dynamical systems analysis.
This paper was a delight to read.  I particularly enjoyed the motivating examples, and the clean exposition of Sharkovsky's theorem.  This result seems to cleanly answer the open question originally posed by Telgarsky, and the proofs are cleanly written, and correct to my (admittedly not perfect) knowledge.  I strongly suggest acceptance.
Questions/comments:
1. Could the author speculate on how the introduction of a bias term might affect their lower bound?  Presumably, this breaks the cleanness of the characteristic polynomial for $A$, but perhaps there are limits where it's still tractable?  This analysis certainly isn't necessary for publishing--I'm simply curious.
2. Could the authors provide some guiding intuition for the sharpness of their lower bound? (possibly on a synthetic dataset?) . I'm particularly imagining a plot that literally shows "classification error" versus "depth" for some fixed task.  While this is certainly a strong theoretical result, it would be nice to be able to contextualize how this result actually shines for a "real" model (and would help me believe the result "in my gut" so to speak).