Neural networks generalize on low complexity data

We show that feedforward neural networks with ReLU activation generalize on low complexity data, suitably defined. Given i.i.d. data generated from a simple programming language, the minimum description length (MDL) feedforward neural network which interpolates the data generalizes with high probability. We define this simple programming language, along with a notion of description length of such networks. We provide several examples on basic computational tasks, such as checking primality of a natural number. For primality testing, our theorem shows the following and more. Suppose that we draw an i.i.d. sample of n numbers uniformly at random from 1 to N. For each number xi, let yi=1 if xi is a prime and 0 if it is not. Then the interpolating MDL network accurately answers, with probability 1−O((lnN)/n), whether a newly drawn number between 1 and N is a prime or not. Note that the network is not designed to detect primes; minimum description learning discovers a network which does so. Extensions to noisy data are also discussed, suggesting that MDL neural network interpolators can demonstrate tempered overfitting.