Implicit Regularization in Deep Learning May Not Be Explainable by Norms

By Noam Razin, Nadav Cohen. 2020

174 citations recorded by the source corpus.

Mathematically characterizing the implicit regularization induced by gradient-based optimization is a longstanding pursuit in the theory of deep learning. A widespread hope is that a characterization based on minimization of norms may apply, and a standard test-bed for studying this prospect is matrix factorization (matrix completion via linear neural networks). It is an open question whether norms can explain the implicit regularization in matrix factorization. The current paper resolves this open question in the negative, by proving that there exist natural matrix factorization problems on which the implicit regularization drives all norms (and quasi-norms) towards infinity. Our results suggest that, rather than perceiving the implicit regularization via norms, a potentially more useful interpretation is minimization of rank. We demonstrate empirically that this interpretation extends to a certain class of non-linear neural networks, and hypothesize that it may be key to explaining generalization in deep learning.

Subfields: Artificial Intelligence, Computational Mechanics, Statistical and Nonlinear Physics, Scaling & Learning Theory

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

1. Lechao Xiao
2. Jeffrey Pennington
3. Wei Hu
4. Ben Adlam
5. Greg Yang
6. Ruslan Salakhutdinov
7. Percy Liang
8. Mohit Bansal

In Computational Mechanics

1. Jeffrey Pennington
2. Wei Hu
3. Lechao Xiao

In Statistical and Nonlinear Physics

1. Lechao Xiao
2. Jeffrey Pennington
3. Wei Hu
4. Greg Yang
5. Sam Schoenholz

In Scaling & Learning Theory

1. Lechao Xiao
2. Jeffrey Pennington
3. Greg Yang
4. Wei Hu
5. Ben Adlam
6. Sam Schoenholz
7. Yuanzhi Li
8. Zeyuan Allen-Zhu

Citations in the corpus

• The Surprising Simplicity of the Early-Time Learning Dynamics of Neural Networks (2020, background): “…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 Bach, 2020, Razin and Cohen, 2020].”
• : "Statistical Modeling: The Two Cultures" (Statistical Science, 2001, 16(3), 199-231) (unknown): “Suddenly the effect of regularization is multi-faceted: parameter, architecture, batch normalization, gradient descent, and more (Neyshabur et al., 2017; Razin and Cohen, 2020).”
• Loss of plasticity in deep continual learning (2024, unknown): “Step size = 0.01 Step size = 0.001”