In the field of deep learning theory, "implicit bias" refers to the tendency of training algorithms like Gradient Descent (GD) to find solutions with specific structural properties, such as low rank or small norm, even without explicit constraints. A recent paper by Zihan Wang and Arthur Jacot, "Implicit bias of SGD in $L_2$-regularized linear DNNs: One-way jumps from high to low rank," provides a rigorous mathematical foundation for this phenomenon in Deep Linear Networks (DLNs).
They demonstrate that Stochastic Gradient Descent (SGD) acts as a "one-way valve," pushing models toward simpler, lower-rank solutions while preventing them from returning to higher-rank complexity. This property makes SGD uniquely suited for tasks like matrix completion, where the goal is to find the simplest underlying structure that fits the data.
The Challenge of Matrix Completion
Matrix completion—predicting missing values in a dataset, such as movie ratings—is often approached using DLNs because they are naturally biased toward low-rank solutions. However, for networks deeper than two layers, the loss landscape becomes non-convex and is filled with local minima of varying ranks.
Standard Gradient Descent is a "greedy" optimizer. If it begins near a high-rank solution that fits the observed data, it often becomes trapped in that local minimum. This paper investigates why SGD succeeds in escaping these traps where GD fails.
The One-Way Jump Mechanism
The authors' core insight lies in the interaction between $L_2$ regularization and the discrete noise of SGD. In deep networks ($L > 2$), $L_2$ regularization on weights is equivalent to $L_p$-Schatten norm regularization on the resulting matrix (where $p < 1$). This creates a landscape where different local minima correspond to different ranks.
Unlike the common "Langevin approximation," which treats SGD as GD plus uniform Gaussian noise, the authors analyze the actual discrete steps of SGD. They prove that SGD noise is highly structured: it can push weights toward zero along specific singular value directions. Once a singular value reaches zero, the noise in that direction vanishes, making the low-rank state an "absorbing set."
Empirical Evidence and Results
The theory was validated using synthetic experiments, specifically a 2x2 matrix completion task designed to have rank-2 local minima and a rank-1 global minimum.
Key findings include:
- Absorbing Property: Once SGD enters a neighborhood of a rank-$r$ solution, it remains within the set of solutions with rank $\le r$ indefinitely, provided the learning rate is sufficiently small.
- Stochastic Success: While GD almost always converges to a suboptimal rank-2 solution, SGD—particularly with annealing or periodic learning rate schedules—can jump to the rank-1 solution.
Conclusion and Future Directions
This research highlights that the discrete, non-isotropic noise of SGD is not just a nuisance but a powerful feature that enables the discovery of simpler models. By proving that these jumps are one-way, the authors provide a theoretical basis for the superior generalization often observed in models trained with SGD.
Future work remains to extend these findings to nonlinear networks (such as ReLU networks) and to understand how these dynamics scale to the massive matrices encountered in real-world applications. For now, the "one-way jump" stands as a compelling explanation for the implicit low-rank bias of stochastic optimization.
Summary updated