When Is Learning a Planted ReLU Network Tractable?

Learning neural networks from data is a fundamental problem, yet the tractability of even one-hidden-layer networks remains poorly understood. Worst-case hardness is known when the output-layer weights may have arbitrary signs, but a basic and surprisingly unresolved case remains: can one efficiently learn a sum of ReLU units with positive output weights, even under standard Gaussian covariates? We study recovery of the hidden weights in planted networks of the form $f_W(x)={\sum }_{\ell =1}^k\text{ReLU}(⟨w_{\ell },x⟩),x\sim \mathcal{N}(0,I_d).$ We first identify when the parameters are statistically determined, up to the natural permutation symmetry. In particular, Gaussian inputs allow the identification of the hidden weights under mild nondegeneracy conditions: no two weights are collinear, and no nonempty subset of the weights sums to zero. However, we show that identifiability alone is far from enough for efficient learning. Even under bounded norms, angular separation, and a strict positive subset-sum margin, any randomized polynomial-time algorithm that exactly recovers the parameters from membership queries at rational points would imply a randomized polynomial-time algorithm for an NP-hard vector subset-sum problem; hence no such algorithm exists unless $NP\subseteq RP$. This hardness result reveals the central obstruction: Gaussian even-order moments can recover the hidden hyperplanes, but orienting those hyperplanes can encode a hard discrete problem. On the positive side, we identify natural geometric conditions that make the orientation barrier tractable. Specifically, we show that a continuous analogue of the subset-sum margin, in the form of a positive-independence condition, enables, for any fixed angular-separation constant, exact recovery from polynomially many samples in polynomial time, given an exact solver for a polynomial-size linear program. Our method first combines implicit Gaussian Hermite moment estimation with random polynomial features and a low-dimensional matrix pencil to recover the network weights approximately up to sign. It then uses convex sign orientation based on the first moment to identify the correct signs, followed by anchored regression to refine the estimates to exact recovery.