Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorization
Authors: Tian Ye
Simon Shaolei Du
Venue: NeurIPS 2021 Poster (2021)
Keywords: non-convex optimization
theory
global convergence
random initialization

Abstract: We study the asymmetric low-rank factorization problem:
\[\min_{\mathbf{U} \in \mathbb{R}^{m \times d}, \mathbf{V} \in \mathbb{R}^{n \times d}} \frac{1}{2}\|\mathbf{U}\mathbf{V}^\top -\mathbf{\Sigma}\|_F^2\]
where $\mathbf{\Sigma}$ is a given matrix of size $m \times n$ and rank $d$. This is a canonical problem that admits two difficulties in optimization: 1) non-convexity and 2) non-smoothness (due to unbalancedness of $\mathbf{U}$ and $\mathbf{V}$). This is also a prototype for more complex problems such as asymmetric matrix sensing and matrix completion. Despite being non-convex and non-smooth, it has been observed empirically that the randomly initialized gradient descent algorithm can solve this problem in polynomial time. Existing theories to explain this phenomenon all require artificial modifications of the algorithm, such as adding noise in each iteration and adding a balancing regularizer to balance the $\mathbf{U}$ and $\mathbf{V}$.

This paper presents the first proof that shows randomly initialized gradient descent converges to a global minimum of the asymmetric low-rank factorization problem with a polynomial rate. For the proof, we develop 1) a new symmetrization technique to capture the magnitudes of the symmetry and asymmetry, and 2) a quantitative perturbation analysis to approximate matrix derivatives.  We believe both are useful for other related non-convex problems.

Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorization
Tian Ye
Institute for Interdisciplinary Information Sciences Tsinghua University
yet17@maile tsinghua. edu.
Simon S. Du Paul G. Allen School of Computer Science and Engineering
University of Washington ssdućcs. washington, edu
Abstract
We study the asymmetric low-rank factorization problem:
min UERmXa VeRoxd
JUV Σ1
where E is given matrix of size admits two difficulties in optimization: 1) non-convexity and 2) non- mooshmootsssss (due to unbalancedness of U and V). This is also prototype for more complex problems such as asymmetric matrix sensing and matrix completion. Despite being non-convex and non-smooth, it has been observed empirically that the randomly initialized gradient descent algorithm can solve this problem in polynomial time. Existing theories explain this phenomenon all require artificial modifications of the algorithm. such as adding noise in each iteration and adding balancing regularizer to balance the U and V.
and rank d. This is canonical problem that
This paper presents the first proof that shows randomly initialized gradient descent converges to global minimum of the asymmetric low-rank factorization problem with a polynomial rate. For the proof. we develop 1) a new symmetrization technique to capture the magnitudes of the symmetry and asymmetry. and 2) quantitative perturbation analysis to approximate matrix derivatives. We believe both useful for other related non-convex problems.
Introduction
This paper studies the asymmetric low-rank matrix factorization problem:
min UeRmxd VeRwud
VU, = UV -
where E m is given matrix of rank d. While solving this optimization problem not hard (e.g., using power method), in this paper, we are interested in using randomly initialized gradient descent to solve this problem:
U - V M U.V.)
(3)
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

where 17 > 0 is the learning rate and Uo Vo are randomly initialized according to some distribution. Empirically, gradient descent with a constant learning rate can efficiently solve this problem (see. e.g., Figure 1 in Du et al. (2018). Somehow surprisingly, there is no global convergence proof of this generic algorithm, let alone convergence rate analysis. The main difficulties are 1) the problem is non-convex and 2) this problem is not smooth with respect to (U, V) because the magnitudes of them can be highly unbalanced.
To motivate the study of gradient descent for this optimization problem, we note that this is a prototypical optimization problem that illustrates the gap between practice and theory. particular, the prediction function UV is homogeneous; if we multiply a factor by scalar c and divide another factor by c, the prediction function remains the same. This homogeneity also exists in deep learning models. Therefore, progress made in understand [[] can further help us gain understanding on other non-convex problems, such as asymmetric matrix sensing, asymmetric matrix completion, and deep learning optimization. We refer readers to Du et al. (2018) for more discussions.
For Problem (I) Du et al. 2018) showed gradient flow (gradient descent with the step size n + 0),
Ú = (Σ UVT) V and V = (Σ ( U,
converges to the global minimum but no rate was given. Here U. R + R U U(t) and V : R Ruxd V -(t) are integral curve over manifold Rmxd Raxd and U du V:= dv dr Key in their proof is an invariance maintained by gradient flow: dt (UTU This invariance implies that if initially the difference between the magnitudes of Uo and Vo is small, then the difference remains small. This in turn guarantees the smoothness on the gradient flow trajectory. Du et al. [2018] further uses a geometric result (all saddle points in the objective function are strict and all local minima are global minima [Ge et al.) 2013 (017b) 2016 Li et al. (019b)), )) and then invokes the stable manifold theorem to show the global convergence of gradient flow [eee et al. 2016 Panageas and Piliouras 2016).
de v (U-UVV = 0.
However, to prove a polynomial convergence rate, the approach that solely relies on the geometry will fail because there exists a counter example [Du et al., 2017]. Furthermore, for gradient descent with 17 0, the key invariance no longer holds
Du et al. [018) also studied gradient descent with decreasing step sizes 7/: = O (t-1/2). and obtained an "approximate global optimality result": the magnitude of the initialization is O (6), then gradient descent converges to 6-optimal solution, i... this result does not establish that gradient descent converges to a global minimum. And again, there was no convergence rate. Furthermore, their result crucially relies on 7/: is of order O (t-1/2) to ensure the second order term does not diverge and thus does not apply to gradient descent with constant learning rate.
Some previous works, e.g.. Ge et al. 2015 Jin al. [2017], modified the gradient descent algorithm to the perturbed gradient descent algorithm by adding an isotropic noise at each iteration, which can help escape strict saddle points and bypass the exponential lower bound in Du et al. [2017). To deal
with the non-smooth problem, they also added balancing regularization term Park et al.) 2017 Tu
et al. 2016 Ge al. 2017a Li et al., 2019b), 1 [|U'U-V V to the objective function to ensure balancedness between U and V throughout the optimization process. With these two modifications, one can prove a polynomial convergence rate. However, experiments suggest that the isotropic noise and the balancing regularizer may be proof artifacts, because vanilla gradient descent applies to the original objective function (T) without any regularizer finds a global minimum efficiently. From a practical point of view, one does not want to add noise or additional regularization because it may require more hyper-parameter tuning.
The only global quantitative analysis for randomly initialized gradient is by Du et al. [2018) who proved the global convergence rate for the case where Σ has rank 1, and U and V are two vectors. In this case, one can reduce the problem to the dynamics of 4 variables, which can be easily analyzed. Unfortunately, it very difficult to generalize their analysis to the general rank setting. Recent work also studies this case with noise injected to the gradient update [Liu et al. 2021
In this paper, we develop new techniques to overcome the technical difficulties and obtain the first polynomial convergence of randomly initialized gradient descent for solving the asymmetric low-rank
While the invariance can still hold approximately in some way, characterizing the approximation error is highly non-triven con-trivial, and this is one of our key technical contributions.

---

matrix factorization problem. Most importantly our analysis is completely different from existing ones: we give a thorough characterization the entire trajectory of gradient descent.
Before presenting our main results, we emphasize that the goal of this paper is not to provide new provably efficient algorithms to solve Problem ( but provide rigorous analysis of intriguing and practically relevant phenomenon on gradient descent. This is of the same flavor as the recent breakthrough on understanding Burer-Moneiro method for solving semidefinite programs (Cifuentes)
and Moitra 2019
1.1 Main Results
Our main result is below.
Theorem 1.1. Suppose each entry of Un and Vo are initialized using Gaussian distribution with mean and variance 6², where Ö (doo(mmt))
Then there exists Totat(O, n)
O
1 + In 2.) such that for any ô > 0 and learning rate 17 O ho In dad + qaa
we have that [ae"" dof
with high probability over the initialization, when t. (6 n).f (U,, V.) 5.
Here, 01 and da are the largest and the smallest singular values of Σ, respectively. Notably, in sharp contrast to the result in Du et al. [2018). which requires the initialization depends on 6, our initialization does not depend on the target accuracy. To our knowledge, this the first global convergence result for gradient descent in solving Problem ( Furthermore,
give polynomial rate. The first term in Total (6, 17) represents a warm-up phase and the second term represents the local linear convergence phase, which will be clear in the analysis sections. On the other hand, while we believe Tisal (6, 1)) is nearly tight, our requirement for r) is loose. An interesting future direction is further relax this requirement.
Now by taking 7) + O, we have the following corollary for gradient flow.
Corollary 1.2. Given d > O, there exists T O ou
In d
+ 1 In such that with high
aa
probability over the initialization, for all t T, have f (U,, V.
This is also the first convergence rate result of randomly initialized gradient flow for asymmetric matrix factorization. We note that our analysis gradient flow is nearly tight. To this, consider
the ordinary differential equation à = (oa af) )ar with initial point ag > 0, then s = a² has
analytical solution 8
Hence, to achieve 8 optimal solution, i.c. loa a² < 8,
need dd (a² 5 +
2002
Hence T (2. In is necessary.
Remark 1.2. We note that the weights will also converge. In section 3.3 we will prove that U and V are always bounded, which implies the gradient norm is bounded in terms of the loss. Since the loss function converges linearly, we have that the gradient norm converges to 0 linearly. The convergence of U and V follows from that the trajectory of (U,, forms a Cauchy sequence.
1.3
Additional Related Work
Here we discuss additional related work. First, in the symmetric setting, e.g., minu JUU - Σ p. global convergence of randomly initialized gradient has been established various settings Jain et al. 2017 Li et al. 2018 Chen et al. 2019 However, as has been highlighted in et al. 2201 Park al. 2017].1 et al. [2016] generalization
the asymmetric case is highly non- non-trivial. The major technical difficulty is to deal with the unbalancedness between U and V. To prevent this, additional balancing regularization is often added [Li al.) [011b)] Park et al. 2017 Tu et 2016
Sun and Luo 2016). though empirically this has been shown to be unnecessary.
Another line of work showed one can first uses spectral initialization find a near-optimal solution. then starting from there, gradient descent converges to an optimum with a linear rate [Tu et al.
2Ô hides logarithmic terms.
In gradient flow, i is continuous time index.
'In Appendix we show the dynamics of gradient flow actually admits closed form, form, and thus can be easily analyzed.
3

---

2016 Zheng and Lafterty 2016 Zhao et al. 2015 Bhojanapalli et al. 2016], though in practice random initialization often suifices. Recently, Ma et al. 2021] proved if I) the initialization is close to a global minimum and 2) U and V are balanced, then without adding additional balancing regularizer, gradient descent converges to a global minimum. Our stage two's analysis is similar to theirs. However, their result cannot be directly applied to our analysis because they require more stringent initialization than our stage two's initial point, There is also other work studying the balancing effect in terms of the learning rate [Wang et al. 2021].
Notations. Throughout the paper, bold letters, e.g., U, V, E, are reserved for matrices running in the algorithm, non-bold letters, c.g., U, V, Σ are for our analysis. For a matrix W with rank r, denote 0, (W) as the ith largest singular value of W, Vi E [r]. Furthermore, if W is symmetrie, denote X; (W) as the 1th largest eigenvalue of W. Let E E IR R be rank-d matrix with singular value σ1 2 ... 2 0g > O, and define its conditional as := _.
Our goal is to factorize E into UVT.
2
Main Difficulties and Technique Overview
2.1 A Reduction to Principal and Complement Spaces.
The starting point is the Polyak-t.ojasiewiiz condition: if we can establish that max (aa(Ue),.al oa(( is lower bounded by considerable constant Cuax, then have [V, V)Il 2 Cmax 22/(U, V). which implies a linear convergence. However, the dt singular values of U and V are not monotonic with t, and they can even decrease to an extremely small value.
To deal with this issue, consider the following transformation. Let the singular value decomposition of Σ is Σ = T''V" where + E mmmxm and V E IR. RR" are unitary matrices, and E' is diagonal matrix. Define U UU and V V VV. Then
rewrite equations (2) and (3) as
U/41 U, + (E U.V Vy:
(4)
V 4+1
V + =>= U.V U.
(5)
Hence, without loss of generality, we can assume Σ is a diagonal matrix with Σ,;- = o, Vi E [d] and E 0 otherwise.
To proceed, we will analyse the principal space and the complement space separately, We denote the upper d x d matrix of U as U and denote the lower (m - d) x d matrix of U as J. Similarly, we define the upper d x matrix of V as V and the lower (n - d) x d matrix as K. Define
E == diag(o), .a)) We can write out the dynamics of these matrices:
U411 = U. + (EE - U.V, VV, - nU,K, KG;
(6)
V4+1 = Ve+ -1(5 - ) -V Jei
(7)
J411 = -e-nJ.(V, V2 K, K,]:
(8)
Ki+1 = =K; (U,T U.+ + +TT J:).
(9)
Additional Notations Throughout this paper, we have some notation conventions. First of all, we omit the subscript (iteration number) of a matrix, then it represents that this matrix at any iteration If some matrices without subscripts appear in the same equation, it means the equation holds for arbitrary iteration f, and the subscript for each matrix should be the same. For instance, if we define A = U+V. it means we define A, := U-1% Vt 2 O. Similarly, we define B == U-V
Besides A, J J and K, there some other special capital letters used to represent specific matrices throughout this paper. Here is a list.
S AAT: p Σ AAT + BBT
AB BAT
We define such S is because in symmetric case (B = 0), although it is hard to find analytical solution for A in continuous time case, we do find analytical form for S, which contains all information about the singular values of A.

---

P and Q are just the symmetric and convergence of gradient descent is equivalent the linearly diminishing of P and c by Pythagorean theorem. We will mention their definitions every time we use them.
part of matrix E - UVT Hence the linear
2.2 Symmetrization
Our key observation is that although the singular values of U and V may not have monotonic property, the symmetrized matrix has this property. Formally, we define
U + V and B U
A
2
Here, A represents the magnitude in the principal space and B represents the magnitude of asymmetry. Empirically, we can observe that by choosing a sufficiently small learning rate 7/, we have two desired properties:
The smallest singular value A is almost monotonically increasing:
2. The norms of B, K are almost monotonically decreasing.
The first property ensures we are learning the "signal", I. and the second property ensures the "noise" disappearing. Therefore, if can establish these two properties, we can prove the global convergence.
2.3 Two Stage Analysis
The analysis for asymmetric low rank case divided into stages. In the first stage mainly focus on the increasing rate of aa(A). We will prove that in gradient descent method a (Aa) increases exponentially fast to / and then [|P||op drops exponentially fast to 4 while preserving |B] F: ||o and ||op small. In the second stage, we will use the large (a(AA to lower bound convergence speed of Σ UV 1|. We will prove that, once gradient descent starts at a point with small || op. [ [| and || |lop. it will converge to global optimal point exponentially fast.
3 Proof Sketch of Theorem 1.1
3.1
Initialization
We first use Gaussian distribution to generate matrices U, J. dlement-wischy and indepen- dently By standard random matrix theory (Corollary 2.3.5 and Theorem 2.7.5 Tao (2012)), we know that 3e >> O, such that with high probability, the smallest singular value of is larger than eva. the largest singular value U+V is smaller than cvd, the Frobenius norm of less than ed 2
5
1
and the operator norms of J and K are less than c/ hm/mammmm d} and o / d). respectively, d, n' n d.
where m'
The initializations Uo. Vo, Jo, Ko are then scaled by where specified in Theorem I.I
3.2 Stage One: Warm-Up Phase
In this stage, we would like to prove the following theorem.
) Theorem 3.1. By choosing e = (Vaai(mmmn) and 1 = O ( aaee doy
2o
we have that there exists
To = da 2
1 In
such that Vt S To.
1
3 A,A, 25:
dd
| < 2cde;
*Strictly speaking, we cannot make any assumption on U, V, K since they need information of singular value decomposition of Σ. However, random generation of U and V implies random generation of U, V, J,, because unitary transformations.
5

---

oa(Ano) 2 V o o1(Pi)) S 1
. [elllop S v //mx/mxmm dJ. [eelopp S (n'x
We first give some intuitions about the five conditions in Theorem 3.1 The first condition represents the "signal" is properly bounded from below and above throughout stage one. The second condition shows the magnitude of asymmetry is small throughout stage one. We note that crucial to study the Frobenius norm of B instead of operator norm, because Frobenius norm admits nice expansion for analysis. The third condition is an important one, which guarantees after To iterations, we have enough "signal" strength in the principal space. The fourth condition is technical one, which represents the symmetric error is small after To iterations. The fifth condition represents the magnitude of the complement space remains small.
Proof Sketch. The proof of Theorem 3.1 is quite challenging and require new technical ideas and careful calculations, which we explain below.
To analyze the dynamic of AA) let recall how it behaves in the continuous-time case. Our main idea is that, instead of analyzing A itself, we consider the symmetric matrix S := AAT. Then ds (Σ S)S + S(E S) plus some small perturbation terms about B, J and K.
If we only consider differential equation $ ( S)S + S(E -), S), (Theorem 12 in Lax 2007]) shows that if the singular values of S are different from each other, and is the singular vector that S = (s(S)), then the derivative (a(S)) is exactly { Št, which is lower bounded by 2( aa(S)))a(SS) To adapt
well-known theorem
discrete case, we prove the following lemma.
Lemma 3.2. Suppose S, Rdxd are two definite positive matrices, 17 0, and S' (I + n) (T) + r - 5)). Suppose oi (S) < 201 (E) 2 oa and 0n (E) S σ1 Define = (5 and = OS")". Then vB E (0, 1) and S 8
8+ 3
s 2 n[aa - -))
1-
This lemma shows if we ignore perturbations from B, J and K, then for small r) (when 17² is of smaller order than the first term), the least eigenvalue of S increases at a geometric rate.
However, there are also some small perturbation terms about B, J and K while doing analysis. |op and || llop are easy to give an upper bound, since by (8) and ( we know that by choosing small enough 7), they are monotonically decreasing, However, the dynamic of B is highly non-trivial. After some careful calculations (cf. (19), we find that the increasing rate of || B is related to the smallest eigenvalue P = Σ AA + BBT: if max (P)) is small, then [| increases slowly.
Now we would like to give a lower bound on Aa(P). Inspired by gradient flow case, P and S are almost complementrry
each other, and their dynamic behaves similarly. Hence we have p 2 - P PCC P) with some small perturbation terms about B, and K. Hence can use lemma 3.3 to give lower bound in discrete case.
Lemma 3.3. Suppose P.Σ E Rdxd are two symmetric matrices, n > 0, and Pt (I - n P() - nT(E - P)). Suppose o < 20 and aal I E I III. Define = (P and p' = >a(P"). Then v/3 10, and n 5 50.
p' 2 { (1 (1- 1-moa)² 0,
8468 1-3
o..
if < 0; ip 2 0.
Notice that we use B while analyzing P and use P while analyzing B. Hence, during the whole process, we need bound both of them inductively.
Finally, once (A( increases to a relatively large amount, we can use it to prove that P| will decrease exponentially fast to es One cannot simply prove that P converges to zero in this stage, since the perturbation term B will never converge to zero
Below give more details.

---

3.2.1 Assumptions
We make assumptions A and B in iterations t S To, where To will be defined the end of subsubsection 3.2.4 and we will verify the assumptions in the end.
T 3 AA 22
(2)
The Frobenius norm of is bounded by cyde for some cb 2 C, where eb will be determined later
Hence its operator norm is also bounded by eyde.
3.2.2 Dynamics on A, B and P
The dynamies on and K trivial since by equations
( and 9 i.e.
Je+1 Jt 1i-ny (V, Vs K. K:):
K++1 K, nU, U, + J. Jt):
1_ one can inductively proved that 0 3 V, V, + K, K₁ J 30 we know that if we choose 1) S 30, and 0 < U, U, J, J, 30 / by using the first assumptions in subsection 3.2.1 And then follows that the operator norms of J and K are monotonically decreasing in this stage.
However, it is trintaiviial to prove that [|p keeps small. We will analyze the dynamics of A, B and P = Σ AAT + BB together inductively.
First of all, from equations 6 and we can write down the dynamics of A == U+V and B U-V as following.
2
A411 = A + 7 - A
+ B,B,
) nA,B, -BA, B
K. K2
J, Jr
K, K; Jr.
BB
(10)
2
2
B
B. --1(E - A,A
+ +BB, }B, + (A B,A, )
K, K. J Jr
K, K₁ + +. Je
A,
-1BB
(11)
2
We can further calculate
P1+ = Pt - PPP
2n P
-2mP.BBB - + -
C.C,T
+ tn(Be + nP.BB)DD + +P..B.)
D.DD
(12)
where
K, K,
J. Je
K, K, J, Jr
C = A,B B, + B,A, B, A
B
(13)
2
2
KJ K₁
J Jr
K K₁ + J Jr
D, +A A. A A, A
B.
(14)
2
are two small perturbation terms.
3.2.3 Dynamics on A
Given (10), give lower bound for the minimal singular value of A
(a(A))1 2 aa(A, + n A,A, At))
K, K, +
J.
KJ K,
J. J
B,B, A. A.B,T B, + BA - A
B
2
2
op
We will show later that it is appropriate choose es 2c.
7

---

For the first part, we could define S : A,A, and S1+1 == (I + ( St))S((I + n( - -())..
Then according lemma 3.2, by choosing and 1j S Iooi have
(a(A))1)
v + o. -(=+((=--aAA)))))) (A.)2 220q'12
-1.5v201n(c + + ) (m
nndd.
(15)
For simplicity, we denote (A,) by ar, and define s; oa(S;) = o².
After some routine computation we can prove that it takes at most Tj : O (
In
iterations
nou x²
to make a, to at least V and additional computations show that, if d2 is always bounded by 22 then once (4 becomes larger than
Ød 2
is always larger than v 0 2
3.2.4 Dynamics on P
To bound P. by equation
12
we need to first bound the norms of C and D. by
13 and
By simple triangle inequalities have
|/elllp Dellop
2201 + ( + n)de?;
where the last inequality holds when choosing
Feed c (m+n)*
Then we can conclude that
P=-1 - - - r/ P.)) - Es,
(16)
where E, is a matrix with operator norm less than of + ne?e? (m + n)da; + offode By
choosing = I voi and 17 S 22c2(mmm)) we have EElloo & O(ne)e + n)dd1). Further more,
end
of
by choosing 3 = 2
and 1 S 160 lemma 3.3 we have
Ad(P+t)) 2 max {(1 - nou)² (P)) - Onage n)do))). Onneee
n)do1)}
Because Po is initially positive, we know that
(a(P)) 2 O(ee' n)dd).
(17)
This lower bound verifies the assumption that A.A, 3 2E, since A,A, = Σ P B.B 3 ag
-+ O(efe? + n)dx)I + ef = 2Σ by choosing efe² = O (mttn)de
On the other hand, can also analyze the operator norm of P by using formula 16 (a(Ar) Z / Z for 1 2 Ti. This implies that
since
ai (P.+1) (1 noan
(P.)+ + m)dai),
and it follows that
( S (1-12) 170d)
2 (P(Pr)) O(eee n))n))
(18)
Inequality 18) shows that we only need at most T2 == 0 ( Ink) iterations after Tj to make
(P))
<
24 4 Because g² I ad, we have the total number of iteration To = Ti + T3 =
In
de
7 Pleasse see (20) for the full steps for this incquality.
$ Pleasee see section D for details.
'leasse
21 for full steps for this inequality.
8

---

3.2.5 Dynamics on B
To verify the assumption about | made in subsection 3.2.1 we cannot simply use equation
ITI. since the error term [I(AB' BAA") "AAoo approximately O BI op). which will perturb
the analysis seriously. Inspired by the continuous case that [|]| 2 B, B Tr(B" PB)
2
Q| 'T(B' PB), where Q = ABT BAT we assume K 0. this inequality, we
hide the term (AB* BA AB )A in - 11 and wipe it completely in our analysis.
Hence, for discrete case, we have the following inequality 10
B 11 -B
I -2) + nl AdlelK,, K; - J, Jelle
+ A,A, + B,B, ) (A, - -A
K, K2 JJ
K2 K, + Jr Jr ||
A
BB
(19)
2 S O e² (m + n) m)rs) By 12. OOn + n)d?
2
where the last equation is because we have chosen r) =
Exee dr!
and eJ,²²
aa [m++n)a
By some routine calculations in section E, we have that by choosing E ò (miessm+m))
appropriate to choose t = 2c, so that Br 13 S ee and induction holds.
3.3 Stage Two: Local Convergence Phase
We have proved in theorem 3.1 that the gradient descent achieved a pretty good point at To. i.e. |r ll 2ode and 01 (Pro I az In this subsection, will prove that start from this point, the gradient descent will converge linearly to the global optimal point. Then theorem follows.
We will prove inductively on the following conditions:
(1) |B| 0 (
(2) A, || UTo+e Totellop S (1 nea faai
(3) oa(U),oa(V)) 2.
Intuitively, the (1) guarantees the magnitude of asymmetry remains small; (2) guarantees that in the principal space, the еттог converges to with geometric rate; and (3) guarantees the "signal" in the principal space remains lower bounded.
Proof Sketch. First of all, it is easy prove linear convergence of J and K by using assumption (3). Now we can verify the assumptions inductively.
(1)+ = (3): We can prove (UVVV) ((az). Because U - V is small, (3) follows by triangle
inequality.
(1) (3) + (2): Consider continuous-timm case, if we assume J = K = 0, the time derivative of Hence the convergence rate is lower bounded by au) and (V). Because the perturbation term J and K decreases exponentially, assumption (2) follows naturally. We transform this intuition to the discrete-time case.
E-UVT - UVT)VVT - -U
(2) + (3) + (1): Again, we use (19) to show that the increasing rate of BB is bounded by A. Because A decreases exponentially, [B]]
f cannot diverge to infinity, but increase by a poly(m, n, n) factor. Then by taking sufficiently small can verify the assumption (1).
The full proof is deferred to appendix.
Please
22 for full steps for this inequality.

---

Summary of Stage 2. To sum up, we have 1 U = | U. | + |U,K
| F + K| p which can be further bounded by
E UU V To Tolell
(1
+ 2(c² + ct)= (m + n)d (1- I0ll
2
5
2
C (1
od:
2
IIn 7
for some universal constant C. Hence one only needs Ty == O an 6-optimal point.
iterations after To to achieve
Conclusion
This paper proved that randomly initialized gradient descent converges global minimum of the asymmetric low-rank matrix factorization problem with a polynomial convergence rate. This result explains the empirical phenomena observed in prior work, and confirms that gradient descent with constant learning rate still enjoys the auto-balancing property as argued in Du et al.) (2018).
We believe requirement of the step size is loose and a tighter analysis may improve the running time gradient descent. Another interesting direction is to apply our techniques to other related problems such as asymmetric matrix sensing, asymmetric matrix completion and linear neural networks
Acknowledgement
Simon S. Du gratefully acknowledges funding from NSF Award's IIS-2110170 and DMS-2134106.
References
Srinadh Bhojanapalli, Anastasios Kyrillidis, and Sujay Sanghavi. Dropping convexity for faster semi-definite optimization. In Conference on Learning Theory, pages 530-582. PMLR, 2016.
Yuxin Chen, Yuejie Chi, Jianqing Fan, and Cong Ma. Gradient descent with random initialization: Fast global convergence for nonconvex phase retrieval. Mathematical Programming, 176(1):5-37, 2019.
Diego Cifuentes and Ankur Moitra. Polynomial time guarantees for the burer-monteiro method. arXiv preprint arXiv:1912.0174:. 2019.
Simon S Du, Chi Jin, Jason D Lee, Michael Jordan, Barnabas Poczos, and Aarti Singh. Gradient descent can take exponential time to escape saddle points. arXiv preprint arXiv:1705. 10412, 2017.
Simon S Du, Wei Hu, and Jason D Lee. Algorithmic regularization in learning deep homogeneous models: Layers are automatically balanced. Advances Neural Information Processing Systems, pages 384-393 2018.
Rong Ge. Furong Huang, Chi Jin, and Yang Yuan. Escaping from saddle points - online stochastic gradient for tensor decomposition. In Proceedings of The 28th Conference Learning Theory, pages 797-842, 2015.
Rong Ge, Jason D Lee, and Tengyu Ma. Matrix completion has spurious local minimum. In Advances in Neural Information Processing Systems, pages 2973-2981, 2016.
Rong Ge, Chi Jin, and Yi Zheng. No spurious local minima in nonconvex low rank problems: A unified geometric analysis. In Proceedings of the 34th International Conference on Machine Learning, pages 1233-1242, 2017a.
For instance, we refer readers section G for possible way extend technique matrix sensing.
10

---

Rong Ge, Jason D Lee, and Tengyu Ma. Learning one one-hidden-lams -laer neural networks with landscape design. arXiv preprint arXiv:1711.0050/ 2017b.
Prateek Jain, Chi Jin, Sham Kakade, and Praneeth Netrapalli. Global convergence of non-convex gradient descent for computing matrix squareroot. In Artificial Intelligence and Statistics, pages 419,488,,2 2017.
Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M. Kakade, and Michael I. Jordan, How to escape saddle points efficiently. In Proceedings the 34th International Conference Machine Learning, pages 1724-1732, 2017.
P.D. Lax. Linear Algebra and Its Applications. Pure and Applied Mathematics: A Wiley Series of Texts, Monographs and Tracts. Wiley, 2007. ISBN 9780471751560 URL https://books
Jason D) Lee, Max Simchowitz, Michael Jordan, and Benjamin Recht. Gradient descent only converges minimizers. In Conference on Learning Theory, pages 1246-1257, 2016.
Qiuwei Li. Zhihui Zhu, and Gongguo Tang. tion. Information and Inference: Journal of the IMA, 8(1):51-96, 2019a.
The non-convex geometry of low-rank matrix optimiza-
Xingguo Li, Junwei Lu, Raman Arora, Jarvis Haupt, Han Liu, Zhaoran Wang, and Tuo Zhao Symmetry, saddle points, and global optimization landscape of nonconvex matrix factorization. IEEE Transactions on Information Theory, 65(6))3489-3514, 2019b..
Yuanzhi Li, Tengyu Ma, and Hongyang Zhang. Algorithmic regularization in over over-varam ver-ppaaaeteriiee matrix sensing and neural networks with quadratic activations. In Conference On Learning Theory, pages 2-47, PMLR, 2018
Tianyi Liu, Yan Li, Song Wei, Enlu Zhou, and Tuo Zhao. Noisy gradient descent converges to flat minima for nonconvex matrix factorization. In International Conference Artificial Intelligence and Statistics, pages 1891-1899, PMLR, 2021.
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.
Joannis Panageas and Georgios Piliouras. Gradient descent only converges to minimizers: Non- isolated critical points and invariant regions. arXiv preprint crXiv:1605.00405: 2016.
Dohyung Park, Anastasios Kyrillidis, Constantine Carmanis, and Sujay Sanghavi. Non-square matrix sensing without spurious local minima via the Burer-Montein approach. In Artificial Intelligence and Statistics, pages 65-74, 2017.
Ruoyu Sun and Zhi-Quan Luo. Guaranteed matrix completion via non-convex factorization. IEEE Transactions on Information Theory, 62(11):6535-66 (177695556699--, 2016.
Terence Tao. Topics in random matrix theory, volume 132. American Mathematical Soc., 2012.
Stephen Tu, Ross Boczar, Max Simchowitz, Mahdi Soltanolkotabi, and Benjamin Recht. Low-rank solutions of linear matrix equations via Procrustes flow. In Proceedings of the 33rd International Conference on International Conference on Machine Booming-Volumme 48, pages 964-973. JMLR. org, 2016.
Yuqing Wang, Minshuo Chen, Tuo Zhao, and Molei Tao. Large learning rate tames homogeneity: Convergence and balancing effect. arXiv preprint 2rXiv:21 2021.
Tuo Zhao, Zhaoran Wang, and Han Liu. Nonconvex low rank matrix factorization via inexact first order oracle. Advances Neural Information Processing Systems, 2015.
Qinqing Zheng and John Lafferty. Convergence analysis for rectangular matrix completion using burer-monteiro factorization and gradient descent. arXiv preprint arXiv:1605.0705/ 2016.


Reviews:
[{"review_id": "iic2dWIv6PD", "reviewer": "Reviewer_UcqW", "summary": "This paper provides a proof of polynomial convergence rate whp of randomly initialized gradient descent on the non-convex problem of matrix factorization with the Frobenius norm. Notably, this problem was considered in previous works and only weaker results have been shown, e.g. no convergence rate, or polynomial convergence rate with the addition of noise and regularization. ", "questions": "", "limitations": "", "rating": 9, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "The related work section provides appropriate context for understanding the problem and the paper's contribution.\nOverall, the paper is very well structured for guiding the reader through the verification of the proof. The authors did a great job with how cleanly and clearly they broke down such a technically heavy proof into individual parts. I was able to follow most of the proof, and did not find any errors. (I assume in line 459, in the supplementary material, the \\sqrt{d^3} in the denominator is meant to be \\sqrt{d}, as this matches the original definition of epsilon and still works in the following lines)\n\nThere are some minor typos/grammatical errors but they do not detract from understanding.\n\nIn terms of the proof itself, I do not feel like I have a good intuitive understanding of what the proof is doing, more specifically what exactly is the main idea behind it, if there is one. I don't mean to say it is technically lacking, rather it is much the opposite as I alluded to above; there is a lot of careful balancing of terms and algebraic manipulation that leverages the specific choices of the noise variance and learning rate in multiple ways, which seems extremely nontrivial to come up with. Suffice it to say, I am not surprised why there were several works on this problem before and apparently none of them were able to solve it without weakening the result in some way. I was not able to see how the PL inequality the authors mentioned is relevant to this specific problem, though maybe that is due to a lack of experience in optimization literature on my part. It just seems like the authors wait for certain quantities to reach certain values, and then once that point is reached a decay factor can be upper bounded and a bunch of perturbation terms can be absorbed/canceled. Again, finding the right terms to pay attention to like the authors did seems extremely nontrivial.  On a more high level aspect of the proof, I found the reduction to the diagonal case and the splitting of the U,V matrices into U/J, V/K very nice. \n\nPerhaps the intuition of the proof machinery could be better conveyed, but because of the significance and difficulty of the problem the authors solved, as of now I rate this paper between an 8 and a 9. To me it clearly deserves to be published at a NeuRIPs-tier conference, but the problem it solves maybe seems like a bit of a toy problem, despite the clear interest in it by the theoretical community demonstrated by previous work. It was not clear whether the result of the paper has any bearing on or could have its proof be extended to something outside of this specific matrix factorization problem.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "dwAOmcOLEM", "reviewer": "Reviewer_tM8e", "summary": "This paper studies the problem of decomposing an m x n matrix of rank r into the product of an m x r matrix and an r x n matrix. While various methods exits for solving this problem, the goal of the paper is to provide theoretical guarantees for gradient descent with random initialization and fixed learning rate. The main result gives sufficient conditions, in terms of the dimensions (m,n), the rank r, and the condition number of the underlying matrix, under which the gradient descent method converges to a global optimum with a polynomial rate. \n\nThis work improves upon prior work which either: focused only the symmetric setting, does not give convergence results, or considered different initializations. The analysis and the conditions are based on two different stages. In the first stages,  the iterates converge slowly to get to a point `````near to an optimal solution. In the second stage, the iterate convergence quickly. \n\nNo numerical results are provided. ", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "The authors do a good job of describing their problem and the contribution of the results in the view of prior work. The main results is clearly explained and the high level idea behind the proof a conveyed. The more technical parts are a bit more difficult for me to follow, in part because the transition from continuous time to discrete was not clear to me, and also the convention of removing the time indices from the expressions made things more difficult for me to parse.\n\nI agree with the authors that the main contribution of this paper is the analysis of the method. Indeed, other efficient solutions exist and similar results have been proven for the symmetric setting. Unfortunately, it is difficult for me to describe that precisely the new ideas in the analysis are. This is partly because I am not super familiar with the immediate prior work I do not know which of the steps are novel and which are standard. The authors could do a better job of making this distinction for readers such as myself.\n\nWhile there is certainly a great deal of work in the literature focusing on variations of this low-rank factorization problem (both in the symmetric and non symmetric settings) it seems to me that it would be much more practically interesting to consider the setting where the matrix is only approximately low rank. I wonder to what extent the insights and analysis from the current line of work extend to this setting. \n\n more comments: \n\n- The distinction between sigma(.) as a function (applied to a matrix) as opposed to the singular values of a specific matrix (namely Sigma) was confusing, especially with respect to the statement of Lemma 3.2.\n\n- The wording in footnote 5 could be made more precise. \n\n- The matrices and A and B and sort-of-but-not-really defined before they are used, and then they are defined later.\n\n\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The assumptions for the theoretical results are clearly stated. Given the theoretical nature of this work I do not see the need for any more discussion on societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "9ucAgWKSgPV", "reviewer": "Reviewer_b8gy", "summary": "The paper shows the global convergence of the matrix factorization problem with geometric convergence speed.", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "I think it is a well-written paper. In prior work, while we know the landscape of matrix factorization problem is nice, all proofs (that I know of) for showing global convergences require some artificial modifications on the algorithm, e.g. additional regularizer. It is nice to have proof that does not need those artificial changes. Furthermore, the paper also reveals that while the eigenvalue of U and V may not behave well, the eigenvalues of A=(U+V)/2 and B=(U-V)/2 do behave well. Hence, this paper not only gives a cleaner proof but also adds some insights to the matrix factorization problem. \nLooking at the submission history, I think proving geometric convergence is important to the problem (otherwise it still does not fully explain the good performance of the standard grandient descent in practice) and I am glad that the authors have proved it in this new submission.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper confirms the well-known observation with theoretical proof that the standard gradient descent algorithm finds the global optimum for the matrix factorization problem. I do not think there is any negative societal impact of this work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "5MWEFl0xNbK", "reviewer": "Reviewer_RZoC", "summary": "This paper studies the performance of the gradient descent (GD) algorithm for a prototypical instance of the asymmetric matrix factorization (AMF) problem. The main result of the paper is establishing the polynomial convergence of GD for an ideal and noiseless, but unregularized instance of the asymmetric matrix factorization. To the best of my knowledge, the technical contributions of the paper are sound and correct.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "While I believe that the technical contribution of the paper is novel and clear, I do have several comments:\n\n1. My major comment is that the proposed analysis of this work seem to only work for an idealized objective function. Indeed, the practical instances of the MF problems mostly rely on linear measurements of the form $y_i = trace(A_i’ X)$. Indeed, the considered loss function in this paper corresponds to the ideal population loss function, where the number of available samples approach infinity (or equivalently, the so-called RIP condition holds with constant zero). This would not pose any issue if the authors had clearly explained how their proposed technique can be extended beyond this synthetic variant of the problem. Based on my understanding, and unlike the authors’ claim, I don’t think their provided technique can be directly used in more general instances of AMF because these problems are not diagonalizable via a change of basis (i.e., Eq. 4 and 5) when the measurements are of the form $y_i = trace(A_i’ X)$. The authors should support their claim by explaining how their proposed technique can be extended to other practical instances of AMF, as well as “other related non-convex problems” (as claimed in the abstract).\n\n2. While I think relaxing the requirement for regularization is one of the main contributions of this work, I’d like to point out that another reason for such regularization is to remove optimal solutions at infinity. Indeed, without a regularizer that balances the norm of the components, globally optimal solutions exist at infinity. On the other hand, Theorem 1.1 and Corollary 1.2 only guarantee the convergence of the objective function, and do not provide any bound on the values of the obtained solution. Is it possible to show that $U_t$ and $V_t$ do not diverge if we run the algorithm for a longer time?\n\n3. Finally, it appears to me that the paper is not polished, and it suffers from numerous grammatical and notational mistakes. While these mistakes are mostly minor and can be fixed, they severely undermine the readability of the paper. For instance, some notations are used before their formal definitions (e.g. A and B in page 4). \n\n\n===================================================\nAfter rebuttal, the reviewers have successfully addressed my comments. I strongly encourage the authors to include their suggested method for handling the general linear measurements to the revised paper.  \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors are encouraged to address the above-mentioned comments.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: We thank the authors for this submission. Overall, the paper presents the first proof that shows randomly initialized gradient descent converges to a global minimum of the asymmetric low-rank factorization problem with a polynomial rate.

The paper well-motivates the approach. The authors have provided extensive responses to the concerns raised (matrix sensing connection, convergence of Ut, Vt, better presentation of results, etc) and the AC + reviewers really thank them for their effort. Overall, the new results obtained during the rebuttal definitely improve the quality of the paper. We all believe that the inclusion of these results during the rebuttal period is something that does not heavily change the message of this paper. 

There was discussion and consensus that this work is interesting. Having in mind issues/concerns raised by the reviewers, the main points of reviewers during further discussion were that this paper deserves publication, given the promised fixes by the authors during the discussion period. 
Decision: Accept (Poster)