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 high- lighted the benefits of depth by presenting a family of functions (based on sim- ple 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 approximation theory, one typically tries to understand how to best approximate a complicated family of functions using simpler functions as building blocks. For instance, Weierstrass (1885) proved a general result stating that every continuous function can be uniformly approximated as closely as desired by a polynomial. It wasn't until later that Vitushkin (1959) gave quantitative bounds between the approximation error and the polynomial's degree. Drifting away from polynomials and given the recent breakthroughs of deep learning in a variety of difficult tasks like image classification, natural language processing, game playing and self-driving cars, researchers have tried to understand the approximation theory that governs neural networks. This question of neural network expressivity, i.e. how architectural properties like the depth, width or the activation units affect the functions it can compute, has been a fundamental ongoing challenge with a rich history. A classical result by (Cybenko (1989) , Hornik et al. (1989) , Fukushima (1980) ) demonstrates the expressive power of neural networks: it states that even two layered neural networks (using well known activation functions) can approximate any continuous function on a bounded domain. The caveat is that the size of such networks may be exponential in the dimension of the input, which makes them highly susceptible to overfitting as well as impractical, since one can always add extra layers in their model aiming at increasing the representational power of the neural network. More recently, in a seminal paper by Telgarsky (2016) , it was shown that there exist functions that can be represented by DNNs, i.e, by some particular choice of weights on their edges (and for a wide variety of standard activation units in their layers), yet cannot be approximated by shallow networks unless they are exponentially large. More concretely, he showed that for any positive integer k, there exist neural networks with Θ(k 3 ) layers, Θ(1) nodes per layer, and Θ(1) distinct parameters which cannot be approximated by networks with O(k) layers, unless they have Ω(2 k ) nodes. At a high level, he uses the number of oscillations present in certain functions as a notion of "complexity" that distinguishes between deep and shallow networks' representation capabilities via the following facts: a) functions with few oscillations poorly approximate functions with many oscillations, b) functions computed by networks with few layers must have few oscillations and c) functions computed by networks with many layers can have many oscillations. Our main contribution is a novel connection between the theory of dynamical systems and the representational power of DNNs via the well-studied notion of periodic points, a notion that captures the important notion of fixed points of a continuous function. Definition 1 (Period). f n (x 0 ) = x 0 and (point of period n) In particular, all numbers in C = {x 0 , f (x 0 ), f (f (x 0 )), . . . , f n−1 (x 0 )} are distinct, each of which is a point of period n and the set C is called a cycle (or orbit) of period n. Observe that since f : [0, 1] → [0, 1] is continuous, it certainly has at least one point of period 1, which is called a fixed point. For the rest of this paper, we focus on (continuous) Lipschitz functions f : [0, 1] → [0, 1], unless otherwise stated. Note that the choice of interval [0, 1] is for simplicity of our presentation and that our results will hold for any closed interval [a, b]. As we observe, points of period 3 are contained in both Telgarsky (2016) and Schmitt (2000) constructions and this could as well have been a coincidence, however we show that the existence of periodic points of certain periods are actually one of the reasons explaining why depth is needed to represent functions that contain them (otherwise exponential width is required). Towards this direction, we will make use of a deep result in the literature of iterated dynamical systems called Sharkovsky's Theorem Sharkovsky (1964; 1965) . In this section, we provide some additional theoretical and experimental remarks on our characterization.
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  Shows how the expressive power of NN depends on its depth and width, furthering the understanding of the benefit of deep nets for representing certain function classes. The authors derive depth-width tradeoff conditions for when relu networks are able to represent periodic functions using dynamical systems analysis.