Towards Resolving the Implicit Bias of Gradient Descent for Matrix Factorization: Greedy Low-Rank Learning

Abstract

Matrix factorization is a simple and natural test-bed to investigate the implicit regularization of gradient descent. Gunasekar et al. (2017) conjectured that Gradient Flow with infinitesimal initialization converges to the solution that minimizes the nuclear norm, but a series of recent papers argued that the language of norm minimization is not sufficient to give a full characterization for the implicit regularization. In this work, we provide theoretical and empirical evidence that for depth-2 matrix factorization, gradient flow with infinitesimal initialization is mathematically equivalent to a simple heuristic rank minimization algorithm, Greedy Low-Rank Learning, under some reasonable assumptions. This generalizes the rank minimization view from previous works to a much broader setting and enables us to construct counter-examples to refute the conjecture from Gunasekar et al. (2017). We also extend the results to the case where depth $\ge 3$, and we show that the benefit of being deeper is that the above convergence has a much weaker dependence over initialization magnitude so that this rank minimization is more likely to take effect for initialization with practical scale.

49 pages, 7 figures; ICLR 2021 camera ready

References in corpus (10)

• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• On Lazy Training in Differentiable Programming
• Gradient descent aligns the layers of deep linear networks
• Gradient Descent Maximizes the Margin of Homogeneous Neural Networks
• First-order Methods Almost Always Avoid Saddle Points
• Implicit Regularization in Deep Learning May Not Be Explainable by Norms
• Stochastic Gradient Descent on Separable Data: Exact Convergence with a Fixed Learning Rate
• On implicit regularization: Morse functions and applications to matrix factorization
• On Approximation Guarantees for Greedy Low Rank Optimization

Cited by in corpus (5)

• Machine Learning and Deep Learning -- A review for Ecologists
• The Low-Rank Simplicity Bias in Deep Networks
• Implicit Regularization in ReLU Networks with the Square Loss
• Understanding Deflation Process in Over-parametrized Tensor Decomposition
• Implicit regularization of deep residual networks towards neural ODEs