Eigenvalue Decay Implies Polynomial-Time Learnability for Neural Networks
This addresses the challenge of efficient learnability for neural networks, a foundational issue in machine learning, by introducing a practical distributional assumption observed in real data, though it is incremental as it builds on prior work but offers new theoretical guarantees.
The paper tackles the problem of learning neural networks, which is computationally intractable in worst-case scenarios, by showing that a distributional assumption of eigenvalue decay in the Gram matrix enables polynomial-time algorithms for expressive classes like ReLU networks in the non-realizable setting, with fully-polynomial time algorithms under strong decay and improved algorithms under milder decay.
We consider the problem of learning function classes computed by neural networks with various activations (e.g. ReLU or Sigmoid), a task believed to be computationally intractable in the worst-case. A major open problem is to understand the minimal assumptions under which these classes admit provably efficient algorithms. In this work we show that a natural distributional assumption corresponding to {\em eigenvalue decay} of the Gram matrix yields polynomial-time algorithms in the non-realizable setting for expressive classes of networks (e.g. feed-forward networks of ReLUs). We make no assumptions on the structure of the network or the labels. Given sufficiently-strong polynomial eigenvalue decay, we obtain {\em fully}-polynomial time algorithms in {\em all} the relevant parameters with respect to square-loss. Milder decay assumptions also lead to improved algorithms. This is the first purely distributional assumption that leads to polynomial-time algorithms for networks of ReLUs, even with one hidden layer. Further, unlike prior distributional assumptions (e.g., the marginal distribution is Gaussian), eigenvalue decay has been observed in practice on common data sets.