Efficient Over-parameterized Matrix Sensing via Alternating Preconditioned Gradient Descent

Thank you for your positive review. We will address your concern in the response below.

In response to your concerns, we provide the following explanation: Our results depend on the over-parameterized rank $r$, which is an artifact of the theoretical analysis. In practice, we do not rely on $r$. As described in Figures 1, 2, and 3 of the main text, the number of observation equations $m = 10n r_\star$, which is independent of $r$. Therefore, even though we only have rank-$r_\star$ RIP, APGD is still able to work. It is worth noting that the core focus of this paper is not on obtaining the optimal rank-$r_\star$ RIP constant. This is a separate direction of research and can be considered as part of our future work.

Thank you for your constructive feedback. Here, we will address your concerns one by one.

Response to weakness 1

Thank you for pointing this out. You are correct that FGD FGD refers to a class of methods that decompose a low-rank matrix into factor matrices and update them using gradient descent. The methods mentioned in the paper, such as ScaledGD$(\lambda)$ and PrecGD, can indeed be regarded as specific instances of FGD. We have added a description of the comparison methods in the experimental section of the revised version, as we believe this will help readers better understand our claims.

Response to weakness 2

Thank you for pointing this out. The baseline for the experiments in Figure 1 is vanilla gradient descent, and we have clarified this in the revised version. Additionally, we have included PrecGD as a comparison method under noisy conditions, since its primary purpose is to handle matrix sensing problems with noise. Due to page limitations in the main text, we have included the experiments under noisy conditions in the supplementary material.

Response to weakness 3

Thank you for your suggestion, which is crucial for improving the quality of our paper. We have emphasized the importance of 'alternating' in the revised version.

Response to question 1

We have added the relevant experiments in the supplementary materials due to page limitations in the main text. The experimental results show that both APGD and PrecGD are robust to the damping parameter under noisy conditions.

Response to question 2

We would be delighted to discuss this issue further with you. As you mentioned, combining preconditioning with similar regularization terms is indeed feasible. We conducted preliminary experiments and included the experimental setup and results in the supplementary material. The results show that adding a regularization term can accelerate convergence for both APGD and ScaledGD$(\lambda)$. However, how to find an appropriate regularization coefficient requires further investigation. Additionally, the theoretical analysis of this approach remains a promising direction for future research.

Thank you for your critical review of our paper. In response to your comments, we would like to clarify the following points:

First, the focus of our work is not on initialization but rather on demonstrating that combining alternating updates with preconditioning achieves superior results. Specifically, APGD alternates updates between the two factor matrices, setting it apart from previous preconditioned methods. This alternating strategy decomposes the original optimization problem into two stages, thereby reducing the Lipschitz constant $L_p$ for each stage and enlarging the feasible range for the step size, i.e., $\eta < \frac{1}{L_p}$.

Second, intuitively, our initialization method does rely on information of $\sigma_{\max}(X_\star)$. However, this requirement is primarily to facilitate theoretical analysis. In practical implementations of the algorithm, it is not strictly necessary to know $\sigma_{\max}(X_\star)$.

Finally, we agree with your suggestion that a more general random initialization, similar to the one used in (Stoger & Soltanolkotabi, 2021), (Lee & Stoger, 2023), and (Xu et al., 2023), would be beneficial. This is indeed an area for improvement in our future work. We are confident that the alternating strategy will remain effective under this general initialization schemes, as evidenced by our experimental results.

Thank you for your positive review and thorough feedback. Below, we would like to take this opportunity to discuss in detail the concerns and questions raised by you:

Response to weakness "The paper's primary theoretical framework relies on the RIP..."

Thank you for your professional suggestions. The Restricted Isometry Property (RIP) is indeed crucial for the analysis in our paper. RIP is a commonly used condition in the field of compressed sensing, which states that the operator $\mathcal{A}(\cdot)$ approximately preserves the distances between low-rank matrices. It serves as a bridge between fully observed and partially observed data. We can first analyze the population case and then extend the results to the sample case using the RIP condition. Without the RIP condition, it may be necessary to derive the results using certain concentration inequalities. Regarding the choice of the RIP constant, the value we selected ensures that $\sigma_{\min}(R_t)$ and $\sigma_{\min}(L_t)$ exhibit a linear convergence rate in the initial phase. While the constant might be optimized further, doing so is not the primary focus of our work. We have included a discussion on the RIP condition in the revised version of the manuscript.

Response to weakness "And the explanation for initialization is missing..."

Thank you for pointing this out. Let us first explain why close to zero initialization does not help. As is well known, gradient dominance is an important property for establishing the convergence of gradient-based methods. The larger the gradient dominance constant $\mu$, the faster the algorithm converges. Based on the analysis presented in our paper, we have $\mu_p=\frac{2(1-\delta_{2r})}{1+\alpha/\sigma_{\min}^2(R_t)}$.

Suppose that we take infinitesimal initialization, i.e., $c_1\to 0$, then we have $\sigma_{min}^2(R_t)\to 0$. If we take $\alpha \le \sigma_{min}^2(R_t)$, i.e., $\alpha \to 0$, this would lead to the singularization of $(R_t^\top R_t+\alpha I)$ and divergence of the algorithm. And if we take $\alpha \ge \sigma_{min}^2(R_t)$, this would lead to a small $\mu_P$, then slow down the convergence. Moreover, a series of studies [1,2,3] have shown that near-zero initialization typically requires a longer time to converge.

In contrast to near-zero initialization, we emphasize that the initialization scale $c_1$ must have a lower bound $c_{init}=\sqrt{\frac{2\alpha}{\sigma_1(X_\star)\sigma_{r_\star}^2(X_\star)\rho^2}}$. This lower bound ensures that, in the first stage, APGD can converge stably and rapidly to a point that is very close to the ground truth.

Response to weakness "In the experimental section, Figures 2 and 3 are presented..."

Thank you for your suggestion. We have added a comparison with PrecGD in Figure 1 as per your recommendation, and we have also adjusted the sizes of Figures 2 and 3.

Response to weakness 'The paper may need thorough proofreading...' and question 1 'Typos and small mistakes in math...'

Thank you for carefully reviewing and pointing out the typos and small mistakes in the paper. We have corrected these issues in the main text and thoroughly reviewed the entire paper to ensure that no similar errors remain.

Dear Reviewer pw3m,

Please let us know if your queries have been addressed satisfactorily. As mentioned in our response, we've thoroughly incorporated your feedback, along with suggestions from the other reviewers. We hope that our response has positively influenced your perception of our work.

If you require further clarifications to potentially reconsider your score, we are enthusiastic about engaging in further discussion. Please do not hesitate to contact us. We highly value the generous contribution of your time to review our paper.