Implicit Bias in Matrix Factorization and its Explicit Realization in a new Architecture

Additional comments

[Does diagonal entries shrink to zero] Yes, they do. The obtained factors are rank-revealing: either the diagonal entries of D or the columns of U converge to zero, leading to truly low-rank solutions. Specifically, U exhibits a tendency to grow along certain directions, while the rescaling induced by projection onto the bounded constraint shrinks other coordinates. This behavior aligns with the mechanism of the power method and provides insights into the connection with divergent forces.

[Add reconstruction error in Figure 1] It is a good idea. We will incorporate this in the revised version. While this requires running the experiment again, we can report the final test accuracies immediately from our saved results.

Below, we report the relative distance between the true matrix ($X^{\natural}$) and the matrix recovered $(X)$ using $UU^T$ and $UDU^T$ methods. The relative error is computed as: $rel.err = ||X^{\natural} - X||_F / || X^{\natural}||_F$

For the settings in Fig 1., we get

For the noisy setting in Appendix A1, Figure SM1, we obtain

[Matrix/vector notation] You are correct. We adopted the explicit sum notation in the neural network training section as it is standard in that domain. We will clarify the connection.

Lack of insight

We take this opportunity to highlight the key distinction between achieving approximately low-rank solutions and converging to truly low-rank solutions, which underpins the novelty, importance, and extraordinary nature of our observations. Prior theoretical work primarily focuses on achieving approximately low-rank solutions, a goal that is theoretically tractable under certain settings and can often be achieved through standard convex optimization formulations, such as those using nuclear norm penalties. In contrast, our empirical results reveal the remarkable and unexpected observation that the proposed framework consistently converges to truly low-rank solutions. This behavior is fundamentally different and cannot be explained by existing theories on approximate low-rank solutions. While providing theoretical guarantees for convergence to strictly low-rank solutions is beyond the current scope of our work, our findings open intriguing directions for future theoretical research.

Limited Empirical Evaluation

We respectfully disagree with the reviewer’s assessment that the experiments are limited in scope. Observing the bias toward truly low-rank solutions requires running the models for extended periods, which is particularly evident in our matrix factorization examples. This constraint naturally limits the scale of datasets we can investigate in the current work. Nonetheless, we have designed our experiments to test this phenomenon across diverse settings, including matrix factorization problem, phase retrieval, neural network training with regression, classification, and transfer learning tasks, with multiple datasets and loss functions. These varied scenarios provide strong evidence of the generality and robustness of our findings. We do, however, plan to explore this framework in the context of self-attention and other architectures in future work.

Pruning

The main contribution of our paper is the extraordinary observation that UDV networks can identify truly low-rank solutions. We believe this observation is of significant interest to researchers studying the theory of neural networks, as the dynamical behavior exhibited by UDV networks provides insights into the underlying mechanisms of implicit bias in fundamentally different ways compared to existing theories based on gradient flow.

The pruning experiments in our paper are intended as a proof of concept, demonstrating that truly low-rank solutions can also be leveraged for practical purposes. Our goal in this section is not to provide an exhaustive analysis of pruning techniques but rather to illustrate one potential application of our framework. We acknowledge the extensive literature on pruning via low-rank factorization and note that UDV networks can be seamlessly integrated with existing compression and pruning methods. We will add the mentioned references to the discussion of related work.

Lack of insight – why constraints are useful?

We posit that low-rank bias is in fact induced from the divergent dynamics. In matrix factorization experiments, we observe that the factors $UDU^T$ formulation finds are rank-revealing: either the diagonal entries of D or the columns of U converge to zero, leading to truly low-rank solutions. Specifically, U exhibits a tendency to grow along certain directions, while the rescaling induced by projection onto the bounded constraint shrinks other coordinates. This behavior aligns with the mechanisms observed in the power method and provides insights into the connection with divergent forces.

Comparison with Li et al. – is this depth 3 of their approach

We will provide a more detailed discussion of this reference in the revised manuscript. However, their results cannot explain our observations, for instance, we have shown that explicit constraints are crucial to obtain truly low-rank solutions in appendix B5. In the original submission, this comparison was limited to the HPART dataset for a regression task. To address the reviewer's concerns and to strengthen the evaluation, we have now extended this section. Specifically, we have included additional datasets, present results also using cross-entropy loss in classification tasks, and explore transfer learning scenarios. We posit that constraints provide a tighter and more interpretable mechanism for promoting low-rank behavior, as they explicitly restrict the space for U and V. This advantage is particularly evident in our experiments.

Comparison with other factorizations

There seems to be a misunderstanding here. The notion of matrix factorization differs slightly between numerical linear algebra and optimization.

In numerical linear algebra, the focus is on exact or stable decompositions, such as LU, QR, or SVD, to solve systems of equations, compute eigenvalues, or invert matrices with high accuracy and efficiency. In optimization, the focus shifts to approximating structured matrices, such as low-rank or sparse representations, to fit specific models or solve specific problems. For example, in our paper, we use the $UDU^\top$ factorization for the matrix completion problem, where the matrix is incomplete. Notably, you cannot compute an $LDL^\top$ decomposition for an incomplete matrix.

UDV decomposition if r=d

We believe there is a misunderstanding. We are already using full-rank factors in our experiment. Our matrix factorization problems are $n \times n$ dimensional, and we choose $r=n$. Despite having no explicit rank-regularization, the method converges to a low-rank solution.

How does rank of X affect qualities

We get similar results for different choices of rank.

We believe our description was clear: as $U$ tends to grow, the projection onto the Frobenius constraint shrinks non-dominant directions. This is why we mentioned the resemblance to the power method and highlighted the role of divergent dynamics in shaping implicit bias, which also clarifies the role of constraints.

We demonstrate that the UDV model naturally exhibits a bias toward truly low-rank solutions without imposing any rank constraints. In contrast, GLRL operates on an entirely different mechanism, manually enforcing low-rankness. Quote from the reference: “At a high level, GLRL is a greedy algorithm that performs rank-constrained optimization and relaxes the rank constraint by 1 whenever it fails to reach a global minimizer of f with the current rank constraint”.

It is unclear to us what the reviewer means by $X$ in this context. We interpret this as referring to the matrix completion problem and the rank of the ground truth matrix. If this interpretation is correct, we obtained low-rank solutions with good recovery accuracies using UDV, for ground truth matrices with different choices of $r$. Otherwise, we would like to emphasize that our approach does not involve a tunable rank parameter, as we use $(n \times n)$ dimensional factors, and the low-rank nature of the solutions comes from implicit bias.

Formulation is not novel enough

The reviewer claims that comparisons with standard depth-3 models are missing, despite these being explicitly addressed in both the main paper (lines 451–457) and Appendix B5. Furthermore, we have already cited the references brought up by the reviewer, such as (Arora et al. 2019) and (Feng et al. 2022). We are disappointed with this comment, particularly because the reviewer’s confidence score was 5.

Unclear contributions

This paper lies in the observation that the proposed framework consistently converges to truly low-rank solutions. To the best of our knowledge, this behavior has not been reported in prior work and is fundamentally different from achieving approximately low-rank solutions, which are more commonly studied.

We can observe the divergent dynamics especially in matrix factorization experiments. The $UDU^T$ formulation finds factors that are rank-revealing: either the diagonal entries of D or the columns of U converge to zero, leading to truly low-rank solutions. Specifically, U exhibits a tendency to grow along certain directions, while the rescaling induced by projection onto the bounded constraint shrinks other coordinates. This behavior aligns with the mechanisms observed in the power method and provides insights into the connection with divergent forces. We have now included more details on this in the supplementary material.

Lack of analysis and insights into the model

As stated earlier, we have already shown in Appendix B5 that standard depth-3 models do not exhibit the same pronounced spectral decay as our proposed framework. In the original submission, this comparison was limited to the HPART dataset for a regression task. To strengthen the evaluation, we have now extended this section. Specifically, we have included additional datasets, present results also using cross-entropy loss in classification tasks, and explore transfer learning scenarios. We posit that constraints provide a tighter and more interpretable mechanism for promoting low-rank behavior, as they explicitly restrict the space for U and V. This advantage is particularly evident in our experiments.

Moreover, prior theoretical work primarily focuses on achieving approximately low-rank solutions, a goal that is theoretically tractable under certain settings and can often be achieved through standard convex optimization formulations, such as those using nuclear norm penalties. In contrast, our empirical results reveal the remarkable observation that the proposed framework consistently converges to truly low-rank solutions. This behavior is fundamentally different and cannot be explained by existing theories on approximate low-rank solutions. While providing theoretical guarantees for convergence to strictly low-rank solutions is beyond the current scope of our work, our findings open intriguing directions for future theoretical research.

Comparison against weight decay

This is a great suggestion. We conducted preliminary experiments using the regression problem with the HPART dataset, comparing the singular value decay observed in depth-2 and depth-3 fully connected neural networks with weight decay regularization. While increasing the regularization parameter led to faster decay in the singular value spectrum, it came at the cost of worse training and validation loss. We tried regularization parameters $10^{-6}, 10^{-5}, 10^{-4}, \dots$, and selected the largest values where the validation loss was at most 10% worse than the UDV baseline (this appeared around $10^{-3}$ or $10^{-2}$, depending on the algorithm). Under these conditions, the resulting singular value decay was not as pronounced as that of the UDV model. When we increased the regularization parameter further to match or surpass the spectral decay of the UDV model, the resulting validation loss became significantly worse than that of the UDV network. These findings highlight that while weight decay regularization does enhance singular value decay, it cannot replicate the results observed with the UDV model. We will include this preliminary result in the updated submission and plan to extend this analysis to other settings with classification and transfer learning for the final version.

Lack of theoretical analysis

We take this opportunity to clarify the key distinction between achieving approximately low-rank solutions and converging to truly low-rank solutions, which underpins the novelty, importance, and extraordinary nature of our observations. Prior theoretical work primarily focuses on achieving approximately low-rank solutions, a goal that is theoretically tractable under certain settings and can often be achieved through standard convex optimization formulations, such as those using nuclear norm penalties. In contrast, our empirical results reveal the remarkable and unexpected observation that the proposed framework consistently converges to truly low-rank solutions. This behavior is fundamentally different and cannot be explained by existing theories on approximate low-rank solutions. While providing theoretical guarantees for convergence to strictly low-rank solutions is beyond the current scope of our work, our findings open intriguing directions for future theoretical research.

Large scale experiments for pruning

The main contribution of our paper is the extraordinary observation that the UDV model can identify truly low-rank solutions. We believe this observation is of significant interest to researchers studying the theory of neural networks, as the dynamical behavior exhibited by UDV networks provides insights into the underlying mechanisms of implicit bias in fundamentally different ways compared to existing theories based on gradient flow. The pruning experiments in our paper are intended as a proof of concept, demonstrating that truly low-rank solutions can also be leveraged for practical purposes. Our goal in this section is not to provide an exhaustive analysis of pruning techniques but rather to illustrate one potential application of our framework. We acknowledge the extensive literature on pruning via low-rank factorization and note that UDV networks can be seamlessly integrated with existing compression and pruning methods. We adopted singular value thresholding in our experiments only for its simplicity.

Worse performance of the method than BM in A1

It is not correct to consider smaller objective value as better performance – given that the goal is finding a low-rank matrix, approximately low-rank matrices provide a relaxation and the smaller objective in training data does not necessarily translate into a good performance in predicting unobserved instances – in other words, the model is overfitting.

To illustrate this, we report the relative distance between the true matrix ($X^{\natural}$) and the matrix recovered $(X)$ using $UU^T$ and $UDU^T$ methods. The relative error is computed as: $rel.err = ||X^{\natural} - X||_F / || X^{\natural}||_F$ and the results are evaluated after $10^6$ iterations (corresponding to the last iterations in Fig. SM1).

These results demonstrate that $UDU^T$ achieves uniformly better generalization than $UU^T$ ⊤ despite the noisy measurements. (Note that we cannot expect a full recovery in this setting, since the measurements are noisy.)

To further evaluate the performance, we repeated the same experiment for the setting of Fig. 1 (noiseless setting). The results are as follows:

In this noiseless setting, $UDU^\top$ achieves near-perfect recovery, limited only by numerical precision.

Lack of Theoretical Insight

We take this opportunity to clarify the key distinction between achieving approximately low-rank solutions and converging to truly low-rank solutions, which underpins the novelty, importance, and extraordinary nature of our observations. Prior theoretical work primarily focuses on achieving approximately low-rank solutions, a goal that is theoretically tractable under certain settings and can often be achieved through standard convex optimization formulations, such as those using nuclear norm penalties. In contrast, our empirical results reveal the remarkable and unexpected observation that the proposed framework consistently converges to truly low-rank solutions. This behavior is fundamentally different and cannot be explained by existing theories on approximate low-rank solutions. While providing theoretical guarantees for convergence to strictly low-rank solutions is beyond the current scope of our work, our findings open intriguing directions for future theoretical research.

In matrix factorization, we observe in experiments that the UDU formulation finds factors that are rank-revealing: either the diagonal entries of D or the columns of U converge to zero, leading to truly low-rank solutions. Specifically, U exhibits a tendency to grow along certain directions, while the rescaling induced by projection onto the bounded constraint shrinks other coordinates. This behavior aligns with the mechanisms observed in the power method and provides insights into the connection with divergent forces. We have now included this result in the supplementary material.

Limited Novelty

We compared our proposed UDV framework against three-layer fully connected neural networks. In Appendix B5, we provided experimental results demonstrating that our approach exhibits significantly stronger spectral decay than a standard three-layer fully connected network. In the original submission, this comparison was limited to the HPART dataset for a regression task. To address the reviewer's concerns and to strengthen the evaluation, we have now extended this section. Specifically, we have included additional datasets, present results also using cross-entropy loss in classification tasks, and explore transfer learning scenarios. We posit that constraints provide a tighter and more interpretable mechanism for promoting low-rank behavior, as they explicitly restrict the space for U and V. This advantage is particularly evident in our experiments.

Issues with the Formulation “This constraint can be met by scaling down U and scaling up D, so it does not affect the solution set for the optimization problem”

Overparameterized neural networks inherently involve redundancy in their parameterization, as this redundancy facilitates learning and often leads to solutions with better generalization properties (e.g., implicit bias toward low-rank solutions in our setting). In nonconvex optimization, algorithms applied to equivalent formulations can (and often do) converge to different solutions due to the inherent sensitivity of the optimization trajectory to the parameterization and constraints. This principle is a cornerstone of neural network training and is precisely why reparameterizations, such as the one we propose, are valuable. In this context, the claim that the model is "not well-defined" fundamentally misunderstands the standard practice of overparameterization in neural network optimization.

Limited Numerical Experiments:

We respectfully disagree with the reviewer’s assessment that the experiments are limited in scope. Observing the bias toward truly low-rank solutions requires running the models for extended periods, which is particularly evident in our matrix factorization examples. This constraint naturally limits the scale of datasets we can investigate in the current work. Nonetheless, we have designed our experiments to test this phenomenon across diverse settings, including matrix factorization problem, phase retrieval, neural network training with regression, classification, and transfer learning tasks, with multiple datasets and loss functions. These varied scenarios provide strong evidence of the generality and robustness of our findings. We do, however, plan to explore this framework in the context of self-attention and other architectures in future work.

Thank you for the reply. The authors mention that the primary advantage of the proposed method is its ability to achieve low-rank reconstruction even in the presence of noise. However, I am not sure why this would be the case. Given that the loss function in equation (4) will ultimately converge to zero, the reconstruction produced by your method would perfectly fit the noisy, high-rank matrix, rather than yielding a low-rank approximation.