Early Stopping in Deep Networks: Double Descent and How to Eliminate it
Authors: Reinhard Heckel
Fatih Furkan Yilmaz
Venue: ICLR 2021 Poster (2021)
Keywords: early stopping
double descent

Abstract: Over-parameterized models, such as large deep networks, often exhibit a double descent phenomenon, whereas a function of model size, error first decreases, increases, and decreases at last. This intriguing double descent behavior also occurs as a function of training epochs and has been conjectured to arise because training epochs control the model complexity. In this paper, we show that such epoch-wise double descent occurs for a different reason: It is caused by a superposition of two or more bias-variance tradeoffs that arise because different parts of the network are learned at different epochs, and mitigating this by proper scaling of stepsizes can significantly improve the early stopping performance. We show this analytically for i) linear regression, where differently scaled features give rise to a superposition of bias-variance tradeoffs, and for ii) a wide two-layer neural network, where the first and second layers govern bias-variance tradeoffs. Inspired by this theory, we study two standard convolutional networks empirically and show that eliminating epoch-wise double descent through adjusting stepsizes of different layers improves the early stopping performance.

Published as a conference paper at ICLR 2021
EARLY STOPPING IN DEEP NETWORKS: DOUBLE DE- SCENT AND How TO ELIMINATE IT
Reinhard Heckel & Fatih Furkan Yilmaz"
Deptt. of Electrical and Computer Engineering, Technical University of Munich "Dept. of Electrical and Computer Engineering, Rice University
ABSTRACT
pver-parameterized models, such as large deep networks, often exhibit double descent phenomenon, where function of model size, error first decreases, in- creases, and decreases at last. This intriguing double descent behavior also occurs a function of training epochs and has been conjectured to arise because training epochs control the model complexity. In this paper, we show that such epoch- wise double descent occurs for different reason: It is caused by superposition of two or more bias-variance tradeoff's that arise because different parts of the network are learned different epochs, and mitigating this by proper scaling of stepsizes can significantly improve the early stopping performance. We show this analytically for i) linear regression, where differently scaled features give rise to a superposi- tion of bias-variance tradeoffs, and for ii) wide two-layer neural network, where the first and second layers govern birs-variance tradeoffs. Inspired by this theory, we study two standard convolutional networks empirically and show that elimi- nating epoch-wise double descent through adjusting stepsizes of different layers improves the early stopping performance.
INTRODUCTION
Most machine learning algorithms learn a function that predicts label from features. This function lies in hypothesis class, such as a neural networks parameterized by its weights. Learning amounts to fitting the parameters of the function by minimizing an empirical risk over the training examples. The goal is to learn function that performs well new examples, which are assumed to come from the same distribution as the training examples.
Classical machine learning theory says that the test error risk function of the size of the hypothesis class U-shaped: a small hypothesis class is not sufficiently expressive to have small error, and large one leads to overfitting spurious patterns in the data. The superposition of those two sources of errors, typically referred to as bias and variance, yields the classical U-shaped curve.
However, increasing the model size beyond the number of training examples decrease the error again. This phenomena. dubbed "double descent" by Bellkin et al. (2019) has been observed as early as 1995 by Opper (1995). and is relevant today because most modern machine learning models, in particular deep neural networks, operate in the over- weer-parameterized regime, where the error often de- creases again function of model size, and where the model is sufficiently expressive to describe any data, even noise.
Interestingly, this double descent behavior also occurs as a function of training time, as observed by Nakkiran et al. (2020a) and as illustrated in Figure [ The left panel of Figure [ shows that as a function of training epochs, the test error first decreases, increases, and then decreases again. important to understand this so-called epoch-wise double descent behavior to determine the early stopping time that gives the best performance. Early stopping, or other regularization techniques, critical for learning from noisy labels (Arpit et al. 2017 Yilmaz & Heckel 2020).
Nakkiran et al. 2020a) conjectured that epoch-wise double descent occurs because the training time controls the "effective model complexity". This conjecture is intuitive, because the model-size, and thus the size of the hypothesis class, can be controlled by regularizing the empirical risk via early stopping the gradient descent iterations, formalized in the pardtttrrraeteeizeee regime by Yao

---

Published as a conference paper at ICLR 2021
best early stopping time
best early stopping time
0.4
test train bias
bias-variance 1 bias-variance
train/test error
0.3
0.3
risk=1 +
risk
0.2
variance
0.2
0.1
0.1
10
10a
10a
100
10
10a
10a
104
epoch
[ <iterations
The test and train error curves of an over-parameterized 5-layer convolutional net- work trained on the CIFAR-10 training set with 20% random label noise. As observed by Nakkiran al. (2020a), the performance shows double descent behavior. Right: As we show here, the risk of a regression problem can be decomposed as the sum of two bias-variance tradeoffs. Both exam- ples: Early stopping the training where the test error achieves its minima is critical for performance.
Figure 1: Left:
et al. (2007); RRakutti et al. (2014); Bühlmann & Yu (2003). Specifically, limiting the number of gradient descent iterations ensures that the functions parameters lie in a ball around the initial parameters. While this conjecture might be true for certain problem setups, it is not consistent with our empirical observation for the 5-layer CNN studied by Nakkiran et al. (2020a): Specifically, the empirically measured overall bias in Figure i increasing for some iterations, whereas an increasing model size would imply that it is decreasing (see Appendix B.2 for details on this experiment).
In this paper, we show empirically and theoretically that epoch-wise double descent-at least in the setups we observed it- arises for a different reason: It is explained by a superposition of bias- variance tradeoffs, illustrated for toy-regression example in the right panel of Figure [ If the risk can be decomposed into two U-shaped bias-variance tradeoff's with minima at different epochs/iterations, then the overall risk/test error has double descent behavior.
We also note that epoch-wise double descent is not phenomena tied to over- parraamattrriziionnn Both under- and overparameterized models can have epoch-wise double descent as we show in this paper. 1.1 CONTRIBUTIONS
The goal of this paper is to understand the epoch-wise double descent behavior. Our main finding is that epoch-wise double descent can be explained as superposition of bias variance tradeoffs, and arises naturally in some standard neural networks because parts of the network are learned faster than others. Our contributions are as follows:
First, we consider a linear regression model and theoretically characterize the risk of early stopped least squares. We show that if features have different scales, then the early stopped least squares estimate as a function of the early stopping time is a superposition of bias variance tradeoffs, which right panel).
yields double descent like curve (see Figure |
Second, we characterize the early stopped risk of a two-layer neural network theoretically and show that it is upper bounded by curve consisting of over-lapping bias-variance tradeoffs that gov- erned by the initializations and stepsizes of the two layers. The initialization scales and stepsizes of the weights in the first and second layer determine whether double descent occurs or not. We provide numerical examples showing how epoch-wise double descent occurs when training such a two-layer network on data, and how can be eliminated by scaling the stepsizes of the layers accordingly.
Third, we study a standard 5-layer convolutional network as well as ResNet- 18 empirically. For the 5-layer convolutional network we find simiilillrryy as for the two-layer model model-epoch epoch-wise double descent occurs because the convolutional layers (representation layers) are learned faster than the final, fully connected layer. Similarl, for ResNet-18, we find that later layers are learned faster than early layers, which again results in double descent. In both cases, epoch-wise double descent can be eliminated through adjusting the stepsizes of different coefficients or layers.
In summary, we provide new examples when epoch-wise double descent occurs, as well as ana- lytical results explaining epoch-wise double descent theoretically. Our theory is constructive in that it suggests simple and effective mitigation strategy: scaling stepsizes appropriately. We also note that epoch-wise double descent should be eliminated by adjusting the stepsizes and/or the initializa- tion, because this often translates to better overall performance.
2

---

Published as a conference paper at ICLR 2021
1.2 RELATED WORKS
There is large number of works that have studied early stopping theoretically. Intuitively, each step of an iterative algorithm reduces the bias but increases variance. Thus early stopping can ensure that neither bias variance are too large. A variety of papers Yao et al. (2007); Raskutti et al. (2014); Bühlmann & Yu (2003): Wei et al. (2019) formalized this intuition and developed theoretically sound early stopping rules. Those works do not, however, predict when double descent curve can occur.
A second, more recent line of works, studies early stopping from a different perspective, namely that of gradient descent fitting different components of a signal or different labels at different speeds. For linear least squares, the data in the direction of singular vectors associated with large singular values is fitted faster than that in the direction of singular vectors associated with small singular values. Advani et al. (2020) have shown this for a linear least squares problem or stated differently, linear neural network with single layer. Li al. (2020); Arora et al.) (2019) have shown that this view explains why neural network often fit clean labels before noisy ones, and Heckel & Soltanolkotabi 22200b have used this view to prove that convolutional neural networks provably denoise images.
Our theoretical results for neural networks build on line of works that relate the dynamics of gradient descent to those of an associated linear model or a kernel method in the highly overparam- eterized regime iaacot et al. [2018)] Lee et al. (2018); Arora et al. (2019); [uu et al. (2018); Oymak & Soltanolkotabi (2020); Oymak et al. (2019): Heckel & Soltanolkotahi (2020b). We use the same proof strategy those papers to characterize the early stopping performance of simple two-layer neural network, but in contrast to those earlier works, we develop early stopping results and optimize over both the weights in the first and second layer, opposed only optimizing over the weights in the first layer. That is important, because we want to demonstrate that initialization and stepsize choices of different layers lead to different bias-variance tradeoffs.
Next, we note that there is an emerging line of works that theoretically establishes double descent behavior as function of the model complexity (e.g., measured by the number of parameters) for linear regression Hastie et al.] (011)); [elkin et al. (2020), for random feature regression Mei &
Montanari 2019 d' Ascoli et al. (2020), and for binary linear regression Deng et al. (2020).
A number of recent theoretical double-descent works Jacot et al. 2200)) Yang et al. (220);; d' A'Asclli al. (2020) have decomposed the risk into bias and variance terms, and studied their behavior. Those works demonstrate that the bias typically decreases as function of the model size, and the variance first increases, and then decreases, which can yield a double-descent behavior. As we demonstrate in Appendix B.2 the epoch-wise double descení phenomena for the standard CNN studied by Nakkiran et al. (2020a) cannot be explained with this observation: The variance is in- creasing function of training epochs, opposed to being unimodal.
Finally, our suggestion to mitigate epoch-wise double descent with step-size adaption and early stop- ping is form of regularization. Related work for model-wise double descent shows that model-wise double descent can be mitigated with (E2) regularization Nakkiran et al. (2020b). and & regulariza- tion and early stopping are strongly related (Ali et al. 2019).
2 EARLY-STOPPED GRADIENT DESCENT FOR LINEAR LEAST SQUARES
We start by studying the risk of early stopped gradient descent for fitting a linear model to data generated by Gaussian linear model. Our main finding is that the risk as a function of the early stopping time is characterized by a superposition of U-shaped biai-variance tradeoffs, and the features of the Gaussian linear model have different scales, those bias-variance tradeoff curves add up to a double descent shaped risk curve. We also show that the performance of the estimator can be improved through double descent climination by scaling the stepsizes associated with the features.
2.1 DATA MODEL AND RISK
Consider a regression problem, and suppose data is generated from a Gaussian linear model as y (x, 0r) + 2, where x E Idd a zero-mean Gaussian feature vector with diagonal co- co-variance matrix Σ = diag(o?. ... 22), and 2 is independent, zero-mean Gaussian noise with variance o². We are given a training set = {(x), y1...... (X,, } consisting of n data points drawn iid from this Gaussian linear model. We consider the class of linear estimators parameterized by vector
3

---

Published as a conference paper at ICLR 2021
0 Rd, which estimate based the training data D. The linear estimator predicts the label associated with feature vector as yj x" 0. The (mean-squared) risk of this estimator is
R(O) IE [ (v-x'
where expectation over an example (x, y) drawn independently (of the training set) from the underlying linear model.
2.2 EARLY-STOPPED LEAST SQUARES ESTIMATE
We consider the estimate based on early stopping gradient descent applied to the empirical risk
n 7 Σ y x²
1
R(
We initialize gradient descent with 0 O and iterate, for t = 1, with updates 0 -- di-d R(0'), where diag(n) is a diagonal matrix containing the stepsizes 7) >> 0 associated with each of the features as entries. Note that we allow for different stepsizes for all the features. In the following, study the properties of the iterates i.e., 0'
2.3 RISK OF EARLY STOPPED LEAST SQUARES
The main result of this section is that in the underparameterizzed regime, where d < n, the risk of gradient descent after iterations, R(0*), is very close a risk expression defined
(1-01 d011 (1-1 ))))))
R( = 0² (1 1 ?
(1)
(.(1)
formalized by the theorem below. We focus the underparameterized regime here, because in the over over-paramenn peer-paramttrizee regime our estimator cannot achieve small risk in general. In Section we study a more general setting in the overparameterized regime.
Theorem 1. Suppose that the stepsizes obey ` S for all i l,... d With probability at least
2d 5 2de-" n/8 -e 2e 32 over the random training set generated by a linear Gaussian model with parameters 0* and E. the difference of the early stopped risk and the risk expression in ① at iteration t is at most
max; 11 d min; n/.0
d _ log(d) + 0² -vva
[R(0') R(OO) R <c
| 12
(2)
n
Here, is numerical constant.
Theorem guarantees that with high probability the risk R(O*) well approximated by the risk expression R(0O),, provided the model is sufficiently underparameterized (i.e., d/n is small).
As consequence, the risk of early stopped least-squares is superposition of U-shaped bias- variance tradeoffs, and if the features are differently scaled, this can give rise to epoch-wise double descent. To see this, first note that the terms (t) in the risk expression [ are U-shaped as a func- tion the early stopping time f, because (1=)07=)) decreases in f. and _ (1-11-1.03))
increases in 1; see Figure 2h for example. The minima of the individual U-shaped curves (t) depend on the product of the stepsize and the i-th features' variance, n. the larger this product, the earlier (as function of the number of iterations, t) the respective U-shaped curve reaches its minimum. Therefore, if we add up two (or more) such U-shaped curves with minima at different iterations, the resulting risk curve can have double descent shape (again, see Figure p This establishes our claim that differently scaled features can give rise to epoch-we wise double descent.
Finally we note that the reason why we refer the U-shaped curves as bias- bias-variance tradeoffs,, is that the terms Σi= (8;)) - 2 and Ei= o² (1 (1 - ))) in the risk expression (T) are approximately equal to the bias and the variance of the model 0¹ in the standard textbook bias- variance decomposition of the risk, Appendix A.2 for detailed discussion.
4

---

Published as a conference paper at ICLR 2021
best stopping time
best stopping time
0.4
I-.. varianee
-... bins variance
142
0.3
hias Mlas-variance 2
bins-variance 3
1+3
1+2
1+3
nisk
0.2
0.1
0
10
10a
10a
10a
10a
10
10a
10a
10a
10a
10a
10a
10a
10a
10
iterations
f itteaaions
t iiterations
constant stepsize
b) climination with diff. stepsizes
c) before after elimination
Figure 2: Early stopped least squares risk for two-feature Gaussian linear model. a: Two U- shaped bias- varianer tradeoffs (t) for the parameters 01 = 1.5, 01 = 1, 71 = 0.05 Obias-variance 1) and 0Σ 10, 02 0.15, 7/2 0.05 (bias-variance 2), along with their sum (1+2) which deter- mines the risk. b: Same plot, but this time the bias-variance tradeoff (2 is shifted to the left by increasing the stepsize 7/2 according minimum overlaps with that of biri-variance tradeoff 1. This eliminates double descent and gives better performance. The resulting risk curves before and after elimination, demonstrating that the minimum of the risk after double descent elimination is smaller than before elimination.
Proposition [ (yielding bias-variance tradeoff 3), that its
Improving performance by eliminating double descent: Epoch-wise double descent can be eliminated by properly scaling the stepsizes associated with each of the features, so that the minima of the individual bias-variance tradeoff's overlap at the same iteration i:
Proposition Pick an optimal early stopping time i 2 1. The minimun of the risk expression min min; R((0) achieved iteration i by choosing the stepsizes pertaining the features
as T4 = (1 (1-
02/n
1/6
Elimination of double descent illustrated in Figure 2b. that all the individual saarivarannce tradeoffs (,( achieve their minima at the same early stopping point f. we achieve the lowest overall risk at the optimal early stopping point. Thus eliminating dou- ble descent is important for optimal performance. In practice typically do not know the variances of the features and therefore may not be able to optimally choose the stepsizes. However, we may be able to mitigate double descent sub-optimally by treating the stepsizes hyperparameters.
By eliminating double descent optimally so
3 EARLY STOPPING IN TWO LAYER NEURAL NETWORKS
In this section, we establish bound on the risk of a two-layer neural network and show that this bound can be interpreted as super-position of U-shaped bias-variance tradcoffs, similar to the expression governing the risk of the linear model from the previous section. The risk of the two- layer network is governed by two associated kernels pertaining to the first and second layer, and the initialization scale and stepsizes of the weights in the first and second layer determine whether double descent occurs or not. We also show in an experiment that if double descent occurs, can be eliminated by adapting the stepsizes of the two layers.
Network model:
We consider two-layer neural network with ReLU activation functions and neurons in the hidden layer: (w, = relu(x" W)v.. Here, x E IRd is the input of the network, W Baxk and R* the weights of the first and second layer. Moreover, relu(z) max(z,0) 0) is the rectified linear unit, applied elementwise.
Data model: We assume that ples (x, yi) drawn iid from some joint distribution. For convenience, we assume that the datapoints normalized, i.e., |Xx||22 1, and the labels bounded, i.e., |ys| < 1.
given training set D {X1, yı)...., (Xn: Vn with exam-
5

---

Published as a conference paper at ICLR 2021
Training with early stopped gradient descent: We train the network with early stopped and randomly initialized gradient descent on a quadratic loss. We choose the weights at initialization as
[ hi. (O,, [v"] Uniform((-v,1)) v))-
(3)
Here, s and are parameters that trade off the magnitude of the weights of the first and second layer. Note that with this initialization, for a fixed unit norm feature vector we have fw.. (x) = Olvw). We apply gradient descent to the mean-squared loss
1 Σ (u fw,v(x;))? L(W, v)
2
The gradient descent updates are Vi+1 = VV vo) and W = W vi), where 17 is a constant learning rate. We study the risk of the network as function of the iterations t.
Evaluation and performance metrie: Our goal is to bound the test error as a function of the iterations of gradient descent. Let l: R R + [0, 1] be loss function that is 1-Lipschitz in its first argument and obeys E(y, y) = 0; a concrete example is the loss ((2, y) = 2z y for arguments 2, E [0, 1]. The test error risk is defined, as before, as R(J) = B [x)](x) y)] where expectation is over examples (x.y) drawn from the unknown joint distribution from which the training set is drawn well.
3.1
RISK OF EARLY STOPPED NEURAL NETWORK TRAINING
Our main result is bound the test error of the two layer neural network trained for t iterations, in the regime where the network is very wide. The result depends on the Gram matrix Σ Raxx determined by kernels associated with the first and second layer of the network. The (1. (-th) entry of the Gram matrix as a function of the training examples is defined as
Σg = 1/2 K1 (x,, x,) + wa K2(x,, Xx),
(4)
with kernels
1 2 (1 cos
cos 1 (pis)
K1 (x(,,,,,)
Pij.
and K2(x;,))) = K1 (x),,)) + /1 //-22/(22T) (2T).
where Pij -(xixx) (recall that assume |xi||2 = 1, for all i). Our result depends on the singular values and vectors of this Gram matrix: Σ - u.u We are now ready to state our result.
of
Theorem 2. Let a > 0 be the smallest eigenvalue of the Gram matrix E, suppose that the network sufficiently wide, i.e., k 2 Th ). and suppose the initialization scale parameters obey vw S aa/ /32 (og(2n/ō) and + w S for some 5 E (0, 1). Then, with probability at least 1 - 5, the risk of the network trained with gradient descent for iterations is at most
uu y) (1 (1 no?
R(Jw..)) S
() -1-189 (11-07)22 +
+0
n
o?
(5)
Regarding the assumptions of the theorem, remark that while the exponent of and in the width-condition (k: 2 Ω ( min((w)) ) can be improved, the width condition ensures that the network is sufficiently wide so that the network operates the kernel regime where the network behaves similar to associated linear model. Regarding the assumption that the smallest eigenvalue of the Gram matrix obeys a > 0, Theorem 3.1 by Du et al. (2019) shows that if no two X,, X, are parallel, then 0, for very related Gram matrix (specifically, the Gram matrix only consisting of the kernel K2 defined above). As argued in that work, for most real-world datasets no two inputs parallel, therefore this assumption is rather mild.
The risk bound established by Theorem 2 can be interpreted as a superposition of n- n-many U-shaped bias variance tradeoffs, similar the expression (1) governing the risk of early stopped linear least

---

Published as a conference paper at ICLR 2021
squares. Specifically, the i-th "bias" term y) (1 ) decreases in the number of gradient descent iterations t, while the i-th "variance" term y) (1-(1-10))) increases in the number of
of gradient descent iterations. The speed which the two terms increase and decrease, respectively, is determined by the singular value of. Those singular values, in turn, are determined by the kernels K1 and K2, the random initialization (in particular the scale parameters v, W), and the distribution of the examples. Whether epoch-wise double descent occurs or not depends on those singular values
and therefore on the kernels, the initialization, and the distribution of the examples, as illustrated with the following numerical example.
Numerical example to illustrate the theorem: We draw data from the linear model specified in Section 2. with geometrically decaying diagonal co-variance entries and zero additive noise. We then train the network for different initialization scale parameters w, once with the same stepsize for both layers (1) = 8e-5), and once with a smaller stepsize for the second layer, i... 7/W = 8e-5 and fΙ 1e-6. In the top row of Figure it can be seen that the empirical risk has double-descent behavior both layers are initialized at the same scale (i.e., w = 1).
To understand the relation to the theorem better, we also plot in Figure 3 the extent to which the singular values are associated with the parameters in the first and second layer. To capture this, we first comment on the relation of the parameters of the first and second layer to the singular values of and vectors uf of the Gram matrix: In the wide-network regime in which the theorem applies, the networks output is well approximated by its linearization around around the initialization. With this, the networks predictions for the training examples are approximately
[fw,v(x1]
Vect(W)
n
Σ
Co Vec((W) + v vf i=1
(6)
(w.)(
where Baxdk** is (approximately) the Jacobian of the network at initialization and J Ei= v. is its singular value decomposition. Here, denote by v.,w Rdth and Vs,v R the parts of the right-singular vectors of the Jacobian associated with the weights in the first and second layer, respectively. The norm of those vectors measures to what extent the singular value o, is associated with the weights in the first and second layer.
Returning to the numerical example, as the bottom row of Figure 3 if we initialize both layers at the same scale (w = = 1), then most of the large singular values are associated, for the most part, with the weights in the second layer. This leads to double descent, that can be mitigated by choosing smaller stepsize associated with the weights in the second layer.
Improving performance by eliminating double descent: Similarly as for the linear least squares problem studied in the previous section, it is possible shape the bias variance tradeoff's by adapting the stepsizes (or through initialization of the layers). In Figure 3 we illustrate this behavior: Double descent is eliminated by choosing a smaller stepsize for the second layer, or by choosing smaller initialization for the first layer, as suggested by our theoretical results, and similar to the linear least squares setup as discussed in the previous section. Also note that, not only does choosing smaller stepsize for the second layer eliminate double descent, it also gives a better overall risk.
To understand the relation to the kernels, suppose we choose the initialization equally, i.e., w and v = 1. If we update the variables of the second layer (i.e., v) with a much larger stepsize than that of the first layer (i.e., W), then the kernel associated with the second layer dominates and the network behaves like random feature model Rahimi & Recht (2008). Similarly, if we update the variables of the first layer with a much larger stepsize than that of the second layer, then the network behaves like a network with the final layer weights fixed. Thus, the stepsizes trade off the impact of the two kernels, and this tradeoff yields a double descent curve.
4 EARLY STOPPING IN CONVOLUTIONAL NEURAL NETWORKS
We finally study the training of standard 5-layer convolutional neural network (CNN) and stan- dard ResNet-18 18 model on the (10 class classification) CIFAR- 10 dataset. Both networks were stud- ied in Nakkiran al. 2020a). As shown in that paper, the risk has a double descent behavior if the
7

---

Published as a conference paper at ICLR 2021
a) w 0.01;
= = 1,==1
c) 1; 0.01
same stepsize
15
different stepeize
risk
10
-in mi
THa may
10
10
10a
10
10
10a
10 10
10a 10
10
10a
100
10
10a
10a
10
10
iterations
iterations
iterations
0.5
10 02
10
10 0,
10
10' 0z
10a
Figure 3: Top row: Risk of the two-layer neural network trained on data drawn from a linear model with diagonal covariance matrix with geometrically decaying variances. The risk has double descent curve unless we either i) initialize the first layer with a smaller initialization strength w than the second one V, or we choose a smaller stepsize for the weights in the second layer. Both improves the risk as suggested by the theory. Bottom row: The norms l/v, and V/v measure to what extend the singular values d; are associated with the weights in the first (W) and second (v) layer respectively. Double descent occurs when singular values are mostly associated with the second layer, because then those weights are learned faster relative to the first layer weights.
stepsize
smaller stepsize fully connected layer
0.5
fully connected layer
test test error
0.4
train error
0.4
conv layers
0.5
0.3
0.2
0.2
0
101.5 102 102.5
10
10a
102
IIE
103
0
100
[IIM 1
10a
1111
102
10
0
epoch
epoch
Figure 4: Mitigating double descent for a 5-layer CNN. Left: Norm of the parts of the right singular vectors of the Jacobian associated with the weights in the convolutional VG, and fully connected layers Vi.r function of the singular values, d, showing that large singular values pertain mostly the fully connected layer. This causes the fully connected layer to be learned faster than the convolution layer. Middle and Right: Performance when trained with the i) same stepsize for all layers, and ii) a smaller stepsize for the fully connected layer. Decreasing the learning rate of the fully connected layer causes it to be learned similar speed the convolutional layers and thereby eliminates double descent and increases performance (i.e., the minima is smaller than that i).
network is trained dataset with label noise, and consider the setup with 20% random label noise. While we have no theoretical results for those two complicated neural network models, demonstrate inseeeeeddede our theory- that epoch-wise double descent can be eliminated and the early stopping performance can be improved by adjusting the stepsizes/learming rates.
5-layer CNN: The 5-layer CNN consists for 4 convolutional layers followed by a fully connected layer. Figure shows that, just like for the two-layer network from the previous section, double descent can be climinated by changing stepsizes, this time by decreasing the stepsize of the final fully connected layer. The intuition behind this is that large singular values of the Jacobian of the network at initialization are mostly associated with the last fully connected layer, measured in the same way in the previous section. This causes the convolutional layers to be learned slower than the fully connected layer which results in double descent. Analogously as before, decreasing the stepsize pertaining the fully connected layer eliminates double descent.
ResNet-18: We next consider the popular ResNet-1k 18 model. ResNet-18 has a double descent behavior when trained the noisy CIFAR-10 problem Nakkiran et al. 2020a). Inspired by
8

---

Published as a conference paper at ICLR 2021
theory, again hypothesize that the double descent behavior occurs because some layer(s) of the ResNet- 18 model are fitted at a faster rate than others. If that hypothesis is true, then scaling the learning rates of some layers should eliminate double descent. Indeed, Figure 6 in the appendix shows that when scaling the stepsizes of the later half of the layers of the network mitigates double descent.
CODE
Code to reproduce the experiments is available at altttpss//gtthbb.c.///// lecps_dduu_____eeeeeeee
ACKNOWLEDGEMENTS
F. Yilmaz and R. Heckel are (partially) supported by NSF award 118-1816986. Heckel also acknowledges support by the TUM Institute of Advanced Study, and the authors would like to thank Fanny Yang and Alexandru Tifrea for discussions and helpful comments on this manuscript.
REFERENCES
Madhu S Advani, Andrew M Saxe, and Haim Sompolinsky. High-dimensional dynamics of gener- alization error in neural networks. Neural Newwors, 132:428-446, 2020.
Alnur Ali, J Zico Kolter, and Ryan Tibshirani. continuous-timn view of early stopping for least squares regression. In The 22nd International Conference on Artificial Intelligence and Statistics, 2019.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks. In Inter- national Conference on Machine Learning, pp. 322-332, 2019.
Devansh Arpit, Stanislaw Jastrzkebski, Nicolas Ballas, David Krueger, Emmanuel Bengio, Maxin- der S. Kanwal, Tegan Maharaj, Asja Fischer, Aaron Courville, Yoshua Bengio, and Simon Lacoste-Julien. A closer look at memorization in deep networks. In International Conference on Machine Learning, pp. 233-242, 2017.
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine- learning practice and the classical bias-variance trade-off. Proceedings of the National Academy of Sciences, (1132)):18499-1888 2019.
Mikhail Belkin, Daniel Hsu, and Ji Xu. Two models of double descent for weak features. SIAM Journal on Mathematics of Data Science, 267):1167-1180, 2020.
Peter Bühlmann and Bin Yu. Boosting With the L2 Loss. Journal of the American Statistical Association, 98(462):324-33) 2003.
Amit Daniely, Roy Frostig, and Yoram Singer. Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivity. In Advances in Neural Information Processing Systems 29, pp. 2253-2261. 2016.
Stéphane d' Ascoli, Maria Refinetti, Giulio Biroli, and Florent Krzakala. Double Trouble in Double Descent Bias and Variance(s) in the Lazy Regime. In International Conference Machine Learning, 2020.
Zeyu Deng, Abla Kammoun, and Christos Thrampoulidis. A Model of Double Descent for High- dimensional Binary Linear Classification. arXiv: 191 1.05822 [cs, eess, stat), 2020.
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient Descent Finds Global Minima of Deep Neural Networks. In International Conference on Machine Learning, pp. 1675- 1685, 2019.

---

Published as a conference paper at ICLR 2021
Simon S. Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient Descent Provably Optimizes parampaaraeteriize Neural Networks. In International Conference on Learning Representations, 2018.
Simon Foucart and Rauhut, Holger. A Mathematical Introduction Compressive Sensing. Springer Berlin Heidelberg, 2013.
Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J. Tibshirani. Surprises in High- Dimensional Ridgeless Least Squares Interpolation. arXiv: arXiv: [cs, math, stat), 2019.
Reinhard Heckel and Mahdi Soltanolkotabi. Compressive sensing with un-trained neural networks: Gradient descent finds the smoothest approximation. In International Conference Machine Learning. 2020a.
Reinhard Heckel and Mahdi Soltanolkotabi. Denoising and Regularization via Exploiting the Struc- tural Bias of Convolutional Generators. In International Conference Learning Representations, 2020b.
Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural Tangent Kernel: Convergence and Generalization in Neural Networks. Advances in Neural Information Processing Systems, pp. 8571-8580 2018.
Arthur Jacot, Berfin Simsek, Francesco Spadaro, Clément Hongler, and Franck Gabriel. Implicit regularization of random feature models. In International Conference on Machine Learning. 2020.
Jaehoon Lee, Yasaman Bahri, Roman Novak, Samuel S. Schoenholz, Jeffrey Pennington, and Jascha Sohl-Dickstein. Deep Neural Networks as Gaussian Processes. In International Conference on Learning Representations, 2018.
Mingchen Li, Mahdi Soltanolkotabi, and Samet Oymak. Gradient Descent with Early Stopping is Provably Robust to Label Noise for Overparameterized Neural Networks. In International Conference on Artificial Intelligence and Statisties, 2020.
Song Mei and Andrea Montanari. The generalization error random features regression: Precise [math, stat), 2019.
asymptotics and double descent curve.
Mchryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning. MIT Press, 2012. ISBN 978-0-262-30473-3.
Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak, and Ilya Sutskever. Deep Double Descent: Where Bigger Models and More Data Hurt. In International Conference on Learning Representations, 2020a.
Preetum Nakkiran, Prayaag Venkat, Sham Kakade, and Tengyu Ma. Optimal Regularization Can Mitigate Double Descent. arXiv:2003.0189 [ex, math, stat), 2020b.
Manfred Opper. Statistical Mechanics of Learning Generalization. The Handbook of Brain Theory and Neural Networks, pp. 922-925. 1995.
Samet Oymak and Mahdi Soltanolkotabi. Towards moderate overparameterization: Global con- vergence guarantees for training shallow neural networks. IEEE Journal on Selected Areas in Information Theory, 2020.
Samet Oymak, Zalan Fabian, Mingchen Li, and Mahdi Soltanolkotabi. Generalization Guarantees for Neural Networks via Harnessing the Low-rank Structure of the Jacobian. arXiv:1906.05392 [cs, math, stat], 2019.
Ali Rahimi and Benjamin Recht. Random Features Large-Scale Kernel Machines. In Advances in Neural Information Processing Systems 20, pp. 1177-1184, 2008.
Garvesh Raskutti, Martin J Wainwright, and Bin Yu. Early Stopping and Non parametri Regres- sion: An Optimal Data-dependent Stopping Rule. Journal of Machine Learning Research, 15: 335-366. 2014.
10

---

Published as a conference paper at ICLR 2021
Martin Wainwright. High Dimensional Statistics: A Non-Asymptotic Viewpoint. Cambridge Univer- sity Press, 2019.
Yuting Wei, Fanny Yang, and Martin Wainwright. Early Stopping for Kernel Boosting Algorithms: A General Analysis With Localized Complexities. IEEE Transactions on Information Theory, 65 (10):6685-6700) 2019.
Zitong Yang, Yaodong Yu, Chong You, Jacob Steinhardt, and Yi Ma. Rethinking Bias- Variance Trade-off for Generalization of Neural Networks, In International Conference Machine Learn- ing. 2020.
Yuan Yao, Lorenzo Rosasco, and Andrea Caponnetto. On Early Stopping in Gradient Descent Learning. Constructive Approximation, 26(2):289-315 2007.
Fatih Furkan Yilmaz and Reinhard Heckel. Image recognition from raw labels collected without annotators.
[cs, stat), 2020.
A SUPPORTING MATERIAL FOR: EARLY-STOPPED GRADIENT DESCENT FOR LINEAR LEAST SQUARES
A.1 INTUITION FOR THE RISK EXPRESSION
Below, we provide a proof of Theorem ! risk expression
Here we provide intuition why the risk is governed by the
First, note that the risk of the estimator can be written as a function of the variances of the features, of, and of the coefficients of the underlying true linear model, 0" [0:..... ..t.....f0. (.], as
R(O) = + Σ 007 0.)
where we used that = and x are drawn independently.
Next, recall that consider the estimate based early stopping gradient descent applied to the empirical risk
(())) = X -0--ypp y
Here, the matrix X E Ruxd contains the scaled training feature vectors and y = vn ly....,, ynl are the corresponding scaled responses.
X1 vn
Vn Xn as rows,
The gradient descent iterates obey
0++1 0" = (I - diag(n) (0' -0) + (iag(n)
where .. 2n] is the noise. As we formalize below, in the under-paree ander-parameterized regime
where n >> d, we have that x 2 Therefore the original iterates are close to the proximal iterates Hr defined by
@ 0- = diag(n)E*>)) (Ø' 0*) + diag(n)
The proximal iterates are, up the extra term diag(n) 17) X TTz z, equal to the iterates of gradient descent applied to the population risk R(0). Note that in contrast to the literature where it is common to bound the deviation of the original iterates from the iterates on the population risk Raskutti et al. 2214), here we control the deviation of the original iterates the proximal iterates 0'.
The iterates @t can easily be written out in closed form. To do so, first note that for the recursion
+ 1-a" gt-l = at' + we have 6' = a0 + Σl=1 a² a'00 + + 1-a where we used the formula for geometric series. Using this relation, and that we are starting our iterations at 00 = 0, we obtain for the i-th entry of 6t that
(1 no?)
0: - -: = -1-no07)00 + 0x
of
11

---

Published as a conference paper at ICLR 2021
where x; is the i-th column of X (not the i-th example/feature vector!). Next note that, IE (x z o²a? because the entries of z are NN0 o2) distributed, and the entries of x; 1/ 1/VnW((0, o, distributed. Using this expectation in the iterates 0', and evaluating the risk of those iterates via the formula for the risk given by ( yields the risk expression (I). The proof of Theorem [ in the appendix makes this intuition precise by formally bounding the difference of the proximal iterates to the original iterates.
2)²
A.2 MOTIVATION FOR CALLING THE U-SHAPED CURVES BIAS- MASS-AAIANCE TRADEOFFS
Let = @DD be the parameter obtained based on the training data (for example by early stopping). The textbook bias-variance decomposition of the risk of 0 is
DD [(0)]] Ex ((x,0') - ED (x, 21 + EDxx
- ED (x, -<xx))_B|(<<,
to².
Bias(()
Variance(0)
The first term above is the bias of the hypothesis h(x) = 0 It measures how well the average
function can estimate the true underlying function fi(x) = (x. 0"). A low bias means that the hypothesis accurately estimates the true underlying function (x, 0*). The second term is the variance of the method. The variance of the method measures the variance of the hypothesis over the training sets.
Recall from the previous paragraph that the estimate Ø' approximates the original iterations well provided that the model is sufficiently underparameterizzed, i.e., d/ n/n is small. It is straightforward to "===((0)) (0:) - ?))?)a and Variance O²) Σx
a _1 - (1 )))) exactly equal to the bias and variance terms in the risk expression ① It follows that the bias and variance of the original gradient descent iterates O are also approximately equal to the terms in the risk expression (I. The U-shaped curves then the bias-variance terms pertaining the i-th feature; this formally establishes the U-shaped curves as birs-variance tradeoffs.
verify that (0*) = "i=
s==
A.3 NUMERICAL RESULTS FOR LINEAR LEAST SQUARES
In this section we provide further numerical results for linear least squares. We consider linear model with d = 700 features, and with n 6d examples. We let fraction 6/7 of the features have singular value a; = and associated model coefficient 0, = 1, and the rest, 1/7 of the features, have singular value
0.1 and 0g 10. In Figure (ggure/5ja) 5[a) show the risk obtained by simulating the risk empirically along with the risk expression R(O*) given by equation ① It can be seen that the risk expression R(00)) slightly under-estimates the true risk. The quality of the estimate becomes better as we increase n; in Figure 5 b) we show simulations for the same configuration but with n = 10d.
B SUPPORTING MATERIAL FOR: EARLY STOPPING IN CONVOLUTIONAL NEURAL NETWORKS
B.1 RESNET-18 TRAINING DOUBLE DESCENT ELIMININATION
In Figure 6 we provide test and train error curves for ResNet- 18 trained with different stepsizes on noisy CIFAR- 10. The results show that, as mentioned in the main body, double descent is eliminated by choosing the stepsizes appropriately.
In more detail: ResNet-18 18 consists of 18 layers in total, where there are 4 residual blocks, each fea- turing 4 convolutional layers with residual connections, between the first standalone convolutional layer and the last fully-connected layer. We consider standard SGD training of ResNet-18 on noisy CIFAR-10 with initial learning rate of = 0.1 and inverse square-root decay with decay rate T 512. This is the standard training setup for ResNet-18, and exactly the setup for which for which Nakkiran al. reported double-descent behavior. We found that similar the 5-layer volutional network, double descent occurs in ResNet-18 because some of the networks' layers are learned at different rates than others. We found that the weights of the last fully-connected layer
12

---

Published as a conference paper at ICLR 2021
R(0*)
R(0')
1.8
1.8
R(0")
R(0')
1.6
risk
1.6
1.4
1.2
1.2
10
10
102
10
104
10
10
102
10
104
t iterations
t iteraaionn
(a) n
(b) n = 10d
Figure 5: The risk of early-stopped gradient least-squares R((0)) based on numerical simulation of the Gaussian model along with the risk expression R((0') given in (T. We averaged over 100 runs of gradient descent, and the shaded region corresponds to one standard deviation over the runs. It can be seen that the risk expression slightly underestimates the true risk, but other than that describes the behavior of the risk well.
0.5
same slepsize
0.4
ii: smaller stepsize last half layers
0.3
test error
0.4
train crror
0.2
0.3
0.1
0.2
0
10
10
10
103
10
102
10a
epoch
epoch
Left: Test error of the ResNet-18 18 trained with the i) same stepsize for all layer, and with ii) smaller stepsize for the latter half of the layers. Decreasing the learning rate of the last layers causes the last layers to be learned at a similar speed as the first and thereby eliminates double descent. Right: The training error curves for i) and ii).
Figure 6:
as well as the last two residual blocks were learned faster relative to the other layers. Following the method inspired by our theory for the linear case and two-layer network and empirical obser- vations from the 5-layer convolutional network, we eliminate the double descent by decreasing the stepsizes of these layers 10-4 from 10-1 after few epochs. Note that ResNet- 18 has different architecture than the simple 5-layer convolutional network and the values chosen differ for the two networks. This is expected double descent depends on many factors such the underlying data distribution as well as the network architecture and training.
B.2 NUMERICAL BIAS- VARIANCE DECOMPOSITION FOR THE 5-LAYER CNN
As discussed before, classical machine learning theory for the underparameterizee regime estab- lishes the bias-variance tradeoff as a result the bias decreasing and the variance increasing as a function of the model size (complexity). In the over-parameterized regime, the bias often contin- ues to decrease, while the variance also decreases. This has been established in a number of recent works Jacot et al. (2020); Yang et al. (2020); d'coolli et al. (2020), and provides bias-variance decomposition the model-wisc double-descent shaped risk curve.
In this paper, demonstrated that epoch-wise double descent occurs for different reason than the model-wise double descent. Namely, epoch-wise double descent can be explained as temporal superposition of multiple bias variinee tradeoff curves rather than with unimodal variance curve.
That also means that the overall bias (i.e., the sum of the individual bias terms) might not decreas- ing and the overall variance might not be uni-modal like in the model-wise case. To demonstrate that
13

---

Published as a conference paper at ICLR 2021
bias variance
2
test
train error
0.4
1.5
1
0.2
0.5
0 m1
0
10
10a
10a
epoch
Figure 7: Bias and variance as function on training epochs for training a 5-layer CNN until convergence. The overall variance is increasing, and the overall bias has double-descent like shape. The training and test error curves show the interpolation of the training set and double descent behavior of the error in this interval.
hea-1ar
stepsize
0.2
25
slepsize
bis Nac
risk
12112 ditiverr
Tisk
0.1
15
10
1100
1.100
10
10
10a
10
10
10
10
10a
10
iterations
f iterations
Figure 8: Left: As we show here, multiple descent curves can arise for regression problem. Here, the risk can be decomposed as sum of three bias-variance tradeoffs. Right: Risk the two-layer neural network trained on the data drawn from a linear model with diagonal covariance matrix with geometrically decaying variances and additive noise yields multi-descent behavior. Both examples: Scaling the stepsizes of the different layers/components eliminates the multi-descen similar to the case of the double descent and improves the optimal early stopping performance for both the linear model and the two-layer neural network predicted by our theory.
it is in fact not, in Figure we plot the numerically computed bias and variance terms (computed as proposed in Yang al. (2020) for the CNN experiment from Section along with the risk, which shows that in fact the overall bias is increasing, while the variance has a doublc-descent like shape.
C MULTI-DESCENT
We note that in principle we can also observe multiple descents as a function of training time. Specif- ically, recall the risk expression for the linear case, equation [ It consists of d many bias-variance tradeoff', so in principle those curves might give rise not only epoch-wise double descent, but to multiple descent. See Figure 8 left panel, in which we show an example of three bias variinae tradeoffs that add up to melti-descent curve.
Likewise multi-descene can occur for neural networks. In Figure right panel, we demonstrate this for the two-layer network introduced Section 33] For multi-descent to oceur neural network, require a very particular setup. Specifically, for the two-layer neural network we consider, we found that the existence of the multiple descents depends heavily on the noise in the data generation process. We found for the two-layer neural network, multi-descent to occur only for particular range of noise levels. more detail, we draw data from linear model specified in exactly the same way for the simulations in the main body; but this time added noise (the noise variance o² of the additive noise z is non-equal to zero). Specifically, the 50-dimensional feature vectors were chosen drawing from Gaussian with diagonal covariance matrix with
Section 2.1
14

---

Published as a conference paper at ICLR 2021
geometrically decaying sigma values starting from 01 4 and with noise variance 11. We generated n = 100 examples, and the network has a width of I: 250.
Intuitively, multiple descents could be observed in other empirical scenarios and for other archi- tectures based on our thcoretical and experimental findings for the linear case and the two-layer neural network. However, did not observe multi-descent in practical setup (such for training CIFAR-10 with a convolutional network), as it requires a very particular setup (i.e., combination of underlying data distribution, network architecture, and training). Image classification datasets considered to be minimally noisy and highly structured and this particular setup does not seem to occur in practice even with the artificially injected label noise, at least we didn't 't observe when training standard networks on CIFAR- 10, and it hasn't t been reported elsewhere.
D PROOF OF THEOREM
The difference of the risk and risk expression can be bounded by
R(O*) R(O0) < [((0') - R(O' + R(O0) R(O')
We bound the two terms on the righ-hand-side separately. We start with bounding the first term by applying the lemma below.
Lemma 1. Define X so that X XE. Suppose that
X
with
min; mo
Then
2max: noo?"
R(00) - -R(O) s (1 min noo max; Ti of min; o
D00 D0 LE(L....kk
2011 (10)
1
max
In order to apply the lemma, we start by verifying its condition. Towards this goal, consider the ma- trix X = X and note that the entries of are iid /o 1/m). A standard concentration inequality from the compressive sensing literature (specifically (Foucart & Rauhut, Holger 2013] Chapter 9)) states that, for any 3 E (0, 1),
P||1-xXX| 2
3
S
no? +4d
With
75d
obtain that, with probability at least e-
x x S 75-.
Next, we bound the term on the RHS of in (T).. with the following lemma.
Lemma 2. Provided that noo s for all i, with probability at least 1 - 2d(e 82 en/8),
d 02
max Eō Σ < 2|
Applying the lemma with g² 10log(d), we obtain that with probability least 1 2d 2de-n/5 n/8 -- we have
max; nf of 75d have that
2 + 4 d 10100000(22))
R( - R(O))
<
(11)
min; n/
We are now ready to bound the second term in 9
Lemma 3. With probability at least 4e
R((O)) - R(@0))
< 33vd.
(12)
72
with R(0)) as defined in II.
Applying the two bounds II and 12 to the RHS of the bound 9
concludes the proof. The remainder of the proof is devoted proving the three lemmas above.
15

---

Published as a conference paper at ICLR 2021
D.1 PROOF OF LEMMA
Recall that the iterates of the original and closely related problem are given by
0 0- = =1 diag m) X () X) 0*) diag 17) x x z.
Φr+1 0" = diag(n) (Ø' 0*) + diag(n) X
Note that X XE, where we defined X which has iid Gaussian entries N 1/n). With this notation, and using that Σ is diagonal and therefore commutes with diagonal matrices, we obtain the following expressions for the residuals of the two iterates:
E0'+1 Σ0- (I diag( (7) X "X) Σ diag(1) Ex)
diag(n)
Σ -00) + diag(n) Σ = x
The difference between the residuals
E0 ~0
(I - diag(n))))))) (aaag()>="'
E0 00-) (1 - diag n) )ー (EO' Σ0-)
= Σ9 - Σθ' diag X(E6' - -E00 diag Σ (EO' - E0")
(I diag n X X) Σ0") + diag 2 X X" E0"),
where the last equality follows by adding and subtracting diag (iiignnn>>>> X Σ0") and rear- ranging the terms. It follows that
D0' +1 Σ0++1 1
| S (1 min m Σσ -E0'
max 100 max DØ E
(13)
Here, we used the bound
| diag(n) E²² + diag()) (I- - I diag(n)) (1)=
(1 min no, + max nofe
(1 min /2
Here, we used that no?? < 1, by assumption, and the last inequality follows by the assumption yields
e <
min: noo
Iterating the bound [3
2 max
min; m2)l/2)
~0'-E0"
max no max Σθ Σ
min, n
which coneludes the proof.
D.2 PROOF OF LEMMA 2
Recall that
(0 - 07) 01 nof)' + +x{x( x(1 (1 - - With noo & 1, by assumption, it follows that
of (0 - 07) < 20 (0:)² + 2x{T2))
(14)
Conditioned on z, the random variable x is zero-mean Gaussian with variance ||z||//n. Thus, | g2 02 Moreover, used previously in (6), with probability least 1 - 2e n/8 || < 202. Combining the two with the union bound, we obtain
P | 2
20² 88 2e /2 + 2e- n/8
P
x 2
n
Using this bound in inequality that
14 we have that, with probability least 2(c-8* 8²/2 + -1/8)
of - - < 20, +
16

---

Published as a conference paper at ICLR 2021
By the union bound over all i we therefore get that
max
Σ0"
|| 2
22
11
+ 100033
n
with probability at least 2d(e /2/2 2d(e-0012 t em188).
D.3 PROOF OF LEMMA
We have
(1 +0,x,2 1- (1 :):0))
R(0") = o² Σ o,
o,
d
= 0² + Σ
(0:11-
+ x z(1 - -11 - no??)²²
2.
The random variable Z, conditioned on z, is squared Gaussian with variance upper bounded by Iælla and has expectation vn
|
E 2 -0
By a standard concentration inequality of sub-exponential random variables (see e.g. WWinwwright 2019 Chapter 2, Equation 2.21)), we get, for 3 E (0, vd) and conditioned on that the event
|
&
Σ Z2 E [(.)
<
Vds
(15)
2e- Eh With the same standard concentration inequality for sub-exponential random variables, we have that the event
occurs with probability at least 1
=11121 ||21 - 0²| 0²| 9
Eg 8=
(16)
82
also occurs with probability at least 1 - 22 3. By the union bound, both events hold simultaneously
8a v. On both events, we have that
with probability at least 1 - 4e
R(O') R(00) =
Σ
(2, B(Zl) +
|1 0²) (1 (1-(1 no?oon
(1=(1-103)
1=1
(Z, B(Zl)
+ d | 1 0²
d
Vd3
+
83
vn
202
VdB +
2
vn
33vd.
concluding the proof of our lemma.
E PROOF OF PROPOSITION
By equation ( the risk expression is a sum of U-shaped curves: R(²²) o2 (t).). We start by considering one such U-shaped curve, and find its minimum function of the number of
17

---

Published as a conference paper at ICLR 2021
iterations, t. Towards this end, set the derivative of one such U-shaped eurve, given by
x² Ōk (t) = (2) - n100) - -moz) + 2( noo
log(1 - n;o 1111-110000 (10)))11117333 7
a²
o²
= 2 log((1 - n:o - no (1-
zero, which gives that the minimum occurs when
02/n
1/1
(17)
of (0)) + oZ
For the iteration which satisfies this equation, get o² / (07)2 min U((t) / + o? (0))²²
thus this minimum is independent of the iteration / and independent of the stepsize, provided their relation is as described in 17 above.
F PROOF AND STATEMENTS FOR NEURAL NETWORKS
In this section, prove the following result, which is slightly more formal version of our main result for neural networks, Theorem
Theorem 3. Draw a dataset D (1x1, (Xn; Un)} consisting of n examples i.i.d. from distribution with ||xell2 1 and lyxl S 1. Let Σ Raxx be the corresponding Gram matrix defined in ( and suppose its smallest singular value obeys > O.
Pick parameter E (0,1) and a failure probability ō (0. 1), and consider the two-layer neural network (w, = /k relulx" W yv, with parameters Wdxk, E R initialized according
1
to with initialization scale parameters v, w obeying vu S E/ 32 and + w S 1. Suppose that the network sufficiently overparameterized, i.e.,
n
k S2 a
(18)
min(v,w)g+
Then, the risk of the network trained with gradient descent with constant stepsize n for iterations obeys, with probability at least 1 8,
a
n
U1s y)² 1
R(fw.v)) S
y) (1 no?)
+ OE//a)
n
o²
Vn
(19)
Theorem 2
direetly follows by choosing the error parameter as O(a).
F.1 PROOF OF THEOREM
In this section, provide a proof of Theorem 2 Our proof relies on the observation that highly overparameterized neural networks behave as associated linear models, as established in a large number of prior works (Arora et al.) 2019 Du et al. 2018 Oymak & Soltanolkotabi 2020 Oymak
ct al. 2019 Heckel Soltanolkotabij 20200).
The proof consists of two parts. First, control the empirical risk as function of the number of gradient descent steps, f. Second, we control the generalization error, i.e., the gap between the population risk and the empirical risk by bounding the Rademacher complexity of the function class consisting of two-layer networks trained with iterations of gradient descent. Recall that our result depends the singular values and vectors of the gram matrix of kernels associated with the two- layer network. The Gram matrix is given as the expectation of the outer product of the Jacobian of the network initialization:
Σ - E J(Wo. vo)JT(Wo,,) vo) = Dofunt
1=1
Here, expectation is with respect the random initialization Wo. Vo-
18

---

Published as a conference paper at ICLR 2021
Bound on the training error: We start with results that controls the training enror and ensures that the coefficients of the neural network move little from its initialization.
Theorem 4. Pick an error parameter & E (0, 1) and any failure probability 8 E (0. 1), and choose v, w so that they satisfy vw S ///32222222 8). Suppose that the network sufficiently overpa- rameterized, i.e,
n (v w)
k 2 Ω
aلل min w){
(20)
Then, with probability least - ô, the mean squared loss after iterations of gradient descent obeys
Σ y/s (x.))
Σ (1 - no?))* (u. + Elyxl12
(21)
i) Moreover, the coefficients overall deviate little from its initialization, i.e.
VIW.- Woll + 1|ve - vollz
1 (1-no?))
E Vn. (22)
(u
Here, F denotes the Frobenius norm. In addition each of the coefficients changes only little, for all iterations
4 -vn) o
[Wer wor S (v
(23)
|etr - vorrd (ogw/Tog(nk//0 (nk
4
VT
2 Vk a²
(24)
Here, Wiy is the r-th row of W. and Vtrr is the r-th entry V
Bound the empirical risk: Because train with respect to the f2-loss but define the risk with respect to the (generic Lipschitz) loss l, the empirical risk and training loss are not the same. Nevertheless, we can upper bound the empirical risk computed over the training set iteration with the training loss at iteration t:
R(fw.v.))
(x:),
IN
Ifw..v - Val
(fw... (xi) - y1)2
uu y) (1- no E,
where (i) follows from ((2, y) = ((2, v) E(y 4) < 1z y because the loss is 1-Lipschitz. Equa- tion (ii) the most interesting one, and follows from Theorem 4 equation (2T). and holds with probability at least 1 - 5. This bound is proven by showing that, provided the network is sufficiently wide, the training loss behaves as gradient descent applied to a linear least-squares problem with dynamics governed by the gram matrix Σ.
Bound the generalization error: Next, bound the generalization error R(f) R(f) by bounding the Rademacher complexity of the functions that gradient descent can reach with gradient descent iterations.
19

---

Published as a conference paper at ICLR 2021
Let FF be class of functions f: R - R. Let 61. ci...., random variables that are chosen uniformly from (-1,11 1}. Given the dataset D, define the empirical Rademacher complexity of the function class F as
.,. Cn be iid Rademacher random variables, i.e.,
RD(FF = E.e
sup SEF
(x)(x))
Here, D = ((x(((()))................)..... vi)...., } is the training set, consisting of n points drawn iid from the example generating distribution. By standard result from statistical learning theory, bound on the Radermacher complexity directly gives a bound on the generalization enror for each predictor in class of predictors.
Theorem 5 ( Mohri et al. 2012 Thm. 3.1) ). Suppose .(.,)) is bounded in [0, 1] and 1-Lipschitz in first argument. With probability at least 8 over the random dataset consisting of n iid examples, we have that
log 12g(2/6)
sup R(f) R(f) R 2RD(F) + 3/ FEF
2n
We consider the class of neural networks with weights close to the random initialization Wo, Vo. defined as:
FQ.M = (fw.v: W WeW. WeW.eer) v).
(25)
with
W- W: W Wolf S w, worrll wM, for r),
V (v: ||v voll2 S Q, Uo,- S vM, for all r).
The Rademacher complexity of this class of functions is controlled with the following result. Lemma 4. Let Wo be drawn from Gaussian distribution with N' w²) entries, and suppose the entries of vo are draw uniformly from {-v. Assume the (x,, ys) are drawn iid from some distribation with ||x; ll2 = and yy S With probubility at least 1 over the random train-
ing set, provided that /log(2n/0) (0122//6//// 22/2k 2k < 1/2, the empirical Rademacher complexity of FQ.M is, simultaneously for all Q, bounded by
- ((++W) W5M3 + 4M /lM (2g(2//))2))
RD(FQ.M) &
(26)
We set M = 1/1) With this choice, the term on the right hand side above is bounded by
1/4).
vw(5M² VK 4M (log(2/6)/2) < O(g/a),
where we used ow < and /log(2/8)/2 < 1, by assumption (8). Note that by (23 and by (4) 82/4
combined with the assumption desired.
(8)
we have that [ww Wo. S wM and [u, - vo.r S sM,, as
Let Q; = i for i = 1,.. Simultaneously for all i, by the lemma above, for this choice of M, the function class FQ.. . has Rademacher complexity bounded by
Qi (v w) + O(E/a).
RD(FQ..M) <
(27)
Vn
We next choose the radius Q as defined in (22) Let i' be the smallest integer such that Q S Qi.,
that Q,- S Q 1. We have that i* s O(v n /a) and
RD(Fo..,M) (Q + 1)
(v w) + O(g/a)
Vn
1
n
Uu 1 1 (1 (1-mo??"
1 +O(E/o).
(28)
71
vn
20

---

Published as a conference paper at ICLR 2021
by the assumption of the theorem on & being sufficiently large, and by + S 1. Next, from union bound over the finite set of integers ,,...,?" 22, we obtain
uu y) (1 no?)) 2
max
sup fEFQ..M
R(f) R(f)
+0(E/a), (29)
i I....
n
as desired.
Final bound on the risk: Combining the bound on the training with the generalization bound yields the upper bound (19) on the risk the network trained for iterations of gradient descent.
The remainder of the proof is devoted to proving Theorem and Lemma
F.2 PRELIMINARIES
We start with introducing some useful notation. First note that the prediction of the neural network for the training data points function of the parameters are
(elu W)v
f(W, v) Vi
relu(X
(30)
Vk
(x W)v
where X is the feature matrix and W Baxk and RR* are the trainable weights of the network. The transposed Jacobian of the function f is given by
Jf (W. v) J (W)
Jd (w)
(31)
where we defined the Jacobians corresponding to the weights of the first layer, W, and the second layer, v, respectively
X diag(relu' (Xw1))
1
T (W, v)
E Bddkxn
J.(W) = relu (XW)" E R
VT.
U X diag(relu' (Xw+))
Here, relu' (x) = 1 (220) the derivative of the relu activation function, which is the step function. Our results depend on the singular values and vectors of the expected Jacobian initialization:
k
E [[Wo. vo) (Wo, vo)) =
E
relu' (Xwa,))reh' (oooolu((oo.. (Xwo,e) " O XXT
t=1
where @ is the Hadamard product, and where used that the entries of vo choosen iid uniformly from v.. Expectation is over the weights Wo at initialization, which are iid (0,,w)) This yields
EE (WW., vo) (WW. vo) 2² Ki (x:, xj) a K2(x;,,));
(32)
where K2 and K₂ two kernels associated with the first and second layers of the network and given by
K7 Ki(Xi,
IP relu' relu' (Xw:)relu' (eee)rrllulXx))) (Xwi)"))
1 (1 - coss (pps) (xi, x,)
2
with Pij 1x
(x.,)) and by
1
K2(x,, x;) = w
[E (elll((X))ll((()))1
1
E (relu(XX)rell(XX))
1
(vi / + (1 cas -t (pu)) ||xilla (x
2
21

---

Published as a conference paper at ICLR 2021
For both of those expressions, we used the calculations from (Daniely et al. 2016 Sec. 4.2) for the final expressions of the kernels. Also note that, by assumption X 1
F.3 PROOF OF THEERRM 4 (BOUND ON THE TRAINING ERROR)
In this subsection, prove Theorem
F.3.1 THE DYNAMICS OF LINEAR AND NONLINEAR LEAST-SQUARES
Theorem relies on approximating the trajectory of gradient descent applied to the training loss with an associated linear model that approximates the non-linear neural network the higbhy-oveeparameelriiee regime. This strategy has been used in a number of recent publica- tions (Arora et al. 2019 Du al., 2018, Oymak Soltanolkotabi 2020, Oymak al. 2019] 2020b): in order to avoid repetition, we rely on statement (Heckel & Soltanolkotabi [220aa] Theorem 4), which bounds the error between the true trajectory of gradient descent and the trajectory of an associated linear problem.
Heckel & Sootanolkotabi
Let f: R- - R" be a non-linear function with parameters E RN, and consider the non-linear
least squares problem
((0) 2 [(( 212
The gradient descent iterations starting from an initial point 0g are given by Dz+1 = 0: - ((((e) where VC(0) = (0) y), where J(0)= E R N is the Jacobian of f at O (i.e., [J(()]s.s) = Ol) least-squares problem is defined as
(33)
The associated linearized
a0;
Lin (0) = [l()()))))))) + J( 0o) y
(34)
Here, J E RRXN refered to as the reference Jacobian, is fixed matrix independent of the parameter that approximates the Jacobian mapping initialization, J(o)). Starting from the same initial point 0g the gradient descent updates of the linearized problem are
θ = 0. --/J" (F(O)) + J(O, - 0n) -y)
(35)
To show that the non-lineen updates 333 are close to the linearized iterates (35). we make the fol- lowing assumptions:
i) We assume that the singular values of the reference Jacobian obey for some o. B
V2a S on I a S 3.
(36a)
Furthermore, we assume that the norm of the Jacobian associated with the nonlinear model f is bounded in radius R around the random initialization
[T())] < B for all 0 E (n))
(36b)
Here, Br((O,) = (0: 0 0ol < R} is the ball with radius R around 0g-
ii) We assume the reference Jacobian and the Jacobian of the nonlinearity initialization J ((o)) are close:
[TT())) - J| S cg.
(36c)
iii) We assume that within radius R around the initialization, the Jacobian varies by no more than
- - ((+)) S S for all 0 (R())).
(36d)
Under these assumptions the difference between the non-linear residual
Fr = f(0.)
and the linear residual
F = ((,) + J(Ø. - 0o) -y close throughout the entire of gradient descent.
22

---

Published as a conference paper at ICLR 2021
Theorem ((Heckel & Soltanolkotabi, 2020a Theorem 4), Closeness of linear and nonlinear least- "squares problems). Assume the Jacobian J(0) E R associated with the function f(0) obeys Assumptions (3aa). (36b). (36c), and (36d) around an initial point 0n R." with respect to ref- erence Jacobian E RaxN and with parameters Ot, B3, co, 6, obeying 23(60 + 6) S a², and R.
Furthermore, assume the radius R. is given by
3a
R = 2 +5 (50+ +c)lool2
(37)
Here, J1 the pseudo-inverse J. We run gradient descent with stepsize v1 S f on the linear and non-linear least squares problem, starting from the same initialization to Then, for all iterations t,
i) the non-linear residual converges geometrically
||rell2 s (1 "1-na²)² ||roll2.
(38)
i) the residuals of the original and the linearized problems are close
20( +c)
Fr F2 F2 e(In 2)a² ||roll2
(39)
iii) the parameters of the original and the linearized problems are close
32
0. 0.-0, 10--0: 5 2.5 (eo + e)llrolle-
(40)
at
iv) and the parameters are not far from the initialization
R
00 0ull
(41)
Theorem Gaooee formalizes that a (small) radius around the initialization, the non-linear problem behaves very similar to its associated linear problem. As consequence, to characterize the dynam- ies of the nonlinear problem, it suffices characterize the dynamics of the linearized problem. This is the subject of our next theorem, which is standard result the gradient iterations of least squares problem, see for example (Heckel & Soltanolkotabi 2020b Thm. 5) for the proof.
Theorem (F.g. Theorem in Heckel & Soltanolkotabi (2020b)) Consider linear least squares problem (34) and let = Ei= o.u.v; be the singular value decomposition of the matrix J. Then the linear residual F, after t iterations of gradient descent with updates (35) is
F1
Σ (1 - no?) u; (u;, ro)
(42)
1=1
Moreover, using a step size satisfying n S oे. the linearized iterates 35 obey
Σ (u. 1 11(1-1173 n)??)) 2
0, -
00
(43)
F.3.2 PROVING THEOREM 4 BY APPLYING THEOREM
We are now ready to prove Theorem We apply Theorem to the predictions of the network given by f(W, v) defined in 30) with parameter 0 (W, v). As reference Jacobian we choose a matrix J E xnnd++k that satisfies JJJ E (W.., vo) (Wo, vo)] (where expectation is over the random initialization (Wo, vo)). and at the same time is very close to the Jacobian at initialization, i.c., to J(Wo, vo). Towards this goal, apply Theorem with the following choices of parameters:
1 3
3n Vk
a Tmin (E)/V2 B= 1=10v + +),
g2 en 2 (w2 + v2)
log(kn/0)
16
(44)
Note that assumption 20 guarantees that co $ a fact used later.
We now verify that the conditions of Theorem are satisfied for this choice of parameters with probability least 1 8. Specifically show that each of the conditions holds with probability least 1 8. By a union bound, the success probability is then at least 1 2(6), and by rescaling by constant, the conditions are satisfied with probability least 1 5.
23

---

Published as a conference paper at ICLR 2021
Bound residual: We need bound on the network outputs at initialization well as the initial residual to verify the conditions of the theorem. We start with the former:
1 [[(Wo volll2
relu W (
Vk
S vww log (2m/5) X
-ww loy 2010
(45)
where the incquality holds with probability at least - 6, by Gaussian concentration (see Lemma 6 in Heckel & Soltanolkotahi (2020b) and recall that Wo has iid ( entries). Moreover, the last equality follows from [xill2
follows that, with probability at least 1 8, the initial residual is bounded by
1 Vk
|roll2
relu WWooo
$ nWV log (2 V + vn
$ 2
(46)
where the first inequality holds by the triangle inequality and using the assumption |ys| S 1, and second inequality by vw (11((22/8))) I 1, again by assumption.
Radius the theorem: In order to verify the condition of the theorem, we need to control the radius in the theorem, which we do next. With our assumptions and the choices of parameters above, the radius in the theorem, defined equation (37. obeys
32 ro 122 (a(eo + felllol
R R= 2
IAE
V2
32
+ 5
(co +e) ||rll22
at
WV
2
5
||ol|2
16a
(in) 4 Vn
(v)
c
min(w, 1) Vk
(47)
X
(M + 3w)
R
Here, (i) follows from the fact that |J definition of en and e), and (iii) from the bound on the residual (46). For (iv) we used assumption (20) in the theorem.
<
22a
|roll (ii from ED + S 2e
c (by
jz
Verifying Assumptions 33aa and (36)) By definition JJ = Σ, thus the lower bound in as-
sumption (36a) holds by the definition of a as o (Σ) 2 22x. Regarding the upper bound of (36a). note that
||
< 12 K 11 2 K 2n + 2
where K, E Ra and K2 E Ruxn are the kernel matrix with entries Ki (x,, x,) and K2(x,, x;). It follows that ||]|| 2( v) vn B, desired. This concludes the verification of (36a).
24

---

Published as a conference paper at ICLR 2021
To verify assumption 36b note that
I1J v)ll - [W]] + [[]]
1
< Vk
[|xx|||vl2 |
1 [ 11v voll + | - Wolls) + (WollF)
$ Vk
S vn10(w + B.
For the last inequality, we used that |olll = vvki and that ||v vollz + W Wolle S R R vk (in v), by the bound on the radius in (47). and finally that | S w with prob- ability at least used that x. Wo is Gaussian vector with iid A/ w²) entries. It follows that assumption 33bb holds with probability at least - 6, as desired.
provided that k log(n/0), which holds by assumption. For this inequality
Verifying Assumption 36ch:
We start with stating concentration lemma from Heckel &
Soltanolkotabi (20205).
Lemma 3)), Consider the par- tial Jacobian Jn (W), and let W =XXX be generated random with i.i.d. NO, w²) entries, and suppose the ve are drawn from distribution with [ve] S v. Then, with probability at least 1 - ó,
Lemma (Concentration lemma (Heckel & Soltanolkotabi 2020b
(W, (W, - [[I(W v)Jf (W, v)]l [[I((W v)J
XII
Vlg (2n/6).
VK
Lemma 6. Let J2(W) J With probubility at least 8,
relu XW), with W generated random with i.d. NN w²) entries.
W²
|[ (W) - [[2((W) (W)]ll 3
|X|| log(kn/0).
(48)
Vk.
Combining the statements of the lemmas, it follows that, with probability least 25,
1
- (W, (W).)) s (w² + +22)3
| log(kn/0)
Vi
1
(w² 2²) Vi
(og(kn/0))
(49)
To show that 49 implies the condition in (36c). use the following lemma.
Lemma Oyyak et al. 2019 Lem. 6.4)). Let Jo E BaxN N 2 and let Σ be n x n psd matrix obeying
JoJ Σ
S E², for a scalar 2 Then there exists matrix J R obeying
Σ = JJ such that
J Joll < 2E.
From Lemma combined with equation
49 there exists a matrix e B that obeys
|J - J(Wo. vo)ll S co. co = = (uP + u2) 3n
log(kn/5).
Vk
This part of the proof also specifies our choice of the matrix as a matrix that is eo close to the Jacobian at initialization, J I(Wu), and that exists by Lemma
We control the perturbation around the random initialization. Lemma 8. Let Wo have iid ((O0w²) entries and let vo have (arbitrary) entries in {-v, +v} entries. Then for W and v obeying, for some Rt jVk,
Verifying Assumption 36d
JW 1--WWy Woll wR, ||v vallz & vR,
25

---

Published as a conference paper at ICLR 2021
the Jacobian in 31 obeys
- JWo, vo)l S
| Vk (w
1
auR+uR+ vlt vV2(218)1/3))
with probability at least 1 ne /12//2///3
Recall the definition π V (x+33) from 47
From Rt s (kR))//8 for Nt S vk, the
bound provided by lemma
g guarantees that
- - vo)ll
S X
+
3v
(kR)
VT.
1 a3
=c=
16
g2
where the second inequality follows by choosing R V/ [|x][[>+3)] bility at least
This holds with proba-
ne R = =1 ne
(1) 17 k
2 1--6, 8,
where in (i) we used 20 Therefore, Assumption (36d) holds with high probability by our choice of
coa 32
Concluding the proof of Theorem 4 By the previous paragraphs, the assumptions of Theorem O88). Therefore we can bound bound the training error and
are satisfied with probability at least 1 the deviation of the coefficients from the initialization as follows.
Training error: We bound the training error in 20 The training error at iteration t is bounded by
|[[WW: e: vo) yll2 I ||eell2 + ||+ rell2
(1 n0? ro) 2 2,3 + c)
e(In 2)a² ||roll2
28(Eo + E)
no??"² (u, + [|[ wo)ll
e(In 2) |1ool
(ii)
(1 no?) (u, y)² + El
where inequality (i) follows from bounding the linear residual || with theorem 7 as well as bounding the distance between the linear residual and the non-linear with (39) Inequal- ity (ii) follows from ro = f(Wo, vo) y, and finally (iii) follows from [[f(Wo, vo) <
pw (10) I & flllll, by (45). and 2 (Eo + _e $ S.
Distance from initialization:
We next bound the distance from the initialization, i.e., we estab- in theorem 7 with equation (39) in theorem
lish 22
Combining equation
6 we obtain
1 (1 1177) Iu; ro)
82 (co + c)llrollz
//W.
Woll + ||v, vollz
VI
+ 2.5
a
SV
n
1 1- ---1o7)0
2
=l vo)ll2 + 2.5 32
Iu y)
q e)llool2z
a
IAB
1- (1 (1-no?)e
!
2
5 Vī.
(u:y)
σ
a
26

---

Published as a conference paper at ICLR 2021
where (i) follows from Fo f(Wo. vo) y and (ii) follows from 2.5 _ 5
at (co+e)||rolz S 150 |xoll v 16a (Ilr(Wo, vo)ll2 + 11y))1)),, where we used eo + S 2 - pr by definition of 6o. combined with [|f(Wo, o, vo)ll2 - E/4/n.
Bound on change of coefficients: Finally, we establish the bounds on the change of the individual coefficients (23) and (24). We start with the weights in the first layer, w.- The gradient with respect to w, is given by V w..,(W, v) = [J (W. v)],r, where [J, (W. v)], is the submatrix of the Jacobian multiplying with the weight w,, and is the residual. Therefore, obtain
|Wer - wo.rl12 =
W
Σ W w1rr Worr)
12
n|[JT (W r. v+) v-)]
-=
4
v/
Vn)
|r>112
a
Vk
4
(v
(1
||rool2
Vk
m
Vn
S
(v+
vn)
v a 11ollz
Here, (i) follows from
|| v+)]+|1 =
8,
diag(relu' (Xw,))
VK
< Vi
vn
< (v +
where the last inequality follows from |0+, - up S ||= - Moreover, for (ii) used that, by (38), the non-linear residuals converge geometrically, and (iii) follows from the formula for a geometric series. This conclude the proof of the bound (23).
Vorrl12 S R R VV by 47
Analogously, we obtain
|0, up $
Σ
MllTT (W>)l
T=0
< (0wwlog((nk/)) - 4 v vn
v a² |roll
where we used that
1
(ew,(X
relu Xw,)
< (IXwo,rllz + IX(wo.r - w,)112)
Vi
VI.
2
V (O(wvnlog(nk//)) + Vnillwor - -wr--- wrlll)
1
(OwwTogg(kk/))
a
Here, the last inequality follows by using that the entries of X Xwo,r not independent but.V((,, w distributed, and by taking an union bound over all entries of that vector and over all Xwo,r- This concludes the proof of the bound 24
27

---

Published as a conference paper at ICLR 2021
F.3.3 PROOF OF LEMMA g
First note that
IIJ(W.v) J(W viIl $ [[1 v) JWW v\Il + W v) JWW vlIl
J1 (W, v) (W,, v\Il + (W[ v' JI(W", viIl (W,,), -2WW", v)I..
(50)
In the reminder of the proof we bound the three terms above. We start by bounding the third term in 500 as:
1
IJ2(W. - JWW (W,Il
- (rclu(X))
relu (
Vk
1
XWW XW'I
Vk
<
XXII W
Vk
We proceed with bounding the first term in
500 as:
[W,, JI (W, v')l
J. (J (W. J. (W. (W.+)) -V (W.
relu' (X) (W)gggg(()) - ,.),....,
..... (we - (ra)) (XW) reel''/(W") o oxx"
I ||| max ||elll (x3 W)diag( v2)l
x ||v v' 11221
Next we establish below that with probability at least 1 2ko2/2 the second term in in (50 is bounded as
[WW v) J(W vill
Vi ll
V
(51)
provided that
- w/ S /9 2k
= wl,
where the last inequality follows from setting q R2 2/3 (note that the assumption π
ensures S k). Putting those three bounds together in (50 yields
[[J(W, v) - J (W', v'll $ X
X
(IW
+ ||v - vll2 + II (2(22))((2))))
V
(52)
which established the claim.
It remains prove (1)). Towards this goal, first note that
(W, v) Jn (W', v'Ill & [[ v) J. (W, v'Il + ||T (W, v/) - (W', v')ll
(53)
We proceed with bounding the second term in the RHS of 53 as:
IJ v') (WW, v'Il2 < +
X 2 max l (x] W) d' w (x]
(54)
Because rehu' is the step function, we have to bound the number of sign flips between the matrices XW and XW For this use the lemma below:
Lemma 9. Let (wbngg) be the q-th smallest entry of v in absolute value. Suppose that, for all i, and q <
x (x(9)
|W Wll < /4
Then
max ||o (x o'((x ('x w S V2g.
28

---

constant for most r, because |w", concentration of a Gaussian. For those coefficient vectors r for which relu' (w, x;) is constant, we bound the difference of Published as a conference paper at ICLR 2021
For the entries W being iid ((0, we note that, with probability at least - ne Rn0//2 the q-th smallest entry of x W F obeys
(x())
q
for all 1,..., n.
(55)
x
2k
We are now ready to conclude the proof of the lemma. By equation (5).
|Ji(W, v/) - vw)ll <
|I
X||
max 10 W) o'x(xx
V
X
22
V
provided that
w
w - / 9
2
with probability at least -ee -k0 Rkg
F.4 PROOF OF LEMMA 4 (BOUND ON THE RADEMACHER COMPLEXITY)
Our proof follows that of related result, specifically (Arora et al. 2019 Lem. 6.4) which pertains to two-layer ReLU network where only the first layer is trained and the second layers' coefficients are fixed. Our goal to bound the empirical Rademacher complexity
RD(FQ.
1 E
sup WEW
C4
rerclu x,)
where expectation is over the iid Rademacher random variables 6, and where (xI,..., .x,) are the training examples.
The derivation of the bound on the Rademacher complexity is based on the intuition that if the parameter M of the constraint l|w, Wo.rllz < wM is sufficiently small, then relu' (w,"" x:) is bounded away from wM with high probability, by anti-
have relu w.xx) x,) relu' (w",, x.). Wxx, x, For the other coefficients, those two values as
relu w.Tx.) xx) - relu' (w., /,,,',/'xx
=relu' (w, (.w"';))e " relu' (wo,, w x;
=relu' (w," x, wx x; relu' aall'(w?" ) wh,
+ relu' (wi, x; wo, - relu' (wi,, W.F w.
- relu( xx) relu(we, relu (wo, xi) (Wo,r Wr.
<2|lw, Wo,1l2||x:112
22wM,
where the last inequality holds for W E W. It follows that
RD((Q.M) <
E
sup WEW
r,relu' r,rel'(ww (w.oX,)
2M
U+ (w
nvk
k
t J.. v)w
2wM ΣΣ
E
sup WWW
+ nvk #=1==
1
(relu (. (.) (orll (w?x;)
(56)
29

---

Published as a conference paper at ICLR 2021
where J1 is the Jacobian defined in (31). and where version of the matrix W with slight abuse of notation. With this notation, we can bound the first
vect( (W) E R for the vectorized
term in 56 by
1 E
E
sup WWW.VE
e J1( vjw
sup LEW.WEY
e (J J1 I[ vo))oo
n
n
(Ji(Wo. - J.(Wo. 3 v)wo (Wo. vo)wo)
E
sup WEW
T
E
sup VEW
(Ji(Wo, v)(w wo) +2 vol)
(Jr(W vol(w Wo + +J((Wo vol(w J2(W) vol)
sup WEW
n
E I||e" J.WWo vo) - [||=" ]2(o) Q+ VkowM²
IN
( 1.
1
Q(v WVVn+ + ViewM2
(57)
Here, equality (i) follows because cJ1 Wo. Vo)wo has zero mean, inequality (ii) follows from the Cauchy-Sehwar inequality as well as from
[Wo. v -vo) wo)ll -
X
Ur wor,,,, worlllz S V Vn,
and inequality (iii) follows from [[ S
|| by Jensen's inequality, and from the bounds J (Wo, vo)ll and ||7a (W)llp w. which holds with probability least
A |
8 provided that /log(2n/8)/25 < 1/2, which turn holds by assumption.
We next upper bound the second term in (56. Following the argument in (Arora et al. 2019 Proof
of Lemma 5.4), we get
log(2/5)
Uy xt) (wTx:) S 2vkn M +
(58)
2k
with probability at least - Here, we used that u,- S |vo.el l0- Morr - 2v. Putting the bounds
on the first and second term in (56) (given by inequality (57) and inequality (58) together, we get
that, with probability at least 1 - o. the Rademacher complexity is upper bounded by
Q RD(F) S Vn
( + + ww (5M 4M /log(288)
which concludes our proof.
30


Reviews:
[{"review_id": "lIMYioC-v5V", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies the phenomenon of double descent. The claim is that double descent is caused by the superposition of multiple bias-variance trade-offs arising from the fact that different parts of the network are trained at different speeds. To corroborate this claim, the following main results are presented:\n\n(1) Analytical results for linear regression in the under-parameterized regime (input dimension $d$ much smaller than the number of training samples $n$). In particular, it is shown that the risk of gradient descent is close to the sum of $d$ U-shaped curves (this is dubbed as the \"risk of early stopped least squares\"). The bound depends on the covariance structure of the model and, in case such a structure is known, one can optimize the learning rates associated to the various components so as to minimize the risk. \n\n(2) Analytical results for two-layer networks in the \"lazy regime\". The author(s) provide an upper bound on the risk which has again the form of the sum of U-shaped curves. The bound depends on the singular values/vectors of the Gram matrix associated to the network. By estimating (or knowing in advance) the spectrum of such a Gram matrix, one can eliminate the double descent phenomenon and optimize the risk.\n\n(3) Empirical results showing how to mitigate the phenomenon of double descent by choosing different step sizes for different layers (or different components). The author(s) provide results both for the toy models analyzed theoretically (see Figure 1 and 3) and for neural networks used in practice (5 layer CNN and ResNet-18 trained on CIFAR, see Figure 4 in the main paper and Figure 6 in the Appendix).\n\nThe analysis for linear regression is quite simple. The analysis for the two-layer network is more involved and it heavily relies on previous literature, in particular recent work by Heckel & Soltanolkotabi.\n\nOverall, the paper is well written, the results appear correct (although I did not do a thorough check on the appendix), and the perspective proposed by the paper is fresh and interesting. However, I am not fully persuaded of the impact that the results of the submission will have on the community. In fact, the paper presents the following major weaknesses:\n\n(a) Theorem 2 provides an upper bound on the risk of two-layer networks. However, there is no indication of how good this upper bound actually is. Is it tight in any way? Does it even go to 0 as n and t grow? It seems that the bound on the risk comes from a bound on the training error, and the training error is known to vanish (as $n$ and $t$ grow) in the over-parameterized regime considered here. However, after staring at the formula for a while, it is not obvious to me that the RHS of (5) can be made arbitrarily small (by taking sufficiently large $t, n$). \n\n(b) The risk of early stopped least squares seems to vanish by taking sufficiently large $n, t$. However, the dependence on t of the RHS of (2) is not clear. There is no explicit t in the formula. Is the dependence hidden in the numerical constant c?\n\n(c) The numerical results in Section 4 are not convincing. The double descent phenomenon appears mitigated, but the test error improves only slightly for the 5-layer CNN (Figure 4) and it is even worse for ResNet-18 (Figure 6 in the appendix). I agree with the author(s) that choosing different learning rates can mitigate double descent. However, it is not clear at all whether this would actually improve performance at the scale of a practical network.  \n\nMinor points:\n\n(d) Is it possible to provide bounds on linear regression in the over-parameterized regime? Do you expect to obtain results somewhat similar to (Hastie et al., 2019)? \n\n(e) Can you make the probability of Theorem 1 arbitrarily close to 1? Now, it is at best 1-2e^{-32}.  \n\n(f) Could you add some technical details explaining how your approach differs from the vast literature on the analysis of two-layer networks in the lazy regime? This would help assess the technical novelty of the paper. \n\n\n--------------------------------------------\n\nUPDATE AFTER AUTHORS RESPONSE: The authors partially addressed my concerns and I (slightly) increased my score. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "eudYEAreoJC", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper provides an interesting analysis and direction to improve generalization capability by eliminating double decent during training by setting learning rates differently for each feature and using early stopping. In terms of technical contributions, the authors prove double decent phenomenon during training due to bias-variance tradeoff in toy problems, and provide experimental results with synthetic data using CIFAR-10 dataset with random label noise.\n\nIn theorem 1, a type of quantifier over t is ambiguous. As I did not see, for example, a (union) bound over t in the main text, I would suspect that the authors mean that t is fixed for this probabilistic statement. But then the relationship only holds for a single t with high probability, which does not support the claim of the paper, which is about a phenomenon for all t up to an early stopping time. So, I think it should be taking some probabilistic bound over time. In either case, the authors can specify it to be clearer. \n\nI like the idea and potential of this direction. Indeed, reading this paper was like attending one of the best talks in my experience. My major concern is that supporting evidence is very week for a technical paper (although it is great for a talk). The main theorems are proven only in very simple unrealistic settings. Theorem for neural network training is really theorem for shallow linear models with the fixed kernel, NTK. This is not for neural network training. The assumption that k >= n^10 in terms of the order is unrealistic, and known to make the neural network to be basically a shallow linear model. As a sufficiently wide neural network is a shallow linear model with a fixed NTK, theory is trivial and simpler in a sense than that of deep linear networks: for example, deep linear network change NTK during training unlike the wide network and its effect was recently studied in https://arxiv.org/abs/2003.02218 (deep linear network with one hidden layer) to understand neural network beyond NTK regime. \n\nGiven the weakness in theory, it will be nice to have more comprehensive experimental results. I think if there are more extensive experimental results, this paper is already strong without improving theory. It is understandable that proving theory under practical setting is challenging for neural networks. However, in the current form of the paper, experimental results are not conclusive. It only uses a single synthetic data (CIFAR-10 with random label noise, instead of original CIFAR-10), does not report error bars and statistical information of the experiments, and does not report sensitivity of hyper-parameters or the way the authors picked hyper-parameters in details. In such an experiment, one can easily construct an artificial case to support the claims. \n\nIt is also highly desirable to conduct experiments with a real dataset without adding random label noise. It can be an artifact of Gaussian (or simple) random label noise. In real worlds, the label noise tends to be much more complicated and the purpose of the experiments should confirm the theory in the simple setting to be valid in some extend in such a more realistic case, instead of keeping the noise to be an artificial one. \n\nIn Figure 4, test errors (and training errors) are much better for the case of ii at the beginning of training, epoch = 1. Can you report the values at epoch = 0 to make sure that both are the same initially? In either case, most improvements seem to be coming from the first epoch. At the first epoch, training error is also better for the case ii, instead of only testing error. Therefore, this observation would change as we change step size and other hyper-parameters (for example, batch size and momentum). \n\n\n- Typo: “as formalized be the theorem bellow” -> “as formalized in the theorem bellow” in page 4.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "BlR5bryCebj", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "UPDATE: The authors have addressed my concerns. Taking also into account the responses to the other reviews, my positive view of the paper has been confirmed and I have therefore increased my score.\n\n\n\nSummary:\n\nThe paper deals with the phenomenon of double descent as a function of training time and offers an alternative explanation as a superposition of bias-variance tradeoffs with minima at different epochs. The analysis is first done theoretically for an early stopped linear least squares problem with different scalings of the features as well as a two-layer network. For both cases it is shown theoretically that the risk function is approximated by a function consisting of overlapping bias-variance tradeoffs. By controlling the stepsizes and initializations it is then possible to mitigate double descent. Motivated by this theory, the authors then consider two recent architectures empirically, a 5-layer CNN and a ResNet model, and show experimentally how double descent can be avoided by adapting the stepsizes corresponding to the last layers. \n\n\nStrengths:\n\n- The paper provides a novel theoretical explanation of the epoch-wise double descent phenomenon, which recently has gained some interest in the community. Understanding the epoch-wise descent better is important to better understand early stopping in neural networks.\n- The theory also suggests a simple and effective mitigation strategy by adaptation of the different stepsizes corresponding to the different U-shaped curves appearing in the approximate risk formulation. This strategy is shown to work not only for the theoretically analyzed models, but also empirically on two common standard architectures, namely 5-layer CNN and ResNet. Thus it may have significant impact for the practical performance of neural networks and may be adopted by the community.\n- The paper is well-written, well-motivated, and relatively easy to follow, taking into account the technical nature of the problem.\n\n\nQuestions:\n\n- By choosing the stepsizes according to Prop. 1, we achieve the lowest value of the approximate risk expression (1). However, since the quality of the approximation in (2) also depends on the choices of the stepsizes, how can we make the conclusion that this also corresponds to the lowest risk?\n- In the discussion after Theorem 2, I do not quite understand what is meant by the statement \"the theorem pertains to the kernel regime where the network behaves similar to an associated linear model\". Maybe you could elaborate a bit on this statement. \n\n\nConclusion:\n\nOverall, the paper constitutes a solid contribution to the understanding of epoch-wise double descent as well as a practical way to mitigate and improve the early stopping performance. Moreover, the paper is well-written and technically sound. I vote for acceptance.\n\n\nMinor comments:\n\n- Page 2, before Section 1.1: \"overparamterized\" -> \"overparameterized\"\n- Page 4, before Theorem 1: \"as formalized be the theorem\" -> \"as formalized in/by the theorem\"\n- page 4, after (2): \"provided the model is sufficiently underparameterized, (i.e. $\\frac{d}{n}$ is large)\" -> should be \"$\\frac{d}{n}$ is small\"\n- Page 5, in \"Network model\": double \"and\"", "extra_scores": {}, "extra_text": {}}, {"review_id": "2CEEKP67S97", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "UPDATE: The authors have addressed my concerns and I have therefore increased my score.\n\nThis work proposes an explanation for the double-descent phenomenon observed by Nakkiran et al. as a function of training time, in models with significant label corruption. Classical theory suggests that the test loss should follow a U-shaped curve, where the model initially learns but then overfits. The proposed explanation is that the observed double-descent curve is a superposition of two such U-shaped curves, each originating from a different underlying \"scale\". This is demonstrated in the context of linear models trained with MSE loss and noisy labels: Each eigenmode of the kernel independently leads to a U-shaped curve in the test loss, and the time scale for each curve is a function of the corresponding eigenvalue. A similar effect is shown for wide 2-layer networks, using wide network theory to relate this network to a linear model. In this case the two scales in the kernel originate from an imbalance between the two layers. The double descent effect can be eliminated by adjusting the initialization scales (or learning rates) of the two layers.\n\nAs a test of this proposal, it is shown empirically that double descent can similarly be eliminated in ResNet-18 and another model by adjusting the learning rates of different layers. The paper presents this as a way to mitigate double descent, although it is not clear that this is beneficial. First, the double descent effect happens relatively quickly (it is over in a fraction of the time it takes to train the network). Second, in the example of ResNet-18, the network that exhibits double-descent ends up performing better than the network where double-descent is mitigated. I do think that the explanation suggested for the origin of double descent is plausible and valuable. In particular, it neatly explains why label noise enhances the effect.\n\nFollowing the proposed explanation, it is not clear to me why models exhibit double-descent and not multi-descent behavior. Given the linear model results, it is possible to engineer linear setups with any number of separate U-shaped curves. Why are there only two typical scales rather than multiple such scales in typical deep learning setups? The paper suggests that the main imbalance is between the last layer and all the previous layers (why?), but based on the ResNet-18 results it seems the imbalance can happen in other parts of the network as well.\n\nThings that would lead me to increase my rating:\n\n1. A clear explanation of why we observe double descent rather than \"multi descent\" in typical deep learning setups.\n\n2. Clarifying the connection (even if only empirically) between mitigating double descent and final model performance. The two convolution networks shown in the paper point to different conclusion. One way to strengthen the conclusion would be to scan over the per-layer learning rates, and determine whether the optimal learning rates in terms of performance do or do not exhibit double descent.\n\nTypos and nits:\n\n- \"such as a neural networks\"\n- \"explains why neural network often\"\n- Below Theorem 2 it says \"for a very related Gram matrix\". What does \"very related\" mean in this context?", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper provides a novel theoretical analysis of epoch-wise double descent for a linear model and a two-layer non-linear model in the constant-NTK regime. Some reviewers noted that these models may be too simple to offer a full explanation for the phenomenon in state-of-the-art practical models, for which the NTK is known to change significantly. While this may be true, I believe that the detailed understanding derived in these simple settings provides an important first step and will surely be of interest to the community. I therefore recommend acceptance.
Decision: Accept (Poster)