Year: 2018

Abstract:
We explore some mathematical features of the loss landscape of overparameterized neural networks. A priori one might imagine that the loss function looks like a typical function from R to R in particular, nonconvex, with discrete global minima. In this paper, we prove that in at least one important way, the loss function of an overparameterized neural network does not look like a typical function. If a neural net has n parameters and is trained on d data points, with n > d, we show that the locus M of global minima of L is usually not discrete, but rather an n − d dimensional submanifold of R. In practice, neural nets commonly have orders of magnitude more parameters than data points, so this observation implies that M is typically a very high-dimensional subset of R.

heading: 1 INTRODUCTION
text: In recent years, it has become clear that neural nets are incredibly effective at a wide variety of tasks. Why they work so well is less understood. During training neural nets implement a form of curve fitting, by minimizing a loss function L : Rn → R. Evidence suggests that they work better when there are more parameters than data points. Here we explore the geometry of the loss landscape of overparameterized neural networks, as a first step toward understanding their unreasonable effectiveness.
A priori one might imagine that the loss function L of a neural network looks like a typical function from Rn to R - in particular, nonconvex, with discrete global minima, many “bad” local minima that are not global minima, and complicated geometry. However, it turns out that in at least one important way, the loss function of an overparameterized neural network does not look like a typical function. In the overparameterized setting where the neural net has n parameters and is trained on d data points, with n > d, it is generally the case that L is nonconvex. However, the locus M ⊂ Rn of global minima of L is often not discrete. Indeed we find M is often quite the opposite – rather than being a discrete set, M is often an n− d dimensional submanifold of Rn. We expect this to be true in a very general setting. The neural network can be any depth, and while our strongest results are for feedforward neural networks, many of the results in this paper apply for a broader set of architectures. In practice, neural nets commonly have orders of magnitude more weights than data points, so in practical applications M is typically a very high-dimensional submanifold of Rn.
Our contributions include:
• Giving a heuristic that explains that in the overparameterized setting, generically the locus of global minima of the loss function should be an n− d dimensional submanifold of Rn, and that at a global minimum, the Hessian ofL has d positive eigenvalues, n−d eigenvalues equal to 0, and no negative eigenvalues. • Proving that for a broad class of activation functions, a large enough feedforward neural
network with one hidden layer can fit a fixed training dataset exactly. • Proving that for an overparameterized feedforward neural network with a rectified smooth
activation function, the locus of global minima for the loss function is a nonempty smooth n− d dimensional submanifold of Rn.
These results provide a theoretical setting for several lines of recent work. It has been widely suggested that gradient descent is successful in producing good solutions in deep learning because many
local minima are close to global minima and give similar results LeCun et al. (2015), Choromanska et al. (2015). As a result, the loss landscape has been studied in papers such as Freeman & Bruna (2017). Several authors have proved that under various strong assumptions, all local minima are global Liang et al. (2018), Ge et al. (2017), Laurent & Brecht (2017), Kawaguchi (2016). This is not true in “real world” settings for deep learning. But recent work has suggested that in some settings there are paths between local minima such that the value of the loss function stays low along the paths Garipov et al. (2018), Draxler et al. (2018). We show a stronger result in a more general setting. We prove that in a very general setting, there are not only one-dimensional paths between minima, but very high dimensional manifolds.
In Section 2, we study the geometry of the loss landscape in the general overparameterized setting. In Section 2.1 we study the global geometry of the landscape. We study the locus M = L−1(0) because L is a nonnegative function, so as long as M is nonempty, M is the locus of global minima of L. We show that if nonempty, M is an n − d dimensional submanifold of Rn. In Section 2.2, we consider the local geometry of the loss landscape near M , and show that if M is nonempty then at a global minimum m ∈ M , the Hessian of L has n − d zero eigenvalues, d positive ones, and no negative ones. This is consistent with previous observations in papers such as Chaudhari et al. (2016) and Wu et al. (2017).
In Section 3, we write down a proof of a commonly believed fact, that given a fixed dataset, a large enough one-hidden-layer feedforward neural net can memorize it exactly, i.e. learn it with zero training error. This is commonly assumed, and in the case that the activation function used is ReLU, proved in Zhang et al. (2016). We require a somewhat more general statement, but our argument is based on the one given there.
In Section 4, we combine the results of the previous two sections to show that in the setting of overparameterized feedforward neural networks, if they are wide enough then the locus M = L−1(0) is in fact a nonempty smooth n− d dimensional submanifold of Rn.

heading: 1.1 ASSUMPTIONS
text: In this paper, we will always consider the overparameterized setting. So in all of our analyses, we assume that the number of parameters n of the neural net is greater than the number of data points d that it is training on.

heading: 2 GEOMETRY OF THE LOSS LANDSCAPE L - GENERAL CASE

heading: 2.1 POSITIVE DIMENSIONALITY OF M
text: Suppose we have a neural net of any architecture (e.g. feedforward, LSTM, etc.), with weights (w1, ...) and biases (b1, ...), n parameters in total. Suppose this net uses a smooth activation function σ and is training on a data set {(xi → yi)} with d data points. Each entry in the data set is given as a pair of vectors, xi ∈ Rp (e.g. a vector of pixel values) and yi ∈ R. We assume that the xi are distinct and that n > d.
Let fw,b be the function given by the neural net with the parameters w, b. For each data points (xi → yi), let fi(w, b) = fw,b(xi)− yi. Assume that each fi(w, b) is smooth in w and b. For most choices of architecture, this is implied by the assumption that the activation function σ is smooth. For example, for any feedforward neural network, if σ is smooth then fi(w, b) is smooth for each i.
Let the loss function used in training be the commonly used L(w, b) = ∑ (fw,b(xi)− yi)2.
Define fi(w, b) : Rn → R as fi(w, b) = fw,b(xi)− yi,
so L(w, b) can be written as
L(w, b) = ∑ fi(w, b) 2.
It is clear from the definition that L(w, b) ≥ 0, so if nonempty, M = L−1(0) is the locus of global minima of L. Therefore, in this section we will focus on understanding the geometry of M in the case that it is nonempty.
Note that M = ⋂ Mi,
where Mi = fi(w, b) −1(0).
The rest of this section is devoted to the following theorem.
Theorem 2.1. In the setting described above, the set M = L−1(0) is generically (that is, possibly after an arbitrarily small change to the data set) a smooth n− d dimensional submanifold (possibly empty) of Rn. Remark 2.2. The loss function
L̂(w, b) = ∑ |fi(w, b)|
is also regularly used. Note that L̂−1(0) = L−1(0),
so Theorem 2.1 also shows that the locus M̂ = L̂−1(0) is a smooth n− d dimensional submanifold of Rn.
We start with a heuristic argument for Theorem 2.1.
Heuristic: For each fi, the regular values of fi : Rn → R are dense. So generically we expect that each Mi = f−1i (0) is a smooth codimension 1 submanifold of Rn. Generically the intersection of d smooth codimension 1 submanifolds of Rn is a smooth codimension d submanifold, so one would expect that M = ⋂ Mi is smooth of codimension d.
With this heuristic in mind, we proceed to a proof of Theorem 2.1.
Proof. We construct a function H related to L. Let H : Rn → Rd be defined as the function
H(w, b) = (f1(w, b), ..., fd(w, b)).
By construction, L = |H|2, and importantly,
M = L−1(0) = H−1 ((0, ..., 0)) .
If (0, ..., 0) is a regular value of H , proceed to next paragraph. If not, pick any > 0. By Sard’s theorem, regular values of H are generic. We may therefore choose a regular value r = (r1, ..., rd) with |r| < . We use r to perturb the data, replacing xi → yi by xi → ỹi where ỹi = yi + ri. Let
f̃i(w, b) = fi(w, b)− ri = fw,b(xi)− ỹi, L̃(w, b) = ∑
f̃2i ,
and H̃(w, b) = (f̃1(w, b), ..., f̃d(w, b))
= H(w, b)− (r1, ..., rd).
Note that |(x, y)−(x, ỹ)| < , meaning that after taking an arbitrarily small perturbation of the data, (0, ..., 0) is a regular value of H̃ .
After possibly replacing H by H̃ , (0, ..., 0) is a regular value of H , meaning
M = H−1((0, ..., 0))
is either empty or smooth of codimension d in Rn, as desired.

heading: 2.2 THE LOCAL GEOMETRY OF THE LOSS FUNCTION NEAR M
text: Proposition 2.3. Consider the submanifold M = L−1(0) = ⋂ Mi, where Mi = f−1i (0). If each Mi is a smooth codimension 1 submanifold of Rn, M is nonempty, and the Mi intersect transversally at every point of M , then at any point m ∈M , the Hessian of L evaluated at m has d positive eigenvalues and n− d eigenvalues equal to 0.
Proof. Let H(L) denote the Hessian of L. At every point p ∈ Rn, the Hessian of L evaluated at p, H(L)|p, is a real symmetric matrix, hence has a basis of eigenvectors. Since m is a minimum (in fact a global minimum) of L, the eigenvalues of H(L)|m are nonnegative. Since M is n − d dimensional, the kernel ofH(L)|m is at least n− d dimensional. It remains to show that it is also at most n− d dimensional. Well, L = ∑d i=1 f 2 i , so
H(L) = d∑ i=1 H(f2i ).
Let us consider each summand. The linear transformation H(f2i ) has n − 1 eigenvalues equal to 0 and a unique nonzero eigenvalue λi. This follows from the fact that Mi is a smooth codimension 1 submanifold. Furthermore, λi is positive as 0 is a global minimum of fi. Let vi denote the eigenvector corresponding to this positive eigenvalue.
The vectors v1, ..., vd are linearly independent because the Mi intersect transversally at m. An elementary linear algebra calculation shows that if an n × n matrix A is the sum of d matrices A = ∑d i=1Ai, n > d, where each Ai has a unique nonzero eigenvalue λi and the corresponding vectors vi are all linearly independent, then A has d nonnegative eigenvalues and n− d eigenvalues equal to 0. We conclude that in our setting, H(L) has d positive eigenvalues and n− d eigenvalues equal to 0, as desired.

heading: 3 FEEDFORWARD NEURAL NETS CAN FIT POINTS
text: We have seen that in a very general setting, assuming almost nothing about the architecture of a neural network, the locus M = L−1(0) is, if nonempty, a positive dimensional submanifold of Rn. However, whether M is nonempty depends on the chosen architecture and other details of implementation. In this section, we address the issue of nonemptiness of M in a (still fairly general) setting of feedforward neural networks with nice activation functions.
We start by recalling the definition of a feedforward network, and setting some notation. A feedforward neural network is specified by the data of a directed acyclic graph G(V,E), a parameter vector p in Rm, a labeling π : E ∪ V → {1, ...,m}, and an activation function σ. Let Vin denote the set of input vertices (the vertices in V with no incoming edges) and Vout the set of output vertices (those with no outgoing edges).
The labeling π associates to each edge or vertex a parameter. The parameters for the edges are commonly referred to as weights, and the parameters for the vertices are called biases. We often reflect this by referring to a pair of vectors w of weights and b of biases instead of a single parameter vector p.
Given a fixed parameter vector p, (or the pair (w, b)), we can construct a function fG,π,σ,p : R|Vin| → R|Vout| as follows. For any input node v ∈ Vin, its output ov is the corresponding coordinate of the input vector x ∈ RVin . For each internal node v, its output is defined recursively as
ov = ∑
u→v∈E σ(pπ(u→v) · ou + pπ(v)),
or perhaps more familiarly with weights and biases, ov = ∑
u→v∈E σ(wπ(u→v) · ou + bπ(v)).
For output nodes v ∈ Vout, no non-linearity is applied and their output ov = ∑
u→v∈E wπ(u→v) · ou + bv
determines the corresponding coordinate of the computed function fG,π,σ,p.
We denote the hypothesis class of functions computable by the neural net using some choice of parameters by N (G, π, σ) = {fG,π,σ,p|p ∈ Rm}. The term neural network can refer to a specific function, the hypothesis class of functions, or other related objects. When we use the term neural network, we generally mean a hypothesis class of functions, or this class of functions along with a framework for choosing parameters p such that the resulting function fG,π,σ,p fits the training data reasonably well.
When we talk about neural networks, we generally consider G, π, and σ fixed, and the task is to find a good choice of parameters p. We often suppress the fixed objects in our notation. For example, in this paper we will commonly use the notation fw,b to denote the function computed by a neural net with a choice of parameters w weights and b biases, and implicitly G, π, and σ are fixed in the discussion.

heading: 3.1 RECTIFIED ACTIVATION FUNCTIONS
text: Definition 3.1. We call a continuous function σ : R→ R rectified if
σ(x) = { 0, x ≤ 0, monotonic increasing, x > 0.
Our strongest results apply to feedforward neural networks whose activation function σ is rectified smooth.
The set of rectified smooth functions doesn’t contain most commonly considered activation functions. For example, ReLU, tanh, and sigmoid are not rectified smooth functions. However, ReLU modified by smoothing the corner at 0, commonly used in practice when implementing neural networks, is. Translated and truncated tanh and sigmoid are as well, and in practice behave similarly to tanh and sigmoid in neural networks.
For a concrete definition of a smooth rectified activation function, we make the following definition. Definition 3.2. Let smooLU be defined as
smooLU(x) = { 0, x ≤ 0, x exp(−1/x), x > 0.
In the remainder of this paper, the reader can take the activation function σ to be smooLU if desired. The function smooLU is similar to softplus, which is commonly used in neural nets.
With these concepts in hand, we proceed to the main result of this section. For the next lemma we don’t need to assume σ is smooth. Lemma 3.3. Fix a data set S = {(xi, yi)} with d data points, xi ∈ Rp, yi ∈ R, and a rectified activation function σ. Assume that the vectors xi are distinct, i.e. no two are equal. For any h ≥ d, there exists a feedforward neural network fw,b with 1 hidden layer of width h and activation function σ that represents S with zero training error. In fact, we produce weightsw, b such that fw,b(xi) = yi for all i. Here the number of parameters n governing the family of neural nets we consider in the construction is n = 2d+ p.
Proof. A feedforward neural net of this form is a function
fw,b(x) =M2σ(M1x− b1)− b2,
where M1,M2 are linear transformations
M1 : Rp → Rh andM2 : Rh → R,
and b1, b2 are vectors b1 ∈ Rh and b2 ∈ R.
The weights w are the entries of M1 and M2, and the biases b are the entries of b1 and b2.
We use the convention that σ applied to a vector denotes component-wise evaluation:
σ(v1, ..., vm) = (σ(v1), ..., σ(vm)).
In our construction, we will take b2 = 0 and all the rows of M1 to be equal to a single vector a = (a1, ..., ap). We also take h = d the number of data points. If h > d, one can set all the weights and biases of the nodes after the first d to be 0, so it suffices to make the construction for h = d. So we are looking for a function fw,b of the form
fw,b(x) = d∑ j=1 mjσ(a · x− bj)
such that fw,b(xi) = yi for all i. Our job is to find values for the 2d + p parameters m1, ...,md, a1, ..., ap, b1, ..., bd satisfying these conditions.
First, we choose a vector a ∈ Rp such that {a · xi} are distinct. This is possible because we assumed the xi are distinct and a general projection from Rp → R will preserve that property. Up to a reordering of the points xi, we can assume that {axi} are increasing. Choose x0 such that ax0 = ax1 − 1. Let
bi = axi−1 + axi
2 .
Now, to arrange that fw,b(xi) = yi we require yi = ∑ j σ(a · xi − bj)mj . (3.1)
We express Equation 3.1 using the notation of matrix multiplication,
 y1... yd  =  σ(a · x1 − b1) · · · σ(a · x1 − bd)... . . . ... σ(a · xd − b1) · · · σ(a · xd − bd)   m1... md  . (3.2) Let us denote the matrix whose i, jth entry is (σ(a · xi − bj)) by A. By construction, A is lower triangular with nonzero entries on the diagonal, hence invertible. So we set the weights by  m1...
md
 = A−1  y1...
yd  . This gives us a choice of weights and biases for a neural network with one hidden layer which has learned the data {(xi, yi)} with zero error.
Since a feedforward neural network with one hidden layer can always be embedded in a deeper feedforward net with sufficient width, we have the following corollary of Lemma 3.3.
Corollary 3.4. Fix a data set S = {(xi, yi)} with d data points, xi ∈ Rp, yi ∈ R, and a rectified activation function σ. Assume that the vectors xi are distinct, i.e. no two are equal. Among feedforward neural networks with activation function σ and T hidden layers, last hidden layer of width h ≥ d, remaining hidden layers of arbitrary width, there exists a choice of weights so that the neural network fw,b represents S with zero training error.
Proof. We can adapt the construction in the proof of Lemma 3.3 to the case of a deeper net by simply choosing a subset of the nodes of the deeper net to use. Suppose the T hidden layers have widths h1, ..., hT . The nodes we use are the first node of each of the first T − 1 hidden layers, and the first d nodes of the last hidden layer. Let the first linear transformation M1 : Rp → Rh1 be constructed as the vector a as in Lemma 3.3 in the first row and 0 in all other rows. Choose b1 so that a · xi− b1 is positive for all i. In the remaining layers, let the matrix Mj , 2 ≤ j ≤ T be 1 in the top left entry and 0 in all the others. Note that the property that a ·xi−b1 are all positive and distinct is preserved through the layers, because the activation function σ is rectified. Finally, let MT+1 be constructed as in Lemma 3.3.

heading: 4 GEOMETRY OF THE LOSS LANDSCAPE L - FEEDFORWARD CASE

heading: 4.1 POSITIVE DIMENSIONALITY OF M
text: Suppose we have a feedforward neural net of any depth and last hidden layer of width h > d. Suppose this net uses a rectified smooth activation function σ and is training on a data set {(xi → yi)} with d data points. Each entry in the data set is given as a pair of vectors, xi ∈ Rp (e.g. a vector of pixel values) and yi ∈ R. We assume that the xi are distinct. Let fw,b be the function given by the neural net with the parameters w, b. As before, let the loss function used in training be the commonly used
L(w, b) = ∑ (fw,b(xi)− yi)2.
Theorem 4.1. In the setting described above, the global minimum of L is generically (that is, possibly after an arbitrarily small change to the data set) equal to 0, and the set of global minima M = L−1(0) is a nonempty smooth n− d dimensional submanifold of Rn.
Proof. By Theorem 2.1,M = L−1(0) is a smooth n−d dimensional submanifold of Rn. It remains only to show thatM is nonempty. But that is exactly the guarantee of Lemma 3.3, given that we have assumed that σ is a rectified smooth activation function and that the architecture of the networks is a feedforward network whose last hidden layer has width at least d.
Remark 4.2. The results in this paper can all be modified to accommodate the case that yi ∈ R` (e.g. a space of labels) where ` > 1. The argument in Theorem 2.1 is modified by letting H : Rn → R`d be (f1(w, b), ..., fd(w, b)) where fi(w, b) is now a function from Rn to R`, and we find that M is codimension `d. The construction in Lemma 3.3 and Corollary 3.4 is modified by having ` copies of the neural network, one for each component of yi. The parameter bounds change appropriately. With strengthened versions of those results, the argument in Theorem 4.1 extends without modification to the more general setting.

heading: 5 DISCUSSION
text: In this paper, we note that far from being a typical function from Rn to R, the loss function of an overparameterized neural network has some special geometric properties. This is compatible with several recent observations. For example, in Chaudhari et al. (2016), it was empirically observed that at solutions found by training neural networks with standard methods, the Hessian of the loss function tended to have many zero eigenvalues, some positive eigenvalues, and a small number of negative eigenvalues, which tended to be small in magnitude compared to the positive eigenvalues. Similarly, in Wu et al. (2017), Wu, Zhu, and E train some small deep neural networks and compute the spectrum of the Hessian at points obtained after training. They too observe that across several different models and datasets most of the eigenvalues are approximately zero, with few negative eigenvalues. In fact, they conjecture that “the large amount of zero eigenvalues might imply that the dimension of this manifold is large, and the eigenvectors of the zero eigenvalues span the tangent space of the attractor manifold. The eigenvectors of the other large eigenvalues correspond to the directions away from the attractor manifold.” We have proved a more precise version of that statement here.
Note that Theorem 2.1 applies in a very general setting. In particular, it holds for a neural network of any architecture learning a data set S = {xi, yi}, as long as the loss function L is of the form
L(w, b) = ∑ i |fi;w,b(xi)− yi|a, a ≥ 1,
and each fi;w,b : Rn → R is smooth. In practice, these conditions usually hold as long as a smooth activation function is used. (In practice, usually all the fi;w,b are even the same.) So in most settings, we are guaranteed that M is an n− d dimensional possibly empty submanifold of Rn. To determine whether M is nonempty requires an argument specific to the chosen architecture and details of implementation, such as the one we gave here for feedforward neural networks with rectified smooth activation functions.

Review summaries:
The paper shows that the set of global minimums of an overparametrized network with smooth activation function is almost surely a high dimensional manifold. In particular, the dimension of this manifold is exactly n-d, where n is the number of parameters and d is the number of datas. To the best of my knowledge, this is the first proper proof of such non-surprising result.