PaperlayerView exact revision on arXiv

Source-linked AI summary

Towards Resolving the Implicit Bias of Gradient Descent for Matrix Factorization: Greedy Low-Rank Learning

Zhiyuan Li, Yuping Luo, Kaifeng Lyu

arXiv:2012.09839v2cs.LGstat.ML

TL;DR

The paper addresses whether gradient flow’s implicit regularization in matrix factorization is adequately described by nuclear-norm minimization. It connects infinitesimal-initialization gradient flow to Greedy Low-Rank Learning, showing broader rank-minimization behavior and extending the analysis to deeper factorizations.

  • Problem

    Gradient descent’s implicit regularization is not fully characterized by the nuclear-norm conjecture, especially for matrix factorization and deeper models.

  • Method

    The paper analyzes gradient-flow trajectories and compares them with Greedy Low-Rank Learning, extending the comparison from depth 2 to deeper matrix factorizations.

  • Results

    Gradient flow with infinitesimal initialization is generally mathematically equivalent to GLRL for depth-2 matrix factorization, enabling counterexamples to the nuclear-norm conjecture.

  • Takeaways & Limitations

    GLRL provides a more expressive description of implicit regularization than norm minimization and clarifies how depth encourages rank minimization at larger initialization scales.

  • Takeaways & Limitations

    The deep-factorization convergence result describes only the early optimization stage, and one technical assumption is believed removable only with refined analysis.

Abstract

from arXiv · show

Matrix factorization is a simple and natural test-bed to investigate the implicit regularization of gradient descent. Gunasekar et al. (2017) conjectured that Gradient Flow with infinitesimal initialization converges to the solution that minimizes the nuclear norm, but a series of recent papers argued that the language of norm minimization is not sufficient to give a full characterization for the implicit regularization. In this work, we provide theoretical and empirical evidence that for depth-2 matrix factorization, gradient flow with infinitesimal initialization is mathematically equivalent to a simple heuristic rank minimization algorithm, Greedy Low-Rank Learning, under some reasonable assumptions. This generalizes the rank minimization view from previous works to a much broader setting and enables us to construct counter-examples to refute the conjecture from Gunasekar et al. (2017). We also extend the results to the case where depth $\ge 3$, and we show that the benefit of being deeper is that the above convergence has a much weaker dependence over initialization magnitude so that this rank minimization is more likely to take effect for initialization with practical scale.

1 INTRODUCTION

The paper studies gradient descent’s implicit regularization in matrix factorization as a tractable route toward understanding why highly overparameterized neural networks can generalize. It argues that infinitesimal-initialization gradient flow is better characterized by greedy rank minimization than by nuclear-norm minimization alone.

  • Overparameterized neural networks can fit randomly labeled data, motivating a mathematical characterization of the implicit regularization imposed by gradient descent.
  • Low-rank matrix factorization provides a simpler setting for studying implicit regularization, including matrix sensing, completion, phase retrieval, and robust principal component analysis.
  • Even without an explicit rank constraint, small-initialization gradient descent can produce good low-rank solutions, although its mechanism remains debated.
  • Gradient flow with infinitesimal initialization was conjectured to converge to the minimum nuclear norm solution in matrix sensing.
  • Prior work showed that gradient descent amplifies large singular values and attenuates smaller ones, with the effect intensified by depth.
  • The paper proves that infinitesimal-initialization gradient flow is generally equivalent to Greedy Low-Rank Learning, which relaxes rank constraints when lower-rank optimization cannot reach a global minimizer.
  • For deeper matrix factorizations, the paper proves early-stage convergence to a deep GLRL variant and argues that depth makes rank minimization more likely at practical initialization scales.

2 RELATED WORKS

Related work connects implicit regularization to norm or margin maximization and emphasizes that initialization scale strongly affects the bias toward low-rank solutions.

  • Prior studies analyze implicit regularization through norm minimization or the closely related perspective of margin maximization across several model classes.
  • Small initialization is important for biasing gradient descent toward low-rank solutions, whereas sufficiently large initialization can induce lazy training and diminish test accuracy.

3 BACKGROUND

The paper formulates symmetric matrix factorization as optimization over positive semidefinite matrices, defines its gradient-flow dynamics, and focuses on the overparameterized setting without an explicit rank constraint.

  • Matrix factorization optimizes a convex loss of UV^⊤, with matrix sensing reconstructing an unknown low-rank matrix from linear measurements.
  • Matrix completion is a matrix-sensing special case in which each measurement observes one matrix entry.
  • For technical simplicity, the paper studies symmetric factorization with W = UU^⊤ and a C3-smooth convex objective.
  • The symmetric formulation does not lose generality because general matrix factorization can be reduced to it through a transformed factorization and objective.
  • The paper defines gradient flow for U and the corresponding end-to-end dynamics for W = U U^⊤, assuming the trajectory exists for all nonnegative initial PSD matrices.
  • Stationary points in the factorized objective correspond to critical points of the end-to-end dynamics, but critical points need not be minimizers.
  • The main analysis uses the overparameterized case r = d, where W has no explicit rank constraint.

4 WARMUP EXAMPLES

Warmup analyses show that small-initialization gradient flow learns dominant components sequentially: it first favors low-rank directions, then increases rank as needed, while linearization limits the simplest explanation to early dynamics.

  • The paper introduces warmup examples to illustrate how gradient descent performs greedy learning.
  • Linearization Around the Origin: Near the origin, Taylor expansion motivates analyzing a linear loss whose factor dynamics follow continuous power iteration.
  • Linearization Around the Origin: When the top eigenvalue is unique, the linearized dynamics become approximately rank-1 as time increases because the leading eigendirection grows exponentially faster.
  • Linearization Around the Origin: The linear approximation explains low-rank bias only while W remains small, leaving the later nonlinear dynamics unresolved by that analysis.
  • Full-observation Matrix Sensing: For a PSD target with diagonal initialization, each learned component follows a logistic trajectory and transitions sharply from near zero to its target value as initialization vanishes.
  • Full-observation Matrix Sensing: The components are learned one by one in decreasing eigenvalue order, so gradient descent starts with simple models and increases rank when the current model underfits.
  • The paper asks whether this sequential rank-increment behavior holds generally and provides theoretical and empirical evidence that it does.

5 GREEDY LOW-RANK LEARNING (GLRL)

The paper characterizes infinitesimal-initialization gradient flow as following a greedy rank-minimization process, GLRL, that progressively increases rank until reaching a minimizer. This equivalence supports rank-one behavior, produces counterexamples to nuclear-norm minimization, and extends across successive phases under stated assumptions.

  • Equivalence with gradient flow: Under local analyticity and generic assumptions, infinitesimal-initialization gradient flow follows the GLRL trajectory, beginning with rank-1 solutions.The limiting first-phase trajectory has rank at most 1, and when its rank-one endpoint is optimal, gradient flow converges to that endpoint.
  • GLRL algorithm: GLRL alternates rank-constrained optimization with rank increases whenever the current critical point is not a minimizer.Each phase optimizes the factorization until stationarity, then appends a small perturbation column before continuing.
  • GLRL algorithm: The perturbation direction is the unit top eigenvector of −∇f(Wr−1), with magnitude controlled by √ϵ.The loss decreases for this perturbation when the leading eigenvalue is positive.
  • Counterexample to nuclear-norm minimization: The rank-minimization characterization can contradict nuclear-norm minimization: gradient flow converges to a rank-1 solution with nuclear norm 2R^2 + 2 instead of the rank-2 minimum-nuclear-norm solution with norm 4R.For R = 100, these norms are 20002 and 400, respectively.
  • Equivalence with gradient flow: Gradient flow proceeds through phases near critical points, escaping each non-minimizing point along the top principal direction of −∇f until reaching a minimizer.Smaller initialization makes the flow remain longer near each intermediate critical point.

6 BENEFITS OF DEPTH: A VIEW FROM GLRL

For depth L ≥ 3, the paper characterizes gradient-flow dynamics through Deep GLRL and explains why depth strengthens low-rank bias with weaker initialization dependence. Experiments support closer tracking of GLRL critical points and show that additional depth beyond three offers limited further improvement.

  • Deep GLRL characterization: Theorem 6.2 characterizes the limiting trajectory of deep matrix factorization with infinitesimal identity initialization.The analysis uses balanced initialization and an end-to-end dynamics reduction for symmetric solutions.
  • Initialization dependence: Deep solutions can have 1-low-rankness O(α), while the depth-2 solution can scale as Ω(α^(1−µ2/µ1)) under the stated minimizer and regularity assumptions.The argument uses a basin around rank-1 matrices in which gradient flow converges to the minimizer.
  • Deep GLRL characterization: Deep GLRL explains depth as a mechanism for encouraging low-rank solutions through phase-wise greedy rank minimization.The paper compares the low-rankness behavior of depth-2 and deep GLRL across multiple phases.
  • Empirical evidence: Figure 2 shows that GD follows the same critical points as GLRL at small initialization and gets closer to them when L ≥ 3.The experiment uses a rank-3 ground-truth matrix and tracks distance to critical points, gradient norm, and phase-dependent low-rankness.
  • Empirical evidence: Once L ≥ 3, increasing depth does not significantly improve the order of low-rankness, although the result is theoretically established only for identity initialization.The paper additionally reports pointwise convergence of the dynamics as L → ∞ under suitable time rescaling.

7 CONCLUSION AND FUTURE DIRECTIONS

The paper frames gradient descent’s implicit regularization through greedy rank minimization rather than nuclear-norm minimization alone. It connects this view to depth and identifies regularity conditions and extensions as important boundaries for the results.

  • Conclusion: The paper connects gradient descent to Greedy Low-Rank Learning to explain its success in finding low-rank matrix-factorization solutions.This perspective also supports analysis of the benefits of depth.
  • Conclusion: The GLRL perspective enables counterexamples to the implicit nuclear norm conjecture of Gunasekar et al. (2017).The conclusion presents this as a consequence of explaining gradient descent through rank minimization.
  • Future directions: The equivalence between gradient flow with infinitesimal initialization and GLRL relies on regularity conditions that the paper expects to hold generically.Justifying these conditions, possibly through smoothed analysis of the objective, is left for future work.
  • Future directions: Future work includes finding a counterpart of GLRL for training deep neural networks to move beyond norm-minimization descriptions of implicit regularization.The paper presents this as an open direction rather than an established result.

B PROOFS FOR COUNTER-EXAMPLE

This section develops proofs for the counterexample and supporting gradient-flow dynamics, including the construction of rank and nuclear-norm solutions and the initialization schemes used in experiments.

  • The formal conjecture states that sufficiently small-initialization gradient flow converges to the minimum nuclear norm solution.
  • The counterexample compares a rank-constrained solution with nuclear-norm minimization, establishing ∥M_rank∥_* = 2R^2 + 2 > 4R = ∥M_norm∥_* for R > 1.
  • The proof analyzes a reduced two-dimensional gradient flow, establishes boundedness, and shows that its limiting critical point must be the rank solution rather than zero.
  • The nuclear-norm minimizer is uniquely characterized by diagonal entries m_ii = R for i = 1, 2, 3, 4, with the remaining specified entries equal to 1.
  • The experimental setup uses low-rank synthetic ground truth, multiple observation probabilities, balanced factorizations, and gradient-flow simulations with adaptive learning rates for deeper models.

C.2 EXPERIMENTAL EQUIVALENCE BETWEEN GLRL AND GRADIENT DESCENT

The experiments support the claimed relationship between GLRL and gradient descent: their trajectories are close, GLRL recovers low-rank ground truth more effectively than comparison methods, and depth changes initialization requirements and convergence behavior.

  • Experiments provide evidence for equivalence between GLRL and gradient flow for both depth 2 and depth at least 3.
  • Gradient descent trajectories from random initialization remain close to the GLRL trajectory and its critical points.
  • GLRL fully recovers the low-rank ground truth, whereas gradient descent with not-so-small initialization, nuclear-norm minimization, and R1MP have difficulty doing so.
  • GLRL trajectories are closer to the reference matrix by magnitudes, while rank-1 initialization makes gradient descent closer to GLRL than random full-rank initialization.
  • Depth 2 requires exponentially small initialization, whereas deeper models require polynomially small initialization but take longer to converge.
  • With fixed initialization and learning-rate-depth product, deeper models converge faster, while differences become marginal among depths L ≥ 16.

E.2 PROOF FOR THE DIAGONAL CASE

This section proves the diagonal case and extends the limiting-trajectory argument to general Jacobians, using eigenvalue separation, boundedness, local stability, and convergence estimates.

  • The diagonal-case proof begins with a diagonal Jacobian and assumes a unique positive top eigenvalue separated from the remaining eigenvalues and zero.
  • Bounds on the flow control its norm up to a stopping time, enabling estimates for trajectory growth and perturbation stability.
  • The limiting trajectory z(t) exists for every fixed time, and the approximation error satisfies ∥z_α(t) − z(t)∥_2 = O(α).
  • Changing basis reduces the diagonalizable case to the diagonal case, while real Jordan-form analysis extends the result to non-diagonalizable Jacobians.
  • The general extension retains convergence when the top eigenvalue is unique and positive, with the proof controlling block dynamics and applying the earlier estimates.
  • The supporting factorization results classify eigenvalues of the Jacobian and characterize second-order stationary points relevant to the matrix-factorization dynamics.

G.4 GRADIENT FLOW ONLY FINDS MINIMIZERS (PROOF FOR THEOREM 5.10)

This section proves that, for convex objectives, gradient flow in the factorized formulation converges to minimizers rather than unstable stationary points for almost every initialization.

  • The cited convex-factorization theorem supplies the key geometric fact that every local minimizer is global and every saddle is strict.
  • A continuous-time dynamical-systems result states that initial points converging to unstable critical points form a measure-zero set.
  • For convex f, the factorized objective L(U) = f(UU^⊤) has stationary points that are either strict saddles or global minimizers.
  • The proof applies the continuous unstable-fixed-point result to the gradient-flow map and uses the factorized objective's strict-saddle structure.

H EQUIVALENCE BETWEEN GF AND GLRL

Under generic regularity and initialization assumptions, infinitesimal-initialization gradient flow follows the phases of Greedy Low-Rank Learning, adding rank-one directions when lower-rank optimization cannot reach a global minimizer.

  • Phase alignment: GF generically aligns with GLRL at the beginning of each phase under the stated regularity assumptions.The argument proceeds inductively across phases, provided GLRL has not already terminated.
  • Assumptions: The equivalence requires GF to converge to local minimizers, a unique top eigenvalue at relevant critical points, and generic positive alignment near rank-deficient limits.These assumptions govern both phase transitions and the initial alignment with the first GLRL direction.
  • Greedy rank expansion: At each nonoptimal phase, the next rank-one direction is determined by the top eigenvector of −∇f(W^{r−1}), assuming its top eigenvalue is unique.Positive top eigenvalue signals that the current lower-rank point is not optimal.
  • Trajectory properties: PSD GF trajectories preserve both positive semidefiniteness and rank over time, supporting the phasewise comparison with rank-constrained dynamics.For PSD initialization, rank(W(t)) equals rank(W(0)) throughout the trajectory.

I.3 PROOF FOR THEOREM 6.2

The proof of Theorem 6.2 analyzes deep gradient-flow dynamics from infinitesimal identity initialization by reducing the early trajectory to tractable scalar growth and bounding its deviation from a comparison system.

  • Comparison analysis: The analysis introduces comparison trajectories and stopping times to control norm growth and compare the original matrix flow with a simplified system.The lemmas bound trajectories up to thresholds T̂α(c) and then extend the estimates using local Lipschitz continuity.
  • Technical bounds: The proof combines local smoothness, eigenvalue-growth estimates, and perturbation bounds to control nonleading eigenvalues during the escape from initialization.The supplied lemmas separately bound matrix norms, trajectory differences, and eigenvalue growth.
  • Convergence bounds: The proof establishes existence of limiting trajectories and bounds their discrepancy from the comparison dynamics as the initialization magnitude tends to zero.The convergence argument uses Cauchy’s criterion in the early regime and continuity afterward.
  • Setup: The proof reduces the deep dynamics to M(0) = α̂I and diagonalizes −∇f(0), with a unique positive leading eigenvalue μ1.The assumptions impose μ1 > max{μ2, 0} and μ1 = ∥∇f(0)∥2.
  • Scope of the proof: For depths L ≥ 3, the closed-form solution is tractable for diagonal initialization, including identity initialization, but not generally for arbitrary initialization.This analytical obstacle prevents directly extending the two-phase analysis to general initialization.

J ESCAPING DIRECTION FOR DEEP MATRIX FACTORIZATION

For deep matrix factorization, the escape direction is tied to the top eigenvector under rank-1 initialization, while general initialization remains analytically difficult and can exhibit different behavior.

  • General initialization: For general initialization at depth L ≥ 3, the paper proves escape along the top eigenvector only for infinitesimal identity initialization.Analyzing early dynamics for general initialization requires an unavailable tractable solution of the deep flow.
  • Perturbation evidence: The paper conjectures that generic perturbations recover the top-eigenvector direction and reports experiments where noise of magnitude 10^-5 produces that alignment.Larger noise accelerates convergence of the top eigenvector toward v1 in the reported experiment.
  • Rank-1 initialization: With rank-1 initialization having positive overlap with the top eigendirection, the trajectory escapes along the top eigenvector.This result holds for arbitrary depth after a time rescaling because the rank-1 vector follows power iteration.
  • Counterexample: A diagonal depth-4 construction shows that the coordinate with the fastest growth can determine the limiting escape direction, even when it is not the top-gradient eigendirection.In the example, the second coordinate grows fastest and yields M = e2e2^⊤.
  • Experimental setup: The experiment perturbs the constructed initialization with symmetric Gaussian noise and simulates the resulting gradient-flow trajectory for depth 4.Five fixed random seeds are used for each noise level, with RMSprop accelerating the simulation.

K PROOF OF LINEAR CONVERGENCE TO MINIMIZER

Near a rank-k minimizer, the deep dynamics converge linearly under a diagonalizable, stable tangent-space Jacobian; approximately rank-k initialization remains controlled by its negligible component.

  • Local geometry: The tangent space consists of first-order variations of the rank-k symmetric manifold and is invariant under the Jacobian at the minimizer.This permits analysis through the Jacobian restricted to the tangent space.
  • Rank-k initialization: If the tangent-space Jacobian at a rank-k minimizer is diagonalizable with negative real eigenvalues, sufficiently close rank-k trajectories converge linearly.The theorem gives ∥W(t) − W0∥V ≤ Ce^-μ1t ∥W(0) − W0∥V.
  • Proof strategy: The proof controls tangent and orthogonal components separately, with the tangent-space component governing local contraction and the orthogonal component treated as a perturbation.The decomposition uses M(t) as the top-k component and N(t) as the remainder.
  • Almost rank-k initialization: For almost rank-k initialization, the trajectory remains near the rank-k critical point when the negligible component is sufficiently small relative to the main component.The theorem bounds the eventual distance from the critical point at roughly the scale of the initial negligible component.
  • Application to deep GF: For infinitesimal initialization, the trajectory reaches the rank-k neighborhood with error O(α), enabling application of the almost-rank-k convergence theorem.The entry time is chosen so that ∥W(T) − W0∥F = O(∥N(0)∥F) = O(α).
Loading 2012.09839v2…