Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: 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.
main_review: # Originality

The 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.

- Zhiyuan Li, Yuping Luo, and Keifeng Lyu. Towards Resolving the Implicit Bias of Gradient Descent for Matrix Factorization: Greedy Low-Rank Learning. ICLR 2021

# Quality

- 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.

- 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.

# Clarity

Overall, 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.
- Typos: pg 4 line 136 “property of design” -> “property of the design”

# Significance

While 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).
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_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
main_review: **Overall comment and impression**

First, 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. 

Second, 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. 

Third, 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.

However, 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]:

- *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.

- *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,
  - 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.
  - 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).

Beyond the comparison with [9], here is a list of questions (that can, I admit, be also applicable to the $N=2$ case):
- *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.
- *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. 

**Minor comments**

- Line 86, I guess that n should be k.
- 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... 
- Comment on the fact that $u_0 = v_0 = \alpha$, what about usual gaussian initialization used in practice?
- I would like scales of $T_u$ and $T_l$ appear in the main text as they are important quantities.

**Conclusion**

I 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.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.
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”.

Comments:

1. 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.


2. 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? 


3. 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.


Minor comment: line 140, the upper bound for $\mu$ is 1/kr, what is r?

Reference:

Gauthier Gidel, Francis Bach, and Simon Lacoste-Julien. Implicit regularization of discrete gradient
dynamics in linear neural networks. arXiv preprint arXiv:1904.13262, 2019.
limitations_and_societal_impact: Please refer to the comments.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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. 
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. 

In 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.

Comments:
- It would be good to define “minimax optimal recovery” and explicitly show that the bound is indeed minimax optimal.
- 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.
 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.
- 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.
- I think the following two papers are relevant for discussion:

https://arxiv.org/abs/1903.11680

https://arxiv.org/abs/1903.09139
- 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$.
- Can you explain Eq. (7) ? Why $\eta$ appears there, and did you use expectation of the loss over $X$, like in [11] ?
- In Figures 1 and 4, please explain how did you determine the location of the dashed black lines of the window.
- 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.
- 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}$.
- 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 ?
- 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].
- 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.:

https://arxiv.org/abs/1903.11680

Typos:
- line 10: "an" in not needed
- line 179: third term -> second term
- line 240: converges -> converge
- line 270: Figure 4 -> Figure 1
- line 274: We -> we
- In Eq. (7): dL/dw_i should be dL/du_i.

limitations_and_societal_impact: N/A
review_title: null

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)