Benign Oscillation of Stochastic Gradient Descent with Large Learning Rate
Authors: Miao Lu
Beining Wu
Xiaodong Yang
Difan Zou
Venue: ICLR 2024 poster (2024)
Keywords: deep learning theory; large learning rate; oscillation of stochastic gradient descent;
Primary area: learning theory
TL;DR: We investigate the generalization properties of NN trained by SGD with large learning rates.

Abstract: In this work, we theoretically investigate the generalization properties of neural networks (NN) trained by stochastic gradient descent (SGD) with large learning rates. Under such a training regime, our finding is that, the oscillation of the NN weights caused by SGD with large learning rates turns out to be beneficial to the generalization of the NN, potentially improving over the same NN trained by SGD with small learning rates that converges more smoothly. In view of this finding, we call such a phenomenon “benign oscillation”. Our theory towards demystifying such a phenomenon builds upon the feature learning perspective of deep learning. Specifically, we consider a feature-noise data generation model that consists of (i) weak features which have a small $\ell_2$-norm and appear in each data point; (ii) strong features which have a large $\ell_2$-norm but appear only in a certain fraction of all data points; and (iii) noise. We prove that NNs trained by oscillating SGD with a large learning rate can effectively learn the weak features in the presence of those strong features. In contrast, NNs trained by SGD with a small learning rate can only learn the strong features but make little progress in learning the weak features. Consequently, when it comes to the new testing data points that consist of only weak features, the NN trained by oscillating SGD with a large learning rate can still make correct predictions, while the NN trained by SGD with a small learning rate could not. Our theory sheds light on how large learning rate training benefits the generalization of NNs. Experimental results demonstrate our  findings on the phenomenon of “benign oscillation”.

Published as a conference paper at ICLR 2024
BENIGN OSCILLATION OF STOCHASTIC GRADIENT DESCENT WITH LARGE LEARNING RATES
Miao Lu Beining Wu*?, Xiaodong Yang', Difan Zou'
Stanford University, UUniversity of Chicago, 'Harverd University, *University of Hong Kong miaolu@stanford edu. en, beir wiwgggguuee uch caag..cao...e xyangêg harvard.edu dzouβcs hku.....h hk
ABSTRACT
In this work, we theoretically investigate the generalization properties of neural networks (NN) trained by stochastic gradient descent (SGD) with large learning rates. Under such a training regime, our finding is that, the oscillation of the NN weights caused by SGD with large learning rates turns out to be beneficial to the generalization of the NN, potentially improving over the same NN trained by SGD with small learning rates that converges more smoothly. In view of this finding, we call such a phenomenon "benign oscillation". Our theory towards demystifying such phenomenon builds upon the feature learning perspective of deep learning. Specifically, we consider a feature-noise data generation model that consists (i) weak features which have small f--norm and appear in each data point; (ii) strong features which have a large εz-norm but appear only in a certain fraction of all data points; and (iii) noise. We prove that NNs trained by oscillating SGD with large learning rate can effectively learn the weak features in the presence of those strong features. In contrast, NNs trained by SGD with small learning rate can only learn the strong features but make little progress in learning the weak features. Consequently, when it comes the new testing data points that consist of only weak features, the NN trained by oscillating SGD with a large learning rate can still make correct predictions, while the NN trained by SGD with small learning rate could not. Our theory sheds light on how large learning rate training benefits the generalization of NNs. Experimental results demonstrate our findings the phenomenon of "benign oscillation".
INTRODUCTION
While deep neural networks (NNs) have achieved tremendous empirical success in various domains including images, language processing, decision-man making. etc, the theoretical understanding of deep learning is still far behind satisfactory, especially the relationships between optimization of the NN and its generalization. From the viewpoint of optimization, using large learning rafes in NN training has been empirically shown to be of vital importance for generalization (He et al. [0166] Xing et al., 2018 Damian et al.) 2022 Kaur al. 2023). Nevertheless, a principled theoretical understanding of the mechanism behind the benefits of large learning rate training still remains limited.
To better capture the key ingredients in the training dynamics of stochastic gradient descent (SGD) with large learning rates, we train a ResNet (He et al. 2016) using SGD with small and large learning rates and present the training and testing results in Figure I When using large learning rate SGD, we can observe "oscilllatin" training curve, i.e., the training loss fluctuates at different iterations (generally this happens only when the learning rate exceeds the inverse of the objective smoothness), while for small learning rate SGD, the training curve is smooth and converges rapidly. On the other hand, the smooth convergence in training loss cannot bring any benefit for the test accuracy SGD with large learning rates achieves a significantly higher test accuracy than SGD with small learning rates. These empirical observations suggest that the oscillation during training can be closely tied to the better generalization performance achieved by SGD with large learning rates.
In this paper, we study the learning dynamics of SGD with large learning rates by investigating the oscillation happening during the optimization process, and explain its benefit to the generalization

---

Published as a conference paper at ICLR 2024
100
80
Test Accuracy oe
70
Training Loss
10-1
60
50
10
40
30
large
large Ir small Ir
10-1
20
small Ir
10
20
40
60
80
100
20
40
60
80
100
epochs
epochs
Figure 1: Training and lest performance R8 on CIFAR- dataset, when trained via SGD with small and large learning rates (1) = 0.01 vs. 17 = 0.75). We adopt the same configuration as in Andriushchenkko et al.) (2023): using weight decay hut no momentum and no data augmentation. A clear difference hetween the large learning rate training and small learning rate training can be observed: SGD with large learning rate leads "oscillating" training curve with higher testing accuracy: SGD with small learning rate has a rapid and smooth convergence but gives lower lesting accuracy.
performance. The key message is that compared to the smooth convergence achieved by SGD with small learning rates, the oscillation prevents the over-greedy convergence and serves as the engine that drives the learning of less-ppominent data patterns. These data patterns would be beneficial for the NN to generalize well on unseen testing data. Thus we explain from the theoretical side why large learning rate training can help NN to generalize better in practice.
Our investigation of SGD with large learning rates for NN training builds on the feature learning per- spective of deep learning theory (Allen-Zhu and Li. 2022), which explicitly considers data models consisting of different types of features and noise. For the sake of our goal, we devise a Feature-noise data model consisting of two types of features that have different strengths and different distribu- tions. Based upon the new data model, by carefully tracking the process of feature learning of a NN trained by SGD with large or small learning rates, we prove that only when trained with large learning rates can the NN effectively learn the key features for generalizing to each new data point. The NN trained by small learning rate SGD fails to generalize to certain testing data because of the limited learning of the features which are crucial to the generalization to those new data points.
To explain such a phenomenon, of learning the key features with large learning rate SGD as the oscillation during NN training, which also related to the regime of "edge of stability" (Cohen al. 2020). Intuitively, the oscillation can prevent over-greedy convergence which could only leverage the most prominent components of the data, thus allowing for all the useful components to be discovered and learned by gradient descent. In view of our finding that indicates oscillating NN training with large learning rates possibly resulting in better generalization, we refer such a phenomenon as "benign oscillation".
theory identifies the core incentives for the superior performance
1.1 OUR CONTRIBUTIONS
Dynamic analysis framework for SGD with large learning rates. We provide theoretical frame- work to understand and explain the oscillation in NN training via SGD with a large learning rate. Specifically, we consider feature-noise data generation model consisting of two types of features the strong features and the weak featuresss - that have different strengths and distributions to capture our core ideas towards explaining the relationships between large learning rate SGD training and generalization. Then, our theoretical framework establishes a sharp characterization of the training dynamics of these features and noises, based on which we can precisely analyze the generalization of NN trained by SGD with small or large learning rates. We remark that in general studying the NN optimization dynamics when the learning rate is greater than twice inversed smoothness is quite challenging, and our theoretical analysis framework based upon the feature-noise model potentially provides useful guidance which can be leveraged to study other nonconvex optimization problems.
A new theoretical argument for feature learning driven by oscillation. The key to explaining the large learning rate training regime is a new theory on learning the weak features driven by oscillation. As we illustrate in Section 3, the oscillation of the NN values (predictions) around the target (label) does not cancel with each other. Instead, the fluctuations accumulate linearly over time. This further serves the engine driving the learning of the weak features, resulting in better generalization. This characterizes the distinctive training dynamics of SGD under the large learning rate training regime, revealing the benefits of the oscillation in learning useful data patterns.
2

---

Published as a conference paper at ICLR 2024
Division for generalization by different learning rates. In contrast effectively learning the weak features by large learning rate oscillating training, we also show that the smooth and rapid convergence achieved by SGD with small learning rates would not help NN learn the weak features, thus being unable to generalize to the new data without strong features. This gives a division of the generalization property of NNs trained by large and small learning rates.
PROBLEM SETTING
In this section, we introduce the theoretical setting for our investigation of generalization properties of SGD through the task of binary classification. We first introduce the multi-view data generation model and then define the two-layer convolutional neural network and the SGD algorithm.
Data generation model. We let v 1 I be two fixed vectors, denoting the signal (or feature) part shared by each data point. Then each data point, denoted by (x.y) where (x("), x()) ())
contains 3 patches, is generated as following: let y E {1, (1- be independently generated according
to Pvy 1) P(y- 1) 1/2, and
Weak signal patch. one patch of x is taken by the weak signal y
Strong signal patch. with probability - p. one patch of x that is different from y v, is taken by the strong signal y u, where P E (0, 1/2) is the probability.
Noise patch. all remaining patches are taken by independent Gaussian noise (O0 oz vv /TVllv/[ uu /l[ul(3) for some variance op O.
For simplicity, we refer to the data with strong signal as the strong data, denoted by ((yu, yV, E), y), and we refer the data with only weak signal as the weak data, denoted by ((É. yv, E), y). Here by "strong", we mean a vector with a larger (2-norm, as we would specify in the theory part. Intuitively, the weak signal y of key objects in an image. The strong signal y u can be understood as the background or the domain information which is stronger but only appears that in order for a classifier to generalize to new data, it must effectively learn the weak signal.
be interpreted as the invariant and common signals across data like the shape
certain fraction of all data points. This indicates
Our proposed data generation model is adapted from the reature-leaning-baseee line of research on deep learning (Allen -Zu and Li 2022 Cao et al., 2022 Zou et al.) (003)), and it can serve as good theoretical platform to explain the relationships between oscillating NN training with large learning rates and NN generalization. Finally, we remark that this data model can be extended for generality, e.g., multiple features, more patches, multi-class data. fact, as long as the signal and noise patches have properly different strength and fractions, our theoretical analysis can be directly applied.
Two-layer CNN. We consider two-layer convolutional neural network (CNN) with filters applied to the three patches separately. We assign the parameters of the second layer of the CNN to fixed +1 and 1,, respectively. Formally, the CNN [(; W): Rdd + is defined as
1
f(x; W)
Σ jF((x jE(11)
(5(: W
Σ rE(m]
((Ws,r;
(1)
m
where E N. is the number of filters (i.e., neurons), (x) (max (2, 0})² is the ReLU activation function, and wy.- E Rd denotes the weights of the r-th neuron of Fj. We use W = and W, [ to denote the collection of the weights.
Loss function and stochastic gradient descent (SGD). Having access to n i.i.d. samples from the data generation model, S {(x,, y4) bx]]e we solve binary classification task by minimizing the following mean squared loss.
1 L(W)-
1 Σ
(x((x; W). = 2n 1E[n]
(J(x; W) y:
[E(m
where {(f(x; W v.).). v.) (x( - stability" (Cohen al. 2020), adopting mean squared error is believed to make it easier to identify the effects of large learning rates. Besides, mean squared loss has also been demonstrated to be comparable even better than cross-entropy loss in many classification tasks (Hui 2020).
) /2 is the loss on a single data point. Inspired by "edge of
3

---

Published as a conference paper at ICLR 2024
We optimize the loss function 2 via multi-paas stochastic gradient descent (SGD), initializing from some Gaussian weights, where each entry of w and - is sampled from N(0, ((). The SGD goes for several epochs. In each epoch, we use each data (x,, 3/) for exactly once, in the exact order of (x1,2) 31) + (x2, 3/2) + (Xn: Vn. Thus, the weights of the CNN are updated obeying the following rule,
+1
(++1)
(t) jr
Vw (((((()) (x,W), Vi.))
5u
3
in (f(W(o,xx)) x:.) Vi.) Σ p=1
(
(p) J.r
(p)
(3)
jr
for each E {=1} and [m], where i, (t 1) mod and 7) 0 is the learning rate.
Generalization via signal (feature) learning. Our goal is to study the generalization property of the CNN trained by SGD (3). Given new testing data point (x", yy) sampled from the data generation model, we measure the generalization of the CNN by the correctness of the classification,
E[1 [(x"; W agga 0} P(y f(x: W agd) > 0),
where W aga denotes the weights trained by SGI, Zhang et al. (2021).
We investigate the generalization property via looking through the process of signal (feature) learn- ing. Specifically, by the SGD updates (3). the weights ('')) of the CNN is a linear combination of
the initialization (0) j.r. the strong signal j u, the weak signal y v, and the noise vectors &i. E.. This motivates us to consider the following representation of the weights, for j E (=1), E [m],
(v) jv + noise parts.
The relative scales of these combination coefficients actually imply how the weights learn the strong signal u, the weak signal v, or memorizing the noise which determines how the CNN can generalize.
As is shown by Cao et al. (202)). the CNN tends to fit the training dataset using patches with higher strength when trained by small learning rate gradient descents. Therefore, in such training regime, the CNN tends fit the training data using the strong signal y u, making less progress learning the weak signal y v, thus resulting in misclassification when the testing data lacks the strong signal component. On the contrary, our paper investigates the large learning rate regime, and suggests that the oscillation of SGD is beneficial for learning the weak signal, giving better generalization results.
Thus, our main focus the sequel would be studying the dynamics of the inner products (w (t)
Jirt ju),
(w (1) j. jv), and (w j.r 5)- We will show that under large learning rate SGD training (w( : can be effectively learned to relatively large scale compared to its initialization. This is further provably
useful for generalizing all new data points.
UNDERSTAND THE OSCILLATION: SINGLE TRAINING DATA CASE
Before giving our main theory large learning rate SGD training, let's first study simplified setup where we consider only a single training data point consisting only of a weak signal patch y v and strong signal patch u, without any noise patch. Such setting helps illustrate the key insights behind our main theory regarding the understanding of oscillation. Without loss of generality, we denote the single training data (x. y) with x (y v.y u), and we can also simplify the CNN expression ① and the SGD updates (3)t to
f(x; W) Σ (F,(x; W,). with (x W,) jE(#1}
Σ alWw,r vu)) + a(W ((((,,r.v))) (4) re(m]
(1+1)
w (t) nj
(f(x: v) (a'(w yu)) yu o' ((w yv)) vv). (5)
m
We consider the same order for all epoch for the simplicity of analysis. Our analysis can he easily extended multi-pass SGD with shuffling.
4

---

Published as a conference paper at ICLR 2024
Velue aignaal leaming LA
yfo T and uore")
value signal learting LR
yfl 1991)) and indi
wwak Signal (myl strong sigral Umy)
Valuee
weak signal limyl strong agral (jay))
Fvalue loss value
0.0
0.2
steps
staps
The progress of signal learning and the values of (x: w and L(W( under different learning rate 17. The CNN in the first two figures is trained by SGD with 0.5 (large LR), while the CNN in the last two figures trained by SGD with 7 = 0.1 (small LR). For signal learning (first and third figures), the gray lines depict the strong signal learning (w g.r, yu) by all neurons E [im]]. and the light blue lines depict see, with large LR, the value of CNN oscillates around y. and (1- (x; W()) is going to increase, which, as our theory indicates, incentivizes (w.rr, yv) to increase. In contrast, with small LR, (w.rr, gv) would stay at the same scale as its initialization.
Figure 2:
the weak signal learning (w..., UV) by all neurons E [m]. As
In such a simplified setup, we aim to explain that, when SGD training belongs to certain oscillation regime, which typically occurs under large learning rate 1j. the CNN is guaranteed to make progress in learning the weak signal y v. Here by oscillation, we mean that the values of the CNN [(x; W(!) keep oscillating around the label y during training. This phenomenon greatly contrasts with known results for feature learning when gradient descent training converges smoothly under relatively small learning rates (Allen-Zhu and Li 2022 Cao et al.) 2022).
Review: small learning rate training regime. Firstly, we make review of what may happen when using SGD with a small learning rate r). The following proposition proves that in this case the CNN can not make much progress in learning the weak signal y v.
Proposition 1 (Small learning rate training: single training data (informal)). Under mild conditions on (d, m, oo |||||2, [lv]))), if we choose learning rate 1j S m/(6]|u/]2) small enough, then with high probability, the training loss can smoothly converge with
{K< [[<o, s ((0ollv1222.
max r(())
Please refer to Appendix D for more details about the proposition. It shows that in the small learning rate training regime, the CNN only learns the weak signal y v to the same scale as its initialization. CNN trained in this manner may fail to generalize to testing data without strong features (substituted by a noise patch E), because it would make predictions relying mainly on the random noise. On the contrary, in the following we intuitively explain that under certain large learning rate training regime, the CNN can learn the weak signal up v to a constant level higher than its initialization. Such a phenomenon is depicted in Figure 2 on an 8-neuron CNN trained by SGD with ry = 0.1.
Theoretical motivations:
large learning rate regime and oscillation. When using a large enough learning rate 77 that exceeds the twice inversed smoothness, the weights of the CNN would keep oscillating, which makes the value of [xx; W())) fluctuate around y. The key finding towards our theory is that the fluctuations of f(x; W(O) around y would not cancel with each other. Instead, the oscillation accumulates over time, which serves as the engine driving the learning of the weak signal y v. In the sequel, we explain why the cancellation does not happen.
The core idea is that, with reasonably large learning rate, the CNN weights will be quickly enlarged from the learning of strong feature and then keep oscillating, but still stay well bounded. As result of the SGD updates (5), the summation of the gradient terms is also well bounded. More specifically, let's look carefully into the dynamics of learning the strong signal y u. For some time steps to. l and certain neuron r E [m]] it holds from (5) that
((1) = (1) yu)
(w(to),
(ollttl.u)))) yu) R Nor
Σ
(1 vf(x: W())) (wlo) sun)
(6)
Now we split the summation on the right hand side of (6) into two parts: one part is St containing s such that y (x; W(()) > and the other part is S containing such that yx(: W(+) < 1. It turns that if the weak signal component of the CNN relatively small compared with the strong signal component, the whole behavior will be dominated by the dynamics of the strong signal component. wr In other words, when yx(; W(e)) > 1, the inner products (w/+), yu) would also take relatively
5

---

Published as a conference paper at ICLR 2024
large value. Conversely, when yx(x; W()) < 1, the inner products (Wa.r) yu) would also take relatively small value. Consequently, in view (6). we can see that the total increase of (w yu) and decrease of (w yu) during the oscillation period are approximately balanced, i.e.,
(s)
Σ (uf(x w(6)) (wle) yu)
Σ
(1-yy (f W())) (wee). yu).
SEST
vf(x:W()))
relatively large
SES
vf(x:Wo)
relatively small
Consequently, the summation of 1 - yx(: W()) over & E S would take a larger value than the summation of (x; W(,) - over E St. This means that the whole summation
Σ (uf(x: w - Σ (1- (1- uf(x: w())) - [(f(xx (uf(x: w 1)) 20.
RESTUS-
#ES
BEST
That is, the oscillation of f(x; W(()) around the label y over time does not tend to cancel with each other. Instead, the summation of the fluctuations would have a determined sign. Furthermore, if the CNN values bounded away from the label by a uniform constant (i.e., the magnitude of the oscillation), we can further prove that
E RES+US-
(uf(x; w()) - -1 x 2766 max(|$+|.|sT]] 2 2(0 (41 - to)).
This is the key motivation behind our theory for studying the oscillating SGD. With 7 in hand, we further show that once the weak signal component of the CNN is still small, which means that the weak signal hasn't 't been well learned, the linear accumulation of the oscillation would incentivize
the learning of the weak signal (w yv) by careful analysis of its updates 5
Outcome of oscillation. Based on previous discussions, we can arrive at our result for the simplified setup of this explanatory section: the oscillating SGD can indeed make progress in learning the weak signal y v, which helps the CNN to generalize to new data points which possibly lacks strong signal y This is summarized in the following (informal) theorem and corollary.
Theorem (Large LR training, single data case (informal)). Under mild conditions on dimension
d, width m, initialization on, and learning rale n > m//4[[ if the SGD training (5) oscillates
in the sense that (x; W(0)- 11 2 for some constant 8 >> and each t 2 0, then with high
probability there exists t" < Timax with Tiax poly(d, m, n 5-11 "//uull =Ivlll ') such that
Σ o((w)) 8, 1621"
m
rElM
Please refer to Appendix Cloor Cfoor formal and detailed statement of Theorem and its proofs. Theorem shows that via oscillating SGD training, the CNN learns the weak signal y to a constant scale of 8, which is typically much larger than the scale of its initialization, since
1
Σ rE(m)
a((w yom vv)) & Ō (M <d< m
Σ ((WW"".sv)) [m]m
7TA
whenever the initializations of the CNN is small. We remark that here we mainly consider neurons with j and testing data with label since the CNN is trained only on a single data with label y.
Implications to the simple signal-noise model. Our findings could also be adapted to explain the setting with data model considered by Cao et al. (2022). In that case, one data point x = (y μa, E consists of single signal patch y- and a single Gaussian noise patch ę. Therefore trained neural network can generalize to new data points only when it learns the common signal vector μ..
As is shown by Cao et al. (2022), under small learning rate training regime, if the data model has low signal-to-noise ratio (SNR), that is, the strength of the noise patch is relatively stronger than the the strength of the signal patch, then overfitting the training data would result poor generalization (harmful overfitting). That is because the neural network would memorize the noise patch quickly so as to fit the data, and consequently the signal patch is not well learned. In contrast, we can show that under the oscillating SGD training regime, the signal can also be well learned even with a low SNR. The mechanism behind this is still that the oscillation during training would accumulate and incentivize the neural network towards signal learning.

---

Published as a conference paper at ICLR 2024
4 MAIN THEORY
In this section, we present our main theory on benign oscillation of SGD training with large learning rates for the setup introduced in Section We will first introduce the key conditions and assumptions required by our theory in Section 4.1 Then we present our theoretical results in Section [42 Finally in Section 4.2
we also compare large learning rate oscillating training to small learning rate training.
4.1 KEY CONDITIONS AND ASSUMPTIONS
Before presenting our theoretical results, we first outline the key conditions and assumptions needed on the model and the training dynamics. Firstly, our results are based upon the following conditions on the initialization scale do. dimension d, number of data n, and neural network width m.
Assumption (Conditions on hyperparameters), Suppose that the following conditions hold: (i) the CNN weight initialization scale do = @(max{[lul]e || (y.a)-vV--- dd-122); (ii) the dimension
d = -An², polylog(m (iii) the signal strength: [|v|]2 S 0.11|uu|2. I|ull2² 1v S n((zzd)-
(iv) the learning rate m//4]]u| S S 2m/(5)) u (12) (v) the weak data fraction p S e for some small constant c.
We explain the conditions in Assumption 3 one by one. The conditions on the initialization scale do and the learning rate 7) are to ensure that the whole training process is well bounded while oscillates (rather than converging smoothly). The condition on the dimension d puts us in the regime of high dimensions for which independent Gaussian noise has small correlations. Finally, the conditions on the signal strength separate the strong signal from the weak signal by fn-norm. Also, we ensure that the data are not too noisy by restricting the variance of the Gaussian noise.
The next assumption is on the training process, which requires that the SGD oscillates. For simplic- ity, we denote the index of weak training data points lacking the strong feature patch as W. Assumption 4 (Oscillating SGD). We assume that there exists a constant 5 E (0.2, 0.8), such that fxx, (()) - 1| 2 holds for any 2 0 such that is & W.
Through Assumption 4. we require that the value of (x(: W on data points with strong features oscillates around the desired value, 1, by scale of E (0.2, 0.8), i.e., the magnitude of the oscilla- tion is least 6. Here the range for 8 is only for technical considerations simplify the theoretical analyses.
It is notable that Assumption 4 liplicitly requires that the learning rate 1 should be scaled properly. A large forces the training trajectories to escape from the regular region, while a small r shall result in smooth convergence. In both cases the phenomenon described in Assumption 4 does not happen. We also remind readers that the 1) condition in Assumption 3 is only sufficient for the regularities such as boundedness and sign stability. Readers can refer to Appendix C.7 for a discussion of the necessary conditions of Assumption
We remark that in general the dynamics of the training process could be quite subtle when oscillation happens, and there exist other more complicated patterns of oscillations if one deliberately chooses a specific learning rate 77. Our work focuses on a relatively simple but common pattern of oscillation. It turns out that under the oscillation pattern in 4 we can show the benefits of oscillation on the generalization properties of the CNN. Actually, we can also extend our theoretical analysis to a weakened version of Assumption 4 that the time average of I W(O) - 1| is larger than 5.
Finally, we remark that we only assume the oscillation on strong data, since intuitively on weak data the CNN fits the label via the weak features and the noise (both have smaller strength than strong features) and may converge slower and more smoothly. See Section 4.3 for experimental evidence.
4.2 MAIN THEORETICAL RESULTS
Our main results are that, under previous conditions and assumptions on the hyperparameters and the training dynamics, the CNN can make enough progress in learning the weak signal v thanks to the oscillation happening during training. We refer to Appendix(Efoor a detailed proof of the results.
Theorem 5 (Weak signal learning: oscillating training with large learning rate). Under Assumptions and w.p. least 1/poly(d) there exists 1 poly (d, m, n, n,557 -n "1 ,
7

---

Published as a conference paper at ICLR 2024
Veller aignall lemming
(ec -12
velue signul leaming,
Value olsome Ne:W")
Lanal akc signal 11-10
weet sggal ()-11 streng sigrall ( 1-1)
strong Nignall (1-1
wesk date weet date fon
weak 031a wesk
strong
108gs
steps
stags
Figure 3: The dynamics of signal learning under large learning rate Marge 1.2 and small learning rate (1) Tsmall 0.1. The values of signal learning are obtained by characterizing the inner products j.r. u) and (w (t)
j.rt v). can seen that when using the large LR, strong signal learning as well as the NN outputs will oscillate, during which weak signal will be gradually learned. When using the small LR, strong signal learning will converge quickly, and the weak signal learning will stay at the same scale as its initialization.
such that
1
Σ rE[m]
((w (in)))))))) m
1
(mmd)) rE(m]
Σ
alw
8
max
je(+1)
m
In contrast, under the small learning rate regime, the CNN would not learn the weak features, which is the following proposition with proofs in Appendix F
Proposition 6 (Small LR training). Under Assumption 35 on (d, m, (d,m, n, oo, ||u|22 l1 if we
choose learning rate 1 I m/(6||u/) small enough, then with high probability, the training loss can smoothly converge with
[KWW)/--v))] S @(0ollv1122.
max re(d))rrE(m)
Division of generalization. Suppose we are given a new testing data point (x", x²) with an input only consisting of the weak signal Then reliable prediction can only count on utilizing the weak signal In the regime specified by Theorem 5 there holds y fxx: W(1) 2 6/4- - o(1) > 0 corresponding to correct prediction almost certainly. ly. In contrast, when applying the small learning rate, as specified by Proposition 6 the trained NN fails take advantage of the weak signal v from the data x". Therefore, it will be likely to make the prediction based on random guess
x v", ;0) )²)
(the randomness stems from the random initialization and the noise patches E 5 Conseguently, note that the weak data takes up , fraction of the dataset (see our data model in Section 2). SGD with large LR will achieve ((p) higher test accuracy than SGD with small LR, demonstrating the benefit of oscillation and large learning training in terms of the generalization ability.
4.3 NUMERICAL EXPERIMENTS
In this part, we conduct numerical experiments to demonstrate findings on "benign oscillation. We follow the same data generation model and optimization algorithm as we described as Section Specifically, we consider dataset with n 16 and |W| 2, that is, p 0.125. The dimension d == 64, and the number of neurons for each direction j is m = 8. We generate the data with strong signal ||u||2 2 = 2, weak signal ||v||2 = 0.4, and noise |E||] R of 0.8.
Weak signal learning. We run the SGD to train the CNN with two different scale of learning rates: a large learning rate Marge = 1.2, a small learning rate 7small = 0.1. We plot the dynamics of signal learning for each neuron
[m] from these two training regimes in Figure The first two figures plot the large learning rate training, and the last two figures plot the small learning rate training.
As we can see from Figure 3. with large learning rate SGD training, the CNN can effectively learn the weak signal to a scale much larger than the initialization. On the contrary. by small learning rate SGD training, the CNN does not learn the weak signal since it just remains at the same level as the initialization. This demonstrates our main theory in Section 4
Furthermore, in Figure 3. we plot the values of y W()) on certain data points i E [n] and the value of L L(W()) for the two training regimes. In specific, we plot the values of fx,; (()) on a strong data é & W (randomly sampled) and the value of fx;; W(+) on the weak data i E W. As can see from the large learning rate training case, the value of ff on the strong data oscillates while
the values of f on the weak data do not. This matches our theoretical assumption in Assumption 4 that the oscillation in f value only happens for strong data. Also, for the small learning rate training
8

---

Published as a conference paper at ICLR 2024
case, the values of on the weak data converge slower than those on the strong data. This is because on the weak data the CNN mainly uses the noise to fit the target which is of lower strength than the strong signals strong data. But still, the noise out weights the weak signals and consequently the CNN makes no progress in learning the weak signal if trained smoothly.
Generalization properties. Finally, we test the CNN trained by two different learning rates new testing data generated in the same way as the training data, The testing data size 32 with 4 weak data points. We repeat the testing evaluation over 5 random seeds and take the average. The result is that for the CNN trained by Marge the test accuracy is 99.38%, and for the CNN trained by 7small the test accuracy is 03,, matching our theoretical insights that large learning rate training benefits NN generalization. For the CNN trained by Nemall, it misclassifies certain weak data points. As we previously discussed, on data without strong signal, the CNN approximately uses random guess.
5 RELATED WORKS
Large learning rate NN training. Gradient descent training coped with large learning rates for deep learning is receiving an ever increasing attention for recent years (Cohen et al.] 2020: [as- trzebski et al. 202T] Andriushchenko al.] 2023). For GD training, the phenomenon of "edge of stability" (Cohen et al. 2020; 2022) showed that the sharpness of the loss Hessian would finally hover just above 2/1 and thus a larger learning rate would prefer a flatter minimum and possibly
better generalization, and have received great attention in recent years (Arora al. 2022 Chen and Bruna 2022; Damian et al.) 2022 Wang et al. 2022; Zhu et al. 2022b). Besides, Li et al. (2019) studied the regularization effect of large learning rates of SGID initialization which results in better generalization than using a small initial learning rate training. Wu et al. (202T) studied the implicit bias of SGD with a moderate large learning rate for overparametrized linear regression. Wu et al. (2023) then studied the implicit bias of large learning rate GD training in logistic regression. In addition, Andriushchenko et al. (023) showed that SGD with a large learning rate can help NNs to learn sparse features from data, but did not provide rigorous theoretical justifications. We highlight that our theoretical work on large learning rate SGD builds upon a multi-pass fashion of SGD and a feature-noise data generation model (see Section 2). which is different from previous works (Li et al.)
2019 Wu et al., 202T] Andriushchenko et al. 2023) where noise-aprroximated SGD is adopted for analysis. Also, we study the behavior of large LR SGD by focusing on the role of oscillation, which is also largely different from the prior works.
Feature learning in deep learning theory. There has been long line of research in deep learning
theory from the perspective of feature learning during training of neural network (Allen-Zhr and
Li 2022
Wen and Li. 2021| Zou et al. 2022; Cao et al., 2022 Chen et al., 2022 Zou et al. [202]] Huang et al. [023] Yang et al. (003).. The idea is that, by explicitly characterizing the dynamics of
feature learning during training, one can figure out how different algorithms and data structures can
influence the learning of features by the neural network, further uncovering the properties of interest in deep learning, e.g., ensemble (Allen-Zhu and Li 2022), adaptive gradients (Zou et al.. 2022). the phenomenon of benign overfitting (Cao et al., 2022). data augmentation via mixup (Zou et al., 2023), etc. Specifically, the work Ca et al. (022) showed that under small learning rate regimes, training on data with low signal-to-noies poor generalization abilities of the neural network. Our work extends this line of research to the less theoretically understood regime of large learning rates by characterizing the feature learning process when oscillation happens during gradient descent and explaining its benefits to generalization.
ratio (SNR) would result in harmful overfitting. leading to
Further related works. Please see Appendix A for more related works.
CONCLUSIONS
This work theoretically investigated NN training with large learning rates and established a theoret- ical framework to understand the oscillation phenomenon. We revealed the benefit of oscillation to the NN generalization, which we summarize the phenomenon of "benign oscillation". Our theory demystified the phenomenon based on a feature learning perspective and showed that the oscillation can drive the learning of weak but important patterns from data that are crucial to generalization. Our theory shed light on the understanding of large learning rate NN training and provided useful guidance towards the optimization analysis when smooth convergence is guaranteed.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENTS
The authors would like to thank the amonymous reviewers and area chair for their helpful comments. This work was done when ML and BW were visiting the Department of Computer Science at the University of Hong Kong. DZ. acknowledges the support from NSFC 62306252.
REFERENCES
ALLEN-ZHU, Z. and LI, Y. (2022). Towards understanding ensemble, knowledge distillation and self-distillation in deep learning. In The Eleventh International Conference on Learning Repre- sentations.
ANDRIUSHCHENKO, M., VARRE, A. V., PILLAUD- -IVIIN,, L. and FLAMMARION, N. (2023). Sgd with large step sizes learns sparse features. In International Conference on Machine Learn- ing. PMLR.
ARORA, S., LI, Z. and PANIGRAHI, A. (2022). Understanding gradient descent on the edge of stability in deep learning. In International Conference on Machine Learning. PMLR.
CAO, Y., CHEN, Z., BELKIN, M. and Gu, Q. (2022). Benign overfitting in two-layer convolutional neural networks. Advances in neural information processing systems 35 25237-25250.
CHEN, L. and BRUNA, J. (2022). On gradient descent convergence beyond the edge of stability. arXiv preprint arXiv:2206.04172 041722
CIIEN, Z., DENG, Y., WU, Y., GU, Q. and LI, Y. (2022). Towards understanding the mixture- of-experts layer in deep learning. Advances in neural information processing systems 35 23049- 23062.
COHIN, J., KAUR, S., LI, Y., KOLTER, J. Z. and TALWALKAR, A. (2020). Gradient descent on neural networks typically occurs at the edge of stability. In International Conference on Learning Representations.
COHEN, J. M., GHORBANI, B., KRISHNAN, S., AGARWAL, N., MEDAPATI, S., BADURA, M., Suo, D., CARDOZE, D., NADO, Z., DAHL, G. E. ET AL. (2022). Adaptive gradient methods at the edge of stability. arXiv preprint arXiv:2207.1442 14484.
DAMIAN, A., NICHANI, E. and LEE, J. D. (2022). Self-stabilization: The implicit bias of gradient descent at the edge of stability. In The Eleventh International Conference Learning Represen- tations.
EVEN, M., PESME, S., GUNASEKAR, S. and FLAMMARION, N. (2023). (s) gd over diagonal linear networks: Implicit bias, large stepsizes and edge of stability. In Thirty-sevntth Conference on Neural Information Processing Systems.
HE, K., ZHANG, X., REN, S. and SUN, J. (2016). Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition.
HUANG, W., CAO, Y., WANG, H., CAO, X. and SUZUKI, T. (2023). Graph neural networks provably benefit from structural information: feature learning perspective. arXiv preprint arXiv:2306. 13926.
HUI, L. (2020). Evaluation of neural architectures trained with square loss cross-entropy in classification tasks. In The Ninth International Conference on Learning Representations (ICLR 2021).
JASTRZEBSKI, S., ARPIT, D., ASTRAND, O., KERG, G. B., WANG. H.. XIONG, C., SOCHER. R., CHO, K. and GERAS, J. (2021). Catastrophic fisher explosion: Early phase fisher matrix impacts generalization. In International Conference on Machine Learning. PMLR.
KAUR, S., COHEN, J. and LIPTON, Z. C. (2023). On the maximum hessian eigenvalue and gener- alization. In Proceedings on. PMLR.
10

---

Published as a conference paper at ICLR 2024
LI, Y., WEI, C. and MA, Т. (2019). Towards explaining the regularization effect of initial large learning rate training neural networks. Advances in Neural Information Processing Systems 32.
PESME, S., DIEULEVEUT, A. and FLAMMARION, N. (2020). On convergence-diagnosiie based step sizes for stochastic gradient descent. In International Conference on Machine Learning. PMLR.
PESME, S., PILLAUD- VIVIEN, L. and FLAMMARION, N. (2021). Implicit bias of sgd for diagonal linear networks: provable benefit of stochasticity. Advances in Neural Information Processing Systems 34 29218-29230.
WANG, Z., LI, Z. and LI, J. (2022). Analyzing sharpness along gd trajectory: Progressive sharp- ening and edge of stability. Advances in Neural Information Processing Systems 35 9983-999 9993-99994.
WEN, Z. and LI, (2021). Toward understanding the feature learning process of self-supervised contrastive learning. In International Conference on Machine Learning. PMLR.
WU, J., BRAVERMAN, V. and LEE, J. D. (2023). Implicit bias of gradient descent for logistic regression at the edge of stability. arXiv preprint arXiv:2305.
Wu, J., Zou, D., BRAVERMAN, V. and GU, Q. (2021). Direction matters: On the implicit bias of stochastic gradient descent with moderate learning rate. In International Conference on Learning Representation (ICLR).
XING, C., ARPIT, D., TSIRIGOTIS, C. and BENGIO, Y. (2018). A walk with sgd. arXiv preprint arXiv:1802.08770.
YANG, N., TANG, C. and TU, Y. (2023). Stochastic gradient descent introduces an effective landscape-dependent regularization favoring flat solutions. Physical Review Letters 130 237101.
ZHANG, C.,, BENGIO, S., HARDT, M., RECHT, B. and VINYALS, O. (2021). Understanding deep learning (still) requires rethinking generalization. Communications of the ACM 64 107-115.
ZHU, L., LIU, C., RADHAKRISHNAN, A. and BELKIN, M. (2022a). Quadratic models for under- standing neural network dynamics, arXiv preprint 2XXi:22055.1788
ZHU, X., WANG, Z., WANG, X., ZhOU, M. and GE, R. (2022b). Understanding edge-of-stability training dynamics with minimalist example. In The Eleventh International Conference on Learning Representations.
ZIYIN, L., LI, B., GALANTI, T. and UEDA, M. (2023). The probabilistic stability of stochastic gradient descent. arXiv preprint 33X1v:2303.13093
ZIYIN, L., LI, B., SIMON, J. B. and UEDA, M. (2021). Sgd with a constant large learning rate can converge to local maxima. arXiv preprint arXiv:2107.1177:
ZoU, D., CAO, Y., LI, Y. and Gu, Q. (2022). Understanding the generalization of adam in learn- ing neural networks with proper regularization. In The Eleventh International Conference on Learning Representations.
ZoU, D., CAO, Y., LI, Y. and GU, Q. (2023). The benefits of mixup for feature learning. In Proceedings of the 40th International Conference on Machine Learning.
11

---

Published as a conference paper at ICLR 2024
CONTENTS
Introduction
Our Contributions
2
Problem Setting
3
Understand the Oscillation: Single Training Data Case
Main Theory
4.1
Key Conditions and Assumptions
Main Theoretical Results
4.3
Numerical Experiments
5
Related Works
6
Conclusions
Further Related Works
13
Preliminary Lemmas Concentration
13
Proofs for Single Training Data Case (Section 3)
14
Basic Properties of Training Dynamics and the Two-1 Lwo-Layer ayer CNN
15
C.2
Fundamental Reasoning towards the Weak Signal Learning
18
Proof of Theorem 13
19
C.4
Proof of Lemmas Appendix C.I
19
4.4.1
Proof of Lemma |4
19
C.4.2
Proof of Lemma
20
4.3
Proof of Lemmallo 16
20
Proof of Fundamental Reasoning (Lemma) 17)
25
C.6
Proof of Technical Results
28
C.6.1 Proof of Proposition
28
C.6.2 Proof of Proposition 19
31
C.7 Discussion: Necessary Condition for 5-Oscillation
32
Single Training Data Case: Small Learning Rate Regime
32
D.I Stage I. Exponential Growth
34
D.2 Stage 2. Stabilized Convergence
35
Proofs for Main Theoretical Results (Section
38
Preliminary Analysis
38
12

---

Published as a conference paper at ICLR 2024
E.2 Overview of Analysis
40
Proof of Theorem
Proof of Lemma
42
Proof of Lemmal3
46
E.6
Proof of Technical Results
49
E.6.1
Proof of Proposition
E.6.2
Proof of Lemma 15 for Multiple Data Setting
49
E.6.3
Proof of Proposition 33
50
E.6.4
Proof of Proposition 34
52
Multiple Training Data Case: Small Learning Rate Regime
53
Stage I. Learning Strong Signal Exponentially Fast
Stage 2. Exploiting Strong Signal
F3 Stage 3. Memorizing Noise
62
A FURTHER RELATED WORKS
Additional related works large LR NN Training. Ziyin al. (202)) Zhu et al. (0022a): Ziyin et al. (2023); Even et al. (2023) also study neural network training with large learning rates. More specifically, the work of Ziyin et al. (2021 2023 is from the perspective of loss landscape of neural network optimization under large learning rates and different signal-to-noise ratios. In contrast, we explain the better generalization properties given by large learning rate training through the lens of feature learning, which has a different target and provides a different viewpoint. Zhuu et al., (2022a) explain the "catapult phase" exhibited by large learning rate NN training on neural quadratic models. Even et al. (2023) investigate the impact of large learning rate on the implicit regularisation of (S)GI) over 2-layer diagonal linear networks.
Diagonal linear neural networks. There is line of theoretical works the training of diagonal
linear neural networks (Pesme et al., 2020) 2021; Andriushchenko et al. 2023 Even et al. 2023) where the impact of large learning rate also investigated (Andriushchenko al. 2023 Even al.
2023). As shown (Andriushchenko et al. 2023 Even et al.) (023), for the diagonal linear neural networks. large learning rate training lead sparse features, which is somehow related to dynamic analysis. More specifically, turns out that our theoretical analysis not only indicates that the weak signal is properly learned (i.e., for (Wy.r, yv) O, it increases), but also be leveraged to prove that all the negative parts (i.e., (w-y.r yv) >> and (w wyrr, yu) >> 0) are "unlearned", that is, they are pushed towards zero (we did not explicitly prove it since an upper bound of these negative parts are sufficient for our analysis, see Lemma 16 or Lemma 31). Therefore, once we prove this, we can actually conclude that the model not only learns the weak signal, but also implicitly learns "sparse" solution to some extent. Also, learning more useful features, which is the outcome of large learning rate SGD, can sortly suppress the noise memorization, since the more noisy model could lead to higher sharpness than the model that largely learns features to fit the training data. This may also connect to the sparsity the learned model.
B PRELIMINARY LEMMAS ON CONCENTRATION
In this section, we give samtle concentration results to characterize the probbbbrbbbii con- centration properties of the random elements involved in our problem. Throughout this paper, fix a small constant failure probability p = 1/poly(d).
Lemma 7. Suppose that n 2 8 log( 4/p), then with probability least p. we have that
Hi E [n] = 1H f(1 [m] - n
4"
13

---

Published as a conference paper at ICLR 2024
Proof of Lemmal 7 See Lemma B.1 in Cao et al. (2022) for proof.
Lemma 8. Suppose that n 2 8 8lg((4/p), then with probability at least 1 p. we have that
2p
[W]
7
Proof of Lemma
This follows from the same proof as Lemma
Lemma 9, Suppose that d = (((log(An/p)), then with probability p, we have that
o.d/2 < | - dz/d/2,
(e:) - 20 vdlog(2n/p)
hold for all i, [n].
Proof of Lemma 9
See Lemma B.2 in Cao et al. (2022) for proof.
Lemma 10. Suppose that d 2 (log(mm//p) Then with probability at least p. we have that
oo collu||2/25
ju) S v /2log(16m/p) col|u||2 je{+1))r(m)
max (0)
min
ju.juu 2 V 22log(16mm//)) oo co||u||ee
(0)
jE(LI))rE(m
0ollv|la/2
max je(=1),rE(m
jv: - v (1mmppmmp)) ool|v|1z
min re{=1]rrEm
(0) jv. 2 - 22lloo col|v|12.
doop vd/4 S
max j [w 6.) S 2/ log((6mm//2)) Vd, Vi [e), rE(m]
Proof of Lemma
TO
See Lemma B.3 in Cao al. 2022) for proof.
C PROOFS FOR SINGLE TRAINING DATA CASE (SECTION 3
In this section, we give formal statement and detailed proof for our main results on the single noiseless training data setup, Theorem
We begin with the formal statement on the conditions and assumptions required for Theorem Firstly, we put requirements on the data model, initialization, and learning rates.
Assumption 11 (Conditions on hyperparameters). Suppose that the following holds:
1. The learning rate m/(4[|ul(3) S 17 S 2m 25|ull)
2. The weight initialization scale @ (11ax(/ [1v12) ...-....// d-1/2);
3. The signal strength ||v||2 < 0.01 ||l||2
4. The dimension d satisfies - [ppoyylog(m)..
These conditions are the simplified version of conditions of Assumption the multiple data setup. The first condition on the learning rate guarantees the regularity of the training trajectories, including the boundedness and the sign stability. The second condition on the weight initialization scale makes sure that the CNN the training trajectory. The third condition the signal strength separates the strong signal from the weak signal by their norm. Finally, the last condition on the dimension d' puts us in the regime of high dimensions for which independent Gaussian noise has small correlations.
initialized too large, which common practice and also helps regularize
We make some additional remarks on the choice of the weight initialization scale dg- It is to ensure that the scale of initialization is smaller than the oscillation magnitude (at least in the high dimen- sional region). A direct benefit this is that by Theorem 2 one can immediately conclude that the weak signal is guaranteed be learned the scale much higher than its initialization, improving
14

---

Published as a conference paper at ICLR 2024
over the small learning rate training regime (Proposition 1. Also, small weight initialization is also assumed the original edge-of stability paper (Cohen et al. 2020). as they need to guarantee "pro- gressive sharpening", where the sharpness at the mitiialization should be smaller than the sharpness at the oscillation phase. So the whole thing we want is a weight initialization that is not too large so that it is smaller than the scale of oscillation. Any other conditions initialization would also work this is guaranteed, e.g.. can be relaxed to du (maxx 2, [|v]|2] -1 d d) for some > O.
The next assumption is on the training process, which requires that the SGD oscillates.
Assumption 12 (Oscillations SGD: single training data case). We assume that there exists some constant 8 E (0.2, 0.8), such that (x](x; W()) 1| 2 8 for any 0, where (x,y) denotes the single data point, W(t) denotes the weights found by SGD 5
Again, refer the readers to Section 4.1 for an explanation of Assumption
12
With Assump-
tions 11 [2 our formal statement of Theorem i the following theorem.
Theorem 13 (Restatement of Theorem 2. Under Assumptions 77 and 12 with probability at least
1 (d), there exists a step T(v) such that for j = y and any i 2
T(vy it holds that
Σ
o(w jmm))))
Σ a a(w
(0) j.r -j.m jv))
4'
rE(m]
[m(m]
where 8 is specified in Assumption 12 and ((v) S 5m
|||| 2 log(moo (Iv[m
[[vl[(())
Proof of Theorem
13
Please refer to Appendix CB for detailed proof.
The following of this section is organized as following. Appendix C.I presents important properties of the whole training dynamics and the CNN, which serve as the basis for all the following proofs. Appendix C.2 presents the fundamental step that allows for proving weak signal learning. Based on that, we prove the main theorem in Appendix C.3) Finally, the remaining subsections collect the proof for all the lemmas and technical results involved in Appendix C
C.I BASIC PROPERTIES OF TRAINING DYNAMICS AND THE TWO-LAYER CNN
Properties of training dynamics. We first define some neuron subsets. For j E (+1), we define that
4002 = {r [m] (w/)) ( vu) > o}. u = fo fr [m] (wl9 We vu) < 0).
and
1/ = fre [m] (w g.r. vv) > 0). y frr [m] (w y.r vv) < <0}
By the update formula (5) we know that the gradient descent iterates the inner products
{(w im ju) h20 follows:
(t)
(w(++1) uir yu) = (w(0) yomr yu) + n||u||3 (1 - yf(x; w(ll)) o' d'((w(!)) girr yu)),
(8)
m
(1) -g.rr yu) + E
(e+1) (w (w-g.r -yu) (w
(1 yx w(i)) o' (ww (2) -uu)).
(9)
Analogously, we have that
7/lv12 (1 - yf(x: w(o)) o' ((w(f) yor (w)()))))
(w((+1) .v) = (w(()
(t) Norr yv)
(10)
m
((+1) (w --- -vv (w mg.r -yv + nllvl (1 - yf(x w()) d (-(w"g..r -vv))
(t)
Then we invite readers to some facts that helps to understand the behavior of the inner products during the training processes. First, we note that by (8) for any 24(0)
{
(w
(1) v.r. yu)
120
15

---

Published as a conference paper at ICLR 2024
stays fixed at its initialization, thus automatically keeps fixed sign. The same phenomenon that the inner products are fixed can verified on following neuron sets,
(w -g.r: yu) J1za" Vr e ( gy
120 Vr E V
{(w_) -uvi 1200' Vr v
2.
The benefit of this phenomenon is when looking the prediction f(: W()) on the single data with label y,
f(x: w
y Σ
((ww).. ((w - o ((w w.rt vu)) ((w u.r yv))
m rE[m]
(11)
By splitting the summation over E [m] according to our defined neuron sets, we can simplify (I1)
as
fx; w(
y
Σ
a
((w yu)) + y yor
Σ
a
((w
m
m
(E
rEV
y/
Σ
o (- y.r. yu))
y
Σ TEV
(- yirr: -v))))))))) (12)
m
m
rE
which only involves Wg.r with u with previous observations, we only need to track the training dynamics of the neurons appearing in
(0)
gt and w
-g. with E 2
U V - Combined
-,-
12p
Thanks to these facts and the signal strength regime in Assumption 12 we can then retreat to tracking the movements of
{ (wife Ser su) 120" Vr E 20
and { (w yu)
Vr (o) -
g.
120"
whenever the weak signal part is not yet effectively learned and the strong signal part still dominates. Ideally, only the inner products (wifr: yu), 24 take the lead.
(t)
Then a natural and crucial question the boundedness these inner products, which turns out to be the cornerstone for the subsequent analysis. A straightforward but helpful lemma indicates that the inner products that are initialized to be the maximal (resp. minimal) among all inner products continue to be the maximal (resp. minimal) throughout the training process. To put formally, have the following.
Lemma 14 (Maximum and minimum neurons). Suppose that the signs of all the related inner prod- ucts do not change throughout [f1, tel, i.e., _ u and U v.- (b) -.-ffrr for all t e [t1,
Then we have that
argmax (ww
(f1). (f1). rE(m] 3. yu) argmax( (t)
rE/m] yur yu),
argmin (w 9art yu) rE(m)
(f1)
argmin (w (t) rE(m]
-v.rt yu)
hold for all [2)
Proof of Lemma 14 See Appendix C.4.] for detailed proof.
direct profit of this lemma is that when the signs keep invariant, it suffices to track two specific indices in (4 and (t()) y.-, the maximum and the minimum, to analyze upper and lower bounds for all neurons.
16

---

Published as a conference paper at ICLR 2024
Single neuron behaves similarly to CNN. The proof of boundedness utilizes another property of two-layer CNN defined in Equation ① that exhibits the connections between the behavior of inner products (Wyrr yu) and the outcome of the model f(:; W). We state it as follows.
Lemma 15 (Single neuron imitates entire CNN). Define the major part of y [xx W) as
g(x, yi W)
= m
Σ
((.
rE(m
Suppose that there is 1 l2 such that Ugi - for all [1, Then, for any e > 0,
g(x, y: W(O) 2 implies that for all t E [ti, t2).
max (w yu) 2 (3:(51) mc)1/2
(8)(1))
re[m] Dirt
On the other hand, g(x; W(O) implies that for all I [1,, 12).
rE(m) p.ri y.r.yu S (3 (f)) (3 m2)
max (w(() (t)
Here Ba()) (0) is defined as
81 (1) max o ((w)r' yu))
Ere(m) o ((w (!) y.r, yu))
Proof of Lemma 15 See Appendix C.4.2 for detailed proof. For multiple training data setting, the proof is in Appendix E.6.2
Being a subtle condition required in the previous two lemmas, whether the signs of these inner products are invariant throughout the process remains unknown, making the behaviors these inner products complicated. The answer to this question is affirmative, as we are able to prove that, under proper conditions, the signs of these inner products are fixed throughout the process. Using Lemmas [4 and 15 we prove the boundedness and the sign stability simultaneously through sophisticated inductive argument. The formal statement this result is as follows.
We first define stopping time. Let
T(v)
= min 120
t:
Σ rE|m]
((w N.rt uv)) >
(13)
Such a stopping time helps to control the non dominninng terms in the CNN. Moreover, once the process reaches T(v), the conclusion in Theorem 13 is nearly achieved. Our results summarized as follows.
Lemma 16 (Boundedness and sign stability: single training data case). Suppose that Assump- 1/poly(d), we have the following
tions 11 and 12 hold. With probability at least 1 1-p bounds:
max(w (1) yor, yu) < 1.5 (1.05% 1/2
VI 5 T(y)-
(14)
min
w y.rr yu) 2 - log( 16m/p) ao collu|12.
Vt < T(v),
(15)
min 20r yv) 2 - 22g22/ll//aelo /2mlgg(6mm/p)) aol|v|12.
VI S T(v):
(16)
0 vx(x: (()) 33
Vt < T(v)-
Here 8 = (0) defined in Lemma 15 Besides, the sign stability holds before T( Lee 4
and v(t) +. remain invariant in and the superscript (t) can be dropped.
Proof of Lemma
16 See Appendix
C.4.3 for detailed proof.
17

---

Published as a conference paper at ICLR 2024
Thanks the stopping time defined in (13) which puts controls the scale of (w (0) jv), the major part function defined in the previous lemma dominates the entire CNN, as the negative parts (3)
(w-") y.rr -...-uu), -u), (w (1)
yor vv) can be lower bounded in Lemma 16 through delicate analysis of the
training dynamics.
Lemmas 14 15 and 16 reveal the key properties of the training dynamics and the two-layer CNN. Several remarks are put here again. Lemmas 14 and T5 are temporarily local, with the condition on the local sign stability. They are not informative until we are able extend the sign stability to wider sense, which is achieved by Lemma 16 Nevertheless, these two local lemmas are used frequently throughout the subsequent analysis, so single them out here to make the proof more readable.
C.2 FUNDAMENTAL REASONING TOWARDS THE WEAK SIGNAL LEARNING
The previous section presents several basic properties of the training dynamics and the CNN. How- ever, they are insufficient in interpreting the driving force of the weak signal learning during os- cillation. In the lemma below, we discover quantitative interpretation towards the increasing on
(wyrr, yv), which formalizes the illustration of the function of oscillation in Section Lemma 17 (Weak signal learning: single training data case). Under Assumptions pose that there exists to I L,, such that:
17 and sup-
1. The sign stability holds on [Lo, f1). Le., ie u and V +y remain invariant in t;
(t) max (w (Wa.r. yu) B (8tm) 1/2 1/2 Vt E [to, to) some 0:
3. minreemm (w Mir yu) > -0.1 and min (w 4ar -yv) > -0.1, VI E [1,, h]:
4. 1 m Er (( 9.ri vV)) < 6, vt E [to, t1]:
(t)
-2 < vf (x; W(0) < 1, A/ E [1.
Then we have that
1--1
mB
(x: w()))) 2 26 (t1 (t1-to) n/|u|/ V1.05
Consequently, we further have that for any r E Vy,+ = fo E [m]]
(whrr) (ta)
vv) > 0}, it holds that
|
B
(witt) yv) 2 (w(to), yv) exp
(11 to)
(1.05 - -8
m
Here = -8-861.05 8 with 8 specified in Assumption /2
Proof of Lemma 17 See Appendix C.5 for a detailed proof.
This lemma asserts that, stable oscillation in bounded and favorable training area leads to linear increasing lower bound for (1 - y.fe). This is the first part of Lemma 17 The second part of this
lemma relates the increasing speed of (w Wy yv) to the summation of yfe. The derivation of this part relies on the fact that a = | | approximate the ratio with first-order Taylor expansion,
(t)
(0, 1) and is close to O. This observation motivates us
(w (tx) yv)
4-11
II
añ(1 - vf(x: w()))}}
( yv)
t'=to
4-1
Σ (1- t'=lo
(1- (x w())).
The proof of the second part of this lemma justifies this intuition formally with more delicate anal- ysis. With all these collected results,
ready to present the proof of the main theorem.
18

---

Published as a conference paper at ICLR 2024
C.3 PROOF OF THEOREM 13
Proof of Theorem 13 have defined that
We prove Theorem 13 by contradiction. Recall that in the previous section
T(v)=
min r20
a ((w Σ rE(m
Birr uv))
m
With this definition, our first goal is to prove that T(v) is bounded by finite time with explicit expression. To put it precisely, we are going to prove by contradiction that
2v mo 0o Follvvl22
|
1.05
Tiv) To
log
+ 1.5
where is specified in Lemma 17 and is specified in Assumption 12 T(v) 2 To- By Lemma 16
Suppose otherwise that see that for E [o] all the conditions of Lemma 17
satisfied. Then Lemma implies that,
(To) (w yur yv) 2 (w (0)
1
1.05 1.05
p.r yv) exp
To
1.5
m
6
m8
00 Ivl2
mm.
To vo||2
where r* arginax [m)] (w yirs yvv are fixed throughout t E [0, Tol (see Lemma 14) and in the second inequality we apply Lemma to lower bound the initialization. This leads to the following,
Σ m
1
<oww (To) vv)) 2 -
1
((w (2b)
yir vv)) 2 5
m
rE[m]
which contradicts the definition of T(v), and therefore Tim < To.
The rest part of the proof is to show that the sequence
1 Σ m
olwwl ((ww)).))))
(17)
rE[m)
12f()
does not fall below 8/2. Intuitively, as long the sequence above falls below 5, the sequence would have the incentive increase, as the results in Lemma 17 are revived again based another boundedness argument. The analysis resembles the proof Lemma 16 with slight differences.
provide the following proposition with the proofs delayed to Appendix C.6
Proposition 18 (Weak signal memorization). It holds that
((w!)) > 2' Vt Tim)
m
rEm)
Proof of Proposition
18
See Appendix C.6.1 for detailed proof.
This proposition finalizes the proof of Theorem 13 and we are done.
C.4 PROOF OF LEMMAS IN APPENDIX C.I
C.4.1 PROOF LEMMA 14
Proof of Lemma 14 By our assumption that the signs of the inner products does not change through- out [t,, tz], it is straightforward that (0 (4())) for every t E [t1 tz]. The same is true for (c -.-- Therefore, we are able to drop the superscript (t) temporarily, as the attention is restricted to local interval (1,
19

---

Published as a conference paper at ICLR 2024
Regarding the maximal index, introducing r' + E Uy.t, we have following relation
argmax (w (t) g.r yu)
argmax (0)
real,. y,r grr yu),
re[m]
argmax(w yu) (w-() (t) reuy,.
y.rts yu)
(w Yor yu)
II
+
20l|ul (1(; W())))
argmax
(11) (w
yir yu)
1
20/lu
(1= W()))
m
argmax (4) reul,.
yu) (w/l) ym)
argmax(w (4)
reul,. : yu).
The same relation can be verified for (w -g yu) with E U- finishing the proof.
C.4.2 PROOF OF LEMMA 15
Again, the local sign stability assumption ensures that each inner product grows proportionally and the superscript (t) the neuron index sets can be dropped, with
Proof of Lemma 15
g(x, y: W(0)
1
Σ rE(m)
a a(w b.r. vu))
m
2m
(1- vf(: w(())) )
Σ
o ((w(tt))
gor yu))
1 1
m
m
rellg.t
t'=t
maxxe[m] of (WW yu))
1
2n 2nllu
(1-1)((x(()))
(1 (1-
vIx:
m33
M=f
a max
(0)
vir: yu))
mp3 (,
Here the second line and the last equality true because ( implies that all the positive (6) yu)
iterates by sequentially multiplying the same factor
2n 2nl|u| (1 yx(: w())).
The third equality comes from the definition of (2) Lemma 15 implies that
Thus, g(x, y; W(O) 2 c
rE m3 yort vu)
max (t) (t)
(t)(t) me
and the desired lower bound follows. The upper bound can be proved analogously and is omitted here.
C.4.3 PROOF OF LEMMA 16
Proof of Lemma 16 A roadmap is provided to help understand how every single step is achieved so that the readers can skip the details without leaving the key ideas behind.
Recap notations. Recall that, 5 the set of indices E [ml such that (w/t), ju) > 0 and
4 is the set of indices r E [m] such that (w (t) ju) < 0. Specially, let = 50 and U- y.
4 (0) With probability one, it holds that Uj U Ulli+
[m]. Let r argmax,e(m/ b.r: yu)
(0)
20

---

Published as a conference paper at ICLR 2024
and r. argm (w (w-g.r: -u), i.e., r" (resp. r.) denote the index of the maximum (resp.
minimum) throughout the process are able to extend the results in Lemma 14 globally.
We also introduce several supplemental notations here to facilitate the proof. Recursively, we define
T = min 12:
vf(x; w()) 2 and yf(x; Wit-l) < 1 t:: tt:t Tx-1,
(18)
with To 0. Similarly, we define that
T = min { t: Th-1. vf(x w())) < and yf(x: w(t-)) 2 21]. :20
and To 0. Intuitively, T3 captures the times that (x(; W just exceeds 1, and similarly for Ta-
Roadmap. From high level, three steps are required to establish the full proof:
1. We verify that the lower bound in Inequality (15) in Lemma 16 holds for all E [0, 7i] with direct monotonicity argument. Additionally, can prove that the upper bound in Inequal- ity (14) holds for E [0, T1) by using Lemma 15 and the definition of T,. The signs do not change in this stage, shown in the details below.
We extend the results in Lemma 16 E [Tı, T2) with repeated use of Lemma 15 The sign stability guaranteed from an intermediate upper bound on yf(x; W
Note that the condition on [0, Ti) (which is proved in the first step) required for the proof the second step is again true for t [0. T2). which is consequence of the second step. Therefore we can repeat the second step to extend the results in Lemma 16 to E [T2, Ts), and so on. So the results are true for all t T(v)-
The first and the last step above are relatively straightforward. However, the second step requires delicate
analysis. Here we provide more detailed roadmap for the second step. The goal is to prove the results in Lemma 16 restricted to i E T2). This would be achieved in four split steps:
2.1 Firstly, we prove the upper bound in Inequality (4) for / Ti by tracking one-step gradient descent and the upper bound for (w (h (T-1)
g.r" yuy). Then with a monotonicity argument,
(w wor yu) S (w (f))
p.rt. yu), VI Ti)-
Besides, for é (i),Ti) we can give lower bound on (w(() "w.r.,,r yu) with the help of Lemmal 15
2.2 Based the previous lower and upper bounds on (w y.r+ yu),
derive lower bound on (w (Ti) yu) by tracking one-step gradient descent. We apply this worst-case tight lower bound to conclude the sign stability. We note that this step is free of the lower bound on (!)
(2:)
y.r. yu) for t (Ti.Tal, T2). which we have not yet proved to be true.
(Ti) 2.3 Now we give lower bounds on (w -y.r. -yu) and (w -w-..r.- -wv). We achieve this by delicate usage of the lower bound on (w W.r yu) (which we have proved in Step 2.2) plus an inequality that connects the relative increment of (w!") "yrrr yu) and (w -yu) (or 15 and (66) for = Tı, and this can be fur-
(Ti)
(t) -... -yv)). Thus we prove Inequalities
ther extended to the entire [T, Tz] by another monotonicity argument since Ti is the local minima.
2.4 The remaining to upper bound (w y.r. yu) for T2). This again a consequence of Lemma 15 as exactly what has been done to upper bound (w g.r yu), t < Ti in Step 1.
Now with the roadmap in mind, are ready to dive into the details of every step.
21

---

Published as a conference paper at ICLR 2024
Step 1: Pre-T; Analysis. Lemma 10 indicates that the lower bound in Inequality (3) holds at initialization t = 0 under Assumption Moreover, the upper bounds on the maximal initial inner products in Lemma I0 with Assumption indicate that
fx; w(")) $ max (w:()) M.rt y max (w (0) rE(m D.r yu)²
re(m
= ( m 1
From this we know that T; 2 1 and the upper bound in Inequality L4 is true at t = 0.
Then the first step to do is to extend the lower (w (2) w.r: -yu) to [1, Ti Definition of T₃ implies
that yf w(0) - 1 for t E [0, Therefore for r E (
8.- Equation ② gives that
(w (++1) -y.r yyu (w(() v.r yyu) +
(1)
(1 (1-wff yf(; w()))) d' (w (1) prr -yu)
m
27y 27/lu/B
(w! -.r yu)
(1 - ys(x; w())) (w -gr mu
(19)
m
(w(1) y,rr yu)
(1)
And furthermore
( p.r yu) 2 (w wir: yu) 2-ollog(1mm/// oo po||u||l--
Taking minimum with respect to [m] gives the result. Same argument can be applied to (Ti) (w -yrr -v) So the lower bounds in Inequalities 15 and 16 hold for lor [i,
yon, yu), r 2 and (w)) yv),r y increase for all t < Tj. natural consequence is that (x: W(!) is non-decreasing in f in this stage, since every summand (possibly with the negative sign before) in the summation is non-decreasing.
Also, 8 and (TO) imply that (wyer)
Now we prove the sign stability. For E 2 (0)
(t) know from 8 that (w yums yu) (Warrs yu) > O, hence U is non-vanishing in t by induction. Additionally, for E Ug (1)
(w yir, yu) stays fixed in f, as mentioned in Appendix for E [1,
C.1
Two points together ensure that
40
4.+ = (0)))
9.+
For E u _ let's take a closer look at Equation 19 with
(w()) uyr- yuu = (w (0)
-yrr yyu)
2n u
(1 yf(x; w())) (w -urr yuu
m
= (w -y.r -yu) (1 (1- 2nl 2n||u|13 (1- uf w(o))
m
>0 |ull,"
Assumption 11 ensures that 77 < 0.4m| u1|22 < ((1-)(1)/2-mm)) so the sign change does not happen at = 0. As mentioned before, (x; W(0) I is non-decreasing in t at this stage, and putting them together we know that
1 2n 2n/|u|/3 of w (()) 2 0, W (i,
The same sign stability can be verified for (w -y.r -w-..rr--p -y), and therefore, the sign stability for ( and (t) - is ensured for t [0, Ti] and the lower bound in Inequality (15) holds for [1, T3).
-.-
Now we turn to prove the upper bound [4p Note that yf(x;; (()) < 1 for t < Ti. and the definition of Tiv) then implies that
g(x, y; W < 1 + 2( log (16mpp) ool (|llllll)) < 1.05.
Now that the sign stability holds for t E T,,, Lemma 15 gives that
max (t)
a.r yu) < (1.05.9mm)1²
(20)
rE[m]
Here 8 is defined in 15 with the superscript (0) dropped.
22

---

Published as a conference paper at ICLR 2024
Step 2.1: Bounding max, (w (.., yu) for / Ti). In order for the upper bound be tight, y.r. need a lower bound on yf (x; W() Let गj = 27) u l8/m 1/2, we have the following result.
(t)
Proposition 19. For every k 2 1, suppose that
(T-1) m Σ o( - (w y.r -yub) + + (w (Te-1) re[m]
6 -vv)) < 2 ( v.r
E
Then we have that
vs(x; W(lk-1)) 2+ / + 4r
(21)
2rj
Moreover, it holds that
yf(x; W()))) S (x: w() (1+ 8j (1 yf(x: w(l)- +2E,,-11 (22)
Also, it is notable that the result here still holds for Th 2 T(v).
Proof of Proposition 79 See Appendix C.6.2 for detailed proof.
Clearly, the conditions required for Proposition 19 is true for before TJ. So consider one-step
gradient descent & Ti 1, by Proposition 19 and Equation (8)
(Ti) (w gort yu) (w- (w D) yu) + n/|u|/
(1 yf(: ((T--)))) of ((w yut)
9.
m
( 1
S (w yir
(2-11) yu) 1 nj
7 2 172 + 47
27j
1.5 (1.058; 1/2
(23)
Here the first inequality above comes from Inequality (1). and the second inequality is derived from taking the suprema i) = 1/2 and Inequality (20) Additionally, we can further deliver an upper
bound on (x; w(T))). Inequality (73) and Inequality (74) that have been proved to be true on
[0, fil indicate that Ey. Ooūilul ( << 1. Combining with Inequality (22). it holds that
yx(x; w())) < (x; w(f (1 (1+ i- (1-uf(x; w(--1)))) o(1)
$ (1 + i (1 - yx(: w w((--11)) )² ?
+1(
< (1 + (î - 1-
12/44 ii) + (1))
(1/2 v/p/4+ 2 (1).
(24)
Since f) < 1, we know that (x; W(h) < 3 and luf(x: w( - 1 < 2. (We keep ñ in the upper bound above for deriving sufficient condition on i for the sign stability later.)
Now we look to the lower bound. The definition of Tı, T(v) and Assumption 12 implies that
yf W(1) 1 + 8, hence g(x, y; W()) > 1 + 5 - 5 1 for t E TT). Thus Lemma 15 implies that
(w(9) wrrt, yu) > 1/2 (TiTT).)
Step 2.2: Lower bounding (w yu). Note that (x::; W(:) S yf(: (f)) from the local monotonicity. Consider doing one-step gradient descent with Equation 88:
(Ti)
(T)) (w y. yu)
(w y.r yu) (I (1- [ (uf(x; w(T -1)
(T-
(w(Ti (T--1)
yyu) (1 (1- .7. (uf(x: w(T:-1) - 1))
(8,m) (1 (1-1) ij (7/2 + v v1p/4 - -o(1))
-1)
(25)
2 with 4/5
23

---

Published as a conference paper at ICLR 2024
Here the last inequality is consequence of Inequality (44) and the deterministic estimation that
{ // ((1/2 v - 1)} > 1/4.
min nE[1/2,4/5]
(26)
We note that every step above is free of the lower bound in Inequality (15). Therefore, the sign stability is true on (Ti.Ti) because all the inner products are non-decreasing in t E [T.T]]]
stability on [0, Til guarantees that for every t Ti -Mir vv). The key is notice that the sign 1,
Step 2.3: Lower bounding (w (Ti)
-yyrr yyr yu) and (w (Ti)
v
1 (x((xx; w())) > 0, 1 1
(1- uf(; w(o)) > O.
From Equation
D we have that
Ti-1
(Ti) (w Ba yu) = (w (0)
-y.- yu)
II
(1 - ri(1 - uf(x; w(1)))
t=
Ti
(w -n.- yu) exp
{-x t=0
-ii Σ
(1 - y- w(ol)
(27)
On the other hand,
(Ti)
T--1
Ti-1
yart yu)
II
11 [1+ -- (1 yf(x; w('))) S exp
Σ
π (1 - v/(; w(l))) (28)
(w prr yu)
t=
However, (wy.r yu) I (81m)1/2
(0)
(16m/p) oo ||ul| and Inequality 25 imply that
(T)) g.r yu)
(Bim) 1/2 (1/4-o(1))
2
(29)
y,r yu)
(0)
1/2 / 2 log 16m/p) oo||u||2
Combining Inequalities 28 and 29
we can obtain that -T--1 1 (1 yf(:; w())) 2 0. Together
with Inequality (7), this in turns leads to
Ti-1
0 min (w (Ti)
p.rt yu) min re(m]
( (0)
v.r yu) exp
nj
(1 yf(x (
rE(m)
re [m] -g.r g,rr yu) 2 - 22 callu||2.
min (w (0)
Analogously we have that
0 >>>>> min (w (2T)
rE [m] yor vV)
(w(())
00)
y.r. -Vv) -exp
-
1
Ti-1
Σ t=
(1- wron)
|ul|
min (w (0) rE[m]
y.r. yyv 2 v w/lloollmmmm/// - 0ol|v|22
In conclusion, we have that
max (w(!) y.r. yu) 2 0.2(33mm 1/2 tE Ts) rE[m]
rE[m] v.rt yu) 2 2222ogg11mmm ou /l|p te [T. Te),
min (t)
(t)
min (w (t)
-v.r yvv 2 (20og(1mm/p)) aoll vollv E [T,, Tz].
rEfm)
Additionally, the lower bound max (w.9) yu) indicates that the sign stability holds on (t)
(Ti, T2), since the last drop step does not change the sign of (w gir; yu). Furthermore, once the
u-sign stability holds, the v-sign stability can be easily derived. To see this, we note that the u-sign stability implies that, for any [[)] it holds that + 27/lu|B (1 yf(x; W()))mm 0.
Now that |||| > [|v]]2, one clearly sees that 1 2n/lv (1 fx w(0))/m > 0 and the vigign stability holds.
24

---

Published as a conference paper at ICLR 2024
(8) Step 2.4: Upper bounding (Wg.r: yu) for / (2)) This is exactly the same the proof of Inequality (20) in Step 1, and is thus omitted.
Step 3. Finalizing proofs. At this point, all the results in Lemma 16 have been proved be true on & E [2). is important to note that the only inductive hypothesis used for the local extension
on [T), Th) is the lower bound on (w -gart -yu) for S Ti. The rest part merely comes from the
definition of Ti and T2 and Assumption 12 So repeating the same argument extends previous steps to all t - T(v)-
Remark 20. In the proof. we implicitly utilize the fact that Tg. Ts +00, Vk N O. One may conjecture that there could be cases that for some k, uf(x; W > 1 (resp. < 1 all > Tr (resp. Te). However, Assumption 12 (guarantee by tuning a proper ni indicates that this cannot happen. One argue that once yf(x; W > 1, the Assumption 12 enables the dynamic to bounce back towards 1 with at least exponential rate. Therefore, yf(x; W falls below 1 + d within a few steps and Assumption 12 forces (x(x; W(0) < 1 6, and Ta < +00. Same argument can be used to prove that Tg +00
C.5 PROOF OF FUNDAMENTAL REASONING (LEMMA 17
Proof of Lemma 17 Let argmax, (
(g.r yu). For the step to t1. 8 implies that
y.r yu) + 20/luuB
(w (6) yomt: vu) = (w (ta)
Σ
(1 - uf-y;(x; W()))) --(xxx;;(e))
(w (5) y.r yu)
sEla..t -I ((x
+
2nl u
Σ
W(+))) (w (w.:.. yu)
(30)
sEltosti- -]: o((x:
1 Ereim) o ((w vv)) < 8. Therefore by By Condition 4 in Lemma 17 for all 8 E [to, 41. on
(1)
Assumption 12 for s such that yf W()) 2 (and thus > + 5), it holds from 122 that
g(x, y; w())
Σ a((w()) y.r, bu)) 2 5 1-
rE(m]
Hence by Lemma 15 we have that
y yu) 2 13)2
(31)
On the other hand, by Conditions in Lemma 17 for all 8 E [4, it holds that minye[m] (s)
v.r. yyu) > -0.1 and minrejma (x)
v.r vv) > 0.1, which lead to
Σ 0 (w p.r yuu) + a (w()) -g.r. vv)) x 0.12 < 0.05.
m
rE(m]
Therefore by Assumption
12 for such that yf(x; W())) < (and thus < 1 - 5), holds from
12 that
1 Σ
g(x, ys W
a(w(()) zu)) < 0.05. 0.05.
m rE(m)
Hence by Lemma
15 we know that
(w( g. yu) I (1.05 - 8)1/2, 187
(32)
Meanwhile, Condition I (u-sign stability) and Condition 2 (boundedness) in Lemma 17 imply that
(w/()) yu) (w/(o) (1o)
yu) < (w/ (m yu)
(to
g.rt yu) S B (8(mm)
1/2
(33)
25

---

Published as a conference paper at ICLR 2024
Putting Inequality
31
32
33
and Equation (30) together, we have that
2n ul
B. (8im)1/2 z
Σ
(1-9((x W(:)) ([))();(()))) (w
m
sElfo. -I]: o()2:
2n 1
Σ (1-yf(x; W()))) (((x))()))) (w ( yu)
m
2yy u
Σ
(uf(x; W(o)) (()))
1) 11) (w (4)
yu)
m
NE (f(ta -I (fx )21
27 |u 2
Σ
(1-9f(x; W(.))) (w yu)
m
-1 W/xx
27y u
(Bmm)
Σ
(uf(x; w(s)) 1)
m
xE(Bo 1J:
vs o(xx2
27 2
(5 122 (1.05 - 6)1/2.
Σ
(1 yf(x; W)))).
m
uf(x:Wie))e]
This is also equivalent to
Σ
(1 vf(x; W())))
(w (w6) y.) 2
Σ
50-120-112 (VJ(x; wlol) -1)
sE(to.h-11 vfx::Wo)e<
sElto.ti 1]: ofxx20
mB
(34)
27/ u u 11.05 8
=A(
Now we are ready to lower bound the summation that we are interested in. Since
I8s E (40.4 4 - 1]: : y/(x; w < 1} + 1(8 E (lo 4 - -]]: w())) > 1||= = 11 - lo-
we have either Ifs E [to, 1] : (x; w()) > | > (t1 to0) which by
34 implies that
Σ (1 vs(;; w(l)) =
Σ
(1- (1-yf(x; w(t))) - Σ
(uS(x; w(o)) -1)
sE(ta:t1-1]:
sE(to,t
> (11005
(6:05-87- - 6)-1/2 -1)
Σ
(yf(x: w(()) -1) A(B)
-1)
-1
v w(xx)()))) 131
2 2 -0)11/ -6) (41 - A(B),
(35)
or (s E tt 11: vf(x: w < 1)1 > (t tto)22, which by
34 implies that
Σ (1 - uf(: (1-)f(x;W(o))) =
Σ (uf(x; w()) 1)
Σ
(1 - vf(x; v(())
s=1o
=E of(x:Wol)el
w(())
26

---

Published as a conference paper at ICLR 2024
> -0)/2)
Σ (1-wf(x; W( (1.05 (.05--5 53) (B) sEltoit--1] w/(x:Woo))s1
2 ( - (4 - -1) - - (1.05- - 0)1/2. (B).
(36)
In both two cases we have used Assumption 12 to bound yx(;; W(+)) from 1. Combining (35 and 36 we have that
4-1
1 (8 5(1.05 - ((1.05-8)//3) (t1 - to) - ABB. (1- w())) 2
(37)
2
==to
Now plugging in the definition of (B) in (4). we have proved the linear increasing lower bound
for the summation, which is the first conclusion of Lemma] 17
Then we turn to prove the second conclusion of Lemma 17 For simplicity, we denote a := ||v]|//| /llll| and c (6 5(1.05 5///2//4 Note that from the v-sign stability (Condition 1)
and (10). we have that
2m v
(1 - vf(x: w())) > 0, Vt [o, - 1].
Therefore, we can lower bound the logarithmic ratio (w ww)////////// yv) for Vy,+ as (recall that i = 21/ ///l|/ll/// ll3mm)
(0)
6 1
log (1 + ani(1 - vx(; w(o)))
1=
7i(1 - -1 W())
1 r|z yx: W(.))) dz
t=
n ((1 (11= W())) +2)
4-1 a
2 + nz ys(x; W())) dz(38)
dz
Σ t=
1 1
- (+ W()))
Jo
Note that by Condition 5 in Lemma 37
-2 2
yf(x; W S 1, which further lower bounds
38
as
-.. (11 (1-1//6 v](x; W(O) +2
1-1
2îj dz
dz
1 + 1jz
i
114-1 (1 - yf(x; w()) + 2(t - to) Lt=to
dz 10m
27i(t1 to)
dz.
(39)
1 n
2012
Now applying 37 to the summation in (39 we can arrive at
7 (2e(t) - to) - A(BB) + 2(t1 - -to)
a 27j(t1 to)
39
dz
2272 dz
1+ -/2
5o
( -t) - A(B) + 2(t - to)) -lo(11 + an) + (ti -to) loog1 - 2ari)
(2c(11 -to) 1 AB)) log(1 + anj + (t1 to) log (1 + anj) (1 -2ari)) (40)
To further lower bound (40). we note that onj > log(1 + ani) > jnj since by Assumption 11
0 < am < 1. Furthermore, Assumption 11 guarrantees that < e/2 (8 - 8. (1.05 1/2/2/8 and
20 3 773 + + < 4a² < 1/5 A 25/5, so we have that
log (1 (1+ ar)) (1 - 20ri) = log (1 - =3 - 2a 17²
27

---

Published as a conference paper at ICLR 2024
3/ + 2/
log 1+
1 3/2 - 200
3a 1/
2a 17
- 37 77
2 -002
(41)
Putting (40) and 41
together, we have that
log (1 ani( (x w(o))) 2 (arje 5a²) (81 to) -BB) log + añ)
2 a (11 1 10) (B)on
(42)
And consequently have the following result, for all r Vy
1-
W. ".r..v) yv)
(ww(te) ,
II
(1 ++aari ani(1 - yf(x: W())))
(w(tt), y.r yvv exp
log (1+ -ff(xx((x w((t))
t=ta
(w(te) yv) exp
onje (t1 - tu) ABB)aa
where in the last inequality proved the second conclusion of Lemma
42 Plugging in the expression of a, and A(B), we have
This concludes the proof Lemma 17
C.6 PROOF OF TECHNICAL. RESULTS
C.6.1 PROOF OF PROPOSITION 18
Proof of Proposition 78 define two stopping times
We want to track the sequence (17 after it falls below ó. To this end,
Ti =
2 T(v)= m
Σ
a ((w(() uv)) < }.
rE(m)
min
T(
Σ o(wilf) yon (v)))) 2 8
(v)
m rE[m]
If T(v.,, = +oo, then the proof is over. Otherwise we prove that, before Ttt²² s too (possibly equal), the sequence never falls below 6/2.
Let's take closer look at the controls over the negative parts while the weak signal remain learned. Note that for E (T(y) T.,) and Vy.+. have that
1-1
20llvll
(w(t) Niri
yv) = (0)
a.r vv)
II
1
- uf w())))
==0
< (w.0).yv
exp
2nllv||
Σ
+-1
(1 vf(x: w()
Meanwhile, for / E [T(v); T.), we have that (w vv) > (8mm5)1/2 > (w!o). yv). Hence
2n 2n/lv
Σ (1 uf(: w(on)) >1, Vt
exp
1).
m
28

---

Published as a conference paper at ICLR 2024
and in consequence we have that
(1-y1(xx (i))) > 0, E E [TM) (TM)) - -1].
(43)
On the other hand, for E V- it holds that (w
(w.r v.r.
(0)
yv) < 0 and thus by 43 we have that
t-1
2nl vIl
w (8)
ygrr VV) = (w -g. yv)
II
1
(1 uf(x: w()))
==0
2nl 3yylvvl
(0)
-, -vv exp
(1 uf(x: w())))
==0
ー. -v 2 -v 2
(44)
for E (T(v): (.)), Analogously, we also have that
(t) p.r yu 2 (w
(0) -g.r- yu 2 -V2log(16m/p)) collull2
(45)
for all fllle E [T(v): T 8.). Therefore, we have that for all E (vv),,.
Eg =
of (w -yor yorr vu)) + a (w (t)
(w
y.rt yvv)
m rE[m]
(a( (w (1)
y.rr -y.: -uu) vol (w p.rt -yvi)
2 max rE]m]
2( 2 llg((6mmpp) oo =
(46)
This allows leverage Proposition 19 to upper bound yf(: w()) for E [Ty) s.v),, Specifically, we locate the last step before 7 (. when yf just bounces up over 1, which is,
T == max T Tk S Tw,s),,
where Th is defined in 18) Then Proposition 19 with Inequality 46) implies that
vf(:; w(T--11) (1 + 7i( vf(x; w())))))) 2
ux(x: W(.)))
+2E
$ 1 + ii(1 yf((x; W -1)]) + o(1)
$ 1 + 7 ( + - v12 + 4n) + o1)
27
33
(47)
where we have applied the fact that n 1. On the other hand, we have that
Σ
((w
1), yy)) 1.05,
rE(m]
for which Lemma 15 indicates that max,e (m (w (T- 1) yu) $ (1)05,8mm)12, As in Inequal-
ity 23 one step gradient descent then gives that
(Ta- y,yu) (1+ 2n/|u|B3 (1- - (x(; w(F < 1.5 (1.053) 1/2 m
(Te)) (T yu) S
3.r
Now we consider the scale of these inner products right at T(v),,LL From the definitions of T and Ta- we know that yft >> 1 between these steps (otherwise the sequence wouldn't 't fall below 8). Thus by 47
1 1< vx(:; w(0) < yf(x; w(fx.)) 33, Vt [Te [...
29

---

Published as a conference paper at ICLR 2024
We first state that 1 Ere(m) a((wy) (Ti)).))))
vVv) not far away from Note that by (43)
Σ o a(w (Tivs.a.))
.yv))
1
((w WWr ( yvv) .v)) (1+ 2nllv 12
(1 uf(x: Will
m re [m]]
m
m
re(m]
1 2 (1 (1-3)
8.
m
|
8
1
2
|
IV
6.
(48)
Last inequality uses the fact that ||v /|ll s 1/4. This shows that the sequence does not fall below 35/4 at the step T. In the sequel, we study the behavior of the sequence after step T( Firstly, by Inequalities (44
and 45 with t = T L, obtain that the negative parts satisfy
min re/m]
(Ti)).))) vir
yu) 2 - 2 2log(16m/p) oo Fol|ull2.
min rE(m]
(Ti))e)) par
yv) 2 v 2ll0(160mmm// oollv/12-
which by definition of E, in 46 implies that
a S (ogg(11mm/)) collull2) < 1.
(49)
For the positive part, we have that
max (w (.)))
(T++) yu) max (w y.r yu) < 1.5- (1.05 1/2
(50)
yor
rE(m]
rE[m]
and by the same argument as Inequality 225 (Tira.))
we
can
obtain the lower bound of
max+e(m] (w Wgr
yu).
( yu
2 max (w,, ( 11 rE[m]
yu) (1+ 2n/lul (1 yf(x; W(l
max (w y.r
rE]m]
2 0.2 (3)m) 1/2
(51)
and finally for t E (T T we have that
1
m Σ
(((w yart uv)) < 6.
(52)
With all these initial conditions 449
and 52 one can then consider all the steps T
Th > 5,L and apply an inductive argument exactly the same as in the proof Lemma to
conclude that for all & E (L(,),,L, ? it holds that
0.2 (8mm) 1/2 max (nxx(w(()
(t) yu) < 1.5 (1.05
min
(t)
D.r yu) v 22oog(16m/p) - co|lu||2.
min(
(t) y.rt vv) /2 oo vol|v|12.
s yf(:: w()) 3,
and the sign stability is also true throughout t E [T'm),,,,, Therefore, Lemma 17 and 48 implies that for any & [Ti,),,,L, 1tt" I, holds that
m Σ σ ((w(() fo vvr)=
1
> m
1 Σ a ((w
(Tivs...) .vv)) exp -2
|v]
1.5
1 8.
v1.05 - -
2
30

---

Published as a conference paper at ICLR 2024
In conclusion, we have obtained that
Σ
o(Ww.., 2 8/2, e (.V.LL (.
re[m]
If 1T) # +oo, repeat the above argument and can finish the proof of Proposition 18
C.6.2 PROOF OF PROPOSITION 19
Proof of Proposition 19
We continue with the notation rj = 2ny u l//m. Define the function
(₂{2)) = (1 + 7(1 - -=))²
Note that |/vl2 - ||u|| and that
2n frllul2
(1- (1-yf(x; w(() < 27|lu12
1,
m
m
from the definition of Tx - 1. Thus we have the following, vf(x, y; w(f))
1 Σ
o ((w(T
(Ww(T=-1) (11))) (1+ 2/l|u113
- uxx; W(Fx-11)) )²
m
m
rE[m]
o ((w(TT ,v))) (1+ 21/l 2//11112 u1=: W(l 2
m
m
rE(m)
1
Σ
(w (fo-1)
-y. . - (1- 2n 2n (1- yf(x W(Th-11))
rE[m]
1
Σ
0
(w
(Te-1)
-yr]) (1- 2n|lv11
(1- y1-yf(x: yf w((h-1))) 2
m
m
rE(m)
(ol(witt--)) yyu) + o <ow((w ((w!Tx-)) .yv))) (1 27/| (1 uf(x: w(Te- )²
m
rE[m]
1
Σ (0(- (T( -yu)) + a0 - (w F. (T-1) yw))
m
rE(m]
(1 (1-2r
2 20/1u112
,x(; w(Fc-111) )² ?
)² = ys(x; W(Ta-11). (1+ 711 - yf(x; (w-))-1)
2
1 Σ ( TT-1) yu)) + +o( - (w (T-1)
yr)) (25 - vf(x; w(hh-11))) 2
v.r
m
rE(m)
<2n<²
Suf(x: W(T (1+ ii1 yf(:; w())
+ +EE
(53)
Thus by (33 we have proved the second conclusion of Proposition 19 In the following, we prove the first conclusion of Proposition 19
By Assumption 12 we know that yx(x; W(Th)) > 1 + 5. The definition of T(v) along with with Inequality (53) imply that
hi (x(; (1= (()) = vx(x; - W(h--))). (1 + -
(1+ (x w(h- )²
2 2 1 - 5 - 0 (5))
31

---

Published as a conference paper at ICLR 2024
Now it suffices to consider the equation hg 1 0, and one easily verify that it has three roots
21 = 1
22 1 + 2
V 17 + 4fj
2ij
23 7 +
v 172 + 4ij
27j +
> 1.
2îj
And the second root 22 if and only if fj > 1/2.
Now if 0 < 1 S 1/2, then 21 < 22 < 23. and then h(z) < 1 for < = 1. Therefore
Inequality 54 implies that (x; (f)-1)) > 1, and recursively implies that f w > 1, which contradicts with the fact that yx W 2 2 (log(1mm/p) /)- col|u||2- So in order for T < +00, must have 17 > 1/2. In conclusion, one necessary condition for the stable oscillation Assumption is that ij > 1/2, and therefore
vf(x ((T-
1+2
172
4n
2rj
This finishes the proof of Proposition 19
C.7 DISCUSSION: NECESSARY CONDITION FOR d-OSCILLATION
Inequality 24
provides upper bound involving 7j. which should be compatible with Assump-
tion
12 hence
(n/2+ /1/4+)) ~1-8
+> 0=(1+=1)(VI22
One can verify with software that RHS is monotonically increasing in E [0, 1] with minimal value 0.5, when f = which in line with the weakest oscillation condition discovered in the last part. And the maximal value taken at 8 = 1 is less than 0.83.
On the other hand, Inequality
should also be compatible with the Assumption 4 which indicates
8 uf(x ((=-1)) 2+ 1
1 + 4
2n
The readers can see that it is equivalent to 7 > 8-1 (01((1 (1-6)) 6)-1/2 - 1). Furthermore, we have that
5-1((1 6)-1/2 - 1) > (1+ + --11) 1) thus it is stronger requirement on f/.
D SINGLE TRAINING DATA CASE: SMALL LEARNING RATE REGIME
This section focuses on training our model with single noiseless data point (x, y). where x = (yu, yv) contains two signal patches with much stronger than Therefore, the whole objec- tive can be rearranged by
L(W) 2 (f(x: W) -))
Σ
i Σ
o(ww..yyu) + ((Wa.rsV)) re[m]
(=
In this simplified setting, each weight vector is updated by
(++1) (c) jum (f(x; (h - (o' (o'((w yu)) ) + o' d'((w for wv))v)
w)
Then we can directly obtain the following updating rules of the inner products,
(w(())) 11) (w(() f.r u) jyn (f(x; w()) v) a d'((w(0) for yu)) ||ul (++1) (w vv (w/) j.r: u) jUn
(f(x; w()) - v) o' ('((w vv)) ||v]
32

---

Published as a conference paper at ICLR 2024
since u and assumed to be orthogonal in our data generation model. In this section, also denote the fitting residual at iteration as g(() = f(x; w for convenience.
To better prepare for the analysis of this section, we single out the following concentration results from Appendix B which provides high-probabee cost-prbbbbiltty bound on the initialization W
Lemma 21 (Initialization), Suppose that = 2(llg(m/pp) and m = 2((log(1/p)) Then with probability at least 1 p, there holds
0ol|ul1/2 < max (w J.r. S [2log(16m///ooo]lu]]
(w(t)
re(m]
6 vollv/1/2 max rE(m]
(1) jv) S 2 V2log(16m//poollx>
for all j E {=1}.
The result of this section relies on the following conditions on the data model and the initialization. Assumption 22 (Conditions on hyperparameters). Suppose that the following holds:
The weight initialization scale do = @(Iuul/a)):
The signal strength ||u||2 > -- l|v]l2:
The dimension d satisfies (poolloog(m)
Theorem 23 (Restatement of Proposition D. Under Assumption 22 choosing the learning rate
" m/6/ u| small enough and 0.01, then with probability least 1 - 1/poly (d)).
there exist
2x
Cm3
T
log
T
+
11(1
oo
[2me]l u
with T, defined in (55) (6). such that: (i) the average loss over iterations ie..
[T T decreased to 2c,
T-T Σ L(W(=)) S 2c,
S=
(ii) the model does not learn weak signal v well enough, compared to initialization, i.e. (w/ (1) j.rr v) s 2 oollvvl2.
max =E(=1),r(m
In the small learning rate regime, the dynamics go through two stages, which the strong signal will be firstly learned exponentially fast, and subsequently fully fit the given data point (x, y) therefore stabilizing the training process. The following lemma plays an important role in the expo- nentially increasing stage, for which we single it out here.
Lemma 24 (Derivative lower bound). For any T 1 to be tuned later, suppose at some time there holds
Sir u|) /mm
2or v V
max rE(m).JE(L1)
then we can lower bound the fitting residual by -ye(t) 21-T.
Proof of Lemma 24 Plug into the CNN model definition
we have that
(+) (x; w()) + (x; w()) 2 (x(:; W(O).
We can upper bound (x;; W(!)) further by
Fx(x; w(t))
Σ a((w birr yu)) a a(ww (v)
rE(m]
(ww()) fi yu) (w vv
max
rE[m]
<
Then it follows that -ye() > 7.
33

---

Published as a conference paper at ICLR 2024
D.1 STAGE 1. EXPONENTIAL GROWTH
We will mainly track the maximal inner product between w and the signal vectors v and u. i.e.,
(T max 2.
(w (1)
v)
(5(1)
max 3.r
(
(1) Jir: u)
In the following, would take
6y 2
7 max
20 ul12
(log(16mmp)))/2
(55)
|
log(2/ / (og(16m//p)
1 1--
T/2
0ol u
2 exp
log
(56)
oollu| /2 2 log 16m//)
By the conditions in Assumption
22 on ||v 12/|||/l we find T, both constants in (0,
Lemma 25 (First stage: one training data case). Under the same conditions as Theorem there exists time
2t. To
T
log
711
|
||lulp2
such that: (i) the model learns the strong signal to constant level, i.e.
max (w (Tt) (E(m) V.r
yu 24
(ii) compared to the random initialization, the model does not learn weak signal that much, i.e.,
(w] (Tl) Jir v> s 22/2loog(6mm//p aa callv]12.
max (E(+)),r((m)
Proof of Lemma 25 Firstly, we would find (w((t) ((()) Je20 having an exponentially growing upper
bound. Recursively, would have that
(T(+1)) < (T())
jum
(J(x; W(())
( - -y) o'((w vv\) 1|
max
jE(Ll)
[m]
m
(1)))
7
(())
||
max
d(((w (
m
je rc(=))rr((m)
(1)))
2m
p(()
|| (p)
m
6nllv|]
S exp
(p(())
m
Therefore, we have that
6nllvv13t
t (*) < exp
(0) < exp
/ //2mmm11mm/)) aollv/12.
(57)
It follows by the same argument that that
6nllu||3 / log(16m/1)) ool|u||2.
10)
< exp
(0) S exp
(58)
m
m
Note that the growing rates of these two bounds differ lot due to the different magnitudes of ||||p and |/vl22- Our subsequent analysis illustrates that ((() can grow into a constant- magnitude since the strong signal u is significant enough. Now we can track how well our model learns by
A max (t) yu).
rE(m]
34

---

Published as a conference paper at ICLR 2024
By the definition, A v ((t) also admits exponentially growing upper bound. For certain
E (0, 1), due to the previous upper bounds (57) and (58. m y(()) S vT/2 remains true at least until
T/2 ool 1ul22222 2 V 2 log 16m/p)
m
T
log
(59)
6n u
Consequently, until at least Ti, we can use Lemma 24 conclude that -ye(o 2 T. which enables lower bounding A Specifically, start with the updating rule
(wi(+)) yu) (ww()) g.r yu) 17 yor
yl(o)
o ('(w p.rt yu)) ||
m
2n 111
2 (w(() U.r yu)
(ww()) yu)) 03.
max rEmm
m
and take maximum over r E [m]] see that
A 2 ( + 21 - T) u
1/(1 7 AA AA 2 exp
m
where the last equality is by 1 + = 2 exp(=/2) for any 0 = 2. Consequently, we would have
(71 7 uu
1 -
A 2 exp
A 2 exp
ou u 12/2,
(60)
at least until S Ti defined in 55
Then we define another time
2i |||u
To 71
log
S Ti,
To
where the inequality due to the scaling of upon r. Plugging T2 into the exponential lower bound 60 we can conclude that
T T
4
which already grows up to a constant level magnitude by the time T2. Lastly, we plug the definition of to upper bound (Tb) as
6
2:
))
u (Ta) < exp
log
s 2 2/22log(6m//))
ou |||
In conclusion, by taking T T2. this lemma is completely proved.
D.2 STAGE 2. STARILIZED CONVERGENCE
In the second stage, our lemmas would suggest that before the model really learns the weak signal v (i.e. before maxj.r (w j.rz v) breaks the O ||]]])) upper bound), the model already fits the given data point by exploiting the strong signal u and decreasing the loss to
Lemma (Second stage: one training data case). Under the same conditions as Theorem 23 for any 0.01. there exists time
Cm3
T=
2Tc |
such that: (i) the average loss over iterations within this stage has decreased to 2e, i.e.,
Σ L(W(+)) 5 2c,
T- T +1 S
(ii) throughout the training dynamics 0 5t 5 T, there holds
max [
(w j,r
v)1 < 2
35

---

Published as a conference paper at ICLR 2024
The proof of Lemma relies the following three lemmas (Lemmas) 27 these lemmas with proofs and then combine them to give the proof Lemma 26
28 and 29
We present
Firstly, we identify when the upper bound on (w]) j.rt v) breaks and find that the conclusions of Lemma still holds before that time.
Lemma 27. Under the same conditions in Theorem 23
lake n S m/6/|ull.. There exists time
T
m
log(2) Z T
61/ v
such that
re[m] V.r. yu) 2 1/2,
max (w (f)
max =E{=1),rE[m]
(w v) S
0ol|v|12.
hold for any T kts 7
Proof of Lemma 27 Firstly, we need to adopt the exponential upper bound derived in proving
Lemma 25
6nllv (T(0) <
exp 6n
(+) S
exp
log(16m//)) oollv|12.
Then naturally find that before 7 it would always hold that
(w/1 (1) j.r: v3 s 2 (log(6mmpp)) 0o||v|12.
max jE(=I)rr((m]
Due to the conditions ||ul///lv|l 7 is found be much larger than Tt, Then proceed by induction to prove the other assertion. At time t = Tt, the lower bound max, (wirr, yu) 2 l/2 holds consequence of the previous lemma. Suppose holds until time We restate the updating rule by
(w(1 (1+1) y.r yy) = (w yor, yu) + m (1 vf(;;(x; W())) a' ((((w (.w....). yu)) ||
from which we find m (w w.r
(++1) yu) 2 max+g[m) ( yu) must hold when yf W s
1. Otherwise, once (x(: W()) > 1, immediately follows that
1 < vx(; w(O)- (x; w()) (x (x)()
$ (x; w(1) m Σ o ((w (.. or ((w(
rE(m]
Σ max (t) rE[m] Mir: yu)² + 2 log( llogllmmmmmmm (6mmp)) v311.
Consequently, for the specific neuron r" argmax, (w (w y.r: yu), there holds
(w (1+1) y.r" yu)
2 (w) g.rr: w.r..yu)
37
(w (1)
(ww...yu) ||ul|
m
(1 - 2 log (16mpp) v (1 (1- 3n
||u||
4
2'
where the last inequality is enabled by taking
m/6llul 1 and
vI -I-
Thus by induction, we have finished the proof of Lemma 27
Our subsequently analysis confirms that even before 7 the model can already the given data point by exploiting u. For the given 0 < < 1, define reference point W as
4m(1 + c)
ju
w j,r
JE (+1), r [m].
(61)
36

---

Published as a conference paper at ICLR 2024
Lemma 28.
Under the same condition the previous lemma, for all T St T there holds that vVV W W 2 2- 2-+11
Proof of Lemma 28
Recall the definition of the CNN in and that u V, so we have
VV W W
Σ
o' d'(W)) 10) .u)) (W), yu)
jE(=1),rE(m
o d'w( J.m vu)) c(1+c)
Σ
Je (l()
4(1+e)
2 max (w(t) g.r1yu)
2 2 c1+
where the last inequality is by ma (w gir: yu) 2 1/2 as shown by the previous lemma.
Lemma 29.
Continued from the previous setting, we know that for T Sts it holds that
[W
w W(+1)
w - 2nT(W 2
Proof of Lemma 29
Firstly we expand the difference by
(w
|| [w+++)) w = 2n (VL(W"), w W -n² (V
With one data point, VL(((9)- ((x; W()) admits simplified expression, where {(() f( (W(0, y denotes the fitting residual. Since the neural network f(W, x) is 2-homogeneous in W due to the activation function ((2) = max(2, 0)² we can have
(x/(x; W()), w() 2x(x; W()).
Stack these observations into the first term of previous difference expansion to obtain that
(VL(W"), w W") = e()) (Vf(x: W()). w W")
= -0o) (2/(x; w(0) (V/(x; W W*))
20(0) (f(x; W(0) - v) + p(0) y (2 v(Vf(x W()), W")).
Note that the first term is exactly (L). As for the second term, need to plug in Lemma 28
to see (VV((x W(O),, W*) < -2 0, so that
(000) (2 y Vxx (()), W
I (100)² + 26 = L(W())) 2ca.
As a result, we would know (VL( W (
W 2 3L(W()) 2ca. Next, an upper bound
on the second order term n/² |V (W( || is given by
n (I = 1" (e(()))
||u||
Σ
o ((ww!! j.r ((w..r vu)) + |
Σ
d'(w f vvi)
re(=
jE(#1).re(m)
I 0 max | 1I (2)) .72 L(W()),
since the dynamics of the inner products fw yu), (w()) j.m uv) well bounded by O(1) through- out the time we are considering. By scaling (Inax [|u||, [[v][²) < 1, we would know that
n ??IIL[(W()) & v)(( Eventually, continued from 622 we can completely prove this
lemma.
Equipped with Lemmas 27
28 and
29
we ready prove the main lemma for the second stage.
37

---

Published as a conference paper at ICLR 2024
Proof of Lemma 26
Continued from Lemma 29 for any t 2 T it holds that
|W(r)) W /
((W()) S
2ny( - + +
t
8=
Before proceeding to scale time t, it would be helpful to decompose | W | and to have an upper bound on this term,
w(()) W' PP
Σ
Jrr
W j,r
u)²
(w! jrr
w j.r
v)2
[1(
vv
uu
(w
(w(rt) jir
(Tt)
w j.rr)
|
1|vl
v
je(L]).re[m)
(TT)
2(w
2
vv
+
Ia
(0)
v
2
3.r
je(+1):rE(m)
(63)
where we exploit the fact that w is parallel to u by Lemma along the directions of u, Recall that by Lemma 27
61 and the gradient steps only updates
max jE=1,r[|m] J.r ju) = 221),
{w
(Tr)
(w max
(21)) J,r
v)
= =(oollvl2))
SEd1.rE(m
and Σ ree (w.,r. u)2 //| Therefore, we conclude that ||W(T))
also that || J.r
= O(oovd). the leading term
in
63
would be
w S Cm3/[|ul for
some constant
C > 0. As result, the average loss after iterations Tt can be bounded by
Cm3
Σ ((W()))
+ +c, Vt stsT!
t -- T +1
2m 2n/|u||3(t - Tt + 1)
T
Then we choose time T Tt + 1Cm3/ (2n))1ul11)] as stated in Lemma 26
Since l
A(m²) by Assumption 22
verify that T < T In conclusion, the final output would be
Σ
=(w()sctt? sc+ 2c.
T T-T
This finishes the proof of Lemma 26
Combine Lemmas and 26 to obtain the full version of Theorem 23
E PROOFS FOR MAIN THEORETICAL RESULTS (SECTION
In this section, we give detailed proof for our main theoretical results for the multiple training data case, i.e., Theorem 5 The proofs follow the similar idea as the proofs for single training data case (Appendix()). The readers interested in the proofs are encouraged to first through Appendix [ get the idea of the core steps. Appendix [..I. we give a preliminary analysis of the SGD training dynamics. In Appendix E.2 we give overview of the proofs with our fundamental reasoning towards weak signal learning. In Appendix E.3 we give the proof of Thcorem 5 lemmas in subsequent sections.
We prove other
E.1 PRELIMINARY ANALYSIS
Recall that W the index set of training data points which lack the strong feature patch. By Equa- tion 3 the CNN weights are updated according to
(++1) (e)
in
(f W(t)) -ve.) (a'(w (1) J.r Vi. u}) Va. 1i & W)
m
+ a' (( (1)
Vi, v)) 34. v + o' d(w
(9) frr E..) E.. + d'( (0) E.)) E.. 1fee E w/).
(64)
38

---

Published as a conference paper at ICLR 2024
Also, recall that the correct index sets for the strong and weak signal patches are defined as U = {r E
[m]] (w W.r. ju) 2 0): D == {r E [m]] (w dv) jiv 2 0
By the CNN expression for each j E {+1}, the inner products that matter are
1. positive neurons: (w j.r. ju) for E U (w (wn)) for E y
2. negative neurons: (w -j) for & u (w jv) for r & vl0 -j+t'
By (4), the update formula of these inner products of interests given by (++1) (w jor .ju) = (w......u + al/u1l2
(1 - Vi. W()) o' d'( ju)jin) 1i & WB5)
m
(wfr (141) jiv) = www...vv + nl 11l
(1 (1-v., fxx.; w())) o' ('(
(66)
Also by (64). the update formula of the inner products with noise vectors are given by
(w jr E.) fi Ex) + 7 7- (1- Ix W()) (o (( (E:. Ei)
(1+1)
m
+ d'( j.rt
(1) E.)) (E,,, 1i;e E w1) [m),
(67)
(w(t)) = (W (1) Ei) + 1. D-jvis. (1- f(x, w()) (d(((w E.)) (E.,
m
+ o'(( f. E.)) (.) 1is E ww). i.W.
(t)
At first glance, the update formulas given above seem intangible. The following proposition in- dicates that we can separate the neurons into two parts, with each individual part learning one kind of sample independently. For simplicity, we let ń = 2ny /ull/m and a = || and ft yi, (x1, w For any j E {+1 and s 2 O, we define effective running time for learning label-j-samples as
(s()) = min {l E INNN 1), y1, 1}:
(68)
with (0) = minft N:::::: yi, = j).
Proposition 30. Suppose that the sign stability condition holds before some Tsign, i.e., U
_ U+ and vit) - = for 1. Taigu. Then for such that Lg(0) S Taigao
holds that
(w (++1))
.ju) = (w//)(00) ju) (1+ - Fo) 1is, EW),,
Er (69)
(w -pr ((((1)
-ju) = (w"l)(e)) -ju) (1 (1-i) -(())) 112 E W)), Vr U,
(w((((ot1)) .jv) = (w/(/(0)) jjv) (1 an - Fe(())), Vr Vitti
-1s()))s))))), Vr Vr Moreover, for every t E (15(8), (s + 1)}, it holds that (w (t)
(w(()(o-1)) -jv) -(wly(0)) -jv) (1 (1-añ(1- - avj(1-
-Jo
(wrrr j.rju ju) (w (1 jju),
Vr E
(1)
ju -ju) (w (1 -ju). Vr E Ellij-
(t)
jv) (w (1(((1))))) .jv). Vr 1/,+i
(1())))) (w j. -jv) (w -Jr -jv), Vr E V -
Proof of Proposition 30
See Appendix
E. for a detailed proof.
This proposition helps to break down the dynamics of multiple data training into two folds. To see this, it suffices to note that the following components
Juo ((w/) }
(t)
revss (( -ivi rev s.
reu ,.
are independent with (i)ii--s and the rest inner products associated with -j.
39

---

Published as a conference paper at ICLR 2024
E.2 OVERVIEW OF ANALYSIS
The roadmap towards proving our main theorem shares nearly the same logic with the proof of single data setup (Appendix C.. Basically, long as the weak signal component and the noise component are not learned in the sense that these inner products remain negligible, we can prove that the inner products associated with the strong signal would dominate and the oscillation would accumulate at linear rate. This further gives Lemma 32 which shows the CNN would learn effectively learn
the weak signal (v)...). Meanwhile, we can prove that the influences from the negative part of
weak signal learning (w ...jv) and the noise memorization =W=1, $x). (w (t) =.. can be well
(t)
controlled (Propositions 33 Putting all together, we can prove the main result Theorem 5
To be formal, define two important stopping times follows:
min 220
t
Σ rE(m]
o ((w!l jv)) 2 8/2
(70)
T( = min
max (E(m)
max
(w Jint Ei)
max NEW
(w j.m
Ei)
2 8/4
(71)
120
xE(m]
We recap that W denotes the index set of weak data, and & denotes the Gaussian noise appearing on the lacking strong signal patch for those weak data. Also we note that Tww T(e) S +o0, where the equal sign is attainable. We then define
T min {TY) T(E)
In the first place, following the same arguments as in the single data setup (Appendix C we can derive the boundedness and sign stability results before time T Lemma 31 (Boundedness and sign stability). Under A Assumptions and 4 for fixed (+1), the followings hold with probability al least
= 1 1/poly(d):
1. it holds that 5 5 # and jut V * for any t [0, Thaxl Hence the superscript (t) can be dropped;
2. for any E [0, T we have that
max (w J...Ju) $ 1.5 (1.05%%
(72)
rE(m
where Ba, is defined in Lemmal 15
3. for any E [0, Thaxl it holds that
rE m)) J.r ju)= 2 - (2log(6mm/p) oo uu||u||e
min (w(t)
(73)
rE[m] J.rt -jv) 2
min (w (t)
dollv|12;
(74)
4. for any E [0, Th such that yı, = j. it holds that
11-,, yi, fxi,; w()) < 2.
Proof of Lemma 31 See Appendix E.4 for a detailed proof.
This boundedness and sign stability result further implies weak signal learning with an exponential rate, which is formally presented as follows.
Lemma 32 (Weak signal learning). Under Assumptions and 4 with probability at least 1 1/poly(d (d), it holds that for any j E {+1} and 0 < 4 S l2 Ti that
(1- (1-yi. fxx, : 2
8
(1 (1.05 - 6/4)²) (t2 - t1 + 2n]lu|3(1105 5/4)3'
m(100))
16
04, =
40

---

Published as a conference paper at ICLR 2024
Moreover,for V we have that
where 8 is specified in Assumption
7/ v 12
|
(w (1a+1) ,v) 2 (w j.r cvp
32m (6 5(1005-1-111111 - 5/4))) - +1)
|| [1.05 6/4)
(75)
Proof of Lemma
32
See Appendix
H.5 for detailed proof.
The last component to complete our proof of main theorem is controlling noise memorization dur- ing the training process. For simplicity, we define the maximum absolute value of the noise inner products over data
r
(w (1) J,rt Ei)
(w J.r (w....EE)) E
max (E
max iiin]
max kW
We have the following proposition to control the growth of (()) Proposition 33 (Noise memorization). Under Assumptions
and 4 then with probability at least
1 1/poly(d), it holds for any 0 S minje(+1) (Tmax) T(E) and j E (=13 that
r S T(t))
(1 + c),
Vr E [m],
vt ststs t + T(e)
where T()) Omm . of c. 1. ( for any c
Proof of Proposition 33 See Appendix
E.6.3 for a detailed proof.
E.3
PROOF THEOREM
With Lemma
31 and 32 and Proposition 33 are ready to prove Theorem 5
Proof of Theorem 5 For the j argminyee+ (Th'a J.
going prove that T bounded by polynomial time by using contradiction. Specifically, prove that
max is
T Tiix
<T30== == 17 1
32m
(8- - 8(1.05 5/4)#)
log
2 mo
1.5
|v
u
V 1.05
1.05
8/4
Suppose that the result fails, then by definition we have that
T max -(/y A T(e) >
Tzuu-
Then Lemma 31 and Lemma 32 hold on [0, T,o)) By applying the lower bound in Inequality 75 as well as Lemma 0 we have that
(2).0) rE/m) mm) j.r
max (w)
jv)
max (w rE/m]
j.r jv) exp
nliv
(6 - - 8/4)))- - 1.5-
1.05
32m
1.05 6/4
2ymo
oollvil2
ooll vo|vv|12
Vmo.
This leads the following,
Σ
(1.o) ..vv) 2 max ((w (2,0) jr
frr jv))² 2 8,
re[m
rE(m]
which clearly contradicts the definition of T in 70p. hence it must be that T3 max I T3, t00.
41

---

Published as a conference paper at ICLR 2024
In the following, we prove that T Max =Tw,)
Tie), for which our conclusion directly follows due to 70 Again prove by contradiction. Suppose that T T(e) Tivy then T(*) would reach
6/4 for time less than T2,0 due to definition of (e) in 71.. But by Proposition 33 with e = we
know (()) takes at least
mmn p
KT (4) =
log
000,
steps to reach 8/4, where T( is defined in Proposition also find that KT(())
33 Then due to the scaling the signal
strength in Assumption 3
Tj.0, which is contradiction with the
definition of (()). Therefore, we must have that Thaxx
(v)) which means that at T T
1 Σ
a((w
fo jv))
8
m rE/m]
In the meanwhile, Proposition
31 guarantees that time to T
1 Σ
a((w (t7) jv)) S 4'
rEmm
Thus, we conclude that at time t*,
Σ
a(w
(v))
Σ
((w
-Jir (v))
Ja
m
rE]m]
rE(m)
This finishes the proof of Theorem
E.4
PROOF OF LEMMA 31
Proof of Lemma 31 Recall that T Thax Th, A T(e): where
TV
min 120
t:
Σ
((W 2 6/2
m
rE(m]
(w/) J.r Ex) v
(win Es) 2 8/4 8/1/.
Te
min 120
t:
max jE (=:))r (m(
max re(m))rr(m))
We now define some notations to simplify our presentation. Recall that f = Vie Ixi, W()), n 2//lu||B/m 1//m and a |vll/||||| For fixed j. we define
$5, min {
S S- such that f(,()) 2 and (max < {1] (76)
with 5,, 0, and
Sj, = min { NEN: Sa such that (,, & W, Fe < and Fe
2 1 (77)
with $5.0 O. From the definition Ti T we know that (8,,)) & W for such that ty(5 1
T T since otherwise F1,(8,2) 8 < Moreover we define
U₁,+ = fr fre [m] (w (w() (t)(0))
jun. > o3. U₁ = free [m] (t)(0))) juu < =0)
and V are defined analogously.
The following analysis is nearly the same as the proof of one data case in the sense that each step of the proof is organized exactly the same to the proof of one data case. Therefore we suggest readers to refer to the roadmap provided in Appendix C.1 C.1 frequently for better understanding.
42

---

Published as a conference paper at ICLR 2024
We note that for tort> S T(m A T(e), which is the time scale mainly focusing on, it holds that
max m Je(] ( Ei) v
(w (e)
J.rr Ex)
a 4
((W 8 2
m re|m
Now we start presenting the proof of boundedness and sign stability with step-by-step analysis. The j is arbitrary but fixed throughout analysis. In view of the effective running time for learning lssmpess defined in (68). 76. and (77). the proofs for certain j directly do induction over
Step 1: Pre-Sj.1 analysis. Clearly at = O, the lower bounds in Inequalities (3) and 77) are
both guaranteed by Lemma 10 Also we know that (o) < 1 and so SJ, 2 1. The initialization
also guarantees that the upper bound in Inequality (72) holds
For S,,), the definition of 5211 indicates that Fe,(0) I Therefore, from Proposition 30 that the (w : .ju), r E Uz,+ and (w" ((()
jir -ju), r E 4-j.- j.- are non-decreasing in during this stage. One naturally infers that for all r E EU_,-,, holds that
(w (S,))) juu)= (w (t,(8,,11)) -ju) 2 (w (t,(0))
jir ju) 2 (1ggpp)))))) col|u||2-
ji
Same can be verified for (w (1)( jjv with r E V-j,-. Hence the lower bounds in Inequality (73 j.r
and (74) are extended to E [0, S,,l Also, for these inner products, the sign stability holds on [0, S,,), since ij < 4/5 and thus we have
1 + 2///ul 2
(1 (((0)) 21 -1 o()) 2 0,
m
1 1 2
(1 - Fey(s)) 2 - ari(1 + o(1) 20. 0.
m
(o)) Then we turn to upper bound (w juuz for E [0. 1y Note that, for such that in,ce) $ W. the definition of Thax implies that
1 - 1-82 Puses 2 m
Σ rE (m]
((w (t)( .iu)) + m rE(m)
1
Σ o ((w (t(e)) .jv))
(w -jr -ju])
(t((a))
Σ o (w (b((o)) -jv))
m
rE(m]
rE(m)
(c())) o ((w j.r
.E:)) + Σ
a(w -j.r
(c((6) (.)))
m rE(m)
rE(m)
1
((w (t)(5) ( - 2 x o(1) - 2x
2
rm[m]
As consequence,
a Σ
(ty(s) ((w fo jju)) < - o(1) S 1.05.
rE]m]
Thanks to the local sign stability, Lemma 15 implies that
max (w (x)) rE|m
juu) S (L)
j.r
If otherwise E [0, (f,-) such that (e) E W. then we choose & = min(s' > 8 (2, & W). holds that either & < S,.1. 1. or & = 5y.. For the previous case, similar argument implies that
(t((s)) juu) (w ((())) (3)( .ju) (1.05/t, (w
(78)
The latter reduces to establish the upper bound for 1z(5,,), which is derived in the next step.
43

---

Published as a conference paper at ICLR 2024
((())) ju) for 1,,1, 1,1)- Since the weak data does contributes Step 2.1: Bounding (w j.r to learning strong signal, as indicated in Proposition 30 we know that
(w (w)rr ((s(a)))
ju) = (w (w (S,)))
.Ju) (1+ ii(1 (e,()..))))
where Sy,1 max(s S 5/1 (s) & W).
We begin with proposition that is parallel to Proposition Proposition 34. For simplicity, we assume that de, (3,,3,, & W and S5.x = Sj.k - Otherwise we can find the last step before Si.x such that te, & W and leverage the previous observation in Equation E.4). Suppose that
Σ rmmm]
o
(w (1,18,x-11) -jui) 3.
t (1,18 11) -jv)) S 5//4,
((((((s)))
(w (1y(Ss.N))
.Ei)
(t((5))))
. S 8/4,
max ]E(#1),
max
then have that
f1,(81111) 7+2
172 + 47
(79)
27
and that
k S (1 77(1 (1 + 2E, (8,x-11) + ((,))
< (i/2 + /1//4+11 1))² (S,, + (S,()))))
Proof of Proposition 34
See Appendix E.6.4 for a detailed proof.
With this proposition, we can derive an upper bound on (w (ty(),)))) jju.. One step gradient (69 implies that, for Uz it holds that
(w/ (3,,)) jor
.ju) = (w j.r
(1,(5,11111 11) juu
(1 1 f7 - -s,
I (w( (S,(,, 1))) jul
1 1 1 7 2 - 172 + 4
21j
S 1.5 (1.05sm, 1/2
Here the first inequality comes from Inequality (w (t,,,_1))) juà has been derived in Inequality 788) in Step 1.. Taking ij = 4/5 easily implies the second inequality above.
79 Note that the upper bound on
(s))) This upper bound continues to hold for (w .ju) with [S,,,, S4,) because of monotonicity. [f((s))
We consider the lower bound for (w juu) with [S,1, Sy,1) and (1)()) $ W. For these s, we have that
1 8 8- fe(0))
1
Σ
((w (t((4) juu)
1
Σ
a(w
(t(()) .jv) + (negative part) + (noise part)
m rEim
m rE/m]
Σ
o ((w
(t((s) dor
jju)) + 6/2 2 + 6/4.
m
re
Combining with Lemma
15 we obtain that
max (w (g(()) .ju) 2 m) rE(m]
for [8,1, S1,1) and (,) W.
44

---

Published as a conference paper at ICLR 2024
(5.a)) yu). Same to the proof of Proposition 34 we can
Step 2.2: Lower bounding max, (Wa." assume that (1) W. without loss of generality.
Note that, while (s)(s) is not monotonically changing in 15.1.1,.1 in the presence of noise components, the inner products are still changing monotonically. as indicated in Proposition 30 Therefore, we can leverage the control over noise components to derive an approximate monotonic property. Specifically, the inner products
(( ((/ (t(()) ju)),, (aw (,(4)) -2ir ju)),
a(w (6())) jv)), -a((w ((0) fr .iv),,
are decreasing in E [8 S3.1]. From Inequality 94 in the proof of Proposition
34
we know that
1) S (1(
1 Σ o ((w
((w (1,()))))
(e, o (( (S,()))))
-j.
m
rE[m]
+
1 Σ
o ((w
(1
j.r
(G,,(,,, o ((w (6((,11-1)
-30
Sie, (i,
m
rE(m]
$ (f/2 / 1) + -EE,, + r(t((S..))
(80)
Recall that in Step 1., we proved that (5 S 2( 200gm///p oo /l]lull22² o(1). Thus from doing one-step gradient descent 69
we know that for E Mz,+, , it holds that
(g((s,)) 1) .ju) (w (tz(S,, 11)
(1 (1+ [1,()..1)))
(w)) frr
(t1(511 1 13) ju) (1+ (f/2 + vIp/4 0.1)
jr
2 0.1 m)) 1/2.
(81)
Here the first inequality is by (80). E o1) and the definition of T(g)= and the second
inequality is consequence of Inequality (26). This positive constant-level lower bound guarantees that our ij choice is sufficient for the sign stability to hold for E [5,,, S3,2), as shown in the next step.
Step 2.3: Lower bounding (w (لم-اا)) -ju) and (w (w (s()))
(w-
-j.r -jv). It suffices to consider
r E V Vーj,- and r E U--j... Inequality (81 indicates that
(w (G(S)))) .ju) jrr
9
Saa-1
(1- (1-Fuse)) ).
1
II
(1 + :i - -ss(oo)) S exp
Σ
(ty(0) (w)r juu)
Therefore,
8.1
Σ
(1 (1- fe))))))= >
Now we can prove the lower bound. For E EM we have that
$
(w ((,,))))
-Jr -ju) = (w- -ju)
(t)()))
II
(1-
f((t))))
S
(w (t,(0)) -jor -juu exp
Σ
(1 - Fests)
-
8=0, WWW
(g(00) (w -J.
juu) 2 - 2 16m/p) col|u||2.
(82)
45

---

Published as a conference paper at ICLR 2024
On the other hand, for [0, 1] such that (e)(s) E W, condition S T -Ty) A T(E) guarantees that
1 Σ
((w (b())) (.v)) -o(- -w (2(()) -jv))
m rElm]
((W (2((+)) (((,(:))) - o (( ()(()))) Sigcol))
m
re[m]
o (( (y(())) (.yws)) - o <( (1(())) (igcoot)
rE|m]
S 6/2 + 2 x 8/4
S 1.
Hence derive that
Σ (1- )((0)
Σ
(1 (1- fe)
E
(1 Fes(or) 20. 0.
SE krG
And in consequence, for E V3.- it holds that
9,
(w (1,(Ssa)) Jor
-jv) = (w (0((0)
3.r -jv)--
II
1l-an(1 - -1)()))))))))
==0
9
(1,(0)) (w -ir
-jv) exp
-aij Σ (1- (uws
(1()0) jjv (2log(16m/p)) oollv|12.
(83)
The monotonicity again extends lower bounds in Incqualities the sign stability naturally holds on this interval.
83 and 82 to E 1S,1, Sy2l. And
Step 2.4 & Finalizing. Thanks to the sign stability proved in the last step, we can now apply Lemma 15 to derive that the upper bound in Inequality (72) continues to hold for all E 1 with exactly the same argument as the Step 1.. With an inductive argument that exactly repeats the argument above, Proposition 30 impliess that for any & E N we can find 8 E N such that 15 (8t) S 1 < 17(5 + 1) and
infer that all the results in Lemma 31 holds for ts(s) with s É (5,.1.
(f) ju) (.r (t((a)) .ju) (so are all other inner products), therefore all the results in Lemma
hold for t < Tia
E.5 PROOF OF LEMMA 32
Proof of Lemma 32 For any 0 St t2 S Tá T j E {+1}, and r ut4 by 665).
27l u
(W .ju) (w (41)
(b++1)
juu
Σ
(1 (1-Bef(xe,: w(+))) ju)
m
f(x,, ((xx;WW()) WW())11
+ 21
Σ
(1- 11-,,,((x, W()))) (w (w/C)..u))
f1 SaSta
Vi, WWW
vi, (Xi,
46

---

Published as a conference paper at ICLR 2024
Note that for 0 S t1 I Tha apply the conclusions of Lemma 31 Specifically, consider the maximal neuron r* argmax ( J.n. and
(1.05) $ (Pu m)² 2
(w (1)+1) j.m
juu - (w j.rt ju}
(84)
27 21/|u|13
Σ S Vi FiJ 18, [xx,; WW
(1- (i, W()))) ((()))) (w)
m
(
Σ h
(xx;())((()))) (1- (1-,,,((x,, w(()))
(w (w])r-
Mi, Ji Mi, fix,, wi9)e1
(1100-8/44} (12. m)
where the red remarks follow from Lemma 15
Rearranging terms, we conclude from 84) that
E
(1- ff, W(o))
(85)
11 SSSS Vi, FWW Ne, (xx, W00
m(1005)
2 (84)5-
E S Ve, FW ne, :xx, Wo0311
(Ui, w(()) 11)
2 u (1.05 - 6/4)² 2
Under Assumption 3 with probability at least 1 - 1/poly(d). it holds that
1
[ta S Us. j. & WH 2
(t2 t1 1),
(86)
Combining 88 and 86), we can finally prove that
m(105))
Vi. fxx, W(+) : (1- (1-(111)))) (1.05 8/4) -ta-1 t1 +
2n 07/lu|/(11055 8/4)
Mi. WW
(87)
Finally, for the weak data i, W. under Assumption 3 with probability at least 1 - 1/poly (c)),
8
H4 < ssstii9 = j.i, w) 2p- (t2 t + 1) (1 -1.05-8/44 - -04)8)))))))))))))))))))) (t2 + 1),
where the second inequality follows from the condition on by Assumption By Lemma 31 we have that 1 fxx;;; W(+)) & for S 8 < Ti and ys j. Therefore, we have that
t
1 nr f(x w(s)) 2 16
(1.05 - 8/4) (1-(1.05 (t2 - t + 1).
(88)
9r, E.
Combining
t and
88
88
we can conclude that
8
m m1100)
Vc, (x;, W(+)
(1 (1.05 - 5/4)))) (1 +
16
2 / (1.05 8/4)
This finishes the proof of the first part in Lemma 32
Now we consider the second part. For sim-
plicity, we denote by [v]l//[[u]3 and vj 2
m. Consider that for any 0 < t < T T
47

---

Published as a conference paper at ICLR 2024
j E (+1), and r E y due to Lemma 31 view of (66). this means that
the v-sign stability condition is true on [0, T In
1+ añj (1 yo, fxi,; w()))) > 0, vO 8 S TH mux s.t. Vi, = j.
Then for any 1 S L T
maxi S. & S and C since 2 yi [xi, W(ll) S 2 due
to Lemma 31 we can lower bound the relative increment as
7i yi, sxx,; W(s)) dz
log 1 + arj(1 yo, (x1, W())))
Σ
1 7z [1 - yr fxxi; W(+)))
==1
86, =j
i( - 11, Ixi,; W(o))) +2
Σ
t
dz
Vi. (xi,; W()))) dz
2n
1 fjz(1 yi [x:: W(o)))
1 nj
V1, =j
Via =j
i i((1 Vi, f(x,; W(o))) +2
1
27 dz
2
Σ
dz
1 2ījz
21jz
V1, =]
81,
17
E (1 - Vi, (x w(())) + (4o, t))
dz
dz, (89)
1 1 2fj2
1 2-122
where for simplicity we denote ()( 114 511188144 yi, = =i}l- Now we can use Proposi-
tion 32 to lower bound the right hand side of (89 Denoting e = 8- (1 (1.05 b/4) we have that
log { 1 + ani(1 v1, f(x,; (x,(())
17 c(t - t1 + - A + 2N, (t..t)
27,,,(11.() dz
dz
00
21jz
J0
1 1-27 2nj
{ (t- 11 1)
A
+ .N((t,,t) logg1 + 2ari) + NN t) loog11 - 2avi)
2
A
-t- t1 +1)
log(1 + 2ari) + (5t(1. log {1 + 2ari) (1- - 2ari)
2
2
where A is defined in Lemma
32
Moreover since for our choice of anj < in Assumption
log(1 + 2arii 2 oñj, log ((1 + 2ori) (1 20rii) = log (1 - 402?7) > -2a221?,
and using the fact that with probability least - (/poly(d) it holds that t,(4,,) S + we finally have that
log { + azi1 - y1. f(x,,; ((()))
2 ant (c 2ari) (c--2rr)) (t1 t1 + 1) - A .lo((1 + 2ari)
2
> an E (4 41 + 1) -2o7 A.
48

---

Published as a conference paper at ICLR 2024
Finally, using (66) again, can lower bound our target
(w (1+ .jv) = (w (11)
.v) ,v)
(1 añ(1 (xs,i W(s)))
s=h
(11) = -w Ao j.v) exp
log 1 +aa(11 (xi, w(ol)) :
1=11 y1
2 (W j.v exp
anj c (t1 -1 1 20rj. 1
Plugging in the definition of A, a, and i7, we can arrive
n 1 (6 8(100 - 6/4)5)-
(1.00)) 3
.jv) 2 (w (f1) (w (++1)
jor jv) exp
32m
||u|| 8/4)
This finishes the proof of Lemma 32
E.6 PROOF OF TECHNICAL RESULTS
E.6.1 PROOF OF PROPOSITION 30
Proof of Proposition 30
From Equation
65 for r E Uz,+ and t' E ty) + 1)}, we can infer
that
n (1 fi) o' -''(( (w..... joh.) 1(i E W).
(w]t)) ju) (w (c())) juu +
(=)(())
The definition of (s) implies that for E (ty(s),ty(s + 1)). yu. = -1. On the other hand Miryo = 1, hence obtain that
(1) (w fa ju) (e,(0) ju) + un| (1-f)()) fW 1(i, E W).
Since the sign stability holds, this multiplication by a non-negative factor does not change the sign of the inner products. Therefore we have that
(w (+++1)) .ju) = -(w (1((00+)))) ju) =... (w (+)(++1) jju)
-(w!1((0) (y(00) ju)) + 7.. (1-
which concludes result for (wof) ju), E Uz Other result can be proved analogously and are omitted here.
E.6.2 PROOF OF LEMMA 15 FOR MULTIPLE DATA SETTING
Proof of Lemma 15 multiple data setting). the multiple data setting, the (positive) inner products only changes at the steps where the corresponding data label aligns with the directions of the neurons (i.e., = 1). Define
(r(((1) max a ((w (fi) .ju))
Ere(on o a(w
((w)))
(11) jju))
49

---

Published as a conference paper at ICLR 2024
Again, the local sign stability assumption ensures that each inner product grows proportionally and the superscript (f) in the neuron index sets can be dropped, with
C((((S rE(m]
1 Σ a(w (1) juu)
II
(1+
2n 20/ (1 yi (xxi,] w(())) )
rEug.1
t'e|t k.
max,e[m] m3²
((w (11) Jir ju))
(1+ 2 (1 yi, (xi,i witt))
II
m
u.j
[-]]:
Wiy 4@W
af max (m(m) (w (w))--u))
(7.()) u.j
Here the first and the third equality is true because Equation x
implies that all the positive
(w yu) iterates by sequentially multiplying the same factor
2m uuli (1 yx(: w()))
The second equality comes from the definition of (fi) in Lemma 15
Therefore, m m- Ereim) of ((w, the desired lower bound follows. The upper bound be proved analogously.
(1) ju)) > implies that o (maxye[(m (w yirs vu)) st.f(a mc and J.... j.y.
E.6.3 PROOF OF PROPOSITION 33
Proof of Proposition 33 We prove the result by induction. For the step t,, the result holds trivially. Suppose that this result holds for each step ",,". then by (67, have that
(w (++1) Jr Ei) = (w/r)
(4) jr
EA) + Σ 17
jyk,
- (1- fx::; :w())) (d'(ww))) E.)) (E.,) Ex)
m
s=f
o' ((w (+)
E. (5,, . EW)
n ll jus.
-(w()) Ex) +
(1- (1-visles (ifi w()))) d((w])) Ei)
m
mlle: 112
jui, (1 - -i. w(())) (o((w())) E.))
(Ei,
11::13
m
+ 0' d'(w((t) E..)
(E,, Ei) |3:113
1fi, [VL.eW em)
50

---

Published as a conference paper at ICLR 2024
Taking absolute value, we have that
(w (w/(t)) j.r Eii
- (w (1a)
E.)
n Eall jyh.
(1 (1-vif(x; W(r))) d'((w)o) Ei)
Jr
m
1 jun. (1 yi, (xi, (xx,;W()))) W(o)))
((( jor Ex.))
(2)
Ei)
+ d'((w (t)
jor Ei,))
(E.,.E)
1ff E wi)
||5: 12
1
Applying the definition of r(s), we further obtain that
(wo/ (e+
.5:) S r(t))
2nll - yxis W(r))| (
m
(ISS Ei)
KKE,, Ei>
|1 vi, (xi,; w(ll)| r(().
(0))
11::11
|
Now using Lemma 31 for S minje (T J. we have that [1 - Vd, f(x,, W())) < 2. Also,
by Lemma 9 it holds th s f and (1///M1 S (dd11/2). Thus we can further upper bound 90 as
max sE[n]
(w) (t++1) [t) & r(t)) +
r(s) + (1--1/13
Σ r())
(91)
m
bnodd
r +
r(t) + +5(d-1/2).
r(t))
6nozd
(r((i) - r(0) + ((2-112) Σ (T(()) - -r(o))
(((())
m
By our induction, we have that (+)) T(4)) S ((1). e, for which we can further bound 91 as
bno
max =E|n]
(w (1+1)
EE) s r(t)).
1 +
c1
Σ 1+ (+-0a-113) 1/2)
m
1 1 Gn02d
(2 (2(--1++) + (cd
(1 - L1 +1)] -(-+++11)
< st())
(1 (1+c).
18n (1+ 11 11410 +1
5 (tt))
1+
mn
where in the first inequality we have utilized the fact that [t) S s S t: = i) < 2(t-t + 11/n,, and in the last inequality we apply the condition that 0(n²) by Assumption Therefore, when
t < t1 + The - with Te = θ(m - 17 ee- (1+e) -1. (0 -)))) it holds that
max vE(x)
(w.tt1) (++1) .E)) < (()) (1 e).
(92)
51

---

Published as a conference paper at ICLR 2024
By using the same argument as proving (92). we can also show that for t t1 T(E) -1
max
(++1)
S r(())) (1 (1+
(93)
sEW
By combining (22 and (93). we can arrive at
T(+1))
max JE _e(+)))r
max
(w
(++1) jir
.Ei
max xWW
(w ((+ Eid s r(l)) (1 c).
Thus we have proved our induction statement for step t + 1. Repeating the induction completes the proof of Proposition 33
E.6.4 PROOF OF PROPOSITION 34
Proof of Proposition 34
We expand (S,,,) as follows.
1
((w (ty(())= 11) ju)) (1+ -()),,))))
(5,,), -
m
rE[m]
o (5, jvl) (1 + + - F1)))
m
rE(m]
Σ
a(
(w
(ty(5 1)) -ju)) (1- - -f,(s,, -j.
m rE|m]
Σ a
(w
(ty(S 1)1 -jv)) (1-ar(1 Se, (3s, (8,() 2
m
rE(m]
o
((w (1,(),)))) ((
Σ
a a(w -3r (ig0
(t)(22))))
rE(m!
rE/m]
0 (w jrr
,ju)) + o l(w j,r (S,(5
(1)(5,x-11) .jv))
m
rE(m)
-0(
- (w -jir
(t, 1]) -juز} -o( -o(- ( (1 -jv))) (1 (1+ 7(1 (1+
Σ
( - (w My (5,(() -ju)) +o - (w (1 - (27(1 - -(
j.r
m
rE[m]
+ T(b((,,,))
f1
(B,,,,,,,,1)) + ((,,)),
(94)
By Assumption 12 we know that Fes(S,N) + 8. From the discussion in the proof of Lemma we know that once
19
2 (F,, + ((b(5s < 6,
have that
7+ - v 172 + 4n
f1,(9,2-1) 2
21
and that
I,, S + 77(1 -1 + E1,( + T())
< (i/2 - V + Ees(S + (1)
This finishes the proof of Proposition 34
52

---

Published as a conference paper at ICLR 2024
F MULTIPLE TRAINING DATA CASE: SMALL LEARNING RATE REGIME
This section focuses on the multiple training data setup with small learning rate.
Recall that W is the index set of training data points which lack the strong feature patch. By 33) the CNN weights are updated according
(1+1)
(0)
jn
(f(x W(()) -w:)) (o' (o'((w (1)
(.r un,u)) yi, u 1( & W}
m
+ o dl j.m yu v)) yb, V + o' d'w (9)
j.r E,,)) Ei.
+ o' ((w). j.r E.)) E.,, 1f E w)).
(95)
Subsequently, by (95) the update formulas of those inner products interests are given by
nl/ull2 (1 Ixii w(1)) o ((w.) 1 & W).
(1) ju) + (w+1) j.u) (w
(w!tt)) ..v) -w ( nl v
(1 Iixis w(()) d'((w)) jv)jnn.)
m
and
(w (w1)) .Ei) = (w/ jirt 6i) + 7. 1944 (1- (1- W()) (d'((w E.)) (Si. E.)
m (t)
+ o' o'w j.r
E.))
(En, 164 E w/)
(w(1+1) (w fir E.) = (w// Ex) + -ilis.. (1- (1x, W()) (o'((w).)) Eil) (Ei.
m
+ o' ('(( j.r E..) (E.,, Ed) 1f E w)), ieW. W.
(1)
For convenience, we also write e f(x;; w()) y, the fitting residual.
The result of this section relies on the following conditions on the data model and the initialization. Assumption 35 (Conditions hyperparameters). Suppose that the following holds. For some (0, 1),
1. The weight initialization scale an = ((1uu|1a));
2. Strong signal strength ||ul|2 > Q(mm /ne) opvd and weak signal strength oy Vy 2
Ω (m (m//ne). ||v||2:
3. The dimension d satisfies d = P(polylog n)).
Theorem 36 (Restatement of Proposition 6). Under Assumption 35 choosing the learning rate
17 S m/6]|u/ small enough and é' E (0, 1), then with high probability 1/poly(d), there exist
4m
2r. collu||a)
Cm3
W W
Tt
log
= +
T' -T
11(1 () uul
[2
21JE
with T, defined in 977. iterations [Tt, i.e.
998 such that: (i) the average loss on samples We decreases 3c
Σ
min {v: f(x;; w(o))² 3e,
2n iEW=
TiSEST
(ii) average loss samples W decreases to 3c' over iterations [T,T") ie.
1 IE
((= w(0)) <3',
min
2n
(iii) the model does not learn weak signal v well enough even until T", compared to initialization, i.e.
max
(w)
(E( v
(0)
12//2oog16mm/11 vll2v Vt V
53

---

Published as a conference paper at ICLR 2024
In the multiple training data small learning rate regime, the dynamics go through three stages, which we characterize in Appendices F.1 F.2 and F.3 respectively. The following lemma plays an impor-
tant role in the exponentially increasing stage (stage 1), for which we single it out here.
Lemma 37 (Derivative lower bound). For any 0 < T < 1 to be tuned later, suppose at some time t there holds
max re(+))
(km u)/
00 jime
v)
max *E(n)
(w Ww Ei)
max
(w
jirt
Eii
VV
KEW
then we can lower bound the fitting residual -ye, 2 T for every i [n].
Proof of Lemma 37 Plug into the CNN model definition I. we have that
ye = =1- (x;; W(() (xy( w 1 (x W())..
if WS, we can upper bound (x1; W(() further by
(x; w(0) = Σ
o ((w (o vu)) + (( (t) v/)) + ((w (2) 2.rr Ei)
re(m)
(ww/ zu)² + (w yvm + (w/h E2) S T.
< max rE]m]
Otherwise, if E W. we also have
(x W())
Σ ol ((w(()) pir: E.) aa Mir: vv)) uv)) + o a(( p.r Ex)
rE(m]
(w/o) v.r. Ei)² Ei) + (wwl) virn Bv)² vv) - -ww!) y.r {:) S.
< max rE(m]
Then it follows that -ye(t) 2 1 T.
F.1 STAGE 1. LEARNING STRONG SIGNAL EXPONENTIALLY FAST
In this stage, we mainly track the maximal inner product between w and the signal vectors v and u, with extra attention to the maximal inner product between and the noise vectors.
(1)
max rE(=
(w (t) J.r v)
(1)
max re(+)))rE(m]
(w (t)
Jor u)
p(t) max
(w
j.r: {2)
(1)
i E [n]]
(=(=)),re(v
(())
max jE(=1).rE[m]
(w] j.r: 5i
i W.
Lemma 38 (First stage: noise). Under the same conditions as Theorem 36 ever since initialization, at least until time
nm
T4 =
311( + p)azd
there still holds that
max (() sE|n]
VdopVd, Vd.
max (((1) S God, Vd.
(96)
iEW
Proof of Lemma 38 For those inner products with noise vectors, Vi E [m]. the updating rules be- come
(w
(w(ttt)) jir
Eti
<
(w jirt
Ex)
+
7
|
(o'((w (x)) ((E., + o' (6 E.,) | Ei)
1fis e w/)
m
(1)
Ec)
6n
Exi) 1(Ea, (ww.2/.... (5,, E.)) 1lue
j.rt
m
54

---

Published as a conference paper at ICLR 2024
By taking maximum [m]] conclude that n((
T 6n (T!e (K P
(....
1f4s E W)),
vi vi
Similarly, we also have that
f((+1)
1ii E w)), vi W. 6n (r (EI. Ei) + [E., Ei)
We then use induction rigorously prove our conclusions. Firstly, (66) holds at time Now suppose that (96) holds until some < T4. Fixing some E [n].
f
(1+)
6noopp
(E.. 1ii w)) ((),,
1=0
bnooopdd
2T (1+ p) .)) od
2n
31jo0o, V4
S 000 Vd.
The first inequality is by induction hypothesis. The second inequality is because that there are at most T/n many it's would equal i and at most pf many i would be in W, and we also use Lemma 9 to control the correlations between noise vectors. The third inequality is by 2 16n log( 4n /p) for Assumption 35 while the last inequality is due to T < T4. Similarly, we can also control (+++) for some fixed E Was as
T Gnooondd
(++))
Σ
(Si.,E))
+ (E.. Ei)
lfir w))
1=0
@nooapdd
[3o
2T
(1
of of, ( 4n?/p)
2n
S God Vd.
where the second inequality is because there are at most T/n many it' would equal i E W. In conclusion, (96) holds at least until TT..
In the following, we would take
6/200²d
T max 200l|ul|2 ( (200g((6m//)))
(97)
|| log(2/ / log( (16m
L 20 B|||| exp {
T) (1))((-)][lu)
(98)
3(4+ p)
By the conditions in Assumption 35 on ||v /13/ |ul
we find t, i both constant in (0, 1).
Lemma 39 (First stage: signal). Under the same conditions as Theorem 36 there exists time
4m
2r
T 71( 71
log [ool|u||22
such that: (i) the model learns strong signal to constant level,
max (w)) (E(m) fr
ju) 2 (+e{+
(ii) compared to the random initialization, the model does not learn weak signal that much, iee.
(T
v) < 22/22ogg110 (16m/))m))))) collv]|2
max Je(1])rr[ml
55

---

Published as a conference paper at ICLR 2024
Proof of Lemma 39 Firstly, would find { 4 k200 having exponentially growing upper bound. Recursively, we would have that
((++1)
I (p))
+
max (=
jym
(f(x; W - 3) . o' o'(( o'(( ov)) 11v
[m]]
m
(+()
+
(())
| _e(=1),r(()
max
d((
S (1))
2g
d(0)
| 4
m
6nl 6nllv
x exp
(1(1)
Therefore, we have that
6nllvl
Gnll Gnllvvl2
(+)) S exp
(0)) S exp
V ool|v|12
(99)
m
m
follows similarly that (+)) S exp (6n(L - p)
6r7( p)
(0) S exp
/ log(16m/p)) ool|
m
m
The extra factor P appears because only P proportion of data points would contain u, and therefore contribute evolution of (()) Note that growing rates of these two bounds differ lot due to the different magnitudes of (1 - []]]]][||| and ||v|22.
Our subsequent analysis illustrates that ((()) can grow into a constant-level magnitude since strong signal is significant enough. We can track how well our model learns u by
A
rE L. u),
max (w (t)
(t)
max EE
(w (t) Mm 1rr u))
By definition, A
(+) also admits exponentially upper bound in (100) For a certain
T E (0, 1), due to the exponential upper bounds 99 and (100). max maxf(((t) (((1) I / /T/3 is true at least until
VT/2
T
log
Gr/(1 1
collu||2v log 16m/p)
Moreover, since we have (1 p) |u|l > ozd/n by Assumption 35
we also know Tj s T4 where
T4 comes from Lemma 38 Therefore
(#) < S vds VT/3, 1(0) Goo ooo VT/3,
VE S
Consequently, until at least time Ti, we can use Lemma 37 to conclude that Vi, e > 1 - which enables lower bounding (+) the following.
The 4g sample would be used to update parameters, according to our multi paass SGD updates 3
If E W, then (w ((+1) juu) (w ju). holds for any j {+1} and [m]. If is W but .) m u) 2 since that neuron will not be activated.
max,(w1f. (w(+1)
(t+1)
Vi. 11, then max,
Otherwise, only if & W and Vi, 1. the updating rule becomes
(1+1) u) (w(t) (4) u)
+ 77
V/, (()) d' (w (1) u/) ||u||
(wirr
m
2m(1
1 max (w u).0
(w u) +
m
Take maximum over E [m] to see that
( A((0
2 T) 1
17(1 (11--)||ulf AA 1 2 exp
m
56

---

Published as a conference paper at ICLR 2024
where the last equality is by 1 exp(z/2) for any 0 S I 2. Consequently, when is large (larger than n),, we would have
7 - [[]-r)|lulß Σ 1fi $ W.yi. = =1} -A
1 2 exp
P'5
17(1 T) ||
(1 (1-p)) p).1))
2 exp
collu|12/2.
(101)
4m
at least until step S TI We use the fact that E St fir & W,y. = 2 (1 p)t/44 because the sample labels are balanced (Lemmal) 7 and 1 - proportion of samples come with the strong signal. In the same manner, we would have that
n(( (((1-T) (1[L=)\lu|((1p))) )
1 2 exp
oolluul2/22
(102)
4m
Define the time when A both break 4
4m
2r.
T2 17(1 r] p) u
log
S Tı,
Tol Col|u|/2
where the inequality is due to the scaling of upon т. Moreover, also need that T2 S T+
where T4 is the time that (w). (f) j.r: Ei), (w(f) j.r: &i) remains in ((ooo And this requirement also achieved by the selection of and Plugging T2 into the exponential lower bounds (IOT) and (102).
we can conclude that
(Tb) 2
24
which already grows up to a constant level magnitude by the time T2. Lastly, plug the definition of T3 to upper bound (T(Ts) as
24
2c |u|p ))
(Ta) s sexp
log
/ log(16m/p) oollvl12 S 2// log(16m/p))
oollvil2.
(1 (1-77 r1
In conclusion, by taking 7 T2, this lemma is completely proved.
F.2 STAGE 2. EXPLOITING STRONG SIGNAL
In the second stage, our lemmas suggest that before the model really learns the weak signal or memorizes any noise vector, the model already fits a proportion - of the data points (i.e., strong data) by exploiting strong signal
Lemma 40 (Second stage). Under the same conditions as Theorem 36 there exists time
Cm3
T T
2n
such that: (i) the average loss over iterations within this stage has decreased 2e, i.e.
1
Σ
min
y f(x,; w( 3e,
2n
riSisT
tEW
(ii) all through the training dynamics 0 S T. there holds that
kww! f.r: v) s 2 1og(16mm ||v||2,
max re(=
(iii) all through the training dynamics 0 5 there holds that
(w j.r, Ex) S S0oap re
(w()) (w) j.r
Ei) s Va.
max (E(L)),rE(mjeee
max
57

---

Published as a conference paper at ICLR 2024
In studying the second stage, firstly identify when the upper bound (w (w that the conclusions of Lemma still holds before that time.
j.m v) breaks and find
Lemma 41. Under the same conditions as Theorem 36 take 17 S m/6/
There exists a time
2/2
m
log
2 7
6r
co colivllav log
such that (96) and
(w j.m v) s 22/2logge log (0g
(1)
max (w re(m]
(0) j.m 2 21/2, Vj {+1),
max
(e(+))
hold for any T St.
Proof of Lemma
41
Firstly, we need to adopt the exponential upper bound derived in proving
Lemma
39
(67llv|B2t
S
exp
(0)) S exp
V log(16m//p) aollv112.
m
Then we naturally find that before 7 it would always hold that
(w (1) jirt v) = 2 2//2log(1mm/p)) vollv112.
max [e(=))rrEm)]
Due to the conditions on Jul 1l.. T is found to be much larger than T Then we proceed to
prove the other assertion by induction. At time / Tt, the lower bound maxj.r (w (1) ju) 2 1/2
j.r.ju)
holds as a consequence of the previous lemma. Suppose it holds until time If i E W, then
(w]. J.r jju) = (w ju) holds for any j {=1),r E [m]. If i, & W but yt. = 11, then (t+1)
(1+1)
wir _u maxrefmJ (wf. i.r u} 2 0 since that neuron will not be activated. Otherwise, if is W and Vi,- = 1, consider the updating rule
max (w]
(wi,r u) (w u)
2 (1 U1-yyf((x.; w()) d' ((w 1. u)) ||ul/2.
m
from which we find ma (w (1+1) vuu) 2 max,g(m), (w (. yu must hold if yi J W(o) < 1. Otherwise, once vs, (xx, W(!) 1, it immediately follows that
1 < yc, (xx, w())= Fu, (xi,i w F F-u., (x,, w())
< Pu, (x W w(1))
a((w 1, Mi, u)) + (((w ff: v. v\) + ((w()...)) Ev))
rE]m]
$ max (t) u/ of |1 2 + of -[(m]
Consequently, for the specific neuron r" argmax (w 1,r u)², there holds
(++1) u)
(w()) (t)
1, u)
3n
(w (a) (w u) ||1||
m
(1 llog(16m/p) /p) .0llv - agoOe)) (1 (1- 37
u
m
5
where the last inequality is enabled by taking
1 |v + odd
n
To
8 8log(16m/pp
(t+1)
Therefore, we find that max,e[m)
(wl.
u) 2 1/2 must hold no matter what i, is. In the same way,
1.r
one can also obtain max4e[m] (w
(++1)
u) 2 1/2. By induction, the induction proof is complete.
-1,
58

---

Published as a conference paper at ICLR 2024
Our subsequently analysis confirms that even before Tl, the model can already fit those data points with strong signal by exploiting u. For the given < e < 1, define a reference point W as
4m(1 + +c)
ju 1
j j [m].
(103)
Lemma 42. Under the same condition as the previous lemma, for all T SIST,, there holds
y V<VVf(x; W w 2.
for any i W.
Proof of Lemma 42
Recall that the definition of CNN in ① and that u 1 span(v, E.). We have
that
MA M (VXxx W()), W*)
a' d'( jirt Biu)) (wi... yuu)
m jE(=1),r(m)
d d'(W (inn) 4(1
Σ re(+1)rr[m
b
4(1+c)
max (w(t)
Bi.r yau) rE(m
22 (1+
where the last inequality is by max, (w ju) 2 1/2 for any j E {+1} as shown by the previous lemma.
Lemma 43. Continued from the previous setting, for T Sts if $ W, there holds
[W())
W
[w(+)) w 2 2n(](x W(t)) - vi.) -2nje" 2
Proof of Lemma 43
Firstly we expand the difference by
[|w()) w || - W -
2n V W()), w W*) -12 -/2-((00 -1(00)
(1)))
: WI
(104)
Since the neural network (x; W) 2-homogeneous in W due to the activation function (()) max(2, 0)2, we have that
fx W()), W() = 2x(:: W()).
Stack these observations into the first term of previous difference expansion to obtain
(e( ((x') w(()) w W e!!) (2f(x,,; ((()): (Vf(x;, W()), w:)
= 20 (f(x; W(!) vi + 1 yi. (2 yı (Vf(x,) w(l),, W*)).
Note that the first term exactly 2xf(x, W(O) y; ). As for the second term, since in & W, we need to plug Lemma 42 to see 2 - yi, (Vf(x,,; W()),, W < -2 < 0, so that
(1) yi. (2 - Vi, (xi( W(O), W*) - ((())
2 " + 2e2.
As result, would know that
3
V[xx, w()), w W*)
> (f(x;; w(1)) y1,) 2-2 -22
2
59

---

Published as a conference paper at ICLR 2024
Next, upper bound on the second order term r/² (VL((( is given by
17
(1)
2
[V
1/2
11112
||u||
Σ
se(L])rr((m]
+| 1
Σ
d' ((..... -1EE;,
Σ
d'(W ((w Ex))
rE(=1))r(m)
jE{=1))r(m
- (0maxx(
livl 111) 17²² (1)2
since the dynamics of inner products (w yu), (w gv), (w Es) are well bounded by O Via scaling 7) (maxx | 12, ||
|s, 113) & 1, we would know n7 1 fIV W v
ne Eventually, continued from (104). we can completely prove this lemma.
Lemma 44. Continued from the previous setting, for T st 7 if E W, there holds
[ - - |w(++) w 2 Croo (1vv12 + ood).
(105)
Proof of Lemma 44 Same as the last lemma, from the SGD setting, we have that
[|w(+)
w P.- - l| w
2m V ) w - W - (1000 [VS( W
(106)
and from the 2- h-homogeneity, follows that
fXx, w("), w(0) = 2x w())). Since W. every V (....((x., W()) is in span(v, (v, E,, E.,) 1 u, so
fx (()), w = 0.
As result, the first term in (166) can be bounded by 2n( fxx,; W()), ( W*)
= 4n (f(X,,; W(9) v..) s(x. W
S 12n
Σ
a(w
jor E.,)
Σ
((w
jor Vi,
v)) v)) +
Σ
al(w Eii))
m
(m(
re(
jE(L1),rE(m)
I Onoillv + a0)
We can also deal with the second term in 106 by
(8) 7
[xs(x 11
< 2/²
(1)2
||
Σ
d' d((w
(t) j.r E.,))
rE(+
+1|v12
Σ
o' o'(ww())
J.r Bi Mi, vi) + 11.
Σ sE(+1]/r[mi
d'lw! fr En.))
re
< 5
a ()
where the last inequality due to (t)) being (1). Since we already take 7) S m/6/|ul the second term of (106) is ignorable compared to the first term of (06).. Therefore, we conclude (105). n
60

---

Published as a conference paper at ICLR 2024
Equipped with Lemmas 41
42
43
and
44
ready to prove the main lemma of second stage.
Proof of Lemma 40
Continued from Lemmas 43 and 44
for any t 2 7 it holds that
_ (f(x. W(l)) vv.)
1
1i $ W}
T +
W (T') (
W 3 2 - T 1
+ e - p) + (Ilvl1++ tzzd)p
Before proceeding scale time is helpful decompose bound,
| - w and have an upper
[W())) (T))
W
E
(w J.r
w. jir
(w (T)) f.r
wj.r v)2
P 5.5 (w (Tt)
-wj
1vv13
rE(=)
2
vV
u111
(w (21)
la
P 3.
-w
M
1 22
2(w (T
.u22 + 2(w j.r: u)²
(w!?r") (2*))
.v22
(Ty1
||u||
llv12
+
P
E
for
je(
+|[
VV
uu
P&.E
(w
(T')
w
(107)
M
where E denotes the projection matrix onto linear space sp Ev). In these deriva- tions, exploit the fact that w* is parallel u, and the gradient steps only updates w along the directions of u, v. Recall that by Lemma 41
max (w(T)) ]E(=]]rE(m] frr iuu) = 22(1,
(w( J.r .v) = (0oollV12)
=
max je(1l))rE(m)
(!! jo
.Ei = O(aua,
max
the leading term in 107 is Σ)e(+1), (WJ,. u ///ll Therefore, we would conclude that
[W(T) w < Cm3 /||u|| 2. As result, the average loss after iterations T can be bounded
by
Σ
1i. & W) ! (f(x,, w()) yi.)²
T +1
T
Cm3
$ 27l 2 -
+ + p) Coz oz
Then choose T' T + [Cm² (2nee |u| as stated in Lemma 40 Since |ul//\ylB 2 mmm²).
verify that T < T where T is given in Lemma 41 until when the weak signal cannot be fully learned. Moreover, we also have T < T_ where T. is given in Lemma 38 when the noise is not memorized.
In conclusion, via scaling of s <<(Cp([[M[1 + ozd)), the final output would be
() f(x; w(o)) } SIST
min
1
Σ 1ii $ W} 22 (f(x. w(0) vi.)²
2n
1- 71
ieWs
s
<et 2 p) + Co (1|v o
< 3e,
ending the proof of Lemma 40
61

---

Published as a conference paper at ICLR 2024
F.3 STAGE 3. MEMORIZING NOISE
After the second stage, the model already fits those data points with strong signal by exploiting u. Subsequently, in the following third stage, the residual e for i W would remain quite small, preventing the model from learning u.
On the contrary, since fx;; W()) ( is still far from its label Yi for each sample i E W without the strong signal u. Therefore, the weight vectors would still evolve in the directions perpendicular to u. In Assumption 35 the ratio between the weak signal v and the typical noise norm op d is scaled by
|vll opVd (vr) (1²)
- H 1
(108)
Therefore, the model will eventually interpolates the whole dataset by memorizing noise vectors (E), W, Now we define new reference point W by
W w 4m(1 + E))
1 1s =
& 1e:l12
11 =
J E (+1), [m].
4
1
NEW
where wj.r defined in (03) is the reference point we used in the second stage. The following lemma an adaptation of Theorem 4.4 of Cao et al. (2022) onto SGD with square loss.
Lemma 45 (Third stage). Under the same conditions Theorem 36 for some e' E (0, 1), lel
||w(T) - -W
T
2ne
where T is the end of the second stage in Lemma
40
Then we would have that
(w(l fir
Ō(oollvl22).
jE(L1),rE(m)
until L S T'. Bul the whole dataset has already been interpolated during this interval,
Σ min yy: - f(x;: wro))3 s 3E'.
2pm
NEW TSKS
Proof of Lemma As the closing stage of the training dynamics, the evolution dynamics during this interval straightforward based on all techniques developed in Appendices [ and Inner products
(w E.), (w()) j.r Ei)
Jie
would firstly go through substage in which they exponentially increase to constant level (just as stage 1). And then the model will all samples indexed by W by memorizing these noise vectors in polynomial time. All through this interval,
(w (t) v) would stay O
due to the scale of [|v|22/(pp in 108). A detailed proof is omitted here for readability.
L
Combine Lemmas and 45 obtain the full version of Theorem 36
62


Reviews:
[{"review_id": "iAWzxr7owB", "reviewer": "Reviewer_1fN5", "summary": "This paper studies the generalization benefit of using large learning rates in stochastic gradient descent. Specifically, in the setting of a two-layer convolutional neural network, it is shown that although using a large learning rate causes the loss value to oscillate, it indeed further enables SGD to do feature learning. The main result is proven under the assumption of a feature-noise data generation model, where the strong and weak features are separated by the $\\ell_2$ norm. Empirical evaluations are also provided to support the theoretical results.", "questions": "1. How to justify the feature-noise data general model? E.g., is this a natural assumption for real-world dataset like CIFAR-10?\n\n2. The authors discussed some necessary conditions of Assumption 4 on the loss oscillation. Are there any comprehensible sufficient conditions?\n\n3. The authors mentioned a bit about the edge-of-stability regime. Can the authors expand a bit more on this? For example, how is the oscillation assumption related to EoS?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The paper is well written and easy to follow, and the authors have explained the theoretical intuition clearly through the example of a single training data in Section 3.\n\n- The generalization benefit of large learning rates is an important topic in the community. This paper presents an interesting result in this direction, though the feature-noise data generation model seems somewhat artificial.\n\n- The theoretical analysis in this paper is very solid.", "weaknesses": "- It is not clear if the feature-noise data generation model is a natural model that contains separate strong feature, weak feature, and noise. \n\n- The network structure seems to be tailored to the feature-noise data generation model, as it applies a separate weight vector to each of the patch. Although the authors claimed that the main results can be further generalized, but it is not immediately clear how.\n\n- The oscillating condition that $|y_{i_t} f(\\mathbf{x}_{i_t};\\mathbf{W}^{(t)} - 1|\\geq \\delta$ is proposed as an assumption, rather than being proved.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DbyZHXuM46", "reviewer": "Reviewer_ahqJ", "summary": "The authors study the effect of large learning rate SGD on a prediction task with a one hidden layer CNN network. More specifically, they study a binary classification problem with weak and strong signal patches and theoretically argue that there is a generalization separation between small and large learning rate SGD training:\n- for small learning rate, SGD is unable to learn the weak signal\n- for large learning rate, SGD is able to learn the weak signal     \n\nThey argue that the oscillatory behavior of large learning rate SGD is a crucial feature of this fact. \nThey also illustrate these results with experiments.", "questions": "- On top of the questions raised above, I really would like to understand whether the setup described above has can also guide on what appears to be a simple problem like diagonal linear networks where the oscillations lead to sparse features.\n\nDoes the analysis of the authors shed light onto this problem ?\n\n- Also, it appears that the initialization is very small ($d^{-1/2}$ with a large $d$). Can the authors comment on the necessity of such an unusual initialization ?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The study of SGD with large learning rates is believed to be crucial to understand the good learning properties of neural networks. Yet, its analysis is in many cases very difficult to handle: the oscillations, the movement due to noise are technically challenging to analyse. \n\nIn this perpective, the authors do a very good job providing a setup for which they 'prove' that such a dynamical behavior leads SGD to good generalization.\n\nOn top of this, I find the paper very well written, the setup very clear and the explanation with the toy model on Section 3 very good.", "weaknesses": "In my opinion, here is a weakness of the paper:\n\n- the authors claim to perfectly prove that the oscillatory behavior of the SGD iterates lead it to learn the weak signal, but they need to assume that the iterate oscillate in the first place. While they show that this oscillation is *consistent* with their hypothesis, it could be great that the authors comment a bit more of this necessity to assume this. How difficult would it be to remove this hypothesis ? Is the problem to control that the iterates do not diverge ? Or on the contrary that they do no converge locally ?\n\n- If this is the second option, could the authors add some (bounded) label noise at each iteration to show this? This is what is explained to be done in a series of paper like *Label noise (stochastic) gradient descent implicitly solves the Lasso for quadratic parametrisation* L. Pillaud-Vivien et al., COLT, 2022. Could the authors comment on this?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "rRN8CU8W4r", "reviewer": "Reviewer_yxwb", "summary": "This paper studies feature learning when the learning rate is large, showing that when there is a strong oscillation in the training, only data points with weak signals are learned", "questions": "See the weakness section", "limitations": "", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 1, "strengths": "I think the message and the insight is sufficiently novel and relevant -- how large learning helps \"selecting\" a subset of data points to be learned. \n\nThe data generation model of strong and weak patches is also quite interesting and can serve as a good starting point for future works\n\nAlso, the signal to noise ratio of the data and gradient plays an important role in the proof and discussion and, therefore, I think the result does catch some level of essence of SGD training in neural networks. Although, on this point, I think the authors should compare with the study of how signal-to-noise ratio affects the learning at a large learning rate in (1) https://arxiv.org/abs/2107.11774 and (2) https://arxiv.org/abs/2303.13093", "weaknesses": "In my opinion, what prevents me from recommending this paper is that the problem setting feels too artificial. The following are the specific problems in my opinion\n\n1. The problem setting. First of all, what is a ReLU^2 activation function? I have never seen this. Is ReLU more essential to the proof or is the quadratic effect more essential to the proof? Does the result hold for ReLU? Does the result hold for the quadratic activation? This is unanswered in the paper. To me, this activation neither feels theoretically appealing nor practically relevant\n\n2. Problem setting 2. The second layer is not trained. Essentially, we understand that training with one layer is very different from training multiple layers simultaneously. For example, see https://arxiv.org/abs/2205.11787\n\n3. Problem setting 3. The model architecture -- the authors refer to the model as a \"CNN,\" which just does not feel right to me. I doubt if the majority of readers would agree that this model is indeed a CNN. \n\nIn summary, the point is the same, the problem setting is not sufficiently simple to be considered theoretically essential, nor is it sufficiently realistic. This significnatly limits the relevance and significance of the results obtained", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)