固定奇偶函数难学，梯度法对单层ReLU网络无效
Hardness of Learning Fixed Parities with Neural Networks
- 用扰动梯度下降训练单层ReLU网络学习固定奇偶函数
- 无论参数如何初始化，都无法逼近目标函数
- 适合研究神经网络泛化极限的学者参考
学习奇偶函数是学习理论中的经典问题，虽计算上可解，但无法用标准梯度方法有效学习。以往的统计查询下界仅说明存在某些最坏情况的奇偶函数难以学习，却无法解释为何固定的奇偶函数（如所有坐标上的全奇偶）在实践中也难以通过标准预测器和梯度方法学习。本文解决这一开放问题，证明对于任意最小规模的固定奇偶函数，使用扰动梯度下降训练单层ReLU网络均无法得到有意义的结果。为此，我们建立了一个关于线性阈值函数傅里叶系数衰减的新定理，可能具有独立研究价值。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。