The Connection Between Approximation, Depth Separation and Learnability in Neural Networks

Eran Malach, Gilad Yehudai, Shai Shalev-Shwartz +1

Several recent works have shown separation results between deep neural networks, and hypothesis classes with inferior approximation capacity such as shallow networks or kernel clas…