Superpolynomial Lower Bounds for Learning One-Layer Neural Networks using Gradient Descent
Superpolynomial Lower Bounds for Learning One-Layer Neural Networks using Gradient Descent
复制标题
DOI：
--
复制
发表时间：
2020-06
期刊：
影响因子：
--
通讯作者：
Surbhi Goel;Aravind Gollakota;Zhihan Jin;Sushrut Karmalkar;Adam R. Klivans
中科院分区：
文献类型：
--
作者：
Surbhi Goel;Aravind Gollakota;Zhihan Jin;Sushrut Karmalkar;Adam R. Klivans
我们使用梯度下降证明了关于高斯分布学习单层神经网络的第一个超多项式下界。我们表明，在访问由一层神经网络标记的样本的情况下，使用相对于平方损失的梯度下降进行训练的任何分类器都将无法在多项式时间内实现较小的测试误差。对于分类，我们给出了更强的结果，即任何统计查询（SQ）算法（包括梯度下降）都无法在多项式时间内实现较小的测试误差。之前的工作仅适用于小批量运行的梯度下降，需要尖锐的激活，并应用于特定类别的查询。我们的下界适用于广泛的激活类别，包括 ReLU 和 sigmoid。我们结果的核心依赖于一个简单的神经网络家族的新颖构造，该神经网络与所有球对称分布完全正交。
We prove the first superpolynomial lower bounds for learning one-layer neural networks with respect to the Gaussian distribution using gradient descent. We show that any classifier trained using gradient descent with respect to square-loss will fail to achieve small test error in polynomial time given access to samples labeled by a one-layer neural network. For classification, we give a stronger result, namely that any statistical query (SQ) algorithm (including gradient descent) will fail to achieve small test error in polynomial time. Prior work held only for gradient descent run with small batch sizes, required sharp activations, and applied to specific classes of queries. Our lower bounds hold for broad classes of activations including ReLU and sigmoid. The core of our result relies on a novel construction of a simple family of neural networks that are exactly orthogonal with respect to all spherically symmetric distributions.