Learning Neural Networks with Two Nonlinear Layers in Polynomial Time
This provides a foundational advancement for machine learning theory by enabling efficient learning of complex neural networks, addressing a long-standing open problem with broad implications for algorithm design and computational learning.
The paper tackles the problem of learning neural networks with two nonlinear layers without structural assumptions, presenting the first provably efficient algorithm, Alphatron, that works for any distribution on the unit ball. It achieves polynomial-time learning with respect to any distribution, subsuming and improving many longstanding results in PAC learning by extending to probabilistic concepts with non-i.i.d. noise-tolerance.
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.