Saddle-to-Saddle Dynamics in Diagonal Linear Networks
Authors: Scott Pesme
Nicolas Flammarion
Venue: NeurIPS 2023 spotlight (2023)
Keywords: gradient flow
saddle-to-saddle
diagonal linear network
incremental learning
TL;DR: We prove and characterise a saddle-to-saddle dynamics of gradient flow with vanishing initialisation over 2-layer diagonal linear networks.

Abstract: In this paper we fully describe the trajectory of gradient flow over $2$-layer diagonal linear networks for the regression setting in the limit of vanishing initialisation. We show that the limiting flow successively jumps from a saddle of the training loss to another until reaching the minimum $\ell_1$-norm solution. We explicitly characterise the visited saddles as well as the jump times through a recursive algorithm reminiscent of the LARS algorithm used for computing the Lasso path.  Starting from the zero vector, coordinates are successively activated until the minimum $\ell_1$-norm solution is recovered, revealing an incremental learning. Our proof leverages a convenient arc-length time-reparametrisation which enables to keep track of the transitions between the jumps. Our analysis requires negligible assumptions on the data, applies to both under and overparametrised settings and covers complex cases where there is no monotonicity of the number of active coordinates. We provide numerical experiments to support our findings.

Saddle-to-Saddle Dynamics in Diagonal Linear Networks
Scott Pesme
Nicolas Flammarion EPFL
EPFL scott. scott.pesm@@pfl..om
nicolas fwa.marion@eppll......
Abstract
In this paper we fully describe the trajectory of gradient flow over 2-layer diagonal linear networks for the regression setting in the limit of vanishing initialisation. We show that the limiting flow successively jumps from saddle of the training loss to another until reaching the minimum f f-oormm solution. We explicitly characterise the visited saddles as well as the jump times through a recursive algorithm remi- niscent of the LARS algorithm used for computing the Lasso path. Starting from the zero vector, coordinates are successively activated until the minimum 4--norm solution is recovered, revealing an incremental learning. Our proof leverages convenient arc-length time-reparamerrisatonn which enables to keep track of the transitions between the jumps. Our analysis requires negligible assumptions on the data, applies to both under and overparametrised settings and covers complex cases where there is no monotonicity of the number of active coordinates. We provide numerical experiments to support our findings.
Introduction
Strikingly simple algorithms such as gradient descent are driving forces for deep learning and have led remarkable empirical results. Nonetheless, understanding the performances of such methods remains a challenging and exciting mystery: (i) their global convergence on highly non-convex losses far from being trivial and (ii) the fact that they lead to solutions which generalise well [53] is still not fully understood.
To explain this second point, major line of work has focused the concept of implicit regularisation: amongst the infinite space of zero-loss solutions, the optimisation process must implicitly biased towards solutions which have good generalisation properties for the considered real-world prediction tasks. Many papers have therefore shown that gradient methods have the fortunate property of asymptotically leading to solutions which have well-behaving structure [38, 24, 16).
Aside from these results which mostly focus on characterising the asymptotic solution, a slightly different point of view has been to try to describe the full trajectory. Indeed it has been experimentally observed that gradient methods with small initialisations have the property of learning models of increasing complexity across the training of neural networks [29]. This behaviour is usually referred to as incremental learning or as a aaddle-to-aaddle process and describes learning curves which are piecewise constant: the training process makes very little progress for some time, followed by sharp transition where a new "feature" is suddenly learned. In terms of optimisation trajectory, this corresponds to the iterates "jumping" from saddle of the training loss another.
Several settings exhibiting such dynamics for small initialisation have been considered: matrix and tensor factorisation [44, 27], simplified versions of diagonal linear networks [23, 7]. linear networks [22, 45, 26]. 2-layer neural networks with orthogonal inputs [10], learning leap functions with 2-yayer neural networks [1] and matrix sensing [2, 33, 28]. However, all these results require
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Train losses )((()
Iterates (9/
Iterates in I spaccc
Fast soddle
|f [1]
Suldloe
Iuapo
Serond soultle
Third adddle
12
80
De-activaing roordinate
Non-stivvted coordinates
81
Global minimum
22
fg
Time t
81
f2
Time
82
Figure 1: Gradient flow (e with small initialisation scale over 2-layer diagonal linear network (for the precise experimental setting, see Appendix A). Left: Training loss across time, the learning is piecewise constant. Middle: The magnitudes of the coordinates are plotted across time: the process is piecewise constant. Right: In the R3 space in which the iterates evolve (the remaining coordinates stay 0), the iterates jump from saddle of the training loss to another. The jumping times as well as the visited saddles 3, are entirely predicted by our theory.
restrictive assumptions the data or only characterise the first jump. Obtaining complete picture of the saddle-to-saddle process by describing all the visited saddles and jump times is mathematically challenging and still missing. We intend to fill this gap by considering diagonal linear networks which are simplified neural networks that have received significant attention lately [50, 48, 25, 43, 20] as they are ideal proxy models for gaining deeper understanding of complex phenomenons such as saddle-to saddlee saddle dynamics.
1.1 Informal statement of the main result
In this paper, we provide full description of the trajectory of gradient flow over 2-layer diagonal linear networks in the limit of vanishing initialisation. The main result is informally presented here.
Theorem 1 (Main result, informal). In the regression setting and in the limit of vanishing initial- isation, the trajectory of gradient flow over a 2-layer diagonal linear network converges towards limiting process which is piecewise constant: the iterates successively jump from a saddle of the training loss to another, each visited saddle and jump time can recursively be computed through an algorithm (Algorithm 1) reminiscent of the LARS algorithm for the Lasso.
The incremental learning stems from the particular structure of the saddles as they correspond to min- imisers of the training loss with a constraint on the set of non-zero coordinates. The saddles therefore correspond to sparse vectors which partially fit the dataset. For simple datasets, consequence of our main result is that the limiting trajectory successively starts from the zero vector and successively learns the support of the sparse ground truth vector until reaching it. However, we make minimal assumptions on the data and our analysis also holds for complex datasets. In that case, the successive active sets are not necessarily increasing in size and coordinates can deactivate as well as activate until reaching the minimum én-nrrm solution (see Figure 1 (middle) for an example of deactivating coordinate). The regression setting and the diagonal network architecture are introduced in Section Section 3 provides an intuitive construction of the limiting aaddle-to-sadde dynamics and presents the algorithm that characterises it. Our main result regarding the convergence of the iterates towards this process is presented in Section and further discussion is provided in Section
Problem setup and leveraging the mirror structure
2.1 Setup
Linear regression. We study linear regression problem with inputs (#1,..., xx) (Rd)" and outputs (y1...., Vn) ) E R., We consider the typical quadratic loss:
1 1>
L(
(B,xz) - 21
(1)
2n
i=1

---

We make no assumption on the number of samples nor the dimension d. The only assumption we make on the data throughout the paper that the inputs (Z1,...,, F.n) are in general position. In order to state this assumption, let X E 12axd be the feature matrix whose ith row is I, and let ē IR" be its jth column for j E [d]. A Assumption I (General position), For any k S min(n, d) and arbitrary signs .i,..., oK E (-1,1), the affine span of any k points "1 , ,x. jr. does not contain any element of the set {+00,, # :..........
This assumption slightly technical but is standard the Lasso literature [47]. Note that it is not restrictive it is almost surely satisfied when the data is drawn from continuous probability distribution [47, Lemma 4]. Letting S = arg ming L(3) denote the affine space of solutions, Assumption ensures that the minimisation problem min = ||: has a unique minimiser which we denote B% and which corresponds to the minimum -norm solution.
2-layer diagonal linear network. In an effort to understand the training dynamics of neural networks, we consider a 2-layer diagonal linear network which corresponds to writing the regression vector B as
B u O where w = (u, v) 2d
(2)
This parametrisation can be interpreted as simple neural network x + (u, (diag(v))) where u are the output weights, the diagonal matrix diag(v) represents the inner weights, and the activation a is the identity function. We refer to = (u, v) E R22d as the weights and to B = Ô E Bd as the prediction parameter. With the parametrisation (2), the loss function F over the parameters = (u, v) E Id2d is defined as:
F(w) = (( 2n Σ (w y²)
1
Though this reparametrisation is simple, the associated optimisation problem is non-convex and highly non-trivial training dynamics already occur. The critical points of the function F exhibit very particular structure, as highlighted in the following proposition proven in Appendix B.
Proposition 1. All the critical points we of F which are not global minima, i.e., V F(w.)) = 0 and F(w2)) > min F(w),, ), are necessarily saddle points (i.e., not local extrema). They map to parameters B. = Uh C Ue which satisfy (3cl V (B(.))= = O and:
Be E arg min
L(B)
=|0=0 for igsupp(8.)
where supp({.) = {ie e [4] A.[i] # 0} corresponds to the support of Be-
The optimisation problem in Eq. (4) states that the saddle points of the train loss correspond to sparse vectors that minimise the loss function L over its non-zero coordinates. This property already shows that the saddle points possess interesting properties from a learning perspective. In the following we loosely use the term of 'saddle' to refer to points 3. Rd solution of Eq. (4) that are not saddles of the convex loss function L. We adopt this terminology because they correspond to points w. E 2d that are indeed saddles of the non-convex loss F.
Gradient Flow and necessity of "accelerating" time. We minimise the loss F using gradient flow: (5)
dw, = Fw,
initialised at uo = /2a1 E R with > O, and 8o - 0 Rdd, This initialisation results in 30 = 0 e d independently of the chosen weight initialisation scale a. We denote 3 == uf @ of the prediction iterates generated from the gradient flow to highlight its dependency on the initialisation scale a.. The origin 0 E 2d is critical point of the function F and taking the initialisation a + therefore arbitrarily slows down the dynamics. In fact, it can be easily shown for any fixed time t, that (uf uf - 0 as a - O, indicating that the iterates are stuck at the origin. Therefore if we restrict ourselves to finite time analysis, there is no hope of exhibiting the observed saddle-to-saddle behaviour. To do so, we must find an appropriate bijection [, in R20 which "accelerates" time (i.e. To (4)= + oo for all f) and consider the accelerated iterates 3 (t) which can escape the saddles. Finding this bijection becomes very natural once the mirror structure is unveiled.
a-
We point out that the trajectory of 0 exactly matches that of another common parametrisation 3... == {we w2 ). with initialisation w+.0 w-.0 al.
3

---

2.2 Leveraging the mirror flow structure
While the iterates (wf),, ) follow gradient flow on the non-conves loss F, is shown in [5] that the iterates 3r follow a mirror flow on the convex loss L with potential di, and initialisation Pi=0 0:
dV ( (g V ( )dt,
where da is the hyperbolic entropy function [21] defined as:
& (B)
BBarcsinhh -
VB BP + az + +
Unveiling the mirror flow structure enables to leverage convex optimisation tools to prove convergence of the iterates to a global minimiser 3% as well as simple proof of the implicit regularisation problem it solves. As shown by Woodworth al. [50], in the overparametrised setting where d and where there exists an infinite number of global minima, the limit S is the solution of the problem:
8 = arg min (3).
(8)
(
Furthermore, a simple function analysis shows that da behaves as a rescaled & -norm as a goes to 0, meaning that the recovered solution B* converges to the minimum & no-mr solution 37 arg y.= ||@||| as goes to 0 (see [49] for precise rate). To bring light the saddle-to- saddle dynamics which occurs as we take the initialisation to 0, we make substantial use of the nice mirror structure from Eq. (6).
Appropriate time rescaling. To understand the limiting dynamics of 87, it is natural to consider the limit a - 0 in Eq. (6). However, the potential Φa, is such that & (B) In(1/a)]|31] for small and therefore degenerates as O. Similarly, for 3 * O, (B)]I=
O. The formulation from Eq. (6) thus not appropriate to take the limit a - We can nonetheless obtain meaningful limit by considering the opportune time acceleration (t)(t) In(1/a) t and looking at the accelerated iterates
3 = FF,()) (m(/aa)
Indeed, simple chain rule leads to the "accelerated mirror flow": d VV - In VL dt. The accelerated iterates (g.T) )e follow mirror descent with a rescaled potential:
aVo. (,,) - (L(
where
Pas
(10)
In (1/a)
with 3.- 0 and where da is defined Eq. (7). Our choice of time acceleration ensures that the [|]11
rescaled potential &. is non-degenerate as the initialisation goes to 0 since &. a-
3 Intuitive construction of the limiting flow and saddle-to-saddle algorithm
In this section, we aim to give a comprehensible construction of the limiting flow. We therefore choose provide intuition over pure rigor, and defer the full and rigorous proof to the Appendix E. The technical crux of our analysis is to demonstrate the existence of a piecewise constant limiting process towards which the iterates 3r converge to. The convergence result is deferred to the following Section In this section we assume this convergence and refer to this piecewise constant limiting process as (B9) )- Our goal is then to determine the jump times (f1...., tp) as well the saddles 3p) which fully define this process.
To do so, it is natural to examine the limiting equation obtained when taking the limit 0 in Eq. (10). We first turn to its integral form which writes:
VL(3g)ds (..)
(1I)

---

Provided the convergence of the flow 3rd towards 3 the left hand side of the previous equation
converges to - So v ( For the right hand side, recall that (B) " || therefore
natural to expect the right hand side of Eq. (11) to converge towards an element of 0| ll1, where we recall the definition of the subderivative of the & -norm as:
0||l1|== = {1} if 3> 3>0, 0,
{-1} if <<0,
[-1,1] if 3 3=
The arising key equation which must satisfy the limiting process 3o is then, for all 0:
A L( E a11,;]11.
(12)
We show that this equation uniquely determines the piecewise constant process 3 by imposing the number of jumps p. the jump times as well as the saddles which are visited between the jumps. Indeed the relation described Eq. (12) provides restrictive properties that enable to construct 3 To state them, let 9t = S v L ds and notice that it is continuous and piecewise linear since 3 is piecewise constant. For each coordinate E [d]. it holds that:
(K1) St [ E [-1,1] (K3)
s = = B 2 0 and 8 = = 5 8e & (-1,1) = (K4)
(K2)
3 > 0 [ and 3 [1] < 0
+ s --1
To understand how these conditions lead to the algorithm which determines the jump times and the visited saddles, we present a 2-dimensional example for which we can walk through each step. The general case then naturally follows from this simple example.
3.1 Construction of the saddle-to-saddle algorithm with an illustrative 2d example.
and data matrix X E 2 such that X ((1, 0.2), (0.2, 0.2)). We consider 3 = (-0.2, 2) R² and outputs y = X This setting is such that the loss L has 3 as its unique minimum and L(3*) = O. Furthermore the non-convex loss F has 3 saddles which map to: $..0 = (0, 0) arg ming. L(3), B (0.2,0) arg min] L(B) and Be,2 = (0, 1.6) arg mi L(B). The loss function L is sketched in Figure 2 (Left). Notice that by the definition of Se,1 and Be,2, the gradients of the loss at these points orthogonal to the axis they belong to. When running gradient flow with a small initialisation over our diagonal linear network, obtain the plots illustrated Figure (Middle and Right). We observe three jumps: the iterates jump from the saddle at the origin to fe, at time 41, then to Be,z at time le and finally to the global minimum 8 at time 13.
Let us consider n =
Accelerated iterates 36
9.
Sketch of the loss
8
82
1p
13 Time
())
V ((8..))
[|]] +3
Bo
12
Time
Figure 2: Left: Sketch of the 2d loss. Middle and right: Outputs of gradient flow with small initialisation scale: the iterates are piecewise constant and s; is piecewise lincar across time. We refer to the main text for further details.
Let us show how Eq. (12) enables us to theoretically recover this trajectory. simple observation which we will use several times below is that for any such that f constant equal to 3 over the time interval (t, f'), the definition of enables to write that se st (t' - t) L())..
5

---

Zeroth saddle: The iterates are at the saddle at the origin: P. Bu = Se.0 and therefore
8, = (t))) Our key equation Eq. (12) is verified since = - a| Boll= -- 1la. However the iterates cannot stay at the origin after time 1 ==
which corresponds to the time at which the first coordinate of s; hits +1: St, [1] = 1. If the iterates stayed at the origin after would be violated. The iterates must hence jump.
11 (K1) for
First saddle: The iterates can only jump to a point different from the origin which maintains Eq. (12) valid. We denote this point 31. Notice that:
St, [2] = -1 [2()))(2] E (-1, 1) and since o, is continuous, we must have 31 = (K3)
St, [1] = and hence for 2 L, sx[1] = 1 - (L- LL We cannot have [L(B:)[1] < 0 (K I). and neither VL( [[] > 0 since otherwise s.[1] E (-1,1) and B1 = 0 (K3)
The two conditions [1 = and ( [[] = uniquely defines 31 as equal to 3.. We now want to know if and when the iterates jump again. We saw that s, [1] remains at the value +1. However since 31 not global minimum, VL(3) of 0 and se[2] hits +1 at time lg defined such that 1. The iterates must jump otherwise (K1) would break.
-(4 (B3) + (42 4 ()V((3))))
The iterates cannot jump to 3* yet! As the second coordinate of the iterates can activate, one could expect the iterates to be able to jump to the global minimum. However note that 8t is continuous function and that 8t, is equal to the vector (1, 1). the iterates jumped to the global minimum, then the first coordinate of the iterates would change sign from +0.2 to -0.2. Due to (K4) this would lead 8 jumping from +1 to 1,, violating its continuity.
Second saddle: We denote as 82 the point to which the iterates jump. St, is now equal to the vector
(1, 1) and therefore (i) 82 2 0 (coordinate-wise) from (K2 and K3) and the continuity of s. Since 8, Sta (t - 12) (S we must also have: (ii) ( 2 0 from (K1) (iii) for i E {1,2). if
[2[1] + 0 then (B = from (K4). The three conditions (i), (ii) and (iii) precisely correspond
to the optimality conditions of the following problem:
arg min L(3). ||]200002|20
The unique minimiser of this problem 3,,,, hence 32 = Bc.2. which means that the first coordinate deactivates. Similar to before, (K1) is valid until the time 13 at which the first coordinate of St, (t- 12 (B2)) reaches -1 due to the fact that (L( >
Global minimum: We follow the exact same reasoning as for the second saddle. We now have Stg equal to the vector (-1,1) and the iterates must jump to a point A3 such that (i) 3g[1] < 0, 8,[2] > 0 (K2 and K3), (ii) [L(3))[1] < 0. (33)) > 0 (K1), (ii)) for i E (1, if [i] + 0 then [( = (K4). Again, these are the optimality conditions of the following problem:
arg min L(B). 0[]
3* is the unique minimiser of this problem and 833 Br. For / 2 13 we have 8, = Stg and Eq. (12) is satisfied for all following times: the iterates do not have to move anymore.
3.2 Presentation of the full saddle-to-saddle algorithm
We can now provide the full algorithm (Algorithm 1) which computes the jump times (f2...., tp) and saddles (5og 0, B1, ........... (p)) as the values and vectors such that the associated piecewise constant process satisfics Eq. (12) for all t. This algorithm therefore defines our limiting process 3
Algorithm in words. The algorithm is concise representation of the steps we followed in the previous section to construct go. We explain each step in words below. Starting from k = 0, assume we enter the loop number & at the saddle 3x computed in the previous loop:
The set A contains the set of coordinates "which are unstable": by having a non-zero derivative, the loss could be decreased by moving along each one of these coordinates and one of these coordinates will have to activate.

---

Algorithm 1: Successive saddles and jump times lima-n0.3 -0
Initialise: (t, s) 0,); while v ( # 0 do
{ E [d], VL(3)() + 0}
A - imf (6 > 0.t. e A, s(i) (VL((3 =13
(1, 8) - (t+
A VL(3))
3 arg min T(3) where B E | Rdd s.t.
A,20 if s0)=+1
8. if s()=-1
}
8,=0 if ((1)(-111)
end
Output: Successive values B and
The time gap As corresponds to the time spent at the saddle 3t. It is computed as being the elapsed time just before (K1) breaks if the coordinates do not jump.
We update 1s+1 4 + As and 1 = 8% A& L((e): 44+1 corresponds to the time at which the iterates leave the saddle 33 and 84++1 constrains the signs of the next saddle 3x+1
The solution Bk+1 of the constrained minimisation problem is the saddle to which the flow jumps to time f4+1- The optimality conditions of this problem are such that Eq. (12) is maintained for & 2 1++1-
Various comments on Algorithm 1. First we point out that any solution 3. of the constrained min- imisation problem which appears in Algorithm also satisfies B. arg m for igsupp(8.) L(3) as in Eq. (4): the algorithm hence indeed outputs saddles expected. Up until now we have never checked whether the algorithm's constrained minimisation problem has a unique minimum. This is crucial otherwise the assignment step would be ill-defined. Showing the uniqueness is non-trivial and is guaranteed thanks to the general position Assumption I on the data (see Proposition 7 in Appendix D.1). In this same proposition, min (24, EE= (()) steps, that the loss strietly decreases at each step and that the final output 3p the minimum -n-orrm solution. These last two properties are expected given the fact that the algorithm arises as being the limit process of 3 which follows the mirror flow Eq. (10).
also show that the algorithm terminates in at most
Links with the LARS algorithm for the Lasso. Recall that the Lasso problem [46, 15] is formulated as:
B arg min L(B) + 1113111-
(13)
BERd
The optimality condition of Eq. (13) writes - VV(33) E A011,3111 Now notice the similarity with Eq. (12): the two would be cquivalent with A = 1/t if the integration on the left hand side the whole trajectory but only the final iterate, in which case
of Eq. (12) did not average L )ds -1 VL())). Though the difference is small, the trajectories of our limiting trajectory 8 and the lasso path (5)) are quite different: one has jumps, whereas the other is continuous. Nonetheless, the construction of Algorithm shares many similarities with that of the Least Angle Regression (LARS) algorithm [19] (originally named the Homotopy algorithm [39]) which is used to compute the Lasso path. A notable difference however is the fact that each step of our algorithm depends on the whole trajectory through the vector whereas the LARS algorithm can be started from any point on the path.
3.3 Outputs of the algorithm under RIP and gap assumption on the data.
Unlike previous results on incremental learning, complex behaviours can occur when the feature matrix ill designed: several coordinates can activate and deactivate at the same time (see Appendix for various cases). However, if the feature matrix satisfies the 2r-restricted isometry property (RIP) [14] and there exists an r-apas solution 8*, the visited saddles can easily approximated using Algorithm 1. We provide the precise characterisation below.
7

---

Sparse regression with RIP and gap assumption. (RIP) Assume that there exists an r-sparse vector 8 such that y; (0,,8)) Furthermore we assume that the feature matrix X R satisfies the 2r-restricted isometry property with constant v2- < 1/2: i.e. for all submatrix X, where we extract any 2r columns of X, the matrix X X,/n of size 8 has all its eigenvalues in the interval [1 - -,,1+ ē]. (Gap assumption) Furthermore we assume that the r-sparse vector 3 has coordinates which have a "sufficient gap'. W.l.o.g g we write 3
.5,00.... 0) with 18112 2 | 0 and we define X == [i 13 D) 2 0 which corresponds to the smallest gap between the entries (3 We assume that 5 8 1| x/2 and we let == 5é.
A classic result from compressed sensing (see Candes [13, Theorem 1. 1.2)) is that the 2r-restricted isometry property with constant v2 1 ensures that the minimum fg-minimisation problem has unique r-sparse solution which is 3 This means that Algorithm 1 will have 3 as final output and the following proposition shows that we can precisely characterise each of its outputs when the data satisfies the previous assumptions.
Under the restricted isometry property and the gap assumption stated right above, Algorithm I terminates in r r-loops and outputs:
Proposition
31 (3: (.).0...... ..... 0)
with
[1[1] E [3] =||3 =||
[,2[1] E [8] - -=| 1. =||
82 = (32[4], (2,11,,,22100.. 2,..).......0
with
[2[2]] E [8] - =|| + +||
3r-1 = (3,-1[1], [1]...., B 10,-111,00 11,0, 0)........
with B,-1 E [8] == =13"11 + +
Br 3* (Bi..... ......... 3r, 0, 0,....0), 0):
at times .1,..., fy such that t; E
| |-- and where ||||| denotes the & norm.
Informally, this means that the algorithm terminates in exactly r loops and outputs jump times and saddles roughly equal to 4 = 1/|,8|| and 3, = (.- 87 O..... 0). Therefore, in simple settings, the support of the sparse vector is learnt a coordinate at a time, without any deactivations. We refer to Appendix D.2 for the proof.
4 Convergence of the iterates towards the process defined by Algorithm 1
We are now fully equipped to state our main result which formalises the convergence of the accelcrated iterates towards the limiting process 8 which we built in the previous section.
Theorem 2. Let the saddles (Bo = 0, .1,,1..,,,,, .p...., Bi, and jump times (to = 0, t,, ... kp)
be the outputs of Algorithm 1 and let (3t)) be the piecewise constant process defined as follows:
(Saddles)
3 =Bx
for I E (l,, 1x41) and 0 < k S p, 1p+1 = +oc.
The accelerated flow (3+), defined in Eq. (9) uniformly converges towards the limiting process (3P)) on any compact subset of TR stadtt....,,t.
Convergence result. We recall that from technical point of view, showing the existence of a limiting process lim,--o 3r is the toughest part. Theorem 2 provides this existence as well as the uniform convergence of the accelerated iterates towards 3 over all closed intervals of TR which do not contain the jump times. We highlight that this is the strongest type of convergence we could expect and uniform convergence over all intervals of the form [0, T] is impossible given that the limiting process
3 is discontinuous. In Proposition 3, we give an even stronger result by showing graph convergence of the iterates which takes into account the path followed between the jumps. We also point out that we can easily show the same type of convergence for the accelerated weights पā := w ( Indeed, using the bijective mapping which links the weights w, and the predictors 3r (see Lemma in Appendix C), we immediately get that the accelerated weights (i²", 5²) uniformly converge towards
the limiting process (v 1/13%, sign(8)) (8') (101)) any compact subset of RRo' (4,,...,pp)
8

---

Estimates for the non-accelerated iterates S.. We point out that our result provides no speed of convergence of 3 towards 8". We believe that non-asymplotic result is challenging and leave as future work. Note that we experimentally notice that the convergence rate quickly degrades after each saddle. Nonetheless, we can still write for the non-accelerated iterates that + O. Hence, for small enough the iterates ff are roughly equal until time 1 in(1/a) and the minimum é 1-nor interpolator is reached time tp -I((//)).. Such precise estimate of the global convergence time is rather remarkable and goes beyond classical Lyapunov analysises which only leads to ((3 S In(1/o)/t (see Proposition 4 in Appendix C).
38 3 1t/m((1/a) 51/1m(1/a)
Natural extensions of our setting. More general initialisations initialisations of the form ut=0 = quo E R lead to the exact same result as it is shown in [50] (Discussion after Theorem that the associated mirror still converges to the fn-rrmm Initialisations of the form [u==o] = a where k; > 0, lead to the associated potential converging towards weighted nnorrmm and one should modify Algorithm 1 by accordingly weighting (((3) in the
easily be dealt with. For instance,
algorithm. Also, deeper linear architectures of the form 3 = wD wD as in [50] do not change our result as the associated mirror still converges towards the l norro Though we only consider the square loss in the paper, we believe that all our results should hold for any loss of the type L(9) = Σm= Elys: (1) where for all y E IR, K(y, .) is strictly convex with unique minimiser at In fact, the only property which cannot directly be adapted from our results is showing the uniform boundedness of the iterates (see discussion before Proposition 5 in Appendix C).
4.1 High level sketch of proof of 3m + 30 which leverages an arc-length parametrisation
In this section, we give the high level ideas concerning the proof of the convergence foo + 3 given in Theorem 2. A full and detailed proof can be found in Appendix E. The main difficulty stems from the non-continuity of the limit process 3 To circumvent this difficulty, clever trick which we borrow to [18, 36) is to "slow-down" time when the jumps occur by considering an arc-length parametrisation of the path. We consider the Rz0 arclength bijection 7" and leverage define the 'appropriately slowed down' iterates 3 as:
= and ((1)=1+ f f'liãcldds.
3
3 (r)
where
This time reparametrisation has the fortunate but crucial property of leading to 80 (r) |1 by simple chain rule, which means that the speed of (ßę), is uniformly upperbounded by 1 independently of a. This behaviour is in stark contrast with the process (3,)), which has speed which explodes at the jumps. This change of time now allows us use Arzela-Ascoli's theorem to extract a subsequence which uniformly converges to limiting process which we denote B. Importantly, 3 enables to keep track of the path followed between the jumps as we show that its trajectory has two regimes:
Connections: 3,
LV 3- (VL(())
Saddles: B, 3r
3+
The process/ 3 is illustrated on the right: the red curves correspond to the paths which the iterates follow during the jumps. These paths are called heteroclinic orbits in the dynamical systems literature [31, 3]. To prove Theorem 2, we can map back the convergence of 3 to show that of 3". Moreover from the convergence 3r- 9 we get a more complete picture of the limiting dynamics of 3 as it naturally implies the convergence of the graph of the iterates (3,)), , converges towards that (3,),, ),. The graph convergence result is formalised in this last proposition.
32
Connections
(8-)
11
Proposition 3. For all T lp the graph of the iterates (gg) converges to that of (3+)+
dist(130 hST, (8r3r20)
(Hausdorff distance)
a+

---

5 Further discussion and conclusion
Link between incremental learning and saddle-to-saddle dynamics. The incremental learning phenomenon and the saddle-to-saddle process are often complementary facets of the same idea and refer to the same phenomenon. Indeed for gradient flows duy- = F(e jdt, fixed points of the dynamics correspond to critical points of the loss. Stages with little progress in learning and minimal movement of the iterates necessarily correspond to the iterates being in the vicinity of critical point of the loss. It turns out that in many settings (linear networks [30], matrix sensing [8. 4 41D. critical points
necessarily saddle points of the loss (if not global minima) and that they have very particular structure (high sparsity, low rank, etc.). We finally note that an alternative approach to realising saddle-to-san -o-ddee dynamics is through the perturbation of the gradient flow by a vanishing noise as studied in [6].
Characterisation of the visited saddles. A common belief is that the saddle-to-saddle trajectory can be found by successively computing the direction of most negative curvature of the loss (i.e. the eigenvector corresponding to the most negative eigenvalue) and following this direction until reaching the next saddle [26]. However this statement cannot be accurate as it is inconsistent with our algorithm in our setting. In fact, it can be shown that this algorithm would match the orthogonal matching pursuit (OMP) algorithm [42, 17] which does not necessarily lead to the minimum f--norm interpolator. In [7], which the closest to our work and the first to prove convergence of the iterates towards piece-wise constant process, the successive saddles are entirely characterised and connected to the Lasso regularisation path in the underparameterised setting. Recently, [9] extended the diagonal linear network setting to diagonal parametrisations of the form fuow. but at the cost of stronger assumptions on the trajectory.
Adaptive Inverse Scale Space Method. Following the submission of our paper, we were informed that Algorithm had already been proposed and analysed in the compressed sensing literature. Indeed it exactly corresponds to the Adaptive Inverse Scale Space Method (aISS) proposed in [1]]. The motivations behind its study are extremely different from ours and originate from the study of Bregman iteration [12, 40, 52] which is an efficient method for solving & related minimisation problems. The so-called inverse scale space flow which corresponds to Eq. (12) in our paper can be seen as the continuous version of Bregman iteration. As in our paper, [11] show that this equation can be solved through an iterative algorithm. We refer to [51, Section 2] for further details. However we did not find any results in this literature concerning the uniqueness of the constrained minimisation problem due to Assumption 1, nor on the maximum number of iterations, the behaviour under RIP assumptions and the maximum number of active coordinates.
Subdifferential equations and rate-independent systems. As in Eq. (12), subdifferential inclusions of the form L((,)) E ar (l..) for non-differential functions have been studied by Attouch et al. [4] but for strongly convex functionn h. In this case, the solutions continuous and do not exhibit jumps. On another hand. [18, 36, 37] consider so-called rate-independer systems of the form Et, q:) E @h((e)) for l-homogeneous dissipation potentials h. Examples of such systems ubiquitous in mechanics and appear in problems related to friction, crack propagation, elastoplasticity and ferromagnetism name a few [35, Ch. 6 for survey]. As in our case, the main difficulty with such processes is the possible appearance of jumps when the energy E is non-convex.
Conclusion. Our study examines the behaviour of gradient flow with vanishing initialisation over diagonal linear networks. We prove that leads to the flow jumping from saddle point of the loss to another. Our analysis characterises each visited saddle point as well as the jumping times through an algorithm which is reminiscent of the LARS method used in the Lasso framework. There are several avenues for further exploration. The most compelling one is the extension of these techniques to broader contexts for which the implicit bias of gradient flow has not yet fully been understood.
Acknowledgments. S.P. would like to thank Loucas Pillaud- Vivien for introducing him to this beau- tiful topie and for the many insightful discussions. S.P. also thanks Quentin Rebjock for the many helpful discussions and Johan S. Wind for reaching out and providing the reference of [11]. The au- thors also thank Jérôme Bolte for the discussions concerning subdifferential equations, Aris Daniilidis for the reference of [32], as well as Aditya Varre and Mathieu Even for proofreading the paper.
10

---

References
[1] Emmanuel Abbe, Enric Boix Adsera, and Theodor Misiakiewicz. Sgd learning on neural net- works: leap complexity and saddle-to-saddle dynamics, In The Thirty Sixth Annual Conference on Learning Theory, pages 2552-2623, PMLR, 2023.
[2] Sanjeev Arora, Nadav Cohen, Wei Hu, and Yuping Luo. Implicit regularization in deep matrix factorization. Advances in Neural Information Processing Systems, 32, 2019.
[3] Peter Ashwin and Michael Field. Heteroclinic networks in coupled cell systems. Arch. Ration. Mech. Anal., 148(2):107-143, 1999.
[4] H. Attouch, Bolte, Redont, and M. Teboulle. Singular Riemannian barrier methods and cradient-projectton dynamical systems for constrained optimization. Optimization, 53(5-6): 435 454, 2004.
[5] Shahar Azulay, Edward Moroshko, Mor Shpigel Nacson, Blake E Woodworth, Nathan Srebro, Amir Globerson, and Daniel Soudry. On the implicit bias of initialization shape: Beyond infinitesimal mirror descent. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 468 477. PMLR, 18-24 Jul 2021.
[6] Yuri Bakhtin. Noisy heteroclinic networks. Probab. Theory Related Fields, 150(1-2):1-42, 2011.
[7] Raphaël Berthier. Incremental learning in diagonal linear networks. arXiv:2208. 14673, 2022.
arXiv preprini
[8] Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Srebro. Global optimality of local search for low rank matrix recovery. In Advances Neural Information Processing Systems, volume 29,
2016.
[9] Enric Boix-Adsera, Etai Littwin, Emmanuel Abbe, Samy Bengio, and Joshua Susskind. Trans- formers learn through gradual rank increase. arXiv preprint urXiv:2306.07044 2023.
[10] Etienne Boursier, Loucas Pillaud-Vivis and Nicolas Flammarion. Gradient flow dynamics of shallow reLU networks for square loss and orthogonal inputs. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022.
[11] Martin Burger, Michael Möller, Martin Benning, and Stanley Osher. An adaptive inverse scale space method for compressed sensing. Mathematics of Computation, 82(28 (:2281):20 0:269-2999 2013.
[12] Jian LannFeng Cai. Stanley Osher, and Zuowei Shen. Split bregman methods and frame based image restoration. Multiscale modeling & simulation. 8(2):337-369, 2010.
[13] Emmanuel J Candes. The restricted isometry property and its implications for compressed sensing. Comptes rendus mathematique, 346(9-10):589 592, 2008
[14] E. Candès, Romberg, and Tao. Stable signal recovery from incomplete and inaccurate measurements. Communications on Pure and Applied Mathematics, 5908): 2006.
[15] Scott Shaobing Chen, David L Donoho, and Michael A Saunders. Atomic decomposition by basis pursuit. SIAM review, 43(1): 2001.
[16] Lénaic Chizat and Francis Bach. Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss. In Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pages 1305-1338. PMLR, 09-12 Jul 2020.
[17] Geoff Davis, Stephane Mallat, and Marco Avellaneda. Adaptive greedy approximations. Constructive approximation, 13:57-98, 1997.
[18] Messoud A. Efendiev and Alexander Mielke. On the rate-independent limit of systems with dry friction and small viscosity. J. Convex Anal., 13(1):151-67, 2006.
11

---

[19] Bradley Efron, Trevor Hastie, lain Johnstone, and Robert Tibshirani. Least angle regression. 2004.
[20] Mathieu Even, Scott Pesme, Suriya Gunasekar, and Nicolas Flammarion. (s)gd over diagonal linear networks: Implicit regularisation, large stepsizes and edge of stability. arXiv preprini TrXiv:2302.08982. 2023.
[21] Udaya Ghai, Elad Hazan, and Yoram Singer. Exponentiated gradient meets gradient descent. In Aryeh Kontorovich and Gergely Neu, editors, Proceedings of the 31st International Conference on Algorithmic Learning Theory, volume 117 of Proceedings of Machine Learning Research, pages 386-407. PMLR, 08 Feb-11 11 Feb 2020.
[22] Gauthier Gidel, Francis Bach, and Simon Lacoste-Julien. Implicit regularization of discrete gradient dynamics in linear neural networks. Advances Neural Information Processing Systems, 32, 2019.
[23] Daniel Gissin, Shai Shalev-Shwartz, and Amit Daniely. The implicit bias of depth: How incre- mental learning drives generalization. In International Conference on Learning Representations, 2020.
[24] Suriya Gunasekar, Blake E Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Srebro. Implicit regularization in matrix factorization. In Advances in Neural Information Processing Systems, volume 30, 2017.
[25] Jeff Z HaoChen, Colin Wei, Jason Lee, and Tengyu Ma. Shape matters: Understanding the implicit bias of the noise covariance. In Conference on Learning Theory, pages 2315-2357. PMLR, 2021.
[26] Arthur Jacot, François Ged, Berfin Şimşek, Clément Hongler, and Franck Gabriel. Saddle-to- saddle dynamics in deep linear networks: Small initialization training, symmetry, and sparsity. arXiv preprint arXiv:2 106. 15933, 2021.
[27] Liwei Jiang, Yudong Chen, and Lijum Ding. Algorithmic regularization in model-free over- parametrized asymmetric matrix factorization. arXiv preprint arXiv:2203.02839, 2022.
[28] Jikai Jin, Zhiyuan Li, Kaifeng Lyu, Simon Du, and Jason D Lee. Understanding incremen- tal learning of gradient descent: A fine-grained analysis of matrix sensing. arXiv preprini arXiv:2301. 15500, 2023.
[29] Dimitris Kalimeris, Gal Kaplun, Preetum Nakkiran, Benjamin Edelman, Tristan Yang, Boaz Barak, and Haofeng Zhang. Sgd on neural networks learns functions of increasing complexity. Advances in neural information processing systems, 32, 2019.
[30] Kenji Kawaguchi. Deep learning without poor local minima. In Advances in Neural Information Processing Systems, volume 29, 2016.
[31] M. Krupa. Robust heteroclinic cycles. J. Nonlinear Sci., 7(2):129-176, 1997.
[32] Krzysztof Kurdyka. On gradients functions definable in o-minimal structures. Ann. Inst. Fourier (Grenoble), 48(3):769-788 1998.
[33] Zhiyuan Li, Yuping Luo, and Kaifeng Lyu. Towards resolving the implicit bias of gradient descent for matrix factorization: Greedy low-rank learning. In International Conference on Learning Representations, 2021.
[34] Julien Mairal and Bin Yu. Complexity analysis of the lasso regularization path. arXiv preprint 10X7v:100..0079 2012.
[35] Alexander Mielke. Evolution of rate-independent systems. Evolutionary equations, 2:461-559, 2005.
[36] Alexander Mielke, Ricearda Rossi, and Giuseppe Savaré. Modeling solutions with jumps for rate- inte-independent systems metric spaces. Discrete Contin. Dyn. Syst., 25(2):585-615, 2009.
12

---

[37] Alexander Mielke, Riccarda Rossi, and Giuseppe Savaré. Variational convergence of gradient flows and aateiindeenndent evolutions in metric spaces. Milan Journal of Mathematics, 80: 381-410, 2012.
[38] Behnam Neyshabur. Implicit regularization in deep learning, arXiv preprini arXiv: 2017.
[39] Michael R Osbore,, Brett Presnell, and Berwin A Turlach. A new approach to variable selection in least squares problems. IMA journal of numerical analysis, 20(3):389 403, 2000.
[40] Stanley Osher, Martin Burger, Donald Goldfarb, Jinjun Xu, and Wotao Yin. An iterative regularization method for total variation-based image restoration. Multiscale Modeling & Simulation, 4(2):460-489 2005.
[41] Dohyung Park, Anastasios Kyrillidis, Constantine Carmanis, and Sujay Sanghavi. Non-square matrix sensing without spurious local minima via the Burer-Monteiro approach. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, volume 54 of Proceedings of Machine Learning Research, pages 65-74. PMLR, 20-22 Apr 2017.
[42] Yagyensh Chandra Pati, Ramin Rezaïfarr and Perinkulam Sambamurthy Krishnaprasad. Or- thogonal matching pursuit: Recursive function approximation with applications to wavelet decomposition. In Proceedings of 27th Asilomar conference on signals, systems and computers, pages 40-44. IEEE, 1993.
[43] Scott Pesme, Loucas Pillaud-Vivien, and Nicolas Flammarion. Implicit bias of sgd for diag- onal linear networks: a provable benefit of stochasticity. In Advances in Neural Information Processing Systems, 2021.
[44] Noam Razin, Asaf Maman, and Nadav Cohen. Implicit regularization in tensor factorization. In International Conference on Machine Learning, pages 8913-8924. PMLR, 2021.
[45] Andrew M Saxe, James L McClelland, and Surya Ganguli. A mathematical theory of semantic development in deep neural networks. Proceedings of the National Academy of Sciences, 116 (23): 2019.
[46] Robert Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society: Series B (Methodological), 58(1):267-288, 1996.
[47] Ryan J. Tibshirani. The lasso problem and uniqueness. Electron. J. Stat., 7:1456-1490, 2013,
[48] Tomas Vaskevicius, Varun Kanade, and Patrick Rebeschini, Implicit regularization for optimal sparse recovery. Advances in Neural Information Processing Systems, 32, 2019.
[49] Johan S Wind, Vegard Antun, and Anders C Hansen. Implicit regularization in ai meets gener- alized hardness of approximation in optimization-shann sharp results for diagonal linear networks. arXiv preprint arXhv:2307.074400 2023.
[50] 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 Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pages 3635-3673. PMLR, 09-12 Jul 2020.
[51] Yi Yang, Michael Möller, and Stanley Osher. A dual split bregman method for fast 11 minimiza- tion. Mathematics of computation, 82(284):2061 2085, 2013.
[52] W Yin, Osher, Goldfarb, and Darbon. Bregman iterative algorithms for l1-minimization with applications to compressed sensing: Siam journal on imaging sciences, 1, 143-168. LIST OF FIGURES, 2008
[53] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In International Conference Learning Representations, 2017.
13

---

Organisation of the Appendix.
Appendix A, we give the experimental setup and provide additional experiments.
2. In Appendix B, we prove Proposition and provide additional comments concerning the unicity of the minimisation problem which appears in the proposition.
3. In Appendix C, we provide some general results on the flow.
4. In Appendix D, we prove Proposition 2 and give standalone properties of Algorithm
5. In Appendix E, we explain in more detail the arc-length parametrisation explained in the main text as well as prove Theorem and Proposition 3.
6. In Appendix F, we provide technical lemmas which are useful to prove the main results.
14

---

A Experimental setup and additional: experiments, extension, related works.
Experimental setup and additional experiments. For each experiment we generate our dataset as = ( 3*) where 2; (0, H) for a a diagonal covariance matrix H and 3 is a vector of Fd Gradient descent is run with small step size and from initialisation uz=0 = /2a1 E R and
2t=0 for some initialisation scale 0.
Figure and Figure 4 (Left): (n, a) (10, 20, 0, 0,0) E RT.
(5, ), H la. 8*
Figure 4 (Right): (n,d,a)
(6,6,10-1)) H diag(1, (1, 10, 10, 10, 10) E R6x6 3 01, 0,0,0, E R.
Figure 3 (Left): (n, a1, a2) (7,2,10-1l) 100 10 1011100.-10 ) H = La. 3 = (10, 20) R?.
Figure 3 (Right): (n, a) (3,3,10 X is the square root matrix of the matrix
((20, 6, - 1.4), 26,2, 0.4), -.4,,,.000...112 3x3 3* (1,9, 10).
Accelerated iterates
3 fol1/
20
Accelerated iterates B P
10
$ę(1)
(2(2)
15
(1)
(3))
(2)
10
(1)
(2)
2-
0.0
0.2
0.1
0.6
0.8
1.0
10
2
10 1
10"
101
10a
Time
Time t
Figure 3: Left: Visualisation of the uniform convergence of 3 towards 3o as a + 0. =
10-100 100 < 02 10-10 Right: some cases, coordinates can activate at the same time. Note that the time axis is in log-scale for better visualisation.
Accelerated iterates 3y
Accelerated iterates 3 Pintt/03
20
(1)
(1)
(2)
(2)
15
(3)
(3)
10
(4)
(4)
Ac (5)
(5)
0.4
5
(6)
(6)
(7)
0.2
0
-5
0.0
0.2
0.4
0.6
0.8
2.5
5.0
12.5
15.0
Time E
Time
Figure 4: Complex dynamies occur. Left and right: Coordinates not monotonic and the number of active coordinates neither as several coordinates can deactivate at the same time. The piecewise constant process plotted in black is the limiting process 3 predicted by our theory.
15

---

B Proof of Proposition 1
Proposition All the critical points we of F which are not global minima, i.e. (F(w)) 0 and F(w2) > min F(w), are necessarily saddle points (i.e., not local extrema). They map to parameters Be ue C te which satisfy (3c (V)e)) and:
Be
arg min
T(B)
p[d==0 for igsupp(3.)
where supp(3.) {i 8. # 0} corresponds to the support of Be-
Proof. Non-existence maxima / non-global minima. This is simpler version of results which appear in [30]. for the sake of completeness we provide here a simple proof adapted to our setting. The intuition follows the fact that there existed local maximum non-global minimum for F then this would translate to the existence of local maximum non-global minimum for the convex loss L, which is absurd.
Assume that there exists a local maximum w* = (u","*) that for all that 3 = u @ x² is a local maximum of L. which is absurd.
v²), i.e. assume that there exists e >> 0 such (u, v) such that ||w w* w1125 F(w) F(w*). We show that this would imply
IRS is bijection with The mapping g (u, + (u v(2² - x2) from Rd x R2d + IRd inverse
: (B,a) + (Va2+ BB + a (3) 2 V + 32 a
(14)
Also notice that F(g (8,
( a)) = L(3) for all 3 and a. Now let É > 0 and let 3 Rd such that || - 111 غ, then for (u, v) =g- (B, a+) where a, ((u=)2 22+ have that:
[1u,, v) (u", w" 112 = 2/ @V( 32 Va + 3.2 =1l,
S 2118² - 80211
= 21[(B 8-)² + 2(3 30
< 21 +) - 3
< 2( + vdl ((o))
where the last inequality for E small enough. This means that L(3) F(w) S F(w*) L(3*) and 8 is local maximum of L. which is absurd.
The exact same proof holds show that there are local minima of F which are not global minima.
Critical points. The gradient of the loss function F writes:
F())
VL(3) σv) v
V. Fwo)
(v.F(w)
E R
Therefore (w.)) = 0 e 2dd implies that VL(3.) @ 8. = E Rdd Now consider such a 8, and let s3pp(3.) {i [d] such that (e( # 0} denote the support of 8.. Since [VL(3.)] 0 for i supp(B.). we can therefore write that
Be E arg min L(3).
0,=0 for (gsupp(02)
Furthermore we point out that since (f.) C [d]. there are at most 2d distinct sets supp(33). and therefore at most 2d values F(w.)= = L(3.), where we a critical point of F.
Additional comment concerning the uniqueness of arg ming, =0, o (suppp((() L(3).
16

---

We point out that the constrained minimisation problem (4) does not necessarily have unique solution, even when 3e a global solution. Though not required for any of our results, for the sake of completeness, we show here that under an additional mild assumption on the data, we can ensure that the minimisation problem (4) which appears in Proposition has a unique minimum when T(3)) > O. Under this additional assumption, there is therefore finite number of saddles Be- Recall that we let X E Rnxd be the feature matrix and (ă1..... Ra) be its columns. Now assume temporarity that the following assumption holds.
Assumption 2 (Assumption used just in this short section). Any subset of (ø1.... Fa) of size smaller than min(n, d) is linearly independent.
One can easily check that this assumption holds with probability soon the data drawn from a continuous probability distribution, similarly to [47, Lemma 4)). In the following, for subset Ç {i1..... 2x } [d]. we write Xę- ...,...... Fie) R (we extract the columns from X).
For vector B E I2 write B[E] (B,,.... ,,,)) and $[c (B.)egg We distinguish two different settings:
Underparametrised setting (n 2 d) in this case, for any { = fi...... } C [d] then 3* argmin L(3) is unique. Indeed we simply set the gradient to and notice that 8,00,igE
due to Assumption 2, there exists a unique solution, indeed f such that [c( (X. Xx y and [*
Overparametrised setting (d > n) Global solutions: arg min L(9) is an affine space spanned by the orthogonal of (z1,---, Tn) in IRd Since span(ā1, .... T.) R from Assumption 2, any 8 E arg min L(3) satisfies X3** = y and ((8*) = "Saddle points": now let B, E Rd be such that we can write 3e E arg (.s.ppp) L(B) and assume that L(3.)) >> 0 (i.c., not global solution), then: (1) 3e has at most non-zero entries, indeed if were not the case, then would necessarily belong to span( (esspp())ssupp(( due to the assumption on the data, and this would lead to L(B.) = 0, (2) therefore, similar to the underparametrised case, arg ming; = L(3) is unique, equal to 8., and we have that [c[c] = (X] Xg)- Xx y and [.(cC] 0 where { = supp(Be).
Thus, in both the underparametrised and overparametrised settings, the minimisation problem (4) appearing in Proposition has a unique minimum when L(3.) > 0 and Assumption 2 holds.
17

---

C General results on the iterates
In the following lemma we recall few results concerning the gradient flow Eq. (5):
dw FW;)dd
(15)
where F' is defined in Eq. (3) as:
F(w) = L(u = 2n
( - -1)
Lemma 1. For an initialisation uo 22, vo O, the flow w = (uf, vff from Eq. (15) is such that the quantity (u.)² - (2 is constant and equal to 2a²1. Furthermore us lug 2 and therefore from the bijection Eq. (14) have that:
" a² (3g)2+ +
= c V -a2 + (B3)) +
Proof. From the expression of Fww),, notice that the derivative of (uz)² (uft)2 is equal to 0 and therefore equal to its initial value.
Since (u (u (uf vt (uf elt) by continuity get that up + oz 0 and 2i uz > 0 and therefore ut > |/2
In this section we consider the accelerated iterates Eq. (9) which follow:
dv (V - V VL where
Ta In(1/a)
Ha
(16)
with 3:-0 O and where oa is defined Eq. (7).
Proposition 4. For all > O and minimum 3 aigging I(3), the loss values T.3gg) and the Bregman divergence D2,, (B+, Be)) are decreasing. Moreover
L(37) L(3*) 2a(3))
(17)
21
I ( 1' 3Rds) -((3) S (B(B²)
(18)
2t
T 33 = -3 V2 (30 < 0. Proof. The loss is decreasing since: a (B3)) vL(3g)
d Dj (8*, 3::) = ( [ 5*) - ((( - L(B")) (since L is the quadratic loss). de
therefore the Bregman distance is decreasing. We can also integrate this last equality from 0 to f, and divide by- -2t:
1
S' L(3 ds L(8t)= = D ,8* 0) Dū. (80) t
2t
ja (8*)
<
2t
Since the loss is decreasing we get that L(3g) L(8*)= <
and from the convexity of we
28
get that T. 7 fo Agds) I((3)) < (B*)
L
2
In the following proposition, we show that for a small enough, the iterates are bounded independently of a. Note that this result unfortunately only holds for the quadratic loss, we expect it to hold for
other convex losses of the type L(3) = + E. E(yi, (a,, B)) where f(y,-) -) is strictly convex has
unique root at y but we don't 't know how to show it. Also note that bounding the accelerated iterates 8 is equivalent to bounding the iterates 8 since 3
18

---

Proposition 5. For a < where depends on 32, the iterates B are bounded independently of
a:
| x0 S 3 11
Proof.
From Eq. (16), integrating and using that L is the quadratie loss, get:
Véh (B
- _ (y x =- - -8),
where we recall that X E R Bexd is the input data represented as matrix and where we denote the averaged iterate by 3 fo ds. Thus get
(38) 8*) = = n1
(3f B²) x X( 8*).
(19)
By convexity of o. we have da (Bt) - (3t) S Vo. (39) T(3; -3)). By the Cauchy-Schwarz
inequality, we also have (39 (*) T X T ( 8r) I [X -11)|||XX B-) Using
Proposition 4: [ " nºal (8*)/t and |X(3) 3*)1 noa (3*)/t we can further
bound the right hand side of Eq. (19) as
( - 88) s (8") (3r - B*) T X
Thus it yields
8. (, - 3. (3*) S 0. (B*).
From [50] (proof of Lemma in the appendix) we get that for
min (1, Vl (211
then:
(a) - 2
111111.
and for all cxp(-d/2):
d
(3) 2 |18|| 1n(1/a2)
||
which finally leads for
< on == min (1, / |18 |l,, 11) exp(_d/2))
to the result.
The following proposition shows that we can bound the path length of the flow for independently of a. Keep in mind that the path length of foo equivalent to that of 8o as the first is just an acceleration of the second: 3 [m(1/a)
Proposition 6. For ao where on is the same as in Proposition the path length of the iterates (8t) )220 is bounded independently of a >> 0:
|| ldt < C,
where does not depend on a. Hence the path length of the accelerated flow Bor is also bounded independently of a.
19

---

Proof. Having shown that the iterates 5f are bounded independently of a, it also implies that the iterates wi (u,, 24) are bounded following Lemma Since the loss + F(w) multivari- ate polynomial function, it is remialgebraie function and we can consequently apply the result of Kurdyka [32, Theorem 2] which grants that
| < <C,
where the constant only depends on the loss and on the bound on the iterates. We further use that B @ e + @ and I ④ v + o كا|ا ([([li||++|)))) using that u and v are bounded and || C2 ||قl|| using the equivalence of norms. Therefore fo f+*1 || < C' for some which independent of the initialisation scale
20

---

D Standalone properties of Algorithm
D.1 "Well-definedness" of Algorithm 1 and upperbound on its number of loops
Notice that this proposition highlights the fact that Algorithm 1 is on its own an algorithm of interest for finding the minimum & -norr solution in an overparametrised regression setting. We point out that the provided upperbound on the number of iterations is very crude and could certainly be improved. Proposition 7. Algorithm I well defined: at each iteration (i) the attribution of A is well defined as A < +o0, (ii) the constrained minimisation problem has unique solution and the attribution of the value of 3 is therefore well-founded. Furthermore, along the loops: the iterates 3 have at most non-zero coordinates, the loss is strictly decreasing and the algorithm terminates in at most arg min ||,81]1-
min (24, Σ (W) steps by outputring the minimum & fn-nrrm solution Big
BE ary min L
Proof. In the following. for the matrix X and for subset {fi...... in} C [d],
we write
)..) E R (we extract the columns from X). For vector B Rd we write X1 (fi
31 = -B,,.... ).
(1) The constrained minimisation problem has unique solution: we follow the proof of [47, Lemma 2]. Following the notations in Algorithm I, we define = {i E [d] | 1--=1p 1} and we point out that after k loops of the algorithm, the value of s is equal to 8 - (A (LIVL(()) + +..
As ( E span(x)..... T..). We can therefore write = X r for some r R..
Now assume that ker(X,) * (0). Then, for some i I, have मं Ejent CySr where ej E RR Without loss of generality, we can assume that / / {i} has at most n elements. Indeed, we can otherwise always find n elements I C 1 \ {i} such that T. = Ejei ejãj. Rewriting the previous equality, we get
S
Σ (,18)C)(($55.)
(20)
JERMO
Now by definitions of the set and of r, we have that (2,, = E (+1, -13 for any j E Taking the inner product of Eq. (20) with r, we obtain that 1 [)(A( Consequently, we have shown that if ker(Xr) * {0). then we necessarily have for some I,
Σ (3(ز,ر,) JER())
with Ejnn a₃ L, which means that ,nē; lies in the affine space generated by (syūg))erMM) This fact is however impossible due to Assumption (recall that without loss of generality we have that I \ {i} has at most n elements, and trivially less that d elements). Therefore X, is full rank, and Card( [) S n. Now notice that the constrained minimisation problem corresponds to arg min 2.2,,e4, ||v 1r Since X, is full rank, this restricted loss is strictly convex and the A,
constrained minimisation problem has unique minimum.
(2) A < +oo: Notice that the optimality conditions of
B = arg min - 3
8. 20,
0.=0,
are (i) 9 satisfies the constraints, (ii) if i e 1+ (resp I_) [- < 0 (resp L >
0) and (ii) if 3, & then [f) = 0. One can notice that condition (ii) ensures that at each iteration, for 8 < A Sk-1 JVL coordinate of the vector $k-1 - (VL(Bkk1) must necessarily hit 1, this value of 5 corresponds to Ak-
[, coordinate wise. Also, if L(3g-1) + 0, then
(3) The loss is strictly decreasing: Let J and Ir be the equicorrelation sets defined in the algorithm at step k k- and k, and f1-1 and 3g the solutions of the constrained minimisation problems. Also, let ig be the newly added coordinate which breaks the constraint at step & (which we assume to be unique for simplicity). Without loss of generality, assume that sy (ix) +1. Since the sets
21

---

I \ (I+,+ \ (det) and 1 I are (if not empty) only composed of indexes of coordinates of Bk-1 which are equal 0, one can notice that 5K- also satisfies the new constraints at step k. Therefore I(3x)) S (( Now since [-VL 1]]i, > O, from the strict convexity of the restricted loss on Jt. this means that 3x (ix) > (which also means that newly activated coordinate l must actívate), and therefore Rk-1 # 3g and [(3x) < I(3k-1).
(4) The algorithm terminates in at most min (24 (+) ) steps: Recall that we showed in part (1) of the proof that at each iteration i of the algorithm, 1 as at most min d) elements. Since ( C Tk. we have that 3% has at most (n, d) non-zero elements, also recall that we always have 3gg arg =, g L(3) (we here have unicity of this minimisation problem
following part (1) of the proof). There are hence most
min(n.d)
Σ
xx - min (2
(
such minimisation problems. The loss being strictly decreasing, the algorithm cannot output the same solution / at two different loops, and the algorithm must terminate in at most min (24. Ek=
iterations by outputting a vector 3 such that VI(**) = 0, i.e. 8 E airgmin ((3).
(5) The algorithm outputs the minimum L -oorm solution. Let 5 be the output of the algorithm after p iterations. Notice that by the definition of the successive sets I2.+ and of the constraints on the minimisation problem, we have that at each iteration 8% E @||5k|12. Therefore Sp E 011 Also, recall from part (1) of the proof that Sp span(æ1..... Zn,) which means that there exists E R" such that Sp = x r. Putting the two together we get that X r E a|| 1l1, this condition along with the fact that L(g-)= min (B3 are exactly the KKT conditions of arg min ||
Be arg min
To put our upperbound on the number of iterations into perspective, the worst-case number of
iterations for the LARS algorithm is (3 + 1)/2 [34]. Hence Algorithm 1 has fewer iterations in the worst-case setting. Whether an exponential dependency in the dimension is inevitable for Algorithm I
is unknown and we leave this future work.
However, when the number of samples is much smaller than the dimension we lose the exponential
dependency. Indeed, for = n/d S 1/2, we have the upperbound Σx=o (i) < (e)d where
H(e) - log2(e) (1 =) loga [1 e) is the binary entropy. Since for E S 1/2, H(c) I
-2s (e), we get the upperbound Σn E (+) 2H())d < (d)2n, which is much better than 2d.
D.2 Proof of Proposition 2
As mentioned several times, for general feature matrices X complex behaviours can occur with coordinates deactivating and changing sign several times. Here we show that for simple datasets which have a feature matrix X that satisfy the restricted isometry property (RIP) [14], we can simply determine the jump times and the saddles as a function of the sparse predictor which we seek to recover.
The non-realistic but enlightening extreme case of the RIP assumption is to consider that the feature matrix is such that X T "/nn = La- In this case, by letting 3 be the unique vector such that y (x, )+ and assuming that 5 ($i..... 8r, 0, .... 0) with |8||> loss writes L(3)- = ||3 - 3 113/2 and one can easily check that Algorithm would terminate in r loops and output exactly f; |,811 and 3, (B,,... B O. .......) 0) for i (the case where several
| 0, then the
coordinates of B* are stricly equal can also be treated: for example if 3 = B3 then the first output of the algorithm is directly 31 (0i O,..,,)))))
We now recall the more realistic RIP setting which is an adaptation of the previous observation.
Sparse regression with RIP and gap assumption. (RIP) Assume that there exists r-sparse vector 3 such that y = (2,, B*). Furthermore we assume that the feature matrix X E Rundd satisfies the 2r-restricted isometry property with constant & < -2-1 < 1/2: i.e. for all submatrix X, where we extract any 8 S 2r columns of X, the matrix XJ X./n of size x 8 has all its eigenvalues in the interval [1 E, + E). (Gap assumption) Furthermore we assume that the r-sparse vector 33
22

---

has coordinates which have a "sufficient gap'. W.l.ogg we write 3 = (B...... .,.0,...... 0, ......0) 0) with |8 ... 2 < and we define X == min 13 1) 2 0 which corresponds to the smallest gap between the entries of (3+). We assume that 5 8 2 X/2 and we let 5é.
A classic result from compressed sensing (see Candes [13, Theorem 1. 1.2)) is that the 2r 2r-restricted isometry property with constant v2 1 ensures that the minimum lo fg-minimisation problem has a unique r-sparse solution which 3r. Furthermore ensures that the minimum - solution is unique and is equal to 3*. This means that Algorithm I will have 3 as final output.
We now recall the result which characterises the outputs of Algorithm I when the data satisfies the previous assumptions.
Proposition 2. Under the restricted isometry property and the gap assumption stated right above, Algorithm I terminates in r-loops and oulputs:
31 (1.
with
31 - - =||
[2[1]] E
82 =
with
[2[2] E [8] - 11.33 ++|
8 = [3,-1[1]...... ..-...,,1111- 11,0, .)
with B,-1 E [8] =1 8: + +
3, = 8* (8) ...... 8r, 02,00... .)....
at times t1, ..... tr such that to |3.1+5||3111
1 10 | and where ||-||| denotes the Eo norm.
Proof. In all the proof ||-|| denotes the f2 norm 1|.1|2- For simplicity we assume that 8 > 0 for all i E [r]. the proof can easily be adapted to the general case. We first define { = X Ia. By the restricted isometry property, for any & S 2r, we have that any ie square matrix extracted from which we denote EAR has its eigenvalues in {- It also means that the eigenvalues of
(Ig + ( - Ig are in | 1, 1] C 22, 2č].
We now proceed by induction with the following induction hypothesis:
B has its support on its (k 1) first coordinates with [3k-1 - 5 for i <
* ty E
32+55l|0-1 8 3- and SI [k]] = 1
1
.
sta [i] E [b
3 II), (3) + 5a|l [D)] C (),, k
From the recurrence hypothesis, the output of the algorithm at step ls is hence B4 = arg min L(3) under the constraint B|o] 0 for i < & and B[t] 0 otherwise. We first search for the solution of the minimisation problem without the sign constraint and still (abusively) denote it Ag: we will show that it turns satisfy the sign constraint and that it is therefore indeed 3g.
In the following, for a vector v, we denote by of: k] its ie first coordinates. Setting the io first coordinates of the gradient to O, we get that [X X (Bxx =++ [[= o, which leads to (Ix + Exu [a( k] 3 [: + [:A), which gives:
[ = (Jx + EKX) -1 (88 ( | + [(+))
[*A: + [[ +
where from the bound on the eigenvalues of (4, + ExX) -1 - 1s and || || E11at|
||va |l < 23 3- + [{(8][(A))
< 11]1111|++1155
< 25(1)8*)+
< 18
Therefore
3x[=k] = (TA:A]] + U2
23

---

where 12 = |: A| + 11 hence |02 ||uy | 5c |8 Notice that from the definition of 2/2 we have that [k coordinate-wise hence verifying the sign
and the fact that 5ē 5- |< constraint. Also note that || S || |+* < 1|
For tk 8t St, (t 14. (L(ce), and [+ X] 0 therefore se kj St, [:]] Now
for i k, [-VL( n X Bx]]: 3 + [E(3, B- Now since (Bk- 3*) is r-sparse we have that:
1|E(BE - 1>> S ||E(B: 8²)l
S E B*1
S E(118A|++11 1|13+-11
$ 55|18~1<< 1/2.
(21)
Now from the fact that sr = St [i] + (t - tx + + (t- - }r and using the recurrence
hypothesis: St. [i] E (3, 6 1)) (3: 5 we get (using the bound Eq. (21))
that 8: [i] E [0(3; 5 I)), (8; + 3- From the "separation assumption" we have that
5 5 < 2/2 and therefore the next coordinate to activate is necessarily the (A + 1)th at time 4+11
with 2t [K + = 1 and:
1
3 + 5E B+1|
3/
52 3
This proves the recursion. The algorithm cannot stop before iteration as 5 the unique minimiser of L that has at most non-zero coordinates. But it stops at iteration r as 9 is the unique minimiser of L(3) under the constraints 2 0 for and 3 otherwise.
24

---

E Proof of Theorem 2 and Proposition 3 through the are-length parametrisation
In this section, we explain in more details the arc-length reparametrisation which circumvents the apparition of discontinuous jumps and leads to the proof of Theorem 2. The main difficulty to show the convergence stems from the non-continuity of the limit process 3 Therefore we cannot expect uniform convergence of 3 towards B as a - O. In addition, 30 does not provide any insights into the path followed between the jumps.
Arc-length parametrisation. The high-level idea is to "slow-down" time when the jumps occur. To do so follow the approach from [18. 36] and consider arc-length parametrisation of the path, i.c., we consider 7 equal to:
1/" [1 l|ss.
T (1) -+
In Proposition 6, we showed that the full path length So 11 is finite and bounded independently of a. Therefore 7 is bijection in RRz-- We can then define the following quantities:
= (T) and
B
3o (r))
By construction, a simple chain rule leads to 80 (r) + |1 1, which means that the speed of ( + is always upperbounded by 1, independently of a. This behaviour is in stark contrast with the process (ft)), ), which has a speed which explodes at the jumps. It presents a major advantage as we can now use Arzela-Ascolis 's theorem to extract a converging subsequent. simple change variable shows that the new process satisfies the following equations:
Lf i. (VLL())ds dds = (.;) and i +1 1
(22)
started from 32 = and lo = 0. The next proposition states the convergence of the rescaled process, up to subsequence.
Proposition 8. Let 2 0. For every a >> 0, let (ia, ,a) be the solution of Eq. (22). Then, there exists a subsequence ( kEEN and (f, () such that Or - 0:
Ba - (t
in (C (10,T),R x ).
(23)
(i0,,Bon (i,3)
in [0,T]
(24)
Limiting dynamics. The limits (t. B3 satisfy:
- -1" i.V E 0113+11 and i, + 11.-111 1
(25)
Heteroclinic orbit. In addition, when By such that 1 K (L(3)) V
+ O. we have
3, 11 OVL(
and é, O.
(26)
Furthermore, the loss strictly decreases along the heteroclinic orbits and the path length 1/d 11 is upperbounded independently T.
Proof. Differentiating Eq. (22) and from the Hessian of d.. we get:
3 = 3. -
-=
25

---

Therefore taking the norm on the right hand side we obtain that
IIV (19)))
|
1 + (V
and therefore
8 V
(27)
1+
(L(
Subsequence extraction. By construction Eq. (22) we have i + || - therefore the sequences (()) (3²)a. )a as well as (e.)... (f²),, are uniformly bounded on [0. 7. The Arzelà- theorem yields that, up to a subsequence, there exists (f, 3) such that (f g ) - (f, in (C" T) R x
IR),, Il-llo)) Since || 1122 we have, applying the Banach Aanach-Alaoglu theorem, that up to a new subsequence
( Ba,) - (i, 3) in Loo (0,
(28)
and 11 lim inf 11 || and thus ?, + +11., 1:
L. 11å- $
J-'² lim inf 2p || S / lim inf /| ||d7 S lim inf 0k Jo ax
+00
( / ||d7 C.
ak
where the third inequality is by Fatou's lemma. Note that since [o. 2J bounded then it also implies the weak convergence in any (0, T), 1 S p < co. Since (δe) converges uniformly on [0, 7]. and V is continuous, we have that (((3g) converges uniformly to (B) Since jou - f in L (0, T). passing to the limit in the equation V ( So è V (Bg ds leads to
vL(3)dds e 0113,11, 12,
due to Lemma 2.
Recall from Eq. (27) and the definition of pa that:
0 a o vL(3;)
8
(29)
1/ln(1/a) + 11 3 + a @ VL(3))II
Hence assuming that 2r is such that (L) O ensure that ||| [VV 0
(3
for r' [T, + e and E small enough. We have then 1/lm(1/a)+lly
converges
uniformly toward v on [T, + +s. Using the dominated convergence theorem, we [15,10V((,,) b
have f
dr' f ( 115,1ev4(,,)1 dr'. We therefore obtain
1/lug(1/a)+Il 94 ta to
8, ( in L, [0, T]. Consequently || and é 0. [1-10V
Proof that the loss stricly decreases along the heteroclinic orbits.
Assume 3 is such that (L,(VV((3,) + 0, then the flow follows
à 1 O ($.)
11 O VL(())))
Letting 7(7) (V)( get:
dL(3.) -7(7) Σ
B. (1 <0,
because 1 # 0.
26

---

Borrowing terminologies from [18]. we can distinguish two regimes: when 3, = 0, the system is sticked the saddle point. When ł and || the system switches to a viscous slip which follows the normalised flow Eq. (26). We use the term of heteroclinic orbit as in the dynamical systems literature since in the weight space (u, v) it corresponds to a path with links two distinct critical points of the loss F. Since f,- 0, this regime happens instantly for the original i time scale (i.e. a jump occurs).
From Proposition 8, following the same reasoning as in Section 3, we can show that the rescaled process converges uniformly to a continuous saddle-to-saddle process where the saddles are linked by normalized flows.
Theorem 3. Let T O. For all subsequences defined in Proposition 8, there exist times 0 = T T1 < < <... < Tp < T < Tp+1 +o0 such that the the iterates () converge uniformly on [0, T) to the following limit trajectory:
("Saddle")
Br = 3k
for E IThy Te+1] where 0 S k
3, 18+10VI(8
(Orbit)
for T E [Te41, To4al where 0 < k S
10
where the saddles (go = 0, 0, -B,,) are constructed in Algorithm 1. Also, the loss (L(3,)), is constant on the saddles and strictly decreasing on the orbits. Finally, independently of the chosen subsequence, for k E we have typ = brg tt where the times (tu)kelp) are defined through Algorithm 1.
Proof. Some parts of the proof are slightly technical. To simplify the understanding, make use of auxiliary lemmas which are stated in Appendix F. The overall spirit follows the intuitive ideas given in Section 3 and relies showing that Eq. (25) can only be satisfied if the iterates visit the saddles from Algorithm 1.
We let 8, == So is V L(3.)dds. which is continuous and satisfies 8, E a||3-|11 from Eq. (25). Let S (3 E RR VL)) 0} denote the set of critical points and let (8k, 8k) be the successive values of t, which appear in the loops of Algorithm 1.
We do proof by induction: we start by assuming that the iterates are stuck at the saddle 3 at time + 2 Tk- where f, = - and , S (recurrence hypothesis), we then show that they can only move at time Tæ and follow the normalised flow Eq. (26). We finally show that they must end up "stuck" at the new critical point 3g. validating the recurrence hypothesis.
Proof of the jump time Tk such that fr, te we set ourselves time 2 Th-1 stuck at the saddle 3x-1. Let Tk = sup(r, &y I txh. we have that TІ < oo from Lemma Note that by continuity of & it holds that (, lu. Now notice that 8, = 8 (Lr [
8k-1 - (1r (---1) V( We argue that for any 8 > 0, we cannot have B, 3k-1 on (TR, T& + e). Indeed by the definition of TA and from the algorithmic construction of time 44 it would lead to 8, (i){> for some coordinate [d], which contradicts Eq. (25). Therefore the iterates must move the time Tk.
Heterocline leaving 3x-1 [Tko +f]= contrary to before, our time rescaling enables to capture what happens during the "jump". We have shown that for any there exists Te E (Tk, T + E). such that Br, * 9x-1- From Lemma 4, since the saddles are distinct along the flow, must have that B., & S for small enough. The iterates therefore follow heterocline flow leaving 3x-1 with speed of given by Eq. (26). We now define T/ == inf{r > Tk Jen > O, Ve E E0] 9r+c E S} which corresponds to the time at which the iterates reach a new critical point and stay there for at least small time Eg. We have just shown that 7/ > тк- Now from Proposition the path length of & is finite, and from Lemma 4 the flow visits a finite number of distinct saddles at a speed of 1. These two arguments put together, we get that o/ < too and also Beg+o -Baz- Ve E 60] On another note, since f 0 for [Tk, Ti] we have &.g Eyg (= tx) as well as S., B (= sn).
27

---

Proof of the landing point 33. we now want to find to which saddle 3. E S the iterates have moved to. To that end, we consider the following sets which also appear in Algorithm
1 = {i E (1....,d} d), s.t. 8rg (1) = =13 and I = I+ U.-AA
(30)
The set Is corresponds to the coordinates of B.g which "are allowed" (but not obliged) to be activated (i.e. non-zero). For T E [Tke T + so] we have that 8, = 8.g- - (fr (x) V By continuity of 8 and the fact that 8, E 9 Ila. the equality translates into:
i $ In. 3 (i) 00
i E L, then [VL(3;;)]: 2 0 and 3,;(1)
i E I_ then [L(3, S and (1)(1) <
. for i E T,, if Brg (1) # 0, then [V((,g))) =
One can then notice that these conditions exactly correspond to the optimality conditions of the following constrained minimisation problem:
arg min
I(B)-
(31)
0,20,4El..t 9,50,
3==0,
We showed in Proposition that the solution to this problem is unique and equal to 8g from Algorithm 1. Therefore 3, 3k for E [T T/. Eu]. It finally remains to show that B, 3g while Tk+1 where Tk+11 sup f tx+1). For this let 7 [T Tk+1], notice that for & Ik. necessarily have that (1) (1) = O, otherwise we break the continuity of s,. Similarly, for E I2,+. we necessarily have that (1) 2 0 and for i E 4._, 3, (i) < O for the same continuity reasons. Now assume that Br (Ix) * (Tx).. Then from Lemma 4 and continuity of the flow, 3r' (T&, such that Ar. E and there must exist heterocline flow Eq. (26) starting from 3g which passes through B.,. This is absurd since along this flow the loss strictly decreases, which is in contradiction with the definition of 3g which minimises the problem Eq. (31).
E.1 Proof of Theorem 2
Theorem 3 enables to prove without difficulty Theorem which we recall below. Indeed we can show that any extracted limit maps back to the unique discontinuous process B
Theorem 2. Let the saddles (Bo = 0, ,1, 3p-1..
87, and jump times (to = 0, ft.....tpp tp) be the outputs of Algorithm and let (6%)e be the piecewise constant process defined as follows: (Saddles)
35 = Bk
for (x+1) and 0 S k p, tp+1 toc.
The accelerated flow (3t) ), defined in Eq. (9) uniformly converges towards the limiting process (3g),
on any compact subset of R2 (b.......
Proof. We directly apply Theorem 3, let og be the subsequence from the theorem. Let >> for simplicity we prove the result on [+1 + e, t2 z). all the other compacts easily follow the same line of proof. Note that since fox (7f) + t and 8ox (T2) - 12, for ag small enough for (71) I f1 + and
for (T2) 2 t2 - E, by the monotonicity of T this means that for ag small enough, 7i S 7 (t1 +
and T2 2 T (t2 =). Therefore
11.00u B1l1= sup tElti -cl
||,3ax (Tan -311l
sup
te,tite,tooel
+El (t) [1 -1il
sup
< sup rEjo(.72
_ (7) 311l.
which goes uniformly to following Theorem Since this result is independent of the subsequence ak, we get the result of Theorem 2.
28

---

E.2 Proof of Proposition
We restate and prove Proposition below.
Proposition 3. For all T>> >> 1p the graph of the iterates (B JesT converges to that of (3r)r
dist 30 HST, (8+}-20)
(Hausdorff distance)
a-0
Proof. For a small enough, we have that / S 4p + 8 T
sup d(3r. ((sT) sup d( d(Br, ( h(s)) +20
T
I sup ||, - 3 ||
TStp
sup 3711
0,
TStb
according to Theorem 3.
Similarly:
sup KTT
(3+)r) sup d(3;; (3+)+1)
-S
S sup |3
Br
11
0,
a-0
according to Theorem 3, which concludes the proof.
29

---

Technical lemmas
The following lemma describes the behaviour of Vda (8*) as - in function of the subdifferen- tial 011-111- Lemma 2. Let (3"))s such that 3a - B E IRd
if B, then V (B8)); converges to
* if < 0 then V (Ba) converges to -1.
Moreover if we assume that V Vé (8a) converges to v E Rd, we have that:
1/1 E =0
= n [-1.1].
Overall, assuming that (3 Voa(B²)
_ (B, we can write:
a-10
1) B|
Proof. We have that
1 aresinh(
g a²
(Vo.
2l1(1/)
1
(Ba)²
In
+
+
2 ll1//a
Now assume that 3rs > then VVo. (8 an odd function. All the claims are simple consequences of this.
)1 + 1, if 3, we conclude using that aresinh is
The following lemma shows that the extracted limits as defined Proposition 8 diverge to co. This divergence is crucial as it implies that the rescaled iterates (3r); explore the whole trajectory.
Lemma 3. For any extracted limit as defined in Proposition 8, we have that 7 C < fr where C the upperbound on the length of the curves defined in proposition
Proof. Recall that
(t) = ++ 1 [1 [1gg
From Proposition 6, the full path length f 1|:2 ds is finite and bounded by some constant C independently a. Therefore 7 is a bijection R2 and we defined éq = (7)) Furthermore (t( < + leads t < 80 (t + C') and therefore 7 < 8' (r) for all t 2 0. This inequality still holds for any converging subsequence, which proves the result.
Under a mild additional assumption on the data (see Assumption 2), we showed after the proof of Proposition 1 in Appendix B that the number of saddles of F is finite. Without this assumption, the number of saddles a priori not finite. However the following lemma shows that along the flow of 3 the number of saddles which can potentially be visited is indeed finite.
Lemma 4. The limiting flow 3 as defined in Proposition can only visit a finite number of critical points 3 E S = {3 E Rd, 3 L() 0} and can visit each one of them at most once.
Proof. Let 2 0, and assume that B, E S. i.c., we are at a critical point at time From Proposition 1, we have that
Br E
arg min L(3),
(32)
8.=0 for (gsupp(8.)
30

---

Let us define the sets
1 = f (I,..... s.t. 8-(1) = +1) and 1=4UL
The set corresponds to the coordinate of 3, which "are allowed" (but not obliged) to non-zero since from Eq. (25), supp(3r)
Now given the fact that the sub-matrix X, = (āi)ier Rexxaad((J) full rank (see part (1) of the proof Proposition for the explanation), the solution of
the minimisation problem (32) is unique and equal to ((g] = (X Xx) xxx= and [|5 = 0 where
ç ===uupg supp((r)) There are 24 = Card(P([d)) (where P((d) contains all the subsets of [d] number of constraints of the form { 0, i & A). where A C [d]. and 3r is the unique solution of one of them. 8, therefore take most 24 values (very crude upperbound). There is therefore finite number of critical points which can be reached by the flow 3. Furthermore, from Proposition 8, the loss is strictly decreasing along the heteroclinic orbits, each of these critical points can therefore be visited at most once.
31


Reviews:
[{"review_id": "2jFNk5jyTP", "reviewer": "Reviewer_BqoH", "summary": "This paper studies the saddle-to-saddle dynamics in Diagonal Linear Networks.\nThe authors present solid theoretical understanding. \nThey show that over 2-layer diagonal linear network, gradient flow starting with vanishing initialization visits then jump from saddles  jumps from a saddle of the training loss to another until reaching the minimum $\\ell_1$-norm solution.\n\n", "questions": "1. I would like to know how much the vanishing initialization would affect the saddle-to-saddle phenomenon. Will saddle-to-saddle dynamics also occur if a practical initialization is used?\n\n2. As shown in the theory and Figure 2, the recovery of coordinates is sequential, which seems to be similar to the Coordinate Descent algorithm. In this setting of 2-layer diagonal linear networks, are GD and CD inherent related?", "limitations": "The analysis in this study focus on 2-layer diagonal linear networks, which have limited representation abilities and exhibit some special properties such as Prop 1.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The paper is clear and well-written. \nUnderstanding the training dynamics of gradient descent over neural networks is a significant theoretical issue. \nParticularly, the phenomenon of saddle-to-saddle during neural network training remains mysterious, and this paper makes a valuable contribution by offering a solid theoretical analysis for 2-layer diagonal linear networks.\nThe proof presented in the paper incorporates innovative techniques, including mirror flow and time-reparametrization.", "weaknesses": "The article's significance may be constrained by the focus on 2-layer diagonal linear networks, which have limited representation abilities and are no better than linear models. \nHowever, this limitation is not a major concern since the problem itself is non-convex, even in this simplified scenario. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for the valuable feedback. \n\nWe answer to your questions below and answer to your comment on the restrictive setting in the *official comment* section since it was made by nearly all the reviewers. We answer to both of your questions below.\n\n**Practical initialisations and saddle-to-saddle**: Saddle-to-saddle type of dynamics (which can also be referred to as the feature learning regime in the deep learning community) have been empirically observed in various cases **with practical initialisations**. For instance, in [22], the authors empirically *\"give evidence for the hypothesis that, as iterations progress, SGD learns functions of increasing complexity\"* when training deep neural networks. They emphasize that these observations are for *\"standard random initialisation\"*.  For further references highlighting the incremental nature of learning for practical initialization, you can observe characteristic stepwise learning curves in Figures 1 and 2 from [a] as well as Figures 2 and 3 from [b]. Therefore, saddle-to-saddle dynamics **do not** simply correspond to a pathological and uninteresting phenomenon which only occurs asymptotically. They gradually appear and then amplify when taking the initialization to zero. In our setting, you can observe the progressive sharpening of the curves in Figure 3 (left) in the appendix. A very interesting question for future work would be to theoretically exhibit the threshold $\\alpha_0$ at which the saddle-to-saddle dynamics starts to appear. However this would require a non-asymptotic and different type of analysis compared to the one we propose in our work. \n\n**Algorithm 1 and CD**: Algorithm 1 and Coordinate Descent share similarities as they both iteratively solve minimisation problems over a fixed set of coordinates. The two are nonetheless distinct algorithms, the major difference is that Algorithm 1 progressively identifies the support of the minimum l1 interpolator: the successive sets of minimized coordinates are appropriately chosen and are of overall increasing size. On the other hand, for CD, only **one coordinate at a time** is updated and this coordinate is chosen very differently to Alg 1: in many cases it is simply chosen randomly. A major consequence of these differences is that Alg 1 terminates in a finite number of iterations while CD only converges asymptotically. \n\n[a] Simon et al., On the Stepwise Nature of Self-Supervised Learning, arXiv 2023\n\n[b] Oswald et al, Transformers Learn In-Context by Gradient Descent, arXiv 2023\n"}, {"review_id": "v9BUAHTahY", "reviewer": "Reviewer_FL6c", "summary": "In this paper, the authors studied the training dynamics of gradient flow that minimizes mean-square loss with 2-layer diagonal linear networks and data in general position. Under the small initialization (initialization scale goes to 0), the authors showed that the limiting dynamics follows a saddle-to-saddle dynamics (jump from one saddle point to another saddle point) until reach the min-$\\ell_1$-norm interpolator. They gave an algorithm that can compute the visited saddle points. The results generalized the previous works on incremental learning. Experiments are also provided to verify the results.", "questions": "1.\tIn Theorem 2, it seems that the final solution is min-$\\ell_1$-norm interpolator, so I think that means we are implicitly assuming the input dimension $d$ is at least the number of samples $n$?", "limitations": "The limitation is discussed in the paper. This is a theoretical work and therefore does not seem to have negative societal impact.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.\tThe paper is clearly written and easy-to-follow. The proof sketch and example are given to help the readers to understand the proof easier.\n2.\tUnderstanding the training dynamics of neural networks/nonlinear models is an interesting and important problem.\n3.\tThis paper gives a precise characterization of the training dynamics that jumps between saddle points. This recovers and goes beyond some of the previous works on the incremental learning for linear diagonal networks.\n4.\tThe technique of reparametrized time to “accelerate” time seems to be interesting and might be of independent interest.\n", "weaknesses": "1.\tThe current paper focuses on the linear diagonal linear networks. It would be interesting to see if such analysis could be generalized to other more complicated problems.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for the valuable feedback. \n\nWe answer to your comment on the restrictive setting in the *official comment* section since it was made by nearly all the reviewers.\n\n**Dimension and number of samples**: your comment on the input dimension $d$ having to be larger than the number of samples $n$ is due to our imprecise definition of $\\beta^*_{\\ell_1}$ in the paper, we make it clearer here and will make it clearer in the revised version. The definition of $\\beta^*_{\\ell_1}$ which we give line 116 as $\\beta^*_{\\ell_1} = \\arg \\min_{X \\beta = y} \\Vert \\beta \\Vert_1$ indeed **only makes sense when $d > n$**. However, when $d \\leq n$, all our results still hold by simply letting $\\beta^*_{\\ell_1}$ be the unique minimiser of the loss (which trivially is still the minimum l1-norm solution as it is then the only solution!). The general and correct (but a bit more heavy) way of defining $\\beta^*_{\\ell_1}$ is as :\n$\\beta^*_{\\ell_1} \\coloneqq \\arg \\min_{ \\beta \\in \\arg \\min L} \\Vert \\beta \\Vert_1$. This definition then holds for any $(n, d)$ and all our results still hold. Thank you for pointing out this imprecision. "}, {"review_id": "3vhRex50oh", "reviewer": "Reviewer_8NQr", "summary": "This paper analyzes a two-layer diagonal linear network, which is a linear regression model where the linear weight is parameterized as the point-wise product of two weight vectors. It is shown that, with vanishing initialization, gradient flow will jump between saddle points of the training loss and eventually reach the $\\ell_1$-minimum-norm solution. This paper further provides an algorithm to calculate all the saddle points.", "questions": "N/A", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "It is very important to understand the training dynamics of neural networks, and this paper analyzes a novel and interesting saddle-to-saddle phenomenon. Moreover, Algorithm 1 in this paper can compute all the jump times and saddle points, giving a complete characterization of the gradient flow trajectory. The writing is also clean, with illustrative examples and graphs.", "weaknesses": "The main weakness is that the two-layer diagonal linear network model (specifically, the point-wise product of two weight vectors) is too simple. If there is some evidence that some of form of the saddle-to-saddle phenomenon also happens in practical networks, this paper will be more convincing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your feedback.\n\nWe answer to your questions below and answer to your comment on the restrictive setting in the *official comment* section since it was made by nearly all the reviewers.\n\n**Evidence for practical networks**:  we would like to re-emphasize that saddle-to-saddle dynamics **have been observed in practice in various cases** and that this preponderance is precisely the motivation behind our work (see lines 25 to 32 in our introduction).  For instance, in [22], the authors empirically *give evidence for the hypothesis that, as iterations progress, SGD learns functions of increasing complexity* when training deep neural networks.  For further references highlighting the incremental nature of learning, you can see characteristic stepwise learning curves in Figures 1 and 2 from [a] or Figure 2 and 3 from [b]. Also note that these observations in practical networks have led to a large amount of works trying to theoretically prove such dynamics in various settings: matrix factorisation, linear networks etc. (see lines 33 to 41 in our introduction). However, our work is the first to theoretically provide a complete picture describing this phenomenon without imposing restrictive assumptions on the design matrix. \n\n[a] Simon et al., On the Stepwise Nature of Self-Supervised Learning, arXiv 2023\n\n[b] Oswald et al, Transformers Learn In-Context by Gradient Descent, arXiv 2023\n"}, {"review_id": "O4X8QnS77Z", "reviewer": "Reviewer_P2pV", "summary": "This work concerns the behavior of gradient flow of 2-layer diagonal linear neural networks when the initialization scale goes to zero. The authors show that this limiting behavior is governed by a piecewise constant trajectory consisting of jumps from saddle to saddle.", "questions": "What is the significance of the connection to the Homotopy algorithm? I'm not familiar with it and would appreciate if the authors can explain a bit more why this connection matters.\n\nIf the authors can address this and the weaknesses above, I'll be happy to raise the score to a 7.", "limitations": "I do not believe the authors addressed the limitations, at least not in an explicit way. I think the paper would be greatly improved if it can touch upon the comment brought up on line 78 that the activation function is the identity. The authors make it very clear that the work is about linear networks, as many other prior works have done. I feel like if the authors can provide some form of experimental results/explanation of whether this phenomenon appear (or does not appear) where $\\sigma$ is nonlinear would be greatly beneficial. That said, I think the paper's technical contribution outweighs this.\n\nIf the authors can address this and all of the above, I'll be happy to raise the score to an 8.", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "The incremental learning and saddle-to-saddle phenomenon is interesting. Although the model considered in this paper is equivalent to linear models, the dynamics that the authors uncover is nonetheless nontrivial and of broader interest. The writing quality is excellent and the technical material is presented in an intuitive to understand way.", "weaknesses": "Is the final point $\\beta_p$ in Theorem 2 the minimum $\\ell_1$ solution to $L$? Theorem 2 does not explicitly state it.\n\nMuch of the later analysis is regarding the $\\beta$'s. But the model is stated in terms of the $u$'s and $v$'s. Can the authors comment on the behavior of the $u$'s and $v$'s? (Or at least point me to where this was discussed, in case I missed it).\n\nline 40 \"diagonal linear networks which are simplified neural networks that have received significant attention lately...\". Could the authors provide a slightly expanded discussion of what these prior work did? Since this paper is specifically about diagonal linear networks, this part of the related work I believe is especially important.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for the extensive and valuable feedback. We answer to your remarks and questions below.\n\n**Final point $\\beta_p$**: the final point $\\beta_p$ is indeed the minimum $\\ell_1$ norm solution $\\beta^*_{\\ell_1}$, we tried to make this clear by pointing out that $\\beta_p = \\beta^*_{\\ell_1}$ in Theorem 2 line 253. We propose to emphasize this point if the reviewer feels it is necessary. \n\n**Neuron point of view**: we indeed did not put much emphasis on the neurons $(u,v)$. However as explained lines 263-265, there exists a bijection (given in Lemma 1) between the neurons and the vectors $\\beta_t$. Therefore we immediately get that the neurons $(u^\\alpha_t, v^\\alpha_t)$ converge towards $(\\sqrt{\\vert \\tilde{\\beta}_t^\\circ \\vert}, \\text{sign}(\\tilde{\\beta}_t^\\circ)  \\sqrt{\\vert \\tilde{\\beta}^\\circ_t \\vert})$.  We will make this point clearer in the revised version.\n\n**Previous works on DLNs**: by lack of space we indeed unfortunately did not provide an extensive discussion on previous works on DLNs. This omission is mostly because the vast majority of these works investigate the properties of the solution recovered by gradient flow / GD / SGD, without looking at the trajectory. The two most relevant references are [4] and [38] and are discussed at the beginning of section 2.2:\n- [4] shows that the iterates $\\beta_t^\\alpha$ follow a mirror flow with potential $\\phi_\\alpha$\n- [38] shows that the recovered solution $\\beta_\\infty^\\alpha$ minimises the potential $\\phi_\\alpha$\n\nConcerning other works on diagonal linear networks, we have:\n- [33] investigates the role of SGD’s noise on the recovered solution\n- [18] investigates the effect of label noise on the recovered solution\n- [13] and [c] investigate the effect of the stepsize on (S)GD's recovered solution\n- [37] investigates the statistical properties of the solution recovered by GD under a RIP assumption\n\nWe will add the discussion concerning these results in the related work.\n\n**Link with the Homotopy algorithm**: the connection between Algorithm 1 and the Homotopy algorithm **is not important in itself but should be seen as a help to understand Alg 1**. \nWe mention this connection for two reasons: *(1)* the main one is to make Algorithm 1 feel less opaque and \"out of the blue\" by linking it to an old and well-established algorithm, *(2)* the construction of Algorithm 1 as given section 3.1 follows very similar lines as that of the Homopy algorithm.\nIn this way, making a link with the Homotopy algorithm is a way (for readers who are acquainted to it) of providing a familiar algorithm which makes our results more natural. **However, we hope that our intuitive construction of Alg 1 in Section 3 is clear enough for the algorithm to be understandable to people who are not familiar with the Homotopy algorithm.** \n\n**Non-linear activation**: We would like to emphasis that **saddle-to-saddle dynamics also occur even when there is a non-linear activation**. To support this claim, we refer to [22] which \"give evidence for the hypothesis that, as iterations progress, SGD learns functions of increasing complexity \" for non-linear deep-networks and that there is a \" separation in phases for learning\". Furthermore, in [8], a 2-layer ReLU network is considered and you can observe a clear saddle-to-saddle dynamics in Figure 3 (for orthogonal inputs) and also in Figure 4 (f) (general inputs). We can also mention more recent works which consider non-linear networks and where clear saddle-to-saddle dynamics are observed: see Figure 2 in [a] and Figure 5 in [b]. We hope that these references will convince the reviewer that a non-linear activation function **does not** prevent the occurrence of saddle-to-saddle phenomenons. We will make this clearer in the revised version. \n\n[a] Simon et al., On the Stepwise Nature of Self-Supervised Learning, arXiv 2023\n\n[b] Oswald et al., Transformers Learn In-Context by Gradient Descent, arXiv 2023\n\n[c] Nacson et al., Implicit Bias of the Step Size in Linear Diagonal Neural Networks, ICML 2022"}, {"review_id": "Wz5ujdiFdY", "reviewer": "Reviewer_tpj2", "summary": "This paper characterizes the trajectory of gradient flow on 2-layer diagonal linear networks for linear regression tasks. Specifically, the paper considers the model parameterized as $x \\mapsto \\langle u \\odot w, x \\rangle$ in the linear regression setting. By interpreting the gradient flow on the nonconvex loss as a mirror flow, the authors show, in the limit of vanishing initialization, that the gradient flow dynamics jump between various saddles before converging to the minimum $\\ell_1$ norm solution. The paper characterizes the exact times of these jumps (after appropriate rescaling based on the initialization size $\\alpha$ in the $\\alpha \\rightarrow 0$ limit), as well as the location of these saddles; these times and locations can be computed via algorithm 1. As a consequence, the paper shows that each saddle is a solution to a constrained minimization problem where some subset of coordinates are fixed 0. Under a RIP assumption on the data, the paper shows that new coordinates are added sequentially at each saddle, thus demonstrating incremental learning.", "questions": "- In general, what can one say about successive saddles? It would be interesting to understand more fine grained properties about the sequence of saddles, such as how many coordinates can change at each step and under what conditions coordinates can get deactivated. I find it unlikely that Algorithm 1 would loop through all possible subsets of activated coordinates, and instead find it more likely that coordinates would be deactivated less frequently. I thus think the paper would benefit from additional investigation (either theoretically or empirically) into how the set of activated coordinates changes between saddles.\n- What can be said in the case when $\\alpha$ is small but isn’t taken to 0? Can one say something quantitatively about whether saddle-to-saddle dynamics occur, or the rate at which the trajectory limits to the piecewise constant trajectory $\\tilde \\beta^\\circ$?", "limitations": "Limitations/Broader Impact are adequately addressed. ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper appears to be technically sound, and is well-written and easy to understand.\n- The quadratically parameterized regression problem has been well studied in prior works (Woodworth et al. 2020, Azulay et al. 2021, and others), which show that the gradient flow can be characterized by mirror descent and converges to the minimum $\\ell_1$ solution in the $\\alpha \\rightarrow 0$ limit. However, the current paper exactly characterizes the limit of the gradient flow trajectory under minimal data assumptions, which is a novel analysis. The main technical novelty here is proving that as $\\alpha \\rightarrow 0$ the trajectory converges to a piecewise constant process. \n- While many prior works on implicit regularization only focus on properties of the solution at convergence, the current paper can describe the saddle points along the trajectory. I find it to be a significant contribution that the successive saddles which can be visited by gradient flow can be characterized (by Algorithm 1) explicitly. In particular, the observation that coordinates can be deactivated has not appeared in prior work and is quite interesting.\n- Finally, I find this paper to be of moderate significance, as the quadratically parameterized linear regression setting is a common toy problem to understand the implicit regularization effect of gradient descent more generally.", "weaknesses": "There are a couple (minor) weaknesses of the current theory.\n- The analysis is limited to the quadratically parameterized regression setting, which while despite possessing rich implicit regularization behavior is still far from more practical settings in which implicit regularization occurs.\n- One weakness of the current paper is that the jump times and saddle locations are only implicitly defined via Algorithm 1. The paper does show that under an RIP assumption that the jump times are $1/\\beta^*_s$ and the saddles correspond to incrementally learning more coordinates. However, it is difficult to interpret the intermediate iterates of Algorithm 1 more generally, which reduces the impact of this paper.\n- Another weakness is that the entirety of the analysis is done in the $\\alpha \\rightarrow 0$ limit, rather than at some small (but finite) initialization $\\alpha$.\n\nMinor typos:\n- line 133 “diferred” → “deferred”\n- line 318 “independant” → independent”", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for the feedback.\n\nWe answer to your questions below and answer to your comment on the restrictive setting in the *official comment* section since it was made by nearly all the reviewers.\n\n**Finite initialisation**: unfortunately, as we acknowledge line 267, our results do not provide a rate of convergence in $\\alpha$ and therefore cannot explain the observed stepwise trajectories for a non-zero initialization. We believe that a non-asymptotic result is currently challenging, but we believe that our work is nonetheless a significant contribution and that the tools and techniques we provide could eventually lead to a non-asymptotic result. \n\n**Additional results concerning Algorithm 1**: we would first start by highlighting that the main goal of our work is to prove that the limiting dynamics of GF for vanishing initalisation is a saddle-to-saddle dynamics which is fully described by Algorithm 1. From there, as rightfully mentioned by the reviewer, many very interesting questions can be raised concerning the behaviour of this algorithm. We already provide a few: \n- upper bound on the number of iterations \n- proof that the  coordinates of the iterates $\\beta_k$ have at most $n$ non-zero coordinates (see prop 6 in the appendix)\n- analysis of the full behaviour under a RIP assumption\n\nMoreover, we believe that further results are out of the scope of our paper. Indeed, to draw a comparison, we are not aware of results for the Homotopy method which go beyond results under RIP assumptions apart from [a] which provides a worst-case lower-bound on the number of iterations. However, note that this result is from 2012, therefore more than 10 years after that the algorithm was initially introduced in [b].\n\n[a] Mairal and Yu, Complexity Analysis of the Lasso Regularization Path, ICML 2012\n\n[b] Osborne et al. A new approach to variable selection in least squares problems, 2000.\n\n"}]

Author rebuttal:
We thank all the reviewers for the time they spent reviewing our paper and for the valuable feedback. An overall comment made by all reviewers (except reviewer P2pV) is that the considered setting (2-layer diagonal linear network) is too restrictive. We naturally agree that our setting is very far from practical networks. However, we want to emphasize that despite its apparent simplicity, the loss function is non-convex and very rich behaviors already occur, as illustrated in the paper. 
This saddle-to-saddle behavior (also called incremental learning or feature learning) has been observed in a variety of more complicated settings as motivated in the introduction. We take advantage of this rebuttal to add two recent works which highlight the prominence of such dynamics in current deep learning settings: see Figure 2 in [a] where several network architectures are considered as well as Figures 2, 3, 5 in [b] where various transformers are studied.

As such, we consider our setting as being an ideal proxy model for gaining a deeper understanding of saddle-to-saddle dynamics. We would also like to highlight that despite the apparent simplicity of the model, the analysis is already rather involved and a non-trivial algorithm emerges. Furthermore, we believe that the tools we leverage in our work could be very useful for future works studying similar dynamics but in different settings. Finally, we want to point out that the solution recovered by gradient flow with vanishing initialization is still not fully understood for more complex frameworks such as matrix multiplication or 2-layer ReLU networks. Hence we believe that studying the full trajectory and explaining the observed saddle-to-saddle dynamics in such general settings is currently out of reach.

In view of all this, we hope that the reviewers will acknowledge that though our framework may seem deceptively simple, the analysis is already quite intricate and our work contributes to the understanding of an important topic as well as provides useful tools for future research.

[a] Simon et al., On the Stepwise Nature of Self-Supervised Learning, arXiv 2023

[b] Oswald et al, Transformers Learn In-Context by Gradient Descent, arXiv 2023


Meta-review: This paper considers two-layer diagonal linear networks for a regression problem, and the main result is a precise characterisation of the trajectory of gradient flow. Specifically, a saddle-to-saddle dynamics is unveiled and described accurately. 

All reviewers are positive about the work (although with varying levels of enthusiasm). As pointed out in multiple reviews and also acknowledged by the authors in the rebuttal, the setting of two-layer diagonal linear networks is a bit restrictive. Nonetheless, I agree with the authors when they claim that 'very rich behaviours already occur'. The insights shed by the paper are certainly non-trivial, and there is technical novelty as well. For these reasons, after my own reading of the reviews, rebuttal and paper, I am happy to recommend acceptance.
Decision: Accept (spotlight)