Theoretical properties of the global optimizer of two layer neural network

By Digvijay Boob, Guanghui Lan. 2017

34 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Statistical Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Statistical Learning Theory

Citations in the corpus

Feature Purification: How Adversarial Training Performs Robust Deep Learning (2020, background): “Most of existing works (1) only focus on the case when the training data is spherical Gaussian [28–43], and some of them require heavy initialization using tensor decomposition, which might fail to capture the specific structure of the input and the property of a random initialization; or (2) only c”
Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data (2018, background): “There also exists a large body of work that analyzes the optimization landscape of learning neural networks [13, 26, 30, 10, 25, 29, 6, 32, 17, 5].”
Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers (2018, background): “1 What Can Neural Networks Provably Learn? Most existing works analyzing the learnability of neural networks [9, 12, 13, 20, 21, 28, 33, 34, 42, 43, 47, 49, 50, 56] make unrealistic assumptions about the data distribution (such as being random Gaussian), and/or make strong assumptions about the netw”
Spurious Local Minima are Common in Two-Layer ReLU Neural Networks (2017, background): “…if the network is over-parameterized, and large enough compared to the data size, then there are no local minima [Poston et al., 1991, Livni et al., 2014, Haeffele and Vidal, 2015, Zhang et al., 2016, Soudry and Carmon, 2016, Soltanolkotabi et al., 2017, Nguyen and Hein, 2017, Boob and Lan, 2017].”
Learning Over-Parametrized Two-Layer ReLU Neural Networks beyond NTK (2020, background): “…such as Kawaguchi (2016); Soudry and Carmon (2016); Xie et al. (2016); Soltanolkotabi et al. (2017); Tian (2017); Brutzkus and Globerson (2017); Boob and Lan (2017); Vempala and Wilmes (2018); Oymak and Soltanolkotabi (2019); Bakshi et al. (2018); Yehudai and Shamir (2019); Zhang et al.…”
Backward Feature Correction: How Deep Learning Performs Deep Learning (2020, background): “For such reason, it is not surprising that most existing theoretical works on the efficient learning regime of neural networks either focus on (1) two-layer networks [9, 10, 12, 22, 23, 36, 41, 41, 42, 46, 50, 51, 53, 54, 56, 58, 61] which do not have any hierarchical structure, or (2) a multi-layer”