SGD and Weight Decay Provably Induce a Low-Rank Bias in Neural Networks
Authors: Tomer Galanti
Zachary S Siegel
Aparna Gupte
Tomaso Poggio
Venue: Submitted to ICLR 2023 (2023)

Abstract: We analyze deep ReLU neural networks trained with mini-batch Stochastic Gradient Descent (SGD) and weight decay.  We show, both theoretically and empirically, that when training a neural network using SGD with weight decay and small batch size, the resulting weight matrices tend to be of small rank. Our analysis relies on a minimal set of assumptions; the neural networks may be arbitrarily wide or deep and may include residual connections, as well as convolutional layers. 
The same analysis implies the inherent presence of SGD ``noise'', defined as the inability of SGD to converge to a stationary point. In particular, we prove that SGD noise must always be present, even asymptotically, as long as we incorporate weight decay and the batch size is smaller than the total number of training samples. 

Under review as a conference paper at ICLR 2023
SGD AND WEIGHT DECAY PROVABLY INDUCE A LOW-RANK BIAS IN NEURAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
We analyze deep ReLU neural networks trained with mini-batch Stochastic Gradi- ent Descent (SGD) and weight decay. We show, both theoretically and empirically. that when training neural network using SGD with weight decay and small batch size, the resulting weight matrices tend to be of small rank. Our analysis relies on a minimal set of assumptions; the neural networks may be arbitrarily wide or deep, and may include residual connections, as well as convolutional layers. The same analysis implies the inherent presence of SGD "noise", defined as the inability SGD to converge to stationary point. In particular, must always be present, even asymptotically, as long as we incorporate weight decay and the batch size is smaller than the total number of training samples.
prove that SGD noise
INTRODUCTION
Stochastic gradient descent (SGD) is one of the standard workhorses for optimizing deep mod- els (Bottou 1991). Though initially proposed to remedy the computational bottleneck gradient descent (GD), recent studies suggest that SGD) also induces crucial regularization, which prevents overparameterized models from converging to minima that cannot generalize well (Zhang et al.) 2016 Jastrzebski et al. 2017 Keskar et 2017 Zhu al. 2019). Empirical studies suggest that SGD outperforms GD Zhu et al. (2019) and SGD generalizes better when used with smaller batch sizes (Hoffer al. 2017: Keskar al., 2017), and (iii) gradient descent with additional noise can- not compete with SGD Zhu et al. (2019). The full range of regularization effects induced by SGD, however, is not yet fully understood.
In this paper we present mathematical analysis of the bias of SGD towards rank-minimization. To investigate this bias, we propose the SGD Cear-Convergence Regime as a novel approach for investigating inductive biases of SGD-trained neural networks. This setting considers the case where SGD reaches point training where the expected update small in comparison to the actual weights' norm. Our analysis is fairly generic: we consider deep ReLU networks trained with mini- batch SGD for minimizing a differentiable loss function with L2 regularization (i.e., weight decay). The neural networks may include fully-connected layers, residual connections and convolutions.
Our main contributions are:
In Thm. M we demonstrate that training neural networks with mini-batch SGD and weight decay results in a low-rank bias in their weight matrices. We theoretically demonstrate that when train- ing with smaller batch sizes, the rank of the learned matrices tends to decrease. This observation is validated part of an extensive empirical study of the effect of certain hyperparameters on the rank of learned matrices with various architectures.
we study the inherent inability of SGD to converge to a stationary point, that we call 'SGD noise". In Props. we describe conditions in which 'SGD noise' is inevitable when training convolutional neural networks. In particular, we demonstrate that when training a fully- connected neural network, SGD noise must always be present, even asymptotically, long as we incorporate weight decay and the batch size is smaller than the total number of samples. These predictions empirically validated in Sec. 4.3
Sec. 3.2

---

Under review as a conference paper at ICLR 2023
1.1
RELATED WORK
A prominent thread in the recent literature revolves around characterizing the implicit regularization of gradient-based optimization in the belief that this is key to generalization in deep learning. Several papers have focused on a potential bias of gradient descent or stochastic gradient descent towards rank minimization. The initial interest was motivated by the matrix factorization problem, which corresponds to training a 2 linear neural network with multiple outputs w.r.t. the square loss. Gunasekar et al. (2017) initially conjectured that the implicit regularization in matrix factorization can be characterized in terms of the nuclear norm of the corresponding linear predictor. This con- jecture, however, was formally refuted by Li et al. (2020). Later, Razin & Cohen (2020) conjectured that the implicit regularization in matrix factorization can be explained by rank minimization, and also hypothesized that some notion of rank minimization may be key explaining generalization in deep learning. Li et al. (2020) established evidence that the implicit regularization in matrix factor- ization is a heuristic for rank minimization. Beyond factorization problems. Ji & Telgarsky| (2020) showed that gradient flow (GF) training of univariate linear networks w.r.t. exponentially-tan classification losses learns weight matrices of rank 1.
With nonlinear neural networks, however, things are less clear. Empirically, a series of papers (Den- ton al., 2014; Alvarez & Salzmann 2017; Tukan et al. 202T] Yu al. 2017 Arora et al. 2018)
showed that replacing the weight matrices by low-rank approximations results in only a small drop
in accuracy. This suggests that the weight matrices at convergence may be close to low-rank matri- ces. However, whether they provably behave this way remains unclear. [Timor et al. (2022) showed that for ReLU networks, GF generally does not minimize rank. They also argued that sufficiently deep ReLU networks can have low-rank solutions under L2 norm minimization. This interesting result, however, applies to layers added to a network that already solves the problem and may not have any low-rank bias. It is not directly related to the mechanism described in this paper, which applics to all layers in the network but only in the presence of regularization and SGD unlike (Timor al. 2022). A recent paper (Le & Jegelka. (202) analyzes low-rank bias in neural networks trained with GF (without regularization) While this paper makes significant strides in extending the anal- ysis in (Ji & Telgarsky, 2020), it makes several limiting assumptions. As result, their analysis is only applicable under very specific conditions, such as when the data is linearly separable, and their low-rank analysis is limited to a set of linear layers aggregated at the top of the trained network.
2 PROBLEM SETUP
In this work we consider a standard supervised learning setting (classification or regression), and study the inductive biases induced by training neural network with mini-batch SGD along with weight decay. Formally, the task is defined by a distribution P over samples (z, y) E X' x V, where X [R xhi xwn is the instance space (c.g., images), and y g is a label space.
We consider a parametric model F Ls': X + RR where each function fw E F is specified by a vector of parameters W E NN,, A function fw F assigns a prediction to any input point z E X, and its performance is measured by the Expected Risk, Lp == E(x.g)- [f( (z). v)], where : I²* x y + [0, oo) is non-negative, differentiable, loss function (e.g., MSE or cross-entropy losses). For simplicity, in the analysis we focus on the case where k: = 1.
Since do not have direct access to the full population distribution P. the goal is to learn pre- dictor, fw. from some training dataset S = {(Tx mm of independent and identically distributed (i.i.d)) samples drawn from P. Traditionally, in order to avoid overfitting the training data, we typ- ically employ weight decay in order to control the complexity of the learned model. Namely, we intend minimize the Regularized Empirical Risk, (fw) == m Di t ((f((x:) M.) + A||lW I|ž. where À > 0 is predefined hyperparameter. In order to minimize this objective, we typically use mini-batch SGD, detailed below.
Optimization. In this work, we minimize the regularized empirical risk (f( by applying stochastic gradient descent (SGD) for a certain number of iterations T'. Formally, we initialize Wo using a standard initialization procedure, iteratively update W, for T iterations and return Wr. At each iteration, we sample subset Š = {Zii) Bir)) 3= C S uniformly at random and update We1 W.- w I. (Sw:), where μ 0 is a predefined learning rate.
2

---

Under review as a conference paper at ICLR 2023
Notation. Throughout the paper, we use the following notations. For integer k 2 1, [k] {I....,k), ,k}. ||ж|| denotes the Euclidean norm. For two given vectors I' E R",y' E R we define their concatenation as follows (ælly) == (Z), (Z1,...., Zn: ,i...... :....)))))))) E R For a given matrix .......Z.
x E RR we denote Ti.; its i'th row and by vec(x)) = (rill-.. ||x.)) its vectorization. For a given tensor x E R we denote by vec(a)) == (vec(z1)ll ... vec(2))) the vectorized form of x. We define tensor slicing follows, Tarb = (Za:..., 26).
2.1 ARCHITECTURES
In this work, the function fw represents a neural network, consisting of set of layers of weights interlaced with ReLU activation units. We employ fairly generic definition of neural network, that includes convolutional layers, pooling layers, residual connections and fully-connected layers.
(V, E), where V= -fr...... ) consists of the various layers of the network and each edge eij (vt, U2) E E specifies a connection between two layers. Each layer is function v geixhixwr + R pexxh;x and each connection ub) holds a transformation C : & Xwy + Raxh,xu, The layers are divided into three categories: (i) the input layer U1. (ii) the output layer uz and (iii) intermediate layers. In this setting, we do not have connections directed towards the input layer nor connections coming out of the output layer (i.e., Y [L] (ez, v;), (co, v,) E). Given an input Re ge; the output of a given layer 0; is evaluated as follows v2(x)) = (C C (1z(z))), except for the output layer uz that computes fw(x)) = (x) = Ejepredlt) (hi(o) Here, pred = [j E [Z.] | 0y) E F), succ(i) : (j E [T.] (uy, E F} and a is the ReLU activation function. Each transformation C either trainable (e.g., a convolutional layer) or constant affine transformation (e.g., a residual connection). We denote by ET the set of trainable connections. In this paper, we consider the following transformations.
Network architecture. Formally, Sw as a directed acyclic graph (DAG)
Convolutional layers. A convolutional layer (Lecun et al. 1998) (see also Goodfellow et al. ) C Re Xw;; Baxx, XMs with kernel sizes (k1, k2). padding p and stride s param- eterized by a tensor Zö E RRxxes x and computes the following tensor as output
(c,,1) (c)4))))()))))))x(( Mort = vec(Ze.e, T -ved(Pad, (1+1)atk),d (1+1))+1g)) (1)
Here, Pady takes a tensor I E Rexhxx and returns new tensor x' E (h (hx+ (ww)2)) where the first and last p rows and columns of each channel x' :: are zeros and the middle x w tensor
equal to Te, F.. :.: The formulas for the output dimensions are hr = (1 hι + 2p) /s + 1) and w2 ([(w) k2 + 2/) + 1). For a given convolutional layer C with weights 2 we define a matrix V E Re:h; Keyh,mn that computes V x E (Kg
vevcc( = (C)))))) This matrix exists since both the padding and convolution operations can be represented as linear operations of the input. We also consider W E Xe, which is matrix whose e'th row is the vectorized filter W == vec (o
Fully-connected layers. As special case of convolutional layers, the network may also include fully-connected layers. Namely, a fully-connected layer F cR > Re associated with a matrix W E Ree can be represented as 1 x convolutional layer C RRxxxxl - Rexxix with
k1 = ln = 1. = 0 and s = 1. Namely, the parameters tensor Z E Rexxxxxxx satisfies Zo, W. for all (a, [c2] x [c1] and the layer satisfies vec(C(z)) Wvee(z).
Pooling layers. A pooling layer (Zhou & Chellappa 1988) (see also GGoodfellow et al. 2016 C with kernel dimensions (k1, 12)) stride and padding p takes input E Rº X xwi and computes an output y E R x x x2 with 02 = C₁ channels, and dimensions hr = (1(hh b + 2p) 1/s /s 1)
and Wi = ([(w) 12 + 2/) //s 1). Each pooling layer computes the following tensor output
A (,,, E [c]] x [hx) x [ws] Ve.t.t op( oPPad, ((+1)s+h),ee (I+1)++k))
where op is either the maximum or average operator.
Rearrangement layers. To conveniently switch between comvolutional and connecedd layers, we should be able to represent tensor layers as vectors and vice versa. To reshape the representation of certain layer, allow the networks include rearrangement layers. A rearrangement layer
3

---

Under review as a conference paper at ICLR 2023
C Ro xhyx + Rexxkoo: takes input vector E Royxhy x and 'rearranges' its coor- dinates in a different shape and permutation. Formally, it returns a vector (I=(M))Re(s))> (1,)x())) where i [cy] x [hy]] x [wy] + [a] x [h:]] [w:]] is invertible (in particular, c,h, = wyy)wyy)
THEORETICAL RESULTS
In this section describe main theoretical results. We investigate the inductive biases that emerge near convergence when training with SGD. For this purpose, we begin by introducing our definitions of SGD convergence (and near convergence) points.
To formally study convergence, we employ the notion of convergence in mean of random variables. Namely, we say that sequence of random variables {W,}== C RR starting from certain vector Wo E RN (constant) converges in mean if the following holds
3 W E R lim E||
W [|] 0.
As consequence of this definition, we have
lim W+1 Well < lim B|ll - W lim E|] t-00
w*lll 0,
1000
where the expectations are taken over the selections of the is possible only when the expected size of each step tends to zero. In particular, when training the network using mini-batch SGD along with weight decay, we have
In particular, convergence
lim V (ww:)l = lim BBll - Will = 0.
1-000
t-
In this work we study the implicit biases of SGD by investigating the "SGD Near Convergence Regime", where SGD arrives at point in training where each subsequent step is small compared the actual weights, i.e., Eglll V W L3 (fwx)) W| II] is small. In Sec. 3.1 show that near- convergence, mini-batch SGD learns neural networks with low-rank matrices and in Sec. 3.2 prove that perfect SGD convergence is impossible in the presence of weight decay.
We acknowledge that our definition differs from the traditional notions of convergence. Several papers study the convergence of SGD to a point where the performance is near-optimal when the learning rate μt decays with the number of iterations. In these cases, convergence is guaran- teed since Ne tends to zero. These papers, however, do not analyze whether the expected gradi- ents Eg V w L (fw.))l also decays at each step. Other papers (e.g.. (Soudry & Carmon 2016 Cooper 2021)) study the critical points of the objective function to better understand the solutions of gradient- optimization methods. While understanding the critical points of the objective function is necessary for characterizing the convergence points of GD and GF, SGD does not neces- sarily converge at these points. For instance, suppose W, is stationary point of (f()) and there exists batch Š for which V L (fw:)) # 0. With probability (?7) -1 > 0 SGD selects the batch S and updates W++1 = W, -VL (fw.) き W,. Therefore, p P[W++1 * W. W.] > O and FB1 [T' WiTh # We Wi] 2 1 (1 (1- p)T' T-
1. As a result, the probability of the
optimization becoming stuck at W, indefinitely is zero
3.1 LOW-RANK BIAS IN NEURAL NETWORKS
We begin our theoretical analysis with the simple observation (proved in Appendix A that the number of input patches Nis of a certain convolutional layer C upper bounds the rank of the gradient of the network w.r.t. W
Lemma 1. Let fw be a neural network and let O be convolutional layer within fw with param- eters matrix W Then, rank WW fw(x)) & Nis.
Interestingly, we obtain particularly degenerate gradients for fully-connected layers. As discussed in Sec. 2.1 for a fully-connected layer C R + xxxxxxx we have N = 1, and therefore, rank wo fw (x)) < 1.
The following theorem provides an upper bound on the minimal distance between the network's weight matrices and low-rank matrices.
4

---

Under review as a conference paper at ICLR 2023
be any matrix norm and any differentiable loss function. Let fa(x) be ReLU neural network and C* be a convolutional layer within fw and let E [m]. Then,
Theorem 1. Let ||
min PEEn%:X,,
W TW
WIl
min VV L/ SCS:
2x
(nk(W))
S$|=B
Proof. Let S S be batch of size B. By the chain rule, we can write the gradient of the loss function as follows
V way (/w)
Σ
BRff (a)a), ofw(x)
Vwo 2AW -Fg + 2AW
(
According to Lem. we have rank(
Eg)) BN Therefore, obtain that 2x
min W: (W)k
|W - W S
min 8C8:
181=8
W
2x Egll
2x
scs: 18
min
Finally, by dividing both sides by | ||
we obtain the desired inequality.
The theorem above provides upper bound on the minimal distance between the param- eters matrix W and a matrix of rank I BN The upper bound is proportional to, ming V|V w T. (fw))l/ [| which is the minimal norm of the gradient of the regularized em- pirical risk evaluated batches of size B, normalized by the norm of the weight matrix. As shown to be small, and therefore,
in equation near convergence we expect EgllI w L (fw (f ||/|||
ming V w (fw))l/ //////////// should also be small (S is distributed uniformly as a batch of sam-
ples size B). In particular, by the theorem above, we expect minw: rank(W) ( || Wy also be small. As result, we predict that the rank of the learned parameter matrices W decreases with the batch size. In Sec. [ we validate this idea with an extensive set of experiments - and also study the relationship between the rank and other hyperparameters.
[ W| to
3.2 DEGENERACY AND THE ORIGIN OF "SGD NOISE"
As we mentioned, it is impossible for SGD to converge to stationary point of the gradient dynam- ical system, resulting in inherent "SGD noise". In this section, we study the cooveeecneeeeeeee of mini-batch SGD. Our results are essentially impossibility results: the assumption of SGD conver- gence critical point of the gradient implies that the network represents the zero function. As result, asymptotic noise is inherently unavoidable (when training properly). For simplicity, we assume that V E [m] : xi &
As shown in equation any convergence point W of SGD satisfies E3 V (f = 0. Since the distribution over mini-batches Š of size is discrete and (/w)) 2 0, we obtain that at convergence we have WWW 0, for all bini-batches 5 of size B. In particular,
Vš 0 Vww
Σ
(e) Vwefw(z) + 2AW 0fw(z)
B
(R.))E
Suppose we have two batches S1 S of size B that differ by only one sample. We denote the unique sample of each batch by (I Ui and (I)n respectively. We notice that,
0 = Vw It (Jw) - Vwe (fw) (2, ).91) TwoSs(ayh 0fw (a,))
0fw(#52)
Therefore, we conclude that for all j1. E [m].
MI = (e(Sw(en))w))) fwofw(1z)) = (fw()s))
(llf 0fw(%))
Vwo (Dzz).
(5)
Hence, for all (1,, v2)) Er and l: E [m],
0fl (ze)we), Vwuf(Ix) + 2AW's MD +2WW 0.
(6)
(*x)
5

---

Under review as a conference paper at ICLR 2023
Therefore, unless À = 0 or V (U,, 1y) E Er W = 0, conclude that (e(fu:(ax))3)) o 0 for all (fw(
(sw) 1 are collinear vectors by equation k E [m]. In this case, we also obtain that { (2
Therefore, any convergence point of training a neural network using mini-batch SGD along with weight decay is highly degenerate and does not fit any one of the training labels. To better understand the essence of this degeneracy, we provide the following proposition (proved in Appendix A), which is specialized for ReLU networks.
(A > 0). Let E(a,b) be a differentiable loss function, X > O, and let fw( be ReLU neural network, where succ(1)- = {p} and (Fpp v1) E Er. Let { N be the NP1 patches of
Proposition
i, used by the layer CP1. Let W be a convergence point of mini-batch SGD for minimizing L.g (Jw) (see equation 4.. Then, either fw = i.je [ma] [ x/)) k==1
Ne1 are linearly dependent tensors.
The preceding proposition shows that unless the patches of any two training samples are linearly dependent, any convergence point of SGD corresponds to the zero function. When NPl is small, the linear dependence criterion unrealistic. For example, if CPI a fully-connected layer, Nel 1, and the condition asserts that any two training samples F;, 2. are collinear. Since this is unrealistic, we conclude that convergence is impossible unless fw = O.
As next step, we consider convergence of SGD when training without weight decay.
Proposition (A = 0). Let = and let be differentiable loss function. Let Jw fw(x) be ReLU neural network, where succ(1) = {p} and (Up, U1) E Er is fully-connected. Let {a) sk-1 be the Ne1 patches of x; used by the layer CP1, Let W be a convergence point of mini-batch SGD (x)))))))))))) = 0 or fw(x;) 0 or V E [m]] for minimizing (fw). Then, V E [m] (fw(#:)
NN
{at x. 1im1 1
No are linearly dependent tensors.
The preceding proposition (proved Appendix A provides conditions for SGD convergence of training convolutional network without weight decay. It shows that at convergence, for every sample the network either perfectly fits the label (i.e., (l(fw(=))))) 0) or outputs zero unless the (x.)
patches of that sample are linearly dependent with the patches of any other sample. As mentioned, the linear dependence criteria is generally unrealistic when (1p, u1) is fully-connected. Therefore, convergence with folly-connected networks is possible only when fw perfectly fits the training set labels.
We note that if E(a, b) is convex and has no minima a for any E R (e.g., binary cross-entropy, lo- gistic loss or exponential loss), then V i E [m] 86(fw (w.)..) + 0. Therefore, the only possible con- (fw((;)
vergence points of fully-connected networks are ones for which V e [m] : fw (z:)
Since this is in general absurd, we argue that perfect convergence of training network with exponential-type loss functions is generally impossible. While convergence to a non-zero function not guaranteed, in practice training without weight decay may still fall into the regime of 'almost convergence', in ae(fw (a.).u) @fw(zz) aW
which max:e[m] [el(fw (x.).8:] is tiny and a result the training steps -μ 0lw [x,(
are very small. This usually the case when an overparameterized network has been properly trained. For the squared loss, convergence may occur when the network perfectly fits the training labels, i.e., Vi E [m] (w. = y/-
It is worth noting that training with mini-batches during optimization and weight decay are critical to our analysis. While many papers examine the training dynamics and critical points of GD, as we show, SGD convergence points are highly degenerate and, in general, behave differently than GD solutions. Surprisingly, this analysis is unaffected by batch size, and therefore, the presence of SGD noise occurs regardless of batch size, as long as it is strictly smaller than the full dataset's size.
EXPERIMENTS
In this section empirically study the implicit bias towards rank minimization in deep ReLU net- works. Throughout the experiments we extensively vary different hyperparameters (c.g., the learning rate, weight decay, and the batch size) and study their effect the rank of the various matrices in the

---

Under review as a conference paper at ICLR 2023
Eooch
keoch
300
keach
300
kzach
300
kaach
0.03
0.05
0.1
0.3
Figure I: Average ranks and accuracy rates of MLP-BN-100-00 trained on CIFAR10 with various batch sizes. The top row shows the average rank across layers, while the bottom row shows the train and test accuracy rates for each setting. Weight decay À 5e-4 was used to train each model. To calculate the rank, we used an = 0.001 threshold.
teech
Exech
Exet
Exar
120
300
300
B
B
Figure 2: Average ranks and accuracy rates of ResNet-18 trained on CIFAR10 with varying weight decay. In this experiment: μ = 1.5 and = 0.001.
network. In addition, experimentally analyze the convergence (and non-convergence) of training neural networks with SGILI
4.1 SETUP
Evaluation process. We consider k-class classification problems and train multilayered neural network fw F RR on some balanced training dataset S. The model trained using CE/ MSE loss minimization between its logits and the one-hot encodings of the labels. After each epoch, we compute the averaged rank across the network's weight matrices and its train and test accuracy rates. For convolutional layer C*i we use W as its weight matrix. To estimate the rank of given matrix M, we count how many of the singular values M M/I|M]] are & [-6, e], where is small tolerance value. In these experiments we consider the MNIST and CIFAR1O 10 datasets.
Architectures. We consider several network architectures. (i) The first architecture is an MLP, denoted by MLP-BN- L-HH which consists of L hidden layers, where each layer contains fully- connected layer of width H. followed by batch normalization and ReLU activations. On top of that, we compose fully-connected output layer. (ii) The second architecture, denoted by RES- BN-L-H, consists of linear layer of width H. followed by L residual blocks, ending with fully- connected layer. Each block computes a function of the form + (n2( (W12)))) where
'The plots hest viewed when zooming into the pictures.

---

Under review as a conference paper at ICLR 2023
keach
Eeech
13 28
13 88
13 22
11
0.004
Ar 0.008
0.02
0.04
Figure 3: Average ranks and accuracy rates of VIT trained on CIFAR1O with various batch sizes. In this experiment: 5 and c 0.01.
CIPARIO CE
30
20B
100
200
1906 2310 160
30"1
2012
CHPARIO MSE
LINTS H07
30--
1744
Epscr
(a)
(b)
(c)
(d)
Figure 4: Convergence of MLP-5-2000 trained on CIFARIO. In (a) we plot the averaged distance
between the weight matrices at epoch and epoch t - 1, captured by, d(W W,). In (b) we plot the train accuracy rates, in (c) we plot the averaged train loss and in (d) we plot the average rank across the trainable matrices.
Wi, W2 E RHHH ni, n2 batch normalization layers and is the ReLU function. We denote by MLP-I-H and RES-L-H the same architectures without applying batch normalization. (fii) The third, denoted VGG-16, the convolutional network proposed by |Simonyan & Zisserman (2014).
but with dropout replaced by batch normalization layers and with only one fully- colnecconeected layer at the end. (iv) The fourth architecture the residual network proposed in (He et (016)), denoted
ResNet- 18. (v) The fifth layer is small visual transformer (Dosovitskiy et al. (020). denoted by VIT. Our VIT splits the input images into patches of size x includes self-attention heads, where each one of them consists of 6 self-attention layers. The self-attention layers are followed by two fully-connected layers with dropout probability 0.1 and a GELU activation between them.
4.2 EXPERIMENTS ON RANK MINIMIZATION
In each experiment we trained various models while varying one hyperparameter (e.g., batch size) and leaving the other hyperparameters constant. The models were trained with SGD for cross- entropy loss minimization along with weight decay. For MLP-BN-10-OE we decayed the learning rate three times by a factor of 0. at epochs 60, 100, and 200 and training is stopped after 500 epochs. We train instances of ViT using SGD and the the learning rate is decayed by a factor of 0.2 three times at epochs 60, 100 and training stopped after 200 epochs. By default, trained the models with weight decay X = 5c-4.
ResNet-18 and VGG-16.
As can be seen in Figs. and 3 by decreasing the batch size, we essentially strengthen the low- rank constraint the network's matrices, which eventually leads to matrices of lower ranks. This
8

---

Under review as a conference paper at ICLR 2023
is consistent with the prediction made in Sec. 3.1 that lear matrices with lower ranks when training the network with smaller batch sizes. Interestingly, we also notice a regularizing effect for the learning rate; the average rank tends to decrease when increasing the learning rate.
As can be seen in Fig. 2 by increasing we typically impose stronger rank minimization constraints. Interestingly, it appears that the batch size have little effect the ranks of the weight matrices when training with À = 0 which is exactly the case when our bound is infinite. This empirically validates that weight decay is necessary obtain significant low-rank bias.
4.3 EXPERIMENTS ON SGD NOISE
In Sec. 3.2 we showed that convergence to a non-zero function is impossible when training fully- connected neural network with SGD and weight decay. To validate this prediction, we trained MLP-5-2000 instances examined their convergence a function of X. Each model was trained for CIFARI0 classification using SGD with batch size 128 and learning rate 0.1 for 2000 epochs.
To investigate the convergence of the networks, measure the averaged distance between the network's 's matrices between consecutive epochs: d(W Wi) |Frl D(p.re [ W:'l,, Il.
1
where (Wr) Ey are the various trainable matrices in the network at epoch t. As mentioned in Sec. 3 convergence is possible only when lim d(W.+1, W2) 0.
In Fig- 4 we monitor (a) d(We+1. Wt). (b) the train accuracy rates, (c) the train losses and (d) the averaged rank of the trainable matrices. predicted Prop. [ when training with > 0, W; either converges to zero and fw, to the zero function (e.g., see the results with X = 1e-4, 1e-3) or W, does not converge (i.c., d(Wi+1, W:) does not tend to zero). Furthermore, we observe that for (+1
A = 0, dd Wa) is smaller by orders of magnitude compared to using À > 0 (except for cases when the selection of À > leads to W.d 0). Interestingly, even though for certain values of
A > 0, the training loss and accuracy converged, the network's 's parameters do not converge.
Finally, when training for cross-entropy loss minimization without weight decay we encounter the "almsst convergence' regime discussed in Sec. 3.2] Namely, even though perfect convergence is impossible, the term d(W,+1, Wi) may become as small as we wish by increasing the size of the neural network. Therefore, since the MLP-5-2000 is relatively large (compared to the dataset's 's size), we may inaccurately get the impression that d(W,+) 111, W,) tends to zero.
CONCLUSIONS
mathematical characterization of the biases associated with SGD-trained neural networks is re- garded as a significant open problem in the theory of deep learning (Neyshabur et al.) 2017). In addition to its independent interest, low-rank bias - though probably not necessary for general- ization may be key ingredient in an eventual characterization of the generalization properties of deep networks. In fact, recent results (Huh et al., 2022) and our preliminary experiments (see Figs. 20 in the appendix) suggest that low-rank bias in neural networks improves generalization.
By investigating the "SGD Near- Bear-Cooverreecee Regime", we proved that SGD together with weight decay induces low-rank bias in variety of network architectures. Our result also shows that the batch size used by SGD influences the rank of the learned matrices. This means that the batch size plays active role in regularizing the learned function. We also prove that when training fully- connected neural network, SGD noise must always be present, even asymptotically, regardless of batch size, long as weight decay is used. Weight decay may not be strictly necessary for SGD noise and low-rank bias to appear. This is the case, for example, when training with exponential-tppe loss functions and Weight Normalization (Salimans & Kingma 2016).
We hope that our work will spark further research into the convergeee regime. For instance, it may provide an interesting algorithmic approach to the long-standing problem of developing low-rank regularizers during optimization. It would also be interesting to study whether additional structures (e.g., neural collapse (Papyan et al. 2020), sparsity) emerge during the near-convergence regime and to extend our analysis to more sophisticated learning algorithms (c.g., Adam (Kingmal & Ba 2015) and learning settings (e.g., unsupervised learning, self-supervised learning, etc).

---

Under review as a conference paper at ICLR 2023
REFERENCES
Jose M. Alvarez. and Mathieu Salzmann. Compression-awee -warre training of deep networks. In Proceed- ings of the 31st International Conference on Neural Information Processing Systems, NIPS'17 17, pp. 356-867, Red Hook, NY, USA, 2017. Curran Associates Inc. ISBN 9781510860964.
Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Zhang. Stronger generalization bounds for deep nets via a compression approach. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 Proceedings of Machine Learning Research, pp. 254-263. PMLR, 10-15 Jul 2018.
Léon Bottou, Stochastic gradient learning in neural networks. In Proceedings of Neuro-Nimes 91, Nimes, France, 1991. EC2. URL http: pttt:://lewn www.://ww...........e..eo pttptcc....////pppptt//tttttooaa
Yaim Cooper. Global minima of overparameterized neural networks. SIAM Journal on Mathematics of Data Science, 3(2):676 691, 2021. doi: 10.1 10.1137/9MM130944, URL http::tps:///o //tp:/o//ooooo//// 10.1137/19M133
Emily L Denton, Wojeiech Zaremba, Joan Bruna, Yann LeCun, and Rob Fergus. Ex- ploiting linear structure within convolutional networks for efficient evaluation. In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K.Q. Weinberger (eds.), Advances in Neural Information Processing Systems, volume 27. Curran Associates, Inc., 2014. URL httttppss//proceednggs..o [2fe5S59LEE42225577444444---2222
neurips. cctpapprr/211//111
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image is worth 16x16 words: Transformers for image recognition at scale. arXiv preprint arXiv:2010. 19299 2020.
Ian Goodfellow, Yoshua Bengio. and Aaron Courville. Deep Learning. MIT Press, 2016. http:
7/www. www.deeppeeannnnghoo.. org
Suriya Gunasekar, Blake Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, and Nathan Sre- bro. Implicit regularization in matrix factorization, 2017. URL httts:t//axxii org/ abs/ 1705. 09280
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In 2016 IEEE Conference Computer Vision and Pattern Recognition (CVPR), pp. 770-778, 2016.
doi: 10.1109/CVPR.2016.99.
Elad Hoffer, Itay Hubara, and Daniel Soudry. Train longer, generalize better: clos- ing the generalization gap in large batch training of neural networks. I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Gar- nett (eds.), Advances in Neural Information Processing Systems, volume 30. Curran Asso- ciates, Inc., 2017. URL a5e0f 3bo0fff2eebb445tttt1eeee32222223
Minyoung Huh, Hossein Mobahi, Richard Zhang, Brian Cheung, Pulkit Agrawal, and Phillip Isola. The low-rank simplicity bias in deep networks, 2022. URL
forum? d=dnn 7
Stanislaw Jastrzebski, Zachary Kenton, Devansh Arpit, Nicolas Ballas, Asja Fischer, Yoshua Ben- gio, and Amos Storkey. Three factors influencing minima in sgd, 2017. URL https:
//arxiv.org/aata
Ziwei Ji and Matus Telgarsky. Directional convergence and alignment in deep learning. CoRR, abs/2006.06657, 2020.
2006. 06657
Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Pe- ter Tang. On large- batch training for deep learning: Generalization gap and sharp minima. In International Conference Learning Representations (ICIR), 2017.
10

---

Under review as a conference paper at ICLR 2023
Diederick P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations (ICLR), 2015.
Thien Le and Stefanie Jegelka. Training invariances and the low-rank phenomenon; beyond linear networks. In International Conference on Learning Representations, 2022. URL https:/ // openreview net/ XetprummidxXXE88Q02200
Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner. mradieet-basede learning applied to document recog- nition. Proceedings of the IEEE, 86( 1):2278:222333) 2324, 1998. doi: 10.1
Zhiyuan Li, Yuping Luo, and Kaifeng Lyu. Towards resolving the implicit bias of gradient descent for matrix factorization: Greedy low-rank learning. CoRR, abs/2012.099833 2020. URL https:
Behnam Neyshabur, Srinadh Bhojanapalli, David Mcallester, and Nati Srebro. Exploring gener- alization in deep learning. In Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.). Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017. URL https: http:::sss///crceeeeeeee neurips cc/ pdf
Vardan Papyan, X. Y. Han, and David L. Donoho. Prevalence of neural collapse during the terminal phase of deep learning training. Proceedings of the National Academy of Sciences, 117(40):
14652-24663. 2020.
Noam Razin and Nadav Cohen. Implicit regularization in deep learning may not be explainable by norms. CoRR, Abs/2005.063998 2020. https://: /atp:i//aaivviiaaa prggabs//005. 06398
Tim Salimans and Diederik P. Kingma. Weight normalization: A simple reparameterization to accelerate training of deep neural networks. Advances in Neural Information Processing Systems, 2016.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. CoRR, abs/1409.1556. 2014.
Daniel Soudry and Yair Carmon. No bad local minima: Data independent training error guarantees for multilayer neural networks, 2016. URL Ltttsss//aaxtir..rrr//////1...0. 08361
Nadav Timor, Gal Vardi, and Ohad Shamir. nogplit maniiiiiiaaiiiiiiiiiiii relu networks. CoRR, abs/2201. 127660 2022. [BL./tttpss//aaxvl..oo/////////2
Murad Tukan, Alaa Maalouf, Matan Weksler, and Dan Feldman. No fine-tuning, cry: Robust svd for compressing deep networks. Sensors, 21(16), 2021. ISSN 1424-8220, doi: 10.3390/ s21 165599. URL https:::///... /ww:://wwwwwww. http://pp..oao//12222///////////
Xiyu Yu, Tongliang Liu, Xinchao Wang, and Dacheng Tao. On compressing deep models by low rank and sparse decomposition. In 2017 IEEE Conference on Computer Vision and Pattern Recog- nition (CVPR), pp. 67-76, 2017. doi: 10. 10.1109/CVPR..2077115
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. CoRR, abs/1611 1221661.03550 1.05300, 2016. URL [ 03530
/
Yi- Toonn Zhou and Rama Chellappa. Computation of optical flow using a neural network. JEEE 1988 International Conference on Neural Networks, pp. 71-78 vol.2, 1988.
Zhanxing Zhu, Jingfeng Wu, Bing Yu, Lei Wu, and Jinwen Ma. The anisotropic noise in stochastic gradient descent: Its behavior of escaping from sharp minima and regularization effects. In Pro- ceedings of the 36th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research. PMLR, 2019.
11

---

Under review as a conference paper at ICLR 2023
A PROOFS
Lemma 1, Let fw be a neural network and let Cd be convolutional layer within fw with param- eters matrix W Then, rank (Vw4fw(r)) S NO.
Proof. Let x E Rexx be an input tensor and (*) be certain convolutional layer with kernel size (ki, k2), stride and padding p. We would like to show that rank (V wes fw)) S N We begin by writing the output of fw sum over paths that pass through C* and paths that do not. We note that the output can be written as follows,
fw(x)
Σ
Clols vi, (2),
Epred(((o)
where lo L and Cholss 22:= Chals (2). In addition, each layer in can also be written as
U1, (x) = Dr, O Σ
chila o or, (I),
(ppred((11)
where Dj == Di(x)
:= = (vx(())) E Ra gaxkixx
A path æ within the network's graph G is sequence т (To, ..., ,T)) where To 1, Ny L and for all = O..... T - (Un, Ux41) ) E E. We can write fw (z) as the sum of matrix multiplications along paths æ from 21 to 1%.- Specifically, we can write fw (x) as follows
(w(x)
Σ
Day ... ..Drgg @ C Dry O C* 0)((x)
from to lg
Σ
C DD DzT-1 2 C DTg @ C oz,
lo
(
Aw (2) + (w
where T = T(x) denotes the length of the path Since is piece-wise linear function with finite number of pieces, for any E Rer with measure over W, the matrices (Di()))=² are constant in the neighborhood of W. Furthermore, W does not appear in the multiplications along the paths from to that exclude (i, Therefore, conclude that BBw 0.
aW
As a next step we would like to analyze the rank of 0Aw (ar) aw For this purpose, we rewrite the convolutional layers and the multiplications by the matrices Di(x) as matrix multiplications.
Representing C*s. We begin by representing the layer C as linear transformation of its input with NO blocks of Wy, For this purpose, we define a representation of a given 3-dimensional tensor input 2 E Ro xhyx as a vector (xc E N First, we pad with p rows and columns of zeros and obtain (z),.2). We then vectorize each one of its patches (of dimensions Cj x k1 x k2) that the convolutional layer is acting upon (potentially overlapping) and concatenate them. We can write the vectorized output of the convolutional layer as U Vec (z), where
W
0
0
0
0
0
0
W
0
(NDc.)) x (2) matrix with N copies of Vij We note that this is a non-standard representation of the convolutional layer's operation as a linear transformation. Typically, we write the convolutional layer as a linear transformation W acting on the vectorized version vec(z) e Re of its input 2. Since (ec*(2) consists of the same variables in vee(2) with potentially duplicate items, there is a linear transformation that translates vec(2) into (z). Therefore, we can simply write vévee(z)) U vee (z).
12

---

Under review as a conference paper at ICLR 2023
Representing convolutional layers. Except of C*i, represent each of the network's convolutional layers Cld in fw as linear transformations. As mentioned earlier, we can write vec(C"((z)) vec(2), for any input 2 Reaxhaxas
Representing pooling and rearrangement layers. An average pooling layer or a rearrangement layer Cld can be easily represented we can write vec(C"((s) = vec()) for some constant matrix Vid max-pooling layer can be written as a composition of ReLU activations and multiple (non-trainable) linear transformations, since max y) o(r - y) + y. Therefore, without loss of generality we can replace the pooling layers with non non-traine non-trainable linear transformations and ReLU activations.
(non-trainable) linear transformation of its input. Namely,
Computing the rank. Finally, we note that vea(C* z) = U (e) vióvec(z), vec(Di @ 2) Pt- vec(2) for diag(vec(Dii). Therefore, we can write
Aw (z)
E W P ... W Pr, U vec (v,(x))
from to
a(x) U
where a(x)" = Ex from lo Wo 1. 1.PaT- .... Pr..W WWP and b(x) := : vect (ey(z)) We note that with measure the matrices (Pi) are constant the neighborhood of W. In addition, a(x) and b(z) are computed as multiplications of matrices Wild and Pt excluding (i.j) (p, q)
Therefore, with measure 1 over the selection of W, the Jacobians of a(x) and b(x) with respect to Vij are 0. Furthermore, due to equation and the definition of U we can write
N
a(x) .U. b(x) = [a)(T) Vy by(x),
where (x) and (z) are the slices of a(x) and b(z) that are multiplied by the t'th V block in U+Ú_ Since the Jacobians of (x))) and b; (x) with respect to Vis are 0 with measure over the selection of W, we have,
0a(x) T .U. ((z))(x)... avij
NO
= (x) ( T.
(8)
Therefore, we conclude that, with measure over the selection of W, we have 0fw (w)
8VG
EN' de(x) (xx) which is a matrix of rank < N
Proposition
0). Let l(a, b) be a differentiable loss function, X > O, and let fw (x)) be
ReLU neural network, where succ(1) = {p) and (vp: v1) E Er. Let {2 k. No1 be the Ne1 patches of I; used by the layer CPl, Let W be a convergence point of mini-batch SGD for minimizing L (fw) (see equation 4. Then, either fw 0or i.j E [m]] Lat a I== are linearly dependent tensors.
Net
Proof. Since (()p)))) E D. E V} C Er is of size we denote this single layer by (Up. 01). Following the proof of Lem. I we define representation of given 3-dimensional tensor input Re Xhyykyx xws as vector vec (x: [x'').... 11x IR eykkkk, where x: is the vectorization of the k'th oj x k1 x kn patch of x. Similar to the proof of Lem. we can write
(w(x)
Σ
O Dar-i O 0*T-177-2... ... O C o.
from I to
H H(x) UPl vecP1 (I)
where H(x) = En from p to L Varzr-1 Par-1 (x:) ... V.RE Pa, (2x) and denote H, = H(x,)
and H, = (H,,.... H.N where H of dimension e cikik2 Hence, we can write,
NP1
ffw():) @Wrl
= -H H T
k=1
13

---

Under review as a conference paper at ICLR 2023
We would like to show that {af a No1 TR=1 are linearly dependent vectors or fw 0. Assume the [km1 are not linearly dependent and that fw # 0. In particular, by equation 9 have, W * O.
opposite by contradiction, i.e., that {- 23 .K1N%
According the analysis in Sec. 3.2
(zw( ym Ereect WP are collinear vectors. Therefore, for any pair
i,j [m)) there is scalar agy E R. such that, Σ H (x Oij E H (xf)).
Consider given index i E [m]] We would like to show that either H; = 0 or { . )== NPI a set of and M and WM according to equation [ which implies that fw 0 (since (eps 01) is the only connection starting from U1). Assume that H; * O. Then, there exist & E [N#l] and E [dim (dim(H.)NN')), for which the NP1
linearly dependent vectors. Assume that H; 0. Then, @fw(2,)
2WP
r'th coordinate of H is non-zero. Therefore, the r'th row Ek=1 (ar))
k= H -x Oaj Σk= H
is a non-trivial linear combination of the vectors {a x k=1
Nel
Proposition 2 (A = 0). Let = O and let be differentiable loss function. Let [w(x) be ReLU neural network, where succ(1) {/} and (1), E ET is fully-connected. Let Leke { be the N patches of x; used by the layer CPI, Let W be a convergence point of mini- batch SGD for minimizing (f(s). Then, V [m] (0.fw(m))).))) = 0 or fw(x,) 0 or V E [m] {at ah a Jkm are linearly dependent tensors.
8fw(#z)
Proof. Let [m]] be an index for which (f(fw( we have
O. Then, by equation 5 for all j E [m],
afw (ar))
@fw(2;) TelSs (elsw((a))) [el(sw(Z)):u)) (fw
0fw(x,) oWrl
(x:( (
(10)
OWwl
WWFT are collinear vectors (for all j E [m]). Hence, by the proof of Prop. I either (w, 0 or {a 1mm
afw In particular, W and (x,)
Ji=1 is a set of linearly dependent vectors.
14

---

Under review as a conference paper at ICLR 2023
B ADDITIONAL EXPERIMENTS
Experiments on rank minimization. To further demonstrate the bias towards rank minimization of SGD with weight decay, we conducted series of experiments with different learning settings. We follow the same training and evaluation protocol described in Sec. 4.2 The results are summarized Figs. 18
Experiments on SGD noise. We repeated the experiment in Fig. for training the models on MNIST. As can be seen in Fig. similar to the previous experiment, when the models were trained with À > 0, the weights W, were not able to converge (i.e., d(We+1 Wa) does not tend to zero), even though for certain values of X > the training accuracy and loss converged. On the other hand, when À = 0, the distance d(W W;) tends to zero.
Low-rank bias and generalization. We looked into the connection between low-rank bias and generalization. In Figs. 20 we trained ResNet-18 and VGG-16 instances on CIFAR10 while varying the batch size and keeping À and μ constant. To provide a fair comparison, we chose and j in each setting to ensure that all models fit the training data perfectly. As be models trained with smaller batch sizes, i.c. models with lower rank in their weights, tend to generalize better. Based on these findings, are trained with SGD with different hyperparameters and perfectly fit the data, the one with a lower average rank will outperform the other at test time.
hypothesize that when neural networks of the same architecture
MNNST. HCD
2012
Epscs
02653
MINIST; MSE
200th
115
banh
176 201
(a)
(b)
(c)
(d)
Figure 5: Convergence of MLP-5-2000 trained on MNIST with CE/ MSE loss. In (a) we plot the averaged distance between the weight matrices epoch and epoch f 1, captured by, Eel E( |[ w I]. In (b) we plot the train accuracy rates, in (c) we plot the averaged train loss and in (d) we plot the average rank across the trainable matrices.
02
30
Eoech
30
150
100
30
302
11
0.001
1 0.01
1 0.1
11 0.5
Figure 6: Average rank of MLP-BN-1001100 trained CIFAR10 with various batch sizes. Each model was trained with a À = 5c-4 weight decay. To estimate the rank, we used an 0.001 threshold.
15

---

Under review as a conference paper at ICLR 2023
02
B 16
B 32
B 64
B 128
Figure 7: Average rank of MLP-BN-10-100 trained on CIFAR10 with varying X. Each model was trained with n 0.1 initial learning rate and 0.9 momentum. To estimate the rank, we used an c 0.001 threshold.
11 0.0125
/ 0.025
11 0.05
11 0.1
Figure 8: Average rank of RES-BN-5-500 trained CIFAR1O with various batch sizes. Each model was trained with a 5e-4 weight decay. estimate the rank, we used an 0.001 threshold.
Spachh
Spach
kauch
0.0125
0.025
0.05
0.1
Figure 9: Average ranks and accuracy rates of MLP-5-500 trained on CIFAR10 with various batch sizes. Each model trained with 5e-4 weight decay. To estimate the rank, used an e = 0.001 threshold.
16

---

Under review as a conference paper at ICLR 2023
Epech
Erech
Erech
B
B 16
B 32
Figure 10: Average ranks and accuracy rates of MLP- trained on CIFAR10 with varying X. Each model was trained with = 0.1 initial learning rate. To estimate the rank, we used an 0.001 threshold.
kpach
$pach
510
Peachh
11 0.05
0.1
JA
0.2
JA 0.3
Figure 11: Average ranks and accuracy rates of MLP-5-500 trained on CIFARIO with various batch sizes. The models were trained with À 5e weight decay. To estimate the rank, we used an 0.001 threshold.
Co
Spach
bpach
Bauch
B
B
B 16
B 32
Figure 12: Average ranks and accuracy rates of MLP-5-500 trained on CIFARIO with varying X. The models were trained with a a 0.025 initial learning rate. To estimate the rank, we used an e = 0.001 threshold.
17

---

Under review as a conference paper at ICLR 2023
Exoch
Erech
0.5
0.8
1.0
2.0
Figure 13: Average ranks and accuracy rates of ResNet-18 trained on CIFAR1O with various batch sizes. The models were trained with X = 5e-4 weight decay. To estimate the rank, we used an c 0.001 threshold.
spach
6pach
62uch
200
B
B
B 16
B 32
Figure 14: Average ranks and accuracy rates of ResNet-18 trained on CIFARIO with varying μ.. The models were trained with a f = 5e-4 initial learning rate. To estimate the rank, we used an 0.001 threshold.
Spach
Spuch
0.1
0.2
0.3
0.5
Figure 15: Average ranks and accuracy rates of VGG-16 trained on CIFAR10 with various batch sizes. The models were trained with a μ 5e-4 initial learning rate. To estimate the rank, we used an = 0.001 threshold.
18

---

Under review as a conference paper at ICLR 2023
414
172
B 16
B 32
Figure 16: Average ranks and accuracy rates of VGG-16 trained on CIFARIO with varying X. The models were trained with μ 0.1 initial learning rate. To estimate the rank, we used an 0.01 threshold.
spach
kpach
6107h
B
B 16
B 32
Figure 17: Average ranks and accuracy rates of VGG-16 trained on CIFARIO with varying μ. The models were trained with a μ = 5e-4 weight decay. To estimate the rank, we used an e 0.001 threshold.
132
332
312
302
111 20
10
111
10
11
20
30
170
22
144ch
Be4ch
beach
B 16
B 32
B 64
B = 128
Figure 18: Average ranks and accuracy rates of VIT trained on CIFAR10 with varying X. The models trained with a F 4e-2 initial learning rate. To estimate the rank, used an 0.01 threshold.
19

---

Under review as a conference paper at ICLR 2023
340
144
144
328-
Avcrage Farv
Avcrog
100
200
390
420
500
106
300
450
165
300
451
300
Epoch
0.4
22
34
04
4.0
116
200
993
400 510
44
166
260
410 106
200
5000
.12
100
Epoch
Epoch
Epoch
(a)
(b)
(c)
Figure 19: Average ranks and accuracy rates of ResNet-18 18 trained on CIFARIO with different batch sizes. We show the relationship between average rank and test performance. (a) was trained with μ 0.001, À = 6e 6e-3, 3, (b) was trained with = 0.005, À = 6e-3, and (c) was trained with
f 0.01, A 4. To estimate the rank, we used an e 0.05 threshold.
200
Avorage Rami
258
:58
2.53
AV%
200
420
250
200
Epoch
AcCursty
22-
32
02
2.
116
200
303
420
500
2.
106
200
200
410
100
03
100
200
200
622
500
Epoch
Epoch
(a)
(b)
(c)
Figure 20: Average ranks and accuracy rates of VGG-16 trained on CIFAR10 with different batch sizes. We show the relationship between average rank and test performance. (a) was trained with μ = 0.001, A = be 3, (b) was trained with 0.005, X = 5e - 4, and (c) was trained with f 0.01, 4. To estimate the rank, we used an c 0.04 threshold.
20


Reviews:
[{"review_id": "GOdBs273Zg", "reviewer": "Reviewer_c3Es", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes studying SGD at the \"near-convergence regime,\" which it defines as a point in training where each subsequent update is small compared to the actual weights. First, the paper shows in Theorem 1 that in this regime, with weight decay $\\lambda>0$ and batch size $B$, the parameter matrices are close to a low rank ($\\propto B$) approximation (in any matrix norm). Then the paper shows that for $\\lambda>0$, SGD doesn't converge for usual non-stylized data sets. This means there is always some non-zero \"SGD-noise\" when training with weight decay. However, when $\\lambda=0$ and the loss function has real minima (such as square loss), SGD converges only if the model perfectly interpolates the data. Experiments are provided to evaluate these theoretical results. ", "summary_of_the_review": "I am concerned about the technical novelty of the paper and thus am inclined towards rejecting it. I believe the results in the paper require more work and need to be better put in context with the existing literature in deep learning theory.\n\n------------------------------------------------------------------------------------------------------------------------------------------------------------\n\nAfter reading the concerns pointed out by the reviewers, especially reviewer g7pt, I am convinced there are major issues with the results in the paper. Thus I am reducing my score. ", "strength_and_weaknesses": "### **Theorem 1 and Experiments**\n\nWhy are there no experiments showing how small the right-hand side is in theorem 1 for the models considered in the experiments, i.e., is SGD actually in the near-convergence regime? Further, it would be good to discuss in the experiments how small $BN^{ij}$ is for the considered models. \n\nAlso, considering the near-convergence regime without mentioning the step size doesn't seem reasonable. As the authors mentioned, with decreasing step size, SGD would indeed converge, albeit forcefully. And with constant step size, one would hope it converges up to a ball around some fixed point, even if the consecutive steps don't imply convergence (see papers like [this](https://arxiv.org/abs/1707.06386) and [this](https://arxiv.org/abs/2006.07904)). Usually, there is a periodic step-size decay when using SGD. Thus the correct notion of convergence should be measured by the actual update (step size times the gradient) normalized by the scale of the parameter. \n\nFurther, the bound in the theorem does not show any non-asymptotic dependence on the step size $\\mu$ or other problem-dependent parameters (such as the initial parameter norm, lipschitzness, etc.). As a result, it is hard to interpret the result without understanding how small the right side is for a specific neural network, optimizer, and set of hyper-parameters. This gets more confusing when one looks at the experiments. It is unclear if the rank-minimization happens before or after the model has \"converged.\" \n\nAnother issue is the conflation between step size and batch size. Ideally, one would tune the step size separately for each batch size, i.e., ensure that the step size offers optimal convergence for the training budget. This would avoid needing four different columns in figures 1 and 3. It seems like some of the differences in rank can be ascribed to non-optimal step-size selection. For instance in figure 1, $B=4, \\mu=0.03$ curves look much more comparable to $B=32, \\mu=0.3$ curves, than $B=4, \\mu=0.3$ (and similarly for figure 3). Based on the theory, there seems to be no reason to compare different batch sizes with the same step size. Am I missing something? If not, the authors should report revised experiments where the step size is treated as a part of the optimizer and tuned optimally.  \n\n### **SGD Noise**\n\nThe observations in section 3.2 are not very surprising. These are good-to-know results but add little to our understanding of the implicit regularization of SGD. For instance, without weight decay, exponential losses are minimized at infinity. In contrast, the square loss is minimized at a unique point is a classical learning theory fact about surrogate losses. And this is often exploited in studying neural networks in the interpolation regime. Proposition 2 almost seems tautological. And showing proposition 1 is not complicated, given the architecture's formalism. Understanding how the SGD noise goes to zero as the batch size increases would be exciting and might not be a problematic extension.     \n\n\n\n  ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "8v0bW5757Xa", "reviewer": "Reviewer_g7pt", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors of the presented paper try to present why SGD + weight decay tend to converge towards low rank solutions.", "summary_of_the_review": "The authors consider as a cornerstone of their analysis an empty assumption. Maybe this idea of low rank can be fruitful in the future and I encourage the authors to pursue their efforts but under this shape I will reject the paper.", "strength_and_weaknesses": "The authors of the paper show that, due to the weight decay, SGD **cannot**, in parameter space, converge towards a point. This is done in Section 3.2 and I totally agree with this result. It is also said that weight decay is crucial to have this property. True.\n\nThat being said, I believe that it is easy to further show that the presence of weight decay will cause the non-degeneracy of the noise implying the irreducibility of the SGD as a Markov Chain on a certain domain in parameter space. **Hence**, *the near convergence* depicted in the first equation of Section 3 cannot occur (even in expectation): there is not single point towards which the dynamics can concentrate except if the authors prove it on **the law** of the iterates ! To give a concrete appreciation of this vacuous assumption, consider the Ornstein-Uhlenbeck process: $d W_t = - W_t dt + \\sqrt{2} dB_t$, there shall not exist a $W^*$ such that $\\mathbb{E}|W_t - W^*| \\to 0$ as $t \\to \\infty$. Here the good object that authors can consider if they want to pursue in this direction is either to focus on the law of $W_t$, either to consider $W_*$ as a random variable coming from this law. \n\nFinally, all the remaining calculations and conclusions collapse. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "4RgxmHk_61t", "reviewer": "Reviewer_g7fW", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the convergence of SGD over deep ReLU neural networks. \n\n**Theoretical Results**\n\nIn the case with weight decay, the authors prove:\n\n1. The weight matrix can be approximated by a low-rank matrix with error bounded by the smallest batch gradient norm across batches (batch gradient stands for the gradient of the loss calculated from batch). \n\n2.  If all batch gradients are $0$, then all the parameters are $0$.\n\n**Experimental Results**\n\n1.  On image tasks, decreasing the batch size or increasing the learning rate leads to a decrease in weight matrix rank. \n\n2. On image tasks, with weight decay, the change in parameters $W_{t+1}-W_{t}$ does not converge to $0$.", "summary_of_the_review": "Based on the above evaluations, I think that the current version of this paper needs to be improved to meet the bar of acceptance, especially the theory part. ", "strength_and_weaknesses": "**Strength**\n\nThe paper is well-written, and the message is easy to get.\n\n**Weakness**\n\n1. The theoretical results seem to be paradoxical. Theorem 1 approximates the weight matrix by a low-rank matrix when the batch gradient norm is small. However, Proposition 1 shows that this is impossible.\n\n2. Theorem 1 does not necessarily lead to the low-rank bias. First of all, the bound has a $1/2\\lambda$ factor. As $\\lambda$ is usually small in practice ($5e^{-4}$, as an example), it is quite possible that the bound is vacuous. Secondly, even when the bound is small, it only indicates that the weight matrix can be approximated by a low-rank matrix in terms of $\\ell^2$ error. This does not necessarily imply the weight matrix itself is low rank. Finally, even if Theorem 1 indicates a low-rank bias, the results are not comparable across different batch-size -- it only shows that with different batch sizes $B$, the weight matrix can be approximated by matrices with different ranks $R(B)$. It does not rule out the possibility that matrices with ranks smaller than $R(B)$ can also approximate the weight matrices.\n\n3. What does Proposition 1 imply? While SGD does not converge to a stationary point, it can oscillate around it -- which is usually the case in practice.\n\n4. I wonder whether the experiments can be explained by the theoretical results. Specifically, for figure 1 and figure 2, I suggest that the authors should plot the batch gradient norms to see whether they are small.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "-j2VfMQfTx", "reviewer": "Reviewer_897C", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper considers training neural networks with SGD and weight decay. It contains two main theoretical results:\n(1) When the batch size is small, convergence of SGD to parameters $W$ implies that the parameters matrices $W^{ij}$ are close to low-rank matrices.\n(2) Unless the dataset is degenerate (i.e., patches of each two examples are linearly dependent) or the learned model is trivial, SGD with weight decay cannot converge to a stationary point. SGD without weight decay can converge to a non-trivial stationary point if the dataset is degenerate, or the predictor perfectly fits the labels.\n\nThe authors demonstrate empirically that increasing the weight decay or decreasing the batch size encourages small ranks. They also demonstrate empirically that SGD with weight decay does not converge to non-zero functions.", "summary_of_the_review": "Due to the issues discussed above, I recommend rejection. I would be happy to read the authors’ response and reconsider.", "strength_and_weaknesses": "Let me start with the theoretical results on SGD noise. The main insight here is that when the objective contains $\\ell_2$ regularization, the requirement of having zero gradients for all possible batches is very strong, and implies that the gradients of the model for different examples must be collinear. As a result, the authors show that stationary points exist only in degenerate cases. I think that it is a nice and simple insight, and I am not aware of prior works that used it.\n\nRegarding the theoretical result on rank minimization, I must say that I am confused. The authors prove (in Theorem 1) that when training with small batches and weight decay, the distance between the weight matrix and a low-rank matrix is bounded by the gradient of the regularized loss w.r.t. a batch of inputs. Then, the authors claim that they expect this gradient to be small “near convergence”. However, the theoretical results on SGD noise imply that this assumption is strong and might not hold in practice. Thus, it is not clear whether for sufficiently large time $t$ the gradient of the loss w.r.t. a batch should be small. The authors justify this assumption with Eq. (3). However, Eq. (3) follows from the “convergence in mean” assumption, which is puzzling. The “convergence in mean” assumption tells us that there exists $W^*$ such that for a sufficiently large $t$, we have w.h.p. that $\\| W_t -W^* \\|$ is small. Thus, it assumes that SGD (possibly with a small batch size) behaves in a deterministic way, since it is guaranteed to be close (w.h.p.) to this specific $W^*$. I don’t think that this assumption should hold in practice.\nMoreover, in the empirical results in Figure 4(a) it seems that the parameters do not converge when training with weight decay. If the authors claim that the gradient does not converge to zero but is “small” for large $t$, then the question is what can be considered “small”. Thus, it requires further analysis and more evidence.\n\nThe experiments are nice, and suggest that small batch sizes and weight decay encourage rank minimization, and also that SGD with weight decay does not converge. However, the paper aims not only to show empirically that there is rank minimization, but also to explain it with Theorem 1. Hence, I would be happy to see how the theoretical bound (the RHS of the equation in Theorem 1) looks in practice (at least roughly). It is not clear to me whether Theorem 1 indeed explains the empirical results on rank minimization.\n\nAdditional comments:\n- Related work:\n    - Razin and Cohen (2020) came before Li et al. (2020), and not “later”.\n    - Ji and Telgarsky (2020) did not assume that the networks are univariate.\n- It seems that the notation $(v_i,v_j)$ is inconsistent (sometimes denotes connection from j to i and sometimes from i to j). There is also a typo in the definition of $v_i$. \n- Proposition 2: $f_W(x_j)$ should be $f_W(x_i)$ ?\n- First paragraph: “(iii)”\n- Page 8: “the the”", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject