Implicit bias of SGD in $L_{2}$-regularized linear DNNs: One-way jumps from high to low rank

Understand

The $L_{2}$-regularized loss of Deep Linear Networks (DLNs) with more than one hidden layers has multiple local minima, corresponding to matrices with different ranks.

• In tasks such as matrix completion, the goal is to converge to the local minimum with the smallest rank that still fits the training data.
• While rank-underestimating minima can be avoided since they do not fit the data, GD might get stuck at rank-overestimating minima.
• We show that with SGD, there is always a probability to jump from a higher rank minimum to a lower rank one, but the probability of jumping back is zero.