Poly-time universality and limitations of deep learning

Emmanuel Abbe, Colin Sandon

The goal of this paper is to characterize function distributions that deep learning can or cannot learn in poly-time. A universality result is proved for SGD-based deep learning an…