Implicit Regularization in Deep Matrix Factorization

Abstract

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.

arXiv commentPublished at the conference on Neural Information Processing Systems (NeurIPS) 2019

References in corpus (14)

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Large Batch Training of Convolutional Networks
• An overview of low-rank matrix recovery from incomplete observations
• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Global Optimality of Local Search for Low Rank Matrix Recovery
• No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis
• Characterizing Implicit Bias in Terms of Optimization Geometry
• Gradient descent aligns the layers of deep linear networks
• Identity Matters in Deep Learning
• An analytic theory of generalization dynamics and transfer learning in deep linear networks
• Generalization Properties and Implicit Regularization for Multiple Passes SGM
• Width Provably Matters in Optimization for Deep Linear Neural Networks
• Implicit Regularization of Discrete Gradient Dynamics in Linear Neural Networks
• Algorithmic Regularization in Learning Deep Homogeneous Models: Layers are Automatically Balanced

Cited by in corpus (25)

• Machine Learning and Deep Learning -- A review for Ecologists
• Deep matrix factorizations
• Understanding Dimensional Collapse in Contrastive Self-supervised Learning
• The generalization error of max-margin linear classifiers: Benign overfitting and high dimensional asymptotics in the overparametrized regime
• Simple, Fast, and Flexible Framework for Matrix Completion with Infinite Width Neural Networks
• Observational Overfitting in Reinforcement Learning
• Implicit competitive regularization in GANs
• Revealing the Structure of Deep Neural Networks via Convex Duality
• Mildly Overparametrized Neural Nets can Memorize Training Data Efficiently
• SCE: Scalable Network Embedding from Sparsest Cut
• The Local Elasticity of Neural Networks
• On implicit regularization: Morse functions and applications to matrix factorization
• Noise-robust latent vector reconstruction in ptychography using deep generative models
• Stochastic Training is Not Necessary for Generalization
• To Each Optimizer a Norm, To Each Norm its Generalization
• Implicit Regularization and Convergence for Weight Normalization
• Spectral Geometric Matrix Completion
• Noether: The More Things Change, the More Stay the Same
• Pure and Spurious Critical Points: a Geometric Study of Linear Networks
• Geometric Matrix Completion: A Functional View
• Explicitly Bayesian Regularizations in Deep Learning
• Understanding Deflation Process in Over-parametrized Tensor Decomposition
• Achieving Small Test Error in Mildly Overparameterized Neural Networks
• Training Linear Neural Networks: Non-Local Convergence and Complexity Results
• Understanding How Over-Parametrization Leads to Acceleration: A case of learning a single teacher neuron