Learning Neural Networks with Two Nonlinear Layers in Polynomial Time

Abstract

We give a polynomial-time algorithm for learning neural networks with one layer of sigmoids feeding into any Lipschitz, monotone activation function (e.g., sigmoid or ReLU). We make no assumptions on the structure of the network, and the algorithm succeeds with respect to {\em any} distribution on the unit ball in $n$ dimensions (hidden weight vectors also have unit norm). This is the first assumption-free, provably efficient algorithm for learning neural networks with two nonlinear layers. Our algorithm-- {\em Alphatron}-- is a simple, iterative update rule that combines isotonic regression with kernel methods. It outputs a hypothesis that yields efficient oracle access to interpretable features. It also suggests a new approach to Boolean learning problems via real-valued conditional-mean functions, sidestepping traditional hardness results from computational learning theory. Along these lines, we subsume and improve many longstanding results for PAC learning Boolean functions to the more general, real-valued setting of {\em probabilistic concepts}, a model that (unlike PAC learning) requires non-i.i.d. noise-tolerance.

Changed title, included new results

References in corpus (3)

• Reliably Learning the ReLU in Polynomial Time
• Distribution-Specific Hardness of Learning Neural Networks
• Provable Methods for Training Neural Networks with Sparse Connectivity

Cited by in corpus (23)

• Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers
• Depth with Nonlinearity Creates No Bad Local Minima in ResNets
• Understanding the Loss Surface of Neural Networks for Binary Classification
• Elimination of All Bad Local Minima in Deep Learning
• Generalization Guarantees for Neural Networks via Harnessing the Low-rank Structure of the Jacobian
• On the Benefit of Width for Neural Networks: Disappearance of Bad Basins
• Reverse-Engineering Deep ReLU Networks
• Standardized Non-Intrusive Reduced Order Modeling Using Different Regression Models With Application to Complex Flow Problems
• Learning Two Layer Rectified Neural Networks in Polynomial Time
• How Many Samples are Needed to Estimate a Convolutional or Recurrent Neural Network?
• Hardness of Learning Neural Networks with Natural Weights
• Neural Networks and Polynomial Regression. Demystifying the Overparametrization Phenomena
• Training a Two Layer ReLU Network Analytically
• Improved Learning of One-hidden-layer Convolutional Neural Networks with Overlaps
• On the Learnability of Deep Random Networks
• Learning Polynomials of Few Relevant Dimensions
• A Deep Conditioning Treatment of Neural Networks
• Bandit Multiclass Linear Classification: Efficient Algorithms for the Separable Case
• Self-Regularity of Non-Negative Output Weights for Overparameterized Two-Layer Neural Networks
• From Local Pseudorandom Generators to Hardness of Learning
• Recovering the Lowest Layer of Deep Networks with High Threshold Activations
• Nested Barycentric Coordinate System as an Explicit Feature Map
• Learning Graph Neural Networks with Approximate Gradient Descent