SMALL NONLINEARITIES IN ACTIVATION FUNCTIONS CREATE BAD LOCAL MINIMA IN NEURAL NETWORKS
We investigate the loss surface of neural networks. We prove that even for onehidden-layer networks with "slightest" nonlinearity, the empirical risks have spurious local minima in most cases. Our results thus indicate that in general "no spurious local minima" is a property limited to deep linear networks, and insights obtained from linear networks may not be robust. Specifically, for ReLU(-like) networks we constructively prove that for almost all practical datasets there exist infinitely many local minima. We also present a counterexample for more general activations (sigmoid, tanh, arctan, ReLU, etc.), for which there exists a bad local minimum. Our results make the least restrictive assumptions relative to existing results on spurious local optima in neural networks. We complete our discussion by presenting a comprehensive characterization of global optimality for deep linear networks, which unifies other results on this topic.
The authors provide a clean and easily understood sufficient
condition for spurious local minima to exist in networks with
a hidden layer using ReLUs or leaky ReLUs.  This condition,
that there is not linear transformation with zero loss,
is satisfied for almost all inputs with more examples than
input variables.
The construction is elegant.  The mathematical writing in the paper,
especially describing the proof of Theorem 1, is very nice -- they
expose the main ideas effectively.
I do not know of another paper using a similar proof, but I have not
studied the proofs of the most closely related papers prior to doing
this review, so I have limited ability to vouch for this paper's
technical novelty.
The authors also show that networks using many other popular
activation functions have spurious local minima for a very
simple dataset.  All of these analysis are unified using a
simple, if technical, set of conditions on activation function.
Finally, the authors prove a somewhat technical theorem about
optima in deep linear networks, which generalizes some
earlier treatments of this topic, providing an checkable
condition for global minimality.
There is extensive discussion of related work.  I am not aware of
related work not covered by the authors.
In some cases, when the authors discuss previous work, they write as
if restriction to the realizable case is an assumption, when it seems
to me to be more of a constraint.  In other words, it seems harder to
prove the existence of spurious minima in the realizable case.
They seem to acknowledge this after their statement of their Theorem 2,
which also uses a realizable dataset.
Also, a few papers, including the Venturi, et al paper cited by
the authors, have analyzed whether spurious local minima exist
in subsets of the parameter space, including those likely to
be reached during training with different sorts of initializations.
In light of this work, the authors might want to tone down claims
about how their work shows that results about linear networks do
not generalize to the non-linear case.  In particular, to make
their construction work in the case of wide networks, they
need an overwhelming majority of the hidden units to be "dead",
which seems as it is unlikely to arise from training with
commonly used initializations.
Overall, I think that this paper makes an interesting and
non-obvious contribution on a hot topic.