<?xml-model href='http://www.tei-c.org/release/xml/tei/custom/schema/relaxng/tei_all.rng' schematypens='http://relaxng.org/ns/structure/1.0'?><TEI xmlns="http://www.tei-c.org/ns/1.0">
	<teiHeader>
		<fileDesc>
			<titleStmt><title level='a'>When Expressivity Meets Trainability: Fewer than n Neurons Can Work</title></titleStmt>
			<publicationStmt>
				<publisher></publisher>
				<date>10/01/2021</date>
			</publicationStmt>
			<sourceDesc>
				<bibl> 
					<idno type="par_id">10341621</idno>
					<idno type="doi"></idno>
					<title level='j'>Advances in neural information processing systems</title>
<idno>1049-5258</idno>
<biblScope unit="volume"></biblScope>
<biblScope unit="issue"></biblScope>					

					<author>Jiawei Zhang</author><author>Yushun Zhang</author><author>Mingyi Hong</author><author>Ruoyu Sun</author><author>Zhi-Quan Luo</author>
				</bibl>
			</sourceDesc>
		</fileDesc>
		<profileDesc>
			<abstract><ab><![CDATA[Modern neural networks are often quite wide, causing large memory and computationcosts. It is thus of great interest to train a narrower network. However,training narrow neural nets remains a challenging task. We ask two theoreticalquestions: Can narrow networks have as strong expressivity as wide ones? If so,does the loss function exhibit a benign optimization landscape? In this work, weprovide partially affirmative answers to both questions for 1-hidden-layer networkswith fewer than n (sample size) neurons when the activation is smooth. First, weprove that as long as the width m>=2n=d (where d is the input dimension), itsexpressivity is strong, i.e., there exists at least one global minimizer with zerotraining loss. Second, we identify a nice local region with no local-min or saddlepoints. Nevertheless, it is not clear whether gradient descent can stay in this nice region.Third, we consider a constrained optimization formulation where the feasibleregion is the nice local region, and prove that every KKT point is a nearly globalminimizer. It is expected that projected gradient methods converge to KKT pointsunder mild technical conditions, but we leave the rigorous convergence analysisto future work. Thorough numerical results show that projected gradient methodson this constrained formulation significantly outperform SGD for training narrowneural nets.]]></ab></abstract>
		</profileDesc>
	</teiHeader>
	<text><body xmlns="http://www.tei-c.org/ns/1.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:xlink="http://www.w3.org/1999/xlink">
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="1">Introduction</head><p>Modern neural networks are huge (e.g. <ref type="bibr">[8,</ref><ref type="bibr">74]</ref>). 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". There are many ways to reduce network size, such as quantization, sparcification and reducing the width (e.g. <ref type="bibr">[20,</ref><ref type="bibr">77]</ref>). In this work, we focus on reducing the width (training narrow nets).</p><p>Reducing the network width often leads to significantly worse performance <ref type="foot">3</ref> . 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 a network can represent; see Definition 1). 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.</p><p>So how is the training error related to expressivity and trainability? The training error is the sum of two parts (see, e.g., <ref type="bibr">[64]</ref>): the expressive error (which is the best a 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.</p><p>It 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 ( <ref type="bibr">[19,</ref><ref type="bibr">35,</ref><ref type="bibr">59]</ref>), while narrow networks (width m &lt; sample size n) suffer from bad landscape <ref type="bibr">([2, 60, 66, 72, 79]</ref>). Therefore, if we want to improve the performance of narrow networks, it is likely that both expressiveness and trainability need to be improved.</p><p>The above discussion leads to the following two questions:</p><p>(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?</p><p>The key challenges in answering these questions are listed below:</p><p>&#8226; It is not clear whether a narrow network has strong expressivity or not. Many existing works focus on verifying the relationship between zero-training-error solutions and stationary points, but they neglect the (non)existence of such solutions (e.g. <ref type="bibr">[71]</ref>, <ref type="bibr">[63]</ref>). For narrow networks, the (non)-existence of zero-training-error-solution is not clear.</p><p>&#8226; Even if zero-training-error solutions do exist, it is still not clear how to reach those solutions because the landscape of a narrow neural network can be highly non-convex.</p><p>&#8226; Even assuming that we can identify a region that contains zero-training-error solutions and has a good landscape, it is potentially difficult to keep the iterates inside such a good region. One may think of imposing an explicit constraint, but this approach might introduce bad local minimizers on the boundary <ref type="bibr">[6]</ref>.</p><p>In this work, we (partially) answer (Q1) and (Q2) for a 1-hidden-layer nets with fewer than n neurons. Our main contributions are as follows:</p><p>&#8226; 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 is strong, i.e., w.p.1. there exists at least one global-min with zero empirical loss. In addition, such a solution is surrounded by a 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.</p><p>&#8226; 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 is a global minimizer". We propose a constrained optimization problem that restricts the hidden weights to be close to the identified nice region. We show</p><p>(e.g. ( for fixed d and n &#8594; &#8734;). We tra ) cked their proof and find that the width bound for general n, d that every Karush-Kuhn-Tucker (KKT) point is an approximated global minimizer of the unconstrained training problem<ref type="foot">foot_1</ref> .</p><p>&#8226; 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.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="2">Background and Related Works</head><p>The expressivity of neural networks has been a popular topic in machine learning for decades. There are two lines of works: One focuses on the infinite-sample expressivity, showing what functions of the entire domain can and cannot be represented by certain classes of neural networks (e.g. <ref type="bibr">[4,</ref><ref type="bibr">45]</ref>).</p><p>Another line of works characterize the finite-sample expressivity, i.e. how many parameters are required to memorize finite samples (e.g. <ref type="bibr">[5,</ref><ref type="bibr">13,</ref><ref type="bibr">21,</ref><ref type="bibr">25,</ref><ref type="bibr">26,</ref><ref type="bibr">42,</ref><ref type="bibr">75]</ref>). The term "expressivity" in this work means the finite-sample expressivity; see Definition 1 in Section 4.1. A major research question regarding expressivity in the area is to show deep neural networks have much stronger expressivity than the shallow ones (e.g. <ref type="bibr">[7,</ref><ref type="bibr">17,</ref><ref type="bibr">41,</ref><ref type="bibr">48,</ref><ref type="bibr">56,</ref><ref type="bibr">57,</ref><ref type="bibr">67,</ref><ref type="bibr">70,</ref><ref type="bibr">72]</ref>). However, all these works neglect the trainability.</p><p>In the finite-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 <ref type="bibr">[1,</ref><ref type="bibr">16,</ref><ref type="bibr">28,</ref><ref type="bibr">80]</ref>). While these wide networks are often called "over-parameterized", we notice that the number of parameters of a width-n network is actually at least nd, which is much larger than n. If comparing n with the number of parameters (instead of neurons), the transition from under-parameterization and over-parameterization for a one-hidden-layer fully-connected net (FCN) does not occur at width-n, but at width-n/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").</p><p>There are a few works on the trainability of narrow nets (one-hidden-layer networks with m n/d neurons). Soudry and Carmon <ref type="bibr">[63]</ref>, Xie et al. <ref type="bibr">[71]</ref> 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 a zero-loss global minimizer exists.</p><p>There are two interesting related works <ref type="bibr">[9,</ref><ref type="bibr">12]</ref> pointed out by the reviewers. Bubeck et al. <ref type="bibr">[9]</ref> study how many neurons are required for memorizing a finite dataset by 1-hidden-layer networks. They prove the following results. Their first result is an "existence" result: there exists a network with width m 4 n 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 &#8805; O n log(1 /&#8364; ) . This result requires width dependent on the precision E; for instance, when the desired accuracy E = 1/n, the required width is at least O n 2 . In contrast, in our work, the required number of neurons is just 2n/d, which is independent of E.</p><p>Daniely <ref type="bibr">[12]</ref> also studies the expressivity and trainability of 1-hidden-layer networks. </p><p>Additionally, there is a major difference between Daniely <ref type="bibr">[12]</ref> and our work: they analyze the original unconstrained problem and SGD; in contrast, we analyze a constrained problem. This may be the reason why we can get a stronger bound on width. In the experiments in Section 5, we observe that SGD performs badly when the width is small (see the 1st column in Figure <ref type="figure">4</ref> (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.</p><p>Due to the space constraints, we defer more related works in Appendix B.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="3">Challenges For Analyzing Narrow Nets</head><p>In this section, we discuss why it is challenging to achieve expressivity and trainability together for narrow nets. Consider a dataset {(xi, yi)} n &#8834; R d &#215; R and a 1-hidden-layer neural network:</p><p>where &#963; w T x is the output of the j-th hidden nodes with hidden weights wj, &#963;( ) is the activation function, and vj is the corresponding outer weight (bias terms are ignored for simplicity). To learn such a neural network, we search for the optimal parameter &#952; = (w, v) by minimizing the following empirical (training) loss:</p><p>The gradient of the above problem w.r.t. hidden weights w = {wi} m is given by: &#8711;wf(&#952;) =</p><p>First order methods like GD converge to a stationary point &#952; * = (w * , v * ) (i.e. with zero gradient) under mild conditions <ref type="bibr">[6]</ref>. For problem <ref type="bibr">(2)</ref>, it is easy to show that if (i) (w * , v * ) is a stationary point, (ii) J (w * ; v * ) R n &#215; md is full row rank and n md, then (w * , v * ) is a global-min (this claim can be proved by setting the partial gradient of (2) over w to be zero). In other words, for training a network with width m &#8805; n/d, an important tool is to ensure the full-rankness of the Jacobian. Recent works have shown that it is possible to guarantee the full rankness of the Jacobian matrix along the training trajectories, however, the required width is above &#8486;(poly(n)). Roughly speaking, the proof sketch is the following: (i) with high probability, J (w; v) is non-singular locally around the random initialization ( <ref type="bibr">[71]</ref>, <ref type="bibr">[63]</ref>), (ii) increasing the width can effectively bound the parameter movement from initialization, so the "nice" property of non-singualr J (w, v) holds throughout the training, leading to a linear convergence rate <ref type="bibr">[16]</ref>. Under this general framework, a number of convergence results are developed for wide networks with width &#8486;(poly(n)) ( <ref type="bibr">[1, 11, 28, 34, 49, 53-55, 80, 81]</ref>). This idea is also illustrated in Figure <ref type="figure">1 (a)</ref>.</p><p>We notice that there is a huge gap between the necessary condition m n/d and the common condition m &#8486;(poly(n)). We suspect that it is possible to train a narrow net with width &#920;(n/d) to small loss. To achieve this goal, we need to understand why existing arguments require a large width and cannot apply to a network with width &#920;(n/d).</p><p>The first reason is about trainability. The above arguments no 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 <ref type="figure">1 (b)</ref>. Also see Figure <ref type="figure">4</ref> (b) &amp; (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 1 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 justified in the following way. The feature matrix</p><p>can span the whole space R n when it is full rank and m n, thus the network can perfectly fit any label y R n even without training the hidden layer. It is important to note that when the width m is below the sample size n, full row-rankness does not ensure that the row space of the feature matrix is the whole space R n . In other words, it is not clear whether a global-min with zero loss exists.</p><p>In the next section, we will describe how we obtain strong expressive power with &#920;(n/d) neurons, and how to avoid sub-optimal stationary points.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="4">Main Results</head></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="4.1">Problem Settings and Preliminaries</head><p>We denote</p><p>, where &#963;(&#8226;) is the activation function, wj &#8712; R d and vj &#8712; R are the parameters to be trained. Note that we only consider the case where f (x; &#952;) &#8712; R has 1-dimensional output for notation simplicity.</p><p>To learn such a neural network, we search for the optimal parameter &#952; = (w, v) by minimizing the empirical loss <ref type="bibr">(2)</ref>, and sometimes we also use f(w; v) or f (w; x, v) to emphasize the role of w. We use the following shorthanded notations: x := (x T ; . . . ; x T ) &#8712; R n &#215; d , y := (y1, . . . , yn) T &#8712; R n , w := (w1, . . . , wm) m</p><p>We denote the Jacobian matrix of f (w; v) w.r.t w as J (w; v), which can be seen in <ref type="bibr">(3)</ref>. We define the feature matrix &#934;(w) as in <ref type="bibr">(4)</ref>. We denote the operator w 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 neighborhood of initialization', it means 'w is in the neighborhood of the initialization w 0 '. Next, let us describe the mirrored LeCun's initialization in Algorithm 1. 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 x; see Figure <ref type="figure">2</ref> for a simple illustration. Note that similar symmetric initialization strategies are also proposed in some recent works such as <ref type="bibr">[11]</ref> and <ref type="bibr">[12]</ref>. However, our purpose is different. More explanation can be seen in the final paragraph of Section 4.2.  Throughout the paper, we will make the following assumptions.</p><p>Assumption 1. For f (x; &#952;) in ( <ref type="formula">1</ref>), we assume its width m is an even number, and m &#8805; 2n . Assumption 2. We assume the activation function &#963;(&#8226;) : R &#8594; R is analytic and L-lipschitz continuous, its zero set only contains 0: {z|&#963;(z) = 0} = {0}. In addition, there are infinitely many non-zero coefficients in the Taylor expansion of &#963;(&#8226;).</p><p>When d &gt; 2, Assumption 1 can be applied to narrow networks 5 with m &lt; n. Assumption 2 covers many commonly used activation functions such as sigmoid, softplus, and Tanh, but it does not cover ReLU since it is nonsmooth.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="4.2">Expressivity Analysis</head><p>In this section, we prove that narrow neural networks (which are still over-parameterized) have strong expressivity. Further, the zero-training-error solution is surrounded by a good landscape with no local-min or saddles, which motivates our trainability analysis in the following sections. Theorem 1. Suppose Assumption 1, 2, and 3 holds.</p><p>) is initialized at the mirrored LeCun's initialization given in Algorithm 1, with &#952; 0 = (w 0 , v 0 ), then there exists E0 &gt; 0 such that for any E &#8804; E0, there exists a w &#8712; B&#8364;(w 0 ) = {w | lw w 0 lF &#8804; E} and a entry-wise non-zero v, such that with probabilty 1 of choosing {(xi, yi)} n and &#952;0, the output of f will be exactly the groundtruth label:</p><p>j=1</p><p>In addition, every stationary point &#952; * = (w * , v * ) (i.e., the gradient is zero) is a global-min of (2) with zero loss if it satisfies w * &#8712; B&#8364;(w 0 ) and v * is entry-wise non-zero.</p><p>Remark 1. Theorem 1 emphasizes the role of hidden weights of a neural network: it is a key ingredient for strong expressivity. When m &lt; n, if we fix all the w = w 0 , the range space of the feature matrix &#934;(w 0 ) does not cover the whole R n space, so there always exists a label y, such that no v * can be found that perfectly maps the input to y. However, a small tolerance of the movement of w will let f (x; &#952;) perfectly fit any input-label pair, so the movement of w is vitally important. The free perturbation of w serves as an effective remedy against the limited expressivity.</p><p>Remark 2. We emphasize that Theorem 1 holds for "any small enough E" instead of "any E". Therefore, Theorem 1 only states "there is no spurious local-min" locally. It is still possible that on the global landscape results there "exists bad local-min" (e.g. Ding et al. <ref type="bibr">[14]</ref>).</p><p>We comment a bit more on the maximum required size of E. In our proof in Appendix E.1, 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 <ref type="figure">1</ref>). To briefly summarize, the maximum radius is (linearly) proportional to the minimum singular value of the initial Jacobian J (w 0 ; v 0 ). Technical details on the size of this radius can be seen in <ref type="bibr">[18,</ref><ref type="bibr">Remark 4.1]</ref>.</p><p>Proof sketch. Theorem 1 consists of two arguments: (i) there exists a global-min with zero loss, (ii) in the neighborhood of initialization, every stationary point is a global-min. A detailed proof is relegated to Appendix E. We outline the main idea below.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>5</head><p>When d = 1, 2, all our results still hold; nevertheless, the required width m &#8805; n, 2n, thus it does not belong to the "narrow" setting we defined earlier in Section 2 (which requires m &#8712;</p><p>To argue (i), the key idea is to use the Inverse Function Theorem (IFT), which is stated in Appendix E.1. According to IFT, as long as an n n submatrix of J (w 0 ; v 0 ) is invertible, then for any y R n and any small enough E, there exists a w * B&#8364;(w 0 ) whose prediction output f (w * ; v 0 ) y f (w 0 ; v 0 ). Additionally, since f (w 0 ; v 0 ) = 0, we have f (w * ; v 0 ) y. Once this is shown, then we just need to scale all the outer weight vj uniformly and the output will be exactly y since f (w * ; v) is linear in v. To argue (ii), recall that all the stationary points &#952; * = (w * , v * ) satisfy wf(&#952; * ) = J (w * ; v * ) T (f (w * ; v * ) y) = 0. Therefore, if J T (w * ; v * ) R md &#215; n is of full column rank, the stationary point &#952; * = (w * , v * ) is a global minimizer with f(&#952; * ) = 0. The desired full-rankness condition is true because: (i) J (w 0 ; v 0 ) is full rank w.p.1 at initialization, (ii) w * will not leave the small neighborhood B&#8364;(w 0 ), so the dynamics of w stays inside the manifold of full-rank Jacobian.</p><p>The proof of Theorem 1 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 (w</p><p>surrounded by all possible directions pointed from 0 R n , so for any y R n , IFT claims that there exists at least one w * B&#8364;(w 0 ), s.t. f (w * ; v 0 ) y f (w 0 ; v 0 ) = y, therefore, f (w * ; v * ) can perfectly match y by scaling v 0 with some constant (Figure <ref type="figure">3</ref>(a) illustrates this case when n = 2).</p><p>In contrast, if we use IFT around regular LeCun's initialization, the existence of f (w 0 ; v 0 ) on the right hand side resists us from scaling v 0 like before (Figure <ref type="figure">3</ref>(b) illustrates this case). As such, Theorem 1 does not hold for any small E around the regular initialization. This is also revealed in our experiments in Section 5.1: training fails if we only search around the regular LeCun's initialization. The illustration here is for n = 2. For (a), scaling v 0 will directly lead to zero loss, while it is not true for (b) due to the non-zero f (w 0 ; v 0 ).</p><p>The idea of zero initial output is also used in other recent works in Table <ref type="table">1</ref>. 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 ( <ref type="bibr">[3,</ref><ref type="bibr">11,</ref><ref type="bibr">23,</ref><ref type="bibr">24,</ref><ref type="bibr">34]</ref> and <ref type="bibr">[12]</ref>). Nguyen <ref type="bibr">[49]</ref> 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 0. 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.</p><p>Table <ref type="table">1</ref>: Comparison of recent works considering zero initial output.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>Work</head><p>Width Motivation <ref type="bibr">[3,</ref><ref type="bibr">11,</ref><ref type="bibr">23,</ref><ref type="bibr">24,</ref><ref type="bibr">34</ref>] mL 1  To avoid handling the bias term in the NTK regime <ref type="bibr">[12]</ref> m = O &#732;(n/d) To avoid handling the bias term in the NTK regime <ref type="bibr">[49]</ref> mL 1 = O(n) To ensure linear convergence via imbalanced weight</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>Ours m = O n</head><p>To achieve strong expressivity via Inverse Function Theorem</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="4.3">Trainability Analysis</head><p>Despite the expressivity and good local properties stated in Theorem 1, in practical training, the weights can easily escape the nice neighborhood, especially when the width is not sufficiently large.</p><p>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 a very large loss <ref type="bibr">[6]</ref>. This is supported by our experiments in Section 5, Figure <ref type="figure">4</ref>, (b): when we add the hidden-weight constraint directly to the regular training regime (i.e., let w w 0 F E), it fails to find a low-cost solution when E and width become small.</p><p>In this sense, we need to design a constrained problem, such that all the KKT points will have small training loss, including those on the boundary. Fortunately, Theorem 1 suggests one such formulation. Recall in the proof of Theorem 1, we construct a zero-loss global-min by scaling v 0 , so v * still follows the pairwise-opposite pattern. Inspired by this, we consider the following neural network (we abuse the notation of f (x; &#952;), f (x; w, v) and v = (v1, . . . , vm ) here):</p><p>Note that the optimization variable for the outer layer is only v = (v1, . . . , vm ), and the rest of the outer weights are automatically set to be v. Despite the change of v, Theorem 1 still applies since it does not have any specific requirement on v. We then use <ref type="bibr">(6)</ref> to formulate the following problem <ref type="bibr">(7)</ref>:</p><p>where f (xi; &#952;) is in the form of <ref type="bibr">(6)</ref>,</p><p>Here, &#950; &gt; 0 is a small constant that keeps the entries of v away from zero, which is an essential requirement of Theorem 1. The requirement of vj/vjt &#954; &lt; allows all entries of v to be uniformly large, but it rules out the case when some entries are much larger than others. Instead of regarding all these requirements of B(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 <ref type="bibr">(7)</ref> implies the near-global optimality for the unconstrained training problem (2). Theorem 2. Suppose Assumption 1, 2, and 3 hold and assume &#952; 0 = (w 0 , v 0 ) as given in Algorithm 1. Then every KKT point &#952; * = (w * , v * ) of ( <ref type="formula">7</ref>) is an approximate global-min w.p.1., that is:</p><p>The proof of Theorem 2 is based on the special structure of neural network f (x; &#952;), including the linear dependence of v and the mirrored pattern of parameters. To better illustrate our proof idea, we provide a user-friendly proof sketch in Appendix F.1. Detailed proof can be seen in Appendix F.2.</p><p>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 <ref type="bibr">(7)</ref>, and the constrained parameter movement. Combining these elements with Projected Gradient Descent (PGD), we propose a new training regime in Algorithm 2 in Appendix H.1. Thorough numerical results are provided in the following sections to demonstrate the efficacy of Algorithm 2.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="4.4">Discussion: Extension to Deep Networks</head><p>In the previous sections, we analyze the trainability and expressivity of narrow 1-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 to Appendix G.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="5">Experiments</head><p>In this section, we provide empirical validation for our theory. Specifically, we compare the performance of two training regimes<ref type="foot">foot_2</ref> :</p><p>(1) Our training regime: we optimize a constrained problem <ref type="bibr">(7)</ref>      Second, it does not work when we directly impose the hidden-weight constraint of ( <ref type="formula">7</ref>) on the regular training regime (and PGD is used accordingly), as it fails to find a low-cost solution when E and width become small. There are two possible causes: perhaps there is no global-min inside the ball, or it converges to bad local-min on the boundary. In contrast, our training regime always finds a low-cost solution with any choice of E. Therefore, we suggest not to directly add constraint and use PGD. Instead, when using PGD, it is better to utilize the mirrored initialization &amp; the of v in <ref type="bibr">(7)</ref> (see 4 (a)).</p><p>Furthermore, Figure <ref type="figure">4</ref>, (c) &amp; (d) depict &#955;min(J (w * ; v * )), i.e. the minimum singular value of the Jacobian at the stationary (or KKT) points. As expected in Section 1, when the width is small, regular training regime (when E = 1, 000) has trouble controlling the parameter movement, and it is likely to 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.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="5.2">Test Accuracy on R-ImageNet</head><p>We check the test accuracy (not just the training accuracy) of the proposed method on R(Restricted)-ImageNet ( <ref type="bibr">[58]</ref>). R-ImageNet is a subset of ImageNet with resolution 224 224, and it is widely used in various papers (e.g. <ref type="bibr">[68]</ref>, <ref type="bibr">[27]</ref>). Detailed description can be found in Appendix H.2. In both training regimes, experiments are conducted on ResNet-18 <ref type="bibr">[22]</ref>, which contains 4 CNN blocks and 1 fully connected output layer. To compare the performance under different widths, we 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 constraints in problem <ref type="bibr">(7)</ref> to the final CNN block &amp; the output layer. In comparison, regular SGD does not perform well in the narrow setting. More theoretical analysis on the generalization power will be considered as our future work.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head n="6">Conclusion</head><p>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 to approximately zero loss in our training regime. We notice some interesting questions by reviewers and colleagues. We provide further discussion on these questions in Appendix A, they may be intriguing for general readers.</p><p>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 1-hidden-layer networks, we are trying to extend it to deep ones. Third, the algorithmic convergence analysis to reach the KKT point is imperative. </p></div><note xmlns="http://www.tei-c.org/ns/1.0" place="foot" n="3" xml:id="foot_0"><p>This can be verified on our empirical studies in Section 5. Another evidence is 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).</p></note>
			<note xmlns="http://www.tei-c.org/ns/1.0" place="foot" n="4" xml:id="foot_1"><p>This result describes the loss landscape of the 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.</p></note>
			<note xmlns="http://www.tei-c.org/ns/1.0" place="foot" n="6" xml:id="foot_2"><p>We call it "training regime" instead of "training method" since we use a different formulation as well a different algorithm compared to standard SGD. i=1</p></note>
		</body>
		</text>
</TEI>
