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

Authors: YIKUN HOU, Suvrit Sra, Alp Yurtsever
Primary area: optimization
Keywords: Implicit Regularization, Matrix Factorization, Neural Networks

Abstract:
Gradient descent for matrix factorization is known to exhibit an implicit bias toward approximately low-rank solutions. While existing theories often assume the boundedness of iterates, empirically the bias persists even with unbounded sequences. We thus hypothesize that implicit bias is driven by divergent dynamics markedly different from the convergent dynamics for data fitting. Using this perspective, we introduce a new factorization model: $X\approx UDV^\top$, where $U$ and $V$ are constrained within norm balls, while $D$ is a diagonal factor allowing the model to span the entire search space. Our experiments reveal that this model exhibits a strong implicit bias regardless of initialization and step size, yielding truly (rather than approximately) low-rank solutions. Furthermore, drawing parallels between matrix factorization and neural networks, we propose a novel neural network model featuring constrained layers and diagonal components. This model achieves strong performance across various regression and classification tasks while finding low-rank solutions, resulting in efficient and lightweight networks.

Decision: reject
Reviewer scores: 3, 3, 3, 5, 3

Reviews and discussion:
<thread>
creation date:
1729812587957

thread_type:
official_review

<thread_object>
creator: reviewer_sbgy

<content>
summary:
Motivated by the literature on the implicit bias towards low rank in matrix factorization, proposes the $UDV^\top$ (and symmetric $UDU^\top$) factorization, which consists of two norm constrained matrices and a diagonal component. Then, empirically shows that this parameterization enjoys a stronger implicit bias towards low-rank solutions, with a weaker dependence on the learning rate and initialization size. Based on the results for matrix factorization, the proposed factorization is evaluated in the context of transfer learning, where it is used to parameterize the linear head of a non-linear neural network base.

strengths:
For standard matrix factorization, the implicit bias towards low rank usually requires a small initialization. Since the origin is a saddle point, this leads to a tradeoff between optimization time and generalization. I find it interesting that the proposed $UDV^\top$ factorization is demonstrated empirically to enjoy an implicit bias towards low rank even for relatively large initializations (and learning rates). This observation can motivate theoretically studying properties of the $UDV^\top$ factorization.

weaknesses:
1. The paper does not provide insight, whether theoretical or empirical, as to why the proposed matrix factorization enjoys a stronger low rank bias that depends less on learning rate and initialization, compared to other matrix factorizations.

2. Given the above, the significance of the contributions hinges on the applicability of the factorization and its empirical evaluation. However, the empirical evaluation is limited. Specifically, the considered datasets are non-standard and outdated (MNIST and a couple of tabular regression datasets), and the results do not seem to suggest that the proposed $UDV^\top$ factorization brings any advantage compared to a standard matrix factorization or a simple two-layer ReLU network head, in the considered transfer learning setting.

3. The novelty of reducing network size with SVD-based pruning is limited. Prior work has already suggested compressing neural networks through low rank matrix (and tensor) decompositions (e.g. [1,2,3]). Furthermore, there is no comparison to these or other alternative network pruning and compression techniques, and the utility of the method proposed in this paper is unclear since it only pertains to the last linear classifier head, leaving the base of the network uncompressed.

At its current form, I find that this work does not meet the bar required for publication at ICLR. I would advise the authors to strengthen either the empirical or theoretical components of their work. In particular, it would be beneficial to use more standard benchmarks (e.g. CIFAR10, ImageNet, or standard datasets from other domains) and compare the low rank pruning method to existing compression and pruning baselines. In terms of theory, any insight as to why the implicit low rank bias of the $UDV^\top$ factorization is more robust compared to that in standard matrix factorizations would also substantially increase the significance of the contributions.


Additional comments:

- It would be interesting to report in the matrix factorization experiments how the singular values evolve under the proposed $UDU^\top$ factorization. Since $D$ is initialized to be the identity, do some of its diagonal entries shrink to zero? This may be an interesting point to try and explain theoretically.

- In Figure 1, it would be useful to report reconstruction error (i.e. how well the learned solution generalizes) alongside the training loss.

- Isn't Equation (6) just $VDU^\top \mathbf{x}$ in a different notation? I believe the connection to the proposed matrix factorization would be more straightforward by writing the equation in matrix notation. Furthermore, what is the purpose of $ \approx y$ in that equation? I would suggest dropping it.

[1] Li, J., Sun, Y., Su, J., Suzuki, T., & Huang, F. (2020, June). Understanding generalization in deep learning via tensor methods. In International Conference on Artificial Intelligence and Statistics (pp. 504-515). PMLR.

[2] Kim, Y. D., Park, E., Yoo, S., Choi, T., Yang, L., & Shin, D. (2015). Compression of deep convolutional neural networks for fast and low power mobile applications. arXiv preprint arXiv:1511.06530.

[3] Yaguchi, A., Suzuki, T., Nitta, S., Sakata, Y., & Tanizawa, A. (2019). Decomposable-Net: Scalable low-rank compression for neural networks. arXiv preprint arXiv:1910.13141.

questions:
--
</content>
</thread_object>

</thread>
<thread>
creation date:
1730197627898

thread_type:
official_review

<thread_object>
creator: reviewer_fryc

<content>
summary:
The main contribution of this work is a novel formulation of the matrix factorization, namely the UDV factorization. The authors conduct a series of numerical experiments to reveal that the proposed formulation has a stronger implicit bias towards low-rank solution than the common factorization $X = UV^T$, which then inspires a structure of neural networks that has the potential to be lightweight by pruning.

strengths:
Overall, this paper is well-written and clearly organized. The idea is simple and straightforward as reflected in Eq. (4). The effect of the proposed formulation is also promising: it clearly exhibits a favor of the low-rank solution, e.g., the singular values decay very fast in Fig. 1. The phenomena observed in this paper definitely give rise to many follow-up questions, e.g., why gradient descent exhibits such a strong preference for low-rank solution compared to other forms of factorization.

weaknesses:
My major concerns are in three aspects.
 
1. The underlying mechanism of the effectiveness of the proposed formulation is completely absent in the current version of this paper. As there is not a clear and compelling motivation for why the formulation proposed in this paper is highly effective for gradient descent to obtain a low-rank solution, I think it is crucial to give a corresponding comprehensive explanation or discussion regarding the effectiveness of the UDV decomposition, including the roles of all the explicit constraints. Even an informal explanation would be helpful for understanding the idea behind the formulation, e.g., why impose these explicit constraints and why they are helpful for finding low-rank solutions?

2. The authors do not carefully discuss the related work Li et al., 2020. Li et al., 2020 clearly showed that gradient flow (GF) prefers low-rank solution by connecting the GF dynamics with Greedy Low Rank Learning (GLRL). In particular, GF implicitly prefers low-rank solution even when $r = d $ for the factorization $X = UU^T, U \in R^{d \times r}$. 

    The lack of a comparison between this work and Li et al., 2020 will induce several key questions. Can the theory in Li et al., 2020 be applied to explain results in this paper as UDV decomposition can be viewed as a three-layer GLRL? What will happen in the UDV decomposition if $r = d$? Does it still exhibit a stronger preference of low-rank solution compared to $UU^T$? What will happen if the constraints on the norms are relaxed, e.g., by assuming a large $\alpha$? 

3. The comparison between the proposed formulation and other related factorizations is absent. There are already a variety of formulations for matrix factorization. In particular, if the UDV decomposition can still be applied in the case with $r = d$, then what are the differences between the UDV decomposition and other ones, say LDLT decomposition, and what are advantages and disadvantages of UDV? More specifically, when will UDV decomposition be a better choice than other decompositions?

Minor comments:

How does the rank of $X$ affect qualities of the recovered solutions for different factorizations? For example, in Fig. 1, if $r$ varies from 3 to 20 ($r = 3$ in Fig. 1), does UDV decomposition still find better solution?

**Reference**

Li et al., 2020. Towards Resolving the Implicit Bias of Gradient Descent for Matrix Factorization: Greedy Low-Rank Learning.

questions:
1. Why is it crucial to impose explicit constraints on norms and why they are helpful for finding low-rank solutions?

2. Can depth-3 GLRL in Li et al., 2020 explain the proposed formulation in this work? If this is not the case, then what will happen in the UDV decomposition if $r = d$ and does it still exhibits a stronger preference of low-rank solution over $UU^T$? 

3. What are the differences between the UDV decomposition and LDLT decomposition?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730259330339

thread_type:
official_review

<thread_object>
creator: reviewer_6ytx

<content>
summary:
In this work the authors introduces a matrix factorization model UDU as an improvement over the traditional BM factorization. The authors claim that while BM factorization find approximate low rank solutions depending on small initialization and lr, the UDU model can find exact low rank solutions independent on initialization scale or stable lr. Then, the authors use this factorization on classification and regression tasks and compare with the two layer UV model.

strengths:
The introduction and the setting of the paper is well established. The proposed method following the lines of past works are clearly written.

weaknesses:
There are several weaknesses in the technical and novelty section of the paper which is highlighted:

*Formulation is not novel enough*


The authors claim that the proposed UDV model leads to faster convergence to low rank solutions irrespective of lr or initialization. However due to lack of analysis, the authors might have missed the fact the model is a mere extension of deep matrix with depth=3 with additional constraints. It is well known that with increasing depth, the solution recovered becomes more low rank. In other words, the residual singular values of the product matrix gets suppresed by the power of depth leading to attenuation of residual singular values, hence stronger low rank. This has been studied in great detail in https://arxiv.org/abs/1905.13655 and followed up in several papers such as https://arxiv.org/abs/2011.13772 and https://arxiv.org/abs/2406.04112. The current model UDV is a depth-3 model with spectral normalization on U and V and diagonal constraint on D. The lack of comparisons or even mention of larger depth models raises question on the novelty of the formulation. 

*Unclear contributions*

The authors mention the dynamics is divergent but in their experiments they show no experiments where this is the case. The paper they cite https://arxiv.org/pdf/2005.06398 only shows divergent behaviours for matrix completion and not for matrix sensing problems. Furthermore, the arcthitecture proposed is just a 3 layer network with spectral normalization on the first, last layer and diagonal contraint on the middle one. There seems to be nothing new about this contribution.

*Lack of analysis and insights into the model*

As stated earlier, the slight advatange the UDV model seems to exhibit is most probably due to the effect of depth which promotes increased attenuation of singular values. Even applying SVT (singular value thresholding) post training to higher depth factors seems to give quite good compression rate https://openreview.net/pdf?id=1KCrVMJoJ9. The lack of any analysis for gradient flow on this model prevents from understanding why this model has slight advantage over BM factorization.

questions:
The primary question is how is the proposed model any different from a deep matrix facrtorization setup with depth>3. There are no experiments comparing higher depth. Is there any difference, if so, can the authors compare and provide analysis and insight for gradient flow?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730275757891

thread_type:
official_review

<thread_object>
creator: reviewer_qwtg

<content>
summary:
The paper looks at the low rank bias of matrix factorization and how to improve upon it. They propose to use a different decomposition of the target matrix and appropriate constraints. The constraints are enforced using a projection. The benefit of the reformulation is shown on a synthetic problem in the paper and additional experiments are provided in the appendix. Moreover, the idea is extended to feedforward neural networks. The paper illustrates using transfer learning that the method is well equipped to prune neurons.

strengths:
The paper is clear in convening the main idea. The idea of the reformulation is to the best of my knowledge novel (although it is directly based on SVD and projected gradient descent). In addition, the extension to neural networks is new. The method outperforms the BM algorithm on several tasks.

weaknesses:
As mentioned by the authors deeper matrix factorization has a lower rank bias. The experiment in appendix B5 shows that just the depth can not explain the bias. This shows the importance of the constraints introduced which act as explicit regularization. Thus, comparing it with explicit regularization such as weight decay is needed. For example, a comparison with weight decay on $U$ and $V$ for the formulation $UV$ which also has been proposed as a pruning strategy in: 

https://openreview.net/forum?id=880tEHqxzg

Furthermore, there is no theoretical analysis of the formulation. For neural networks, an unconstrained optimization problem would get worse results on a metric than a constrained one based on that metric. Similarly, which of the constrained formulations leads to the best (convex) domain? In appendix A1 it is seen that the BM algorithm gets lower residual than the proposed method at the cost of a higher rank. This suggests that the constrained loss landscape is excluding good minimizers. Therefore, looking at the loss landscape might be a needed addition.

The neural network experiments are of small scale. To show that the reformulation can be used as a pruning method it has to work for larger scale experiments as well. Note that there are multiple pruning methods to compare with:

https://arxiv.org/abs/2002.03231

https://arxiv.org/abs/2402.19262

questions:
- Could you please compare with weight decay?
- Provide large scale experiments and comparison to pruning benchmarks.
- Motivate the use of particular constraints by theory or loss landscapes.
- Explain the worse performance of the method than the BM algorithm in A1.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730356936354

thread_type:
official_review

<thread_object>
creator: reviewer_xaqq

<content>
summary:
The paper introduces the use of a three-factor decomposition X=UDV^T of weight matrices along with a strong weight decay penalty during the training of neural networks. It also includes numerical demonstrations of this method's effectiveness on a small dataset.

strengths:
The paper is generally well-written and pleasant to read. The three-factor decomposition appears to be effective.

weaknesses:
**Limited Novelty:** The reasoning behind the improved compression achieved by three-factor decomposition with weight decay has been previously presented in Proposition 4.2 of [1] and this explanation holds for algorithms including gradient descent. While the original proposition does not enforce a diagonal constraint on D, its proof generalizes to the diagonal case. Could the authors clarify how their approach advances beyond the method proposed in [1]? Notably, [1] utilizes a Frobenius norm penalty rather than a constraint—could the authors discuss the potential benefits of using a Frobenius norm constraint over a penalty if any, considering that the latter might simplify implementation?

**Issues with the Formulation:** The reparameterization approach raises concerns due to its reliance on the constraint ∣∣U∣∣_F≤α, which appears redundant. 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. Consequently, optimization problem (4) is not well-defined. If this constraint is intended to influence the solution during the gradient descent update, this section would benefit from revision to avoid presenting (4) with a potentially redundant constraint. 

**Lack of Theoretical Insight**: Since the paper focuses on studying the three-factor reparameterization of a single network layer without nonlinear activation, restricted to gradient descent updates, theoretical insights would be highly expected. Prior work in similar settings with two-factor reparameterization has provided theoretical analysis, which suggests that this problem is amenable to theoretical investigation. Given the existing literature, the paper’s empirical results without theoretical support limit its contribution. Could the authors provide some theoretical analysis on aspects such as convergence rates, optimality conditions, or guarantees on the rank of the solution for their proposed method? How does the theoretical behavior of the three-factor decomposition compare to that of two-factor methods in previous work?

**Limited Numerical Experiments:** The experiments conducted in the paper are limited in scope. Could the authors include comparisons with other state-of-the-art compression methods? Additionally, extending the experiments to larger, more challenging datasets like CIFAR-10 or ImageNet would provide a more comprehensive evaluation of the method's effectiveness and scalability.

[1]Zhang, X., Alkhouri, I. R., & Wang, R. (2024). Structure-Preserving Network Compression Via Low-Rank Induced Training Through Linear Layers Composition. arXiv preprint arXiv:2405.03089.

questions:
Please refer to the weaknesses above. I would consider raising the score if these concerns are adequately addressed
</content>
</thread_object>

</thread>
<thread>
creation date:
1733272338878

thread_type:
official_comment

<thread_object>
creator: authors

<content>
comment:
We appreciate the time and effort the reviewers dedicated to evaluating our work. However, we are disappointed that they failed to recognize, even after the discussions, the fundamental distinction between constraints and regularization. Our paper builds on the observation that Frobenius-norm constraints in matrix factorization (and neural network training) produce truly low-rank solutions. Our proposed formulation produces rank-revealing solutions, where the factors tend to grow in certain directions, while the rescaling induced by projection onto Frobenius norm-ball shrinks other coordinates. This behavior resembles the mechanisms of the power method, drawing connections between the alignment along dominant components and implicit bias. **Our findings are different from the mainstream narrative**, which seems to be one clear reason behind the failure to recognize this paper's main message. We admit, it is our responsibility to clarify the novelty and importance of our results, but the reviewers’ insistence on interpreting our observations within the framework of the mainstream narrative –largely focused on gradient flow dynamics and weight decay regularization– overlooks the crucial **distinction between regularization and constraints on the algorithm's dynamical behavior**, hence misses the core contributions of our work. We argue that **constraints make the implicit bias transparent** and captures the true dynamics. Regularization approximates this behaviour, resulting in approximately low-rank solutions and obscuring the fundamental dynamics that drive implicit bias. We believe **our observations are insightful and hold significant value** for researchers exploring implicit bias.
</content>
</thread_object>

</thread>


Metareview:
metareview:
In this work the authors propose a reparameterization of matrix factorization and neural network linear layer operators into the product of three matrices, where the middle matrix is constrained to be non-negative and diagonal and the left and right matrices are constrained to have bounded Frobenius norm.  The authors argue that the motivation for doing so is to achieve a more pronounced implicit bias towards a low-rank solution due to the optimization dynamics that result from the reparameterization.  The reviewers are all somewhat in agreement that the paper is not ready for publication as the proposed model is somewhat incremental to other works, the paper lack any theoretical analysis, and there are missing comparisons to other closely related works/benchmarks.

Overall, while I find the idea intriguing, I am in agreement with the reviewers that the paper is not yet meeting the bar for publication at ICLR.  There are numerous potential reparameterizations and optimization algorithms one could propose that might be expected to encourage low-rank solutions based on optimization dynamics, but one of the core contributions of the implicit bias literature is to show theoretically that (under certain conditions, loss functions, etc) the optimization dynamics will provably converge to these low-rank solutions.  Unfortunately, much of the argument here appears to be largely empirical, which, while perhaps encouraging, does not meet the typical standard for papers on this topic.

One point highlighted by the authors is that the dynamics induced by their formulation result in "exact" low-rank solutions.  While this is perhaps desirable, it is not particularly surprising to me, since as soon as one of the diagonal elements goes negative during gradient descent the projection onto the non-negative orthant (presumably via simply clipping negative entries) lowers the rank of the factorization.  However, this is a double-edged sword, as depending on the choice of initialization, step-size, etc one could easily truncate the rank of the factorization prematurely from which the algorithm can never recover.  I would encourage the authors to consider theoretical analysis to establish under what conditions the formulation can be guaranteed to succeed.