Implicit Bias of SGD for Diagonal Linear Networks: a Provable Benefit of Stochasticity
Authors: Scott Pesme
Loucas Pillaud-Vivien
Nicolas Flammarion
Venue: NeurIPS 2021 Poster (2021)
Keywords: Implicit bias
SGD
diagonal neural networks
SDE
implicit regularisation

Abstract: Understanding the implicit bias of training algorithms is of crucial importance in order to explain the success of overparametrised neural networks. In this paper, we study the dynamics of stochastic gradient descent over diagonal linear networks through its continuous time version, namely stochastic gradient flow. We explicitly characterise the solution chosen by the stochastic flow and prove that it always enjoys better generalisation properties than that of gradient flow.Quite surprisingly, we show that the convergence speed of the training loss controls the magnitude of the biasing effect: the slower the convergence, the better the bias. To fully complete our analysis, we provide convergence guarantees for the dynamics. We also give experimental results which support our theoretical claims. Our findings highlight the fact that structured noise can induce better generalisation and they help explain the greater performances of stochastic gradient  descent over gradient descent observed in practice.




Implicit Bias of SGD for Diagonal Linear Networks: a Provable Benefit of Stochasticity
Scott Pesme EPFL scott coott.pesme@epl.cc
Loucas Pillaud-Vivien
EPFL
loucas loucas.pillauee.. wtw.aapppiiaaddiiiiieeeee......
Nicolas Flammarion
EPFL
nicolas, . www.mamion@epplllcmmmmmmmm
Abstract
Understanding the implicit bias of training algorithms is of crucial importance order to explain the success of overparametrised neural networks. In this paper, we study the dynamics of stochastic gradient descent over diagonal linear networks through its continuous time version, namely stochastic gradient flow. We explicitly characterise the solution chosen by the stochastic flow and prove that it always enjoys better generalisation properties than that of gradient flow. Quite surprisingly, we show that the convergence speed of the training loss controls the magnitude of the biasing effect: the slower the convergence, the better the bias. To fully complete our analysis, we provide convergence guarantees for the dynamics. We also give experimental results which support our theoretical claims. Our findings highlight the fact that structured noise can induce better generalisation and they help explain the greater performances of stochastic gradient descent over gradient descent observed in practice.
Introduction
Understanding the performance of neural networks certainly one the most thrilling challenges for the current machine learning community. From the theoretical point of view, progress has been made several directions: we have a better functional analysis description of neural networks [3 and we stcadily understand the convergence of training algorithms (29 [0] as well the role of initialisation [20 12]. Yet there remain many unanswered questions. One which is why do the currently used training algorithms converge to solutions which generalise well, and this with very little use of explicit regularisation 33
To understand this phenomenon, the concept of implicit bias has emerged: if over-fitting is benign, must be because the optimisation procedure converges towards some particular global minimum which enjoys good generalisation properties. Though explicit regularisation is added, the algorithm implicitly selecting a particular solution: this is referred to as the implicit bias of the training procedure. The implicit regularisation of several algorithms has been studied, the simplest and most emblematic being that gradient descent and stochastic gradient descent in the least-squares framework: they both converge towards the global solution which has the lowest squared distance from the initialisation. For logistic regression on separable data, Soudry et al. show in the seminal paper BI that gradient descent selects the max- mar-mn classifier. This type of result has then been extended to neural networks and to other frameworks. Overall, characterising the implicit bias of gradient methods has almost always come down unveiling mirror-descent like structures which underlie the algorithms.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Train losses
||
Test losses
|
12,11
10a
SGD
SGD
10"
GD
10-2
10
10
10-2
10-6
10'
10a
10
10
10
10
10
Iteration t
Q
Figure 1: Sparse regression with n 40, - 100, 11,
5, 5,
70,
3%g Left:
for initialisation scale a 0.05, SGD converges towards a solution which generalises better than GD. Right: for different values of the initialisation scale a, the solution recovered by SGD has better validation loss than that of GD. The sparsifying effect due to their implicit biases differ by more than an order of magnitude. See Section 5. for the precise experimental setup.
While mostly all of the results focus on gradient descent, it must be pointed out that this full batch algorithm not used in practice for neural networks since it does not lead to solutions which generalise well [23]. Instead, results on stochastic gradient descent, which is widely used and shows impressive results, are still missing or unsatisfactory. This has certainly to do with the fact that grasping the nature of the noise induced by the stochasticity of the algorithm is particularly hard: mixes properties from the model's 's architecture, the data's 's distribution and the loss. In our work, by focusing on simplified neural networks, we answer the following fundamental questions: do SGD's and GD's 's implicit bias differ? What is the role of SGD's noise over the algorithm's 's implicit bias?
The simplified neural networks which consider diagonal linear neural networks; despite their simplicity they have become popular since they already enable to grasp the complexity of more general networks. Indeed, they highlight important aspects of the theoretical concerns of modern machine learning: the neural tangent kernel regime, the roles of pree-parametiittion, of the initialisation and of the step size. For regression problem where interpolating solution, we study stochastic gradient descent through its continuous version, namely stochastic gradient flow (SGF). Though the continuous modelling of SGD has not yet led many fruitful results compared to the well studied gradient flow, we believe it is because capturing the essence of the stochastic noise is particularly difficult. It has generally been done in non realistic and over simplified manner, such as considering constant and isotropic noise. In our work, we attach peculiar attention to the adequate modelling of the noise. Tools from Itô calculus are then leveraged in order to derive exact formulas, quantitative bounds and interesting interpretations for our problem.
assume the existence of an
1.1 Main contributions and paper organisation.
In Section 2 we start by introducing the setup of our problem as well as the continuous modelisation of stochastic gradient descent. Then, in Section 3 we state our main result on the implicit bias the stochastic gradient flow. We informally formulate it here and illustrate it in Figure
Theorem (Informal). Stochastic gradient flow over diagonal linear networks converges with high probability to a zero-loss solution which enjoys better generalisation properties than the one obtained by gradient flow. Furthermore, the speed of convergence of the training loss controls the magnitude of the biasing effect: the slower the convergence, the better the bias.
Unlike previous works [4 36), in addition to characterising the implicit bias effect of SGF, we also prove the convergence of the iterates towards zero-loss solution with high-probabilityy To accomplish this, we leverage in Section the fact that the iterates follow stochastic continuous mirror descent with a time-varying potential. We support our results experimentally and validate our model in Scction

---

1.2 Related work
As recalled, implicit bias has recent history that has been initiated by the seminal work [31 on max-margn classification with log-loss for linear setup and separable data. This work has been extended other architectures, egg. multiplicative parametrisations [1]. linear networks [22 and
more general homogeneous neural networks [27 I1. In (36] the authors show that the scale of the
initialisation leads to an interpolation between the neural tangent kernel regime (20 12 (which is
linear regression on fixed features) leading to &2 minimum norm solutions and the rich regimes
leading to l minimum norm solutions. Note that these works focus on full batch gradient descent (or flow) and are deeply linked to mirror descent.
While the links between SGD's stochasticity and generalisation have been looked into in numerous works [2 21 16, 18 24], no such explicit characterisation of implicit regularisation have ever been given. It has been empirically observed that SGD often outputs models which generalise better than GD [6] One suggested explanation is that SGD is prone to pick flatter solutions than GD and that bad generalisation solutions are correlated with sharp minima, i.e., with strong curvature, while good generalisation solutions are correlated with flat minima, i.e., with low curvature [7 23 This idea has been further investigated by adopting a random walk on random landscape modelling [88). by suggesting that SGD's noise is smoothing the loss landscape, thus eliminating the sharp minima (24), by considering a dynamical stability perspective (38] or by interpreting SGD as a diffusion process [16 21 8). Recently, label-noise has been shown to influence the implicit bias of SGD, by biasing the solution towards the origin for
paaiiilalyypaammteerieeed models [15] or by implicitly regularising the expected squared norm of the gradient of the model with respect to the weights (5). Thus, if the notion of implicit bias of GD is fairly well understood both in the cases of regression and classification, it remains unclear for SGD, and its explicit characterisation is missing.
The linear diagonal neural networks we consider have been studied in the case of gradient descent [} and stochastic gradient descent with label noise [15. In both cases the authors show that this model has the ability to implicitly bias the training procedure to help retrieve sparse predictor. The link between gradient descent and mirror descent for this model has been initiated by [13 and further for its sparse inducing property.
exploited by the same author in 37 34
Contrary to the deterministic case, the modelling of stochastic gradient descent as stochastic differential equation is quite recent, see (2 21. However, as highlighted by M. early attempts often suffer from the drawback that they model the noise using constant covariance matrix. On the contrary, state dependant noise has now become the legitimate manner for modelling SGD as a stochastic gradient flow and it is shown in (26) that it can be done consistently. Yet, noise modelling still remains the principal issue 335 as it influences largely the behaviour of the dynamies X 9..
1.3 Notations
For input data (.)) E (Rd)" and output (yi,..., Mn) E IR", we denote respectively X E Raxd the design matrix whose i-th row is feature 2, E Id and y E R" the vector of outputs. R; denotes the set of strictly positive real numbers. For = 1,2, the f--norm of x E IRd is ||=: = E. |r, The operations @ will stand for coordinate wise product between vector: [u @ v); = u4,0; and u² O u. For p N* we also define u" == u ... C u. the p times product of with itself. All inequalities between vectors should be understood value by value. For f.g E R, the existence of C such that f= Cg and Cg S f will be denoted f S O(g) and ((g) S respectively. We shall use the symbole Ô when this is true up to log factors. For a vector u E Rdd diag(u) denotes the x d diagonal matrix which has its diagonal equal to u. For a matrix M E Rdddd, diagg (M) denotes the vector (Mi1...., Mad) Rd The indexed vector 3 will stand for any /3 interpolating the data, ie. any vector in the affine space (3 IRd s.t, XB3 Yj of dimension at least d n. Out of all || For any vector, Zoo or n0 will always designate of lim zt. 1-200
these, let Bi, = arg min
SeRd st X8=y
Setup and preliminaries
2.1 Architecture and algorithm.
Overparametrised noiseless regression. We consider linear regression problem with outputs (y1...., y,) E R and inputs (Z1,..., Ix)) (IRd)". We study an overparametrised setting (n < d)
3

---

and assume that there exists at least one interpolating parameter 3 E R which perfectly fits the training set, i.. y/ (8", for all 1 I S n. We parametrise the regression vector 8 as S.r with E IRP. We will see that though in the end our final models + (3w, are classical linear models whatever the parametrisation w + Bw: the choice of this parametrisation has crucial consequences on the solution recovered by the learning algorithms. We study the quadratic loss and the overall loss is written as:
R Σ ((Bur xii) - -y;)== - 4n Σ
1
L(w) (BBw) =
(3w0 ,,)
where by abuse of notation we use L(w)= L(Bw).
2-layer diagonal linear network. The simplest parametrisation of 3w to consider B.. = w which corresponds to the classical least squares framework. It is well known that in this case, many first order methods (GD, SGD, with and without momentum) will converge towards the same solution: say that they have the same implicit bias. This is experimentally not the case for neural networks where SGD has been shown to lead to solutions which have better generalisation properties compared to GI (23 To theoretically confirm this observation, we study simple non-linear parametrisation: Se
W v² with w = [w++ w- E 2d We point out that it is 2-positive homogeneous
and that it is equivalent to the parametrisation Sy. u O with v E IR It should be thought of a simplified linear network of depth 2 (see 33 Section 4] for more details). We consider two weight vectors W+ and w- (and not only 3 = w²) in order to ensure that our final linear predictor parameter 8. can take negative values. For the sake of completeness, the study of diagonal linear networks of arbitrary depth 2 3 is done in Appendix F.2 Also note that additionally to being a toy neural model, has received recent attention for its practical ability to induce sparsity 33 to solve phase retrieval problems 377
or
Stochastic Gradient Descent. With this quadratic parametrisation, the loss now rewrites as: L(w) 1 4n "E= (w) w² 8 2;)². Note that despite its simplicity. this loss is non con- vex and its minimisation is non trivial. The algorithm we shall consider is the well known SGD algorithm, where for step size 7 0:
W++1,+ Wz,+ - 7(3 - -3", Nieh Vie O We,+ 11+1,- Wr,- + 7/w B*, wieh Ni, O Wr,-
where ~ nn).
(1)
is convenient to rewrite this recursion as
11+1== Wr - 7V w. ((wr) 1 diag(ur, (we, (B:),
3", z,,)e; E,, [(8 ( ,,, =r.)e,,)) E R is a noise which vanishes at any global optimum (e, denotes the 7thh element of the canonical basis). We point out that all the results we shall give hold for any initialisation such that Wt=0,++ Wt==0-- E Rd under which we have that Swr.n = O. To understand under what conditions the SGD procedure converges and towards which point it does, we shall consider its continuous counterpart which has the advantage of leading to clean and intuitive calculations. We highlight the fact that we consider a bath-size equal to for clarity, however all our analysis holds for mini-batch SGD (with and without replacement) simply by considering an effective step-size Toff instead of y, this is clearly explained in Appendix A
where E.,
multiplicative
2.2 Stochastic gradient flow
Continuous time modelling of sequential processes offer a large set of tools, such derivation, which come in helpful to understand the dynamics of the processes. This has led to large part of the recent literature to consider continuous gradient flow in order and understand the behaviour of gradient descent on complicated architectures such as neural nets. However, the continuous time modelling of stochastic gradient descent is more challenging: it requires to add on top of the gradient flow diffusion term whose covariance matches the one SGD. Hence, it is fundamental to understand its structure and scale.

---

Understanding the noise's structure. As seen in equation (2) evaluated at wi: the stochastic
noise y diag t (x)xxx E,, (w) has two main characteristics which we want to preserve:
It belongs to span(w+ @ .1,...,, W ② xm)
It has covariance Soao (w+) := 72 diag(w+) X Covi, (Si, (8)) diag(w+) E Rdxd
remains to understand the structure of the covariance of f,, which has the following closed form: 1
1 Cov,, (8)) = " diag( (3 - ,x," ( n² ((5 3", xx) 8*, z2y) ISi.gSn" We identify the two key facts: (i) it is diagonal the leading n= order and (ii) its trace linked to the loss as Var;, (llss (8)112) (B) + O ( This leads us in modelling Ei, (3)'s covariance matrix as T. as it preserves these two characteristics Finally this brings us to consider the following
modelling of the overall noise's 's structure: Egen (w-) ~ 4 (d)]adig(((e (wrinngw++xXX))))
Stochastic differentiable equation modelling. Guided by the previous considerations, we study the following stochastic gradient flow:
dwa,t V L(w, dt + 2/ 1 [(w,) w @ [XT dB.]
(3)
dwa,- = V
V -- L(w,)((w))))))))))) dt - 2 L(we) wh O [ dB,).
where dB3 is standard R" Brownian motion. The SDE is perturbed gradient flow with diffusion
term that is defined such that its Euler discretisation with step size leads Markov Chain whose
covariance exactly matches SGD's noise covariance E (w+). We refer to [26] or [25] for the
technical details regarding consistency of such a procedure in the limit of small step sizes. This stochastic differential equation is the starting point of the analysis.
3 The implicit bias of the stochastic gradient flow
Implicit bias and hyperbolic entropy. To understand the relevance of the main result and how stochasticity induces a preferable bias, we start by recalling some known results for gradient flow, In (36) it is shown, assuming global convergence, that the solution selected by the gradient flow initialised at a E Rd and denoted 3% solves a constrained optimisation problem involving the hyperbolic entropy introduced by [13]:
g arg min
(a( =
1 1=1
1 d
Baarcsinh(
B: 20
V BP 4a
(4)
BERd st. XB=
Though the hyperbolic entropy function has non-trivial expression, its principal characteristic is that it interpolates between the & and the Ez norms according to the scale of a. More precisely for
E RR
1 In (1]11 and (3) a - =Fa² + Toa 1 || 22 + o(a 2). We refer to (3) a0
Theorem 2] for more details on the asymptotic analysis. The implicit optimisation problem therefore highlights the fact that the initialisation scale of the weights controls the shape of the recovered solution. Small initialisations lead to low -norm solutions which are known induce good generalisation properties: this is what is often referred to the rich regime. Large initialisations lead to low f2-norm solutions: this is referred to as the kernel regime or lazy regime in which the weights move only very slightly. The dynamics of the gradient flow are then very similar to the one of kernel linear regression with the kernel depending on the initialisation (20 Overall, to retrieve sparse solution, one should initialise with the smallest possible. However, is clearly explained in [36], it is important to stress out that there a generalisation optimisation tradeoff:: the point 0 happens to be saddle point for the loss and a smaller will lead to longer training time.
36
Main result. In the main theorem we show that, for an initialisation scale a, the stochasticity of SGF biases the flow towards solutions which still minimise the hyperbolic entropy. However, what is remarkable is that it does so with an effective parameter ass which is strictly smaller than a. The recovered solution therefore minimises an optimisation problem which has better sparsity inducing properties than that gradient flow.
I 'the general case is discussed Appendix E.1
If E IP consider the abuse of notation da da1.
5

---

Theorem 1. For p S 2/ and Wo,+ = E (R*)², let (wi)e20 follow the stochastic gradient
flow ② with step size 7 S (((In())mma max ( ll, In
[ lla
miim a ); [|a]12]]] where BE,
arg min ||,8|1 and Amax is the largest eigenvalue of X X/n. Then, with probability at least 1 p. BEX x8=y
(3 e2o converges towards a zero-training error solution 5%
the solution 8% satisfies
XT n
8% arg min SER* Lr. X3=y
Oa (3) where ako = a ( exp
22 diag
L(B,) ds) (5)
The theorem is three-fold: with high probability and for an explicit choice of constant step size (i) the flow (3))200 converges, (ii) its limit 8% is an interpolating solution, i.e. X 8 = y , (iii) this solution minimises the hyperbolic entropy problem with parameter that depends on the dynamics. We illustrate these results in Figure Now let us comment further the theorem.
Train losses L(3)
[(3.)dss
Test losses | 8 11
10a
GD
10a
GD
10
SGD
5GD e1
10 9.
SGD #2
10-1
SGD #2
10-9
10
10-12
GD
10-4s
SGD #1
10-1
SG0
42
10-1
16a
10
10a
10
10a
10
10'
10'
10"
10
iteration t
iteration t
iteration t
Figure 2: Sparse regression (see Section 5. for the detailed experimental setting). Both SGD and GD are initialised at a = 0.1. 2 different runs of SGD over the training set are performed, they differ due to the inner stochasticity of the algorithm. Lefi: GD and SGD both converge towards global minimum. Middle and right: for two different trajectories of SGD, the higher the value of the loss integral at convergence, the better the validation loss. In both cases SGD converges towards a solution which generalises better than GD. This figure illustrates Theorem
Beneficial implicit bias through effective initialisation. The most remarkable aspect of the result is that the recovered solution 3% minimises the same potential as for gradient flow but with an effective parameter Osc which is strictly smaller than a. Hence, the hyperbolic entropy closer to the & norm compared to the deterministic case, proving a systematic benefit of stochasticity. Note that this effective parameter is random and controlled by the loss integral fo+= L(3x) ds: the higher the integral, the smaller the effective initialisation scale. In other words and quite surprisingly. the slower the loss converges to 0, the "richer" the implicit bias. However, it must be kept in mind that, as explained in [36). there is a tension between generalisation and optimisation: a longer training time might improve generalisation but comes the cost of... a longer training time. Yet is clear experimentally that SGD systematically largely wins the trade-off over GD (see Figure 2 Interestingly, Problem (5) tells us that the implicit bias of SGD initialised at a acts as if we run GD initialised at a (see Section (.3). Note that the minimisation problem (3) only makes sense posteriori since the quantity ac depends on the whole stochastic trajectory. Finally, an interesting question is whether one can quantify the scale of this beneficial phenomenon, i.e. how small a. compared to a. To answer this, we quantify the scale of the loss integral w.r.t. y and a (see Proposition 3) and show under slightly stronger conditions that the relative scale axe /a decays as power of a (See Eq. (8) of the main text and Proposition 66 of the appendix for proof).
Kernel regime. Though it is less our focus, our result still holds as + +oo which corresponds to the kernel regime. In this regime, believe that f0 T(33)) ds - (not shown in the paper but experimentally observed) and hence SGF and GF converge towards the same solution. This is expected since in the NTK regime, the iterates follow a kernel linear regression for which the bias of SGF and GF are the same.

---

Step size. Note that the convergence of the iterates holds for a constant step size. This is not illogical since in the overparametrised setting, the noise vanishes at the optimum (see [32 for convergence result in the overparametrised least-squares setup). The explicit formula for the upper [l 11 bound is 7 - (400 In Amax XX_X max |1,9 l1 In (v2 min; af
It has classical dependence on Amax (XT (XTX/n) which can be computed, but also on the unknown value of || I|1- However in practice we choose the highest value of for which the iterates converge. Note that in practice the weights are often initialised such that ||a:] is roughly equal to and hence is sensible to consider ||a|12 < 118t, 1I In the explicit bound, there is a In (118;, /lz/ min; at) -1 factor, believe that is an artefact our analysis and could be removed. It is hence best to think of the upperbound on simply be y I 0 Auma 192 I1
||all
Convergence and proof sketch. Let us put emphasis on the fact that since we deal with a non- convex problem, neither convergence nor convergence towards global minimum are obvious. In most of similar works, convergence of the iterates is assumed [36] [4]. In fact, the hardest and most technical part of our result is show the convergence of the flow with high probability: once the convergence is shown, describing the minimisation problem 8 verifies is straightforward In the
following section we give several properties which constitute the major keys of the theorem's 's proof.
Links with mirror descent
The aim of this section is to show that the sequence (Be) (3e) follows stochastic version of continuous mirror descent with a time dependent mirror. From this crucial property, we show how the convergence and implicit bias characterisation follow. Finally, as it is one of the central objects of our main theorem, we give an estimation of So L(3,) ds.
4.1 Stochastic continuous mirror descent with time-varying potential
We start by recalling known results on the link between implicit bias and mirror descent. We recall also convergence guarantees for mirror descent dynamics.
Mirror descent:
convergence and implicit bias. For any So E Rd and convex potential function V consider the mirror descent flow (5.), which corresponds to (V (L, Though the convergence of the loss to is straightforward, showing the convergence of the iterates requires more work and shown 4 Theorem 2] for strongly convex potentials. Yet, once the convergence of the iterates is shown, deriving the implicit minimisation problem is straightforward. We recall the reasoning here (see Section of 2 for more details): integrating the flow yields ($x)))
(P)) = - _ (B.).) ds = -4XT Jo X(3, Boo) ds E span(X). This condition, along with the fact that 83 exactly corresponds to the KKT conditions of the problem:
8o0 = arg min
(3.
(6)
BER st. Xß=
where (3,3,))) = - (36) - (V)() - (b) is the Bregman divergence w.r.t. V.
Link with our model. It turns out that these general observations mirror descent apply to framework when (we); follows the gradient flow dw.,, - Vwa L(w,) dt. Indeed it has been shown in (36) that the corresponding iterates 3r = w w follow a mirror descent with potential &, defined in Eq.44). Therefore we can apply the previous remarks obtain the convergence towards an interpolator" as well as the associated implicit minimisation problem which in our case can be arg min (3) since Vd. (8o 0) O.
rewritten as 3 BER X8=mm)
Stochastic Mirror descent with a time varying potential. To address the problem where (wy) follows a stochastic gradient flow instead of a gradient flow, it is natural, as in the deterministic framework, to see what type of flow (3)), follows. Because of the noise, we cannot hope to simply
II our case, d., is not strongly convex so bit more work is necessary to show the convergence of the iterates (see Appendix C).
7

---

recover a classical mirror descent. However interestingly the next property shows that it follows stochastic mirror-like descent with geometry that depends on time.
Proposition 1. Consider the iterates (w))120 issued from the stochastic gradient flow in Eq. with initialisation Wo,+ = a E )² Then the corresponding flow (51) a "stochastic continuous mirror descent with time varying potential" defined by:
dV (5i)
(BB) dt + L(B)) dB,,
where az 3 exp (-2y diag in
[ m So L(Ba) ds) and da is the hyperbolic entropy defined
Under this form we clearly see that the iterates (Be), follow a flow which closely resembles that of mirror descent but with two major differences: (i) the potential Φo,, changes over time according the random quantity Sg L(B.) ds, (ii) the flow is perturbed by noise. We highlight the fact that viewing the dynamics this way has the major advantage of giving clear roadmap for the proof of Theorem [ (i) we can adapt classical mirror-descent results to our framework and construct appropriate Lyapunov functions to prove the convergence of the flow with high probability to some interpolator 8 (ii) immediately recover the corresponding minimisation problem as in the deterministic case. Indeed, integrating Eq. 7 still yields V Voa (8 E span (X) which, along with X y. are the KKT conditions of the implicit minimisation problem (5) We emphasise the fact that the structure of the noise, belonging span(XV (X), is crucial in order obtain this minimisation problem. This would for instance clearly not be true we considered isotropic noise in the SDE modelling. This highlights the fact that not every form of noise improves the implicit bias: the shape of the intrinsic SGD noise is of primal importance
15
4.2 Convergence and control of Jo I(3)) ds
Though it seems easy to derive the implicit minimisation problem (5) from the mirror-like structure of (.. is necessary to ensure that the iterates converge towards an interpolator 3xc. This the purpose of the following proposition.
Proposition 2 (Convergence of the iterates). Consider the iterates (w))12 issued from the stochastic gradient flow ( initialised at wo,+ E (Rt)*. For p S 2/2 and y such as in Theorem 1 then with probability at least 1 the flow (Be), converges to an interpolating solution 3
The convergence of the iterates is technical and requires several intermediate results. We start by considering appropriate Bregman-type stochastic function with a time-varying potential and show that it converges with high probability. Leveraging the fact that we are able to bound the iterates fe, are able to show that the limit of the function is in fact O. Owing to the fact that the function consider also controls the distance of Se to a particular 8 we finally get that the iterates converge.
However for the objects (such atoo) and functions we introduce to be well defined, we need to guarantee the convergence of f ((3,)ds Besides, it is crucial to grasp the scale of this quantity
since it gives the overall scale of axc. This is done in the following proposition where we lower and upper bound its value.
Proposition 3. Under the same setting as in Proposition 2 with initialisation W = al, we have with probability at least p:
2e (1105, 111 In [107%,11 1h a
((3.) < o( max {11S7, 11 In (1.5 a²
) add)).
a-+0
We point out that the lower bound is given for small a's for simplicity but provide in Lemma 7 (Appendix B.5) lower bound which holds for all a's. Note that when 7 = O, which corresponds to deterministic gradient flow, we can give the exact value for the integral: _r+ I(3x) ds
Do.. (8% Bo) (see Proposition 7 in Appendix Cp. This matches the scale of the bounds given in Proposition 3 hence showing the Tightness of the result. We focus now on how this translates to the scale of the effective initialisation w.r.t. a when this latter is small enough. In fact, this lower bound on the integral of the loss along with a stronger assumption on the boundedness of the iterates lead to
a0o0 a
(8)
1 ||
a0
8

---

for some > O. Hence the smaller the initialisation scale a and the greater the benefit of SGD over GD in terms of implicit bias (see Appendix [B.6 for more details).
Again, the proof of this proposition is technical and relies on considering appropriate I Lyapunov functions which highly resemble to Bregman divergences, but which take into account the fact that the geometry changes over time. These overall decreasing Lyapunov's ' enable to bound the iterates as well as lower and upper bound the integral of the loss. The stochastic integrals which naturally appear are controlled with high probability using time-unifomn concentration of martingales [T9].
5 Experiments
5.1 Experimental setup for sparse regression
We consider the following sparse regression setup for our experiments. We choose 40, 100 and randomly generate a sparse model S%, such that || = 5. We generate the features as I ~ (0, I) and the labels y4 x 52 SGD, GD and the SGF always initialised using the same scale a > 0 and is specified each time. We use the same step size for GD and SGD and choose it be the biggest as possible why still ensuring convergence. Note that since the true population covariance E p.:". is equal to identity, the quantity 13, -3% 3%,11 corresponds to the validation loss.
5.2 Validation of the SDE model
In this section, we present an experimental validation of the stochastic gradient flow model. In Figure for the same step size, we run: (i) the trajectory of gradient descent, (ii) trajectories of stochastic gradient descent that correspond to different realisations of the uniform sampling over the data, (iii) 5 trajectorics of the stochastic gradient flow (its Euler discretisation with dt = -/10)) corresponding to different realisations of the Brownian. We clearly see (left) that the loss behaves similarly for SGD and SGF across time. We also see that the validation losses (right) of the iterates of SGD and SGF have very similar behaviours. This tends to validate our continuous modelling from Section
Train losses ((3))
Test losses ||3r - B8
GD
10-1
10a
SGDs
SDEs
10-1 11
10-1
GD
10
10
SGDs
SDEs
10-3
10 10-10
10
10
10a
105
10a
10
105
Iteration
Iteration
Figure 3: Sparse regression (see Section 3.1 for the detailed experimental setup). Left and right: the training and the validation losses behave very similarly, corroborating the continuous modelling.
5.3 GD and SGD have the same implicit bias, but from different initialisations.
In order to confirm and illustrate the main Theorem we provide the following experiment which is illustrated Figure 4 We first run GD and SGD with the same step-size and ini- tialise them both at al with a = 0.01. As expected, the solution recovered by SGD gen- eralises better. Then, using the iterates 3SGD from the first SGD run, we compute the value as0 a exp(-2> diag(X' X/n) l L(SSCD)dss Jds) E IRd (the integral is approximated by its dis- crete time approximation with di = 7). We then run gradient descent but this time initialised at Wo.t aso- According to our main result from Theorem [ it should approximately (it would be exact if we ran SGF and GF) converge to the same solution as SGD initialised a1. This is clearly
observed Figure 4 (right). Also note that SGD and GD (initialised at aco) seem to have overall very

---

similar dynamics, this is not shown by our results and we leave this as future work. However keep in mind that though the validation losses converge the same iteration rate, in terms of computation time, SGD is n times faster.
Train losses ((s))
Test losses ||
f8 11
10
10c
GD from
SGD from a
10
10-1
GD from disc
10-6
GD from
10-3
10-9-
5GD from
10 12 GD from diec
10'
10a
10
10
103 10a
Iteration
Iteration t
Figure 4: Sparse regression (see Section 5.1 for the detailed experimental setup). Left and
right: SGD initialised at a1 converges towards the same point GD initialised at axo axexp(- diag(X X X/n) So (dB)
5.4 Doping the implicit bias with label noise
As largely discussed throughout the paper, the effect of the implicit bias is controlled by the conver- gence speed of the loss: the slower it converges, the sparser the selected solution will be. Hence the following question: can we leverage this knowledge to dope the implicit bias? We argue in this Section that the answer to this question is affirmative. Indeed, consider a sequence (5, )eE E IR and assume that artificially inject some label noise A, at time I, say for example A, Unif(26,, 26.) (independently from iz). This injected label noise perturbs the SGD recursion as follows:
11+ Wt, F ((3 8 v.,)) + D.) Z4, 3 We,+
where i, ~ Un, (9)
As in Section 2.2 we can derive its related stochastic gradient flow (see Appendix D.I for more details):
dw - wa L(w,) +
2 (L + 83) wt,- O dB.).
(10)
Assuming that (8.)22 E (B..) and y are such that the iterates converge, the corresponding implicit regularisation minimisation problem is preserved but with a "slowed down" loss: f.(3.) = L(33)+
((3)) The label noise therefore helps recovering solution which has better sparsity properties. However, it must be kept in mind that adding too much label noise can significantly slow down the convergence of the validation loss even prevent the iterates from converging. Yet, experimental results showing the impressive effect of label noise are provided Figure 5 in Appendix [.I
and the effective initialisation writes: ã = a @ exp (-2y diag( "
So* xXx
Conclusion and Perspectives
In this paper, we have shown the benefit of using stochastic gradient descent over gradient descent for diagonal linear networks terms of their implicit bias. Indeed, we prove that stochastic gradient flow acts as gradient flow but initialised at smaller scale: this induces sparser finale iterate. This effect controlled by the speed convergence of the loss. Moreover, we prove the convergence of the flow and exhibit interesting link with mirror descent. Fully understanding this novel type of dynamics could help to grasp the implicit biasing properties of stochastic gradient descent in other frameworks. It is also natural to ask whether the integral of the loss also controls the difference of implicit regularisation for more general architectures. It would also be interesting to analyse how this property adapts to log losses known to lead to max-margin solutions in classification.
NF would like to thank Nathan Srebro for introducing him the question of SGD's 's implicit bias as well as for the stimulating discussions they had during his visit at EPFL.
Acknowledgements.
10

---

References
[1] Alnur Ali, Edgar Dobriban, and Ryan Tibshirani. The implicit regularization of stochastic gradient flow for least squares. In International Conference Machine Learning, pages 233-244, PMLR, 2020.
[2] Shahar Azulay, Edward Moroshko, Mor Shpigel Nacson, Blake Woodworth, Nathan Srebro, Amir Globerson, and Daniel Soudry. On the implicit bias of initialization shape: Beyond infinitesimal mirror descent. arXiv preprint (11i::2002.09669 2021.
[3] Francis Bach. Breaking the curse of dimensionality with convex neural networks. Journal of Machine Learning Research, 18 18(19)11-53, 2017.
[4] Heinz Bauschke, Jérôme Bolte, and Marc Teboulle. A descent lemma beyond lipschitz gradient continuity: first-order methods revisited and applications. Mathematics of Operations Research, 42(2))330-348, 2017.
[5] Guy Blanc, Neha Gupta, Gregory Valiant, and Paul Valiant. Implicit regularization for deep neural networks driven by an manstein-uhlenber like process. Conference on learning theory, pages 483-513, PMLR, 2020.
[6] Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration inequalities: A nonasymptotic theory of independence. Oxford university press, 2013.
[7] Ioannis Chatzigeorgiou. Bounds on the lambert function and their application to the outage analysis of user cooperation. IEEE Communications Letters, 17(8):1005-155 2013.
[8] Pratik Chaudhari and Stefano Soatto. Stochastic gradient descent performs variational inference. converges to limit cycles for deep networks. In 2018 Information Theory and Applications Workshop (ITA), pages 1-10. IEEE, 2018
[9] Xiang Cheng, Dong Yin, Peter Bartlett, and Michael Jordan. Stochastic gradient and I Langevin processes. In Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 1810-1819. PMLR, 13-18 Jul 2020.
[10] Lénaic Chizat and Francis Bach. On the global convergence of gradient descent for over- parameterized models using optimal transport. In Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
[11] Lenaic Chizat and Francis Bach. Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss. In Conference on Learning Theory, pages 1305-1338. PMLR, 2020.
[12] Lénaïc Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable program- ming. In Advances in Neural Information Processing Systems, volume 32, Curran Associates, Inc., 2019.
[13] Udaya Ghai, Elad Hazan, and Yoram Singer. Exponentiated gradient meets gradient descent. In Proceedings of the 31st International Conference on Algorithmic Learning Theory, volume 117 of Proceedings of Machine Learning Research, pages 386-407, San Diego, California, USA, 08 Feb-11 Feb 2020. PMLR.
[14] Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Characterizing implicit bias terms of optimization geometry. In International Conference on Machine Learning, pages 1832-1841. PMLR, 2018.
[15] Jeff Z HaoChen, Colin Wei, Jason D Lee, and Tengyu Ma. Shape matters: Understanding the implicit bias of the noise covariance. arXiv preprint arXiv:2006.08690, 2020.
[16] Fengxiang He, Tongliang Liu, and Dacheng Tao. Control batch size and learning rate to generalize well: Theoretical and empirical evidence. In Advances in Neural Information Processing Systems, volume 32, 2019.
[17] Sepp Hochreiter and Jürgen Schmidhuber. Flat minima. Neural Comput., 9(1::1-42, jan 1997.

---

[18] Elad Hoffer, Itay Hubara, and Daniel 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.
[19] Steven R. Howard, Aaditya Ramdas, Jon McAuliffe, and Jasject Sekhon. Time-uniform Chernoff bounds via nonnegative supermartingales. Probability Surveys, 17(none):257 317, 2020. doi: 00.1214/18-PS322
[20] Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
[21] Stanislaw Jastrzebski, Zac Kenton, Devansh Arpit. Nicolas Ballas, Asja Fischer, Amos Storkey, and Yoshua Bengio. Three factors influencing minima in SGD. In International Conference on Learning Representations, 2018.
[22] Ziwei Ji and Matus Telgarsky. Gradient descent aligns the layers of deep linear networks. In International Conference on Learning Reprexentations, 2019.
[23] Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Peter Tang. On large-batch training for deep learning: Generalization gap and sharp minima. In International Conference on Learning Representations, 2017.
[24] Bobby Kleinberg, Yuanzhi Li, and Yang 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 2018.
PMLR, 10-15 Jul
[25] Peter E Kloeden and Eckhard Platen. Stochastic differential equations. In Numerical Solution of Stochastic Differential Equations, pages 103-160. Springer, 1992.
[26] Qianxiao Li, Cheng Tai, and Weinan E. Stochastic modified equations and dynamics of stochastic gradient algorithms i: Mathematical foundations. Journal of Machine Learning Research, 20(40): 2019.
[27] Kaifeng Lyu and Jian Li. Gradient descent maximizes the margin of homogeneous neural networks. International Conference on Learning Representations, 2020.
[28] Stephan Mandt, Matthew D. Hoffman, and David M. Blei. A variational analysis of stochastic gradient algorithms. In Proceedings of the 33rd International Conference International Conference on Machine Learning Volume 48, ICML' 16, page 354-363, 2016.
[29] Song Mei, Andrea Montanari, and Phan-Minh Nguyen. A mean field view of the landscape of two-layer neural networks. Proceedings of the National Academy of Sciences, 115(33): E7665-E7671, 2018.
[30] Daniel Revuz and Mare Yor. Continuous martingales and Brownian motion, volume 293. Springer Science & Business Media, 2013.
[31] Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasckar, and Nathan Srebro. The implicit bias of gradient descent on separable data. The Journal of Machine Learning Research, (9()):282222873 2018.
[32] Aditya Varre, Loucas Pillaud- -iiiin,,, and Nicolas Flammarion. Last iterate convergence of sgd for least-squares in the interpolation regime. 2021.
[33] Tomas Vaškevičius, Varun Kanade, and Patrick Rebeschini. Implicit regularization for optimal sparse recovery. arXiv preprint arXiv: /909.05999000 /22 2019.
[34] Tomas Vaskevicius, Varun Kanade, and Patrick Rebeschini. The statistical complexity of early- stopped mirror descent. In Advances in Neural Information Processing Systems, volume 33, pages 253-264, Curran Associates, Inc., 2020.
12

---

[35] Stephan Wojtowytsch. Stochastic gradient descent with noise of machine learning type. Part I: Discrete time analysis, 2021.
[36] Blake Woodworth, Suriya Gunasekar, Jason D Lee, Edward Moroshko, Pedro Savarese, Itay Golan, Daniel Soudry, and Nathan Srebro. Kernel and rich regimes in overparametrized models. In Conference on Learning Theory, pages 3635-3673 PMLR, 2020.
[37] Fan Wu and Patrick Rebeschini, A continuous-time mirror descent approach to sparse phase retrieval. In Advances in Neural Information Processing Systems, volume 33, pages 20192- 20203, Curran Associates, Inc., 2020.
[38] Lei Wu, Chao Ma, and Weinan E. How SGD selects the global minima in over-parameterized learning: dynamical stability perspective. In Advances in Neural Information Processing Systems, volume 31, 2018.
[39] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track P Proceedings. OpenReview.net, 2017
13


Reviews:
[{"review_id": "kMSDRc_iVQY", "reviewer": "Reviewer_a887", "summary": "This paper studies the implicit bias of SGD over GD trained solutions for a regression task, with MSE loss, and a quadratic parameterization of the regression coefficients.  Building off recent analysis demonstrating how the initialization for GD toggles between an implicit sparse/L2 regularization on the interpolating solution, they demonstrate that SGD has the same effect but with a strictly smaller initialization (leaning to sparse).  To get this conclusion they model SGD using an SDE with a spatially dependent, anisotropic diffusion.  Lastly, they demonstrate their main claims on synthetic data.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Originality/Significance:**\nThe key qualitative assumption discussed in this paper is \"the effect of the implicit bias is controlled by the convergence speed of the loss: the slower it converges, the sparser the selected solution will be.\"  As far as I am aware, this is a very novel statement and quite significant (even if only made for a constrained class of models).  Overall, this work was very well done, however I think more emphasis could have been on experiments (such as some of the suggestions I give below) and discussing the qualitative takeaways that might apply to the general class of nonlinear networks. I agree with the authors, the most interesting direction for future work would be \"whether the integral of the loss also controls the difference of implicit regularisation for more general architectures.\"  A longer discussion at the end on the connections of this analysis to nonlinear networks (where the benefits of SGD really shine compared to GD) would be very helpful.\n\n**Clarity/Quality:**\nThe writing and mathematics in this paper are incredibly clear and well done.  I found the flow very natural and the discussion of related work very helpful for grounding their analysis.  The experiments were well documented and explained.\n\n**Areas for Improvement:**\n- Throughout the work (such as in abstract) you say \"better the bias\", but its not clear what \"better\" means.  Is there another description that might be more specific you can use as your tag line? Such as \"sparse\"?\n- This analysis is done assuming a batch size of 1? Can this be extended to mini-batches?  A discussion about this assumption/limitation should be given.\n- In the buildup to the SDEs you never explicitly assume the noise term is Gaussian, as done in many of the \"SDE for SGD\" papers.  Yet implicitly it seems like you are,  as the Euler-Maruyama discretization of equation (3) would lead to gaussian noise with the same covariance as your noise term.  I think its worth having a discussion about this, as the Gaussian assumption has been one of the major sources for complaint on the \"SDE for SGD\" literature? \n- The statement on line 206/207 \"the recovered solution minimizes the same potential as for gradient flow but with an effective parameter which is strictly smaller\" makes me want to see an experiment where you run SGD with $\\alpha$ and compute $\\alpha_\\infty$ from trajectory then run GD with $\\alpha_\\infty$ and compare overall optimization time and final solution.  An experiment like this would definitely help convince me of the statement \"However it is clear experimentally that SGD systematically largely wins the trade-off over GD\".  If for example the SGD and GD trajectory both converge to same performing solution but SGD does it faster, then I would be very convinced on this.\n- All your experiments used features generated from an isotropic gaussian. I understand that this was done to make distance to sparse solution a measure of validation performance, but I would have been very curious to see how dynamics change with features from an anisotropic gaussian.  Intuitively, I would assume that anisotropy would have a large effect on the SGD dynamics...and maybe even the final solution reached.\n- The section \"Doping the implicit bias with label noise\" is interesting.  I would devote more space to this discussion in revision and pull experiments up from appendix.\n\n**Specific Comments:**\n- Consider citing the recent work \"ON THE ORIGIN OF IMPLICIT REGULARIZATION IN STOCHASTIC GRADIENT DESCENT\"\n- [line 105-106] \"All inequalities between vectors should be understood value by value\" => replace \"value by value\" with \"element-wise\"?\n- In the section \"Implicit bias and hyperbolic entropy\" the analysis in [32] you are referencing is for the same quadratic parametrization correct?  If so, can you make this clear.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "hlIhCwGb3a2", "reviewer": "Reviewer_9yUy", "summary": "In this paper the authors study the dynamics of SGD for diagonal linear networks. The exact expression of implicit bias is derived, showing that SGD with some initialization scale is equivalent to full batch GD (or gradient flow) will a smaller effective initialization scale. In addition, SGD slows down the convergence speed, and the slower the convergence, the smaller the effective initialization scale. For sparse problems, the smaller effective initialization scale induces better generalization, as also demonstrated empirically on synthetic data.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, I think this is a good paper. While previous works that study diagonal linear networks only consider the case of full batch GD (or gradient flow), the authors provide a novel analysis for the case of SGD. To this end, the authors model the dynamics through a stochastic differentiable equation, which solution is then analyzed.\n\nThe analysis is highly non-trivial and this is an important step forward since in practice SGD is usually used. Also, the effect of label noise on the effective initialization scale is naturally integrated into the proposed analysis.\n\nThe paper is well written and easy to read.\n\nWeaknesses:\n1.\tThe analysis only considers the case of batch size = 1 and it is not clear how the batch size affects the effective initialization scale. \n2.\tThe effect of the step size in Theorem 1 is not clearly discussed. On the one hand, a large step size will accelerate the convergence and thus the integral of the loss will be small, but on the other hand, the step size appears explicitly in the exponent.  So, is increasing step size result in smaller effective $\\alpha$ ? If yes, is it correct also for GD or only for SGD ?\n3.\tIt would be good to complement the paper will experiments on real data with real networks. Clearly, the interaction of initialization scale, batch size and step size is an important practical question.\n\nMore comments:\n- line 130: I don’t think the model is equivalent to the model $\\beta=u\\odot v$, as discussed in section 4 of [1].\n- In Theorem 1 the tradeoff in $p$ is not clear. It seems that $p$ can be arbitrarily small.\n- In Theorem 1, can you explain why a bound on the step size is needed ? Is it for stability reasons ?\n- Several relevant papers are missing:\n\nOn the implicit bias of SGD:\n\nhttps://arxiv.org/abs/2101.12176\n\nhttps://arxiv.org/abs/2003.07802\n\nOn diagonal linear networks and mirror descent:\n\nhttps://arxiv.org/abs/2007.06738\n\nhttps://arxiv.org/abs/2004.01025\n\n- In section 3 the kernel regime is discussed. Is it possible to have a similar discussion for the rich regime ? Is there a difference between SGD and GD in the rich regime ?\n- In line 220 the integral goes to 0, I couldn’t find the proof in the appendix. Also, the upper bound of the integral in proposition 3 goes to infinity when $\\alpha\\rightarrow\\infty$. Can you explain this ?\n- Can you explain why the equality in line 303 is correct ?\n- $\\alpha$ is sometimes used as a scalar and sometimes as a vector, and it will be good to distinguish between them, e.g. make vector a bold symbol. For example, in proposition 3 it is not clear if $\\alpha$ is a scalar or a vector.\n- In section 5.1 please specify what is the step size.\n- In section 5.3 will be useful to compare the result to [12].\n\ntypos:\n- line 160: I think the second diag is not needed.\n- line 316: why -> while\n- line 348: understand -> understanding\n- line 444: $\\alpha_t$ is incorrectly defined", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "15"}, "extra_text": {}}, {"review_id": "hhcvC9UoCj", "reviewer": "Reviewer_MruN", "summary": "Summary:\nThis paper studies the implicit bias of stochastic gradient flow (SGF) over a linear model, re-parameterized as a quadratic difference: $\\beta=(w_1)^2 - (w_2)^2$. The paper establishes that in the said setting, SGF has implicit bias towards sparsity (lower $\\ell_1$ norm w.r.t regular GF).", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Originality** - The paper uses original analysis to discuss stochasticity in the specific framework. The paper insinuates that SGF is presented in this work (line 151-154). Yet previous work exists [2] therefore it is difficult to determine exactly how novel are the ideas. In addition, the paper discusses some related work rather superficially (lines 75-77) neglecting to cite relevant works such as [1] that discuss implicit bias of linear regression with SGD vs GD.\n\n**Quality** - Overall, the paper is well written. My biggest concern is the setting, it is not clear to me why diagonal networks are an interesting re-parameterization of linear networks. Additional issues are (1) Unrealistic initialization, the analysis holds for any initialization such that $w_{+}=w_{-}$ which also means $\\beta_{w}=0$, it is not clear how this relates to standard initialization schemes. (2) The role of $\\alpha$ - as stated in the paper, the tradeoff is between generalization and optimization (line 212), therefore a user can set it to a desired value and control the tradeoff, it is not clear how the $\\alpha_{\\infty}$ relates to initial $\\alpha$ except from being upper bounded by it. Further discussion can be interesting.\n\n**Clarity** - The paper is very clear in an abstract level, the claims in the main manuscript as well as the specific setting are very clearly written. As for the analysis, there seems to be no apparent structure for the mathematical analysis. In the appendix it is not clear what are the important details and which sections are more technical. It made it hard to understand specific claims. For example, I would expect a more clear presentation and discussion of $\\alpha_{\\infty}$ which is written implicitly in proposition 1.\n\n**Significance** - Understanding the effect of stochasticity on the implicit bias of GD is extremely significant, with that being said, this work is limited to a non-realistic setting which makes this result weaker.\n\n[1] Wu, Jingfeng and Zou, Difan and Braverman, Vladimir and Gu, Quanquan. Direction Matters: On the Implicit Bias of Stochastic Gradient Descent with Moderate Learning Rate\n\n[2] Ali, Alnur and Dobriban, Edgar and Tibshirani, Ryan. The Implicit Regularization of Stochastic Gradient Flow for Least Squares\n\n\n**---------------------------------------------------------------------------**\n\n**Update**: Thank you for the detailed rebuttal.\n\nAfter reading other reviews and authors' responses - I believe I underestimated the significant of the problem setup and the contribution of the paper. Therefore I chose to change my score accordingly.\n\nGood luck.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations:\n- Result applies only to diagonal networks.\n- Initialization schemes does not follow standard schemes.\n\nThe reviewer does not see any negative social impact of the submitted work.\n", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "15"}, "extra_text": {}}, {"review_id": "Co5wObEugJv", "reviewer": "Reviewer_yevU", "summary": "The paper studies the implicit bias of SGD in diagonal linear networks. Specifically, through the study of SGD continues time version, i.e., stochastic gradient flow, the authors investigate the noise influence on the generalization performance. The authors show that with high probability stochastic gradient flow converges to zero loss solution that enjoys better generalization properties than the solution obtained by gradient flow. In addition, they show that slower convergence results in better generalization.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper studies the implicit bias of SGD in diagonal linear networks and the square loss. To this end, the authors model SGD dynamics using its continuous time, i.e., stochastic gradient flow (SGF).\n\nThe paper main contributions are:\n-\tThe authors prove that with high probability SGF converges to zero loss solution.\n-\tThe authors characterize the obtained solution (similarly to [32]). Specifically, their characterization implies that SGF biases the flow toward solutions with better sparsity inducing properties than GF (smaller effective $\\alpha$).\n-\tThe authors provide experimental results that validate their model and theoretical results.\n\nMy main question:\n-\tWhen modeling SGD the authors assume that all partial losses are approximately uniformly equal to their mean (Appendix A). Can you please elaborate and justify this assumption? Also, this assumption should appear in the main paper.\n\nClarity/writing: \n-\tThe paper is well written, and the results are clearly stated.\n\nMinor comment:\n-\tFigure 2 will be more clear if you include the fact that $\\Vert \\beta_t - \\beta_{\\ell_1}^*\\Vert_2^2$ corresponds to the validation error in the caption (and not just in section 5.1) \n\n---\n\nUpdate: Thank you for the detailed rebuttal. I accept your answer regarding the modeling choices you made.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors discussed the limitations of their results.", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Reviewers generally agreed that the paper is clearly written, technically solid and interesting.  Reservations with regards to the significance of the analyzed setting (diagonal linear neural networks) were raised, but given that this setting already received notable attention, the committee reached a decision by which this paper comprises a meaningful step forward (analysis of stochasticity), and should thus be accepted to the conference.
Decision: Accept (Poster)