Implicit Regularization in Tensor Factorization

2021/02/19 by Noam Razin, Razin, Noam, Asaf Maman +3 · 5 citations
Computer Science · Engineering · Mathematics · Physics and Astronomy · #Algorithm #Artificial Intelligence (cs.AI) #Artificial intelligence #Artificial neural network #Computer science #Deep learning #Eigenvalues and eigenvectors #FOS: Computer and information sciences #Factorization #Generalization #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Mathematical analysis #Mathematics #Matrix decomposition #Neural and Evolutionary Computing (cs.NE) #Physics #Pure mathematics #Quantum many-body systems #Regularization (linguistics) #Sparse and Compressive Sensing Techniques #Tensor (intrinsic definition) #Tensor decomposition and applications #Theoretical computer science #cs.AI #cs.LG #cs.NE #stat.ML

paper · pdf · doi:10.48550/arxiv.2102.09972

published in arXiv (Cornell University) (Cornell University) · Accepted to ICML 2021

openalex publication_date 2021/02/19 · arxiv created 2021/06/09 · arxiv updated 2021/06/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Citations

• Adam: A Method for Stochastic Optimization
• SimNets: A Generalization of Convolutional Networks
• Tensor Decompositions and Applications
• Robust Estimation of a Location Parameter
• Most Tensor Problems Are NP-Hard
• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Understanding training and generalization in deep learning by Fourier analysis
• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview

Cited by

• Tuning-Free Structured Sparse Recovery of Multiple Measurement Vectors using Implicit Regularization
• Lyapunov stability of the Euler method
• Learning In-context \pmbn-grams with Transformers: Sub-\pmbn-grams Are Near-stationary Points
• Understanding Deflation Process in Over-parametrized Tensor Decomposition
• Why is Your Language Model a Poor Implicit Reward Model?

Related

• Implicit Regularization in Hierarchical Tensor Factorization and Deep Convolutional Neural Networks
• Implicit Regularization for Tubal Tensor Factorizations via Gradient Descent
• Implicit Regularization in Deep Matrix Factorization
• Low-Rank Tensor Decompositions for the Theory of Neural Networks
• Implicit Regularization in Deep Learning May Not Be Explainable by Norms