Preconditioning Matters: Fast Global Convergence of Non-convex Matrix Factorization via Scaled Gradient Descent
Authors: Xixi Jia
Hailin Wang
Jiangjun Peng
Xiangchu Feng
Deyu Meng
Venue: NeurIPS 2023 poster (2023)
Keywords: Non-convex optimization
matrix factorization
low rank
scaled gradient descent
TL;DR: This paper proves the global linear convergence of scaled gradient descent method for non-convex low-rank matrix factorization

Abstract: Low-rank matrix factorization (LRMF) is a canonical problem in non-convex optimization, the objective function to be minimized is non-convex and even non-smooth, which makes the global convergence guarantee of gradient-based algorithm quite challenging. Recent work made a breakthrough on proving that standard gradient descent converges to the $\varepsilon$-global minima after $O( \frac{d \kappa^2}{\tau^2} {\rm ln} \frac{d \sigma_d}{\tau} + \frac{d \kappa^2}{\tau^2} {\rm ln} \frac{\sigma_d}{\varepsilon})$ iterations from small initialization with a very small learning rate (both are related to the small constant $\tau$). While the dependence of the convergence on the \textit{condition number} $\kappa$ and \textit{small learning rate} makes it not practical especially for ill-conditioned LRMF problem.

In this paper, we show that precondition helps in accelerating the convergence and prove that the scaled gradient descent (ScaledGD) and its variant, alternating scaled gradient descent (AltScaledGD) converge to an $\varepsilon$-global minima after $O( {\rm ln} \frac{d}{\delta} + {\rm ln} \frac{d}{\varepsilon})$ iterations from general random initialization. Meanwhile, for small initialization as in gradient descent, both ScaledGD and AltScaledGD converge to $\varepsilon$-global minima after only $O({\rm ln} \frac{d}{\varepsilon})$ iterations. Furthermore, we prove that as a proximity to the alternating minimization, AltScaledGD converges faster than ScaledGD, its global convergence does not rely on small learning rate and small initialization, which certificates the advantages of AltScaledGD in LRMF.

Preconditioning Matters: Fast Global Convergence of Non-convex Matrix Factorization via Scaled Gradient
Descent
Xixi Jia" Hailin Wang" Jiangjun Peng" Xiangchu Feng"* Deyu Meng
Schooo of Mathematics and Statisties, Xidian University
Schooo of Mathematics and Statisties, Xi'an an Jiaotong University
3 Macao Institute of Systems Engineering, Macau University of Science and Technology (hsij axidian, andrew jengjj]@gmal com; wanghai 1in970163. xcf oefengemail. xidiian.... edu. cn; dymeng@xjtu, edu. cn
Abstract
Low-rank matrix factorization (LRMF) is a canonical problem in non-convex optimization, the objective function be minimized is non-convex and even non-smooth, which makes the global convergence guarantee of gradient-based algorithm quite challenging. Recent work made breakthrough on proving that
standard gradient descent converges to the e-global minima after O dw² In das +
In In E4) iterations from small initialization with a very small learning rate (both
are related to the small constant 7). While the dependence of the convergence on the condition number к and small learning rate makes it not practical especially for ill-conditioned LRMF problem.
In this paper, we show that precondition helps in accelerating the convergence and prove that the scaled gradient descent (ScaledGD) and its variant, alternating scaled gradient descent (AltScaledGD) converge to an E-global minima after (n + ln iterations from general random initialization. Meanwhile, for small initialization in gradient descent, both ScaledGD and AltScaledGD converge to e-global minima after only (In iterations. Furthermore, we prove that as proximity to the alternating minimization, AltScaledGD converges faster than ScaledGD, its global convergence does not rely on small learning rate and small initialization, which certificates the advantages of AltScaledGD in LRMF.
1 Introduction
Low-rank matrix factorization aims to approximate given rank d matrix M E Rmxn by the product of two factor matrices U E Roxd
Raxd which plays fundamental and essential role in Ge low-rank matrix recovery such as matrix completion Jain et al. [2013), Ge et al. [2016], , Sun and
Luo (2016), matrix sensing Chi et al. [2019]. Zhao al. [ [015)] Charisopoulos et al. [2021] T). robust principal component analysis Candes et al. [2011]. Cai al. [202]]. and the theoretical analysis of deep neural network Du al. [2018]. Meanwhile, low-rank matrix factorization is also viewed as a canonical problem in non-convex optimization as the objective function to be minimized is non-convex and even non-smooth. Mathematically, we are to solve
min UeRmxd VERMx f(U, V) f(U,V) L M
"Corresponding author.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

(m, n.. Though problem ① is not difficult to solve, the study of this problem has great significance to the gradient- baaeed algorithm for low-rank matrix recovery Hou al. (2020) [L] et al. [201b)] Chen et al. [2019] Tong et al. [021]. as it is exactly the population loss of low-rank matrix recovery models. Meanwhile, from the perspective of non-convex optimization, problem
where d & min
(I) is an ideal test bed for the theoretical analysis of the asymptotic convergence of gradient-base
algorithm for non-convex optimization.
The theoretical guarantee for the global convergence of gradient-based algorithm for problem T is challenging, which due to the following reasons: 1) the problem is non-convex with respect the variables U and V, and there are infinitely many local minima and saddle points. Specifically, if U and V is an optimal solution of problem (T). then U*Q Q and V-Q-T is also an optimal solution for any invertible matrix Q: 2) the problem is non-smooth with respect to the variables U and V and is not coercive due to foU a V = S(UVT) where the scalar a can he arbitrarily large or small. In theory, gradient-based algorithm is only able to find critical points, while practically, gradient descent algorithm has been verified to converge to the global minima of problem (I efficiently.
To close the gap between theory and practice, et al. 2019a Ge et al. [017], Chi et al. 2019
proved that even-though the loss in Eq. (T) is non-convex loss landscape has some nice property: all local minima are global optima and all the saddle points are strict saddles. Therefore gradient descent algorithms can be guarantee to converge to the global minima. To help escape the striet saddles, et al. [2017] proposed perturbed gradient descent by adding isotropic noise to the gradient at each iteration, they prove that with high probability, perturbed gradient descent converges to the global minima from random initialization at linear rate. While as analyzed in Ye and Du 2021 and verified by experiments that the gradient perturbation is not really necessary for problem
In contrast to the perturbed gradient descent, Du et al. 20188) studied the naive gradient descent for problem (I) they exploited the balancedness of the two factors || 3| | 1/ maintained by gradient flow and proved polynomial
10
Saddle
region
Saddle region
10a²
convergence rate of gradient descent for problem (T) when
Relative error
= 1. Furthermore, Ye and Du [2021) improved the results Du et al. [2018] to rank d case, they proved that
Saddle region
20
gradient descent converges to the e-global minima of prob-
10
GD x
de² lem after O dx= 7 In das + 7 In e iterations, Ye and
CD
50
Sed 10
Du [021] I] divided the convergence process into two stages:
10.a
GDD 50
warm-up phase which takes O ( In dax) iterations and
local convergence phase which takes O dic² In Tu itera-
10a
10a
10a
tions. The warm-up phase in Ye and Du [2021] is actually the saddle avoid phase after which the gradient descent escapes all the saddle regions as shown in Fig.
Iteration count
Figure I: Illustration of the global con- vergence of GD and AltScaledGD from random initialization.
It can be seen from Fig. [ and proved by Ye and Du [2021] that both the saddle avoid phase and local convergence
phase of gradient descent highly rely on the condition number k of the matrix M. If the condition number x is large, then gradient descent takes long time to escape the saddle regions and also converges slowly. It is therefore very important know can we improve the gradient-bused algorithm such that the global convergence is independent of the condition number? Besides, the global convergence of both Du et [2018) and Ye and Du [2021] require very small learning rate (related to the small constant T), which seriously limits the application of gradient descent algorithm for ill-conditioned LRMF problem.
Recently, the scaled gradient descent algorithm (ScaledGD) Apuroop 2012 [016)] | Tanner and Weil (2016). has been proved by Tong et al. 2021| Tong 2022 to converge very fast from specialized imitialization (spectral initialization) to the global minima of problem [ and the convergence rate is independent of the condition number (Theorem in Tong et al. 2021 l). Yet the convergence result provided by Tong et al. (2011) is only local, whether the scaled gradient algorithm can escape saddle regions efficiently for the non-convex problem ① is still not clear.
Mishra and Sepulchre
In this paper, we are the first to prove that ScaledGD as well as AltScaledGD converge to the global minima of problem ( from general random Gaussian initialization, and the convergence rate is independent of the condition number of the matrix M. Moreover, we show that the global convergence

---

results of ScaledGD and AltScaledGD do not rely on small initialization, the global convergence of AltScaledGD does not even require small learning rate, which significantly improves the result of Ye and Du [021]. To sum up, the contributions of this paper are three-fold:
1. We provide very simple proof framework for the convergence of ScaledGD and AltScaledGD from general random initialization. Specifically, we divide the optimiza- tion process into three phases: initial phase, saddle avoid phase and linear convergence phase. We prove that the loss decreases at rate (1 7))ak the initial phase, and fur- ther decreases linearly (1- X*)* k in the saddle avoid phase and the linear convergence phase, where and Xs are independent of the condition number and is monotonically increasing from (2
"1" (2-n)² to n);
2. We prove that the scale of the random initialization is smaller than a given constant (small initialization), then the loss decrease linearly (1 n7) from such small initialization to the global minima for both ScaledGD and AltScaledGD.
3. We show that AltScaledGD a significant improvement of the ScaledGD in that it converges fast with large learning rate up to 1. While in contrast the learning rate of ScaledGID should be smaller than a constant Cy that is much smaller than
The organization of this paper is as follow. In Section 2 we introduce the related works on ScaledGD and AltScaledGD. In Section 3 we present our main results, then we give more detailed theoretical analysis on the proof sketch Section Finally, we conclude this work in Section 5
Related work
In this section, we introduce the ScaledGD and the AltScaledGD as specified in Apuroop (2012). Mishra and Sepulchre (2016], [Tanner and Weil (2016) Tong et al. [2021). We show that our work is significant improvement to these existing works on the global convergence analysis.
2.1 Scaled gradient descent
Different to the gradient descent algorithm which takes the negative gradient direction as the descent direction, scaled gradient descent is designed to accelerate the convergence process by scaled the gradient with a preconditioning matrix. Specifically, the ScaledGD updates the variables Us. Vi as
Uk+1 Ux f(U, V2) (V.Tv))
(2)
Va+1 = Vv fV, Vo) Uk)
where 77 is the learning rate, U. Un and V V3 are matrices of d x d. and < min(m, n) therefore the computation of ScaledGD is comparable to that of gradient descent. The inverse matrices (V, T Vx.) and (UJUU, is the preconditioning for the gradient descent. If denote X
(U, V), then Eq. (2) corresponds to
X = X - -X,,
(3)
(VTV))
where H₂
U U
Apuroop 2012). Mishra and Sepulchre (016) proved that ScaledGD is derived by imposing new metric on the tangent space of the Riemannian manifold. They verified empirically that ScaledGD converges much faster than gradient descent while there is no rigious convergence rate analysis. Recently, Tong et al.] [02T] the first to prove the linear convergence property of Eq. 2 for problem while their proof relies specialized initialization that dist X.) < 0.1oa
where X (U", V*) and U* M (Theorem 5 T/ong et al. (021 The local convergence guarantee is far from satisfactory to understand the convergence of ScaledGD for the non-convex
optimization problem (I)
3

---

2.2 Alternating scaled gradient descent
The Gaussian-Seider version of ScaledGD is the following alternating scaled gradient descent which writes
Uk+1 = U² - I(k,, VV & V
V++1 V - v/V (UUK+,, (4) 1 UK+1))
Eq. 4 was studied as scaled alternating steepest descent algorithm in Tanner and Wei| 2016) and is also closely related to the alternating minimization algorithm for the minimization problem (T) when
n = 1, and other matrix recovery problem as Wen et al. 2012 Jain et al. (2013), Chandrasekher et al.
[022]_ Different to alternating minimization, the AltScaledGD presented in Eq. (4) can be broadly used in lots of low-rank matrix recovery problem where alternating minimization is computationally
prohibitive, such matrix completion Zilber and Nadler [2022] Sun and Luo [016]. matrix sensing
Ma et al. [2021]. Existing works for Eq. (4) only proved convergence to critical point as Wen et al. 2012 lanner and Wei 2016]. yet global convergence analysis of AltScaledGD is still vague.
In this paper, we provide rigorous proofs for the global convergence of ScaledGD Eq. (2) and AltScaledGD Eq. (4), and we show that both ScaledGD and AltScaledGD converge linearly for random Gaussian initialization after saddle avoid phase. Meanwhile, we show that AltScaledGD robust to the learning rate which can be set as large as 1, while large can seriously deteriorates the convergence property of ScaledGD as illustrated by Fig. [6] which sheds light on the superiority of AltScaledGD Eq. (4) over ScaledGID Eq. 2 on problem (T) as well as more low-rank matrix recovery problem.
Main results
In this section, we present main theorems the convergence of ScaledGD and AltScaledGD for two different random initialization: general random initialization and small initialization. These two initializations both random Gaussian initialization with zero mean but different variances. Small initialization is widely used in the convergence analysis of low rank matrix factorization problem Stöger and Soltanolkotabi 22021), J, Ye and Du [202]) J, Ma and Fattahi (2022]. while small initialization is skin to spectral initialization which does not help us fully understand the global convergence of the non-convex problem. In this paper, we provide both the global convergence analysis of general random initialization and small initialization.
3.1 Global convergence of ScaledGD
If the matrix M is rank one, i.e., d in Eq. 11 is 1, then Eq. is exactly gradient descent with adaptive sizp-size. We show that such specialized gradient descent for d 2 converges linearly to the global minima after initial decreasing phase and the convergence rate is independent of the singular value of M.
Theorem (General random initialization). Let Uo Bndd and Vo Raxd be random Gaussian that follow (O, a) for > Cmit (Cnit is positive constant), and UR Vy are updated by Eq. (2). 1f S On < 1 for small constant Cpp we have that the objective function of problem f decreases linearly after Ti O (In 4) iterations, namely
[|U+tT ViTT,, M S a1 X
[M [F, 4k 20
(5)
where XK+T, is monotonically increasing from (2-1)² to n, 8 is sufficiently small constant, O' is constant.
q²
The Theorem Tindicates that the global convergence of ScaledGD can be divided into three phases: the initial phase that lasts Tj iterations, the saddle avoid phase in which Xk+T, increases from n/2 I-n/2 to and the final linear convergence phase with convergence rate - 17. While the scale of the initialization Uo and Vi are very small (with small σ), then the following theorem shows that the ScaledGID converges linearly without entering the saddle regions.
Theorem (Small initialization). Let Up E Rm and Vy E Ra ddd be random Gaussian that follow (0, o), with a I Cuit and Up. Vv updated by Eq. (2. If S Cn < for small constant Cpp have that the objective function of problem (7) decreases linearly, namely
VU MM f S az (1-1)))) (--m) n)* [M]] ||
(6)

---

where Cuit is a small constant and 0g is a constant.
3.2 Global convergence of AltScaledGD
We now present the main convergence results of AltScaledGD.
Theorem 3 (General random initialization). Let Uo E m and Vo E Raxd be random Gaussian that follow (0, σ) for > Cmit- Uk. V& are updated by Eq. 4 we have that the objective function of problem 7 decreases linearly after Ti OIn 4)) iterations, namely
[ V V
M I 01 (1-xxx1)) x |M]]
where Xk+T, is monotonically increasing from
n/² (2-n}² to 77 < 1 and a1 is constant.
Theorem (Small initialization). Let Up Rmmdd and Vo Raxd (0. p). with a S Cuitt, Uk. Vy are updated by Eq. (4) then we have that the objective function of problem T decreases linearly, namely
x be random Gaussian that follow
|U&VE
M| S oz (1 (1-1)* n)* |M|
(8)
where 0 < n I the step size, og is constant and Cinit small constant.
The convergence results of ScaledGD and AltScaledGD almost the same with differences in that for ScaledGD the learning 1) should be smaller than a constant Cn which is much less than 1. The small constant Cy greatly restricts the convergence rate of ScaledGD. While for AltScaledGDD the learning rate y) can be as large as 1, which indicates the superiority of AltScaledGD over ScaledGI) in convergence 1j is crucial to the convergence rate. From the above theorems, deduced that both ScaledGD and AltScaledGD converge to s-global minima after OIn 4 + In ) iterations from general random initialization. While for small initialization, these two algorithms only need Oln () iterations to converge to an e-global minima. More detailed analysis and proofs are provided in Section the proof sketch part and the supplementary materials.
be easily
3.3 Why does preconditioning help?
In previous works, preconditioning has been used to improve the condition of the optimization problem [Sadd [2003), /Zhang et al. [202T]. In this paper, we analyze how does the preconditioning help improving the convergence by analyzing the effect of condition number on the learning rate as the convergence rate highly depends on the learning rate. For simplicity, we take one step of the AltScaledGD example to analyze the effect of the preconditioning. Since f(U, V) is quadratic on
U, then it can be verified
1(UR+1, VR) S(U,, VR) (Viu,
(9)
where A Uk+1 Us and || IIA, is local norm defined by
A (AV V2.
For gradient descent, we take A = -n (UK, VR), then Eq.
becomes
f(Ux+1, Vi) < f(U,, Vv) n VUU Vo ( VU Vill
$ f(U,, VR) - -2)0) Vv) + (V) V%)
(10)
$ - (2) f(U,,
f(U,,
Similarly, it holds
f(U++I, VR+1) S (2 17a - f(UR+1, Vo)
(11)
Therefore, we have
1(U++1 Vo+1) S (1- (1- - - -v) S(U,, VA
(12)
5

---

General random initialization
Small initalization
10
10
StaleGGD x-
ScaledGD
StaledDD x 100
ScaledGD 100
StaledDD x-
SealedGD x- 200
AltScaledGD 10
AltSouieGG
AltScalelGD
AltSnalsiCD -10
Relatve error
10
AltScaledGD 200
Nelatve error
10 0
AltSealedDD 200
10.3
10
10
10
10:10
50
100
150
200
250
50
100
150
200
Iteration count
Iteration count
Figure 2: Illustration of convergence of ScaledGD and AltScaledGD under different condition g and different initialization.
To guarantee the linear convergence of gradient descent, it is required that 2110 (V+) 2 (V
and (Ux+)( 2 n (Ux+1) which implies S min o3(V) x ( (VV)) ++(U)+1) kl k(U++1) 2
In
contrast, we take A = -n)VSr(Us, VV Vx)= then
"
f(UR+1, Vx) $ f(U,, Vv.) (1
2 ((URVV - MIMVV, (UV - -M))
S(Kk, Vi)) - (n
or, (VEV)) s(Uk. Vo)
(13)
2
1 (1- (17 n²
or (VEV)) S(Uk. Vi))
2
and similarly
f(Ux+I, Vi+1) S f(UK+1, Vxx) - (11
((V.U M MT (U++1 Vo - -M))
n2
$ f(U++1, Vv) - (n orr (Ubl)+a) f(U1+1, VR)
1²2
1 (17 oor (( f(UK+2, Vs)
(14)
Thus
112 Jo, (VEVi) 2
-00""100 "0, (uflhett) f(Uk, Vz). (15)
1/2
f(U++1, Va+1) < (1- (17
2. or (U well a. (VI V&) To guarantee the linear convergence, we only need 0 < <.
strictly larger than 0 (Ve is the orthogonal row subspace of U3 V M and V4 is the orthogonal subspace of VR), which indicates that the linear convergence rate is independent of the condition number of matrix M.
We show in Fig. 2 that the convergence of ScaledGID and AltScaledGD are independent of the condition number of the matrix M with general random initialization and small initialization. In
Fig. 2 we set the rank of the matrix M as 5, with condition number ranging from 10, 100, 200. It can be seen from the left subfigure Fig. 2 that for general random initialization, the error curves of ScaledGD with different x are the exactly the same, and the error curves of ScaledGD also coincide with that of the AltScaledGD. These results are also true for small initialization as shown in the right subfigure of Fig. [ These observations certificate that preconditioning in Eq. (2) and Eq. (4) indeed help accelerating the convergence such that the convergence rate is independent of the condition number of the matrix M.
Since U.VI M. k + co and the same analysis is applied on Eq. 10 with respect to V, we know that
S

---

4 Theoretical analysis proof sketch
In this section, provide the proof sketch of our results in Section For simplicity, present the theoretical analysis for rank one matrix factorization where U E R mx and V E IR"x, More detailed proofs for the main theorems provided in the supplementary material.
4.1
Convergence of ScaledGD
can be deduced that the objective function of problem | is upper bounded by four terms as
|u++1 ViT+
M s (1 U M +(1 m)n
M M||F|V II Valla
1
M peoosf
(16)
+ r11 1)) |M [M 2ell2 +n
||
IU V ||F
where Ug and Va correspond the orthogonal basis of the column space of Uj and VE, U.i and Vi are the orthogonal complements of the left and right singular vector matrices of M (i.e. U., V.), and coso% is cosine value of the angle between the vectors U3 and U., coso is cosine value of the angle between the vectors V2 and V.. The upper-bound depicts the differences between Uk+1 V and M in two aspects
The angle between the subspace of U V and M: [12,, U4 222 [VIVall
The difference of the length (norm) between UR V and M: || |0 V
|r-
The term 2 and 3 are related to the angle between the subspace of M and U V the term 4 is related to the difference between the norm of M and U Vx as given by the following lemma. Lemma 1. If
2 V Il then there is constant Cy 2 such that
[M] cos0 coso &
< Cu (1
U V lIF)
(17)
[ ||r
According to Eq. (T6), we know that the decrease of the objective function problem IT decided by the decrease of the distance between the subspace (2 and 3)) and the difference between the norm of M and Uº V (4). The following lemma further reveals that the distance between subspace of Up V and M decreases.
Lemma 2. (Convergence of the distance between subspaces) For the ScaledGD if
|| coss0 2 | V ||,, then the following holds
| M4.1uk+11 S 1-)))444llll [D Va+ille S (1 (1- 1) IVT Vallz
(18)
The Lemma 2 indicates that the term ② and 3 in Eq. (6) decrease linearly if the norm of ||U V !|r smaller than norm the projection of M onto the column and row spaces of Ug V,T the mean time, the condition |M FcosSp cos@ Z ||U V; || also guarantees the linear convergence of the differences between the norm of U₁ Vg and M.
Theorem 5. (Convergence of the matrix norm) For the ScaledGD (2). if Fcos > | V for all k 2 0, then we have
|| - |1++1 VIT |l S (1-1)) kC,
(19)
where Co is constant and is the step length S < 1.
Both Lemma 2 and Theorem are built on the condition that | Fcos00 Z U V F for all & > O, while this is not trivial condition for ScaledGD. The following lemma guarantees that the condition can be satisfied if the step length vj is smaller than a constant.
Fco00 > U0 VoJ | then the Lemma 3. Let 1 S Gn with Cn a small constant, [|
following is true
M F coso" > | V
LF, Vk 0.
(20)

---

The above results guarantee the local linear convergence of the term 2 3 and 4 on the condition that
10*
Zoom
10'
saddle region
region
M pcosO cos 2 10%V ||
(21)
10
10
Relative ener
which is critical for our analysis on random Gaussian initialization and small initialization.
202
10
40
50
Reraton Count
4.1.1 Small initialization
10
10a
In practice, the condition |
ScaledED -=]
ScaledGD +>3/1000
V || can be easily satisfied by very small (near zero) initialization. According the random matrix theory The- orem 2.7.5 in Tao [2012). for Gaussian initialization there exists v > such that with high probability cosoğ and cosoi is lower bounded by constant 1 1/v, therefore one can simply set the norm of Uo and V, to be sufficiently small such that the inequality (2T) holds. In consequence small initialization can guarantee the global linear conver-
10:00
0
50
100
150
200
250
300
Iteration count
Figure 3: Global convergence of small
initialization and general random initial- ization.
gence of ScaledGD, as shown in Fig. While small initialization is very special. it can not helps us fully understand the global convergence property of ScaledGD from arbitrary initialization for the non-convex objective (I. even though small initialization has been widely used in the global convergence analysis of gradient descent algorithms Stöger and Soltanolkotabi (202T), J. Ye and Du 2021], Ma and Fattahi| [2022] and ScaledGD for symmetric low rank matrix recovery problems Xu
ct al.] 2023). Zhang et al. 202T].
4.1.2 General random initialization
In order to understand the optimization path of ScaledGD for the non-convex objective T we present the theoretical analysis of ScaledGD from random Gaussian initialization that may not satisfy the condition in Eq. (2T). As shown in Fig. + when initialized with = 1 ScaledGD iterations are also attracted by the saddle point thus enter the saddle region (zoomed region marked by red rectangle), while it can escape saddle region very fast. To rigorously characterize the saddle avoid phase, we first show and prove that the norm of matrices Us and Vi decrease ||r as given by the following lemma and shown in Fig. 4
||M]] r max [cos0% cos0g} < || V
Lemma 4. If the condition [M] || max max[cos0f cos0g) < ||U V
|| is satisfied then we have
||+++1
1I < |U&|IF and || ll < Ville
(22)
Furthermore, if the condition
M Foos
| Vg || satisfied then we have
||+++ 1| 2 || and Ve+1 || 2 Ville
(23)
In general, if we initialize the matrices U and V as (0, σ) with large a, then in the initial phase. with high probability we have || max coso" cosoj} } < |U Vg ||.. According to Lemma and Lemma 4 we know that the norm of the matrices Un and V& decreases with the increase of until it reaches the condition || M [ 2 V ||r, which is also illustrated in Fig. 4 In Fig. 4 plot the changes of the norm of matrices U and V, the nested subfigure illustrates the the matrix norm in log scale. It is very interesting to study the changes of the matrix norm with respect to the optimization path. Generally, if | F and VV 1/ is initialized very large, then the decrease of the norm will decrease the objective function TT. Meanwhile, U = 0 and V = O is a saddle point of the objective function (I). the results in Lemma thus indicate that the matrices UR and V are updated toward the saddle point zero. While interestingly, as shown in Fig. 4 the matrix norm decreases to a magnitude which strictly larger than zero, then the matrix norm begins increase. These observation indicates that ScaledGI can escape from the saddle point zero, the saddle avoid phase also illustrated in Fig. 5
Analysis on the entire iteration process. It can be easily deduced from Eq. 16 that
U V
M (1 2k Vo M M
|| ||,
(24)
8

---

50
10.
norm of U
SaBi Lisha error
andd Intol
40
Norm of the matrices
Norm in log scale
M hood 1
Linner
convergance
Relative enor
10
30
10
U.Y.
20
10
400
500
lteration count
10
10"
10
100
150
200
Strictly larger than zero
10"
50
100
150
200
500
1000
1500
2000
Iteration
lteration count
Figure 4: Illustration of the norms of matrices U and V.
Figure 5: Illustration of the saddle avoid phase.
therefore after Ti= = O(In)) iterations (for sufficiently small 8 8 have
| M||F || F. Vk Ti;
(25)
which indicates that || cosff cosof UR V ||r. We term this period of time the initial phase. The following lemma tells that after 7. iterations the term 2 3 and 4 decrease linearly.
Lemma 5. After Ti iterations of ScaledGD, the following inequalities hold wk 2 Ti
4x+ S (1 - xx) 14, Usll2
(26)
IV. 14t1l2 S (1 xx) I Valla
(27)
1 coso k4 i R+1 I (1 x (1 - cosof
(28)
where Xk I-n(1-r4
4TH
and Tk =
|
[ULV V. 1| E [1/2,1].
2 V F < M | coss <
U V I and cos@ Thus the above Lemma indicates that
M |E 2 V V I[,, we have that the
term ④ in Eq. (16) is upper bounded by after Ti iterations, the objective function decreases at rate
Xx- Meanwhile, cos and cos are increasing, and ||U V, || continues to decrease until || |M coss 2 I V [[e, which
means the value тı |M pco=@"cco0""" is monotonically increasing with the increase of until up
[ V. ||F
n/2 to 1. In consequence, the Xx is monotonically increasing from T-n/2 to 1). We name the period in
which X increases from 1-n/2 17 the saddle avoid phase shown in Fig. The Lemma also indicates that the ScaledGID escapes saddle points exponentially fast. After the saddle avoid phase, the ScaledGD converges to the global minima at rate according to the analysis in Section 4.1.1 since || co 2 | Vi [|,, name this period the linear convergence phase as shown in Fig. 5
n/2
4.2 Convergence of AltScaledGD
The convergence analysis of the AltScaledGD is similar to that of ScaledGI, while different to ScaledGD, the objective function
[1 is upper- apper-bounded by three terms in AltScaledGD
[|0441 VIT - M][F < (1 - V M +(7 - n²") || Vv_ Villa +n M [4 U4.
(29)
PPlease refer to the supplementary results for detailed analysis.
*Since in this period of time, the norm of the matrices Us and V, decrease, while once X y (equivalently Tk = 1), according to Lemma and Lemma 3 the norm of the matrices Us and V2 begin to increase, which indicates that the matrices Us and VA escaping from the saddle point zero

---

therefore, the analysis of AltScaledGD for ① is much easier than that of the ScaledGD in Eq. (T6). Specifically, we only need guarantee that the distance between subspaces of U2 and U.
(I (2l))), V& and V. (IV-.1 V (22) decrease linearly. The Lemma Cemmaaalso holds for AltScaledGD as
Lemma 6. (Convergence of the distance between subspaces) For AllScaledGD [M f coss0 coosf UU V || and 0 < 1) S 1, then the following holds
4 if
[ S (1 - 7) [4 24l12 [M_ V4t1lle S (1-n)]lV Vell2.
(30)
The condition in Lemma 6 can be satisfied Vk if M| coos0fcos0 2 |10 Vo || and 0 < n < 1
as specified by the following lemma, the condition is mild compared to the condition in Lemma S
Lemma 7. For AltScaledGD following true
if
| |cos0 co
N Vo le and 0 < n S 1, then the
M cos00
|| Lx Ak 0.
(31)
The convergence analysis of AltScaledGD is the same as that of the ScaledGD in Section 1 with small initialization and general Gaussian initializa- tion (the three phases convergence). The main differ- ence between ScaledGD and AltScaledGD is that 1) in ScaledGD should be small such that vj S Gy 1, while for AltScaledGD can be as large
10a
Relative error
10
1. It
can be seen from Eq. (29) that if 7 = 1, the the AltScaledGD Eq. converges to the global min- ima in just one iteration. We also illustrate the con- vergence of ScaledGD Eq. 2 and AltScaledGD Eq. (4) with respect to the learning rate 77 in Fig. 6 It can be seen from Fig. that for small learning rate = 0.1, the convergence property (the loss curve) of AltScaledGD is almost exactly the same ScaledGD, while for large learning rate = 0.8, the AltScaledGD converges very fast, in contrast the ScaledGD does not converge as the condition 1) S on is not satisfied according to Lemma 3 These results certificates the superiority of AltScaledGD over ScaledGD, since both ScaledGD and AltScaledGD converges fast with large 7), while the learning rate 17 is upper-bone bounded by small constant Cyp in ScaledGD.
20
ScaledG 00.1
AltSccllddi y =0.1
ScaleoCh 00,8
10
A AlScallech -00.8
100
300 Iteration account
200
400
500
Figure 6: Illustration of the effect of learning rate for the convergence.
5 Conclusion
In this work, we are the first to rigorously prove the global convergence of ScaledGD and AltScaledGD for the non-convex low rank matrix factorization problem and show that thanks to the preconditioning matrices the global convergence rate of ScaledGD and AltScaledGD are independent of the condition number of the matrix M, thus they converge faster than gradient descent algorithm for ill-conditioned problem. We further prove that ScaledGD and AltScaledGD converges linearly from both small initialization and general random initialization, which is in contrast to the existing global convergence analysis that are only applicable to small initialization. Meanwhile, we show that compared to ScaledGD, AltScaledGD is more practical as it enables larger learning rate thus converges fast.
Limitations. This paper concerns low-rank matrix factorization which is the population loss of the more general low-rank matrix recovery problem, such as matrix completion and matrix sensing. While the empirical loss is different to the population loss in that the number of the samples is limited, therefore our results can not directly applied to general low-rank matrix recovery. Our further work is to study the empirical loss with the help of RIP condition for matrix sensing and the sampling lower-bound for matrix completion.
Acknowledgements
This research was supported by the National Key R&DD Program of China (2020TAA0119000) the 12226004, the Macao Science and Technology Development Fund under Grant 061/2020/A2, and the Fundamental Research Funds for the Central University under Grant ZYTS23056.
China NSFC projects under contracts 62372359, 61721002
10

---

References
K Adithya Apuroop. A riemannian geometry for low-rank matrix completion. arXiv preprint arXiv:/211.1550, 2012.
HanQin Cai, Jialin Liu, and Wotao Yin. Learned robust pea: A scalable deep unfolding approach for high-dimensional outlier detection. Advances in Neural Information Processing Systems, 34: 16977-16989, 2021.
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.
Kabir Aladin Chandrasekher, Mengqi Lou, and Ashwin Pananjady, Alternating minimization for generalized rank one matrix sensing: Sharp predictions from a random initialization. arXiv preprint arXiv:2207.09666, 2022.
Vasileios Charisopoulos, Yudong Chen, Damek Davis, Mateo Díaz, Lijun Ding, and Dmitriy Drusvy- atskiy. Low-rank matrix recovery with composite optimization: good conditioning and rapid convergence. Foundations of Computational Mathematics, 21(6):1505-1525 2021.
Yuxin Chen, Yuejic Chi, Jianqing Fan, and Cong Ma. Gradient descent with random initialization: Fast global convergence for nonconvex phase retrieval. Mathematical Programming, 176:5-37, 2019.
Yuejie Chi, Yue M Lu, and Yuxin Chen. Nonconvex optimization meets low-rank matrix factorization: An overview. IEEE Transactions on Signal Processing, 67(20))5239-522 5269, 2019.
Simon S Du, Wei Hu, and Jason D) Lee. Algorithmic regularization in learning deep homogeneous models: layers are automatically balanced. Advances Neural Information Processing Systems, 31:382-393, 2018.
Rong Ge, Jason D Lee, and Tengyu Ma. Matrix completion has no spurious local minimum. Advances in Neural Information Processing Systems, pages 2981-2989, 2016.
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.
Thomas Hou, Zhenzhen Li. and Ziyun Zhang. Fast global convergence for low-rank matrix recovery via riemannian gradient descent with random initialization. arXiv preprint 1554 2020.
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.
Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M Kakade, and Michael Jordan. How to escape saddle points efficiently. In International conference on machine learning, pages 1724-1732. PMLR, 2017.
Qiuwei Li. Zhihui Zhu, and Gongguo Tang. The non-convex geometry of low-rank matrix optimiza- tion. Information and Inference: Journal of the IMA, 8(1)551-96, 2019a.
Zhenzhen Li, Jian-Feng Cai, and Ke Wei. Toward the optimal construction of a loss function without spurious local minima for solving quadratic equations. IEEF Transactions Information Theory, 66(5):3242-326)) 2019b.
Cong Ma, Yuanxin Li, and Yuejic Chi. Beyond procrustes: Balancing-free gradient descent for asymmetric low-rank matrix sensing. IEEE Transactions on Signal Processing, 69:867-877, 2021.
Jianhao Ma and Salar Fattahi. Global convergence of sub-gradient method for robust matrix re- covery: Small initialization, noisy measurements, and over-parameterizaaion.. arXiv preprint arXiv:2202.08788, 2022.
11

---

Bamdev Mishra and Rodolphe Sepulchre. Riemannian preconditioning. SIAM Journal on Optimiza- tion, 26(1):635-66l) 660, 2016.
Yousef Saad. Iterative methods for sparse linear systems. SIAM, 2003.
Dominik Stöger and Mahdi Soltanolkotabi. Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstruction. Advances in Neural Information Processing Systems, 34:23831-23888 2021.
Ruoyu Sun and Zhi-Quan Luo. Guaranteed matrix completion via non-convex factorization. IEEE
Transactions on Information Theory, 62(11))6535-6677) 2016.
Jared Tanner and Ke Wei. Low rank matrix completion by alternating steepest descent methods. Applied and Computational Harmonic Analysis, 40(2):417-429, 2016.
Terence Tao. Topics in random matrix theory, volume 132. American Mathematical Soc., 2012.
Tian Tong. Scaled gradient methods for ill-conditioned low-rank matrix and tensor estimation, PhD thesis, Carnegie Mellon University, 2022.
Tian Tong, Cong Ma, and Yuejie Chi. Accelerating ill-conditioned low-rank matrix estimation via scaled gradient descent. The Journal of Machine Learning Research, 22(1):6639-6700 2021.
Zaiwen Wen, Wotao Yin, and Yin Zhang. Solving low-rank factorization model for matrix
completion by nonlinear successive over-relaxation algorithm. Mathematical Programming Computation, 4(4):333-3611 2012.
Xingyu Xu, Yandi Shen, Yuejie Chi, and Cong Ma. The power of preconditioning overparameter- ized low-rank matrix sensing. arXiv preprint arXiv:2302.01 186, 2023.
Tian Ye and Simon S Du. Global convergence of gradient descent for asymmetric low-rank matrix factorization. Advances in Neural Information Processing Systems, 34:1429-1439, 2021.
Jialun Zhang, Salar Fattahi, and Richard Zhang. Preconditioned gradient descent for over- parameterized nonconvex matrix factorization. Advances in Neural Information Processing Systems, 34:5985-5996, 2021.
Tuo Zhao, Zhaoran Wang, and Han Liu. A nonconvex optimization framework for low rank matrix estimation. Advances Neural Information Processing Systems, 2015:559-567 2015.
Pini Zilber and Boaz Nadler. Inductive matrix completion: bad local minima and a fast algorithm. In International Conference on Machine Learning, pages 27671-27669 PMLR, 2022.
12


Reviews:
[{"review_id": "70MChIGPZX", "reviewer": "Reviewer_QnG3", "summary": "This paper considers the classical problem of low rank approximation. In particular, given a matrix $M\\in \\Re^{m \\times n}$ with rank $d$, we want to find $U\\in \\Re^{m\\times d}, V\\in \\Re^{n\\times d}$ that minimizes $f(U,V) = |UV^T - M|_F$ (i.e $U,V$ are low rank matrices whose product approximate $M$). The problem is very well studied and classical. \n\nObviously, one can perform classical gradient descent on $U,V$ to optimize for $f$ (although this is not desirable because it relies on the condition number of $M$). It is shown that the local minima of $f$ do not misbehave, so gradient descent works fine. However, in the literature, there are two \"gradient scaled\" iterative variants of gradient descent that \"scale\" the gradient by right multiplying it by appropriate matrices. This is well studied in the literature, and the two variants considered in the paper in ScaledGD and AltScaledGD (where AltScaledGD is similar to ScaledGD but \"alternates\" the scaling matrix multiplied by the gradient). There has been a lot of work that studies the theoretical convergence of these two problems. The latest is the work from 2021 by Ye and Du that get linear convergence until very strong assumptions (technically, they're not \"assumptions\", but the convergence rate is not clean at all). \n\nIn this paper, the authors give an elegant proof that both ScaledGD and AltScaledGD converge linearly for the low rank approximation problem. This is the first \"clean\" analysis (in the sense that all the constants are clear) for the two algorithms. ", "questions": "Line 154: Theorem 1, I might be missing something, but where is the dependence on \\sigma in Theorem 1 statement?", "limitations": "Lines 346-351. Well addressed. ", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is cleanly written, and reads well. \n- The analysis is quite elegant and sheds a lot of answers on the intuition on why these algorithms work well and do not rely on the condition number of $M$. \n- Some of the lemmas proven along the way might me of independent interest (for example, while I am not related directly to this line of research, one of the Lemmas proven will probably very useful for my next paper). The proofs are well written (although there are some rough patches there). ", "weaknesses": "- Some areas are rushed in the main paper. Some areas need to be explicitly written instead of using \"it can be deduced\" which is frustrating to the reader and is used a couple of times by the authors (when it really shouldn't). I've noted some examples below, but please avoid doing this and write the steps explicitly. I understand this would take longer to write, but it makes the reading process much more pleasant. \n- The author(s) can spend a bit more time on explaining the intuition behind some of the inequalities they derive. The proofs sometimes seem very mechanical, and in other areas seem to shed a lot of intuition on what is happening. It would be nice if this is standardised so that the overall picture of the proof is explained first, before churning out the math. For example, some of the proofs from Section 3 are quite heavy and go through math without offering why said computations are being made. It's only in the end after rereading that you get what was happening. \n\n------------------------------------------------------------------\nLines 80: AltScaledGD is not introduced earlier. Please introduce it earlier. \n\nLine 108: Scaled -> scaling \n\nLine 117: \"converges much faster than gradient descent while ther\" ==> \"converges much faster than gradient descent. However, ....\"\n\nLine 120-122: \"The local convergence .. problem (1).\" This is an unnecessary sentence. Remove or rephrase. \n\nLine 154: Theorem 1, I might be missing something, but where is the dependence on \\sigma in Theorem 1 statement?\n\nLine 216: \"It can be deduced tha..\" Don't do that, please spell it out explicitly (i.e sub in eq(2) and expand..\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We deeply appreciate the reviewer for your careful review, constructive suggestions and positive feedbacks. The followings are our responses to your concerns. We will greatly appreciate that you can raise your score if you find our responses resolve your concerns.\n\n**Q1: Write some of the proof steps explicitly.**  \n**A1**: We will carefully check our proof and rewrite the proof with more details such that it is easy to read. Thank you for your kind suggestions.\n\n**Q2: Explain the overall picture of the proof and the intuition behind some of the inequalities.**  \n**A2**: To help us understanding the proof of the main results in section 3, we provided the proof sketch of the main results for rank-1 case in section 4 since it is easy to follow and understand (the proof sketch of AltScaledGD for rank-1 case is the similar to that of ScaledGD). The proof of the rank-d case follows the sketch of the rank-1.   \n\nSpecifically, the error $ || U_k V_k^{\\top} - M||_F $ is upper bounded by four terms in ScaledGD as in Eq. (12) and three term in AltScaledGD as in Eq. (25), all the remaining lemmas and inequalities are to guarantee that each of the upper-bound terms decrease linearly. To this end, the inequality $ <U_k V_k^{\\top}, M > \\geq || U_k  V_k^{\\top}||_F^2$ is crucial to our analysis since once it is satisfied, according to Lemma 4, Lemma 5 and Lemma 6 the upper bound terms in Eq. (12) and Eq. (25) decrease linearly, which reveals the linear convergence of ScaledGD and AltScaledGD.\n\nOnce again, we thank the reviewer for the valuable and constructive suggestion. We will revise our manuscript of section 4 and the Appendix in the revision such that the overall picture of the proof can be clear and easy to follow.\n\n**Q3: Some typos need to be rectified and the writings need to be improved.**  \n**A3**: We will carefully proofread the entire manuscript to ensure that all the writing mistakes will be rectified. \n\n**Q4: Where is the dependence of $\\sigma$ in Theorem 1 statement?**  \n**A4**: Thank you for your careful reading and pointing this out. $\\sigma$ determines the scale of the initialization and correspondingly the initial error $||U_0 V_0^{\\top} -  M||_F$, which further determines the time the initial phase lasts. Specifically, the variable $\\sigma$ is contained in $T_1$ as $T_1 = O(\\ln \\frac{\\sigma d}{\\delta})$, since $\\sigma$ is only a constant ($O(1)$) compared to the problem dimension and other parameters, we thus omitted it in our previous submission. We will revise the corresponding part in the revision. "}, {"review_id": "oq7hI7i65c", "reviewer": "Reviewer_eEnz", "summary": "This paper studies  low rank matrix factorization, which is an important topic with many applications in machine learning. The main challenge of this problem comes from the non-convexity of the objective function, especially, this objective function can be non-smooth. As a consequence, the global convergence remains a difficult question in this area. The most recent approximate global minima convergence guarantee depends on quite a few parameters, and this, especially small initialization and small learning rate, might reduce the practical application potential of the convergence results. To address this issue, this paper shows that precondition helps in accelerating the convergence and the scaled gradient descent converges to approximate minima after a better number of iterations. ", "questions": "1. It is not quite obvious to me that why the initialization can be completely random. Since the objective function is non-convex, the initial points can still converge to different local minimum, and this might cause a difference in the resulting output.\n\n2. Why the saddle avoidance phase hold for random initialization? I might miss some point, but one of the contribution of this paper is about the initialization can be random, and then, at least intuitively, this will cause some technical challenges in analyzing the saddle avoidance phase. Could you please provide some intuition on the proof of 157-176 in Appendix, so that it is more clear that the saddle avoidance can be done for random initialization?\n\n3. Another question on the theoretical side is: what is the main technical challenge in proving the convergence of alternating scaled GD, compared to the main algorithm?\n\n4. Line 71, why near zero initialization is an issue? How does it effect specific ill-conditioned LRMF problems?\n\n5. Line 78, results of Tong et al are local or global? The presentation causes confusion.\n", "limitations": "As stated before, the main limitation of this paper is the experiment, it is not convincing that current theoretical results is powerful enough to have strong impact in applications. ", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The problem in this paper is well motivated and studied. The main strength of this paper is the convergence result does not sensitively depend on condition number and small learning rate, which improve the application potential of the current algorithm and convergence analysis. \n\nAnother strength is that this paper provide some variants of the main algorithms and simultaneously provide comparable convergence rates, which might of independent interests.\n", "weaknesses": "1. The main weakness of this work is lacking of real data based experiments. Despite the theoretical analysis is complete and technical, matrix factorization is a powerful method in real application. \n\n2. The convergence rate is theoretically improved, however, the practical impact of matrix factorization algorithm is inevitably tied with real data set experiments. It is not clear how the algorithm works in real data set, so it might cause some difficulty to judge the contribution of this theoretically sound paper.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We greatly thank the reviewer for the valuable comments and the constructive suggestions. Here we response your concerns one by one. We will deeply appreciate that you can raise your score if you find our responses resolve your concerns.\n\n**Q1: How does the algorithms work on real data set.**  \n**A1**: The ScaledGD and AltScaledGD are not only work on simulated data but also on real data set such as multi-spectral image (MSI) data and video data sets. We provide a PDF file in the author rebuttal part, and report the experimental results of GD, ScaledGD and AltScaledGD on MSI and video data sets in Figure 3 and Figure 4. In these figures, we can see that ScaledGD and AltScaledGD converges much faster than GD on both MSI data sets and video data sets. Specifically, the relative error of ScaledGD/AltScaledGD is less than $10^{-2}$ for MSI data \"flower\" and is less than $10^{-5}$ for MSI data \"Simu_Indian\" within $500$ iterations, while the relative errors of GD are still very large after $2000$ iterations. The experimental results are consistent with the theoretical results provided in the main paper. We will also replenish these real data sets experiments on the Appendix of our revision.\n\nMeanwhile, our follow-up works indicate that ScaledGD/AltScaledGD work well for more applications, please refer to our response to Q1 of reviewer Cp2y and Figure 1,  Figure 2 on the PDF file which show that ScaledGD/AltScaledGD work well for neural network model.\n\nOverall, this conference paper focuses on proving the global convergence of ScaledGD and AltScaledGD for the non-convex LRMF model and analyze the descent trajectory of the algorithms. The results are significant improvements to the work of Tong et al. 2021 for the analysis of the ScaledGD. More applications of ScaledGD and AltScaledGD and their convergence analysis are our ongoing work. \n\n**Q2:  Why the initialization can be completely random.**  \n**A2**: For non-convex optimization, if the objective functions satisfy the strict saddle property (SSP) that is all saddle points have a decent direction, then gradient based algorithm can converge to local minima [1]. The low rank matrix factorization as well as low rank matrix recovery satisfy the SSP, meanwhile, the objective functions have benign landscape (all local minima are global minima) [2], therefore even with random initialization ScaledGD/AltScaledGD is able to converge to the global minima. While, existing works do not provide global convergence rate of ScaledGD/AltScaledGD on asymmetric LRMF, we are the first to give a detailed convergence rate analysis of ScaledGD and AltScaledGD with random initialization.\n\n[1] Lee, J. D., et al. Gradient descent only converges to minimizers. In COLT, 2016.   \n[2] Ge, R., et al. Matrix completion has no spurious local minimum. In NeurIPS, 2016.\n\n**Q3: Provide some intuition on the proof of 157-176 for the saddle avoid.**  \n**A3**: The saddle avoid phase (line 157-176 in Appendix) is analog to the rank-1 case analyzed in section 4.1.2 line 295-305 in the main paper, which guarantees that ScaledGD does not trap into the saddle point. Specifically, for general Gaussian initialization with the scale of the initial valuable $U_0$ and $V_0$ greater than some constant $c_{init}$, according to Lemma 4, we know that the norm of the matrix $U$ and $V$ decrease toward the saddle point $U = 0$ and $V = 0$ until the inequality $ <U_k V_k^{\\top}, M > \\geq || U_k  V_k^{\\top}||_F^2$ is satisfied. The inequality is crucial to our analysis since once it is satisfied, according to Lemma 4 the norm of the matrix $U_k V_k^{\\top}$ tends to increase as shown in Figure 4 of the main paper, and meanwhile Lemma 5 and Lemma 6 in the main paper show that the angle between the subspace of $U_k$ ($V_k$) and $ U^*$ ($ V^*$) decrease linearly, which reveals that the ScaledGD has escaped the saddle region (since in rank-1 case the saddle point is 0 matrix with norm 0).\n\nThe proof of 157-176 in Appendix is to show that after the initial phase we have $< U_kV_k^{\\top}, M> \\geq \\tau_k ||U_kV_k^{\\top}||_F^2$, and in the saddle avoid phase the variable $\\tau_k$ is increasing from 1/2 to 1 such that the inequality $<U_k V_k^{\\top}, M> \\geq ||U_kV_k^{\\top}||_F^2$ is fulfilled. After $\\tau_k$ grows up to 1, the algorithm enters the linear convergence phase as analyzed in line 177-185 in Appendix.\n\n**Q4: Technical challenge in proving the convergence of alternating scaled GD ?**  \n**A4**: The proof of the convergence of the AltScaledGD is similar to that of the ScaledGD, with only difference in that the term ④ in Eq. (12) limits the learning rate $\\eta$ to be smaller than a constant $c_{\\eta}$, while there is no corresponding term ④ in Eq. (25), therefore the learning rate $\\eta$ can be set as $0\\leq \\eta \\leq 1$ in AltScaledGD. In consequence, AltScaledGD enjoys lager learning rate and faster convergence rate than ScaledGD as specified in line 318-336 of the main paper. \n\n**Q5: Why near zero initialization is an issue?**  \n**A5**: Near zero initialization as well as spectral initialization limit the initialization to a local region near some certain points, which has strong initialization bias. While for the theoretical analysis of non-convex optimization, one is interested in the global convergence property of the optimization algorithm which starts from any random initialization (without initialization bias) rather than a local region of some certain point. We prove that the ScaledGD and AltScaledGD are not sensitive to the scale of the initialization, they converge fast in both general random initialization and near zero initialization.\n\n**Q6: Results of Tong et al. are local or global?**  \n**A6**: The results of Tong et al. are local, since it relies on the spectral initialization (initialization in a local region the global minima). In contrast, our results are global as our initialization is random without initialization bias. We will revise our statement in the main paper.\n\n \n"}, {"review_id": "DwsGlSEuMe", "reviewer": "Reviewer_beQc", "summary": "This paper considers the problem of low-rank matrix recovery using preconditioned gradient descent. Traditionally, although GD can be used to solve this problem, it becomes extremely slow when the problem is ill-conditioned. Recently a method called ScaledGD was proposed that makes GD immune to ill-conditioning. However, previously, the theoretical analysis of ScaledGD required spectral initialization, and this work extends that analysis to small or moderate random initialization. The authors also analyze an alternating version of ScaledGD, which they call AltScaledGD, and also prove global convergence for this algorithm. ", "questions": "N/A", "limitations": "N/A", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "Previously, algorithms like ScaledGD with make GD immune to ill-conditioning relies on an initial point close to the ground truth. Although this can be achieved through a method known as spectral initialization, it can be very expensive. This work strengthens previous results by showing that a *random* initialization can also achieve linear convergence. Similar results have been established for vanilla GD with small initialization. Here the authors extend such results to ScaledGD, and show that a moderate random initialization also works. To me this is the main novelty of this work. ", "weaknesses": "The main weakness that prevents me from giving this work a higher score is the organization of the technical sections. In the introduction the authors claim that they prove global convergence of ScaledGD with moderate initialization. However, in section 3.1 the main results are only stated for the **rank-1** case. Again, in section 4, the authors claim that they will present the theoretical analysis for the rank-1 case. In the appendix, however, they authors present Theorem 3, which is the moderate initialization case for the rank-d case. But the proof of Theorem 3 refers to some results in section 4, which was presented for the rank-1 case. As a result, it is hard to decipher which parts of the rank-1 case generalize directly to the rank-d case, and which parts need more work. \n\nOverall I think the organization of the technical sections is confusing and needs significant improvement.\n\n\n\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to express our sincere gratitude for your valuable comments on our work. As for your concerns, we give detailed response below which we hope can help you fully understand our work. Please feel free to let us know if you have any further concerns. We will deeply appreciate that you can raise your score if you find our responses resolve your concerns.\n\n**Q1: The organization of the technical sections should be improved, some of the results are only stated for rank-1 and the proof from rank-1 to rand-d is confusing.**  \n**A1**: The overall picture of the technical sections is that we first present the main results (rank-1 for ScaledGD and rank-d for AltScaledGD) in section 3.  Then to have a proof guideline, we give the proof sketch of the rank-1 case of both ScaledGD and AltScaledGD in section 4, as the rank-1 case is easy to understand and follow. At last, in Appendix we present more detailed proofs of both rank-1 and rank-d based on the proof sketch in section 4. Since the proof of rand-d follows the proof sketch of rank-1 with some moderate changes of the lemmas and inequalities from rank-1 to rank-d, we refer the proof sketch of rank-1 as the proof guideline of Theorem 3 in Appendix.  We are sorry to make you feel confused on our proof. \n\nNote that ScaledGD is closely related to GD but it has quite different convergence property compared to GD, if $rank(M)=1$, ScaledGD becomes exactly GD but with varying step-size. Therefore, to make a concise and clear comparison between ScaledGD with GD, we present the convergence results of ScaledGD for rank-1 case (the preconditioning relates to a number rather than a matrix). Then for AltScaledGD, to fully understand the convergence property we present the results for general rank-d in section 3.2, therefore section 3 consists of all our main results.\n\nOnce again, we thank the reviewer for your valuable comments, we will carefully revise the current manuscript according to the suggestions provided by the reviewer to further enhance the writing."}, {"review_id": "Ww91n7WWzt", "reviewer": "Reviewer_Cp2y", "summary": "This paper considers the low-rank matrix factorization problem (LRMF).  Recent work provided global convergence for gradient descent on LRMF starting from small random initialization and small learning rate, but the convergence rate there depends on the matrix condition number.  This paper considers a variant of gradient descent where the update is rescaled akin to steepest descent, called ScaledGD (and its alternating version, AltScaledGD). The main result of this paper is proving that ScaledGD (and AltScaledGD) converges at a faster rate, with no dependence on the matrix condition number.  Moreover, AltScaledGD converges even without small initialization and small step-size. ", "questions": "To address the concerns in the 'weaknesses' box, please defend the motivation for studying ScaledGD (or AltScaledGD).  Could these algorithms reasonably be implemented on nonlinear neural network optimization problems (or on optimization problems beyond matrix factorization where it could be the state-of-art algorithm)? \n\n\nCan you provide experimental evidence that the algorithms here perform significantly better than GD (or AltGD) when the underlying matrix is not exactly low-rank, but just approximately low-rank?  Of course, any algorithm for LRMF should remain competitive when the matrix M is not exactly low-rank.\n\n\n\n\n\n", "limitations": "yes", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The main theoretical results of this paper are quite solid.  ScaledGD (and AltScaledGD) are very reasonable algorithms for solving the LRMF problem, and this paper proves that they converge at a fundamentally faster rate than plain GD on the LRMF problem.  \n\n\n\n\n\n  ", "weaknesses": "The presentation is pretty good, although it does seem written in a rush in many places.\n\nThe main weakness of this paper is its motivation.  \n- The low-rank matrix factorization problem can solved very efficiently using specialized matrix algorithms, so if one studies simple general algorithms like gradient descent for LRMF, the end goal should not be to use it for LRMF, but rather to gain some understanding on the behavior of the simple algorithm on more complicated optimizations like neural networks.  But while gradient descent is feasible on more complicated problems, I do not see how to implement ScaledGD (or AltScaledGD) on neural network optimization problems, or on any optimization problem where a specialized algorithm can already do better.    ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We greatly appreciate the reviewer for your positive evaluation of our work, and we also thank you for your valuable and constructive suggestions. As for your concerns, we make detailed responses as follows. We will deeply appreciate that you can raise your score if you find our responses resolve your concerns.\n\n**Q1: The motivation for studying ScaledGD/AltScaledGD on LRMF and could these algorithms be implemented on nonlinear neural network optimization problems?**  \n**A1**: Gradient descent algorithm is of great significance in non-convex optimization problems as studied by recent works Chi et al. [2019], Li et al. [2019a], Ye and Du [2021]. ScaledGD is a simple extension of GD by scaling the gradient with a precondition matrix with minimal computational overhead, while it resolves the convergence barrier of GD for ill-conditioned non-convex optimization problems such as low rank matrix recovery (LRMR) Tong et al. [2021]. ScaledGD is also computationally more efficient than the current SOTA algorithm for the LRMR problem as analyzed in Tong et al. [2021].\n\nWhile the current convergence analysis of ScaledGD for LRMR in Tong et al. [2021] is only local (with spectral initialization), it is more important to study the global convergence of the ScaledGD for the non-convex LRMR problem. Our work makes the first attempt to study the global convergence of ScaledGD and AltScaledGD for asymmetric LRMF, and our results can be directly extended to general low rank matrix recovery problem with the help of conditions such as RIP for matrix sensing.\n\nThe ultimate goal of studying ScaledGD is to use it for more non-convex optimization problems such as the training of deep neural networks. We show our recent results of ScaledGD and AltScaledGD on more challenged optimization problems such as deep linear network and nonlinear network in Figure 1 and Figure 2 of the PDF file in the Author rebuttal part. \n\nSpecifically, we consider the following deep linear model:\n$$\\min_{W_3, W_2, W_1} f(W_1, W_2, W_3) := \\frac{1}{2} ||W_3W_2W_1 - M||_F^2$$ \n\nwith the ScaledGD iteration given by:\n\n$$W_1^{k+1} = W_1^{k} - \\eta (W_2^{k\\top} W_3^{k\\top}W_3^k W_2^k)^{-1} \\textcolor{red}{{{\\nabla} _{W_1}}f}$$\n\n$$ W_2^{k+1} = W_2^{k} - \\eta (W_3^{k\\top} W_3^k)^{-1} \\textcolor{red}{{{\\nabla} _{W_2}}f} (W_1^kW_1^{k\\top})^{-1}$$\n\n$$W_3^{k+1} = W_3^{k} - \\eta  \\textcolor{red}{{{\\nabla} _{W_3}}f}(W_2^k W_1^kW_1^{k\\top} W_2^{k\\top})^{-1} $$\n\n and the nonlinear model:\n$$\\min_{W_2, W_1} f(W_1, W_2) := \\frac{1}{2} ||W_2\\sigma(W_1) - M||_F^2$$\n\nwith ScaledGD iteration given by:\n\n$$W_1^{k+1} = W_1^k - \\eta {G^k} \\odot \\left( (W_2^{k\\top} W_2^k)^{-1} (H^k\\odot  \\textcolor{red}{{{\\nabla} _{W_1}}f})\\right)$$\n\n$$W_2^{k+1} = W_2^k - \\eta  \\textcolor{red}{{{\\nabla} _{W_2}}f }\\left( \\sigma(W_1^k) \\sigma(W_1^k)^{\\top}\\right)^{-1}$$\n\nwhere $G^k$ is a matrix with $G_{i,j}^k = \\frac{\\partial \\sigma(W_{1_{i,j}}^k)}{\\partial W_{1_{i,j}}^k}$, $H^k$ is a matrix with elements $H_{i,j}^k = 1/G_{i,j}^k$, $\\eta$ is the step-size and $\\sigma(\\cdot)$ is a piece-wise linear function as Leaky ReLU. It can be seen from Figure 1 that ScaledGD converges much faster than GD and the convergence rate is independent of the condition number $\\kappa$ of the target matrix $M$, whereas GD convergence at different rates for different $\\kappa$. Figure 2 shows the result of ScaledGD/AltScaledGD for the nonlinear network problem. Figure 2 (a) plots the loss curves of ScaledGD and GD under different condition number $\\kappa$, Figure 2 (b) plots the zoomed-in curves of GD in Figure 2 (a). It can be seen from these figures that ScaledGD converges much faster than GD even for this nonlinear network model, and the convergence rate of ScaledGD is also independent of the $\\kappa$, while in contrast GD converges at different rate under different $\\kappa$. In Figure 2 (c), we compare ScaledGD with AltScaledGD, it can be seen that both ScaledGD and AltScaledGD converges linearly to the global minima, while AltScaledGD converges faster than ScaledGD. Please refer to the PDF file for the figures.\n\n**Q2: Provide experimental evidence to show that the algorithms here perform significantly better than GD when the underlying matrix is not exactly low-rank.**  \n**A2**: We have tested the proposed methods on real data sets such MSI data and video data which are not exactly low-rank but are approximately low-rank. We show the experimental results in Figure 3 and Figure 4 in the attached PDF file at the author rebuttal part. It can be seen from these figures that even for real data sets with not exactly low-rank, the ScaledGD and AltScaledGD still converge much faster than the vanilla GD.\n"}]

Author rebuttal:
Dear AC and reviewers,

Thank you so much for your valuable comments and we truly appreciate the time and effort you've taken to review our work. We are also glad that the reviewers found our work valuable and give us positive feedbacks. Your feedback is very important to us, and according to the reviewers comments, we have revised the manuscript carefully and made detailed response to all your concerns (**please refer to our rebuttal for each reviewer for more detailed responses**).

As this paper focus on the theoretical side to prove the global convergence of ScaledGD and its variant AltScaledGD on the basic model of the low rank matrix recovery problem, reviewers may concern whether ScaledGD/AltScaledGD can be used for more advanced non-convex optimization problem such as nonlinear neural networks. To use ScaledGD/AltScaledGD for the optimization of deep learning is a very interesting research direction, we are still working on this problem. We provide one page PDF file to show some experimental results on this problem. Specifically, we show in the attached PDF file Figure 1 and Figure 2 the experimental results of ScaledGD/AltScaledGD on deep linear network and non-linear network, which all certificates that ScaledGD/AltScaledGD converge much faster than vanilla GD. Though ScaledGD/AltScaledGD work well for deep network, their convergence analysis require new theoretical tools, which is quite challenging compared to the convergence of LRMF, we will present the results in our next work.
 
Meanwhile, we also tested the ScaledGD/AltScaledGD on real data sets in Figure 3 and Figure 4 of the PDF file. In real data sets, the target matrix is not exactly low-rank but approximately low-rank with very large condition number $\kappa$. The experimental results show that ScaledGD/AltScaledGD still work well for real data sets compared to GD.

Though the proof of our results is a little bit lengthy, and requires some important lemmas and inequalities, we have provided the overall picture of the proof by the proof sketch for rank-1 case in section 4. The proof for rank-1 case is easy to follow and understand. The proof of rank-d follows directly the proof sketch of rank-1 but with moderate changes of lemmas and inequalities from rank-1 to rank-d, we thus leave the proof in Appendix. In this paper, we first present the main results in section 3 and provide an overall picture of the proof in section 4, detailed proof are provided in the Appendix, therefore the overall structure of the manuscript is clear. In the revision, we will further improve the organization of this paper to make it easy to read. 

Once again, thank you for taking the time to review our work and providing valuable insights, and we will take all the suggestions given by the reviewers into consideration for future improvements. We would also like to have discussions with all the reviewers if you have any further concerns.

Meta-review: The reviewers agree that the paper makes a solid, worthy contribution. One dissenting reviewer expressed some skepticism with the rank-1 proof for ScaledGD. Indeed, one can argue that in the rank-1 case, ill-conditioning is impossible, and this completely obviates the whole point of preconditioning. I would also very much like to see the minor revision done for the rank-d for ScaledGD. Please incorporate reviewer feedback into the final submission.
Decision: Accept (poster)