标题： 神经网络学习固定奇偶性的问题难度 显示英文标题

标题： Hardness of Learning Fixed Parities with Neural Networks

摘要： 学习奇偶函数是学习理论中的一个经典问题，尽管在计算上是可行的，但不适用于梯度相关的标准学习算法。 这种难度通常通过统计查询下界来解释[Kearns, 1998]。 然而，这些界限只意味着对于任何给定的算法，存在某些最坏情况下的奇偶函数难以学习。 因此，它们无法解释为什么固定的奇偶函数——例如所有坐标上的完整奇偶函数——在实践中，至少使用标准预测器和梯度下降方法时，难以学习[Abbe and Boix-Adsera, 2022]。 在本文中，我们通过证明对于任何固定大小的最小奇偶函数，将其作为目标函数来训练带有扰动梯度下降的一层隐藏层ReLU网络将无法产生任何有意义的结果，从而解决了这个开放问题。 为了建立这一点，我们证明了一个关于线性阈值（或加权多数）函数的傅里叶系数衰减的新结果，这可能具有独立的兴趣。 显示英文摘要

摘要： Learning parity functions is a canonical problem in learning theory, which although computationally tractable, is not amenable to standard learning algorithms such as gradient-based methods. This hardness is usually explained via statistical query lower bounds [Kearns, 1998]. However, these bounds only imply that for any given algorithm, there is some worst-case parity function that will be hard to learn. Thus, they do not explain why fixed parities - say, the full parity function over all coordinates - are difficult to learn in practice, at least with standard predictors and gradient-based methods [Abbe and Boix-Adsera, 2022]. In this paper, we address this open problem, by showing that for any fixed parity of some minimal size, using it as a target function to train one-hidden-layer ReLU networks with perturbed gradient descent will fail to produce anything meaningful. To establish this, we prove a new result about the decay of the Fourier coefficients of linear threshold (or weighted majority) functions, which may be of independent interest.