  We study the loss surface of a feed-forward neural network with ReLU
non-linearities, regularized with weight decay. We show that the regularized
loss function is piecewise strongly convex on an important open set which
contains, under some conditions, all of its global minimizers. This is used to
prove that local minima of the regularized loss function in this set are
isolated, and that every differentiable critical point in this set is a local
minimum, partially addressing an open problem given at the Conference on
Learning Theory (COLT) 2015; our result is also applied to linear neural
networks to show that with weight decay regularization, there are no non-zero
critical points in a norm ball obtaining training error below a given
threshold. We also include an experimental section where we validate our
theoretical work and show that the regularized loss function is almost always
piecewise strongly convex when restricted to stochastic gradient descent
trajectories for three standard image classification problems.
