On the Complexity of Learning Neural Networks

By Le Song, Santosh Srinivas Vempala, John Wilmes, Bo Xie. 2017

63 citations recorded by the source corpus.

The stunning empirical successes of neural networks currently lack rigorous theoretical explanation. What form would such an explanation take, in the face of existing complexity-theoretic lower bounds? A first step might be to show that data generated by neural networks with a single hidden layer, smooth activation functions and benign input distributions can be learned efficiently. We demonstrate here a comprehensive lower bound ruling out this possibility: for a wide class of activation functions (including all currently used), and inputs drawn from any logconcave distribution, there is a family of one-hidden-layer functions whose output is a sum gate, that are hard to learn in a precise sense: any statistical query algorithm (which includes all known variants of stochastic gradient descent with any loss function) needs an exponential number of queries even using tolerance inversely proportional to the input dimensionality. Moreover, this hard family of functions is realizable with a small (sublinear in dimension) number of activation units in the single hidden layer. The lower bound is also robust to small perturbations of the true weights. Systematic experiments illustrate a phase transition in the training error as predicted by the analysis.

Subfields: Artificial Intelligence, Statistical Learning Theory, Algorithms & Complexity

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistical Learning Theory

In Algorithms & Complexity

Citations in the corpus

A Convergence Theory for Deep Learning via Over-Parameterization (2018, background): “Stronger hardness results have been proved over the last decade (Daniely, 2016; Daniely & Shalev-Shwartz, 2016; Goel et al., 2017; Klivans & Sherstov, 2009; Livni et al., 2014; Manurangsi & Reichman, 2018; Song et al., 2017).”
Neural-net-induced Gaussian process regression for function approximation and PDE solution (2018, background): “For NN, the accurate estimate of time complexity for training is still an open question [21].”
Adversarial examples from computational constraints (2018, background): “, 2017), or learning a function computable by a small neural network (Song et al., 2017).”
Polynomial Convergence of Gradient Descent for Training One-Hidden-Layer Neural Networks (2018, background): “More recent lower bounds hold even for specific distributions and smooth functions, for basic gradient descent [23], and even realizable smooth functions for any SQ algorithm and any product logconcave input distribution [24].”
Gradient Descent for One-Hidden-Layer Neural Networks: Polynomial Convergence and SQ Lower Bounds (2018, methodology): “The approach taken in [30], are revisited here, is to require the query function h : X × R → [0, 1] to be Lipschitz for every fixed x ∈ X .”
Learning Neural Networks with Two Nonlinear Layers in Polynomial Time (2017, methodology): “For completeness, we define the two models and refer the reader to Valiant (1984); Kearns and Schapire (1990) for a detailed explanation.”