Rank-1 Matrix Completion with Gradient Descent and Small Random Initialization
Authors: Daesung Kim
Hye Won Chung
Venue: NeurIPS 2023 poster (2023)
Keywords: Matrix completion
gradient descent
random initialization

Abstract: The nonconvex formulation of the matrix completion problem has received significant attention in recent years due to its affordable complexity compared to the convex formulation. Gradient Descent (GD) is a simple yet efficient baseline algorithm for solving nonconvex optimization problems. The success of GD has been witnessed in many different problems in both theory and practice when it is combined with random initialization. However, previous works on matrix completion require either careful initialization or regularizers to prove the convergence of GD. In this paper, we study the rank-1 symmetric matrix completion and prove that GD converges to the ground truth when small random initialization is used. We show that in a logarithmic number of iterations, the trajectory enters the region where local convergence occurs. We provide an upper bound on the initialization size that is sufficient to guarantee the convergence, and show that a larger initialization can be used as more samples are available. We observe that the implicit regularization effect of GD plays a critical role in the analysis, and for the entire trajectory, it prevents each entry from becoming much larger than the others.

Rank-1 Matrix Completion with Gradient Descent and Small Random Initialization
Daesung Kim Samsung Electronics dskim95phd@gmil. com
Hye Won Chung
School of Electrical Engineering KAIST
hwchung@kaist.ace ac..istt.c..k.. ac.kr
Abstract
The nonconvex formulation of the matrix complction problem has received signif- icant attention in recent years due to its affordable complexity compared the convex formulation. Gradient Descent (GD) is a simple yet efficient baseline algo- rithm for solving nonconvex optimization problems. The success of GD has been witnessed in many different problems in both theory and practice when it is com- bined with random initialization. However, previous works on matrix completion require either careful initialization or regularizers to prove the convergence of GD. In this paper, we study the rank-1 symmetrie matrix completion and prove that GD converges to the ground truth when small random initialization is used. We show that in a logarithmic number of iterations, the trajectory enters the region where local convergence occurs. We provide upper bound on the initialization size that is sufficient to guarantee the convergence, and show that larger initialization can be used as more samples effect of GD plays a critical role in the analysis, and for the entire trajectory, it prevents each entry from becoming much larger than the others.
available. We observe that the implicit regularization
Introduction
Recovering a low-rank matrix from set of linear measurements is at the heart of many statistical learning problems. Depending on the structure of the matrix and the linear measurements, it reduces to various problems such as phase retrieval [[] blind deconvolution (2), and matrix sensing [3]. Matrix completion 4 also one such type of problem where each measurement provides an entry of the matrix, and the goal is to recover the low-rank matrix from partial, usually very sparse, observation of the entries. One of the most notable applications of matrix completion is collaborative filtering 5. which aims to predict user preferences for items based on highly incomplete observation of user-item ratings. There are also a number of different applications, such as principal component analysis 6 and image reconstruction 77. just name a few.
Extensive amount of work has been dedicated to provide an efficient recovery algorithm for matrix completion with theoretical guarantees 8 The convex relaxation based nuclear norm minimization 9 was the first algorithm proven to recover the matrix with near optimal sample complexity. Despite its theoretical success, the convex algorithm was found hard to be used in practical scenarios due its unaffordable computational complexity and memory size. Therefore, the nonconvex formulation of matrix completion with quadratic loss has received significant attention in recent years. Many different algorithms have been proposed for the nonconvex problem, and their convergence toward the ground truth has been analyzed. Examples include optimization on Grassmann manifolds 10, alternating minimization [II, projected gradient descent [12], gradient descent with regularizer and (vanilla) gradient descent 15
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Gradient descent (GD) has served as baseline algorithm for solving nonconvex optimization problems. However, the convergence of GD global minimizers is not guaranteed, and it can take exponential time to escape saddle points [16]. Nevertheless, GD with random initialization has been shown to successfully recover the global minimum many different problems such as phase retrieval M. matrix sensing [1]], matrix factorization [8]. and neural network training [1]]. Previous work on matrix completion [14] 15] proved the convergence of GD under the spectral initialization, which locates the initial point in the local region of the minima. However, the role of random initialization in solving matrix completion with GD is not fully understood yet, although its success is observed in practice. Therefore, we aim to answer the following question:
Can GD with random initialization solve the nonconvex matrix completion problem?
We answer this question affirmatively and show that GD with small random initialization successfully converges to the ground truth for rank-1 1 symmetric matrix completion. In the analysis. we use vanilla GD, which does not incorporate any modifications, such regularization truncation, into the GD algorithm. We also characterize the entire trajectory that GD follows by showing that the trajectory well approximated by the fully observed case. The small initialization plays a critical role in analyzing the trajectory of the early stages, where the randomly initialized vector is nearly orthogonal to the first eigenvector of the ground truth matrix. We provide bound on the required initialization size for the algorithm to converge, and our bound suggests that one can use a larger initialization to improve the convergence speed as more samples are provided. However, any case, GD with a small random initialization takes only logarithmic amount of time (with respect to the matrix dimension) to reach the point where local convergence can begin. To the best of our knowledge, this is the first result on matrix completion that proves the convergence of vanilla GD without carefully designed initialization.
Although our result is restricted to the rank-1 case, we believe that this work provides an important evidence for understanding the more general rank-r case. At the end of this paper, we will discuss some technical difficulties that the rank-r case naturally has, and provide some empirical results related to them. However, studying the rank-1 matrix completion problem is not only motivated by theoretical interest, but the problem itself also appears in some practical problems such as crowdsourcing (20 21)
This work is motivated by the recent success of small initialization in matrix factorization and matrix sensing. It was first conjectured in 22 that sufficiently small step sizes and initialization lead GD to converge to the minimum nuclear norm solution of a dilensinnnson matrix sensing problem. The conjecture was proved in [17] for the fully overparameterized matrix sensing under the standard restricted isometry property (RIP). A recent study by (23] provided more general results by showing that the early iterations of GD with small initialization have spectral bias. Many other works such as [24 25 26 have also studied how GD or gradient flow with small initialization implicitly forces the recovered matrix to be low-rank. However, the recovery guarantee for matrix completion has not been provided by any work.
Related Works
For the matrix sensing where RIP holds, the loss function has global benign geometry in that it does not contain any spurious local minima or non-strict saddle points [27]. In the case of matrix completion, a similar result was obtained but with a regularizer that penalizes the matrices with large rows (28). Controlling the norm of each row (absolute value of each entry in the case of rank- 1) is the biggest hurdle in the analysis of matrix completion. In the local convergence analysis of [4] it was proved that GD implicitly regularizes the largest fy-norm of the rows of eтror matrices, showing that explicit regularization is unnecessary. In this paper, we also prove that such an implicit regularization is induced by GD when it starts from a point of small size. We show that the trajectory is close to the fully observed case in both & and lo norms. Thus, the trajectory is confined to the region where has benign geometry, and GD can converge without an explicit regularizer.
We denote vectors with lowercase bold letters and matrices with uppercase bold letters. The components or entries of them are written without bold. We use |1-11g and |1-Il.o to denote Eg and lo- of vectors. respectively, and |1-1|p is used for Frobenius norm of matrices. For any norm ||-I| and two vectors x, y, we let æ + yll = min + yll, 1| - }. Asymptotic dependencies with respect to the matrix dimension are denoted with the standard big O notations, or with the symbols, S. x and Z.
Notations
2

---

2 Problem Formulation
The matrix completion problem aims to reconstruct a low-rank matrix from partially observed entries. In this paper, we focus the case where the ground truth matrix, denoted by M _ is rank-1 positive semidefinite matrix. Thus, the ground truth matrix is decomposed as M = =\=uu u=uu u²' with X > 0 and a unit vector u². We define x" = V\=u" so that M = x==x"_ To follow the standard incoherence assumption, we let | = V and allow fu to be as large as pooy(log nz). We consider a random sampling model that is also symmetric as M Each entry in the diagonal and the upper (or lower) triangular part of M' is independently revealed with probability 0 p 1. We consider the noisy case where Gaussian noise is added to each observation. Formally, we get as an observation the matrix M whose (i, j)th entry is b (Mīj + EEg),, where [ōeglısisján are independent Bernoulli random variables with expectation and [Rolisis/sn are independent Gaussian random variables with the distribution (N0, o²). They are both symmetric in the sense that dij òjz and Eg- Egi for all 1 S S j S n. We use to denote the symmetric matrix whose entries are Enj. We denote the set of observed entries as f2 == {(i,j) dig = 1). and define an operator Pa on matrices that sets the entries not contained in 52 to zero. (e.g. M P E))
To recover the matrix M', we find E R" that minimizes the nonconvex loss function f(x). which is the sum of the squared differences on the observed entries. It is explicitly written as f(x) := +p (ee)) (Zęzz 27=} E,2)² ). We apply vanilla GD to solve the optimization problem starting from a small randomly initialized vector ("), Each entry of ((() is sampled independently from the Gaussian distribution N (o, 1 n. :8), so that the squared norm of x0()) is expected to be $8. The update rule of GD is written
(1+1) = (1) S (a) (0())
P' x (10 a00) + n/Max0
(I)
p
where 7) >> 0 the step size.
We define F' as the loss function f when all entries of M are observed without noise, i.e., F(x)
||| M p. We also define ((()) the trajectory of GD when it is applied F with the same initial point x (0) i... a(t) is the trajectory of the fully observed case. Specificially, it evolves with
(0+1) = (1) VF((() = (0)) - (00) + +/Ma
from the same starting point x (0)
Lastly, we introduce the so-called leave-one-out sequences. These were the main ingredient in controlling the -nom of trajectory in [14] We use them for similar purpose. For each / [x]]
we define an operator P( such that pl (X) is equal to X on the /th row and column, and equal to (x) otherwise. The lth leave-one-out sequence, (f.11) evolves with
x ((1.0) = (1,1) - -1pp!! (1)
(o ((,0 ((.1)))((. (o + (1
for (U.1) (0), where M -p11 (M*) + E(0, and E(U) obtained by zeroing out the Ith row and column of p Pa (E).
3 Main Results
In this section, we present our main results. The first main result concerns the global convergence of GD with small random initialization.
Theorem 3.1. Let us consider a rank-I matrix completion problem that recovers the matrix M*
xt x E RRax such that || 1| = vx- and || = //(<>> l|.- where μ Opoly (log n)). Let the initial point (0)) E " be sampled from the Gaussian distribution (O, 1 1) and (!) be updated with (I). Suppose that a small step size with 1a'-
< 0.1 is used and the sample complexity satisfies n²p 2 1ºn log n. Then, there exists T (1 + o(1)) A log 90
vxa such that
3

---

(0 + x+
2
Vlogn
1
x
2
(4)
max 1giSn
2 (1)
x (R.d)
1 2
Vlogn
1
(6)
1
+ x"
x
(5)
max gg
(t.1 xx
)1
1l
(7)
Vlogn
Vlo
hold at t = T with probability at least 1 1ool/1//ooo// Vlg if a sufficiently small initialization with
V\nn
10
25
80
ua
(8)
log
n mn
is used and the noise satisfies S A' log
Theorem 3.I proves that, starting from a small random initialization, the trajectory of GD eventually enters the local region of the global minimizers = in terms of both lz and & norms. Combined with the result of (14), GD starts to converge linearly to either x' or -x" after t = T as stated in the corollary below.
Corollary 3.2. Suppose that the conditions in Theorem 3.1 1.1ea are satisfied, and let be constant such 1/ VVog n), we have
that 2 S p < Then, with probability at least o(1
x (1)
+
x:'
VVog
p'
x
n
||== ll2.
(9)
(1) + x=*
||=:" Ilao:
(10)
Vlogn
x
p
for all T* StsT= O(n).
The desired global convergence result is provided by Corollary remb 3.T and Corollary 3.2 are order.
3.2 Several remarks about Theo-
Matrix Recovery Suppose a²!) converges global minimum y" of the function f. which is different from =xx In such a case, despite achieving global convergence, the reconstructed matrix y y'y² deviates from the ground truth matrix M However, Theorem 3.1 establishes that (!) converges exclusively to the correct global minima =x", so that the matrix M* is recovered with high probability.
Leave-one-out Sequence To apply the local convergence result of [1 in addition to 4 and 5 the existence of leave-one-out sequences ((.)) hejn satisfying (6) and 7 is required. Leave-one-out sequences also play critical role and appear naturally in the proof of Theorem 3.1
Sample Complexity The required sample complexity for Theorem [.1 to hold is optimal up to a logarithmic factor compared to the statistical lower bound of 2nn log n). We have not done our best to optimize the log factors, and about half of them can be reduced with more delicate analysis. We will discuss this briefly in Section 6
Convergence Time Considering that 3 is at most polynomial in (due to the lower bound of ( only O (logn) n) iterations are required for GD to enter the local region. It takes (llg(()) )) more Iterations to achieve e-accuracy in the local region, the total iteration complexity is given by O(log m) + O(lo(()))
Initialization Size Although small initialization provides good geometry to GD, larger initial- ization is preferred because the convergence time, T is inversely proportional to Bg. When the sample complexity is optimal, i.e., n²p x n poly(log r²), an upper bound the initialization size given by Theorem 3.1 n ignoring the log factors. However, as more samples are provided, are allowed to use a larger initialization to reduce the convergence time. When the sample complexity satisfies n² x n Itt the bound is n (1=a) ignoring the log factors. The bound becomes nearly constant as approaches 1, namely the fully observed case, and this is consistent with the previous result that small initialization is unnecessary for the fully observed case [18). We also note that the lower bound of (8) is necessary in the proof of Theorem 3.1 since we derive probabilistic bounds for all iterations, and the lower bound limits the maximum number of iterations. However, we can further reduce the lower bound - to n -c for any constant e. > 10 by tuning some constant factors during the proof.

---

Noise Size From the incoherence assumption, the maximum absolute value of entries of M* is bounded by A The condition S A' Vlog in Theorem 3.1 allows the standard deviation of the Gaussian noise be much larger than the maximum entry. It also implies X- V - "V log up so that the upper bounds in Corollary 3.2 are dominated by the first terms at T and they eventually converge to the second terms as t increases.
Estimation Error The current estimation bounds 4 7 are all proportional vlog times the norms of x²" However, if we do not allow the initialization size to grow with the sample complexity, we are able to obtain tighter bounds; we use the fixed initialization size n n- regardless of the sample complexity, in Theorem 3.1. the factor Vlog is improved to vap V and the upper
bound on noise size is also improved to S A" Aup (not being precise on the factors of f and log here). Then, the estimation error in Corollary 3.2 is improved to <ap
to match the result of [4]] which uses spectral initialization. Thus, we have a tradeoff between estimation error and initialization size.
+ x 2/
The next main result concerns the trajectory of GD before it enters the local region. The theorem states that for all é < T", (t) stays close to the fully observed case x(() in both & and foo norm.
Theorem 3.3. Suppose that the conditions of Theorem 3.1 hold, and T is defined as in Theorem 3.1 Then, for all t S TT", we have
(1) -000
(1)
(11)
a0(0)
=00 x
[
(12)
Vlogn.
2
Vlog n
with probability at least o(1/ //l//oogn n).
Trajectory of GD The sequence ((() is linear combination of x (0)) and u (see C.I in the
appendix), and it is easy to analyze how (+)) evolves. By showing that (1()) stays close to z! for all
iterations, we not only show the convergence GD with small initialization as in Theorem 3.1 but
also characterize the exact trajectory that GD follows by Theorem 3.3
Implicit Regularization One can prove that (() is incoherent up to some log factors over all itera-
tions, and from (11) and (2). the incoherence of (f) bounded by that of ())), Thus, Theorem 3.3
shows that the incoherence of (+)) implicitly controlled by GD without any regularizer. This an
improvement over the previous result on the global convergence of GD for matrix completion (28].
where an explicit regularizer was used to control the fox -norm of ((),, although no small initialization was used in that work.
4 Fully Observed Case and Proof Sketch
Before we explain the proof of Theorems 3.] and 3.3 we
describe the trajectory of the fully observed case. We
109
characterize o( with three variables: a, Tu=T= (+))
10
3 |5(0 ||2. and % | |e22/
[|2. where a(1) (
3
u n"uu" z(1), According to the three variables up-
10a
%
dated with
Ōc+1 = (1 (1, + Jā;; 7411 (1 )
10
3 a
10
Locat Region
Phase
Phase II
At / = O, due to random initialization. the initial vector nearly orthogonal u*, and have 0g A and
10
50
100
150
Iteration
%o A Bg = 3g. Also, due the small initialization, the term 3 is ignorable until & becomes sufficiently large, so dee grows exponentially the rate of 1 nd'", while remains still. Thus in the early iterations where (1+1)*))
Figure I: Evolution of the quantities a
3. and 7/ simulated with oo = J Bo.
30 1. X 1, and n 1000.
is still much less than /n, 3, is kept close to its initial
5

---

value Po while the trajectory becomes more parallel to u" as a increases. When (1 ) becomes much larger than vn, the trajectory becomes almost parallel to u' in that 3n âg 7t. Until | (asymptotically) reaches vx we can consider O₂ as increasing at a rate of (1 + x))*) and it takes vlogn"
about 1og(1++)))) log v steps reach this point. After that, can longer ignore the term ny.3. Ao
and ā increases slower rate as Br increases. We can show that o6 becomes sufficiently close to X within Olog log additional iterations, as stated in the following lemma.
Lemma 4.1. Let T2 be the largest such that 3 64 lo Art T2 +
6 6 Blogloge we have
log (og
8 (1-111))) Iogm)
Finally, local convergence to u* occurs in that cr approaches X and 7/2 decreases exponentially with the rate (1 n)*)). The actual behavior of quantities 04, Be, are plotted in Figure
We define the iterates before (1 + + reaches
Vup vnn within some logarithmic factors, as Phase I,
and the next iterates before 3 reaches X (1 log x as Phase II. Different techniques are used for
_ So from each phase to prove that (*) stays close to (+)), At the end of Phase I, ā is increased to <mp its initial scale - Bo. but is still not dominant over 3g. Therefore, the magnitudes of both x+() and (+) are kept close to 3o throughout Phase I, and we take advantage of the small random initialization to show that the deviation of (t( from (+) does not increase much, and is kept at v up times the
norms of x (1) In Phase II, we show that (1) (1) expands at a rate of at most (1 + m)²*). Since the norms of (*) also grows at rate of (1 +)²) during most of Phase II, the norms of (t)) ((()
remain negligible compared to those of (t) The next two sections give the main lemmas of Phase I
and II, respectively, which used to prove Theorems 3.1 and 3.3
For visual representation of the
results in the following two sections, please refer to Figure
Phase I: Finding Direction
We provide detailed results and proof ideas for Phase I. Our main goal is analyze the deviation of (tt)) from ( First, if we look the update equations 1 and ( the second term is proportional to
the third power of || []xz I! while the other terms depend linearly on [|x](t) ll. Thus, the second term
almost negligible due to the small initialization. Without the second terms, the difference between
(t) and (()) at
is 1/( MM ()) From concentration inequalities, one can see that the &
and Eo norms of 17( ( M (0) are about Vup times smaller than those of (1).
rate of (1 (A*) in the worst where x!!) ((()) is parallel to u*. In such case, the norms of (1) a(() would be larger than those of ((() at the end of Phase since those of (t)) remain still in Phase I. However, we overcome this problem by proving that the bounds grow at most polynomially with
Due to the third terms of 1 and 2 the norms of (+) x(t) can grow exponentially
respect to and since is at most (log n),, the bounds remain times smaller than the norms of mp
(((() up to logarithmic factors throughout Phase I.
Lemma 5.1. Let Ti be the largest such that (1 nx S log Theorem
Vn. Under the conditions of 3.1 with probability least o(1 /lg n), , for all Tú we have
up
(0) -000
<
log np
Bot,
(13)
(1)
1 log 2 np
Bo f2
(14)
vn
Ti is defined to be the end of Phase I. Lemma 5.1 proves Theorem 3.3 for Phase
We will first demonstrate how obtain the f-rmrrm bound of Lemma define a sequence ((1) that is updated as
Proof of 13
5.1
Let us
(1+1) 2 n =
1 + mM))(
20) (0)
(15)

---

Phase
Phase
Phase
X
80
80 4/90
A/-
(1)
x
xx
(x.1)) 11
/pp
Vlog
Vlog m
Vldg
30
(1)
Ldg
Ing loy
||20(0 101
VR
u
(x(0)
2
(1.0)
par12
part3
local
Iteration
T1
Iteration
Ti
T1
Iteration
T
(a)
(b)
(c)
Figure 2: An illustrative description of trajectory of various quantities compared to the norms of ( on logarithmic scales. Arrows between lines represent the ratio between them. The quantities depicted are not precise, and only the key factors are shown for simplicity.
(a) In Phase I, || T
increases linearly and [|x((() 1 increases exponentially with the rate of (1 + m)>)). They have the same scale at the end of Phase I. (b) In Phase I, even if the u* component of xz 2t.1)) grows exponentially, it remains almost orthogonal to u throughout the phase. (c) Phase II is divided into
three parts according to the growth speed of (+) and xx()) T()) The ratio between them at the start and the end of each part is described, and it is at most vlogn in Phase II.
Note that the norm of (+() is used in the second term of 15 The update equation of E(t) differs from (0()) in the third term and from (1) in the second term. We use x(t) as a proxy for bounding
||x((t) " We first show that || - | grows at most linearly with respect to t.
Lemma 5.2. With probability at least 1 - o(1/ o01///olgg n). for all t S Ti, we have
|| - 11
log
Bot.
(16)
np
The proof of this lemma is based the fact that (()) is product of x and matrix polynomial of I and M while ((() is product between (9) and matrix polynomial of I and M We prove the lemma by comparing the two matrix polynomials. We remark that Lemma 5.2 holds regardless of the small initialization, but relies on the randomness of (0).
Since (f) and (+)) differ only in the second term, their initial difference is proportional to B8. More precisely, it is 38 We show that the difference grows exponentially rate of (1 + n)²*).
Vap
Lemma 5.3. If 14 holds for all < Tı. we have
(0)
100 ||
- X
3 log n
(1 1/1")'333
(17)
np
for all t S Ti with probability at least 1 - o(1/ Vlg n).
The upper bound in (17) becomes smaller than that of (16) + '72""'83 S
p 2 n. One can
check that this condition is satisfied from the definition of T; given in Lemmal [.] and the bound on the initialization size
8 Thus, [3 is proved by (16) and (17).
We control the ith component of (t) x()) using the ith leave-one-out sequence. Leave-one-out sequences have two important properties. First, because they are defined without only one row/column, they are extremely close to (0) and = 1, ||ax(0) (t..)) [|, is about /ap / Second, the Ith component of /th leave-one-out sequence evolves similarly to that of ((()) and easy to analyze. With these two properties, bound the /th component of (1) T as
Proof of 14)
&
(1()) T0)) (0( x (t.))
+ (1.1) xz10 )
(18)

---

We claim that both ||x(() - x (1.10) l1 and (x(1.)) - x(0),| increase at most polynomially with respect
to from the initial scale
8o /np vn
Lemma 5.4. With probability at least 1 - o11/vlog VVoggn,,, n), for all t 1 T1, we have
|0 - 11 2 20000
log" n
80 L (19) Vn
( (allh)) - - 2
11 log 2 n So 1² (20)
"V
np
np
As explained for (²) x((), due to the third terms of ( and 3 x((t) xtt.l) can also grow
exponentially the rate of (1 + +)²² in the worst case where x1 (f.1) is parallel to u*. This
contradicts our result (19) that ||x(() 1 =(th")|| grows only linearly. We show that x(t) (t.))
remains nearly orthogonal to uz in Phase I, and thus the worst case does not occur.
Lemma 5.5. For all I E [ni] and S Tí, we have
(1)) (xx(0) - 2!l.i)/ S
1 log" n
(1 + y
np
with probability at least 1 o(1/ Vll//olo/) n), where ()) is the first eigenvector of M (1)
Note that u is almost parallel to u² (see Lemma A.5 in the appendix). The u component of (+) - (t..l) is initialized to the order of yupi En which is 1 times smaller than [x(1) x+t.0) || /n
Although it is increased exponentially, from the definition of Ti, the ( component remains much smaller than (x( x((.D
[|, in Phase I.
One can see that (xx -(0) increases by |ax(1) 2 ||2 | at each step, and summing
the bound (13) up to f gives (20) Finally, (14) is obtained by putting (19) and (20) into (18)
6 Phase II: Expansion
In the next phase, we show that the bounds obtained in Phase are increased at rate of (1 + +))).
Lemma 6.1. Let T2 be the largest t such that 33 S X (1- logn) Then, for all T₃ < t < T2, we
1
have
log3
x1))
S M1
B1 + -7("))=-)
(21)
log n 30 (1 + -)
x (1) x (t,]
S
(22)
np
vn.
423 log 8 n 3o
(0()) x0(0)
x
(1 + 1//
(23)
np
Vn
( (x0((.)) - x $
1 log
n G0
(1 + -
(24)
np
Vn
with probability at least 1 o(1/v (/11//lo// VVvo n).
T2 is defined the end of Phase II. We will explain how Lemma 6.1 leads to Theorem 3.3 in Phase II. Let us first focus on (1 and (IT). We can divide Phase II into three parts according to the behavior of
[0 2. First, ||=00 2 is kept close to 3o until (1 - m7>*) becomes /n, or (1 + 17λ )o becomes /mp. In this part, although the bounds increase exponentially with the rate of (1 + m7²"), the factor
vap. which was already present in 11 of Phase I, compensates for this increase. At the end of the
first part, ||x(() (+) |l, is smaller than (
1g by some log factors. Next, || || grows at the rate V Since both (e((()) T and [ increase with (1 + +**),
of (1 (1*) until it reaches 8ylogn
8

---

10
10
1.4
0.01
10
10
1.2
0.02
10
10-
1.0
10
10
0.8
0.04
10
10
0.6
10
|
10-
10
0
0.4
10a
2/
1x
10
10
210
0.2
10-1
10-
0
150
200
250
10t1
10-
10 10 10
Iteration
Iteration
Initialization Size
(a)
(b)
(c)
Figure 3: (a) Evolution of the quantities |u" (0) and ||a:(0) ||2, which behave similarly to ã₁ and Be, respectively, and ||x(() + x=112, which shows local convergence. (b) Comparison between the norms of (*) and (+)) (t)) (c) Convergence of GD with respect to the initialization size and sampling
probability, ||x((1) + x= 2|2 was measured at [gg(++AA*] log v + 100 and averaged over 1000 trials.
Bo
the ratio between them is maintained in the second part. Finally, in the remaining iterations, ||>00|| increases with (1 n) m7a") at each step, and the increment becomes smaller as it converges to vx Thus, in the first part, ||x((0) - x ||2 increases faster than ||x((1 2 However, from Lemma 4.1 the length of this part is (log n.). and the ratio between ||x((0 x(t)
|| and ||ā( increases only by log" n. We prove that the log factors already present at the end of the second part compensate this, and finally (IT) holds for all t in Phase A more delicate analysis may prove that [x(* (x()))(()))) I12 grows the same rate as ||=(() l/2 in the third part, and this will reduce the required sample complexity by at most log n. A similar argument can be used to prove that the bounds for (0) - (()) (x((0) (t.1) and (x(t..)) - (())² are smaller than ||((0) by some log
factors throughout Phase II.
At the end of Phase II, ((t) is very close to + in both & and t. norms (see Corollary C.3 in the appendix), so one can replace a(() of Lemma 6.1 with +x" to prove (4 to 7 of Theo- rem 3.1 Hence, we can let T T2, and as explained in Section Tg approximately given by
(1+ log A + (log lo.
Be
7 Simulation
In this section, we present some simulation results that support our theoretical findings.
Trajectory of GD With the dimension n 5000, we constructed the ground truth vector u by sampling it from the Gaussian distribution N(O, 1 I and normalizing
have unit norm. We let = 1 so that the matrix M is given by u*u* and we randomly sampled the matrix symmetrically with a sampling rate of p 0.1 and Gaussian noise of 0.1 The initialization size was set to S - and step size of 0.1 was used for GD. Figure 3 (a) and (b) represent
trial of the experiment, but similar graphs were obtained in each repetition of the experiment. The evolution of some important quantities such as ||x || and |u=
( (T()) is shown in Figure ((a). As in the
fully observed case, the signal component |u" (+)) increases the the rate of (1 ma²) until it
approaches v and a local convergence to xx occurs, where ||x-(() - x a*1|2 decreases exponentially and saturates at the level determined by the noise size In Figure (b), we describe the deviation of
(+) from (1)) in both f2 and fox norms. The solid lines represent the norms of (n( and the dotted
lines represent those of (4) - (4)), We can see that there is gap between the solid and the dotted
lines during the whole iterations. Thus, (+)) stays close to the trajectory of the fully observed case, as we proved in Theorem 3.3
Small Initialization In the next experiment, we investigated the importance small initialization for the convergence of GD. We used the same conditions in the previous experiment except

---

500. We measured ||x(*) = =x11, att= loa(I-ux~} log vi-n + 100 and averaged it over 1000 trials. We repeated the experiment while changing the initialization size from 10 to 10-9 and the sampling probability from 0.01 0.04. The result is summarized in Figure c). For all sampling probabilities, the small initialization improves the convergence of GD. Also, the performance starts to saturate at much larger initialization sizes as the sampling probability increases, and this is consistent with our finding (8) that a larger initialization is possible as more samples are available.
8 Discussion
In this paper, we showed that for rank-1 symmetric ma- trix completion with l2 loss, GI can converge to the ground truth starting from small random initialization. Ignoring log factors, the bound the initialization size is n when the optimal poly(log n) samples are pro- vided, and the bound becomes larger as more samples provided. The result is interesting because the loss function does not have global benign geometry if no reg- ularizer is applied. Our result does not any explicit regularizer and relies only on the implicit regularizing effect of GD.
10
10
10-1
10-
10a
10
ex(Xi))
|X -x-1a
ex(x))
|X
10-
The most important future work is an extension to the rank-r case. Suppose that M is rank-r matrix and its eigendeconpositionn is given by U--*U*T X X*x*T, where Σ- diag(Aī. x2) and X*
10
100
150 200
350 400
Iteration
Figure 4: Trajectory of GD obtained for rank-3 matrix with non-zero eigenvalues 1, 0.0.75, 0.5. The same parameters were used as in Figure 3
- Then, the trajectory of GD becomes an n X matrix ((), which is updated
X ((+1) x (10_2 "P 100__pn x
X
X (1) +
p
Each entry of (0) sampled independently from the Gaussian distribution N (0, ())) as in the rank-1 case.
An instance of (t) is shown in Figure 4 The same conditions in Figure 3 are used, except that the ground truth matrix is a rank-3 matrix with non-zero eigenvalues 1, 0.75, 0.5. The singular values of (1) behave similarly to [|x 2 in the rank-1 case. the early iterations, where the orthogonal components dominate, the singular values stay close to their initial scale Bu. After that, each singular
value o, (x(1) increases at a rate of (1 + myλt) and saturates at vXP. We use | Y to denote
the Frobenius norm between X and under best rotational alignment. ||x(() X n. decreases
exponentially and saturates at the level determined by the noise size after all singular values have
saturated, as local convergence begins.
To extend the results of the rank-1 I case, need to show that ||x(0) - x || remains much smaller
than || |xx() throughout the iterations, where ( is the trajectory of the fully observed case. Before (x)()) saturates around / /A,, it behaves similarly to
||x(*) (()) [|2 of the rank-1 case,
i.e., it expands at rate of (1 + m)Aī) along with [+) after the early iterations. However, because each singular value grows a different rate, different phenomenon is observed for the rank-r case.
|| and || do not increase much. Our current theory can only show that X X increases at rate less than (1 + 11++ j., and in order for (x()) X to remain much smaller than |X ||p- additional sample complexity is required to compensate for the exponential increases. Therefore, we expect that the convergence of GD for the case of rank-r can be proved with the techniques developed in this paper if n ((=-)( poly (r, r, log n) samples are provided, where x = N/ is the condition number. Nevertheless, whether GD can converge with the optimal poly (1, log n) samples for the rank-r matrix completion problem remains an open problem.
During the iterations before 0z+1 (X(1) saturates after (1)) does, both ( (()]
|x(0|||
10

---

Acknowledgments and Disclosure of Funding
This research was supported by the National Research Foundation of Korea under grant 002RICIC11008539
References
[1] Y. Chen, Y. Chi, J. Fan, and C. Ma, "Gradient descent with random initialization: Fast global convergence for nonconvex phase retrieval," Mathematical Programming, vol. 176, no. 1-2. pp. 5-37, 2019.
[2] A. Ahmed, B. Recht, and J. Romberg, "Blind deconvolution using convex programming." IEEE IEEE Transactions on Information Theory. vol. 60, no. 3. pp. 1711-1732, 2014.
[3] S. Tu, R. Boczar, M. Simchowitz, M. Soltanolkotabi, and B. Recht, "Low-rank solutions of linear matrix equations via procrustes flow," in International Conference on Machine Learning, pp. 964-973, 2016.
[4] E. J. Candès and B. Recht, "Exact matrix completion via convex optimization," Foundations of Computational Mathematics, vol. 9, no. 6, pp. 717-772, 2009.
[5] D. F. Gleich and L.-h. Lim, "Rank aggregation via nuclear norm minimization," in Proceedings of the 17th ACM international conference on Knowledge discovery and data mining, pp. 60-68, ACM, 2011.
[6] E. J. Candès, X. Li, Y. Ma, and J. Wright, "Robust principal component analysis?," Journal of the ACM, vol. 58, no. 3, pp. 11:1-11:37, 2011.
[7] Y. Hu, X. Liu, and M. Jacob, "A generalized structured low-rank matrix completion algorithm for mr image recovery," IEEE Transactions on Medical Imaging, vol. 38, no. 8, pp. 1841-1851, 2019.
[8] Y. Chi, M. Lu, and Y. Chen, "Nonconvex optimization meets low-rank matrix factorization: An overview," IEEE Transactions on Signal Processing, vol. 67, no. 20, pp. 5239-5269, 2019.
"The [9] E. J. Candès and T. "The power of convex relaxation: Near-optimal matrix completion,"
IEEE Transactions on Information Theory, vol. 56, no. 5, pp. 2053-2080, 2010.
[10] R. H. Keshavan, A. Montanari, and S. Oh, "Matrix completion from few entries," IEEE Transactions on Information Theory. vol. 56, no. 6, pp. 2980-29909 2010.
[11] Jain, P. Netrapalli, and Sanghavi, "Low-rank waw-rank matrix completion using alternating mini- mization," " in Proceedings of the forty-fifth annual ACM symposium Theory of computing, pp. 665,674, ACM, 2013.
[12] Y. Chen and M. Wainwright, "Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees," arXiv preprint arXiv:1509.000 03025, 2015.
[13] R. Sun and Z.-Q. Luo, "Guaranteed matrix completion via non-convex factorization," IEEE Transactions on Information Theory, vol. 62, no. 11, pp. 6535-6579, 2016.
[14] C. Ma, K. Wang. Y. Chi, and Y. Chen, "Implicit regularization nonconvex statistical esti- mation: Gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution," Foundations of Computational Mathematics, vol. 20, no. 3, pp. 451-632, 2020.
[15] Chen, D. Liu, and X. Li, "Nonconvex rectangular matrix completion via gradient descent without 2, regularization," IEEE Transactions Information Theory, vol. 66, no. 9, pp. 5806- 5841, 2020.
[16] Du, C. Jin, J. D. Lee, M. I. Jordan, A. Singh, and B. Poczos, "Gradient descent can take exponential time to escape saddle points." in Advances in Neural Information Processing Systems, 2017.
[17] Y. Li, T. Ma, and H. Zhang, "Algorithmic regularization per-paaameterizee matrix sensing and neural networks with quadratic activations," in Conference on Learning Theory, pp. 2-47, 2018.
[18] Ye and S. S. Du, "Global convergence of gradient descent for asymmetric low-rank matrix factorization," in Advances in Neural Information Processing Systems, pp. 1429-1439, 2021.

---

[19] S. Du, J. Lee, H. Li, L. Wang, and X. Zhai, "Gradient descent finds global minima of deep neural networks," in International Conference on Machine Learning, pp. 1675-1685, 2019.
[20] Y. Ma, A. Olshevsky, C. Szepesvari, and V. Saligrama, "Gradient descent for sparse rank- one matrix completion for crowd-sourced aggregation of spansely interacting workers," in International Conference Machine Learning, pp. 3335-3344, 2018.
[21] Q. Ma and A. Olshevsky, "Adversarial crowdsoureing through robust rank-one matrix comple- tion," Advances in Neural Information Processing Systems, pp. 21841-21852 2020.
[22] S. Gunasekar, E. Woodworth, S. Bhojanapalli, B. Neyshabur, and N. Srebro, "Implicit regularization in matrix factorization," in Advances in Neural Information Processing Systems, 2017.
[23] D. Stöger and M. Soltanolkotabi, "Small random initialization is akin spectral learning: Opti- mization and generalization guarantees for overparameterized low-rank matrix reconstruction," Advances in Neural Information Processing Systems, pp. 2383 1-23843,, 2021.
[24] S. Arora, N. Cohen, W. Hu, and Y. Luo, "Implicit regularization in deep matrix factorization," in Advances in Neural Information Processing Systems, pp. 7413-7424, 2019.
[25] N. Razin and N. Cohen, "Implicit regularization in deep learning may not be explainable by norms," in Advances in Neural Information Processing Systems, pp. 21174-21 11177 2020.
[26] Z. Li, Y. Luo, and K. L. Lyu, "Towards resolving the implicit bias of gradient descent for matrix factorization: Greedy low-rank learning," in In International Conference on Learning Representations, 2021.
[27] S. Bhojanapalli, B. Neyshabur, and N. Srebro, "Global optimality of local search for low rank matrix recovery," in Advances in Neural Information Processing Systems, 2016.
[28] R. Ge, J. D. Lee, and T. Ma, "Matrix completion has no spurious local minimum," in Advances in Neural Information Processing Systems, 2016.
12

---

Detailed proofs for the results explained in the main text are provided in this appendix. We say that an event happens with high probability if happens with probability least 1 मo for a constant C 0 and C' can be made arbitrary large by controlling constant factors. A union poly(n) number of events that happens with high probability still happens with high probability. For matrix A, we denote the spectral norm by |||] and the maximum absolute value of entries by || Also, the largest é2 norm of rows of A is denoted as ||
A Spectral Analysis
We introduce some spectral bounds related random sampling and Gaussian noise. Lemma A.I. Ifn2p 2 n log have
Pa(M)) M
S X* VV
log n
rep
with high probability. Lemma A.2. If n 2 pm log for all 1 E [m), we have
Pa p (M*)
1 p
(M
1 V. mp
S 5.x
with high probability.
Lemma A.3. 1f Z n log" n, we have
- Pa(E) E)
Sav n
with high probability.
Note that Lemma A.3 also implies that ||
|
S o / for all 1 E [n]] with high probability.
Combined with the condition I A'M Vlogn, ni we have
Pa
(E)
S x u
logn np
|
X
log n np
for all I E [m]. Proofs for Lemmas 12 for the proof of Lemma A.3
A.1
and A.2
are provided Appendix
Check Lemma 11 of
Next, we state bounds on the eigenvalues of M and ( The first eigenvalues of M and M are denoted as X and (1),, respectively. The following lemma is derived from Lemmas A.1 and A.2 with Weyl's Theorem.
Lemma A.4. n Z pm log we have
log n np
AX X 1
(A.1)
1100 x²
log m np
(A.2)
for all E [n] with high probability.
Lastly, Lemmas A.I and with Davis-Kahan Theorem give the following lemma.
Lemma A.5. If Z um log n, we have
(1))
u 11 S v1
log n
np
for all l E [ni] with high probability.
13

---

B Initialization
In this section, we introduce some properties that the initialization vector x (0) satisfies. Recall that each entry of a(()) sampled from from (0, (%) independently. We use H denote the perturbation M M
Lemma B.1. The initialization vector (0) satisfies
3 2
30
x
(0)
S
80
(B.1)
with probability at least en/32 and
(0)
2
log n
Bo
(B.2)
VTi
30 Vn
u²1
H (0)
< 2v log n
H
vs S 30 log n,
(B.3)
with probability at least 1 1-1
30
It also satisfies
n
1 Bu
S 2 T (0)
(B.4)
Vlog n vn
with probability at least 2y/og
Proof. To bound |=:10||| 2! we use the following basic concentration inequality that holds for i.i.d.
standard normal variables (X:)semm)
X?
1
2t t
S
2e
nn?
If put 1. with probability least 1 nn/32 have
1
(U) 2
3 %
%
and this implies B.I
For centered Gaussian random variable with standard deviation σ,, we have
PI
S 2.?
Hence, an entry of (0) is less than 2/log n V
fo with probability at least 1 _ and all entries
of (0) are less than 2 n Po with probability at least 1. u- H follows a centered vn
Gaussian distribution with standard deviation HH'"lll 1l2 S |||||" for all s, and (B.3) holds
with probability at least 10 n n²
For random variable X that is sampled from N(1 o²), we have
t
P|X < 1] S
22
Hence, we have
3o
< u TT (0)
Mog
Vn
with probability at least
2yTog
Lemma B.
implies that the u' component of (0) is in the range
3o S u T 10)
30 Vni
< 2 log
(B.5)
Vogn vn
14

---

Lemma B.2. We have
|ax!0) + bu" 1ua11 2
1 vn
(1a|30 + 1b11
(B.6)
for all a, with probability at least exp(
1ap(-21) 2p
Proof. The probability that an entry of (0 is less than & bounded by '25" Without loss of V generality, let us assume that all entries of u" are not negative and a, 2 0. There are at least 2
entries of u that are larger than Vn For such entries, the probability that all entries of (0) less
than 8u is bounded by v
exp 2yp
Hence, for at least one position, both entries of (0)
and u larger than
8o vn
and
respectively, with probability at least exp( 2y
vn
In the following sections, assume that we given initialization vector x (0) that satisfies BB.
to B.6
C Fully Observed Case
We provide some lemmas related to ((()) in this section. We first note that ((()) is explicitly written as
II 20 (0)
II m/32 r)d"((" x (0))" = (0) B( (C.1)
Let us define T3 as the last such that B3 S 64 logg We claim that T3. S Then, for all t S Ty, we have
64 64gog and prove this later. n
1 (1 (1+n29)
< II 13
S (1
(C.2)
<
n
because
T2
1 + nT - n33
T
n
5dlogn Dx
1
II
II
33
1+ TJ²*
64 log n
1. Note that the upper bounds in (C.2) hold even if T2.
04 log n
From C.2 we have the approximation ((t) ~ (0)
+ (1 + 71 (0)) for all S Tÿ and
the fo-m of (() is also approximately given by (I+ (1+d2") 30. The form is about +
v
times smaller than the norno We make this observation rigorous with the following lemma.
Lemma C.1. For all t < T% we have
[1+ (1 + n2-)1) (1
1+ (1 + m12)0
Bu < [00)
s 22/log logn
30.
8 Vlggn
Vn
vn
1
(1 + nd*
3o Vn
< [
< 22 log
1 (1 + (1+))*
Bo
4 logn
Vn
Proof. For brevity, les us drop the superscript (t) and write ã = Ax + Bu= For the upper bounds, we may use the triangle inequality
Axx + Bu"
A 00 + |B|||**|
15

---

If we use ( and C.2 we get the upper bounds for A and B. We have ||z || - 25o by (B.1)
and the foo norm of x is controlled through (B2.. These finish the proof for the upper bounds.
From the definition of B, we have Buu*1 x:(0)
2 0, and
Ax (0) = Bu
A²
a (0)
+ B + -2AA(uu x()))
2 12
(
+ B
1
x
+ [1B
4
B.1 and (B.4) together with the lower bound in (C.2 give the desired lower bound for +
The
2
lower bound Ior loo -norm is directly implied from Lemma B.2 together with B.4 and C.2
With Lemma
we have
(1 + y
(1 + y2
A
3o S
1+
3o $
Vlogn
Vn
8 Vlog n
vn
8 8/log n
and thus
1 log(1 m)**)
vxnn
11 llg
64 n 1/
T S
log
log(1 +1)aa)
For / S Ti where (1 + n2-) is not big, the bounds in Lemma
C.1
are simplified to
Bu 5
(()
S Vlog nB.
(C.3)
v log n
Bo
Bu
(1)
S
/lg n
(C.4)
Vlog n vn
vn
After ((()) becomes almost parallel to u² and before Ty, we could approximate 3, as increasing with the rate (1 )) However, after Tž. this approximation is invalid, and 3 grows at slower rate as it increases and it eventually converges v\*. How much iterations will be required for reach
V lug after Tg? With Lemma C.2 we will prove that O(log log n.) iterations are required
after TV
Lemma C.2. Arl T3 log log n
TnAr) have 3
X (1
Tog 72
Proof. From the decomposition
we have
(0)
B(O)
5
(0)
u²
x (0)
B(t)
A(1)
u
T (0)
<
x (0)
and thus
A*
0tt
3e 5 2 x (
(C.5)
3 log"
holds for l. Because
for all > Ty C.5 implies that 3, well approximated by a Hence, we will focus on og, which is an increasing sequence that evolves with
160
22
log x
ā (1 - m ))))aa
For all > 1. let N₁ be the last such that A 0 2 Then, we have
x" N e
x N1+1
(C.6)
16

---

Let i 2 2. For all N < <tsA N,
01+1
7/**
7
1
1//3 + y/ = 1 + n/* - -x2) n( 8 2 1 +
2 1 + 0.99
e²
log n
of
We used
(C.5)
(..6 and the fact that Oity Be S v for all t. This implies
+ 0.99 7
Ni-N-1-1
2N NN..
From the lower and upper bounds provided by
C.6 have
1 0.99 77
N.-N.-111
V 1 e
ei-1
1 - 0.99 n
c²
ei11
ef1
<
e-1l
e-
Taking log on both sides and using the inequality get
L < log(1 + x) < x that holds for 0 <
x < 1,
log (1 Φ
N No-1 S 1
S 1+
log + 0.99 et
0.99mA
For t S N1, we have
ăx+1 āt
2 1 + 0.09 7
and thus
V 1 2a. aN 2
(1+0.99 71-
N1
7/1* No
x+
1 0.99
V
21 log n
Taking log both sides we get
log log
N1 S 3
m/A*
Hence, we have
e
Noog log n+1 +15
1 +
loglog n + N₁ +
0.99m/
e
log lglogr n + log log 7
+ 0.99mA
n +
6log log n
log(1 + ))
but at t = Noog log n+1 + 1, it holds that
1"
1
elog n
and we have
1
x
log n
as desired. Note that Be is also an increasing sequence as Ct..
is implied from Lemma C.2 that T2 5
Log(1+yAAT] log A 6log logn (1+o(1)) nx log V log(++nA*]
The following corollary shows that (t) is sufficiently close to xx at = T2. Corollary C.3. Art T3. we have
min [00)
x
2
(1))
+
x
2
<
v logn
| 22lll2
(C.7)
min {|
|
x
(2)
xx
|| llao
(C.8)
/
Vogn
17

---

Proof. When B > 0, from the decomposition
x (t) x== = (0
+ +BB - -B:)u* + (3: - V\+)u",
we have
V
2
(t) 00111 2 (0)
x 112-
Vlog
Vlogn
vlog n
For the cases ((t) < 0 and -nom, we may use similar technique.
D Phase
D.1
Proof of Lemma 5.2
In this subsection, we provide a proof to the following lemma, which is a formal statement of Lemma 5.2
Lemma D.1. With high probability, there exists a universal constant co > such that
-00 1 /
log
But
(D.1)
mp
for all I. S T1, if. 2 log and the initialization point x satisfies B.
B.6
Proof. Let us rewrite the update equations ② and (15) as
((+11) (I n19 + n (01)
(1++1)
m)3t + nM a(1)
where 3. = | Then, (+) (()) is a product between x (0) and (I, M H)., which is M
matrix polynomial of I, M H, where H M
(I, H) =
[I (1 - (1-m3,)1 + M + nH
II (1- + nMMi) s=1
(D.2)
(1) T = p()) (I, M ())
(D.3)
We classify the terms that appear after expanding the matrix polynomial (() [I, M H) into two types; 1) the terms that contain H but not M 2) the terms that contain both H and M We define p!o (I, H) to be a matrix polynomial of I and H, which is equal to summation of the first type, and it is explicitly written as
plt (I = II (11 ( +H II
s=1
We correspondingly define P(() M H) be summation of the second type, and it is equal to
p! (I, M' H) p (I,M* H) - (I.
For x. E R, we define ((0) (z. 3) as the value that is obtained by substituting x, y instead of I, H, respectively. For example, P( P(
(1, IT n 2n) IT' - n) For x. V R.
p! (z, y, z) is defined in similar manner.
We bound the contribution of each type separately because the triangle inequality gives
(+))
x00 < P (1)
p(0) M,M, .H (o)
+
Every term in ((O) (I, H) is H times constant. We have [ (0) || H x0 and hence with triangle inequality
(I,
p(0) (1, 1)
18

---

If nrpp 2 22n log" n, we can further bound ( (1, H
P (1. H (1
3
+ nl
(1 - 31-)
s=1
7 H
-1
(1-1
1
n7.3?
#=1
7
[H]]
-1
17
11
|| (|lll
-1
exp
1
n1**
2n
||E/||
The third line uses the fact that 8/ < X for all t S Ti. The fourth and fifth lines are derived
from an elementary inequality 1 + x S e" 1 + 2x. which holds for small x > O. Note that
vl H X n PV < from Lemmas A. and A.3 and the fact that Ti S logn. n.
We can decompose every term of second type as a product of n, X3, ut, Hou", u T H')
u H'u" and ut (0)), We describe this with some examples.
(n (1)) n X (H (H*
(u (H= (0))
(1H)"(1M"))) )x (0) = -17 1 (w ()))
)x (0) = = x (u" Hu")("" x (0))
(n) (0)
(0))
The terms Hu and u* H are bounded with
HH' 12 |HI,
H 1 < H|)
(D.4)
and the terms that contain (0) are bounded with (B.3) For every term of second type that includes
$1 times of nM* and 82 times of nH, the bounds (D.4) and (B.3) imply that fg-norm of the term
multiplied by (0) is at most
log n 3u- 22
Hence, similar to the first type, we have
p ( (I. H))
2 < (()) (1, A7, | 1
log n So.
If ff Z log n, we can further bound pb (1, X*, H| as
p300 (1, [H]
(1 n + + + 1/ H|)
II (1-1 + +122) - -110 (1, H())
s=1
8=1
- n + +nd* + n/ H|)
(1 n + +1ン*)
(1 ne + +m
11.32 n |1l -1)
17
< (1+ + + ((1 + 1|| 11)
2m H [1(1 + +
19

---

Combining all, we have
[0100
- 4nl H |
1
log n
(1 + 172"0 Bo
log n
4n/ H 1
1
(1 + 17
80
4 log 22 n
< 4nl H|
1+
30
np
log n nu
S V
Bot
for all S Ti for some constant co > 0f 12f 2 p0
D.2 Proof of Lemmas to
We prove Lemmas 5.3 to 5.3 all together in an inductive manner.
Lemma D.2. Suppose that the initialization point x (0) satisfies B.1 for all I S Tú, we have
B.6
If 2 p nog 22
logn np
(1) x(0)
S 200lu
Sot,
(D.5)
1ra log?
9o 12.
19 (00))
I (3co + cco)
(D.6)
np
Vn
1 log n
(1) 200)
|| I c2(3c0 + +cs + +1
(1 + 7
(D.7)
X+
n2
log2 Bo t
(1))) x (1.00
S c
(D.8)
np
nn"
1 log np
(1 + 1/22)) y) Bu
4 (T) (xx - -s.(1.0))
S sco
(D.9)
n2
13 log 2 n Ba 12
( - =((1 S 30o1
(D.10)
up with high probability, where c22 co Ce are positive constants.
Before we start the proof, we introduce some notations. For x E IR", let us define
|
In
diag diag( :.
| |
|
||حا| is the morm of x estimated with sampling of the ith row. With this notation, we can write the gradient of f as
vf(x)= ||0||||| 1 M
The function is defined as
1 g(x) 1 |Pa(aa'' )|p 4p
and its gradient satisfies
V f(x) Vg(æ) M2 x.
20

---

The Hessian of ((x) is equal to
V'g(z) = - + 2 Pa
The base case f = 0 for induction hypotheses (D.5) to (D.10) trivially hold because all three sequences (t)), ((0), T04) start from the same point. Now, we assume that the hypotheses hold up to the tth iteration and show that they hold at the (t 1)st iteration. For brevity, we drop the superscript (t) from (11), xt..) (0)), a0t) and denote them æ, x ã, 2, respectively. Also, recall that T₁ is defined 1 Toy
to be the last such that (1 + n
Vn. and the magnitude of initialization satisfies np
$8 S X
μ log vi so that there exists constant >> O such that (1 + 7 S V
up 1
X v log
D.7 at (t 1) We first decompose x: (++1) - (++1) as
(t++))
(1++1) (I 7 (x T) - 7 n||م|| æ + 1 جز
.| + M (ar 3) n) ||~||
| x.
(D.11)
With the help of Lemma G.8 we bound the maximum entry of a diagonal matrix We have
||2| 1212120
|
log n
log n |
max m²]
| - n||x
x6 0c
+
|
p
p
1 loo' 3
log" 2 n
log 2
3 (3co + cs)
n
g2.2
3
+
np
np
np
n log 3
2A
( + cz){² +1)
np
if n²'p 2 n log" n. Hence, there exists a universal constant 02 > 0 that independent of L such that
(*)
|a())) ||
1 log n ( + ct))t + 1)
max kE(n]
S 2
2
2,
np
for all t < Tí.
With the decomposition D.II), we have
[o((+ - (
< (1 (1-1)
, n/>0) | Ø112
1)
max (E(m)
|101| -10162 |
1
1
133 log" n
< (1 + , Ø112 + 2 =o2
((3co + tc)tt² + 1).
npp
From A.1
there exists universal constant C3 >> 0 such that 1 Combiing all, for all s S t, we have
nnd +
2 if 2 2m log" log n
(+(+)) 1 < 1 n +
C3 log²
x (3) [(0)
$2 (1dt)a
1
1 log'
(g cz)s² + 1).
x
np
An analysis on the recursive equation
4 log n mp
Te+1= = 1 + n
+
Is +
12 (nd'))
93 ( + cc)ss² + 1), xo = 0,
log" n
2
x-
proves that
[l(+1)) - -((+1)
< <32 + G5 + 1)
1
u log" np
(1 + +
21

---

D.8 at (++1) 1) We decompose (t++1) - (x++1.11 as
x((+1) (1+1.)) (1 n/| (xx xz1)) 2n xx
x
7) /- (v'g(z(T)) (1 2 )) (xr x xd))dr dr
17 Pai ((.) - Pi x (t.1)) (z(h1))) (0 x(111)
p
+ 17 100 20 " 2 1T (x((0) (((1))) tn MM 200 2 u (xx (1.)
1 P -P (P(((M))) with +n Pp(())) E(!)
x (1.)))
+ 1)
p
where (T) (1)
+ 7(x 1)) 1 is easily bounded by
|0 2 | x (1))
S 3 x 10 22
np
x
V
log
26
n
n
2
From Lemma G.10 and (.44) for all 0 S S 1, we have
V'g(x - ||
+ 200 ) ||| [n|l=((F) (
[ loo)) +
log
30
Ttp
(D.12)
From the definition of (T)), we have
(T) z
S (1- (1- - 20
+ || - El1oc
- S
p log n
B
Vn
mp
where the last inequality is from the induction hypotheses D.6.. D and the fact that t Ti x log n. Inserting this bound back to (D.12), we get
1 log" 7
V2 gl 11 (7))
[1
200
S
(D.13)
np
which also implies
4 log" 7
1212
22
x1))
S x*
x
np
p22nlg
n
is implied from Lemma G. that
3 2 <
(1)
log n
(1)
log
88 Vn
X
30
np
n log
A bound on 4 follows from the induction hypothesis
D.9 and the spectral bound (A22
n log" n Bo (1 + 17>-)* S x
Vn log 23 n
30
|0/ s 1 n (1) (2)()) (.(111)) $
np
n
np
Vn
The second largest eigenvalue of (1)) is most Lemmas A.I and A.2 we have
| M by Weyl's Theorem, and from
M M.
M
+ M - M 1 X 1 M
log n np
22

---

Hence, we get
1
$ (/
M
M
200000
x0(0 x01)
2
log n2
_01) 2
np
Lastly, we apply Lemmas G.1
and
G.13 to get
log Su np Vn
log n Po
2
O
< x
7
S
M
npp
vn
There exists universal constant C₁ > 0 such that
7 (2| 101, + 1
C4
(1)
log" 2
n2pp 2 p2n log n, and there exists universal constant Cg > 0 such that
log 2 n Bo np vn
" (1 + O1 + 10l, + 110112) s 2 os/4
if nnpp Z pn log n. Combining all, we have
(0(+2) (042.0)
1 ((())
[ 12 log n
C4
|00
(x(0))
1
log" Bo
+ CB/4
mp
n
1+
C1 log n
(0(())
||
1
c5/1
log" 2 Bo
2
np
/n
for all S t. An analysis on the recursive equation
1 C5
log n
8g
Es+1
[
log
2 n
+
2
np /
gives the desired bound
| - ((+11))
<
log 2
Cs
(1+
log" 1
C4
t+1 -
2
1
05/l
log 2 n
np
Vn.
3o
log 30
< cspu
(t (t++ 1),
vn
where we used basic inequalities (1 + x²0a < e ae and az S 2ax which hold if is small and ax is small, respectively.
23

---

D.9 at (++1)
We decompose x (t+1) - (t+ as
x (1+1) (1(+11))
= (x -VV - (0 - ~VF
= (x: (V)(())
(.:0) VV (x!(1))
+ 17 M - (M)
(x - -VVg(()) (w ~nVg((())
(Vg(z(()) {x()
+ (M M + "/ xl1))
II - 4/44 g( (T)) - x) dr 17 ( 1
Pai (2)))(0T) P/ (zx))² 200)) x00)
+ (x )00) + M - -M²) (x - x + (M - M1 x!11
(1 n (x x00) 21jă00"" (x (o--20 x
" I' ( () (7)) (1 + 200 )) (o x0000d
17 Pai x (0T) -Pi (7(21)((07 x1(
+ > (x ()) + 17 [M M1)) - xx)) + 17 (M - MM)) 200)
where x (0) (T) = x1)) + +(x - x Then, we take inner product with u (1) on both sides.
(T (xt+)) _((+1.1)) (1 n 12) () (xc xx11) 2n u (1) aa
x x. (1)
71 /' (1) (V²g(x((T)) - (101 + 20 )) (o x (d)
n (T)
1
-Pon (20) P/ x0 2=()))))))) x())
D
+ +n (0) (xc x))) + (TT (M - M0)) (x - ())
+ 1T (M - Mn) (0))
For the term Q we have
(T re (0))
+ (1 + (1+1))))) / (x)0 (1) 2t x
log
(1+ 'B
n
by Lemma A.5 and thus,
log (1 + nd )) " x x0))
2A
n
2
log n. 88
- VV
(1 n7:114
np
P. Bo
$ X*
npp
24

---

The definition of Phase I was used to bound (1+ (1+a)))) in deriving the last line, We use D.13
to get
2
veg(z(T))-
[| + 2..
x
(1)
2
dr
1 log'
n
log" n 30
B0
np
np vn
up
log
15
n
We apply Lemma G.12
3 to yield
x
(1)
log n
(4)
(1)
x
(1)
p
2
2
p log
n
S
X
1
50
np
ne'n log
22 n n
We divide 4 into two terms that are related to sampling and noise, respectively.
u (T)
p - -
(M*) (x "0)) C)
( (((E)) EE4) (o0 x0)
Then, Cauchy- Seanchy-Schwatz inequality is applied yield
+ S
( - (M²)
u |||||= x0()
11, Pp
E(i) E(
21 1 | x0
Applying Lemmas G.1l and G.13 to the two terms, respectively, we get
1 log"
1 (0
11 log Bo
S X
np
Vn
np n
For the term 5 we decompose it into two terms as for
④
5 - (U)
(1 Pa(M))) - P (M')
(1)
+ (TT
(
Pa((E) -E()) 2000)
pp
Then, apply Lemmas G.12 and G.14 to each term to obtain
3 log n 30
5
np
Combining all, there exists a universal constant C6 > 0 such that
1
log
3
(2 + 2 + 3
2 C61
np
n
n2p Z 12 log n, and there exists a universal constant C7 >> 0 such that
7 S n
+
C7
log²
2
by A.2 if n2p 2 4rn log n. Finally, we have
((T (a(1+1) -
- -((+11)) s (1 11-10 n 1i-n|aa) + m))
-x(0)) (000)))(0)) (x O00
7
10 log 3
Bu
2 co +
np
n
< 1 +
27
(T (xc -x(11)
1
1 log
n 3o
log? m)
C6
np
n
An analysis on the recursive equation
(1+1>* 172
C7
n7*
1 logo
3 n Bo
Z141
+
+
2 co/
2o =
0
log² n
np
gives the bound
(T( (a((t+1) ce(()1))))
1 logo"
(1 n)*))++++ 30
s /
np
25

---

D.10 at (t + 1) We decompose (x(+++1))) 2((+()); as
(0(t+10-5(t1 -(1 -1-11(1113) m|(ā113) (z) +nd""" (z10
+n (اقق - -|
21
and this implies
-0011))=((++))))) x((+))) (1 0 (xx )))1
n xxl)) x 1 10 + 1/|20112
x (0) z
|
From D.5 and D.8
we have
log Bot. up
(0
x01)) -x0
+ 1|0 3 1212 S 3cully V
If n is sufficiently large, we have
# loog n
1 + -
S
for all / < Ti because
nd 1 11 + +122012000 S Snx V 1
log n
m
88 S
V
Hence, we have
(z(0+111) - - (0+1))) 1 (z((e.) - -z(0)); 300
113 log 2
30
Tip
for all s S Finally, we have
lo'o"" n B0
(zo (1+,,1) - (((+1))) s /
Vni Σg
np
log n 30
< 300
(t + 1)²
Vn
np
D.5 at (t + 1)
We can obtain this through the combination of D.7 and Lemma 5.2
(((+)) - [(++3)
< xz ((+1) x((+1)
+ [(++1) (1+1)
1
113 log" n
log n np
<32(300 c3 1)
(1 (1+ +
33 cujf
Bu +
x+
np
3 log" n np
log n2 npp
5 + + 1)
(1 + 22
33 + coly
3o (t + 1)
X
logn n np
< c302(300 + os + 1)lg
30 + cO/y
Bo + 1)
np log" 2
logn Bo + 1)
< 22c0uu np
26

---

D.6 at (t + 1)
The ith component of x (1+11 x((+1) is bounded by
(xx(++1) x((tt))1/ x x (++1) (1+1,1
+ (2 x 1)
(t++1) - x((+1.1)
(x(1+111) - 1)
log 2 8o (t + + 3c01 np
4 loog 30 (t 1)2
vn
up vn
1
logg
Bo
S (3co + +ss)
vn (t 1)2
np
At = Ti Because 71 X log n, it is implied from Lemma D.2 that at Tı, there exists a
constant C7 > 0 such that
log 3 n 07
(2 -5(11
8
np
3 log n 3o S 07
(1) x(1)
np n
(D.14)
[2.(0) x: (11))
log n 3o
S 17/
np vn
( (a((t.)) - -(()),, S vrV
4 log n 3o
np
These bounds serve as base case for the induction of the next part.
E Phase II
This section is mostly devoted to the proof of Lemma E.1 which is formal version of Lemma 6.1
Lemma E.1. Suppose that (D.4) holds at i Ti and the initialization point (0) satisfies
B.
to B.6). Then, for all Ti t S T2. we have
log 3 np
(0(()) -000
< 20744
30 + -)
(E.1)
|20(0) [(10
5 C13
3 log
n 8o
(1 + m/> "(-
(E.2)
np
Vn
(0()) x x(1.)||
s 207
log" 5
Bo
(1 + -
(E.3)
np /n
|( (al(l))) (aall)) - -x("))
307
4 log n
3o
(1 + 111
(E.4)
Vn
np
with high probability, where T2 is the largest t such that B S X (1 logn and 013 0 is constant.
Proof of Theorems
3.1 and 3.3
We first explain how Theorems 3.1 and 3.3 are derived from
Lemmas D.2 and E.
We first focus on (+()
a01 ||z- For t < Ti, from Lemma D.2 and C.3 we
have
(0 xz(() ||,
log 3
1
$ m
30 x
30 S
np
log
Vlogn. n
2
27

---

provided that n²p2 2 lo'n n. For Ti < t S T2, from the definition of T2 and Lemma E.1 we have
90
-000)
-5(0)
2 -
(1 + nAa
log 18
Vn
From the lower bound of Lemma C.1
for all
S T2. we have
(+)
-
1+
(1 + md-
Bo x
(1))
1
(1)
2
log 18
n
vn
log 17
m2
2
Vlog n
Now, for T32 <ts T2. we have
(1 7T²"T²
(1))
-
1
Bo + m7a)1-2
2
log
18
n
24
(22)
(1 M
log 17
For any T3 < < T2, is Lemma C.2 implied from Lemma C.2
that (1 n)*)(-Tz S log n, and
we have [((5)
I | Hence, we get
2
(1))))
1 log
12
||3 S
x(t)
(E.5)
log 27
Vlog
2
and the proof for 11 of Theorem 3.3 is completed. If we combine this with C.7
we are able to
prove 4 of Theorem 3.1
We move on to
[xx(1) z00)
For t < Tı, from Lemma D.2 and (C.4) we have
1 -0()
4 log 8
3u
1
80
00
np
Vn
log
n2
vn
Vlogn n
provided that n 2 n log 10 n. For Ti have
<
Ty. from the definition of Ti and Lemma E.
[ (())
8 (1 +
log n vn
From the lower bound of Lemma
C.I for all I Ty. we have
(1)
201 S
1+ (1 + 3
30
700
log 13
Vn
log 12
log
Now, for T3 < 1 5 T2, if we do the same as before, we get
(1 700
log
12
(1)
(1))
log n
Vlog n
and the proof for 12 of Theorem 3.3 is completed. If we combine this with C..) we are able to prove (5) of Theorem
Going through a similar way with 22 and
24). we can complete the proof of Theorems 3.1 and 3.3
Proof of Lemma E.1 Before we start the proof, we define function G as
1 ||00 x Ip
G(x)
The gradient of G satisfies
Fx)x)= vG(x) - M
Now, assume that the hypotheses hold up the tth iteration and show that they hold at the (L + 1)st iteration. For brevity, we drop the superscript (L) from (0) (t.1), ((()) and denote them as x, x (1), Ø. respectively.
28

---

E.1 at (t ++ 1)
We decompose x ((++)) - [(++1) as
x (t-1) 1) x((+1)
(x: [)))( (ar VF()
(x- VV(())) - -(x vVV((T) + + (M M'
(x ()Vg(=)) ( (V) 1/ (Vg(3) VG( + M' (z 3) + nM Ma
II VVgg((())
77 1 [1 1) H + 11 - + m - -M² ja
(1 I 2n + MM (x- m) 1 [ (V)((((T) ( +
2 )) (a d)
2
[ 2 [1 1) x +n (M- - M'
where x(T)= = + 7(x - X). For the term D we require a bound on
(L n I 21aa + "
we write T as ā,u* + 1. we have ag S x and |ا11| 2 S So. Then, we have
- ,|| | 21ya + 1
(1 π| I + 77^² - 22, 2 T -2n(xx'
0 u u
< (1 y| ( I - 7 - 2 w 2 7 2nI
T..
o, u u
(1 m (2x [ 212 + + 12)
<1+m\ nパ log n
for some universal constant Cg > O. This implics the desired bound
100 1 9
C8 log" n
||:0
2 2|
For all 0 S S 1, we have ||x(())
-
x 0
I |
x bo and the induction hypothesis E.2
gives
(1 + 7/ Bo
o
#
log
13 n
Hence, by Lemma G.10 we have
V ()(((()))
(1 m I 2=x
)|
s
nl|x
x Tillo
(1
+ +1
n log
|
1
12 log n np
88
(1 + m/ 22
+
log
12 n
1
X*
log n
if nn'pp 2 u²n log n because | loo S
p log ni( + To
2o
and (1+ n\+)>>
S v This
3g
gives
1
S X+
x
(E.6)
2
log
12
29

---

For the term 3 we use Lemma G.8
to obtain
log
3
Xr
np
Lastly, the term 4 bounded with
log n np
O
M
M | S X X
|0l1
Combining all, there exists universal constant Cg
0 such that
|0ll, + ||2|2 - n
||0 z112.
log n
log
" (1 3 2 + 11l)) S cap
np
Because ||
< Vlogn, by CC33 and
(0)
112 can grow at rate at most (1 + +)2),, there
exists universal constant 610 > 0 such that
log n
log
ca/4
(1)
S /iuMy
(1 + 2 So.
(E.7)
Hence, for all Ti S t, we have
a (s(+)) - - < 1 n7 (1+
Cg log"
|2010) - -5(0)
clofy
log² n np
(1 + 11A*)=-TT
Bo.
An analysis on the recursive equation
log 2 (1 -
log 3
Ts+1 1 n
n
Cg log n
Hs + /
Bo,
2n, cnp
Bo
np
np
proves that
log n np
(1+1) [
S
207H4
So + 1/14)+1-T7
DI3
at (t + 1)
Similar the proof of D.8 we have the decomposition
x (1+1) x (++1.)) [1-/|=0]
2npa (xx (1))
(V'g(z(0()) (1 + )) (x )d
Pau (200x(011 Pi (= x
p
+ (x= - =0 + n (M - Mx - (1))
( p
-P( (M (1)) +n
PPa(E) EE() E( "
+n
P
p
30

---

where x (T) xz + x)))
Both of the terms ! and 2 can be bounded similar to ! and
2 of x(++1) (2(-1) as
1011 - 1+ m7a* 1+
+
Ci1
(1)
log n
2
| S X
x
log n
2
for some universal constant C11 >
0. For the terms
3 and
(
we use Lemma G.11 1
to obtain
log n
log n
1
3
<
(1)
(1)
S X
p
- 2
P
np vn
log
5
2
X
P1
nip
/n
2
and use Lemma G.13 to obtain
log² n
S X²
vn 2 l
From Lemmas A.1 and A.3 the term 4 is bounded as
1 - M M x= x00) S A
log n np
x
Combining all with E.7 there exists universal constant C12 > 0 such that
10 2 + |01, + |011 1 (1 +++ +
612
||x 2112.
log 2
log" Bo
" (131, | + (11, S c12/11
(1 + 1
np vn
Hence, we have
[2(0+1) (0+1111)
11+ 1
C12
|00 x
+01211
log" So
(1 (1+ (1
2 log n
np vn
for Ti SS5t. An analysis on the recursive equation
log 3 8o
log 8o
#s41
1 [++1>* π/
C12
V.
c12m
(1 + -
oT, enu
log" n
up vn
np
vn
proves that
log"
log*
Go
[((+1) - (0(11)))
2 /
(t + 1 Ti)
+ + ezp
(1 + +11-7+t1-1
np
vn
log 5
80 vn
S S1app
(1 + ()(+)(+1-1
np
holds for some universal constant Cis because T3 Ti S logn.
E.4 at (t 1) We use the same bound
(2 ((+1..1) - ((+1))) s (1 1)]))= (zx()) - 3)/| + m7(211 1|x* 1lace + |
31

---

that was used in the proof of (DI0). From E.1 and E.3 we have
log" n
- - - xx
+ || - 2112 S 3
Po(1 + 1
np
Combined with the fact that X*|/u= + || C14 > such that
S 3X VH. v there exists universal constant
7(A' |ee 1l + ||1ا||||@@111 10 - 2012 S cuu
n logo" Bo (1
np vn
Hence, for all Ti S 8 Stt, we have
1 log" s n 800
(2(0t110)) - {((tt)) s (x/(10) -2(0))))) + cua
(0(0t10)5((0tt)))
up vn (1 + n/
and this implies
(20(+120)- ,((t1))) s c
1 log
80
Σ
(1 +1 ) + V
1
log 8 B0
np
vn
np
Vn
s=
10 log
Bo n
$ V
(1 17d n/
np
E.2 at (t+11 1) (xl(++)) - (((+1))
The /th component of x (++1) ((+11) is bounded by
x x (t+ -x (1+1,)
+ ( - =((+
<
x (t+1) -x (++1,)
+ (c - x((+1))
log
3 n 30
1 log n Bo
< C13/1
(1 + m/1") n + 2071
(1 + n1
np
Vn
np
vn
μ log 8
80
< 307
(1 + -
mp
F Fixed Initialization Size
In Section we claimed that the estimation error is improved to 1 +
a E the initialization
vmp X VV
size is fixed n 1/4 regardless of the sample complexity. We briefly discuss how the proofs should change in such a case. For clear presentation, and log n factors are ignored in this section.
For every bound of Phase I (Lemmas 5.1 to 5.50. /ap
1 is changed to vAp + X. V p.
while allowing
to be as large as A'H Vnp. More importantly, the definition of Phase I is changed to be the largest t such that (1+ n/ < Vn, so it is lengthened by nnp times than before. In the original proof, the obtained at the end of Phase I was increased to poly(log nz during the first
estimation error of part of Phase II. However, if (1 + 77*"' equals vn at the end Phase I, we do not have such a part in Phase II, and the estimation error obtained the end of Phase I is maintained through Phase II.
G Technical Lemmas
We introduce some technical lemmas in this section. Most of them are the results of classical concentration inequalities.
32

---

Theorem G.1 (Matrix Bernstein Inequality). Let {X,} be n x n independent symmetric random matrices. Assume that each random matrix satisfies X; and || almost surely. Then, for all T 2 0, we have
11
Σ x
2T
S nxxp (V+L7/3)
where V = -1,,,
Corollary G.2 (Matrix Bernstein Inequality). Let {X;} } be x n independent symmetric random matrices. Assume that each random matrix satisfies X; and [nn|||X, || L. almost surely. Then, with high probability, we have
Σ X
VVlogg logn logn,
where V -1,,,
Lemma G.3. For any fixed matrix M E Raxx, we have
P M
log
log
M
|| M
P
p
with high probability
Proof. We decompose the matrix into the sum of independent symmetric matrices.
5ij 1)
Milee, +e,e,) + Σ da -1) Mieee
Pa(M) M
We calculate L and V of Corollary
G.2
We have L S |
M 1lc because
8ij (
Mis(ese] + tcze,))
- p
M booot
p
[ p
-1 M
$ M
We also have the following bound on V.
V
Σ
MG Mifeee eiee
S 11 1
p
Hence, Corollary G.2 implies the desired result.
We can prove Lemma A. by applying Lemma G.3 to M and using || 11 A=
We introduce classical Bernstein incquality and the results obtained from it. Theorem G.4 (Bernstein Inequality). Let {X,} be independent random variables. Assume that each random variable satisfies E X; and [Xal S almost surely. Then, for all 2 O, we have
-72/2
P
Σ
X
2
< 2exp
V LT/3
where V - E[3].
Corollary G.5 (Bernstein Inequality). Let {X,} be independent random variables. Assume that each random variable satisfies E X; and [X, S almost surely. Then, with high probability, we have
Σ X, s Vlog n + L logn,
where V = E;
33

---

Lemma G.6. Let and { be independent Bernoulli random variables with expectation p. Then, for any fixed vector a, we have
Σ
Xi
0j
S
log n1
aal2 +
log n2
|
P
p
p
with high probability.
Proof. We can apply Corollary
G.5 with L = gllall
and V =
1-
2
p
Lemma G.7. 1fn2p 2 pm log we have
Pa(Mr))
V
p
2,00
ri
with high probability.
Proof. Let consider f--norm of the ith row of M
| (()a((M))
x u
bejuzz
1
Σ 1 5nguz²
1 +2 | 11
|| 112 +
1|120112
11
p
x=2
log n
A=2
1
np
np
np
The third line follows from Lemma G.6
Proof of Lemma A.2 The spectral norm of symmetric matrix that has nonzero entries only on the 1th row/column is bounded by twice of the norm of its Ith row. Hence,
| PP (M*)
2 (2 Pa(M)))) - (M()))
(
- .MM)
1x 12
+||M*
12
1,,00
S x"
V
ı
np
2,00
where the last inequality follows from Lemma
G.7
Lemma G.8. Let be a vector that is independent from the sampling. Then, if Z n log n, we have
log n
log n p |1
max :E(m]
| - 11 S nllær ull (11=01 + 1111lloo) +
V
| +
p
with very high probability.
Proof. Let us fix and decompose the difference
6ij 1 13.
1
|
13) + Σ
/=1 p
The first term is bounded as
8 (1 - 93)
S x
+ yll 00
Σ
S
n x
111 1| + ylloo
j=1
34

---

and the second term is bounded as
dij p 13
log
log
-1 1
Σ
1
1
p
p
by Lemma G.6
Lemma G.9. Let y be a vector that is independent from the sampling. Then, if 2 n log n, we have
1 Pa yy _
log n y 1
S a||
(l + 11 +
p
with very high probability.
Proof. We have the following sequence of inequalities
- (xxx 7) yy"
-
- Pn
(x
))
-
Pnyyyy) 7)
Pn(yy)) yy |
p
p
p
+ | Pa (ar ) yn
xx
yy
11 p
Ps
(11(11) [11
1 Pn yy
||
y
(1|=||
+ 11
Pa (11
n blog n
S Sn|l Vll 1l + 11 +
where the second line derived from basic inequality ||||| - and the last line follows by applying Lemma G.3 11 and yy
||| that holds for any matrix A,
Lemma G.10. Let y be a vector that is independent from the sampling. Then, iř p Z n log we have
V2 g(x) (111)122. + 2yy ))
S n2|2 - ylllo (1|a=l + 11
log
log
log
1 11ll p
|1
p
p
Proof. This follows directly from Lemmas G.8 and G.9
Let us define an operator Pa, such that an entry of Ps, (X) is equal to that of X if it is contained both in the ith row/column and Ω and otherwise We also define an operator Pa that makes the entries outside the ith row/column zero. Then, we have
1 P - (!') (x)
1 Ps, (x)))
p
p
Also, note that
1 P.(EE E(0
1
P - (E).
p
p
The following lemma also introduced in 14] but include the proof for completeness.
Lemma G.11. Suppose that matrix M and vector independent from sampling of the Ith row/column. If n2p Z nloo n, we have
( Pa (M) - P((M) 0l
log n |0l12 + p
In log n | + V [101l20)
||
(V
p
with high probability.
35

---

Proof. If we consider the contribution of ith term and the other terms separately, we have
(
n j=1
δa
2
Mijus U3
Σ
1)
Ma
p
n
n
2
||
Σ
- 1 vs
|10l
2
1
p
p
i=1
From Lemma G.6
we have
T1
ôtj -
log
log m
Σ
1) 1/
|/00|12
+
1001
p
p
Ø=1
with high probability. Regarding the second term, notice that
δa
2
-
n
8a p
Σ
=
i=1
Lemma G.6 impliss that Ei=1 n with high probability n2p 2 log n. Hence, we have
8 - 1 PPP P
and this finishes the proof.
Lemma G.12. Let M be matrix and be vectors that are independent from sampling of the Ith row/column. Then, if n2p 2 n log n, we have
w (. (M (M) 1LMM-PP((AN)) -PP())
log
log 1200 + 11 a0)
||
||
1/ 1lo0
p
Proof. We can consider the /th row and column separately by
(M) (P((M)
w
p
del -1
(
1
Ma
+
11 Σ
My
M
+
Mayrir
p
p
i
Ez Σ
ōij -1
< ||
20
||00|| oc
1
+
|
Σ
Vj
+
| p
|1ll
|
p
j
If apply Lemma Go the summations, get the desired result.
Lemma G.13. Let E be a symmetric matrix whose upper and on diagonal entries are drawn from Gaussian distribution ((0, o²) independently. Let be a vector that independent from sampling of the lth row and column. Then, nf p222 2 nlog n, we have
1 Ps. 1
log p
Vlog" n
E)
So
(v
|1012
+
V
p
Proof. If we consider the contribution of ith term and the other terms separately, we have
1
- Pa
E
24
+
- |el
8 E
p
j=1
1=1
36

---

For the first term, we will calculate V and L of Corollary G.5 V is calculated as
n
B B(y)) = po 1
To find L, we first note that || Bt looo S a Vlgg with high probability, where Eg, is the Ith of E. Thus, for all j E [n], we have
Bi Eijuy S o /og 1
Corollary G.5
implies that the first term is bounded
1
(v
1 log
v Vlog" 100100
Σ big Big
So
11012 +
(G.1)
p
p
p
For the second term, suffices to bound
1 Σ
8al (F 02)
As before, obtain V and L through
Σ
-
-E
> E
E E1 - 20 Eg + o4] = 20"
i=1
(aa(E) o²) 0² logn.
Corollary G.5 implies that
Σ ba(L 02) $ S0² <02(wuplogg + log m)
1=1
Because Σ du np, we have
Σ
da F2
02
np + nnp log n + log n) S oznp
(G.2)
n2pp 2 n log n. Combining G.1 and G.2). we get the desired bound.
Lemma G.14. Let E be symmetric matrix whose upper and on diagonal entries are drawn from Gaussian distribution (0, independently. Let v, w be vectors that are independent from sampling of the lth row and column. Then, nn 2 n log n, we have
w T (E)o S (v |lo
(1o0p
(1w0lll) wlls + || + Vlog" n | ll
Proof. We can consider the /th row and column separately by
1 1/w0 Pa, 11
EE)ol
Sa Eaws
+
Wi
Seg Eijuy
Öū Envraal
p
p
p
||0||
|
8n Eaww
+
Σ 8ig Biyuy
+ || wolllll/wlllx En]-
p
We bound the two summations similar to with high probability.
G.1 and for the last term, we note that Eul S a log n
37


Reviews:
[{"review_id": "1NxQWPSILT", "reviewer": "Reviewer_ewei", "summary": "This work considers the convergence analyses of gradient descent method for rank-one matrix completion problem. In particular, this work assumes small random initialization, which is relatively relaxed condition compared to existing work. With such assumption, the logarithmic convergence of the gradient descent method has been proved in this work. Also, the impact of the regularization for gradient descent method has been analyzed.", "questions": "- Can you compare the major results about the rank-one matrix completion problem with the following works?\nhttps://arxiv.org/pdf/2008.04988.pdf\nhttps://proceedings.neurips.cc/paper/2020/file/f86890095c957e9b949d11d15f0d0cd5-Paper.pdf", "limitations": "Please see comments above.", "rating": 4, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The motivation of this work is clear and valid, also this work is well-organized. Meanwhile, this work is technically sound, where the proof and related analyses are provided, also some simulations are provided to further support the major results. ", "weaknesses": "- I have concern for the novelty or the contribution of this work. Rank-one matrix completion problem is the simplest problem for matrix completion problems. Also there have constraints for the noise assumption of the revealed entries in this paper. For such cases, there are many efficient methods to deal with, like alternating minimization or projected gradient descent method. For gradient descent method, there also have existing works which have proved its convergence. Though this work provided with relaxed conditions, such contribution may be limited for the optimization and machine learning community, let alone the real problems in industry.\n- The presentation for the proof of the major results can be further improved. For instance, the proof of Lemma 5.1 is separated into two parts at different places, it may be better to combine them together after finishing other proofs.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for the feedback. Please see our response to the reviewer’s question.\n\n>**I have concern for the novelty or the contribution of this work. Rank-one matrix completion problem is the simplest problem for matrix completion problems. Also there have constraints for the noise assumption of the revealed entries in this paper. For such cases, there are many efficient methods to deal with, like alternating minimization or projected gradient descent method. For gradient descent method, there also have existing works which have proved its convergence. Though this work provided with relaxed conditions, such contribution may be limited for the optimization and machine learning community, let alone the real problems in industry.**\n\nThe question of whether the combination of GD with random initialization can effectively solve a specific problem holds significant importance in the field of optimization. Phase retrieval and matrix sensing are one of the low-rank recovery problems, like matrix completion. For those problems, the global convergence of GD from a randomly initialized point has been proved. However, despite its similarity to matrix sensing, no analogous result had been established for matrix completion. The problem remains open especially after the local convergence result [a] published in 2017.\n\nAlthough the rank-one case does not have much impact in itself, it will provide a good starting point for someone who challenges the full problem. Our novel analysis on Phase I provides a good understanding on the dynamics of GD that starts from a small random initializer. We expect that our key lemmas such as Lemmas 5.2 and 5.5 will continue to hold for the general rank-r case in a similar way. For Phase II, we have a difficulty in analyzing the singular values of the trajectory, and it is discussed in Section 8 with some simulation results.\n\nFor the noise model, we followed the standard of many previous works on low-rank recovery, and we do not think it is a strong and restrictive assumption. It is common to model noise with the Gaussian distribution in different engineering fields although it may not be appropriate for some specific problems.\n\n---\n\n>**The presentation for the proof of the major results can be further improved. For instance, the proof of Lemma 5.1 is separated into two parts at different places, it may be better to combine them together after finishing other proofs.**\n\nThe lines from 227 to 243 are all related to the proof of (11), and the lines from 246 to 263 are all related to the proof of (12). They are not separated.\n\n---\n\n>**Can you compare the major results about the rank-one matrix completion problem with the following works? (Rui Liu and Alex Olshevsky, 2020) and (Qianqian Ma and Alex Olshevsky, 2020)**\n\nA special error model was studied in [b]. For some fractional number of rows and columns, the observed matrix is allowed to be corrupted entirely by any order. Based on an algorithm similar to alternating minimization, the corrupted rows and columns are found recursively, and those rows and columns are not used in the estimation of singular vectors. The main theorem gives the required sample complexity as a function of the fraction of corrupted rows and columns, and it is implied from the theorem that at most a fraction of $1 / \\log \\log(n)$ rows can be corrupted.\n\nBecause [b] uses different error model with ours, a direct comparison is difficult. However, our model allows Gaussian noise to be added to every entry of the observed matrix not to some fractional number of entries. Moreover, the variance of Gaussian noise can be as large as $\\sqrt{\\log n}$ times the maximum entry of the ground truth matrix. Our main theorem shows that by increasing the initialization size, convergence time is reduced if more than optimal number of samples ($n \\mathrm{poly} (\\log n)$) are provided. In [b], however, only the necessary and sufficient condition on the sample complexity was analyzed, and how extra samples affect the performance or convergence speed of the algorithm was not provided.\n\n[c] studies the alternating minimization algorithm for rank-1 matrix completion problem and convergence of the algorithm was analyzed. However, both [b] and [c] assume that every entry of the ground truth matrix is positive. We suspect that such an assumption is required to show that singular vectors (x, y) at each round is incoherent. Our result does require such an assumption.\n\nLastly, we would like to mention that the main purpose of this work is not to insist that GD with small random initialization is the best algorithm to use when solving rank-1 matrix completion problem. Our prior interest is at explaning the convergence of GD for nonconvex problems depite the existence of local minima or saddle points, which also gains much attention in machine learning and optimization community in recent years.\n\n---\n\n[a] Cong Ma et al. \"Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution.\"\n\n[b] Q. Ma and A. Olshevsky, “Adversarial Crowdsourcing Through Robust Rank-One Matrix Completion”\n\n[c] R. Liu and A. Olshevsky, \"Asymptotic Convergence Rate of Alternating Minimization for Rank One Matrix Completion\"\n"}, {"review_id": "55BYDMqgOn", "reviewer": "Reviewer_KM6V", "summary": "This paper shows some convergence properties of gradient descent with small random initialization for rank-1 noisy matrix completion. ", "questions": "I have no question at this moment.", "limitations": "This paper does not have potential negative social impact. ", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "This paper uses a new approach (gradient descent with small random initialization) to solve the nonconvex formulation for rank-1 noisy matrix completion. It is shown that the GD trajectory will arrive at a local neighborhood (in both $\\ell_2$ and $\\ell_{\\infty$ norm) of the ground truth within a number of iteration.", "weaknesses": "1. My major concern of this paper is a lack of theoretical novelty. After looking at the results and quickly go through the proof, I believe the proof idea of this paper is similar to that in [1], which focus on a general low-rank matrix sensing problem (we know that the low-rank matrix sensing problem with certain RIP condition has the same population-level loss function as the noisy matrix completion problem). For example, the analysis idea that the GD dynamic is close to a simplified linear evolution system in the initial phase thanks to the small initialization already appeared in [1]. Compared with [1] which works for general low-rank setting, this paper only works for the rank-1 case, which is more restricted. On the other hand, matrix completion problems are known to be more difficult than the matrix sensing problem in the sense that it requires incoherence and $\\ell_{2,\\infty}$ error analysis to show that the empirical loss concentrates around the population counterpart. This difficulty was not encountered in [1]. This paper uses leave-one-out analysis that has been widely used in low-rank estimation literature like [2,3] to track the $\\ell_{\\infty}$ error of the GD trajectory. The analysis does not seems to be challenging, if one is familiar with the above-mentioned literature. If I underestimate the technical novelty of the paper, I hope the authors could clarify and please highlight their technical novelty.\n\n2. I am not satisfied with the convergence guarantees. The estimation error provided by Theorem 3.1 only shows that the output of the proposed algorithm is consistent, namely is $o(1)$. However state-of-the-art results for matrix completion already shows that GD with spectral initialization (which I believe is equivalent to small random initialization in some sense, since the initial phase of the latter algorithm is similar to some form of power method) achieves minimax-optimal estimation error [2]. Could the authors please explain why their analysis leads to looser error bound?\n\n3. In addition, the noise condition in Theorem 3.1 is $\\sqrt{np}$ times more stringent than that in [2]. Could the authors please explain why their analysis requires stronger noise conditions?\n\n[1] Li, Yuanzhi, Tengyu Ma, and Hongyang Zhang. \"Algorithmic regularization in over-parameterized matrix sensing and neural networks with quadratic activations.\" Conference On Learning Theory. PMLR, 2018.\n\n[2] Ma, Cong, et al. \"Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution.\" Foundations of Computational Mathematics 20 (2020): 451-632.\n\n[3] Chen, Yuxin, et al. \"Gradient descent with random initialization: Fast global convergence for nonconvex phase retrieval.\" Mathematical Programming 176 (2019): 5-37.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for the feedback. Please see our response to the reviewer’s question.\n\n>**1. My major concern of this paper is a lack of theoretical novelty.  ... If I underestimate the technical novelty of the paper, I hope the authors could clarify and please highlight their technical novelty.**\n\nThe results presented in this paper cannot be obtained by just combining the previous works that the reviewer mentioned. The technical novelty of our work is at delicate analysis of both $\\ell\\_2$ and $\\ell\\_\\infty$ norm in Phase I, which was not studied before.\nIn order to show that the norms decrease exponentially at a rate less than 1, the strong convexity of Hessian matrix around $\\mathbf{x}^\\star$ was mainly used in [2]. In Phase I, we do not have such convexity, and the Hessian matrix implies that both $ \\Vert \\mathbf{x}^{(t)} - \\tilde{\\mathbf{x}}^{(t)} \\Vert\\_2$ and $ \\Vert \\mathbf{x}^{(t)} - \\mathbf{x}^{(t,l)} \\Vert\\_2$ may grow at a rate $(1 + \\eta \\lambda^\\star)$ in Phase I. However, with some simulation, we observed that both quantities do not increase exponentially, and we actually prove through Lemma 5.1 and 5.4 that the quantities increase polynomially with respect to $t$.\n\nTwo techniques were developed to obtain such results. First, we introduced another sequence $\\hat{\\mathbf{x}}^{(t)}$ that evolves with simpler recursive equation than $\\mathbf{x}^{(t)}$, and proved that $\\Vert \\hat{\\mathbf{x}}^{(t)} - \\tilde{\\mathbf{x}}^{(t)} \\Vert\\_2 $ increases polynomially as stated in Lemma 5.2. We proved the lemma by expanding both sequences with matrix polynomial, and such an approach was not used in any of the previous work. The quantity $\\Vert \\mathbf{x}^{(t)} - \\hat{\\mathbf{x}}^{(t)} \\Vert\\_2 $ is allowed to grow exponentially with the rate $(1 + \\eta \\lambda^\\star)$ as stated in Lemma 5.3, but since its initial size is proportional to $\\beta\\_0^3$, it is negligible compared to $\\Vert \\hat{\\mathbf{x}}^{(t)} - \\tilde{\\mathbf{x}}^{(t)} \\Vert\\_2 $ in Phase I, thanks to the small initialization.\n\nSecond, we proved that $(\\mathbf{x}^{(t)} - \\mathbf{x}^{(t,l)})$ is almost orthogonal to $\\mathbf{u}^\\star$ in Phase I (see Lemma 5.5). $ \\Vert \\mathbf{x}^{(t)} - \\mathbf{x}^{(t,l)} \\Vert\\_2$ can only grow exponentially at the rate $(1 + \\eta \\lambda^\\star )$ when it is parallel to $\\mathbf{u}^\\star$. However, by showing that they are almost orthogonal to each other in Phase I, the norm grows only linearly with respect to $t$. With this result, we finally succeed to show that the trajectory is close to the fully observed case in the sense of $\\ell\\_\\infty$-norm and the norm is kept to $\\frac{1}{\\sqrt{np}} \\frac{\\beta_0}{\\sqrt{n}}$ ignoring for log factors, as stated in (12) of Lemma 5.1. To conclude, although the same leave-one-out approach was used, different induction hypotheses from [2] were used in our work to reflect different geometry of Phase I.\n\nNote also that due to our delicate analysis of $\\ell\\_2$-norm in Phase I, the initialization size of up to $n^{-1/4}$ is allowed in our result, while the upper bound on initialization size reads $n^{-3/4}$ in [4], which generalizes the result of [1].\n\n---\n\n>**2. I am not satisfied with the convergence guarantees. The estimation error provided by Theorem 3.1 only shows that the output of the proposed algorithm is consistent, namely is o(1). However state-of-the-art results for matrix completion already shows that GD with spectral initialization (which I believe is equivalent to small random initialization in some sense, since the initial phase of the latter algorithm is similar to some form of power method) achieves minimax-optimal estimation error [2]. Could the authors please explain why their analysis leads to looser error bound?**\n\n>**3. In addition, the noise condition in Theorem 3.1 is $\\sqrt{np}$ times more stringent than that in [2]. Could the authors please explain why their analysis requires stronger noise conditions?**\n\nBoth questions are answered in Section 3: Estimation Error of the main text and Section F of the supplementary material. To summarize, out current approach employs extra samples to enhance the upper bound on initialization size, which is evident from equation (8). (it reads $n^{-1/4} \\sqrt[4]{np}$) Nonetheless, by keeping the initialization size to $n^{-1/4}$ regardless of sample complexity, we are able to obtain the minimax-optimal estimation error and the noise condition of [2]. We discussed about this tradeoff in Section 3 of the main text, while the potential adjustments required for proving in the context of a fixed initialization size are briefly outlined in Section F of the supplementary material. Hence, with extra samples, one has the option to either improve the estimation accuracy or to increase the initialization size to reduce the number of iterations.\n\n---\n\n[1] Li, Yuanzhi, Tengyu Ma, and Hongyang Zhang. \"Algorithmic regularization in over-parameterized matrix sensing and neural networks with quadratic activations.\" Conference On Learning Theory. PMLR, 2018.\n\n[2] Ma, Cong, et al. \"Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution.\" Foundations of Computational Mathematics 20 (2020): 451-632.\n\n[3] Chen, Yuxin, et al. \"Gradient descent with random initialization: Fast global convergence for nonconvex phase retrieval.\" Mathematical Programming 176 (2019): 5-37.\n\n[4] Dominik Stöger and Mahdi Soltanolkotabi “Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstruction”"}, {"review_id": "B4CegOIxDB", "reviewer": "Reviewer_kLXw", "summary": "This paper studies the global convergence of vanilla GD for the rank-1 matrix completion problem. It is shown that with small random initialization and after a logarithmic number of steps, GD enters a region around the global minimizers in which linear convergence happens. The paper provides sufficient conditions on the initialization scale to ensure this phenomenon happens and shows a tradeoff between the initialization scale and the number of available samples. Illustrative simulations are provided. ", "questions": "- The nature of the presented proofs lies very much in the detail. While the authors did a good job providing a higher-level view of the proof strategy, and the writing is clear, the text is still difficult to follow at times. A possible improvement would be to include some pictorial description of the phases -- similar to the one in section 4, for the analysis carried out in sections 5, 6. This can significantly aid understanding, in my opinion. \n\n- Figure 2 a: the green line is labelled as $\\\\| x^{(t)} - x^{\\star} \\\\|$, but in the figure commentary it is written $\\\\|x^{(t)} \\pm x^{\\star}\\\\|$. Which one is the correct one?\n\n- Figure 2 c: Perhaps instead the label \"Distance\" can be replaced with $\\\\|x^{(t)} \\pm x^{\\star}\\\\|$ for clarity. ", "limitations": "The limitations are adequately discussed. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper studies a topic of interest for the Neurips community, which it presents in a clear manner and for which it provides results of both practical and theoretical importance. The derivations in the main paper are cleanly carried out, and the reasoning behind them is well-presented. ", "weaknesses": "- The sample complexity seems to be quite large (for example, compared to that in [1]). In this light, can the authors elaborate further on this aspect (my question is despite the further commentary in section 6)? \n\n[1] C. Ma, K. Wang, Y. Chi, and Y. Chen, “Implicit regularization in nonconvex statistical estimation: Gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution,” Foundations of Computational Mathematics, vol. 20, no. 3, pp. 451–632, 2020.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for the feedback. Please see our response to the reviewer’s question.\n\n>**The sample complexity seems to be quite large (for example, compared to that in [1]). In this light, can the authors elaborate further on this aspect (my question is despite the further commentary in section 6)?**\n\nThe global convergence of gradient descent for phase retrieval was proved in [a], and it also required more log factors ($\\log^{13} n$) compared to the local convergence result [b] ($\\log n$). An improved analysis compared to ours could reduce the required sample complexity to that in [b], but we want to point out that it is difficult as it was for phase retrieval.\n\nThe global geometry of loss function is not as benign as the local geometry around the global minimum. Additionally, it is customary to partition the gradient descent trajectory into distinct phases during the analysis of global convergence. However, establishing precise bounds during phase transitions is usually challenging and we have to rely on extra sample complexity.\n\n---\n\n>**The nature of the presented proofs lies very much in the detail. While the authors did a good job providing a higher-level view of the proof strategy, and the writing is clear, the text is still difficult to follow at times. A possible improvement would be to include some pictorial description of the phases -- similar to the one in section 4, for the analysis carried out in sections 5, 6. This can significantly aid understanding, in my opinion.**\n\nDue to space limit, we could not insert a figure for Sections 5 and 6 in the main text. We will at least include the figure in supplementary in the final version.\n\n---\n\n>**Figure 2 a: the green line is labelled as $\\Vert \\mathbf{x}^{(t)} - \\mathbf{x}^\\star \\Vert$, but in the figure commentary it is written $\\Vert \\mathbf{x}^{(t)} \\pm \\mathbf{x}^\\star \\Vert$. Which one is the correct one?**\n\n$\\Vert \\mathbf{x}^{(t)} \\pm \\mathbf{x}^\\star \\Vert$ is the correct one. We appreciate your careful review.\n\n---\n\n>**Figure 2 c: Perhaps instead the label \"Distance\" can be replaced with $\\Vert \\mathbf{x}^{(t)} \\pm \\mathbf{x}^\\star \\Vert$ for clarity.**\n\nWe will change the label accordingly.\n\n---\n\n[a] Yuxin Chen et al. \"Gradient descent with random initialization: Fast global convergence for nonconvex phase retrieval.\"\n\n[b] Cong Ma et al. \"Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution.\"\n"}, {"review_id": "S7apMpCKCY", "reviewer": "Reviewer_irzy", "summary": "The authors study a random initialization scheme for gradient descent applied to the problem of rank-one matrices, assuming a known ground truth. Their results concern global convergence properties of the with respect to a particular random model of partially observed matrices. Specifically, starting from a $n\\times n$ symmetric positive definite, fully-revealed ground truth matrix $\\bf{M}^\\star = \\lambda^\\star \\bf{u}^\\star (\\bf{u}^\\star)^T= \\bf{x}^\\star (\\bf{x}^\\star)^T$, entries above or on the diagonal are perturbed by noise drawn i.i.d. from a zero-mean Gaussian, and revealed independently with probability $p.$ The main result, Theorem 3.1, requires a coherence assumption: namely, for $\\lVert \\mathbf{u}^\\star \\rVert = \\sqrt{\\frac{\\mu}{n}},$ the quantity $\\mu$ is polynomially-bounded in $n.$ With this assumption, the main result claims that, if the Gaussian noise is sufficiently small and an initial iterate $\\mathbf{x}_0$ is provided whose magnitude is not too large or small according to quantities depending on $n, \\mu , \\lambda^\\star ,$ and $p,$ that gradient descent will converge to the given ground truth with probability tending to $1$ as $n\\to \\infty .$ In addition to giving proofs, the authors explain the qualitative behavior of convergence as determined by several phases, which appear in both the analysis and a simulation study.", "questions": "line 3: Do you mean \"simplest yet _most_ efficient?\"\n\nline 121: It would helpful to clarify that asymptotic notation like $o(1)$ refers to the regime $n\\to \\infty ,$ as opposed to other parameters tending towards infinity or zero.\n\nTheorem 3.1: It seems that a corollary of this theorem would be that $\\pm \\bf{x}^\\star$ are the only ground-truth solutions to the matrix completion problem. Is that something that is already assumed in the proof of your result? I don't see anywhere an explanation of why the cases with multiple ground truth solutions would be asymptotically rare.", "limitations": "n/a", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "It seems that the combination of leave-one-out sequences developed in [14] and the random initialization used in areas like phase retrieval are a novel aspect of this work, although as mentioned in Sec. 6 there is difficulty in extending this combination to the case of arbitrary rank. Theorems and definitions are, for the most part, stated unambiguously, and I was unable to find any errors. The topic is clearly a good fit for NeuRIPS.", "weaknesses": "One issue I have with this paper is that rank-1 symmetric matrix completion (as well as rank-1 general matrix completion) is simply a much easier problem than general matrix completion. \n\nIndeed, I would like to point out the reference \"Uniqueness of Low-Rank Matrix Completion by Rigidity theory\", by Singer and Cucuringu, which is not cited in this work. Section 5 of this paper shows that the existence of an exact completion is guaranteed (with \"probability one\") based purely on combinatorial conditions of the graph of revealed entries. By contrast, the authors make high-probability statements about matrices whose entries are drawn and hidden according to specific distributional assumptions as the sample size goes to infinity, which seem to be much stronger. In general, the bibliography could be more extensive.\n\nAdditionally, equation (8) shows that there are _lower_ bounds in addition to upper bounds on the magnitude of the initialization that is needed. Thus, merely a \"small\" initialization is not enough to ensure convergence, contrary to the title. Finally, there is a nontrivial coherence assumption. This may be standard in compressed sensing, but it is still a nontrivial assumption.\n\nIn summary, the assumptions are overly restrictive, and, unlike the arbitrarily matrix completion problem, rank-1 matrix completion is a fairly simple problem. So, I think the paper's claimed results are not very interesting overall.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for the feedback. Please see our response to the reviewer’s question.\n\n>**One issue I have with this paper is that rank-1 symmetric matrix completion (as well as rank-1 general matrix completion) is simply a much easier problem than general matrix completion.**\n\nThe question of whether the combination of GD with random initialization can effectively solve a specific problem holds significant importance in the field of optimization. Phase retrieval and matrix sensing are one of the low-rank recovery problems, like matrix completion. For those problems, the global convergence of GD from a randomly initialized point has been proved. However, despite its similarity to matrix sensing, no analogous result had been established for matrix completion. The problem remains open especially after the local convergence result [a] published in 2017.\n\nAlthough the rank-one case does not have much impact in itself, it will provide a good starting point for someone who challenges the full problem. Our novel analysis on Phase I provides a good understanding on the dynamics of GD that starts from a small random initializer. We expect that our key lemmas such as Lemmas 5.2 and 5.5 will continue to hold for the general rank-r case in a similar way. For Phase II, we have a difficulty in analyzing the singular values of the trajectory, and it is discussed in Section 8 with some simulation results.\n\n---\n\n>**Indeed, I would like to point out the reference \"Uniqueness of Low-Rank Matrix Completion by Rigidity theory\", by Singer and Cucuringu, which is not cited in this work. Section 5 of this paper shows that the existence of an exact completion is guaranteed (with \"probability one\") based purely on combinatorial conditions of the graph of revealed entries. By contrast, the authors make high-probability statements about matrices whose entries are drawn and hidden according to specific distributional assumptions as the sample size goes to infinity, which seem to be much stronger. In general, the bibliography could be more extensive.**\n\nFor more than a decade, the probabilistic model investigated in this paper has stood as the standard model for researchers studying matrix completion, following the pioneering work of [b]. There have been hundreds of papers studying matrix completion under the probabilistic model; therefore, it is difficult to assert that the model is overly restrictive. However, we will try to include the paper that the reviewer suggested in the final manuscript, as it offers a distinct perspective on matrix completion.\n\n---\n\n>**Additionally, equation (8) shows that there are lower bounds in addition to upper bounds on the magnitude of the initialization that is needed. Thus, merely a \"small\" initialization is not enough to ensure convergence, contrary to the title.**\n\nAn exceptionally small initialization size such as $e^{-n}$ could be detrimental to the convergence of GD because it extends convergence time from $\\Theta(\\log n)$ to $\\Theta(n)$. Because we are deriving probabilistic bounds for all iterations, establishing an upper bound on the iteration count is imperative. Similar bound can also be found in previous work [a]. While imposing a limit on the number of iterations might seem counterintuitive when proving local convergence, Theorem 2 of reference [a] does that precisely by constraining the maximum iteration count to $O(n^5)$. Nonetheless, we can further reduce the lower bound $n^{-10}$ to $n^{-c}$ for any $c > 10$ by tuning some constant factors during the proof. We do not think this is a restrictive assumption.\n\n---\n\n>**Finally, there is a nontrivial coherence assumption. This may be standard in compressed sensing, but it is still a nontrivial assumption.**\n\nThe incoherence condition is another standard assumption that researchers follow when studying matrix completion. The seminal work [b] provides a good explanation on why such an assumption is required. If information of matrix is concentrated on only few entries, we will not be able to recover the matrix unless we observe those entries. The incoherence assumption ensures that information is distributed nearly evenly across all entries of the matrix.\n\n---\n\n>**line 3: Do you mean \"simplest yet most efficient?\"**\n\nWe will change the sentence to “a simple yet efficient”.\n\n---\n\n>**line 121: It would helpful to clarify that asymptotic notation like $o(1)$ refers to the regime $n \\to \\infty$ as opposed to other parameters tending towards infinity or zero.**\n\nWe will mention in somewhere that all asymptotic relations in this paper are with respect to $n$.\n\n---\n\n>**Theorem 3.1: It seems that a corollary of this theorem would be that $\\pm \\mathbf{x}^\\star$ are the only ground-truth solutions to the matrix completion problem. Is that something that is already assumed in the proof of your result? I don't see anywhere an explanation of why the cases with multiple ground truth solutions would be asymptotically rare.**\n\nWe are not assuming that $\\pm \\mathbf{x}^\\star$ are the only global minima. What Theorem 3.1 implies is that GD converges to $\\pm \\mathbf{x}^\\star$ with high probability (even if some other global minima exist).\n\n---\n\n[a] Cong Ma et al. \"Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution.\"\n\n[b] E. J. Candes and B. Recht, “Exact Matrix Completion via Convex Optimization”\n"}, {"review_id": "wXHUgIBcYE", "reviewer": "Reviewer_96zD", "summary": "The paper studies global convergence of GD (with a fixed step-size) for the rank-1 matrix completion problem (with symmetric and i.i.d. Bernoulli(p) observation and Gaussian noise on the entries) started from \"small\" random initialization. The authors prove that such vanilla GD, without any explicit regularization as commonly used in the literature, converges to the ground truth matrix in a polynomial time with near-optimal sample complexity. The result is interesting and the program is well-motivated. The analysis is mostly based on dynamical systems rather than optimization techniques, and a similar approach could be applied for related problems. \n\nThe proof idea seems to be novel (although some of the ideas seems to be motivated by recent literatures on GD with small initialization & stepwise for matrix factorization and matrix sensing problem). First, the authors first show that GD for the fully observed case with small initialization converges to the ground truth matrix (Corollary 1 in the appendix). This is possible due to an explicit formula for the GD iterates (a linear combination of the initialization and the ground truth with dynamic coefficients). The analysis is not very difficult, but also not so trivial. \n\nHaving established the desired convergence result for the fully observed GD dynamics, the main idea is to couple that with the partially observed GD dynamics by starting at the same initialization and use an interpolated dynamics eq. (13). The main novelty is in showing that these two trajectories remain close, and much closer than the norm of the iterates from the fully observed case. This allows one to show that the partially observed iterates converges to a local region near the ground truth after a polynomial number of iterations, and then one can use existing local convergence result [14]. \n", "questions": "eq. (8): Is it intentional to not to cancel out $n^{1/4}$ factor in the upper bound?\n\nL216: Shouldn't $\\tilde{x}^{(1)}$ here be $x^{(0)}$?\n\nLemma 5.5: $u^{(l)}$ is not defined. Same as $u^{\\star}$ but 0 at the $\\ell$th coordinate?", "limitations": "N/A", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "\nThe main text is exceptionally well-written (with minor comments/suggestions) in that it gives the structure of the proof of the main result in a very clear manner (which was a pleasure to read for the most part). The argument in the main text is well-complemented with various simulation results. The general rank-r case was also discussed at the end, and the main difficulty of having the r singular values possibly growing at different rates is well-pointed out. It seems that the appendix gives a rigorous justification of most of the claims in the main text (although some references and pointers are missing). I've only read the appendix until Section C and cannot assess that the remainder (the coupling analysis, which is the most substantial part) is correct, but the sketch in the main text is convincing. ", "weaknesses": "Minor comments: \n\nL98: \"To recover the matrix,\"  --> \"To recover the matrix $M^{\\star}$,\"\n\nL110: \"controlling the $\\ell_{\\infty}$-norm in [14]\" --> $\\ell_{\\infty}$-norm of what?\n\nNotation $\\lesssim$ is not defined \n\nL166: \".. linear combination of $x^{(0)}$ and $u^{\\star}$, ..\" --> \".. linear combination of $x^{(0)}$ and $u^{\\star}$ (see eq. (C.1) in the appendix)\" \n\nL214: \"becomes\" --> \"is\"\n\nL233 and L234: \"between\" --> \"of\"\n\nL259: \".. parallel to $u^{\\star}$.\" --> \".. parallel to $u^{\\star}$ (see Lem. A.5 in the appendix).\"\n\nL286: \".. in both $\\ell_{2}$ and $\\ell_{\\infty}$ norms, ..\" --> \".. in both $\\ell_{2}$ and $\\ell_{\\infty}$ norms (see Cor. 1 in the appendix), ..\" \n\n\n\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for the feedback. Please see our response to the reviewer’s question.\n\n>**Minor Comments: ...**\n\nWe will change the manuscript accordingly. Thanks for your careful review.\n\n---\n\n>**eq. (8): Is it intentional to not to cancel out $n^{1/4}$ factor in the upper bound?**\n\nYes, it was intentional to not to cancel out $n^{1/4}$. We tried to emphasize that when optimal samples are provided, i.e. $np = poly(\\log n)$, the initialization size should be less than $n^{-1/4}$.\n\n---\n\n>**L216: Shouldn't $\\tilde{\\mathbf{x}}^{(1)}$ here be $\\mathbf{x}^{(0)}$?**\n\nWe tried to compare the norms of $\\mathbf{x}^{(1)} - \\tilde{\\mathbf{x}}^{(1)}$ to those of $\\tilde{\\mathbf{x}}^{(1)}$, so $\\tilde{\\mathbf{x}}^{(1)}$ is the right one.\n\n---\n\n>**Lemma 5.5: $\\mathbf{u}^{(l)}$ is not defined. Same as $\\mathbf{u}^\\star$ but 0 at the $l$th coordinate?**\n\n$\\mathbf{u}^{(l)}$ is defined at the end of Lemma 5.5. $\\mathbf{u}^{(l)}$  is the first eigenvector of $\\mathbf{M}^{(l)}$ .\n"}, {"review_id": "j6CpimI21W", "reviewer": "Reviewer_zH8c", "summary": "In this work, the authors proved the global convergence of the gradient descent algorithm with a small initialization for the rank-1 matrix completion problem. ", "questions": "(1) Line 55: I would suggest the authors to be more specific on what parameters the convergence time has a logarithmic dependence on.\n\n(2) Line 78: it would be better to be consistent in using \"GD\" as the abbreviation of \"gradient descent\".\n\n(3) Line 86: it would be better to explicitly mention that u^* is a vector.\n\n(4) Line 102: I think the squared norm of x^0 is expected to be \\beta_0^2. But I am not sure if the norm of x^0 is expected to be \\beta_0.\n\n(5) Line 128: I think it may be better to include the global convergence result in a formal theorem (instead of a remark).\n\n(6) Line 143: besides the relation between T^* and \\beta_0, I wonder if there is a reason why \\beta_0 is lower bounded. It seems that the initialization size is not necessarily lower bounded in [17, 23]. It may be better to explain the reason why a lower bound is necessary.\n\n(7) Line 154: the remark on the estimation error could also be formalized as a theorem.\n\n(8) in Line 88, the authors mentioned that the incoherence at be at most poly(log n). But this condition is not included in Theorem 3.1. I wonder if this condition is necessary for the results.\n\n(9) Line 170: please be more specific on the meaning of \"incoherent up to a logarithmic factor\".\n\n(10) In my opinion, the discussion of proof ideas in Sections 4-5 is a little too long. It would be ideal if the length can be reduced by ~2 pages. With that said, I am okay with the current structure.\n\n(11) Line 319: \"an optimal number of samples\" is confusing. Please consider using a different word.\n\n(12) Another interesting open problem will be whether the results can be extended to the over-parameterized case, where a small initialization is also required.\n\n(13) Besides the aforementioned problem, it would also be interesting to consider the asymmetric matrix completion problem; see the follow-up work:\n\nSoltanolkotabi, M., Stöger, D., & Xie, C. (2023). Implicit balancing and regularization: Generalization and convergence guarantees for overparameterized asymmetric matrix sensing. arXiv preprint arXiv:2303.14244.", "limitations": "See my comments in the previous section.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The results in this work is novel and should be interesting to audiences in optimization and machine learning fields. This work shows that the incoherence regularizer may be unnecessary for the matrix completion problem.", "weaknesses": "A more detailed comparison with \n\nChen, J., Liu, D., & Li, X. (2020). Nonconvex Rectangular Matrix Completion via Gradient Descent Without ℓ₂,∞ Regularization. IEEE Transactions on Information Theory, 66(9), 5806-5841.\n\nshould be included. In addition, the importance of analyzing the rank-1 case should be discussed in more detail.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for the feedback. Please see our response to the reviewer’s question.\n\n>**A more detailed comparison with Chen, J., Liu, D., & Li, X. (2020) ... should be included.**\n\nThe paper that reviewer mentioned is an extension of the local convergence result [a] to the asymmetric case and it reduces the required sample complexity by some log factors. If we apply the techniques developed in the paper, we may also reduce the sample complexity, but we are not sure about this at this moment because for the rank-1 case, many parts of the analysis in [a] are already simplified.\n\n---\n\n>**In addition, the importance of analyzing the rank-1 case should be discussed in more detail.**\n\nThe question of whether the combination of GD with random initialization can effectively solve a specific problem holds significant importance in the field of optimization. Phase retrieval and matrix sensing are one of the low-rank recovery problems, like matrix completion. For those problems, the global convergence of GD from a randomly initialized point has been proved. However, despite its similarity to matrix sensing, no analogous result had been established for matrix completion. The problem remains open especially after the local convergence result [a] published in 2017.\n\nAlthough the rank-one case does not have much impact in itself, it will provide a good starting point for someone who challenges the full problem. Our novel analysis on Phase I provides a good understanding on the dynamics of GD that starts from a small random initializer. We expect that our key lemmas such as Lemmas 5.2 and 5.5 will continue to hold for the general rank-r case in a similar way. For Phase II, we have a difficulty in analyzing the singular values of the trajectory, and it is discussed in Section 8 with some simulation results.\n\n---\n\n>**(1) Line 55: I would suggest the authors to be more specific on what parameters the convergence time has a logarithmic dependence on. (2) Line 78: it would be better to be consistent in using \"GD\" as the abbreviation of \"gradient descent\". (3) Line 86: it would be better to explicitly mention that $u^{*}$ is a vector.**\n\nWe will change the manuscript accordingly. We appreciate your careful review.\n\n---\n \n>**(4) Line 102: I think the squared norm of $x^0$ is expected to be $\\beta\\_0^2$. But I am not sure if the norm of $x^0$ is expected to be $\\beta\\_0$.**\n\nYes, the square norm is expected to be $\\beta_0^2$, and the expectation of norm is not precisely $\\beta_0$, but it is very close to $\\beta_0$. We will correct this.\n\n---\n\n>**(5) Line 128: I think it may be better to include the global convergence result in a formal theorem (instead of a remark).**\n\nWe tried to emphasize our own contribution with the main theorem. We will state the global convergence result in a formal theorem in the supplementary due to lack of space.\n\n---\n \n>**(6) Line 143: besides the relation between $T^{*}$ and $\\beta_0$, I wonder if there is a reason why $\\beta\\_0$ is lower bounded. It seems that the initialization size is not necessarily lower bounded in [17, 23]. It may be better to explain the reason why a lower bound is necessary.**\n\nAn exceptionally small initialization size such as $e^{-n}$ could be detrimental to the convergence of GD because it extends convergence time from $\\Theta(\\log n)$ to $\\Theta(n)$. Because we are deriving probabilistic bounds for all iterations, establishing an upper bound on the iteration count is imperative. Similar bounds can also be found in previous work [a]. While imposing a limit on the number of iterations might seem counterintuitive when proving local convergence, Theorem 2 of reference [a] does precisely that by constraining the maximum iteration count to $O(n^5)$. Nonetheless, we can further reduce the lower bound $n^{-10}$ to $n^{-c}$ for any $c > 10$ by tuning some constant factors during the proof.\n\n---\n\n>**(7) Line 154: the remark on the estimation error could also be formalized as a theorem.**\n\nThe potential adjustments to the proof when initialization size is fixed is briefly discussed in Section F of the supplementary. We will include a formal theorem on this result in the supplementary in the final version.\n\n---\n \n>**(8) in Line 88, the authors mentioned that the incoherence at be at most poly($\\log n$). But this condition is not included in Theorem 3.1. I wonder if this condition is necessary for the results.**\n\nYes, it is also assumed in Theorem 3.1. We will include the condition in Theorem 3.1.\n\n---\n \n>**(9) Line 170: please be more specific on the meaning of \"incoherent up to a logarithmic factor\".**\n\nWe will define the incoherence of a vector in Section 2.\n\n---\n \n>**(10) In my opinion, the discussion of proof ideas in Sections 4-5 is a little too long. It would be ideal if the length can be reduced by ~2 pages. With that said, I am okay with the current structure.**\n\nWe agree with this, but it would be hard to rewrite the sections in this submission.\n\n---\n\n>**(11) Line 319: \"an optimal number of samples\" is confusing. Please consider using a different word.**\n\nWe will mention the optimal number of samples as $n \\mathrm{poly}(\\log n)$.\n\n---\n\n>**(12) Another interesting open problem will be whether the results can be extended to the over-parameterized case, where a small initialization is also required. (13) Besides the aforementioned problem, it would also be interesting to consider the asymmetric matrix completion problem; see the follow-up work: Soltanolkotabi, M., Stöger, D., & Xie, C. (2023). ...**\n\nWe are aware of both directions, and we will mention them in Section 8 if space is allowed. We have tried for both directions, but it was not trivial to extend the current result to both cases.\n\n---\n\n[a] Cong Ma et al. \"Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution.\""}]

Author rebuttal:

Meta-review: The manuscript does a really outstanding job at explaining the question they pose, that of rank one matrix completion using gradient descent from small random initialisation. The main criticism of the manuscript are concerns about how interesting new results are about the rank one matrix completion question, and that many other manuscripts in the area are not cited; these are fair criticism that I completely agree with. That said, those concern focuses on the results themselves and don't take as much account of the technique of proof a I think is warranted. I agree with the reviewer that is most supportive of acceptance, that the manuscript gives a lot of scope for impacting future study of the question, in particular for higher rank. The value of the manuscript is in the clarity of the proof, see section 4-6, which explain not just how the result are derived, but give good quantitative explanations as to how the algorithm acts in practise. This is explained through a direction finding and then a expansion phase. This is explained so nicely that one imagines it can be extended to the larger rank setting and might also give insight into how to solve related questions. It is this clarity and accuracy of the proof that shine for the manuscript. That said, one can rightly wonder if this approach is ever going to be a sensible method in real applications as the ability to explain the behaviour comes from a very poor starting point and slow step size; surely the one step method of scaled rank projection in [10] will always be preferred to this extremely slow gradient descent approach. That said, I think there is intellectual merit in method of proof which might be applied effectively in other settings.
Decision: Accept (poster)