Adding One Neuron Can Eliminate All Bad Local Minima
One of the main difficulties in analyzing neural networks is the non-convexity of the loss function which may have many bad local minima. In this paper, we study the landscape of neural networks for binary classification tasks. Under mild assumptions, we prove that after adding one special neuron with a skip connection to the output, or one special neuron per layer, every local minimum is a global minimum.
[Updates]  After reading the author's response, I think my concerns about the existence of minima has been partly, but not completely addressed. In the begging of the response a proof for the existence of a global minima is provided. However, an important distinction has been ignored. The author wrote that "By assumption 2, there exists θ* such that f(·; θ*) achieves zero training error". However, the existence a parameter for which all the data can be correctly classified (Assumption 2) is not the same as having a parameter for which the loss function is zero. That is precisely how the counterexample I provided works. Of course, the author could avoid this problem by modifying Assumption 2 to "there exists a parameter for which the loss function is zero", or by adding one assumption stating that $f$ can be rescaled as they did in the response, which I believe they should.   Another thing I'm very interested in is how difficult is to find a local minima of the modified network. If I understand correctly, after adding the neuron, each stationary point in the previous network becomes a corresponding saddle point (if one just keep the added neuron inactive) in the modified network (except for the global minima). How does such a loss landscape affect the optimization process? Is it computationally efficient to actually find the minima? How well does the minima generalize? It would be more convincing if the authors can provide some numerical experiments.  Overall I believe this is a very good paper, and should be accepted. I've changed my overall score to 7.   [Summary of the paper]  This paper presents a rather surprising theoretical result for the loss surface of binary classification models. It is shown that under mild assumptions, if one adds a specific type of neuron with skip connection to a binary classification model, as well as a quadratic regularization term to the loss function, then every local minima on the loss surface is also a global minima. The result is surprising because virtually no assumptions have been made about the classification model itself, other than that the dataset is realizable by the model (namely, there exists a parameter under which the model can classify all samples in the dataset correctly), hence the result is applicable to many models. The paper also provides some extensions to their main result.  [Quality]  I have concerns about the main result of the paper:  -- In section 3.2, the authors add the output of an exponential neuron to the output of the network, namely, the new architecture $\tilde{f}$ is defined by  $\tilde{f}(x, \theta) = f(x, \theta) + a \exp (w^T x + b)$  Note that the added term has an invariance in its parameters, namely, if one perform the following transformation:  $a^\prime = a / C, b^\prime = b + \log C$  then the model will stay exactly the same, i.e., $a^\prime \exp (w^T x + b^\prime) = a \exp (w^T x + b)$ holds for any input $x$.   Now, consider the loss function $\tilde{L}_n(\theta, a/C, w, b + \log C)$. Because there is also a regularization term for $a$, by the invariance argument above we can see that $\tilde{L}_n(\theta, a/C, w, b + \log C)$ decreases monotonically as $C$ increases (assuming $a \neq 0$). But as $C$ increases, $b$ is pushed to infinitely faraway. This argument naturally leads to the following concern: Theorem 1 is stated as "if there is a local minima for $\tilde{L}_n, then it is a global minima", but how does one ensure that $\tilde{L}_n$ actually has a local minima at all?   To further illustrate my point, consider the following very simple example I constructed. Suppose $f(x, \theta) = 1$, i.e., the model always output 1. Suppose we only have one sample in the dataset, $(x, y) = (0, 1)$. Note that the realizability assumption (Assumption 2) is satisfied. Let the loss function be $l(z) = \max(0, 2 + z)^3$, so that Assumption 1 is satisfied. Finally let $\lambda = 2$. Now, we have   $\tilde{L}_n = \max(0, 1 - a \exp(b))^3 + a^2$  One can immediately see that this function has no local minima. To see this, note that when $a = 0$, we have $\tilde{L}_n = 1$; on the other hand, let $a = t$ for some $t > 0$, and $b = - \log t$, and we have $L_n -> 0$ as $t -> 0$, but this would also make $b -> +\infty$. Hence the function has no global minima, and by Theorem 1 it cannot have any local minima.   While this observation does not mean Theorem 1 is wrong (because theorem 1 assumes the existence of a local minima), it does limit the scope of Theorem 1 in the case where local minimas do not exist.   [Clarity]  The paper is well written and well organized. The proof sketch is also easy to follow.   [Originality]  To the best of my knowledge, the results presented in the paper are original.   [Significance]  I really like the results presented in this paper. It is quite surprising that by making very simple modifications of the model, one can eliminate bad local minimas, especially given the fact that little assumptions on the model itself are needed. Despite so, I feel that the significance of the results might be slightly less than it appears:  -- As mentioned in the [Quality] part, there are cases where the loss function of the modified model has no local minima at all. In such cases, the theorems in the paper do not apply. It is not clear to me what conditions are needed to guarantee the existence of local minimas. It would be nice if the authors can address this issue.   -- The theorems in the paper do not actually make any assumptions on the model $f$ except that there exist parameters with which $f$ can correctly classify all samples in the dataset. While this makes the results very general, this unfortunately also implies that the paper is not really about loss surface of neural networks, but rather a general way to modify the loss surface that can be applied to any model so long as the realizability assumption is satisfied. The results seem to have nothing to do with neural networks, and hence it does not really add anything to our understanding of the loss surface of neural networks.  The assumptions made in the paper seem reasonable enough to be satisfied in realistic settings. It would be nice if the authors can present some numerical experiments.