How Over-Parameterization Slows Down Gradient Descent in Matrix Sensing: The Curses of Symmetry and Initialization

1. All results only assume RIP for A_i. If A_i are i.i.d. Gaussian matrices, is it possible to derive sharper or even asymptotically exact results?

Since we only use one derived property of RIP, (G.19) in Lemma G.2, the sample complexity might be improved if we use particular properties of Gaussian matrices to prove (G.19). It might be possible to further derive a sharper or even asympototically exact results, but it requires a different set of techniques rather than standard RIP technique in matrix sensing.

2. Could the authors comment on how crucially the results rely on the "linearity" of the problem? Does it make sense to consider a "generalized" matrix sensing problem in which $y_i = \phi(<A_i, M^*>)$ for some non-linearity $\phi$?

This is a good question. In this paper, our analysis heavily relies on the linearity of the problem: We utilize a key property that the imbalanced term $F_t^TF_t-G_t^TG_t$ keeps large during the convergence of the gradient descent. This property is derived by the updating rule that the change is $O(\eta^2)$. However, when the problem is nonlinear, this property does not hold and it seems hard to apply a similar technique. We leave it as a future work.

3. In Sec 5, an accelerated method is proposed. In particular, step (5.1) should be executed once the iterates are sufficiently close to the optimum. But in practice, how can one verify this neighborhood condition? Note that Sigma is unknown.

In practice, since we can get an estimate of the loss $F_tG_t^T-\Sigma$ by calculating $\mathcal{A}^*(y) = \mathcal{A}(F_tG_t^T-\Sigma)$, we can set a threshold and apply the modification step when the loss first becomes less than the threshold. We can also apply the modification at the half of the process like the experiment in our paper.

4. It seems that both the model and the algorithms are deterministic. What happens if the observations are noisy?

Since our paper mainly focuses on the exact global convergence result, we do not consider the noisy setting. The noisy setting induces an additional error term in the gradient. We believe that when the variance of the noise is small, our result can be extended to the noisy setting, and the gradient descent finally converges to a statistical error dependent on the noise.

5. It's claimed on top of page 6 that the results easily extend to the rectangular case. Could the authors state such results formally (even without formal proofs)? I'm curious to see how the results depend on the aspect ratio n_2 / n_1.

Assume that $F \in \mathbb{R}^{n_1\times k}$ and $G \in \mathbb{R}^{n_2\times k}$. Since we do not use the property that $F$ and $G$ are square matrices, we can replace $n$ by $\max\{n_1,n_2\}$ among all the proof and main theorem of Theorem 4.2, 4.3 and 5.1.

6. Lemma G.1 assumes x, y are "random vectors". Are they actually independent and uniform over the sphere? For generic joint distribution, not much can be said about their angle. Please make the statement more precise.

Thanks for catching it. Indeed, we assume every element of the random vector $x,y$ is independent and Gaussian. We have updated our paper accordingly.

7. typos

Thanks for pointing out the typos. We have fixed them in our revised version.

References:

[1]. Tian Ye, Simon S. Du. Global convergence of gradient descent for asymmetric low-rank matrix factorization. NeurIPS 2021.

[2]. Jiang et al. Algorithmic Regularization in Model-free Overparametrized Asymmetric Matrix Factorization. SIAM 2023.

[3]. Soltanolkotabi et al. Implicit Balancing and Regularization: Generalization and Convergence Guarantees for Overparameterized Asymmetric Matrix Sensing. COLT 2023.

[4]. Zhuo et al. On the computational and statistical complexity of over-parameterized matrix sensing. preprint 2021.

Thanks for the detailed response! Please find our response to your questions below.

1. Theorem 1.1: it would be better to say that each entry of X is independently initialized with Gaussian random variable with variance \alpha^2. A similar comment applies to other theorems.

Thanks for your reminder. We have updated our paper accordingly.

2. In Section 1, I think the authors did not mention any requirements on the sample size m. It might be better to briefly mention the requirement on the sample complexity or the RIP constant in Section 1.

Below the Definition 2.1, we state that $m = \widetilde{\Omega}(nk/\delta^2)$, where $\delta$ is the RIP error parameter. Combining with the constraint of $\delta$ in Equation 4.8, we can get $m = \widetilde{\Omega}(nk^2r)$ is needed, where we ignore the polynomial terms of $\kappa$. We have added this argument in Sections 1 and 2.

3. For the asymmetric case, I think most convergence results require a regularization term $\|F^TF - G^TG\|_F^2$ to penalize the imbalance between F and G. It would be better to mention the intuition why the regularization term is not required in this work.

Recently, the paper [1] provides the global convergence result for the gradient descent without the regularized term. They mainly focus on the exact-parameterized case, while the over-parameterized case remains open. Some other recent works [2], [3] also provide the convergence guarantee of the gradient descent without the regularization term. However, their convergence is not exact, meaning they only deal with a finite number of iterations.

The intuition why the regularization term is not required is because the change of the $||F^TF-G^TG||\_F^2$ is actually $O(\eta^2)$, i.e. $||(F_{t+1}^TF_{t+1} - G_{t+1}^TG_{t+1})-(F_t^TF_t-G_t^TG_t)|| = O(\eta^2)$. Thus when $\eta$ is small, we can prove that $F_t^TF_t-G_t^TG_t$ will not diverge. Hence, the two matrices $F$ and $G$ will not diverge and be too imbalanced.

4. mention the two current state-of-the-art results on landscape analysis

Thanks for pointing out these works. We have mentioned them in the related work section of our revised version. These two works provide an analysis of the global geometry of general low-rank minimization problems via the Burer-Monterio factorization approach for the exact-parameterized case ($k=r$). The paper [1] obtains less conservative conditions for guaranteeing the non-existence of spurious second-order critical points and the strict saddle property, for both symmetric and asymmetric low-rank minimization problems. The paper [2] analyzes the gradient descent for the symmetric case and asymmetric case with a regularized loss. They provide the local convergence result using PL inequality, and show the global convergence for the perturbed gradient descent. Compared to them, our paper tends to focus on the over-parameterized case and the vanilla gradient descent.

5. Theorem 3.1: it seems that the "ultimate error" does not appear in Section 3.1.

In the previous paper for the symmetric case [4], they prove that the gradient descent will linearly converge to a small error that is dependent on the initialization scale. We want to state that the "ultimate error" refers to this small error. Indeed, note that our lower bound in Equation (3.2) also has a $\alpha^4$. So it is also consistent with the phenomenon that the gradient descent first quickly converges to a small error (which we call "ultimate error") that depends on the initialization scale, with a linear convergence rate. Theorem 3.1 characterizes the behavior of the gradient descent after this quick convergence: The convergence speed becomes $\Omega(1/T^2)$ after the GD converges to a small error linearly.

6. Also, it might be better to mention that the over-parameterization size k depends on $\alpha$ and briefly explain what happens if the size k is smaller than this threshold.

The over-parameterization size $k$ is subject to a lower bound requirement in (3.1) that depends on $\alpha$. However, since $\alpha$ appears in the logarithmic term, this requirement is not overly restrictive. We posit that (3.1) may be a result of a proof artifact, and the lower bound of $\Omega(1/T^2)$ still holds even when $k$ is smaller than this threshold.

7. Below Theorem 3.1: For the inequality $\|X_tX_t^T - \Sigma\|_F^2 \geq A_t / n$, I wonder if it can be improved to $\|X_tX_t^T - \Sigma\|_F^2 \geq A_t$?

We find that the result can be improved. We also need to mention that there is a typo in this paragraph: Equation (3.3) implies $A_t = O(\alpha^2/t)$. Then since $(X_tX_t^T-\Sigma)\_{ii} = \|x_i\|^2$, we can have $||X_tX_t^T-\Sigma||\_F^2 \ge \sum_{i>r}(X_tX_t^T-\Sigma)\_{ii}^2 = \sum_{i>r}\|x_i\|^4\ge A_t^2/n,$ where the last inequality uses the Cauchy's inequality. Thus the $n^{-2}$ in the final result (Equation (3.2)) can be improved to $n^{-1}$. However, We do not find a way to directly prove $\|X_tX_t^T-\Sigma\|_F^2 \ge A_t^2$.

8. I wonder if there is a reason that initialization scales are chosen as \alpha and \alpha/3? Would it be possible to use, for example, \alpha and \alpha / 10 to achieve a better convergence rate?

The selection of the more imbalanced initialization $\alpha$ and $\alpha/10$ can make two matrices more imbalanced, thus leading to a faster convergence rate after the gradient descent converges to a local point (Section D.4, D.5 and D.6). However, this might result in a slower convergence rate and impose more stringent requirements on the parameters (up to a constant) at the beginning of the proof, as outlined in Theorem 1 in [3], a pivotal component employed in Section D.3 as the foundation of the proof. To be more specific, a more imbalanced initialization may lead to a looser constant in Lemma B.7 and condition (23) in [3].

We also want to highlight that a more imbalanced initialization also gives a guarantee $\|\Delta_0\| = O(\alpha^2)$ where $\Delta_0 = F_0^TF_0 - G_0^TG_0$. Thus all the changes are only up to a constant.

9. typos

Thanks for your reminder. We have fixed them in our revised version.

References:

[1]. Tian Ye, Simon S. Du. Global convergence of gradient descent for asymmetric low-rank matrix factorization. NeurIPS 2021.

[2]. Jiang et al. Algorithmic Regularization in Model-free Overparametrized Asymmetric Matrix Factorization. SIAM 2023.

[3]. Soltanolkotabi et al. Implicit Balancing and Regularization: Generalization and Convergence Guarantees for Overparameterized Asymmetric Matrix Sensing. COLT 2023.

[4]. Stoger and Soltanolkotabi. Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstruction. NeurIPS 2021.

Thanks for the positive review! We have added more experiments according to your suggestions. Please find our response to your questions below.

1. In Fig 2 we see that for larger $\alpha$ the convergence rate is faster. What is the limit of how large $\alpha$ can be?

In practice, a large initialization may not be able to converge at the initialization phase. We run an experiment to show that a large $\alpha$ fails to converge to a local point. The experiment result is in Appendix I.3

On the theoretical side, the initialization scale $\alpha$ has a constraint in Equation (4.7). A large $\alpha$ does not satisfy the constraint.

2. Do the numerical results hold also for larger ranks of the true matrix and over-parameterized ranks? Also larger imbalance of ranks, lets say k = 20 and r = 5?

Since we need a relatively small $k$ in Theorem 4.2 $(k<n/8)$, we only run an experiment using $k=10$ and $r=5$. The number of samples is $m=2000$. The experiment results are in Appendix I.4, which shows that a similar phenomenon also holds for a larger rank of the true matrix and a larger over-parameterized rank.

Thank you for your review and for thinking our paper is good. We have updated our paper, including more experiments according to your suggestions. Please also find our response to your comments below.

1. In the symmetric case, if we use GD with small initialization, then it is often the case that GD goes through an initialization phase where the loss is relatively flat, and then converges rapidly to a small error. However, in the experiments in Figure 2, I do not see this initialization phase in Figure 2b. Instead, linear convergence is observed right from the start, even when a small initialization is used. I wonder why is this the case? For the asymmetric case, is the initialization phase much faster?

In Figure 2b, our purpose is to show the exact linear convergence. Hence, we run the algorithm with a large number of iterations, 70000 iterations. Thus, the initialization phase is not clear in Figure 2b. After zooming into the first 5000 iterations of Figure 2b, we find the existence of the initialization phase. That is, the loss is rather flat during this phase. We can also see that the initialization phase is longer when $\alpha$ is smaller. The experiment results are shown in Appendix I.5.

2. Additional experiments that I think should be nice: on the same plot, compare the convergence of asymmetric versus symmetric parameterization, using the same initialization. Also, perform the experiment for different initialization scales.

We add the detailed comparison in Appendix I.1. The comparison shows that the asymmetric parameterization performs better than the symmetric parameterization.

3. I think the authors should also plot convergence for ill-conditioned versus well-conditioned matrices, as GD with small initialization performs differently based on the eigenvalues.

We plot the curve when $\kappa = 1.5, 3, 10$ with minimal eigenvalue $0.66, 0.33, 0.1$. The experiment results are in Appendix I.2. From the experiment results, we can see two phenomena:

• When the minimum eigenvalue is smaller, the gradient descent will converge to a smaller error at a linear rate. We call this phase as the local convergence phase.
• After the local convergence phase, the curve first remains flat and then starts to converge at a linear rate again. We can see that the curve remains flat for a longer time when the matrix is ill-conditioned, i.e. $\kappa$ is larger.

This phenomenon has been theoretically identified by the previous work for incremental learning [1,2], in which GD is shown to sequentially recover singular components of the ground truth from the largest singular value to the smallest singular value.

4. In Theorem 1.3, the convergence rate depends on the initialization scale . This is also observed empirically in figure 2b. In practice, does this mean that small initialization has no advantage? One could just set to be large to ensure rapid convergence?

In practice, a large initialization may not be able to converge at the initialization phase. We run an experiment to show that a large $\alpha$ fails to converge to a local point. The experiment result is in Appendix I.3

On the theoretical side, the initialization scale $\alpha$ has a constraint in Equation (4.7). A large $\alpha$ does not satisfy the constraint.

References:

[1] Jin et al. Understanding incremental learning of gradient descent: A fine-grained analysis of matrix sensing. ICML 2023.

[2] Jiang et al. Algorithmic Regularization in Model-free Overparametrized Asymmetric Matrix Factorization. SIAM 2023.