Understanding Incremental Learning of Gradient Descent: A Fine-grained analysis of Matrix Sensing
Authors: Jikai Jin
Zhiyuan Li
Kaifeng Lyu
Simon Shaolei Du
Jason D. Lee
Venue: Submitted to ICLR 2023 (2023)
Keywords: deep learning theory
incremental learning
non-convex optimization

Abstract: The implicit bias of optimization algorithms such as gradient descent (GD) is believed to play an important role in generalization of modern machine learning methods such as deep learning. This paper provides a fine-grained analysis of the dynamics of GD for the matrix sensing problem, whose goal is to recover a low-rank ground-truth matrix from near-isotropic linear measurements. With small initialization, we that GD behaves similarly to the greedy low-rank learning heuristics~\citep{li2020towards} and follows an incremental learning procedure~\citep{gissin2019implicit}. That is, GD sequentially learns solutions with increasing ranks until it recovers the ground-truth matrix. Compared to existing works which only analyze the first learning phase for rank-1 solutions, our result is stronger because it characterizes the whole learning process. Moreover, our analysis of the incremental learning procedure applies to the
under-parameterized regime as well. As a key ingredient of our analysis, we observe that GD always follows an approximately low-rank trajectory and develops novel landscape properties for matrix sensing with low-rank parameterization. Finally, we conduct numerical experiments which confirm our theoretical findings.

Under review as a conference paper at ICLR 2023
UNDERSTANDING INCREMENTAL LEARNING OF GRA- DIENT DESCENT: A GIANNGRAINED ANALYSIS OF MA- TRIX SENSING
Anonymous authors Paper under double-bling brind review
ABSTRACT
The implicit bias of optimization algorithms such as gradient descent (GD) is be- lieved to play an important role in generalization of modern machine learning methods such deep learning. This paper provides a fine-grained analysis of the dynamics of GD for the matrix sensing problem, whose goal is to recover a low-rank ground-truth matrix from near-isotropic linear measurements. With small initialization, we that GD behaves similarly to the greedy low-rank learning heuristics (Li et al., 2020) and follows an incremental learning procedure (Gissin et al., 2019). That is, GD sequentially learns solutions with increasing ranks until it recovers the ground-truth matrix. Compared to existing works which only alyze the first learning phase for rank-1 solutions, our result is stronger because it characterizes the whole learning process. Moreover, our analysis of the incre- mental learning procedure applies to the key ingredient of our analysis, we observe that GD always follows an approx- imately low-rank trajectory and develops novel landscape properties for matrix sensing with low-rank parameterization. Finally, we conduct numerical experi- ments which confirm our theoretical findings.
regime as well. As
INTRODUCTION
Understanding the optimization and generalization properties of optimization algorithms is one of the central topics in deep learning theory (Zhang et al., 2021; Sun, 2019). It has long been a mystery why simple algorithms such Gradient Descent (GD) Stochastic Gradient Descent (SGD) can find global minima even for highly non-convex functions (Du et al., 2019), and why the global minima being found can generalize well (Hardt al., 2016).
One influential line of works provides theoretical analysis of the implicit bias of GD/SGD. These results typically exhibit theoretical settings where the low-loss solutions found by GD/SGD attain certain optimality conditions of a particular generalization metric, egg., the parameter norm (or the classifier margin) (Soudry et al., 2018; Gunasekar al., 2018; Nacson et al., 2019; Lyu & Li, 2020; Ji & Telgarsky, 2020), the sharpness of local loss landscape (Blanc et al., 2020; Damian et al., 2021; Li al., 2022: Lyu et al., 2022).
Among these works, a line of works seek to characterize the implicit bias even when the training away from convergence. Kalimeris et al. (2019) empirically observed that SGD learns model from simple ones, such as linear classifiers, to more complex ones. This behavior, usually referred to as the simplicity bias/incremental learning of GD/SGD, can help prevent overfitting for highly wver-parameterized models since it tries to fit the training data with minimal complexity. Hu et al. (2020); Lyu et al. (2021); Frei al. (2021) theoretically establish that GD on two-layer nets learns linear classifiers first.
The goal of this paper is to demonstrate this simplicity bias/incremental learning in the matrix sens- ing problem, non-convex optimization problem that arises in wide range of real-world applica- tions, e.g., image reconstruction (Zhao et al., 2010; Peng et al., 2014), object detection (Shen & Wu, 2012: Zou et al., 2013) and arry processing systems (Kalogerias & Petropulu, 2013). Moreover, this problem serves as a standard test-bed of the implicit bias GD/SGD in deep learning theory, since it retains many of the key phenomena in deep learning while being simpler to analyze.

---

Under review as a conference paper at ICLR 2023
Formally, the matrix sensing problem asks for recovering ground-truth matrix Z' E Rdxd given m observations y1..... Mm- Each observation yi here is resulted from a linear measurement y/ = (A,, Z*). where {Ai)sism is collection of symmetric measurement matrices. In this paper, we focus on the case where 2" is positive semi-definite (PSD) and of low-rank: Z = 0 and rank (Z*) < d.
An intriguing approach to solve this matrix sensing problem is to use the Burer-Monteir type de- composition Z UU with U E pdxf, and minimize the squared loss with GD:
1 (v: (v- (A.
min
f(U) = 4m
(1)
UERaXP
In the ideal case, the number of columns of U, denoted as above, should be set to but may not be known in advance. This leads to two training regimes that are more likely happen: the under-paramettrrized regime where f < T., and the peeepparaeteriieed regime where f
The over-parameterized regime may lead to overfitting at first glance, but surprisingly, with small initialization, GD induces good implicit bias towards solutions with exact approximate recovery of the ground truth. It was first conjectured in Gunasekar et al. (2017) that GD with small initial- ization finds the matrix with minimum nuclear norm. However, series of works point out that this nuclear norm minimization view cannot capture the simplicity bias/incremental learning behavior of GD. In the matrix sensing setting, this term partieularly refers to the phenomenon that GD tends learn solutions with rank gradually increasing with training steps. Arora et al. (2019) exhibits this phenomenon when there is only one observation (m = 1). Gissin al. (2019); Jiang al. (2022) study the full-observation case, where every entry of the ground truth is measured independently f(U)= 1 I UU Il.. and GD is shown to sequentially recover singular components of the ground truth from the largest singular value to the smallest one. Li et al. (2020) provide theoretical evidence that the incremental learning behavior generally occurs for matrix sensing. They also give a concrete counterexample for Gunasekar et al. (2017)'s conjecture, where the simplicity bias drives GD to a rank-1 1 solution that has large nuclear norm.
In spite of these progresses, theoretical understanding of the simplicity bias of GD remains limited. Indeed, vast majority of existing analysis only shows that GD is initially biased towards learning a rank-1 solution, but their analysis cannot be generalized to higher ranks, unless additional assump- tions on the GD dynamics are made (Li et al., 2020, Appendix H), (Belabbas, 2020; Jacot et al., 2021: Razin et al., 2021; 2022).
1.1 OUR CONTRIBUTIONS
In this paper, we take step towards understanding the generalization of GD with small initialization by firmly demonstrating the simplicity bias/incremental learning behavior in the matrix sensing setting, assuming the Restricted Isometry Property (RIP). Our main result is informally stated below. See Thcorem 4.1 for the formal version.
Definition 1.1 (Best Rank-s Solution) We define the best rank-s solution as the unique global min- imizer Z of the following constrained optimization problem:
min
(us - (A:, 2))² s.l. Z z- 0, rank (Z) S
ZERaxd
4m
Theorem 1.1 (Informal version of Theorem 4.1) Consider the matrix sensing problem (1) with rank-r- ground-truth matrix Z and measurements {e Assume that the measurements sat- isfy the RIP condition (Definition 3.2). With small learning rate μ > O and small initialization Ua.0 = aU E Rdxt, the trajectory of UN.UT during GD training enters o(1 neighhtooooo of each of the best rank-s solutions the order of 1,2, ...... PAT T. when a -
a,t
is shown in Li et al. (2018); Stöger Soltanolkotabi (2021) that GD exactly recovers the ground truth under the RIP condition, but theorem goes beyond this result in number of ways. First, in the over over-parann paramettriiee regime (i.e.. f 2 r.). it implies that the trajectory of GD exhibits an incremental learning phenomenon: leaming solutions with increasing ranks until it finds the ground
2

---

Under review as a conference paper at ICLR 2023
truth. Second, this result also shows that in the ander-parameterizeer regime (i.e., A < r.), GD exhibits the same implicit bias, but finally it converges to the best low-rank solution of the matrix sensing loss. By contrast, to the best of our knowledge, only the over-parameterrized setting is analyzed in existing literature.
Theorem 1.1 can also be considered as a generalization of previous results in Gissin et al. (2019); Jiang et al. (2022) which show that U,, passes by the best low-rank solutions one by one in the full observation case of matrix sensing S(U) पæ I UU I1 However, our setting has two major challenges which significantly complicate our analysis. First, since our setting only gives partial measurements, the decomposition of signal and error terms in Gissin et al. (2019); Jiang et al. (2022) cannot be applied. Instead, we adopt a different approach which is motivated by Stöger & Soltanolkotabi (2021); intuitive explanations of our approach is discussed in Appendix B. Second, it is well-know
that the optimal rank-s s solution of matrix factorization is X, (defined in Section 3). but little is known for Z In Section 5 we analyze the landscape of (2), establishing the uniqueness of Z and local landscape properties under the RIP condition. We find that when UA, ~ 3 GD follows an approximate low-rank trajectory. so that behaves similarly GD in the under- parameterized regime. Using our landscape results, we can finally prove Theorem 1.1.
Organization. We review additional related works in Section 2. In Section we provide an overview of necessary background and notations. We then present our main results in Section 4 where we also give proof sketch. In Section 5, we outline the key landscape results that we use to prove Theorem 4.1. Experimental results are presented in Section 6 which verify our theoretical findings. Finally, in Section 7, we summarize our main contributions and discuss some promising future directions. Complete proofs of all results in this paper are given in the Appendix.
RELATED WORK
Low-rank matrix recovery. The goal of low-rank matrix recovery is to recover an unknown low- rank matrix from a finite number of (possibly noisy) measurements. Examples include matrix sens- ing (Recht et al., 2010), matrix completion (Candès & Recht, 2009; Candes & Plan, 2010) and robust PCA (Xu al., 2010; Candès et al., 2011). Fornasier et al. (2011); Ngo & Saad (2012); Wei et al. (2016); Tong et al. (2021) study efficient optimization algorithms with convergence guar- antees. Interested readers can refer to Davenport & Romberg (2016) for an overview of low rank matrix recovery.
Simplicity bias/incremental learning of gradient descent. Besides the works mentioned in the introduction, other works study the simplicity bias/incremental learning of GD/SGD on tensor fac- torization (Razin al., 2021; 2022), deep linear networks (Gidel et al., 2019), two-layer nets with orthogonal inputs (Boursier et al., 2022).
Landscape analysis of non-convex low-rank problems. The strict saddle property (Ge et al., 2016; 2015; Lee et al., 201 6) was established for non-convex low-rank problems in unified framework by Ge et al. (2017). Tu et al. (2016) proved a local PL. property for matrix sensing with exact parame- terization (i.e. the rank of parameterization and ground-truth matrix are the same). The optimization geometry of general objective function with Burer-Monteiro type factorization is studied in Zhu et al. (2018); Li et al. (2019); Zhu et al. (2021). We provide comprehensive analysis in this regime for matrix factorization as well as matrix sensing that improves over their results.
3 PRELIMINARIES
In this section, first list the notations used in this paper, and then provide details of our theoretical setup and necessary preliminary results.
3.1 NOTATIONS
We write min(a, a, b} as ab b for short. For any matrix A, we use || of A. use |||]] to denote the spectral norm || and use mmin (A) to denote the smallest singular value of A. We use the following notation for Singular Value Decomposition (SVD):
|r to denote the Frobenius norm
3

---

Under review as a conference paper at ICLR 2023
Definition 3.1 (Singular Value Decomposition) For any matrix A E Rd of rank use = V to denote a Singular Value Decomposition (SVD) of A, where VA E Rdix XT, WA E Rd satisfy V.
= I, and A E Xx is diagonal.
For the matrix sensing problem (1), we write the ground-truth matrix as Z XXX for some X = (1), "2,".,, Ur.] E - with orthogonal columns. We denote the singular values of X as d1, 02.002...,0, ,r., then the singular values of Z" are of. .
We set Ør == for convenience. For simplicity, we only consider the case where Z has distinct singular values, i.e., of
> o7. > O. We use k == minrg.sr. f0 -0 to quantify the degeneracy of the singular values of z We also use the notatiowrite X, = [V), U2.-.. U.]] for the matrix consisting of the first columns of X. Note that Z; (Definition 1.1) does not equal X,X_ in general.
of 02
We write the results of the measurements {A as a linear mapping A Rdxd + R where [A(Z)]=
/ (A., Z) for all 1 I S m. We use A' : R Rdddd A" = E wi A; to denote the adjoint operator of A. Our loss function (1) can then be written
as (U) = 1 -UUT) The gradient is given by VS(U) = A" (u A(UUT))U= A (xx - U.
In this paper, we consider GD with learning rate μ starting from Uo. The update rule
U441 U. - (U,) (I + pM, where M, = A'XX ). We specifically focus GD with small initialization: letting Uo- = aU for some matrix U E RRdx with ||ū]] 1, we are interested in the trajectory of GD when + 0. Sometimes we write U, as U..t to highlight the dependence of the trajectory on a.
3.2 ASSUMPTIONS
For our theoretical analysis of the matrix sensing problem, we make the following standard assump- tion in the matrix sensing literature:
Definition 3.2 (Restricted Isometry Property) We say that measurement operator A satisfies
the (ō, RRP condition if (1 - Z < [| S (1 + 6)]l for all matrices Z E Rddd with rank (Z) S r.
Assumption 3.1 The measurement operator A satisfies the (2r, + 1)8) property, where r. rank (Z*) and < 10-7x=4,,3
The RIP condition is the key to ensure the ground truth to be recoverable with partial observations. An important consequence of RIP is that guarantees AA' AZ() = 1 Z is low-rank. This is made rigorous in the following proposition. m Em (A,, Z) A, ~ when
Proposition 3.1 (Stöger Soltanolkotabi, 2021, Lemma 7.3) Suppose that A satisfies (r, RIP with 2, then for all symmetric Z,
(1). rank (Z) < r L, we have [IAA* A 1) S Zl
(2). |IAA'A- I) - 8 8| where || - ||+ is the nuclear norm.
We also need the following regularity condition on the initialization..
Xx U) 2 for some positive constant p, where Assumption 3.2 For all 1 < < f Ar.. min (VI,
Vx, is defined as Definition 3.1.
The following proposition implies that Assumption 3.2 is satisfied with high probability with a Gaussian initialization.
Proposition 3.2 Suppose that all entries U E Rdxt are independently drawn from N (0, (1) and p = c Vt-vFAr-- 2 - then amin (VX,U) U) 2 p holds for all S S PAr, with probability VF
at lleast & (Ce - where c, C 0 are universal constants.
4

---

Under review as a conference paper at ICLR 2023
4 MAIN RESULTS
In this section, we present our main theorem, following the theoretical setup in Section 3.
Theorem 4.1 Under Assumptions 3.1 and 3.2, consider GD (3) with learning rate μ S 10 and initialization Ua = at for solving the matrix sensing problem (1). There exists universal constants c, M > 0, a constant C. (depending on i and k) and a sequence of time points To < To <
T such that for all 1 S & S f Tu,, the following holds when a = O ((pr.)
Uu.:: 5 - MR
(4)
where we recall that Z3 is the best rank-s solution defined in Definition I.I. Moreover, GD follows an incremental learning procedure: we have lima-0 m (Ua.) = 0 for all 1 S S i A Te, where (A) denotes the i-th largest singular value of a matrix A.
Compared with existing works (Li et al., 2018; Stöger & Soltanolkotabi, 2021) in the same setting, our result characterizes the complete learning dynamics of GD and reveals an incremental learn- ing mechanism, i.e., GD starts from learning simple solutions and then gradually increasing the complexity of search space until it finds the ground truth.
Now outline the proof of our main theorem. In the following, fix an integer 1 S s S Ar
and show the existence of Th > O satisfying that lim Un.Ta a,T. 2 = 0. We then show that Tg is monotone increasing in s for any fixed a.
Our first result states that with small initialization, GD can get into a small neighbourhood of Z
Lemma 4.1 Under Assumptions 3.1 and 3.2, there exists Ia 0 for all a > and S S
such that lim maxx (U,,) 0. Furthermore, it holds that Up: U Z;
1:
O (R33 vr.5 12).
Proof sketch: The proof is motivated by the three-phase analysis in Stöger & Soltanolkotabi (2021) but has some technical modifications. Starting from a small initialization, GD initially behaves sim- ilarly to power iteration since Ul+1 = (I + UM) = (I UM) where M := A' A(XX") a symmetric matrix. Let M
be the eigendecomposition of M. Then we have Σk=1 oR ŌJ
Uz ( (M+ = E( (o?) 0.0 Uo &
Σ (1 uo?) Uo 1=1
(5)
where the last step holds because it can be shown that + μō= > 1+ μ causing an exponential separation between the magnitude of the top-s and the remaining components.
phase which we call the parallel improvement phase. We consider the decomposition U, = U.W,W" + U,W,, WTT,, where W == W U, E RFxx is
When (5) no longer holds, we enter
the matrix consisting of the right singular vectors of VX, U, (Definition 3.1) and W., E (( is an orthogonal complement of W..
Assume X, = [0]e1, (.ex) without loss of generality. The columns of W, is an orthogonal basis of the subspace spanned by the first rows of U.. Each vector in Rº can be decomposed as parallel component and an orthogonal component w.r.t. this subspace. Intuitively, the row vectors of U,W; are the parallel components of the row vectors in Uú; we call U,W, the parallel component. For similar reasons, U, W.. will be referred to as the orthogonal component. More discussions for this decomposition are given Appendix
| We show in Appendix C.2 grows exponentially t, until the former reaches a constant scale, while the latter stays o1) (a + 0).
By the end of the spectral phase we have Tmin (U,W)) > (uinnU W.)
that afterwards, ||0, l
After Miin (U, ((1), we enter the refinement phase where we show in Appendix C.4
that X.X, U.U,T keeps decreasing until it is O (8x2 |1 (see Lemma 5.1). On
5

---

Under review as a conference paper at ICLR 2023
the other hand, we can show that best rank-s solution is close to the matrix factorization min-
imizer i.e. || z
x,X, Ir = O (fx We thus obtain that z - -, || =
O (on² ( /r_ Finally, since rank (,, S 8, we have a (U,) s | = o as desired.
Lemma 4.1 shows that U.U,T would enter neighbourhood of Z with constant radius. However, there is still gap between Lemma 4. and Theorem 4. since the latter states that U would actually get o( o-Iose to Z To illustrate our proof idea of this result, we first consider the simpler setting where the model is under-parameteriin i.e., f S r" and show that U,U, would eventually converge to Zz-
Proposition 4.1 (Convergence in the puram-taraeeterized regime) Suppose that F I r", then there exists constant = c(f, K) > O such that when a < c, we have lime+++o Ua U.. a,t Zz
Proof sketch: We can deduce from Lemma 4.1 by taking s = that there exists a global minimizer Už of (1) (equivalently, a matrix in Rdxa satisfying U; T z"), such that U |a.1: U²
On Vr.5 (cf. Corollary F.1). On the other hand, by taking s f in Theorem 5.1, we can see that within a neighbourhood of U, with constant radius, f satisfies a (PL) type condition with respect to the procrutes distance defined in Definition 5.1, and the global minimizer of f is unique up to orthogonal transformation. When 5 is sufficiently small, U, r. lies in this neighbourhood, and the PL condition implics that GD converges linearly to the set of global minimizers, which yields the desired conclusion.
Now we turn to the over-parameterized regime, where f is not necessarily local PL, and thus we cannot directly derive convergence as in Proposition 4. 4.1. To proceed, use low-rank approxima- tion for U, and associate the dynamics in this neighborhood with the GD dynamics of the following ander-parameterizzee matrix sensing loss:
S.(U) = 1 ||A(2 -UU Il
-U
U Ed
(6)
can be shown that when is sufficiently small, the global minimizer of fa is unique up to rotation, i.e, if Ü is a global minimizer of Sa. then any other global minimizer can be written as Ü: R for some orthogonal matrix R E Rexs The main observation is that GD) follows an approximate low- rank trajectory until it gets into a small neighbourhood of Z;, so that we can still use our landscape results in the low-rank regime.
Proof sketch of Theorem 4.1: For all / 6> -Āe, define Üa.t U Va W autfz Bdxx, where Wa,: = WVZ, U. as defined in the proof sketch of Lemma 4.1. Note that Lemma 4.1 implies that Ug is approximately rank-s, so within a time period after T3 the GD trajectory remains close to another GD initialized at Ú for the rank-s matrix sensing loss (6) until = θ (log 2). i.e.
Úa.ú ant Ro U Vo
U ag
Again by Lemma 4. the initialization Üo.0 is within a small neighbourhood of the global min- ima of (U). Furthermore, Theorem 5.1 implies that fa(U) satisfies local PL-like condi- tion, so that GD with good initialization would converge linearly to its global minima (Karimi et al., 2016). We need to choose time t such that (7) remains true while this linear con- vergence takes place for sufficiently many steps. We can show that there always exists some t= tt = such that both |iasUn att U 12 UT
- and (.at- - U:] are O a m.a Hence IUa, Zill S M.. for Ta : Tá tta-
For all S 8 < <<AA... since (7) always holds for L S ia and rank (Uns)) S 8, we must
have maxigisT; Je+1 (Ua,)) = o(1) as a + O. Finally, |z X X s4all = O()) (cf. Z 2 = O(1). Therefore, U..UT.
a,, cannot be close to Z:41 when & < T so we must have T T This completes the proof of Theorem 4.1.
Lemma E.5), 5o 0

---

Under review as a conference paper at ICLR 2023
5 CONVERGENCE IN
MATRIX SENSING
In this section, we analyze the properties of the landscape of the matrix sensing loss (1), which plays a crucial role in proving results Section 4. While the landscape
over-parameterized matrix sensing (i.e. f 2 r*) is well-studied (Tu et al., 2016; Ge et al., 2017), few results are known for the under-parameterized case. Our results provide useful tools for analyzing the convergence of gradient- algorithms for solving problems like low-rank matrix approximation and might have independent interests.
To prove convergence results like Proposition 4.1, first study the landscape of f. defined in (6) near the set of global minimizers. One major difficulty here is that fs is not locally strongly- convex, because if U E Rdx= is global minimizer of fs. then UR is also global minimizer, for any orthogonal matrix R E Raxs Nonetheless, we can establish Polyak-Lojasiewice (PL) like condition, Theorem 5.1, which is the main result of this section.
Definition 5.1 (Procrutes distance) For any d,s E N+ and U1 E Rdx=, we define dist(Un, U2) min [|| - U2R g R E Rx is orthogonal).
We note that the procrutes distance is well-defined because the orthogonal matrices are compact set and thus ||U U2 yr is continuous in R. It can be verified that procrutes distance a pseudo metric, i.e., it symmetric and satisfies the triangle inequality.
Theorem 5.1 (Landscape of under-pand parrrettraaaeizeed matrix sensing) The global minimizer of fa unique up to an orthogonal transformation, iee. the set of global minimizers of fs is R R: E R is orthogonal); where Uü is an arbitrary global minimizer. Moreover, let U Rdxs and U be a global minimizer of fa such that IU - U. dist(U, U:). Sup- |
pose that Assumption 3.1 holds and | 0.1rdist
U2ll S 10 10-2k |||]||
then (Vf.(U), -U) Z
(undist"UU,U (U,U) U.)
Remark 5.1 Recall PL condition means there exists some constant p. > such that [Vg(=)]1 24 (o(x) minger g())) holds for all x. Since fo is locally smooth around U", there exists constant e > 0 such that f=(U) [x(U;) S eı IIU U.l Moreover, Theorem 5.1 implies that IIU - U3 < 100- [ f.) In other words, Theorem 5.1 implies that the matrix sensing loss (1) is locally PL.
P f.. so we have [U) 2 2-0 (fa(U) - fUū)))
When 0, [s reduces to the matrix factorization loss Fs Rdxe - RR F.) =
I LUUT- 11 The following corollary immediately follows from Theorem 5.1. TJz
Corollary 5.1 (Landscape of under-parameterized matrix factorization) The of global min- imizers of F. is {X. R. R E Raxs is orthogonal). Moreover, under Assumption 3.1, given U gaxs and let R be an orthogonal matrix such that |IU R p (ost(UXX)) If dUst(U, X.) S 10-2x-111 || then (VF(U), X,R) 2 0.17dist
We end this section with the following lemma that formalizes the intuition that all global minimizers of the Js must be close to X, under the procrutes distance, which used in the proof sketch of Theorem 4.1 in Section 4.
Lemma 5.1 Under Assumption 3.1, have dist(U;, X.) < 400x|| for any global minimizer U of fo Moreover, I xXXX 1l 806k /x
EXPERIMENTS
In this section, we perform some numerical experiments to illustrate our theoretical findings.
Experimental setup. Consistent with theory, consider the matrix sensing problem (1) with = 50, r. = 5. a E (1, 0.0.1.0.11. 0.001}. J. m E {1000, 2000, 5000}. We will consider different choices for e in the experiments. The ground-truth z" XX is generated such that the entries

---

Under review as a conference paper at ICLR 2023
reletive error
ronc ran
relative crror
rank
16-7
(a) a 1, 1000 measurements.
(b) a 0.1, 1000 measurements.
107
ranc
makk rank: 2
r2n12
reletive ertor
relative crror
10"
15.4
182
150 Beeraion
300
250
123
200
400
Iteration
0.01, 1000 measurements.
(d) 0.001, 1000 measurements.
11-
reletive e110r
10'
reletive
ranit rank-2
rank
rank
16-
Iteration
itaration
(e) a = 0.001, 2000 measurements.
(1) a = 0.001, 5000 measurements.
Figure 1: The evolution of relative against the best solution of different ranks time.
of X are i.i.d. standard Gaussian variables. Throughout our experiments, we use the same ground- truth to compare different choices of parameters. For i 1, 2, ... all entries of the measurement A; Rdd are chosen i.i.d. from the standard Gaussian (0, 1). When m 2 dr_6-2, this set of measurements satisfies the RIP with high probability (Recht et al., 2010, Theorem 4.2).
We solve the problem (1) via running GD for T 10a iterations starting with small initial- ization with scale Specifically, choose Uo = aU where the entries of U E Rdx are drawn i.i.d. from standard Gaussian distribution. We consider both the over-parameterized and the exactaander-prrameteriiaia parameterized regime. The learning rate of GD is set to be 0.005.
6.1 IMPLICIT LOW-RANK BIAS
In this subsection, we consider the over-parameterized setting with r = 50. For each iteration
UU,U,_ xx,x, measure the t E [T] and rank [r.], define the relative error Et) || x, x IP
proximity of the GD iterates to X., We plot the relative error in Figure for different choices of and m (which affects the measurement error d).
Small initialization. The implicit low-rank bias of GD is evident when the initialization scale is small. Indeed, one can observe that GD first visits a small neighbourhood of X,, spends a long period of time near it, and then moves towards X₂. It then proceeds to learn X3. Xx, in similar way, until it finally fits the ground truth. This is in align with Theorem 4.1. By contrast, for large initialization do not have this implicit bias.
8

---

Under review as a conference paper at ICLR 2023
reletivv 60101
ronc ran:
rank4
2
Beeation
Iteration
(a) a 1, 1000 measurements.
(b) a = 0.1, 1000 measurements.
107
ranc
rank
r2n12
rank
reletive ertor
relative error
1.
100
200
400
200
423
Beeraion
iteration
0.01, 1000 measurements.
(d) 0.001, 1000 measurements.
Figure 2: The evolution of the loss and relative error against best solution of different ranks in the exact-parameterized case 5.
The effect of measurement error. For fixed a, one can observe the the relative error becomes smaller when the number of measurement increases. This is in align with Lemma 4.1 in which the bound depends on 8. In particular, for the case r.; although GD with fixed initialization does not converge to global minima, but the distance to the set of global minima scales poly(a:).
6.2 MATRIX SENSING WITH EXACT PARAMETERIZATTOON
Now we study the behavior of GD the exact parameterization regime (r= rx). We fix m 1000 and r r. 5 and run GD for 7 500 iterations. We plot the relative error in Figure 2. We can see that GD exhibits an implicit low-rank bias when a small. However, choosing very small would slow down the convergence speed. This is because GD would get into poly(a)- neighbourhood of the saddle point Z. and spend a long time escaping the saddle. Also, convergence to global minimizers is guaranteed as long as is below certain threshold (see Proposition 4.
7 CONCLUSION
In this paper, we study the matrix sensing problem with RIP measurements and show that GD with small initialization follows an incremental learning procedure, where GD finds near-optimal solu- tions with increasing ranks until finds the ground-truth. We take a step towards understanding the optimization and generalization aspects of simple optimization methods, thereby providing insights into their success modern applications such as deep learning (Goodfellow et al., 2016). Also, provide a detailed landscape analysis in the under-parameterized regime, which to the best of our knowledge the first analysis of this kind.
Although we focus on matrix sensing in this paper, it has been revealed in a line of works that the im- plicit regularization effect may vary for different models, including deep matrix factorization (Arora networks (Lyu et al., 2021; Timor al., 2022), Also,
et al., 2019) and nonlinear ReLU/LeakyRell it is shown Woodworth et al. (2020) that different initialization scales can lead to distinct induc- tive bias and affect the generalization and optimization behaviors. All these results indicate that need further studies to comprehensively understand gradient- based optimization methods from the generalization aspect.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Sanjeev Arora, Nadav Cohen, Wei Hu, and Yuping Luo. Implicit regularization in deep matrix factorization. Advances in Neural Information Processing Systems, 32, 2019.
Mohamed Ali Belabbas. On implicit regularization: Morse functions and applications matrix factorization. arXiv preprini AxXi::001.0042660 2020.
Guy Blanc, Neha Gupta, Gregory Valiant, and Paul Valiant. Implicit regularization for deep neural networks driven by ornstein-uhlenbeck like process. In Jacob Abernethy and Shivani Agarwal (eds.), Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pp. 483-513. PMLR, 09-12 Jul 2020.
Etienne Boursier, Loucas Pillaud-Vivien, and Nicolas Flammarion. Gradient flow dynamics of shal- low relu networks for square loss and orthogonal inputs. arXiv preprint arXiv:2206.0099: 2022.
Emmanuel J Candes and Yaniv Plan. Matrix completion with noise. Proceedings of the IEEE, 98 (6):925-936, 2010.
Emmanuel J Candès and Benjamin Recht. Exact matrix completion via convex optimization. Foun- dations of Computationnal mathematics, 96))7117777,, 2009.
Emmanuel J Candès, Xiaodong Li, Yi Ma, and John Wright. Robust principal component analysis?
Journal of the ACM (JACM), 58(3):8833))) 2011.
Alex Damian, Tengyu Ma, and Jason Lee. Label noise SGD provably prefers flat global mini- mizers. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 77449-27466 Curran As- sociates, Inc., 2021.
Mark A Davenport and Justin Romberg. An overview of low-rank matrix recovery from incomplete observations. IEEE Journal of Selected Topics Signal Processing, (0(4):608-62) 2016.
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai Gradient descent finds global minima of deep neural networks. In International Conference on Machine Learning, pp. 1675- 1685. PMLR, 2019.
Massimo Fornasier, Holger Rauhut, and Rachel Ward. Low-rank matrix recovery via iteratively reweighted least squares minimization. SIAM Journal Optimization, 21(4);1614-1640, 2011.
Spencer Frei, Yuan Cao, and Quanquan Gu. Provable generalization of sgd-trained neural networks of any width in the presence of adversarial label noise. Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference Machine Learning, volume 139 of Proceed- ings of Machine Learning Research, pp. 3427-3438, PMLR, 18-24 Jul 2021.
Rong Ge, Furong Huang, Chi Jin, and Yang Yuan. Escaping from saddle points-online online stochastic gradient for tensor decomposition. In Conference learning theory, pp. 797-842. PMLR, 2015.
Rong Ge, Jason D Lee, and Tengyu Ma. Matrix completion has spurious local minimum. In Advances in Neural Information Processing Systems, pp. 2973-2981, 2016.
Rong Ge, Chi Jin, and Yi Zheng. No spurious local minima in nonconvex low rank problems: A unified geometric analysis. In International Conference Machine Learning, pp. 1233-1242. PMLR, 2017.
Gauthier Gidel, Francis Bach, and Simon Lacoste-Julien, Implicit regularization of discrete gradient dynamics in linear neural networks. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché- Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, vol- ume 32. Curran Associates, Inc., 2019.
Daniel Gissin, Shai Shalev-Shwartz, and Amit Daniely. The implicit bias of depth: How incremental learning drives generalization. In International Conference on Learning Representations, 2019.
Ian Goodfellow, Yoshua Bengio, Aaron Courville, and Yoshua Bengio. Deep learning, volume 1. MIT Press, 2016.
10

---

Under review as a conference paper at ICLR 2023
Suriya Gunasekar, Blake E Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Sre- bro. Implicit regularization in matrix factorization. Advances in Neural Information Processing Systems, 30, 2017.
Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Characterizing implicit bias in terms of optimization geometry. In International Conference on Machine Learning, pp. 1832- 1841. PMLR, 2018.
Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In International conference on machine learning, pp. 1225-1234, PMLR, 2016.
Wei Hu, Lechao Xiao, Ben Adlam, and Jeffrey Pennington. The surprising simplicity of the early- time learning dynamics of neural networks. In H. Larochelle, M. Ranzato, Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp- 17116-17128. Curran Associates, Inc., 2020.
Arthur Jacot, François Ged, Franck Gabriel, Berfin Şimşek, and Clément Hongler. Deep linear networks dynamics: Low-rank biases induced by initialization scale and 12 regularization. arXiv preprint (tt.::200..19333, 2021.
Ziwei and Matus Telgarsky, Directional convergence and alignment in deep learning. In
H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neural Infor- mation Processing Systems, volume 33, pp. 17176-17186. Curran Associates, Inc., 2020.
Liwei Jiang, Yudong Chen, and Lijun Ding. Algorithmic regularization in model-free over- parametrized asymmetric matrix factorization. ArXiv, abs/2203.02839, 2022.
Dimitris Kalimeris, Gal Kaplun, Preetum Nakkiran, Benjamin Edelman, Tristan Yang, Boaz Barak, and Haofeng Zhang. Sgd on neural networks learns functions of increasing complexity. In H. Wal- lach, H. Larochelle, A. Beygelzimer, d' d'Alché- Buc, E. Fox, and R. Garnett (eds.). Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
Dionysios S Kalogerias and Athina P Petropulu. Matrix completion in colocated mimo radar: Re- coverability, bounds & theoretical guarantees. IEEE Transactions on Signal Processing, 62(2): 309-321, 2013.
Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal- gradient methods under the polyak-tojasiewicz condition. In Joint European conference on ma- chine learning and knowledge discovery in databases, pp. 795-80 811. Springer, 2016.
Jason D Lee, Max Simchowitz, Michael Jordan, and Benjamin Recht. Gradient descent only converges to minimizers. In Conference on Learning Theory, pp. 1246-1257, 2016.
Xingguo Li, Junwei Lu, Raman Arora, Jarvis Haupt, Han Liu, Zhaoran Wang, and Tuo Zhao. Sym- metry, saddle points, and global optimization landscape of nonconvex matrix factorization. IEEE Transactions on Information Theory, 65(6):3449-355 2019.
Yuanzhi Li, Tengyu Ma, and Hongyang Zhang. Algorithmic regularization in over-parameterized matrix sensing and neural networks with quadratic activations. In Conference On Learning The- ory, pp. 2-47. PMLR, 2018.
Zhiyuan Li, Yuping Luo, and Kaifeng Lyu. Towards resolving the implicit bias of gradient descent for matrix factorization: Greedy low-rank learning. International Conference on Learning Representations, 2020.
Zhiyuan Li, Tianhao Wang, and Sanjeev Arora. What happens after SGD reaches zero loss? -a
mathematical framework. In International Conference on Learning Representations, 2022.
Kaifeng Lyu and Jian Li. Gradient descent maximizes the margin of homogeneous neural networks. In International Conference on Learning Representations, 2020.
Kaifeng Lyu, Zhiyuan Li, Runzhe Wang, and Sanjeev Arora. Gradient descent two-layer nets: Margin maximization and simplicity bias. Advances in Neural Information Processing Systems, 34:1 14.19998-12991 2021.
11

---

Under review as a conference paper at ICLR 2023
Kaifeng Lyu. Zhiyuan Li, and Sanjeev Arora. Understanding the generalization benefit of normal- ization layers: Sharpness reduction. arXiv preprint arXiv:2206.07085. 2022.
Mor Shpigel Nacson, Suriya Gunasekar, Jason Lee, Nathan Srebro, and Daniel Soudry. Lexico- graphic and depth-sensitive margins in homogeneous and non-homogeneous deep models. In International Conference on Machine Learning, pp. 46834444488 4692..4662222 PMLR, 2019.
Thanh Ngo and Yousef Saad. Scaled gradients grassmann manifolds for matrix completion. Advances in neural information processing systems, 25, 2012.
Yigang Peng, Jinli Suo, Qionghai Dai, and Wenli Xu. Reweighted low-rank matrix recovery and its application in image restoration. IEEE transactions cybernetics, (1211))):1182430) 2014.
Noam Razin, Asaf Maman, and Nadav Cohen. Implicit regularization in tensor factorization. In International Conference on Machine Learning, pp. 8913-8924, PMLR, 2021.
Noam Razin, Asaf Maman, and Nadav Cohen. Implicit regularization in hierarchical tensor factor- ization and deep convolutional neural networks. arXiv preprint arXiv:2201.11729, 2022.
Benjamin Recht, Maryam Fazel, and Pablo A Parrilo. Guaranteed minimum-ran solutions of linear matrix equations via nuclear norm minimization. SIAM review, 52(3):471-501, 2010.
Mark Rudelson and Roman Vershynin. Smallest singular value of random rectangular matrix. Communications on Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences, 62(12):1707-1739 2009.
Xiaohui Shen and Ying Wu. A unified approach to salient object detection via low rank matrix recovery. In 2012 IEEE Conference Computer Vision and Pattern Recognition, pp. 853-860. IEEE, 2012.
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The im- plicit bias of gradient descent on separable data. Journal of Machine Learning Research, 19(70): 1-57, 2018.
Dominik Stöger and Mahdi Soltanolkotabi. Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstruc- tion. Advances in Neural Information Processing Systems, 34, 2021.
Ruoyu Sun. Optimization for deep learning: theory and algorithms. arXiv preprint
arXiv:1912.08895, 2019.
Nadav Timor, Gal Vardi, and Ohad Shamir. Implicit regularization towards rank minimization in relu networks. arXiv preprint arXiv:2201. 12760, 2022.
Tian Tong, Cong Ma, and Yuejie Chi. Accelerating ill-conditioned low-rank matrix estimation via scaled gradient descent. J. Mach. Learn. Res., 22:150-1, 2021.
Stephen Tu, Ross Boczar, Max Simchowitz, Mahdi Soltanolkotabi, and Ben Recht. Low-rank so- lutions of linear matrix equations via procrustes flow. In International Conference on Machine Learning. pp. 964-973. PMLR, 2016.
Per-Ake Wedin. Perturbation bounds in connection with singular value decomposition. BIT Numer- ical Mathematics, 12(1):99-111, 1972.
Ke Wei, Jian-Feng Cai, Tony F Chan, and Shingyu Leung. Guarantees of riemannian optimization for low rank matrix recovery. SIAM Journal on Matrix Analysis and Applications, 37(8):1198- 1222, 2016.
Blake Woodworth, Suriya Gunasekar, Jason D Lee, Edward Moroshko, Pedro Savarese, Itay Golan, Daniel Soudry, and Nathan Srebro. Kernel and rich regimes in overparametrized models. In Conference on Learning Theory, pp. 3635-3673. PMLR, 2020.
Huan Xu, Constantine Caramanis, and Sujay Sanghavi. Robust pea via outlier pursuit. Advances in neural information processing systems, 23, 2010.
12

---

Under review as a conference paper at ICLR 2023
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):107- 2021.
Bo Zhao, Justin Haldar, Cornelius Brinegar, and Zhi-Pei Liang. Low rank matrix recovery for real-time cardiac mri. In 2010 ieee international symposium on biomedical imaging: From nano to macro, pp. 996-999. IEEE, 2010.
Zhihui Zhu, Qiuwei Li, Gongguo Tang, and Michael B Wakin. Global optimality in low-rank matrix optimization. IEEE Transactions Signal Processing, 66(1 66(13):311433623 2018.
Zhihui Zhu, Qiuwei Li, Gongguo Tang, and Michael B Wakin. The global optimization geometry of low-rank matrix optimization. IEEE Transactions on Information Theory, 67(2):1308-1331, 2021.
Wenbin Zou, Kidiyo Kpalma, Zhi Liu, and Joseph Ronsin. Segmentation driven low-rank matrix recovery for saliency detection. In 24th British machine vision conference (BMVC), pp. 1-13, 2013.
13

---

Under review as a conference paper at ICLR 2023
Appendix
Table of Contents
A Preliminaries
15
A.1 The RIP condition and its properties
15
A.2 Matrix analysis
15
A.3 Optimization... ....aaiiio......................
16
A.4 Proof Proposition 3.2
B Main idea for the proof of Theorem 4.1
17
B.1 Heuristic explanations of the decomposition
17
B.2 Proof outline
18
C Proof of Lemma B.1
19
C.I The spectral phase
19
The parallel improvement phase
21
C.3 Induction
26
C.4 The refinement phase and concluding the proof of Lemma B.1
27
D Auxiliary results for proving Lemma B.1
30
D.1 The spectral phase
30
D.2 The parallel improvement phase
31
E Proof results in Section
F Proof of Theorem 4.1
37
G The landscape of matrix sensing with rank-1 parameterization
39
14

---

Under review as a conference paper at ICLR 2023
The appendix is organized follows: in Appendix A we present number of results that will be used for later proof. Appendix B sketches the main idea for proving our main results. Appendix C is devoted to rigorous proof of Lemma B.1 ,with some auxiliary lemmas proved in Appendix D. In Appendix E. we analyze the landscape of low-rank matrix sensing and prove our results Section 5. These results then used in Appendix F to prove Theorem 4.1. Finally, Appendix G studies the landscape of rank-1 matrix sensing, which enjoys a strongly convex property, as we mentioned in Section without proof.
A PRELIMINARIES
In this section, we present some useful results that is needed in subsequent analysis.
A.1 THE RIP CONDITION AND ITS PROPERTIES
In this subsection, we collect a few useful properties of the RIP condition, which we recall below:
Definition A.1 We say that the measurement A satisfies the (RPP condition if for all matrices Z Rdxd with rank (Z) S r, we have
2 < |A(Z) (1 8) 2
The key intuition behind RIP that A I, where A 4 7 Σm v is the adjoint of A. This intuition is made rigorous by the following proposition:
Proposition A.1 (Stöger & Soltanolkotabi, 2021, Lemma 7.3) Suppose that A satisfies (r, 8--RIP, then for all symmetric matrix Z of rank S r 1. we have
[[A z) Zll
A.2 MATRIX ANALYSIS
The following lemma is direct corollary of Proposition A.I and will be frequently used in our proof.
Lemma A.1 Suppose that the measurement A satisfies (6, 2r, + R)-RIP condition, then for all matrices U E gddxr such that rank (U) I Tw, we have
(AtA- (XX UU S [| + (101)))
In our proof we will frequently make use of the Weyl's 'ss inequality for singular values:
Lemma A.2 (Weyl's inequality) Let A,A E ddxd be two matrices, then for all 1 I S d. have
(A) a + A) S ||||
We will also need the Wedin's sin theorem for singular value decomposition:
Lemma A.3 (Wedin, 1972, Section 3) Define R(-) to be the column space of a matrix. Suppose that matrices B A + T, A,, B, are the top-s components the SVD of A and B respectively, and A A A, Bo B B 1f 8 amin (B)) o Quax AA)) 0, then we have
|
sin e (R(A)) R(B)))
where ((.,)) denotes the angle between two subspaces.
Equipped with Lemma A.1, we can have the following characterization of the eigenvalues (recall that M A" AA*AAXXX (XXT))
15

---

Under review as a conference paper at ICLR 2023
Lemma A.4 Let M A'A((XX)) and M _ be the eigen-decomposition of M. For $ i & we have
o - of < 61|
Proof :By Weyl's inequality we have
S M xx | x| of - o
as desired.
A.3 OPTIMIZATION
Lemma A.5 Suppose that a smooth function f E R b R with minimum value f > -00 satisfies the following conditions with some 0:
(1). limpall->oo f(x) +oc.
(2). There exists an open subset S C Ih'h such that the set S of global minima of f is contained in S. and for all stationary points a of f in Rm SS, have f(x:) f 2 2e on Os.
S, we have f(z) f 2e. Moreover, we also
Then have
tor E R' f(x) se
Proof: Let xx the minimizer of f on RTM exists. Moreover, since any local minimizer of a function defined on compact set must either be stationary point or lie on the boundary of its domain, we can see that either E OS or V ff(x") holds. By condition (2), either cases would imply that f(x") f 2 2e, as desired.
By condition (I) we can deduce that xt always
Lemma A.6 Let fxx) (vn) C IR" be two sequences generated by 2x+1 IK f(*)) and yk+1 yk V (Vy)). Suppose that | < B and ||y:|| I for all i and f is L-smooth in
(x E R" - S B}. then we have
|00E yM S (1 1L)* x0 yoll
Proof: The update rule implies that
x yk+il
[3x yk - -Vf + (V)())
< [ ynll # f f(yw)l
I (1 + pL) yk
which yields the desired inequality.
A.4 PROOF OF PROPOSITION 3.2
Proposition 3.2 immediately follows from the following result:
Proposition A.2 (Rudelson Vershynin, 2009) Suppose that all entries Of E Rddx are indepen- dently drawn from N (0, + and p _f-_/=__ then Jmin (Vx.U) U) p with probability at
Jr
least 1 - - (Ce)r=at s+1 Here c, C > are universal constants.
By Proposition A.2, we have
2c P 31 SISSSPANE s.t. Jmin (VI
r
Prr.
P Omin (VI < Vr / -
Vr
pAr.
or + (Ce)r-ot1) < (r -or Cc)
which concludes the proof of Proposition 3.2.
16

---

Under review as a conference paper at ICLR 2023
B MAIN IDEA FOR THE PROOF OF THEOREM 4.1
In this section, we briefly introduce our main ideas for proving Theorem 4.1. Motivated by Stöger & Soltanolkotabi (2021), we decompose the matrix U, into parallel component and an orthogonal component. Specifically, we write
U, U.W.W. U,W. W.W.
(8)
parallel component
orthogonal component
where W, = WVZ U, E R is the matrix consisting of the right singular vectors of Vx, U (Definition 3.1) and Wi,1 E (Rf is an orthogonal complement of W. Our goal is to prove that at some time t, we have x, (U,U, X,X,) = later, these imply that |U X,X, R The remaining part of this section is organized as follows: in Appendix B.1 we give a heuristic explanation for considering (8), and in Appendix B.2, we present our proof outline.
and ||, = 0. As we will see
Additional Notations. Let Vx,.1 Rdx(d=s) be orthogonal complement of Vx, E Rdxs
Let Σ, diag(T),...... and Es = diag(os+1....... We use A, (A* A- - [xx T,U.)) denote the vector consisting of measurement errors for XX -U,U
B. HEURISTIC EXPLANATIONS OF THE DECOMPOSITION
simple and intuitive approach for showing the implicit low rank bias is to directly analyze the growth of Vx U, versus V Vx._1 Ur. Ideally, the former grows faster than the latter, that GD only learns the components in X.
By the update rule of GD (3),
VX U141 VX.. I
- -,UT) U. =VX III+xXX -U,U,]] U, VX A.U,
=.,11
=.
= =G.,1 + +.G.2.
For the first term G..1. we have
G..1 = WE
(I+ VV,
+ O
where the last term O²²2) is negligible when μ is sufficiently small. Since |E 0s41, the spectral norm of G1, can be bounded by
|Ga || & |
V Uul II- -UU 0 < {1 ( X V
U.l + 0
However, the main difference with the full-observation case (Jiang et al., 2022) is the second term G1 = VX,__ A,U, Since the measurement errors A, small but arbitrary, it is hard to compare this term with I U141 As a result, we cannot directly bound the growth [IV U.|]
However, the aforementioned problem disappears if we turn bound the growth of | x U441 W. To see this, first we deduce the following by repeatedly using VX U,W 0 due to the definition of W...
G..1 W. VI.. x NU.U,T U.W.L.
= -Vx,, (I+ JUW -UVI i
- - U.W.W,WW + W. W.T.T. W. =(I+WE VV. UI U.W.
(I++EE
-RVE U.W.W. U.
17

---

Under review as a conference paper at ICLR 2023
Gt, UXU,A,WW,W VX A.Vx VX U.W.L
So we have the following recursion:
VX. W111
(I+ E UV A.Vx,. U.W
W.. U.W. U.W.))
- -VV - U.W.W,WWWW U, U.W. 1+ +0(12)
We further note that VX W VX U W.W, W4L1 VX,, U441 W M.Ti W, WTI,L (9)
which establishes the relationship between x., U241 W., and Vx., U-11 W1111 I. To complete the proof we need to prove the following:
The minimal eigenvalue of the parallel component U,W,W, grows a linear rate with speed strictly faster than ds+1.
The term
VX Vu.w.
< 1, which implies that the first term in (9) is negligible.
B.2 PROOF OUTLINE
An important intermediate step of our proof is the following result:
Lemma B.1 Under Assumptions 3.1 and 3.2, if initialization scale a is sufficiently small, then for all 1 S s S A T, there exists a time T E B. such that
X,X_ Ur
UrgU Ura 1| S R² 1
We begin with the spectral alignment phase, where we can make the following approximation
U2+1 (I + pM)U
(I0)
since U, is initially small. At some time = To. U2 would become approximately aligned with the first components, as long there is positive gap between the s-th and (s + 1)-th largest eigenvalues of M. The choice of To is subject to a trade-off such that the alignment takes effect while (10) does not induce large error.
We then enter the second phase which we call the parallel matching phase, in which the parallel components grow constant magnitude and is well-matched with the ground-truth (the orthog- onal components remain small). Specifically, for small constants G, 1 S < 3, we show that the followings are true in this phase:
Xx (1). Mmin (VI, U,) grows exponentially fast until it reaches e og for some constant at some time
T.. Specifically, we have
Tmin VV,U+++ Uz+1 W.) 2 Jmin VX, U.) (1 + no= - no (VX, U.))
(2). When & Ts, the growth speed of (,U.W.,. || is slower than of (VX, U.): W < (1 + po + 02) WU
(3). VX Ve,w, remains true until / t T..
These statements will proven by induction. At l T., we have amin [V, U.) = 0(1), and we enter the refinement phase in which we show that the quantity VX (U,U, - xxx,,)
decrease exponentially until it reaches (18). Note that in general GD would not converge to an neighbbogoor
X,X_ as the initialization scale a O, because X,X_ is not the rank-s minima of the RIP loss. As a result, in the refinement phase we can only expect to obtain |U,U," X S poly(r)
To conclude the proof of Theorem 4.1, we prove in Section 5 that the landscape of the matrix sensing loss with rank-s parameterization, though non-convex, satisfies a local Polyak-Lojasiewicz (PL) condition within neighborhood of constant radius. As result, for sufficiently small 8, GD converges linearly to global minima with good initialization. We then show that within a time period after the refinement phase, the GD trajectory is close to the trajectory of well-initialized GD for rank- s parameterized matrix sensing. The length of this period goes to infinity when a + O, thereby implying that GD finds the rank-8 minimizer with o(1) error. The details are given in Appendix F.
18

---

Under review as a conference paper at ICLR 2023
C PROOF OF LEMMA B.1
In this section, we give the full proof of Lemma B.1, with some additional technical lemmas left to Appendix D. Appendices C.I and C.2 are devoted to analyzing the spectral phase and parallel improvement phase, respectively. Appendix C.3 uses induction to characterize the low-rank GD trajectory in the parallel improvement phase. In Appendix C.4 study the refinement phase, which allows us to derive Lemma B.I.
C.I. THE SPECTRAL PHASE
Starting from small Uo aU, < first enter the spectral phase where GD behaves similar to power iteration. As in Stöger Soltanolkotabi (2021), we refer to this phase as the spectral phase. Specifically, we have in the spectral phase that
U2+1 (I+ + (A" A) (XX* - U,U,)) U, = ((
The approximation holds with high accuracy long as ||U: < 1. Moreover we have M (A" A) ( =
XX by the RIP condition; when is sufficiently small, we can still ensure positive eigen-gap gap of M. As result, with small initialization U, would become approximately aligned with the top eigenvector of M. Since || - XX (T.)r.) by Proposition A.1, we have ||æu will = (r.) so that Vx, Vu.w = ((6 This proves the base case for
the induction.
Formally, we define M = A*A(XX)), Z, - + nM and Ü, Z,Up. Suppose that M E(ank(Mr) 0.00 is the spectral decomposition of M. We additionally define M, Li=1 ( 0. By Lemma A.4 and 6/r, - 10 3 as stated in Lemma B.1, we have o. 2 G. 0.017 and 8,+1 2 Fe+1 + 0.01T, where T d, Js+1 Additionally, let L, be the span of the top-s left singular vectors of U,. We make the following assumption on the initialization, which holds with high probability when is i.i.d. Gaussian:
Assumption C.1 The matrix VM, U E Raxr has full row-rank iee. p Omin (VM, U) > 0.
Let
;= min fi {iEN: (U-I-UU-1) T
the following lemma bounds the error of approximating U. via U.:
Lemma C.1 (Stöger Soltanolkotabi, 2021. Lemma 8.1) Suppose that A satisfies the rank-1 RIP with constant ó1. For all integers such that 1 S t* it holds that
| = U. T.|l s 40 2
2r (1 + 6,) +1+ (1+) 31 |1i1.
(1I)
Corollary C.1 We have
log a 2 log po? log (1 + m
Proof: By Lemma C.I we have
||E S 40, aa²r. (1 51) (1 + mo?) 31 ||i11
for S tn On the other hand, we have
Ü = [| HMM
2 a(1 + μa?) U
> (1 + uuō?)² ap.
Thus, follows from Er-1 > U that
log n0?
po?
log a(1t))r.
+ (1+))
a + 1²
V 4(1 + 6n (r)r1 U|
log (1 (1a))
as desired.
19

---

Under review as a conference paper at ICLR 2023
Lemma C.2 There exists a time
2 llog -1 + log (1+6)
1 = To =
1sa
3 log(1 + mo7) log(1 + u s+1)
such that
U² Σ a(1 + 2o? a
where y = llog( (+p log 1+
Proof: It's easy to check that To S t* by applying Corollary C.I.
We consider the following decomposition:
U. a(1 vo?) U $ U. U Ú. Σ a(1 + 1o?)
When S 1", the first term can be bounded as
E - 40 (1 51) (1+ (1+))
For the second term we have
Ú, Σ a( 20
S
Σ a(1 107) U
Sa (1 + (1+10²++1) "
1=
In particular, the definition of To implies that
U,
Σ a(1 + (o7) U
Zaz
as desired.
We conclude this section with the following lemma, which states that initially the parallel component U, W, would grow much faster than the noise term, and would become well-aligned with X
Lemma C.3 The following inequalities hold for t = To when a S 4x is sufficiently small:
||U||| < |X||
(12a)
Lo (n
mmin (UZY W vb) 2 p poly(r.)- -I. 3logis log(
(12b)
IIT, W To 1 - poly(r.) a Slogl bolll
(12c)
|| 1 VUr, Wo, < 2005
(12d)
Proof: We prove this lemma by applying Corollary D.I t To defined in the previous lemma. The inequality (12a) can be directly verified by using Lemma C.2:
|U,| S + (L+) To + a S (rly n/3 < X For the remaining inequalities, we first verify that the assumption in Corollary D.I: aa,(Z.) 10 (aa.+1 (Zx) EE))))
(13)
By definition of Z,, we can see that
a0 (Z.,) + Era S a (1+ pO² TTD + ET,
S a S 0.1ppx
Flog(1+ logt
0.laao, (ZT.)
20

---

Under review as a conference paper at ICLR 2023
when prly((x) ) that (13) holds. As result, have
ax (U, > 0.400, (Ze) muin (V
> 0. (rx)y(r=) ap (1 + )
2 p alog(1+p00)) (10o--00))1l0((+-1111
U < (10 (4)1 B
2log(++103
(14)
a
3lo((+ +oxl)+me3+1)
8 000+1 (Z)) U +
Ee
V Vo.w.
& 100
app (Ze)
alog 21oog tw0
$ 100
da F louel 126 2-11
2006.
The conclusion follows.
C.2
THE PARALLEL IMPROVEMENT PHASE
C.2.1
THE SIGNAL TERM
In the following we estimate Jmin (VX, lemma below.
Uc+1 W.). We state our main result of this section in the
Lemma C.4 Suppose that VX, U, RRer is of full rank, μ < 10-11 c3 10-3
U,U,) )||
10 x0= and [Vxx Vo.w, S C32 then we have
Omin (Vx, U2+1) 2 mmin (V, U W.)
2 (1 (5cg 206 X (12) 500p (|x))) (1 po U.) Mmin (VX, U.).
Proof: The update rule of GD implies that
VX, WWtWW
-Vx, ([+
= =VX, (I+ - U,U, ) U.W.
(15a)
= =(++NE)) U,W:-MV, U,U, U,W, + U,W,
+WV A,U.W,
(15b)
U.W.W. -UJU, Vx, +NVI A,W,W
Vx.. V U.W,
= + U.W.(I uw, U. Vx. VX, U.W. + + A,U,,
-NVJU.T Vx.. V + Nr V U.W.W, U, Vx, U.W.
(15c)
where (15a) follows from XX - X,X VX X and X. 0:
(15b) follows from VX. X,X = VI. Vx. E. = E.V and (15c) follows from VX U, V W.W.W. + +V, W.W. =V. U.W.W, by definition of W, and W.,
We now relate the last three terms in (15c) to V U.W, Since VJ U,W, is assumed to be invert- ible, xx VU.,, Ev, w. and W..,,, thus have
U.W. = (V U.W.) VV. U.W,
= U.W, (VX, Vo,w Wu, WT...) VVV
(16)
= Vu.w. (VI, Vu.w.) VI.
'VF U.W.
21

---

Under review as a conference paper at ICLR 2023
Plugging (16) into the second and third terms of (15) and re-arranging, we deduce that
VX, S.UiiW W
-( PI P2)) VX U.W. U, Vx, U.W,W.
+ ( + + P3) VX, UWW, U, Vx VX U,W.
= I + P1 + Pb) + +H² ( +1t + P2) VX U.W.W U, -V U.W,W, Vx.) ) -
VX U. - ,w, U. Vx, VX U.W)
(17)
where the equation A (I - ) (ATT)-A(E A(I PATA with A VX,U (when
1 9 x112 1 pAA T is invertible), and
P VX U,U, VX Vuew, (VX, Vu.w.)
(18)
P: VX A, Ve,., (VX, Vu...)
By assumption we have
min (VX, Vu.w.) 2 V1- VX,. vo:wal || 2
so that
P VX, U,U, Vx,, ||. 1 Vu.w, || 11V..V Vu.w:) -1 < (19)
<||||
and by our assumption we have
|| - x, Vu.w,) "1 S 10 1
(20)
Moreover,
note that
|2
| and when
have
10
X
[|1 - U.W.W, Vx.) 1-11
2. Thus
1 Pi P3) U.W.W, U.W.W.W,UU. (I UVW.V, U, Vx.) - 500|
The equation (18) implies that
Mmin
(V.
U W.)
[ + 1 P. + P3 ( P1 + P3) VX WWW. (I - -V- V.
miin
(VX, U, W. W., U, Vx. VX U.W.))
Mmin
2 (1 + 21o (E,) /1| ||||| Pal| - 500 X (1 miin (V), U.) (1 no (Vx, U.)
(1 + n 1|| P|| || - |0|| Pa||
500,²² 500 Tmin (V, U.) (1 pomin (Vx, U.)
Recall that P1 and P2 are bounded in (19) and (20) respectively, so we have that
mmin Vx, U+11)
2 Omin (Vx, U Wi)
> (1 / (o (5cg 206) |²) 500,² (1 iio (VX, U.)) mmin (VX, U.).
The conclusion follows.
The corollaries below immediately follow from Lemma C.4.
Corollary C.2 Under the conditions in Lemma C.4, if om (VI, U.) < 0.3(0, - -02+1) 0.3k - 12, then we have
mmin (Vx, U2+1) 2 ( Fmin (VI U,).
Corollary C.3 Under the conditions in Lemma C.4, if
2
min (V U, 0² - 50(cs + 8x11
X,
then have that minn V U U++) 2 0 min (V U.).
22

---

Under review as a conference paper at ICLR 2023
C.2.2
THE NOISE TERM
In this section we turn analyze the noise term. The main result of this section is presented in the following:
Lemma C.5 Suppose that Vx, U. W. E ERer is of full rank,
[Vx,,, Vu,wi S 0g < 10 30-
and
[(XX U,U, )l 5 xx
then have
[0e+1 W & (1 no + 30 x1 + 0.1 x1 W.W.W.lll
Proof: : By the definition WT we have VX, U.W = 0, thus [U,
N.W.U.W.... The latter can be decomposed as follows:
VX UiLUU11WHLL. U W.W, WTt1
W W. WT111
=(a)
In the following, we are going show that the term (a) is bounded by j where e is small constant, while (b) grows linearly with a slow speed.
Bounding summand (a). Since
0 = Vx, Ue+i W = VX, U WoW, W + VX, W W. WTI11 by definition, we have
W. WL+11 = (VX U2i1 VX U44 W. WT, W4L11
(21)
Thus the summand (a) can be rewritten as follows:
V U4A W, W.W. WTHLL
=-V,, U.+1 W. (Vx, U2+1 U++ W., W. W.HL
U+I
(22a)
=-VX.. UC+1 W. (VX, VoL. W. EU W.)...)) VX U4I Wi, W. W4I11
= =VVX.. VU.. w. (Vx, VUL.iW.)
UKUUWi W. WTL1
(22b)
VX,, VU w. (Vx, VU.. w.)
-1 VX, AA+ - U,U))) U.W. W.
W1111
= =-VVI, Vu W. (V,, Vue...)
-1 Vx, [xXX - -,,,)) + A,] U.W. W. W
(22c)
= = Vo (Vx, Vo....)
VX. [U.UU - U.W, W. WHIL
=uVI. Vol.., (VX, Vo....)) M, U.W. WT W. W1L.1
where M1 VX, [UU, Vx.. A, V. In (22), (22a) follows from (21), (22b) holds since
EU., W. WT U.L.W. E Raxx is invertible, and in (22c) we use VX U.W.LL = 0. follows that
[[(a]] < p Vi Voen
(Vx. Vu. wu.)..) " V
(23)
By Lemma D.4 we have
VT Vu.... S 0.01, which implies that
- 1 +
(Vx, Vu.. - - (Vx, Vu
= (1 VI.. Vel Von.will
2 (24)
23

---

Under review as a conference paper at ICLR 2023
Lastly, we bound M1 follows:
| S Vx, UUU Vx.. ||AA
I -1 - U
VV U.W.ll V| U.W. + +1003x-'es 2
(25)
- x0 c3
where the second inequality follows from our assumption on 1A4AA1) -,U,) Combining (23), (24) and (25) yields
[I(a)]| s 20p||x
Bounding summand (b). This is the main component in the error term. We'll see that although this term can grow exponentially fast, the growth speed is slower than the minimal eigenvalue of the parallel component.
We have
VX, W41
VX... [+x(XXX - -0AA- -U,)) U.W.
(26a)
I+ WVV -VV U,U, V
+ VV
A.VX...
U.W
(26b)
=.M.
-1++ U.W.W U VX..1 + MM) N...U.W.. 11-WWLU W.W...)
(26c)
+ + E VX U,W.W, U, Vx. + M2) VX U.W. W. U.W. (26d)
where recall that Σ diag(o.+ from the update rule of GD, (26b) is obtained from VX XX = -,, VX and U,W. =
0 -: 0z,0,... 0........ ,0) (dd-)) In (26), (26a) follows
Vx, VX. U.W Vx,,1 VX,, U.W. Vx,. Vx,,1 U,W,LL and lastly in (26d) we use
V V..VV VX, U.W.
=VX U.W.W, U, X. U.W. U.U.UUWW W. U, W.
U.W
=V VV U. VX.. VX U.W VX.. U.W, W. U.W.
follows that
V U- W.,Ll
(|| p U.W, U, +|
M| V U,W. - (I- all VI.. U.W,
+ JU,,,, 11 (02+1 + U, 2 + 10- X 13)
(1 (1+ مor + M2 U.W (I (I- 11) 1
|
|U, (1 f + /r 2
To summarize, we have
|U W WHilll $ +1 + 30 X + 0.1 We.lllll
as desired.
To bound the growth speed of the orthogonal component, need to show that the quantity VT. Vu,w, remains small. The following lemma serves to complete an induction step from
t:
Lemma C.6 Suppose that Vu.wl. I c3 and [ I C₁. with
max (Cs, call ||ll < 10 10-3x-1 and (A'' ( U,U,T <
10 30-3 - 1
(where K is the condition number defined in Section 3.1) and μ < 10 4x V x... V Win S c3.
X ?cg then we have
24

---

Under review as a conference paper at ICLR 2023
Proof: Let M, A'X - U,U,)), so the update rule of GD implies that (I W.)u,.
U1+1 W 141
(I HM) (U,,W, + W,W
= =(I (M) (Vu.w, V..w U.W,W, W + UUW,, W Wo+1)
(I + (M PiVo.w V VU.W U,W,W, W4+1:
where
P= U.W, W. WHI (VU, U.W.W, W++1) VU.w.
and V.W. U, W, W4+1 is invertible since VU,, U,W, is invertible by our as- sumption that Vx, U, is of full rank and rank (U, W)) 2 rank (Vx, U,W.) = rank (VX, U,) 8, and W, W4+1 is invertible by Lemma D.6 and the assumptions on and A [XX U,U,) I||
The key observation here is that because the (square) matrix VT U,W.W, W is invertible, so that the column space of U,+1 W is the same as that of Z. Following the line of proof of (Stöger & Soltanolkotabi, 2021, Lemma 9.3) (for completeness, we provide details in Lemma D.7), we deduce that
L V.G.W...l = VX
V2 l
Vx..1
I I+B
Vu.w. Vu.w (B (B+ (B+BT) Vu.w, - BVu.w, Vu.w. (B B (B+BJ) Vo.w. + +D
2
1
Vx
I B
- Vu.w. Ve,w. (B (B+B1) Vu.w. + +2 |D||
2
(27)
where B = (I (I P) and D < 100 B By assumption we have
P < U.W, W W
min (U,W) min (W, W W+11)
< 2 W W4+1ll,
so that
|B - x(X - U,U
Sl|MM - (XX - -I0
A - W |I + | W. W
(28)
$ - - W4all
18p (10μ X 3 (4)
03 X --7=](44AA-)(0- XXxx U.U,))
18p (10 X 3 c1)
c3 X|| + 0.01px-1c9||XX
where we use Lemma D.6 to bound
W. W/ Let B = x(XXT U.U,) and R = (I ( B, - Vu.w, VJ, B1) Vu.w,, then we have
x
(xx R. -II (I p Vu.w. V..w (XXT -U,U,)) Vu.w
= =I++ VX. Vo.W (I -V.UV..W XX Vo.w.)
(29)
W.TUU.UUU - (I-V..w Vo,w.) U.W., W. U, VX.. VJ Vu.w,
+ + VI.. VV.WW Vo. XX Vu.w.
25

---

Under review as a conference paper at ICLR 2023
By Weyl's inequality (cf. Lemma A.2) and our assumption cg.
Jmin (V..w,X XX Vu,w.)
2 min (Vu.w. X,X, Vo.w.) - - X Vo.w.ll
2 min (VU, X,X, T Vu.w.) - -o.-1 Vx Vu.will
2 o Vu.. Vx, 1| 0
0,410
1
= - (o² + o 11
(0
+ o2+1)
2
So we have
R1 - -1-2 )(tz)) ( Ve.w. +..w.1+3300 + 3 + + 1|
4 [o
It thus follows from (27) that
x VU W.+1
< R || + 2 B - Bill + B1
< (1 H
2 102 - -o²+1) || Vu,w, || 40pcaca|| + 0.02ppx x|| + 10
Since VX..IVe.ww
S Cs. it follows from assumption
cs.
C3 Ca and f that
| VUL+iWer1
S cg as well, which concludes the proof.
C.3
INDUCTION
Let
T: -== = =in {t > 0: oiin (VX, Ua,+1) > 0.3 - - =.)
In this section, we show that when To S < Tū the parallel component grows exponentially faster than the orthogonal component. We prove this via induction and the base case is already shown in Lemma C.3.
Lemma C.7 Let max c4 -1 S 10-3x-1
S 10 cs and l S 10 x- -1 ||||| -2 Then the following holds for all To S Ta,s as long as a S poly(r)
Amin (VX, U++1)
2 mmin (VX, U++1 W.) 2 (1 + 0.5p (o: + 02+1) m (VX, Ua.) (30a)
1u 1 < min {{1 + (0.40² + 0.)0..1)) W,,
(30b)
1 Vu Witil S C3.
(30c)
rank (VX, U441) = rank (VX, U44 Wt) = s.
(30d)
Proof: The base case To is already proved in (12). Now suppose that the lemma holds for t,
we now show that it holds for t + 1 as well.
To begin with, we bound the term
A as follows:
A || = (AA'A - X T D,UTT
$ (A' - xXx U,W.W, [ - U,]
108 X| U.W., W.LuU U II.
s 106 X| 2 + 8 d (1 + 20.400 + 0.60 1-2 U WT..ll
By induction hypothesis, it's easy to see that
min (VX, U.)
2 Gmin (X, UT.)
2 poly(r) -
(31)
W
Ur, WT.
26

---

Under review as a conference paper at ICLR 2023
where
2 (log (1+ po²)) log (1 u
% 3 3og (1 + mO]) log (1 + pa
2 4x
x+11
Since must have min (VX, Xx U.) v 0.37 ((1) by definition of Ta it follows that W, S poly(r)a=*,, so for sufficiently small S poly(r) 1| S 116 I| holds.
The above inequality combined with our assumption on implies that the conditions on || in Lemmas C.4 to C.6 hold. We now show that (30a) to (30d) hold for / + 1, which completes the induction step.
First, since Ta we have miin (Vx, U2+1) S т. Moreover, the induction hypothesis implies that V Vu,.iW... I Cy and that Vx, Ua, of full rank. Thus the conditions of Corollary C.2 are all satisfied, and we deduce that (30a) holds.
Second, the assumptions on ca, c4 and 6, combined with Lemma C.5, immediately implies [|0+11 We S (1 + (0.40² + 0.6o [|U,W,,
As result, similar to (31) observe that
min (Vx, X, Ue+1)
Omin (VX, X, UT.)
[UT, Wi.lil 2 poly(r) a +.
|u++ W W1+1.ll
Since Omin (VX, U++1) S | when a < poly(r)-1 we must have that |1++ W S c4. Finally, Lemma C.6 implies that (30c) is true, and (30d) follows from application of Lemma C.4. This concludes the proof.
C.4 THE REFINEMENT PHASE AND CONCLUDING THE PROOF OF LEMMA B.
We have shown that the parallel component Juin U grows exponentially faster than the orthogonal component ||U Wi In this section, we characterize the GD dynamics after Ts. We begin with the following lemma, which is straightforward from the proof of Lemma C.7.
Lemma C.8 The following inequality holds when a S poly(r)-1 is sufficiently small:
Ug. W Wi.L < poly(r) att.
The following lemma states that in a certain time period after T. the parallel and orthogonal com- ponents still behave similarly to the second (parallel improvement) phase.
on a 1) when a + (here we omit the dependence of TV of a for simplicity) such that when 0 < t To < Es we have
Lemma C.9 There exists i O (log
Omin (V. U.) > min (U, 2 0.3r
(32a)
W.W S (1+ 40.400 + 0.60 1- Uf: Wr:
(32b)
Vx,,1 Vu.w || 5 C3.
(32c)
Proof: We choose to = min {t 2 0: U W +1, 2 < cs}
where
C = 10 10
1
X|
(33)
We prove (32) by induction. The proof follows the idea of Lemma C.7, except that we need bound A || in each induction step. Concretely, suppose that (32) holds at time then
A (AAA X U.U.))
DUW. (A'A () U,W.W, U, I W.
(34)
10 U.W., W.TUU II.
< 108 + dos / 30
27

---

Under review as a conference paper at ICLR 2023
where used the definition of Cs in the last step. As result, can apply the conclusion of Lemmas C.4 to C.6 which implies that (32) holds for + 1. Finally, combining Lemma C.8 and (32b) yields Tx = (1).
We now present the main result of this section:
Lemma C.10 Suppose that 0 S st tar VE Vu.wi S C3 and the conditions on C32 Ca. and p in Lemma C.7 hold, then we have
Vx (XxT - U U
1 (1- 2"T) || (XxT - -U,U,)1 20p |0 (6 + 5cg) + 2000p² Vril X|0
where we recall that r min SaghAr, -2.1 > 0.
Proof: The update of GD implies that
xx U411
= -xX - (I UI MM)
(I-UU, (XXT- -,U,) (I- (U,U)) tu A,U,U
=(1)
+ U.UU A, +1² (Et,1 + E1,2,
-(66)
where
VX, Edrllr = U,U, U.,,),, S VT. VX,
< $100 Vr
and
| = V/, () (xxT- - -,U,,) U,U (AAAA) -XXT-- S V== A) (XX-- - U,U,), U,U [(A*A) (XxT - U,V,)] < 10 |
Note that we would like to bound VX (XXT (4+1UU1)) We deal with the above three terms separately. For the first term, we have
Vx, (I -U,U, (Xx U,U,T) (I -U,
V (I (I-NU,U,) Vx. VX, (XX -U,,,) (XX)- (I- -U,,,,,)
+ VVV, (I -MU,UT V...VV (xx - -U,,.) (I- ---U,,,T)
< I - VVx, U.U. Vx. VX, (Xx-- - -U,U,)) || + V U.U. "UU,V..... VX,.. (XXT
- -U,U,))
(35a)
$ (1 u (U (,, min (Vz, Vu.w.)) VX, (XXT - U,U,T) + |000|||X|' (35b)
< 1 ) || [Xx_ - -U,,, }11 + 100 |||
(35c)
where in (35a) we use || nUU,U,T] || < 1, (35b) follows from
Gmin (VJ, U,U, (TU)) = amin (Vx, U.W.W, T,, Vx.) 2 minn U.,))
2 2 (U.W.)o min (VJ. Vu.w.)
and
U,V, VX. U.U, Vx,, ||=-1| V U.W.W, U. Vx.. || V 1. S.,,(U.11
28

---

Under review as a conference paper at ICLR 2023
and lastly (35c) is obtained from
min (Vx, V..w.) 21- VV Vu,w,
kaw.1122 1/22 cz.
For the second and the third terms, we have
[[ (' (xx* U.U.) U., +UU (I- UU!!)! 2 0.1x
(36)
where we use the estimate in (34), Combining (35) and (36) yields
Vx, -U+11
1 (1=
1 2 VI (xx - -U,,,) + |00 + 110p² /r.0//1
To apply the result of Lemma C.10, we need to verify that [|Vx.. Vu.will s 03 still holds when t 2 Th In fact, this is true as long as T: S O (log 2)-
We are now ready to present our first main result, which states that with small initialization, GD would visit the ( neighboooooo of the rank-s minimizer of the full observation loss i.e. X,X!
Theorem C.1 When poly(r.)- and 5 10 10-4*=1a cs with C3 < 10 10-3k 10-3x-'rr"" 'r.t time Ta E E4 such that
there exists
X X U.U, 1 1000-11 Vi.cs.
Proof: First, observe that for all t 2 0,
X.X, U.U, 11 -
X x _ - U,U,T) Vx, Vx. +
U,U, Vx, V
< X U.U,) Vx, VX +
U,U, VX
Vx [ U.W. 1|
2
< VX, (X,X²- - -U,,,) | Vr.
+ Va
Vx U.W.
x VX. (X.X. - ( X ||Vx Vo.w
(37)
We set 8 = 1003
2Tcs and
log (10-21 ||| X
th: T
(38)
log - wT)
then for small we have T3 < T3 +T (defined in Lemma C.9). Hence for Th S 1 < T we always have |Vx,,, Vu.w.ll S c3. By Lemma C.10 and the choice of c3 and 6, we have for T < t < T that
VV. - UU-UU S ) | (XXT U.U.) 150 Vrrros
which implies that
VX. (XXT - Ur. UT, < 400---1 Vr.c3.
Meanwhile, by Lemma C.9 we have ||U,W, < cs and VK_,, Ve.ww 5 c3 at Tg. Plugging into (37) yields
X U+. 12
< 400- |x|| VF.c3 + 2 +oVd.
By definition of 03 and cs we deduce that X
Up.10
UT 1:2 10 x 1T as de-
sired.
29

---

Under review as a conference paper at ICLR 2023
Corollary C.4 There exists constant 1 = (R, rx) such that
[U,Wa,1l & Cja
max 0StSTA
Proof:
The case of Ta directly follows from Lemma C.8. For t Ta know from Lemma C.9
that
U A.W.lls By (38), the second term is a constant independent of a, so the conclusion follows.
U
||
(1 + vo?)
D AUXILIARY RESULTS FOR PROVING LEMMA B.1
This section contains a collection of auxiliary results that are used in the previous section.
D.1 THE SPECTRAL PHASE
In the section, we provide auxiliary results for the analysis in the spectral phase.
Recall that N, (I + pM)² and U, U, E, NUU, + E, and Uo aU. Also recall that M = -i (M))((M)) 0 we additionally define M, = Ei m ú, Similarly, let Le be the span of the top-s left singular vectors of U, The following lemma shows that power iteration would result in large eigengap of U..
Lemma D.I Let p= minn M. U) O, then the following three inequalities hold, given that the denominator of the third is positive.
(U,)) 2 po., (2:) - -0st1
Z1 ||01])
- E.ll
(39a)
0++1 (U,) S .0..11
(2,) | + |EEl
(39b)
a0 Z |U|| + |
Vid Veul
(39c)
2r - (105+1 2, | + [E
apos
Proof: By Weyl's inequality we have
(U,) = Js+1 ((1 + (M) + E,1l
a0 ((1 (11+/0 UM) + ||E,|
< a0,+1 ((1 UU, +a [1 HM) - (1 pM.) ) U + E1
<a( + 1) |0] + |
Thus (39b) holds. Similarly,
(U,) ad, (N. V Mr U) a(1 ('.+I)* Eyll
ao, (N, mmin (ViT,, U) a(1 + (da+1) E
ap(1 + pd.)² a(1 u | -EEll..
Finally, note that write a(1 + PM,)' VM, (E,)) ViJ, U.
invertible
so that the subspace spanned by the left singular vectors of a(1 + 'M coincides with the column span of VM,,- Since L, is the span of top-s left singular vectors of U, we apply Wedin's 's sin theorem (Wedin, 1972) and deduce (39c).
The next lemma relates the quantities studied in Lemma D.1 with those that needed in the induction. The proof is the same as (Stöger & Soltanolkotabi, 2021, Lemma 8.4). so we omit here.
30

---

Under review as a conference paper at ICLR 2023
Lemma D.2 Suppose that VX Vz.
- 0.1 some 2 Then it holds that
1
as (U,W.) 2 20 (Ut):
(40a)
V Vu.w - 10 V Vi.ll, | S 20,+1 (U?).
(40b)
(40c)
Combining the above two lemmas, we directly obtain the following corollary:
Corollary D.1 Suppose that oa (N,) > 10 (000++1 (N+) + -1 (]), then we have that
0. (U,,), 2 0.4c0,,
(1)) min (V U)
I & 2 a00+1
Z: ||l||| + [Ell)
(41)
V Vu.w & 100 8 00 (Z.) | |U| + +|| ||
aspo, (Z,)
D.2 THE PARALLEL IMPROVEMENT PHASE
In the section, we provide auxiliary results for the analysis in the parallel improvement phase.
Lemma D.3 (Stöger & Soltanolkotabi, 2021, Lemma 9.4) For sufficiently small p. and 8, suppose that ||U,]| S X|}, then we also have ||U++a|| || S X||
Lemma D.4 Under the assumptions in Lemma C.5, we have
V\. Vu.,. w. (c3 + 10p|| I 0.01.
Proof: The proof of this lemma is essentially the same as (Stöger & Soltanolkotabi, 2021, Lemma B.I), and we omit it here.
0
Lemma D.5 Under the assumptions in Lemma C.6, we have
1
Gmin (VX, Ut-1) 2 min (U,W)).
2
Proof: We have
Omin (Vx, Ul+1) 2 Omin (Vx, U+i Wi)
Omin (VX, (I + +MMM) U.W.)
min (Vx, (I+ +MM,) Vo,w.) Jmin (V.WW U,W,)
IV Iv Jmin (Vx, Vu.w,) Mell Jmin (U,W))
og - 10
mmin (U,W)) 2 2
min (U,W))
where the last step follows from
Omin (Vx, )u,w.) 1 V Vo,w, 1 1-22
The conclusion follows.
Lemma D.6 Under the assumptions in Lemma C.6, we have
W., Wi41l < 3μ (10μ) X cca c3 X + [| 1((XX" -,,0,)) |||
Proof: The proof roughly follows (Stöger Soltanolkotabi, 2021, Lemma B.3), but we include here for completeness.
31

---

Under review as a conference paper at ICLR 2023
Since VX. U141 E++1 W4+1 and V4+1 E++1 E Rx is invertible, have
| W ++
W. Ux, Vx, (VX U2 U Vx.) -1
Since
-Vx,
- U,,, U.W.,
=Vx, (T+ -,,,)) W.W + +NVX, A.W.W,
--NVI -
+WVx, A.U.W.L.
(42a)
=-WVX, U.W.W, U.W.L + +VVx A.U.W.
(42b)
=- U,W.W, U, Vx.. VX,, U.W TH V. A,W.W.L.
(42c)
K
K.
where (42a) follows from VX, XX U,W = use VX, U,W.,1 O.
= O. and in (42b) and (42c) we
For K1, note that
Vx, U U Vx.) - VX Ui
(Vx, U Vx.) - VX. Un+11
UVX (V -
S +1+10pu X 3 min (Vx, U1+1)
so that
(VV, U 1+1 Vx.) K1
[ 10 X 3 (V U++1) || U.W, U.W
Plugging into (42), we deduce that
[..T] Wi+il
- 3/4 (1 10 01 min (Vx, U, U++1) V Vo.w, |
+ μo min (Vx, U(+1) U. W A [)xx - U,U,))
< 3y (IU, 10 X ()) [ Vu, Vu.w;||||X)
+ no mi (Vx, U(+1) U,W.
-UU,)
< 3p (10pl] | ca) cal X || + P A 1)(X- - -U,,
where in the last step use Lemma D.5 and the induction hypothesis which implies that Jmin (U, 2 (,.l.
Lemma D.7 The matrix Z defined in the proof of Lemma C.6 satisfies the following:
2 2) - Vu.w, BVU.w, 1 (I B)Vu, VJ.w, (B+ + +B Vu.w, D.
2
where
D < 30|2
Proof:
By definition of 2 we have
2(2 2)-
(I pM) P)Vo.W (VT.w, (I+ PT) (I 2 P)Vo.w.)
= -II B)V VV..w. (T+BT + +B + B B) Vu.w
= -I B)Vu.w.
I+ VU.W. (B + B + B B) Vu.W
32

---

Under review as a conference paper at ICLR 2023
It follows from (28) and assumptions ey and e₁ that
B S = U,U, 6μ (ca || || + 50| x
I 10pm X 2 + 6ucs (c, + 1) ||| <.1
(note that this step is independent and does not rely on earlier derivations in the proof of Lemma C.6), so by Taylor's formula, we have
(T -)- I+ 2 -
3
Hence,
2(2T2)- Vv..w, + +BV...
1 (I + B)Vu. W.Vu.w.V..w (B+B) Vu.w.)
2
(1 (1++B)D Vu,, (I- - -I
-
1
1 Vu.w. B BVo...
A
2
2
$ (1 (1+1) [B)
||||| + 1 [B||3]
11BAI)+
< BI2
as desired.
E PROOF OF RESULTS IN SECTION 5
Theorem 1.1 states that GD approximately learns the rank-s constrained minimizer of the matrix sensing loss. However, Theorem C.1 only implies that GD would get into an ( neighborhood of X,X, As a result, more fine-grained analysis is needed. Note that it is not even clear whether the rank-s minimizer of is unique. If it is not, then we may naturally ask which minimizer it converges to.
In this section, we study the landscape of padee--prameteriiee matrix sensing problem
(aUU) = |AAUUU - xx UE e Rdx
and establish local convergence of gradient descent. Our key result in this section is Lemma E.6, which states a local PL condition for the matrix sensing loss. Most existing results only study the landscape of (1) in the exact- and over wee-pparameterized case. Zhu et al. (2021) studies the landscape of parrtttrieeee matrix factorization problem, but they only prove striet saddle property without asymptotic convergence rate of GD.
When the measurement satisfies the RIP condition, similar to that of the hander-parameterizedl matrix factorization loss:
expect that the landscape of looks
F.(U) | X FF
1
Rdd
for some <. Recall that XXT = of The critical points of FU) is characterized by the following lemma:
Lemma E.1 U E Raxx is critical point of FU) and only if there exists an orthogonal matrix R E x2xx, such that all columns of U R are in {0,0; 15iss, r.).
Proof: : Assume WLOG that XX = diag (o) o3 ,0
.0) = E. Let U be a critical point of F., then we have that (UUT - X U = 0. Let W = _UT then ( W)W = 0.
Since W is symmetric, so is 2 and we obtain that EW is also symmetric. It's then easy to > X 0, then W is also in -dock-liagonal form: W diag (W1, W2, ... Wt) where W, E mm For each 1 < i < f, then have the equation (A₂ W,) W. 0. Hence, there exists an orthogonal matrix R; such that R. W, R. is diagonal matrix where the diagonal entries either 0 vX; o, Let
that that if Σ diag Imyym..... >eAm,) with X X2
33

---

Under review as a conference paper at ICLR 2023
R diag [R1, R2, R.), then R W'is is diagonal and its nonzero diagonal entries form s-subset of the multi-set : The conclusion follows.
In the case of s I, the global minimizers of F3 are 1 and strongly convex around these minimizers. Therefore, we can deduce that f is locally strongly- 1, we put these details in Appendix G. When
show that F, is locally
convex well. Since main focus is F,(U) is not locally strongly-convex due to rotational invariance: if U a global minima, then so UR for any orthogonal matrix R R*x= Instead, we will establish local PL property w.r.t the procrustes distance:
1,
Definition E.1 Let U2 Raxs, we define
dist(U1,U2)) inf {1| U2R R E I2** is orthogonal)
The following characterization of the optimal R in Definition 5.1 is known in the literature (see e.g. (Tu et al., 2016, Section 5.2.1)) but we provide proof of it for completeness.
Lemma E.2 Let R be the orthogonal matrix which minimizes positive semi-definite
|U - -U2R then U, TTURR is
Proof: Observe that
U U = - ) U2R))
=| |U21| 2tr (R U, U1).
Let
U1 U AEB be its SVD. then
U U.) ( R AΣ) < B R A (2) = tr(),,
where the final step is due orthogonality B R A gaxs, and equality holds if and only B B I i.. R = AB Thus U, U2R = BEB is positive semi-definite.
The following lemma states that the minimizer of matrix sensing loss is also near-optimal for the matrix factorization loss. The main idea for proving this result to utilize
Lemma E.3 Let Z be best rank-8 solution as defined in (1), then we have
Z ---XXP xx X 1 < XX.XX X
108 x x
Proof: Since U the global minimizer f. by the RIP property we have
|Xx
2:1 (1 - 5) 8) (Xxx - 2;) 11
< (1-8)) 8) | (XX-- -x,x,
1 8
XX -X,X.11 1|
< 1
< XXT x, 11 10
as desired.
The next lemma show that F. satisfies local PL property:
Lemma E.4 Given U Rdxe and let be an orthogonal matrix such that I R.R.
dist(U, X.). Suppose that dist(U, X.) S 0.1] (where we recall that
min.e[r-) (o? o2+1) is the eigengap of XXT) then we have
(VF,(U),U X,R 2 (U,
Proof: Assume WLOG that R = then U X, is positive semi-definite. Let H = U X,, then
FF, (UUT -XX U
= [H X.) + xX)) XX ( X.),
34

---

Under review as a conference paper at ICLR 2023
so that
(VF.(U), X,)
([ X,) (( x.) Xx ( H)
=t [( + X.) + (X) -x H + H (HH² + HXX, + X.H x.)
2 - tr (H x,, X 1.1 H) - 3
X X
H + ir (H H x.)
(43a)
2 (0] 11) |
3| H 0.1 l|:
(43b)
where in (43a) use tr (H xx) 2 0 (since H Xg is symmetric as noticed in the beginning of the proof), and (43b) is because of
tr H H X.) tr (H HWx, (x,)
tr (WX, H HWx. xx,
2 o tr (WX, H' HWx.) = H.
and
tr
H H
= tr H Vx E. VX,, H)
S 1| H Vx,, || S o s+1 H
Corollary E.1 Under the conditions of Lemma E.4, we have |VF, 2 0.1rdist(U, X,)..
The following lemma shows that the rank-s global minima of matrix sensing must lie in an (6)-
neighbourhood of the minima of F..
Lemma E.S Suppose that Assumption 3.1 holds. Let U be global minimizer of fao then we have
d x,) S 408k|| X Ir-
where we recall that = -1 X|| is the condition number of XX T.
Proof: Define
S = U E Rdx= dist(U, S 0.1 0.1 |X
First we can show that U E S. The main idea is to apply Lemma A.5. Indeed, it's easy to see that
lim ++o
FU(U) +00.
Let U E aS i.e. dU, X.) 0.1 XI| Assume WLOG that dU, X.) = I1 X.1la then by Lemma E,4 we have
F.(U) F.(X.)
t (VF, + (1- X.) dt
0.1 | x, dt
> 10 X -233
Recall that all the stationary points of F, are characterized in Lemma E. so that for all U & S with (U.(U) have
FU(U) - F > 0.5 (o - 2 0.57
On the other hand, we know from Lemma E.3 that
F.(U)) - F" < 5 < 0.57
(44)
so Lemma A.5 implies that U E S.
35

---

Under review as a conference paper at ICLR 2023
Inside S, we can apply the local PL property that previously derived. Indeed, note that
|VF,(
[xx_ - -U; (U()) v:ll A1'A 1) (XXT -U; (U:)) U: 6 Xxx
T - (U;) 7 |U:
S 48 X|| || ||p
Hence we have that
dist(U, - 4 | 3 X F = 408x |||r.
Corollary E.2 Suppose that Assumption 3.1 holds, then we have minn ((U:) 2 o2
806k; [|]]
Proof: We assume WLOG that ||U X.llr dist(U x,) i.e. R I in Definition 5.1. By Lemma E.5, we have that
[U;) U. - xX_ X.
> (U)) U - X,
S max U || |X,I| I X,Il
808k|| X |
Lemma E.6 Suppose that Assumption 3.1 holds. Given U Rddxs, let U Raxx be a minimizer of Sa, and U. R be the rank-s minimizer which is closest to U (R E Rex is orthogonal). When
I U R S 10 2
|X|] I1, we have
UV) - R 2 0.1rdist(U,U)) (U,U)²
Proof: We assume WLOG that I, then U positive semi- Let H U U,
then
SU,(U) (UU - -X
-(A'A) [(H + +U;)T -x (H+
= =((A-A) (HH + +
(H( U,) - -AAA(AXX--XXUUU H
where we use the first-order optimality condition
A -
- U; (U;)" =0
Since |0:|1 < X| by Lemma E.5, we may thus deduce that
V.. - [ H + H (U:))) (H+ + +U) (XXT-U;(U,) H
(A'AA 1) (H HUH + HU:)) (H + -U) + +A 1)
-U; (U:) -U; H
x | ||
Hence
(VS.(U),U - -U)
HHH HUHH + +U:)) (H+ (xxT - (U;) H. H -00||
H(H + U,) (H (H+ H TH H ((U:) H)
2 tr
X UU. H) 506 X H }
> Omin (U:)) U:) - -
U, (U;) ||
3 H - -| |
36

---

Under review as a conference paper at ICLR 2023
By Corollary
E.2 we
have
min (U:) U:}
2
o² -806x X
|||
and
XX - U,(U,) (U;) T
Σ x++ + 800k|
J so that
(VS,(U), - 2 (0² o 1600x
X X
||
506 |
31
H
H
H P.
When 5 5 100 and H 10 10-
X -1 the above implies that (VI,(U),
U
0.5T|| H H p. as desired.
F PROOF OF THEOREM 4.1
With the landscape results in hand, we are now ready to characterize the saddle-to-saddle dynam- ies of GD. We first note the following proposition, with is straightforward from Lemma C.9 and Theorem C.1. In the following we use Ua,t denote the f-th iteration of GD when initialized Uo aU.
Proposition F.1 There exists matrices Ua, -T I t S
with rank S s such that
max T3 S150
Ura U Va,fgtt
o
(a (a=+0)
where ggg defined in Theorem C.I (we omit the dependence on a there) and moreover
||0g0g Zz| S 100x. || x||
where Z, U; (U;) is the rank-s minimizer of the matrix sensing loss i.e.
Z. arg min { A (x((-xXT) Z pddd is positive semi-definite and rank (Z) S
(45)
Remark F.1 We omit the dependence a for simplicity of notations, when it is clear from context.
Proof: follows from Lemma C.9 that max IsiST; 1,1 = ( We choose
U. = U Uzzt W Wiztt WT T
then rank (U.) S s and moreover by Theorem C.I we have
Ts+e'
|| - UpU, I 2x | V On the other hand, similar to Corollary E.2 we have
that Dz X,X
806x X p. Thus |00000 Z. s 100k> |XX] ||
desired.
Let Ü.,t Un. Wa.: E Rdxx, then it satisfies Ú,úğ = U,Ü,- The following corollary shows
that ÜΛ.0 close to U in terms of the procrutes distance.
Corollary F.1 We have dist U3) < 80 ||
Proof: : We know from Lemma E.5 that dist(U;; X.) & 400k|| r|,, so it remains to bound dist dist(Uo. X.).
The proof idea is the same as that of Lemma E.5, so we only provide proof sketch here. has been shown in the proof of Proposition F.1 that
F. (Ú,) = } X 0,0,7 || Sr. X 0 <4<t,, < 0.57
Note that F, is the matrix factorization loss with X.X, as the ground-truth, so the local PL property (ef. Lemma E.4) still holds here, and by the same reason as (44), we deduce that dist(U,, X.) < xx1||X||-4 i.e. Úg is in the local PL region around X,. Finally, it follows from the PL property that
dist Üp X.) < 10r
< 10- -1001
x.X_ - 0,0, || < 40 X
The conclusion follows.
Recall that matrix sensing loss satisfies local PL property (ef. Lemma E.6). As result, when 8 is small, we show that GD initialized U, converges linearly the ground-truth.
37

---

Under review as a conference paper at ICLR 2023
Lemma F.1 Let Ü, be the t-th iteration of GD initialized at Up. Suppose that 8 S 10 2,, x-
and μ S 10-3 || then have that
dist (ist((0, U;) (1- dist (U, U.).
Proof: We know from Corollary F.1 that
U ||||| 40. X
We will prove the following result, which immediately implies Lemma F.1: suppose that dist(U,, U2) z dist(Uo, Ug), then
dist (U++1, S (1 (10.000070)distt (Ü,, Ug).
(46)
Let R be the orthogonal matrix satisfying ||U - U R dist(U, UZ). Assume WLOG that
R I. We first bound the gradient (U,) as follows:
A xx - -Z,ū, Ú,
< A [xx-- - -ZÜ, )l U. -U;
U² + +|(0,,7 - (U:) U3
s x1 1 |0: U²²]
(47)
where we use ūنن s || || + 40x , x 18 < 2| X|| and the RIP property. It follows that
dist (UH1, -
Ú141 U.
(48a)
Ü -VV((.) U ?
F - U, | μ (V) - +
(1 0.1 400 X |0 Ug R.
(48b)
where (48a) follows from the definition of dist, and (48b) is due to Lemma E.6 and (47). Finally, (46) follows from the condition S 10 32
We are now ready to complete the proof of Theorem 4.1.
Theorem F.1 (Restatement of Theorem 4.1) Under Assumptions 3.1 and 3.2, consider GD (3) with learning rate μ. S 10-1|2-1| and initialization Ua.0 = aU for solving the matrix sensing problem (1). There exists a universal constant >> O, a constant C (depending on and x) and sequence of time points T < T2 < ... < <TArr, such that for all 1 S S P.A.A Arr the following
1
holds when a =0 =0 ((pr.)
Ua.I:Unn Z: S Ca
(49)
where we recall that Z the best rank-s solution defined in Definition 1.1. Moreover, GD follows an incremental learning procedure: for all 1 < 8 < f. A Tx, have lima-so max (U+1(Ua.)) = O. where (A(A) denotes the (s 1)-th largest singular value of matrix A.
Proof: : Recall that | - 0o o(1) (a - 0) where ia is defined in Proposition F.I; we omit the dependence on a to simplify notations. We also note that by the update of GD, we have
Ü,ū,T- = -,Ú, for all t 2 0.
By Lemma F.I. we have that dist dist? (Ú, < (1 - 0.0574)* dist? dist? U?) and, in particular, U. < || X for all I. Thus | < X|| as well. Moreover, recall that || U.]] < 3| X|| for all
38

---

Under review as a conference paper at ICLR 2023
t. It's easy to see that that the matrix sensing loss f is L-smooth in {U E Rax,; | - x|
for some constant I. O(1 (X) 112) so it follows from Lemma A.6 that
U Ura+ U, s (1 (1+ + Up2 -Uo Uo
On the other hand, since dist 2 (Ü,, U3) $ (1 - 0.05T 1²) dist (Uo. Uł), we can deduce that
UU++: UTste
U rg++
Z. 1
U Ur U 1z U,0, + ",ū, -U; -U; T|
|gg+t U Tatt 0,0, | 11, + |ū:0, UU; (U;)
||| (1 - -U, +dist(U,, U?)
s x|| (1+ |U:y - -Voll + - -.055T)) dist (Uo, U?))
Since when a + 0. +0.1Upg 0o ||| = 0(a +( ), it's easy to see that there exists a time
to so that
we have max -P U/ U. F = 0 (ari) and |ig+t U 1zte - Zo
a c as
=
F
well, where 0j is a universal constant. Let T = Ta + th then Ur: Z
= o(1) holds. F
Recall that rank (Un) I s, so that maxosisT; J++1 (U,) =1)). Finally, for all 0 S s < f A Txy
we need to show that T% < T Indeed, by Corollary E.2 and the Assumption 3.1 we have
2 (Ur:) 2 Js+1 (Z++1) d(1) 2 0.50?+1. so that T > Ty as desired.
G THE LANDSCAPE OF MATRIX SENSING WITH RANK-1 PARAMETERIZATION
In this section, we establish a local strong- crongg-onvexxty result Lemma G.2 for rank-1 parameterized matrix sensing. This result is stronger than the PL-condition we established for general ranks, though the latter is sufficient for our analysis.
Lemma G.1 Define the full-observation loss with rank-1 1 parameterization
1 (1(u)= = uuu" - -
Then the global minima of gi are u² 0101 and -w". Moreover, suppose that g(u) - g((u) ) S
0.5Ti where Ti- = =o o is the eigengap, then we must have
||u u 1 < 20 (o)( -i("))).
Proof:
We can assume WLOG that Xx = diag ,",,"""",,,, ,0", 0,.,0....))) ... ,0). Then
1
gi (u)
||ul| -2 2 Σ of + X x 2
(50a)
4
i=1
1
2 (llull - -oof 20711u112 + |
(50b)
4
2 4
1
(1xx*x 1| - xt)
(50c)
where equality holds if and only if u2
us 0 and ||||2 of i.. 1o,e1
Moreover, suppose that 91 (1) 11-911(6 (u*) S 0.5r, it follows from (50b) that 72 Σ م u² S 2( (u)
gi () which implies that Ei= u < 2T (gl (w) - 91 (u )). Also (50c) yields |||u|| of S
4 91 (u)) 91(""). Assume WLOG that in > 0, then have
2 (u² oi)² 2 + Iu 1 S -
Σ
2
1=2
s 20 (u) 91 (u"))
39

---

Under review as a conference paper at ICLR 2023
Lemma G.2 Let
fi( = ||A (wu" xx u EER
Suppose that 8 < 10 then there exists constants an and such that fi is locally strongly convex in B1 = B( C R.. Furthermore, there a unique global minima of fi inside Bi.
Proof: Recall that we defined the full observation loss g1(u) = i1luu X Let h1 fi 91, then
1
hi (w)l
2 [1AAAA A- I) (un" xx*) - uuu'
(2|ue11 + |
When |/ue - 0|vill 112 < 0.1 min ( (recall = oz2)
1
miin (V (u))
min (||u||31 3 2ur2" - xxx) 2 0.4m
2
Hence we have
Mmin ((()) 2 (V g) (w)) - (n)) 2 0.4m 1|| 2 0.2m,
ie. strong-coneent holds for af 0.1 min ( } and = 0.27
Let rx" be global minima of f1, then we must have ||,=]] || S 2 X (otherwise fi > fi())). We can thus deduce that
91(2") S fi("") Kun" XXT (A"A Iyuua xx*))
- (u) + 1081 X 1 & (w) 205 X12
It follows from Lemma G.1 and our assumption on N that min ||u" اrlill 11 ,Iuu" + +oreil? |1] < aj. Moreover, by strong convexity, there exists only global minima in Bi which concludes the proof.
40


Reviews:
[{"review_id": "fHBFBdXJO3", "reviewer": "Reviewer_7KXn", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "", "summary_of_the_paper": "This paper analyzes the dynamics of gradient descent on overparameterized and underparameterized matrix sensing. The authors show that gradient descent learns solutions with increasing rank -- i.e., it finds the minimizer of the rank-1 matrices that best approximate the given measurements, then increases its rank and learns the best rank-2 approximation, and so on until the true rank is achieved.\n\nFor the case of underparameterized matrix sensing, the authors show that the L2-loss function satisfies a local PL inequality, which guarantees a unique global minimum when fitting a rank-s matrix to satisfy the given measurements. However, there is no guarantee that gradient descent will not get at some other stationary point.", "summary_of_the_review": "The stated problem is interesting, but the results are written in an extremely confusing manner. Overparameterized and underparameterized matrix sensing are arbitrarily exchanged between Theorem 4.1, 4.2, and corollary 4.1. The incremental learning aspect is not rigorously shown, theorems 4.1 and 4.2 are for a fixed rank $s$, and not for all $s=1,\\cdots, r$.", "strength_and_weaknesses": "Weakesses:\n- I'm very confused about the results, and I don't see how the authors claim the incremental learning aspect. Li et al 2018 showed that once you start from $U_\\alpha$ for a small enough $\\alpha$, you will reach the rank-$r^*$ solution quickly (where $r^*$ is the true rank). Theorem 4.1 shows that for each $s \\leq r^*$ , there exists a time $T_{\\alpha, s}$, such that gradient descent will come close to the rank-$s$ matrix that minimizes the L2-loss on the measurements (it is also not true that the loss will continue to decrease after this hitting time). But there is no guarantee that this hitting time $T_{\\alpha, s}$ is an increasing function in $s$ -- it is not necessary that it learns the rank-1 minimizer, then the rank-2 minimizer, and so on until the rank $r^*$ minimizer. Another difficulty is that each of the ranks require an initialization from a sufficiently small $\\alpha$, and hence I do not see why finding a rank-1 solution should help with finding the rank-2 solution.\n\n- This is related to the above point, but the proof of Lemma 4.1 makes no sense. If $\\tilde{U}_0$ is supposed to have all eigenvalues $=\\alpha$, then how does the proof sketch of Lemma 4.1 satisfy this? Also, there is no proof of Lemma 4.1 in the appendix.\n\n- What is the value of $r$ in theorem 4.1 and 4.2 ? I thought it satisfies $ r \\geq r^*$, but then in corollary 4.1 the authors say $r \\leq r^*$ and use results from section 5.\n\n- I don't understand how you can claim incremental learning for the underparameterized setting. The theorem in section 5 says nothing about local minima or saddle points, and Theorems 4.1 and 4.2 are defined for overparameterized setting.\n\n\nMiscellaneous:\n- In Theorem 1.1, the step size $\\mu$ needs to be redefined, else it's meaning is lost as the gradient step is not in a block environment.\n\n- In Assumption 3.2, Proposition, what is $V_{X_s}$ ? This has not been defined \n\n- In Lemma 4.1, what is $W_{\\alpha, T_\\alpha}$?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "VZoDvNO5jt", "reviewer": "Reviewer_rmE5", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "This paper studies gradient descent (GD) for low-rank, PSD matrix sensing problem. The authors show that, with RIP sensing matrices and small initialization, GD exhibits an incremental learning behaviour, i.e. its trajectory goes through a series of low-rank solutions with increasing rank. In the under-parameterized regime, GD eventually converges to a global minimizer under rank constraint; in the over-parameterized regime, GD (with possibly early stopping) finds the true solution as loss goes to 0. Some numerical experiments are then provided to illustrate this learning behaviour.", "summary_of_the_review": "Although the results in the paper are interesting, the quality of the paper suffers from the many errors in the paper. The paper also only considers the noiseless case without a discussion of the noisy case (or experiments that show similar behaviour of GD can be expected in the noisy case). ", "strength_and_weaknesses": "Strength\n- The paper provides an analysis on behaviour of gradient flow for a non-convex problem of matrix sensing. The analysis also holds for low rank matrix with rank > 1, unlike previous results which was limited to rank = 1. \n\n\n\nWeakness\n\n- The analysis limited to the noiseless case without a discussion of the challenges of the extending it to the noiseless case. In the noisy case, is the expected behaviour that $||U_{\\alpha, T_\\alpha} U_{\\alpha, T_\\alpha}^\\top - Z_s|| \\approx 0$ for small $\\alpha$? The experiments are limited to noiseless setting as well. Is the recovery behaviour of GD recovering higher rank matrix with iterations present in the noisy case as well?\n\n- Unclear notation\n     -  In Assumption 3.2, where is $V^\\top_{X_S}$ defined?\n     - In equation 3, $\\mu$ is missing. Also, $M_t$ is used without referring to where it is defined. \n\n- Typos\n     - In corollary 4.1, is $s=r$ ?\n     - In abstract, in complete pharse: \"we that....\"\n     - In page 2, rank$(Z) = r_* \\ll d $ should be rank$(Z^*) = r_* \\ll d $ \n     - In proposition 3.1, what is an asymmetric matrix? Is it supposed to be symmetric instead?\n     - In equation 4, I believe $U_t$ should be $U_T$ instead.\n     - In Theorem 1, please specify the minimization variable.\n    - Theorem 5.1 is for the case when $\\delta = 0$. Is the condition $\\delta \\leq 0.01...$ in (2) needed?\n\n- Unclear experiment\n     - Is figure 1 for the overparametrized case? What is r? Also, what is the behaviour of the relative loss for larger iteration for figure 1(a). Does the relative error for $r^* = 5$ go to zero?\n     - In figure 2, was GD run for 1000 iterations or 500 iterations? Figure shows 500 but in section 6.2, T = 1000.\n\nGeneral comment\n- In Thm 1.1, does $T_\\alpha$ depend on s? If so, is it true that $T_{\\alpha, s+1} \\geq T_{\\alpha, s}$?\n- In page 1, the authors state attribute incremental learning as the reason for why overparametrized neural networks do not overfit? Are there other reasons such as early stopping (which the results in the papers seems to suggest to be true in the under parametrized case)? If so, please adjust the phrasing accordingly.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "-KnMB8PvcV", "reviewer": "Reviewer_vVy7", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "", "summary_of_the_paper": "This paper studies the convergence of gradient descent on the matrix sensing problem in both the overparametrized and underparametrized regimes, with the latter one being completely new compared to existing studies. The (matrix) RIP property is assumed so that the problem is well-conditioned from the statistical perspective, leaving the problem of optimization to study. The results show that if the initialization is small enough, the learning process grows towards a rank 1 approximation of the solution, and then towards a rank 2 approximation, and so on until it approaches the rank s approximation, where s is the minimum of the ground truth rank and the explicit rank restriction in the optimization problem.  \n\nSynthetic data experiments confirm that the training procedure exhibits this behavior in practice. \n\n", "summary_of_the_review": "This seems like a very solid paper with highly impactful results of general interest to the community. I hope I get to read the appendix more deeply in the future. ", "strength_and_weaknesses": "Strengths: \n\n\nThis is a very interesting topic and a very powerful result. Even if only the extension to the underparametrized case is novel, this is a very significant contribution. \n\nThe main paper and some \"textual\" parts of the appendix are written in a very reader friendly way. A substantial amount of effort is made to try to explain the ideas to the reader.  I love how the authors explain that the dynamics of GD approximate iterative power methods in the early stages, for instance. \n\nThe text of the main paper is very well polished.\n\nI think the experiments and conclusions are very believable as well. I actually remember observing similar phenomena in experiments I was running (though I wasn't actually working on the theoretical properties of the optimization strategy). \n\n\nWeaknesses: \n\n\n\n(not serious) The actual mathematical computations are sometimes a bit difficult to follow without extra details. \n\n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject