Learning Narrow One-Hidden-Layer ReLU Networks
This solves a fundamental problem in neural network theory for researchers, enabling efficient learning of ReLU networks without restrictive conditions, though it is incremental in improving over prior methods.
The paper tackles the problem of learning a one-hidden-layer ReLU network with constant k neurons under Gaussian inputs, presenting the first polynomial-time algorithm that succeeds without additional assumptions like positive coefficients or well-conditioned weights. The result overcomes prior limitations by using random contractions of higher-order moment tensors and a multi-scale analysis to collapse close neurons.
We consider the well-studied problem of learning a linear combination of $k$ ReLU activations with respect to a Gaussian distribution on inputs in $d$ dimensions. We give the first polynomial-time algorithm that succeeds whenever $k$ is a constant. All prior polynomial-time learners require additional assumptions on the network, such as positive combining coefficients or the matrix of hidden weight vectors being well-conditioned. Our approach is based on analyzing random contractions of higher-order moment tensors. We use a multi-scale analysis to argue that sufficiently close neurons can be collapsed together, sidestepping the conditioning issues present in prior work. This allows us to design an iterative procedure to discover individual neurons.