Invited Open Problem: Is the Power of Deep Learning over Linear Models Inherently Distribution Dependent?

Abstract

We ask whether distribution-independent SQ learning implies low dimension complexity, and whether anything learnable with (S)GD on a (benign) neural network under any input distribution is also learnable with a linear model.