Stability of Low-Rank Implicit Regularization in Perturbed Deep Matrix Factorization

This paper studies the stability of low-rank implicit regularization in deep matrix factorization, a tractable model for understanding how gradient-based training can favor low-complexity structure.

We first revisit the noiseless setting and derive sufficient spectral conditions under which gradient descent exhibits a nonempty low-rank interval.

These conditions clarify how the target spectrum, initialization, and step size jointly determine when a low-rank phase is observable along the optimization trajectory.

We then analyze the perturbed problem, where the target matrix is subject to an additive perturbation.

By studying the perturbed gradient descent dynamics at the eigenvalue level, we prove convergence guarantees and quantify how the perturbation size affects iteration complexity and eigenvalue recovery.

Finally, we establish stability of the low-rank phase under perturbation: the effective rank of the iterates remains close to that of the rank-L approximation of the noiseless target over a perturbed low-rank interval, with explicit dependence on the perturbation size.

Numerical illustrations support the theoretical predictions and illustrate the role of spectral structure in determining when this stability is observed.