An Exponential Learning Rate Schedule for Deep Learning
Authors: Zhiyuan Li
Sanjeev Arora
Venue:  (2020)
Keywords: batch normalization
weight decay
learning rate
deep learning theory

Abstract: Intriguing empirical evidence exists that deep learning can work well with exotic schedules for varying the learning rate. This paper suggests that the phenomenon may be due to Batch Normalization or BN(Ioffe & Szegedy, 2015), which is ubiq- uitous and provides benefits in optimization and generalization across all standard architectures. The following new results are shown about BN with weight decay and momentum (in other words, the typical use case which was not considered in earlier theoretical analyses of stand-alone BN (Ioffe & Szegedy, 2015; Santurkar et al., 2018; Arora et al., 2018)
• Training can be done using SGD with momentum and an exponentially in- creasing learning rate schedule, i.e., learning rate increases by some (1 + α) factor in every epoch for some α > 0. (Precise statement in the paper.) To the best of our knowledge this is the first time such a rate schedule has been successfully used, let alone for highly successful architectures. As ex- pected, such training rapidly blows up network weights, but the net stays well-behaved due to normalization.
• Mathematical explanation of the success of the above rate schedule: a rigor- ous proof that it is equivalent to the standard setting of BN + SGD + Standard Rate Tuning + Weight Decay + Momentum. This equivalence holds for other normalization layers as well, Group Normalization(Wu & He, 2018), Layer Normalization(Ba et al., 2016), Instance Norm(Ulyanov et al., 2016), etc.
• A worked-out toy example illustrating the above linkage of hyper- parameters. Using either weight decay or BN alone reaches global minimum, but convergence fails when both are used.

Published as a conference paper at ICLR 2020
AN EXPONENTIAL LEARNING RATE SCHEDULE FOR DEEP LEARNING
Zhiyuan Li
Sanjeev Arora Princeton University and Institute for Advanced Study aroraêcs . princetor edu
Princeton University
zh i yuanl i0cs www.:prinnccctc edu
ABSTRACT
Intriguing empirical evidence exists that deep learning can work well with exotic schedules for varying the learning rate. This paper suggests that the phenomenon may be due to Batch Normalization or BN(Loffe & Szegedy, 2015), which is ubiq- uitous and provides benefits in optimization and generalization across all standard architectures. The following new results are shown about BN with weight decay and momentum (in other words, the typical use which not considered in earlier theoretical analyses of stand-alone BN (loffe & Szegedy, 2015; Santurkar et al., 2018; Arora al., 2018)
Training can be done using SGD with momentum and an exponentially in- creasing learning rate schedule, i.e., learning rate increases by some (1 + a) factor in every epoch for some > (Precise statement in the paper.) To the best of our knowledge this is the first time such a rate schedule has been successfully used, let alone for highly successful architectures. As expected, such training rapidly blows up network weights, but the network stays well- behaved due to normalization.
Mathematical explanation of the success of the above rate schedule: a rigor- ous proof that it equivalent the standard setting of BN + SGD + Standard Rate Tuning + Weight Decay Momentum. This equivalence holds for other normalization layers as well, Group Normalization Wu He, 2018), Layer Normalization(Ba et al., 2016), Instance Norm(Ulyanow et al., 2016). etc.
A worked-out toy example illustrating the above linkage of hyper- parameters. Using either weight decay or BN alone reaches global minimum, convergence fails when both are used.
INTRODUCTION
Batch Normalization (BN) offers significant benefits in optimization and generalization across archi- tectures, and has become ubiquitous. Usually best performance attained by adding weight decay and momentum in addition to BN.
Usually weight decay thought to improve generalization by controlling the norm of the parameters. However, it is fallacious to try to separately think of optimization and generalization because we are dealing with a nonconvex objective with multiple optima. Even slight changes to the training surely lead to different trajectory in the loss landscape, potentially ending up at a different solution! One needs trajectory analysis to have hope of reasoning about the effects of such changes.
In the presence of BN and other normalization schemes, including GroupNorm, LayerNorm, and InstanceNorm, the optimization objective is scale invariant the parameters, which means rescaling parameters would not change the prediction, except the parameters that compute the output which do not have BN. However. Hoffer et al. (2018b) shows that fixing the output layer randomly doesn't t harm the performance of the network. So the trainable parameters satisfy scale invariance. more in Appendix E) The current paper introduces new modes of analysis for such settings. This rigorous analysis yields the surprising conclusion that the original learning rate (LR) schedule and weight decay (WD) can be folded into a new exponential schedule for learning rate: in each iteration multiplying it by (1 + a) for some a > 0 that depends upon the momentum and weight decay rate.

---

Published as a conference paper at ICLR 2020
Theorem 1.1 (Main, Informal). SGD scale-invariant objective with initial learning rate n, weight decay factor X, and momentum factor y is equivalent to SGD with momentum factor ? where at iteration t, the learning rate tt in the new exponential learning rate schedule is defined as iie a- 22 without weight decay() ( 0) where a is non-zero root of equation
x² - (1+7 - Xn)
= 0, + -
(1)
Specifically, when momentum 7 = 0, the above schedule can be simplified as ît = (1 Xn) -2
The above theorem requires that the product of learning rate and weight decay factor, Ary, is small than (1 - v7)², which is almost always satisfied in practice. The rigorous and most general version of above theorem is Theorem 2.12, which deals with multi-phase LR schedule, momentum and weight decay.
There are other recently discovered exotic LR schedules, e.g. Triangular LR schedule(Smith, 2017) and Cosine LR schedule(Loshchilov & Hutter, 2016), and our exponential LR schedule is an extreme example of LR schedules that become possible in presence of BN. Such an exponential increase in learning rate seems absurd at first sight and to the best of our knowledge, no deep learning success has been reported using such an idea before. It does highlight the above-mentioned viewpoint that in deep learning, optimization and regularization are not easily separated. Of course, the exponent trumps the effect of initial Ir very fast (See Figure 4), which explains why training with BN and WD is not sensitive to the scale of initialization, since with BN, tuning the scale of initialization is equivalent to tuning the initial LR 7j while fixing the product of LR and WD, y/À (See Lemma 2.7).
Note that customary in BN to switch to a lower LR upon reaching a plateau in the validation loss. According to the analysis in the above theorem, this corresponds to exponential growth with a smaller exponent, except for a transient effect when a correction term is needed for the two processes to be equivalent (see discussion around Theorem 2.1
Thus the final training algorithm is roughly as follows: Start from a convenient LR like 0.1, and grow it at an exponential rate with suitable exponent. When validation loss plateaus, switch to an exponential growth of LR with a lower exponent. Repeat the procedure until the training loss saturates.
In Section 3, we demonstrate on a toy example how weight decay and normalization are inseparably involved in the optimization process. With either weight decay normalization alone, SGD will achieve zero training error. But with both turned on, SGD fails to converge to global minimum.
In Section 4, we experimentally verify our theoretical findings on CNNs and ResNets. We also construct better exponential LR schedules by incorporating the Cosine LR schedule on CIFARIO, which opens the possibility of even more general theory of rate schedule tuning towards better performance.
1.1 RELATED WORK
There have been other theoretical analyses of training models with scale-invariance, (Cho Lee, 2017) proposed to Riemanian gradient descent Grassmann manifold G(1, n) since the weight matrix is scaling invariant to the loss function. observed that the effective stepsize is proportional to [wo p (Arora al.. 2019) show the gradient is always perpendicular to the current parameter vector which has the effect that norm of each scale invariant parameter group increases monotonically, which has an auto-tuning effect. (Wu et al., 2018) proposes a new adaptive learning rate schedule motivated by ccale-invariance property of Weight Normalization.
Previous work for understanding Batch Normalization. (Santurkar et al., 2018) suggested that the success of BNhas does not derive from reduction in Internal Covariate Shift, but by making landscape smoother. (Kohler et al., 2018) essentially shows linear model with BN could achieve exponential convergence rate assuming gaussian inputs, but their analysis is for a variant of GD with an inner optimization loop rather than GD itself. (Bjorck et al., 2018) observe that the higher learning rates enabled by BN empirically improves generalization. (Arora et al., 2019) prove that with certain mild assumption, GS)GD with BN finds approximate first order stationary point with any fixed learning rate. None of the above analyses incorporated weight decay, but (Zhang et al., 2019; Hoffer et al., 201 Sa; van Laarhoven, 2017) argued qualitatively that weight decay makes parameters
2

---

Published as a conference paper at ICLR 2020
have smaller norms, and thus the effective learning rate, ||>, is larger. They described experiments showing this effect but didn't have a closed form theoretical analysis like ours. None of the above analyses deals with momentum rigorously.
1.2 PRELIMINARIES AND NOTATIONS
For batch B = (.;;) network parameter 0, we denote the network by fo and the loss function at iteration by L.(fo) = L(fe. Br). When there's no ambiguity, we also use ()) for convenience.
We say a loss function L(0) is scale invariant to its parameter O is for any E R L(0) [(cl). In practice, the source of scale invariance is usually different types of normalization layers, including Batch Normalization (loffe & Szegedy, 2015). Group Normalization (Wu & He, 2018), Layer Normalization (Ba et al., 2016), Instance Norm (Ulyanov et al., 2016), etc.
Implementations of SGD with Momentum/Nesterrv comes with subtle variations in literature. We adopt the variant from Sutskever et al. (2013), also the default in PyTorch (Paszke et al., 2017). 7). L2 regularization (a.k.a. Weight Decay) is another common trick used in deep learning. Combining them together, we get the one of the mostly used optimization algorithms below.
Definition 1.2. [SGD with Momentum and Weight Decay] At iteration t, with randomly sampled batch B,, update the parameters O, and momentum it as following:
0, -0:1 72-110
0: - + V Lc(0 + A--1 0: 11-
where 77t the learning rate at epoch t, y is the momentum coefficient, and is the factor of weight decay. Usually, is initialized to be 0.
For ease of analysis, we will use the following equivalent of Definition 1.2.
0, 0:- 0,-1- Ve (L(0)-1)+ + dr-1 1 110-111
(4)
T where 7/-1 and 0-1 must be chosen in a way such that 00 00-0-1 satisfied, c.g. when vo = 0,
1
2
0 = 0g and 1 could be arbitrary.
key source of intuition is the following simple lemma about scale-invariant networks Arora al. (2019). The first property ensures GD (with momentum) always increases the norm of the Weight. Lemma C.I in Appendix C) and the second property says that the gradients are smaller for parameteres with larger norm, thus stabilizing the trajectory from diverging to infinity.
Lemma 1.3 (Scale Invariance). for any c R+, L()) L(cO), then (1). (VeL, 0) = 0; (2). VoL 0=00 = cVe 0 for any c >> 0
2 DERIVING EXPONENTIAL LEARNING RATE SCHEDULE
As a warm-up in Section 2.1 we show that if momentum is turned off then Fixed I.R + Fixed WD can be translated an equivalent Exponential LR. Section 2.2 we give more general analysis on the equivalence between Fixed LR + Fixed WD + Fixed Momentum Factor and Exponential LR + Fixed Momentum Factor. While interesting, this still does completely apply to real-life deep learning where reaching full accuracy usually requires multiple phases in training where LR is fixed within phase and reduced by some factor from one phase to the next. Section 2.3 shows how to interpret such multi-phase LR schedule WD Momentum as certain multi-phase exponential LR schedule with Momentum.
2.1 REPLACING WD BY EXPONENTIAL LR IN MOMENTUM-FREE SGD
We use notation of Section 1.2 and assume LR fixed over iterations, i.c. 7, = 7/- and 7 (momen- tum factor) is set O. We also use À to denote WD factor and Og denote the initial parameters.
3

---

Published as a conference paper at ICLR 2020
The intuition should be clear from Lemma 1.3, which says that shrinking parameter weights by factor P (where p < 1) amounts to making the gradient p times larger without changing its direction. Thus in order to restore the ratio between original parameter and its update (LR x Gradient), the easiest way would be scaling LR by p². This suggests that scaling the parameter 0 by at each step is equivalent to scaling the LR 1) by p=²
To prove this formally we use the following formalism. We'll refer to the vector (0, 17) the state of training algorithm and study how this evolves under various combinations of parameter changes. We will think of each step in training as a mapping from one state to another. Since mappings can be composed. any finite number of steps also correspond a mapping. The following are some basic mappings used in the proof.
1. Run GD with WD for step:
GD n) (p0 ()),
2. Scale the parameter 0:
(1, 17) (cO,1))
3. Scale the LR 1y:
(0, 17) (0,cr).
For example, when & = GD. is vanilla GD update without WD, also abbreviated as GD,, When p 0= 1- Aroo- G -Apo is GD update with WD X and L.R vpo Here I, is the loss function at iteration f, which is decided by the batch of the training samples B, in 1th iteration. Below is the main result of this subsection, showing our claim that GD + WD + GD+ Exp LR (when Momentum is zero). It will be proved after a series of lemmas.
Theorem 2.1 (WD Exp LR). For every p 1 and positive integer following holds:
GD ..... o GD = TTp IT o 12 o GD,-1 o 11. GD2 o m1p o GDg o 1T
With WD being X, is set as 1 - Aooo and thus the scaling factor of LR per iteration is pー (1 (1-Arp) Ano) except for the first iteration it's p=
Ano)
We first show how to write GD update with WD as composition of above defined basic maps.
Lemma 2.2. GD II 11g GD, o I1."
Below we will define the proper notion of equivalence such that (1). IIf IE which implies GD, IT3 GD, IT. ; (2) the equivalence is preserved under future GD updates.
We first extend the equivalence between weights (same direction) to that between states, with addi- tional requirement that the ratio between the size of GD update and that of parameter are the same among all equivalent states, which yields the notion of Equivalent Scaling.
Definition 2.3 (Equivalent States). (0,n) is equivalent to (0', ,') iff 3c 0. (0. = [Lf
10, = (cO, e²m)) which is also denoted by (0. (0,m) 2 (0.n). IIf 115 is called Equiva- lent Scaling for all e 0.
The following lemma shows that equivalent scaling commutes with GD update with WD, implying that equivalence is preserved under GD update (Lemma 2.4). This anchors the notion of equiv- alence we could insert equivalent scaling anywhere a sequence of basic maps(GD update, LR/parameter scaling), without changing the final network.
Lemma 2.4. For any constant c, > O and I 2 0, GD o [T o n35)= [ o n GD.. In other words, (0,1) - (0',n') n/) = GD, 2 (O'(
Now we formally define equivalence relationship between maps using equivalent scalings.
Definition 2.5 (Equivalent Maps). Two maps F, G are equivalent iff 3e 0, F IIf o IT5 G. which is also denoted by S G.
Proof of Theorem 2.1. By Lemma 2.2., GD, L 11 o GD, o 11 By Lemma 2.4, GD update preserves map equivalence, i.e. F 2 G GD, o o e GD, deve,p > 0. Thus,
GDL_, o.... GD$ L TT." GD o TT' o.. GD, m
GD, TT
n
4

---

Published as a conference paper at ICLR 2020
95.0
Train Acc
1027
l|w_t|l
92.5
Test Acc
10
||w_i||>2 2
90.0
10
87.5
10
85.0
10
82.5
10a
80.0
25
50
75
100
125
150
25
50
100
125 150
Figure Taking PreResNet32 with standard hyperparameters and replacing WD during first phase (Fixed LR) by exponential LR according to Theorem 2.9 to the schedule îj. 0.1 x 1.481". momentum 0.9. Plot on right shows weight satisfying Iw, %
of the first convolutional layer in the second residual block grows exponentially, constant. Reason being that according to the proof essentially the norm square of the weights when trained with Fixed LR WD Momentum, and published hyperparameters kept this norm roughly constant during training.
2.2 REPLACING WD BY EXPONENTIAL LR: CASE OF CONSTANT LR WITH MOMENTUM
In this subsection the setting is the same to that in Subsection 2.1 except that the momentum fac- tor is instead of O. Suppose the initial momentum is tn. set 0-1 On Ut/). Presence of momentum requires representing the state of the algorithm with four coordinates, (0, 17. 0', (²))),
which stand respectively for the current parameters/LR and the buffered parameters/L.R (from last iteration) respectively. Similarly, we define the following basic maps and equivalence relationships.
1. Run GD with WD for step:
GD, 0',' (00 + (7
VL2(0)) .1, 0.
2. Scale Current parameter 0
1,',,,,'',1f (cO,1) n1, 0', O',r));
3. Scale Current LR
I5( 0''0 (0, cn) 0', ,')
4. Scale Buffered parameter 0':
ug(0,, n, 07,7 (0, c0', 10),1));
5. Scale Buffered parameter n/:
1q(0,n,0'.. n',""") = (0, m. 0' ,PC))
Definition 2.6 (Equivalent States). (0,n.0',1)
equivalent to (0,7, 0', iff 3e
(0, 0', (7)7 (cf, c2,,c,,,, c0', ,'',e' ,,,)), which is also denoted by (0, 1, ,0, n/') - (0,7. 0", )7). We call 11ş ITg" nTg IT5" Equivalent Scalings for all e > 0.
(0, 17, 0' n1') [I IT5" II II.")
Again by expanding the definition, we show equivalent scalings commute with GD update.
Lemma 2.7. Ve, p > and 2 0, GD$ o [1 115 IIg 11
[ o 115
IIg n1 GD
Similarly, we can rewrite GD& as composition of vanilla GD update and other scalings by expand- ing the definition, when the current and buffered LR are the same in the input of GD,. Lemma 2.8. For any input (0, 17, 0', .7), a >> 0 is a root of a + 7a p 1+ then (0,(0, 0' .1) = [T o m GD, 0'
1I o GD,
IT o Ti o IT (0, 0' ,',)). ). In other words,
II
II
o II o GD, II II II
(0, 0', n).
(5)
Though looking complicated, the RHS of Equation actually the desired TT conjugated with some scaling on momentum part Iīg II; and Ig II in the current update cancels with the Ig II in the next update. Now we are ready show the equivalence between WD and Exp LR schedule when momentum is turned on for both.
GD, II
Theorem 2.9 (GD WD + GD+ Exp LR; With Momentum). The following defined two sequences of parameters {0, 100 and |0 satisfy 0 = a'O,, thus they correspond to the same networks in function space, i.e. fo. fe. Vt E N, given O, 0o. 0_ 0_10, and ñj -
1.
0
7(0
1 0, 2)
vo(L(O,-1) + (0,1)
70
2.
0. 0
7(0 カー-1
0. 2)
VeL(0,-1)
5

---

Published as a conference paper at ICLR 2020
angle between W. w,t, W. [+1
95
TEXP
0.4
Step Decay
Test Accuracy
90
0.2
85
TEXP
Step Decay
0.0
80
100
200
300
100
200
300
Figure 2: PreResNet32 trained with standard Step Decay and its corresponding
LR sched-
ulc. As predicted by Theorem 2.12, they have similar trajectories and performances.
where a is a positive root of equation x² - (1 + - \mo) + 7 = 0, which is always smaller than 1(See Appendix B.1). When y = 0, 1 - Anoo is the unique non-zero solution.
Remark 2.10. Above we implicitly assume that Amjo < (1 v such that the roots are real and this is always true in practice. For instance of standard hyper parameessssssess where ? 0.9, nlu 0.1, 0.0005, (I-vT)² 0.019 <
Ano
Proof. Note that (0o, To. 0 7-1
113
113 o
11g
(Oo, no. Oo no). it suffices to show that
[ig III
I12 o GD,-1 11
GD, 11. GD, 11 o IIg 11$
(0o, 70. no)
GD 1-Aoo
GD
- (Pu. To, co no),
Amo
Vt 2
which follows immediately from Lemma 2.7 and Lemma 2.8 by induction.
2.3 REPLACING WD BY EXPONENTIAL LR: CASE OF MULTIPLE LR PHASES
Usual practice in deep learning shows that reaching full training accuracy requires reducing the learning rate a few times.
Definition 2.11. Step Decay is the (standard) learning rate schedule, where training has K phases I 0, K where phase starts at iteration Ty (To 0), and all iterations phase use a fixed learning rate of 177.
The algorithm state Section 2.2, consists 4 components including buffered and current LR. When LR changes, the buffered and current LR not equal, and thus Lemma 2.8 cannot be applied any more. In this section we show how to fix this issue by adding extra momentum correction. In detail, show the below defined Exp LR schedule leads the same trajectory of networks in function space, with one-time momentum correction at the start of each phase. We empirically find on CIFARIO that ignoring the correction term does not change performance much.
Theorem 2.12
LR Schedule). There exists way to correct the momentum only at the first iteration of each phase, such that the following (TEXP) { with momentum factor 7 and no WD, leads the same sequence networks in function space as that of Step Decay LR schedule(Definntion 2.11) with momentum factor y and WD X.
LR schedule
1 X (aj-1)-² 71-1
if + < <t 1 1,121;
(6)
x "
"i (0i)~
if Ti, 1 2 1,
1+ (14t- 7o 1o (a 1/ (aa))1
where a7
The analysis in previous subsection give the equivalence within each phase, where the same LR used throughout the phase. To deal with the difference between buffered LR and current LR when entering new phases, the idea is to pretend 7h- = 7/t and 0:-1 becomes whatever it needs to maintain 0.-0.-1 such that we can again apply Lemma 2.8, which requires the current LR of 7t-1 the input state is equal to its buffered LR. Because scaling in RHS of Equation 5 is different in different phases, so unlike what happens within each phase, they don't cancel with each other phase transitions, thus remaining correction of the momentum. The proofs are delayed to Appendix B, where proves more general statement allowing phase-dependent WD, 1-1

---

Published as a conference paper at ICLR 2020
Alternative interpretation of Step Decay to exponential LR schedule:Below present new LR schedule. TEXP++, which is exactly equivalent to Step Decay without the need of one-time correction of momentum when entering each phase. We further show in Appendix B.1 that when translating from Step Decay, the TEXP++ we get is very close to the original TEXppEquaiion 9),
i.e. the ratio between the LR growth per round, T / Vi-1 converges to exponentially each phase. For example, with WD 0.0005, max LR 0.1, momentum factor 0.9, the ratio is within + 0.0015 0.9 meaning TEXP and TEXP++ are very close for Step Decay with standard hyperparameters.
Theorem 2.13. The following two sequences of parameters ,{0: 1 and {0:] define the same sequence of network functions, i.e. fo. fo. Vt E N, given the initial conditions, 0g Poou. 0-1
P-10-1.
1. 0,-01-1
0 01-1
Vo (((())_)) + 4-1 1 for 1,2....
Q--1
7
M11
2
2.
0. 01-1
7
8 0.-2 VoL(O.-1), for 1,2,...
Mt-1
l1--
where f7- = P.Pe+im.
Pt = II aj Vt 2 -1 and a₁ recursively defined as
1=-1
0₁ = - T/- - + 1+ Th 7(1 ar a. 1.
(7)
2h-2
The LR schedule (Th J is called Tapered Exponential ++, or TEXP++
3 EXAMPLE ILLUSTRATING INTERPLAY OF WD AND BN
The paper so far has shown that effects of different hyperparameters in training are not easily sep- arated, since their combined effect on the trajectory is complicated. We give a simple example to illustrate this, where convergence is guaranteed if either BatchNorm weight decay in isolation, but convergence fails if both are used. (Momentum is turned off for clarity of presentation)
Suppose we are fine-tuning the last linear layer of the network, where the input of the last layer is assumed to follow a standard Gaussian distribution N (00 T,,), and m is the input dimension of last layer. We also assume this is binary classification task with logistic loss, 1(u, y) In(1 + exp(-uy)), where label E 1, 1} and u E IR is the output of the neural network. The training algorithm is SGD with constant LR and WD, and without momentum. For simplicity we assume the batch size B is very large so we could assume the covariance of each batch B3 concentrates and is approximately equal to identity, namely B Σ 21,,,0,66 Lm- We also assume the the input of the last layer are already separable, and w.l.o.g. we assume the label is equal to the sign of the first coordinate of E R", namely sign (x1). Thus the training loss and training error are simply
Setting:
E L(w) (0,N(0,) )
[In(1 exp(-x: ['w)))]] 2 N (... siggn((()))
Pr
x wy S 0 arccos
Wi
[
Case 1: WD alone: Since both the above objective with 1.2 regularization is strongly convex and smooth in w, vanilla GD with suitably small learning rate could get arbitrarily close to the global minimum for this regularized objective. In our case, large batch SGD behaves similarly to GD and can achieve O(v ndd test error following the standard analysis of convex optimization.
Case 2: BN alone: Add a BN layer after the linear layer, and fix scalar and bias term to 1 and O. The objective becomes
E LBN(W) 1.-N(o..mm.v-ssotttee
E [LB x)] 1.
In(1 + exp(-x" |
y))
From Appendix B.6, there's some constant C. such that Yo E Rm with constant prob- C
ability, VWLLEN (w, (w,x))l x)| 2 [ By Pythagorean Theorem, ||
(Iw,, +
x)12 As a result, for any fixed learning rate, | 4 2 2 2 7 V Lax ( w, ))l? grows at least linearly with high
LL, x) 12 2 ||,,| 1 #++ V
probability. Following the analysis of Arora et al. (2019), this is like reducing the effective learning
7

---

Published as a conference paper at ICLR 2020
rate, and when ||w/|| is large enough, the effective learning rate is small enough, and thus SGD can find the local minimum, which is the unique global minimum.
Case 3: Both BN and WD: Suppose WD factor is X, LR is n, have the following theorem:
Theorem 3.1. [Nonconvergence] Starting from iteration any To, with probability 1 ó over the randomness of samples, the training error will larger than g least once for the following
consecutive ) In 611 PPsBB + 9 in iterations.
7/m-2
Sketch, (See full proof in Appendix B.) The high level idea of this proof is that if the test error is low, the weight is restricted in small cone around the global minimum, and thus the amount the gradient update is bounded by the size of the cone. In this case, the growth of the norm of the weight by Pythagorean Theorem is not large enough to cancel the shrinkage brought by weight decay. As a result, the norm of the weight converges to 0 geometrically. Again need to the lower bound for size of the gradient, that Le = O gy/m holds with constant probability. Thus the size of the gradient will grow along with the shrinkage of ||,ll until they 'e comparable, forcing the weight leave the cone in next iteration.
EXPERIMENTS
The translation to exponential LR schedule is exact except for one-time momentum correction term entering new phases. The experiments explore the effect of this correction term. The Tapered (xponential(TEXP) LR schedule contains two parts when entering a new phase I: an instant LR decay ) and adjustment of the growth factor (aī-1 af). The first part is relative small compared to the huge exponential growing. Thus a natural question arises: Can we simplify TEXP LR schedule by dropping the part of instant LR decay?
Also, previously we have only verified our equivalence theorem in Step Decay LR schedules. But not sure how would the Exponential I.R schedule behave on more rapid time-varying I.R schedules such as Cosine LR schedule.
Settings: We train PreResNet32 on CIFARIO. The initial learning rate is 0.1 and the momentum 0.9 all settings. We all the scalar and bias of BN, because otherwise they together with the following conv layer grow exponentially, sometimes exceeding the range of Float32 when trained with large growth rate for a long time. We fix the parameters in the last fully connected layer for scale invariance of the objective.
4.1 THE BENEFIT OF INSTANT LR DECAY
We tried the following LR schedule (we call it TEXP--). Interestingly, up to correction of momentum when entering a new phase, this schedule is equivalent to a constant LR schedule, but with the weight decay coefficient reduced correspondingly at the start of each phase. (See Theorem B.2 and Figure 6)
M/ (aj-1)
if S tt Tr 1, 1;
TEXP-
M++1
x 17t
(at)
(a
if Tı, I 2 1,
(8)
147 147-MDf An) + (1177 Anj) >
where a;
.ju = = no (aa)) = n (ani)
2
4.2 BETTER EXPONENTIAL LR SCHEDULE WITH COSINE LR
We applied the TEXP LR schedule (Theorem 2.12) on the Cosine LR schedule (Loshchilov & Hutter, 2016), where the learning rate changes every epoch, and thus correction terms cannot be
ignored. The LR at epoch & < T is defined as: π) = 170 1+cos( Our experiments show this hybrid schedule with Cosine LR performs better CIFAR10 than Step Decay, but this finding needs to be verified on other datasets.
5
CONCLUSIONS
The paper shows rigorously how BN allows a host of very exotic learning rate schedules in deep learning, and verifies these effects in experiments. The Ir increases exponentially in almost every
8

---

Published as a conference paper at ICLR 2020
0.5
96
angle between t.. W t+]
TEXP
0.4
TEXP--
TEXP ;Decay once
Test Accuracy
92
0.3
TEXP-.:Decay once
90
0.2
88
TEXP
TEXP--
0.1
86
TEXP :Decay once
84
TEXP-;Decay
0.0
50
100
150
200
250
300
100
200
300
Figure 3: Instant LR decay is crucial when LR growth 7/. / 1 is very small. The original LR of Step Decay is decayed by 10 at epoch 80, 120 respectively. In the third phase, LR growth îj. fh./7-11 is approximately 100 times smaller than that in the third phase, it would take TEXP-- hundreds of epochs to reach its equilibrium. As a result, TEXP achieves better test accuracy TEXP a comparison. the second phase, Îje/ f only times smaller than that the first phase it only takes epochs to return to equilibrium.
94
0.5
EXP LR
Angle between W t. w.
Instant Decay
0.4
Test Accuracy
0.3
88
0.2
86
0.1
EXP LR
Instant LR Decay
25
75
100
125
150
#epochs
25
50
75
100
125
150
Figure 4: Instant LR decay has only temporary effect when LR growth 7j. ht//1p-11 is large. The blue line uses exponential LR schedule with constant exponent. The orange line multiplies its LR by the each iteration, also divide LR by 10 at start of epoch 80 and 120. The instant LR decay only allows parameter to stay at good local minimum for epoch and then diverges, behaving similarly to the trajectorics without no instant LR decay.
constant
COSINE
96
0.4
COS-EXP
94
TEXP
angle between W.
0.3
Step Decay
Test Acc
92
90
0.2
88
COS-EXP
0.1
TEXP
86
Step Decay
84
0
50
100
150
200
250
300
0
50
100
150
200
250 300
Figure Cosine and Step Decay schedule behaves almost same as their exponential counterpart, as predicted by our equivalence theorem. The (exponential) Cosine LR schedule achieves better test accuracy, with a entirely different trajectory.

---

Published as a conference paper at ICLR 2020
iteration during training. The exponential increase derives from use of weight decay, but the precise expression involves momentum as well. We suggest that the efficacy of this rule may hard to explain with canonical frameworks in optimization.
Our analyses of BN is a substantial improvement over earlier theoretical analyses, since accounts for weight decay and momentum, which are always combined in practice.
Our tantalising experiments with hybrid of exponential and cosine rates suggest that more surprises may lie out there. Our theoretical analysis of interrelatedness of hyperparameters could also lead to faster hyperparameter search.
REFERENCES
Sanjeev Arora, Nadav Cohen, and Elad Hazan. On the optimization of deep networks: Implicit acceleration by overparameterization. In International Conference on Machine Learning, pp- 244-253 2018.
Sanjeev Arora, Zhiyuan Li, and Kaifeng Lyu. Theoretical analysis auto rate-tuning by batch normalization. In International Conference Learning Representations, 2019. URL https: / //openreview net. forum? wd-.mmmiddii-ddaee nA 9FX...
Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hinton. Layer normalization. arXiv preprint arXiv:1607.064500 2016.
Nils Bjorck. Carla P Gomes, Bart Selman, and Kilian Q Weinberger. Understanding batch normal- ization. In Bengio, H. Wallach, Larochelle, K. Grauman, N. Besa-Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems 31, pp. 7705-7716. Curran Asso- ciates, Inc., 2018
Minhyung Cho and Jachyung Lee. Riemannian approach to batch normalization. In Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems 30, pp. 5225-52555555 5235. Curran Associates, Inc., 2017.
Sanjoy Dasgupta and Anupam Gupta. An elementary proof of a theorem of johnson and linden- strauss. Random Structures & Algorithms, 22(1):60-65 65, 2003.
Robert Mansel Gower, Nicolas Loizou, Xun Qian, Alibek Sailanbayev, Egor Shulgin, and Peter Richtárik. Sgd: General analysis and improved rates. arXiv preprint 1901v:901.0094000 2019.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference computer vision and pattern recognition, pp- 770-778, 2016a.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Identity mappings in deep residual networks. In European conference on computer vision, pp. 635-645. Springer, 2016b.
Elad Hoffer, Ron Banner, Itay Golan, and Daniel Soudry. Norm matters: efficient and accurate normalization schemes deep networks. S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Biandhe and R. Gareett (eds.), Advances in Neural Information Processing Systems 31, pp. 2164-2172 Curran Associates, Inc., 2018a.
Elad Hoffer, Itay Hubara, and Daniel Soudry. Fix your classifier: the marginal value of training the last weight layer. In International Conference on Learning Representations, 2018b. URL https:://// wwpp/ppeeeveeeeeeeeeeeeeeeeeeeee .nt/ forum?id=S11Dh8Tgg))
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International Conference on Machine Learning, pp. 448-456, 2015.
Jonas Kohler, Hadi Daneshmand, Aurelien Lucchi, Ming Zhou, Klaus Neymeyr, and Thomas Hof- mann. Exponential convergence rates for batch normalization: The power of length cengtt-direction decoupling in non-convex optimization. arXiv preprint / 10694, 2018.
10

---

Published as a conference paper at ICLR 2020
Iyy Loshchilov and Frank Hutter. SGDR: Stochastic Gradient Descent with Warm Restarts. arXiv e-prints, art, arXiv:1608.03995 Aug 2016.
David Page. How to train your resnet 6: Weight decay?
URL https://myrtle.aat
tow-to-traiin your resnet- 6 6-weight berighhtdeecy/-
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. 2017.
Shibani Santurkar, Dimitris Tsipras, Andrew Ilyas, and Aleksander Madry. How does batch nor- malization help optimization? In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa- Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems 31, pp. 2488- 2498. Curran Associates, Inc., 2018.
Leslie N Smith. Cyclical learning rates for training neural networks. 2017 IEEE Winter Confer- ence on Applications of Computer Vision (WACV), 464-472. IEEE, 2017.
Ilya Sutskever, James Martens, George Dahl, and Geoffrey Hinton. On the importance of ini- tialization and momentum deep learning. In Proceedings of the 30th International Confer- International Conference Machine Learning Volume 28, ICML'I3, pp. III-1139- III-1147. JMLR.org. 2013. URL http: /tt.daaacmmmm.mmmmmmmmmoomoo wwt.ttot//tttiiioonooo cwm woc.mmmiiiie of0..o.328mmm11112211111 3043064.
Dmitry Ulyanov, Andrea Vedaldi, and Victor Lempitsky. Instance normalization: The missing in- gredient for fast stylization. arXiv preprint arXiv:1607.08022 2016.
Twan van Laarhoven. L2 regularization versus batch and weight normalization. arXiv preprint arXiv:/706.. 05350, 2017.
Xiaoxia Wu, Rachel Ward, and Léon Bottou. WNGrad: Learn the Learning Rate in Gradient De- 2018.
scent. arXiv preprint
Yuxin Wu and Kaiming He. Group normalization. In The European Conference Computer Vision (ECCV), September 2018.
Yang You, Igor Gitman, and Boris Ginsburg. Large Batch Training of Convolutional Networks. arXiv e-prints, art, ww.Xiv1108..00 03888, Aug 2017.
Guodong Zhang, Chaoqi Wang, Bowen Xu, and Roger Grosse. Three mechanisms of weight decay regularization. In International Conference Learning Representations, 2019. URL https: / // /pppneevieww.c.om wmr - 3Rct

---

Published as a conference paper at ICLR 2020
A VIEWING EXP LR VIA CANONICAL OPTIMIZATION FRAMEWORK
This section tries to explain why the efficacy of exponential LR deep learning is mysterious to us, at least as viewed in the canonical framework of optimization theory.
Canonical framework for analysing 1st order methods This focuses on proving that each -or most-steps of GD noticeably reduce the objective, by relying on some assumption about the spec- trum norm of the hessian of the loss, and most frequently, the smoothness, denoted by 3. Specifically,
for GD update 01+1 = 0, L()), we have
3 L(0,+1) L().) < (0.+1 0.) T.)TTLLL VL( + 2 11.111 -
Bn 2 (L(()))
When / < the first order term is larger than the second order one, guaranteeing the loss value decreases. Since the analysis framework treats the loss as a black box (apart from the assumed bounds on the derivative norms), and the loss is non-convex, the best one can hope for is to prove speedy convergence a stationary point (where gradient close to 0). An increasing body of work proves such results.
Now we turn to difficulties in understanding the exponential LR in context of the above framework and with scale-invariance in the network.
1. Since loss is same for 0 and f for all > simple calculation shows that along any straight line through the origin, smoothness is a decreasing function of and is very high close to origin. (Note: is also possible to one can show the following related fact: In any ball containing the origin, the loss is nonconvex.)
Thus if one were trying to apply the canonical framework to argue convergence to a sta- tionary point, the natural idea would be to try to grow the norm of the parameters until smoothness drops enough that the above-mentioned Canonical Framework starts to ap- ply. Arora et al. (2019) showed this happens in GD with fixed LR (WD turned off), and furthermore the resulting convergence rate to stationary point is asymptotically similar to analyses of nonconvex optimization with learning rate set as in the Canonical framework. Santurkar al. (2018) observed similar phenomenon in experiments, which they described as a smoothening of the objective due to BN.
2. The Canonical Framework can be thought of as discretization of continuous gradient descent (i.e., gradient flow): in principle it is possible to use arbitrarily small learning rate, but one uses finite learning rate merely keep the number of iterations small. The discrete process approximates the continuous process due to smoothness being small.
In case of gradient flow with weight decay (equivalently, with exponential LR schedule) the discrete process cannot track the continuous process for very long. which suggests that any explanation of the benefits of exponential LR may need to rely on discrete process being somehow better. The reason being that for gradient flow one can decouple the speed of the 0: into the tangential and the radial components, where the former one has no effect on the norm and the latter one has no effect on the objective but scales the tangential gradient exponentially. Thus the Gradient Flow with WD gives exactly the same trajectory vanilla Gradient Flow does, excepting a exponential reparametrization with respect to time t.
3. It can be shown that if the local smoothness is upperbounded by 7 (as stipulated in Canon- ical Framework) during sequence O₂ (t 1, 2,...) of GD updates with WD and constant LR then such sequence satisfies 0, + 0. This contrasts with the usual experimental obser- vation that O, stays bounded away from O. One should thus conclude that in practice, with constant LR and WD, smoothness doesn't 't always stay small (unlike the above analyses where WD is turned off).
B OMITTED PROOFS
B. OMITTED PROOF IN SECTION 2
Lemma B.1 (Some Facts about Equation 1). Suppose 21, 22) 2 2²) are the two real roots of the the following equation, we have
(1+ An) + +7=0
12

---

Published as a conference paper at ICLR 2020
=²= An /(1
1. 2
2
2. 2 are real - Am 1 (1 vT)²:
3. 2 = -,,² + = 7 Xn))
4. 1152 S s::$:: 1
5. Lett I- we have 2 2 Itt 21-1=1- An 1-7
6. if view 2 (An), x2 (2n) as functions of 2n,. then 2 (2n) is monotone decreasing, z² =2(n) is monotone increasing.
Proof.
4. Let = x² (1 (1+7 -2
Xn)a + have f(1) f()) Xn 0. Note the minimum
of is taken 1+7-An An [0, 1], the both roots of f(x) 0 must lie between 0 and 1, if exists.
1 2 1-7 An /(1 (1
7)2 2(1 7) + X272
1+t 1+7 1+1++ + t I-7
(1 (1-7)
2t + 2 l+7
(1
1-7
2(1 + / 1- +
1-9 1
< (1 7) 4(1 +t)
t
(1+
6. Note that (z) 22
22)2 (z + 2)2 42 (1 (1+~-XA 2 -4y is monotone decreasing,
since 2 (>n) 2² (An) is constant, 2. (An) 22n),, 2. 32(m)) must be decreasing and (2ri) must be increasing.
B.2 OMITTED PROOFS SECTION 2.
Proof of Lemma 2.2. For any (0, n)), we have
GD, m) (p0 v)V [II o 1II - GD,](0, ") /
-[I 11 GD, 11, (0.m) (00")
Proof of Lemma 2.4. For any (0, we have
GD, o II o I1
(0.n) = GD, en) = (cf - L.VV = (c(0 VL(()), en)
[ o m o GD, (0,n).
= Scale Invariance, Lemma 1.3)
13

---

Published as a conference paper at ICLR 2020
B.3 OMITTED PROOFS SECTION 2.2
Proof of Lemma 2.7. For any input (0, ,''), it's easy to check both composed maps have the same outputs the 2,3,4th coordinates, namely (c2n,c0, c2n'). For the first coordinate, we have
GDO, cf' ,en),, pcd en (> 0 0' ry
VL. (c0) = (o 0 + (7 0 0'
VL,(0)
ry
=c (e," 17 0¹ n)h =: Scale Invariance, Lemma 1.3
Proof of Lemma 2.8. For any input (0, 0', n1)), it's easy to check both composed maps have the same outputs on the 2,3,4th coordinates, namely (17, 0, 17) For the first coordinate, we have
n HI
I o GD, II
11 o a
(0, n. 0' m) = a [GD,(0, a "n,n,,, at', .nn]]
1 - -VL((0) 0 + 'n
=a
= =a ya - nVV m
= ( - VV 00' = [GD 0', m)]
B.4 OMITTED PROOFS OF THEOREM 2.12
In this subsection will prove a stronger version of Theorem 2. 2(restaae below), allowing the WD.A, changing each phase.
Theorem B.2 (A stronger version of Theorem 2.12). There exists a way to correct the momentum only at the first iteration of each phase, such that the following Eppered-Exponentiin LR schedule (TEXP) {ic with momentum factor y and no WD, leads the same sequence networks in function space compared that of Step Decay LR schecule(Defimiition 2.11) with momentum factor y and phase-dependent WD Xj in phase J, where phase / lasts from iteration Ty to iteration T1+1, To = 0.
πr. x (aj_1)-
if + t - 1.121
7h+1 =
Tt Mi x (a)
if = Tr, 2
where a; 1+ )
7 To (aa)a) (ā()))
2
Towards proving Theorem 2.12, we need the following lemma which holds by expanding the defi- nition, and we omit its proof.
Lemma B.3 (Canonicalization). We define the Canonicalization map as N(O, 0', n/) = (0, 11,
2 ( -0), n), and it holds that
1. GD o N GD,, Vp > 0.
2. N M1 mg mIg n
I1 I15 IT e 11
N, Ve> 0.
Similar to the case of momentum-free SGD, we define the notion of equivalent map below Definition B.4 (Equivalent Maps). For two maps and G, we say F is equivalent to G iff Fe > 0.
F TTC nl TT o mTg") G, which is also denoted by F e G.
Note that for any (0, n, 0' 1/)), (N n, 0', ./))22 = (N(O, n. 0', (///).. Thus as a direct consequence of Lemma 2.8, the following lemma holds.
Lemma B.5. Vp,a 0, GD, o N 2 ng
IT
GD, o o
nT o II o N.
Proof of 122 Starting with initial state (0o, no. 0_1, n-1) where 7-1 Yu and given LR schedule {nı h:20 the parameters generated by GD with WD and momentum satisfies the following
relationship:
14

---

Published as a conference paper at ICLR 2020
11+11711,,0,111 0p, = 112 1ill
GD
m
(0,, 0: 1,
Define O Fi Fb Fb-1 Fa. for a S b. By Lemma B.3 and Lemma B.5, letting a, be the
1=
root of x²
(7 + 1 - Ttt 11-11111a + = 0, we have
R++1 12
GD -
112
GD, GD! m NN
11, "
R++1
o Ilg
t+1 o 111
fe o 11
GD, o Mr o Ilg Mn oN
=I1, 77-1
1II 11g
77-1 II""" o G
T-1 1
O
11
H. o GD )
II,""
11. -
o
11 o N,
(10)
1
π a
where
because of Lemma B.5, and H, is defined as
Wt-1 1I TE
II
Gi++
o IIftt o No II o II. II
II, PT-T
Since the canonicalization map N only changes the momentum part of the state, it's easy to check that H, doesn't it touch the current parameter and the current LR 7). Thus He only changes the momentum part of the input state. Now we claim that H, GD,-i = GD;-1 whenever T/t 7h-1-- This is because when V
7h-11 0g = 0++1
thus H, o GD,-1 = GD, In detail,
H2 GD
mT M I
No M3 I I GD,11
m II II
II oIl II GD,-1
-GD,11
where = is because GD update GD), sets '/' the same n, and thus ensures the input of N has the same momentum factor in buffer as its current momentum factor, which makes N an identity map.
He Thus we could rewrite Equation 10 with "eloppy"versioon of He Hi = Id o.w.
# T-1;;
11i1 II,
GD.
-II,
II
AT-1
II
GDr-1o
T-1
O II
a aj
Hi o GD,
1) II,"
nI
Il
N
t=1
GD, II o HH] oDD, 11 II II N,
=I1, II,
IIl
II
(11)
Now we construct the desired sequence of parameters achieved by using the Tapered Exp LR schedule and the additional one-time momentum correction per phase. Let (0g. To. 0
0,,77-1) =
(0o, 110, 0 O-1, 70), and
15

---

Published as a conference paper at ICLR 2020
(01, M, po Noo
GDg !
Iig' II .o (0,, To. 0_ 7-1
GDg 2 o g r
(On, t0. 0 1, 7--1)
( 1, 1, Oc, 7h) GD, 1l af
11 Hi (0,, Tt. n 1. 7h1)
we claim {0: t=u is the desired sequence of parameters. We've already shown that 0g ~ 0,, vt. Clearly (= is generated using only vanilla GD, scaling LR and modifying the momentum part of the state. When * Tj for any I, 7kk = Mh-1 and thus Hi = Id. Thus the modification on the momentum could only happen at (T 0). Also it's easy check that a, =77 if T7 + < tts T1
B.5 OMITTED PROOFS OF THEOREM 2.13
Theorem B.6. The following sequences of parameters {(,) and (0.) define the same sequence network functions, i.e. Sa. = Sö. VI N. given the initial conditions, 0o PoOp.
0_ = P-10-1.
1. 0: 0.-0.-
0:
1 0 Vo (L((0)_)) + A 1 10. fort t 1,2,...;
M--1
74-2
2. 0.-1
01-1 D.-2 VoL(O,-1) 1), fort - -1,2 1,,....
!1-1
where 77- PiPt+ilh P.
II a; Vt -1 and a recursively defined
Nh- 7 ar 7/-2
04 =-
(12)
needs to be always positive. Here oo. 0-1 are free parameters. Different choice of on, a-1 would lead to different trajectory for {Or}. but the equality that O: P.O, is always satisfied. If the initial condition given via vo. then it's also free to choose 77-1, 0-1 long as 7-1
0g-
Vo-
Proof of Theorem 2.13. We will prove by induction. By assumption S(I) : P.O. = o. fort 11,0. Now we will show that S(I) - S(t + 1), vi 2 0.
0,
0
P:11 0:-2
Vo (I(()--)) + Ae-1 110.
=
77-1
71-2
gradient
0:
θ1-1
7
0:1
0
- 01-2
VoL(O + N--10-11
M--1
71-2
Scale Invariance 0
01-1
011 01-2
Pa-
VoL( + 1--10-11
1/1-
111-2
Rescaling
Pr(O, - 0,-1)
(
02-2)
VOL(O,1)) -
0-11
=
PiPi-1911-
P1-1P1-27112
1-2
P.
Simpllying
P.O: 0₁
0,-1
0 ||
0
Vol((,-1)
77-1 1
P.O.
11-2
1/-1 P._ Pt
Simplfying
P.O, 04 0,-1
04 0
0 0
VoL(ū,1)) - 1-114-11
a, 0
=
i/11
11-2
Mh-1
Simplfying
P.O. 02 (1
17t 1 1-1 0
at
0--
- 0 voI(0.-11)
771
π2-2
16

---

Published as a conference paper at ICLR 2020
To conclude that P,O, θ2, it suffices to show that the coefficients before 0 is the same that in (2). In other words, we need to show
1 + a4 (1 n1 1d--2-22 7(1 - (((1)
7/-2
which is equivalent to the definition of ag Equation 12.
Lemma B.7 (Sufficient Conditions for positivity of az). Let Amaz max; de, Tmma max, Tje Define Zmin is the larger root of the equation x² (1 + 7 Amazmman x + ! 0. To guarantee the existence of 2max also assume Tmoo Amax
VPP. Then have
Va- 1,
ag
2min S a 1
(13)
Proof. We will prove the above theorem with strengthened induction
s(t):
vO l' S i, Zmin S or 1
Zmmn
Umaz
Since ag 1, S(() is obviously true. Now suppose S(t) is true for some N, we will prove S(t + 1).
First, since 0 < at & 1, at- = -c + + 7 - a, S
Again by Equation 12, we have
1 a++1 1-0+11 = Te + M1-1 1177 nh +
min
ne S Ap + (z 1)y = 1 Zmin:
7mnax
which shows C1+1 2 Zmin- Here the last step is by definition 2min-
Because of 0+++11 1 2 Zmins we have
0441
1- as41
2 (A++ O2 7) S = (Amax
min
-1
7)
Zmin
min
min
Z
T7-1
Mmaz
Bmar
Mmna
Now ready give the formal statement about the closeness of Equation 9 and the reduced LR schedule by Theorem 2.13.
Theorem B.8. Given a Step Decay LR schedule with {Tr (m ( LR schedule Theorem 2.13 the following(un = = 0):
the TEXP++
Mi Xj + +1 (
0;
0,
Xi
1 ni
7(1 - -
P II a
(=11
0t = P.P
It's the same the TEXP LR schedule((ū.)) in Theorem 2.12 throughout each phase J, in the sense that
1-1-1
(71 + Amannhmaz (1-Ti-1)
Mr-1
7/1
AmaxThaa
7
AmaxTaaaa
<
3
3
VT, $1S
7}
1-9
mmin
1
17

---

Published as a conference paper at ICLR 2020
where 2min is the larger root of x² - (1 + Amaz7maz) )x + y 0. In Appendix B, show that 2min 1 AmusAmau When Amax//maz is small compared to 1 7/ which is usually the could approximate Zmin by 1. For example, when 7 0.9, Amaz 0.0005,
1-7
case in practice,
Mmaz 0.1, the above upper bound becomes
ft-1
1/-1
S 0.0015 x 1.90099-T,--1
1/.
Proof Theorem B.8. Assuming 2 and 27{2} 2 27) are the roots of Equation 1 with rj ?) and
À = Az. we have S 27. I / S 2min = S 1, VI, I' E [K -K-11 1] by Lemma B.1.
We can rewrite the recursion in Theorem 2.13 the following:
at = - + 1+ 7(1 a a = - (2) + +z + 2/ -1
(14)
In other words, we have
2] - 1.
- 2
(15)
04-1
By Lemma B.7, we have 0₁ 2 Smins Vt 2 0. Thus !
at 1|
02-1
Smin
G4-1
S 7(1 + An 2j
which means geometrically converges to its stable fixed
point 27.
and 7t-1
(z Since that Zmén S at S 1, Emin
S 2) S 1, we have 1 - 1| S
1-Emin
Amazulmaz 1-7
< 1, and thus - 11 Amarymaa I-y
) - T141-
-1
Zmiin
Note that aj 2). Pe-1 0400+1 By definition of TEXP and TEXP++, we have
(2/_1)2
If -
9--1
Di 27
(16)
if =
7/-
0++10t
if + +1 ift= 11,111121
a++10
7i Cry +1
(17)
ft
Thus we have when = Tı,
Mc-1
71-1
0T
OT,
aT;+1
QT
aT,+1
<
<
1
+
1/.
2j
1
27
21
27
Amaz Tman
3
When T) + +1 T/41, we have
Ā7-1
7h-1
ac++1
a++1
0++1
5
1
91
1/t
2]
2/_1
Amaz Minax
7
8-
-1
7
2
Thus we conclude V/ E KK
T7+1, we have
fr-1
1/-
Amax Mmax
t-1--1
Amaz Mmaa . x- Ti T1-1(14
Amaalmaz ) 2(1--T
1
<
3
114
7/
716
?
2min
1
18

---

Published as a conference paper at ICLR 2020
B.6 OMITTED PROOFS IN SECTION 3
We will use v to denote w |
and Luw to arccos(ú (w)). Note that training error I is equivalent
to Lei E.
Case 1: WD alone Since the objective is strongly convex, it has unique argmin wt. By symmetry,
w = Be1, for some B > O. By KKT condition, we have
2 -V
A (0.1)
E (1.1(
| =
I exp(3(x1))
which implies ||=0| = x
By Theorem 3.1 of Gower et al. (2019), for sufficiently large t, we have les, =01 = 0( (x))) Note that Zei W. -="w: sin Lw" w; <2 /w0" "o0==wll expected error E. (Ze, w // O A
have E (Ler 0(%) ), the
Case 3: Both BN and WD We will need the following lemma when lower bounding the norm of the stochastic gradient. Lemma B.9 (Concentration of Chi-Square). Suppose XI,... Xx
Lid.
~
NO, 1), then
X? < kB < (Bel
Pr
(18)
Proof. This Chernoff-bone fronndff-ooudd based proof is special case of Dasgupta & Gupta (2003).
Pr
X²
k3
< (3c2-
exp
ktß
X?
1
i=1
(19)
E
exp
ktß t Σ x?
(Markov Incquality)
i=1
=e ktB
(1 + 21) 21)
The last equality uses the fact that E [tX]]
for t < 3. The proof is completed by taking
-1
t
1-8
Setting for Theorem B.6: Suppose WD factor is LR n,, the width of the last layer is m 2 3. Now the SGD updates have the form
B
01++1 =w:
B
"
IV
In(1 + eexp(-aaa
24.6"
|
w. 11,8)) ) + 2 1 /eesel?
B
IT 10 F1,8
Vt,b
=(1 - --n)
B
+ exp(x
Tw. vc,b)
|/
6m
where Ltb Ltd. (00 Im.) Ur.b = sign ([x,,o1), and IT.,.
w.w,
1 1
Proof of Theorem B.6.
19

---

Published as a conference paper at ICLR 2020
64 wry Pe and T2 = 9 g. Thus if we assume the training Step 1: Let Ti 2(m)-2e3) In
1/v
error is smaller than from iteration To To T1 + T2, then by spherical triangle inequality, ww & Leiwe + Zej Wi = 2e, for To 1 t,t _ To
T2.
Now let's define w/ (1 n,)w, and for any vector w, and we have the following two relation- ships:
||a0||| = (1 S)al[epl|.
2. [|w++|l| S
||
cos 22
The second property because by Lemma 1.3, (we++1 -o/) w/ and by assumption of small error, /W;+1 S 2s.
Therefore
WT +Tb 112 [TT 1
1 1/d Cos 2s
27
1 7
271
S 5 (nd -2??)
<e-221(AA-26)
7
2
2e
64 [Ur, 12
B
(20)
In other word, 11 112
7
Since | monotone decreasing,
||
S
61s
B
21
71
holds for any f T...... Ti T2.
618
Step 2: We show that the norm of the stochastic gradient is lower bounded with constant probability. 24.
In other words, we want show the norm of & -bm1 1+exp(2e.6 bounded with high probability.
is lower uP
T
Mr.b)
Let II be the projection matrix for the orthogonal space spanned by w, and é1. W.L.O.G. we can assume the rank of 11 is 2. In case w; e1. just exclude random direction to make I1 rank 2. Now we have II ee, Lt,b are still i.i.d. multivariate gaussian random variables, for Ve.6
b = 1. B, and moreover, II I.,,,,, Zt,b is independent to 1+exp(2ss, wy vi.o)" When m 2 3, we
lower bound ||&:| by dealing with || Er/l-
It's not hard to show that conditioned on f
T we [w
B
B Σ
Σ
Vr.b + exp(x111
II 10
Lt,b
Vt.b exp(xx1.
II Il
(21)
Vt,b)
1
| v1.b)
hml
6m
where x ~ NN(0 Im). We further note that
[T
22|2
(m 2). By Lemma B.9,
1
| ee 22
(22)
8
8e
8E
3
2
Now we will give a high probability lower bound for Σbm
Note that
T+explos,
| M1,b)
NO, 1), we have
We
1
Pr
1
(23)
which implies the following, where A is defined as
w. |2c
<
2
Tw
20

---

Published as a conference paper at ICLR 2020
1
E AA Pr
11
exp
x
Twlll y1
we
1+e
2
2
(24)
Note that Eb=1 Ar,6 S B. and E b=
EE==
13
Ar,o 2 2 we have Pr
Ebe Ar. <
B
Thus,
Pr Σ
Ut.b 1 (116
B 4(1
2 Pr
B
A
B
1
(25)
u Vr
E)
4
3
Thus w.p. at least 1. gr equation 25 and equation 22 happen together, which implies
7 B
V Vln(I+exp((aa
wi Lib
m.b) =
"
B
Vt.b
11 w. Lr,b
17 v m
11
wi
+ exp(x x
u0 Tez
U/.
8|| 8|1w
32 w0
(26)
Step 3. To stay in the cone {w] Zwe S e), the SGD update || w/ll 11 2b=1 V In(1 +
wy exp(-a,,b [elll (r,b))ll has to be smaller than |/wre|| sin 2s for any To + Ti...., To + T1 T2-
However, step I and 2 together show that |/V In(1 + exp(-a; [= [.i 2 2//w,, ||e w.p. b per
iteration. Thus the probability that we always stays in the cone for every t = To + .......... To
Ti + T2 is less than (5) T2 < 6.
Remark B.10. It's interesting that the only property of the global minimum we use is that the if both w/ W+41 are optimal, then the angle between w, and W is most 2e. Thus we indeed have proved stronger statement: At least once in every 2[n 2- In 6-Il IiteBBB + In 1/ iterations, the n//m2
angle between w, and w++1 will be larger than 2e, In other words, if the the amount of the update stablizes in terms of angle, then this angle must be larger than /2r for this simple model.
B.7 OMITTED PROOPS IN SECTION A
Lemma B.11. Suppose loss L is scale invariant, then L is non-comvex in the following two sense:
1. The domain is non-convex: scale invariant loss can't 't be defined at origin;
2. There exists no ball containing origin such that the loss is locally convex, unless the loss is constant function.
Proof. Suppose I(OO)= = supeeB L(O). W.L.O.G, we assume ||0*|| < 1. By convexity, every line segment passing 0" must have constant loss, which implies the loss is constant over set B - T -1 S c 0). Applying the above argument on any other maximum point 0' implies the loss is constant over (0).
Theorem 1. Suppose the momentum factor = O, th = is constant, and the loss function L is lower bounded. If 3c and T > such that VI 2 T. [(0+1)) f(0,) < -cy V
then lim 0 = 0.
Proof in Item 3. By Lemma 1.3 and the update rule of GD with WD, we have
| = [|(1 - An) |0 ( = (1 - Xn) 11 + (
which implies
[-1
10,12 = Σ (1 20- -
2))
T=
21

---

Published as a conference paper at ICLR 2020
Thus for any T > T
1
Σ 10:11 11 - (1 2
[T(())) + +10011
VI(00)] 110
An
Note that by assumption we have E ((0T) - f(OT.).
As conclusion, we have Σi=T |0,112 <
f(0r)-mine ((0) +
|0r11", An
which implies lim
|0,113 t-00
c
C OTHER RESULTS
Now rigorously analyze norm growth in this algorithm. This greatly extends previous analyses of effect of normalization schemes (Wu et al., 2018; Arora et al., 2018) for vanilla SGD. Theorem C.1. Under the update rule 1.2 with X O, the norm of scale invariant parameter 0, satisfies the following property:
Almost Monotone Increasing: ||0++1||2 ||011 2 - x+ (1) |0-1112).
Assuming 7) is a constant, then
10+111 Σ 1- (10; -0 0
11100-11-111111 0:113) +-1100++ 1 1- -+1
(110112-110-11
Proof. Let's use Re, Dr. C. to denote |0.112. |1 - 0, 0 (0.+1 0,) respectively.
The only property will use about loss is VoL, 0, 0.
Expanding the square of 0 1 I| = [1(0++ 0.) + 0, 2|2 we have
11 N -1
S(I) R1+1 R₂ = Dt + 2C,.
We also have
C₁
0.
01+1 0: 0
0, 0 x,0i)
7
(Di + CC--1) - -RR
F)t
T7-1
T7-1
namely,
11 > 0 P(():
C.
7Dr
7 O RRR
9t-1
17-1
Simplify
s((-11 5(0)
+ P(I),
we have
T--1
R++1 R
R₁
Rr
Dt
Dz-1 22, Rr-
+
(27)
7/t
17t
1)t
When d; =0 0. we have
Rut R
R
R
1
Dj
Di-1
2 x+
Ro - R-
4/8
7-
M/
110
1=0
Further if nn 17 is constant, have
(D,+> - 1 1-
R = Ro +
(Ro -R-1),
1-7
1 1-7
1=0
22

---

Published as a conference paper at ICLR 2020
95.0
0.5
TEXP
TEXP--
Alp Alp Maaderawnn
Reducing WD
92.5
Reducing WD
0.4
Test Accuracy
90.0
Angle between
0.3
87.5
0.2
85.0
0.1
82.5
150
200
300
#epochs
25
100 125
150
Figure 6: The orange line corresponds PreResNet32 trained with constant L.R and WD divided by 10 epoch and 120. The blue line is TEXP-- corresponding Step Decay schedule which divides LR by 10
epoch 80 and 120. They have similar trajectories and performances by a similar argument to Theorem 2.ee Theorem B.2 and its proof in Appendix B)
which covers the result without momentum in (Arora et al., 2019) special case:
R411 = Ro + Σ D3.
i=0
For general deep nets, we have the following result, suggesting that the square of the update are constant compared to the mean square of the norm. The constant mainly determined by 1,,, explaining why the usage of weight decay prevents the parameters converge in direction."
Theorem C.2. For SGD with constant LR 7, weight decay À and momentum 7 when the limits Rxx li + EiD ||w D=o limn - [ - w.ll exist, we have
2nd
Doc 1
R
Proof of Theorem C.2. Take average of Equation 27 over t. when the limits Roc
lim + - |w, Doo limy 7 + |1 w; exists, we have
1 1+ D20 22
D ADDITIONAL EXPERIMENTAL FIGURES
SCALE INVARIANCE IN MODERN NETWORK ARCHITECTURES
In this section, we will discuss how Normalization layers make the output of the network scale- invariant to parameters. Viewing a neural network as DAG, we give a sufficient condition for the scale invariance which could be checked easily by topological order, and apply this on sev- eral standard network architectures such as Fully Connected(FC) Networks, Plain CNN, ResNet(He et al., 201 6a), and PreResNet(He et al., 2016b). For simplicity, we restrict our discussions among networks with ReLU activation only. Throughout this section, we assume the linear layers and the bias after last normalization layer are fixed to its random initialization, which doesn't harm the performance of the network empirically(Hoffer et al., 2018b).
((Page) had similar argument for this phenomenon by connecting this the LARS(You et al., 2017), though it's rigorous in the way it deals with momentum and equilibrium of norm.
23

---

Published as a conference paper at ICLR 2020
E. NOTATIONS
Definition E.1 (Degree of Homogeneity). Suppose k is an integer and 0 is all the parameters of the network, then is said be homogeneous of degree k, k-homogeneous, if ve 0, f(cO) c² ((0). The output of f can be multi-dimensional. Specifically, scale invariance means degree of homogeneity is O.
Suppose the network only contains following modules, and we list the degree of homogeneity of these basic modules, given the degree of homogeneity of its input.
(I) Input
(L) Linear Layer, e.g. Convolutional Layer Fully Connected Layer
(B) Bias Layer(Adding Trainable Bias to the output of the previous layer)
(+) Addition Layer (adding the outputs of two layers with the same dimension")
(N) Normalization Layer without affine munsformation BN, GN, LN, IN etc.)
(NA) Normalization Layer with affine transformation
Module
B
NA X
Input
(x.X)
Output
x+1
X
Table 1: Table showing how degree of homogeneity of the output of basic modules depends the degree of homogeneity
input. For the row the Input. entry '-' means the input the network doesn't have any extra input, entry 'I' of Bias Layer means the input is 1 I-homogeneous then the output is 1- homogeneous. '(x, x)' for '+' means if the inputs of Addition Layer have the same degree of homogeneity, the output has the same degree of homogeneity. ReLU, Pooling( and other fixed linear maps) ignored because they keep the degree of homogeneity and can be omitted when creating the DAG in Theorem F.3.
Remark E.2. For the purpose of deciding the degree of homogeneity of a network, there's no difference among convolutional layers, fully connected layer and the diagonal linear layer in the affine transformation of Normalization layer, since they're re all linear and the degree of homogeneity increased by after applying them.
On the other hand, BN and IN has some benefit which GN and LN doesn't have, namely the bias term (per channel) immediately before BN IN has zero effect on the network output and thus can be removed. (See Figure 15)
We also demonstrate the homogeneity of the output of the modules via the following figures, which will be reused to later to define network architectures.
Theorem E.3. For a network only consisting of modules defined above and ReLU activation, can view it as Directed acyclic graph and check its scale invariance by the following algorithm.
Input DAG G EV translated from neural network; the module type of each node U. V.
for in topological order of G do Compute the degree of homogeneity of v using Table 1;
if v not homogeneous then return False;
if Vouptut is O-homogeneous then
return True;
else
return False.
Addition Layer(+) is mainly used in ResNet and other similar architectures. In this section, also use it alternative definition of Bias Layer(B). See Figure
24

---

Published as a conference paper at ICLR 2020
X
x
x+1
X
X
x
O
N
(a) Imput(1)
(b) Linear(L)
(c) Addition(+)
(d) Normalization(N)
O
1
L
1
1
B
1
1
(e) Bias(B)
(f) Alteraaivee Definition of Bias(B)
1
1
1
0
1
1
NA
N
L
B
(g) Normalization
with
(h) Definition of Normalization with Affine(NA)
Afline(NA)
Figure 7: Degree of homogeneity the output of basic modules given degree of homogeneity of the input.
25

---

Published as a conference paper at ICLR 2020
E.2 NETWORKS WITHOUT AFFINE TRANSFORMATION AND BIAS
We start with the simple cases where all bias term(including that of linear layer and normalization layer) and the scaling term of normalization layer are fixed to be 0 and element-wise respectively, which means the bias and the scaling could be dropped from the network structure. We empirically find this doesn't tt affect the performance of network a noticeable way. We will discuss the full case in the next subsection.
Plain CNN/FC networks:
See Figure 8.
I O O
1 LLLLB
L
N
O
L
1
N
O
L
1
N
0
Figure 8: Degree of homogeneity for all modules in vanilla CNNs/FC networks.
x Block Block
D-Block x X
0 N
D-Block
An example of the full network structure of ResNee/PreResNee represented by composite modules de- fined in Figure 10.11,13,14, where 'S' denotes the starting part of the network, 'Block' denotes normal block with residual link, 'D-Block' denotes the block with downsampling, and 'N' denotes the normalization layer defined previously. Integer z 10, 2} depends on the type network. details Figure 10,11,13,14.
Figure 9:
See Figure 10. To ensure the scaling invariance, add additional normalizaiton layer in the shortcut after downsampling. This implementation is sometimes used in practice and doesn't t affect the performance noticeable way.
ResNet:
1 PLIL
0
L
N
(a) The starting part of ResNet
1
0
1
0
L
N
N
0
(b) A block of ResNet
x+1
o
1
0
N
N
X
x+1
0
N
(c) A block of ResNet with downsampling Figure 10: Degree of homogeneity for all modules in ResNet without affine transformation in normalization layer. The last normalization layer is omitted.
26

---

Published as a conference paper at ICLR 2020
Preactivation ResNet: See Figure 11. Preactivation means to change the order between convolu- tional layer and normalization layer. For similar reason, we add an additional normalizaiton layer in the shortcut before downsampling.
O
O
1
N
L
(a) The starting part of PreResNet
0
1
0
1
N
N
L
1
(b) block of PreResNet
O
1
0
1
N
L
N
L
X
O
1
1
N
(c) A block of PreResNet with downsampling
Figure 11: Degree of homogeneity for all modules in ResNet without affine transformation in normalization layer. The last normalization layer is omitted.
27

---

Published as a conference paper at ICLR 2020
E.3 NETWORKS WITH AFFINE TRANSFORMATION TRANSFORMATION
Now we discuss the full case where the affine transformation part of normalizatiee layer is trainable. Due to the reason that the bias of linear layer (before BN) has gradient the bias term is usually dropped from network architecture in practice to save memory and accel- erate training( even with other normalization methods)(See PyTorch Implementation (Paszke al., 2017)). However, when LN or GN is used, and the bias term of linear layer is trainable, the network could be scale variant (See Figurt 15).
mentioned in E.2,
Plain CNN/FC networks:
See Figure 12.
1
1
2
1
2
0
NA
NA
N
Figure 12: Degree of Homogenenly for all modules in vanilla CNNs/FC Detworks.
ResNet: See Figure 13. To ensure the scaling invariance, we add additional normalizaiton layer the shortcut after Aerrsammpoo This inelimmmentttiionn is sometimes used in practice and doesn' affect the performance in noticeable way.
O
1
1
L
NA
(a) The starting part of ResNet
2
1
2
1
L
NA
NA
1
1
(b) A block of ResNet
x+1
1
2
1
NA
L
NA
X
x+ 1
A
1
1
NA
(c) A block of ResNet with downsampling nomogencity for all modules in ResNet with trainable affine transformation. The last
Figure 13: Degree of homogencity normalization layer omitted.
Preactivation ResNet: See Figure 14. Preactivation means change the order between convolu- tional layer and normalization layer. For similar reason, we add an additional normalizaiton layer in the shortcut before downsampling.
28

---

Published as a conference paper at ICLR 2020
O
1
2
NA
L
(a) The starting part of PreResNet
1
2
1
2
NA
L
NA
L
2
2
+
(b) A block of PreResNet
1
2
1
2
NA
L
NA
L
X
NA
1
L
2
+
2
(c) A block of PreResNet with downsampling
Figure 14: Degree of homogencity for all modules in PreResNet with trainable affine transformation. The last normalization layer is omitted.
O
1
1
0
1
1
2
F
B
N
B
B
N
Figure 15: The network can be not scale variant if the GN or IN is used and the bias of linear layer is trainable. The red 'F' means the Algorithm will return False here.
29


Reviews:
[{"review_id": "rklU4eINhr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "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 TO MY EARLIER REVIEW\n===========================\n\nThe authors improved the writing of the paper substantially relative to the first version they submitted, and fixed minor issues. I am changing my rating from \"Weak accept\" to \"Strong accept\". It is now a must-read paper for anyone doing research on deep learning. \n\n\n\nMY EARLIER REVIEW\n=================\n\nThis exciting and insightful paper presents theorems (and illustrating examples and experiments) describing an equivalence of commonly used learning rate schedules and weight decay settings with an exponentially increasing learning rate schedule and no weight decay, for neural networks with scale-invariant weights. Hence, the results apply to a large set of commonly employed settings. The paper contains an interesting example of a neural network for which gradient descent converges if with batch normalization as well as with L2 regularization, but not when both are used. \n\nFrom a theory viewpoint, the paper offers new insights into Batch normalization and other normalization schemes. From a practical viewpoint, the paper suggests a way to speed up hyper-parameter search, effectively allowing to consider learning rate and weight decay as one parameter. \n\nA small gripe: this paper is a bit rough around the edges, and reads a bit like a draft (see comments on details below). \n\n\nDetailed Comments / advice / questions\n==================================\n\n- It often takes a bit of searching to figure out what proof goes with what theorem / fact. I recommend to add to each occurrence of “Proof.” (before a proof) with a reference to the theorem or fact that is being proved, e.g. “Proof of Theorem 2.6”. \n\n- The authors state that theorem B2 applies to “general deep nets”. In this theorem, the limit R_\\infty could very well be zero (e.g. for networks with weights that are not scale-invariant), in which case the statement contains a division by zero. I wonder if the authors overlooked this or forgot to state an assumption in the theorem. Maybe I am missing something. Since this theorem does not appear to be critical to the main contributions of the paper, it may be easiest to remove the theorem if the division by zero is indeed a problem. \n\n\n- On page 6, if c_w(x) is independent of w, would c(x) be more suitable? \n\n- At the bottom of page 6, the authors state that “As a result, for any fixed learning rate, ||w_{t+1}|| ^4= …”. It appears that the authors get the expression for  ||w_{t+1}||^4 from the expression for ||w_{t+1}||^2 above (maybe by multiplying by ||w_{t+1}||^2?), but I don’t see how. Could the authors explain this? Maybe authors mixed up w_t and w_{t+1} by accident? \n\n- The authors claim to “constrict better Exponential learning rate schedules”. Since the authors only perform a limited evaluation of their proposed learning rate schedule on CIFAR10, I suggest qualifying this statement. \n\n- Theorem 1.1 does not introduce what \\tilde{\\gamma} is. It’s somewhat obvious, but I would state it nonetheless. \n\n- The authors state that “…the exponent trumps the effect of initial lr very fast, which serves as another explanation of the standard wisdom that initial lr is unimportant when training with BN”. I don’t think that this constitutes a full explanation without further argument. I am also wondering if “another” is appropriate here: I am not aware of any (other) mathematically precise explanations of why initial learning rates do not matter in this set-up. If the authors are, they should cite it. \n\n- The authors often forgot spaces before \\cite commands. If you are trying to avoid a line break before the \\cite command, you can use a tilde ~ , like this “Group Normalization~\\cite{somepaper}”. \n\n- Please introduce the abbreviation LR for “Learning Rate”, and always use the all-upper-case version (not “lr”). \n\n- Definition 1.2 has a broken \\cite . \n\n- Theorem 2.7 should introduce \\hat{eta}_t, but it doesn’t. \n\n- Appendix A.1 contains a broken sentence (“as a function of…”)\n\n- It’s odd that the proof for theorems B1 and B2 appear before theorems B1 and B2. I would restructure the appendices to improve this. \n\n- Theorem B2 contains a stray “when”, and “exists” should be “exist”\n\n- What the authors call “Proof of Theorem 2.4” in the appendix is really a proof of the rigorous version of Theorem 2.4 - Theorem 2.7! The proof should in my opinion be labeled “Proof of Theorem 2.7”\n\n- The typo “eventsequation” should be replaced with something like “the events from equations”\n\n- Replace the colloquialism “nets” with “networks”. \n\n- Replace “BatchNorm” with “Batch Normalization”\n\n- “COvariate” has casing issues\n\n- “Riemmanian” should be “Riemannian”\n\n- “BNhas” should be “BN has”\n\n- The paper’s title states that the results are for batch-normalized networks, while the analysis appears to be more generally for networks with scale-invariant weights, which as the authors point out can arise from mechanisms other than batch normalization. Have the authors considered changing the paper’s title to better capture what their work applies to? In terms of discoverability, the authors would do the community a service by titling the paper in such a way that it captures the set-up well. ", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "rJlhm_ETtH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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 to the review %%%\nThanks for your clarification and the revision - the paper looks good! With regards to your comment on accelerating hyper-parameter search, note that there are fairly subtle issues owing to the use of SGD - refer to a recent work of Ge et al \"The Step Decay Schedule: A Near Optimal, Geometrically Decaying Learning Rate Procedure For Least Squares\" (2019). \n%%%\n\nThe paper makes an interesting observation connecting the use of weight decay + normalization to training the same network (without regularization) using an exponentially increasing learning rate schedule, under an assumption of scale invariance that is satisfied by normalization techniques including batch norm, layer norm and other variants. An example is also provided where the joint use of batch norm and weight decay can lead to non-convergence to a global minimum whereas the use of one (without the other) converges to a global minimum - serving to indicate various interdependencies between the hyper-parameters that one needs to be careful about.\n\nWhile the connection of scale invariant models to novel schemes of learning rates is interesting (and novel), the paper will benefit quite a bit in its contributions through attempting a convergence analysis towards a stationary point even for solving a routine smooth non-convex stochastic optimization problem. Owing to the equivalence described in the paper, this enables us to understand the behavior of the combination of batch norm (or some scale invariance property) + weight decay + momentum (+ step decay of the learning rate), which, to my knowledge isn’t present in the literature of non-convex optimization. \n\nThe paper is reasonably written (the proof of the main claim is fairly easy to follow), but needs to be carefully read through because I see typos and ill-formed sentences that should be rectified - e.g. see point 3. in appendix A.1 - some facts about equation 4, missing citation in definition 1.2 amongst others. I went over the proof of the main result and this appears to be correct. Furthermore, I find the connections to other learning rates (such as the cosine learning rate) to be rather hard to understand/interpret, in the current shape of the paper.\n\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HkxH37tRFH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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 exciting and insightful paper presents theorems (and illustrating examples and experiments) describing an equivalence of commonly used learning rate schedules and weight decay settings with an exponentially increasing learning rate schedule and no weight decay, for neural networks with scale-invariant weights. Hence, the results apply to a large set of commonly employed settings. The paper contains an interesting example of a neural network for which gradient descent converges if with batch normalization as well as with L2 regularization, but not when both are used. \n\nFrom a theory viewpoint, the paper offers new insights into Batch normalization and other normalization schemes. From a practical viewpoint, the paper suggests a way to speed up hyper-parameter search, effectively allowing to consider learning rate and weight decay as one parameter. \n\nA small gripe: this paper is a bit rough around the edges, and reads a bit like a draft (see comments on details below). \n\n\nDetailed Comments / advice / questions\n==================================\n\n- It often takes a bit of searching to figure out what proof goes with what theorem / fact. I recommend to add to each occurrence of “Proof.” (before a proof) with a reference to the theorem or fact that is being proved, e.g. “Proof of Theorem 2.6”. \n\n- The authors state that theorem B2 applies to “general deep nets”. In this theorem, the limit R_\\infty could very well be zero (e.g. for networks with weights that are not scale-invariant), in which case the statement contains a division by zero. I wonder if the authors overlooked this or forgot to state an assumption in the theorem. Maybe I am missing something. Since this theorem does not appear to be critical to the main contributions of the paper, it may be easiest to remove the theorem if the division by zero is indeed a problem. \n\n\n- On page 6, if c_w(x) is independent of w, would c(x) be more suitable? \n\n- At the bottom of page 6, the authors state that “As a result, for any fixed learning rate, ||w_{t+1}|| ^4= …”. It appears that the authors get the expression for  ||w_{t+1}||^4 from the expression for ||w_{t+1}||^2 above (maybe by multiplying by ||w_{t+1}||^2?), but I don’t see how. Could the authors explain this? Maybe authors mixed up w_t and w_{t+1} by accident? \n\n- The authors claim to “constrict better Exponential learning rate schedules”. Since the authors only perform a limited evaluation of their proposed learning rate schedule on CIFAR10, I suggest qualifying this statement. \n\n- Theorem 1.1 does not introduce what \\tilde{\\gamma} is. It’s somewhat obvious, but I would state it nonetheless. \n\n- The authors state that “…the exponent trumps the effect of initial lr very fast, which serves as another explanation of the standard wisdom that initial lr is unimportant when training with BN”. I don’t think that this constitutes a full explanation without further argument. I am also wondering if “another” is appropriate here: I am not aware of any (other) mathematically precise explanations of why initial learning rates do not matter in this set-up. If the authors are, they should cite it. \n\n- The authors often forgot spaces before \\cite commands. If you are trying to avoid a line break before the \\cite command, you can use a tilde ~ , like this “Group Normalization~\\cite{somepaper}”. \n\n- Please introduce the abbreviation LR for “Learning Rate”, and always use the all-upper-case version (not “lr”). \n\n- Definition 1.2 has a broken \\cite . \n\n- Theorem 2.7 should introduce \\hat{eta}_t, but it doesn’t. \n\n- Appendix A.1 contains a broken sentence (“as a function of…”)\n\n- It’s odd that the proof for theorems B1 and B2 appear before theorems B1 and B2. I would restructure the appendices to improve this. \n\n- Theorem B2 contains a stray “when”, and “exists” should be “exist”\n\n- What the authors call “Proof of Theorem 2.4” in the appendix is really a proof of the rigorous version of Theorem 2.4 - Theorem 2.7! The proof should in my opinion be labeled “Proof of Theorem 2.7”\n\n- The typo “eventsequation” should be replaced with something like “the events from equations”\n\n- Replace the colloquialism “nets” with “networks”. \n\n- Replace “BatchNorm” with “Batch Normalization”\n\n- “COvariate” has casing issues\n\n- “Riemmanian” should be “Riemannian”\n\n- “BNhas” should be “BN has”\n\n- The paper’s title states that the results are for batch-normalized networks, while the analysis appears to be more generally for networks with scale-invariant weights, which as the authors point out can arise from mechanisms other than batch normalization. Have the authors considered changing the paper’s title to better capture what their work applies to? In terms of discoverability, the authors would do the community a service by titling the paper in such a way that it captures the set-up well. ", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "HJxfYraZsB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "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 work makes an interesting observation that it is possible to use exponentially growing learning rate schedule when training with neural networks with batch normalization. This paper provides both theoretical insights and empirical demonstration of this remarkable property. In detail, the authors prove that for stochastic gradient descent (SGD) with momentum, this exponential learning rate schedule is equivalent to constant learning rate + weight decay, for any scale invariant networks, including networks with Batch Normalization and other normalization methods. This paper also contains an interesting toy example where  gd converges when normalization or weight decay is used alone while not when normalization and weight decay are used together.\n\nPros:\n\n1. This paper gives new and important insight to the complex interplay between the tricks of network training, such as weight decay, normalization and momentum. The assumption and derivation are simple but the result is quite surprising. In classical optimization framework, it is common to keep the learning rate smaller than the 1/smoothness such that gd decreases the loss. However, the connection between exponential learning rate schedule and weight decay in common practice built by this paper suggests that the current neural net training recipe may be inherently non-smooth.\n\n2. The experiment of this paper also suggests that in practice (with normalization layer), learning rate and weight decay coefficient can be packed into a single parameter, which reduces the effort needed for hyper-parameter tuning.\n\nCons:\n\n1. Though it's obvious for the feedforward networks with normalization layers to be scale invariant, it's not the case for ResNet ( and the authors use this for experiment). And this needs to be clarified.\n2. The writing of the proofs should be imporved.\n\nTypos:\n\n1. Definition 1.2 broke citation\n2. Equation (1)  \\eta_t should be \\eta_{t-1}\n3. Some facts about Equation 4, incomplete sentence\n4 In thm B.2,R_\\infty might be 0. So the authors can just delete the last equation on page 12 and use the equation above as the statement of the lemma.\n5. In the first line of Equation (13), the appearance of ( \\beta * e^{1-\\beta} )^{ k/2 } seems to be a mistake\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: After the revision, the reviewers agree on acceptance of this paper.    Let's do it.
Decision: Accept (Spotlight)