Implicit Regularization in Deep Learning May Not Be Explainable by Norms

Abstract

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.

References in corpus (28)

• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• Scalable Tensor Factorizations for Incomplete Data
• An overview of low-rank matrix recovery from incomplete observations
• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Smooth PARAFAC Decomposition for Tensor Completion
• Quantum Entanglement in Deep Learning Architectures
• Characterizing Implicit Bias in Terms of Optimization Geometry
• Provable Tensor Factorization with Missing Data
• Gradient descent aligns the layers of deep linear networks
• Gradient Descent Maximizes the Margin of Homogeneous Neural Networks
• Implicit Regularization in Deep Learning
• Identity Matters in Deep Learning
• Implicit Regularization in Deep Learning May Not Be Explainable by Norms
• Overparameterized Nonlinear Learning: Gradient Descent Takes the Shortest Path?
• An analytic theory of generalization dynamics and transfer learning in deep linear networks
• SGD on Neural Networks Learns Functions of Increasing Complexity
• The Implicit Regularization of Stochastic Gradient Flow for Least Squares
• On the Expressive Power of Overlapping Architectures of Deep Learning
• Analysis and Design of Convolutional Networks via Hierarchical Tensor Decompositions
• On Polynomial Time Methods for Exact Low Rank Tensor Completion
• Tensorial Mixture Models
• Dropout: Explicit Forms and Capacity Control
• Minimum weight norm models do not always generalize well for over-parameterized problems
• Boosting Dilated Convolutional Networks with Mixed Tensor Decompositions
• On implicit regularization: Morse functions and applications to matrix factorization
• Implicit Regularization and Convergence for Weight Normalization
• An Optimization and Generalization Analysis for Max-Pooling Networks
• Unique Properties of Flat Minima in Deep Networks

Cited by in corpus (32)

• Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges
• Implicit Regularization in Deep Learning May Not Be Explainable by Norms
• A Geometric Analysis of Neural Collapse with Unconstrained Features
• Shape Matters: Understanding the Implicit Bias of the Noise Covariance
• Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstruction
• The Surprising Simplicity of the Early-Time Learning Dynamics of Neural Networks
• Towards Resolving the Implicit Bias of Gradient Descent for Matrix Factorization: Greedy Low-Rank Learning
• An Unconstrained Layer-Peeled Perspective on Neural Collapse
• The Low-Rank Simplicity Bias in Deep Networks
• When Does Preconditioning Help or Hurt Generalization?
• Implicit Rank-Minimizing Autoencoder
• Implicit Bias in Deep Linear Classification: Initialization Scale vs Training Accuracy
• On the Implicit Bias of Initialization Shape: Beyond Infinitesimal Mirror Descent
• To Each Optimizer a Norm, To Each Norm its Generalization
• Implicit Regularization in ReLU Networks with the Square Loss
• Inductive Bias of Multi-Channel Linear Convolutional Networks with Bounded Weight Norm
• The Benefits of Implicit Regularization from SGD in Least Squares Problems
• Limitations of Implicit Bias in Matrix Sensing: Initialization Rank Matters
• Continuous vs. Discrete Optimization of Deep Neural Networks
• Implicit Gradient Regularization
• Implicit bias of deep linear networks in the large learning rate phase
• Implicit Regularization in Tensor Factorization
• The loss landscape of deep linear neural networks: a second-order analysis
• Implicit Regularization in Matrix Sensing via Mirror Descent
• On Margin Maximization in Linear and ReLU Networks
• Comments on Leo Breiman's paper 'Statistical Modeling: The Two Cultures' (Statistical Science, 2001, 16(3), 199-231)
• Implicit Bias of Linear Equivariant Networks
• Understanding Modern Techniques in Optimization: Frank-Wolfe, Nesterov's Momentum, and Polyak's Momentum
• On the Regularization of Autoencoders
• Rank-One Measurements of Low-Rank PSD Matrices Have Small Feasible Sets
• A Modular Analysis of Provable Acceleration via Polyak's Momentum: Training a Wide ReLU Network and a Deep Linear Network
• The Interplay Between Implicit Bias and Benign Overfitting in Two-Layer Linear Networks