Why Learning of Large-Scale Neural Networks Behaves Like Convex Optimization
Authors: Hui Jiang
Venue:  (2020)
Keywords: function space
canonical space
neural networks
stochastic gradient descent
disparity matrix

Abstract: In this paper, we present some theoretical work to explain why simple gradient descent methods are so successful in solving non-convex optimization problems in learning large-scale neural networks (NN). After introducing a mathematical tool called  canonical space, we have proved that the objective functions in learning NNs are convex in the canonical model space. We further elucidate that the gradients between the original NN model space and the canonical space are related by a pointwise linear transformation, which is represented by the so-called  disparity matrix. Furthermore, we have proved that gradient descent methods surely converge to a global minimum of zero loss provided that the disparity matrices maintain full rank.  If this full-rank condition holds, the learning of NNs behaves in the same way as normal convex optimization. At last, we have shown that the chance to have singular disparity matrices is extremely slim in large NNs. In particular, when over-parameterized NNs are randomly initialized, the gradient decent algorithms converge to a global minimum of zero loss in probability. 

Under review as a conference paper at ICLR 2020
WHY LEARNING OF LARGE-SCALE NEURAL NET- WORKS BEHAVES LIKE CONVEX OPTIMIZATION
Anonymous authors Paper under double-blind review
ABSTRACT
In this paper, we present some theoretical work to explain why simple gradient descent methods are so successful in solving non-convex optimization problems in learning large-scale neural networks (NN). After introducing a mathematical tool called canonical space, we have proved that the objective functions in learning NNs are convex in the canonical model space. We further elucidate that the gradients between the original NN model space and the canonical space are related by a pointwise linear transformation, which is represented by the so-called disparity matrix. Furthermore, we have proved that gradient descent methods surely converge to a global minimum of zero loss provided that the disparity matrices maintain full rank. If this full-rank condition holds, the learning of NNs behaves in the same way as normal convex optimization. At last, we have shown that the chance to have singular disparity matrices is extremely slim in large NNs. In particular, when over-parameterized NNs are randomly initialized, the gradient decent algorithms converge global minimum of zero loss in probability.
INTRODUCTION
In the past decade, deep learning methods have been successfully applied to many challenging real- world applications, ranging from speech recognition to image classification and to machine translation, and more. These successes largely rely on learning a very large neural network from a plenty of labelled training samples. It is well known that the objective functions of nonlinear neural networks are non-convex, and even non- smooth when the popular ReLU activation functions are used. The traditional optimization theory has regarded this type of high-dimensional non-convex optimization problem as infeasible to solve (Blum & Rivest 1992, Auer et al., 1995) and any gradient- first-order local search methods do not converge to any global optimum in probability (Nesterov) 2004). However, the deep learning practices in the past few years have seriously challenged what suggested by the optimization theory. No matter what structures are used in a large scale neural network, either feed-forward or recurrent, either convolutional or fully-connected, either ReLU or sigmoid, the simple first-order methods such as stochastic gradient descent and its variants can consistently converge to a global minimum of zero loss no matter what type of labelled training samples used. At present, one of the biggest mysteries in deep learning is how explain why the learning of NNs is unexpectedly easy to solve. Plenty of empirical evidence accumulated over the past years in various domains has strongly suggested that there must be some fundamental reasons in theory to guarantee such consistent convergence to global minimum in learning of large-scale
neural networks. Recently, lots of empirical work (Goodiellow al. 2014 Zhang al. 2015) and
theoretical analysis (Baldi & Hornik 1989/ Choromansk et al. 2014; Livni et al. 2014 4|| Kawaguchi
2016: Safran & Shamir [016)] Soudry Carmon 2016 Nguyen Nguyen & Hein 2017 Chizat & Bach
2018 Safran & Shamir 2018 Du et al. [2018b al Allen-Zhu et al. 2018: You et al. 2018) have been reported to tackle this question from many different aspects.
In this paper, we present a novel theoretical analysis to uncover the mystery behind the learning of neural networks. Comparing with all previous theoretical work, such as Choromanska et al. (2044); Kawaguchi (2016); Soudry & Carmon (006)); Du et al. (2018b): Zou et al. (2018), we use some unique mathematical tools, like canonical model space and Fourier analysis, to derive theoretical proofs under very general setting without any unrealistic assumption on the model structure and data distribution. Unlike many math- neah- treatments in the literature, our method is technically concise and conceptually intuitive that it leads to intelligible sufficient condition for such

---

Under review as a conference paper at ICLR 2020
consistent convergence to occur. Our theoretical results have also well explained many common practices widely followed by deep learning practitioners.
PROBLEM FORMULATION
In this work, we study model estimation problems under the standard machine learning set- ting. Given finite training set of T samples of input and output pairs, denoted Df {(x1)11) (x2, 12), ... (xr M/r) the goal is to learn a model from input to output over the entire feature space f : y (x E R !/ RR,, which will be used to predict future imputs. In all practical applications, the input x normally lies in a constrained region in RKK, which can always be normalized into a unit hypercube, denoted as Ux- _ [o, 1]x Without losing generality, we may formulate the above learning problem to search for the optimal function f(x) within the function class L' (Ux) to minimize a loss functional measured in Dr. where (Ux) denotes all bounded absolutely inte- grable functions defined in [0, 1jK The loss function is computed as empirical errors accumulated over all training samples in Dr. The empirical error at each sample, (Xe, Vt), is usually measured by convex loss function (ye, f(x)), which penalizes classifiiiiinnnonnn errors and rewards correct classifications. In other words, meaningful loss function lyy s²) always satisfies:
y 1/) (y + v¹
1yy (gy./))
Obviously, the popular loss measures, such as mean squared error, cross-entropy, always satisfy the condition in eq.(l) and clearly convex functions with respect its second argument. Therefore, we may use a general notation to represent this learning problem as follows:
T Σ ((x:))
f arg min
Q([[r)) = arg min fEL'(Ux)
JEL
Next, let's consider how to parametarize the function space L' (UU) make the above optimization computationally feasible.
2.1 LITERAL MODEL SPACE
Based on the universal approximation theorems in Cybenko 1989) Hornik al. (1989) Hornik (1991), any function in L' (U)) can be approximated up to arbitrary precision by a well-structured neural network of sufficiently large model size. Here, structured neural networks using M free model parameters, and all weight parameters of each neural network are denoted as vector (w E MR Obviously, if M is made sufficiently large, M is good choice to parameterize the function space L L'(Ux) because given any bounded function fx) E L (UK)), ), there exists least one of model parameters in AM. denoted as w, to make the corresponding neural network approximate fxx up to arbitrary precision. In this case, the function represented by the underlying neural network denoted as fw (x). Furthermore, if M is finite and all model parameters are bounded, every function represented by each possible neural network in Am belongs to L (UU) As a result, once we pre-determine the neural network structure of model size M = || (assume that M is sufficiently large), the functional minimization problem in eq, can be simplified into an equivalent parameter optimization problem as follows:
AM to represent the set of all well-
w" arg min Q(wl)Dx) arg min WERM
Σ (yt, (x+)). W WERM
However, due to the weight-space symmetries and network redundancy, the mapping from AM to L7 (UK) is surjective but not injective. For any function f E L (U)). there always exist many different w in Au to make neural networks represent f equally well. In this work, the space of neural networks, AM, is called literal model space of L (Uk) because it only satisfies the existence requirement but not the uniqueness one. It is the non-uniqeeness of AM that makes extremely difficult directly conduct the theoretical analysis for the optimization problem in eq.
2

---

Under review as a conference paper at ICLR 2020
2.2 CANONICAL MODEL SPACE
Here, let's consider the so-called canonical model space for L-(Ux) A model space is called to be canonical it satisfies both existence and uniqueness requirements. other words, for every function f L' LEL' there exists exactly one unique model in the canonical model space to represent f- Moreover, every model in the canonical model space corresponds to a unique function in I, L.U(K) Therefore, the mapping between Z/(Ux) and its canonical model space is bijective. For (UK)) the multivariate Fourier series naturally form such canonical model space for I, (UK).
As in Pinsky 22022) given any function (x) E L' (Ux), we may compute its multivariate Fourier coefficients as follows:
---- XEUU f(x) e x dx (vk E Z*K
1k :
(4)
where i i= VII and 0x C, and ls = [ky, ... .... k&] is a tuple of K integers, denoting the K K-dimensional index of each Fourier coefficient. All Fourier coefficients of function f(x) can be arranged as an infinite sequence, i.e. 0 = {0p & E z² which in turn can be viewed as a point in a Hilbert space with an infinite number of dimensions. This Hilbert space is denoted as O. For the notational simplicity, we may represent eq.(4) by a generic mapping from any f(x) E L (Ux) to a θ as: = $ (f(x))-
According to the Fourier theorem, for any function f(x) E x.),,) these Fourier coefficients may be used to perfectly reconstruct (xx by summing the following Fourier series, which converges everywhere in x E Uk:
f(x)
Σ kEZ
ON 2 F -x
Because both eq. and 55. converge for any function f(x) T." (Uxx). therefore, θ is canonical model space of (x). Every function in f(x) can be uniquely represented by all of its Fourier coefficients 0 in O
According to the Riemann-Lebesgue lemma (8 in Pinsky 2002)), the Fourier coefficients O₂ decay from both sides in every dimension of As, i.e., 10x + the absolute value of any dimension of k goes to infinity, max kk| + oc. As a result, the Fourier serie in eq. can be truncated into partial sum centered at the origin. Given any small number >> 0, for any function fxx) E T. (UUx,, we can always choose finite number of the most significant Fourier coefficients located in the center, which are denoted as N. == (k |&y] S .,.... | S N The cardinality of N. is denoted as N [..] The truncated Fourier coefficients can also be arranged onto an N N-dimensional vector, O. = [0x & E N.J. which may be viewed as a point in a complete normed linear space with N dimensions. This mmitt-dimensione normed linear space is thus denoted as O Moreover, may use these truncated coefficients in Ne to form partial sum to approximate the original function fxx up to the precision 1 - c
f(x)
Σ KEN.
O% x
(6)
where fxx) is an infinitely differentiable function in UK. approximating f(x) up to e² in the 1 norm, i.c. -.-Exx [lf(x)) fxx)]]
In summary, for any function f(x) E (UKR), we may calculate its Fourier coefficients as in eq.(4)
to represent uniquely in the infiniteddimensional canonical space θ as F (J(x)) where 6. Furthermore, for the computational convenience, we may approximate C with finite-dimension space up to any arbitrary precision. For a given tolerance error e, we may truncate 0 by leaving out all insignificant coefficients and construct O of N dimensions above. This process is conveniently denoted as mapping: 9. =x))x On the other hand, 9, may be used to construct f(x) based on the partial sum in eq. (6) i.c. f(x) F - (xxxx)) 0.). As shown above. f(x) approximates the original function fx) up to the precision 1 - 22, denoted as f(x) = fxx + O().. Here, we call e-precision canonical model space of L (Ux). ). Obviously,
this finite dimensional space θ
the approximation error e² can be made arbitrarily small so as to make θ, approach O as much as possible.
3

---

Under review as a conference paper at ICLR 2020
Literal Modal Space Am
Canonical Space 0
Class LP[00,]]
W;
surjective
bijective
6,04)
Wa
0,
[dH]]
W,
8,
fj(x)
WL
Figure 1:
An illustration to show how literal vs. canonical model spaces are related when neural networks are used to approximate function class T. (UUx).
2.3 LITERAL VS. CANONICAL MODEL SPACE
For any neural network in the literal model space Am, assuming its model parameter is w(O), it forms function wwin (x) between its input and output. As we know fwoe; (x) L+(xx), we can easily find its corresponding representation in the canonical model space with infinite dimensions via (()) = * (Swro) (x)), where (()) E e. Similarly, we may truncate (()) to find its representation in an e-precision canonical model space with N dimensions as e & Fe (f (x)), where e! O.. As shown in Figure 1 the mapping from AM to @ is surjective but not injective while the mapping from θ T. (Uxx is bijective.
3
MAIN RESULTS
3.1 LEARNING IN CANONICAL SPACE
Let's consider the original learning problem (2 in the canonical model space. Since canonical model spaces normally have nice structures, i.e., every f(x) is uniquely represented as linear combination of some fixed orthogonal base functions. The functional minimization in eq. turns to be optimization problem determine the unknown coefficients in linear combination follows:
0- = arg min ec Q(0(Dr) = arg min
(v.. (x:
1=1
This learning problem turns out to be strikingly easy in the canonical model space.
Theorem The objective function QT) in 2 when constructed using convex loss measure I()), a convex convexfunction in the canonical model space, If the dimensionality of the canonical space is not less than the number of training samples in Dr, the global minimum achieves zero loss.
Proof: Given an arbitrarily small tolerance error e
any function f(x) e L'(UR) can be
uniquely mapped to point in an canonical space θ as: 0. (x)) Mcanwhile, the function f(x) may approximated by 0 = (k l E Mc with the partial sum Fourier series: fo. (x) EREN, 0₂ 2n = EREN, O ()), where 7) (x) ik If we constrain to optimize eq.
in the canonical space e,, the objective function is represented as:
T
QUooI Σ (v.,
Σ 1=
Σ O (xx))
Ut.
KEN,
Since the loss measure I(.) itself is a convex function its second argument, and the argument is linear combination of all parameters 0z. therefore, the right-hand side of the above equation is
4

---

Under review as a conference paper at ICLR 2020
convex function of its parameter 0.. When mean squared error is used for ((.), the above procedure is the same as the well-known least square method.
Due to eq. eq. if global minimum 0: achieves zero loss, it must satisfy: (yi, f(x)) 1 (Wi, EnEN, (x.) 0 (i 1.2. ,T), which are equivalent to a system of T linear equations: LREN, (x,) ya (1=1,2....,1
Obviously, the dimensionality of the canonical model space is not less than the number of point- wise distinct (and noncontradictory) training samples, T, we have more free variables in 0r than the total number of linear equations. Therefore, there exists at least one solution to jointly satisfy these independent equations, which also achieves the zero loss at the same time. If the dimensionality of the canonical model space is equal to the number of point-wise distinct training samples, there exists unique global minimum that achieves zero loss.
Corollary Dr) in 2) is convex functiooaal in L' L-Ux)-
For any two functions, f1, f2 L' (UKx, we may map them into the canonical model space C to find their representations as: A = =$ (fi) and 0₂ = (f2). As shown in e5. both fi and f2 can be represented
Proof:
linear function of 01 and 0g. Since I(-) is convex function, for any
0 S & S 1, it is trivial to show that Q fi + (1 - c) f2(D)) I e @(f + () (1 Therefore, Q(flPr) is convex functional in (URx.
3.2 GOING BACK TO LITERAL SPACE FROM CANONICAL SPACE
As shown above, learning in the canonical model space is standard convex optimization problem. However, the direct learning in the canonical model space may be computationally prohibitive in high-dimensional canonical spaces. At present, the common practice in machine learning is still to learn neural networks the literal model space. Here we will look at how the canonical space may help to understand the learning behaviours of neural networks in the literal space.
The learning of neural networks mainly uses the first-order methods, which solely rely on the gradients of the objective function. We will first investigate how the gradients in the literal model space related to the gradients in the canonical model space. Given model parameters w of neural network, point in the literal space AM with M |w| dimensions, the objective
which may be viewed function at w is denoted as (fw (Dr). ). If the training set Dr has T point-wise distint training samples, we consider e-precision canonical space, O.. The cardinality of O,, denoted N, is chosen to satisfy two conditions: i) N is not smaller than T; ii) N is large enough to make the truncation error sufficiently small. In this way, for any W in A A may be mapped to this canonical space as 0. = Pe w (x)) (0. E +.). Obviously, Qf [DN) = [ + O(e). However, the residual error term may be ignored since it can made arbitrarily small when we choose a large enough N. Moreover, due to N > T. the global minimum of the objective function achieves zero loss in this canonical space. In this work, we consider the learning problem of over-parameterized neural networks, where the dimensionality of the literal space, M |w], is much larger than the dimensionality of this canonical space, namely M > N.
Based the chain rule, we have:
V (w = Vo. (P) = Vo.
V (wFre(((x))
which can be represented as the following matrix format:
aQ
F
(xw
owi
0Q
30
aQ Owne
Fc
fO (x) Ormm
aQ
(8)
0e.,
aQ
8Q
O5 (x) Bur
Twn
Mx1
N
MXN
where the M x N matrix is called disparity matrix, denoted as H(w). The disparity matrix H(w) composed of M sets of Fourier coefficients (computed over the input x) of partial derivatives of
5

---

Under review as a conference paper at ICLR 2020
the neural network function with respect each of its weights. When we form the m-th row of the disparity matrix, we first compute the partial derivative of the neural network function fw (x) with respect to m-th parameter, Wm, in the neural netowork. This partial derivative, 0fw(x), Duum is still function of imput x. Then we first apply Fourier series in eq. to it and then truncate to keep the total N most significant Fourier coefficients. These N coefficients are aligned to be placed in the m-th row of the disparity matrix H w). This process is repeated for every parameter of the neural network so as to fill up all rows in the M x N matrix. Obviously, the disparity matrix depends on because when take different values, these function derivatives are normally different and so are their Fourier coefficients. For any given neural network w, this mapping can be represented as a compact matrix format:
V
Mx1 = H(W)
Vo. 0 Nx1
MxN
From the above, we can see that the gradient in the literal space related to its corresponding gradient in the canonical space through a linear transformation at every w, which is represented by the disparity matrix H(w). The dispurity matrix varies when w moves from one model to another in the literal space. As a result, we say that the gradient in the literal space is linked to its corresponding gradient in the canonical space via a point-wiss wise linear transformation.
Lemma Assume the used neural network sufficiently large (M 2 N). If w* is a stationary point of the objective function (f (Dr) and the corresponding disparity matrix H(w") has full rank at w", then w a global minimum of (DT..
Proof: If w" is stationary point, implies that the gradient vanishes at w in the literal model O. Substituting this into eq (9), we have
space, i.e., [w=((w)) Mx1
H(w")
MxN Vo. Q(0.)
0
(10)
Nx1
because M 2 N and H(w*) has the full rank (N), the only solution to the above equations in the canonical space is Ve. Q(0)) = O. In other words, the corresponding model 0 in the canonical space is also a stationary point. Since Q(+.) is a convex function in the canonical space, this implies the corresponding model 0* is a global minimum. Due to the fact that the objective functions are equal across two spaces when we map w to 0 i.e., Q(w") = Q(+)), we conclude that w is also global minimum in the literal space.
Lemma If w(O) is a stationary point of ((fw(Dr), but the corresponding disparity matrix H(w()) does not have full rank at w(O), then w(O) may be local minimum or saddle point or global minimum of ([[((DT))
Proof: The disparity matrix is an M x N matrix and we still assume M 2 N. If (w degenerates and does not have full rank at w()), it is possible have zero or some nonzero so- lutions in the canonical space to the system of under-specified equations in eq. TO). For the zero solution Vo, )))
0, the corresponding model of "!") in literal space is global minimum because the objective function is convex in the canonical space. However, for the non-zero solutions,
Ve, (( * 0, the corresponding model of σ!") in literal space is certainly not global minimum since the gradient does not vanish in the canonical space. They may corresponds to some bad local minimum or saddle points in the literal space since the gradient vanishes only in the literal space.
As we know that neural networks are directly learned in the literal space as in eq. 3.. We normally use some fairly simple first-order local search methods to solve this non-convex optimization problem. These methods include gradient descent (GD) and more computationally efficient stochastic gradient descent (SGD) algorithms. As shown in Algorithm l these algorithms operate in pretty simple fashion: it starts from a random model and the model is iteratively updated with the currently computed gradient V QaeQQ((ll (t) and some preset step sizes, h4 (k = 0, 2, which are usually decaying.
The optimization in eq. (3) is clearly non-convex in the literal space for any nonlinear neural networks. However, due to the fact that both literal and canonical spaces are complete and the gradients in both

---

Under review as a conference paper at ICLR 2020
Algorithm 1 Stochastic gradient descent (SGD) to learn neural networks in the literal space randomly initialize w(O), and set k 0 for epoch L do for each vnánibaatch in training set Dr do
w <- (A) - h2 V Q(w(k))
k +1
end for end for
spaces are linked through a point-wise linear transformation, in the following, we will theoretically prove that the gradient descent methods can solve this non-convex problem efficiently in the literal space in a similar way solving normal convex optimization problems. As long some minor conditions hold, the gradient descent methods surely converge to global minimum even in the literal space.
Theorem In the gradient descent methods Algorithm 7 assume neural network is large enough (M 2 N), if the initial model, w and the step sizes, byg (k = 0, ), are chosen as such to ensure the disparity matrix H (w) maintuins full rank at every w (k 0, 1,...), then it surely converges to a global minimum of zero loss. Moreover, the trajectory of Q (w((k) (k = 0, 0,1,
behaves in the same as those in typical convex optimization problems.
Proof: In non-convex optimization problems, as long as the objective function satisfies the Liptschitz condition and the step sizes are small enough at each step, the gradient descent in Algorithm 1 is guaranteed to converge
stationary point, namely Q(wQ(((())) 2004). As long H (()(k)) maintains full rank, according to Lemma minimum, i.e. ((w(+)) 0 as ls
O as k - (Nesterov w approaches global
where g(*) denotes the corresponding representation of (() in the canonical space. As V ((w(((())) + 0, ((w(k)) normally does not approach O. Let us show this by contradiction. Assume H(w(()) + 0. which means that every row of (+) approaches 0 at the same time. As we know, m-th row of H(w) corresponds to the Fourier series coefficients of the function 0fw(x) If the Fourier coefficients 8i.
Moreover, shown in eq. we have Qw)(w(())) H(w voQ(O()) for k =
are all approaching zero, means that the function itself approaches
well, i.e., 0fw(x) 0. 8w.
means the current neural network function fw (x) is irrelevant to the weight Wm. We may simply remove the link associated to Wm, without changing fw (x). Because all rows of H(w) approaches O, we may remove all links of all weights from the neural network without changing fw (x). ). In all network structures used for artificial neural networks, after all weights are removed, there usually does not exist any link from input to output. As result, as long as (w)(k)) - O, the current fw (x) approaches a constant function in the entire input range Uk. This normally will not happen if suitable initial model chosen. Therefore, we have H(w(()) - 0 for all 0, 1,..., If (+)) w maintain full rank at the same time, as VwQ(w - O, we will surely have v)Q(O(*)) - 0. The trajectory of g(*) will converge towards global minimum in the convex loss suface in the canonical space. Since the objective functions are equal across two spaces when we map w<(k) ((x), i.e.. Q ((w(k)) (k)) = (()(k)), ), then the trajectory of Q(w(+)) will go down steadily in the literal space until it converges to the global minimum.
3.3 WHEN DO THE DISPARITY MATRIX H (w) DEGENERATE?
As shown above, the success of gradient descent learning in the literal space largely depends on the rank of the disparity matrix H (w). Here we will study under what conditions the disparity matrix H(w) may degenerate into singular matrix. As we have seen before, the disparity matrix H(w) a quantity solely depending on the structure and model parameters of neural network, w, and has nothing to do with the training data and the loss function. Since its columns orthogonal Fourier bases, its column vectors remain linearly independent unless its row vectors degenerate. As an M x N matrix (M N), H(w) may degenerate in two different ways: i) some
derived from
7

---

Under review as a conference paper at ICLR 2020
rows vanish into zeros; ii) some rows are coordinated to become linearly dependent. In the following, we will look at how each of these cases may actually occur in actual neural networks.
3.3.1 DEAD NEURONS
In a neural network, if all in-coming connection weights to a neuron are chosen in such a way as to make this neuron remain inactive the entire input range Ug. e.g., choosing small connection weights but a very negative bias for ReLU node. In this case, for any x E Uk, this neuron does not generate any output. It becomes a dead neuron in the network. Obviously, for any connection weight to to a dead neuron, 0fw(x) = O. As a result, the corresponding row of w in H(w) is all zeros. Therefore, dead neurons lead to zero rows in H(w) and they may reduce the rank of H(w), The bad thing is that the gradients of all weights to a dead neuron are always zero. In other words, the gradient descent methods can save any dead neurons once they become dead. In very large neural network, if a large number of neurons are dead, the model may not have enough capacity to universally approximate any function L' (Ux), this invalidates the assumption of completeness from the literal space to the canonical space. Obviously, the learning of this neural network may not be able to converge to a global minimum once large number of neurons are dead.
Dw
3.3.2 DUPLICATED OR COORDINATED NEURONS
If many neurons in a neural network are coordinated in such a way that their corresponding rows in the disparity matrix H ((w) become linearly dependent, this may reduce the rank of H (w) well. However, in a large nonlinear neural network, the chance of such linear dependency is very small except the case of duplicated neurons. Two neurons called be duplicated only if they connected to the same input nodes and the same output nodes and these input and output connection weights happen to be identical for these two neurons. Obviously, two duplicated neurons responds in the same way for any input x so that one of them becomes redundant. The rows of H(w) corresponding to duplicated neurons are the same so that its rank is reduced. Similar to dead neurons, the duplicated neurons will have the same gradients for their weights. As result, once two neurons become duplicated, they will remain as duplicated hereafter gradient descent algorithms. Like dead neurons, if there are large number of duplicated neurons in a neural network, this may affect the model capacity for universal approximation. As a result, the learning may not be able to converge to global minimum.
3.3.3 INITIAL CONDITIONS ARE THE KEY
In an over-parameterized neural network (assume M >> N), the disparity matrix H(w) becomes singular only after at least M N neurons become dead or duplicated or coordinated, each of which essentially indicates all neural network parameters happen to satisfy an equality constraint. If the initial model (())) is randomly selected in such way that all hyperplanes corresponding to all neurons intersect the input space UK from the center as much as possible. The initial disparity matrix nonsingular in probability one. When we use the gradient descent algorithms in Algorithm to update the model, the chance to derive any new dead or duplicated neurons is extremely slim because it unlikely for all parameters to simultaneously satisfy a large number of equality constraints. This is intuitively similar to the case where a large number of random points are generated in high-dimensional space, the chance for all points to happen to lie hyper-plane is sufficiently small. Therefore, when an over- peeerpaarmtteizeed neural network is randomly initialized, the gradient descent algorithm in Algorithm will converge to a global minimum of zero loss in probability one.
4 FINAL REMARKS
In this paper, we have presented some theoretical analysis to explain why gradient descents can effectively solve non-convex optimization problems learning large-scale neural networks. We make use of a novel mathematical tool called canonical space, derived from Fourier analysis. As we have shown, the fundamental reason to unravel this mystery is the completeness of model space for the function class L' (Ux) when neural networks are wer-parameteriized The same technique can be easily extended to other function classes, such as linear functions (Baldi & Hornik 1989 Kawaguchi 2016: Haeffele & Vidal. 2015), analytic functions and band-limited functions (Jiang
8

---

Under review as a conference paper at ICLR 2020
2019 As another future work, may further quantitively characterize the disparity matrix H(w) to derive the convergence rate in learning large neural networks.
REFERENCES
Z. Allen-Zhu, Y. Li, and Z. Song. A convergence theory for deep learning via over- paramceeriizztionnn In preprint arXiv:1811.03962. 2018.
P. Auer, M. Herbster, and M.K. Warmuth. Exponentially many local minima for single neurons, In Proc. of Advances in Neural Information Processing Systems 8 (NIPS), 1995.
Baldi and K. Hornik. Neural networks and principal component analysis: Learning from examples without local minima. Neural Networks, 2:5 1989.
A. L. Blum and L. Rivest. Training 3-node neural network is NP-complete. Neural Networks, (1):117-127, 1992.
L. Chizat and Bach. On the global convergence of gradient descent for over-parameterizedd models using optimal transport. In Proceedings of the 32nd Conference on Neural Information Processing Systems (NeurIPS), 2018.
A. Choromanska, M. Henaff, M. Mathieu, G. Ben Arous, and Y. LeCun. The loss surfaces of multilayer networks. In preprint arXiv:1412.025:: 2014.
2014.
G. Cybenko. Approximation by superpositions of a sigmoidal function. Mathematics of Control, Signals, and Systems, 2:303-314, 1989.
Du, Lee, H. L., L. Wang, and Zhai. Gradient descent finds global minima of deep neural networks. In preprint arXiv: /8/ 038804, 2018a.
S. S. Du, X. Zhai, B. Poczos, and A. Singh. Gradient descent provably optimizes wver-parameterized 2018b.
neural networks. In preprint arXiv:
I. Goodfellow, O. Vinyals, and A. M. Saxe. Qualitatively characterizing neural network optimization problems. In preprint 14 1412.6544, 2014.
B. D. Haeffele and R. Vidal. Global optimality in tensor factorization, deep learning, and beyond. In preprint arXiv:1506.07540 2015.
K. Hornik. Approximation capabilities of multilayer feedforward networks. Neural Networks, 4: 251-257, 1991.
K. Hornik, M. Stinchcombe, and H. White. Multilayer feedforward networks are universal approxi- mators. Neural Networks, 2(5):359-366, 1989.
H. Jiang. A new perspective on machine learning: How to do perfect supervised learning. In preprint 1901.0090. 2019.
K. Kawaguchi. Deep learning without poor local minima. In Advances in Neural Information Processing Systems 29 (NIPS 2016), 2016.
R. Livni, Shalev-Shwartz, and O. Shamir. On the computational efficiency of training neural networks. In preprint 141111140..1141, 2014.
Y. Nesterov. Introductory Lectures Convex Programming. Springer, 2004.
Q Nguyen and M. Hein. The loss surface of deep and wide neural networks. In Proceedings of the 34th International Conference on Machine Learning, 2017.
M. A. Pinsky. Introduction Fourier Analysis and Wavelets. Brooks/Cole Thomson Learning, 2002.
I. Safran and O. Shamir. On the quality of the initial basin in overspecified neural networks. In Proceedings of the 33rd International Conference on Machine Learning, 2016.

---

Under review as a conference paper at ICLR 2020
1. Safran and O. Shamir. Spurious local minima are common in two-layer ReLU neural networks, In Proceedings of the 35th International Conference on Machine Learning, 2018.
D. Soudry and Y. Carmon. No bad local minima: Data independent training error guarantees for multilayer neural networks. In preprint 3xXi::660.083600 2016.
Zhang, H. Jiang, S. Wei, and Dai. Rectified linear neural networks with tied-scalar regularization for LVCSR. In Proc. of Interspeech, 2015.
D. Zou, Y. Cao, D. Zhou, and Q. Gu. Stochastic gradient descent optimizes ver-parameterized deep ReLU networks. In preprint arXiv:1811.08855 2018.
10


Reviews:
[{"review_id": "ryl74Xw_cr", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper studies the problem of optimization for neural networks. It compares the optimization problem in parameter space with the corresponding problem in function space. In particular, it parameterizes function space using Fourier coefficients, so that the new problem is convex. When the \"disparity matrix\" (Jacobian) of the mapping from parameter space into function space has full rank, then critical points in parameter spaces are critical points in function space and hence global minima. The paper concludes by stating that \"an over-parameterized neural network is randomly initialized [...] will converge to a global minimum of zero loss in probability one\".\n\nI believe that the paper in its current form should be rejected. The main reason is that the second part of the paper is not rigorous, and the results that are shown do not imply that the optimization process will converge to a global optimum (contrary to what is explicitly stated). Indeed, while it is reasonable to assume that the \"disparity matrix\" should have full rank at initialization, this may not remain true throughout the training process. \nThere are also other technical problems, discussed below.\n\nSome comments:\n\n* The notation Q(.) is used inconsistently (Q(f), Q(w) and Q(\\theta)). The same is true for f_*, (f_w and f_\\theta).\n* I believe the disparity map is simply the Jacobian of the mapping w->theta.\nAlso, there are missing gradient symbols in eq. 8.\n* The \"canonical model space\" is not clearly defined. I believe it is simply L1(U) parameterized in a certain way, but this should be stated.\n* By considering the mapping into the truncated \"canonical model space\" (i.e., using a finite number of Fourier coefficients) then f_theta is not exactly equal to f_w. In particular, if f_theta has zero loss, then the same is not necessarily true for f_w. Thus, we cannot conclude that f_w is a global minimum. \n* The last statement in Theorem 2 is not clear (\"the trajectory [...] behaves in the same as those in typical convex optimization problems\"). From the proof, I believe it should mean that the disparity map never vanishes, but I don't understand why this is relevant (we would like for it to have full rank).\n* The main result of the paper rests on the claim \"When we use the gradient descent algorithms in Algorithm 1 to update the model, the chance to derive any new dead or duplicated neurons is extremely slim because it is unlikely for all parameters to simultaneously satisfy a large number of equality constraints\" but this is not rigorous and wrong.\n* Some typos: \"pointwise distint\", \"suface\"", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "rken2bFEcS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\nThis paper presents an argument that massively overparameterized neural networks trained with gradient descent on a supervised learning problem with convex loss function will converge. It argues that by mapping each model to a truncated Fourier series we can recover a canonical representation for the functions in the model space. Viewing this as a linear map at each point in parameter space and assuming that this matrix is always full rank, they claim convergence of gradient descent.\n\n\nDecision:\nThis paper should be rejected because it lacks originality, the assumptions are often too strong, and the rigor of some claims is questionable.\n\nMain argument:\nOriginality:\nThis is the main issue with the paper. Several papers, for example the ones from Allen-Zhu et al. and Du et al. cited in the paper, have shown that gradient descent on supervised learning provably converges for massively overparameterized neural networks. Not only that, but those works give rigorous proofs of their claims and even handle issues like step size, convergence rates, and precise conditions on the size and architecture of the neural network. This paper does not attempt to handle any of these details, claiming to simplify the proof. To me the proof is only simplified since the details are all omitted.\n\nAssumptions:\nThe main way that details are avoided is by adding a strong assumption that the “disparity matrix” remains full rank over the course of training. This assumption is not supported in an empirical or formal way, but rather by appeal to some vague argument in section 3 that since the matrix is likely to be full rank at initialization, it is likely to remain so for large enough networks. \n\nRigor:\nAs explained above, many details are omitted in favor of strong assumptions, but there are also some technical details that I think may be wrong. On page 2, it is claimed that the mapping from Lambda_M to L^1 is surjective, this is not true. Every function in L^1 can be approximated by some function in Lambda^M, but for finite M this map cannot be surjective. Another similar issue arises in the proof of Theorem 1 when it is claimed that there is a unique theta_epsilon corresponding to each f. This is again false since by truncating the Fourier series, infinitely many functions will get mapped to the same truncation (when they only differ in the higher coefficients). These issues make me question the validity as well as the originality of the arguments presented.\n\n\nAdditional feedback:\n- I saw a few spelling and grammatical errors. For example: in the abstract the tenses alternate between present and past almost every sentence (“we have proved” should be “we prove”),  page 2 “parametarize”, page 3 “serie”, page 5 “distint”, page 7 “Liptschitz”, section 3.3 title should be “when does” not “when do”.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "SJxjTucgcr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper claims to analyze the global convergence of large-scale neural networks (NNs). Their analysis relies on the idea of “canonical space”, which upon further reading, is nothing more than multi-dimensional Fourier analysis.\n\nWhile the analysis of NNs is an extremely important problem, it is not clear what results are actually presented here nor how their results relate to other theoretical analyses of NNs. The introduction of Fourier analysis as a new mathematical tool, and devotion of a whole page to this “canonical space model” is almost laughable. Furthermore, this statement in the introduction is not only incorrect but it is absurd. To make such a claim would require a significant amount of background and review of literature to even place these statements in context.\n        “No matter what structures are used in a large scale neural network, either feed-forward or recurrent, either convolutional or fully-connected, either ReLU or sigmoid, the simple first-order methods such as stochastic gradient descent and its variants can consistently converge to a global minimum of zero loss no matter what type of labelled training samples are used.” \n\nSpecific comments:\n“to derive theoretical proofs under a very general setting without any unrealistic assumption on the model structure and data distribution.” - how is this possible?\n“A new mathematical tool called canonical space” = Fourier analysis (??) this is not a new mathematical tool\nSection 2 = a standard formulation of neural networks, followed by undergraduate level Fourier analysis.\nIn 2.1. What is a “well structured” network? Unclear from the notation and definitions.\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "SJgepihG9H", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper looks at the neural net training problem in a \"canonical space\" which is parameterized by the Fourier coefficients of the function. This canonical space is a bijection of the function space L^1([0, 1]^K), and if we allow an epsilon approximation of the function we can truncate the Fourier coefficients so that the canonical space is finite-dimensional. The paper shows that in the canonical space, the training problem is always convex. Going back to the literal space (original parameter space for a neural network), it is shown that as long as a \"disparity matrix\" remains full rank, gradient descent will converge to a global minimum.\n\nI don't think this paper has anything new or non-trivial. I also don't think it's helpful to look at the canonical space proposed in the paper. In particular, it just transfers the difficulty of the problem into a disparity matrix, which we actually don't have control over. The paper claims that the matrix can be made full rank. This is not correct. Maybe one can prove it's full rank at random initialization, but I don't see how to prove this throughout training. The authors would need to provide a rigorous proof in order to claim this.\n\nIn fact, in non-convex optimization it's easy to arrive at a scenario where you \"only\" need some matrix to remain full rank in order to prove convergence to global minimum. One such example is the recent series of work on neural tangent kernel (NTK). There, as long as the NTK matrix stays full rank (actually, one needs eigenvalues bounded away from 0), one can show convergence to global minimum. However, to actually show this, one needs to apply stringent assumptions on the neural network architecture and to devote dozens of pages to the proof.", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies the problem of optimization for neural networks, by comparing the optimization problem in parameter space with the corresponding problem in function space. It argues that overparametrised models leads to a convex problem formulation leading to global optimality. 

All reviewers agreed that this paper lacks mathematical rigor and novelty relative to the current works on overparametrised neural networks. Its arguments need to be substantially reworked before it can be considered for publication, and as a consequence the AC recommends rejection. 
Decision: Reject