Accelerating SGD for Highly Ill-Conditioned Huge-Scale Online Matrix Completion
Authors: Gavin Zhang
Hong-Ming Chiu
Richard Y. Zhang
Venue: NeurIPS 2022 Accept (2022)
Keywords: huge scale optimization
stochastic gradient descent
SGD
scaled gradient descent
ScaledGD
preconditioned gradient descent
PrecGD

Abstract: The matrix completion problem seeks to recover a $d\times d$ ground truth matrix of low rank $r\ll d$ from observations of its individual elements. Real-world matrix completion is often a huge-scale optimization problem, with $d$ so large that even the simplest full-dimension vector operations with $O(d)$ time complexity become prohibitively expensive. Stochastic gradient descent (SGD) is one of the few algorithms capable of solving matrix completion on a huge scale, and can also naturally handle streaming data over an evolving ground truth. Unfortunately, SGD experiences a dramatic slow-down when the underlying ground truth is ill-conditioned; it requires at least $O(\kappa\log(1/\epsilon))$ iterations to get $\epsilon$-close to ground truth matrix with condition number $\kappa$. In this paper, we propose a preconditioned version of SGD that preserves all the favorable practical qualities of SGD for huge-scale online optimization while also making it agnostic to $\kappa$. For a symmetric ground truth and the Root Mean Square Error (RMSE) loss, we prove that the preconditioned SGD converges to $\epsilon$-accuracy in $O(\log(1/\epsilon))$ iterations, with a rapid linear convergence rate as if the ground truth were perfectly conditioned with $\kappa=1$. In our numerical experiments, we observe a similar acceleration for
ill-conditioned matrix completion under the root mean square error (RMSE) loss, Euclidean distance matrix (EDM) completion under pairwise square loss, and collaborative filtering under the Bayesian Personalized Ranking (BPR) loss.

Accelerating SGD for Highly IIl-Conditioned Huge-Scale Online Matrix Completion
Gavin Zhang
Hong-Ming Chiu
University of Illinois at Urbana CaaananChampaigh jialun20111inois.
University of Illinois at Urbana Urbana-Champaaa Champaign hmchiu2011linois. edu
Richard Y. Zhang
University of Illinois at Urbana- Chaampainn
ryz8illinois.co
Abstract
The matrix completion problem seeks to recover d d ground truth matrix of low rank < from observations of its individual elements. Real-world ma- trix completion is often huge-scale optimization problem, with d so large that even the simplest full-dimension vector operations with (()) time complexity be- come prohibitively expensive. Stochastic gradient descent (SGD) is one of the few algorithms capable of solving matrix completion on huge scale, and can also naturally handle streaming data over an evolving ground truth. Unfortunately, SGD experiences dramatic slow-down when the underlying ground truth is ill- conditioned; it requires at least OO log(1/e)) iterations to get e-close to ground truth matrix with condition number In this paper, propose a preconditioned version of SGD that preserves huge-scale online optimization while also making it agnostic to k. For sym- metric ground truth and the Root Mean Square Error (RMSE) loss, we prove that the preconditioned SGD converges to e-accuracy in (log (L/e) iterations, with a rapid linear convergence rate as if the ground truth were perfectly conditioned with 1. In our experiments, collaborative filtering on the MovieLens25M dataset via a pair-wise ranking loss, with 100 million training pairs and 10 million testing pairs. [See supporting code at https:://// //gtt/bbb.bt..t.// com/ Hanp/Hong-ine Saaknn/SScaleSGD,
the favorable practical qualities of SGD for
observe similar acceleration for item-item
Introduction
The matrix completion problem seeks to recover an underlying d x ground truth matrix M low rank r < d from observations of its individual matrix elements M. The problem appears most prominently in the context of collaborative filtering and recommendation system, but also numerous other applications. In this paper, focus the symmetric and positive semidefinite variant of the problem, in which the underlying matrix M can be factored as M ZZ where the factor matrix Z is d r, though that our methods have natural extensions to the nonsymmetric note that the symmetric positive semidefinite variant is actually far more common collaborative filtering, due to the prevalence item-item models, which enjoy better data (most platforms contain several orders of magnitude more users than items) and more stable recommendations (the similarity between items tends change slowly over time) than user-user and user-item models.
We
For the full-scale, online instances of matrix completion that arise in real-world collaborative fil- tering, stochastic gradient descent SGD is the only viable algorithm for learning the underlying matrix M. The basic idea is to formulate a candidate matrix of the form XX" with respect to a
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

learned factor matrix X E Rdx,, and to minimize cost function of the form o(X -M). Earlier
work used the root mean square error (RMSE) loss |XXX" M 1 = EXX" --xx""M), -M)
though
later work have focused on pairwise losses like the BPR [1] that optimize for ordering and therefore give better recommendations. For the RMSE loss, the corresponding SGD iterations with (rescaled) learning rate > reads
Fi,+ = x2 - a: 2g Mis) By, JJ.t = a. (x Mij) Ji:
where M.y is the sampled (it element of the ground truth matrix M, and 24, I and F5,+ F denote the i-th and j-th rows of the current iterate X, and new iterate Xe+1. Pairwise losses like the BPR can be shown to have similar update equation over three rows of X [1]. Given that only two or three rows of X are accessed and updated at any time, SGD is readily accessible to massive parallelization and distributed computing. For very large values of d, the update equation (I) can be run by multiple workers in parallel without locks, with vanishing probability of collision [2]. The blocks of X that are more frequently accessed together can be stored on the same node in a distributed memory system.
Unfortunately, the convergence rate of SGD can sometimes be extremely slow. One possible expla- nation, as many recent authors have pointed out [3-6], is that matrix factorization models are very sensitive to ill-conditioning of the ground truth matrix M. The number of SGD iterations grows at least línearly the condition number which here is defined as the ratio between the largest and the r-th largest singular values of M. Ill-conditioning causes particular concern because most real- world data are ill-conditioned. In one widely cited study [7], it was found that the dominant singular value accounts for only 8=80% prediction accuracy, with diversity of individual preferences making up the remainder ill-conditioned singular values. Cloninger et al. [8] notes that there are certain applications of matrix completion that have condition numbers as high as k- = 1005_
This paper is inspired by recent full-batch gradient method called ScaledGD [4. 9] and closely related algorithm PrecGD [5] in which gradient descent is made immune to ill-conditioning in the ground truth by right-rescaling the full-batch gradient by the matrix (XT X)-1. Applying this same strategy to the SGD update equation (1) yields the row-wise updates
Fi,+ = T; - a. (I. æ
M,j) Pxş, Ij+t = 2j - a (x x3
Ma) Px.,
(2a)
in which we precompute and cache the preconditioner P = (X=X)- ahead of time', and update it after the iteration as
P_ P==(P + + + T + xy x,,- xtoe x -z,z5)-
(2b)
by making four calls to the Sherman-Morrison rank-1 update formula
P
(P- - uu ) = Puu P
(P + uu -u=))=-= = 1+ w² Pu
n" Pu.
This way, the rescaled update equations use just O(r²) arithmetic operations, which for modest values of is only marginally more than the O(r) cost of the unscaled update equations (1). Indeed, the nearest-neighbor algorithms inside most collaborative filters have exponential complexity with respect to the latent dimensionality r, and so are often implemented with r small enough for (1) and (2) to have essentially the same runtime. Here, we observe that the rescaled update equations (2) preserve essentially all of the practical advantages of SGD for huge-scale, online optimization: it can also be run by multiple workers in parallel without locks, and can also be easily implemented over distributed memory. The only minor difference is that separate copies of P should be maintained by each worker, and resynchronized once differences grow large.
Contributions In this paper, we provide rigorous proof that the rescaled update equations (1), which we name ScaledSGD, become immune to the effects of ill-conditioning in the underlying ground truth matrix. For symmetric matrix completion under the root mean squared error (RMSE) loss function, regular SGD is known to have an iteration count of O(k² dr log (d/e)) within a local neighborhood of the ground truth [10]. This figure is optimal in the dimension d, the rank
'oor an initialization, if the d rows of Xo selected from the unit Gaussian as in Iiy..., Rd N(0, o² I.), then we can simply set Pa = o²T without incurring the ((d) time needed in explicitly com- puting Po = (XF (x)xx)- -1.

---

and the final accuracy e, but suboptimal by four exponents with respect to condition number R. In contrast, we prove for the same setting that ScaledSGD attains an optimal convergence rate, converging to 6-accuracy in O(r (d) iterations for all values of the condition number k. In fact, our theoretical result predicts that ScaledSGD converges as if the ground truth matrix perfectly conditioned, with a condition number of k 1.
At first sight, it appears quite natural that applying the ScaledGD preconditioner to SGD should result in accelerated convergence. However, the core challenge of stochastic algorithms like SGD is that each iteration can have substantial variance that "drown out" the expected progress made in the iteration. In the case of ScaledSGD, a rough analysis would suggest that the highly ill-conditioned preconditioner should improve convergence in expectation, but the cost of dramatically worsening the variance.
Surprisingly, we find in this paper that the specific scaling (XTX)-1 used in ScaledSGD not only does not worsen the variance, but in fact improves it. Our key insight and main theoretical contri- bution Lemma 4, which shows that the same mechanism that allows ScaledGD to converge faster (compared to regular GD) also allows ScaledSGD to enjoy reduced variance (compared to regular SGD). In fact, is this effect of variance reduction that is responsible for most (s3 out of x*) of our improvement over the previous state-of-the-art. It turns out that a careful choice of preconditioner can be used as a mechanism for variance reduction, while at the same time also fulfilling its usual, classical purpose, which is to accelerate convergence in expectation.
Related work Earlier work on matrix completion analyzed convex relaxation of the original problem, showing that nuclear norm minimization can recover the ground truth from a few incoher- ent measurements [11-15]. This approach enjoys a near optimal sample complexity but incurs an O(d)) per-iteration computational cost, which is prohibitive for a even moderately large d. More recent work has focused more on a nonconvex formulation based on Burer and Monteiro [16], which factors the optimization variable as M XXX" where X E Rdxr and applies local search method such as allernatig-miniiizztioon [17-20], projected gradient descent [21, 22] and regular gradient descent [23-26]. A separate line of work [27-35] focused on global properties of nonconvex matrix recovery problems, showing that the problem has no spurious local minima if sampling operator satisfies certain regularity conditions such as incoherence or restricted isometry.
The convergence rate of SGD has been well-studied for general classes of functions [36-39]. For matrix completion in particular, Jin et al. [10] proved that SGD converges towards an e-accurate solution in (d log(1/)) iterations where K is the condition number of M. Unfortunately, this quartic dependence on R. makes SGD extremely slow and impractical for huge-scale applications.
This dramatic slow down of gradient descent and its variants caused by ill-conditioning has become well-known in recent years. Several recent papers have proposed full-batch algorithms to overcome this issue [9, 40, 41], but these methods cannot be used in the huge-scale optimization setting where is so large that even full-vector operations with (dd time complexity are too expensive. As deterministic full-batch method, ScaledGD [9] requires a projection onto the set of incoherent matrices at every iteration in order to maintain rapid convergence. Instead our key finding here is that the stochasticity of SGD alone is enough to keep the iterates incoherent the ground truth, which allows for rapid progress to be made. The second-order method proposed in [41] costs at least O(d) per-iteration and has no straightforward stochastic analog. PrecGD [5] only applies to matrices that satisfies matrices satisfying the restricted isometry property, which does not hold for matrix completion.
2 Background: Linear convergence of SGD
In our theoretical analysis, we restrict our attention to symmetric matrix completion under the root mean squared error (RMSE) loss function. Our goal is solve the following nonconvex optimiza- tion
min f(x) def |Xxx - 12 XER
where Z = [21, 22,.... 1T. E dxd
(3)
in which we assume that the d x d ground truth zZT 1 0 matrix is exactly rank-r, with a finite condition number
def
>max (ZZ")/2,ZZ")
Amax (z" /)/ ( < c0.
(4)
3

---

In order to be able to reconstruct Zz" from a small number of measurements, we will also need to assume that the ground truth has small coherence [42]
def
max 15i5d
(5)
Recall that j takes value from 1 to d/r. with the smallest achieved by dense, orthonormal choices of Z whose rows all have magnitudes of 1/vd, and the largest achieved by ground truth ZZ containing a single nonzero element. Assuming incoherence μ = O(1) with respect to d, well-known result that all df matrix elements of zz can be perfectly reconstructed from just (dr log d) random samples of its matrix elements [12, 43].
This paper considers solving (3) in the huge-scale, online optimization setting, in which individual matrix elements of the ground truth (ZZ") 2 2j are revealed one-at-a-time, uniformly at random with replacement, and that a current iterate X is continuously updated to streaming data. We note that this is a reasonably accurate model for how recommendation engines are tuned to user preferences in practice, although the uniformity of random sampling is admittedly an assumption made to ease theoretical analysis. Define the stochastic gradient operator as
SG(X) 2d (xf 2 (e,ay + +eaaf) where (i.j) ~ Unif([d] x [d])
where F; Fj E RD' are the i-th and j-th rows of X, and the scaling d2 is chosen that, over the randomness of the sampled index (i, j). we have exactly B[SG(X)) f(()). Then, the classical online SGD algorithm can be written as
X1+1 = X, - aSG(X,) where ar > O.
(SGD)
Here, we observe that single iteration of SGD coincides with full-batch gradient descent in pectation, as in [ = X, (Xx)) Therefore, assuming that bounded deviations and bounded variances, it follows from standard arguments that the behavior of many iterations of SGD)
should concentrate about that of full-batch gradient descent X = X₁ f
Within region sufficiently close to the ground truth, full-batch gradient descent is well-known to converge at a linear rate to the ground truth [23, 44]. Within this same region, Jin et al. [10] proved that SGD also converges linearly. For incoherent ground truth with μ (1), they proved that SGD with an aggressive choice of step-size is able to recover the ground truth to e- accuracy O(k* dr log(d/c)) iterations, with each iteration costing O(r) arithmetic operations and selecting random sample. This iteration count is optimal with respect to d, r, and 1/e, although its dependence
x is cubic factor (i.e. factor of Λ²) worse than full-batch gradient descent's figure of (x log(1 (1/e)), which is itself already quite bad, given that k in practice can readily take on values of 10s 10".
Theorem 1 (Jin, Kakade, and Netrapalli [10]. For 2 Rdx with T (7) = 1 and f(X) ||XXT- - 77 1/ and (x, ||e]" X|2,, define the following
fmax
def
hmax
def 20
2² pr d
10K
For an initial point Xo E RRd that satifies f((x)) S mmxx and max; hi (Xo) S 2 L.maae there
exists some constant e such that for any learning rate a < c- (R hmax d2 log d) with probability least T/ we will have for all t < T iterations of SGD that
a )
f(X)) 1
fmax:
max ( S hmax-
2
The reason for Theorem I's additional x3 dependence beyond full-batch gradient descent due to its need to maintain incoherence in its iterates. Using standard techniques martingale concen- tration, one can readily show that SGD replicates single iteration of full-batch gradient descent over epoch of dl iterations. This results in an iteration count O(k dd log(1/e)) with an optimal dependence on k, but the entire matrix is already fully observed after collecting df samples. Instead, Jin et al. [10] noted that the variance of SGD iterations is controlled by the step-size times the maximum coherence μxx = $ maxi,t /le/ X. over the iterates Xt, Xy-1..... Xo. If the iterates can be kept incoherent with yax O(1), then SGD with more aggressive step-size will reproduce an iteration of full-batch gradient descent after epoch of just O(dr log d) iterations.

---

The main finding in Jin et al. [10]'s proof of Theorem is that the stochasticity of SGD is enough to keep the iterates incoherent. This contrasts with full-batch methods the time, which required an added regularizer [20, 30, 45] an explicit projection step [9]. (As pointed out by a reviewer, it was later shown by Ma et al. [46] that full-batch gradient descent also able to maintain incoherence without a regularizer nor projection.) Unfortunately, maintaining incoherence requires shrinking the step-size by a factor of K, and the actual value of px that results is also a factor of x² worse than the original coherence μ of the ground truth Z. The resulting iteration count O(x² dr log(d/e)) is made optimal with respect to d, T; and 1/e, but only at the cost of worsening its the dependence on the condition number by another three exponents.
Finally, the quality of the initial point Xy also has dependence on the condition number R. In order to guarantee linear convergence, Theorem requires Xo to lie in the neighborhood [|xxX] I < Amin () = ). This dependence on x optimal, because full- batch gradient descent must lose its ability to converge linearly in the limit -> oo [5, 6]. However, the leading constant can be very pessmistic, because the theorem must formally exclude spurious critical points Xspur that have f In practice, it is commonly observed that SGD converges globally, starting from an arbitrary, pos- sibly random initialization [30], at a linear rate that is consistent with local convergence theorems like Theorem 1. It is now commonly argued that gradient methods can escape saddle points with high probability [47], and so their performance is primarily dictated by local convergence behav- ior [48, 49].
0 but f(Xapur) O in order to be provably correct.
3 Proposed algorithm and main result
Inspired by a recent full-batch gradient method called ScaledGD [4, 9] and a closely related algo- rithm PrecGD [5], we proposed the following algorithm
X441 X₁ (x)
where a >> O.
(ScaledSGD)
As we mentioned in the introduction, the preconditioner P (X" can be precomputed and cached in practical implementation, and afterwards efficiently updated using the Sherman- Morrison formula. The per-iteration cost of ScaledSGD is Or²²) arithmetic operations and I random sample, which for modest values of is only marginally more than the cost of SGD.
Our main result in this paper that, with region sufficiently close to the ground truth, this simple rescaling allows ScaledSGID to converge linearly to e-accuracy Odr log(d/e)) iterations, with no further dependence on the condition number This iteration count is optimal with respect d, 1/c, and к, and in fact matches SGD with perfectly conditioned ground truth x = 1. In our numerical experiments, we observe that ScaledSGD converges globally from a random initialization at the same rate as SGD as if K = 1.
Theorem 2 (Main). For Z E Rddr with m (Z) = 1 and f(X) = |XXX 22T 12 and (x( = c. X(x"x) X e,, select a radius < 1/2 and set
fmax def (2)²
def
24
pr
Jmax
(1 - 2p) d'
For an initial point Xo RRdxr that satifies f(Xo) S fmmx and max; gi (o)) S Zymaxx there exists some constant C such that for any learning rate a <. [9max + p) d log d] d|-1, with probability at least - do we will have for all t < T iterations of ScaledSGD that:
f(X.) < (1- fmax:
max maxx9;(X) (X,, S Imax.
Theorem 2 eliminates all dependencies on the condition number in Theorem I except for the quality of the initial point, which we had already noted earlier as being optimal. Our main finding is that it is possible to maintain incoherence while making aggressive step-sizes towards highly ill-conditioned ground truth Z ZZ In fact, Theorem says that, with high probability, the maximum coherence y over of any iterate X, will only be mild constant factor of x 16 times worse than the coherence f of the ground truth ZZT. This particularly surprising in view of the fact that every iteration of ScaledSGD involves inverting potentially highly ill-conditioned matrix (XT x)-1 In
5

---

contrast, even without inverting matrices, Theorem I says that SGD is only able to keep μx within a factor of x² of μ. and only by shrinking the step-size by another factor of k.
However, the price we pay for maintaining incoherence is that the quality of the initial point X now gains dependence dimension d, in addition to the condition number K. In order guarantee fast linear convergence independent of k. Theorem 2 requires Xo to lie in the neighborhood || Z < pr>xin (Z 2)/d (wad)-1 so that p can be set to be the same order of magnitude as Imax. In essence, the "effective" condition number of the ground truth has been worsened by another factor of d. This shrinks the size of our local neighborhood by a factor of d, but has no impact on the convergence rate of the resulting iterations.
In the limit that + and the search rank becomes overparameterized with respect the true rank r" < r Zz", both full-batch gradient descent and SGD slows down to a sublinear conver- gence rate, in theory and in practice [5. 6]. While Theorem 2 is longer applicable, our numerical experiments that ScaledSGI) nevertheless maintains its fast linear convergence rate as if K Following PrecGD [5], we believe that introducing small identity perturbation the scaling matrix of ScaledSGD, in (X* + n//) for some 1) as vT(X). should be enough to rigorously extend Theorem 2 to the overparameterized regime. We leave this extension as future work.
observe in
4 Key ideas for the proof
We begin by explaining the mechanism by which SGD slows down when converging towards an ill-conditioned ground truth. Recall that
[X)] = 1F(2d (xx* 2z" )as (ecef + +efef) = 4(xx² xx VX()).
As X converges towards an ill-conditioned ground truth Zz the factor matrix X must become progressively ill-conditioned, with
IXX - ZZ" IIXX 1 1+p
Amin (x") = x
K
Therefore, it is possible for components of the error vector XX" - -2 to become "invisible" by aligning within the ill-conditioned subspaces of X. As SGD progresses towards the solution, these ill-conditioned subspaces of X become the slowest components of the error vector to converge to zero. On the other hand, the maximum step-size that can be taken is controlled by the most well- conditioned subspaces of X. A simple idea, therefore, is to rescale the ill- ill-conditioned components of the gradient (XX in order to make the ill-conditioned subspaces of X more "visible".
More concretely, define the local norm of the gradient | = (XX(x) Ir and its corresponding dual norm as [Xx [[V 1/2 F. It has long been known (see e.g. [23, 44]) that rescaling the gradient yields
| def ||4(X"" zz" )xx" 1/2
x)-122) 1
cos 0. ||XX - -ZZ 1
where 0 is the angle between the error vector XXT zzT and the linear subspace (XYT +YXT: Y E Rddr). This insight immediately suggests an iteration like X+ X (XX(X)(XXX) In fact, the gradients of have some Lipschitz constant L, so
L 2 2 -X
((X+) ((X) V/
Lx a² (IV[(()) 2
$ f(x) - -(IVV
S [1 a coss 8] f(x)
for a S 1/Ixx.
However, a naive analysis finds that Lx = L/>min (X"X) x L K. and this causes the step-size to shrink by a factor of K. The main motivating insight behind ScaledGD [4. 9] and later PrecGD [5] is that, with a finer analysis, it is possible to prove Lipschitz continuity under a local change of norm.
Lemma 3 (Function descent). Let X, Z nx satisfy |XXXT_ - zzT I| S pdmiu (ZT Z) where p < 1/2. Then, the function fXX = |XXx 1 satisfies
(Vf())((((X))))..))))))))))))))) V) + Lx I 2
(IVI(X)) 13-f(x)

---

for all |VI|x C.. Vf(X) with Lx = 6 6 80+2
This same idea can be "stochastified" in straightforward manner. Conditioning on the current iterate X, then the new iterate X+ = X aSG(()(X' has expectation
Lx [(([5G(X))1)))
B[((x+) S S(X) a (IVG
+
2
The linear term evaluates as (E(G((X)XX X while the quadratic term is
Σ 4d (Xx* 222 4 40.4maxxlee (Iee) xIIx)² -16- ((X) max (X(,,,
where (x( = X -x (1 Combined, we obtain geometric convergence [X)( < (1 a1-a -1- cos? 0) s(x)
for O d dd²))
We see that the step-size depends crucially on the incoherence (x)) S Imax of the current iterate. If the current iterate X incoherent with Imax O(1/d), then a step-size of
((1dd) is possible, resulting in convergence in Odr (og(d/c) iterations, which can be shown using standard martingale techniques [10]. But if the current iterate Imax O(), then only a step-size of = (()/d²) is possible, which forces us to compute d2 iterations, thereby obviating the need to complete the matrix in the first place.
Therefore, in order for prove rapid linear convergence, we need to additionally show that with high probability, the coherence g& (X)=<(le{ xIxx remains (1) throughout ScaledGD iterations. This is the most challenging part of our proof. Previous methods that applied similar scaling to full- batch GD [9] required an explicit projection onto the set of incoherent matrices at each iteration. Applying a similar projection to ScaledSGD will take O(d) time, which destroys the scalability of our method. On the other hand, Jin et al. [10] showed that the randomness in SGD is enough to keep the coherence of the iterates within a factor of n² times worse than the coherence of the ground truth, and only by a step-size of at most a 0(x²))
Surprisingly, here we show that the randomness in ScaledSGI is enough to keep the coherence of the iterates with constant factor of the coherence the ground truth, using a step-size with depen- dence on K. The following key lemma is the crucial insight of our proof. First, it says that function (X) satisfies a "descent lemma" with respect the local norm ||- l Second, and much more importantly, it says that descending 9u (X) along the scaled gradient direction Vf(X)(X"X) incurs linear decrement 1-2e g& (X) with dependence of the condition number K. This is in direct analogy to the function value decrement in (6), which has no dependence on K, and in direct contrast to the proof of Jin et al. [10], which is only able to achieve a decrement of (8/ (5/K))((A due the lack of rescaling by (X" X)-
Lemma 4 (Coherence descent). Let 9x = of xXX X Cx. Under the same conditions as Lemma 3, we have
5(
9h X +V) & 9h (x) - (V, (X))
+ - 2 2
2p
(X)( >
1 (X)
1 v (x (Z)
Conditioning on X, we have for the search direction V SG(X) and X+ x
(1IV1)))2
E[gx((+)) S go (X) a(Vg
+ E
V
- 2p
( (2) + a2 E [(IVV)))) )²]
1
1 1- a
(x) + +a: 1-p P
1- 2 V 11x
1 1 1- 2p
1 1- a) gx(X) +a V Imaxx
Imax + a² O(d -max p²) 1-p
0 1/2
p)
< (1 (1- (a) (X) +a 5
for a = O(p 22)
Imax
2
7

---

It then follows that gt (X+) converges geometrically towards 29max in expectation, with a conver- gence rate (1 {a) that independent the condition number K:
1 Blgg (X+) 2 -max < (1 (a) (x( + a
1 2 9max - <1 (1- (xx(X)
1
2 2max
2 9max
The proof of Theorem 2 then follows from standard techniques, by making the two decrement con- ditions (6) and (7) into supermartingales and applying a standard concentration inequality. We defer the rigorous proof to appendix E.
Experimental validation
In this section we compare the practical performance of ScaledSGD and SGD for the RMSE loss function in Theorem and two real-world loss functions: the pairwise RMSE loss used to complete Euclidean Distance Matrices (EDM) in wireless communication networks; and the Bayesian Per- sonalized Ranking (BRP) loss used to generate personalized item recommendation filtering. In each case, ScaledSGD remains highly efficient since it only updates two three rows at time, and the preconditioner P can be computed through low-rank updates, for a per-iteration random Gaussian initializations and initial P = I²I.
collaborative
cost of (r²²). All of our experiments To be able to accurately measure and report the effects of illccondiiin on ScaledSGD and SGD, focus small-scale synthetic datasets in the first two experiments, for which the ground truth is explicitly known, and where the condition numbers can be finely controlled. In addition, to gauge the scalability of ScaledSGI) on huge-scale real-world datasets, in the third experiment, we apply ScaledSGD to generate personalized item recommendation using Moviel dataset [50], for which the underlying item-item matrix has more than 62,000 items and 100 million pairwise sam- ples are used during training. (Due to space constraints, we defer the details on the experimental setup, mathematical formulations, and the actual update equations Appendix A.) The code for all experiments are available at https: / thub. com Beap//oongMMMnnSSMe Ming/ScaledSGD.
Matrix completion with RMSE loss. The problem formulation is discussed in Section 3. Figure plots the error f(X) = || XXX M as the number of epochs increases. As expected, in the well-conditioned case, both ScaledSGD and SGD converges machine error at roughly the same linear rate. However, in the ill-conditioned case, SGD slows down significantly while ScaledSGD converges at almost exactly the same rate in the well-conditioned case.
Well-conditioned
Il-conditioned
10
102
ScaledSGD SGD
ScaledSGD SGD
10:2
10:2
10
10 6
(()
10
10
10 14
10 14
10
18
0
50
100
150
200
0
50
100
150
200
Epochs
Epochs
Figure 1: Matrix Completion with RMSE loss. We compare the convergence rate of ScaledSGD
and SGD for well-conditioned and ill-conditioned ground truth matrix of size 30 x 30 and rank 3. (Left) Well-conditoned M, x(M) = 1. Step-size a = 0.3. Both ScaledSGD and SGD converges quickly to the ground truth. (Right) Ill-conditoned M, s(M) = 10a, Step-size stagnates while ScaledSGD retains the same convergence rate as the well-conditioned case.
0.3. SGD
Euclidean distance matrix (EDM) completion. The Euclidean distance matrix (EDM) is ma- trix of pairwise distance between d points Fuclidean space [51]. In applications such as wireless sensor networks, estimation of unknown distances, i.c., completing the EDM is often required. We
8

---

emphasize that this loss function is a pairwise loss, meaning that each measurement indexes multiple elements of the ground truth matrix.
To demonstrate the efficacy of ScaledSGD, we conduct two experiments where D is well- conditioned and ill-conditioned respectively: Experiment 1. We uniformly sample 30 points in a cube center at origin with side length 2, and use them to compute the ground truth EDM D. In this case, each row I; R$ corresponds the coordinates of the i-th sample. The corresponding matrix X E 13003 is well-conditioned because of the uniform sampling. Experiment 2. The ground truth EDM generated with 25 samples lie the same cube in experiment 1, and samples lie far away from the the cube. These five outliers make the corresponding X become ill-conditioned.
Sample Positions (Uniform in Cube)
Sample Positions (With Outliers)
Samples
Samples
Outlier
Y
X
Y
Uniform in Cube (Well- )onditionn)))
With Outliers (III- (Il-Conditioned)
10
102
ScaledSGD SGD
ScaledSGD
SGD
10
10
10 6
10 6
f(x)
10
10
10.14
10-14
10 18
10
18
100
200
300
400
500
0
100
200
300
400
500
Epochs
Epochs
Figure 2: Euclidean distance matrix (EDM) completion. We compare the convergence rate of ScaledSGD and SGD for EDM completion for two set of samples. (Upper right) 30 samples are uniformly distributed in the pink cube center at origin. (Upper left) 25 samples (in blue) are uniformly distributed in the cube, 5 outlier samples (in orange) are outside of the cube. (Lower left) Sample uniformly in cube. (Lower right) Sample with outliers.
Item-item collaborative filtering (CF). In the task of item-item collaborative filtering (CF), the ground truth M is d x matrix where d is the number of items we wish to rank and the i, j-th of M is similarity measure between the items. Our goal is to learn a low-rank matrix that preserves the ranking of similarity between the items. For instance, given a pairwise sample (i. j. k), if item i is more similar to item j than item k. then My > Mik. We want to learn a low-rank matrix that also has this property, i.c., the i, j-t entry is greater than the i, k-th entry.
To gauge the scalability of ScaledSGD on a huge-scale real-world dataset, we perform simulation on item-item collaborative filtering using a 62, 000 x 62, 000 item-item matrix M obtained from MovieLens25M dataset. The CF model is trained using Bayesian Personalized Ranking (BRP) loss [1] on a training set, which consists of 100 million pairwise samples in M. The performance of CF model is evaluated using Area Under the ROC Curve (AUC) score [1] on a test set, which consists of 10 million pairwise samples in M. The BPR loss is a widely used loss function in the context of collaborative filtering for the task of personalized recommendation, and the AUC score is

---

popular evaluation metric to measure the accuracy of the recommendation system. We defer the detail definition of BPR loss and AUC score Appendix A.4.
Figure plots the training BPR loss and testing AUC score within the first epoch (filled with red) and the second epoch (filled with blue). In order measure the efficacy of ScaledSGD, we compare its lesting AUC score against a standard baseline called the NP-Maximum [1], which is the best possible AUC score by non-personalized ranking methods. For a rigorous definition, see Appendix A.4.
We emphasize two important points in the Figure 3. First, the percentage of training samples needed for ScaledSGD to achieve the same testing AUC scores NP-Maximum is roughly 4 times smaller than SGD. Though both ScaledSGD and SGD are able to achieve higher AUC score than NP-Maximum before finishing the first epoch, ScaledSGD achieve the same AUC score NP- Maximum after training on 11% of training samples while SGD requires 46% of them. We note that in this experiment, the size of the training set is 100 million, this means that SGD would require 35 million more iterations than ScaledSGI) before it can reach NP-Maximum.
Second, the percentage of training samples needed for ScaledSGD to converge after the first epoch roughly 5 times smaller than SGD. Given that both ScaledSGD and SGD converge to AUC score at around 0.9 within the second epoch (area filled with blue), we indicate the percentage of training samples when both algorithms reach 0.9 AUC score in Figure 3. As expected, ScaledSGD is able to converge using fewer samples than SGD, with only 16% of training samples. SGD, the other hand, requires 81% training samples.
Training BPR Loss
Testing AUC Score
1.2
ScaledSGD
SGD
0.9
BPR Loss
AUC Score
0.8
0.8
0.6
0.7
ScaledSGD
0.4
0.6
SGD
NP-Maximum
0.2
0.5
Epochs
Epochs
Figure 3: Huge-scale item-item collaborative filtering. (Moviel.en225M dataset with [Qrmin|
100 million and Rees 10 million pairwise measurements). We compare the training BPR loss and testing AUC score of ScaledSGD and SGD. (Left) Training BPR loss on the training set Paruin- (Right) Testing AUC score on the test set P
6 Conclusions
We propose an algorithm called ScaledSGD for huge scale online matrix completion. For the non- convex approach to solving matrix completion, ill-conditioning in the ground truth causes SGD to slow down significantly. ScaledSGD preserves all the favorable qualities of SGD while making immune ill-conditioning. For the RMSE loss, prove that with an initial point close to the ground truth, ScaledSGD converges to an c-accurate solution in (log(1/c) iterations, independent of the condition number k. We also numerical experiments tions commonly used in applications such as collaborative filtering, distance matrix recovery, etc. We find that ScaledSGD achieves similar acceleration on these losses, which means that it is widely applicable to many real problems. It remains future work to provide rigorous justification for these observations.
wide range of other loss func-
10

---

Acknowledgments
The authors thank Salar Fattahi for helpful discussions and feedback on an earlier draft. Financial support for this work was provided in part by the NSF CAREER Award ECCS-2047462 and in part by C3.ai Inc. and the Microsoft Corporation via the C3.ai Digital Transformation Institute.
References
[1] Steffen Rendle, Christoph Freudenthaler, Zeno Gantner, and Lars Schmidt-Thieme Bpr: Bayesian personalized ranking from implicit feedback. arXiv preprint arXiv:/205.266 2012.
[2] Benjamin Recht, Christopher Re, Stephen Wright, and Feng Niu. Hogwild!: A lock-free ap- proach to parallelizing stochastic gradient descent. Advances neural information processing systems, 24, 2011.
[3] Qinqing Zheng and John Lafferty. Convergence analysis for rectangular matrix completion using burer-monteiro factorization and gradient descent. arXiv preprint arXiv: 2016.
[4] Tian Tong, Cong Ma, Ashley Benter-Bennette,, Erin Tripp, and Yuejic Chi. Scaling and scalabil- ity: Provable nonconvex low-rank tensor completion. In International Conference on Artificial Intelligence and Statistics, pages 2607-2617. PMLR, 2022.
[5] Jialun Zhang, Salar Fattahi, and Richard Y Zhang. Preconditioned gradient descent for over- parameterized nonconvex matrix factorization. Advances in Neural Information Processing Systems, 34:5985-5996, 2021.
[6] Jiacheng Zhuo, Jeongyeol Kwon, Nhat Ho, and Constantine Caramanis. On the compu- tational and statistical complexity of over-parameterized matrix sensing, arXiv preprint arXiv:2102.02756. 2021.
[7] Michal Kosinski, David Stillwell, and Thore Graepel. Private traits and attributes are pre- dictable from digital records of human behavior. Proceedings of the national academy of sciences, 1 (10(15):58025888 2013.
[8] Alexander Cloninger, Wojeiech Czaja, Ruiliang Bai, and Peter Basser. Solving 2d fredholm integral from incomplete measurements using compressive sensing. SIAM journal imaging sciences, 7():1175-1798, 2014.
[9] Tian Tong, Cong Ma, and Yuejie Chi. Accelerating ill-conditioned low-rank matrix estimation via scaled gradient descent. Journal of Machine Learning Research, 22(150): 2021.
[10] Chi Jin, Sham M Kakade, and Praneeth Netrapalli. Provable efficient online matrix comple- tion via non-convex stochastic gradient descent. Advances in Neural Information Processing Systems, 29, 2016.
[11] Emmanuel J Candes and Yaniv Plan. Matrix completion with noise. Proceedings of the IEEE, 98(6):925-936 2010.
[12] Emmanuel J Candès and Terence Tao. The power of convex relaxation: Near-optimal matrix completion. IEEE Transactions on Information Theory, 56(5):2053-22885 2010.
[13] Benjamin Recht, Maryam Fazel, and Pablo A Parrilo. Guaranteed minimum-rant -ran solutions of linear matrix equations via nuclear norm minimization. SIAM review, 5200) 2010.
[14] Nathan Srebro and Adi Shraibman. Rank, trace-norm and max-nome In International Confer- ence on Computational Learning Theory, pages 545-560. Springer, 2005.
[15] Sahand Negahban and Martin J Wainwright. Restricted strong convexity and weighted matrix completion: Optimal bounds with noise. The Journal of Machine Learning Research, 13(1): 1665-1697, 2012.
11

---

[16] Samuel Burer and Renato DC Monteiro. A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization. Mathematical Programming. 95(2):329- 357, 2003.
[17] 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.
[18] Moritz Hardt and Mary Wootters, Fast matrix completion without the condition number. In Conference on learning theory, pages 638-6 (78.678.77 PMLR, 2014.
[19] Moritz Hardt. Understanding alternating minimization for matrix completion. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pages 651-660. IEEE, 2014.
[20] Ruoyu Sun and Zhi-Quan Luo. Guaranteed matrix completion via non-convex factorization. IEEE Transactions on Information Theory, 62(1 1):66))-66575) 2016.
[21] Yudong Chen and Martin Wainwright. Fast low-rank estimation by projected gradient de- scent: General statistical and algorithmic guarantees. arXiv preprint arXiv: 1509.03055 2015.
[22] Prateek Jain and Praneeth Netrapalli. Fast exact matrix completion with finite samples. In Conference on Learning Theory, pages 1007-1034. PMLR, 2015.
[23] 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 Learming, pages 964-973. PMLR, 2016.
[24] Srinadh Bhojanapalli, Anastasios Kyrillidis, and Sujay Sanghavi. Dropping convexity for faster semi-definite optimization. Conference on Learning Theory, pages 530-582, PMLR, 2016.
[25] Emmanuel J Candes, Xiaodong Li, and Mahdi Soltanolkotabi. Phase retrieval via wirtinger flow: Theory and algorithms. IEEE Transactions on Information Theory, (14: 2007, 2015.
[26] Jianhao Ma and Salar Fattahi. Implicit regularization of sub- gradient method in robust matrix recovery: Don't be afraid of outliers. arXiv preprint 1.Xiv:2/02.02990 2021.
[27] Srinadh Bhojanapalli, Behnam Neyshabur, and Nathan Srebro. Global optimality of local search for low rank matrix recovery. arXiv preprint arXiv.1605.07221, 2016.
[28] Qiuwei Li, Zhihui Zhu, and Gongguo Tang. The non-convex geometry of low-rank matrix optimization. Information and Inference: Journal of the IMA, 8(1):51-96, 2019.
[29] Ju Sun, Qing Qu, and John Wright. A geometric analysis of phase retrieval. Foundations of Computational Mathematics, 18(5): 131-1198, 2018.
[30] Rong Ge, Jason D Lee, and Tengyu Ma. Matrix completion has spurious local minimum. arXiv preprint 1605:v660.00700 000.077772 2016.
[31] Rong Ge, Chi Jin, and Yi Zheng. No spurious local minima in nonconvex low rank problems: unified geometric analysis. International Conference on Machine Learning, pages 1233- 1242. PMLR, 2017.
[32] Ji Chen and Xiaodong Li. Memory--fficient kernel pca via partial matrix sampling and non- convex optimization: a model-free free analysis of local minima. arXiv preprint arXiv:1711.0174 2017.
[33] Richard Y Zhang, Somaych Sojoudi, and Javad Lavaci. Sharp restricted isometry bounds for the inexistence of spurious local minima in nonconvex matrix recovery. Journal of Machine Learning Research, 20 14):1134, 2019.
[34] Richard Y Zhang. Sharp global guarantees for nonconvex low-rank matrix recovery in the overparameterized regime. arXiv preprint arXiv:2104.10790 2021.
12

---

[35] Cédric Josz and Lexiao Lai. Nonsmooth rank-one one matrix factorization landscape. Optimization Letters, pages 1-21, 2021.
[36] Raef Bassily, Mikhail Belkin, and Siyuan Ma. On exponential convergence of sgd in non- convex over-parametrrized learning. arXiv preprint 1rXiv:/81 100564, 2018.
[37] Sharan Vaswani, Francis Bach, and Mark Schmidt. Fast and faster convergence of sgd for over- parameterized models and an accelerated perceptron. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1195-1204. PMLR, 2019.
[38] Robert Mansel Gower, Nicolas Loizou, Xun Qian, Alibek Sailanbayev, Egor Shulgin, and Peter Richtárik. Sgd: General analysis and improved rates. In International Conference on Machine Learning, pages 5200-5209. PMLR, 2019.
[39] Yuege Xie, Xiaoxia Wu, and Rachel Ward. Linear convergence of adaptive stochastic gradient descent. In International Conference on Artificial Intelligence and Statistics, pages 1475-1485. PMLR, 2020.
[40] 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 Signal Processing, 69:2396-2409, 2021.
[41] Christian Kümmerle and Claudio M Verdun. A scalable second order method for ill- conditioned matrix completion from few samples. International Conference Machine Learning, pages 9872-5883. PMLR, 2021.
[42] Emmanuel J Candès and Benjamin Recht. Exact matrix completion via convex optimization. Foundations of Computational mathematics, 96):717-77 2009.
[43] Benjamin Recht. A simpler approach to matrix completion. Journal of Machine Learning Research, 12(12), 2011.
[44] Qinqing Zheng and John Lafferty. A convergent gradient descent algorithm for rank minimiza- tion and semidefinite programming from random linear measurements. Advances in Neural Information Processing Systems, 28, 2015.
[45] Yuejic Chi, Yue M Lu, and Yuxin Chen. Nonconvex optimization meets low-rank matrix fac- torization: An overview. IEEE Transactions on Signal Processing, 67(20))5239-5266 5269, 2019.
[46] Cong Ma, Kaizheng Wang. Yuejie Chi, and Yuxin Chen. Implicit regularization in noncon- vex statistical estimation: Gradient descent converges linearly for phase retrieval and matrix completion. In International Conference on Machine Learning, pages 3345-3354. PMLR, 2018.
[47] Jason D Lee, loannis Panageas, Georgios Piliouras, Max Simehowitz, Michael Jordan, and Benjamin Recht. First-order methods almost always avoid strict saddle points. Mathematical programming, 176(1):311--)) 11-337, 2019.
[48] 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.
[49] Chi Jin, Praneeth Netrapalli, Rong Ge. Sham M Kakade, and Michael I Jordan. On nonconvex optimization for machine learning: Gradients, stochasticity. and saddle points. Journal of the ACM (JACM), 68(2):1-29 2021.
[50] Maxwell Harper and Joseph A. Konstan. The movielens datasets: History and context. ACM Trans. Interact. Intell. Syst., 5(4), dec 2015. ISSN 2160-6455. doi: 10.1145/2827872. URL https: http://doo.oog/o.o 1145/2827872
[51] Ivan Dokmanic, Reza Parhizkar, Juri Ranieri, and Martin Vetterli. Euclidean distance matrices: essential theory, algorithms, and applications. IEEE Signal Processing Magazine, 32(6):12-30, 2015.
13

---

[52] James Davidson, Benjamin Liebald, Junning Liu, Palash Nandy, Taylor Van Vleet, Ullas Gargi, Sujoy Gupta, Yu He, Mike Lambert, Blake Livingston, al. The youtube video recommen- dation system. In Proceedings of the fourth ACM conference on Recommender systems, pages 293-296, 2010.
[53] Greg Linden, Brent Smith, and Jeremy York. Amazon, com recommendations: Item-to-item collaborative filtering. IEEE Internet computing, 7(1):76-800 2003.
[54] Brent Smith and Greg Linden. Two decades of recommender systems at amazon. com. leee internet computing, 21(3):12-18, 2017.
[55] Mark A Davenport, Yaniv Plan, Ewout Van Den Berg, and Mary Wootters. 1-bit matrix com- pletion. Information and Inference: A Journal of the IMA, 3(3):199-223, 2014.
14


Reviews:
[{"review_id": "eQtWX8LsdYr", "reviewer": "Reviewer_3eem", "summary": "The matrix completion is a classic type of method that tries to recover the ground truth from the observation elements. The stochastic gradient descent (SGD) is one of the solutions to the huge-scale matrix completion in the real world. However, it is suffering from the ill-conditioned ground truth. This work is proposing an SGD-based method that is not affected by the ill-conditioned ground truth. Meanwhile, achieves the per iteration complexity improvement.", "questions": "\nFor soundness, it could be better to emphasize whether or not the algorithm is trying to invert the ill-conditioned matrix and the XX^T for complexity discussion.", "limitations": "No potential negative societal impact. ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths：\nThe SGD version in this problem is missing, and this work is trying to fill the missing piece.\n\nThis work is a nice extension of previous work, including the full-gradient method ScaledGD and PrecGD, the matrix completion SGD results (symmetric PSD case) from Jin [40]. The main contribution of this work could be eliminating the k-dependency in the complexity.\n\nThe experiment in the paper is synthetic data, but they offer real data in supplementary. \n\nIt’s a solid improvement on per iteration complexity.\n\nWeaknesses：\nIt’s not actually a weakness. The main contribution is about eliminating the condition number k in complexity. It reads like the previous work did not consider that at all. However, the previous work ScaledGD did discuss the case that k is independent. It’s fine but probably fairer to mention that to make it clearer.\n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "TSw5Vwe7fA4", "reviewer": "Reviewer_XHQZ", "summary": "The paper looks at online matrix-completion -- the goal is to obtain a matrix $X \\in \\mathbb{R}^{d \\times r}$ that minimizes $\\|XX^\\top - M\\| _F^2$ when the elements of the $d \\times d$ matrix $M$ are revealed in an online fashion. The paper looks at improving the convergence guarantees of SGD for this task, in terms of the dependence in the condition number $\\kappa$ of the ground-truth $M$. \n\nA previous result of [1] showed a convergence guarantee of $O(\\kappa^4 dr\\log(d/\\epsilon))$ for the regular SGD update. This result shows that multiplying the stochastic gradient with a pre-conditioner -- $P = (XX^\\top)^{-1}$ -- gives the aforementioned convergence guarantee without any dependence on $\\kappa$. \n\nThe paper shows that this preconditioner can be maintained by making 4 calls to the Sherman-Morris formula and incurs an additional cost of $O(r^2)$ as compared to $O(r)$ in regular SGD. \n\nThe main contribution in the analysis is a descent lemma -- arguing that the coherence of the iterates remains $O(1)$ throughout. \n\n[1] Chi Jin, Sham M Kakade, and Praneeth Netrapalli. Provable efficient online matrix completion via non-convex stochastic gradient descent. Advances in Neural Information Processing Systems, 29, 2016.\n", "questions": "Since you require $\\|X_0X_0^\\top - ZZ^\\top\\|_F^2 < 1/(\\kappa \\cdot d)$, which is a $1/d$ factor smaller than required for [1], couldn't you make the critique that, for a fair comparison to [1], your result in fact needs an $O(d)$ **factor** more iterations? If that's the case then the complexity of ScaledSGD is $~O(d^2)$, which as pointed out is vacuous. Am I missing something here? ", "limitations": "Yes.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "SGD for Online matrix-completion seems to be well-motivated [1] and applying a pre-conditioner in the descent step is a natural idea that also seems to be well-studied for full GD [2,3]. Hence, this idea is natural but the main contribution seems to be in the analysis -- specifically in Lemma 4 -- that argues that the coherence of the iterates decreases at a linear rate, independent of $\\kappa$. This analysis seems to be an important contribution to understanding the preconditioned stochastic optimization for RMSE matrix-completion.\n\nWEAKNESS \n\nAs you have mentioned. It seems like, the quality of approximation required for the initial iterate $X_0$ contains a factor of $1/d$ that [1] doesn't. Please see questions section.\n\n\n[2] Jialun Zhang, Salar Fattahi, and Richard Y Zhang. Preconditioned gradient descent for over329\nparameterized nonconvex matrix factorization. Advances in Neural Information Processing\n330 Systems, 34:5985–5996, 2021.\n\n[3] Tian Tong, Cong Ma, and Yuejie Chi. Accelerating ill-conditioned low-rank matrix estimation\n341 via scaled gradient descent. Journal of Machine Learning Research, 22(150):1–63, 2021.\n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "T8PT5pJlOC3", "reviewer": "Reviewer_To6Q", "summary": "This paper propose new online algorithm for matrix completion. When the underlying low-rank matrix is ill-conditioned (has a large condition numer), the authors delivered improved theoretical guarantees for the local convergence of the algorithm.", "questions": "The claim on line 156-158 is not correct. Full-batch gradient descent also does not require regularizer or projection to maintain incoherence, which was shown in [5].\n\n[5] Ma, C., Wang, K., Chi, Y., & Chen, Y. (2020). Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution. Foundations of Computational Mathematics, 20(3), 451-632.", "limitations": "This is a theory paper and I believe there is no potential negative societal impact.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: This paper makes solid contribution to online matrix completion when the ground truth is ill-conditioned. The authors present a new algorithm that provably handles ill-conditioned low-rank matrix with theoretical guarantees. Extensive numerical experiments are conducted to illustrate the theory. \n\nWeakness: my concerns for this paper is mainly about its novelty, as discussed in the first point below.\n1. Given that prior literature [1] already showed the fast convergence of SGD for online matrix completion with well-conditioned ground truth, and a series of recent work [2,3,4] showing that scaling provably improves the performance of gradient descent in the presence of ill-conditioned ground truth, it is not surprising to see that by incorporating the scaling scheme with SGD will improve the performance for online matrix completion with ill-conditioned ground truth. What is the technical novelty of this paper? I recommend the authors to highlight their technical contributions of this paper.\n2. The theory in this paper only guarantees local convergence. If I am not missing anything, this paper does not discuss how to obtain an initialization that satisfies the conditions in Theorem 2. The most popular initialization scheme is spectral method. Under what conditions does spectral method or other method satisfy the conditions in Theorem 2? How does these conditions depend on the condition number? If we don't have a good initialization scheme when the ground truth is ill-conditioned, then the local convergence result in this paper alone will not be so useful.\n3. The claim that \n4. The writing quality of this paper need to be improved, and the paper need to be proof-read. For example, only on page 4 I see the following problems:\n(a) the equation (SGD) contains multiple typos; \n(b) the sentence \"many iterations of SGD should concentrate about the behavior of full-batch gradient descent\" is ungrammatical;\n(c) on line 140, \"a cubic factor of $\\kappa^3$\" is actually $\\kappa^9$;\n(d) on line 144 \"initial\" -> \"initialization\" or \"initial point\";\n(e)  on line 145 \"with at least XXX probability\" -> \"with probability at least XXX\"\n\n[1] Jin, C., Kakade, S. M., & Netrapalli, P. (2016). Provable efficient online matrix completion via non-convex stochastic gradient descent. Advances in Neural Information Processing Systems, 29.\n\n[2] Tong, T., Ma, C., & Chi, Y. (2021). Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descent. J. Mach. Learn. Res., 22, 150-1.\n\n[3] Tong, T., Ma, C., & Chi, Y. (2021). Low-rank matrix recovery with scaled subgradient methods: Fast and robust convergence without the condition number. IEEE Transactions on Signal Processing, 69, 2396-2409.\n\n[4] Tong, T., Ma, C., Prater-Bennette, A., Tripp, E., & Chi, Y. (2022, May). Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Completion. In International Conference on Artificial Intelligence and Statistics (pp. 2607-2617). PMLR.\n\n---------------After rebuttal----------------------\n\nI would like to thank the authors for addressing my comments. I have updated the score accordingly.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept