Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 8: Accept
review_content: 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).
review_title: Official Blind Review #1

final_score: rating: 8: Accept
review_content: 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.

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

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

Another small comment: it would be useful to provide intuition for some of the definitions in the paper. For example Def. 3 lacks such.
review_title: Official Blind Review #2

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)