- 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
- 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.
- The paper connects stochastic dynamics, sharpness minimization, and weighted nuclear-norm regularization, providing a convincing theoretical explanation for the improved recovery behavior.
Critical weaknesses
- 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.
- 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
-
Can the authors provide further insights into whether the noise-induced implicit regularization mechanism persists when the original measurements contain observation noise?
-
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.
-
Is it possible to obtain a more explicit characterization of the iteration complexity required by label-noise SGD to achieve a prescribed recovery accuracy?
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⋆⟩+ei, where ei 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.Consequently, the injected noise induces the same slow dynamics, minimizing the same objective J, but over the set of solutions fitting the noisy measurements.
Moreover, by continuity of these dynamics, for any fixed finite recovery time T 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.