On the Complexity of Learning Neural Networks
On the Complexity of Learning Neural Networks
复制标题
DOI：
--
复制
发表时间：
2017-07
期刊：
影响因子：
--
通讯作者：
Le Song;S. Vempala;John Wilmes;Bo Xie
中科院分区：
文献类型：
--
作者：
Le Song;S. Vempala;John Wilmes;Bo Xie
神经网络的惊人经验成功目前缺乏严格的理论解释。面对现有的复杂性理论下限，这种解释会采取什么形式？第一步可能是证明由具有单个隐藏层、平滑激活函数和良性输入分布的神经网络生成的数据可以有效地学习。我们在这里证明了一个全面的下限排除这种可能性：对于广泛的一类激活函数（包括所有当前使用的），以及从任何对数凹分布中提取的输入，存在一族单隐藏层函数，其输出是一个和门，很难在精确意义上学习：任何统计查询算法（包括随机梯度下降的所有已知变体，具有任何损失函数）即使使用与输入维度成反比的容差，也需要指数数量的查询。此外，这个硬家庭的功能是可实现的一个小的（次线性维度）数量的激活单元在单个隐藏层。该下界对真实权重的小扰动也是鲁棒的。系统的实验说明了相变的训练误差的分析预测。
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.