Eigenvalue Decay Implies Polynomial-Time Learnability for Neural Networks

Abstract

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.

References in corpus (9)

• Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivity
• No bad local minima: Data independent training error guarantees for multilayer neural networks
• Beating the Perils of Non-Convexity: Guaranteed Training of Neural Networks using Tensor Methods
• Recursive Sampling for the Nyström Method
• Diving into the shallows: a computational perspective on large-scale shallow learning
• On the Complexity of Learning Neural Networks
• Distribution-Specific Hardness of Learning Neural Networks
• Learning Halfspaces and Neural Networks with Random Initialization
• Provable Methods for Training Neural Networks with Sparse Connectivity