Paper recorded by Signals 4 on 2026-10-23 in cs.LG. Abstract reproduced from arXiv; link to the original below.
Published 2026-10-23 on arXiv · recorded by Signals 4 on 2026-10-26
Category: cs.LG · 机器学习 · first seen 2026-10-26
We study the fundamental problem of PAC learning positive linear combinations of $k$ arbitrary ReLU activations on $\mathbb{R}^d$ with respect to the Gaussian distribution, in $L_2$ loss. We give the first fully-polynomial time algorithm for this learning task. Specifically, our algorithm draws $\mathrm{poly}(d, k, 1/ε)$ samples, runs in $\mathrm{poly}(d, k, 1/ε)$ time, and outputs a hypothesis th