2019

Complexity of Linear Regions in Deep Networks

Hanin, Boris, Rolnick, David

Understand

It is well-known that the expressivity of a neural network depends on its architecture, with deeper networks expressing more complex functions.

In the case of networks that compute piecewise linear functions, such as those with ReLU activation, the number of distinct linear regions is a natural measure of expressivity.
It is possible to construct networks with merely a single region, or for which the number of linear regions grows exponentially with depth; it is not clear where within this range most networks fall in practice, either before or after training.
In this paper, we provide a mathematical framework to count the number of linear regions of a piecewise linear network and measure the volume of the boundaries between these regions.

Do deep nets really need to be deep?
Ba, J. and Caruana, R · 2014
Earlier work this paper cites.
On the complexity of neural network classifiers: A comparison between shallow and deep architectures
Bianchini, M. and Scarselli, F · 2014
Earlier work this paper cites.
On the number of linear regions of deep neural networks
Montufar, G. F., Pascanu, R., Cho, K., and Bengio, Y · 2014
Earlier work this paper cites.
Representation benefits of deep feedforward networks
Original
Telgarsky, M · 2015
Earlier work this paper cites.
The power of depth for feedforward neural networks
Eldan, R. and Shamir, O · 2016
Earlier work this paper cites.
Learning functions: when is deep better than shallow
Original
Mhaskar, H., Liao, Q., and Poggio, T · 2016
Earlier work this paper cites.
Deep vs. shallow networks: An approximation theory perspective
Mhaskar, H. N. and Poggio, T · 2016
Earlier work this paper cites.
Exponential expressivity in deep neural networks through transient chaos
Poole, B., Lahiri, S., Raghu, M., Sohl-Dickstein, J., and Ganguli, S · 2016
Earlier work this paper cites.
Benefits of depth in neural networks
Telgarsky, M · 2016
Earlier work this paper cites.

A closer look at memorization in deep networks
Arpit, D., Jastrzębski, S., Ballas, N., Krueger, D., Bengio, E., Kanwal, M. S., Maharaj, T., Fischer, A., Courville, A., Bengio, Y., et al · 2017
Cited alongside, same era.
Why does deep and cheap learning work so well?
Lin, H. W., Tegmark, M., and Rolnick, D · 2017
Cited alongside, same era.
Exploring generalization in deep learning
Neyshabur, B., Bhojanapalli, S., McAllester, D., and Srebro, N · 2017
Cited alongside, same era.
Why and when can deep – but not shallow – networks avoid the curse of dimensionality: a review
Poggio, T., Mhaskar, H., Rosasco, L., Miranda, B., and Liao, Q · 2017
Cited alongside, same era.
On the expressive power of deep neural networks
Raghu, M., Poole, B., Kleinberg, J., Ganguli, S., and Dickstein, J. S · 2017
Cited alongside, same era.
Error bounds for approximations with deep ReLU networks
Yarotsky, D · 2017
Cited alongside, same era.
Understanding deep learning requires rethinking generalization
Zhang, C., Bengio, S., Hardt, M., Recht, B., and Vinyals, O · 2017
Cited alongside, same era.
Understanding deep neural networks with rectified linear units
Arora, R., Basu, A., Mianjy, P., and Mukherjee, A · 2018
Cited alongside, same era.
Which neural net architectures give rise to exploding and vanishing gradients?
Hanin, B · 2018
Cited alongside, same era.

Products of many large random matrices and gradients in deep neural networks
Original
Hanin, B. and Nica, M · 2018
Later among the works it cites.
How to start training: The effect of initialization and architecture
Hanin, B. and Rolnick, D · 2018
Later among the works it cites.
Sensitivity and generalization in neural networks: an empirical study
Novak, R., Bahri, Y., Abolafia, D. A., Pennington, J., and Sohl-Dickstein, J · 2018
Later among the works it cites.
Optimal approximation of piecewise smooth functions using deep ReLU neural networks
Petersen, P. and Voigtlaender, F · 2018
Later among the works it cites.
The power of deeper networks for expressing natural functions
Rolnick, D. and Tegmark, M · 2018
Later among the works it cites.
Bounding and counting linear regions of deep neural networks
Serra, T., Tjandraatmadja, C., and Ramalingam, S · 2018
Later among the works it cites.
Failures of gradient-based deep learning
Shalev-Shwartz, S., Shamir, O., and Shammah, S · 2018
Later among the works it cites.
Optimal approximation of continuous functions by very deep ReLU networks
Yarotsky, D · 2018
Later among the works it cites.

alphaXiv searches the wider corpus for related work and actual follow-ups.

alphaXiv is searching for related work…

Reading the bibliography…