A Combinatorial Perspective on the Optimization of Shallow ReLU Networks

Michael Matena, Colin Raffel

The NP-hard problem of optimizing a shallow ReLU network can be characterized as a combinatorial search over each training example's activation pattern followed by a constrained co…