Noise Improves Implicit Regularization in Linear Networks for Matrix Sensing

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.