Summary
The authors study an algorithm framework for symmetric matrix sensing based on overparametrized Burer-Monteiro matrix factorization which additionally imposes a group lasso penalty on the columns of the factor matrix, and which intertwines a gradient descent-type approach for this objective with iterative pruning.
They argue that gradient descent applied to the unregularized loss does, on the other hand, lead to factor matrices whose generalization properties are negatively affected by magnitude pruning.
As main theoretical contribution, the authors show in Theorem 4 that for a sample complexity whoses dependence is quadratic in the ground truth rank and of order 5 in the overparametrization rank, algorithmic parameters can be chosen appropriately so that after pruning, an approximate second-order stationary point (which can be arguably found via perturbed gradient descent) can be followed by gradient descent to obtain a solution that is close to the ground truth.
A connection to quadratic shallow neural networks is further used to justify similar approaches combing greedy pruning of a regularized loss with post-pruning fine tuning for more complex machine learning models.
Strengths
- The paper provides insights towards relevant insights on how an overparametrized Burer-Monteiro factorization can be made successful and computationally efficient.
- The manuscript is well-structured and clearly written.
- From my point of view, the work provides a theoretical justification of the popular practice in deep neural network training of alternating the pruning weight matrices and fine-tuning steps.
- The technical work to establish the results is quite extensive.
- The benefit of group lasso regularization is for the problem type considered is clearly illustrated in a simple computaitonal experiment.
Weaknesses
- Many of the results in the paper focus on the presented population setting, in which the ground truth is assumed to be known to the algorithm. While they can arguably be seen as paving the road for the setting in which the (regularized) empirical loss minimized, the paper could have benefitted from a clearer focus and presentation on this more realistic case.
- Some relevant literature has not been included in the manuscript. In particular, the proposed group Lasso regularization is presented to be new for the problem in consideration, however, similar regularization and a tailored algorithm was already proposed for the very problem (in the more general rectangular case) in
- Giampouras, Paris V., Athanasios A. Rontogiannis, and Konstantinos D. Koutroumbas. "Alternating iteratively reweighted least squares minimization for low-rank matrix factorization." _IEEE Transactions on Signal Processing_ 67.2 (2018): 490-503.
It also already introduced the pruning step in its algorithm.
Furthermore, a connection of the group Lasso penalty considered with a Schatten-1/2 norm on the product matrix variable was established in:
- Giampouras, P., Vidal, R., Rontogiannis, A., & Haeffele, B. (2020). A novel variational form of the Schatten-$ p $ quasi-norm. _Advances in Neural Information Processing Systems_ (NeurIPS 2020), _33_, 21453-21463.
- The proof of Theorem 1 is potentially erroneous. In particular, in Appendix A, the quantity $r(t)= U^T U_\star$ is not a vector in $\mathbb{R}^k$ , but a $(k \times k)$-matrix. In the proof, it is consistently treated as a vector, which leads to several problematic statements.
Questions
- $f_\operatorname{emp}$ is somehow only defined on page 7. Mentioning it before the introduction of Algorithm 1 will improve the readability of the paper.
- Can the assumptions of Theorem 4 and Theorem 5 be better clarified? It seems that the RIP is used, it would be better be mentioned in the theorems.
- How do we end up with the sample complexity mentioned in Remark 6?
- In line 314, it is mentioned that linear convergence cannot be established due to ill-conditioning of the objective. Please elaborate on whether this could be mitigated algorithms that take the problem structure better into account than standard gradient descent, such as preconditioned examples (e.g., PrecGD from "Zhang, J., Fattahi, S., & Zhang, R. Y. (2021). Preconditioned gradient descent for over-parameterized nonconvex matrix factorization. _Advances in Neural Information Processing Systems_, _34_, 5985-5996.").
Rating
5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Limitations
The authors mostly covered well the limitations of their approach. In the sample complexity results, it would have been beneficial, if would have been better if the suboptimal parameter dependency (at least on $k$ and $n$). had been mentioned.