Optimization and Generalization Guarantees for Weight Normalization
Authors: Pedro Cisneros-Velarde
Zhijie Chen
Sanmi Koyejo
Arindam Banerjee
Venue: Accepted by TMLR ()

Abstract: Weight normalization (WeightNorm) is widely used in practice for the training of deep neural networks and modern deep learning libraries have built-in implementations of it. In this paper, we provide the first theoretical characterizations of both optimization and generalization of deep WeightNorm models with smooth activation functions. For optimization, from the form of the Hessian of the loss, we note that a small Hessian of the predictor leads to a tractable analysis. Thus, we bound the spectral norm of the Hessian of WeightNorm networks and show its dependence on the network width and weight normalization terms--the latter being unique to networks without WeightNorm. Then, we use this bound to establish training convergence guarantees under suitable assumptions for gradient decent. For generalization, we use WeightNorm to get a uniform convergence based generalization bound, which is independent from the width and depends sublinearly on the depth. Finally, we present experimental results which illustrate how the normalization terms and other quantities of theoretical interest relate to the training of WeightNorm networks.

Published in Transactions on Machine Learning Research (1/2025)
Optimization and Generalization Guarantees for Weight Normalization
Pedro Cisneros- "eesarro-VVeladee
pacisne com
VMware Research
Zhijie Chen University of Iilinois
luemon edu
Sanmi Koyejo Stanford University
sanmi@@s..tannordd edu
Arindam Banerjee
orindamb mondamb@illiiii...om edu
University of Alinois Urbuna- Champa-n
Reviewed on OpenReview: https: openrevveew, net/ forum? id- gpHotQQPPG
Abstract
Weight normalization (WeightNorm) is widely used in practice for the training of deep neural networks and modern deep learning libraries have built-in implementations of it. Tn this paper, we provide the first theoretical characterizations of both optimization and generalization of deep WoightNorm models with smooth activation functions. For optimization, from the form of the Hessian of the loss, we note that a small Hessian of the predictor leads to a tractable analysis. Thus, we bound the spectral norm of the Hessian of WeightNorm networks and show its dependence on the network width and weight normalization terms the latter being unique networks without WeightNorm. Then, we use this bound to establish training convergence guarantees under suitable assumptions for gradient decent. For generalization, use WeightNorm to get uniform convergence based generalization bound, which is independent from the width and depends sublinearly on the depth. Finally, we present experimental results which illustrate how the normalization terms and other quantities of thcorctical interest relate to the training of WeightNorm networks.
1 Introduction
Weight normalization (WeightNorm) was first introduced by Salimans and Kingma 2016).. The idea is to normalize each weight vector- by dividing it by its Euclidean norm in order to decouple its length from direction. Salimans and Kingma (2016) reported that WeightNorm able to speed-up the training of neural networks,
alternative to the then recently introduced and still widely-used batch normalization (BatchNorm) [Loffe and Szegedy 2015). WeightNorm is different from BatchNorm because it is independent from the statistics of the batch sample being used at the gradient step. It is also different from another class of normalization, called layer normalization (LayerNorm) (Ba et al. 2016) in that it does not entail the normalization of any activation function of the neural work. Thus Weight also has less computational overhead because it does not require the computation and storage additional mean and standard deviation statistics as the other methods do. However, its empirical testing performance (or accuracy) has often been found to not be good other normalization methods by itself, and thus various versions have been formulated to improve its performance (Salimans and Kingma 2016 Huang et al. 2017 Qiao et al., 2020 Nevertheless, WeightNorm has been one of the most popular normalization methods since its introduction, and as a result current machine learning libraries include built-in implementations of it, e.g., PyTorch 2.0
* *Corresponding author.

---

Published in Transactions on Machine Learning Research (1/2025)
Parallel to the empirical development of normalization methods, recent years have seen advances in theoretically understanding convergence of gradient descent. (GD) and variants for deep learning models (Du et al. 2019 Allen-Zhu et al. 2019 Zou et al., 2020 Nguyen 2021 Liu et al. 2022 [anerjee et al. 2023). However, to the best of our knowledge, no prior work has focused on providing formal optimization and generalization guarantees for deep models with WeightNorm. In this paper, our contribution is to study the effect of WoightNorm on both training and generalization from a thcoretical perspective. In particular, we focus on smooth networks deep models with smooth activations setting which has become increasingly popular in recent years (Du et al. 2019 Huang and Yau. 2020 Liu et al. 2022 Banerjee et al. 2023
Training a neural network is a non-convex optimization problem, and establishing optimization guarantees using GD requires analyzing the empirical loss used for training. Particularly, our analysis is based on the second-order Taylor expansion of the empirical loss, for which we require bounds on its Hessian and gradient. We observe that it possible to bound the empirical loss Hessian by using a bound on the Hessian of the network or predictor. Thus, our first technical contribution (Section 4 is a charactcrization of the spoctral norm of the Hessian of smooth WeightNNrm neural network. Similar to nelworks without, WeightNNrrm (Liu et al. 2020 Banerjee et al.) 2023), our bound decreases with width, but unlike networks without Weight.Norm, our bound also decreases with the minimum weight vector norm across all hidden layers. A similar dependence appears when bounding the norm of the empirical loss gradient, which follows from bounding the norm of the predictor gradient (with respect to the network weights). Now, towards establishing the generalization of WeightNNrrm networks, we obtain a bound on the output of the predictor which does not have any dependence on the minimum weight vector norm. Similarly, the Lipschitz constant of the network does not have such a dependency either. These results are used subsequently establish a uniform convergence bound based on the Rademacher complexity of WoightNorm networks (Section D Remarkably, all of our bounds used for est establishing both optimization and generalization guarantees have at most polynorial dependence on the depth of the network.
Our second technical contribution (Section 5 is to provide optimization guarantecs for the training of smooth deep networks with WeightNorm by GD under suitable assumptions. Using our previously derived bounds, we use the restricted strong convexity (RSC) approach recently introduced by [Banereee al. (2023) to establish sufficient conditions that ensure decrease on the value of the loss function with respect to its minimum value. In particular, one such condition relies where L is the empirical loss and V its gradient. This inequality benefits from a larger width as well as a larger minimun weight vector norm as opposed to another condition for networks without WeightNorm which only benefits from a larger width (Banerjec et al. 2023). We relate our condition to the so-called restricted Polyak-Tojasiewice (PI. condition, showing that ours is milder.
inequality (lower bound) the quantity |VV /C,
Our third technical contribution (Section 6) is to provide generalization guarantees to smooth networks with WeightNNorm. We iteratively use WeightNorm properties and our network scaling to obtain generalization gap which is independent of the network width- our bound is simply O(VL/ VT), where L is the depth and n the sample size. Thus, NeimhtNorm allows for a natural non-exponential dependence on the depth compared to networks without WeightNorm (Bartlett et al., 2017 Neyshabur et al.] 2018 Golowich et al. 2018). Our generalization guarantee uses a uniform convergence approach based on the Rademacher complexity of Weight networks.
Fourth, we present experiments on the training of WeightNorm networks (Section 7 We present numerical evidence that the convergence rate improves for larger values of (i) the ratio ||VC|/ /C, and (ii) the minimum weight vector norm. According to our theoretical results, larger values of those two quantitics strengthen the RSC property of the empirical loss, which then improves the optimization convergence rate.
2 Related work
Norgh and Other Normalizations WeightNorm was first proposed by Salimans and Kingma 2016). after a year from the introduction of BatchNorm by loffe and Szegedy (2015). LayerNorm was proposed in the same year by Ba et al. (2016), and has also become very popular (Xu et al. 2019). Extensions and variations of WeightNorm have been introduced since then, for example, centered weight normalization (Huang et al. 2017), orthogonal weight. normalization (Huang et al. 2018), and weight standardization (Qiao et. al.
2

---

Published in Transactions on Machine Learning Research (1/2025)
2020 Theoretical analysis of normalization techniques in general has caught increasing recent interest. We focus mostly on Norm,, but mention that BatchNorm has some theoretical work, e-g. (Santurkar et al. 2018 Lian and Liu 2019). The work (Arit et al. 2019) uses a theoretical approach to better come up with initialization schemes tailored for WeightNNrrm networks with RcLU activations. In contrast, our work focuses in understanding the optimization (training) and generalization of WeightNorrm net with smooth activations. [Wu et al. (2020) study the effect of WeightNNrm on the convergence of overparameterized least squares problem (which translates to normalization of the parameters to estimate). We, in contrast, study the non-convex problem of optimizing WeighNorm networks. Dukler et al. (2020) present exponential convergence guarantees on shallow ReLU networks with WeightNorm, whereas we study smooth deep networks and present generalization too. We conclude by remarking that the field of normalization is growing in proposing new normalization schemes and improving their understanding and application we refer the reader to the recent survey (Huang et al. 2023
Training Guarantecs of Neural Networks Given the incrcasingly vast literature, we refer the readers to the surveys [Fan et al., 2021: Bartlett al., 2021 for an overview of the field of gradient descent. training
of neural networks. Deep ReLU networks were analyzed by [Zou and Gu (2019); Zou et al. (2020); Allen-
ct al.
2019; Nguyen 2021 : Nguyen et al. (2021), whereas deep networks with smooth activations our case were analyzed by Du et al. (2019); Ngyeen and Mondelli (2020); Liu et al. (2022). Regarding the convergence analysis of gradient descent, Du et al. (2019); Zhu et al. (2019); Zou and Gu (2019);
Zou et al. (2020g; Liu et al. (2022) used the Neural Tangent Kernel (NTK) approach (Jacot et al, 2018 ;
whercas Banerjec et al. (2023) used the RSC approach. All training guarantecs hold over a neighborhood
around the lizatinization point of the network's weights.
Generalization of Neural Networks To the best of our knowledge, the first work in studying the Rademacher complexity for neural networks was (Neyshabur et al. 2015). Then, the seminal work (Bartlett) eet al. 2017) provided generalization bounds for neural networks considering Lipschitz activation functions. The bound, obtained using a covering approach, depends exponentially on the depth of the network. The generalization bound was tightened for ReLU activations in (Neyshabur et al. 2018) using a PAC-Bayes approach, but the same exponential dependency persisted. Then, the work (Golowich et al., 2018) avoided some exponential dependence on the depth and established conditions the norm of the network's weight, matrices in order to obtain generalization bounds independent of depth. Unlike work, all the cited works do not study WeightNorm networks indeed, we show, through suitable adaplation of such existing results, that WoightNorm allows the generalization bound to depend on VL, where L is the depth. Finally, we remark that our generalization bound estimates how well finding a solution to the empirical loss approximates finding a solution to the loss under the real data distribution. A different problem bias, ie., how a specific optimization method, while training the network, may converge to a solution that
the literature is inductive
generalizes well. This was studied for WeightNorm under GD in (Morwani and Ramaswamy 2022 and under
stochastic GD in (Li et al. 2022
3 Problem setup: deep learning with WeightNorm
Consider a training set ((x;, 1.)),,;; E X' & Rd. y EVCR. R. For suitable loss function E, the goal is to minimize the empirical loss: ((0) ( (y. f(0;x:)) where the prediction t : f(0;x;) is from a deep neural network with parameter vector 0 E R for some positive integer p. In our setting f is a feed-forward multi-layer (fully-comnected) neural network with weight normalization (WeightNorm). having depth L and hidden layers with widths my, I E [Z] == {l..... L}; and it is given by
(1 (
(W: (
(x) = xx, a. (x) =
a (11)(x) i= 1, 1..., my, l b,.
(.(1)
(1)
2
f(0:x) = VJ (x()(x)
3

---

Published in Transactions on Machine Learning Research (1/2025)
where aj (x) E R is the i-th entry of the activation function (x) E R w:"h E R is the weight vector corresponding to the transpose of the i-th row of the layer-wise weight matrix W R E [L], E TR is the last layer vector, o(.) is the smooth (pointwisc) activation function. The total set of parameters is represented by the parameter vector
= (vec(W((U), ...... vec(W(())
[.. ,VT) E ERE maME-1tmL
with mo d. The pre-activation function a E RT has its i-th entry defined by aj
a (x) ő(à, (x)),
!
E [L]. For simplicity, assume that the width of all hidden layers is the same, L.e,, my m, I E [L], and (dm+(2-13m** +m We remark that I is also called the predictor since it is the predictive output of the neural network.
Define the pointwise loss & = ((v,,)))) .) R R+ and denote its first- and second-derivative f .0)....). dù:
and E" = ( The particular case of square loss E(ys, Di) (wi - ). We denote the gradient and
dy.
Hessian of f(:x;): : IR + by Vif == (fxx)) and Vif 8 ((0x..) respectively. The gradient and Hessian of the empirical loss w.r.t. are given by
80
802
AC(0) 08
n
CC)
n n
Σ
VV
VV + +Vi
(3)
002
We denote the gradient with respect to the input data x,, E [m], by (xf(0; = 0f(0x) 8x
for any I E RR. Let -I- ll2 denote the spectral norm for matrices and L2-norm for vectors. Finally, we introduce the following convenient notation:
x=
Definition 3.1 (Minimum weight vector norm). || l|2 min
w I As an example of the
[E
notation, let (W!") mmLL y J=ill=1 and ( be two sets of hidden weights and define Jiiil=
aw + +,wr(!) for some a, 3 E R, then [[ W = minke[m (E(L]
(aw(") + +
We state the following two assumptions:
Assumption 1 (Activation function). The activation & is 1- 1-Lipschitz, i.e., 10'| S 1, and Bo Bs-smooth, i.e., |o\| S Sp.
Assumption 2 (Ouput layer and input data). We inilialize the veclor of the oulpal layer Vo R as unit vector, i.e., ||voll2 = 1. Further, we assume the input data satisfies: ||x|||2 = 1, i [n].
The assumption |x||2 = 1 is for convenient scaling. Normalization assumptions are common in the litera- ture (Allen-Zhu et al. 2019 Oymak and Soltanolkotabi 2020 Nguyen et al.) (021). The unit value for the last layer's 's weight norm at initialization is also for convenience, since our results hold under appropriate scaling for any other constant in (1).
We introduce some additional notation. For two vectors n, E R", cos(m,, #) denotes the cosine of the angle between т and #. We define the Euclidean ball around with radius p 0 by (FEc(T) == { E R. A 1|2 S p).
Finally, we point out that the original Weight paper by Salimans and Kingma 2016 also has a scalar multiplying the normalized weight vectors w:"h/ ((()) 2 I [Z]. Their work considers optimizing over such scalars whereas we consider fixed scaling for our analysis.
4 Characterizing WeightNorm bounds on the loss and predictor
To characterize both the optimization with gradient descent (GD) and generalization of WeightNorm networks, need bounds the empirical loss and predictor, well their gradients, and the Hessian of the
4

---

Published in Transactions on Machine Learning Research (1/2025)
latter. For example, the optimization guarantees in Section make use of the second-order Taylor expansion of the empirical loss &. for which we need to bound its Hessian and gradient. As seen in equation (3), the loss Hessian contains terms related to the gradient and the Hessian of the predictor f, which we then need to bound. Now, regarding our generalization guarantees in Section [ we need to obtain a bound on the values of the predictor order bound the generalization gap. We obtain this bound by using intermediate results derived from both the proofs of the Hessian and empirical loss C bounds.
All of these bounds are presented in this section, which we believe could also be of independent interest. The proofs are found in Section A and Section B of the appendix.
Theorem 4.1 (Hessian bound for WeightNNorm). Under Assumplions and 2 for any 0 E IR? with (voc, and any x,, 1 E [n], we have
V E pi
(
mm 1 +
L2 max (1x)), ((00))
V 11) so
(4)
min || [
Corollary 4.1 (Hessian bound for WeightNorm under <(0) = 0). Under Assumptions 1 and g and assuming that the activation function satisfies x(0) = O, we have for any E R with v E BEuc (Vo), and any pi
x,, E [n].
(1+ P1)L3
(7,(0;x))11 50
[W]] 2 W 12)
Vmmmin
Remark 4.1 (Comparison to networks without Weight.Norm). The recent works (Liu et al. 2020 Banerjec et al. 2023 analyzod the Hessian spectral norm bound for foodforward networks without Weight Liu et al. 2020) presented an exponential dependence on the network's depth L, whereas (Banerjee al., 2023) avoided exponential dependence upon the choice of the initialization variance for the hidden layers' weights. We show that Weight.Norm eliminates such exponential dependence for at most L independent from any initialization of the weights, which improves to 3 when ((0) = 0. Another important difference is that our bound also depends on the inverse of the minimum weight vector norm large enough values on the weight vectors decrease the upper bound. Finally, our bound is defined over any value on the weights, and not just over a neighborhood around the initialization point.
Remark 4.2 (Dependence
the activation function). Corollary 4.1 shows that the Hessian bound becomes lighter when (00) = 0 because of an additional I
Vm scaling, In contrast, the Hessian bounds by Liu et al. (200)); Banerjee et al. (2023) have the scaling y independent from the value of @(0). The reason for this difference is the use of difterent scale factors: while those two other works introduce extra scale factor
Vm on the lincar output layer, we do not. In our paper, we follow the neural network scaling as done in the seminal work on the Neural Tangent Kernel by Jacot et al. (2018).
Lemma 4.1 (Predictor gradient bounds). Under Assumptions and 2 for any O E Rp with v E BEuo
and any Xz, i E [n), we have
[Vo[(0x)))la S 00 50 (1+ (1+1)0())) (1+ (1 vI(++1))
(6)
Wllp
vm (1 -1- ()-1)))())) 2
where d/ (1 + [[000) 4(1 21) Σt
and
W
VV xx) lle + P1.
Corollary 4.2 (Predictor gradient bounds under x(0) = 0). Under Assumptions and 2 and assuming
that the activation function satisfies (0)) = 0, we have for any f E RR with v E BEuc (vo), and any x,, i E [n].
[oof - 20 so 1+ vI(I+p1)
(8)
where 03 ;= 1+
1L(1 +
W
5

---

Published in Transactions on Machine Learning Research (1/2025)
Remark 4.3 (The Lipschitz constant is the same for networks of any depth). Surprisingly, the Lipschitz constant of the network -uulke networks without Weight dore not explicitly depend on the depth L of the network nor its width m. It depends on the radius P1 which can be set to be a constant O(1). This is a direct effect of WoightNNorm: when computing xf;() we use a chain-rule argument that depends on the product of Jacobians of the output a at layer / with respect to the previous put a ((-11), and we show each Jacobian has at most unit norm due WeightNorm. Thus, no matter how deep
the network is, the final effect this product of Jacobians has on the Lipschitz constant of the network is just a constant one.
Proposition 4.1 Empirical loss and empirical loss gradient bounds). Consider the square loss.
Under Assumptions 1 and 2 the following inequality holds for any 0 E IP with v E B
[(0) S 9 O((1 +1 (l)(0))m)))
(9)
where := = 2 E.
Moreover,
|vc(()) & 2V/((0) S 200
(10)
with 09 in Lemma 4.1
Corollary 4.3 (Empirical loss and empirical loss gradient bounds under x(0) = 0). Consider the square loss. Under Assumptions and & and assuming that the activation function satisfies <(0) = 0, the following inequality holds for any RP with v E B (vo),
((0) s 5(1 p1))),
(11)
where == Ei= uZ 2 p1) Moreover, the bound in equation 10 holds with @o in Covollary 4.2
Remark 4.4 (Comparison to networks without Weight.Norm). As Remark 4.1 our bounds are polynomial on L irrespective of weight values, whereas previous results were exponential on L.
5 Optimization guarantees for WeightNorm
In this scction we prove training guarantees for WeightNorm networks under the square loss. We first introduce two technical lemmas that will be used for our convergence analysis, defining the restricted strong convexity (RSC) property and a smoothness-like property respectively. These two properties use the bounds dcrivod in Section ! All proofs are found in Scction C of the appendix.
Definition 5.1 (O% sets). Given 0 E R and E (0, Il, define Qº 10 RP ||cos( - 0. VoL(O)) x).
Lemma 5.1 (RSC for WeightNorm under Square Loss). For square loss, under Assumptions and BBue(() with 0 E TR and v, v' E BEuc(vo),
for every E 0% n P2
p.
L(0') 2 (()) + (0' 0 VoC(O))
08,0
1|0|
011
(12)
2
with
2
VoL(O)1
00,09
2
L())
(1++
VT.
vm p1) 1 L2, (001))((1,,,100
(13)
0
[W]
min [[ W2) 1I ((WWW,))&ll
where f(W', W)& = EW' + (1-11111 W) for some E E [0, 1), A , 16(0)) = vm + 122 max (1)) (0)))
and B1,, L, (0(0) /m) : 1 Ll@(0)) m. We say that the empirical loss satisfies the RSC property w.r.l. (Qº ( whenever 0g.0 0.
6

---

Published in Transactions on Machine Learning Research (1/2025)
Corollary 5.1 (RSC for WeightNorm under Square Loss and Φ(0) -). Consider the square
loss. Under Assumplions
1 and and assuming that the actination function satisfies x(0) = 0, for every
0' E 0% n BBT(() with 0 E _ and v,v's E BLue (vo), the inequality in 13 becomes
R² [oL(
00,0' = 2
(())
(11
(14)
(1+
VL
(1+ + 21) [[5("r, -I [I W)ll
|m|
Vm
W
vm min
using the same notation as in Lemma 5.1
Remark 5.1 (The RSC paramcter ag and prior work). Our RSC characterization in the left-hand side of 13 depends on [( whereas Banerjec et al. 2023 the work that introduced the RSC-based [())
optimization analysis- dellynss- on | E Vof x.)] Morcover, the minimum weight vector norm appears in the right-hand side since we used the bounds on Section
Remark 5.2 (Conncction with the restricted Polyal-Lojasiewiez (PL) inequality). The RSC condition has the form [V,C(0)1 2,4.,r where He.er depends the parameters and l', which are in turn ((0)
restricted to a specific set. This is a milder condition than the so-called restricted PL condition (Oymak and Soltanolkotabi 2019 Banerjoc al., 2023). which is satisfied whenever Meaar is a constant independent from both and 8¹ Our RSC condition becomes even milder when 6(0) 0 (see Corollary 5.1 since now the parameter p0.0r has the term 1/vm which decreases with the width.
Remark 5.3 (The right-hand side of the RSC parameter aæ). When Φ(0) 0, Corollary 5.1 shows that the right-hand side of 13 will have the scaling paramcter v.m. duc to the Hessian bound (Corollary 4.1
Lemma 5.2 (Smoothncss-like property for WeightNorm under Square Loss). For square loss, under Assumptions and] 2
for every 0,0' Re with v,v' BBuc
Bo.0 110 012
L(0') < [(0) (0' - 8, VoL(O))
(15)
2
with
30.0 S O
L A 12,1,, + p1)²
1+
(16)
fair)) f(W", we
where f(W', W)₂ = <W' (1- for some & [0, 1], A(L, A(L. (1 L2 max (())) 2 }m)
Corollary 5.2 (Smoothness-like property for WeightNorm under Square Loss and d(0) = 0).
Consider the square loss. Under Assumptions 7 and 2 and assuming that the activation function satisfies
<(0) = 0, for every 0, 0' E BP with v. E Buu (Vo), the inequality in 16
becomes
B0.0 S <0
(1+
La p1)²
(17)
S m (il ssll 11 F[WW (F(WW.)e w)
using the same notation as in Lemma 5.2
Remark 5.4 (A stronger notion of convexity and smoothness). If the expressions in equations
12
and 15p hold for any 0,0 0' E R so that 0g,8 = a and B0.0r = 3 O, then we have the definitions strong convexity and smoothness, respectively mereelvvelymmoroveeerr,, it immeddatell follows that $ <.
The following assumptions are useful for establishing our convergence decrease on the loss value is guaranteed as long as these assumptions are satisfied.
byssis--indedd, as we shortly show, a
Assumption 3 (Iterates' conditions). Consider the iterate 0, E R with v, E BBac(vo) and that: (A3.1) gradient descent (GD) update 6,41 0t M). ((e:) with learning rate ne chosen appropriately so that V++1 E Eue (vo); (A3.2) 02 is chosen that Oz41 BEucc(). (0.).

---

Published in Transactions on Machine Learning Research (1/2025)
The first statement in Assumption ensures that gradient descent has an appropriate learning rate. The second statement defines a ball around the current iterate that should cover the next iterate in principle, its radius could be defined after defining the learning rate of GD of the first assumption; more details in Remark 5.7
Finally, we present our main optimization result: a reduction on the empirical loss towards its minimum value (with the last layer in the Euclidean set of radius p1) using gradient descent. This is proved by using Lemmas 5.1 and 5.2 and an adaptation of (Banerjee et al. 2023 Theorem 5.3); see Section C.2 of the appendix.
Theorem 5.1 (Global Empirical Loss Reduction for WeightNorm under Square Loss, (Baner- jee et al. 2023 Theorem 5.3)). Let Be Q% n B (0.) {0 RpIv ( 0" E
-(0))-((0)) Let 00, be as in Lem- arginf DE (0ERP vE " (vo)) [(0), Be E arginfoen, [(0), and Yt = [(0.) (((r)-
mas 5. and 5.2 respectively with Se, =30, 0011 = Bo, 0, VoL(... Consider Assumptions 7 and 3 and the RSC properly 00 a. > 0. Then, we have 7/t E [0, 1); and is (((.)) + L(0"), then for gradient descent wilh
- slep size 1/: 3o.² we have R E (0, 1] and Do.
- < (1 (1- 08 0: (1 1:) (1-))) (2(0,)
(18)
Bo,
The result in 18 implies training convergence as the mumber of iterations increase. Since the rate at which the loss decreases is time- and weight-dependent in (18), it is difficult to establish the number steps needed for convergence to specific loss value; however, this shows that our framework may cover cases where the convergence rate is heterogeneous across iterations. Finally, we note that the rate is always guaranteed to be less than onc.
Remark 5.5 (Important differences with respect to networks without WeightNorm). Theorem 5.1 differentiates from (Banerjee et al.] 2023 Theorem 5.3) in that (i) it is deterministic, i.e., it is not stated as holding with high probability; (ii) does not have all the weights of the network defined over a particular ncighborhood (with the exception of the output linear layer). Indeed, these differences also hold for all the
previously derived results in Section | and Section 5] We summarize the comparison between our results
and those for networks without WeightNorm by Banerjee et al. (0223 in Table from Section D of the appendix.
Remark 5.6 (About the radius P2 in Assumption 3). We prove in Proposition C.2 of the appendix that. VI
for the case of ((0) = 0, [10++1 - 0ell2 S n - ((1 21 1 /m /m]lw ) Note that P2 as in Assumption 3
could in principle depend on t, and thus we could set P2 to be equal to the upper bound just shown for [[0+1 - 2el12- Remarkably, ?e as chosen in Theorem 5.1 can be upper bounded by one and if [Wa (| has a uniform lower bound across & (note that our experiments in Section provide evidence for || 2 [W (oll))
then the upper bound of [|0z+1 0ell2 becomes a constant independent of l, and so does P2 to satisfy (A3.2) in Assumption 3
Remark 5.7 (About gradient descent in Assumption 3). Regarding (A3.1) in Assumption 3 we
remark that we are only considering that the weight vector of the output layer is inside a neighborhood of its initialization value across iterations- no constraint exist on the weights from the hidden layers. Moreover, the radius P1 of this neighborhood region can be set to be any arbitrary constant of order @(1) or even a polynomial of L; thus, P1 is not assumed to be arbitrarily close to zero and the neighborhood not restrictod to be arbitrarily small. These arguments imply that. our optimization guarantees are not restricted to be in the lazy training regime (Liu et al. 2020). We also point out that (A3.1) is necessary assumption so that the linear output of the neural network, which has no normalization, remains bounded. Finally, we remark that (A3.1) is not stronger than other existing works where assumptions of closeness around initialization
points are needed even on the hidden weights; e.g., see [Lu et al. 2020 2022 Banerjee et al. 2023).
We can set So. that S So, from 17 and
Po. 11
8

---

Published in Transactions on Machine Learning Research (1/2025)
6 Generalization guarantees for WeightNorm
We establish generalization bounds for Nergh networks. Our bound is based on a uniform convergence argument by bounding the Rademacher complexity of functions of the form (1) as long as the last layer vector v stays within a ball of radius the same condition we used in our optimization analysis. The core of the analysis relies on the use of a contraction-like property across the network layers similar (Golowich) et al., 2018) and uses WeightNNorm and the network's scaling to avoid exponential dependence the depth and avoid any dependence the width. All proofs are found in Section E of the appendix.
Consider the training set S = {(x; vi) ~ D, E [n]}, where D denotes the true but unknwon distribution. The training and population losses are respectively defined as
Cs(0)
elys f(0:x:)) and CD(() = -(x))
We added the subscript S to the empirical loss notation to explicitely denote its dependence on the training set 5.
Theorem 6.1 (Generalization Bound for WeightNorm under Square Loss). Consider the square
loss and the braining set S ((x hid. D E [n]} and lyl S 1 for any y ~ Dy with probability one. Under
Assumptions 1 and 4 assuming the activation function satisfies <(0) = =, with probability at least (1 6)
over the choice of the truining data Dx, E [m], for any WeightNorm network f(0;-) of the form (1 with
any fized 0 E I2 and v p1 (vo),, we have
2 (2log(2)L +1 + 2(11 + (1+ 31)
loo(22/)
- < 4(2 pz) p1)
(19)
Vn
Vn
Remark 6.1 (About the activation function). Theorem 6.1 unlike our previous results in the paper. requires the smooth activation function to satisfy x(0) = As mentioned earlier Remarks 4.2 and 5.3
the case when ((0) = 0 improves our Hessian bounds and thus improves our optimization conditions by introducing a better dependence on the width m. We point out that commonly used activation functions such the hyperbolic tangent function tanh and Gaussian Error Linear Unit (GELU) satisfy both d(0) 0 and Assumption
Remark 6.2 (The independence from the width m and the dependence on depth L). The generalizaton bound (19 does not explicitly depend on the network's width, but explicitly depends on its depth. Setting P1 = (1), a choice which does not negatively affect our optimization results, results in a generalization bound of 0(14) Elfectively, for deeper networks, we would need increase the number of samples at least lincarly on the depth to improve our generalization bound-in practice, the number of samples is usually much larger than the network's s depth. This is a benign dependence that WeightNorm allows compared to an exponential one found in networks without WeightNorm (Bartlett et al. 2017 7 Neyshabur et al. 2018 Golowich et al. 2018
7
Experimental results
We show empirical results to support our theory. In our experiments, the Weight.Norm networks are fully connected with two hidden layers of equal width m, tanh activation function, and linear output layer. We do empirical evaluations on CIFAR-10 (Krizhevsky) 2009) and MNIST (Deng) 2012). Because of computational efficiency, we apply mini-batch stochastic gradient descent (SGD) with batch size 512 to optimize the WeightNorm networks under mean squared loss. In our experiments we are only concerned about the training of WeightNorm networks from an optimization perspective the fact that the training error minimizes across epochs enough for our purposes. Therefore, using a squared loss with a lincar output in our experiments suffices as opposed to cross-entropy loss with softmax output layer. Our experiments were conducted on a computing cluster with AMD EPYC 7713 GorC Processor and NVIDIA A100 Tensor Core GPU.
In our theory, the convergence rate as in Theorem 5.1 is directly proportional to the RSC parameter 0g, 0g becomes larger under two
and it benefits from larger positive 0g, According to equation 13
9

---

Published in Transactions on Machine Learning Research (1/2025)
0.020
0.393
0.999
0.018
0.998
0.392
0.016
IC. IWE
0.997
0.014
0.996
0.012
2048
2048
0.995
0.010
0.300
0.008
0.389
0.006
100
175
150
Epachs
Epochs
(a)
(b)
Figure 1: Training neural networks for two different widths m E (1024, 2048} the CIFAR-10 dataset, with two hidden layers L = 2 of same width, with learning rate 0.001, and weights initialized independently from a uniform distribution | vm I.1. Each subfigure plots: (a): min 1E[4]
(b): (VZ(0)))22//(00 where
represents the number of iterations.
conditions: as the ratio \VC(0))3/C((0) increases and/or the minimum weight vector norm min
w
1,t
[E
increases. Then, the relevant qucstion is: Can we prowide empirical evidence of these two conditions benefiting convergence during training!
We provide an affirmative answer in our simulations. We present our experiments on CIFAR-10 in Figure and on MNIST Figure 2
We first focus the effect of the ratio (VV that the values for the minimum weight vector stay nearly constant across epochs for both networks (in reality, they increase in value very slowly), i.e., the second term in the RSC parameler cæ,, (see equation (13 basically remains stable. Therefore, according to our theory, the convergence speed should mostly depend on the ratio [[.) /l3/ [(O,), i..., the first term in the RSC parametor og,, (sce equation [3))). Indoed, this is expressed in Figure [b): the curve of the ratio (VL(0.)1B//(0)) has decreasing trend towards the end of training for both networks (starting at around epoch 75) while the curve of the loss ratio between two consecutive epochs ((0++))/((,, has an increasing trend. Therefore, since an increase in the ratio L(0++1)/ [(::) corresponds to decrease convergence speed, both networks have slower convergence than they had at the initial epochs.
the RSC parameter. In Figure [a), we show
Next, we focus on the effect of the minimum weight vector norm on the RSC parameter. According to our theory, the two networks in Figure | have the same value for the ratio [[V (B/((()) the network with the larger minimum weight. vector norm will have a larger RSC parameter (see equation (33), and so we would expect such network have faster convergence. Indced, we observe this in our experiment: when the red solid curve crosses the dashed red curve (around epochs 70 and 115) in Figure Dbb, the two networks have the same value for ||VC(0,)) [(()). At this crossing, Figure [bb) shows that the network with larger width-and so with larger minimum weight vector ((0,)))/C(O.) for the green dashed curve has smaller values than the green solid curve).
converges faster afterwards (i.c., the loss ratio
We present similar results on the MNIST dataset in Figure 2 For example, similar to Figure ! the minimum weight vector norms for both networks Figure 2 are practically stable, which results in the convergence speed changing according the changes in the ratio (VC()))B/C(()) Interestingly, the two curves of the ratio ||VL(0)))] C(0+) do not cross, but they become very close value around epoch 25. After this,
10

---

Published in Transactions on Machine Learning Research (1/2025)
1.2250
1.000
0.975
1.2200
1.2175
190901 109/
1,2150
2024
-...
1024
0.500
1.2125
0.875
1,2100
1.2075
500
Epochs
Epachs
(a)
(b)
Figure 2: Training neural networks for two different widths m E {512, 1024] on the MNIST datasct, with two hidden layers L 2 of same width, with learning rate 0.001 and the weights are initialized with a uniform distribution | V J- Each subfigure plots: (a): minge[m 1e[4]
w/( 3,
(b): [VL(0))) where
represents the number of iterations.
observe that the wider network, which is the network with the larger minimumn weight vector norm, keeps achieving faster convergence for the rest of epochs despite having lower values of the ratio [[
8 Conclusion
We formally analyzed the training and generalization of deep neural networks with WeightNorm under smooth activations. For this needed characterize a series of bounds which highlighted the dependence of our results on the depth, width, and minimum weight vector norm. Our simulations showed the possibility that our training guarantees hold in practice. We hope our paper will elicit further work on the theoretical foundation for other types of normalization whose connection to training and generalization are not well explored.
Acknowledgments
Part of the work done when Pedro Cisneros-Velarde affiliated with the University of Illinois Urbana- Champaign and was concluded during his current affiliation with VMware Research. The work was supported in part by the National Science Foundation (NSF) through awards IIS 21-31335, OAC 21-30835, DBI 20-21898, as well as a C3.ai research award. Sanmi Koyejo acknowledges support by NSF 2046795 and 2205329, NIFA award 022067701-32299, the Alfred Sloan Foundation, and Google Inc.
References
Pytorch 2.0. Pytorch 2.0 documentation. http:://pppooo.oooooo//////aa/aa utils
weight_noree norm html Accessod: 05-09-2023.
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. In Proceedings of the 36th International Conference Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 242-252. PMLR, 2019.
Devansh Arpit, Victor Campos, and Yoshua Bengio. How to initialize your network? robust initialization for weightnorm resnets. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
11

---

Published in Transactions on Machine Learning Research (1/2025)
Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E. Hinton. Layer normalization, 2016.
Arindam Banerjee, Pedro Cisneros-Velarde, Libin Zhu, and Misha Belkin. Restricted strong convexity of deep learning models with smooth activations. In The Eleventh International Conference on Learning Representations (ICLR), 2023.
Peter Bartlett, Dylan Foster, and Matus J Telgarsky. Spectrally-normaaized margin bounds for neural networks. In Advances in Neural Information Processing Systems (NeurIPS), volume 30, 2017.
Peter I.. Bartlett, Andrea Montanari, and Alexander Rakhlin. Deep learning: statistical viewpoint. Acla Numerica, 30:87-20 201, 2021.
Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford University Press, 02 2013. ISBN 9780199535255. doi: 00.1093/acpro oso oso 2to/9998019953555500000000
URL https://doi: org/ 12///10.010 1093/ 1wwp//009/0/::0./o :tt 001 0001
Li Deng- The mnist database of handwritten digit images for machine learning research. IEEE Signal Processing Magazine, 29(6))141 142, 2012.
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Reseorch, pages 1675-1685. PMTR, 09-15 Jun 2019.
Yonatan Dukler, Quanquan Gu, and Guido Montufar. Optimization theory for ReLU neural networks trained with normalization layers. In Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Muchine Learning Research, pages 2751 2760, 2020.
Jianqing Fan, Cong Ma, and Yiqiao Zhong. A selective overview of deep learning. Stotistical Science, 36(2): 264 2900, 2021.
Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity of neural networks. In Proceedings of the 3ist Conference On Learning Theory, volume 75 of Proceedings of Machine Learning Research, pages 297-299, 2018.
Jiaoyang Huang and Horng- Tzer Yau. Dynamics deep neural networks and neural tangent hierarchy. In International conference on machine learning, pages 4542 4551. PMLR, 2020.
Lei Huang, Xianglong Liu, Yang Liu, Bo Lang, and Dacheng Tao. Centered weight normalization in accelerating training of deep neural nelworks. In Proceedings of the IEEE International Conference on Computer Vision (ICCV), Oct 2017.
Lei Huang, Xianglong Liu, Bo Lang, Adams Yu, Yongliang Wang, and Bo Li. Orthogonal weight normalization: Solution to optimization over multiple dependent stiefel manifolds in deep neural networks. Proceedings of the AAAI Conference on Artificial Intelligence, 32(1), Apr. 2018. doi: 10.1609/ wit.a.......11.6..
Lei Huang, Jie Qin, Yi Zhou, Fan Zhu, Li Liu, and Ling Shao. Normalivation techniques in training dnns: Methodology, analysis and application. IEEE Transactions on Pattern Analysis and Machine Intelligence, pages 1-20, 2023. doi:
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In Proceedings of the 32nd International Conference on Machine Learning, volume 37 of Proceedings of Machine Learning Research, pages 448-456. PMLR, 2015.
Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural tangent kernel: Convergence and generalization in neural networks. Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
Alex Krizhevsky. Learning multiple layers of features from tiny images. 2009.
12

---

Published in Transactions on Machine Learning Research (1/2025)
Michel Ledoux and Michel Talagrand. Probability in Banach Spaces. Classics in Mathematics. Springer Berlin, Heidelberg, 1991. doi: 10.1007/998-33-122222222
Zhiyuan Li, Tianhao Wang, and Dingli Yu. Fast mixing of stochastic gradient descent with normalization and weight decay. Tn Advances in Neural Information. Processing Systems, volume 35, pages 9233 90-8,9484-4 2022.
Xiangru Lian and Ji Liu. Revisit batch normalization: New understanding and refinement via composition optimization. In Proceedings of the Twenty-Second Second International Conference on Artificial Intellignnce and Statistics, volume 89 of Proceedings of Machine Learning Research, pages 3254-3263 PMLR, 16-18 Apr 2019.
C. Liu, L. Zhu, and M. Belkin. Loss landscapes and optimization in over-parameterized non-linear systems and neural networks. Applied and Computational Harmonic Analysis, 59:85-14 116, 2022.
Chaoyue Liu, Libin Zhu, and Misha Belkin. On the linearity of large non-linear models: when and why the tangent kernel is constant. In Advances in Neural Information Processing Systems, 2020.
Depen Morwani and Harish G. Ramaswamy. Inductive bias of gradient descent for weight normalized smooth homogencous neural nets. In Proccedings of The 33rd International Conference Algorithmic Learning Theory, volume 167 of Proceedings of Machine Learning Research, pages 827-880, 2022.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control in neural networks. In Peter Grünwald, Elad Hazan, and Satyen Kale, editors, Proceedings of The 28th Conference on Learning Theory, volume 40 of Proceedings of Machine Learning Research, pages 1376-1401, Paris, France, 03-06 Jul 2015. PMLR.
Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. A PAC-bayesian approach to spectrally- normalized margin bounds for neural networks. In International Conference on Learning Representations, 2018.
Q. Nguyen and M. Mondelli. Global convergence of deep networks with one wide layer followed by pyramidal topology. In Neural Information Processing Systems (NeurIPS), 2020.
Quynh Nguyen. On the proof of global convergence of gradient descent for deep relu networks with linear widths. In International Conference on Machine Learning (ICML), 2021.
Quynh Nguyen, Marco Mondelli, and Guido Montufar. Tight bounds on the smallest eigenvalue of the neural tangent kernel for deep relu networks. In International Conference on Machine Learning (ICML), 2021.
S. Oymak and M. Soltanolkotabi. Towards moderate overparamcterizaaton:: global convergence guarantocs for training shallow neural networks. IEEE Journal on Selected Areas in Information Theory, 2020.
Samet Oymak and Mahdi Soltanolkotabi. Overparamcterized nonlincar learning: Gradient descent takes the shortest path? In International Conference on Machine Learning (ICML), 2019.
Siyuan Qiao, Huiyu Wang, Chenxi Liu, Wei Shen, and Alan Yuille. Micro-batch training with batch-channel normalization and weight standardization, 2020.
Tim Salimans and Durk P Kingma. Weight normalization: A simple reparameterization to accelerate training of deep neural networks. In Advances in Neural Information Processing Systems, volume 29, 2016.
Shibani Santurkar, Dimitris Tsipras, Andrew llyas, and Aleksander Madry. How does batch normalization help optimization? In Advances in Neural Information Processing Systems, volume 31, 2018.
Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning: From Theory to Algorithms.
Cambridge University Press, 2014.
Xiaoxia Wu, Edgar Dobriban, Tongzheng Ren, Shanshan Wu, Zhiyuan Li, Suriya Gunasckar, Rachel Ward, and Qiang Liu. Implicit regularization and convergence for weight normalization. In Advances in Neural Information Processing Systems, volume 33, pages 2835-28477 2020.
13

---

Published in Transactions on Machine Learning Research (1/2025)
Jingjing Xu, Xu Sun, Zhiyuan Zhang, Guangxiang Zhao, and Junyang Lin. Understanding and improving layer normalization. In Advances in Newral Information Processing Systems, volume 32, 2019.
Difan Zou and Quanquan Gu. An improved analysis of training over-perameterized deep neural networks. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Gradient descent optimizes over- over- pa-aacctttrrzzed deep relu welkorks Machine Learning, 109:467 492, 2020.
A Spectral norm of the Hessian for WeightNorm
We establish the main theorem from Section Theorem 4.1 (Hessian bound for WeightNNrrm). Under Assumptions and 2 BEuc (V)), and any X,, i [n], have
for any 0 E IR with
(1+ (L+ 1 + L2 max (nax(1@(0)) (l)()), ()))
x1)10 50
(4)
min [1W | [
A.1 Starting the Proof
For an order-3 lensor T E Rdd xd2xds we define the operator || 11-112,2, as follows,
de T Tiz
222,2,211
sup
E Rd
R2
(20)
||x|| xx|la
j=1
Let us consider any E Rd such that ||x|| Vd. Our analysis follows the general structure developed
in Liu et al. 2020
Theorem 3.1). We first observe that
0 x() (0A)2
8 f(0:x)
0 f(;(0xx)
ff((0:)
<
+2
Ow(L)) OWL11)
+
(1)
11/2==1
4=1
L
0P f(0:))
22 f():x)
Σ
+
(21)
(W(4))W(())
@W (W)
h.4=1
where the equality follows by noticing that, since W(++1) =v,
8 f(0x)) (WWetny
= 0 for (i,j) E [m]] [m], and
8 ((0x))
So
ToWiLTny
0.
From now on, for simplicity of notation, we will obviate the dependency when necessary.
Now, again from the proof of (Liu et al. 2020
Theorem 3.1), for 1 I l S la S L,
2² @0)
0f da(li)
aw aw())a(())
(aw(1))2
2,2,1
(1)
(a
(la(2))
0f (12)
+ 1|zi
II
Ow())
(a(1-1)
dalls - (1)
1=4++1
2,2,
80
(22)
+ 1 |
(1)
(b)
Σ
II
[W
1a
(0a!!-1)p2
1=11+11
1=
2,2,1
ta!h
0ʃ
x II
(a!1-1)
Fai
1=
14

---

Published in Transactions on Machine Learning Research (1/2025)
We use the following conventional notation: if product has the form IT 2 where b given some real scalars {2:) where 2 b, then I O)
Now we proceed to obtain upper bounds for all the required terms in the previous expression.
A.2
Upper bounds of the Lz-norms of a
Lemma A.1. Consider Assumption For any E [L], any x Rd such that ||x|| = 1, and any 0 IR, we have
|1a0 (x)ll2 +1+1((()))
Proof. Following (hllen-Zhu et al. ||x||2 = by assumption, we have
2019 Liu et al. 2020), we prove the result by induction. First, since a [x
2 1. Since & is 1-Lipschitz,
1)
(Wo
(0)
10)()) S
Φ
(0)
(00)
(2)
m
(x
(W ( T
(0)
m
( (1)
that
(1)
ll (1)
1
(0)
5
(0)
+ [1)(0)]22
m
Wi())
(1)
m
((1)
(1)
2
2
1
1
m
(W((1)
((1)
(000)/m
mml
||00011 lo(0))
= 1 1+ (0(0)//m
where (a) follows from Stauuch-SShwaane For the inductive step, we assume that for layer - 1, we have
la 122 S (1 + (2 1))0(())))
Since o is I-Lipschitz, for layer I, we can similarly conclude that
(W (1) (1)
(1) T a (1-1)
(111
(0)l)) <
m
w
2
2
15

---

Published in Transactions on Machine Learning Research (1/2025)
that
(W!()) T
(w:t))
1a0012
a1111)
-
all-1)
+1)((0)l2
m
m
(!!!)
2
2
|all 1) 122 + 1
m
(a)
(1 + (1-1)) + +000)
1 + (00)mmm
where (a) follows from the inductive step. This completes the proof.
A.3 Upper bounds on the spectral norms of BW
and
Lemma A.2. Consider Assumption 1 For any E {2,... .., LJ, any x E IRd such that ||x||| = Vd, and any
A R2, have
aa (x)
11,
(23)
(c(l11)(x))
and
0a (x)
(x)
51.
(24)
Da (0) (x))
Ox
Additionally, under Assumplion with v E Bp BBuc(vo),
0f(x)
11+ PI-
(25)
da(l)(x))
2
Proof. By definition, we have
1a
w
l'aa!))
(26)
1alll-1) i.
vm
w
Then, we have that for 2 1 L,
(1
W-(1)
d'(a!") (1)
(a!l-1)
||v]|==1 771
sup
w
V,
(W,(1)) T
sup
m
||v1|
sup
m |
|w
m
16

---

Published in Transactions on Machine Learning Research (1/2025)
where (a) follows from & being 1-Lipschitz by Assumption [
Finally, it is easy to follow the same proof and
show that 00 8a
2
S 1. This completes the proof for equation 24
Finally, for proving equation 25 note that
= lIvila S [[vll2 + || volla $ (1 + (p).
8atzy
2
Lemma A.3. Consider Assumption
For any 1 E [L], any x E Rd such that ||x||2 = 1, and any 0 E IRP, we
have
(x)
2
1 (Vm + (1 1)16101).
(w!!
w!!)
(27)
12
[m]
Proof. Note that the parameter vector w(t = vec(W(1)) and can indexed with j E [m] and j' E [d] when 1 and j' [m] when > 2. We will do the analysis for > 2 since a similar analysis holds for the case
= 1. Thus, we have
(
awws
(!)
6.3
1.55"
( (1-))
0
= =(((
1i==
aw aW j.''
m
w
((W(1) T Ta a1-1)) Es'
o'(ā("))
1
(1-1)
(28)
aj
b=
vm
w:(()
('(a(")
a
(1-1)
o'
d(al") ((W!") I
1)
1
レ=
m
W
(1)
Vm
2
(17)
where we used the fact that
)
① aW )
| || )
Wer
2
Defining the matrices A, B mmmm² by [A]a,g (T) and [B]ss (TT), we observe that
SW A B.
0a
17

---

Published in Transactions on Machine Learning Research (1/2025)
da Then, noting that away Rmxm" and | l|vee ( for any matrix V, we have
(1-1)
(a
||1122 = sup
1 [==
V 33'
|
3='==1
mm
W
b(aa; (1)
(1-1)
aj
sup
V 13'
||V||==
mm
s=1
(1-1)
1 sup
E5''
m [Vil==
W
(1)
1
sup
(1-1)
2
|
11
m
[
(1)
|aa-1)1
Σ
2 sup
m mmi
W((0
||V||==
(1
(w(0)
2
m min
2
1
+ (1 1)1(())))
2
vm
minse[m]
where (a) follows from Lemma A.1
18

---

Published in Transactions on Machine Learning Research (1/2025)
Similarly,
(( ((W,
B sup
29'
V 15'
MV
j+'=1
m
m0(1)
('(a. (aal-)
sup
if
Voy
<=
vm
(Iw!!0) x )²
2
sup
X|X m==1
(w aa-1))2
|w:00/ 1|2 V
sup
|[]]
(1-1) 12
11 V..11
sup m [
W
aa(-111 11
|V
sup
|[V|
1=1
||a4-1112
m min
1
+ (1- 11lo(o1))
Vm
min ml)
2
where (a) follows from Lemma A.1
Using the recent derived results, we have
(a
2
(1 (1 1)((()))
||All2 + |B11,
@W
w,10)
2
min [m(m]
That completes the proof.
A.4 Bound on |1:1122211
Lemma A.4. Consider Assumption 1 For any x E Rdd such that ||x||2 and any 0 E RP, each of the following inequalities hold,
Bo,
(29)
(x))
1)
2,2,1
(x) (x)
2(3ol (m + (1 1){{(0)) + 1)
(30)
Da 1011-1)(x))) (x))((()
w(())
2,2.1
minje(m]
2
for = 2,...,4. L; and
8 8a (x)
2(2 mm
+ 1))(())) + +3) 1 + (2 ()))
m
(31)
(OW(1)²
(1)
2,2,1
min
19

---

Published in Transactions on Machine Learning Research (1/2025)
for E [L].
Proof. For the inequality
29
note that from
26
we obtain
oal!
1
(a!"")
ik
19
(Da(l-1))2
m
|
and
ea
1 m
6" (((")) (wW!0) (TN())TT)((H ())
(0a(1-1)33
sup
2,2.1
ll I
m7
m
((W:)) T Tv ((W My (TvT2)))))))))
<
sup
m
|
v2ll2
w
2
W 1|
w
||2ll
sup
m
|
=
V:
21
w
(1)
2
3p
m.
(32)
m
For the inequality
30
carefully following the chain rule
26
we obtain
a2 (a((-)))0)))
w
(1-1)
= (a()
ag
EjAKk
Vm
Vm
w 2
(1)
(W
[
vm
w-(O)
v-(() 59
('(a.")
1 [===)]
+
1
1
[==
Vm
w
(1)
w
2
20

---

Published in Transactions on Machine Learning Research (1/2025)
Then, we have
2,2,1
m
m
(a
((/m
w
Ok''
(1-1)
||v/l==IVVall
sup
! (2)
w (1)
(W! (all W
it'
(1
mm
w w- (1) sk
1
0 (a!!))
[t' [=
V1.s V2,en
Vm
vm
W (1)
W (1)
((())
sup
(a
17
(1-1)
V1. V2,0
m
(1)
(wW(1))
(1 3
ΣΣ (a("
w: ik!
V1.5 V2,
(33)
2
v (((
(1)
3
Vis
V2.kk +
m
1
p'(a!!)
|w
112
Vi.i
V2,5 Vi.5V
(
sup
8" (a !1)
|w:00
2 R
1)
V1.
V2.5
| 11 =
W (1)
)(W())a((1))
((-1)
("(a!()
10()) ik' V1. V2,5
sup
|
1=1
M
W (1)
w::0 (1)
sup
2 (a!")
w: (1)
V1.5 Va.a
||
V2
P=1
0 (a.))
1
sup
ViJ
2.15
|v.||,=||V.
m
w,(0)
21

---

Published in Transactions on Machine Learning Research (1/2025)
Now we upper bound each of the terms in the last inequality. We analyze the first term,
W
sup
(a
(1-1)
Vi.j
22,i
llvll,=
Vol
1=1 k=
m
| ||
36
sup
V1.5
o'k
(1- 1)
V2
||vi 111.=111 [V2ll==
(1)
1|v1l2
V
V2a (1-1)
sup
171 ||vil|2
[V
w
8
sup
Σ
1
V2
(11-1)
171
2|
w
(6)
1)
W (
(6) Bp 1 ())]o(())
1
Vm
Vm
Vm
min
w:
2
Bol
+ (1 --)))(())
w/!)
minic(m)
where (a) follows from applying Schway- first with respect the dot product described by the index
and then the index (b) follows from ||2ll2 I ||V2llr; and (c) follows from Lemma A.1
22

---

Published in Transactions on Machine Learning Research (1/2025)
Now we analyze the second term,
((W
) (all1))
sup
1 8² (aa!)
|
1j
1 11
W (1)
sk" V1.5 22,
M -
k'=
2
36
m
(w T (111
w-(1
172
W-l1)
sup
ik!
V2
2,0
[]v
wwil2=10 [2
(
W
8
172
m
(1)
m
(1)
ik!
sup
Vidi
2,2k
m
||v1l22
Vall
(1)
w((
(a)
l 2
m
a
(1-1)
sup
12...
1 lla = 1|22l
Σ 1/ l
(-11)
sup [
|22ll
m
[vill==|V Vall
W
36
m
(-1)
a
w
(6) 33
+ (1 - ()())))))
Vm
Vm
w:(0
minee mm]
3 mm + (1 1)))(()))
min.e(m]
where (a) follows from successive applications of the Cauchy-Sehwarz inequality; (b) follows from Lemma A.1
23

---

Published in Transactions on Machine Learning Research (1/2025)
Now we analyze the third term,
m
m
W ik!
sup ||v
Vm
(a
||
will
ij v1. V2,ck
Vall
V1
j=1 R'
W (1)
sup
ViJ
V 2,5
m ||v
(
w !1)
i=1
12
| 2
2 l1
sup
[ill2
V2lp
Wr(0)
1
| VVll
sup
|
W (1)
==1
1
min.e(m) [m]
w0l0 2
where (a) follows from successive applications the Cauchy-Sehwaer Schwarz inequality. Finally, for the fourth term,
sup |vv|_=IVa
(a;
w:(0)
V1.j V2.i5
Val
1=1
m
m
sup
V1 V2.5
m minge|m]
w
||v|l2==||
m
sup
2. 112 l|v1ll
m min
w
i=1
sup
V2 V2,x2l2 1l2
m minse[m]
[|Vall
m
V 2, l1
sup
m
m minje(m] [m]]
w::0
11 =
1
min
24

---

Published in Transactions on Machine Learning Research (1/2025)
Then, taking all the analyzed terms back in 33 we obtain
aa
28 mm + (1 - ()))
2
1,2211
minje(ml
minse(m]
2
2(Bb( (/m + (1 1)(((0))) +1)
|
minge[m]
which proves the inequality (30).
We now analyze the last incquality 31
Carefully following the chain rule in
28
we obtain
8aa0
(DW())2
(1-1)
((W
w
(a()
Ap=
vm
||w//0//
|
(111)
Ta (WW,()) )
1
x
Vm
|||,/00
(x:00)
1 [
(1-1)
+d((a(")
+
1 |ي=
1-(1)
1 [===]
mm
||
(11)
((W)")) ( (a(l-1))
((W:0)Tad (1)) mr())
o
53
M=j 3
1 |-=1
(
|w:00
s
|
2
25

---

Published in Transactions on Machine Learning Research (1/2025)
Then, we have, after some careful calculation,
8a
(2W()2
2,2,1
m
(1)
1
aft
( T
w (
sup
(a
II.
,
1ml
o'=1k==1 ==
vm
W
1
(1-1)
Ta (wW
T
ik!
V1.5 V2.5
m
||m, 112
m
m
ag.""
1) w
(0 (1)
mm
| 1
y'=1k'= 11=1
2
at-)
((,
S Tau-1))
(W!")) TaaTall-1 a will
[==1
3
( 2
3
ww!0) 12
2
x V V2,0o
sup
m
1
8 (a
(1)
ay ax
(1-1) (1-1)
V1,8 V2,44
IIVil V2
1=1
8" (aaa ((W:")) ST (1))))
W (1-1)
+
sup
ag.
V
Visg V2.3
(34)
|w:00
i=1
R==1
1 (a ( ((W!")) IT
+
sup
(1-1) w:(l)
V 1.5 V2.w
IVV [V
1=1
172
172
1
6" ((a!!) ((W,1) J
W
will V1, Vig Va.
sup
IV. 11
[V
1=1
==1
m
|
1o
192
172
(a(a!))
1
will a a- 11
V 1,65 V2
sup
I 11
m
||::0/1/
m
Y72
((a
1
w (1-1)
D'
+
sup
ezi a
1,6 V2
|/V ||
[V=
m
|
m
m
o ((a(1) (WW,00) (1))
+
sup IIV VVlll
V1.3 V2.8
m
m
m
m
(1) (W,()) ( (1111))
+ sup
Σ
0 (a!!))
W w
V1a9 V2.3
IV IVIll=-
m
w
2
26

---

Published in Transactions on Machine Learning Research (1/2025)
Now we upper bound each of the terms in the last inequality. We analyze the first term,
sup
m
172
0 (a. 9j Ok
(1)
(1-1)
(1-1) 2,
1.
V
m
2
i=1
88
m
(Viall-1)) )e( V
(2
sup
m7
[|Vill,= Will:=11\e 1VallVaall
8
1
Via (22ll-11
2
sup
m
[in
[ 112
V
2
30
1
sup
Villa V2ll2
m
min.e(m)
1122111 Vell,
3
1
m min(e(m)
(1:00
30 7m + (1 - (0))²
min.g[m]
Now we analyze the second term,
Φ² (WW!) TT (1
(1) (1-1)
sup [Vil
a3
V 1,58 V2.3k
[|
m
w.:00
8
m (W:ll)y | 1
(a(l))a((-1))) (11-11)
m
m
W (1)
sup
Σ aj.
a--1) 1)
V
1,65
ik
V 2,3k'
m
[|V
w (1)
3
V Via(t-11
sup
m
IV. - V2
minig(m)
W W-(()
x
iR
V2
W (t)
36 < m
| [l 1)
1
m
sup
|w!01/
min
=1
301 vm + (1 - 1))²
1 2
minse[m]
The third term is analyzed very similarly as the second term and thus have the same upper bound.
27

---

Published in Transactions on Machine Learning Research (1/2025)
Now, we analyze the fourth term,
170
m
YPS
o" (a ((W,0) ( ()
sup Milla
6
W
'j"
V 1.15 V2
Vall
m
56
m
\ (1
W
m
W (1)
sup
V1,03
V V2,0
m7
|IV = VV 1111=
w/(0) (1)
(1)
W
w
a (1-1))
min [m]]
w
2
sup
V2
Σ
W (1)
V1,5
W ske
x
2,
W
<
B6
(1-1))
2
sup
m
Σ
m
V V2,1+
m
min.e(mm [m]
(
1 I Valla=1
B6
a (1-1
m
w!(:) 2
min [m]
Ba (1 (1 1) ())((())/m))
1
w 2
m
m(m
Bol
1 + (1 - 1)()()))2
vm
| minic[m]
Now, for the fifth term,
m
sup IV -
k vm (a!!)) (1)
( Is
1ill)
ay
(t-
aij
1,05 V2
W-U ik
Via
sup
V2
ww!0) Ville
W
min [m]
1 (1-1)
1
Σ
m
I 2. 11
sup IVall ==
Vm
w.W/l
min
+ (1 - (0))
| 2
minig(m)
The sixth term is analyzed very similarly the fifth term and thus have the same upper bound.
28

---

Published in Transactions on Machine Learning Research (1/2025)
Now, for the seventh term,
) aaa-1))
0' (a!")
sup [V 1 = Vo plpp
3
V1,5 22,45
((W T Tall1))
| 22 2
sup
w
V 1,6 V2,07
5'=1
m
12
(1-1)
2
sup
Vay V2,8
min [m)]
i=
sup
V ll IIV
||=il===10 =2
[mm]
im
(1-1)
sup
VVell IV
min
[ -V
(1-1)
Vm min
|
2
(1 - 1) (0))))
| 1|
min
Finally, for the eight term, following an analysis similar to the fourth term,
((W:)) T (a-1
sup [V V
8 (a)
W.O
13'
wr(
sk'
Viig V2
1l
m
W (1)
<
a (--1) 1)
sup
V
VI.
2 1VV
V
W !
W ik
X
V2,a
(1)
<
a (1-1)
sup |vl.
VV1.a 2
|| 2,5x
Vm
mim]
w
Vall
3( vm + (1 - ())(())))
min.e(m]
Then, taking all the analyzed terms back in 34 we obtain
48 J (1 - 1)(²()))2
3 + (1 - 1)({(0)))
2,2,1
minie(mi (m)]
w
|
2
min:e(m) ||0;001/
2
This finishes the proof.
29

---

Published in Transactions on Machine Learning Research (1/2025)
A.5 Upper bound of the Loo of
af
As seen before, upper bound the Hessian, we need to upper bound the quantity we will actually upper bound the Lg-norm
of
For our purposes,
Dalty
and use this to upper bound the norm.
(a 2
Lemma A.5. Consider Assumptions 1 and For any E [L], any x E Rd such that |xx|| 1, and any
RR with E BEue (vo), we have
0f(0:x) 0x(0(x)
(1+
(35)
Proof. From Lemma A.2 know that (1+ (+Pi) p1) for any 1 Then,
af TattT
51 + Pr- Now, for the inductive step, assume
af Jal
0f Da 11-)
= da! !))
0f
da! !
0f Dall)
Dall-1) (1)
<
la 1]
1
(1++))
12
where the last incquality follows again from Lemma
A.2
We have finished the proof by induction.
A.6 Finishing the proof of Theorem 4.1
Replacing all the previously derived results back in
22 obtain
30

---

Published in Transactions on Machine Learning Research (1/2025)
8f (W
2(23 - + (4 1)]o())1) 3)(
+ (41 1)1)(01))
7m
mm
(1 (1+1) P1)
min
2 mm
+ (4 - 1)1{(0)))
12
2(3p 7m + (/2 1)1o(0)1) + 1)
+
1
minte(m!
minie(m]
(1 + p1)
2( 7m + (4 - 1)1((0))) 2( 7m + (12 1)1
I
II
+
mince(m)
w!(!i)
min [m]]
W: (1b)
1
(1=1++1
Bs
(1 (1+ /=12-1
II
2(280( vm + (11 1-)))(0)) 3)( mm + +( 1)1(())))
p1+
min.g[m]
2( 1 + (4 - 1)(o(0))) 2(3b( vm + (12 - 1)1@(())) + +1)
+
mm
(1 + p1)
min.e(m] [m)] [T(1aa
min+e(m)
(36)
2( 7m
_ (4 1)({(())) 2( Vm
(12 1 1)(((001)
(L- -b((1 mp)
( 2
min
min
2(2 J/ + L|o(0))) + 3)( + L[o(0)))
(1+
min ml
[EiL]
4 + (1)(0))( + L(((0))) +1)
+
(1 + p1)
| 112
min
4L,3( mm
+ L(((0)))
(1 + p1)
|w/011
min:e[m] [E(L]
L(1 (1)+ Fm + L max (oo())))))))))))))))))))) (o)
(,(00)
minae(mi SE[L]
Now, notice that aw()) aw())
a1)
dall) Ih
"n v, then
(2)(0)
(h)
L II
(')
<
aw(l)) (L+1)
@w(h)
01 -1)
M=
2( -m
+ (41 1)({(0)))
2( mm
+ L|o(0))
( + L(0(0)))
50
(37)
min
| (1)
min:e(m)
(((())
min tE]L]
w |w!0
31

---

Published in Transactions on Machine Learning Research (1/2025)
Replacing 36
along with 37 back in 21
we obtain
(()) (20)2 2
L(1 + +i) vm
L max (1(00),
vm + I|((0)
2L0
min mm
w:(1) (1)
min [m)) [E|L]
(
112
(38)
(1+ + (1) vm
+ L2 maxx (000))
0
11
min
min [E[L]
W
This finishes the proof.
B Upper bounds on gradients of the predictor and empirical loss for WeightNorm
Lemma 4.1 (Predictor gradient bounds). and any x, [n], we have
Under Assumptions and for any 0 E R2 with v E pt
BBuc(vo),
[of(0:xx)ll S e0 0 (1 L|0(0)lvm)) (1 1+ VI(1+ v pi)
(6)
Wll
Vm + (1 1)1(())) ? and [
where o3 = (1+ [l0(0) + 4(1 p1) Σt
[v,(0xx;))ll + Pl.
(7)
Proof. We first prove the bound on the gradient with respect to the weights. Using the chain rule,
0f
da
dall)) 0f
II
OW
da!l-1) da(L)
1=1+1
and
0s (W (1)
8a
0ʃ
(0)
Oc
(1 P1)
(1)
!a
dw())
2
1
IA3
2
1) 1))(())))
(1 + P1)
min;g[m] [m]
w
Vm
for E [L], where (a) follows from Lemma
A.5
(b) follows from Lemma
A.3
Similarly,
0f
| (1 Llø(0))\m)
@W(++))
where we used Lemma A.1 for the incquality. Now,
0s (W())
|vof1
Vm + (1 - =-Do)(o)))
S (1 + T[o(0)) /m) + 4(1 + p1)
1=1 minge[m] |
32

---

Published in Transactions on Machine Learning Research (1/2025)
We further note that,
1
0 0
(1 + (oo(0) (m) L(1 p1)²
L (o(0))
min [m] [E[L]
w
m
2
L(1 + p1)
0
(1 + 1,2 (2(((0))mm)
1+
[1:01 (1)
2
min.e[m] [m IE
VI(1 + pi)
7 Do 0
(1+ (l00)/mm)
1+
w:O0)
min]g[[]] [E[L]
where the implication follows from the property Va va+bs Va + vb for a, 2 0.
We now prove the bound on the gradient with respect to the input data. Again, using the chain rule, and so
0f 0f Oa
II
dall"
0f da(L)
δx
0a
oa(()
da (a
0f
(1)
oall)
0f da(L)
0x
(a)
2a((--1)
1
V'=2
(1
0a!l))
0f da(())
(o)
(a
2
(a)
+
where (a) follows from Lemma A.2 and Lemma A.5 This completes the proof.
Proposition 4.1 (Empirical loss and empirical loss gradient bounds). Consider the square loss. the following inequality holds for any 0 e R' with BEac(vo)
Under Assumptions
1 and g
[(0) S & 0(1 p1) ())
(9)
2 where vp n
Ei= v2 2(1 + p (1 ())(0)mmm)) Moreover,
| < C(0)e I 200
(10)
with 09 as in Lemma 4.1
Proof. We start by noticing that for 0 E RD.
(()) Σ (v [(0; x:))
1 n
1 n Σ (2y + (.)
(39)
Now, using the assumption on the weight of the output layer,
[f(0xx) v (x)
- |v/l |a(1 (2) 2 (a)
(40)
19 + p1) (1)
(1+ (1 m
33

---

Published in Transactions on Machine Learning Research (1/2025)
where (a) follows from ||l||| - Vull2 + 1|v Vull2 =++ Pl. and (b) follows from Lemma A.1 Now, replacing
this result back in 399 we obtain [(0) ! I (2yî + 2(1 + )1 ml)(0))/m))) This finishes the proof for inequality (9.
Now, we observe that \Vo((0)12 = E. Vo
S A E V
20w Eis1 184
Del -
(b)
20o v [()) S 2/000 where (a) follows from Lemma and (b) from inequality
This finishes the
proof for inequality (10h. This completes the proof.
C Training using restricted strong convexity for WeightNorm
We establish the results from Section
5
C.1 Restricted Strong Convexity and Smoothness
Lemma 5.1 (RSC for Noig under Square Loss). For square loss, under Assumplions and for every 0' E 0% n pz (B) with 0 e R' and v,v's E BEue p: (vo), 00,00
((0') 2 (()) + (0' 0, VoC(O))
100 012
(12)
2
with
x²2
VoL(0)]
0gg.gr 2
(())
- ((1+
VL
(1 (1)) 7.n L3, (00))) (00) m)
(13)
[W]]
min {1F(WW' W)&l22 ((W
where f(W", W)p = <W" + (1 E)W for some E [0, 1), A I.? 10(0)) v + L max (1)(0)), 1o(0)
and (11, L, (6(0) vm) == 1 Llo(0)) m. We say that the empirical loss C satisfies the RSC property w.r.t. (Q% n Buc (6),)) whenever ag.er O.
Proof. For any 8' E 2222 n (0) with v' E BEac (vo), (vo),, by the second order Taylor expansion around 9, we have
[(0') ((0) + (0' - 0, Vol(O)) 2 (0' -0)T T)T (L((0
0g2 (0' - 0)
where 8 00 + (1 {)o for some
[0. We note that v E BE since, 1 llEv Evo + (1 E)v (1 (11-()e v)voll S llvl voll2 (1 - E) lvvlllvw - P1.
Focusing on the quadratic form in the Taylor expansion, it can be shown that
L())
(0' 0)T
(0'
0)
002
05 x;)
s(:: x,) Σ C 0)T
n 82
1 0
(0' 0)
Og2
n
n
where l, = Elyi, f (0, x)), E 3e()...)
and P
Likewise, we set l.
8z
f(0 x.))
(0=(0.))))
Elyi, f0, x:)), P 0e(y..))
and 7"
8 (()..)
Then, following a similar analysis to Banerjee
8z
82²
(0,x0).))
(0.x.))
et al.
2023
34

---

Published in Transactions on Machine Learning Research (1/2025)
(f(0:x.) x.)
2
1
4 0,
00
2
0' 8 0f x;)
1
0f(0xx;) x;)
0f(0;x;)
0f(0;x;)
00
72
00
2
09
00
x |10' 012
11
8' 0, P. 05 x;)
n
05(0; x.)
[0(0;xx;) x:)
0s(0;x;) x:)
11
(e)²
00
71
09
08
00
x 110'
012
2
1
0f(0:x;)
x;)
2
4
n
Of((;x;,) xx)
H' 0 E.
Σ
11
12 Σ
j=1
(2,)
00
71
00
0f(0:x.) x.) x.)))..)
x
110' 01
00
00
0f(0; x.)
2
4
af(0;x,)
05(0: x.)
05(0; x;
8'
0 E
2n C(0)
00
n
00
00
00
x 110' 0
2
1
1
af(0:x,) x1,
8 f0; x;)
0
D8
110 0112110' - 011
2C(0)
n
00
π
002
1=1
1
(0' 0, VoC(O))
2
4
Σ
08
f(0 xx)
110 0122110' 011
2C(00)
11
00
302
2
69
1
1
0 f0; x4)
(0' 0,, VoL())) 400 011
2C(0)
002
x2
8 f(0: x,)
(()) 110' - -013 420 - 0
2C(0)
002
1=1
/oL(()) 40o - -012-
-
1
Σ
2 f(; )
110' - -013
2C(0)
7
802
1=1
where 0 is some point in the segment that joins 0 and 0: and where (a) is the inequality derived in the proof of (Banerjee al. 2023 Theorem 5.1); (b) follows by ")))()²²
(f - 4nn((); (c) follows
by Jensen's inequality on the first term and on the second term by the use of Lemma 4.1 due BSper (vo)
and the mean value theorem; (d) follows by ||0 0||2 l|ger + (1 {)o 01l e 011 ||0 - 0112: (c)
follows since 0' Q% and from the fact that p cos(p, 4) ||lll || for any vectors p.q.
35

---

Published in Transactions on Machine Learning Research (1/2025)
Regarding 12, note that
8 [0;00xxx xi)
12
(
8)
(6' -9-)) +)
Og2
8 s [0; x;)
110 011
vn
(6)
1/2
02 S(O: x+)
1/2
110'
011
1/2
2/ ((θ)
1
Σ
02 f(0; xc:
110'
011
n
002
where (a) follows from the Cauchy-Schwartz incquality and the submultiplicative property of the induced
norm; (b) follows by Cauchy-Schwarlz inequality again; and (c) from [1 _/f Σn (J:: y1)² = 4L(0).
Replacing the lower bounds on 4 and /2, and using Lemma 4.1 and the fact that or BBBc((), we finally obtain,
pz
(0' - 00' T C(0)
02
x2 VoC(0)1
f(0: x;)
10' - 0) 2
400
Σ
002
(())
002
1/2
02 f(0; x;)
-2/1
100 - -013
302
1=1
Now, note that use Theorem 4.1 to upper bound the norm of the Hessian of the predictor because V belongs to the segment joining V and two vectors which belong to the convex set B BEue (Vu), and so it follows that V BBue)
36

---

Published in Transactions on Machine Learning Research (1/2025)
Then, using Theorem 4.1
Lemma 4.1
and Proposition 4.1
@2 f(0: x,) 002
02 f f(O: x;)
2)
400
+ +20
002
1 L2 max(1 (00)
4gop2
$ (1 + ( (1)
/m
1//012
min
minge ml [E[4]
minee|m [m] [E
1
2 /
|1:00
min
minjg[m] [E|L]
min ml 1E L)
(1 + 3
1
L max (6((0))
s (400p2 2
mm
(w(()) mmiig(mm) (m)
|
min minie [m]
min.c(m) [m] [E[L]
min:e (m)
12
[e[L]
L
LE
(1 + T3 Vm
1 + I max max (1o(0)), ((0)
0
(00P2 + vp)
(-(1)
( 2
|
min
(in [e(1]
mmiie(() (ml [E(r.
min.e[m] 1E
min,
ZE(T)
VL
1+
(((t)
min.e ml L]
max + (1 p1), + ( 23 vm + _ max m (mxx( 4|(())
|w/00
| min
|w:
min
minjg[m] [E]L
min [m] 1E L)
min.e[m
[E
1E[L)
VL
o
1+
(.(0)
min [mm LE[L]
2
(1 p2)(1 + I 1
vm + L +10)))000000)0))+++++0+000101))) L
min
minjg(m) LE|L
|/:00
minjgim) [m))
|
min:e(mi re
wi
minig(ml [m] LE
W
le L)
37

---

Published in Transactions on Machine Learning Research (1/2025)
where (a) follows from
VL( + pl)
(DoP2 vP) 0o + (o(1+) vm)
1+
+ +1+ +1)++
W!
mmn [.
(1+
VI(1 + pi)
0 (1 21 (10(0)/m
1+
w
min te(1)
That completes the proof.
Lemma 5.2 (Smoothness-like property for WeightNorm under Square Loss). For square loss, under
Assumptions and 2 for every 8, H' E Re with v, v' E P1
(vo()
C(0') - [()) + (0' - 8, voL(O) + B
1 - -00 012
(15)
2
with
30.0 So L L., 21)² (1+
1+
(16)
min [lin W)& 212 F(W", w>
where f(W', W)e EW + W) for some & E [0, I], A(1, LZ, (o)) (1 + L2 max (0))), (0(0) (m))².
Proof. By the second order Taylor expansion about 0 E R2 with v E B (vo), we have L()') = (()) + (0'
0. Vol(o)) + 10'0 O)T
a² (0' - 0), where = 50" + (1 E)o for some E [0. 1]. Similarly to what was
30
proved in Theorem 5.1 V E B BEuc (vo).
Now,
LCO)
00' 0)T
(0' 0)
002
0f (f(0xx))
2
n
82 f(0: x:)
0 0' 0,
(
0)
(0' 0) 0A2
n
00
f1
1a
where & = f f(0,xi), f _)()..))
and
E
0² ((uue)) 8x
1t is easy to note that 4 <
82
100(0xx.)
(0.x)
202/10' - -012. For 12, we have that
02 ((0xxx)
1
E,(0'
0)T
(0' -0)
802
i=1
02 f(0((0x))) (1)
110'
-013
002
1=1
1/2
1
0 0f(00xx) x,)
1/2
1111
110'
0112
71
002
1/2
82 f(0: x;)
2/ (())
0 012
002
1=1
38

---

Published in Transactions on Machine Learning Research (1/2025)
where (a) follows by
and (b) from 1 bounds on / and 12 on the original expression, and using Lemma
1=1 (1/ - yx22 4C(0). Replacing the
4.1
(0' - 0) 0()
0a
f(O, x:)
2
1/27
(0' - 0) < 200 + 2
110 - 0
002
002
Now, note that from the proof of Lemma
4.1
L(1 - p1)²
oØ 0
(1 L2 (3)))mmm
14
n 11
minge [m] [E(1]
and so,
1/2
1 n
82
f(0: xs)
200 + 2/8
n1 Σ
002
12)
L(1 + p1)²
00
(1 11+1210000 13((0(0) (m)
1+
17:10
min.e[m] IE(T.)
(1 (1+ Ll0(0)lm) (1 11) +0
+ I max (1o(0)), ())
min mmin
(1)
m(m [m] [E(1]
[E[r]
L
(1 + La mxxx p1)² oo
1+
w
2
min.e [m [E(L]
(+m + La max]
min min(min (mi
s [m] LE
LE[L]
so (1(1 + I.2 max mmx(() p1)²
14
(1(
1w 22
min/min,er
min
maneeno [m]
[E
This completes the proof.
C.2 About the adaptation of (Banerjee et al. 2023 Theorem 5.3)
To adapt (Banerjee et al. 2023 Theorem 5.3) to our setting, we need to adapt the supporting lemma Banerjee
et al.
2023 Lemma 5.1) our setting as follows:
Lemma C.1 (Auxiliary result using RSC, (Banerjee et al.j 2023 Lemma 5.1)). Let B,
0% n Bue (0:) n {0 / BBuc(vo)) and 0, E arginfoes, C(0). Using the setting of Lemma 5.1 if
00 0, then
((O.) inf C()) S |VoL(0.)1
(41)
20,,
39

---

Published in Transactions on Machine Learning Research (1/2025)
Proof. By Lemma 5.1 have
((0,) 2 ((0,) (0, 0. VoC(O.)) + 0. 110 0el12
(42)
Now, let us take 0, and define
L(00 = [(0,) + (0 0r. Vo((O.))
08, 110 0:112
2
Note that (o( is minimized at 0.+1 == == 0, - VoL(0))/ a0, and the minimum value is:
inf (0) (be+1) _((,) BERP
1
20
Then, we have
(()) ((0.) (4)
inf
(0.))) inf (,(0) -((+) 200
[VoC(0.)1
BEB,
Deloe
where (a) follows from
42
Rearranging the terms completes the proof.
Finally, note that Theorem 5.1 makes the claim that
(0, 1] (using the notation from the same
Bi,
theorem). We now provide the proof for this result.
Proposition C.1 (The RSC to smoothness ratio). Consider the setting of Theorem 5.1 Then, "8..8. (0,1).
S0,
Proof. From Lemma C11 have
-(0.))((0))) S |V
(43)
0.
Now, using Lemma 5.2 we obtain
+ Bo 1| 0.11
C(0++)) - C(0,) (0+1 Os voL(O.))
2
Se. v/ (()))
= L(0,) Th (VL(())] +
(44)
2
= L(0.) 2,30.
VoL(0,)]
where the last equality follows from 17-
1.
Bor""
Now, we notice that 0.+1 E Q by Definition 5.1 O.11 E B ( E R2 v BEuc (Eue(vo)) by Assumption 3 and l-1 E B,. This implics that C(0,)
pi
L(0.+z). Thus, using 44
obtain
VoL(0))] < ((0)) C(,,)
23p.
Using this inequality along with leads Be, 0. This completes the proof.
2 < Finally, by assumption we have 0g,7 and
a -. Do,
by 17 we have Ba, > 0, and 8o
40

---

Published in Transactions on Machine Learning Research (1/2025)
C.3 Distance between consecutive iterates
Proposition C.2 (Bound on the distance between consccutive itcrates for WoightNorm under ((0) = 0). Under Assumplions 1 and and assuming (A3.1) from Assumplion and that the aclivation
function satisfies o(0) = 0, we have
10 - 0el2 S. sm.. (1+
(.. (1)
(1+ W.
(
VL. vm
Proof. We have that 10++1 - 08ll2 = 100 voL(O,) - 02ll2 = (VoC(()) (a) o (1 pi) from Proposition 4.1 and the definitions of da, and (p presented therein; and (b) follows from Corollary and Corollary
200. /v
vL(+pp) s 1tt O (1 p1)² 1
V
where (a) follows from using 10
vm W. 12
/m Wi
4.3
D Comparison between networks with and without WeightNorm
We summarize in Table the comparison between bounds and optimization results and those for networks without WeightNNrm by Banerjee et al. (2023).
with WeightNorrm
without Weight.Norm
Deterministic results
High probability results
Hidden layer weights can take any value
Hidden layer weights restricted to a neighborhood
around their initialization
Appearance of normalization terms, iee. the mini- mum weight vector norm, in the Hcssian bounds and the RSC and smoothness parameters
No appearance of such normalization terms
The polynomial dependence on the depth in our bounds and parameters is independent from the initialization variance of the weights
Polynomial dependence on the depth requires care- ful choice of initialization variance
Lipschitz constant bound is independent from the depth
Lipschitz constant bound exponentially grows with the depth unless careful choice of initialization variance is done
Table 1: Comparison of results for neural networks with and without WeightNorm.
E
Generalization bound for WeightNorm
We first state the following auxiliary technical result, which is based on (Golowich et al, 2018 Lemma 1). We let A(U) = ((W(1) W(2) ...., w()) Raxd Rmxm ... Bmxm]
Lemma E.1. Under Assumptions 1 and 2 assuming the activation function satisfics Φ(0) = 0, consider any WeightNorm network (6: of the form with any fixed R and E BFa()v)), along with some input data set { Consider also any convex and monotonically increasing function g I [0, oo). For any
41

---

Published in Transactions on Machine Learning Research (1/2025)
LE fl...., L 17,
w T |ul||
Σ cΦ
(9) (x:)
sup 9 WEA WER"
m
| (45)
Σ _ (x,,
< 2 E (ca)
sup
g
WEA
m
Proof. Since y is posilive, s([=|) s s(z) + g(==), and
Σ Ge
1 T
sup g WEA
(mm
||:|
(xx:)
WER
B
sup WEA
g
Σ
n
c/
m
1 w
|
(0)
(xxi
WER"
sup WEAD> WER"
9
Σ
G
v/m
w
(xx)) (x:)
(0) 2 (c
sup g WEA
Σ
cΦ
m
1 w"
||/||
(1)) (xc:
WER
b 2 (e,
9
sup
Σ
G/
1 w
(1)))
(x::)
vmn
WEA! WER"
1=1
(0)
w T
< 2
g
sup
E
|
a
(xi)
WEA WEB
1=1
w T
2 (c.)
g ()) WER
sup
Σ E2
m
|l|||
a
(1)
(xx)
i=1
(d)
T
< 2 E
sup (E WER"
|
(1)
(xx)
i=1
sup ()
Σ Ga
11
(xx)
where (a) follows from the fact that 6 and -G have the same (symmetrical) distribution; (b) from g being monotonically increasing; (c) from (Ledoux and Talagrand 1991 equation (4.20)) which makes use of g
being convex and increasing, and of o being 1-Lipschitz and ((0) = 0; and (d) follows from the increasing monotonicity of g.
We now prove our generalization result.
Theorem 6.1 (Generalization Bound for WeightNorm under Square Loss). Consider the square loss and the braining set S ((1 v.) idddd D [m]) and lvl S 1 for any y Dy, with probability one. Under
42

---

Published in Transactions on Machine Learning Research (1/2025)
Assumptions 1 and 2 assuming the activation function satisfies o(0) = 0, with probability at least (1 - 6)
over the choice of the training data x; ~ 'x, E [n], for any WeightNorm network (0; of the form ① with any fized 0 E I2 and v E p1 (vo), we have
2 (2) +1 +(11+ (1+ pi) v 2 1og(2/0)
(D( - Ls( 4(2 + p1)(1 + pi)
(19)
Vn
vn
Proof. Recall that for a class of functions F, the Rademacher complexity is given by
1 |EF
(R =
sup
<x((x)) ==1
(46)
where samples x,, i E [n], are drawn i..d. from Dx, and G, E [m], are drawn iid. from the Rademacher distribution, i.e., +1 or -1 with probability $. Assuming (/ S B, E F, a standard uniform convergence argument implies
1
nt2
P
sup JEF
Σ f(x:) - Ex [f(x)] 2 (F)
< 2exp
2B2
(47)
In other words, with probability at least (1 8) over the draw of the samples, we have
a n Σ f(x)) + 2R, (F) + BV
2 log &
F, Bx-DxI((x))
(48)
n
Now, consider a given loss function l so that, for given constant y such that |y/ 1, it computes E(y, f(x)). If à Ely, () has Lipschitz constant of X, then by using the Rademacher contraction lemma (e.g., an adaptation from (Shalev-Shwarte and Ben- BaviD 2014 Lemma 26.9)), the uniform convergence result can be extended to the loss function: with probability at least (1 (1-) 5) over the draw of the samples, we have
2 loo 2
VIEF, Colf] Cs(f] (F) + BV
(49)
n
with Cr[f]= = ((xx)) Cslfi= E" f(x)),, and sup JeF ((,,)( s B. lols1
Now we put everything according to the context of our setting. We let F be the set all WeightNorm networks -(0:-) of the form with any fixed 8 R2 and v E BEue (vo) under Assumptions and 2 and p1 assuming the activation function satisfies <(0) O. We also set CD(() == Colf(A:)) and (0) (0( (0: )]
Consider any E Rd with ||x||| 1. Now, using the assumption o(0) 0, obtain
xf(0x)) < (1 + p1) from equation (40
and so f(y. f(0xx) = (y f(): I 2/yl + 21f((:x))
<
2(1 + (1 + +1)))) ie.,
B B= = 2(1 + p1)
(50)
Likewise, this allows us to obtain, for lyl 1
dé 9)
< 2 + (f(0x)))) < (1+++(+)))
p1)) = 2(2 + p1))
dğj ;=f((0x)
and
A = 2(2 p1)
(51)
43

---

Published in Transactions on Machine Learning Research (1/2025)
Next, focus on bounding R., (F).
(F( n
sup fEF
(x,)
1
Σ scall (x
n
Eix
sup WE VeR S1tp
11
(1 + pı)
((x))
sup WEA(2)
c2a cga (xx,)
n
i=1
(52)
(1 + P1)
E 12 talii
sup
E2a (aall)((1) (xi)
n
WEA())
(1 pI)
n cØ
W
E (x))
sup max WEA()) kc[m]
Vm
12 (xx))
n
m
W (L)
iml
2
(1+P)) P1)
w T
E (1))
sup sup mm WEA(Z-1) we
GØ
11-
(L-
v
mm
1=1
Then,
n
(F) S
sup WEALL
VII 1) wERm
sup
n Σ i=1
1 w
a
(1-1))
(1 + P1)
vm
|wll
= 7 log exp AEixi
w
a (L- 1) (xx;)
sup (EALL-1)
sup weRm
m
m |ell
(0) A log E ((x))22
n
1 w
Aym Σ
(1-
(xx) (xx,)
sup (EA(1-1) EER
exp
||2ll22
(53)
where (a) follows from Jensen's inequality. Now, using Lemma
E.1 with the function g(=) exp(e 2),
1 w
log E ((x))22(())
sup WEA(C-1) wER
exp
Aym m
Σ
E
(L 13 (2c1)
A
m
/wl1
1=1
< log 2E (x(x)))
sup ()
exp
A/m
1
Σ Ga
(I
(xxs)
Vm
= log 21
sup (1-1)
exp
Σ
(xix)
Now we realize the expression on the right-hand side of the above equality is very similar to the second inequality of equation 53 therefore, we can iterate the same procedure using Lemma E.1 until we eventually obtain,
1
(F) - log 2 2'x
exp
Ga
(0)
(x²)
(1+ P1)
(54)
1
n
log
2%.
exp
Σ
E2Xi
44

---

Published in Transactions on Machine Learning Research (1/2025)
Now, closely follow the proof of (Golowich al. 2018 Theorem 1) after the equation (9) from that
same paper. We first define the random variable 2 = -i=1 exill2 and obtain
log (2" Eixi)a (exp(AZ]))
log(2) log Disattinteet exp () (z Dieriiz [ (21)11
log Exxx exp (G 121)
(55)
Now,
(a)
(()),,1213
B
Σ cx
i=1
E
Σ
x X +
cEe Xj
i=1
==1
(56)
n
(b)
11
X;
i=1
1x:133 1)
=x log E [exp (XEte. (2)))
1
log
Eixiiinn
exp
Σ
n
1
log (exp (dvr))
X
where (a) follows by Jensen's inequality and (b) from the fact that e, is independent from Ej, j # i. If we consider {z as constants, then we have that Z is deterministic function of the i.id variables (4))_ which satisfies
.6......,GG,....... 6n) - Z(EL..... ,.,..., 6n) S 2|xx112
obtained by using the reverse triangle incquality. This incquality a bounded-difference condi- tion which implies that Z (considering
{ in as constants) sub-Gaussian with variance factor Boucheron et al. 2013 Theorem 6.2); which then implies 1|x:12]) Then, we obtain
v = - 4 2|xx = Σ |x see
Eia exp () (z Bicr11 [21) S exp
log (E(x))) exp (a (z Pece) 1om (z))])
log Fx(x)) exp Aa Σ
| 12))
1 X2n
An
2
(57)
V2log(2)L vn
Replacing equations (56) and 157 back in 55
with X
let us obtain
1 log (2t. ((x.)2
2 (
2log(2)L
+ vn= (V2log 1)vm
(58)
X
2
2
which replacing back in 54 let us obtain,
n
R2 Rg (F) = (22oo)) 2) + 1)
(1 + p1)
(1 + p1)
R
2 log(2) + 1).
nn
Plugging this bound back in 49 along with
50 and
51
completes the proof.
45


Reviews:
[{"review_id": "1Q6UrHpUJo", "reviewer": "Reviewer_GJGR", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths \n1. Theoretical guarantees for both optimization and generalization that indicate the favorable impact of weight normalization. \n2. This article is well-written, and clear (including the several proofs in the appendix). To the best of my knowledge, the calculations in this appendix are sound and intuitive. \n\n# Weaknesses\nI think the technical results are potentially overstated in the writeup. At several points, the authors claim that their generalization bounds avoid the exponential dependence in depth. I contend that the contribution in this aspect is more nuanced. I am interested in hearing the authors’ perspective on my comments below. \n\n1. Suppose the activation functions are $M_a$-Lipschitz and the weight normalization ensures $M_w$ Lipschitz constant in each layer (by an additional scaling factor of $M_w$ instead of unit norm), then the resulting bounds on the norms of gradients, Hessians, and the Lipschitz constant all exhibit the dependence $\\prod_{1\\leq l \\leq L} M_a M_w$, i.e. the bounds are exponential in depth. The authors are *correct* in their observation that setting $M_a, M_w$ to be 1 presents a opportunity to instantiate a O(1)-Lipschitz predictor. However, I am not certain that weight normalization is critical for this effect. \n\nWhen the learning task is classification (rather than regression as considered here), and the activations are ReLU, the bounds on the norm of the margin scale with the norms of the weight vectors. This is the primary motivation of the spectrally-normalized margin bounds developed in (Bartlett et.al, 2017). In particular, for any multi-layer feedforward network f with no bias vectors, if each of the feedforward weight vectors are scaled by a constant $M_{scaling}$, then the function output is correspondingly scaled by $M_{scaling}^L$. Further one is always free to choose $M_{scaling} = (M_a M_w)^{-1}$ which results in an equivalent 1-Lipschitz feedforward network with the same prediction properties and error as the original unnormalized predictor. Such an observation is also noted in Neyshabur et. al. (2015)'s work on path-normalization of ReLU networks. In this article, unless I'm mistaken the assumption of smooth activations can be removed for the generalization bound (correct me if I'm wrong!). \n\nWith this context, for a classification task if one fixes the margin threshold $\\gamma$ in (Bartlett et.al, 2017) arbitrarily then the bound on the generalization error is indeed exponential in depth as it depends on the Lipschitz constant $(M_a M_w)^L$ (see spectral complexity in Bartlett, et.al  (2017)). However, if the the margin threshold is set to be $\\gamma_{scaled} = \\gamma *  (M_a M_w)^{L}$ then the bounds on the generalization error are not exponential in depth! Thus, generalization bounds in the classification setting are readily devoid of exponential dependence when viewed through the spectrally normalized margin perspective. This behaviour is possible because the absence of bias vectors lends the networks amenable to such a simple scaling. (Such a scaling is less clear if the networks have non-zero bias but this article restricts to discussion to zero-bias networks.) \n\nAs a result of this behaviour, generalization bounds are exponential in depth if the margin threshold or loss function are oblivious to the scaling and the bounds are not exponential in depth if the threshold or loss function is appropriately scaled (as spectrally normalized margin suggests). While the above comment is explicitly for classifications tasks, the analogous phenomena for regression tasks is the scaling of the observed outputs. If the observed output $y$ is assumed to have unit-norm then appropriately scaling the predictors ensures a good generalization bound and if instead each of the weight norm layers are scaled to an alternate threshold $M_w$ then the resulting bounds exhibit exponential dependence in depth again. Such an appropriate scaling does not require WeightNorm for classification as it can be overlayed on any learnt predictor due to the scaling invariance in classification prediction. Similarly for regression, this scaling has to be adapted to the norms of the observed outputs and any regression function can be scaled this way, if the regression task is itself normalized such that the observed outputs have unit norm. Thus, I think the absence of explicit exponential dependence in depth in the main generalization reflects the appropriate scaling for the task under consideration (indeed Theorem 6.1 assumes that $|y|<=1$ w.p.1). \n\n2. I think there might be a ready-made bound for the Rademacher complexity of the output of WeightNorm predictors on the training data. To see this, I believe one can instantiate the bound on the Rademacher complexity just like Lemma A.8, Bartlett et. al (2017). (Assuming Bartlett et. al’s notation), For WeightNorm predictors, the layer-wise spectral norms $s_j$ are bounded by 1 and the l1 norm bounds $b_j$ are bounded by the layer widths ($m$ in this case) and the activation function Lipshcitz constants $rho_j$ are simply 1. In this case, the spectral complexity does not exhibit exponential dependence in depth in the same way the sensitivity calculations in this article do not. The resulting bound on the Rademacher complexity via the spectral complexity scales as $\\sqrt{\\text{depth}}$ just like the bound on the Rademacher complexity in this article in Page 42. The straightforward on the Rademacher complexity via Bartlett's result automatically translates to a bound on the generalization error by the standard analysis and already avoids the explicit exponential dependence in depth when the network is weight normalized. There are still subtle differences between this straightforward bound and the bounds developed in this article, (perhaps with width dependence) and I think this point of comparison needs to be clearly communicated in the draft to appropriately contextualize the exponential dependence on depth. \n\n3. As a final technical point, even when the predictors are appropriately normalized to be 1-Lipschitz, there is still a version of exponential dependence in depth that matters. This stems from a conservative estimation of the true sensitivity in each layer, for eg. if at each input, a predictor is $\\frac{1}{2}$-locally Lipshcitz at an input x, the function output exhibits a local Lipschitz constant of ${\\frac{1}{2}}^L$ but the global Lipschitz constant is still 1! This results in a poor generalization bound since the spectral norm scaling of the margin thresholds is inadequate. Here, the exponential dependence on depth of the local Lipschitz senstivity is beneficial if one is able to appropriately account for it in generalization theory. This observation has motivated a few articles that I think deserve a citation and comparison amidst the discussion on exponential dependence in depth. In particular refer -  Nagarajan and Kolter (2019), Wei and Ma (2019), Muthukumar and Sulam (2023). While these article often discuss bounds for supervised classification, they each make a case for avoiding exponential dependence in depth and their results have reasonable extensions to the regression setting. Additionally, Wei and Ma (2019) consider smooth networks and compute bounds that depend on the local linear Lipschitz constant (i.e norms of Jacobians) and are closely related to the authors’ work. \n\nIf the authors agree with the above comments, then the claim of exponential dependence needs to be significantly revised to account for the above nuances. I want to emphasize that I do not intend to downplay the authors’ contribution but rather I would like a more appropriate contextualization of this well written article in certain key aspects. \n\n### References\n- Behnam Neyshabur, Ryota Tomioka, Nathan Srebro. Norm-Based Capacity Control in Neural Networks. (COLT 2015)\n- Peter L Bartlett, Dylan J Foster, and Matus J Telgarsky. Spectrally-normalized margin bounds for\nneural networks.  (NeurIPS, 2017)\n- Vaishnavh Nagarajan and Zico Kolter. Deterministic PAC-bayesian generalization bounds for deep\nnetworks via generalizing noise-resilience. (ICLR 2019)\n- Colin Wei and Tengyu Ma. Data-dependent sample complexity of deep neural networks via lipschitz\naugmentation. (NeurIPS, 2019)\n- Ramchandran Muthukumar, and Jeremias Sulam.. Sparsity-aware generalization theory for deep neural networks. (COLT 2023).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "Normalization strategies are a form of regularization that seeks to enhance learning algorithms by improving (1) the convergence dynamics during the training phase and (2) the generalization properties of trained predictors. This article investigates the impact of WeightNorm (Salimans and Kingma, 2016), a normalization strategy where weight vectors are constrained to be unit Euclidean norm. The analysis in this article is focused on a regression task where inputs are unit-norm (Assumption 2).  The hypothesis class under consideration is multi-layer feedforward networks with weight normalizationa and smooth 1-Lipschitz activations (Assumption 1). \n\nThe core contributions of this article are, \n1. A training convergence guarantee for WeightNorm predictors under a variant of restricted strong convexity assumption (Assumption 3). \n2. A uniform convergence generalization bound with favorable dependence on architectural hyperparameters such as width and depth. \n\nTo establish these results, the authors undertake careful calculations where the norms of the predictor gradient and Hessian (on the training data) are bounded. These calculations benefit from the unit-norm constraint on the weight vectors enforced by design in WeightNorm predictors. To see why, if $w_1$ and $w_2$ are two arbitrary vectors consider the impact on their distance $\\|w1-w2\\|_2$ before and after projection to the unit-surface. If $w_1$ and $w_2$ are initially far away from unit surface, then the distance between their projections are drastically smaller compared to the original distance (i.e better sensitivity w.r.t $w$’s). But if the vectors $w_1$ and $w_2$ are initially closer to the origin, then the distance between them is enlarged because each unit angular change corresponds to larger norm of perturbation in the unit surface. This intuition I believe conveys the authors' central observation that inverse of the minimum weight vector norms impacts the sensitivity.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I suggest the following minor changes (and questions to address) to improve the exposition. \n### Minor Technical Questions\n- The inequalities in the final lines of equations after (49) differ the last inequality in (49) with a $\\sqrt{m}$. Does this impact the result? \n- Why is the output layer not directly assumed to be unit-norm like the feedforward layers? There is a consistent emphasis that the output layer vector $v$ is within distance $\\rho$ from a reference unit vector. As a result all bounds additionally carry the factor $(1+\\rho)$. It appears that the final results would be greatly simplified if $v$ is instead directly assumed to be on the unit-surface (i.e. weight normalization is also applied to $v$).  \n\n\n### Minor Editorial Comments\n- Fix the spacing in the appendix proofs if possible. \n- Don’t use $v$ as a free parameter when it also has a specific meaning as the last linear layer (for eg. in Proof of Lemma A.2).", "broader_impact_concerns": "I don't anticipate any concern on the broader impact of this scientific article.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Jy1K19ejN0", "reviewer": "Reviewer_83Qz", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n\n1. This paper presents optimization and generalization guarantees for neural networks with normalization, which is an important topic in deep learning theory.\n2. The established bounds have only a polynomial dependence on the depth.\n\n### Weaknesses\n\n1. The proof is poorly written. The current version does not provide an outline for the proof, which makes it hard to see how the lemmas in the appendix are related to each other and contribute to the proof for the final theorem. Some equations and inequalities are too long and also the authors did not provide enough explanations. For example, the derivation on Pages 17, 20, 25, 30.\n2. From the current version, it is hard to see how this paper may help researchers and practitioners to better understand the training dynamics of neural networks with weight normalization:\n    1. Although this paper presents a lot of theoretical results, it merely states the difference to previous works on neural networks without normalization and doesn't provide any high-level explanation of why weight normalization is the key to deriving such results.\n    2. The weight normalization studied in the paper is NOT the weight normalization used in practice because it has a trainable scaling factor but this paper just ignores it without further explanation.\n3. A key proof insight is that the spectral norm of Hessian of the neural network output is small, but this also means the entire training is in the lazy training regime, where the neural network may be approximated by a kernel method. This regime usually leads to worse generalization in practice, no matter how good generalization bounds may be proved in theory. This issue could be addressed by running experiments on CIFAR-10 / ImageNet that closely follow the theoretical setup and show a comparable test error as a more standard training pipeline.\n4. Assumptions A3.2 and A3.3 state that the weights are bounded in a local region near the initialization. Making such assumptions on the dynamics (rather than the loss landscape) significantly weakens the result because theoretically there might be no hyperparameter choices that can make the assumptions hold. This issue could be fixed if the authors could prove these assumptions for some learning rates.\n5. Since a selling point of the paper is that the bounds do not strongly depend on the depth, can the authors actually show this in the experiments? In the current experiments, neural networks only have two hidden layers. It would be good to check if they still converge and generalize well as the number of layers increases.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents optimization and generalization guarantees for training neural networks with weight normalization. Under a proper parameterization of the networks (similar to NTK parameterization), the authors establish bounds on loss convergence and generalization for wide neural networks. Notably, these bounds have only a polynomial dependence on the depth of the network.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Improve the readability of the proof in the appendix and add a high-level proof sketch in the main text.\n2. More empirical validation of the theory to address Weaknesses 3 and 5.", "broader_impact_concerns": "/", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "3ttWmRlX3m", "reviewer": "Reviewer_z5TM", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- The paper provides the theoretical guarantees for WeightNorm networks.\n\n\n\nWeaknesses:\n\n- The result is limited to smooth activation functions which may further limit its practicality.\nAlso, the result mainly focuses on square loss which may not be helpful in classification tasks.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the following problem.\nGiven a dataset $(x_1,y_1),\\dots (x_n,y_n)$, we define a loss function to be $L(\\theta) := \\frac{1}{n}  \\sum_{i=1}^n \\ell(y_i, f(\\theta; x_i))$ where $f$ is a neural network parameterized by $\\theta$ and $\\ell$ is the loss function between the true value $y_i$ and the predicted value $f(\\theta,x_i)$.\nIn particular, this paper considers the WeightNorm network, i.e. the norm of the weight vector in each layer is normalized to be $1$.\nWe train the neural network $f$ by using gradient descent and would like to minimize the generalization bound.\nThe authors provide the theoretical guarantees on the Hessian of WeightNorm networks and the generalization bounds.\nAlso, the authors evaluate their result on CIFAR-10 and MNIST datasets.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- The authors may want to extend the result to non-smooth activation functions such as ReLU because it is more commonly used.", "broader_impact_concerns": ".", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies neural networks with batch normalisation and proves results which consist of two components: optimisation guarantees and generalisation guarantees. 

The optimisation guarantees constitute the bulk of the work and culminate in Theorem 5.1, which implies convergence of the empirical loss under suitable conditions on the iterates. This is an analogue of Theorem 5.3 in [1]. The generalisation guarantees instantiate the result of [3] (which generalises [2]) to the regression setting studied here, where the distance from initialisation is assumed to be bounded as a result of an assumption on the iterates. 


Two out of three reviewers weakly recommend acceptance, whilst one competent reviewer recommends rejection. 
The two most salient points during the discussion were: 

1. The lack of novelty of the generalisation results (pointed our by GJGR and which I discussed with the authors during the discussion phase).

2. The limitation introduced by Assumptions 3.2 and 3.3. 



Regarding point 1, it is true that the original description of the results was misleading in presenting the results as original and as a solution to the exponential width dependence present in typical norm based generalisation bounds for neural networks [2,3,4]. Indeed, the bounds are indeed a **nearly direct consequence of** existing work [3] when incorporating the assumptions made in this work. However, after the discussion with the authors, the authors have acceptably downplayed their claims. Perhaps going slightly further in this contextualisation step would further strengthen the camera-ready revision. 

On a tangent note related to point 1, it is worth mentioning also that parameter counting bounds such as those of [4] naturally do not explicit any exponential depth dependence, even without batch norm (the results from [4] apply to DNNs as a particular case of CNNs). More generally, there are plenty of bounds for neural networks with subtle differences in depth scaling compared to [3]. See, e.g. [5] and the references therein for details and comparisons. 


Regarding point 2, I agree that **assumptions 3.2 and 3.3** introduce a significant limitation. I understand the authors' rebuttal which states that the conditions on $\rho$ can be incredibly mild and that (quoted from the rebuttal) **"we should be able to find such a $\rho_2$ because the empirical loss  is smooth, and so, since we are using gradient descent, it is not possible for $\theta_{t+1}$  to diverge and be “too far” from $\theta_{t}$"**. However, I still feel like a full resolution would have to express this vague statement in more quantitative terms, and achieve a bound which only depends on constants related to the loss function rather than relying on assumptions on the iterates. I am not sure if that is fully possible, but I would like the authors to try in the camera-ready (minor) revision (even for a specific loss function). At an absolute minimum, if a solution is genuinely not possible, the limitations and the reason for the difficulty should be discussed.

The accepted ICLR work of [1] uses a similar *iterates assumption*, so I don't think this issue is strictly cause for rejection, but I would like to see either a solution or a candid description of the limitations in the camera ready revision. 

It might also be a good idea to mention (near the discussion of Theorem 5.1) that remark 5.4 (which controls the ratio $\alpha/\beta$ by showing it is less than 1) holds regardless of the value of $\rho$ and incorporate reformulations of some of the rebuttal to reviewer 83Qz  into the revision to make Theorem 5.1 more approachable to readers (such as myself and reviewer 83Qx) who might be initially shocked by assumption 3.


In conclusion, the paper makes a valid contribution to the field and **deserves to be accepted** after some further polishing according to the changes requested above. 

***References***


[1] Arindam Banerjee, Pedro Cisneros-Velarde, Libin Zhu, and Misha Belkin. Restricted strong convexity of deep learning models with smooth activations. ICLR 2023

[2] Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-Based Capacity Control in Neural Networks. COLT 2015

[3] Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-Independent Sample Complexity of Neural Networks. COLT 2018.

[4] Peter L. Bartlett, Dylan J. Foster, and Matus Telgarsky. Spectrally-normalized margin bounds for neural networks. NeurIPS 2017.

[5] Philip M. Long and Hanie Sedghi. Generalization bounds for deep convolutional neural networks. ICLR 2020. 

[6] Florian Graf, Sebastian Zeng, Bastian Rieck, Marc Niethammer, and Roland Kwitt. On Measuring Excess Capacity in Neural Networks. NeurIPS 2022.
Decision: Accept (poster)