How Over-Parameterization Slows Down Gradient Descent in Matrix Sensing: The Curses of Symmetry and Initialization
Authors: Nuoya Xiong
Lijun Ding
Simon Shaolei Du
Venue: ICLR 2024 spotlight (2024)
Keywords: non-convex optimization
random initialization
global convergence
matrix recovery
matrix sensing
Primary area: learning theory
TL;DR: This paper study the different convergence behaviors of symmetric and asymmetric matrix sensing in exact and over-parameterized settings, and show the first exact convergence result of asymmetric matrix sensing.

Abstract: This paper rigorously shows how over-parameterization dramatically changes the convergence behaviors of gradient descent (GD) for the matrix sensing problem, where the goal is to recover an unknown low-rank ground-truth matrix from near-isotropic linear measurements.
First, we consider the symmetric setting with the symmetric parameterization where $M^* \in \mathbb{R}^{n \times n}$ is a positive semi-definite unknown matrix of rank $r \ll n$, and one uses a symmetric parameterization $XX^\top$ to learn $M^*$. Here $X \in \mathbb{R}^{n \times k}$ with $k > r$ is the factor matrix. We give a novel $\Omega\left(1/T^2\right)$ lower bound of randomly initialized GD for the over-parameterized case ($k >r$) where $T$ is the number of iterations. This is in stark contrast to the exact-parameterization scenario ($k=r$) where the convergence rate is $\exp\left(-\Omega\left(T\right)\right)$. Next, we study asymmetric setting where $M^* \in \mathbb{R}^{n_1 \times n_2}$ is the unknown matrix of rank $r \ll \min\{n_1,n_2\}$, and one uses an asymmetric parameterization $FG^\top$ to learn $M^*$ where $F \in \mathbb{R}^{n_1 \times k}$ and $G \in \mathbb{R}^{n_2 \times k}$. We give the first global exact convergence result of randomly initialized GD for the exact-parameterization case ($k=r$) with an $\exp\left(-\Omega\left(T\right)\right)$ rate. Furthermore, we give the first global exact convergence result for the over-parameterization case ($k>r$) with an $\exp\left(-\Omega\left(\alpha^2 T\right)\right)$ rate where $\alpha$ is the initialization scale. This linear convergence result in the over-parameterization case is especially significant because one can apply the asymmetric parameterization to the symmetric setting to speed up from $\Omega\left(1/T^2\right)$ to linear convergence. Therefore, we identify a surprising phenomenon: asymmetric parameterization can exponentially speed up convergence. Equally surprising is our analysis that highlights the importance of imbalance between $F$ and $G$. This is in sharp contrast to prior works which emphasize balance.  We further give an example showing the dependency on $\alpha$ in the convergence rate is unavoidable in the worst case. On the other hand, we propose a novel method that only modifies one step of GD and obtains a convergence rate independent of $\alpha$, recovering the rate in the exact-parameterization case. We provide empirical studies to verify our theoretical findings.

Published as a conference paper at ICLR 2024
HOW OVER-PARAMETEERIZATOO SLOWS DOWN GRA- DIENT DESCENT IN MATRIX SENSING: THE CURSES OF S SYMMETRY AND INITIALIZATION
Nuoya Xiong nuoyaxiong@@maill
Lijun Ding Idinget amu edu
Simon S. Du
ssdu@cs www.wwwtts.hn...oooooo edu
ABSTRACT
This paper rigorously shows how reeeraaramtteiizttionn dramatically changes the convergence behaviors of gradient descent (GD) for the matrix sensing problem, where the goal is to recover unknown low-rank ground-truth matrix from near- isotropic linear measurements. First, we consider the symmetric setting with the symmetric parameterization where M E Rax= is positive semi-definite known matrix of rank r < n, and one uses a symmetric parameterization X learn M*. Here, X E Raxk with & > is the factor matrix. We give novel 2 (1/T2) lower bound of randomly initialized GD for the over-parameterized case (k > r) where T is the number of iterations. This is in stark contrast to the exact-paramettrizztioon scenario (A: = r) where the convergence rate is exp exp(-S (2)). Next, we study asymmetric setting where M Rm.x*= is the un- known matrix of rank & min(n1, m2). and one uses an asymmetric parameter- ization FG to learn M where F Ra x and G "2 Building on prior work, we give global exact convergence result of randomly initialized GD for the exact-parameterization case (k- = r) with an exp (-52 (T)) rate. Furthermore, we give the first global exact convergence result for the parameterrizziionn case (k > r) with an exp (-St (a²T)) rate where a the initialization scale. This linear convergence result in the over parameterizaaionn case is especially signif- icant because one can apply the asymmetric parameterization to the symmetric setting to speed up from f (1/T²) to linear convergence. Therefore, we identify a surprising phenomenon: asymmetric parameterization can exponentially speed up convergence. Equally surprising is our analysis that highlights the importance of imbalance between F and G. This is in sharp contrast to prior works which emphasize balance. We further give an example showing the dependency on the convergence rate is unavoidable in the worst case. On the other hand, we pro- pose novel method that only modifies one step of GD and obtains convergence rate independent of a, recovering the rate in the sractpaarameterization case. We provide empirical studies to verify our theoretical findings.
INTRODUCTION
A line of recent work showed over-paramettriizaionn plays a key role in optimization, especially for neural networks (Allen-Zhu et al., 2019; Du al., 2018b; Jacot et al., 2018; Safran & Shamir, 2018; Chizat et al., 2019; Wei et al., 2019; Nguyen & Pham, 2020; Fang et al., 2021; Lu et al., 2020; Zou al., 2020). However, our understanding of the impact of over-parameterization on optimization is far from complete. In this paper, we focus on the canonical matrix sensing problem and show that over-parameterrizatoo qualitatively changes the convergence behaviors of gradient descent (GD).
Matrix sensing aims to recover a low-rank unknown matrix M from m linear measurements,
V/ A:M')) (A,, M*) tr(A, M*), for i 1,..,,,,
(1.1)
"IIS, Tsinghua University. Part of the work was done while Nuoya Xiong was visiting the University of Washington
Wm Michael Barnes '64 Department of Industrial & Systems Engineering, Texas A&M University. Paul G. Allen School of Computer Seience and Engineering, University of Washington

---

Published as a conference paper at ICLR 2024
Los5
n0 km1.
n-50, k-5, n~2
log
Loss
5= k=3, r22
n=
Symmetric, k=50,K-3
n0 k=2, rm2
Asymmetric, n=50,
5.
700
Wes shaa
1965
Wene trio win
100
2003
Se 200 uik Roe aive
Iterations
Iterations
Iterations
(a) Loss curve
(b) Logloss: logr ||X.X, -X.XT-1 -M (c) Comparison between symmetric and asymmetric parameterization
Figure 1.1: Experiments symmetric setting. The first two figures show that the convergence rate of symmetric matrix factorization in the over-parameterized setting is about (11/T²), while the rate of the pract-paraetterized setting is linear. 1(c) shows that using asymmetric parameterization is exponentially faster than symmetric parameterization. See ŠH for experimental details.
where A, is a linear measurement operator and A; is the measurement matrix of the same size as M This is elassical problem with numerous real-world applications, including signal processing (Weng & Wang, 2012) and face recognition (Chen et al., 2012), image reconstruction (Zhao et al., 2010: Peng et al., 2014). Moreover, this problem can serve
test-bed of convergence behaviors in deep learning theory since it is non-convex and retains many key phenomena (Soltanolkotabi et al., 2023; Jin et al., 2023; Li al., 2018; 2020; Arora et al., 2019). We primarily focus on the over- parameterized case where we use model with rank larger than that of M* in the learning process. This case particularly relevant because (an is usually unknown in practice.
1.1 SETTING 1: SYMMETRIC MATRIX SENSING WITH SYMMETRIC PARAMETERIZATION
We first consider the symmetric matrix sensing setting, where M E R is a positive semi- definite matrix of rank < n. standard approach to use a factored form X to learn M where X E Raxk We call this symmelric parameterization because XXT is always symmetric and positive semi-definite. the case when &- the parantttrttttonnnooonnnnnn because the rank of X.X matches that of M However, in practice, r is often unknown, so one may choose some large enough > r to ensure the expressiveness of XXT, and call this case over-parameterization.
will also introduce the asymmetric parameterization soon. We call
We consider using gradient descent to minimize the standard L2 loss for training: Le(XX) = 2= (y:- (A,, XXT)) We the Frobneius norm of the reconstruction as the per-
m
formance metric:
1 1XXXX -M
L(X)= =
(1.2)
We note that T(X) is also the matrix factorizution loss and can be viewed special case of Tar when (A, pm are random Gaussian matrices and the number of linear measurements go infinity.
For the exact-parameterizztin case, one can combine the results by Stöger & Soltanolkotabi (2021) and Tu et al. (2016) to show that randomly initialized gradient descent enjoys an exp (-D(T)) convergence rate where T' is the number of iterations. For the parametrrizaaionnn case, one can combine the results by Stöger Soltanolkotabi (2021) and Zhuo et al. (2021) to show an O (1/T²) convergence rate upper bound, which is exponentially worse. This behavior has been empirically observed (Zhang et al., 2021b; 2023; Zhuo al., 2021) without a rigorous proof. See Figure
Contribution 1: Q(1/T²) Lower Bound for Symmetric Over- Over-Parameterizaaion.. Our first contribution a rigorous exponential separation between the exact- parrattttaattiinaiooonnn and over- parameterization by proving 1(1/T²) convergence rate lower bound for the symmetric setting with the symmetric over-parameterizzaion..
Theorem 1.1 (Informal). Suppose initialize X with Gaussian distribution with small enough variance that scales with a?, and use gradient descent with a small enough constant step size to optimize the matrix factorization loss (1.2). Let X, denote the factor matrix the t-th iteration.
2

---

Published as a conference paper at ICLR 2024
Then with high probability over the initialization, there exists T(,) > 0 such that we have'
a²
| M Z
v2 T()))
(1.3)
Technical Insight: We find the root cause of the slow convergence is from the redundant space in XXX", which converges to 0 at much slower rate compared to the signal space which converges to M with a linear rate. To derive the lower bound, we construct a potential function and use some novel analyses of the updating rule to show that the potential function decreases slowly after few rounds. See the precise theorem and more technical discussions in Section 3.
1.2 SETTING 2: SYMMETRIC AND ASYMMETRIC MATRIX SENSING WITH ASYMMETRIC PARAMETERIZATION
Next, we consider the more general asymmetric matrix sensing problem where the ground-truth M 2m is asymmetric matrix of rank r. For this setting, we must use the asymmetric parameterization. Specifically, we use FG to learn M where / E [gn xk and G E R Same as in the symmetric case, exact- exact-paramme paramettrreeiinooonnnn means h r and over peer-arameterization means k > r. We still use gradient descent to optimize the L2 loss for training:
Lar (F,))
(A,, FGT))"
(1.4)
2m
and the performance metric is still: L(F, FI M To enable the analysis, we assume throughout the paper that the matrices {A, [ satisfies the Restricted Isometry Property (RIP) of order 2Λ: + 1 with parameter 8 < O (See Definition 2.1 for the detailed definition).
Also note that even for the symmetric matrix sensing problem where M* is positive semi semi-definite, one can still use asymmetric parameterization. Although doing so seems unnecessary at the first glance, we will soon see using asymmetric parameterization enjoys an exponential gain.
Contribution 2: Global Exact Convergence of Gradient Descent for Asymmetric Exact- Parameterization with Linear Convergence Rate. Our second major contribution is global exact convergence result for randomly initilized gradient descent, and we show it enjoys a linear convergence rate.
Theorem 1.2 (Informal). the exact-parameterization setting (k = r), suppose we initialize F and G using a Gaussian distribution with small enough variance a² and use gradient descent with small enough constant step size to optimize the asymmetric matrix sensing loss (1.4). Let Fe and G, denote the factor matrices at the t-the iteration. Then with high probability over the random initialization, there exists T() such that we have
|.F.G. - M = exp (-Q(t)) 222 T(1)
(1.5)
Compared to our results, prior results either require initialization to be close to optimal (Ma et al.. 2021), or can only guarantee to find a point with an error similar scale as the initializa- tion (Soltanolkotabi et al., 2023). In contrast, our result only relies random initialization and guarantees the error goes to 0 as goes to infinity. Notably, this convergence rate is independent of a. See Figure 2(a). Naturally, such result is expected and can be derived (with considerable effort) by the works (Ma et al., 2021, Theorem 1) and (Soltanolkotabi et al., 2023). Our proof strategy is very different from (Ma et al., 2021) as further decompose the factors F and G, and we only need (Soltanolkotabi et al., 2023, Theroem 3.3) to deal with the initial phase.
Contribution 3: Global Exact Convergence of Gradient Descent for Asymetric Over- Parameterization with an iiitaaizatiin-Dependde Linear Convergence Rate. Our next con- tribution analogue theorem for the parametrriiiiinonnnn case with caveat that the initialization scale a also appears in the convergence rate.
'Frr clarity, in our informal theorems Section 1, we only display dependency on a and T, and ignore parameters such as dimension, condition number, and step size.
27(0) here and (1)) T(2) T3() in theorems helow represent the burn-in time get to neighhorhood of an optimum, which can depend on initilization seale a, condition number, dimension, and step size.
'By exact convergence we mean the error goes to O as goes to infinity in contrast to prior works which
only gurantce converge a point with the error proportional the initialization scale
3

---

Published as a conference paper at ICLR 2024
alpaa 0.2
0.05
LO5S
GD. ko4, Our Mathod, k-4,
alpha 0.55
ko
0.
alpha 0.05
Our Method, k-3.
200
Sal wile til Wine trlo wilw
2000 calo mio
160
wis valo 1960 noe vii 2900
Iterations
Iterations
Iterations
(a) sraattparameterizeed case
ever-parameterized case
(c) Loss curve for our new method
Figure 1.2: Curve of asymmetric matrix sensing. Figure 2(a) shows that the convergence rate is linear and independent on the initialization scale under the exact-parameterized case. Figure 2(b) shows that the convergence rate is linear and dependent on the initialization scale under the over- parameterized case. When the initialization scale larger, the convergence speed is faster. Figure 2(c) shows the efficacy of our new method. See ŞH for experimental details.
Theorem 1.3 (Informal). In the vverpaarameterizationn setting (k > r), suppose initialize F and G using a Gaussian distribution with small enough variance a² and use gradient descent with a small enough constant step size optimize the asymmetric matrix sensing loss (1.4). Let F; and Gt denote the factor matrices at the t-th iteration. Then with high probability over the random initialization there exists T12) >> 0 such that we have
|F..G - M exp (-2(aa))) V1 2(2)
(1.6)
This is also the first global exact convergence result of randomly initialized gradient descent in the wverpparameterized case. Recall that for the symmetric matrix sensing problem, even if M is positive semi-definite, one can still use an asymmetric parameterization FG to learn M and Theorem 1.3 still holds. Comparing Theorem 1.3 and Theorem 1.1, we obtain a surprising corollary:
For the symmetric matrix sensing problem, using asymmetric parameterization exponentially faster than using symmetric parameterization.
Also notice that different from Theorem 1.2, the convergence rate of Theorem 1.3 also depends on the initialization scale which we require to be small. Empirically verify this dependency is necessary. See Figure 2(b). We also study a special case in Section 4.1 to show the dependency on the initialization scale is necessary in the worst case.
Technical Insight: Our key technical finding that gives the exponential acceleration is the imbalance of F and G. Denote the imbalance matrix A, = F. F. G, G,. We show that the converge rate is linear when A, is positive definite, and the rate depends on the minimum eigenvalue of A, We use imbalance initialization so that the minimum eigenvalue of Ao is proportional to a, show that the minimum eigenvalue A, will not decrease too much, so the final convergence rate is linear. Furthermore, such connection also inspires to design a faster algorithm below.
further
Contribution 4: A Simple Algorithm with Initialization- Inttialization-nndeeeeeeen Linear Convergence Rate for Asymetric Over-Parameetrization. Our key idea is to increase the degree of imbal- ance when F and G are close to the optimum. We develop a new simple algorithm to accelerate GD. The algorithm only involves transforming the factor matrices F and G one of iteration to intensify the degree of imbalance (cf. Equation (5.1)).
Theorem 1.4 (Informal). In the over-purameterization setting (k r). suppose we initialize F and G using a Gaussian distribution with small enough variance a?, gradient descent with small enough constant step size, and the procedure described in Section 5 optimize the loss (1.4). Let Fe and G, denote the factor matrices at the t-the iteration. Then with high probability over the random initialization, there exists (3) > such that we have
|...GT - 11 cxp (-2(6 ((-T(()) VV
(1.7)
1.3 RELATED WORK
Matrix sensing is a canonical problem and has been widely studied via the nuclear norm minimiza- tion approach (Candes & Recht, 2012; Liu et al., 2012; Recht et al., 2010; Wu & Rebeschini, 2021),
4

---

Published as a conference paper at ICLR 2024
Table 1: Comparison of previous representative work. The second column shows that the sults hold for symmetric matrix factorization/sensing or asymmetric matrix factorization/sensing: The third column lists different types of initialization, where "Random" means the algorithm uses random initialization (typically Gaussian), "Local" indicates requirement for initialization to be close to the optimal point. The fourth column "exact-envrg" represents whether the loss will go to zero when round T' goes to infinity. The fifth column indicates whether the result applies to over- parameterization case or just the paramtttaraatttizzaiionn case. The last row lists the convergence rate of algorithms with exact-convergence results.
Is Symmetric
Init.
exact-cnvrg
k Range
Rate
Stöger Soltanolkotabi (2021)
Symmetric Symmetric
Random
K
2
N/A
Zhuo et al. (2021)
Local
k
O1//T")
Stöger & Soltanolkotabi (2021)
Symmetrie
Random
/
2
0(1/T")
Zhuo et al. (2021)
Soltanolkotabi et al. (2023)
Asymmetric
Random
x
k
N/A
(2016)
Both
Local
/
exp(-I3(T)
Ma et al. (2021)
Asymmetrie
Local
7
=
exp(-(2(T)
Thearem 4.3 (our paper)
Asymmetric
Random
V
k= r
exp(-s2(T))
Theorem 4.2 (our paper)
Asymmetrie
Random
7
k> r
exp( (T))
Theorem 3.1 (our paper)
Symmetrie
Random
2
(1(1/1²
spectral method (Ma et al., 2021; Tu et al., 2016) and landscape analysis (Ge et al., 2017; Zhu et al., 2018) The most relevant line of work considered global convergence of gradient descent (Zhuo et al., 2021; Stöger & Soltanolkotabi, 2021; Soltanolkotabi et al., 2023; Tu et al., 2016). We compare our results with the them in Table 1. The detailed discussions related work is deferred to Appendix A.
PRELIMINARIES
Norm and Big-O Notations, Given vector we use ||||| to denote its Euclidean norm. For a matrix M, we use || to denote its spectral norm and || Frobenius norm. The notations O()), ((), and ((-)) in the rest of the paper only omit absolute constants.
Asymmetric Matrix Sensing. Our primary goal is to recover an unknown fixed rank r matrix I,..., m satisfying Yi (A,, M*) tr(A, M*),
M E R2xx22 from data (yi, A,), = A(M*), where y E Ihe and A : 1 - Rh is a linear map tr(A, M). We further denote the singular values of M as σ dn. the condition number k = 3t, and the diagonal singular value matrix as L with (E); = d.. To recover M*, we minimize the following loss function:
1,..., m, or compactly
with [A(M)],
or >
gr+1 = 0 =
Lue (ue G) = I[((FFTT) -y1
(2.1)
where F, E Bunk where & 2 r is the user-specified rank. The gradient descent update rule with step size 17 0 with respect to loss (2.1) can be written explicitly
Fi11 F; A(F.G) E), G G. n(A' - -)) Ft,
(2.2)
where A :Rm - R is the adjoint map of A and admits an explicit form: A²(z) = Σm - Ai.
We make the following assumption on A: Restricted Isometry Property (RIP) (Recht et al., 2010).
Definition 2.1. /Restricted Isometry Property] An operator A Ro1xx2 - R. satisfies the Re- stricted Isometry Property of order r with constant 5 > O for all matrices M Ruixxn xnz with rank at most r, we have (1 - M < [[(MM)] < (1 + 6) M [|2..
From (Candes & Plan, 2011), 1), if the matrix A; has i.i.d. (0, 1/m), the operator A has RIP of order 2k + with constant 8 (0, 1) when m Ω (nk/5²). Thus, m ((nk?r) is needed with (4.8). Diagonal Matrix Simplification. Since both the RIP and the loss are invariant to orthogonal trans- formation, we assume without loss generality that M Σ in the rest of the paper for clarity,
5

---

Published as a conference paper at ICLR 2024
following prior work (Ye & Du 2021; Jiang al., 2022). For the same reason, also assume 71 = n2 = n to simplify notations, and our results can be easily extended to n1 + n22.
Symmetric Matrix Factorization. In this setting, further assume M * is symmetric and positive semidefinite, and A is the identity map. Since M admits a factorization M = F-F-" for some F. E R we can force the factor F G X in (2.1) and the loss becomes L(x) |X
El Here, the factor X Raxk We shall focus on the over par-paaameteiizationn setting, i.e., h in the Setion 3 below. The gradient descent with a step size >> 0 becomes
X1+1 = Xt - 2n(X, Xx.
(2.3)
LOWER BOUND OF SYMMETRIC MATRIX FACTORIZATION
We present sublinear lower bound of the convergence rate of the gradient descent (2.3) for sym- metric matrix factorization with small random initialization. Our result supports the empirical observations of the slowdown in Zhuo et al. (2021); Zhang et al. (2021b; 2023) and Figure 1.
Theorem 3.1. Let Xo = a Xo, where each entry of Xo is independent initialized from Gaussian distribution
For some universal constants c,, 1 S i is 7, if the gradient descent method (2.3) starting at Xo with the initial scale a. the search rank k, and the stepsize yj satisfying that
0<as
CIV
k 02 ((r))² log(r log(rvoi/a))) and 0 17 S
C3
(3.1)
Vologr//)
n2ROT
then with probability at least 1 - 2n - Vcak) 2mexp(-csk/A) for all t 2 T()) /og/r// we have
C7 logl (oog(/ro///aa 2 At 2 T())
XX.XT- - E 2
(3.2)
80,.1yn
The proof of Theorem 1.1 demonstrates that, following rapid convergence phase, the gradient descent eventually transitions a sublinear convergence rate. Also, the over-parameeerrizaion rank k is subject to lower bound requirement in Eq. (3.1) that depends appears in the logarithmic term, this requirement is not overly restrictive. It is also consistent with with
However, since only
the phenomenon that the gradient descent first converges small error that depends linear convergence rate (Stöger & Soltanolkotabi, 2021), since our lower bound has a term a
3.1 PROOF SKETCH OF THEOREM 3.1
We provide a proof sketch of Theorem 3.1 in this section, deferring the details to Appendix B. The main intuition of Theorem 3.1 is that the last n - r rows of X,, corresponding to the space of 0 eigenvalues of Σ, converge
at speed no faster than 1 To make this intuition precise, for each where of E R We let the potential function be We aim to show the following two key inequalities.
t 2 0, we let X, E R = [aq, ... "eij......e .x*]
A, Σ Sir |
| 0 12 2 a²/8, for all i>>
(3.3a)
A 2 11 (nA)))) for all f (0))
(3.3b)
Suppose (3.3) is true, then it implies that A, 2 O (+) for all t T(O), Since (X,X7
E)
| the lower bound (3.2) is established by noting that |X,,X,T Σ1 2 D || 2
2 A//n,
where the last inequality uses the Cauchy's inequality. See more details in Appendix B.
4 CONVERGENCE OF ASYMMETRIC MATRIX SENSING
Here we investigate the dynamic of GD in the context of the asymmetric matrix sensing problem. Surprisingly, we demonstrate that the convergence rate of gradient descent for asymmetric matrix sensing problems is linear, so long as the initialization is imbalanced. However, this linear rate is contingent upon the chosen initialization scale.

---

Published as a conference paper at ICLR 2024
4.1 A TOY EXAMPLE OF ASYMMETRIC MATRIX FACTORIZATION
We first use a toy example of asymmetric matrix factorization to demonstrate the behavior of GD. If assume A is the identity map, and the loss and the GD update become
L) = - - - -)G -+-1= = GG- - Σ) T
(4.1)
Fi+1 = - F
(4.2)
The following theorem tightly characterizes the convergence rate for a toy example.
Theorem 4.1. Consider the asymmetric matrix factorization (4.1). with = + 1. Choose 17 E [0, 1/6] and E [0, 1J. Assume that the diagonal matrix Σ diag(o)....,, .n), where d; 1 for i i and is O otherwise. Also assume that gradient descent (4.2) starts at Fo: Go. where (Fo)at = a for 1 S i S k, and (Go) a for 1 < S T, (Go) / for i
1, and all other entries of Fo and Go are zero. Then, the iterate (F,, Gt) of (4.2) satisfies that
a (1 4n $ I|F.G. - Σ1 W 4n - -1- 14) TT), Vt V22T.
36
where Ti = c1 log lgg(1/a)/1/ and 01 is a universal constant.
The above initialization implicitly assumes that we know the singular vectors of E. Such an assump- tion greatly simplifies our presentations below. Note that we have a different initialization scale for Ft and G.. As we shall see, such an imbulance is the key to establishing the convergence of F,G,
We introduce some notations before our proof. Denote the matrix of the first row of F, G as U, V grxk respectively, and the matrix of the last n - r row of F, G as J, K E (B(n-r)xk respectively. Further denote the corresponding iterate of gradient descent as Ut, Ve, Jr. and K₁. The
difference F,G.T Σ can be written in a block form as F.G.T - VUV. Er J
where
U.K
J.K
E, E R xr is the identity matrix. Hence, we may bound ||F.CT Σll by |J S ||F.C. - Σ| < |U,V - E,ll + | || + ,
T || + II
(4.3)
From (4.3), we shall upper bound |,,, - E1 V II. |U,K, []. and || K, ||. and lower bound
|J T. Let us now prove Theorem 4.1.
Proof. With our particular initialization (4.2), we have the following equality for all t:
U.K.T = 0, JVV, = 0, Ue = V/, J a,A,
K, = =b,,, U1 = (a,4r, 0),
(4.4a)
an a, bn a/3,
on = a a++1 = at na,b?
(4.4b)
(4.4c)
6,+1 = b, n
(4.4d)
0441 = 0x + - 70?))
(4.4e)
where A E (n-r) is the matrix that (A) = 1 and other elements are all zero, and a, b, a E IR We leave the detailed verification of (4.4) Appendix C. By considering (4.3) and (4.4), we see that we only need to keep track of three sequences az bt, 0g. In particular, we have the following inequalities for az, be, Or for all / 2 Ti:
a _
17
at 2 22 b E
4nj 5
1/2 and Ja. 1| S (1- ( (4.5)
is then easy to derive the upper and lower bounds. We leave the detail in checking (4.5) to Appendix C. Our proof is complete.
Technical Insight. This proof of the toy case tells us why the imbalance initialization in the asym- metric matrix factorization helps us to break the (11/T2) convergence rate lower bound of the symmetric case. Since we initialize Fo and Go with different scale, this difference makes the norm K converge to zero at a linear rate while keeping J larger than a constant. However, in the symmetric case, we have a, by, so they must both converge to zero when the loss goes to zero (as |[F,GT - Σ 2 a,b,), leading to a sublinear convergence rate. In short, the imbalance property in the initialization causes faster convergence in the asymmetric case.
7

---

Published as a conference paper at ICLR 2024
4.2 THEORETICAL RESULTS FOR ASYMMETRIC MATRIX SENSING
Motivated by the toy case in Section 4.1, the imbalance property is the key ingredient for a linear convergence rate. If we use a slightly imbalanced initialization Fo = a Fo, Go = (a/3) Go- where the elements of Fu and Go are (0, 1/n), we have [ Fo Gy Goll = 22(a²) ). Then, we can show that the imbalance property keeps true when the step size small, and thus, the gradient descent (2.2) converges with a linear rate similar to the toy case.
Our result is built upon the recent work (Soltanolkotabi et al., 2023) in dealing with the initial phase. Define the following quantities co. 1/u according to (Soltanolkotabi et al., 2023, Theorem 1):
CR
VT n22 122/maxy ///maa(22))) (2n, k3}
00 = 1 max 2n, k)
(4.6)
1 log
2y/mm
Belvk-vr-
where and C' are some numerical constants. Below, show exact convergence results for both k r and 1: > r.
Theorem 4.2. Consider the matrix sensing problem (1.4) and the gradient descent (2.2). For some numerical constants c; > 0, 1 15 if the search rank k satisfies r < k n. the initial scale and 1j satisfy
a S min Vor
n I min (1aa /0. mo
(4.7)
where oo. tlo are defined in (4.6), and the operator A has the RIP of order 2k + with constant satisfying
8V2k + 1 S min { cIR llg 1ao=="log'VVo///000 (Vorr/na)), "3
1/128 1/128)
(4.8)
then the gradient descent (2.2) starting with Fo a Fo, Go (a/3) Go. where Fo, Go e g
whose entries are i..dd. NO, 1/m). satisfies that
o
na² 1
1/4
[.G - E1 <
V1 2 T(1).
(4.9)
C7a4k²2
8
with probability at least 2c c2n
C3e cak
where T())
ep log( /orl////))))/)) /no,) and v E [0, 1] is arbitrary parameter.
Next, we state our results exact parametrization.
Theorem 4.3, Consider the same setting as Theorem 4.2 except assuming k = r, then with proba- bility at least 1 -en cane eze eak CSU, the gradient descent (2.2) achieves
(1- n0? 640
[.G.G. ElIE- < 2no,
Vt V2 (2))
(4.10)
where (2) = 07 (og(//r/noox)) ///,)/)))))))))>()) for some numerical constant 07.
Now we highlight two bullet points of Theorem 4.2 and 4.3.
Exact Convergence. The main difference between the above theorems and previous convergence results in (Soltanolkotabi et al., 2023) is that we prove the exact convergence property, i.e., the loss finally degenerates
when T tends infinity (cf. Table 1). Moreover, we prove that the convergence rate of the gradient descent depends on the initialization scale a, which matches our empirical observations in Figure 1.2.
Discussions about Parameters.
First, since we utilize the initial phase result in (Soltanolkotabi al., 2023) guarantee that the loss degenerates
small scale, our parameters a, and 1) should satisfy the requirement d = O ((()) ), ao, 77 in (Soltanolkotabi et al., 2023). We further require
526-11 Ō(,-)), a O(k Vo,), which are both polynomials of the conditional number к. In addition, the step size 17 has the requirement 7 O(a which can be much smaller than the requirements " O(1/k² in (Soltanolkotabi et al., 2023). In Section 5, propose novel algorithm that allows larger learning rate which is independent of a.
8

---

Published as a conference paper at ICLR 2024
Technical insight Similar to the asymmetric matrix factorization case in the proof of Theorem 4.1, the main effort is in characterizing the behavior of J,K," In particular, the update rule K₁ is
K1+1 K₂(1 F. Fi) nE,
(4.11)
where E is some matrix since AA is an identity. Because of our initialization, we know the following holds for = 0 and A, = Fr F. G. Gr.
ca 2 3 A. CC.1.
(4.12)
for some numerical constant c, C O. Hence, (4.11) true, E = 0, and G. is well-bounded. Indeed, we can prove (4.12) and Gr upper bounded for all 2 0 via a proper induction. We may then be tempted conclude J, K converges to O. However, the actual analysis of the gradient descent (2.2) for matrix sensing is much more complicated due to the error E. It is now unclear whether || will shrink under (4.12). To deal with it, we further consider the structure of E. We leave the details to Appendix D.
show || shrinks towards 0 so long as
A SIMPLE FAST CONVERGENCE METHOD
As discussed in Section 4, the fundamental reason that the convergence rate depends on the ini- tialization scaling is that the imlabace between F and G determines the convergence rate, but the imbalance between F' and G remains at the initialization scale. This observation motivates us to do a straightforward additional step in one iteration to intensify the imbalance. Specifi- cally, suppose at the To iteration we have reached neighborhood of an optimum that satisfies: A(Fres) GT I| S Y where the radius o, // |I| Fr GT |/3/4 / / is chosen for some tech- nical reasons (cf. Section F). Here we use F3 and G, to denote the iterates before we make the change we describe below and F, and G2 to denote the iterates after make the change.
Let the singular value decomposition of Fres AE'B with the diagonal matrix E' E R and Σg = df. then let Dine E & be a diagonal matrix and (Eine) = 3/o for some small constant Oa,,), then we transform the matrix Fras, GrO, by
Fres = Frrcs B Einns GT()) Gr(, BΣ-1
(5.1)
We can show that, when F' and G' have reached local region of optimum, their magnitude will have similar scale as M Therefore, the step Equation (5.1) 1) can create an imbalance between F and G as large the magnitude of M which is significantly larger than the initial scaling The following theorem shows we can obtain a convergence rate independent of the initialization scaling a. The proof is deferred Appendix F.
Theorem 5.1. With the same setting as Theorem 4.2, suppose that at the step T(3) we have ||A" A(F GTe - E] I y for some Y > O, and we do one step as in Equation (5.1). Then with probability at least 1 oom coe-cak (r5v)( we have for all t T(3),
2(1-T(31)
n2.
1792
[.G.G. - EE < of
1
2
1/3 < 3 S caor, and the step size satisfies v S 00.32/o from the iteration so long as 0 1/6 01
(T3) c1o (o, nn, for some positive numerical constants C,, 1,.... 10.
CONCLUSION
This paper demonstrated qualitatively different behaviors of GD the prattrpasteurization and over- pasteurization scenarios in symmetric and asymmetric settings. For the symmetric matrix sensing problem, we provide a (((/T22 lower bound. For the asymmetric matrix sensing problem, we show the initialization
that the gradient descent converges at linear rate, where the rate is dependent scale. Moreover, we introduce a simple procedure to get rid of the initialization scale dependency. We believe analyses are also useful for other problems, such deep linear networks.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
Simon S. Du supported by supported by NSF ISS 2110170, NSF DMS 2134106, NSF CCF 2212261, NSF ISS 2143493, NSF CCF 2019844, NSF IIS 2229881.
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. Learning and generalization in overparame- terized neural networks, going beyond two layers. Advances in neural information processing systems, 32, 2019.
Sanjeev Arora, Nadav Cohen, Wei Hu, and Yuping Luo. Implicit regularization in deep matrix factorization. Advances in Neural Information Processing Systems, 32, 2019.
Srinadh Bhojanapalli, Anastasios Kyrillidis, and Sujay Sanghavi. Dropping convexity for faster PMLR, 2016.
semi-definite optimization. In Conference on Learning Theory, pp.
Yingjie Bi, Haixiang Zhang, and Javad Lavaei. Local and global linear convergence of general low- rank matrix recovery problems. In Proceedings the AAAI Conference on Artificial Intelligence, volume 36, pp. 20129-10137, 2022.
Emmanuel Candes and Benjamin Recht. Exact matrix completion via convex optimization. Com- munications of the ACM, 55(6):11--119 2012.
Emmanuel J Candes and Yaniv Plan. Tight oracle inequalities for low-rank matrix recovery from minimal number of noisy random measurements. IEEE Transactions on Information Theory, 57 (4):2342- 22599, 2011.
Chih-Fan Chen, Chia-Po Wei, and Yu-Chiang Frank Wang. Low-rank matrix recovery with struc- tural incoherence for robust face recognition. In 2012 IEEE conference compuler vision and pattemn recognition, pp. 2618-2625 IEEE, 2012.
Lenaic Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable programming. Advances in neural information processing systems, 32, 2019.
Mark A Davenport and Justin Romberg. An overview of low-rank matrix recovery from incomplete observations. IEEE Journal of Selected Topics Signal Processing, 10(4):608-63) 622, 2016.
Simon S Du, Chi Jin, Jason D Lee, Michael Jordan, Aarti Singh, and Barnabas Poczos. Gradi- descent can take exponential time to escape saddle points. Advances neural information processing systems, 30, 2017.
Simon Du, Wei Hu, and Jason Lee. Algorithmic regularization in learning deep homogeneous models: Layers are automatically balanced. Advances in neural information processing systems, 31, 2018a.
Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterizzed neural networks. arXiv preprint 180.0.1810.02054, 2018b.
Raaz Dwivedi, Nhat Ho, Koulik Khamaru, Martin J Wainwright, Michael I Jordan, and Bin Yu.
Singularity, misspecification and the convergence rate of em. 2020.
Cong Fang, Jason Lee, Pengkun Yang, and Tong Zhang. Modeling from features: a mean-field framework for over-paramettrized deep neural networks. In Conference on learning theory, pp- 1887-1936. PMLR, 2021.
Rong Ge, Chi Jin, and Yi Zheng. No spurious local minima in nonconvex low rank problems: A unified geometric analysis. In International Conference on Machine Learning, pp. 1233-1242. PMLR, 2017.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kemnl:: Convergence and gen- eralization in neural networks, Advances in neural information processing systems, 31, 2018.
10

---

Published as a conference paper at ICLR 2024
Liwei Jiang, Yudong Chen, and Lijun Ding. Algorithmic regularization in model-free over- parametrized asymmetric matrix factorization. arXiv preprint arXiv:2203.02889, 2022.
Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M Kakade, and Michael Jordan. How to escape saddle points efficiently. In International conference on muchine learning, pp. 1724-1732. PMLR, 2017.
Jikai Jin, Zhiyuan Li, Kaifeng Lyu, Simon Shaolei Du, and Jason D Lee. Understanding incre- mental learning of gradient descent: A fine-grained analysis of matrix sensing. In International Conference on Machine Learning, pp. 15200-15233 15388. PMLR, 2023.
Xingguo Li, Junwei Lu, Raman Arora, Jarvis Haupt, Han Liu, Zhaoran Wang, and Tuo Zhao. Sym- metry, saddle points, and global optimization landscape of nonconvex matrix factorization. IEEE Transactions Information Theory, 6586)33489-3514 2019.
Yuanzhi Li, Tengyu Ma, and Hongyang Zhang. Algorithmic regularization in over-parameterized matrix sensing and neural networks with quadratic activations, In Conference On Learning The- ory, pp. 2-47. PMLR, 2018.
Zhiyuan Li, Yuping Luo, and Kaifeng Lyu. Towards resolving the implicit bias of gradient descent for matrix factorization: Greedy low-rank learning. arXiv preprint arXiv:2012.09839 2020.
Guangean Liu, Zhouchen Lin, Shuicheng Yan, Ju Sun, Yong Yu, and Ma. Robust recovery of subspace structures by low-rank representation. IEEE transactions on pattern analysis and machine intelligence, 35(1):171-184, 2012.
Yiping Lu, Chao Ma, Yulong Lu, Jianfeng Lu, and Lexing Ying. A mean field analysis of deep resnet and beyond: Towards provably optimization via overparameterizztion from depth. In In- ternational Conference Machine Learning, pp. 6426-6436 PMLR, 2020.
Cong Ma, Yuanxin Li, and Yuejie Chi. Beyond procrustes: Balancing-free gradient descent for asymmetric low-rank matrix sensing. IEEE Transactions Signal Processing, 69:867-877, 2021.
Jianhao Ma and Salar Fattahi. Sign-rip: A robust restricted isometry property for low-rank matrix recovery. arXiv preprint (eXXi:2202.0096: 2021.
Jianhao Ma and Salar Fattahi. Global convergence of sub- bob-gradient method for robust matrix recov- ery: Small initialization, noisy measurements, and over-paramettriizaton.. Journal of Machine Learning Research, 24(96): 2023.
Phan-Minh Nguyen and Huy Tuan Pham. A rigorous framework for the mean field limit of multi- layer neural networks. arXiv preprint 20Xiv:2001.14444 2020.
Yigang Peng. Jinli Suo, Qionghai Dai. and Wenli Xu. Reweighted low-rank matrix recovery and its application in image restoration. IEEE transactions on cybernetics, 44(12):2418 2014411-8430,, 2014.
Benjamin Recht, Maryam Fazel, and Pablo A Parrilo. Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM review, 52(3):471-501, 2010.
Frederieke Richert, Roman Worschech, and Bernd Rosenow. Soft mode the dynamics of over- realizable online learning for soft committee machines. Physical Review E. 105(5) 2022.
Itay Safran and Ohad Shamir. Spurious local minima are common in two-layer relu neural networks. In International conference on machine learning, pp.
PMLR, 2018.
Mahdi Soltanolkotabi, Dominik Stöger, and Changzhi Xie. Implicit balancing and regularization: Generalization and convergence guarantees for overparameterized asymmetric matrix sensing. arXiv preprint arXiv:2303.1422 2023.
Dominik Stöger and Mahdi Soltanolkotabi. Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstruc- tion. Advances in Neural Information Processing Systems, 34:23831-23844 2021.

---

Published as a conference paper at ICLR 2024
Tian Tong, Cong Ma, and Yuejie Chi. Accelerating ill-conditioned low-rank matrix estimation via scaled gradient descent. The Journal of Machine Learning Research, 22(1):6639-6700 2021.
Stephen Tu, Ross Boczar, Max Simchowitz, Mahdi Soltanolkotabi, and Ben Recht. Low-rank lutions of linear matrix equations via procrustes flow. In International Conference on Machine Learning. pp. 964-975 PMLR, 2016.
Roman Vershynin. figgh-dmeessooal probability: An introduction with applications in data science, volume 47, Cambridge university press, 2018.
Lingxiao Wang. Xiao Zhang, and Quanquan Gu. A unified computational and statistical framework for nonconvex low-rank matrix estimation. In Artificial Intelligence and Statistics, pp. 981-990. PMLR, 2017.
Colin Wei, Jason D Lee, Qiang Liu, and Tengyu Ma. Regularization matters: Generalization and optimization of neural nets vs their induced kernel. Advances in Neural Information Processing Systems, 32, 2019.
Zhiyuan Weng and Xin Wang. Low-rank matrix completion for array signal processing- In 2012 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 2697- 2700. IEEE, 2012.
Fan Wu and Patrick Rebeschini. Implicit regularization in matrix sensing via mirror descent. Ad- vances in Neural Information Processing Systems, 34:20558-20570 2021.
Yihong Wu and Harrison H Zhou. Randomly initialized em algorithm for two-component gaussian mixture achieves near optimality in o(n) iterations. Mathematical Statistics and Learning, 4(3), 2021.
Weihang Xu and Simon Du Over-paramettrization exponentially slows down gradient descent for learning a single neuron. In The Thirty Sixth Annual Conference on Learning Theory, pp. 1155- 1198. PMLR, 2023.
Xingyu Xu, Yandi Shen, Yuejie Chi, and Cong Ma. The power of preconditioning in overparame- terized low-rank matrix sensing. arXiv preprint arXiv:2302.01 186, 2023.
Tian Ye and Simon S Du. Global convergence of gradient descent for asymmetric low-rank matrix factorization. Advances in Neural Information Processing Systems, 34:1429-144 1439, 2021.
Gavin Zhang, Salar Fattahi, and Richard Y Zhang. Preconditioned gradient descent for overparam- eterized nonconvex burer-monteiro factorization with global optimality certification. J. Mach. Learn. Res., 24:163-11 2023.
Haixiang Zhang, Yingjie Bi, and Javad Lavaei. General low-rank matrix optimization: Geometric analysis and sharper bounds. Advances in Neural Information Processing Systems, 34:27369- 27380, 2021a.
Jialun Zhang, Salar Fattahi, and Richard Y Zhang. Preconditioned gradient descent for over- parameterized nonconvex matrix factorization. Advances in Neural Information Processing Sys- tems, 34:5985-5996, 2021b.
Xiao Zhang, Lingxiao Wang, and Quanquan Gu. A unified framework for nonconvex low-rank plus sparse matrix recovery. International Conference on Artificial Intelligence and Statistics, pp. 1097-1107. PMLR, 2018a.
Xiao Zhang, Lingxiao Wang, Yaodong Yu, and Quanquan Gu. A primal-duse analysis of global opti- mality in nonconvex low-rank matrix recovery. In International conference machine learning, pp. 5862-5871. PMLR, 2018b.
Bo Zhao, Justin P Haldar, Cornelius Brinegar, and Zhi-Pei Liang. Low rank matrix recovery for real-time cardiac mri. In 2010 ieee international symposium on biomedical imaging: From nano to macro, pp. 996-999. IEFR, 2010.
12

---

Published as a conference paper at ICLR 2024
Tuo Zhao, Zhaoran Wang, and Han Liu. A nonconvex optimization framework for low rank matrix estimation. Advances in Neural Information Processing Systems, 28, 2015.
Qinqing Zheng and John Lafferty. A convergent gradient descent algorithm for rank minimization and semidefinite programming from random linear measurements. Advances in Neural Informa- tion Processing Systems, 28, 2015.
Zhihui Zhu, Qiuwei Li, Gongguo Tang, and Michael B Wakin. Global optimality in low-rank matrix optimization. IEEE Transactions on Signal Processing, 66(13)33614-3) --228,, 2018.
Zhihui Zhu, Qiuwei Li, Gongguo Tang, and Michael B Wakin. The global optimization geometry of low-rank matrix optimization. IEEE Transactions Information Theory, 170):1108-1131,, 2021.
Jiacheng Zhuo, Jeongyeol Kwon, Nhat Ho, and Constantine Caramanis. On the computational and statistical complexity of over-parameterized matrix sensing. arXiv preprint arXiv:2102.02756. 2021.
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Gradient descent optimizes over- parameterized deep relu networks. Machine learning, 109:467-492, 2020.
13

---

Published as a conference paper at ICLR 2024
Supplementary Material
CONTENTS
Introduction
1.1 Setting 1: Symmetric Matrix Sensing with Symmetric Parameterization
1.2 Setting 2: Symmetric and Asymmetric Matrix Sensing with Asymmetrie Parame-
terization
1.3
Related Work
2
Preliminaries
3 Lower Bound of Symmetric Matrix Factorization
3.1 Proof Sketch of Theorem 3.1
4
Convergence of Asymmetric Matrix Sensing
4.1 A Toy Example of Asymmetric Matrix Factorization
4.2
Theoretical Results for Asymmetric Matrix Sensing
8
5
A Simple Fast convergence method
Conclusion
Related Work
16
Proof of Theorem 3.1
17
B.1 Proof outline of Theorem 3.1
17
B.2 Phase
18
B.3 Phase 2
23
B.4 Phase 3: lower bound of convergence rate
26
C Proof of Theorem 4.1
27
D Proof of Theorem 4.2
29
D.I Preliminaries
29
D.2 Proof Outline
30
D.3 Initial iterations
31
D.4 Phase 1: linear convergence phase.
32
D.5 Phase 2: Adjustment Phase
35
D.6 Phase 3: local convergence
38
Proof of Theorem 4.3
47
F Proof of Theorem 5.1
48
14

---

Published as a conference paper at ICLR 2024
F.1
Proof Sketch of Theorem 5.1
48
F.2 Proof of Theorem 5.1
48
Technical Lemma
52
G.1 Proof of Lemma B.1
52
G.2 Proof of Lemma B.2
................................
53
H Experiment Details
54
Additional Experiments
54
L1
Comparisons between Asymmetric and Symmetric Matrix Sensing
................................
54
1.2
Well-Conditioned Case and Ill-Conditioned Case
55
1.3
Larger Initialization Scale
56
1.4
Larger True Rank and Over- Parameterize Rank
56
I.5
Initialization Phase
57
15

---

Published as a conference paper at ICLR 2024
Appendix
A RELATED WORK
Matrix Sensing, Matrix sensing aims to recover the low-rank matrix based on measurements. Candes & Recht (2012); Liu et al. (2012) propose convex optinization-based algorithms, which minimize the nuclear norm of a matrix, and Recht et al. (2010) show that projected subgradient methods recover the nuclear norm minimizer. Wu & Rebeschini (2021) also propose mirror descent algorithm, which guarantees to converge to a nuclear norm minimizer. See (Davenport & Romberg, 2016) for comprehensive review.
Non-Convex Low-Rank Factorization Approach. The nuclear norm minimization approach in- volves optimizing over
matrix, which can be computationally prohibitive when n is large. The factorization approach tries to use the product of two matrices to recover the underlying matrix, but this formulation makes the optimization problem non-convex and is significantly more challeng- ing for analysis. For the exact-parameterization setting (k: = r). Tu et al. (2016); Zheng & Lafferty (2015) shows the linear convergence of gradient descent when starting at a local point that is close to the optimal point. This initialization can be implemented by the spectral method. For the over- parameterization scenario (k r), in the symmetric setting, Stöger & Soltanolkotabi (2021) shows that with a small initialization, the gradient descent achieves small error that dependents on the ini- tialization scale, rather than the exact-convergence. Zhuo et al. (2021) shows exact convergence with (L/TT²) convergence rate in the overparamierizatioon setting. These two results together imply the global convergence of randomly initialized GD with an O (1/T²) convergence rate upper bound. Jin et al. (2023) also provides a fine-grained analysis of the GD dynamics. More recently, Zhang et al. b:021b; 2023) empirically observe that in practice, in the over- parameterization case, GD converges with a sublinear rate, which is exponentially slower than the rate in the exact- sxact-paramettrizatton case, and coincides with the prior theory's 's upper bound (Zhuo et al., 2021). However, no rigorous proof of the lower bound is given whereas we bridge this gap. On the other hand, Zhang et al. (202 lb; 2023) propose a preconditioned GD algorithm with shrinking damping factor to recover the lin- ear convergence rate. Xu et al. (2023) show that the preconditioned GD algorithm with a constant damping factor coupled with small random initialization requires less stringent assumption on A and achieves a linear convergence rate up to some prespecified error. Ma & Fattahi (2023) study the performance of the subgradient method with L1 loss under a different set of assumptions on A and showed a linear convergence rate up to some error related to the initialization scale. We show that by simply using the asymmetric parameterization, without changing the GD algorithm, we can still attain the linear rate.
For the asymmetric matrix setting, many previous works (Ye & Du, 2021; Ma et al., 2021; Tong et al., 2021; Ge et al., 2017: Du et al., 2018a; Tu et al., 2016; Zhang et al., 2018a;b; Wang et al., 2017; Zhao et al., 2015) consider the pxact-parametterizaion case (k = r). Tu et al. (2016) adds a balancing regularization term g F F F-G GIE to the loss function, to make sure that F and G are balanced during the optimization procedure and obtain a local convergence result. More recently, some works (Du et al., 201 Sa; Ma et al., 2021; Ye & Du, 2021) show GD enjoys auto auto-balancing property where F and G are approximately balanced; therefore, additional balancing regularization is unnecessary. In the asymmetric matrix factorization setting, Du et al. (201 8a) proves global convergence result of GD with a diminishing step size and the GD recovers M up to some error. Later, Ye & Du (2021) gives the first global convergence result of GD with a constant step size. Ma et al. (2021) shows linear convergence of GD with a local initialization and a larger stepsize in the asymmetric matrix sensing setting. Although praatttarametrrizee asymmetric matrix factorization and matrix sensing problems have been explored intensively in the last decade, our understanding of the prermerrmmttiiiaaioon setting, i.e., > r. remains limited. Jiang et al. (2022) considers the asymmetric matrix factorization setting, and proves that starting with a small initialization, the vanilla gradient descent sequentially recovers the principled component of the ground-truth matrix. Soltanolkotabi et al. (2023) proves the convergence of gradient descent in the asymmetric matrix sensing setting. Unfortunately, both works only prove that GD achieves a small error when stopped early, and the error depends on the initialization scale. Whether the gradient descent achieve exact-convergence remains open, and we resolve this problem by novel analyses. Furthermore, our analyses highlight the importance of the imbalance between F and G.
16

---

Published as a conference paper at ICLR 2024
Lastly, we want to remark that focus gradient descent for Lg loss, there works more advanced algorithms and more general losses (Tong et al., 2021; Zhang et al., 202 lb; 2023; 201 8a;b; Ma & Fattahi, 2021; Wang et al., 2017; Zhao et al., 2015; Bhojanapalli et al., 2016; Xu et al., 2023). We believe our theoretical insights are also applicable to those setups.
Landscape Analysis of Non-convex Low-rank Problems. The aforementioned works mainly focus on studying the dynamics of GD. There is also complementary line of works that studies the landscape of the loss functions, and shows the loss functions enjoy benign landscape properties such (1) all local minima global, and (2) all saddle points strict Ge et al. (2017); Zhu et al. (2018); Li et al. (2019); Zhu et al. (2021); Zhang et al. (2023). Then, one can invoke generic result on perturbed gradient descent, which injects noise to GD Jín al. (2017), to obtain convergence result. There are some works establishing the general landscape analysis for the non-convex low- rank problems. Zhang al. (2021a) 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 Bi al. (2022) 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. We remark that injecting noise is required if one solely uses the landscape analysis alone because there exist exponential lower bounds for standard GD (Du et al., 2017).
Slowdown Due to over-parameetrrizaion.. Similar exponential slowdown phenomena caused by wver-parameterizzaion have been observed in other problems beyond matrix recovery, such as teacher-student neural network training (Xu & Du, 2023: Richert et al., 2022) and Expectation- Maximization algorithm on Gaussian mixture model (Wu & Zhou, 2021; Dwivedi et al., 2020).
B PROOF OF THEOREM 3.1
In this proof, we denote
X E gank
(B.1)
where 24 E Rixl is the transpose of the row vector. Since the updating rule can be written as
X = X. - -X,x, - - Σ)X,,
where we choose instead of 2n for simplicity, which does not influence the subsequent proof. By substituting the equation (),1), the updating rule can be written as
) T = (1 - n([l=]11 oz) - j=l
n((?t) (
where a; 0 for i r. Denote
(z) xx
= max 3.8
||æ 12 | 1|
is the maximum angle between different vectors in 31, Fn. We start with the outline of the proof.
B. PROOF OUTLINE OF THEOREM
Recall want to establish the key inequalities (3.3). The updating rule (2.3) gives the following lower bound of xf+ for i
||atl| 12 22 ||
1 11-210
1--200 Σ | 11? - 2n Σ
1aa3112
(B.2)
55
1>
17

---

Published as a conference paper at ICLR 2024
where the quantity of' (b) Peg,t and the square cosine 255. cos² (xx, Thus, establish the key inequalities (3.3), we need control the quantity 0f Our analysis then consists of three phases, In the last phase, we show (3.3) holds and our proof is complete.
In the first phase, show that ||=;||] for r becomes large, while ||>] l| for i still remains small yet bounded away from O. In addition, the quantity 0zj, remains small. Phase I terminates when | 2 is larger than or equal to g0,
After the first phase terminates, in the second and third phases, we show that of converges to 0 linearly and the quantity o 0 Eysr |a converges zero at linear rate as well. We also keep track of the magnitude of ||a]]]] | and show ||a:||| stays close to o, for S r, and || < 2a for i r.
The second phase terminates once 04 < 5O 11591 and we enter the last phase: the convergence behavior of Σj>r |af5 Note with o 5 [olll//o and || 20, for i S prove (3.3b). The condition (3.3a) can be proven since the first two phases are quite short and the updating formula of z, for > r shows | cannot decrease too much.
B.2 PHASE
In this phase, we show that || for i < becomes large, while || for i > still remains small. In addition, the maximum angle between different column vectors remains small. Phase terminates when || is larger than constant.
To be more specific, we have the following two lemmas. Lemma B.1 states that the initial angle Oo Ologg (rH)) is small because the vectors in the high-dimensional space nearly orthogonal.
Lemma B.1. For some constant e4 and c, if 2
(1 with probability at least On S log (rg
1 - c4n exx((xxx) we have
(B.3)
Proof. See S for proof.
Lemma B.2 states that with the initialization scale a, the norm of randomized vector 2i is O(a?).
Lemma B.2. With probability at least - 22 en.exxpp_cckk/ for some constant we have
|0 [22/2, 2a
Proof. See &..2 for the proof.
Now we prove the following three conditions by induction.
Lemma B.3. There exists a constant C₁ such that Ti S C1 Co and then during the first T, rounds, with probability at least 1 - 2cnn exp(=eepppv (Vk) - 2n exp(-cck/ for some constant ea and es, the following four statements always hold
|| 2| < 201
(B.4)
2 < |
|| < 20
(i >
(B.5)
20g >
(B.6)
Also, if 1|/l//112 S 30//4 we have
| 12 (1 not/4)ll<111
(B.7)
Moreover, Ti rounds, |1 3 and Phase terminates.
18

---

Published as a conference paper at ICLR 2024
Proof. By Lemma B.1 and Lemma B.2, with probability at least 1 2cnn 2 exp(-vV -Vk
2n exp(-c5k/ (////kk//4 4), we have || E [a2/2, 2a for i E [n], and du I (og"(r//o///)(rm) Then
assume that the three conditions hold for rounds before t, then the t + 1 round, we proof the four statements above one by one.
Proof of (q.(B. For i > r, we have
(x)t)) (z)) (z))
(xt) (T)) (T))
5=1
Then, the updating rule of | can be written
[1x ( || 2n Σ ((:)) n2(
(x)) x5)))))))))) (((x))
S 1-111 (B.8)
J,k=1
The last inequality in (B.8) is because
(uf) af(x))) (x4) (x/) s (xt) x [/))3 (
(B.9)
{ Tax)) Tz)))
(B.10)
and then
n
n
2
(a Tx) S ?
((x)) 25)² ((a1) x2))))
==
jik=1
= 12 noi > ((x)) 2gy² Tay)
5=1
$ Σ (<)))
(B.11)
1=1
where the last inequality holds because S 1/no1. Thus, the -n-morm of x.! does not increase, and the right side of (B.5) holds.
Also, we have
|
2
|| - 2n Σ (xf)) (aa))=a)) 24)² +,²
Σ (xf) Taf)))()))))
==1
1=1
n
2 || || 2 2n10 Σ
|0ا1 2
2n|10,111
(B.12)
j7i
((x{) |< Oij. S O,. Now by (B.4) and (B.5), we can get
Equation (B.2) is because
Σ
|af11 rr. r. 20 + (n r). 20 < 20 + 2na²
Hence, we can further derive
||
112
2 || (1 21 + 2naa)
2m. 202)
2 || (1 1780/111 + 4022))
where the last inequality because a S /roi/ VT. Thus, by (1 a1 b) (1 a b) for b >> O, we can get
1 2 | (1 - 11-11(80,0 + 4Q2))
2 a² 2
(1 - Ti Tin( (200) + 4o²))
(B.13)
a²
(B.14)
4
Equation (B. holds by induction hypothesis (B.6), and the last inequality is because of our choice on T1, a, and 0g < O log(////a)) from the induction hypothesis. Hence, we complete the proof of (B.5).
19

---

Published as a conference paper at ICLR 2024
Proof of Eq.(B.)) For < r. if || v 3 by the updating rule,
2 (1 (1)
- 2n Σ
((x)) Tz)) + (/1121111 o.) Σ
((x)) Tay)
j+1
jfi
(B.15)
2 (1 -
- 21
- (( Taa) 2 1 - og
|
J
2 (1 - [| - 2n
((+)) x1)) ) 4n (no
THe last inequality uses the fact that |||=;|1- 0.l S 20 and || s 201 Then, by Tof) S | |||]1=]]1 0, we can further get
| 12 2 - 27(1==911-00 -.)) - 2n) Σ | - -21 ||
j
2 (1 no:/2 - (no - n100 11)0//1))<=;111
(B.16)
(1 + (11/2 12 1/ 11/16)) ||:11
(B.17)
(1 no: n0:/4)]|=113
The inequality (B.16) uses the fact 0 < 20g- S 128kr and Ejfs ||=,|| < 20,r + 2na - 40,r S
The incquality (B.17) uses the fact that S 32n07
324
Proof of Eq.(B.4)
If ||] 2 3 by the updating rule, can get
|| +
11
0.l
s
7?
((=)) TTf))
|| 0,l
24
(w+)) Ta)) + x/
Σ
((+)) (
$$1
< - -1-m0o |||;1|| oi + 3n
((z)) Taf)
(B.18)
jiytt
(8)
The last inequality holds by (B. and
2n 21||=/112 1 ([:1==[1--0)))aaf33 (x)12 2n/²
Σ (af)) xf)² Taf)
(B.
jfi
311
2 0. (201) 201 - nof
(B.20)
nott.
(B.21)
where (B. (B.20) holds by || ス 3r, || < 20, for all E [m]. The last incquality (B.21) holds
by S C( (()) for small constant C. The first term of (B.18) represents the main converge part, and (a) represents the perturbation term. Now for the perturbation term (a), since a कmnン and
20

---

Published as a conference paper at ICLR 2024
of 20ro
0 < 200- S 20rk
we can get
(a) Σ ((x)) 1j)++ + Σ (c))aTy)
(B.22)
Hijjor
< (ro1 + 2nax )0 201
(B.23)
S 2roi O2- 2011
(B.24)
Arof 8:
S of /5,
(B.25)
where (B.23) holds by (B.4) and (B.5). (B.24) holds by a = OlVro1/ and the last inequality (B.25) holds by 0 is small, i.c. 0, 28g- (11rk²)). Now it is easy to get that (x) (o) by
x < 20,
|| ||a oi S - -00))))([==]] o.)) + 3n0
3nd
S (1 no,)o; +
S.
(B.26)
5
Hence, we complete the proof of (B.4).
Proof of Eq.(B.6) Now we consider the change of 0. For i * j. denote
0.g = (cr))TT))
12. 1
Now we first calculate the (a)+t)T<t) aj by the updating rule:
T -1- o.)) (1- n 11135111 o3)) (of) 2y n||=551 - -o)))) of
111 - 2 + n²
(xf) (xf)) a3
D
(n - n1|==|12- o.)) n1(20/11 oU))
(xf) a (xa) Ta,
ktic
+n² Σ kgij
+1 Σ xf Aesht.
Now bound A, B, C. E and F respectively. First, by || < 20 for any i E [m], we have
A (1 - 7 [|=]||] o,) - ~(1=51]1 (100--11111000---------000000000
o,) (1=/]1 -3))) (at)
$ (1 - 7 (1|=)| + || σ. - 0,) + + 4of) Tay,
(B.27)
Now we bound term B. We have
B + = (-n(1>=;]1 + [|,) 7 (11=5|12-0))13331
- 0ا)رااا11 + -1:)1--0)))111111 (at) of (8o (x aty.
<
(B.28)
Then, for D, by 0, < 1, we have
D D=1 n²
Σ
| Ves. (of)
(n²² n² .0 01/ (Bs.s) (ai) 2rj.
(B.29)
21

---

Published as a conference paper at ICLR 2024
For E. since we have
E
2m
((t)
af
Jay] + 4011?
of (xf() x521
((xt)
x
21
| Von 10
Σ
||
Vewaeensss (a1) 23
kii.
ktip
27
| V Ou, 0ks.// + 4no 172 (201) 0 Vo0,s
og.
(B.30)
Lastly, for since (a²) of (x)t) T of S ||33 12 S 4of, we have
S ) (a:) Tay..
(B.31)
Now combining (B.27), (B.28). (B.29), (B.30) and (B.31), we can get
(u(tt) 3
1+1
(B.32)
$ 1 - (2||==]|| + 2||25|1 -5)) + 21, Σ
Des,, + 30m2oin' /o35,)
(xf)) Tnj.
Aight.
(B.33)
On the other hand, consider the change of ||=:|| By (B.15.)
1 2 (1 -;))) 2n Σ ((x)) 22)² + 77 (1 o.) Σ (aa)) x²)²
Jti
2 (1 20 - -o;) 2n Σ
|a3ل| 1000. 4n 1n"n8(o7))laf
2 (1 21(11=211 - -,) 2n Σ
4n
Hence, the norm of x, +1 and 25t2 can be lower bounded by
|0 112+11111a
2 (1-2n(1==211
2n (| - oo)) - 20(11=5]12 o,) -2n
Σ
|| + 0ze,e) 2n((12z)1 + || 1lz::12)0 10
4n 20 + Σ (11 σ1) Σ 1 + - | 2e0l1111111"
1
2 (1 2011/111 - -o:)= - 20(111/11 -a,) - 2n Σ
| + 0gk,,) 2n((1 112 + || ( 10
A
- -4y20nn² 150nnoff of - 2 417 (201)n - (20,)0. - 4nj0 -72n2 (000of ||;;|| (B.34)
2 (1-2n 1- - -o;) - 27(11=9]1 o,)) - -2n Σ (1 + 03r.e) - -2n(1 |2,1112 + || 1))as
0nf0nn² (aan2of]] o3) ||=2
(B.35)
where (B.35) holds by 8k 2 8 and 2m 1121112 - σ1) S 4no 1. Then, by (B.33) and (B.35), we have
0 = =Bzj.. . (aft1)T 2z +
|| |Plla 112 | 1|?
T2)
1- A + B
S S0zz
(B.36)
1 A C-
22

---

Published as a conference paper at ICLR 2024
where
A 2m (1222221 - 0, ||,]]1 o:)) s 4n00
(B.37)
B = 20|1=xe1? / 00., 0ks. 30n² on/ Vo.j.
(B.38)
and
21
Σ k
1 (0st,t + 0gb,a) + 21 1|² + ||,;11 + n
(B.39)
< (8mo)) + 22nan 2ro,) + 6n²n2oof og) O2,
(B.40)
where the last inequality uses the fact that
Σ kyL
| I|
- Σ | S
+
Σ kS
||al1 - 2ro1 + 2na?
Hence, we choose v 1000m01 to be sufficiently small so that max (Ax(A S 1/100, then by I-A+B
S 1 + 2B 2C for max { A, C} < 1/100,
I-A-C
1-
Oij.e 1-
$ (1 2B + 2C)
$ Oei + 4n Σ ||,x||2. Vis,,O0s; + 60n20nn'' /iss
kti,j
+ 02 8810 + 22)(2na² + 2ro,) + 6n?
$ 0yg + 40r + 2na 100/22 + 60n 2/
+ 8 8811 + 2n + 2ro,) ) + 6n n
$ 81g + 62 + 2na 60m² 0? 8no + 6n
S 0 981) (ra,0//²)
The last inequality holds by a S /01/ Vn, and n² n²oin² < because 7) S n²
Hence,
0,+1 S 0, + 98n)(r )02/2
(B.41)
The Phase terminates when ||x;" 1| > 3n. Since |a:911 2 a²/2 and
| 1|2 2 (1 no, 42)
(B.42)
there is constant C3 such that Ti v C1 (log( /0/
Hence, before round Tı, 0r, S 0o 98m7i rri 3/2 < 0. 980 3/2 log(Voi/o) s 20.
This is because
6, = 0 (1700/00/////7/)))mm))
by Lemma B.1 and choosing & 2 c2((rk)² log log(r for large enough 02
B.3 PHASE 2
Denote 0f = max Ozg.c. . this phase, we prove that 0f linear convergence, and the convergence rate of the loss is at least ((1/T2). To be more specific, we will show that
0 $ 0.- (1 (1-n-- n
0/44) S 6
(B.43)
8
00
(1 110 5 4" oi (r)
Eier |att1 -
(B.44)
Eisr
|
8
|||=م11 - ozl 5.l5
(B.45)
||اl < 2a² (1>r)
(B.46)
23

---

Published as a conference paper at ICLR 2024
First, the condition (B.45) and (B.46) hold round T1. Then, if it holds before round consider round + 1, similar to Phase 1, condition (B.46) also holds. Now we prove Eq.(B.43), (B.44) and (B.45) one by one.
Proof of Eq.(B.45) For S r, || 2 / by Eq.(B.18
|| oıج Σ -1- - oil + 3n
Σ
((x))
(Tx)Taa))²
(B.47)
Hence, by (B.45) and (B.46), we can get
((x)))
2 E (<x)) 2/)2+
Σ (Ta))azf
jti
jtiii
jtijr
I (ro1 + 4no 1
2 2r
(B.48)
S 2r0 0%
(B.49)
S 2ro1 20p S /2/
(B.50)
The inequality (B.48) is because
4mom the inequality (B.49) holds by induction hypothesis (B.43), and the last incquality (B.50) is because of (B.6) and 0g S 80rk
Hence, if |||=||| 12 0ıl S /4 by combining (B.47) and (B.50), we have ||| 0, S (1 no:) ||=))l== oil + 3no,/20 S o./4. Now is easy to get that |||=م|| - oi - 0.25Ø, for t 2 Tj by induction because of ||| 0zl S 0.250; Thus, we complete the proof of (B.45)..
Proof of (B.33.43) First, we consider < r. j * i E [n] and 0zg, > 8t/ /2, since (B.4) and (B.5) still holds with (B.45) and (B.46), similarly,
still have equation (B.36), i.e.
( - 1 1- --
0ij.tt1 = Ozj.e
where
A 2n (| o.) + 2n(111111 -0,) 2 22 (o,/4)) 1/1100.
B [|] + ||=)|1)) - -2n Σ ||a0112 / Vou Okj.t/ O 30m2
/ Voia.
kgi
2 2n(1211 + ||05|13) - 4n Σ
||
Anma? 70
(B.51)
AST
30, Shro v /20T, - 4nmo² - 40n217o07
2 2n
(B.52)
4
21 0r
(B.53)
The inequality Eq. (B.51) holds by 0ig,e > 0% /2, the inequality (B.52) holds by (B.43), and (B.53)
holds by
Or. 0 m2
a= a=o " ==0(1/n²kar)
(B.54)
The term C is defined and can be bounded by
= 21
Σ
||<
110,.) + 0gn,)) + 21(1120012 + | 13)) 6r/00n200
4n
1f + 4mma2 + 6n 0n,
kSr
< i 0f + 4yma² + 6n1²n of
< 8rno, 01, + 4nna" + 6njnn² n² o
(B.55)
< n 0./2.
(B.56)
24

---

Published as a conference paper at ICLR 2024
The inequality (B.55) holds by (B.43), and the inequality (B.56) holds by (B.54).
Then, for i S r,j #i [r]] and 0eg,e > 0 /2, we can get
A 1
Oij.e-1 S Opgs.
- A-C C
2 --
s 0sg
2 - 2-9.001/2
1- 11 00/2
S Obgs
- Oig,t (1 11 0,/4)
(B.57)
For i I r,j E [m] and Pzga I / /2, we have
B 2 22 1ex1100% Vij. 2n Σ
| 1 Vil / VBj, 30m2n/o0t 08 /V2,
(B.58)
kSr
kSr
-nrro 0 V (Anma² 2 + +30n² 27/ o1 04 / V
(B.59)
11- B 0ij,441 S Oijs. (I-A-C) S Oij (1 - 2B + 20)
S 0iz,t + 1 1 VBiga + (4mma + +30n2n2 of) Vol + 200
$ 0
+8nros1 (Anna² + 30n²1) o2'00' no
2
30
(B.60)
4
The last inequality is because Spro11 + 4nna + 30n²n) + n0, S by r s O(1/no,) and S O(1/na"). Hence, by (B.57) and (B.60) and the fact that n0,/4 /4 S 1/4,
0u O max 14'
3
n..07.... r,../44 =(1 7. 0,/4)0/"
(B.61)
Thus, complete the proof of (B.43)
Proof of (Q.(B.44) Also, for > r, denote Oi, = 1, then
Ean (+)) (1)) (c)))(())))
| 1 || 2n
(a/)) 25)² n
1=1
uAk=1
2 | - 2n Σ
|| 12:112:0 (2)j.t))
(B.62)
j=1
| |1 - 21ro, 00 - -mma?
The last inequality holds because | 20 0,/8)
0. < 0 < ((1/TK) a < Vo,/n
(B.63)
(B.64)
Hence, the term 8t
/||x;| for i > r is also linear convergence by
04' 1+
0U
1- 17 0
0
(1
no.
Essr Hence, complete the proof of (B.44).
E
|
1 17 0
Σ Eisr |
8
25

---

Published as a conference paper at ICLR 2024
B.4 PHASE 3: LOWER BOUND OF CONVERGENCE RATE
Now by (B.44), there are constants co and e7 such that, if we denote T2 Ti + (=(lo/(/To//))//o0))) co (llo(y/ra (rroi/)//oo)) then we will have
04
<
Σ
|| T2 //ro
(B.65)
ir
because of the fact that 07. /i>r 11 v ninz we can have
4
S 4/a². Now after round T2, consider i > T,
2 |,:11 |a,t"1192
2n Σ
|, (05113)03..))
j=1
z |
20 -2n Σ
|1a5113)
jor
Hence, by (B.62), have
Σ j2r
1aatt1122
z
|a5ا|| 1??
1 1-2000028 05 - 2n Σ
110511?
(B.66)
j>r
32r
Σ
|a5s1 11?
4n
Σ 1105112
(B.67)
j>
j3r
where the second inequality is derived from (B.65).
Hence, we can show that Ejer ||ar| = (211 (T2 In fact, suppose round T2, denote AT;
Ejsr 1 then by
|| 2 ||=]11(11 21) Σ |= 2(thee)
1=
> ||
2 8 -
we can get
| T
> T 11 21ro 2 0% 2)maa2)2=-21
IV
||> Th 112 (1 cs
(2nro101, + 2nma?))
|| 1 -1
cs log(rVoi/o) (4rk0o 2na 2no2/orr)
IV IV
|
(B.68)
where the inequality (B.68) is because
0p 0
(B.69)
mxllo((r /oi/a)
Vor
a² 0
(B.70)
n llgg(r (o/g()/o1/a))
Hence,
T2Ar; 2 T3 (n r) a² 2 (r) r)
(B.71)
8
8
by n > r. Define A = A1s+s(1 4nAr2+i), by (B.66.)7), we have
A1,ti S Ar, = Σ 122 < 2na
(B.72)
25
26

---

Published as a conference paper at ICLR 2024
On the other hand, if mTT2 + A) S 1/8, and then
(T2 + 12+111 'T(2 + +1+ 4m)
= <T2 A1 - (T2 + :)/1)² A71 is + 1T 4n1AT++)
2 + +1)Ar,+1 - (I2 + +)41)) 2 + nATz+1/2
(B.73)
2 (T2 - n/TT+i/22 2) A
2 (T2 + +1)ATz+in
where (B.73) holds by AAgt S 2nna² < $1/8.
If (T2 + Ar,++ 1/8, since n,, $1/8, we have nA,, 2nma - 1188.
(T2 +) Ar+++1 2 (72 + A))rr+i(11 4nAr,+1) + nATs+1(1 4n Ar,t)
1
1
1
A
8 2
2
IV
16
Thus, by the two incqualities above, at round t 2 T2, can have
ntA. 2 m 1/16].
Now by (B.71),
27 colog(/ror /ro////a nTzAr,
(B.74)
80,
then for any 2 T2, we have
07 log( /roi/aaa² 1/16
m/,, 2 min
(B.75)
80,
Now by choosing a Ö(Vo,) that
er log( Vroi /a)a² 8a,,
$ 1//16, we can derive
C7 log / /
A
2
(B.76)
80,
Since for j r, (X,X, - E)ij |,,5|1 1 have |xxX
Σ11 Ej>r
A2/n and
(7 (oloo(Vros/ajoo
|| E11² > A2/n 2
n
C PROOF OF THEOREM 4.1
Denote the matrix of the first row of F, G U. respectively, and the matrix of the last n r row of F, G J, K respectively. Hence, U, V Rr JJ E (n-))xk In this case, the difference F.G.T - Σ can be written in block form as
F.G. - U.V. E, U.K.
J J,Ky
(C.1)
where E, I Rr Hence, the loss can be bounded by
||:KT|| < |...T- - Σ|| < |IU, E,1 |AV | + |U + |MKK
(C.2)
The updating rule for (U, V. J, K) under gradient descent in (4.2) can be rewritten explicitly as U+1 = U, + T,,, -V, V + K, K.) V41 = Vj + 1,E,U, - VVV U, + J. J:) J+1 = Jr (V, V. + K, K,TK,) K2)
K411 = K; (U, U, + J. Jt).
27

---

Published as a conference paper at ICLR 2024
Note that with our particular initialization, we have the following equality for all t:
U = 0, J.V," = 0, and U. = Vv-
(C.3)
Indeed, the conditions (C.3) are satisfied for = 0. For + 1, we have
Ut+1 Ut + n22, - U.V. Vv, - V2 + n22, - UVV, Ju, - Vi+1, Ke+1 Kr nKJJ Jr U241KH41 1+1 = U.K, n - U.V, )UKK - VVVJj J.KT- -1p - U.V, JU,, J.KT =0
The last equality arises from the fact that U, K.K.T = 0, J.V. = and U+ Vi. Similarly, we can get Jet1 V+T = 0. Hence, we can rewrite the updating rule of Jr and K₁ as
J++1 J1 14-10 n,, Ke
(C.4)
Kt+1 K2 n..Je. Jr.
(C.5)
Let us now argue why the convergence rate can not be faster than 92((1 - 6n) Denote A E (nn-r)x as the matrix that (A) 1 and other elements are all zero. We have that Jn a and
Ko= = (a/3)- A. Combining this with (C.4C. and (C.5), we have Jr = a, Kr = b, A, where
= a. bo = a/3,
(C.6a)
a++1 = n
(C.6b)
bi+1 bt na,
(C.6c)
It is immediate that 0 S 0r+1 S 0r, 0 S byt < be max{ br} S a because of not S 1 =
gas < 1 and similarly naas < 1. Now by na² - 1/4
| = = (1 [1 Dare 2 (1 (1-21p) 22naa 2 (1 4na- 4na2)abbe
(C.7)
By (C.2) that ||F.GT Σ| 2 K Il. the convergence rate of [|F.G. - El| can not be faster than agdu(1 4na?)' 2 o (1 4na?y.
Next, we show why the convergence rate is exactly @((1 (mna)))*) in this toy case. By (C.3). the loss ||F.G,T - E I |02U, - Er + JJ,K, ||. First, we consider the norm |U - Erll-
Since in this toy case, E, = I, and U. = V2 for all t, the updating rule of U, can be written as
U1+1 U. - nU,U, - 1)U
(C.8)
Note that Un = (aI,. 0) E R By induction, we can show that U, = (a,I, 0) and 0441 = at - 1 - 1)a, for all / 2 0. If ar S 1/2, we have
0++1 = (1 + 17 n 2 ar + 2/2).
Then, there exists constant a and T, ci (log( (1/gg1//)) / /n) such that after T3 rounds, we can get
ae 2 1/2. By the fact that 0++1 = a+ + 1 a - max (as, 2} when 17 < 1, it is easy to show
at < 2 for all > O. Thus, when 1) 1/6, we can get 11(ar + 1)a, > 0 and then
|a0+1 - 1| = 1(a.- - 1) 17( () + 1)cxl
|a, 1 1/a= + 1)az)
< aa - 1|(1 - 2/2)).
we know that IU.U, Σ = 07 1 converges a linear rate
(3) Σ|| < (1 - 2 v (1 nna-nnaaaaan (1-//12
NTUUU
(C.9)
where (a) uses the fact that
1 1- n-² 022/421-17 ビ (1 - 222
(C.10)
Hence, we only need to show that To do this, we prove the following statements by induction.
||- || converges at a relatively slower speed
a z a 2 a/2, bZ.1 032 n7a2? (/22/44
(C.11)
28

---

Published as a conference paper at ICLR 2024
Using bu = a/3, we the above implies that || || a,b, O(1 (naa)))))
Let us prove (C.11) via induction. It is trivial to show it holds at t and the upper bound os by
(C.6). Suppose (C.11) holds for t' S t, then at round t + 1, we have
6,41 = bg (1 n - be( na²//4²² - by 1/2244)
(C.12)
Using d++1 (1 - )bt{), we have
(a) 0c+11 = 40 II (1 n66)) 2 a0 1
t
(6)
a²
4 a/2. (C.13)
Σ 1/
2 a
1 - 1
9 sao
1=1
i=1
where the step (a) holds by recursively using (1 a)
b) 2 (1 (a + b)) for a, b E (0, 1), and
the step (b) is due to ba I b/- (1 n/0//4/*=/// I 9 (1 - qa 2 y and the sum formula for geometric series. Thus, the induction is complete, and
a²
4
|| || = a,b, S (a²/3)- //) (1 - na² /4)1/2 < (1 na? /22/ ([1-n2/4)(--i)) (C.14)
Combining (C.9) and (C.14), with ||Al|2 ||||| - rank(AA) ||A||2, complete the proof.
D PROOF OF THEOREM 4.2
We prove Theorem 4.2 in this section. We start with some preliminaries.
D.1 PRELIMINARIES
In the following, we denote 826-1 V2k + 18. Also denote the matrix of the first r row of F, as U, V respectively, and the matrix of the last U. V.V. E RT*, K E (n)-x) We denote the corresponding iterates as U, V1, Jr, and K,
of F, G J, K respectively. Hence,
Also, define E(X) A A(X) XX We also denote r(X) A(X).. By Lemma G.2, we can show that |E(X)] S 028+1 |||X|| for matrix X with rank less than 2k by Lemma G.2. Decompose the error matrix FXX) into four submatrices by
(x) Ex(X)
B((x))
E(X)=
where (X) E RT Ex() e R Rrx(n-r), (x)) E ((a-))xr,,sC E R(n-r)x(-rr) Then the updating rule can be rewritten in this form:
U U. + VV (V, V, + K, K.) + +EI - EVV, + 1EZ - Σ)K, (D.1)
V441 V++ ,/V.QU, U, J, J.) + E (P.G. -EJU, + +nE (F.G. E)J, (D.2)
J++1 = Jt - (V, V/+ K, (.) - +),,+ - K)
(D.3)
K441 = K, (,,,KK,U,, + J,T, +n (F.G.. - E)U;+ + +FF, - E)
(D.4)
Since the submatrices" operator norm is less than the operator norm of the whole matrix, the matrices GF - -E, ..., 4 satisfy that
[...F.GTT Σ)| < |[EGG - Σ)|l S2tt1 Σ||, = 4.
An important property in analyzing the asymmetric matrix sensing problem is that G = U U + - V K K remains almost unchanged when step size n is sufficiently small, i.e., the balance between two factors F and G are does not change much throughout the process. To be more specific, by
Imbalance term
F+t1 = F. (FF.TT - -)G,,-(F,CG. - -)G, G++1 = G. - (P..G - -E) - - - Tr,
we have
(PTT Fet1 G[+ (F. F. G. G.)]| < 2/2 |...G. - E11 max Fell, 2.
(D.5)
29

---

Published as a conference paper at ICLR 2024
In fact, by the updating rule, we have
F Pi+1 G++1
- -EG, F (F.G. - E)AG -2) -2) F.). F Pi - G. G. +1 (FT - - (GGT
so that
F1-1 G4+1G1+1 (F. F. - G.)l & | | - -E1?
S 2n |.F.G.
Σ|| max Fl [IGG,l
Thus, will prove that, during the proof process, the following inequality holds with high proba- bility during all t 2 0:
20²1 2 U. + U. J. V K, K. 2 a² I.
(D.6)
8
Next, we give the outline of our proof.
D.2 PROOF OUTLINE
In this subsection, give proof outline.
Recall A, = FTF, - - U that with high probability, Åg has the scale a, i.e., Ca Ao 2 ca2I, where C constants. Then, we apply the converge results in Soltanolkotabi et al. (2023) to argue that the algorithm first converges local point. By Soltanolkotabi al. (2023), this converge phase takes at most To = ((11no,,
V. - K, Kg. In Section D.3, we show two
(15(//11/))) rounds.
Then, in Section D.4 (Phase I), we mainly show that Mr = max(] Elg. || II. VIV,, [I} converges linearly until it is smaller than
M, S O(076 + a²) |2)
(D.7)
This implies that the difference between estimated matrix U, U.V, and true matrix Σ, |,VVV Σ|| will be dominated by K, []. Moreover, during Phase we can also show that Ae has the scale a. Phase begins at To rounds and terminates at Ti rounds, and Ti may tend to infinity, which implics that Phase 1 may not terminate. In this case, since M, converges linearly and M, 2(0 + []. the loss also converges linearly. Note that, in the exact-parameterized case, i.e., k k= r, can prove that Phase I will not terminate since the stopping rule (D.7) is never satisfied as shown in Section E.
a JT
The Section D.5 (Phase 2) mainly shows that, after Phase 1, the I0 Vi]l converges linearly until achieves
| Vill S Oa22 / + O J[K, 1l
Assume Phase 2 starts at round Ti and terminates round T2. Then since we can prove that ||U: Vill decreases from 4 (a1)) to ((a?), Phase 2 only takes relatively small number of rounds, i.e. most T2- Ti O (log(Vo,//)) (Vo,/a)/mo- rounds. We also show that M2 remains small in this phase.
The Section D.6 (Phase 3) finally shows that the norm of K2 converges linearly, with rate depen- dent on the initialization scale. As in Section 4.2, the error matrix matrix sensing brings additional challenges for the proof. We overcome this proof by further analyzing the convergence of (a) part of K2 that aligns with U,, and (b) part of K, that lies in the complement space of U.. We also utilize that M, and UU, Vell are small from the start of the phase and remain small. See Section D.6 for a detailed proof.
*The upper bound ((51) of ||U, Vell is proved in the first two phases.
30

---

Published as a conference paper at ICLR 2024
D.3 INITIAL ITERATIONS
We start our proof by first applying results in Soltanolkotabi et al. (2023) and provide some ad- ditional proofs for our future use. From Soltanolkotabi et al. (2023), the converge takes at most To = ((1/no,,)) Log(voi//aa) rounds.
Let us state few properties of the initial iterations using Lemma G.3.
Initialization By our imbalance initialization Fo = a. Fo. Go = (a//3) - Go and by random matrix theory about the singular value (Vershynin, 2018, Corollary 7.3.3 and 7.3.4), with probability at least 1 - 2 2exp(-co
for some constant if n > 8k: we can show that [Amin (Po), max (Fo)) S 22 J. mo (Go), max (Go)] S //x
33x y30
and
V6
3a 2
a²
I 12
F2
Fu Go Go = U Un + Jo - Vo Kg Ku 2
(D.8)
2
2
As we will show later, we will prove the (D.6) during all phases by (D.5) and (D.8).
First, we show the following lemma, which is subsequent corollary of the Lemma G.3.
Lemma D.I. There exist parameters So. do coo, no such that, if choose
Qg. Fo Fo, Go = (a/2)- Go. where the elements of Fo, Go is (N0,,), and suppose that the operator A defined in (1.1) satisfies the restricted isometry property of order 2r + with constant å S bo. then the gradient descent with step size T7 will achieve
|FG.T - - & min(or/2,a 3/4
(D.9)
within To = c2(1/no,) log( rounds with probability at least 1 - Co and constant 02 2 1, where Co c₁ exp(-c2k) + exp(-(k + 1]) is a small constant. Moreover, during t S To
rounds, we always have
max Fill I| S 2V01
(D.10)
||U, - Vvll S 4a 40526+101
3/2
(D.11)
Or
3/2 3/2 824+10 log( (os(/o1/1tt
J|l < 0
(D.12)
Or 3a 2
13a² 2
12 A
I
(D.13)
Proof. Since the initialization scale a < ((1o)) Eq. 10), Eq.(D.11), Eq.(D.12) and Eq.11.13)
hold for t' 0. Assume that (D.9). Eq.(D.10), (D.111,, (D.12. and (D.11. hold for 1' -'=-11
Proof of (D.)). and Eq.(..
First, by using the previous global convergence result Lemma G.3, the Eq.(D.9) holds by 2//50//10 7/10 /2 because OO.5////000/0///////////// /o / OkT Vor). Also, by Lemma G.3, (D.10.)) holds for all E [T].
Proof of Eq.(D.13)
Recall A, U, + J V,V, K, Ki, then for all < To. we have
< |AAl-
250 4o S 20g log( / no /no) = 200c2yKo log( Voi/na) S a²/8.
The first inequality holds by Eq.(). and F.F.G. Σ1| < | + ||>|| S 50 The last inequality uses the fact that 1) O(a² kof log (o((/i//na)) Thus, at / To. we have Amin (Ar.) 2
'Ntt that in Soltanolkotabi et al. (2023), the initialization is Fb = a Fo and Go = a Go. while Lemma G.3 uses imbalance initialization. It is easy to show that their results continue hold with this imbalance initialization.
31

---

Published as a conference paper at ICLR 2024
Amin((u) a2/822 2 a2/2 - a2/8= = 3a² /8 and A I || + 3a² /2/8 13a2 /8. Proof of Eq.(D.11)
Now can prove that ||U - V| keeps small during the initialization part. In fact, by Eq.(D. and Eq.(D. we have
1lU4+1 - V++1)1I
< 11U; Vall| - -1/ (V, V; + (.)1I +/|||lll] + V. - K2 Kill
41822++1 |.... =| max (11 || [|
< (1 - IU, Vi + 2nja 2 + 47022+11 [|| + ||_]]] 2
< (1-woa0 no-,,, V. + 2naa 2V + 40782841-0 3/2
The second incquality uses the inequality (D.6), while the third inequality holds by max (1l ||, S 2. Thus, since a = 06824+110 3/2 /ar), we can get I1U Voll s 4a s
3/2 If | Vill 4a + or 4a + 40 0
40 82x-101 3/2 we know that
or
110-1 - V++1l $ (1 - n1,,)
40 4a
82 02 3/2
+nna² Voi + 40md24+1 3/2
Or 40
$ (1 n1r))
4a
5241107/2 3/2
4no,a + 82k+10 3/2
40 or
or
< 4a +
40
6284101
3/2
Hence, ||U Vell S 4a + 10 1
3/2
for t S To by induction. The second inequality holds by
== 0 (T)) Proof of (D.12)
Now we prove that Jj and K2 are bounded for all t < To. By Eq.(D.3) and max Fill, ||G.1l] - 2 denote C2= = max 32} 2 32, we have
To-1
|3, - |oll| + t
Σ t=
max [G.Il) 2628+1 [[ +|]])
< | + nTTo 200 3/2 826+1
S || + 20cz log( //, / [
0 3/2 /or)
< 2a + 20c² log( /o
3/2 / (rr)
2a + C2 log( ( Voi / (a)/ 01 /rr).
3/2
Similarly, we can prove that |KT S 2a + C2 loiogoovinaaa(bbx. proof of (D.11).
o 3/2 3/2//r). We complete the
D.4 PHASE LINEAR CONVERGENCE PHASE.
In this subsection, analyze the first phase: the linear convergence phase. This phase starts at round To, and we assume that this phase terminates at round Ti. this phase, the loss will converge linearly, with the rate independent of the initialization scale. Note that Ti may tend to infinity, since this phase may not terminate. For example, when = т. we can prove that this phase will not terminate ($E), and thus leading linear convergence rate that independent the initialization scale. In this phase, we provide the following lemma, which shows some induction hypotheses during this phase.
Lemma D.2. Denote Me max{ EII, |UKK, 11. JJVV [I). Suppose Phase I starts at To and ends at the first time Ti such that
Mo < (1770182441 + Je
(D.14)
32

---

Published as a conference paper at ICLR 2024
During Phase I that To S $ Ti, we have the following three induction hypotheses:
max [|[]l] S 2
(D.15)
| - Σ 0r/22.
(D.16)
max(ll K+ll)> s 1
1/4
2C2 ( x² vovo voi
(D.17)
7 1 A
a²
(D.18)
The induction hypotheses hold for = To due to Lemma D.I. Let us assume they hold for t' < t. and consider the round t. Let us first prove that the r-th singular value of U and V are lower bounded by poly(ar, 1/a1) at round I, if (D.16). holds at round I. In fact,
2/01 ou( 2 o, (u(()r 2 (UVUT 0,/2.
which means
o,(U) 2 0,/4VoT
(D.19)
Similarly, (v) 2 o,/4vor
Proof of Eq.(D.16)
First, since |U--V Σ|| S 0,/2,, by (D.11. we can get Gr
oi or 2
(D.20)
4V0i
Define M, = = IU, II. ||
||] By the induction hypothesis,
max IIl, 1 s 2
1/4 + 2C2 log( max || ||,,I1 2v
3/2 /o,))
Then, by the updating rule and C₂ 2 1, we can get
U, U.K, - 1 - - + m/ UU-VV
+ J A+:
(D.21)
where A, is the perturbation term that contains all O - Σ)) terms and Ovr²) terms such that
|| < 4np22+11 F.G.T - E max (| | + 817 I.G.G. E1 max (1 [G.13]
+ n² max [[]] [| | Σ||
4n F.G.T >3 max [[. Snj" |...T 21| 50, 44
+ 1 160 FI.GG Σ||
S 4 + || ||)40 + na (32 + JJ- II)
Using the similar technique for J.V,T and U.V.T Σ, we can finally get
M, < 1 no?
M + 2n 1-1 2 ma
160
+ 4nj2x
(3Mr-1 | 4a + + || k(
no?
/// /0,,
Mi-1 27 2
166
+ 4n82k+1
(3M, 1 + || 4o + 2 + |1 ||--1K(T11)
?oo
M,-1 + (VOTT (a+ log 3/2 //.////))///)))))))) M,-1
160
+ (171)010224 + J
<
1
Mr-1 (1710 [I- [ K,
(D.22)
320
33

---

Published as a conference paper at ICLR 2024
The last inequality holds by 82k+1 O1 3/2).
and
0 1/2
During Phase 1, we have
Mo2M,-1/6A0 2 (1710) 828+1 + ||1- 1 KT
then
Mr - 1 n Mc-1.
(D.23)
640
Hence, | 2:11 S M, Mr. 2 P G/
2i S d2k+1.
Proof of Eq.(D. Now we bound the norm of U, and Vi. First, note that
|I(U, v/) || - (1 - 1 1| + n 2a 2/11 + 40n d2k+1 01
3/2
Hence, |U, - Vill < 4a + 4052x 3/2 /o, still holds using the same technique in the initialization part.
3/2
Thus, by the induction hypothesis (D.11. and a 2 52x+1, we have
201 2 01 + 62x+1 2 | + UUV.
Σ|| 2 LUVV = V1VV T + +U, - 1VV,
VVV - 11U - VeIllvG
2 |111 - ||Val 44 + 4052x+10
Cr
2 1/ [[all-
Then, we can get ||V|l $ 2 Similarly, || < 2 01.
Proof of Eq.(D.17)
Since during Phase 1,
o²
S M, JJ S M 64a, (170 (170,8222 - +
1088x2 + 14,2
by 828+1 < 1/128 and (D.23)..
|...G. - Σ|| S 4 maxx [| I], M,] S 4M, max {1, 1088x + 64a2n/o0
1
S Fr, Gr, Σ|| (1 no? /o///440 /640z) TTTo /110888 22x+1 64a2kk/00 (D.24)
Thus, the maximum norm of Jr, K₁ can be bounded by
| < 11. + 2n 20n-2//100 2V0102441
|...G - Σ||
< 2a + Colog(Vo
3/2 //2)/r)) + 1088 2 + 6442k/0,
4n /
Pr Grg - El
640 no?
-/ /0r) + 6
= = + Ca++Ccool
Fr Gr, El
4x20?
3/2 (0,) + 1/2 9/4
< 2a + (iio((/T//n))Baaa.
01
4x2
< <2/00 1/4 + C2 log( log(
x2 %oi
22 1/4 + 2C2 log( / (028+1 x²² Voi).
The last inequality uses the fact that 2a vony/a 2/00 1/4 2C2 /o 62. voi). We complete the proof of (D.17...).
S 2 by a O(vo)) Similarly, |[]]|| s
34

---

Published as a conference paper at ICLR 2024
Proof of Eq.(D.18) Last, for t [To, T2), we have
Ti
A - Az -
Σ t=To
2(1
FF..G -
-11
max Fell, |G((1)
1707
((t-
- 2n
Fro GTa -El2
Σ
40
1601
t=To
1601 ?oo
s 2n/² 250
40
< 3200m
s a²² /8/
where the last inequality arises from the fact that 17 - 0(a/((03))) By 8
I AT, I 13a² I, we 30 IS
8
can have || < 13a² /8 + a²/8 < 7a2/4 and Amin (A,) 2 382/8 a²/8 8 = //24 Hence, the inequality (D.18)) still holds during Phase 1. Moreover, by (D.24), during the Phase 1, for round 2 0, we will have
IFL4T,GGTT Σ|| S FI, GI, Ell (1 no0,/000/)))) /(10//1108811 6 82441 + 64a2 k/or)
< Fr GT.
Σ|l (1 - -nnoo/4/000
or
64a
S or
(1 /64//) or
2
64a2k
of - no-no////00
(D.25)
128a2k
The conclusion (D.25) always holds in Phase 1. Note that Phase may not terminate, and then the loss linear convergence. We assume that at round Ti, Phase terminates, which implies that
MT -M17-1/640, < (177,18244 + I1) K7, K7
(D.26)
and the algorithm goes to Phase 2.
D.5 PHASE ADJUSTMENT PHASE.
In this phase, prove U V will decrease exponentially. This phase terminates at the first time T2 such that
8a² Vo2 + 1-4822411 /oi IT. -17, all
||T - VT--1ll
(D.27)
dr
By stopping rule (D.27), since Ollog(Va,/a)//mg rounds, i.e.
||T; Vi s O this phase will take at most
T3 - Ti =
(D.28)
We use the induction to show that all the following hypotheses hold during Phase 2.
max(]]4i-.ll, ||, - 2
(D.29)
M. (1088x* 6 (ooaa/////,,)lll 1/4 + (2C2 + 16Cs) Vosl/////a)ae x² Voi) S
||,K,
(D.30)
max(()r-11,, < 2/00
aa/4/oi
(D.31)
not
JJ. || 5 1+
|J 1J.-KKT-11
(D.32)
1280,
IU. V/ll < (1 n1,,
U, V.-
(D.33)
30
29a
1 A <
(D.34)
16
16
35

---

Published as a conference paper at ICLR 2024
Proof of (D.31) To prove this, first assume that this adjustment phase will only take at most Ca(log(a)/noa)) rounds. By the induction hypothesis for the previous rounds.
[| s Jn +
Σ noa++1 II& Ell
$ 22/00 2C² log 2022oo(/V///aa(bur ///2/.))
/a,) + n62241 |E..] 2:1
22/00 14 2C2 log Lo
07 /o + C3 (log(Voi//a)) 1822411 411 K 01
$ 22 1/4 2C2 log
3/2 /. + +Cs(log(VT/nne))/mg n7224116600 1601
22/00 1/4 (2C2 + 16Cs) log( (ooll(Vo//aaaa)
o lo+).
Similarly, due to the symmetry property, we can bound the | using the same technique. Thus,
max (1 [K]]] [|all ///0 + (2C₂ 16C3) log( / 3/2
2/22/0,1 /a,)-
Proof of (D.30) First, we prove that during t T2),
M, S (1088x 62441
s [|,K "
S 4an 1/2 + 8264101.
(D.35)
in this phase.
Then, by 62x+1 I ((L//oo(VVT//noo)t and a - O Vo1). choosing sufficiently small coef- ficient, we can have
= -1-1- -LU
+ -rw. K Kr KT_
UKK Vo -J,U U,K, + C,-1,
(D.36)
where Ct represents the relatively small perturbation term, which contains terms of O()) and O (17²).
By (D.29), we can easily get
C.-1 2 (4n662+1 11 1142-11G1111 - Σ1 40,)
(D.37)
Thus, combining (D.36) and (D.37), we have
|JK, |
2 ||1 - 1---- |1|/ nK,, K,] 11 41pMe11 40
4n022+1 Jr Kr-1 20, -7" 17640
2n max (1x - 16 1088
10887)*6244100
6244101
1024na"n* 8172211 0z) |J-iK,
no? ||
1
1280
The second inequality is because M,11 < (1088x 28 + 64a22/00,)177-133 and the last inequality holds by (D.31) and
824+1 0 0(x
(D.38)
Then, note that by (D.22), we have
goo
1
M. + (17701ō2e41 + )|a [[]]J_KK,_]
320
36

---

Published as a conference paper at ICLR 2024
Then, by M & (1088x²82t:4 + 64a2k/o,) have
[|l-)1lJJKK11111 and denote L 170,82x44 + +
M4 1
M--1 +
(1770 + 1-
32
no?
+ 64a / ) 1
3201
no?
64LK
| + m
3201
Or
64Ix
2nL
||1--181-111
Of
6ALK
2n1.)
1/11)/111111 ) |J.kk
1280 (1--1280)
no?
Or
64LK
|Jrk ||-
or
Hence,
M, s 64L |J S |J,K711
or
for all t in Phase 2. The last inequality is because 82k+1 (1/ks² log( /oi/n))) 826+1 I O11kk² log( (oinaa)) and (a + b)2 2a² 2b we have
Moreover, by
| S | S (2V00 + (2C₂ + 16C;) log loolll///////lo Voi/na) x² vo,)²
(D.39)
S 4ax* 0i + 8244101.
(D.40)
We complete the proof of (D.30).
Proof of Eq.(D.32)
Moreover, by the updating rule of J, and K,, (D.36) and (D.37) we have
1 |
$ - J
(D.41)
4 . 40 + 47722 || KT 20
+ 4n 64L
< [
|| KTT :40 + 8111 62x || KTT
= -I ill + 1 1024L + 80 62x+11.
The last inequality uses the fact that || & Voi/2, 2, Ki-- I
VoT/2 and M 1
G4LK || ||. Now by the fact that L 170,020+1 + a² of
= =0 oikz
we can choose small
constant so that
of
o² 80, 82x02 S
o
oo/
1024Lx2
<
384
38401
384
Thus, we can have
J,KK || S | (1+
no? 1280
We complete the proof of (D.32)
Proof of (D.33) Hence, similar to Phase 1, by |,U, Σn < Me < 4ax + 824-100 and
| Vill $ ||,,, - Vz, |l < 4a + 4060
we can show that
ma [[ll < 2
37

---

Published as a conference paper at ICLR 2024
Also, consider
U--V. Ve
= -1- - V, Vi K, (U) - - VVA
+ (EI - - + (2 -)
- (E1 (Fe-IGI-1 E)U1-1 + Eg (Pe-IGT-1 E))(-1)
Hence, by the RIP property and - S 2 ((D.34)), we can get
II(U, vo) (1 n1, ( Vi-1ll + 2ma 2 + 4nd22+11 2 [| - E||
$ (1 n1 n V/-1ll + 2na² 2 8np22+1 voi -T-4)---KK
2 + 32ndd2+11 I (1 - 2nja²
+
Vol ||-11
Since
8a2 201 + 6422x+1 Vobl----oll---
1 Vi-11
0r
for all in Phase 2, we can have
I V S (1- - -V--l
during Phase 2.
Moreover, since Phase 2 terminates at round T2, such that
||T V/2- S Sa2 Voi + / KKT |l|
Or
it takes most
Cg Cglog(Vo,/a)/1o =
(D.42)
rounds for some constant C3 because (a) (D.33), (b) and U. Vi decreases from 11 V7; || < 4 4 to at most |[U, Vz₃ A(a² /or/o,). Also, the changement of A, can bounded by
T--1
ll 1
Σ 2(1² [F... - -112 .4r1)
T=
$ 2(7)) 1000 (T2 Ti)
< 2mn²) ) 1000 C3 log( (og(vo//na))L//p))
$ 10Cs log( (osVVo/nn))(nnd)
< a² 1/11..
The last inequality holds by choosing n S a² (aap:ingnaa///0CCa00aaa0 002/160CyKo} a²/4 a² /16 30² /16 and || < ||Ar, + a² /16 < 7a /4 + a² /66 < 29a 2/1 Hence, inequality (D.6) still holds during Phase 2.
Then, A (Ag) 2 Amin Ar, a² 22/162
D.6 PHASE LOCAL CONVERGENCE
In this phase, we show that the norm of Ke will decrease at a linear rate. Denote the SVD of U, as U, = A,E, W, where E, E Rr W, E gr and define W E (k--r)xk is the complement of W..
38

---

Published as a conference paper at ICLR 2024
We use the induction show that all the following hypotheses hold during Phase 3.
max [ell || 2 \ + 82k+1 log( (oe(/oiina))... -n² Vo1) S 12
(D.43)
64LK
Mr v
| TI S |,
(D.44)
Or
1+ not
| $
|
(D.45)
12801
8a Voi + 64022+
Vo J,K,
It, V. <
(D.46)
a²
I A, S 2021
(D.47)
8
| $ 2
(D.48)
14,, & [K,W, (1 na?
(D.49)
8
Assume the hypotheses above hold before round f, then round t, by the same argument in Phase and 2, the inequalities (D.44) and (D.46) still holds, then max(|]U [[V]]] < 2 and oin) 2 0r/A/oi
Last, we should prove the induction hypotheses (D.43), (D.47), (D.48) and (D.49).
Proof of Eq.(D.45) Similar to the proof of (D.32) in Phase 2, can derive (D.45) again.
Proof of Eq.(D.48)
First, prove (D.48), note that we can get
M 2 U K.l = 11
|KWW |0,
K,W, 1l
2 o0)(U) 1K,WT
4
4VK
Hence,
64 LVF
32Lx3/2 3/2
32L
|K, 4VRM/VO
|J,K.
|
Vo S
|K&ll-
or
5/2
Or
(D.50)
Thus,
| |K.W I.WWW II
K.W. I. 64L |K,]l or
< K.W. + 2 |Kll |||
The last inequality uses the fact that 82841 ((03/o9) Hence, |K,W,, 2 ||K|]//, and (D.48)
holds during Phase 3.
39

---

Published as a conference paper at ICLR 2024
Proof of Eq.(D.47)
To prove the (D.47), by the induction hypothesis of Eq.(D.49), note that
| Anll $ 2112
F.F.G. - E11=401
M=T2
2n)
160 [| 11
1'=12
$64am
||e||2|KK> [r 11
P==Tz
< 64 of
01, W T2
11, 1/02
(D.51)
512n a²
||rr 1|
1281 a²
01
2 /16.
The (D.51) holds by the sum of geometric series. The last inequality holds by n S O(a Then, we have
29a²
a
A < || || + || AT, S
2a²
16
16
3a
a
a
Amin
(At) Amin (Arz) 1. Ar,
16
16
Hence, (D.47) holds during Phase 3.
Proof of Eq.(3.43)
To prove the (D.43), note that
2 S 10 log(Voi/na) o0 ||K||| < 2| 2|, W 11 On the other hand, by A, S 2T 7, we have
3/2 /o.). (D.52)
W J,W,T1 W K.W.W. W. V. S 2a² 1.
Hence, denote L. = 1 I1 S 01/4
W WT J.W.T1 S <2a²1 W. W.LKK K.K,TKWWWW... W V.W.W.
2 + W., K. K.W., + WV, U.) U,) (V. - W,,,
Sa² V0l + 648 Vo
< 20"1 + W KJ K.W.I+ +
1
Wi, K. K.W. + (2a+
8a² Voi + 64822+1 VoLLi
I.
(D.53)
Also, by inequality (D.53), we have
J.WW I.W.L 1|2
JMW I..WLII
I... L I.WWI.I
(2a + Sn² Joi +6482 I
2 K, WT L. + IMW.
K2 WT
2a + 8a² 4 LVoTL
d+
J!&.W W.W.W !
40

---

Published as a conference paper at ICLR 2024
Thus, by L, S 01/4, we can get
8a² 8a²voi +6482k+1 VOLL
| S W[ 1,1 || + 2a
or
- |TT || + 2a + 8a 802 + 64d2x+1 Voi
Of
- _0(2//0)) 1/4 + 82x+1 log( (oo //0//no / n vo1).
The second inequality holds by [|K,W, - |KT WT, 1, S | ||. On the other hand, note that
|| - +W
< ||JUU, $1J,U, [10,,()+
x (VVill//,UUU++1111// -
- Mi/o,(U) [ (1, vo))l/o,(U) + |
64L |
AV + ||
Sa² Voi + 64824+1 [.
4V0i
K,
+ I..W
or
6401/2)
3/2
32a 2 01 + 256d284101 .0
.Voit
|| + |.W
o7
o?
$ 2 J + IJ..
(D.54)
The last inequality holds because
022+1 OOx=" "Vo""loo""V"/nnoa) (Voi/nox)), S O(ar/vor))
Hence, by the inequality (D.54), we can get
|elll s 2| 0(2/a0) 1/4 + 82 log(Von/na) x2 Vo1).
(D.55)
Thus, (D.43) holds during Phase 3.
Proof of Eq.(D.49) Now we prove the inequality (D.49). We consider the changement of Kg. We have
KG+1 = Ki(I-KIUU0 K, U. Ex - E)U, + EA - -)),,
Now consider K2+1W. (,1. we can get
K,t Ki(I w,W E J. J.W. + - E)UWT + +EE EJJ.T
= K.W.T - nK.J, J.W. + ME((FGT - EJAWI
K,W.T W.W.W. J. J.W._ K,WWW W.J. J.W. + F. - E.J.W.L
Hence, by the (D.50.
64mTA3322
[[441 W.,. & IKWW.IC. (T WW J.W.DI
[|
IJ.W. ||I 4no M, J.W.T.
3/2
< (KWW 1 JWW.DI
|| || -IWW II
3/2
+ Il JJ,K, J.W. II
0f
< IK.W, nW J. J.W,T)I + 80
o, J.K. II [|AWILI
The second inequality uses the fact that 628 S 1/16 and (D.50). The last inequality uses the fact that ||]l]l /01. Note that Xmiu (A+) a² /8 T, then multiply the W.L. can get
a²
Wi, J. J.W. - W., V. V. W..1 KJ K.W.
I.
8
41

---

Published as a conference paper at ICLR 2024
Hence,
W W J.W.L W W W.L.KKWW.... a² .. 8
Thus, define Φ: 1 J.W.T Wa, W...KTKWW. then we can get
S [K.W W. JWIII 80L*2
[[
71 WT
| || (J.W
80LK²
$ [,W E (T W.LK K.W,LL no))ll +
or ||&KK] [1.
Define loss Le = |J,K, TT ||. Note that
L. ||
WI W. KT + J.W, J.W.I
S IIJ.W W., K, 11 + IIA.W W.K,
6/Lx3/2
= I| W. K. +|+ Voi
|| T
(D.56)
03/2
Le 2
< I. W K2
The Eq.(D.) holds by (D.(0. and [ = 1, and the last inequality holds by dor41 = O(n²).
Hence,
J.W. T 11 W., K. 12
(D.57)
Similarly,
W W. KT 22L
(D.58)
Then,
160mLx2
[| W.Ll & [K,W - W KT K.W.11 - -)or
[| N.W.WWWWKK W|
If [] t,1 < 10ka, we can get
160mLk² [[ WTLl < (K,WL W. KJ K.W.1 16)1
J... W. W.ekk 11 1I....11
of 160mL
< I.W. W.W - W,, KT K.W.T.
1)0:)
W II 1IM.
n02
160
+
J.WW W KT K
8
Or
na?
160
< I..WWLL IIl-
20
8
Or
na
< |.WWLll
(D.59)
16
W.I.WW.LI
< I.WWLlI-
(D.60)
1600x²
by choosing 826+1 S O(x~5) Now if J..WT || 2 10ka,
JT J.W. - W. K.W. W.,J J.W. 2.1 - -W.KK K.W.T s 2a² I We,1 (U, - -1) (U)) V.
- 1. W.L.KKKWWWW V.W. S 22a2.1
42

---

Published as a conference paper at ICLR 2024
Hence,
If [, 2 10ka, then
1 J. J. |..W, =|,,,
< [ K2 K.W 11 + 2x 2x+ Sa²vo, + +64824+100
Or 8a² Naivoi- +
|| VV 2
$ k K.
2a
or < [ KI KW I1 (10a + b 1I)
& [ KJ K,W.L (1/10k 64822+18). W 11
$ [ K, K.W,ll +| + (1/2) (11/2)_[J.W...1. II..W,
Thus, |K,W 11 2 |JWT 1 11/222/222 2 |
160mLK²
[[ WT V |K,W w,, K2 K.W.1 n))1)l
J.W. C, Wt, K. -I..WW
Or
160mLk
S |KKW w,W KJ K.W.L 1101)1
W.:. W KIJ| 1IW.
Then, if we denote K' = K.W.TI. then we know (K'(1nn(K') K'Il S (1 (1-17 ( ||||| Let
K' = A'EWW'
((()- = - (C (X)"
-|E' (
Let Ee = Si for i < then E'(In(EE)));: = C n--n then by the fact that Ci - (K.W., S 1.
we can have (i n/ maxisisi 4i 77, and then
|E(I n 7/ ,|]
Hence,
1.0 J..W f, Wt, K. I| IJA..
[K WT |1 S [.W.. (I W7, KJ K.W.T. - 76.1
Or 160
< K.W (I W/ KJ K.W.
J.W. Wt_ KT I.W.T
Tr
(.W.L.I 11
160m Or
< [.WWWLII
J.J.W T (.1
KK KJTI -I
W.W. 1 1
160m
< [.WWL.I
J. T
f, II K. I.I.W.W
8
Or
W 11
< J.W/
1
(D.61)
16
< JKWWWLI (1 Ann²a?)
(D.62)
The fifth inequality because 8 O(K Thus, for all cases, by (D.59.))) (D.60), (D.62) and (D.61), we have
{11 na²
| WT II
K.W. II min
1
1600R²
(1 na²)
(
wll.eW.T1 112
K.WWT
(D.63)
8
3200k²
43

---

Published as a conference paper at ICLR 2024
where we use the inequality max(a, b} I Vab. Now prove the following claim:
[ W +-1,1 - KKK++WW,11 |l (1 01 ///////))
(D.64)
First consider the situation that |,,,,, 1,1 S 10ka. We start at these two equalities:
K K4+1 W W1 + K441W, W
K++1 = K441W, WH1, + K4t1 W 6+1 W4+1-
Thus, we have
W WT W WT (41. K W,W 141. K4t1Wi1.
Consider
411,1 || = W I
[1+1.1 U. (U12,
W U ) 1/21|
Wett,
|1| - -Uel (U)-
4 17- 17(2Vo1 -M, + 282x+1 (L, + 3M) 22
Or
4 1] (3Voi MM + 2822+1 TT))
Ør
Vool .n( 48L
| + 2 00822+11 L.)
I Cn(ō24+1n + Or
Or / [o))]] ||.
for some constant C. Also, note that [|F,CT E|| L, + 3M, S 4Lc,
|| W,T = [1(K++ - W.) || ||K,WTTI
$ IlnK,UU, U,+ WT |I + + (4L.) 2V + |,W,TT
6/T
< InK.J J.W, 8/omdaa L +
L
3/2
3/2
I 2n4, 8 011024411 L. + 3/2
L1
6/2x
L. (n Voi + 0 +
3/2
or
1
4Voi
1
|K,
4
and
|K WT 1
2 | [[(K_ - K.W..II
[gll - //l K,U, U, J. WT || - 8 Ia
K+]|
1/ 011022411 Lr
> ||4& 2 1ll (J.W. Svondd2441 (|
N | 2 1J01 8112x-1011)
N |elll
> KKt1 W.
44

---

Published as a conference paper at ICLR 2024
Here, use the fact that 77 - 1/01, 62k+1 I 1/32 and ||ll & Vol. Hence, have
Ke+1 W
& || K W - + [| W W1lWW,W
< K i W. w + W ال-ي Cn(62x+115 K² + a²xx² x²/ /o,)),))
< (1 + Cn(62x+1n a² /o,0/o,,))))))) or Lc) 1 II
< (1 + 2Cn(62n+1n
a o Wl W I1) [| W - (1 + 2Cn(52x+11 + a22 ar J.W. W Il) [ W.
The inequality on the fourth line is because (q.(D.))).
Note that
W W J.W. W K.W.T1 2 a² 1.
8
Thus, WKW,W, 6, 11 S W || and
K4t1 1 & (1 + 2Cn(62c+11 + 022n2/ /o)/// IIl K, [ W.
$ (1 + 2C7(52k+1n + a²22 3////o [/.]ll, (
(D.65)
By inequalities (D.63) and (D.65), get
Ke+1 i1
< (1 + 2C1(024+1n /12//,))]//.... [
naa² (1-ma²) (1 (1-")
www...... 112 112
< (1 + 2CCn(02x+1nn + a² /,
I.K.W...
3200k2
na² K
The last inequality is because
WWW.WWW.. 1|
2C 2Cm(62M41n6* + 1| 1
3200k2
by choosing
-2k+1=0 = 0(
(D.66)
and
a= 0 vor))
(D.67)
Thus, we can prove J.W. 6,11 decreases at a linear rate.
Now we have completed all the proofs of the induction hypotheses. Hence,
F.G.T. - Σl| s 2 II
< 4 K || Voi
S K| W. Vl
t-T,
170
S <4|,WW T.
Voi
8
na²
t-Ta
< KTyl Voi
1
(1
n
t-T2
s 20
(D.68)
Now combining three phases (D.25), (D.42) and (D.68), if we denote tž To = T T' ((1/no,), then for any round T 2 4T', Phase and Phase 3 will take totally at least T" rounds. Now we consider two situations.
45

---

Published as a conference paper at ICLR 2024
Situation 1:
Phase 1 takes at least 3(T-T)) rounds. Then, by (D.25), suppose Phase starts at To rounds and terminates at Ti rounds, we will have
of
n0?
Ti-To
[F, GT - -E -
1
128a2 k
64
of
?1?
T/2
1
(D.69)
128a
64
The last inequality uses the fact that T 2 47 and
3(T T
T To 2
4 2
T/2
Then, by (D.32), (D.30), (D.44) and (D.45), we know that
|| || - Σ|| - J1
T-T:
s 4 KJ.
-Vll
1
1280
T-7;
s F4 G...
Σ||
1
1280
T/2
no?
S FT, GT,, -;|
|+
(D.70)
128
The last inequality uses the fact that Ti Then, combining with (D.69), we can get
To >
3(-T7"
>
T T which implies that
2
2 T - Ti
of
T/2
170
T/2
G Σ||
S
128a2 K
64
1280
o²
T/2
(D.71)
128k2
128
o²
na² 2
T/2
1
(D.72)
128a2
8
(D.71) uses the basic inequality (1 21 x) S (1 - x), and (D.72) uses the fact that & O(x vo,) (KKK))
Situation 2: T2. we have
Phase 3 takes at least T-T" rounds. Then, by (D.68), suppose Phase 3 starts at round
T-T2
(1
naa
F. - Σ1 < 201
8
(T-T')/4
na?
< 20
[
8
T/8
a²
na²
1
(D.73)
128a
8
The last inequality uses the fact that a O(x Vo.)
0 (o)) and T-T' > T-T/1
4 > T/8.
Thus, by [ - 212 < n [[ - 1 we complete the proof by choosing 47' = (1) and
G7 1/1282
46

---

Published as a conference paper at ICLR 2024
E PROOF OF THEOREM 4.3
By the convergence result in (Soltanolkotahi et al., 2023), the following three conditions hold for t To.
max[|]J+]|, [K.Il s 0 2a 028+1 3/2 log( ////na)
(E.1)
0r
max[||U;]| [|&l|| s 22/01
(E.2)
and
|P. - |لل < a 1/2 o 3/4 S 0r/2.
(E.3)
Then, we define M, = max - | 11. [| 1|, by the same techniques Section D.4, if we have
o?.Mo-1/640 2 (170)624+1 + a aa))lll--1k2
(E.4)
we can prove that
Mr Mi s (1
no?
M--1-
(E.5)
640
and
max [ s 2/ 1/4 2C2 log( log( :2VoT voi
||..T - Eل| s 0,/2
max [|x(|]UUll.IVVV]] 22101.
Now note that
|| K 2 Amin (UtnUU))))))))) (U1-1)-||KTTI)) (U,-)) |K 4V
Or |K11ll1,
(E.6)
Now since d2s+1 O and a O( 1 Vor) are small parameters, we can derive the M,'s lower bound by
M 2 |
2 Or
||
4
2 or
|i-ill
|
(E.7)
4/01
Vol
170,02841 + a
> 640
(E.8)
o7
Hence, (E.4) always holds for 2 To, and then by (E.5), we will have
I-To
1707
M, <
1
MT.
16
no?
t-To
1
FT, G
1601
(1
no?
1-Tb
2
160
Thus, we can bound the loss by
|.G.T - اا| < |,..V. Σ|| + IIV.V || [
+ |J,KT] II
< 3M, + I,
4/01 Me
< 3M, + O(2a + 82x+ / log
ar
< 4Mc
(E.9)
< 20, (1- 1102
t-1
64
47

---

Published as a conference paper at ICLR 2024
where (q.(E. uses the fact that 62k41 (xx 2log ((Voi/na)) and 2 O(a,/Vol,) Now
can choose 7(2) 2To. and then by To t/2 for all t 7:22, we have
|FG. - Σ n|| F.G. E|1 S 2mo, (1-
noo
T-To
S 2n (1-
no?
1/2
6401
640
(E.10)
We complete the proof.
F
PROOF OF THEOREM 5.
During the proof of Theorem 5.1, assume B satisfy that
max 1 20 2/ / S B S cavo,
(F.1)
for some large constants C7, and small constant cs. In particular, this requirement means that S 0r/4. Then, since AA* GTa - Σ|| 2 I Pris GrOs - Σl by RIP property and further derive [Tr
828+1 S 1/2,
Σ| Frees GrC Σ| 0,//2.
To guarantee (F.1), we can use choose & be small enough, i.e. 7 < 01 so that (F.1) holds easily. In the following, denote 02k+1 v 2k 16.
F.I PROOF SKETCH OF THEOREM 5.1
First, suppose we modify the matrix Fron, Gros to Free and Grey at t= T()), then || Frow I|== Amax ((Fr())) Fr()) 8² and [U 11? B². Also, by || || 2 we get
that |[ S ||Grooo1| (
I ||Grooll Byor is still bounded. Similarly, || |I s 5
||Vros>|| 2 and ||oo S || || 2 is still bounded. With these conditions, define T [|} and P. = max max[[]J.VV [U,V - ΣlI} For || |l. since we can prove Amin ( (F. F.) 2 82/2 for all 2 T(3) using induction, with the updating rule, we can
S. = -max max[[1 (IU,K, [|,,K,
bound ||,+ as the following
||e+1 < K, ||I1 - FF. Fill + 2md28+1 |IF.G - -E| max max UIl I|II
(F22
(1- n1 + (4m62x+18 Pt + 1824+11 [(ll)
< Kg ||
(F33
2
The first term (F.3 ensures the linear convergence, and the second term represents the perturbation term. To control the perturbation term, for Pt, with more calculation (see details in the rest of the section), we have
P+11 S (1- P. + n/l - ((SA1117 +
Soooon+//ooo Voo7') 18) 18)-
(F.4)
The last inequality uses the fact that S, < K.|| max (UU,), |J < |K || S /28 |
Combining (F.4) and (F.3), we can show that P.+ _ K, converges at a linear rate (1 (1-0(n3²)) since the second term of Eq. (F.4) and (F.3). contain d2s+1 or a, which is relatively small and can be canceled by the first term. Hence, F.F.G. Σ|| < 2P, 2S, < 2P, + K, converges at linear rate.
F.2 PROOF OF THEOREM 5.1
At time
2 T(3), we have Tmin (Urga) Vi(as) 2 Omin (Σ) || ViT Σl 2 or 1/2 3/4 22. The last inequality holds because 0(x-0// 3/2 vo,). Then, given that [| 12=
01
Amax ((Fr()) Fro)) = B², we have ||U 32. Hence, by 01 (U)) or (V) 2 o, (UVV we have
(T(O))))) > 0r (UTON Viror)
0,
(I(UT())) 23
48

---

Published as a conference paper at ICLR 2024
Also, by of || s 2 can get
| - ||GTra) III| |ل
||ōToO||
of
$ ||
2
3
B
Similarly, [| || < |V |rss
2/oi and ||
|| K K ||
2
3
Denote St = max[ I1. || I1,, Pt = maxill |l, 10 E}}. Now we prove the
following statements by induction:
P0+ - (1
no? 8,32
Log(voi/ (aa /22/nn2)))22++)) 10 o2 + vao! 7/4
P. + ns O
(F.5)
82
86
1752
141-718)
Σ1| v
00,12
(R6)
of
2
max || || ||} S
401/3
(F.7)
8²
2 S F Fi+1 S 2
(F88
|| < O22 1/4 + d2x+1 log( (og(voi/na) x22 Voi)
2
(F.9)
B
Proof of (F.5) First, since ||F Amax ( (F..) F.) S 2,3 we have || < 283.. Then,
because mmin (U,V) 2 miin (E) |U,VV Σ|| 0, (U) (V 2 (UV we have
(v) (U.V)) 0r
(U,) 2,3
we write down the updating rule as
U - E -1 nL-,U,U (U,VV =)(1-)VVV)) nU,K? K.V," - nU.J. JoV. + B.
where B, contains the (17²) terms and (F, - Σ)) terms
| < 1 Σ) max [|xx |G, 12) + 001 E11² 211f F 20122,111 ||Gr
Hence, we have
||/c+1 ViT1= - 21
< (1 700 VIU.V - Σ1| + + K + JVV J U, 11 ||+++ +BBl
4,2
$ (1 N10
Pt + / |7 + np.
J Uall + |Bll
4
S (1 no?
Pt + SJS:
401
O (2v 1/4 + 62x+1 log(Voo////
12 v2io)) 22 + 1
4
4a
40
+ 41102441 2(P. SS) 40
+ + S.)2 40
B2
< 1 !1?
(
[og(
2f + voo B²
7/4
Pt + n). O
(F.10)
8,2
The last inequality uses the fact that
8² = 2
8zk+1 = (kx-2)
P. S. F.
Σ1| S O < 1/n-
49

---

Published as a conference paper at ICLR 2024
Similarly, we have
|| Villl
$ (1 n JJ (1- - nJK KV - JJ (UVT Σ) + C.
where C, satisfies that
||C.ll - 41 (F.G. ( max || O11 Σ max Frl? |
I 47d2x+1 2(P: + St)
1
+ ( (P 5)) 01 9
3)
g²
Thus, similar to (q.10. we have
Je+1 s (1-
[o0l/////00)bb--11 in2? + vaoi 2/4
P: + ns: o
8,32
82
Hence, we have
n1o 8,32
Pt + n).. o ( (Los(//T/naa)ex:1 + vao,/// 7/4
Pot1 S 1
3
Proof of (q.(F.)) We have S₁ | ma (1 || ||P|| S 229 ||,
So the
inequality above can be rewritten as
no? 8,32
P. + 1728. -||K|| O /1 Vog(Von/naa)) haa/:/n0)0221 022 of + vooi
P1+ 5
1
82
1
no?
P. + m||k|| .0 [oo(/ of + vao? 7/4
8,32
Also, for K1+1, we have
|K++1|| = [| F
Fi)1 + 28 [F, - E| max [|Ub [
11.22
$ [1
+ 2nd22+11
(P. St) v28
2
1132
S (1
+ 27022+1
P. /2. + 21822+11 Kell V23
2
7/32
= || (1
+ 417024+11
: 3., 4,3 : Kel
2
Thus, get
Pat + | K(+1|
n
11.32
< maxx11
2 [P, + [Koll)
852
0 (on(VV///))
3/2 5/4
vaol(t)
+ max
+ 4 82 /01001211
c
(Pr + Vail Kt]])
3 (P: + Kil).
<
The last inequality uses the fact that 3 < / and
8zk+1 S 0(3/Vo, log( log(Vo1/na))
(F.11)
50

---

Published as a conference paper at ICLR 2024
Hence,
Leoos/Va Voi + +(0 (1-1/) 7/82 1-7
| s (Pros/
2
s ( + ||F.G. El//Vor
- O(Vao 1/4 + 82x log((o//aa 12 (2) + +a 1/2 o0
1/4
= =oVao 1/4 +
Vog / na) ) x²2 Vo)
Hence, P: + /oal Ke]l is linear convergence. Hence, by 3 - V01,
[F Σ|| 2P(+1 + 2S
s 2Pt+ + K21l|
$ (2 v23/ (P1) + Voil|Ke+1ll)
$ 4(Pr:: + Voil Il) (1 n/22 (-1-7(()
2
Last, note that by B 2 c7(>2/601
133 and B 2 cd 1/6 x 2//6 01 5/12 log(
(oglyar /oi (T//nxx)//6, by choosing for
2
some constants 07 and c, by choosing large d' and 07 = 20, can get
8
8
Voi
of 3/2 /o,) (2V07/3) -
207
207
and
Pres + Voil + -(TTOOlog(VV////// 01 (22/77/3) S /0/
have
1+1-7(3)
56
1
17.22
|F411 E1 S
(F.12)
0
2
Proof of Eq.(F.) Note that have ma Frca) ll. G ||} I 4
voi/B 401/B. Now
suppose max ma |[3 S 4 voi/ / for all t' E [T{3), t). then the changement of Fit1 and G++1 can be bounded by
[[4+1 - Fres S 7
Σ
FLFFGe - >e]]Ge s n.
86
+
dr
2
40
16,33
+
8a 2
2
11.22
3
01
,3
(3=T(3)
16,33
8a
|G,- Gro In
Σ
Fp
E Fell 5
01
g3
(=)(3))
Then, by the fact that 8 < (0T we can show that
20
16,33
80
40
|| F |l < || Frey + |141
From ||
<
+
+
f3 <
8
σ1
B
20
36
8
< 40
|G++ll < || + [|441 - Gy <
+
+
3
01
g3
8
Proof of (q.(F.8)
Moreover, we have
@+ 2 0x FF(())
Omax (Ft+1 Fr((:)
(T())
F Fr
2 8 16.3
σ1
2 1/
51

---

Published as a conference paper at ICLR 2024
and
1633
| S [[rr))) + [F, Pris || s 33
S V23.
01
The last inequality is because / S 0(0i011))) Hence, since Fi+1 E Ri*k we have
8² S F Fit1 S 2
(F.13)
Thus, we complete the proof.
G TECHNICAL LEMMA
G.1 PROOF OF LEMMA B.
Proof. We only need to prove with high probability,
max cos² 02 log (roo JJEnn]
(G.1)
In fact, since cos² 02 = si - Oz Oz S (T/2 2 Ozgize 2x) )², we have
log(rvor/aa>r ( 2 P cos 0z > 0 ( log log"(rvoi/a)(mm))
Ve
P T/2 - 02y.zall >
(G.2)
Moreover, for any m 0, by Lemma G.I,
(sin( [ m²))-2
PP [|T/2 2 - Ox 02z,20l > m] S 0
-0 (V:: 2(cos m) m))-2)
(G.3)
1/Vk
0 ( VTl(l m² m²2/4)6-2
(G.4)
Vkexp m²
4h
<0
(G.5)
The second inequality uses the fact that cos S 1 - x2/4. Then, if we choose
Ve
log(r Voi/a)rn
and let k: 2 16/m²
16 16log (rre)
can have
P
|coos 0 Ozzize
m²
5 P [|T/2
0 0zyizal ml
(G.6)
m²kk
< 0 eep
(G.7)
< k exp
(-vk)
(G.8)
Thus, by taking the union bound over j, k E [n]. there is constant C2 such that, with probability least 1 (xp(kexp((v// we have
0u 5 log oon"
(G.9)
n
52

---

Published as a conference paper at ICLR 2024
G.2 PROOF OF LEMMA B.2
Proof. Since H; = aa/v Iú, where each element in I; is sampled from (0,, 1). By Theorem 3.1 in Vershynin (2018), there is constant such that
P [ kl 2 t]
S exxp(-ct)
(G.10)
Hence, choosing (1- /2 )h, we have
P1 E [k/V2, ]
111 kl 2/ 2 2exp(-et) S <2xxp(-ck/4)
Hence,
IP || E (2,//222 = IP | E [k/v2, v = 2exp(-cck44
(G.II)
By taking the union bound over i E [n], we complete the proof.
Lemma G.1. Assume x. y 1n are two random vectors such that each element is independent and sampled (0, 1). then define 0 as the angle between I, y, we have
P P((
3 3 n ((inn T 2 m))n
m
(G.12)
2
4/2
are independent and uniformly distributed over the sphere Sn-1, Thus, without loss of generality, we can assume x and y are independent and uniformly distributed over the sphere.
Proof. First, is known that || and
y
T>ıl
Note that 0 E [0, r7. and the CDF of
((0) = T(n/2) sin sinn=2(0)
(G.13)
/TI(-=1
Then, we have
1/ 7/2+m sin Acl0 x/2-m
J0 / sin n- 0d0
P
8- 7
m
=
(G.14)
2
So" sin 2-2 0d0
Jn /= sin n- 0d0
(T 22) ssn"" 2 (TI - ml)
(G.15)
5a -- 0d0
(T/2 (TT/2 12- mm
(G.16)
50 1/2(11 (1 12 12/2)n=22)
(T/2) (T/2 - m
(G.17)
2v2
3/n-2
3 n 2(sin (T/2 m))
(G.18)
4/2
Lemma G.2 (Lemma 7.3 (1) in Stöger & Soltanolkotabi (2021)). Let A be linear measurement operator that satisfies the RIP property order 2k + 1 with constant ō, then we have for all matrices with rank no more than 2k
[|(I A-AA)II & V2k 8||X-|
(G.19)
Lemma G.3 (Soltanolkotahi et al. (2023)). There exist parameters Cor 5gz Cng 9o such that, if we choose a S Co. Fu = Fo, Go (a/3) Go. where the elements of Fu, Go N 1/n), and
'Nte that in Soltanolkotabi et al. (2023), the initialization is Fb = a Fo and Go a Go. while Lemma G.3 uses slightly imbalance initialization. It is easy to show that their techniques also hold with this imbalance initialization.
53

---

Published as a conference paper at ICLR 2024
suppose that the operator A defined in Eq.(1.) satisfies the restricted isometry property of order 2r with constant 5 I ōū. then the gradient descent with step size dj S 7u will achieve
||F,G; 5 7/10
(G.20)
within T (1//na)) rounds with probability at least 1 Co where Ço ei exp(-c2k) (czu))-rt1 is small constant. Moreover, during I rounds, we always have
Fall ||, S 2
(G.21)
The parameters oxg, do and no are selected by
Ck
ag = 0
v
Vk Vr
(G.22)
max 2n, k32
62 / max 2n, (
80
(G.23)
Ard Vr
1
1) S O
(G.24)
1o001
log
2//0m
H EXPERIMENT DETAILS
In this section, we provide experimental results corroborate theoretical observations.
Symmetric Lower Bound In the first experiment, we choose n = 50, r = 2, three different = 5,3, 2 and learning rate // 0.01 for the symmetric matrix factorization problem. The results shown in Figure I, which matches our (11/T²) lower bound result in Theorem 3.1 for the over- parameterized setting, and previous linear convergence results for exact- paaamttaratteei setting.
Asymmetric Matrix Sensing In the second experiment, we choose configuration n = 50, k 4 sample number m 700 s nk²2 and learning rate 7j 0.2 for the asymmetric matrix sensing problem. To demonstrate the direct relationship between convergence speed and initializa- tion scale, we conducted multiple trials employing distinct initialization scales a 0.5, 0.2, 0.05. The experimental results in Figure 1.2 offer compelling evidence supporting three key findings:
The loss exhibits a linear convergence pattern.
A larger value of results in faster convergence under the over-parameteriiztion setting
The convergence rate is not dependent on the initialization scale under the exact-paramettriizaioon setting.
These observations highlight the influence of the initialization scale on the algorithm's performance.
In the last experiment, we run our new method with the same n and but two different &: 3, 4. Unlike the vanilla gradient descent, at the midway point of the episode, we applied a transformation to the matrices F, and G; as specified by Eq. (5.1). As illustrated in Figure 2(c), it is evident that the rate of loss reduction accelerates after the halfway mark. This compelling observation serves as empirical evidence attesting the efficacy of our algorithm.
I ADDITIONAL EXPERIMENTS
In this section, provide additional experiments to further corroborate theoretical find- ings.
I.1 COMPARISONS BETWEEN ASYMMETRIC AND SYMMETRIC MATRIX SENSING
We run both asymmetric and symmetric matrix sensing with n 50, n 4, = with sample
1 1200 and learning rate 0.2. We run the experiment for three different initialization
54

---

Published as a conference paper at ICLR 2024
scales 0.5, 0.2, 0.05. The experiment results in Figure 1.1 show that asymmetric matrix sensing converges faster than symmetric matrix sensing under different initialization scales.
10-1
10
Loss
symmetric alpha=0.5
10-5
asymmetric alpha 0.5
symmetric alpha 0.2
asymmetric alpha 0.2
10
symmetric alpha = 0.05
asymmetric alpha 0.05
5000
10000
15000
20000
Iterations
Figure 1.1: Comparisons between asymmetric and symmetric matrix sensing with different initializa- tion scales. The dashed line represents the asymmetric matrix sensing, and the solid line represents the symmetric matrix sensing. Different color represents the different initialization scales.
1.2 WELL-CONDITIONED CASE AND ILL-CONDITIONED CASE
We run experiments with different conditional numbers of the ground-trus truth matrix. The conditional number 6 is selected 1.5, 3 and 10. The minimum eigenvalue is selected by 0.66, 0.33 and 0.1 respectively. The experiment results are shown Figure 1.2
109
kappa 1.25
kappa= 3
10-1
kappa 10
10-2
Loss
10-3
10-4
10-5
10000
20000
Iterations
Figure I.2: Comparisons between different conditional numbers
From the experiment results, phenomena:
55

---

Published as a conference paper at ICLR 2024
#ghumga
194
LosS 085
Loss
GD. alpha-0,5
Method. alpha-0.3
GD. alpham0.0g -000
Our Mathod. alpha-0.05
Iterations
Iterations
Iterations
(a) Symmetric case
Asymmetric Case
(c) Our new method
Figure 1.4: Experiment Results of larger true rank and over-parameterizze rank k 10.
When the minimum eigenvalue is smaller, the gradient descent will converge smaller error at a linear rate. We call this phase the local convergence phase.
After the local convergence phase, the curve first remains flat and then starts converge at linear rate again. We can see that the curve remains flat for a longer time when the matrix is ill-conditioned, ie. is larger.
This phenomenon has been theoretically identified by the previous work for the incremental learn- ing (Jiang et al., 2022; Jin et al., 2023), which GD is shown to sequentially recover singular components of the ground truth from the largest singular value to the smallest singular value.
1.3 LARGER INITIALIZATION SCALE
We also run experiments with larger initialization scale a. The experiment results are shown in Figure I.3, We find that if is overly large, i.e. 3 and 5, the algorithm actually converges slower and even fails to converge. This reasonable since there is an upper bound requirement Eq. (4.7) for in Theorem 4.2.
10a
alpha=0.5
alpha=
101
alpha
alpha 5
10-1
Loss
10-3
10-5
2500
5000
10000
12500
15000
17500 20000
Iterations
Figure I.3: Comparisons between different large initialization scales
1.4 LARGER TRUE RANK AND OVER-PARAMETERIZZD RANK
We run experiments with larger configurations n = 50, = 10 and r = 5. We use m = 2000 samples. The experiment results shown in Figure 1.4. We show that similar phenomena of symmetric and asymmetric cases also hold for larger rank of the true matrix and a larger over- parameterized rank. Moreover,
method also performs well in this setting.
56

---

Published as a conference paper at ICLR 2024
1.5 INITIALIZATION PHASE
If we use GD with small initialization, GD always goes through an initialization phase where the loss is relatively flat, and then converges rapidly a small error. In this subsection, we plot the first 5000 episodes of Figure 2(b). After zooming into the first 5000 iterations, we find the existence of the initialization phase. That is, the loss rather flat during this phase. We can also see that the initialization phase is longer when is smaller. The experiment results are shown in Figure 1.5.
alpha 0.5
beta= 0.2
alpha 0.05
Loss
10-1
10-2
1000
2000
3000
4000
5000
Iterations
Figure I.5: First 5000 episodes of Figure 2(b)
57


Reviews:
[{"review_id": "xCTvIYW1fR", "reviewer": "Reviewer_MU8J", "summary": "This paper provides several new results for over-parameterized matrix sensing. First, the authors rigorously prove that with a symmetric parameterization, over-parameterization slows down GD.  In particular, they give a lower bound rate of $\\Omega(1/T^2)$. Second, the authors also show that with an asymmetric parameterization, GD converges at an linear rate depending on the initialization scale. This is in contrast with GD with symmetric parameterization, which has a sublinear rate. Finally, the authors extend their algorithm so that the linear convergence rate is independent of the initialization scale.", "questions": "In Theorem 1.3, the convergence rate depends on the initialization scale $\\alpha$. This is also observed empirically in figure 2b. In practice, does this mean that small initialization has no advantage? One could just set $\\alpha$ to be large to ensure rapid convergence?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Overall I think this is a good paper. The fact that over-parameterization slows down GD for matrix sensing has been observed by quite a few previous papers. However, this is the first paper that I'm aware of to rigorously establish a lower bound. The authors also show that with asymmetric parameterization, GD converges at an exponential rate that depends on the initialization scale. This is somewhat surprising, given that the asymmetric case has traditionally been considered harder due to potential imbalance of the factors.", "weaknesses": "My main concern is with the experiments in this paper. I think the paper could benefit from a more thorough experimental section, perhaps in the appendix. \n\nIn 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?\n\nAdditional experiments which 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. 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. \n\nIn any case, i would like to see a more detailed comparison of symmetric versus asymmetric parameterization, even just using synthetic experiments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "bG0kbuMo9b", "reviewer": "Reviewer_Z4Yg", "summary": "The reviewed paper is a theoretical investigation of the convergence properties of gradient-descent, and other first-order based methods, for over-parameterized matrix factorization/sensing for symmetric matrices. The specific focus is on the role of using **symmetric** versus **general** Burer-Monteiro factorization as parameterization and how it effects the convergence properties. The unexpected result is that the *symmetricity* versus *imbalance* plays a significant role.\n\nThe main \"positive\" result states that the over-parameterized gradient descent on $FG^T$ factorization is able to achieve linear convergence when the two components are imbalanced in the sense of the spectrum of $\\Delta = F^\\top F - G^\\top G$, and the specific convergence rate depends on this imbalance. The main \"negative\" result shows that there will always exist a positive measure of cases when symmetric parametrization $FF^\\top$ cannot have faster than sublinear convergence.\n\nThe work provides simple, but well explained numerical examples of small matrix sizes ($50 \\times 50, \\mathrm{rank} =3$) that clearly demonstrate this phenomenon.\n\nThe proofs take more than 30 pages in the appendices, they are technically involved and not easy to check in their entirety, but at first sight the result seems correct.", "questions": "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?\n2) 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?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "I believe this paper has several very strong points:\n* It presents a novel and surprising result\n* It gives rigorous proofs for the two main statements which together describe a very interesting behaviour\n* The numerical examples corroborate the proven theory\n* The paper is very clearly written, the structure and main message is clear (although the theorems themselves can be a bit complicated to interpret)\n* It gives a very good comparison with existing literature", "weaknesses": "There is not much that I would consider a weakness to this paper. That said, I would like to know, how much the results of the numerical experiments in terms of the neat convergence rate depend on a specific initialisation of the methods and whether these result would also occur for larger ranks and problem sizes.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "RaeHmkdmAZ", "reviewer": "Reviewer_UZwv", "summary": "In this work, the authors provided the analysis on the different convergence rates when exact-parameterization or over-parameterization are used. They also proposed a new algorithm to avoid the dependence of the convergence rate on the initialization rate for the asymmetric and over-parameterized case.", "questions": "(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. Similar comment applies to other theorems.\n\n(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.\n\n(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.\n\n(4) After Theorem 1.3: I think it should be \"Comparing Theorem 1.3 and Theorem 1.1\".\n\n(5) Section 1.3: It might be better to also mention the current state-of-the-art results on landscape analysis:\n\nZhang, H., Bi, Y., & Lavaei, J. (2021). General low-rank matrix optimization: Geometric analysis and sharper bounds. Advances in Neural Information Processing Systems, 34, 27369-27380.\n\nBi, Y., Zhang, H., & Lavaei, J. (2022, June). Local and global linear convergence of general low-rank matrix recovery problems. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 36, No. 9, pp. 10129-10137).\n\n\n(6) Section 2: \"Asymmetric Matrix Sensing\"\n\n(7) Theorem 3.1: it seems that the \"ultimate error\" does not appear in Section 3.1.\n\n(8) 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.\n\n(9) In (3.3a), I think T should be T^{(0)}?\n\n(10) 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?\n\n(11) 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?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The results of this paper are novel and should be interesting to audiences in optimization and machine learning fields. The theory provides an explanation for the slow-down of GD in the over-parameterized case, and the paper offered a partial solution to this problem. However, due to the time limit, I cannot check the appendix. So I am not sure about the correctness of the results in this work.", "weaknesses": "I can only see a few minor problems with the presentation. For example, the requirement on the sample complexity can be briefly discussed when the informal results are introduced.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "NwQ9DKTMBf", "reviewer": "Reviewer_XP68", "summary": "This paper studies the matrix sensing problem where one observes y_i = <A_i, M^*> and A_i, and aims to estimate M^*. \nThis problem makes sense for either symmetric or asymmetric matrices. \nThe most significant contribution is that this paper unveils a surprising phenomenon that even for the symmetric version of the problem, introducing asymmetry in the initialization and the parametrization produces qualitatively faster convergence rate.", "questions": "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 (in the sense of e.g. https://arxiv.org/abs/2207.09660) results?\n\n2. 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 somewhat motivated by other models with similar structures such as generalized linear models or single-index models. I guess the information exponent of phi or something like that will play a role in the convergence rate. \n\n3. 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. Please let me know if I missed something simple here. \n\n4. It seems that both the model and the algorithms are deterministic. What happens if the observations are noisy?\n\n5. 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. In fact, if the matrices are extremely rectangular (e.g. n_2 / n_1 is growing or decaying), I actually doubt if such extensions are so straightforward. Thanks in advance for the clarification. \n\n6. 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. \n\nMinor notational/grammatical issues. \n1. The ground truth is interchangeably denoted by M^* or M^\\star. I suggest stick to M^\\star to avoid conflict with adjoint operator. \n\n2. In the title of Sec 1.2, where is the word \"symmetric\" repeated twice?\n\n3. Statement of Theorem 1.3: t-the iteration --> t-th iteration. \n\n3. Page 4: which we require it to be small --> which we require to be small.\n\n4. Description of Table 1: by \"row\" I think the authors meant \"column\". \n\n5. Right after equation (2.2): definition of A should be A^*.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The matrix sensing problem requires no more motivation (at least to me) and the results in this paper bring further insights to this classical problem. \nThe paper is reasonably well-written and the results are definitely sufficiently interesting for ICLR. \nThe punchlines (the fact that asymmetry helps and why/how this is the case) are clearly addressed within the first 4 pages. \nSec 4.1 is pedagogically helpful. \nSeveral versions of the problems are treated to a reasonably systematic extent.", "weaknesses": "I don't see major weaknesses. \nPlease see technical comments below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (spotlight)