Implicit Regularization in Matrix Factorization

By Suriya Gunasekar, Blake E. Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, Nati Srebro. 2017

585 citations recorded by the source corpus.

We study implicit regularization when optimizing an underdetermined quadratic objective over a matrix $X$ with gradient descent on a factorization of X. We conjecture and provide empirical and theoretical evidence that with small enough step sizes and initialization close enough to the origin, gradient descent on a full dimensional factorization converges to the minimum nuclear norm solution.

Subfields: Computational Mechanics, Mathematical Physics, Numerical Analysis, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Mathematical Physics

In Numerical Analysis

In Optimization & Training

Citations in the corpus

Implicit Regularization of Discrete Gradient Dynamics in Deep Linear Neural Networks (2019, methodology): “A similar idea has been developed in the context of matrix factorization [Gunasekar et al., 2017].”
The Surprising Simplicity of the Early-Time Learning Dynamics of Neural Networks (2020, background): “…of (stochastic) gradient descent has also been studied in various settings, suggesting a bias towards large-margin, low-norm, or low-rank solutions [Gunasekar et al., 2017, 2018, Soudry et al., 2018, Li et al., 2018, Ji and Telgarsky, 2019a,b, Arora et al., 2019a, Lyu and Li, 2019, Chizat and…”
Reconciling modern machine-learning practice and the classical bias–variance trade-off (2018, background): “While the behavior of SGD for more general neural networks is not fully understood, there is signiﬁcant empirical and some theoretical evidence (e.g., [20]) that a similar minimum norm inductive bias is present.”
Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data (2018, background): “Recent studies are on SGD for different tasks, such as logistic regression [27] and matrix factorization [11, 19, 16].”
The Implicit Bias of Gradient Descent on Separable Data (2017, neutral): “The implicit bias of adaptive method has been a recent topic of interest, with Hoffer et al. (2017) and Wilson et al. (2017) suggesting they lead to worse generalization.”
On the Global Convergence of Gradient Descent for Over-parameterized Models using Optimal Transport (2018, background): “For example, with symmetric matrices, F = Rd×d and Φ(θ) = θθ>, we recover low-rank matrix decompositions [15].”
Just Interpolate: Kernel "Ridgeless" Regression Can Generalize (2018, methodology): “Our analysis can then be viewed in the light of recent work on implicit regularization of optimization procedures [30, 23, 17, 21].”
Implicit Bias of Gradient Descent on Linear Convolutional Networks (2018, methodology): “…and even with homogeneous polynomials, the characterization is not as crisp when other loss functions are used, e.g., with a squared loss and matrix factorization (a homogeneous degree two polynomial representation), the implicit bias is much more fragile Gunasekar et al. [2017], Li et al. [2017].”
Fix your classifier: the marginal value of training the last weight layer (2018, background): “…theoretical results related to neural network training (Soudry & Hoffer, 2017; Xie et al., 2016; Safran & Shamir, 2016; Soltanolkotabi et al., 2017; Soudry & Carmon, 2016) and even generalization (Gunasekar et al., 2017; Advani & Saxe, 2017; Wilson et al., 2017) usually assume over-speciﬁcation.”
Stochastic Mirror Descent on Overparameterized Nonlinear Models (2019, background): “This trend is observed consistently for all other mirror descents and all initializations (see the results in Tables 8 and 9 in the appendix).”
Implicit Regularization in Deep Learning May Not Be Explainable by Norms (2020, background): “Conjecture 1 (from [34], informally stated).”
Contrastive Behavioral Similarity Embeddings for Generalization in Reinforcement Learning (2021, background): “…follows that Furthermore, it is well-known that gradient descent tends to ﬁnd low-rank solutions due to implicit regularization (Arora et al., 2019; Gunasekar et al., 2017), e.g., with small enough step sizes and initialization close enough to the origin, gradient descent on matrix factorization…”
Implicit Regularization in Deep Learning (2017, background): “[42] provided empirical and theoretical evidence on the implicit regularization of gradient descent for matrix factorization.”
The Implicit and Explicit Regularization Effects of Dropout (2020, background): “A large body of recent work has studied implicit, or algorithmic regularization in deep learning, defined to be a regularization effect imposed by the training algorithm, not by the objective (see for example (Gunasekar et al., 2017; Li et al., 2017; Gunasekar et al., 2018b; Arora et al., 2019) and ”
Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution (2017, background): “For instance, it has been conjectured that in matrix factorization, over-parameterized stochastic gradient descent effectively enforces certain norm constraints, allowing it to converge to a minimal-norm solution as long as it starts from the origin [52].”
Reconciling modern machine learning and the bias-variance trade-off (2018, background): “That the test risk improves beyond the interpolation threshold is compatible with the conjectured “small norm” inductive biases of the common training algorithms for neural networks [14, 16].”
Explaining Sequence-Level Knowledge Distillation as Data-Augmentation for Neural Machine Translation (2019, background): “However, explanations for why stochastic gradient descent (SGD) on big neural nets works so well remain elusive, although significant steps are being taken (Vidal et al., 2017; Gunasekar et al., 2017).”
Step Size Matters in Deep Learning (2018, methodology): “i=1 Ai ∣∣∣ {W∗ j } ẼBi ∣∣∣ {W∗ j } (7)”