Polynomial Learning of Positive ReLU Networks under Gaussian Inputs

We study bias-free, one-hidden-layer ReLU networks with nonnegative output weights under standard Gaussian inputs. Hidden directions may be arbitrarily close or linearly dependent. The labels have the target as their conditional mean, and only the unconditional second moment of the noise is bounded. We present a candidate real-arithmetic learning guarantee: a width-k target with total output weight at most one can be approximated to squared prediction error ε by a nonnegative ReLU network of width at most k + min{k, d}, with sample and operation cost (1 + σ²) poly(d, k, ε⁻¹, log(1/δ)). The argument combines implicit high-order moments with a direction cover that is complete for heavy atoms and sound for every output. Exact Gaussian soft localization refines this cover while pruning keeps at most k centers at every scale. Clipping the query multipliers controls heavy-tailed, input-dependent noise without assuming a uniform conditional variance bound. A final convex fit and an exact sparsification step give the stated output width. We also obtain a parameterized projective direction-recovery guarantee. The result concerns real-arithmetic complexity; no bit-complexity or practical running-time guarantee is asserted.