Implicit Regularization in Tensor Factorization
arXiv:2102.09972
Abstract
Recent efforts to unravel the mystery of implicit regularization in deep learning have led to a theoretical focus on matrix factorization -- matrix completion via linear neural network. As a step further towards practical deep learning, we provide the first theoretical analysis of implicit regularization in tensor factorization -- tensor completion via certain type of non-linear neural network. We circumvent the notorious difficulty of tensor problems by adopting a dynamical systems perspective, and characterizing the evolution induced by gradient descent. The characterization suggests a form of greedy low tensor rank search, which we rigorously prove under certain conditions, and empirically demonstrate under others. Motivated by tensor rank capturing the implicit regularization of a non-linear neural network, we empirically explore it as a measure of complexity, and find that it captures the essence of datasets on which neural networks generalize. This leads us to believe that tensor rank may pave way to explaining both implicit regularization in deep learning, and the properties of real-world data translating this implicit regularization to generalization.
arXiv commentAccepted to ICML 2021
References in corpus (29)
- Adam: A Method for Stochastic Optimization
- Scikit-learn: Machine Learning in Python
- Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms
- Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
- 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
- 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
- Understanding training and generalization in deep learning by Fourier analysis
- 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
- SimNets: A Generalization of Convolutional Networks
- Tensorial Mixture Models
- On Polynomial Time Methods for Exact Low Rank Tensor Completion
- Understanding Generalization in Deep Learning via Tensor Methods
- Boosting Dilated Convolutional Networks with Mixed Tensor Decompositions
- Generalized Tensor Models for Recurrent Neural Networks
- Limitations of Implicit Bias in Matrix Sensing: Initialization Rank Matters
- An Optimization and Generalization Analysis for Max-Pooling Networks
- Beyond Lazy Training for Over-parameterized Tensor Decomposition