Implicit Sparse Regularization: The Impact of Depth and Early Stopping
Authors: Jiangyuan Li
Thanh V Nguyen
Chinmay Hegde
Raymond K. W. Wong
Venue: NeurIPS 2021 Poster (2021)
Keywords: gradient descent
implicit regularization
early stopping
initialization
depth
sparse recovery

Abstract: In this paper, we study the implicit bias of gradient descent for sparse regression. We extend results on regression with quadratic parametrization, which amounts to depth-2 diagonal linear networks, to more general depth-$N$ networks, under more realistic settings of noise and correlated designs. We show that early stopping is crucial for gradient descent to converge to a sparse model, a phenomenon that we call \emph{implicit sparse regularization}. This result is in sharp contrast to known results for noiseless and uncorrelated-design cases. 
  
We characterize the impact of depth and early stopping and show that for a general depth parameter $N$, gradient descent with early stopping achieves minimax optimal sparse recovery with sufficiently small initialization $w_0$ and step size $\eta$. In particular, we show that increasing depth enlarges the scale of working initialization and the early-stopping window so that this implicit sparse regularization effect is more likely to take place.

Implicit Sparse Regularization: The Impact of Depth and Early Stopping
Jiangyuan Li j jianyuann1 i @taamu. edu Texas A&M University
Thanh V. Nguyen thanhng. cswgmail...mmmmmmmmmmmmmmmmm.. com
AWS AI
Chinmay Hegde
Raymond K. W. Wong raywong@tamu edu Texas A&M University
chinmay h@nyu edu New York University
Abstract
this paper, we study the implicit bias gradient descent for sparse regression. We extend results regression with quadratic parametrization, which amounts depth-2 diagonal linear networks, to more general depth-NV networks, under more realistic settings of noise and correlated designs. We show that early stopping is crucial for gradient descent to converge to a sparse model, phenomenon that we call implicit sparse regularization. This result is in sharp contrast to known results for noiseless and uncorrelated-design cases. We characterize the impact depth and early stopping and show that for general depth parameter N, gradient descent with early stopping achieves minimax optimal sparse recovery with sufficiently small initialization wo and step size 7). In particular, enlarges the scale of working initialization and the early-stopping window so that this implicit sparse regularization effect is more likely take place.
show that increasing depth
Introduction
Motivation. Central recent research in learning theory is the insight that the choice of optimization algorithms plays an important role in model generalization [1, 2, 3J. A widely adopted view is that popular optimization algorithm in machine learning
(stochastic) gradient descent the exhibits some implicit form of regularization. Indeed for example, in the classical under-determined least squares setting, gradient descent (with small step size) starting from the origin converges to the model with minimum Euclidean norm. Similar implicit biases are also observed in deep neural network training in which the networks typically have many more parameters than the sample size. There, gradient descent without explicit regularization finds solutions that not only interpolate the training data points but also generalize well on test sets [2, 4, 5, 6, 7].
This insight, combined with the empirical success stories of deep learning, has sparked significant interest among theoretical researchers to rigorously understand implicit regularization. The majority of theoretical results focus on well-understood problems such as regression with linear models [8, 9, 10, 11, 12, 13] and matrix factorization [14, 15, 16, 17], and show that the parametrization (or architecture) of the model plays crucial role. For the latter, Gunasckar et al. [15] conjectured that gradient descent on factorized matrix representations converges the solution with minimum nuclear norm. The conjecture was partially proved by Li et al. [16] under the Restricted Isometry Property (RIP) and the absence of noise. Arora et al. [17] further show the same nuclear-ne norm implicit bias using depth-N linear networks (i.e., the matrix variable is factorized into N components).
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Parallel work on nonlinear models and classification [5, 9] has shown that gradient descent biases the solution towards the max margin/minimum 2n-nom solutions over separable data. The scale of initialization in gradient descent leads to two learning regimes (dubbed "kernel" and "rich") in linear networks [18], shallow ReLU networks [19] and deep linear classifiers [20]. Li et al. [21] showed that 2epth-2 network requires an exponentially small initialization, whereas depth-N network (N 2 3) only requires a polynomial small initialization, to obtain low-rank solution in matrix factorisation. Woodworth et al. [18] obtained a similar result for high dimensional sparse regression.
The trend in the large majority of the above works has been to capture implicit regularization of gradient descent using some type of norm with respect to the working parametrization [18, 22, 23, 24]. On the other hand, progress on understanding the trajectory of gradient descent has been somewhat more modest. [11, 12] study the sparse regression problem using quadratic and Hadamard parametrization respectively and show that gradient descent with small initialization and careful early stopping achieves minimax optimal rates for sparse recovery. Unlike [16, 18] that study noiseless settings and require no early stopping. [11, 12] mathematically characterize the role of early stopping and empirically show that it may be necessary to prevent gradient descent from over-fitting to the noise. These works suggest that the inductive bias endowed by gradient descent may be influenced not only by the choice of parametrization, but also algorithmic choices such as initialization, learning rate, and the number of iterations. However, our understanding of such gradient dynamics is incomplete, particularly in the context of deep architectures; see Table I for some comparisons.
Contributions. Our focus in this paper the implicit regularization of (standard) gradient descent for high dimensional sparse regression, namely implicit sparse regularization. Let us assume ground- truth sparse linear model and suppose we observe n noisy samples (x,: Vi), such that y = Xw" + E: a more formal setup is given in Section 2. Using the samples, we consider gradient descent on squared loss Xw - yll² with no explicit sparsity regularization. Instead, we write the parameter vector w in the form
u V with N > 2. Now, the regression function fx, u, v) (x, u v can be viewed as a depth-N diagonal linear network [18]. Minimizing the (now non-convex) loss over u and v with gradient descent is then analogous to training this depth-N network.
Our main contributions are the following. We characterize the impact of both the depth and early stopping for this non-convex optimization problem. Along the way, we also generalize the results of [11] for N >> 2. We show that under general depth parameter N and an incoherence assumption on the design matrix, gradient descent with early stopping achieves minimax optimal recovery with sufficiently small initialization Wo and step size 17. The choice of step size is of order O(1/N2.. Moreover, the upper bound of the initialization, well as the early-stopping window, increase with N, suggesting that depth leads to a more accessible generalizable solution on gradient trajectories.
Techniques. At a high level, our work continues the line of work on implicit bias initiated in [11, 12, 18] and extends to the deep setting. Table highlights key differences between our work and [11, 13, 18]. Specifically, Woodworth et al. [18] study the interpolation given by the gradient flow of the squared-erros loss function. Vaskevicius et al. [i1] analyze the finite gradient descent and characterize the implicit sparse regularization on the recovery of true parameters with N = 2. Lastly, Gissin al. [13] discover the incremental learning dynamic of gradient flow for general N but in an idealistic model setting where u 2 0, v 0, & 0, uncorrelated design and with infinitely many samples.
Table 1: Comparisons with closely related recent work. GF/GD: gradient flow/descent, respectively.
Design Matrix
In Noise
Depth
Early Stopping
GD vs. GF
Remark
Vaskevicius al. (2020) [LI]
RIP
N 2 N 2
GD
recovery
Gissin et al. (2020) [13]
uncorrelated X
X
GF
interpolation
Woodworth et al. (2020) [18]
N = 2, >
X
GF
interpolation
This paper
p-coherennc
N>
/
GD
recovery
At first glance, one could attempt a straightforward extension of the proof techniques in [11] to general settings of N > 2. However, this turns out to be very challenging. Consider even the simplified case where the true model w* is non-negative, the design matrix is unitary (i.c., n ' = D), and the noise is absent (g 0); this is the setting studied in [13]. For each entry wy of w, the 1hh iterate of gradient descent over the depth-N reparametrized model is given by:
W0 11,11 = =W,,e (1 + wi,
1- 2 (w] - ww.)) N
2

---

which is no longer simple multiplicative update. As pointed out in [13] (see their Appendix C), the recurrence relation is not analytically solvable due to the presence of the (pesky) term w when
N >> 2. Moreover, this extra term Wi, 1- leads to widely divergent growth rates of weights with different magnitudes, which further complicates analytical bounds. To resolve this and rigorously analyze the dynamics for N > 2, rely novel first order, continuous approximation study growth rates without requiring additional assumptions on gradient flow, and carefully bound the approximation error due to finite step size; see Section 4.
2 Setup
Sparse regression/recovery. Let w* E IR be p-dimensional sparse vector with k non-zero entries. Assume that observe n data points (x,, yi) E IR? x such that yı (x,, + for = I...., n, where & = (E.....; En) is the noise vector. We do not assume any particular scaling between the number of observations n and the dimension p. Due the sparsity of w", however, we allow < p.
The linear model can be expressed in the matrix- vector form:
Xw" + E.
with the n x design matrix X = [x] x,]" where x; denotes the 7th row of X. We also denote = X X i...... .pl., where X; denotes the 7th column of X.
The goal of sparse regression is to estimate the unknown, sparse vector from the observations. Over the past two decades, this problem has been topic of active research in statistics and signal processing [25]. common approach to sparse regression penalized least squares with sparsity- induced regularization such as ln or ε penalties/constraints, leading to several well-known estimators [25, 26, 27] and algorithms [28, 29]. Multiple estimators enjoy optimal statistical and algorithmic recovery guarantees under some conditions of the design matrix X (e.g.. RIP [30]) and the noise &.
We deviate from the standard penalized least squares formulation and instead learn w via polyno- mial parametrization:
N u U
where N 2 and N [a 2p for any z [z,,... [ 2 R.. The regression function f(x, v) = (x, u N ) induced by such a parametrization is equivalent to a N N-layer diagonal linear network [18] with 2p hidden neurons and the diagonal weight matrix shared across all layers.
Given the data (X,y y) observed (1), we analyze gradient descent with respect to the new parameters and v over the mean squared error loss without explicit regularization:
L(u, v) X(u - -1
u. u RP.
Even though the loss function yields the same value for the two parametrizations, L(u, v) is non- convex in u and v. Unlike several recent studies in implicit regularization for matrix factorization and regression [16, 18. 13], we consider the noisy setting, which is more realistic and leads to more insights into the bias induced during the optimization. Because of noise, the loss evaluated the ground truth (i.e., any v such that w* = N v') is not necessarily zero or even minimal.
Gradient descent. The standard gradient descent update over L(u, v) reads as:
Up vo = al,
(1-1) (uc. - aC(u,, vt).
t t= 0,1,....
(2)
a(u vz)
Here, 17 > 0 is the step size and 0 is the initialization of algorithm presented in (2), and at each step t, we can estimate the signal of interest by simply calculating W, u,a v." We consider constant initialization for simplicity sake. Our results apply for random initialization concentrating on a small positive region with a probabilistic statement.
In general, we analyze the
Vaskevicius et al. [11] establish the implicit sparse regularization of gradient descent for N = 2 and show minimax optimal recovery, provided sufficiently small a and early stopping. Our work aims to generalize that result to N 2 and characterize the role of N in convergence.
3

---

Notation. We define = fi fI.....pp : * 0} and 5 = [1,...,P}l. The largest and smallest absolute value on the support denoted wmax maxies |wm] and w minkes |w We use 1 to denote the vector of all ones and 1ş denotes the vector whose elements on 5 are all one and otherwise. Also, @ denotes coordinate-
multiplication. We denote 8, 1s @ wy and = g= Ô We meaning the signal part and error part at each time step t. We use A and V to denote the pointwise maximum and minimum. The coordinate-wise inequalities are denoted as x. We denote inequalities up to multiplicative absolute constants by S. which means that they do not depend on any parameters of the problem.
Definition 1. Ler X E R be matrix with lz-normalized columns XI...., Xp. ie., |X = for all i. The coherence μ = p(X) of the matrix X is defined as
== max
(Xi;X))
151415P
The matrix is said to be satisfying j-incchherence.
The coherence is measure for the suitability of the measurement matrix in compressive sensing [31]. In general, the smaller the coherence, the better the recovery algorithms perform. There are multiple ways to construct sensing matrix with low-incoherence. One of them is based on the fact that sub-Gaussian matrices satisfy wwwinccherenne property with high probability [32, 33]. In contrast to the coherence, the Restricted Isometry Property (RIP) is powerful performance measure for guaranteeing sparse recovery and has been widely used in many contexts. However, verifying the RIP for deterministically constructed design matrices is NP-hard. On the other hand, coherence a computationally tractable measure and its use in sparse regression is by now classical [33, 34). Therefore, in contrast with previous results [I]] (which assumes RIP), the assumptions made in our main theorems are verifiable in polynomial time.
3 Main Results
We now introduce several quantities that are relevant for our main results. First, the condition number r wmax/ "min plays important role when we work on the incoherence property of the design matrix. Next, we require an upper bound on the initialization which depends on the following terms:
o maaes Winn C, N) = (1)
2/(N-2/ -2)
(wmax) (NV 2/(N-2)
(wimit) (NV 4/(N-2)
8
log M
log Minta
(wiii N) = (2 2
2
N (witin) 4 * -1)x (wiin)) )
Finally, define
ç= 5= wiin
1
200
| V 200c.
n
We are now ready to state the main theorem:
Theorem 1. Suppose that k 2 1 and X/ satisfies p-incoherence with S 1/kr. Take any precision e O, and let the initialization be such that
4/N
0<as
A D( Wmin e, N, A (w N).
(3)
p+1)
For any iteration that satisfies
Ti(w*, ar
N,,W",,,,,,,,.... N,n.S,))
(4)
where Ti(.) and T are given in (25) of the Appendix, the gradient descent algorithm (2) with step N
size 17 I 8 NONN-2YN yields the iterate w, with the following property:
4 Ve ku
if E S and w "ii
1 XTg g
Vc,
|Wa,i will x
[XX 2)
Isll Ve
if E S and winn
x
Ve,
N/4
if $ S.
(5)
4/N
In the special case w² = 0, if <
c
.ns N(N-1)aa 2n7 and S Tu(w*, a, N, n, S.C),
p+1
then we have (wri - wil < a N/1 Vi.

---

Theorem 1 states the convergence of the gradient descent algorithm (2) in foc norm. The exact formula of (.) and (-) is omitted here due to the space limitation. We ensure that T-)() > T:(-) so that there indeed exists some epochs to early stop at. The error bound on the signal is invariant to the choice of N 2 2, and the overall bound generalizes that of [11] for N We also establish the convergence result in 22-norm in the following corollary:
Corollary 1. Suppose the noise vector & has independent p2-sub-Gaussice entries and = [2g(2p) Under the assumptions of Theorem 1, the gradient descent algorithm (2) would produce iterate we satisfying ||: 11 - (ko² log with probability at least 1 - 1/(8p²)
2
Note that the error bound we obtain is Munimax--ppimmll which is the same as [11] in the N case. However, with some calculation, the sample complexity we obtain here is 2 k2r², while the sample complexity in [11] is Z k2 log" log p/ k. Although neither our work nor [11] achieved the optimal sample complexity k &logp/ k; the goal of this work understand how the depth parameter affects implicit sparse regularization.
Let us now discuss the implications of Theorem and the role of initialization and early stopping:
(a) Requirement on initialization. To roughly understand the role of initialization and the effect of N, we look at the non-negative case where w and w uº\ This simplifies our discussion while still capturing the essential insight of the general setting. At each step, the "update" on w can be translated from the corresponding gradient update of u w/N as
Wp 1,
W We O (1- 2N
x ('X(w:-w') - 3 w
(N-2)/N
(6)
In order to guarantee the convergence, we require the initialization error outside the support can be controlled. On the other hand, too small initialization slows down the convergence of the signal. Interestingly, the choice of N affects the allowable initialization that results in guarantees on the entries inside and outside the support.
be sufficiently small the
Specifically, the role of N is played by the term w! (N-2)/N in (6), which simply disappears as N = 2. Since this term only affects the update of W entry-wise, we only look a particular entry un of W.. Let W. represent an entry outside the support. For N > 2, the term w (N-2)/N is increasingly small as N increases and w/ 1. Therefore, with a small initialization, it remains true that w; < for the early iterations. Intuitively, this suggests that the requirement on the upper bound of the initialization would become looser when N gets larger. This indeed aligns with the behavior of the upper bound we derive in our theoretical results. Since = wnp I/N increases naturally with N, we fix Wo = N instead of a to mimic the same initialization in terms of wo, for the following comparison.
We formalize this insight in Theorem 3 in Appendix A and show the convergence of (6) under the special, non-negative case. Note that, in terms of initialization requirement, the only difference from Theorem is that no longer require the term (wiin .)) in (3).
We investigate how the depth N influences the requirement on initialization due to the change on gradient dynamics. We rewrite 4 b(wtaaaz Wmita e, N) in terms of Wi a²", and therefore the upper bound for wo under the simplified setting of non-negative signals (Theorem 3) is
Remark 1.
(1) 8
2N/(N-2)
(
((w (w ) (NN-)/N 2N/(N-2)
(w++ min JNN 4N/(N-2)
Wo I
A
log WHaa
log
W min
We start by analyzing each term in the upper bound. First, we notice that 2N/(N-2) is increasing with respect to N. For the second term,
(w+ (w (NN -2/2 2N/(N-2)
(w )
log
(log W.max )2N/(N-2)
the denominator gets smaller as N increases when we pick the error tolerance parameter small. Therefore, we get that the second term is getting larger N increases. The last term
5

---

(we (wuiin)) 1(N-2)/N (N/(N-2)
follows similar argument. We that it is possible to pick larger
log initialization Wo for larger N. We will demonstrate that below our experiments.
(b) Early stopping. Early stopping is shown to be crucial, if not necessary. for implicit sparse regularization [11, 12]. Interestingly, [13, 18] studied the similar depth-N polynomial parametrization but did not realize the need of early stopping due to an oversimplification in the model. We will discuss this in details in Section 4. We are able to explicitly characterize the window of the number of iterations that are sufficient to guarantee the optimal result. In particular, we get lower bound of the window size for early stopping to get a sense of how changes with different N.
Theorem 2 (Informal). Define the early stopping window size as Tu(w", a, N, N,N.S. Ti(w", a, N, n, (.e), the difference between the upper bound and lower bound of the number of iterations (4) of Theorem Fixing and 17 for all N, the early stopping window size is increasing with N under mild conditions.
We defer the formal argument and proof of Theorem to Appendix D.3. We note that the window we obtain in Theorem is not necessarily the largest window that allows the guarantee, and hence the early stopping window size can effectively regarded a lower bound of that derived from the largest window. We note that precise characterization of the largest window is difficult. Although we only show that this lower bound increases with N, we see that the conclusion matches empirically with the largest window. Fix the same initialization = 0.005 and step size 7 = 0.01 for N = 2, 3, 4, we show the coordinate path in Figure We can see that as N increases, the early stopping window increases and the error bound captures the time point that needs stopping guite accurately. The experimental details and more experiments about early stopping is presented in Section 5.
N=2, window size- 528
N-3, window size 19178
N-4, window siz- 1485577
122-1445577
C S Holll ertrr bound
5
c Hell
encr bound
emor bound
0
0.5
0.0
1000
100000
200000
33000
30003
Number itorations
Figure 1: The black line indicates the early stopping window for different N = 2, The blue line is the coordinate path for each entry on the support. The red line indicates the absolute value of the largest entry on the coordinate path outside the support. We use the orange line to indicate the requirement outside the support for early stopping.
Remark 2. Similar to Theorem 2, we look at how initialization scale affects the early stopping window for any fixed N > 2. With n fixed, the early stopping window is increasing the initialization a decreases.
We defer the detailed calculation Section D.4. This generalizes the finding that vanishing ini- tialization increases the gap between the phase transition times in [14] from N = 2 to any N > 2.
4 Proof Ingredients
The goal of this paper is to understand how generalization and gradient dynamics change with different N 2. For N 2, gradient descent yields both statistically and computationally optimal recovery under the RIP assumption
[11]. The matrix formulation of the same type of parametrization considered in the setting of low-rank matrix recovery, and exact recovery can be achieved in the noiseless setting [15, 16]. The key proof ingredient is to reduce the convergence analysis to one-dimensional iterates and differentiate the convergence on the support from the error outside the support. Before get into that, we conduct simplified gradient flow analysis.

---

4.1 A Simplified Analysis
Consider a simplified problem where the target signal w is non negaeteeeee, n n x I and the noise is absent. We omit the reparametrization of v like before and the gradient descent updates on will be independent for each coordinate. The gradient flow dynamics of w u is derived as
Ow, dw, Su, aw, Oc = 2 - we ) 2- &
Ot
Ou: Ot Ou, Ou,
for all E f1,2...., p). Notice that w; increases monotonically and converges to w if w is positive or otherwise keeps decreasing and converges to if W = 0. As such, we can easily distinguish the support and non-support. In fact, gradient flow with dynamics as in (7) would exhibit behavior of "incremental learning" - the entries are learned separately, one at time [13]. However, with the presence of noise and perturbation arising from correlated designs, the gradient flow may end up weer-fitting the noise. Therefore, early stopping as well as the choice of step size is crucial for obtaining the desired solution [1]]. We use (7) obtain a gradient descent update:
Wi,++1 1++ wr (1 + 2N n ws,.)wi, 1- &
1- The gradient descent with N 2 is analyzed in [11]. However, when N 2, the presence of wie imposes an asymmetrical effect on the gradient dynamics. The difficulty of analyzing such gradient descent (8) is pointed out in [13]. More specifically,, the recurrence relation is not solvable. However, gradient descent updates still share similar dynamics with the idealized gradient flow in (7). Inspired by this effect, we are able to show that the entries inside the support and those outside the support learned separately with practical optimization algorithm shown in (2) and (12). As a result, we are able to explore how the depth N affects the choice of step size and early stopping criterion.
4.2 Proof Sketch
Growth rate of gradient descent. We adopt the same decomposition as illustrated [11], and define the following error sequences:
b Xc,
1 X.T. n
P. = --xxxxx--1 1xxx-1) (st w*), -s:-
n
where and s; stand for error and signal accordingly, and the definitions can be found in (13) in Appendix. We can then write the updates on S; and e as
St+1 = @ (1 - (s - w + P. + b.) O S;
(N-2)/N
(10)
e = e, 3 (1 2Nr + b.) و e, (N-21/N
To illustrate the idea, we think of the one-dimensional updates {sr {st and (er (2) ignore the error perturbations P, and b, in the signal updates (8th22- and treat Pr + byllo S B in the error updates {ex (200
St+1 = sc(1 - 2Nn(s - (N-)/NN
= - Be (N 2NNN)
(1I) We use the continuous approximation to study the discrete updates. Therefore, can borrow many insights from the analysis about gradient flow to overcome the difficulties caused by w.r as pointed out equation (8). With proper choice of step size the number of iterations T₁ for s, converging w is derived as
T: T <
w+ a
8141 St
s(2N 22/N do +
2 8t) (2N 2)/N
N2
22N
The number of iterations T, for e staying below some threshold a N/4 is derived as
N/4
Ctt1 Ct
1
Tw
4N (2N-2)/N
4N2
e(2N 2)/N
7

---

With our choice of coherence in Theorem 1, we are able to control B to be small so that Tj is smaller than T.. This means the entries on the support converge the true signal while the entries outside the support stay around O, and we are able to distinguish signals and errors.
Dealing with negative targets. We now illustrate the idea about how generalize the result about non-negative signals to general signals. The exact gradient descent updates on u and v are given by:
U++1 Ur
1 1-22N
x (X((, w*) - u N
(12)
| [ - w*) -) 3 v N-2
V++ v
1 2Nr
The basic idea is to show that when w is positive, of remains small up to the early stopping criterion, and when wi is negative, uf remains small up to the early stopping criterion. We turn to studying the gradient flow of such dynamics. Write r(t) x (X((() w*) &. It easy to verify that the
gradient flow has a solution:
u(l) 2 ++2 2)m L r(v)dv)
N
v(t) 12-N1- - -N(N 2)m ''" r(u)dv
We may observe some symmetry here, when wi,t is large, Vi, must be small. For the case w; O. to ensure the increasing of u,, and decreasing of Ug, as we desire, the initialization needs to be smaller than W/ which leads to the extra constraint on initialization (w c) with order of O(w as defined before. It remains to build the connection between gradient flow and gradient descent, where again uses the continuous approximation before. The detailed derivation is presented in Appendix B.3.
Simulation Study
We conduct series of simulation experiments' to further illuminate our theoretical findings. Our simulation setup is described as follows. The entries of X are sampled as i.i.d Rademacher random variables and the entries of the noise vector & are i.i.d. (0, o²) random variables. We let w =-1s- The values for the simulation parameters are: n = 500, p = 3000, k = 5, 7 = 1, o = 0.5 unless otherwise specified. For f2-plots each simulation is repeated 30 times, and the median & error is depicted. The shaded area indicates the region between 25th and 75th percentiles pointwisely.
Convergence results. We start by showing that the general choice of N leads to the sparse recovery, similar to N = 2 in [1.]. as shown in our main theorem. We choose different values of N to illustrate the convergence of the algorithm. The result on simulated data is shown in Figure 2, and we defer the result on MNIST to Appendix E. Note that the ranges in the r-axes of these figures differ due to different choice of N and n,. We observe that N increases, the number of iterations increases significantly. This is due to the term u N- and v N-2 in (12), and the step size R N With a very small initialization, it takes large number of iterations to escape from the small region (close to 0).
Larger initialization, As discussed in Remark I, the upper bound on initialization gets larger with larger N. We intentionally pick a relatively large a " = 2 x 10-3 where the algorithm fails to converge for N With the same initialization, the recovery manifests as N increases (Figure 3).
Early stopping window size. Apart from the coordinate path shown in Figure 1, we obtain multiple runs and plot the log-l2 error (the logarithm of the f2-error) of the recovered signals further confirm the increase of early stopping window, as shown in Section 3. Note that for both Figures 1 and 4, we set = 100 and p 200. Since a would decrease quickly with N. which would cause the algorithm takes large number of iterations to escape from the small region. We fix a = 10-5 instead of fixing a for Figure
Incremental learning dynamics. The dynamics of incremental learning for different N is discussed in [13]. The distinct phases of learning also observed in sparse recovery (Figure 5), though we do
The code is available on ht https: sttps://githbb com/ 1angyyua211/Immmiiiitt Saar--Sppaarreeee Regul Raaasse-Rguulaizzaiion arization.
8

---

N-2
N-3
N-5
1-.55 ||oll
16.88
||o||
10)
20
00
03
80
100
500
1000
1500
13000
20700
30000
Number ieeatione
Figure 2: Coordinates paths for different choice of N 2,3, with a. 10 10-6 and 1) = 1/ (5N2).
N-2
N--3
N-10
F..55 [|||]-
1.25
|4/1-
2 0.75
0.75
213
080
020
900
1000
500
2000
1003
2000
1000
2000
3000)
4000
5000
Number iterations
Figure 3: The effect of N on the initialization a with 7) 1/(5
N-22 window 410
N-3, winslow siee 3096
N-4, window sire- 8060
-6
7000
10000
0000
1000
5000
10000)
30000
15200
Number io atiens
Figure 4: log-& error of N 3, 4 with the fixed step size 77 0.01.
not provide theoretical justification. Larger values of N would lead to more distinct learning phases for entries with different magnitudes under the same initialization a and step size 77.
N
N-3
N-5
8
[[lll
3.0
3050
5000
5000
19000
Number iteratioss
Figure 5: Coordinates paths for N = 2, 5. The entries of w on the support S now [1, The initialization is a N 10 and the step size is r7 = 10 for all N.
Kernel regime. As pointed out in [18], the scale of initialization determines whether the gradient dynamics obey the "kernel" or "rich" regimes for diagonal linear networks. We have carefully analyzed and demonstrated the sparse recovery problem with small initialization, which corresponds to the "rich" regime. To explore the "kernel" regime in a more practical setting, we set 500, p= 100, and the entries of w* are i.i.d. (/ 1) random variables. The noise level a 25, and the initialization and step size is set as N 1000 and 77 10-7 for all N. Note that we not working

---

in the case & as [18]. We still observe that the gradient dynamics with large initialization (Figure 6) can be connected to ridge regression if early stopping deployed.
N
N
No:4
8.0
8.0
rdgee
ridge
ridee
7.6
7.
7.5-
seuare
6.6
0.5
0.5
Berations
Figure 6: log-l2 error of N = 2,3,4 for ridge regression setting. The ridge regression solution is selected by 5-fold cross validation.
6 Conclusions and Future Work
In this paper, we extend the implicit regularization results in [11] from N = to general N > and further study how gradient dynamics and early stopping is affected by different choice N. We show that the error bound is invariant with different choice N and yields the minimax optimal rate. The step size is of order (11/N2). The initialization and early stopping window gets larger when increasing N due to the changes on gradient dynamics. The incremental learning dynamics and kernel regime of such parametrizations which is left for future work.
empirically shown, however not theoretically justified,
The convergence result can be further improved by relaxing the requirement on the incoherence of design matrix from μ Z kwy ur to K k log(wwas>/w we j. similar to [11]. Overall, we believe that such an analysis and associated techniques could be applied for studying other, deeper nonlinear models in more practical settings.
Acknowledgements
This work was supported in part by the National Science Foundation under grants 19F-1934904, CCF-1815101, CCF-2005804, and DMS-1711952.
References
[1] Chiyuan Zhang. Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint arXiv:1611.03530, 2016.
[2] Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In International Conference Machine Learning, pages 1225-1234. PMLR, 2016.
Mingehen Li, Mahdi Soltanolkotabi, and Samet Oymak. Gradient descent with early stopping is provably robust to label noise for overparameterized neural networks. In International conference on artificial intelligence and statistics, pages 43 4313-4324. PMLR, 2020.
[4] Behnam Neyshabur, Ryota Tomioka, Ruslan Salakhutdinov, and Nathan Srehro. Geometry of optimization and implicit regularization in deep learning. arXiv preprint arXt::/705.03077/ 2017.
[5] Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The implicit bias gradient descent on separable data. The Journal of Machine Learning Research, 19(1):222-22778 2018.
[6] Mikhail Belkin, Daniel Hsu. Siyuan Ma, and Soumik Mandal. Reconciling modern machine-learning practice and the classical bias-variance trade-off. Proceedings of the National Academy of Sciences of the United States of America, 116(32):15849 15854, 2019.
10

---

[7] Vidya Muthukumar, Kailas Vodrahalli, Vignesh Subramanian, and Anant Sahai. Harmless interpolation of noisy data in regression. IEEE Journal on Selected Areas in Information Theory, 1(1):67-83, 2020.
[8] Andrew M Saxe, James I. McClelland, and Surya Ganguli. Fxact solutions to the nonlinear dynamics of learning in deep linear neural networks. arXiv preprint arXiv:1312.6120, 2013.
[9] Suriya Gunasekar, Jason D Lee, Nathan Srebro, and Daniel Soudry. Implicit bias of gradient descent on linear convolutional networks. Advances in Neural Information Processing Systems, 2018:9461-9471, 2018
[10] Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Characterizing implicit bias in terms of optimization geometry. In International Conference on Machine Learning, pages 1832-1841. PMLR. 2018.
[11] Tomas Vaskevicius, Varun Kanade, and Patrick Rebeschini. Implicit regularization for optimal sparse recovery. In Advances in Neural Information Processing Systems, pages 2972-2983, 2019.
[12] Peng Zhao, Yun Yang, and Qiao-Chu He. regularizionn via hadamard product over- vve-parramttrization in high-dimensional linear regression. arXiv preprint arXiv:1903.0936) 2019.
[13] Daniel Gissin, Shai Shalev-Shwartz, and Amit Daniely. The implicit bias of depth: How incremental learning drives generalization. arXiv preprint (Tti::1999.1255555 2019.
[14] Gauthier Gidel, Francis Bach, and Simon Lacoste-Julien. Implicit regularization discrete gradient dynamics in linear neural networks. arXiv preprint /904. /9262.2222, 2019.
[15] Suriya Gunasckar, Blake Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, and Nathan Srebro. Implicit regularization in matrix factorization. In 2018 Information Theory and Applications Workshop (ITA), pages 1-10. IEEE, 2018.
[16] Yuanzhi Li, Tengyu Ma, and Hongyang Zhang. Algorithmic regularization in over-parameterized matrix sensing and neural networks with quadratic activations. In Conference On Learning Theory, pages 2-47. PMLR, 2018.
[17] Sanjeev Arora, Nadav Cohen, Wei Hu, and Yuping Luo. Implicit regularization in deep matrix factorization. arXiv preprint arXiv: 13655, 2019.
[18] Blake Woodworth, Suriya Gunasekar, Jason D Lee, Edward Moroshko, Pedro Savarese, Itay Golan, Daniel Soudry, and Nathan Srebro. Kernel and rich regimes in overparametrized models. In Conference on Learning Theory, pages 3635-3673, PMLR, 2020.
[19] Francis Williams, Matthew Trager, Claudio Silva, Daniele Panozzo, Denis Zorin, and Joan Bruna. Gradient dynamies of shallow univariate relu networks. arXiv preprint arXiv: 1906..0894... 2019.
[20] Edward Moroshko, Blake E Woodworth, Suriya Gunasckar, Jason Lee, Nati Srebro, and Daniel Soudry, Implicit bias in deep linear classification: Initialization scale vs training accuracy. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 22182-22193. Curran Associates, Inc., 2020.
[21] Zhiyuan Li, Yuping Luo, and Kaifeng Lyu. Towards resolving the implicit bias of gradient descent for matrix factorization: Greedy low-rank learning. arXiv preprint wrXiv:2012.09833 2020.
[22] Gergely Neu and Lorenzo Rosasco. Iterate averaging as regularization for stochastic gradient descent. In Conference On Learning Theory, pages 3222-3242. PMLR, 2018.
[23] Garvesh Raskutti, Martin J Wainwright, and Bin Yu. Early stopping and non non-parametric regression: an optimal data-dependent stopping rule. The Journal of Machine Learning Research, 15(1):335-366, 2014.
[24] Arun Suggala, Adarsh Prasad, and Pradeep K Ravikumar. Connecting optimization and regularization paths. Advances in Neural Information Processing Systems, 11110068810619, 2018.
[25] Robert Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society: Series B (Methodologicall) 58( ):267-288, 1996.
[26] Scott Shaobing Chen, David L Donoho, and Michael A Saunders. Atomic decomposition by basis pursuit. SIAM review, 43(1): 2001.
[27] Emmanuel Candes, Terence Tao, et al. The dantzig selector: Statistical estimation when is much larger than Annals of statistics, 35(6):2313 13333331,11322111,-- 2007.

---

[28] Kristian Bredies and Dirk A Lorenz. Linear convergence of iterative soft-thresholding. Journal of Fourier Analysis and Applications, 14(5-6):11-8377 2008.
[29] Alekh Agarwal, Sahand Negahhan, and Martin J Wainwright. Fast global convergence of gradient methods for high-dimensional statistical recovery. The Annals of Statistics, pages 2452 2482, 2012.
[30] Emmanuel J Candes and Terence Tao. Decoding by linear programming. IEEE transactions on information
theory, 51(12):4203-4215 2005.
[31] Simon Foucart and Holger Rauhut. An invitation to compressive sensing. In A mathematical introduction compressive sensing, pages 1-39. Springer, 2013.
[32] Lawrence Carin, Dehong Liu, and Bin Guo. Coherence, compressive sensing, and random sensor arrays.
IEEE Antennas and Propagation Magazine, 53(4):28-39, 2011.
[33] David L Donoho, Michael Elad, and Vladimir N Temlyakov. Stable recovery of sparse overcomplete representations in the presence of noise. IEEE Transactions information theory, 52(11)6-18, 2005.
[34] Emmanuel J Candes, Yonina C Eldar, Deanna Needell, and Paige Randall. Compressed sensing with coherent and redundant dictionaries. Applied and Computational Harmonic Analysis, 31(1):59-73, 2011.
12


Reviews:
[{"review_id": "YcUujXJ7rcw", "reviewer": "Reviewer_LYJJ", "summary": "This paper studies the implicit bias of gradient descent on the depth-N diagonal linear network for the problem of sparse recovery. It shows the convergence results for gradient descent and provides error bounds to the ground truth sparse signal. The result highlights the importance of early stopping in preventing overfitting and shows the role of network depth in extending the stopping window.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper is well-written. I did not go through all the proofs but the proof ideas are clear to me. This work makes contributions in studying the deep network model (N>2) with more realistic settings: gradient descent, the presence of noise. Therefore I recommend “accept”.\n\nComments:\n\n1. It seems to me that Theorem 1 does not apply to the case of N=2, since $\\Phi$ and $\\Psi$ are undefined. It would be great if the author can improve the theorem by including the case of N=2. Also, in line 149, it states that “the overall bound generalizes that of [9] for N=2”, I don’t see this as a direct generalization because [9] assumes RIP and this paper assumes $ \\mu$-coherence.\n\n\n2. For the initialization, u_0 and v_0 are initialized to be all one vectors scaled by small $\\alpha$. Can we have similar implicit bias if one randomly initializes the entries of u_0 and v_0 with a small variance? \n\n\n3. In other models where implicit bias arises under small initialization (Gidel’19), the initialization scale affects the time windows for early stopping. The author may want to discuss the effect of $\\alpha$ on the time window.\n\n\nMinor comment: line 140, the upper bound for $\\mu$ is 1/kr, what is r?\n\nReference:\n\nGauthier Gidel, Francis Bach, and Simon Lacoste-Julien. Implicit regularization of discrete gradient\ndynamics in linear neural networks. arXiv preprint arXiv:1904.13262, 2019.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Please refer to the comments.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "RvDk6zxqsM3", "reviewer": "Reviewer_WsVt", "summary": "In this work, the authors study the implicit bias of gradient descent for sparse linear regression when parameterizing the ground truth signal as a depth-$N$ diagonal linear network. Previous works have shown that when utilizing a Hadamard parameterization $w = u \\odot u - v \\odot v$, gradient descent exhibits an implicit bias towards sparse solutions, without any explicit regularization encouraging sparsity. Follow-up work has also considered the depth-$N$ case in simplified settings (e.g., without noise, positive signals, and idealized measurement setups). The authors extend this analysis to the general depth-$N$ case $w = u^N - v^N$ in the presence of noise. They prove that when the measurement matrix is $\\mu$-incoherent with sufficiently small $\\mu$ and noise is present, there is an early stopping window depending on the problem parameters where any iterate during this time is close in $\\ell_{\\infty}$ norm to the underlying ground truth sparse signal. These results hold for any depth $N \\geqslant 2$ and showcase that depth allows for larger initialization sizes and that the early stopping window grows with deeper parameterizations. Experimental evidence on toy examples is also provided corroborating several elements of the proposed theory.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "# Originality\n\nThe present work appears to be a non-trivial extension of the results in [9] to the depth-$N$ case. While some of the analysis appears similar, some of the techniques in the quadratic case do not immediately port over to the depth-$N$ case and this work offers insights into the benefits of depth. On this note, I believe another work along these lines that should be cited is Li et al (ICLR 2021), who also showed in depth-$N$ matrix factorization, a deeper parameterization allowed for larger initialization sizes.\n\n- Zhiyuan Li, Yuping Luo, and Keifeng Lyu. Towards Resolving the Implicit Bias of Gradient Descent for Matrix Factorization: Greedy Low-Rank Learning. ICLR 2021\n\n# Quality\n\n- Strengths: - The analysis presented is for general depth $N \\geqslant 2$ and no restrictions on the sign of the ground truth signals entries. - The results apply to gradient descent, as opposed to usual simpler analyses for gradient flow. - The impact of depth is discussed in multiple ways in the results. In particular, the results show that “deeper” diagonal networks allow for larger initialization sizes to still succeed and that the early stopping window becomes larger with larger values of $N$. - Various aspects of the theory are experimentally shown in toy examples.\n\n- Weaknesses: - It seems that the condition number $r = w_{\\max}^*/w_{\\min}^*$ is integral to the analysis, but there is little discussion about how it influences the results. For example, given a signal with $w_{\\max}^* = O(1)$ and $w_{\\min}^* = O(1/k)$, how would the generalization error in Corollary 1 scale? This would require a very tight incoherence parameter $\\mu \\leqslant 1/k^2$, so I wonder if for certain design matrices $X$ (e.g., subGaussian), this could result in sub-optimal sample complexity scalings.\n\n# Clarity\n\nOverall, the paper is well-written and previous work seems to be properly placed in the context of the results. The proof sketches and discussions on the theorem’s assumptions and implications were quite helpful in parsing the result.\n- Typos: pg 4 line 136 “property of design” -> “property of the design”\n\n# Significance\n\nWhile the implicit bias for the quadratic case is known and well-studied, the extension to the depth-$N$ case appears non-trivial. It is good to know that such a result does hold for the depth-$N$ case and the result adds to the literature on the various benefits of depth (albeit in a simplified setting).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This work does not have a clear societal impact. The authors have discussed some limitations of their work, such as the scaling on the coherence parameter $\\mu$. Some example cases for certain design matrices and how many measurements are required to satisfy $\\mu \\leqslant 1/kr$ for various $r$ and distributions on $X$ would be good to see. In terms of other limitations, a short discussion or mention of what other phenomena concerning depth has not been theoretically shown, for example the incremental learning dynamics verified experimentally but not proven.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "JBTztOLnNZY", "reviewer": "Reviewer_JHGS", "summary": "In this paper the authors study implicit sparse regularization for diagonal linear networks. Specifically, the authors extend the previous result of Vaskevicius et al. [9] to the case of depth>2, showing that for noisy regression under a relaxed assumption on the inputs, increasing depth enlarges the scale of working initialization and the early-stopping window. ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is interesting and well written. However, my main concern is that this paper is quite similar to Vaskevicius et al. [9]. So, it would be good to add a detailed comparison to [9], e.g. state their bound and compare to the bound in this paper. \n\nIn addition, the empirical part is rather weak. I think it would be good to show empirically that the conclusions in this paper for the simple model hold also in more realistic deep networks trained on real data.\n\nComments:\n- It would be good to define “minimax optimal recovery” and explicitly show that the bound is indeed minimax optimal.\n- lines 65-66: “Woodworth et al. [16] study the gradient flow of the squared-error loss function in the noiseless case” – I think their result is rather general (noiseless or noisy). For any dataset (X,Y), taking $\\alpha\\rightarrow 0$ results in a minimum L1-norm solution.\n Also in line 184 “but did not realize the need of early stopping due to an oversimplification in the model”. Again, [16] discuss the implicit bias at convergence to global minima, so early stopping is irrelevant there.\n- It would be good to discuss special cases in Theorem 1 – the noiseless case and the case $k=p$. Specifically, it seems that in the noiseless case $T_l$ and $T_u$ are undefined.\n- I think the following two papers are relevant for discussion:\n\nhttps://arxiv.org/abs/1903.11680\n\nhttps://arxiv.org/abs/1903.09139\n- When comparing the window size for different $\\alpha$ (theorem 2 and Figure 1), I think that need to fix $\\alpha^N$ and not $\\alpha$, since $\\alpha^N$ is the initialization scale of the model for any $N$.\n- Can you explain Eq. (7) ? Why $\\eta$ appears there, and did you use expectation of the loss over $X$, like in [11] ?\n- In Figures 1 and 4, please explain how did you determine the location of the dashed black lines of the window.\n- There is an unclear discrepancy between Figure 1 and Figure 4, since Figure 1 uses $\\alpha$ but Figure 4 uses $\\alpha^N$. I believe both figures should use $\\alpha^N$ and show similar window size.\n- Please explain why in Figures 1,4,5 the step-size is fixed for all $N$ but in  Figures 2,3 it is ~$\\frac{1}{N^2}$.\n- Would be good to add a discussion of $\\mu$-coherence in simulations and the effect of the value of $\\mu$. Specifically, does $\\mu$-coherence hold for the $X$ used in simulations ?\n- It is not clear what is the point of Figure 5 ? Incremental learning is not discussed/proved in this paper, and Figure 5 is just the same as the figures in [11].\n- The discussion about kernel regime (Figure 6) seems detached from the paper. The relation between early stopping and ridge regression is well established in prior work, e.g.:\n\nhttps://arxiv.org/abs/1903.11680\n\nTypos:\n- line 10: \"an\" in not needed\n- line 179: third term -> second term\n- line 240: converges -> converge\n- line 270: Figure 4 -> Figure 1\n- line 274: We -> we\n- In Eq. (7): dL/dw_i should be dL/du_i.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "15"}, "extra_text": {}}, {"review_id": "F8ZYgbYwOT_", "reviewer": "Reviewer_P9DX", "summary": "The paper under review studies the implicit sparse regularization induced by gradient descent on a diagonal linear network-like of arbitrary depth. Doing so, they extend a past work on depth 2 showing the possible benefit of larger depth. More precisely the authors show the role of early stopping to recover a sparse signal.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Overall comment and impression**\n\nFirst, I would like to say that, despite its apparent technicality, the paper is clearly written and properly referenced. The reading is pleasant and understanding the results is almost effortless. \n\nSecond, the authors take the time to clarify the main ideas of the proofs and the overall dynamics taken by the gradient descent. This is, of course, highly appreciated. \n\nThird, the main result is clear and answers (at least partially) to the non-trivial question of signal recovery in this depth N non-convex setting.\n\nHowever, I have read in the past the article on depth 2 (referred as [9] in the paper) and was impressed by this result: this paper was one of the first on the subject and it compared well to other technique for sparse recovery. Even, if this paper extends its result to the N-depth case, I feel that the results are naturally *weaker* than the aforementioned paper. I do not doubt of the technical difficulty of extending the result to the N-depth case, but, despite this potentially considerable achievement, I do not see the real implications of such a result. More precisely, here is a list of concerns regarding the comparison with [9]:\n\n- *Assumption on the data*. The assumption on the coherence of the matrix $\\textbf{X}$ seems quite restrictive compared to the RIP property that seems largely adopted for sparse problem as a necessary and sufficient condition for recovery. Is there a link between RIP and coherence ? Can the authors provide simple settings (e.g. Gaussian variable) for which they have a control on $\\mu$ ? How the hypothesis $\\mu < 1/kr$ can limit the applicability of the Theorem ? What about lower bounds with this assumption ? The reference [29] given to justify that the assumption is \"now classical\" dates back to 2005... In a word, I would expect more justifications.\n\n- *A not-so-clear benefit from depth N*. For me the benefit of depth N diagonal networks over depth 2 case really need to be clarified. Indeed, with the current justification of the authors (mainly Remark 1 and Theorem 2), I have hard times to conclude. More precisely,\n  - The *stability* perspective offered by Theorem 2 is not very clear. First, the authors only gave a lower bound on the time-window, and it is not really clear whether this estimate is tight (see argument on *Precise role of early stopping* below). Going further, they fixed $\\alpha$ and $\\eta$ to state Theorem 2 and, as they both depend on N, it is very not clear whether large N enlarges the time window. Finally, it is known (and shown in Theorem 1) that, concerning the step sizes, the larger the N, the less stable the gradient descent is! Hence, I am very confused with this statement.\n  - When comparing the initialization scales of depth 2 and depth N, it must really be clear that the *Optimization speed* are going to be different! At fixed depth, the larger the initialization, the faster the convergence. Yet, the deeper the diagonal neural nets, the slower the escape from $0$. As clearly pictured in figure 2, depth 2 clearly wins the trade-off. This is one of the reason, it is difficult to conclude for me that depth is preferable for these systems (and I know that the authors do not conclude this crudely).\n\nBeyond the comparison with [9], here is a list of questions (that can, I admit, be also applicable to the $N=2$ case):\n- *Tightness of initialization and step sizes*. I really would like a discussion on the tightness with respect to the initialization and step size, that both go with the inverse of the dimension. Is this really needed ? Do the authors observe this in practice ? Because this can slow down dramatically the dynamics in high dimension.\n- *Precise role of early stopping*. I am not clear why early stopping is necessary. When there is no noise, we know from papers the authors cited that it is not the case. But I really wonder if the noise really ruins the results (let us even assume that it is Gaussian). Somehow I feel like the noise can make the iterates fluctuate but may not totally blow the iterates away. Maybe a tighter control of this part of the decomposition could lead to a more in depth analysis of the dynamics. \n\n**Minor comments**\n\n- Line 86, I guess that n should be k.\n- Line 105, can the authors develop a bit on the fact that the noisy setting should be more realistic and lead to more insights ? This is quite the opposite of what the current machine learning community states... \n- Comment on the fact that $u_0 = v_0 = \\alpha$, what about usual gaussian initialization used in practice?\n- I would like scales of $T_u$ and $T_l$ appear in the main text as they are important quantities.\n\n**Conclusion**\n\nI would be happy to increase my score if the authors manage to convince me that the depth N model gives new insights on recovering a sparse signal or on the  training of neural networks. However, even if the technical achievements of the paper are undeniable, I would not accept the paper under the current form.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5 "}, "extra_text": {}}]

Author rebuttal:

Meta-review: In this paper the authors study the implicit bias of gradient descent for sparse linear regression problem. They focus on a particular parameterization where the model is the hadamard product of two vectors and more generally deep diagonal linear network. Prior literature has shown the propensity or implicit bias of gradient descent towards sparse solutions in some settings including deep linear cases but with simplified assumptions and no noise. The authors' result however applies in the general deep diagonal linear case and also considers noise. The authors show that under proper incoherence assumptions there is an early stopping window in which the reconstruction error is sufficiently small. The authors also utilize their theory to provide a variety of insights. The reviewers overall liked the generality of assumptions compared to prior work and thought the writing was clear. The reviewers did raise some concerns about (1) related work, (2) originality, (3) condition number of signal, (4) too strong of an incoherence assumption, (5) and lack of special insight for deep networks. During the discussion period the authors addressed some of the questions raised which led to reviewers raising the scores. My own reading of the paper is similar. The paper has some nice results but with a few caveats which limits the utility. Therefore, I recommended acceptance as a poster. I strongly urge the authors to revise the paper per reviewer suggestions.  

Decision: Accept (Poster)