Title: THE LOSS LANDSCAPE OF OVERPARAMETERIZED NEU-RAL NETWORKS

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 n 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 n . 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 n .

1. INTRODUCTION:

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 : R n → 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 R n 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 ⊂ R n 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 R n . 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 R n .

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 R n , and that at a global minimum, the Hessian of L has d positive eigenvalues, n-d eigenvalues equal to 0, and no negative eigenvalues. 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 R n . 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 R n .

1.1. ASSUMPTIONS:

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.

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



2.1. POSITIVE DIMENSIONALITY OF M:

Suppose we have a neural net of any architecture (e.g. feedforward, LSTM, etc.), with weights (w 1 , ...) and biases (b 1 , ...), n parameters in total. Suppose this net uses a smooth activation function σ and is training on a data set {(x i → y i )} with d data points. Each entry in the data set is given as a pair of vectors, x i ∈ R p (e.g. a vector of pixel values) and y i ∈ R. We assume that the x i are distinct and that n > d.

Let f w,b be the function given by the neural net with the parameters w, b. For each data points

(x i → y i ), let f i (w, b) = f w,b (x i ) -y i . Assume that each f i (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 f i (w, b) is smooth for each i.

Let the loss function used in training be the commonly used

L(w, b) = (f w,b (x i ) -y i ) 2 . Define f i (w, b) : R n → R as f i (w, b) = f w,b (x i ) -y i , so L(w, b) can be written as L(w, b) = f i (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 = M i ,

where

M i = f i (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 R n .

Remark 2.2. The loss function

L(w, b) = |f i (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 R n .

We start with a heuristic argument for Theorem 2.1.

Heuristic::

For each f i , the regular values of f i : R n → R are dense. So generically we expect that each

M i = f -1 i (0) is a smooth codimension 1 submanifold of R n . Generically the intersection of d smooth codimension 1 submanifolds of R n is a smooth codimension d submanifold, so one would expect that M = M i 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 : R n → R d be defined as the function

H(w, b) = (f 1 (w, b), ..., f d (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 = (r 1 , ..., r d ) with |r| < . We use r to perturb the data, replacing

x i → y i by x i → ỹi where ỹi = y i + r i . Let fi (w, b) = f i (w, b) -r i = f w,b (x i ) -ỹi , L(w, b) = f 2 i , and H(w, b) = ( f1 (w, b), ..., fd (w, b)) = H(w, b) -(r 1 , ..., r d ).

Note that |(x, y) -(x, ỹ)| < , 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 R n , as desired. Well, L = d i=1 f 2 i , so

2.2. THE LOCAL GEOMETRY OF THE LOSS FUNCTION NEAR:

M Proposition 2.3. Consider the submanifold M = L -1 (0) = M i , where M i = f -1 i (0). If each M i is a smooth codimension 1 submanifold of R n , M

H(L) = d i=1 H(f 2 i ).

Let us consider each summand. The linear transformation H(f 2 i ) has n -1 eigenvalues equal to 0 and a unique nonzero eigenvalue λ i . This follows from the fact that M i is a smooth codimension 1 submanifold. Furthermore, λ i is positive as 0 is a global minimum of f i . Let v i denote the eigenvector corresponding to this positive eigenvalue.

The vectors v 1 , ..., v d are linearly independent because the M i 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=1 A i , n > d, where each A i has a unique nonzero eigenvalue λ i and the corresponding vectors v i 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.

3. FEEDFORWARD NEURAL NETS CAN FIT POINTS:

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 R n . 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 R m , a labeling π : E ∪ V → {1, ..., m}, and an activation function σ. Let V in denote the set of input vertices (the vertices in V with no incoming edges) and V out 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 f G,π,σ,p : R |Vin| → R |Vout| as follows. For any input node v ∈ V in , its output o v is the corresponding coordinate of the input vector x ∈ R Vin . For each internal node v, its output is defined recursively as

o v = u→v∈E σ(p π(u→v) • o u + p π(v) ),

or perhaps more familiarly with weights and biases,

o v = u→v∈E σ(w π(u→v) • o u + b π(v) ).

For output nodes v ∈ V out , no non-linearity is applied and their output

o v = u→v∈E w π(u→v) • o u + b v

determines the corresponding coordinate of the computed function f G,π,σ,p .

We denote the hypothesis class of functions computable by the neural net using some choice of parameters by

N (G, π, σ) = {f G,π,σ,p |p ∈ R m }.

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 f G,π,σ,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 f w,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.

3.1. RECTIFIED ACTIVATION FUNCTIONS:

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 = {(x i , y i )} with d data points, x i ∈ R p , y i ∈ R, and a rectified activation function σ. Assume that the vectors x i are distinct, i.e. no two are equal. For any h ≥ d, there exists a feedforward neural network f w,b with 1 hidden layer of width h and activation function σ that represents S with zero training error. In fact, we produce weights w, b such that f w,b (x i ) = y i 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

f w,b (x) = M 2 σ(M 1 x -b 1 ) -b 2 ,

where M 1 , M 2 are linear transformations We use the convention that σ applied to a vector denotes component-wise evaluation:

σ(v 1 , ..., v m ) = (σ(v 1 ), ..., σ(v m )).

In our construction, we will take b 2 = 0 and all the rows of M 1 to be equal to a single vector a = (a 1 , ..., a p ). 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 f w,b of the form

f w,b (x) = d j=1 m j σ(a • x -b j )

such that f w,b (x i ) = y i for all i. Our job is to find values for the 2d + p parameters m 1 , ..., m d , a 1 , ..., a p , b 1 , ..., b d satisfying these conditions.

First, we choose a vector a ∈ R p such that {a • x i } are distinct. This is possible because we assumed the x i are distinct and a general projection from R p → R will preserve that property. Up to a reordering of the points x i , we can assume that {ax i } are increasing. Choose x 0 such that

ax 0 = ax 1 -1. Let b i = ax i-1 + ax i 2 .

Now, to arrange that f w,b (x i ) = y i we require

EQUATION

We express Equation 3.1 using the notation of matrix multiplication,

   y 1 . . . y d    =    σ(a • x 1 -b 1 ) • • • σ(a • x 1 -b d ) . . . . . . . . . σ(a • x d -b 1 ) • • • σ(a • x d -b d )       m 1 . . . m d    . (3.2)

Let us denote the matrix whose i, j th entry is (σ(a

• x i -b j )) by A.

By construction, A is lower triangular with nonzero entries on the diagonal, hence invertible. So we set the weights by

   m 1 . . . m d    = A -1    y 1 . . . y d    .

This gives us a choice of weights and biases for a neural network with one hidden layer which has learned the data {(x i , y i )} 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 = {(x i , y i )} with d data points, x i ∈ R p , y i ∈ R, and a rectified activation function σ. Assume that the vectors x i 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 f w,b represents S with zero training error.

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 = {x i , y i }, as long as the loss function L is of the form

L(w, b) = i |f i;w,b (x i ) -y i | a , a ≥ 1,

and each f i;w,b : R n → R is smooth. In practice, these conditions usually hold as long as a smooth activation function is used. (In practice, usually all the f i;w,b are even the same.) So in most settings, we are guaranteed that M is an n -d dimensional possibly empty submanifold of R n .

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.

:



Figures and Tables:

is nonempty, and the M i 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 ∈ R n , 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 of H(L)| m is at least n -d dimensional. It remains to show that it is also at most n -d dimensional.

R p → R h and M 2 : R h → R, and b 1 , b 2 are vectors b 1 ∈ R h and b 2 ∈ R. The weights w are the entries of M 1 and M 2 , and the biases b are the entries of b 1 and b 2 .

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.

Table content: <table/>

Peer review (iclr2019):
 This paper gave an interesting theoretical result that the global minima of an overparameterized neural network is a high-dimensional sub-manifold. This result is particularly meaningful as it connected several previous observations about neural networks and a indirect evidence for why overparameterization for deep learning has been so helpful empirically. The proof in the paper was smart and the rough logic was quite easy to follow. The minor issue is that the proof in the paper was too sketchy to be strict. For example, in proof for Thm 2.1, the original statement about Sard’s theorem was about the critical values, but the usage of this theorem in the proof was a little indirect. I can roughly see how the logic can go through, but I still hope the author can give more detailed explaining about this part to make the proof more readable and strict. Overall, I think the result in this paper should be enough to justify a publication. However, there’re still limitations of the result here. For example, the result only explained about the fitting on training data but cannot explain at all why overfitting is not a concern here. It also didn’t explain why stochastic gradient descent can find these minima empirically. In particular, even though the minima manifold is n-d dimensional, it’s still a zero-measure set which will almost never get hit with a random initialization. Of course, these are harder questions to explore, but maybe worthy some discussion in the final revision.