Provable limitations of deep learning

Abstract

As the success of deep learning reaches more grounds, one would like to also envision the potential limits of deep learning. This paper gives a first set of results proving that certain deep learning algorithms fail at learning certain efficiently learnable functions. The results put forward a notion of cross-predictability that characterizes when such failures take place. Parity functions provide an extreme example with a cross-predictability that decays exponentially, while a mere super-polynomial decay of the cross-predictability is shown to be sufficient to obtain failures. Examples in community detection and arithmetic learning are also discussed. Recall that it is known that the class of neural networks (NNs) with polynomial network size can express any function that can be implemented in polynomial time, and that their sample complexity scales polynomially with the network size. The challenge is with the optimization error (the ERM is NP-hard), and the success behind deep learning is to train deep NNs with descent algorithms. The failures shown in this paper apply to training poly-size NNs on function distributions of low cross-predictability with a descent algorithm that is either run with limited memory per sample or that is initialized and run with enough randomness. We further claim that such types of constraints are necessary to obtain failures, in that exact SGD with careful non-random initialization can be shown to learn parities. The cross-predictability in our results plays a similar role the statistical dimension in statistical query (SQ) algorithms, with distinctions explained in the paper. The proof techniques are based on exhibiting algorithmic constraints that imply a statistical indistinguishability between the algorithm's output on the test model v.s.\ a null model, using information measures to bound the total variation distance.

References in corpus (4)

• Understanding deep learning requires rethinking generalization
• Gradient Descent for One-Hidden-Layer Neural Networks: Polynomial Convergence and SQ Lower Bounds
• Time-Space Tradeoffs for Learning from Small Test Spaces: Learning Low Degree Polynomial Functions
• An Information-Percolation Bound for Spin Synchronization on General Graphs

Cited by in corpus (21)

• Adversarial Attacks on Deep Learning Models in Natural Language Processing: A Survey
• Deep Learning in Mining Biological Data
• Optimization and Generalization of Shallow Neural Networks with Quadratic Activation Functions
• Can Shallow Neural Networks Beat the Curse of Dimensionality? A mean field training perspective
• Hybrid Classical-Quantum Deep Learning Models for Autonomous Vehicle Traffic Image Classification Under Adversarial Attack
• Quantifying Point-Prediction Uncertainty in Neural Networks via Residual Estimation with an I/O Kernel
• Poly-time universality and limitations of deep learning
• Engineering Reliable Deep Learning Systems
• A multi-component framework for the analysis and design of explainable artificial intelligence
• Neural Anisotropy Directions
• Adversarial shape perturbations on 3D point clouds
• Robustifying deep networks for image segmentation
• When Hardness of Approximation Meets Hardness of Learning
• Efficient Deep Learning of GMMs
• Learning Boolean Circuits with Neural Networks
• Ten AI Stepping Stones for Cybersecurity
• VideoModerator: A Risk-aware Framework for Multimodal Video Moderation in E-Commerce
• An Evasion Attack against Stacked Capsule Autoencoder
• Marine life through You Only Look Once's perspective
• Fast-UAP: An Algorithm for Speeding up Universal Adversarial Perturbation Generation with Orientation of Perturbation Vectors
• Critical Temperature Prediction for a Superconductor: A Variational Bayesian Neural Network Approach