On the Quality of the Initial Basin in Overspecified Neural Networks

By Itay Safran, Ohad Shamir. 2015

131 citations recorded by the source corpus.

Deep learning, in the form of artificial neural networks, has achieved remarkable practical success in recent years, for a variety of difficult machine learning applications. However, a theoretical explanation for this remains a major open problem, since training neural networks involves optimizing a highly non-convex objective function, and is known to be computationally hard in the worst case. In this work, we study the \emph{geometric} structure of the associated non-convex objective function, in the context of ReLU networks and starting from a random initialization of the network parameters. We identify some conditions under which it becomes more favorable to optimization, in the sense of (i) High probability of initializing at a point from which there is a monotonically decreasing path to a global minimum; and (ii) High probability of initializing at a basin (suitably defined) with a small minimal objective value. A common theme in our results is that such properties are more likely to hold for larger ("overspecified") networks, which accords with some recent empirical and theoretical observations.

Subfields: Artificial Intelligence, Computational Mechanics

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 Computational Mechanics

Citations in the corpus

Visualizing the Loss Landscape of Neural Nets (2017, background): “For networks with specific structures, there likely exists a monotonically decreasing path from an initialization to a global minimum [32, 15].”
Geometric Deep Learning: Going beyond Euclidean data (2016, background): “Understanding the structure of the optimization problems (10) and ﬁnding efﬁcient strategies for its solution is an active area of research in deep learning [60], [61], [62], [63].”
Convergence Analysis of Two-layer Neural Networks with ReLU Activation (2017, background): “[35] proved that with high probability, there exists a continuous decreasing path from random initial point to the global minimum, but SGD may not follow this path.”
No bad local minima: Data independent training error guarantees for multilayer neural networks (2016, background): “Previous works have shown that, given several limiting assumptions on the dataset, it is possible to get a low training error on a MNN with one hidden layer: [10] proved convergences for linearly separable datasets; [27] either required that d 0 > N , or clustering of the classes.”
Gradient Descent Finds Global Minima of Deep Neural Networks (2018, background): “Many previous works thus try to study the optimization landscape of neural networks with different activation functions [Soudry and Hoffer, 2017, Safran and Shamir, 2018, 2016, Zhou and Liang, 2017, Freeman and Bruna, 2016, Hardt and Ma, 2016, Nguyen and Hein, 2017, Kawaguchi, 2016, Venturi et al.,…”
Topology and Geometry of Half-Rectified Network Optimization (2016, background): “This is consistent with the overparametrization results from [13, 16] and the general common knowledge amongst deep learning practitioners.”
Recovery Guarantees for One-hidden-layer Neural Networks (2017, background): “…setting, where the global optima or local minima close to the global optima will be achieved when the number of parameters is large enough, including (Freeman & Bruna, 2016; Haeffele & Vidal, 2015; Livni et al., 2014; Dauphin et al., 2014; Safran & Shamir, 2016; Hardt & Ma, 2017).”
Gradient Descent with Identity Initialization Efficiently Learns Positive-Definite Linear Transformations by Deep Residual Networks (2018, background): “…treatments of neural network learning algorithms include Lee et al. (1996); Arora et al. (2014); Livni et al. (2014); Janzamin et al. (2015); Safran & Shamir (2016); Zhang et al. (2016); Nguyen & Hein (2017); Zhang et al. (2017); Orhan & Pitkow (2018), although these are less closely…”
Spurious Local Minima are Common in Two-Layer ReLU Neural Networks (2017, background): “Moreover, the probability of starting at a basin of such local minima is exponentially high in the dimension [Safran and Shamir, 2016].”
Algorithmic Regularization in Learning Deep Homogeneous Models: Layers are Automatically Balanced (2018, background): “…et al., 2015, Du and Lee, 2018, Hardt and Ma, 2016, Bartlett et al., 2018, Haeﬀele and Vidal, 2015, Freeman and Bruna, 2016, Vidal et al., 2017, Safran and Shamir, 2016, Zhou and Feng, 2017, Nguyen and Hein, 2017a,b, Zhou and Feng, 2017, Safran and Shamir, 2017], showing that the objective…”
Fix your classifier: the marginal value of training the last weight layer (2018, methodology): “Using normalized weights and an additional scale coefficient is similar in spirit to weightnormalization (Salimans & Kingma, 2016), with the difference that we use a single scale for all entries in the weight matrix, in contrast to a scale for each row that Salimans & Kingma (2016) uses.”
Exponentially vanishing sub-optimal local minima in multilayer neural networks (2017, background): “In assumption 3, for simplicity we have d 0 ˙ ≤ N , since in the case d 0 ≥ N the input is generically linearly separable, and sub-optimal local minima are not a problem (Gori & Tesi, 1992; Safran & Shamir, 2016).”
Spurious Valleys in One-hidden-layer Neural Network Optimization Landscapes (2019, methodology): “Other analysis involved studying goodness of the initialization of the parameter values θ0 (Daniely et al., 2016; Safran and Shamir, 2016; Du et al., 2017) or other topological properties of the loss (1), such as connectivity of sub-level sets (Draxler et al.”