In this paper, we study the problem of optimizing a two-layer artificial neural network that best fits a training dataset. We look at this problem in the setting where the number of parameters is greater than the number of sampled points. We show that for a wide class of differentiable activation functions (this class involves most nonlinear functions and excludes piecewise linear functions), we have that arbitrary first-order optimal solutions satisfy global optimality provided the hidden layer is non-singular. We essentially show that these non-singular hidden layer matrix satisfy a ``"good" property for these big class of activation functions. Techniques involved in proving this result inspire us to look at a new algorithmic, where in between two gradient step of hidden layer, we add a stochastic gradient descent (SGD) step of the output layer. In this new algorithmic framework, we extend our earlier result and show that for all finite iterations the hidden layer satisfies the``good" property mentioned earlier therefore partially explaining success of noisy gradient methods and addressing the issue of data independency of our earlier result. Both of these results are easily extended to hidden layers given by a flat matrix from that of a square matrix. Results are applicable even if network has more than one hidden layer provided all inner hidden layers are arbitrary, satisfy non-singularity, all activations are from the given class of differentiable functions and optimization is only with respect to the outermost hidden layer. Separately, we also study the smoothness properties of the objective function and show that it is actually Lipschitz smooth, i.e., its gradients do not change sharply. We use smoothness properties to guarantee asymptotic convergence of $O(1/\text{number of iterations})$ to a first-order optimal solution. Neural networks architecture has recently emerged as a powerful tool for a wide variety of applications. In fact, they have led to breakthrough performance in many problems such as visual object classification BID13 , natural language processing BID5 and speech recognition BID17 . Despite the wide variety of applications using neural networks with empirical success, mathematical understanding behind these methods remains a puzzle. Even though there is good understanding of the representation power of neural networks BID1 , training these networks is hard. In fact, training neural networks was shown to be NP-complete for single hidden layer, two node and sgn(·) activation function BID2 . The main bottleneck in the optimization problem comes from non-convexity of the problem. Hence it is not clear how to train them to global optimality with provable guarantees. Neural networks have been around for decades now. A sudden resurgence in the use of these methods is because of the following: Despite the worst case result by BID2 , first-order methods such as gradient descent and stochastic gradient descent have been surprisingly successful in training these networks to global optimality. For example, Zhang et al. (2016) empirically showed that sufficiently over-parametrized networks can be trained to global optimality with stochastic gradient descent. Neural networks with zero hidden layers are relatively well understood in theory. In fact, several authors have shown that for such neural networks with monotone activations, gradient based methods will converge to the global optimum for different assumptions and settings BID16 BID10 BID11 BID12 ).Despite the hardness of training the single hidden layer (or two-layer) problem, enough literature is available which tries to reduce the hardness by making different assumptions. E.g., BID4 made a few assumptions to show that every local minimum of the simplified objective is close to the global minimum. They also require some independent activations assumption which may not be satisfied in practice. For the same shallow networks with (leaky) ReLU activations, it was shown in Soudry & Carmon (2016) that all local minimum are global minimum of the modified loss function, instead of the original objective function. Under the same setting, Xie et al. (2016) showed that critical points with large "diversity" are near global optimal. But ensuring such conditions algorithmically is difficult. All the theoretical studies have been largely focussed on ReLU activation but other activations have been mostly ignored. In our understanding , this is the first time a theoretical result will be presented which shows that for almost all nonlinear activation functions including softplus, an arbitrary first-order optimal solution is also the global optimal provided certain "simple" properties of hidden layer. Moreover, we show that a stochastic gradient descent type algorithm will give us those required properties for free for all finite number of iterations hence even if the hidden layer variables are data dependent, we still get required properties. Our assumption on data distribution is very general and can be reasonable for practitioners. This comes at two costs : First is that the hidden layer of our network can not be wider than the dimension of the input data, say d. Since we also look at this problem in over-parametrized setting (where there is hope to achieve global optimality), this constraint on width puts a direct upper-bound of d 2 on the number of data points that can be trained. Even though this is a strong upper bound, recent results from margin bounds BID19 show that if optimal network is closer to origin then we can get an upper bound on number of samples independent of dimension of the problem which will ensure closeness of population objective and training objective. Second drawback of this general setting is that we can prove good properties of the optimization variables (hidden layer weights) for only finite iterations of the SGD type algorithm. But as it is commonly known , stochastic gradient descent converges to first order point asymptotically so ideally we would like to prove these properties for infinitely many iterations. We compare our results to some of the prior work of Xie et al. (2016) and Soudry & Carmon (2016) . Both of these papers use similar ideas to examine first order conditions but give quite different results from ours. They give results for ReLU or Leaky ReLU activations. We, on the other hand, give results for most other nonlinear activations, which can be more challenging. We discuss this in section 3 in more detail. We also formally show that even though the objective function for training neural networks is nonconvex, it is Lipschitz smooth meaning that gradient of the objective function does not change a lot with small changes in underlying variable. To the best of our knowledge , there is no such result formally stated in the literature. Soltanolkotabi et al. (2017 ) discuss similar results, but there constant itself depends locally on w max , a hidden layer matrix element, which is variable of the the optimization function. Moreover, there result is probabilistic. Our result is deterministic , global and computable. This allows us to show convergence results for the gradient descent algorithm, enabling us to establish an upper bound on the number of iterations for finding an ε-approximate first-order optimal solution ( ∇f () ≤ ε). Therefore our algorithm will generate an ε-approximate first-order optimal solution which satisfies aforementioned properties of the hidden layer. Note that this does not mean that the algorithm will reach the global optimal point asymptotically. As mentioned before, when number of iterations tend to infinity, we could not establish "good" properties. We discuss technical difficulties to prove such a conjecture in more detail in section 5 which details our convergence results. At this point we would also like to point that there is good amount of work happening on shallow neural networks. In this literature, we see variety of modelling assumptions, different objective functions and local convergence results. BID15 focuses on a class of neural networks which have special structure called "Identity mapping". They show that if the input follows from Gaussian distribution then SGD will converge to global optimal for population objective of the "identity mapping" network. BID3 show that for isotropic Gaussian inputs, with one hidden layer ReLU network and single non-overlapping convolutional filter, all local minimizers are global hence gradient descent will reach global optimal in polynomial time for the population objective. For the same problem, after relaxing the constraint of isotropic Gaussian inputs, they show that the problem is NP-complete via reduction from a variant of set splitting problem. In both of these studies, the objective function is a population objective which is significantly different from training objective in over parametrized domain. In over-parametrized regime, Soltanolkotabi et al. (2017) shows that for the training objective with data coming from isotropic Gaussian distribution, provided that we start close to the true solution and know maximum singular value of optimal hidden layer then corresponding gradient descent will converge to the optimal solution. This is one of its kind of result where local convergence properties of the neural network training objective function have studied in great detail. Our result differ from available current literature in variety of ways. First of all, we study the training problem in the over-parametrized regime. In that regime, the training objective can be significantly different from population objective. Moreover, we study the optimization problem for many general non-linear activation functions. Our result can be extended to deeper networks when considering the optimization problem with respect to outermost hidden layer. We also prove that stochastic noise helps in keeping the aforementioned properties of hidden layer. This result, in essence, provides justification for using stochastic gradient descent . Another line of study looks at the effect of over-parametrization in the training of neural networks BID9 Nguyen & Hein, 2017) . These result are not for the same problem as they require huge amount of over-parametrization . In essence, they require the width of the hidden layer to be greater than number of data points which is unreasonable in many settings. These result work for fairly general activations as do our results but we require a moderate over-parametrization , width × dimension ≥ number of data population, much more reasonable in practice as pointed before from margin bound results. They also work for deeper neural network as do our results when optimization is with respect to outermost hidden layer (and aforementioned technical properties are satisfied for all hidden layers).
This paper talks about theoretical properties of first-order optimal point of two layer neural network in over-parametrized case
{"src": "scitldr-AIC_train", "paper_id": "BkIkkseAZ"}