Provable Acceleration of Nesterov's Accelerated Gradient for Asymmetric Matrix Factorization and Linear Neural Networks
Authors: Zhenghao Xu
Yuqing Wang
Tuo Zhao
Rachel Ward
Molei Tao
Venue: NeurIPS 2024 poster (2024)
Keywords: matrix factorization
nonconvex optimization
Nesterov's acceleration
linear neural networks
Primary area: optimization

Abstract: We study the convergence rate of first-order methods for rectangular matrix factorization, which is a canonical nonconvex optimization problem. Specifically, given a rank-$r$ matrix $\mathbf{A}\in\mathbb{R}^{m\times n}$, we prove that gradient descent (GD) can find a pair of $\epsilon$-optimal solutions $\mathbf{X}_T\in\mathbb{R}^{m\times d}$ and $\mathbf{Y}_T\in\mathbb{R}^{n\times d}$, where $d\geq r$, satisfying $\lVert\mathbf{X}_T\mathbf{Y}_T^\top-\mathbf{A}\rVert_F\leq\epsilon\lVert\mathbf{A}\rVert_F$ in $T=O(\kappa^2\log\frac{1}{\epsilon})$ iterations with high probability, where $\kappa$ denotes the condition number of $\mathbf{A}$. Furthermore, we prove that Nesterov's accelerated gradient (NAG) attains an iteration complexity of $O(\kappa\log\frac{1}{\epsilon})$, which is the best-known bound of first-order methods for rectangular matrix factorization. Different from small balanced random initialization in the existing literature, we adopt an unbalanced initialization, where $\mathbf{X}_0$ is large and $\mathbf{Y}_0$ is $0$. Moreover, our initialization and analysis can be further extended to linear neural networks, where we prove that NAG can also attain an accelerated linear convergence rate. In particular, we only require the width of the network to be greater than or equal to the rank of the output label matrix. In contrast, previous results achieving the same rate require excessive widths that additionally depend on the condition number and the rank of the input data matrix.

Provable Acceleration of Nesterov's Accelerated Gradient for Rectangular Matrix Factorization and Linear Neural Networks
Zhenghao Xu Georgia Institute of Technology zhenghaoxu@@attech. edu
Yuging Wang University of California, Berkeley yq. wawg@berkeeee..cooo edu
Tuo Zhao
Rachel Ward University of Texas at Austin rward@math. utexas. edu
Georgia Institute of Technology
tourzhao@gatech.. edu
Molei Tao
Georgia Institute of Technology mtao@gatech. edu
Abstract
We study the convergence rate of first-order methods for rectangular matrix factor- ization, which is canonical nonconvex optimization problem. Specifically, given a rank-r matrix A E Rmxx we prove that gradient descent (GD) can find pair e-optimal solutions X E R and YT Rand where d 2 r, satisfying YY AlF S <||A]] || in 7 Oxx² 2 log iterations with high probability, where denotes the condition number of A. Furthermore, we prove that Nesterov's 's accelerated gradient (NAG) attains an iteration complexity of O1: log 2), which is the best-known bound of first-order methods for rectangular matrix factorization. Different from small balanced random initialization in the existing literature, we adopt an unbalanced initialization, where Xo is large and Yo is Moreover, initialization and analysis can be further extended to linear neural networks, where we prove that NAG can also attain an accelerated linear convergence rate. particular, only require the width of the network to be greater than equal the rank the output label matrix. In contrast, previous results achieving the same rate require excessive widths that additionally depend on the condition number and the rank of the input data matrix.
Introduction
Nonconvex optimization is pervasive in the training of modern machine learning models. Despite the success of first-order methods in practice, thcoretical understanding of their convergence properties limited even for simple nonconvex problems. Take the rectangular low-rank matrix factorization problem example, which is canonical nonconvex problem:
1 |A- XX XY
min XeRwxd Yd
f(X, Y)
where we solve for two small matrices X E Bmxd and Y E Rn to approximate a big rank-r target matrix A I mm with & min min(m, n) and m, not necessarily equal. Specifically, consider the over parametreetri regime where d 2 r, so that the global minimum of (I) zero. While various
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

direct methods exist for solving ( we focus on understanding the global convergence behaviors of first-order methods applied to such nonconvex problem, with the motivation of gathering insight into the training dynamics of neural networks.
Most existing results study the simplest first-order method, gradient descent (GD), under different initialization schemes. Note that the initialization scheme matters to convergence analysig due to the fact that ( is a nonconvex and nonsmooth c ootiiiizaiion problem. Thus, proper initialization is important for the fast convergence rates of first-order methods. Ye and Du [202]] show that with small Gaussian random initialization, GD can find XT and Yr such that I f(XT. Yr) S in T= (at (m + n)* log :) iterations with high probability, where k denotes the condition number. Jiang et al. [203)] improve this result to On log +) which has no explicit dimensional dependence on m and nt These analyses rely on balanced initialization where entries of Xo and Yo have the same variance so that the iterates are guaranteed to stay in smooth region.
Moreover, we remark that to the best of our knowledge, we are not aware of any existing theoretical results on rectangular matrix factorization analyzing the global convergence rate of more ad advanced first-order methods such as Nesterov's 's accelerated gradient (NAG), which has been proved to achieve faster rates for smooth convex optimization problems [Nesterov] 2013).
Recently, Ward and Kolda (2023) showed that by using unbalanced random initialization where Xo is larger than yo. alternating gradient descent (AIGGD) that alternatingly optimizes X, and Y, via gradient steps can achieve (d - + 1) 2x² log 2) iteration complexity. However, their analysis is specifically designed for AltGD and not applicable to GD, let alone more advanced methods such as NAG which are nevertheless widely used in machine learning practice. Two questions naturally arise here:
Q1: Can GD achieve the same convergence rate as AltGD for !
Q2: Can more advanced first-order methods (e.g. NAG) achieve faster convergence rate for T
Main Results. We answer the two questions above affirmatively by developing a new theory on first-order methods for (1). Specifically, we consider an unbalanced initialization scheme X,- cA and Yo = O, where > O is a large constant and 4 is Gaussian random matrix. Note that our initialization of Xo the same as that in Ward and Kolda [2023]. J. but they initialized Yo using a small Gaussian random matrix. This modification is mainly for simpler analysis and makes little difference in practice. Under our new initialization scheme, we first prove an (d r + 1) (1))2pp) 22,² log 2)
iteration complexity for GD (Theorem I] matching that of AltGD in Ward and Kolda [2023) Our analysis is based on new theoretical framework different from Ward and Kolda [2023] and can be further extended to analyzing NAG. We then show that NAG can attain a provable acceleration
with an (dd(d - + 1) -1 log -) iteration complexity (Theorem 2). We discuss the tightness of our
results (Remark 2 and conduct numerical experiments for validation (Section 5). Empirically, we
observe that NAG exhibits a much faster rate than GD and our bounds are quite tight.
Our analysis technique can also be applied to linear neural networks. We consider unbalanced initialization similar to the one for ( We show that NAG can achieve an accelerated convergence rate for each overparameterization level (Corollaries to 1) under the commonly adopted interpolation assumption (Assumption] [ see e.g. Du and Hu 2019 J. In particular, we only require the network width to be greater than the rank of the output matrix.
Additional Related Work. For matrix factorization, there is large body of works focusing on the symmetric case, where A is positive semidefinite and A = XX [Bhojanapalli et al. 2016 Li
al. 2018 . However, these analyses are difficult to generalize to the rectangular case (1) due the additional unbalanced scaling issuc")
Fl To overcome this, additional balancing regularization is often
required [Tu et al., 2016 Park et al. 2017 Zhang et al. [202 Bi et al. 2022], which changes the
objective function in (I) Du et al. [018]] show that GD can automatically balance the two factors hence explicit regularization is not necessary, but they only establish linear convergence rate for rank- 1 matrix and cannot generalize to rank-r case. Some other works remove this regularization for the
proving convergence of GD for general initialization under large learning rate and similar objective functions, but nonasymptotic convergence analysis is very challenging and highly dependent initialization.
'There are some works Waag et al. 2022 2023
2 Here, the nonsmoothness refers to the lack of uniform Lipschitz constant for the gradient the full domain. In the symmetric case, the solution's uniqueness is up rotation, whereas in (I) it is also up scaling.

---

general matrix sensing problem and show linear convergence rate for general ranks [a et al. 2021 Tong et al., 2021a b). These results do not directly apply our setting as they require singular value decomposition (SVD) at initialization, which consumes roughly the same amount of computation as solving I Moreover, these works only consider exac! parameterization (d r), leaving out the overparameterizzaion regime (d > r). Overparameterization may heavily slow down convergence due to the possible singularity of iterates [Stöger and Soltanolkotabi [021], thus some works consider preconditioning for acceleration [Zhang et al. 2023 Xu et al., 2023] These preconditioned methods are specifically tailored to symmetric factorization and are not directly comparable with the first-order their algorithms not only use the gradient. For algorithmic acceleration, Zhou et al. 2020] first propose a computationally tractable modified Nesterov's 's method for general loss function that is L-smooth f--strongly convex to the product X However, their method still requires balancing regularization when applied to rectangular matrices, and SVD-based initialization that dominates the computation. Moreover, their acceleration pertains to the condition number T./J of the loss function rather than A: of the target matrix, on which their dependence is ((r²).
methods consider,
For linear neural networks, Du and Hu 2019) and Hu et al. 2020) show linear convergence of GD with Gaussian and orthogonal initialization respectively, and Min et al. [2021] studies convergence rate of gradient flow (GF) for unbalanced initialization. [Wang et al. 2022] show that Polyak's 's heavy ball (HB) method [Polyak] 1964] attains accelerated convergence rate with orthogonal initialization.
Liu al. [2022] further investigate NAG and show similar accelerated rate for Gaussian initialization.
All these previous works consider sufficiently wide networks that depend on the output dimension, the rank, and the condition number of input. The results are summarized in Table
Table 1: Results for linear neural networks. All results in table are based on the assumption L = AD for some A with cond(A) A) O(1), where D denotes the input data, L denotes the output data, dout denotes the output dimension, 5 denote the failure probability, r rank(D), r rank(L), 7
D F | k cond?
2
(D), cond?
O(k²), N2 O(k).
Algorithm
Initialization
Width
Rate
GD
Du and Hu
2019
Gaussian
Ω
[rk
(rx"(dom (dout + log 5))
(1 3 )
4/. )
GD
Hu et al.
2020
Orthogonal
Ω
PK? (dout + log ())
(1 1n.
HB
Wang et al.
2021
Orthogonal
N² Q D (dout + log f))
(1 IV )
NAG
Liu al.
2022
Gaussian
2 rx 3 (dout + 1ogg 4))
(1 2VK )
NAG
(ours, Corollary
Unbalanced
12
2 F + Ailog }))
(1 2
NAG (ours, Corollary
Unbalanced+Orth
13
2VK
NAG (ours, Corollary
Unbalanced
14
w dont + 22log 5)
(1 2/12
Throughout this paper, ||-|| denotes the Fuclidean norm of vector or the spectral norm of matrix, and ||-1|p denotes the Frobenius norm of a matrix. For any matrix, a,(-) denotes its i-th largest singular value. For square matrix, (-)-) denotes its i-th largest eigenvalue. For nonzero positive semidefinite matrix, Amax(() (.) and Amiu (-) denote its largest and smallest nonzero eigenvalues respectively. For matrix X, we use col col(X) to denote its column space, ker(X) to denote its kernel space and define cXn == ||X xt as its condition number, where X denotes the pseudoinverse of X. For any positive integer ni, I,, denotes the identity matrix of size n. We use 6 to denote the Kronecker product between matrices, @ to denote the direct sum of vector spaces, and vec(-) to denote the column-first vectorization of a matrix. We use N(u, o?) to denote Gaussian distribution with mean μ and variance o².
Notations.
2 Results for Matrix Factorization
We start with formalizing our initialization scheme for matrix factorization problem (]. Let & E Rexd be Gaussian random matrix with i.i.d. entries ($b jij (N We initialize
X, cA Yo 0,
where e > is a constant to be specified later. Typically, we require e to larger than a certain threshold, which depends on the dimensions, the extreme singular values of A, and possibly the
3

---

condition number of X We note that changing would not affect cond(Xo). hence there is no recursive definition. As we mentioned, (2) is modified version of the initialization in Ward and Kolda [2023], where we replace the small random Gaussian matrix Yo by 0 and choose independently of the step size. We set Yo- mainly for simplicity, and our analysis can be extended to the case where Yo is sufficiently small Gaussian random matrix. While the initialization of Xo differs from standard Gaussian initialization, it has the following interpretation: Suppose we start from & = -1 and let X_1 c' and -11 c for some 0 < c' < c" < 1 and Gaussian random matrix 4', then by taking a gradient step with step size c/c" we get X R cA and Yo O. This initialization of Xo also coincides with the first step of randomized singular value decomposition, which is also referred to as sketching (see e.g. [Halko et al. 2011
2.1 Gradient Descent
With initialization (.. we can analyze the global convergence rates of various first-order methods.
Consider gradient descent (GD) first. The gradient of the squared Frobenius error in (T) is given by
Vxf(X, Y) = (XYT T AjY, Vyf(X Y) = (XY A) X.
For 2 0, the GD update with constant step size 1) > is written as
X++1 Y1+1/
7 Y - AJYY, X. Y - (X, - -A)
Let R. = X,Y, -A denote the residual, then f(x,, Y,) = Rell We have the following convergence rate for GD.
Theorem 1 (GD convergence rate). For < < C1, denote 8 3e -di-++)) = } where 01 and 02 are universal constants. Denote L ox())),
(Xo). Let 2
coodd (Xx)]l)X (Xl) be sufficiently large constant. Then with e plugged in c 12r(vd- BerVV-Vr-I) cond? (Xa)-1
(d),(A)
initialization 2. GD returns X4 and Y, with probability at least 1 such that
[Rell S 30 (A)
(1-4)
64
In particular, if G. then GD finds |R 11p S E || in
d²
T=0 72 - r + 1)²
log
iterations, where C = 27- (d-r((=++1)) cond' cond'(X,)e" (X,)
162
(ondd"XXo-TT
Theorem shows that GD converges in (d log iterations with initialization (2) and the constant prefactor does not have dependence on the ambient dimension m and n. This matches the convergence rate for AltGD derived in Ward and Kolda [2023). The step size L+ is commonly used in optimization literature and leads to optimal convergence rate [Nesterov] 2013).
While the bound on |RRllp in Theorem I does not explicitly depend on || l| the norm still affects the convergence rate through the choice of defined in (2) When e c O(Vl|A(l)) the bound linearly depends on || When > s, the bound linearly depends on c², which dominates |||||
2.2 Nesterov's Accelerated Gradient
We then consider Nesterov's accelerated gradient (NAG) method [Nesterov] 2013 applied to ( We take the form of NAG that is originally designed for smooth strongly convex loss function &
2++1 & v((2), ž 2t41 + 3(( =2,,
where is the step size, ,9 is the momentum parameter, and or in our case consists of both X and Y. If we focus on the {&, } sequence with &, = (X,, Y,) and plug in the objective function in (I).
then with X_ = X1 and Y = Yo. the NAG update is given by
X 1+1 Y(+1
(1 + (X, nR, Y.) B(X,-1 1/R,11 Y(-1) (1 3Y, RR, Xx) 3(Y - - -1R((X(-1))
(4)
We have the following convergence rate for NAG.

---

Theorem 2 (NAG convergence rate). For 0 < c1, define as in Theorem 1 Denote L = oî (Xo). == (Xo). Let 1
3-
-L-VI VLtVA e= 29 d(2//+v/))ll p be constant. Then with oP('
plugged in initialization
NAG returns X, and Y with probability least 1 such that
(A) (1 v/
Relly
64cond(Xo)
2VL
In particular, if then NAG finds ||T||| I <<||A||p in
dk
T(d -(1--+1) T T=0
log
841d(2v 64 V-- rond(Xa))
iterations, where C
Theorem 2 shows that NAG can achieve O(d(d - r x: !) iteration complexity with high probability. The dependence on the condition number x improved from being quadratic to linear. Moreover, the dependence iteration number has an (dd²) dependence in the worst case (d = r). Here, NAG has at most O(d) dependence. The level of overparameterization d will affect both the convergence rate and the probability of success. To ensure a small fail probability 6, it requires d = r + 22log 7 Again,
the dimension is also improved. As shown in Theorem T the GD
the step size 1 and momentum
VL-VE
commonly used in the literature [Nesterov 2013
VL+VE
3 Proof Sketch for Convergence Rates
We now provide the proof sketch for Theorems I and 2 Our proof is based on induction. We start with the assumptions that X, and Y, are not too far from Xo and Y, respectively and the initial residual is bounded by some constant, which are guaranteed at time O. Given the induction assumptions, we then track the dynamics of residual R, and decompose it into linear and higher-order parts. We can show that the linear part is contracted and the higher-order part shrinks exponentially, together implying that ||R+ || O(0') for some 0 E (0, 1) and X and Y,+1 is still within bounded region around initialization. This shows the induction assumptions for the next iterate, thus by invoking the induction complete the proof.
The key our proof show the contraction and its rate. Firstly, the linear part of the dynamics is not a contraction over the whole space, thus we need to identify in which subspace it is contraction. Secondly, we need quantify the rate of contraction to get global convergence rates. These necessitate the following proposition about the properties of Xo with initialization (2)
Proposition 1. For any T,C 0, A E Rm being rank-r matrix with condition number K = cond A), & Randd being random matrix with i..dd entries from N 1/d), the following holds for Xo cA & with probability at least 6;
r(vd - Vr
2vd+ VF Vd
or (A) S (Xo) <
(A))
Vd
where 5 = 3e (in((d-++)])) log of oad. ei and e2 are universal constants. When it holds, the condition number of Xn bounded:
2/d + VT
6d
cond(X,) 7(vd - Vr-I) VI
7(d r
By Proposition] [ the top singular value of X,, is bounded from above by 0 (A), and the r-th singular
value of X, bounded from below by or (A), hence we have cond( (x) = 0(x). Moreover, Xo has col(A). This subspace preservation property will be passed to subsequent iterations of first-order methods and
rank with probability and thus it preserves the column space of A, i.e., col(X,)
critical to analysis. In particular, we will show this space corresponds to the contraction subspace.
5

---

3.1 Proof Sketch for GD Convergence Rate (Theorem
!
As mentioned, we track the dynamics of R, for GD to prove Theorem Let vec(R,) denote the vectorized residual, then the GD update (3) corresponds to the following dynamics:
Proposition (GD dynamics). Ler P; X,+1 X, and Q = Y(+1 Y, denote the update steps
for 2 0. Then GD (3) admits the following dynamics:
F++11 (Imn HHo)r E.:
where H, (Y,Y,) Im + I & (X,X)) and &, nHo Hi)r, + vec(P.Q.).
The linear part at time is (Imn )r, which is approximately (Imm HHHrr when X, and Y, are close their initialization. The approximation error along with the higher-order term vec(P, is contained in &.. It follows immediately from Proposition 2 that
Te+1 (Imn H/Ho) e+1 ro Σ (1mn Ho) E..
If TGD == Im Ho a contraction map, i.e. it has all eigenvalues bounded | S for some p [0, 1), and the nonlinear error &. shrinks exponentially rate 0 (p. 1). then have ||r, = ((8). However, for d < min(m, n2/2, TeD cannot be a contraction map for any 7, the rank of Hn is most (m + n)dd < mn. In fact, if Xo initialized rank(Ho) nr < mn regardless of the choice of d. As Hn has no full rank, TGD must have a non-trivial eigensubspace corresponding eigenvalue 1. In the following lemma, we show that r, and &, are not in this "bad" subspace but rather in a contracted subspace as desired.
in (2), then
Lemma (Eigensubspacee, Let C R denote the linear subspace containing all eigenvectors of Ho with positive eigenvalues. If Xo is initialized as in ( then we have
H = (col(A))" and Er),200220 C H.
where Ho, Yt and &, are defined as in Proposition
2
Given that rt and E, are in the contracted subspace H throughout all iterations, the convergence rate is determined by the contractivity of TGD over this subspace, which corresponds to the condition number of Xo with initialization ( Lemma (GD contractivity). Let L (Xo)) μ (Xo). and H be defined as in Lemmal 1 E (0, 2) then for any v E H,
Let
[TDDV|| S max([1 nLI, |11 nn1 livl
2 then | < In particular, if L+p'
L-R l|vl] I+H
By Lemmas I and 2 the linear part of GD dynamics contracts r, and & and the rate of contraction is p max [TT L2 -mul]. To complete the proof, it remains to bound the magnitude of error E, and show induction conditions for the next iteration. This is guaranteed by the following lemma. Lemma 3 (Nonlinear error). there exist 0 E (0, 1) and some constants Cj and C2 such that for any S t, the GD dynamics (5) yields ||r.]| S C18* [[ol] ||,, Xool I C2. Y| Yolle I Cz.
then have
[e QT s C3 ||roll and [ln(Ho H.)r S C₂B" ||oll for some constants O3 and C₂ depending on C1 and Cz. Moreover, if C1 and C2 satisfy
(max( (|Xoo)l ooll + +2)
||ro|| S (1 (1- 8)C2.
(6)
then have [Xe+1 Xool C2 and Y++1 Yolle C2.
Lemma shows that ||E,|| = O(0') if the residual shrinks exponentially and the iterates are not too far from initialization, which in turn implies that X,+1 and Y,+1 are also within the Ca-balls around their initialization. turns out that there a set of valid coefficients for the induction to go through as long as the in (2) is sufficiently large. Therefore, by choosing properly and plugging L-
in p L+w and 0 1 E. we prove the convergence rate for GD, and the iteration complexity follows immediately from Proposition] I The complete proof is provided in Appendix B.6

---

Remark 1. In our proof. the unbalanced initialization guarantees the existence of induction constants
in Lemma The amount of unbalance affects the constant factors but will not affect the convergence
rate (1
[ ). To be explicit, suppose we initialize Xo 01 A E Rmxxd Yo 02 E RRaxd
1.j (0, 1/d) and ($2)1. ~ N n/), then by replacing Ho in Proposition 2 with Hy = In @ (X,X)), ), we can generalize the proof and obtain the same convergence rate when e1 sufficiently large and C2 O(1). Meanwhile, we have [Rollp S (1 + (ce)c2) || with high probability ( [Ward and Kolda 2023y. Therefore, when eı is fixed, a smaller e2 yields a smaller initial loss, resulting in a smuller constant factor. Meanwhile, the convergence rule remains the same the condition number of H2 is not affected, and the shift H. Hy is controlled for small ez-
where
3.2 Proof Sketch for NAG Convergence Rate (Theorem
We now turn to prove Theorem 2 Similar to GD, we track the residual dynamics of NAG.
Proposition 3 (NAG dynamics). Let P. X,+1 -x, and Q Y(t1 Y, denote the update steps for t 2 0. Then NAG (4) admits the following dynamics:
Tt+1 Ft
(1 (1+8))[mm (I - HoO
-8(Imn -
Ft rt-1
E1
+
(7)
I Inn
0
where H. (Y, @ Im + II, (X,X,), S1 +h
6: = : 3 ( + 3n vec Y 1 Q + R(-1),
4 (1 + (Ho H,)r, (n H111)r-11-
As Proposition shows, NAG dynamics 7 has additional momentum terms involving Pa and Q When 3 = 0, reduces to the GD dynamics (5. The introduction of momentum terms allows the linear part in contract r, and E, faster. To be more explicit, let
(1 ()+ (Lmn HHH) -B(Imm - H)
TNAG=
(8)
Inn
0
denote the linear part of the system. The next lemma shows NAG improves the rate of contraction.
Lemma 4 (NAG contractivity). Let B- = VT- then for all (u, v) E H x H. VT+
TNAG S (1-V |
L
The price to pay for the faster rate of contraction is the additional perturbations. The 4 term characterizes dynamics shift, which can be controlled as GD in Lemma The C, term characterizes higher-order terms in the dynamics (7). which can be controlled by the updates P, and Q In GD, these terms correspond to the gradient that they can be bounded if R, shrinks and X, and Y. are not too far away from Xo and Yo. In NAG, we have
P. = RR +
Y.
and similar equation holds for Q If shrinks at rate 0 > 0 2 3, then we have O(0*) upper bound for ||Pellp and | We formalize the argument in the following induction lemma.
Lemma 5. Suppose 0 < B S 0² < <
1. If there exist some constants C₁ and C2 such that for
any s S t, the NAG dynamics 7 yields
r.
S C
IX, Xolle Cz. and r-1
ro
re-1)
YY, Yollr S O2, then we have
2
((T)
IIC.l1 < C2
ro r-
and ||a|| s Cap'
for some constants O33 and C2 depending on C₁ and Cz. Moreover, if C1 and C2 satisfy
(max() Xoll Yoll) + C2)
$ {1 - 0)
(9)
then we have [X++1 Xolle S C2 and || Y Yolle C2.
7

---

Lemmapji similar to Lemma 3 Again by choosing a sufficiently large to initialize Xo, we can find
of feasible coefficients for the induction. In particular, we plug in p vL 0 =01-
2vL
and B VI.-V then c defined in Theorem ensures the success of induction, hence the accelerated VI++
convergence rate of NAG is proved. The complete proof is provided in Appendix C.4
Remark 2. Our analysis differs from that of Ward and Kolda (2023.. Their analysis is based on the Dolyak-Lojasiewice (PL) inequality [Lojasiewicz) 1963/: [Xx,, Y) is approximately μ-PL and L-smooth in Y, and the unbalanced initialization (large X small Yu) ensures that only matters the convergence rate, X is not changing by much. Since the objective function in ① is quadratic in X. the problem has condition number & = L O With these notations, the complexity in
Ward and Kolda (023) reads as O log 2 which is standard for PL functions.
However, PL inequality cannol fully capture the properties of ②. and the analysis in Ward and Kolda 2023] does not apply to the case where X, and y are updated sinultaneously rather than alternatingl. In fact, if we fix X Xo and optimize Y only, then our initialization (2) makes the
problem quasi-strongly convex (QSC), which is strictly stronger than PL (Necoara et al. 2019 For
QSC functions, NAG can achieve O DVVR R Rlgg }) convergence rale Necoara et al. 2019)) while for PL
functions the rate can only be { log !) \Yue et al. 2023).
We note that simultaneously optimizing X and causes the nonconvexity issue and hence T does not fit in the framework for QSC functions as it requires convexity. Our results in Theorems and match the ones for QSC functions and Theorem 2 further matches the lower bound for general smooth strongly convex functions (Nemirovski and Yudin 1983), which generally exhibit more favorable properties than nonconvex optimization problems to which ( belongs. Hence, we conjecture that our rate bounds tight for both GD and NAG. However, rigorous theory is yet be constructed to solidify our conjecture.
Extension to Linear Neural Network
Our analysis can be extended to the squared loss training of two-layer linear neural networks, which is equivalent to the following optimization problem:
- - -L-
min XgRmxxd Y e
S(X,)
(10)
Here, D E RaxN corresponds to all input data concatenated together, L E m denotes the labels, N is the total number of training data samples, and d is the network width. We make the following interpolation assumption, which is commonly adopted in the study of the convergence rate of linear neural networks [Du and Hu (219) Hu et al. 2020 Wang et al., 2021].
Assumption 1 (Interpolation). There is A with cond(A) O(1) such that L = AD, rank(L)
Under Assumption [ we can establish a linear convergence rate for NAG when the initialization is sufficiently unbalanced and Xo contains the column space of L.
Theorem 3. Let L (Xo) Amax (DDD) )) j =f{(X) Amin Amin(DDD) (DDT). Suppose Yo = 0. Xo is initialized such that col(Xo) 2 col(L) and satisfies
up 2 4v2 LD I (1+p),
(11)
where p F. does not depend on the scaling of Xo. If we choose 1 and 3 = VL-vi VI
JB
Vi+VT' then the 1-th iterate of NAG (X, and Y,) will correspond to residual R, = X.Y,DD - -L satisfying
(1
((()))omin (D)
Vi 2
R 1p <
576
Equivalently, let C (m)i)))))()) ( 576 LD ll
then the iteration complexity for e relative error is
01 (X,()) Amas (DD
E )
T =
log
(C)
(Xo) Amin (DD
8

---

As Theorem shows, if our initialization guarantees the column space of Xu contains columns of L, then the residual shrinks a linear rate. the worst case, the columns of L span the whole space of Rmm hence d should be at least m. However, when the data exhibits some low-dimensional properties, e.g., D low-rank, then can be much smaller than m and N. In this case, an initialization similar to can meet the requirement of Theorem 3 Moreover, note that the convergence rate depends on both and Xo, hence by orthonormalization we can make cond(X,) = for a faster rate. When S d < min(m, N), such orthonormalization is affordable as it takes (mmd) time rather than Om in the worst case. We summarize these initialization options:
d d21 r, 2 r, 2 m,
+ R Nxd
+ kJ
(001//))
X, c. L4
Yo 0;
(12)
T R Nxd
X, Orth L Yo
(13)
+ Rm
k. // 1/d), X,-
Yo = 0:
(14)
Here, Orth(-) denotes the orthonormalization result whose columns are orthonormal. By applying singular value bounds and invoking Theorem
3 we obtain the following corollaries.
Corollary Suppose initialization
12)
b is applied with some sufficiently large c. For any 0 < T < C1.
0 < 8 1, if d r 1 52(lgg then with probability least 6, NAG finds XT and Yrr such that f(T:: YT) S |LD where
d (L) V Amaa (DD
T = o
log
T(d-r+ Amiin (DDT)
Corollary Suppose initialization probability 1, NAG finds XT and Yr such that f(XT, Yr) I <<|LDTT [| where
13) is applied with some sufficiently large c. If 2 r, then with
T T=o
Amax (DD
log 1
Amin (DD
Corollary 3. Suppose initialization (14) is applied with some sufficiently large c. For any 0 < T < ci < 8 if 2 m 2log
). then with probability at least 1- 6. NAG finds XT and Yrr
such that (XT, Yr) < LD
where
d
Amax
(DD
log 2
T= 0
r(d m 1) V Amin (DD
DDi
Remark 3. While we only consider NAG in this section, our analysis can be directly applied to GD convergence rate with initializations
and obtain Of a (2))))mo (DD
log 1
(2(X)) (DDT)
Corollaries 2 and show accelerated convergence rate of NAG, as their dependence the condition
number A =
Amiin (DD cond (D) is (VKk) rather than O(k), matching the results in Wang et al. [221] for HB Liu al. [2022 for NAG. Meanwhile, Corollary has an additional dependence
Amaz (DD")
on (L) Under Assumption
(L) O(vR) and hence the overall dependence ((s).
Although this is slower than NAG with initialization [3} (4). it still outperforms GD with initialization (12). which has (xx)) dependence. Compared to previous results listed in Table I we Q(m + log 3) depending
the initialization and there is no additional dependence on the input rank or condition number. When the data low-rank, (w.r.t. output dimension and sample size) network to converge linearly. can be further accelerated if orthonormalization is adopted (I3), which echos the orthogonal initialization in Hu al. (2020) [Wang et al. [2021). I]. In the general case, our analysis still provides a tighter result, as (14) only requires the width to be 2(m + log })-
only require the network width to be lor+ }
NAG with initialization (12) enables the sublinear-wide
Numerical Experiment
We validate our results via numerical experiments. For matrix factorization we construct
A T e 11000080 where Σ E 1g55 is diagonal with 0f (Σ) 1 and 05 Σ) 0.2, and

---

U and V are orthonormal matrices. We set different levels of overparameterization (d 2 5) and initialize Xn and Yo according to 2 with 50vd. For linear neural network (TO), we construct the input data matrix D U R where Σ R diagonal with 01 [Σ) = 1 and
(s( 0.5, U is orthonormal and V is Gaussian. We use Gaussian matrix A E R 100 to
construct the label matrix L AD. We keep 50vd and initialize X. and Yo according to 12 We run all experiments with 10 different initialization seeds and take the average.
We first compare GD and AlGDD. For matrix factorization, We use the same initialization and the same step size 7) 2/(L + 14), where L and μ are computed as defined Theorems [ 2 For linear neural networks, L and are replaced by L and j in Theorem 3 As shown in Figure they perform very similarly and the loss curves are overlapped. To better illustrate, we additionally use 1/L. for GDD, and performs differently from GD/AIIGD with rj
matrix factorization
linear network
10'
F-T GD.d=5
AlGDDamm
10-2
10
5- 00,5-90
10-1
100
260
1:00
260
Ineration
Iteration
Figure 1: GD and AltGD achieve similar performance. The left plot is for ①. and the right plot is for 1T).
2/(L+ + p).
We then compare GD and NAG. For matrix fac- torization, we use 7 = 2/ (L+ for GD and use
factorization
n I/L and 3 = (vT. vu)//vT++ vu) for
10a
NAG, where L and are computed as defined
G0,des
NAG.d-5
in Theorem 2 For linear neural networks, we re- place L and μ by L and jí defined in Theorem 3
10-40
6D,6-20
10-1s
GD. 6-20
NAG.1=20
The results are shown Figure As illustrated, NAG exhibits much faster convergence than GD. Moreover, a higher overparameterization level helps accelerate convergence, predicted by the prefactor (ppoly(d - + 1)=1) in our iteration complexity.
10.29
NAG.
10-25
100
200
0
100
200
Iteaatin
Iteration
Figure 2: NAG converges faster than GD. The left plot
for I and the right plot is for 10
To further illustrate the tightness of our the- ory, we compare with the actual loss in matrix factorization, as shown in Figure 3. We set
1=10
k=100
GD,d=5
theoretical predictions
GDIT).w55
10-1
2 and (E)) E {0.1, 0.0T), keeping other settings un- changed. The theoretical prediction at step is computed as (/-=/))² f(Xo, Yo) for GD and (1 (1- (1-V)/2VI)) f(Xo, Yo) for NAG. We observe that the slope of the predicted loss closely matches the actual loss, supporting the
10-*
NAGITI.--5
G0,3-20
CDIT)
NAG.2-20
10-16
NAGITI
50.5-30
GDIT).020
10144
NAG
NAGITI
1000
1000
2000
Itoration
Iteaaion
Comparison of predicted loss and numerical loss for matrix factorization. The left plot is for GD where k 10, and the right plot is for GD and NAG where K = 100. (T) denotes theory prediction.
Figure 3:
tightness of our theory, especially for GD. Addi- tional experiments are provided in Appendix E
6 Conclusion and Future Work
We establish the convergence rate GD and NAG for rectangular matrix factorization I under an unbalanced initialization and show the provable acceleration of NAG. We further extend our analysis to linear neural networks (TO) and show the acceleration of NAG without excessive width requirements in previous work. Numerical experiments provided to support our theory.
We believe our analysis can be extended to initialization where X. cA and Yo 0 rather than exact equalities. Relaxing the exact rank-r condition to approximately rank-r is also possible generalization. The linear neural network model considered in this paper cannot fully capture the practical settings. We leave the extension to nonlinear activations for future work.
10

---

Acknowledgments and Disclosure of Funding
The authors are grateful for the partial support by NSF DMS- 1847802, Cullen-Peck Scholarship, and GTT-Emory Humanity.Al Award. RW was supported in part by NSF DMS-1952735, NSF IFML grantv2019844, NSF DMS-N2109155, and NSF 2217033. We thank the anonymous reviewers for their helpful comments.
References
S. Bhojanapalli, A. Kyrillidis, and S. Sanghavi. Dropping convexity for faster optimiza- tion. In Conference on Learning Theory, pages
PMLR, 2016.
Y. Bi, H. Zhang, and J. Lavaei. Local and global linear convergence of general low-rank matrix recovery problems. In Proceedings of the AAAI Conference Artificial Intelligence, pages 10129-10137, 2022.
S. Du and W. Hu. Width provably matters in optimization for deep linear neural networks. In International Conference on Machine Learning, pages 1655-1664. PMLR, 2019.
S. Du, W. Hu, and J. D. Lee. Algorithmic regularization in learning deep homogeneous models: Layers are automatically balanced. Advances in Neural Information Processing Systems, 31, 2018.
N. Halko, P.-G. Martinsson, and J. Tropp. Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions, SIAM Review, 53(2):217-288, 2011.
R. A. Horn and C. R. Johnson. Topics in matrix analysis. Cambridge University Press, 1994.
W. Hu, L. Xiao, and J. Pennington. Provable benefit of orthogonal initialization in optimizing deep linear networks. International Conference Learning Representations, 2020.
L. Jiang, Chen, and L. Ding. Algorithmic regularization in model-free overparametrized asymmet- ric matrix factorization. SIAM Journal on Mathematics of Data Science, 5(3): 2023.
Y. Li, T. Ma, and H. Zhang. Algorithmic regularization in over-parameterized matrix sensing and neural networks with quadratic activations. In Conference on Learning Theory, pages 2-47. PMLR, 2018.
X. Liu, Tao, and 7. Pan. convergence analysis of nesterov's accelerated gradient method in training deep linear neural networks. Information Sciences, 612:898 925, 2022.
S. Lojasiewicz. A topological property of real analytic subsets. Coll. du CNRS, Les équations aux dérivées partielles, 117(87889)22 1963.
C. Ma, Y. Li, and Y. Chi. Beyond procrustes: Balancing freen gradient descent for asymmetric low-rank matrix sensing, IEEE Transactions on Signal Processing. 69:867-877, 2021.
H. Min, S. Tarmoun, R. Vidal, and Mallada. the explicit role of initialization on the convergence and implicit bias of overparametrrzed linear networks. In International Conference Machine Learning, pages 7760-7768. PMLR, 2021.
I. Necoara, Y. Nesterov, and F. Glineur. Linear convergence of first order methods for non-strongly convex optimization. Mathematical Programming. 175:69 107, 2019.
A. S. Nemirovski and D. B. Yudin. Problem complexity and method efficiency in optimization. Wiley-Interscience, 1983.
Y. Nesterov. Introductory lectures convex optimization: A basic course, volume 87. Springer Science & Business Media, 2013.
D. Park, A. Kyrillidis, C. Carmanis, and S. Sanghavi. Non-square matrix sensing without spurious local minima via the burer-monteiro approach. Artificial Intelligence and Statistics, pages 65-74. PMLR, 2017.

---

B. T. Polyak. Some methods of speeding up the convergence of iteration methods. USSR Computa- tional Mathematics and Mathematical Physics, 4(5):1-17, 1964.
M. Rudelson and R. Vershynin. Smallest singular value of random rectangular matrix. Communica- tions on Pure and Applied Mathematics, 62(12):1707-1133, 2009.
D. Stöger and M. 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-2388 2021.
T. Tong, C. Ma, and Y. Chi. Accelerating ill-conditioned low-rank matrix estimation via scaled gradient descent. Journal of Machine Learning Research, 22(150): 2021a.
Tong. Ma, and Y. Chi. Low-rank matrix recovery with scaled subgradient methods: Fast and robust convergence without the condition number. IEEE Transactions on Signal Processing, 69: 2396-24099 2021b.
S. Tu, R. Boczar, M. Simchowitz, M. Soltanolkotabi, and B. Recht. Low-rank solutions of linear matrix equations via procrustes flow. International Conference on Machine Learning, pages 964-973. PMLR, 2016.
R. Vershynin. Introduction the non-asymptotic analysis of random matrices. arXiv preprint arXiv: 2010.
K. Wang, C.-H. Lin, and J. D. Abernethy, A modular analysis of provable acceleration via polyak's momentum: Training wide relu network and a deep linear network. In International Conference on Machine Learning, pages 10816-10827 PMLR, 2021.
Y. Wang, M. Chen, T. Zhao, and M. Tao. Large learning rate tames homogeneity: Convergence and balancing effect. International Conference on Learning Representations, 2022.
Y. Wang, Z. Xu, T. Zhao, and M. Tao. Good regularity creates large learning rate implicit biases: edge of stability, balancing, and catapult. arXiv preprint arXiv:2310. 10.77777,, 2023.
R. Ward and T. Kolda. Convergence of alternating gradient descent for matrix factorization. Advances in Neural Information Processing Systems, 1-22369-223333 2023.
X. Xu, Y. Shen, Y. Chi, and C. Ma. The power of preconditioning in overparameterized low-rank matrix sensing. In International Conference on Machine Learning, pages 3861 1-38654. PMLR, 2023.
T. Ye and S. S. Du. Global convergence of gradient descent for asymmetric low-rank matrix factorization. Advances in Neural Information Processing Systems, 144:1429-1439 2021.
Yue, C. Fang, and Lin. On the lower bound of minimizing polyak-tojasien functions. In Conference on Learning Theory, pages 2948-2968 PMLR, 2023.
G. Zhang, S. Fattahi, and R. Zhang. Preconditioned gradient descent for overparameterized nonconvex burer-montein factorization with global optimality certification. Journal of Machine Learning Research, 24(163):1 55, 2023.
H. Zhang, Y. Bi, and J. Lavaci. General low-rank matrix optimization: Geometric analysis and sharper bounds. Advances Neural Information Processing Systems, 34:27369-27380, 2021.
D. Zhou, Y. Cao, and Q Gu. Accelerated factored gradient descent for low-rank matrix factorization. In International Conference on Artificial Intelligence and Statistics, pages 4430 4430-4440. PMLR. 2020.
12

---

A Singular Value Bounds
A.1 Singular Value Bounds for Random Matrix
Proposition (Rudelson and Vershynin (2009). Let A be an N x n random matrix, N 2 n,, whose elements i..dd zero mean sub-Gaussian random variables with unit variance. Then for 0, have
(A) S <T(VN- -ANN-Vn-T Vn S (c1T) + where C1, C2 0 depend (polynomially) only the Sabb-Gassian moment.
Proposition (Vershynin 2010). Let be an N x n random matrix, N 2 n, whose elements are i.idd zero mean Gaussian random variables with unit variance. Then for 2 0, we have
P(oi VN + Vn + 5e
A.2 Proof of Proposition 1
Proof of Proposition ! Singular value decompose as A UEVT, then X. cUEV Φ. Since VTV I, the columns of V + E R are independent Gaussian vectors with distribution N(0, a VV =N(0, 2 I,). By Proposition
Appendix A we have
P
V D
vr-1)
--(-r++1) - o2d
Vd
for some universal constants C1 and and any 2 0. On the other hand, by Proposition S Appendix A
we have
vd+ V Vs
P
(((TV
S
Vd
Plugging in s = d and applying the union bound yield
r(vd
Vr <o 4) <oi(V
2vd+ vrr 2 21-5,
P
Vd
vd
where 5 3e min((d-++1) lox + 22 The proposition follows immediately from the fact that
c. c. ()o S o, (Xo) S の (Xo) S Sc-oi(V ())1(AA)
B
Missing Proofs for GD
B.1 Auxiliary Lemma
Lemma 6. Suppose {arh:2 and (be F12 are two non-negative sequences satisfying
a++1 p ae be, b, l¹ co.
where 0 S p < 1, co 2 0, then the following holds for all 2 0:
Co
a S 00
40
+
Proof. The inequality holds trivially for = 0. For 2 0. have
ac+1 = 00 00
0
Co
g++1 1+1
00 +
0 Co
01+1,
00
Co
f
13

---

B.2 Proof of Proposition 2
Proof of Proposition According to
we have
R = X L-1 A
= (X; P.) -
R 7 (R, Y.Y, X,X, R.) P.Q.
Applying vectorization on both sides yields
r++1 = r2 rH + (r, r(-1) + vcc(P...)
[I nH vcc (c P.Q.).
Hence we have the result.
B.3 Proof of Lemma
Proof of Lemma 7 By Proposition I the symmetric matrix H, I, 30 (X,X,) has positive eigenvalues, and the eigensubspace of these positive eigenvalues is
H col Xo) (A).
According to the GD update 33,
col(X,+1) co,(X,) + col(X, Y, col(AY,) S col(X,) + col(A), hence by induction conclude col(X,) S col A) for all 2 0. As result, we have r; = vec(X, A) H.
For f,, notice that
(o + X,X, R,) col(R.) + col(X,) col(A)
and
col coI(P,Q..)
X1) - -ox
col(A),
thus have
f. = 1) voc YoYo +X,Y R, - R,Y,Y, - X,X, Ro e 7.
B.4 Proof of Lemma 2
Proof of Lemma 2 Since Im commutes with symmetric matrix Ho, we can simultaneously diago- nalize the two matrices and get
(To)) = - 17mm (Ho), Vi = 1,2,.... mn.
When 7 (0, 2), A GD) for = 1,2, ..... (m - -)nn Let {vr)men
I be orthonormal eigenvec-
tors, v, corresponds to X₂ (TGD). then we have Span( (m (m- r)m)
(oo(H) T H. Consequently, Σ (v. v. Vi
mn
| = TGD
mi
Σ
(v.v.) X?
iimm-rjnt1
max (m-r)n+tsiSmm
(TpD)
||]|
max (
TTT,|,11
mul ||v||
where the second identity is from result.
H ker (Hp). Plugging in the step size yields the second
14

---

B.5 Proof of Lemma 3
Proof of Lemma For all s S t, by assumption we have
P IP.Ilr - R Yslle
5/ [Rallp
$ Yoll + +|Y,, - -Yoll) R
<nI + [Y, Yolle) [R,le
$ Ylll + C2) | IF
/ + C2) ||ro|l-
Similarly, we have
1Q < < Xool + C2)C,0 |roll-
Combining the two bounds yields
|/ve((. P. Q. 11p S P. QQl1p S Cz0 1ro13
where C3- = 1/ CP + C2) C2).
For the second part, we have
[| H. r.
RY.Yo - -Y,Y,) + (X,X, - x,X_ RR 1F
R,,Yo - -Y,Y, 0|p + (X,X - x,X_ RR
< YoYo Y.Y. |R. Xx,X, -X,X! RR,
(oll +|,,, -Yolpp) Y YollF |RilI
+ Xool + +XX,- x [X, - Xo IF |Rell
$ X(|Xoll + YYol + C2)C2 R.llr
S 0 ||roll
where C4 = 27y(1 Xxol + Yool C2)
Finally, when 6 holds, we have
Yoll + C2)C
X Xolle
|
|rool| S Cz.
1-0
==0
Similarly, we have YY+1 - Yollp S C²-
B.6 Proof of Theorem I
Proof of Theorem
7 Let Ci to C4 be constants defined in Lemma 3 Define p
レー 0 = 4.
Lt# we have
a: C₁ [rel], and by C1 [|E for t 0. By Proposition 2 and lemmas and 2
0,+1 E p ag + b
for all 2 0. remains to show that b. S 0º cn- By initialization p(L-p)
ag = C1 ||ro|| = = | IF
bo 0. Let C
ut u(L+tupp and C2 PVL where p 3[[A||
1). Plugging 2
241.
L+
|xo| VI and YYol = 0 into C3 and C4 yields
p
2pp²
C3
C4
A F L(1 +p)
A
Let
co CC ||ol| + C4) |roll,
then we can show the following relations:
ag 0 8-p
Co
< C|
C 1.
(15)
p
15

---

Indeed, by Proposition
1 with probability at least 1 5, our choice of e guarantees
144 cond (Xo) ||A 144L2 ||
1
(cond 2 (Xa) - PLL - 14)
(16)
Our goal is to show
L(++ MLT. 11)
Ci Ip Ci +C))
S |AlFF
Go
which is equivalent to
| + (L(1T)) + +20
up3
L(L+ p))
p + p)p 2L(1 +
L -
The above inequality holds when:
A S nL + u)
(17)
67 +
1²
<
(18)
I, T- P 6T.
2pL 1
(19)
6T(1 p)
Let p
p(L-p) 242"
then we have p pI. p and
n²
p
L 1b
L 1
2412
6L
2pL
pb
<
L p
12L
6L(1
p)
thus 18 and 19 hold. Finally,
17 holds in view of (16)
u(L + p)P
2
up
LL p))
2 ||
6L
6
144L2
Combining the results proves the 15
Now we can proceed with the induction in Lemma 3
Firstly, ||rol S C1 ||rall as C1 2 by 15).
and [X,- Xoolp Y) YollE 0 S C2. Suppose the induction conditions in Lemmal 2 holds
for s < 6, then we have
6, = C1 ||
< CC ||rol| + C₂0" ||rol]) S co 0"
Consequently, by Lemma 6 and 15) we have
0+41 S 0++1_
00 +
Cu
CC. 0++1 |
thus ||r+all || S 0,0++1 ||o|]. Moreover, by our construction C₁ and C2, 6 always holds, thus we also have | Xollr < C2 and ||++ Yollp < C2. All conditions for the ( + 1 step are satisfied, hence the proof is completed by induction. Plugging in C₁ and the choice of yields the results.
D
16

---

C Missing Proofs for NAG
C.1 Proof of Proposition 3
Proof of Proposition
3
According to the NAG update rule, we have
R 1 Y 141 A
= =X, + P.) + Q2) - -
RR + P,Y, + +,Q +PQQ
R. + (8(X, - -X,-) -1) X B) 1 X, (8(7 -Y(-) 3) 3)n R2 B Bx- +.Q.
R. - -(1+ 8)n (R,Y,Y, + +X, R + +XYYY, - X(-IX,-1)
+ 8n (R.-1X,-11 + +X,
+ x - ; + X, x - (X, + +X,Y
-
Bn (R--Y--- + +X,X, R - R,-1 Y X,-1X ( +PQ.
R. - -1+ (RYY,
X,X, R.) ( + + - -R-1))
+ B1 (R--I Y + X, X R,
R.-1) + -I,,
3(X,Y, + X - Y, x,Y,)
+ +n (Ri-IY--1Y, + X,X, R R,- Y, 1-I
X R +P.Q7
Applying vectorization on both sides yields
F(+1 r, (1 + H + B(r, rt-1) + H1
+ veo X, Y - - x,,, x,YLT)
+ Bn (o + X,X, R - R+ Y,-1 -
Rt-1) R. vec(P.
-1 3+ THH, )r; - 3[mm 10 + 3 + 6..
Hence we have
Te+1
(1 (1
(I - HoO) mn
-8 -HH))
It rz-1
+ E2
Ft
C.2 Proof of Lemma 4
Proof of Lemma 4 Suppose À is an eigenvalue of TNAG, then we have
det TNAG Al2ma) det((B + 2 - (1+
Lmn + (n B) - Ho)
Since Ho is symmetric, it can be simultancously diagonalized with I, hence the above equation becomes
- (1 + 3) (1))))()))))))) ( =0
for some S i is mn. Solving the equation yields
(-43 (1+ A (1 3) ([++)) - (1+ (Ho)))
For i > nr, (Ho) = 0, hence \ = 1 or X = B. The corresponding eigen subspaces are
H4 = {(u v T == v E kor(H,)) }
Hg = {(uJ, v TT -u fv E kcr (Ho))
The dimensions are dim(Hi) = dim (m - easy to verify that whenever 0 < 3 < 1,
H1 @ H1 = ker(Ho) x ker(Ho)
The complement space of H, + H. corresponds to the eigen subspace for non-trivial eigenvalues. By checking the dimension and orthogonality, have
(H1 ① Hz) = 7 x H.
17

---

For i S nr, the subspace is H. x H. and the contraction condition requires
2(1+ 5)
2(1 + ()
0 < 7
(1 + (X)
(1+ 28)
By checking the monotonicity of [A] with respect to (Ho) E [1 1L,1 mpp. we have
||| max
(1 () mpe) + ((1 7/1 (-43 (1 3) (1+3)(1-771) mn1i
1 ((1 + ()(1 nT. n1- 43 (1+ (1.))
2
we choose step size yl + momentum 3
-I-VE VI+VA
then we have | s 11 - -1
C.3 Proof of Lemma
Proof of Lemma
5
According Lemma
&, = S7 + 4,
5: = Q, + 3 vec(n - + +
R +
11))
4 = (1 + (H H.)r, - (Ho 11-1)r(-1-
We first bound ||P||p and || |QrIp For every 0 S S 1, we have
Rg Yollp
$ ||Y [Ralle
$ Yll + +|JY, =-|Y,,-Ye Yoll) |Rilr
-Xs-Yol.
< Ylloll +||Y, -Yolp) |Ral|
$ Y|ll + C2) |R,lIF
Similarly,
R x || s (1Xxl + C2) |R.
By assumption, we have
R lr S
rs
s c/
rz-1
r-1
As result, the momentum terms can be bounded:
I = RR RRYY Y. +
R, Y,
s=1
<n Y 11 +
g1-0+1 R2 Y.
<n||ooll + C2)
|Rille Σ gt-s+1 1+1 | 11r
( ro
nnC(11 + Cc2)
0'+ Σ
g 00
[-1
s T + +c2
g¹
ro
(20)
0
|--
and
|Qul S ( (2)
gt
(
Ioo
(21)
1-
r--
where we use 3 S 6² < 9 in the last steps.
18

---

Next, we bound ||s.]1- Using the triangle inequality, we get
Icllll - P.Q. 1r +
I P R,-1 Pa-1
For the first term, we have
X + (2) Yol + +2)
rb |
2
I. pl < [P 1Qll <
0
(1-
r--1
For the second term, we have
3 X 7 R + P 1 Q.-111
<3 (1 ( Ir (1 1-1 Q X - P -
P 1l [Qr-1lp))
( + C2) Yoll + C2) 20 gzt
2
(1 0)2
r--1
As result, we have
||
||c.11 s Cz
Fo
rr-1
where C33 (I +CD0Y (4) (1-0)2
We then show upper bound for |..l Using the triangle inequality, we get
||||| s (1 + Il He)rell Bn (Ho H. H.-1)r-
(22)
For any S L, have
[Ho r. R, Yo - + +
- X,X, RR F
RY, Yo -Y,Y, )|p + (X,X, X,X! R
$ NoYO Y.Y. [R. + X x,xX
||,
$ Yoll + +|, - -Yolp) I|, - Yollo RRll
+ (2||Xol + +|X, -Xollp) |X, - Xolla |Rull
s 2(|Xol + Yool + +22)C2 Rallr
s 2(|xol + Yoll + +02)01220*
(1-)
ro
Plugging it into 22 yields
< 2(| + + + + 81101111 /
ru [mm)
dell
(--1
I C20'
where C4 = 2ny(1 X + Yoll +1)))
Finally, given and 220). we have
X Xolls - Σ Pall S
( + C2)
ro (1m)
< C2n
0)
==0
where the last inequality is from our assumption on C2- Similarly, by
21 we have
Y Yoll < 1Qullr < n/ X + C2)
Tu
< C2.
(1 - 8)2
r-1
0
19

---

C.4 Proof of Theorem
Proof of Theorem
By initialization, we have ||roll --rr- = -|All Let C₁ C₁ be constants
defined in Lemma
Define p V
y 0
2VL' Ci (| , and b, C1 ||&.1
y/
for t 2 0. It is easy to verify that ,3 S f2 < < and < 0 < 1. By Proposition and lemmas
and 4 we have
0++1 S p ai + bt
for all 2 It remains show that S 0 co. For the initial step, do v2C | bo 0. Let
C1 4v | (1+bp) and C2 = PVL where p
pp
/
I 144 < 1, then we have
144VI
u2 + VE,
13 -3
C3 8 || (1+p)
C4
2/2||All
Let co = V2C((V2C, || + C.) || pp. then we can show the following relations:
0g p-p 22 || and C1 2 1.
(23)
Indeed, by Proposition with probability least 1 6, our choice of guarantees
1 = (X,) r²(vd vr - (A)
4v | (1+
(24)
d
p
thus C1 2 1. Here, we use the bound show
p S 144
1
verify the numerical constant. It remains to
co
S 220 |
ag + p-p
which is equivalent
p3 VuL(2 + V
p² VDL VE)
|| +
Pp 4v2(1 + p)
2v2(1 p)
V2
Since we set
V/ < 1, each one of the three terms on the left hand side is upper bounded 144VE hence the inequality holds. The relations (33 guarantee the induction conditions in
by 12 [+p)
Lemma thus we have
(
|r++ll S (2
||
g++1 ||A|F
64 | Ip cond Xx)
where the last inequality uses p 0 and Proposition]
1
D Missing Proofs for NAG in Section
Let F; vec(Re), then have the following dynamics.
Lemma 7. LetP, X X, and Q YY+1-Y YY, denote the momentum. Let X,Y, D-L denote the residual, R, = X,Y. DD LD denote the projected residual, F, voc(R.) R Then NAG has the following dynamics:
Fe+1 Fí
(1 (1++ B)
Ho)
-3(Im - -(Ho))
(
Fr io-1
52 +
0
(25)
Inn
where
H. (DD Y.Y, +DD+DDD & (X,X.),
&, C, + 4n
C. vec (P Q DD ) 3 vec (P. DT
+ By veol RR Y Q __
P P R DD
= (1 B) H,
rr
3n H
20

---

Proof of Lemma 7 We denote R², = D L as the residual, R. R2D as the projected
residual, then the NAG update for T0p can be written as
Xx+1 Y(+1)
(1 (1x ( -1, nR X(-1) (
(26)
(1 3) Xx) 3(Y - (
The result follows from (26) by direct computation.
Lemma Let C g denote the linear subspace containing all eigenvectors of Hg = (DD (X with positive eigenvalues. If cool(X)) col(L) and Yo 0, then we have
H = cD & L) and (1,,5,)120 C H.
where Ho, F. and &, are defined in Lemma
Proof. By Theorem 4.2.15 in Hor and Johnson 1994 we have the following eigenvalue decompo- sition for Kronecker product:
Ho (UD @ (E) ) @ U
where D = Vn and X, Un are singular value decompositions of D and Xo- Therefore, we have
H = =o D 8 Un) = cD @ Xx) col 2 L).
In partieular, the eigenvalues (not ordered) are
A (Ho) X, (DD (X, of (D)o i [n]. [m],
where (Xo) 0 for 1 S j S (x(,) = 0 for r + S S d. By Assumption thus have
L = AD,
vec(LDT) = vee vec (D & L)ly E col & L) H.
Meanwhile,
Y,,,, DDT) = X.) vecl (o,(Y col(D & X,) C col D @ Xo) = H. thus have it H. Similarly, we have & H.
Lemma 9 (NAG contraction). If we choose step size 1) = F. and momentum 3 Vi- SI
where
VL+VI
=
Xx)
Amax (DDJ) ), ū (Xo) Amin (DDT), thenfor all (u, E H x H. H defined in
Lemma
NAG
u
Proof. Following the same line of proof for Lemma in Appendix C.2 and substituting the eigenval- ues in Lemma we obtain the result.
4
Lemma 10. Suppose 3 < 02 < <
If there exist some constants Ci and C2 such that for
F,
To
any S I, the NAG dynamics 7 yields
< 0
|X,
Xollr C2. and
Fe-1
F-
||Y, Yollf I C2, then we have
IIC.lI S C3
To P-
and
||4/|| < C2p'
(
To
for some constants C3 and C4 depending on C₁ and C2. Moreover, if Cr and C2 satisfy
(max(||Xolll | + C2)
To و-1
< (1 02
then we have
[X4+1 - Xollo S C22
|Y - Yollp 5 C2.
21

---

Proof of Lemma 10 Following the same line of proof for Lemma 5 in Appendix
C.3
we have
1
ro F-1
PPllp S Ci + C2) 1 1-
+2)
(27)
and
( Fo
|Qrl S x]Ci(||Xoll C2)
(28)
[--1
As result, we have
P.Q.
DD P.
x + Yol + CDD
0
To F-1
(1-
and
3
(n ..-1 Q + t R P. QTT,, DD
F
<BA 11 R || (1 11Q X
P
[Il) + PPPtilll 10-
v X Yoll + C2) 20) (DDT)
2
g2t
(1- 0)2
F-1
Combining the inequalities, we get
12
|| S Cz
Fo
F-1
where C33 = ( Yo
(1-8)²
Similarly, we have
( Fo
||+||| $ 2(| + YYol +G)GCA ((1 + B)n0' + B100-11
F-1
Fu F-1
< 02
where C4 = 21)(|| + |ool + 20)
Finally, by
27 we have
y + C2)
To C2.
X Xollp -
01 8)2
F-1
#=0
where the last inequality is from our assumption on C2. Similarly, by
28 we have
1/11( x + C2)
Fo
Y Yolle S
QQ 1p
C2.
(1 0)-
F-1
D.1 Proof of Theorem 3
Proof of Theorem 3 By initialization, we have ||Fol| = F = LD T
F. Let C₁ to C4 be
constants defined in Lemma
10 Define 1 L 0 = 2vI = Ci |R, R and
Va
VI
by = Ci |&&lll for 2 is easy to verify that 3 < 0 < 0 < and p < 0 < 1. By Lemmas
we have
G++1 S. b
22

---

for all 2 0. It remains to show that b, S 6' co. For the initial step, v2C1 LD
bo
0.
Let C1 4v2
Bp
and C2 = PVL where
v/
I 144 < 1, then we have
1p(+p)
144V i.
Tup
Tap
P
C3 ||LLD
2
C4
- V
p)
2 LLD
Let cu = V2C1 choice of constants, there hold
LD
+ Ca)
LD
I|m then we can show the following relations: Given
Ag
Co p-p
22?
|
and C1 2 1.
(29)
Indeed, by we have C 2 1. remains to show
a. p
V20
LD
which is equivalent
V jup'
pupp
LD
IF +
2v p)
2 +
v2
V
4
211
PP
By 111 and
VT < 1, each one of the three terms the left hand side is upper bounded by guarantees the induction conditions Lemma 10 thus
111V hence the inequality holds.
HP
12 2(1+(()
we have
4+1
1
Petill S V20, 0++1
LD
LD 1p
576 LD T
|F
2V
By Assumption
we have row(L) (L) E row (D) col(D)) T), thus we have
R |r X Ll|r
S _ (D)
(Xo)) (D)
(1- (1- 20, (Xo) Amax (DDT)
or (Xo) Amin (DD
576
D.2 Proof of Corollaries
Proof of Corollary ! By Proposition (X O d-cond(L)
7(d-r+1) with probability at least
where 5 = 3e" (d-r(()++1 log aj (ad. Plugging it in Theorem yields the result.
L
Proof of Corvllary
After orthonormalization, we have cond(X,, = The result follows immedi-
ately from Theorem
Proof of Corollary
3
By Propositions and 5 cond (Xo) = =0 F(d-m+++ m with probability at least
1 8, where
3e
min((d-mm log c2d, Plugging it in Theorem yields the result.
E Additional Experiments
This section provides additional experiments. Firstly, we investigate larger-sized problems by setting (m, n.) = (1200, 1000) for matrix factorization and (m, n, N) (500, 400, 600) for linear neural networks. We keep other settings the same as for Figure 2 and compare the performances of GD and NAG. The results are provided in Figure 4 As illustrated, the conclusion that NAG performs better than GD and overparameterizztion accelerates convergence remains valid for large matrices.
23

---

matrix factorization
linear network
G0,dw5
NAG,6w5
10-10
G0,6-20
NAG,d=20
10-15
00,0=80
10-20
NAC,6+80
10-2
100
200
100
200
iteration
iteratioon
Figure 4: GD and NAG on large matrices exhibit similar behavior small matrices in Figure 2 Left: matrix factorization with m 1200 and 1000. Right: linear neural networks with m 500, n 100, 600.
matrix factorization
linear network
Mf.c=10.GD
MF.c=10,NAG
10
MF.c=50.GD
MF,C=50,NAG
10:4
MF.c=250.CD
MF,0=25ONAG
10-11
LNN.C=10,GD
LANC=110,NG
UNN,c=50,GD
10-2
LNN.C=30.MMG
LNN,C=250.60
10-20
LNN.c=250,N0 NAG
100
200
100
200
Reration
Iteration
Figure 5: GD and NAG with different values of c. When e is sufficiently large, changing its value would not significantly affect the convergence rate.
matrix factorization
linear network
F-4
MF.22m0.02.co
10a
MF.c2=0.2.6U
MF,
MF,22-0.2.NAG
10-7
MF.2-2.NAG
LNN.2200.02.0
LNN.22-0.02,MM NAG
LNN.2-02,CD
10-11
LNN.2-2,60
10-2
LNNG2=22NAG
100 keration
200
100 Iteration
Figure 6: GD and NAG with initialization Xo cı 1 Yo
C2 C1 50.
The initial loss (intercept)
increases as eg increases within a range, while the convergence rate (slope) does not change significantly.
Secondly, we conduct additional experiments on GD and NAG with different values of e and plot the results Figure We set = 20, while other settings remain the same as Figure As illustrated, when is sufficiently large, further increasing has little effect on the convergence rate, which is consistent with our theory.
We also investigate general unbalanced initialization X, A E Ruxd Yo = c2 2 Bx where ( 1l.s (O, L/d) and [$2].,s *N 1/n). We set d 20, while other settings remain the same as in Figure 2 We keep C1 = 50 and set different values of c2. The results are plotted in Figure 0 As illustrated, changing C2 within a range only results in different initial losses (intercept), while the convergence rates (slope) are not significantly affected. This supports our claim in Remark
NeurIPS Paper Checklist
1. Claims
24

---

Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
The main claims made in the abstract and introduction (Section I accurately reflect the paper's contributions and scope.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: We state all settings and assumptions required for our results and discuss
limitations (e.g. exact rank-r A, Yo = 0, etc.) in Sections and 6
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point any strong assumptions and how robust the results are violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and a complete (and correct) proof?
Answer: [Yes]
25

---

Justification: We clearly state all sets of assumptions (Sections) 1 and 4 and proof sketches in the main part of the paper (Section B), and provide complete and verified proof in the appendix (Appendix A to D). Theorems and Lemmas are properly referenced.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We state all main configurations of our experiments in Section S that allows one to reproduce our results.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
26

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We provide anonymized code in the zip file for experiments in Section 5 as supplement materials.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips... cc/
oolicy) for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
//nips.ccpublle wwwppppgpuuiiieeeep /otic///uuiee//oeeuuuiiiiiii SooodeSubiissie ssiiiiolcccy for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We specify all important experiment details in Section 5
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer:
[No]
Justification:
Our experiments do not require error bars.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi-
dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for
example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
27

---

The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out of range (c.g. negative emror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [No]
Justification: Our experiments have no special requirements on compute resources.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics oica
Answer: [Yes]
Justification:
The research conducted in the paper conform with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is no socictal impact of the work performed.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
28

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
29

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
30


Reviews:
[{"review_id": "DAwyPAbHtz", "reviewer": "Reviewer_SNTq", "summary": "In this papers the authors analyze the convergence of  Nesterov Accelerated Gradient algorithm for a) rectangular matrix factorisation and b) linear neural networks. By using imbalanced initialisation,  the authors come up with linear rates of convergence impoving upon state-of-the-art regarding dependence of the rates condition numbers of sought matrices.", "questions": "- In [1] the authors provided rates of convergence of gradient flows in the imbalance initialisation regime. Could these results provide some insights on how to generalise the derived rate for different amount imbalance of imbalance?\n- Could the authors provide some insights on whether the theoretical results on linear neural network  could be extended to non-linear and possibly non-smooth activation functions?\n\nMinor: \nEq. under line 132: Should $x_t$  be replaced by $z_t$ (??", "limitations": "Yes", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The paper is well written and easy-to-follow. \n- The analysis of convergence of NAG on rectangular matrix factorisation and linear neural networks is an interesting topic of research.\n- The authors improved upon state-of-the-art results using novel technical approaches and elegant proof techniques.", "weaknesses": "- The authors didn't mention relevant works studying imbalance effect on the similar  problems e.g.  [1].\n- The results address the linear neural network case but it's not obvious how the analysis could be extended to account for non-linearities or non-smooth activation functions. \n\n[1] Min, Hancheng, et al. \"On the explicit role of initialization on the convergence and implicit bias of overparametrized linear networks.\" International Conference on Machine Learning. PMLR, 2021.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your positive feedback and constructive comments. Our responses to each of the comments are listed below. \n\n> W1\\& Q1: The authors didn't mention relevant works studying imbalance effect on the similar problems e.g. [1]. In [1] the authors provided rates of convergence of gradient flows in the imbalance initialisation regime. Could these results provide some insights on how to generalise the derived rate for different amount imbalance of imbalance?\n\nWe thank the reviewer for pointing out the related work, and we will cite [1] and discuss it in the next version. \nIn particular, our settings and proof techniques differ from [1]. Consequently, their results cannot directly translate into our case. \n\n1. We consider GD and NAG with step size $O(1/L)$, while [1] considers GF with infinitesimal step size. Without carefully characterizing discretization error, the result in [1] for GF cannot be applied to GD. \n\n2. In our proof, the imbalance initialization guarantees the induction steps to be valid. The amount of imbalance will affect the constant factors but will not affect the convergence rate $(1-\\frac{\\mu}{L})^t$ (or $(1-\\sqrt{\\frac{\\mu}{L}})^t$). To be more explicit, suppose we initialize $X_0=c_1A\\Phi_1\\in\\mathbb{R}^{m\\times d}$, $Y_0=c_2\\Phi_2\\in\\mathbb{R}^{n\\times d}$, then by replacing $H_0$ in Proposition 2 with $H_0^\\prime=I\\otimes (X_0X_0^\\top)$, we can generalize the proof in lines 814-815 and 821-832. The induction requires a sufficiently large $c_1$ and a relatively small $c_2\\leq O(c_1)$. Meanwhile, by Proposition 4.3.2 in [2], we have $$\\frac{1}{1-O(c_1c_2)}|A_0|_F\\leq|R_0|_F\\leq (1+O(c_1c_2))|A_0|_F$$ with high probability. Therefore, when $c_1$ is fixed, a smaller $c_2$ yields a smaller initial loss, resulting in a smaller constant factor. However, the convergence rate remains the same, as it depends on the extreme non-zero eigenvalues of $H_0^\\prime$, i.e., $\\mu$ and $L$, which only relates to $c_1$ but not $c_2$. We conduct additional experiments on GD/NAG with different values of $c_2$, and the numerical results support our claim. Please find the experiment details and results in \"Author Rebuttal\" and Figure 6 in the PDF file. \n\n> W2\\& Q2: The results address the linear neural network case but it's not obvious how the analysis could be extended to account for non-linearities or non-smooth activation functions. Could the authors provide some insights on whether the theoretical results on linear neural network could be extended to non-linear and possibly non-smooth activation functions?\n\n\nExtending our results to neural networks with non-linear (and possibly non-smooth) activations is an interesting topic that we want to investigate in the future. \nWhile non-linearity complicates the analysis, we believe some of our techniques still apply. \nSuppose we apply non-linear activations $\\sigma(\\cdot)$ and the problem becomes $\\min_{X,Y}|L-X\\sigma(Y^\\top D)|_F^2$. In our analysis, one of the key steps is to show that the residual and error terms are in the contraction subspace of the dynamics. \nSince the second layer is linear, by sketching initialization $X_0=cL\\Phi$ we can still get $X_0$ that shares the same column space with $L$. By checking the dynamics of GD/NAG, we can verify that this space contains the column space of residuals and errors of all later iterations. \nHowever, due to the non-linear activation, the analysis of the linear part of the system and error terms becomes complicated. \nIt requires further effort to verify whether our results can successfully generalize to the non-linear activation setting. \n\n> Q3: Eq. under line 132: Should $x_t$ be replaced by $z_t$?\n\nThank you for pointing this out. This is indeed a typo and we will replace $x_t$ with $z_t$ in the next version. \n\n[1] Min, Hancheng, et al. \"On the explicit role of initialization on the convergence and implicit bias of overparametrized linear networks.\" International Conference on Machine Learning. PMLR, 2021.\n\n[2] Ward, Rachel, and Tamara Kolda. \"Convergence of alternating gradient descent for matrix factorization.\" Advances in Neural Information Processing Systems 36 (2023): 22369-22382.", "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": "", "extra_scores": {}}, {"review_id": "K6vd08yYh4", "reviewer": "Reviewer_t3Co", "summary": "The paper calculates convergence rates of the gradient descent and the Nesterov's accelerated gradient descent algorithms for factorization of rectangular matrices- a nonconvex optimization problem. Their analysis is for algorithms when the factor matrices are initialized as follows:  one matrix is initialized as the original matrix multiplied with Gaussian random matrix with appropriate scaling and the other is a zero matrix. They show convergence rates with quadratic dependence on condition number of the data matrix for GD and linear dependence for NAG. They also extend their analysis to linear neural networks and back their theoretical findings with empirical results.", "questions": "See Weaknesses", "limitations": "See Weaknesses", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1) Gradient descent algorithm and its variants are used almost everywhere in machine learning. Deep neural networks have made nonconvex optimization also very frequent in ML and matrix factorization is a basic problem. As such a work providing theoretical guarantees for the problem is very relevant.\n\n2) Although the paper is difficult to read, it is structured in a very nice manner so that a reader can follow the high-level ideas quite clearly. The related works and the placement of this work among existing works is discussed very clearly.\n\n3) I could not check the proofs in detail, but enough intuition, proof sketch and moderate level of details are provided in the main paper itself. The ideas appear solid and sound.", "weaknesses": "1) The experimentation is done on very small matrices. In practice much larger rectangular matrices are often encountered. It would give more insights if the experiments were also performed with moderate and large size matrices.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your positive feedback and constructive comments. \n\n> W1: The experimentation is done on very small matrices. In practice much larger rectangular matrices are often encountered. It would give more insights if the experiments were also performed with moderate and large size matrices.\n\nThank you for your suggestion. We add additional experiments on large-scale matrices. In particular, we set $(m,n)=(1200,1000)$ for matrix factorization and $(m,n,N)=(500,400,600)$ for linear neural networks in the additional experiment. We compare the performances of GD and NAG while keeping other settings the same as in Figure 2 in the paper. The results are plotted in Figure 4 in the PDF file attached to \"Author Rebuttal\". As illustrated in Figure 4, our conclusion in the paper that (1) NAG performs better than GD and (2) overparameterization accelerates convergence remains valid for large matrices.", "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": "", "extra_scores": {}}, {"review_id": "IrxfWGzDVt", "reviewer": "Reviewer_tURQ", "summary": "This paper considers the convergence of the first-order optimization method, which includes the gradient descent and the nesterov's acccelerated gradient \nfor the marix factorization and the linear neural network. \n\nIn Section 2.1, they analyze the gradient descent algorithm on the matrix factorization (c.f. Thm. 1). \nIn Section 2.2, they analyze the NAG (c.f. Thm 2).  Section 3 illustrates the proof strategy. \nSection 4 extends the analysis to the linear neural network (c.f. Thm. 3) and Section 5 presents the numerical experiments.", "questions": "1. Why the convergence rate is independent of $\\|A\\|_F$?\n2. Can you explain the line 807? Why the eigenvalues of $\\lambda_i(T_{GD})$ ($1\\leq i \\leq (m-r)n$ can be ignored? The previous line suggest these eigenvalues are one.", "limitations": "NA", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "This paper is generally well-written and is quite easy to follow. Also, the analysis seems to be valid.", "weaknesses": "The major concern is the potential impact of this paper.  Generally speaking, this paper studies a well-studied problem with quite standard technique. \n\nAlso, there are some small typos that are quite annoying. For example, the $\\|A\\|_F$  in Thm. 1and Thm. 2 can cancel out. Thm 2 (line 14), the GD should be NAG. Please do another round of proof-reading.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time in reviewing the paper and helping us improve. \nOur responses to each point of the Weaknesses and Questions are listed below.\n\n> W1: The major concern is the potential impact of this paper. Generally speaking, this paper studies a well-studied problem with quite standard technique.\n\nImpact is a little subjective, but we hope the reviewer could consider the following regarding whether this is a well-studied problem and whether our technique is standard: \n\nQuantitative theoretical guarantee for the optimization of general nonconvex function without Lipschitz gradient, even after decades of remarkable progress, is still largely an open problem. We managed to do it for a specific type of problem, namely matrix factorization. It is still a nonconvex problem without Lipschitz gradient. Moreover, it carries a lot of insight for a better understanding of deep learning, as it is closely related to linear neural networks, which we also analyzed. Therefore, it is extensively studied, however *not well-studied* because many understandings are still lacking. \n\nTo illustrate this more precisely, consider [1] which is a very recent progress (NeurIPS'23): the motivation was to understand Gradient Descent (not gradient flow, which was easier) for this problem, but due to technical difficulty that was not accomplished; instead, the authors managed to work out a variant, namely Alternating Gradient Descent, and obtained convergence rate. Now, in our work, we not only work out Gradient Descent but also its momentum version, which is more complicated to analyze but beneficial, because we quantitatively prove that Nesterov's momentum indeed accelerates convergence. This requires *new analysis techniques* (as discussed in Remark 1) and rather precise (if not tight) error bounds, and we're glad it can work out.\n\n[1] Ward, Rachel, and Tamara Kolda. \"Convergence of alternating gradient descent for matrix factorization.\" Advances in Neural Information Processing Systems 36 (2023): 22369-22382.\n\n> W2: There are some small typos that are quite annoying.\n\nThank you very much for helping us catch them. \nAlthough we intentionally put one $|A|_F$ in the denominator of the prefactor so the other $|A|_F$ can align with the definition of relative error (lines 124 and 140), the expression indeed becomes more confusing. \nWe will cancel out $|A|_F$ in Theorem 1 and 2 and $|LD^\\top|$ in Theorem 3 to avoid confusion. \n\nThe GD on line 140 is indeed a typo. We will proofread and fix it along with other typos in the next version. \n\n> Q1: Why the convergence rate is independent of $|A|_F$?\n\nWhile the convergence rate does not explicitly depend on $|A|_F$, $|A|_F$ will still affect the convergence rate through $c$ defined in Eq. (2). Theorems 1 and 2 require $c^2\\geq\\underline{c}^2=O(|A|_F)$, and the results show $|R_t|_F$ depends on $c^2$. When we choose $c=\\underline{c}$, the bound will have an explicit dependence on $|A|_F$. When we choose $c>\\underline{c}$, $|A|_F$ is dominated by the factor $c^2$, hence it is implicitly contained in our results in lines 123-144 and 139-140. \n\nMoreover, when considering the iteration complexity, we adopt relative error as the metric, i.e., $|R_t|_F/|A|_F\\leq\\epsilon$. Therefore, the right-most $|A|_F$ in the line between 123-124 (and the line between 139-140) does not appear in the iteration complexity. \n\n> Q2: Can you explain the line 807? Why the eigenvalues of $\\lambda_i (T_{GD}) (1\\leq i\\leq (m-r)n)$ can be ignored?\n\nThanks for the opportunity to correct a critical misunderstanding. It is *not* because eigenvalues are ignored, but because $\\left<v,v_i\\right>=0$. By Lemma 1 (line 188), $\\mathcal{H}$ is the eigen subspace corresponding to positive eigenvalues of $H_0$, which is orthogonal to the kernel subspace of $H_0$. Through the derivation from line 804 to 807, we know that $\\{v_1,\\dots,v_{(m-r)n}\\}$ exactly spans the kernel subspace of $H_0$ (where $\\lambda_{mn-i}(H_0)=0$). Given the condition that $v\\in\\mathcal{H}$, we get $\\left<v,v_i\\right>=0$ for $i=1,\\dots,(m-r)n$, hence the first $(m-r)n$ terms vanish. \nThanks to the reviewer we realize this was under-explained, and will add an explanation about this in line 808 in the next version.", "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": "", "extra_scores": {}}, {"review_id": "6tdAooNN0l", "reviewer": "Reviewer_u7PK", "summary": "In this study, the authors established the convergence rate of the gradient descent and Nesterov's accelerated gradient descent methods for the asymmetric matrix factorization and the 2-layer linear network. The authors proved that an unbalanced initialization can lead to linear convergence of both methods, and the Nesterov's acceleration result in a faster convergence rate. Numerical experiments are implemented to support the theory.", "questions": "- I think the following two papers also discussed the asymmetric low-rank matrix optimization problem. It would be better if the authors could discuss them and the references therein:\n\n[1] Zhang, H., Bi, Y., & Lavaei, J. (2021). General low-rank matrix optimization: Geometric analysis and sharper bounds. Advances in Neural Information Processing Systems, 34, 27369-27380.\n\n[2] Bi, Y., Zhang, H., & Lavaei, J. (2022, June). Local and global linear convergence of general low-rank matrix recovery problems. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 36, No. 9, pp. 10129-10137).\n\n\n- Following the above comment, I wonder if the authors can briefly discuss the potential and challenges of extending the results to more general low-rank matrix optimization problems.\n\n- Lines 79-80: I am not sure why the method in [Stöger and Soltanolkotabi, 2021] is considered a preconditioned method.\n\n- Theorem 1: In my understanding, the value $\\|R_t\\|_F$ should be proportional to the scale of $A$. However, in the bound of $\\|R_t\\|_F$, the right hand-side grows with the size of $A$. Maybe there is a typo?\n\n- The above comment also applies to Theorem 2.\n\n- It would be better to mention in Theorems 1-2 that the bound $T$ is derived using the bound in Proposition 1?\n\n- Line 182: I think the shrinkage rate $\\theta \\in (0, \\rho]$?\n\n- I wonder if the authors can compare the performance of GD/NAG with different values of c?", "limitations": "See my comments in the Questions section.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper is clearly written and easy to follow in general. The results are novel and inspiring to audiences in the non-convex optimization field. I did not check the proofs in the appendix due to time limit, but the part in the main manuscript looks correct to me.", "weaknesses": "I do not see major weaknesses. The authors could consider discussing more related literature and include more intermediate steps in the main manuscript. Also, I think the authors can consider illustrating the effect of an unbalanced initialization in numerical experiments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your positive feedback and constructive comments. Our responses to each of the comments are listed below. \n\n> Q1: I think the following two papers also discussed the asymmetric low-rank matrix optimization problem.\n\nWe thank the reviewer for pointing out these related works, and we will cite [1] and [2] and discuss them in the next version. \n\n> Q2: I wonder if the authors can briefly discuss the potential and challenges of extending the results to more general low-rank matrix optimization problems.\n\nGeneralizing the results to the general low-rank matrix optimization problem $\\min_{X,Y}f(XY^\\top)$ is challenging. One of the challenges is the possible non-linearity of the gradient w.r.t. $X$. In our proof, a key step is to show the residual and the error terms in all iterations are in the contraction subspace of the dynamics, which requires the gradient of $f$ to preserve the column space of $X$. Unfortunately, such a property does not hold for general loss functions. \nNevertheless, generalization to neural networks with non-linear activations, $\\min_{X,Y}|L-X\\sigma(Y^\\top D)|_F^2$, will not have this issue, and we believe it is an interesting topic that is worth future investigation. \n\n> Q3: Lines 79-80: I am not sure why the method in [Stöger and Soltanolkotabi, 2021] is considered a preconditioned method.\n\nThank you for pointing out this misplacement. The method in [Stöger and Soltanolkotabi, 2021] is not a preconditioned one. We cite it to support the former claim \" Overparameterization may heavily slow down convergence\", as it shows $O(\\kappa^2\\log\\frac{1}{\\epsilon})$ for exact parameterization case and $O(\\kappa^6\\log\\frac{\\kappa}{\\epsilon})$ for overparameterization case. \nTo avoid confusion, we will move it before the comma in the next version. \n\n>  Q4 & 5: Theorem 1 & 2: In my understanding, the value $|R_t|_F$ should be proportional to the scale of $A$. However, in the bound of $|R_t|_F$, the right hand-side grows with the size of $A$. Maybe there is a typo? \n\nThere is no typo here. The bound on $|R_t|_F$ implicitly depends on $|A|_F$ through the choice of $c$. The Theorems require $c^2\\geq\\underline{c}^2=O(|A|_F)$, and the RHS grows with $c^2$, so $|R_t|_F$ implicitly depends on $|A|_F$. When $c$ is larger than $\\underline{c}$, $|A|_F$ is dominated by $c^2$ and our results still hold. When $c$ is too small, our proof does not work. \n\nMoreover, the RHS does not explicitly depend on the size of $A$. The size might affect the bound through $|A|_F$ and $\\sigma_i(A)$, but there is no explicit dependence on the dimensions $m$ and $n$. The bound only depends on the rank $r$ and the overparameterization $d$, both are not directly related to the size of A. \n\n> Q6: It would be better to mention in Theorems 1-2 that the bound $T$ is derived using the bound in Proposition 1\n\nThank you for the suggestion. We will mention the use of quantitative results in Proposition 1 in the next version. \n\n> Q7: Line 182: I think the shrinkage rate $\\theta\\in(0,\\rho]$?\n\nIt is not a typo, the error shrinkage rate $\\theta$ is larger than the \"ideal shrinkage rate\"  $\\rho$ given by the condition number of the linear part of the dynamics. Intuitively, the existence of nonlinear error terms will slow down convergence, so $|R_t|$ will shrink at a rate $\\theta$ slower than $\\rho$, namely $\\theta>\\rho$. Then by Lemma 3, all error terms can be controlled by sequences with shrinkage rate $\\theta$. The auxiliary Lemma 6 provided in Appendix B.1 then guarantees that the final residual $|R_t|_F$ is controlled by $O(\\theta^t)$. \n\n> Q8: I wonder if the authors can compare the performance of GD/NAG with different values of c.\n\nWe add additional experiments on GD and NAG with different values of $c$. The results are provided in Figure 5 in the PDF file in \"Author Rebuttal\". As illustrated, when $c$ is sufficiently large, increasing $c$ further has little effect on the convergence rate, which is consistent with our theory. \n\n[1] Zhang, H., Bi, Y., \\& Lavaei, J. (2021). General low-rank matrix optimization: Geometric analysis and sharper bounds. Advances in Neural Information Processing Systems, 34, 27369-27380.\n\n[2] Bi, Y., Zhang, H., \\& Lavaei, J. (2022, June). Local and global linear convergence of general low-rank matrix recovery problems. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 36, No. 9, pp. 10129-10137).", "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": "", "extra_scores": {}}]

Author rebuttal:
We thank all the reviewers for dedicating their time to reviewing our paper and providing valuable feedback.
In response to the comments involving the size of the matrices (by reviewer t3Co), the performance of GD/NAG with different values of $c$ (by reviewer u7PK), and the amount of imbalance (by reviewer SNTq), we conduct additional numerical experiments and show the results (Figures 4 to 6) in the attached PDF file. We discuss each of them below: 

> W1 by t3Co: The size of the matrices is small.

Our original submission uses $(m,n)=(100,80)$ for matrix factorization and $(m,n,N)=(100,80,120)$. 
In this rebuttal where we investigate larger-sized problems, we set $(m,n)=(1200,1000)$ for matrix factorization and $(m,n,N)=(500,400,600)$ for linear neural networks. We compare the performances of GD and NAG under the same setting as in Figure 2 with moderate/large matrices in these sizes. The results are provided in Figure 4. As illustrated, the conclusion that (1) NAG performs better than GD and (2) overparameterization accelerates convergence remains valid for large matrices. 

> Q8 by u7PK: The performance of GD/NAG with different values of $c$.

We conduct additional experiments on GD and NAG with different values of $c$ and plot the results in Figure 5. 
As illustrated, when $c$ is sufficiently large, increasing $c$ further has little effect on the convergence rate, which is consistent with our theory. 

> Q1 by SNTq: The effect of the amount of imbalance at initialization. 

We conduct additional experiments on GD and NAG with initialization $X_0=c_1A\Phi_1\in\mathbb{R}^{m\times d}$, $Y_0=c_2\Phi_2\in\mathbb{R}^{n\times d}$, where $[\Phi_1]\_{i,j}\sim{N}(0,1/d)$ and $[\Phi_2]_{i,j}\sim{N}(0,1/n)$. We keep $c_1=50$ and set different values of $c_2$. The results are plotted in Figure 6. As illustrated, changing $c_2$ within a range will not significantly affect the convergence rate (slope), but will change the initial loss (intercept). This result supports our claim in the individual response to reviewer SNTq. 

In the next version, we will add these results and discussions in an "Additional Experiments" section in the appendix. 
For responses to other comments, please refer to our responses to reviewers.

Meta-review: The paper studies the problem of factorization of rectangular matrices. The authors prove the convergence rate of gradient descent with quadratic dependence on the condition number of the data matrix, and the convergence rate of Nesterov's accelerated gradient descent with linear dependence on the condition number. They also extend their analysis to linear neural networks. Three reviewers are unanimously positive, and one review with borderline reject is short and less informative. I decide to accept the paper.
Decision: Accept (poster)