Research map / Learning theory and algorithms / Matrix and tensor methods
Connectivity Shapes Implicit Regularization in Matrix Factorization Models for Matrix Completion
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that data connectivity determines whether small-initialized matrix factorization for matrix completion implicitly finds low-rank (connected) or minimum nuclear norm (disconnected with complete bipartite components) solutions, via a hierarchical invariant manifold traversal (HIMT) theory.
Problem
Prior work disagrees on whether matrix factorization trained by gradient flow from small initialization implicitly favors low nuclear norm or low rank for matrix completion; the role of observation pattern is unclear.
Approach
Data connectivity of the observation bipartite graph governs implicit bias: connected data yields low-rank solutions via a hierarchy of invariant manifolds Omega_k that the trajectory traverses rank by rank (HIMT), while disconnected data induces sub-manifolds that trap the dynamics; with complete bipartite components the minimum nuclear norm solution is reached.
Key results
- Connected observation patterns consistently yield the lowest-rank solution in 3x3 exhaustive experiments, while disconnected patterns do not.
- For disconnected 3x3 matrix M2 with complete bipartite components, the learned solution attains the minimum nuclear norm, whereas disconnected M1 does not.
- Theory: a Hierarchical Invariant Manifold Traversal process is proved, and a minimum nuclear norm guarantee is proved for disconnected data with complete bipartite components.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use connected rather than disconnected observation patterns | Matrix factorization · 3×3 matrix completion, all sampling patterns | rank | Helped |
| use connected rather than disconnected observation patterns | Matrix factorization · 10×10 rank-1 matrix completion | reconstruction error | Helped |
| use disconnected observations with complete bipartite components | Matrix factorization · 3×3 matrix completion, M2 | nuclear norm | Helped |
| use disconnected observations without complete bipartite components | Matrix factorization · 3×3 matrix completion, M1 | nuclear norm | Hurt |
| use connected observations | Matrix factorization · 3×3 matrix completion, M3 | rank | Helped |
| use connected observations | Matrix factorization · 3×3 matrix completion, M3 | nuclear norm | Hurt |
| decrease initialization scale (ablation) | Matrix factorization · Connected matrix completion, target with one unknown element | rank | Helped |
| use larger initialization (ablation) | Matrix factorization · Connected matrix completion, target with one unknown element | rank | Hurt |
| use disconnected observations | Matrix factorization · Disconnected matrix completion, typical experiment | rank | Hurt |
Surprising findings
- Disconnected observation patterns generally fail to reach the minimum-rank solution, even though the connected case does.
- The GLRL equivalence assumed by prior work fails in the disconnected case because the first critical point reached is not a second-order stationary point of the rank-1 manifold.
Limitations
- Overall this is a valid card.
Experimental setup
Datasets: synthetic low-rank matrices
Benchmarks: 3x3 and 4x4 synthetic matrix completion 10x10 rank-1 reconstruction
Metrics: nuclear norm rank singular values reconstruction error loss curves
Baselines: Greedy Low-Rank Learning (GLRL) minimum nuclear norm solution minimum rank solution
Builds on: Greedy Low-Rank Learning (GLRL) embedding principle Li et al. 2020 (implicit regularization of deep linear networks / commutative ob
Closest papers by meaning
- Implicit Regularization in Deep Matrix Factorization (NeurIPS 2019 · similarity 0.90)
- Towards Resolving the Implicit Bias of Gradient Descent for Matrix Factorization: Greedy Low-Rank Learning (ICLR 2021 · similarity 0.90)
- Implicit Regularization in Tensor Factorization (ICML 2021 · similarity 0.89)
- Implicit Regularization in Deep Learning May Not Be Explainable by Norms (NeurIPS 2020 · similarity 0.89)
- Generalization Analysis of Deep Non-linear Matrix Completion (ICML 2024 · similarity 0.87)
- Implicit Regularization for Tubal Tensor Factorizations via Gradient Descent (ICML 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.