🔢 mathematics

Convergence of Alternating Gradient Descent to Nuclear-Norm Minimizing Factorizations

This paper proves that alternating gradient descent with small random initialization converges linearly to the unique balanced factorization of a low-rank matrix, which minimizes the nuclear norm, by providing a rigorous analysis that clarifies why certain counterexamples do not apply and distinguishing this behavior from asymmetric or simultaneous gradient descent methods.

Original authors: Anjali Jaiswal

Published 2026-09-30

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Anjali Jaiswal

Original paper licensed under CC BY 4.0 (https://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

In the world of machine learning and data science, there is a fundamental task that appears in everything from recommending movies to compressing images: taking a large, complex table of numbers and breaking it down into two smaller, simpler tables that, when multiplied together, recreate the original. This process is known as matrix factorization. Imagine trying to describe a massive, intricate painting by finding two simpler sketches that, when layered, produce the same image. The challenge is that there are often countless ways to choose these two sketches. Some combinations are mathematically messy, while others are remarkably clean and balanced. For years, researchers have observed that when they use a specific, simple method to find these sketches, the computer almost always picks the cleanest, most balanced version, even though the method itself was not explicitly programmed to look for balance. This phenomenon, where the algorithm seems to have a hidden preference for simplicity, is called implicit regularization, and understanding exactly why it happens has been a major puzzle.

A new study by Anjali Jaiswal at the Indian Institute of Technology Guwahati provides a definitive answer to this puzzle for a specific and widely used method called alternating gradient descent. The research focuses on a scenario where the data is fully visible and the goal is to find the simplest possible breakdown of the numbers. The author proves that when this algorithm starts with a tiny, random guess, it does not just find any solution; it converges with mathematical certainty to the single, unique solution that minimizes the total "size" of the two factor tables. In the language of the field, this means the algorithm naturally selects the factorization that minimizes the nuclear norm, a measure of complexity that corresponds to the most balanced and efficient representation of the data. The study confirms that this behavior is not a lucky accident or a flaw in the proof, but a guaranteed outcome of the algorithm's mechanics, provided the starting point is small and random.

The paper addresses a specific point of confusion in the scientific community. Previous work had shown that in situations where data is incomplete or missing, this same algorithm does not always find the simplest solution, leading some to believe the rule was broken. Jaiswal clarifies that those earlier counterexamples apply to a different, messier problem where the data is incomplete. In the setting studied here, where the full picture is available, the solution space is structured differently. Every possible way to break down the data into two tables forms a specific, closed loop of possibilities. The new research proves that the algorithm acts like a precise selector, navigating this loop to find the one specific point where the two tables are perfectly balanced in size. This balance is the key to minimizing complexity, and the paper demonstrates that the algorithm drives the system toward this state every time.

To reach this conclusion, the author developed a rigorous mathematical argument that tracks the behavior of the algorithm step by step. The proof relies on two main tools. First, a "Lyapunov function" acts as a global energy meter, showing that the overall error of the system decreases steadily with every step the algorithm takes. Second, and more crucially, the author introduces a "balance function" that measures the difference in size between the two factor tables. The analysis reveals that the specific way the algorithm updates the tables—one after the other, rather than simultaneously—creates a unique effect. This alternating rhythm causes the difference in size between the two tables to shrink rapidly, driving them toward perfect equality. The paper shows that this balancing act happens at a predictable, linear speed, meaning the system gets closer to the ideal solution by a fixed percentage with each iteration.

The study also explores what happens when the algorithm is given more freedom than strictly necessary, a scenario known as overparameterization, where the tables are allowed to be larger than the data requires. Even in this case, the algorithm behaves with remarkable discipline. It automatically suppresses the extra, unnecessary parts of the tables, driving them to zero, and still converges to the same balanced, minimal solution found in the simpler case. This suggests that the algorithm's preference for simplicity is robust and does not depend on the tables being exactly the right size.

To verify these theoretical findings, the author ran numerical experiments on a small, five-by-five matrix. The results matched the theory perfectly. When the algorithm started with a symmetric, random guess, the difference between the sizes of the two factor tables vanished completely, and the total complexity reached the theoretical minimum. In contrast, when the experiment was run with an asymmetric starting point or when the tables were updated simultaneously rather than alternately, the system failed to reach this perfect balance. The simultaneous method left a noticeable gap in size between the two tables, and the asymmetric start left a residual imbalance. These experiments confirm that the specific combination of alternating updates and a small, symmetric starting point is the secret ingredient that forces the system to find the simplest possible solution.

This work settles a long-standing question about the behavior of alternating gradient descent in the context of full data recovery. It proves that the algorithm's tendency to find the simplest, most balanced factorization is not a coincidence but a mathematical certainty under the right conditions. By distinguishing this setting from cases with missing data, the paper clarifies the boundaries of where this powerful property holds. The findings offer a deeper understanding of why simple, iterative methods are so effective in practice, revealing that the very structure of the algorithm contains a built-in mechanism for selecting the most elegant solution.

Technical Summary: Convergence of Alternating Gradient Descent to Nuclear-Norm Minimizing Factorizations

Problem Statement
The paper investigates the convergence behavior of the Alternating Gradient Descent (AGD) algorithm applied to the non-convex bilinear matrix factorization problem:
$\min_{X, Y} \frac{1}{2} \|XY^\top - A\|_F^2$
where $A \in \mathbb{R}^{m \times n}$ is a target matrix of rank $r$ . The study considers two settings: the exact-rank case ( $d=r$ ) and the mildly overparameterized case ( $d \ge r$ ). The primary objectives are to establish linear convergence from small random initialization and to characterize the implicit regularization properties of the algorithm, specifically whether it converges to a factorization that minimizes the nuclear norm of the product.

Methodology
The analysis relies on a rigorous decomposition of the iterates and the construction of specific Lyapunov functions.

Initialization and Setup: The algorithm is initialized with small, symmetric, isotropic Gaussian matrices ( $X_0, Y_0$ with i.i.d. $N(0, \delta^2)$ entries). The step size $\eta$ is fixed and sufficiently small.
Rank-1 Analysis: The paper begins with a detailed analysis of the rank-1 case ( $A = \sigma uv^\top$ ). By decomposing iterates into components along the singular directions ( $\alpha_t, \beta_t$ ) and orthogonal residuals ( $x^\perp_t, y^\perp_t$ ), the author proves that the scalar product $p_t = \alpha_t \beta_t$ increases monotonically until it reaches $\sigma$ , while the orthogonal residuals decay geometrically. A key step involves bounding the "balance" between factors ( $|\alpha_t^2 - \beta_t^2|$ ) to show they converge to the balanced fixed point $\alpha_\infty = \beta_\infty = \sqrt{\sigma}$ .
General Rank-r Analysis: For the general case, the author introduces a joint Lyapunov function:
$L_t = \|E_t\|_F^2 + \lambda \|R_t\|_F^2 + \lambda \|S_t\|_F^2$
where $E_t = X_t Y_t^\top - A$ $E_{t} = X_{t} Y_{t}^{⊤} - A$ is the reconstruction error, and $R_t, S_t$ $R_{t}, S_{t}$ represent the components of the factors in the orthogonal complements of the singular subspaces of $A$ $A$ .
- Joint Induction: The proof employs a joint induction argument to resolve the circular dependency between the singular value lower bounds of the factors and the decay of the Lyapunov function.
- Matrix-Valued Monotone Product: The base case for the induction is established using a matrix-valued monotone-product argument, ensuring the smallest singular values of the factor blocks remain bounded away from zero.
Balance Matrix Dynamics: A critical component of the proof is the analysis of the balance matrix $B_t = \tilde{X}_t^\top \tilde{X}_t - \tilde{Y}_t^\top \tilde{Y}_t$ . The author demonstrates that the leading-order corrections to $\tilde{X}_t^\top \tilde{X}_t$ and $\tilde{Y}_t^\top \tilde{Y}_t$ in the Gauss-Seidel update are identical matrix expressions. Consequently, their difference (the balance matrix) decays geometrically, driving the factors toward a balanced state.

Key Contributions and Results

Linear Convergence: The paper proves that AGD converges linearly to the balanced factorization $X_\infty = U\Sigma^{1/2}Q$ and $Y_\infty = V\Sigma^{1/2}Q$ (where $Q$ is an orthogonal matrix). The convergence rate is explicitly dependent on the condition number $\kappa = \sigma_1/\sigma_r$ and the step size, matching the iteration complexity of prior work (e.g., Ward and Kolda) up to constants.
Nuclear-Norm Minimality: The author establishes that the limit of AGD is the unique minimizer of the factorization cost $\|X\|_F^2 + \|Y\|_F^2$ over all factorizations of $A$ . By the inequality $\|X\|_F^2 + \|Y\|_F^2 \ge 2\|XY^\top\|_*$ , this implies the algorithm selects the factorization with the minimum nuclear norm ( $2\|A\|_*$ ).
Resolution of Counterexamples: The paper clarifies why previous counterexamples (Razin–Cohen; Li–Luo–Lyu) do not apply. Those works address underdetermined settings (matrix sensing) where the solution set is not a single orbit and $\|XY^\top\|_*$ is not constant. In contrast, this work addresses the fully observed setting where $XY^\top = A$ is fixed; thus, the nuclear norm of the product is constant, and the algorithm's role is to select the specific balanced orbit element.
Overparameterization: The results extend to the overparameterized setting ( $d > r$ ), showing that the extra columns of $X$ and $Y$ vanish, and the algorithm still converges to the balanced form with the same nuclear-norm minimal cost.
Symmetric Initialization vs. Asymmetric/Simultaneous GD: Numerical experiments confirm that the "balance" property (convergence to equal factor norms) is specific to AGD with symmetric initialization. Asymmetric initialization (as used in Ward–Kolda) leads to a residual imbalance, and simultaneous gradient descent fails to drive the balance matrix to zero, converging more slowly.

Significance and Claims
The paper claims to provide the first rigorous proof that AGD with symmetric small initialization converges linearly to the nuclear-norm minimizing factorization in the fully observed matrix factorization setting. The principal contribution is not merely the convergence rate (which was known via Polyak–Lojasiewicz arguments) but the explicit characterization of the limit point as the balanced, nuclear-norm minimizing solution.

The author emphasizes that their proof makes "to-leading-order" arguments from prior literature fully rigorous by explicitly tracking error terms and utilizing a joint Lyapunov argument with a proven base case. The work complements existing literature (specifically Ward and Kolda) by using a more natural symmetric initialization and providing the missing theoretical justification for the implicit regularization toward the nuclear norm in this specific structural setting.

Technical Summary: Convergence of Alternating Gradient Descent to Nuclear-Norm Minimizing Factorizations

More like this