Succinct Neural Networks

Channel:

Simons Institute for the Theory of Computing

Subscribers:

68,700

Published on February 17, 2023 6:23:22 AM ● Video Link: https://www.youtube.com/watch?v=ZAQkBTjK5AM

Duration: 45:05

671 views

2

Adam Kalai (Microsoft Research)
https://simons.berkeley.edu/talks/succinct-neural-networks
Lower Bounds, Learning, and Average-Case Complexity

Abstract
We present a Deep Neural Networks (DNN) architecture that is succinct: with a constant number of parameters, it is capable of representing any constant-sized Turing machine. In contrast, most prior DNNs are non-uniform in the sense that they require polynomial size to represent computations. One consequence is that our simple architecture can provably learn as well as any efficient learning algorithm, with simple random initializations. Our architecture combines recurrent and convolutional neural networks and builds on work of Abbe and Sandon [2020].