arXiv：cs.LG· Sangrock Lee·· 3 小时前
双层 ReLU 神经网络最小神经元数的 NP 难性
NP-Hardness of Minimizing Neurons in Two-Hidden-Layer ReLU Neural Networks
AI 导读
论文证明，在 L^p(R^d,R^m) 逼近约束下，对任意固定 d≥1、m≥1 和 1≤p<∞，精确计算两层隐藏层 ReLU 网络逼近目标函数所需的最少隐藏神经元数是 NP-hard。
正文
Abstract:A fundamental question in neural network architecture optimization is whether the minimum hidden-neuron count required to approximate a target function within a prescribed tolerance can be computed efficiently. This paper resolves this question for two-hidden-layer ReLU networks under an $L^p(\mathbb{R}^d,\mathbb{R}^m)$ approximation constraint. For every fixed $d \ge 1$, $m \ge 1$, and $1 \le p < \infty$, we prove that computing the optimum exactly is NP-hard. The result holds even when the target is represented by a rational ReLU network whose realization is nonzero, componentwise nonnegative, compactly supported, globally Lipschitz, and continuous piecewise affine. The polynomial-time reduction from 3-SAT produces an architecture gap in which unsatisfiable formulas yield an optimum of zero, whereas satisfiable formulas yield an optimum of at least $d+2$. The proof constructs compactly supported polyhedral frustum functions realized by two-hidden-layer ReLU networks and establishes the $L^p$-density of finite linear combinations of box-frustum functions. The results offer theoretical justification for employing heuristic approximation methods in the design of ReLU neural networks, illustrating that attaining a minimal configuration within polynomial time is computationally unachievable.
| Subjects: | Machine Learning (cs.LG) |
| Cite as: | arXiv:2610.11313 [cs.LG] |
| (or arXiv:2610.11313v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2610.11313 arXiv-issued DOI via DataCite (pending registration) |
|
| Journal reference: | Lee, S., NP-Hardness of Minimizing Neurons in Two-Hidden-Layer ReLU Neural Networks, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 48, no. 11, 2026 |
| Related DOI: | https://doi.org/10.1109/TPAMI.2026.3711513
DOI(s) linking to related resources |
Submission history
From: Sangrock Lee [view email]
[v1]
Thu, 8 Oct 2026 06:19:10 UTC (87 KB)
来源：arXiv：cs.LG · arxiv.org