Analysis of Alignment Phenomenon in Simple Teacher-student Networks with Finite Width
Authors: Hanlin Zhu
Chengyang Ying
Song Zuo
Venue:  (2021)
Keywords: alignment
finite width network
teacher student model
angular distance function

Abstract: Recent theoretical analysis suggests that ultra-wide neural networks always converge to global minima near the initialization under first order methods. However, the convergence property of neural networks with finite width could be very different. The simplest experiment with two-layer teacher-student networks shows that the input weights of student neurons eventually align with one of the teacher neurons. This suggests a distinct convergence nature for ``not-too-wide'' neural networks that there might not be any local minima near the initialization. As the theoretical justification, we prove that under the most basic settings, all student neurons must align with the teacher neuron at any local minima. The methodology is extendable to more general cases, where the proof can be reduced to analyzing the properties of a special class of functions that we call {\em Angular Distance (AD) function}. Finally, we demonstrate that these properties can be easily verified numerically.

Under review as a conference paper at ICLR 2021
ANALYSIS OF ALIGNMENT PHENOMENON IN SIMPLE TEACHER-STUDENT NETWORKS WITH FINITE WIDTH
Anonymous authors Paper under double-blind review
ABSTRACT
Recent theoretical analysis suggests that ultra-wide neural networks always con- verge to global minima near the initialization under first order methods. However, the convergence property of neural networks with finite width could be very dif- ferent. The simplest experiment with two-layer teacher-student networks shows that the input weights of student neurons eventually align with one of the teacher neurons. This suggests a distinct convergence nature for "not-too-wide" neural networks that there might not be any local minima near the initialization. As the theoretical justification, we prove that under the most basic settings, all student neurons must align with the teacher neuron at any local minima. The method- ology is extendable to more general cases, where the proof can be reduced to analyzing the properties special class functions that we call Angular Dis- tance (AD) function. Finally, we demonstrate that these properties can be easily verified numerically.
INTRODUCTION
The theoretical understanding to the training of neural networks has been major and long-standing challenge. A recent line of research (Du et al. 2019c bla Arora et al. 2019a presented major theoretical breakthrough via elegant approach to characterize the training procedure of ultra- wide neural networks. At the high level, the training loss profile of an ultra-wide neural network (m S(NN),, N is the size of the training set) uniformly converges to procedure, almost all neurons' weight vectors remain close to their initialization, which in term preserves the uniform converging rate. As result, the training loss converges zero with almost all neurons' weight vectors near their initialization.
During the training
Does the elegant theory reveal the fundamental mechanics behind the success of practical neural networks whose widths are finite (m = O(N))? The theory suggests a clear property that is crit- ical the uniform convergence: The weight vectors of the neurons rarely move away from their initialization.
In this paper, we first examine this conjecture with experiments. Unfortunately, a simple experiment with two-layer teacher-studens networks exhibits contradicting properties: Despite of their random- ized initialization. the weight vectors of the student neurons eventually align with the weight vector of one of the teacher neurons.
In other words, almost all the student weight vectors end up somewhere far away from where they begin: from the randomized initialization to some specific teacher weight vector. We emphasize that such experiments with teacher-student models are generic in the sense that, according to the universal approximation theorem, any target function can be equivalently described as two-layer neural network with ReLU activation. Although such a teacher network may not be accessible for an arbitrary dataset, the teacher-student model is sufficiently representative for empirical justification.
Similar alignments are also observed for over pee-parameterized student and teacher networks of multi- ple layers Tian 2020). In other words, the neuron weights alignment might be the more appropriate fundamental mechanics for neural networks with finite width. In fact, once the studett-teacher align- ment has been established, it is straightforward that the training loss converges zero.
We then investigate the other direction of the observation: Does the convergence of gradient descent in this case imply perfect alignment between the student and the teacher neurons? To the best

---

Under review as a conference paper at ICLR 2021
Figure 1: The weight vectors of teacher neurons (dotted lines) and student neurons (solid lines) in epoch 0, 10, 1000, 5000, 50000 respectively.
of knowledge, the theoretical understanding this question is extremely limited for the simplest 1-teacher 2-student case.
In this paper, initiate the study of the fundamental yet highly non-trivial question with the most basic 1-teacher m-student setting. Both the teacher and students are two-layer neural networks with ReLU activation. Mathematically, the question is equivalent whether there exist any alignment solutions to the set of equations defining zero gradients.
and rule the existence of solutions with special form for general m 2 3: (i) all student neuron weight vectors fall in the same half-plane; or (ii) the angles between any two weight vectors are rational multiples of
We demonstrate complete proof of non-existence for
For general cases, we show that the theoretical problem can be reduced to the analysis of a special class of functions which we call angular-din distance (AD) functions: If one of the associated matrices of the AD function has non-positive determinant, then there is no non-trivial solution to the set of equations. Hence no local minima without perfect alignment.
In light of the reduction, we numerically examined the property that the minimum determinant of the associated matrices are always non-posites non-positive unless perfect alignment or problem degenerated. Moreover, the minimum determinant behaves a potential function in the sense that the further from being degenerated, the further from being non-negative.
1.1 RELATED WORKS
Recent papers have made tremendous progress the theoretical analysis of sufficiently over- parametrized neural networks or those with even infinite width. With some mild assumptions, has been proved that the training eтror uniformly converge to via gradient descent (Allen-
Zhu et al. 2019b] Du et al. 2018b 2019c|b Du and Hu 2019 Lee et al.] 2019 Li and Liang 2018 Zou et al. 2018). Surprisingly, such uniform convergence implies there always exist global minima near a random initialization, generalization bounds also emerge under the same frameworks
(Allen-Zhu et 2019a Arora al. 2019a| Cao and Gu 2019). Moreover, the network width
approaches to infinity, fundamental connections between over-parameterized neural networks and kernel methods are also discovered, which hint potential correspondence between the generality of deep learning and that of kernel methods (Arora et al. 2019b Daniely et al. 2016 Daniely 2017)
Du al. 2019a Hazan and Jaakkola, 2015) Jacot al.
2018 Mairal et al.) 2014 Yang 2019).
Despite the beauty of the theoretical results, empirical studies exhibit certain mismatches with the theory. Nagarajan and Kolter (2019) shows that the uniform convergence property may insuffi cient to explain the generalization ability of neural network. Moreover, Tian (2020) considers using teacher networks to train over- paramerametri student networks of the same depth and demonstrates that almost all student neurons either align with some teacher neuron or have contribution to the final output. Our theoretical results derive from analyzing the behaviour gradient descent as- suming that the input distribution is Gaussian, following the methodology commonly used in many recent works [Brutzkus and Globerson 2017
al. 2017 Du and Lee, 2018 Du et al. 2018a
Li and Yuan 2017
Tian 2017
Zhong et al. 2017
2

---

Under review as a conference paper at ICLR 2021
2 PRELIMINARIES
Consider training two-layer student network with two-layer teacher network, where the teacher network has only one neuron in its hidden layer while the student network has m neurons in its hidden layer. Both networks have ReLU activation and we fix their weights of output layers as to simplify the notations. Let wo E I denote the weights of the teacher's hidden neuron, and w1,,-- Wmm E IRd denote the weights of each student hidden neuron, respectively. Formally, the output of the teacher and the student network are
Fteacher (I, W) (w x))
sstudent (I, W) - (w) +... + aw
Let Boy E [0, π be the angle between w; and w,, i.e.,
w; wy
O.j arccos
u, =w; be the unit-length vector with the same direction wy and p: -|22:112 be the length of w; In particular, for the 2-dimensional cases, i.e., d = 2, we use 0; E [0, (T) to denote the polar angle of w; and (0) to denote the unit-length vector with polar angle 0.
student neuron wy is called aligned with the teacher, if for = 0, or negatively aligned with the teacher, if 0or For the 2-dimensional cases, i.c., d 2, being aligned equivalent 0g Og-
Assume the data follows the normal distribution, i.e., ~ ((0, 1), then the population loss is
1 = Ra--((..)) | (o(w)x=) - E (w
(w][z))) m²))²
The partial derivative of the squared loss with respect each student neuron w; is Brutzkus and Globerson 2017))
01
Σ
Oij
+ Pj sin 01 0sju.) - -
Pe
sin 0lous)
w;
ow;
4T
4m
4T
4m
j=1
In other words, the training process terminates, i.c., the gradient zero, and only
( 0
TP: - Po sin 0:0
+Σ Pj sin Ozg j
ui +
Σ iti
01g) Vi.
Observation 2.1. If the following two conditions are met, then equation 2 are satisfied:
1. all student neurons (p; > 0) are aligned with the teacher,
2. and the sum of their lengths equals to Po-
In this paper, we argue that these two conditions are also necessary for equation 2 to stand. In the remaining part of this paper, always assume d = 2.
ALIGNMENT PHENOMENON AND THE BASIC CASE
As mentioned, simple experiments show that the student neurons eventually align with teacher neu- rons under gradient descent. Figure illustrates an example in which the teacher network has neurons. While training via gradient descent with data generated from (O, I), the randomly initial- ized student neurons gradually get aligned with one of the teacher neurons. We call it the alignment phenomenon.
In this section, we prove for the most basic case with m 2.
3

---

Under review as a conference paper at ICLR 2021
3.1 BASIC CASE WITH S
Note that when m 1, the only solution to equation that the student perfectly aligns with the teacher, i.e., wt wp. Because (st 010) (Tpi Po sin 010)u: implies that wo and ui point towards the same direction. Thus, 010 = O, which means that Tw0 = TP1 U1 = TW
However, the proof the following theorem for m becomes quite non-trivial. Theorem 3.1. When
2, there is no other solution to equation 2 except the trivial one, i.e.,
801 = 8o2 and P1 + P2 = po-
Therefore, once the training converged, the student neuron(s) must be aligned with the teacher neuron.
Due to the space limit, send the complete proof to Appendix A while highlight the key steps here.
Proof sketch. Suppose there exists a solution with 012 F 0. In this case, the two equations in equation imply two decomposition of wy onto and u2. Because such a decomposition is unique for m = 2 = d, we know the coefficients of wh. U1 U2 must be proportional. From there,
we have
WD 1
W1
22
80
0
By projecting this equation onto we and the orthogonal direction of wo. we can further conclude that
Po
P1
P2
012 12
- 020)
020
(π
010) sin
By plugging the above equation into equation we can reach contradiction and complete the proof.
Note that a major challenge of extending this proof to m 2 3 is that the decomposition is not unique anymore, which breaks the first step of the proof.
Even though, it is still useful to notice that whenever two student neurons get aligned, i.c., 0ij = 0, they can be replaced by single neuron it of the same direction and unified length, Pi. Pi Pj. so that any such non-trivial solution to m = k implies non-trivial solution to m = k - 1.
Therefore, for general
3, we can without loss of generality prove that there is no solution to equation 2 with ( = 6 < 01 ... < 6m < 2n and pa = 1, Pl...., > 0.
4 SPECIAL CASES
In this section, we prove that for m 2 3, there no solution to equation
satisfying either of the
two special conditions:
Students in a half-planee 0 - 0 < 01 < < Om n
Polar angles being rational multiples of n: Vi E (1...., mm.0 = q: for some rational number qs-
4.1 SPECIAL CASE WHEN ALL NEURONS ARE IN THE UPPER HALF-PLANE
We first show the following theorem.
Theorem 4.1. When all vectors of student neurons are in the upper half-plane, i.e., 0 0= 0g < 8 <
Om n. then equation system equation 2 has non-trivial solution.
The rigorous proof of Theorem 4.1 is provided in Appendix B.3 Here, we present two lemmas of function f(0) (π 8) 0 + sin and the proof of the following two lemmas can be found in
Appendix B
Lemma 4.2. (decreasing lemma) f(0) = sin + (I 8) cos 9 decreases the interval [0, π]. and
f(0) n, f(m) = 0.

---

Under review as a conference paper at ICLR 2021
Lemma 4.3. (log-com log-concave lemma) Va, 3 E (0, T), and 0 + 3 n, it holds that f(a)f(3) f(a + 8)f(0).
The above two lemmas reveal some properties of function f(0) - sin 0 ( cos f. In Section 5 we will show another amazing property of f which correlates to positive semi-definite matrices, and f also applies to analyze the phenomenon behaviour of our neural network in general case.
4.2 SPECIAL CASE WHEN ALL THE POLAR ANGLES ARE RATIONAL MULTIPLES OF
In this subsection, we consider another special case, and prove that under this constraint, equation system equation 2 has no non-trivial solution.
Theorem 4.4. When all polar angles are rational multiples of x, equation system equation has no non-trivial solution.
The proof of Theorem 4.4 shown Appendix C The key point of the proof is the following lemma.
Lemma 4.5. When 0 01 < 02 then the following m x m matrix [Tt - 0igl is positiveddefnite.
Om 2m, and there does exist i. O2 Oj.
This lemma directly derives from Theorem 3.1 in et al. 2019cc. we define f(0) = π - 0, then the associated function g is PAD function (see Definition 5.7) which will be further discussed in Section
Moreover, in this subsection, assume that all the polar angles rational multiples of Since rational numbers are dense, equation system equation 2 has no non-trive non-trivial solution 'almost every- where', which indicates that equation system equation has non-trivial solution without any constraints.
ANALYSIS OF GENERAL CASE
The general when 2 3 without any special constraints is rather difficult to prove. However, if determinant condition (see Theorem [.I) always holds, then we can rigorously prove that the alignment phenomenon always happens for arbitrary number of student neurons.
Moreover, the determinant condition can be generalized to a novel class of functions Angular Distance (AD) function (see Subsection 5.2). Since the proof of two special cases in Section are with the aid of AD functions directly or indirectly, and AD function actually appears in the previous literature (e.g.. Du et al.] (2019ch) although implicitly, it is great likely that function can be applied widely theoretical analysis of neural networks.
5.1 DETERMINANT CONDITION
The following theorem clarifies the relationship between determinant condition and alignment phe- nomenon.
Theorem 5.1. Define f0) (πt - cos + sin Les f: [f(0).. f(02))
... ... (f(mm))) I for for fo.ffa. f ... fm and M = [f1, fm] If
i S m. Also, define matrix M, = [f....... f: the following condition (determinant condition):
Vm 3,0 0g < 01
0m 2m with 0 S < i S.I. 0 == θ,,
always holds that det M > 0 and there exists - S m, S.I. det M S0
holds, then equation system equation has no non-trivial solution, i.e. the student neural network converges only when aligning.
Proof. We only consider the general case when m 2 3, since the basic case when m S has been proved in Subsection 3.1
we project i-th equation in equation systems equation to the direction u((e),, we will obtain that
(πT 0z)) cos 0apo -pp;- Po sin 0.
Σ
Pj sin Ozj
> (T 0zy) cos 01g2i, Vi,
1
5

---

Under review as a conference paper at ICLR 2021
which is equivalent to
(sin 0:0 + (I 020) cos P0 Tp; +
Σ sinn 0ty + (T 01z) cos 0is) vi.
(3)
Note that f(0) = sin 0 + (IT 0) cos f, so equation
3 is equivalent to
m
p(00)) Σ
((0s))e,.
(4)
1=1
We can express equation in matrix form
Mp = b.
(5)
where
s(0m))
f(012)
f(0
f(010)
P1
1(22))
f(022)
f ((22m)
5(02))
P2
M
p
= Po
f(0m)) f(0m2)
f(Omm)
Pm
f(0ma)
det M > 0, then by Cramer's rule, Ps det M, < 0, thus p1 S O.
M. det M
And since there exists 1 I S m. s.t.
Determinant condition has elegant and simple form, and can be easily verified numerically (see Sec- tion 6). Moreover, the analysis of function (() sin 0 + (π 0) cos 0 and determinant condition, can be generalized to novel class of function Angular Distance (AD) function, which will be
further discussed in Subsection 5.2
5.2 AD FUNCTION
In this subsection, we provide the formal definition of angular distance (AD) function, and analyze the relationship between its proposition and the determinant condition Theorem 5.1
Definition 5.2. (AD ) Let [0. T + IR be a continuous function, and let [0, 2m] x [0, 2T] + IR, where g(x, y) = f (minn x - yl, 2n - |x-
-Ix - vl3). Then function g is an angular distance(AD) function if f [0, 2x] R that is continuous and real-valued in [0, 2n), with h(0) (2T),, it holds that
2m
2m
h(zg((z, v)h(y)dddy 0.
y=0
Also, we call the associated function of f.
Another important concept is the associated matrices of an AD function.
Definition 5.3. (associated Matrix) Let g be an AD function and give (m + 1) fixed angles
8o < 8 < 02 <.... < 8m < 2τ. Let g: = [9(01, g(0g. B,). ... g( 0,) for 0 S m. Also, define matrix M, ig...... 19:11. 1. 9n- I:+1. 9mm] and M (9 02.92--2 Im. We call M, M,.... ..... Mn, associated matrices of g and given 0n, O,.... Om.
Along with the above two definitions, provide proposition and conjecture of AD functions. Proposition 5.4. (positive semi-definite) Given 0 = 6u < 0, < .... < 8. < 2n,, for an AD function its associated matrix M is positive semi-definite.
Conjecture 5.5. (non-positive determinant) For m 2 3, given = 0p < 01 < ... < fm < 2n,, for an AD function g. and its associated matrices M1, My.... Mn then there exists where 1 i m, s.f. det M, <
The proof of Proposition 5.4 is shown in Appendix D.1 For Conjecture 5.5 although able to prove it, some experimental results (see Section show is very likely that the conclusion always holds.
not
For f(0) = sin + (π 8) cos f. its associated function g that we have analyzed in Subsection 5.1 actually an AD function by the following theorem, and the proof is presented in Appendix D.2

---

Under review as a conference paper at ICLR 2021
Theorem 5.6. For f(0) sin 0 (= (x- 0) cos 8, the associated function g is an AD function.
Combining Proposition 5.4 (oositive semi-definite), we have actually proved that part of determinant condition (det M 2 0) holds theoretically.
Note that g y) = 0 is a trivial AD function, and its associated matrices are always O. Obviously, this function not powerful enough, so we introduce a special class of AD function which is more powerful.
Definition 5.7. (PAD function) An AD function g is called positive-defiitte angular distance (PAD) S i < S m s.t.
function if for any given angles 0 0o 01 < < Om 2 with
0 + π = 0j. its associated matrix M is always positive-definite
PAD function does exist. For example, if f(x) = π x, then g is PAD function by Theorem 3.1 in Du al. (2019c).
f(0) sin 0 + (Λ 8) cos 0, we have proved that its associated function is an AD function, and will show that g is PAD function if the following conjecture holds.
Conjecture 5.8. (criterion of PAD) If an AD function is the associated function of a strictly decreasing function I, and No, (3 8.1. a, 0x B3 E (0, x), it holds that f() > +(x++ ())(0) then is a PAD) function.
Conjecture 5.8 (criterion of PAD) holds, then by Lemma 4.2 (decreasing lemma) and Lemma 4.3
(log-concave lemma), g is a PAD function. Then by Definition [5.7 (PAD function) and Conjec- ture 5.5 (non-positive determinant), the determinant condition in Theorem 5.] always holds.
Therefore, Theorem 5.1 can be rewritten the following form.
Theorem 5.9. If Conjecture 5.3 (non- mnon-positive determinant) and Conjecture 5.8 (criterion of PAD)
holds, then equation system equation has no non-trivial solution, i.e., the above neural network converge only if aligning.
Although we leave some conjectures in this subsection unproved, AD function is worth extensive re- search, since the alignment phenomenon in slightly general case can be rigorously proved directly by the conjectures concerned with AD function, and we actually apply decreasing, log-concave lemma and definition of PAD function the proof two special cases in Section respectively. Also, AD function appeared implicitly in the previous literature, which indicates that AD function can not only be applied to the theoretical analysis of alignment phenomenon, but also other behaviour of neural networks.
EXPERIMENTS
In this section, show experimental results to verify Conjecture 5.5 (non-positive deter- minant) numerically. Since impossible to test all the AD functions, we select the associated function g of ((0) sin(O) (w 0) cos(O) representative. Note that is actually equivalent to verify determinant condition Theorem 5.1
Figure 2: We fix 0: 1, 1, 0g and 0g are variables. Also, minfdet M,, det M2, det M3)
First, we test the case when m 3. Without loss of generality, we assume that 6, = 0, then fix 0 and rotate 02 Og from 0 to 2v.. We choose 02 to be and 3, and draw the minimum value of the
7

---

Under review as a conference paper at ICLR 2021
determinant of three associated matrix of 9, which is defined in Definition 5.3 (associated matrix). The results are shown Figure
It is obvious that is always non-positive. Also, test the when 4. We fix 0 and 01. The results are similar to the case when m = 3 and shown in Figure
THEL J+ 1.up...
Figure 3: We fix (01,0.) (1, (1, 6), (2, 4). min M1, det M2, det Ms det Mc).
For more general cases, it is difficult to draw figures due to the high dimension. Therefore, we randomly choose I,, f and compute the minimum value of associated matrices for 100000 times for m = and m = respectively. Again, 2 is always non-positive (see Figure
400
Figure 4: For 6 and 9, randomly choose 01.-.. Am and compute
min det M,...., det Mm } for 100000 times respectively. For visualization, & is clipped.
7 CONCLUSION
In this paper, we investigated the question that whether the elegant convergence theory for ultra-wide neural networks (m ((NN)) could apply to practical neural networks (m O(N)). We observed dissenting behaviors from the training in simple two-layer teacher-student framework with ReLU actívation and Gaussian inputs: The student neurons all get aligned with one of the teacher neurons, hinting that no local minima near any random initialization.
Following the empirical observation, student setting. We proved that there is no local minima except students being aligned with the teacher for m
analyzed the local minima the single-teacher multi-
and excluded the existence of local minima taking certain special forms for m 2 3: (i) all students falling in half plane, or (ii) all students with polar angles being some rational multiples of π.
Moreover, for general cases, proposed reduction from the existence of non-trivial local minima (i.e., local minima without alignment) to analyzing certain mathematical properties of class of functions that we call angular distance (AD) functions. In particular, we showed strong empirical evidence that the such properties hold for the specific AD function, which in term serve as a sufficient condition for existence of non-trivial local minima for general > 3.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang, Learning and generalization in overparameter- ized neural networks, going beyond two layers. Advances neural information processing systems, pages 6155-6166, 2019a.
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. convergence theory for deep learning via over- parameterization. In International Conference on Machine Learning, pages 242-252, 2019b.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of op-
timization and generalization for overparameterized two-layer neural networks. In International Conference Machine Learning, pages 322-332 2019a.
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Russ Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. In Advances in Neural Information Processing Systems, pages 1139-8148, 2019b.
Alon Brutzkus and Amir Globerson. Globally optimal gradient descent for convnet with gaussian inputs. In Proceedings of the 34th International Conference on Machine Sharning-Volumee 70, pages 605-614. JMLR. org, 2017.
Yuan Cao and Quanquan Gu. A generalization theory of gradient descent for learning over- parameterized deep relu networks. arXiv preprint arXiv:1902.01384 2019.
Amit Daniely. Sgd learns the conjugate kernel class of the network. In Advances in Neural Infor- mation Processing Systems, pages 2422-2430, 2017.
Amit Daniely, Roy Frostig, and Yoram Singer. Toward deeper understanding of neural networks: The power of initialization and dual view expressivity. In Advances In Neural Information Processing Systems, pages 2253-2261, 2016.
Simon Du and Wei Hu. Width provably matters in optimization for deep linear neural networks. In International Conference on Machine Learning, pages 1655-1664, 2019.
Simon Du and Jason Lee. On the power of over peremaarametinnnooonn in neural networks with quadratic activation. International Conference on Machine Learning, pages 1329-1338, 1338, 2018.
Simon Du, Jason Lee, Yuandong Tian, Aarti Singh, and Barnabas Poczos. Gradient descent learns one-hidden-layer enn: Don't be afraid of spurious local minima. International Conference on Machine Learning, pages 1339-1348, 2018a.
Simon S Du, Chi Jin, Jason D Lee, Michael I Jordan, Aarti Singh, and Barnabas Poczos. Gradient descent can take exponential time to escape saddle points. In Advances in neural information processing systems, pages 1067-1077, 2017.
Simon Du, Wei Hu, and Jason Lee. Algorithmic regularization in learning deep homogeneous models: Layers are automatically balanced. In Advances in Neural Information Processing Sys- tems, pages 384-395, 2018b.
Simon S. Du, Jason D. Lee, and Yuandong Tian. When is a convolutional filter easy to learn? In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018c
Simon S. Du, Kangcheng Hou, Ruslan Salakhutdinov, Barnabás Póczos, Ruosong Wang, and Keyulu Xu. Graph neural tangent kernel: Fusing graph neural networks with graph kernels. In Ad- vances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, 8-14 December 2019, Vancouver, BC, Canada, pages 5724-5734, 2019a.
Simon S. Du, Jason D. Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In Proceedings of the 36th International Conference Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pages 1675-1685. PMLR, 2019b.

---

Under review as a conference paper at ICLR 2021
Simon S. Du, Xiyu Zhai, Barnabás Póczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. 7th International Conference on Learning Representa- tions, ICLR 2019, New Orleans. LA, USA, May 6-9, 2019. OpenReview.net, 2019c.
Tamir Hazan and Tommi Jaakkola. Steps toward deep kernel methods from infinite neural networks. arXiv preprint arXiv:1508.000
2015.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and gen- eralization in neural networks. In Advances neural information processing systems, pages 8571-8580, 2018.
Jaehoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl- Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. In Advances in neural information processing systems, pages 8570-8581, 2019.
Yuanzhi Li and Yingyu Liang. Learning overparameterized neural networks via stochastic gradient descent on structured data. In Advances Neural Information Processing Systems, pages 8157- 8166, 2018.
Yuanzhi Li and Yang Yuan. Convergence analysis of two-layer neural networks with relu activation. In Advances in neural information processing systems, pages 597-607, 2017.
Julien Mairal, Piotr Koniusz, 7aid Harchaoui, and Cordelia Schmid. Convolutional kernel networks. In Advances neural information processing systems, pages 2627-2635, 2014.
Vaishnavh Nagarajan and Zico Kolter. Uniform convergence may be unable to explain general- ization in deep learning. In Advances in Neural Information Processing Systems, pages 11611- 1- 11622, 2019.
Yuandong Tian. An analytical formula of population gradient for two-layered relu network and its applications in convergence and critical point analysis. In Proceedings of the 34th International Conference on Machine Learning-Vole Volume 70, pages 3404-3413 JMLR. org, 2017.
Yuandong Tian. Student specialization in deep relu networks with finite width and input dimension. In International Conference on Machine Learning. 2020.
Greg Yang. Scaling limits of wide neural networks with weight sharing: Gaussian process behavior, gradient independence, and neural tangent kernel derivation. arXiv preprint 2019.
Kai Zhong, Zhao Song. Prateck Jain, Peter L Bartlett, and Inderjit S Dhillon. Recovery guarantees for one-hidden-layer neural networks. In Proceedings of the 34th International Conference Machine Learning- Volume 70, pages 4140 JMLR. org, 2017.
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Stochastic gradient descent optimizes over-parameterried deep relu networks, arXiv preprint arXiv:1811.08880 2018.
10


Reviews:
[{"review_id": "d0bYdDc2ekk", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "[Summary]\n\nThis paper studies the optimization landscape of one-hidden-layer neural networks in the teacher-student setting, where the ground truth teacher network is one relu and the learner network is m>=2 relus. The paper proves that (1) when m=2, any stationary point (of the student network) has to be aligned with the teacher; (2) when m>=3, stationary points satisfying certain additional conditions have to be aligned with the teacher. Above, alignment means that the student network is perfectly equal to the teacher. \n\n[Pros]\n\nThe one-hidden-layer teacher-student setting studied in this paper is an important and difficult theoretical problem. The reason why GD on an over-parameterized student could perfectly recover the teacher has been a somewhat long-standing open problem. This paper makes progress on this problem by proving the alignment property at m=2, and showing that the “determinant condition” implies alignment at m>=3.\n\n\n[Cons]\n\nI feel like the direction of studying alignment in this specific one-neuron teacher model may be a bit problematic, and may not be that significant or generalizable.\n\n---First, results in this paper seem to be about the *stationary points*, not the *local minima* (which at least additionally requires the Hessian to be PSD). This can be seen from Eq (1) and (2) which is only the stationarity condition (gradient equals zero) and does not consider the Hessian. This means that all the subsequent claims are about stationary points and must also contain the saddle points. It seems like the authors may be unaware of this. (The paper talks about “local minima” where it really means gradient equals zero.)\n\n---Second, the fact that the theory contains saddle points makes it somewhat confusing --- If a saddle point does exist, then it has to be non-aligned (because a saddle point must have non-zero loss). So the present result seems to imply that there is no saddle point at m=2 and (likely) no saddle point at m>=3, when the teacher is one relu. (Could the authors confirm or comment on this?)\n\n---Further, even if we restrict attention to local minima, (Safran and Shamir 2018) already showed that when the teacher contains multiple neurons, the student network could have spurious local minima with non-zero risk (i.e. non-aligned minima). Therefore we could not hope for alignment for all local minima when the teacher has multiple neurons, which implies that the studying the alignment in the one-neuron teacher model may not be generalizable.\n\n------\nThank the authors for the responses. While I agree with some of the points made by the authors (e.g. understanding the base case is interesting), I am still concerned about the significance of the result. Therefore I would like to keep my original evaluation.", "extra_scores": {}, "extra_text": {}}, {"review_id": "WcNiNJjNCSd", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "### Summary\n\nThis work considers learning one-hidden layer convex neural networks where the teacher is a single ReLU and the data follows a two-dimensional Gaussian distribution. The authors study the loss landscape of the population loss and provide conditions on critical points which imply that the neurons are aligned with the teacher network (I will call this an aligned solution). They show that for m<=2, any critical point is necessarily an aligned solution. For m > 2, they show that a critical point is an aligned solution in certain special cases (e.g., when all polar angles are rational multiples of pi). They further show that in the general case, under certain conjectures, a critical point is an aligned solution. For the latter result they introduce a novel concept of Angular Distance (AD) functions.\n\n### Reason for score\n\nAnalyzing the non-convex loss landscape of neural networks is extremely challenging (even in seemingly \"simple\" cases) and I appreciate the effort of the authors to tackle it. While the theoretical results are novel and may be useful for analyzing more advanced settings, I think that the scope of the current manuscript is too narrow and lacks several important empirical results and discussions. Therefore, I don't think that the current version is ready for publication and I highly encourage the authors to improve the current paper (see my suggestions for improvement below).\n\n### Pros\n1.\tThe authors tackle a very challenging problem and provide novel theoretical results.\n2.\tThe concept of AD functions is interesting and might be useful in other analyses of neural networks.\n\n### Cons\n1.\tIn this paper the authors only show results for d=2. This is highly restrictive. I understand that for d>2 the analysis might be intractable. Therefore, I think that the authors should add extensive experiments which show that alignment occurs in higher dimensions. To further strengthen the results, it would be interesting to see if some of the theoretical insights of d=2 can be also applied to higher dimensions (e.g., the analysis of AD functions). The authors mention d=2 only once in the paper. This should be clearly stated in the Abstract, Introduction and Conclusion sections.\n2.\tThe authors cite the work of Tian (2020) but do not provide a clear comparison to this work. Specifically, it is not exactly clear what is the novelty of this work compared to Tian (2020) since the latter also shows that alignment occurs for any dimension.\n3.\tIn the experiments section the authors do not empirically verify Conjecture 5.5. Therefore, it is not clear whether this is a realistic conjecture.\n4.\tThe authors show two special cases where any critical point is an aligned solution. The key question is whether gradient descent converges to solutions which satisfy the conditions of these cases. This is not discussed and I encourage the authors to perform experiments to check if this holds.\n5.\tThe authors should cite more works on student specialization, e.g., \"Dynamics of stochastic gradient descent for two-layer neural networks in the teacher student setup\" of Goldt et al. (2019) and \"Dynamics of on-line gradient descent learning for multilayer neural networks\" of Saad et al. (1996).\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "VfaW484GAuR", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper considers the problem of learning neural networks with finite width. More specifically, the authors consider the simple teach-student setting and show that the input weights of student neurons will align with the teacher neuron. The problem considered in this paper is interesting. However, the results derived in this paper only consider some simple setting which may limit its impact. Here are some concerns I have for the current paper:\n1. The authors only consider the setting that the teach network only has one neuron. Thus it may not be reasonable to claim that the student neurons will align with one of the teacher’s neurons. If the authors can provide results for the teacher network with multiple neurons, the contribution of the current paper would be stronger.\n2. Why the results only consider the case when d=2?\n3. The presentation of the current paper needs to be improved. For example, for the proof sketches of Theorems 4.1, 4.4, it is unclear the roles of Lemmas 4.3, 4.5.\n4. There is a recent work [1] also studying the learning of a single neuron model, the authors may want to compare with their results.\n5. The introduction and related work sections are clear and thorough. However, there are some relevant papers [2,3] also study the teacher network setting, the authors may want to discuss them in these sections.  \n\nReferences:\n[1] Frei, Spencer, Yuan Cao, and Quanquan Gu. \"Agnostic Learning of a Single Neuron with Gradient Descent.\" Advances in Neural Information Processing Systems (NeurIPS), 2020\n\n[2] Fu, Haoyu, Yuejie Chi, and Yingbin Liang. \"Guaranteed recovery of one-hidden-layer neural networks via cross entropy.\" IEEE Transactions on Signal Processing 68 (2020): 3225-3235.\n\n[3] Zhang, Xiao, et al. \"Learning one-hidden-layer relu networks via gradient descent.\" The 22nd International Conference on Artificial Intelligence and Statistics. PMLR, 2019.\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "6-0mu0kqvvT", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary of review:\n\nThis paper studies the optimization landscape of over-parametrized two-layer ReLU neural networks under an (isotropic) Gaussian input distribution. The main goal is to characterize the critical points of the over-parametrized student network, and show that these critical points \"align\" with the neurons of the teacher network. This is a well-motivated study since the alignment phenomenon is intriguing (Tian, 2020) but lacks a theoretical analysis.\n\nSetting:\n\nThis paper focuses on a teacher network with a single two-dimensional neuron followed by a ReLU activation function. The student network contains multiple (two-dimensional) neurons followed by a ReLU activation function.  \n\nResults:\n\nThis paper presents a suite of results for the above setting, including:\n\n(i) When the student network has two neurons, this paper shows that both neurons \"align\" perfectly with the neuron of the teacher network. Furthermore, the sum of the length of the two neurons is equal to the length of the neuron of the teacher network.\n\n(ii) When the student network has more than two neurons, this paper shows that the above \"alignment\" result holds for two special cases:\n\n-- (ii-a) when all the neurons of the student network are in the upper half-plane;\n\n-- (ii-b) when all the polar angles are rational multiples of $\\pi$. Furthermore, the polar angles satisfy a certain positive-definiteness condition in this special case.\n\n-- For the general case, this paper discovers an interesting determinant condition that guarantees the condition of (ii-b), hence the \"alignment\" result. In general, it is not clear whether the determinant condition always holds, and this paper provides several conjectures/ideas that provide some preliminary evidence for why this condition should hold.\n\nLimitation:\n\nWhile the questions are well-motivated and the settings are quite standard, I am concerned that the techniques of this paper are too restrictive to the assumptions. In particular, these include:\n\n(a) The dimension of the neurons being only two. This looks like a strong assumption, but is not mentioned or even discussed anywhere in the abstract and the introduction.\n\n(b) The results for the student network having more than two neurons are still rather preliminary. While this paper does provide several interesting ideas that might help in ultimately resolving the question, as the results stand currently, it is quite unclear to the reviewer whether the conjecture(s) will hold or not.\n\nQuestions:\n\n(a) The proof of Theorem 3.1 relies on that the critical point condition holds exactly. What if the critical point condition only holds approximately up to a small error of $\\epsilon$? Would your analysis still extend there? This setting is more interesting because in general, it is difficult for gradient descent to converge to an exact critical point. Furthermore, this setting might only extend to allow for sampling errors in an empirical loss.\n\n(b) What about the proof of Lemma 4.5 and Theorem 5.1? Would the analysis extend to allow for sampling errors or not?\n\nOther comments:\n\n- At the bottom of page 5, it will help to move the $\\rho_0$ and $\\rho_j$ outside of $\\cos$. Right now, this equation looks a bit confusing..", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewer seems to reach a consensus that the paper is not ready for publication at ICLR. One of the major issues seems to be that the paper only analyzes the case of $d=2$. (In the AC's opinion,  $d>2$ might be fundamentally more difficult to analyze than $d=2$). 


Decision: Reject