SGD vs GD: Rank Deficiency in Linear Networks
Authors: Aditya Varre
Margarita Sagitova
Nicolas Flammarion
Venue: NeurIPS 2024 poster (2024)
Keywords: SGD dynamics
label noise
implicit bias
low rank
Primary area: optimization_for_deep_networks

Abstract: In this article, we study the behaviour of continuous-time gradient methods on a two-layer linear network with square loss. A dichotomy between SGD and GD is revealed: GD preserves the rank at initialization while (label noise) SGD diminishes the rank regardless of the initialization. We demonstrate this rank deficiency by studying the time evolution of the *determinant* of a matrix of parameters. To further understand this phenomenon, we derive the stochastic differential equation (SDE) governing the eigenvalues of the parameter matrix. This SDE unveils a *replusive force* between the eigenvalues: a key regularization mechanism which induces rank deficiency. Our results are well supported by experiments illustrating the phenomenon beyond linear networks and regression tasks.

SGD vs GD: Rank Deficiency in Linear Networks
Aditya Varre
Margarita Sagitova
EPFL
EPFL
aditya.
Nicolas Flammarion
EPFL
nicolas nicolas. fla.laas..ammm..oepep...cc
Abstract
In this article, we study the behaviour continuous-time gradient methods on a two-layer linear network with square loss. A dichotomy between SGD and GD is revealed: GD preserves the rank at initialization while (label noise) SGD diminishes the rank regardless of the initialization. We demonstrate this rank deficiency by studying the time evolution of the determinant of a matrix of parameters. To further derive the stochastic differential equation (SDE)
understand this phenomenon, governing the eigenvalues of the parameter matrix. This SDE unveils replusive force between the eigenvalues: key regularization mechanism which induces rank deficiency. Our results are well supported by experiments illustrating the phenomenon beyond linear networks and regression tasks.
1 Introduction
Deep neural networks have significantly advanced machine learning in recent decades. A key attribute of these models is their ability, despite being heavily overparameterizeed to learn effective representa- tions which generalizes well across different tasks. This capability has sparked substantial interest in understanding how neural networks learn internal representations for specific tasks [Bengio et al., 2013]. Gaining deeper insights into these mechanisms is crucial for enhancing model interpretability and refining training and application methodologies in real-world scenarios.
The success in learning these representations is often attributed to the gradient methods used in training. These methods navigate complex non-convex landscapes, finding solutions that not only minimize the training objective but also yield effective representations. They achieve this generaliza- tion while avoiding the spurious features that could potentially arise from the models' large number of parameters. Empirical studies have shown that the stochastic noise in gradient algorithms en- hances generalization [eskarr al., 2017] by favoring solutions with simpler structures that mitigate spurious features [A (Andriushchenko et al., 2022]. This paper address the overarching question:
How does stochasticity facilitate the discovery of solutions with simplified structures?
We explore this question using a simplified model: a single hidden-layer linear network. Despite lacking non-linearity, such networks capture some intricate phenomena of real-world deep networks and have been extensively studied to understand convergence [Arora et al., 2019a, Min et al., 2021] I] learning dynamics [Saxe al., 2014], and the implicit bias of optimization algorithms [Gunasekar et al., 2017, Soudry et al., 2018]. Our work builds on this foundation by comparing stochastic algorithms with their deterministic counterparts, focusing on how these differences influence the learning of simpler structures.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Specifically, we analyze vector regression on two-layer linear networks trained with both gradient flow and stochastic gradient flow methods. Our contributions include:
In Section 4, we track the evolution of the determinant of the parameter matrix under gradient flow and stochastic gradient flow. We show that stochastic gradient flow drives the determinant towards zero, effectively removing irrelevant direction(s).
In Section 5, we derive a stochastic differential equation that describes the behavior of the eigenvalues of the parameter matrix. This analysis reveals a repulsive force between eigenvalues that pushes them apart and geometric Brownian motion that pulls them toward
zero.
In Section 6, we discuss the generalizability of our approach beyond square loss and various noise models, including discrete step sizes. Finally, we present experimental results in Section that support our theoretical findings.
2
Related Work
Our work lies at the convergence of distinct research topics:
Effect of SGD on generalization. The relationship between the stochasticity of SGD and its generalization capabilities has been extensively examined [Mandt et al., 2016, Jastrzebski et al., 2018, He et al., 2019, Hoffer et al., 2017, Kleinberg et al., 2018]. Notably, SGD tends yield models with superior generalization compared to gradient descent [Keskar et al., 2017, Jastrzebski et al., 2018, He et al., 2019]. Various explorations into this phenomenon have been conducted through various approaches: hypothesizing that SGD favors flatter minima linked to better generalization, as opposed to sharp minima associated with poor generalization [Hochreiter and Schmidhuber, 1997, Keskar et al., 2017, Andriushchenko et al., 2023], using a random walk on a random landscape model to understand the impact of stochasticity [Hoffer et al., 2017], proposing that the inherent noise in SGD smooths the loss landscape [Kleinberg et al., 2018], and exploring the implications of dynamical stability [Wu et al., 2018].
Stochastic dy dynamics and Label Noise. Recent literature has explored label noise-driven Gradient Descent as effective method to probe the beneficial impact of stochasticity on generalization, with two distinct perspectives emerging. Firstly, an asymptotic view on general model parametrization is considered, where Blanc et al. [2020]. Damian et al. [2021] suggest that stochastic dynamics preferentially optimize a hidden objective linked to the curvature of the loss. In a related vein, Li et al. [2021] demonstrates appropriate limiting dynamics
the manifold of interpolators through time rescaling. Secondly, specifically for diagonal linear networks, HaoChen et al. 2. Fillaud-Vivien al. [2022] observe a similar collapsing effect due to label noise but with finer characterization of the limiting process. Finally, in the absence of label noise, Pesme et al. [2021]. Even et al. [2023] have characterized the outcomes of stochastic GF and GD for diagonal linear networks as the solutions to an implicit regularization problem that results in sparser solutions than without stochasticity. Recently, Ghosh et al. [2023] further exhibit a similar sparser features effect for single-neuron autoencoder. Chen et al. [2023] provides a condition under which an invariant set is attractive for SGD characterizing the local behavior around these sets. The paper also studies linear networks in a teacher-student setup, however due to structured label-noise [Chen et al., 2023, A2 in p.30], the analysis falls short of capturing the repulsive force in the singular values.
Linear Networks. The study of two-layer linear networks has been explored extensively, particularly when optimized using gradient flow on the square loss, across various settings including zero-balance initialization and whitened data Fukumizu [1998], Saxe et al. [2014, 2019]. Braun et al. [2022]. Early work by Saxe et al. [2014, 2019] elucidates the temporal changes in the singular values of the predictor, assuming decoupled dynamics and a specific data detendee weight initialization. This condition broadened by the analyses of Fukumizu [1998] and Braun et al. [2022], Tarmoun et al. [2021], who apply solutions from matrix Riccati equation to characterize the weights dynamics under full-rank network initialization. Furthermore, Gidel et al. [2019] extends the existing framework by relaxing the whitened data assumption, conducting perturbation analysis. and discussing the temporal evolution of the weight matrices' singular values. Additionally, Varre et al. [2024] eliminates the need for vero-balanced and full-rank initializations. Their study provides detailed formulas for weight evolution as a function of the initial scale, also studies a simple version of a stochastic flow without the drift. Wang and Jacot [2023] studied the implicit bias of SGD with lg fg-rgulaarizatoo.
2

---

Matrix valued stochastic process and their eigenvalues. Stochastic process on the space of symmetric (or Hermitian) matrices and the evolution of their eigenvalues are well studied since Dyson [1962]. These techniques were further developed by Bru [1989, 1991] to study perturbations of principal component analysis and the eigenvalues of Wishart processes. Norris et al. [1986], Graczyk and Malecki [2013] applied SDE-based techniques to study the eigenvalues and eigenvectors of Brownian motion on ellipsoids.
Linear networks and continuous-time gradient method
Notation We use (-,-) denote the inner product, i.e., (u, u) u for vectors, and (A, B) Tr (AB") ) for matrices. la denotes the identity matrix of dimension d and Opx denote the matrix with all zero entries of dimension p x k.
Vector regression. We study the vector regression problems with inputs 21.....2. in (R")" and outputs yı,-... Yn in (R* We consider the minimization of the square loss over a class of parametric models = {fo(-) R2
+ R& } specified in the next paragraph. The train loss therefore can be written as & (0) 2n Σ 1y: - fl
Parameterization with linear network. We focus two-layer linear neural networks of width I E N The model is described by the parameterization 0 = (W1, W2). where W E [gxx and W R and the function fz(x) W wi z. This model is linear with respect the input æ. In terms of expressivity, is comparable to the linear class of predictors, represented fπ((x) 3 x. where 3 equals Wi W2. Throughout our analysis, we denote the equivalent linear predictor of the network B. A key aspect of this parametrization homogeneous of degree 2 with respect to 0: specifically, for any À E I. fxe X fe. This property mirrors that of two-layer ReLU networks and significantly influences the loss landscape navigated by the parameters 9. It is important to note that this parameterization introduces some redundancy, single linear predictor B can have multiple representations W1. We such that W, W₂ = f. Some representations have a rich structure whereas other resemble random features. For example, consider the case scalar regression (A: = 1), for a vector ,3 there exists rich parameterizations where all the neurons, i.e., columns of W₁ align with ,3 and also some lazy structures where W, resembles random matrix [Chizat et al., 2019, Varre al., 2023].
that the prediction function fe is positive
Train loss. By defining X = [II...., In. and Y = [11. Un). the loss function is given by:
C(W W₂)
XXW, W. -1
(3.1)
2n
For simplicity, we adjust for the normalization factor n by rescaling the data to (X, Y) < (X/va, (X/vn,//vn) V/v),, thereby implicitly considering it in the loss function without directly mentioning n in the formula. Note that the loss non-convex in W1, W2.
Gradient flow. The dynamics induced in parameter space by running GF on Equation (3.1) is given by
dW, = CW1, dz XT (V XW, W. W, dt, dW2 = - VW, W di WT (Y X XW, W2 dr.
(3.2)
(3.3)
Introducing the block matrix, O = [ W2] (p+ and denoting the residual matrix by R = X TTYY (Y XW W2), the evolution of O can be written
0 Opxp
R 0kck
d [dw, T [d2 2 W.R di W Rdi] = W
W
dt.
R
The gradient flow can therefore be compactly written as
Opxp R
R Ok
de OJdr, where
(3.4)
The gradient flow (GF), when expressed in this form, reveals an inherent multiplicative structure with respect to O the gradient of the loss. As we see in subsequent sections, this representation of the gradient flow with block matrices proves to be very convenient.

---

Label noise gradient descent. Label noise gradient descent (LNGD) is theoretically studied alternative SGD that mirrors its practical behavior by sharing the geometric properties of the noise Blanc et al. [2020], Damian et al. [2021]. Let E, E Raxk where each entry of e, is an independent Gaussian random variable. At iteration i, the labels are perturbed with this Gaussian noise at an intensity 5, i.e., y =Y= + Vōε,, The LNGD algorithm updates the iterates with a step size 17 in the direction of the gradient computed after the labels have been perturbed, as follows:
W = W V/, & (V. Wi, W2); W = W w/ ( (Y,X, WI, W:),,
where, by abuse of notation, L XY W1, W2) 1/2 XWX We Y11.. be restructured into a block matrix:
The iterates can then
0 Opxp LE X
X Ok
θ /+ = = - - -
where & =
(3.5)
and Jr is defined as in Equation (3.4).
Stochastic gradient flow (SGF). We aim to model the aforementioned LNGD in continuous time using an appropriate SDE. Stochastic continuous-timg counterparts of discrete stochastic gradient algorithms are favored for their enhanced amenability to theoretical analysis. We propose the following stochastic differential equation (SDE) to model LNGD in continuous time:
Opxp _dB, X
XT
dp = - Jdt + v1jōdg] where dg =
(3.6)
O
where B, denotes matrix Brownian motion in T LNGD defined in Equation (3.5), can be interpreted as the the Euler-Mary Maryaaa discretization of the above SGF with a stepsize Although the inclusion of step size in the continuous-time modeling of an SDE may seem counter-intuitive, it is necessary component [Li et al., 2019b]. As all the terms of the SDE in Equation (3.6) are polynomial in θ, both the drift and diffusion terms are locally Lipschitz continuous. Hence, the solution of the SDE is uniquely defined up to the explosion time Too [see, e.g., Khasminskii, 2012]. Furthermore, the explosion time can be proven be infinite (Toe oo almost surely), by using that the GF does not diverge and applying the techniques outlined by Pillaud- Vivien et al. [2022, Proposition 10].
The dynamics of gradient methods on homogeneous models are significantly influ- enced by initialization, which determines the regime they operate in -i--sseccfillll......mmmmm the lazy regime for large initializations and the rich regime for small ones [Chizat et al., 2019, Woodworth et al., 2020]. Thus, the scale of initialization has garnered significant interest, particularly its impact on the training of linear and non-linear networks with GD [Woodworth al., 2020, Boursier et al., 2022]. It is observed that stochastic methods eliminate the dependence on initialization [Pesme et al., 2021].
Initialization.
Conserved quantities and balanceness. Gradient flows follow specific conservation laws along their trajectory [Marcotte et al., 2023], maintaining characteristics of the initial conditions. For linear networks, this conservation manifests as the balanceness property [Du et al., 2018], described by:
W W, W w. (0)W1 (2) WT (0).
As result, Saxe al. [2014], Arora al. [2018, 2019b] have adopted balanced initialization, where A (0) = 0, to ensure that weight matrices remain low rank throughout the trajectory. However, unbalanced initialization do not preserve these simple low-rank structures, as aspects of the initial conditions persist.
In contrast, stochastic methods do not adhere to these conservation laws [Ziyin et al., 2023] and the evolution of the imbalance A for SGF is
dA dW, W1 WwW,) = (XX W.W
k W X XWt
While there is diffusion term in the derivative, the matrices remain stochastic and no definitive conclusions can be drawn from this. However, in the case where & = p and X X = Ip. it can be shown that W W, - W2W, + 0, indicating that the stochastic noise eliminates initial imbalance.
Conclusion. Understanding how stochastic methods mitigate dependency on initialization requires exploring beyond the evolution of the imbalance A. To this end, we identify and discuss other conserved quantities, such the determinant of the block matrix θ θ in the following sections.

---

Separation between Gradient Flow through determinant
Here, we present our first separation result between GF and SGF. While the determinant of the parameters is preserved in GF, it is driven to zero by the stochasticity of SGF, leading to simplistic low-rank structure.
4.1 Determinant evolution of the gradient flow
The theorem below demonstrates that the determinant of the parameters is preserved in gradient flow. Theorem 4.1. For the gradient flow defined in Equation (3.4), the following property holds,
dddt @ ))) =
Hence, det (O()) det (0) Oo). where O, (0) is the initialisation at time t 0.
The proof presented the App. B.I, is based on straightforward computations of the derivative of the determinant and the fact that the matrix J has trace. We note that the simplicity of the proof arises from the strategically chosen block structure of θ. This result would have been less straightforward with different parametrizations, which likely explains why such simple finding appears to be novel. The theorem implies that the determinant of M along the trajectory remains equal the determinant initialization. If O On is full-rank initially, meaning the determinant is non-zero, the theorem ensures that the determinant of M remains non-zero. Consequently, the rank of @ does not diminish along the trajectory. When / > p p+ k: i.e., the hidden layer has large width and W W2 are initialized randomly from a Gaussian distribution, O Og has full rank almost surely. The theorem also reveals some implications regarding the impact of initialization scale. Note that Aman (A) I det A, indicating that when the scale of initialization is very small, at least one singular value of O is small.
4.2 Determinant evolution of the stochastic gradient flow
In contrast, the theorem presented below demonstrates that the determinant of the parameters verges to zero in stochastic gradient flow.
Theorem 4.2. For the SDE, defined in the Equation (3r6,, S Too, the following property holds for the evolution of determinant
d(det (TT)) -2nōktr (X X)det (OT (TTO)
Hence, det (+(I) det (O) Oo) exp -2yōktr (xx)t), where On is the initialization.
Although the evolution of the parameters in SGF is random, the evolution of the determinant is deterministic. The theorem highlights a striking phenomenon: the noise in SGF diminishes the determinant along the trajectory, leading to simplification the network over time. The larger the noise and the stepsize, the faster the determinant vanishes. The vamishing of the determinant suggests that the rank the parameters decreases by at least one, effectively eliminating some components. holds for any initialization of O and indicates how the SGF overrides some aspects of initialization. The proof uses the fact that stochastic Brownian term in the SDE, through Itô's calculus, introduces negative drift, ultimately driving the determinant to zero (refer to B.3 for the proof).
Limitations. Given the large width of the hidden layer, the determinant converging to zero does fully reveal the complexity of the situation. It merely indicates that at least one singular value is approaching zero. Furthermore, the theorem provides limited insights when the determinant already 0 at initialization, det O = 0 which happens whenever <p+ k. Next, we explore the mechanisms behind this low-rank phenomenon, suggesting that the repulsive forees induced by stochasticity drive the spurious singular values to zero as seen in the right plot of Figure 1.
5 Mechanism behind the low-rank phenomenon
In this section, we investigate the evolution of singular values under stochastic training to gain deeper insights into the low-rank phenomenon. To simplify the discussion, throughout the section
5

---

we consider the case where k 1 and for notational convenience, we let W1 = W, W2 = a Additionally, we assume that 1 I p, however the results can be extended any l.
Warm-up: Comparison with diagonal networks. Let W = UEVT be the singular value decom- position (assuming 1 & p). The predictor ( can be expressed
Wa UEV a U a c], where V
This expression reveals Hadamard product between a and c, reminiscent of diagonal networks which are widely studied to understand the nonconvex dynamics of gradient algorithms [Woodworth al., 2020, Pesme et al., 2021, Pillaud- Vivien al., 2022]. In the context of diagonal networks, SGD known to provably induce sparsity predictions. Similarly, for linear networks, SGF may induce sparsity in terms of the singular value We next derive the SDE governing the evolution of the singular values E of the weight matrix to gain a clearer understanding of the low-rank phenomenon.
Scalar Regression. We assume that the data is isotropic, i.e., X = Ip- Under these conditions, the loss function for scalar regression can written as
L (W, a) = 2 llu Wall"
(5.1)
We train the above objective with SGF, formulated as follows,
dW (y Waja dt + vn dB,a da W (y
Wa)dt + Vnd W dB, (5.2)
where B, is the standard Brownian motion in RP, For analytical convenience, we rescale the time 1 + 8/18 and use the process dX 1/1s(y Wa)d/ + dB,. The SGF can then be rewritten as,
dw dXaa; da = Wa=
(5.3)
Our focus is understanding the evolution of the singular values of the matrix W. This aim is facilitated by considering the symmetric matrix M = W W, whose eigenvalues are the squares of the singular values of W. Taking the derivative of M, find
dM dW W W dw + dw dw adX W T dXa + paa di.
(5.4)
Note that drdy represents d[,, y] for any continuous semi-martingales v [see, e.g., Ikeda and Watanabe, 1981, chapter for reference).
Eigenvalues of a matrix-valuce stochastic process. We leverage tools from the study of eigenvalues of matrix-valued stochastic processes [Bru, 1989, Graczyk and Malecki, 2013] derive the evolution of the eigenvalues of M in the theorem that follows.
Theorem 5.1. Let 81 ... > 8t the order of the eigenvalues of the matrix M defined by Equation (5.4). Let the collision time for the eigenvalues be defined
= {inf (t) = (t) for siiij
(5.5)
For S T, the eigenvalues are semi-martingales given by the solution of the following SDE
s.c +
d(s.) po? di +
S di + 2 s. (dx).
(5.6)
/ s 2 dt + de; with u, being the 8th column of U and (so. E1-1) is the standard Brownian motion in R!. The evolution of and U are presented in the appendix B.5.
where V T and (ax), 1/76 (u,
This theorem can be interpreted as the stochastic counterpart to the evolution of eigenvalues previously described for linear networks by Arora et al. [2019c], Varre et al. [2023]. The derivation of the eigenvalues is inspired by the work of Bru [1989].
The evolution of the eigenvalues features a key term highlighted in Equation (5.6) consisting of the sum of skew-symmetrie elements t,, and thus 8; > 8jo- the term 5,,% t 1 S/ -jo positively influences the evolution of the larger eigenvalue ds,, and negatively affects the smaller eigenvalue ds Therefore, this force is repulsive,
For a pair of indices (o) with in < jo

---

driving the cigenvalues apart and increasing their gap. Another factor influencing the dynamics is the presence of Geometric Browmian motion, where the singular value o, multiplicatively influences the Brownian motion as Vs,c, (dx), similar to what is observed in diagonal linear networks (refer to the previous discussion for similarities). This effect tends to pull the singular values toward zero. Together with the fact that (s., c;) = (0, 0) represents a fixed point of the dynamics, these two forces collectively push redundant singular values toward zero.
To further understand the interplay of repulsive forces and geometric Brownian motion, we consider the evolution of the smaller singular value Sp for = p. Using the Ito chain rule, we analyze the evolution of logs,, sp. expressed as,
2 p dt Sp
Sp
+ + dt
2- c2
d(log
+ Sp
dx
Sp
Sp Sj
Sp
}p
Using that tp.. -... for all indices j. the repulsive force accumulates to -pp (sppp)))) and the Ito correction term from the logarithm contributes an additional -2(c (the GBM component) thus offsetting the positive drift of p(c)/s,), In the case of | * p, considering a polynomial dº with an appropriate a would demonstrate similar behaviour. This discussion outlines the forces at play, yet a complete characterization of the solution of the SDE Equation (5.6) remains missing. Morcover, we have not established that the eigenvalues avoid a.s. collision, i.c., the explosion time Teo = oo which is in itself a significant challenge [Bru, 1989, Graczyk and Malecki, 2014].
A simplitied two-vector problem. To enhance our understanding of the SDE governing the evolution of the eigenvalues detailed in Equation (5.6), we consider the large noise limit. In this scenario, the process described in Equation (5.3) simplifies to a purely noise-driven process without drift:
dW = dB,aa;
da = W dB,-
This SDE exhibits notable symmetry: allowing for analysis using matrix with sub-sampled columns. Let S be any subset of 1,...,,, with (w.) representing the columns of W. We define
Ws E R as the subsampled matrix obtained by selecting columns w, where i E S, and similarly, we define subsampled vector as by selecting the corresponding coordinates. The SDE restricted to the set S is structured as follows:
dWs 5 = dB,a5;
dag W dB,
To demonstrate that the columns of W align. we leverage the symmetry of the SDE by examining the restricted problem on every pair of rows S {i,j}, and proving alignment within this subset. This approach leads us to consider the two vector problem (1 = 2), where W = =[ [w2] and W1, W2 E R", a E R We describe the behavior of the eigenvalues for this two-vector problem in the theorem below.
Theorem 5.2. In the large noise limit, so > 8ı be the eigenvalues of W, the following properties hold, for t S T defined by T = {inf t: st()) = si (t)).
(a) So. $ are greater than zero almost surely.
(b) for a = (p- (3)) is a super-martingale while sT is a sub-martingale.
This model for 1 2 mirrors the dynamics of the Wishart process studied by Bru [1991], motivating the exploration of the evolution of an appropriately chosen exponent of So, 81. The first part of the theorem arises from the fact that 8| " a is a local continuous martingale that cannot explode to infinity in finite time. The second part highlights a clear separation between the eigenvalues: one is sub-martingale that consistently increases in expectation, while the other is a super- super-martingale that diminishes (note that the cigenvalues are raised to a negative power). This dynamic, coupled with the symmetry argument, suggests that for every pair of columns, there a component that strengthens the alignment through its increases in expectation. Refer to App. B.6 for the proof.
Conclusion. In this section, we derive the SDE of eigenvalues for the matrix of parameters evolving under SGF. This derivation provides deeper insights into the mechanisms contributing to low-rank behavior. Specifically, repulsive forces drive the eigenvalues apart, while the geometric Brownian motion pulls them towards zero. These forces, unique to training with SGF, highlight the regularization effects of stochastic methods compared to gradient flow. However, fully characterizing the solution of this SDE remains a challenging open problem we let as future work.
7

---

6 Generalization to other settings
In this section, generalize our results beyond the square loss and the label noise gradient flow. We consider the general framework of a loss function over the weight product Wi W defined as
L (WI, I, W2) - 2(W, W2) B(a,))> [&(W, w2;,,))]
In this framework, the loss function e combines the prediction loss directly with the parametrized model fe. This approach applies, for example, to classification problems using linear networks where l' might represent any classification loss and fo = W, W2. It also directly extends to more complex architectures where = a [W1 W2) for activation function o, including settings like a self-attention layer with frozen value vectors. We denote the product by 3 = Wi W2 noting solely controls the loss. We investigate the evolution of the weight matrix determinant for general loss across various algorithms, from gradient flow to gradient descent, and demonstrate that a similar separation occurs due stochasticity.
Warm-up: Gradient flow. The gradient flow on the loss L can be written as the following.
-V
Opxp
dO OJdt,
where -V((3)
(6.1)
Okxk
Following similar proof as in Theorem 4.1, we obtain that d(det (@T@), O. For separable classification problem, the gradient flow converges to infinity [Soudry et al., 2018, Ji and Telgarsky, 2019], hence, after appropriate rescaling, the layers are aligned, as shown by Ji and Telgarsky [2019]. Next, we contrast this result with the outcomes observed in stochastic and discrete algorithms.
Continuous modelling SGD. We consider the SGD algorithm with a batch size B. We denote the mini-batch version of the loss functions L and E as LB and LB. respectively. The SGD update with stepsize 77 can be represented with the following block structure.
- -(Vī(B) -(VC(3)-VCs(1) VL2(3))
Opxp
+ ++1 = 0 n -
1/0's' -
where ç¹
(vī(8) - (V((3)-V(s(3))
0
We denote the SGD noise as It
((13)-((x(B)) and the noise covariance as Σ, gg [g*)T] where the expectation is over all the minibatches. Following Li et al. [2019a], the SGD update can be modelled with the following SDE,
dO -Jdd /Tddg where de [
Σ 1/2 dB,
0pxp (X)
(6.2)
OBxR
The main difference with SGF is that, in overparameterized problems, the noise covariance is time- varying and decreases to zero upon convergence. Using Theorem B.3, the evolution of the determinant
of M θ T ④ is given by d(det (M)) -njdet (M)Ir (I(t)) dt and can be explicitly solved as
d(det (M)(1) = det (M(0))exp(-n) L Tr (d))))d)..
Hence, the decay in the determinant is governed by the integral J Tr (E(())df which is stochastic quantity. Tr (E(() represents the strength of the stochastic noise, which, in aver-parameterized regression, proportional to the loss, i.e., Tr (E(() x (() [Pesme al., 2021]. Therefore, the rate of decay in the determinant depends on L L ((O(t)) dt, with slower convergence leading to simpler model at convergence, as observed in the case of diagonal networks by Pesme et al. [2021]. The result above also holds for non- nep-seeae classification tasks where the noise of SGD drives the determinant to 0, a scenario not covered by the previous analysis of Ji and Telgarsky [2019].
Discrete gradient algorithms. We can extend the previous results to discrete (possibly stochastic) gradient algorithm. Both algorithms can be written as
+ θ (Ip+* + nJJ))
for stepsize 1 and J, the possibly stochastic block gradient matrix defined in Equation (6.1). l). In the context of discrete algorithms, the determinant controlled by the following lemma (refer B.4 for the proof).
8

---

10
Determinne
307
20
22-1
12-11
60
Figure Evolution of the model characteristics for gradient flow (6 0) and stochastic gradient flow (5 = 2). Left: Determinant of M. Right: Top-5 singular values of W
20
Figure 2: Evolution of the top-5 singular values of W for SGD with small and large stepsizes Left: Regression with MSE loss, linear network. Middle: Classification with logistic loss, linear network. Right: Regression with MSE loss, 2-layer ReLU network.
Lemma 6.1. When I = + k and 1ndd))|JJA I I 1, the following property holds for the determinant,
deet O S exp n² |_/|(3/ det O
If the factor " < 1 every iteration the determinant is reduced by the discrete step size. However, there is a tradeoff: the sum = Ei n?2 [ can be finite, indicating that does not compictely drive the determinant to zero. Increasing to increase S might lead to instability and divergence. Furthermore, since |Je||² and the simplicity of the parameters. This illustrates how step sizes that produce non-convergent training loss patterns, such as the catapult effect [Lewkowycz al., 2020] or the edge of stability mechanisms [Cohen et al., 2020], can simplify the network's 's parameters.
(Q.), there is additional tradeoff between convergence
Experimental evidence
We consider regression problem on synthetic data with n = 1000 samples of Gaussian data in R (p 5) with labels in R22 (k: 2) generated by some ground truth B Ráx2 the width of the network is = 10. We use Gaussian initialization of the network parameters with entries from (0 1). Experiments details can be found in the appendix C. In the left plot of Figure 1, we show the time evolution of the determinant of matrix M. As suggested by theorems 4.1 and 4.2, in the case without label noise, det (O + stays constant, while with the Label Noise of intensity d it goes to zero with time. In the right plot of Figure 1, we demonstrate the time evolution of the top-5 singular values of the matrix W1. Note that in the case of Gradient Flow all except the first singular values (To and σ1) stay at the same scale, while adding Label Noise forces smallest d l singular values (02, 03, and 044 to tend toward zero. Further experiments illustrate Figure evolution of singular values of parameter matrix W, when optimized with SGD, for classification tasks and with ReL.U network. These results also confirm that the beneficial effects of stochasticity hold in these contexts.

---

8 Conclusion
In this paper, we demonstrate a distinct separation between GF and SGF when trained on linear networks. This separation is obtained by tracking the evolution of the determinant of the parameter matrix. However, while the determinant is a sigmificant factor, it does not fully capture the implicit regularization effects. Notably, the determinant mirrors the imbalance u v² in diagonal networks represented by u @ v, whose dynamics play a crucial role in attuning the implicit regularization across various algorithms [Woodworth al., 2020, Pesme et al., 2021, Papazov et al., 2024]. Our analysis presents the initial step in deciphering implicit regularization for stochastic methods in linear networks, yet achieving complete characterization remains a promising direction for future research.
Acknowledgments and Disclosure of Funding
AV supported by Swiss data science fellowship. This work was supported by the Swiss National Science Foundation (grant number 212111).
References
M. Andriushchenko, A. Varre, L. Pillaud-Vivien, and Flammarion. Sgd with large step sizes learns sparse features. arXiv preprini arXiv:22/0.0533: 2022.
M. Andriushchenko, F. Croce, M. Müller, M. Hein, and N. Flammarion. A modern look at the relationship between sharpness and generalization. In International Conference on Machine Learning, pages 840-902. PMLR, 2023.
S. Arora, N. Cohen, and E. Hazan. On the optimization of deep networks: Implicit accelcration by overparameterization. In Proceedings of the 35th International Conference on Machine Learning, 2018.
Arora, N. Cohen, N. Golowich, and Hu. A convergence analysis of gradient descent for deep linear neural networks. In International Conference on Learning Representations, 2019a. URL bttpps///ort //ppnrevieeeeeeeeeeeee/ee wtwt/feuummiiiiiie wwrrm?iddSkkM@gaCC
Arora, N. Cohen, W. Hu, and Y. Luo. Implicit regularization in deep matrix factorization, Advances in Neural Information Processing Systems, 32, 201 9b.
S. Arora, N. Cohen, W. Hu, and Y. Luo. Implicit regularization in deep matrix factorization. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Bue, E. Fox, and R. Garnett, ed- itors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 20 URL https: https: h/tr:////c/ceeeeessseeee wewrreinnnnnnnnnnnnneee.....
1d1 4aa.0332111.600902000-2Pa neurips. cttpscccppppppeeeeeeeeeee wwwes//apeeeeeeeeee ftlles/paper2209//1111 . .ddf.
Y. Bengio, A. Courville, and P. Vincent. Representation learning: review and new perspectives. IEEE Trans. Pattern Anal. Mach. Intell., 2013.
G. Blane, N. Gupta, G. Valiant, and Valiant. Implicit regularization for deep neural networks driven by an ornstein-uhlenbeck like process. In Conference on Learning Theory, COLT 2020, Proceedings of Machine Learning Research. PMLR, 2020.
E. Boursier, I.. Pillaud-Vivien, and N. Flammarion. Gradient flow dynamics of shallow reL.U networks for square loss and orthogonal inputs. In A. H. Oh, A. Agarwal, D. Belgrave, and K. Cho, editors, Advances in Neural Information Processing Systems, 2022. URL https: /ttp:///e/e/.../.e//////m// net/ Darum?id=1744e -111741ccxxx11...
L. Braun, C. C. J. Dominé, J. E. Fitzgerald, and A. M. Saxe. Exact learning dynamics of deep linear networks with prior knowledge. In A. H. Oh, A. Agarwal, D. Belgrave, and K. Cho, editors, Advances in Neural Information Processing Systems, 2022. URL httpp:://ppenrriiiii net/ forum? idd1.xxvvng-Kic
M.-F. Bru. Diffusions of perturbed principal component analysis. Journal of Multivariate Analysis, 29(1):127-136, 1989. ISSN 0047-259X. doi: http::/wwwooogg////o.loo////2220 URL https:/ wttp:/wwwwww.e...etwtwoo/wwtwttw www.esccinceiieect.... com wttp////caao//ttttto///////////0
M.-F. Bru. Wishart processes. Journal of Theoretical Probability, 4:725-751, 1991.
10

---

F. Chen, D. Kunin, A. Yamamura, and S. Ganguli. Stochastic collapse:
How gradient noise attracts SGD dynamics towards simpler subnetworks. Thirty-seventh Conference on Neural Information Processing Systems, 2023. URL https://openreviiet httppeerwweeeee.eeeoouurrttttt/e www.:/eennn/neee httts/Eooruttdd-Pxxwweeeeedd
L. Chizat, E. Oyallon, and F. Bach. On Lazy Training in Differentiable Programming. Curran Associates Inc., Red Hook, NY, USA, 2019.
J. Cohen, S. Kaur, Y. Li. J. Z. Kolter, and A. Talwalkar. Gradient descent on neural networks typically occurs at the edge of stability. International Conference on Learning Representations, 2020.
A. Damian, T. Ma, and D. Lee. Label noise sgd provably prefers flat global minimizers. Advances in Neural Information Processing Systems, 34:27449-27488 2021.
S. S. Du, W. Hu, and D. Lee. Algorithmic regularization in learning deep homogeneous models: Layers are automatically balanced. In Advances in Neural Information Processing Systems, 2018.
F. J. Dyson. A Brownian-Motion Model for the Eigenvalues of Random Matrix. Journal of Mathematical Physics, 16):11991- 1962. ISSN 0022-2488. doi: 10.1063/1.1703822 URL https: / /ttp://oooooo/////////o/ 10. 1063/1.1703862.
M. Even, S. Pesme, S. Gunasekar, and N. Flammarion. (s) gd over diagonal linear networks: Implicit regularisation, large stepsizes and edge of stability, Advances in Neural Information Processing Systems, 2023.
K. Fukumizu. Effect of batch learning in multilayer neural networks. Gen, 1(04):1E-03, 1998.
N. Ghosh, S. Frei, W. Ha, and B. Yu. The effect of sgd batch size on autoencoder learning: Sparsity, sharpness, and feature learning. arXiv preprint arXiv:2308. 03215, 2023.
G. Gidel, Bach, and S. Lacoste-Julien. Implicit regularization of discrete gradient dynamies in linear neural networks. Advances in Neural Information Processing Systems, 32, 2019.
P. Graczyk and J. Matecki. Multidimensional hamada-watanahy theorem and its applications to particle systems. Journal of Mathematical Physics, 54(2), 2013.
P. Graczyk and J. Malecki. Strong solutions of non-colliding particle systems. 2014.
S. Gunasekar, B. E. Woodworth, S. Bhojanapalli, B. Neyshabur, and N. Srebro. Implicit regularization in matrix factorization. Advances in Neural Information Processing Systems, 30, 2017.
J. Z. HaoChen, C. Wei, J. D. Lee, and T. Ma. Shape matters: Understanding the implicit bias of the noise covariance. In M. Belkin and S. Kpotufe, editors, Conference on Learning Theory, COLT 2021, 15-19 August 2021, Boulder, Colorado, USA, 2021.
C. R. Harris, K. J. Millman, S. J. der Walt, R. Gommers, P. Virtanen, D. Cournapeau, E. Wieser, Taylor, Berg, N. J. Smith, R. Kern, M. Picus, Hoyer, M. H. van Kerkwijk, M. Brett, A. Haldane, J. F. del Río, M. Wiebe, P. Peterson, P. Gérard-Marchant
K. Sheppard, T. Reddy, W. Weekesser, H. Abbasi, C. Gohlke, and E. Oliphant. Array programming with NumPy. Nature, URL httop:://di..... org/10.
585(7825) Sept. 2020. doi: 00008//4156-000-22200 1038/s41586 020- -20-1-699---2-222922-2
F. He, T. Liu, and D. Tao. Control batch size and learning rate to generalize well: Theoretical and empirical evidence. In Advances in Neural Information Processing Systems, volume 32, 2019.
Hochreiter and J. Schmidhuber. Flat minima. Neural Comput., 9(1): jan 1997.
E. Hoffer, I. Hubara, and D. Soudry. Train longer, generalize better: Closing the generalization gap in large batch training of neural networks. In Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS' 17, page 1729-1739, 2017.
N. Ikeda and S. Watanabe. Stochastic differential equations and diffusion processes, volume 24 of North-Holland Mathematical Library. North-Hollane Publishing Co., Amsterdam, 1981. ISBN 0-444-86172-6.
S. Jastrzebski, Z. Kenton, D. Arpit, N. Ballas, A. Fischer, A. Storkey, and Y. Bengio. Three factors influencing minima in SGD. In International Conference on Learning Representations, 2018
Z. Ji and M. Telgarsky. Gradient descent aligns the layers of deep linear networks. In International Conference on Learning Representations, 2019. URI. Hgf1g30
net/ fdd

---

N. S. Keskar, D. Mudigere, J. Nocedal, M. Smelyanskiy, and P. T. P. Tang. On large-batch batch training for deep learning: Generalization gap and sharp minima. In International Conference on Learning Representations, 2017.
R. Khasminskii. Stochastic Stability of Differential Equations, volume 66 of Stochastic Modelling and Applied Probability. Springer, Heidelberg, second edition, 2012.
B. Kleinberg, Y. Li, and Y. Yuan. An alternative view: When does SGD escape local minima? In Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages (668-27009 PMLR, 10-15 Jul 2018.
A. Lewkowycz, Y. Bahri, E. Dyer, J. Sohl-Dickstein, and G. Gur-Ari. The large learning rate phase of deep learning: the catapult mechanism. arXiv preprint arXiv:2003.022/16 2020.
Q Li, C. Tai, and W. Stochastic modified equations and dynamics of stochastic gradient algorithms i: Mathematical foundations. Journal of Machine Learning Research, 20(40):1-47, 20199.
Q Li, C. Tai, and W. E. Stochastic modified equations and dynamics of stochastic gradient algorithms Mathematical foundations. Journal of Machine Learning Research, 20(40):1-47, 2019b. URL http:/ jmmrr. hatll//lllrlaa..aeeeeeeeeeeeeeee wwrg/appers/v200 https//vv/11771/// 576 html.
Z. Li, T. Wang, and S. Arora. What happens after sgd reaches zero loss?-a mathematical framework. In International Conference on Learning Representations, 2021.
S. Mandt, M. D. Hoffman, and D. M. Blei. A variational analysis of stochastic gradient algorithms. In Proceedings of the 33rd International Conference on International Conference on Machine Learning- Volume 48, ICML' 16, page 354-363, 2016.
S. Marcotte, R. Gribonval, and G. Peyré. Abide by the law and follow the flow: conservation laws for gradient flows. In Thirty-seventh Conference on Neural Information Processing Systems, 2023. -tw.ormmmdd-kueEEBBS.
URL https: http::::///peeeevieeeeee
E. Mayerhofer, O. Pfaffel, and R. Stelzer. On strong solutions for positive definite jump diffusions. Stochastic processes and their applications, (2(9))2072-2088) 2011.
H. Min, S. Tarmoun, R. Vidal, and Mallada. On the explicit role of initialization on the convergence and implicit bias of overparametrized linear networks. In Proceedings of the 38th International Conference on Machine Leurning, 2021.
J. R. Norris, of the American Mathematical Society, 294(2):757-765, 1986. ISSN 00029947. URL http: // /www. jjtorr arg/stable pattaalee20000 22002244.
G. Rogers, and D. Williams. Brownian motions of ellipsoids. Transactions
H. Papazov, S. Pesme, and N. Flammarion. Leveraging continuous time understand momentum when training diagonal linear networks. In International Conference on Artificial Intelligence and Statistics, pages 3556-3564. PMLR, 2024.
A. Paszke, S. Gross, F. Massa, A. Lever, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, I.. Antiga, A. Desmaison, A. Kopf, E. Yang, Z. DeVito, M. Raison, A. Tejani, S. Chilamkurthy, B. Steiner, I. Fang, J. Bai, and S. Chintala. Pytorch: An imperative style, peg--performance deep learning library. In Advances in Neural Information Processing Systems 32, pages 8024-8035. Curran Associates, Inc., 2019. URL http://papers. http::///paperr..eeipppsse. newrips. ptteurippsccpppper///. pdf.
library.
S. Pesme, L. Pillaud-Vivien, and N. Flammarion. Implicit bias of sgd for diagonal linear networks: a provable benefit of stochasticity. Advances in Neural Information Processing Systems, 34: 29218-29230, 2021.
L. Pillaud-Vivien, J. Reygner, and N. Flammarion. Label noise (stochastic) gradient descent implicitly solves the lasso for quadratic parametrisation. In Conference on Learning Theory, pages 2127-2152 PMLR, 2022.
A. M. Saxe, J. L. McClelland, and S. Ganguli. Exact solutions to the nonlinear dynamics of learning in deep línear neural networks. In 2nd International Conference on Learning Representations, ICLR 2014, 2014.
A. M. Saxe, J. L. McClelland, and S. Ganguli. A mathematical theory of semantic development in deep neural networks. Proceedings of the National Academy of Sciences, 153(23::11537-111444 2019.
12

---

D. Soudry, E. Hoffer, M. S. Nacson, S. Gunasekar, and N. Srebro. The implicit bias of gradient descent on separable data. Journal of Machine Learning Research, 19(70):1-57, 2018.
S. Tarmoun, G. Franca, B. D. Haeffele, and R. Vidal. Understanding the dynamics of gradient flow in overparameterized linear models. In M. Meila and T. Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 10153-10161. PMLR, 18-24 Jul 2021.
Townsend. Differenniating the singular value decomposition. Technical report, Technical Report 2016, https://j-towns.. github. lo/papers/svvdderivvtvve ...,
G. Van Rossum and F. L.. Drake. Python 3 Reference Manual. CreateSpace, Scotts Valley, CA, 2009. ISBN 1441412697.
A. V. Varre, M.-L.. Vladarean, L.. Pillaud-Vivis Vivien, and N. Flammarion. On the spectral bias of two-layer linear networks, In sevenhhe Conference on Neural Information Processing Systems, 2023. URL https: https://oppnreviees wwt./oommmmddfFFffarro Xkm33Z..
A. V. Varre, M.-L. Vladarean, L. HilluddViiveen and N. Flammarion. On the spectral bias of two-layer linear networks. Advances in Neural Information Processing Systems, 36, 2024.
Wang and A. Jacot. Implicit bias of sgd Iz-regularized linear dnns: One-way jumps from high to low rank, 2023.
B. Woodworth, S. Gunasekar, J. D. Lee, E. Moroshko, P. Savarese, Golan, D. Soudry, and N. Srebro. Kernel and rich regimes overparametrized models. In J. Abernethy and S. Agarwal, editors. Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pages 3635-3673, PMLR, 09-12 Jul 2020.
L. Wu, C. Ma, and W. E. How SGD) selects the global minima in peee-parameterized learning: A dynamical stability perspective. Advances in Neural Information Processing Systems, volume 31, 2018.
L. Ziyin, H. Li. and M. Ueda. Law of balance and stationary distribution of stochastic gradient descent. arXiv preprint arXiv:2308.00 06671, 2023.
13

---

A Notations
Notation Sa, S4 , St denote the set of symmetric, positive semi-definite and positive definite matrices Baxd We use @ to denote the Hadamard product.
B
Proofs
Theorem B.1. For the gradient flow defined in Equation (3.4), the following property holds,
d(det (TT)) 0.
Hence, det (O())((I)) det Oo), where O ( the initialisation time O.
First, we present proof of this theorem, based on straightforward computations of the derivative of determinant and the fact that the matrix has zero trace.
Proof. Let M = O. The dynamics of M are governed by the ODE,
dM = de e + + de θ OJdt + JO Odt = (MJ + JM)dt.
Using the gradient of the determinant given in Proposition B.2, the determinant of M evolves as follows,
d(det (M)) deet (M), dM) det (M) (M-1 MJ + JM) dt. = det (M) (M-,, MJ) + (M-), JM) = 2det (M) (Ip+k, 2det (M)Tr (J). Given that Tr (J) = 0, it follows that d(det (M)) =
Proposition B.2. For any matrix M St² the first two derivatives of the determinant of M, denoted by det (M) are the following
(i) Vdet (M) = det (M)M-
(ii) For 1 S a, b, k,, 1. S d, the second order partial derivative is given by
ddet (M) det (M) (M) (M )1 (M-')on MM (M- )tal
(B.1)
OM
Theorem B.3. For a stochastic process given by the SDE,
de θ Jdtt + dg]
(B.2)
with TrJ Tr 0, the determinant of the M θ T evolves
d(det (M)) det (M)Tr [d5dE].
(B.3)
Proof. First, we compute the evolution of M θ + using the Ito's product rule,
dM d d + d O θ de d de
The last term is interpreted derivative of the finite variation and it should be computed using dt. (dB.),, = and (dB.),, (dB,) )) dd Using Eq. (3.6),
dM = Jddt + de θ e e J[ + dg) + dg@ Odg,
JMd MJdi dgMdg d Mdg.
Using the Ito chain rule, compute the evolution of determinant following,
g (M) dMajdMgi, i
d(det (M)) = (Vdet (M),MM) + Σ
a,b,k,
14

---

The first term is
(Vdet (M),MM = det (M) (M-) .JMde + MJdd + dgMdg + d + Mdg).
(M) (1p+kk J) dt + 2det (M) (1ptks dg) + det (M) (M-) dEME)
Using the property that Tr (J) the second term
= Tr (dg) = 0. We get that (Vdet (M), dM)
For
det (M) dM
Σ
det M (
(M- (M )aa d.M.dM..
OM
2
o,b,k,l
a.b.k.
(M)(M)
aaa
(Ma aMaddMa
2
a.b.k,
Σ
(aa )ial dMaddMat
a.b.k,l
Rearranging the terms in the summation, we get,
Σ (M-*) (M- )(x]
dMaddMa = E Joaddda "MM")udMMs
k.b.k.l
a.b,k,
1(M-))n dMr Σ(M -M- DuddM
b,1
(M
(M- 11 Σ (M- bb E (M dM)
b,1
Tr (M (M Ir (M-+dM).
Similarly for the other term, get,
Σ
[M Do (Ma)
dM =
Σ
[M (od )ia
A.
a.d,Ad
Σ
Σ (M- dMdi [(M- DaddMa
Σ
Σ M (M) by (M-dM)
= Σ [M [M'dMMM- 'dMM-'dM
Tr (M-'dM) (M (M-)
Note that the diffusion part M- de M Md Using this
Tr (M-+d))T Ir (M- Tr [dg + M -- Tr [de M- 0,
as Tr df = 0. For the other term,
Tr [M( dM)] = Tr [(ds - M M- (dS dgM)]
2Tr [dede] + 21r [MMMd.
Putting everything together, we get,
1
Σ
ddet (M) det M (Tr [dEdE] + Tr [M dddMe))
2
MM
a.b.k!l
which gives us
d(det (M)) -de (M) Tr [dEdg).
15

---

Lemma B.4. When = k and n/ n2 I 1, the following property holds for the determinant.
deet O S exp (
o | det O₂
Proof. Note that because of the block structure of the matrix J. its nonzero eigenvalues come in +-pairs: _01...., no moreover, since is symmetric, singular values of J, are the absolute 0m Then, the determinant of 0+41 can be written as the following.
values of eigenvalues, i.e. 01....,0m:
det 0+11 = det O,dct (Ip+* + +.J,)) = det o II (1 r²a;))
k=1
Using that - x² S ee == for all x, we can estimate
II - ( S exp
-1p
Σ 1=1
0,
= exp
[Je((²]
2
m71
We obtain the required inequality by observing that II -2a
II (1 r)ao)
since each
term 1 n²o when v/" [ 1.
Theorem B.S. Let 81 > ...8) 81 the order of the eigenvalues of the matrix M defined by Equa- tion (5.4). Let the collision time for the eigenvalues be defined
T T= (inf (t) (tr sitjsh.
(B.4)
Fort t S T, the eigenvalues are semi-martingales given by the solution of the following SDE
s,c s dt 2 2 (dx),
d(s;) pea dt
(B.5)
s, S Sj
where (ax),
s dt + de; with u, being the ith column of U and ......,,E-1.. is the standard Brownian motion in R. The evolution of c, and U are presented the appendix.
1/16 (u.
UEVT be the singularvalue decomposition (see D involved with r 1 and / and it will be the rank). Our focus is understanding the evolution of the singular values and singular vectors of the matrix W. To derive the evolution of Σ, V we can consider the eigenvalues and eigenvectors of the PSD matrix process M. Note that M VΣ
Proof. The proof follows the approach of Bru [1989]. Let W
Σ²
Evolution of D and V Taking the derivative of M, we find
dM dw W W dw + dwi dW
adX W W
dXa
+ paa dt.
(B.6)
We invoke the theorem D.2 we derived to give the eigenvalues of any matrix valued stochastic process. Note that VVT T₁, so some terms of the computation are not required.
dD 1 Ñ dt + dM dt +IG (dM @ (odd))
and the evolution of the eigenvectors,
dV = V (Q) dt + + (Nat + +M)
where you define,
1@
8
dM)
3 dM)
s (s dM) dM oIl S (dM (M)M
16

---

where the matrix S is given by
Sij- 0
if j.
(S)- 8:) O.W.
Ñ V (paa) TV pec
dM V aaxX W + W dXa XXa]v. V,
cdX UE EU dXc".
Note that E diag (o......, 01-1)) where on 01 .... 11 Let D E² and denote the
entires of D as following, D diag (80) (Su)...., sp......pp1lp 1p-1)) Note that
u dx U
110 (y - Wa)dt + dB:).
1
U Σcl di U dB, no
Using Levy's s characterization U dB, is Brownian motion in Ry, lets call that dB,, The diffusion part of dM (say dF)
dF EV c T + edB; VV,
o @ dB c (o @B.)
cm.c
cdm;
where dm, def (o O dB.). We are required to compute dF @ dF) to compute the evolution of eigenvalues. Using the lemma D.4, get
dF(S e dF) cs Sdiag (c) Ddiag (Sdiag (c) c) + Ddiag (c) Sdiag (c) dt,
Io (S @ dF)] I@ ccs Sdiag (c) df Ddiag (Sdiag (c) c) df
The element wise computation of this term gives the required result for evolution of eigenvalues. Evolution of c. Note that e V a. Computing the derivative using the Ito's product rule, we get, dv a = V da + dV a + dV da,
= V da dV VV a a dV VVT da,
dV T V = [Qq dt - o dx
V da = v T W dB. + no
U Ec| dl EdB. dm; + n
[UT y- - Ee| dl,
dV VV da = - (S @ dF dm,
dv VV VV
da [QQ dt S Ndd + dM
Using the lemma D.6, D.5, D.4 and computing the element wise summation, we get the following evolution for de
dc; Σ
Syy (s,c +s,c7)dt c,
(
Σ Sk
j=l
j=1
tighti
- (p- - 2)c, Σ
Σ
Siss,tt
/=1
1=1
( dx)
- -
(U ax),
Evolution compute the evolution of U, we invoke the theorem D.2 on the evolution of WW UDUT We ignore it here it does not have much consequence our results. D
17

---

Theorem B.6. In the large noise limit, when = 2, the following properties hold, for t S T,
(a) So. S1 are greater than zero almost surely.
(b) for = (p- (p 32/2, 80" ax is a super-martingale while si is sub-martingale.
Proof. First, note that in the large noise limit with 1 = 2, the evolution of the eigenvalues is expressed
as
Soef + s1
d(su) pejdt
dt + 2 2/ soc (BB:), 50 S1
(B.7)
sec + Si ci
d(s1) = pefdt
dt + 2 saes (dB.).
(B.8)
50 S
Using the Ito chain rule, for the evolution of so
we can write
d(s5
0(55%)
(pefett +
8oeी + -sio
dt spc (dB.).) + 1 15
(2 (2/soof)) dt
Use
So S S1
8250
p + s1c dt 2( + 1) 22 focs +2/ (dB.).)
=-as
(pedet +
5o 51
-as
cgjdt +
spes + s1c
2
dt + 2 soc (aB.),
So S
analogously
d(s = -ass ---1 (fjdt
spet + si că dt + 2 $ ( (IB.).)
8o
and finally for so "si"
d( d(550 870) = "(s5")s( ss + so d(T + d d((T
Soce + ci dt 2 coco ( (iB:),)
-as a-1 8 ceidt +
80
oocs + c dt + 2 s (BB.).
as ss
cidl
80 81
Now, we can show that the drift term in the SDE that describes the dynamics of sn 8T is zero, which gives us the first part of the result by Mckean's argument [Mayerhofer et al., 2011].
+
s1cs
soct + s
080
0100
+
8)
+ s
+ So
So
S1
coi +
+ s/c siet + 5osi
-008
0-
8s
a-1
$ + c
S
(s1 Su) (sucy + $1 $1c)
-08
8
a--
ci + c
=0. 0.
80 81
The second part is obtained by noticing that
c
+
8o (cf + ci)
2 0,
8o 81
8n 81
Spc C
81 (c/ + c1)
< 0,
Sp 81
So 81
and hence the drift term of ds55a) is not positive, while the drift term of d(sTaa is not negative.
18

---

C Experiment details
In all the graphs we plot the values averaged on 20 runs with different random seeds as well as the 95% confidence interval (lightly colored). To numerically emulate GF (Figure 1), we set stepsize of le 6 in numerical simulation.
In the further experiments, we study the behaviour of the linear network for regression with the same synthetic data and same network initialization in previous experiment. As seen in the left plot of the Figure 2, when the stepsize is large (7) = 0.1). singular values exhibit behavior similar to the case of LNGF, while with the small stepsize (1) 0.005) the evolution of singular values closer to GF case. Next, we examine the effect of SGD in the case of classification task with logistic loss, as illustrated the middle plot of the Figure 2. We consider synthetic data with n 1000 samples of Gaussian data in R (d = 5) constituting two clusters corresponding to two classes (k = 1). Note that larger stepsize (1- 0.5) in this case also forces the smallest singular value tend zero, however the effect is not so dramatic for the rest of singular values. Additionally, we study the 2-layer ReLu network optimized with SGD on the same regression task before. seen in the right plot of the Figure 2, the decrease of the last singular value da is much slower than in the case of the linear network, however, the larger stepsize still facilitates divergence of largest (op and σ1) and p smallest (d2, 03 and 04) singular values.
All experiments are implemented with Python [Van Rossum and Drake, 2009] under PSF license, NumPy [Harris et al., 2020] under BSD license, and PyTorch [Paszke et al., 2019] under BSD-3- Clause license.
The experiments were run on Intel i5-8250U, 8-GB RAM, with OS Ubuntu 20.04.6.
D Supplementary material
D.1 Notations and preliminary definitions
Definition D.1 (Eigen decomposition and Singular Value decomposition). We discuss the eigen value decomposition for a symmetric square matrix, and the singular value decompostion for any matrix is defined as the following
(a) Eigen decomposition. For any rank matrix R E Sp. VDVT the eigen decomposition, where V E Rexr D Rr'x, D is diagonal matrix and V V = I however, VVT is not necessarily an identity matrix unless r =
(b) Singular Value Decomposition. For any rank r matrix W E RPxI W UEVT, where U Rexr V E Riix Σ E Rrxr, r E is diagonal matrix and U UU- V however the UUT and VVT are not necessarily identity unless = p or respectively.
D.2 Eigenvalues of matrix valued stochastic process
Theorem D.2. For matrix-valued stochastic process on Sp
dR Ndt + dM
where dM is a local martingale process. Let VDVT the eigenvalue decomposition of the process, the evolution of eigenvalues satisfy the SDE for time less than the collision time,
dD - -I IO I dM (S dM) + +D-1 (V dR (I-VVV dRV).
where is defined as per Eq. D.I and dM = VTaMV, = VTNV. The evolution of the eigenvectors,
dV = V di + - - dt dR VD VD-1).
19

---

where you define,
10 S o dM)
S (So dM
1@ D dR (I VV dRVD-1
Q1
2
so [ dM) dM + |] +S o (M (S ( (oddM)
+S (V dR (I - VV dRVD
Q = [dRVD 'I [[S o dM] D dM D-1
Evolution of eigenvalues for general matrix SDE
Proof. Using the eigen decomposition, we have R = VDVT,
D = RVR
dD V dRV + VdR
RdV +VVRY + V dRdV + dV dRV + dv RdV,
=VTdRV + DV aV +VV VD + V dRdV + dv dRV + (dV V) (VTav).
The approach follow is use the jacobian of the evolution of V (see [Townsend, 2016] ) and solve the constrains equations to obtain the Ito correction term as done in Bru [1989]. Let ($1, S2...., s,) denote the diagonal entries of D. Furthermore, we define the matrix S, which plays notable role in Jacobian w.r.t V, as the following.
if J. S (s} (s)=-s))-
(D.1)
s:)-1 o.w.
For the sake of brevity, we denote the evolution
dF def
V dRV = V NV dt V dMV,
def N dl dM
The evolution of the eigenvectors,
dV = VdΩa + VV-VVTnm dEv
Using the Jacobian of the eigen vectors, we write,
dΩvy QΙ dt + S dF,
dEv = Q dt + dR VD-1
Note that V = I,, using this we have,
0 0= d(ddvvv T v) = dV V + V av + dv dv,
=dΩy T + ddy + dv VV dV + +VV (I- VV dV,
=dΩy + dupy + dup dd + d T [I [VVVV] dEv,
=d2 + dΩ (S o dF) (S 2 dF) D V dR (I- VVT) dRVD
Using d22 Q dt S c dF, we have dΩ + dS2y = (qT + Q11 dt.
(Q) Q dt (s o dM (s aM) D V JR (1- VVT) JRVD-1
(D.2)
Coming back to the evolution of singular values,
dD = V aRV + DV dv +av VD V aRav + +VV dRV + ( DVTAV)
dF + [DQ + Q D) di D c dF) (S & dF) D + d22
+ v dR VdΩy + (I - VVT) d=v] + |dy TV + +dv T (I-VVT) dRV,
20

---

dD = 1 d dF + [DQ + q D) di ( D ( R dM + dM S o dM)
S o dM) dM V dR (I VV dRVD - dR (1 VVV) dR.
(D.3)
Note that dD is diagonal, hence, I dD = dD.
I dD = o dF +I@ (DQ) + Q D) - I [(S @ dM) D (S 3 dM)
+ o dM (S o dM) + 21 o DD 'v dR VV- dR)
Note that & (DM) 1 (MD) D @ M for any matrix M and diagonal matrix D, using this property, simplify the above expression as,
dD 1 dF D
Q + Q dt - 1 (SodM) D ( O dM)
21 о dM (S o dM) 2D (V dR [I-VV] dR)
Using Eq. D.2, we have,
D Q + Q dt D ② [S の dM)
(S O dM) D D- dR [I- VV dRVD-1
I@ (s - dM
S 2 dM
D -
D
V
dR (I- vVT) dRV).
Using this,
dD=IodB dF +10 (s dM)
(s @S@dM) D - - (S dM dM D ( @ dM)
21 (M [ o dM +D (v dR (1 vv dRV).
10 dF +10 (s 9 dM)
[S dM D D
2 + (d S の dM
+
D (V dR -1- (1- dRV).
= 10 dF +10
[SS dM)
dM
2 (dM (S o dM) +D 1 (V (I- dRV),
To dF To
dM
(S (S@MM)
dM)
+ D-1 0 (V dR (T VVT) dRV).
Evolution of eigenvectors for general matrix SDE. Here, we derive the evolution of eigenvectors,
Using Eq. D.2, have,
(Q D) dt (s dM (S dM) D- dR (V-VT) dRV
Now further using the constrain that dD needs to be diagonal we get,
DQQ + Q D) dt = dD 10 dF + (s c dM) D (s & dM) dM (s e @ + (S 3 dM) dM
V dR (I- VV dRVD D V dR (I VV dR.
(DQ) - QQ di = dD dF - (S の dM
[(S の dM) D - (S R dM) dM S @ dM
+ ( dM dM v dR (I VV dRVD-1
dD 16 (S o dM
[M o i| - dM (S dM
+ (s (S dM v aR (T- VV dRVD-1
= dD - 10 + (S dM
dM @1 dM (s + dM
V ('dR(1-VV) VV dRVD-!
I6 (DQ] - Q dt =0 (D 10 dF) I (S dM)
dM I]] -i (d aM)
- To ( dR [T VV dRVD
21

---

( di So
[-(s
dM
dM +
| + dM
dM
dM) + v'aR (T- -V- dRVD-1.
Combing these, get the diagonal and off diagonal terms of Q]
Q dt To (Q) 27ddr.
I (s o dM) o dM)
I@ D- dR (I VVT) dRVD
2
2
T (S
dM)
(S dM
10 D- (1- VVT) dRVD
Q
2
2
so [(S の dM)
dM @ |] + +S@ e (M (S e dM)
+ S (V dR dR
VV- dRVD-1)
Computing of Q1. Recalling the evolution of the eigenvectors.
dV Vddl + (T VV VV
ddv.
Using the Jacobian of the eigen vectors, write,
dΩgy Q dt G
d=v Q_ d/ dR VD-1
VD dV V [Q] dt S o dF] + (T VV (q] di + dR VD- )
dV [q] dt S o dF V + dt dR| -I- VVT).
Using the fact that (T VVT) R 0 and deriving it,
= (I- VVT) R
0 = =d[(11 [[[I-VV vv R).
dR -d(VVR), R);
=dVV R+ VdV R VV dvav R R dR + VdV dR
dRV dVD - Vdv VD VV dRV +Vva VD dVV dRV + vdv dRV,
dVD = V QQ d
+ VV- + dR VR.
Vdv VD = V {Q dt So D,
dVaV VD = v dF 2 dF) D - [[1 VV dRVD '1 dF
dVV dRV = V dF OF + [I- VV dRVD dF
VdV dRV [S dF| dF + VD-'V dR VV dRV.
Adding the terms up get,
V Q Q Ddt + VV Q Dd
V o dF S @ dF D [(1 VV dRVD [S dF
+ [[I - VV dRVD '] dF + VD V dR(1 VV dRV =
(I-VVT) Q Ddi [(T VV dRVD 1 [S @ dF + [(1 VV dRVD-1 dF 0.
(T-VVT) Q
(VV)Q.DD. Ddt [[] VV dRVD '1 S ④ dF) D [ VV dRVD d]F
dF,
(1-VV Q = [11 VV dRVD '1 [S O dF) D dF) D-1
Q [dRVD '1 [ dF) D dF D
This gives the expression for Q and this ends our computation.
22

---

Lemma D.3. For any matrix A E Ruxm B E R m X n-dimenssioall Brownian motion dB, the following results hold the covariance
dB,AdB; = AT,
(D.4)
dB, = tr (B) I
(D.5)
Lemma D.4. With S defined in Equation (D.I), dF = EV dB,cT + cdB, VV and
dm,
(a ② dB.).
dF C dF) cs Sdiag (c) dt Dddaa (Sdiag (c) c) dt Ddiag (c) Sdiag (c) dt.
(D.6)
Proof.
@ dF [diag (c) Sdiag (dm²) + diag (dm;) Sdiag (c)], dF o dF) (cdm," + dm.c ") [diag (c) Sdiag (dm;) + diag (dm)) Sdiag (c)], cs Sdiag (c) Ddiag (Sdiag (c) c) + Ddiag (c) Sdiag (c) dt.
Lemma D.5. With S defined in Equation (D.1), dF dFF ΣV dB,c² T + cdB, T 'V and def
dm;
dB.).
SS dF)(S o dF) Ddlaa (Sdiag (c)² dt + diag (c) SDSdiag (c) dt.
(D.7)
Proof.
(S @ dF)
S ② (dm,c) + cdm, T),
diag (c) Sdiag (dm,) + diag (dm;) Sdiag (c).
Now, computing the product,
(S ② dS @ dF) [diag (c) Sdiag (dm;) diag (dm:) Sdiag (c)] [diag (c) Sdiag (dm,) + diag (dm,) Sdiag (c)] Ddiag (Sdiag (c)² s) di + diag (c) SDSdiag (c) dt.
Lemma D.6.
(S c dF)dm,c T dF
Proof.
(S c dm, = [diag (c) Sdiag (dm;) + diag (dm;) Sdiag (c)] dm, diag (c) S(o 3 σ)
23

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The dichotomy between SGD and GD is revealed by theorems 4.1 and 4.2, the repulsive force between the eigenvalues of parameter matrix is discussed in theorems 5.1 and 5.2. Supporting experiments are discussed in section 7.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: The limitations of the work are discussed section a designated paragraph well as in section 5 in the discussion of theorem 5.1.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
24

---

Answer: [Yes]
Justification: Proofs the theorems that are not presented in the main body are presented in appendix B.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: The data as well as the models and optimization algorithms used are discussed in the section 7
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
25

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: The code the form of Jupyter notebook provided and all random seeds are fixed for the reproducibility purposes.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.c cc/
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: / cii.ps.cc/publii coubblic/uuiiee twwp///weeee/eee// CCodeSubmeaaac ssi asionPooicyy for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new reproducible, they proposed method and baselines. only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The setup is discussed in the section 7.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: All the graphs the parameters evolution are accompanied with the 95% confidence interval calculated on the 20 runs with different random seeds.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
26

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma enror bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
All relevant information stated in the appendix section
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https:: httppsss////riis..../// Cepublic/Ethicsiiiiiee ines?
Answer: [Yes]
Justification: The research is theoretical and does not suggest any new model that can cause harm. All the data used is synthetic.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The work investigates the effects of well known algorithms on the simple models and doesn't suggest any new applications.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
27

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The work doesn't entail models or datasets releases.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: All relevant information is stated in the appendix section C.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in package should be provided. For popular datasets, paperswithcode. thcode. com/ datasets
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
28

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodl as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
29


Reviews:
[{"review_id": "s1OsVaMGQs", "reviewer": "Reviewer_V8cQ", "summary": "The paper proposes an analysis of the gradient flows of two layer linear neural networks with a squared loss borrowing tools from differential equations. The paper's result establishes that the stochastic gradient method generates solutions (limit of the flow as time goes to infinity) with determinant of the parameters x parameters transpose tending to zero. This implies that the parameters of a model optimized with stochastic gradient converge to a low-rank (simple) solution. While the full gradient method's solutions for the same problem do not exhibit the same simple structure. Authors conclude that this finding gives an explanation to the implicit bias of SGD.", "questions": "Is it possible to verify the breadth of validity of the result (parameters of SGD based solution live in a low-rank manifold, not the FGD) on different neural network architectures and see whether similar conclusions hold? Or which other property (if low rank is too restrictive) would you test for?\n\nDoes this theory imply that for the simpler vector problem the solution of SGD is a sparse vector where FGD finds dense solutions?\n\n\nIf we add a ReLU non-linearity between W1 and W2, then in what form the simplicity of the solution by SGD will get modified? locally low-rank?", "limitations": "The papers does not discuss how broadly their findings are valid. Numerical experiments could be used for testing whether findings are still valid in slightly more complex models", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper is tackling a very interesting problem and in a relatively simple yet representative setup where learnings can be used for deriving broader intuitions on the reasons behind SGD's implicit bias. The paper's methodology looks solid and the conclusions in the proposed context are well presented.", "weaknesses": "The paper studies a very simple model. Numerical experiments are also on the same and in very small data. It would benefit the paper to run experiments on larger / more complex models to discuss the limits and validity of this theory. The generalization to other settings section 6 is only changing the loss function. The section's title is perhaps overpromising.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their interesting questions and encouraging comments. \n\n > Numerical experiments are also on the same and in very small data. It would benefit the paper to run experiments on larger / more complex models to discuss the limits and validity of this theory. \n\nPlease refer to the general comment. \n\n  > Is it possible to verify the breadth of validity of the result (parameters of SGD based solution live in a low-rank manifold, not the FGD) on different neural network architectures and see whether similar conclusions hold? Or which other property (if low rank is too restrictive) would you test for?\n\nThe phenomenon that the parameters of solutions found by SGD live in a low-rank manifold is already empirically observed in [1] (note that the noise is more prominent when the step size is large, hence the effects of SGD are prominent with large step size). Given that measuring the rank is too computationally expensive, metrics that measure the similarity between the activations or weights of the neurons would serve as a good alternative. Such metrics are used by [1] and [2]. \n\n[1] M. Andruischenko, AV Varre, L. Pillaud-Vivien, N. Flammarion. SGD with large step\nsize learns sparse features, ICML 2023. \n\n[2] Feng Chen, Daniel Kunin, Atsushi Yamamura, Surya Ganguli. \"Stochastic Collapse: How Gradient Noise Attracts SGD Dynamics Towards Simpler Subnetworks\". NeurIPS 2023.\n\n> Does this theory imply that for the simpler vector problem the solution of SGD is a sparse vector where FGD finds dense solutions?\n\nNo, the theory does not directly imply it.\nConsider the vector problem of diagonal networks where $u \\odot v$ is the re-parameterization considered. \nLet $U = \\textrm{diag}(u)$, and  $V = \\textrm{diag}(v)$ be diagonal matrices with diagonal entries  $u$ and $v$, respectively. \nThe block structure can be recovered with $\\theta = [ U ~ ~ V ] $. \nHowever, the dimensions of this block matrix are $p \\times 2p $, hence our theory does not have any implications as we need $l > d+k$. However, if a complete characterization can be obtained, then indeed a low rank of $\\theta$ would imply a sparse solution. The sparse vector problem with label noise has received much attention [3,4] and the complete characterization in the symmetric case (u=v) is given by [5]. \n\n\n\n[3]J. Z. HaoChen, C. Wei, J. Lee, and T. Ma. Shape matters: Understanding the implicit bias of the noise covariance. COLT, 2021. \n\n[4] Z. Li, T. Wang, and S. Arora. What happens after sgd reaches zero loss? –a mathematical framework. ICLR 2022.\n\n[5] Pillaud-Vivien, L., Reygner, J., and Flammarion, N. Label noise (stochastic) gradient descent implicitly solves the lasso for quadratic parametrisation. COLT, 2022.\n\n> If we add a ReLU non-linearity between W1 and W2, then in what form the simplicity of the solution by SGD will get modified? locally low-rank?\n\nPlease refer to the general comment, particularly the paragraph on ReLU networks, as the experiments indicate the simplicity bias that SGD tends to induce.", "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": "", "extra_scores": {}}, {"review_id": "FpuPZmxGPd", "reviewer": "Reviewer_Kp9L", "summary": "This paper studies the implicit bias of SGD for two-layer linear networks. The authors study this primarily using (stochastic) gradient flow (S)GF, the continuous time version of (S)GD. To model the stochasticity, they approximate the SGD noise with independent label noise. Under these assumptions, they prove that the determinant of the Gram matrix of the parameters is invariant under GF, whereas it exponentially decays under SGF. Hence, if such a network is initialized with a full-rank parameter matrix, the rank asymptotically drops by at least one under label noise SGF, which lends some evidence to a low-rank bias for SGD not present in GD. The stochastic eigenvalue dynamics are investigated further, and while the exact dynamics are not rigorously pinned down, the paper calls out the repulsive forces that could explain why SGD converges to lower rank solutions. These results are empirically verified using some synthetic data experiments for regression and classification.", "questions": "1. In line 95, should $d$ and $p$ be swapped? Since the input is $p$-dimensional, whereas the parameter $\\theta$ is $d$-dimensional (for example, the two-layer setting $d = p \\cdot k$).\n2. In line 96, there should be an $\\ell_2$ norm outside of $y_i - f_\\theta(x_i)$. \n3. In line 108, $k=1$ should be in math mode. \n4. There is a minor typo on the equation after line 208: it should read $Wa$ rather than $W^\\top a$.\n5. In the statement of Theorem 5.1 on Line 228, there is a missing comma in the definition of the ordered eigenvalues. \n6. Could the authors add a reference to the proofs in the appendix when the result is stated in the main text (e.g. Lemma 6.1)?\n7. In Section 7, I think I am missing something obvious: why are the $d + \\ell - k$ smallest singular values equal $\\sigma_2, \\sigma_3, \\sigma_4$, since to my understanding $d + \\ell - k = 10 + 10 - 2 = 18$?\n8. What can one hope to say about deeper linear networks? If I understand correctly, if one naively generalizes the construction of $\\Theta$ then the special block structure of the label noise portion will no longer hold (in particular, it seems that $Theta$ would need to contain all the prefix and suffix products of the linear layers)", "limitations": "Yes", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1. Laying theoretical foundations for the benefit of SGD over GD for optimizing neural networks is an important direction for the theory of deep learning. This paper takes a step towards identifying the implicit bias of SGD.\n2. Previous work has that balancedness of adjacent layers is a conserved quantity for deep linear neural networks optimized using GF. Invariants of the dynamics are an important analytic tool; balancedness is crucial for proving convergence for deep linear networks. This paper identifies a very clean invariant for GF which separates GF from (label noise) SGF: the determinant of the Gram matrix of a certain concatenation of the linear layers ($\\Theta$ in the paper). In particular, although the determinant is conserved for GF, for SGF the determinant decays exponentially (exactly!). This is a very nice contribution to the theory of SGD. \n3. By itself, the determinant decay only establishes that the rank drops by one in SGF. However, the authors also investigate the behavior of the singular values of the first layer $W$ in a simpler scalar regression setting by deriving the SDE for the eigenvalues of $M = W^\\top W$. Although they are not able to characterize the solution to this SDE, they clearly interpret the forces at play and highlight a repulsive effect between the eigenvalues of $M$, which encourage the singular values to decay towards zero.\n4. The authors also consider the large noise limit and cleverly reduce to the 2-dimensional setting, where having a zero singular value is equivalent to the two rows being multiples of each other. They prove that, in expectation, (a power of) the larger singular value does not decrease, whereas the (same power of the) smaller singular value does not increase.\n5. Section 6 contains many interesting extensions to other settings, such as classification, directly modeling the SGD noise as Gaussian with matching covariance, and discrete time methods. \n6. The paper is quite transparent with the limitations of the theory. It also clearly highlights where the future directions are (e.g., the full characterization of the solution for the SDE governing the evolution of eigenvalues).", "weaknesses": "It was nice to see some experiments validating the theory, but I felt that the dimensionality of the problems should be increased to be more convincing. Right now the experiments are done with $(p, l, k) = (5, 10, 2)$. Even increasing these to being in the hundreds would be interesting, and correspondingly it might be appropriate to use other metrics to measure the rank of $W_1$, such as the effective rank  $\\tr(M)/||M||$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable feedback, encouraging remarks, and meticulous proofreading of our work. They will help to make our work clearer.\n\n> It was nice to see some experiments validating the theory, but I felt that the dimensionality of the problems should be increased to be more convincing. Right now the experiments are done with $(p,l,k) = (5,10,2)$. Even increasing these to being in the hundreds would be interesting, and correspondingly it might be appropriate to use other metrics to measure the rank such as the effective rank. \n\nWe refer the reviewer to the general comment for the experiments with higher dimensions. \n\n> In Section 7, I think I am missing something obvious: why are the smallest singular values equal \n$\\sigma_2, \\sigma_3, \\sigma_4$. since to my understanding $d + l - k = 18$ ?\n\n Apologies for the typo. As we are measuring the singular values of $W_1$, it should be the $p - k$ smallest singular values instead of the $p + l -k$ ones . Here $p=5$, $l = 10 (>p)$ and  $k=2$, hence the $p - k = 3$ smallest singular values are $\\sigma_2,\\sigma_3,\\sigma_{4}$. \n\n> What can one hope to say about deeper linear networks? If I understand correctly, if one naively generalizes the construction of $\\Theta$\n then the special block structure of the label noise portion will no longer hold (in particular, it seems that $\\Theta$\n would need to contain all the prefix and suffix products of the linear layers) \n\nThank you for this question. Indeed, deeper layers cannot be directly written in this multiplicative format. However, if the network has $l$ layers $W_1,\\ldots,W_l$, for any adjacent layers $W_{i}$ and $W_{i+1}$, we can form a block matrix, $\\theta_{i} = \\begin{bmatrix} W_{i}^{\\top} & W_{i+1} \\end{bmatrix}$ and the multiplicative structure can be seen in the evolution of $\\theta_i$. The analysis can then be performed with these block structures. For the stochastic case, however, the noise covariance is not straightforward and needs to be handled carefully. \nThis approach might present a preliminary way forward for deeper networks. Another approach could be to carefully formulate a tensor structure that extends the spirit of our work beyond two layers.", "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": "", "extra_scores": {}}, {"review_id": "Lywr21tEo1", "reviewer": "Reviewer_cAQT", "summary": "This paper studies and analyzes how the rank of the parameter matrices evolves for two-layer linear networks when using GD and label noise SGD. The paper basically shows that while GD preserves the rank at initialization throughout its trajectory, SGD reduces the rank, thereby removing spurious directions. A stochastic differential equation (SDE) is derived to characterize the evolution of the eigenvalues of the parameter matrix to formalize the rank-reducing behavior of SGD. Small-scale experiments validate the derived theory.", "questions": "Please see the Weaknesses. Also, I have the following questions:\n\n**1.** In line 174, is $M = \\Theta^\\top \\Theta$?\n\n**2.** In line 207 and the equation thereafter, if $W = U \\Sigma V^\\top$, then $W^\\top a$ should be $V \\Sigma U^\\top a$.\n\n**3.** I don't understand the jump from eq. (5.2) to (5.3). There seems to be an issue with the $\\sqrt{\\eta \\delta}$ term (with the definition of $d X$).", "limitations": "Discussed somewhat throughout the paper.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "The paper has a nice insight backed up by solid theory. I'm not an expert in this area but it seems that this is a novel insight.", "weaknesses": "**1.** While the rank-reducing property of SGD is interesting, it does not imply that the prediction error (which is the generalization metric most people would care about) of SGD is lower than that of GD. What if SGD converges to a completely erroneous low-rank solution? I understand that the paper is not directly about the generalization abilities of SGD and GD, but I feel this point should be discussed somewhere. \n\n**2.** Since the results here are only for linear networks (which is completely fine), is there any intuition for why the results and claims of this paper should extend to non-linear networks?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for their insightful suggestions.\n\n> Low-rank solutions and prediction error. \n\nWe agree with the reviewer's comment that the implicit regularization might only be useful for generalization if it is aligned with the ground truth model (i.e., in the classical example of sparse regression, $\\ell_1$-regularization only improves generalization of ERM if the ground truth regressor is sparse). We also agree with the reviewer's comment regarding convergence to a sub-optimal low-rank solution which can happen due to possible over-regularization. We will discuss these issues in the conclusion of our manuscript. \n\n\n> Intuition for non-linear network. \n\nEmpirically, the low-rank phenomenon is prominent for non-linear networks when trained with SGD, see Figure 2,3 in the attached pdf.\nFor piecewise linear non-linearity like ReLU, each neuron's weights exhibit a multiplicative structure. Let $h (a,w, .) = \\sum_{j} a_j \\sigma(\\langle{w_j}{.}\\rangle) $ be the parametric model where $\\sigma$ is the ReLU non-linearity and $(w_i,a_i)$ are the input and output weights of a neuron. With $\\theta_i = \\begin{bmatrix}\n    w_i^{\\top} &  a_i \n\\end{bmatrix}  $, the dynamics of the neuron can be rewritten as $\\mathrm{d}{\\theta_i} = \\theta_i \\mathrm{d}{J_i}$, for some curated matrix stochastic process $J_i$. \nFor linear networks, these matrix-valued processes are identical across neurons, which makes the analysis tractable. In contrast, non-linear networks do not share this property. However, during the large noise phase, the stochastic matrices $J_i$ are dominated by noise even for the ReLU dynamics, which can result in some similarities between these matrices. This may vaguely explain the observed low-rank behavior.\n\n\n> Is $M = \\theta^{\\top}\\theta$ in line 174 ?  The clarification of $W^{\\top}a$ in line 207 ?\n\nYes, thank you for pointing out this missing definition. We will correct it. In l.207, it should be $Wa$ instead of $W^{\\top}a$. \n\n> The jump from eq. (5.2) to (5.3).\n\nIt is possible due to changing the time, let $t' = (\\eta \\delta) t $. Now we have that $$ \\mathrm{d}{t} = \\frac{1}{\\eta \\delta} \\mathrm{d}{t'}. $$ The Brownian motion has the following property $\\mathrm{d}{\\mathbf{B}_{t'}} = \\sqrt{\\eta \\delta} ~ \\mathrm{d} {\\mathbf{B}}_t$  (the square root is due to different scaling of Brownian motion while changing time). Substituting these gives us the required  jump.", "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": "", "extra_scores": {}}, {"review_id": "urbIhdE2tl", "reviewer": "Reviewer_kpcH", "summary": "This paper presents an interesting dichotomy between SGD vs. GD, and how stochasticity in the gradients have the ability to implicitly regularize towards low-rank solutions. I believe this point is best highlighted by Theorem 5.1, where the show that the highlighted term in Equation (5.6) has a repulsive force, increasing the gap between larger and smaller eigenvalues. The \"punchline\" of the paper is technically given in Theorems 4.1 and 4.2, where they show that the solutions given by GD cannot have its rank diminished (rather stays at initialization), whereas we can see a decay in SGD (or SGF rather).", "questions": "See Weaknesses. I would be more than happy to raise my score if my concerns can be addressed.", "limitations": "I have stated the limitations throughout my review.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- I believe this paper fits well within the study of implicit regularization properties of certain optimizers and how they drive generalization. To this end, it also includes a related works section.\n- The results are interesting, albeit a little limiting.\n- I think the result in Theorem 4.2 also highlights how large step sizes can be beneficial for generalization. This is quite a popular topic in the literature. It is easy to see that when $\\eta$ increases, the determinant vanishes faster.", "weaknesses": "- I think the presentation of the paper can be slightly improved. For example, the discussion on initialization on Page 4 was a bit confusing. The authors discuss different initialization tactics and the balancing effect, but they do not clarify which initialization they ultimately chose. I believe the intention was to show how initialization plays a role in Theorems 4.1 and 4.2, but this could be made clearer if that was indeed the intention. Furthermore, the authors could also change the notation to $\\Delta(t)$ between lines 149-150. The authors are also missing a > in line 228.\n- The experiments section is a bit lacking. Are there ways we can leverage the results from this paper to more practical scenarios / networks?\n- My main concern (which is also the weakness) is the similarity between this paper and [1], which I don't believe the authors cited. From what I read, the main takeaway in [1] is that the noise in SGD has the ability to \"push\" or \"attract\" networks towards simpler networks, which they describe to be invariant sets. If you look at Sections 5 and 6 in [1], I believe what they are trying to say is that the noise has the ability to collapse the network to an invariant set that is low-rank, and one in which some singular modes are actually never learned. At a high-level, it seems to me that this might be a stronger result than to say that there exists a repulsive force between the eigenvalues, which is the current result. If I am missing something, please feel free to correct me. Though, at the very least, I think the authors should cite this paper and delineate the similarities / differences.\n\n[1] Feng Chen, Daniel Kunin, Atsushi Yamamura, Surya Ganguli. \"Stochastic Collapse: How Gradient Noise Attracts SGD Dynamics Towards Simpler Subnetworks\". NeurIPS 2023.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable comments, and for pointing out the missing reference.\n\n> The result in Theorem 4.2 also highlights how large step sizes can be beneficial for generalization.\n\nYes, the presence of $\\eta$ does control the rate of decrease of the determinant. Hence, the larger the step size, the greater the regularization effect, which can be beneficial for generalization. Note however that due to our choice of continuous-time modeling of gradient methods, as the step size increases, the discretization error makes it difficult to accurately capture the trajectories of the discrete methods with their continuous-time counterparts, leading to potentially different behavior. In the revision, we will add a statement indicating that our model captures the role of step size up to a certain order.\n\n> Initialization, balancedness and presentation.\n\nThank you for the suggestion and the comments on the presentation of the initialization and its balancing effects. We address these points here and will revise the manuscript to incorporate these comments, making the presentation clearer.\n\nWe mentioned initialization in the problem setup because it is an important ingredient in studying the implicit bias of homogeneous networks, including linear and ReLU networks. Previous works offer various initialization strategies for gradient flow, where certain structures emerge due to the balancedness properties of gradient flow.  In contrast,  with stochastic methods, the initialization does not matter. The emergence of low-rank structures is observed despite general initialization. This behavior is exemplified in Theorem 4.1 and 4.2, which hold for any initialization. In addition, we discuss these different initialization strategies to highlight the challenges for stochastic gradients, as the balanced quantities studied for gradient flow are insufficient. \n\n> Limited experimentation, more practical networks. \n\nWe kindly refer the reviewer to the general comment regarding this limitation. \n\n> Detailed comparison with [1]\n\nThank you for pointing out this work. We were aware of it but unfortunately missed including the reference and detailed comparison in the manuscript. We will revise it accordingly. \n\n[1] investigates a phenomenon similar to ours, referred to as stochastic collapse, where the noise in the gradients causes the iterates to collapse onto certain invariant sets.  [1] also uses continuous-time modelling of SGD as an SDE. The differences between the works are outlined as follows:\n\n- In the first part of their work, [1] provides a condition under which an invariant set is attractive for the SDE they consider. Methodologically, their work characterizes the **local behavior** around the invariant sets. Specifically, once the iterates enter a small \n$\\epsilon$-neighborhood of these sets, they are attracted towards the sets. However, their does not address whether the iterates ever enter such an $\\epsilon$-neighborhood for a general initialization. \n\n  In contrast, we offer a **global guarantee**, albeit within a simplified model: low-rank behavior is observed for any initialization. To establish these global properties, we developed a novel approach by tracking a specific quantity (the determinant).  This approach enables us to characterize the global behavior and reveal the dichotomy between the presence and absence of noise.\n\n\n- The paper also studies linear networks in a teacher-student setup.  Under a set of assumptions A1-A4~[1, p.30], they derive the evolution of singular values. However, due to the balanced spectral initialization (A3-A4) and structured label-noise (A2), the analysis falls short of capturing the repulsive force in the singular values. On a technical front, deriving the SDE for the singular values is simpler when the singular vectors remain stationary, as their assumptions ensured. When the singular vectors do not move, all the matrices can be simultaneously diagonalized, which simplifies deriving the singular values' dynamics. In our problem, however, the singular vectors move and follow a stochastic process, which makes tracking them significantly more challenging.\n\n[1] Feng Chen, Daniel Kunin, Atsushi Yamamura, Surya Ganguli. \"Stochastic Collapse: How Gradient Noise Attracts SGD Dynamics Towards Simpler Subnetworks\". NeurIPS 2023.", "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": "", "extra_scores": {}}]

Author rebuttal:
## Broader empirical evaluation 
We would like to thank the reviewers for their positive assessment of the paper and their appreciation of our work. Below, we address general comments that were raised multiple times. Individual responses can be found following each review. All referenced figures can be found in the attached PDF.

**Higher dimensions.**
First, at the request of reviewer Kp9L, we have conducted experiments in higher dimensions to robustly evaluate our theoretical findings. We choose a scalar linear regression problem on Gaussian data in dimension $p = 100$. We trained a linear network with an inner layer width of $l = 100$ using gradient descent, both with and without label noise. As shown in Figure 1, we observe that when trained with label noise, all singular values of the $W_1$ matrix, except the largest one, diminish to zero. This behavior is in contrast to the deterministic full-batch gradient descent where the singular values do not diminish. 

**Non-linear networks.**
Many reviewers have asked for broader empirical validation of the phenomenon we theoretically capture in linear networks. 
Indeed, recent efforts have been made to empirically understand the regularization effects induced by stochastic noise across various architectures. 
For the sake of completeness, we recall some empirical results here. First, we consider simple non-linear architectures and then discuss general architectures. This discussion will be added to the revised version of the manuscript. 

**ReLU non-linearity.** (more relevant to the question of reviewers V8cQ, cAQT).  
Following the approach of [1], we consider a one hidden-layer ReLU network in a teacher-student setup for a scalar regression task. 
We first present empirical evidence for $p=2$, as this allows for clearer visualizations. 
Figure 2 shows how training with label noise regularizes ReLU networks by pushing the neurons to align with a few relevant directions (the directions of the teacher neurons here). 
As reviewer V8cQ pointed out, the weight matrix gets locally low rank and the neurons are aligned. 
Once they are aligned, they stay aligned, thus inducing alignment globally. 
In Figure 3, we show the singular values for a regression problem in dimension $p=5$.  The dynamics of the singular values are also similar to the case of linear networks we have theoretically studied. 

**General architectures.** 
For large-scale neural networks, we refer to the experiments in papers [1] and [2]. 
[1] studies implicit regularization across various architectures, from single hidden-layer networks to deep networks like DenseNet, while [2]  focuses on various deep learning architectures like ResNet and VGG. 
The main takeaway from these works is the empirical verification of the low-rank phenomenon, which we aim to support with theoretical backing. 
The low-rank phenomenon is verified by the sparsity coefficient in [1] and the fraction of independent neurons in [2], which measures the alignment between the weights or activations of the neurons. 
Intuitively, the more aligned they are, the lower the rank of the parameters. 
We will appropriately cite these empirical works throughout our paper to broaden the scope of our results.


[1] M. Andruischenko, AV Varre, L. Pillaud-Vivien, N. Flammarion. SGD with large step
size learns sparse features, ICML 2023. 

[2] F. Chen, D. Kunin, A. Yamamura, S. Ganguli. "Stochastic Collapse: How Gradient Noise Attracts SGD Dynamics Towards Simpler Subnetworks". NeurIPS 2023.

Meta-review: The paper investigates the differences between Stochastic Gradient Descent (SGD) and Gradient Descent (GD) in the context of a two-layer linear network with square loss. It reveals a dichotomy: GD maintains the rank of the parameter matrix from initialization, whereas SGD, especially in the presence of label noise, reduces the rank over time. This phenomenon is analyzed by examining the evolution of the determinant of the parameter matrix, and the stochastic differential equation (SDE) governing the eigenvalues is derived. The SDE indicates a repulsive force between eigenvalues, leading to rank deficiency. The findings are supported by experiments extending beyond linear networks and regression tasks.

The referees highlighted that the analysis was comprehensive: the derivation of the SDE governing eigenvalues adds depth to the understanding of rank deficiency, providing a strong mathematical foundation for the observed phenomena. I recommend to accept it to NeurIPS 2025.

Nevertheless, I believe the authors should take into account the issues raised by the referees for the camera-ready version, but it seems the authors acknowledged them during the rebuttal.
Decision: Accept (poster)