Globally Optimal Training of Generalized Polynomial Neural Networks with Nonlinear Spectral Methods
The optimization problem behind neural networks is highly non-convex. Training with stochastic gradient descent and variants requires careful parameter tuning and provides no guarantee to achieve the global optimum. In contrast we show under quite weak assumptions on the data that a particular class of feedforward neural networks can be trained globally optimal with a linear convergence rate with our nonlinear spectral method. Up to our knowledge this is the first practically feasible method which achieves such a guarantee. While the method can in principle be applied to deep networks, we restrict ourselves for simplicity in this paper to one and two hidden layer networks. Our experiments confirm that these models are rich enough to achieve good performance on a series of real-world datasets.
This paper presents a nice theory that demonstrates that a certain class of neural network has a global optimal which can be achieved in a linear convergence rate. The main constrain is that all the input data and the weights of the linear layer are positive and activation functions are generalized polynomial. The proposed theory is first proved on the neural network with a single hidden layer and later extend to the networks with multiple hidden layers. The authors also proposed an optimization algorithm based on nonlinear spectral method. Experiments show that the proposed algorithm works quite well on a small 2D synthetic dataset, and it also achieves a reasonable performance on some small real-world datasets (UCI datasets).
Pros: As claimed by the authors, this is the first work that proposed a potentially practical neural work with optimal guarantee and convergence guarantee. Previous work that have convergence guarantees requires a complicated method to check its preconditions, some of them even impossible to check in practice, as they depend on the data-generating measure. The theory proposed in this work has comparatively simple preconditions that only depends on the spectral radius of a nonnegative matrix consists of the parameters of the network. The authors also demonstrate that the proposed theory can be applied to network of arbitrary depth and show a reasonable result on small real dataset.  Cons: The proposed network still has limited applications. The theory requires both the input data and network parameters be positive, activation functions be generalized polynomials, and spectral radius (Theorem 1) be smaller than 1. I think the non-negative constrains on the input data should not block too much potential usage, as most of train data can be easily shift to be all positive. However, the fact that network parameters are positive might limit the expressiveness of the model. Also, the fact that all activation functions of all hidden layers are different is unnatural and it might also limit its application. At last, the authors said that in order to satisfy the spectral radius constrains, they need to increase p1 and p2 and decrease pw and pu, which effectively decreases the weights of linear units. And if I understand correctly, in order to satisfy the spectral radius constrains, the higher dimension of the input and network parameters, the lower the weights of linear units. Since when the linear weight is very small, the activation functions will almost act the same as a linear function. In that case, adding more layers is just adding another linear function, which won't increase the expressiveness of the network. Thus, I am little worried that this method might not easy to extend it to deep architectures. Despite all these concerns, this is still an encouraging result as an initial attempt and I think this paper should be accepted.  Minor comments:  I am curious the how p1, p2, pw, pu, the dimension of the input and the size of the network parameters affects the spectral radius rho(A). For example, when the dimension of input increases, does rho(A) increases linearly or exponentially, and in order to counter effect that, should we linearly or exponentially decreases pw and pu. I know it might not be easy to prove that, but it might be possible to empirically plot that relationship on a synthetic data.