Vegard Antun: Implicit regularization in AI meets generalized hardness of approximation

Why is deep learning so successful in many applications of modern AI? This question has puzzled the AI community for more than a decade, and many attribute the success of deep learning to the implicit regularization imposed by the Neural Network (NN) architectures and the gradient descent algorithm. In this talk we will investigate the implicit regularization of so-called linear NNs in the simplified setting of linear regression. Furthermore, we will show how this theory meets fundamental computational boundaries imposed by the phenomenon of generalized hardness of approximation. That is, the phenomenon where certain optimal NNs can be proven to exist, but any algorithm will fail to compute these NNs to an accuracy below a certain approximation threshold. Thus, paradoxically, there will exist deep learning methods that are provably optimal, but that can only be computed to a certain accuracy.

Vegard Antun is a postdoctoral fellow at the University of Oslo, department of Mathematics.