Learning Deep ReLU Networks Is Fixed-Parameter Tractable

Understand

We consider the problem of learning an unknown ReLU network with respect to Gaussian inputs and obtain the first nontrivial results for networks of depth more than two.

• We give an algorithm whose running time is a fixed polynomial in the ambient dimension and some (exponentially large) function of only the network's parameters.
• Our bounds depend on the number of hidden units, depth, spectral norm of the weight matrices, and Lipschitz constant of the overall network (we show that some dependence on the Lipschitz constant is necessary).
• We also give a bound that is doubly exponential in the size of the network but is independent of spectral norm.