Implicit Regularization in Deep Matrix Factorization

Sanjeev Arora; Nadav Cohen; Wei Hu; Yuping Luo

Source-linked AI summary

Implicit Regularization in Deep Matrix Factorization

Sanjeev Arora, Nadav Cohen, Wei Hu, Yuping Luo

arXiv:1905.13655v3May 31, 2019cs.LGcs.AIcs.NEstat.ML

TL;DR

The paper asks how gradient-based optimization regularizes overparameterized models and whether that effect can be described by standard matrix norms. Studying deep matrix factorization through matrix completion and sensing, it finds that greater depth strengthens low-rank bias and recovery, while theory and experiments suggest norm-based descriptions are insufficient. The paper instead advances a dynamical view based on optimization trajectories and singular-value evolution.

Problem
The paper asks how implicit regularization can be characterized independently of validation data and whether standard matrix norms capture it.
Method
The paper studies gradient-based optimization of deep linear neural networks for matrix completion and sensing, analyzing singular-value and singular-vector dynamics in deep matrix factorization.
Results
Greater depth strengthens the implicit tendency toward low-rank solutions, while matrix factorizations outperform nuclear norm minimization when observations are too scarce for exact nuclear-norm recovery.
Takeaways & Limitations
Implicit regularization in matrix factorization may require analyzing optimization dynamics rather than describing the effect with a simple mathematical norm.
Takeaways & Limitations
For depth N ≥3, the product-matrix dynamics cannot be exactly equivalent to gradient descent on the loss with a penalty-term regularizer.

Abstract

from arXiv · show

Efforts to understand the generalization mystery in deep learning have led to the belief that gradient-based optimization induces a form of implicit regularization, a bias towards models of low "complexity." We study the implicit regularization of gradient descent over deep linear neural networks for matrix completion and sensing, a model referred to as deep matrix factorization. Our first finding, supported by theory and experiments, is that adding depth to a matrix factorization enhances an implicit tendency towards low-rank solutions, oftentimes leading to more accurate recovery. Secondly, we present theoretical and empirical arguments questioning a nascent view by which implicit regularization in matrix factorization can be captured using simple mathematical norms. Our results point to the possibility that the language of standard regularizers may not be rich enough to fully encompass the implicit regularization brought forth by gradient-based optimization.

1 Introduction

The paper uses matrix completion as a tractable setting to study implicit regularization from gradient-based optimization. It finds that depth improves low-rank recovery when observations are scarce, while theory and experiments question whether this bias is captured by simple matrix norms.

Deep neural networks can generalize despite having many more learnable parameters than training examples, motivating the study of implicit regularization.
Matrix completion treats observed entries as training data and reconstruction error on unseen entries as test error for evaluating generalization.
Depths 3 and 4 significantly outperform depth 2 with few observed entries, while all factorizations perform well when more entries are available.Figure 1 evaluates depths 2, 3, and 4 on rank-5 and rank-10 matrices of size 100 × 100.
Deep matrix factorization parameterizes a matrix as a product of multiple factor matrices, extending depth-2 matrix factorization to deeper linear networks.
The paper investigates whether deeper factorizations implicitly minimize Schatten quasi-norms or another norm that approximates rank more accurately as depth increases.
Matrix factorizations outperform nuclear norm minimization when observations are too few for nuclear norm minimization to recover exactly, suggesting a stronger low-rank bias than Conjecture 1 predicts.
Singular-value dynamics provide an alternative explanation: evolution rates scale with singular-value size raised to 2 − 2/N, strengthening the tendency toward low rank with depth.

2 Can the implicit regularization be captured by norms?

The paper finds that existing theory can extend nuclear-norm implicit regularization from shallow to arbitrarily deep factorizations under specific assumptions, while experiments challenge whether any single norm captures the broader behavior.

2.1 Current theory does not distinguish depth-N from depth-2: The theory therefore suggests that nuclear norm captures implicit regularization for every depth, despite empirical findings that distinguish deeper factorizations.The paper identifies this theoretical implication as inconsistent with its experimental results.
2.1 Current theory does not distinguish depth-N from depth-2: Theoretical analysis extends nuclear-norm characterization from shallow matrix factorization to arbitrary depth when measurement matrices commute and the limiting solution is a global optimum.The result assumes the small-initialization limit exists and achieves zero loss.
2.1 Current theory does not distinguish depth-N from depth-2: For any d ≥3, there are commuting symmetric sensing instances where the deep-factorization limit minimizes nuclear norm but is not even a local minimum of any Schatten-p quasi-norm with 0 < p < 1.This rules out Schatten quasi-norms as a general explanation in the theorem's setting.
2.2 Experiments challenging Conjecture 1: Experiments indicate that matrix factorization favors lower effective rank at the expense of higher nuclear norm when observations are insufficient for reliable recovery.This behavior is stronger for deeper factorizations and contrasts with the minimum-nuclear-norm solution.
2.2 Experiments challenging Conjecture 1: Because nuclear norm agrees with minimum rank when observations are sufficient but diverges from it in underdetermined cases, experiments suggest optimization dynamics may matter beyond a single norm.The paper consequently hypothesizes that a detailed account of the optimization process may be necessary.

3 Dynamical analysis

The paper characterizes gradient-flow trajectories in deep matrix factorizations, showing that depth changes singular-value dynamics and intensifies movement toward effectively low-rank solutions.

Dynamical analysis: Gradient flow is analyzed for deep linear factorizations of a general analytic loss, assuming balanced factor initialization.The product is W(t)=WN(t)···W1(t), with factor updates obtained by differentiating the factorized objective.
3.1 Implicit regularization towards low rank: Smaller initialization strengthens depth-2 factorization’s implicit tendency toward low rank and may approach the tendency of deeper models only far below customary initialization scales.This observation is reported as an empirical qualification on how initialization interacts with depth.
Dynamical analysis: The product matrix admits an analytic singular value decomposition whose signed singular values and singular vectors can be tracked over time.The singular vectors are the columns of U(t) and V(t), while the diagonal of S(t) contains the signed singular values.
Dynamical analysis: Depth modifies singular-value evolution through factors proportional to N·(σr(t)^2)^(1−1/N), amplifying large singular values and attenuating small ones.The enhancement and attenuation become more pronounced as the factorization depth increases.
Dynamical analysis: Stationary singular vectors imply that U(t)^T∇ℓ(W(t))V(t) is diagonal, establishing alignment between product-matrix and gradient singular vectors.Experiments show diagonal dominance while singular values are moving, consistent with the theoretical alignment result.
3.1 Implicit regularization towards low rank: For deeper factorizations, a larger singular value can continue growing while a smaller one asymptotes, increasing their separation and promoting lower-rank solutions.The analysis contrasts depth 1, depth 2, and depth N≥3, with the asymptotic value of the smaller singular value decreasing as depth grows.

4 Related work

The paper situates its contribution within prior work on implicit regularization in nonlinear and linear networks, emphasizing its focus on deep multi-output linear networks and solution type rather than optimization success or speed.

4 Related work: Prior implicit-regularization research is predominantly empirical for nonlinear networks and theoretically concentrated on single-layer predictors and multilayer linear networks.The paper presents these areas as the main existing lines of theoretical attention.
4 Related work: Matrix factorization is a widely studied linear-network setting for low-rank matrix recovery, with prior work establishing successful recovery under suitable conditions.The related literature includes broad surveys and theoretical recovery results.
4 Related work: The paper claims to be the first study of implicit regularization in deep, three-or-more-layer linear networks with multiple outputs.It distinguishes this setting from prior work where implicit regularization was reported as insensitive to depth.
4 Related work: The work studies which solutions gradient descent reaches, not whether an optimal solution is found or how quickly optimization reaches it.Those complementary convergence and rate questions are attributed to earlier and contemporaneous studies.
4 Related work: Related results include depth-dependent frequency-domain sparsity in linear convolutional networks, whereas the paper analyzes multiple-output matrix factorizations.The comparison highlights a different model structure and implicit-regularization behavior.

5 Conclusion

The conclusion presents deep matrix factorization as a test bed for implicit regularization, arguing that depth-dependent training dynamics promote low rank while standard norms may not fully explain the effect.

5 Conclusion: Theory and experiments on matrix completion and sensing show that adding depth enhances gradient-based optimization’s tendency toward low-rank solutions.The paper frames deep matrix factorization as a stepping stone toward understanding implicit regularization in deep learning.
5 Conclusion: The paper questions whether norm-based explanations adequately capture implicit regularization in matrix factorization.It proposes a dynamical account based on the trajectories traversed during training.
5 Conclusion: Training trajectories may be necessary for understanding generalization and implicit regularization, including in future analyses of nonlinear neural networks.This is stated as the broader implication the authors draw from their study.
5 Conclusion: The theoretical analysis uses gradient flow on a factorized objective with balanced initialization and studies the resulting product-matrix dynamics.The product is formed from factors W1,…,WN, with gradient-flow updates applied to each factor.
A Useful lemmas: The proof relies on a sign-preservation lemma for scalar dynamics, while allowing finite-time divergence when α>1/2.The sign remains preserved until divergence in the latter regime.

B.1 Proof of Theorem 2

The proof establishes nuclear-norm optimality by analyzing transformed diagonal product dynamics, dual feasibility, and a limiting dual certificate under an assumed convergent trajectory.

B.1 Proof of Theorem 2: The proof diagonalizes the measurement operators and product matrix, reducing the dynamics to scalar equations for diagonal coordinates.Simultaneous orthogonal diagonalization is used because the measurement matrices are symmetric and commutable.
B.1 Proof of Theorem 2: For depth N≥3, the diagonal coordinates remain positive and follow an explicit solution derived from the sign-preservation lemma.The transformed product remains diagonal, with positive diagonal entries under the stated initialization.
B.1 Proof of Theorem 2: The argument assumes that the limiting product matrix Wdeep,∞(α)=limt→∞W(t) exists and that the limiting scalar coordinates are finite.These assumptions avoid the technical treatment of infinite coordinates.
B.1 Proof of Theorem 2: Positive definiteness of the transformed limiting matrix yields A†(ν∞(α))≺Id for every α>0.The result is transferred back to the original variables through the orthogonal change of basis.
B.1 Proof of Theorem 2: A limiting sequence of dual-feasible vectors makes the duality gap vanish, proving that the limiting feasible matrix attains the minimum nuclear norm.The primal and dual programs are linked through the bound ν^T y≤OPT and the limit argument.
B.1 Proof of Theorem 2: The proof concludes with ||W*||*=OPT after taking the dual-certificate limit.This identifies the target matrix’s nuclear norm with the primal optimum.

B.2 Proof of Proposition 1

The proof constructs a diagonal measurement system whose deep-factorization limit is diagonal, positive semidefinite, and nuclear-norm minimal, then shows nearby feasible matrices have smaller Schatten-p quasi-norm for every 0 < p < 1.

Construction: Diagonal measurement matrices ensure symmetry and commutativity, and imply that the limiting deep-factorization matrix is diagonal and positive semidefinite.The construction uses diagonal A1, ..., Am and invokes Theorem 2's proof for the structural implication.
Nuclear-norm property: The matrices A1, ..., Am are linearly independent, while the limiting matrix has minimal nuclear norm among positive semidefinite matrices satisfying the equations.For positive semidefinite matrices, nuclear norm equals trace.
Construction: The constructed limit is ¯Wdeep = diag(1, 1, 0, 0, ..., 0).
Schatten-p comparison: For every 0 < p < 1, a nearby positive semidefinite feasible matrix is constructed with strictly smaller Schatten-p quasi-norm.The nearby matrix uses eigenvalues 1 + ϵ and 1 − ϵ, and approaches ¯Wdeep as ϵ → 0+.
Schatten-p comparison: The smaller quasi-norm follows from strict concavity of θp(x) = x^p on R≥0.

B.3 Proof of Lemma 1

The proof differentiates an analytic singular value decomposition of the product matrix and combines orthonormality, skew-symmetry, and projections to derive evolution equations for singular vectors and values.

Analytic decomposition: Analyticity of the loss and gradient-flow factors makes the product matrix W(t) analytic, enabling differentiation of its singular value decomposition.
Regularity conditions: Assuming nonzero and distinct singular values away from isolated times, the proof derives expressions for U̇(t) and V̇(t), then extends them to isolated points by continuity.
Singular-value dynamics: Differentiating W(t) = U(t)S(t)V^⊤(t) and multiplying by U^⊤(t) and V(t) isolates the singular-value and singular-vector dynamics.
Singular-value dynamics: Orthonormality makes U^⊤(t)U̇(t) and V̇^⊤(t)V(t) skew-symmetric with zero diagonals, so the diagonal part determines Ṡ(t).
Projection decomposition: The resulting formulas use projections PU(t) and PU⊥(t), with PU⊥(t) = Id − U(t)U^⊤(t), to separate subspace and orthogonal-complement components.

B.6 Proof of Corollary 1

The proof extends the derived differential relation to all times by continuity and uses nonzero singular values to show that stationary singular-vector dynamics require a diagonal transformed gradient.

Regularity conditions: The derivation initially assumes all singular values are nonzero and pairwise distinct, with exceptional times treated as isolated points.
Stationary singular vectors: When U̇(t) = 0 and V̇(t) = 0, the derived relation implies that U^⊤(t)∇ℓ(W(t))V(t) is diagonal.
Regularity conditions: Continuity carries the relation over to isolated times where the nonzero or distinct-singular-value conditions fail.
Stationary singular vectors: Because the product matrix starts full-rank and the factorization is non-degenerate with N ≥ 2, the singular-value evolution is used to establish the result across time.

C Extension of [20] to asymmetric matrix factorization

The paper extends the nuclear-norm characterization from symmetric shallow factorizations to asymmetric depth-2 factorizations under commuting measurements, and relates the proof to matrix-sensing experiments.

Asymmetric factorization: The extension studies gradient flow for asymmetric depth-2 factors initialized at W1 = W2 = αI and considers the α → 0 optimization limit.
Nuclear-norm characterization: If the limiting product exists, reaches zero loss, and the measurement matrices commute, it is a global optimum with minimal nuclear norm.
Proof strategy: The proof uses positivity of the diagonalized product and shows that its dynamics coincide with those for symmetric matrix factorization.
Matrix sensing experiment: Figure 4 uses random projections for matrix sensing rather than a randomly chosen subset of matrix entries, while otherwise matching Figure 1.

D.1 Further experiments

Figures 4, 5, and 6 provide matrix sensing experiments that supplement the matrix completion experiments in Figures 1, 2, and 3.

Figures 4, 5, and 6 report matrix sensing experiments.These experiments supplement the matrix completion experiments in Figures 1, 2, and 3.
Figure 4 supplements the matrix completion experiments in Figure 1.
Figures 5 and 6 supplement the matrix completion experiments in Figures 2 and 3, respectively.

D.2 Implementation details

The experiments use Python and specified synthetic-data, optimization, initialization, and evaluation procedures for deep matrix factorizations.

The implementation uses PyTorch for deep matrix factorizations and CVXPY for minimum nuclear norm solutions.Source code is provided in the cited repository.
Random rank-r matrices are generated as UV^⊤ with independently standard-normal entries in U and V.Synthetic sensing measurement-matrix entries are also independently drawn from a standard normal distribution.
Deep matrix factorizations are trained by full-batch gradient descent on ℓ2 loss without explicit regularization.The loss uses observed entries for completion and given projections for sensing; weights are Gaussian-initialized.
Figure 5 evaluates nuclear-norm behavior using matrix sensing with random projections instead of randomly chosen matrix entries.The projections are measurements of the ground-truth matrix using Gaussian-drawn measurement matrices.
Figure 6 illustrates gradient-descent dynamics for matrix sensing using 2000 random projections instead of 2000 randomly chosen entries.The measurement matrices are drawn independently from a Gaussian distribution.
Dynamics illustrations use learning rate and initialization standard deviation 10^-3, while nuclear-norm evaluations vary both over 10^-3, 5 · 10^-4, and 2.5 · 10^-4.Error bars represent standard deviation over three initialization seeds, and reconstruction error is normalized Frobenius distance.