Plateau in Monotonic Linear Interpolation --- A "Biased" View of Loss Landscape for Deep Networks
Authors: Xiang Wang
Annie N. Wang
Mo Zhou
Rong Ge
Venue: ICLR 2023 poster (2023)
Keywords: monotonic linear interpolation
loss landscape
deep learning theory

Abstract: Monotonic linear interpolation (MLI) --- on the line connecting a random initialization with the minimizer it converges to, the loss and accuracy are monotonic --- is a phenomenon that is commonly observed in the training of neural networks. Such a  phenomenon may seem to suggest that optimization of neural networks is easy. In this paper, we show that the MLI property is not necessarily related to the hardness of optimization problems, and empirical observations on MLI for deep neural networks depend heavily on the biases. In particular, we show that interpolating both weights and biases linearly leads to very different influences on the final output, and when different classes have different last-layer biases on a deep network, there will be a long plateau in both the loss and accuracy interpolation (which existing theory of MLI cannot explain). We also show how the last-layer biases for different classes can be different even on a perfectly balanced dataset using a simple model. Empirically we demonstrate that similar intuitions hold on practical networks and realistic datasets.

Published as a conference paper at ICLR 2023
PLATEAU IN MONOTONIC LINEAR INTERPOLATION A "BIASED" VIEW OF Loss LANDSCAPE FOR DEEP NETWORKS
Xiang Wang', Annie N. Wangs, Mo Zhou', Rong Ge Department of Computer Science
Duke University, USA (xwang, mozhou, rongge) @cs. duke. edu, aannie. samlle.wag022ebbkeeeee
ABSTRACT
Monotonic linear interpolation (MI.)- - on the line connecting a random initial- ization with the minimizer it converges to, the loss and accuracy are monotonic is a phenomenon that is commonly observed in the training of neural networks. Such phenomenon may seem suggest that optimization of neural networks is easy. In this paper, we show that the MLI property is not necessarily related to the hardness of optimization problems, and empirical observations on MLI for deep neural networks depend heavily on the biases. In particular, we show that interpolating both weights and biases linearly leads to very different influences on the final output, and when different classes have different last-layer biases deep network, there will be long platcau in both the loss and accuracy interpolation (which existing theory of MLI cannot explain). We also show how the last-layer biases for different classes can be different even on a perfectly balanced dataset using simple model. Empirically demonstrate that similar intuitions hold on practical networks and realistic datasets.
INTRODUCTION
Deep neural networks can often be optimized using simple gradient-based methods, despite the objectives being highly nonconvex. Intuitively, this suggests that the loss landscape must have nice properties that allow efficient optimization. To understand the properties of loss landscape, Goodfellow et al. (2014) studied the linear interpolation between a random initialization and the local minimum found after training. They observed that the loss interpolation curve is monotonic and approximately convex (see the MNIST curve in Figure 1) and concluded that these tasks are easy to optimize. However, other recent empirical observations, such Frankle (2020) observed that for deep neural networks on more complicated datasets, both the loss and the error curves have a long plateau along the interpolation path, i.e., the loss and error remain high until close the optimum (see the CIFAR- 10 curve in Figure 1). Does the long plateau along the linear interpolation suggest these tasks are harder optimize? Not necessarily, since the hardness of optimization problems does not need to be related to the shape of interpolation curves (see examples in Appendix A).
In this paper we give the first theory that explains the plateau in both loss and error interpolations. We attribute the plateau to simple reasons as the bias terms, the network initialization scale and the network depth. which may not necessarily be related to the difficulty of optimization.
Note that there are many different theories for the optimization of overparametrized neural networks, in particular the neural tangent kernel (NTK) analysis (Jacot et al., 2018; Du al., 2018: Allen-Zhu et al., 2019; Arora et al., 2019) and mean-field analysis (Chizat & Bach, 201 8; Mei et al., 201 8). However they don't 't explain the plateau in both loss and error interpolations. For NTK regime, the network output is nearly linear in the parameters and the loss interpolation curve is monotonically decreasing and convex no plateau in the loss interpolation. Mean-field regime often uses a smaller initialization homogeneous neural network (as considered in Chizat & Bach (2018); Mei et al. (2018)). In this case, the interpolated network output is basically a scaled version of the network output the minimum and has same label predictions plateau in the error interpolation curve.

---

Published as a conference paper at ICLR 2023
Interpolation
Interpolation
2.5
FCH on MNST VG616 on CHAR 30
FOR on MNST V6615 on CIAR 10
0.8
2.0
1.5
1.0
0.5
0.0
0.0
5.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.5
0.0
1.0
Figure 1: Loss interpolation curve and error interpolation curve for a four-layer fully-connected network (FCN4) on MNIST and for VGG16 on CIFAR- 10.
1.1 OUR RESULTS
Our theoretical results consist of two parts. In the first part (see Section 3), we give a plausible explanation for the plateau in both the loss and error curves.
Claim (informal). If a deep network has a relatively small initialization, and its last-layer biases are significantly different for different classes, then both the loss and error curves will have a plateau. The length of the plateau is longer for deeper network.
We formalize this claim in Theorem 1. For intuition, consider an r-layer neural network that only has bias on the last layer, and consider Xavier initialization (Glorot & Bengio, 2010) which typically gives small output and zero bias. If we consider the a- a-interpolation point (with coefficient a for the minimum and (1 a) for the initialization), then the weight "signal" from the minimum scales a" (as it is the product of r layers) while the bias scales as a. As illustrated in Figure 2 (right), when r is large and there is difference in biases, the bias will dominate, which creates plateau in error. For the loss, one can also show that the weight signal is near 0 for small at so the network output is dominated by the biases and the loss cannot beat the random guessing initialization. Note that this explanation for the plateau does not have any implication on the hardness of optimization.
However, why would the last-layer biases be different for different classes, especially in cases when the biases are initialized as zeros and all classes are balanced? In the second part (see Section 4), we focus on a simple model that we call r-homogeneous-wweigee network. This a two-layer network whose i-th output is (W..,, xr)' + b, where E Rd is the network input, W.,: E Rd is the weight vector and by E TK is the bias (see Figure 2 (left)). Our simple model simulates a depth-r ReI.U/linear network with bias the output layer, in the sense that the signal is r-homogencous while the bias is l-homogeneous in the parameters. Under this model we can show that:
Claim 2 (informal). For the r n-hhmmgeneou-wweigee network on simple balanced dataset, the class that is learned last has the largest bias.
Here, a class is learned when all the samples in this class get classified correctly with good confidence. We basically show that once a class gets learned, the bias associated with this class starts decreasing and eventually the class that is learned last has the largest bias. We formalize this claim in Theorem 2.
In Section 5, we verify these ideas empirically on fully-connected networks for MNIST (Deng. 2012), Reshion-MNIST (Xiao et al., 2017) and on VGG-16 (Simonyan & Zisserman, 2014) for CIFAR- 10. CIFAR- 100 (Krizhevsky et al., 2009). We first show that if we train a neural network without using any bias, then the error curve has much shorter plateau or no plateau at all. Even for networks that are trained normally with biases, we design homogeneous interpolation scheme for biases to make sure that both biases and weights are r-homogeneous. Such an interpolation indeed significantly shortens the plateau for the error. We also show that decreasing the initialization scale or increasing the network depth can produce a longer plateau in both the error and loss curves. Finally, we show that the bias is correlated with the ordering in which the classes are being leamned for small datasets, which suggests that even though the model we consider in the convergence analysis is simple, captures some of the behavior in practice.
2

---

Published as a conference paper at ICLR 2023
Weights (uetee
+bi
Bias
(6 0
0,07)
W
0
022
1
Figure 2: (Left) Our r-homoggnccuu--weighhe model with f((x) (W x)" + b,. (Right) The
comparison between interpolated bias a(bb (T) b2 (T) and interpolated weights signal (w!o) 22)
1.2 RELATED WORKS
There are two major lines of work studying interpolation between different points for neural networks, one monotonic linear interpolation that interpolates the initial network and the learned network, and the other on mode connectivity that connects two learned networks.
Monotonic linear interpolation. Goodfellow et al. (2014) first studied the linear interpolation between the network at initialization and the network after training on MNIST. Frankle (2020) extended the experiments to modern networks on CIFAR-10 and ImageNet and found that though the loss/error is still monotonically non-increasing along the path, remains high until close to the optimum. Lucas et al. (2021) showed that MLI holds when the network output curve along the interpolation path is close to linear (measured by Gaussian length). However, the Gaussian length can only be formally controlled in the NTK regime.
Mode connectivity. Mode connectivity considers the interpolation between two learned networks (modes) found by SGD. In general, linear interpolation between two different local minima crosses regions of high loss (Goodfellow et al., 2014). Surprisingly, Draxler et al. (2018) 18) and Garipov et al. (2018) observed that local minima found by SGD from different initializations can be connected via a piece-wise linear path of low loss. Frankle et al. (2020) and Fort et al. (2020) observed that local minima trained from the same initialization can also be connected using linear path. Freeman & Bruna (2016); Venturi et al. (2018): Nguyen (2019; 2021); Kuditipudi et al. (2019); Shevchenko & Mondelli (2020); Nguyen al. (2021) gave several theoretical explanations for this phenomenon.
2 PRELIMINARIES
We first formally define the linear interpolation between the network at initialization and the network after training. Then we describe the notations that we will use in the paper.
E IRP Suppose the network is initialized with parameters ((o) and it converges to ((T), A linear interpolation is constructed by setting the parameters [la] (1 a))) + a0(T) for a [0, 1]. The loss interpolation curve is defined as (a)) [0, 1] IR such that (a) is the training loss of the network at Glai, Similarly, the error interpolation curve is defined as (eror(()) [0, + [0, 1] with Tauer(a) as the training error of the network at gia), Here, the training error is simply the ratio of training samples that get classified incorrectly by the network.
Linear interpolation:
Consider network with parameters
Notations: We use [k] to denote the set (1, 2.. .:.. We use (00 82) to denote the Gaussian distribution with mean zero and variance 8², We use ||-Il to denote the &g norm for vector or the spectral norm for a matrix. For any non-zero vector v, we use ö to denote v/ ||l||- We use O(-), ((),, to hide the dependency on constant factors and use Ö(.), ((), ((-) to hide the dependency on poly-logarithmic factors.
For any time f, use g(t) (()) to denote the parameters and the network at time t. For any a E (0, 1), use 0læi, flal to denote the interpolation point, which means (ial (1 a00 + T and
plol is the network with parameters gla)
3

---

Published as a conference paper at ICLR 2023
3 PLATEAU FOR LOSS AND ERROR INTERPOLATIONS
We prove that the long plateau exists the loss and error curves when the initialization is small and the network is deep on fully-connected networks. The detailed proof can be found in Appendix B.3.
We consider an r-layer fully-connected neural network with r at least three. Given input æ E R"", the network output is
g(z) == V,a (V--1----oV where Vi E - for each layer E (r] and b E RK"r, Here the activation function a (-) can be either identity function or ReLU function. The output layer width equals to the number of classes, i.e, n, = k. We use ((V) b) to denote the sum of cross entropy loss over all samples.
6,
For the biases, we initialize them zeros and assume after training there exists gap between the largest bias and the second largest, which also holds empirically (see Figure 8). Note this bias gap is essential for the plateau in the error interpolation. If all the biases equal in the trained network, the logits for different classes only differ by the weights signal and the interpolated network has same label predictions as the trained network.
Assumption 1 (Bias Gap). Choosing i' E arg max b(7), we have b( max 6,5h 0. (T)
Without loss of generality, we assume that ((T) max ((T). We denote Amin 0/ max 6y and Amax = minng]s--- 6. (2)
Then, we show both the loss and error interpolation curves have a long plateau in Theorem 1. Theorem 1. Suppose the network is defined as in Equation (1) and suppose the weights satisfy
V 8, | S Vmax for all layers i [r]. On a k-class balanced dataset whose inputs
(,11 (
have lg norm at most 1. if Assumption I holds, for any E >> O, as long as < imiin
there exist 01
Zmmn 02 = 1+V8
Ainn 2V
and az
A/r Vinao
such that
1. for all a E a2), the error is 1/k:
2. for all a E [0, aaa, we have log k ZEE S L (( [vlol)..00 .6la)) I log + am + 2ee, where N is the number of training examples.
The above theorem shows that for all a E [ai, 02], ,, the error remains at 1 - 1/k that the same as random guessing. We skip the very short initial region [0, _ since the bias is very small and the error can be unpredictable due to the randomness in initial weights. When initialization scale is small, this error plateau region is roughly [0, 2V max
Ammn is smaller than 1 and Amin --). Empirically, 2V may
does not change much when depth increases. So the plateau becomes longer in deeper network.
Intuitively, the plateau in error eurve is there because for small initialization, the output close to a' ('V (v
(v) ...) ab(T). When is not large enough a" is much smaller than
O, so for every class i * h. the first term (signal part) cannot overcome the bias gap (b (T) b(P) This implies that all samples are predicted as class ic and the error is 10--1/1 1/k.
We also show that the average loss cannot be lower than log A: 2ec when S Vmax Note a small random initialization can achieve loss of approximately log k. Usually the bias gap Amax in practice not very large, so the loss curve remains nearly flat during this interpolation region. Again, the loss plateau is becoming longer when depth increases. This is because the weights signal remains near 0 for a larger range of a.
TRAINING DYNAMICS FOR CREATING A BIAS GAP
In this section, explain how the gradient flow dynamics generates bias gap balanced dataset by analyzing a simple model. Below, we first define the network model, training dataset and optimization procedure for our analysis.
4

---

Published as a conference paper at ICLR 2023
r-homoggeneous--eeighh network: We consider a two-layer and k-output neural network with activation function (z)) := =", where r is positive constant that is at least three. As illustrated in Figure 2 (left), under imput
RR, the i-th output fz() is (W,,,, =²)" + b, where the weight vector W., E Rd is the i-th row of weight matrix W E R and b; R is the i-th entry of vector b IR... In output (z)), we call (W... 2²" the signal since it is input-dependent and call b the bias.
Dataset: We consider k-class balanced dataset, with & as constant. We denote the whole dataset as S and denote the subset for each class E [k] as S. Each subset S; has exactly Ník samples and each sample z E Id is independently sampled v, + where the noise & ~ (O0 of D). To differentiate the noise terms among different samples, we denote the noise associated with sample x as Sa. We assume all U/ are orthonormal; without loss of generality, we assume v; e; for each class i. Here, we assume the orthogonal features to facilitate the convergence analysis beyond the NTK regime, following previous works (Allen-Zhu & Li, 2020; Ge et al., 2021).
We initialize each entry in weight matrix W by independently sampling from Gaussian distribution NN, 6²) and then taking the absolute value ! Our analysis can be triv- ially generalized to standard Gaussian initialization (without taking absolute value) when r is an even integer. We initialize all bias terms as zeros. We use cross-entropy loss L(W, b)
Optimization:
EiERK Exes, -log (>, Sie exp(f((z)) and run gradient flow on & L(W, b) for time T. Our analy- sis can also be extended to gradient descent with small step size.
(xp(
Next we show that running gradient flow from a small initialization can converge to a model with zero error and constant bias gap.
Theorem 2.
Suppose the neural network, dataset and optimization procedure are as defined in Section 4. Suppose initialization scale 8 S @(1), noise level S ((1), dimension d d' 6(1 //2 and number of samples N > 0(1/8-1)), with probability at least 0.99 in the initialization, there such that we have
exists time T = ((log(1/8)/88
1. zero error: for all different i, E [k)] and all x E S, (z) (z)
2. bias gap: b maxi ((T) > 2(11) with i arg ma 6,47
Due to space limit, only give proof sketch here and leave the detailed proof in Appendix C. Since our dataset is perfectly balanced, it might seem surprising that gradient flow learns diverse biases. We can compute the time derivative on the bias, b, = N Exes uz(2)) where uz(2) exp(f(()) Even Even (x) At the beginning, all logits are small, we have (I) x 1/k and b, = O. If all the samples are learned at the same time, we have (x(x) R 1, (x())) R 0 for E S E S ( S. which again leads to 6, x O.
the softmax output for class i, that is
On the other hand, we can consider what happens if all samples in one class (e.g., class i) are learned before any sample in any other class (e.g., class j) is learned 2, In this case we have
by
k
Σ
(x(z)
k N
Σ
k
N
1
k
N(k
1)
1
h
N
N
k
N
k:
k
k
N
k
N(k
1)
b, = 1
(x)
1y(x)
x
0
N
N
N
k
N
k
k k'
RES;
where for any learned sample St, we have uz ~ 1, (x( O: for any not yet learned sample E S \ Sr we have u,(x), uy (x) R 1/k. The above calculation shows that b, starts to decrease and all the other bias terms increase. Generalizing this intuition, we show that by starts to decrease whenever class is learned, and the class that is learned last will have the largest bias.
In the Xavier initialization, each entry in weight matrix W is sampled from (0, 1/d), 1/ /d that is small when input dimension is large.
can think of
82
2This is indeed possible since all samples of one class only differ in the noise terms in our setting. In the analysis, we show that the noise term has negligible contribution to the network output and all samples in one class learned almost the same time.
5

---

Published as a conference paper at ICLR 2023
b4
11,1
33
b3
W2,2
b2
W4,4
b
0
51
L
52
02
S3
54
S1
1
52
22
53
03
S4
Figure The training dynamics of W and in a four-class example.
As the weights initialized randomly, by standard anti-concentration, one can argue that there is a gap between Wi:''s s. Without loss of generality, we assume W > W > ..... > R,K" The initial difference in the weights will lead to different classes being learned at different time. We show that by doing induction on the following hypothesis through training:
Proposition (Induction Hypothesis). In the same setting of Theorem 2, with probability at least 0.99 in initialization, there exist time points O =: < 1 < 82 < L2 < <... <. Sk-1 < lk-1 8k: := T with 4 -8; 8, (1l0g(1/6)/88) (0)/88-))) and 8,11 -t, 0(1 E [K- such that for any E [st, 8:+1];
1. (classes not yet
yet learned) for any class j.j' 2 i+1, 1, we have (1)bg) 2 maxreMM 6/9 0(8")
(2) (2)(09)) 0/00 S O(8)) and (3) w/S < 2(6);
2. (classes already learned) for any class j S 3--11 - 1, we have (1) b/ S maxvel 60 - (1)),
(2) 1/09 (x) (x) 1 (x) + for i' #j. E S₁ and (3) w!t)
3. 2 2(1);
3. (parameters movement) (1) for any j E (6)) w <
(( jjz (2) for any distinct
3.j' E [k),0 < W S 06) and for any j.j E [K] and any Sy, (w/( Ex min (0(5).W9) 3.'
3:
This proposition shows that gradient flow learns l classes one by one, from class to class k. More
precisely, each class i is learned during time [sa, 8:41]. All the not yet learned classes j 2 + 1 have close to maximum biases and their weights W
j. 's are small. All the already Iearned classes
j E i 1 have small biases and large weights W (t) For the parameters movement, we know that all the diagonal entries w:(!),
j.j 's are larger than the initialization and all the off-diagonal entries w-(1), are only (5). The correlation between the weights and noise terms also remains small.
When learning class during time [s 11+1], the weight w:(0) slowly grows to small constant in [s;, tx] and then quickly grows large in [t,, 8241-] As result, all S, become classified correctly. During the same time, (1) decreases and becomes smaller than the largest bias by at least a constant. remains small, all E S₁ are also classified correctly because bL (T), the largest bias. See an illustration of this learning process in Figure 3.
At the end time T Sk. although W-(T) k.
Although we consider a simple neural network and data distribution, the analysis for the training dynamics is still non-trivial. There are three major challenges in our proof: (1) How to ensure that class + 1 is learned much later than class ?? (2) For any class j that has not been learned, how to maintain that its bias is close to the maximum? (3) For any learned class j, how to maintain the large bias gap from the top bias? Next, we give the proof ideas for these questions. Since all the off-diagonal entries and correlations with noise terms in W+()) are negligible, in our proof we can essentially foeus on the movement of w!())s 's and o(4))ss.
Lower bounding 8i+1 8;. During time [si, 1,). the dynamics of W(( is similar as in the tensor power method (Allen-Zhu & Li, 2020; Ge al., 2021). The initial gap between W:(") and W

---

Published as a conference paper at ICLR 2023
ensures that when W rises small constant, W (t) is still O()) for all j 2 i Then after constant time 824-1 LG + is still (()) since the increasing rate of W j.j merely 0(6-11).
jJ
Bias for classes that are not learned. For j 2 i 1, maintain that 1/) Z maxye[j 6/7 ( First, we use the below lemma to show biases for any two classes j. 2 + remain close.
Lemma 1 (Coupling Biases). Assuming W , W5s S O(5) and by by 2 maxpe[j) by (
have by bj > 0 by bj S -uō", and by bj < 0 by bj z + for some positive constant μ..
Second we show that any already learned or being learned class j' S cannot have bias much larger than any class j 2 i + 1 not yet learned.
Lemma 2 (Bias Gap Control D. For any different j'.j j E [k], if W 2 W3s, Was S 0()) and by bj 2 0()),, by 2 maxre[m] by - 0(8",, we have by - bj < O.
Bias for learned classes. At time sy+1, we can prove that 1 uj (5)+1) (x) S C1 for all Sj and 0f ((511))
b/ 1(5511) S -C2. According to the below lemma, we can ensure that b1)) (1) S -C2 for
any 2 8j+1-
Lemma 3 (Bias Gap Control II). There exist small positive constants C1 C2 such that for any
j E [k 1| and any x E Sj. if - uz(x) S C1, WK, S (()) and by - by 2 -O2, we have
63 by < Q(1).
4.1 PLATEAU AND MONOTONICITY FOR T-HOMOGENEOUS-WEICGE NETWORK
Now assuming the network at initialization and after training satisfies the properties described in Theorem 2 and Proposition 1, we can prove a tighter bound on the plateau region and also show the monotonicity in error and loss curve. See the complete proofs in Appendix B.1 and Appendix B.2.
Same as in Assumption 1, we use A, to denote the bias gap b(() 6(7) for E [k 1] and de-
note A min = min A; and Amax ma A, For the weights, we denote W min
min W and Wmax max W!?" We denote Runi min (: Rmax max A./[W(()rr Below, we show the plateau and monotonicity of loss and er- 1.
ror interpolations in Theorem
Theorem 3. Suppose the neural network, dataset and optimization procedure are de- fined in Section 4. Suppose the network at initialization and after training satisfies the properties described in Theorem 2 and Proposition 1. For any e =0,1), sup-
pose 8 S (in(O())")))((R)))) A O(( Wmin ()). There exist an A.m. (THO(V))
Wiaxx
- - 0z
2/rr and 04 (1 (()) - (Bmux)) ) such that Wian
1. for all a E (a1,az), the error is k/k for all a E [aı, 1], the error is non-increassig:
2. for all a E [0, oa). we have log k S 1 L(Wlal, blol) s log k + a + ee; for all a E [[a,,], the loss is strictly monotonically decreasing.
The analysis for the plateau is very similar as in Theorem similar to a depth-r fully connected neural network with only last-layer biases in the sense that the weights are r-homogencous while the (last-layer) bias is 1-homogeneous, For the error plateau, we prove tighter bound on the right boundary 02 than in Theorem 1. We also show the error is non- increasing for a E [5/4 A//mmn 1] by arguing that once sample is correctly classified at interpolated point a' 2 5/ A/Amin it will remain so for any a 2 a'. Similar as in Theorem 1, we can show that the
since r-homoogeneous-weing weight network
loss is no smaller than log h - ec when S W
1/r
To show the monotonicity of loss after 0c4, we
Waax'
show that f!0) (z) f(() (x) is increasing in for i + j and e S,.
In summary, for Jaj a2]. the signal is smaller than the bias gap and the error remains at 1 1/k. Before ag the signal is very small and the loss remains large; after a4, the signal starts to overcome the bias gap and the loss is decreasing. See an illustration in Figure (right).
7

---

Published as a conference paper at ICLR 2023
5 EXPERIMENTS
In this section we empirically show that intuitions from our simple theoretical model can also be applied to more realistic datasets and architectures. First, we show that bias plays an important role in creating the plateau in the error interpolation, predicted by Theorem 1. We then demonstrate the influence of initialization size and network depth (also see Theorem 1). Finally, we show that similar to Proposition the class that is learned last often has larger bias. Due to space constraint, we only show the results on MNIST and CIFAR-100 in this section, while similar results also hold on Rishion-MNISS and CIFAR-10 10 (see Appendix D).
Unless specified otherwise, we use a depth-10 10 and width-1024 fully-connected ReLU neural network (FCN10) for MNIST and use VGG-16 (without batch normalization) for CIFAR-100. We use Kaiming initialization (He et al., 2015) for the weights and set all bias terms zeros. For FCNI0 on MNIST, we use small initialization by scaling the weights of each layer by (0.001) so the output scaled by 0.001. We train each network using SGD for 100 epochs. See more experiment settings in Appendix D.
We linearly interpolate using 50 evenly spaced points between the network initialization and the network at the end of training. We evaluate eπror and loss on the train set. For each setting, we repeat the experiments three times from different random seeds and plot the mean and deviation.
Loss Intorppiiiiinn HVST
Brror interppo on, KMSST
Locs Interpolation CIFA 100
Envriinrrauitionn CIFAR 100
23
34
1-14-
0.
0.
60
60
0.
04
0.5
0.3
3.3
60
62
64
06
68
3.5
32
0.4
0.
0.0
46
62
64
6.6
68
1.0
Figure 4: Loss and error curves across networks with all bias, last bias and no bias.
Role of bias in creating plateau. We demonstrate the importance of bias using two experiments. In the first experiment, we compare the loss/error interpolation curves between networks equipped with bias for all the layers (all bias), with bias only for the output layer (last bias), and with no bias at all (no bias). Figure 4 shows that networks with all bias and last bias have a much longer error plateau than networks without bias. Three bias settings have similar loss interpolation curves.
Lostinterliiation MNST
Error Interpo on, MMST
Less Interpetation. CIFAR-100
Emorimoraciation CIFAR
23-
last rermll
las: daa Jemo
66
Nik. perral
bos, sarol 2o
Nox, murra hobe
03-
homo
65
05
60
6/
04
64
0.4
60
62
1.6
6/
0.5
0/4
02
24
Figure 5: Loss and error curves across networks with normal and homogeneous interpolation on bias.
By our theory, the bias dominates the signal at the beginning of the interpolation because the bias term scales as a while the signal scales as a". In the second experiment, to correct this discrepancy, we interpolate the bias the h-th layer (input the O-th layer) as bfc1 (1 a)* 1/00 + +a²b
(T We call this the homogeneous interpolation as now terms involving bias and weights all have a" coefficients. We compare this with the normal interpolation that linearly interpolates the bias terms. Figure 5 shows that for networks with all bias or last bias, using homogeneous interpolation can significantly reduce the plateau in the error interpolation, but does not affect the loss interpolation.
Role of initialization scale and network depth. Our theory suggests that with a smaller initial- ization, the signal magnitude at the initial interpolation is smaller, which can create longer plateau in both loss interpolation and error interpolation. We compare networks under initialization scales 0.1, 0.01 and 0.001, where scale 1 corresponds the standard Kaiming initialization. For other
8

---

Published as a conference paper at ICLR 2023
Interpiiation, HNST
HMSST
interpdationn CFAR-100
Emarintepplatiinn CIF6R-100
2.3
Intel
231
m8x0 E3
Figure 6: Loss and error
networks with different initialization scales.
initialization 3, we rescale each layer by the same factor the output is rescaled by B. According to Figure 6, smaller initialization does create longer plateau in loss and error interpolation.
Losu Interpaaationnn MNST
Error Interpoldtoon MMMST
Loss Interpolation. CIFRR
Emariimaaacitionn. CIFAN-100
3.0
FOW FOVLO
FON FOND
VC008
0.5
VO0M
VOOTL
VODIS
1.3-
044
0.4
Figure 7: Loss and
networks with different depths.
With a deeper network, the signal grows slower at the initial interpolation phase, which can potentially create longer plateau in both loss interpolation and error interpolation. We compare FCN4, FCN6, FCN8, FCN10 on MNIST and compare VGG11, VGG13, VGG16, VGG19 on CIFAR-100. According to Figure 7, deeper networks do have longer plateau loss and error interpolation.
Train Loss. 2.Clas HNST
Biss. Clss WNIST
Tran loss. 5-Class MUST
Bas S-alas NHIST
0.5
1ex33
0.5
0-30
20
25
spoth
spech
82007
Figure 8: Train loss for each class and bias term dynamics on 2-class MNIST and 3-class MNIST.
Bias learning dynamies. Our dynamics analysis Section shows that gradient descent can learn diverse biases on balanced dataset by learning different classes at different time points. In particular, the last learned class should have the highest bias term. We verify this theory by studying FCNI0 with only output bias on balanced 2-class 3-class MNIST. To separate the learning of different classes, we compute the per-class loss by only considering the examples in that particular class. According to Figure 8, in the 2-class MNIST, number 1 is learned last and its bias is larger, which fits our theory. Also in the 3-class MNIST, class learned first, class 3 the second and class 1 the last; for the learned bias, class bias is smallest, class 3 bias in the middle and class I bias the highest.
CONCLUSION
Our theory suggests that the plateau in loss/error interpolation curves may be attributed to simple reasons, and it's unclear these reasons are related to the difficultyleasiness our experiments although the training succeeds in all the settings, the loss and error interpolation curves can easily manipulated by changing the initialization size, network depth and bias terms. Therefore, we believe needs to look at structures more complicated than linear interpolation to understand why optimization succeeds for deep neural networks.
optimization. In
Though our theory requires a small initialization, we also observe plateau in CIFAR-100 with standard initialization, which suggests that the useful signal is still a high order term in a. We also observe that sometimes the ordering of the biases does not exactly follow the ordering of the learning. We believe this is partially due to the correlation between different-clas features and offer a preliminary explanation in Appendix D.5. We leave the thorough study of these problems in the future work.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENT
This work is supported by NSF Award DMS-2031849, CCF-1845171 (CAREER), CCF-1934964 (Tripods) and Sloan Research Fellowship.
REPRODUCIBILITY STATEMENT
For our theoretical results, we listed all the assumptions and stated the theorems in the main text and we left the complete proof for all the claims in the Appendix. For our experimental results, we defined the detailed experiment settings in the Appendix and also uploaded the source code as supplementary material.
REFERENCES
Zeyuan Allen-Zhu and Yuanzhi Li. Towards understanding ensemble, knowledge distillation and self-distillation in deep learning. arXiv preprint arXiv:2012.09816. 2020.
Zeyuan Allen-Zhi Zhu, Yuanzhi Li, and Zhao Song. convergence theory for deep learning via over- paramcterization. In International Conference on Machine Learning, pp. 252. PMLR, 2019.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine- sine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. In International Conference on Machine Learning, pp. 322-332. PMIR, 2019.
Lenaic Chizat and Francis Bach. On the global convergence of gradient descent for over-parameterized models using optimal transport. Advances in neural information processing systems, 31, 2018.
Li Deng. The mnist database of handwritten digit images for machine learning research. IEEE Signal Processing Magazine, (9(6):141116 2012.
Felix Draxler, Kambis Veschgini, Manfred Salmhofer, and Fred Hamprecht. Essentially no barriers in neural network energy landscape. In International conference on machine learning, pp. 1318. PMLR, 2018.
Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. arXiv preprint arXiv:1810.02054. 2018.
Stanislav Fort, Gintare Karolina Dziugaite, Mansheej Paul, Sepideh Kharaghani, Daniel M Roy. and Surya Ganguli. Deep learning versus kernel learning: an empirical study of loss landscape geometry and the time evolution of the neural tangent kernel. Advances in Neural Information Processing Systems, 33:5850-58611 2020.
Jonathan Frankle. Revisiting" qualitatively characterizing neural network optimization problems". arXiv preprint arXiv:20/2.06899 2020.
Jonathan Frankle, Gintare Karolina Dziugaite, Daniel Roy, and Michael Carbin. Linear mode connectivity and the lottery ticket hypothesis. In International Conference on Machine Learning. pp. 3259-3269. PMLR, 2020.
Daniel Freeman and Joan Bruna. Topology and geometry of half-rectified network optimization. arXiv preprint arXiv: 161101141 2016.
Timur Garipov, Pavel Izmailov, Dmitrii Podoprikhin, Dmitry P Vetrov, and Andrew G Wilson. Loss surfaces, mode connectivity, and fast ensembling of dnns. Advances in neural information processing systems, 31, 2018
Rong Ge, Yunwei Ren, Xiang Wang, and Mo Zhou. Understanding deflation process in parametrized tensor decomposition. Advances in Neural Information Processing Systems, 34, 2021.
10

---

Published as a conference paper at ICLR 2023
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the thirteenth international conference on artificial intelligence and statistics, pp. 249-256. JMLR Workshop and Conference Proceedings, 2010.
Ian J Goodfellow, Oriol Vinyals, and Andrew M Saxe. Qualitatively characterizing neural network optimization problems. arXiv preprint arXiv: 1eXXiv::11.600 1412.654,, 2014.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. In Proceedings of the IEEE international conference on computer vision, pp. 1026-1034, 2015.
Christopher Hillar and Lek-Heng Lim. Most tensor problems np-hard. Journal of the ACM (JACM), 60(6):1-39, 2013.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. Advances in neural information processing systems, 31, 2018.
Alex Krizhevsky, Geoffrey Hinton, al. Learning multiple layers of features from tiny images. 2009.
Rohith Kuditipudi, Xiang Wang, Holden Lee, Yi Zhang, Zhiyuan Li, Wei Hu, Rong Ge, and Sanjeev Arora. Explaining landscape connectivity of low-cost solutions for multilayer nets. Advances in Neural Information Processing Systems, 32, 2019.
James Lucas, Juhan Bae, Michael R Zhang, Stanislav Fort, Richard Zemel, and Roger Grosse. Analyzing monotonic linear interpolation in neural network loss landscapes. arXiv preprint arXiv:2104.11044, 2021.
Song Mei, Andrea Montanari, and Phan-Minh Nguyen. A mean field view of the landscape of two- layer neural networks. Proceedings of the National Academy of Sciences, (1563)))7765-E777,,, 2018.
Quynh Nguyen. On connected sublevel sets in deep learning. In International Conference on Machine Learning, pp. 4790-4799. PMLR, 2019.
Quynh Nguyen. A note on connectivity of sublevel sets in deep learning. arXiv preprint 11Xiv:2007.08566. 2021.
Quynh Nguyen, Pierre Bréchet, and Marco Mondelli. When are solutions connected in deep networks? Advances in Neural Information Processing Systems, 34, 2021.
Alexander Shevehenko and Marco Mondelli. Landscape connectivity and dropout stability of sgd solutions for paramaaraeeeei neural networks. In International Conference on Machine Learning, pp.
PMLR, 2020.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint 14Xx:::409.15500 1556, 2014.
Luca Venturi, Afonso S Bandeira, and Joan Bruna. Spurious valleys in two-layer neural network optimization landscapes. arXiv preprint arXiv:1802.06333 2018.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms. arXiv preprint 1788::7708.07747, 2017.
11

---

Published as a conference paper at ICLR 2023
A EXAMPLES FOR THE DISCONNECTION BETWEEN LINEAR INTERPOLATION SHAPE AND OPTIMIZATION DIFFICULTY
We give two examples that illustrate the disconnection between the linear interpolation shape and the optimization difficulty. In Section A. we show a function that is NP-hard to optimize, but has a convex and monotonically decreasing loss interpolation. Then in Section A.2, give function that is casy to optimize, but has a non-monotonic loss interpolation.
A.1 HARD FUNCTION WITH CONVEX LOSS INTERPOLATION
For any symmetric third-order tensor 7 E Rdxdxd our goal is to minimize
f(x, Tx,,,, | +4
(2)
where x E Idd and = E R.
It's known that finding the spectral norm of symmetric third-order tensor (that is, max.eRd maxeeed./eel==1 T(, v, v)) is NP-hard (Hillar & Lim, 2013). We prove that minimizing f(z, also NP-hard by reducing the tensor spectral norm problem to it.
Proposition 2. Minimizing (xx 2) as defined in Eqn. 2 is NP-hard.
Proof. For any non-zero tensor T, let (x", be one minimizer of f(z, 2), it's easy to verify that T(x", x², ,x²) > O. We show that 5² == x²/ ||=*]| must be solution to max [//x///////=11 T(v, v).
For the sake of contradiction, assume there exists o" with unit norm such that T(v", oz, v*) > T( "","" ,², It's easy to verify that f[[|==]| x²,,") < ,(x",2"), which however contradicts the optimality of 22).
Next, we prove that start from certain initialization, the loss along the linear interpolation path is convex and monotonically decreasing. Note that assuming the unit Frobenius norm of T does not hurt the NP-hardnes, of the problem. And our initialization is oblivious of the tensor T.
Proposition 3. Assume [|T'| = 1. Suppose we start from initialization (Ip, 20) with 2g =
and |=ol 3x2 Let (x",²") ²²) ) be minimizer of f(x,, 2)) as defined in Eqn. 2. We know the loss interpolation curve 7(a) == f ((1 - a)zo + -ax", (1 a))0 + azz)) is convex and monotonically
decreasing for a E 1].
Proof. We first prove that at any minimizer (x",**), =²), we must have =² = 0. Otherwise, we can set zero to further decrease the loss. Starting from an initialization know at each interpolation point zlal = ax"", z/al (1 a)2(1), Therefore, we have
with (0)) 0,
7(a) = f(zlo), (/aa) = - Txllal اااي اااعي + | || [2aa]]
T(ax", ar"", axx) + ||o2 1| + [11 -a)=(00
- a²T(2" x², x²) + + ||> | + (1 a)² |210)]
To prove the convexity of (a) for [0, 1]. we only need to prove (((a) for a E [0, 1]. We have
12a² || |1 + 12(1 - a)² [210
(a))) = 6a7 (x" x²,
xx) x;,xx")
6a ||>~ 1| T(=", x"" xー) 2 | + 12(1 a)² [0)
Since the formula for (a) involves both T( ,² . and ||~=|| we first figure out the relation
between these two quantities. Suppose T (x* ,-*)= = > 0, it's not hard find ||a=|| must be
>>
equal to áp. This is because - ||x" 1s' p'p- + ||>"| is minimized when ||>*|| = -p. Next, we prove (a) for a E (2/3, and a E (0,2/3) separetely.
12

---

Published as a conference paper at ICLR 2023
When (2/3, 1], have
12a² |001|* 6pa || 1 = 6a ||x*| | (x""""","),
Therefore, we know (a) >
When E [0, (033/3], we know
12(1 - aa)
2 ==0]]
3
Since F 1, know T(**, x, x*) S 1 and ||00
3/4. Therefore, have
2
3
3
27
6a |> T( xx x)) 6
1
4
16
Then, we know that if |2(0]
3v2 we have (a(a) 0.
A.2 EASY FUNCTION WITH
LOSS INTERPOLATION
In this section, we give an easy-to-optimize function that however has non-monotonic loss interpo- lation curve. We consider the following loss function
f(x,V) {(1-
if y =0
((02 22² + otherwise,
37
where x, y/ E R. We can also re- re-parameterize f(r, (x,y) y) using angle 0 E [0, 2x) and length [0, oo) h(0,r) sin(0)
(1*-2r") 2r²). 2r?))
Next, we prove that starting from any non-zero point, gradient flow converges to the global minimizer.
Proposition 4. Starting from any non-zero initialization, gradient f(r y) as defined in Eqn. 3 converges to the global minimizer (0,- -1).
Proof. We know the unique minimizer of f(r, u) is (0, -1) by considering its equivalent form h(0, r). For h(0,r) = sin(0) (ra 2n²), we know (x 2T²) is minimized at r = and
(1 (1- ) is maximized at 0
3nt 2
Besides the minimizer (0, -1). the other stationary point at (0, 0). For any point (z, y) different from (0, 1) and (0, 0), if =² y² * 1, the gradient along the radial direction is non-zero; if
V++y² # 1, the gradient along the tangent direction non-zero. It's also easy to verify that
V
starting from non-zero point, gradient flow does not converge (0, it must converge to -1)
It's also very easy to prove that gradient descent with appropriate step size converges to an neighborhood of the global minimizer within poly(1/e) number of iterations. This is because the gradient is at least poly(e) for any non-zero point outside of the e-neighborhood of the global minimizer. Starting from an initialization (x, y) with x2 + y2 (1), the smoothness along the training is also bounded by constant.
Next, we prove that starting from certain initialization 3 the loss interpolation between the initializa- tion and the global minimizer is mon-oonot..ic. We prove this by identifying two points along the interpolation path such that the point closer to minimizer has higher loss compared with the point further to the minimizer.
Note the initialization condition in Prop. is satisfied with constant probability for a reasonable initialization scheme. For example, if uniformly sample (at, y) from the set S [(x, y) R + y² < R) with R 2, the condition satisfied with constant probability.
13

---

Published as a conference paper at ICLR 2023
Proposition 5. Suppose start from an initialization (Iu, yo) (r sin (3), cos( with 2 and
E / 3/3. Consider the loss interpolation curve y(a) = f((11a(()))))) + ax" :1- (1-a) + aay"
with (a* , (0, -1) and f( defined in Eqn. 3. We know there exist 0 I a1 a2 such
that
5
2 32
Proof. We prove for any B [-7/3, r/3] and any 1, the loss interpolation between (r (3), r cos( to -1) is non-monotonic. In particular, we show there are two points along the linear interpolation satisfying
f (sin (3/2) cos (3/2), sin (3/2) sin (3/2)) - -f (sin cos( 2 1/12,
where (sin (8/2) cos (3/2), sin (3/2) sin (3/2)) is the middle point between (sin( (3) and (0, 10).
Next,
we separately upper
bound f (sin(3), cos(
and
lower bound
(sin (3/2) cos (3/2), sin (3/2) (8/2)). We have
8E //, (sin(3), cos(3)) - f(0, 1) 3
max
and
min f (sin (3/2) cos (3/2), sin (3/2) sin (3/2)) ////n/33.//3
2 (sin (z/6) cos (x ()) sin (T/6) sin /6)
1 2 3
=
1+
2
2
49
96'
Therefore, we have / (sin (3/2) cos (3/2),- sin (8/2)sin - (sin(3), 32
B PROOF FOR PLATEAU AND MONOTONICITY
We first consider the r-homogeneeus-weiieee model. We prove the plateau and monotonicity properties for the error interpolation (Theorem 4) in Section B.1. We then prove the plateau and monotonicity properties for the loss interpolation (Theorem 5) in Section B.2. Theorem is simple combination of Theorem and Theorem 5. Finally, we give the plateau analysis for the fully-connected neural networks (Theorem 1) in Section B.3.
B. ERROR INTERPOLATION FOR 7- HOMOGENEEUUS WEIGHT MODEL
Theorem 4 (Error Interpolation). Suppose the network at initialization and after training satisfy the properties described in Theorem and Induction Hypothesis Suppose <
min O min 1/rr), (, O(( Wiin) ) There exist a1 = 2i.. and a2 = (1+0(v5) -- R such that
1. for all a E 02), the error is - 1/k;
2. for all a E [ai, 1], the error is non-increasing.
Proof of Theorem 4. This theorem directly follows from Lemma 4 and Lemma 5.
Next, we separately prove the initial plateau in Lemma and the monotonicity in Lemma
Lemma 4 (Error Plateau). In the same setting in Theorem 4, there exists an Ami and
4
Q2 (1+OV3) R. such that for any interpolation point with a E [[r,, arzl, the error
1 1/k. Moreover, we have !!al (e,) (( for all j E [k) and all + k.
14

---

Published as a conference paper at ICLR 2023
In the proof of Lemma 4, show that for interpolation point E [a1,02] the bias term dominates and all samples are classified as class &s that has the largest bias.
Proof of Lemma 4. We only need to show that for all (01,a2), have
(x) (x)
(x)
for all x S and all i * k which immediately implies the error is 1 1- 1/k. Without loss of generality, assume x Sj where j may equal or
For a E 01 W
of
we only need to consider the case when a E
Amin
Vō W 022
So here we assume
V8 Wminn
We can lower bound s (x) _!((())
(x) as
Amin
5/. (x)
(x)
(w/a) Ri, xx
W )²)]" bla)
[/]
[W/ + =0()] - 6(0)
k x
204:-
+ +oW
(2) 1y
+ +00)]
< (w!ao Ex O6) and the inequality uses (wla)
where the second equality uses
k,i
2r)
2 0.
To prove (1) (x)
> 0 for E Amin
V5 only need to prove
Amin A
Wminn
! + Wain
/ + 066)
> 0. Since A
A Amins we know
A 2 Due to full ac-
Amia
curacy, we know (W!T)) x
2 1/r for x E S₁, which then implies
(2) f,5
2 S2 (1
because
A, 2 ((1) and (w(!) (2)
< 06)) S O(1). Since (: f,z 2 Ω
(A
1/r
and W (T) O for
Ex
LJ
i + J. so we have
iij (
< ( s Wmxx as long as < O(A 1/r). So we can upper bound
w +
(0)
/8 w(T) + 0(0] as follows.
min
w 1,
V8
VOW max Wmin
+
w - 0(0)
< 0(5) +
W min
v VoW Wiax
VoW
rmmin
Wmin
VoW 55max
Se
Wmin
W2 W
where the second inequality assumes
<
max min
Therefore, to prove Amin A
w + Wmen
w
tjj + 0(6)]
> O we only need
Vow max
0,
W m
2 "
which holds as long as d <
Wiin max
For a E
v Wiii
Similar as above, we only need to show that aA,
W
O + +aw in
+ 0(6)
> 0 for i of k and j E [k]. Since w(O) < 00) and a 2 Vo/W W/in we
15

---

Published as a conference paper at ICLR 2023
(0) have W & O(VoaW min). Therefore, we have W + taw +0(6) = (1+ aw!!
Therefore, have
W (0) A.j + aw! +0(0) 2 ad, (1+0(V0)) a" [w: > 0,
aA:-
where the last inequality assumes a S a2 == (IHO(vS)
Rmin
where
Rmin
mingg[a-1] A//(W
Next, we show that the error is non-increasing for a E [an, 1] by proving that once a sample is classified correctly it will remain so.
Lemma 5 (Error Monotonicity). In the same setting as in Theorem 4, there exists ó = Amin such that the error is non-increasing for a E [ax, 1].
Proof of Lemma 5. We first show that sample ek is correctly classified for the whole range [a1, 1]. Second, we show for any other sample once it become classified right it will remain so. Combining these two cases, we prove the monotonicity of the error rate.
Class K. We first show that every x E Sg is classified correctly for any a E [an, 1]. According to Lemma 4, we know that
p (x) (x)) > s! (x) (xx
for any i + k We only need prove that (1)) f (x)) is increasing for [on, Expanding
aaal (x) - slal (z). we have
1 (x) (z)
= =[11 a) ( (WEO
k. (0) 2) +
( (W!?) ((.,,z)) ))= (1- a) ( (w:o) .0) + a (W!?) .x)]"
(1-a)
[ + (b 69 B
kis 22) >/1 (w//0 xz) >| < (w!T) 11 1/11 (w x 1 O()) and
which is increasing since
(T) ( > 2(1).
Other classes. For any class i a k. from Lemma 4, we know that it is classified incorrectly for a E Jan, oz). We prove that once it become classified correctly at some a' E (0xz, 1). it remains so for a E 1).
We show that at a, for any x e S, if f! (x) > a da (z) (x)) > O. Expanding
() for all j * i, we have
(1) slol (x), we have
|l0)(x) (x))
Kwwlll 'I + +b/al - [[ [( 3 )I - 6/a0
(woel ax) >1 - [wrlal } (b9T)) - 1 (9?))
Since (z) ()) O, we have
[wwlet (rvl:,.)) }) > a -197-
where we use ( (WJal, x) > 0. Computing & (z) - 1/(0(()) (z)) we have
0 (1) - -1001110 (())
da
8
([(1- a) (w!!!) .2) a ( )xx]= - -[11 [[1-a) a) (w!!o) (,) + a (w .2) ))]" + a (B - -)))
da
( (w!0) xx) *a((11) (( .x) - (w!!0) (z) )) (( ((w!7)) ) (e))(((()))) (.00,))) (D!T) ((T) 0(8),
2r
16

---

Published as a conference paper at ICLR 2023
where the inequality uses ( (w xx) (W . .z) 50())
If 16 -b000 S 0, we only need to prove
{ (w (0) ) + a ((w!!r) 1; , x2) ( (W::0) x ,z) ( (wW:.)) .x) - -WW:...)) - 010') > 0,
which holds since ((W!?T.))) ( (W!o0 (.:.:20 .x)) ( (W!o) x 2 =(().
If 1
1 -
((0) -b/0) > 0, we have
da (1 (x) -f()
0
=r io 2) + a (( (w//7) 22 - (Wrl)) x ))
( (w!"7) (,) - (w:00'0 (9(022)) .x)) - -b - -088)
(1 (1-0(8)) r ( (W:!?) .00
(697- b(7) (6)m) - -070-(7)) )
( i1 x + a (W!(?) :2)
(W!D)
[o] [(w1d]
a (15t) (T)) Therefore, prove
where the last inequality uses
(1-0(8")) >>r (w!?7) .0) (W:o0' .2)
8 (e)) - 1/00 (e:)) > O, we only need to prove da
2
(w!!)>> xz) +o (w:?? (0) (w (1)
We have
(1 ((-0()))) (( (W!?)) (2) x
( (w:!O(z)
(1 (1-)()))
(W .2) - (W!!! .x) (W x0)
r
(0) x + ( (w(?)) ,
(D 1: x
2a
(W!o) x
a
The first inequality requires (w!0) 2x S ( (T ,
( x
and the second inequality
uses 3, (1-0 2 2/3. To prove ( (w:() xx)
(W!?)) x
W (1) x7 ). it's equiva-
lent to show (W: .2) s Ita to x) Since a 2 a2
R min we can lower
(40(Vh)
bound T#a as follows,
R Riin
I+a 22 1
Ruin
where the first inequality uses a S 1 and the second inequality uses 1 + 0(VB) 2 2. So we
have Ita (w(l) x 2 R A min. Therefore, we only need 8 < 0 R R 4 A/r to ensure that
x. S (WITT .x) (W!0) .a)).
B.2 LOSS INTERPOLATION FOR H-HOMGGENEOUS WEIGHT MODEL
In this section, we give a proof of Theorem 5.
Theorem 5 (Loss Interpolation). Suppose the network at initialization and after training satisfy the properties described in Theorem and Induction Hypothesis 1. For any (0, 1), suppose (Rmax)
8 < O(e2/r, there exist 03-
2/r Wmas and a4 (1 + ((8)
such that
1. for all E a3), we have log k es S L .(al) S log k + a'max + ee;
2. for all a E (oa, 1), the loss is monotonically decreasing.
17

---

Published as a conference paper at ICLR 2023
Proof of Theorem 5. This theorem directly follows from Lemma 6 and Lemma 7.
Next, we prove the initial loss plateau in Lemma and the monotonicity Lemma
2/r
Lemma (Loss Plateau), In the same setting as in Theorem 5, for any > 0, there exists as such that for all a E [0, ag]
Winos
N (log k - ee) S L(Wlal, Bll)) v N (log k: + mm + ee).
We show that for a E [0, as), the weights W is negligible and the bias dominates, which then gives lower bound and an upper bound of the loss.
e/r and 8 I (c!//") we have
Proof of Lemma 6. Since a S az
Wman
(w K [/la .x) )){"" (w. x) + al a ( 2)) - -W!!0 )))] - ((1+ cvol sec,
for all E ( E
We can divide the dataset S into N/k disjoint subsets {Pi) N/K where each P. contains exactly one sample from each class. Next, bound the total loss of each subset P.. Without loss of generality, let's consider subset Pi and suppose 2010) is the i-th class sample in this subset. For convenience, denote the total loss of samples in Pi Li (W(o), blol).
Lower bounding Li(Wial,ble
We have
ΣjE(N exp (1) (z(11)
4 [W (Wl)) = Σ log
exp g|al (x(3))
iE [4]
Σ SEENN) exp
(1)0] (xx(0)
= log
II KE(M
exp ( (x(0))
2 llog
exp (261))
Σ ΣjE(k]
Σ exp (1 (2(21))
where the last inequality uses the HM-GM inequality. as follows,
We can then upper bound
exp ((()))))
Eielki ΣSEA exp (1 (2(t))
exp (f: (z(1i)
exp ([ww )(())) + +abi)
EjERk exp (1, (2x(0))
EE|k E SEEN exp [((rd -x())))0))) 'J" + aby))
xE(A)
exp (ab; + ec)
jE(Nj exp (ab,)
E
Σ Eielal exp (abi)
Σjetk exp (aby)) exp (ee)
exp (ec).
Plugging back to the lower bound of L (W(o), blol), we have
h kan)) exp (ec)
Ty [Wiilll,ble 2 llog
= A (log k: ec).
18

---

Published as a conference paper at ICLR 2023
Upper bounding L1 (Wllll,,
We have
EjE(a exp (1(1)))(1))
(zo10)
Li(Wlo),
Σ log
exp
Σ jEiN exp (ab, + eE)
log
exp (ab;)
xe [k]
k log exp (aAmax + +E))
<k (log k + aAmax + et)
The above analysis applies for every subset Pt, so we have
N (log k - ee) S L(Wlo), blol) s N (log + aAmax + eE).
Next we show that when a is reasonably large, we have f! (ex) (ex) increasing for all i + J. which then implies that the loss is decreasing.
Lemma (Loss Monotonicity). In the same setting as in Theorem 5, there exists as =
(1+ (()))= - ( [Rmax
such that the loss is monotonically decreasing for a E [as. 1].
Proof of Lemma 7. To prove that the loss is monotonically decreasing, only need to show that for any i [k] and any S,, s!a (x) 1 (x) is monotonically increasing for j +
Same as in Lemma 5, it's easy to prove that for x E Sk, fa(x) - [x) with j # k monotonically increases for E [0, 1]. So we focus on other classes.
For i * k, we show that @ (F! (x)) > 0 for x E S; when a 2 a4:
(1 ,f))(s))
da
0
([1 a) (W:10) ) + a (w!T)) ,2)) "1= - [[1 -1)
a) (1 :2) + (W(T). .x) ] + a (1!T) - ()()))
(w!))
da
(w!!)- 2) a ( .x)) ((W!)) .2) - (W!!) .x)) (60 b(T) 0(8)
2r
(1 a)
2ra"
W/ x))
(w!!7)
(T)
ti ,.) (w! .x)) (157) - -b(7) 0(0")
K (w!?)) (T) ] (B(T) (.T7) (1+0(8))
2ra
1-0 0
A
min
>0,
(w:-0) .x) / (T) 22 s 0 (6/A 1/r) bim) The last inequality
where the second last inequality uses requires
( -()
ra r- 2 (1 0())
(.(T)
which is satisfied long as (1+0()))
Renax
where
R
max A.(Ww/1))
B.3 PLATEAU FOR DEEP FULLY-CONNECTED NETWORKS
In this section, we consider fully cully-connected neural networks as defined in Section 3 and prove that both the error and loss curves have plateau. We restate Theorem follows.
19

---

Published as a conference paper at ICLR 2023
Theorem 1. Suppose the network is defined as in Equation (1) and suppose the weights satisfy
(()) S o, v
S Vmax for all layers i E [r]. On a k-class balanced dataset whose inputs
have lg norm at most Assumption I holds, for any O, long as ò min (#
+ and az
there exist 01
Zmm 02
(1+V8)
A/r Vinax
such that
1. for all a E [a1,ax) the error is 1/h:
2. for all or E aa), we have log k Zer S I. ( .blo)) S log h: + a + 2 where N the number of truining examples.
Proof of Theorem 1. This theorem directly follows from Lemma and Lemma 9.
We separately prove the plateau of error interpolation in Lemma 8 and the plateau of loss interpolation in Lemma 9. Then, Theorem is simply a combination of Lemma and Lemma 9. For convenience, we denote (xx) == V,Øa
...) in the proof.
Lemma 8. In the setting of Theorem I, there exist 0n Amt and a2 1+v/8
Amin 2V
such that the error is 1 1/k k for any interpolation point [a1, az2.
Proof of Lemma 8. Recall that the network output under input is g(x) V,a (Vy-1---ooVi ....) + 6. Similar as in the proof of Lemma 4, we only need to show that for all a E [ai, a2), we have
g d0 (x)
9 |a
(x)
for all * and all samples v, which immediately implies the error is 1/k.
For a E a1
Vā_
a
6 Auin
2
we only need to consider the case when a E
Vinax
02
So here we assume
Amin
5
|ol We can lower bound |od (x) g (x)
gl (x) 0. (x) h4 (x) + blal
h/ (x) |al
aA min 2 II (1- v) +
jE(r]
a 2 + aVmax))
where the first inequality holds because [(/) [ b/at 2 aAmin and (2)) ( s
Hi
(1 a) ()) + aar The second incquality uses
(| (1- ,)v + av ar s (1-
a) 1
+ |
< 5 + aVvmax-
Since a E
we have
Amn'
Vanax
|al (I)) 1ol (ar) 2 8
/
V
Amin
Vmax
min
Vinx
(1+ v8
28 2
28 2/0 >0,
where the second inequality assumes 8 1/r2 and the last inequality assumes d < (
20

---

Published as a conference paper at ICLR 2023
For a E
Vo Viax
az)
Similar as above, we only need to show that a&min - 26 + a aamax) 0.
Since
Vō
we have 8 I VoaVmaxx. Therefore, we have
Vanas"
a Ammin (6 + aV )" a'mmn -2 ((1+ vō) a aVmmx)) )" > 0,
where the second inequality holds as long S 02 == 7
Amin
Next, we show that for a E [0, v the loss cannot decrease by much. Similar as in Lemma 6, we prove that the signal is very small and the logit is dominated by the bias term. This then gives a lower and upper bounds for the loss.
Lemma 9, In the setting of Theorem 1, there exists 0z =
e/rr
such that for all [0,
Vinax
1 1 (v(a) }. ,bla)) I log k + ammax + 2ee,
log k - Z2E S
where is the number of samples.
Proof of Lemma 9, Since a S a3-
2/r Vana
and 6 < dire
we have
hnld S (8 <Vama) S
for all input x.
Similar as in the proof of Lemma 6, can show that
ト ((v)a)) } dlll) S log a.max + Zee,
log k 2Ee
where we have an additional factor of 2 before ee because now the signal can be positive or negative. Here N is the number of samples.
C PROOF OF TRAINING DYNAMICS
In this section, we give the complete proof of Theorem 2.
Theorem 2. Suppose the neural network, dataset and optimization procedure are as defined in Section 4. Suppose initialization scale 8 < @(1), noise level < ((1), dimension d' O(1 6(1/ (22 and number of samples N 0(1/8-11,, with probability at least 0.99 in the initialization, there such that we have
exists time T = (o(log(1/))88
zero error: for all different i, E [k) and for all x E S, ( (z) 2(1);
2. bias gap: b.- maxifi ((T) > 9(1) with i arg maX b(7)
(T)
Proof of Theorem 2. This theorem directly follows from Proposition 1.
We consider the r-homogeneous-wweieee network as defined in Section 4. Our simple model simulates a depth-r ReLU/inear network with bias on the output layer, the sense that the weights signal is r-homogeneous while the bias I 1-homogeneous in the parameters.
Next, we prove Proposition while leaving the proof of supporting lemmas into Section C.I. Through the proof of Proposition 1, we restate the lemmas when use it for the convenience of readers.
Proposition (Induction Hypothesis). In the same setting of Theorem 2, with probability at least 0.99 in initialization, there exist time points 0 81 with t4 s; (log(1// (1/8)/8* 1 2) and $:41 -t, = i E [ such that for any E [st, St41],
82 l2 < <. Sk-1 < lk-1 8k T
1. (classes not yet learned) for any class j.j 2 i+1, we have (1)b)) 2 maxvejy 6/00 -(0").
(2) (/50 - 0501 < 0(8") and (3) (((t) < 0());
21

---

Published as a conference paper at ICLR 2023
2. (classes already learned) for any class 1, have (1) b) S max by -Q(1).
(2) 13" (x) 1/ (x) +11 for + j. E Sg and (3) 33 2 2(11;
3. (parameters movement) for any j E ((6) W
(t))
ij for any distinct
j.j' E [k),0 O < 3 S 088) and (3) for any j.j' E [k] and any z E Sy, - min (O(6).W()) w
Proof of Proposition 1. Through the proof, we assume the conditions in Theorem 2 hold in all the lemmas without explicitly stated. At the initialization, we have the following properties with probability at least 0.99.
Lemma 10 (Initializationn. With probability at least 0.99 in the initialization, we have
1. for all j.j E [k]. 33' =(0);
2. for all distinct j.j' E [k], | W O(0);
3. for all x E S, 11E 0(o);
Vlog(an) vi
4. for all distinct x, x' E (arn 50
5. for all [k] and all E S, (En, (Ee. wr ||s0
s0
[VloR(N)
vd
Without loss of generality, we assume W W
W (0) k.k'
It's not hard to verify that the induction hypothesis holds at the initialization 4. For any i [k 1], assuming the induction hypothesis holds for time [0, s:], now we prove that it continues to hold in (st, 8-+1]- Next, we first prove the first two properties in the Proposition and leave the last one the end.
The learning of x E S; can be divided into four stages:
1. Stage 0 for & [st, tx] with st O(log(1/0)/8 a small constant 14g-
2). During this stage, w:O grows to
2. Stage 1 for / E [4,,4 with ((") - 44 = 0(1). this stage, w grows from pn to a large constant /41-
3. Stage for é E [1 (w)) minges, uz ((2(2)) (z) 2 - P22 for small constant f/2.
,4, [((") with vft)) (:)) O At the end of this stage, have
4. Stage for E [o("), (b) with ( {(t) 0(1), where (0) 8 During this stage, we have ( b% decreases to -13 with μs positive constant.
Next, we consider these four stages one by one.
Stage O. We show that w(t increases faster than W (t) 1,4, so that 2, reaches a constant while #41,041 is still (()). We use the following lemma to characterize the increasing rate of (:(t) 1-1,441 and (!!!) f.
f,z
(itt)
*We maintain stronger bound on | (ww!.) <.) by proving (wdd).s.)) <O(vlog Noő), which implics (w/)) {.> O(8) long (/1//Tog/V)
22

---

Published as a conference paper at ICLR 2023
Lemma 11. For any j E [k], we have
aw (t)
- (0
VVog ( No
dt
Vd
If miiizes, (1 - (x)( 2 (1)), we further have
OW(!) 1n
(1-O(VlogNo))
k N
Σ (1- (x)) - SES
k - (1+)(vlog.No)
Σ zES,
(1))
(1
N
di
It's not hard to verify that minzes, (1 (1-4% (x)) minges..1 (1- 2 21))., so we have
aw!!
Öt 2 (1-o((VogNo))
k N
Σ
E(1 4 (0)) r [m<!]]--
#ES:
aw (0)
i+1,0
< (1+ 00VV0((oogg (1+O(VlogNo))
h N
Σ
(1- (2 (o)) [w(t] 141.541
r-1
Ot
xESH+1
We can upper bound 1 - 11+1 (x)) for any x E S as follows,
Ever exp (5( (x)) - -exp (1221())
1 - u (x)
EVENO exp (F('(()) (1))
EvER exp (6(0)
eep (t) (1+0(8"))
Evety exp
exp
( ( x) S (6) for every i' E [A].
where the inequality uses
We can lower bound 1 - ( (z) for St as follows,
1 1 ui (x) Eveny exp (x)) - exp (1.0 (x))
Erelq exp (1(0 (1)
Eveny exp (110)
exp (0!0)
(1 ((4))
EvERK) exp
(0(0)
ΣvE(N) exp (6(0)
(0)
exp
(1 (1-0(1)-0(6))
Eve(n exp
The first inequality uses ( (w.)) x)
< O(H)) for every i' E [k]. The second inequality uses
(4) < (t) + 0(8), which is guaranteed by the following lemma. Lemma 2 (Bias Gap Control I). For any different j',j E [k], if W 2 W,s, W5.5 S 50) and byr b; 2 0(8"), by 2 maxre[ by - 0(8"), we have by by < O.
According to Lemma 10, we know there exists constant C > 1 such that 1,2 2 CW 141,141
+11,111 Choose constant S such that S = VC and w: 2 - (C /C Choosing An as small constants and < 0(1/ Voog N,,8 5 0(1), we have
1 O max
(1- (())) S (1 O(Viog
min (1 (1) (s))
xE8.41
FES,
23

---

Published as a conference paper at ICLR 2023
We also lower bound
( (x) for St by a constant,
Σ EvE( exp (6())
(190)
exp
1 - uz (x) (x) 2
(1 0145))
EPE(K) exp ((())
exp (6it)
(!!))
(1- 0(4)))
EvEW exp 0.
25(1),
where the last inequality holds because fn is small constant and 1/41 2 maxyelM 6y )
Lemma 12 (Adapted from Lemma C.19 in Allen-Zhi & Li (2020)), Let 2 be constant and let
{WT2 w 4e + 33 h22 be two positive sequences updated as
aw!!)
[
2 C.
for some C. O()),
0L
aw!
(0)
[w]]]] for some S ((1)
S SC₁
0t
Suppose wiO 2 | 5 (1+ + ((1))
then we must have for every = 0(1), let t, be the first
j.j
time such that W((t) 2 A, then
w S )(W))
Then, according to Lemma 12, we know that there exists O (1oog(108)00'=3) such that w:ft)) No and (=()s))
141.441 0()). By similar argument, we also know w((h) s (6)) for any 1+1.
Stage 1. In this stage, show that w:(!) grows to a large constant μ1 within constant time. Since
(1) w!l s μr and 6 < 6114411 Od"), we have
(t) 1 1- us (x) 2 2(1),
for all x E S. This further implies,
aw!!)
2 (1 (1-0 log
Σ (1 1 12 (x)) [w]]]]
Ot
N
#ES;
20(1),
where the inequality also uses w:O 2 poo Since the increasing rate is at least constant, know w!l grows to Yu in constant time. For any j 2 i + 1, since the increasing rate of w:( is merely 0(8-11,, we know w!()) remains 0(8) through Stage 1.
Stage 2. In this stage, prove that u (x) for any S grows to 1 #2 with #22 small constant. We use the following lemma to characterize the increasing rate of f! (x) (x))
Lemma 13. For any x E S, and any + i, if ux(x) 2 2(1), we have àt (f((z) fx)) 2 -(W??--)) -(()).
Since ui (1) (x) < #2, know 1 (1) (z) 2 ((1). For any j * i, we have
(x) 20 [w:!!] 2r-2 0(1) σ (x) (x)
i (
20(1),
24

---

Published as a conference paper at ICLR 2023
where the last inequality holds because W!?? 2 fa with jai a large enough constant.
The next lemma guarantees that the beginning of Stage 2, we have 66() ol51) 2 -0(1), which
then implies 1. (ar) J (a)
(x) 2 -1()-
Lemma 14 (Bias Gap Control III), For any different i.j E [k], if W S W, - (6) and
b. - bj I (1), we have
b, bbz >0. 0.
Let C' be constant such that (x) (x) C for every j + implies ue(x) μ22 Since the at the beginning of Stage 2, we have (10(x)
(x) 110 (z) O(1), within constant time, have 1 (1c) - 1100(()) 2 C for every j i and uz(x)) 422
Lemma 15 (Accuracy Monotonicity). Given any positive constant C2. there exists positive constant C such that for all different i E [ki,, as long as W 2 Ci and f((x) - [5(x) S f2 any Si, we have ((f((x) (-(]))((())) O.
According to Lemma 15, by choosing large enough μl, ensure that f!º 5/00 C and (e(e)) 2 1 - μ2 throughout the training. Note that once i, rises to M1, it will stay least μ1 (6) throughout the training, according to the gradient lower bound in Lemma 11.
Stage 3. In this stage, we prove that within constant time we have b(0) b S -13 The following
lemma shows that b(t) - b(() decreases in at least a constant rate.
Lemma 3 (Bias Gap Control II). There exist small positive constants C1, C2 such that for any
j E Ik - 1] and any I E Sj. if 1 - uz(x) S C1, WE, S O()) and by - by 2 -O2, we have
by by < -1().
Choosing μ22 = C1, = C2 where C1, C2 are from Lemma 3, so we know that ((t) b/2 decreases
constant rate until 6(t) - -b(h) < -- At time (()) know that by (4) (w)
by
088). So within
constant time, we have brit1 bat41 M1g. By Lemma 3, we also know that for any t 2 8441, have 6/4) b2 S 413
The following lemma shows that 6 is close to the maximum bias. Lemma 1 (Coupling Biases). Assuming W Wjj S O()) and by by 2 maxvej by - 0(8")
we have by - b, > 0 by bj S -pō", and by- b, < if by b, 2 +p8" for some positive constant
Combining Lemma and Lemma 2, we know that throughout the training ( maxpe(K) 110
O6")). Therefore, have b(") max;e[[] by I (11) for t > 81+1.
Finally, let's bound the movement of different parameters.
Monotonicity of diagonal terms: For j E [k 1], according to Lemma 11 we know W can only start decreasing when it exceeds a large constant and can only decrease by at most (8) through the algorithm. By choosing 5 I O(1), we can ensure that W:(0)
j.j < w for any f. For ((()) we know monotonically increases since we always have 1 - u/ (x) 2 (11) for E Sg. This is because (:(t)
remains as small as (6)) through the algorithm and 6 (22 < 0(1).
Bounding non-diagonal terms: We use the following lemma to prove that π(6) ( for j + jr
j3' S 00)
Lemma 16. For any j + we have TW55 S (6)) Furthermore, there exists absolute constant
> 0 such that if < W33 <
n8
we have TW 2 log (1/8)
μd
log 1016)
25

---

Published as a conference paper at ICLR 2023
The first property in Lemma 16 guarantees that the increasing rate is so small that that the total increase within time is only (()), which then implies that Wx() j. I (6) through the training. The
second property in Lemma 16 guarantees that once ( falls below
pd its decreasing rate
j.j
log
= (1/6)
is so small that that the total decrease within T 'ime is only
p5
which then implies that (1/6)
log
W J. (6) through the training-
Bounding noise correlations: The following lemma shows that the total change of (Wr()) s Eo within
T time is only OVVlog Nod). Since at initialization, we know (wrji0 E - O(Vloog log Noσ), we
conclude that (wiL Ex)
I O0(Vlog 5o throughout the training. Since W 2 (2()), long
- Ō(),, also have
( Ex) - p.y' for Sy-
Lemma 17. For every j E [K] and every S, we have
(W .TS 0 (VlogNod) Noo)
C.I PROOF OF LEMMAS
Lemma 10 (Initialization). With probability at least 0.99 the initialization, we have
1. for all j.j' E [k]. ( 3. (
2. for all distinct j.j' E [k]. [ w O(0);
O());
3. for all x 1k&l < 0
4. for all distinct x, x' E S, (E $0
50
Vlor(N) Vit
5. for all [k] and all E S, (Enn (Ex,
(1,
11,00))
S0
(log(M)
vd
Without loss of generality, we assume w 1,1
(0)
K.K-
Proof of Lemma 10. Recall that each (= is independently sampled from (0 82) before taking the absolute value. By standard Gaussian concentration inequality, we know for any j.j [kt), with probability least 1 1000k2
j.j
wr10 < (8)).
By anti-concentration inequality of Gaussian polynomials, we know for any j.j' E [k], with proba- bility at least 1000g2>
O 2 2(6). JJ
Also by anti-concentratiin inequality of Gaussian polynomials, we know for any distinct j.j E [6], with probability at least 1
T0008
(0) 2
(0) j''"'
(0) 2 2 2(62),
which implies w/10
[110 2 20))) assuming W W 10 0()).
26

---

Published as a conference paper at ICLR 2023
By the norm concentration of random vectors with independent Gaussian entries, for each x: S, have with probability at least 1000N
K S O())
long as d 2 Ollog N).
By the concentration of standard Gaussian variable, for any distinct x, x' E S, we have with probability least 1 1000N";
Vlog N
Ex 5
Similarly, for any x and any ey, we have with probability at least
I000kN
(voog vd
)
((Ex e3) s
for any and any (( we have with probability at least 1
1000
KE w/ >
Vlog N
Vd
Taking union bound over all these events, we know with probability least 0.99 in the initialization, we have
1. for all j.j E [A]] W = O(6);
2. for all distinct j.j E [k). W
w j''3 (()):
3. for all S, |kx|| O(r);
4. for all distinct x, x, E S, (Ee, E.e)) | S0
(log(N)
v/
5. for j E [k] and all S (Ee. (,)k,,ee)1111 (Ex, 11:1011
50
[log(N)
Vd
Lemma 12 (Adapted from Lemma C.19 in Allen-Zhu & Li (2020)). Letr 2 3 be constant and let (W wHy Jizo be two positive sequences updated as
(t
Øt 2 C.
[
for some C₁ O(1),
ow()
j. < SC,
[w!]]] for some S @(1).
Øt
Suppose : 2 W! - (1+ + ((1))
then we must have for every = 0(1), let l4 be the first
j.
time such that (() 2 A, then
with) < o(w))
Proof of Lemma 12. This lemma directly follows from Lemma C.19 in Allen-Zhu & Li (2020) by taking the continuous time limit and setting & as constant.
0
Lemma 1 (Coupling Biases). Assuming W W5 S O6) and by, maxvep by 0
we have by - b, > 0 by - bú < -uu"" and by - b, < 0 bf - b; 2 +10" for some positive constant μ.
27

---

Published as a conference paper at ICLR 2023
Proof of Lemma 1. Let's first write down the time derivative on by,
h
by. =1
Uy (g)
EES
exp (Wy xy + by. EPE( exp ((W x) + by)
ESS
exp exp((W, (W,r,))))+b))
For any x E S, we can bound
as follows,
Erew exp (Wer,)))) tby)
exp ((W 3) +
bby)
exp (byr)
S 00()),
ΣreR exp ((W x²¹ +bx) Σre(H exp (W x²" + b..)
where we uses (W | < (6) + OVVlo Noo) S 068) assuming 1/ N. The similar bound also holds for
(N [.-5) +b,)
Evew exp ( +by)
If by b, 2 nd"", we can now upper bound by - b, as follows, by by
h N
exp (b,) exp (by:)
S
+ 0(0))
EE exp ((We,,, ,, x) + bv)
rES
k
exp (b,) - exp (byr) EvER exp (We,,, x) by))
+ 0(8)
N
uE,,
k
exp (b,)
s - Q-Q(")))
+ 0(8))
N
sESjUS, E Erem exp (W x) bz)
When E Sj U Sy, we can lower bound
exp(l,) Eve( exp((Wy...) +by) as follows,
ebp(b)) EvEn exp ((W bv) - ME(M exp (bv) exp (We,,,
exp (b²)
exp (b,)
Σ Eee exp (bx) 1 O(5r)
20(1),
where the first inequality uses (W,,,,, < 5 and the second inequality assumes bj 2 max by O(8") and is at most some small constant.
Therefore, if by b, 2 pō", we have
by - b, S - + O(8*) < 0,
where the second inequality chooses i as a large enough constant. Similarly, we can prove that if by b, S -u8", we have
by - b, 2 2(18)) 0(8)) 0.
Lemma 2 (Bias Gap Control I). For any different j' E [k), W 2 W,, W, S 06) and b, by b, 2 0()), bj 2 maxve(k] by 0(8",, we have by. - by < 0.
Proof of Lemma 2. We can write down by- - by as follows,
k
by by = 1
(g)((t)
1
Σ m5(xr)
N
N
#ES
DES
k
k
(uz(x) (x:) up (x)) +
(uz(2)) (x)))
N
N
ZES,
RES
28

---

Published as a conference paper at ICLR 2023
We first prove that for any Sy, we have uz(x) - uz(2x) 1 0. We can upper bound fz) and lower bound fy (z) as follows,
fz(2) (W j. x3¹ + b; S O(6") + bj
(--( = (W 2)¹ + bby 2 b,.
The bound on (x) holds because (W).:. = W + (W,.: Ea) S =008) Noo) I 0()).
The bound on fy (x) holds because yW z) = W + (Wy,,. (. Eu) 2(()) ((vlog Noo) > 0. With the above two bounds, we know that (2) Ug S as long as by. - bj 2 ((8))
Same as in the proof of Lemma I, for each x E S \ Sy, we can bound up (x), (z) as follows,
exp (by)
exp (by)
EveR exp (fv( 0(8") 1 (z)( - ENER exp (fr(
0(8",
exp (b,)
exp (b;)
EVENN exp (x)) 0(6") uy(() ErERK exp (fr 0(8).
Therefore, if - bj 2 μō",
can further upper bound by. by follows,
k
by - وN z
(u,(z)- - uz)()))
N
ZESIS
h
exp (b,) - exp (by) + 0(8))
N
Σre(H) exp (frr (z))
SE
h
exp (b,) cxp (by)
Eve(n exp (fe (x)) + 0(8")
N
ES
exp (b,)
S - I(ud")
+ +(8))
E ENE( exp (fv()))
=ES,
Similar as in Lemma 1, we can show that Even (x) by 2 maxvem by - -(8". So, finally we have by - by S -Q(ud") + 0 < 0,
exp(b,)
2 2(11) due to Was S O()) and
where the last inequality chooses fa as a large enough constant.
Lemma 15 (Accuracy Monotonicity). Given any positive constant C2, there exists positive constant C1 such that for all different i, j E [k:), as long as Wi, 2 C₁ and f((x) fz(x) < for any I E S,, we have (((((a)-f(())) 8t
> 0.
Proof of Lemma 15. Since f1(z) - fa(a)= < C2. we know 1- (x) > ((1). This immediately
implies mss, (1 (x())) 2 211) since [u,(x) ux(x') S 06). According Lemma 13, we can bound ((((ee))/(ee)) as follows, dt a (1(x)) -x)())))(())) 2 S(W2:- 0(1) 0
Ot where the second inequality holds because Wi, 2 C1 with Ci large enough constant.
Lemma 3 (Bias Gap Control II). There exist small positive constants C1, C2 such that for any
j [k 1] and any Sj. if 1 - uz(x) S C1, WR. I 06)) and b, bb -C2, we have
by by < (1).
Proof of Lemma 3. Since 1 1 (x(xx) < C1 for some E Sj. we know 1 - uz(ax) C1 O(6) for every x' E SS. We can write down b, by as follows,
by in
h:
Σ us(0')
1
k ue((²))
Σ
N
N
E'ES
x'ES
k
(x²) uy(=²))
Σ
(ux(xe) 1)(2/))
N
N
29

---

Published as a conference paper at ICLR 2023
First, we upper bound ux (a") uy(x') for every x' Sj as follows,
u uz(2') S 1 uz(2') 25(x') =-1+ 2 (1-u,(z') s 20,
-
Same as in the proof of Lemma 1, for each x' E ES\ Sj, we can bound uy(x'), 4x(x²) as follows,
exp (xp(b,)
exp (b,)
Σrew exp (J)) 0(8") S <uy(x')
exp (F 066")
exp (bx)
exp
Σrel exp (fv()')) 0(8") s uu((') S
expp)xxx(f + 0(6")
Therefore, upper bound ux (x') - (x') follows,
ux(x') - (z(2²) S exp (bx) - exp (b₂)
+ 0(8)
EvElN exp (fr (x')
exp (bj)
ENER exp (fr()")) (exp(h> - b,) 1) 0(6) 20(C2) + 000",
where the last inequality uses by bj S Cz. Above all, we can upper bound by by as follows,
by be S - 1 2C + 0(())++((8))
< S(1),,
where the second inequality holds as long as C1, C2, are at most some small constants.
Lemma 14 (Bias Gap Control III). For any different j.j E [M]) if W., S O(1), Was S 0() and b, bj S O11), we have
b, b, > O.
Proof of Lemma 14. We can write down b; - b, as follows,
u((x)) (1 1
k
k Eu,(or)
b - bj
N
ZES
FES
(uz( ux(x))
N
Next, we lower bound uy (x) u. (z) for every S,
uz(z)= - ux(x) exp (W xz¹' + +b,) cxp (W x)" + bi)
Eve(s] fv)
exp (0(8") + b;) exp (O(1) + 6,)
Eve (x(
So as long as by - b, > O(1), we have u,(x) - uz(x) > 0 for all x E S, which then implies
b, b by > 0. Lemma 17. For every j E [k] and every x E S, we have
KWan)&)) T so 0 ( (Vlog
No6) Noo)
Proof of Lemma 17. For each j E [k], we have
W. 3
k N
Σ (1 (1-u;(x'))
(W
j: x0) 1 xd
Σ uz(2²)r (W ( x x'ESYs,
E'
30

---

Published as a conference paper at ICLR 2023
and
W Win:.5
k N
Σ (1- (1-u)(z())r (W "' (o' r'ES,
Σ x'ES'SS
uy ( x') (at, (ol:ba))
We know that (zrEe)) S 0 + Vlog N vd). For any x' # I, we have Ez' S O((ovlog /log//vd & OVVlog N/ /Vd) as long as o S 1.
According to Lemma 18, we know that for x' E ESj, we have (1=)) W x/> 50(1).
For x' E S \ S₁, we have (u((z') (W x²) 1 & 0(8-11 since (W),, 1 0
O(y Nóo) < (6)) assuming a S 1/ N.
Therefore, we can bound (Wis. E as follows,
(W s Ex 50 N
vlog.N N vd
Since T - O(log(1/8)/88))) N (00g1//)/00' and d ž log (1/8)/00)2 we know
( 6x) ) . TT O(
Lemma 18. For any i [k) and x E if (xxx)) () 2 @()) have
d
dt (L- - (z))) (W 0.
Proof of Lemma 18. We write ux(x) as EjEM ser for any j' # i, we have
exp(fs(a)) sx
(xp(s(()) Next, we prove that
d
exp (Jz(z))
( (Wiss))-11 < O.
dt EjENA, exp (f)( + exp (f((z))
This derivative be written the sum of two terms:
cxp (x)) dt EjEMNAA exp (x)) + exp (fi(z)) (W... 2))
d
1
[z (IW..) ((
d
EjE(H)AAA exp +o) + d
di (jENHIs exp (f)()) (x) (f(()) f3((x)) ( (W
For the first term, we have
ff (()) exp fz((x)) (Ww..
Ejepaline -
(x)))) (5 exp (Fi(z) - [z(( (r 1) (W 2) (Wi.
Ejelhoa exp
(Wi,,))" - (
(fix)) fx())) (1
31

---

Published as a conference paper at ICLR 2023
For the second term, have
d
di Σ SEMIIA (x(()) + exp( [-()) ( ()
+ exp
ΣJE(H)A exp - -f(z)) (f(()) - f)(()) + exp - f2) (f((z) (f()))-f((*)) (Wess
EJENNWAH exp (f5(z) (x)( exp (Xi(() f3- (1)())))))
1 x) 1 (Wiss))
$ 2 exp (f((z) - (z)) (Wiss2)"-1
where the last inequality uses fz(z) ff(2) 2 2(1), (1))))))))))))) fx( s 0(1) and - f fz((2) (W, (Wa,; = [ x 0(1) 2 ((1).
Combining the bounds on both terms, as long (Wi., x)) is larger than certain constant (which is guaranteed by (1 - (z())) x)) "-1 (1)), we know d
de ( (11-u: (z)))) (W ().:,.)"-] < 0. O
Lemma 16. For any j + j', we have 3 S O6). Furthermore, there exists absolute constant j such that if < W3s' log (116) we have TW
pd
nd
2 (1/6) (1/8)
Proof of Lemma 16. We can write down the derivative of W 3,3' as follows,
W3
Σ
u1-) (W).. 2)) (e
#ES,
Σ SySy
uy(x)r (W (i (2)) 20)
N
Σ
uz(x)r (W x3)" r-1 ()
N
(ESUSS,SS,))
#ES
o V N
- (( (Vlog (v1og.Noo)) + Vvog N
=
Va
The bound on the first term relies on (1 Uj (2)) (
j.:1 2)--/
< O(1) and (ey,z) 2)
+ gyllog for x E Sj, where (1 (,=(;(x)) (W x) r- < 0(1) is guaranteed by Lemma 18.
The bound on the second term uses (Wj., Wjs' + 0 (Vlog Noo) and (ey,a) = 1 + for Syr. The bound on the third term uses ()) O and (ey,z)
o
oylog
Vd
+
gy/og
N
for S \ (S3 U.y)).
Vd.
To prove the upper bound of the derivative, we have
WWS 50 o /vlogg N
Vd
where we use W + 0 O (VVlogNNo) Ndo) 0. Since T 000g((100)/88-)) we have
TW i S (6)).
long d 2 0 log N log"
g
32

---

Published as a conference paper at ICLR 2023
We show that there exists absolute constant f 0 such that if 0 <
Was
we have
log
(1/8)
TW53 2
4d
which holds as long as W3s 2 -0
We have
2l0g
(1/6)
Ing (1/6)
W 3'''
0
log N
(Wis'' J,3 =
v Vlog /logNNoo)) Nóor) 1-1
vd
2 0 log N
10-188-1
vdd
log (1/6)
10" 1r- 8
-
1og (1/8)
1
log- 2 (1/6)
The first inequality assumes S <0(- VVog N log 7-7 (1/8)
The second inequality assumes d >
0 log N log 2n-2
r-2 (//0) (/00)) The third inequality chooses y as a small enough constant.
Lemma 11. For any j E [K], we have
aw(
8
Vlg No
J.j
0
a
Vd
If minuzes, (1- - ux)( 2 21)), we further have
aw!0
(1 (1-O(VlogNo) k N
Σ (1-u,(x)) (1-) S #ES,
jJ
k - (1 (1+O(Vlog.No)
Σ (1-
Øt
N zES,
Proof of Lemma 11. We have
W N
Σ (1 u2(x)) r (W 2; (x,,)))
k
Σ uy(z)r (()))(W,,,,)) (W,,,, -) (x) j,:1
N
S
DESIS,
k
Σ 5
(1 uy ( (WsJ = (Vlog (Vlog.Noo)
1#0
Vlog No
Vd
Σ uz(x)r (0(0) 00 0 SES
10 ( Vlog No Vd.
A Σ (1 - (;(x))x))) rW +0 10-1VTog Tog No N
01 No))
vil
SES;
where the second equality uses (W,., < OVVoo (6e,, ez)l ej)l= 100000 ( (oog O6)) for j + j'. Therefore, if minzes; (1 (1- (x)) 2 2(1), we know
No
and Wi 5
(I-O(VIog
k
Σ (1- <W < (1+0(VlogNo)
k Σ (
N xES,
N
And we always have
(
(5-~vVlog No
W3J 2 -0
Vd
33

---

Published as a conference paper at ICLR 2023
Lemma 13. For any a E St and any + i, if -4(x)= 2 2(1), we have
(f(()) fx)) 2 S2(W?, -1()). Ot
Proof of Lemma 13. Recall that fi(x) = (Wi,, " + b;. so we have
f((x) =r x²) (W..; +
=7 (Wi,+ = v log Moog r-1 (wi,+ + - (WastE)) + b, 20(W? - 0(1).
where in the last inequality we uses W., 2 S((W(7 12(8") and (MiL:: aog No 0(8-1)..
1
log(1/8)
We also have
f1(0) =r (W x) ( (W Vi:n, +
=r (Wax+ + vlog No8) 1-1 (W5, + (Wo:)ka) + b,
s0(1),
where we uses |W - 0(6), /3.5| s 50(8-))) and (Ws:: $ 0000))) Therefore, we have
dt
d (f((z) fx)) 2 -
D ADDITIONAL EXPERIMENTS
In this section, we describe the detailed setting of our experiments and also include additional experiment results.
MNIST & Fashion-MNIST. Unless specified otherwise, we use a depth- 10 and width-1024 cully-connected ReLU neural network (FCN10) for MNIST and Fashion-MNIST. We use Kaiming initialization for the weights and set all bias terms zero. We small initialization by scaling the weights of each layer by (0.001) 1/h so the output is scaled by 0.001, where h is the network depth. We train the network using SGD with learning rate 0.01 and momentum 0.9 for 100 epochs.
CIFAR-10 & CIFAR-100 We use VGG-16 (without batch normalization) for CIFAR-10 and C00, We use Kaiming initialization for the weights and set all bias terms as zero. We run SGD with momentum 0.9 and weight decay 1e-4 for 100 epochs. For the learning rate, we start from 0.01 and reduce it by a factor of 0.1 at the 60-th epoch and 90-th epoch.
We linearly interpolate using 50 evenly spaced points between the network at initialization and the network at the end of training. We evaluate error and loss on the train set. For cach setting, we repeat the experiments three times from different random seeds and plot the mean and deviation.
Note in Figure 1, to contrast the convex curve and plateau curve, we have used FCN4 with standard initialization on MNIST, and VGG-16 with 0.001 initialization on CIFAR-10.
Our code is based on the implementation from Lucas et al. (2021). Each trial of our experiment can be finished on an Nvidia Tesla P100 within one hour.
34

---

Published as a conference paper at ICLR 2023
D.1 ALL BIAS V.S. LAST BIAS V.S. NO BIAS
Loss Interrpo at on, Fecrion-RAST
Troor Interpotation Tash ensFRSST
Loss Inoerelation CIAR-10
Enor Interpsiation. CBFR-11
15
02
03
Figure 9: Comparison between networks with all bias, last bias and no bias on Eashion-MNIS, and 10.
Figure shows that on both Fashion-MNIST and CIFAR-I0, having bias on the last layer or on all layers can create longer plateau in eтror curve, while does not significantly affect the loss curve.
D.2 NORMAL INTERPOLATION V.S. HOMOGENEOUS INTERPOLATION.
Loss interpolaton on, Fashion WUST
Erarr inter on Fashion WNIST
Loss interpalat CIFAR110
Enor interpalation CHARR
bol rermul
66
krt remeal
MAL FOTTal
0.5
Jome
0.2
0.6
05
0.5
0.6
0.5
60
3.2
0.4
0.6
0.0
0.6
6.
Figure 10: Comparison between networks with normal interpolation and homogeneous interpolation on bias on
and CIFAR-10.
Figure 10 shows that on both MaSSion-MNIST and CIFAR-10, 10, applying homogeneous interpolation on biases can significantly reduce the plateau on error interpolation curve.
D.3 DIFFERENT INITIALIZATIONS
Intel
2021
3.303
IiEd 50
Figure 11: Comparison between networks with different initialization scales on MNIST and CIFAR- 100 with last bias.
Pastton WUST
interse WIIST
insersoiation,
Interpolation,
23
03
1.5
DA
15
1.0
0.5
03
63
60
60
60
62
04
0.5
0.3
3.3
60
62
04
05
60
3.0
8.
62
64
0.5
0.
2.0
86
62
64
66
60
2.0
Figure 12: Comparison between networks with different initialization scales on and CIFAR-10 with all bias.
35

---

Published as a conference paper at ICLR 2023
Loss ontorpaation Fashion MMSTT
Eriur inter ston, Fashian MMST
on, CIFA-10
Enu incorslationn CIRAR
1800
Intort
5 1.5
022
1nt-2.021
Figure 13: Comparison between networks with different initialization scales on Rashion-MNIST and CIFAR-10 with last bias.
Smaller initialization creates longer plateau in both error and loss curves. See Figure 11 for MNIST, CIFAR-100 1-0 with last bias; see Figure 12 for Fashion-MNIST, CIFAR-10 with all bias; see Figure 13 for Fashion-MNIST, CIFAR-I0 with last bias.
D.4 DIFFERENT DEPTHS
Loss Inderpolation. PRIST
Erao Interpolation, MhitT
Loss Interpaiation, CIFA--100
Error Intrrsiation, CFAR-100
VB011
Roa
1.5
V5511
01-
Figure 14: Comparison between networks with different depth on MNIST and CIFAR-100 with last bias.
Loss Interrto on. Fashion VIBST
Brror Interpotation on, Fach
MMST
Loss Intersoladio, CFAR-10
Eroo Interpotation. OFAR-
FCM
PCM
VO223
PCM
PCS
VC22
1.0
Figure 15: Comparison between networks with different depth MaShion-MNIST and CIFAR-10 with all bias. We use 0.001 initialization scale for VGG-16 on CIFAR-10.
Interro Tawhion-V9851
Interpstat en, Tash end/NISt
Inoerzolados, CLAMI-1
Ener Inderpolation. CIAA8-10
20-
2.
1.0
V0013
08
VO033
VC023
0.4
05
04
05
0.3
044
0.5
04
0.5
Figure 16: Comparison between networks with different depth on Fashion-MNIS and CIFAR-10 with last bias. We use 0.001 initialization scale for VGG-16 on CIFAR-10.
Deeper networks create longer plateau in both error and loss curves. See Figure 14 for MNIST, CIFAR-100 100 with last bias; see Figure 15 for for Fashion-MNIST CIFAR-10 with last bias.
CIFAR- 10 with all bias; see Figure 16
36

---

Published as a conference paper at ICLR 2023
D.5 BIAS DYNAMICS
Tram Loss. 2 Cass HNIST
Tr n Loss. Class MUIST
Plas. 2-Cass MNSST
0.10
Mla)
03-
0.1
0.95
0.30
02-
-0.05
431
-20
-0.0
25
0.000
693ch
opoch
Figure 17: Train loss for each class and bias term dynamics on MNIST(1, 2} and MNIST 3/.
In Figure 17, give more examples two-class MNIST in which the later learned class has larger bias.
Lass, 3 Class MNIST
Dias Der valive S-lasss MABST
KS 3iClass MINST
0.04
0.6-
60-
0.4
0.2
-62
0.3
15
20
15
20
90
10
32
15
30
spach
Figure 18: Train loss for each class and bias term dynamics on MNIST
In Figure 18, although class 9 is learned last, class 7 gets the largest bias after training. Let S be the set of all samples for number 7,8,9 and let S7, Sg, Sg be the set of samples for each class. For convenience, use u. to denote [ST Eves, uz(x), where u.(x) is the softmax output for class under input x. Then, we can write down the derivative on three bias terms:
by
U7,7 - 11,88 U7,9
bg 18.7 11..8 18.9
by U1,7 Ug,8 U9
According to the per-class loss, we know that E Eves, log (ur (ur(x)) Exes, log (x)), which intuitively implies that Exes, u7(x) Exss, (1) that is W1,7 Ugy9. This tends to drive by smaller than b9 However, because U9,8 47 actually have 69 < b7. So eventually by becomes smaller than by. Intuitively, class 9 is more correlated with class 8, so ug,s > U7,8-
37


Reviews:
[{"review_id": "vuQFruP9pj", "reviewer": "Reviewer_snjJ", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper shows that monotonic linear interpolations (MLIs), commonly used to study the loss landscapes of neural networks (NNs), may be misleading if used to estimate problem difficulty. Specifically, it is shown (both theoretically and empirically) that the plateaus on the MLI plots, attributed to problem “hardness”, are in fact related to the bias training dynamics. The authors argue that the flatness of the MLI curve can be easily manipulated by tweaking hyper parameters such as initialisation range and network depth. The authors also make an interesting observation that the class that happens to be learned last by the NN ends up with the strongest (largest) bias.", "summary_of_the_review": "Overall, I think this is a good paper that may yield interesting discussions in the community. Developing theory of NN learning is crucial for the field, and this work adds to the overall understanding, even if in a humble way.", "strength_and_weaknesses": "Strengths:\n* The paper challenges the naive use of a crude estimation to make far-reaching conclusions. I strongly resonate with the message: do not over-interpret, aim to fully understand first.\n* The results are supported by both theory and practice. The experiments are realistic and do not over-simplify the application domain.\n\nWeaknesses:\n* The overall presentation flow is a bit incoherent, with numerous past and future references to sections and figures. I found myself furiously scrolling up and down in an attempt to follow the plot. \n* The authors “attribute the plateau to simple reasons as the bias terms, the network initialization scale and the network depth”. Specifically for the last two, it is shown that smaller initialisation and larger depth lead to bigger plateaus. But is it really that unfair to correlate these with problem difficulty? Intuitively, weights initialised in a smaller region would yield weaker gradients in a deep network, which may slow down the learning = make the problem harder. Similarly, deeper networks experience vanishing gradients, which once again increases the difficulty of learning. Stating these as “simple reasons” sounds like an oversimplification.\n* The paper contains a few small grammatical and formatting mistakes, please refer to the following non-exhaustive list of suggested corrections:\n\n\t\tPage 2: “Under this model we can show” - the sentence ends abruptly with no punctuation, consider adding “…that:” or otherwise rephrasing.\n\t\tPage 4: “achieve loss approximately” -> achieve a loss of approximately…\n\t\tPage 5: “detailed proof in Section C” - do you mean Appendix C?\n\t\tAppendix A: “We give two examples that illustrates” -> that illustrate", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "k7cSoAiQnFi", "reviewer": "Reviewer_jXBe", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper considers the problem of monotonic linear interpolation (MLI) in deep neural networks. That is, one connects the initialization of the neural network with the fully trained neural network through a line. Then one considers how the loss function behaves when one is interpolation between the weights at initialization and the weights at the fully trained neural networks. What has been observed is that in modern architectures, the loss stays first for some time at a plateau and then suddenly decreases as one is moving from the initialization to the fully trained neural network.\n\nThis paper argues that the reason for the reason for this phenomenon is that the biases in the last layer scale linearly with the interpolation parameter $\\theta$, whereas all the other parameter scale with $\\theta^r$, where $r$ denotes the number of layers. Importantly, they claim that there is one bias in the last layer which is much larger than all the others.\n\nThe paper makes the following contribution which corroborates these claims.\n1. They prove that if there is bias which is much larger than the others, then the phenomenon described above appears.\n2. They prove that in a simple toy setting there is indeed one bias which is larger than all the others (and they can subsequently use the results to strengthen the results in point 1 for this simple toy model.)\n3. They provide numerical experiments which corroborate 1. and 2.", "summary_of_the_review": "I think that this is a good paper, which has good theoretical and numerical experiments and which gives insight into an interesting question regarding the behaviour. of neural network training.\nFor these reasons, I think that this is a good paper which should be accepted.", "strength_and_weaknesses": "Strenghts: The problem in this paper is well-motivated and the paper is very nice to read. The explanations are convincing both in theory and practice. I think that this is a paper which should be of interest to the ICLR community.\n\nWeaknesses: The toy model is a bit simplistic but I think that this is OK since our understanding of neural network training is still very limited.\n\nTypos and minor issues:\n1. p. 4: \"$V_{\\max}$for all\" (blank space missing)\n2. p. 5, third line: \"where (the) weight vector\"\n3. p. 5: The work of Ge et al., 2021 is about tensor decomposition. Consider explaining how it connects to the setting in this paper and, in particular, to the chosen activation function.\n4. p. 5, statement of Theorem 2: \"Suppose the neural network, dataset and optimization procedure are as defined in Section 2.\" Are these things really all defined in Section 2? I cannot find them there. Please consider clarifying.\n5. p. 5, Theorem 2, statements 1 and 2: By using the notation $\\Omega (1)$, do you mean that there is a small constant $c>0$ such that these statements hold? Otherwise please clarify. \n6. p. 7: In the second statement of Theorem 3, consider replacing \"monotonically decreasing\" with \"strictly monotonically decreasing\"\n\nQuestions:\n1. p. 4, Theorem 1: It seems to me that Theorem 1 makes only Assumption 1 regarding the (fully) trained neural network.\nIs that really true? Do you not also need an assumption which says that the loss function is small at the end? Or am I missing something? Otherwise please consider adding the missing assumptions to the theorem.\n2. p. 4: \"Empirically, $\\frac{\\Delta_{\\min}}{2 V^r_{\\max}}$... does not change much when depth increases.\" Do you mean that you empirically notice that increases depth increases $\\Delta_{\\min}$?\n3. p. 5, beginning of page: Why do you need $r\\ge 3$? Why would $r=2$ not suffice?\n4. Suppose all biases would be equal after the network has been fully trained. Why can't you then prove that there is a plateau? There would still be the different scaling, i.e. $\\theta$ vs. $\\theta^r$. Consider adding this explanation to the main text.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "_G2M2GHX1pr", "reviewer": "Reviewer_K8b8", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper analyses the shape of the loss curve along the linear interpolation from initialization to minimum for neural networks. In particular, in analyses under which circumstances the loss curve is monotonic and when it exhibits a plateau. The paper shows theoretically that for fully-connected neural networks the existence of the plateau can be linked to the gap in last-layer biases and the network's initialization, independent of the difficulty of the optimization problem. Moreover, the paper analyzes the training dynamics wrt. this bias gap. These theoretical results are supported by empirical evidence on MNIST and CIFAR100.", "summary_of_the_review": "The paper presents novel theoretical results on the loss curve of the linear interpolation between initialization and minimum. These results indicate that the hardness of the learning problem plays little role in the existence of a plateau. Instead, the existence of a plateau can be linked to the bias terms, which in term can be linked to initialization and network depth. This is a valuable insight. The examples in the appendix that underpin this insight are great.\n\nThe theoretical analysis is limited to specific types of networks (fully-connected feed-forward networks with at least three layers and only an output bias for Sec 3 and two-layer fully-connected feed-forward networks with a specific polynomial activation function for Sec 4), but the empirical results are performed on standard DNNs (including VGG16). It would be great if the results in Sec. 3 and 4 could be linked, though, because now the assumptions on the network are mutually exclusive. \n\nNonetheless, the paper is insightful and relevant to the community, technically sound, and well-written.\n\nDetailed comments:\n- In Thm. 2: network as defined in Section 2 -> should be section 4\n- r is used both as number of layers in Sec 3 and as parameter of the activation function in Sec 4, this is a it confusing", "strength_and_weaknesses": "Strength:\n- strong theoretical contribution\n- empirical support for theoretical results\n- insightful conclusion that the shape of the loss curve along the linear interpolation is not indicative of the success of training or the simplicity of the optimization problem\n\nWeaknesses:\n- the results on training dynamics hold only for a two-layer FCNN with specific activation\n- Thm .1 does not apply to the r-homogeneous-weight network used in the following section, since it requires a neural network with at least 3 layers", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "4otcc3Rccl_", "reviewer": "Reviewer_KBHX", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper explores how plateau occur in the loss curves of neural networks. Specifically, it shows that a significantly different last-layer bias may result in a long plateau in the loss and error curves. It also analyzes how gradient dynamics generates such bias gap during training with a simplified classification model. Numerical experiments support the proposed theory.", "summary_of_the_review": "In summary, I think the paper is in the right direction and presents new ideas. I recommend accepting this paper.", "strength_and_weaknesses": "Overall I enjoy reading this paper. The paper proposes a novel view of the MLI property, which is related to the last-layer biases. The observation is not previously explained, and could be a good supplementary of the existing theory of MLI. I personally like the implicit idea presented by the authors that a seemingly common optimization property is actually \"not common\", but dependent on specific factors instead. This might explain why it is so difficult to obtain a common but useful theory for neural nets.\n\nI have some questions regarding the results in the paper and would like to learn the authors' opinions.\n\n1. The paper's setting considers a classification problem with a cross-entropy loss. Do authors expect similar phenomenon happens in other problems such as regression problems, or with a different type of loss function?\n\n2. It seems that by Theorem 1, we can only predict the length of the plateau after we train the network and obtain the final bias gap. Is there a way of knowing the length of the plateau before training (if the initialization is known)? \n\n3. In the experiments, will changing the initialization affect the sequence of the class learned during training? For example, assume that in one experiment, class 1 is learned first and then class 2 is learned. By theory, the bias term in class 1 is smaller than class 2. Is it possible that class 2 turns to be learned first when we change a different initialization? In this case, the bias term in class 2 is smaller than class 1, and thus the two experiments result in very different outputs (although they may have similar loss or even similar training dynamics). ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster