In plain words: A simple iterative routine that fits a monotone curve on top of a similarity-based predictor learns networks with two stacked nonlinear layers, with no assumptions about the data or network structure. It is the first method proven to run quickly on any data distribution.
Abstract · Learning Neural Networks with Two Nonlinear Layers in Polynomial Time
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.
Surbhi Goel, Adam Klivans
arXiv:1709.06010 · cs.DS, cs.LG, stat.ML · submitted Sep 18, 2017 · updated Apr 20, 2018
abstract · pdf · html · Changed title, included new results
In Supervised Machine Learning, our only goal is to predict the underlying "unknown" distribution given a set of data instances from the same. Let us say, I gave you set of images of cats and dogs to be classified. As a machine learning engineer, you would probably build me a Binary Classifier on top of an SVM and all done. But, how would you justify it to me that how well your algorithm generalizes? Or, in other words, how would you provide me a guarantee that your model will work "well" on images that you haven't seen yet. What would a model working "well" mean? If you recall SVM basics, one tries to build a max-margin hyperplane in some high-dimensional space. We will call the set of all such hyperplanes as our "concept class" and this is what you are trying to learn to be technical (hold that thought). When you finally give me your SVM model with some parameters, we will call it the target concept. Now, coming back to the point of "well"-ness of SVM, what guarantees can you provide me when I provide you images outside your training set but from the same underlying distribution (to be fair to you). We call the error you make during your training as the "empirical risk" and the error you make outside your training set on unseen data as the "risk". Our aim is to minimize "risk", or in words to "generalize" well.
In Learning Theory, we are concerned with defining the "well"-ness of a learning algorithm. More generally, we are interested in answering the question "what is learnable and how well?". The fundamental answer to that question is a theory known as the PAC (Probably Approximately Correct) Theory [1].
Paraphrasing in plain English (I'd recommend you to take a look at the formal definition affirmatively right after this), it states that learning is tractable if and only if we are able to provide a polynomial time algorithm such that for any possible set of samples from an unknown underlying distribution, we can provide an upper bound for the generalized error/risk with a confidence measure. This also has to happen so that we are able to provide a polynomial lower bound for the number of samples we use to run the algorithm.
Skipping a few other details, PAC theory is powerful because it provides a statistical framework to quantify the "wellness" in a probabilistic setting. On top of this, it makes absolutely no assumption about the underlying distribution and hence is "distribution-free". This means that whatever learning algorithm you provide, it should work on any distribution possible (with added technicality of the number of training samples needed being polynomial in terms of the error and confidence measure).
To get a more intuitive understanding, consider the prediction to the series of numbers "1,2,4,8,16,_". Your first guess most likely will be "32" because it seems like a GP with ratio 2. But I say that the next number is actually "12345". Am I wrong? No. Were you wrong? No. The take away is that true learning is intractable when the underlying distribution is truly "unknown" (like in this case). Instead, I will quantify the correctness and tell you that I am 99% confident that the the generalization error for unseen points of my predictions will be at most 10%. Note that those numbers are arbitrary to get a point across.
Now that we have PAC-theory in place, many times it is hard to use this tool because it is very strict, instead we rely on distribution-dependent bounds which might be more easily computable in some scenarios like the Rademacher complexity, Growth Function or VC Dimension.
Coming back to the paper, Neural Networks have been a hard nut to crack in terms of such theoretical bounds because sometimes these bounds tend to be trivial and useless (e,g, Probability <= 10). First the paper introduces lots of probabilistic tools on the basis of which it claims to have found an "efficient" (because polynomial time) PAC algorithm for learning intersections of polynomially many halfspaces.
[1] A Theory of the Learnable (http://web.mit.edu/6.435/www/Valiant84.pdf)