Source-linked AI summary
Implicit Regularization in Matrix Factorization
Suriya Gunasekar, Blake Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, Nathan Srebro
TL;DR
Underdetermined matrix objectives have many global minima, making the optimization procedure itself a source of implicit bias. The paper studies gradient descent on a matrix factorization, identifies a nuclear-norm bias, and presents empirical and theoretical evidence that small steps and near-zero initialization approach minimum nuclear norm solutions. The analysis also shows that this bias is sensitive to step sizes and differs from the flatter geometry of convex gradient descent.
Problem
Underdetermined objectives admit many global minima, motivating the question of which solution measures different optimization procedures implicitly minimize.
Method
The paper analyzes gradient descent on the factorization X = UU^⊤, using empirical experiments and theoretical analysis of its optimization dynamics.
Results
Gradient descent biases solutions toward low nuclear norm, and with full-dimensional factors, sufficiently small step sizes, and initialization approaching zero, it is argued to converge to a minimum nuclear norm solution.
Takeaways & Limitations
Non-convex factorization can induce a useful implicit bias even when the model class is unchanged and no explicit regularization is imposed.
Takeaways & Limitations
The theoretical analysis cannot ensure the required KKT conditions for arbitrary residual controls in the noncommutative case, and empirical gaps may reflect initialization or numerical issues.
Abstract
from arXiv · showhide
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.
1. Introduction
Underdetermined objectives admit many global minima, so optimization can implicitly select solutions with different generalization behavior. This paper studies that bias in matrix factorization and identifies conditions under which gradient descent favors minimum nuclear norm solutions.
- Motivation: Underdetermined objectives can have many global minima, and optimization algorithms may implicitly bias toward a particular one.This bias acts like regularization even when the objective contains no explicit regularizer.
- Motivation: Deep models can generalize well despite zero training error, overparameterization, and the existence of global minima that generalize poorly.
- Research question: The introduction frames the central question as which measures are implicitly minimized by different optimization procedures.
- Approach: The paper analyzes implicit regularization in matrix factorization viewed as a two-layer linear network.
- Main contribution: Gradient descent on a full dimensional factorization biases optimization toward the minimum nuclear norm solution without constraining the factored matrix.The paper conjectures that sufficiently small step sizes and near-zero initialization yield convergence to that solution, with empirical and theoretical evidence in restricted settings.
2. Factorized Gradient Descent for Matrix Regression
The paper studies underdetermined matrix regression through the factorization X = UU^⊤, especially in the full-dimensional case where no rank constraint is added. Experiments suggest that small-step, near-zero initialized gradient descent favors low nuclear norm solutions, including when reconstruction is impossible.
- Problem setting: The linear operator A maps matrices to measurements through A(X)_i = ⟨A_i, X⟩, covering matrix completion, linear matrix reconstruction, and multi-task training.
- Problem setting: When m ≪ n^2, the matrix regression system is underdetermined and has many global minima, so minimizing the objective alone need not ensure recovery or generalization.In matrix completion, unobserved entries can be assigned arbitrary values while preserving the observed measurements.
- Factorization: The factorization X = UU^⊤ is optimized over U; d < n constrains rank, whereas d = n imposes no additional constraint beyond positive semidefiniteness.
- Experiments: Experiments vary factorization dimension, initialization, and step size on planted 50 × 50 reconstruction problems, measuring training objective and relative reconstruction error.The study includes rank-2, decaying-spectrum, and non-reconstructable settings, with results averaged over three random initializations.
- Results: For sufficiently large d, gradient descent reaches a global optimum, as indicated by zero training error.
- Results: Even for d = n, near-zero initialization and small step sizes produce good reconstructions despite underdetermination.
- Implicit bias: The resulting solutions exhibit lower nuclear norm, including in a setting with too few measurements to reconstruct the planted rank-2 matrix.Figure 2 compares solutions against rank-unconstrained and minimum-nuclear-norm references; the authors report a bias toward lower nuclear norm without explicit regularization or early stopping.
- Conjecture: The convergence target depends on step size and initialization, but full-dimensional gradient descent is argued to approach a minimum nuclear norm solution as step size shrinks and initialization approaches zero.
3. Gradient Flow and Main Conjecture
The paper formulates factorized gradient flow and conjectures that, under full-rank initialization and global convergence, its limiting solution minimizes nuclear norm among feasible positive semidefinite matrices.
- Gradient-flow dynamics: Gradient descent on factor matrices approaches a continuous-time gradient-flow equation as the step size tends to zero.
- Gradient-flow dynamics: The induced dynamics for X_t = U_tU_t^⊤ depend on X_t and the residual r_t, rather than on the particular factorization.
- Gradient-flow dynamics: Factorized gradient flow has different dynamics from standard gradient flow that directly optimizes X.
- Main conjecture: The main conjecture states that, for any full-rank initialization whose small-step limit exists and is globally feasible, the limit minimizes nuclear norm.
- Main conjecture: Full-rank initialization requires a full-dimensional d = n factorization; under this setting, local minima are generally also global minima.
- Main conjecture: The conjectured behavior also applies to asymmetric factorizations X = UV^⊤ under gradient flow on both factors.
4. Theoretical Analysis
The analysis explains why factorized optimization can select minimum-nuclear-norm solutions, proving this for commuting measurement matrices and identifying obstacles in the non-commutative case.
- Commutative case: Gradient descent on the original matrix remains in the measurement span, so any zero-error limit is the minimum Frobenius norm solution.This follows from the KKT conditions for the unconstrained least-squares problem.
- Commutative case: For one measurement matrix, the factorized gradient-flow solution evolves as Xt = exp(stA) X0 exp(stA), with sT determined by the residual control.The analysis uses this path to study the limit from infinitesimal initialization.
- Commutative case: When the measurement matrices commute, Theorem 1 shows that any existing zero-error limit from vanishing initialization solves the minimum nuclear norm problem.The proof verifies dual feasibility and complementary slackness through simultaneous diagonalization.
- Commutative case: The commuting analysis relies on a manifold preserved by gradient flow, and the resulting minimum-nuclear-norm conclusion extends to certain alternative norms and measurement subsets.The manifold is defined through conjugation by exp(A*(s)); its tangent space contains the gradient-flow directions.
- Limits of the analysis: Finite-step gradient descent can leave the non-flat manifold, so the manifold argument directly supports infinitesimal gradient flow rather than ordinary finite steps.The tangent space changes from point to point, making finite-length updates fall off the manifold.
- Limits of the analysis: For non-commuting matrices, time-ordered products leave the commuting manifold, and commutator directions can generate much broader movements than the basic gradient directions.The analysis therefore says residual structure must be exploited rather than relying on arbitrary-control KKT arguments.
5. Empirical Evidence
Additional experiments examine matrix completion and exhaustive small-problem grids, finding trends generally consistent with the minimum-nuclear-norm conjecture while exposing possible discrepancies in some settings.
- Additional matrix completion experiments: Experiments extend evaluation to simulated and real matrix completion, including power-law sampling that violates incoherence assumptions.The study also evaluates non-simulated MovieLens data and numerically solves the gradient-flow ODE.
- Additional matrix completion experiments: Some Figure 3 panels show a gap between the minimum nuclear norm global optimum and the gradient-flow solution initialized with ∥U0∥F = 10^-4.The authors attribute this discrepancy to finite initialization, ODE approximation, or a possible weakening of the conjecture.
- Empirical conclusion: The experiments report strong evidence for at least approximate versions of the conjecture across a wide range of problems.This conclusion is qualified by the observed discrepancies in some panels.
- Exhaustive search: Exhaustive grid search evaluates 15 × 10^4 symmetric p.s.d. 3 × 3 matrix-completion instances from 15 observation masks and 10^4 value combinations.Each instance uses four observations filled with uniformly spaced values in [−1, 1].
- Exhaustive search: Figure 4 measures sub-optimality as ∆(X∞) = ∥X∞∥∗ − ∥Xmin∥∗, comparing the limiting solution's nuclear norm with the minimum feasible nuclear norm.The figure presents a histogram of this quantity across grid-search experiments.
6. Discussion
The paper argues that non-convex factorization selects a particular global minimum through implicit bias, rather than merely establishing global convergence. It identifies the nuclear norm as the relevant bias, while emphasizing dependence on step size and unresolved theoretical difficulty in general cases.
- Discussion: The paper's central contribution is identifying a potentially useful implicit bias induced by non-convex modeling despite equivalent high-capacity model classes.Problems (1) and (2) are equivalent when d = n, yet their optimization dynamics can select differently biased solutions.
- Discussion: Unlike convex gradient descent, the non-convex bias depends delicately on step sizes because the factorization manifold is curved.Momentum and past gradients can leave this manifold, unlike linear combinations of gradients in the flat least-squares setting.
- Discussion: The paper distinguishes selecting among global minima from proving global convergence and does not assume reconstruction, incoherence, or other structural properties.Whether the minimum nuclear norm solution benefits reconstruction or learning is treated as a separate question.
- Discussion: The conjecture is based on extensive simulations spanning reconstructible, nonreconstructible, incoherent, non-incoherent, and exhaustively enumerated problems.The authors state that additional technical conditions or corrections may be needed and discuss a possible proof approach involving control on manifolds and time-ordered exponentials.