Neural Networks Generalize on Low Complexity Data

Sourav Chatterjee, Timothy Sudijono

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, t…