Understanding Multi-phase Optimization Dynamics and Rich Nonlinear Behaviors of ReLU Networks
Authors: Mingze Wang
Chao Ma
Venue: NeurIPS 2023 spotlight (2023)
Keywords: non-convex optimization
training dynamics
neural network
TL;DR: We conduct a complete theoretical characterization of the whole training process and nonlinear behaviors of ReLU networks trained by Gradient Flow on a linearly separable data.

Abstract: The training process of ReLU neural networks often exhibits complicated nonlinear phenomena. 
The nonlinearity of models and non-convexity of loss pose significant challenges for theoretical analysis. Therefore, most previous theoretical works on the optimization dynamics of neural networks focus either on local analysis (like the end of training) or approximate linear models (like Neural Tangent Kernel). 
In this work, we conduct a complete theoretical characterization of the training process of a two-layer ReLU network trained by Gradient Flow on a linearly separable data. In this specific setting, our analysis captures the whole optimization process starting from random initialization to final convergence. 
Despite the relatively simple model and data that we studied, we reveal four different phases from the whole training process showing a general simplifying-to-complicating learning trend.
Specific nonlinear behaviors can also be precisely identified and captured theoretically, such as
initial condensation, saddle-to-plateau dynamics, plateau escape, changes of activation patterns, 
learning with increasing complexity, etc.

Understanding Multi-phase Optimization Dynamics and Rich Nonlinear Behaviors of ReLU Networks
Mingze Wang
Chao Ma Department of Mathematics
School of Mathematical Sciences Peking University
Stanford University Stanford, CA 94305
Beijing, 100081, P.R. China
mingzewang@stu. pkw. edu.
chaoma@s tanfedrdttto...oom edu
Abstract
The training process of ReLU neural networks often exhibits complicated nonlinear phenomena. The nonlinearity models and non-convexity of loss pose significant challenges for theoretical analysis. Therefore, most previous theoretical works the optimization dynamics of neural networks focus either on local analysis (like the end of training) approximate linear models (like Neural Tangent Kernel). In this work, we conduct a complete theoretical characterization of the training process of two-layer ReLU network trained by Gradient Flow linearly separable data. this specific setting, our analysis captures the whole optimization process starting from random initialization final convergence. Despite the relatively simple model and data that we studied, we reveal four different phases from the whole training process showing general paapliffying----ompliaallll trend. Specific nonlinear behaviors can also be precisely identified and captured theoretically, such as initial condensation, saddle-to- to-ptttea dynamics, plateau escape, changes of activation patterns, learning with increasing complexity, etc.
learning
Introduction
Deep learning shows its remarkable capabilities across various fields of applications. However, the theoretical understanding of its great success still has long way to go. Among all theoretical topics, one of the most crucial aspect the understanding of the optimization dynamics of deep neural network (NN), particularly the dynamics produced by Gradient Descent (GD) and its variants. This topic is highly challenging due to the highly non-convex loss landscape and existing works usually work with settings that do not align well with realistic practices. For instance, the extensived studied Neural Tangent Kernel (NTK) theory (Jacot et al., 80 Du et al., 2018; 2019; Zou et al., 2018; Allen-Zhu et al., 2019) proves the global convergence of Stochastic gradient descent (SGD) zero training error for highly wer-paaraeterrieed neural networks; however, the optimization behaviors similar to kernel methods and do exhibit nonlinear behaviors, because neurons remain close to their initialization throughout training.
In reality, however, the training of practical networks exhibit plenty of nonlinear behaviors (Chizat and Bach, 2018; Mei et al., 2019; Woodworth et al., 2020). In the initial stage the training, a prevalent nonlinear phenomenon induced by small initialization is initial condensation (Maennel et al., 2018; Luo et al., 2021), where neurons condense onto a few isolated orientations. At the end of training, NNs trained by GD directionally converge to the KKT points of some constrained max-margin problem (Nacson et al., 2019; Lyu and Li, 2019; Ji and Telgarsky, 2020). However, KKT points are not generally unique, and determining which direction GD converges can be challenging. Nonlinear training behaviors besides initial and terminating stages of optimization are also numerous. For example, for square loss, Jacot al. (2021) investigates the saddle-to-sen to-dddle dynamics where GD traverses a sequence of saddles during training, but it is unclear whether similar behavior can
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

occur for classification tasks using exp-tailed loss. Moreover, while in lazy regime, most activation patterns do not change during training ReLU networks, it remains uncertain when and how activation patterns evolve beyond lazy regime. Additionally, while it is generally conjectured that GID learns functions of increasing complexity (Nakkiran et al., 2019), this perspective has yet to be proven.
As reviewed in Section 2, works have been done to analyze and explain the nonlinear training behaviors listed above. However, due to the complexity of the training dynamies, most existing works only focus on one phenomenon and conduct analysis on certain stage of the training process, Few attempts have been done to derive full characterization of the whole training dynamics from the initialization to convergence, and the settings adopted by these works are usually too simple to capture many nonlinear behaviors (Phuong and Lampert, 2021; Lyu et al., 2021; Wang and Ma, 2022; Boursier et al., 2022).
In this work, make attempt to theoretically describe the whole neural network training dynamics heyond the linear regime, in a setting that many nonlinear behaviors manifest. Specifically, We analyze the training process of a two-layer ReLU network trained by Gradient Flow (GF) on linearly separable data. In this setting, our analysis captures the whole optimization process starting from random initialization to final convergence. Despite the relatively simple model and data that we studied, we reveal multiple phases in training process, and show general simplifying--o-compiicc t0-copllicating learning trend by detailed analysis of each phase. Specifically, by our meticulous theoretical analysis of the whole training process, we precisely identify four different phases that exhibit numerous nonlinear behaviors. In Phase I. initial condensation and simplification occur as living neurons rapidly condense in two different directions. Meanwhile, GF escapes from the saddle around initialization. In Phase II, GF gets stuck into the plateau of training accuracy for a long time, then escapes. In Phase III, significant number of neurons are deactivated, leading to self-ssinllfication of the network, then GF tries to learn using the almost simplest network. In Phase IV, a considerable reactivated, causing self-complication of the network. Finally, GF converges
number of neurons towards an cetiuuiizationdepeetteee direction, and this direction is not even a local max margin direction. Overall, the whole training process exhibits remarkable simpliyiing-to-compicco behavior.
2 Other Related Works
Initial condensation phenomenon studied in (Maennel et al., 2018; Luo et al., 2021; Zhou et al., 2022a;b; Abbe et al., 2022a;b; Chen et al., 2023). Theoretically, Lyu et al. (2021); Boursier et al. (2022) analyze the condensation directions under their settings, which are some types of data average. Additionally, Atanasov et al. (2022) demonstrates that NNs in the rich feature learning regime learn a kernel machine due to the silent alignment phenomenon, similar to the initial condensation.
The end of training is extensively studied for classification tasks. Specifically, for classification with exponentially-taiiee -tiled loss functions, if all the training data can be classified correctly, NNs trained by GD converge to the KKT directions of some constrained max- max-margin problem (Nacson et al., 2019; Lyu and Li, 2019; Chizat and Bach, 2020; Ji and Telgarsky, 2020; Kunin et al., 2023). In (Phuong and Lampert, 2021; Lyu et al., 2021), they analyze entire training dynamics and derive specific convergent directions that only depend on the data. Furthermore, another famous phenomenon in the end of training is the neural collapse (Papyan et al., 2020; Fang et al., 2021; Zhu et al., 2021; Han et al., 2021), which says the features represented by wer-parameterized neural networks for data in same class will collapse to one point, and such points for all classes converge to a simplex equiangular tight frame.
Saddle-to-saddle dynamics are explored for square loss in (Jacot et al., 2021; Zhang et al., 2022: Boursier et al., 2022; Pesme and Flammarion, 2023; Abbe et al., 2023). Furthermore, learning of or frequency- frequency-principle,, is investigated
increasing complexity, also called tumplifying-t-ccomliiai in (Arpit et al., 2017; Nakkiran et al., 2019; Xu et al., 2019; Rahaman et al., 2019).
Beyond lazy regime and local analysis, Phuong and Lampert (2021); Lyu et al. (2021); Wang and Ma (2022); Boursier et al. (2022) also characterize the whole training dynamics and exhibit few of nonlinear behaviors. Specifically, Lyu et al. (2021) studies the training dynamics of GF on Leaky ReLU networks, which differ from ReLU networks because Leaky ReI.U is always activated on any data. (Safran et al., 2022), they studies the dynamics of GF on one dimensional dataset, and characterizes the effective number of linear regions. In (Brutzkus et al., 2017), they studies the
2

---

dynamics of SGD on Leaky ReLU networks and linearly separable dataset. Moreover, Boursier al. (2022) characterizes the dynamics on orthogonally data for square loss. The studies closest to our work are Phuong and Lampert (2021); Wang and Ma (2022), exploring the complete dynamics on classifying orthogonally separable data. However, this data easy to learn, and all the features can be learned rapidly (accurac==100%) in initial training, followed by lazy training (activation patterns do not change). Unfortunately, this simplicity does not hold true for actual tasks on much more complex data, and NNs can only learn some features in initial training, which complicates the overall learning process. Furthermore, we provide a detailed comparison between our results and these works in Section 5. Another related work (Saxe et al., 2022) introduces novel bias of learning dynamics: toward shared representations. This idea and the view of gating networks are enlightening for extending two-layer theory to deep ReLU neural networks.
Our work also investigates the max-margin implicit bias of ReLU neural networks, and related works have been listed above. Although in homogenized neural networks such as ReLU, GD implicitly converges to KKT point of the max-margin problem, it still unclear where it is an actual optimum. A recent work (Vardi et al., 2022) showed that in many cases, the converged KKT point is not even a local optimum of the max margin problem. Besides, there are many other attempts to explain the implicit bias of deep learning ( (Vardi, 2023). Another popular implicit bias is the flat minima bias (Hochreiter and Schmidhuber, 1997; Keskar et al., 2016). Recent studies (Wu et al., 2018; 8;; Blanc et al., 2020; Ma and Ying, 2021; 1; Li et al., 2021; Mulayoff et al., 2021; Wu et al., 2022; Wu and Su, 2023) provided explanations for why SGD favors flat minima and flat minima generalize well.
3 Preliminaries
Basic Notations. We use bold letters for vectors or matrices and lowercase letters for scalars, e.g. I (II, xz)) E Rd and P = (Pty ma xma E Im XM We use (-.-) > for the standard Euclidean inner product between two vectors, and ||- for the 12 norm a vector the spectral norm of matrix. We use progressive representation O Ω θ to hide absolute positive constants. For any positive integer n, let [n] {1...., n). Denote by ((, Σ) the Gaussian distribution with mean μ and covariance matrix Σ, U(S) the uniform distribution on set S. Denote by I{E} the indicator function for an event E.
3.1 Binary Classification with Two-layer ReLU Networks
Binary classification. In this paper, we consider the binary classification problem. We are given n training data S {( y)) C Rd x {=1}. Let f(; 0) be neural network model parameterized by 0, and aim to minimize the empirical risk given by:
n n
((0)=
(v.f(x;;))
(1)
where (()): R + R is the exponential-type loss function (Soudry et al., 2018; Lyu and Li, 2019) for classification tasks, including the most popular classification losses: exponential loss, logistic loss, and cross-entropy loss. Our analysis focuses on the exponential loss {(z) = =- while our method can be extended to logistic loss and cross-entrer cross-entropy loss.
Two-layer ReLU Network. Throughout the following sections, we consider two-layer ReLU neural networks comprising m neurons defined as
m Σ
[wx; 0)
abo x),,
where (2)) max(2,00, 0} is the ReLU activation function, b bm IRd are the weights in the first layer, a1, am are the weights in the second layer. And we consider the case that the weights in the second layer are fixed, which is common setting used in previous studies (Arora al., 2019; Chatterji et al., 2021). We use 0 (b ...... b md to denote the concatenation of all trainable weights.
3

---

3.2 Gradient Flow Starting from Random Initialization
Gradient Flow, As the limiting dynamics of (Stochastic) Gradient Descent with infinitesimal learning rate (Li et al., 2017; 2019), we study the following Gradient Flow (GF) on the objective function (1):
(0 dt E 8 (()(t)) 120.
(2)
Notice that the ReLU is not differentiable at O, and therefore, the dynamics is defined subgra- dient inclusion flow (Bolte et al., 2010). Here, d denotes the Clarke subdifferential, which is a generalization of the derivative for non-differentiable functions. Additionally, address the potential non-uniqueness of gradient flow trajectories, we adopt the definition of solutions for discontinuous systems (Filippov, 2013). For formal definitions, please refer to Appendix B, G, and H.
Random Initialization. We consider GF (2) starting from the following initialization:
by (0)
Lid.
U(S and 0g 8k
K2 for l: [m]]
Vm
Vm
1 for k E [m/2]: - for & E [m] - [m//]]-
Here, 0 <1 < K2 I 1 control the initialization scale. It is worth noting that since the distribution (O, La/d) is close U(Sd-1) in high-dimensional settings, our result can be extended to the initialization by ~ NO0 aa/a/md) with high probability guarantees.
l1d
3.3 Linearly Separable Data beyond Orthogonally Separable
In previous works (Phuong and Lampert, 2021; Wang and Ma, 2022), special case of the linearly separable dataset was investigated, namely "orthooonally separable". A training dataset is orthog- onally separable when (z)) classes. As mentioned in Section 2, in this case, GF can learn all features and achieve 100% training accuracy quickly, followed by lazy training. In this work, we consider data that is more difficult to learn, which leads to more complicated optimization dynamics. Specifically, we consider the following data.
for j in the same class, and (ar,, S 0 for i, in different
Assumption 3.1. Consider the linearly separable dataset S {(xx, y:) Rd R such that (xr,, 9:) = ( 1), E [m+]
(x_,-) -1), i E [n] [n+] where 2+, x__ gd-1 are two data points with a small
angle A E (0, n 7 and n. are the numbers of positive and negative samples, respectively, with n4 + n.. We also use p= n+/n_ to denote the ratio of n. and n.,, which measures the class imbalance. Furthermore, we assume p cos A >> 1.
Remark 3.2. We focus on the training dataset satisfying Assumption 3.1 with a small < 1. The margin of the dataset is sin(A/ /2), which implies that the separability of this data is much weaker than that of orthogonal separable data. Additionally, the condition p cos A merely requires slight imbalance in the data. These two properties work together to produce rich nonlinear behaviors during training.
Characterization of Four-phase Optimization Dynamics
In this section, we study the whole optimization dynamics of GF (2) starting from random initialization when training the two-layer ReLU network on linearly separable dataset satisfying Assumption 3.1 and using the loss function (1). To begin with, introduce some additional notations.
Additional Notations. First, we identify several crucial deta-dependent directions under Assumption 3.1. These include two directions that are orthogonal to the data, defined as x
and + 22 -mp.-mm |++ (.4. (#+*=-)=_1) which satisfy (x+, , x..) (x x O. Additionally, we define the label-average data direction as μ == म where z = 1 Σn
i= 34 One can verify that (1,, x4) > 0 and (ju, x ) under the condition cos A 1. In Figure 3, we visualize these directions.
Second, we use the following notations to denote important quantities during the GF training process. We denote the prediction x4 and x_ by f+(t) := f(x+ (()), f-(t) == f(x_;0(t) We use

---

Ace(t): ;= Ei= Hy: ((t) > 0 to denote the training accuracy at time t. For each neuron E mm] we use wx(() b(t) [[[()] and Px((t) := ||b(t)]l to denote its direction and norm. respectively. To capture the activation dynamics of each neuron & E [m)] on each data, we use sgng (t) = sgm (bx(t), (t), x+)) ) to record whether the k-th neuron is activated with respect to 2., and sgn, (t) = sgm (b& (t),
defined similarly, which we call ReLU activation patterns.
4.1 A Brief Overview of four-phase Optimization Dynamics
We illustrate different phases in the training dynamics by numerical example. Specifically, we train a network on the dataset that satisfies Assumption 3.1 with 4 and A = x/15. The directions and magnituees of the neurons at some important times are shown in Figure 1, reflecting four different phases the training behavior and activation patterms. More experiment details and results can be found in Appendix A.I.
t
(b) f 200
(c) t 50000
(d) 60000
(c) 150000
Figure 1: These figures visualize (in polar coordinates) the projections of all neurons (b. ke|ml
onto the 2d subspace span(x+. + - during training. Each purple star represents a positive neuron (Ie E [m/22), while each brown star represents a negative neuron (It E [m] - [m/2]). Additionally, the directions of 20 _ #t, a=,, la are plotted in blue, orange, green, red and pink colors, respectively. The complete version of these figures Figure 4 in Appendix A.
From Fig ((a) (b) is the Phase I of the dynamics, marked by condensation of neurons. Although the initial directions are random, we see that all neurons are rapidly divided into three categories: living positive neurons (k E K.) and living negative neurons (k KC_) condense in one direction each (μ and ). while other neurons (k K4 UK_ are deactivated forever. From the perspective of loss landscape. GF rapidly escapes from the saddle near where the loss gradient vanishes.
From Fig (bb) to (c) is the Phase II of the dynamics, in which GF gets stuck into plateau with P for long time Tplat before escaping. Once the dynamics escapes from the training accuracy 1+p
plateau, the training accuracy rises to a perfect 100%. Moreover, activation patterns do not change in this phase.
From Fig I(C) to (d) is the Phase III of the dynamics. The phase transition from phase II to phase rapidly, while other
III sees rapid deactivation of all the living positive neurons k K4 activation patterns are unchanged. This leads to a simpler network in phase III, in which only living positive neurons (in KC+) predict +. and only living negative neurons (in K_. predict x_.. Hence, in this phase the GF tries to learn the training data using almost the simplest network by only changing the norms of the neurons.
Finally, Fig 1(d) to (e) shows Phase IV, starting from another "phase transition" when all the living negative neurons (k E K.)) reactivate simultaneously x+. This leads to a more complicated network. After the phase transition, the activation patterns no longer change, and the neurons eventually converges towards some specific directions dependent on both data and initialization. Additionally, this direction is not even the local optimal max margin direction.
Overall, the whole dynamics exhibit simplifying- to--t----ooo to-complicating learning trend.
In the following four subsections, present meticulously detailed and comprehensive depiction of the whole optimization dynamics and nonlinear behaviors. For clarity, in Figure 2, we first display the timeline of our dynamics and some nonlinear behaviors.
In Appendix A.2, we further validate our theoretical bounds on the key time points in Figure numerically. Additionally, in Appendix A.3, we relax the data Assumption 3.1 by perturbing the
5

---

θ
(1+
K2
(
Phase I
Phase II
Phase III
Phase IV
T
Tplat
Ti
Tm
00 t
Figure 2: Timeline of the four-phase optimization dynamics, containing some key time points Ti Tu, Tim, Tplat and their theoretical estimates, and some basic nonlinear behaviors: @ initial condensation, @ saddle escape, getting stuck in plateau, 4 plateau escape, @ neuron deactivation, @ neuron reactivation, @ initialization deeeeedditiondeeeeeentt directional convergence. Notice D~~ are only some basic nonlinear behaviors. Moreover, @++ is saddle-to to-ptttau, O+6+0 is simplifying-to complicating.
data with random noise, and our experimental results illustrate that similar four-phase dynamics and nonlinear behaviors persist.
4.2 Phase 1. Initial Condensation and Saddle Escape
Let Ti 10
/ /0/2 and we call E [0, Ti) Phase I. The theorem below our main result in Phase I.
Theorem 4.1 (Initial Condensation). Let the width m 52 (log(1/6)), the initialization K1, K2 (1) and R1/K2 = O(A²). Then with probability at least 1 6, the following results hold at Ti:
(S1) Let K4 be the index set of living positive neurons at Ti, i.e. K+ == {k E [m/2] agn (Ti) 1 or sgny (Ti) 13. Then, (i) 0.21m S KK+ (Ti)l S 0.29m. Moreover, for any K.+, (ii) its norm small but significant: (Ti(Ti) θ
(V
Nika
(iii) direction is strongly aligned with p.:
m 0.55);
(w))(T), pb 2 1 - O (VKiR2) - O ((K) /x2)
(iv) agnt (Ti) =sgn, (Ti) 1
(S2) Let K__ be the index set of living negative neurons Tí, i.e. K_ == [k E [m] [m//] g (Ti) or sgn, (Ti) 1}. Then, (i) 0.075m I |K_| I 0.205m. Moreover, for any K_,, (ii) its norm tiny: pk (Ti) O
2 (iii) its direction is aligned with P
7/m
x (w (Ti), xt) 2 1 ((
Ne R.
A )1.6): (iv) agng (Ti) = 1, but sgnj (Ti) =0. 0.
(83) For other neuron & K.4 U U.K, dies and remains unchanged during the remaining training process: sgn (t) S 0, sgn (t) S 0, by (t) = by (Ti), Vt 2 TІ.
P (S4). f+ (Ti) = (#2) . (Ti) = θ (12 k2), and Acc(Ti) = I+F
Initial condensation and simplification. Theorem 4.1 (SI)(S2)S33) show that, after short time Ti T1=0 ((V/1//K2) all neurons are implicitly simplified to three categories: K.+ K._ and others. The living positive neurons i E K__ align strongly with μu, and the living negative neurons & E K_ align with 4 and lie on the manifold orthogonal to x4. Other neurons die and remain unchanged during the remaining training process. Moreover, we also estimate tight bounds for [KC, and |KC J. Actually, K1 /1/K2 O(1) can ensure Theorem 4.1 and initial condensation hold (please refer to Appendix C), and we write /k/ = ( here to ensure that the dynamics of later phases hold. In Phase I, the dynamics exhibit fast condensation phenomenon, i.e., in addition to dead neurons, living positive and negative neurons condense in one direction each.
The network is initially close to the saddle point at 0 (where the loss gradient vanishes). However, Theorem 4.1 (S1) reveals that despite being small, there a significant growth in the norm of living positive neuron k E KC+ from O(K1/ /m) to (K/K/// /m) and the predictions also experience substantial growth (S4). This means that GF escapes from this saddle rapidly. Furthermore, it is worth noting that initial training accuracy randomly be O, -_ T+p' or 1. However, after Phase the training accuracy reaches Acc(Ti) 1-p which we will prove as plateau in the next subsection. Therefore, Phase exhibits saddle-to-plateau dynamics.
p
Remark 4.2. Throughout the following subsections, we call the neuron & E K4+ the "living positive neuron", the neuron k E K__ the "living negative neuron", and the neuron k & K4 U K__ the

---

"dead neuron".. Moreover, we denote m := |K_||, m-
== |K_|| and a ==
IR m
Notice that
Theorem 4. (.1(S1)SS2) guarantee that 0.975
S a -
0.205
< 1.
0.29
0.21
Remark 4.3. The results the following subsections are based on the occurrence the events in
Theorem 4.1 and with the same settings as Theorem 4.1. So they all hold with probability at least 1 6-
Please refer Appendix C for the proof of Phase I.
4.3 Phase II. Getting Stuck in and Escaping from Plateau
In this phase, we study the dynamics before the patterns of living neurons change again after Phase I. Specifically, we define
Tu = in > T 3E E K.+ UK_, sgat (1) + sgnt (Ti) or sgaz (t) & sgnz (Ti)),
and call / E (Ti, Tu] Phase II.
Theorem 4.4 (End of Phase II). (S1) Ti = A
T-n KEAA
(S2) ((0(TT)) θ T
(S3) One of living positive neuron ko K.+ precisely changes its pattern on a at Tit: lim sgm (t) = 1 and lim sgn (t) 0, while all other activation patterns remain unchanged. T
Recalling the results Theorem 4.1, during Phase II, the activation patterns do not change with sgn; (4) agng (t) for k E KC+ and agn (t) 0, agn, (t) 1 for l: E K... Theorem 4.4 demonstrates that at the end Phase II, except for one living positive neuron kn K.+ precisely changes its pattern x_, all other activation patterns remain unchanged.
Theorem 4.5 (Plateau). We define the hitling time Tplat itl E [Ti. Acc(l) = 1}. Then, (S2) VI E [Ti, Tpaat Acc(()=
(S1) Tplat θ
I+p' (S3) VI E (Tplat, Tn), Acc(l) = 1.
Plateau of training accuracy. According to Theorem 4.5, during Phase II, the training accuracy gets stuck in a long plateau Th. which lasts for O (53 time. However, once escaping from this plateau, the training accuracy rises to 100%. It is worth noting that this plateau is essentially induced by the dataset. All that's required is only mild imbalance (p is slightly greater than such that p cos A > 1) and small margin (in( of two data classes. Notably, if the dataset has an extremely tiny margin (A - 0), then the length of this plateau will be significantly prolonged (Tptar + +o0), which implies how the data separation can affect the training dynamics. Additionally, using a smaller initialization scale K1 the input layers cannot avoid this plateau.
Please refer to Appendix D for the proof of Phase II.
4.4 Phase III. Simplifying by Neuron Deactivation, and Trying to Learn by Simplest Network
Building upon Phase II, we demonstrate that within a short time, all the living positive neurons K4, change their activation patterns, corresponding to "phase transition". Specifically, define
TP == inf (1> Th : Vk E K4,, sgng (1) = =0,,
and we call E (Tu, T the phase transition from Phase II to Phase III.
Theorem 4.6 (Phase Transition). (S1) TPT = 1 O K kij
Ti:: (S2) sgnj (TFT)) = 1 and sgn, (TPT) = for any k E K4:; sgn (TPT) = 0 and sgn, (TP = for any & K...
Neuron deactivation. As shown in Theorem 4.6 (S2), after the phase transition, all the living positive neurons k E K++ undergo deactivation for x_, i.e., sgn, (t) changes from 1 to 0, while other activation patterns remain unchanged. Furthermore, Theorem 4.6 (S1) reveals that the phase transition is completed quite quickly by using sufficiently small initialization value K1, R2. A smaller initialization value leads to more precise initial condensation urs (Ti) R p, causing all living positive neurons to remain closer together before Ti and thus changing their patterns nearly simultancously.
7

---

Self-simplifying,. As result, the network implicitly simplifies itself through the deactivation behavior. At T only living negative neurons E K+ are used for predicting on a.. i.e. v EkER_ ((bbx(""") x.)))) In contrast, during Phase II, both living positive vm Σkek, (t)
f- f-(2
and living negative neurons jointly predict on æ-, i... (t) = =2 82
ΣKEK_ (tb x=)). As indicated in Table I, two classes activation patterns are simplified ym
from (1, to (0, 0), while others do not change.
After this phase transition, we study the dynamics before the pattemss of living neurons change again. Specifically, we define
Tm = in THT 3K KC+ sgn (t) + sgn (TTT) or sgn (t) + sgmk (TT )}
and call & (Tn, Tim] Phase III. Theorem 4.7 (End of Phase III), Tiu = (1+
Learning by simplest network. During / E (T Tin), all activation patterns do not change. This ensures that (() v ExER, (((ba (1), while f-(()
K2 ΣKEK_ (I), x))
Additionally, by using sufficiently small Kl, the neurons in K.+ and K_ keep close together re- spectively before TiII. making the network close a simple two-neuron network consisting of one positive neuron and one negative neuron. Please refer to Appendix E for more details. Furthermore, this pattern scheme almost the "simplest" way ensure binary classification: the living positive neurons only predict positive data while the living negative neurons only predict negative data a... Therefore, GF tries to learn by this almost simplest network this phase.
Please refer to Appendix E for the proof of Phase III.
4.5 Phase IV. Complicating by Neuron Reactivation, and Directional Convergence
Phase IV begins with an instantancous phase transition at time Tin-
Theorem 4.8 (Phase Transition). All living negative neuron k E K_ simultaneously change their patterns x4 at Tim: lim s (t) 0, lim sgn (t) 1, while others remain unchanged.
+
t-
Neuron reactivation. According to Theorem 4.8, all of living negative neurons k E K. reactivate simultaneously x4 at Tin: sgną (4) changes from 0 to 1, while other activation patterns remain
unchanged.
Self- Colf-Compliaaing. Along with the reactivation behavior, GF implicitly complicates itself. In Phase III, only living negative neurons & E KC+ are used to predict on xt, i.c., f+(() = Vm Σkek ((bb(t), In contrast, after the phase transition at Tim. both living positive and living negative neurons jointly predict on xT, i.c (t)
K2 Vm ΣkEK, ((bb(t)), x-))
Vm ΣkEk ((bbx()) a+)). As indicated in Table 1, two classes of activation patterns are compli- cated from (0, 0) to (0, 1), while others do not change.
In this phase, we study the dynamics before activation patterns change again after the phase transition in Theorem 4.8. We define the hitting time:
Tiv == in Ti 3K E KC+ UKK, agn + lim sgn, (s) or sgn, (t) * lim
sgnū (s)),
s
s-2
and we call E (Tm,, Tivl Phase IV. Theorem 4.9 (Phase IV). (S1) Tiv = toc Moreover, for any t >> Til (S2) all activation patterns do not change; (S3) the loss converges with ((e(t)) =
p a a + -1-A2(t-Tin))
Theorem 4.9 illustrates that all activation patterns never change again after the phase transition at Tin with sgn (t) = 1, sgng (t) = 0 for any E K4 and sgn, (t) = sgn; (t) = 1 for any & K_. Additionally, the loss converges with the polynomial rate (1/k3AA)) Furthermore, we present the following theorem about the convergent direction of each neuron.
8

---

Theorem 4.10 (Directional Convergence). The limit lim
o(1)
exists and denoted by 0
t-+0c [
(6, ..... 6 gmd-11 Moreover, for any & K UK_, by = (ii) for any k K+ by
2+ = C( a cos A); ffrr)for any k E K_ by = v_ = C((1+ +01 4 x- x+ where
sin"
C> 0 is scaling constant such that |0 2 1. (iv) Additionally, (0 { > 0.
Initialization-deeendee
Directional Convergence. As an asymptotic result, Theorem 4.10 provides the final convergent direction of GF. All living positive neurons (k: E K.+) directionally converge to 24 || x with (u+,20 ) > and (v+. x = 0. while all living negative neurons (k: KK_)
directionally converge to v E s -_ with (v_, xx4 > 0 and (v_, .- > 0. is worth noting that v. directly depends not only on the data but also on the ratio a = | (defined in Remark 4.2). Recalling the results in Phase I, lies in a certain range with high probability; but it is still random variable due to its dependence on random initialization. Different initializations may lead to different values |/|]/ at the end of Phase I, eventually causing different convergent directions in Phase IV.
Direction. Lastly, we study the implicit bias of the final convergence rate. According to Lyu and Li (2019); Ji and Telgarsky (2020) and our results above, 0 in Theorem 4. 10 must be a KKT direction of some max- max-margin optimization problem. However, it is not clear whether actual optimum of this problem. Surprisingly, in next Theorem,
Von-(Local)-Max-Mal
the direction 0 is actually demonstrate that the final convergent direction not even a local optimal direction of this problem, which enlightens us to rethink the max margin bias of ReLU neural networks.
Theorem 4.11 (Implicit Bias). The final convergent direction 0 (in Theorem 4.10) is a KKT direction
of the max-margin problem min |101|2 8.1. y: 0) 2 1, E [n]] However, 0 is not even a local
optimal direction of this problem.
Please refer to Appendix F for the proof of Phase IV.
5 Discussion and Comparison on Nonlinear Behaviors
Throughout the whole training process in Section 4, we divide the phases based the evolution of ReLU activation patterns. During Phase I, as well as the beginning of Phase II and III, numerous activation patterns undergo rapid changes. Table 1 summarizes the evolution of activation patterns for all living neurons after Phase I. These results are also numerically validated in Figure 1.
Table 1:
The evolution of two classes of activation patterns of living neurons after Phase I. As for other two classes, sgn, (t) (A K4) and sgn, (t) (k KC-), they remain equal to 1 after Phase I.
E Tu)
t (Tit, " or 0
t (TT... Tur)
(Tir, +o0)
sgn (t) (K E K.+) sgn (1) (KE
0
0
Sagpifyinngt--CCopiiaaaatgg In phase I, GF simplifies all the neurons from random directions into three categories: living positive neurons K4 and living negative neurons K_ condense in one direction each, which other neurons are deactivated forever. After Phase I, as shown in Table 1,
the two classes of activation patterns change from (1,0) simplity (0, 0) complicate
(0, 1), while other patterns remain unchanged. Therefore, the evolution of activation patterns exhibits a simplifying- to-complicating learning trend, which also implies that the network trained by GF learn features in increasing complexity.
Comparison with NTK. In the lazy regime such NTK, most neurons keep close to the initialization and most activation patterns do not change during training. Specifically, for any training data C;, (0), xx))} = o(1), Vt > (Du et al., 2018). However, our work stands out from lazy regime as activation patterns undergo numerous changes during training. In Phase I, initial condensation causes substantial changes in activation patterns, which similarly observed in (Phuong and Lampert, 2021). Furthermore, even after Phase I, there are notable modifications in activation patterns. As shown in Table 1, the proportion of changes in
1 Etg(m ml ((sgn((b(t)) xx)) # sgn( (b), m

---

activation patterns for any given training data is the (1), as compared with the o(1) in NTK
regime. Specifically, at any t > Tiu, J. _ _ (t) o sgnj (Ti)} = ||||| = (1) and @(1). On the other hand, in our analysis, the m Exefm Ilsgn (t) * agmg (Ti) = m |
requirement on the network's 's width m is only m = ((log(1/6)) (Theorem 4.1), regardless of data parameters p, A, while NTK regime requires much larger width m = ((log(p/8)/49 (Ji and Telgarsky, 2019).
Comparison with Phuong and Lampert (2021); Lyu et al. (2021); Wang and Ma (2022); Boursier et al. (2022). Beyond lazy regime and local analysis, these works also characterize the entire training dynamics and analyze few nonlinear behaviors. Now we compare our results with these works in detail. (i) While Lyu et al. (2021) focuses on training Leaky ReLU NNs, our work and the other three papers study ReLU NNs. It is worth noting that the dynamics of Leaky ReLU NNs differ from ReLU due to the permanent activation of Leaky ReLU (a)()) 2 a > 0). (ii) Initial condensation is also proven in (Lyu et al., 2021; Boursier et al., 2022), and the condensation directions are some types of data averages. In our work, neurons can aggregate towards not only the average direction j4, but also another direction a Moreover, we also estimate the number of neurons that condense into two directions. (iii) Saddle-to-sadee where the second saddle is about training loss and caused by incomplete fitting. However, our work focus on classification with exponential loss and exhibit a similar saddlc-to- -addle-to-plateuu dynamics, where the plateau is about training accuracy, caused by incomplete feature learning. (iv) Phased feature learning. In (Phuong and Lampert, 2021; Wang and Ma, 2022), all features can be rapidly learned in Phase (accuracy= 100%), followed by lazy training. However, for practical tasks on more complex data, NNs can hardly learn all features in such short time. In our work, the data is more difficult to learn, resulting in incomplete feature learning in Phase (accuracy< 100%). Subsequently, NNs experience long time to learn other features completely. Such multi-phase feature leaning dynamics are closer to practical training process. (v) Neuron reactivation and deactivation. For ReLU NNs, The evolution of activation patterns is one of the essential causes of nonlinear dynamics. In (Phuong and Lampert, 2021; Wang and Ma, 2022), activation patterns only change rapidly in Phase I, after which they remain unchanged. In (Boursier et al., 2022), their lemma 6 shows that their dynamics lack neuron reactivation. However, in our dynamics, even after Phase I, our dynamics exhibit significant neuron deactivation and reactivation discussed in Table 1. (vi) The final convergent directions are also derived in (Phuong and Lampert, 2021; Lyu et al., 2021; Boursier et al., 2022), which only depend on the data. However, in our setting, the convergent direction is more complicated, determined by both data and random initialization. (vii) Furthermore, our four -hare dynamics demonstrate the whole evolution of activation patterns during training and reveal general simplifying-to-comeee to-compliaating learning trend.
dynamics are proven in (Phuong and Lampert, 2021) for square loss,
In summary, our whole four-phase optimization dynamics capture more nonlinear behaviors than these works. Furthermore, we conduct a more thorough and detailed theoretical analysis of these nonlinear behaviors, providing more systematic and comprehensive understanding.
6 Conclusion and Future Work
In this work, we study the optimization dynamics of ReLU neural networks trained by GF on a linearly separable data. Our analysis captures the whole optimization process starting from random initialization to final convergence. Throughout the whole training process, we reveal four different phases and identify rich nonlinear behaviors theoretically. However, theoretical understanding of the training of NNs still has a long way to go. For instance, although we conduct fine-grained analysis of GF, the dynamics of GD are more complex and exhibit other nonlinear behaviors such as progressive sharpening and edge of stability (Wu et al., 2018; Jastrzębski et al., 2019; Cohen et al.. 2021; Ma et al., 2022: Li et al., 2022; Damian et al., 2022: Zhu et al.. 2022: Ahn et al., 2022a:b). Additionally. unlike GD. SGD uses only
of data and injects noise (Zhu et al., 2019; Thomas et al., 2020; Feng and Tu, 2021: Liu et al., 2021: Ziyin et al., 2022; Wu al., 2022; Wojtowytsch, 2023; Wang and Wu, 2023) in each iteration, which can have a pronounced impact on the optimization dynamies and nonlinear behaviors. Better understanding of the nonlinear behaviors during GD or SGD training is an important direction of future work.
10

---

Acknowledgments and Disclosure of Funding
We thank Prof. Weinan E, Prof. Lei Wu, Prof. Zhi-Qin John Xu and anonymous reviewers for helpful suggestions. Mingze Wang is supported in part by the National Key Basic Research Program of China: 2015CB856000.
References
Emmanuel Abbe, Enric Boix Adsera, and Theodor Misiakiewicz. The merged-staircase property: necessary and nearly sufficient condition for sgd learning sparse functions on two-layer neural PMLR, 2022a.
networks. In Conference on Learning Theory, pages
Emmanuel Abbe, Elisabetta Cornacchia, Jan Hazla, and Christopher Marquis. An initial alignment between neural network and target is needed for gradient descent to learn. International Conference on Machine Learning, pages 33 52-52. PMLR, 2022b.
Emmanuel Abbe, Enric Boix- Adsera, and Theodor Misiakiewicz. Sgd learning on neural networks: leap complexity and saddle-to-sadde dynamics. arXiv preprint arXiv:2302. 1055, 2023.
Kwangjun Ahn, Sébastien Bubeck, Sinho Chewi, Yin Tat Lee, Felipe Suarez, and Yi Zhang. Learning threshold neurons via the" edge of stability". arXiv preprint arXiv:2212.077666 2022a.
Kwangjun Ahn, Jingzhao Zhang, and Suvrit Sra. Understanding the unstable convergence of gradient descent. International Conference on Machine Learning, pages 247-257. PMLR, 2022b.
Zeyuan Allen-Zlhi Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. In International Conference on Machine Learning, pages 242-252. PMLR, 2019.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine- Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. In International Conference on Machine Learning, pages 322-332. PMLR, 2019.
Devansh Arpit, Stanistaw Jastrzebski, Nicolas Ballas, David Krueger, Emmanuel Bengio, Maxinder Kanwal, Tegan Maharaj. Asja Fischer, Aaron Courville, Yoshua Bengio, et al. A closer look at memorization in deep networks. In International conference on machine learning, pages 233-242.
PMLR, 2017.
Alexander Atanasov, Blake Bordelon, and Cengiz Pehlevan. Neural networks as kemee learners: The silent alignment effect. International Conference on Learning Representations, 2022.
Guy Blane, Neha Gupta, Gregory Valiant, and Paul Valiant. Implicit regularization for deep neural networks driven by an ornstein-uhlenheck like process. In Conference on learning theory, pages 483-513. PMLR, 2020.
Jérôme Bolte, Aris Daniilidis, Olivier Ley, and Laurent Mazet. Characterizations lojasiewicz inequalities: subgradient flows, talweg, convexity. Transactions of the American Mathematical Society, 362(6)3331-3336) 2010.
Etienne Boursier, Loucas Pillaud- Vivien, and Nicolas Flammarion. Gradient flow dynamics of shallow relu networks for square loss and orthogonal inputs. Advances in Neural Information Processing Systems, 2022.
Pillaud-Vivien,
Alon Brutzkus, Amir Globerson, Eran Malach, and Shai Shalev-Shwartz. Sgd learns over- parameterized networks that provably generalize on linearly separable data. arXiv preprint 1rXiv:1710.10174 2017.
Niladri Chatterji, Philip M Long, and Peter I. Bartlett. When does gradient descent with logistic loss find interpolating two-layer networks? Journal of Machine Learning Research, 22(159):1-48 2021.
Zhengan Chen, Yuqing Li, Tao Luo, Zhangchen Zhou, and Zhi-Qin John Xu. Phase diagram of initial condensation for two-layer neural networks, arXiv preprint arXiv:2303.06560 2023.
11

---

Lenaic Chizat and Francis Bach. On the global convergence of gradient descent for over- parameterized models using optimal transport. Advances in neural information processing systems, 31, 2018.
Lenaic Chizat and Francis Bach. Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss. In Conference on Learning Theory, pages 1305-1338. PMLR, 2020.
Francis H Clarke, Yuri Ledyaev, Ronald Stern, and Peter Wolenski. Nonsmooth analysis and control theory, volume 178. Springer Science & Business Media, 2008.
Jeremy M Cohen, Simran Kaur, Yuanzhi Li, J Zico Kolter, and Ameet Talwalkar. Gradient descent on neural networks typically occurs at the edge stability. arXiv preprint Sxiv:2103.00066 2021.
Alex Damian, Eshaan Nichani, and Jason D Lec. Self-stabilization:: The implicit bias of gradient descent at the edge of stability. arXiv preprint arXiv:2209, 15594, 2022.
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In International Conference Machine Learning, pages 1675-1685. PMLR, 2019.
Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. arXiv preprint arXiv:1810.02054, 2018.
Joydeep Dutta, Kalyanmoy Deb, Rupesh Tulshyan, and Ramnik Arora. Approximate kkt points and proximity measure for termination. Journal of Global Optimization, 56(4):1463- 1499, 2013.
Cong Fang, Hangfeng He, Qi Long, and Weijie J Su. Exploring deep neural networks via layer-peeled model: Minority collapse in imbalanced training. Proceedings of the National Academy of Sciences, 118(43))e210301 18, 2021.
Yu Feng and Yuhai Tu. The inverse variance-flatness relation in stochastic gradient descent is critical for finding flat minima. Proceedings of the National Academy of Sciences, 118(9), 2021.
Aleksei Fedorovich Filippov. Differential equations with discontinuous righthand sides: control systems, volume 18. Springer Science & Business Media, 2013.
XY Han, Vardan Papyan, and David L Donoho. Neural collapse under mse loss: Proximity and dynamics on the central path. arXiv preprint w:Xiv:2106.0207, 2021.
Sepp Hochreiter and Jürreen Schmidhuber. Flat minima. Neural compulation, 9(1):144,, 1997.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. arXiv preprint 18Xiv:8806.0777 2018.
Arthur Jacot, François Ged, Berfin Şimşek, Clément Hongler, and Franck Gabriel. Saddle-to-saddle dynamics in deep linear networks: Small initialization training, symmetry, and sparsity. arXiv preprint arXiv:2 0022110..15509 15933, 2021.
Stanislaw Jastrzebski, Zachary Kenton, Nicolas Ballas, Asja Fischer, Yoshua Bengio, and Amos Storkey. On the relation between the sharpest directions of dnn loss and the sgd step length. International Conference Learning Representations, 2019,
Ziwei Ji and Matus Telgarsky. Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow relu networks. arXiv preprint arXiv:1909.1 12292, 2019.
Ziwei Ji and Matus Telgarsky. Directional convergence and alignment in deep learning. Advances in Neural Information Processing Systems, 13:17176-17188 2020.
Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Peter Tang. On large-batch training for deep learning: Generalization gap and sharp minima. In International Conference on Learning Representations, 2016.
Daniel Kunin, Atsushi Yamamura, Chao Ma, and Surya Ganguli. The asymmetric maximum margin bias of quasi-homogeneeus neural networks. International Conference on Learning Representations, 2023.
12

---

Qianxiao Li. Cheng Tai, and Weinan E. Stochastic modified equations and adaptive stochastic gradient algorithms. International Conference on Machine Learning, pages 2101-2110. PMLR, 2017.
Qianxiao Li, Cheng Tai, and Weinan Stochastic modified equations and dynamics of stochastic gradient algorithms i: Mathematical foundations. The Journal of Machine Learning Research, 20 (1):1474-1520, 2019.
Zhiyuan Li, Tianhao Wang, and Sanjeev Arora. What happens after sgd reaches zero loss?-a mathematical framework. arXiv preprint arXiv:2110.06914.22 2021.
Zhouzi Li. Zixuan Wang, and Jian Li. Analyzing sharpness along gd trajectory: Progressive sharpening and edge of stability. arXiv preprint arXiv:2207. 2022.
Kangqiao Liu, Liu Ziyin, and Masahito Ueda. Noise and fluctuation of finite learning rate stochastic gradient descent. In International Conference on Machine Learning, pages 7045-7056. PMLR, 2021.
Tao Luo, Zhi-Qin John Xu, Zheng Ma, and Yaoyu Zhang. Phase diagram for two-layer relu neural networks infinite-width limit. The Journal of Machine Learning Research, 22(1):332733373, 2021.
Kaifeng Lyu and Jian Li. Gradient descent maximizes the margin of homogeneous neural networks. arXiv preprint 1eti1996660000 2019.
Kaifeng Lyu, Zhiyuan Li, Runzhe Wang, and Sanjeev Arora. Gradient descent on two-layer nets: Margin maximization and simplicity bias. Advances in Neural Information Processing Systems, 34, 2021.
Chao Ma and Lexing Ying. On linear stability of sgd and input of neural networks. Advances in Neural Information Processing Systems, 34:16805 10666-86811,,,,11111111111111111 17, 2021.
Chao Ma. Daniel Kunin, Lei Wu, and Lexing Ying. Beyond the quadratic approximation: the multiscale structure of neural network loss landscapes. arXiv preprint arXiv:2204. 2022.
Hartmut Maennel, Olivier Bousquet, and Sylvain Gelly, Gradient descent quantizes relu network features. arXiv preprint arXiv:7803.0836) 2018.
Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Mean-field theory of two-layers neural networks: dimension free bounds and kernel limit. In Conference on Learning Theory, pages 2388-2464. PMLR, 2019.
Rotem Mulayoff, Tomer Michaeli, and Daniel Soudry. The implicit bias of minima stability: A view from function space. Advances in Neural Information Processing Systems, 34:17749- 2021.
Mor Shpigel Nacson, Suriya Gunasekar, Jason Lee, Nathan Srebro, and Daniel Soudry. Lexicographic and depth-sensitive margins in homogeneous and non-homogeneous deep models. In International Conference on Machine Learning, pages 4683-4692. PMLR, 2019.
Preetum Nakkiran, Gal Kaplun, Dimitris Kalimeris, Tristan Yang, Benjamin L Edelman, Fred Zhang, and Boaz Barak. Sgd on neural networks learns functions of increasing complexity. arXiv preprint arXiv:1905.1 10000.11604.. 1604, 2019.
Vardan Papyan, XY Han, and David L Donoho. Prevalence of neural collapse during the terminal phase of deep learning training. Proceedings of the National Academy of Sciences. 117(40): 24652-24663, 2020.
Scott Pesme and Nicolas Flammarion. Saddle-to-saddle dynamics in diagonal linear networks. arXiv preprint arXiv:2304. 004888 2023.
Mary Phuong and Christoph H Lampert. The inductive bias of relu networks on orthogonally separable data. In International Conference Learning Representations, 2021.
13

---

Aristide Rahaman, Nasim xd Baratin, Devansh Arpit, Felix Draxler, Min Lin, Fred Hamprecht, Yoshua Bengio, and Aaron Courville. On the spectral bias of neural networks. In International Conference on Machine Learning, pages 5301-5316 PMLR, 2019.
Itay Safran, Gal Vardi, and Jason D Lee. On the effective number of linear regions in shallow univariate relu networks: Convergence guarantees and implicit bias. Advances in Neural Information Processing Systems, 35:32667-32611 2022.
Andrew Saxe, Shagun Sodhani, and Sam Jay Lewallen. The neural race reduction: Dynamics of abstraction in gated networks. In International Conference on Machine Learning, pages 19287- 19309. PMLR, 2022.
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The implicit bias of gradient descent on separable data. The Journal of Machine Learning Research, 19(1): 2822-2878, 2018.
Valentin Thomas, Fabian Pedregosa, Bart Merriënboer, Pierre-Antoine Manzagol, Yoshua Bengio, and Nicolas Le Roux. On the interplay between noise and curvature and its effect on optimization and generalization. In International Conference on Artificial Intelligence and Statistics, pages 3503-3513, PMLR, 2020.
Gal Vardi. On the implicit bias in deep-learning algorithms. Communications of the ACM, 66(6): 86-93, 2023.
Gal Vardi, Ohad Shamir, and Nati Srebro. On margin maximization linear and relu networks. Advances in Neural Information Processing Systems, 0177024-370386 2022.
Mingze Wang and Chao Ma. Early stage convergence and global convergence of training mildly parameterized neural networks. Advances in Neural Information Processing Systems, 2022.
Mingze Wang and Lei Wu. The noise geometry of stochastic gradient descent: quantitative and analytical characterization. arXiv preprint arXiv:2310.0069) 2023.
Stephan Wojtowytsch. Stochastic gradient descent with noise of machine learning type part i: Discrete time analysis. Journal of Nonlinear Science, (3)5):45, 2023.
Blake Woodworth, Suriya Gunasekar, Jason D Lee, Edward Moroshko, Pedro Savarese, Itay Golan, Daniel Soudry, and Nathan Srebro. Kernel and rich regimes in overparametrized models. In Conference on Learning Theory, pages 3635-3673. PMLR, 2020.
Lei Wu and Weijie J Su. The implicit regularization of dynamical stability in stochastic gradient descent. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 37656-37684. PMLR, 2023.
Lei Wu, Chao Ma, and Weinan E. How sgd selects the global minima in parr-paraeeeerized learning: A dynamical stability perspective. Advances in Neural Information Processing Systems, 31: 8279-8288, 2018
Lei Wu, Mingze Wang, and Weijie Su. When does sgd favor flat minima? quantitative characteriza- tion via linear stability. Advances in Neural Information Processing Systems, 2022.
Zhi-Qin John Xu, Yaoyu Zhang, Tao Luo, Yanyang Xiao, and Zheng Ma. Frequency principle: Fourier analysis sheds light deep neural networks. arXiv preprint 19Xv::101 2019.
Yaoyu Zhang, Yuqing Li, Zhongwang Zhang, Tao Luo, and Zhi-Qin John Xu. Embedding principle: A hierarchical structure of loss landscape of deep neural networks. Journal of Machine Learning, 1(1):60-113, 2022. ISSN 2790-2048.
Hanxu Zhou, Zhou Qixuan, Zhenyuan Jin, Tao Luo, Yaoyu Zhang, and Zhi-Qin Xu. Empirical phase diagram for three-layer neural networks with infinite width. Advances in Neural Information Processing Systems, 35:26021-26033 2022a.
Hanxu Zhou, Zhou Qixuan, Tao Luo, Yaoyu Zhang, and Zhi-Qin Xu. Towards understanding the condensation of neural networks at initial training. Advances Neural Information Processing Systems, 35:2184-2196 2022b.
14

---

Xingyu Zhu, Zixuan Wang, Xiang Wang, Mo Zhou, and Rong Ge. Understanding edge-of-stability training dynamics with minimalist example. arXiv preprint arXiv:2210.03294, 2022.
Zhanxing Zhu, Jingfeng Wu, Bing Yu, Lei Wu, and Jinwen Ma. The anisotropic noise stochastic gradient descent: Its behavior of escaping from sharp minima and regularization effects. In International Conference on Machine Learning, pages 7654-7663. PMLR, 2019.
Zhihui Zhu, Tanyu Ding, Jinxin Zhou, Xiao Li, Chong You, Jeremias Sulam, and Qing Qu. A geometric analysis of neural collapse with unconstrained features. Advances in Neural Information Processing Systems, 34:29820-29834 2021.
Liu Ziyin, Kangqiao Liu, Takashi Mori, and Masahito Ueda. Strength of minibatch noise in SGD, In International Conference on Learning Representations, 2022.
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Stochastic gradient descent optimizes over-parameterized deep relu networks. arXiv preprint arXiv: /. 1.0888, 2018.
15

---

Appendix
Contents
Experimental Details
17
Proof Preparation
20
Proofs of Optimization Dynamics in Phase I
22
D Proofs of Optimization Dynamics in Phase II
47
Proofs of Optimization Dynamics in Phase III
66
F Proofs of Optimization Dynamics in Phase IV
79
Clarke Subdifferential and KKT Conditions for Non-smooth Optimization
91
H Solution of Discontinuous System
92
Some Basic Inequalities
93
16

---

A Experimental Details
All experiments are conducted on a MacBook pro 13 (M2) only using CPU. See the code httpaaeppppmmatttoollllllSSSSSS
at pebttps:/giitee com/wmz9 http////eeettnnnnaiiiiiie
A.1 Experiments standard Dataset
We train the two-layer network on the dataset that satisfies Assumption 3.1 with = 20, 4 and A 15. Specifically, we choose the network width 100; the initialization scale K1 = 0.1, K2 = 1; the small learning rate = 0.01.
In Figure 3, show some key data directions in this dataset, well the training accuracy. which contains a long plateau. Furthermore, in Figure 4, we provide the evolution of all neurons during training from f 0 t 150000, which is more complete version of Figure 1.
Tata Directions
Acefi
briiing accuracy
50000
spach
Figure 3: (left) Some key data directions: the directions of x., x x_, at. a f are plotted in blue, orange, green, red and pink colors, respectively; (right) The training accuracy.
x.,
117
(a) = 0
(b) = 200
(c) 1 2000
(d) = 30000
(c) t = 50000
(f) f = 60000
(g) 1 80000
(h) t = 120000
(i) 1 150000
Figure 4: (A more complete version of Figure 1) These figures visualize (in polar coordinates) the projections of all neurons (t)) onto the 2d subspace span(æ4, x- during training (from t= 0 150000). Each purple star represents positive neuron E [m/2)), while each brown star represents negative neuron (k E [m] [m/
17

---

A.2 Numerical validation on our theoretical bounds
We conduct experiments validate our theoretical bounds on plat and Tiu under different p and A, and the results are shown in 2.
In the first experiment (Ist and 2nd subtable), we fix p for change A; in the second experiment (3rd and 4th subtable), we fix = x/15 and change p. As for other hyperparameters (such as setups in Appendix A.1.
K1, Ki, d, m), keep the same scales
We have two main conclusions: (1) four training phases in our theory persistently exist; (the same as Fig in Appendix A, and be omitted due to the limited space) (2) our theoretical estimates Tplat. and Tin are relatively tight, basically in the same magnitude as the realistic time.
Table The change of our theoretical bounds on plat and Tinr under different p and A.
4
47
47
(2)
4
(2)
45
45
15
45
45
Realistic pllat
1.96 x 104
3.68 x 10
7.25 x 104
12.87 X 104
Our estimate (1/AA²): 950/ A + 1520/4 A 9943
1.90 104
3.82 10a
7.14 10a
12.89 101
A Realistic Tiu Our estimate (1//A²):
1n
(#)
())
15
45
45
4.98 10*
6.14 10
9.18 10*
15.63 10*
4.97 x 104
6.17 x 104
9.16 x 104
15.63 x 104
1772/ 12218/ A + 67621
p Realistic plat
10
12
6.14 10a
9.57 x 10
13.96 x 10*
17.61 x 10a
Our estimate (p)) 19400p 56400
6.00 x 10a
9.88 x 10a
13.76 X 104
17.64 X 10a
p Realistic TiI
6
8
10
12
8.92 10*
13.40 10*
19.72 x 10*
27.68 x 10*
Our estimate (pp MIpT-acoo 6912p 15897
8.59 10
14.05 10
20.27 10
27.14 x 10
A.3 Experiments on Noisy Dataset
We conduct numerical experiments on the setting of adding small stochastic noise on top of 4 and
æ_ a little bit more realistic setting. Specifically, in span ._ we perturb the angles of n4 1 instances x4 and n instances x using stochastic noise & Unif((0, A/4)).
In Figure 5, we visualize (i) the evolution of each neuron throughout the training process; (ii) some key data directions; (iii) the evolution of training accuracy.
From the numerical results in Figure we have two main conclusions: (1) we ascertain that the same four-phase optimization dynamics and nonlinear behaviors persist, even for our dataset with small stochastic noise; (2) a slight difference is that there is more than one plateau of training accuracy in Phase II. The reason is that for noisy data, GF needs to learn negative data one by one in Phase II. For example, three distinct negative data are employed this experiment, so three plateaus of training accuracy emerge (12/15. 13. 13/15 15, and 14/15).
18

---

Aod(()
100
80-
120
60-
1000000
2000000 apech
300000
400000
(a) key data directions
(b) training acc
pes
(c)
(d) = 200
(c) t 2000
(l) 30000
(g) 1 65000
(h) = 90000
(i) f 200000
(i) 400000
Figure 5: The experimental results for noisy data with = π t/15, n = 12, n- = 3. Fig (a): Some key data directions, including X+,, +noise, æ_,, x_ tnoinoee. μt, x and x Fig (b): The evolution of training accuracy. Figs (c)~(j): the evolution of the projections of all neurons (t) onto the 2d subspace s __ during training (from to = 400000). Each purple star represents a positive neuron (k E [m/2)), while each brown star represents a negative neuron (k E [m] mm/2)). Four-phase dynamics: from Fig (c) to (d) is Phase I; from Fig (d) to (g) Phase II; from Fig (g) (h) Phase III; from Fig (h) (j) Phase IV. To compare these results
with noiseless data, please refer to Figures and 4.
19

---

B Proof Preparation
Selection of initialization parameters.
For the data satistying Assumption 3. we consider the regime that A < the entire proof, we select the initialization scale K1; K2 as follows:
with p cos > 1. During
K2 O(1,
K1 O (A*).
(3)
K2
Gradient Flow. general, for any [m]], the GF dynamics of by (1) can written as
(t)(t) (L(()) SkK2 e
dt E ab V
(4)
St.22 mm
p e01+0000 ((bb))))
1 e- ( ())=)
1
where 8 is Clarke's subdifferential defined in Defnition G.I. Notice that if L continuously differentiable at 0, then d (()) (V)(0) is unique.
However, for discontinuous differentiable points of L, the differential inclusion flow de may not be unique. To study a more specific dynamics, we also utilize Definition H. determine GF at some of such points, which overcomes non-uniqueness of GF trajectories to some extent. It is worth noting that Definition H.1 and Definition G.I are compatible and specifically, the dynamics defined in Definition H. (Case I, III) lie in the convex hull defined in Definition G.I.
ar E 8 (())
Remark B.1. In (Lyu et al., 2021), the non- bon-branching starting point Assumption is employed to address the technical challenge of non-uniqueness in GF trajectories. By comparison, in this work, we not need this assumption. We adopt Definition H. I to uniquely determine the Gradient Flow trajectories theoretically near some discontinuous differential regions, such as "Ridge", "Valley", and "Refraction edge" discussed Section I.2 in (Lyu et al., 2021).
Additionally, in the following sections, we may rewrite this dynamics accordingly, such as specific forms and dynamics decomposition.
Additional Notations. As a similar description to sgn, ()) and sgnj (+), we also employ the following six manifolds characterize activation patterns (by judging which manifold the neuron wy belongs to):
MI = ww E gd-1 x+) > 0}, Mt = (w E dd-1 (w, > 0),
M = (w E gd-1 (w. = 0},
M = {w E dd-1 1 (w, ) = 0),
MI = {w E gd-1 (w, S 0), MI = {w E Sd--1 (w. S 0).
As one of our interested manifolds, the border { nM can be divided into
a(M nw =(w E gd-1, (w, x4) = 0 or (w,x_) ) = 0}
=(w E gd-1, (w, x4) 0, (w, x > 0} Utw E gd-- (w, xx4 > 0, (w, 0}
Ulw E sd-1; (w, = 0, (w, x-) 00
=(M² nM) u (ML nM) u (M. MM).
Furthermore, we also utilize the following notations:
pt = {b E Rd (b,z+) > 0),
p = (b E Rd (b,x > 0).
p0 = (b E Rdd (b,x4) = -}.
pu = (b E pd-1 (b.z ) = 0}.
Pf = b Rd (b.x+) < 0),
P_ (be Rd (b < <0).
Notice that for the direction of neuron b + 0, using P.. pl. P , P- to describe b is equivalent to using MT, M M_ to describe w
20

---

Lemma B.2 (Dead neurons keep dead). For the k-th neuron. if there exists to 2 0. s.t. wx(to) e
MI __,, then it dies and remains unchanged during the remaining training: wx E MINM. and by (t) bu(to) for any t z to.
Proof of Lemma B.2. A straightforward calculation.
The above fact is a basic fact in our setting, which illustrates that if the neuron by deactivated for both data 44 and x- at some time, then it remains "dead" forever.
It is worth mentioning that if the neuron by is deactivated x4 but activated æ at some time, can still reactivate on #. later, which is one of the important reasons why our ReLU optimization dynamics complicated.
21

---

C Proofs of Optimization Dynamics in Phase
In this section, conduct detailed analysis of the training dynamics of each neuron in Phase I. The main proof idea is to decompose neurons' dynamics into tangential and radial dynamics. For small initialization, in Phase I, the radial increasing of neurons much slower than their tangential velocity, which can result in condensation. However, the main challenges arise from the initial direction's 's randomness and ReLU's discontinuous derivative, leading eight categories of neuron dynamics. Moreover, it is also nontrivial and requires meticulous analysis to estimate the number of two classes of living neurons the end of Phase I.
We define the time
K1 K2
T = 10
(5)
and call & [0, [i] "Phase I".
Recall that the selection (3) about initialization parameters can guarantee the whole four-phase
optimization dynamies. Nevertheless, when focus Phase I, li ( and K (1)
suffice to ensure the dynamics in Phase Specifically, during the proof of Phase I, we can use the
following selection (6) on K1, K2, which is much weaker than (3):
K2 = O(),,
K (().
(6)
K2
For simplicity, we assume < J. And for convenience, we assume p 2 5. It is worth mentioning that our proof approach also applies for 3,444 4, with at most one absolute constant difference.
Prepared for the analysis in Phase we decompose the dynamics of by (t) into the radial movement (tt(t) and the tangential movement (x)(t) g satisfied b (t) Pk (t)
Lemma C.1 (Dynamics decomposition). For any & [m]] the dynamics of by (t) can be decomposed into the radial movement (t.(t) E IR and the tangential movement wy(t) E sd-1;
dt)x(t) dt Vmpa (1)
E SAK2
(Fm()) (Fx((), (x)()) wv wR)(
dp
E 8&82
(Fx(t), (Fx()),w,(11)
dt
Vm
where (t) = [[)(( (t) = (t)/ |b (t)l and
(t) = Σ -u.::000 (t), y.
(8)
Proof of Lemma C.I. From the dynamics by (t):
db&(t) dt
S4K2 Vm
(t) = Sy
e 0 ((wx(t) yoor yia)
/m n
we have
dpk(t)
1 (t)(1
(bb(t)
[bb (t).
dt
[()((()]
dt
dt (Fu(t), wx)))))
1
(ba(),
SKA2 Vm
F((())
S4A2 Vm
dw
bb. (b2(e)
allba(01l
(x)
1
dbx(t)
dpx(t)
de
ww wx(()
dl
(t)))
di dl
Ft(()
SkK22
(F+(t), wx(()) wx(())
SkK2 (t)
(Fa(t) (F&(t), ww (t)) (())(((((())..
(t)()
mm
22

---

Prepared for the analysis of the neurons' dynamics, we establish a rough estimate about the norm and prediction growth of each neuron in Phase and we will improve later.
Lemma C.2 (A Rough Estimate Norm and Prediction Phase I).
For any S T1, & E [m], and i E [n), we have the following estimates:
Pt(() - 11 + 1.1k2t
Vm
Ifa(t) S VR1K2,
v. -1 $ 1.1 1.1
Proof of Lemma C.2. First, we define the hitting time
T VNING inf {t 0: max [f((t) VKAK2)
ig|m]
From [f((0] E m Ko Ki = K1 < R2 and the continuity of f((.), we know Tumanz > 0.
Then we will prove 10, El T Jaing.
For any & E [m). E [n]. and S T Viimz have the following estimates.
Recalling the definition of (t) (8), we have
|F
Σ
uu ((unx(1), yaar
I max -if(t) xE(ni
7
(1(1 Se
SevRina S 1.1.
Recalling the dynamics (7), for any 5 T V11K2
dpn(() (1)
((Fx(!), wx(())
K2
|F <
1.1x2
dt vm
Fm
vm
Then combining Pt: (0) Vm
Ks
for any S T JNINK
px(t) < Ki + 1.1ngt
vm
(9)
R2 Kn + 1.1xtt
lf((t) S Σ (anlpx(t) S
S n2(Mm + 1.1n2t).
Vm
v
So for any < Tí, we have
|f(0)) < + L.122T) I Na na( 11vKINZ) I 12 S VRIK2.
(10)
From the definition of T MaRRa have proved Ti < T ,
Moreover, from this proof, we know (9) holds for any &. S Ty. Moreover, by Mean Value Theorem,
c v.f(() - 1/5 5 max 1)1-v:f(() < 1.1)f(() & 1.1
Now we delve into the optimization dynamics of neurons in Phase I the following Section C. and C.2.
23

---

C.1
The Dynamics of Positive Neurons
According the initial direction, all positive neurons (sk: can be divided into the following four classes.
[m/2] {1t E [m/2]: (0) EI MINMMM [m/2]: wx(() EMTNM Ufk E [m/2] (D) E MInM= U E [m/2] (x) E MINME}.
In the following four lemmas, will prove the dynamics for these four classes of positive neurons. In summary. in Phase (t < Ti), some of positive neurons align well with the direction μu, and their norms experiment small but significant increase, while other positive neurons go dead.
Lemma C.3 (Positive, MI n.M.).
For positive neuron l E (I [m/2]: (x)(0) E M n nMI,, at the end of Phase it holds that
(1 (1-0( Ki 0.55)
(Direction). It is aligned with μ (w)) 14) 2 (1 (1-O(V(1122) (1
R2
(Norm). It has a small but significant norm : Px = 0
VKin22
vm
Proof of Lemma C.3.
We do the following analysis for any E {le [m/2] wx MI n nt), ie. sp
(w (0), x+) > 0, and (0), x=) > O.
Step I. The neuron stays in Mt n MI for any S Ti.
First, we define the hitting time
Tut == inf {i E (0, Ti]: (x)(1) & oMM
and we aim to prove that Thit does not exist. From the definition of Thit and (4), the dynamics of the neuron is:
(t) K2 Pe-100
(10)
-(-(()) S Thit-
x4 I I+
dt mm
I+p
From Thn S Ti and Lemma C.2, we have have:
(e-u - s 1.1//1122 for any t s Thit Then we
d
(b), x.)
pe pe- f+(1)
et-
1 1+p cos A
dt
Vm
1 1+p
K2
p(1
1.1 k2g
(1 + 1.1 K1K2) COS A
>0,
V m
1 p
1+p p
d (t), x-)
18g
pe -f+(1) cos A
el-(1)
dt
mm
1 1+p
1 1+p
R2 Vm
p(1
1.1 Kg)
cOs A
1+ 1.1 1k1
>0.
1 1+1 Pp
1+p p
Hence, for any t. & Thits (t), x44 > (b. (0), (0), > and (bs x)) >
(bx(0)
According to the definition of This, we have proved that Thit does not exist, which means the neuron stays in M n Mt for any f < Tí.
Step II. Estimate the evolution of (w)()). n).
With the help of Step I, we were able determine the dynamics for S Ti. For any /. S Ti, we can do the following estimate.
24

---

From (7). the tangential dynamics of the neuron is
dwwx(t)
Vmpx(!) FF(())(Fx(()) ((((t)))))))))))))))))))))))(( wx(()).
122
- (Fx(t),
di
P -01000
1 el 1
where Fx(t):= = 1+p
1+p
Recalling the definitions of je and 2, we can estimate the difference between Fx(() and z:
(F)(t),
2 P
(e-1=(0)
1)
1+p (e/-(0 -
1
(d1-0)-1)x -1)x0,2)
1+p p
= =| +
(e (e-((()) - -1)x+
1
(cf - -1)x
P x4+
1
x
1 +p p
1+p p
1 1+ p
1 1+ p
2 2|/=|
p²
ef+1 -1 1|
1
e-(()) 11|
pcos A
e (e-+(0) - 1
e (t) -1 1)
(1 + p)2
(1+ p)²
(1 p)3
Lemma C.2
2
|||1 2 1.1 1k1
p2
1
+ 2pcos A
2 || 2 1.1 /B1k2,
(1+
(1+ p)2
p1+
|| (1((1) =|
P
(e --(()) - 1)
(ef- (t) - 1)
1+p p
1 p
P (c (+(+) - 1)
1
(ef- - -1)x-
+
1+p P
1 1+ p
Lemma C.2
P + 1.1 1.111.1mmm R2 /
1
R22 1+p
1.1//
1+p
The dynamics of (wx((), (1) is: d (wx(()..)) 1 (t),
R2
((Fx(t),)) - (Fx(1), (t) (w))())=)))
di
I dl
|| (t)
And it can be estimated by: d (wx (ww((), 1e)
dt
K2
(Fx(t), 2) - wx, (wx(t), 2) - (FF(()) - z, (t)) (xxx))))
|| Vmpx(!) (t)
K2
(FF((t), 2) - (t))(t) - [x - =1 |
|| Vmpx(t) (t)
12
(11=11- - 1.1 - (wx (t), x)² 1.1 / ||=||
|| Vmpx(t) (t)
12
- ||=11 (11=)|-
(t), 22)² 1.1 1 + ||
|| (mpx(t) (t)
K2
||||
(1-(wa(t), (w)x(), n0)² 111K11 (1 + ||
(t)
|| 2
Lemma 1.3
2
(1 (1- (w)((), 24)² -1.1 -111/1182
1.5 1.5+ + (1.5+155))
2K²
(1-4.2/m16 - (wo((). 22)
2
3/mpx(t)
(v)px(tt)
Lemma
C.2
26g
(1- 1-2.2/18122 (11x(1).111²)) 3 K2
2
-11tt) (1
4.222//8172 - (unx(()) -1120/17--0022(0)1)1))) (1)(
3
m
ki Llle2t
Ai
mm
(11)
Noticing wxx(0) E M n.t we have:
(w) n1) = (wx(0),
P x
1
x_
>
1+p x
2
1+p (12)
1
1+p p
1 ++7 p
p
25

---

Now we consider the following auxiliary ODE:
au(()
2
(1 (1-4.2/6163 1199-U341 U2(1))
3 132 +1.10)
(13)
U(0))
I+P
and let (t) is the solution of (13). Due to (11) (12), we know that (we (t), μu) is an upper solution of ODE (13). From the Comparison Principle ODEs, we know this means:
(wx (t) (t), for any Ti.
Hence, in order to estimate (wx (t), p)), we only need to study the solution of ODE (13). It is easy to verify that the solution of (13) satisfies
log
1 - 1-422/ + +((()
llog
1 1- 1124.v/K15 Rine
I+p
1
4(1
4.2
K2
log 1+
1.1k2
t)
- 4.2. K1 - U(t))
1- 1-2.2 4.2. 12122 +
I+p
1
3.3
A1
Then have:
4.2% + +())
- 4.2%
4(1
4.2
Kig
K2
log 1+ 1.12 t
log
> log
+
4.2//112- U())
1 4.2.4/2/1 /K1N2
3.3
Ki
1.182 t
1.15)
1.15
log
0.7
1
log
0.7 1
15
11
which means
U(t) 2 (1-4.2
4.2 122//122))
1 1 0.7 (1+
L.122
1.15
131
Hence, we have the estimate of (wox(1),
(wr (1:))2(11444mm 4.2
(14)
1 0.7 (1+
1.122
1.15
K1
Specifically, we have:
(w (Ti). 2 (1- (1-4.2 (1-4.//1112)
(1-
2
1.15
0.7 (1+
11
152
R1
Step III. A finer estimate px((i))
In this step, we will estimate the lower bound and upper bound for px:
First, lemma C.2 gives us the upper bound for (T)):
81 1.18IT
KI +ILRRIR
12/KIR2
Pk (Ti)
<
Vm
Vm
Vm
Now we focus on the estimate of the lower bound. Recalling the dynamics of pv(() (7), for any I < Ti.
dpx(t) = K2
(F)(t), wx(()) =
R2
(z, (x)(t) + (F&(t) - 2, wx(())
dt
vm
vm
2 K2
(2, (1)) - [x - -211 >
(
K2
||>|| (t)):(t), (t). (4) - 1. 1.1 1
mm
mm
26

---

2
/
(14)
2
vm
1 0.7
(1
1.102
1.15
1.278
0.627
Vm
0.7(14 +
1.1ma 1.15 a
We denote To
10k1, X2
and is easy to verify:
1.278
0.627
1.15 > 0.53, for any i E (To, Ti]-
+ 0.7(1 +
1. t)
So we have:
Ti
R2
1.278
(T) 2 (TTD +
0.627
dt
vm
1 0.7(1
+
1.1m2 t) 1.15
61
Ti 0.53Rz df
0.53
81
10k1
K2
n2
5.3
0.9, K1
v.77 K2
>0
10
m
m
mm
Lemma C.4 (Positive, M nMM). For positive neuron k E {k E [m/2]: (x) E M n.M),, at the end of Phase I, it holds that
(Direction). It is aligned with μ (Ti). p)) 2 (1- ((-O(())))))
(1-0(( )0.55
K2
(Norm). It has a small but significant norm pa (Ti) e VKiN2
vm
Proof of Lemma C.4.
We do the following analysis for any E {k [m/2] wv( E MI MM i.c. sk = 1,
(w)( x4) 0, and (wx(0), _-) S O.
Step I. The neuron must arrives M a in KI
time.
The case (wy, (0), x) = 0 is trivial. Then we only need to consider the case (0), x=) < 0.
First, we define the hitting time
Thit := inf {( (0, Til wx(()) & MM
and we aim estimate Thit and prove wp((hir n We focus on the dynamics of (t), x4) and (b, x-). From the definition of This and (4), the dynamics of the neuron is:
db,.(t) dt Vm +p
- (+()) x+, S Thit
Then have
d d (t), x+)
K2 p e
[+(1) x.., x4
Kzp
e. (+(()
di
Vm
+ P
Fm(1 + p)
(by (t), x)-
K2
f (8)
K2p cos e (()
x x
dt
Vm 1-1
Vm(l + p)
It is clear d(bx(t)...)) dt
> 0, so (bx (t), x+) >
> 0 for any t S Thit If we denote
T Tuit. = inf {
(0, Til (w) x.) 20.
27

---

then it holds:
Thit Thit.-.
So we only need to estimate Thit.-. Due to Thit S Ti S Tinit and Lemma C.2, for any & S T hit, we
have e -Wif((t & 0.11. Then for any 1 S Thit. we have:
d (bb (t), x-) 0.89r2p A
dt
Vm +
and (0), < O, with the help of Lemma 1.2, we have (m,, x-) sin A. Combining the two estimate, we have:
Recalling
(bx(t), x-) 2 (bx x-) /'" 0.80mppcos A
dt
vm(1 + p)
(0) sin 0.89kBp A K1 sin A vm(1 +
0.89kyp A
vm
Vm(l+ + p)
Hence,
(1 p)) lan A Ki
2A K1
Thit- Thit, <
0.89p
K2
Step II. Dynamics after arriving in the manifold MI n
In this step, we analyze the training dynamics after ww (Ziss) E MI
First, we will prove (1) passes immediately from one side of the surface MI n m to the other, ie. wx(() enters into Mt n nMt at time Tha Equivalently, we only need to prove (t) passes immediately from one side of the surface Pf n Ph to the other, i.e. (b)()) enters into P n p at time Thit-
For any b Pt- p2 and 0 < d0 < 1. we know that P n p separates its neighborhood B(b, 8n) into two domains G_ (b E B(b, 5n) (b, x-) 0} and g_ {b E B(b, do) (b, (b,x_) 0). Following Definition H.1, we calculate the limited vector field on b from G_ and G+.
(i) The limited vector field F on b (from G_):
db FT, where F mm
K2
P
dt
1+p
(ii The limited vector field F+ on b (from G+):
db dt = F+, where F+ K2 Vm
pe (t())
(f-
C+
x
1 1
1 pp
(iii) Then we calculate the projections of F and F+ onto x (the normal the surface PI n PP)):
FN F x KopE (t)
Vm(1 (1 + p) COs A,
K2PE (t)
Kgef-1 (t)
F = F x
mm +)) cos A
Vm(11 +
From Ti < Timit and Lemma C.2, we know le v.(() 1| < 0.11, so pe (() cos A ef-())
0.89p A 1.11>0, which means F 0. And it is clear that F 0. Hence, the dynamics corresponds to Case (II) in Definition H.1 (FN 0 and F 0).
(iv) Hence, (t) passes immediately from one side of the surface PI n pe to the other, i.e. by (t) enters into P n Pt time Tha--
Second, proceeding as the proof of Step I~Ill of the Proof of Theorem C.3, we have the results:
(T)) p1) 2 (1-4.2
4.2 (1222)
1 0.7 0.7 1.1 Thi)) 1.15
28

---

2
4.2 11122
1.15
1.7
1
1.1
#2
(10
V
24
n2
x2
2
-1-42 4.2//1822
1
1.15
1.7.7
(1 1.9
9.9
82
K1
1l
+
11 K11k2
12
12
(T) 1
Vm
vm
m
Ti
12
1.278
(T(T)) 2 (To)
0.627
di
Thit
10N1
m
1 + 0.7(1+ +
1.1m2 t)
1.15
0.53kz
0.53
K1
(10+2A)M;
)K2 (6 5.3 0.88 0.88//182
4.66 K2
>0+ +
That
10K1
m
m
m
Vm
52
Lemma C.5 (Positive, MT n.M.)
For positive neuron ls E (k E [m/2]: (0) E M MMn. after O
kipA
time, it goes dead:
kipA
wx(() MIN for any Ti 0
K2
Proof of Lemma C.9.
We do the following analysis for any E {k E [m/2] wx((0) E MI MMJ i.e. Sk = 1. (0) x.) > and (0), a; 0.
First, we define the hitting time
Thit inf { E (0, wx(() & J
and we aim to estimate Thit and prove w& (Tiit) MINME. From the definition of This and (4), the dynamics of the neuron is:
(b)(t) di Vm 1 +
K2
f-(() x__, i 6 Thit-
Then we have
d (b& (t), x+)
122
1
e (1 x0_120 x+
K2
ef (9) cos A,
dt
Vm +
Vm + p
d (bx(t), x-) dt
R2 1
f-(1)
K2
(t)
Φ_, x-
Vm
+
Vm 1 +
is clear ((b.(t)).m.)
< 0, so (bx (t), x4) < (0) x.) $ 0 for any t S Thit- If we denote
di
Thit = inf { E (0. Til (w), x= =0).
then it holds:
Thit Thit.-.
So we only need to estimate Thit-. Due to Thit E Ti & Tini and Lemma C.2, for any 1 S T Thit, we
have le vif((( 1| s 0.11. Then for any L < Thit we have:
(b),(), x 5 Vm + p) dt
0.89kz
29

---

Recalling (w)(0), x4) < 0 and (0), O. with the help of Lemma 1.2, we have (0), sin A. Combining the two estimate, we have:
(bx(1), (0)) S (0), x L Vm(1 + p)
0.89k2 di
0.89K² t
sin A
0.89k2 t.
(0x(0) sin A
v Vm + p)
m
V /m p)
Hence,
Thit T p1+ sin A
< 10
0.89
K2
R2
Moreover, the analysis gives us wx (Thit) M M.. By Lemma B.2, we obtain:
wx(1) E MEMMMMMM for any 1 2 Thit.
Lemma C.6 (Positive, MT nM For positive neuron & E {k E [m/2]: wy( E M MMM,, it keeps dead forever.
Proof of Lemma C.6. Due Lemma B.2, this lemma is trivial.
C.2 The Dynamics of Negative Neurons
According to the initial direction, all negative neurons (dą = -1) can be divided into the following four classes.
[m] [m/2]
= [k E [m] - [m/22] (k) E MMMMMMMN U (k E [m] - [m/2] (x) E MT nmt
U [ml (0) MI UKKE [m]-(m/2] (x) MMMMMEE
In the following four lemmas, will prove the dynamics of these four classes of negative neurons. In summary, in Phase I (t < Ti), some of the negative neurons move to the manifold M n m in a shorter time and then remain on this manifold, and their norms grow slowly, while other negative neurons go dead.
Lemma C.7 (Negative, Mt nMtt. For negative neuron k [k [m] [n]-Im/ [mm wx) E MI ntM,, in Phase I (t S Ti), it's dynamics must belong to one of the following two cases:
(i. Living). (S1). (t( E M. n for any t 2 0 (
K2
/K1R2
)
-
(S2). It has small norm pk (Ti) O
Vm
1:2
p
(S3). It weakly aligned with at (wx (Ti), x 2
0(1
Ki
A
Ki
(ii. Dead). (x) E MT n MM for any t 2 0 (1))
K2
Moreover, if (wx x-) > (I+ (1+0 cos A (1-00())2)
(1 (10(x1 kg)pp (1 (1+0(x)z)) cas (wx x4), it must belongs to Case
(1+0 (1 018 (): if (w) (1-0mmma))))
(10(m))))) (w)y (0), x)), it must belongs to Case (ii).
Proof of Lemma C.7.
We do the following analysis for any E (k [m] - [m/2] : we (0) E EM ninnMttiee. 8 = =1
(wx (0), x4) > 0, and (wx(0), x-) 0.
30

---

Step I. Neuron must arrives in the border i nM*) in O mi time.
First, we define the hitting time
Thit inf { E (0, ux((1) o(MinMt)]
and aim prove Thit exists and estimate Thit.
Recalling the decoupling a(M n nM) = (M² nt) u (M2 nā) u (M² nm).. we only need to focus the dynamics of (bx(1), x+) and (t),
From the definition The and (4), the dynamics of the neuron is:
(t) dt
1
mil((1 yea:
122 P
(1
S1
(4)
1 ef (.x=), Thit-
v V n
vm
1
1
Then have
d (bb (b)x x
R2
P E
f+(1) x4
1
e5 x ,
di
Vm
1
1 1 ++p
c
f+(1)
1
c (0) cos 1
Vm
1 1+p
1+p p
d (b), x-)
R2
P C
-f4(1) 2
1
e ef((()x)))) ) x
dt
Vm
1+p
1+p
p
(+(1)
cos A
1
el-(t)
mm
I ++p
I+p
Due to Thit S Ti S. Tint and Lemma C.2, for any S This we have |e vus(() - 1| s 1.1//1k2 Then for any < Thit, we have:
d (1), dt
122 (1 k1k22
1+11VKKR2
<
COS A
mm 1+p p
1+p
R2 (1-1.1 S-
(1 + 1.1 K1
COS A
Ki (0.988 1.02)
vm(1 + pp)
vmll +p)
d (bx (f),
R22 (1
1.1 1.1/K112)p
1+1.1 11k2
cos A
df
m
1+p
1 1+p P
Ri (1 -
/LIKKikg)ppooo A (1 /1kk)
0.98k2 cos A 1). 2/mm(1 1 + p)
vm (1)
Now we consider the time
381
T
K2
we assume Trest < Thit then we have the estimate:
Tiest R2z K2(0.98p 1.02)
(b& (Test),, x44 S (0), xx
Vm p) d
K1 R2 (0.988 - 1.02) 3k1
< 0,
m
Vm(1 p)
K2
which is contradict to the definition of Tha Hence, we have:
3k1
Thit S Ttest <
K2
which means neurons must arrive in the border a(M nMt in O (1) time.
31

---

ef- Because @(MI - (M in M. nmt M nMt or Mr n.m. If the neuron arrives in M n. it goes dead forever (Lemma B.2). We will analyze the training dynamics after arriving M n.t M nMt in the following Step II and Step III.
nM u (M4 n.M", the neuron must arrives
Step II. Dynamics after arriving in the manifold M. n
In this step, we will analyze the training dynamics after wx (Thit) E M4 nMt, i.e. after (Tht)) E pt n Pt.
We first analysis the vector field around the manifold P npt for Thit S ST
For any b pt n P and 0 < ón < 1, we know that P4 n P separates its neighborhood B(b, 6n) into two domains G_ {b E ((6, (b, 0} and g_ {b E B(b, do) (b, 0}.
Following Definition H.I, we calculate the limited vector field on from G_ and G+.
(i) The limited vector field F" on b (from 9-):
db FT, where FT m 1 +
K2
ef- xc
dt
(ii) The limited vector field F+ on (from 94):
db dt = F+ where F+
R2
pe [pe--+00 f+(()
+ p x
V Vm
1 1+p
(iii) Then we calculate the projections of F and F onto x+ (the normal to the surface p n Pt):
kgef (t)
F xT,
cos A,
Vm(1 + +p)
Rzef (t)
K2pe -ape-f(()) (()
F ( x+)
Vm +p) cos A
Vm((1 +
From Ti < Tinit and Lemma C.2, we know le-w.f(()) - 1| I 0.11, so pe (+) cos - ef-(1) 0.89p cos 1.11>0, which means F < 0. And it is clear that FN > 0. Hence, the dynamics corresponds to Case (I) in Definition H.1 (Fx > and F < 0).
(iv) Hence, (t) can not leave Pt n Pt for That S t t Tí.
(v) Moreover, the dynamics of by on p4 n satisfies:
= aF + - (1-a) a JN db dt
JN f
which is
db&(l) k1)
( x. cos A). dt Vm(1 p)
By Lemma C.I, we know that the dynamics of (x(() on Ma n M and the dynamics of Pk (1) are:
dwn(1) (t)
pa(0)m((1+ (1 ( (1),,,)) 2) we xx cos A).
(())
(15)
dt
dpx(t) Kyed (0)
dt Vm(1 +p) (wx (t),
(16)
(vi) In this step, we aim to estimate pa and (w) (t), x
From we (Thx) E MQ At f, it holds that (unx(Thn))) (Thit, x. and (une(Tnit), x.) 0. Using lemma 1.2, we have 0 < (wo (Thit) x=) < sin A.
32

---

Recalling Lemma C.2 and the estimate of Thi in Step I, we have:
- K1 + L.IngThit
0 S pk (Thit)
Vm
and we can estimate the dynamics for Thit St Ti by (v)(vi):
dpx(t)
Kge (8)
Kyel (1)
S dt
vm +p) (wx(t), (wx(t)===)$ Vm +p)
sin A,
e 1 0.11 = 1.11.
Then we obtain the estimate of (1()) for any Thit <9< Tr:
(Toht + L dp((s)
K1 + 1. Thit ds
Rzef f (t) sin A
px(()
(t Thit)
Tim dt
Vm
Vm + p)
11 + 1.1ssThit
1.11mg sin A vm +p) (Ti Tha)
R1 + 1.122
3x1 n2
1.11ky sin A
381
(Ti
Vm
vm
Vm(l+ +
A62
4.3k1
1.118g sin
t.
Vm
vm([+p)
Specifically, we have:
4.3k1 1.11 sin A
4.3% Vm
11.1 / K2 sin A
/81 m
K1
11.1
sin
A
(T)T S
Ti S
4.3
vm
Vml(1 + p)
mm +p)
K2
1
+
For any w E M4 n Mt, we have (w, xx)) = 0, so
(w, xn) w.
a_ 24 COS A
(w0 x
1
w
x
x=_ x+ cos All
|x__ x. cos All
sin
A
So we only need to focus on the dynamics of (wx(() x a-) derive the dynamics of (wx (wx(1), x+).
By (15) and the estimate of pk (t), for any Thit S < Ti we have:
d (w)x(t). x-)
ef
(1())mm( + +)) x (w) (t), x-) wk (x(() x+ cas A) )). x
K265-(1) (1)
(1 0.11)K2
sin2 (wx (t), )²))
(sin" A (t)x(t)x==))
Px(t) (1 +p)
(1 + p) 4.3Ki + 11lkg
(1+p)
0.89k2
sin2 - (t), x=)
2 4.3(1 + p)k1 + 1.11kytsin A
And we have 0 <
381
sin A.
Now we consider the following auxiliary ODE:
do(r) de (U(0)= 0
0.89k
ssinn (sin²A-U2(1))
4.3(1pp)
(17)
and let (t) the solution of (13), We know that (wx (1), x-> is an upper solution of ODE (17).
From the Comparison Principle of ODEs, we know this means:
(wx (t), x- > (t), for any t < Ti.
In order to estimate (t), x),,, we only need to study the solution of ODE (17). It is easy to verify that the solution of (17) satisfies
sin + U()
sin A
1.78kz log
4.3(1 + p)s + 1.11k2/ sin
log
logg
=
sin A U(t)
sin A
1.11 sin A
4.3(1 p)k1 3.33n, sin A
33

---

Then we have:
sin A + (Ti)
1.78
4.3(1 + p)li + +1.11 /1.12/
log
log
sin
(Ti))
1.11
4.3(1 + p)ki + 3.33kt sin
(11.1,
3.33
sin
11.
-..33
sin
T+p
1+p
>1.6 log
1+
1.6log
1+
4.3 + 3.33
sin
4.6
1+p
10.7
K2 sin A
>1.6log
14
4.6
K1 1+pp
which means
2
U(T)) 1
sin A.
1.6
10.7 T.6
K2
+
1+p
Hence, we have the estimate of (wx(t), x4))
1 (wx (Zi,, x-) sin A
2
(wx(T)), sin A
U(ii)
1.6
1 + 2.32
A
+
l+p
Step I11. Dynamics after arriving in the manifold MI nM
In this step, we analyze the training dynamics after w (Thtt) M i.e. (T(T) PInP2.
For any b P n po and 0 < dy < 1, we know that p P separates its neighborhood ( 8n) into two domains g_ = {b E B(b, 6() (b, x_) < 0} and g_ = {b E B(b, 6n) (b, x_ 0}. Following Definition H.I, calculate the limited vector field on b from G_ and G+.
For any b 1 n p and 0 < du < 1, we know that P n po separates its neighborhood B(b, 8n) into two domains G_ (b e ((6, da) (b, x-) 0} and G_ {b E B(b, 6o) (b, x-) 0}. Following Definition H.1, we calculate the limited vector field on b from g_ and g+-
(i) The limited vector field F b (from G-):
db F", where F Vm
R2 P c
(100 (0x4.
dt
+
(ii) The limited vector field F+ on (from G4):
db F+, where F+
pe ((())
ef (t)
E+
x
dt
Vm 1 +
+
(iii) Then we calculate the projections of F and F+ onto x_ (the normal the surface P p2):
K2pe ft(1)
FN (F (F,
Vm(l p) cos A,
K2pe (t(t)
K2ef-(9)
F
F x x-)= -
Vm(l + pp) cos
Vmn1 +p)
From Ti Timit and Lemma C.2, we know le- vif((t) 1 s 0.11, so pc f+(() cos A - cf-(1) 0.89p cos A 1.11>0, which means F > 0. And it is clear that F 0. Hence, the dynamics corresponds to Case (II) in Definition H.l (F 0 and F 0).
(iv) Hence, (t) passes immediately from one side of the surface P n po to the other, i.e. bx
enters into Pf n pt time Thit.
34

---

Then the dynamics of by in P np= satisfies:
(bb
122 P e -+() x+ vm
dt
1 +p
(v) We define the following time, and our aim is to estimate Tiest.1
Test, inf { (Tuit Til (wx (t), x+) s or (wx(t), 20]
Trest inf f (Thit Til: (w) x+) <0}
d(b,(t), It is clear 1 I 1- Moreover, due to
Kig -- (+(() cos A < 0 and
mm 14p (by (Thit), O, we know (bx(t), < 0 holds for any Tiest,1 Hence, have Tiest,1 = Trest, (TTsstts.,))) x4) 0, (wox (Tiest,1), x-) O.
dt
And we only need to estimate T.st, For any Thit < S Testt1 Tistt we have d (bx (4), dt
K2
P (+(1)
(1)
Lemma C.2
K2
p (1 0.11)
0.89k2p
mm
+
v m 1 1+11
vm(1 + +)
Recalling Lemma C.2 and the estimate of The in Step I, we have:
(Tht), x & [()(())) K1 + 1.122
Ki 1. R2
4.3k1
(px(t)))
vm
vm
/m
Then for any Thit < t Trest,2 have:
f"
0.8982P
4.3kg
0.89k2p((t - Thit)
(t), (bb((Thtt) xx)
ds S
This
mm(1 +p)
m
vm(1 + p))
So we have the estimate
Testt,1 Trest, S This 4.3 + p)
4.3-
9K1
3
Tí.
0.89k²2
0.89
K2
K2
Recalling wx (T E MM and Lemma B.2, the neuron by (f) keeps dead for any t > Ti
Step IV. Which subspace does the neuron select?
From Step II, we know that the neuron wn (t) must arrives in M nmt or m or MQ In this step, we will analyze which subspace does the neuron select.
We only need to compare the following two times:
Thit,+ := inf t E (0, (t), $0].
Thit- := inf t [i) (bu. (t), x-) =0].
From the definition of This, know Thit, Thit Thit.- Thit- Recalling the proof in Step I. we compare the following two dynamics for This: d (by (t), x+)
R2
P
(4(()
I+p -el cos A).
e
dt
mm
1+p
d (bx (t), df
K2 P
Pe-
cos A I+p e (+())
Vm
1+p
With the help of Lemma C.2 and the estimate of Thit, for any S Thit
le (t) - 1 < 1.1kg(k + 1.1kgThis) I 1.16g(k1 + -3.3k1) 4.73m1K22
Hence, we have the estimate of the dynamics:
K2 (1 1.73 - (1 11-4.3xk (22) cos A
No x2((1 4.73K182)P (1 4.73k 122) cos A
d (bx (1),
Vm(1 + p)
dt
Vm + p)
35

---

K2 (11 ( A (1 (-73311k))
K2 (1 4. 4.73k182) A (1 (1+ 4.73k1122)
d (bxx (1), (1)x))))
dt S
vm(1 p)
vm(11 +p)
(i) If the initialization satisfies (0), prove that the neuron selects M n at Thit. For any t < Thit. we have the estimate:
(1447730mg 4.73kg (1
(b)( x+), we will
-1- (1-4,738112)p (1 4.73/51 cOs A)
(ba(1), S (bb:(0), xx)
vm(1+p)
(bx(t),x_)) (bx(0), xz) N2 (1+ (1++..3kiss)p A (1 4.73k182)
Vm(l+ +p)
K2 (1 (T33)1K222p (1 + 4.73kz K22) cOs A
(1 + 4.7.3x1 A (1- k.7
(b,( x+))),++)
(1 4.73kk (1 + 4.73 cos A
vm p)
Comparing these two inequalities, we have:
Thit, This Thit,-
which means
(bx (Tha),, 24) 0, (ba((hit), x-) 0.
So the neuron (Thht) E M. n.t..
(ii) If the initialization satisfies (b. (0), .x) (1+4773m
(1 (b), x x= we will
prove that the neuron selects M n MM Thit.
For any Thit: we have the estimate:
K22 (1 4.7331K2) A 4.73x182)
(bu(t), s ((b()))
t.
Vm(1 + +p)
(b)( 2 (0), K2 (1+4.73m112) - (1 - 4.73 cos A
vm(1+2) +
K2 (1
A 4.73/1122)
(1 + 4.73K11 (1 4.73kg cOs A
(bx(0),
(1 - 4.73% R22 ) cos A (1 4.73%) Comparing these two inequalities, we have:
vm((+p)
Thit,- Thit < Thit
which means
(Tassi)), x-) = =0, 0, (ba(Thit), > 0.
So the neuron wpy E M Mo.
Lemma C.8 (Negative, MM. ntt.. For negative neuron & E {k E [m] [m/2]: (x) E MI Mt in Phase I (t < Ti), we have:
(SI). (x(() E MD 0 M for any t < 0 Ki p
(S2). It has a small norm: (Ti) 0
/Kig
(1
Ri
+
A
vm
K2
(S3). It is aligned with at (w: ax 2 21-0((1)
001
K1
P
1.6
K22
36

---

Proof of Lemma C.8.
We do the following analysis for any E {k [m] [m/2] wE (0) E MMn.MM,.ie. 5p = 11
(m0x(0) x+) < 0, and (w),(0), x- > 0.
Step I. The neuron must arrives in Mr M. in
KipA
time.
The case (wx((), (0), x+) = is trivial. Then we only need to consider the case (wx x+) < O.
First, we define the hitting time
Thi inf {te (0, wx(() MI n.
and we aim to estimate Thi and prove (Thit) Mº n We focus on the dynamics of (b,(t), x+) and (bs (t), x-). From the definition of The and (4), the dynamics of the neuron is:
db (t)
12
(1) x__ S Thit.
dt
+ p
Then we have
d (bx m+
K2
1
1-11)= D4
CD8 A vm(1 p)
el((1))
dt
Vm +
d (bx (f),
K2
1
f x_
K2 el-(t).
dt
Vml
1+7
vm(1 p)
It is clear d(bx(().
0, (b,(t), x-) > (bx (0), x-) > for any t S Thit If we denote
Thit := inf { (0, Til (t) s =0].
then it holds:
Thit Thit, So we only need to estimate Tait... Due to Thi S Ti < Tint and Lemma C.2, for any t < Thit, we have le a0 s 0.11. Then for any 1 S Thit, we have:
d (bb(()), x+)
0.89kz cos A
dt
vm(1+p) pp)
Recalling (w) x.) 0 and
0, with the help of Lemma I.2, we have (w,( (0), x+) sin A and (w), (0), ,), x < sin Combining the two estimate, we have:
(w) (0), x)
(bb(t), x+) 2 (0), x+) + J-"
0.8992z cos A
dt vm(1+ p)
> (0) sin A 0.89k² cos A
/m(1 + 1 == K1 sin A
0.89 cos A /m(1 p) t.
+
Vm
Hence,
(1 p)+ tan A R1
Thit Thit,+ <
<
2p
Ti 10
0.89
K2
K2
K2
Moreover, we can estimate of pk (Tist).
Since (Ix( x4) < 0 and (wx((), x-) > 0 hold for any S Thits with the help of Lemma 1.2, we have (w)(()) (t), x sin A. Combining (7), for any t < Tha have
(k(1) S Pk(0) + /'' Vm + +p)
K2
f- (1) (1)) x)))).)))))) dl
K1 + S. 1.1182 sin Adt < (m((+p)
K1
1.11kg sin A
Vm
Vm
Vm(1 + p)
37

---

Step II. Dynamics after arriving in the manifold M n
Proceeding as in the proof of Step II in the Proof of Theorem C.7, we have:
(xt(t) not leave Mr. n.t for Thi sts Ty. Moreover, the dynamics of wv M O nM satisfies:
dw)
kt)
Px(t)/m(1 +p) ar- (a-- (w0k, x.-) wv F COS A),
dt
dpı(t)
K2)
vm(1+p) ((x(t))x=)).
dbb (1)
k2)
a_ - x.+ cos A)
dt
vm(1+ pp
Recalling the estimate of Thi in Step I, we have
1.11k2 sin A vm + p) Thi--
Pk (Tiie) S
m
As the proof of Step II in the Proof of Theorem C.7, for any Thit <t S Ti, we have
(t) = (Titc) + L dpp(s)
N1
1.11kg sin A
Thit + Age! (4) sin A
ds S
(t Thit)
Tha ds
vm
vm 11 + p)
Vm +
K1 +
1.11kg sin A
1.11kg sin A
(1. Thin) = K1
1.11kg sin A
Thit
vml(1 p) L.
mm Vmi(1 P)
vm(1 + p)
m
Combining the estimate in Step I, for any 0 < S Tr, we have:
(x(t) S
K1
1.11kg sin A
mm Vm p)
Specifically, we have:
K1 Vm
11.1 /112 sin A
VK1K2 vm
Ri
A
(Ti)
vm +
R2
I+
Similar to the proof of Step II in the Proof of Theorem C.7, we have the estimate of the dynamics of (w,(t),x=])
(w) (t) (t), 2 (1 p)kp + 1.1 1.1 sin
0.89k²
sin" A (wx(t), x)) 0 O<ts
dt
0 < (0), x-) < sin A. In the same way, we can derive
(wx())) 1 (1+11.1 11.1
sin A
1.6 1+p
82
+
R1
Hence, we have the estimate of (w (t), xt):
1
(wx (T)) = sin A
(1 ( 11.1
No sin A
1.6
+
1+p
Lemma C.9 (Negative, M M+NME.
For negative neuron K (k E [m] [m/2] (0) MI nM it keeps dead:
(+)() E N.M.M.... for any 2 Ti > O Ki A
38

---

Proof of Lemma C.9.
We do the following analysis for any E {k [m] [m/2] wy E MMnM S 1. s 0.
(m)x(0); x+) > 0, and
First, define the hitting time
Thit == inf {i (0, Til wx(1) M
and we aim estimate Thit and prove wx(Thit MINM.. From the definition The and (4), the dynamics of the neuron is:
dbb((t)
K2
(+(0) ++ t S Thit.
dt m +
Then we have
d (b& x+)
1/2 p
-1
x+ x1, 2t
K2 p e -1((()
e
dt
vm + P
vm +
d (b& (t).
N2 P
e
(1
0+, x--
K2
p
(1)
cos A.
dt
Vm
+p
1 +p
is clear
d(bx(t).._) de
< 0, so (b) x-) < (bx (0), x-) ) 0 for any t I Thit If we denote
Thit+ inf { E (0. Ti) (t)x(t, $0).
then holds:
Thit = Thit,.
So we only need to estimate Thit,-. Due to Thit I Ti S Tini and Lemma C.2, for any t S Thit, we have ee (0) -1 s 0.11. Then for any t Thas have:
(bx(t) (t), x+) dt
0.89K2p
< mm(1 +p)
Recalling (w,(0), (0), xz)) 0 and (w)( x-) 0, with the help of Lemma I.2, we have (0), x+) S sin A. Combining the two estimate, we have:
0.89k2P dt
(t), (bx(
Vm((1 + p)
0.89K2P
K1 sin A
0.89x2p d.
(0) sin A
Vm(1 +p)
mm
Vm(1 +p)
Hence,
(1+ A K4
K
Thit Thit+
< T
10
0.89p
R2
K2
Moreover, the analysis gives wx (Thit) EM7 N.M By Lemma B.2, obtain:
wx(t) E M. MM, for any t 2 Thi-
Lemma C.10 (Negative, MM. n.M..
For negative neuron & {k [m] [m/2] wx(() MM it keeps dead: wx(t) M M_ any >
Proof of Lemma C.10. Due to Lemma B.2, this lemma is trivial.
39

---

C.3 Initialization Estimation and Proof of Theorem 4.1
To get the number of neurons in the eight classes in the subsection above, we also need to estimate the initial positions of these neurons under the random initialization.
Lemma C.11 (Initialization Estimation). If ( (1)6), then with probability at least 1 we have:
k E [m/ (wx((), x4) > 0) m
20.04m,
# #(* k [m] - [m/2] (wxx (0), 00 0, (wxx (0): A (wx(0), x..)
20.055m,
#1 E [m] - [m/2] (w (0). x-) (wz (0), x+) S (w (w)(0), x 20.205m.
where
(1+4.73% ko) 73x N2)
co0 and
(1+ 4. 73m
N2) cos A (1+4, (144)3 (mentioned
[1- 1.-..3N,,
[1 1. 73. cos
in Lemma C.7).
Proof of Lemma C.I..
(i) By Hoeffding's Inequality (Lemma I.1), for any c > 0 we have:
P
{ k E [m/2] (wx(), > -
z
me
P
Σ (((w)(0),)))
>0] 2
2
m
kE(m/2]
2
T{ (0), > 00} 1 TTT (0,r 03] 2r
=P
m
kE[m/22
2 2262
<2 exp
= 2 2exp(-mee)
(ii) From (x) 1(8 without loss of generality, we can let x- ej and x+ ei cos A
22 sin A.
So have:
h: E [m] - [m/2] (w)x(0), x-) > 0, (wxx x-) A (wxx (0), x0),)
t: E [m] - [m/2] (0) > 0, wk, (0) > A ( cos A + (0) sin })}
k: E [m] - [m/2] w.. (0) > 0, (1 - cos A)w (0) > 20 sin }}
From (6), we have A >> 0 and
A = =11 1+ (1 + 4.73k)k))) cos (1 - 4.73k (p + 1)
(1 4.73x182 P (1 4.73k) A2)) COS A
4.73kI (1 + cos A) p+1 1
9.46x K22 90
<1 +
11+
< 1 + 12.66k) K2,
4.73x1
p
10
9
19
71
(1 417347))) cos (1 4.73k= 122)
(p + 1)
A = 1+
(1 4.73k
(1 + 4.73% K2)
cos A
4.73k1 Ko (1 + cos A) + (1 - cos A) p ++1
+
A
90
21
2
19
2
1- 4.73kg K2
p 10
71
1
90
>1
19
2 0.78,
18
71
40

---

1 1 A cos A Asin A
1 1- A Asin A
12.66A R2
12.66K A22 0.78 sin A
12.66M K2
25.5K1K2
Asin A
0.782
A
100
For simplicity, we denote the event
A₂ = Wk, (0) > 0,
1
2k,1 (0) > wn.2 k E [m] - [m/2].
100
Then we have the estimate:
k E [m] [m/2] wx, (0) > 0, (1 A cos A 10) A0) sin A
ス k E [m] - [m/2] wn, (0) > 0, 100 W7,1 (0) w0,2
Σ
1(A}).
[Elm]-mm/2]
We first estimate the lower bound for [T[T AA H|:
1
E [[( Am }
P(Am)
Wm.1
(0)
> 0,
100 Wm.1 "m,1( > mkx2(0))
(0.10)
P
91
0,
1
91
92
91 > 0. < -100g)) = =P 91 > 0. < (100g2)
|19||
100
||
IP
100g2 > 91 > 0)
>
sup
PP
92 1, 1001
91 > 0) g~
sup
P {1 > :))((1001 (100s g 930)
1>0
t>0
2P 2P g
)
1 P 10 > g > 0) 2 0.23.
Secondly, by Hoeffding's inequality (Lemma I.1,, for any >> 0, we have
P
[[ 0.115m S =- m
SP
[[Aa]
2 [[Am)]
--
s m
kE(m]
m2/2]
ke(m)
[m/2]
=P
2
Σ
I(Ac] E [(Am] S s-e) [E [[T(Am)]]
S exp
2( 2( )26 -exp(-me?)
m
km(m)] [m/2]
2
(iii) This proof is similar to (ii). From (x) ~ U(Sd-1), without loss of generality, we can let
x_ = e1 and x4 = e1 cos A + eg sin A.
so we have:
k: E [m]] - [m/2] (wx (0), x > 0, (wx( < (wx (0), x->}
k E [m] [m/2]: wk.1 (0) > 0, wk.1 (0) cos A + 2x.2 sin S Bw (0)}
k E [m] [m/2]: wh.1 (0) > 0, (B cos A mk. (0) > (0) sin A }
From (6). we have B > 0 and
(1 + 4. (1- cos A
(1 4.73k31k2) cos - 4.7kk {
B - cos A
(1 -1-48 4.
(1 4.73%, 162 (p
cos
+ posss A) cOS
4.7 4.73x1 )
(1 4.73k1/2)
p pinn A + 4. 4.7 + cos A coss A
sin A 9.46K142
p+1
(1 k.733n
(1 + 4. 4.73%, Ko2)
1- 4.73
p cos A
10
9
sin" A 9.46
A
p + 1
sin A + 9.46 5100
siin A
p+1
2500
19
1
1
19
10 P 9
10
0.315 + 9.46m
10
sin A
5100
sin
A
18
10
2
I9
10
9
41

---

For simplicity, we denote the event
1 B5 :== [( 0, -0,220,,0 (0x > mx.2 e [m] [m//2].
Then we have the estimate:
# k [m] - -mm/2] (0) > O, - cos A)wk, > (0) sin }}
S S# k E [m] - 1m/2| (0) 0, (0) wt.2(0)} = E
1Bb3.
ke(ml (m//)
We first estimate the lower bound for R[[[ Bm }|:
1
IE Bm }
P(Bm)
Wm.1 (0) 0, 2
Wm,1(0) (0) > ww,2(0))
g~.110.111
91
1 91
g2
91 > 0,91 > 292) = -P(91> 0,92 S 50) + P((11 > 2gz >
0,
PP
||9||
2 9g
|
1
+ P
91 > 2g2 > 0) -
+
(
to0
c
/
/ e :
dydx
S
1 1 +00
2 J
/
x
2e
- dx
4
2x 0
4
2
1 -
4m
Secondly, by Hoeffding's 's inequality (Lemma I.1), for any e >> O, we have
P
Σ
IBxx (5
1
m
m
2 é
SP
Σ
I(Ba]
T2 E
[[BBBBB]] 2 m
2
8T
kE(m)
mm
kE(m)
[m//2]
=P
2
I(Ba) - E [1[
26
exp
2 2 )262
exppp-mee
m
[m) [m/2]
2
let c = 0.08 and i = 4 4exp(-me> /2). Combining the uniform bounds in (i)ii)iiii,, we obtain this
theorem:
(4/ 0.08
If m >
then with probability at least 1 - 6, we have:
# k [m/2] (w,( x.) > 0) m
<0.04m,
4
# k E [m] [m/2] wn. (0) > 0, (1 Acos A Wk. (0) > Aw) sin A
0.075m,
# k E [m/ (0)
0, (B cos A 1k (0) wk.2 sin A
0.205m.
So far, Lemma C.3, C.4, C.5, C.6, C.7, C.8, C.9, C.10 characterize the training dynamics of each neuron in Phase I, and Lemma C.11 estimate the initial positions of the neurons. Now we can prove main theorem in Phase I.
Theorem C.12 (Restatement of Theorem 4.1).
Under the data Assumption 3.1, let the two-layer network trained by Gradient Flow (2) starting from random initialization. Let the width = 5i (log(1 (1/5), the initialization scales satisfy (6). Then with
probability at least 1 - 5, the following results (S5)~(S5) hold at the end of Phase I (Ti = =0
x1
Nz
(S1). For positive neurons E [m/2] (Sk = 1). let K4+ be the index set of living neurons, i.e. K4 = {kr E [mm/]] wa (T;) E Mt] Then 0.21m I |K+1 0.29m. Moreover, for any neuron & E K44, it has the following properties (P1)(P2).
(P1). Its norm is small but significant: 4.66 R1
12
S (Ti) S
m
mm
42

---

(P2). Its direction is strongly aligned with pa:
(1
(w)((T).)) 2 (1 (1- (1-422/k1kzz)
(
2
1.15
1+ 0.7 (1+9.9,
9.9,
= -s== let K- be the index set of living newrons, i... K-_ = {k E [m] 1m/2] (Ti(Ti) E MI UM]. Then 0.075m & [K--| S 0.205m. Moreover, for any neuron & E K-,, it has the following properties (N1)(22)(3)..
(S2). For negative neurons & E [m]] - |m/2]
V2
K1
11.1 A
(N1). Its norm is tin: : (T)(T) S
4.3,
m
R2
1+p
(N2). It lies on a manifold perpendicular to x4 : wx((t)
EM, nM
2
(N3). Its direction is weakly aligned with x (Ti), x +)
1.6
2.32,
K2 A Ni 1+p
(S3). For other neurons lo & KC_ UK_. it will remain dead forever:
(Ti) MMMMME bx(()= = bT),, Vt E [T,
(S4). The predictions for x+ and have the estimate:
0.978K2 K2KK2
P 1
-0.1)
If+ (Ti) I 3.85kz K2
p p-1
0.947
cos A 0.2
STi( S 3.855m2 K212,
p+
and the training accuracy Acc(Ti)
P
1+p'
(S5). 0.258 < 0.075 0.29
K
0,205 0.21
0.977 < 1.
K+
Proof of Theorem C.12.
This theorem a corollary of Lemma C.3, Lemma C.4, Lemma C.5, Lemma C.6, Lemma C.7, Lemma C.8, Lemma C.9, Lemma C. 10, and Lemma C.11. We focus on the end of Phase I: Ti 10 81
Proof of (S1). From Lemma C.11, we know that: if m = Q (log(1/8)) (1/8),, then with probability at least 1 8, we have:
# k E [m/2] (0) > 0} m 4 # E [m] - [m/2] : (w) x_) > 0, (0) A (0), z+>
<0.04m,
20.075m,
# k E [m] - [m/2] (w)x (0), .- > 0, (w (0), < B (w) (0), x0)
<0.205m.
where A (144.7xgm22) A- (1147
(1- k.l (1t cas and B (144.73mp=2)p (1
(1-4.7361 (1+4
Recalling the dynamics analysis in Lemma C.3, C.4, C.5, and C.6, we have:
0.21m S |C+ # { E [m/2] (wx (0), x > 0) s 0.29m.
Recalling the dynamics analysis in Lemma C.7, C.8 C.9, and C. we have:
|K-| ž # k E [m] - [m/2] (wxx (0), x-) > 0, (wmz (0). x-) > A (w)) x+))
2 0.075m,
|K-| v # kE [m] [m/2] (m (0), ) > 0, (w (0), ..) < B (w): (),x=)) < 0.205m.
43

---

Moreover, the estimates in Lemma C.3, C.4, C.5, and C.6 ensure that for any & E K.,,, the following results hold:
2
(w (Ti), 2 (1-422/118)))
1
1.15
1 - 0.7 119.9
12
4.66 K1R22 Vm
12/K1n2
S (Ti)
S
Vm
Similarly, the estimates in Lemma C.7, C.8 C.9, and C. ensure that for any l E K__, the following results hold:
VKIN2
K1
11.1 sin
A
Pk (T))
4.3g
+
vm
12
1+p p
wx(Ti) E M4
nm
2
(w (T)),
1 1.32
sin A
+
1+p
Proof of (S3). A direct corollary of Lemma C.3, C.4, C.5. C.6, C.7, C.8, C.9, C.10.
Proof of (S4). (S4) are direct corollaries of (S1)
For f+ (Ti), we have the following estimate:
(Ti Σ and (bb( x+) +
Σ ag (bx(Ti) xx))
kEK
Σ ORO (ba(TT) T x+) +0= Σ
K2
Pk (Ti)o (wi(Ti) Tx+))
Vm
KE
kEK_
N2 4.66 y N21
(we (T),, xx 2
K2
4.66
(1,, x..) - -1lwx - --all)
m
m
vm
kE
kEK.,
K2 4.66 / K2
||||| (2, x4) 2 (w (Ti)
m
Vm
KEK+
4.66x2 /
- 1p - cos A
-2+ 2 4.2//1n2
2
2 KC+
m
p+1
p+1
1
(1+9.9
1.15
p 1 p COS A
4
20.21 4.66682 K182
p p+1
p+1
1.7. 0.7
11
+
9.9
1.15
(p-1) 8.4VKiK2
20.978k2 F 11K2
p+1
0.7 (1 9.9,
N2
1.15
P |
- --.11=
20.978K2
p+1
(Ti) = Σ
62
ph (Ti)o (wo(Ti)Tenr xx_
Vm
K
K2 12 12 K2
(wy, (Ti), x+) 5
K2
12 ( (H,, +
/wx(Ti) [11
m
Vm
Vm
Vm
kEK
kEK
K2
12/K122
[|2]
+ 2 (Ti)
m
REK.
44

---

12kg /Rg
1 p cos A
4
S|
2.8.4/11
m
p p+1
1+ 0.7
+
9.9,
1.15
p cos A
50.29 12 K2
+ +8.4v K1 +
p+1
1+0.7 0.7 (1 + 9.9,
N2
1.15
4
S3. $3.48K2
+ 0.084 +
S 3.85k2 /K112.
1 0.7(1
99)
Then we have:
P 1
0.978k2 K1R2
p+1 1
(Ti) S 3.85kz 1K182. -0.11
In the same way, we can estimate (TiT:::
f-(T)) E ago (bx
(TT x-)+
Σ
ago (bx (Ti) x-)
KE
kEK
K2 4.66/K1K2
11.1 sin A
(wx, (T), x0)
Σ
4.33
(wxx(Ti), x)
Vm
Vm
m
v
K2
1 1+p p
kEK+
kEK_
4.66 (666/K1K /K182 K2
(1, - 11/0 (Ti) rell
Σ KEK-
K2
0.43 +
11.1
sin A
mm
12
KEK+
|C+
4.66 y K2
p p+1
pcos A 1
2 2+2 4.2 K2
2
m
p+1
1 0.7
(1 9.9,
82
1.15
Ri /22//1162
- ||
1.355 sin A
m
p poss A -
20.21 4.66/22 KgK22 K22
p 0.11 - 0.205 1.355 sin ANs K2
p+1
2k2 2K2VRIRS R1K2
0.978
p
1 cos A - 0.11 - 0.28 sin A 2 0.947 2
cos A - 0.11 0.07
p
P (P-1
20.947
) cos A 0.2
p +++1
f-(Ti) Σ agd (Tx) (T))TT=)>
x-)++ + Σ
agd (bı(Ti) x-)
kER
kEK
12 (
Vm
mm
kEK
K2 12 /2IN2
|| (z, + 2 (wx (T))
VI
Vm
KER.
12K2//IK2
1 pcos A
<|K+
+ 2 2.4 p+1
1.15
m
1 0.7 9.9,
pcos
4
<0.29 12k2 /1182
+ /2 +
p+1
1 [1 + 9.9
Ka
1.15
4
<3.48K2 /1INg 1+0.0844
S 3.85kz /
1 0.7(1
99)
45

---

Them we have:
((--)) (p+1'
(p-1, )² cos A -0.2 (Ti I 3.85822/1112
0.947
Due to (-i > 0 and f-(Ti) > 0, we obtain ACC(Ti) = 1+p
Moreover, from Theorem C.12 (SI)(S2), we have
0.075m
KK_|
m-
0.205m
0 < 0.258 v
a
S 0.977 < 1.
(18)
0.29m
[K+
m 0.21m
Remark C.13. The results in the following proof' are all based on the occurrence of the events in Theorem C.12. All of these results use the same settings as Theorem 4.1, except using a stronger condition on the initialization parameters (3) than (6) in Theorem C.12. So they all hold with probability least 1 5.
46

---

D Proofs of Optimization Dynamics in Phase II
In this phase, we study the dynamics before the patterns of living neurons change again after Phase I. Specifically, we define
Tu = inf (t Ti 3k K+ UK_ sgnj (t) + sgnj (Ti) or sgn, (t) * agm (Ti)),
and call / E (Ti, Tm) Phase II.
Recalling the results in Theorem 4.1, during Phase II, the activation patterns do change with sgn; (t) = agn, (t) 1 for k E X+ and sgnj (t) = 0, sgm, (t) 1 for k E K_.. Theorem 4.4 demonstrates that at the end of Phase except for one of living positive neuron kn K precisely changes its pattern on Φ-, all other activation patterns remain unchanged.
Recall that the end of Phase I, (i) the neuron lo & KC+ U K_ is dead forever; (ii) as for the living neuron k E K.4, U KC_,, the activation patterns are: for k KC+;
sgn (t) sg (t)
sgn (t) = 0, agm (t) = for k E K.
In this section, we will focus on the Phase when the negative neuron k E K__ still stays on the manifold Mº n NMM (hence is still dead for x=) and the positive neuron h KC+, is still activated for æ_.. In general, we aim to estimate the
As stated in the main text, define as following hitting time:
Tn inf
Ti 36 E K+ UK_ sgn # sgnă (Ti) sgn (f) # agng (Ti)
inf
Ti 3k E K+; s.t. (wa(t), 2+) - (wx()t,, x-) 50
(19)
or 3k K_,, s.t. (0), x+) # or (1) =0).
and we call Ti < t < Tn "Phase II"
First, define more relaxed hitting time than Tu, only about the change of living positive neurons:
T inf { Ti: 3k E KC+,, s.t. (wxx (1), ax)) S 0 or (wxx (1), x- S 0).
(20)
Noticing that the changes in activation partitions are essentially caused by the change of discontinuous vector fields, we first define the following auxiliary hitting time:
Ti = -i A inf (t > Ti (F +t)), S <0),
where (+)
P
c (44 x+ 1+p
(-(0) x_
(21)
1 1
We call Ti t Th "Phase II"".
In the subsequent proof, we first meticulously characterize the optimization dynamics in Phase I1# and then prove Tn = T = Ti. The crucial proof technique is fine-grained prior estimations for 2d ODEs on (1) and (t), leading the vector field estimation.
To begin with, we establish the following lemma about the optimization dynamics of living neurons.
Lemma D.1 (Dynamics of living neurons in Phase II
In Phase II,, E [Ti, Til, we have the following dynamics for each neuron k K_ U.+.
(SI) For positive neuron k E K.4,, we have:
wk (t) M nMt.
(bb
K2
F+
K2
-
P
14(0)
e-(() x +
e
dt
mm
mm
1+p
(S2). For negative neuron & E K_,, we have:
wx(() E M¹ n Mt
db&(!) Aze! (0)
dt Vm((1 +p) x_ - x4 COs A).
47

---

Proof of Lemma D.1.
(S1) Let & K, Recalling the definition of Ti- holds that (wx((), xx) and (wx x-) for any Ti
_ Tt so the dynamies holds.
(S2) Let l E K_.. Recalling the definition of Ti, it holds (F+ x+) > for any Ti 1 S Ti-
Due to wy (Ti) E MM. n.t,, we first analysis the vector field around the manifold Pt n Pt for Ti S - T
For any b p n and 0 < d0 < 1. we know that P4 n - separates its neighborhood B(b, 6n) into two domains G_ {b E B(b, do) (b, x-) 0} and g_ = {b E B(b, do) (b, x+) > 0}. Following Definition H.I, calculate the limited vector field on b from G_ and G+-
(i) The limited vector field F on b (from G-): db dt FT, where F
82 -000xx
m 1+1++ +
iii) The limited vector field F on b (from 9+):
db
F+ where F+ K2
pe pe- (e f(())
ef (4) 2+
+ x
dt
V
1 1+p
(iii) Then we calculate the projections of F and F onto x+ (the normal to the surface p PT):
(1))
F F x vm(1 (1 +p) cos A,
Vm((1 + cos A K2pe -2(() f+(()
Rze5-(t) (t)
F F+ xx)
Vml(1 +p)
We further define the hitting time to check whether wA (t) M. nM for Ti S Ti.
= Ti inf(t > Ti 3k K__, s.t. (w) x 03.
From the definition of Ti. we know (F (t), > for any Ti S S Ti, so F And is clear that F 0. Hence, the dynamics corresponds to Case (I) Definition H.1 (Fğ and
F < 0), which means by (t) can not leave pt (i.c., (bx(t), x+) = 0) for ortt E [Ti -_ and the dynamics of (t) satisfies:
db
fN LE [Ti,
aF +1 a= JN 5
dt
which is
db&(t)
(2)f-(t)
(x--xx
x x x. cos
x A):
1 E [Ti,
dt vm(1 +p)
By Lemma C.I. know that the dynamics of (x)() on Ma n nmt and the dynamics of pa (t) are:
dw)(t)
(2) (2)
x (w) x x ww x cos A).
dt
p+(t)/m(1+ pp)
dpx(t)
K2el- (1)
(w) (t), x-).
db vm(1 + pp
From this dynamics, for any t E T"} we have
(bb()))) 1- dbx(s)
ds x )ds ds
-bbx(0), x-) f/' kx)
sin? Ads > (0), x >0 0,
which means that Ti - Vmil1 + +p)
48

---

Noticing that Lemma D.1 determines the activation patterns for living neurons in Phase I1s, the next lemma gives the first-order dynamics of f+ (t) and (t)...
Lemma D.2 (First-order dynamics of predictions in Phase II*). In Phase 11 (Ti S L Ti) we have the following dynamics for J+ (1) and f-(1):
(t)
pe (0)
cf (c)
Ri m
COS 4).
dt
m
1+p p
1 1+2
dt-(t)
m4
(pe
(+(()
COs A
ef-(()
K22 m 1 + p
2 ef (t)
sin 2 A.
m
1+p
1 1+p/
Proof of Lemma D.2.
From the definition of Ti for any Ti S 1
Ti have
(t) Σ
(6 (t)x+) -
Σ
or (b (b (t)x+)
Σ
K2 by (t)x++
m
Vm
KEK+
kEK
KEK+
[-(1) = Σ
K2
o (b (1)x-)
Σ
K2
o (b) (1)x.)
= Σ
R2 by (1)x
82 by (1)x...
V
vm
vm
vm
K
kEK_
REK.
REK.
With the help of Lemma D.I, we have the dynamics of predictions:
(t-
Σ
K2
dbx(t)
n2 Σ
(1
P -1-1
ef cos A
dt
m
dt
1+p
1 ++1 p
K
KEK+
(A(
ef
(4)
m+
2
cOs 4).
N2
m
1+1 p
1+p
df-(t)
dbb(t)
Σ
R2
(tp
E
dt
vm
dt
mm
dt
kEK
kEK
pe-
pe
(t)
COS A
el
R2
[ cos? 4)
m
1+p
1+p/
m
1 p
k
pe -f+(1)
ef-(1)
ef
m+
K22
COS A
m_
R2
sin A.
m
1+p
1+p
m
1+p
Due the specificity of the first-order dynamics, the following lemma gives second-order autonomous dynamics of predictions, which is is the core dynamics in this phase.
Lemma D.3 (Second-order Autonomous Dynamics of predictions Phase II*),
Consider the following two variables:
(u(I) = n2 m I+p V(t)
m P --100
K2 m (-))
Itp
Then the following autonomous dynamics of and (tt) hold in Phase 11 (Ti $ Ti):
deA(t)
U(1)V(I) cos A - -(2(1), aVLe) u(t)V(t) cos A- v²(() (1 + ain A).
Proof of Lemma D.3. Recall the first-order dynamics in Lemma D.2:
(f) dt
K2 m
pe -
(1) (8)
COs A
1+p
1-p
df-(t)
dt
Ki m+
m
pe (1)
1 l+p
008
(f) (1)
1+p
K2
1+p
sin? A.
49

---

Then this proof is straight- forrard calculation:
dt((t) m4 p de de- (+())
=-K2 2 m4 P c c-110)
=K²
dt
+ p
dt
1 p
dt
= ((t) df+(t)
= =((t)V(t) cos A - (t(),,
dt
av(t)
2 m2 1 def (t)
2 14
ef (t) df- (t)
222 m 1+1 p di
Kig
di
1+1 p
di
=V(1) df- (t)
= ((1)V(()) cos - (2( (1 + sin 2 A)
dt
Lemma D.3 enlighten us that we only need to study the dynamics of (tt) and (tt) to study the dynamics in Phase II, where U(t), Vtt) satisfies the following autonomous dynamics:
dei(t) (tt))(tt) cos A - ((((t); aV(t) u(t)V(tt) cos (t) (1 + aa A)
t 2 Tri
de
(22)
(U(Ti) .n2 m+ P -4(1))
in Itp
V(TT) .22 m4
T+P (1)))
The next lemma provides fine- fine-grained prior estimate of the dynamics (22).
Lemma D.4 (Fine- Frinnggrained prior estimate of the dynamics (22)).
For the dynamics (22), then we have the following results:
(S1). U(Ti) = (x2) and v(Ti) = =
(S2). For any t 2 Tú, we have U(t) V(t) > 0.
(S3). If we define the hitting time == inf { Ti ((() cos A S V(1) (1 + ain? 2)nnn2) 3) }.
then
1 sin? A
U(TT)
V(TI), V(T)) O (R220
1
Cos A
log(1/A)
p p1-coe3 1
p 11
71 0
-
12
2
R2
(S4). For any t 2 we have
+
m
sin 2 A <
U(t)
<
1 + 2a sin?
2m+
V(t)
cos A
u(1) =
7 V(() = θ
+ A2 - T1)
P T.
+ 12 - T1)
(S5). For any 1 2 Ti, we have U(1) - V(() cos - (APV(()) > O.
IIToors 1og(1/2)
(86). For any t 12 T2 = O
2 2T,, we have
k3
U(t) cos -VI)) = - (A2v(t)) <0.
Proof of Lemma D.4. For simplicity, in this proof, we denote
: a sin A.
50

---

Step I. Preparation. From Theorem C.12 (S4), we know 0 < f+(T)).f-TT) & 3.85x2 /11k2 S 0.04 (1g())))) so
<< e<(0))) < 1 -
K2 1 + 1.004 3.85 /2 S + 3.87 / K2,
1 e -/ 2
K1 K2 2 1.004 3.85k2 2 /
Notice that ((T))
1i2 m ltp
m P (Ti and V(Ti) R22 m I+p
el (Ti). Then we have the estimate:
(
1 - 3.87x2 / S
S 1,
2 L
K22 Itp
V(zi)
1
S 1 3.87K2 R1
2
14p
From Theorem C.12 (S1)(S2), we have
0.075m
0.205m
0.258 <
5 0.21m
& 0.977.
(23)
0.29m
Fort = Tí, it holds that
(TT)) cos A (TI) <0,
(TTi) cos A V²( (1 e)+ 0.
Step II. A rough estimate on ((t)) and V(t). In this step, we aim to prove:
u(t)= > V(t) > 0, .u(()) + (tt) s ((T) - (TT)), Vt E (Ti.
First, from the definition of ((1) and (()), we have (1(1) and V(I)= > 0.
Then we consider the dynamics of (t) + ((). From
d (u()) + v(1) 224(()VV(( cos A (P (1) di
= --(((t) - V(t))² cos A (1 cos - (1) COS A) <0
we have
u(1) + v(I) S (((T)++((TT), 44 Ti
Then we consider the dynamics (f) V(t). We define the hitting time
T--V inf { 2 Ti : u(() S v()
For any t E [Ti, Tu-v), we have:
d dt (u(())(())) = -1)()) -0)))--))==((()+ + V(0)) -
> (u(()) +
- (4(T) + V(ZI)) -())((t())))) V(t)),
We consider the auxiliary ODE: di P(t) (((TU((((TT)))P)) where P(Ti) =
0. From the Comparison Principle of ODEs, we have:
u((I V(I) 2 P(L) = (4(Ti) - v(Ti)) exp ( (- (((((T)++ V(T))) --)) >0, VI E nv,
From the definition of Tu-V, have proved
Tu-y = too; u(t) > V(t), Vt [Ti, +00).
Step III. Finer estimate in the early Phase t E [T, n.. Define the following hitting time
= inf {1 2 Ti (()) cos A (1++))
51

---

From Step I, we know 7i exists and T,. From (22), we have 20(() 1 E [Ti, m. Moreover, we have the following dynamies for E [7i, TI):
< 0 and dv())
when
dt
dt
dul UV cos A 2122
cos A - (4)
dV Co cos A (1++)
D cos A - (1 +
we define (t) =
u(d Vit) then we have du = ZdV + Vdz.
The dynamics above can transformed to:
d2
2 008 A z²
Z cos A (1+c) 2;
dv
which means
1 +
sin A t
dv + cos +
d2.
(1 + cos + c) 2(1 + cos A)
Integrating this equation from Ti to E [Ti, m1), we have:
V(() ((Ti)) )
+
(()
log
log
1 cos A te
2
sin A +e
(1 (1+ cos () cos co0 )
(1 + cos () (1 cos o1
log
LE (T),)).
11 + cos A + (1 + cos A)
(24)
From the continuity ufu()), v(t) and 2(),, we have
1+e)
= inf 2 Tr: 2(1) S
(25)
cos A
Combining (25) and (24), let f + 7i Then have:
2(T1) = 1
Cos A
((m)
AFT
(1 + cos (T (1 + cOs + +()
V(n) = v(Ti)
> 0.
((Ti)
+ cos A) (1 + COs A + +e)
cos
where
3 KR
u(Ti)
Ps ((T))
V(Ti) S p.
+ 3.87kK
Therefore,
((m)
p 0088 A
1+ Ireas
sin 2 A +
zin 4100
V(Ti)
lte
((1 COS A)p
(1 + E)) cos A
V(TI)
(1 -1-33 3.87k2 p COS
sin 2 A +e
>
V(Ti)
(1 3.87.2272 /1 (1
(1- (1-388kk///1e)]ttteee A)
p (1 cos A +)) cos
143.8TN2/RR1P
and
1 1+ V(TI),
u(
cos
where
V(T)
5
Kg estimated in Step
Step IV. Nearly tight bounds for 71
From the definition of Tı, have dv(() Vt E TT) So we have
> 0 for any [T, thus V(Ti) < V(t) < V(n).
dt
u(t) cos A (1) < du((1) < u((t)V(m) -P(()) V e (Ti.)).
52

---

We first estimate the upper bound for 71. Consider the following dynamics and the hitting time
dølt) ((t) cos (t),, z Ti dt (Ti)) = ((T)).
/ inf { Ti: @(t) S {((T))
Then Ti < T/. From the dynamics of (t), for any t E (Ti, -;', it holds
o(t)
log ((1) ((T)) cOs A
= (t- ((--T))V(T)) cos A.
cos
Therefore,
1
(((+)) (d(Ti) V(TT) cOs A) ((Ti) (o(rl) ((rr cos A) [((TT) (L((T)) - ((TI) COs A) (Ti)) (M(()) V(T) cos A)
7/" Ti V(ri) cos A
log
1
V(TI) cos A log
With the help of Theorem C.12, we have m=
(1) and m- = 6(1) From Step I, we have
C=
((Ti) = (k2) and v(Zi) =
Moreover, holds
3
V(T)
It p p1-on s+c
2
sin A+C 11+000 [e](-o- d)
cor & Hooe
cos = (p: [1
=
V(Ti)
V(n) = + (V(T))p
Cos A
hig
Ttoma
It is easy to verify
u(T))
1 V(TI)
=
((Ti)
p
cor
θ (p 1oo
((Ti)
cos A(TTi
U(Ti)
u(Ti) V(Ti) cos A
x2
p
k2
p T+oos
+
= =0
U(T) V(T) cos A
ltc cos A
cos A)
nZg 14cos
kig A 22p
Itcoe
A
Hence, we obtain the upper bound for T1:
p 140oo
TI S T
Ti
log
p
RPp Ireos
KK1 (V
p 1 & log(1/A)
p p log 1/A)
+
+
=
K22
R2
In a similar way, we can derive the lower bound for 71. Consider the following dynamics and the hitting time
dwjt)) ((t))((i) cos - (t), t2 Tı. de (Ti) = U(Ti).
inf inf { > Ti (t) S {((TT)
Then 71 > T.. From the dynamics of (()., for any E (Ti, (T]. [ it holds
(t)
log (t) - (Zii cos A
= - (T) cos co
Tt.
Therefore,
((71') (o(Ti) V(T)) cos A) (TT)) (Ø(7)) - V(Ti) cos A)
c Ti V(Ti) cos A log
53

---

1
U((T)
- V(T)) ( cos A)
v(Ti) cos A log
((Ti) (2(T)) - VV(i COS A)
1
1+ V(Ti) (M(Ti) - (((T)) cOs A
log
V(Ti) cos A
u(Ti) (2(TT) - V(Ti) cOs A)
is easy to verify
V(T)) (U(T)) - ((T)) cOs A U(Ti) (U(TI) - V(Ti) cos A)
1 K2 p Tian
coa A 14000
= p
P 1/13
Itcor
p)1)
thus
V(TI) (U(Ti) - U(TT)) cOs A c08
log 1+
0
u(T) (U(TT) V(T) cos A)
Hence, we obtain the lower bound for TI:
2 ol +
P
T
=0
[0(V
K1 Kgg
+
p 1
0
p p 5
K2
R2
Step V. Finer Estimate in the late Phase t > T1
In this step, we focus on the dynamics when f. m1-
First, we will prove the following nearly tight bound about the ratio of ((t) to V(t):
1+ E <
u(t)
< 1+ 2e
Vt too).
2 ((t)
cos A
For the right inequality, we define the hitting time
1 2e cos A
Tu,y = inf ( > TI :(()) 2
v(0)
From
24(m)) v
1+e
1+ cos A
we know Tuzn exists and u/ > T1.
cos A
For any 1 E (TI, [(m)))
consider
d
u(I) 1 2c v(0))
-1-111 1+ + 2c
U(I)(()) cos A - L((() + 1 2c
(1 (1+))
d
cos A
cos A
cos A
((t) 1+ 2E
(u(t)+ + (1 (1+ 2e) +
v(t)
cos A -005\) -cos
coos A v(t)
cos A
+ coss A (1 + 2c)
coS ) + 1 + 2c (1 (1) (²((1)
1
cos A
(u()) 1+ 2c
cos 1 v(t)
(u(t) +
(1+26) + 1
-cos
cos A v(t)
cos A
+ (coos A- - -1) +
1 1 2c
26)
1²(())
COs A
u(t) 1+ v(t)
(u(t)+ +
(1+ (1+26) +
1
- cos A
v(t)
cos A
cos A
Step II
(1 (1+2c) +
1
cos A
(U()+ + V(t)) (u(t)
1 2c v(t)
Cos A
COS A
Step II
(1 (1+ (11+2) 21)
1
cos A
(U(T) + V(T)) ((())
1+ 2c
cos v(t)
cos A
For simplicity, we denote C := ((1 + 2c) cos -
cos A) (U(TT) + V(Ti)) > 0. We consider
the auxiliary ODE:
d P(t) PC)((t), where P(T1) U(T1) c V(n) < 0. From the di Comparison Principle of ODEs, we have:
u(t 1 2e v(t) $ P(t) P(TT)e P -i(t-n)) < <0, Vt E (T.)
cos A
54

---

From the definition of ////,, we have proved
T//V +00;
u(I) 1+ 2E V(I,, V1 (o)) cos A
In the same way, it can be proved that
u(t) > (1+ (1++++)+00 2)00,, W (oo)
Moreover, we also need to derive a tight bound for U(1) and V(() when / > nI respectively.
For any / > 71, we have
d dt v(t) -0 (1+)))(())
cos (1
>0 114++2100
()(()) cos A - (1+ (1 ( cos 4)
(²).).
We consider the auxiliary ODE: de P(t) = - From the Comparison Principle of ODEs, we have the lower bound for V(t):
(000)=(((+))))))))0 ((1+)) (1++) 2) cos a) P)²(()) where P(TL) = V(n).
V(t) 2 P(t)
WE (TI, too).
DirT + (1++)) - (1 + 5) cos (1-
In the same way, for any > TI, we have
d dt
u(t) = u(t) (V(1) (os) cos A -
<u(t) cos A 1+ - u(t)) -
cos A
1 (t))).
We consider the auxiliary ODE: a Ptt) -(1 (1-
c (t),), where P(Tr)= = U((1). From the 1+$
Comparison Principle of ODEs, have the upper bound for
u(t) < P(t) =
Vt E +oo). ) (l-
U() + (1
(1- I+&
cos A
The upper bound for Vtt) and the lower bound for (t) can be estimated by:
U(t)
1
V(I)
4l (71,
1+ 3/ 1+ E 1 +
(1
A
(t 71)
u())
l+;
u(t)= > (1+ 2) v(t)= N
1 +
Vi E (TI,
1
- C (1+1 c) (1 + 2 cos 1 (t-
(t (t-
v(n)
Hence, we obtain the tight bound for U(1) and V(I):
<u((t)= <
Vt E (T))
1tc +
cos 2) (1
[(.)))) + (1
A
m1)
[++))(())
1+
1
1
$ Vtt) <
Vt E (TI,
V.j + (1++) - (1 +
cos A cos
(1)
1+1 [[))
+
(1 + 1 cos (0ss))(-T)
means
p | log(1/A)
u(t) 0
1
2
p
p1
+ A2 - -n)
R2
55

---

| a log( 1/A)
V(t) O
p pl A
+ A2((t - m1)
Ki
Step VI. The tight bound for U(1) - V(() oos
From 1 + <
M(t) v(()
1+2r
proved in Step V, the two-side bound is straight-forward: for any 1 2 TI
cos A
u(t) (t) cos A >
(1+ é
cos ))(())()))))))))) - θ (
V(0)
2
u(t) Vtt) cos A
+ 2e
cos coss))(()) (A))
cos A
Then we obtain
u(I) V(() cos A = ((AV(())
V1 T2..
p 1ifood
+ (t-
Step VII. The tight bound of ((t) cos A V()).
If we follow the proof in Step VI, 1 2 <
u(t)) v())
1+2c cos can only gives us a loose two-side bound <
for 21 (t) cos A Vtt:
m_ cos A - 1) v(1) 3 (A?VV())
U(t) cos A v(1) > cos A +
2m
U(t) cos A v(t) cos A (1+2e (1+ 11=2=-))(0=0(AA91))
Hence, we need more fine-grained analysis to derive its sharper bounds. We first focus on its sharper upper bound. From the dynamics (22), for any t 2 Tí, we have
d ((t)) cos V(1))
dt
(U(I) cos A v(1) (4(1) + ( (11 + - cos -cs A)V(1)) - - - cos A - -c)x2()
cos A
cos
(u(t) cos v(t) (u(t) +
+1 - cos A)V()) - -V(()( 1
cos A -a) sin" A
cos A
We define the hitting time
ut = inf t>> ni Ul()) cos -()) (/))s0.
From M(m) 1tc V(m) cos A we know THn exists and TØ// > T1.
Then for any t E (TI, whyn), we have (tt cos A - V(f) > 0, so
d
(U(1) cos A - V(1)
dt
= (u(t) cos ((t))((()) +
+ 1 - cos A)v(t)) - v²(t)
cos 1 a) sin? D
cos A
IV
(((t) (((t)cos cos v(1)) cos A
+ +2+ 2
cos A) v(t) - 1²())
1
aa) sin A)
cos A
sin" A cos A
+2+ { (u(t) cos - V(tt)
sin" 2
Ie IV
0os
A -
a
p(m) + (1 E) (1+ + } cos A
TI)
पाता + (11
(1 + { cos 1 (t (L-r1)
56

---

For simplicity, we denote A Vir.j B = (1+ (1 +
2 cos A, Ci
sin
+ 2 + 2.
cos
C2 = 006 2 - a) sin 2 A. And we consider the auxiliary ODE:
dE(l)
CiE(L)
C2
dt - B(t TI) (A+ B(t 7)) 21
where E(T)) U(T)) cos A V(n) = (T))
Its solution is
B E(I) (1 (1+ A
- (1-
C2
(1
4 - B (1 (1+
)1))
E(T))
A(C1 B)
From the Comparison Principle of ODEs, for any / E (TI, (yyT) we have
((t) cos A V(t) - Ett.
((1+
Let Tg- = A
(Ci Bie
+ -1 -1) it is easy to verify (TT)) = 0. Moreover,
B
C2
A
1
p p 2
θ
-
B
V(TT) (1 + c) - (1 ]
cos A
1330
14000 a A
n2j22
1
1 (C1 - B)e
O(A2)
)) O(D));
C 1 log
= Q
A log
+
C2
0(A2)
(C1 B)e
4 1
1
(G1 B)e ) -1 0(43)
1+
1 = exp
log
1
-1-0(A3).
C2
C
C2
Therefore.
pi-cau 4
uu/v S Tg =1 + 0
A2
K3 A 2
p p - (og(1/A) =0
p -
D log (1)(1)))
+ θ
0
K2
122
K2
Then we define the next hitting time
Tujv == inf { /u : cos - - 20
From ((Tt//)) cos A - v(Tttp)) 0 and a - 1
0. we know Tepv exists
and T//v TuIV
For any E (Tt/p) Tup)), we have U(()) cos A V(t) < 0. so
d (U()) cos A V(1))
de
(-(u1())oo cos A v(11 (u()) +
+ cos A)V(1) - v2(1) (-10011
cos A a) sin² A
cos A
IV
(((() cos A (v(t)
cos I
+ 1 cos A
Ju(t) -2) (
coo A -a) sin? A)
1 1+
1 + cou a +1-cus +1-amm ())((((()) cos A - V(t))
1 -a) sin² A
Step IV
1+1
co0
1
(1- 1
(t (1)
V + (11 (1+ - (1 + { cos 1 (1 - -1) 2
u()))
1+3
57

---

+ mi (U(t) cos A - v(t))
00s & aa sin? A
l+3
a 1
(1 e) (1 + {) cos (t-
(प + (1 +e) - (1+ E
cos 2 (t (1)) 2
Ite V(T)
3( 1 + -1000 (((1) cos A - v(0))
3 - a sin A
1+5
(1 + - (1 5)00s
cos 1 ) (1 - TI)
(ाा + (1+ (1+ + f) cos A (1 - ))) 2
V(n)
For simplicity, we denote C3 3 1 man
+1-c0s
And we consider the auxiliary ODE:
1+2
dF((t
CzF(t)
C2 (A+ + B(I - T)) 2
dt
A+ 13 T1)
where
F(Tui/)) = M(T cos A V(Ta/y) = 0.
Its solution is
C2
$ (1+
B
(t - T1) (t- 8 -1 - -1)
F(t)
A
A(C3 - B) () 11 [ - -i))
C2
1
S
1
AC3(
+ B (t. - 7))
A
(1+ [1 -1)
4-
| log(1/2)
Let r/ 11 O
2n. Then for any t 2 7/. it holds
x3
1
1
exp (-(C)) C3
11)
log (1+ ( -n))
B
(1+ (t - m))
3
1
B ( 11)
B
A
A
1
~ 2
pitcor log(1/A)
exp
-
A
log 1 1+0
T
R2
exp
-0
log (1 + θ log log(1/A1))) (0)))>ccpp) =cxp -60
1
(A (A>log(1/A)))
A2
12
= =exp (looo(/))))))))))))))))()))))))) S 2
thus,
C2
(1- 1 2)
2
F(t) S
-
AC' (1 11 (1-T)) m1)
p T+mmx x
+ At - 71)
pl-ion a log( 1/A)
W -
> 2TI-
|litens log(1/A) m9
If we let 72 =
> 2T(, then we have:
A 2
-
1I 2 m2.
11
2 ((t--T) 71)
From the Comparison Principle of ODEs, for any t E (Ttp Twjy), we have
u(t) cos A - V(t)= S F(t) 0.
58

---

From the definition of "u// we obtain
Tu/V +00.
Moreover,
A
p pl+oos log(1/A)
u(() cos A 5 -
1A 2 12
+ At
TI)
Recalling the lower bound the beginning of Step VII, we obtain the tight bound:
A²
p pTicos log (og(1/A)
U(t) V(t) -
= EN1=6
I+cor
At -11)
Ki
Lemma D.5 (Hitting time relationship).
T = In inf {t 2 Ti: 3k E K+, s.t.
=inf t 1 3k K+, s.t. (b& (Ti), (" vm
((s))cos2) - ds s =0
k2m
where Tit and Ti are defined in (20)(21), and ((),, V(t) satisfy (22).
Proof of Lemma D.5.
Recall the definitions of T and Th:
Ti inf t Ti 3k E K+, s.t. (wx((), or (txx s0}
inf { { Ti 3k E K4, s.t. (1), or (1), 50)
x-) Ti inf {t {t> Ti (F (t), x.) 1 oo 3k E kC+, s.t. (t), soor (bx
where (t) 1 1 p
p
f+ x+ 1 1+p
ff xt)
Notice
F (t),
p e -f+
f- cos A
(u(t)- - V(t) cos A).
+ p
1 1+p
x2m4
And for any E K.+.
(ba(t), xx = (T), x.4) + 1" /dlb(())
1i ds x+ ds
=(bx(Ti), 1¹ vm
ST, k:2m+
(u(s) - VV()) cos A )do;
(bx(1), = (Tx x)) 1" /clba(s) (lb((s)
ds x_ ds
(T))) + S vm
(U(s) - V(8) ds.
1:214
So we have
Ti sup { Ti
((t) cos A > 0;
(b (Ti), xx+) + '' Vm
(u(s) V(s) cos > 0, 4k K4;
k2m4
59

---

(bx (T)),--) + Sr vm (U(s) cos D. K+).
ds 0, 0, E
k2m
With the help of Lemma D.4, we know that ((()) - V(t) cos A > 0 for any 2 T₁. So (T), x+)+
Vi Sn R2m44 A ((s)) V()) cos A ds > (bx (Ti), x+} O, vk E KC,,, A z Tr. Hence, we have the transformation of the hitting time:
Tī inf { 1 Ti 36 K+, s.t. (bx(Ti), x-) l
Vm (U(s) cos A v(s)) ds =0].
kgmn+
T = Tí.
Lemma D.6 (Time Estimate of Phase II).
p
Th Ti = T" =
Proof of Lemma D.6. With the help of Theorem C.12 (S1), for any k E K4,, we have:
4.66 / K2 S (Ti)
12 12
S
m
v m
(wx(T)), 2(1 (1 4.2//kn12)
1 ('
1.15
1 0.7
1 (1 9.9,
2
>1 - -.24. K2
1.13
1 0.7 (1+ 9.9
122 K2
With the help of Lemma 1.4, have the estimate of (Wi(Ti), x-);
cos A
sin A E (wa(Ti),
<
2eessin A,
12 + 2p cos A
where
2
e= 4.2
1.15
1 1.0.7 0.7 (1 (1+ 9.9
Then have:
(T)(
12/Ki12 Vm
pcos A -
+ +2vesin
p2 + 2pcos A
/1122
pcos A
2/csin A -c).
(T))
mm
2 1 2p A
which means
(T))
Vm
From the dynamics (22), we have
Utt)) cos A Vtt)
m. CoS A
(u(t) - (tt) cos A) + m_ + m4
m4
(u(t) cos A V(() (1 + sin A))
m_ + m+
60

---

COS A du((t)
m dv(t)
m- m4 (())d
m + m4 V(()di'
Taking integral, we obtain:
u(s) - v(s))d ds
Ti
V
m- cos A dll(s)
m4
dv(s)
k
Ti
m- + m+ 2(())
m- + m+ V(s)
vm
m- COS A
log u((t)
m4
V(t) V(Ti)
log
K2m
m. + m+
U(TT)
m
+ m+
m_
mm
U(Ti)
TT
V(t)
7m
log
K
u(t)) +m44
V(Ti)
m +
From Lemma D.5, we have:
Ti Tî inf { Ti 3k E K+, s.t. (Zi), x x=)
/"
vm
(u(s) cos A -V(())() ds s 0
Jr k2
Recalling the definition of 7i in Lemma D.4, we know ((s) cos A V(s) > for any S T1. so
Ti
From Lemma D.4 (S4), know
u(1) =
V(() =
p
+ A2 - T1)
p
+ A2(t TI)
22
From the proof of Lemma D.4, we know U(Ti) = (133) and v(Ti) = 6 Therefore, solving
vm
0 -= (bx, x-)
(os) cos A - ds
k2m+
T1 coo
VK1R2
vm
U(T))
+m
V(T
-0
+
log
mm
K2m+
((TT))
V(TT)
10 co
VKin2
1
u(Ti)
Fm
V(Ti))
+ θ
log
Vm
K2
Kaym
u(Ti)) (m (m_+44)
V(Ti)
we obtain
coo u(Ti)
V(T+
+m4)
exp (-0 (N2V/11K2) O(1).
=(()).
m V(Ti)
A straight-forward calculation gives us:
V(TA)
u(Ti)
(m Fm44
U(T
V(Ti)
4
my
=
19-0 19 CON
7 1
p I
+ A - T1)
P
61

---

=
m
D1t000 + ~T -1))
mi
Hence, we get
++
( 1)
p p cc
Ti - 71 =
= 6
2
12
Combining Lemma D.4 (S3), we obtain
pT-acora
p log (1()
p pi-
pT-
Ti = Tii = 110
O
+0
-
2
N2
2
R3j22
Ri A
Recall the relationship between T'r and Tif (19)(20):
Tu T A inf Ti 3k E K-, s.t. (wx(t), # or (wxr(t), x-) S 0}.
Then using Lemma D.1 (S2), we obtain:
p
Tn TH =
12
Lemma D.7 (Length of Plateau).
If we define the hitting time Tplas == inf { E [Ti, Acc(t) 1. then we have:
(S1). Tplat
(S2). Vt [Ti, } Acc(t)= 1tp"
(S3). Vt (Tplas, Tu), Aco(t)
Proof of Lemma D.7. It is easy to verify
Tplat inf {I TT] [4(() S or (1) > 0).
From Theorem C.12 (S4), we know (Ti) and f- (Ti) > 0. From Lemma D.3, we have
u(l)= = m2 m p
e f+(1) V(I) = K3 1+p
m f-())
m
1+p
From the proof of Lemma D.4, we know du(() < VI E [i, Tin,, so
u(t)= U(T)), (+ 2 f+ (Ti) Vi Tu).
Recall the definition of Tı and T2 in Lemma D.4. From the proof of Lemma D.4, we know 4 v()) > 0, Vt E 71,,00
((t) 2 V(Ti) .f(() 0, Wt [.,
With the help of Lemma D.4 (S4), we know
((t) = θ
Vt E (1,
1
p p1+000
+
A - T1)
122
62

---

Because V(Tplat)
162 m
1
we have
1+p
A2 +
θ
Vt E (T1,
p Fooo
A plat - -i1)
Therefore,
P
P
Tplt = =1 =1 +
A3
1
car Teee
=
+
RSAZ
p | log(1/A) (1/A)
P
P
=0
+
θ
N2
K
A2
It is easy to verify plat = A
Ti1 θ
p-- pi-acora corr
Because - T1 =
plicow Lou(1/A)
for any t E (TI, T2], we have
12
1
1
V(t)= A
=
T4
+
+ 72)
+
A12 71)
x2
K2
θ
V(Tplat).
p S
Thus,
f-(1)> (Tpia) VI E (T1,72--
From Lemma D.4 (S6), we know that U(t) cos A V(t) < 0. VI E (72, Tul. Then dV(() Vt (T2, Tir). Thus,
< 0,
f-(1) (Tppa) 0, VI (T2, Tplat); 1-(1) < (T = 0, VI E (Tplat: Tirl.
Hence, we know
f-) 2 0, Vt Tpatl: f-(t) < 0, Vt E (Tplat, Tu.
In summary, we have proved (S3))
Lemma D.8 (Prediction end of Phase II). (SI) For the predictions, we have:
e e-+((hn) = θ @(p Fawss
(Tht) =0 mome
((O(Ti)) 0 p coo
pc (Tm)
(Tin)i))
COS A 1 6(42)) 22p' T-n
1+p
+ p
pe (T())
(T-(Th))
0O8 A
- AA2
+
1+p
(S2). For any & E K4,, we have:
(bx((Tn),
=0
vm
(S3). For any l E K_,, we have (Tn),,,, 0.
63

---

Proof of Lemma D.8.
Proof of (S1). Recall the definitions in Lemma D.3:
[(tt)= k2 P e--1+400 14(1)
1+p
V(()
K2 1+p
m+
r- (1))
From Lemma D.4 (S4) and Lemma D.6, we have
1
u(t)
V(t) = =
Foun &
A2 - -1)
p T
+ 51)
K2
p1 & log (1/A
p 8
Tn O
KG
A3A²
Therefore, obtain the estimate:
e ef4(fm =0 (
12 u(Tn))
=
0
122
p p--co
2
N2
N A
p ( =0
P
o cor
v(Tin)
p
A
22
~
Moreover, Lemma D.4 (S4)(S5)(S6) give
u(Tn)) ((Ti)) cos A (A3V((Tn)) (RăA²)* --acoa -
1- u(Th) cos A v(Tn) θ (A2V - -13AAPP 1
Hence,
pe pe-1+(Th) (Thi)
ef-(Tn)
1
(U(Tn) V(TH) 4) =0(2") T
A
1 1+p pe (Ti)
1
82
(T-(Tn)
(((Ti))os) -V(TT)) - (A²p I-0
0O8
14p
1 1+p
K2
Proof of (S2). Denote K.. = { K+ (wx. (=)) x-) =00 From the definition of Th and the x-)
proof in Phase II, we know that (Tw) x-) > 0 holds for any h E K. ACO
From the proof in Lemma D.5, for any k K4, it holds
1" /db((s)
(bx(t), = -bb.=_))>b(Tiiii
x-) (T)(
ds x ds
=bb((T), + l' Vm kgm4
(U(s) cos A V(s)) ds, Vt E [T).
Thus for any K-4 K0, we have
(b,(Tu), - (Tx x-) = (bx. (Ti1) - (Ti), = (bb,, (Ti), x x=
so
(bs (Tn), x-)) =
-bbko (Ti).
From the proof of Lemma D.6, we know
(b) (T)). x 12
coss A
+ +2vesin
m
22
2p cocos A
64

---

4.66 /
cos A --1
(bx( x-)
2 A --
mm
p2
2pcos A
where c = 4.2/11822 + 140.7(1-2) 1-9.
This means
(K112 vm
x-) =
Hence, for any 1s E K++ - K44
0 < = =1bbx( (T)), (bko (T1). am-)l S ((bb(Ti): a-))
(bko (Ti), x-
VK1/22
θ /21
Ki /K182
=
θ
vm
vm
vm
Proof of (S3). Due to the dynamics of the neuron k E K. in Phase II, this conclusion is clear.
As simple corollaries of these lemmas, we can prove two theorems in Phase II.
Proof of Theorem 4.4 and 4.5. Theorem 4.5 is Lemma D.7. Theorem 4.4 (S1) has been proven in Lemma D.6; Theorem 4.4 (S2) has been proven Lemma D.8. Additionally, combining (i) Ti Tí in Lemma D.6, (ii) the transformation in Lemma D.5, and (iii) the definition of Tı, we obtain Theorem 4.4 (S3).
65

---

E Proofs of Optimization Dynamics in Phase III
E.1 Optimization Dynamics during Phase Transition
Building upon Phase II, we will demonstrate that within a short time, all the living positive neurons K change their activation patterns, corresponding to "phase transition". After the phase transition, all the living positive neurons k E K++ undergo deactivation for æ-, i.c., sgni (t) changes from to while other activation patterns remain unchanged.
Specifically, we define the hitting time
TH inf Tn Ak K+, sgn, (t) 0}
(26)
inf (t Tn Ak K (wx xt))).=))))) -}.
and we call E (Ti, T "Phase Transition" from Phase II to Phase III.
Notice that the dynamies during phase transition highly nonlinear with [K (m)) changes on activation partitions. Fortunately, we can keep the neurons of IC+ and K._ close enough respectively in Phase by using sufficiently small initialization K1. Moreover, their differences do not enlarge in Phase II. As result, the phase transition can be completed quickly without significant changes in the vector field.
In order to analyze the dynamics of neurons and vector fields, we introduce the auxiliary hitting time:
TP TP A inf {i Tu (F+ x+) 50 or (F+(1), 03:
(27)
where F (+) 1+
1+(1) x+
c0(10) xr.
1 1+p
call Th S TH "Phase *ransition
Lemma E.1 (Dynamics of living neurons during Phase Transition"). In Phase Transition*, i.e. E [Tir, THT*), we have the following dynamics for each neuron k E
K__ UK+
(SI). For living negative neuron &s E K_,, we have:
(xx(t) E M4 n-
(b&(t) Rzef-(0)
dl Vm(1+ +ppp (x- (x_-x+
x. cos A).
(S2) For living positive neuron l: E Kc+, we define the hitting time:
TPT- == inf {t > Tu (wxx(), x= Ainf (t Tu (F (t), 00 (F+(t) xf) 20.
Then it holds that:
(PO) TPTT max T1.
keK+
(P1) For any I (Ti TPPT*, we have
db²(t) dt
K2 (t);:
Vm
IfT < PTr strictly, thenfor any 1 E [TPP. TTPT'* we have wx(()= E M n M and (P2)
dbx(t) Kype -1 (t(()
dt vm(11 + -x+-z_ --+-x_00 cos
(P3) Regardless of the relationship between TPT.= and TPT for any E [Tir, [Ti,, TTTT we have (w) 21) O, (w) x 2 0.
Proof of Lemma E.I.
Proof of (S1). Recalling the definition of TP it holds (F, (4), ..4 > for any Tn SLS TPTx So (S1) can be proved in the same way employed in the proof of Lemma D.I (S2) and is omitted.
66

---

Proof of (S2)(PO) and (S2)P1)) (S2) is obvious. Moreover, for any k E K+ and E [Tn.. TH, ) we have (t), x..) > 0 and (unx(t) x=> for any Ti S S Ti so (S2)(11) can be proved in the same method as shown in the proof of Lemma D.1 (S1), and we have the dynamics:
db&(() dt
N2 F+(t,, E (Tu, TPT*).
Additionally, recalling the definition of TPTx know (F+(t), x+) 0 holds for any t [Ti,, THTK) Combining the dynamics of by (f), we further have:
K2
(bx(t), (bx (2iT)
(F+ (++(s) ds
Vm
Th
(bb(TTi) x+)
vt E [Tn. TH.""
Proof of (S2) Let E KC+.
TT
11,k <
TP we have the following results:
Step I. (T.( M
Recalling the definition of TPTT 11,k and TH TPT 11,k <
<TH implies that (wxx (TP,T) x 0.
Then recalling our proof of (S2XP1), we obtain (bx (TT,T) x+ >
Hence, we obtain w E -M n..
Step II. Dynamics after I. T
In this step, we will analyze the training dynamics after wa wx((T) E MM n ic. (x(T) E pt n po. We first analysis the vector field around the manifold PI n ph For any b PI ni po and 0 < 8n < 1, we know that Po n npt separates its neighborhood (bb, ōu) into two domains g_ (b E B(b,
) < 0) and G (b E B(b, 56) (b, > 0}. Following Definition H. calculate the limited vector field on b from G_ and G+-
(i) The limited vector field F- on b (from G-):
db FT, where F Vm 1 +
K2 p f+(1) f+(0 x+
dt
(ii) The limited vector field F+ on (from G4):
db F+, where F+ R2
pe f+(t) f+(())
ef-(t)
dt
vm
1+p
1 + p
(iii) Then we calculate the projections of F and F+ onto a (the normal to the surface Pt n po)
x Kope (+)
F F
cos A,
vm(1 + +p)
F Rgef (t)
K2pe f+())
F
COs A
Vm(1
p)
Vml(1 +p)
We further define the hitting time check whether wr (t) E M for T.k sts TTT
+ = inf {1 [TI TPTT): (wx( s $.}.
From the definition of T know that (F+ (f), 1+p e- (+(1) cos 1 el- < 0 for any t [Ti..TP IPTT, which means F < 0. And it is clear that Fx > 0. Hence, the dynamics
1tp
67

---

corresponds to Case (I) in Definition H.1 (FN > 0 and FÑ < 0), which means that (t(() can not
leave _ for any & E 11, r and the dynamics of by for t E [T + satisfies:
db
di = aF + (1-a) F a fN
JN JN
which is
db& (t)
Kepe-f+(5) f+(1)
K2pe
x+ H- cos A) t [Tiik -
dt
/mil + p)
By Lemma C.I, know that the dynamics of (x((t) on M n.ve and the dynamics of pk (t)
dwv(tt)
mm +p) (2+ - (w), xx) we x_ cos A).
Kape (f)()
dt
dlx(()
K2pe K2pe-1-10 1+(1)
dt vm(1 +p (ux((),, x.))
Moreover, The dynamics above also ensures that:
(bx(t), x+) = (bx(Til ). + /" Kype f (i()
sin? Ads
T. vm +p)
(ba(TH a..)) 0, 14 E
[ 77.6
which means T = TTI Hence, we have proved (P2)
Proof of (S2)(P3). Our proof for (S2)(PI) and (S2)(2) imply this result directly.
Lemma E.2 (Evolution of the prediction in Phase III*).
For any E [Tn, TPTT we have
1 Chef -Tn) Sel (0-F (Ti) <
e
1 (fn)f-((n))-)(((( Tn)
exp (1 -ii)) 5e1+(T1)-440)
$
where
K3 2
Co =
C1 O 1 of (Tn) ① (p
I-a car
cos
) C2= 602=0(1)) cos
P
Proof of Lemma E.2.
Step I. Preparation. With the help of Lemma E.1(SI) and (S2)(P3,, we know that
(i) For l E IC_, we have
(wx(t), 0, (wx(t),x_)> 0, Vt [Tn TTTT
(ii) For &s E KC,, we have
(w (1), x+) > O, (wx x; 000 14 E [Tir, TFTT>
So (t) and ft( have the following representation for any t E Th. TPTT]:
f4(1) = Σ
82 bJ. (1)x4,
mm
kEK.
f-(t) Σ
K2
by (t)x
Σ kek_
K2
by (t)x
mm
vm
kek.
Step II. Evolution of ft).).
68

---

To begin with, we need to do rough estimate of ΣKEK_ b/ (t)x_. Let k K++ For any
t tel [Ti "I we have (t), x-) = 0. And for any t E [T11, TPTT)) ) we have:
d (bx(1), x=
Lemma E.
K2
(Fu(t), x- < 0.
(27)
di
Vm
Therefore, for any t E [TI, " we have 0 S
S (bx(T11) (TII), x x.)),
82 by (Tii)
0 5 vm
by (t)x=
Vm
kEk
kEC+
bg (t)
f- (t) <
Σ
K2 by (Tu)æ=
bs (t)x
mm
REK
kE
kEK
According to Lemma E. it follows that for any h E K_ its dynamics is db, dt /m(ltp) x_
Rge (0)
x.4 cos cosss) A), thus
(t)x== by (Tnn)== + 1"' ( (dbu(s),
ds by (Tn)) + K2 sin" A
/ml(+ + '" cl-(t)
ds x
S
m_ sin A m(1 p) nn
l' ef (s
Σ by (t)x=
Σ
by (Tn))=++ +
mm
kEK
kEK-
Therefore, we have two-side bounds of ft):):
ft) m- R2 sin? A
'" e (1) Σ
N2 by (Tin)
+ Σ
R2
by (Tin)a-,
m(1 p)
Vm
vm
TT
kEK_
EEK.
f-()) m_ 122 sin? A
1'
(t)
Σ
R2 by (Tu)o_.
m(1 + p)
Tn
KEK
mm
For simplicity, we denote Co
K3 sin" A m(1+p)
C ΣNEK_
(Tn)e= and C vm
N2
K2 b2 ΣKEK,
yo by (Tn)a... Then we have:
-Co L" c- C Cf -C -Co 1" l/
--
Let v((1== = Sú, el-(o) then dd(1) el-(1), So Vi (TT)) 0 and
-CoV(1) C SIS.S log (dv(t)
< -CV((()) C + +
dt
dV(()
c- < dt
I --+0t= -CoV(()
For the right hand, for any e (0, 1), we consider the auxiliary ODE: aP())) di P(TT)) = 0.
The solution of this ODE P(t) th log (1 + Coe 0I+LH0 Tir). From the Comparison Principle of ODEs, have the upper bound for (t):
v(()) S P(() = Co
log + CI
Taking 6 - 0, we obtain
1
log (1 + Coe -0 -Ti))
(t) < Co
69

---

In the similar way, we can derive the lower bound for y/ (t):
((t)=
1 C.
log (1 + Coe Coe---tttt (t--tTi))
Consequently, infer that
f-(t) - (t)((t) CI + 5 - 1+ Obe -t Tii) - C + +
f-(t) 2 (t) C 2 log G1+
Cue - Che
(t (t-Tii) Tul) C_.
Noticing (Ti) = C C_. we obtain
-log Cl-
+0 (t (e-Tinl Tri) C.
- -f-))--) - - log 1 Coe C-e (t-i)l)))
Noticing (T1i = C -C this inequality means
e c-
I Se (()-(0)--(7)))
<
1 1 Coef (ti))t Tin)
1 Coelt Co Tn)
m3-n3slu"" m(1+p)
n31² p
where Co-
Moreover, according to Lemma D.8 (S1)(S2), we have
(Ta) =
cox
c
K2
bl (Tin)ac = O m
K2
= O (112)
KE
Step III. Evolution of (t).
Let k E X.+. According to Lemma E.1 (S2)(P2) and (P3) it follows that for any k E K its dynamics during E [Tn, TPT> is
db.(t)
K2
(t).
dt vm
(b.
Kippe (1(1)
x.. x cos cos
or
dt
/m(11 + p)
Notice that
+ Σ 1' /dbx(l)
f+(1= Σ
b (1)++
Σ by (Ti)aa++
x. ds
vm
Vm
KEK, Ti Vm ds
KEK+
kEk
dbx(t)
[TT(Tn)
++ ds.
Vm
ds
KE
On the one hand, for any t E [Tn. TPTT], we have the lower bound:
min { 2+)) pe (s)
24()2
1+p sin A Jdss 2 fTir)).
kEK.
Tn
On the other hand, for any [Tı. TPTx) we can derive an upper bound:
pe (+)
f+(1) (f+() +
max
(F (s), x+))
sin? A ]ds
m
kEK
Tu
1+p
pe f+(s))
pe- (x)(s)
pe
(TT( +
max
sin" A ds
1+
1+p
kEK+
Tu
((())
ds < f4 (Ti) + 12m pe (Tn)
(Ti( +
Σ
pe
(t - Ti))
Tu 1
+ p
k
70

---

Hence, we obtain
22 k pe -f+(Tn)) exp
(1 (1-Tir) Tir) S sel+(Ti)~++()) 1
p
where
k.3++ pe -
Lemma D.8 θ (nze (nze- =0 -1(2p (13P-T a
m
1+p
Lemma E.3 (Nearly fixed vector filed in Phase III*), There exist absolute constants Q1, Q2 > O, such that: For any time Tix [T1,+ +00), if we choose K1, R2g s.t.
N2 Tix A THP PT+ Tu))
Faco O(A7),
2
K1
O(A2),
K2
then for any E [TI, Tix A TPPT", we have
Q1 A2p 1-cco (t),
Q2 A2P 1-0cord
(++) <
2
Proof of Lemma E.3. For simplicity, we denote d7 = Tix A THT Tn From Lemma E.2, for any E [TiT, Tix A THF*) have
e (0(0)-1((mm) -15 1 (he))-171--G155
1
150, c - 1 Coef-(Til
e C
(Tw)dT
C1 + Coef (Tul
(-(()-f((T)) -12
1 Cnel-(Uh)8T
1 Chel-(Un)
+ -
(Tn)))) -1141011111 1
cf-(4h))1-10) 2 e C2ór 12 -C2ōT.
Recalling Lemma D.8 (SI), there exists absolute constants Q1, Q2 > 0 such that
(F+(T pe- (4(hr)
ef-(Tn)
COs A 2 4 000
1 1+p
1 1+p
pe- (Ti)) (Tin)
(Tn)
(TT)),,....
0O8 A
< A2 G0E.S
1 1 p
p
Step I. Bounding the term
(F+ x+) - (F+() x+)]
(1-
Jf(TT))
P e -1())
P e (11)))
+pp COS A +
COS A
1+p
1 1+p
1
ef COS A
ef-
P f4(1)
p (4(Tin)
COS A
1 p
1 1+p
1+p p
1+p
1 + ed (Tn)
P-e---10 (-(Ti) (f((T1)-4(0)
e1
1 I+p
1+p
II C- 1- (Th) (T80 (Ti C1 + Chef (Tu))
1+p 1+ Cyel-
To ensure
[P [F+( - (FTT),), x+)1 1Q:22p
T-O we need only select parameters
such that
(Tw C + Coef (
p (Ti)) (TT) +
< A142p
1 p
1+p 1 Coel-(Tu)8)
2
71

---

From Lemma E.2 and Lemma D.8, we have:
122 A
C. c=
C (K(VVKI2)))
C2 = = hig
P
e c- (Tul = 0 (p (-Tooox))
ef((T)) = - (p
uew &
Therefore, if we take
Coet- (Fii 0 = =
then we have
ef-(Tu) C1 + Chel-(TTi)))
P c
C28) + 1tp 1 Coe! (TT))T
+
Kgp i- s
1 + (p-ian (O(K2/ + x2GA2p 1-acos - 28r)
A1
=
K22
1-a cos 8TP 1-a00ss + Ol1
K2
If we can take
w = =O(A²).
K2
ki = O(A))
V
K2
then <3/2pp--owwe - 87 0(1) and
(t++(), - (Tu). =00+))00(( ( Iacoss
2 2001090 I
1
Hence,
(F+ 2 (F+ x+) - x+)1
22 A2p i-neaa = ? (App-~aaan -
VtE [Tin, Thx A T..T'.
Step II. Bounding the term (t).
The proof can be completed by the method analogous to that used in Step I, and we omit it. The result is
(F+ (f+
(F+ (Ti),,.. + IF (t), x+) - (F+ (Tu))x=)).
0222p - St (A²p -I-
VI E [TiI, Tix A THTT).
Lemma E.4 (The end of Phase Transition).
If we choose K1, R2 s. (11) and v = 0 (A+) (3), then it holds that
(SI) (Time).
TP==TPT PT+ = TiI +0
(V
(V
K1
(1+0
(VeinS)
Ti:
122
A2
(S2) (Prediction).
e e-+(hH" A ( ()--cco))))
ef (ITT) = 0 p
(T-(T
coS A 0 A2p
1+p
1 1+p
pe (TTTT
eL-(TTT)
COS A
1 = 0 A22 T-
1+p
(S3) (Activation patterns).
(wneTTiP ), xx44) > 0, (wax ( )= =0, Vk Kct
)
(wx(TTiT) PT ), = 0, (w PT )) > 0, VK K.
72

---

Proof of Lemma E.4. Step I. Time Estimate. Let k E K.
Recalling the definition of TPPT= in Lemma E.I, Lemma E.1 (S2)(P0) also gives us
T max k
11,k
From Lemma D.8 (S2), know that there exists absolute constant Q3 0, 0 S
(by (Ti); a=) S Q3
/kisa And we Q2 > 0 be absolute constant Q2 in Lemma E.3.
v'm
First, we choose the time
3Q3
f6
Tix Tn +
Q2
R2
cox
then we choose K1, s.I.
K2 = O(),
K1
o (A4).
It can ensure
2
Trxx A TH
TTi)
Ti P
0.00 0
A
122
K1
O(A²),
K2
2
R2
O(A7).
Then according to Lemma E.3, it follows that
(f+ Q2 A2p
VL [TH, TiE A Tax)-
2
Now consider the dynamics for TH. Recalling lemma E.I, we have
TPT Tix).
l" /dbb(s)
(b PT Tnx),
(TT()
x+ ds
In ds
TPT-AT ATER
(bx (TiI),
x
R2
(F+()),
m
VKIK2
Q2
<Qa
A p
TPPT A Trix - -Tin)
Vm
2
<Q3
VKIK2
Q2
22p
T- (TIIIx TTi) Q2
3Q3
K1
p1-acon
Vm
2
R2
We claim TPT+ 11,k
Ti <
2Qa
M p T-onna If otherwise, then
Q247
VRINZ
(bu(TH Tix), Q3
Q3
0.
Vm
mm
From the definition THA we know TPT < TPT- A Tixx which leads to a contradiction. therefore, have proved that for any k E K4p
TPT Tix = TiL
2Q3 Ki
PT < Tú
Q
With the help of Lemma E.1 (S2)(PO), we obtain
T A Tix = PT,
7PPT PT+ max
PTx 11,
< Tn +
2Q3
K
kek.
A₂
73

---

Recalling Lemma E.3, (F)(), > 0 and (F (t), x-) < 0 hold for any t [Tn. H A A
[Ziz, TH ". From the definitions of TH and T1 (26) we obtain
T T1
In conclusion, have proved:
- TI +
(v
Kil p
Lemma D.6
1
(Vmin) Th-
K2
Step II. Prediction Estimate. Step I gives us the result:
(V
87 = TH Ti 0
K22 A
Recalling the proof Lemma E.2, we know
C + Che (7
<e1-(()-S-(Tn) 150,
1 + Coet- (71)8
-C287 Sel (Ta) -1000-40-11-0 -10
where
Co θ
C1 O (K2V/112)) C2 θ
kyp
2
1-a com
p
Then straightforward calculation gives us:
0 0 ed-(0)-1-(m)) 1 1-
Kg
-
K2
2
K1
0
R2
2
Ki
K2
N2
P2
0 > e (Tu) (4 (TT
-1=
0
N22
2
M1
A
K2
With the help of Lemma D.8, we obtain the prediction estimate the end of Phase III:
e (1 = (+) (A -0 (c~A/(u)) θ
f -f = θ (ef-(Ti))= = =
I-a COR
Moreover,
pe (T+
cf-(TTTT)
pe (T-(T)
(Ti))
cos A
1+p cos A
1+p
1+p
1 1+p
14
df A
pe f+(Tn)
(2ir) cos
1+p
1+p
+
1+p p
7+ (21)) (2m)
1 1+p
e (Pi1) cos A 1+p
1+p
1-n non
K2
A
+
I-o FOR
Ki
K2
0
"In3=0(A")
0 A3p
K2
A
which means
pe fi (T
ef (TP
cos A = (A'2
(A3p-1-occmd 1
1+p
1+p
In the same way, we can obtain
pe f+ (TFT)
ff
COS A
- (A'p
+ p
1
74

---

Step III. Activation Patterns.
Recall proofs in Step we know that
wn PT ), = 0, Ak: E KC+
Moreover, from the dynamics in Lemma E.1 (S1) and (P2) we obtain:
(wx xx) > 0, AA k+: Ww x, = 0, (w, (T x > 0. vk EC
Proof of Theorem 4.6.
Theorem 4.6 (S1) has been proven in Lemma E.4 (S1), and Theorem 4.6 (S2) has been proven in Lemma E.4 (S3).
E.2
Optimization Dynamics after Phase Transition
After Phase Transition (L > TT we study the dynamics before the patterns of living neurons change again. Specifically, we define the following hitting time
t T PT 3k E K++ UK_ sgnn (f) + sgn (Ti) or sgng (t) + sgn (Ti)
Tmm == inf
inf
1 T PT 3K E K+, s.t. (wa (1), x < 0 or (wa (1), x-) + 0;
(28)
or 3k K_, s.t. (t), x+) * 0 or (w) (t). < 0)
and we call / (TFTT, Tim) "L-Phase III" Moreover, call t [Tn, Ti) "Phase III", i... "Phase Transition" "L-Phase III".
In order analyze the dynamics of neurons and vector fields, we introduce the auxiliary hitting time:
Ti = Tin A inf {t THTT (F+
S 0 or (f),
(29)
where F+ (t) 1 1+p
P -- 1400 x+ 1+p x0)
We call t E (IP (in) "L-Phse -II
Due to the almost simplest activation patterns, this phase is easier analyze, and only need to estimate the time and size of the changes in the vector field. Nevertheless, our challenge is to prove that all living negative neurons simultaneously change their activation patterns Tin which also implies that Tin Tim-
Lemma E.S (Dynamics of activate neurons during L-Phase III*), In L-Phase III* (t [THT, Tim),, have the following dynamics for each neuron k K.K. U K.+
(SI). For negative neuron & E K_,, we have:
wx(t) E M n n=,
dbx(1) (1)
(a__ (x- (r--2x x4 cos A).
dt Vm(1 + p)
(S2) For positive neuron & E K.,, we have:
wx((1) E MI n MM
db&(!)
Kope Kope--110 (1)
Vm((1 +p) 24 - x- Cos A).
dt
75

---

Proof of Lemma E.5.
From the definition of Tim- we know that (t), t E [TPTT Tn.) Moreover, Lemma E.4 ensures that for h E K+, wa (T M M for E K_ wy (TH E M MM.. Hence, this lemma can be proved in the same way as shown in the proof of Lemma E.1 (SI) and (S2)(2).. We do not repeat it here.
and (F+ 0 hold for any
Lemma E.6 (Time and prediction estimate at the end of L-Phase III*), (SI) (Time).
p pi-acon cor
Ti T O
= =1+ TH 01+ Tu:
R2
(S2) (Prediction).
e (Tiii = 0 ( T-acoa
ef (Tinii)) =0
T-o
pe -f+(En)
ef-(Tin)
008 A 0,
1+p
1 1+p
pe (+(THT)
e
CO8 A
- A
+ p
1 1+ p
Proof of Lemma E.6.
Step I. Explicit Solution to f+ (t) and ft)...
For any E [TPT. Tim), we have:
f+())
K2
Σ by (t)a++
mm
kEK.
f-)
K2
b (t)x=
Vm
kEK-
Let us consider the dynamics of (1) and f-)(). With the help of Lemma E.5, these two dynamics are nearly independent:
(f+()) = K2
Σ
Kape (1(
x=cos 1).
.x+) 1.2.) x2m ponnpsinn A e e11((1)
a++ x- cos
dt
mm
Vm((1 + p)
m + p)
KE
(t)
R2
f-)
a- x. Cos 2). x0
k sin? 2 A f-(1). m(1 p)
dt
m
/m(1 +p)
kEK_
Their solutions are:
é f+(77)
ff(()
1 e (TPT) 12mppsin A (t TI"T
m(1+p)
(T
e-
1 + pf (T 3am sin A (t T m(1+p)
Step II. Time Estimate of Tim-
For simplicity, denote G <3 m a psin and G_ ml)
K sin? A
m (l+pp)
First, we consider the evolution of the vector field (F+ x));
pe- (t)
(4)
(F+()),
COS A
1+p
1 p
76

---

pe fTTT cos A
ef (TTT))
1+D 1+e0++(1)) (T
GG (
T 1+e/-(0i G- (t - T
(pe -+(TT1")) cos A - ef-(1 )) + eel ef -4- (pp cos A - Gt) - T
p1+ + e (11 G+ (1 - (1 + (T 10-0116-11 GG
))
(1 ()+ (F+ (TPP)) x-) + cf (Ti) (T (pG cos A G+)(t - T
O.
(1+p)(L e n G TH e (T G- ))
Hence, the hitting time Tim can be converted to the following Til:
Tü Ti = Tiu A inf { t> THT (F+(1), $0].
Then we consider (F (F)(t),
(F+(t).0+)+ pe f+( ef
cos A
1 +
1 +
1
(TT)
el-( 00s A
1+P P 1+ e f1 (T G+(t - TPTT) 1 1 (TH G- - -
(pe -+(( ( cos A) + e- (TT - /+ (T ( (pG - G+ cos A) -t-
p1+ + (+ Gt - [1 + ( G - ))
(1 (F+ )x e-
(pG G4 cos
C08 A) - T
(1 + (1 + e 1- G+ (1- TH e - "G -T
From Lemma E.4, we know
De 1+(0) ef-(()
(1 +1+p) F+ (TPT) ) x.) = (1+
C08 A = = A2p (0(A²) 1+p 1
CoR
ef )- = (f-(Tiyx)$+ (Tiaa)) =
1to 4
pG_ G+ cos A = K2psin sin? 2 "A (m- m+ cos A)
- (kİ27)
1+p p
m
These imply the hitting time:
- TP +
A p
= TT +0
pr-a
14a
2
R2
Step III. Prediction estimate. From the explicit solution in Step I and the time estimate in Step II, it is easy to verify
e --
(TT))
① (p
I
1te (TTTT 8mm psin A m(1+p)
(Tin TPP
el-(TTT)
ef (Tir)
I
1 el (TFT) p3m sin" m(I+p)
(Tii THTT
Recalling the calculation in Step II, we have:
pc (Ti
ef (Tr))
F_ F_(Tim), x4)
cos A = 0.
1 1+9 p
p
(F+(TT)) x-)- pe pe-ft (fi(aa))
f-(rin)
COS A
1
1 + p
77

---

(1+p) F- PTT) x e (Th (T
G+) - - )
cos A
(1 + (1+p)(1 + t -- G+ - () el- G G- - -)
A2p cor 2
a car 1-0
) - - (520 T-n
(
Lemma E.7 (Hitting time relationship). If we define the following hitting time:
TW inf {t > TP vk K_,, (w)
then holds that Tm Ti TW
Proof of Lemma E.7.
We define the following hitting time:
Tii inf { TiPT (F (t), s 50};
TN inf [ TH 3k K_, s.t. (w)(t), xx) > 0}.
T inf (1> TH Ak E KK_, (wr (1),+)) > 0},
From the proof in Lemma E.4, we know (F+ (Ti(Ti x.) < O. From the continuity of (F+ ++),, xt we know that there exists Ti > 0, such that (F + (1), x.) ) < 0 holds for any / E (Ti. Ti + Then in the same way as the proof of Lemma E.5 (S2), we know that for & E K., w(t) E M n M for any E [Tin Ti + TT).
Recalling that for any K_,, (bu(Tin),, x-> > 0, from the continuity, we know that there exists holds for any E [Tn. Til + 72).
x-) 72 0 such that (bx xt).
Hence, we have: Ti = TH A TN = inf {t TPT: (1+ S or 3k E E._, s.t. (we (w,, + O0.
is obvious that TN 2 THi A TM = Tin- Now we prove TN = Tin-
If assume TN Ti strictly, then the dynamics about (1) and (4) in the proof (Step I) of Lemma E.6 still hold for any E Tii TM) Using the same calculate about (F+ (t), in the proof (Step II, III) of Lemma E.6,
obtain: (t), x4) 0, t E [Tin TNY
Then we consider the vector field around the manifold M n M fort E [Ti. T... In the same way as the proof of Lemma E.1 (S1), we can prove that the two-side projections onto x_ (the normal to the surface Mt O M²) satisfies f (t. w)) fy (t, w) > 0 for any E (Tin Th + T)), which satisfies (Case II) in Definition H.1. This implies that wx (t) enter the manifold M ie.. (wx(( (t), x))) > 0 for any t E [Ti. TN which is contradict to the definition of TN Hence, have proved
T TN TH Tm-
Noticing that the change of activation patterns of sgn (t) (k E K__) is due to the change of the vector field (F), x44), is easy to verify that TFF TN A TEE Then we have TN T. Th A T Tin
Moreover, noticing that Tim S TN and Tin I Tm, we obtain Tm = Ti TN = -TF
Lastly, noticing that all living negative neurons (k E IC_. belong to M². n nM at time Tim As discussed above, for each living negative neuron & K_,, the vector field near by (Tm) is the same, with f > 0 and + 0 in Definition H.1 (Case II). Hence, each living positive neuron wa leaves from M and enter M instantly at Tiu, which means T.W TN
Hence, we have proved Ti Ti
TW = TN = -T
Proof of Theorem 4.7. Combining Lemma E.6 and E.7, we obtain Tiu +1+ ((A3)) Tn.
78

---

Proofs of Optimization Dynamics in Phase IV
Proof of Theorem 4.8.
From Lemma E.7, know that all living negative neuron i A_ simultaneously change their patterns on 2+ at TmI: lim sgag (t) = 0, lim sgag (t) = Moreover, from our proof of t-Ti
t-
Lemma 7.7, we know that other activation patterns remain unchanged at TıII-
this phase, we study the dynamics before activation patterns change again after the phase transition in Theorem 4.8. We define the hitting time:
Tiy inf Tm 3K KC+ U. (t) + lim sgnū (s) sgn, (t) lim
sgn; (s)),
s-fin
s-Tii
and we call E (Tm,, Tiv) Phase IV. In order to analyze the dynamics of neurons and vector fields, we introduce the auxiliary hitting time:
Tiv = inf {t> Tm : (F+
> O, or (f+ 0).
(30)
p -111(0) 1 e xx
where (1) - +
1+p
and we call E (Ti..Ty) Phase IV*
First, we will provide meticulous prior estimatiins for 2d ODEs (t) and f- (l), similar to Phase II, which can imply Tïv +oc. Additionally, we can prove Tiv Tiv Lastly, with the help of our fine-grat fine-grained analysis for the 2D dynamics and the results in (Lyu and Li. 2019; Ji and Telgarsky, 2020), we can determine the unique convergent direction from numerous KKT directions.
F1 Non-asymptotic Analysis of Optimization Dynamics in Phase IV*
Lemma F.1 (Dynamics of activate neurons in Phase IV*).
In Phase IV* (t E (Tı.. ]iv)), we have the following dynamics for each neuron k E K_ U U.+.
(SI). For negative neuron k E K_,, we have:
(+( E MM n- dbb dt mm
K2 (+)
K2
P
c (+(())
1 e1-(1) x
x4
mm 1+p
1 1 +
(S2) For positive neuron l E K4,, we have:
wp(t) M M=, dbb(t)
Kope f+(1) (+(()
x_ cos D).
x4
/m(1+ + p)
Proof of Lemma F.I. Using the definition of Tiv, this lemma can be proved the same way as shown in the proof of Lemma D.1, E.1 and E.5.
The next lemma gives the first-order dynamics of (t) and f-(t)-
Lemma F2 (First-order Dynamics of predictions in Phase IV*). In Phase IV (Tm 5 t t 1Tv), we have the following dynamics for f+()) and f-(t):
(t)
K2 m
2 mh pe (t)
sin"
A
K22
m_
pe (t)
ef (t) cos A
dt
1+P
m
1 1 p
df-(t)
k2 m_
pe (t)
ef- (t) COS
dt
m
1 +
1
79

---

Proof of Lemma F.2. From the definition Tiv. for any Tin St & Tiv. we have
f+(t)= = Σ
R2
bR (t)x+
R2
b& (t)
Vm
Vm
kER
REK.
f-(1) = Σ
R2
b% (t)x...
Vm
kER_
With the help of Lemma F.I, we have the dynamics of predictions:
df+(t)
Σ
R2
(bx
Σ
K2
dbx(t)
x
dt
Vm
dt
Vm
dt
kEK+
REK-
x3
Σ
P
E
(f+
(1 cos A)
12
COS
(+)
P
e e-f+1))
m
1+p
1 +
1 + p
kEK.
REK.
pe (+(())
m+
2
p
e
(+(0
sin?
m-
R2
COs
6 f-(t))
m
1 1+p
1+p
1 1+p
df-(t)
Σ
K2
dbx(t)
K2
Σ
P
[+00)
C08 A
ef
dt
Vm.
dt
m
1
1
kEK_
kEK_
R22
2
c
(f((1)
cos A
1
cl-
m
1 1+p
1
Following the proof in Phase II, focus the dynamics about predictions. Due the specificity of the first-order dynamics, the following lemma gives an second-order autonomous dynamics of predictions.
Lemma F.3 (Second-order Autonomous Dynamics of predictions in Phase IV*).
If we consider the following two variables:
I(l)
Kig m
1+p
E (+)))
[(t)
= 22 1+p
e())))
then the following autonomous dynamics u()) and V(t) hold in Phase IV (Tin Sts Tiv):
aztt) dt
[()) cos A I2(() (1 m+ sin A).
dT(()) I(t)J(tt cos A J2()).
Proof of Lemma F.3. With the help of the first-order dynamics Lemma F.2, the proof straight-forward.
Lemma F.3 enlighten us that only need to study the dynamics of I(t) and J(t) to study the dynamics in Phase IV* where Z(t), (t) satisfies the following autonomous dynamics:
dI(()) de
I(t)J(tt) cos - (t) (1+ m sin? A)
12 Tmu
d
I(I)J(I) A J2()),
(31)
I(Tim)
=m² m-
ltp 1-(m))
(Tm) N2 m Itp
el (Tin),
The next lemma studies the dynamics (31) for any E [Ti, +00).
80

---

Lemma F,4 (Fine aeme-grained analysis of the dynamics (31)). For the dynamics (31), we have the following results:
(S1). Initialization.
I(Tm) = A [KGp ( [(Tm) =0 (n33 Fuic
I(Tm)) ((Tmn) cos A 0, I(Tin) cos [(TTn) = - (n332 can
(S2). Fine-grained two-side bound for (t))
1 COS A
I(t) J(1)
< A,
VI E +oc).
+ cos
+ mLL sin
(S3). The limit (t)
I(t)
1 + cos A
lim t-
J(t)
1 + cos A
1 sin A
(S4). Tight estimate of I(t) and J
I(t)= =
VI E +o0);
p pI-o
+ - Tin) (Tnn-Tin)
1
[(t) =
Vt E +oo).
p bor
+ at - (Tm)
Proof of Lemma F.4. For simplicity, in this proof, we denote
m+ sin A.
Step I. Preparation. Recalling Lemma E.6, we have:
I(Tin) = k22p (
[(Tim) = (n2pp 1-0000 -1-00on
I(Tm) - (Tiu)) cos = 0, I(Tm)) cos J(Tm)) = (13A22
Step II. A rough estimate I(t) and J(t). In this step, aim to prove:
J(1) I(t) 0, I(t) [() s I(Tm)) (Tmm), Vt (Tm,
First, from the definition of (t)) and J (f), we have I(t) and ((t) > 0.
Then we consider the dynamics of I(t) + [t).. From
d
[(()+ +()++())) 2I((( A (2() (c) - J2(() = (I(t) (I(t) cos A cos () - I2( (1 + cOs A) 0,
dt
have
I(t) + J(1) < I(Tm)) + ((Tm), 21 Tm-
Then consider the dynamics of J(t) I(t). We define the hitting time
TJ-I == inf { 2 Tim J(t) S I(t)).
From Step I, we know ((Tm) I(Tm)) = (1 cos (T)(Tm) > 0. From the continuity, Tイ- exists and T--I Till.
81

---

For any t TT-1), we have J(t) I(t) > 0 and
()()) - --0--)))--70000000000-0000001110 > >- + -00)))))0) (00
We consider the auxiliary ODE: _ - I((m)))()))) where P(Tin) = [(Tin)
I(Tm)) > 0. From the Comparison Principle of ODEs, we have:
[(t) - I() 2 P(t) = (J(Tm) I(Tin)) exp ( (J(Tm) I(T)) > >0, A2 (T))
From the definition of Ty-z, we have proved
T--I= +00; J(t)>I(t) Vt E [Tm. +oo).
Step III. A rough two-side bound for (tt)/((t).
In Step II, we have given a rough upper bound for I(1)/((1): I(1/((I 1, V Tm. And we want derive lower bound for I(I)/(() in this step. We aim prove:
I(t)/J(t) 1 + cos A
Vt [Tu,
cos Ae
First, we define the hitting time:
t inf tt Tm I(t) <
1 cos A + [(1}.
1 + cos A
From Step we know
+ cos A
1 ++ cos A
I(Tm) 1 cos +E
[(Tm) >
cos A
((Tm)
1+ cos A +
sin² A Cos A m_
m+
Cos
1) sin? A
T [Tmm)
0.977
[(Tm)
+ 0O8 A +
C0s A +e
0.980
1) sin?
0.977
I(Tmm) > 0.
+ cos A +
From the continuity, T// exists and I/J > Til
For any t [Tuı, ) we have I(t)
1+00s A+c A+o J(t) and
1+cos A
d
1 cos A
I(l)
1 cOs A J(I)
dt
-I(I)((I) cos A (1
1 cos A +2) ) - (1++) + 1 cos
1 cOs A
1+ cos A + J2(1)
1 cos A
I(1)
cos + [(t)
(1++)I(()+3))
I(t]) 1 cos A
(1 +c)
cos + [()) (I(t) + (I()++ J(t))
cos cos A [(l)) 1 cos
(1 +e) (I(Tm) ((mm))
We consider the auxiliary ODE: d Q(1) -(1 + (T((m)) + ((Tm)) where Q(Tin) 14o0s A
I(Ti)) I+cos A+c I (Tim) > 0. From the Comparison Principle of ODEs, we have:
I(t)= 1 cos A
J(t) 2 Q(t)
cos A +
82

---

I(((Tu) 1 + cos A
1 cos + J (Tmi) exp (- + ((Tm))(t -hm))TTm)))))))) > 0, Vt E (Tm.
From the definition of Tz- have proved
T +00;
1 cos A
[tt) >
vt E [Tims +o0).
1 COs A A+é'
Hence, obtain the two-side bound for I(t)/J(t):
1 cos A
I(t)
<1,
E [Tu,, +oo).
1+ COS A te
[(]
Step IV. I(t) cos A J(t) and I(t) [t) cos A are both negative.
The estimate on I(t) cos A
[t) is straight-forward:
I(t) cos A (t) I(t) cos A I(t) < O.
As for I(t) - (1) cos A, we will actually prove a tighter upper bound:
I(t)
cos
J(t)
We need do finer analysis using the specific dynamics (31). First, we define the following hitting time:
Define the following hitting time
Tis inf { { Ti T:: I(() [(t cos A 2 0).
From I(Tin)- (Tim) cos A = 0, at (I(Tm)) J (Tin) cos A) < 0 and the continuity, we know Ti/s exists and Ti/3 Till.
d
Recalling I(1) cos A
(1) < 0, we have
d [() = [(t) (I(t) cos A [(t)) < 0,
Vt > Tim.
So we can consider the following dynamics for E [Till, T/
dj = IJ
dI
cos cos A I2 +c)
f cos A -(Z) (1 +c)
IJ cos A J2
y cos 1
we define Z(t) = I(t) J(t)
then we have dI ZdJ + Jdz.
The dynamics above can transformed to:
J J1z cos A dJ
(1( +6) - 2(1 + cos A) 22 + cos +
cos A -
Z cos A -
Recalling the result in Step III, we have (1 + cos A) (1 cos A + <) z() t 2 Tim. So the dynamics is equal to:
0 holds for any
dJ
Z cos A
dz
J
2(1 + cos A)
2 + 008 A +
1
sin 2 A +c
dZ.
1 cos A
1 cos A
2(1 + cos A +
Integrating this equation from Tim to E [Tm,, TH TH, have:
J(L)
I A log 2(1)
1
log
((Tin)
((Tin)
sin A
- (1 A (1 (1+ A +e)Z(()
cos A)
log
(1 + cos A + (1 + cos A)
(11 cos + c) (1 + cos A)
(32)
83

---

If we assume T/jJ < +00, the continuity gives us
lim Z(t)
lim I(t)/[(t) = A A I(m 2(Tm).
(-12//3
Then letting
+
~u 'I/J in (32), we have
[(t)
lim
log
0 =
115
[(Tim)
which means - -
But on the other hand, we have:
[(T2)o) I(Tm) ( (I())[(I) (0s (2))dd
Imm
(22 (()(((()) cos J(1))d
-I(Tmm +
TTu
1213 J(II(()) < ((m)),
<I(Tim) + (cos A 1)
Tm
which leads contradiction. Hence, have proved
Tz/o +00;
- cos A < 0, Vt E [Tmm
Moreover, obtain sharper two-side bound for I(t)/J(t):
cos <
I(I) < cos cos vt E [Tm. [t))
(33)
COs +e
Step V. Tight bound for I(t) and J(t).
In this step, we aim to give tight bound for I(t) + J().. With the help of the two-side bound (33),
we have
d
- -(((t) - I()))² cos - - -
(I()) + J()) = 2I( cos A
dt
A) c0 A) (I(t) {
2 ([tt)+
cos A) (J²(t+
2
d
I(t) [[()) + J(1) = 2I()) COs (1 - A)
dt
(I(I) - -(()²² cos A C1
(1 1 cos
) j²(t) - cOS (1) 11-1101111111111
- -1(0)
+ A
2 m+ A (I(t)+ + > 24 (I(t) + 2
> (1 (1+ cos A) + >
For the first inequality. we consider the auxiliary ODE: d P(t) = where P(Tin)
I(Ti)) + J (Tin) > 0. From the Comparison Principle of ODEs, we have:
1
I(t) + J(t S P(t)
A1 2 Tm-
(t
(t - Tin)
377m)++(mmm
In the same way, we can obtain the lower bound:
I(t) + J(t)
Vt 2 Tm.
212 - Ti))
1(Tm)+J(mm)
84

---

Recalling Step I, we have I(7m))+((mm)
(
| /n3
Hence, we obtain the tight bound:
I(t) +(t)
Vt [Tim +00).
I- cord
+ Tuu)
Taking (33) into the equation above, we have:
1
I(1) =
1I E (fim++0))
mix Don
A2 Tin)
1
J(t) =
V E [Tm,, +oo).
a
+ A1 A
Tin)
Step VI. The limit of (tt)
By Step and the proof Step IV, we know lim J(1) = 0 and J() < holds for any 1> Tin- t-000
Then for any e' > 0, there exists T > Ti such that
T(t)
1000
log
log (1000 A T
((Tm))
A
Taking it into (32), we obtain that for any t T"
0 < (1 + cos A e() (1 + cos A) <
By the definition of limit, we get
I(t) cos A J(I)
1 + cos A
lim
1+ Cos
1
C0S A +
sin 2 A
Lemma F.5 (Time and prediction estimate). (S1). For any & E (Tim,+o0
pe [+(1 fe00+ =
1
ee-(00 =
1
p pl-acors + +n2 Tim)
pi-acom 122A Tim)
C(O(t)) =
p x2 Tim)
(S2). For any / E (Tmm, to0),
+ cos A
< pe (f+())+--(0) < cos A.
1 cos A + mi sin
Moreover, pe me-(+((mm++--(h))) = cos and lim pe -1+(000)))) t-020
1+c0s A+ sin
(S3). For any t (Tin, +oo),
(b) x4) > 0, (bx = 0, KE K+: (tx x+) > (bx(1), x 0, k E K...
(S4) (Time).
Tiv = Tiv +00.
85

---

Proof of Lemma F.5.
Notice the relationships: pe-f-(t) =m 14p'
m I(t) ef n² m- 3(0)
1tp and pe-(f-(0+f-(1)
[t)). Then Lemma F.4 implies that Tīv +oc. Recalling the dynamics in Lemma F.1, then
lemma (S3)(S4) hold. Then using Lemma F.4 again, we obtain (S1)(S2).
Proof of Theorem 4.9.
Theorem 4.9 (S1), (S2), and (S3) are obtained in Lemma F.5 (S4), (S3), and (S1), respectively.
F.2 Asymptotic Directional Convergence
In this section, we will study the final convergence direction in our setting. mainly depends on our prior fine-graing tne-grained analysis of the training dynamics in Phase IV and the following result about the final convergence direction the end of training.
Lemma F.6. Let f(; 0) be homogeneous neural network parameterized by 0. Consider minimizing
the exponential loss over a binary classification dataset {(2;. [==) (|æzil2 S 1, E (+1}) using
Gradient Flow. Assume that there exists time to such that ((0(t))) < Then,
(I) (Paraphrased from (Lyu and Li, 2019; Ji and Telgarsky, 2020)). (() converges in direction to KKT point (Definition G.3) of the following maximum margin problem:
min 2 1101
8.1. fi (3 0) 1
(II) (Lyu and Li, 2019; Ji and Telgarsky, 2020)). (0()))l2 + os and L(O(t)) +
(III) (Ji and Telgarsky (2020)). - (e)(())) and (tt) converge to the same direction, meaning the angle between (tt) and ())((t)) converges to O.
Lemma F.7 (Final Convergence Direction). The limit lim t
0002 exists, and denoted by =
(b,
gmd-1, then it satisfies
b 0, Vk KKKKKKK
b =C x cos A).
Vk K+;
by =c ((+
m+ sin? A
a_ x--x+) Y
m_ + cos A)
where C' > 0 is a scaling constant such that 0
= 1. Moreover, f(e+; -f(x=;0) > 0.
Proof of Lemma F.7.
Let 0
(b, ... b,
gmn-1 be the limits point of eto) [e())
:t 2 to From Lemma F.6 (I),
we know that there exists a scaling factor a > 0 such that o0 satisfies KKT conditions (Definition G.3) of the maximum maximum-margin margin problem
1
min
0
2
2
(34)
s.t. f(x 0) 2 f(=_;0) S -1
For simplicity, we denote 0" = a0, where
= (b) b T)T.
Moreover, let X the corresponding Lagrange multipliers (with respect 0*) Definition G.3.
Step I. The rough direction of each neuron.
Recalling the training dynamics about the dead neurons in Theorem 4.1 (S3).
bx(t) (Ti), (b)( x4) < 0, (bx(t), 0, A e [m/2] K4;
86

---

(t) (Ti, (t),
- 0, (b,(t), x-) 2 00, KE [m] - [m/2] K_
Noticing Lemma F.6 (II) or Lemma F.5 (S1), [t)l] + 20,
b = 0, vk $ K+ U.K.
Then we only need to focus on 0% for K. E K4 UKK
Recalling in Lemma F.5 (S3), for any 1 Tiv,
(bx(t), x4) > 0, (t), x-) ) 0, k E K+;
(bx()), x+) +) > 0, (1) > 0, k E K.
then we have
(b) x.) 2 0, =-) 0, k kEK+;
(b) x+) 2 0, xb. 0, k K.
Moreover,
f(x4;0")= = /m
122
((b),
Σ ((bb,,+)))
k
kE
f(x_;0")
K2
((bg, x-))
Σ
((b x.
K2
Σ a ((bb,
mm
kEK
kEK
REK
Step Determine the direction of the neurons E K++
Since 0" a possible point, f(x+; 0*) 2 which gives us
o((bj, x+)) 2 vm
Σ
>
K2
kEK
Hence, there exists 1 E K+ s.t. (b%, x+) > 0 strictly.
Then study the neuron li KC+ (h2 k1). Lemma F.1 and Lemma F.5 (S3) give that
Kope (+(1) (1)))
(bx, (t), x1) = (Tv), Tiv /m(1 + p)
sin? Adt
f' Kope kepe-f+(0 f+(()
sin? Adl ( (bbs (Tiv), (bxz (Tiv), 2x
(Tvv,
Tiv vm(1 + p)
(1), + (bs; (Tiv), x+) (bkg (iv),æ+))
Multiplying the above formula by c/ [10(t) lg and taking go to infinity, we obtain
(b x4) (bi x+) O.
Due to the arbitrariness of k2, we know
b + 0,
(bi, x4) > 0. x-), =0 Wh: KC+.
Then we can write the KKT condition about the gradient of b (k E K.+) of Problem (34):
K2 x4
Kg
0 E b X
X
0
(0)x_
mm
It is clear that by E span +. x x- Then combining two formulations above, obtain:
6i = 14 (x+ x= cos Vk E K4.
Step III. Determine the direction of the neurons l E K.
87

---

Since 0 is possible point, ( = -1, which gives
Σ
vm o(1b,, x--) z
> 0.
K2
REK
Hence, there exists 1y E K__, s.t. (b x-) > 0 strictly.
Then we study the neuron hi2 E KC (1/2 & k1). Lemma E.1 and Lemma F.5 (S3) give use that
(be, (t), x-) (bar (Tiv), + l 122
(1 et-(0)
1 1+p c c- cos ) dt
Jwv vm
(1+
=bs,, (Tiv), . )- + f
vm 1 el
K2
P -110 cos 2 ) de + ( (bis, (Tiv), (bxa (Tiv),
1+p
= (bb, (1), x-) + (bs, (Tiv), (bkg (Tiv), ax-)
Multiplying the above formula by c/ [10(t)) la and taking go to infinity, we obtain
(b x-) = (bra x -=>00 O.
Due to the arbitrariness of l2, know
bj + O, x-) > O, x4) 20, 0,
Vk K...
The next difficulty in this step is to determine whether (b ..) can be O. To prove this, will use our fine-grained analysis of training dynamics (Lemma F.5) and Lemma F.6 (III).
Let k K__. Recalling the dynamics of (t) in Lemma F.1, we know AC(e(t))
K2
P
-f((
1
(xx
Vm 1+p e
x 1
ab
R2 e1-
-pe (0-(((())+$-000)
x -
mm 1 + p
Recalling Lemma Lemma F.5 (S2), lim pe (f-(1)+--1))
1-cas 1 At " sin?
Then using Lemma
1-000
F.6 (III), there exists > 0, s.t.
+ cos A
bj = 61
x
1 + cos A
mi sin A
Hence, we have proved
(b x > 0, Vk K.
Then writing the KKT condition about the gradient of by of Problem (34):
Rig x-
bj
x
x_,
Vk E K...
m
m
Combining the two equations about bi. we obatin
122
1 cos
6 = x
sin? A 2+
vkEK.
A
mi
m
X
+ COS
x
1
sin? A
m
summary, we have proved the final convergence direction 0 0= =(6b; (b] ,T)) bT) gmd-1 satisfies
by =0 Yk K. UK=;
by =C x4 - x_ cos d). wk K44
88

---

by =c ((++
m. sin2 A
a -x+)
Ak K_:
m- + cos A)
where C
is scaling constant such that [0|| 1.
Moreover, a Atraight-fowwan calculation gives us that
(a+4; 0) = -f( > 0.
Proof of Theorem 4.10. Lemma F.7 implies Theorem 4.10 directly.
Proof of Theorem 4.11.
From Lemma F.7, the final convergence direction 0 - (b) ,r)) E gmd-1 satisfies
P 0, Wk UK-;
6 =C 2 - x cos A).
cos
Ak Kti
by C (1 1
m+ sin A
x -2++ Ak VKEK-
m_ cos A)
where C' is a scaling constant such that
00 and f+(0) ff- > 0.
It is easy to verify that There exists scaling factor C1 > 0 such that f+ (0) = -f = 1, where
CjO. For simplicity. we denote Q = CC1, then (b 6 T E Rmdd satisfies
T
6 =0, Ak & K- UK=;
6 =Q a++ x- cos A).
Ak E KC+;
b -Q
((1+ m- + cos A)
m4 sin?
Vk E K_; x x- -2+). )x-xx
S+ (0) 1
Therefore, 1 is a feasible point of Problem (34). Moreover, from
- -1
Σ
(b, xb)
Vm
KE
12
(0) (0((1
m4 sin" A
x+
mm
m_ + cos A)
162
1 A + m4 sin? A
Q
m_
m
m_(1 + cos A)
62
sin? 2 A
Q
m1
cos A) + m 1 + cos A
/m
we have
18g m_ (1 A) m
Q
sin?
m
T+ros
For any 2 0, now we consider another solution O(c) near 0: ((b)))(b]()))) (c), (()) where
(c(() =0, Ak K.4 UK=;
(x()) =Q x+ - x_ cos A) Qc (x( Qc(xx+ - x_ cos 2). Ak E EKi;
_e_cos
x_cos_]
89

---

bc(c) -Q ((++ m. sin² A
m_ (1 + cos A) 2- -0--2,, x44 + Qe Qc(z++ a- cos A). 4k K.
and it holds that ((0) 0. Moreover, it is easy verify that ((e) is also feasible point of Problem (34).
f-(0(c)) =f- -1;
(+(ec) (f+ = 1.
Then we compare the norm of ((e) and 0(0).
| - (o(2++ cos A Qe C.+ (0(
a- cos cooss))
-++
m_ (Q (0((1+ (1+
m4 sin A
-/--=+) + +EE(x=
x- 1=--1) -x+)
x- cos 4))
m_ (1 + cos A)
At c = 0, we can calculate that
d
((e)
2m+ Q
k==0
1
x- co8 All² + +m_ ((1+ m4 sin A
2- 24. x+ 20 cos 2))
-M
||0.
m
m. (1 + A)
sin² A
+ cos
x x- 10--(1
11
[ 2+ x A
m+
I cos
m4
Denote m
a (
sin A
A
T_ (1+0)x4.2, 24 x- cos A
+ cos
sin?
a+ 1+ COS A
+ cos
COS A (1+a)
sin A
+ cos A
COS A + (1 +a) cos A
1+ A
(1 a.)
Then combining the continuity of a| holds:
there exists 8 0 such that the following inequality
|())||
Ve E (0,8).
Hence, we have proved that 0 is not local optimal direction of the max-margin problem (34),
90

---

G Clarke Subdifferential and KKT Conditions for Non-smooth Optimization
Definition G.1 (Clarke's Subdifferential (Clarke al., 2008)). For locally Lipschitz function :: Ω - R, the Clarke's s subdifferential at 0 E Ω is the convex set
8 ((()) == conv lim VL(),) : lim 0; = 0, L is differential at )
11-00
1-00
Remark G.2. Notice that if L is continuously differentiable at 0, then 0 (V is unique. However, for discontinuous differentiable points of L. the differential inclusion flow do defined by Definition G. may not be unique. To study a more specific dynamics, we also utilize Definition H.1 to determine GF at some of such points.
ar E 0 (())
Now we review the definition Karush- Kuhn-Tucker (KKT) conditions for non-smooth optimization problems (Dutta et al., 2013). Consider the following constrained optimization problem (P):
min :f(x)
s.t. (z) Vi [N]
where ... gN Rd + R are locally Lipschitz functions. We say that æ E IR is a feasible point of (P) if x satisfies g (xx) < for all E [N].
Definition G.3 (KKT Point for Non- Optimization). We say that feasible point of (P) is KKT point there exists λy, ... AN 2 0 such that
1.0 0())
A: g()); iE[N]
Σ
2. Vi E [N], A. = 0.
91

---

H Solution of Discontinuous System
In this section, we add some supplements about the definitions of solutions discontinuous systems. which can overcomes non-uniqueness of GF trajectories (2) to some extent. Many definitions of solutions of differential equations with discontinuous systems have been proposed. this paper, we adopt a widely used definition of the solutions in Chapter 2.4 in (Filippov, 2013).
Definition H.1 (Solutions of Discontinuous Systems, Chapter 2.4 in (Filippov, 2013)), Consider n-dimensional equation or a system (a E R):: de in domain G. We aim to define the dynamics near some discontinuous regions.
dæ = f(z) with a piecewise continuous function f
Let the function f be discontinuous on smooth surface giieen by the equation <(x:) = Let x² S and the surface S separate the neighborhood of x² into domains G and G+. Let the function (ax) have the limit values:
(x
lim BEG
f(x),, f ("(x")== :=
lim
f
=EG
Here one should distinguish between two main cases. Let fN (x²) and (x") be projections of the vectors f (x=) and f (x=) onto the normal the surface S at the point x", where the normal is directed towards the domain G
(Case 1). If the vectors f(x") are directed to the surface S on both sides, i.e. (a > 0, I (x=) < O, then the solution the solution starting from x" can not leave S for some time. Moreover,
its dynamics on can be defined in the following way:
dæ
(a)),
dt
(x) where (x) = of (x) + (1 (2r), a (x( (*)
(Case IT). If (xx) 2 0, (x*)
(=*)) 2 0, but f5 and (x=" not both 0, then the solution
starting from x passes from one side of the surface S to the other instantly.
(Case III. If (x*) < 0, (x*) > 0, then the dynamics is defined in the similar way as (Case I).
(Case IV). If / < 0, / (x*) ) < O, but (x= and J (xx) are not both 0, then the dynamics defined in the similar way as (Case II).
Remark H.2. Notice that Definition H.1 overcomes non- uniquunessss of GF trajectories to some extent. It is worth noting that Definition H.1 and Definition G.1 are compatible and specifically, the dynamics defined in Definition (CI I, III) lie in the convex hull defined in Definition G.1.
Remark H.3. In (Lyu et al., 2021), the non-branching starting point Assumption is employed to address the technical challenge of non-uniqueness GF trajectories. By comparison, in this work, do not need this assumption. We adopt Definition H.1 I to uniquely determine the Gradient Flow trajectories theoretically near some discontinuous differential regions, such as "Ridge", "Valley", and "Refraction edge" discussed in Section I.2 in (Lyu et al., 2021).
92

---

I Some Basic Inequalities
Lemma 1.1 (Hoelfding's Inequality). Let X1,... Xn, are independent random variables, and
X, E (a., 6,] for any E [n]. Define X = 1/4 -im X₁. Then for any e > O, we have the following probability inequalities:
2n²²2
P x - [ 2 6) S Sexp
Σ a;)²
2n²²²
PP P(x [[]] S -c) exp
- (b; - a;)²
Lemma I.2. Consider 21, 22 y E g where (011 222) cos A (A E (0, If (y. 20 and x2) S 0, then we have 0 S (y. æτ) S sin A and sin A S y x22 S 0.
Proof of Lemma 1.2. Denote M₂ == span (2)). We can do the orthogonal decomposition of yy:
= yMM + V.M.
where M E MM and yyM Ma. From y E x Ø2). there exist a, 3 E R, s.t. YM = aæ1 + 322.
Due to the orthogonal decomposition, we know yl $ 1, which means a² + 22,3 cos A S
Noticing a² + 3 203 cos A (a B cos A) 2 a² sin? A, know a² sin" A < 1.
Due to x1) 2 and (y, x22 - 0, we have (y σ1) 2 0 and (y .2) - 0, which means
+ 8 cos A 2 0, cos A + 3 O.
So a 2 0 and a sin A 2 Recalling a² cos A S 1, we know S a sin A S 1, Hence, we have + cos A S a a cos A sin" A < sin A, i.e. (1) I sin A.
In the same way, we have sin A (y x2) S
Lemma L33. I 5, have || 2 p+l
2
Proof of Lemma 1.3.
||
1 n
ye
P
x+
E_
2
2
+
2
(1+ (x+,x_)
2p
12
1+p
1+p
(+p/
(1pp)
p +
1
2p
(cos A
+
2
2p
2
pp-1 1 p 1
1+p
1+p)
(1 p)2
(p+
1)2
Lemma 1.4 Let Sd-11 10 If nb) 21 (E ()), p> 5 and cos A 2 4/5, then have
poos A -
-2 A - - (w, Vp² + 2p A
2 A.
Proof of Lemma I.4.
(w, x x.-) = (w. 14) + (w, x 11) = (w, 1n) + (11 11) + (w ,1 x- -1)
It is easy to verify
c08 A |pa x_ x -
pac x=
(,, - 11) = (11, x -1
1:
p2 + 1 2p cos
ccos A-
|x_- - -ull = 222- 2 (1,, x
11 2 2-2 Vp² +
2p cos A
93

---

w - uel| = 2 - 2 (w, mL).
Thus,
(w - ,1 x - 14) S [ - pell | - Hl1
pcos A
pcos A
2
2 (w, p1) S
2
Vp2 p2 + 2ps A V2c
1² +1 2pcos A
V2
p² sin? 2 A
Vp² + cps A + poos 2
1/2 1 cpsos cos A
2VE
psin A
22vesin A.
vp 1 vp- 1+ + poos A
Then we have the bound:
poos A
(ur, x xT
S p² + 2p cos A
+ (w, 11) + 1(w0 p. - -11)
C
+ +2Vesin A,
2pcos cos A
poss A
(w, x) 2 Vp² 1 2pcos A
+ (w. - -K - μ. x_ - -1)1
pcos
c svi
2p cos A
94


Reviews:
[{"review_id": "e0bFvBYigv", "reviewer": "Reviewer_vhgo", "summary": "In this work, the authors attempt an exact analysis of the training dynamics of 2-layer ReLU networks trained via gradient flow on linearly separable data. Specifically, the authors aim to build on related work (e.g., Boursier et al. [2022] on square loss) to the case of:\n- Exponential loss (a more appropriate characteristic of classification problems)\n- With data having mild orthogonal separability\n\nDue to the additional non-linearity introduced by this specific loss type, and the complex data structure, the authors aim to characterize a richer non-linear structure.\n\nBy considering a 2-layer network, where the second-layer weights are held fixed, the authors demonstrate that under gradient flow, the tunable weights of the network evolve in 4 distinctive phases, indicative of a simple to complex learning phenomena.", "questions": "- Can you detail how In Fig. 1, the projection to a 2D subspace span was performed?\n- If the specific dot product of Line 151 has to be true, then data should be normalized, yet that is not mentioned in Assumption 3.1\n- Can you explain the reason behind the assumption on $T_1$ in Line 191?\n- Can you at least intuitively explain why the positive neuron has initial condensation/alignment with the label averaged direction $\\mu$ and *then* transition to the expected $x_{-}^{\\perp}$ direction? On a similar note, is there a reason only the negative neurons eventually *converge toward some specific directions dependent on both data and initialization*? Is it due to $p>1$? If so, I would assume the alignment signal impacts the positive labels over the negative ones, though.", "limitations": "See Questions and Weaknesses", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- The authors extend the analytical formulation established in related previous literature to the case of the harder exponential loss type, which categorizes standard classification loss\n- The authors relax the data orthogonality assumption utilized in these previous works by considering a case where the angle of separability between data points is $<90^\\circ$\n- The authors demonstrate additional data condensation and alignment phases over existent work at the onset and the end of the training, thus attributing to the aim of capturing richer non-linear phenomena.\n- The authors establish bounds on the measure of the bounds on the count of the tunable *positive/negative* neurons in each phase along with the same on their norms, the time extent of these phases.", "weaknesses": "1. While the authors do draw similarities between their work and that of [Boursier et al. [2022]]*, they refer to the latter as performing substantial simplifications and, therefore, unable to capture a lot of non-linear phenomena. Nevertheless, the authors of this work too adopt an identical model and initialization strategy as in the above-cited work.\n1.1 **Most importantly** in Assumption 3.1, are the authors comprising a dataset using **just two data points**? If so, then that is an exceptionally restrictive assumption.\n1.2 The reference to the usage of data averaged direction over the Gram-Schmidt type orthogonal direction, between that work and this, as defining a key improvement, is again not entirely justified if 1.1 above is true. In the case of a set of *non-degenerate* data vectors, defining *useful* orthogonal directions is challenging", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for appreciating our work, as well as the valuable comments. We address the questions in the following.\n\n**Response to Weakness 1.** \n- **Main advantage over [1].** \n  - We acknowledge the similarity in our network and initialization strategy as [1]. However, our analysis takes a step further by delving into more intricate exp-type loss and non-orthogonal data. These aspects empower us to unravel richer nonlinear training behaviors. \n  - While our initial alignment directions ($\\mu,x_+^\\perp$) differ from [1], we don't consider this point as our main advantage. Initial condensation is broadly observed in reality, manifesting in various directions [2]. As the reviewer mentioned, determining condensation directions for realistic settings, such as useful orthogonal ones, is an important topic for future work. \n  - Our main advantage over [1] is that we capture richer nonlinear behaviors, such as Neuron Reactivation, Staged feature learning, and Initialization-dependent directional convergence. Please refer to our Section 5 for more details.\n- **About Assumption 3.1.** \n  - We acknowledge the importance of this assumption in our theory. However, a complete analysis under such a relatively strong assumption is also of great interest to understanding the neural networks’ training dynamics and nonlinear behaviors.\n  - Our motivation is to illustrate that even in a simple setting, GF could exhibit *numerous nonlinear behaviors* that researchers have speculated about, such as saddle-to-plateau, simplifying-to-complicating, etc.\n  - We will work to relax this assumption conditionally. Inspired by reviewers' comments, we have explored a slight relaxation of this assumption by perturbing $x_+$ and $x_-$ with noise, and our experimental results illustrate that similar four-phase dynamics and nonlinear behaviors still exist. For details, Please refer to our **``Global'' Response to All Reviewers**. For a more in-depth study, we leave it to future work.\n\n**Q1. The projection in Fig 1.**\n\n**Response.** WLOG, we can let $x_+=(\\sin(\\Delta/2),-\\cos(\\Delta/2),0_{d-2}^T)^T, x_-=(-\\sin(\\Delta/2),-\\cos(\\Delta/2),0_{d-2}^T)^T$. In this case, the subspace D=span{$x_+,x_-$} is span{$e_1,e_2$}. For k-th neuron at time t, denoted as $b=(b_1,\\cdots,b_d)^T$, its projection onto D is $(b_1,b_2,0_{d-2}^T)^T$. Hence, its polar coordinates is $(\\rho,\\theta)=(\\sqrt{b_1^2+b_2^2},\\arctan(b_2/b_1))$.\n\n**Q2. Data normalization.**\n\n**Response.** Yes, the data is normalized. In Ass 3.1, the requirement $x_+,x_-\\in S^{d-1}$ (Line 136) is actually the $l_2$ normalization.\n\n**Q3. Explain $T_I$.**\n\n**Response.** First, we clarify that $T_I=10\\sqrt{\\kappa_1/\\kappa_2}$ is a result derived in our proof rather than an assumption. By our analysis, at $T_I$, initial condensation can be perfectly completed. Second, we can offer an intuitive explanation for the positive correlation between $T_I$ and $\\kappa_1$, and the negative correlation between $T_I$ and $\\kappa_2$. For small initialization, during initial training, neurons' radial growth is much slower than their tangential speed, leading to directional condensation. For tangent velocity $\\|dw_k(t)/dt\\|$ (equ(7)), notice that (i) $\\kappa_2/\\sqrt{m}\\rho _k(0)=\\kappa_2/\\kappa_1$; (ii) during transient initial training, $F_k(t)$ mostly stays constant, independent of $\\kappa_1$ and $\\kappa_2$. Combining these facts, we see that smaller $\\kappa_1$ and larger $\\kappa_2$ correlate with greater tangential speed, leading to smaller $T_I$.\n\n**Q4. Intuitive explanations for two dynamics.**\n\n**Response.** We agree with the reviewer that it is important to provide intuitive explanations for these dynamics. We will add this aspect in our revised version.\n- **Some positive neurons (PN) moves from $\\mu$ to $x_-^\\perp$.** We will provide an intuitive understanding. For rigorous proof,please refer to Lemma C.3 ~ Lemma C.10. For PN s.t. $w_k(0)^Tx_+>0,w_k(0)^Tx_->0$, it holds:\n    - During Phase I, tangential velocity is much larger than radial velocity, and vector field $F_k(t)\\approx\\mu$. Thus PN rapidly align well with $\\mu$. Concurrently, some negative neurons (NN) align with $x_+^\\perp$. Additionally, since living PN are much closer to $x_-$ than living NN at $T_I$, the prediction of $x_-$ is incorrect ($f_-(T_I)>0$). \n    - After Phase I, to correct the prediction of $x_-$, living PN gradually move away from $x_-$ and decrease positive $w_k^Tx_-$. Notably, living PN can’t move into {$w:w^Tx_-<0$} because the vector field abruptly changes at boundary {$w:w^Tx_-=0$} (due to ReLU’s non-smoothness), redirecting PN to {$w:w^Tx_->0$}. Thus, living PN eventually satisfy $w_k^Tx_-=0$. Notably, vector field $F_k(t)$ lies in the subspace span{$x_+,x_-$}, causing living PN to reach $x_-^\\perp$.\n\n- **Only living negative neurons converge toward directions dependent on initialization.** We will intuitively explain this via \"simplicity bias\". For rigorous proof, please refer to our proof of Theorem 4.10.\n    - In Remark 4.2, we demonstrated that after Phase I, the number of living positive neurons (LPNs) exceeds living negative neurons (LNNs).\n    - At the end of Phase III, the network has the simplest patterns: LPNs exclusively predict  $x_+$, while LNNs solely predict $x_-$. However, prediction $f_-(t)$ evolutes much slower than $f_+(t)$, disliked by GF. Then GF aims to rectify this speed imbalance through a simple approach -- by adjusting directions of fewer LNNs while preserving LPNs' directions.  Precisely,  for LNNs, GF increases $w_k^Tx_-$ and reactivates on $x_+$.    \n    - Hence,  as shown in Thm 4.10, different ratios $\\alpha$ between the numbers of LPNs and LNNs can yield different convergent directions of LNNs, without affecting LPNs.\n\n[1] Boursier et al.  Gradient flow dynamics of shallow relu networks for square loss and orthogonal inputs. (NeurIPS 2022)\n\n[2] Zhou et al. Towards Understanding the Condensation of Neural Networks at Initial Training. (NeurIPS 2022)"}, {"review_id": "adrDHquaYt", "reviewer": "Reviewer_79Zb", "summary": "This paper aims to provide a theoretical understanding of the dynamics involved in training neural networks beyond the linear regime. The authors focus on a specific scenario where a two-layer ReLU network is trained using Gradient Flow (GF) on linearly separable data. The analysis encompasses the entire optimization process, starting from random initialization and concluding with final convergence.\n\nDespite the simplicity of the model and data used in the study, the authors uncover multiple phases within the training process. By conducting a meticulous theoretical analysis, they precisely identify four distinct phases that exhibit various nonlinear behaviors.\n\nIn Phase I, the initial stage of training, there is a phenomenon of condensation and simplification as active neurons rapidly gather in two different directions. Simultaneously, the GF successfully escapes from the saddle point around the initialization.\n\nPhase II involves a prolonged period where the GF becomes trapped in a plateau of training accuracy. However, it eventually manages to escape from this stagnation.\n\nDuring Phase III, a significant number of neurons are deactivated, leading to self-simplification of the network. The GF then adapts its learning approach using this simplified network configuration.\n\nIn Phase IV, a considerable number of previously deactivated neurons are reactivated, resulting in self-complication of the network. Finally, the GF converges towards an initialization-dependent direction.\n\nOverall, the training process exhibits a remarkable behavior of transitioning from simplification to complication. The detailed analysis of each phase sheds light on the intricate dynamics involved in the learning process beyond the linear regime.", "questions": "Dear authors, I have a few questions regarding your work that would greatly aid my comprehension:\n\nHow reliable are the predictions made in this study, and what was the extent of experimentation conducted to support them?\n\nCan general principles be derived from this research that would benefit machine learning practitioners?\n\nHave alternative types of architectures been tested to determine if the findings hold true across different models as well (i.e., more realistic architectures and data sets)?", "limitations": "The limitations of the proposed method are summarized as follows:\n\n* Narrow Scope: This study focuses exclusively on ReLU neural networks trained with Gradient Flow (GF) on linearly separable data. Although the analysis comprehensively captures the optimization process and identifies four distinct phases with rich nonlinear behaviors, the generalizability of the findings to other neural network types or more complex datasets may be limited.\n\n* Limited Generalization to Gradient Descent (GD): While the paper provides a detailed analysis of GF dynamics, it acknowledges that Gradient Descent (GD) dynamics are more complex and can exhibit additional nonlinear behaviors like progressive sharpening and the edge of stability. Consequently, a comprehensive understanding of the nonlinear behaviors during GD training is not fully explored in this study, indicating the need for future research in this direction.\n\n* Theoretical Understanding of Neural Network Training: While this work makes significant strides in theoretically understanding the training dynamics of neural networks, it acknowledges that there is still much progress to be made in fully comprehending the entire training process. Theoretical advancements related to nonlinear behaviors in neural network training, beyond the specific focus of this study, present valuable opportunities for future investigations. With this in mind I would like to suggest works like' The Neural Race Reduction: Dynamics of Abstraction in Gated Networks' Saxe 2022, that get analytical solution to 'Relu like' Neural Networks.\n", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The manuscript demonstrates excellent organization, comprehensiveness, and clarity, effectively covering crucial aspects such as a thorough review of related works and a comprehensive discussion of limitations. Moreover, the paper stands out by successfully combining empirical and theoretical approaches.\n\nOverall, this work makes significant contributions that advance the current state of the literature.", "weaknesses": "These suggestions are intended to improve the overall clarity and accessibility of the research.\n\nThe manuscript does not provide sufficient details regarding the resources and computational aspects involved in the research. Additionally, the work would greatly benefit from a clear delineation of its limitations.\n\nOutlined below are some limitations that underscore the weaknesses of the paper, despite its current status as the best effort in the field.\n\nThe paper lacks a significant number of experimental results to demonstrate the robustness of the findings. It would greatly enhance the study's credibility to include additional examples where the predictions have been validated and to provide measures of their robustness.\n\nThe submission would be strengthened by the addition of the code ran for the experiments", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for appreciating our work and for pointing out the relevant papers. We answer the reviewer’s questions in the following.\n\n**Weakness on experimental results and details.**\n\n**Response.** We thank the reviewer's suggestions on experiments to improve our paper.\n\n  - **More experiments.** We have conducted more experiments to verify the robustness of our theoretical results under more hyperparameter settings. Please refer to our **``Global'' Response to All Reviewers** for further details.\n\n  - **Code.** Following the rebuttal rule in NeurIPS 2023, we have sent an anonymized link to the AC in a separate comment encompassing our standard code along with details of computational resources.\n    \n**Q1. How reliable are the predictions made in this study, and what was the extent of experimentation conducted to support them?**\n\n**Response.** We have conducted more experiments to verify our theory, please refer to our **``Global'' Response to All Reviewers**.\n\n**Q2. Can general principles be derived from this research that would benefit machine learning practitioners?**\n\n**Response.** Through our theoretical analysis, we suggest that the following insights could offer guidance to practitioners:\n\n  - **Use Balanced data by preprocessing.** Our focus is the binary classification problem a small ``margin'' between two data classes and a slight imbalance ($p=n_+/n_->1$). These factors can lead to training challenges and undesirable behaviors such as plateau. Our theory established that training accuracy platea in Phase II persist for $T_{plat}=\\Theta(p/\\kappa_2^2\\Delta^2)$ (Theorem 4.5), which is proportional to $p$ and inversely proportional to $\\Delta^2$. Our experiments support this, revealing that even a slight data imbalance ($p=4$) with $\\Delta=\\pi/15$ can result in a significantly long plateau. Therefore, for practitioners, although regulating $\\Delta$ for multi-class data is complex, the data imbalance can be resolved by simple preprocessing (equalizing the numbers of data in each class), which can reduce the time of plateau and accelerate the rise in training accuracy.\n\n  - **Proper early stopping.** Our theory reveals that neural network training follows a simplifying-to-complicating dynamics learning trend. Initially, the network simplifies itself in Phase I and III, resulting in the ``simplest'' pattern at the end of Phase III (living positive neurons exclusively predict $x_+$, while living negative neurons solely predict $x_-$). However, in Phase IV, living negative neurons revert to predicting $ x_+ $, and the network's pattern becomes more intricate, which can be interpreted as overfitting. Therefore, proper early stopping is necessary to mitigate overfitting in real-world tasks.\n\n**Q3. Have alternative types of architectures been tested to determine if the findings hold true across different models as well (i.e., more realistic architectures and data sets)?**\n\n**Response.** For more practical architectures and datasets beyond our specific settings, while strict theorems might not hold, similar training behaviors persist, as evidenced by the following studies:\n\n  - *Initial condensation* occurs in multi-layer fully-connected neural networks [2];\n    \n  - *Directional convergence* is demonstrated in homogeneous deep neural networks [3];\n    \n  - *Saddle-to-saddle* dynamics are found in deep linear neural networks [4];\n    \n  - *Learning with increasing complexity* is observed in realistic datasets (such as CIFAR-10) and various architectures (FNNs, CNNs, and ResNets) [5].\n    \n  These studies provide valuable insights into the generalizability of the training behaviors discussed in our work.\n\n**L1. Narrow Scope.**\n\n**Response.** As the reviewer commented, under such a relatively strong assumption, our work completely characterizes the entire multi-phase optimization dynamics and exhibits rich nonlinear phenomena. For more complex network architectures and datasets, while strict theorems might not be applicable, our **response to Q3** demonstrates the persistence of similar phenomena. Additionally, we will work to relax this assumption conditionally. For example, our new experiments suggest that training accuracy falls into more plateau during training for noisy data. For more details, please refer to our **``Global'' Response to All Reviewers**. For a more in-depth study, we leave it to future work.\n\n**L2. Limited Generalization to Gradient Descent (GD).**\n\n**Response.** As mentioned by the reviewer, GD can exhibit more nonlinear behaviors, such as progressive sharpening and the edge of stability. Technically, analyzing these phenomena is more difficult compared to GF due to the consideration of appropriate learning rate and stability conditions. We leave analyzing GD's training dynamics for future work.\n\n**L3. Theoretical Understanding of Neural Network Training.**\n    \n**Response.** As the reviewer commented, there is still a long way to go to study the training dynamics of neural networks. We thank the reviewer for pointing out the interesting related work [1]. The neural race introduces a novel implicit bias of learning dynamics: toward shared representations. This idea and the view of gating networks are very enlightening for extending our two-layer theory to deep ReLU neural networks and understanding the dynamics of deep ReLU networks. In our revised version, we will add and discuss this work.\n\n[1]  Saxe et al. The Neural Race Reduction: Dynamics of Abstraction in Gated Networks. (ICML 2022)\n    \n[2] Zhou et al. Towards Understanding the Condensation of Neural Networks at Initial Training. (NeurIPS 2022)\n\n[3] Ji and Telgarsky. Directional convergence and alignment in deep learning. (NeurIPS 2020)\n\n[4] Jacot et al. Saddle-to-Saddle Dynamics in Deep Linear Networks: Small Initialization Training, Symmetry, and Sparsity. (aXiv 2021)\n\n[5] Nakkiran et al. SGD on Neural Networks Learns Functions of Increasing Complexity. (NeurIPS 2019)\n    \n"}, {"review_id": "uI5HDETX1Q", "reviewer": "Reviewer_yJvt", "summary": "The training of ReLU neural networks involves complex nonlinear phenomena, challenging theoretical analysis due to the nonlinearity of models and non-convexity of loss. This study provides a comprehensive theoretical characterization of the training process of a two-layer ReLU network using Gradient Flow on linearly separable data. From random initialization to final convergence, the analysis identifies four different training phases indicating a trend from simplification to complication. Specific nonlinear behaviors, like initial condensation, saddle-to-plateau dynamics, plateau escape, activation pattern changes, and increasing learning complexity, are accurately captured.", "questions": "- Do these four phases persistently exist across different settings (\\kappa_1, \\kappa_2, \\delta, etc.)?\n- For Phase III: “deactivation of positive neurons on $\\mathbf{x}-$” — is this a sign of implicit bias of NN during gradient flow?\n- Phase IV: “reactivation of negative neurons on $\\mathbf{x}+$” — is this a sign of NN's overfitting?\n- It is a bit surprising to me that network width ($m$) and learning rate ($\\eta$) are not included in the form of T1~T4. Could authors intuitively explain why is it from the viewpoint of the proof strategy in this paper?\n- One previous work on NN convergence stated that \"strong correlations\" (of input patches) \"imply faster convergence\", which contradicts the conclusions in this work (i.e. smaller $\\delta$ indicates slower convergence). Could authors compare their work?\n\n[2] \"When is a Convolutional Filter Easy To Learn?\" Du et al. 2017.", "limitations": "- Assumption 3.1 is oversimplified. Basically, all training data collapse into two signals. How will the results change when we switch to a little bit more realistic setting by adding some stochastic noises on top of $\\mathbf{x}+$ and $\\mathbf{x}-$ to each data point?", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper presents a complete theoretical characterization of the training dynamics of 2-layer ReLU networks, which addresses the nonlinearity and non-convexity challenges.\n2. The precise characterization of four distinct phases of the training dynamics.", "weaknesses": "- A missing related work on network's training dynamics and phases [1]\n- Could authors run more hyperparameter settings (\\kappa_1, \\kappa_2, \\delta, etc.) and see if simulated training times (T1 ~ T4) are aligned with estimated ones?\n\n[1] \"Neural Networks as Kernel Learners: The Silent Alignment Effect\" Atanasov et al. 2021", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the appreciation of our work and helpful suggestions to improve this paper. In the following, we answer the reviewer’s questions in detail.\n\n**Q1. A missing related work on network's training dynamics and phases [1].**\n\n**Response.** We thank the reviewer for pointing out the interesting related work [1]. In [1], the authors also characterize multi-phase dynamics of training NNs and demonstrate that NNs in the rich feature learning regime learn a kernel machine due to the silent alignment phenomenon, similar to initial condensation phenomenon in our work. We will add and discuss this work in the revised version.\n    \n**Q2. Could authors run more hyperparameter settings and see if simulated training times are aligned with estimated ones? Do these four phases persistently exist across different settings?**\n\n**Response.** We thank the reviewer's valuable suggestions on new experiments to supplement our theoretical results. To address this, we have conducted additional experiments under more hyperparameter settings (different $\\Delta$, $p$, $\\kappa_1$, and $\\kappa_2$). These experimental results consistently validate the existence of four training phases in our theory and the reliability of our theoretical estimates on training time. For more details, please refer to our **``Global'' Response to All Reviewers**.\n\n**Q3. Explanations for Phase III and IV.**\n\n**Response.** We appreciate the reviewer's insightful perspective. We concur with the reviewer's understanding and will integrate this discussion into our revised version. \n\n  - In Phase III, neurons' deactivation is indeed an implicit bias of GF, which is a ``simplicity bias'' [3] more accurately. Additionally, GF does similar things in Phase I, simplifying the network through initial condensation. \n\n  - In Phase IV, neurons' reactivation is indeed an overfitting behavior because the ReLU activation patterns change from the ``simplest'' scheme to a more complex scheme (as discussed in Table 1).  \n\n  - Combining these understandings, the evolution of activation patterns exhibits a simplifying-to-complicating learning trend.\n\n**Q4. Why network width and learning rate are not included in the estimated times?**\n\n**Response.**\n\n  - Learning rate $\\eta$. Since our focus lies on GF, the version of GD with infinitesimal learning rate (equ (2) in Line 117), our results are independent of $\\eta$.\n    \n  - Network width $m$. We would like to provide an intuitive explanation for the influence of $m$ from our proof strategy. \n\n    - $T_I.$ In Phase I, we decompose neurons' dynamics into tangential and radial dynamics. For small initialization, during initial training, radial neuron growth is much slower than tangential velocity, resulting in directional condensation. For tangent velocity $\\|d w_k(t)/d t\\|$ (equ (7)), note: (i) at initialization, both $\\kappa_2/\\sqrt{m}\\rho _k(0)=\\kappa_2/\\kappa_1$ and $F_k(0)$ are independent of $m$; (ii) During transient initial training, both the norm $\\rho_k(t)$ and $F_k(t)$ stay close to initialization. Thus, tangent velocity is unaffected by $m$ during Phase I.\n    \n    - $T_{II}$, $T_{III}$ and $T_{IV}$. In Phase II, III, and IV, we analyze $f( x_+;\\theta(t))$ and $f( x_-;\\theta(t))$. Notably, both $a_k$ and $b_k$ are normalized by $1/\\sqrt{m}$. Thus, in terms of $m$, the prediction $f(x;\\theta)=\\sum_{k\\in[m]}a_k\\sigma(b_k^\\top x)$ (on data $x$) has magnitude $m\\cdot(1/\\sqrt{m})\\cdot(1/\\sqrt{m})=1$, independent of $m$. Moreover, at the end of Phase I, living positive neurons (LPN) and living negative neurons (LNN) align with $\\mu$ and $ x_+^\\perp$, respectively. After Phase I, LPNs stay close, as do LNNs. So, for prediction, LPN and LNN can be conceptually treated as a single positive neuron and a single negative neuron, respectively, independent of $m$. A similar idea is present in the neuron embedding technique in [3].\n\n**Q5. Comparsion with the previous work [2] ``strong correlations'' (of input patches)**\n\n**Response.** We thank the reviewer for raising this intriguing question, and we provide the following response: \n    \n  - In [2], the authors mentioned that when utilizing a CNN to extract a single feature $w^*$, optimization becomes easier with higher correlation between patches $\\arg\\left<Z_i,Z_j\\right>$, and between patch and target $\\arg\\left<Z_i,w^*\\right>$ (as shown in their Figure 1). The underlying reason lies in the context of a regression problem that involves only a ``single class of data'' (single feature).\n\n  - However, our setting is binary classification with two distinct classes of data ($\\pm 1$), and the correlation between two classes should be characterized by label-weighted data angle: $\\arg\\left<1\\cdot x_+,-1\\cdot x_-\\right>=\\pi-\\Delta$. Thus, smaller $\\Delta$ means weaker data correlation. Moreover, our theory and experiments validate that larger $\\Delta$ (indicating stronger data correlation) yields easier training.\n\n  - Therefore, the conclusions of our work and [2] are consistent, both implying: ``strong correlations imply faster convergence''.\n\n**Q6. Relax assumption 3.1 to noisy data.**\n\n**Response.** We thank the reviewer for offering this insightful suggestion to generalize our findings to noisy data. We have conducted additional experiments on our dataset with some stochastic noises on top of $x_+$ and $x_-$. Our numerical results illustrate that the same four-phase optimization dynamics and similar nonlinear behaviors persist for noisy data. For more details, please refer to our **``Global'' Response to all Reviewers**.\n\n[1] Atanasov et al. Neural Networks as Kernel Learners: The Silent Alignment Effect. (ICLR 2022)\n\n[2] Du et al. When is a Convolutional Filter Easy To Learn? (ICLR 2018)\n\n[3] Lyu et al. Gradient Descent on Two-layer Nets: Margin Maximization and Simplicity Bias. (NeurIPS 2021)"}, {"review_id": "A7KbweqtdR", "reviewer": "Reviewer_w3Qj", "summary": "This paper conducts a comprehensive theoretical analysis of the training dynamics of two-layer ReLU neural networks on a linearly separable data. The authors isolate four discrete phases of the training procedure and describe specific nonlinear behaviors that occur during each phase. Moreover, they derive explicit formulae for the evolution of the network parameters and prove convergence results for the network's output. The paper's contributions include a complete theoretical characterization of the training process, a better understanding of the role of initialization and regularization, and insights into the generalization properties of ReLU networks. In brief, the research provides a valuable addition to the domain of deep learning theory and sheds light on the training process of ReLU.", "questions": "Can the authors provide empirical validation of their theoretical results? While the authors provide rigorous mathematical proofs and derive explicit formulas, it would be useful to validate these results on real-world datasets.\n", "limitations": "Yes.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "The originality of the paper lies in its complete theoretical characterization of the training process of the two-layer ReLU network. While previous work has focused on local analysis or approximate linear models, this paper provides a more comprehensive understanding of the optimization dynamics of ReLU networks. The authors identify four distinct stages of the training process and describe the specific nonlinear behavior that occurs at each stage. They also derive explicit formulations for the evolution of network parameters and demonstrate convergent results for network outputs. Besides, the authors provide rigorous mathematical proofs and derive explicit formulas that shed light on the complex dynamics of ReLU networks.\n", "weaknesses": "First, a weakness of the paper is that it focuses on the specific setting of two-layer ReLU networks trained on linearly separable data. While this setting is useful for providing a full theoretical characterization of the training process, it may not generalize to more complex networks or datasets. \n\nSecond, another weakness of the paper is that it does not provide empirical verification of its theoretical results. While the authors provide rigorous mathematical proofs and derive explicit formulas, it would be useful to validate these results on real-world datasets.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's recognition of our work and helpful comments. Below, we offer detailed responses to the reviewer's questions:\n\n**Q1. First, a weakness of the paper is that it focuses on the specific setting of two-layer ReLU networks trained on linearly separable data. While this setting is useful for providing a full theoretical characterization of the training process, it may not generalize to more complex networks or datasets.**\n\n**Response.** As the reviewer commented, under such a relatively strict assumption on data and networks, we can capture the entire training process of the neural network, exhibiting multi-stage optimization dynamics and rich nonlinear behaviors. While our theorems might not hold for more intricate networks and datasets, similar multi-phase dynamics and nonlinear behaviors could still manifest. For a preliminary exploration of the extension of our findings, please refer to our **``Global'' Response to All Reviewers**. Furthermore, we are intrigued by exploring the complete training dynamics of more complex networks and datasets, focusing on characterizing new nonlinear behaviors. We leave this to future work.\n    \n**Q2. Second, another weakness of the paper is that it does not provide empirical verification of its theoretical results. While the authors provide rigorous mathematical proofs and derive explicit formulas, it would be useful to validate these results on real-world datasets. Can the authors provide empirical validation of their theoretical results?**\n\n**Response.** We thank the reviewer for reminding us of more empirical validation. We have conducted more experiments to further support our theoretical results. For experimental results, please refer to our **`` Global'' Response to All Reviewers**. Regarding real-world datasets and networks, some previous works indicate similar nonlinear phenomena may still occur; please refer to our **response to Reviewer 79Zb's Q3**. Additionally, we will pursue theoretical investigations into these aspects in our future work."}]

Author rebuttal:
**``Global'' Response to All Reviewers.**

1. First, we sincerely thank all the reviewers for appreciating our result, i.e., a theoretical analysis of multi-phase optimization dynamics and the rich nonlinear behaviors of ReLU networks. We also thank all the reviewers for their comments and suggestions to improve our paper. In our revised version, we will correct all typos, provide complete experimental settings and results, and incorporate the discussions with the reviewers.

2. **More Experiments.** In response to multiple reviewers' suggestions regarding the need for further numerical validation of our theory, we have included two additional experiments to showcase the effectiveness of our theoretical findings. Below, we summarize the experimental setups, results, and conclusions. As for detailed experimental results, please refer to our updated **one-page PDF**.

    - **Experiment 1: More hyperparameter settings.**
      - **Setup.** We run experiments under more hyperparameter settings (different $\Delta$, $p$, $\kappa_1$, $\kappa_2$). We aim to verify whether the same four training phases persistently exist and evaluate the consistency between our theoretical bounds ($T_{\rm I}$, $T_{\rm plat}$, $T_{\rm II}$, $T_{\rm III}$) and empirical outcomes.
        
      - **Result.** Due to space constraints, a subset of the results is presented in **Table 2 in one-page PDF**. Precisely, the table displays outcomes under different $\Delta$ and $p$ (data-dependent hyperparameters), and we focus on the changes of $T_{\rm plat}$ (time plateau of training accuracy) and $T_{\rm III}$ (ending time of Phase III).

      - **Conclusion.** From our numerical results in Table 1 in one-page PDF, we have two main conclusions: (i) four training phases in our theory persistently exist; (ii) our theoretical estimates on $T_{\rm plat}$ and $T_{\rm III}$ demonstrate noteworthy alignment with realistic results (in terms of $p$ and $\Delta$).
        
        In the revised version, we will present the complete results.
    
    - **Experiment 2: Noisy Data.** 
        
      - **Setup.** We conduct numerical experiments on the setting of adding small stochastic noise on top of $x_+$ and $x_-$, a little bit more realistic setting. Specifically, in span{$x_+,x_-$}, we perturb the angles of data $x_+$ and $x_-$ by noise $\xi\sim{\rm Unif}([0,\Delta/4])$.
    
      - **Result.** In **Figure 5 in one-page PDF**, we visualize (i) the evolution of each neuron throughout the training process; (ii) some key data directions; (iii) the evolution of training accuracy. To compare these results with noiseless data, the reviewers can refer to our previous Figures 3 and 4 in Appendix A.
        
      - **Conclusion.** From our numerical results in Figure 1 in the one-page PDF, we have two main conclusions: (1) we ascertain that the same four-phase optimization dynamics and nonlinear behaviors persist, even for our dataset with small stochastic noise; (2) a slight difference is that there is more than one plateau of training accuracy in Phase II. The reason is that for noisy data, GF needs to learn negative data $(y=-1)$ one by one in Phase II. For example, three distinct negative data are employed in this experiment, so three plateaus of training accuracy emerge (12/15, 13/15, and 14/15).

3. We have addressed every concern raised by each reviewer through separate responses provided below.

Meta-review: This paper explores the dynamics of learning in ReLu networks. Their theoretical analyses find four stages of learning, expanding on previous efforts that focused on the beginning or end of learning, or on approximations of learning such as linear networks. The contributions of this work are primarily theoretical, although numerical verification of the theory is provided.

The reviewers generally appreciated the work. The main drawbacks were the assumptions chosen to enable the more thorough derivation, including using Gradient Flow over the more generally used Gradient descent, the focus on linearly separable data, and the focus on ReLu networks. Nonetheless the reviewers agreed that the depth of the result compensates for the more narrow assumptions and is a worthy contribution to the NeurIPS conference. I therefore recommend this work be accepted.

Some side commentary, the analysis is reminiscent of the information bottleneck principles in deep learning explored by the late Tali Tishby and others. it would be quite interesting to understand the relationship between the four stages found by the authors and the two stages identified by that analysis.
Decision: Accept (spotlight)