Fully Polynomial Learning of Positive ReLU Sums

We give a fully polynomial algorithm for learning positive sums of bias-free ReLUs under Gaussian inputs. From labeled examples of a sum with $k$ hidden units in ${\mathbb{R}}^d$, the algorithm returns, with probability at least $1-\delta$, an efficiently evaluable polynomial of degree $O({ϵ}^{-4/3})$ with relative $L_2$ error at most $ϵ$. It uses $\mathrm{poly}(d,k,1/ϵ,\log (1/\delta ))$ labeled samples and arithmetic operations, with the same bound on memory, output size, and evaluation time. The guarantee holds for arbitrary nonnegative weights and ridge vectors, including coincident and antipodal directions. The central step estimates a small, label-observable covariance at each degree. Aligning its factor with the hidden ridge tensors gives a low-rank comparator for tensor-train rounding; balanced degree splits then prevent the rounding loss from accumulating exponentially.