Convergence of Alternating Gradient Descent for Matrix Factorization
Authors: Rachel Ward
Tamara G. Kolda
Venue: NeurIPS 2023 spotlight (2023)
Keywords: matrix factorization; gradient descent; global convergence; concentration; optimization

Abstract: We consider alternating gradient descent (AGD) with fixed step size applied to the asymmetric matrix factorization objective.
  We show that, for a rank-$r$ matrix $A \in \mathbb{R}^{m \times n}$,
  $T = C ( \frac{\sigma_1(A)}{\sigma_r(A)} )^2 \log(1/\epsilon)$
  iterations of alternating gradient descent suffice to reach an $\epsilon$-optimal factorization 
  $\| A - X_{T} Y_{T}' \|^2 \leq \epsilon \| A \|^2$   with high probability
  starting from an atypical random initialization. The
  factors have rank $d \geq r$ so that $X_{T}\in \mathbb{R}^{m \times d}$ and $Y_{T} \in\mathbb{R}^{n \times d}$, and mild overparameterization suffices for the constant  $C$ in the iteration complexity $T$ to be an absolute constant. 
  Experiments suggest that our proposed initialization is not merely of theoretical benefit, but rather significantly improves the convergence rate of gradient descent in practice. Our proof is conceptually simple: a uniform Polyak-Lojasiewicz (PL) inequality and uniform Lipschitz smoothness constant are guaranteed for a sufficient number of iterations, starting from our random initialization.  Our proof method should be useful for extending and simplifying convergence analyses for a broader class of nonconvex low-rank factorization problems.

Convergence of Alternating Gradient Descent for Matrix Factorization
Rachel Ward University of Texas Austin, TX rward@math. waarddmaat.utexxs..ooo ute.as. edu
Tamara G. Kolda
MathSci.ai Dublin, CA
tammy kol.a@mathsci....cccmcc.oom. ai
Abstract
We consider alternating gradient descent (AGD) with fixed step size applied to the asymmetric matrix factorization objective. We show that, for rank-r matrix A E mR T = C( ((ox(A)) log(1/e iterations of alternating gradient descent (-((
suffice to reach e-optimal factorization ||A X, Y ll < <||A|i with high probability starting from an atypical random initialization. The factors have rank d r so that XT E R gexd and Yr E Ruxd and mild overparameteriiztion suffices for the constant C' in the iteration complexity T to be an absolute constant. merely of theoretical
Experiments suggest that our proposed initialization benefit, but rather significantly improves the convergence rate of gradient descent practice. Our proof is conceptually simple: a uniform (PL. inequality and uniform Lipschitz smoothness constant are guaranteed for a sufficient number of iterations, starting from our random initialization. Our proof method should be useful for extending and simplifying convergence analyses for a broader class of nonconvex low-rank factorization problems.
Introduction
This paper focuses on the convergence behavior of alternating gradient descent (AGD) on the low-rank matrix factorization objective
min /XX, Y)
XYT AlE subject X R Y E Rand
Here, we assume m, n > 2 r = ran While there are a multitude of more efficient algorithms for low-rank matrix approximation. this serves simple prototype and special case of more complicated nonlinear optimization problems where gradient descent (or stochastic gradient descent) is the method of choice but not well-understood theoretically. Such problems include low-rank tensor factorization using the GCP algorithm descent [HKD20), a stochastic gradient variant of the GCP algorithm [KH20], as well deep learning optimization.
Surprisingly, the convergence behavior of gradient descent for low-rank matrix factorization still not completely understood, in the sense that there is a large gap between theoretical guarantees and empirical performance. We take a step in closing this gap, providing a sharp linear convergence rate from a simple asymmetric random initialization. Precisely, we show that if A is rank-r, then
(A) number of iterations T = C (Vd-vr-Ty (((A) log(1/e) suffices to obtain an e-optimal factorization
with high probability. Here, a% (A) denotes the kth singular value of A and C' > is a numerical
constant. To the authors' knowledge, this improves on the ofate-of-art convergence result in the
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

literature [JCD22], which provides an iteration complexity T =((e,(a) log(1/e) for gradient descent to reach an e-approximate rank-r approximation'.
(o)(A)
Our improved convergence analysis is facilitated by our choice of initialization of Xo. Yo. which appears to be new in the literature and is distinct from the standard Gaussian initialization. Specifically, for 12 and D2 independent Gaussian matrices, we consider an "unbalanced" random initialization of the form X. vi
1 1 and Yu v7 where 1) > is the step-size used in (altemating)
gradient descent. crucial feature of this initialization is that the columns of X, are in the column span of A, and thus by invariance of the alternating gradient update steps, the columns of X, remain in the column span of A throughout the optimization. Because of this, a positive rth singular value (PL) inequality for the region of the loss landscape on which
of X, provides the trajectory of alternating gradient descent is guaranteed to be confined to, even though the matrix factorization loss function f in (1) does not satisfy a PL-inequality globally.
By Gaussian concentration, the pseudo-condition numbers #1(X)) o1(A)
(x.))) a,(A) are comparable with
high probability"; for range of step-size 1j and the unbalanced initialization Xo-
1 Ad and
v
Yo 27 we show that (X(). is guaranteed to remain comparable to (-(A)
(A) for a sufficiently
(X)
large number of iterations t that we are guaranteed a linear rate of convergence with rate (xx(Xo) (X.)
The unbalanced initialization, with the particular re-scaling of Xg and Yo by vi and vn, respectively, not a theoretical artifact but crucial in practice for achieving a faster convergence rate compared standard Gaussian initialization, illustrated in Fig. Also in Fig. 1, we compare empirical convergence rates to the theoretical rates derived in Theorem 3.1 below, indicating that our rates are sharp and made possible only by our particular choice of initialization. The derived convergence rate of (alternating) gradient descent starting from the particular asymmetric initialization where the columns of X. are in the column span of A can be explained intuitively as follows: in this regime, the X, updates remain sufficiently small with respect to the initial scale of Xg. while the Y updates change sufficiently quickly with respect to the initial scale Yo, that the resulting alternating gradient descent dynamics on matrix factorization follow the dynamics of gradient descent on the linear regression problem min g YY= = |X, - A l7 where X, is held fixed at its initialization.
We acknowledge that our unbalanced initialization of X, and Yo is different from the standard Gaussian random initialization in neural network training, which is a leading motivation for studying gradient descent as algorithm for matrix factorization. The unbalanced initialization should not be viewed as at odds with the implicit bias of gradient descent towards a balanced factorization (CKL+21, WCZT21, ABC 22, CB22], which have been linked to better generalization performance in various neural network settings. An interesting direction of future research is to compare the properties of the factorizations obtained by (alternating) gradient descent, starting from various (balanced versus unbalanced) initializations.
2 Preliminaries
Throughout, for an m X n matrix M, |M] refers to the spectral norm and |M]] F refers to the Frobenius norm.
Consider the square loss applied to the matrix factorization problem (1). The gradients are
V Y) = (XYT - AAYY, V.f(X. = (XYT X
(2a)
(2b)
We will analyze alternating gradient descent, defined as follows.
'We note that our results are not precisely directly comparable as our analysis is for alternating gradient descent whereas existing results hold for gradient descent. However, empirically, alternating and non-alternating
gradient descent exhibit similar behavior across many experiments
[1(A] "The pseudo-condition number, oy[A], is equivalent to and sometimes discussed as the product of the product of the spectral norms of the matrix and its pseudoinverse, i.e., ||||||||] A'

---

(.(A)
- = 3.14e-3
(.(A) 0
0.5,
7.89c-3
(.(A)
0.7, 7 1.39e-2
(A)
10-2
relative error
10-6
Theory
10-10
Proposed
Random
10-14
500
1000
1500
2000
0
500
1000
1500
2000
500 1000
1500
2000
iteration (L)
iteration (1)
iteration (1)
Figure Alternating gradient descent for A 10000x 100 with rank(A) 5 and factors of size 100 x 10, The plot shows five runs each of our proposed initialization and compared with the standard random initialization. The title of each plot shows the condition and step length.
Assumption (Alternating Gradient Descent). For fixed stepsize > O and initial condition (Xo, Yo). the update is
X X; - Y.), Y t+1 Y. Vx, Y.).
(Ala) (Alb)
assume that the iterations are initialized in an asymmetric way, which depends on the step size and assumes known upper bound on the spectral norm of A. The matrix factorization is of rank > r, and we also make assumptions about the relationship of r, and quantities 8, 3, and 8 that will impact the bounds on the probability of finding and e-optimal factorization.
Assumption 2 (Initialization and key quantities). Draw random matrices + t Raad with i.i.d.
((0,1/0) and (0, /n) entries, respectively. Fix C 2 1, v < 1, and < C and let
X = 1/ Co) Ad, and Yo 1/2 Do (A) 422
(A2a)
The factor matrices each have 2 r columns. For 0, define
Vr-1
(A2b)
Vd
The number of iterations for convergence to 6-optimal factorization will ultimately be shown to depend on
8 (A) (2)
(A2c)
The probability of finding this e-optimal factorization will depend on
8 = (Ci7) - + - + -d/2
(A2d)
where C1, C2 > 0 are the universal constants in A.I.
Observe that the initialization of Xo ensures its columns are in the column span of A.
Remark 2.1. The quantity f(X,, Yo) does not depend on the step size r or 0 (A) Assumption
since
Y.YO - A = A
c T -
3

---

3
Main results
Our first main result gives a sharp guarantee on the number of iterations necessary for alternating gradient descent be guaranteed produce c-optimal factorization.
Theorem 3.1 (Main result, informal). For rank-r matrix A E TR set d 2 and consider Xo. Yo randomly initialized as in Assumption 2. For any e > O, there is an explicit step-size 7 n(e) > for alternating gradient descent as in Assumption 1 such that
|A - 1.XxYT for all T C (A) 02( p²
A
log
C
with probability 1- 8 with respect to the draw of Xo and Yo where ö is defined in (A2d). Here, C > 0 is an explicit numerical constant.
For more complete theorem statements, see Corollary 5.2 and Corollary 5.3 below. We highlight few points below.
The iteration complexity Theorem 3. is independent of the ambient dimensions n, m. In the edge case d =. O(r2), so the iteration complexity scales quadratically with
With mild multiplicative overparameteriiattoon d = (1+ a)r, p² (vT+a-13) and the iteration complexity essentially dimension-free. This is a direct result of the dramatic improvement in the condition number of (1 + a)r x Gaussian random matrix compared to the condition number of a square r x r Gaussian random matrix.
(1+a)
2. Experiments illustrate that initializing X₂ in the column span of A, and especially re-scaling Xu and Y, by v and /7, respectively, is crucial in practice for improving the convergence rate of gradient descent. See Figs. to 4.
3. The iteration complexity in Theorem 3.1 is conservative. In experiments, the convergence rate often follows a dependence on [A( rather than (A()) for the first several iterations.
a-(A)
(A)
3.1 Our contribution and prior work
The seminal work of Burer and Monteiro [BM03, BM05] advocated for the general approach using simple algorithms such as gradient descent directly applied low-rank factor matrices for solving non-convex optimization problems with low-rank matrix solutions. Initial theoretical work on gradi- descent for low-rank factorization problems such [ZWI.15], [TBS 16), [ZL16],, [SWW17], [BKS16] did not prove global convergence of gradient descent, but rather local convergence of gradient descent starting from spectral initialization (that is, initialization involving SVD compu- tations). In almost all cases, the spectral initialization is the dominant computation, and thus a more global convergence analysis for gradient descent is desirable.
Global convergence for gradient descent for matrix factorization problems without additional explicit regularization first derived in the symmetric setting, where A E Rax= is positive semi-definite, and f(X) = ||A X see for example [GHJY15, JJKN17, CCFM19].
For overparameterizet symmetric matrix factorization, the convergence behavior and implicit bias towards particular solutions for gradient descent with small step-size and from small initialization was analyzed in the work [GWB+1 17, LMZ18, ACHL19, CGMR20J.
The paper [YD21] initiated a study of gradient descent with fixed step-size in the more challenging setting of asymmetric matrix factorization, where A E mm is rank-r and the objective is | XYT || This work improved previous work in the setting of gradient flow and gradient descent with decreasing step-sit size [DHL18]. The paper [YD21] proved an iteration complexity of T (nd( (i(A)) log((/)) for reaching e-approximate matrix factorization, starting from small i.i.d. Gaussian initialization for the factors Xo, Yo. More recently, [JCD22] studied gradient descent for asymmetric matrix factorization, and proved an iteration complexity T = ((C((c((A)) llo(1/c))
(i(A]
to reach an e-optimal factorization, starting from small i.i.d. Gaussian initialization.

---

We improve on previous analysis of gradient descent applied to objectives of the form (1), providing an improved iteration complexity = ((( (A)
(1(A) log(1/e)) reach an e-approximate factorization. There is no dependence on the matrix dimensions in our bound, and the dependence on the rank r disappears if the optimization is mildly wer-parameterized, i.e., d = (1 + a)r. We do note that our results are not directly comparable to previous work as we analyze alternating gradient descent rather than full gradient descent. Our method of proof is conceptually simpler than previous works; in particular, because our initialization Xo is in the column span of A, we do not require a two-stage analysis and instead can prove a fast linear convergence from the initial iteration.
4 Preliminary lemmas
Lemma 4.1 (Bounding sum of norms of gradients), Consider alternating gradient descent in Assumption 1. (ll S +.r then
IV Y.I (f Y,) - f(X.+1, Y.)).
(3)
If moreover |X,||2 < 2. then f(, Yi) S f(X,, Y-1)). Consequently, if , < 1 for all
4,
"
= 0=.....,T, T, and |X+|l 2 S q for all O,..., T, then I Y, ll I (Xo, Y.)
Likewise, if x++1ll 2 s 1 then
VV Y.I - 2 (f(x.+1, Y.) f(X++1, Y++1)).
(4)
1)
and YY < 2, then (X1+1, Y.) S f(x,, Yi), and so if [X+1 1|2 for all O,....T,
7
and Y 112 < 2 for all ..., 1
, T, then Et= [X Y.) " (Xo, Yo).
Proof. The proof of Lemma 4.1 is a direct calculation:
1
f(X Y.)
A
X
2
1
A
(X, V./ YO
2
1
A
X,Y,
+ VX, YOYTTE
2
1
A
X.
Y. trace (X, AX, Y.)IDII
2
1
A
X.Y!
x,
[r Y.YYT trace (X A)Y, Y.JI
2
-(x,, Y,) !
V Y Y IIX. Y
2
? < S((,, Y,) VX 11 // V.X,, Y.)
" V., Y (X, YOIIF
S1(8, Y,) 2
< fX, Y,) "
V.f(X, Y.II
5

---

Proposition 4.2 (Bounding singular values of iterates), Consider alternating gradient descent as in Suppose (Xo) S 16n of (Y))) - 16y
Assumption Set fo := f(Xo, Yo). Set T. 32n To
99
Then for all 0 s T v T.:
1. |xrll S v1
1 and ||r|| S
1
vp
2. o, (Xo) - v2Tnfo S or (XT) S 01 (XT) S (Xo) + V
3. (Y,) - /2I & (Y & o (Yr) E ( + 22
The proof of Proposition 4.2 is in the supplement Appendix B.
Proposition 4.3 (Initialization). Assume X. and Yo are initialized as in Assumption 2, which fixes C 1 1, and D I U, and consider alternating gradient descent in Assumption 1. Then with probability at least
6, with respect to the random initialization and defined in (A2d),
1. p or (A)
3 S or (Xo), (1(X)) = CV.
o1(Y)) - (nCvv)(A)
VJ C 0i (A)
3
1
2.
2(1 - w) A f(x,, Yo) S (1
The proof of Proposition 4.3 is in the supplement Appendix C. Combining the previous two propositions gives the following.
Corollary 4.4. Assume Xo and Y are initialized as in Assumption 2, with the stronger assumption that C Z 4. Consider alternating gradient descent in Assumption with 1j S (Cvo.(A) With 3 as
in (A2c) and fo = f(Xo. Yu), set T = 807 So
With probability at least 1 - 6, with respect to the
random initialization and 8 defined in (A2d), the following hold for all t I....,T: T:
(X,,) N 1 B and o (x)), S
3
1
B
+
2
CV
2
1
Proof. By Proposition 4.3, we have the following event occurring with the stated probability:
(²oo(A)m S {X,)) S of (A))
9
1677
where the upper bound uses that C 2 4. Moreover, using that S ACuolAj of (Yo) S
( S I6nj For 3 as (A2c), note that T Boy
which means that we
32 To
can apply Proposition 4.2 up to iteration T, resulting in the bound o, (X,) 2 o, - v 2T 2
V 2 " Similarly, 01 (Xt), 01 (Y,) S C.. + /
Finally, we use a couple crucial lemmas which apply to our initialization of X, and Yo-
Lemma 4.5. Consider alternating gradient descent as in Assumption I. If ColSpan(X)) (Xo) C
ColSpan A), then ColSpan(X.) C ColSpan A) all t.
Proof. Suppose ColSpan X,)
C ColSpan (A). Then
S ColSpan(X.) S
ColSpan A) and by the update of Assumption
ColSpan (X+11) = ColSpan (X, + AAY, - X,Y,
C ColSpan U ColSpan AY) (oISSan(XXXXXXX
C ColSpan A).

---

Lemma 4.6. If A is rank ColSpan(X,) C (A)) and o, (X,) then
IV, Y, --1 20 (X;) Y Y,-
Proof. If A is rank r. ColSpan(X,) _ ColSpan (A), and o, (X,) then X, is rank-r; thus, ColSpan( Xz) = (olS In this case, each column of (X;Y) A) is in the row span of X], and so
( - - A)
[X - A)IE ox)) |X A O
Remark 4.7. While Lemmas 4.5 and 4.6 are straightforward to prove in the setting consider where is exactly rank-r, these lemmas no longer hold beyond the exactly rank-r setting (while the rest of the theorems use do extend). Numerical experiments such as Figure 4 illustrate that the proposed algorithm does extend finding best low-rank approximations to general matrices, the theory for these experiments will require careful reworking of Lemmas 4.5 and 4.6.
Main results
We are now ready to prove the main results.
Theorem 5.1. Assume Xo and Yo are initialized as in Assumption 2, with the stronger assumplion that 2 4. Consider alternating gradient descent as Assumption I with
9
1 S
4CvO (A)
With 8 as in (A2c) and fo = f(Xo, Yo), set
B
T
8nF
Then with probability at least - 8, with respect to the random initialization and 8 defined in (A2d), the following hold for all 1. ,,...,T.
A - X,Y! < 2exp fo
exp (=)p
(6)
Proof. Corollary 4.4 implies that or rX,) X, is initialized in the column space of A, X, remains in the column space of A for all t, and
8 for I,..,, Lemmas 4.5 and 4.6 imply since
4n
J Y. (1AT Y,X X 141 1
8
A - X, Y! pP
f(x+1, Y.).
27j
That is, a lower bound on (x,) implies that the gradient step with respect to Y satisfies the
Polyak- Lojasiewiii (PL)-equalit?"
We can combine this PL inequality with the Lipschitz bound from Lemma 4.1 to derive the linear convergence rate. Indeed, by (3),
B f(X+11, Y.+1) 1(X,11, Y,) < - [V Y < - 5(x Y.)-
'A function f satisfies the PL-equality if for all x Rm f(x) - f(x') = | where f(x")
minx fx)

---

where the final inequality is (7). Consequently, using Proposition 4.3,
1r. 8/4)" f(Xo, Yo) $ cxxp(-8T/4) Yo).
Corollary 5.2. Assume Xo and o are initialized as in Assumption with the stronger assumptions that C 2 4 and v S 2. Consider alternating gradient descent in Assumption with
B
7 32fo log (2f(E
(8)
where B is defined in (A2c) and fo = f(Xo, Y))- Then with probability at least 1 - 5, with respect the random initialization and 6 defined in (A2d), it holds
B
AA 1 S
interation T
8n7 fo
Here is defined in (A2b). Using the upper bound for 1j in (8), the iteration complexity to reach e-oplimal loss value is
(1((A)
2
|A|
T=
log
(r((A)
p
This corollary follows from Theorem 5.1 by solving for that the RHS of (6) is most c, and implies that 1) (A) when 1.2 using the lower bound
then noting that 7) S /32fo (og(2/ on fo from Proposition 4.3.
B
Using this corollary recursively, we can prove that the loss value remains small for T provided we increase the lower bound on by a factor of The proof is in supplementary section D.
8zy Jo
Corollary 5.3. Assume Xo and Y o are initialized in Assumption with the stronger assumptions that C 2 8 and v < 2- Fix < 1/16, and consider alternating gradient descent as in Assumption with
B
n S
/32.f log(1/e)
where 3 is defined in (A2c) and fo = f(Xo, Yo). Then with probability at least 1 - 6, with respect the random initialization and ê defined in (A2d), it holds for any N that
AA Se S 11JA-XoY[] X.YT
for T M
4e
8xy fu
6 Numerical experiments
We perform an illustrative numerical experiment to demonstrate both the theoretical and practical benefits of the proposed initialization. We use gradient descent without alternating to demonstrate that this theoretical assumption makes little difference in practice. We factorize rank-5 (r 5) matrix of size 100 100. The matrix is constructed A UEVT with and random 100 x orthonormal matrices and singular value ratio a, (A) (A) 0.9. The same matrix is used for

---

each set of experiments. We compare four initializations:
1
viDoi
Proposed:
X, ViVaCo
A (nxd)
Yo
4 (nxd)
Vn
1
ColSpan(A):
X. 10Vd
A& (nxd)
Yo
$ (nxd)
10yn n
1
Random:
X 10 m
$ (mxd)
Yo = (nxd)
10 n
1
Random-Asym:
X, T 10ym (mxd)
Yo V 10yn
+ (nxd)
Here, & denotes a random matrix with independent entries from (o, 1). The random initialization is what is commonly used and analyzed. We include ColSpan( A) to understand the impact of starting in the column space of A for Xy. Our proposed initialization (Assumption 2) combines this with an asymmetric scaling. In all experiments for computing the proposed initialization as well as the theoretical step size. We assume σi = (A) known in these cases. (In practice, misestimate of σ be compensated with different value for C.)
use the defaults C 4 and D Cv/9 with 1c-10
Figure 2 shows how the proposed method performs using the theoretical step size and compared to its theory. We also compare our initialization to three other initializations with the same step size. We consider two different levels of over-factoring, choosing d = 10 (i.e, 2r) and d = 6 (i.e., r + 1). All methods perform better for larger d = 10. The theory for the proposed initialization underestimates its performance (there may be room for further improvement) but still shows stark and consistent advantage compared to the performance of the standard initialization, as well as compared to initializing in the column span of A but not asymmetrically, or initializing asymmetrically but not in the column span of A.
d 10, =
2.072e-4 =2072
d d= 6, 11 = 1.792e-5
10
relative error
Theory
Proposed
10 10-6
ColSpan (A)
Random Random- Asyo
10-10-
10-14
2000
4000
6000 8000 10000 0 2000 4000 6000 8000
10000
iteration (t)
iteration (t)
Figure 2: Theoretical advantage of proposed initialization. Gradient descent (non-alternating) for A E IR 10100010 100 with rank(A) A) = 5, 01 and o, = 0.9. The plot shows five runs with each type of initialization.
Figure 3 shows how the three initializations compare with different step lengths. The advantage of the proposed initialization persists even with step lengths that are larger than that proposed by the theory, up until the step length is too large for any method to converge (17 = 1). We emphasize that are showing standard gradient descent, not alternating gradient descent. (There is no major difference between the two in our experience.)
Although the theory requires that be exactly rank-r, Fig. shows that the proposed initialization still maintains its advantage for noisy problems that are only approximately rank-r.
References
[ABC+22] Kwangjun Ahn, Sébastien Bubeck, Sinho Chewi, Yin Tat Lee, Felipe Suarez, and Yi Zhang. Learning threshold neurons via the "edge of stability". arXiv preprint a21.:2221..07469, December 2022.

---

= le-1
1)
le-2
1e-3
100
relative error
10
10-4
10-6
10-3
10-10
200
200
400
200
400
iteration (t)
iteration
(t)
iteration (t)
iteration (t)
Proposed
ColSpan(A)
Random
Random-Asyu
Figure 3: Advantage of proposed initialization for different step lengths. Gradient descent (non- alternating) for A E 10000x100 with (nn 0 and or 0.9. The plot shows five runs with each type of initialization.
7 = 1e-1
77 = 1e-2
71 = 1e-3
100
relative error
Proposed
ColSpan (A)
Random
Random-Asym
10
100
200
100
200
100
200
iteration (4)
iteration (1)
ileration (1)
Figure 4: Advantage of proposed initialization for noisy problems. Gradient descent (non- alternating) for E R 100x100 with rank(A) x (10% noise), 0 = 1 and a, = 0.9. The plot shows five runs with each type of initialization.
[ACHL19] Sanjeev Arora, Nadav Cohen, Wei Hu, and Yuping Luo. Implicit regularization in deep matrix factorization. Advances in Neural Information Processing Systems, 32, 2019.
[BKS16] Srinadh Bhojanapalli, Anastasios Kyrillidis, and Sujay Sanghavi. Dropping convexity for faster semi-definite optimization. In Conference on Learning Theory, pages 530-582. PMLR, 2016.
[BM03] Samuel Burer and Renato DC Monteiro. A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization. Mathematical Programming, 95(2)3329-357, 2003.
[BM05] Samuel Burer and Renato DC Monteiro. Local minima and convergence low-rank semidefinite programming. Mathematical programming, 103(3):427 444, 2005.
[CB22] Lei Chen and Joan Bruna. On gradient descent convergence beyond the edge of stability. arXiv preprint arXiv:2206.04/77 June 2022.
[CCFM19] Yuxin Chen, Yuejie Chi, Jianqing Fan, and Cong Ma. Gradient descent with random initialization: Fast global convergence for nonconvex phase retrieval. Mathematical Programming, 176:5-37, 2019.
[CGMR20] Hung-Hsu Chou, Carsten Gieshoff, Johannes Maly, and Holger Rauhut, Gradient descent for deep matrix factorization: Dynamics and implicit bias towards low rank. arXiv preprint arXiv:2011.13777 2020.
10

---

[CKL* 21] Jeremy M Cohen, Simran Kaur, Yuanzhi Li, J Zico Kolter, and Ameet Talwalkar. Gradient descent on neural networks typically occurs at the edge of stability. arXiv preprint arXiv:2 2wrXiv:213.000m 100.00065 February 2021.
[DHLI8] Simon S Du, Wei Hu, and Jason D Lee. Algorithmic regularization in learning deep ho- mogeneous models: Layers are automatically balanced. Advances neural information processing systems, 31, 2018.
[GHJY15] Rong Ge, Furong Huang, Chi Jin, and Yang Yuan. Escaping from saddle points online stochastic gradient for tensor decomposition. In Conference on learning theory, pages 797-842. PMLR, 2015.
[GWB+17] + 17] Suriya Gunasekar, Blake Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Srebro. Implicit regularization in matrix factorization. Advances in Neural Information Processing Systems, 30, 2017.
[HKD200] David Hong, Tamara G Kolda, and Jed A Duersch. Generalized canonical polyadic tensor decomposition. SIAM Review, 62(1):133-163, 2020.
[JCD22] Liwei Jiang, Yudong Chen, and Lijun Ding. Algorithmic regularization in model-free overparametrized asymmetric matrix factorization. arXiv preprint urXiv:2203.02833 March 2022.
[JJKN17] 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 479-488. PMLR, 2017.
[KH20] Tamara Kolda and David Hong. Stochastic gradients for large-scale tensor decompo- sition. SIAM Journal on Mathematics of Data Science, 2(4): 2020.
[LMZ18] Yuanzhi Li, Tengyu Ma, and Hongyang Zhang. Algorithmic regularization in over- parameterized matrix sensing and neural networks with quadratic activations. In Confer- ence On Learning Theory, pages 2 2-47. PMLR, 2018.
[RV09] Mark Rudelson and Roman Vershynin. Smallest singular value of random rectangular matrix. Communications on Pure and Applied Mathematics: Journal Issued by the Courant Institute of Mathematical Sciences, 62(12):1707-1739, 2009.
[SWW17] Sujay Sanghavi, Rachel Ward, and Chris D White. The local convexity of solving systems of quadratic equations. Results in Mathematics, 71 71:569-608, 2017.
[TBS+ 16] Stephen Tu, Ross Boczar, Max Simchowitz, Mahdi Soltanolkotabi, and Ben Recht. Low-rank solutions of linear matrix equations via Procrustes flow. International Conference on Machine Learning, pages 964-973. PMLR, 2016.
[Ver10] Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices. In Compressed Sensing, pages 210-268. Cambridge University Press, may 2010.
[WCZT21] Yuqing Wang, Minshuo Chen, Tuo Zhao, and Molei Tao. Large learning rate tames homogeneity: Convergence and balancing effect. arXiv preprint 1rXiv:2110.03677 2021.
[YD21] 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- 1439, 2021.
[ZL16] Qinqing Zheng and John Lafferty. Convergence analysis for rectangular matrix completion using Burer-Monteiro factorization and gradient descent. arXiv preprint arXiv:160..07051. 2016.
[ZWL15] Tuo Zhao, Zhaoran Wang, and Han Liu. Nonconvex low rank matrix factorization via inexact first order oracle. Advances in Neural Information Processing Systems, 158:461-461 2015.

---

A Non-asymptotic singular value bounds
Proposition A.1 (Theorem 1.1 of [RV09]). Let A be an d x r matrix, d 2 whose entries are independently drawn from N(0, 1). Then for every T 2 0,
Pr (,,(A) S r(va -r ( & (CIT) +e Crd
where C, C2 > O are universal constants.
Proposition A.2 ([Ver10]. Let A be an r matrix whose entries are independently drawn from 1). Then for every 2 0, with probability at least 1 1 -exp(t?2 -2// we have
(A) 2 Vd -i
and for every t 2 0, with probability least exp( -t² -t2/2), have
(A < vd +i+t
B Proof of Proposition 4.2
First, observe that by assumption, |X 2 Yoll I
9 S
1. Now, suppose that that
|Xoll |oll S 9 and || S for 1
0,... T 1, and
S S 32 Fo
169
Then by Lemma 4.1,
1 2
(X,, X.) S 2
(10)
F
Hence,
| - Xoll 11
VX/(X, Y.)
ST Σ V. Y.)
2 sn / 2150-
[>,, Y, =
(11)
Then, for $ T., | || $ Xpl + X x < \/ + 2T <
It follows that .タ.
1
| < for = 0,... ...... T. Using Lemma 4. I again, repeating the same argument,
YY
O....,T.
Iterate the induction until == 32n To J. to obtain
|x |2 S 1 for I,.... T..
Because X Xoll S Jo for T < T. Jo
(XT) > (Xo) - X Xoll:
a (XT) 5i + | Xoll-
similar argument applies achieve the stated bounds for o, (Yr) and 01 (Yr).
C Proof of Proposition 4.3
Write the SVD A = Unx Exxr VT PXn so that AΦ, = Umxr Bexr(VTT.)) Note that VT E Rexd has i.i.d. Gaussian entries \O, 2). By Proposition A.1, with probability at least 1 dCic)d-rt1 -Odd
(v( 2 vr-1
Vd
12

---

On the other hand, Proposition A.2 implies that with probability at least - - - dd1
-
2/r
S 3, and (1(22) - (1 2vd
0 = (1
S
Vd
vm
If all aforementioned events hold, 01 (VT S (V S 3, and
(1- 11ー--1 vrr1 vd
3 (A) (A( S (Xo,) (X)) v
VAC (1 S 33/TDo((A) I ViCioi(A).
3
where the last inequality uses D s -r. Consequently,
1 -- (
<
| 1--011 2
D S
(1)0010))) s +1+ M..
Hence,
D
2
2f(Xo, Yo)
A(I 7 2 2
S (1+
20(Xo, Yo) 2 min!!
(I- 0 tb
D
+3))
A
2
(1- (12)
1
D Proof of Corollary 5.3
Set 81 = 3 as in (A2c). Set fo(1) fo-
By Corollary 5.2, iterating Assumption for Ti -L fo(s
iterations with step-size
Lin
B1
32 (2 log(1/e)
guarantees that
2 A X Y 11 S f0(2) == co()) (X, xr, )| N 31
This means that at time T1, we can restart the analysis, and appeal again to Proposition 4.2 with modified parameters
s(X,, Yn) S So2: = f0o
:2 = 91
Corollary 5.2 again guarantees that provided
B2
31
5
(13)
32 f2 log(1/c)
4Ve f2 log(1/c)
then f(XT,+I,, YT,TT,) S eX(, YT,) s <ef((o Yo) where
Ti Th
(14)
4e
We have that (13) is satisfied by assumption we find that after T = Ti +.. Tę Ti E < Ti (1(2)* iterations, we are guaranteed that f(XT, Yr) < e fXo. Yo). This is valid for any T I because we may always apply
assume S 1 Repeating this inductively,
13

---

Proposition 4.2 in light of summability and C' 2 8: for any t,
01 (X{) S (Xo) + Vn
2 f0(z)(())
3
1
B1 f
2(1/(4c))
8 V1I
8f01
VB
k Σ (1/2)'
8 8
2/7 1=1
3 3+ 4VB S 2/7
1
8/
14


Reviews:
[{"review_id": "NmN3ZAPTgW", "reviewer": "Reviewer_Zy5R", "summary": "This paper proves an improved convergence bound on alternating gradient descent for asymmetric matrix factorization problem, i.e. given $A \\in R^{m \\times n}$, finding $X \\in R^{n \\times d}$ and $Y \\in R^{m \\times d}$ that minimize $||XY^{\\top} - A||_F^2.$ This paper establishes that if $A$ is rank $r$ for some $r < d,$ (so the optimal solution is 0) then the algorithm converges to a solution with error at most $\\varepsilon ||A||_F^2$ in roughly $\\frac{d}{(\\sqrt{d}-\\sqrt{r})^2}\\kappa^2 \\log \\frac{1}{\\varepsilon}$ iterations, where $\\kappa = \\frac{\\sigma_1(A)}{\\sigma_r(A)}$. Thus, if the problem is constantly over-parameterized, i.e. $d-r = \\Omega(r),$ this gives a dimension independent convergence bound.\nA crucial piece in their algorithm and analysis is starting from an unconventional asymmetric initialization, where $X$ is initialized as $\\frac{1}{\\sqrt{\\eta}}A\\Phi_1$  and $Y$ as $\\sqrt{\\eta}\\Phi_2,$ where $\\Phi_1, \\Phi_2$ are (normalized) iid Gaussian matrices, and $\\eta$ is the step size.\nThe paper also reports several numerical simulations demonstrating the significant advantage of their initialization.", "questions": "- I think the bound on line 30 is incorrect? there should be a square-root on d and r.\n", "limitations": "N/A", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The (asymmetric) matrix factorization problem is both an important problem in itself, and an important test bed for developing techniques to analyze non-convex optimization. I think this paper takes a significant step towards understanding (alternating) gradient descent in this setting. It improves on the previous best known bound for GD which was ~ $\\kappa^3.$\nI find the improvement due to the asymmetric initialization quite illuminating, and I think it will inspire other advantageous (yet quick) initializations for descent algorithms.", "weaknesses": "I don't see any major weaknesses.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ""}, {"review_id": "guLqex5b79", "reviewer": "Reviewer_BUrC", "summary": "The authors explore the use of alternating gradient descent (AGD) with a fixed step size for asymmetric matrix factorization. They demonstrate that a finite number of AGD iterations can achieve a high-probability -optimal factorization, even when starting from an asymmetrical random initialization. Empirical evidence supports the significant convergence rate improvements resulting from their proposed initialization. The authors' proof leverages a uniform Polyak-Lojasiewicz (PL) inequality and Lipschitz smoothness constant, providing a simpler approach for analyzing nonconvex low-rank factorization problems.\n\nThe findings in this paper challenge the conventional belief that symmetrical randomization is necessary when the underlying data structure allows for symmetry. This novel result, supported by solid theoretical justification, showcases promising improvements and highlights the potential for broader impacts in machine learning and optimization.", "questions": "There are two parts to the initialization. One is the $A\\Phi_1$ vs $\\Phi_2$, another is $\\sqrt{\\eta}$ vs $\\frac{1}{\\sqrt{\\eta}}$. I am curious whether  $\\sqrt{\\eta}$ vs $\\frac{1}{\\sqrt{\\eta}}$ is the major factor for bringing improvements. For example, what are the results if the authors use symmetrical random initialization with $\\sqrt{\\eta}$ on one side and $\\frac{1}{\\sqrt{\\eta}}$ on another side?", "limitations": "I don't foresee any potential negative societal impact resulting from this research.\n", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- Excellent novelty\n- Theoretical proof is elegant\n- Promising numerical results  ", "weaknesses": "It is worth noting that there are numerous competitors beyond first-order methods in the field to solve an exact rank-r matrix decomposition problem. To further enrich the discussion, it would be valuable if the authors explored potential avenues for generalizing their results. For example, investigating the application of their findings in matrix completion or the singular value decomposition (SVD) of a low-rank matrix with added noise could provide insights into the broader applicability of their approach.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ""}, {"review_id": "Gz7LzCDCvD", "reviewer": "Reviewer_Ewek", "summary": "This paper provides a new analysis for the convergence of alternating gradient descent on the low-rank matrix factorization problem $min_{X,Y} f(X,Y) = ||XY - A||_F^2$. The authors show that, by warm-starting the solution using the target matrix $A$, and appropriate step size scaling, they can achieve $\\epsilon$ error in $f$ in $O(\\kappa^2 \\log \\frac{||A||_F}{\\epsilon})$ iterations of alternating gradient descent, where $\\kappa$ is the pseudo-condition number of $A$, as long as the rank of $XY$ is larger than the rank of $A$ by a constant factor. This improved the best known dependence of $\\kappa$ from $\\kappa^3$ to $\\kappa^2$. Also, in contrast to some previous works, the initialization step does not require computing an SVD of $A$.", "questions": "1. Could the authors give some intuition behind the importance of imbalanced scaling? I understand that it is used to balance the norms of $X$ and $Y$, but the fact that it is so significant in the experiments is somewhat surprising so I am wondering if there is something deeper.\n\n2. Could this approach be used in the noisy setting, i.e. when $A$ is not exactly low rank? What are the difficulties?", "limitations": "NA", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "- The main technical contribution of this paper is the introduction and analysis of an asymmetric warm starting rule for matrix factorization. To the best of my knowledge this is an original technical contribution.\n- The theoretical analysis is interesting and advances the state of the art. Matrix factorization is a fundamental optimization task that among others, can be viewed as a subproblem of neural network training. As a result, progress in theoretical understanding of optimization algorithms is highly relevant.\n- The experimental results are interesting and show a surprising quality gap between different initialization methods.\n- The paper is very well written and technically sound.", "weaknesses": "- It seems to me like the assumption in line 454 that $V^\\top \\Phi_1$ has i.i.d entries is incorrect, and it only has i.i.d columns. In this case, a different lemma should be used in place of Proposition A.1. Does this change anything in the bounds?\n\n- I have some comments about the experiments in Section 6. It seems like the authors compare different algorithms using the same step size, however in my opinion it would be fairer to compare using the best fixed step size for each algorithm. This is especially so because of the special imbalanced step size setup in the authors' algorithm. For example, in Figure 3, Random and ColSpan significantly improve when increasing the step size from $0.001$ to $0.1$. What happens if the step size is increased even more? Can we rule out that the improvement in convergence is because of the step size magnitude?\n\nSome typos: \n- decent -> descent in multiple theorem/lemma statements.\n- Line 231: it should not be a strict subset", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ""}, {"review_id": "7YMAqIY8Ll", "reviewer": "Reviewer_GCxr", "summary": "This problem considers a matrix factorization problem: it seeks to minimize a function of the form $f(X,Y) = 1/2 \\Vert A - XY^T \\Vert_F^2$. In general, matrix factorization problems have applications to matrix sensing, phase retrieval, and are seen as prototypical non-convex optimization problems. The special case of the matrix factorization problem provided in this paper is very simple, and should be seen as a first theoretical step to understand other matrix factorization problems with more practical applications. \n\nThe contribution of this paper is to propose a particular initialization of the optimization problem that induces an improved convergence rate of alternating gradient descent to recover the matrix $A$. This is supported by both rigorous results and simulations. \n\n", "questions": "- Given that the convergence rates are exponential, wouldn't logarithmic y-axes be more suitable to plot the evolution of the errors?\n- I think it is a bit tough to skip the proof of Lemma 4.1. The least would be to explain that X -> f(X,Y) is a convex ||Y||^2-smooth function and thus you can use classical (but not really \"direct\"!) manipulations from convex optimization to derive the bounds. \n- Could you comment on why you are using alternating gradient descent rather that full gradient descent? Is it related to using only marginal smoothness in Lemma 4.1? Could your techniques be adapted for full gradient descent?\n- l.312: Are you using different Gaussian matrices for X_0 and Y_0?\n- l.319: Can you comment on the very small value for \\nu?\n- Figure 3: It seems that the benefits of the proposed initialization reduces when using large stepsizes. Could you try even larger stepsizes? Can you push simulations to the limit of stability of the gradient descent equations? \n\nTypos\n- l.407: \"non-asympototic\" -> \"non-asymptotic\"\n- l.80: \"and\" -> \"an\"\n- l.263 and footnote same page: \"PL-equality\" -> \"PL inequality\"?\n- l.280: \"interation\" -> \"iteration\"\n- l.300: inconsistent notation for the transpose", "limitations": "See weaknesses section.", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 1, "strengths": "The paper is clear and well-written. I checked the proofs of the main text and believe they are correct. \nI think the paper addresses an interesting problem in matrix factorization, but I am not convinced by the specific initialization that they propose. This is detailed below. ", "weaknesses": "I would like the authors to discuss more the motivations underlying their paper. My understanding is that factorizing a matrix $A$ in a product $XY^T$ is not hard, for instance one can choose $X=A$ and $Y = Id$. Of course, it is interesting to see if gradient descent is able to recover a factorization of the matrix $A$, given that there is non-convexity and non-smoothness. However, it seems to me that the initialization that you are proposing is similar to the solution $X=A$ and $Y = Id$. In this sense, the papers [YD21] and [JCD22] are stronger as they prove convergence from a Gaussian initialization, that seems further away from the solution.\n\nOf course, a contribution of your paper is to improve the convergence rates. However, it does not seem to me that obtaining optimal convergence rates is an identified challenge in the literature. For instance, you compare your convergence rate to the rate of [JCD22], but again these authors use a more challenging initialization, and prove that incremental dynamics appear, which is much harder than proving a simple convergence rate. \n\nIn light of the above points, I think that the comparison with related works in Section 3.1 is a bit unfair.\n\nGiven that this model is toyish, it is important to focus on behaviors that we believe to generalize on more sophisticated (matrix multiplication, non-convex) models. While incremental learning is one of them, I didn't understand whether an improved convergence with an atypical initialization satisfies this criteria. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ""}]

Author rebuttal:
Thank you to all the reviewers for the helpful comments.

Response to Reviewer Zy5R

- [Typo in bound on Line 30:] Thanks! Yes, the bound should be $\frac{d}{(\sqrt{d} - \sqrt{r})^2}$,  not $\frac{d}{d-r}$


Response to Reviewer BUrC

- [Generality of results] The analysis extends beyond matrix factorization but we prefer not to write details as we are in process of writing up follow-up papers.  
- [Importance of two parts to the initialization] Thanks for this point.  Both parts of the initialization are important.  See FIGURE 2 in the attached PDF for a comparison of the convergence behavior when both parts are used, compared to when just one or the other part is used. We will add these empirical comparisons to the revised version.  

Response to Reviewer Ewek

- [Assumption that $V^T \Phi_1$ has i.i.d entries] This assumption is correct, since we assume $\Phi_1$ has i.i.d. Gaussian entries and $V$ has orthonormal columns, which implies that $V^T \Phi_1$ has i.i.d. Gaussian entries.  

- [Comparison of algorithms using larger step-size]
This is a great point.  Please see FIGURE 1 in the attached PDF, where we consider step-size $1$. Larger step-sizes lead to divergence, so step-size 1 is close to the edge of stability of the algorithms.  Observe that while our initialization has a small advantage, the algorithms are all essentially comparable at the edge.  This should not be surprising, since at $\eta=1$, $1/\sqrt{\eta} = \sqrt{\eta}$ and the asymmetric component of the initialization is minimal.  We will include the comparison for $\eta = 1$ in the revised version and add this commentary.  Understanding the theory of gradient descent for matrix factorization at the edge of stability (e.g., for this example, $\eta \approx 1$) is quite challenging, and beyond the scope of this paper.  

- [Typos] Thanks! we will fix these.

- [Intuition for importance of imbalanced scaling] Good point.  Our intuition is as follows: with this particular asymmetric initialization, the $X$ updates remain sufficiently small with respect to the scale of the initialization $X_0$, and the $Y$ updates remain sufficiently large with respect to the initial scale $Y_0$, that alternating gradient descent behaves comparably to the \emph{linear} regression problem $\text{minimize}_Y \| A - X_0 Y \|_F^2$ (that is, $X = X_0$ is kept fixed at its initialization).  

- [Noisy setting, i.e. when $A$ is not exactly low rank] Empirically, yes, alternating gradient descent with our initialization converges to the best low-rank approximation to $A$ when $A$ is not exactly low-rank. The theoretical difficulty (although not impossibility!) is in carefully extending our Lemmas 4.5 and 4.6, which are no longer invariants of the algorithm beyond the exact low-rank setting.  

Response to Reviewer GCxr

- [Significance of initialization] Our initialization is not comparable to $X = A$ and $Y = Id$.  The sizes of the factors are completely different. 

- [Comparison to previous papers] While we agree that the papers $[$YD21$]$ and $[$JCD22$]$ prove convergence from a more generic starting point, our initialization has the same cost as a single step of gradient descent, and thus could potentially lead to an equally cost-effective initialization strategy (for matrix factorization and beyond). In this sense, our initialization is closer to the Gaussian initialization of $[$YD21$]$ and $[$JCD22$]$ than previous lines of work on spectral initializations.

- [Optimal convergence rates as identified challenge] This was not an identified challenge in the literature previously.  One contribution of our paper is identifying this challenge.  

- [Behaviors that extend to more sophisticated models] Our theory does extend to more sophisticated models. We prefer not to disclose details as we are in process of writing up follow-up papers.

- [logarithmic y-axes] Yes, good point and we can make this change in the revision.

- [Proof of Lemma 4.1] You are right; we will include at least a summary of the proof as you suggest in the revision.

- [Alternating rather that full gradient descent] Yes exactly, the marginal smoothness from alternating gradient descent allows us to prove a descent lemma, Lemma 4.1, which is the crucial first step in the convergence proof.  We did not see how to prove a descent lemma for (non-alternating) gradient descent, but numerics indicate that the two algorithms behave essentially the same.
\item[$X_0$ and $Y_0$:] We are using independent Gaussians for $X_0$ and $Y_0$, but the theory also holds if we use the same Gaussian matrix for $X_0$ and $Y_0$ (with $Y_0$ re-scaled).  We chose to focus on the case where they are different, to more closely compare to the Gaussian random initialization in $[$YD21$]$ and $[$JCD22$]$.

- [small value for $\nu$ in plot] A smaller $\nu$ leads to slightly better concentration of $f_0 = f(X_0, Y_0)$, see Proposition 4.3 part 2.

- [Benefit of the proposed initialization at large stepsizes:] Good point.  Please see the response to Ewek above, and FIGURE 1 in the attached PDF.



Meta-review: In this paper, the authors studied the classical problem of asymmetric matrix factorization, and came up with an alternating gradient descent (AGD) algorithm that enjoys provable fast global convergence for solving this problem. The rapid convergence is guaranteed even when the algorithm is initialized at asymmetric random initialization, which expands our understanding of the role of initialization for this nonconvex optimization problem. I would encourage the authors to expand their algorithm and theory to accommodate a broader (and more challenging) class of problems like matrix completion and matrix sensing, in order to further enhance the impacts of this paper.
Decision: Accept (spotlight)