Hardness of Learning Neural Networks with Natural Weights

Abstract

Neural networks are nowadays highly successful despite strong hardness results. The existing hardness results focus on the network architecture, and assume that the network's weights are arbitrary. A natural approach to settle the discrepancy is to assume that the network's weights are "well-behaved" and posses some generic properties that may allow efficient learning. This approach is supported by the intuition that the weights in real-world networks are not arbitrary, but exhibit some "random-like" properties with respect to some "natural" distributions. We prove negative results in this regard, and show that for depth-$2$ networks, and many "natural" weights distributions such as the normal and the uniform distribution, most networks are hard to learn. Namely, there is no efficient learning algorithm that is provably successful for most weights, and every input distribution. It implies that there is no generic property that holds with high probability in such random networks and allows efficient learning.

References in corpus (25)

• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• A Convergence Theory for Deep Learning via Over-Parameterization
• Gradient Descent Provably Optimizes Over-parameterized Neural Networks
• Convergence Analysis of Two-layer Neural Networks with ReLU Activation
• Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
• Provable Bounds for Learning Some Deep Representations
• Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivity
• Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks
• Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers
• Beating the Perils of Non-Convexity: Guaranteed Training of Neural Networks using Tensor Methods
• A Comparative Analysis of the Optimization and Generalization Property of Two-layer Neural Network and Random Feature Models Under Gradient Descent Dynamics
• Towards moderate overparameterization: global convergence guarantees for training shallow neural networks
• Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networks
• An Analytical Formula of Population Gradient for two-layered ReLU network and its Applications in Convergence and Critical Point Analysis
• Diverse Neural Network Learns True Target Functions
• Overparameterized Nonlinear Learning: Gradient Descent Takes the Shortest Path?
• Quadratic Suffices for Over-parametrization via Matrix Chernoff Bound
• An Improved Analysis of Training Over-parameterized Deep Neural Networks
• Learning One Convolutional Layer with Overlapping Patches
• SGD Learns Over-parameterized Networks that Provably Generalize on Linearly Separable Data
• Learning Neural Networks with Two Nonlinear Layers in Polynomial Time
• Neural Networks Learning and Memorization with (almost) no Over-Parameterization
• Mildly Overparametrized Neural Nets can Memorize Training Data Efficiently
• On the Learnability of Deep Random Networks
• A Deep Conditioning Treatment of Neural Networks

Cited by in corpus (5)

• Learning Deep ReLU Networks Is Fixed-Parameter Tractable
• On the average-case complexity of learning output distributions of quantum circuits
• From Local Pseudorandom Generators to Hardness of Learning
• MixCon: Adjusting the Separability of Data Representations for Harder Data Recovery
• Learning to Sample from Censored Markov Random Fields