证明了在标准假设下，学习单层神经网络是困难的。
On the Hardness of Learning One Hidden Layer Neural Networks
- 基于连续学习错误问题，构建了理论难解性证明
- 即使网络规模多项式、输入为高斯分布、噪声小，仍难学习
- 适用于关注神经网络安全性的研究人员
本文研究从ℝ^d中学习单层ReLU神经网络的问题。我们证明，在标准密码学假设下，该学习问题仍是困难的，即便满足：(1) 网络大小在d的多项式范围内，(2) 输入分布为标准高斯分布，(3) 噪声为高斯且在d上多项式小。该难解性结果基于连续学习带误差（CLWE）问题的难度，特别是基于近似求解最短向量问题在多项式因子范围内的最坏情况难解性，这一假设被广泛接受。
原文摘要 · Abstract (English)
In this work, we consider the problem of learning one hidden layer ReLU neural networks with inputs from $\mathbb{R}^d$. We show that this learning problem is hard under standard cryptographic assumptions even when: (1) the size of the neural network is polynomial in $d$, (2) its input distribution is a standard Gaussian, and (3) the noise is Gaussian and polynomially small in $d$. Our hardness result is based on the hardness of the Continuous Learning with Errors (CLWE) problem, and in particular, is based on the largely believed worst-case hardness of approximately solving the shortest vector problem up to a multiplicative polynomial factor.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。