Learning Neural Networks with Two Nonlinear Layers in Polynomial Time

Understand

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.