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 -amiiee 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) x.
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- 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.
singular-Jacobian
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; x0) 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.
(lotte 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 2 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 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.
(b): when we add the wolden-weighh constraint directly to
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 w here):
m
[z; = Σ My (o(wf - o(w sq 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 DE (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 (v)) 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.
1014
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: 1rXiv: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 Aftalo, 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: 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": "zU1ve5gNHi4", "reviewer": "Reviewer_Lvky", "summary": "This paper considers narrow (width<input dimension) neural networks with one hidden layer. In particular, they consider a special intialization scheme and show that as long as the network width $m$ is at least $\\frac{2n}{d}$ where $n$ is the sample size and $d$ is the dimension, then such network can memorize full samples. Moreover, they propose a constrained formulation of the training problem and show that every KKT point is approximately a global minimizer, so the trainability is guaranteed. They also conduct experiments to support these theoretical findings.", "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: \nThe expressivity and trainability of neural networks have been studied for long, yet most of existing works focus on 'large' networks and the setting considered in this paper is rather less touched. It's quite surprising at first glance that such small networks can memorize full samples.\n\nQuality: \nThe proofs are intuitive and written in a friendly manner. Proof sketches are good. The use of IFT is clever. However, the mirrored LeCun’s initialization is purely technical and only serves to make $f(w_0;v_0)=0$ for the use of IFT.\n\nClarity: \nThis paper is overall well-written and easy-to-follow.\n\nSignificance: \nIn my opinion, the results of this paper are interesting from a theoretical viewpoint, but lack potential impact on practice. The reasons are twofold. First, memorization of training data is not the main concern of practical algorithms, and actually most algorithms can fit training data easily. Generalization of such narrow neural networks is more important, and in fact a seemingly promising direction, as narrow networks should have smaller complexity. Second, such 'compact' network structure is rarely used in practice, and the results don't appear to be able to help explain the success of deep learning.\n\nOther comments:\nThe section on extension to deep networks seems unnecessary.\n\nThe first result of this paper is merely memorization of training data, rather than expressivity as claimed by the authors. Expressivity measures the ability of the model to express various functions.\n\nAs a result, the authors should also cite previous works on memorization of training data, such as \n'Understanding deep learning requires rethinking generalization',\n'Small ReLU networks are powerful memorizers: a tight analysis of memorization capacity'.\nSince this paper discusses 'expressivity' of narrow neural networks, previous works on this topic should be included in the bibliography as well, for example:\n'The expressive power of neural networks: A view from the width'.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors address the limitation of this work that only neural networks with one hidden layer are considered. It would be better if authors can include generalization results or at least a discussion on this topic.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "mWN8cfI34j4", "reviewer": "Reviewer_HxjM", "summary": "This paper tries to understand neural network (NN) expressivity (interpolability) and trainability, i.,e effectiveness of (proposed) training procedures in the underparameterized regime, i.e, m < n, where m is the width of the NN and n is the number of samples, albeit for 1 -hidden layer neural networks and activation functions (except ReLUs).\n\nThe problem is important since, a majority of existing literature focuses on the performance in the overparamterized regimes or expressivity alone.\n\nUnder some assumptions on the architecture of the NN, the activation function and when $m > \\frac{2n}{d}$ and $m < n$, they show by careful initialization of the weights (mirrored Lecun initialization), any stationary point is a minima of the training loss in a small radius around the initialization. Furthermore, they propose a modified projected Gradient descent algorithm, whose stationary points approximately, minimize the training loss (with probability 1). ", "questions": "", "limitations": "", "rating": 7, "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 use of the Inverse Implicit function theorem in this context seems new to analyze the loss landscape around the initialization and show the existence of the global minima in a ball around the initialization.\nIn addition, they show that under the assumptions, narrow networks can be trained with a modified projected gradient descent algorithm, that ensures to preserve the properties of the Jacobian matrix around the initialization.\nThe initialization is simple and these techniques seem to be useful in analyzing the m < n regime.\n\nHowever, below are some questions and some concerns:\n1) I believe expressivity in the sense defined by Telgarsky 2016 and related papers (Chatziafratis et al. 2019,2020) provide a function and (family of functions resp.) where shallow networks (where the depth can be greater than 1 but o(L) , where L is a parameter indicating composition of functions), require exponential width to express these functions, which signifies some fundamental benefits/limitations of deep/shallow networks. Here the problem is to study trainability and interpolation properties of narrow networks (which are still beneficial).\n2) Can the assumption about the even number of neurons be removed? Let's say by setting the weight in the middle to be 0?(naively), so that initialization holds.  \n3) Does the same method and initalization work in practice with ReLU neurons?\n4) What can be said about the d=1 and d=2 cases? when m < n? Of course, in practice it is interesting to analyze behavior in high-dimensions, but it would be interesting to understand the challenges here.\n5) The IFT as far as i understand guarantees the existence of a radius around w_0 (maybe a small radius). Can something be said about the radius, as the Theorem 2 uses this radius in the constraints. Also, it seems like sometimes a larger radius helps in the test-accuracy for some problems. What would be the advice on setting the radius?\n6) Finally, it is not clear if PGD always converges for non-convex problems. In practice, what are some things that are useful in the aspect?\n\nReferences:\nTelgarsky, Matus. \"Benefits of depth in neural networks.\" Conference on learning theory. PMLR, 2016.\nChatziafratis, Vaggos, et al. \"Depth-width trade-offs for relu networks via sharkovsky's theorem.\" arXiv preprint arXiv:1912.04378 (2019).\nChatziafratis, Vaggos, Sai Ganesh Nagarajan, and Ioannis Panageas. \"Better depth-width trade-offs for neural networks through the lens of dynamical systems.\" International Conference on Machine Learning. PMLR, 2020.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See above for limitations. The authors have adequately addressed the social impact of their work.", "review_text": "", "extra_scores": {"ethical_concerns": "N.A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "NWgn4dkbBb3", "reviewer": "Reviewer_qqLe", "summary": "This paper studies narrow 1-layer neural networks with respect to their expressivity and trainability. More precisely, the authors prove a lower bound for the width of such networks so that in the optimization landscape one global minimum does exists and can be found by using a specific training regime based on a mirrored LeCun's initialization. Several numerical experiments show superiority of this approach for such classes of neural networks.", "questions": "", "limitations": "", "rating": 8, "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": "Ensuring trainability of narrow neural networks is of key importance when \"small\" networks are required due to, for instance, limited memory. This paper not only provides an analysis for the 1-layer setting, but also very nicely combines it with expressivity considerations, which is intriguing both from a conceptual viewpoint and also beneficial for solving this problem. The authors are able - in the considered setting - to also introduce a training regime for which they can prove success in the sense of reaching the global minimum. Interestingly, they here rely on a mirrored LeCun's initialization, which now for the first time is linked with expressivity as well. Hence, to my mind, this is a relevant paper from various viewpoints. \n\nI just have a few minor comments, in addition, to the comments in the next part:\n* Various articles are wrongly used. This would be good to check again.\n* Line 22/23: It would be helpful to say where \\theta on the right hand side of (1) appears. This is only mentioned later on.\n* The writings in the figures is too small such as in Figure 1.\n* The term expressivity is used often, but in a vague sense. It would be nice to be more precise about what is meant, and in particular, include a definition for the term \"strong expressivity\".\n\n\nThe authors addressed my comments successfully, and I will keep my (positive) rating.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations:\n* The current analysis is only for 1-layer neural networks. This I don't see as a problem, since first it is highly difficult to derive results of such a type and thus nice to see that at least in this setting this is possible, and second in Subsection 3,4 the authors do point out some ideas on how to extent is to deep networks.\n* The current analysis is only for smooth activation functions, and, in particular, does not include the ReLU. If a review is requested, I would ask the authors to comment on possibilities on how to include the ReLU in their analysis. \n\nSocietal Impact:\n* This analysis and the provided training algorithm are a key step towards memory-efficient, yet trustworthy neural networks. ", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "51mSgGlUQNK", "reviewer": "Reviewer_qdo9", "summary": "The paper studies empirical risk minimization (= minimizing training error) in two-layer neural networks under mean squared error, in the mildly over-parameterized regime where the number of network parameters is linear in the sample size. The main contributions of the paper include: 1) a symmetric LeCun initialization, 2) under which neighborhoods of the initial hidden layer weights include a global minimum with zero error, and a 3) constraint optimization problem whose KKT points are approximate global minima of the empirical loss.", "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": "+ Writeup quality: I think there is room for improvement. Here are some suggestions:\n- Repetitions: there are several instances. For example, the jacobian is defined twice, in lines 37 and 108. Feature matrix is defined in lines 55 and 110. Remark 1, “When d>2, Theorem 1 is applicable to narrow networks with m<n” is stated right before the theorem in line 122.\n- Clarity: some wordings are sloppy. For example, the challenges listed in lines 64-72 are not very precise. What do you mean by a “solution”? To me, a solution corresponds to a particular network parameterized by weights (w,v). Then how can a network be “expressive”? Expressiveness is a property of a class of functions, not a single function. Therefore, I do not completely understand what you mean by “expressive solutions” in these three bullet points.\n+ Some other minor comments on the writeup:\n- Footnote 1, page 1, do you mean Chen et al.?\n- Line 58: whether *an* global-min\n- In algorithm 1, step 1, “i” only needs to go through 1,...,m/2, right?\n- Figure 5 and 6 are difficult to read; it helps if you use larger font sizes.\n- The quality of the plots are not great, and they can be fixed easily. For example, in Figure 6, why not dedicate the whole space to the plots by including the legend inside the figure? You certainly don't need to repeat “Test acc: Our training regime with ” in every legend for every curve.\n+ Assumptions: Assumptions 1 and 3 are reasonable. Assumption 2 is very confusing. On one hand, it requires the nonlinearity to be zero at the origin (sigma(0) = 0). On the other hand, it requires sigma(0),sigma’(0),...,sigma^{n-1}(0) to all be non-zero, which is a contradiction. I assume this is a typo -- please clarify. I also found the assumption -- at least the way it’s currently stated -- to be odd in the sense that the requirements on the nonlinearity become more stringent as the sample size increases.\n+ Statement of Theorem 1 is a bit confusing. Isn’t “every stationary point” in line 133 redundant? Because you follow up by saying that the gradient at that point is zero. Also, because the theorem statement does not quantify epsilon whatsoever, I assume that it holds for any epsilon. Then, the second part of the theorem essentially reads as: “no spurious local minima if v is not elementwise zero”. Does it not contradict landscape results in the literature that establish existence of bad local minima? In any case, it would be helpful if you add a discussion on that.\n\nWeakness:\n- The paper merely focuses on the optimization aspect, that is, minimizing the training loss, and ignores the more important problem (from ML perspective) of generalization. It would have been helpful if the authors include a discussion on the implications of these results on the generalization error as well.\n- Also, the paper does not provide any convergence guarantees; therefore, the claims about the “trainability” of models with m < n in the introduction are not well supported.\n- The “trainability” results -- ignoring the fact that there are no computational const analysis or guarantees in the paper -- suggest that the proposed initialization+PGD framework for solving the constrained problem will only (if at all) yield a epsilon-subotimal minima if the hidden weights remain epsilon-close to the initialization. This, in essence, is not desirable as it does not allow learning representations which is crucial in deep learning. Also, this is conceptually similar to the requirements in the NTK / lazy regime, with the difference that those results offer precise convergence rates.\n- Experiments: A lot of important information about the experimental setting is missing. What is the learning rate scheme for SGD? What is the initial learning rate? What is the mini-batch size? Have you tried initialization schemes other than LeCun’s? Also, the plots look very noisy to me, as they are only averaged over two independent runs. Figure 5 is very confusing. How does “constraint size” come into play in “regular training”? As far as I understood, according to line 271, this is just “unconstrained GD-based method with LeCun’s initialization”, where no constraints are in effect. In figure 6 in section 4.2, if the goal is to “further evaluate your theory”, why is the “test accuracy” plotted, and not the “training loss”?\n\nOverall, in my opinion, the merits of the paper outweigh the drawbacks. However, given my detailed comments above, the paper is borderline. Therefore, I vote for a marginal accept. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "14"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper considers the loss landscape of relatively narrow neural networks with 1 hidden layer. Specifically, the regime is that the width is at least the number of datapoints divided by the input dimension. The authors prove the existence of a global optimum that perfectly fits the training data, with at least a small neighborhood around this point within which training converges. The reviewers agree that this is an valuable contribution, with the width of the networks in question large enough to be interesting while being far from existing work, which often focuses on extremely wide networks. While nets with just 1 hidden layer are of course quite simple, this is nonetheless an advance from prior literature. I accordingly recommend acceptance. The reviewers note that the authors do not offer convergence guarantees except in the vicinity of the optimum, which should be made clear in the abstract and introduction to avoid any possibility of misunderstanding to the reader.
Decision: Accept (Poster)