  We draw connections between simple neural networks and under-determined
linear systems to comprehensively explore several interesting theoretical
questions in the study of neural networks. First, we emphatically show that it
is unsurprising such networks can achieve zero training loss. More
specifically, we provide lower bounds on the width of a single hidden layer
neural network such that only training the last linear layer suffices to reach
zero training loss. Our lower bounds grow more slowly with data set size than
existing work that trains the hidden layer weights. Second, we show that
kernels typically associated with the ReLU activation function have fundamental
flaws -- there are simple data sets where it is impossible for widely studied
bias-free models to achieve zero training loss irrespective of how the
parameters are chosen or trained. Lastly, our analysis of gradient descent
clearly illustrates how spectral properties of certain matrices impact both the
early iteration and long-term training behavior. We propose new activation
functions that avoid the pitfalls of ReLU in that they admit zero training loss
solutions for any set of distinct data points and experimentally exhibit
favorable spectral properties.
