We analyze the dynamics of training deep ReLU networks and their implications on generalization capability. Using a teacher-student setting, we discovered a novel relationship between the gradient received by hidden student nodes and the activations of teacher nodes for deep ReLU networks. With this relationship and the assumption of small overlapping teacher node activations, we prove that (1) student nodes whose weights are initialized to be close to teacher nodes converge to them at a faster rate, and (2) in over-parameterized regimes and 2-layer case, while a small set of lucky nodes do converge to the teacher nodes, the fan-out weights of other nodes converge to zero. This framework provides insight into multiple puzzling phenomena in deep learning like over-parameterization, implicit regularization, lottery tickets, etc. We verify our assumption by showing that the majority of BatchNorm biases of pre-trained VGG11/16 models are negative. Experiments on (1) random deep teacher networks with Gaussian inputs, (2) teacher network pre-trained on CIFAR-10 and (3) extensive ablation studies validate our multiple theoretical predictions. Although neural networks have made strong empirical progress in a diverse set of domains (e.g., computer vision (16; 32; 10), speech recognition (11; 1), natural language processing (22; 3), and games (30; 31; 35; 23)), a number of fundamental questions still remain unsolved. How can Stochastic Gradient Descent (SGD) find good solutions to a complicated non-convex optimization problem? Why do neural networks generalize? How can networks trained with SGD fit both random noise and structured data (38; 17; 24), but prioritize structured models, even in the presence of massive noise (27)? Why are flat minima related to good generalization? Why does overparameterization lead to better generalization (25; 39; 33; 26; 19)? Why do lottery tickets exist (6; 7)?In this paper, we propose a theoretical framework for multilayered ReLU networks. Based on this framework, we try to explain these puzzling empirical phenomena with a unified view. We adopt a teacher-student setting where the label provided to an over-parameterized deep student ReLU network is the output of a fixed teacher ReLU network of the same depth and unknown weights ( FIG0 ). In this perspective, hidden student nodes are randomly initialized with different activation regions. (Fig. 2(a ) ). During optimization , student nodes compete with each other to explain teacher nodes. Theorem 4 shows that lucky student nodes which have greater overlap with teacher nodes converge to those teacher nodes at a fast rate, resulting in winner-takeall behavior. Furthermore, Theorem 5 shows that if a subset of student nodes are close to the teacher nodes, they converge to them and the fan-out weights of other irrelevant nodes of the same layer vanishes.With this framework, we can explain various neural network behaviors as follows:Fitting both structured and random data. Under gradient descent dynamics, some student nodes, which happen to overlap substantially with teacher nodes, will move into the teacher node and cover them. This is true for both structured data that corresponds to small teacher networks with few intermediate nodes, or noisy/random data that correspond to large teachers with many intermediate nodes. This explains why the same network can fit both structured and random data ( Fig. 2(a-b) ).Over-parameterization. In over-parameterization , lots of student nodes are initialized randomly at each layer. Any teacher node is more likely to have a substantial overlap with some student nodes, which leads to fast convergence ( Fig. 2(a) and (c), Thm. 4), consistent with (6 ; 7). This also explains that training models whose capacity just fit the data (or teacher) yields worse performance (19).Flat minima. Deep networks often converge to "flat minima" whose Hessian has a lot of small eigenvalues (28; 29; 21; 2). Furthermore, while controversial (4), flat minima seem to be associated with good generalization, while sharp minima often lead to poor generalization (12; 14; 36; 20). In our theory, when fitting with structured data, only a few lucky student nodes converge to the teacher, while for other nodes, their fan-out weights shrink towards zero, making them (and their fan-in weights) irrelevant to the final outcome (Thm. 5), yielding flat minima in which movement along most dimensions ("unlucky nodes") results in minimal change in output. On the other hand, sharp min- Figure 2 . Explanation of implicit regularization . Blue are activation regions of teacher nodes, while orange are students'. (a) When the data labels are structured , the underlying teacher network is small and each layer has few nodes. Over-parameterization (lots of red regions ) covers them all. Moreover, those student nodes that heavily overlap with the teacher nodes converge faster (Thm. 4), yield good generalization performance. (b) If a dataset contains random labels, the underlying teacher network that can fit to it has a lot of nodes. Over-parameterization can still handle them and achieves zero training error.(a) (b) (c) Figure 3 . Explanation of lottery ticket phenomenon . (a) A successful training with over-parameterization (2 filters in the teacher network and 4 filters in the student network). Node j3 and j4 are lucky draws with strong overlap with two teacher node j • 1 and j • 2 , and thus converges with high weight magnitude. (b) Lottery ticket phenomenon: initialize node j3 and j4 with the same initial weight, clamp the weight of j1 and j2 to zero, and retrain the model, the test performance becomes better since j3 and j4 still converge to their teacher node, respectively. (c) If we reinitialize node j3 and j4, it is highly likely that they are not overlapping with teacher node j ima is related to noisy data ( Fig. 2(d) ), in which more student nodes match with the teacher.Implicit regularization . On the other hand, the snapping behavior enforces winner-take-all: after optimization , a teacher node is fully covered (explained) by a few student nodes, rather than splitting amongst student nodes due to over-parameterization. This explains why the same network, once trained with structured data, can generalize to the test set.Lottery Tickets. Lottery Tickets (6; 7) is an interesting phenomenon: if we reset "salient weights" (trained weights with large magnitude) back to the values before optimization but after initialization, prune other weights (often > 90% of total weights) and retrain the model, the test performance is the same or better; if we reinitialize salient weights, the test performance is much worse. In our theory, the salient weights are those lucky regions (E j3 and E j4 in Fig. 3 ) that happen to overlap with some teacher nodes after initialization and converge to them in optimization. Therefore, if we reset their weights and prune others away, they can still converge to the same set of teacher nodes, and potentially achieve better performance due to less interference with other irrelevant nodes. However, if we reinitialize them, they are likely to fall into unfavorable regions which can not cover teacher nodes, and therefore lead to poor performance ( Fig. 3(c) ), just like in the case of under-parameterization. We propose a novel mathematical framework for multilayered ReLU networks. This could tentatively explain many puzzling empirical phenomena in deep learning. . Correlationρ and mean rankr over training on GAUS.ρ steadily grows andr quickly improves over time. Layer-0 (the lowest layer that is closest to the input) shows best match with teacher nodes and best mean rank. BatchNorm helps achieve both better correlation and lowerr, in particular for the CNN case. [5] Simon S Du, Jason D Lee, Yuandong Tian, Barnabas Poczos, and Aarti Singh. Gradient descent learns onehidden-layer cnn: Don't be afraid of spurious local minima. ICML, 2018.[6] Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Training pruned neural networks. ICLR, 2019.[7] Jonathan Frankle, Gintare Karolina Dziugaite, Daniel M Roy, and Michael Carbin. The lottery ticket hypothesis at scale. arXiv preprint arXiv:1903.01611, 2019.[8] Song Han, Jeff Pool, John Tran, and William Dally. Learning both weights and connections for efficient neural network. In Advances in neural information processing systems, pages 1135-1143, 2015.[9] Babak Hassibi, David G Stork, and Gregory J Wolff. Optimal brain surgeon and general network pruning. In IEEE international conference on neural networks, pages 293-299. IEEE, 1993.[10] 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.[ 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 5. Appendix: Mathematical Framework Notation. Consider a student network and its associated teacher network ( FIG0 ). Denote the input as x. For each node j, denote f j (x) as the activation, f j (x) as the ReLU gating, and g j (x) as the backpropagated gradient, all as functions of x. We use the superscript• to represent a teacher node (e.g., j • ). Therefore, g j • never appears as teacher nodes are not updated. We use w jk to represent weight between node j and k in the student network. Similarly, w * j • k • represents the weight between node j• and k • in the teacher network.We focus on multi-layered ReLU networks. We use the following equality extensively: σ(x) = σ (x)x. For ReLU node j, we use E j ≡ {x : f j (x) > 0} as the activation region of node j.Objective. We assume that both the teacher and the student output probabilities over C classes. We use the output of teacher as the input of the student. At the top layer, each node c in the student corresponds to each node c • in the teacher. Therefore, the objective is: DISPLAYFORM0 By the backpropagation rule, we know that for each sample x, the (negative) gradient DISPLAYFORM1 The gradient gets backpropagated until the first layer is reached.Note that here, the gradient g c (x) sent to node c is correlated with the activation of the corresponding teacher node f c • (x) and other student nodes at the same layer. Intuitively, this means that the gradient "pushes" the student node c to align with class c• of the teacher. If so, then the student learns the corresponding class well. A natural question arises:Are student nodes at intermediate layers correlated with teacher nodes at the same layers?One might wonder this is hard since the student's intermediate layer receives no direct supervision from the corresponding teacher layer, but relies only on backpropagated gradient. Surprisingly, the following theorem shows that it is possible for every intermediate layer: DISPLAYFORM2 . If all nodes j at layer l satisfies Eqn. 4 DISPLAYFORM3 then all nodes k at layer l − 1 also satisfies Eqn. 4 with β * kk • (x) and β kk (x) defined as follows: DISPLAYFORM4 Note that this formulation allows different number of nodes for the teacher and student. In particular, we consider the over-parameterization setting: the number of nodes on the student side is much larger (e.g., 5-10x) than the number of nodes on the teacher side. Using Theorem 1, we discover a novel and concise form of gradient update rule: Assumption 1 (Separation of Expectations). DISPLAYFORM5 DISPLAYFORM6 Theorem 2. If Assumption 1 holds, the gradient dynamics of deep ReLU networks with objective (Eqn. 3) is: DISPLAYFORM7 Here we explain the notations. DISPLAYFORM8 We can define similar notations for W (which has n l columns/filters), β, D, H and L FIG4
A theoretical framework for deep ReLU network that can explains multiple puzzling phenomena like over-parameterization, implicit regularization, lottery tickets, etc. 
{"src": "scitldr-AIC_train", "paper_id": "S1xcwNr22E"}