Efficient Over-parameterized Matrix Sensing via Alternating Preconditioned Gradient Descent
matrix sensing;over-parameterization;low rank matrix recovery;gradient descent
Yes
No ethics review needed.
Typos and small mistakes in math expressions I found and not complete:
Line 145 Local -> local;
Line 201 should be 0<=delta_r<1;
Line 204 the definition of RIP is defined on ||M||_F^2;
Line 207 Lemma 1 should be a high probability result, that is with probability 1- exp(-...);
Line 250 does not define sigma_min before;
Line 256 right hand side of equation should be 1/2*||A(L_{t+1}R_t^top -X_*)||_2^2;
Line 259 third line of eqn4 (a-b)^2 =a^2+b^2-2ab, the -0.5\eta should multiply by 2;
Line 265 missing );
Line 305 Lt ->L_t;
Line 309 have not defined A^*;
Line 339 reference of equation is not 64 but 62;
Line 397 should be L_t R_t^top;
Line 862 eqn36 should be (1-\eta/2);
Line 1049 second line missing coefficient 2;
Line 1070 same as Line 339;
Line 1239 in eqn 83 there should not be ^\top for (1-\eta_c)


In line 412, the authors assert that their results do not require a bound on L, the gradient Lipschitz constant, but are solely dependent on \delta_2 r. However, the RIP constant is linked with the restricted strongly convex and smooth property. Specifically, the RIP is equivalent to this property with a condition number of (1 + \delta)/(1 - \delta), suggesting that the Lipschitz constant L cannot be entirely disregarded. The authors may need to clarify this relationship and address whether it is possible to completely eliminate the dependence on L in their analysis.
This work introduces a novel approach by combining the preconditioning technique to address the asymmetric matrix sensing case effectively. Unlike Zhang (2024)'s method, in which the second update step relies solely on L_t, the proposed APGD method introduces a modification: the second step updates R_{t+1} using information from L_{t+1} within the same iteration. This strategic adjustment accelerates the convergence, allowing the algorithm to approach the solution more efficiently.

Furthermore, the APGD method offers increased flexibility in parameter selection and random initializations, which significantly enhances its robustness. This flexibility enables APGD to handle larger step sizes without compromising convergence speed or stability, making it a promising choice for practical applications where traditional methods might fail or be too restrictive.

The theoretical analysis in this work follows a two-phase framework. This approach may inspire future studies to analyze optimization tasks that start from a random initialization rather than a local starting point, potentially broadening the range of problems where APGD or similar methods can be applied. The insights from this framework could serve as a basis for analyzing other matrix recovery tasks.
This paper proposes a novel optimization approach, the Alternating Preconditioned Gradient Descent (APGD) method, specifically designed to address challenges in asymmetric matrix sensing problems. The APGD method is developed to tackle the unique difficulties posed by these tasks, especially when the problem is over-parameterized and the matrices involved are ill-conditioned.

The authors rigorously prove that under an over-parameterized setting, starting from a random initialization that is not too close to zero, the APGD method can achieve a linear convergence rate Furthermore, the APGD approach is shown to be more robust to large learning rates and damping parameters, which often destabilize other optimization methods in similar settings.
The paper's primary theoretical framework relies on the RIP, which is central to understanding the convergence guarantees. However, the RIP condition is not fully explained or discussed. For example, the choice of requiring an RIP constant smaller than sqrt(2)-1 is mentioned but not elaborated on. A detailed discussion on the role of RIP in the APGD approach can help to understand the global convergence.

And the explanation for initialization is missing in the main context, it's hard to understand directly why close to zero initialization does not help and the relation between c_init and \sigma_1(X_*).

In the experimental section, Figures 2 and 3 are presented in a format that significantly reduces clarity. The curves in these figures are zoomed in to the extent that it is challenging to distinguish between them based on the legend. Increasing the figure size or changing legend could greatly improve readability. Additionally, a comparison with the PrecGD method is missing in Figure 1. Given the relevance of PrecGD as a related approach, its inclusion in Figure 1 would provide a more comprehensive comparison and highlight the performance differences between APGD and this established baseline.

The paper may need thorough proofreading, especially regarding notation. Some symbols and terms are borrowed from reference papers but are not defined within this paper. This lack of consistent definitions can hinder readability and force the reader to consult external sources, interrupting the flow of understanding. Furthermore, there are minor mistakes in the mathematical expressions, both in the main text and in the appendix. While these errors might not compromise the overall framework or the validity of the theoretical results, they introduce unnecessary obstacles that may lead to misunderstandings.
Yes
No ethics review needed.
1. No evidence shows the initialization scheme is reasonable and practical. It cannot be said to be a contribution.
2. Why does the alternating scheme make sense to the robustness of the choice of hyperparameters?
1. The writing is generally fluent.
2. The proposed algorithm makes sense for addressing the acceleration of ill-conditioning and over-parameterization.
This paper proposes an alternating preconditioned gradient descent for the over-parameterized ill-conditioned asymmetric low-rank matrix sensing problem. The proposed algorithm contains two stages: it starts from a specified initialization and then performs alternating preconditioned gradient descent for the over-parameterized variables $L$ and $R$. The alternating preconditioning technique is claimed to make the algorithm robust to over-parameterization, ill-conditioning, and hyperparameters.
1. The proposed algorithm is not explained well and properly, though it has been investigated in this line of work.
2. The claimed contributions are not well demonstrated and supported, e.g., the intuition and rationality of the proposed initialization, the role of alternating played for robustness and acceleration, and the key novel techniques for the main result.
3. The initialization scheme is not reasonable for the first stage of the algorithm. It needs information about the unknown ground truth. It is more like concealing the spectral initialization and using circular reasoning to prove it works. Previous related work has a much more involved explanation for the effectiveness of small random initialization.
4. For the second stage of the algorithm, it is no surprise that the preconditioning works for the acceleration based on previous work. However, though the introduction claims the robustness and acceleration of the "alternating", the theoretical results do not present it well.
Yes
No ethics review needed.
I have two questions: one concerns the experiments, and the other might go beyond the scope of this paper as a discussion.

1. How does APGD perform in comparison to PrecGD in the sensitivity analysis of the damping parameter in the noisy setting?

2. Alternating preconditioned gradient descent is one approach to solving asymmetric matrix sensing through LR factorization. However, as noted in "Low-rank Solutions of Linear Matrix Equations via Procrustes Flow", adding regularization during the optimization process is another method for asymmetric matrix recovery. Could combining preconditioning with a similar regularization technique be a promising direction for achieving better performance?
This paper introduces the Alternating Preconditioned Gradient Descent (APGD) algorithm, which significantly improves matrix sensing in more practical and real-world settings by relaxing some of the strict assumptions made in prior works. The authors theoretically prove that APGD can still achieve linear convergence to a good solution under these relaxed conditions, highlighting both its theoretical contributions and practical potential. The experiments are well-designed, with appropriate and comprehensive parameter settings. The results align closely with the theoretical findings, further demonstrating that APGD achieves state-of-the-art performance compared to current FGD-based methods.
The paper proposes a novel Alternating Preconditioned Gradient Descent (APGD) algorithm for solving the over-parameterized low-rank matrix sensing problem. The authors address key challenges such as ill-conditioning, over-parameterization, and initialization issues in matrix sensing. The proposed method achieves linear convergence from random initialization, even in the presence of high condition numbers and rank overestimation. Theoretical results are supported by experiments that demonstrate APGD's faster convergence and robustness compared to existing methods.
This paper has a few shortcomings, mainly in its presentation:

1.The abstract emphasizes APGD’s advantages over FGD, but since FGD refers to a class of methods, the paper should explicitly list which algorithms in the comparisons (e.g., ScaledGD) belong to this category, especially in the experimental section. This would help readers quickly verify the claims made in the abstract by directly comparing APGD with FGD-based methods.

2. The paper distinguishes APGD from PrecGD, which is a good approach to comparing with SOTA methods. However, several other algorithms are included in the experiments, and it should be clearly stated which one serves as the baseline. If PrecGD is a key comparison, it would be beneficial to include its performance in the noisy setting of the sensitivity analysis (e.g., damping parameter), or to explain why it was excluded from certain analyses.

3.While the importance and benefits of "alternating" in alternating preconditioned gradient descent are clear from the content for me, this aspect is under-emphasized in the abstract. A stronger focus on this in the abstract would highlight its contribution more effectively.
Yes
No ethics review needed.
In the weaknesses section I mentioned that the theoretical results in work rely on rank-$r$ RIP. Is this an artifact of the theoretical analysis, or is this something that actually appears in experiments? If we only have rank-$r^*$ RIP, does the method still work?
Overall I think this paper is well-written and makes solid contributions. The main problem and its key difficulties are introduced in a natural way. The authors also state very clearly what the prior state of art is. As a result, it is easy to compare the contributions of this work with prior work. 

In terms of the technological contributions, I think it is an important improvement over prior work that the proposed algorithm APGD does not require small initialization. Previous works relied on either small initialization or spectral initialization, both of which can be very expensive (although in different ways). Here the authors show that APGD converges with just random initialization, and is able to both prove this rigorously and demonstrate this in their numerical experiments.
This paper considers the problem of over-parameterized matrix sensing, where the goal is to recover a low-rank matrix $X$ from a limited number of measurements. It was previously known that over-parameterization and ill-conditioning significantly slows down methods like gradient descent. In this work the authors proposed a preconditioned version of alternating GD that starts from a random initialization and converges linearly to the optimal solution.
I did not find any major weaknesses in this paper. However, it is worth noting that previous work which uses small initialization (such as Stoger & Soltanolkotabi, 2021) only requires rank-$r^*$ RIP for the measurement operator, whereas this work requires rank $r$ RIP. I think this fact should be noted, as it can make a big difference when the estimated rank $r$ is very large.
We propose an alternating preconditioned gradient descent (APGD) method to solve low-rank matrix sensing problem in the over- parameterized and ill-conditioned setting.
@inproceedings{
anonymous2024efficient,
title={Efficient Over-parameterized Matrix Sensing via Alternating Preconditioned Gradient Descent},
author={Anonymous},
booktitle={Submitted to The Thirteenth International Conference on Learning Representations},
year={2024},
url={https://openreview.net/forum?id=b6juTJZ1I9},
note={under review}
}
We consider solving the low-rank matrix sensing problem in the over-parameterized setting, where the specified rank is larger than the true rank. Precisely, our main objective is to recover a matrix $X^*\in\mathbb{R}^{n_1\times n_2}$ with rank $r_\star$ using an over-parameterized form $LR^{\top}$, where $L\in\mathbb{R}^{n_1\times r},\ R\in\mathbb{R}^{n_2\times r}$ and $\min(n_1,n_2)\ge r> r_\star$ with the true rank $r_\star$ being unknown. The commonly used methods tackling such a problem such as Factorized Gradient Descent (FGD) can only demonstrate sub-linear convergence behavior, and their performance could significantly deteriorate when the matrix condition number is relatively large. To address this issue, we propose the Alternating Preconditioned Gradient Descent (APGD) method that an inexpensive right preconditioner with a constant damping parameter is applied to the original gradient. We prove that even starting from a random initialization, APGD can recover the target matrix at a linear convergence rate in the over-parameterized situation, independent of the condition number. Notably, unlike previous methods such as FGD, APGD does not rely on small initialization or small step sizes, enabling faster convergence. Through a series of experiments, we demonstrate that APGD achieves the fastest convergence speed compared to other methods, and further possesses of strong robustness with respect to step size, condition number and other parameters.
I certify that there is no URL (e.g., github page) that could be used to find authors’ identity.
I acknowledge that I and all co-authors of this work have read and commit to adhering to the ICLR Code of Ethics.
matrix sensing over-parameterization low rank matrix recovery gradient descent
I certify that there is no acknowledgement section in this submission for double blind review.
/pdf/3475e049a1cd7cc88fb76b594f43be6a06351fd6.pdf
optimization
I understand the reciprocal reviewing requirement as described on https://iclr.cc/Conferences/2025/CallForPapers. If none of the authors are registered as a reviewer, it may result in a desk rejection at the discretion of the program chairs. To request an exception, please complete this form at https://forms.gle/Huojr6VjkFxiQsUp6.
I certify that this submission complies with the submission instructions as described on https://iclr.cc/Conferences/2025/AuthorGuide.
/attachment/07fb9f33c8b67764bb2723a398705c8105319e6a.zip
Efficient Over-parameterized Matrix Sensing via Alternating Preconditioned Gradient Descent
ICLR 2025 Conference Submission
ICLR.cc/2025/Conference/Submission