IMPLICIT BIAS OF SGD IN L₂-REGULARIZED LINEAR DNNS: ONE-WAY JUMPS FROM HIGH TO LOW RANK

The L₂-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 critical point to a lower rank one, but the probability of jumping back is zero. More precisely, we define a sequence of sets B₁ ⊂ B₂ ⊂ ··· ⊂ B_R so that B_r contains all critical points of rank r or less (and not more) that are absorbing for small enough ridge parameters λ and learning rates η: SGD has prob. 0 of leaving B_r, and from any starting point there is a non-zero prob.