Inductive Bias of Gradient Descent for Exponentially Weight Normalized Smooth Homogeneous Neural Nets
Authors: Depen Morwani
Harish Guruprasad Ramaswamy
Venue:  (2021)
Keywords: Deep Learning Theory
Weight Normalization
Inductive Bias
Gradient Descent

Abstract: We analyze the inductive bias of gradient descent for weight normalized smooth homogeneous neural nets, when trained on exponential or cross-entropy loss. Our analysis focuses on exponential weight normalization (EWN), which encourages weight updates along the radial direction. This paper shows that the gradient flow path with EWN is equivalent to gradient flow on standard networks with an adaptive learning rate, and hence causes the weights to be updated in a way that prefers asymptotic relative sparsity. These results can be extended to hold for gradient descent via an appropriate adaptive learning rate. The asymptotic convergence rate of the loss in this setting is given by $\Theta(\frac{1}{t(\log t)^2})$, and is independent of the depth of the network. We contrast these results with the inductive bias of standard weight normalization (SWN) and unnormalized architectures, and demonstrate their implications on synthetic data sets.Experimental results on simple data sets and architectures support our claim on sparse EWN solutions, even with SGD. This demonstrates its potential applications in learning prunable neural networks.

Under review as a conference paper at ICLR 2021
INDUCTIVE BIAS OF GRADIENT DESCENT FOR EXPO- NENTIALLY WEIGHT NORMALIZED SMOOTH HOMO- GENEOUS NEURAL NETS
Anonymous authors Paper under double-blind review
ABSTRACT
We analyze the inductive bias of gradient descent for weight normalized smooth homogeneous neural nets, when trained on exponential or cross-entropy loss. Our analysis focuses on exponential weight normalization (EWN), which encourages weight updates along the radial direction. This paper shows that the gradient flow path with EWN is equivalent to gradient flow on standard networks with an adap- tive learning rate, and hence causes the weights be updated in way that prefers asymptotic relative sparsity. These results can be extended to hold for gradient de- scent via an appropriate adaptive learning rate. The asymptotic convergence rate of the loss in this setting is given by O E(loggya ). and is independent of the depth of the network. We contrast these results with the inductive bias of standard weight normalization (SWN) and unnormalized architectures, and demonstrate their im- plications synthetic data sets. Experimental results on simple data sets and architectures support our claim on sparse EWN solutions, even with SGD. This demonstrates its potential applications in learning prunable neural networks.
INTRODUCTION
The prevailing hypothesis for explaining the generalization ability of deep neural nets, despite their ability fit even random labels (Zhang et al. 2017). that the optimisation/traniing algorithms such as gradient descent have a "bias' towards 'simple" solutions. This property is often called inductive bias, and has been an active research area over the past few years.
It has been shown that gradient descent does indeed seem to prefer 'simpler' solutions over more 'complex' solutions, where the notion complexity often problem/architecture specific. The predominant line of work typically shows that gradient descent prefers a least norm solution in some variant of the L2-norm. This is satisfying, as gradient descent over the parameters abides by the rules of L2 geometry, i.c. the weight vector moves along direction of steepest descent, with length measured using the Euclidean norm. However, there is nothing special about the Euclidean norm in the parameter space, and hence several other notions of 'length' and 'steepness' recent years, several alternative parameterizations the weight vector, such as Batch normalization and Weight normalization, have immense success and these do not seem respect La geometry in the 'weight space'. We pose the question of inductive bias of gradient descent for some of these parameterizations, and demonstrate interesting inductive biases. In particular, it can still be argued that gradient descent with these reparameterizations prefers simpler solutions, but the notion of complexity is different.
equally valid. In
1.1 CONTRIBUTIONS
The three main contributions of the paper are as follows.
We establish that the gradient flow path with exponential weight normalization is equal to the gradient flow path of unnormalized network using adaptive neuron depen- dent learning rate. This provides a crisp description of the difference between exponential weight normalized networks and unnormalized networks.

---

Under review as a conference paper at ICLR 2021
We establish the inductive bias of gradient descent standard weight normalized and exponentially weight normalized networks and show that exponential weight normalization is likely to lead to asymptotic sparsity in weights.
We provide tight asymptotic convergence rates for exponentially weight normalized net- works.
RELATED WORK
2.1 INDUCTIVE BIAS
Soudry et (2018) showed that gradient descent(GD) on the logistic loss with linearly separable data converges to the L2 maximum margin solution for almost all datasets. These results were ex- tended to loss funetions with super-polynomial tails in Nacson et al. (2019b). Nacson al. (2019c) extended these results to hold for stochastic gradient (SG)) and Gunasekar et al. 2018a) extended the results for other optimization geometries. Ji & Telgarsky (2019b) provided tight con- vergence bounds in terms of dataset size as well as training time. Ji & Telgarsky (2019a) provide similar results when the data is not linearly separable.
Ji & Telgarsky (209c) showed that for deep linear nets, under certain conditions on the initial- ization, for almost all linearly separable datasets, the network, in function space, converges to the maximum margin solution. Gunasekar et al.) (2188) established that for linear convolutional nets, under certain assumptions regarding convergence of gradients etc, the function converges to a KKT point of the maximum margin problem in fourier space. Nacson et al. (2019a) shows that for smooth homogeneous nets, the network converges to KKT point of the maximum margin problem in pa- rameter space. Lyu & Li (2020) established these results with weaker assumptions and also provide asymptotic convergence rates for the loss. Chizat & Bach (2020) explore the inductive bias for 2-layer infinitely wide ReLU neural net in function space and show that the function learnt max- max-margin classifier for variation norm.
2.2 NORMALIZATION
Salimans & Kingma 2016) introduced weight normalization and demonstrated that it replicates the convergence speedup of BatchNorm. Similarly, other normalization techniques have been proposed as wBll(Ba al., 2 Qiao et al., 22i al.) 2019).. but only few have been theoretically explored. Santurkar et al. (2018) demonstrated that batch normalization makes the loss surface smoother and L normalization in batchnorm can even be replaced by L₁ and L normalizations. Kohler et al. (2019) showed that for GD, batchnorm speeds up convergence in the case of GLM by splitting the optimization problem into learning the direction and the norm. [Cai et al. (2019) analyzed GD on BN for squared loss and showed that it converges for wide range of Ir. Bjorck al. (20T8) showed that the primary reason BN allows networks to achieve higher accuracy is by enabling higher learning rates. Arora al. (2019) showed that in case of GD SGD with batchnorm, Ir for scale-invariant parameters does not affect the convergence rate towards stationary points. Du et al. (2018) showed that for GD one- one-hidden-llyer weight normalized CNN, with constant probability over initialization, iterates converge to global minima. QQao et al. (2019) com- pared different normalization techniques from the perspective of whether they lead to points, where neurons are consistently deactivated. Wu et al. (2019) established the inductive bias of gradient flow with weight normalization for overparameterized least squares and showed that for a wider range of initializations as compared to normal parameterization, it converges to the minimum Le norm solution. Dukler al. (2020) analyzed weight normalization for multilayer ReLU width regime and showed that it may speedup convergence. Some other papers(L.ug et al. 2019 Roburin et al.) 2020) also provide other perspectives to think about normalization techniques.
the infinite
3 PROBLEM SETUP
We use standard view of neural networks collection of nodes/neurons grouped by layers. Each node u is associated with a weight vector w.. that represents the incoming weight vector for that node. In case of CNNs, weights can be shared across different nodes. represents all
2

---

Under review as a conference paper at ICLR 2021
25
7.5
5.0
10
30
25
13.0
(a) EWN
(b) SWN
(c) Unnorm
Figure 1: L2 neighborhoods with e 0.5 radius in parameter space for different parameterizations. For EWN in the left (resp. SWN in the middle) the parameter (y. v) (the parameter [a, v) resp.) is restricted 3-d ball of radius and the values that the 2-d weight vector w takes is illustrated for 6 different centers.
the parameters of the network arranged in form of vector. The dataset is represented in terms of (x,, y:) pairs and m represents the number of points in the dataset. The function represented by the neural network is denoted by ((w,-). The loss for single data point is given by ((vi, &(w, x;)) and the loss vector represented by l. The overall loss is represented by [(w) and is given by L( ((w):
Σ i=1
((y,, ((w. x,)). We sometimes abbreviate L( (()) as L when the context is clear.
In standard weight normalisation (SWN), each weight vector w. reparameterized as 7/u [v.] This was proposed by Salimaans & Kingma (2016), as substitute for Batch Normalization and has been practically used in multiple papers such (Sokolic et al. (2017), Dauphin al. (2017). Kim et al. 2018) and Hieber et al. (2018). The corresponding update equations for gradient descent are given by
7a(t + 1) = 7u(t) 11)) Vt(() W..
(t(t)
(I- V.-vv(Vv. Iv)
V. (t + - v. -n(()
Vww..
(2)
(t)ll
In exponential weight normalisation (EWN), each weight vector wa reparameterized as e This was mentioned in Salimans & Kingma (2016), but to the best of our knowledge, has not been widely used. The corresponding update equations for gradient descent with learning rate r7(1) given by
V.
T
O,,(1 + 1) = at,(1) am(()))()) vu(l) V..
(3)
[|v
(1-
(au(t)
va + v. (tt) v.ll
Ww.f
The update equations for gradient flow are the continuous counterparts for the same. In case of gradient flow, for both SWN and EWN, we assume (0)l = 1. to simplify the update equations.
INDUCTIVE BIAS OF WEIGHT NORMALIZATION
In this section, state our main results for weight normalized smooth homogeneous models exponential loss(E(y; ((w,x))
(w.,))).) The results for cross-entropy loss and proofs have been deferred to the appendix due to space constraints. First, we state the main proposition that helps in establishing these results for EWN.
Theorem 1. The gradient flow path with learning rate ( EWN and SWN are given as follows:
dw,(!)
EWN:
(1) (t))l/
(5)
dt
dw. (n())([w,, L+ (1---111111)
(1-] [w,(()))
SWN:
(w.(t) TV Cww,()
(6)
dt
3

---

0 holds for Under review as a conference paper at ICLR 2021
Thus, the gradient flow path of EWN be replicated by adaptive learning rate given by n(t)]l on unnormalized network(Unnom), These parameterizations also induce different neighborhoods in the parameter space, that have been shown in Figure
4.1 ASSUMPTIONS
The assumptions in the paper can be broadly divided into loss function/architecture based assump- tions and trajectory based assumptions. The loss functions/arcciiecctrre based assumptions are shared across both gradient flow and gradient descent.
Loss function/Arrciitecture based assumptions
(yi, xw), = (....(
((, x) is C² function, for a fixed x (Aw,, x) = (w, x). for some and L
Gradient flow. For gradient flow, make the following trajectory based assumptions (A1) lim;-+o0 L(w (t))
(A3) lime-ooo ((w(t)) L [BM
(A2) lime-+oo w(t)
[w]
(A4) Let p min, y (w, x.). Then 0.
The first assumption is typically satisfied scenarios where a positively homogeneous network achieves 100% training accuracy. This is not a completely unreasonable assumption, given recent papers demonstrating neural networks with sufficient overparameterization can fit even random la- bels(Zhang et al. (0177), Jacot et al. (2018)), and is standard assumption made when the purpose to find the inductive bias. The second assumption states that the network converges in direction and this has been recently shown in Ji & Telgarsky (2020) hold for gradient flow homoge- neous neural nets without normalization under some regularity assumptions. The third and fourth assumptions are required to show convergence of the gradients in direction. The fourth assumption is indeed true for SWN as shown in Lyu & Li (2020)
Gradient Descent. For gradient descent, we also require the learning rate 17(1) not grow too fast.
(A5) lim (w. = 0 for all in the network Proposition Under assumptions (AI)-(A4), lim,-soe n/tt]] (t)))(..()))) (t) every u in the network with ntt = O (z)) where c <
This proposition establishes that the assumption (A5) is mild and holds for constant 17(),, that is generally used in practice.
While some of these assumptions are non-standard we believe they do generally hold, and demon- strate the viability of these assumptions toy experiment which we call Lin- Sep. In this ex- periment 2-layered EWN neural network, with 8 neurons in the hidden layer and a ReLU-squared activation function, trained on linearly separable dataset. The learning rate schedule used was O goor and the network was trained till a loss of e -300 The corresponding graphs for EWN are Similar results for SWN have been deferred to Figure 8
shown in Figure 2
in the appendix.
4.2 EFFECT OF NORMALISATION ON WEIGHT AND GRADIENT NORMS
This section contains the main theorems and the difference between EWN and SWN that makes EWN asymptotically relatively sparse as compared to SWN. First, we will state a common proposi- tion for both SWN and EWN.
Proposition 2. Under assumptions (AI)-(A4) ( for gradient flow and (AI)-(A5) gradient descent, for both SWN and EWN, the following hold:
(i) lim (.C(((() E(w(T = E E. x,) = where p >
'Homogenoous networks in the w space are also homogeneous in the 7, v space. Therefore results regard- ing convergence rates and monotonic margin hold from Lyu & I.j (2020). However, the results for convergence KKT point of the max margin problem do not hold. For details, refer Appendix
4

---

Under review as a conference paper at ICLR 2021
]|wll
1
]|
I|all
[|wlll
[[
5.0
[wsll
[wlll
||
[|wall
class -1
class
Steps
(a) Dataset
(b) Evolution of |wull
25
Normalized Margin
0.20
0.25
-9.
0.2
Steps
Staps
Steps
Weight convergence
(d) Loss convergence
(e) Normalized parameter margin
Figure 2: Verification of assumptions for EWN in Lin-Sep experiment: (a) shows the dataset. In (b), it can be seen that only weights 5,7 and keep on growing in norm. So, only for these, ||wlll > 0. (c) shows the components of the unit vector ww] only for the weights 5, and 8 as they keep evolving with time. Eventually their contribution to the unit vector become constant. (d) shows the components of the loss vector and they also become constant eventually. (c) shows the normalized parameter margin converging value greater than 0.
(ii) Let W. lim
(..() [w(]]]]
-we, -vn, C(w(r) Then, W. Ag. for some and gu. +om I [ww(Ti]
A 2 0
The first and second part state that under the given assumptions, for both SWN and EWN, gradients converge in direction and the weights that contribute to the final direction of w, converge opposite direction of the gradients. Now, we provide the main theorem that distinguishes SWN and EWN.
Theorem 2. Under assumptions (AI) (AA4) for gradient flow and (AI)-(A5) for gradient descent, the following hold
(i) for EWN, |Wall 0.
lim
[w. [t)]l (ww()))
W. 2
[.]]]
2 (w]]
|
K
(ii) for SWN, w.
lime
[.. V.,, ((w())
[...
K-1l
w. ww
((w(1)]
w.
Thus, asymptotically, for EWN, (()l IV [w((T)] while for SWN, (W)l (V) w., (ww())ll, where (t) and (2) are independent of the neuron We demonstrate this property EWN on the Lin-Sep Sep experiment in Figure The results for SWN have been deferred to Figure in the Appendix.
ky (t)
Now, we provide a corollary for case of multilayer linear nets.
Corollary 1. Consider weight normalized(SWW) or EWN) multilayer linear net, represented by
y W, Wn-1...W1z Under assumptions (AI)-(A4) for gradient flow and (AI)-(A5) for gradient descent, if the dataset is sampled from continuous distribution w.E. Bd. then, with probability
0 = W, W, ...... converges in direction to the maximum margin separator for all linearly separable datasets.
5

---

Under review as a conference paper at ICLR 2021
-0.4
W5
Cosine b/w Va.. and g
Cosine b/w Wo and V
-0.4
W
Ws
-0.8
-0.8
-1.0
-1.0
200
400
600
200
400
600
Steps
Steps
(a)
(h)
-2374
-190
Ag
log [12 c11
-25.2
-2660
[|P
-190
x+yy- 100.00
-231.
226-32
-
-2822
-1864
24
15
1.8 log [ed]
2.
1.6
1.
2.5
22
1.
1.8
235
22
log [w/]]
log [eul
(c)
Figure 3: Demonstration of Results for EWN in Lin-Sep experiment: (a) demonstrates part of Proposition [ where g approximated by using w from the last point of the trajectory. Clearly, V.., C stops oscillating and converges to g. (b) demonstrates part 2 of Proposition 2 and shows that for weight vectors 5,7 and 8, w. (t) converges in opposite direction of V ww, ((w[)), (c), (d) and (e) demonstrate Theorem 2 for EWN, where for weight vectors 5,7 and 8. The three graphs are plotted loss values of -00 250 and -300 respectively. At each loss value, for the 3 weights,
log |wull log W.., C| is approximately same.
4.3 SPARSITY INDUCTIVE BIAS FOR EXPONENTIAL WEIGHT NORMALISATIONN
The inverse relation between (t)l and WV., [tw(t))] in the EWN trajectory results in an interesting inductive bias that favours movement along sparse directions.
Proposition 3. Let assumptions (A (A1)-(A5) be satisfied. Consider two nodes u and v in the network [@
such that |@ | > O and [[w,(t)ll, [t)ll)]l co. Let
be denoted by Let c, be lig.ll
such that E e and 0 < < 2x. Then, the following holds:
1. There exists time l, such that for all 1 >> L1 both SWN and EWN trajectories have the following properties:
(a)
Vw. ((w(t))
[c cc
Ww ((w()))
(b)
(t)
V ((w(+))
2 coss()
[wll
V we ((w(1))]]
(c)
wa(t)
((w(t))
2 cos(o).
[W][
IV LIw(ONT
2. for SWN, lime-so0
[w)]( (1)ll
=
3. for EWN, if as some time t2 > tı.
(a) [wa(t))]
lim [w]]
[tw][
(e-r) cos(())
[[]]
0c
(b) [[,]]
[t2]]
cos(6)
lim lim
[w.(C]
c+f
[[]]

---

Under review as a conference paper at ICLR 2021
50
EWN Unnorm
W1
40
30
y
W22
(a) Network Architecture
10
30
(h) Weight trajectories
Figure 4: (a) Network architecture for the Simple-Trel experiment (b) Trajectories of the two weights for EWN and Unnorm, starting from 5 different initialization points.
diasa
-2
(a) Dataset
(b) EWN
(c) Unnorm
Figure 5: (a) Training data for the XOR experiment. (b, c) Norm of the incoming neuron weights for the EWN and unnormalized architectures.
The above proposition shows that the limit property of the weights in Theorem w an unstable convergent direction for EWN. But that is not the case for SWN. We demonstrate the relative sparsity between EWN, SWN and Unnorm through two toy experiments Simple-Tra and XOR.
2 makes non-sparse
In the Simple-Trel experiment, have single data point at (2, 1), that is labelled positive and train a network with linear activations. The architecture is shown in Figure 4a where weights in blue and red are frozen to values and respectively. Thus, there are effectively only two scalar parameters- and W2. The network is trained till a loss value of e 50 starting from different initialization points. The weight trajectories Figure 4b shows that EWN prefers to converge either along the x or axis, and hence has an asymptotic relative sparsity property.
In the XOR experiment, we train 2-layer ReLU network, with 20 hidden neurons on XOR dataset(shown in Figure Sa). The second layer is fixed to the values or -1 randomly. For at- taining 100% accuracy on this dataset with this architecture, least hidden units are needed. can be seen in Figure 5 EWN asymptotically uses exactly 4 neurons out of 20, while Unnorm uses all the 20 neurons. The results for SWN have been deferred to Figure 10 in the appendix.
CONVERGENCE RATES
Under Assumption (A2), be represented 9() r()), where lim 0(
[(1)]
0.
Let N RR, given by d(t) Σt= ((() denote total step size.

---

Under review as a conference paper at ICLR 2021
byyer 4layer
layer
Train Lozs
Train
2000
4002
2000
4100
2300
4002
Steps
Steps
Steps
(a) EWN
(b) SWN
(c) Unnorm
Figure 6: Variation of convergence rate of train loss with number of layers for multilayer linear nets
The asymplotic convergence rate of loss for SWN and Unnorm have already been established in Lyu
& Li (020)) as θ d(t)(logd(t)) For EWN, the corresponding theorem is provided below
Theorem 3. For EWN, under Assumptions (A1)-A5) and lime- hold
[[(++1] -r(t)l 0, the following ((+1) 9())
1. [[w(t)] asymptotically grows O ((oo(((())
2. [(w(t) asymptotically goes down at the rate o a(t) d(t))
For multilayer linear nets, the variation of convergence rate with number of layers for a linearly sep- arable dataset is illustrated in Figure All these networks were explicitly initialized to represent the same point in function space. can be seen that EWN, SWN and unnormalized networks all converge faster with more layers, but the effect is much less pronounced for EWN.
MNIST PRUNING EXPERIMENTS
As EWN leads asymptotically sparse solutions, it is likely that a sufficiently trained EWN net- work would be comparatively robust to pruning. In this section, we compare the pruming efficacy of EWN, SWN and Unnorm on a 2-layer ReLU network trained on the MNIST dataset. In case of EWN and SWN, only the first layer is weight normalized as only this layer needs to be pruned. The pruning criterion used that grow the least in norm are pruned first. The corresponding pruning graphs at different loss values are shown in Figure 7 can be seen that when the loss levels are sufficiently low, the EWN network becomes better adapted for pruning, significantly outperforming SWN and the unnormal- ized network terms test accuracy for a given level of pruning. The variation norm of the weight vectors with gradient descent steps for neurons in the first layer has been deferred to Figure il in the appendix.
difference between the initial and final weight norm, i.e, the weights
CONCLUSION
In this paper, we analyze the inductive bias of weight normalization for smooth homogeneous neural nets and show that exponential weight normalization is likely to lead to asymptotically sparse solu- tions and has faster convergence rate than unnormalized or standard weight normalized networks.
REFERENCES
Sanjeev Arora, Zhiyuan Li, and Kaifeng Lyu. Theoretical analysis of auto rate-tuning by batch normalization. In International Conference on Learning Representations, 2019. URL https:
/ooeenreveww net cesss/fooumiide rkx nA9FX
Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hinton. Layer normalization. arXiv preprint arXiv: 1607:0060.6400 2016.
8

---

Under review as a conference paper at ICLR 2021
1.0
1.0
0.9
Test Accuracy
Test Accuracy
0.9
0.7
0.6
Unnorm
0.7
Unnorm
EWN
EWN
SWN
5WN
0.5
20
40
80
20
40
60
Percentage of neurons pruned
Percentage of neurons pruned
(a) 10
(b) L -300
Figure 7: Variation of test accuracy vs percentage of neurons pruned in first layer at different loss values for MNIST experiment
Nils Bjorek, Carla Gomes, Bart Selman, and Kilian Q Weinberger. Understanding batch normalization. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa- Bianchi, and R. Garnett (ods.), Advances in Neural Information Processing Systems 31, pp. 7694-7705. Curran Associates, Inc., 2018. URL http: http://ppapers cttp://paappaaiss..ccc.cccccccce www.. #396-underttanddnngbaacecc
Yongqiang Cai, Qianxiao Li, and Zuowei Shen. A quantitative analysis of the effect of batch normal- ization on gradient descent. volume 97 of Proceedings of Machine Learning Research, pp. 882 890, Long Beach, California, USA, 09-15 Jun 2019. PMLR. URL BtLhttp: httttp://proceedngs.. mlr pptsss/99/caa1l.
html
Lénaïc Chizat and Francis Bach. Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss. volume 125 of Proceedings of Machine Learning Research, pp.
PMLR, 09-12 Jul 2020. URL http: http::///oceeeeing..... mlr press/v125/
chizat20a.
Yann N. Dauphin, Angela Fan, Michael Auli, and David Grangier. Language modeling with gated convolutional networks. volume 70 of Proceedings of Machine Learning Research, pp. 933- 941, International Convention Centre, Sydney, Australia, 06-11 Aug 2017. PMLR. URL
Simon Du, Jason Lee, Yuandong Tian, Aarti Singh, and Barnabas Poczos. Gradient descent learns one-hidden- CNN: Don't be afraid of spurious local minima. volume 80 of Proceedings of Machine Learning Research, pp. 1349-1348, Stockholmsmässsan Stockholm Sweden, 10-15 2018. PMLR. WRRL/tttp///rooceeeiei
mir. press/v80/dns dul html
Yonatan Dukler, Quanquan Gu, and Guido Montúfar. Optimization theory for relu neural networks trained with normalization layers. International Conference on Machine Learning. 2020.
Suriya Gunasckar, Jason Lec, Daniel Soudry, and Nathan Srebro. Characterizing implicit bias in
terms of optimization geometry. volume 80 of Proceedings of Machine Learning Research, pp- 1832-1841, Stockholmsmässan Stockholm Sweden, 10-15 Jul 2018a. PMLR. URL http: / //proceedings..o mlr. htt.:eedddnnn......rpesess/esses press/v80 wwwas//unneeaaaaa...mm html
Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nati Srebro. Implicit bias of gradient descent on linear convolutional networks. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa- Dasa-Bianchi, and R. Gareett (eds.), Advances in Newral Information Processing Systems 31, pp. Curran Associates, Inc., 2018b. URL htthtttp:/ppapzaa nips cc cct wtwpp/ppppppppcppcccoocccc....a 8156- 196-implicit. bias of -iatt--i--ii------e--n------ - on www.--iiearr pdf

---

Under review as a conference paper at ICLR 2021
Felix Hieber, Tobias Domhan, Michael Denkowski, David Vilar, Artem Sokolov, Ann Clifton, and Matt Post. Sockeye: A toolkit for neural machine translation, 2018.
Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural tangent kemel: Convergence and generalization neural networks. In S. Bengio, H. Wallach, H. Larochelle, Grauman, N. Cesa-Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems 31, pp. 857 8571-8580. Curran Associates, Inc., 2018. URL http: /ttp:::/pppppeaaeee nips. pww.. cc/paper/ 8076 tanga-- ortpraaaaaaaaaaaaaaaaao-o--eoeea and aaa.eeeeeeaaeeeeeeeaaaaaaaaa htt.aa/awwaaaaaaoaoao..ooooaaaaa -ew.-oo-----eeeeeeeeeeeeeeeee- pdf
Ziwei Ji and Matus Telgarsky. The implicit bias of gradient descent on nonseparable data. volume 99 of Proceedings of Machine Learning Research, pp. 1772-1798, Phoenix, USA, 25-28 Jun 2019a. PMLR.
mww.rirr.m.mm www.mmrr.pp.... presa /v99 /illa..1..... html
Ziwei Ji and Matus Telgarsky. refined primal-dual analysis of the implicit bias. 2019b.
Ziwei Ji and Matus Telgarsky. Gradient descent aligns the layers of deep linear networks. In International Conference on Learning Representations, 2019c. URLhttps: ptntttps://opereevieee
net//foumm? d= 1333ggg q30
Ziwei Ji and Matus Telgarsky. Directional convergence and alignment in deep learning. arXiv preprint arXiv:2006.0660 2020.
Jin-Hwa Kim, Jaehyun Jun, and Byoung-Tas Zhang. Bilinear attention networks. In S. Ben- Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (eds.), Ad-
gio, H. Wallach, vances in Neural Information Processing Systems, volume 31, pp. 1564-1574. Curran Asso- ciates, Inc., 2018. URL http:::::///t..tt.tttttt httttpp::/ppooceddggsss.. newraiinnnnnnnuineaeeeeeeeeeee neurips cacpppscc/ppppee cc//papperr/111//11l)
pdf
Jonas Kohler, Hadi Daneshmand, Aurelien Lucchi, Thomas Hofmann, Ming Zhou, and Klaus Neymeyr. Exponential convergence rates for batch normalization: The power of length-direction decoupling in non-convex optimization. volume 89 of Proceedings of Machine Learning Re- search, pp. 805-815. PMLR, 16-18 Apr 2019. URL/tttp::/pzzceeeinng mlr. press/
v89/kohler1s html
Boyi Li, Felix Wu, Kilian Q Weinberger, and Serge Belongie. Positional normalization. In H. Wal- lach, H. Larochelle, A. Beygelzimer, d'Alché Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems 32, pp. 1622-1634. Curran Associates, Inc., 2019. URL 8440 pospppssnaaaoe www.aliiatiiiiioo pd..f
Ping Luo, Xinjiang Wang, Wenqi Shao, and Zhanglin Peng. Towards understanding regularization in batch normalization. In International Conference on Learning Representations, 2019. URL
net wtt.:ete//oooummii--0-1111
Kaifeng Lyu and Jian Li. Gradient descent maximizes the margin of homogeneous neural net- works. In International Conference on Learning Representations, 2020. URL https://
openreview wwt. mett/forummiiii wtw.oormni.dSSeeegee....
M. Muresan. A Concrete Approach to Classical Analysis. CMS Books Mathematics, Springer New York, 2015. ISBN 9780387789330. URL petttps:/bbokss. https/////ooossppgl.....oo.... www.gllo....../oooo..
1d=:8rBBgtuu Iu_
Mor Shpigel Nacson, Suriya Gunasekar, Jason Lee, Nathan Srebro, and Daniel Soudry. Lex- icographic and depth-sensitive margins in homogeneous and non-homogeneous deep models. volume 97 of Proceedings of Machine Learning Research, pp. 4683 4692, Long Beach, Cali- fornia, USA, 09-15 Jun 2019a. PMLR. URL http::ttpp/ppe htttt:://proceedinga. ml wtt.mmlr.pprss. r.press/v97/ nacsoni 9a htm
Mor Shpigel Nacson, Jason Lee, Suriya Gunasekar, Pedro Henrique Pamplona Savarese, Nathan Srebro, and Daniel Soudry. Convergence of gradient descent separable data. volume 89 of Proceedings of Machine Learning Research, pp. 3420-34222 PMLR, 16-18 Apr 2019b. URL http://proceedi ngs. wtwpsngg.........///./e.eee.s.ee / csoni html
10

---

Under review as a conference paper at ICLR 2021
Mor Shpigel Nacson, Nathan Srebro, and Daniel Soudry. Stochastic gradient descent separable data: Exact convergence with a fixed learning rate. volume 89 Proceedings of Machine Learn ing Research, pp. 3051-3059. PMLR, 16-18 Apr 2019c. URL / .mlr...sss........mmmm.m.......m
peaas/v89/nacee 19a. html
Siyuan Qiao, Huiyu Wang, Chenxi Liu, Wei Shen, and Alan Yuille. Rethinking normalization and elimination singularity in neural networks. arXiv preprint arXiv: 2019.
Siyuan Qiao, Huiyu Wang, Chenxi Liu, Wei Shen, and Alan Yuille. Micro-batch training with batch-channel normalization and weight standardization, 2020.
Simon Roburin, Yann de Mont-Marin, Andrei Bursuc, Renaud Marlet, Patrick Pérez, and Mathieu Aubry. Spherical perspective on learning with batch norm. arXiv preprint arXiv:2006, 13382. 2020.
Tim Salimans and Durk Kingma. Weight normalization: A simple reparameterization to accelerate training of deep neural networks. In D. D. Lee, M. Sugiyama, U. V. Luxburg, Guyon, and R. Garnett (eds.), Advances in Neural Information Processing Systems 29, wwtp://wrrrrpp...ccc...pppp
pp. 901-909. Curran Associates, Inc., 2016. URL
pdf
Shibani Santurkar, Dimitris Tsipras, Andrew Ilyas, and Aleksander Madry. How does batch normalization help optimization? In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchh and R. Gameett (eds.), Advances in Newral Information Processing Systems 31, pp. 2483-2493. Curran Associates, Inc., 2018. URL httt:://papeeee nips..nnppp..............m...... cc/paper/ 7515 how does
phelpoopiimizaiion..
Jure Sokolic, Raja Giryes, Guillermo Sapiro, and Miguel R. D. Rodrigues. Robust large margin deep neural networks. IEEE Transactions on Signal Processing, 65(16)4225-42288 Aug 2017. ISSN 1941-0476. doi: 10.1 n..11099sp.2217.770000 URL http:tt//........rrr//////// TSP 201.7.20000333
Daniel Soudry, Elad Hoffer, and Nathan Srebro. The implicit bias of gradient descent sep- arable data. In International Conference on Learning Representations, 2018. URL https:
//openreview. net. www.://ootm.ddrriieo....
Xiaoxia Wu, Edgar Dobriban, Tongzheng Ren, Shanshan Wu, Zhiyuan Li, Suriya Gunasekar, Rachel Ward, and Qiang Liu. Implicit regularization of normalization methods. arXiv preprint arXiv:1911.07956. 2019.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. International Conference on Learning Rep- resentations, 2017. URL petttss://openrevieee httpeeewwwweeeetteeeeeeeennesess
A PROOF OF THEOREM
Theorem. The gradient flow path with learning rate ry(t), for EWN and SWN are given as follows:
EWN: dww((t)
dt. (())))
SWN: dw.((t) -(00 (1 (1- ( Vw.
dl
The proof for the two parts will be provided in different subsections, where the corresponding part will be restated for ease of the reader.
11

---

Under review as a conference paper at ICLR 2021
A.1 EXPONENTIAL WEIGHT NORMALIZATION
Theorem. The gradient flow path with learning rate rT(1), for EWN is given by:
dwu(t) =
Proof. In case of EWN, weights reparameterized Wa 60
||vil|
Then
V w. L
V aa
== c0
V|val
V.
vv [
V
Vw.. C
||v
Now, in case of gradient flow with learning rate (t)), say
da,(t) Co, ( Vu(t) V... L [V
dv vr, eau(t)
(u(t)va(t)
[vx(t)] [tv(
Vw., &
dt
Now, using these equations, we can say d| (t) 2V) dt
(dxaat
(dvu(t)
dt
Thus, (t)]l does not change with time. As assumed ||vu(0)] to be 1, therefore for any [[) = Using this simplification, we can write
(t.(t) d(caa((vv,,t)) dt (- (t)e (0. (v. C)v
dt
(f)v) = =
Thus, the gradient flow path with exponential weight normalization can be replicated by an adaptive learning rate given by nttt] (t)l
A.2 STANDARD WEIGHT NORMALIZATION
Theorem. The gradient flow path with learning rute 17(1) for SWN given by:
dw,(t) = -000000 (+ [|
[Iw(())13))
(V (),,(()
Proof. In case of SWN, weights are reparameterized W. Ta [v.l Then
7. L v. V.V...
Vv,C=
Yu
(1
|| 12 Vw..C C
Vuv.
v
Now, in case of gradient flow with learning rate it))), we can say
(t) =- -)() (t) W.
dv
%a(t) (t(t)va(()
()t vv. -n((t)
[v,( [1v( Ww C
dt
12

---

Under review as a conference paper at ICLR 2021
does not change with time. Using the fact that [|vu(t)]] 1 for all Now, similar to EWN, [t)v t, we can say
dw.(l) dt
d(Tu(()v(())
di
-1l00(-n(00a(0000-vvv (v) [w..
= =-n(0(n(()²' w.. L+ (1- Vw.
(1 (1-7u(01) (1)3
= -nt())a((t) V w. C+
(wu(t) V (w..)
7u(2)
Replacing To (t) by [t)]l gives the required expression.
B PROOF OF PROPOSITION
Proposition. Under assumptions (A1)-(A4), lim ( ((w(t)) holds for every u in the network with r)t) = O (e), where c <<
Proof. Under assumption (A1) and (A2), w can be represented as w g(t + r(t), where 0. Now, for exponential loss,
lim (())
[r(]]]
V Vw Σ Vw
4 ( = -0(1)
ritl
mtes
r(t)
V (w = gtt) 1- - V f + g(t)
xx))
From assumption (A4), we know d w. x,) 2 for all i. Now, using Euler's homogeneous theorem, can say
V x, 4 W x;)
Thus, V/ > 0 for all i. Now, using the equations above and assumption (A3), we can say
lim 1-000
ki
c- g(t) Σ Lu D x;)
where kn some constant. Now, 17(1)) = Ol ((( where e < 1, then using the fact that L goes down at the rate of e = and || goes up at the rate of g(t), we can say
ki (() W
lim ((0))/((0)ll<<<<((()))) lim 1-000
t-000
((w(t))
k = PPo()' g(1)--111 11th Eeu V (W,
lim
t-000
L(w(t))
C PROOF OF PROPOSITION 2
Proposition. Under assumptions (AI)-(A4) for gradient flow and (A1)-(A5) for gradient descent, for both SWN and EWN, the following hold:
(i) lim ((w()) [(w((
=
E.v. V (.W.).).))))))).).....)))))) = where μ 0.
(ii) Let W. lim
(t. X > 0 Tw(T
and g..
lim
-w., C(w(t)) Then, W. Ag.. for some TV
13

---

1. Under review as a conference paper at ICLR 2021
The proof for different cases will be split into different subsections and corresponding proposition will be stated there for ease of the reader. The proof will depend on the Stolz Cesaro thcorem(stated in Appendix D Integral Form of Stolz-Cesaro Theorem(stated and proved in Appendix P and fol- lowing lemmas that have been proved in Appendix [
Lemma 1.
Under ussumptions (A1)-(A4) for gradient flow and (A1)-AS) for gradient descent, for both SWN and EWN, w, ga 2 0 for all nodes in the network.
Lemma 2. Under assumptions (AI)-(A4) for gradient flow and (AI)-A5) for gradient descent, for both SWN and EWN, there exists atleast one node u in network satisfying [|wal and [ 0.
Lemma 3. Consider two unit vectors and b satisfying a b 2 0 and a Tb < 1. Then, there exists a small enough > such that for any unit vector с satisfying c 2 cos(e) and any unit vector satisfying d b 2 cos(E), b cc )d 2
bb
Lemma 4. Consider sequence satisfying the following properties
1. 0g >
2. Σ k=0 = 00
3. lim; +o0 = 0
Then Σk=0
Ee
00
Lemma 5, Consider two sequences and b satisfying the following properties
1. > 0, 0, ax = xo and lim4-+00 Olk = 0
2. by 0, b is increasing and by ++ I bg + )2
Then Ek=0 by
Lemma 6. Consider two sequences and satisfying the following properties
1. 02 and Ek=0 ak = 00
2. by 0 and Ek-n by 0o
3. (a= - by) converges to a finite value
4. limp-x00 as exists by
Then limg by
C.I EXPONENTIAL WEIGHT NORMALIZATION
In this section, we will use ea(()) and [[)] interchangeably.
C.1.1 GRADIENT FLOW
Proposition. Under assumptions (A1)-(A4) for pradient,flow for EWN, the following hold:
(i) limp- ((w(((
= Em m Eryx V (W,, x:) = where p
[[
(ii) Let W. lime >>0 0
Wull) [w([]] and g. lim4
-v., C(w(r)) Then, W. for some [[V[(((())]]
Update Equations:
do.,(t) = (v ((w(t))
(7)
dt
14

---

Under review as a conference paper at ICLR 2021
dv
(1)e ((1))a -VV((())))))))))mo (w,
(8)
dl
(i) 1 C(w(r)) = Ei= Pat $ W, x+) = g. where >> 0 L(w(t)
Proof. Using the fact that 0 and Euler's homogeneous theorem, say
(wW,,; L ( xz4) > 0
Thus, V 26 xw) for all
Let w(t) = g() r(t), where lo
[r(e 9(1)
O. Now, by Taylor's Theorem, we can say
V vw V (g()),,x)
+ (
k=
r(() r(t)
= D(w, 24) + g(t)4-1 D +
g()) 24)
dk
g(t)
Now, V2 + x.((t)
o(1) m3) can be bounded by a constant and lim
[|x()]]
0. Thus,
9(1)
lit F v2 + k 900
vs 1 dk = 0. Thus, we can say, if |/ 15 xw)
> 0 for some
then
lim VwI(((t), = (w, t000
g(1)--1
Now,
Now, Let S = {i y, (w,, = min, y, (W Let denote minjgs ((. p-
Consider a and & S, then
KO &s (w(()) lim e =()) (#( 100
utty ..) - +WW++ r(t)
lim 1-000 (w())
Now, as the minimum difference is e, therefore lim using Equation O and the expression for - AVr--wAr ((w(((()))))))))) from before, we can say
4 (w()))
E. [w()] 0. Thus, Vj S, 0. Now,
Vw((w(())
lim
Σ Lny 2(
VwC(w(1))
where μ = ELES (lu:)(W.))))
(ii) W..l > 0 - W. Ag. for some >>
Proof. Consider a node u having [.,] >
The proof will be split into two parts depending on
[ > or |
Case 1: | >0
Let the angle between w. and ga be denoted by A. Using Lemma 1 can say A 3. We will prove the statement by contradiction, so let's assume A > 0.
Now, we know, V..,
TV Z(w(T]] converges to g. and vt.(t) converges in direction of w... Taking
dot product with Ru both sides of Equation (8 and using Lemma 3 say there exists
time t and small enough e, such that for any t
gu
dva(t) dt
2
((w(t)l
(10)
g
15

---

Under review as a conference paper at ICLR 2021
Now, using the fact that au - and Equation
say
(t))e
((
Integrating Equation 100 on both the sides from & to oo, we get
v. 00
This is not possible as vectors on LHS have bounded norm. This contradicts. Hence A 0.
Case 2:
|
We are going to show that it is not possible to have [w..l > 0 and
|| 0.
Using Lemma 2 we
say there exists atleast node satisfying ||wlll 0 and
ge
0. Now, using Equation
we can say
Iwa(1|l < '
w. [(w(k))llk
===
From Case 1, we know, for any 6 > 0, that there exists time 4, such that for 11,
(2)
V L(w(t)) W. ((w()))
2 cos(c). Now, using Equation 7) we can say
[w]l
/ k (1F
[t)l 2 /w + cos(e)
Thus, can say, for L1.
[t)l
Ti=o
((w(k))]ldk
[t]l
[w,(t)) + cos(e) Jé n(k) w.
Now, as [wall > 0 and | > 0, therefore both the integrals diverge. Also, the integrands converge in ratio to 0 as using the Integral form of Stolz-Cesaro theorem, can say
gg.ll = and ||g.111 0. Thus, taking limit t - oo on both the sides and
lim [w)()) (t)
50
2000
However, this is not possible as [.wll and |ee > 0. This contradicts. Therefore, such a case not possible.
C.1.2 GRADIENT DESCENT
Proposition. Under assumptions (A1)-(A5) gradient descent, for EWN, the following hold:
((w(t) (i) lime+100 [[
= = Σm m E.y. V (( x;) =g. where μ >
(ii) Let W., lime
(..()) [0 and g.. lim
Vw. C(w(t)) TV=L(w(()]]]
Then, W., Ag... for some
À 0
Update Equations:
au (t) ((t)ea va(t) (V Vw.
(11)
[vv(t)]l
v=(++1)=v. ntt) (au())
v (t) (T v=(()vn(()
((w(t)
(12)
[[v,(t]
(i) limp-+00 VwL(w(t) [ww(((]
= و Σm 1 V W. xw) = where > 0
Proof. Follows exactly shown for gradient flow in Appendix C.I.I
16

---

Under review as a conference paper at ICLR 2021
(ii) [w]] 0 W. Aga for some
Proof. Consider a node u having [w,] > 0. The proof will be split into two parts depending on |[
> or [[
Case 1: [ >>> O.
Let the angle between w. and gu be denoted by A. Using Lemma 1 say A 5 We will prove the statement by contradiction, so let's assume A > 0.
Now, we know Vw,, ((w(t) dot product with time t and small enough e, such that for any t L1.
[(w(E)] converges gu and vu(t) converges in direction of w.. Taking say there exists
5u both sides of Equation (12 and using Lemma
ggul
(t 1) gx
vu(t) gu luul
(tu(t)
<n((t)
I ww ((w((I)
B..
[t)l
However, in this case, (t)]l doesn't stay constant and thus increase in dot product doesn't directly correspond to an increase angle. Now, using Equation
(2), we can say
(t)(
Itv 1)11 21v. (nt(t)
IV ((w(t))l))
(13)
v[](()]]
Using the above two equations, we can say, for time 41.
v.. + 1) Bu V B.
(1( g=
=e(((t) enu(t)
[v,(
V w.. ((w(I))
[t)l(1)12 + (n)(t) ebu(t)
(()] Vw.
Unrolling the equation above, we get
V. + 1) vt 1) ga.
(..(,)) Nu
Bu
k=t k=t,
e(n(k)
(K]]
V W.. (ww.C((())]])
(14)
k=t (17(k)
V W.. (
Now, (t) co, therefore, using Equation
we can say
Σ (()) ((w())) 00
Now, using this identity, along with the Assumption (A5), Equation
13 and Lemma
5 we can say
(k)
(k)
| w. ((w)k] 00
Vv
(b)]
Using this along with Equation 14 and Lemma
we can say
Vl(l + 1) T lim 600
gu.
Vt. + 1)
However, this not possible as the vectors on LHS have bounded norm. This contradicts. Thus A 0.
Case 2: |
We going show that its not possible to have /wal > 0 and |g.ll| = 0. By Lemma know
there exists atleast one node s satisfying [.al > 0 and [g. > O. Now from Equation we can say
akk) (8) Vk( V C(w(k))
a.,(t) (a,)=,
[k)
a.(() = (0) a (1) (k(
Vn, L(w(k))
[k)(l
17

---

Under review as a conference paper at ICLR 2021
Thus,
hmt-1
(7(()) Va(k) V (k) (w())) [v((k)]
(())eau()) Vu(k)
(k)
TO V w. [(w(k))
[k)
(15)
Now, we know, (t) and as (t) - 2c. Also, as [. > and || > O, therefore Cu as converges. Therefore the RHS of Equation (5) converges well. However, RHS is the dif- ference of two diverging series. Also, as (z(t) and Vw, [(w(t)) eventually get aligned and
Vw. ((w(t))]
0, so, lim V ((w(r)]
say
(ault) Vo(()
V V ((w()))
lim (-000 ga (t) va
vv.00l
Vw, ((w(e))
[.)]l
However, this contradicts Lemma 6 the ratio must be converging if the limit exists. Therefore this case is not possible.
C.2 STANDARD WEIGHT NORMALIZZTTON
C.2.1 GRADIENT FLOW
Proposition. Under assumptions (A1)-(A4) for gradient flow, for SWN, the following hold:
C((()) (i) lim [[V ((w(r)) = = m Lit V 1 W x;) = where μ > 0.
(ii) Let W. = lim (f) |[(]]] and gu. lime-soo C(w(() [[
Then, W. = =xg. for some
X 0
Update Equations:
dtu(t) -n((t) vu(t) VT V., ((W(((())
(16)
[vv((t]]
dv.(!) (t) Tu(1)
[|v(tt]] (I- Vx(()v,(()
((w(t)
(17)
dt
[[v(())]12
(i) lim C(w()) [(w(((( = m E.1 V + (w) = g. where >
Proof. Follows exactly shown for gradient flow in Appendix
C.I.I
( w
w. = Ag. for some >
Proof. Consider node u having ||w,||| > 0. In this case, (t(() (t) can either tend to do or -co. We will consider the case (t) + oc. The other case can be handled similarly. The proof will be split into two parts depending on ||gu]] || > or |g 0.
Case 1: -
Let the angle between w. and ga be denoted by A. Using Lemma | we can say A < 5. will prove the statement by contradiction, let's assume A > 0.
Now, we know,
VV... ((w(e)] converges g. and v..()) converges in direction of w,, Taking
V ((w(t))
dot product with 5u Il
on both sides of Equation 17 and using Lemma we can say there exists time 4 and small enough e, such that for any / LT
gu
T
dvv(t)
2
(18)
dt
18

---

Under review as a conference paper at ICLR 2021
Now, using the fact that Yo and Equation (I6). we say
(t) ((w(t))ltt= oo
Integrating Equation 18
on both the sides from 1 to cc, we get
(t 2 00
This is not possible as vectors on LHS have bounded norm. This contradicts. Hence
Case 2:
gg.
We are going to show that it is not possible to have || ||w..1 > 0 and
|| 0.
Using Lemma 2 we
say there exists atleast one node satisfying ||wll 0 and [16, we can say
g |l 0. Now, using Equation
[
(w.(t)]l - = Vw))ll...(((())]]
From Case 1, we know, for any c > that there exists time t,, such that for ti, V. ((w(t))
w. (t)
( [V TVV, ((w(t)]
Z cos(t). Now, using Equation (16), we can say
(D)l
[[w,(t] 2 [tt]l)) + cos(c) f k=
V())) ldk
Thus, we can say, for t > t1.
w. (t)ll
((k]l ([w( di:
ww((1)|
|| (t1 cos(c) SE ()]]] ((w()) dk
Now, as |wall 0 and ||wl| > 0, therefore both the integrals diverge. Also, the integrands
converge in ratio as ggull and || 0. Thus, taking limit - both the sides and using the Integral form of Ktolz-Cesaro theorem, we can say
w [w)(t]
lim
(()l 0
However, this is not possible as ||wlll not possible.
0 and | || > 0. This contradicts. Therefore, such a case
C.2.2 GRADIENT DESCENT
Proposition. Under assumptions (A1)-(A5) for gradient descent, for SWN, the following hold:
(i) lim +00 V
C(w() (W())) = Σm m
- E. V x;) = where μ > 0.
-w,, C(w(t)
and gu lim (ii) Let W. = 4om [w
[ww(((()) Then, W. = -ggu for some
X 4 0
Update Equations:
Va( T Vw., L(w(()
1)) = - -n(()
(19)
[t
V. (1++1)=vvlll - nn(t) (1)(1)
|| (t)l (1 (1)
W... ((w(t)
(20)
[[va(1)122
(i) lime-so L(w((] = M / + W x.) = g. where
V C(w())
Proof. Follows exactly shown for gradient flow in Appendix C.I.I
19

---

Under review as a conference paper at ICLR 2021
(it) [w]] 0 W. Aga for some
Proof. Consider node u having ||wull 0. In this case, (t(t) can either tend -oo. We will consider the case Yu (t) - oc. The other case can be handled similarly. The proof will split into two parts depending on |!g..] || > 0 or |!g. = 0.
Case 1: [all
Let the angle between w. and gu be denoted by A. Using Lemma 1 say A 2 We will prove the statement by contradiction, so let's assume > 0.
Now, we know, V.., ((w(t))
[V,., [(w(t)] converges to g.. and (t converges in direction of w.. Taking
dot product with Eu time l and small enough e, such that for any (
B.ll both sides of Equation (00) and using Lemma 3 say there exists
Vt 1) T. gu.
v.(t) gu Bull
Tu (t)l
<(n(t)
V ((w(l))
Bull
However, in this case, (t)]l doesn't it stay constant and thus increase in dot product doesn't 't directly correspond to increase in angle. Now, using Equation 20). we can say
%a(() [[v((t]]
Vt 1) [1v. (1t(t)
I w., ((w(t))l))
(21)
Using the above equations, say, for time t tı.
Vu vu + 1) gu
Ya (0) Bu
<(n(t)
7a(()
V w. (()II)
Ku
(t + 1.l
(t)l2 + (v)(t) (1)
V Vw.
(Q]l
Unrolling the equation above, we get
V.. 1) ga VI (t
vu(tt) lBull
S 2 ((n(k)
(k)
V. ((w.((
(22)
VIv
(t))1
k= Amtt
(n)(k)
The (RJT ((w:))l
Now, (1) - therefore, using Equation f0 we can say
k=o
Σ
k=
Now, using this identity, along with the assumption (A5), Equation 21 and Lemma 5
we can say
The
(k)
V w. (ww())
do
V
[1:)
k=tz
Using this along with Equation
22 and Lemma
we can say
(t g..
lim
(t 1)
However, this is not possible as the vectors on LHS have bounded norm. This contradicts. Thus A
Case 2:
|g 0
We are going to show that its not possible to have |.,|| > 0 and ||g = O. By Lemma
we know
there exists atleast one node s satisfying [ww |l > 0 and ||g. > O. Now from Equation 19 say
we can
k=
Vu(k) V [(w(k))
Yu = (0)
Σ 0=0
n(k)
20

---

Under review as a conference paper at ICLR 2021
kmt-1
Vo(k) V (w.C(w(k))
7o(1)= = (0)
Σ
m(k)
llv.
k=0
Now, (t) either diverges to oo or -00. In both the cases, it is strictly monotonic sequence for large enough t. Also
lim (c( - Vv(()
t-000
% (1 + (t(
and from Case (t( and -w, [(w(t)) eventually get aligned. Thus, using Stolz-Cesaro theorem, we can say
Tu = 0 100 (t)
lim
However, this is not possible as w[ > and [. || > 0. This contradicts. Therefore, this is not possible.
D PROOF OF THEOREM
Theorem. Under assumptions (AI)-(A4) for gradient flow and (AI)A5) for gradient descent, the following hold
(i) for EWN, [[w.]] 0. W.
limy-oo
[w)] ((w())]
[.]]
41 (w(]]]]
[w..(O]ll ((w(t)) (.,
(ii) for SWN, W.l
0
lim4-400
Proof for different cases will be split into different subsections and the corresponding case will be restated there for ease of the reader.
D.1 EXPONENTIAL WEIGHT NORMALIZATION
D.1.1 GRADIENT FLOW
Theorem. Under assumptions (A])-(A4) for gradient flow. the following holds for EWN:
(i) W. 0, |.
lim
(() V ((w(t)]
[w ((w
Proof. Consider and such that wwwll 0 and W 0. Using Proposition 2 we can say gu > and || > O. Also, from Proposition we can say, for both u and v, weights and gradients converge in opposite directions. Henee there exists a time t2, such that for any t >> t2,
V L(w(t)) and w.(t) make an angle c or lesser with each other
V ww Ctw(t)) and (t) make an angle e or lesser with each other
Then, using Equation we can say for any time > tz.
[[w,(()] (f)ll [w. (t2)ll + cos(c) f (( (Cb)
[[w,(t)] (ww.(t2)l I"
[ww]()]] 2 (t2)l + cos(E) /
[[w](t)] [[wo(t2)]l L"
k=zz
21

---

Under review as a conference paper at ICLR 2021
Using the above equations, we can say, for time t > t2.
[[]l
[|wx(12)]| + cos(E) (iw
[t]] (12)l + Si (+)) L(w
[w]]
l| Ii=e, (8)) [w,)(1)) + cos(e) Ie= (k) (1,
(t)l
We know that both integrals diverge as |[)ll and [[)((t)] cc, lim
[2) and
(e)
lim;- IV wu ell exist. Taking limit + oo on both the equations and using the Integral form of Stolz-Cesaro theorem, get
cos(c)]l..(())IIIV w.. ((W(I
[wa
(w.))////......CC W.
lim
lim 1-000
lim
1-000
[w.(()]
t-000 cas(c) w.. v.
As we know these limits exist and this holds for any e >> O. therefore
I. (t)l
w. (1) w. (0) ((w (t)
lim t-000
lim 10000
W (+)
w w.(
(t)l
Simplifying further, we get
W (t)]l (t) CII
lim 1100
=1
w, (t) w. CII
D.1.2 GRADIENT DESCENT
Theorem. Under assumptions (AI)-(A5) for gradient descent, the following holds for EWN:
(i) Wall 0, |.
lim
[tw. V [(w(t))] (w) (t)
Proof. Consider two nodes u and such that [[wll > and |/wll 0. From Proposition we know || > 0, || 0 and for both and s. weights and gradients eventually get aligned opposite to each other. Using Equation (II) we can say
am) V (k) ( (w.((((()))
(f) = (0)
[v)(()]]
a,(t) a.( - mkke a (.) (kk Vw, L(w(k)
[v<(k)
Thus,
(1(k))))(1) Vo(k) V (w.(k)((((k)) ((k)) Vu(k)
V w. [(w(A)))
an(()-aa() (,.00-aa(0(aa0()-0a00000000 (o.
[v)())]
(23)
Now, we know, ar, (1) and a, (1) + xo. Also, as | > and [w > O, therefore a..( ats
converges. Therefore the RHS of Equation (23 converges well. However, RHS is the difference
(ol)) Vw., ((wco)
of two diverging series. Also, lim can say
exists. Therefore, using Lemma we
(aa(e) vo(e) V., Aiwton
(1)) V ((w(I))
lim (1) V., C(w(t))l
=1
22

---

Under review as a conference paper at ICLR 2021
D.2
STANDARD WEIGHT NORMALIZATION
D.2.1 GRADIENT FLOW
Theorem. Under assumptions (A1)-(A4) for gradient flow. the following holds for SWN:
ii) W.. > W 0
[w. |I w... ((w(t))
[ [w (()(
Proof. Consider u and e such that w 0 and || and || > O. Also, from Proposition we can say, for both and e, weights and gradients converge in opposite directions.
Well O. Using Proposition 2 we can say
Consider time 122 such that for any 12.
V w. ((w(t) and (.) atmost make angle with each other
Vw. (()()) and (t) atmost make an angle with each other
Then, using Equation (6). we can say for any time t2.
[ta(t)] 2 [[2)l))) + cos(e) f" 1=12
[[w,(()] S ||w.( f" n(k)] V.. ((w))(
k=12
/" [](k)]] (ww))
|w.( 2 [|w)( cos(()
[[w,((1] [1,)l + L [())),,,
k=ta
Using the above equations, we can say, for time > l2
[tll
[[a)l + cos(c) Si Cl ((w)))ll
Wy (+)l
[ww.(12) I ()(b)]] V ((w()))
[w](t)]
(w,((2))] Si V ((w()))
[t)l (to)l) cos(c) fi n[k)] V L ((w(k))
We know that both integrals diverge as [[w, (1)l and [[w,(()) + oo, lime [.,+)))|
[wll and
IV te exist. Taking limit -> both the equations and using the Integral limy- VV ce [[)[
form of Stolz-Cesaro theorem, we get
V w. (1) ((w(I))] V (o
(ww(t)]
V. w. (ww ((w())) cos(E) w. ((w)
< lim
lim 1oo
(t)ll)]
As we know these limits exist and this holds for any c > 0, therefore
w (t( Ll
lim
w (t) V (t) CI
23

---

Under review as a conference paper at ICLR 2021
D.2.2 GRADIENT DESCENT
Theorem. Under assumptions (AI)-A5) for gradient descent, the following holds for SWN:
ii) Ww. 0, W. > = lime-+00
[Iw II [(w(t))
[w (t)(
Proof. Consider u and such that [ and [u > and lgg. > O. Also, from Proposition we can say, for both a and weights and gradients converge opposite directions. Now from Equation (99 we can say
0. Using Proposition 2 can say
h=1-1
Vu(k)
V w. [(w(k))
Tu(t) = ro
Σ (76)
[
h=t-1 1
m(kk) Vo(k) TV (w,((w()))
7s(1) = 7.(0)
[v,(k)]
Now, (1) either diverges to oc or -00. both the cases, it is strictly monotonic sequence for (u((+))-7uu0) large enough t. Also lim (u(f+1)-7.. exists. Therefore, using Stolz-Cesaro Theorem, say
w (t)
V w. CII
lim t
w V (t)
PROOF OF PROPOSITION 3
Proposition. Let assumptions (AI)-A55) be satisfied. Consider nodes and in the network be denoted by c. Let e, be
such that || 2 ||gu|| > 0 and [t)(l))ll [[)ll + co. Let
such that 0 < E < e and 0 < 8 < 2x. Then, the following holds:
1. There exists a time t,, such that for all t both SWN and EWN trajectories have the following properlies:
(a) Vw. ((w(t))l [V ((w(
E cc
(b)
w. (t) [w]]]]]
we L(w(())
2 cos(
V w. ((w(t))Il
(c)
w.(t) [w][
V ((w(1))
2 cos(8).
IV,, L(w(O))
2. for SWN, lime-so
[[w((f)] [w)l
=
3. for EWN, if at some time to tı.
(a) (ta)l
lim
w. w.) (t)ll
(c-e) cos
ww[0]
(b)
w [ta]]
cos(6)
lim lim
[t]]
[wa]l
The proof of different cases will be split into multiple subsections and corresponding proposition will be stated there for ease of the reader.
E. STANDARD WHIGHT NORMALIZATION
E. GRADIENT FLOW
Proposition. Let assumptions (A1)-(A4) be satisfied. Consider two nodes u and v in the network
be denoted by Let e, be such that || > ||g.|| > 0 and [[,(()]l, [[w,(t)]] co. Let Tgall
[Bulll
such that 0 and 0 < 5 < 2m. Then, the following holds:
24

---

Under review as a conference paper at ICLR 2021
1. There exists time t,, such that for all t 81, SWN traeecoory has the following properties:
(a) Vw. ((w(t))l
c
WV C(w()))
(b)
(i)
w... ((w(1))
2 cos(6)
[w
ww ([)(l)]]]
(c)
(t)
Vun Vu,, ((w(t))
cos(
[[w]
Vw ([w(A))]
[w),(t)]
2. lim
[w,[e]]l
Proof. The proof of part 1a, i.e, wu ((w())] I1V (t) É [c 6, + c) follows from the definition of limit
V [(w(t)) tends
V (t))
Now, we will move to the proof of part lb, i...
2 cos(o). The assumptions in this Proposition differ slightly from Proposition and thus the proof slightly more involved as we also need to show that w (!) converges in direction. The proof will be given for
Wu(t) [t)]
(-V [(w(()) V
F ((w(A))
Tu + oo. The one for 7 7 - can be handled similarly.
As g > O, therefore V ww_ (()()) converges in direction. Therefore, for every satisfying 0 < T
(Nvr,, Ciw(t)) T < 2m, there exists a time t3. such that fort > f3. [[V C(w(C))l
2 cos(T). Now, Let's
assume that w,, (t) does not converge the direction g.. Then, there must exist T satisfying
2x, such that for this т, there exists a time 13 satisfying vu((4)
cos(A). I
where A > T.
Now, we are going to show that for any x satisfying K < A, there exists time ts to such
that v. (ts)
cos(sc.. Let's say for given x, no such ds exists. Then, taking dot product on both sides of Equation we can say
with
E g.ll
gu
dv,,t)
C(w(t))
gu
(1 (1-vall ((-v((t)v.(tT))
-V. [w(()(((t) ((w(()
dt
1u
( Vw,, (vw(((((()) L(w(())]T 2 cos(()) and
Now,
8. [B=l
2u [gu
v. S cos((s), we can say
dvu(!)
gu |/gulll
2 (t)) (w.
cos(1s)
(24)
dt
Now, using the fact that Yo + oo and using Equation [6], we can say
(()) V ((w()))ldd xc:
Using this fact and integrating the Equation 24 both the sides from t4 to co, get contradic- tion as vectors on LHS have finite norm while RHS tends to co. Thus, for every x between т and A, there must exist fG. such that vt,(t)
cos(R:).
Now, we are going to show for all 1s. (t)
cos(K). Now, consider any such that < B < k. Using similar argument as in Equation (4 we can say, if for any le > ls.
(46
F |
cos(33), then
gu
dva(to)
((tt))a ((w - cos(3))
(25)
|
dt
This means that the dot product between
Eu [I....|
and v.. (t) goes up. whenever
vu(() <
[
cOs(T). Therefore, its not possible that v!)
R...
< cos(k) for any > Ls.
As k. can be
I...
25

---

Under review as a conference paper at ICLR 2021
arbitrarily chosen between and A, and the argument holds for any 0, wu(() converges in the direction of ga
The proof of part 1c, i.e, lb.
(.(t) Vw, ((w(O)
cos( can be shown in the same way as V. ((w())]]
[wa(())]])
The proof of part 2, i.e lim;+0o0 [w]
can be shown in the same way Theorem 2 for SWN
(.]
gradient flow from Appendix D.2.
E.1.2 GRADIENT DESCENT
Proposition. Let assumptions (AI)-(A5) be satisfied. Consider two nodes u and v in the network
such that | 2 |g.|l > O and [ww[()]l (()ll)l + co. Let
Kull be denoted by Let 6, be lgg.
such that 0
and 0 < 8 2n. Then, the following holds:
1. There exists time L1 such for all t L1, SWN trajectory has the following properties:
(a) V C(w())]l
cc
IV Vw, L(w(H))T
(b)
(.( (t)
- Vw. L(w(t))
2 cos(8)
[w.[()]]
Ve ((w(t))]]
(c)
(t)
Ve ((w(!))
> cos(
W. C(w(t)i
2. lim
[t)
[w([]]]
Proof. The proof of part la, i.e, | L(w(t)ll [vw
E [c- c, follows from the definition of limit
V ((w(t))] tends to c.
as
(ew(
Now, will move to the proof of part lb, ie, sumptions in this Proposition differ slightly from Proposition 2 and thus the proof is slightly more involved also need to show that (!) converges in direction. The proof will be given for Yu - 00. The one for 7/a - 00 can be handled similarly.
(.(()
-w,, ((w(t)) Vw. ((w(r))l 2 cos(6). The
[w.lt)
As ga 0, therefore Vw. (t)(t) converges in direction. Therefore, for every 7 satisfying 0 | 2 cos(T). Now, Let's
C(w(t)) < 2m, there exists time f3, such that for t >> ts. (IiV.,, C(w(t))ll
assume that (f) does not converge the direction ga. Then, there must exist t satisfying
T 2x, such that for this т, there exists a time 44 > f3 satisfying (t,
cos(A), 1
where A
Now, we are going to show that for any x satisfying T < k < A, there exists a time i5 > t4 such cos(k). Let's say for given such exists. Then, taking dot on both sides of Equation 20), we can say
that
(a(ts) [M.il
product with
R
[[=
Va Va (1
gu
(t) Bu
+
[gul
n(t) (1) [t)]l]
V C(w(t))
gu
(I v=(()
[t)(())| V ((w(()
(V., ((w(()
Igu
Now, as
Ww, C(w(t))
2 cos(T) and
g.. |
vult) [v.())]])
I cos(R), we can say
V [(w(t))]
V.. (t + 1)
gu
V
ga
(cos(T) - (on())))((t))))
Tu(t)
V C(w(t)
(26)
gu
[[]]
26

---

Under review as a conference paper at ICLR 2021
Now,
using arguments similar to the proof of Proposition 2 for SWN gradient descent in Appendix we can show that the above statement leads to a contradiction and thus there must exist a it cos(k).
C.2.2
such that (f.(f))
(fs)il
Now, we are going to show that there exists a ls > is. such that for all f > 4.
vu(t) [vu[[[]]]
Rv cos( (3s)
(K)(
Consider a / such that < B < k. Now, if at any time t, [vv
then, similar Equation 266
we can say
Vu (t + B.
Bu
(t) Bu
(t(
+ (cos(T) - cos((3))((()
(t)l ((w(())
Bu
1uu
Using the upper bound on ||va.( + 1)ll from Equation 21 we can say
(t +
+1 Bu
v. B (cos(T) cos (m))) (1))
To(e)
V ((w(I)))
8x
(27)
VV 1) gu
(l)a + (17(t)
V V ((w(()))))
(i])
Let (1{) (D]l
(t)
V w. ((w(()) be denoted by x((). Then, the above equation can be rewritten
v.(tt + 1)) gu
(v.l + (cos(T) - coo(33) Ball (l) + X(t)
x(t)
(L. + 1) |
v.. + X(t)
Now, we going to show that for small enough x(t.. RHS is greater than
(u()) B. [M)
Va Bu
vv((
x(t)
Vu(() ga
+ (cos(T) - cos(3))
|| (t)
gull (lv
+ x(t)²
v ([]l(()]l + x(1)2
[lv gall
x(t)
Vt(() gu
(vy(())l
(cos(T)= - cos(3))
(1 VIlva(0]12 +0001+x(00 x(t)²
v (t) x(t)
[tvu g..l
(t(t) gu
+ x()2 (1)
(cos(T)= - cos(3)) >
[t)(ll]
x(t)
Clearly as x() - 0, the RHS tends to 0, therefore the equation is satisfied. Thus for small enough (l), RHS of Equation Assumption (A5), lim (t) C(
(t.(t) g. is greater than [ -. As [[v]l()]] keeps on increasing and by
(w((t) = O,
say there exists time t7, such
that for any >> 17,
[v.[llll. goes up whenever
v.()) g..
v..() [Tu
< cos(3).
Also, by using Equation 20 and Assumption (A5), can say, that there exists time (s. such that for > 1s.
[ > cos(ks), as goes to 0 norm in limit. Now, define to > ma.r(t, ts) such that cOs(K) (must exist from previous arguments). Then, the dot product always goes up when between cos( and cos(w), and can't go in single step from being greater
(r)
cos(3) =
(ult++Di (
(e]l
the RHS of Equation 20
(ta)
[
than c3) to less than (Ks( therefore, for every t6- (Iv..
(t(t)
g
cos(K).
Now as the above argument holds for any between and A, and for any 0, can say that (t( converges in direction of ga.
The proof of part 1c, i.e, part lb.
wa(t) (x(l)
V ((w(O) cos( follows exactly the same steps as | w.. ((w(t)]]
The proof of part 2, i.e, lim
can be shown in the same way as the proof of Theorem 2 for SWN gradient descent from Appendix D.2.2
[ww((t)
[[]
27

---

Under review as a conference paper at ICLR 2021
E.2 EXPONENTIAL WEIGHT NORMALIZATION
E.2.1 GRADIENT FLOW
Proposition. Let assumptions (AI)-(A4) be satisfied. Consider two nodes and in the network
such that || | > 0 and [|)]())]l (I co. Let
&ull be denoted by Let e, be
1g
such that < e and 0 < 6 < 2x. Then, the following holds:
1. There exists time i, such that all & b1, EWN trajectory has the following properties:
(a) Ww. ((w(t))l (ww(C((([])
cc
(b)
Vi L(w(t))
2 cos(6)
[w.(ff]l
V ((w(t))]]
(c)
(t( Vur ((w(t))
2 cos
[[w(t]]]
|| 1V [(w(t))]
2. If at some time t2 ti.
(a) [w.(t2]l
lim
[w)(t]]
[wolfa]] (c-c)
[w][
(b) [|w] cte
(ta]l
c
lim
[w.(
0
[[,(
Proof. The proof of part la, i.e
W. ((w(t))l [1 ((w(t))ll
E 6, + E] follows from the definition of limit
as VV.. ((w(t)) tends to Vw. [[w(I)]]
Now, we will move to the proof of part 1b, i.e., assumptions in this Proposition differ slightly from Proposition 2 and thus the proof slightly more involved also need show that (t. converges in direction.
ww.(t)
-- Wwn. > cos( The TV w., (()T
[[)T
As ga > 0, therefore Ww. converges in direction. Therefore, for every J satisfying 0 < 2 cos(T). Now, Let's
(- Vw,, C(w(t))
2m, there exists time f3, such that for > fa. [|V [(w(t)ill
assume that (t) does not converge in the direction of ga. Then, there must exist satisfying g
0 < T < 2n, such that for this there exists a time t > t3 satisfying vu((t) where T.
= cos A),
[
Now, we are going to show that for any x satisfying 7 < K < A, there exists time is 14 such cos(s.. Let's say for a given N, no such is exists. Then, taking dot product both sides of Equation (8, can say
that v. (ts)
with
gu
dv dv (())) Vw ((w()))
gu
(T (Ivv.(()..()))
(
(- V w. ((w(L)) VV ((w(t)))
gu
dt
g.
Now,
- Vwn (-w(e(((()) [V [IV. ((w(e)l
cos(()) and
nu [g.ll)
V. S cos(1s), say
[Bul
dva(t)
ga
2 n
V L(w ((w(()) - -commr)<))))))
(28)
lgglll
dt
Now, using the fact that aa + so and using Equation
we can say
(()) | ((w(t)) =
Using this fact and integrating the Equation 28 on both the sides from la to oo, we get a contradic- tion as vectors LHS have finite norm while RHS tends to co. Thus, for every x between 7 and
A, there must exist ls. such that (ls)
a.
cOs(R).
28

---

Under review as a conference paper at ICLR 2021
Now, we are going to show for all 2 to. (t)
cos(x).. Now, consider any such
that < 8 K. Using similar argument in Equation 28
we say, if for any te > ls.
(t6) T
R
cos(3), then
[B..
dvu(to)
Su
2 n(to)e (Vw, - cos(3))
(29)
dt
This means that the dot product between
and vu(() goes up, whenever
(i(
|
R
cOs(T). Therefore, its not possible that (!)
cos(K) for any L5.
As can be
g
arbitrarily chosen between and A, and the argument holds for any 0, w. (t) converges in the direction of ga
w.(() The proof of part Ic, i.e, [[w.((]]]) ) part lb.
T
cos(6) follows exactly the same steps as ( (T [(w(t)ill
((w(L))
Now, we will move to the proof of part 2a, i.e. Using Equation
[wa
[w.(fa))
cos(
lime
(e]l
w.
0c
d W [[(]l)l
dea
dt dt = -00)) ww (w(((((1))
(30)
Using the equation above and part 1 of the Proposition, can say for >>>> l1,
ww.(Oll (fll
(w)l (ril
[[]] dl (!]l
dt
dt
[t]l?
[t]] (t)ll
2 n(()
(Iww()))IV& w. ((w(I))] cos(o) -Iw.
(31)
wew (13] ien (e5 dt
In this case, using Equation 31 we can see greater than
O at f2. Thus,
[w,( w (1)ll
always remains
(e- c) and keeps on increasing. Let's denote
(talll (fa)
by Then we can say
[t)ll (A)
> (ccos(o) A(c
dt
As Oa > 00, therefore using Equation 7 we can say 1 (f))ll.. ((w + oo. Thus, integrating both the sides of the equation above from to to co, we get
(t)ll
dt 2 0
dt
Thus lim
Iw. [[][
Now, we will move the proof of part 2b, i.e,
[wa (t2))
cos(8) ctc
lim
[t))
|w, (ta)l
[[w(()]]
Using Equation (30) and part of the Proposition, we can say for & t1,
w.. (.ll
[t)ll) toil
(/w((t)) (ill
w. (t]l
dt
(t)l
[t)
< (t)
((w(t)) (Iw.(t))lll - (ww. cos(8))
(32)
[t)]l
d (t))
In this case, using Equation (32). we can see smaller than cos(o) c+t and keeps decreasing. Now, lets say lim
weltil
< O at tz. Thus, [w,((]]]
(w( always remains
dt
(0]]
0. This means that
[[](0]]
29

---

Under review as a conference paper at ICLR 2021
W. (0)l (1)l A. for some A > 0. Also, let's denote
[| (.2
by B. Then we can say
d [wo(t) (1)I (w)l dt
S -A(cos(D))
B(c ( ((w(t))l
As Ove - 00, therefore using Equation 7 we can say Seg 7 w/l (t)llll ((W()))l + Thus, integrating both the sides of the equation above from to co, get
(e)ll
dt -00
dl
This is not possible as
[w.[ (Q)l
lower bounded by Thus limg-+00
[w, (w)] 0.
E.2.2 GRADIENT DESCENT
Proposition. Let assumptions (AI)-A55) be satisfied. Consider nodes and in the network [ull be denoted by c. Let c, be
such that ||g..| 2 |g > and [[w,(t)]l,
[[),( (I)
+ co. Let
l
such that 0 < < e and 0 < 8 < 2x. Then, the following holds:
1. There exists time ti. such that all t,, EWN trajectory has the following properties:
(a) Vw. ((w(t))l
cc
(w,CC(w())
(b)
(t.())
Vw, L(w(t))
2 cos(8)
[w.(fll
TV ((w()))]]
(c)
wu(t)
V.. ((w(C))
2 cos(
[w,(F]]
[V [(w(t)]]
2. If at some time 1/ t1.
(a) [wa(ta]]
lim
[wutfa]]
(c-c)
[w]]
(b) w.. [ta]] cos(
lim
[ww
0
[w.[
[w.[
| ((w(t))l Proof. The proof of part 1a, i.e,
E [c- c, + c] follows from the definition of limit
Ww. ((w()))] tends to [[ (Vw.L(w(()))
as |V ((w(I))]
Now, we will move the proof of part 1b, i.e,
cos The as- sumptions in this Proposition differ slightly from Proposition and thus the proof is slightly more involved as we also need show that (t) converges in direction.
w. (.(()
((wit) Vww ((w(
(w]l
2
As g > 0, therefore V L(w((() converges in direction. Therefore, for every satisfying 0 <
T 2m, there exists a time 13. such that for > t3, [V [(w(E)]l
V Ciw(t))
2 cos(T). Now, Let's
assume that w,( does not converge the direction g.. Then, there must exist T satisfying
0 2x, such that for this r, there exists time 44 la satisfying v..(44]
i [g
cos( A),
where A > T.
Now, we are going to show that for any x satisfying K A, there exists time ts t such cos(k). Let's say for given no such to exists. Then, taking dot both sides of Equation 12), can say
that v.l(t) (Ma
Zu
product with Ball
Va + 1) gu
Vi(
g
gul
(a(())
vu(t)vu())
Vw., ((w(()
(1))
Vw, L(w(())
(I
[t)]]l
Ig
[V((!)]??
30

---

Under review as a conference paper at ICLR 2021
Now, as
Vw,, [(w(t)) Vun ((w(t]]]
cos(T) and
vi(0)) [u
S COs(()), we can say
18
Vn 1) gu
(1) ga
ga. (cos(T) - ((n())
eaa(()
V Ww. ((w(t(
(33)
gu
V [+)ll
Now, using arguments similar to the proof of Proposition 2 for EWN gradient descent in Appendix we can show that the above statement leads to a contradiction and thus there must exist a is
C.T.2
such that (u.(ss)
cos(x).
Now, we are going to show that there exists a ts > ts. such that for all ts.
[[v.(t)]]
Vu(t)
8+ &
(O)(k). Consider / such that < 3 < k. Now, if at any time t,
vi(()) [vv(OT]
R=
cos(
Bu
then, similar to Equation
(33
we can say
Vu (t 1) gu
(u(t) gu
(ar(1)
+ (cos(T) (3s(
WV ((w(t))l)
gu
gull
vv
Using the upper bound on l|va(( + 1)ll from Equation 13p. we can say
vt + 1) gu
v.(C) B (CoS(T) - cos( (3)(()) (ow()) [V
V ((w(()))
(34)
|| + 1) gu
(t)l + (17(t)
V w. ((w(t))))
[+]]
Let 7t() cau(t)
Vw.. [(w(t)) be denoted by x(t). Then, the above equation can be rewritten as
[t]
Va (t + 1) gu
vu(t) go
(t)|l
x(t)
[.ll (1 + x())2 (cos(T) cos(3))
[L 1) gull
vo) +1 x()2
Now, we are going to show that for a small enough x(t). RHS is greater than Ve(c)
I
v1) Bu
vn(0I
x(1)
vu(() gm.
+ (cos(r)-cos(3))
cos(3))
V
Bul
(t)ll
+ x()2
vI + x())
[Vv g..
x(t)
(t( gu
(t
(cos(T)
- cos(
(1 (I) + x(1)2
(IVv,(()I1 x())
(t)
vu(() Tg.
v. + +X11 lVv((1ll)
(cos(T) - cos(3)) >
x(1)
Clearly as (t) - O, the RHS tends 0, therefore the equation is satisfied. Thus for a small enough xt),, RHS of Equation (34 is greater than v.,()) &
[v. [... As [[)[[))] keeps increasing and by
Assumption (A5), lim, lim (tt))..t)) w.. ((w(t))l = O, we can say there exists a time ty, such
that for any t 17, (.) g.. goes up whenever (.(()) Tvatol|
cos(33).
[...0lllg..
Also, by using Equation and Assumption (A5), we can say, that there exists a time ts. such that for > ts.
cos(k), as the RHS of Equation 12 goes to O norm in limit. Now, define to > maxx(t, (&) such that Vu(ta) (Vu
(()(t) V.[[]]]
cos(3)
vu(t+1) [v.[++I]]
cos(k) (must exist from previous arguments). Then, as the dot product always goes up when between cos(3) and cos(x), and can't go in a single step from being greater
R
[E..
v..(t) than co) to less than cos(k:,, therefore, for every t > to. [[v..
cos(k).
R
Now as the above argument holds for any x between T and A, and for any T >> 0, we can say that (.(() (1) converges in direction of g..
31

---

Under review as a conference paper at ICLR 2021
The proof of part Ic, i.e, part lb.
w.(() [[w,(0]]
(
(
Vw. L(w(t)) Vw C(wit]]l
cos( follows exactly the same steps as
Now, we will move the proof of part 2a, i.,
[w2] [w.
lim
[., [.]]]]]
(c=c)
Using Equation 11 and part of the Proposition, we can say
w., (t2 + 1)ll
|| (7t2)) cos Wa I [w,
W.. + 1)]l
|w (12)l + (1(2)()))))))))))) w. (12) V ((w((2))
(t2)ll
1+ [1) (tw. ((w(()))
(o(12)]l
+ (74 (6
(1,)l
[w2(t)]
Thus, (t)
keeps on increasing for t > 82. It can either diverge to infinity or converge to a finite value. If it converges finite value, then by Stolz Cesaro theorem,
[w]]f]]
[t)
lim [wa(t] V w. L(w ((w(t))
lim
(1) w. (()(I)
However, this is not possible as
[w]( [w]l
1 for every t > t2. Thus,
[wll (w)l
diverges to infinity.
Now, we will move the proof of part 2b, i.c,
w. (ta)] Tw. (ta)l
cos(8)
lim
[w,(t)
0
Using Equation
11 and part of the Proposition,
say
W. (t2 + 1)ll
[|w,((2)]| + 17
(tt2)l (t.) ((w(t)))
W (t2 + 1)
(w2)t) + n)(2) cos W/ co Vw
(1,)l
1 + m(12 W.,, [t.,
(f2)ll
(127 w, (tz (t2()
(w.(12]
(12)l
Thus, [w.(( [w] keeps on decreasing for & > 12. As it is always greater than zero, it must converge.
Therefore, by Stolz Cesaro Theorem,
Iw. (t) lim
W [wa(1)2 W. L(w ((w(I)ll
lim
[t)
[.. w. (t()l)
For
[w. [w](O]] < 1 e,
this can only be satisfied when lim
[w]]
w.] 0.
[wa( (6]l
F PROOF OF COROLLARY
Corollary. Consider a weight normalized(SWN or EWN) multilayer linear net, represented by y W,W Wn Wn-1...Wi. Under assumptions (AI)-(A4) for gradient flow and (AI)-(A5) for gradi- ent descent, if the dataset is sampled from continuous distribution w.r. Rd, then, with probability 0 W, WT_.. ... converges in direction to the maximum margin separator for all linearly separable datasets.
Proof. Consider a linear net given by f = WwWWw. W1,, z. where f is a scalar as we are consider- ing a binary classification problem with exponential loss. Then
ac(w(t)) = Σ - ((0),.W..00.....00..W..000 @W1(t)
(35)
32

---

Under review as a conference paper at ICLR 2021
Now, atleast one of the neurons in every layer would have non-zero component w, otherwise @ (W, x,) = for all i, that implies p p= Let be one of the nodes of Wi that has non-zero component in w. and let w. be the t row of the matrix W1. Now, from Proposition we know W. = Xg.. Denoting the component of w along matrix We by Wa and using Equation 35
we get, for some λ > 0,
W. -
W3
1=1
where (WW,, (W..n-I....Wg [k] represents the h component of the product column vector. Let S represent the set of rows in Wi that have non-zero component in w. Also, let 0 denote the final convergent direction of 0. Then, for some μs > O, we can say
= pWf W
= J Σ > p- W2) D)D Σ Eyxxx
JES
Thus, satisfies the KKT conditions of the maximum margin problem and if data sampled from continuous distribution w.r.t Rd then with probability 1(Soudry et al. 2018). would converge to the maximum margin separator.
G PROOF OF THEOREM 3
Theorem. For EWN, under Assumptions (A1)-(A5) and lim hold
[+((+|)-r((] g((+1)-9(1
0, the following
1. [[w(t)] asymptotically grows at O ((og(d(tt))+)
2. [(w(I)) asymptotically goes down the rate of ((ollod(())))
First, will establish rates for gradient flow and then go to the case of gradient descent.
G.1 GRADIENT FLOW
Although the asymptotic convergence rates for smooth homogeneous neural nets have been estab- lished in Lyu & Li (2020), the proof technique becomes easier to understand for smooth homoge- neous nets, without weight normalization.
G.1.1 UNNORMALIZED NETWORK
dr(()
Theorem. For Unnorm, under Assumptions (A1)-(A4) gradient flow and litt the following hold
0,
g (f)
1. [[w(I)] asymptotically grows at O (log(())))
(_1
2. L(w(l)) asymptotically goes down at the rate o
1(log F
Proof. Consider w g + r(t), where lim
[r(t]]] a(t)
O and r(t) Tw 0. Now, make
drre)
0. This basically avoids any oscillations in r(t) for large t, where it can have higher derivative, but the value may be bounded. Now, we know
an additional assumption that lim (()))
dw(() dt
Σ c v.((((t))))) V. (w((t) xx)
33

---

Under review as a conference paper at ICLR 2021
Now, we know || dw(()) for any finite t, otherwise won't change and C can't converge to 0.
Thus, for all t, we can say
dw (t)
Σ e (w(()))))))))))))) V 1 W. x;)
Taking limit oo on both the sides, we get
dw([]
lim
dt
(36)
2e
(w(((())))))g V (WW (w,x;)] x;
==1
Now, we know
11g |
dw(() ||
dr(1)
dt
m Σ
0: (.((((().x)) U/ VwD(w, x:)11
m
vig(t) /
513
(vig(t)
2 -V 2 w
r(t)
x,)
g(1)
Let = {i @ x,) min, 2 ((W, Then as > 0, we can say
Σ i=1 (.g(t) ( 3 x.) (vig(t) (w Vw r(t) oit) x,)]
lim
p- ((t) Eies Lift V (w,,
where & is some constant, Also, by assumption
(dw(())
lim
g((t)
Substituting the above two equations in Equation
36 we get
g((t)
lim 700 e pg(t)"
g(t))--1|| |1 Ey., (
k
Now, as loss goes down at the rate of -9 multiplying the numerator and denominator by (-- and denoting h(1) = (1) we get
ht())
Le Le ((t) \ Eies Egys V (.. xx)| k
Thus, asymptotically, h(t) grows at @(log(t) + (2 2) log logt) and thus loss goes down at O
Alog 2)2
G.1.2 EXPONENTIAL WEIGHT NORMALIZATION
drie
Theorem. For EWN, under Assumptions (A1)-(A4) for gradient flow and lim; following hold
of (t) 0. the
1. [[w(t]] asymptotically grows at & (Tog(()+)
2. L(w(t)) asymptotically goes down at the rate O
1 (llgg))
Proof. Consider w g(t) r(t), where lim
[|((t]]] g(t)
0 and r(t) [t) w =0 0. Now, we make an
additional assumption that lim, ( 0.
In this case,
d.((wtt)
dw = Σ e v. v.((((t)xx))) (()()
34

---

Under review as a conference paper at ICLR 2021
However, in this case, for node
dw n (1) - -lw.,(t)) (W())))
dt
dw.
Consider vector a()) of equal dimension as w, and its components corresponding node is
given by (t) - -l 2| dc(((t))) Now as we know w converges in direction to W, therefore, using the update equation above, we can say
dw.
dw())
lim t00
g at)
Using the update equation for dC(w(1)
say
dC(w(t))
lim
der
g(t) k1
(37)
pa(1)²
where is some constant. Now, using the expression for a(t), we can say
||a(t]] e pa(t)" g(t) k
lim
where & is some constant. Using the equations above, can say
g'(t)
1
lim t1000 e 20()) g(t k
Now, as loss goes down at the rate of -- multiplying the numerator and denominator by pL and denoting h(t)= = p we get
pt)(() (1000 e h(t)(tt)
1 k
lim
Thus, asymptotically, h(t) grows at @(log(t) 2 log log t) and thus loss goes down at the rate of O (logeyz)
G.2 GRADIENT DESCENT
Theorem. For Exponential Weight Normalization, under Assumptions (A1)-A5) and
lim 0(+1)-9(() 0, the the following hold
r((+1)-r((t)
1. |w(t)] asymptotically grows at & ((og(d(t))
2. L(w(t)) asymptotically goes down at the rate of (:0)log
Proof. Consider w = =g(t) + r(t), where lim
[+(t]]]
0 and r(t) w = 0. Now, we make
a(t)
additional assumptions that lim, a(t+1)-9(t)
[I((++))-(()] 0.
Consider node a in the network that has || > The update equations for v. (1) and (t. are given by
(()) Vt(t) V L(w(t)
[v
eai(
(t(v),.(t)
v. + 1) vt) - rt()
V w., L(w(t))
Now, we will first estimate (++1)
(++11
eau(() v.(() ll. Let 8t( denote [v.(t)]
Vr. (f+1I]]
(())em.(0]IV.. [(w(())] and (t) denote the angle between va(()) and - L(w(()). We know
35

---

Under review as a conference paper at ICLR 2021
lim (t) 0 and lim (t( 0. Now, rewriting update equations in terms of these symbols, we get
(a0(t+1) = (am(0)) (02000 (t) coe(en(())
-V Vw.C(w(tt)v.an)
Vu v.,(t) + du (t) sin Cc (t))
(ww,(((())v.
where ww.,C(((t))
denotes the component of V w.. [(w(t) perpendicular va
Now, using these equations we can say
cau(t=1) (u 1)
eau(t) Va(t) eaa(t) (e5it))) |i((tt] V| + 1)ll
1) Vu(()
Vv + 1)ll [[v](t)]
vt.l
(0 5, sin(()(t))))))) - -V -v.,((w(t))vane) [[v v.. 1)ll
((w(t)) (38)
Now as limm
[[v [++I]]]]
1, therefore we can say
(aa(t)ooleeuu))
[t)l (r(++)
lim
40000
8n (t)()))s(e)(())
Now, [[)]l keeps increasing during the gradient descent trajectory, therefore we can say (. S k, where k > 0 is some constant. Now dividing both sides of Equation (38 by eau(t) on (4) cos(ee())) (4)) and analyzing the coefficient of the second term on RHS, we get
(5a(() (t)( sin(Cu(()) <
lim
(t) (os((.(())
Taking norm on both sides of Equation above, can say
38
using Pythagoras theorem and the limits established
(t++()+)) (1+++1
V. [I+1] - (t)
V.(E)
(A)
lim
8000
(au(t)a((t)
Now, we also know
c am(+1)
(..( [u(++1>]
vu(t++1)
lim 8-000
Ww,
g(t + 1) g()
Now, using equations above and Equation
37 we can say
g) g(t)
lim t-000
(t)e pg(()) g(t)
where e is some constant. This determines the asymptotic rate of g(). To get better closed form, define define map N RR, given by d(t) Et= (T)) and real analytic function f() satisfying (d((t) g(t) for all t N and lim (d(0) 0. Substituting this f in the equation above, can say
(d(())
f'((())
lim 1-000 e of (dke)) f(d(t))++ =C
Thus f(d(t) grows ((log(d(t))t) Now, to get convergence rate for loss, multiply and divide the equation by pf (d(())) and denoting h(d(()) pf(((t)) we get
(d)(((())
lim
h(d())(d((t)
Thus, h(d(t)) grows the O(log(d(t) + 21 log log d(t)). Now as g(t) (d(tt) and pg(t)² h(d(t)), therefore g(t) asymptotically grows at Ollo d(t) b) and loss goes down asymptotically at O( ((0) log )(
36

---

Under review as a conference paper at ICLR 2021
H CROSS-ENTROPE Loss
In this section, we will provide the corresponding assumptions and theorems, along with their proofs, for cross-entropy loss.
H.1 NOTATIONS
Let denote the total number of classes. As ((w, x;) is multidimensioonal function for multi-class classification, let's denote the jth component of the output by (w)). Also, denote the margin for jth class corresponding jth data point(j A ys) by Pi.j- i.e, Pi.j = 4y, (w, Margin for data point is defined as Pi = minjzty Pi.j- The margin for the entire network is defined as p = min; Pt- Also, define a matrix M (w) of dimensions (m, k). that is given by
Q (W, xz).
0 e (,
M(w)li,
34
y + j
Also, for matrix A, vec(AA represents the matrix vectorized column-wise.
H.2 ASSUMPTIONS
The assumptions can be broadly divided into loss function/archiiecturee based assumptions and tra- jectory based assumptions. The loss functions/architecuue based assumptions are shared across both gradient flow and gradient descent.
Loss function/AArchitecuure based assumptions
Eyy, (ww,x.) = log(1 + Ejan ( x) is a C function, for fixed (Aw,, x) = X > x), for some > and L 0
(w.,x))) (w.x.)))
Gradient flow. For gradient flow, make the following trajectory based assumptions
(A1) lime-+oo L(w(l) (1))
(A3) lim vee( ((w(t)))
(Ww)) vec(M)
(A2) lime-
w(t) [
(A4) 0.
All the assumptions above are exactly the same for exponential loss, except for (A3). Using assumption (A1), we can say
lim (",, 600 j#
(,()))))))))x))))mw0000.. =
(39)
log(1 + Σ lim 10000
(w())))))))))
(40)
Ejtn. e (w(()))( 45 (w((),))))))
Thus, we can say, for large enough t, l, 2 Ej (9 xx) 4y (w()),x.)) Thus, assumption (A3) basically states that, not just the loss vector converges direction, but its components cor- responding to various classes also converge in direction. This is required to show that gradients converge in direction case multi-class classification.
Gradient Descent. For gradient descent, we also require the learning rate r7(t) to not grow too fast.
(t) for all in the network Proposition 4. Under assumptions (AI) lim,- ()t)]] (t))]l ((w(t))l 0 holds for every u in the network with ()) = O (=), where e
(A5) lim4-100
Proof. The gradient of the loss function is given by
V
1
Σ 3
(1xx (wix:) -0, (V b (w,x,) -x))xxva.o By (w,x,)
1
(wx,)) - (w))))
1=1
(41)
37

---

Under review as a conference paper at ICLR 2021
Under Assumption (A1), w(t) can be represented w(t) = g(0) + r(t), where lime-voc O and r(t) w = O. Using the equation above, we can say
||[(]]
g(
[V k
lim 700 pa(t)" g(t)
As the order remains the same in the proof for exponential loss, the proof follows from Appendix
This proposition establishes that the Assumption (A5) mild and holds for constant 17(t), that is generally used in practice.
H.3 EFFECT OF NORMALISATION ON WEIGHT AND GRADIENT NORMS
This section contains the main theorems and the difference between EWN and SWN that makes EWN asymptotically relatively sparse compared to SWN. First, will state common proposi- tion for both SWN and EWN.
Proposition 5. Under assumptions (A1) for gradient flow and (AI)-(A5) for gradient descent, for both SWN and EWN, the following hold:
(i) lim C(w(() where μ > 0.
[[ H +E M(i,j)(V ( VwD,
(ii) Ww.ll > 0
Wu = Xgu for some À > 0
ii) lim T C(w(() [[w((((()]] 1 Em jty. M (V Ty (W.x,) V (w,,((xx;;) g, where
1a 1>0
Proof. using Assumption (A1), w(t) can be represented as w(t) = g(t) + r(f), where [+])]]
oi 9(1)
0. Then,
(2,, (w.x))
-0(0) ((1b,, (W+ rit) DEE)
x.) xx))
r(t)
r(t)
V (w, V v1 w. x.) -(t)
x,) - V by
g(t) x.))
g(t)
Now, using > and Fuler's homogeneity theorem, we can say
T (W (w, x;)
V (w, x:)) = L( (w, x;) Bw xx)) > 0
Thus, V (w, x; V B (w, x,) 0 for all i. Using these facts, Equation and Equation we can say
33
Equation
(t)(t) Www(w(()))
him
(w, - V D (w,,,,
E=1 j71
(ii) [w
0
W. = Xg. for some >
Proof. The proof follows from Appendix
The first and second part state that under the given assumptions, for both SWN and EWN, gradients converge in direction and the weights that contribute to the final direction of w, converge in opposite direction of the gradients. Now, we provide the main theorem that distinguishes SWN and EWN.
Theorem 4. Under assumptions (AI)-(A4) for gradient flow and (AI)-(A5) for gradient descent, the following hold
(i) for EWN, ||.|||
W.
lim lim
Wa (t) V ((w(r) w.
V. [(w(((
38

---

Under review as a conference paper at ICLR 2021
(ii) for SWN, [..]|
0
lim
Ww (cill) V w.. ((w(()) Wo
Proof. The proof follows from Appendix D
H.4 SPARSITY INDUCTIVE BIAS FOR EXPONENTIAL WEIGHT NORMALISATION
The following proposition shows why EWN is likely to converge to relatively sparse points.
Proposition 6. Lel assumptions (A (A(5) be satisfied. Consider two nodes u and v in the network such that llg.1l |l > 0, gull > O, w. (f)ll + and [|)llt)] + Let
Tggal &.ll be denoted by Let
e, 6 be such that
and 0 < 8 < 2x. Then, the following holds:
1. There exists time ti, such that for all t1 both SWN and EWN trajectories have the following properties:
(a) V. ((w(t))l
[c cc
L(w(E)I
(b) W.
V. Lim(t))
2 cos(8)
Iw (f)l
wa ((w(t))]
(c)
(.(
Vun, ((w(t)) V. ((w())]
cos
[w,(
2. for SWN, lime-soo
[wa(()] [w (3)l
=
3. for EWN, if as some time l2 > 4
(a) (t2)l
[f2)]
(o-e) cos(5)
lim ooo
w.. [t]l
[c]]
00
(b) [w, [+5]
w. (fa)
cos(6)
lim lim 000
[
ctc
[w]]
The above proposition shows that the limit property of the weights in Theorem makes non-sparse unstable convergent direction for EWN, while that the case for SWN.
Proof.
The proof follows from Appendix
H.5 CONVERGENCE RATES
Theorem 5. For EWN, under Assumptions (A1)-(5) and lim
[+(++]] -((ill
the following
((+11-99())
hold
1. |w|] asymptotically grows at O ((og(((())
2. C(w(t)) asymptotically goes down at the rate of (tc)(log
Proof. The proof follows Appendix G.2 the only difference is in the gradient update. Let w be
represented g(t) rrf), where lim
||((O]l O. Using Equation 41), say g(t)
lim (ww((()) k t-000
PP g(1)
As the order remains the same as in the proof for exponential loss, the proof follows from Appendix
I
LEMMA PROOFS
Lemma 1. Under assumptions (AI)-(A4) for gradient flow and (AI)-(A5) gradient descent, for both SWN and EWN, gu 2 0 ffror all nodes in the network.
39

---

Under review as a conference paper at ICLR 2021
Proof. We will show the proof just for exponential parameterization and gradient descent, but other cases can be handled similarly.
We only need to consider nodes having | and
[u
0, as for other nodes gu. = 0.
Consider node u having || [wull > 0 and
| || > Let's say w gu < O. This means, there exists V w. [(w(t))) < Then using Equation 11
time 11, such that for any 81, w.(t)
can say that, for > t1, Ou (t + 1) < (t).). But, this contradicts the assumption that [w,, 0c. Thus, W, gu 2 O.
Lemma 2. Under assumptions (A1)-(44) for gradient flow and (A1)-A5) for gradient descent, for both SWN and EWN, there exists atleast one node u in the network satisfying [| and Bull > 0.
Proof. Under the assumption that p > 0 and using Euler's homogeneous theorem, using Proposition
we can say
m
W g 11 Σ &yww VwD((w,.)) = Lu _
Euy @ W. xx) > 0
Thus, there must be atleast node satisfying W shown for cross-entropy loss as well.
and
0. Similarly, it can be
Lemma 3. Consider two unit vectors and b satisfying a Tb > 0 and bb 1. Then, there exists a small enough > O, such that for any unit vector satisfying c' a 2 cos(E) and any unit vector d satisfying d b 2 cos(E), b (1 )d
Proof. First we will try to find bounds on b c and c d.
b c b (a ca+c-ar a)
b bTa b (c (c-a)
c d = ca aa T (b+d- - -b b)
= a bbball (d - b) bT (c 1
(c (d b)
Now, using the fact that c a 2 cos(c) and d 2 cos(e), we can say ||c all S /2 - 2 cos(c)
and ||d bll 22 2 cos(c). Using these bounds and the equation above, say
b c c < a Tbb
b + /2 ccos(c)
c a b+ 2/2 2 cos(c) + (2 cos(c))
Using these, we can say
b (I cc ) 2 cos(c)
(a b /2 ccs b+ +2 - c00((c (2 2 cos((c)
Now, we need to show that there exists > 0 such that cos(E) - (a bb -2- coss(e) bb 2/22- cos(e) + (2 2 cos(e))) > e. At 0, LHS takes the value 1- (a b) while RHS takes the value 0. Thus, by continuity with respect to of the functions involved, we can say that there exists an c for which the condition satisfied.
Lemma 4. Consider sequence satisfying the following properties
1. > 0
2. Ek=p Og
3. limg aj
Then 2k=0
V E/ a²
40

---

Under review as a conference paper at ICLR 2021
Proof. If EE== of is bounded, then the statement is obvious. Let's consider the case when 2k=0 dg diverges. As lim O = 0, therefore there must be an index k1, such that for h 2 k1, 4 S c. Now, Ox S therefore o eag. Now, as k a diverges, therefore, there must be an index
k2 > 11, such that for any k > k2, Ej=n, aj = Σ h1 == az.
Now, for h > k2 we can say
1
aj
2
2
1=
j=ki
k1
k
1
jj
>
V2
j
k1
Ea
aj
2c
j=ki
Li=kk
at
1
aj
2E
j=k
As Lk=o ag diverges, therefore Ex
diverges as well.
a
Lemma 5. Consider two sequences and b satisfying the following properties
1. 0k > 0, Ek ax = xo and limp-toc O2= = 0
2. bo > 0, b is increasing and 6 b S 62 + 42 )2 (px)
Then Ek=o
a oc. by
Proof. As we know b is increasing and 07
S
b% + (0x )2, we get
k-1
k-1
bk 1
66
16 +
2
bj
j=0
0=0
Using this, we can say
Σ a bj
aj
aj kー-1 6/
08
+ Σ1
af
of
Now, if Et= ag does not diverge to infinity, then remains bounded using the bound above and then its trivial establish that Σk=o as diverges. In case. Ex ag diverges to infinity, then there by
must be an index b such that for any ls > k1, we can say Σ/=0 az 2 by- So, for k > k1, we can say
k
a
j=0
1=0
21=0
Now, as we have assumed tends to zero, so there must be an index ky such that for any h > k2,
as S e. Also, as we have assumed Ei= a² diverges, therefore there must be an index kg > k2.
such that for Ks, Ej= af
= az. Using these things and that if a, S e, then a3 < eaj.
k2
we can say for k K3.
bo
bn
2
2
aj
2i=kg
Eas
j=ks
Now, Exe ag diverges, thus Σk=o bg
diverges as well.
41

---

Under review as a conference paper at ICLR 2021
Lemma 6. Consider two sequences and satisfying the following properties
1. 0g > and Ek=0 aj = 20
2. by 0 and 2k=0 bk 00
3. Lk=o(ax by) converges a finite value
as exists 4. lim bp
ak Then limg-400 by
Proof. Let's say lim
as = 1. The other case can be handled similarly. Choose an >>>
be
such that c e > 1. Then, there exists an index k1, such that for k > k1, we can say
0k E
scte
bk
Using this, we can say, for l > k1
b 1) S a2 - by I bb(c+c-1)
Summing the equation above from kn and recognizing that Ex=o diverges, we get Ei=k (ag by) = 2o. This contradicts. Therefore lim 1.
J INTEGRAL FORM OF STOLZ-CESARO THEOREM
We first state the Stolz-Cesaro Theorem.
Theorem. Murresan 2015) Assume that {a] and {b) are two sequences of real numbers
such that (b) is strictly monotonic and diverging. Additionally, if limmpoo b by then lima- by exists and is equal L.
1--1-06 exists,
Now, state and prove the Integral Form of Stolz-Cesaro Theorem.
Theorem. Consider two functions f(I) and g(l) greater than zero satisfying St [(]]dI < oo and
Sh g()ddt < for every fintte a, b. For any time I, its known that f, [(()dl = oo and f. g(()dt=
f(t) co. If lim g(t)
exist and is equal to L. then lim 1º flgaas exists, any and is equal to L.
1e alt)dt
Proof. Case 1: L = 0 or oo:
We will prove for L co. The case for 0 be handled similarly. For any M 0, there must exist a time 1 > c, such that f(t)
M, for > l1. Thus we can say for 41
g(t)
L f())tt 1 f(t)dt + +M [ g(t)dt
Adding M 1 g(t)dt on both the sides, we get
J. f(t)dt + M/ S. a(t)dt> [" f(t)dt + M J. g(t)dt
Dividing both sides by 1e (t)ddt and taking limsup t + co(using also the fact that J f(t)dt < oo and S g(t)dt < oo for every finite a, b), we get
(()ddt M
lim sup 50
1e g())dt
Similarly the equation holds for liminf as well. Thus, both liminf and limsup are greater than M for any M. Hence limg [ f()dt
T. g(fitt
DC.
42

---

Under review as a conference paper at ICLR 2021
Case2: L finite
In this case, there must exist some time & c, such that - g(t)
-(t)
< L e.Tuus, we can say
for > ti,
Jx f(t)dt+ ( (L- [((00)dte g(1)dt & S: s())t s S.
s()dt f(t)dt (L++) E) S g(t)dt
+(t)dt+(L
Taking the left inequality, adding (L c) S² g(t)dt on both the sides, dividing both the sides by Se (()dd and taking lim inf we get
L- S lim inf Le s()dd
1-0 So g()ddt
Similarly, taking the right inequality, adding (L +c) S: g(t)dt on both the sides, dividing both the
sides by fe (f)ddt and taking lim supsup get
Le f(t)dt
lim sup
Lte
S: 9t)dtt
Using the two inequalities, we get, for any E>
L:. f(t)dt
Sc f(tddt
lim sup t-000
lim inf
I 2e
So g())d
t-000 St g())dt
L. f())dt Thus, lim s())d
exists and is equal to I.
K STANDARD WEIGHT NORMALIZATION IS NOT LOCALLY LIPSCHITZ ITS PARAMETERS
In this section, we will denote w by so to be consistent with the notaion Lyu & Li (0200) SWN((in its parameters " and v) is also a homogeneous network. Therefore, results from Lyu & Li (020)) should directly apply to the case of SWN as well. However, crucial point to noted is that is not even locally Lipschitz around v!v..l = 0. Therefore, the assumptions from Lyu & Li (020)) do not hold.
However, during gradient descent gradient flow, if started from finite ||v..|| >> 0, for all then during the entire trajectory, ||v..]l cannot go down. Therefore, the network is still locally Lipschitz along the trajectory it takes. Examining the proofs from Lyu & Li (2020), its clear that the proof regarding monotonicity of margin and convergence rates are just dependent on the path that gradient descent/flow takes and thus the proofs hold.
do not hold. One of the crucial theorems the However, the result regarding the limit points of [ proof relies on is stated below
Theorem. Let {I E Rd k E NJ be sequence of feasible points of an optimization problem (P), (ex > 0 N] and {6g > 0 k E N} be two sequences. 2g an (Egs -KKT point for every and MFCQ holds then x is KKT point of (P)
and c 0, 6% 0. Iz + as k
The above statement requires MFCQ be satisfied x, that was shown in Lyu & Li suming local lipschizznssssmootthne
20200)
at æ. However, in this case, for gradient flow, as v.,l does
not grow, while hul + xo, therefore the convergent point of 9 will always have the component corresponding to v, as O. Thus, the network is not locally lipschitz at and the proof that MFCQ holds violated. Similarly, for gradient descent as well, can't 't be said that v. has a non-zero component in & Thus, the proof does not hold.
[
L EXPERIMENT DETAILS
In the experiments, techniques for handling numerical underflow were used as described in Lyu & Li (2020). However, the learning rate they used was of O but in our case, we generally modify be O (z)z), where 1.
43

---

Under review as a conference paper at ICLR 2021
L.1 LIN-SEP
The learning rate used was 20.0.. so that it speeds up at the beginning of training, but slows down as loss approaches e-300 The constant k(() was initialized at 0.01, and was increased by a factor of 1.1 every time loss went down and decreased by factor of 1.1 every time loss went up after gradient step. Its value was capped at 0.01 for EWN and SWN.
L.2 STMPLE-TRAI
The learning rate used was 203, so that it speeds up at the beginning of training, but slows down as loss approaches e -50 The constant k(t) was initialized at 0.01, and was increased by a factor of 1.1 every time loss went down and decreased by factor of 1.1 every time loss went up after gradient step. Its value was capped at 0.1 for EWN and Unnorm.
L.3 XOR
The learning rate used was g9.93. so that it speeds up at the beginning of training, but slows down as loss approaches -50 The constant kt()) was initialized at 0.01, and was increased by a factor of 1. every time loss went down and decreased by factor of 1.1 every time loss went up after gradient step. Its value was capped at 0.01 for EWN and 0.1 for other cases.
k(t)
L.4 CONVERGENCE RATE EXPERIMENT
For all SWN, EWN and Unnorm, the learning rate constant v 0.01 and they trained for 5000 steps. All the networks were explicitly initialized to the same point in function space.
L.5 MNIST PRUNING EXPERIMENT
The learning rate used was A(t) E The constant k:()) was initialized 0.01, and was increased by
factor of 1.1 every time loss went down and decreased by a factor of 1.1 every time loss went up after an epoch. Its value was capped at 0.01 for all the cases.
M RESULTS FOR STANDARD WEIGHT NORMALIZATION
N MNIST PRUNING EXPERIMENTS
44

---

Under review as a conference paper at ICLR 2021
[A4.1
||w.l1
[[ey]
[eeil
class -1 class
5000
10000
Steps
(a) Dataset
(b) Evolution of |wwll
3.5
Normalpped Margin
01
0.
5003
10003
Steps
Steps
Weight convergence
(d) Loss convergence
(e) Normalized parameter margin
Figure 8: Verification of assumptions for SWN in Lin-Sep experiment: (a) shows the dataset. In (b), it can be seen that only weights 5, and 8 keep growing in norm. So, only for these, [Wall > O. (c) shows the components of the unit vector [w] only for the weights 5, 6 and 8 as they keep evolving with time. Eventually their contribution to the unit vector become constant. (d) shows the components of the loss vector and they also become constant eventually. (c) shows the normalized parameter margin converging value greater than 0.
45

---

Under review as a conference paper at ICLR 2021
-0.6
Cosine b/w and V..C
-0.4
Cosine b/w V. and
-0.6
-0.8
-0.8
-1.0
5000
10000
5000
10000
Steps
Steps
(a)
225.0
-2317
-800
yix 234.7
log [19
-255
10g
-199
-227.5
-2061
log [wwll
log
(c)
(d)
(e)
Figure 9: Demonstration of Results for SWN in Lin-Sep experiment: (a) demonstrates part of Proposition 2 where is approximated by using w from the last point of the trajectory. Clearly, V... C stops oscillating and converges g. (b) demonstrates part of Proposition and shows that for weight vectors 5,7 and 8, w., (L) converges in opposite direction of V w. L( ((w(()) (c), (d) and (e) demonstrate Theorem for SWN, where for weight vectors 5,7 and The three graphs are plotted loss values of 200 250 and 300 respectively. At each loss value, for the 3 weights,
log Ww. Cl| - log |w.|l is approximately same.
46

---

Under review as a conference paper at ICLR 2021
30
20
class -1
class
10
Steps
Datasct
(b) EWN
10
10
[|wll
||w
500
1000
1500
500
1000
1500
Steps
Steps
(c) Unnorm
(d) SWN
Figure 10: (a) shows the XOR dataset. (b), (c) and (d) demonstrate that EWN weights grow sparsely when compared to Unnorm and SWN
47

---

Under review as a conference paper at ICLR 2021
Norm
60
Norm
2000
4000
6000
8000
10000
5000
10000
15000
20000
Steps
Steps
EWN
(b) SWN
Norm
Steps
(c)
Unnorm
Figure 11: Norm of the weight vector vs gradient descent steps, for various nodes in the first layer, when trained MNIST.
48


Reviews:
[{"review_id": "YNluSAMr75b", "reviewer": "AnonReviewer2", "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": "### Summary \nThis paper studies the inductive bias of gradient methods with normalization on smooth homogeneous models. The focus is on two normalization methods, standard weight normalization (SWN) and exponential weight normalization (EWN). The authors show two main results. The first characterizes the trajectory of normalized gradient methods from which they provide theoretical evidence that EWN is biased towards sparse solutions. The second provides convergence rates for the normalized methods which shows the difference between convergence rates of normalized and unnormalized methods. The theoretical results are corroborated with experiments on several toy datasets.\n\n### Reason for score\nI am currently inclined towards accepting the paper because the results are novel, solid and should be interesting and useful for researchers working on theory of deep learning. However, the score is only marginally above the acceptance threshold, because I have several concerns regarding the clarity and significance of the results. I am willing to raise my score if the authors address my concerns in the rebuttal.\n\n### Pros\n1.\tThe theoretical results are solid, novel and the proof techniques might be useful in other inductive bias analyses.\n2.\tThe sparsity result for EWN is interesting and provides novel insights on pruning neural networks as the MNIST experiments show.\n3.\tMost of the paper is clearly written.\n\n### Cons (roughly ordered from major to minor comments)\n\n1.\tIt is not clear in which cases SWN and EWN are used in practice. The authors do not explicitly cite papers that use them. Therefore, it is not clear how to assess the significance of the results.\n2.\tAfter Theorem 2 it is claimed that ||w_u(t)|| is inversely proportional to ||grad_u L(t)||. I am not sure why this is correct. If ||w_u(t)|| = t and ||grad_u L(t)|| = 1/t^2 for all u, then the theorem result holds, but the claim after the theorem (mentioned above) does not hold. Am I missing something?\n3.\tIn Proposition 3, the assumption that the ratio of gradient norms is exactly c from some t onwards is very strong. The authors should comment on this. Does it hold in practice? Does the Proposition hold under weaker assumptions?\n4.\tMost of the experiments are performed on very simple datasets with few points in the training sets. I think that experiments on other datasets (e.g., with 1000s of points) can strengthen the results.\n5.\tIn Proposition 1, eta(t) is said to be a constant but it seems to depend on the loss which changes with time. What is the L in the denominator of the learning rate equation? Is it the loss?\n6.\tIn Figure 1, the neighborhood of a point for different geometries is not formally defined. The current figures are not clear.\n7.\tIn several experiments, it is claimed that the loss achieved values of order e^(-300). This seems like an unrealistic precision to get empirically. Is there a mistake here?\n8.\tThe presentation of the normalization methods in the equations in page 2 is not very clear. Specifically, why these equations result in a form of normalization. Can the updates be presented in a concise equation where the normalization is showed explicitly?\n9.\tI think that the authors should provide more context to the pruning results in Section 6. Specifically, say why the insights on EWN in previous sections can be useful for pruning applications.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "NPck5HgmCRX", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "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 studies the gradient flow dynamics over smooth homogeneous models with two types of weight normalized parameterization - standard weight normalization (SWN) and exponentiated weight normalization (EWN). Thm 1 shows the induced dynamics in the unnormalized parameter space resulting from gradient flow on respective weight normalized parameterization. This result is a good starting point that highlights the different dynamics arising from the two parameterizations.\n\nHowever, in the remainder of the paper, there are several technical issues/confusions, outlined below (p.s., please number the equations):\n\n1. In the proof of Proposition 3 and also Thm 2 (see e.g.,  last eq. in page 23 and corresponding equations for GD in Appendix E.1.2, and similarly, last eqn in page 20), the following equality is used which is not true in general. Please clarify if I missed something: ||w(t)||=||w(t_2)||+int_{k=t_2}^t ||dw(t)|| -- triangle inequality would show that the RHS is an upper bound but I do not see how we can get exact equality. \n\n2. In the proof of Thm 3 (page 20), why does Proposition 2 imply that w_u and its negative gradient are aligned in opposite directions? Specifically, why should there be a t_2 such that for all t>t_2, cos(-\\nabla_{w_u} L,w_u)<=\\epsilon?\n\n3. In Appendix D.2 (page 22) while bounding ||w_u(t)|| for SWN, along with the above two concerns, I am also not sure how the two terms in ||dw(t)|| from Thm 1 lead to the simplified bounds on ||w_u(t)|| in the first non-thm equation on page 22. \n\n4. Finally, although not a technical mistake, I believe that the discussion comparing between EWN and unnormalized GF (which I will simply call GF) is conceptually confusing. As the authors themselves note, EWN and GF both follow the *same trajectory*. EWN simply has a scaling factor of ||w(t)||^2 which affects the “speed” along the trajectory but the path itself if the same -- both have dw(t) = -s(t) nabla_w L(w(t)) for different scalar speeds s(t) and it corresponds to the same path in the space of w but with different time warping. Thus, if one solves the differential equations indefinitely both EWN and GF will trace the exact same path albeit at different times and will eventually lead to the same separator. But the plots and the discussion about Fig 5 for example suggest that EWN and GF leads to different asymptotic solutions, which is not correct.\n\nThus, when comparing EWN and GF, the message could be that EWN when discretized could lead to faster convergence - this is somewhat justified experimentally (from Fig 5) but not theoretically as to truly compare one needs to show analysis for the discretized algorithm. Also experimentally to provide correct comparison of the speed, in Fig 5, the number of iterations of the two methods (EWN and GF) should be matched which is not true in the current plots. On the other hand, it is simply wrong to phrase the message as “EWN and GF lead to different solutions asymptotically”. \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "9mqqM34fbP", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper analyzes weight normalization methods, including exponential weight normalization (EWN) and standard weight normalization (SWN), in contrast with unnormalized networks. Under a number of assumptions, the paper characterizes the asymptotic relation between weight norm and gradient norm at the node level (Theorem 2), which shows a distinction between SWN and EWN. Then it's argued that SWN leads to sparser solutions (Proposition 3), which is potentially beneficial for pruning. The paper also shows a convergence rate for SWN which is slightly faster than unnormalized and SWN from previous work, but under stronger assumptions. The paper verifies these results empirically on some toy examples.\n\npros:\n+ The exponential weight normalization method seems new.\n+ The paper has some interesting findings regarding the asymptotic behavior of weight normalization methods (if the results can be justified properly).\n\ncons:\nThe theoretical results are based on very strong asymptotic assumptions, which are not justified properly. The experiments are on very toy settings which are far below the bar. Either the theory or the experiments need to be stronger for this paper to be a solid contribution.\n\n- The assumptions (A1)-(A4) used throughout the paper are much stronger than those in previous work, such as Lyu & Li (2020). In particular, (A3) and (A4) are nonstandard. I'm not sure when these assumptions are expected to hold, and they are only empirically verified on an extremely simple dataset (4 examples).\n\n- In Proposition 3, which is where it is shown that SWN leads to sparsity, there is an extremely strong assumption that the ratio of two gradient norms at two nodes stays constant forever after some point in training. How can this possibly be true?\n\n\n---------- after rebuttal ----------\n\nThanks for the response and the updated manuscript. I'm raising my score from 4 to 5. I'm still leaning towards rejection since I still find the results quite subtle and I hope to see more empirical justifications.\n\nIn the updated Proposition 3, the sparsity-inducing property 3 assumes the existence of a time $t_2>t_1$ when the ratio between the two weight norms deviate from $1/c$. However, it seems entirely possible that this ratio will have already converged $1/c$ after time $t_1$; in this case the two weight norms grow at the same rate. It would be good to investigate this more carefully to see which cases are more likely to happen. I'm also concerned that the advantage of EWN for pruning only shows up in extremely small loss value (Figure 7), and therefore the practical relevance shown in the current paper is not very convincing.", "extra_scores": {}, "extra_text": {}}, {"review_id": "2qaMFOrrKuf", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper analyzes the implicit bias of gradient descent with both the standard weight normalization (SWN), which basically uses the gradients with respect to the radial part and spherical part of the weights, and the exponential weight normalization (EWN), which further parameterizes the radial part using an exponential function. Under a few convergence assumptions, it is shown that for SWN, given a node in the network, the norm of the input weight vector is proportional to the norm of the gradient with respect to this weight vector, while for EWN, the norm of the weight vector is inversely proportional to the norm of gradient. It is further shown that such an implicit bias implies that EWN induces sparse limiting directions, and empirical support is provided. \n\nI think SWN and EWN proposed by this paper are interesting, and it is surprising that they introduce opposite implicit biases. It is also interesting that EWN can find sparse or \"simple\" solutions.\n\nI have the following questions regarding experiments:\n1. Can Proposition 3 be verified on MNIST? For example, can you compare the distribution of norms of weight vectors for EWN, SWN, and unnormalized gradient descent?\n2. Can EWN also improve generalization or sparsity on more complicated datasets, such as CIFAR?", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The main concern is that the results in this paper are based on strong asymptotic assumptions. (At least) more empirical results are needed.

Decision: Reject