Implicit Regularization in Deep Matrix Factorization

By Sanjeev Arora, Nadav Cohen, Wei Hu, Yuping Luo. 2019

634 citations recorded by the source corpus.

Efforts to understand the generalization mystery in deep learning have led to the belief that gradient-based optimization induces a form of implicit regularization, a bias towards models of low "complexity." We study the implicit regularization of gradient descent over deep linear neural networks for matrix completion and sensing, a model referred to as deep matrix factorization. Our first finding, supported by theory and experiments, is that adding depth to a matrix factorization enhances an implicit tendency towards low-rank solutions, oftentimes leading to more accurate recovery. Secondly, we present theoretical and empirical arguments questioning a nascent view by which implicit regularization in matrix factorization can be captured using simple mathematical norms. Our results point to the possibility that the language of standard regularizers may not be rich enough to fully encompass the implicit regularization brought forth by gradient-based optimization.

Subfields: Artificial Intelligence, Computational Mechanics, Mathematical Physics, 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 Artificial Intelligence

In Computational Mechanics

In Mathematical Physics

In Optimization & Training

Citations in the corpus

The Surprising Simplicity of the Early-Time Learning Dynamics of Neural Networks (2020, methodology): “Another line of work has identified that deep linear networks gradually increase the rank during training [Arora et al., 2019a, Saxe et al., 2014, Lampinen and Ganguli, 2018, Gidel et al., 2019].”
Interventional Few-Shot Learning (2020, background): “Nowadays, there are theoretical [3, 8] and empirical [77, 71] evidences showing that disentangled semantic manifolds emerge during training deep networks.”
Kernel and Rich Regimes in Overparametrized Models (2019, background): “[2], and can be thought of as a depth-D diagonal linear network.”
Gradient Starvation: A Learning Proclivity in Neural Networks (2020, background): “The same phenomenon is referred to as implicit bias, implicit regularization, simplicity bias and spectral bias in several works [83, 75, 36, 74, 70, 53, 94, 10, 13, 35, 82, 66].”
Gradient Descent Maximizes the Margin of Homogeneous Neural Networks (2019, background): “Other related works include [Ma et al., 2017, Gidel et al., 2019, Arora et al., 2019a, Suggala et al., 2018, Blanc et al., 2019, Banburski et al., 2019, Neyshabur et al., 2014, 2015].”
Modelling the influence of data structure on learning in neural networks (2019, background): “…played a major role in theoretical studies of the generalisation ability of neural networks from an average-case perspective, particularly within the framework of statistical mechanics [3, 12, 4, 5, 13, 14, 15, 16, 17], and also in recent statistical learning theory works, e.g. [18, 19, 20, 21].”
Machine Learning for Neural Decoding (2017, methodology): “For more complicated methods like neural networks, the assumptions are more complicated (and are still under debate; Arora et al., 2019) but still exist.”
Noise against noise: stochastic label noise helps combat inherent label noise (2021, background): “It is believed to provide a crucial implicit regularization effect (HaoChen et al., 2020; Arora et al., 2019; Soudry et al., 2018) for training overparameterized models.”
Understanding Dimensional Collapse in Contrastive Self-supervised Learning (2021, methodology): “We adapt two useful lemmas from Arora et al. (2019a).”
Implicit Regularization in Deep Learning May Not Be Explainable by Norms (2020, methodology): “[34, 8]), we focus on the case in which the search space is unconstrained, meaning min{dl}l=0 = min{d0, dL} (rank is not limited by the parameterization).”
Machine learning and deep learning—A review for ecologists (2022, positive): “One hypothesis to explain the discrepancy between simple and deep neural networks is that overparameterization combined with stochastic training of the networks (stochastic gradient descent) leads to an implicit regularization (Arora, Cohen, et al., 2019 ; Huh et al., 2021; Li et al., 2021 ).”
What shapes feature representations? Exploring datasets, architectures, and training (2020, background): “The inductive biases of SGD in highly over-parameterized models might contribute to finding solutions that meet various notions of simplicity [3, 4].”
Observational Overfitting in Reinforcement Learning (2019, background): “…connections is implicit regularization (Neyshabur et al., 2015a; Gunasekar et al., 2017; Neyshabur, 2017), as overparametrization through more layer depth and wider layers has proven to have no `p-regularization equivalent (Arora et al., 2019), but rather precondition the dynamics during training.”
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 ”
Contrastive Behavioral Similarity Embeddings for Generalization in Reinforcement Learning (2021, background): “…horizon LQR, it 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…”
The Platonic Representation Hypothesis (2024, neutral): “…in the absence of external influences, deep networks naturally adhere to Occam’s razor, implicitly favoring simple solutions that fit the data (Solomonoff, 1964; Gunasekar et al., 2018; Arora et al., 2019a; Valle-Perez et al., 2019; Huh et al., 2023; Din-gle et al., 2018; Goldblum et al., 2023).”
The Vendi Score: A Diversity Evaluation Metric for Machine Learning (2022, background): “, 2020) and to study the implicit bias of gradient descent for low-rank solutions (Arora et al., 2019).”