acceptodds
Under review as a conference paper at ICLR 2027

Noise Improves Implicit Regularization in Linear Networks for Matrix Sensing

Abstract

We study how stochasticity affects implicit regularization in two-layer linear networks for matrix sensing. We compare full-batch gradient descent with stochastic gradient descent with additional label noise, using the same data and large initialization. For a low rank target, we prove that deterministic gradient descent does not recover the true matrix, while noisy SGD achieves recovery to arbitrarily small error. The proof relies on the over-parameterization of two-layer networks, and we provide numerical evidence that the effect strengthens with depth.

Primary area:
learning theory
Keywords:
implict regularization, matrix sensing, label noise, stochastic gradient descent

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.25 over 4 reviews, above 96% of the others.
Reviewer_DcRCOpenReview ↗
Rating
4
Confidence
2
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper investigates how stochasticity influences implicit regularization in overparameterized two-layer linear networks for matrix sensing. The authors establish a theoretical separation between deterministic gradient descent and SGD with persistent label noise under the same initialization. In particular, they show that gradient descent with sufficiently large initialization may converge to an interpolating solution with nonvanishing recovery error, whereas label-noise SGD can recover the underlying low-rank matrix to arbitrarily high accuracy. The theoretical analysis connects noise-induced stochastic dynamics to sharpness minimization and weighted nuclear-norm regularization. Numerical experiments further illustrate the benefits of label noise and explore the effect of network depth.

Critical strengths
  1. The paper establishes a rigorous separation between GD and label-noise SGD in low-rank matrix sensing, providing new insights into noise-induced implicit regularization beyond diagonal linear networks.
  2. The paper connects stochastic dynamics, sharpness minimization, and weighted nuclear-norm regularization, providing a convincing theoretical explanation for the improved recovery behavior.
Critical weaknesses
  1. The main theoretical results are established under noiseless Gaussian measurements and persistent injected label noise. While these assumptions facilitate a rigorous analysis, it would be interesting to further discuss whether similar conclusions could hold under noisy measurements or more general sensing operators.
  2. The numerical experiments effectively illustrate the theoretical findings, but they are primarily conducted on relatively small synthetic matrix sensing problems. Additional experiments with different matrix dimensions, ranks, initialization scales, and noise levels would help demonstrate the robustness and generality of the observed phenomena.
Questions for authors
  1. Can the authors provide further insights into whether the noise-induced implicit regularization mechanism persists when the original measurements contain observation noise?

  2. How sensitive is the recovery performance to the initialization scale and the magnitude of the injected label noise? A more systematic empirical investigation would be helpful.

  3. Is it possible to obtain a more explicit characterization of the iteration complexity required by label-noise SGD to achieve a prescribed recovery accuracy?

1 comment
AuthorsOpenReview ↗

Thank you for your comments

Thank you for you comments.

Q1 on what changes if there is observation noise: We believe that our result should extend to the case where the observations are noisy.

Indeed, suppose that yi=⟨Ai,M⋆⟩+eiy_i=\langle A_i,M^\star\rangle+e_i, where eie_i denotes fixed observation noise. Since the model can still interpolate these measurements, the argument of Proposition 3 remains unchanged. In particular, at any interpolating solution,

Covi,ξ(∇ℓi,ξ)=σ2∇2L.\mathrm{Cov}_{i,\xi}(\nabla \ell_{i,\xi})=\sigma^2\nabla^2 L.

Consequently, the injected noise induces the same slow dynamics, minimizing the same objective JJ, but over the set of solutions fitting the noisy measurements.

Moreover, by continuity of these dynamics, for any fixed finite recovery time TT and sufficiently small observation noise,

\leq \\|M_T(0)-M^\star\\|_F+C_T\\|e\\|_2.$$ Thus, the regularization mechanism should persist, with an additional recovery error controlled by the observation noise. Although we therefore believe that this extension is possible to achieve, we do not pursue it in the manuscript, since it would require establishing more general quantitative bounds and other technical developments, and the paper is already quite long. Our main interest is instead to understand the effect of noise on implicit regularization. **Q2 on sensitivity to initialization scale and magnitude of label noise:** We thank the reviewer for this suggestion. As detailed in our general comment above titled "New empirics", we have added experiments varying the initialization scale and noise magnitude, comparing GD, ordinary SGD, and label-noise SGD. We briefly discuss these experiments here. When increasing the initialization scale $\alpha$ from $0.05$ to $2$, the median recovery error of GD increases from $0.163$ to $0.724$. In contrast, label-noise SGD maintains an error around $0.048$ across all tested scales $\alpha\in[0.1,3]$. We also observe that the noise magnitude affects recovery. At $\alpha=2$, increasing $\sigma$ from $0.1$ to $0.5$ reduces the median error from $0.736$ to $0.048$, while increasing it further to $\sigma=3$ raises the error to $0.318$. Thus, the benefit of label noise is robust to initialization, while its magnitude controls a trade-off between recovery speed and final accuracy. **Q3 on iteration complexity bounds:** We thank the reviewer for this question. Since other reviewers also asked about this, we addressed it in our overall comment above titled "Non-asymptotic results". We briefly summarize our comments here. Our proof gives the iteration count $$N_\eta=\left\lfloor\frac{2T}{\sigma^2\eta^2}\right\rfloor,$$ where $T = T(\varepsilon)$ is the time needed by the limiting sharpness flow to reach the prescribed accuracy. However, we do not currently have an explicit bound on $T(\varepsilon)$ or on the admissible step size $\eta$. Thus, our theorem guarantees recovery to any prescribed accuracy for sufficiently small $\eta$, but does not provide an explicit iteration complexity. Obtaining such a bound would require additional quantitative control of the sharpness flow and its approximation by label-noise SGD.
Reviewer_jhdfOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies if noise helps implicit regularization in matrix sensing. The model is a two layer linear network M=UV⊤M = UV^\top. GD and label noise SGD start from the same initialization. Theorem 1(a) shows that GD from a large initialization fails. Theorem 1(b) shows that label noise SGD reaches any error ε\varepsilon. The key idea is that, after the loss reaches zero, noise slowly lowers the Hessian trace.

Critical strengths

The data, model, initialization and step size are all fixed, so only the noise differs. This extends beyond diagonal networks.

The sample size is optimal.

Critical weaknesses

Part (b) has no rate. The time T(ε)T(\varepsilon) is not bounded. The step size η\eta is not bounded. The number of steps NηN_\eta is not bounded either. The allowed step size depends on σmin⁡(Wt)\sigma_{\min}(W_t), which shrinks exponentially.

no comparison with other matrix sensing algos like altmin, altgdmin, fast rpca etc.

Questions for authors

Can you bound T(ε)T(\varepsilon), η\eta and NηN_\eta?

How does η\eta depend on σmin⁡(Wt)\sigma_{\min}(W_t)? Does η\eta go to zero as ε\varepsilon goes to zero, and how fast?

Can a comparison table be provided with respect to other matrix sensing algos like altmin, altgdmin, fast rpca etc.

2 comments
AuthorsOpenReview ↗

Thank you for your comments

Q1 on quantitative bounds on T(ϵ),η,NηT(\epsilon), \eta, N_\eta: We thank the reviewer for this question. As detailed in our overall response, our main result establishes a qualitative separation between GD and label-noise SGD, rather than quantitative convergence rates.

Our proof identifies the number of iterations in terms of the recovery time TT of the limiting sharpness flow: Nη=⌊2Tσ2η2⌋.N_\eta=\left\lfloor\frac{2T}{\sigma^2\eta^2}\right\rfloor. However, we do not currently have explicit upper bounds on T(ε)T(\varepsilon) or on the admissible step size η\eta. Obtaining such bounds would require additional quantitative analysis of the nonconvex sharpness flow and its finite-step approximation. Please see our comment above on "non-asymptotic results" for more discussion.

Q2 on the relationship between$\eta$ and \sigma_\min: Our analysis of the sharpness flow is only asymptotic, because the sharpness (namely ΔL\Delta L) is non-convex on the manifold Γy\Gamma_y. In particular, the proof proceeds via first showing that a critical point is eventually attained and then that any non-global minimum critical point would not be stable under the flow. The role of \sigma_\min is to make this instability argument go through. Therefore, it is not immediately clear from our proof what the quantitative relationship between η\eta and \sigma_\min should be.

Our theorem allows η\eta to decrease with the desired accuracy ε\varepsilon, but does not quantify how fast. Obtaining explicit end-to-end complexity bounds would require additional quantitative analysis of the nonconvex sharpness flow and its finite-step approximation. We discuss this point more in the general comment above on "non-asymptotic bounds".

Q3 on comparison to other matrix sensing algorithms: We sincerely thank the reviewer for their suggestion to do a more detailed comparison to the algorithmic literature on matrix sensing. We have added a new paragraph to the related work section, "Algorithms for low-rank matrix sensing", where we discuss algorithms for solving low-rank matrix sensing. Because this is a large area, we mainly discuss algorithms which use a factorized parameterization as in our work. In particular, we discuss each of the algorithms you mentioned with the exception of fast RPCA, since it appears that that algorithm is for a different problem where the whole matrix is observed up to some sparse noise (please let us know if you had a different paper in mind). These algorithmic works differ from our own in two important ways:

  1. they study deterministic algorithms
  2. they either take very small and often structured initialization, OR they explicitly encode the low-rank in the parameterization, thus precluding any implicit regularization

Most notably, we did find a paper which we were not previously aware of, Xu et al. 2023, which studies a pre-conditioned GD algorithm and shows that it achieves improved convergence over vanilla GD even with over-parameterized factorizations. We have also therefore modified slightly our discussion of our contribution relative to the literature on over-parameterized GD to take this paper into account.

We decided to put a paragraph rather than a table because we do not want distract too much from the main contribution of this work, which is not algorithmic but conceptual: we show that stochasticity yields improved implicit regularization at large initialization. We study a different regime than almost all previous work, and identify a novel phenomenon for this regime.

Thank you for the detailed response and acknowledging the related matrix sensing work. I have updated my score.

Reviewer_6zVuOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies implicit regularization in the two-layer linear parametrization M=UV⊤M = UV^\top for low-rank matrix sensing, asking whether noise in gradient descent strengthens implicit regularization. Holding the dataset, architecture, initialization, and step size fixed, the authors compare full-batch GD against single-sample SGD with ±σ\pm \sigma Rademacher label perturbations, and prove the conclusion: (1) GD achieves no meaningful recovery; (2) label-noise SGD reaches arbitrarily small Frobenius recovery error. Over-parameterization is necessary for the effect.

Critical strengths

1. The paper advances the study of "stochasticity vs. implicit regularization" from diagonal linear networks to two-layer matrix factorization with full neuron interactions, and under the same dataset, architecture, initialization, and step size it provides both a failure lower bound for GD and a full-recovery guarantee for noisy SGD. This is more convincing than a separation that only holds at the level of sample complexity.

2. Readability is noticeably better than in comparable theory papers. AI usage is also disclosed.

Critical weaknesses

1. This paper does not prove that "the stochasticity of SGD in practice beats GD"; it proves that "artificially injected persistent label noise drives a sharpness flow." Yet the abstract, title, and opening paragraph conflate the two, which invites readers to misread this as a proof of a practical generalization advantage of SGD. I recommend explicitly restricting the claim to "exogenously injected label noise" in the abstract and introduction, and stating plainly that ordinary SGD does not exhibit the effect in this setting.

2. Section 4.2 uses Xavier (small) initialization, whereas both branches of the theory (especially the GD branch) are built on large initialization. For small initialization GD, it is already known to recover via incremental low-rank learning (Jin et al. 2023). Hence "deeper recovers better" cannot be attributed to noise. This set of experiments lacks GD and plain-SGD baselines at the same depth and same initialization. Moreover, depth 50 (0.065) is slightly worse than depth 20 (0.051), which is inconsistent with the narrative of monotone strengthening with depth.

3. Section 4.1: Please add an α\alpha-sweep and report the GD error, rather than just current setting.

Questions for authors

1. In the Related Work, Zhang et al. (2026) (AAAI 2026 Oral, arXiv:2603.10397) and Varre et al. (2024) (NeurIPS 2024) theoretically prove the main results of this paper, i.e., “GD fails at large initialization while label-noise SGD still recovers”. Until Q1 is answered satisfactorily, novelty can only be judged as a moderate increment.

2. Can the authors give explicit upper bounds on TT and on the threshold for η\eta? If not, does that mean ϵ\epsilon cannot go to 0 at fixed η\eta?

3. Can the authors add GD and plain-SGD baselines at the same initialization and same depth? Under small initialization, how much of the improvement from depth actually comes from GD's own incremental low-rank learning?

4. σ\sigma seems to enter only through a time reparametrization (Nη∝1/σ2N_\eta \propto 1/\sigma^2). Under a finite η\eta and finite NN budget, is there an optimal σ\sigma, or a threshold beyond which too-large σ\sigma breaks the discretization?

2 comments
AuthorsOpenReview ↗

Thank you for your comments

Thank you for your comments.

For your first comment regarding the distinction between SGD and SGD with label noise, we tried to make this explicitly clear in the abstract when we wrote "We compare full-batch gradient descent with stochastic gradient descent with additional label noise, using the same data and large initialization." However, we can see that this wasn't made sufficiently clear, so we have changed the phrase "noisy SGD" in the abstract to "SGD with label noise". We have also changed the title of the paper to "Label noise improves implicit regularization in linear networks for matrix sensing" to make this even more clear. For the introduction, we discuss SGD because it does form the motivation for what we study in this work. We note that, although vanilla SGD doesn't exhibit the same implicit regularization as SGD with label noise, variants of SGD are ubiquitous in practice anyways, so the study of another variant is very well-motivated in our view.

All of your remaining questions were shared with other reviewers, and are therefore addressed in general comments above. Nonetheless, we give brief responses here.

Q1 on Zhang et. al (2026) and Varre et al. (2024): We agree that these works consider the interplay of label-noise and implicit regularization. However, neither proves a recovery guarantee for label-noise SGD. As explained in our overall response, Varre et al. (2024) establish a mechanism favoring rank deficiency through decreasing determinant, without identifying which low-rank matrix is eventually recovered. In particular, they do not establish recovery of the true low-rank matrix. Zhang et al. (2026) prove that label-noise SGD escapes the lazy regime, but their only recovery result is for GD with small initialization.

Our contribution is rather to prove that label-noise SGD itself achieves arbitrarily accurate matrix recovery from essentially arbitrary full-row-rank initialization. Moreover, we establish a direct separation from GD under the same data, architecture, initialization, and step size. Please see the general comment above for more discussion.

Q2 on explicit bounds for TT and η\eta: Our main result establishes a qualitative separation between GD and label-noise SGD, rather than quantitative convergence rates.

As explained in Appendix E.4, if the limiting sharpness flow reaches the prescribed accuracy at time TT, the corresponding number of SGD iterations is Nη=⌊2Tσ2η2⌋.N_\eta=\left\lfloor\frac{2T}{\sigma^2\eta^2}\right\rfloor. However, our proof does not provide explicit upper bounds on T(ε)T(\varepsilon) or on the admissible step size η\eta. Obtaining such bounds would require additional quantitative control of the nonconvex sharpness flow and its finite-step approximation.

Regarding fixed η\eta, our theorem allows the step size to depend on the desired accuracy ε\varepsilon. This is natural because the injected label noise remains active even at interpolation, which means that due to stochastic fluctuations the dynamics will never remain near the low-rank solution for all times. Thus, we do not claim arbitrarily accurate recovery at a fixed positive η\eta, although our result guarantees recovery to any prescribed accuracy by choosing η\eta sufficiently small. Please see the general comment above for more discussion.

Q3 on GD and plain-SGD baselines for deep linear networks: We agree that small initialization can already favor low-rank recovery with GD. As detailed in our overall response, we have added GD and ordinary SGD baselines at every depth, using the same initialization and sensing data. Both baselines improve with depth, but label-noise SGD consistently performs substantially better. At depth 55, its median recovery error is 0.00230.0023, compared to 0.14780.1478 for ordinary SGD and 0.23220.2322 for GD. Thus, depth helps on its own, but label noise provides a substantial additional improvement.

Q4 on the role of σ\sigma: Indeed, in the limiting sharpness flow, the noise magnitude σ\sigma only affects the time scale, with Nη∝1/(σ2η2)N_\eta \propto 1/(\sigma^2\eta^2). However, this equivalence holds in the small-step limit for fixed σ\sigma. At finite step size, the noise magnitude also affects the fluctuations and the accuracy of the approximation.

This leads to a tradeoff: smaller noise slows down the implicit regularization, while larger noise can increase the finite-step error. We also discuss this in the general comment titled "Non-asymptotic results" above.

To explore this tradeoff, we conducted additional experiments varying σ\sigma at a fixed step size and iteration budget. We observe that intermediate noise levels achieve the best recovery, while both smaller and larger values perform worse. These experiments suggest that an optimal noise magnitude may exist for a given step size and computational budget. See the comment above on new empirics for additional discussion.

Thanks for the authors' detailed response. It addresses my concern. I will increase my score.

Reviewer_ZBbROpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies how persistent label noise changes implicit regularization in two-layer linear networks for Gaussian matrix sensing. Full-batch GD and noisy SGD use the same data, architecture, initialization, and step size in a shared large-initialization regime. Theorem 1 proves a separation: deterministic training converges to an interpolator with Frobenius error bounded away from zero, and noisy SGD can reach arbitrarily small recovery error with high probability. The proof identifies two time scales. Training first approaches the interpolation manifold. Label noise then induces projected gradient flow for the Hessian trace, which is equivalent to a data-weighted nuclear-norm objective. The authors prove that this flow reaches the target matrix. A one-layer lower bound shows that factorized over-parameterization is essential. Small synthetic experiments clearly illustrate the two stages. A preliminary depth study suggests that deeper factorizations can accelerate recovery. The depth evidence currently uses five small instances and one shared step size.

Critical strengths
  • Theorem 1 holds the data, initialization, architecture, and step size fixed, isolating the effect of persistent label noise.
  • Concrete mechanism: Propositions 3–6 connect the noise covariance to Hessian trace, identify the induced weighted nuclear norm, and prove that the projected flow reaches the target matrix.
  • The appendix proves the required regularity and global convergence and includes a one-layer lower bound showing that factorization is essential.
Critical weaknesses
  • The noisy guarantee is existential. The admissible step size depends on the target accuracy, confidence, and noise level.
  • The stopping time and total gradient complexity remain implicit, and persistence after the selected iterate remains open.
  • The depth study uses five small synthetic instances and one untuned step size for every depth. This is too limited to support a general claim that depth strengthens the effect.
Questions for authors
  1. Can you make the admissible step size and stopping time explicit in the accuracy, confidence, noise level, dimensions, rank, and initialization? It would also help to know whether accurate recovery persists over a nontrivial interval of iterations.
  2. Relative to Varre et al. (2024) and Zhang et al. (2026), which conclusion is genuinely new: exact recovery, arbitrary full-row-rank initialization, global convergence of the induced flow, or the direct separation from full-batch GD? A direct comparison of the theorem statements would sharpen the contribution.
  3. Does the apparent advantage of depth remain when the step size and noise magnitude are tuned separately for each depth and the comparison is compute-matched?
1 comment
AuthorsOpenReview ↗

Thank you for your comments

Thank you for your comments. All three of your questions were shared with other reviewers, and so are addressed in general comments above. We nonetheless give brief replies here.

Q1 on quantitative bounds We thank the reviewer for this question. Our main result establishes a qualitative separation between GD and label-noise SGD, rather than quantitative convergence rates.

The proof identifies the number of SGD iterations in terms of the sharpness-flow recovery time TT:

Nη=⌊2Tσ2η2⌋.N_\eta=\left\lfloor\frac{2T}{\sigma^2\eta^2}\right\rfloor.

However, we do not currently have explicit bounds on T(ε)T(\varepsilon) or on the admissible step size in terms of the accuracy, confidence, noise magnitude, dimensions, rank, and initialization. Deriving such bounds would require additional quantitative analysis of the nonconvex sharpness flow and its finite-step approximation.

Regarding persistence, our existing uniform finite-time approximation (Proposition 40) gives a stronger conclusion than recovery at a single iterate. For any prescribed accuracy ε>0\varepsilon>0, confidence 1−δ1-\delta, and finite duration H>0H>0, there exist a finite time TT and a sufficiently small constant step size η\eta such that, with probability at least 1−δ1-\delta, all SGD iterates corresponding to sharpness-flow times in [T,T+H][T,T+H] achieve recovery error at most ε\varepsilon. The injected noise remains active throughout this interval.

Please see our general comment above for more details.

Q2 on Varre et al. (2024) and Zhang et al. (2026): We thank the reviewer for this question. As detailed in our overall response, Varre et al. (2024) only show that label noise drives a determinant toward zero in a continuous-time model, which, although suggestive of implicit regularization, does not identify which low-rank matrices the dynamics converge to. In particular, they do not prove recovery of the target matrix. Zhang et al. (2026) show that label-noise SGD escapes the lazy regime, but their recovery result is only for GD with small initialization.

In contrast, our main result proves that label-noise SGD recovers the true low-rank matrix to arbitrary accuracy from any full-row-rank stacked initialization, while GD fails from the same large initialization. We also establish global convergence of the induced sharpness flow, which is essential to proving recovery. Please see the general comment above for more discussion.

Q3 on empirics for depth when step-size and noise magnitude are tuned separately: We thank the reviewer for this suggestion. As detailed in our overall response, we have revised Section 4.2, comparing depths 22, 33, and 55 over 512512 independent instances, with step sizes tuned separately for each depth. We also compare methods at equal computational cost. The benefit of depth persists: the median recovery error of label-noise SGD decreases from 0.01550.0155 at depth 22 to 0.00610.0061 at depth 55, a factor of 2.52.5 improvement. Thus, the observed benefit of depth is not simply due to a larger computational budget. Please see the general comment above and the new text and figures in section 4.2 as well as Appendix A for more details.

Comments on the paper

4 comments
AuthorsOpenReview ↗

Thank you to reviewers; new version has been uploaded

We sincerely thank the reviewers for their questions and comments. We have uploaded a new version of the manuscript incorporating many of the requested changes which are highlighted in blue. We will post three more comments addressing questions that arose in multiple reviews.

AuthorsOpenReview ↗

More details on comparison to Zhang et. al (2026) and Varre et. al (2024)

Reviewers 1 and 2 asked for more details on the differences between our work and these papers. We have added a more detailed discussion to the related work section (highlighted in blue) and here give a precise comparison.

Comparison to Zhang et al (2026): This paper studies two layer linear neural networks with output dimension 11. While in our paper we study pure label-noise SGD, in Zhang et al the authors only show that label-noise SGD exits the lazy regime (Theorem 4.2), where by "lazy regime" they mean that the parameters move a significant amount from initialization. This is similar to the content of our Prop. 4, which states that, for sufficiently small step-sizes, the dynamics will eventually move away from the endpoint of gradient flow, thus exiting the lazy regime. While they do prove recovery of the underlying signal in Lemma 4.6, this result is only for deterministic gradient descent starting from small initialization, which they study for "mathematical tractability". In this regard, their recovery result is closer to that of Li et. al (2018). By contrast, our main result studies one algorithm, label-noise SGD, and shows that it can recover the true low-rank matrix to arbitrary accuracy.

Comparison to Varre et. al (2024): This work also studies two layer linear neural networks with square loss. However, they focus mainly on comparing two continuous-time models: deterministic gradient flow with an SDE model of label-noise SGD. In our notation, their main result says that deterministic gradient flow does not change det⁡Mt\det M_t, while under their SDE model, det⁡Mt\det M_t is decreasing (although never 00). In particular, their result for the SDE model, in addition to not applying to label-noise SGD, does not prove recovery of the underlying matrix M⋆M_\star. In Proposition 24 of the appendix, we prove a similar result for the lifted matrix WtW_t when it is undergoing sharpness flow, but the purpose of this result is to ensure that the matrices remain regular (full row rank) throughout the trajectory. Since there are typically many low-rank matrices which interpolate the data, determinant contraction, while suggestive of implicit regularization, is not conclusive because it does not identify which low-rank matrix the trajectory approaches.

AuthorsOpenReview ↗

New empirics on depth and the dependence on the magnitude of the noise

Several reviewers asked for a more systematic investigation of the effect of initialization scale and injected label-noise magnitude on recovery, and felt that our characterization that the implicit regularization effect "strengthens with depth" was not sufficiently substantied in the empirics. We sincerely appreciate this feedback and have both significantly strengthened our empirical experiments while also moderating our language regarding the effect of depth. In particular, in the abstract we now say that "we provide empirical results studying how the effect changes with depth".

We have also added new empirical results to section 4 of the main text as well as created a new section of the appendix, Appendix A, with additional new experiments. Let us now describe these new results.

New empirics on the effect of depth

We have substantially revised our experiment on depth to better understand the interaction between depth and label noise. In particular, we changed the experimental setting to distinguish the benefit of noise from that of depth itself, and to account for the additional computational cost of deeper networks.

We now compare GD, ordinary SGD, and label-noise SGD at depths 22, 33, and 55, using the same sensing problems and initial product, and crucially tune hyperparameters independently for each method and depth. We consider both matched optimization steps and matched compute, and evaluate recovery over 512512 independent instances.

The results show that label-noise SGD substantially outperforms both GD and ordinary SGD at every depth, under both budgets. Moreover, its recovery error decreases from depth 22 to depth 55, by a factor of 9.49.4 with matched updates and 2.52.5 with matched compute. The new comparisons give a more precise picture: depth improves recovery even without injected noise, while label-noise SGD provides a substantial additional benefit at each depth.

This experiment is complementary to our main theoretical result, which establishes the separation between GD and label-noise SGD at depth two. Its purpose is to illustrate an interesting interaction between depth and noise, and to motivate its theoretical study in future work.

Effect of hyperparameters for label-noise SGD

We have also conducted additional experiments in the setting of Section 4.1, comparing GD, ordinary SGD, and label-noise SGD across multiple random instances. We include the corresponding figures and detailed results in Appendix A of the revised manuscript.

1. Effect of initialization scale. We vary the initialization scale α\alpha from 0.050.05 to 88. As predicted by Proposition 2, the recovery error of GD increases substantially with initialization, from 0.1630.163 at α=0.05\alpha=0.05 to 0.7240.724 at α=2\alpha=2, before stabilizing around 0.7250.725. In contrast, label-noise SGD achieves nearly constant recovery error (around 0.0480.048) across all tested scales α∈[0.1,3]\alpha\in[0.1,3], while ordinary SGD remains close to GD. This provides further empirical evidence that label noise can overcome the poor implicit regularization of large-initialization GD.

2. Effect of noise magnitude. We vary the injected noise magnitude σ\sigma from 00 to 33, at initialization scales α=0.25\alpha=0.25 and α=2\alpha=2. The results reveal a clear trade-off: small noise leads to slower recovery, especially at large initialization, while excessively large noise increases the final recovery error. For example, at α=2\alpha=2, increasing σ\sigma from 0.10.1 to 0.50.5 reduces the median error from 0.7360.736 to 0.0480.048, whereas increasing it further to σ=3\sigma=3 raises the error to 0.3180.318. This agrees with the interpretation of our limiting dynamics: larger noise accelerates the induced regularization but also increases finite-step fluctuations.

Overall, these experiments strengthen our empirical conclusions. The benefit of label noise persists across a wide range of initialization scales, while the choice of noise magnitude controls the trade-off between recovery speed and final accuracy at a fixed step size and computational budget.

AuthorsOpenReview ↗

Non-asymptotic results

Several reviewers ask whether the recovery time, admissible step size, and number of SGD iterations can be made explicit, and how these quantities depend on the magnitude of the injected noise.

We emphasize that the main goal of our paper is to establish a rigorous separation in implicit regularization between GD and label-noise SGD. Starting from the same initialization, with the same data, architecture, and step size, we prove that GD fails to recover the underlying low-rank matrix, whereas label-noise SGD achieves arbitrarily accurate recovery with high probability. Obtaining precise convergence rates is therefore an interesting question but orthogonal to our goal in this work. Nevertheless, our analysis already provides several useful quantitative insights.

1. Recovery time and iteration count. If the limiting sharpness flow reaches the prescribed accuracy at time TT, the corresponding SGD iteration count is

Nη=⌊2Tσ2η2⌋,N_\eta=\left\lfloor\frac{2T}{\sigma^2\eta^2}\right\rfloor,

where η\eta is the step size and σ\sigma the label-noise magnitude. On the other hand, our proof technique is based on the asymptotic limit in Prop. 4, and so it is not possible to immediately extract quantitative bounds on the required size of η\eta. The parameter TT is also not possible to immediately control, because our proof technique only establishes asymptotic convergence of the sharpness flow, without any rate. This is a challenging problem in its own right, because the sharpness ΔL\Delta L is non-convex on the solution manifold Γy\Gamma_y.

2. Persistence of recovery. Our existing uniform finite-time approximation, Proposition 3, gives a stronger conclusion than the single-iterate statement of Theorem 1 by simply taking multiple times and applying the convergence in probability jointly. For any prescribed accuracy ε>0\varepsilon>0, confidence 1−δ1-\delta, and finite duration H>0H>0, there exists a sufficiently small constant step size and a time TT such that, with probability at least 1−δ1-\delta, all SGD iterates corresponding to sharpness-flow times in [T,T+H][T, T + H] achieve recovery error at most ε\varepsilon. The injected noise remains active throughout. We have added a remark to this effect after the statement of our main theorem.

3. Step size and noise magnitude. Our result allows the step size to depend on the desired accuracy. This is necessary for persistent label-noise: at fixed positive step size, noise continues to generate fluctuations even at interpolation. Moreover, while σ2\sigma^2 determines the time scale of the limiting flow, the noise magnitude also affects finite-step fluctuations. Thus, choosing σ\sigma involves a tradeoff between the speed of the induced regularization and the accuracy of the finite-step approximation.

In summary, our theorem establishes the qualitative separation in recovery behavior without requiring quantitative convergence rates. The additional observations above clarify its finite-time interpretation and strengthen its conclusion regarding persistence. Deriving sharp end-to-end complexity guarantees is a complementary direction for future work.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.