Distribution-Specific Hardness of Learning Neural Networks

Abstract

Although neural networks are routinely and successfully trained in practice using simple gradient-based methods, most existing theoretical results are negative, showing that learning such networks is difficult, in a worst-case sense over all data distributions. In this paper, we take a more nuanced view, and consider whether specific assumptions on the "niceness" of the input distribution, or "niceness" of the target function (e.g. in terms of smoothness, non-degeneracy, incoherence, random choice of parameters etc.), are sufficient to guarantee learnability using gradient-based methods. We provide evidence that neither class of assumptions alone is sufficient: On the one hand, for any member of a class of "nice" target functions, there are difficult input distributions. On the other hand, we identify a family of simple target functions, which are difficult to learn even if the input distribution is "nice". To prove our results, we develop some tools which may be of independent interest, such as extending Fourier-based hardness techniques developed in the context of statistical queries \cite{blum1994weakly}, from the Boolean cube to Euclidean space and to more general classes of functions.

arXiv commentSimpler and more explicit theorems in section 4

References in corpus (3)

• No bad local minima: Data independent training error guarantees for multilayer neural networks
• Beyond Convexity: Stochastic Quasi-Convex Optimization
• Learning Halfspaces and Neural Networks with Random Initialization

Cited by in corpus (10)

• Recovery Guarantees for One-hidden-layer Neural Networks
• Understanding Deep Neural Networks with Rectified Linear Units
• Depth Creates No Bad Local Minima
• Failures of Gradient-Based Deep Learning
• Learning Neural Networks with Two Nonlinear Layers in Polynomial Time
• On the Connection Between Learning Two-Layers Neural Networks and Tensor Decomposition
• Weight Sharing is Crucial to Succesful Optimization
• Eigenvalue Decay Implies Polynomial-Time Learnability for Neural Networks
• Convergence of a Relaxed Variable Splitting Method for Learning Sparse Neural Networks via ${\ell }_1,{\ell }_0$, and transformed-${\ell }_1$ Penalties
• Deep Semi-Random Features for Nonlinear Function Approximation