Depth-Width Trade-offs for ReLU Networks via Sharkovsky's Theorem
Authors: Vaggos Chatziafratis
Sai Ganesh Nagarajan
Ioannis Panageas
Xiao Wang
Venue:  (2020)
Keywords: Depth-Width trade-offs
ReLU networks
chaos theory
Sharkovsky Theorem
dynamical systems

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 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.

Published as a conference paper at ICLR 2020
DEPTH-WIDTH TRADE-OFFS FOR RELU NETWORKS VIA SHARKOVSKY'S THEOREM
Vaggos Chatziafratis
Department of Computer Science Stanford University
Sai Ganesh Nagarajan Ioannis Panageas & Xiao Wang
Singapore University of Technology and Design
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 seminal paper, Telgarsky high- lighted the benefits depth by presenting 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 '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-aaproximmtee by smaller depths.
In this work, we point to 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 the presence of a generalized notion of fixed points, called periodic points (a fixed point is point of period 1). Motivated by 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 the celebrated result by Li-Yorke we proceed to give general lower bounds for the width needed to represent periodic functions 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.
INTRODUCTION
In approximation theory, one typically tries understand how to best approximate a complicated family of functions using simpler functions as building blocks. For instance, Weierstrass (1885) proved general result stating that every continuous function can be uniformly approximated as closely as desired by a polynomial. It wasn't t until later that Vitushkin (159)) gave quantitative bounds between the approximation error and the polynomial's degree. Drifting away from polyno- mials 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 nerwork expressivity, i.e. how architectural properties like the depth, width or the activation units affect the functions it can compute, has been fundamental ongoing challenge with rich history. classical result by [Cybenko| (1989). Hornik et al. (989), Fukushima (198)) 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.

---

Published as a conference paper at ICLR 2020
More recently, in seminal paper by Telgarsky (2016), it was shown that there exist functions that can be represented by DNNs, Le, 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 ki there exist neural networks with ((-)) layers, ((1) nodes per layer, and (1) distinct parameters which cannot be approximated by networks with (kk) layers, unless they have 22(2*) 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 three 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 rep- resentational 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). We say that (continuous) Lipschitz function f : [0, 1] + [0, 1] contains point of period 2 if there exists a point 2o E [0, 1] such that"
("(x)) = 3o
and (*())) F vo, A visksn-l.
(point of period r²)
In particular, all numbers in C = fao. fx)), f f(f(z))).... (x-))((()) are distinct, each of which is 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. - [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 are contained in both Telgarsky (0166) and Schmitu (2000) con- structions 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, that gave rise to the field of Combinatorial Dynamics (Alseda et al. (2000)), called Sharkovsky's Theorem (Sharkovsky 1964 1965)).
1.1 SHARKOVSKY'S ' THEOREM
Consider the set of positive natural numbers No = (1,2,.... and define the following (decreasing) ordering & called Sharkovsky's 's ordering as follows:
3>50 ................................ (odd numbers bigger than one)
62. 32.302.555 50 7 . & (odd multiples of two but not two)
22 22 2 . (odd multiples of four but not four)
>... 21 23 2 2 (powers of two in decreasing order).
This is a total ordering; we write / > or r < I whenever / is to the left of r. Sharkovsky showed that this ordering describes which numbers can be periods for a continuous map on an interval; allowed periods need to be suffix of the Sharkovsky ordering:
Theorem 1.1 (Sharkovsky's "Forcing" Theorem, Sharkovsky (1964 1965)). Let T be a closed in- terval and - be a continuous map. If n is a period for f and n n', then n' is also a period for f.
Remark 1.I. Note that the number 3 is the maximum period according to Sharkovsky's 's ordering, so important corollary is that function having point of period must also have points of any
As usual, (z0) denotes the composition of with itself times, evaluated point 270
2

---

Published as a conference paper at ICLR 2020
period. This special corollary is weaker version of Sharkovsky's theorem and proved some years later in a celebrated result by Li & Yorke (1975), who coined the term "chaos" as used in Mathematics.
We conclude the subsection with the definition of a prime period of a function f. Definition (Prime period). function f has prime period as long as it has a cycle of period n, but has no cycles with period greater than according to the Sharkovsky ordering.
For example, in the interval [0,1], the function f(z) = 1 - x has prime period 2, since f(f(x)) = (1 - = x. so all points are periodic with period 2, except the fixed point at 1/2.
Before formally stating our main theorems, we present an illustrative example inspired from Telgar- sky's triangle wave construction and we connect it to DNNs' sensitivity to weight perturbations and their representational power.
1.2 SENSITIVITY ANALYSIS A MOTIVATING EXAMPLE
An important ingredient Telgarsky's 's proof, was the "triangular wave" function (sometimes re- ferred to as the tent map or sawtooth) depicted in Figure Ib]and given by:
2x,,
if 505505
-(1-x), t(x;2) = 2(1 x)),
if <
0,
otherwise
He shows that the composition of f(:; 2) with itself & times (denoted by (x; 2)), will create expo- nentially (in k) many oscillations and result he able to show a separation for the classification error when using shallow deep neural network predictor.
Our starting point the observation that the triangular wave function (xx;) contains points of period 3. e.g. (2
+ (.) It follows in particular, that ((r;; 2) exhibits Li- Li-Yorke Chaos
(Li Yorke (1955) in the sense that it contains all periods. The compositions of such functions will look highly complex (see /ee/ure 2) and in fact Telgarsky heavily relied on the highly oscillatory behavior of ((;; 2) to prove his depth separation result.
what would happen if one used slightly modified version of the triangle wave t(;;; 2). Observe that since simple neural network with one hidden layer represent the function (a:; 2), the question is basically equivalent asking how modifying the weights on the edges of the neural network can affect its representational power (see (see Figure T). hence the title of the current subsection. The main question is can have general theory that informs us on when will the function composition be hard to represent and when not? Our paper's s main point to provide an answer by checking if the function at hand has a simple property, relating to the presence of chaotic behavior.
However, his result doesn't 't inform
To illustrate our point, consider the generalized triangle wave function t(:; (1) parameterized by μc:
paz,
ifos=s} <
t(:;1)
p(1 x),
0,
otherwise
This function parameterized by / ranges from [/2) and is closely related the logistic map [(x) == r - x) used in Schmiti 2000) and exhibits a variety of limiting behaviors: for instance, converges to stable fixed point when μ if we set fu 1. we get the network depicted in Figure Ic]
exhibits chaos when μ = 2 etc Instead of μ 2,
Duue to historical reasons during the late 20th century, the theory of dynamical systems saw a parallel development in the USA and the USSR, hence Sharkovsky's theorem (1964) remained unknown the USA, until in 1975 weaker version was rediscovered by James Yorke and his graduate student Tien- Yien Li, in their celebrated paper called "Period Three Implics Chaos".
For more, the interested reader can also check https::/eet wik ped' www.g/wwkiiii /ogiii/oooisiiii
map
3

---

Published as a conference paper at ICLR 2020
0
t(2; 2)
O
4
0.5
(a) Neural with the appropriate weights and biases (the value indicated inside the hidden and output neurons).
(b) Tent map with 2
t(æ; 1)
0
-2
0.5
(c) Neural net with the appropriate weights and biases (the value indicated inside the hidden and output neurons).
(d) Tent map with y
Figure 1: The neural network instantiations that used create two different tent maps which vary only in the maximum value. This is effected by a small change weights the output layer. All activation functions are ReLU's.
Note that compositions of f(;; (created by the same neural network architecture but with slightly different weights), behave completely differently since the = case, we will not get highly oscillatory behavior. This can be seen in Figure 3 One difference between the two cases is the relative position of the map with the line y and their generalizations i.c. periodic orbits play important role when dealing with function compositions. Indeed, despite the wide range of possibilities one can expect by composing such show, their behavior the exponential growth in complexity (or lack thereof) of these compositions can be explained by invoking fundamental property of these continuous functions bounded intervals which is the existence (or not) of periodic points of certain periods.
and this seems
pointing that fixed points
functions,
be characterized using tools from dynamical systems;
argue about changing the parameters of the logistic map which is given by f(;;r) := rz (1 I) used in Schmitt (2000) for sigmoidal networks (where 4x; was used). The properties of the logistic map are well known and was first studied by Robert May and Mitchell Feigenbaum (May 1976) and Feigenbaum (176)). It is known that as one varies the parameter r, the logistic map gives rise plethora of different behaviors, hence the same true for when one slightly perturbs the weights of neural net used to represent the map. Please refer to AApendixx C for some figures that illuminate these differences in the logistic map.
Similarly,
1.3 INFORMAL STATEMENTS MAIN THEOREMS
We demonstrate that simple property of governs the depth-width trade-off's in order represent it and we give quantitative bounds for them. This simple property has to do with the periods that the function f contains. Informally, our first main theorem states that function contains periodic points with certain periods, then composing f with itself many times, will result in exponentially many oscillations, giving rise to complicated behaviors and chaos:
Theorem 1.2. Let f [0, 1] - [0, 1] be a continuous function. Assume that there exists a cycle of period where
p with being an odd number greater than one and with m being
4

---

Published as a conference paper at ICLR 2020
100
0.
01
(a) (a) = 3.9 20 2) on the interval [0, 1]
(b) (1x of the map on the left (zoomed in)
Figure 2: Compositions of the logistic map f(x) 3.9x(1 x) defined the interval [0, 1]. This map well known to exhibit chaos and in the above figure non-vanishing oscillations that grow with the number of compositions, albeit irregularl..
(a) (w;p)) for the tent map with j = 2 (blue) and μ (red)
(b) 6 ("(;; μi) for the tent map with = (blue) and 1 (red).
Figure 3: Compositions f(x;; v)) with different parameters μa = and are shown. The compositions create (cxponential) non-vanishing oscillations when f = 2, however the compositions remain unchanged when L.

---

Published as a conference paper at ICLR 2020
power of two (it might be = 1). Then, there exist y. E [0. 1] such that the function fm (taking mt compositions of with itself) "oscillates" (also look Definition (4) at least pf times between and y for all t E N,, where p is the positive root greater than of the polynomial equation XP-1 Xp-2
O.
Our second main theorem then draws the connection between the number of oscillations a function has and the depth- width trade-offs needed:
Theorem 1.3. Let k be positive integer and f be function as above. We set to be the positive root greater than one of the polynomial equation
We can construct a sequence - such that the classification error of the function funk is zero, whereas the classification error of any neural network with layers and u nodes per layer, where
of points (æi, ))) with n :- -
< 8. necessarily has classification error 2 1
Formal statements for the two theorems can be found in [Section 3 and [Section]4
Using these theorems, we draw connections with previous results (elgarsky| (2016), Schmitt (2000) in a unified way. thus identifying chaotic behavior as the main underlying thread for depth- width trade-offs. Technically, our approach is based on an eigenvalue analysis of certain matrices associ- ated with such periodic functions.
1.4 OTHER RELATED WORK
Understanding the benefits of depths on the expressive power a specific computational model can have, is an important area of research spanning different computational models and results come in the flavor of depth separation arguments. Roughly speaking, many of the results in this area rely on a suitably defined notion of "complexity" of a function we would like to represent, and then proceed by proving that under this notion, deep models have significantly more power than shallower models. For example, if the computational model of interest is the family of boolean or threshold circuits, depth lower bounds are given in Hasttd (1986); Rossman et al. (2015); Hástad (987); Parberry et al. (1994); Kane & Williams (2016). Furthermore, people have analyzed sum- product networks (summation and product nodes) and studied trade-offs for depth (Delalleau &
Bengio (2011) Martens & Medabalimi (2014)).
Coming closer to neural networks computation where the activation units can be general vall-v functions, important previous results include Eldan & Shamir (2016); Telgarsky (2015)
2016);
Schmitt (2000): Montufar et al. (2014); Malach & Shalev-Shward (2019); Poole et al. (016);
Raghu et al. (2017); Arora al. (2016); Liang Srikant (2016); Kileel al. (2019). Regarding
the aforementioned notions of "complexity" used in depth separation arguments, examples include the notion of global curvature (Poole et al. (2016)) trajectory length (Raghu et al. (2017). number of oscillations (Telgarsky] (2015) 2016) and [Schmitt (2000)), number of linear regions (Montufar Shhalv-Shwwrtz// (2019)), dimensions for algebraic varieties (Kileel et al. (2019)) and more. Our work is more closely related to Telgarsky (2015 2016), and [Schmitt (2000) since it is easy to see that their maps are chaotic, but we conjecture that many of the notions of complexity introduced in this line of research showcase benefits of depth actually arise due to chaotic behavior. In this sense, we conjecture that chaotic behavior is the main culprit for the failure of neural networks represent certain functions, unless they sufficiently deep (or have exponential width). Moreover, other works that have exploited the powerful result by Li- Yorke (in online learning frameworks) are PPllioopanos et al. (2077): Chotibut al. (2019).
al. (2014)), fractals (Malach
FURTHER BACKGROUND: THE COVERING LEMMA
The crux of the proof of Sharkovsky's theorem provided by Burns & Hasselblatt (201T) contains covering lemma that will be our starting point to prove our main results. Before we proceed with the statement of the Covering Lemma, we provide one more important definition.
Definition (Covering relation). Let ff be a function and 1 In be two closed intervals. We say that
I covers 1a under denoted by J L, Tz as long as Ta s(1)..

---

Published as a conference paper at ICLR 2020
f
Jo
Jr
Ji
f
Jo
J1
E
f
J2
(a) Covering Lemma period three (r 1).
Commaarreation reeationn for cycle
(b) Covering Lemma | relations for cycle of odd period at least three.
Figure 4: The covering relations of intervals Ja, ..., J, from Lemma | Observe that the graph is directed cycle with a self loop at interval Jo. Note that there might be more relations ("edges").
For example, the triangle wave f(x;2 2) that has the period 3 point (recall g
)
naturally defines intervals I [2 4 and 12
[4
8 with the covering relations: g
Iı 4 I2.
g
12 4 12 and l2 4 I1.
Lemma (Covering Lemma for odd periods). Let f [0, [0, be continuous functionn and assume f has cycle C of period n, where the elements of the cycle in increasing order and define the sequence of closed intervals To, Io....,In.-
is odd number. Denote 3a....,,,.
C
where = [,,,3,+ [,+1] (they have pairwise disjoint interiors). Then, there exists a sub-collection of the aforementioned intervals (not necessarily in the same ordering) Jo....,, with < r S such that the following covering relation holds:
1. J; I. Jit1, for si
2. J, 4 Jo and Jo 4 Jo J1.
For a pictorial illustration of the Covering Lemma, see Figure|4 In particular, observe that for n = get
the covering relation is in Figure We conclude this section with the formal definition of crossings (or oscillations) and we refer the reader to Figure for some examples.
Definition 4 (Crossings). We say that a continuous function f [0, + [0, crosses the interval [x, vl with x, y E [0, if there exist a, b such that f(a) x and f(b) = y. Moreover we denote (f) the number of times f crosses [x. y). That is Cz.g(f) a2, b2 < .... < at, by in [0, 1] so that f(a;)) = x and f((b:) = y for all S S Observe that if I,z is used to denote the number of intervals the function fz)(2)) = 1 [f(()) N = is piecewise constant and partitions (0, 1), then Cr, S I
t there exist numbers a1 bı <
3 PERIODS DETERMINE THE NUMBER OF CROSSINGS
3.1 PERIOD THAT IS NOT POWER OF TWO IMPLIES EXPONENTIAL. CROSSINGS
In this section, we prove main theorem, the statement of which is given below. Technically, we make use of the Lemma [ (Covering Lemma) to show the exponential growth of the number of crossings.
[0. 1] be a continuous function. Assume that there exists cycle of period n where = m P, is an odd number greater than one and m being power of two (ir might be m 1). It holds that there exist x, y [0,1] so that Cz, fmm)) is d for all E N where
Theorem 3.1. Let f [0,
the positive root greater than one of the polynomial equation XP-1 XP 1= 0.
'In Telgrasky's 's paper, I, is used to denote the number of intervals where 1f((z) 2 1 is piecewise constant and partitions (0, 1).

---

Published as a conference paper at ICLR 2020
For given continuous function [0 [0. 1], let Jo. Jo...., Jy, where 1 I Σ n a-2 2. be the intervals as promised from Lemma I We define a sequence of vectors 8 E N++ such that 8 is defined as the number of times the function f crosses the interval J; for all 0 S i I r. In particular we define fo to be the identity function and hence 8 = (1,- .......)) ,1 (all ones vector). For what follows, 8'-1 and in the end we will show that of is S((c)) where с is some constant that depends on To build some intuition, we first analyze the case of period three and then prove the general case.
Counting the number of oscillations.
will try express recursively 5 in terms of
3.1.1 WARM UP: THE CASE OF PERIOD 3 AND THE FIBONACCI SEQUENCE.
Assume that f has cycle of period that is the numbers { (((0)) are distinct and (xo) = Ty for some To E [0. 1]. Let 30 < 81 < 32 be the numbers We. [ (mo) in
increasing order. We define Io- [So, 3,] and I1 [3 32]. From Lemma [ when 3, we can
see that r = 1 and thus we have the following possibilities for the covering relations:
Either To 4 To JoUT J,
or 1i 4 Ih
We define Jo to be the interval among lo, J that involves the self-loop covering and J1 to be the remaining interval. Define 8 E N² as above, and so we get that:
(
6 gt+1
1
%
8 +
Z
1
8j
(3.1)
)) can be interpreted as the adjacency matrix
where 80 and 8 = 1. The matrix A =
that corresponds to the covering relations between Jo, J1 (which consists of a directed cycle with a self-loop at vertex Jg). The reason we have an inequality instead of an equality is because the Covering Lemma only guarantees that the number of times Jn "covers" Jo and J1 is at least one and not necessarily exactly one.
We set a 8 and we define *+1 N. Moreover, ab is the well-known Fibonacci sequence Fet1 (with Fo Fi 1), therefore
Aa'. is clear that 8 2 a (entry- wise) for all t
(1455) (-))))))-(---))
af
We conclude that 86 (2+55) See also Figure for a pictorial
v5
illustration about the proof for t 1,2,3,4 4.
3.1.2 EVERY PERIOD GREATER THAN 3 BUT NOT POWER OF TWO
Assume that ʃ has cycle of period ( ) (xo), fn- (xo)) are distinct and f"(xo) = Tp for some xo [0. Let Po < < B2 ... < 8n-1 be the numbers zo. (xr)) ( (xo), (xo) in increasing order. We define 1, = [8,, B141] for < i S n 2. From Lemma it follows that there is a subcollection
> 3 with odd, that is the numbers
of the intervals lo..., In- (with not necessarily the same ordering) Jo....,,, (1 S 2) such that
1. Jj 4 J4L for 1
2. J, 4, Ju and Ju 4 Jo Jr.
The interval Jo is the that involves the self-loop covering. As in the for 3, define 5 which is in Nr+1, with of capturing the number of times f crosses the interval J, We get that:
o
A
(3.2)
g++1
8

---

Published as a conference paper at ICLR 2020
where 8 (1,.... , 1) (all ones vector) and A ((++))((++1) is defined to be:
AJ: = 1, if 0,j =
A₁; = 1, = and 0 - -isr-1
(3.3)
Ay: 1, if =fi=
A₁ 0, otherwise
In words, is the adjacency matrix of graph with + nodes that is a directed cycle that involves a self-loop vertex Jo- We define a² in similar way as in the case for period three, i.e., a Ao and a = 8 so that 8 2 of (entry-wise) for & E N. We can easily observe that the following holds: a+1 a
Our next plan is to compute a lower bound on the spectral radius of the matrix A (denoted by sp(AT) )) with the following claim (proof in Appendix A).
Claim 3.1. The characteristic polynomial of A is:
x (A) X 1
(3.4)
Let us call pr the largest root in absolute value of the polynomial (A)) in A.1 Since A is negative matrix, the largest root in absolute value is actually a positive real number (by the Perron- Frobenius theorem). is easy see that the polynomial in A.1 has always root greater than and less than two (by Bolzano's 's theorem, see (1) = < 0 and π (2) = 2"+1
= 2" > 0).
Hence have sp(A) P. > 1. Furthermore, it is easy (and powers of A are also non-negative), it holds that
that since A is non-negative matrix
A
Ab
for all / 2 1, that is the row with the largest sum of its entries is the first row (row for i = 0). Using the fact that
| | 2 sp(A') = Pr:
that is the spectral radius of a matrix is always at most any matrix norm, we conclude that Ejzo Aby 2 pf..
The case of odd period greater than three follows by noting that Σj= Abj aij thus 8 2 at
P. Observe that for period three, we have that = and also P1 1+y5 (the largest root of 0).
2
We would like to make the following two remarks:
Remark 3.1. The spectral radius Pr is strictly decreasing in this is easy see since Pr 1 and satisfying the equation x++1 x" = (note that -=+1 x" increasing in r for x > 1). This implies that smaller odd periods can potentially have number of crossings that grows faster rates than larger odd periods, hence giving rise to more complex behaviors. See also Remark 4.1
Remark 3.2 (The case of even period but not power of two). Our result above is applied for cycles of period n = m n' where m is a power of two and n' an odd number greater than one. The trick is to observe that if a function has cycle of period n, then fd has eycle of period n' (which is an odd number greater than one). Therefore, the number of oscillations Cz.y (frmi with æ, y being the endpoints of Jo. is at least P/ for t E N.
Proof of Theorem 3.7
The proof now follows from the case analysis carried out in Sections
3.12 and Remark 3.2
3.2 PERIOD THAT IS A POWER OF TWO MAY HAVE POLYNOMIAL CROSSINGS
Lemma 2 (Period power of two proof in Appendix A). There exist continuous functions f with prime period n that is a power of two so that the number of crossings Cz.y((t) scales at most polynomially with t for any x. y [0, 1).

---

Published as a conference paper at ICLR 2020
4 PERIOD-DEPENDENT LOWER BOUNDS FOR DNNS
Building on Telgarsky 2015 2016), the representation power of different networks will be measured via the classification error. For given collection of points (æ;, Us) with Yi {0, 1), one can define the classification error of a function to be (g is just the thresholded value of g):
R(g) = (0(x;) # Mil
In this section, we argue that functions with cycles of period not power of two, will have compo- sitions for which any shallow neural network will have classification emor positive constant.
Assume we are given continuous function f: [0, 1] -> [0, 1] so that f has cycle of period m x p where p is an odd number greater than one and m is a power of two. From Theorem there exist
J, E [0. 1] so that (f.)( is at least 6 2 where Pr is defined to be the root that is greater than one of the polynomial equation A A 1 O. We set p Pp-2. 2. h == fkom and assume that g [o, 1] + [0, 1] is a neural network with layers and u nodes (ReLU activations) per layer. In Lemma 2.1 of Telgarsky (2015), it is proved that neural network with u ReLU units per layer and with layers is piecewise affine with at most (2m)' pieces.
We define as h((z) [[((z) 2 2 and g(2) = 1 1g(z)> 2 (note that we changed the threshold
to be xtv instead of that was used in Telgarsky (0155). 2
Since Cz.y (h) is least p², it holds that there exist points (zi, W) with Le" such that h(z;) = x, Mj = 0 for j odd and h(z;) y, Mj = for j even. is clear that for this collection of points the classification error of the function h is zero, whereas the classification error for function g is bounded from below by
4(2u)
(2u)
R(g)
2
2n
n
The above inequality is an application of Lemma 2.2 of Telgarsky (0015) (with careful counting has been slightly improved). By choosing be at most pf it holds that the classification error R(g) 2 for any neural network with ReLUS and layers.
The above discussion implies the following theorem:
Theorem 4.1 (Classification Error Theorem). Let k be a positive integer and f be a function of period m. x p with p an odd number greater than one and m. being a power of two might hold
1). We set to be the positive root greater than one of the polynomial equation
= 0.
We can construct sequence of points (Ii, ):m with n Le so that the classification error of function frnk zero, whereas the classification error of any neural network of layers and u nodes
per layer with u S f satisfies R(g)= 2 1.
Remark 4.1. Observe that the number of units u per layer constant and the number layers I is o(k), then the classification error is always positive constant for any neural network (whereas for frisk is zero). Moreover, observe that since p is decreasing in p (recall p is the odd factor of the period), it holds that the classification error decreases p increases (with fixed number of layers and nodes per layer). This indicates that the composition functions with large odd period is simpler than of functions with small odd period (period greater than one) following the intuition have from the Sharkovsky's ordering.
ACKNOWLEDGMENTS
Vaggos Chatziafratis is partially supported by an Onassis Foundation Scholarship. Sai Ganesh Na- garajan would like to acknowledge SUTD President's 's Graduate Fellowship (SUTD-PGF). Ioannis Panageas and Xiao Wang would like to acknowledge 136 and ANR NRF 0095 ALIAS. Part of this project happened while the authors visiting the Simons Foundation program "Foundations of Deep Learning" at Berkeley and would like to thank the organizers for their hospitality.
A.F-NREFAII-2019-0000 SRG ISTD 2018
10

---

Published as a conference paper at ICLR 2020
REFERENCES
Lluis Alseda, Jaume Llibre, and Michal Misiurewicz. Combinatorial dynamics and entropy in di- mension one, volume 5. World Scientific Publishing Company, 2000.
Raman Arora, Amitabh Basu, Poorya Mianjy, and Anirbit Mukherjee. Understanding deep neural networks with rectified linear units. arXiv preprint arXiv: /61 1.01491, 2016.
Philip G Breen, Christopher N Foley, Tjarda Boekholt, and Simon Portegies Zwart. Newton vs the machine: solving the chaotic three-body problem using deep neural networks. arXiv preprint arXiv:1910.07991, 2019.
Keith Burns and Boris Hasselblatt. The sharkovsky theorem: A natural direct proof. The American Mathematical Monthly, 118(3)2229-244, 2011.
Thiparat Chotibut, Fryderyk Falniowski, Michal Misiurewicz, and Georgios Piliouras. The route to chaos in routing games: Population increase drives period-doubling instability, chaos & ineffi- ciency with price of anarchy equal to one. CoRR, abs/1906.02486. 2019.
George Cybenko. Approximation by superpositions of sigmoidal function. Mathematics control, signals and systems, 2(4):303-314, 1989.
Olivier Delalleau and Yoshua Bengio. Shallow vs. deep sum-product networks. In Advances in Neural Information Processing Systems, pp. 666-674, 2011.
Ronen Eldan and Ohad Shamir. The power of depth for feedforward neural networks. Conference on learning theory, pp. 907-940, 2016.
MJ Feigenbaum. Universality in complex discrete dynamics. Technical report, LA-6816-PR, LASL Theoretical Division Annual Report July 1975-Se7ee Sertt-eete,,rr, 1976.
Kunihiko Fukushima. Neocognitron: A self-organizing neural network model for mechanism of pattern recognition unaffected by shift in position. Biological cybernetics, 36(4):193-20, 1980.
Johan Håstad. Computational limitations of small-depth circuits. 1987.
John Hastad. Almost optimal lower bounds for small depth circuits. In Proceedings of the eighteenth annual ACM symposium on Theory of computing, pp. 6-20. Citeseer, 1986.
Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks are uni- versal approximators. Neurul networks, 2(5):359-366, 1989.
Daniel M Kane and Ryan Williams. Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pp. 333-643. ACM, 2016.
Joe Kileel, Matthew Trager, and Joan Bruna. On the expressive power of deep polynomial neural networks. arXiv preprint arXiv: 12007, 2019.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 1rXiv:1412.6988. 69800 2014.
Tien-Yien Li and James A Yorke. Period three implies chaos. The American Mathematical Monthly, 82(10)9985999, 1975.
Shiyu Liang and Rayadurgam Srikant. Why deep neural networks for function approximation? arXiv preprint arXiv:1610.0416. 2016.
Julia Ling, Andrew Kurzawski, and Jeremy Templeton. Reynolds averaged turbulence modelling using deep neural networks with embedded invariance. Journal of Fluid Mechanics, 807:155- 166, 2016.
Lu Lu, Yanhui Su, and George Em Karniadakis. Collapse of deep and narrow neural nets. arXiv preprint arXiv: 1808. 099444447 2018.
11

---

Published as a conference paper at ICLR 2020
Eran Malach and Shai Chalev-Shwartz Is deeper better only when shallow is good? arXiv preprint arXiv:1903.03488, 2019.
James Martens and Venkatesh Medabalimi. On the expressive efficiency of product networks. arXiv preprini urXiv: 2014.
Robert May. Simple mathematical models with very complicated dynamics. Nature, 261(5560): 459, 1976.
Guido F Montufar, Razvan Pascanu, Kyunghyun Cho, and Yoshua Bengio. On the number of linear regions of deep neural networks. In Advances in neural information processing systems, pp- 2924-2932, 2014.
Gerasimos Palaiopanos, Ioannis Panageas, and Georgios Piliouras. Multiplicative weights update with constant step-size in congestion games: Convergence, limit cycles and chaos. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Pro- 2017.
cessing Systems 2017, 4-9 December 2017, Long Beach, CA, USA, pp.
Ian Parberry, Michael R Garey, and Albert Meyer. Circuit complexity and neural networks. MIT press, 1994.
Ben Poole, Subhaneil Lahiri, Maithra Raghu, Jaseha Sohl-Dickstein, and Surya Ganguli. Exponen- tial expressivity in deep neural networks through transient chaos. In Advances in neural informa- tion processing systems, pp. 3360-3368, 2016.
Maithra Raghu, Ben Poole, Jon Kleinberg, Surya Ganguli, and Jascha Sohl Dickstein. On the expressive power of deep neural networks. In Proceedingy of the 34th International Conference on Machine Learning- Volume 70, pp. 2847-2854. JMLR. org, 2017.
Benjamin Rossman, Rocco A Servedio, and Li- Yang Tan. An average-cuse depth hierarchy theorem for boolean circuits. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pp. 1030-1048. IEBE, 2015.
Michael Schmitt. Lower bounds on the complexity of approximating continuous functions by sig- moidal neural networks. In Advances in neural information processing systems, pp. 328-334, 2000.
OM Sharkovsky. Coexistence the cycles of a continuous mapping of the line into itself. Ukrainskij matematicheskij zhurnal, 16(01):61-71, 1964.
OM Sharkovsky. On cycles and structure continuous mapping. Ukrainskij matematicheskij zhur- nal, 10403):004-11,, 1965.
Matus Telgarsky. Representation benefits of deep feedforward networks. arXiv preprint 10X 2015.
Matus Telgarsky. benefits of depth in neural networks. In Conference Learning Theory, pp- 1517-1539, 2016.
AG Vituhkkn. Estimation of the complexity of the tabulation problem, 1959.
Karl Weierstrass. Über die analytische darstellbarkeit sogenannter willkürlicher functionen einer reellen veränderlichen. Sitzungsberichte der Königlich Preußischen Akademie der Wissenschaften zu Berlin, 2:633-639, 1885.
A APPENDIX
Claim A.I. The characteristic polynomial of A is:
क *())
X -
(A.1)
12

---

Published as a conference paper at ICLR 2020
Proof. Let I denote the identity matrix of size (r
1)
(r
+
1).
We consider the matrix:
X
0
0
0
0
0
0
0
0
0
AT A X
: 0
0
1
Observe that = 0, are not eigenvalues of the matrix A hence we can multiply the first row by X-1 the second row by x(x-1), the third row by x²(A-1) the i-th row by x=-1(A-1 (and so on) and add them to the last row. Let B be the resulting matrix:
1
0
0
0
0
0
1
B
:
0000
->
0
0
0
0
-X + x (A-1)
clear that det( (B) = as an equation has the same roots as det(AT AI) = 0. Since an upper triangular matrix, it follows that
dct(B) = (-1)" (- (-+--------
We conclude that the eigenvalues of T (and hence of A) must be roots of (A" X--1 and the claim follows.
Lemma 3 (Period power of two). There exist continuous functions f with prime period n that is power of two so that the number of crossings (ft) scales at most polynomially with t for any n, 10, 1].
Proof. The easiest example one can construct is the function / [0, - [J that defined f(x) =
Observe that for any [0, 1] one has f(f(a)) f(a) + a. Hence is a function of prime period two. is also clear that f'(x) if is even and ('(x)) = x if is odd, so the number of crossings is always one for all / N
and moreover if + 1 then
One other less trivial example is the following function (see also Figure
- +, f(z)
1<x<2
+7, 2 2 3
2 2,
3 S 4.
not hard to see that this function has prime period four (/(1) = 4, f(4) 2, = =3,(33
1). Let Jo [1, J1 = 3]. J2 [3, 4). It is clear that
f(J) Jz. f(J]) Jo J. and f(J2) Jp.
By letting o be the number of crossings of the function f for the interval J, (i E (,,1,2]) one has recursively
+++1
0 1
+1
=
0 1
0
(A.2)
1
where 8 (1, 1) (all vector). easy observe that the matrix A
0
0 has
spectral radius (as opposed to the case of odd period greater than one) and moreover holds
13

---

Published as a conference paper at ICLR 2020
4.5
45
3.
2.5
18
05
0.
(b) This figure captures two compositions of func- tion f. Ohserve that f crosses the interval [2, 3] three times (two times for E [2,3] and once for x E [1. 2)) and it crosses the interval [1, 2] two times (once for E [1.2] and once for E [2,3]) In particular, 8 (3,
(a) This figure captures one composition of function
f. Observe that of crosses the interval [2, 3] two times (once for x E [1 and once for æ E [2.3] 3) and it crosses the interval [1,2] once. In particular, 6' (2, 1).
45
4.5
3.5
3.5
1M
2.25
255
1.5
1.5
0.5
(c) This figure captures three compositions of func- tion f. Observe that f crosses the interval [2.3] five times (three times for æ [2, 3] and twice for
(d) This figure captures four compositions of func-
tion f. Observe that f crosses the interval [2,3] cight times (five times for x: [2, 3] and three times for x E [1, 2)) and it crosses the interval [1, 2] five times (twice for E [1, 2] and three times æ [2, 3). In particular, 8 = (8, 5).
E [1,2]) and it crosses the interval [1, 2] three times (once for æ E [1 and twice x E [2, 3). In particular, = (5.3).
Figure 5: Compositions of piecewise linear function that has a point period
35-
15-
83
35
Figure 6: A piecewise linear function f: [[[1,4] + [1.4] that has prime period four.
14

---

Published as a conference paper at ICLR 2020
100
Pgo
(a) 8 2,,
(b) 8 = 2,,
(c) 8 = 3,
(d) 8 = (1, 5, 7)
Figure 7: Compositions piecewise linear function that a point period We start with the all ones
vector for 8 and each composition arises from the covering relation between the sets.
that E Eio for all E N We conclude that af + af + aB = 3. therefore the number crossings for Jo. J1, J2 of the function I' grows linearly with /. (and not exponentially). Since the function defined is of prime period four and is piecewise monotone (and so is any composition with itself) in each interval J1, J2, we conclude that the number of crossings of f for any possible pairs of values is
linear in
B AN EXAMPLE WHICH IS PERIOD 5 BUT NOT PERIOD 3 (LI & YORKE 1975))
Here, show example function, that has point of period 5, but not period 3, thereby respecting the Sharkovsky ordering. Our proof approach for general odd periods is similar to the case of period 3, by using the induced covering graph and counting the crossings over each interval. This is illustrated in Figure
C THE HETEROGENEITY OF THE LOGISTIC MAP
In this section, we illustrate how the compositions of the logistic map f(zrr) := rxx(1 - behaves as r varies slightly. We give certain examples in the form Figure It known that the map when 3.9, has point of period 3. In contrast when is reduced 3.5 the map has point of period and further bringing r down to 3.2 will ensure that the map has a point of period 2. The figures below illustrate how the oscillations grow under these scenarios.
15

---

Published as a conference paper at ICLR 2020
M
19
0.
08
104
2.55
0.4
(a) Here f(; 3.9) = 319x(1 x) is shown.
(b) Here f (a;; 3.9) is shown.
37
Here 3x5 3.5.z (1 x) shown.
(d) Here fl(x; 3.5) is shown.
37
82
05
62
35
(e) Here (x23 3.2x(1 2)) is shown.
(1) Here (z; is shown.
Figure 8: The compositions of the logistic map (x; = rx(1 2) with different parameter values are shown here. The left column has the functions themselves while the right column shows the corresponding compositions. We that oscillations in these family of functions vary vastly with changes and these changes are made weights of an appropriate neural network (see Telgarsky (016) Schmitt (000)).
16

---

Published as a conference paper at ICLR 2020
0.0
0.6
0.4
0.
02
(a) The numerical solutions to (xx) = x are shown here.
(b) The numerical solutions to g (x) x are shown here.
Figure 9: see that (xx has solutions other than just fixed point, since it intersections in other places, other than the fixed point. However, 9 (x) = ar does not have any solutions other than the fixed point, as there are no other intersections.
D FURTHER DISCUSSIONS
In this section, we provide some additional theoretical and experimental remarks on our characteri- zation.
D.1 INCORPORATING BIAS TERMS
If add bias term in the ReLU activation unit, e.g., use max(v, instead of max(r, 0) for the activation gates, where is small number (positive or negative), then our results do not change; in particular our trade-off in Theorem 4..1 still holds (since the Lemma 2.2 from Telgarsky (2015) is for general sawtooth functions). But, if one adds the bias term to the function f itself, then things get more interesting indeed: Suppose has some period p where p is a power of two; due to bifurcation phenomena (i.e., phenomena arising because we are at critical regimes of parameters such as the parameter ş our generalized triangle wave function), then the compositions of the function (f+bias term) with itself may give rise to qualitatively different behaviors compared to f. In particular, the function (f (f+bias term) might have period p anymore. Intuitively, one can think that the small bias term is amplified after many compositions and is not negligible anymore.
One such example the triangle function fz) = áz for S x S 0.5 and ((1-x) for 1/2 2 S 1, where é (1 + v5)/2 the golden ratio. This function has period 3, see Figure 9a However, we consider the function g(x) = (ø <)æ for () S x S 0.5 and (Φ -1)(1 -x) for 0.5 S x S 1 with
e > 0 (arbitrarily small positive) then does not have period 3, see Figure 9b In this sense, period
as property can be brittle to numerical changes if we are at the critical point.
D.2 SOME EXPERIMENTAL EVIDENCE
In this section, we provide experimental evidence for our depth separation results by training a neural network of constant width, but with increasing depth on classification task that closely resembles the n-allernatinn points problem that appeared in Telgarsky (2015) and is the foundation of our separation results as well. As mentioned before, this specific instance of function that has point of period 3. For simplicity, we do not consider this original problem exactly but rather "smoothed" variant of it, in order make it more amenable the training procedure. Our goal is to create diagram showing how the classification error drops function of the depth of the network for a fixed value of the width.
We create 8000 equally spaced points from [0,1] (in increasing order), where the first 1000 points are of label 0, the second 1000 are label and this label alternates every 1000 points. This is what we call a "smoothed" alternating point problem. Although, the theory would have used the classical 8-alternating points to argue about the lower bounds, in practice, performing training of deep (4 and above layers) and narrow networks (hidden layers with less than neurons) with very few data points is a major challenge, see for instance Lu et al. (2018). Apart from the separation results that show in theory, show empirically that deep networks generally do improve the accuracy in
17

---

Published as a conference paper at ICLR 2020
Classification Error (Fraction of misclassifed points)
Classification Error vs Depth
0.3
0.2
0.1
0.0
2
Depth
Figure 10: We that depth does reduce the classification error for this particular task and when depth is 5, the classification error is close The saturation in between may be attributed the general uncertainties the training/optimization.
this task compared to the shallow network and in fact a deep network with 5 layers can reach an accuracy of 99.04%. Any additional uncertainties in the error is generally attributed to the training procedure.
To perform the experiments, we vary the depth of the neural network (excluding the input and the output layer) as d = 1, 2, 4, 5. In addition, we fix the neurons for each layer to be 6. All activations are ReLU's, while the last layer is the classifier that uses sigmoid to output probabilities. Each model adds one extra hidden layer and we make use of the same hyper-parameters to train all networks. Moreover, require the training eπrоr the classification eπооr to tend to 0 during the training procedure, i.e, we will try and overfit the data (as we try to demonstrate a representation result, rather than parameters to train all the different models using the "ADAM" optimizer KKngmma & Ba (2014) and make the epochs to 200 in order enable overfitting. To record the training error, verify that the training saturates by seeing the performance over the epochs and report by default the error in the last epoch. The results are shown in Figure 10
result). Thus, for the actual training we the same
D.3 PERIOD AS A NATURAL CIARACTERRIZTTION
In nutshell, our paper provides a "natural" property of a function (periodic points certain periods) and then derive depth- depth-width trade-offs based on it. This addresses in Telgarsky (2016) 2015y's 's works, but also in the paper Poole et al. (2016) that seeks to provide natural, general measure of functional complexity helping understand the benefits of depth. On the contrary, many of the previous depth separation results take worst case approach for the representation question (showing that there exist functions implemented by deep networks that hard to approximate with a shallow net). However, it is not clear whether such analysis applies to the typical instances arising practice of neural-networks. We believe that our work together with Telgarsky (2016) 2015) and the paper Eldan & Shamir (2016) show depth separation argument for very natural functions, such as the triangle waves or the indicator function of the unit ball.
questions raised not only
Given specific prediction task in practice, how could one assess the period? We believe that this would be extremely useful yet a very difficult question that seems to be outside the reach of current techniques in the literature. Previous works and our work far are able to present depth separation for representing certain functions.
We point out that, intuitively, our characterization result consists of certificate informing us qualitatively and quantitatively about which functions have complicated compositions and which not. Similar to computational problems in class NP, if one is given the certificate (the points (z)...., pp), then one can easily verify (if we have oracle access to evaluate the function f), the given function has p-periodic cycle with points (31,...,, Tp). Nevertheless, believe that
18

---

Published as a conference paper at ICLR 2020
finding the certificate for arbitrary continuous functions is not straightforward problem, except maybe for particular restricted classes of functions. Having said that, we want to emphasize that in many prediction problems that inspired by physics, one may priori expect to have complicated dynamics behavior and hence require deeper networks for better performance. Such examples in- clude efforts to solve the notorious 3-body problem turbulent flows showing empirical evidence that complex physical processes require deep networks (see for instance, Ling et al. (2016) and Breen et al. (2019) that uses a 10 layered neural network).
19


Reviews:
[{"review_id": "ryl5620g5S", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper studies how the expressive power of NN depends on its depth and width. Sharkovsky's theorem is leveraged to characterize the depth-width tradeoff in the ability of ReLU networks to represent functions with periodic points. A lower bound on the depth necessary to represent periodic functions is also provided. All in all, the paper furthers the understanding on the benefit of deep nets for representing certain function classes.\n\nI found this to be a serious and well-written paper. The application of Sharkovsky's results is clever and well in place. My main criticism has to do with the structure, which I think overloads with general theory before getting to the main point the paper is making. I suggest stating Theorem 4.1 earlier, even as soon as Section 1.3, and use the discussion therein as an interpretation of the result. All the technical details, such as definition, Sharkovsky's Thm and proofs, can follows after than. The theoretical background is very interesting, but it would be better to start from the contribution to ML and get into the math later on. \n\nThe period dependent depth lower bound is nice but not very useful. Given a certain classification task, how could one assess/bound/approximate the period? This is general issue with this type of theory -- while it broadens our understanding it is hard to put it into actual use.\n\nAnother small comment: it would be useful to provide intuition for some of the definitions in the paper. For example Def. 3 lacks such.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HJgnwZWW5H", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nThis 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.\n\nQuestions/comments:\n\n1. 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.\n\n2. 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).", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The article is concerned with depth width tradeoffs in the representation of functions with neural networks. The article presents connections between expressivity of neural networks and dynamical systems, and obtains lower bounds on the width to represent periodic functions as a function of the depth. These are relevant advances and new perspectives for the theoretical study of neural networks. The reviewers were very positive about this article. The authors' responses also addressed comments from the initial reviews. 
Decision: Accept (Spotlight)