Towards Resolving the Implicit Bias of Gradient Descent for Matrix Factorization: Greedy Low-Rank Learning
Authors: Zhiyuan Li
Yuping Luo
Kaifeng Lyu
Venue: ICLR 2021 Poster (2021)
Keywords: matrix factorization
gradient descent
implicit regularization
implicit bias

Abstract: Matrix factorization is a simple and natural test-bed to investigate the implicit regularization of gradient descent. Gunasekar et al. (2017) conjectured that gradient flow with infinitesimal initialization converges to the solution that minimizes the nuclear norm, but a series of recent papers argued that the language of norm minimization is not sufficient to give a full characterization for the implicit regularization. In this work, we provide theoretical and empirical evidence that for depth-2 matrix factorization, gradient flow with infinitesimal initialization is mathematically equivalent to a simple heuristic rank minimization algorithm, Greedy Low-Rank Learning, under some reasonable assumptions. This generalizes the rank minimization view from previous works to a much broader setting and enables us to construct counter-examples to refute the conjecture from Gunasekar et al. (2017). We also extend the results to the case where depth >= 3, and we show that the benefit of being deeper is that the above convergence has a much weaker dependence over initialization magnitude so that this rank minimization is more likely to take effect for initialization with practical scale.

Published as a conference paper at ICLR 2021
TOWARDS RESOLVING THE IMPLICIT BIAS OF GRADIENT DESCENT FOR MATRIX FACTORIZATION: GREEDY LOW-RANK LEARNING
Zhiyuan Li; Yuping Luo"
Kaifeng Lyu'
Princeton University
Tsinghua University
r yupingl) 8os. www.ppeceetooo..comommm.m edu
stleaking@gmaile com
ABSTRACT
Matrix factorization is simple and natural test-bed to investigate the implicit regularization of gradient descent. Gunasekar et al. (2017) conjectured that Gradi- ent Flow with infinitesimal initialization converges to the solution that minimizes the nuclear norm, but a series of recent papers argued that the language of norm minimization is not sufficient to give full characterization for the implicit reg- ularization. In this work, we provide theoretical and empirical evidence that for depth-2 matrix factorization, gradient flow with infinitesimal initialization is math- ematically equivalent to a simple heuristic rank minimization algorithm, Greedy Low-Rank Learning, under some reasonable assumptions. This generalizes the rank minimization view from previous works to much broader setting and enables us to construct conter-examples to refute the conjecture from Gunasekar et al. (2017). We also extend the results to the case where depth 2 3, and we show that the benefit of being deeper is that the above convergence has a much weaker dependence over initialization magnitude so that this rank minimization is more likely to take effect for initialization with practical scale.
INTRODUCTION
There are usually far more learnable parameters in deep neural nets than the number of training data, but still deep learning works well on real-world tasks. Even with explicit regularization, the model complexity of state-of-the-art neural nets is so large that they can fit randomly labeled data easily (Zhang et al., 2017). Towards explaining the mystery of generalization, what kind of implicit regularization does Gradient Descent (GD) impose during training. Ideally, we hoping for nice mathematical characterization of how GD constrains the of functions that can be expressed by a trained neural net.
must understand
As a direct analysis for deep neural nets could be quite hard, line of works turned to study the implicit regularization on simpler problems to get inspirations, for example, low-rank matrix factorization, fundamental problem in machine learning and information process. Given a set of observations about an unknown matrix W E ddxd of rank r" < d, one needs to find a low-rank solution W that is compatible with the given observations. Examples include matrix sensing, matrix completion, phase retrieval, robust principal component analysis, just to name few (see Chi et al. 2019 for survey). When W* is symmetric and positive semidefinite, one way to solve all these problems is to parameterize W W UUT for U E d and optimize L(U) := fUU where f(.) is some empirical risk function depending on the observations, and r is the rank constraint. In theory, if the rank constraint is too loose, the solutions do not have to be low-rank and we may fail to recover W However, even in the case where the rank is unconstrained (i.e., r = d), GD with small initialization can still get good performance in practice. This empirical observation reveals that the implicit regularization of GD exists even in this simple matrix factorization problem, but its mechanism is still on debate. Gunasekar al. (2017) proved that Gradient Flow (GD with infinitesimal step size, a.k.a., GF) with infinitesimal initialization finds the minimum nuclear norm solution in a special case of matrix sensing, and further conjectured this holds general.
Conjecture 1.1 (Gunasekar et al. 2017, informal). With sufficiently small initialization, GF converges to the minimum nuclear norm solution of matrix sensing.
Alphahet ordering.

---

Published as a conference paper at ICLR 2021
Subsequently, Arora et al. (2019a) challenged this view by arguing that simple mathematical norm may not be a sufficient language for characterizing implicit regularization. One example illustrated in Arora et al. (2019a) is regarding matrix sensing with a single observation. They showed that GD with small initialization enhances the growth of large singular values of the solution and attenuates that of smaller ones. This enhancemenn/attenuttion effect encourages low-rank, and it is further intensified with depth in deep matrix factorization (i.e., GD optimizes f(U1.. Ut) for L 2 2). However, these are not captured by the nuclear norm alone. Gidel al. (2019); Gissin et al. (2020) further exploited this idea and showed in the special case of full-observation matrix sensing that GF learns solutions with gradually increasing rank. Razin and Cohen (2020) showed in a simple class of matrix completion problems that GF decreases the rank along the trajectory while any norm grows towards infinity. More aggressively, they conjectured that the implicit regularization can explained by rank minimization rather than norm minimization.
Our Contributions. In this paper, we move one further step towards resolving the implicit regularization in the matrix factorization problem. Our theoretical results show that GD performs rank minimization via a greedy process in a broader setting. Specifically, we provide theoretical evidence that GF with infinitesimal initialization is in general mathematically equivalent to another algorithm called Greedy Low-Rat Now-Rank Learning (GLRL). At a high level. GLRL is a greedy algorithm that performs rank-constrained optimization and relaxes the rank constraint by 1 whenever it fails to reach a global minimizer of f()) with the current rank constraint. As a by-product, we refute Conjecture 1.1 by demonstrating an counterexample (Example 5.9).
We also extend our results to deep matrix factorization Section 6, where we prove that the trajectory of GF with infinitesimal identity initialization converges to deep version of GLRL, at least in the early stage of the optimization. We also use this result to confirm the intuition achieved on toy models (Gissin et al., 2020), that benefits of depth in matrix factorization to encourage rank minimization even for initialization with relatively larger scale, and thus it is more likely to happen in practice. This shows that describing the implicit regularization using GLRL is more expressive than using the language of norm minimization. We validate all our results with experiments in Appendix E.
RELATED WORKS
Norm Minimization. The view of norm minimization, or the closely related view of margin maximization, has been explored in different settings. Besides the nuclear norm minimization for matrix factorization (Gunasekar et al., 2017) discussed in the introduction, previous works have also studied the norm minimizationnmarrinn maximization for linear regression (Wilson al., 2017; Soudry et al., 201 8a:;; Nacson et al., 201 20;9b;e; Ji and Telgarsky, 2019b), deep linear neural nets (Ji and Telgarsky, 2019a; Gunasekar et al., 2018), homogeneous neural nets (Nacson et al., 2019a; Lyu and Li, 2020), ultra-wide neural nets (Jacot et al., 2018; Arora et al., 2019b; Chizat and Bach, 2020).
Small Initialization and Rank Minimization. The initialization scale can greatly influence the implicit regularization. A sufficiently large initialization can make the training dynamics fall into the lazy training regime defined by Chizat et al. (2019) and diminish test accuracy. Using small initialization is particularly important to bias gradient descent to low-rank solutions for matrix factorization, as empirically observed by Gunasekar et al. (2017). Arora et al. (2019a); Gidel et al. (2019); Gissin et al. (2020); Razin and Cohen (2020) studied how gradient flow with small initialization encourages low-rank in simple settings, as discussed in the introduction. Li et al. (2018) proved recovery guarantees for gradient flow solving matrix sensing under Restricted Isometry Property (RIP), but the proof cannot be generalized casily to the case without RIP. Belabbas (2020) made attempts to prove that gradient flow is approximately rank-1 in the very early phase of training, but it does not exclude the possibility that the approximation error explodes later and gradient flow is not converging to low-rank solutions. Compared to these works, the current paper studies how GF encourages low-rank in a much broader setting.
3 BACKGROUND
Notations. For two matrices A, B, we define () = TrAB as their inner product. We use | |A||, and ||A]]] to denote the Frobenius norm, nuclear norm and the largest singular value of A respectively. For matrix A E Idddd, we use X₁ (A)...., AA) to denote the eigenvalues of A in decreasing order (if they are all reals). We define S. as the set of symmetric x d matrices and St Sa as the set of positive semidefinite (PSD) matrices. We write A > B or B 3 A iff A B
is PSD. We use St Si.r to denote the set of d x d PSD matrices with rank r, S respectively.
2

---

Published as a conference paper at ICLR 2021
Matrix Factorization. Matrix factorization problem asks one to optimize L(U, V) : 2((VV) among U, V RR where f Rdxd I is convex function and in this paper assume f is -s-smooth. A notable example is matrix sensing. There is an unknown rank-r" matrix W E Rdxd with r* < d. Given m measurements II...., Xm Rdddd one can observe y/ := (X,, W through each measurement. The goal of matrix sensing is to reconstruct W via minimizing
[[ Σ ((W, X;) yı) Matrix completion is a notable special case of matrix sensing in which every measurement has the form X; Cp. c where (ei,'.. ed) stands for the standard basis (i.e., exactly one entry is observed through each measurement).
Note that matrix factorization in the general case can be reduced to this symmetric case: let U [V] E Rd2xr, f" (12 B) )) = { + ((()), then [(UVT) = ('U'"" So in this paper we focus on the symmetric case in previous works (Gunasekar et al., 2017), i.e., finding low-rank solution for the convex optimization problem: minw>o f(W). For this, we parameterize W as
W = UUT for U E ddxr and optimize ((U) == f(U ). We assume WLOG throughout this paper that f(W)= = f(WT); otherwise, we can set f'()) = 1/ (f(W) + f(WT) )) so that ((() f'(W while L(U) { is unaffected. This assumption makes ((W) symmetric for every symmetric W.
Gradient Flow. In this paper, analyze Gradient Flow (GF) for symmetric matrix factorization, defined as the solution of the following ODE for (t) E gdxr;
dU = - VL(U) = VV
dt
Let ((t) = (t)
T E Radd Then the following end-to-end dynamics holds for W(t):
dW
(VF(W)-f((W)) =: =W:
We use < oWo t) to denote the matrix ((t) in (2) when W(0) Wo 2 0. Throughout this paper, we assume of Wo.6 1) exists for all E IR, Wo 2 O. is easy to prove that U is a stationary point of C(-) (i.e., VL(U)= = 0) iff W UU is critical point of (2) (i.e., g (W) = 0); see Lemma C. for proof. If W is a minimizer of f(-) in st then W is critical point of (2), but the reverse may not be true, e.g.. (0) 0, but 0 is not necessarily a minimizer.
In this paper, we particularly focus on the overparameterized case, where r= d, to understand the implicit regularization of GF when there no rank constraint for the matrix W.
4 WARMUP EXAMPLES
First, we illustrate how GD performs greedy learning using two warmup examples.
Linearization Around the Origin. In general, for a loss function L(U) = 2 (UUT). we can always apply Taylor expansion f(W f(0) (W, ff(O)) around the origin to approximate with a linear function. This motivates us to study the linear case: f(W) := fo (W, Q) for dU
some symmetric matrix Q. In this case, the matrix U follows the ODE, de = QU, which can be understood as continuous version of the classical power iteration method for solving the top
eigenvector. Let Q := Ei= " be the eigendecomposition of Q, where μn 2 μ2 2 Pd and vi...., Ua are orthogonal to each other. Then we can write the solution as:
d U(t) U0) (Ein cHill U,va
U(0).
(3)
1=1
When μn > U2, the ratio between el1 and e for + 1 increases exponentially fast. Ast + toc, U() and (() become approximately rank- as long a. U()) / 0.
lim m U()) = da (0), 1-00
lim t-000 e -222' (() = (v. (0)er)oo.
(4)
The analysis for the simple linear case reveals that GD encourages low-rank through a process similar to power iteration. However, f(W) is non-lineat in general, and the linear approximation is close to ((W) only if W is very small. With sufficiently small initialization, we can imagine that GD still resembles the above power iteration the early phase of the optimization. But what W(I) grows to be so large that the linear approximation is far from the actual f f(W)?
Full-observation Matrix Sensing. To understand the dynamics of GD when the linearization fails, we now consider well-studied special case (Gissin et al., 2020): L(U) = ( "), JWW) =
[
W [|3 for some unknown PSD matrix W GF in this case can be written as:
3

---

Published as a conference paper at ICLR 2021
dU -W'
dW
di ( w)w + WWW" W).
(5)
di Let W -ii= "o be the eigendecomposition of W Our previous analysis shows that the de W in the early phase and thus encourages low-rank.
dynamics is approximately du
To get a sense for the later phases, we simplify the setting by specifying U()) = vāI for a small number a. We can write (0) and W as diagonal matrices W = diag(a, a.... .a), W = diag((1; (2,.... ... ". ,Haa) with respect to the basis vi..... ddd It is easy to see that (t)) is always a diagonal matrix, since the time derivatives of non-diagonal coordinates stay 0 during training. Let (t) = diag(ar (t), (2()).... (2(())
aa(()), then (t) satisfies the dynamical equation 4 (1) = one (t)(() - (t)), and thus (t))) a+ ((j--aa) Zmzt- This shows that every (t) increases from a 14 over time. As a - O, every (t) has a sharp transition from near O to near μá at time roughly (2u. +1)) log a' which can be seen from the following limit:
0
C (- 1 0),
lim oi ((t) + +c) log(1/a)) a-+
lim a-0 a + (Mi - 22
2pr 14 ( 000).
1 for = 1....,d d - 1 (or q E 22, -00) for i d). This means for every E (2n4. 2/111
l W (ogg(//)) = diag(11, U2. M4, 0, 0, 0). Therefore, when the initialization is sufficiently small, GF learns each component of W one by one, according to the relative order of eigenvalues. At a high level, this shows greedy nature of GD: GD starts learning with simple models; whenever underfits, it increases the model complexity (which is rank in our case). This is also called sequential learning or incremental learning (Gidel et al., 2019; Gissin et al., 2020).
However, it is unclear how and why this sequential learning/mnrremenaal learning can occur in general. Through the first warmup example, we may understand why GD learns a rank-1 matrix in the early phase, but does GD always learn solutions with rank 2, 3, 4.... sequentially? If true, what is the mechanism behind this? The current paper answers the questions by providing both theoretical and empirical evidence that the greedy learning behavior does occur in general with a similar reason as for the first warmup example.
GREEDY LOW-RANK LEARNING (GLRL)
In this section, we present a trajectory-based analysis for the implicit bias of GF on matrix factoriza- tion. Our main result is that GF with infinitesimal initialization is generically the same that of simple greedy algorithm, Greedy Low-Rank Learning (GLRL, Algorithm 1). See Appendix A for a comparison with existing greedy algorithms for rank-constrained optimization.
The GLRL algorithm consists of several phases, numbered from 1. In phase r, GLRL increases the rank constraint to r and optimizes (U,)) == (U,,U,)) among U,
Algorithm 1: Greedy Low-Rank Learning
parameter: :tep size 17 > 0; small 6 0
Rdxr via GD un-
r + 0, Wo < 0 E [Rdx and
tl it reaches a stationary point (oo),, i.e..
Ua(o)) dddx
(C)) = O. At convergence, W, == (o( )U, (oo) is a critical point of (2), and we call it the r-th critical point of GLRL. If W, is further minimizer of f(-) in St. or equivalently, I (-W.)((W)) (see Lemma C.2), GLRL. returns Wr: otherwise GLRL enters phase r + 1.
while A1 V f(W,)) 0 do
u f unit top eigenvector of -V((W, --)
U,(0) + ( Veu,l E R
for = 0, 1..1....d do
L (t + + - (-(t))nC((,,()) W, + U,( (xo)
To set the initial point of GD in phase r, GLRL appends a small column vector d, E Rd to the resulting stationary point (00) from the last phase, i.c., (0) <
return W
(xc) 5,1 E Rdxr (in
the case of = 1. U, (0)+ + [8,] e ([]RR)) 1d) In this way, (O)U, (0) W, 5,6,7 is perturbed
"In practice, we approximate the infinite time limit by running sufficiently many steps.
away from the (r (r-11) 1) 1)-th critical point. In GLRL, set 5, Veu,,, where u, is the top eigenvector of (W,,)) ) with unit norm ||22,112 and e > 0 is a parameter controlling the magnitude of perturbation (preferably very small). Note that it is guaranteed that (aa-V/(W,,-) > O; otherwise W is a minimizer of the convex function ʃ(-) in Sj and GLRL exits before phase r.
4

---

Published as a conference paper at ICLR 2021
Trajectory of GLRL. We define the (limiting) trajectory of GLRL by taking the learning rate 7 + O. The goal is to show that the trajectory of GLRL is close to that of GF with infinitesimal initialization. Recall that oWo, o. t) stands for the solution W in (2) when W(O) Wo-
Definition 5.1 (Trajectory of GLRL). Let W 0,e == 0 be the Oth critical point of GLRL. For every 2 1, if the (r 1 critical point r,,, exists and is not minimizer of f(-) in S we define W (t) := o ( r-1. + eur eur, t). where ur is a top eigenvector of V.(WW r-.e)) with unit norm, ||u,,ell2 = 1. We define Wr,e == lim W r,e (t) to be the r-th critical point of GLRL if the limit exists.
Throughout this paper, we always focus on the case where the top eigenvalue of every V Vf(W,,. -.,,e unique. In this case, the trajectory of GLRL is unique for every E >> O, since the normalized top eigenvectors can only be Ur and both of them lead to the same W
r.c (t).
5.1 THE LIMITING TRAJECTORY: A GENERAL THEOREM FOR DYNAMICAL SYSTEM
To prove the equivalence between GF and GLRL, we first introduce our high-level idea by analyzing the behavior of a more general dynamical system around its critical point, say 0. A specific example is (2) if we set to be the vectorization of W.
d0
(6) We use Φ(Oa. t) to denote the value of (()) in the case of @(0) = Oo. We assume that g(0) is C²-smooth with I()) being the Jacobian matrix and Φ(0..) t) exists for all 0g and t. For ease of presentation, in the main text we assume ((] is diagonalizable over TR and defer the same result for the general case into Appendix G.3. Let (0) = V VDVI be the eigendecomposition, where V is an invertible matrix and D diag(jn. ..... pd) the diagonal matrix consisting of the eigenvalues A 2 ui 2.... .... 2 ja. Let V = (Ø)...., 0.) and V-1 = (uI...., ūa) T then ü, é; are left and right eigenvectors associated with it and ü, 0, 5.j. We can rewrite the eigendecomposition as (()) = -i= ".," We also assume the top eigenvalue رú is positive and unique, Note شJ > 0 means the critical point 0- = 0 is unstable, and in matrix factorization it means 0 is a strict saddle point of 2(.) ). The key observation is that if the initialization is infinitesimal, the trajectory is almost uniquely determined. To be more precise, we need the following definition:
dt g where g(0) =.
Definition 5.2. For any Og E IRd and u E Rd, we say that (0a {0a)ac(0.1) converges to Gg with positive -. a-+0 To.- To00-0011 u) O.
alignment with u if lim O, = O, and lirn inf a-+0
special case is that the direction of 0,, 0g converges, i.e., 0 == lim To 0
0. 0
exists. this
case, } has positive alignment with either means any convergent sequence generically falls into either of these two categories.
except for aero-measure subset of 0. This
The following theorem shows that if the initial point 0., converges to O with positive align- ment with ún as a + 0, the trajectory starting with 0. converges to a unique trajectory =t) == o + I {0a} with positive alignment to ū1, which is x'(t) == of o(-aūj, t surprising: different initial points should lead to very different trajectories, but our analysis shows that generically there are only two limiting trajectories for infinitesimal initialization. We will soon see how this theorem helps in our analysis for matrix factorization in Sections 5.2 and 5.3.
fi log 4). By symmetry, there is another unique trajectory for sequences
jiy log 2) This is somewhat
Theorem 5.3. Let zo (f) := ((a01, ++ 1 log for every a > O, then (t) := lim,- Za (t) exists Ps
and is also a solution of (6), ie.., x(t) = ((=(0),)) t). If 6, converges to O with positive alignment with ú1 as a + O. then Vt E IR, there a constant C > 0 such that
| (Sa.t+
++ 1 log (6..
x(t) SC 11
P1
for every sufficiently small a, where 7 = # u22 > 0 is the eigenvalue gap.
Proof sketch. The main idea is linearize the dynamics near origin as we have done for the first warmup example. For sufficiently small 0, by Taylor expansion of g()), the dynamics is approximately de ~ (()), which can be understood as a continuous version of power it- eration. If the linear approximation is exact, then O()) e())) For large enough to.
dø
5

---

Published as a conference paper at ICLR 2021
e'oJ10) -'== ū, cBito ū + O(clito). Therefore, as long as the initial point (()) has a positive inner product with új (to) should be very close to eÙj for some e > 0, and the rest of the trajectory after to should be close to the trajectory starting from eti However, here is tradeoff: we should choose to to be large enough so that the power iteration takes effect; but if to is so large that the norm of (fo) reaches constant scale, then the linearization fails unavoidably. Nevertheless, if the initialization scale is sufficiently small, we show via a careful error analysis that there is always a suitable choice of to such that ((t) is well approximated by eÙj and the difference between 0 (fo + t) and @(c0), t) is bounded as well. We defer the details to Appendix G.
5.2 EQUIVALENCE BETWEEN GD AND GLRL: RANK-ONE CASE
Now we establish the equivalence between GF and GLRL in the first phase. The main idea is to apply Theorem 5.3 on (2). For this, need the following lemma on the eigenvalues and eigenvectors.
Lemma 5.4. Let g(W) == - (W) WWWWWW
and JW) be its Jacobian. Then (() is
symmetric and thus diagonalizable. Let- (V = Σ 1 119 be the eigendecomposition of the symmetric matrix - ((),, where μ1 2 U2 2 ... 2 pd. Then J(] has the form:
d
J(O)A ΣΣ (m + pb) (A. un 11 =1
(8)
where [O] stands for the resulting matrix produced by left- meft-multippying J(O) to the vectorization of A. For every pair of iiiss j S d, p4 + H1 is an eigenvalue of J (0) and u1 "T + "1())
is a corresponding eigenvector. All the other eigenvalues are O.
We simplify the notation by letting u := W1[1]. direct corollary of Lemma 5.4 is that u dnnn is the top eigenvector of J(O). According to Theorem 5.3, now there only two types of trajectories, which correspond to infinitesimal initialization W. + 0 with positive alignment with u or -u As the initialization must be PSD, W., 0 cannot have positive alignment with _u For the former case, Theorem 5.6 below states that, for every fixed time I, the GF solution <(W., T(W.) + t) after shifting by a time offset T (WW.)= := 2n log( (W. a. us (,u))=)) converges to the GLRL solution (t) as Wa + O. The only assumption for this result is that 0 is not minimizer of f(-) in S (which is equivalent to (-v > 0) and - f() has an eigenvalue gap. In the full observation case, this assumption is satisfied easily if the ground-truth matrix has a unique top eigenvalue. The proof for Theorem 5.6 is deferred to Appendix I.1.
Assumption 5.5. f1 > max (12, 0), where μ4 == Theorem 5.6. Under Assumption 5.5, the following limit (t) exists and is a solution of (2).
A22 == f(0)..
((( = lim W e
2pm log ! +++ ++)+
=lim= lim & (curuT, 2nr log ! +t).
-+0
Let (Wa) S St be PSD matrices converging to with positive alignment with u u as a +
that is, lima-so W.. = 0 and 3ao, q > 0 such that <Was u,,uu )= 2 q [| lp for all a cg. Then
Vt E R, there is constant C > O such that
1 log (W..uru,) u.) ④ Wa 2pr
+ r - (T(()
SC SCIWall
(10)
for every sufficiently small a, where = 2/11 (m1 + (2) = p41 112-
It is worth to note that (() has rank S for any t E TR, since every W 1,e (t) has rank < 1 and the set St.51 is closed. This matches with the first warmup example: GD does start learning with rank-l solutions. Interestingly, in the case where the limit W := lim (((() happens to be minimizer of f(-) ) in $ GLRL should exit with the rank-1 I solution W, after the first phase, and the following theorem shows that this is also the solution found by GF.
Assumption 5.7. S(W) is locally analytic at each point.
Theorem 5.8. Under Assumptions 5.5 and 5.7, if (1)le is bounded for all 1 2 O, then the limit W, = lim (1) exists. Further, if W, is a minimizer of (() in St. then for PSD
matrices (Wa) C St converging to 0 with positive alignment with unui as + 0, it holds that lim to o (W., Wa,4. l) W

---

Published as a conference paper at ICLR 2021
Assumption 5.7 is natural assumption, since f(-) in most cases of matrix factorization is quadratic or polynomial function (e.g., matrix sensing, matrix completion). In general. it is unlikely for a gradient-based optimization process to get stuck at saddle points (Lee et al., 2017; Panageas et al., 2019). Thus, we should expect to see in general that GLRL finds the rank-1 I solution if the problem is feasible with rank-1 matrices. This means at least for this subclass of problems, the implicit regularization of GD is rather unrelated to norm minimization. Below is a concrete example:
Example 5,9 (Counter-xxample of Conjecture 1.1, Gunasekar et al. 2017). Theorem 5.8 enables us to construct counterexamples of the implicit nuclear norm regularization conjecture in (Gunasekar et al.. 2017). The idea is to construct a loss L : Rdxd + IK where every rank-1 stationary point of ((U) attains the global minimum but none of them is minimizing the nuclear norm. Below we give concrete matrix completion problem that meets the above requirement. Let M be partially observed matrix to recovered, where the entries are observed and the others (marked with "?") are unobserved. The optimization problem is defined formally by (UU) = (UU ((W) = 2 (ii))enWW
= {11,3, 3). (1,4), (2,3), (3, 1), (3, 2), (4, 1))
M,y)²
?
?
1
R
[R
1
1
R
1
R
1
R
?
R
R
R
R²
R
R
M
M norm
Mrank
1
R
?
?
1
R
R
1
1
R
1
R
R
?
?
?]
R
1
R.
R
R2
R
R
Here R > is large constant, e.g., R 100. The minimum nuclear norm solution is the rank-2
matrix Mnorm which has || |Mooorll- I = 4R (which is 400 when R = 100). Mrank is a rank-1
solution with much larger nuclear norm, | ll. = 2R +-2 (which is 20002 when R = 100). We can verify that f(-) satisfies Assumptions 5.5 and 5.7 and WF()) converges to the rank-1 solution M Therefore, GF with infinitesimal initialization converges to Mrank rather than norm- which refutes the conjecture in (Gunasekar et al., 2017). See Appendix D for formal statement.
5.3 EQUIVALENCE BETWEEN GD AND GLRL: GENERAL CASE
Theorem 5.6 shows that for any fixed time t, the trajectory of GLRL in the first phase approx-
imates GF with infinitesimal initialization, i.e., ((( lima- W. (t), where (!())
- log((W., " + 1). However, (x()) + lima- W. (oo) does not hold in ((W,, 2/41
general, unless the prerequisite in Theorem 5.8 is satisfied, i.e., unless W WT (oo) is a minimizer result that GD converges to local minimizers (Lee et al., 2016; 2017). We adapt Theorem 2 of Lee et al. (2017) to the setting of GF (Theorem I.5) and obtain the following result (Theorem 5. 5.1;); see Appendix 1.4 for the proof.
of f(-) in S This is because of the
Theorem 5.10. Let f RRaxd - TR. be a convex C2-smooth function. (1). All stationary points of L: C: Edxd + R, L(U)= ff(UUT) are either strict saddles or global minimizers; (2). For any random initialization, GF (1) converges to strict saddles of C(U) ) with probability 0.
Therefore, for convex (()) such as matrix sensing and completion, suppose ʃ(-) has no rank-1 PSD) minimizer, then no matter how small a is, (a( (if exists) is a minimizer of f(.) ) with a higher rank and thus away from the r matrix W 1. In other words. W (t) only describes the limiting trajectory of GF the first phase, i.e., when GF goes from near 0 to near W After a sufficiently long time (depending on (),, GF escapes the critical point W 1, but this not described by (I).
To understand how GF escapes W 1. a priori, we need to know how GF approaches WT. Using a similar argument for Theorem 5.3, Theorem 5.11 shows that generically GF only escapes in the direction of 0; peT where VI is the (unique) top eigenvector of SVW(W) 1). and thus the limiting trajectory exactly matches with that of GLRL in the second phase until GF gets close to another critical point Wa E $2 If Wa is still not a minimizer of f(.) in S (but it is local minimizer in d. generically), then GF escapes Wa and the above process repeats until Wr x is a minimizer in St for some K. Here by "generically" we hide some technical assumptions and we elaborate on them in Appendix J. See Figure and Figure 2 for experimental verification of the equivalence between GD and GLRL. We end this section with the following characterization of GF;
Theorem 5.11 (Theorem I.2, informal). Let W be a critical point of (2) satisfying that W is a local minimizer of f(.) in St for some r 1 but not minimizer in ST. Let -VS(W)
7

---

Published as a conference paper at ICLR 2021
[Wi -20 19
[W]:]] -2
10
Woog =1g
13
[W101]: =0
10-
[RiCr) -20
16'
1W0 21 2011-mmm 10
10"
12"
20
04
trajectory of depth-2 GD. Won(O) converges trajectory GLRL. Wanar (0). initialization scale goes We plot dist(t) = minger || Wan(f)- - Warm(t)) for different initiaizattinn scale ((0) where T is a discrete subset of I that 5 coverss the entire trajectory of GLRL: max, mingrrr (t) WWaR (f') F S á for 6 z 0.00042. For each [|W (0)lle we run 20 random seeds and plot them separately. The ground truth W R as randomly generated rank-3 matrix with W || 20. 30% entries are observed. See more in Appendix E.I.
Figure 1:
Eiz i' be the eigendecomposition of VS(W). If > #22 and if there exists time To E TR for every a so that "WWa,To Ta) converges to W with positive alignment with the top principal component in di as - 0, then every fixed t, lima-+o o( Ta 24s log (J.We.Ta).ne.)
+t)
exists and is equal to WG lim o6 W c010 2p1
log 1 + t).
Characterization of the trajectory of GF. Generically, the trajectory of GF with small initialization can be split into K phases by K K+1 critical points of (2), (W,} (Wo = 0), where in phase GF escapes from W -1 in the direction of the top principal component of - WVS(W r-1) and gets close to W.. r. Each W, is a local minimizer of f(-) in st. but none of them is minimizer of f(-) in Sj except WK. {W, WJ o corresponds to { [W,, wW,eefe r,ee) in Definition 5.1 with infinitesimal e > 0.
k. The smaller the initialization is, the longer GF stays around each W,. Moreover,
6 BENEFITS OF DEPTH: A VIEW FROM GLRL
In this section, we consider matrix factorization problems with depth L 2 3. Our goal is to
understand the effect of the depth-Li L parametrization W UUU2.... UL on the implicit bias - how does depth encourage GF to find low rank solutions? We take the standard assumption in existing analysis for the end-to-end dynamics that the weight matrices have a balanced initialization, i.e. U. (0) = U++1 (0)U (0), V1 < i S L-11 1. Arora et al. (2018) showed that if (U:) is balanced at initialization, then we have the following end-to-end dynamics. Similar to the depth-2 case, we use o(W t) to denote W (t), where
dW -- ==
(WW (VV W)
(11)
dt The lemma below is the foundation of our analysis for the deep case, which greatly simplifies (11). Due to the space limit, we defer its derivations and applications into Appendix K.
Lemma 6.1. For M(I) = ((1)2/4, we have dM de (33
M (M
Our main result, Theorem 6.2, gives a characterization of the limiting trajectory for deep matrix factorization with infinitesimal identity initialization. Here W(1) = lima--o W (f) is the trajectory of deep GLRL, where W (t) == δaaeje,, a (1-1/P) ( + t) (see Algorithm 2). The dynamics for
general initialization is more complicated. Please see discussions in Appendix L.
Theorem 6.2. Let P = +.4 T. 2 3. Suppose [|V](0))lz = (()))(()) > max (2))))(()) a-1-1/9 2p1(P-1) + ((t) | = =0(a =(a
for every fixed t E R, (1,
(12)
and for any? 2 < kSa dd,
-011 for every fixed L E R, dn (ob (oI, (11P-11 + +)) O(a).
(13)
So how does depth encourage GF to find low-rank solutions? When the ground truth is low-rank, say rank-k, our experiments (Figure 2) suggest that GF with small initialization finds solutions with smaller d-low-rankness compared to the depth-2 case, thus achieving better generalization. At first glance, this is contradictory to what Theorem 6.2 suggests, i.e., the convergence rate of deep GLRL at constant time gets slower the depth increases. However, it turns out the uniform upper bound for the distance between GF and GLRL is not the ideal metric for the eventual E-low-ranknes, of learned solution. Below we will illustrate why the r-low-rankness of GF within each phase is better metric and how they are different.
Definition 6.3 (r-low-rankness). For matrix M E Rdxd, we define the r-lowwranknesss of M as V VEL d / (M), where ((M) is the i-th largest singular value of M.
We believe assumption [[)]l, 1 (())((0) could he removed with more refined analysis.
8

---

Published as a conference paper at ICLR 2021
10-02
-00
10
10
32-0
15th
1841
16
10
2008
L-22 [W/01g -10->
2. (W101] -10--
2.2. PW101] -10-
-2 pW001] - 100
L- pw:01] - 10
101
10P
100
10
100
10-
12-1
32
12
16.
10
20
221
10
20F
30
121
30
32
12'
10
32
101
[Win0]-
-10-3
-15-4
[WiDi] 10-4
195
[Win1] 10:4
[Wi0t]- -10
20
23-1
33-4
11-2
11-
1:00
10-10
1011
10-0
1040
1st
L- [W1D]] -1
[WIDI]
[WIDIj -10
[WIDIj--10
L-4. [W/01] 110
107
10
12
12
1000
2003
1003
220
0.5 0.50
0.75
235 3.50 0.75
3.5
Figure 2: GD passes by the same critical points grad norm
distance
f-low-rankness
when initialization scale small, gets much closer the critical
points when L 2 3. 2 GD requires a much smaller initialization scale to maintain small low-rankness. Here the ground truth matrix W E x =00x200 of rank as stated in Appendix E.I. In this case. GLRL has 3 phuses and 4 critical points (W .), r-- where Wo O and Wa W For each depth I. and initialization scale [WO]] we plot the distance between the current step of GD and the closest critical point of GLRI, [tW W.lle. the norm of fall gradient, VVV,, L)l and the (r 1)-low-randee low-rankknss of Wao with arg minosyga (t) W.lle
Suppose (()) admits unique minimizer Wo in S and we run GF from of for both depth-2 2 and depth-L cases. Intuitively, the I-low-rankness of the depth-2 solution is (0/=1// which can be seen from the second warmup example in Section 4. For the depth-L solution, though it may diverge from the trajectory of deep GLRL more than the depth-2 solution does, its 1-low-rande moo-ranksess is only ((a), shown in Theorem 6.4. The key idea is to show that there is basin in the manifold of rank-1 matrices around Wo such that any GF starting within the basin converges to Wo- Based on this, prove that starting from any matrix ((a)-close to the basin, GF converges to solution (la)-close to Wo. See Appendix M for more details.
Theorem 6.4. In the same settings Theorem 6.2, if (oo) exists and is minimizer of f(-) in St under regularity assumption M.1, we have infrER | (ad, W O(a).
Interpretation for the advantage of depth with multiple phases. For depth-2 GLRL, the low- rankness is raised to some power less then per phase (depending on the eigengap). For deep GIRLI, show the low-rankness is only multiplied by some constant for the first phase and speculate it to be true for later phases. This conjecture is supported by our experiments; see Figure 2. Interestingly, our theory and experiments (Figure 5) suggest that while being deep is good for generalization, being much deeper may not be much better: once L 2 3, increasing the depth does not improve the order of low-rankness significantly. While this theoretical result is only for identity initialization, Theorem F.1 and Corollary F.2 further show that the dynamics of GF (11) with any initialization pointwise converges as + xi, under a suitable time rescaling. See Figure for experimental verification.
7 CONCLUSION AND FUTURE DIRECTIONS
In this work, connect gradient descent to Greedy Low-Rank Learning (GLRL) explain the success of using gradient descent to find low-rank solutions in the matrix factorization problem. This enables construct counterexamples to the implicit nuclear norm conjecture in (Gunasekar et al., 2017). Taking the view of GLRL can also help us understand the benefits of depth.
ACKNOWLEDGMENTS
The authors thank Sanjeev Arora and Jason D. Lee for helpful discussions. The authors also thank Runzhe Wang for useful suggestions on writing. ZL and YL acknowledge support from NSF, ONR, Simons Foundation, Schmidt Foundation. Mozilla Research, Amazon Research, DARPA and SRC. ZI. is also supported by Microsoft PhD Fellowship.

---

Published as a conference paper at ICLR 2021
REFERENCES
Akshay Agrawal, Robin Verschueren, Steven Diamond, and Stephen Boyd. A rewriting system for convex optimization problems. Journal of Control and Decision, 5(1):42-60, 2018.
Sanjeev Arora, N Cohen, and Elad Hazan. On the optimization of deep networks: Implicit acceleration by overparameterization. In 35th International Conference on Machine Learning, 2018.
Sanjeev Arora, Nadav Cohen, Wei Hu, and Yuping Luo. Implicit regularization in deep matrix factorization. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' Alché-Bus Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 7411-7422. Curran Associates, Inc., 2019a.
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Russ R Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 8139-8144 8148. Curran Associates, Inc., 2019b.
Mohamed Ali Belabbas. On implicit regularization: Morse functions and applications to matrix factorization. arXiv preprint arXiv:2001.0422 2020.
Jeff Bezanson, Stefan Karpinski, Viral B Shah, and Alan Edelman. Julia: A fast dynamic language for technical computing. arXiv preprint 120955145, 2012.
Yuejie Chi, Yue M Lu, and Yuxin Chen. Nonconvex optimization meets low-rank matrix factorization: An overview. IEEE Transactions Signal Processing, 37(20):5239-5266) 2019.
Lénaïc Chizat and Francis Bach. Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss. volume 125 of Proceedings of Machine Learning Research, pages 1338. PMLR, 09-12 Jul 2020.
Lénaic Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable programming. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché- Buch E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 2937-2947. Curran Associates, Inc., 2019.
Francis H. Clarke, Yuri S. Ledyaev, Ronald J. Stemn, and Peter R. Wolenski. Nonsmooth analysis and control theory, volume 178. Springer Science & Business Media, 2008.
Frank H. Clarke, Generalized gradients and applications. Transactions of the American Mathematical Society, 205:247-262, 1975.
Frank H Clarke. Optimization and Nonsmooth Analysis. Society for Industrial and Applied Mathe- matics, 1990. doi: 10.1137/1.978 1778111111 1111111999111 1971309.
Steven Diamond and Stephen Boyd. CVXPY: A Python-embeddde modeling language for convex optimization. Journal of Machine Learning Research, 17(83)11-5, 2016.
Simon Du and Jason Lee. On the power of over- parametrization in neural networks with quadratic activation. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 1329-1338, Stockholmsmässan, Stockholm Sweden, 10-15 Jul 2018. PMLR
Gauthier Gidel, Francis Bach, and Simon Lacoste-Juiee Julien. Implicit regularization of discrete gradient dynamics in linear neural networks. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' Alché-But E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 3196-3206. 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, 2020.
Suriya Gunasekar, Blake E Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Srebro. Implicit regularization in matrix factorization. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems 30, pages 6151-6159. Curran Associates, Inc., 2017.
10

---

Published as a conference paper at ICLR 2021
Suriya Gunasekar, Jason D Lee, Daniel Soudry, and Nati Srebro. Implicit bias of gradient descent on linear convolutional networks. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa- Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems 31, pages 9482-9491 Curran Associates, Inc., 2018.
Benjamin D. Haeffele and René Vidal. Structured Law- Matrix Factorization: Global Optimality, Algorithms, and Applications. IEEE Transactions on Pattem Analysis and Machine Intelligence (PAMI), 4266)1146811482, 2019.
Jean-Baptiste Hiriart-Urruty and S. Lewis. The clarke and michel-penot subdifferentials of the cigenvalues of symmetric matrix. Comput. Optim. Appl., 13(1-3):1322) 1999. doi: 10.1023/A.
1008644520093.
Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa- Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems 31, pages 8571-8580 Curran Associates, Inc., 2018.
Ziwei Ji and Matus Telgarsky. Gradient descent aligns the layers of deep linear networks. In International Conference on Learning Representations, 2019a.
Ziwei Ji and Matus Telgarsky. A refined primal-dual analysis of the implicit bias. arXiv preprint arXiv:/906. 04540, 2019b.
Rajiv Khanna, Ethan Elenberg, Alexandros G Dimakis, and Sahand Negahban. On approximation guarantees for greedy low rank optimization. arXiv preprint arXiv:1703.02221, 2017.
Jason D Lee, Max Simchowitz, Michael Jordan, and Benjamin Recht. Gradient descent only converges minimizers. In Conference on learning theory. pages 1246-1257, 2016.
Jason D Lee, Ioannis Panageas, Georgios Piliouras, Max Simchowitz, Michael Jordan, and Benjamin Recht. First-order methods almost always avoid saddle points. arXiv preprint 17010:171, 2017.
Yuanzhi Li, Tengyu Ma, and Hongyang Zhang. Algorithmic regularization in over- over--arametten parameterized matrix sensing and neural networks with quadratic activations. In Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet, editors, Proceedings of the I Conference On Learning Theory, volume 75 of Proceedings of Machine Learning Research, pages 2-47, PMLR, 06-09 Jul 2018.
Kaifeng Lyu and Jian Li. Gradient descent maximizes the margin of homogeneous neural networks. In International Conference on Learning Representations, 2020.
Mor Shpigel Nacson, Suriya Gunasckar, Jason Lee, Nathan Srebro. and Daniel Soudry. Lexicographic margins in homogeneous and non- non-homogeneous deep models. Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 4683-4692, Long Beach, California, USA, 09-15 Jun 2019a. PMLR.
and
Mor Shpigel Nacson, Jason Lee, Suriya Gunasekar, Pedro Henrique Pamplona Savarese, Nathan Srebro, and Daniel Soudry. Convergence of gradient descent separable data. In Kamalika Chaudhuri and Masashi Sugiyama, editors, Proceedings of Machine Learning Research, volume 89 of Proceedings of Machine Learning Research, pages 3420-3428. PMLR, 16-18 Apr 2019b.
Mor Shpigel Nacson, Nathan Srebro, and Daniel Soudry. Stochastic gradient descent on separable data: Exact convergence with fixed learning rate. In Kamalika Chaudhuri and Masashi Sugiyama, editors, Proceedings of Machine Learning Research, volume 89 of Proceedings of Machine Learning Research, pages 3051-3059, PMLR, 16-18 Apr 2019c.
Ioannis Panageas, Georgios Piliouras, and Xiao Wang. First-order methods almost always avoid saddle points: The case of vanishing step-sizes. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Curran Associates, Inc., 2019.
Systems 32, pages 6474-6488
11

---

Published as a conference paper at ICLR 2021
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary Vito,, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang. Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Bus E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 8024-8035.
Curran Associates, Inc., 2019.
Lawrence Perko. Differential equations and dynamical systems, volume Springer Science Business Media, 2013.
Noam Razin and Nadav Cohen. Implicit regularization in deep learning may not be explainable by norms. arXiv preprint arXiv:2005.06:3 06.398 2020.
Shai Shalev-Shwartz and Yoram Singer. On the equivalence of weak learnability and linear separa- bility: New relaxations and efficient boosting algorithms. Machine learning, 80(2-3):141-63, 2010.
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The implicit bias of gradient descent on separable data. Journal of Machine Learning Research, 19(70):1-57, 8a.
Daniel Soudry, Elad Hoffer, and Nathan Srebro. The implicit bias of gradient descent separable data. In International Conference on Learning Representations, 2018b.
Tijmen Tieleman and Geoffrey Hinton. Lecture 6.5-rmsprop: Divide the gradient by running average of its recent magnitude. COURSERA: Neural networks for machine learning, 4(2):26-31, 2012.
Zheng Wang, Ming-Jun Lai, Zhaosong Lu, Wei Fan, Hasan Davuleu, and Jieping Ye. Rank-one matrix pursuit for matrix completion. In International Conference on Machine Learning, pages 91-99, 2014.
Ashia C Wilson, Rebecca Roelofs, Mitchell Stem,, Nati Srebro, and Benjamin Recht. The marginal value of adaptive gradient methods in machine learning. In Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances Neural Information Processing Systems 30, pages 4 4148-4158. Curran Associates, Inc., 2017.
Quanming Yao and James Tin Yau Kwok. Greedy learning of generalized low-rank models. In IJCAI International Joint Conference on Artificial Intelligence, 2016.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understand- ing deep learning requires rethinking generalization. In International Conference Learning Representations, 2017.
Stanistaw Lojasiewicz. Ensembles semi-analytiques. IHES notes, 1965.
12

---

Published as a conference paper at ICLR 2021
A COMPARISON TO EXISTING GREEDY ALGORITHMS FOR RANK-CONSTRAINED OPTIMIZATION
The most related one to GLRL (Algorithm 1) is probably Rank-I Mairix Pursuit (RIMP) proposed by Wang et al. (2014) for matrix completion, which was later generalized to general convex loss in (Yao and Kwok, 2016). RIMP maintains set of rank-1 matrices the basis, and in phase RIMP adds the same u, as defined in Algorithm into its basis and solve mina f(Σ i for rank-r estimation. The main difference between RI RIMP and GLRL is that the optimization in each phase of RIMP is performed on the coefficients a, while the entire U, evolves with GD in each phase of provide empirical evidence that GLRL generalizes better than R MP when
GLRL. In Figure ground truth is low-rank, although GLRL may have higher computational cost depending on v),
Similar RI RIMP, Greedy Efficient Component Optimization (GECO, Shalev-Shwartz and Singer 2010) also chooses the r-th component of its basis as the top eigenvector of f while solves ming f( By for the rank-r estimation. Khanna et al. (2017) provided convergence guarantee for GECO assuming strong convexity. Haeffele and Vidal (2019) proposed local-descent meta algorithm, of which GLRL can be viewed as a specific realization.
B DEEP GLRL ALGORRITM
Algorithm 2: Deep Greedy Low-Rank Learning (Deep GLRL)
parameter: : :seep size >> 0; small e 0
é' é' e//L L (U1,--. ... Ur.) == f(W,... Wt). Wo + Rdxd and Uo (oc),..., (00) Rdx0 empty matrices
while A1 vf (W+)) 0 do
r r
let u, be top (unit) eigenvector of -VS (W,-1)
(0) + [ (U0),,(00)
c'ur) Rddr
U U,-1,((00) 0
Ur, f-
E E for all 2 < k: < L 1
0
(0) +- U,-1,2(00) e'u,
E Brxd
fort = 0, 0. do
L Ut. 1) + (t,(t) VV,, (..(()),1ssis W, + (xc) (2x))......()))))) (n0)
return W,
C PRELIMINARY LEMMAS
Lemma C.I. For Un E Bdxx and Wo = U,U, the following statements are equivalent:
(I), Uo is a stationary point of C(U) (UUT)
(2). Vf(Wo) 0;
(3). W, U,U is critical point of (2).
Proof. (2) - (3) is trivial.
We only prove (1) = (2), (3)=
Proof for (1) = (2). If Uo is stationary point, then 0 = VL(U)) Vf(W)) So (((W)) Wo (V/(W))U))) -
Proof for (3) - (1). If Wi is critical point, then
0= (g)), ((())) = -2 -2 -2TI(V/(WWWWW///WW = - V/ which implies (LU,) 0.
13

---

Published as a conference paper at ICLR 2021
Lemma C.2. For stationary point Uo Rd of L(U) ( where f(.) is conver, Wo U attains the global minimum of f(.) in S == { W = 0) iff V =
Proof. Since f(W) is convex function and S is convex, know that Wo is global minimizer of (WW in S iff
(V)( Wo) 20,
VW Σ 0.
(14)
Note that (V.(Wo): Wo) (W,, By Lemma C.1, (VF(W)), Wo) = 0. Combining this with (14), we know that Wo is a global minimizer iff
(V/(W)) W 2 O,
MA = 0.
(15)
is easy to check that this condition equivalent Vf(WW) =
D PROOFS FOR COUNTER-EXAMPLE
Conjecture D.1 (Formal Statement, Gunasekar et al. 2017). Suppose f Raxd - R is quadratic function and min f(W) 0. Then for any Wint > 0 if W lim lim @(a exists t-
W'00
and /(Wi) = 0, then W ||-
[W]|. s.t. f(W)= 0. W20
min
Propsition D.2 (Formal Statement for Example 5.9). For constant R > 1, let
?
R
R
1
R
R
1
R
?
R
1
R
R
1
R
R
R
R
M
M Mnorm
and Mrank
R
1
R
R
1
R
?
?
R
1
R
R
R
R
R
and
((U) = -00)=5(000 f(UU)) f(W)
Σ
(Wy M1y)
2
(KJ)ER
where Ω ((1,3), (1,4), (2,3), (3, (3.2),,.,
Then for any Wini ł 0, s.t. Wint > 0.
lim lim ②( (nii, Mrank- +00
Moreover, we have
Mrank ll. = 2R +2 4R |
M
min
W ll..
W
Proof. We define WL,(), (F) in the same way as in Definition 5.1, Theorem 5.6.
(4) = & TT)) (f(()= = lim W log + t). --0
2pm
Below will show
1. Assumption 5.7 and Assumption 5.5 are satisfied.
2. (1))p bounded for / 2 0;
3. lim (t) = Mranki
4. M Maorm arg min Wl..
14

---

Published as a conference paper at ICLR 2021
Thus Since Mank is a global minimizer of f( applying Theorem 5.8 finishes the proof. Proof for Item 1. Let Mo = (f)) then
0
0
1
R
0
R
0
M.
1
R
0
0
R
0
0
Let A := [ 0) then we have (A) = 1+V1+12 .2((A) = V-VI+ thus (A > [A2(A) > 2
2
0 > A2(A). As result, (A) = || |l Let vn E R2 be the top eigenvector of A. We claim that u1 = [ E Rd is the top eigenvector of (0)) First by definition is easy to check that Mau A1 (A) Further noticing that M = A²
0 A² we know (M)) (A) AB(A) - 22 (A). (M = (2 and >, = (A). Thus Assumption 5.5 is satisfied. Also note that f is quadratic. thus analytic, i.e., Assumption 5.7 is also satisfied.
for all eigenvalues (MM)). That is. (M X1 (A). Xg
Proof for Item 2. Let (x, (t), (t)) R2 be the gradient flow of g(x, v) = (=² - 1)2 + (zy R)² starting from (0), Ve (0)) = VeU1.
dx((t) dt
(1 x<()))=((() 2v(()((()xx()) R)
(16)
dy(() 2x (00((())))) R)
dt
Let Wt(t) be the following matrix:
[t)
(t)
Wc(1)
(x)(t) (t()) ze(t) vc(t)].
(t)
(ee(t)
Then it easy verify that W.(0) W (0) and (t) satisfies (2). Thus by the existence and
uniqueness theorem, we have We(t) = W (t) for all t. Taking the limit e - O, we know that (t) can also be written in the following form:
2
(t)
wF(
[x((t)
v(t) x(t) v(t),,
=
att)
[t(()
and (z) (t)) E 2 is a gradient flow of g(x, y) _122 1)2 + (xy- - R)2.
Since g(x(t), y()) is non-increasing overtime, and lim g(0(- t), v( (t)) = g(x(-oo), v()) = 10-2
g(0. 0) R² + 0.5, we know (x())((t) s 3R for all t. So whenever (t) - -=²(t)= 2 9RR we have (1) < गल < - < 1. In this case, 2()) 2x 2x)(1(2=²(1) 1) 0. Combining this with y( - x2 = 0 < 9R², we have (t) - 2²()) < 9RR for all t, which also implies that (t) is bounded. Noticing that 9 2 g(x(t),v(t)) (2² - 1 we know (²) is also bounded. Therefore, ( is bounded.
9/2
Proof for Item 3. Note that (I(20), y0 y(0o)) is a stationary point of g y). It is clear that g(r y) only has stationary points- (0, 0), (1, R) and (-1, - R). Thus W, can only be or Mrank- However, since for t, (W) < f(),, W, lim, W (t) cannot be O. So W, must be Mrank-
Proof for Item 4. Let mij be (i,j th element of M. Suppose M > 0, have
(e: -a) M(ei ea) 2 0 - mi1 + m44 2 m14 + m41 = 2R
(ez es) M(ea es) 2 M22 + ma3 m23 + M32 2R
15

---

Published as a conference paper at ICLR 2021
Depth (I.
Simulation method
Constant LR, 1j 10 for 10 iterations
Adaptive LR. 17 2 x 10 and 10 for 10th iterations
Adaptive LR, 3 x 10 andd 10 for 10 iterations
Table 1:
Choice of hyperparameters for simulating gradient flow. For L = 2. gradient descent escapes saddles in (log )) time, where is the distance between the initialization and the saddle.
Thus 4R = minm (0 W
where the equality is only attained at my = R, - 1,2,3,
Otherwise, either that M 2 O.
mi1 m41
mh4
or
m22
1223
will have negative eigenvalues. Contradiction to
M844
m2g2
m233
1
-1
1
0
07
Below we will show the rest unknown off-diagonal entries must be Let
0
0
0
1
then
0
13
M22
m14
M22
M 0 = VMV 2 -
M31
R
R
> 0,
m41
m44
which implies m13 m23, M11 1211
[
0
0
0
With the same argument for V
1
0
0
we have m13 m14, 17233
1224-
Also
0
0
1
-1
note M is symmetric and ma thus maj Myj Vi 2, 3, 4.
Thus M M
arg w2o, [ Wll. which is unique.
E EXPERIMENTS
E. GENERAL SETUP
The code is written in Julia (Bezanson et al., 2012) and PyTorch (Paszke et al., 2019).
The ground-trune truth matrix W. is low-rank by construction: we sample random orthogonal matrix U, diagonal matrix S with Frobenius norm ||S and set W, USU Each measurement X in X1.... X,, is generated by sampling two one-hot vectors u and v uniformly and setting you"
X
2 uuo
In Figures 1, 2, 3 to 5 and 7, the ground truth matrix W. has shape 20 x 20 and rank 3, where 17.41, >x(
| 1p 20, X (W*) 6.23, Az( (z)) = 5.41. = 0.3 is used for generating measurements, except = 0.25 in Figure 3, i.e., each pair of entries of Wiy and W is observed with probability p.
8.85, (W 4.31 and X1 (z(-V((0)
Gradient Descent. Let È > 0 be the Frobenius norm of the target random initialization. For the depth-2 case, we sample 2 orthogonal matrices Vi, V2 and diagonal matrix D with Frobenius norm ?, and we set U V2D'/"V,T for the depth-L case with L 3. we sample L orthogonal matrices Vi.... Vz and diagonal matrix D with Frobenius norm and set U, V,D'/LV, (Vz+1 = Vi). In this way, we can guarantee that the end-to-end matrix W = U ... Ur is symmetric and the initialization is balanced for L 3.
We discretize the time to simulate gradient flow. When L 2, gradient flow stays around saddle full-batch GD with adaptive learning rate 7,, inspired by
points for most of the time, therefore
16

---

Published as a conference paper at ICLR 2021
RMSprop (Tieleman and Hinton, 2012), for faster convergence:
1t+1 = at;; + (1 ax) V2(00))
!
9/
I-atTT +
1ell
Oz+1 0, 1n V ((0));
where a = 0.99, is the (unadjusted) learning rate. The choices of hyperparameters are summarized in Table 1. The continuous time for 0, is measured as Σ T)-
GLRL In Figures 1, 2, and 4, the GLRL's trajectory is obtained by running Algorithm 1 with 10-7 and = 10-3, The stopping criterion is that the loop has been iterated for 10" times.
E.2 EXPERIMENTAL EQUIVALENCE BETWEEN GLRL AND GRADIENT DESCENT
Here we provide experimental evidence supporting our theoretical claims about the equivalence between GLRL and GF for both cases, I. 2 and I. 2 3.
In Figure 1, we show the distance from every point on GF (simulated by GD) from random initializa- tion is close to the trajectory of GLRL. In Figure 2, we first run GLRL and obtain the critical points (W, )2= passed by GLRL. We also define the distance of matrix W to the critical points to be mino<rsa W W..lF.
E.3 HOw WELL DOES GLRL WORK?
We compare GLRL with gradient descent (with not-so-small initialization), nuclear norm minimiza- tion and RIMP (Wang al., 2014). We use CVXPY (Diamond and Boyd, 201 6; Agrawal al., 2018) for finding the nuclear norm solution. The results are shown in Figure 3. GLRL can fully recover the ground truth, while others have difficulty doing so.
d=20, |= 10
10a
GLRL, L-2
nuclear norm
10-1
RIMP
R1MP (rank 10)
loss
10-2
10-3
0.5
1.0
1.5
2.0
2.5
Continuous Time
Figure 3: GD with small initialization outperforms RIMP and minimal nuclear norm solution on synthetic data with low-rank ground truth. Solid (dotted) curves correspond test (training) loss. Here the loss f(W)= z2 W W || and f(0) 1. We run 10 random seeds for GD and plot them separately (most of them overlap).
E.4 How DOES INITIALIZATION AFFECT THE CONVERGENCE RATE TO THE RANK-1 GLRL TRAJECTORY?
We the general setting in Appendix F. In these experiments,
the constant learning rate 10-5 5 for 4 x 10 iterations. The reference matrix War obtained by running the first stage of GLRL. with W [0) 10-1 and pick one matrix in the trajectory with Wwerll about 0.6.
For every 10" {-1. -21 -4, -5), run both gradient descent and the first phase of GLRL with [(O)] = e. For gradient descent, we use random initialization so | [W(O]] is full rank w.p. The distance of trajectory to W is defined minzzo [[ W In practice,
17

---

Published as a conference paper at ICLR 2021
discretized time to simulate gradient flow, we check every during simulation compute the distance. As a result, the estimation might be inaccurate when a trajectory really close to ret.
The result is shown at Figure 4. We observe that GLRL trajectories
closer to the reference matrix Wer by magnitudes. Thus the take home message here is that GLRL is in general a more computational efficient method to simulate the trajectory of GF (GD) with infinitesimal initialization, as one can start GLRL with much larger initialization, while still maintaining high precision.
mig JW... WWeltti
10
rank
10
10-
10-5
10
10-3
10"2
10
[Wezt011r
Figure 4: Using ev (denoted by "rank 1") as initialization makes GD much closer to GLRL compared using random initialization (denoted by "rank d'"), where i is the top eigenvector of (O). We take fixed reference matrix on the trajectory of GLRL with constant norm and plot the distance of GD with each initialization to it respectively.
L-2
L-2
C-3
Lw4
15
10
-25
22-48
15-1
-2
-3
-150
-125
-12
-14
-15
Controou Time
360
Condroous Time
Continuus Teme
164
Condrueu Time
163
Figure 5: Deep matrix factorization encourages GF to find low rank solutions at a much practical initialization scale, e.g. 10-3 3, Here the ground truth is rank-3, For each setting, we run different random seeds. The solid curves are the mean and the shaded area indicates one standard deviation. We observe that performance shaded area with initialization scale 10-? is large, as the sudden decrement of loss occurs at quite different continuous times for different random seeds in this case.
GD quite robust -
initialization. Note that for L 2, the
E.5 BENEFIT OF DEPTH: POLYNOMIAL VS EXPONENTIAL DEPENDENCE ON INITIALIZATION
To verify the our theory in Section 6, we run gradient descent with different depth and initialization. The results shown in Figure 5. We can that the initialization becomes smaller, the final solution gets closer to the ground truth. However, a depth-2 model requires exponentially small initialization, while deeper models require polynomial small initialization, though it takes much longer to converge.
F THE MARGINAL VALUE OF BEING DEEPER
Theorem F.1 shows that the end-to-end dynamics (17) converges point-wise while L + do the product of learning rate and depth, T,L, is fixed as constant. Interestingly, (17) also allows to simulate the dynamics of W(t) for all depths L while the computation time is independent of In Figure
compare the effect of depth while fixing the initialization and nLL We deeper models converge faster. The difference between = 1,2, and 4 is large, while difference among T. > 16 is marginal.
that
18

---

Published as a conference paper at ICLR 2021
Towards infinite depth
1.0
0.8
0.6
1-16
6664
0.2
-112
250
500
750
1000
Figure 6: The marginal value of being deeper. The trajectory of GD converges when depth goes to infinity. Solid (dotted) curves correspond to test (train) loss. The r-axis stands for the normalized continuous time (multiplied by L).
Theorem E.1. Suppose W = ÜΣVT is the SVD decomposition of W, where dia.( oa). The dynamics of L-layer linear net is the following, denotes the entry-wise multiplication:
dW
- LÜ (( VUTT((()))))) k(1) V..
(17)
dt
where K(L)) = 2-24
k-()) bj
2/1 for i
Lo, 21 Log
Proof. We start from (11):
dW
Σ (W
dt
1=0
Σ
ÚS
-Ū
L Σ
( V.
Note that Σ is diagonal, so
ΣΦ ((
27-1111 = ((WW)))HH!)
where H
2 aj Therefore, 0;
21-1-11)
Σ Σ W 201--111 L- 1--1 1=0
1-1
L
V)(WVV) H H
-Ū ((
where 1100=1 -L- 1-1 (!),, Hence,
dW
dt = - LÜ (0 ((VT)()))))))) K V.
The entries of (L)) can be directly calculated by
R(L) = - 1j
1-1
211-1-1)
0 2-2/1
i
a 0j
-
i
1=0
Lof Log
Corollary F22 As L - xc, (LL) converges to K*, where K = 07 K;;
-
for +
lno
19

---

Published as a conference paper at ICLR 2021
Experiment details. We follow the general setting in Appendix E.1. The ground truth W is different but is generated in the same manner and has the same shape of 20 x 20 and = 0.3 is used for observation generation. We directly apply (17), in which we compute V and U through SVD, to simulate the trajectory together with constant learning rate of 10- for depth L. (()) is sampled from 10-3 x (0, Ta)-
--
G PROOFS FOR DYNAMICAL SYSTEM
In this section, we prove Theorem 5.3 in Section 5.1. In Appendix G.I, we show how to reduce Theorem 5.3 to the case where (() is exactly diagonal matrix, then we prove this diagonal case in Appendix G.2. Finally, in Appendix G.3, discuss how to extend it the case where J (() is non-diagonalizable.
G.1 REDUCTION TO THE DIAGONAL CASE
Theorem G.I. If (0) diag( is diagonal, then the statement in Theorem 5.3 holds.
Proof Theorem 5.3. We show how to prove Theorem 5.3 based on Theorem G.1. Let de g
be the dynamical system in Theorem 5.3. Let (0) VDV-1 be the cigendccomposition, where
V is an invertible matrix and D diag(A1. (fr.......... ........ (aa) Now we define the following new dynamics by changing the basis:
((t) 0-)
Then d
g() for g()) = V (VO). and the associated Jacobian matrix is f(Ø)
V, and thus J(0) = diag ( .a))
Now we apply Theorem G.1 to (t). Then (t) = V-12.(1) converges to the limit a(t)
lim 2, (t). This shows that the limit (t)) 2 exists in Theorem 5.3. We can also verify that
(t) is solution of (6).
Given 8., converging to 0 with positive alignment with ūn as + O, we can define 8_, V- 6
then 8, converges to with positive alignment with e1, where en is the first vector the standard basis and is also the top eigenvector (O). Therefore, for every E (-o0, +oo), there is constant
C> 0 such that
| 1 (5,l+
1 1 (6,, )
2(1)
+ log P4
SC 1 11
(18)
for every sufficiently small a. As V are invertible, this directly implies (7).
G.2 PROOF FOR THE DIAGONAL CASE
Now only need prove Theorem G.1. Let c1,...; Ca be the standard basis. Then ú₁ é e1 in this diagonal case. We only use ej to stand for ú and on in the rest of our analysis.
Let R > Since g()) is C² -mmsthhh, there exists 3 such that
[J(0) ( h)ll2 < B///122
(19)
for all [|0||, |0 h/12 - R. Then the following can be proved by integration:
g( + h) g(0) = (L. J(O + {h)dE) h,
(20)
(0 h) (0) J(0)hll2 S B|
(21)
By (21), we also have
(l)(0) J (00)
(l ( J(0)0122 3100
(22)
20

---

Published as a conference paper at ICLR 2021
Let K = B/p1. We assume WLOG that R S 1/k. Let F(x) log log(1 1 + kr). It is easy to see that (z) xt*== and F(z) is an increasing function with range (-o0, log(1/))) We use (y) to denote the inverse function of F(z). Define (r) b. (F(r) P(a))
log - log 1ter 1+ka
Our proof only relies on the following properties of J(O) (besides that μú, e1 are the top eigenvalue and eigenvector of (O)):
Lemma G.2. For J (0) = diag(āi, ................................ (a)), we have
1. For any h E Rd, h T J(O) < ju 11111112:
2. For any 2 0, ||lesli0) c elei e 1|2 = elizt.
Proof. For Item 1, T J(O)h = Em fu I in h- For Item 2, ||e cûr cñiteee [diag(O, east e ||| ePee.
Lemma G.3. For (t) c t) with |10u 2| I a and t S (r)),,
1 + kr
(0 - + ka
a ei <
Proof. By (22) and Lemma G.2, we have 1 ((()))(((())) & (0(1), ((O)(()) + 8100(11 - (1)) + (10( df
This implies dilercil de < (1 (()) + x1000())) Since Fx) スサッz. we further have
F( (()(())))) S j..
di
So F(()(())22) S F(a) + jat. By definition of (r), we then know that [[0(t) l2 S for all
t t To (r). (r). So
log [0))) - F( (())()))))) + log(1 + Kr) s F(a) + +pt+ + +
Expending F(a:) proves the lemma.
Lemma G.4. For (t) = (00. t) with |0ull2 I a and t v (r),,, we have
(t) 10) 0(r²).
Proof. Let Ō(1) e0 0g. Then we have 1 (0()) 0(1)1 < (9(0()) - ((O))(()) 0(1)
dl.
(g()(t)) J(O)@(t), 0(t) (0(t) O(t) (( - ((t))
< (0()) - ((O))(1)2 10(1) 0(1)12 + A (()) 0()
where the last inequality is due Lemma G.2. By (22) and Lemma G.3, we have
2
1 Kr
(g())t)) - ((O) 31 (1) - 3
I + ka a
2 20st + ir ((t) - (()) By Grönwall's inequality,
So we have ( - 0t)]l2 s 3 Htta a
||((t) - 0(t)ll2 - 6-¹ B
1 (1+tr kT
2
2017 (
a
1 I+raa ka
Evaluating the integral gives
1 Rr 1 ka
2
Ciit -1
S / kr
a eiit) 2 S kr?
(0()) () - 0())2 8
@ut
1 ka
which proves the lemma.
21

---

Published as a conference paper at ICLR 2021
Lemma G.5. Ler ((t) ((0u, 0tt) = =6(0u. t). If max 110ll2 a, fort S (r))).
[10(1) - s cBitter 100 -00122.
Proof. For t $ Ta (r(r): (r). . by (20),
2 dt (t) ((t)l = (((())) g(((()), 0(t) - -(t))
(0(t) T(t)) (f," ](0 (0(1) - Q()))
where (g(() = (Q(t) + (1 - ()) By Lemma G.3, max [0()) & itna a efiat for all / < (r)).. So [10{(1)122 - 1 ar efit. Combining these with (19) and Lemma G.2, we have
h. ((O h J(0) + h (J)O J(O)) S (m + B-
1+
efiit) ||hl|
1 kaa
for all h E Rd. Thus, (1(()) - 0(1)l2 S (ir + Lter Itraa
a editt) 10(1)) - 0(1)l2. This implies
log
(0(() 0(1)l2
[Mmn +
[ir
1 kr
a odir) dr
10(0) - 0(0)
1 ka
1 Kr aie
jul
1 ka
$ Sht + nr
Therefore, [0((t) - ( S eittt 10(00 0(0)ll2
Lemma G.6. For every E (-o0, x(t) exists and (t) converges to z(t) in the following rate:
[1= 2(1)112 = O(a), where O hides constants depending on g and t.
Proof. We prove the lemma in the cases of t E (-00, F(R)/pll and t> F(R)/A1 respectively.
Case Fix E (-o0, (R))/n)) Let the unique number such that Itkā a (i.e., F(ā) = l)) Let a' be an arbitrary number less than a. Let to == in log o Then to = 1
in (F(ā) - ao) s (a). By Lemma G.4, we have
| (a'e1, el, (0) - 0e1ll2 (a'e),, (o) - 20 d'el
= O(a))
Let::= F- < R. Then /. + بي log _ = Ta(r) if <T.
By Lemma G.3, || (a'e e1, to)
12 S Also, ||aeil12 ItRā S a. By Lemma G.5,
1
2>1{ Ān (aei,,+ log 1
|| (t) za (t)ll2
④ [d'e,,t+ log a²
Φ (ac,,t+ log
11
Φ (ola'e..0)))++
1
1 -
1
log
a
2
s O cillt + log t)tter)
0
For small enough, have ā O(a), for any a' (0,
1|z. 2, (t)ll, Oaa).
This implics that (t) satisfies Cauchy's 's criterion for every t, and thus the limit =(t) exists for t & F(R)/jn The convergence rate be deduced by taking limits for a' - on both sides.
22

---

Published as a conference paper at ICLR 2021
Case 2. Fort = F(R)/ + with > 0, e(0, is locally Lipschitz with respect to 6. So
|zx(() (0)(1) (F()))((((())))))) (PE.))
= =((a),
which proves the lemma for 1> F(R)/
Proof for Theorem G.I. The existence of z(t) == lima- (t) = -lim o (ael, + 1 in log !
has already been proved in Lemma G.6, where we show [|za() - 2(1) = 0(a).
By the continuity of o( ,)) for every t R. we have
1 2) o f11 a
1 P1
) = (z(().t)
xtt)
lim @ a01 t a-+0
log
lim Φ a-
adi, log
Now is only left to prove (7), WLOG we can assume that | ll is decreasing and //8 I || 2 S a
(otherwise we can do reparameterizationn). Then our goal becomes proving
(1a(l)) =(1]l22 O ( (aFT)T)
(23)
where (t) = o (8. t + I log ( ) We prove (23) in the cases of t E (-00, F(t)/a) and t> F(R)/m4 respectively.
Case 1. Fix (-00, (F(R) + log p/ Let à a ब Let a == P(ās)
Let
I-ka:
to 1/ (F((1) - log a) s T11bal12 (ā1). At time to. by Lemma G.2 we have
(2oJ(0) - -ii [ || clizto e #2 (P(())))
01
PT
(24)
Let go - e1). By Definition 5.2, there exists g such that ga 2 g for all sufficiently small a. Then we have
(8,, (n) a go 112 = | (8):10) t 8n
+ 1
- gas cirteeeee [āltter))ee 8,
= =(aî) +
P1 110,112
= =O + affa/i
Palia Th a 21-22/A1)
= O(a)).
Letr == F ( + log %oo
S R. Then t +
1 log a19a
I Ta(r) i r. By Lemma G.3,
(5 (0),t âr. Also, |1a1q.e1l1 Sa Itrr] I âr. By Lemma G.5,
1
1 - log
1 _
[1) Za, (0)l2 S Φ ④ (8ar 40, ,
log
&b (11%, 1+
aggo
14
af ci (++a) log ay
tar
0
O(a)).
Combining this with the convergence rate for Zo, (t), we have
1|0 (t) - (t)]l2 - (t. Za, (t)ll2 + || (t) (f))l2 = O(a)).
Case 2. For 1 = (F(R + log 4) / + - with - > 0, $(0, 7) is locally Lipschitz with respect to 0. So
(1) - =(1)l22 - 11 log - + logg)/ūr)lll)
(<=(((()) logg)/
=0(a1),
which proves (23) for 1. > (F(R) + loggg//n.
23

---

Published as a conference paper at ICLR 2021
G.3 EXTENSION TO NON-DIAGONALIZABLE CASE
The proof in Appendix G.2 can be generalized to the case where JO). Now we state the theorem formally and sketch the proof idea. We use the notations g <(O0. 1), (() in Section 5.1, but we do not assume that (0) is diagonalizable. Instead, we use A1, (2,,..... ,42,...,/d Ai E C to denote the eigenvalues of JO), repeated according to algebraic multiplicity, We sort the eigenvalues in the descending order of the real part of each eigenvalue, i.c., R(Ar) R(ū2) 2 ... 2 R(āa), where R(2) stands for the real part of a complex number E We call the eigenvalue with the largest real
part the top eigenvalue.
Theorem G.7. Assume that is a critical point and the following regularity conditions hold:
1. g()) is -mmooohh;
2. d(0s.) 1) exists for all Og and
3. The top eigenvalue of (() is unique and is a positive real number, i.e.,
in max Max(R((ja);.00
Let 01, ún be the left and right eigenvectors associated with fb1, satisfying ūj 01 = Let (t) =
1 0(a0), jii log 2) for every a O, then Vt R. z(t) lim za(() exists and z(t) = ((=()),t).
o converges to O with positive alignment with ún a-1 there is constant C such that for every sufficiently small a,
0, then for any t RR and for any
| (dar
M2 log (....)) 2(0|| SC 116
(25)
where 7 ji1 ((()) the eigenvalue gap.
Proof Sketch. Define the following two types of matrices. For 2 1,a, E R, we define
a
8
J(()
a
E R
0,8
=
a
For b, E IR, we define
C 58
C 81
C
81
(r)
E R 2r22r
0.6, =
C
81
C
where C C= [b] 22
By linear algebra, the real matrix J() can be written in the real Jordan normal form, i.c., J(0) = ddiag(J[).....
V- where V E Bdxd is an invertible matrix, and each Jij is real Jordan
block. Recall that there are two types of real Jordan blocks, f(() or J The former one is associated with a real eigenvalue a, and the latter one is associated with pair of complex eigenvalues + bi. The sum of sizes of all Jordan blocks corresponding multiplicity. The sum of sizes all Jordan blocks corresponding to a pair of complex eigenvalues + bi is two times the algebraic multiplicity of bi bi (note that + bi have the same multiplicity).
real eigenvalue is its algebraic
It is easy to that J DJ D for D diag( 1 ...... 11......, 8) Rr and Jab.5
(r(()) (r) D-1 for D "a"ag(0",'"" 5""88" 18-1,8 ,..., 5. a.b.1
2r2xx This means for every d >
24

---

elie for Published as a conference paper at ICLR 2021
there exists V, such that J(0) VaJaV; where Js diag(J811) . Jimm)) J&y J.
[b == Juh or Japl J if Jbj == J a.b.1. Since the top eigenvalue of (() is positive and unique, ji corresponds to only one block [in] E Rix!, WLOG we let J1 = [it,, and thus Ja[1] [-
We only need to select a parameter 8 > 0 and prove the theorem in the case of J(0) Js since we can change the basis in a similar way as we have done in Appendix G.I. By scrutinizing the proof for Theorem G.I, we can find that we only need to reprove Lemma G.2. However, Lemma G.2 may not be correct since (() is not diagonal anymore. Instead, we prove the following:
If (0, R), then h Joh & 11llb1l for all R4;
2. For any Nl E (R(()), (n), if E (0, 132 R(jz)), then ||e.s. ehrl ej ll all 2 0.
S
Proof for Item 1. Let K. be the set of pairs (k1. k2) such that Lı # K2 and the entry of Js at the ky-th row and the k22thh column is non-zero. Then we have
J
d
h J,h hT
h
Σ
Iky hug
2
kml
(2)
h2 +
hkz
2
(k1 E2)
Note that R(4a)) < R(22) for 2 2. Also note that there is no pair in has h = 1 or 1/ = 1, and for every h: there at most pairs in I. has kn l: lo2 k. Combining all these together gives
h Jgh S hn (R((2)) + +6)
h
< p1 12
k==
which proves Item 1.
Proof for Item 2. Since Js is block diagonal, only need prove that || " [2 S elit for every j 2 2. If Jay. = ((() = aI + 8N, where N is the nilpotent matrix, then
ااال = + = 6 = eat at. .IN
where the second equality uses the fact that I and N are commutable. So we have
Je ll 5CN 5LN c (a(00)
If Jöis] ( D 8N2 where D C,,gg C) and N is the nilpotent matrix, then J = e DD+8tN2 ID 8tN2
where the second equality uses the fact that and N are commutable. Note that elC
eat cos(ht) - -sin(be) which implies | 1|2 ||e || ạtt So we have sin(be) cos(bi)
Je ||2 S |D l2 -le 5L ||2 = at 5tt St No S (a+d))
Since 8 E (0. F22 R(p))). know that 8 < p22 which completes the proof.
Proof for fixed 8. Since Item I continues to hold for E (0,7), Lemmas G.3 to G.6 also hold. This proves that z(t) exists and satisfies (6).
remains to prove (25) for any > 0. Let 5 E (0,5) N4 = μ - - Phg - R(ū)). By Item 2, we have || ea e,ee || < e for all t 2 0. By scrutinizing the proof for Theorem G.1, find that the only place we use Item 2 in Lemma G.2
5) be a number such that Ar A c. Fix
4/
25

---

Published as a conference paper at ICLR 2021
is in (24). For proving (25), repeat the proof while replacing all the occurrences of juz by 1242 Then we know that for every t E IR, there a constant >> 0 such that
Vo ' o (Sa.t
t Ai log To..uu)
V8 x(t)
S S. VVV
for every sufficiently small By definition of of have 11V ||a2- < 1 for sufficiently small a. Then we have
5/
7
Since o. 0 as - 0.
1 log (o.lur)) -=00) - 1V8l2 V 1 |100 60,, / + in
(on L + I log (o.. V/ -=/00
Volla C 11V 8a l1 11
s CC Vol2
| 1
11
7
116 12
Absorbing [|V] IV, 11 into C proves (25).
H EIGENVALUES OF JACOBIANS AND HESSIANS
In this section analyze the eigenvalues of the Jacobian (W) at critical points of (2).
For notation simplicity, we write sz(A) == A + A T to denote the symmetric matrix produced by adding up A and its transpose, and write ac A, { two matrices A, B. Then (W) can be written as g (W) == - ac -cC (WW)), W)
B} AB + BA denote the anticommutator of
Let Uo Rdxr be stationary point of the function L Raxr + R, ((U) fUU i.e.,
(LU, VVU Uo 0. By Lemma C.I, this implies
V((W)) Wo =0
(26)
for Wo = UOU and thus Wo is a critical point of (2).
For real-valued or vector-valued function F(0), we use (F 62] to denote the first- and second-orde directional derivatives of F() at O.
Let X be linear space, which can be gaxd or _gxr, For function F; X + X, we use DF(() to denote the directional derivative of F at 0, represented by the linear operator
F(O + F(O)
DF(O) X X,A A (F
-im [-+
We also write DF A (DF(0) A2)
For a function F; + I, we use ( = D(VF(()) to denote the second directional derivative of F at i.e., D²F A D(VF A), D2 A, A2] (())(O))(A 1. A2).
Define J(W): := Dg( (). By simple calculus, we can compute the formula for J(W)):
J(W.) | -ac ac(VV A ac(D) Wo).
J(W))A,, Ao] (V.(W.)) sz( "
sw,
where A, A., Ag E Edxd
We can also compute the formula for D²
D²C(U))[A] = Vf(W)) + f (AU
DPC(U)) A, Ag] (Z + D2 )
(, (2. 1))
where A,A,, A1,46 Rdxr.
26

---

Published as a conference paper at ICLR 2021
H.1 EIGENVALUES AT THE ORIGIN
The eigenvalues of J(0) is given in Lemma 5.4. Now we provide the proof.
Proof for Lemma 5.4. For Wo = O, we have
J(O)A)] V/(0)A -V/00))AV(()
[( A2] ( (x)00)ss(AAA)))
is easy to see from the second equation that (0) symmetric.
Let -V) = E 1 be the eigendecomposition of the symmetric matrix - -Vf(0).
Then we have
](O)AA
=
Σ
Mi ( A Au())
1=1
Σ
Mi (1 uull uis unn "is Au u11s)
(ms + m3 ) Aunn uil
(ps + (n) ( (111111111)) unn
which proves (8).
For A = (1) + (1)) we have
J(0) (Mt + My 1 + (Mz + (y) " (wz + mz)
unn TT + " u [(]] is an eigenvector of JO) associated with eigenvalue μ + Mj- Note that [uip) + un | ..j [d] spans all the symmetric matrices, these all the eigenvectors in the space of symmetric matrices.
So
For every antisymmetric matrix A (i.e., A = A ), we have
J(O)A J (O) A J (O)]
and every antisymmetric matrix is an eigenvector associated with eigenvalue Since every matrix can be expressed as the sum of a symmetric matrix and an antisymmetric matrix, we have found all the eigenvalues.
So J(0) [
H.2 EIGENVALUES AT RECOND-ORDED STATIONARY POINTS
Now we study the eigenvalues of ((W)) when Uo is second-order stationary point of L( i.e.. VL(U)) D2 D2 A A 2 0 for all A BRdx._ We further assume that Un is full-rank, i.e.. rank(Un) This condition is meet if W, U²U? is local minimizer of f(-) in S but not minimizer in S
Lemma H.1. For r < d, if Un E Rdxr is second-orter stationary point of L( then either rank(Un) = rarkkaaW = r, or Wo is a minimizer of f(.) in St, where Wo = U,U,
Proof. Assume to the contrary that Up has rank and Wo is minimizer of f(.) in S)- The former one implies that there exists a unit vector q E Rr such that Unq = 0, and the latter one implies that there exists Red such that (((W)) < 0 by Lemma C.2.
27

---

Published as a conference paper at ICLR 2021
Let A uq
Then we have
D'L(UO))A, A = (V)(Wo), vo > D2 (Wo(((oss((((a))))
(VS(W)), vo
D² D²
2
= (V)(WW), vo
So D2C(UU)) A] < which leads contradiction.
By (26), the symmetric matrices (W)) and Wo commute, so they can be simultaneously diagonalizable. Since (26) also implies that they have different column spans, we can have the following diagonalization:
Σ mwa ==1
Wo
Σ
(27)
(=d-
First prove the following lemma the eigenvalues and eigenvectors of the linear operator D2 (U)): Lemma H.2. For every E =ddxd if
U + AUU = 0
(28)
then A is an eigenvector of the linear operator -DD -DVL([V lRdxr + RRd associated with eigenvalue O. Moreover, the solutions of (28) spans linear space of dimension r(r-1)
Proof. Suppose U + AUT = 0. Then have U
-A and thus A
-U, AUD where U, is the pseudoinverse of the full-rank matrix Un. This implies that there is matrix Rexr, such that A R. Then we have
[ (.WW)), D2 (W AU - (V.(W)))U) D2 (Wo
0.
Replacing with R in (28) gives Un(R UU = 0. which is equivalent to R - since Uo is full-rank. Since the dimension of r x antisymmetric matrices is r(r-1) the span spanned by the solutions of (28) also has dimension r(r-1)
2
Definition H.3 (Figendecompositionn of DD2 ((U)), Let
rd
D² = Σ E E A) E,
be the eigendecomposition of the symmetric linear operator - D2 DD : Rd - Rdxr, where Erd are eigenvalues, E,,..., Erd E RRdxr are eigenvectors satisfying (Ep, Eg) = 8pg- We enforce Ep to be and E, to be solution of (28) for every rd r(r-1) < $ rd.
Lemma H.4. Let A E D be a matrix. If (ūn.... ūx} is a set of linearly independent left eigenvectors associated with eigenvalues )i,..., Åx and (ū1....,ūp-K) } is set of linearly independent right eigenvectors associated with eigenvalues ÅI,..., AD..,, k. and (ū,, ú2) = 0 for all "h....,p_K.. k are all the eigenvalues of A.
1 15is K, S D - K, then
Proof. Let Ū == (ū)..... T E KxD and V = (i....., kD-k) DD--K). Then both U and V are full-rank. Let Ü+ = Ú (TÚÚÚ V+ (V Vi-1V be the pseudoinverses of U and V.
28

---

Published as a conference paper at ICLR 2021
Now define
Ü V+
p:
Q: (U+ v].
Then have
ÚỨ+ ÚV
PQ
V+O+ V+V
Note that Ü0+ K. ÚV = 0, V+0+ (VTV)-((VV (007))=00000000 -l-k-
So PQ ID, equivalently Q = P Then we have
P-IPP = diag(A (1...... )x)
x)
0
diag (A..................
where can be any K x (D - K) matrix. Since AP is upper-triangular, we know that P-1 AP has eigenvalues ÅI,..., ......,Ke AK A.,.... ÄD-K. and so does A.
Theorem H.5. The eigenvalues of J (W)) can be fully classified into the following 3 rypes:
1. pe + Pj an eigenvalue for every S S S d r, and Üig =v.0] t is associated left eigenvector.
2. Ep is an eigenvalue for every E P S rd associated right eigenvector.
r(r=1) 2 and Vp = E,UD + U. is an
3. 0 is an eigenvalue, and any antisymmetric matrix is associated right eigenvector, which spans a linear space of dimension d(d-1)
Proof of Theorem H.S. We first prove each item respectively, and then prove that these all the cigenvalues J (W)).
Proof for Item 1. For Un = 1isa + U., it is easy to check:
(c(-))(Wo). U,)) (A: 2,)
Ü, Wo 0 Woll
So we have
J(Wo)A, = (Ax + X1) (A. (A. -D (A, As) ( (i)
which shows that Ü.j is left eigenvector associated with eigenvalue + Ayz
Proof for Item 2. By definition of eigenvector, we have -D2 D22 = Ey so
E, (Wo,) D2 DD ((Wo))UOE) E,U,
Right hight-nultillying both sides by Up we get
E, = --V - D2 (')
(V,) + ) (WW))
=-V/(W)VV, (
where the second equality uses the fact that v.(W.) - since Un is critical point. Taking both sides into sz(-) gives
En sz( Vf((W)) - sz(D2 (V))
which proves that V, is right eigenvector associated with eigenvalue Ep-
29

---

Published as a conference paper at ICLR 2021
Proof for Item 3. Since (W() is symmetric, 9 (WW is also symmetric. For any A -
(Wo) | J(W))| J (W))
So J[ and A is an eigenvector associated with eigenvalue O.
No other eigenvalues. Let Sa be the space of symmetric matrices and Aa be the space of anti- symmetric matrices. easy to see that Sy and An are orthogonal to each other, and S and Aa are invariant subspaces of J (W,) [.). Let h Su + Sa- A + J(W)) [A] be the linear operator J [ restricted on symmetric matrices. We only need to prove that is diagonalizable.
It is easy to see that (Üt) are linearly independent to each other and thus spans a subspace of S with dimension (d-r)(d-r+1) We also prove that (Vp) spans subspace of Sa with dimension rd- r(r=1) by contradiction. Assume to the contrary that there exists scalars ap for 1 S S rd rrr - 1)/2, not all zero, such that Ep=1 End-r(r- 1)/2 ap Vp O. Then Σp=1 Erd-r(r-1)) 1)/2 Ep is a solution
of (28). However, this suggests that pp=1 rdd-((r11)/ a Ep lies the span of {Ep)rd- 1) which contradicts to the linear independence of ISpsed.
Note that
(d r) - + + rd r(r 1) -0r-11
d(d+1)
dii
2
2
Also note that Üiz. V,,) = 20 U u, 2u] E 0; = 0. By Lemma H.4, Items I and give all the eigenvalues of h, and thus Items 1, 2, 3 give all the eigenvalues of (W)).
I PROOFS FOR THE DEPTH-2 CASE
1.1 PROOF FOR THEOREM 5.6
Proof for Theorem 5.6. Since (t) always symmetric, it suffices to study the dynamics of the lower triangle of (l). For any symmetric matrix W E Sa, let veCLT(WW E
A(d+1)
R
be the vector
consisting of the d(d+1) entries of W in the lower triangle, permuted according to some fixed order.
Let g (W) be the function defined in (2), which always maps symmetric matrices to symmetric matrices. Let ğ IR 41a+12 + R d(d+1)
be the function such that g(vecLT(W) = vecrr (g))) for
any W E S.. For (t) evolving with (2), we view veerT (W (f)) as a dynamical system.
vecrT (Rrer(Wii) (t)) g(vecLr (W
dt
By Lemma 5.4, the spaces of symmetric matrices E and antisymmetric matrices A. are invariant subspaces of (O), and { (ps + PJ; "1[]] [ + " isigisd is the set of all the eigenvalues and eigenvectors in the invariant subspace Sy. Thus, ã1 = 2/11 and já2 = μn + lz are the largest and second largest eigenvalues of the Jacobian of ğ(-) at vecLT(W) 0, and ū = t1 u u are the corresponding left and right eigenvectors of the top eigenvalue. Then it is easy to translate Theorem 5.3 to Theorem 5.6.
1.2
PROOF FOR THEOREM 5.8
The proof for Theorem 5.8 relies on the following Lemma on the gradient flow around a local minimizer:
Lemma L.1 If 0 is a local minimizer of ((0) and for all ||e 0|1 I r, satisfies Lojasiewicz inequality:
[V((0) (C(0) -(0))
().,t) t) converges to a point 0x near 0 if 0g is for some μ E [1/2, 1), then the gradient flow ((t) = ((0,,
close enough O, and the distance can be bounded by 100 O|| 0 0 0 2(1-p)
30

---

Published as a conference paper at ICLR 2021
Proof. For every t 2 0f [[((t) = Sr,
di (c()()))<(0)) = (1 14) (E((())) [(0)) " (VL, d0
dp
d0
= -(1 - 1D (C(O())) - C())) - ||
dt
d0
S - (1 uee
dl
Therefore, [1((t) 0oll2 - a dt - [1-p1c ((0)) ) 0(110 012 0 (111))) If we choose
1
(t(()) 0 small enough, then (t0(t) 0|1 S [1((t) (0l()) + 110 0|1 O 0 2 (
de and thus Jo dt
2 df is convergent and finite. This implies that 00 == + ( 00 0|12 0 (
exists and
Proof Theorem 5.8. Since (F(() E Sī satisfies (2), there exists ull) E Rd such that a(t)(tt) = (() and u(() satisfies (I), i.e., de 2 [um ). If (F) does not diverge infinity, then does utt). This implies that there is limit point u of the set (u(t) : [ 03.
du VL(uu, where L : Rd + R,
Let {u L(u)= 2 [(u)). Since L(u(t)) is non-increasing, have u(t) E U for all t. Note that ū is a local minimizer of ((-) in U. By analyticity of f(- .). Lojasiewicz inequality holds for f(-) around (łojasiewicz, 1965). Applying Lemma I.1 for L restricted on U,
know that if u(to) is sufficiently close to ú, the remaining length of the trajectory of u(f) (f 2 to) is finite and thus lim utf) exists. As is a limit point, this limit can only be ū. Therefore. W to ()(()= au exists.
If W, is minimizer of S(.). O,.0.... 0) Rdxd is also a minimizer of L Rdxd R. U + f(UU By analyticity of f(( Lojasiewicz inequality holds for L(.) around U. For every 0, we can always find a time te such that [ta u|l2 S e/2. On the other hand, by Theorem 5.6, there exists number a such that for every ac.
1
|lo(W., + -
E//2, where T(W) = 2/11
log
(W, uuu))
Combining these together have [ W.. T(W.) +t) W1 S.
is easy to construct a factorization @(W.. ((W..T(W.)) + +z) :=): U.. such that || |Ua, - Ull2 = (c)), e.g., we can find an arbitrary factorization and then right-multiply an orthogonal matrix so that the row vector with the largest norm aligns with the direction of ú. Applying Lemma I.I, we know that gradient flow starting with U... converges to point that is only (1)2(1))) far from ú. So we have
lim <+o
+ W
= (()2(())))
2
Taking 6 + 0 complete the proof.
1.3 PROOF FOR THEOREM 5.11
Theorem 1.2. Let W be a critical point of (2) satisfying that W a local minimizer of J(.) in St.3r for some but not a minimizer in S Let (WW Di_ pau.' be the eigendecomposition of /WW p4 P2, the following limit exists and is solution of (2).
w (t) = lim & c-
W + coree
log +
241
For (Wa) St. if there exists time Ta for every that di W.. Ta) converges to W with positive alignment with the top principal component lane as + 0. then Vt E R.
lim ④ Wa,To + 2/11 o0
log
(Ø(Wa, Ta), (alla +1 = ((()).
31

---

Published as a conference paper at ICLR 2021
Moreover, there exists constant C' >> 0 such that
W.. Ta + 2 log (o. (ale +1) - wc(1)
SCllo T.)ll
for every sufficiently small a, where 5 == 2p11 max//1 + 12, 0}.
Proof. Following Appendix I.I, we view vecLT as a dynamical system.
vecrT (W - ( (W)))).
Let W- = UU' be a factorization of W. where U E Raxr, Since W is a local minimizer of S(.) in st. U is also local minimizer of L: Rdxrr - R, U (IUU Since W is not minimizer of f(-) in S by Lemma H.1, U is full-rank. By Theorem H.5, (WW has eigenvalues M4 + +1 Sps O. By a similar argument in Appendix I.I, the Jacobian of g at veeLr (W))) has eigenvalues μ4 + Sp-
Since U is local minimizer, &p S 0 for all p. If fn > 12, then 2p1 is the unique largest eigenvalue, and Theorem H.5 shows that vecLr is a left eigenvector associated with 2/11. The eigenvalue gap 7 2 max + μ2; max S p S rd - }} 2 2p1 max(e1 + 42, 0}.
by (27). If o(Wa, Ta) converges to W as a + 0, then it has positive alignment with 0 o iff (WW..Ta).ros
Also note that (o(W... Ta) - W. "
(ø (Wa, Ta), ) because [ )T
lim infa I (WW,,, W 0. Then it is easy translate Theorem 5.3 to Theorem I.2.
1.4 GRADIENT FLOW ONLY FINDS MINIMIZERS (PROOF FOR THEOREM 5.10)
The proof for Theorem 5.10 based on the following two theorems from the literature.
Theorem 1.3 (Theorem 3.1 Du and Lee 2018). Let f idddd RR be C² convex functionn Then L: Rdxk + R, L(U) = f(UU ), 2 d satisfies that (1). Every local minimizer of L is also global minimizer; (2). All saddles are strict. Here saddles denote those stationary points whose hessian are not positive semi-definite (thus including local maximizers).
Theorem I.4 (Theorem 2 in Lee et al. 2017). Let g be a C2 mapping from X. - X and det (Dg(z)) + for all x E X. Then the set of initial points that converge to an unstable fixed point has measure zero. (fzo lim g" (xo) A4)) = 0, where Ag = {x g(x)
max; (A.(D(( > 1}.
Theorem I,5 (GF only finds minimizers, a continuous analog of Theorem 1.4). Let f Rd - Red be C smooth function, and Φ Idd x TR + Bd be the solution of the following differential equation,
dø(x, t) = f(b(,, ()), $(x,0) 0) = Vx E ERRR dt
Then the set of initial points that converge to a unstable critical point has measure zero, where Uj = (ar f(x) = 0, (Df(()))))) > 0) and
I xo lim a(Fo, 1) E =(z})
Df is the Jacobian matrix of f.
Proof of Theorem 1.5. By Theorem in Section 2.3, Perko (2013), we know o(.,) -) is -mmsoooth for both x, L. We let (xx d(x, 1), then we know g -xx) = Φ0xx-111 and both g, g are C*-smooth. Note that Dg (x) is the inverse matrix of (z So both of the two matrices are invertible. Thus
we can apply Theorem 1.4 and we know (( liigg-oo (x0) E A11) =
Note that if lime-so 6(x ()) exists, then limg- (xz) lim (αx, l). It remains to show that UG Az. For f(xo) O, we have (( 1) = æ0 and thus g (mr)) Bg. Now it suffices to prove
Though the original theorem is proven for convex functions form Σn_ UU,UU T Je. y.). where {(-,) is e convex for its first variable. By scrutinizing their proof, can see the assumption can be relaxed to f is C² convex.
32

---

Published as a conference paper at ICLR 2021
that A1 (Dg( 1. For every t E [], by Corollary of Theorem 1 in Section 2.3, Perko (2013),
we have 0 86 DoD((a a. t) = t) t), Vz,t. Thus,
0 () = ( Do) = (6(e0 σt
Solving this ODE gives D0( = Do(æ, =)= ( Do(a, 0) eff(o)), where the last equality due to (x 0) I, Vz. Combining this with A (Df(zo) 0, we have A1 (Dg((z)) 1.
Thus we have Uł == {ao : f(æo) = O, (. > 0} C Ag which implies that { oo Φ( 1) [('} S (wo lime 9" (2ro) E An}
Theorem 5.10. Let f Rdxd + BR be a convex C²-smooth function. (I). All stationary points of C: Radxd + R, L(U) 1 f(UUT) are either strict saddles or global minimizers; (2). For any random initialization, GF (1) converges to strict saddles of L(U) with probability 0.
Proof of Theorem 5.10. For (1), by Theorem I.3, we immediately know all the stationary points of C(- are either global minimizers strict saddles. (2) is just direct consequence of Theorem 1.5 by setting f in the above proof to - VL.
J EQUIVALENCE BETWEEN GF AND GLRL
In this section we elaborate on the theoretical evidence that GF and GLRL are equivalent generically, including the case where GLRL does not end in the first phase. The word "generically" used when we want to assume one of the following regularity conditions:
1. We want to assume that GF converges to local minimizer (i.c., GF does not get stuck on saddle points);
2. We want to assume that the top eigenvalue A1 (1-V/ is unique for critical point W
of (2) that is not minimizer of f(-) in s
3. We want to assume that a convergent sequence of PSD matrices W. - W has positive
alignment with vo" for some fixed vector v with (W, ve 0, i.e., for convergent
sequence of PSD matrices W. W. it holds for sure that lim lim inf (W..vo") a-0
a-+ W - WilF vo voT)=
w. w
I.. W 2 0, and we further assume that the inequality is strict generically.
Theorem 1.2 uncovers how GF with infinitesimal initialization generically behaves. Let W o == O. For every r 2 1, -r- is a local minimizer $7 but not a minimizer S then A((V)((,,-i)) r-1) > 0 by Lemma C.2. Generically, the top eigenvalue Ai (IVf((W,-))) should be unique, i.e., Ai(-V (i--)((W.... deduce that the limiting trajectory
Xa(-V5((,- This enables us to apply Theorem I.2 and
1 log +1 6
w-((1= = lim Φ -0
W Wr-1+ u,
2 1))
exists, where u, is the top eigenvector of - (VS(W, --)). This (.)..) is exactly the trajectory of GLRL in phase r as 0.
Note that (-((-) corresponds to trajectory of GF minimizing C(-) in Rexr, which should generi- cally converge local minimizer of L(-) -) in gdxr, This means the limit W,:= lim (()()) should generically be local minimizer of f(-) in st.rr- If W, is further minimizer in St. then A .) < 0 and GLRL exits with W.. ri otherwise GLRL enters phase r + 1.
If GF aligns well with GLRL in the beginning of phase r (defined below), then by Theorem 1.2. as a ++ 0, the minimum distance from GF to (t) converges to 0 for every E R. Therefore, GF can get arbitrarily close to the r-th critical point W, of GLRL, i.c., there exists a suitable choice T that lim Φ (Wa, T(t)) W,. Note that (W, r, u, u,;)) by (27) and thus
33

---

Published as a conference paper at ICLR 2021
lim inf < dW..T W.
Ilo(W. W- Wll u,u, lim inf (o ). ju.u
loo ".. -- 0. Generically, there should
a-0
exist suitable choice of T that ((W. )) not only converges to W, but also has positive alignment with u, u, that is, GF should generically align well with GLRL in the beginning of phase ++1 1.
Definition J.I. We say that GF aligns well with GLRL in the beginning of phase if there exists Te(") for every a > 0 such that @f Wa T converges to W r-1 with positive alignment with u, O.
If the initialization satisfies that W. a converges to 0 with positive alignment with Un as + 0, then GF aligns well with GLRL in the beginning of phase 1, which can be seen by taking T:! 0. Now assume that GF aligns well with GLRL in the beginning of phase 1, then the above argument shows that GF should generically align well with GLRL in the beginning of phase т, GLRL does not exit in phase 1. In the other case, we can solution near the minimizer W,, , of f(-) as oo, and the distance between
similar argument in Theorem 5.8 to show
that GF converges the solution and W r converges to 0 as + O. By this induction we prove that GF with infinitesimal initialization equivalent to GLRL generically.
K PROOFS FOR DEEP MATRIX FACTORIZATION
K.1 PRELIMINARY LEMMAS
Lemma K.1. If W (0) = O. then (tt) ł 0 and rank W (t) rank W (0)) all
Proof. Note that we always find set of balanced (t),) such that (t) Ut(() (t).
d2 = dg _... = d, = rank (t)) and write the dynamics of (() in the space of (U,) Thus it is clear that for all f', rank W (t)) S (ank(W(()) We can apply the same argument for t' and we know rank
rank(W(t)) (t) S. rank W (t)). Thus rank( (t)) is constant over time, and we denote it by k. Since eigenvalues are continuous matrix functions, and Vt, (W(())), i E [A] o Thus they cannot change their signs and it must hold that (()) 2 O.
Lemma K.2. Va, b. P R, if b 0, 1, then -b
< PaP-1
Proof. Let f(x) = P(1 - x) (1 =') Since f'(x) = - - Px < 0 for all x E [0, 1).
f(x) 2 /(0) = 0. Then substituting x by b completes the proof.
Recall we use (F(N) to denote the directional derivative along M of F at N. Lemma K.3. Let : + St M + MP, where P 2 and P Q Then VM, N 2 0.
IDF MI] P PINII-
P-1 |MIl.
where DF(N)(M) = Iiim F(N+IM) F(N) is the directional derivative of along M.
Proof. Let UEUT, where T I and Σ diag(o1, ,.Oa). Note that FUUMU
UF(M)UT for any M Sj. Then we have
F(N + tM) F(N)
lim t-0
t F 1 MU) - F(E)
=lim
(-0
=||DF(JJU" MU
Therefore, it suffices to prove the lemma for the where N is diagonal, i.e., N E.
34

---

Published as a conference paper at ICLR 2021
Assume P= 2. where p, q N and q 2 >>> 0. Define G(N) N Then G(E)² E. Taking p directional derivative on both sides along direction M, we have
Σ E=1
(())) M,
So we have
Maj
[DG
h-1 P
E 0, O)"
Let H(G) G4, With the same argument, we know
9 k- + Σ 0 0
[ = maj
k=1
Note that H((E)) = F(E). By chain rule, we have
That is,
[F](E) = mij
-k=1
Σ
When oj, clearly [DF(E) M liy mij 0, Pm.jo Otherwise, we assume WLOG that o; oj. we multiply a; Jj to both numerator and denominator and we have
of' of 0, oj
D (FFE)) = |ma]
mig Pop-1 s mmm1 P|E
where the first inequality is by Lemma K.2. Thus conclude the proof.
Lemma K.4. For any A, B > 0 and P E R, 1
A P B" F S P P
BlIp max [|A
P-1 |BB1 (1B1)111]
Proof. Since both sides continuous in P and Q is dense in R. it suffices to prove the lemma for E Q. Let == max [|||| | [l1 and (MM) = MP. Define N [0, + St N(t) = 1)A + IB, we have
1. [[N())) 2 p. since 1|11, is convex.
2. (DF(N A]LF = P11N B Alp by Lemma K.3.
Therefore,
- & L dF(
di
dt
(DF(( A]] dt
$ P
B P P-1
which completes the proof.
For locally Lipschitz function f(-), the Clarke subdifferential (Clarke, 1975; 1990; Clarke et al., 2008) of f at any point is the following convex set
a f())
co lim vf(xx) æ + x, f is differentiable at 2
dx
K0000
where denotes the convex hull.
Clarke subdifferential generalize the standard notion of gradients in the sense that, when f is smooth,
8" (())
(z)( Clarke subdifferential satisfies the chain rule:
35

---

Published as a conference paper at ICLR 2021
Theorem K.5 (Theorem 2.3.10, Clarke 1990). Let F R RR be differentiable function and
: R + R Lipschitz around F(). Then ggo F is Lipschitz around a and one has
0 f f()) 0" (F))))))
(
dæ
OF
dæ
Let Am Su + R, M + (m(M) be the m-th largest eigenvalue symmetric matrix M. The following theorem gives the Clarke's subdifferentials of the cigenvalue:
Theorem K.6 (Theorem 5.3, Hiriart- Urruty and Lewis 1999). The Clarke subdifferential of the eigenvalue function Am given below, where co denotes the convex hull:
8 Am (M) co(ve) :M Am (M)U, |ll12 1}.
K.2
PROOF LEMMA 6.1
The equation to be proved is:
dM
dt VMM M (M11)
(29)
Since (t) 2 by Lemma K.1, (11) can be rewritten as the following:
dW
L-1
W WW 2042
(30)
di
Proof Lemma 6.1. Suppose W (t) is symmetric solution of (11). By Lemma K.I, we know (tt) also satisfies (30). Now we R(t) be the solution of the following ODE with R(0)
(0)),, È. Note we don't define R(t) by (t)
L-1
dR
Σ 1
(31)
di
The calculation below shows that R (t) also satisfies (30).
dR
ER
R dR
RL-1-1
Σ
dt
dt
1=0
2L-2
Σ (-11)
RV
1=0
( (V 2+24
Since (0) (0)), by existence and uniqueness theorem, R ( W(t), AA R. So
dM
dR
dR
R
R = -V -
dt
di
dt
which completes the proof.
K.3 PROOF FOR THEOREM 6.2
Now we turn to prove Theorem 6.2. Let P I./2. Then (29) can be rewritten as
dM
dt (Vf(MP) M M M2
(32)
The following lemma about the growth rate of A (M) used later in the proof.
36

---

Published as a conference paper at ICLR 2021
Lemma K.7. Suppose (t) satisfies (32), we have for any T T, and & [d].
{M(((()) -M(((T))))MMMTT) [" (M(
(33)
and
P A (M((T)) & f (f)l
(34)
Proof. Since ) (t) is locally Lipschitz in t, by Rademacher's theorem, know (t) is differentiable almost everywhere, and the following holds
{M(((T)) {M [ (M dt.
dt
When (MT( de exists, we have
(MR(M(
G. aM G
8 (M))
dt
dt
0 (M
(V)((((())) ( GE
AM
Note that | < ||]||_ = 1. So |G, (VC. (V (0)]22. We can prove (34)
with similar argument.
To prove Theorem 6.2, it suffices to consider the case that M(0) = àI where == 1/P, WLOG we can assume f() diag(M1.... , Ma) by choosing suitable standard basis. By assumption Theorem 6.2, we have μ4r > max(u2, 0} and μn |V We use @m (Mo, t) to denote the
solution of M()) (t) when ((0) Mp.
Let R > Since f(.) is C smooth, there exists 8 > such that [Vf((;)) vf(W2) S 8 W1 W2ll2
for all Wi, Wa with W 112 |2ll22 - R.
(P-(P11)
Let K. 3/p1. We assume WLOG that R S x((-1)) Let Fa(x) f (a-(P-1) 1-x2-P/CO P)(P-1)
Then (x) (P-1)=-
P-1 "F"" We will use this function to bound norm growth. Let
ItRx"
(t) 8-(F-11 x(P (P-I" Define Ta(r) a-(P-1) 1p
It is easy to
2pr(P
verify that ga. (Ta(r)) p-1
Lemma K.8. For any (ā; R. we have
(a-(P-1) -x-1-xx10 -P(-1) FF((x) E <0 1)x]
Proof. On the one hand, we have
(P-1)
à (PP-1) ((P-1) (P-1)
Fa(x) (
2
1 KZ -a-k///-PP
P/[P-1] -1-1--
On the other hand,
(P-1P-1) K
c (P-11)
& (P-11 x -F())))F(())=
Fa(x)) = Ja-(P-1) pP((P-1) +
dz <
P/(P-11 dz
x-(P-11
à (P
-1
= k(P 1)
21/(P-1) 1)
(PP-1)
< <k(P 1)x,
which completes the proof.
37

---

Published as a conference paper at ICLR 2021
Lemma K.9. Let Mo be PSD matrix with ||Moll2 s 1. For (tt (m and (T(c).
| = (M) & (1, (t)
Proof. Since IVS(M)))| & M S + + (()()))) P, by Lemma K.7, we have (M) - (M) ! 2( +((((M))))))(((
dr = 2 (P L F((M((((T))
So
(a(A)(M(t))) S (P -1)t. If [0Ml2 < é, then [((]] (1) (I) If (1)l22 2 á, then by Lemma K.8, a- (P-1)) -:(0p- - 1)c (P-1) c
(((l)
Fa(c),
so ( S e for all 1 & (a(c). Applying Lemma K.8 again, we have
à- (P - (IM (P-1) (())(()))2) x(P 1)c 2p 1)l + x(P 1)c,
which implies |M(() S (1) ग by definition.
Consider the following ODE:
dM
- (VSO)M +
dl
We use (Mo t) to denote the solution of M when M(0) MM. For diagonal matrix Mo. (I) is also diagonal for any I, and it easy to show that
{ (1oee Moe.) (P-1) (P
+
e. Moc; # 0,
e, M(t)e
(ae)
(35)
e. Moe; =
Remark K.10. Unlike depth-2 case, the closed form form solution, M(t) is only tractable for diagonal initialization, i.e., (35) (note that the identity matrix diagonal). And this is the main barrier for extending our two-phase analysis to the case of general initialization when L 2 3. In Appendix L, we give more detailed discussion on this barrier.
The following lemma shows that the trajectory of M()) is close to M())
Lemma K.11. Let Mo be a diagonal PSD matrix with |ooll S For M(I) = Φm 1)
and M (t) = @. (áMy, t), we have
(M) M M(T. O(T =((P))))=0((+)))))
Proof. We bound the difference D = M - M between M and M.
dD dt
= =2||T5() Vf(0) [M" - -M²) + (Vf(M") -f(())))))(()))))o M²I
< 2 (IVS( M - M P | |V/(( -
22 #1 P max M - M
P- D /r + 311M1
where the last step is by Lemma K.4. This implics that
(D(T)
dr < / 2 (piPga.(())
D(t]le <
(D()) ([D()) (T), dr.
==0 dr
F
38

---

Published as a conference paper at ICLR 2021
So
Ta(r)
(a(r)
[ -
exp (1g
22
2/11P/ exp
gā.r(F)d5
Ta(r)
P
Perr (Ta()))))))
23ga 1 (x)=
exp
In
dt
P-1
gār
Ia(r)
28ga (t) (T)=T gā.r (Ta (Ta(r)) dt
1
ga. (Ta(r)) gā.r (T,((Ta(r)) =f
=28-
2411
Kga,
(Ta(r)) p-1
=rr
which proves the bound.
Lemma K.12. Let (() = om (). M() = (m((MMo,)) If max [olll S 1.
Fort t < (r(r), we have
M(t) M(OlIe & (2) 200 | M()))
Proof. Define (t) M()) (t). Then we have
dD
(V]((M)) (M--MY + (V(MM)-VV((?>) VS(M²) M²)
di
S [IVF(M** 122 M + B - M |F |||| 12)
2 (1 + M|| 12 (1MM)
D|
P- DIIF
where the last step is by Lemma K.4. So
Ta(t)
[((T()))) < |(D())l - cxp
2Pp1
(1+ 1iggaarr (t) ga (t)dt
P
Pa. (Ta(T)
< [(OO) cxp
In
2kgga, (Ta(r)) (Tga.((T(rr) Df
P-1
(0.r(0)
2ar"
which proves the bound.
Let M (t) = dm (aeieT, à (P (P-1) PP-( +t) Let M())
lim M (t).
a-+0
Lemma K.13. For every t E (-00, M(t) exists and M (t) converges to M(t) in the following rate:
M M
(P-1) We prove this lemma in Proof. Let e be a sufficiently small constant. Let T == 241(P-1)
the cases of t [- and t T respectively.
Case 1. Fix t (-00, T). Then (F 1) (-1(P-T] + S Tc(.). Let ā be the unique number such that k(P - 1)ā + à (P-1) (P-1), Let á' < be an arbitrarily small number. Let to = Tax
2-1(P-1) By Lemma K.1l and (35), we have
(n'e (0) âeje T1p < |m (ā' 10) ( w))l SO(ā+t)).
39

---

Published as a conference paper at ICLR 2021
By Lemma K.9, I0 ( to)ll2 á. Then by Lemma K.12, we have
@mm to +)- ((āereT = ( 2nc" -0(ātt))= - 0 (()).
This implies that {M satisfies Cauchy's 's criterion for every t, and thus the limit ((t) exists for & T. The convergence rate can be deduced by taking limits for &' + 0 on both sides.
Case 2. For 1. = T with > 0, 6m (M, is locally Lipschitz with respect to M. So [ (1) M2(0 = (1mm(MM))) (T), - &m (T),
-T)
O(à),
which proves the lemma for t > T.
Theorem K.14. For every t E (-00, t00), as a + 0, we have: 1P-1)
ât, 2/11 11 +1) - M(0) = O(artt)
pm
(36)
and for any 2 S k S d,
d dm àt, à (11-1) (um(P-)))
2/1 -1 +1) +1)) O(a).
(37)
Proof. Let Ma == om àI, a (P-1) 2p1(P-1) +1) Again we let e be a sufficiently small constant and
T: -k( 1x(P-1)) -1(P-1)a--- (P-1)
We prove in the cases of E (-o0, T) and > T respectively.
2pr (P-1)
Case 1. Fix E (-00, TV. Let ân == âetI. Let ân be the unique number such that Ko (P- 1)ā2 +
an (P--1) = aj (P-11) Let = (ā)) --10-11-a-11 (P-1)
Then
(P-1
lI0m(aI, to) d 1| S @m to) - (mI, (o),,tt)// to) 1p + +|[ām(at, to) âre
F
= =O aa)
=())..
By Lemma K.9,
S a. Then by Lemma K.12, we have
MM(()) - MG, (1)l = || ( to + +1) - om (d
c
2ne" O(a) = 0(a
Combining this with the convergence rate for M (1) proves the bound (36). For (37), by Lemma K.7, we have
(T) --- A--((M((t)) < 2(P-1) ((P-))|V((M[()) di
2(P 1)(m 3 MM |M )d
(38)
10
S 2(P - 1) (ni(1 - TT)) タ (1 xiz
k
By Lemma K.11, AI | = c + O(cPtl). For 22
(T) 2 ((0-1(111) - 2(P - 1) (1I(T - -T;) + k:
2 0)
à + (P-1)
2 l(a (P-1))
(cc)
2p1 (P - 1)
> 2iaa- ((P-)))
40

---

Published as a conference paper at ICLR 2021
Thus Au As - (()).
Case 2. Fort = + with 7 > 0, @m (M, is locally Lipschitz with respect to M. So
(a -M, (1)lF -
(M. (,0 (M),
=0 -
which proves the bound (36).
For (37), again by Lemma K.7, have
N 1-P X (Ma(TT) - (Ma(T+
T+T
2( 1) f (t) dt
T+T
2(P - ( (B (1) (M ( + +IVVS ((M)) (12) di
T+1
2(P 1) + B M ( dt
T
$ (11).
Thus X1- (M, + (T))) = ((( that is, A (T, O(6), 22.
Proof of Theorem 6.2. Note that (M()) (()) and
@m âI, à (P())
2p1 (P (P-1) + +t)) P
a-(P-1)
o (al, 2P 11) +
By Theorem K. 14, We have
(1-1/P) 2/1 P -
+1) W(1)
Φ
aI,
F
âl à (P--1)
11 +1 +1) P
- -M(())
<
mm
2411 11
④I, à (P--)
max (1
@m âI, ā (P-1)
P-1
P
2/11 - +1) - -M(())
(P - +1) [
- ग 00(1) = ((a _.t))))
and for k d
d (0 (aI, aI, a (1111)
PP - +1) +1)) dx (dm aI, à (P--1) 2 (P- 1) + +1)) 0(ā0) =(a).
L ESCAPING DIRECTION FOR DEEP MATRIX FACTORIZATION
For deep matrix factorization, recall that we only prove that GF with infinitesimal identity initialization escapes in the direction of the top eigenvector. The main burden for us to generalize this proof to general initialization that we don't know how to analyze the early phase dynamics of (29), i.e., the analytical solution of (39) is difficult to compute, when L 2 3. Intuitively, the direction that the infinitesimal initialization escapes 0 is exactly M == lim |MO| where Mt) is the solution
M
of (39). Showing M Tade is critical step in our analysis towards convergence GLRL.
dM dl
V 1124/(().
(39)
41

---

Published as a conference paper at ICLR 2021
However, unlike the depth-2 case, M can be different from fata even if of o (0)0r 0. We here give an example for diagonal (0) and f(() at Appendix L.2. Nevertheless, we still conjecture that except for a zero measure set (0), M = Li based on the following theoretical and experimental evidences:
If o. M (0)o, 0 and rank(M = 1, we prove that M -ia (See Theorem L.1)
For the counter-example we show experimentally, even with perturbation of only magnitude 10-5, M = vi The results are shown at Figure 7. The y-axis indicates (#), un (t)) where u, (t) is the top eigenvector of (t). As [[[]l) becomes larger. u, (t) aligns better with v1, which means the noise helps M escaping from vy The larger the noise is, the faster un (1) converges 01.
L.I RANK-ONE CASE
Theorem L.1 (rank-1 1 initialization escapes along the top eigenvector). When rank(M((0) = 1,
lim [ Vlll if (0)o) 0.
((t)
Proof. Let u0)) be the vector such that M M0) (0) and u()) Rd be the solution of du(t) = [| (t))u(t).
dt
It is easy to check that M(t) = (t) is the solution of (39), because
dM
du
du
+ u
(()) (1 M(t)V [u(()]) V - (2)
dt
dt
dt
Let T() = So (s))2 2-2
ds. Then
du du dt
1
| | Tull-~vs(()))) -v(())
di
dr de
That is, under time rescaling t + r Tt), the trajectory of utt) still follows the power iteration, regardless of the depth L.
L.2 COUNTER-EXAMPLE FOR ESCAPING DIRECTION
Let (f(o) diag (2 0.............. E 100 be diagonal. Let (0) be also diagonal and W (0);,, Unif 1.1] for i [10] (2), ( 16a, where 10- 16 is small constant. Let the depth be 4.
Lemma L.2. With V (() and ((0) constructed above, vn M > and M + Tale
Proof. It is easy to check that e = e₁. so v [ > 0. Now we prove that M( + Tale As both (0) and (0( are diagonal, ((1) is always diagonal and has dynamics
(M = 2V M()
(10)
dt
therefore we have closed form of M()::
M(1 M(O) (V) vi [10].
For i E [10), the time for M() going infinity is (2M (0))).))) By simple calculation, M (1)2.2 goes to infinity the fastest, thus M E viu.
We remark that the scales of W (0) and V (0) do not matter as in gradient flow, scaling V (0( is cquivalent to scaling time (by Lemma L.3 below). And for this reason, the a-axis is the chosen as [ the relative growth rate. [W 1
42

---

Published as a conference paper at ICLR 2021
dynamics VROJM -M'V0
10
[M, ux(t))
10
10
10
1=10-2
10a
10a
10th
1044
10
[WIC]]
Figure 7: Dynamics of dM - -
plotted, where L = 4, u is the
de
top eigenvector of (t) and the relative magnitude of noise. The initialization we use this
where ( is what we construct at Appendix L.2, and a matrix where entries are i.i.d. samples from the standard Gaussian distribution (O, 1). We run 5 fixed random seeds (the noise matrix) for each The trajectory of W is calculated by simulating gradient flow on M with small timestep and RMSprop (Tieleman and Hinton, 2012) for faster convergence.
experiment is W noise (0) W (0) + ? (Z+
Lemma L.3. Suppose g : Fd + Rd P-homogeneous function, that is, g(a0) X (() for any a > 0, and (0'(() (t)(. Then a00((a (PP-)t)) is the solution of
d0(() g))()))
@(0) = a0 a0'(0).
(40)
dt
Proof. Simply plug in O(t) aa Pa then we have
do(t) dad' (a (t) = d(a"-It) = a
(a
=g(((t)).
dt dt
M PROOF OF LINEAR CONVERGENCE TO MINIMIZER
In this section, we will present the theorems that guarantee the linear convergence to a minimizer Wo of f(.) if the dynamics (41) is initialized sufficiently close to Wo. i.e., [[(()) Wollp is sufficiently small. In Appendix M.3, we will apply this result to prove Theorem 6.4.
dW
2642 =: gWW) - Σ w WFWWWW)
L-1
(41)
dt
Throughout this section, we assume (ank(W)) = & and use m = A& Wo) to denote the k-th smallest non-zero eigenvalue of Wo. The tangent space of manifold of rank-k symmetric matrices
Wo is T (VW, WoV e [dd can be shown that dim = k(d k) A(++1)
k(2d k(2d-k+1)
Let J(W) be the Jacobian of g(W) in (41). For depth-2 case, we have shown that T an invariant
subspace of J(W,) in Theorem H.5, property 2. This can be generalize the deep where
L > 3. Therefore, we can use J (W))::: T + T to denote the linear operator J (WW) restricted on
T. We also define 11 (W) as the projection of W e ddd on T. and 115 (W) = W 11 (W).
Towards showing the main convergence result the section, we make the following assumption. Assumption M.1. Suppose J 7 diagonalizable and all eigenvalues negative real numbers.
Wo is a minimizer, so is clear that J J(W))l has no eigenvalues with positive real parts (otherwise there is descending direction of f(-) from W.. since the loss f(-) strictly decreases along
43

---

Published as a conference paper at ICLR 2021
the trajectory of (41)). If further Assumption M.1 holds, then we know J (Wo)): T T can be diagonalized as JW = V(EV-(()) where Σ; diag(- (diim()) V Rdim(T) T. V(z) ()i x; V,, and V, is the eigenvector associated with eigenvalue -AA-
As shown in Theorem M.3 below, this assumption implies that if ((0) is rank-k and is sufficiently close to Wo, then (t) Wol S Ce- for some constant C. For depth-2 case, the above assumption is equivalent to that ((U)) is "strongly convex" at Ug. except those 0 eigenvalues due to symmetry, by property 2 of Theorem H.5). For the case where
3, because this dynamics is not gradient flow, in general it does not correspond to loss function and strongly convexity does not make any sense. Nevertheless, in experiments we do observe linear convergence to Wo, so this assumption is reasonable.
M.1 RANK-k INITIALIZATION
For convenience, we define for all W E Sa.
W ha|==||y-1 (IT" (W)) I| [[ = | (W))p- || == |n
|
II (W)
The reason for such definition of norms, as we will see later, is that the norm (or the difference) in the tangent space of the manifold of symmetric rank-r matrices, !|W - W dominates that in the orthogonal complement of the tangent space, I WW when both W, W get very close to the Wo (see a more rigorous statement Lemma M.2). WLOG, we can assume
| I1II, 1- 11 S 11 I1..
for some constant K, which may depend on f and Wo. This also implies that I1- S 1-11g- Below we also assume for sufficiently small R, and any W such that IW - Wollr S R, we have [VV/())ll S p and [|J [A]]] p S 3 || for any A. In the proof below, we assume such properties hold as long as we can show the boundedness of W Wo.
Lemma M.2. Lei max W Wolle, W
Wo = r, when
we have
5r
I
W
WW
W'll...
m
As a special case, we have
5 5|
W
W
W
Wol
S
m
Proof. WLOG we can assume Wo is only non-zero in the first k dimension, i.c., [Wolg = 0, for all i> k + +15 k + 1. We further denote W and W' by
A B B
A' B'
W =
and W'
C
B'
C'
where A, A' E 1
B, B' E R(d-kixk C. C' E (dd-))((d-k),
By definition, we have
A A'l B B' p < I - W IE and WW W F.2 = =ICC - CC'pp Moreover, we
have Amiin (A) 2 m - A Woll 2 m I W [F
2
m
Since W, W' is rank-k, we have C= = BA BT C' = B'A B² Thus
IW W |F
||C C'Il
BA- 'T B'A' B'
|B
B'll 11 B
FF + BA -
|| A' A|| B
||
BB' A'
| -B' 1|F BT
2r
(2r
2r
IW
W F.
+ W W
+ IW
WI
m
5r
W
W
W
m
44

---

Published as a conference paper at ICLR 2021
Theorem M.3 (Linear convergence of rank-k matrices). Suppose that rank ( = rank(Wa) and
[ - Wolly S R = max
m
M1 (293
2K
10p/mm
have (t) Wolly - Ce [ Wolly for some constant C depending on Wo, where (t) satisfies (41).
Proof. For convenience, define Wi(1) == 11 (W(1) Wo), W2(1) 11 (6) Wo) 11 (t)). We also use (: 1-11 = (V-1()) (.), V- ()) for short.
d W|]Wi dll (t) Wolli
dt
dt = 2 IT (W(()) .. (W(t) Wo) -Wo)
dt
22 "f (e(W(())) wi())) ((W(())).((())
$ 2 II (J(W))(W(1) Wo). w1(1))
(2))g(W(I) Wo) ((W)) Wolly (W()) Wollv
(uf (J(Wo)[W1(t) wa(t))) Wi(t)) V-1
+2 W.) - ((()) Wolly Wi((tlly
(TT (W)) wi((), V 2 [ ([)ll)
+1)lg(W(I)- Wo) - ((W)) - Woll [Willly
For the first term (n (W()) Wi (t) we know W1 T. and T is an invariant space of JWW). Recall =
have
2 TH (W1()) Wi(() )-1 = -2 (Wi(t) V- (w1((()))) < 2 [Wi(f)
For the second term 2/ [/ (1) we have
2 [J(( s [2] 2 2 ((W)l W 2 = 2p W2(1)FF
For the third term 2 ( - (W) J(WW) - Woll, [W]ll) we have
2 (l Wo) J(W.) wolll s 28
((()) | (11- - ( + ([
< 48(K² [Wi (
Thus have shown the following. Note far we have not used the assumption that W is rank-k.
W| (V)) < 2 [ (p (lllWa(()le
+ 23K ( + 23 (
dt
that is,
dlog W
< 2241 43K² [[ 4,3 ( + 2p Wa(t)ll
(42)
dt
[t)
Let T = stpft 0: (1)l m ). Setting W' Wo in Lemma M.2, have for T.
r = W[t) - Woll - [[(]) W < K W (f) - Woll I m 2
Thus,
5 |
Wolle
5 W (t)
W
[2(t))l; - <
< m.
m
4
45

---

Published as a conference paper at ICLR 2021
Thus, from (42) derive that
d log Wi (1)
< 2m + K22298 + 10p/m)) [Wi()ly S -
(43)
dt
Since μ1 0, [Wy decreases for [), Thus T must be oc, otherwise [[ii(T)ly lim;-r- [| < Rí. Contradiction.
Therefore, for any & E o0), we have W (4)ly -
[0)]l) e- #1, That is,
2 [W] v
2R
(
μ1
P1
Thus from (43), have
-H1 (29 + 10p/m) [
K²
( 1|W [/
[[w = W[ (1)l - [W)]l) exp
2
K2 R
- (i cxp
+ni++
(29 + 10p/ml)
A1
=: [ E
which completes the proof.
M.2 ALMOST RANK-R INITIALIZATION
We use Mtt) to denote the top-k components of (t)) in SVD, and (t))) to denote the rest part, i... ((t) (t). One can think (t) as the main part and N (t) as the negligible part.
Below we show that for deep overparametrized matrix factorization, where W satisfies (41), if the trajectory is initialized some (()) in small neighborhood of the k-thh critical point Wo of deep GLRL,, and (O)) is approximately rank-k; in the sense that N(0) is very small, then (t) Wolly is roughly at the same magnitude of N()).
inf,2o
Theorem M.4 (Linear convergence of almost rank-k matrices, deep case). Suppose Wa is critical point of rank k and Wo satisfies Assumption M.I, there exists constants Co and such that if Co (O)l < (W) I r, then there exists a time and constants C, C', such that
(1). (W))) Wolly S //t/t (W Wollyz S.
(2). W (T) Woll S C' (IN()))
Proof. When W - WolF S (o)) [N(|) S Amin thus we have
Amin Wo) 2
MM WollE (W Wolle (N(())
thus by Lemma M.2, we have
W2(1)le2 < [M(()) Woll + ([N()))
(() Wolls
+ +INN(1))
Amin (W))
[oll (t)ll + 10 (1)
Amin (W))
10K²
[t)l + (t) + (t)
Amin (W))
Thus we can pick constant Co large enough and r small enough, such that for any t 2 0. Co [[N(()) < (t)ll S r, then it holds that:
46

---

Published as a conference paper at ICLR 2021
The "small terms" in the RHS of (42) satisfies that
4 Wttl + || [2(t))le
48K² [W
S C, + S p
|
for some C1 and C2 independent of
The spectral norm
[VT (WFf( =: p for all t 2 O.
Vz < r,
MIPE (L- 2%p
2
2r Coa
where K. = 0.
Note these conditions can always be satisfied by some Co and because can first find 3 groups (Co, r) to satisfy each individual condition, and then take the maximal Co and minimal r. it's easy check these conditions are still verified. And we let Te,.r be the earliest time that such condition, i.e., Co || [[)] I [ - fails. Thus by (42), for E [0, Tc..r) we have "2", [W = (() & [[)le) "i = (O)ll) e-=". Thus (I) holds for any T smaller than Tc.,r. If Tc..r Therefore, below it suffices to consider the case where Tc..r finite. And we know the condition that fails must be Co [t) I [W)ll),,, i.e. Co (T [| (WT(Tco)))ll
oo, then clearly we pick sufficiently large T, such that (2) holds.
By (34) in Lemma K.7, we have
2 --1
(1 S ( p).t.
Define T" = (0)1 2-
(L-2)p we know for any < T', we have [IN(
|1 3
KL [IN( That is,
IN(OI 8 -1 OO
= 10.5 10.5"z" "z" .0.5 _0.5-"5 1.5--z²²
[
E
1KKI: KL. 1- K.
E [1/
[O)
Now we claim it must hold that T" 2 TCo.r. Otherwise, we have
Co
|N(()] S Co (N((T)) V [WT(T')l Se --
|W1 S 12
2
* (I-
7 T <
Therefore,
2 In p
which contradicts to the definition of Co and C. [
As result, we have
2Cova (N(0)) 2C/1/ 2200|INN))222 2 Co (N ) [WT((T),)))l)
[i Tog
and therefore,
2 In [W]ll)
Tco. I
P1
2vdC, [N(0]]
Thus by Lemma M.2, we know
(TT...)) Wollp I (T - Wolle.1 (Tc.r) - WollE
< K|| W (T [ (Mc..) Woll + (TT.)c.))
2 {((IN()))))))
(0)le)
= (((I)))))
47

---

Published as a conference paper at ICLR 2021
M.3 PROOF FOR THEOREM 6.4
Proof for Theorem 6.4. Let Co, r be the constants predicted by Theorem M.4 w.r.t to ((o). We claim that we can pick large enough constant T, and ag sufficiently small, such that for all S Olg. the initial condition in Theorem M.4 holds, i.e. Co (N S [[)lll S r, where
(0)) = di (al, (P-1) (P-1) T)-
This is because
first ensure (T) ((o))ll is sufficiently small, i.c., smaller than By Theorem 6.2, we know when a - 0. ((T) - W()) I K ( (0))) = o(1) and [[]] = O(a).
By Theorem M.4, we know there is a time T (either o or some sufficiently large number when Tco.r = 00), such that || (T)- Woll = (()l)))))l = O(a).
48


Reviews:
[{"review_id": "rg66xkHo3hG", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "**Summary**\n\nThe paper studies the implicit bias of gradient descent in the problem of matrix factorization. The objective is to gain some intuition on the effective regularization performed by gradient descent in more involved problems, e.g. neural networks. Previous papers conjectured that gradient flow (i.e. the continuous-time limit of gradient descent) implicitly regularized by the nuclear norm, while more recent ones conjectured that the regularization was done purely in terms of rank. This work provides an answer to this question in an important setting, i.e. they show analytically and numerically that for the problem of factorizing two matrices without any rank constraint, the gradient flow (GF) algorithm effectively minimizes the rank rather than the nuclear norm, if starting from an infinitesimal initialization. This is done by showing that GF is equivalent to an algorithm called Greedy Low-Rank Learning (GLRL). They also provide evidence to show that this phenomenon transfers to the factorization of a larger number of matrices, and that in this context it is actually stronger as its dependency on the infinitesimal initialization weakens. \n\nNote that given the length and available time, I did not check all calculations and experiments given in the supplementary material.\n\n**Main comments and overall decision**\n\nI found the paper well-written and pleasant to read. The results are quite clearly stated and explained. I think the paper would deserve some re-organization to better fit the 8-pages limit, as it feels a bit compressed, especially towards the end. I also believe that some numerics in the appendix should be included in the main text, clearing space by removing some technicalities. Moreover, the previous literature on greedy rank algorithms should be perhaps better discussed. \nI believe the paper should ultimately be accepted at ICLR 2021, after the authors have taken into account the comments and criticisms I expressed.\n\n**Strengths of the paper, by section**\n\n- The paper is overall well-written and clear. In particular, the introduction and related works give a very clear overview of the previous literature (however I have to say that I am not extremely familiar with the previous works on the implicit regularization of gradient descent, so I could be forgetting important works). \n\n- I genuinely enjoyed Section 4 which gives an intuition on the reasons behind this low-rank learning behavior of GF in very simple toy models. On a general note, the splitting of the paper into clear sections is very good for the readability of the paper.\n\n- Section 5 is quite technical, and I believe some of these technicalities could be moved to appendix to improve readability and gain space. Having generalities in Section 5.1 makes the intuition quite clear, especially with Thm 5.3. I found the counterexample 5.9 to be particularly simple and appropriate. Section 5.3 could also perhaps be shortened, by making the results even more informal: the intuition behind the iterative rank growth of the solution of GF is very interesting and should be emphasized more than the technicalities.\n\n- The treatment of depth in Lemma 6.1 and Theorem 6.2 is well presented. I noticed that in both Thm 6.2 and 5.3 the times considered in GF and GLRL are not the same, could the authors comment on this time difference, and its dependency on alpha ?\n\n**Concerns and remarks**\n\n- In general, the paper has many results and claims, however it feels like the 8-page limit is quite limiting the results, resulting in numerous references to the supplementary material. I think the paper should perhaps be shortened, removing some technicalities, for instance in Section 5. For instance the last paragraph of the paper (page 8) should either be removed, or the experiments should be included in the main text, but its current state makes it unclear. In this paragraph I also did not understand the sentence “For depth-2 GLRL, the low-rankness is raised to some power smaller than 1, which depends on the eigenvalue”, could the authors clarify it?\n\n- On Greedy Low Rank algorithms, the paper (if I am not mistaken) does not compare this GLRL algorithm to previous algorithms developed in the literature, e.g. in “On Approximation Guarantees for Greedy Low Rank Optimization” , ICML 2017 or “Greedy Learning of Generalized Low-Rank Models” (IJCA 2016). I have to admit that I am not very familiar with this literature, but I believe that this type of algorithm is not entirely new, and the authors should perhaps discuss it more, or at least clarify this in their response.\n\n- Figure 1 is the only numerical analysis presented in the main text (there are more in appendix). The numerics show that it requires really an extremely small initialization to see the closeness of GF and GLRL (it starts to be clear for initial norms around $10^{-12}$ !). This is counterbalanced with Figure 2 in the depth $L\\geq 3$ setting, but this is only shown in appendix. In general, I believe that at least some part of Figure 2 should be included in the main text, perhaps merging it with Figure 1.\n\n**Minor remarks**\n\n- I was a bit confused when reading: after analyzing the simple linear case, the authors write “But what if $W(t)$ grows to be so large that the linear approximation is far from the actual $f(W)$?”, suggesting that the real behavior is not captured by the linear approximation, however to me it seems like Theorem 5.3 precisely shows under which conditions on the initialization one can use the linear approximation for the dynamics of GF.\n\n- In Section 4, when considering Matrix Sensing, appealing to Thm~1 and 4 of (Gissin&al 20) seems completely overkill and does not read well, as the first result is simply writing the ODE in the diagonal basis, and the second is simply solving an ODE by separation of variables.\n\n- What do the authors mean in Algorithm 1 by “if $W_r$ is close to a local minimizer of f among PSD matrices” ? Do they mean that going from rank r to (r+1) in GLRL does not change $W_r$ ?\n\n- In Theorem 6.3, why do the authors consider $inf_t$ and not a limsup? Is this simply for technical reasons in the proof, or is this genuinely possible that the trajectory “escapes” the GLRL solution for long enough times ?\n\nFinally, a list of typos :\n- Introduction: “we show GF […] converges” → “we show that GF […] converges” ?-\n- “before GLRL reaches first stationary point” → “before GLRL reaches its first stationary point” \n- Related works sections: “which remains it unclear”\n- Beginning of page 7: “Which is 40 when $R = 40$” → “Which is 40 when $R = 10$”]\n- Thm 5.10: “the eigendecomposition of $W$” → “the eigendecomposition of $– \\nabla f(W)$”\n- Page 7 : A parenthesis is misplaced close to the end of the page. \n- Page 8 (middle) : Gf → GF\n- Page 8 : “depth-2 solution of have” → Something missing. \n- Page 8 : a “but” should be removed.", "extra_scores": {}, "extra_text": {}}, {"review_id": "a2n8lpZ_tbt", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper analyses the implicit regularization in matrix factorization. The author suggest that for infinitesimal initialization the implicit regularization can be equivalently understood as iteratively solving matrix factorization with increasing rank until the rank is high enough such that the model can be fitted to zero loss. They provide certain theoretical evidence for their hypothesis. Furthermore, they analyze certain models with higher depth, claiming that in those models the described phenomenon appears already with \"less infinitesimal\" initialization.\n\nAs another contribution, the authors claim that their result refutes a conjecture by Gunasekar et al by giving a concrete counterexample. However, I think their counterexample is invalid: $M_{\\text{rank}}$ does not have rank 1 as the authors claim; in particular, it is not even symmetric and, hence, it cannot be represented in the form $UU^T$. Also, I do not believe that there is a rank-one matrix, which can represent $M$. Hence, $M_{\\text{nuc}}$ is the matrix of smaller norm, which fits to the observations.\nThis mistake is the main reason for my low score. I am willing to raise my score, if these issues have been addressed.\n\nFurther comments:\n-Do I understand it correctly that Theorem 6.3 and its interpretation below do not predict any different behavior as long as the number of layers is chosen larger than $3$? Moreover, I am not sure whether I find this argument very convincing: The authors claim that one advantage of deeper layers lies in the fact that it keeps the low-rank component more separated from the learned component. I agree that Theorem 6.3 gives some hint, but there is much more evidence required and at its current state this is rather speculative.\n\nTypos:\n-p.4: sixth line from below: Do you mean  $ \\mathcal{L} (U_{r-1}) \\approx \\mathcal{L} (U_r)- \\epsilon \\mu_1$ instead of $ \\mathcal{L} (U_r) \\approx \\mathcal{L} (U_r)- \\epsilon \\mu_1 $?\n-p.4 second line from below: $\\phi$ is not really defined yet, if I make no mistake\n-Theorem 5.3: $\\tilde{\\gamma}$ is not yet defined\n-p.7: seventh line from below, $T_{(}' \\alpha )$\n\n-----------------------------\nAfter having another look at the paper, I noticed that my complaint could be resolved easily in the following way: In $M_{rank}$ you replace 100 with $R^2$ and then the resulting matrix is symmetric and rank-one. Is this just a typo? I apologize that I missed this. \nFurthermore, I wonder whether the proof in Appendix H could be clarified. I feel that the part where the assumptions 5.5 and 5.7 are verified is not particularly clear and more details would be helpful.\n(Of course, I realize that I am late with this particular request, but I still believe that in this way the paper could be improved.)\n\n--------------------------\n\nThank you for your response. I raised my score accordingly.\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "ZDeno7BD_yW", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "## Summary\n\nThis paper study the solution of matrix factorization that can be found using gradient descent. In particular, the authors show that gradient descent converges toward low rank solution obtained with GLRL when the initialization magnitude is small enough. The proof are based on the analysis of Gradient Flow and its link to power iteration for linear system. The authors show that for rank-1 solution, trajectories with any small enough initialization have 2 behaviors:\n- a power iteration one where the trajectory gets close to $\\epsilon v_1v_1^\\top$\n- the same trajectory as the one starting from this $\\epsilon v_1v_1^\\top$ point, which correspond to the GLRL algorithm.\n\nThus the limit of the trajectory are independent of the initialization for the init is small enough. Then these results are extended to higher rank solution and to more layers. Some small scale experiments highlights those results.\n\n## Overall assessment\n\n- I find the results and the methodology of for the results in the rank-1 case very interesting. Part of the discussion of the results can be improved -- in particular the tradeoff between power iterations and the trajectory and the effect of the $\\log \\frac{1}{\\langle W_alpha, u_1u_1^\\top\\rangle}$ on the convergence speed.\n- The results in the general case (5.3) and deep MF (section.6) are harder to grasp and understand in the current form. I would advise to move section.6 in appendix to make more room for section5.3 and experiments. In particular, the setting of Figure.1 is not detailled enough. We don't know the data generation process/ the ratio of missing entries/... which are important to understand the figure.\n- One big question to me is how to ensure the assumption that one can find $T_\\alpha$ such that $\\phi(W_\\alpha, T_\\alpha)$ converges to $\\widebar W$ when it is not rank 1. In particular, we know that there exists a $T_alpha$ such that it will be very close of a rank-1 saddle point. The question is how to make sure this can be escaped as for 1st order differential equation, once 2 trajectories cross, they are the same I think. I would like the authors to clarify this point.\n- Figure.1, instead of the mean, it would be more interesting to report the max as the bound in (7) is uniform on the $\\|W_\\alpha\\|_F$ ball. Also, using 20 repetitions would be more convincing (these are small scale experiments so averaging over many realisation is possible).\n- I would find it interesting to explore the effect of using $\\epsilon v_1v_1^\\top$ as an initialisation compared with random init. As a significant part of the optim is used to perform power iteration to find the right direction and the results does not depend on it, it should give better results.\n- There is a series of work very related to this one on global optimality of matrix factorization that also advocate for a greedy resolution. It would be interesting to mention this in the related work. See:\n\n```bibtex\n@article{Haeffele2019,\n  title = {Structured {{Low}}-{{Rank Matrix Factorization}}: {{Global Optimality}}, {{Algorithms}}, and {{Applications}}},\n  author = {Haeffele, Benjamin D. and Vidal, Ren{\\'e}},\n  year = {2019},\n  volume = {42},\n  pages = {1468--1482},\n  archivePrefix = {arXiv},\n  eprint = {1708.07850},\n  eprinttype = {arxiv},\n  journal = {IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI)},\n  number = {6}\n}\n```\n\n## Minor comments, nitpicks and typos\n\nSome minor comments and grammatical comment. I am not an english native speaker so it might not be real mistakes.\n\n- p.1: `(see (Chi et al. 2019) for` - use `citealt` to avoid duplicated parenthesis?\n- p.1: `however, even in the case that the rank` -> `in the case where`?\n- p.1: `but its behind mechanism` -> `but its mechanism`?\n- p.2: `one single` -> `a single`?\n- p.2: `and matrix factorization -- the focus of our paper.` references are needed here.\n- p.3: `there is an unknown rank-$r$ matrix` -> rank $r^*$.\n- p.4: `a unit top eigenvector` -> isn't it the normalized top eigenvector? The part on the `arbitrary` top eigenvector is unclear. This should be clarified.\n- p.6: `Thm5.6` There is a missing $\\epsilon$ in the definition of $W_1^G$.\n- p.8: `for distance between Gf` -> `GF`.\n- Algorithm.2: I think the update run for `perform on step` is incorrect. It should be something like $U_{r,i} \\leftarrow U_{r,i} - \\eta \\prod_{j=1}^{i-1}U_{r,j}\\nabla f(\\prod_{j=1}^LU_{r, i})\\prod_{j=i+1}^{L}U_{r,j}$.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "H1kXKXG5bgd", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary\nThis paper analyses the dynamics of gradient descent learning for matrix factorization. The authors show that when there are two factors, the gradient flow initialized close from 0 closely follows another algorithm, called greedy low rank learning (GLRL), which learns the factors starting from rank one approximations, and then greedily adds dimension. This shows that the gradient flow learns incrementally, and favors low rank solutions. This allows to invalidate a conjecture stating that gradient flow finds minimum nuclear norm solutions. The authors finally study deeper factorizations under the light of GLRL\n\n\nMajor comments\n- The article is easy to read and well organised. Some results could be made more explicit (see minor comments).\nI am not an expert in this domain, but it seems like the article provides an advance towards understanding the implicit bias of gradient descent.\n- Algorithm 1 is not implementable, the authors should be clearer about what ‘keeps decreasing’, or ‘close to a local minimum’ mean. I think that it is rather a theoretical ‘oracle’ algorithm, where the gradient descent on $U$ should be a gradient flow and the outer look ends when the rank is matched. The practical approximation to this algorithm can then be discussed in appendix.\nThm.5.3 seems like an important and fairly general result for the dynamics of the gradient flow.\n\n\nMinor comments\n- In eq.5, the matrices are always going to be symmetric, so why is there a transpose? \n- Beginning of page 4, why start from $U(0) = \\sqrt{\\alpha} I$ ? I think that the general case ($U(0)$ non diagonal), is also tractable in closed form. \n- The references to Gissin 2020 in the same paragraph also seem unnecessary to invoke for such a simple result, and feel a bit frustrating.\n- In 5.1, the authors assume that $J(0)$ is diagonalizable, and write $J = \\sum_{i=1}^d\\mu_i \\mathbf{v}_i \\mathbf{v}_i^{\\top}$. It should be specified exactly what the vectors $\\mathbf{v}_i$ and $\\mathbf{u}_i$ verify: to me, this looks more like a singular value decomposition; a diagonalization would imply that $U = V^{-1}$ (but I think that the authors really need diagonalization here).\n- Page 5: “One can easily show that for the other case that the initialization has positive alignment with...” it would valuable to explicitly write down the expression for the “other $z(t)$” in question.\n- Theorem 5.3: similarly, it would be valuable to explicitly write down the expression for $z(t)$.\n- Lemma 5.4: it would be insightful to write down the (simple) explicit expression for $J(0)$.\n- Lemma 6.1: It should be specified before that $W$ is symmetric, otherwise it makes the definition of $W^{2/L}$ awkward.\n- The reasoning in the proof of the lemma 6.1. is also slightly misleading: it should be made more explicit that the authors do not assume that $R= W^{1/L}$, but rather that $R$ is defined by the initial value problem $R(0) = W(0)^{1 / L}$ and the ODE (25). Then, the authors verify that $R^L$ satisfies the same ODE as $W$, hereby showing $R = W^{1/L}$.\n\n\nMisc\n\n- In the intro: “which remains it unclear whether the approximation error can be bounded until convergence”: this should be rephrased\n- Avoid undefined acronyms\n- Page 5: “, e.g., GF around a saddle point lies in this case” this sentence is unclear to me.\n- Page 5: “A special case is that the direction of$\\theta_{\\alpha}  -\\theta_0$ converges.”: I don’t understand this sentence, does it mean something like “this definition implies that $\\theta_{\\alpha}  -\\theta_0$ converges”?\n- Theorem 5.6, first equation: there is a missing $\\varepsilon$ subscript missing after the first missing on the $W$\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The article is easy to read, of interest for the community, and provide some advance towards understanding the implicit bias of gradient descent.
The results and the methodology for the rank-1 case are very interesting and convincing.
Yet, some results could be made more explicit and the comments by the reviewers should be addressed for the camera ready paper, in particular the one on the organization.

Decision: Accept (Poster)