Speaker: Sourav Chatterjee (Stanford)

Title: Neural networks can learn any low complexity pattern

Abstract:

Neural networks have taken over the world, but research on why they work so well is still in its infancy. I will present a baby step in this direction, based on joint work with my student Tim Sudijono. We show, with quantitative bounds, that a certain kind of neural network can quickly learn any pattern that can be expressed as a short program. An example is as follows. Let N be a large number, and suppose we have data consisting of a sample of X’s and Y’s, where each X is a randomly chosen number between 1 and N, and the corresponding Y is 1 if X is a prime and 0 if not. The sample size n is negligible compared to N. If we fit a neural network to this data which is “sparsest” in a suitable sense, it turns out that the network will be able to accurately predict if a newly chosen X is a prime or not, with a sample of size as small as (log N)^2 — even though the network does not know, a priori, that we are asking it to detect primality. The talk will be accessible to those with no background in neural networks; I will define all necessary concepts.

*Pre-reception held in 2-290 at 4pm.