📊 statistics

Implicit Regularization in Perturbed Deep Matrix Factorization: Spectral Conditions and Stability

This paper establishes sufficient spectral conditions and convergence guarantees demonstrating that the low-rank implicit regularization effect in deep matrix factorization remains stable under noise perturbations, with explicit dependencies on the target spectrum, initialization, and perturbation size.

Original authors: Jingzhe Wang, Hung-Hsu Chou

Published 2026-05-28

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Jingzhe Wang, Hung-Hsu Chou

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Finding the "Soul" of a Messy Dataset

Imagine you have a giant, complex puzzle. In the world of deep learning, this puzzle is a matrix (a grid of numbers) that represents real-world data, like images or user preferences. Often, this data is "overparameterized," meaning the puzzle has way more pieces than necessary, making it confusing and messy.

The goal is to find the simplest, cleanest version of this puzzle (a "low-rank" approximation) that still captures the main picture.

The paper investigates a specific tool used to solve this puzzle: Gradient Descent. Think of Gradient Descent as a hiker trying to find the bottom of a valley. The hiker takes steps downhill, hoping to reach the lowest point (the best solution).

The Surprise: Even if you don't tell the hiker to look for a simple solution, the way they walk (the math of the algorithm) naturally leads them to a simple, low-rank solution first. This is called Implicit Regularization. It's like the hiker's footsteps naturally avoiding the thorny bushes and sticking to the smooth path, even without a map telling them to do so.

The Problem: What Happens When the Map is Dirty?

In the real world, data is rarely perfect. It's often corrupted by noise (measurement errors, privacy additions, or random glitches). In the paper's language, the "ground-truth" matrix (the perfect puzzle) is corrupted by a noise matrix ( $E$ ).

The researchers asked: If we give the hiker a dirty, noisy map, will they still find the simple path? Or will the noise make them wander off into the thorny bushes?

The Three Main Discoveries

1. The "Sweet Spot" for a Perfect Map (Noiseless Setting)

First, the authors looked at the ideal scenario where the map is perfect. They wanted to know exactly when the hiker finds the simple path.

The Finding: There is a specific "time window" (a low-rank interval) during the hike where the solution is perfectly simple.
The Analogy: Imagine the hiker is walking through a forest. For a specific amount of time, they are walking on a wide, flat, grassy plain (the low-rank solution). Before that time, they are climbing a steep hill; after that time, they might start wandering into the woods again.
The Conditions: The paper proves that for this "grassy plain" to exist, three things must align:
1. The Landscape (Spectrum): The differences between the "heights" of the data features must be large enough (big gaps between eigenvalues).
2. The Starting Point (Initialization): The hiker must start at the right spot.
3. The Step Size: The hiker must take steps that are neither too big (skipping the plain) nor too small (taking forever to get there).

2. The "Dirty Map" Analysis (Perturbed Setting)

Next, they introduced the noise. The target matrix is now $Target + Noise$.

The Finding: The hiker still finds the grassy plain, but the boundaries of the plain shift slightly.
The Analogy: Imagine the map is now covered in fog and smudges. The hiker can still find the grassy plain, but:
- The plain might start a little later and end a little sooner.
- The hiker might not be exactly in the center of the plain, but they are still very close to it.
- The size of the "smudge" (the noise level) directly determines how much the hiker wanders off-center. The bigger the noise, the wider the margin of error, but the simple solution still exists.

3. The Stability Guarantee

The most important claim is Stability.

The Finding: The "low-rank phase" (the time when the solution is simple) is robust. It doesn't disappear just because there is noise.
The Analogy: Even if you shake the table the puzzle is sitting on, the hiker doesn't fall off the cliff. They might stumble a bit, but they stay on the path. The paper provides mathematical formulas to calculate exactly how much the "start" and "end" times of the simple phase shift based on how loud the noise is.

How They Proved It

The authors didn't just guess; they did a deep dive into the math of the hiker's steps:

Eigenvalue Tracking: They broke the complex matrix down into its individual "vibrations" (eigenvalues). They watched how each vibration changed step-by-step.
The "Gap" Logic: They showed that if the noise isn't too loud, the "gaps" between the important vibrations and the unimportant ones remain large enough to keep the hiker on the simple path.
Numerical Experiments: They ran computer simulations (like a video game of the hiker).
- Figure 1: Showed that with the right step size, you see clear "plateaus" (flat lines) where the solution stays simple. If the step size is wrong, the plateaus vanish.
- Figure 2: Showed that as they added more noise (increased the "smudge"), the plateaus shifted and the error grew slightly, but the hiker never completely lost the path.

Summary in One Sentence

This paper proves that even when your data is noisy and imperfect, the natural way computers learn (gradient descent) will still reliably find simple, low-rank solutions for a specific period of time, and we can mathematically predict exactly how much the noise will nudge that solution.

Technical Summary: Implicit Regularization in Perturbed Deep Matrix Factorization

Problem Statement
Deep learning models, particularly overparameterized ones, often generalize well despite the nonconvex nature of their training objectives. A prevailing explanation is "implicit regularization," where the optimization algorithm (e.g., gradient descent) induces a structural bias toward specific solutions, such as low-rank matrices, even without explicit regularizers. While the behavior of gradient descent in noiseless deep matrix factorization has been analyzed, the stability of this phenomenon under realistic conditions remains an open question. Specifically, this paper investigates how additive noise (perturbations) in the ground-truth target matrix affects the implicit regularization dynamics of deep matrix factorization. The core problem is to determine whether the "low-rank phase"—a transient period where the effective rank of the iterate remains close to a target rank $L$ —persists when the target matrix $\mathbf{W}$ is corrupted by a noise matrix $\mathbf{E}$ , resulting in a perturbed target $\tilde{\mathbf{W}} = \mathbf{W} + \mathbf{E}$ .

Methodology
The authors analyze the dynamics of gradient descent applied to the deep matrix factorization problem:
$\min_{\mathbf{W}_1, \dots, \mathbf{W}_N} \|\mathbf{W}_N \cdots \mathbf{W}_1 - \tilde{\mathbf{W}}\|_F^2$
where $\tilde{\mathbf{W}}$ is the perturbed symmetric ground-truth matrix. The analysis proceeds in three stages:

Noiseless Spectral Analysis: The paper first revisits the noiseless setting to derive explicit sufficient conditions for the existence of a nonempty "low-rank interval" $[T_0, T_1]$ . This involves analyzing the function $T(\lambda)$ , which represents the time required for an eigenvalue $\lambda$ to be recovered. The authors decompose $T(\lambda)$ into components involving logarithmic terms and ceiling functions, proving that under specific spectral gap conditions (large gaps between eigenvalues) and appropriate initialization/step-size choices, the time to recover lower eigenvalues is strictly greater than the time to recover higher ones, creating a window where the effective rank is stable.
Perturbation Modeling and Convergence: The study models the noise $\mathbf{E}$ as a symmetric Gaussian matrix. Using Weyl's inequality and matrix perturbation theory, the authors bound the deviation between the eigenvalues of the perturbed matrix $\tilde{\mathbf{W}}$ and the true matrix $\mathbf{W}$ . They analyze the gradient descent dynamics at the level of individual eigenvalues, establishing convergence guarantees for the perturbed system. The analysis quantifies how the perturbation size $\|\mathbf{E}\|$ affects the iteration complexity and the recovery of non-negative eigenvalues.
Stability of Implicit Regularization: Building on the convergence results, the authors prove that the low-rank phase persists in the perturbed setting. They define a perturbed low-rank interval $[\tilde{T}_0, \tilde{T}_1]$ and derive explicit bounds on the shift of these endpoints relative to the noiseless interval $[T_0, T_1]$ . The analysis relies on tracking the effective rank $r(\mathbf{W}(k)) = \|\mathbf{W}(k)\|_* / \|\mathbf{W}(k)\|$ and bounding the error between the iterate's effective rank and the rank- $L$ approximation of the noiseless target.

Key Contributions

Explicit Spectral Conditions for Noiseless Intervals: The paper provides a rigorous derivation of sufficient spectral conditions (involving eigenvalue gaps, initialization scale $\alpha$ , and step size $\eta$ ) that guarantee the existence of a nonempty low-rank interval $[T_0, T_1]$ in the noiseless case. This clarifies the dependency of the low-rank phase on the target spectrum, which was previously less transparent.
Spectral Stability under Perturbation: The authors establish that the implicit regularization behavior is stable under additive perturbations. They prove that the gradient descent dynamics on the perturbed matrix $\tilde{\mathbf{W}}$ still exhibit a low-rank phase, provided the perturbation size is bounded.
Quantitative Bounds on Perturbation Effects: The work provides explicit error bounds quantifying:
- The shift in the low-rank interval endpoints ( $\tilde{T}_0, \tilde{T}_1$ ) as a function of $\|\mathbf{E}\|$ .
- The approximation error of the effective rank relative to the noiseless target's rank- $L$ approximation.
- The recovery error of non-negative eigenvalues.
Convergence Guarantees: The paper proves convergence of the perturbed gradient descent dynamics and quantifies the iteration complexity required to achieve specific accuracy levels in the presence of noise.

Results

Theoretical Findings: The main theorems (Theorems 5.1–5.3) demonstrate that for a perturbed target $\tilde{\mathbf{W}} = \mathbf{W} + \mathbf{E}$ , the effective rank of the gradient descent iterates remains close to that of the best rank- $L$ approximation of the noiseless target $\mathbf{W}$ over a perturbed time interval. The error bounds are linear in the perturbation size $\|\mathbf{E}\|$ . Specifically, the paper shows that the low-rank interval $[\tilde{T}_0, \tilde{T}_1]$ is a shifted version of $[T_0, T_1]$ , with the shift magnitude dependent on $\|\mathbf{E}\|$ , the spectral gaps, and the step size.
Numerical Validation: Experiments confirm the theoretical predictions. Figure 1 illustrates that the low-rank plateaus (observable implicit regularization) appear when spectral gaps and step sizes satisfy the derived conditions, and disappear when these conditions are violated (e.g., large step sizes). Figure 2 demonstrates that as the noise level increases, the approximation error grows, and the low-rank plateaus shift in time, consistent with the derived bounds.

Significance
The paper claims to provide the first rigorous analysis of implicit regularization in deep matrix factorization under additive perturbations. Its significance lies in bridging the gap between idealized noiseless theoretical models and practical scenarios where data is noisy (e.g., due to measurement errors or privacy-preserving mechanisms like differential privacy). By proving that the low-rank phase is robust to bounded noise and quantifying the degradation in terms of perturbation size, the work offers a theoretical foundation for understanding why deep linear networks can still generalize well in noisy environments. The results suggest that the spectral structure of the target matrix is a critical determinant of both the existence and the stability of implicit regularization.