用稀疏输入和乘积结构网络，让梯度下降高效学高维异或函数。
Learning High-Dimensional Parity Functions with Product Networks using Gradient Descent
- 用乘积型网络加随机稀疏输入，突破传统神经网络的指数样本瓶颈。
- 在 N=10 万维度下仍能收敛，样本复杂度呈多项式增长。
- 适合研究神经算术、二值网络和自动化协议发现的读者。
异或函数是机器学习、密码学和纠错中的基础布尔运算。然而，在一般情况下，标准神经网络需指数级样本才能学习高维异或函数，使基于梯度的优化对大量输入不可行。本文证明，结合乘积型神经架构、随机稀疏输入（伯努利分布，概率 p_e ≤ 1/N）及合适超参数，可实现高效异或学习，并具备理论收敛保证。实验验证了理论在高达 N = 100,000 维下的有效性，实证表明最优 p_e 与学习率 α 的选择，以及多项式复杂度规律。该工作揭示了模型结构归纳偏置与数据稀疏性的深层关联，为神经算术、结构化推理、二值神经网络及自动化协议发现开辟新路径。
原文摘要 · Abstract (English)
Parity functions are fundamental Boolean operations with critical applications across machine learning, cryptography, and error correction. Yet, learning high-dimensional parity functions poses significant challenges: in a general setting, standard neural network architectures typically require exponential sample complexity, making gradient-based optimization intractable for large number of inputs $N$. We demonstrate that compact product-based neural architectures combined with stochastic data sparsity (Bernoulli inputs with $p_e \leq 1/N$) and appropriate hyperparameter choice enable efficient parity learning, with theoretical guarantees of convergence. Experiments validate our theory across dimensions up to $N = 100{,}000$, with empirical evidence showing optimal hyperparameter choices for $p_e$ and learning rate $α$, as well as polynomial complexity scaling laws. This work establishes fundamental connections between architectural inductive bias and data sparsity, opening new possibilities for neural arithmetic, structured reasoning, binary neural networks, and machine learning applied to automated protocol discovery.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。