Proper Learning of Signed Narrow ReLU Networks

Cancellation among signed neurons complicates uniform learning guarantees for narrow ReLU networks. We address this challenge with a proper learner for normalized, bias-free networks under Gaussian inputs, without separation assumptions. Specifically, for width $k$ and squared $L_2$ error $ϵ$, it uses $g(k){ϵ}^{-O(k^2)}\tilde{O}(d)$ noiseless examples and $g(k){ϵ}^{-O(k^2)}\tilde{O}(d^2)$ real-arithmetic operations. Thus, at any fixed width, sample complexity is nearly linear in dimension and running time is nearly quadratic, while both are polynomial in inverse accuracy. To prove this, we combine first-moment control with a scaled nonlinear label-distance statistic to lower-bound a second-moment signal using residual variance. A norm-preserving rotation then ensures approximation by at most $k$ units in the original normalized class, yielding proper output.