When Expressivity Meets Trainability: Fewer than $n$ Neurons Can Work
Authors: Jiawei Zhang
Yushun Zhang
Mingyi Hong
Ruoyu Sun
Zhi-Quan Luo
Venue: NeurIPS 2021 Poster (2021)
Keywords: deep learning theory
narrow
small neural networks
optimization
memorization
deep learning
neural networks

Abstract: Modern neural networks are often quite wide, causing large memory and computation costs. It is thus of great interest to train a narrower network. However, training narrow neural nets remains a challenging task. We ask two theoretical questions: Can narrow networks have as strong expressivity as wide ones? If so, does the loss function exhibit a  benign optimization landscape? In this work, we provide partially affirmative answers to both questions for 1-hidden-layer networks with fewer than $n$ (sample size) neurons when the activation is smooth.  First, we prove that as long as the width $m \geq 2n/d$ (where $d$ is the input dimension), its expressivity is strong, i.e., there exists at least one global minimizer with zero training loss. Second, we identify a nice local region with no local-min or saddle points. Nevertheless, it is not clear whether gradient descent can stay in this nice region. Third, we consider a constrained optimization formulation where the feasible region is the nice local region, and prove that every KKT point is a nearly global minimizer. It is expected that projected gradient methods converge to KKT points under mild technical conditions, but we leave the rigorous convergence analysis to future work. Thorough numerical results show that projected gradient methods on this constrained formulation significantly outperform SGD for training narrow neural nets. 

When Expressivity Meets Trainability: Fewer than n Neurons Can Work
Jiawei Zhang*
Yushun Zhang*
Shenzhen Research Institute of Big Data
Shenzhen Research Institute of Big Data
The Chinese University of Hong Kong,
The Chinese University Hong Kong,
Shenzhen, China
Shenzhen, China
j jiaweizhang2@link cuhk. edu.
yushunzhang@l. ink. cuhk. ouhk.edu.com
Mingyi Hong
University of Minnesota Twin Citie MN, USA
mhong@umn edu
Ruoyu Sun
Zhi-Quan Luo
University of Illinois at Urbana-Champaiga IL, USA
Shenzhen Research Institute of Big Data The Chinese University of Hong Kong, Shenzhen, China luozq@cuhk. edu. on
ruoyus@illinois.. edu
Abstract
Modern neural networks often quite wide, causing large memory and com- putation costs. is thus of great interest to train narrower network. However, training narrow neural nets remains challenging task. We ask theoretical questions: Can narrow networks have as strong expressivity as wide ones? If so, does the loss function exhibit benign optimization landscape? In this work, we provide partially affirmative answers to both questions for I-hidden-layer networks with fewer than n (sample size) neurons when the activation is smooth. First, we prove that as long as the width m 2 2n/d (where d is the input dimension), its expressivity is strong, i.c., there exists least one global minimizer with zero training loss. Second, we identify nice local region with no local-min or saddle points. Nevertheless, is clear whether gradient descent can stay this nice re- gion. Third, we consider constrained optimization formulation where the feasible region is the nice local region, and prove that every KKT point nearly global minimizer. It is expected that projected gradient methods converge to KKT points under mild technical conditions, but we leave the rigorous convergence analysis to future work. Thorough numerical results show that projected gradient methods on this constrained formulation significantly outperform SGD for training narrow neural nets.
1 Introduction
Reducing the size of neural nets is appealing for many reasons: first, small networks are more suitable for embedded systems and portable devices; second, using smaller networks can reduce power consumption, contributing to "green computing".
Modern neural networks are huge (e.g. 8 (4]).
"Equal contribution. These authors are listed in alphahetical order.
i Corresponding author: Ruoyu Sun.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

There are many ways to reduce network size, such as quantization, sparcification and reducing the width (e.g. (20 777) In this work, we focus on reducing the width (training narrow nets).
Reducing the network width often leads to significantly worse performance F] What is the possible cause? From the theoretical perspective, there are three possible causes: worse generalization power, worse trainability (how effective a network can be optimized), and weaker expressivity (how complex the function network can represent; see Definition []. Our simulation shows that the training error deteriorates significantly as the width shrinks, which implies that the trainability and/or expressivity are important causes of the worse performance (see Section 5.1 for more evidence ) We do not discuss generalization power for now, and leave it to future work.
So how is the training error related expressivity and trainability? The training error is the sum of two parts (see, e.g., [64] ): the expressive error (which is the best given network can do; also the global minimal error) and the optimization error (which is the gap between training error and the
global minimal error; occurs because the algorithm may not find global-min). The two errors are of different nature, and thus need to be discussed separately.
is understandable that narrower networks might have weaker expressive power. What about optimization? There is also evidence that smaller width causes optimization difficulty. A number of recent works show that increasing the width of neural networks helps create a benign empirical loss landscape (119 35 (59), while narrow networks (width m < sample size n) suffer from bad landscape (22 60 66, 72, 79).. Therefore, if we want to improve the performance of narrow networks, it is likely that both expressiveness and trainability need to be improved.
The above discussion leads to the following two questions:
(Q1) Can a narrow network have as strong expressivity as a wide one? (Q2) If so, can a local search method find a (near) globally optimal solution?
The key challenges in answering these questions are listed below:
It is not clear whether a narrow network has strong expressivity or not. Many existing works focus on verifying the relationship between zero-training-enen solutions and stationary points, but they neglect the (non)existence of such solutions (e.g. [7]] [63). For narrow networks, the (non)-existence of vero-training-erroo-oouuiii is not clear.
Even if zero-training-erro solutions do exist, it still not clear how to reach those solutions because the landscape of narrow neural network can be highly non-convex.
Even assuming that we can identify a region that contains zero-training-ere solutions and has a good landscape, it is potentially difficult to keep the iterates inside such good region. One may think of imposing an explicit constraint, but this approach might introduce bad local minimizers on the boundary (6).
In this work, we (partially) answer (Q1) and (Q2) for a I I-hidden-layer nets with fewer than neurons. Our main contributions are as follows:
Expressiveness and nice local landscape. We prove that, as long as the width m is larger than 2n/d (where n is the sample size and d is the input dimension), then the expressivity of the 1-hidden-layer net strong, i.e., w.p. 1. there exists least one global-min with zero empirical loss. In addition, such a solution is surrounded by good local landscape with no local-min or saddles. Note that our results do not exclude the possibility that there are sub-optimal local minimizers on the global landscape.
Every KKT point is an approximated global minimizer. For the original unconstrained optimization problem, the nice local landscape does not guarantee the global statement of "every stationary point a global minimizer". We propose a constrained optimization problem that restricts the hidden weights to be close to the identified nice region. We show
"This can be verified on our empirical studies in Section Another evidence that structure pruning (reducing the number of channels in convolutional neural nets (CNN)) is known to achieve worse performance than unstructured pruning: this is an undesirable situation since many practitioners prefer structure pruning (due to hardware reasons).

---

that every Karush-Kuut Kuhn-Tucker (KKT) point is an approximated global minimizer of the unconstrained training problem
In real-data experiments, our proposed training regime can significantly outperforms SGD for training narrow networks. We also perform ablation studies to show that the new elements proposed in our method are useful.
2 Background and Related Works
The expressivity of neural networks has been popular topic in machine learning for decades. There are two lines of works: One focuses on the infinite-sann -aaiiee expressivity, showing what functions of the entire domain can and cannot be represented by certain classes of neural networks (e.g. 4 45)). Another line of works characterize the finite-sample expressivity, i.e. how many parameters are The term "expressivity" in this work means the finite-sample expressivity; see Definition in Section [4.]] A major research question regarding expressivity in the area is show deep neural networks have much stronger expressivity than the shallow ones (e.g. 77 17 trainability.
required to memorize finite samples (e.g. [5] 21 25 26 42 75
57 67
70 72) However, all these works neglect the
In the sample case, wide networks (width poly(n)) have both strong representation power (i.e. the globally minimal training error is zero) and strong trainability (e.g. for wide enough nets, Gradient Descent (GD) converges to global minima 16 28 80). While these wide networks are often called "over- parameterrraddd"" we notice that the number of parameters of a width-n network actually at least nd, which much larger than n. If comparing n with the number of parameters (instead of neurons), the transition from maeeiidden-layer fully-connected net (FCN) does not occur at width-n, but at width-n/a d. In this work, we will analyze networks with width in the range [n/d, n)). which we call "narrow networks" (though rigorously speaking, we shall call them "narrow but still overparameterized networks").
and over- parameterization for
There are a few works on the trainability of narrow nets cone-hidden-lle layer networks with m 2 n/d neurons). Soudry and Carmon 63], Xie et al. (71 show that for such networks, stationary points with full-rank NTK (neural tangent kernel) are zero-loss global minima. However, it is not clear whether the NTK stays full rank during the training trajectory. In addition, these two works do not discuss whether zero-loss global minimizer exists.
There two interesting related works p 12]
pointed out by the reviewers. Bubeck et al. 9 study how many neurons are required for memorizing a finite dataset by I-hidden-layer networks. They prove the following results. Their first result is an "existence" result: there exists network with width m 2 4n which can memorize n input-label pairs (their Proposition 4). However, in this setting they did not provide an algorithm to find the zero-loss solution. Their second result is related to algorithms: they proposed a training algorithm that achieves accuracy up to error e for a neural net with width m 2 0 loR(1/e) This result requires width dependent on the precision e; for instance,
d
when the desired accuracy c c 1/n, the required width is at least O (n' In contrast, in our work, the required number of neurons is just 2n/d. which is independent of e.
Daniely [2] also studies the expressivity and trainability of 1-hidden-layer networks. To memorize n11 e) random data points via SGD, their required width is (nn/d). They assumed n = d where > O is fixed constant (appeared in Sec. 3.3 of 1. in which case the hidden factor in Ô is Ollog (d(og d)](). other words, if n. d -> do with the scaling n = de for fixed constant c, then their bound is roughly ((n/d) up to a log- factor. Nevertheless, for more general scaling of n, d, the exponent e = (log n (log d) may not be a constant and the hidden factor may not be a log-factor (e.g. for fixed d and n - oi). We tracked their proof and find that the width bound for general n,, d O (n//d) (log(dlog n)) // lo which can be larger than O (n² (n) (see detailed computation and explanation in Appendix C). In contrast, our required width 2n/d for arbitrary n and d. Our bound is always smaller than when d > 2.
*This result describes the loss landscape of constrained optimization problem, not directly related to algorithm convergence. Nevertheless, it is expected that first-order methods converge to KKT points and thus approximate global minimizers. A rigorous convergence analysis may require verifying extra technical conditions, which is left to future work.
3

---

Additionally, there is a major difference between Daniely [2] and our work: they analyze the original unconstrained problem and SGD; contrast, we analyze a constrained problem. This may be the
reason why we can get stronger bound on width. In the experiments in Section 5 we observe that
SGD performs badly when the width is small (see the stt column in Figure 4 (b)). Therefore, we
suspect an algorithmic change is needed to train narrow nets with such width (due to the training difficulty), and we indeed propose a new method to train narrow nets.
Due to the space constraints, we defer more related works in Appendix B
3 Challenges For Analyzing Narrow Nets
In this section, we discuss why it is challenging to achieve expressivity and trainability together for narrow nets. Consider dataset {(1,, y:) 12d x IR and a I-hidden-layer neural network:
m
f(x; Σ Ujo (w, z) j=1
(1)
where o (w] 2²) is the output of the j-th hidden nodes with hidden weights w.. a()) is the activation function, and By is the corresponding outer weight (bias terms are ignored for simplicity). To learn such a neural network, we search for the optimal parameter 0 = (w, v) by minimizing the following empirical (training) loss:
1
min (())
Σ 1=1
(ye (o;;; 0))²
(2)
2
The gradient of the above problem w.r.t hidden weights w {w, W is given by: Vwe(() J [w;; o)" (ww - y) E m where J(w; E Ruxmd is the Jacobian matrix w.r.t wt
=
V f (w;z1, 1)*
Vio' (wf (wf'x1) 21) of
Uma (wTTx) xa
E C
V (w; Fn,
oro' (wf xn) xh
uma' (whxx)) xo
First order methods like GD converge to a stationary point 0" = -w", v²) (i.e. with zero gradient) under mild conditions (6) For problem (2). it is easy show that if (i) (w" )*) is stationary point, (ii) J (w":e"" E [nxmdd is full row rank and S md, then (w", e²)) is global-min (this claim can be proved by setting the partial gradient of over w to be zero). In other words, for training a network with width m n/d, an important tool is ensure the full-rankness of the Jacobian.
Recent works have shown that is possible to guarantee the full rankness of the Jacobian matrix along the training trajectories, however, the required width is above (ppol((n)). Roughly speaking, the proof sketch is the following: (i) with high probability, J(w;,) v) is non-singular locally around the random initialization (17I), 63 (ii) increasing the width can effectively bound the parameter movement from initialization, so the "nice" property of non-singualr J J(w, v) holds throughout the training. leading to a linear convergence rate [16). Under this general framework, number of convergence results are developed for wide networks with width ((poly(n)) (I 28 34 53
55 80 8.). This idea is also illustrated in Figure (a).
We notice that there huge gap between the necessary condition m 2 n/d and the common condition m 2 (ppoly(n)). We suspect that it is possible to train narrow net with width ((n/d) d) to small loss. To achieve this goal, we need to understand why existing arguments require large width and cannot apply to network with width (n//d).
The first reason is about trainability. The above arguments longer hold when the width is not large enough to control the movement of hidden weights In this case, the iterates may easily travel far away from the initial point and get stuck at some singular- singular-Jacobian Jacobian critical points with high training loss (see Figure (b). Also see Figure (b) & (d) for more empirical evidence). In other words, GD may get stuck at sub-optimal stationary points for narrow nets.
The second reason, and also an easily ignored one, is the expressivity (a.k.a. the representation power, see Definition T for a formal statement). In above discussion, we implicitly assumed that there exists a zero-loss global minimizer, which is equivalent to "there exists a network configuration such that the network can memorize the data", For networks with width at least n, this assumption can be

---

jour traning regime)
(a) Wide networks
(b) Narrow networks
(c) Narrow networks (our regime)
Figure 1: The parameter movement under different regimes. The shaded area indicates the region where (w; v) is non-singular, the black circle denotes the region that GD iterates will explore, and the red circle is the constraint designed in our training regime, it will be discussed in Section 4.3
justified in the following way. The feature matrix
(wi x1) ....., (wma1)
(w)
E 22
(4)
a (wf x..) ,...., (WTTan)
can span the whole space I" when it is full rank and m 2 n. thus the network can perfectly fit any label y E IR" even without training the hidden layer. It is important to note that when the width m below the sample size full row-rande row-rankness does not ensure that the row space of the feature matrix is the whole space RR. In other words, it not clear whether global-min with zero loss exists.
In the next section, we will describe how we obtain strong expressive power with (nn/d) neurons, and how avoid sub-optimal stationary points.
Main Results
4.1 Problem Settings and Preliminaries
We denote ((1,, y:) C TRd x TR as the training samples, where 3; E Rdd Di E R. For theoretical analysis, we focus on I-hidden-layer neural networks ((;;0) Σ5=1 Uga (wy x) E IR, where (-)) is the activation function, wy E IRd and vy E IR are the parameters to be trained. Note that we only consider the case where f(x; f) E R has 1-dimensional output for notation simplicity.
To learn such neural network, we search for the optimal parameter 0 (w, v) by mini- mizing the empirical loss (2). and sometimes we also use f(w; v) or fww; v) to emphasize the role of w. We use the following shorthanded notations: T := i
Roxd
y = (J1...., yn)"" R", w == (Wi,.... Wm )=) Rdxm U == (UI,..., Um) RT. and f(w;)) = (f(x1: w. v), f(zz; w,,,, v)..... f(rn; w. D))T E R". We denote the Jacobian matrix of v(;;)) w.r.t w (ww,)), which
be seen in B). We define the feature matrix ((w) in (4). We denote the operator V. as "taking the gradient w.r.t. w", and the same goes for V.. Throughout the paper, 'w.p.1' is the abbreviation for 'with probability one'; when we say 'in the neighhorhood of initialization' it means "w is in the neighborhood of the initialization w
Now, we formally define the term "expressivity". As discussed in Section we focus on the finite-sample (as opposed to infinite-sample) expressivity, which is relevant in practical training.
Definition 1. (Expressivityy We say a neural net function class F {f 0); θ) has strong (n-sample) expressivity for any input-outpul pairs D {(I;, 9:) C Rd x R where x; 's are distinct, there exists (D) ④ such that f(z D(D) = yı, 1,... n. Or equivalently, the optimal value of empirical loss equals for any D. Sometimes we may drop the word "strong" for brevity.
Next, let us describe the mirrored LeCun's 's initialization Algorithm The idea is that through this initialization, the hidden outputs will cancel out with the outer weights, so that we get zero initial output for any input æ; see Fig- ure for simple illustration. Note that similar symmetric initialization strategies are also proposed in some recent works such as [11] and [2]. However, our purpose is dif- ferent. More explanation can be seen the final paragraph
Figure 2: A simple example of the mir- rored LeCun's initialization.
of Section 4.2
5

---

Algorithm The mirrored LeCun's 's initialization
1: Initialize all the weights using LeCun's initialization: why ~ NO0, 2), ug N(0, :.), for
i == l..... . j = L.....d.
2: Set (++1 wnn + (...... w ). and set (v +1 u t (-2 r
Throughout the paper, will make the following assumptions.
Assumption 1. For (x; 0) in 4 we assume its width is an even number, and 2 2m. Assumption 2. We assume the activation fanction a()) IR + IR is analytic and L-lipschitz continu- ous, its zero set only contains 0: {z]o(z) =0 = [0]. In addition, there are infinitely many non-zero coefficients in the Taylor expansion of (-).
d'
Assumption 3. 21,""' Bn are independently sampled from a continuous distribution in Rd..
When d 2, Assumption I can be applied to narrow networks with m < n. Assumption 2 covers many commonly used activation functions such as sigmoid, softplus, and Tanh, but it does not cover ReLU since is nonsmooth.
4.2 Expressivity Analysis
In this section, we prove that narrow neural networks (which are still wer-pprramterizze) have strong expressivity. Further, the zero-training- eeroor solution is surrounded by good landscape with no local-min or saddles, which motivates our trainability analysis in the following sections.
Theorem 1. Suppose Assumption !
2 and 3 holds. If the neural network f(;; 0) =
Σ uya (wf x)) is initialized at the mirrored LeCun's initialization given Algorithm 7 with 00= (w", v²), then there exists > 0 such that for any S ED, there exists w E (.(w") {w
m| w S c} and entry-wise non-zero v, such that with probabilty of choosing {I y/s 1= and fo the output of f will be exactly the groundtruth label:
f(z;; 0) Σ uo xz)) = yy.i
(5)
j=1
In addition, every stationary point 0* (w", ,²)) (i.e., the gradient is zero) is a global-min of (2) with zero loss if satisfies w" E (ww")) and v² is entry-wise non-zero.
Remark 1. Theorem D Tempasiizes the role of hidden weights of neural network: it is a key
ingredient for strong expressivity. When m < n. if we fix all the w = w the range space of the feature matrix ((w") does not cover the whole R" space, so there always exists a label y, such that no v" can be found that perfectly maps the input to However, a small tolerance of the movement of will let (>; 0) perfectly fit any input-label pair, the movement of is vitally important. The free perturbation of w serves as an effective remedy against the limited expressivity.
We emphasize that Theorem [ holds for "any small enough e" instead of "any e". Therefore, Theorem Only states "there is spurious local-min" locally. It is still possible that on the global landscape results there "exists bad local-min" (e.g. Ding et al. [14).
Remark 2.
We comment a bit more on the maximum required size of c. In our proof in Appendix F. it should not exceed the the radius of the region where the Jacobian J/ (w: v) stays full-rank (the yellow-shaded area in Figure I. To briefly summarize, the maximum radius is (linearly) proportional to the minimum singular value of the initial Jacobian J Jw=:; o Technical details on the size of this radius can be seen in [18] Remark 4.1].
Proof sketch. Theorem consists of two arguments: (i) there exists a global-min with zero loss, (ii) in the neighborhood of initialization, every stationary point is global-min. A detailed proof is relegated to Appendix E We outline the main idea below.
'When d' = 1, all our results still hold; nevertheless, the required width m 2 n, 2n, thus it does not belong to the "narrow" setting defined earlier in Section 2 (which requires E [n/d, n)).

---

To argue (i). the key idea is to use the Inverse Function Theorem (IFT), which is stated in Appendix E. According to IFT, as long as an n x n submatrix of [[w"; e²) invertible, then for any y E F and any small enough there exists a w" E Bc(")) whose prediction output f'w";; v0) xx y sw"; :.)). Additionally, since I [w"":0 = 0. we have f(w"; ; r0) x y. Once this is shown, then we just need to scale all the outer weight by uniformly and the output will be exactly since f'w"; v) is linear in v.
To argue (ii, recall that all the stationary points 0" Jww;; e* (f(("""" =*) - y) 0. Therefore, if J" (w="""""" v²) <mddx is of full column rank, the stationary point 0* = (w", (w")
(w* ; u²) satisty V.)((0))
) is a global minimizer with E(0*) = O. The desired full-rankness condition is true because: (i) [u is full rank w.p.1 initialization, (ii) w" will not leave the
small neighhorhood B, (ww),, ), so the dynamics of w stays inside the manifold of full-rank Jacobian.
L
The proof of Theorem relies on the full-rankness of the Jacobian matrix. We note that such full-rankness holds for both the mirrored and the regular LeCun's initialization (the case for the regular one can be proved using the same technique). So why do we insist on shifting the initial output to 0? Simply put, the "randomness of weights" contributes to the "full-rankness", while the "shifting' allows us to gain local representation power by applying IFT properly. To be more specific, f(wo, )²) 0 e R" is important because it is surrounded by all possible directions pointed from 0 E R" so for any y E R", IFT claims that there exists at least one w' E Be (w²), s.t. fw""; ed) y f(w"; e = y, therefore, fw="; =*) can perfectly match y by scaling vd with some constant (Figure 3 a) illustrates this case when n = 2).
In contrast, if we use IFT around regular LeCun's 's initialization, the existence of f(w2; v0) on the right hand side resists us from scaling 6º like before (Figure (/b illustrates this case). As such, Theorem | does not hold for any small around the regular initialization. This is also revealed in our experiments in Section 5.1 training fails we only search around the regular LeCun's initialization.
(l ocy
(a) The mirrored LeCun's 's initialization
(b) Regular LeCun's 's initialization
Figure 3: Examples of using Inverse Function Theorem (IFT) under different initialization strategies. The illustration here is for n = 2. For (a), scaling o will directly lead to zero loss, while it is not true for (b) due to the non-zero f(w","")
The idea of zero initial output is also used in other recent works in Table 1 Despite the similar design, they use such an initialization for different purposes. In NTK regime, zero initial output helps eliminate the bias term and simplify the proof (3I 23 24 34 and [12). Nguyen [49] also uses zero initial output, but their initialization is very different in that all the hidden layers will have high values while the last layer is assigned to O. In this way, they manage to limit the movement of hidden layers without increasing the width. To our knowledge, this is the first time that the zero initial output has been linked to Inverse Function Theorem, by which the strong expressivity of a narrow neural network can be identified.
Table I: Comparison of recent works considering zero initial output.
Work
Width
Motivation
23
24
34
ML-1-
To avoid handling the bias term in the NTK regime
Ö(n/d)
To avoid handling the bias term in the NTK regime
49
m 1 = ((n)
To ensure linear convergence via imbalanced weight
Ours
0 (②)
To achieve strong expressivity via Inverse Function Theorem
7

---

4.3 Trainability Analysis
Despite the expressivity and good local properties stated in Theorem | in practical training, the weights can easily escape the nice neighborhood, especially when the width is not sufficiently large. To keep the hidden weights inside this nice region, an intuitive idea is to impose an explicit constraint, but it may suffer from bad local-min on the boundary with very large loss [6]. This is supported by our experiments in Section [ Figure 4
(b): when we add the wolden-weighh constraint directly to the regular training regime (1.c., let w|w 10 I e), it fails to find a low-cost solution when and width become small.
In this sense, we need to design constrained problem, such that all the KKT points will have small training loss, including those on the boundary. Fortunately, Theorem suggests one such formulation. Recall in the proof of Theorem [ we construct a zero-loss global-min by scaling va so v* still follows the pairwise-opposite pattern. Inspired by this, we consider the following neural network (we abuse the notation of (x; 0), (a; w. v) and (U1:-..,, Vzg m here):
m
[z; = Σ My (o(wf - o(w s4 x)) ,=1
(6)
Note that the optimization variable for the outer layer is only v = (U1..... , Um and the rest of the outer weights are automatically set to be -v. Despite the change of Theorem still applies since it
does not have any specific requirement on v. We then use (6) to formulate the following problem 77
min (())
(ys - f(a;;))) s.t.
w B. v EE (xn(v)
1=1
where fax;; 0) is in the form of 6
(w == [w [ - w w c)
(v) == [w 22 (1 and 0s/0y S K. KK (.. .m., where <> O, K < oo.).
Here, < > 0 is small constant that keeps the entries of away from zero, which is an essential
requirement of Theorem [ The requirement of /uy S K < oo allows all entries of be uniformly large, but it rules out the case when some entries are much larger than others. Instead of regarding all these requirements of (vv) as prior assumptions, we formulate them into the constraints in the problem, so all the iterates in the practical training algorithm will strictly follow these requirements. In Theorem 2 we show that every KKT point of problem 7 implies the near-global optimality for the unconstrained training problem 2).
Theorem 2. Suppose Assumption and hold and assume @ = =w",, =0) as given in Algorithm i Then every KKT point 6* = (w" of is approximate global-min w.p.I., that is:
E(w". v = =(2)
(8)
The proof of Theorem is based on the special structure of neural network fax; 9). including the linear dependence of u and the mirrored pattern of parameters. To better illustrate our proof idea, we provide user-friendly proof sketch in Appendix ET Detailed proof can be seen in Appendix [22
Theorem 2 motivates a training method to reach small loss. We highlight three new ingredients that is not used in regular neural net training: the mirrored initialization, the pairwise structure of v in (7). and the constrained parameter movement. Combining these elements with Projected Gradient Descent (PGD), propose new training regime in Algorithm 2 in Appendix H.I Thorough numerical results are provided in the following sections to demonstrate the efficacy of Algorithm
4.4 Discussion: Extension to Deep Networks
In the previous sections, we analyze the trainability and expressivity of narrow I-hidden-layer networks. We find it possible to extend the previous analysis to deep nets, and we already have some preliminary results. Due to space constraints, more relevant discussions are deferred Appendix G
Experiments
In this section, we provide empirical validation for our theory. Specifically, we compare the perfor- mance of two training regimes d
'We call it "training regime" instead of "training method" since we use a different formulation as well a different algorithm compared to standard SGD.
8

---

(1) Our training regime: we optimize a constrained problem 7 by using PGD (projected gradient descent), starting from the mirrored LeCun's 's initialization. (See Algorithm in Appendix H.II)
(2) Regular training regime: optimize an unconstrained problem starting from LeCun's 's initialization.
2 by using GD-based methods,
all KKT points in our training regime have small empirical loss. To reach such KKT points, use Projected Gradient Descent (PGD) (see Bertsekas [6]. Even though we do not provide convergence analysis, PGD can, empirically, converge to KKT point with proper choice of stepsize. We outline the proposed training regime in Algorithm 2 in Appendix H.. To briefly summarize, there are three key ingredients in Algorithm 2 the mirrored initialization; the pairwise structure of in (7) and the PGD algorithm. Each of these changes only involves a few lines of code changes based on the regular training. We demonstrate the PyTorch implementation of these changes in Appendix H.T
Main ingredients of our algorithm. As shown in Theorem 2
Better training and test error. To evaluate our theory in terms of training error, we conduct experiments synthetic dataset (shown in Section 5.1) and random-labeled CIFAR-10 10 [1 (shown in appendix H.6). We further observe the strong generalization power of Algorithm 2 even though is not yet revealed in our theory. Our training regime brings higher competitive test accuracy on
(Restricted) ImageNet [58] (shown in Section 3.2). MNIST [33]. CIFAR-10 10, CIFAR-100
31] (shown
in Appendix HH) Detailed experimental setup are explained in Appendix H.2
As side note, for all the experiments in our training regime, we observe that v never touches the boundary of Bc,x(1) when = 1,5 0.001. So we can regard problem 7 as unconstrained problem for v, and PGD only projects the hidden weights w into B. (ww). When 1000, problem (7) degenerates into an unconstrained problem (but still different from the regular training due the changes in the structure of v and initialization).
5.1 Training Error on The Synthetic Dataset
On the synthetic regression dataset, we train 1 I-hidden-layer networks under different widths and different training settings, the final training errors are shown in Figure 4 We explain as follows.
010
-00
6050
1200 928 900
(a) Our training regime
(b) Regular training
2000
(d) Amin Amin (J(w"; ")in regular training regime Figure 4: Synthetic data: training losses and ) x²)) in different width & hidden-weight
(c) Amia (J(n" :o" ))in our training regime
constraint size c.
As for our training regime, we try different -eedht constraint size e, these results can be seen in Figure 4 (a). Accordingly, the performance of the regular training regime can be seen in the 1st column in Figure (b). argued above, e 1000 degenerates PGD into unconstrained GD, so this column shows the results for regular training regime. As for the rest of the columns in the Figure 4

---

(b), we try to investigate an ablation study: "What will happen if we directly add constraint B. (ww)) on w, and use PGD without any modification of the initialization & network structure?" In each block in Figure 4 grid search of step-size is performed to ensure the convergence of algorithms. The key messages from this set of experiments are summarized as follows.
First, our training regime performs well regardless of width, yet regular unconstrained training fails when the network is narrow (Ist column in Figure (b)).
Second, it does not work when we directly impose the weight constraint of (7 on the regular training regime (and PGD is used accordingly), as it fails to find low-cost solution when and width become small. There are two possible causes: perhaps there is no global-min inside the ball, or converges to bad loi on the boundary. In contrast, solution with any choice of 6. Therefore, we suggest not to directly add constraint and use PGD. Instead, when using PGD, it is better utilize the mirrored initialization & the pairwise structure of v in (see Figure (a)).
training regime always finds a low-cost
Furthermore, Figure 4 (c) & (d) depict Amin (J=n([(w"; ;"");"")))) i.e. the minimum singular value of the Jacobian at the stationary (or KKT) points. As expected in Section when the width is small, regular 1, 000) has trouble controlling the parameter movement, and it is likely to
training regime (when get trapped at a stationary point with a singular Jacobian matrix, leading to a large loss despite the convergence. However, this is not an issue in our training regime.
5.2 Test Accuracy R-ImageNet
We check the test accuracy (not just the train- ing accuracy) of the proposed method on R(Restricted))Imageel
([58)). ). R- R-ImageNet is
subset of ImageNet with resolution 224x224,
and it is widely used in various papers (e.g. [68]. (77). Detailed description can be found Ap- pendix H.2 In both training regimes, experi- ments are conducted on ResNet-18 18 [22]. which contains 4 CNN blocks and 1 fully connected output layer. To compare the performance un- der different widths, shrink the number of channels in the final CNN block gradually from 512 to 64 (note that we will call "the number of channels" as the "width" in CNN, this is a straightforward extension of the width in FCN). In our training regime, we apply all the con- straints in problem (7) to the final CNN block & the output layer.
26.0
85.
85.0
86.5
C=0.1
0.05
840
0.04
83.5
triiiin
512
256
128
64
Wich
Figure 5: R-ImageNet: test accuracy under our training regime with different vs regular training regime. In x-axis, width stands for the number of channels in the final CNN block of ResNet-18. 18. These results are averaged over 5 seeds.
There are two messages shown in Figure 5 First, training regime outperforms regular training when using the standard ResNet-18 (i.c., width 512 in the final CNN block). Second, our training regime in the most narrow setting (width 64) performs quite close to the standard case (width 512). In comparison, regular SGD does not perform well the narrow setting. More theoretical analysis on the generalization power will be considered our future work.
Conclusion
In this work, we shed new light on both the expressivity and trainability of narrow networks. Despite the limited number of neurons, we prove that the network can memorize n samples, and it can be provably trained approximately zero loss in training regime. We notice some interesting questions by reviewers and colleagues. We provide further discussion on these questions in Appendix they may be intriguing for general readers.
Finally, there are several important future directions. First, we empirically observe that our training regime brings strong generalization power, more theoretical analysis will be interesting. Second, our current analysis is still limited to I-hidden-layer networks, we are trying to extend it to deep ones. Third, the algorithmic convergence analysis to reach the KKT point is imperative.
10

---

Acknowledgments and Disclosure of Funding
We would like to thank Dawei Li for valuable and productive discussions. We want to thank the anonymous reviewers for their valuable suggestions and comments. We would also like to express our gratitude Zeyu Qin, Jiancong Xiao and Congliang Chen for the support of R-ImageNet and CIFAR experiments. M. Hong is partially supported by an NSF grant CMMI-1727757, and an IBM Faculty Research Award. The work Z.-Q. Luo supported by the National Natural Science Foundation of China (No. 61731018) and the Guangdong Provincial Key Laboratory of Big Data Computation Theories and Methods.
References
[1] Zeyuan Allen-Zhu. Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via wer-paraaeterization. In International Conference on Machine Learning, pages 242-252. PMLR, 2019.
[2] Peter Auer, Mark Herbster, Manfred K Warmuth, al. Exponentially many local minima for single neurons. Advances in neural information processing systems, pages 316-322, 1996.
[3] Yu Bai and Jason D Lee. Beyond linearization: quadratic and higher-order approximation of wide neural networks. arXiv preprint arXiv:1910.01619 2019.
[4] Andrew R Barron. Universal approximation bounds for superpositions of sigmoidal function. IEEE Transactions on Information theory. 39(3):930-945, 1993.
[5] Eric B Baum. On the capabilities of multilayer perceptrons. Journal of complexity, 4(3):193-2155 1988.
[6] Dimitri P Bertsekas. Nonlinear programming. Journal of the Operational Research Society, 48(3):334-334, 1997.
[7] Monica Bianchini and Franco Scarselli. On the complexity of neural network classifiers: A comparison between shallow and deep architectures. IEEE transactions on neural networks and learning systems, 25(9)11553-1555 2014.
[8] Tom B Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models few-shot learners. arXiv preprint arXiv:2005. /4/65, 2020.
[9] Sébastien Bubeck, Ronen Eldan, Yin Tat Lee, and Dan Mikulincer. Network size and weights size for memorization with two-layers neural networks. arXiv preprint (xXii:20060028555 2020.
[10] Zixiang Chen, Yuan Cao, Difan Zou, and Quanquan Gu. How much over pareraattattiiiiaioonnn is sufficient learn deep relu networks? arXiv preprint 1911.v9111.12360 2019.
[11] Lenaic Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable program- ming. arXiv preprint arXiv: /812.0795, 2018.
[12] Amit Daniely. Neural networks learning and memorization with (almost) no over- parameterization. arXiv preprint arXiv: 1et119991199.. 2019.
[13] Olivier Delalleau and Yoshua Bengio. Shallow vs. deep sum sum-product networks. Advances in neural information processing systems, 24:666-674, 2011.
[14] Tian Ding, Dawei Li, and Ruoyu Sun. Sub-optimal local minima exist for almost all over- parameterized neural networks. arXiv preprint arXiv: urXiv::91// /et//99911.,33 2019.
[15] Tian Ding, Dawei Li, and Ruoyu Sun. Sub-optimal local minima exist for neural networks with almost all non-linear activations. arXiv preprint arXiv: /91 1.01413, 2019.
[16] Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In International Conference on Machine Learning, pages 1675-1685, PMLR, 2019.
[17] Ronen Eldan and Ohad Shamir. The power of depth for feedforward neural networks. In Conference learning theory, pages 907-940. PMLR, 2016.
[18] Kai-Seng Chou et. al. Chapter 4: Inverse function theorem. https://xww.nanr math. cuhk edu. www.hkccuuree builder/1415mmtthie http://wwwppppooe/eo////oooo//ta
20Theorem, pdf 2015.

---

[19] C Daniel Freeman and Joan Bruna. Topology and geometry of half-rectified network optimiza- tion. arXiv preprint arXiv:1611.01540 2016.
[20] Song Han, Huizi Mao, and William Dally. Deep compression: Compressing deep neural net- works with pruning, trained quantization and huffman coding. arXiv preprint arXiv:1510.00144 2015.
[21] Boris Hanin and David Rolnick. Complexity of linear regions deep networks, In International Conference on Machine Learning, pages 2596-2604. PMLR, 2019.
[22] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition. pages 770-778, 2016.
[23] Wei Hu, Zhiyuan Li, and Dingli Yu. Simple and effective regularization methods for training on noisily labeled data with generalization guarantee. arXiv preprint arXiv: 113699 2019.
[24] Wei Hu, Lechao Xiao, Ben Adlam, and Jeffrey Pennington. The surprising simplicity of the early-time learning dynamics of neural networks. arXiv preprint arXiv:2006, (tfi::2000..1559, 2020.
[25] Guang-Bin Huang. Learning capability and storage capacity of two-hidden-layer feedforward networks. IEEE transactions on neural networks, 14(2):274-281, 2003.
[26] Guang-Bin Huang and Haroon A Babri. Upper bounds on the number of hidden neurons in feedforward networks with arbitrary bounded nonlinear activation functions. IEEE transactions on neural networks, 91):224-2 1998.
[27] Nathan Inkawhich, Kevin J Liang, Binghui Wang. Matthew Inkawhich, Lawrence Carin, and Yiran Chen. Perturbing across the feature hierarchy to improve standard and strict blackbox attack transferability. arXiv preprint arXiv:2004. 14861, 2020.
[28] Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. arXiv preprint arXiv: 1806.07572 2018.
[29] Ziwei Ji and Matus Telgarsky. Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test enror with shallow relu networks. arXiv preprint arXiv: 12292, 2019.
[30] Kenji Kawaguchi. Deep learning without poor local minima. In Advances in neural information processing systems, pages 586-594, 2016.
[31] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[32] Thomas Laurent and James Brecht. Deep linear networks with arbitrary loss: All local minima are global. In International Conference on Machine Learning, pages 2908-2913, 2018.
[33] Yann LeCun, Corinna Cortes, and CJ Burges. Mnist handwritten digit database. ATT Labs [Online]. Available: http://yann.lecun.cc www.ee/...o/eee///nniiiiiii 2, 2010.
[34] Jachoon Lee, Lechao Xiao, Samuel S Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl-Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. arXiv preprint arXiv: 1902.0670,, 2019.
[35] Dawei Li, Tian Ding, and Ruoyu Sun. On the benefit of width for neural networks: Disappear- ance of bad basins. arXiv preprint arXiv: 1039, 2018
[36] Dawei Li, Tian Ding, and Ruoyu Sun. On the benefit of width for neural networks: Disappear- ance of bad basins, 2021.
[37] Shiyu Liang, Ruoyu Sun, Jason D Lee, and R Srikant. Adding one neuron can eliminate all bad local minima. In Advances in Neural Information Processing Systems, pages 4355-4365, 2018.
[38] SHIYU LIANG, Ruoyu Sun, Yixuan Li, and Rayadurgam Srikant. Understanding the loss surface of neural networks for binary classification. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages
PMLR, 10-15 Jul 2018.
[39] Shiyu Liang, Ruoyu Sun, and R. Srikant. Revisiting landscape analysis in deep neural networks: Eliminating decreasing paths to infinity, 2019.
[40] Shiyu Liang, Ruoyu Sun, and R. Srikant. Achieving small test error in mildly overparameterized neural networks. CoRR, Abs/2104.11899 2021.
12

---

[41] Henry W Lin, Max Tegmark, and David Rolnick. Why does deep and cheap learning work so well? Journal of Statistical Physics, 12241 2017.
[42] Roi Livni, Shai Shalev-Shwartz, and Ohad Shamir. On the computational efficiency of training neural networks. arXiv preprint arXiv: 2014.
[43] Ilya Loshchilov and Frank Hutter. Sgdr: Stochastic gradient descent with warm restarts. arXiv preprini arXiv: 1608.03883, 2016.
[44] Haihao Lu and Kenji Kawaguchi. Depth creates no bad local minima. arXiv preprint
wwXiv:1702.085880 2017.
[45] Zhou Lu, Hongming Pu, Feicheng Wang, Zhiqiang Hu, and Liwei Wang. The expressive power of neural networks: A view from the width. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pages 6232 6240, 2017.
[46] George A Miller. WordNet: An electronic lexical database. MIT press, 1998.
[47] Boris Mityagin. The zero set of a real analytic function. arXiv preprint arXiv: urXiv:1512.07276 2015.
[48] Guido Montúfar, Razvan Pascanu, Kyunghyun Cho, and Yoshua Bengio. On the number of linear regions of deep neural networks. arXiv preprint urXiv:14022 1809, 2014.
[49] Quynh Nguyen. On the proof of global convergence of gradient descent for deep relu networks with linear widths. arXiv preprint arXiv:2101.09612 2021.
[50] Quynh Nguyen, Mahesh Chandra Mukkamala, and Matthias Hein. On the loss landscape of class of deep neural networks with no bad local valleys. arXiv preprint 1rXiv:1809.10744 2018.
[51] Atsushi Nitanda, Geoffrey Chinot, and Taiji Suzuki. Gradient descent can learn less over-paramettriize two-layer neural networks on classification problems. arXiv preprint arXiv:1905.09870 2019.
[52] Maher Nouiehed and Meisam Razaviyayn. Learning deep models: Critical points and local openness. arXiv preprint lee::::030000 2018.
[53] Asaf Noy, Yi Xu, Yonathan Aflalo, Lihi Manor, and Rong Jin. A convergence theory towards practical over-parameterized deep neural networks. arXiv preprint arXtv:2101.04243 2021.
[54] Samet Oymak and Mahdi Soltanolkotabi. Overparameterrzee nonlinear learning: Gradient descent takes the shortest path? In International Conference on Machine Learning, pages 4951-4960. PMLR, 2019.
[55] Samet Oymak and Mahdi Soltanolkotabi. Toward moderate overparamettriizatoo:: Global convergence guarantees for training shallow neural networks. IEEE Journal on Selected Areas in Information Theory, 1(1):44-055, 2020.
[56] Sejun Park, Jaeho Lee, Chulhee Yun, and Jinwoo Shin. Provable memorization via deep neural networks using sub-linear parameters. arXiv preprint arXiv:2010.13363 2020.
[57] David Rolnick and Max Tegmark. The power of deeper networks for expressing natural functions. arXiv preprint arXiv: 170.05500, 2017.
[58) Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, al. Imagenet large scale visual recognition challenge. International journal of computer vision, 1 11((3):11 2015.
[59] Itay Safran and Ohad Shamir. On the quality the initial basin overspecified neural networks. In International Conference on Machine Learning, pages 774-782. PMLR, 2016.
[60] Itay Safran and Ohad Shamir. Depth- tradeoffs in approximating natural functions with neural networks. In International Conference on Machine Learning, pages 2979-2987. PMLR, 2017.
[61] Itay Safran and Ohad Shamir. Spurious local minima are common in two-layer relu neural networks. arXiv preprint arXiv: 1712008968 2017.
[62] Mahdi Soltanolkotabi, Adel Javanmard, and Jason D Lee. Theoretical insights into the op- timization landscape of over-parameterizzd shallow neural networks. IEEE Transactions on Information Theory, 65(2):742-769, 2019.
13

---

[63] Daniel Soudry and Yair Carmon. No bad local minima: Data independent training error guarantees for multilayer neural networks. arXiv preprint arXiv: 1605.v:605.080 6066000666,,, 2016.
[64] Ruo-Yu Yu Sun. Optimization for deep learning: An overview. Journal of the Operations Research Society of China, pages 1-46, 2020.
[65] Ruoyu Sun, Dawei Li, Shiyu Liang, Tian Ding, and Rayadurgam Srikant. The global landscape of neural networks: An overview. IEEE Signal Processing Magazine, 37(5):95-108 108, 2020.
[66] Grzegorz Swirszez, Wojciech Marian Czarnecki, and Razvan Pascanu. Local minima in training of deep networks. 2016.
[67] Matus Telgarsky. Benefits of depth in neural networks. In Conference on learning theory, pages 1517-1539. PMLR, 2016.
[68] Dimitris Tsipaas, Shibani Santurkar, Logan Engstrom, Alexander Turner, and Aleksander Madry. Robustness may be at odds with accuracy. arXiv preprint 1rXiv:180../1:: 2018.
[69] Luca Venturi, Afonso Bandeira, and Joan Bruna. Spurious valleys in two-layer neural network optimization landscapes. arXiv preprint arXiv: 0002.8002.6688 2018.
[70] Roman Vershynin. Memory capacity of neural networks with threshold and rectified linear unit activations. SIAM Journal on Mathematics of Data Science, 100: 2020.
[71] Bo Xie, Yingyu Liang, and Le Song. Diverse neural network learns true target functions. In Artificial Intelligence and Statisties, pages 1216-1224. PMLR, 2017.
[72] Chulhee Yun, Suvrit Sra, and Ali Jadbabaie. Small nonlinearities in activation functions create bad local minima in neural networks. arXiv preprint arXiv: 1802.83087..77 2018.
[73] Chulhee Yun, Suvrit Sra, and Ali Jadbabaie. Small ReLU networks are powerful memorizers: tight analysis of memorization capacity. arXiv preprint urXiv:/810.077700 2018.
[74] Sergey Zagoruyko and Nikos Komodakis. 1rX1v:1605.07146, 2016.
Wide residual networks.
arXiv preprint
[75] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64 115, 2021.
[76] Li Zhang. Depth creates no more spurious local minima. arXiv preprint 2019.
[77] Aojun Zhou, Anbang Yao, Yiwen Guo, Lin Xu, and Yurong Chen. Incremental network quanti-
zation: Towards lossless cnns with low- low-precision weights. arXiv preprint arXiv:1702.0304 2017.
[78] Mo Zhou, Rong Ge, and Chi Jin. A local convergence theory for mildly over-parameterizee two-layer neural network. arXiv preprint urXiv:2 102.02100, 2021.
[79] Yi Zhou and Yingbin Liang. Critical points of neural networks: Analytical forms and landscape properties. arXiv preprint arXiv:1710. 1205,, 2017.
[80] Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Stochastic gradient descent optimizes wwer-parameterized deep relu networks. arxiv e-prints, art. arXiv preprint arXiv: 181 11111111000000 1.08888, 2018.
[81] Difan Zou and Quanquan Gu. An improved analysis of training over-parameterized deep neural networks. arXiv preprint arXiv:1906.0466 2019.
14


Reviews:
[{"review_id": "lmZCCmg2lVz", "reviewer": "Reviewer_xfuA", "summary": "This paper studies the expressivity and trainability of two-layer (one-hidden-layer) neural networks with the number $m$ of neurons fewer than the number $n$ of samples. Specifically, it is shown that if $m\\geq 2n/d$, then with probability one, there exists at least one global minimum with zero training loss. Moreover, there is no local minimum or saddle around such global minimum. The authors also proposed a constrained minimization problem whose KKT condition implies the near global optimality for the unconstrained problem. Numerical tests show that the proposed training regime performs better than the regular training regime. ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "The paper does an excellent job in analyzing the expressivity and trainability of shallow neural networks in the regime that the network width is fewer than the sample size. The results presented in the paper complements the recent theoretical studies on the convergence of neural network training in the overparameterized regime (e.g. Neural Tangent Kernel regime).  From my perspective, the paper is among the top 30% of all submissions. I only have the following minor comments. \n\n*My major comment is about the generalization. The main results claim that there exists a shall neural network that attains zero empirical loss, but the generalization performance of such network was not discussed. To guarantee a zero loss, the parameters $v$ are used to scale the initial value $v_0$ to match the output $y$. It is possible that $v$ can be extremely large depending on the values of $v_0$ and $y$. Large values of $v$ may induce large generalization error. In Section 3.3, the author rules out the large values of $v$ by requiring that the ratio of $v_i$s are bounded by $\\kappa$. However, I do not see how large $\\kappa$ is and how the final convergence guarantee (equation 6) depends on $\\kappa$. It would be nice if the authors could make this more precise. \n*The main results were proved for analytical activation functions. Can the authors comment on to which extent the result can be extended to non-smooth activations, such as ReLU or powers of ReLU?\n*Some important relevant references on convergence of GD for shall networks are missing:\n\n[1] S. Oymak and M. Soltanolkotabi, Toward moderate overparameterization: Global convergence guarantees for training shallow neural networks, IEEE Journal on Selected Areas in Information Theory 1 (1), 84-105\n\n[2] S. Oymak and M. Soltanolkotabi, Overparameterized nonlinear learning: Gradient descent takes the shortest path?, ICML 2019.\n\nAfter receiving the feedbacks of the other reviewers, I find that the paper share substantial similarities to some earlier works. I have now changed score. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"ethical_concerns": "none", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "48 hours"}, "extra_text": {}}, {"review_id": "YimzNjyIYhM", "reviewer": "Reviewer_wktj", "summary": "The paper studies the expressivity and trainability of shallow 2-layer neural networks. First, in terms of expressivity it is shown, under certain assumptions, that for a 2-layer network, it is enough to have 2n/d neurons to memorize n data points in d dimensions. In addition, it is shown that in the close neighborhood of the initialization, every stationary point w.p 1 is a global minimum. Next, it is shown that for a certain constraint setting, every KKT point is an approximated global minimum. Finally, several experiments are shown to validate the theoretical results.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "I think the questions of how many neurons are required for memorization, and whether neural networks actually converge to a global minimum are very interesting. On the other hand, there are two major issues that significantly impair the contribution and novelty of this paper:\n\n1) There are already several papers showing that only O(n/d) neurons are required for memorizing n data points in d dimensions, which are not mentioned in this paper (e.g. see Daniely 2019 https://arxiv.org/abs/1911.09873, Bubeck et al. 2020 https://arxiv.org/abs/2006.02855, and the references therein). In Bubeck et al. the authors also show a convergence result to the global minimum. In light of this, it is very hard to evaluate the novelty of this paper. I suggest the author to cite these papers and highlight the novel part of their work. Specifically, why the results here are different from previous results which also show similar memorization and convergence guarantees.\n\n2) There is a major issue with the proofs. In Theorem 1 the authors claim to show that “every stationary point \\theta^* is a global min…”. On the other hand, in the proofs, the authors show something completely different. Namely, that w.p 1 over the initialization, the Jacobian of the loss is invertible. Next, it is shown that outside of a manifold of zero measure (where the Jacobian is not invertible) there are no bad global minima or saddle points. I don’t see how this theorem is helpful since there still might be many bad local minima close to the initialization. Even a single bad local minimum (which as a single point has measure zero) can be disastrous for the optimization process. From my understanding, what the authors actually show is that all the bad local minima and saddle points are located in a zero-measure manifold where the Jacobian is not invertible. This in itself is not surprising, and I don’t currently see how this observation can help with analyzing the optimization process.\n\nThis issue persists to Theorem 2, where the authors show that under certain constraints every KKT point w.p 1 is an approximated global minimum. Again, in the proof, the authors seem to assume that the only bad local minima are in the boundary. On the other hand, for any \\epsilon >0 there can be bad global minima in the interior of the considered set. \n\nIn order to claim that the only bad local minima are in the boundary of the constraint set, the authors should prove that either (1) The Jacobian is invertible at *all* the points of this set. Not w.p 1, or outside of a zero measure set as even a single bad local minima ruin this argument; or (2) That if the Jacobian is not invertible at some point inside this set, then this point is not a bad local minimum (or saddle point). The fact that the set of bad local minima is of measure zero does not say anything about whether GD will converge to these points. \n\n\nThe experimental part is nice, and many datasets are considered. To further improve it, I suggest also conducting experiments on these datasets but with randomized labels. Since the claim of the paper is about memorization of *any* labels, a more convincing experimental argument is that even when the labels are not the correct ones, neural networks with sufficient width can memorize them (this flavor of experiments also appears in Zhang et al. 2017). Also, the text in figure 5 (and also other figures) is very small and makes it difficult to read.\n\nTo conclude, the paper studies an interesting question, but there are major issues that make it difficult to assess the contribution of the paper. I will be happy to see the author’s response and will consider changing my score accordingly.\n\n\n----------------------------Post rebuttal comment----------------------------\n\nI thank the authors for their feedback. After reading the author's response and rereading the proof in their paper I decided to raise my score to 6. Here are my explanations:\n\nRegarding my second remark about the correctness of their proof. I was admittingly mistaken and I am now convinced that what I thought was wrong is actually true. So, I drop my second claim. The proof seems sound.\n\nRegarding the similarity to Daniely's and Bubeck et al. papers. I agree that there are differences between the current paper and these two papers, both in the results and techniques. On the other hand, all three papers essentially claim the same thing - memorization using O(n/d) parameters and *some* optimization guarantees of convergence to a global minimum. I think the authors should have done a better job comparing their work to previous works, probably dedicating a paragraph/subsection to the comparison to these two papers.\n\nFor this reason, I think this paper is only slightly above the threshold.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors adequately addressed the limitations and potential negative societal impact of their work", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "YiRIUJ15PaX", "reviewer": "Reviewer_Ep5m", "summary": "Recent theoretical analysis on two-layer neural networks usually assumes the number of hidden neurons to be larger than the number of training samples so that the model could fit the data perfectly. This paper works on scenarios where the number of hidden neurons is smaller than the training samples. Clearly the small number of hidden neurons makes it harder to fit the data perfectly. Also some nice properties of the over-parameterized neural networks are missing, making it harder to prove guarantees on the optimization procedures. \n\nThe authors prove that for two layer neural networks even when the hidden neuron number is smaller than n it can still fit the data, demonstrating the expressivity of the two-layer network compared to the single layer network. The authors also propose a constrained optimization procedure with a new initialization method so that the global optimality is guaranteed. \n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "Analysis on limited width neural networks is in general scarce. Even though the analysis is still limited to two layer networks with quadratic loss, this work is making progress towards understanding the ``deep” models in terms of expressivity and optimum. \n\nJust one question about the wording in Theorem 1: in line 130 should the ‘’for any small neighborhood” be ‘’there exists a small neighborhood” instead? I believe the Implicit Function Theorem is saying “ there exists a small neighborhood”. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "the authors adequately addressed the limitations and potential negative societal impact of their work", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "WUNWIbzlwY", "reviewer": "Reviewer_LkFg", "summary": "This paper studies memorization capacity of depth-2 neural networks showing under certain conditions that 2n/d units suffice to perfectly memorize n dimensional labeled data points and that small gradient implies small (global loss).", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "I find the description of the results and related work lacking. First of all the paper ignores recent results about memorization of relu networks that work with similar assumptions and parameters such as \"Neural networks learning and memorization with (almost) no over-parameterization\" and \"Network size and weights size for memorization with two-layers neural networks\". Do these existing results imply already the results in this paper? Second, the paper does not detail if points with small gradient can be approached efficiently (no running time analysis is given). I would suspect that if true this result would be hard to prove as current papers regarding convergence of over-parametrized ReLU's of depth 2 require far more parameters than 2n/d. \nPerhaps the i.i.d assumption  can be used here. In general the paper cites 15-22 (dealing with the ReLU activation function) whereas the paper deals with smooth activation functions. I do not even know if the results of 15-22 hold for depth-2 networks with such activation functions. It would be good if the authors could comment on this point. \n\nThe paper is full of typos and the bibliography is not sorted according to alphabetical order. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7 hours. "}, "extra_text": {}}, {"review_id": "59aOhnoLECe", "reviewer": "Reviewer_hn5z", "summary": "The authors study expressivity and trainability for one hidden layer neural networks. They showed that, when the number of neurons is larger than $n/2d$, where $n$ is the sample size and $d$ is the input dimension, then it has strong expressivity, i.e.,  with probability one, one global-min solution with zero training loss exists. The authors also propose a method to find such a global-min during training.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "Originality: The related works are adequately cited. The novelty of this paper is high. The study of the expressive power and trainability of neural networks is very important. The previous works on the expressivity of one hidden layer neural networks, such as [Soudry and Carmon 2016] and [Xie et al. 2017], did not discuss whether a stationary solution exists around the initial point. The results in this paper improve such previous works in a significant way. Therefore, I think this is a significant contribution to deep learning immunity. One disadvantage of this paper is that the authors only study one hidden layer neural networks, it will be more interesting to investigate multi-layer neural networks in the future. \n\nQuality: This paper is technically sound.\n\nClarity: This paper is clearly written and well organized. I find it easy to follow.\n\nSignificance: I think the results in this paper is important, as explained above.   ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, the authors have adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper makes a significant contribution and the results were found interesting and technically innovative.

However, the authors failed to discuss relevant literature in their original paper, in particular Daniely's and Bubeck et al. papers. Regarding Bubeck et al, this is an easily fixable mistake, and there seem to be no real issue here that cannot be resolved.

However, as far as Daniely's work, the relevance is too large to be brushed off. Now, the authors did make convincing arguments in their rebuttal. But, bottom-line, they make arguments about the validity of the result in Daniely. Now, of course this is completely acceptable, and from my brief view of their comments I am even inclined to believe that they have a point.  But such claims and discussions should have been part of the original paper and must go through the scrutiny of peer-review, they shouldn't be assessed in the limited form of the discussion period.

Given that Neurips does not accept revised versions, it is not possible to assess how the paper might look like once these issues will be resolved by the authors, and therefore I cannot recommend acceptance.
Decision: Accept (Poster)