When Hardness of Approximation Meets Hardness of Learning
arXiv:2008.08059
Abstract
A supervised learning algorithm has access to a distribution of labeled examples, and needs to return a function (hypothesis) that correctly labels the examples. The hypothesis of the learner is taken from some fixed class of functions (e.g., linear classifiers, neural networks etc.). A failure of the learning algorithm can occur due to two possible reasons: wrong choice of hypothesis class (hardness of approximation), or failure to find the best function within the hypothesis class (hardness of learning). Although both approximation and learnability are important for the success of the algorithm, they are typically studied separately. In this work, we show a single hardness property that implies both hardness of approximation using linear classes and shallow networks, and hardness of learning using correlation queries and gradient-descent. This allows us to obtain new results on hardness of approximation and learnability of parity functions, DNF formulas and circuits.
References in corpus (10)
- On the Number of Linear Regions of Deep Neural Networks
- Spurious Local Minima are Common in Two-Layer ReLU Neural Networks
- Representation Benefits of Deep Feedforward Networks
- On the number of response regions of deep feed forward networks with piece-wise linear activations
- Benefits of depth in neural networks
- Failures of Gradient-Based Deep Learning
- Provable limitations of deep learning
- Learning Parities with Neural Networks
- Approximate is Good Enough: Probabilistic Variants of Dimensional and Margin Complexity
- Neural Networks with Small Weights and Depth-Separation Barriers