Hidden Progress in Deep Learning: SGD Learns Parities Near the Computational Limit
Hidden Progress in Deep Learning: SGD Learns Parities Near the Computational Limit
复制标题
DOI：
10.48550/arxiv.2207.08799
复制
发表时间：
2022-07
期刊：
影响因子：
--
通讯作者：
B. Barak;Benjamin L. Edelman;Surbhi Goel;S. Kakade;Eran Malach;Cyril Zhang
中科院分区：
文献类型：
--
作者：
B. Barak;Benjamin L. Edelman;Surbhi Goel;S. Kakade;Eran Malach;Cyril Zhang
越来越多的证据表明，随着我们扩大数据集、模型大小和训练时间，深度学习方法的能力会出现新的现象。虽然有一些关于这些资源如何调节统计能力的说明，但关于它们对模型训练的计算问题的影响却知之甚少。这项工作进行了这样的探索，通过透镜的学习$k$-稀疏奇偶校验的$n$位，一个典型的离散搜索问题，这是统计上容易，但计算上困难。从经验上讲，我们发现各种神经网络成功地学习稀疏奇偶校验，在训练曲线中具有不连续的相变。在小的实例中，学习突然发生在大约$n^{O（k）}$迭代;这几乎匹配SQ下限，尽管明显缺乏稀疏先验。我们的理论分析表明，这些观察结果不能用类似Langevin的机制来解释，即SGD“在黑暗中绊倒“，直到它找到隐藏的特征集（一种自然的算法，也在$n^{O（k）}$时间内运行）。相反，我们表明，SGD通过人口梯度中的傅立叶间隙逐渐放大稀疏解，使损失和错误度量不可见的持续进展。
There is mounting evidence of emergent phenomena in the capabilities of deep learning methods as we scale up datasets, model sizes, and training times. While there are some accounts of how these resources modulate statistical capacity, far less is known about their effect on the computational problem of model training. This work conducts such an exploration through the lens of learning a $k$-sparse parity of $n$ bits, a canonical discrete search problem which is statistically easy but computationally hard. Empirically, we find that a variety of neural networks successfully learn sparse parities, with discontinuous phase transitions in the training curves. On small instances, learning abruptly occurs at approximately $n^{O(k)}$ iterations; this nearly matches SQ lower bounds, despite the apparent lack of a sparse prior. Our theoretical analysis shows that these observations are not explained by a Langevin-like mechanism, whereby SGD"stumbles in the dark"until it finds the hidden set of features (a natural algorithm which also runs in $n^{O(k)}$ time). Instead, we show that SGD gradually amplifies the sparse solution via a Fourier gap in the population gradient, making continual progress that is invisible to loss and error metrics.