כתבה
arXiv cs.LG ·
NP-קשיות של הקטנת נוירונים ברשתות רלו
NP-Hardness of Minimizing Neurons in Two-Hidden-Layer ReLU Neural Networks
הוכח כי החישוב של כמות הנוירונים המינימלית ברשתות ReLU הוא NP-קשה. זה נובע מכך שהקטנת נוירונים ברשתות ReLU היא NP-קשה. התוצאה חשובה עבור רשתות רלו ומסבירה את חשיבות של שימוש בשיטות הערכה ניסיוניות בעיצוב רשתות ReLU.
תקציר מקורי באנגליתarXiv:2610.11313v1 Announce Type: new 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 wh
קרא במקור המקורי
arxiv.org
פתח כתבה מקורית