Timezone: »

Poster
Better depth-width trade-offs for neural networks through the lens of dynamical systems
Evangelos Chatziafratis · Sai Ganesh Nagarajan · Ioannis Panageas

Thu Jul 16 07:00 AM -- 07:45 AM &amp; Thu Jul 16 08:00 PM -- 08:45 PM (PDT) @ Virtual #None
The expressivity of neural networks as a function of their depth, width and type of activation units has been an important question in deep learning theory. Recently, depth separation results for ReLU networks were obtained via a new connection with dynamical systems, using a generalized notion of fixed points of a continuous map $f$, called periodic points. In this work, we strengthen the connection with dynamical systems and we improve the existing width lower bounds along several aspects. Our first main result is period-specific width lower bounds that hold under the stronger notion of $L^1$-approximation error, instead of the weaker classification error. Our second contribution is that we provide sharper width lower bounds, still yielding meaningful exponential depth-width separations, in regimes where previous results wouldn't apply. A byproduct of our results is that there exists a universal constant characterizing the depth-width trade-offs, as long as $f$ has odd periods. Technically, our results follow by unveiling a tighter connection between the following three quantities of a given function: its period, its Lipschitz constant and the growth rate of the number of oscillations arising under compositions of the function $f$ with itself.

#### Author Information

##### Vaggos Chatziafratis (Stanford University)

I am a 3rd year PhD student at Stanford University working with Prof. Tim Roughgarden, Moses Charikar and Jan Vondrak. My research interests are in Algorithms and Learning Theory.

##### Ioannis Panageas (Singapore University of Technology and Design)

I am an Assistant Professor in Information Systems at SUTD. Before that I was a MIT Postdoctoral Fellow working with Costis Daskalakis. I obtained my PhD in Algorithms, Combinatorics, and Optimization (ACO) at Georgia Tech, advised by Prasad Tetali. At Georgia Tech, I also obtained a MSc in Mathematics. I did my undergrad studies in National Technical University of Athens. I am interested in theory of computation and its interface with optimization, dynamical systems, probability and statistics, machine learning and their applications to game theory.