初始权重分布决定神经网络能否高效学习高阶奇偶函数。
Learning High-Degree Parities: The Crucial Role of the Initialization
- 使用Rademacher初始化可高效学习接近全维的奇偶函数
- 当初始权重方差超过O(d⁻¹)时，学习能力完全失效
- 结果对理解神经网络训练初期的梯度对齐机制有启示
奇偶函数已成为评估学习算法的标准基准。近期研究显示，常规神经网络通过梯度下降可在常数阶奇偶性下高效学习均匀输入上的度k奇偶函数，但当k与d−k随维度d增长时则失败。然而，当k=d−O_d(1)（几乎全维奇偶）时，包括度d奇偶（全奇偶）的情况仍悬而未决。本文表明，对于常规神经网络的梯度下降，学习能力取决于初始权重分布：离散Rademacher初始化可实现几乎全维奇偶的高效学习，而其高斯扰动（标准差σ足够大）则会阻止学习。正向结果在σ=O(d⁻¹)范围内成立，暗示可能存在更尖锐的阈值现象。不同于统计查询（SQ）学习中单个函数类如全奇偶可轻易学习，本文负向结果针对固定函数，依赖于初始梯度对齐度量，该度量可能具有更广泛的神经网络学习意义。
原文摘要 · Abstract (English)
Parities have become a standard benchmark for evaluating learning algorithms. Recent works show that regular neural networks trained by gradient descent can efficiently learn degree $k$ parities on uniform inputs for constant $k$, but fail to do so when $k$ and $d-k$ grow with $d$ (here $d$ is the ambient dimension). However, the case where $k=d-O_d(1)$ (almost-full parities), including the degree $d$ parity (the full parity), has remained unsettled. This paper shows that for gradient descent on regular neural networks, learnability depends on the initial weight distribution. On one hand, the discrete Rademacher initialization enables efficient learning of almost-full parities, while on the other hand, its Gaussian perturbation with large enough constant standard deviation $σ$ prevents it. The positive result for almost-full parities is shown to hold up to $σ=O(d^{-1})$, pointing to questions about a sharper threshold phenomenon. Unlike statistical query (SQ) learning, where a singleton function class like the full parity is trivially learnable, our negative result applies to a fixed function and relies on an initial gradient alignment measure of potential broader relevance to neural networks learning.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。