Preconditioned Gradient Descent for Over-Parameterized Nonconvex Matrix Factorization
Authors: Gavin Zhang
Salar Fattahi
Richard Y. Zhang
Venue: NeurIPS 2021 Poster (2021)
Keywords: low-rank matrix factorization
matrix sensing
nonconvex optimization
semidefinite programming
gradient descent

Abstract: In practical instances of nonconvex matrix factorization, the rank of the true solution $r^{\star}$ is often unknown, so the rank $r$
of the model can be over-specified as $r>r^{\star}$. This over-parameterized regime of matrix factorization significantly slows down the convergence of local search algorithms, from a linear rate with $r=r^{\star}$ to a sublinear rate when $r>r^{\star}$. We propose an inexpensive preconditioner for the matrix sensing variant of nonconvex matrix factorization that restores the convergence rate of gradient descent back to linear, even in the over-parameterized case, while also making it agnostic to possible ill-conditioning in the ground truth. Classical gradient descent in a neighborhood of the solution slows down due to the need for the model matrix factor to become singular. Our key result is that this singularity can be corrected by $\ell_{2}$ regularization with a specific range of values for the damping parameter. In fact, a good damping parameter can be inexpensively estimated from the current iterate. The resulting algorithm, which we call preconditioned gradient descent or PrecGD, is stable under noise, and converges linearly to an information theoretically optimal error bound. Our numerical experiments find that PrecGD works equally well in restoring the linear convergence of other variants of nonconvex matrix factorization in the over-parameterized regime.

Preconditioned Gradient Descent for Over-Parameterized Nonconvex Matrix Factorization
Gavin Zhang
Salar Fattahi University of Michigan fattahi @um fimiich.. edu
University of Illinois at Urbana- Champaign jialun2011linor edu
Richard Zhang
University of Illinois at Jirbnna-Chappan ryz@illinois.ee
Abstract
In practical instances of nonconvex matrix factorization, the rank of the true solution r' is often unknown, so the rank r of the model can be overspecified as r > r*. This peeemtrraette regime of matrix factorization significantly slows down the convergence of local search algorithms, from a linear rate with r = r" to a sublinear when
r". We propose an inexpensive preconditioner for the matrix sensing variant of nonconvex matrix factorization that restores the convergence rate of gradient descent back to linear, even in the pver-parameterized case, while also making it agnostic to possible ill-conditioning in the ground truth. Classical gradient descent in neighborhood of the solution slows down due the need for the model matrix factor to become singular. Our key result is that this singularity can be corrected by & regularization with specific range of values for the damping parameter. In fact, a good damping parameter can be inexpensively estimated from the current iterate. The resulting algorithm, which we call preconditioned gradient descent or PrecGD, is stable under noise, and converges linearly to an information theoretically optimal error bound. Our numerical experiments find that PrecGD works equally well in restoring the linear convergence of other variants of nonconvex matrix factorization in the perrpaaaaeterizzd regime.
Introduction
Numerous problems in machine learning be reduced to the matrix factorization problem of recovering a low-rank positive semidefinite matrix M ž 0, given a small number of potentially noisy observations [1-7]. In every case, the most common approach is to formulate matrix M = X X in factored form, and to minimize noncomee empirical loss f(X) over its n x low-rank factor X. But in most real applications of nonconvex matrix factorization, the rank of the ground truth r* rank MM) is unknown. It is reasonable to choose the rank r of the model X XXT conservatively, setting it to be potentially larger than r*, given that the ground truth can be exactly recovered so long as r 2 r*. In practice, this will often lead to an over-parameterized regime, in which r" and we have specified more degrees freedom in our model X.X" than exists in the underlying ground truth M
candidate
Zhuo al. [8] recently pointed out that nonconvex matrix factorization becomes substantially less efficient the over weepparmmeterized regime. For the prototypical instance of matrix factorization known matrix sensing (see Section below for details) it is well-known that, if r r*, then (classic) gradient descent or GD
= - -VV
(GD)
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

converges at a linear rate, to an e-accurate iterate in O ((xlee(1/e) iterations, where A1 (M (//"x((MM) (M*) is the condition number of the ground truth [9, 10]. But in the case that r r*, Zhuo et al. [8] proved that gradient descent slows down to sublinear convergence rate, now requir- ing poly(1/6 iterations to yield a comparable 6-accurate solution. This is dramatic, exponential slow-down: whereas 10 digits of accuracy can be expected in just few hundred iterations when r r", tens thousands of iterations might produce just 1-2 accurate digits once r r". The
slow-down occurs even if r is just off by one, as in r r- + 1.
is helpful to understand this pheonomenon by viewing over paraaaaterrzzttionn as special, extreme case of ill-conditioning, where the condition number of the ground truth, K, is taken to infinity. In this limit, the classic linear rate (o (o/e) breaks down, and in reality, the convergence rate deterioriates to sublinear.
In this paper, we present inexpensive preconditioner for gradient descent. The resulting algorithm, which we call PrecGD, corrects for both ill-conditioning and reee-parameterzzation at the same time, without viewing them as distinct concepts. We prove, for the matrix sensing variant of nonconvex matrix factorization, that the preconditioner restores the convergence rate of gradient descent back to linear, even in the over-parameterizee case, while also making it agnostic possible ill-conditioning in the ground truth. Moreover, PrecGD maintains similar per-iteration cost to regular gradient descent, is stable under noise, and converges linearly to an information theoretically optimal error bound.
We also perform numerical experiments other variants of nonconvex matrix factorization, with different choices of the empirical loss function f. In particular, we consider different E, norms with 1 1 p < 2, in order gauge the effectiveness of PrecGD for increasingly nonsmooth loss functions. Our numerical experiments find that, if regular gradient descent is capable of converging quickly when the rank is known r r*, then PrecGD restores this rapid converging behavior when r > r*. PrecGD is able to overcome ill-conditioning in the ground truth, and converge reliably without exhibiting sporadic behavior.
2 Proposed Algorithm: Preconditioned Gradient Descent
Our preconditioner is inspired by a recent work of Tong et al. [11] on matrix sensing with an ill- conditioned ground truth M prre-parammttrization which X, X,M)), the r-th largest eigenvalue of M is allowed to approach all the way to zero. For finite but potentially very small values of (M-) > O, Tong al. [11] suggests the following iterations, which they named scaled gradient descent or ScaledGD:
be viewed as the limit of this regime, in
(ScaledGD) They prove that the scaling allows the iteration to make large, constant amount of progress at every iteration, independent of the value of (AM) > 0. However, applying this same scheme to the over-parameterizee case with (M*)) = 0 results in inconsistent, sporadic behavior.
X X (xx
The issues encountered by both regular GD and ScaledGD with over preepaaramttiizntionnn r r* can be explained by the fact that our iterate X must necessarily become singular as our rank-r model Xg.X converges towards the rank-r* ground truth M For GD, this singularity causes the per-iteration progress itself to decay, so that more and more iterations are required for each fixed amount of progress. ScaledGD corrects for this decay per-iteration progress by suitably rescaling the search direction. However, the rescaling itself requires inverting near-singular matrix, which causes algorithm to take on sporadic values.
A classical remedy to issues posed by singular matrices is lg regularization, in which the singular matrix is made "less singular" by adding small identity perturbation. Applying this idea ScaledGD yields the following iterations
X X -ol=x-aa((x)))a VVf(X) --
(PrecGD)
where 7) 2 0 is the damping parameter specific to the k-th iteration. There are several interpretations to this scheme, but the most helpful is to view r) as parameter that allows us to interpolate between ScaledGD (with 77 0) and regular GD (in the limit 7 + se). In this paper. we prove for matrix sensing that, if the k-th damping parameter M) is chosen within a constant factor of the error
XIx M || S mh Cub X
M where Cbb, Cub > 0 are abs. const. (1)
2

---

16
1015
1010
AMr m Vna
ScaledGD
10
10
erro
RrecGD
error
ScaledGD
10
10
PrecGD
10
10
10"16
100
200
300
400 500
200 300
500
iterations
iterations
Figure 1: PreeGD converges linearly in the overparameterized regime. Convergence of regular
gradient descent (GD), ScaledGD and PrecGD for noiseless matrix sensing (with data taken from [12, 13)) from the same initial points and using the same learning rate linear rate, though GD converges at
10 22 (Left = r*) Set
2. All three methods convergence a slower rate due to ill-conditioning in the ground truth. (Right > r*) With =
4 and r*
4 and
r* 2, over-varennnnnn parameterization causes gradient descent to slow down to a sublinear rate. ScaledGD also behaves sporadically. Only PrecGD converges linearly to the ground truth.
then the resulting iterations are guaranteed to converge linearly, at a rate that is independent both over-parameterization and ill-conditioning in the ground truth M With noisy measurements, setting "i to satisfy (1) will allow the iterations to converge to an error bound that is well-known to be minimax optimal up logarithmic factors [14].
We refer to the resulting iterations (with properly chosen 77 as preconditioned gradient descent, or PrecGD for short. For matrix sensing with noiseless measurements, optimal T)2 that satisfies the condition (1) is obtained for free by setting / (Xx). In the case of noisy measurements, we show that a good choice of 7h is available based on an approximation of the noise variance.
3 Background and Related Work
Notations. We use -| || to denote the Frobenius norm of matrix and (.,.) is the corresponding inner product. We use Z denote an inequality that hides constant factor. The big-O notation Ô hides logarithimic factors. The gradient of the objective is denoted by V f(X) _R The eigenvalues are assumed to be in decreasing order: A1 2 X2 2 Xy-
The symmetric, linear variant of matrix factorization known matrix sensing aims to recover positive semidefinite, rank-r* ground truth matrix M from small number of possibly noisy measurements
A(MM)) +G,
where A(M*) = [1,, M*), (A,, M*), (Am. M
in which A is linear measurement operator, and the length-m vector models the unknown measurement noise. A distinguishing feature of matrix sensing is that A assumed to satisfy the restricted isometry property [14, 15]. Throughout this paper, will always assume that A satisfies RIP with parameters (2r, 8).
Definition (RIP). The linear operator satisfies RIP with parameters (2r, 5) there exists constants 0 < 6 < 1 and > 0 such that, for every rank-2r matrix M, we have
(1 - 8)
< - [|(MM)) < (1 + +)]MM
common approach for matrix sensing is to use a simple algorithm like gradient descent to minimize the nonconvex loss function:
f(x)
1 119 - m
|| Xx*) +ell
(2)
m

---

Recent work has provided a theoretical explanation for the empirical success of this nonconvex approach. Two lines of work have emerged.
Local Guarantees. One line of work studies gradient descent initialized inside a neighborhood of the ground truth where X x M already holds [10, 16-19]. Such an initial point can be found using spectral initialization, see also [18, 20-23J. With exact rank r = r", previous authors showed that gradient descent converges
linear rate [9. 10]. In the peer-paramttrriee regime, however, local restricted convexity no longer holds, so the linear convergence rate is lost. Zhuo al. [8] showed that while spectral initialization continues to work under pver-arramtteizzation gradient descent now slows down to a sublinear rate, but it still converges to a statistical error bound of ((a²nr" /m). where denotes the noise variance. This is known to be minimax optimal up to logarithmic factors [14]. In this paper, we prove that PrecGD with damping parameter 774 satisfying (I) also converges to an ( /m) statistical error bound.
Global Guarantees. A separate line of work [13, 24-31] established global properties of the landscapes of the nonconvex objective f in (2) and its variants and showed that local search methods can converge globally. With exact rank r = r", Bhojanapalli et al. [24] proved that / has no spurious local minima, and that all saddles points have strictly negative descent direction (strict saddle property [32], see also [28, 33)). In the paramtteeetee regime, however, we are no longer guaranteed recover the ground truth in polynomial time.
Other related work. Here we mention some other techniques can be use to solve matrix sensing in the over perr--aaamettezeed regime. Classically, matrix factorization was solved via its convex SDP relaxation [14, 15, 34-36]. The resulting O to (n2)) time complexity [37] limits this technique to smaller problems, but these guarantees hold without prior knowledge on the true rank r*. First- order methods, such as ADMM [38-40] and soft- teffthhresholdin [41], can be used to solve these convex problems with a per-iteration complexity comparable to nonconvex gradient descent, but they likewise suffer from a sublinear convergence rate. Local recovery via spectral initialization was originally proposed for alternating minimization and other projection techniques [21, 23, 34, 42-45]. These also continue to work, though draw baak here is a higher per-iteration cost when compared to simple gradient methods. Finally, we mention a recent result of Li et al. [46], which showed in the pver-parameterized regime that gradient descent with early termination enjoys an algorithmic regularization effect.
4 Sublinear Convergence of Gradient Descent
In order to understand how to improve gradient descent in the over wer-parameterized regime, we must first understand why existing methods fail. For algorithm that moves in search direction D with step-size o, it is a standard technique to measure the corresponding decrement in f with a Taylor-like expansion
-(x-aD) < S(X) ar (VI(X), Dj +o (L/2))
Vinear progress
inverse step-size
in which I. is the usual gradient Lipschitz constant (see e.g. Nocedal and Wright [47, Chapter 3)). A good search direction 1) is one that maximizes the linear progress (V)()), D) while also keeping the inverse step-size (I/2) D 3- sufficiently small in order to allow a reasonably large step to be taken. As we will show in this section, the main issue with gradient descent in the pwrr-parameterized regime is the first term, namely, that the linear progress goes down to zero as the algorithm makes progress towards the solution.
Classical gradient descent uses the search direction D = (X). Here, a common technique is to bound the linear progress at each iteration by condition known gradient dominance (or the or PL inequality). which is written as
(VS(X), D) = ||V 2 p(((X) (*)
where > 0 and s - min f(X).
(4)
X
Substituting the inequality (4) into the Taylor-like expansion (3) leads
-(X < ((X) -
f(X - < - (f(X)
(5)

---

Here, we can always pick a small enough step-size to guarantee linear convergence:
Q = pao pa² < = - 5 fT
(6)
In particular, picking the optimal step-size a = L/L minimizes the convergence quotient Q = 1 1/(kk,, where 1//p is the usual condition number. This shows that, with optimal step-size, gradient descent needs at most ( log(1/))) iterations to find an e-suboptimal X.
Matrix sensing with exact rank r" is easily shown to satisfy gradient dominance (4) by manipu- lating existing results on (restricted) local strong convexity. In the over wer-parameterized case r >> r", however, local strong convexity is lost, and gradient dominance can fail to hold. Indeed, consider the following instance of matrix sensing, with true rank r = 1, search rank r 2, and A set to the identity
f(x) = |XX" - -2 1 where X = [
0 and = 1
We can verify that |V( 452 1821((x) - f*] and this suggests that f satisfies gradient dom- inance (4) with a constant of μ S 25 But & itself a variable that goes to zero as the candidate XX* approaches to ground truth z= For every fixed > 0 in the gradient dominance condition (4), we can find a counterexample
in (7) with & < /u/2. Therefore, we must conclude that gradient dominance fails to hold, because the inequality in (4) can only hold for μ = O.
In fact, this same example also shows why classical gradient descent slows down a sublinear rate. Applying gradient descent X = X (VV)((e)) with fixed step-size a to (7) yields a sequence of iterates the same form
-
0 Eo
0 c
1
1 Ex-
0
Xu =
X =
Ex+1
from which we can verify that f(X++1) (1- (1-of))) f(Xx).
As each k-th X approaches 22?
the element & converges towards zero, and the convergence quotient Q= (1- a approaches 1. We see a process of diminishing returns: every improvement to ʃ worsens the quotient Q. thereby reducing the progress achievable in the subsequent step. This is precisely the notion that characterizes sublinear convergence.
Linear Convergence for the Noiseless Case
To understand how it is possible make gradient descent converge linearly in the over-parameterized regime, we begin by considering gradient method under change of metric. Let be a real symmetric, positive definite nr x matrix. We define corresponding P-inner product, P-norm, and dual P-norm on gaxr as follows
(X2Y)p def Pvoc()) ||||| def V(X,X)
||||e def
V vec(X)"P-vvecc
where Roxr - R is the usual column-stacking operation. Consider descending in the direction D satisfying vec D) = P (XX)): the resulting decrement in can be quantified by P-norm analog of the Taylor-like expansion (3)
f(x aD) - f(X) aaa())-aaVoaa))
a D) +2
(8)
f(x) -((
(9)
where Lp is a P-norm gradient Lipschitz constant. we can demonstrate gradient dominance under the dual P-norm,
|VS()) 2 (r(s(X) f*)
where pr > and f = min f(X),
(10)
then we have the desired linear convergence
f(x-aD)- (1--a)-===---a((--oo
(11)
= - 1/1xp] (2((2//x))((((X-----() with 1/Lp,
(12)
in which the condition number xp = T.P/ur should be upper-hounded. To make the most progress per iteration, want to pick metric P to make the condition number Kp as small possible.
5

---

The best choice of P for the fastest convergence is simply the Hessian V2 f(X) itself, but this simply recovers Newton's 's method, which would force us invert a large nr x nr matrix to compute the search direction D at every iteration. Instead, we look for preconditioner P that is cheap to apply while still assuring a relatively small condition number Kp. The following choice particularly interesting (the Kronecker product @ is defined to satisfy vec(AXB") = (B & A A))eo(X))
P = (X" X + +1,) @ I, = x & I,. + n/hrr
because the resulting D = V V X + m//ー" allow us to interpolate between regular GD and the ScaledGD Tong et al. [1I]. Indeed, we recover regular GD in the limit v + oo, but as we saw in Section 4, gradient dominance (10) fails to hold, so the condition number Kp Lp/ Lpppp grows unbounded as μp + O. Instead, setting 7 = 0 recovers ScaledGD. The key insight of Tong et al. [11] is that under this choice of P. gradient dominance (10) is guaranteed to hold, with a large value of pi that is independent of the current iterate and the ground truth. But as we will now show, this change of metric can magnify the Lipschitz constant I.p by a factor of X (X" X), so the condition number Kp- = Lp/Pr becomes unbounded in the over-parameterized regime.
Lemma 2 (Lipschitz-like inequality). Let || | + nT,, 1/e Then have
S(X (X+D) D) S ((X)+ (V]())) + (x, D)
where
= =) o) 4+ 2||XX - M + 41111r
|DIp 27 Amin ( (XT) + +1)
A +n
Lemma 3 (Bounded gradient). For the search direction D VV(X)(XX X + nI)-1, we have | = [V) I 16(1+ + (X).
The proofs of Lemma 2 and Lemma 3 follows from straightforward linear algebra, and can be found in the Appendix. Substituting Lemma into Lemma 2, we see for ScaledGD (with v) = 0) that the Lipschitz-like constant is bounded as follows
Lr(X & (IXX* - -M" Amin (X²x))²
(13)
In the exact rank case r", the distance of X from singularity can be lower-bounded, within "good" neighborhood of the ground truth, since X = Xr XX and
||XX* 1F S (M'), p<1 - Xx 2 (1 (M)r > 0. (14)
Within this "good" neighborhood, substituting (14) into (13) yields Lipschitz constant Lp that depends only on the radius p. The resulting iterations converge rapidly, independent of any ill- conditioning in the model X nor in the ground-trut M In turn, ScaledGD can be initialized within the good neighborhood using spectral initialization (see Proposition 6 below).
In the over over- parameterized case > r", however, the iterate X must become singular in order for X X to converge to M*, and the radius of the "good" neighorhood reduces to zero. The ScaledGD direction guarantees large linear progress no matter how singular X may be, but the method may not be able to take a substantial step in this direction if X becomes singular too quickly. To illustrate: the algorithm would fail entirely if it lands at point where Amin (X x) 0 but XXT * M
While regular GD struggles to make the smallest eigenvalues of X X converge to zero, ScaledGD gets in trouble by making these eigenvalues converge quickly. In finding good mix between these two methods, an intuitive idea is to use the damping parameter 77 control the rate at which X becomes singular. More rigorously, we can pick an ~ X ZZZ || and use Lemma 2 to keep the Lipschitz constant Lp bounded. Substituting Lemma 3 into Lemma 2 and using RIP to upper-bound S(X) < + 6)] X 1 and 5 < 1 yields
(15) However, the gradient dominance condition (10) will necessarily fail if 1 set too large. Our main result in this paper is that keeping 7 within the same order of magnitude as the error norm XX 72 F enough to maintain gradient dominance. The following is the noiseless version
2 Ctb | - -zz
- Lp(X, D) < 16 136/CI, + C.
of this result.

---

Theorem 4 (Noiseless gradient dominance). Let minx fX) = 0 for M # 0. Suppose that X
satisfies f(X) S p² 8) (M*) with radius p that satisfies p²/(11 p²) S (1 8²)
Then, we have
1 S CubllXXT - 12"
= IV 2xps(X)
where
1 + 82
2
2 (v22n)
Cub
-!
(r-r*)
PP
8
-min
82
(16)
The proof Theorem 4 involved and we defer the details to the Appendix. In the noiseless case, we get good estimate of 1 for free consequence of RIP:
"1 - s(X)
vI v M Sn
-
Repeating (8)-12) with Lemma 2, (15) and (16) yields our main result below.
Corollary 5 (Linear convergence). Let X satisfy the same initial conditions in Theorem 4. The search direction D = (Xx) nT)-1 with damping parameter 1j vf()) and stzp
a S 1/Lp yields
S(X ([X-DD) s (1 app/22 f(X)
where Lp is as in (15) with Cib = v
5 and μpp is as in (16) with Cub vI+
For a fixed RIP constant 8, Corollary says that PrecGD converges at a linear rate that is independent of the current iterate X, and also independent of possible ill-conditioning the ground truth. However, it does require an initial point Xo that satisfies
||A(Xx-X3 - M² < p² 5)A (M*)²
(17)
with radius p > 0 satisfying p²/(1 pp) (1 - //2 Such an initial point can be found using spectral initialization, even if the measurements are tainted with noise. Concretely, we choose the initial point Xo
X Pr
y: A m Σ
where (.( = arg min
|XX" M]rr;
(18)
XeRex
where we recall that A(M*) + e are the m possibly noisy measurements collected of the ground truth, and that the rank-r projection operator can be efficiently implemented with singular value decomposition. The proof of the following proposition can be found the appendix.
Proposition 6 (Spectral Initialization). Suppose that 5 I (8kv/*)-1 and m Z 1+8 o² log
T-8 pax. (M
where k = \M (M*). Then, with high probability, the initial point Xo produced by (18) satisfies the radius condition (17).
However, if the measurements y are noisy, then vf(X= = |A(XX" - M2) + Ell now gives biased estimate of our desired damping parameter 7). the next section, we show that good choice of is available based on an approximation of the noise variance.
Extension to Noisy Setting
In this section, extend analysis the matrix sensing with noisy measurements. Our main goal is to show that, with a proper choice of the damping coefficient 7), the proposed algorithm converges linearly to an "optimal" estimation error.
Theorem (Noisy measurements with optimal
Suppose that the noise vector e R. has sub- Gaussian entries with zero mean and variance o Supeatt _m Be Moreover, suppose that me -==1
VTT AAXx, M*) for is 0,1,..., K, and that the initial point Xo satisfies |IA(XxxX
M I1 < (1- (2+)². Consider k* = arg mink The and suppose that the step-size S 1/L, where L > is constant that only depends on Then, with high probability, we have
1 (1 (1-a (r)) 1XooX -M -M" Estar 1
|| - < max
(19)
where Estat == d' lo up(1-8)m'

---

Assuming fixed parameters for the problem. the above theorem shows that PrecGD outputs solution with an estimation error of O (Estat) O (log (1/Estat) iterations. Moreover, the error O (Estat) is minimax optimal (modulo logarithmic factors), and cannot be improved significantly. In particu- lar, Candes and Plan [14] showed that any estimator X must satisfy || M I 2 o²nr / with non- non-negligible probability. The classical methods for achieving this minimax rate suffer from cataatiinnnllloooobtttiiii
per iteration costs [15, 21, 48]. Regular gradient descent alleviates this issue the expense of a slower convergence rate of O( ((v 1/Estat) [8]. Our proposed PrecGI) achieves the best of both worlds: converges to the minimax optimal error with cheap per-iteration complexity of O(rr + r²), while benefiting from an exponentially faster convergence rate than regular gradient descent in the over-parameterized regime.
Theorem 7 highlights the critical role of the damping coefficient in the guaranteed linear convergence of the algorithm. In the noiseless regime, we showed the previous section that an "optimal" choice 77 (X) is available for free. In the noisy setting, however, the same choice of rj becomes biased by the noise variance, and is therefore no longer optimal. As is typically the case for regularized estimation methods [49-51], selecting the ideal parameter would amount to some kind of resampling, such via cross-validation or bootstrapping [52-54], which is generally expensive implement and use in practice. As an alternative approach, we show in our next theorem that a good choice of is available based on an approximation of the noise variance o².
Theorem (Noisy measurements with variance proxy). Suppose that the noise vector c E TR. has Gau-saas entries with zero mean and variance 0² m E Bie?]. Moreover, suppose that ......,,, K, where à² is an approximation of o², and that the initial point Xo satisfies (X - M < p² - 8) (M Consider k- = arg mink Ti, and suppose that the step-size S I/L, where L > 0 is constant that only depends on 8. Then, with high probability, we have
Th = vlf(Xx) - 6² for l = 0.l....,4
1+8 (1 (1-a aae K
X - M S max
1xxox - M Estat, Edess Ever
(20)
1 1- 8
where
nnr log n 1p 8)m Edev = 1
0²
logn
Extat ==
Ever == 021.
(21)
In the above theorem, Edee captures the deviation of the empirical variance 1 E e from its expectation 0², On the other hand, Evar captures the approximation error of the true variance. According to Theorem 8, it is possible to chose the damping factor 7/s merely based on f(Xx) and an approximation of a², at the expense of a suboptimal estimation error rate. In particular, suppose that the noise variance known precisely, i.e., 6² =z² Then, the above theorem implies that the estimation error is reduced to
1 X M Z max (Estat; } after o 0 max (Estat- Eden ))
iterations.
If m is not too large, i.e., m S 222 log the estimation error can be improved to X| XT. M 1 S Estor, which is again optimal (modulo logarithmic factors). As m increases, the estimation error will become smaller, but the convergence rate will decrease. This suboptimal rate is due the heavy tail phenomenon arising from the concentration of the noise variance. In particular, one can write
11AxXX- - - m
f(x)
1 2 m
2 m
-xx))_ (22)
variance deviation
cross-term
Evidently, f(X) -2 is in the order of m |XXXX" - MI if both variance deviation and cross- term are dominated by 11 - ) )|2
2
_ In the proof of Theorem 8, we show that, with high probability, the variance deviation is upper bounded by (1 5) and it dominates the cross-term. This implics that the choice of 17 = vfx()) o²| behaves similar to vm |A(XX" -M*)| and
hence, the result of Theorem 7 can be invoked, so long as
|A[XX" -AXXX"-M')]+- (1 -1-8) x) M Z (1 8)
m
8

---

7 Numerical Experiments
Finally, we numerically compare PrecGD on other matrix factorization problems that fall outside of the matrix sensing framework. We consider the lp empirical loss fx - K4, XX" -M* for 1 S < 2, in order to gauge the effectiveness of PrecGD for increasing nonsmooth loss functions. Here, we set the damping parameter ` = [ (Xx)) as a heuristic for the error ||XX" - -M* The data matrices A!...., Am were taken from [13, Example 12]. the ground truth M = 2Z" was constructed by sampling each column of Z e Rux*" from the standard Gaussian, and then rescaling the last column to achieve desired condition number.
The recent work of Tong al. [55] showed that in the paaely--prameterizzedd setting, ScaledGI) works well for the ( loss function. In particular, if the initial point is close to the ground truth, then with Polyak stepsize ag f(Xx)/1l (XXx)ll ScaledGD converges linearly the ground truth. However, these theoretical guarantees no longer hold in the over-parameterized regime.
When r", numerical experiments show that ScaledGD blows up due singularity near the ground truth while PrecGD continues to converge linearly in this nonsmooth, over parameterizee setting. In Figure 2 compare GD, ScaledGD and PrecGD in the exact and over ver-parameterizee regimes for the lp norm, with p = 1.1, 1.4 and 1.7. For ScaledGD and PrecGD, we used modified version of the Polyak step-size where og s(Xx) / [(Xx)]] For GD stepsize. When r = r", we see that both ScaledGD and PrecGD converge linearly, but GD stagnates due to ill-conditioning of the ground truth. When r", GD still converges slowly and ScaledGI) blows very quickly, while PrecGD continues to converge reliably.
decaying
p 1.1
p 1.4
p 1.7
10²
10"
10a
10
BealenGD
10-10
10m1
ScaledGD
ScaledGD
1'
7-
PreoGD
90
10
10
PrecGD
200
200
300
400
100
200
500
Bleratooss
llerations
ilerations
105
105
Scaleck22
ScaledGD
10/
10
10
DITOF
10
>
7-*
10-12
PreeGD
10
PrecGD
PreeDDD
15
15
10
200
400
600
lterations
Figure 2: Nonconvex matrix factorization with the l empirical loss. We compare l, matrix sensing with n = 10 and p* 2 and A taken from [13]. The ground truth is chosen to be ill- conditioned (x 10²). For ScaledGD and PrecGD, we use the Polyak step-size in [55]. For GD we use a decaying step-size. (Top r = r") For all three values p, GD stagnates due to the ill-conditioning of the ground truth, while ScaledGD and PrecGD converge linearly in all three cases. (Bottom r > r") With 4, the problem over-porann wver-paaaeeterize. GD again converges slowly and ScaledGD is sporadic due ninu-singylarity caused by veeeparaaettiizitionn Once again
PrecGD converge at a linear rate.
8 Conclusions
In this paper, we propose preconditioned gradient descent or PrecGD for nonconvex matrix factorization with a comparable per-iteration cost to classical gradient descent. For pver-parameterized matrix sensing, gradient descent slows down to sublinear convergence rate, but PrecGD restores

---

the convergence rate back to linear, while also making the iterations immune to ill-conditioning in the ground truth. While the thoeretical analysis in our paper uses some properties specific to RIP matrix sensing, our numerical experiments find that PrecGD works well for even for nonsmooth loss functions. We believe that these current results can be extended to similar problems such as matrix completion and robust PCA, where properties like incoherence can be used to select the damping parameter Tis with the desired properties, so that PrecGD converges linearly as well. remains future work to provide rigorous justification for these observations.
Acknowledgements
G.Z. and R.Y.Z are supported by the NSF CAREER Award ECCS-2047462. S.F. is supported by MICDE Catalyst Grant and MIDAS PODS Grant. We also thank an anonymous reviewer who provided a simplified proof of Lemma 14 and made various insightful comments to help us improve an earlier version of this work.
References
[1] Kai Yu, Shenghuo Zhu, John Lafferty, and Yihong Gong. Fast nonparametric matrix factorization for large-scale collaborative filtering. In Proceedings of the 32nd international ACM SIGIR conference on Research and development in information retrieval, pages 211-218, 2009.
[2] Xin Luo, Mengehu Zhou, Yunni Xia, and Qingsheng Zhu. An efficient non-negative matrix- factorization- approach to collaborative filtering for recommender systems. IEEE Trans- actions on Industrial Informatics,
1284, 2014.
[3] Emmanuel J Candès, Xiaodong Li. Yi Ma, and John Wright. Robust principal component analysis? Journal of the ACM (JACM), 58(3):1-37, 2011.
[4] Venkat Chandrasekaran, Sujay Sanghavi, Pablo A Parrilo, and Alan S Willsky. Rank- sparsity incoherence for matrix decomposition. SIAM Journal on Optimization, 21(2):572-596, 201 1.
[5] Ali Ahmed, Benjamin Recht, and Justin Romberg. Blind deconvolution using convex program- ming. IEEE Transactions on Information Theory, 60(3):1711-1733) 2013.
[6] Shuyang Ling and Thomas Strohmer. Self-calibration and biconvex compressive sensing.
Inverse Problems, (1(11):1 2015.
[7] Amit Singer. Angular synchronization by eigenvectors and semidefinite programming. Applied and computational harmonic analysis, 30(1):20-3)) 2011.
[8] Jiacheng Zhuo, Jeongyeol Kwon, Nhat Ho, and Constantine Caramanis. On the compu- tational and statistical complexity of over-parameterizer matrix sensing, arXiv preprint arXiv:2102.02256. 2021.
[9] Qinqing Zheng and John Lafferty. A convergent gradient descent algorithm for rank minimiza- tion and semidefinite programming from random linear measurements. In Advances Neural Information Processing Systems, volume 28, 2015.
[10] Stephen Tu, Ross Boczar, Max Simchowitz, Mahdi Soltanolkotabi, and Ben Recht. Low-rank solutions of linear matrix equations via procrustes flow. In International Conference on Machine Learning, pages 964-973. PMLR, 2016.
[11] Tian Tong, Cong Ma, and Yuejie Chi. Accelerating ill-conditioned low-rank matrix estimation via scaled gradient descent. arXiv preprinl arXiv:2005.0888 2020.
[12] Richard Zhang, Cedric Josz, Somayeh Sojoudi, and Javad Lavaei. How much restricted isometry is needed in nonconvex matrix recovery? In Advances in Neural Information Processing Systems, volume 31, 2018.
[13] Richard Y Zhang, Somayeh Sojoudi, and Javad Lavaei. Sharp restricted isometry bounds for the inexistence of spurious local minima in nonconvex matrix recovery. Journal of Machine Learning Research,
2019.
[14] Emmanuel J Candes and Yaniv Plan. Tight oracle inequalities for low-rank matrix recovery from minimal number of noisy random measurements. IEEE Transactions on Information Theory, 57(4):2342-2359 2011.
10

---

[15] Benjamin Recht, Maryam Fazel, and Pablo A Parrilo. Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM review, 52(3):77--51, 2010.
[16] Qinqing Zheng and John Lafferty. A convergent gradient descent algorithm for rank mini- mization and semidefinite programming from random linear measurements. arXiv preprint arXiv:1506.06088 2015.
[17] Srinadh Bhojanapalli, Anastasios Kyrillidis, and Sujay Sanghavi. Dropping convexity for faster semi-definite optimization. Conference on Learning Theory, pages 530-582. PMLR, 2016.
[18] Emmanuel J Candes, Xiaodong Li, and Mahdi Soltanolkotabi. Phase retrieval via wirtinger flow: Theory and algorithms. IEEE Transactions on Information Theory, 61 61(4):1985-2007 2015.
[19] Jianhao Ma and Salar Fattahi. Implicit regularization of sub gradient method in robust matrix recovery: Don't be afraid of outliers. arXiv preprint wrXiv:2/02.02900 2021.
[20] Raghunandan H Keshavan, Andrea Montanari, and Sewoong Oh. Matrix completion from
few entries. IEEE transactions on information theory, 56(6):2900-2998, 2010.
[21] Yudong Chen and Martin J Wainwright. Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees. arXiv preprini arXiv: 1509.030222 2015.
[22] Ruoyu Sun and Zhi- Zhi-Quan Luo. Guaranteed matrix completion via non-convex factorization.
IEEE Transactions on Information Theory, 62(11):653566577 2016.
[23] Praneeth Netrapalli, UN Niranjan, Sujay Sanghavi, Animashree Anandkumar, and Prateek Jain. Non-convex robust pea. arXiv preprint 14 2014.
[24] Srinadh Bhojanapalli, Behnam Neyshabur, and Nathan Srebro. Global optimality of local search for low rank matrix recovery. arXiv preprint arXiv:
2016.
[25] Qiuwei Li, Zhihui Zhu, and Gongguo Tang. The non-convex geometry of low-rank matrix optimization. Information and Inference: A Journal of the IMA, 8(1):51-96, 2019.
[26] Ju Sun, Qing Qu, and John Wright. A geometric analysis of phase retrieval. Foundations of Computational Mathematics, 18(5): 1 131-1198 2018.
[27] Rong Ge, Jason D Lee, and Tengyu Ma. Matrix completion has no spurious local minimum. arXiv preprint arXiv: /605 07272, 2016.
(28) Rong Ge, Chi Jin, and Yi Zheng. No spurious local minima in nonconvex low rank problems: A unified geometric analysis. In International Conference on Machine Learning, pages 1233-1242. PMLR, 2017.
[29] Ji Chen and Xiaodong Li. Memory-effiieen kernel pea via partial matrix sampling and non- convex optimization: a model-free analysis of local minima, arXiv preprint 17Xiv:1711.0111 2017.
[30] Ju Sun, Qing Qu, and John Wright. Complete dictionary recovery over the sphere i: Overview and the geometric pieture. IEEE Transactions on Information Theory, 63(2):853-884 884, 2016.
[31] Richard Y Zhang. Sharp global guarantees for nonconvex low-rank matrix recovery in the overparameterized regime. arXiv preprint (oo::2104.1177 2021.
[32] Rong Ge, Furong Huang, Chi Jin, and Yang Yuan. Escaping from saddle online stochastic gradient for tensor decomposition. In Conference on learning theory, pages 797-842.
PMLR, 2015.
[33] Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M Kakade, and Michael I Jordan. How to escape saddle points efficiently. In International Conference on Machine Learning, pages 1724-1732. PMLR, 2017.
[34] Raghu Meka, Prateek Jain, and Inderjit S Dhillon. Guaranteed rank minimization via singular value projection. arXiv preprint arXiv:0909.544 5407, 2009.
[35] Emmanuel J Candès and Benjamin Recht. Exact matrix completion via convex optimization. Foundations of Computational mathematics, 96)) 2009.
[36] Emmanuel J Candès and Terence Tao. The power of convex relaxation: Near-optimal matrix completion. IEEE Transactions on Information Theory, 56(5):2053-2080 2010.
[37] Farid Alizadeh. Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM journal Optimization, 5(1):13-51, 1995.
11

---

[38] Zaiwen Wen, Donald Goldfarb, and Wotao Yin. Alternating direction augmented lagrangian methods for semidefinite programming. Mathematical Programming Computation, 2(3-4):
203-230, 2010.
[39]
Brendan O'donoghue, Eric Chu, Neal Parikh, and Stephen Boyd. Conic optimization via operator splitting and homogeneous self-dual embedding. Journal of Optimization Theory and Applications. 169(3):1042-1068 2016.
[40] Yang Zheng, Giovanni Fantuzzi, Antonis Papachristodoulou, Paul Goulart, and Andrew Wynn. Chordal decomposition in aperator-splittiin methods for sparse semidefinite programs. Mathe- matical Programming, 180(1):489-533 2020.
[41] Jian-Feng Cai, Emmanuel Candès, and Zuowei Shen. A singular value thresholding algorithm for matrix completion. SIAM Journal on optimization, 20(4):1956-199 2010.
[42] Prateek Jain, Praneeth Netrapalli, and Sujay Sanghavi. Low-rank matrix completion using alternating minimization. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 665-674, 2013.
[43] Moritz Hardt and Mary Wootters. Fast matrix completion without the condition number. In Conference learning theory, pages 638-678 PMLR, 2014.
[44] Xinyang Yi, Dohyung Park, Yudong Chen, and Constantine Caramanis. Fast algorithms for robust pea via gradient descent. arXiv preprint 1r05v 2016.
[45] Mahdi Soltanolkotabi. Structured signal recovery from quadratic measurements: Breaking sample complexity barriers via nonconvex optimization. IEEE Transactions on Information Theory, 65(4):2374 2400, 2019.
[46] Yuanzhi Li, Tengyu Ma, and Hongyang Zhang. Algorithmic regularization in pver-parameterized matrix sensing and neural networks with quadratic activations. In Conference On Learning Theory, pages 2-47. PMLR, 2018.
[47] Jorge Nocedal and Stephen Wright. Numerical optimization. Springer Science & Business Media, 2006.
[48] Sahand Negahban and Martin Wainwright. Estimation of (near) low-rank matrices with noise and high-dimensional scaling. The Annals of Statistics, pages (069-1097, 2011.
[49] Ernesto De Vito, Andrea Caponnetto, and Lorenzo Rosasco. Model selection for regularized least-squares algorithm in learning theory. Foundations of Computational Mathematics, 5(1): 59-85, 2005.
[50] Gavin C Cawley. Leave-one-out cross-validattonn based model selection criteria for weighted Is-svms. In The 2006 IEEE international joint conference on neural network proceedings, pages 1661-1668. IEEE, 2006.
[51] Jian Guo, Elizaveta Levina, George Michailidis, and Zhu. Joint estimation of multiple graphical models. Biometrika, 98(1):1-15, 2011.
[52] Phillip Good. Resampling methods. Springer, 2006.
[53] Bradley Efron and Robert J Tibshirani. An introduction to the bootstrap. CRC press, 1994.
[54] David Roxbee Cox and David Victor Hinkley. Theoretical statistics. CRC Press, 1979.
[55] Tian Tong, Cong Ma, and Yuejie Chi. Low-rank matrix recovery with scaled subgradient methods: Fast and robust convergence without the condition number. IEEE Transactions on Signal Processing, 69:2396-2409, 2021.
12


Reviews:
[{"review_id": "MlvQ7FyWPTq", "reviewer": "Reviewer_hWq7", "summary": "This paper proposed a preconditioned gradient descent (PreGD) method for low rank matrix factorization.\nIn practice, the true rank r* of the matrix is unknown.\nTo be conservative, people usually choose an over-estimated r to start with.\nHowever, in such case, the convergence of local search algorithms falls from a linear rate (r=r*) to a sublinear rate (r>r*).\nThe PreGD method proposed in this paper restores the linear convergence rate for the r>r* case.\nNumerically, it is also found that the PreGD method works well in restoring the linear convergence for some variants of the problem.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The major contributions of this paper are twofold:\n(1) the so called PreGD method;\n(2) It is shown that PreGD restores the linear convergence for an over-estimated rank.\n\nGeneral Comments:\n\n(1) The PreGD method, in my opinion, is not surprising, since it is quite natural to impose a regularizer \\eta to cure the ill-conditioning for the over-estimated case. In addition, in practice, after a few iterations of GD, the true rank r* can be revealed from the SVD of the current estimation of X, under the assumption that lambda_{r*}(M*) is larger than the noise. So, one may simply run GD for a few iterations with an overestimated rank at the beginning stage, then reveal the true rank r*, after that, continue to run GD with the true rank. So, the value of PreGD in practice is not significant.\n\n(2) The major contribution of this paper is (2) -- the theoretical analysis. The major results (corollary 5, Theorems 7 and 8) are all established under the assumption that a good initial guess of X is obtained from spectral initialization such that (17) holds. Let us consider the case when lambda_{r*} is small. The smaller lambda_{r*}, the more samples are needed to ensure (17) (by proposition 6). However, when M* has a low numerical rank that is much smaller than the true rank, the condition on m in proposition 6 will be too restrictive. Note that the overestimated rank case is quite similar to the low numerical rank case, I believe the results in this paper can be generalized to deal with the low numerical case, the term lambda_{r*}(M*)  in the  lower bound for m in proposition 6 will be replaced by some other eigenvalue of M* larger than a threshold.\n\n(3) Figure 2, why the error for PreGD stagnates? Is it because of the noise? This is unclear from the context. \n\n\nMinor comments:\n\nSome tyros need to be fixed, e.g.,\n\nLine 227, equation (16), a full stop is missing.\n\nLine 233, Lemma 4 —> Theorem 4 ?\n\nLine 237, theorem 5 —> corollary 5 ?\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "NA", "review_text": "", "extra_scores": {"ethical_concerns": "NA", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "KZC9B5vcmI6", "reviewer": "Reviewer_KAr6", "summary": "The authors consider low-rank matrix recovery problems, where the $n\\times n$ matrix variable $M$ is factorized as $M=XX^T$, for some $X$ of size $n\\times r$, with $r\\ll n$. It is known from previous work that, although they are typically non-convex, these problems can oftentimes be solved through simple gradient descent over $X$, applied to a suitable loss function.\n\nHowever, gradient descent tends to converge very slowly when either the ground true matrix is ill-conditioned, or the problem is overparameterized (that is, $r$ is strictly larger than the rank of the ground true matrix). In Reference [11], Tong, Ma and Chi have proposed a gradient preconditioner which solves the slow convergence issue when it is due to ill-conditioning. However, the method does not work when the problem is overparameterized.\n\nIn this article, the authors propose a refined preconditioner, which accommodates both ill-conditioning and overparameterization. In the particular setting of RIP matrix sensing with least-squares cost, they show that, with this preconditioner, gradient descent converges linearly in a neighborhood of the solution, up to the unavoidable statistical error.", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I liked this article.\n* It is well-written and pleasant to read.\n* I did unfortunately not find the time to read all proofs, but I read everything related to the noiseless case (until page 22 of the supplementary material), and found no issue.\n* The subject of the article is important: slow convergence of gradient descent in overparameterized settings is a significant obstacle for successfully using Burer-Monteiro methods in practice. Proposing an algorithm which is capable of overcoming this issue is therefore, in my opinion, a very valuable contribution, although its significance is limited by the fact that it is unclear to me whether the algorithm applies to other problems than RIP matrix sensing (see Remark 1 below).\n* The principle of the algorithm looks quite simple (the main idea is to add a very classical regularizer to the ScaledGD preconditioner), but proving that it works is rather involved.\n\nI have the following points of criticism.\n1. The fact that the damping parameter must satisfy Equation (1) looks like a rather strong constraint. The article explains how to find $\\eta_k$ satisfying this equation in the case of RIP matrix sensing, but RIP matrix sensing is a rather particular problem. I think it would be important to discuss whether this constraint prevents the algorithm from being applicable to other problems (which would significantly reduce its interest), or whether (and how) it can be overcome.\n2. Some clarifications in the setting would be welcome. In particular, the assumptions on the noise $\\epsilon$ should be explicitely stated at the beginning (otherwise, it is difficult to understand Proposition 6, for instance). I also did not find in the article the assumption $||A_i|| \\lesssim \\sqrt{n}$ used in the proof of Lemma 17.\n3. It seems to me that the proof of Lemma 14 can be significantly simplified (see the end of the review for a proposition of a simpler proof).\n4. I find Section 7 (Numerical experiments) a bit too short and confusing.\n   * Why did the authors choose the setting of their experiment as in Example 12 of reference [13]? The corresponding data matrices are very peculiar.\n   * A single example (although three different cost functions are considered, the underlying sensing operator is the same in each case), moreover in very small dimension, is not enough to establish that PrecGD works better than GD and ScaledGD.\n   * It seems that PrecGD stagnates: the error does not go to zero. This is especially visible on the figures of the first column. What happens?\n   * The experiment entangles three sources of difficulty: the ill-conditioning of the ground truth, the over-parameterization and the non-smoothness of the objective function. As a consequence, it is difficult to tell what exactly makes GD and ScaledGD fail or converge slowly. The fact that the figures in the first and second row of Figure 2 are quite similar gives the impression that the issues encountered by ScaledGD are not caused by overparameterization. Therefore, it does not illustrate the main message of the article (which is that PrecGD works better than ScaledGD when the problem is overparameterized).\n   * If PrecGD is able to successfully handle non-smooth objectives whereas GD and ScaledGD fail, this is very interesting, but also a bit mysterious. Would it be possible to provide at least an intuitive explanation?\n5. There are many typos in Appendix D.1. I recommend proofreading this subsection.\n\nIn addition, I have the following minor remarks.\n* Line 27: \"exists\" $\\to$ \"exist\"?\n* Line 59: \"suggests\" $\\to$ \"suggest\"\n* Line 89: \"logarithimic\" $\\to$ \"logarithmic\"\n* Line 90: space missing before \"$\\lambda_1$\"\n* Line 110: $\\sigma$ has not been previously defined.\n* The assertion at lines 118-119 is not correct. From my understanding of [31], the strict saddle property also holds in the over-parameterized regime. Indeed, Theorem 1.2 of [31] shows that, even in the over-parameterized regime, if the RIP constant is smaller than some threshold, then for any non globally optimal $X$, either $\\nabla f(X)\\ne 0$ or $\\nabla^2 f(X)\\not\\succeq 0$, which is to say that all non-optimal points have a descent direction.\n* Equation (4): \"$f^*=\\min f(X)$\" $\\to$ \"$f^*=\\min f$\" or \"$f^*=\\min_X f(X)$\".\n* Equation after line 164: I think there should be a factor \"$2$\" before \"$\\alpha$\".\n* Line 165: the value of $f(X_{k+1})$ is not correct.\n* Line 184: \"forces\" $\\to$ \"force\".\n* Line 188: \"$\\nabla f(X)(X^TX+\\eta I)$\" $\\to$ \"$\\nabla f(X)(X^TX+\\eta I)^{-1}$\"\n* Lines 196 and 531, and Equation (32): \"$\\eta$\" $\\to$ \"$\\eta I$\".\n* Equation (25): there should be no point at the end.\n* Line 208: \"the the\" $\\to$ \"the\".\n* Line 265: \"Candes\" $\\to$ \"Candès\"; \"any other estimator\" $\\to$ \"any estimator\"?\n* Line 289: \"$f(X)$\" $\\to$ \"$f(X_k)$\".\n* Equation (35): I think there should be no sum over $i$.\n* Between Lemmas 12 and 13: in my opinion, it should be explicitely said at the beginning that this is a high-level description of the proof, not a rigorous proof. In addition, this high-level description presents several issues because of which I could not understand it:\n  * Equation after line 583: I think the right-hand side is not correct (a scalar product is missing).\n  * Equation (37): the inequality is not correct. First, there is no reason why $\\sum_{i=k+1}^r \\lambda_i^2(X^TX)$ should be smaller than $\\lambda_{k+1}^2(X^TX)$. Second, Lemma 13 does not prove that $||Z^T(I-U_kU_k^T)Z||_F \\lesssim ||E||_F^2$: it proves that $||Z^T(I-U_kU_k^T)Z||_F \\lesssim ||E||_F$ (without the square).\n  * If $||E||\\_F^2 \\geq 1 $, then Equation (37) does not imply that $\\lambda_{k+1}(X^TX)$ is large whenever $\\sin(\\theta_k)$ is large.\n  * Line 593: what is $T_1$?\n* Equations (44) and (45): \"$\\lambda_{k+1}^2(X^TX)$\" should be \"$\\lambda_{k+1}(X^TX)$\".\n* I found it a bit difficult to understand the induction in the proof of Theorem 4; I recommend stating the inductive assumption explicitely.\n* Line 625: \"where we prove\" $\\to$ \"that is, we prove\"?\n* Second line of Equation (46): there is a factor $2$ missing.\n* Lines 641-642: what does \"the rank can be verified\" mean?\n* Line 645: the definition of $d$ is not correct (there is a mismatch between the dimensions of $\\Sigma_k^{-1}$ and the size of $e$); it should be $d=V_k\\Sigma_k^{-1}U_k^T$.\n* Problem after line 673, first line: there should be parentheses around $(1+\\delta)\\mathop{Tr}(V)-(1-\\delta)\\mathop{Tr}(U)$.\n* Line 674: I think that there should be a division by $||w||$ in the equality which defines $M(w)$.\n* Problem after line 674, first line: there should be no \"$(1+\\delta)$\".\n* Line 679: there are traces missing.\n* Line 691: if we assume that $k=r^*$, then $X_1,Z_1$ belong to $\\mathbb{R}^{r\\_* \\times r\\_* }$.\n* Equation after line 724: in the second line, I think the \"$||Z||\\_F$\" should be replaced with \"$||Z_2|\\|_F$\" (without this replacement the second inequality has no chance to hold when $Z_2=0$).\n\nSimpler proof of Lemma 14: Let $Y$ maximize the right-hand side of Equation (47). Let $W$ be the matrix corresponding to the orthogonal projection onto $\\mathrm{Range}(X)+\\mathrm{Range}(Z)$. If we set $\\tilde Y=W Y$, it holds that\n$$\\langle X\\tilde Y^T + \\tilde Y X^T, E\\rangle\n = \\langle X Y^T, E W\\rangle + \\langle Y X^T, W E\\rangle\n = \\langle X Y^T + Y X^T, E\\rangle$$.\nOn the other hand,\n$$ ||X\\tilde Y^T+\\tilde Y X^T||_F = ||W (XY^T+YX^T) W||_F \\leq ||XY^T+YX^T||_F$$\nand $||\\tilde Y||_P = ||WYP||_F \\leq ||YP||_F = ||Y||_P\\leq 1$.\nThis allows to show that $\\tilde Y$ also maximizes the right-hand side of Equation (47).\n\nSince $\\mathrm{Range}(\\tilde Y)\\subset \\mathrm{Range}(X)+\\mathrm{Range}(Z)$, the $(2r,\\delta)$-RIP implies\n$$\n|\\langle \\mathcal{A}(X\\tilde Y^T+\\tilde Y X^T),\\mathcal{A}(E)\\rangle -\n\\langle X\\tilde Y^T+\\tilde Y X^T,E\\rangle| \\leq\n\\delta ||X \\tilde Y^T + \\tilde Y X^T||\\\\,||E||.\n$$\nAs a consequence,\n$$ \\begin{align*}\n||\\nabla f(X)||_{P^*}\n& = \\underset{||Y||\\_P \\leq 1}{\\max} \\langle \\mathcal{A}(XY^T+YX^T),\\mathcal{A}(E)\\rangle \\\\\\\\\n& \\geq \\langle \\mathcal{A}(X\\tilde Y^T+\\tilde Y X^T),\\mathcal{A}(E)\\rangle \\\\\\\\\n& \\geq \\langle X\\tilde Y^T+\\tilde Y X^T,E\\rangle - \\delta ||X \\tilde Y^T + \\tilde Y X^T||\\\\,||E|| \\\\\\\\\n& = \\underset{||Y||_P \\leq 1}{\\max} \\langle X Y^T+ Y X^T,E\\rangle - \\delta ||X Y^T + Y X^T||\\\\,||E||.\n\\end{align*}$$\n\n**Added after author feedback**\n\nI thank the authors for adequately addressing my concerns, as well as for the discussion we had during the discussion period. I have increased my grade and hope the article will be accepted.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Not applicable to this article.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "C-AXONgWEQ", "reviewer": "Reviewer_Yim3", "summary": "This paper considers the problem of matrix sensing in the over-parameterized setting where the rank of the estimator is larger than that of the ground truth. A new algorithm called preconditioned gradient descent is proposed, and its performance is discussed both theoretically and numerically.", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, this paper is well-written and easy to read. The literature review is comprehensive, and the discussion about the limitation of prior art as well as the intuition of the proposed algorithm is very helpful.\n\nMy main concern is about the theoretical guarantee in the noisy setting (Theorem 8). The current error bound is not minimax optimal. It seems quite crude because authors simply adds up the three error terms that appear in the proof, and the sub-optimality might be attributed to the theoretical analysis.  It would improve the quality if authors can improve the error bound.\n\nTypo:\nTheorem 5 in Line 237 should be Corollary 5.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "5enCXLnngL", "reviewer": "Reviewer_bQAG", "summary": "This paper studies the problem of (noisy) nonconvex matrix factorization. The authors proposed an algorithm PrecGD that accommodates to over-parameterization and ill-conditioned ground truth.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n1. The paper proposes a novel algorithm that performs well in numerical experiments, accompanied with solid theoretical guarantees.\n2. The paper provides detailed high-level ideas and intuitions of their theory, which is helpful for those interested in their proof technique.\n\nWeakness / comments:\n1. The writing of this paper is not clear. Taking Section 5-6 as an example, I think it would be better to have a Section only presenting main results (Corollary 5, Proposition 6, Theorem 8), and this section should be self-contained. The intuitions / high-level ideas and the proof outlines can be deferred to earlier / later sections. The current version makes it difficult for readers to read the main result like Corollary 5 because necessary definitions required to understand Corollary 5 is spread out across the lengthy Section 5.\n2. The definition of $\\sigma$ first appeared in Theorem 7, but is already used in Proposition 6 and earlier in the main text. A definition is necessary before using this quantity.\n3. It seems that Theorem 7 allows the noise level $\\sigma$ to be arbitrarily large. I am skeptical about this as prior literature on matrix sensing usually prohibits the noise level from being too large, which usually reads $\\sigma\\sqrt{n/m}<<1$ under the setting of the current paper. \n4. How to obtain an approximation of the variance in Theorem 8? What is the order of $\\mathcal{E}_{var}$ in (21) under this approximation method? How does this quantity compared with two other quantities in (21)?\n5. If I understand the remarks under Theorem 8 correctly, when the sample size $m$ is large, the estimation error rate becomes sub-optimal. This is quite strange as large sample size, or large SNR, ususally makes the problem easier. Could you explain more details on why you can get an optimal rate when SNR is small, but fail to do so when SNR is large?\n6. I think maybe it is possible to estimate the rank precisely under the setting of Proposition 6. In that case, we no longer need to over-parameterize the model. Is that correct or not?\n\nTypos:\nTheorem 4 is sometimes cited as \"Lemma 4\".", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This is a theoretical work and I think there is no potential societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes regularized scaled gradient descent for low-rank matrix factorization. Particularly, it considers the scenarios where the model parameter r is an overestimation of the true rank r*. This is quite a common scenario. Though the scaling (and its regularized variant) is well-known (see papers from 2013 onwards based on numerical analysis or Riemannian metric selection), a deeper convergence analysis was missing that the paper presents. Though experiments are adequate for showing the good performance, some comparisons on real data would have been nice. Nevertheless, the reviewers agree that the paper has useful insights for NeurIPS community. 


Decision: Accept (Poster)