Paper deep dive
On the Learning Dynamics of Two-layer Linear Networks with Label Noise SGD
Tongcheng Zhang, Zhanpeng Zhou, Mingze Wang, Andi Han, Wei Huang, Taiji Suzuki, Junchi Yan
Intelligence
Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 93%
Last extracted: 3/13/2026, 1:10:22 AM
Summary
The paper investigates the learning dynamics of two-layer over-parameterized linear networks trained with stochastic gradient descent (SGD) under label noise. It identifies a two-phase learning process: Phase I, where weight magnitudes decrease and the model transitions from a 'lazy' regime to a 'rich' (feature learning) regime, and Phase II, where weights align with the ground-truth interpolator. The authors demonstrate that label noise drives this transition and extend these findings to Sharpness-Aware Minimization (SAM).
Entities (5)
Relation Signals (3)
Label Noise SGD → drivestransition → Lazy Regime
confidence 90% · Our analysis highlights the critical role of label noise in driving the transition from the lazy to the rich regime
Sharpness-Aware Minimization → fosterstransition → Rich Regime
confidence 90% · We show that SAM also fosters the transition from the lazy to rich regime
Label Noise SGD → inducedby → Implicit Bias
confidence 85% · One crucial factor behind the success of deep learning lies in the implicit bias induced by noise inherent in gradient-based training algorithms.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:One crucial factor behind the success of deep learning lies in the implicit bias induced by noise inherent in gradient-based training algorithms. Motivated by empirical observations that training with noisy labels improves model generalization, we delve into the underlying mechanisms behind stochastic gradient descent (SGD) with label noise. Focusing on a two-layer over-parameterized linear network, we analyze the learning dynamics of label noise SGD, unveiling a two-phase learning behavior. In \emph{Phase I}, the magnitudes of model weights progressively diminish, and the model escapes the lazy regime; enters the rich regime. In \emph{Phase II}, the alignment between model weights and the ground-truth interpolator increases, and the model eventually converges. Our analysis highlights the critical role of label noise in driving the transition from the lazy to the rich regime and minimally explains its empirical success. Furthermore, we extend these insights to Sharpness-Aware Minimization (SAM), showing that the principles governing label noise SGD also apply to broader optimization algorithms. Extensive experiments, conducted under both synthetic and real-world setups, strongly support our theory. Our code is released at this https URL.
Tags
Links
- Source: https://arxiv.org/abs/2603.10397v1
- Canonical: https://arxiv.org/abs/2603.10397v1
Trouble viewing inline? Open PDF directly →
Full Text
122,231 characters extracted from source content.
Expand or collapse full text
On the Learning Dynamics of Two-layer Linear Networks with Label Noise SGD Tongcheng Zhang1∗, Zhanpeng Zhou1 , Mingze Wang2, Andi Han3,4, Wei Huang4,5†, Taiji Suzuki4,6, Junchi Yan1 1Sch. of Computer Science and Zhiyuan College, Shanghai Jiao Tong University 2Peking University 3University of Sydney 4RIKEN Center for Advanced Intelligence Project 5The Institute of Statistical Mathematics 6The University of Tokyo a-usually, zzp1012, yanjunchi@sjtu.edu.cn, wei.huang.vr@riken.jp Equal contribution.Corresponding authors. Junchi Yan is also with School of AI, Shanghai Jiao Tong University. The authors of Shanghai Jiao Tong University were partly supported by NSFC 92370201. Abstract One crucial factor behind the success of deep learning lies in the implicit bias induced by noise inherent in gradient-based training algorithms. Motivated by empirical observations that training with noisy labels improves model generalization, we delve into the underlying mechanisms behind stochastic gradient descent (SGD) with label noise. Focusing on a two-layer over-parameterized linear network, we analyze the learning dynamics of label noise SGD, unveiling a two-phase learning behavior. In Phase I, the magnitudes of model weights progressively diminish, and the model escapes the lazy regime; enters the rich regime. In Phase I, the alignment between model weights and the ground-truth interpolator increases, and the model eventually converges. Our analysis highlights the critical role of label noise in driving the transition from the lazy to the rich regime and minimally explains its empirical success. Furthermore, we extend these insights to Sharpness-Aware Minimization (SAM), showing that the principles governing label noise SGD also apply to broader optimization algorithms. Extensive experiments, conducted under both synthetic and real-world setups, strongly support our theory. Our code is released at https://github.com/a-usually/Label-Noise-SGD. 1 Introduction One central factor behind the success of modern deep learning stems from the implicit bias induced by inherent stochastic noise in gradient-based training algorithms. While clean training data is ideal, recent studies [44, 21, 10] revealed that injecting label noise, or label smoothing during training can paradoxically improve the generalization of neural networks. Figure˜1 demonstrates the observation where stochastic gradient descent (SGD) with label noise enhances model generalization capability and inherently favors sparser solutions. Wang and Jacot [49] also demonstrated that training with SGD alone jumps from the local minimum solution with only a small possibility. These phenomena challenge conventional wisdom and raise a fundamental question: How does label noise, often undesirable in statistical learning, confer benefits in over-parameterized models? Existing theoretical works have tried to understand the mechanisms behind SGD with noisy labels. Blanc et al. [5], Damian et al. [10], Li et al. [34] focused on the local geometry around the global minimizers selected by label noise SGD. HaoChen et al. [21], Vivien et al. [47] analyzed the behavior of diagonal linear networks under label noise SGD. However, few attempts to study the learning dynamics of label noise SGD in a more realistic setting. Our Contributions. In this work, we provide a theoretical analysis of the learning dynamics in a two-layer linear network trained with label noise SGD. • Theoretical analysis. In this work, we rigorously characterize the learning dynamics of a two-layer linear network where both layers are trainable by label noise SGD on a regression task. In particular, we identify two phases: • Phase I. The magnitudes of neuron weights progressively diminish, and the model escapes from the lazy regime [9]; enters the rich regime Geiger et al. [17]. • Phase I. The neurons increasingly align ground-truth interpolator, and the model becomes sparser. Refer to Table˜1 for a summary. In the lazy regime, the dynamics are linear and the model achieves zero training loss with parameters hardly varying [13, 32, 12, 2]. The lazy regime is often considered undesirable in practice and fails to explain the surprising generalization of neural networks [9]. In contrast, the rich regime, or feature learning, which draws significant attention recently, captures complex non-linear dynamics and is considered beneficial for generalization. Our analysis highlights the effect of label noise SGD in shifting dynamics from lazy to rich regime, serving as a minimalist example to explain its intriguing properties. Notably, the combination of over-parameterization and the intricate coupling between the first and second layers makes the theoretical analysis of label noise SGD far more challenging than for simpler linear models. To the best of our knowledge, our work presents the first detailed theoretical investigation of label noise SGD in networks with two or more trainable layers. • Extension. Furthermore, we explore whether the principles underlying label noise SGD apply to broader optimization algorithms. We extend our findings on label noise SGD to Sharpness-Aware Minimization (SAM) [15]. We show that SAM also fosters the transition from the lazy to rich regime and promotes sparsity in neural networks. In summary, our work unveils a richer set of implicit bias of label noise SGD. We theoretically analyze the dynamics of SGD with label noise and carefully characterize how it transitions from lazy to rich regime. Our results offer valuable insights into the mechanisms behind the noise inherent in stochastic learning algorithms. Figure 1: (Left).Label noise SGD (Algorithm˜1) leads to better generalization. Test loss ℒ((t))L( θ(t)) and accuracy Acc((t))Acc( θ(t)) vs. training epochs t. (Right). Label noise SGD leads to sparser solutions. Testing accuracy of pruned model Acc((T;α))Acc( θ(T;α)) vs. the percentage of remaining parameters α. Here, (T;α) θ(T;α) represents the pruned model derived from the pretrained model (T) θ(T), with α% of parameters remaining. We use both vanilla SGD and label noise SGD to train the models, with no weight decay or momentum. The learning rate is set to 0.10.1, and the total number of epochs is 160160. Exponential moving average is employed to smooth the test accuracy curves. Results are presented for ResNet-18 [22] trained on CIFAR-10 [28], across different label noise probabilities, (τ∈0.05,0.1,0.2)(τ∈\0.05,0.1,0.2\). As shown in figure (a) and figure (b), label noise SGD consistently outperforms vanilla SGD in both test loss and accuracy across different values of the label flipping probability τ, providing an around 1.51.5% improvement in test accuracy. As shown in Figure˜1 (c), models trained with label noise SGD maintain higher performance at the same sparsity level compared to those trained with vanilla SGD. 2 Related Work Lazy Regime. Numerous theoretical studies investigated the learning dynamics of highly over-parameterized neural networks in the lazy (or kernel) regime [25, 13, 12, 2, 53]. In this regime, the model behaves as its linearized model around initialization throughout training, making it equivalent to a deterministic kernel, specifically the neural tangent kernel (NTK) [25]. The lazy regime typically occurs in over-parameterized models with relatively large initialization [9]. While global exponential convergence can be established in this setting, the lazy dynamics fail to explain the generalization advantage over kernel methods—a fundamental question in understanding the success of deep learning. Rich Regime. In contrast to the lazy regime, where learning dynamics remain linear, the rich regime111This term broadly refers to learning behaviors that deviate from the lazy regime., also known as feature learning regime, exhibits complex nonlinear dynamics [8, 40], including the initial alignment phenomenon [39, 36] and saddle-to-saddle dynamics [26, 1, 43]. Some studies have demonstrated that the initialization scale governs the emergence of the rich regime in (S)GD, which typically occurs at small initialization scales [17, 50]. In this regime, it is shown that small initialization induces simplicity biases, leading to sparse or low-rank features [39, 33, 38, 6, 48, 41]. Subsequent work further revealed that the relative scale of initializations [3, 29] and their effective rank [35] can similarly induce feature learning. Beyond initializations, factors like weight decay [31, 27, 37] and large learning rates [30, 4] have also been shown to drive the rich regimes. Label Noise SGD Theories. Many existing theoretical works have analyzed label noise SGD from the perspective of implicit regularization. Blanc et al. [5], Damian et al. [10], Li et al. [34] showed that label noise implicitly regularizes the sharpness of the minimizers. HaoChen et al. [21], Vivien et al. [47] proved that training with label noise helps recover the sparse ground-truth interpolator in a diagonal linear network setup. Takakura and Suzuki [45] analyzed the implicit regularization of label noise from a kernel perspective. In addition to implicit regularization, Huh and Rebeschini [24] derived a generalization bound for label noise SGD. Han et al. [19] theoretically analyzed the training dynamics with static label noise. Huang et al. [23] analyzed the generalization capability in low SNR regimes. Varre et al. [46] showed that label noise SGD tends to gradually reduce the rank of the parameter matrix. In comparison, we theoretically analyze the learning dynamics of label noise SGD in an over-parameterized two-layer linear network, highlighting the transition from lazy to rich regime. Analyzing the two-layer linear network with label noise SGD requires careful treatment of the update rule of both layers, which introduces complex coupling effect between the first and the second layer parameters, thus posing significant challenges to theoretical analysis. 3 Preliminaries Algorithm 1 Label Noise SGD [21, 10] Input: Initial parameters (0) θ(0), step size η, label flipping probability τ, batch size B, steps T. 1: for t=0t=0 to T−1T-1 do 2: Sample a batch ℬt∈[n]BB_t∈[n]^B uniformly. 3: for each i∈ℬti _t do 4: Sample u∼Uniform(0,1)u Uniform(0,1). 5: if u<τu<τ then 6: y~i= y_i= sample from [c]\yi[c] \y_i\. 7: else 8: y~i=yi y_i=y_i. 9: end if 10: ℓ^i((t))=ℓ(f((t);i),y~i) _i( θ(t))= (f( θ(t); x_i), y_i). 11: end for 12: ℒ^((t))=1B∑i∈ℬtℓ^i((t)) L( θ(t))= 1B _i _t _i( θ(t)). 13: (t+1)=(t)−η∇ℒ^((t)) θ(t+1)= θ(t)-η∇ L( θ(t)). 14: end for Basic Notation and Setup. Denote [k]=1,2,…,k[k]=\1,2,…,k\. Let =(i,yi)i=1nD=\( x_i,y_i)\_i=1^n be the training set, where i∈ℝd x_i ^d is the input and yi∈ℝy_i is the label/target of the i-th data point. Let f:×ℝd→ℝf:D×R^d be the model function and let f(i;)f( x_i; θ) be the model output on the i-th data point, where ∈ℝp θ ^p are the model parameters. The loss of the model at the i-th sample (i,yi)( x_i,y_i) is denoted as ℓ(f(i;),yi) (f( x_i; θ),y_i), simplified to ℓi() _i( θ). The loss over the training set is then given by ℒ()=1n∑i=1nℓi()L_D( θ)= 1n _i=1^n _i( θ). Note that we consider classification tasks in our empirical observations, where yi∈[c]y_i∈[c] and c are the number of classes. We also use Acc()Acc_D( θ) to denote the classification accuracy of f()f( θ) on the dataset D. Throughout the paper, bold lowercase letters denote vectors, and bold uppercase letters represent matrices. The unbolded lowercase letters with subscripts indicate the entries of vectors or matrices, such as xix_i for the i-th entry of x and ai,ja_i,j for the (i,j)(i,j)-th entry of A. For simplicity, we use ‖\| x\| as ‖2\| x\|_2 for a vector x and ‖\| X\| as ‖F\| X\|_F for a matrix X. Label Noise SGD. We recall the algorithm of label noise SGD in Algorithm˜1. We focus on a classification setting, where the label flipping probability τ governs the noise level; for simplicity, our theoretical analysis considers a regression task. Specifically, label noise SGD can be adapted to regression by replacing τ with the noise variance σ2σ^2. In this context, the noisy label y~i y_i is generated by y~i=yi+ϵ,where ϵ∼−σ,σ. y_i=y_i+ε,where ε \-σ,σ\. Assuming the squared loss without loss of generality, the training loss at the i-th data is given by: ℓ^i((t))=12|f((t);i)−yi−ϵ|2. _i( θ(t))= 12 f( θ(t); x_i)-y_i-ε ^2. (1) This setup is widely adopted in recent theoretical advances on label noise SGD [10, 21, 34, 47, 14]. 4 Theoretical Analysis: The Learning Dynamics of Label Noise SGD This section presents a theoretical analysis of learning dynamics in a two-layer linear network, characterizing the phase transition from lazy to rich regimes under label noise SGD. Roadmap. In Section˜4.1, we formulate the problem setup and provide an overview of our theoretical results. In Section˜4.2, we present formal theorems. In Section˜4.3, we demonstrate the role of oscillation using a simple scenario. In Section˜4.4, we validate our theory by extensive experiments under both synthetic and real-world setups. 4.1 Setup and Overview: A Two-Layer Linear Network Problem Setup. We consider a regression task where each data pair (i,yi)∈( x_i,y_i) maps input i∈ℝd x_i ^d to its corresponding target yi∈ℝy_i . We solve this task using a two-layer linear network of the form: y^i=⊤i, y_i= a W x_i, (2) where ∈ℝm×d W ^m× d and ∈ℝm a ^m. Here, m represents the number of neurons and i w_i denotes the i-th neuron of W. • Label noise SGD. The network’s parameters =⊤ θ= a W are optimized using label noise SGD with a squared loss function (see Equation˜1). The update rule is written as: (t+1)=(t)−η∇ℓ^ξt((t)), θ(t+1)= θ(t)-η _ θ _ _t( θ(t)), (3) ℓ^ξt((t))=12|f((t);ξt)−yξt−ϵt|2, _ _t( θ(t))= 12 f( θ(t); x_ _t)-y_ _t- _t ^2, (4) where ξt∈[n] _t∈[n] represents the index of a randomly sampled training sample at iteration t, and the noise ϵt∼−σ,σ _t \-σ,σ\ is controlled by the variance σ2σ^2. • Initialization. We consider label noise SGD starting from the following initializations: for i∈[m]i∈[m] and j∈[d]j∈[d], wi,j(0)∼i.i.d.1d(0,I)andai(0)∼i.i.d.1m(0,I). w_i,j(0) i.i.d. 1 dN(0,I) \ and\ a_i(0) i.i.d. 1 mN(0,I). (5) This initialization scheme is commonly referred to as the NTK initialization Jacot et al. [25]. Allen-Zhu et al. [2] showed that training over-parameterized models initialized as Equation˜5 with SGD stays in the lazy regime. • Data generation. Without loss of generality, we assume each input i x_i is drawn from (0,d×d)N(0, I_d× d), and that there exists at least one interpolating parameter ⋆ θ that perfectly fits the training set, i.e., ℒ(⋆)=0L_D( θ )=0222ℒ(⋆)=1n∑i=1nℓi(⋆)=1n∑i=1n12|f(⋆;i),yi|2L_D( θ )= 1n _i=1^n _i( θ )= 1n _i=1^n 12 f( θ ; x_i),y_i ^2. I The magnitudes of model weights progressively diminish; Lemma˜4.3 The model escapes the lazy regime; enters the rich regime. Theorem˜4.2 I The alignment between model weights and the ground-truth Lemma˜4.5 interpolator increases; the model eventually converges. Lemma˜4.6 Table 1: Overview of the two-phase picture and corresponding theoretical results. Overview. We first state our main conditions. Condition 1. Suppose there exists a sufficiently large constant 333C≥max(e−(σCdata)23,((1−3/(4π))⋅2d1/2−3/(4π)π)8,eCdata2)C≥ (e^- (σ C_data)^23,( (1-3/(4 π))· 2 d1/2-3/(4 π) π)^8,eC_data^2), where CdataC_data is a constant defined in 1 A(5) C such that the following holds: 1. (A1) Model width. The width of the network m satisfies m=Ω(1η)m= ( 1 η ). 2. (A2) Learning rate. The learning rate satisfies η≤1C96η≤ 1C^96. 3. (A3) Dataset size. The training set size satisfies n≥1η2n≥ 1η^2. 4. (A4) Scale of the optimal parameter. The ground-truth interpolator satisfies ‖⋆‖≤m−1/4\| θ \|≤ m^-1/4. 5. (A5) Input magnitude. The maximum norm of the input samples satisfies maxi‖i‖≤Cdata _i\| x_i\|≤ C_data. 6. (A6) Dimension of sample. The dimension of a single sample d satisfies d≥9(ln2)⋅K42cd≥ 9( 2)· K^42c. Remarks on ˜1. Specifically, A1 ensures over-parameterization, where m≫dm d, which is important for enabling the progressively diminishing of weight norm in Phase I. A2 ensures the step size is small enough to allow Phase I to persist over a long range of iterations. A3 addresses the dataset size: when using gradient descent, a substantial volume of training data is typically required. A4 assumes the sparse ground-truth interpolator. For the sake of clarity in our theoretical analysis, we additionally introduce the A5 to give an upper bound of input norm and A6 to give a lower bound of input dimension. In A5, CdataC_data is a constant and by definition of C in A1, we have Cdata≤C≪mC_data≤ C m. In A6, both K and c are constant and defined in Appendix (Lemma A.5). Under these conditions, we can state our main results: we identify a two-phase picture in the training dynamics of label noise SGD, as outlined in Table˜1. In the following, we will formally present our formal theorems, with each claim supported by corresponding analysis. Figure 2: Two-phase dynamics of label noise SGD under synthetic setup. We replicate the synthetic problem setup from Section˜4.5. (a) Loss curves. Training ℒtrain((t))L_D_ train( θ(t)) and test loss ℒtest((t))L_D_ test( θ(t)) vs. training iteration t. (b) Learning dynamics on average. The mean neuron norm Avgi∈[m](‖i(t)‖2)Avg_i∈[m](\| w_i(t)\|_2) and the mean neuron alignment Avgi∈[m](⟨i(t),⋆⟩)Avg_i∈[m]( w_i(t), θ ) vs. training iteration t. (c) Learning dynamics of i-th neuron. The alignment of the i-th neuron ⟨i(t),⋆⟩ w_i(t), θ vs. its weight norm ‖i(t)‖2\| w_i(t)\|_2, with darker points indicating larger t. (Bottom) Complete view of dynamics of each neuron. This plot is similar to (c); yet instead of focusing on a single neuron, we plot the status over iterations. 4.2 Phase I: Progressively Diminishing; From the Lazy to the Rich Regime In this section, we present theoretical support for Phase I. Inspired by Du et al. [13, 12], Allen-Zhu et al. [2], we first introduce the definition of the lazy regime. Definition 4.1 (The lazy regime). ∀i∈[m]∀ i∈[m], it holds that ‖i(t)−i(0)‖≤1m\| w_i(t)- w_i(0)\|≤ 1 m. Definition˜4.1 depicts a minimal variation of model weights from its initialization at time t. Based on Definition˜4.1, we establish the following theorem. Theorem 4.2 (Escaping the lazy regime). Suppose ˜1 (A1-2, 4-6) hold and consider the update rule in Equation˜3. With probability at least 1−O(1m)1-O( 1m), all the neurons i w_i (i∈[m]i∈[m]) escape from the lazy regime at time T1=384logmσ2η2mT_1= 384 mσ^2η^2 m. Insights from Theorem˜4.2. Theorem˜4.2 indicates that in Phase I, label noise SGD facilitates the transition from the lazy to the rich regime. Indeed, such transition is induced by the progressively diminishing of the first-layer weights W. Specifically, for each neuron i(i∈[m]) w_i(i∈[m]) at time T, we can easily derive that ‖i(T)‖2=‖i(0)‖2+η2∑j=0T−1ΔWi(j)−ai(0)2+ai(T)2\| w_i(T)\|^2=\| w_i(0)\|^2+η^2 _j=0^T-1 W_i(j)-a_i(0)^2+a_i(T)^2 and ΔWi(j)=−∇ℓ^ξj((j))2((ξj⊤⋅i(j))2−ai(j)2⋅‖ξj‖2) W_i(j)=-∇ _ _j( θ(j))^2(( x_ _j · w_i(j))^2-a_i(j)^2·\| x_ _j\|^2). Since (0) a(0) is initialized small, the term ∇ℓ^ξj((j))2(ξj⊤⋅i(j))2∇ _ _j( θ(j))^2( x_ _j · w_i(j))^2 dominates the evolution of the weight norm. Notably, by Equation˜3, we have ∇ℓ^ξj((j))2(ξj⊤⋅i(j))2=(ai(j+1)−ai(j))2.∇ _ _j( θ(j))^2( x_ _j · w_i(j))^2=(a_i(j+1)-a_i(j))^2. Consequently, the evolution of the first-layer weight norm is primarily determined by the oscillations of the neurons in the second layer. Intuitively, label noise accelerates the oscillations in the second layer, thereby contributing to the progressive diminishing of the first-layer weights. Proof Sketch of Theorem˜4.2. The proof relies on Lemma˜4.3. Lemma 4.3 (Progressively diminishing at each step). Suppose ˜1 (A1-2, 4-6) hold and consider the update rule in Equation˜3. Assume the model is still under the lazy regime at step T, then with probability at least 1−O(1m)1-O( 1m), for all the iterative steps j≤T1j≤ T_1 and for every i∈[m]i∈[m]: 1. ΔWi(j)≤0 W_i(j)≤ 0 with probability at least 1−ρm1/81- ρm^1/8. Furthermore, ΔWi(j)≤−(σ4)2 W_i(j)≤-( σ4)^2 with probability at least 14 14. 2. ΔWi(j)>0 W_i(j)>0 with probability at most ρm1/8 ρm^1/8. Furthermore, we have ΔWi(j)≤O(1) W_i(j)≤ O(1). where ρ=2dπρ= 2 d π is a constant. Lemma˜4.3 states that with high probability, ΔWi(j) W_i(j) is negative at each step. Furthermore, with probability at least 14 14, ΔWi(j) W_i(j) significantly deviates from zero. In our setup, we can prove that with high probability, |ai(t)||a_i(t)| remains small throughout training. Thus, ΔWi(j) W_i(j) primarily governs the change in ‖i‖2\| w_i\|^2 at each step. With Lemma˜4.3, we can demonstrate the progressive diminishing of the first-layer weights W, thereby driving the transition from lazy to rich regime. 4.3 Simulation Setup: Oscillation Induces Progressive Diminishing In the previous analysis, we have shown that the oscillation of the second layer plays a central role in the progressive diminishing of the first-layer weights W, and label noise SGD facilitates the oscillations, leading to the phase transition. Simulation Setup. Inspired by the discovery, we propose to simulate the oscillation of the second layer via a simple three-state Markov process. To eliminate the interference of SGD noise, the first-layer weights i w_i follow GD update rule: i(t+1)=i(t)−η⋅ai(t)∇ℒ((t))i, w_i(t+1)= w_i(t)-η· a_i(t) _D( θ(t)) x_i, (6) ai(t+1)=ai(t)+δi(t), a_i(t+1)=a_i(t)+ _i(t), (7) where δi(t)=−η0.25if ai(t)=η0.25η0.25if ai(t)=−η0.25∼−η0.25,η0.25if ai(t)=0 _i(t)= \ aligned &-η^0.25 $a_i(t)=η^0.25$\\ &η^0.25 $a_i(t)=-η^0.25$\\ & \-η^0.25,η^0.25\\ \ \ \ if $a_i(t)=0$ aligned . The initialization of aia_i is set to η0.25η^0.25 or −η0.25-η^0.25, each with probability 1/41/4 and set to 0 with probability 1/21/2. The initialization of i w_i remains consistent with Equation˜5. With this design, the neurons in the second layer exhibit strong oscillations within a small range. The following lemma demonstrates the progressive diminishing under this algorithm. Lemma 4.4 (Progressively diminishing under simulation setup). Suppose ˜1 (A1-3, 5-6) holds (let m=1ηm= 1 η) and consider the update rule in Equations˜6 and 7, there exists a step t0≤1η2t_0≤ 1η^2 such that 444We simply denote x(t−1)i=0t−1∈D,ϵii=0t−1∼−σ,+σE_\x^(t-1)\_i=0^t-1∈ D,\ _i\_i=0^t-1 \-σ,+σ\ as E [1m∑i=1m‖i(t0)‖2]≤η. [ 1m _i=1^m\| w_i(t_0)\|^2]≤ η. (8) Insights into Lemma˜4.4. Lemma˜4.4 further confirms our key message that label noise SGD primarily contributes to the oscillation of the second layer, which induces the progressively diminishing phenomenon, ultimately leading to the transition from the lazy to the rich regime. Figure 3: Label noise SGD induces the rich regime. (a, b). Training ℒtrain((t))L_D_ train( θ(t)) and test loss ℒtest((t))L_D_ test( θ(t)) vs. training epochs t. Label noise SGD induces the progressively diminishing phenomenon. (c). The first-layer weight norm ‖(t)‖F\| W(t)\|_F vs. training epochs t. We use GD to train the models with NTK parameterization [25], both with and without label noise. We also train a linearized model with GD as baseline. Results are presented for WideResNets trained on a random subset of 64 images from CIFAR-10 due to the O(n2)O(n^2) computational complexity of NTK. 4.4 Phase I: Alignment and Convergence In this section, we present theoretical support for Phase I. When all the neurons satisfy ‖i‖,|ai|≤η\| w_i\|,|a_i|≤ η, we say that Phase I begins. This situation is analogous to small initialization [17, 50]. During this phase, the neurons in the first layer rapidly align with the ground-truth interpolator ⋆ θ . Notice that we consider gradient descent in Phase I for simplicity. This simplification maintains mathematical tractability without affecting our conclusion in Phase I. The following lemmas formalize our results in Phase I. Lemma 4.5 (Alignment). Suppose ˜1 (A1-3,5-6) holds and consider gradient descent for updates. Assume that phase I begins at time t1t_1, then at time t2=t1+T2t_2=t_1+T_2, T2=1‖⋆‖⋅ln(1η)T_2= 1\| θ \|· ( 1η), for any neuron i w_i it holds |⟨⋆,i(t2)⟩|‖⋆‖⋅‖i(t2)‖≥1−|O(ln1η⋅η)|. θ , w_i(t_2) \| θ \|·\| w_i(t_2)\|≥ 1- O( 1η· η) . (9) Lemma 4.6 (Convergence). Suppose ˜1 (A1-3, 5-6) holds and consider gradient descent for updates. Assume all the neurons are perfectly aligned at step t2t_2. Let t3=t2+1‖⋆‖2⋅ln(1/η)ηt_3=t_2+ 1\| θ \|^2· (1/η)η. Using gradient descent, we have ‖(t3)−⋆‖≤|O(η⋅ln1η)|\| θ(t_3)- θ \|≤|O(η· 1η)|. Furthermore, for any neuron ‖i(t3)‖≥η\| w_i(t_3)\|≥ η (i∈[m]i∈[m]), we have |⟨⋆,i(t3)⟩|‖⋆‖⋅‖i(t3)‖≥1−|O(η⋅ln1η)|. θ , w_i(t_3) \| θ \|·\| w_i(t_3)\|≥ 1- O(η· 1η) . (10) Insights from Lemmas˜4.5 and 4.6. Lemma˜4.5 indicates that the directions of each neuron rapidly align to a common direction, that of the ground-truth interpolator ⋆ θ . This alignment process is critical in Phase I, where the optimization shifts from the progressive diminishing phase to a more stable and efficient convergence towards the global minimum. Once perfect alignment is achieved, Lemma˜4.6 guarantees that after T3=O(−lnη)T_3=O( - η) steps, (t) θ(t) converges to the solution ⋆ θ . 4.5 Experiments: Synthetic and Real-World Setups In this section, we provide extensive empirical evidence support for our theory. The Two-phase picture under synthetic setups. The synthetic experiments precisely replicate the problem setup in Section˜4.1. In Figure˜2 (b), the averaged neuron norm 1m∑i=1m‖i(t)‖ 1m _i=1^m\| w_i(t)\| initially drops as t increases, suggesting the progressive diminishing phenomenon in Phase I. Afterwards, the averaged neuron alignment 1m∑i=1m⟨i(t),⋆⟩ 1m _i=1^m w_i(t), θ rapidly increases, implying the convergence to the global solution in Phase I. Additionally, in Figure˜2 (c) and (bottom), we visualize the dynamics of each neuron in the training process, where a clear two-phase pattern is observed. The transition from the lazy to rich regime under real-world setups. The real-world experiments are presented for WideResNets [51] trained on a small subset of CIFAR-10. Specifically, we compare the loss curves of models trained with and without label noise. We also train a linearized model without label noise as a baseline. In Figure˜3 (a) and (b), the model trained without label noise behaves similarly to its linearized counterparts, indicating the lazy regime; whereas the model trained with label noise follows a distinctly different training trajectory, suggesting the rich regime. Additionally, we also plot the evolution process of the first-layer weight norm ‖(t)‖\| W(t)\|. In Figure˜3 (c), when training with label noise, the first-layer weight norm notably decreases, especially compared to the case without label noise This result further validates our progressively diminishing phenomenon in real-world setups. Figure 4: Two-phase dynamics of SAM under synthetic setup. We replicate the synthetic problem setup from Section˜4.5, replacing label noise SGD with SAM. (a) Loss curves. Training ℒtrain((t))L_D_ train( θ(t)) and test loss ℒtest((t))L_D_ test( θ(t)) vs. training iteration t. (b) Learning dynamics on average. The averaged neuron norm Avgi∈[m](‖i(t)‖2)Avg_i∈[m](\| w_i(t)\|_2) and the averaged neuron alignment Avgi∈[m](⟨i(t),⋆⟩)Avg_i∈[m]( w_i(t), θ ) vs. training iteration t. (c) Learning dynamics of i-th neuron. The alignment of i-th neuron ⟨i(t),⋆⟩ w_i(t), θ vs. its weight norm ‖i(t)‖2\| w_i(t)\|_2, with darker points indicating larger iteration t. 5 Extension: From Label Noise SGD to SAM We conjecture that the principles governing label noise SGD also apply to broader optimization algorithms. In this section, we extend our findings from label noise SGD to SAM. Figure 5: SAM induces the rich regime. Training ℒtrain((t))L_D_ train( θ(t)) and test loss ℒtest((t))L_D_ test( θ(t)) vs. training epochs t. We use both GD and full-batch SAM to train the models with NTK parameterization [25]. We also train a linearized model with GD as baseline. Results are presented for WideResNets trained on a random subset of 64 images from CIFAR-10 due to the O(n2)O(n^2) computational complexity of NTK. Sharpness-Aware Minimization (SAM). SAM, introduced by Foret et al. [15], has substantially improved the generalization of neural networks. The core idea of SAM is to perform an inner adversarial gradient perturbation, followed by an outer gradient update. Its update rule is written as (t+1)=(t)−η∇ℓξt((t)+ρ∇ℓξt((t))‖∇ℓξt((t))‖2), θ(t+1)= θ(t)-η∇ _ _t ( θ(t)+ρ ∇ _ _t( θ(t))\|∇ _ _t( θ(t))\|_2 ), where ξt∈[n] _t∈[n] is the index sampled at iteration t and ρ is the perturbation radius. Recent works [42, 52] have shown that the effectiveness of SAM stems from its ability to amplify the stochastic noise inherent in SGD. As label noise SGD also benefits from additional noise, a natural question arises: Can our findings on label noise SGD extend to SAM? SAM exhibits the two-phase learning dynamics under synthetic setups. First, we focus on the exact dynamics of SAM on synthetic data. We conduct the synthetic experiments similar to previous sections except for replacing label noise SGD with SAM. In Figure˜4 (b), the norm of the first-layer weights W initially decreases, demonstrating the progressive diminishing phenomenon; subsequently, the alignment between W and ground-truth interpolator ⋆ θ increases, indicating an active feature learning process. Furthermore, in Figure˜4, we visualize the learning dynamics of a single neuron, evidently confirming that the two-phase picture holds for SAM. SAM promotes feature learning in practice. Second, we explore the properties of SAM in applications. As in phase I, we compare the loss curves of models trained with different strategies. In Figure˜5, the model trained with GD shows loss curves that closely align with its linearized approximations, a hallmark of the lazy regime. In contrast, training with SAM results in loss curves that deviate significantly from GD trajectories, signaling entry into the rich regime. In summary, SAM shows similar behaviors to label noise SGD across various setups, suggesting that the underlying ideology of label noise SGD is generalizable. 6 Conclusion and Outlook We present an in-depth study on the implicit regularization effect of label noise SGD from empirical observations to theoretical analysis. Notably, our theory demonstrates the surprising effect of label noise on the oscillation of the second layer, which induces the progressively diminishing phenomenon, leading to the transition from lazy to rich regime. Our theories are derived from a two-layer linear network. A future direction is to consider non-linear activation functions and study whether non-linearity influences the training dynamics. Besides, extending our theory to classification tasks remains an open challenge, which we will explore in future work. References [1] E. Abbe, E. Boix-Adsera, and T. Misiakiewicz (2023) SGD learning on neural networks: leap complexity and saddle-to-saddle dynamics. arXiv preprint arXiv:2302.11055. Cited by: §2. [2] Z. Allen-Zhu, Y. Li, and Z. Song (2019) A convergence theory for deep learning via over-parameterization. In Proceedings of the 36th International Conference on Machine Learning, Vol. 97, p. 242–252. Cited by: §1, §2, §4.1, §4.2. [3] S. Azulay, E. Moroshko, M. S. Nacson, B. E. Woodworth, N. Srebro, A. Globerson, and D. Soudry (2021) On the implicit bias of initialization shape: beyond infinitesimal mirror descent. In Proceedings of the 38th International Conference on Machine Learning, Vol. 139, p. 468–477. Cited by: §2. [4] J. Ba, M. A. Erdogdu, T. Suzuki, Z. Wang, D. Wu, and G. Yang (2022) High-dimensional asymptotics of feature learning: how one gradient step improves the representation. In Advances in Neural Information Processing Systems, Vol. 35. Cited by: §2. [5] G. Blanc, N. Gupta, G. Valiant, and P. Valiant (2020) Implicit regularization for deep neural networks driven by an ornstein-uhlenbeck like process. In Conference on learning theory, p. 483–513. Cited by: §1, §2. [6] E. Boursier, L. Pillaud-Vivien, and N. Flammarion (2022) Gradient flow dynamics of shallow relu networks for square loss and orthogonal inputs. In Advances in Neural Information Processing Systems, Vol. 35. Cited by: §2. [7] Y. Chen, Z. Zhou, and J. Yan (2024) Going beyond neural network feature similarity: the network feature complexity and its interpretation using category theory. In The Twelfth International Conference on Learning Representations, Cited by: Appendix D. [8] L. Chizat and F. Bach (2018) On the global convergence of gradient descent for over-parameterized models using optimal transport. In Advances in neural information processing systems, Vol. 31. Cited by: §2. [9] L. Chizat, E. Oyallon, and F. Bach (2019) On lazy training in differentiable programming. In Advances in Neural Information Processing Systems, Vol. 32, p. . Cited by: 1st item, §1, §2. [10] A. Damian, T. Ma, and J. D. Lee (2021) Label noise sgd provably prefers flat global minimizers. In Advances in Neural Information Processing Systems, Vol. 34, p. 27449–27461. Cited by: §1, §1, §2, §3, Algorithm 1. [11] E. Diao, G. Wang, J. Zhang, Y. Yang, J. Ding, and V. Tarokh (2023) Pruning deep neural networks from a sparsity perspective. In The Eleventh International Conference on Learning Representations, Cited by: Appendix D. [12] S. Du, J. Lee, H. Li, L. Wang, and X. Zhai (2019) Gradient descent finds global minima of deep neural networks. In Proceedings of the 36th International Conference on Machine Learning, Vol. 97, p. 1675–1685. Cited by: §1, §2, §4.2. [13] S. S. Du, X. Zhai, B. Poczos, and A. Singh (2019) Gradient descent provably optimizes over-parameterized neural networks. In International Conference on Learning Representations, Cited by: §1, §2, §4.2. [14] J. Eun Huh and P. Rebeschini (2024) Generalization bounds for label noise stochastic gradient descent. In Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, Vol. 238, p. 1360–1368. Cited by: §3. [15] P. Foret, A. Kleiner, H. Mobahi, and B. Neyshabur (2021) Sharpness-aware minimization for efficiently improving generalization. In International Conference on Learning Representations, Cited by: §1, §5. [16] J. Frankle and M. Carbin (2019) The lottery ticket hypothesis: finding sparse, trainable neural networks. In International Conference on Learning Representations, Cited by: Appendix D. [17] M. Geiger, S. Spigler, A. Jacot, and M. Wyart (2020) Disentangling feature and lazy training in deep neural networks. Journal of Statistical Mechanics: Theory and Experiment 2020 (11), p. 113301. Cited by: 1st item, §2, §4.4. [18] M. Hagiwara (1993) Removal of hidden units and weights for back propagation networks. In Proceedings of 1993 International Conference on Neural Networks (IJCNN-93-Nagoya, Japan), Vol. 1, p. 351–354 vol.1. Cited by: Appendix D. [19] A. Han, W. Huang, Z. Zhou, G. Niu, W. Chen, J. Yan, A. Takeda, and T. Suzuki (2025) On the role of label noise in the feature learning process. arXiv preprint arXiv:2505.18909. Cited by: §2. [20] S. Han, H. Mao, and W. J. Dally (2016) Deep compression: compressing deep neural networks with pruning, trained quantization and huffman coding. In International Conference on Learning Representations, Cited by: Appendix D. [21] J. Z. HaoChen, C. Wei, J. Lee, and T. Ma (2021) Shape matters: understanding the implicit bias of the noise covariance. In Proceedings of Thirty Fourth Conference on Learning Theory, Vol. 134, p. 2315–2357. Cited by: §1, §1, §2, §3, Algorithm 1. [22] K. He, X. Zhang, S. Ren, and J. Sun (2016) Deep residual learning for image recognition. In 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Vol. , p. 770–778. Cited by: Appendix D, Figure 1. [23] W. Huang, A. Han, Y. Song, Y. Chen, D. Wu, D. Zou, and T. Suzuki (2025) How does label noise gradient descent improve generalization in the low snr regime?. arXiv preprint arXiv:2510.17526. Cited by: §2. [24] J. E. Huh and P. Rebeschini (2024) Generalization bounds for label noise stochastic gradient descent. In International Conference on Artificial Intelligence and Statistics, p. 1360–1368. Cited by: §2. [25] A. Jacot, F. Gabriel, and C. Hongler (2018) Neural tangent kernel: convergence and generalization in neural networks. In Advances in Neural Information Processing Systems, Vol. 31, p. . Cited by: §2, Figure 3, §4.1, Figure 5. [26] A. Jacot, F. Ged, B. Simsek, C. Hongler, and F. Gabriel (2021) Saddle-to-saddle dynamics in deep linear networks: small initialization training, symmetry, and sparsity. arXiv preprint arXiv:2106.15933. Cited by: §2. [27] A. Jacot, E. Golikov, C. Hongler, and F. Gabriel (2022) Feature learning in L2L_2-regularized DNNs: attraction/repulsion and sparsity. In Advances in Neural Information Processing Systems, Vol. 35. Cited by: §2. [28] A. Krizhevsky, G. Hinton, et al. (2009) Learning multiple layers of features from tiny images. Note: https://w.cs.toronto.edu/˜kriz/learning-features-2009-TR.pdfAccessed: 2025-1-19 Cited by: Appendix D, Figure 1. [29] D. Kunin, A. Raventos, C. C. J. Domine, F. Chen, D. Klindt, A. M. Saxe, and S. Ganguli (2024) Get rich quick: exact solutions reveal how unbalanced initializations promote rapid feature learning. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, Cited by: §2. [30] A. Lewkowycz, Y. Bahri, E. Dyer, J. Sohl-Dickstein, and G. Gur-Ari (2020) The large learning rate phase of deep learning: the catapult mechanism. arXiv preprint arXiv:2003.02218. Cited by: §2. [31] A. Lewkowycz and G. Gur-Ari (2020) On the training dynamics of deep networks with l2 regularization. In Advances in Neural Information Processing Systems, Vol. 33, p. 4790–4799. Cited by: §2. [32] Y. Li and Y. Liang (2018) Learning overparameterized neural networks via stochastic gradient descent on structured data. In Advances in Neural Information Processing Systems, Vol. 31, p. . Cited by: §1. [33] Z. Li, Y. Luo, and K. Lyu (2020) Towards resolving the implicit bias of gradient descent for matrix factorization: greedy low-rank learning. arXiv preprint arXiv:2012.09839. Cited by: §2. [34] Z. Li, T. Wang, and S. Arora (2022) What happens after SGD reaches zero loss? –a mathematical framework. In International Conference on Learning Representations, Cited by: §1, §2, §3. [35] Y. H. Liu, A. Baratin, J. Cornford, S. Mihalas, E. T. SheaBrown, and G. Lajoie (2024) How connectivity structure shapes rich and lazy learning in neural circuits. In The Twelfth International Conference on Learning Representations, Cited by: §2. [36] T. Luo, Z. J. Xu, Z. Ma, and Y. Zhang (2021) Phase diagram for two-layer relu neural networks at infinite-width limit. The Journal of Machine Learning Research 22 (1), p. 3327–3373. Cited by: §2. [37] K. Lyu, J. Jin, Z. Li, S. S. Du, J. D. Lee, and W. Hu (2023) Dichotomy of early and late phase implicit biases can provably induce grokking. arXiv preprint arXiv:2311.18817. Cited by: §2. [38] K. Lyu, Z. Li, R. Wang, and S. Arora (2021) Gradient descent on two-layer nets: margin maximization and simplicity bias. In Advances in Neural Information Processing Systems, Vol. 34. Cited by: §2. [39] H. Maennel, O. Bousquet, and S. Gelly (2018) Gradient descent quantizes relu network features. arXiv preprint arXiv:1803.08367. Cited by: §2. [40] S. Mei, T. Misiakiewicz, and A. Montanari (2019) Mean-field theory of two-layers neural networks: dimension-free bounds and kernel limit. In Conference on Learning Theory, p. 2388–2464. Cited by: §2. [41] H. Min, E. Mallada, and R. Vidal (2023) Early neuron alignment in two-layer relu networks with small initialization. arXiv preprint arXiv:2307.12851. Cited by: §2. [42] E. Monzio Compagnoni, L. Biggio, A. Orvieto, F. N. Proske, H. Kersting, and A. Lucchi (2023) An SDE for modeling SAM: theory and insights. In Proceedings of the 40th International Conference on Machine Learning, Vol. 202, p. 25209–25253. Cited by: §5. [43] S. Pesme and N. Flammarion (2023) Saddle-to-saddle dynamics in diagonal linear networks. arXiv preprint arXiv:2304.00488. Cited by: §2. [44] C. J. Shallue, J. Lee, J. Antognini, J. Sohl-Dickstein, R. Frostig, and G. E. Dahl (2019) Measuring the effects of data parallelism on neural network training. Journal of Machine Learning Research 20 (112), p. 1–49. Cited by: §1. [45] S. Takakura and T. Suzuki (2024) Mean-field analysis on two-layer neural networks from a kernel perspective. In Forty-first International Conference on Machine Learning, Cited by: §2. [46] A. Varre, M. Sagitova, and N. Flammarion (2024) SGD vs gd: rank deficiency in linear networks. In Advances in Neural Information Processing Systems, Vol. 37, p. 60133–60161. Cited by: §2. [47] L. P. Vivien, J. Reygner, and N. Flammarion (2022) Label noise (stochastic) gradient descent implicitly solves the lasso for quadratic parametrisation. In Proceedings of Thirty Fifth Conference on Learning Theory, Vol. 178, p. 2127–2159. Cited by: §1, §2, §3. [48] M. Wang and C. Ma (2023) Understanding multi-phase optimization dynamics and rich nonlinear behaviors of relu networks. In Advances in Neural Information Processing Systems, Vol. 36. Cited by: §2. [49] Z. Wang and A. Jacot (2023) Implicit bias of sgd in L2L_2-regularized linear dnns: one-way jumps from high to low rank. arXiv preprint arXiv:2305.16038. Cited by: §1. [50] B. Woodworth, S. Gunasekar, J. D. Lee, E. Moroshko, P. Savarese, I. Golan, D. Soudry, and N. Srebro (2020) Kernel and rich regimes in overparametrized models. In Proceedings of Thirty Third Conference on Learning Theory, Vol. 125, p. 3635–3673. Cited by: §2, §4.4. [51] S. Zagoruyko and N. Komodakis (2016) Wide residual networks. arXiv preprint arXiv:1605.07146. Cited by: §4.5. [52] Z. Zhou, M. Wang, Y. Mao, B. Li, and J. Yan (2025) Sharpness-aware minimization efficiently selects flatter minima late in training. In The Thirteenth International Conference on Learning Representations, Cited by: §5. [53] D. Zou, Y. Cao, D. Zhou, and Q. Gu (2020) Gradient descent optimizes over-parameterized deep relu networks. Machine learning 109, p. 467–492. Cited by: §2. Appendix A Preliminaries A.1 Additional notations Complementary Event. Let A be an event. We use A¯ A to denote the complementary event of A. We have Pr[A]+Pr[A¯]=1Pr[A]+Pr[ A]=1. Definition A.1. (sub-exponential) A random variable X with mean μ=[X]μ=E[X] is sub-exponential if there are non-negative parameters (ν,b)(ν,b) such that [eλ(X−μ)]≤eν2λ22for all|λ|<1b.E[e^λ(X-μ)]≤ e ν^2λ^22 all |λ|< 1b. We denote X∈SE(ν,b)X∈ SE(ν,b). A.2 Preliminary lemmas Lemma A.2. Let X=∑i=1nXi2X= _i=1^nX_i^2 where Xi∼N(0,1)X_i N(0,1) and i.i.d. Then X∈SE(2n,4)X∈ SE(2 n,4). Corollary A.3. Let Z=∑i=1nXi⋅YiZ= _i=1^nX_i· Y_i where Xi,Yi∼N(0,1)X_i,Y_i N(0,1) and i.i.d. Then X∈SE(2n,4)X∈ SE(2 n,4). Proof of Corollary˜A.3. For every i∈[n]i∈[n]. we have [eλXi2−1] [e^λ X_i^2-1] =12π⋅∫−∞+∞e−λ(x2−1)⋅e−x2/2x = 1 2π· _-∞^+∞e^-λ(x^2-1)· e^-x^2/2dx =e−λ1−2λ = e^-λ 1-2λ And we have [eλXiYi] [e^λ X_iY_i] =∫−∞+∞∫−∞+∞eλxy⋅12πe−x22e−y22xy = _-∞^+∞ _-∞^+∞e^λ xy· 12πe^- x^22e^- y^22\,dx\,dy =∫−∞+∞∫−∞+∞12πe−(x−λy)22e−(1−λ2)y22xy = _-∞^+∞ _-∞^+∞ 12πe^- (x-λ y)^22e^- (1-λ^2)y^22\,dx\,dy =11−λ2∫−∞+∞∫−∞+∞12πe−x22e−y22xy = 1 1-λ^2 _-∞^+∞ _-∞^+∞ 12πe^- x^22e^- y^22\,dx\,dy =11−λ2≤[eλX2−1] = 1 1-λ^2 [e^λ X^2-1] So we have [eλZ]=[eλ∑i=1nXi⋅Yi]=[∏i=1neλXi⋅Yi]E[e^λ Z]=E[e^λ _i=1^nX_i· Y_i]=E[ _i=1^ne^λ X_i· Y_i] Since Xi⋅YiX_i· Y_i are independent, we have [∏i=1neλXi⋅Yi] [ _i=1^ne^λ X_i· Y_i] =∏i=1n[eλXi⋅Yi] = _i=1^nE[e^λ X_i· Y_i] ≤∏i=1n[eλXi2−1]=[eλX] ≤ _i=1^nE[e^λ X_i^2-1]=E[e^λ X] By lemma A.2, we have X=∑i=1nXi2∈SE(2n,4)X= _i=1^nX_i^2∈ SE(2 n,4). Therefore, we retain Z=∑i=1nXi⋅Yi∈SE(2n,4)Z= _i=1^nX_i· Y_i∈ SE(2 n,4). □ . Lemma A.4. (Sub-exponential tail bound) Suppose that X is sub-exponential with parameters (ν,b)(ν,b). Then Pr[X≥μ+t]≤exp(−t22ν2)if 0≤t≤ν2bPr[X≥μ+t]≤ (- t^22ν^2) 0≤ t≤ ν^2b (11) Lemma A.5. (Concentration of the norm) Let X=(X1,…,Xn)∈ℝnX=(X_1,…,X_n) ^n be a random vector with independent, sub-gaussian coordinates XiX_i that satisfy Xi2=1EX_i^2=1. Then Pr|∥X∥−n≥t|≤2exp(−ct2K4)for all t≥0Pr \ \|X\|- n≥ t \≤ 2 (- ct^2K^4 ) all t≥ 0 (12) where K=maxi‖Xi‖ψ2K= _i\|X_i\|_ _2 and c is an absolute constant. Lemma A.6. (Chernoff’s inequality) Let XiX_i be independent Bernoulli random variables with parameters pip_i. Consider their sum SN=∑i=1NXiS_N= _i=1^NX_i and denote its mean by μ=[SN]μ=E[S_N]. Then, for any t>μt>μ, we have ℙSN≤t≤e−μ(eμt)t.P\S_N≤ t\≤ e^-μ ( eμt )^t. (13) Appendix B Phase I: Progressively Diminishing and Escaping the Lazy Regime B.1 Step 1: Bounding aia_i Let ∇ℓ^ξt((t))=f((t);ξt)−yξt−ϵt∇ _ _t( θ(t))=f( θ(t); x_ _t)-y_ _t- _t. Using label noise SGD, for any i∈[m]i∈[m], the gradient at time step t is ∂ℓ^ξt((t))∂i⊤(t)=ai(t)(f((t);ξt)−yξt−ϵt)⋅ξt⊤ ∂ _ _t( θ(t))∂ w_i (t)=a_i(t)(f( θ(t); x_ _t)-y_ _t- _t)· x_ _t (14) ∂ℓ^ξt((t))∂ai(t)=(f((t);ξt)−yξt−ϵt)⋅ξt⊤⋅i(t) ∂ _ _t( θ(t))∂ a_i(t)=(f( θ(t); x_ _t)-y_ _t- _t)· x_ _t · w_i(t) (15) Then we retain (t+1)=(t)−η⋅(t)⋅(f((t);ξt)−yξt−ϵt)⋅ξt⊤ W(t+1)= W(t)-η· a(t)·(f( θ(t); x_ _t)-y_ _t- _t)· x_ _t (16) (t+1)=(t)−η⋅(f((t);ξt)−yξt−ϵt)⋅(t)⋅ξt a(t+1)= a(t)-η·(f( θ(t); x_ _t)-y_ _t- _t)· W(t)· x_ _t (17) The following Lemma˜B.1 provides a bound of the initialization of ‖i‖\| w_i\| at step 0. Lemma B.1. Let event B0=‖()‖≤1/4⋅m1/12for all i∈[m]B_0=\\| w_i(0)\|≤ 1/4· m^1/12\ for all $i∈[m]$\. Suppose ˜1 (A1) holds. Under NTK initialization as in Equation˜5, we have Pr[B0]≥1−O(1m)Pr[B_0]≥ 1-O( 1m). Proof. Notice that ()∼1dN(0,I) w_i(0) 1 dN(0,I), Let Z=d⋅()Z= d· w_i(0) and Z∼N(0,I)Z N(0,I). By Lemma˜A.5, we have Pr[|‖Z‖−d|≥18⋅m1/12]≤2exp(−c⋅m1/664Kw4)Pr[ \|Z\|- d ≥ 18· m^1/12]≤ 2 (- c· m^1/664K_w^4) (18) where KwK_w and c both are positive constant. Thus Pr[|‖(0)‖−1|≥m1/128d]≤2exp(−c⋅m1/664Kw4)Pr[ \| w_i(0)\|-1 ≥ m^1/128 d]≤ 2 (- c· m^1/664K_w^4) (19) Since 1≪m1 m and d≥1d≥ 1, we have Pr[‖(0)‖≥14⋅m1/12]≤2exp(−c⋅m1/664Kw4)Pr[\| w_i(0)\|≥ 14· m^1/12]≤ 2 (- c· m^1/664K_w^4) (20) Using union bound, we have Pr[B0¯]≤m⋅2exp(−c⋅m1/664Kw4)Pr[ B_0]≤ m· 2 (- c· m^1/664K_w^4) (21) Thus Pr[B0]≥1−m⋅2exp(−c⋅m1/664Kw4)≥1−1mPr[B_0]≥ 1-m· 2 (- c· m^1/664K_w^4)≥ 1- 1m (22) The last inequality holds under ˜1(A1). □ Lemma B.2. Suppose ˜1 (A1-2, 4-6) holds and consider the update rule in Equation˜3. Given the model is still in the lazy regime within T0=O(logmη2⋅m1/2)T_0=O( mη^2· m^1/2), with probability at least 1−O(1m)1-O( 1m), we have the following two propositions hold: (i). (Bound of Loss) For every t≤T0t≤ T_0, |∇ℓ^ξ0((t))|=O(m1/4) ∇ _ _0( θ(t)) =O(m^1/4). (i). (Bound of aia_i) For every t≤T0t≤ T_0, ai(t)≤m−1/4a_i(t)≤ m^-1/4. Proof. We prove by induction. When step t=0t=0, we first prove the (i) holds. When t=0t=0, for any i∈[m]i∈[m], let i(0)=1d(Xi1,Xi2,⋯,Xid) w_i(0)= 1 d(X_i1,X_i2,·s,X_id) , Xij∼(0,1)X_ij (0,1) and (0)=1m(Y1,Y2,⋯,Ym) a(0)= 1 m(Y_1,Y_2,·s,Y_m), Yi∼(0,1)Y_i (0,1). Let Zj=∑i=1mXij⋅YiZ_j= _i=1^mX_ij· Y_i where j∈[d]j∈[d]. For all i∈[m],j∈[d]i∈[m],j∈[d], Xij,YiX_ij,Y_i are independent, so we have [Zj]=[∑i=1mXijYi]=∑i=1m[XijYi]=∑i=1m[Xij][Yi]=0 [Z_j]=E[ _i=1^mX_ijY_i]= _i=1^mE[X_ijY_i]= _i=1^mE[X_ij]E[Y_i]=0 (23) and Var[Zj]=Var[∑i=1mXijYi]=∑i=1mVar[XijYi]=∑i=1mVar[Xij]Var[Yi]=m [Z_j]=Var[ _i=1^mX_ijY_i]= _i=1^mVar[X_ijY_i]= _i=1^mVar[X_ij]Var[Y_i]=m (24) By Corollary A.3, we have for any j∈[d]j∈[d], Zj=∑i=1mXij⋅Yi∈SE[2m,4]Z_j= _i=1^mX_ij· Y_i∈ SE[2 m,4]. By Lemma 11, let t=(8logm)/mt= (8 m)/m and we retain Pr(|Zj=∑i=1mXij⋅Yi|≥8logm⋅m) ( |Z_j= _i=1^mX_ij· Y_i |≥ 8 m· m ) ≤2exp(−(8logm⋅m)22⋅(2m)2) ≤ 2 (- ( 8 m· m)^22·(2 m)^2 ) =2m = 2m Using union bound, with probability at most 2dm 2dm, there exists j∈[d]j∈[d] such that |∑i=1mXij⋅Yi|≥8logm⋅m | _i=1^mX_ij· Y_i |≥ 8 m· m So with probability 1−2dm1- 2dm, |∑i=1mXij⋅Yi|≤8logm⋅mfor all j∈[d] | _i=1^mX_ij· Y_i |≤ 8 m· m all $j∈[d]$ (25) Then we have ‖(0)−∗‖ \| θ(0)- θ^*\| ≤‖(0)‖+‖∗‖ ≤\| θ(0)\|+\| θ^*\| =‖∑i=1mai(0)i(0)⊤‖+‖∗‖ =\| _i=1^ma_i(0) w_i(0) \|+\| θ^*\| =1d⋅1m∑j=1d(∑i=1mXijYi)2+‖∗‖ = 1 d· 1 m _j=1^d( _i=1^mX_ijY_i)^2+\| θ^*\| ≤1d⋅1m8⋅d⋅m⋅logm+m−1/4(by Inequality (25) and ˜1(A4)) ≤ 1 d· 1 m 8· d· m· m+m^-1/4 (by Inequality ( x_ijY_i) and @crefcreftype~refnumcond:main(A4)) ≤3logm ≤ 3 m So we have |∇ℓ^ξ0((0))| ∇ _ _0( θ(0)) =|(0)(0)ξ0−yξ0−ϵ0| = a(0) W(0) x_ _0-y_ _0- _0 ≤|(0)(0)ξ0−yξ0|+|ϵ0| ≤ a(0) W(0) x_ _0-y_ _0 + _0 ≤‖((0)−∗)‖⋅‖ξ0‖+σ ≤\|( θ(0)- θ^*)\|·\| x_ _0\|+σ ≤3logm⋅Cdata+σ ≤ 3 m· C_data+σ Therefore, with probability at least 1−2m1- 2m, we have |∇ℓ^ξ0((0))|=O(m1/4) ∇ _ _0( θ(0)) =O(m^1/4), so (i) holds when t=0t=0. Then we prove (i) holds at step 0. Let event Ct=|ai(t1)|≤m−1/4 for all t1≤t and for all i∈[m]C_t=\|a_i(t_1)|≤ m^-1/4\ for all $t_1≤ t$ and for all $i∈[m]$\. Since ai(0)∼1mN(0,1)a_i(0) 1 mN(0,1), we have Pr[|ai(0)|≥m−1/8]≤2exp(−c⋅m3/44Ka4)Pr[|a_i(0)|≥ m^-1/8]≤ 2 (- c· m^3/44K_a^4) (26) by Lemma˜A.5, where KaK_a and c are both positive constant. Using union bound, we have Pr[C0¯]≤m⋅2exp(−c⋅m3/44Ka4)⋅(1−3dm)Pr[ C_0]≤ m· 2 (- c· m^3/44K_a^4)·(1- 3dm) (27) Thus Pr[C0]=1−Pr[C0¯] [C_0]=1-Pr[ C_0] ≥1−m⋅2exp(−c⋅m3/44Ka4)⋅(1−3dm) ≥ 1-m· 2 (- c· m^3/44K_a^4)·(1- 3dm) ≥(1−1m)⋅(1−3dm) ≥(1- 1m)·(1- 3dm) ≥(1−4dm) ≥(1- 4dm) Since d is a constant, we have Pr[C0]≥1−O(1m)Pr[C_0]≥ 1-O( 1m) , which implies (i) holds when t=0t=0. Assuming the lemma holds at step t, we proceed to step t+1t+1 where we first establish property (i) by constructing a super-martingale, and subsequently demonstrate that property (i) also holds. By definition of online label noise SGD algorithm, xξt,ϵtx_ _t, _t are independent with (t) θ(t) , i(t) w_i(t) and has memorylessness property. Let ℱ0=σ(i(0),ai(0)for i ∈[m])F_0=σ( w_i(0),a_i(0)\ for i\ $∈[m]$). For t≥1t≥ 1, let ℱt=σ(ℱ0,ϵ(t),(t))F_t=σ(F_0,ε^(t), x^(t)). Here ϵ(t)ε^(t) denotes the set ϵ0,ϵ1,…,ϵt−1\ _0, _1,…, _t-1\ and (t) x^(t) denotes the set ξ0,ξ1,…,ξt−1\ x_ _0, x_ _1,…, x_ _t-1\. Obviously, we have ℱ0⊂ℱ1⊂⋯⊂ℱtF_0 _1⊂·s _t. Notice that [ξt⋅ξt⊤|ℱt]=IE[ x_ _t· x_ _t |F_t]=I and [ϵt|ℱt]=0E[ _t|F_t]=0. Additionally, in the lazy regime, for any i∈[d]i∈[d] at step t, every neuron holds ‖i(t)−i(0)‖≤1m\| w_i(t)- w_i(0)\|≤ 1 m. So we have [|ai(t+1)||ℱt] [ a_i(t+1) |F_t] =|ai(t)−η⋅[((t)−⋆)⋅(t)|ℱt]| = a_i(t)-η·E[( θ(t)- θ )· w_i(t)|F_t] =|ai(t)−η⋅[((t)⊤(t)−⋆)⋅(t)|ℱt]| = a_i(t)-η·E[( a(t) W(t)- θ )· w_i(t)|F_t] =|ai(t)−η⋅[(∑j=1mj(t)j(t)⊤−⋆)⋅(t)|ℱt]| = a_i(t)-η·E[( _j=1^m a_j(t) w_j(t) - θ )· w_i(t)|F_t] =|ai(t)−η⋅(∑j=1mj(t)[j(0)⊤⋅(0)])+η⋅⋆(0)+o(η/m)| = a_i(t)-η·( _j=1^m a_j(t)E[ w_j(0) · w_i(0)])+η· θ w_i(0)+o(η/ m) =|(1−η)⋅ai(t)+η⋅⋆(0)+o(η/m)| = (1-η)· a_i(t)+η· θ w_i(0)+o(η/ m) Let Yi(t)=|ai(t)−∗i(0)−o(1m)|Y_i(t)= a_i(t)- θ^* w_i(0)-o( 1 m) . Since [|ai(t+1)−∗i(0)−o(1m)||ℱt]=|(1−η)⋅(ai(t)−⋆i(0)−o(1m))|E[ a_i(t+1)- θ^* w_i(0)-o( 1 m) |F_t]= (1-η)·(a_i(t)- θ w_i(0)-o( 1 m)) (28) We have [Yi(t+1)|ℱt]=(1−η)⋅Yi(t)≤Yi(t)E[Y_i(t+1)|F_t]=(1-η)· Y_i(t)≤ Y_i(t) (29) Therefore, Yi(0),Yi(1),…,Yi(t)Y_i(0),Y_i(1),…,Y_i(t) are super-martingale. By Lemma˜B.1, with probability at least 1−O(1m)1-O( 1m), ‖i(0)‖≤m1/12\| w_i(0)\|≤ m^1/12 for all i∈[m]i∈[m]. Conditioned on ‖i(0)‖≤m1/12\| w_i(0)\|≤ m^1/12 and we have |Yi(t+1)−Yi(t)| Y_i(t+1)-Y_i(t) =||ai(t+1)−∗⋅i(0)−o(1m)|−|ai(t)−∗⋅i(0)−o(1m)|| = |a_i(t+1)- θ^*· w_i(0)-o( 1 m)|-|a_i(t)- θ^*· w_i(0)-o( 1 m)| ≤|ai(t+1)−ai(t)|+o(1m)(triangle inequality) ≤|a_i(t+1)-a_i(t)|+o( 1 m) (triangle inequality) =|η⋅(∇ℓ^ξt((t)))⋅ξt⊤⋅i(t)|+o(1m) =|η·(∇ _ _t( θ(t)))· x_ _t · w_i(t)|+o( 1 m) ≤η⋅|∇ℓ^ξt((t))|⋅‖⋅‖i(t)‖+o(1m) ≤η·|∇ _ _t( θ(t))|·\| x_ _t\|·\| w_i(t)\|+o( 1 m) ≤η⋅|∇ℓ^ξt((t))|⋅‖⋅(‖i(0)‖+1m)+o(1m)(in the lazy regime) ≤η·|∇ _ _t( θ(t))|·\| x_ _t\|·(\| w_i(0)\|+ 1 m)+o( 1 m) (in the lazy regime) ≤2η⋅|∇ℓ^ξt((t))|⋅Cdata⋅m1/12 ≤ 2η·|∇ _ _t( θ(t))|· C_data· m^1/12 With one-side Azuma’s inequality, for any λ>0λ>0, we have Pr[Yi(t+1)−Yi(0)>λ]≤exp(−λ2(t+1)⋅4η2⋅(Cdata⋅|∇ℓ^ξt((t))|⋅m1/12)2)Pr[Y_i(t+1)-Y_i(0)>λ]≤ (- λ^2(t+1)· 4η^2·(C_data·|∇ _ _t( θ(t))|· m^1/12)^2) (30) Thus Pr[|ai(t+1)|≥2⋅|∗⋅i(0)|+|ai(0)|+λ]≤exp(−λ2(t+1)⋅4η2⋅|∇ℓ^ξt((t))|⋅(Cdata⋅m1/12)2)Pr[|a_i(t+1)|≥ 2·| θ^*· w_i(0)|+|a_i(0)|+λ]≤ (- λ^2(t+1)· 4η^2·|∇ _ _t( θ(t))|·(C_data· m^1/12)^2) (31) By ˜1(A4), ‖∗‖≤1m1/3\| θ^*\|≤ 1m^1/3. Then we have |∗⋅i(0)|≤14m1/4| θ^*· w_i(0)|≤ 14m^1/4. Notice that Pr[|ai(0)|≥m−1/4]≤2exp(−c⋅m1/44Ka4)Pr[|a_i(0)|≥ m^-1/4]≤ 2 (- c· m^1/44K_a^4). Let λ=12m1/4λ= 12m^1/4, so with probability at least (1−2exp(−c⋅m1/44Ka4))⋅(1−3dm)(1-2 (- c· m^1/44K_a^4))·(1- 3dm), we have 2⋅|∗⋅wi(0)|+|wi(0)|+λ]≤12m1/4+14m1/4+14m1/4≤1m1/42·| θ^*· w_i(0)|+|w_i(0)|+λ]≤ 12m^1/4+ 14m^1/4+ 14m^1/4≤ 1m^1/4 by ˜1(A1). So we retain Pr[|ai(t+1)|≥m−1/4]≤exp(−m1/6(t+1)⋅8η2⋅(Cdata⋅|∇ℓ^ξt((t))|)2)⋅(1−3dm)Pr[|a_i(t+1)|≥ m^-1/4]≤ (- m^1/6(t+1)· 8η^2·(C_data·|∇ _ _t( θ(t))|)^2)·(1- 3dm) (32) By induction hypothesis, we have |∇ℓ^ξt((t))|=O(m1/4)|∇ _ _t( θ(t))|=O(m^1/4). Using union bound and by ˜1(A2), we have Pr[Ct¯] [ C_t] ≤∑j=0t−1exp(−m1/12j⋅8η2⋅(Cdata⋅O(m1/4))2)⋅(1−3dm) ≤ _j=0^t-1 (- m^1/12j· 8η^2·(C_data· O(m^1/4))^2)·(1- 3dm) ≤t⋅exp(−m1/12t⋅8η2⋅(Cdata⋅O(m1/4))2)⋅(1−3dm) ≤ t· (- m^1/12t· 8η^2·(C_data· O(m^1/4))^2)·(1- 3dm) ≤T0⋅exp(−η−1/12T0⋅8η2⋅(Cdata⋅O(m1/4))2)⋅(1−3dm) ≤ T_0· (- η^-1/12T_0· 8η^2·(C_data· O(m^1/4))^2)·(1- 3dm) ≤T0⋅exp(−η−1/12T0⋅8η2⋅(Cdata⋅O(m1/4))2)⋅(1−3dm) ≤ T_0· (- η^-1/12T_0· 8η^2·(C_data· O(m^1/4))^2)·(1- 3dm) =O(−lnη2)⋅exp(−η−1/12O(ln1η)⋅Cdata2⋅O(1))⋅(1−3dm) =O( - η^2)· (- η^-1/12O( 1η)· C_data^2· O(1))·(1- 3dm) ≤O(η)⋅(1−3dm)=O(1m) ≤ O(η)·(1- 3dm)=O( 1m) The last inequality is due to ˜1(A2). Therefore, we have Pr[Ct]≥1−O(1m)Pr[C_t]≥ 1-O( 1m), which implies (i) holds. Then we prove (i) holds. By Definition˜4.1, we have ‖i(t+1)−i(t)‖≤m−1/2\| w_i(t+1)- w_i(t)\|≤ m^-1/2. Therefore, with the bound of ai(t)a_i(t) holds, we retain ‖(t+1)‖≤‖(t)⊤⋅(t)‖≤‖(0)⊤⋅(0)‖+m−1/2⋅m−1/4⋅m=‖(0)‖+m1/4\| θ(t+1)\|≤\| a(t) · W(t)\|≤\| a(0) · W(0)\|+m^-1/2· m^-1/4· m=\| θ(0)\|+m^1/4 (33) Therefore, |∇ℓ^ξt((t+1))| ∇ _ _t( θ(t+1)) =|(t+1)(t+1)ξt+1−yξt+1−ϵt+1| = a(t+1) W(t+1) x_ _t+1-y_ _t+1- _t+1 ≤|(t+1)(t+1)ξt+1−yξt+1|+|ϵt+1| ≤ a(t+1) W(t+1) x_ _t+1-y_ _t+1 + _t+1 ≤‖((t+1)−∗)‖⋅‖ξt+1‖+σ ≤\|( θ(t+1)- θ^*)\|·\| x_ _t+1\|+σ ≤2(‖(0)‖+m1/4)⋅Cdata+σ ≤ 2(\| θ(0)\|+m^1/4)· C_data+σ =O(m1/4) =O(m^1/4) which implies (i) also holds at step t+1t+1. So it follows by induction that the lemma holds. □ B.2 Step 2: Estimating ΔWi W_i Let ∇ℓ^ξt((t))=f((t);ξt)−yξt−ϵt∇ _ _t( θ(t))=f( θ(t); x_ _t)-y_ _t- _t, by equ (14) and equ (15), we have i(t+1)=i(t)−η⋅ai(t)⋅∇ℓ^ξt((t))⋅ξt w_i(t+1)= w_i(t)-η· a_i(t)·∇ _ _t( θ(t))· x_ _t (34) ai(t+1)=ai(t)−η⋅∇ℓ^ξt((t))⋅ξt⊤⋅i(t) a_i(t+1)=a_i(t)-η·∇ _ _t( θ(t))· x_ _t · w_i(t) (35) According to equ (34), after taking the norm on both sides and then square them, we have: ‖i(t+1)‖2=‖i(t)‖2−2η⋅ai(t)∇ℓ^ξt((t))ξt⊤i(t)+‖η⋅ai(t)∇ℓ^ξt((t))ξt‖2\| w_i(t+1)\|^2=\| w_i(t)\|^2-2η· a_i(t)∇ _ _t( θ(t)) x_ _t w_i(t)+\|η· a_i(t)∇ _ _t( θ(t)) x_ _t\|^2 (36) According to equ (35), we have η⋅∇ℓ^ξt((t))⋅ξt⊤⋅i(t)=ai(t)−ai(t+1)η·∇ _ _t( θ(t))· x_ _t · w_i(t)=a_i(t)-a_i(t+1) (37) Substitute equ (37) into the equ (36) and we retain: ‖i(t+1)‖2=‖i(t)‖2−2⋅(ai(t)−ai(t+1))⋅ai(t)+‖η⋅ai(t)∇ℓ^ξt((t))xξt‖2\| w_i(t+1)\|^2=\| w_i(t)\|^2-2·(a_i(t)-a_i(t+1))· a_i(t)+\|η· a_i(t)∇ _ _t( θ(t))x_ _t\|^2 (38) For any time T∈ℕ+T ^+, summing up from 0 to T and we have: ‖i(T)‖2=‖i(0)‖2−2⋅∑j=0T−1(ai(j)−ai(j+1))⋅ai(j)+∑j=0T−1‖η⋅ai(j)⋅∇ℓ^ξj((j))⋅ξj‖2\| w_i(T)\|^2=\| w_i(0)\|^2-2· _j=0^T-1(a_i(j)-a_i(j+1))· a_i(j)+ _j=0^T-1\|η· a_i(j)·∇ _ _j( θ(j))· x_ _j\|^2 (39) Notice that 2⋅∑j=0T−1(ai(j)−ai(j+1))⋅ai(j) 2· _j=0^T-1(a_i(j)-a_i(j+1))· a_i(j) =∑j=0T−1(ai(j)2−2⋅ai(j)ai(j+1)+ai(j+1)2)+ai(0)2−ai(T)2 = _j=0^T-1(a_i(j)^2-2· a_i(j)a_i(j+1)+a_i(j+1)^2)+a_i(0)^2-a_i(T)^2 (40) =∑j=0T−1(ai(j)−ai(j))2+ai(0)2−ai(T)2 = _j=0^T-1(a_i(j)-a_i(j))^2+a_i(0)^2-a_i(T)^2 (41) Thus we have ‖i(T)‖2 \| w_i(T)\|^2 =‖i(0)‖2−∑j=0T−1(ai(j)−ai(j+1))2−ai(0)2+ai(T)2+∑j=0T−1‖η⋅i(j)⋅∇ℓ^ξj((j))⋅xξj‖2 =\| w_i(0)\|^2- _j=0^T-1(a_i(j)-a_i(j+1))^2-a_i(0)^2+a_i(T)^2+ _j=0^T-1\|η· w_i(j)·∇ _ _j( θ(j))· x_ _j\|^2 =‖i(0)‖2−∑j=0T−1(‖ai(j)−ai(j+1)‖2−‖i(j)−i(j+1)‖2)−ai(0)2+ai(T)2 =\| w_i(0)\|^2- _j=0^T-1(\|a_i(j)-a_i(j+1)\|^2-\| w_i(j)- w_i(j+1)\|^2)-a_i(0)^2+a_i(T)^2 =‖i(0)‖2−∑j=0T−1η2⋅∇ℓ^ξj((j))2(ξj⊤⋅i(j))2−ai(j)2⋅‖ξj‖2−ai(0)2+ai(T)2 =\| w_i(0)\|^2- _j=0^T-1η^2·∇ _ _j( θ(j))^2\( x_ _j · w_i(j))^2-a_i(j)^2·\| x_ _j\|^2\-a_i(0)^2+a_i(T)^2 Let ΔWi(j)=−∇ℓ^ξj((j))2⋅(ξj⊤⋅i(j))2−ai(j)2⋅‖ξj‖2 W_i(j)=-∇ _ _j( θ(j))^2·\( x_ _j · w_i(j))^2-a_i(j)^2·\| x_ _j\|^2\. Since ai(j)a_i(j) is small with high probability, ΔWi(j) W_i(j) almost dominates the change of ‖i‖2\| w_i\|^2 at every step. We have ‖i(T)‖2=‖i(0)‖2+η2⋅∑j=0T−1ΔWi(j)−ai(0)2+ai(T)2\| w_i(T)\|^2=\| w_i(0)\|^2+η^2· _j=0^T-1 W_i(j)-a_i(0)^2+a_i(T)^2 (42) Lemma B.3 (Progressively diminishing at each step). Suppose ˜1 (A1-2, 4-6) holds and consider the update rule in Equation˜3. Given the model is still under the lazy regime at step T, then with probability at least 1−O(1m)1-O( 1m), for all the iterative steps j≤T1j≤ T_1 and for every i∈[m]i∈[m]: 1. ΔWi(j)≤0 W_i(j)≤ 0 with probability at least 1−ρm1/81- ρm^1/8. 2. ΔWi(j)≤−(σ4)2 W_i(j)≤-( σ4)^2 with probability at least 14 14. 3. ΔWi(j)>0 W_i(j)>0 with probability at most ρm1/8 ρm^1/8. 4. ΔWi(j)≤O(1) W_i(j)≤ O(1). where ρ=2dπρ= 2 d π is a constant. Proof. By Lemma˜B.2 (i), with probability at least 1−O(1m)1-O( 1m), for all i∈[m]i∈[m] and all step t≤T1t≤ T_1, |ai(t)|≤1m1/4|a_i(t)|≤ 1m^1/4, i.e. the event CjC_j happens. All the "Pr" in this lemma conditioned on CjC_j. For each j<Tj<T, we have ΔWi(j)>0⇔(ξj⊤⋅i(j))2<ai(j)2⋅‖ξj‖2⇔(ξj⊤‖ξj‖⋅i(j))2<ai(j)2 W_i(j)>0 ( x_ _j · w_i(j))^2<a_i(j)^2·\| x_ _j\|^2 ( x_ _j \| x_ _j\|· w_i(j))^2<a_i(j)^2 i.e. |⊤⋅i(j)|<|ai(j)| x · w_i(j)|<|a_i(j) (43) where =ξj‖ξj‖ x= x_ _j\| x_ _j\| follows a uniform distribution on the n-dimensional unit sphere. Let x1x_1 denotes the element in the first dimension of x. By symmetry, we have Pr[|⊤⋅i(j)|<|ai(j)|]=Pr[−‖ai(j)‖i(j)‖<x1<‖ai(j)‖i(j)‖]Pr[ x · w_i(j)|<|a_i(j) ]=Pr[- \|a_i(j)\|\| w_i(j)\|<x_1< \|a_i(j)\|\| w_i(j)\|] (44) The density of x1x_1 is f(x1)=Γ(d2)πΓ(d−12)(1−x12)d−32f(x_1)= ( d2 ) π\, ( d-12 ) (1-x_1^2 ) d-32, where Γ denotes the gamma function. Then we have Pr[−‖ai(j)‖i(j)‖<x1<‖ai(j)‖i(j)‖] [- \|a_i(j)\|\| w_i(j)\|<x_1< \|a_i(j)\|\| w_i(j)\|] =∫x1=−‖ai(j)‖i(j)‖ai(j)‖i(j)‖f(x1)x1 = _x_1=- \|a_i(j)\|\| w_i(j)\| \|a_i(j)\|\| w_i(j)\|f(x_1)dx_1 =∫x1=−‖ai(j)‖i(j)‖ai(j)‖i(j)‖Γ(d2)πΓ(d−12)(1−x12)d−32x1 = _x_1=- \|a_i(j)\|\| w_i(j)\| \|a_i(j)\|\| w_i(j)\| ( d2 ) π\, ( d-12 ) (1-x_1^2 ) d-32dx_1 ≤∫x1=−‖ai(j)‖i(j)‖ai(j)‖i(j)‖Γ(d2)πΓ(d−12)x1 ≤ _x_1=- \|a_i(j)\|\| w_i(j)\| \|a_i(j)\|\| w_i(j)\| ( d2 ) π\, ( d-12 )dx_1 =2⋅‖ai(j)‖i(j)‖⋅Γ(d2)πΓ(d−12) =2· \|a_i(j)\|\| w_i(j)\|· ( d2 ) π\, ( d-12 ) ≤2dπ⋅‖aj(j)‖i(j)‖ ≤ 2 d π· \|a_j(j)\|\| w_i(j)\| ≤ρm1/8 ≤ ρm^1/8 The second-to-last inequality is because Γ(d2)Γ(d−12)≤d ( d2 ) ( d-12 )≤ d. So we retain ΔWi(j)≤0 W_i(j)≤ 0 with probability at least 1−ρm1/81- ρm^1/8 and ΔWi(j)>0 W_i(j)>0 with probability at most ρm1/8 ρm^1/8. By Lemma B.2 (i) , ∇ℓ^ξj((j))≤O(m1/4)∇ _ _j( θ(j))≤ O(m^1/4). So with ˜1A(5), ‖ξj‖≤Cdata\| x_ _j\|≤ C_data we have ΔWi(j) W_i(j) =−∇ℓ^ξj((j))2⋅(ξj⊤⋅i(j))2+∇ℓ^ξj((j))2⋅(ai(j)2⋅‖ξj‖2) =-∇ _ _j( θ(j))^2·( x_ _j · w_i(j))^2+∇ _ _j( θ(j))^2·(a_i(j)^2·\| x_ _j\|^2) ≤∇ℓ^ξj((j))2⋅(ai(j)2⋅‖ξj‖2) ≤∇ _ _j( θ(j))^2·(a_i(j)^2·\| x_ _j\|^2) ≤O(m1/4)2⋅Cdata2m1/2=O(1) ≤ O(m^1/4)^2· C_data^2m^1/2=O(1) Finally, we prove Pr[ΔWi(j)≤−(σ4)2]≥14Pr[ W_i(j)≤-( σ4)^2]≥ 14. We have Pr[ΔWi(j)≤−(σ4)2]=Pr[∇ℓ^ξj((j))2(ξj⊤⋅i(j))2−ai(j)2⋅‖ξj‖2≥(σ4)2] 0.8Pr[ W_i(j)≤-( σ4)^2]=Pr[∇ _ _j( θ(j))^2\( x_ _j · w_i(j))^2-a_i(j)^2·\| x_ _j\|^2\≥( σ4)^2] = Pr[∇ℓ^ξj((j))2(ξj⊤⋅i(j))2−ai(j)2⋅‖ξj‖2≥(σ4)2|ξj:|ξj⊤‖ξj‖⋅i(j)|<|ai(j)|]⋅Pr[|ξj⊤⋅i(j)|<|ai(j)|] = 0.5Pr[∇ _ _j( θ(j))^2\( x_ _j · w_i(j))^2-a_i(j)^2·\| x_ _j\|^2\≥( σ4)^2|\ x_ _j:| x_ _j \| x_ _j\|· w_i(j)|<|a_i(j)|]·Pr[| x_ _j · w_i(j)|<|a_i(j)|] + Pr[∇ℓ^ξj((j))2(ξj⊤⋅i(j))2−ai(j)2⋅∥ξj∥2≥(σ4)2|ξj:|ξj⊤‖ξj‖⋅i(j)|≥|ai(j)|]⋅Pr[|ξj⊤⋅i(j)|≥|ai(j)|] + 0.5Pr[∇ _ _j( θ(j))^2\( x_ _j · w_i(j))^2-a_i(j)^2·\| x_ _j\|^2≥( σ4)^2|\ x_ _j:| x_ _j \| x_ _j\|· w_i(j)|≥|a_i(j)|]·Pr[| x_ _j · w_i(j)|≥|a_i(j)|] ≥ Pr[∇ℓ^ξj((j))2(ξj⊤⋅i(j))2−ai(j)2⋅‖ξj‖2≥(σ4)2|ξj:|ξj⊤‖ξj‖⋅i(j)|≥|ai(j)|]⋅Pr[|ξj⊤⋅i(j)|≥|ai(j)|] ≥ 0.5Pr[∇ _ _j( θ(j))^2\( x_ _j · w_i(j))^2-a_i(j)^2·\| x_ _j\|^2\≥( σ4)^2|\ x_ _j:| x_ _j \| x_ _j\|· w_i(j)|≥|a_i(j)|]·Pr[| x_ _j · w_i(j)|≥|a_i(j)|] ≥ (1−ρm1/8)⋅Pr[∇ℓ^ξj((j))2(ξj⊤⋅i(j))2−ai(j)2⋅‖ξj‖2≥(σ4)2|ξj:|ξj⊤‖ξj‖⋅i(j)|≥|ai(j)|] ≥ 0.7(1- ρm^1/8)·Pr[∇ _ _j( θ(j))^2\( x_ _j · w_i(j))^2-a_i(j)^2·\| x_ _j\|^2\≥\ ( σ4)^2|\ x_ _j\ :| x_ _j \| x_ _j\|· w_i(j)|≥|a_i(j)|] Since ∇ℓ^ξj((j))2=(((j)−∗)ξj−ϵj)2∇ _ _j( θ(j))^2=(( θ(j)- θ^*) x_ _j- _j)^2 and ϵj _j is chosen uniformly,the probability that ((j)−∗)ξj( θ(j)- θ^*) x_ _j and ϵj _j have the same sign is at least 12 12. If the two elements have the same sign, then ∇ℓ^ξj((j))2≥σ2∇ _ _j( θ(j))^2≥σ^2. So we have Pr[∇ℓ^ξj((j))2(ξj⊤⋅i(j))2−ai(j)2⋅∥ξj∥2≥(σ4)2|ξjs.t.|ξj⊤‖ξj‖⋅i(j)|≥|ai(j)|] [∇ _ _j( θ(j))^2\( x_ _j · w_i(j))^2-a_i(j)^2·\| x_ _j\|^2\≥\ ( σ4)^2|\ x_ _j\ \ s.t.\ \ | x_ _j \| x_ _j\|· w_i(j)|≥|a_i(j)|] ≥12⋅Pr[(ξj⊤⋅i(j))2−ai(j)2⋅∥ξj∥2≥(14)2|ξjs.t.|ξj⊤‖ξj‖⋅i(j)|≥|ai(j)|] ≥ 12·Pr[\( x_ _j · w_i(j))^2-a_i(j)^2·\| x_ _j\|^2\≥( 14)^2|\ x_ _j\ \ s.t.\ \ | x_ _j \| x_ _j\|· w_i(j)|≥|a_i(j)|] ≥12⋅Pr[(ξj⊤⋅i(j))2−1m1/4⋅∥ξj∥2≥(14)2|ξjs.t.|ξj⊤‖ξj‖⋅i(j)|≥|ai(j)|](ai(j)2≤m1/4) ≥ 12·Pr[\( x_ _j · w_i(j))^2- 1m^1/4·\| x_ _j\|^2\≥( 14)^2|\ x_ _j\ \ s.t.\ \ | x_ _j \| x_ _j\|· w_i(j)|≥|a_i(j)|] ($a_i(j)^2≤ m^1/4$) =12⋅Pr[|ξj⊤‖ξj‖⋅i(j)|≥(14⋅‖ξj‖)2+1m1/4|ξjs.t.|ξj⊤‖ξj‖⋅i(j)|≥|ai(j)|] = 12·Pr[ x_ _j \| x_ _j\|· w_i(j) ≥ ( 14·\| x_ _j\|)^2+ 1m^1/4|\ x_ _j\ \ s.t.\ \ | x_ _j \| x_ _j\|· w_i(j)|≥|a_i(j)|] =12⋅Pr[|ξj⊤‖ξj‖⋅i(j)|≥(14⋅‖ξj‖)2+1m1/4](|ai(j)|≤1m1/8≤1‖ξj‖2+1m1/4) = 12·Pr[ x_ _j \| x_ _j\|· w_i(j) ≥ ( 14·\| x_ _j\|)^2+ 1m^1/4\ ] (|a_i(j)|≤ 1m^1/8≤ 1\| x_ _j\|^2+ 1m^1/4\ ) ≥12⋅Pr[|ξj⊤‖ξj‖⋅i(j)|≥(14⋅‖ξj‖)2⋅32] ≥ 12·Pr[ x_ _j \| x_ _j\|· w_i(j) ≥ ( 14·\| x_ _j\|)^2· 32\ ] By ˜1A(6), we have Pr[|‖i‖−d|≥d3]≤2exp(−4⋅c⋅d9K4)≤12Pr[ \| x_i\|- d ≥ d3]≤ 2 (- 4· c· d9K^4)≤ 12 (45) which implies Pr[‖ξj‖≥23d]≥23Pr[\| x_ _j\|≥ 23 d]≥ 23. So we have Pr[|ξj⊤‖ξj‖⋅i(j)|≥(14⋅‖ξj‖)2⋅32] [ x_ _j \| x_ _j\|· w_i(j) ≥ ( 14·\| x_ _j\|)^2· 32\ ] ≥Pr[|ξj⊤‖ξj‖⋅i(j)|≥32d⋅14⋅‖ξj‖] [ x_ _j \| x_ _j\|· w_i(j) ≥ 32 d· 14·\| x_ _j\|] =1−Pr[|ξj⊤‖ξj‖⋅i(j)|≤38d] =1-Pr[ x_ _j \| x_ _j\|· w_i(j) ≤ 38 d] ≥1−ρ⋅38d ≥ 1-ρ· 38 d =1−2dπ⋅38d=1−34π =1- 2 d π· 38 d=1- 34 π By ˜1(A1), m≥((1−34π)⋅ρ/(12−34π))8m≥((1- 34 π)·ρ/( 12- 34 π))^8. Therefore, we have Pr[ΔWi(j)≤−(σ4)2] [ W_i(j)≤-( σ4)^2] ≥(1−ρm1/8)⋅12⋅(1−34π) ≥(1- ρm^1/8)· 12·(1- 34 π) =14+12⋅((12−34π)−(1−34π)⋅ρm1/8) = 14+ 12·(( 12- 34 π)-(1- 34 π)· ρm^1/8) ≥14 ≥ 14 which completes the proof. □ Theorem B.4 (Escaping the lazy regime). Suppose ˜1 (A1-2, 4-6) holds and consider the update rule in Equation˜3. With probability at least 1−O(1m)1-O( 1m), all the neurons i w_i (i∈[m]i∈[m]) escape from the lazy regime at time T1=384logmσ2η2mT_1= 384 mσ^2η^2 m. Proof. Let event Ct=|ai(t1)|≤m−1/4 for all t1≤t and for all i∈[m]C_t=\|a_i(t_1)|≤ m^-1/4\ for all $t_1≤ t$ and for all $i∈[m]$\. By Lemma˜B.2 (i), with probability at least 1−O(1m)1-O( 1m), the event CT1C_T_1 happens. We assume CT1C_T_1 happens and all the "Pr" in this theorem conditioned on CjC_j. In the following, we will provide a proof by contradiction. Assume with probability at least O(1m)O( 1m), there exists some neurons i w_i (i∈[m]i∈[m]) s.t. ‖i(t)−i(0)‖≤1m\| w_i(t)- w_i(0)\|≤ 1 m holds for all T1T_1 steps. By Lemma˜A.5, we have Pr|∥i(0)∥−2logm≥t|≤2exp(−c⋅logmk4)=O(1m)Pr \ \| w_i(0)\|- 2 m≥ t \≤ 2 (- c· mk^4 )=O( 1m) (46) where k and c is an absolute constant. Using union bound, with probability at least 1−O(1m)1-O( 1m), for these neurons stuck in the lazy regime, ‖i(0)‖≤2logm\| w_i(0)\|≤ 2 m. We view ΔWi(j) W_i(j) as a random variable. We use Ω to denote the whole sample space. Let event Ωi=ω∈Ω|ΔWi(j)(ω)≤−(σ4)2 _i=\ω∈ \ | W_i(j)(ω)≤-( σ4)^2\ For any ω∈Ωω∈ , by Lemma˜B.3, we have Pr[Ωi]≥14Pr[ _i]≥ 14. Since the event CT1C_T_1 happens and i w_i stays in the lazy regime, the estimation of the lower bound of ΔWi(j) W_i(j) only depends on the randomness of ξj x_ _j. Thus, there exists a subset of Ωi _i we denote Θi _i such that Θi=ω∈Ωi|ΔWi(ω)≤−(σ/4)2,‖i(j)−i(0)‖≤1m,|ai(j)|≤1/m1/8 _i=\ω∈ _i| W_i(ω)≤-(σ/4)^2,$\| w_i(j)- w_i(0)\|≤ 1 m,|a_i(j)|≤ 1/m^1/8$\ and Pr[Θi]=14Pr[ _i]= 14. For Θi _i (i∈[T1−1]i∈[T_1-1]), the random randomness only depends on ξt x_ _t. Therefore, Θ0,Θ1,⋯,ΘT1−1 _0, _1,·s, _T_1-1 are mutual independent events. Then we define indicator random variable X0,X1,⋯,XT1−1X_0,X_1,·s,X_T_1-1 as follow: for every ω∈Ωω∈ , for any j∈[T1−1]j∈[T_1-1], Xj(ω)=1if ω∈Θi.0otherwise.X_j(ω)= \ array[]l1 $ω∈ _i$.\\ 0 .\\ array . So we have X0,X1,⋯,XT1−1X_0,X_1,·s,X_T_1-1 are independent and Pr[Xj(ω)=1]=14Pr[X_j(ω)=1]= 14. And we have [∑j=0T1−1Xj]=∑j=0T1−1[Xj]=T14E[ _j=0^T_1-1X_j]= _j=0^T_1-1E[X_j]= T_14 (47) Then we have Pr[η2⋅∑j=0T1−1ΔWi(j)≤−22logm] [η^2· _j=0^T_1-1 W_i(j)≤ -2 2 m m] =Pr[η2⋅(∑j=0T1−1ΔWi(j)⋅[ΔWi(j)>0]+∑j=0T1−1ΔWi(j)⋅[ΔWi(j)≤0])≤−22logm] =Pr[η^2·( _j=0^T_1-1 W_i(j)·I[ W_i(j)>0]+ _j=0^T_1-1 W_i(j)·I[ W_i(j)≤ 0])≤ -2 2 m m] ≥Pr[η2⋅(∑j=0T1−1ΔWi(j)⋅O(1m1/8)+∑j=0T1−1ΔWi(j)⋅[ΔWi(j)≤−(σ4)2])≤−22logm] [η^2·( _j=0^T_1-1 W_i(j)· O( 1m^1/8)+ _j=0^T_1-1 W_i(j)·I[ W_i(j)≤-( σ4)^2])≤ -2 2 m m] ≥Pr[η2⋅T1⋅O(1)⋅O(1m1/8)−η2⋅(σ4)2∑j=0T−1Xj≤−22logm] [η^2· T_1· O(1)· O( 1m^1/8)-η^2·( σ4)^2 _j=0^T-1X_j≤ -2 2 m m] =Pr[−η2⋅(σ4)2⋅∑j=0T1−1Xj≤−22logm−o(1m)](T1⋅η2=O(1m)) =Pr[-η^2·( σ4)^2· _j=0^T_1-1X_j≤ -2 2 m m-o( 1 m)] ($T_1·η^2=O( 1 m$)) ≥Pr[−η2⋅(σ4)2⋅∑j=0T1−1Xj≤−3logm] [-η^2·( σ4)^2· _j=0^T_1-1X_j≤- 3 m m] =Pr[∑j=0T1−1Xi≥48logmσ2η2m]=Pr[∑j=0T1−1Xi≥T18] =Pr[ _j=0^T_1-1X_i≥ 48 mσ^2η^2 m]=Pr[ _j=0^T_1-1X_i≥ T_18] ≥1−exp(−T14)⋅(e⋅T1/4T1/8)T1/8=1−(2e)T1/8 ≥ 1- (- T_14)·( e· T_1/4T_1/8)^T_1/8=1-( 2e)^T_1/8 The last inequality is by Equation˜13. Since T1=1η2⋅m≫mT_1= 1η^2· m m and ai(T)2≤1ma_i(T)^2≤ 1 m, with probability at least (1−O(1m))⋅(1−(2e)T1/8)=1−O(1m)(1-O( 1m))·(1-( 2e)^T_1/8)=1-O( 1m), we have ‖i(T)‖2−‖i(0)‖2 \| w_i(T)\|^2-\| w_i(0)\|^2 =η2⋅∑j=0T−1ΔWi(j)−ai(0)2+ai(T)2 =η^2· _j=0^T-1 W_i(j)-a_i(0)^2+a_i(T)^2 ≤η2⋅∑j=0T−1ΔWi(j)+1m ≤η^2· _j=0^T-1 W_i(j)+ 1 m ≤−22logm+1m≤−2logm ≤-2 2 m m+ 1 m≤- 2 m m Thus ‖i(T)‖−‖i(0)‖ \| w_i(T)\|-\| w_i(0)\| ≤−2logm⋅1‖i(T)‖+‖i(0)‖ ≤- 2 m m· 1\| w_i(T)\|+\| w_i(0)\| ≤−2logm⋅11m+2logm ≤- 2 m m· 1 1 m+ 2 m <−2logm⋅12logm=−1m <- 2 m m· 12 m=- 1 m Which is a contradiction to the definition of lazy regime! Therefore, we complete the proof. □ B.3 Algorithm 2: oscillation of the second layer within low range We design a new update rule as follow: for every neuron i w_i and aia_i at step t, we have i(t+1)=i(t)−η⋅ai(t)⋅1n∑i=1n((t)⊤(t)i−yi)⋅i w_i(t+1)= w_i(t)-η· a_i(t)· 1n _i=1^n( a(t) W(t) x_i-y_i)· x_i (48) ai(t+1)=ai(t)+δi(t) a_i(t+1)=a_i(t)+ _i(t) (49) where δi(t)=−η0.25if ai(t)=η0.25η0.25if ai(t)=−η0.25∼−η0.25,η0.25if ai(t)=0 _i(t)= \ aligned &-η^0.25 $a_i(t)=η^0.25$\\ &η^0.25 $a_i(t)=-η^0.25$\\ &$ \-η^0.25,η^0.25\$\ \ \ \ if $a_i(t)=0$ aligned . (50) Besides, we design a new initialization for a: for every i∈[m]i∈[m], we have ai(0)=−η0.25with probability 1/4η0.25with probability 1/40with probability 1/2a_i(0)= \ aligned &-η^0.25 probability 1/4\\ &η^0.25\ probability 1/4\\ &0 \ \ \ with probability 1/2 aligned . (51) Notice that ai(0)a_i(0) follows the stationary distribution. Since the transition matrix of aia_i is Q=[01012012010]Q= bmatrix0&1&0\\ 12&0& 12\\ 0&1&0\\ bmatrix it is easy to verify that [1/4,1/2,1/4]=[1/4,1/2,1/4]⋅Q[1/4,1/2,1/4]=[1/4,1/2,1/4]· Q. Thus by large number law, we can approximate ‖(t)‖2\| a(t)\|^2 by ‖(t)‖2=∑i=1m|ai(t)|2=m⋅[|ai(t)|2]=m⋅η0.52\| a(t)\|^2= _i=1^m|a_i(t)|^2=m·E[|a_i(t)|^2]= m·η^0.52 (52) Lemma B.5. Using algorithm 2, we have [(t)]=[(0)]E[ θ(t)]=E[ θ(0)] (53) Proof. Notice that (t+1)=(t+1)−η⋅(t)⋅1n∑i=1n((t)⊤(t)−yi)⋅⊤ W(t+1)= W(t+1)-η· a(t)· 1n _i=1^n( a(t) W(t) x_i-y_i)· x_i (54) (t+1)=(t)+(t)⊤ a(t+1)= a(t)+ δ(t) (55) Where (t)=[δ1(t),δ2(t),⋯,δm(t)]⊤ δ(t)=[ _1(t), _2(t),·s, _m(t)] . Notice that (t+1)⊤⋅(t)=0 a(t+1) · a(t)=0, then we have (t+1) θ(t+1) =(t+1)⊤⋅(t+1) = a(t+1) · W(t+1) (56) =((t)⊤+(t))⋅((t)−η⋅(t)⋅1n∑i=1n((t)⊤(t)i−yi)⋅i⊤) =( a(t) + δ(t))·( W(t)-η· a(t)· 1n _i=1^n( a(t) W(t) x_i-y_i)· x_i ) (57) =(t)+(t)⋅(t)−((t+1)⊤⋅(t))⋅η⋅1n∑i=1n((t)⊤(t)i−yi)⋅i⊤ = θ(t)+ δ(t)· W(t)-( a(t+1) · a(t))·η· 1n _i=1^n( a(t) W(t) x_i-y_i)· x_i (58) =(t)+(t)⋅(t) = θ(t)+ δ(t)· W(t) (59) Since [(t)]=E[ δ(t)]= 0, we have [(t)] [ θ(t)] =[(0)] =E[ θ(0)] B.4 Progressive diminishing of norm using Algorithm 2 Since i∼N(0,I) x_i N(0,I) i.i.d, by law of large numbers, 1n∑i=1ni⋅i⊤ 1n _i=1^n x_i· x_i is approximately to [i⋅i⊤]=IE[ x_i· x_i ]=I. So we have (t+1)=(t)−η⋅ai(t)⋅((t)−∗)⊤ w_i(t+1)= w_i(t)-η· a_i(t)·( θ(t)- θ^*) (60) ai(t+1)=ai(t)+δi(t) a_i(t+1)=a_i(t)+ _i(t) (61) Square both sides of the equation and we have ‖i(t+1)‖2=‖i(t)‖2−2η⋅ai(t)⋅((t)−∗)⊤⋅i(t+1)+η2⋅ai(t)2⋅‖(t)−∗‖2 \| w_i(t+1)\|^2=\| w_i(t)\|^2-2η· a_i(t)·( θ(t)- θ^*) · w_i(t+1)+η^2· a_i(t)^2·\| θ(t)- θ^*\|^2 (62) Since |ai(t)|≤η0.25|a_i(t)|≤η^0.25, we have 1m∑i=1m‖i(t+1)‖2 1m _i=1^m\| w_i(t+1)\|^2 =1m∑i=1m‖i(t)‖2−2η⋅((t)−∗)⊤⋅1m∑i=1mai(t)i(t)+η2⋅1m∑i=1mai(t)2‖(t)−∗‖2 = 1m _i=1^m\| w_i(t)\|^2-2η·( θ(t)- θ^*) · 1m _i=1^ma_i(t) w_i(t)+η^2· 1m _i=1^ma_i(t)^2\| θ(t)- θ^*\|^2 (63) =1m∑i=1m‖i(t)‖2−2η⋅1m⋅((t)−∗)⊤⋅(t)+η2⋅1m∑i=1mai(t)2‖(t)−∗‖2 = 1m _i=1^m\| w_i(t)\|^2-2η· 1m·( θ(t)- θ^*) · θ(t)+η^2· 1m _i=1^ma_i(t)^2\| θ(t)- θ^*\|^2 (64) ≤1m∑i=1m‖i(t)‖2−2η⋅1m⋅((t)−∗)⊤⋅(t)+η2⋅(η0.25)2‖(t)−∗‖2 ≤ 1m _i=1^m\| w_i(t)\|^2-2η· 1m·( θ(t)- θ^*) · θ(t)+η^2·(η^0.25)^2\| θ(t)- θ^*\|^2 (65) =1m∑i=1m‖i(t)‖2−(2ηm−η2.5)‖((t)−∗)‖2−2ηm⋅((t)−∗)⊤⋅∗ = 1m _i=1^m\| w_i(t)\|^2-( 2ηm-η^2.5)\|( θ(t)- θ^*)\|^2- 2ηm·( θ(t)- θ^*) · θ^* (66) Lemma B.6. If we set ai(0)a_i(0) to stationary distribution, then for any t,k∈+t,k ^+, we have [δi(t)⋅δi(t+k)]=−η0.52if k=10if k>1E[ _i(t)· _i(t+k)]= \ aligned &- η^0.52 $k=1$\\ &0 $k>1$ aligned . (68) Proof. Without loss of generality, assume we know that δi(t)=η0.25 _i(t)=η^0.25, then the distribution changes to (0,12,12)(0, 12, 12). So we have [δi(t)⋅δi(t+1)]=12⋅η0.25⋅(−η0.25)+12⋅0=−η0.52E[ _i(t)· _i(t+1)]= 12·η^0.25·(-η^0.25)+ 12· 0=- η^0.52 Then just after that, the distribution changes from (0,12,12)(0, 12, 12) to stationary distribution (14,12,14)( 14, 12, 14) again. Thus for any k>1k>1 we have [δi(t)⋅δi(t+k)]=0E[ _i(t)· _i(t+k)]=0 Lemma B.7 (Progressively diminishing under simulation setup). Suppose ˜1 (A1-3, 5-6) holds (let m=1ηm= 1 η) and consider the update rule in Equations˜48 and 49, there exists a step t0≤1η2t_0≤ 1η^2 such that [1m∑i=1m‖i(t0)‖2]≤ηE[ 1m _i=1^m\| w_i(t_0)\|^2]≤ η (69) Proof. Firstly, we give a lower bound of [‖(t)−∗‖2]E[\| θ(t)- θ^*\|^2], which shows the decrease of each step. According to equ (59), we retain (t)−∗=(0)−∗+∑i=0t−1(i)⋅(i) θ(t)- θ^*= θ(0)- θ^*+ _i=0^t-1 δ(i)· W(i) (70) And Since [(i)]=0E[ δ(i)]=0, we have [((0)−∗)⋅∑i=0t−1(i)⋅(i)]=[(i)]⋅[((0)−∗)⋅∑i=0t−1(i)]=0E[( θ(0)- θ^*)· _i=0^t-1 δ(i)· W(i)]=E[ δ(i)]·E[( θ(0)- θ^*)· _i=0^t-1 W(i)]=0 (71) So we have [‖((t)−∗)‖2]=[‖((0)−∗)‖2]+(η0.25)2⋅∑i=0t−1[‖(i)‖2]+2∑i=0t−1∑j<i[((i)(i))⋅((j)(j))⊤]E[\|( θ(t)- θ^*)\|^2]=E[\|( θ(0)- θ^*)\|^2]+(η^0.25)^2· _i=0^t-1E[\| W(i)\|^2]+2 _i=0^t-1 _j<iE[( δ(i) W(i))·( δ(j) W(j)) ]\\ (72) Notice that [((i)(i))⋅((i+1)(i+1)⊤] [( δ(i) W(i))·( δ(i+1) W(i+1) ] =[(i)((i)(i+1)⊤)(i+1)⊤] =E[ δ(i)( W(i) W(i+1) ) δ(i+1) ] =∑1≤l,r≤m[δl(i)δr(i+1)⋅((i)(i+1)⊤)[l,r]] = _1≤ l,r≤ mE[ _l(i) _r(i+1)·( W(i) W(i+1) )[l,r]] =∑1≤l,r≤m[δl(i)δr(i+1)⋅l(i)⊤r(i+1)] = _1≤ l,r≤ mE[ _l(i) _r(i+1)· w_l(i) w_r(i+1)] Case 1: r≠lr≠ l. In this case, δl _l are independent with δr _r. So we have [δl(i)δr(i+1)⋅l(i)⊤r(i+1)] [ _l(i) _r(i+1)· w_l(i) w_r(i+1)] =[δl(i)δr(i+1)⋅l(i)⊤(r(i)−η⋅ar(i)⋅((i)−∗)⊤] =E[ _l(i) _r(i+1)· w_l(i) ( w_r(i)-η· a_r(i)·( θ(i)- θ^*) ] =[δl(i)δr(i+1)⋅l(i)⊤r(i)]−[δl(i)δr(i+1)⋅l(i)⊤η⋅ar(i)⋅((i)−∗)⊤] =E[ _l(i) _r(i+1)· w_l(i) w_r(i)]-E[ _l(i) _r(i+1)· w_l(i) η· a_r(i)·( θ(i)- θ^*) ] =[δl(i)]⋅[δr(i+1)⋅l(i)⊤r(i)]−[δl(i)]⋅[δr(i+1)⋅l(i)⊤η⋅ar(i)⋅((i)−∗)⊤] =E[ _l(i)]·E[ _r(i+1)· w_l(i) w_r(i)]-E[ _l(i)]·E[ _r(i+1)· w_l(i) η· a_r(i)·( θ(i)- θ^*) ] =0 =0 Case 2: r=lr=l, by Lemma 68, we have [δl(i)δl(i+1)⋅l(i)⊤l(i+1)] [ _l(i) _l(i+1)· w_l(i) w_l(i+1)] =[δl(i)δl(i+1)⋅l(i)⊤(l(i)−η⋅al(i)⋅((i)−∗)⊤)] =E[ _l(i) _l(i+1)· w_l(i) ( w_l(i)-η· a_l(i)·( θ(i)- θ^*) )] =[δl(i)δl(i+1)⋅l(i)⊤l(i)]−[δl(i)δl(i+1)⋅l(i)⊤η⋅al(i)⋅((i)−∗)⊤] =E[ _l(i) _l(i+1)· w_l(i) w_l(i)]-E[ _l(i) _l(i+1)· w_l(i) η· a_l(i)·( θ(i)- θ^*) ] =[δl(i)δl(i+1)]⋅[‖l(i)‖2]−[δl(i)δl(i+1)⋅l(i)⊤η⋅al(i)⋅((i)−∗)⊤] =E[ _l(i) _l(i+1)]·E[\| w_l(i)\|^2]-E[ _l(i) _l(i+1)· w_l(i) η· a_l(i)·( θ(i)- θ^*) ] =−η0.52[‖l(i)‖2]−η[δl(i)δl(i+1)⋅al(i)⋅((i)−∗)⊤⋅l(i)] =- η^0.52E[\| w_l(i)\|^2]- [ _l(i) _l(i+1)· a_l(i)·( θ(i)- θ^*) · w_l(i)] =−η0.52[‖l(i)‖2]−O(η1.75) =- η^0.52E[\| w_l(i)\|^2]-O(η^1.75) Thus we have [((i)(i))⋅((i+1)(i+1))⊤] [( δ(i) W(i))·( δ(i+1) W(i+1)) ] =∑1≤l,r≤m[δl(i)δr(i+1)⋅l(i)⊤r(i+1)] = _1≤ l,r≤ mE[ _l(i) _r(i+1)· w_l(i) w_r(i+1)] =∑l=1m[δl(i)δl(i+1)]⋅l(i)⊤l(i+1)) = _l=1^mE[ _l(i) _l(i+1)]· w_l(i) w_l(i+1)) =−η0.52∑l=1m[‖l(i)‖2]−O(m⋅η1.75) =- η^0.52 _l=1^mE[\| w_l(i)\|^2]-O(m·η^1.75) =−η0.52[‖(i)‖2]−O(m⋅η1.75) =- η^0.52E[\| W(i)\|^2]-O(m·η^1.75) Then we retain ∑i=0t−1∑j<i[((i)(i))⋅((j)(j))⊤] _i=0^t-1 _j<iE[( δ(i) W(i))·( δ(j) W(j)) ] =∑i=0t−2[((i)(i))⋅((i+1)i+1)⊤] = _i=0^t-2E[( δ(i) W(i))·( δ(i+1) W_i+1) ] (73) =−η0.52⋅∑i=0t−2[‖(i)‖2]−O(m⋅η1.75) =- η^0.52· _i=0^t-2E[\| W(i)\|^2]-O(m·η^1.75) (74) Combining equ (72) and equ (74), we have [‖((t)−∗)‖2] [\|( θ(t)- θ^*)\|^2] =[‖((0)−∗)‖2] =E[\|( θ(0)- θ^*)\|^2] +η0.5⋅∑i=0t−1[‖(i)‖2]+2∑i=0t−1∑j<i[((i)(i))⋅((j)(j))⊤]+O(m⋅η1.75) +η^0.5· _i=0^t-1E[\| W(i)\|^2]+2 _i=0^t-1 _j<iE[( δ(i) W(i))·( δ(j) W(j)) ]+O(m·η^1.75) =[‖((0)−∗)‖2]+η0.5⋅∑i=0t−1[‖(i)‖2]−η0.5⋅∑i=0t−2[‖(i)‖2]+O(m⋅η1.75) =E[\|( θ(0)- θ^*)\|^2]+η^0.5· _i=0^t-1E[\| W(i)\|^2]-η^0.5· _i=0^t-2E[\| W(i)\|^2]+O(m·η^1.75) =[‖((0)−∗)‖2]+η0.5[‖(t−1)‖2]−O(m⋅η1.75) =E[\|( θ(0)- θ^*)\|^2]+η^0.5E[\| W(t-1)\|^2]-O(m·η^1.75) ≥[‖⋆‖2]+η0.5[‖(t−1)‖2] [\| θ \|^2]+η^0.5E[\| W(t-1)\|^2] Then we give a proof of this theorem by contradiction. Assume for every step t≤1η2t≤ 1η^2, we have [1m∑i=1m‖(T)‖2]≥ηE[ 1m _i=1^m\| w_i(T)\|^2]≥ η (75) i.e. [‖(t)‖2]≥m⋅ηE[\| W(t)\|^2]≥ m· η (76) When T=1η2T= 1η^2, according to equ (66), sum up from 0 to T−1T-1 and we have [1m∑i=1m‖(T)‖2] [ 1m _i=1^m\| w_i(T)\|^2] =[1m∑i=1m‖i(0)‖2]−(2ηm−η2.5)⋅∑t=0T−1[‖((t)−∗)‖2]−2ηm⋅∑t=0T−1[((t)−∗)⊤⋅∗] =E[ 1m _i=1^m\| w_i(0)\|^2]-( 2ηm-η^2.5)· _t=0^T-1E[\|( θ(t)- θ^*)\|^2]- 2ηm· _t=0^T-1E[( θ(t)- θ^*) · θ^*] ≤[1m∑i=1m‖i(0)‖2]−(2ηm−η2.5)⋅(T⋅[‖∗‖2]+η0.5∑t=0T−1[‖t‖2])+T⋅2ηm⋅[‖∗‖2] [ 1m _i=1^m\| w_i(0)\|^2]-( 2ηm-η^2.5)·(T·E[\| θ^*\|^2]+η^0.5 _t=0^T-1E[\| W_t\|^2])+ T· 2ηm·E[\| θ^*\|^2] ≤[1m∑i=1m‖i(0)‖2]−2η1.5⋅T⋅η+O(T⋅η2.5) [ 1m _i=1^m\| w_i(0)\|^2]-2η^1.5· T· η+O(T·η^2.5) =1−2η1.5⋅1η2⋅η+O(T⋅η2.5)=−1+O(T⋅η2.5)<0 =1-2η^1.5· 1η^2· η+O(T·η^2.5)=-1+O(T·η^2.5)<0 Which is absolutely a contradiction! Therefore, we complete the proof. □ Appendix C Phase I: Feature Learning and Convergence C.1 Rotation to alignment We use gradient descent in phase I. For every neuron i w_i and aia_i (i∈[m]i∈[m]) at step t: ∂ℒ((t))∂i(t)⊤=ai(t)⋅1n∑j=1m((t)⊤(t)j−j)⋅j⊤ ( θ(t))∂ w_i(t) =a_i(t)· 1n _j=1^m( a(t) W(t) x_j- y_j)· x_j (77) ∂ℒ((t))∂ai(t)=1n∑j=1m((t)⊤(t)j−j)⋅j⊤⋅i(t)⊤ ( θ(t))∂ a_i(t)= 1n _j=1^m( a(t) W(t) x_j- y_j)· x_j · w_i(t) (78) The update rule of gradient descent is i(t+1)=i(t)−η⋅ai(t)⋅1n∑j=1m((t)⊤(t)j−j)j w_i(t+1)= w_i(t)-η· a_i(t)· 1n _j=1^m( a(t) W(t) x_j- y_j) x_j (79) ai(t+1)=ai(t)−η⋅1n∑j=1m((t)⊤(t)j−j)j⊤⋅i(t) a_i(t+1)=a_i(t)-η· 1n _j=1^m( a(t) W(t) x_j- y_j) x_j · w_i(t) (80) By law of large numbers, we have 1n∑j=1nj⋅j⊤=[j⋅j⊤]+O(1n)=I+O(1n) 1n _j=1^n x_j· x_j =E[ x_j· x_j ]+O( 1 n)=I+O( 1 n) (81) Then we have i(t+1) w_i(t+1) =i(t)−η⋅ai(t)⋅1n∑j=1mj⋅j⊤⋅((t)−∗) = w_i(t)-η· a_i(t)· 1n _j=1^m x_j· x_j ·( θ(t)- θ^*) (82) =i(t)−η⋅ai(t)⋅((t)−∗)+O(ηn) = w_i(t)-η· a_i(t)·( θ(t)- θ^*)+O( η n) (83) And ai(t+1) a_i(t+1) =ai(t)−η⋅((t)−∗)1n∑j=1mj⋅j⊤⋅i(t) =a_i(t)-η·( θ(t)- θ^*) 1n _j=1^m x_j· x_j · w_i(t) =ai(t)−η⋅((t)−∗)⋅i(t)+O(ηn) =a_i(t)-η·( θ(t)- θ^*)· w_i(t)+O( η n) Since ai(t),‖i(t)‖≤n0.5a_i(t),\| w_i(t)\|≤ n^0.5 when phase I begins, we have i(t+1) w_i(t+1) =i(t)−η⋅ai(t)⋅((t)−∗)+O(ηn) = w_i(t)-η· a_i(t)·( θ(t)- θ^*)+O( η n) =i(t)+η⋅(ai(t)⋅∗)+O(η1.5) = w_i(t)+η·(a_i(t)· θ^*)+O(η^1.5) Similarly, we have: ai(t+1) a_i(t+1) =ai(t)+η⋅∗⋅i(t)+O(η1.5) =a_i(t)+η· θ^*· w_i(t)+O(η^1.5) Combine both we have: [i(t+1)ai(t+1)]=(+η)⋅[i(t)ai(t)]+O(η1.5) [ matrix w_i(t+1)\\[5.69054pt] a_i(t+1) matrix ]=( I+η M)· [ matrix w_i(t)\\[5.69054pt] a_i(t) matrix ]+O(η^1.5) (84) where =[∗⊤∗0] M= [ matrix 0& θ^* \\[5.69054pt] θ^*&0 matrix ]. The top eigenvalue of M is λ1=‖∗‖ _1=\| θ^*\| and the lowest eigenvalue of M is λn+1=−‖∗‖ _n+1=-\| θ^*\|. All the other eigenvalues of M are equal to 0. Since M is symmetry matrix, there exists orthogonal matrix Q_M such that =M⊤⋅diag(‖∗‖,0,…,−‖∗‖)⋅M M= Q_M ·diag(\| θ^*\|,0,…,-\| θ^*\|)· Q_M (85) Lemma C.1 (Alignment). Suppose ˜1 (A1-3, 5-6) holds and consider gradient descent for updates. Assume that phase I begins at time t1t_1, then at time t2=t1+T2t_2=t_1+T_2, T2=1‖⋆‖⋅ln(1η)T_2= 1\| θ \|· ( 1η), for any neuron i w_i it holds |⟨⋆,i(t2)⟩|‖⋆‖⋅‖i(t2)‖≥1−|O(ln1η⋅η)|. θ , w_i(t_2) \| θ \|·\| w_i(t_2)\|≥ 1- O( 1η· η) . (86) Proof. By equ (84), we have [i(t1+T2)ai(t1+T2)] [ matrix w_i(t_1+T_2)\\[5.69054pt] a_i(t_1+T_2) matrix ] =(+η⋅)T2⋅[i(t1)ai(t1)]+O(T2⋅η1.5) =( I+η· M)^T_2· [ matrix w_i(t_1)\\[5.69054pt] a_i(t_1) matrix ]+O(T_2·η^1.5) =∑k=0T2(T2k)(η)k⋅[i(t1)ai(t1)]+O(T2⋅η1.5) = _k=0^T_2 T_2k(η M)^k· [ matrix w_i(t_1)\\[5.69054pt] a_i(t_1) matrix ]+O(T_2·η^1.5) =(I+T2η+T2(T2−1)2(η)2+⋯+(ηM)T)⋅[i(t1)ai(t1)]+O(T2⋅η1.5) =(I+T_2η M+ T_2(T_2-1)2(η M)^2+·s+(η M)^T)· [ matrix w_i(t_1)\\[5.69054pt] a_i(t_1) matrix ]+O(T_2·η^1.5) =(∑i=0T2(T2η)i!+O(T2⋅η2))⋅[i(t1)ai(t1)]+O(T2⋅η1.5) =( _i=0^T_2 (T_2η M)^ii!+O(T_2·η^2))· [ matrix w_i(t_1)\\[5.69054pt] a_i(t_1) matrix ]+O(T_2·η^1.5) =(exp(T2η⋅)+O((T2η⋅)T+1(T+1)!))⋅[i(t1)ai(t1)]+O(T2⋅η1.5)(taylor expansion) =( (T_2η· M)+O( (T_2η· M)^T+1(T+1)!))· [ matrix w_i(t_1)\\[5.69054pt] a_i(t_1) matrix ]+O(T_2·η^1.5) (taylor expansion) =e⋅‖∗‖[i(t1)ai(t1)]+O(T2⋅η1.5)(η−lnη≪(−lnη)−lnη) = e· M\| θ^*\| [ matrix w_i(t_1)\\[5.69054pt] a_i(t_1) matrix ]+O(T_2·η^1.5) ($η^- η (- η)^- η$) So we have i(t1+T2)=e⋅ai(t1)‖∗‖2⋅∗⊤+O(ln1η⋅η1.5) w_i(t_1+T_2)= e· a_i(t_1)\| θ^*\|_2· θ^* +O( 1η·η^1.5) (87) Then we have, |⟨∗,i(t2)⟩| θ^*, w_i(t_2) =|⟨∗,e⋅ai(t1)‖∗‖2⋅∗⊤+O(ln1η⋅η1.5)⟩| = θ^*, e· a_i(t_1)\| θ^*\|_2· θ^* +O( 1η·η^1.5) =|‖∗‖⋅e⋅ai(t1)+∗⋅O(ln1η⋅η1.5)|‖∗‖⋅‖i(t2)‖ = \| θ^*\|· e· a_i(t_1)+ θ^*· O( 1η·η^1.5) \| θ^*\|·\| w_i(t_2)\| =|e⋅ai(t1)+∗‖∗‖⋅O(ln1η⋅η1.5)|‖e⋅ai(t1)‖∗‖⋅∗⊤+O(ln1η⋅η1.5)‖ = e· a_i(t_1)+ θ^*\| θ^*\|· O( 1η·η^1.5) \| e· a_i(t_1)\| θ^*\|· θ^* +O( 1η·η^1.5) \| ≥e⋅ai(t1)−|O(ln1η⋅η1.5)|e⋅ai(t1)+|O(ln1η⋅η1.5))|(triangle inequality) ≥ e· a_i(t_1)- O( 1η·η^1.5) e· a_i(t_1)+ O( 1η·η^1.5)) (triangle inequality) =1−|O(ln1η⋅η1.5)|e⋅ai(t1)+|O(ln1η⋅η1.5)|≥1−|O(ln1η⋅η)| =1- O( 1η·η^1.5) e· a_i(t_1)+ O( 1η·η^1.5) ≥ 1- O( 1η· η) Therefore, we complete the proof. □ C.2 Convergence to sparse solution We assume that all the neurons are perfect aligned, i.e. for every neuron i w_i (i∈[m]i∈[m]) at step t, there exists coefficient γi(t) _i(t) such that i(t)=γi(t)⋅∗ w_i(t)= _i(t)· θ^*. Lemma C.2 (Convergence). Suppose ˜1 (A1-3, 5-6) holds and consider gradient descent for updates. Assume all the neurons are perfectly aligned at step t2t_2. Let t3=t2+1‖⋆‖2⋅ln(1/η)ηt_3=t_2+ 1\| θ \|^2· (1/η)η. Using gradient descent, we have ‖(t3)−⋆‖≤|O(η⋅ln1η)|\| θ(t_3)- θ \|≤|O(η· 1η)|. Furthermore, for any neuron ‖i(t3)‖≥η\| w_i(t_3)\|≥ η (i∈[m]i∈[m]), we have |⟨⋆,i(t3)⟩|‖⋆‖⋅‖i(t3)‖≥1−|O(η⋅ln1η)|. θ , w_i(t_3) \| θ \|·\| w_i(t_3)\|≥ 1- O(η· 1η) . (88) By equ (79), when t=t2t=t_2, we have i(t+1) w_i(t+1) =i(t)−η⋅ai(t)⋅1n∑j=1m((t)⊤(t)j−j)j = w_i(t)-η· a_i(t)· 1n _j=1^m( a(t) W(t) x_j- y_j) x_j (89) =γi(t)⋅∗−η⋅ai(t)⋅(1n∑j=1mj⋅j⊤)⋅(∑k=1mak(t)⋅γk(t)⋅∗−∗) = _i(t)· θ^*-η· a_i(t)·( 1n _j=1^m x_j· x_j )·( _k=1^ma_k(t)· _k(t)· θ^*- θ^*) (90) =γi(t)−η⋅ai(t)⋅(∑k=1mak(t)⋅γk(t)−1)⋅∗+O(ηn) = \ _i(t)-η· a_i(t)·( _k=1^ma_k(t)· _k(t)-1) \· θ^*+O( η n) (91) The last equation is due to 1n∑j=1mj⋅j⊤=I+O(1n)=I+O(η2) 1n _j=1^m x_j· x_j =I+O( 1 n)=I+O(η^2) by large number law and ˜1(A3). Notice that (t)=(t)⊤⋅(t)=∑i=1mai(t)⋅i(t)=(∑i=1mai(t)⋅γi(t))⋅∗ θ(t)= a(t) · W(t)= _i=1^ma_i(t)· w_i(t)=( _i=1^ma_i(t)· _i(t))· θ^* (92) Then we have (t+1) θ(t+1) =(t)−η⋅(t)⊤(t)⋅1n∑i=1n((t)⊤(t)i−yi)⋅i⊤ = θ(t)-η· a(t) a(t)· 1n _i=1^n( a(t) W(t) x_i-y_i)· x_i −η⋅1n∑i=1n(⊤(t)(t)i−yi)⋅i⊤(t)⊤(t)+O(η2) -η· 1n _i=1^n( a (t) W(t) x_i-y_i)· x_i W(t) W(t)+O(η^2) =(t)−η⋅∑i=1mai(t)2⋅(∑j=1mai(t)⋅γi(t)−1)⋅∗−η⋅(∑j=1mai(t)⋅γi(t)−1)⋅‖∗‖2⋅∗+O(η2) = θ(t)-η· _i=1^ma_i(t)^2·( _j=1^ma_i(t)· _i(t)-1)· θ^*-η·( _j=1^ma_i(t)· _i(t)-1)·\| θ^*\|^2· θ^*+O(η^2) =(t)−η⋅(∑j=1mai(t)⋅γi(t)−1)⋅(∑i=1mai(t)2+‖∗‖2)⋅∗+O(η2) = θ(t)-η·( _j=1^ma_i(t)· _i(t)-1)·( _i=1^ma_i(t)^2+\| θ^*\|^2)· θ^*+O(η^2) We consider the change of (t)−∗ θ(t)- θ^*. Subtracting θ∗θ^* on both side and we retain (t+1)−∗ θ(t+1)- θ^* =(t)−∗−η⋅(∑j=1mai(t)⋅γi(t)−1)⋅(∑i=1mai(t)2+‖∗‖2)⋅∗+O(η2) = θ(t)- θ^*-η·( _j=1^ma_i(t)· _i(t)-1)·( _i=1^ma_i(t)^2+\| θ^*\|^2)· θ^*+O(η^2) (93) =(∑k=1mak(t)⋅γk(t)−1)⋅(1−η⋅(∑i=1mai(t)2+‖∗‖2))⋅∗+O(η2) =( _k=1^ma_k(t)· _k(t)-1)·(1-η·( _i=1^ma_i(t)^2+\| θ^*\|^2))· θ^*+O(η^2) (94) =((t)−∗)⋅(1−η⋅(∑i=1mai(t)2+‖∗‖2))+O(η2) =( θ(t)- θ^*)·(1-η·( _i=1^ma_i(t)^2+\| θ^*\|^2))+O(η^2) (95) In the beginning, |ak(t2)|,‖k(t2)‖≤η|a_k(t_2)|,\| w_k(t_2)\|≤ η, so γi(t2)≤η‖∗‖ _i(t_2)≤ η\| θ^*\| and we have |∑k=1mak(t2)⋅γk(t2)|≤m⋅η‖∗‖ _k=1^ma_k(t_2)· _k(t_2) ≤ m· η\| θ^*\| (96) by equ (95), for any t2≤t≤t3t_2≤ t≤ t_3 it holds ‖(t+1)−∗‖ \| θ(t+1)- θ^*\| =‖(t)−∗‖⋅|(1−η⋅(∑i=1mai(t)2+‖∗‖2))|+O(η2) =\| θ(t)- θ^*\|· (1-η·( _i=1^ma_i(t)^2+\| θ^*\|^2)) +O(η^2) (97) ≤‖(t)−∗‖⋅(1−η⋅‖∗‖2)+O(η2) ≤\| θ(t)- θ^*\|·(1-η·\| θ^*\|^2)+O(η^2) (98) Let T=−lnη‖∗‖2⋅ηT= - η\| θ^*\|^2·η, we retain ‖(t3)−∗‖≤‖(t2)−∗‖⋅(1−η⋅‖∗‖2)T+O(T⋅η2)\| θ(t_3)- θ^*\|≤\| θ(t_2)- θ^*\|·(1-η·\| θ^*\|^2)^T+O(T·η^2) (99) Since (1−x)T≤exp(−x⋅T)(1-x)^T≤ (-x· T), we have ‖(t3)−∗‖ \| θ(t_3)- θ^*\| ≤‖(t2)−∗‖⋅(1−η⋅‖∗‖2)T+O(T⋅η2) ≤\| θ(t_2)- θ^*\|·(1-η·\| θ^*\|^2)^T+O(T·η^2) ≤‖(t2)−∗‖⋅exp(−η⋅‖∗‖2⋅T)+O(η⋅ln1η) ≤\| θ(t_2)- θ^*\|· (-η·\| θ^*\|^2· T)+O(η· 1η) =‖(t2)−∗‖⋅η+O(η⋅ln1η) =\| θ(t_2)- θ^*\|·η+O(η· 1η) =|O(η⋅ln1η)| = O(η· 1η) So we reatin |1−∑k=1mak(t3)⋅γk(t3)|≤|O(η⋅ln1η)| 1- _k=1^ma_k(t_3)· _k(t_3) ≤ O(η· 1η) (100) Since the summation of i(i) w_i(i) approach to ∗ θ^*, which shows that there exists some neurons with "big" norm. For any neuron ‖i(t3)‖≥η\| w_i(t_3)\|≥ η, we have γi(t3)≥η‖∗‖ _i(t_3)≥ η\| θ^*\|. For these neuron, we retain |⟨i(t3),∗⟩| w_i(t_3), θ^* =|⟨(∑k=1mak(t3)⋅γk(t3))⋅∗+O(T⋅η2),∗⟩| = ( _k=1^ma_k(t_3)· _k(t_3))· θ^*+O(T·η^2), θ^* =|(∑k=1mak(t3)⋅γk(t3))⋅‖∗‖2+O(η⋅ln1η)γi(t3)⋅‖∗‖2+O(η⋅ln1η)| = ( _k=1^ma_k(t_3)· _k(t_3))·\| θ^*\|^2+O(η· 1η) _i(t_3)·\| θ^*\|^2+O(η· 1η) ≥|γi(t3)⋅‖∗‖2|−|O(η⋅ln1η)||γi(t3)⋅‖∗‖2|+|O(η⋅ln1η)|(by triangle inequality and equ (100) ) ≥ _i(t_3)·\| θ^*\|^2 - O(η· 1η) _i(t_3)·\| θ^*\|^2 + O(η· 1η) (by triangle inequality and equ ( t_3bound) ) =1−|O(η⋅ln1η)| =1- O(η· 1η) Therefore, we complete the proof. □ Appendix D Experiments details Main Experimental Setup. We perform our empirical observations on commonly used image classification datasets CIFAR-10 Krizhevsky et al. [28], with the standard architectures ResNet-18 He et al. [22]. Optimization is done with vanilla and label noise SGD, with no weight decay or momentum. The learning rate is set to 0.10.1, and the total number of epochs is 160160. Model Pruning and Sparsity. Model pruning is a compression technique that reduces network size by selectively removing redundant components, such as weights and neurons, while maintaining comparable performance. The pruning limit of a trained neural network is often linked to its sparsity [11], as weights and neurons with small magnitudes are typically considered redundant or non-influential [18, 20, 16]. Therefore, a sparser model tends to retain higher performance after pruning to the same level. In this work, we use model pruning to investigate the sparsity of solutions obtained through different training algorithms. Specifically, we focus on the Iterative Feature Merging (IFM) algorithm [7]. To the best of our knowledge, IFM is the first pruning technique that does not require fine-tuning or modifications to the training procedure and thus can be directly applied to a pre-trained model. Appendix E Additional experiment Figure 6: Neuron dynamics in alternating noisy/noiseless SGD training. We replicate the synthetic problem setup from Subsection "Setup and Overview: A Two-Layer Linear Network", changing the standard SGD label noise to training with alternating noisy and noiseless SGD every 5000 steps. (a) Learning dynamics on average. The averaged neuron norm Avgi∈[m](‖i(t)‖2)Avg_i∈[m](\| w_i(t)\|_2) and the averaged neuron alignment Avgi∈[m](⟨i(t),⋆⟩)Avg_i∈[m]( w_i(t), θ ) vs. training iteration t. (b) Learning dynamics of i-th neuron. The i-th neuron norm ‖i(t)‖2\| w_i(t)\|_2 and the corresponding absolute value |ai(t)||a_i(t)| in the second layer vs. training iteration t. In this section, we present the supplementary experiment to help understand the mechanistic principles of label noise SGD. Alternating label noise SGD: We trained the model using SGD but alternate label noise every 5,000 steps (adding label noise for 5000 steps and then remove label noise for 5000 steps). As shown in Figure˜6, this experiment reveals two key phenomena: (i) the norms of first-layer neurons gradually decrease when adding label noise and the norm reduction stops when removing label noise. (i) the second-layer neuron weights oscillate near zero under noise but stabilize. These observations collectively demonstrate that the crucial role of label noise in facilitating the transition from lazy to rich regimes. Our theoretical analysis further in paper establishes that label noise SGD induces the second-layer oscillations, driving the progressive reduction of first-layer norms, thereby enabling the model to escape the lazy regime.