Implicit Regularization in Matrix Factorization

We study implicit regularization when optimizing an underdetermined quadratic objective over a matrix $X$ with gradient descent on a factorization of X. We conjecture and provide empirical and theoretical evidence that with small enough step sizes and initialization close enough to the origin, gradient descent on a full dimensional factorization converges to the minimum nuclear norm solution.

• Publication year

  2017

• Venue

  Information Theory and Applications Workshop

• Publication date

  2017-05-25

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1109/ITA.2018.8503198arXiv 1705.09280
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Python

  2019cited by this paper
• Geometry of Optimization and Implicit Regularization in Deep Learning

  2017cited by this paper
• On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima

  2016cited by this paper
• Understanding deep learning requires rethinking generalization

  2016cited by this paper
• Global Optimality of Local Search for Low Rank Matrix Recovery

  2016influential reference
• Gradient Descent Only Converges to Minimizers

  2016influential reference
• Matrix Completion has No Spurious Local Minimum

  2016influential reference
• In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learning

  2014cited by this paper
• Efficient algorithms for collaborative filtering

  2012cited by this paper
• Concentration-Based Guarantees for Low-Rank Matrix Reconstruction

  2011cited by this paper
• Low-Rank Optimization on the Cone of Positive Semidefinite Matrices

  2008influential reference
• Exact Matrix Completion via Convex Optimization

  2008influential reference
• Uncovering shared structures in multiclass classification

  2007cited by this paper
• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization

  2007influential reference
• Rank, Trace-Norm and Max-Norm

  2005cited by this paper
• Generalization Error Bounds for Collaborative Prediction with Low-Rank Matrices

  2004cited by this paper
• A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization

  2003cited by this paper
• SciPy: Open Source Scientific Tools for Python

  2001cited by this paper

• Is Memorization Helpful or Harmful? Prior Information Sets the Threshold

  2026cites this paper
• NuMuon: Nuclear-Norm-Constrained Muon for Compressible LLM Training

  2026cites this paper
• A Regularization-Sharpness Tradeoff for Linear Interpolators

  2026cites this paper
• Same Error, Different Function: The Optimizer as an Implicit Prior in Financial Time Series

  2026cites this paper
• Pruning as Evolution: Emergent Sparsity Through Selection Dynamics in Neural Networks

  2026cites this paper
• Why Deep Jacobian Spectra Separate: Depth-Induced Scaling and Singular-Vector Alignment

  2026cites this paper
• Data Distribution as a Lever for Guiding Optimizers Toward Superior Generalization in LLMs

  2026cites this paper
• The Representational Alignment Hypothesis: Evidence for and Consequences of Invariant Semantic Structure Across Embedding Modalities

  2026cites this paper
• Grokking Finite-Dimensional Algebra

  2026cites this paper
• Why Inference in Large Models Becomes Decomposable After Training

  2026cites this paper
• On the implicit regularization of Langevin dynamics with projected noise

  2026cites this paper
• Emergent Low-Rank Training Dynamics in MLPs with Smooth Activations

  2026cites this paper
• The Impact of Anisotropic Covariance Structure on the Training Dynamics and Generalization Error of Linear Networks

  2026cites this paper
• Does SGD Seek Flatness or Sharpness? An Exactly Solvable Model

  2026cites this paper
• Implicit regularization of normalized gradient descent

  2026cites this paper
• Why LoRA Resists Label Noise: A Theoretical Framework for Noise-Robust Parameter-Efficient Fine-Tuning

  2026cites this paper
• Implicit Bias in Deep Linear Discriminant Analysis

  2026cites this paper
• Optimal scaling laws in learning hierarchical multi-index models

  2026cites this paper
• Never Saddle for Reparameterized Steepest Descent as Mirror Flow

  2026influential citation
• Diagonalizing the Softmax: Hadamard Initialization for Tractable Cross-Entropy Dynamics

  2025cites this paper
• Saddle-To-Saddle Dynamics in Deep ReLU Networks: Low-Rank Bias in the First Saddle Escape

  2025cites this paper
• Tuning-Free Structured Sparse Recovery of Multiple Measurement Vectors using Implicit Regularization

  2025cites this paper
• Mirror, Mirror of the Flow: How Does Regularization Shape Implicit Bias?

  2025influential citation
• Implicit bias produces neural scaling laws in learning curves, from perceptrons to deep networks

  2025cites this paper
• Exploring a Principled Framework for Deep Subspace Clustering

  2025cites this paper
• Entropic Mirror Descent for Linear Systems: Polyak's Stepsize and Implicit Bias

  2025cites this paper
• Understanding the Evolution of the Neural Tangent Kernel at the Edge of Stability

  2025cites this paper
• Temperature is All You Need for Generalization in Langevin Dynamics and other Markov Processes

  2025cites this paper
• The Features at Convergence Theorem: a first-principles alternative to the Neural Feature Ansatz for how networks learn representations

  2025influential citation
• These Are Not All the Features You Are Looking For: A Fundamental Bottleneck in Supervised Pretraining

  2025cites this paper
• Continuous Representation Methods, Theories, and Applications: An Overview and Perspectives

  2025cites this paper
• IRMAE-AKDE: A Novel Solution to Deep Imbalanced Regression for Performance Prediction of Rolled Steel Plate

  2025cites this paper
• Why is Your Language Model a Poor Implicit Reward Model?

  2025cites this paper
• A Unified Stability Analysis of SAM vs SGD: Role of Data Coherence and Emergence of Simplicity Bias

  2025cites this paper
• Understanding Untrained Deep Models for Inverse Problems: Algorithms and Theory

  2025cites this paper
• LoRaDIP: Low-Rank Adaptation With Deep Image Prior for Generative Low-Light Image Enhancement

  2025cites this paper
• Implicit Bias of Spectral Descent and Muon on Multiclass Separable Data

  2025cites this paper
• How Memory in Optimization Algorithms Implicitly Modifies the Loss

  2025cites this paper
• Forget the Data and Fine-Tuning! Just Fold the Network to Compress

  2025cites this paper
• A Comprehensive Survey on Communication-Efficient Federated Learning in Mobile Edge Environments

  2025cites this paper
• Optimal and Diffusion Transports in Machine Learning

  2025cites this paper
• Neural Collapse under Gradient Flow on Shallow ReLU Networks for Orthogonally Separable Data

  2025cites this paper
• Implicit Unitarity Bias in Tensor Factorization: A Theoretical Framework for Symmetry Group Discovery

  2025cites this paper
• Gradient Descent Robustly Learns the Intrinsic Dimension of Data in Training Convolutional Neural Networks

  2025cites this paper
• Zero Generalization Error Theorem for Random Interpolators via Algebraic Geometry

  2025cites this paper
• Rényi Sharpness: A Novel Sharpness that Strongly Correlates with Generalization

  2025cites this paper
• Single-Head Attention in High Dimensions: A Theory of Generalization, Weights Spectra, and Scaling Laws

  2025cites this paper
• LightSAE: Parameter-Efficient and Heterogeneity-Aware Embedding for IoT Multivariate Time Series Forecasting

  2025cites this paper
• All Roads Lead to Likelihood: The Value of Reinforcement Learning in Fine-Tuning

  2025cites this paper
• Early-Stopped Mirror Descent for Linear Regression over Convex Bodies

  2025cites this paper
• SparsyFed: Sparse Adaptive Federated Training

  2025cites this paper
• Sign-In to the Lottery: Reparameterizing Sparse Training From Scratch

  2025cites this paper
• Challenges and Opportunities for Statistics in the Era of Data Science

  2025cites this paper
• Implicit Balancing and Regularization: Generalization and Convergence Guarantees for Overparameterized Asymmetric Matrix Sensing

  2025cites this paper
• An entropy formula for the Deep Linear Network

  2025cites this paper
• Intrinsic training dynamics of deep neural networks

  2025cites this paper
• Implicit Bias in Matrix Factorization and its Explicit Realization in a New Architecture

  2025influential citation
• The Nuclear Route: Sharp Asymptotics of ERM in Overparameterized Quadratic Networks

  2025cites this paper
• A Dynamics Theory of RMSProp-Based Implicit Regularization in Deep Low-Rank Matrix Factorization

  2025cites this paper
• Reparameterized LLM Training via Orthogonal Equivalence Transformation

  2025cites this paper
• Generalization or Hallucination? Understanding Out-of-Context Reasoning in Transformers

  2025cites this paper
• Convergence guarantees for gradient descent in deep neural networks with non-convex loss functions

  2025cites this paper
• Unpacking the Implicit Norm Dynamics of Sharpness-Aware Minimization in Tensorized Models

  2025cites this paper
• Lyapunov stability of the Euler method

  2025cites this paper
• Understanding Incremental Learning with Closed-form Solution to Gradient Flow on Overparamerterized Matrix Factorization

  2025cites this paper
• Implicit ℓ1-regularization of positively quadratically reparameterized linear regression: precise upper and lower bounds

  2025cites this paper
• Diagonal Linear Networks and the Lasso Regularization Path

  2025cites this paper
• Closed-form ℓr norm scaling with data for overparameterized linear regression and diagonal linear networks under ℓp bias

  2025cites this paper
• Scaling Laws and Spectra of Shallow Neural Networks in the Feature Learning Regime

  2025cites this paper
• Sharpness of Minima in Deep Matrix Factorization: Exact Expressions

  2025cites this paper
• Memorizing Long-tail Data Can Help Generalization Through Composition

  2025cites this paper
• One-Bit Quantization and Sparsification for Multiclass Linear Classification via Regularized Regression

  2024cites this paper
• How Uniform Random Weights Induce Non-uniform Bias: Typical Interpolating Neural Networks Generalize with Narrow Teachers

  2024cites this paper
• Corridor Geometry in Gradient-Based Optimization

  2024cites this paper
• On the Role of Initialization on the Implicit Bias in Deep Linear Networks

  2024cites this paper
• On the dynamics of three-layer neural networks: initial condensation

  2024cites this paper
• SGD vs GD: Rank Deficiency in Linear Networks

  2024cites this paper
• Implicit Regularization via Spectral Neural Networks and Non-linear Matrix Sensing

  2024influential citation
• Linear Recursive Feature Machines provably recover low-rank matrices

  2024cites this paper
• The Implicit Bias of Heterogeneity towards Invariance: A Study of Multi-Environment Matrix Sensing

  2024cites this paper
• Bilinear Sequence Regression: A Model for Learning from Long Sequences of High-dimensional Tokens

  2024influential citation
• S2FT: Efficient, Scalable and Generalizable LLM Fine-tuning by Structured Sparsity

  2024cites this paper
• On Generalization Bounds for Neural Networks with Low Rank Layers

  2024cites this paper
• Tuning-Free Online Robust Principal Component Analysis Through Implicit Regularization

  2024cites this paper
• Improving Adaptivity via Over-Parameterization in Sequence Models

  2024cites this paper
• The Optimality of (Accelerated) SGD for High-Dimensional Quadratic Optimization

  2024influential citation
• Low-Dimension-to-High-Dimension Generalization And Its Implications for Length Generalization

  2024cites this paper
• Optimization Insights into Deep Diagonal Linear Networks

  2024cites this paper
• Multiple Rotation Averaging with Constrained Reweighting Deep Matrix Factorization

  2024cites this paper
• Learning to Compress: Local Rank and Information Compression in Deep Neural Networks

  2024cites this paper
• Approaching Deep Learning through the Spectral Dynamics of Weights

  2024cites this paper
• Weight decay induces low-rank attention layers

  2024cites this paper
• Mask in the Mirror: Implicit Sparsification

  2024cites this paper
• Orthogonal Subspace Decomposition for Generalizable AI-Generated Image Detection

  2024cites this paper
• Benefits of Stochastic Mirror Descent in High-Dimensional Binary Classification

  2024cites this paper
• Simplicity Bias via Global Convergence of Sharpness Minimization

  2024cites this paper
• Multilinear Kernel Regression and Imputation via Manifold Learning

  2024cites this paper
• Bayes-optimal learning of an extensive-width neural network from quadratically many samples

  2024cites this paper
• Lecture Notes on Linear Neural Networks: A Tale of Optimization and Generalization in Deep Learning

  2024cites this paper
• Mini-Workshop: Nonlinear Approximation of High-dimensional Functions in Scientific Computing

  2024cites this paper