Globally Q-linear Gauss-Newton Method for Overparameterized Non-convex Matrix Sensing

We greatly appreciate the reviewer for your positive evaluation of our work, and we also thank you for your valuable and constructive suggestions. As for your concerns, we make detailed responses as follows.

1. Question: The computational cost of AGN over GD.
Answer: In general, the computational cost of the Gauss-Newton method is higher than that of GD. However, in our low-rank matrix recovery problem, the proposed AGN benefits from the low-rank structure, making the computational cost of solving equation (8) not much higher than that of GD, given that the dimension $d$ is much smaller than $n$. Specifically, equations (33) and (34) indicate that the main computational overhead of AGN compared to GD is the inversion of a matrix of size $d \times d$, which is manageable for small $d$.

2. Question: About the RIP constant and the advantage of AGN over GD under special initialization.
Answer: We aim to show that the proposed AGN method can effectively avoid saddle points with linear convergence of the function value. As a result, we may not need to improve the RIP constant, though this could be a valuable direction for our future research. With this small RIP constant, even with good initialization, GD converges sub-linearly for the over-parameterized low-rank matrix sensing model, as noted by [15]. Additionally, the convergence of GD highly depends on the condition number of the target matrix, as indicated by [26]. In contrast, AGN guarantees linear convergence that is independent of the condition number of the target matrix.

3. Question: The convergence in terms of the function value vs. the variables X.
Answer: Our primary objective is to demonstrate that the AGN method avoids getting trapped in saddle points where the function value is high, but the gradient norm is low. We aim to illustrate the decrease in function value (as adopted by [15]), based on the premise that if an optimization method is hindered by saddle points, its function value will decrease very slowly near these points, as shown for GD in Fig. 1 of the main paper. The linear convergence at a constant rate of the AGN on function value clearly demonstrates that AGN does not get trapped in saddle points.

Moreover, with a small RIP constant, it is straightforward to derive the convergence of the variable $X$ based on the linear convergence of the function value and the following distance metric ${\rm{dist}}(X_t, X^*) = \min_Q \frac{1}{2}||U_tQ-U^*||_F^2 + \frac{1}{2}||V_tQ-V^*||_F^2$ with orthogonal matrix $Q$, where $X_t= \begin{bmatrix} U_t^{\top} & V_t^{\top} \end{bmatrix}^{\top}$, $X^* = \begin{bmatrix} U^{* \top} & V^{* \top} \end{bmatrix}^{\top}$ is the global optimal solution. We thank the reviewer for the helpful comment. We will include the convergence of ${\rm{dist}}(X_t, X^*)$ in our revision.

We would like to express our sincere gratitude for your valuable comments on our work. As for your concerns, we give detailed response below which we hope can help you fully understand our work. Please feel free to let us know if you have any further concerns. We will deeply appreciate that you can raise your score if you find our responses resolve your concerns.

1. Question: About the typos.
Answer: We apologize for the typo here and will thoroughly review the entire manuscript to eliminate any remaining errors.

2. Question: For the expression $\mathcal B(X,X)= \mathcal A(PXX^TQ)$.
Answer: We will restate the bilinear function as $\mathcal B(X,Y)= \mathcal A(PXY^TQ)$ to ensure clarity, such that $\mathcal B(\Delta, X) = \mathcal A(P\Delta X^TQ)$ is unambiguous.

3.Question: About the Jacobian and the first-order approximation of $\mathcal B(X,X) - b$.
Answer: It is straightforward to find that $J\Delta = \mathcal B(X, \Delta) + \mathcal B(\Delta,X)= \mathcal A(P\Delta X^TQ) + \mathcal A(PX\Delta^TQ)$. Note that $\phi(X+\Delta) = \mathcal A(P(X+\Delta)(X+\Delta)^TQ) = \mathcal A(PXX^TQ) + \mathcal A(P\Delta X^TQ) + \mathcal A(PX\Delta^TQ) + \mathcal O(\Delta^2)$. Therefore the first-order Taylor expansion is $\mathcal A(PXX^TQ) + \mathcal A(P\Delta X^TQ) + \mathcal A(PX\Delta^TQ)$.

We deeply appreciate the reviewer for your careful review, constructive suggestions and positive feedbacks. The followings are our responses to your concerns. We will greatly appreciate that you can raise your score if you find our responses resolve your concerns.

1. Question: About the experiments.
Answer: Thank you for the reviewer’s suggestion. We have added comparisons of the iteration complexity of the proposed AGN with GD, PrecGD, and ScaledGD ($\lambda$), as in the following table

where $\kappa$ is the conditional number of the target matrix, $n$ is the matrix dimension. These results are also presented in Table 1 (in the rebuttal PDF file). Additionally, we provide comparisons of the computational time of these competing methods across different dimensions in Table 2 (in the rebuttal PDF file). Both theoretical and experimental results demonstrate the superiority of the proposed AGN over the competing methods. We will include details of the experimental settings and the above comparisons in the revision.

2. Question: About the superlinear convergence.
Answer: The superlinear convergence is indicated by $c_q=0$ in Theorem 2, which is presented at the end of the Theorem 2. We will make it more clearer in the revision.