On the Crucial Role of Initialization for Matrix Factorization
Authors: Bingcong Li
Liang Zhang
Aryan Mokhtari
Niao He
Venue: ICLR 2025 Poster (2025)
Keywords: nonconvex optimization
initialization
quadratic rate
low rank adapter
lora
Primary area: optimization
TL;DR: We prove that a specific initialization can significantly improve the complexity bounds of ScaledGD for matrix factorization under a wide spectrum of settings, including quadratic convergence in cases where only linear rates were previously known.

Abstract: This work revisits the classical low-rank matrix factorization problem and unveils the critical role of initialization in shaping convergence rates for such nonconvex and nonsmooth optimization. We introduce Nystrom initialization, which significantly improves the global convergence of Scaled Gradient Descent (ScaledGD) in both symmetric and asymmetric matrix factorization tasks. Specifically, we prove that ScaledGD with Nystrom initialization achieves quadratic convergence in cases where only linear rates were previously known. Furthermore, we extend this initialization to low-rank adapters (LoRA) commonly used for finetuning foundation models. Our approach, NoRA, i.e., LoRA with Nystrom initialization, demonstrates superior performance across various downstream tasks and model scales, from 1B to 7B parameters, in large language and diffusion models.

Published as a conference paper at ICLR 2025
ON THE CRUCIAL ROLE OF INITIALIZATION FOR MATRIX FACTORIZATION
Bingcong Li', Liang Zhang', Aryan Mokhtari', Niao He' 'ETH Zurich, "The University of Texas at Austin (bingcong. 1i, liang. zhang, niac. he) inf winf.ee www.f.etz... ch mokhtari@aust in. utexas edu
ABSTRACT
This work revisits the classical low-rank matrix factorization problem and unveils the critical role of initialization in shaping convergence rates for such nonconvex and nonsmooth optimization. We introduce Nyström initialization, which signifi- cantly improves the global convergence of Scaled Gradient Descent (ScaledGD) in both symmetric and asymmetric matrix factorization tasks. Specifically, we prove that ScaledGD with Nyström initialization achieves quadratic convergence in cases where only linear rates were previously known. Furthermore, we extend this initialization to low-rank adapters (LoRA) commonly used for finetuning foundation models. Our approach, NoRA, i.e., LoRA with Nyström initialization, demonstrates superior performance across various downstream tasks and model scales, from IB to 7B parameters, in large language and diffusion models.
INTRODUCTION
Compared with learning rates and descent directions, initialization has been relatively overlooked aspect of optimization. In the widely studied smooth optimization literature (Nesterov, 2004; Ghadimi & Lan, 2013), long as suitable (small) learning rate is chosen, most of optimization algorithms such as GD provably converge to a stationary point at the same rate, regardless of initialization. This work goes beyond stationary points and highlights the crucial role of initialization for global optimality of Montr-oooteiro factorization (Burer & Monteiro, 2003) the same algorithm can exhibit markedly different behaviors, such as linear vs. quadratic convergence, depending on initialization.
We consider matrix factorization lems, minx ||XX A : and ii) asymmetric ones, minx,y |XYT A l.. While these classical problems can be handled via various approaches, they are notoriously challenging for optimization, since they are nonconvex, nonsmooth (albeit diffcrentiable). non-coeroe non-coercive (for asymmetric prob- (PL) condition (Chi et al., 2019). Let A Rmxx (or
canonical example, where the goal is to solve i) symmetric prob-
lems), and do not satisfy A E mm x for asymmetric (symmetric) problems, X E I Xr lation of rank(A) and r, can categorize matrix factorization into three setups: exact-pare paact-parmmetrzeed (rank(A A) r), over-parametrized (rank A)) <r), and under-paranne parametrized (rank (A) >>>>))) r).
and Y E R=*r, Building on the re-
The asymmetric problem ii) is thoroughly explored in the literature. For the exact- and over- parametrized cases, global convergence has been established for GD, Alternating GD (AltGD), and ScaledGD (Du al., 2018; Ye & Du, 2021; Ward & Kolda, 2023; Jía et al., 2023; Tong et al., 2021), where most of them admit a linear rate. Regarding under-paramettre global convergence of GD is established in (Du et al., 2018) the best of our knowledge. Common to above algorithms is the small initialization with X,, NO, <2) and Y, (00, (3) for some sufficiently small < and Cg. However, such initialization results in unfavorable performance both thcoretically and empirically, partly because of the need of escaping from saddle point (0,
settings, only asymptotic
This work proposes Nyström initialization to effectively bypass the aforementioned saddle point. More importantly, it significantly enhances the global convergence rates when applied on top of ScaledGD. In the exact- and over-parametrized settings, Nyström initialization boosts ScaledGD to converge at a quadratic rate (i.e.. (log (o)))) on symmetric problems and enables one-step convergence for asymmetric problems. For the more challenging case with under- parteerrratttiiiooonn we prove that with our Nyström initialization, ScaledGI converges at linear rate to the neighbor of

---

Published as a conference paper at ICLR 2025
Table 1: Comparison of complexity for global optimality for (a)symmetric matrix factorization. Here, EP, OP. and UP are abbreviations for exact-, over- and under- parametrization. The prescribed optimality error denoted e, and K is the condition number of A. Note that our bounds for UP depict the complexity to near optima. The "special" initialization in AltGD is still small
initialization, but with more careful designs that will be clear in Sec. 3.1. Works marked with * are for the closely related matrix sensing setting (hence the comparison may not be fair).
setting
alg.
ref.
init.
rate
GD
(Ye & Du, 2021)
small
O + nOt log(1/e))
AltGD
(Ward Kolda, 2023)
special
(oo(ee))/)))
EP
Asymmetric
ScaledGD
(Tong et al., 2021)
local
(log((1/c)
ScaledGD
Theorem
Nyström
O(1)
modified GD*
(Xiong al., 2024)
small
1x2 log(l/e))
OP
AltGI)
(Ward & Kolda, 2023)
special
(k Oo22 O(1)
ScaledGD
Theorem 6
Nyström
GD
(Du al., 2018)
small
asymptotic
UP
ScaledGD
Theorem
Nyström
O(1)
GD*
(Stöger & Soltanolkotabi, 2021)
small
O ( + x² log(1 (1e))
EP
Symmetric
ScaledGD
Theorem
Nyström
0 (153 + log log 1/c))
GD
(Stöger & Soltanolkotabi, 2021)
small
O + x3 log(k/e))
OP
ScaledGD-A*
(Xu al., 2023)
small
o (log* + log (1/e))
ScaledGD
Theorem
Nyström
O (163 + +log log (1/c)
UP
ScaledGD
Theorem
Nyström
O(1/e ((1/e-log(1)
global optimum symmetric problems, and then exhibits a sublinear rate to more fine-grained neighboring area. Overall, Nyström initialization enables us to improve existing rates in exact-, over-, and mnder-parametrizer settings; more detailed comparisons in Tab. 1.
Our results highlight that the convergence ScaledGD critically determined by the initialization. Taking symmetric and exact-parametrized problems example, our quadratic rate slows down to a linear one when adopting either small initialization or slightly perturbed Nyström initialization.
After demonstrating the theoretical merits of Nyström initialization, we further extend its applications to another scenario with Burer-Monteiro factorization, in the context of LoRA for finetuning deep neural networks (Hu et al., 2022). This is motivated by the fact that asymmetric matrix factorization equivalent to LoRA applied on linear models with whitened data (Arora et al., 2018), and is in line with several recent works that take insights from matrix factorization to improve LoRA (Zhang & Pilanci, 2024; Yaras et al., 2024). Compared with existing strategies for initializing LoRA (Büytkakyūūz, 2024; Meng et al., 2024; Wang al., 2024), our Nyström initialization for LoRA (abbreviated as NoRA) ) is more economical and aligns better with existing deployment pipelines. The effectiveness of NoRA demonstrated on downstream tasks from various domains, through both diffusion and large language models (LLMs). In a nutshell, our contributions can be summarized as:
Faster rates. Nyström initialization is provably beneficial to ScaledGD. For symmetric problems, it catalyzes not only the first quadratic rate in exact- and over- parameterized settings, but also a (sub)linear rate for under-parament parametrization where only asymptotic results were known. It also allows more remarkable improvement on asymmetric problems; details in Tab.
Critical role of initialization. Our theoretical results convey intriguing message for nonconvex (nonsmooth) optimization: the behaviors of the same algorithm, whether converging at a quadratic linear rate, are critically determined by initialization.
+ Practical implications. We further illustrate the power of Nyström initialization for finetuning diffusion and large language models (LLMs). The resultant approach, NoRA, effectively improves the performance of LoRA several representative tasks.
2

---

Published as a conference paper at ICLR 2025
Notation. Bold lowercase (capital) letters denote column vectors (matrices); ()), (-) and || IF refer to transpose, pseudo inverse, and Frobenius norm of a matrix; || || is the lz (spectrum) norm of vector (matrix); (-) and (-) denote the i-th largest singular value and eigenvalue, respectively.
1.1 RELATED WORKS
We only streamline results on the convergence of matrix factorization under the broad umbrella of quartic optimization. Other closely related topics, such as LoRA variants, can be found in Apdx. A.
Quartic Optimization. Matrix factorization problems considered in this work are classical examples of forth-order growth functions. It involves a complex landscape characterized by nonconvexity, nonsmoothness, and the absence of PL. condition. Similar to other works listed in Tab. 1, the goal of this work to recap this classical problem and to unveil intriguing behaviors from an optimization perspective, Recent works have examined the convergence of several algorithms, such as GD, AltGD, and ScaledGD (Du al., 2018; Ye & Du, 2021; Ward & Kolda, 2023; Jia et al., 2023; Jiang et al., 2023b) in exact- and over- parametrized settings. Most of them admit linear convergence with different dependences on the condition number of the factorized matrix A. A concurrent work (Xu et al., 2024) studies Nyström initialization for Nesterov's accelerated method on the asymmetric and over wwer-parametrizor setting, giving an improved condition number dependence over GD. GD for matrix square root problems is studied in (Jain et al., 2017). Another closely related setting within forth-order growth is matrix sensing; sec c.g., (Stöger & Soltanolkotabi, 2021; Zhang et al., 2021; Jin al., 2023; Xiong et al., 2024). Linear rates obtained for problems with exact- and over- parametrization, despite some of them demand early stopping. Similar to matrix factorization, not too much is known for munder-arraettrizane growth optimization. For example, relative smoothness is considered in (Lu et al., 201 8); adaptive step sizes induced by fine-grained geometry are studied in (Davis al., 2024). The work of (Dragomir & Nesterov, 2023) also copes with such problems but requires convexity of the objective.
There are other approaches tackle general forth-order
2 THE POWER OF INITIALIZATION FOR SYMMETRIC MATRIX FACTORIZATION
2.1 PRELIMINARIES
We start to examine the critical role of initialization on symmetric matrix factorization problems
1 -AII.
min XERIX
Within this section, we assume that A E Rmxm is positive semidefinite (PSD), otherwise one can employ the asymmetric formulation as in later sections. Problem (1) also closely links with matrix sensing, particularly under sufficient number of Gaussian measurements (Xiong et al., 2024). From an optimization perspective, problem (1) is nonconvex and has no global Lipschitz gradient (Tu et al., 2016; Chi et al., 2019). These undesirable properties pose challenges for analyzing its convergence.
Notationally, r == rank A) and further denote the compact eigendecomposition as A = QEQ where Q R m.x and Σ E R xra, Since PSD matrices share the same eigen and singular values, we employ (-) to denote both in this section. Without loss of generality, we assume that the largest and σr (A) = 1/K such that the condition number k.
and smallest singular values are σ (A)
ScaledGD as our optimizer. We investigate the power of initialization on ScaledGI (Tong et al., 2021), preconditioned version of GD; see detailed discussions e.g., (Tong al., 2021; Jia et al., 2023). Starting from = 0, the update of ScaledGD is given by
X = X, nXXx, - -A)X; (x, x,)
(2)
The inversion of the matrix X, is computationally feasible in the low-rank setting with r < m. Small initialization is widely adopted, i.e., [Xo]ij ~ No (2), where Ç is a sufficiently small positive number. Under such initialization, ScaledGD converges linearly for exact-parametriizaton (r = - yet less is known for under- and over-parametrization:; see more in Tab. 1. Next, we show that simple yet effective initialization can provoke faster convergence of ScaledGD.
'This linear rate is indicated by our numerical results in Fig. (a). While we are not aware of direct proof for this observation, it is presumahle that the analysis in the asymmetric and exact parametrraeer setting (Jia et al., 2023) could be adapted provide some guarantees.
3

---

Published as a conference paper at ICLR 2025
2.2 NYSTRÖM INITIALIZATION
To improve the convergence rates, it is essential to ensure that the initialization satisfies two conditions for exact- and under-parametrriee problems*: i) each column of Xn is in the column space of A, and ii) Xo is full rank, i.e., rank (X)) = r. The analytical rationale will be elucidated in the subsequent sections. straightforward means to meet these conditions is via Nyström sketch (Tropp et al., 2017)
Nyström initialization:
X = AΩ2 where [5] ~ (), Vi,
(3)
where Ω E R is a Gaussian random matrix. Note that the Gaussian Ω is only for practical convenience, and does not exclude other valid choices such as random draw from a Stiefel manifold St(m, r). From the initialization in (3), it is not difficult to see that condition i) is satisfied already. Our next lemma shows that condition ii) holds w.h.p.
Lemma (Initialization for exact- and under- parametrization). For some universal constant 0, o, (X.)) 2 ÉT(yTA - vr - 1),,, (A) is satisfied with high probability, i.e., rank (Xo) = w.h.p.
The detailed expression for this "high probability" in Lemma can be found in Apdx. B. Note that although we do not state explicitly, most of our results below hold under rank and auder-parametrizer setting, while rank(Xo) = -A is needed when over-parametrized.
in exact-
2.3 NYSTRÖM INIIIALIZATION IN THE SLACT-PARAMTTIEEE SETTING
We start with Nyström initialization for exact-parametrized problems, i.e., TA =r. r. Our first result dives into the implicit regularization induced by the ScaledGD under the proposed initialization.
Lemma 2. If Xo is obtained by Nyström initialization (3), ScaledGD in (2) ensures that for all t 2 0 i) every column of X4 is in the column space of A, and X Q for some D, RR and, ti) the smallest eigenvalue of X,X! satisfies that
(x(x)+1X(41) 2 21 2)2++2,, 0, (XxX + (1- (1 20+3
or (A).
Lemma implics the full rankness of X, over the trajectory, i.e., rank (x,) = rank (P)) = r, Vt. This ensures invertible preconditioner X, X₁. In other words, iteration (2) is well-defined. The most important implication of Lemma is the alignment of X, with the directions of eigenvectors of A, that is, X, Q This can be equivalently understood the elimination of the residual space, i.e., (I- QQ X = O, Vt. While we will expand this discussion shortly, this alignment in directions enables us to establish a quadratic rate for ScaledGD.
Theorem 1. With Nyström initialization (3), ScaledGD in (2) exhibits a two-phase behavior.
Phase (linear convergence). Let = =O( A After Tj = On /Flog k) iterations, ScaledGD ensures that [x; AlF S O(L/k²); and,
Phase 2 (quadratic convergence). After Phase I, ScaledGD converges quadratically with = 0.5. In particular, X A S e achieved after = O log log( h)) iterations.
Theorem establishes that global optimality of (1) is attained by ScaledGI within O Vr log log 1) iterations. ScaledGD first converges to local region satisfying XX,X, - -A linearly, after which a quadratic rate can be granted. This is, to the best of our knowledge, the first quadratic rate for symmetric matrix factorization (1). Interestingly, it is achieved without requiring (exact) Hessian on a nonconvex and nonsmooth problem. A graphical illustration of this quadratic rate can be found in Fig. (a) using synthetic data detailed in Apdx. E. is observed that ScaledGD with Nyström initialization outperforms linearly converging algorithms such as GD and ScaledGD with small initialization. Moreover, it is worth emphasizing that Theorem has no requirement on the magnitude of Nyström initialization it does not need & in (3) to be small. Compared with small initialization, i.e., X, Ri O, this avoids escaping from the stationary point O. The convergence of ScaledGD under various choices of & can be found in (the solid lines of) Fig. 1(b).
For the case of presentation, the over-parametrized setting considered in the appendix.
4

---

Published as a conference paper at ICLR 2025
10
10
E=1.6=0
104
10*
10
8-1.5-01
10"
10
6-10.6-011
6-10,6-0
102
Ire02
1014
10
10a
g-10n, m.
10-4
10-4
E- 0-0.16--
E E.0.1..-
10-31
Scaled
10-11
Ours
10
10:41
(a) exacttpprrmettriiatioon
(b) exact-parametrizatton
(c) unnder-parametrization
Figure I: Convergence of ScaledGD under Nyström initialization (optimality error vs. iteration) in different settings. (a) Comparison of GD, and ScaledGD with small / Nyström initialization (ours). (b) Solid lines show that our initialization is not sensitive to magnitude of ç; and dotted lines illustrate that quadratic convergence cannot be obtained after perturbing the initialization. i.c., X AΩ + N, where [ ~ (0, (.). (c) Comparison of ScaledGD under Nyström initialization with various
The critical role of initialization. As shown in Lemma 2, Nyström initialization aligns X, to the directions of cigenvectors Q, thereby eliminating the residual space, i.c., -I-QQI )X; is critical for quadratic rate and it is in stark contrast with most of existing works (Du et al., 2018; Ye & Du, 2021; Jía al., 2023), where small initialization only guarantees that I|(T QQ T )x, |I converges to 0 at linear rate. We graphically illustrate this point in Fig. 1 (b), where we perturb Nyström initialization slightly to inject noise into the residual space. Reflected in the dotted lines, even if the noise is so small such that the earlier convergence does not differ from Nyström initialization, only a linear convergence can be observed for the perturbed initialization.
0, Vt. This
Extensions to the case of over-varanne parametiization. Nyström initialization is further extended cope with peeaparraetrizee case (r >> TA) in Apdx. B.4. For this specific setup, we slightly modify ScaledGD by substituting the possibly non-invertible (X, x,) in (2) with (X, X,):; see (26). Unlike previous works (Xu et al., 2023; Zhang et al., 2021), our modification requires no damping parameters thanks to our Nyström initialization. This leads to, far for over-parametrized problems. Additional numerical experiments on over-parametrized problems are provided in Fig. appendix validate the established quadratic rate.
know, the first quadratic rate
2.4 NYSTRÖM INITIALIZATION IN THE UNDER-PARAMETRIN SETTING
Next, we consider the under- ander-pprametrizeed case of (1), i..., < TA. To the best of our knowledge, only asymptotic convergence is established for GD such problems (Du et al., 2018). This is partially because that even the local PL condition is challenging to be verified. With Nyström initialization, will show that ScaledGD converges under slightly weaker criterion.
Definition (Weak optimality). Matrix X Rmxr is weakly optimal to A -, =.
Our first result characterizes that all global optima are also weakly optimal. In other words, if weak optimality ensured, this algorithm has a chance to reach a global optimum as well.
Lemma 3. All globally optimal solutions to (1) are also weakly optimal.
We then focus on the convergence of ScaledGD to weak optimality. In the case of under- parametrization, Nyström initialization also aligns X, to the directions of eigenvectors of A.
Lemma 4. If ScaledGD in (2) is equipped with Nyström initialization (3), write X, Q&i,, for some 4; E Rraxx.
Lemma 4 shows that (I QQ Xx = O, Vt also holds, namely, Nyström initialization eliminates the residual space. Building upon this, the convergence of ScaledGD can be established.
Theorem 2. The following holds for ScaledGI) (2) with Nyström initialization (3):
i) (Linear convergence to neighborhood of weak optima). If one chooses a constant rj S 1, ScaledGD ensures that X A.X, -L,lFF O(rr) - in O !) iterations; or,
ti) (Convergence to weak optima). Let 1j = O weak optimality is ensured by ScaledGD after O log !) iterations, iee., X A Atx, I, S
5

---

Published as a conference paper at ICLR 2025
If one chooses constant learning rate e.g. 17 0.1, linear convergence be established until reaching a neighboring area of a weakly optimal solution. The error X A'X, - I, || ((r)) is low, given that is typically small in practice. A graphical illustration of this linear rate can be found in Fig. (c). On the other hand, if the learning rate chosen according to the prescribed accuracy 6, one can obtain sublinear rate O log !) to exact weak optimality. These behaviors clearly indicate a step scheduling of learning rates (c.g., setting convergence and exact weak optimality in practice. It is also worth mentioning that the convergence under both choices of has no dependence on R. This aligns with the presumption in previous works (Tong al., 2021; Jia et al.. 2023) that ScaledGD performs well on ill-conditioned problems, providing the first rigorous justification for the under-pante under-parametrized setting.
0.1, 0.01, every few iterations) for both fast
Finally, we show that even the worst case, ScaledGD guarantees that X, converges to a point that is adequately close to global solution, and the relative distance is sublinear in r.
Lemma S. Let Q1 be the first r column on Q, and Σ1 be the top-left r x sub-block of E. Denote an optimal solution (1) X. Q1 E 1/2 ScaledGD (2) with Nyström initialization (3) ensures
lim 100
X X.IlF S O(13/4).
THE POWER OF INITIALIZATION FOR ASYMMETRIC MATRIX FACTORIZATION
3.1 INITIALIZATION AND MODIFIED SCALEDGD
This section demonstrates that the power of initialization is even more striking in solving asymmetric matrix factorization than symmetric ones. Given A E Rmxx, consider the following problem
|XY T -AIE.
min XERmXr,YERRE
Denote rank(A) = TA. and the compact SVD as A = UEVT, where U E R E RrAXFA, and V RnXrA, Similar to the previous section, assume that 0 (A) and or (A) 1/k.
Nyström initialization. We adopt an asymmetric manner to initialize Xg and Yo for (4), i.c.,
Nyström initialization: Xo AS2, Yo 0
where Z is Gaussian random matrix of Raxr with [S]e NO {²), Vi, Vj. We can follow the same steps of Lemma 1 to show that X, in (5) is rank r w.h.p. in exact- and under-panee muder-parametrizer settings. Moreover, there is requirement
the magnitude of &, meaning that it is possible to start far from the saddle point (0, 0). This asymmetry of X, and Yo in (5) is in contrast with small initialization which typically induces |X F |oolf (Du al., 2018; Jia et al., 2023). The merits will become clear shortly. Note that AltGD (Ward & Kolda, 2023) also adopts sketch at initialization, i... X O(A /o1 (A)) and Y, ( (A) where S2 and f2g are Gaussian random matrices. Besides the requirement on small variance of Ωr and f2 and the explicit need of o (A), this initialization cannot eliminate the residual space. Consequently, AltGD demands early stopping in exact- and peerpaarmettrized problems, and little is known for
case.
Modified ScaledGD. To adapt to the non-invertible YJ Yo- = 0 in Nyström initialization (5), we modify the first iteration of ScaledGI.. More precisely, the updates are summarized below
X, Xo, and X X, Y,YY A)Y, Y.) 2 1;
(6a)
Y ++ = Y. - -,,,, (XYYT - A) X, ( X.) V 20
(6b)
3.2 NYSTRÖM INITIALIZATION IN THE PAATT-PARAMETRIEEE SETTING
We start with the pract-pprametrized case, i.e., r' in (4). The benefit of Nyström initialization (5) for iteration (6) is again the alignment of X, and Y, to the directions of singular vectors.
Lemma 6. The modified ScaledGD in (6) under Nyström initialization (5) guarantees that X, = U and Y, V Vt. 2 0 for some D E xr and W, , Brxr.

---

Published as a conference paper at ICLR 2025
Similar to the symmetric problems, the implication of Lemma 6 is the elimination of residual space, ie., (I )X, = 0 and (I - VV")Y, = O. This turns out to be even more beneficial for asymmetric problems, as it induces one-step convergence of ScaledGD.
Theorem 3 (One-step convergence), With dj and Nyström initialization (5), the modified ScaledGD (6) guarantees X, Y A. In other words, global convergence is achieved in one step.
Comparing to symmetric case (cf. Theorem 1), Theorem 3 suggests that solving problem (4) requires less iterations owing to the asymmetry of X. and Yo at initialization (5). This agrees with results in (Xiong al., 2024), which illustrate the benefit of asymmetry for matrix sensing.
Remark 1. The one step convergence of ScaledGD can also be interpreted as a new approach for matrix factorization. While the complexity of this factorization is generally equivalent to that of SVD, can be faster than SVD when O 0.3) <r< S n. Further details are provided in Apdx. A.5.
Lastly, we present result that may be of independent interest the asymmetric and symmetric problems are interconnected under our Nyström initialization. This link made clear in the proof of the following corollary (to Theorem 1), which states that ScaledGD admits quadratic convergence under different choices of step sizes.
Corollary (Quadratic convergence). With Nyström initialization (5) and different choices of step
sizes, modified ScaledGD in (6) has a similar behavior as Theorem 1, i.e.
Phase I (linear convergence). Let O ((TTAT)) After Ti := Ox* VFlog k) iterations, ScaledGD ensures that |XT, Y,; - AFF S ((L/n²).
Phase 2 (quadratic convergence). After Phase I, ScaledGD converges quadratically with 17 0.5. In particular, X Al|F S e is ensured after T = 0 log( iterations.
Extensions to over-parametrization One-step global convergence can also be established for over-parametrized asymmetric problems under Nyström initialization. More on this can be found in Apdx. C.3, where we provide the first convergence result on ScaledGD under such setup.
3.3 NYSTRÖM INITIALIZATION IN THE PARAMETRIZED SETTING
Lastly, we tackle the case of pramettaraattiiiationnn the asymmetric problem (4), where rA r. Similar to the symmetric case in Sec.2.4, we consider a slightly weaker version of optimality.
Definition 2 (Generalized weak optimality). We say (X, Y) is weakly optimal if Y A - I, 0.
Generalized weak optimality is satisfied by any global optimum, which is proved in Lemma 13 in the appendix. With this preparation, we are ready to show that ScaledGD converges in single step. Theorem 4. If n 1, ScaledGD in (6) with Nyström initialization (5) ensures generalized weak optimality in one iteration, i.e., Y X - O.
The critical role of initialization. Through the theoretical analyses in the previous two sections, is evident that the convergence of ScaledGI for matrix factorization is highly dependent on the initialization, Here is an intuitive, though not strictly rigorous, summary: Small initialization results in behaviors similar to first-order optimizers, i.e., linear convergence (Jia et al., 2023). In contrast, the proposed Nyström initialization catalyzes quadratic rates and even one-step convergence, resembling the optimization trajectory of second-orded approaches such as Newton's 's method (Nesterov, 2004).
NORA: NYSTRÖM LOW RANK ADAPTERS
Our theoretical results highlight the merits of suitable initialization for matrix factorization problems. One of the key insights is that the Burer-Monterio factorization benefits from good directions of Xo and Yo at initialization; ef. Lemmas 2 and 6. We term this as directional alignment. In this section, we extend the benefit of initialization to practical scenarios, showing that directional alignment is also beneficial for low-rank adapters (LoRA) in finetuning deep neural networks (Hu al., 2022).
LoRA enhances parameter efficiency of finetuning by approximating the unknown parameter-change A AWE E xm through Burer-Monteric factorization
Wo + AW ~ W. + X
7

---

Published as a conference paper at ICLR 2025
20
Frqueno
15-
frquster
20-
(a) BoolQ
(b) ReCoRD
(c) RTE
Figure 2: Which singular values have the largest change after finetuning with LoRA of rank r?
Orange: top-r singular values; blue: other singular values. Note that here we only plot the first 64 singular values as others rarely have sufficiently large change.
Table 2: Performance of NoRA and NoRA+ for few-shot learning with OPT-1.3B
OPT.1.3B
SST.2
BoolQ
ReCoRD
MuliRC
SQuAD
avg (1)
Pretix
92.940.9
59.6
73.1+2.3
71.6=2.9
65.2+2.0
69.7-1.0
64.443.2
82.++1.
72.3
LoRA
93.1
59.112.0
70.61..2
72.6.3.7
69.1
70.8_1.0
68.01144
81.911.
73.2
OLoRA
92.7.0.5
60.01..a
70.91..1
80.3g..7
69.7.1.0
7..321.2
66.710.9
80.0g1.4
74.0
PISSA
92.7.0.6
60.613.7
70.4...7
78.0g7.2
70.4
70.9_1.2
67.9
82.1
74.1
NoRA
93.4go.r
60.6g3.
73.2
79.2:3.2
12.0
71.321.0
68.5
81820.7
75.0
NoRA+
93.2.0.5
61.220.6
72.911.3
79.523.8
72.433.6
71.520.9
68.4112
82.020.9
75.1
where Wo E Rmx" the pretrained weight (of a particular layer), and E R and Y E Baxr with r & min min(m,n): n). A more detailed recap of LoRA can be found in Apdx. A. Directional alignment can be achieved if singular vectors for AW are leveraged to initialize X, and Yo. While AW is unavailable priori, empirical wisdom suggests that there exists set of well-performed adapters that lie in the column span of the pretrained weight matrix (Lingam et al., 2024), i.c., ColSpan( AW) S ColSpan (Wo)). In other words, Wo can be adopted suitable replacement of AW for directional alignment.
Having ColSpan (W) alone is insufficient for directional alignment, since it does not specify which directions are more crucial. To answer this question, we examine the singular values that undergo the most significant change after LoRA finetuning on few-shot learning task (Malladi et al., 2023). OPT-1.3B is chosen as the base model and LoRA is applied to its query and value matrices with r = 8; more details can be found in Apdx. E.3. For each LoRA layer, we count the indices of singular values that exhibit the largest changes after finetuning, and summarize their frequencies across all layers in Fig. 2. It is observed that the top-r singular values tend have larger change, explaining the success of LoRA initialization approaches that aligns X, with the directions corresponding to these singular values, such as PiSSA and OLoRA (Meng al., 2024; Büyükakyūz, 2024). However, across all tested datasets, substantial portion of non-top-r singular values also demonstrate significant variation, and the frequency is positively linked to the singular values. In other words, the directions corresponding larger singular values tend to be more important. This is akin to the principle of Nyström initialization X.- = Wosl, evidenced by its spectrum, i.c., X[X x W...
Building upon these observations, and considering the accelerated convergence with Nyström initial- ization in ScaledGD, we propose two novel variants LoRA:
Nyström LoRA (NoRA): This approach applies (5) directly on top of LoRA, that is, Xg- = W.2 and Y, 0.
Nyström preconditioned LoRA (NoRA+):
This approach not only advances LoRA initialization with (5), but also leverages ScaledGD for optimization.
We note that ScaledGD has already been applied for LoRA training in (Zhang & Pilanci, 2024), which we refer to LoRA-P (P for preconditioning). We will show that both LoRA and LoRA-P benefit significantly from Nyström initialization. Due to space limitation, we summarize NoRA and NoRA+ in Algs. and 2, respectively in the appendix, with additional explanations in Apdx. A.3.
Deployment efficiency. NoRA offers practical advantages over other initialization methods such as PiSSA and OLoRA. It not only bypasses the computationally expensive SVD or QR decomposition, but also avoids the need to modify to the pretrained weights. NoRA is thus an off- off-the-shelf solution to enhance LoRA without altering existing pipelines. We expand on this in Apdx. A.3.
8

---

Published as a conference paper at ICLR 2025
Table 3: Training loss of NoRA and NoRA+ with stable-diffusion.
loss(L)
LoRA
LoRA-P
NoRA
NoRA+
avg
0.092::0.012
0.09311.012
0.08410.017
0.08410.015
LoRA-P LoRA
NoRA
NoRA+
Figure 3: Generated images from NoRA and NoRA+ with stable-diffusion.
5 NUMERICAL RESULTS FOR NoRA
The efficiency of proposed NoRA and NoRA+ is demonstrated on large-scale finetuning tasks involving diffusion and LLMss. The experiments are conducted with PyTorrch (Paszke et al., 2019) on NVIDIA H100 GPUs Details on datasets and experimental procedures can found in Apdx. Code is available https://///
5.1 FEW-SHOT LEARNING WITH OPT-1.3B
Our evaluation starts with a few-shot learning task following (Malladi et al., 2023). The objective to rapidly adapt language model with a small training set. The datasets for this experiment are drawn from GLUE and SuperGLUE benchmarks (Wang et al., 201 2019b;a). Consistent with (Malladi et al., 2023), we randomly sample 1,000 data points for training and another 1,000 for testing.
We embrace O.T-1.3B value matrices the attention module. This aligns with common practice for models this size. The rank of LoRA is set 8, leading approximately 1.5M trainable parameters, which is significantly less than the model size. We compare the proposed NoRA and NoRA+ with LoRA, prefix tuning (Li Liang, 2021), OLoRA (Büyükakyüz, 2024), and PiSSA (Meng et al., 2024), Note that the latter two serve as alternative methods for initializing LoRA.
base model (Zhang al., 2022) and apply LoRA to the query and
The performance of different algorithms is summarized in Tab. It evident that OLoRA, PISSA, NoRA, and NoRA+ all outperform LoRA because their initialization strategies have provided more favorable directions for optimization. Among these initialization approaches, NoRA and NoRA+ have the best average accuracy, with absolute improvement over LoRA by 1.8 and 1.9, respectively.
5.2 SURJECT-DRIVEN IMAGE GENERATION WITH STABLE-DIFFUSION
Next, we focus on dubject-driven image generation (Ruiz et al., 2023). The goal of this task is to finetune a diffusion model with only a few user-specific images (typically less than 10) so that the modal can generate the same object in various contexts. The base model is selected as StableDiffusion v1.4 (Rombach et al., 2022) (0.98B parameters in total). We adhere to the default setting and finetune the U-Net with LoRA. The rank of LoRA is set as 4, amounting 0.8M trainable parameters. The diffusion model is finetuned on a user-specific training set containing pictures of a dog labeled "a photo of Vaog." with the aim generate proper images under the prompt "a Vang eating nachos."

---

Published as a conference paper at ICLR 2025
Table 4: Performance of various algorithms for commonsense reasoning LLaMA-7B and I.L.MA2-
7B. The results marked with $ are taken from (Liu et al., 2024). HS and WG are abbreviations for HellaSwag and WinoGrande, respectively.
Alg.
BoolQ
PIQA
SIQA
HS
WG
ARC-e
ARC-c
OBQA
avg (1)
LoRA
66.42
80.03
77.84
82.88
81.85
79.92
63.40
77.20
76.19
LLaMA
LoRA-P
68.96
80.95
77.43
81.54
80.27
78.83
64.16
79.20
76.41
NoRA
68.20
80.79
78.40
85.09
80.27
79.17
62.80
78.80
76.69
NoRA+
69.85
81.83
77.38
82.09
80.03
79.67
64.25
78.60
76.71
LLaMA2
LoRA3
69.8
79.9
79.5
83.6
82.6
79.8
64.7
81.0
77.6
LoRA-P
71.47
81.50
78.81
85.97
80.43
81.14
66.55
81.00
78.35
NoRA
71.16
83.08
79.53
85.90
81.85
80.64
66.13
81.80
78.76
NoRA+
70.52
81.94
79.07
87.66
82.24
82.70
67.06
80.20
78.92
To demonstrate the power of initialization, we compare NoRA and NoRA+ with LoRA and LoRA-P. The averaged training loss of considered approaches are summarized Tab. can seen that NoRA and NoRA+ have 9.6% smaller training loss compared with LoRA and LoRA-P, demonstrating the benefits of directional alignment at initialization. The generated images are listed in Fig. 3. Some of images generated by LoRA are natural. For instance, the third expression for nachos, and the tenth is not vivid. For LoRA-P, the dog in the third image is also not natural. NoRA and NoRA+ a floating plate in the 8th image of NoRA+, but ensuring diffusion models to follow physical laws goes beyond the scope of this work. Additional results provided in Apdx. E.5, where finetune on images of cat toy. The generated images from NoRA and NoRA+ have more lively facial details compare those not using Nyström initialization.
does not have nice
the other hand, both generate high-fidelity pictures. However, there is
5.3 COMMONSENSE REASONING WITH LLAMA-7B AND LLAMA2-7B
Our evaluation is further scaled to LLMs using LLaMA and LLaMA2-7B (Touvron et al., 2023a;b). We tackle commonsense reasoning tasks following the setup in (Hu et al., 2023). Training data are merged from 8 datasets listed in Tab. 4. The test sets remain separate for individual evaluation. These reasoning tasks are intended to push the model beyond pattern recognition, requiring commonsense and knowledge to make proper inferences. The rank of LoRA is chosen 32.
The results on LLaMA-7B are summarized in the upper block of Tab. It is observed that NoRA improves the average accuracy by 0.5 over LoRA, while NoRA+ also surpasses LoRA-P. These results underscore the significance of initialization for optimizing LoRA. The numerical results on I.LAMA2-BB are presented in the lower block of Tab. 4. It is observed that LoRA is unstable, henceforth the results for LoRA are taken from (Liu et al., 2024). This instability is not observed in other approaches tested. In this experiment, the benefit of the Nyström initialization particularly pronounced, as the absolute improvement is even greater compared to the results on LLaMA-7B.
A Additional numerical results. The efficiency of NoRA and NoRA+ is further validated Gemma- 7B for math reasoning tasks. More details can be found in Apdx. E.7.
CONCLUDING REMARKS
This work characterizes how initialization can crucially determine the convergence behavior of the same optimization algorithm on matrix factorization problems. We prove that Nyström initialization can significantly improve the complexity bounds of ScaledGI under wide spectrum of settings; see details Tab. One of the key improvements is that Nyström initialization enables a quadratic convergence for exact- and over-parametrized problems, whereas small initialization only guarantees a linear rate on ScaledGD. This performance gap calls for more careful investigation into the role of initialization in optimization. Additionally, the proposed Nyström initialization offers practical merits when applied on finetuning with LoRA, delivering deployment flexibility and promising numerical performance on large-scale problems with L.MSs and diffusion models.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGEMENTS
We thank anonymous reviewers for their suggestions, BL is supported by Swiss National Science Foundation (SNSF) Project Funding No. 200021-207343. LZ gratefully acknowledges funding by the Max Planck ETH Center for Learning Systems (CLS). AM is partially supported by the NSF AI Institute for Foundations of Machine Learning (IFML), the NSF CARÉER Award CCF-2338846, and Google Research Scholar Award. NH is supported by ETH research grant funded through ETH Zurich Foundations and SNSF Project Funding No. 200021-207343.
REFERENCES
Josh Alman, Ran Duan, Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou. More asymmetry yields faster matrix multiplication. 2rXiv:2404.100 16349, 2024.
Sanjeev Arora, Nadav Cohen, Noah Golowich, and Wei Hu. A convergence analysis of gradient descent for deep linear neural networks. In Proc. Int. Conf. on Machine Learning (ICML), 2018.
Klaudia Batazy, Mohammadreza Banaei, Karl Aberer, and Jacek Tabor. LoRA-XS: Low-rank adaptation with extremely small number of parameters. arXiv:2405. /7604, 2024.
Yonatan Bisk, Rowan Zellers, Jianfeng Gao, Yejin Choi, al. Piqa: Reasoning about physical commonsense in natural language. In Proc. AAAI Conf. Artif. Intel., pp. 7432-7439, 2020.
Samuel Burer and Renato DC Monteiro. A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization. Mathematical programming, 95(2):329-33) 00003329-37,,000 2003.
Kerim Büyükakyüü.. OLoRA: Orthonormal low-rank adaptation of large language models.
arXiv:2406.01775, 2024.
Yukang Chen, Shengju Qian, Haotian Tang, Xin Lai, Zhijian Liu, Song Han, and Jiaya Jia. Long- LoRA: Efficient fine-tuning of long-context large language models. In Proc. Int. Conf. on Learning Representations (ICLR), 2024.
Yuejie Chi, Yue M Lu, and Yuxin Chen. Nonconvex optimization meets low-rank matrix factorization: An overview. IEEE Trans. Signal Processing, 67(20):5239-5269, 2019.
François Chollet. On the measure of intelligence. arXiv: 2019.
Christopher Clark, Kenton Lee, Ming-Wei Chang, Tom Kwiatkowski, Michael Collins, and Kristina Toutanova. BoolQ: Exploring the surprising difficulty of natural yes/no questions. arXiv: 10044, 2019.
Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, al. Training verifiers solve math word problems. arXiv:2110.14169 2021.
Damek Davis, Dmitriy Drusvyatskiy, and Liwei Jiang. Gradient descent with adaptive stepsize converges (nearly) linearly under fourth-order growth. arXiv:2409. 19791, 2024.
Marie-Catherine De Marneffe, Mandy Simons, and Judith Tonhauser. The CommitmentBank: Investigating projection naturally occurring discourse. Proc. Sinn und Bedeutung, 23(2):107- 124, 2019.
Tim Dettmers, Artidoro Pagnoni, Ari Holtzman, and Luke Zettlemoyer. QLoRA:
Efficient finetuning of quantized LLMss. In Proc. Neural Information Processing Systems (NeurlPS), volume 36, 2023.
Radu-Alexandru Dragomir and Yurii Nesterov, Convex quartic problems: homogenized gradient method and preconditioning. arXiv:2306.17633 2023.
Simon S Du, Wei Hu, and Jason D Lee. Algorithmic regularization in learning deep homogeneous models: Layers are automatically balanced. In Proc. Neural Information Processing Systems (NeurIPS), volume 31, 2018.
11

---

Published as a conference paper at ICLR 2025
Ziqi Gao, Qichao Wang, Aochuan Chen, Zijing Liu, Bingzhe Wu, Liang Chen, and Jia Li. Parameter- efficient fine-tuning with discrete fourier transform. In Proc. Int. Conf. on Machine Learning (ICML), 2024.
Rong Ge, Chi Jin, and Yi Zheng. No spurious local minima in nonconvex low rank problems: A unified geometric analysis. In Proc. Int. Conf. on Machine Learning (ICML), pp. 1233-1242. PMLR, 2017.
Gemma-team, Thomas Mesnard, Cassidy Hardin, Robert Dadashi, Surya Bhupatiraju, Shreya Pathak, Laurent Sifre, Morgane Rivière, Mihir Sanjay Kale, Juliette Love, et al. Gemma: Open models based on gemini research and technology. arXiv:2403.08: 08295, 2024.
Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4))2341-2366 2013.
Yuchao Gu, Xintao Wang, Jay Zhangjie Wu, Yujun Shi, Yunpeng Chen, Zihan Fan, Wuyou Xiao, Rui Zhao, Shuning Chang, Weijia Wu, et al. Mix-of-show: Decentralized low-rank adaptation for multi-concept customization of diffusion models. In Proc. Neural Information Processing Systems (NeurIPS), volume 36, 2023.
Yongchang Hao, Yanshuai Cao, and Lili Mou. FLORA: Low-rank adapters are secretly gradient compressors. In Proc. Int. Conf. Machine Learning (ICML), 2024.
Soufiane Hayou, Nikhil Ghosh, and Bin Yu. The impact of initialization on lora finetuning dynamics. 20X10:2406.08447,, 2024.
Neil Houlsby, Andrei Giurgiu, Stanislaw Jastrzebski, Bruna Morrone, Quentin De Laroussilhe, Andrea Gesmundo, Mona Attariyan, and Sylvain Gelly. Parameter-efficient transfer learning for NLP. In Proc. Int. Conf. on Machine Learning (ICML), pp. 2790-2799, 2019.
Edward Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li. Shean Wang, Lu Wang, and Weizhu Chen. LoRA: Low-rank adaptation of large language models. In Proc. Int. Conf. on Learning Representations (ICLR), 2022.
Zhiqiang Hu, Lei Wang, Yihuai Lan, Wanyu Xu, Fe-Peng Lim, Lidong Bing, Xing Xu, Soujanya Poria, and Roy Ka- Wei Lee. LLM--Aapters: An adapter family for parameter-effiiint fine-tuning of large language models. In Proc. Conf. Empirical Methods in Natural Language Processing (EMNLP), 2023.
Prateck Jain, Chi Jin, Sham Kakade, and Pranceth Netrapalli. Global convergence of non-convex gradient descent for computing matrix squareroot. In Proc. Int. Conf. Artificial Intelligence and Statistics (AISTATS), pp. 479-488. PMLR, 2017.
Uijeong Jang, Jason D Lee, and Ernest K Ryu. LoRA training in the NTK regime has no spurious local minima. In Proc. Int. Conf. on Machine Learning (ICMI), 2024.
Xixi Jia, Hailin Wang, Jiangjun Peng, Xiangchu Feng, and Deyu Meng. Preconditioning matters: Fast global convergence of non-convex matrix factorization via scaled gradient descent. In Proc. Neural Information Processing Systems (NeurIPS), 2023.
Kaiqi Jiang, Dhruv Malik, and Yuanzhi Li. How does adaptive optimization impact local neural network geometry? Proc. Neural Information Processing Systems (NeurIPS), 36, 2023a.
Liwei Jiang, Yudong Chen, and Lijun Ding. Algorithmic regularization in model-free over- parametrized asymmetric matrix factorization. SIAM Journal on Mathematics of Data Science, (3):723-744, 2023b.
Ruichen Jiang, Qiujiang Jin, and Aryan Mokhtari. Online learning guided curvature approximation: A quasi-newton method with global non-asymptotic superlinear convergence. In Proc. Annual Conf. on Learning Theory (COLT), pp. 1962-1992. PMLR, 2023c.
Jikai Jin, Zhiyuan Li, Kaifeng Lyu, Simon Shaolei Du, and Jason D Lee. Understanding incremental learning of gradient descent: A fine- ane-grained analysis of matrix sensing. In Proc. Int. Conf. on Machine Learning (ICMI). pp. 15200-15238, 2023.
12

---

Published as a conference paper at ICLR 2025
Qiujiang Jin and Aryan Mokhtari. Non-asymptotic superlinear convergence of standard quasi-newton methods. Mathematical Programming. 200(1):425 473, 2023.
Daniel Khashabi, Snigdha Chaturvedi, Michael Roth, Shyam Upadhyay, and Dan Roth. Looking beyond the surface: A challenge set for reading comprehension over multiple sentences. In Proc. Conf. Assoc. Comput. Linguist. Meet., pp. 252-262, 2018.
Diederik Kingma and Jimmy Ba. Adam: method for stochastic optimization. In Proc. Int. Conf. on Learning Representations (ICLR), 2014.
Dawid Jan Kopiczko, Tijmen Blankevoort, and Yuki M Asano. VeRA: Vector-based random matrix adaptation. In Proc. Inl. Conf. on Learning Representations (ICLR), 2024.
Hector Levesque, Ernest Davis, and Leora Morgenstem. The winograd schema challenge. In Proc. intl. conf. on Principles of Knowledge Representation and Reasoning, 2012.
Bingcong Li, Liang Zhang, and Niao He. Implicit regularization of sharpness-aware minimization for scale-invariant problems. In Proc. Neural Information Processing Systems (NeurIPS), 2024a.
Xiang Lisa Li and Percy Liang. Prefix-tuning: Optimizing continuous prompts for generation. In Proc. Conf. Assoc. Comput. Linguist. Meet., pp. 4582 4597, 2021.
Yixiao Li, Yifan Yu, Chen Liang, Pengcheng He, Nikos Karampatziakis, Weizhu Chen, and Tuo Zhao. LoftQ: LoRA-fine-uunng--ae aware quantization for large language models. In Proc. Int. Conf. on Learning Representations (ICLR), 2024b.
Vladislav Lialin, Sherin Muckatira, Namrata Shivagunde, and Anna Rumshisky. ReLoRA: High-rank training through low-rank updates. In Proc. Int. Conf. on Learning Representations (ICLR), 2024.
Vijay Lingam, Atula Tejaswi, Aditya Vavre, Aneesh Shetty, Gautham Krishna Gudur, Joydeep Ghosh, Alex Dimakis, Eunsol Choi, Alcksandar Bojchevski, and Sujay Sanghavi. Svft: Parameter-efficient fine-tuning with singular vectors. arXiv:2405. / 19597, 2024.
Shih-Yang Liu, Chien-Y Yi Wang, Hongxu Yin, Pavlo Molchanov, Yu-Chiang Frank Wang, Kwang- Ting Cheng, and Min-Hung Chen. DoRA: Weight-dccomposed low-rank adaptation. In Proc. Int. Conf. on Machine Learning (ICML), 2024.
Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In Proc. Int. Conf. on Learning Representations (ICLR), 2017.
Haihao Lu, Robert M Freund, and Yurii Nesterov. Relatively smooth convex optimization by first-order methods, and applications. SIAM Journal on Optimization, 28( 28(1)3333-554, 2018.
Sadhika Malladi, Tianyu Gao, Eshaan Nichani, Alex Damian, Jason D. Lee, Danqi Chen, and Sanjeev Arora. Fine-tuning language models with just forward passes. In Proc. Neural Information Processing Systems (NeurIPS), volume 36, 2023.
Fanxu Meng, Zhaohui Wang, and Muhan Zhang. PiSSA: Principal singular values and singular vectors adaptation of large language models. arXiv:2404.00 024444440 2024.
Todor Mihaylov, Peter Clark, Tushar Khot, and Ashish Sabharwal. Can a suit of armor conduct electricity? A new dataset for open book question answering. arXiv:1800 1809.82789, 2018.
Yurii Nesterov, Introductory lectures on convex optimization: A basic course, volume 87. Springer Science & Business Media, 2004.
Mahdi Nikdan, Soroush Tabesh, and Dan Alistarh. RoSA: Accurate parameter-efficient fine-tuning via robust adaptation. In Proc. Int. Conf. on Machine Learning (ICML), 2024.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style. high- performance deep learning library. In Proc. Neural Information Processing Systems (NeurIPS), volume 32, 2019.
13

---

Published as a conference paper at ICLR 2025
Pranav Rajpurkar, Jian Zhang, Konstantin Lopyrev, and Percy Liang. SQuAD: 100,000+ questions for machine comprehension text. In Proc. Conf. on Empirical Methods in Natural Language Processing (EMNLP), pp. 2392, 2016.
Anton Rodomanov and Yurii Nesterov. Greedy quasi-newton methods with explicit superlinear convergence. SIAM Journal on Optimization, (1()):755-111 2021.
Robin Rombach, Andreas Blattmann, Dominik Lorenz, Patrick Esser, and Björn Ommer. High- resolution image synthesis with latent diffusion models. In Proc. Conf. Computer Vision and Pattern Recognition (CVPR), pp. 10684-10695, 2022.
Mark Rudelson and Roman Vershynin. Smallest singular value of random rectangular matrix. Communications on Pure and Applied Mathematics, 1707271777 2009.
Nataniel Ruiz, Yuanzhen Li, Varun Jampani. Yacl Pritch, Michael Rubinstein, and Kfir Aberman. Dreambooth: Fine tuning text-to-image diffusion models for subject-driven generation. In Proc. Conf. Computer Vision and Pattern Recognition (CVPR), pp. 12500-22511 2023.
Keisuke Sakaguchi, Ronan Le Bras, Chandra Bhagavatula, and Yejin Choi. Winogrande: adversarial winograd schema challenge at scale. Communications of the ACM, 64(9):99-106,
2021.
Maarten Sap, Hannah Rashkin, Derek Chen, Ronan LeBras, and Yejin Choi. Socialiqa: Commonsense reasoning about social interactions. axXiv:1904.09728. 2019.
James Seale Smith, Yen-Chang Hsu, Lingyu Zhang, Ting Hua, Zsolt Kira, Yilin Shen, and Hongxia Jin. Continual diffusion: Continual customization of text-to-image diffusion with c-LoRA
arXiv:2304.06027, 2023.
Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher D Manning, Andrew Y Ng, and Christopher Potts. Recursive deep models for semantic compositionality over a sentiment treebank. In Proc. Conf. on Empirical Methods in Natural Language Processing (EMNLP), pp. 1631-1642, 2013.
Dominik Stöger and Mahdi Soltanolkotabi. Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstruction. In Proc. Neural Information Processing Systems (NeurIPS), volume 34, pp. 23831-23844 2021.
Salma Tarmoun, Guilherme Franca, Benjamin D Haeffele, and Rene Vidal. Understanding the dynamics of gradient flow in overparameterized linear models. In Proc. Int. Conf. on Machine Learning (ICML), pp. 10153-10161, 2021.
Tian Tong, Cong Ma, and Yuejie Chi. Accelerating ill-conditioned low-rank matrix estimation via scaled gradient descent. Mach. Learn. Res., 22(150):1 163, 2021.
Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al. Llama: Open and efficient foundation language models. arXiv:2302.13991, 2023a.
Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et Llama 2: Open foundation and fine-tuned chat models. arXiv:2307.09288 092888 2023b.
Joel A Tropp, Alp Yurtsever, Madelcine Udell, and Volkan Cevher. Fixed-rank approximation of a posidive-semidefinite matrix from streaming data. In Proc. Neural Information Processing Systems (NeurIPS), volume 30, 2017.
Stephen Tu, Ross Boczar, Max Simchowitz, Mahdi Soltanolkotabi, and Ben Recht. Low-rank solutions of linear matrix equations via procrustes flow. In Proc. Int. Conf. on Machine Learning (ICML), pp. 964-973. PMLR, 2016.
Alex Wang, Yada Pruksachatkun, Nikita Nangia, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel Bowman. SuperGLUE: A stickier benchmark for perrroe- language understanding systems. In Proc. Neural Information Processing Systems (NeurIPS), volume 32, 2019a.
14

---

Published as a conference paper at ICLR 2025
Alex Wang. Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel R Bowman. GLUE: A talk benchmark and analysis platform for natural language understanding. In Proc. Int. Conf. on Learning Representations (ICLR), 2019b.
Shaowen Wang, Linxi Yu, and Jian Li. LoRA-GA: Low-rank adaptation with gradient approximation. arXiv:2407.05000, 2024.
Rachel Ward and Tamara Kolda. Convergence of alternating gradient descent for matrix factorization. In Proc. Neural Information Processing Systems (Neur/PS), volume 36, pp. 22369-2262222 -23322, 2023.
Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou. New bounds for matrix multiplication: from alpha omega. In Proc. of ACM-SIAM Symposium on Discrete Algorithms, pp. 3792-3835. SIAM, 2024.
Wenhan Xia, Chengwei Qin, and Elad Hazan. Chain of LoRA: Efficient fine-tuning of language models via residual learning. arXiv:2401.04155 2024.
Nuoya Xiong, Lijun Ding, and Simon S Du. How weer-parameterization slows down gradient descent in matrix sensing: The curses of symmetry and initialization. In Proc. Int. Conf. on Learning Representations (ICLR), 2024.
Xingyu Xu, Yandi Shen, Yuejie Chi, and Cong Ma. The power of preconditioning in overparameter- ized low-rank matrix sensing. In Proc. Int. Conf. on Machine Learning (ICML), pp. 3861 1-38654, 2023.
Zhenghao Xu, Yuqing Wang, Tuo Zhao, Rachel Ward, and Molei Tao. Provable acceleration of nesterov's 's accelerated gradient for rectangular matrix factorization and linear neural networks. In Proc. Neural Information Processing Systems (NeurIPS), 2024.
Can Yaras, Peng Wang, Laura Balzano, and Qing Qu Compressible dynamics in deep overpa- rameterized low-rank learning & adaptation. In Proc. Int. Conf. on Machine Learning (ICML), 2024.
Haishan Ye, Dachao Lin, Xiangyu Chang, and Zhihua Zhang. Towards explicit superlinear conver- gence rate for sr1. Mathematical Programming, (99())..11999))))))9)))) 199()):123--103,, 2023.
Tian Ye and Simon S Du. Global convergence of gradient descent for asymmetric low-rank matrix factorization. In Proc. Neural Information Processing Systems (NeurIPS), volume 34, pp. 1429- 1439, 2021.
Longhui Yu, Weisen Jiang, Han Shi, Jincheng Yu, Zhengying Liu, Yu Zhang, James Kwok, Zhenguo Li, Adrian Weller, and Weiyang Liu. MetaMath: Bootstrap your own mathematical questions for large language models. In Pruc. Inf. Conf. on Learning Representations (ICLR), 2024.
Rowan Zellers, Ari Holtzman, Yonatan Bisk, Ali Farhadi, and Yejin Choi. Hellaswag: Can a machine really finish your sentence? arXiv: /et..090500000 000000 2019.
Fangzhao Zhang and Mert Pilanci. Riemannian preconditioned LoRA for fine-tuning foundation models. In Proc. Int. Conf. on Machine Learning (ICML), 2024.
Jialun Zhang, Salar Fattahi, and Richard Y Zhang. Preconditioned gradient descent for over- parameterized nonconvex matrix factorization. In Proc. Neural Information Processing Systems (NeurIPS), volume 34, pp. 5985-5996, 2021.
Qingru Zhang, Minshuo Chen, Alexander Bukharin, Pengcheng He, Yu Cheng, Weizhu Chen, and Tuo Zhao. Adaptive budget allocation for parameter-efficient fine-tuning, In Proc. Int. Conf. on Learning Representations (ICLR), 2023.
Sheng Zhang, Xiaodong Liu, Jingjing Liu, Jianfeng Gao, Kevin Duh, and Benjamin Van Durme. ReCoRDD: Bridging the gap between human and machine commonsense reading comprehension. 1810. /2885, 2018.
Susan Zhang, Stephen Roller, Naman Goyal, Mikel Artetxe, Moya Chen, Shuohui Chen, Christopher Dewan, Mona Diab, Xian Li, Xi Victoria Lin, et al. OPT: Open pre-trained transformer language models. arXiv:2205.. 005.0/068. 2022.
15

---

Published as a conference paper at ICLR 2025
Jiacheng Zhu, Kristjan Greenewald, Kimia Nadjahi, Haitz Sáez de Ocáriz Borde, Rickard Brüel Gabrielsson, Leshem Choshen, Marzyeh Ghassemi. Mikhail Yurochkin, and Justin Solomon. Asymmetry in low-rank adapters of foundation models. In Proc, lnt. Conf. on Machine Learning (ICML), 2024.
16

---

Published as a conference paper at ICLR 2025
Supplementary Document for "On the Crucial Role of Initialization for Matrix Factorization"
Contents
Missing details
18
A.I More on related work
18
A.2 LoRA for linear models as Asymmetric matrix factorization
18
A.3 More on NoRA and NoRA+
19
A.4
Initialization without knowing A
20
A.5 ScaledGD as new matrix factorization for asymmetric problems
20
A.6 Additional discussions
20
B Missing proofs for symmetric settings
21
B.1 Initialization of exact- and under-parametrized problems
B.2 Missing proofs for the symmetric and exact-parametrized setting
21
B.3 Missing proofs for the symmetric and under-parametrized setting
B.4 Symmetric and over- pece-arametrized setting
26
Missing proofs for asymmetric settings
28
C.1 Missing proofs for asymmetric and exact- ssact-parametrizee setting ................................
28
C.2 Missing proofs for asymmetric and under- saller--rrametrieee setting
30
C.3 Asymmetric and over-parametrized setting
30
D Other useful lemmas
31
Missing experimental details
E,1 Details for problems with synthetic data
32
E.2 Datasets
32
E.3 Details for Fig. 2
33
E,4
Few-shot learning with OPT-1.3B
................................
34
E.5
DreamBooth with stable-diffusion
34
E.6
Commonsense reasoning with LLaMA and LLaMA2
34
E.7
Math reasoning with Gemma-7B
34
17

---

Published as a conference paper at ICLR 2025
A MISSING DETAILS
A.1 MORE ON RELATED WORK
Convergence of over-paramelrized matrix factorization problems. Consider again the asymmetric problem as an example, i.e., m |XY - A with A E TR X E TR and Y E RR wver-parametrization refers the case where rank( A) over-parametrized problems, where r 2 max J. is studied in (Tarmoun et al., 2021). There are also papers (Stöger & Soltanolkotabi, 2021; Zhang et al., 2021; Xiong al., 2024) considering the matrix sensing problem, which partially relates to our problem when there are sufficient Gaussian measures. The work of (Arora et al., 2018) considers deeper problem (i.e., having more than layers) while assuming A is full rank. Our results on over-parametriization can be found in Apdx. B.4 and Apdx. C.3 for symmetric and asymmetrie problems, respectively. The comparison of ScaledGD with other works on over- wver-parametrized problems can be found in Tab. 1.
The gradient flow on the extreme
Convergence of quasi-Newton methods. ScaledGD is sometimes regarded as a quasi-Newton method (Tong et al., 2021) for our nonconvex objective (4). Since much of the existing work on this topic focuses on the smooth and strongly convex case, we briefly review these approaches to highlight the significance of our results in achieving quadratic convergence for nonconvex and local-smooth problems. In the smooth and strongly convex regime, the primary advantage of quasi- Newton methods lies in their asymptotic ability achieve super-linear convergence Non-asymptotic analyses demonstrating super-linear local rates have only been established recently; see, e.g., (Rodomanov & Nesterov, 2021; Jin & Mokhtari, 2023; Ye et al., 2023; Jiang al., 2023c).
- oo.
LoRA and parameter-efficient finetuning, LoRA (Hu et al., 2022) is notable example of parameter- efficient finetuning (PEFT) approaches. The goal of PEFT is reduce the resource requirement for finetuning LLMs on downstream tasks. Other commonly adopted PEFT methods include, e.g., adapters (Houlsby al., 2019) and prefix tuning (Li & Liang, 2021). There are also various efforts to further enhance LoRA via adaptivity (Zhang et al., 2023), chaining (Lialin et al., 2024; Xia et al., 2024), low-bit training (Dettmers et al., 2023; Li et al., 2024b), regularization (Li et al., 2024a), modifications for long-sequences (Chen et al., 2024), weight decomposition (Liu et al., 2024), and combining with sparsity (Nikdan et al., 2024). Additionally, there are several approaches aiming at further reducing the number of trainable parameters in LoRA; examples include (Kopiczko et al., 2024; Lingam et al., 2024; Gao et al., 2024; Zhu et al., 2024; Hao et al., 2024; Balazy et al., 2024). While originally designed for finetuning LLMs, LoRA also finds its applications in other domains, such as image generation (Gu et al., 2023) and continual learning (Smith et al., 2023).
LoRA initialization. When first proposed, LoRA initialization was largely overlooked. The work of (Hayou et al., 2024) justifies that whether setting X, or Yo to be 0 affects performance from a stability perspective. Recent works (Büyūkakyūžz 2024; Meng et al., 2024) observe fundamental difference between initialization of LoRA and neural networks, emphasizing the availability of prior knowledge, These works experimentally demonstrate that pretrained model can serve as prior guide the direction of adapters, and hence perform QR or SVD on the pretrained matrix and using (scaled) top-r singular vectors for LoRA initialization. Follow-up study (Wang al., 2024) exploits stability for further improvement. However, these initialization methods are computationally expensive and lack flexibility for deployment. The proposed NoRA initialization overcomes these limitations.
A.2 LORA FOR LINEAR MODELS AS ASYMMETRIC MATRIX FACTORIZATION
We argue that LoRA applied on linear models given whitened dataset is equivalent to the asymmetric matrix factorization problem. The whitened dataset is widely adopted for theoretical analyses, and we refer to (Arora et al., 2018; Jiang et al., 2023a; Yaras et al., 2024) for more details.
Assume that we have a pretrained (linear) model Wo E mm Applying LoRA on this layer with whitened data B is equivalent to solving the following problem
IlW + XY - BIF
(8)
It is clearly that this problem (8) is the same (4) by setting A = W
Unfortunately, existing works provide no theoretical support on the most widely adopted initialization
approach for LoRA in practice either X, Yo is chosen as 0 to preserve W. X, W..
18

---

Published as a conference paper at ICLR 2025
Algorithm NoRA for spe-
Algorithm NoRA+ for specific LoRA layer
cific LoRA layer
1: Initialize: ç standard deviation of random matrix Ω2; X numerical stability of matrix inversion 2: Set X, and y, via Nyström initialization (5)
1: Initialize: standard
deviation of random ma-
trix 52
do 4: Get gradient Gx, and Gy,
for .,...,
2: Set Xo and Yo via
Nyström initialization (5)
if > 0 then
3: Standard training process
6:
Gx, + Gx, ( AI,
7: end if
8: Gy, <-
X,
+ AI -1,)-
9: Optimizer update
10: end for
In this sense, our Nyström initialization in (5) is the first means of initialization that justifies one variable can be set to O.
Additional similarities between LoRA and matrix factorization. LoRA and matrix factorization share similar mathematical properties. For example, they both have no spurious local minima (Du al., 2018; Ge al., 2017: Jang et al., 2024). There are also recent efforts using insights from matrix factorization to further improve LoRA; see e.g., (Yaras et al., 2024; Nikdan et al., 2024).
A.3 MORE ON NORA AND NORA+
As discussed in Sec. 4, LoRA can significantly benefit from the aligned directions at initializa- tion. Besides the theoretical benefits of applying Nyström initialization ScaledGID (NoRA+), Nyström initialization can also be used directly with Adam (or Adam W), i.e., NoRA. There are several reasons for this. First, directional alignment from initialization is beneficial to most optimizers. While our theoretical results focus on ScaledGD, we believe that the aligned directions also improve GD. Despite the improvement may be less significant in ScaledGD, we conjecture that the linear term in (Ye & Du, 2021, Theorem 1.1) can be removed with Nyström initialization, because it can be roughly understood as the price of searching for proper directions. In other words, the benefits of Nyström initialization extend to other optimizers as well. Second, Adam also affords an explanation of preconditioning, and the preconditioner for X, is also closely related to Y,. In other words, Adam shares similarities with ScaledGD in (6). These two reasons prompt the proposed NoRA, as summarized in Alg. 1. For NoRA+ in Alg. 2, we modify the vanilla ScaledGD iterations in (6) with two add-ons. First, small parameter À is introduced for numerical stability of matrix inversion. This is a standard practice for numerical optimizers such as Adam (Kingma & Ba, 2014; Loshchilov & Hutter, 2017). Second, the gradient is normalized by the Frobenius reason is that an optimal À is difficult to tune as shown in (Zhang & Pilanci, 2024), where they use from 10 6 to 100. With this normalizer, we can set À 10-6 in all our experiments without any tuning. Moreover, this normalizer is useful to prevent the instability in earlier iterations due to the non-invertable Y,-
of its preconditioner. The
Deployment efficiency of NoRA. One benefit of NoRA (as well as NoRA+) is that it can be deployed jointly with adapters trained with LoRA- and hence there is no need modify the current pipeline for deployment. This is because both of NoRA and LoRA do not need to modify the pretrained parameters, and the finetuned model just Wn + Y where Wa is the pretrained model, and Xr and YT are finetuned adapter weights. On the contrary, other initialization approaches such as PiSSA and OLoRA (Meng et al., 2024; Büyükakyüüz, 2024) are less efficient for using jointly with LoRA deployment because both approaches modify the pretrained weights, that the finetuned model becomes Wi + Xr YT, where Wo W. X, Y The use of Wo comes from the fact that initialization in PiSSA and OLoRA does not satisfy X, Y J O. Consequently, when deploying PiSSA jointly with LoRA, one needs to store both Wo (for LoRA) and Wo (for PiSSA), leading to reduced memory efficiency.
19

---

Lower computational complexity than SVD in certain regime. Observing that the computation for (6) mostly arises from matrix multiplication, whose complexity can be reduced with state-of- the-art algorithms (Williams et al., 2024; Alman et al., 2024). In particular, multiplication of two square matrix of size n X n can be done with complexity 2 To apply this on ScaledGD in (6), can pad the rectangular matrices with 0 to make them square. Simple calculation shows that when r > Onn0.35) ). the complexity is lower than truncated SVD. Additionally, our derivation does not account for the sparsity of the padded matrices, suggesting that the theoretical Published as a conference paper at ICLR 2025
A.4 INITIALIZATION WITHOUT KNOWING A
In certain scenarios, direct access to in problems (1) and (4) may not be available. Nevertheless, the Nyström initialization remains applicable, as it can be derived from the gradient, which is the minimum requirement for gradient-based methods. We take parattrrratttinniioon as an illustrative example. For the symmetric problem (1), Nyström initialization (3) can be obtained from the gradient Ω2 i.e., Go = (2S A) and set initialization as X Go + ΩN T Ω. Similarly, for the asymmetric problem (4), our Nyström initialization in (5) can be obtained via the negative gradient at X and Y 5
A.5 SCALEDGD AS A NEW MATRIX FACTORIZATION FOR ASYMMETRIC PROBLEMS
The one-step convergence of ScaledGD for asymmetric matrix factorization (4) can be interpreted as a new method to factorize matrix A. Taking the exact-parametrizee case as an example, this new factorization induced with ScaledGD in (6) has several computational benefits.
computational complexity could be further reduced.
Potential acceleration with GPUs. Note that the computational pattern of (6) enables it to embrace hardware acceleration provided by e.g.. GPUs. In particular, (6) extensively uses matrix multiplication, and there is no vector operation. This is in stark contrast SVD, which needs sequential householder transformation. Such sequential operations of SVD is often performed on CUDA cores, while (6) can be done Tensor cores (suitable for matrix multiplication). This enables (6) to enjoy the massive benefits of Tensor core, such as computation with mixed precision, and significant throughput improvement (roughly 15x on H100).
A.6 ADDITIONAL DISCUSSIONS
An alternative interpretation of our results. Our theoretical results can also be interpreted as emphasizing the importance of identifying the correct directions when optimizing functions with fourth-order growth. In the matrix factorization and sensing literature, it is common for algorithms such as GD or ScaledGD to exhibit two-phase behavior: an initial phase of selecting the correct direction (also known the spectral phase), followed by second phase of rapid (c.g., linear) local convergence. Our findings clearly indicate that the correct directions in the first phase are critical not only for faster termination of this phase, more importantly, for exponentially impacting the convergence rate in the second phase of ScaledGD.
Future directions. Our findings present several avenues for further exploration. From theoretical standpoint, this work focuses on the impact of initialization in canonical matrix factorization problems. We believe results can be extended more complex settings, such matrix sensing and tensor factorization, which are part of our future research plans. On the practical side, our work hints at the potential for further gains by leveraging priors embedded pretrained weights within the context of Burer- Monte-ro factorization with LoRA. Investigating how to better uncover and utilize this hidden information another attractive direction for future research.
hhttps://www.t 1su edu.edu//i www..eddd/kpppeee /oppe/ / http://w.a....accoooo/oo///////a wtpppettttappppppppp.....e.
20

---

Published as a conference paper at ICLR 2025
B MISSING PROOFS FOR SYMMETRIC SETTINGS
B.1 INITIALIZATION OF EXACT- AND UNDER-PARAMETRIZEE PROBLEMS
B.1.1 PROOF LEMMA
Proof. Let the compact eigenvalue decomposition A be = QEQT, where Q E mRxr and Σ E RrAXrA, We then have that
X = (Q))
(9)
is not hard verify that the matrix T Rra x is also Gaussian random matrix, where each entry follows (0, (2). Applying Lemma 19 on Q T Ω2 it can be seen that
P (Q Ω)) ST(VrA ST(JAA-Vr-)) v)- (CIr) te Cara = E
where C₁ and C2 are universal constants independent of F and r. This inequality shows that with probability least 1 8, or 52) {T(TTA 11.
Note that inequality min (CD) 2 min (C)omin (D) holds given full column rank of C: see Lemma 17. Applying it to (9), we have that
or (Xo) Z Ora (QE)o, = or (A)o,
(2) -T(VTA- - 1)=,)o,,AA)
where (a) holds with probability at least 6.
B.2 MISSING PROOFS FOR THE SYMMETRIC AND EXACT-PARAMETRIZED SETTING
In the exact-parametrized setting, it is convenient to define
B == P
(10)
where P, E IR"X* comes from Lemma 2, i.c., X, QØ, The notation B, will be used frequently this subsection. With the help of Lemma 2, B, can be understood as the "core" part of X,X, because X,X, Q o Q QB, Once proving Lemma 2, it allows us to study dynamics using a simpler but equivalent notion B. F||F, i.e.
X,X, - AlIF " Σ)Q ||
P. - EF B, -E
B.2.1 PROOF OF LEMMA
The proof relies on B, defined in (10). We will prove this lemma by induction. Since Xn AΩ in Nyström initialization, have that 4. EQ Ω. Moreover,
Proof.
base assumption o, > is true because rank(B,)) = rank(X,, X = r, which is the result of Lemma 1.
For induction, assume that X, be written X, Q with full rank + E Bexr at iteration t. By the update (2), we have that
X = X, (X,x xx,
QΦ, (, Σ)Q Q Q QΦ.)
Q
④; 11 () 2,)
(1I)
(b) Q (1 n) p. ET
where (a) uses QTQ = I,; and (b) uses Φ is full rank (hence invertible). Note that Q and share the same column space. This proves the first claim i) of this lemma.
21

---

Published as a conference paper at ICLR 2025
Next show that the smallest eigenvalue of Bt+1 is bounded away from 0 equivalently, D1+1 is full rank. To start with, we have that from the expression of Φ(+1 in (11),
B 11+1 1 & 1 (1 - , $ 2ny 7) + _
T Φ
(12)
= (1 BB + 2n - 7) 7 E
Note that B is PSD matrix by definition (hence the eigenvalues and singular values are the same). To see the smallest eigenvalue of Br+1 is lower bounded, we will apply Lemma 15 on (12) twice, i.e.,
or (B++1)
2 21(1 1),, + or ( (1-11) r)) 1/" EB, '
(0)
(4)
- 2n(1 - 1100 (2) + (1 - 11) (B.)
(13)
(c)
1 - (1 22)22
2 (1 (1) 2)) or (Bn) + 21y(1 0)
211 172
2 (1 20 σr (Ba) (1- n), (1- n)) 0 (E),
where (c) and (d) are because of Lemma 15; (e) is by unrolling or (B,) using (d); and (f) is by
2n 2 1. Combining (11) and (13) concludes the induction.
2n
B.2.2 PROOF OF THEOREM
Proof. The proof is by combining Lemmas 7 and 8.
Lemma 7 (Phase I. Linear convergence to near optima). Let O 3 AA
1
Afte O (I12/Flogm n)
iterations, ScaledGD (2) with Nyström initialization (3) ensures that | ALIF S 0(1/k²²)
Proof. Subtracting E from both sides of (12), can obtain that
B - Σ = (1 - -)) - Σ) u 'I.
This implies that
[B4+1 El|F
(1 7)²| - Σ| + 7
|||
n21 EB 1|2 |
(1 - I)) - Σ| + 7
Σ F +
|
B
E|F
< (1 1)) [B, Σ + > Σ F +
2
[Σ)
o, (B.,
where (a) is by | < |M|| | and (b) follows from the sub-multiplicity of -
By Lemma 2, if 1 S 2/3 and there exists Tj such that (,BBr, 2 o,.(%//3, then it holds that o, (B,) > 0, (E)/3 Vt Ti. According to Lemma 1, we can choose & in (3) sufficiently large such that or (Bo) 2 /3)3,, i.c., Ti = O. Alternatively, to avoid such a requirement on E. we can simply choose a constant step size, e.g. 17 = 0.5, and run a constant number of steps, Ti 0(1/n), to ensure o, (Br,) 2 a, (E)/3 see Lemma 2. For simplicity of the results, our proof below goes with the first method, i.e., Ti- =0
[B Σl[F
0
(E)
E|
$ (1 - n)) |B, Σ| +
(B.)))
Σ Σ
$ (1 m) [ Σ
+
371"
(x(2)
(c)
$ >>|EE|F 3 E|1F + (1 - (1- -
By; Σ|[F
>/|A||
37yl5
A
|F
(1
-
-
Br, Σ F
22

---

Published as a conference paper at ICLR 2025
where (c) is by Lemma 14. From this inequality it is not difficult to that once 7) O ạ
one will have [B41 - E I (11/k²) within the stated iterations.
Lemma 8 (Phase II. Quadratic convergence to global optima), Ie choose lj = 0.5 and suppose that after T2 iterations, or (Br,) ) 2 ( and [Br, Σ 2/3k²) are satisfied, ScaledGD then ensures that for any t 2 T2.
4 1
X A [Bt41 E,11F S
3x.² 22
Proof. Let C, = = BB, We can rewrite (12)
C.+1 = (1 - C) + 2n - 1),, + +
Subtracting I, and rearranging it, we arrive at
C.+1 - I, = (1 2n) CC I,) + 1/ C2 (C, -,)²²
By choosing 7 0.5, we have that
C++1 1 4
C, CC, 1,)
Multiplying both sides with E, we have that
B++1 E = } EB, ECC I(C,-I,)(C) I,)
EB. (B,-EE- -E).
This implies that
BB41 EllF <
B,
|2
Σ| ||2 B: Σ|
(a) 0 (Σ)
(b) 3x²
|B. Σ1
J Σ
4 o
where (a) is by Lemma 2, i.e. once o,
(B o,
a, / then or (B,)) 2 0r EE)3 holds for all
t2 T3; and (b) is by σ (E)- and o, ( 1/K.
Finally, applying Lemma 16, can be seen that quadratic rate can be established long as | Elle 3. and this condition is satisfied from Lemma 7.
B.3 MISSING PROOFS FOR THE SYMMETRIC AND UNDER- PARAMETRIZED SETTING
We start with some notation that would be helpful for this subsection. Let the compact eigenvalue decomposition of A QEQ T where Q RmxrA, and
Rrax
In Lemma 4, we will prove that X, Q always holds if we employ Nyström initialization and ScaledGD in (2), where 4, E Rraxr, We also denote θ == +b ( x.)) -1 where the invertibility of (Φ) Φ.) will become clear in the proof.
Lastly, let B == T Σ & Note that B, E R and B, X AtX,
B.3.1 PROOF OF LEMMA
Proof. We start with rewriting A,
Σ,
0
Q
A [Q,, Q2
Q + Q2E
(14)
0
Σg
Q
where QI E mxx and Q2 E (
-) are the first r and other columns of Q, respectively; and Σ E Rr and Eg E (((-rA) are diagonal matrices formed by the first r and the rest diagonal entries of E.
23

---

Published as a conference paper at ICLR 2025
It is difficult to see that the optimal solution of (1) X, = =QIE//TT where U E Rrx is any unitary matrix that accounts for rotation. Note that the pseudo-inverse of A can be written as A QQ-1QQ Plugging X. into the definition of weak optimality, we arrive at
A
Q + Q2 ) 2
where in (a) use the facts Q Q1 L, and Q1 Q2 -0x((r--)- This concludes the proof.
B.3.2 PROOF LEMMA
Proof. The proof is based on induction. First we have that X = AΩ QEQ S2. is clear that
2o EQ S. Now suppose that one write X, Q following the update (2), it is not hard to see that
4 p++1
4. 1,(
Σ D. 2.)
= - 1) +
+,,
7
D
Φ D
(15)
The variable θ RR can be roughly viewed as a pseudo-inverse of Φ because Φ O I,. We note that the invertibility of (Ø, 4;)) will become clear in Lemma 9.
B.3.3 PROOF THEOREM
Proof. Using $ O I, definition of B, = .b. --1 1b, (at the start of Apdx. B.3), and the update of 4141 in (15), it is not difficult to verify that
B++1 (1 17) ',, + 2n(1 1))1, + 1/00 DO
(16)
Subtracting I, on both sides of (16), get
B B I, = (1 1)) I,, - 1, + 1 De.
This ensures that
B I,lFF
< (1 - [ I,|| + '/2 + 0 E0,|F
< (1 2 LL 17 Vr + 17² (,,
where the last inequality is because of Lemma Suppose that 1 S 2/3, from Lemma 9, one can see that there exists a time Ti such that o, (B,) > 1/3, Vt Ti. We assume Ti 0 following the same argument (i.c., initialized large with large ( as previous proofs. With these arguments, we obtain that
BB I, l|
<1 11) [B, - I, + + 12 + 3rn
(17)
< ///F+ + 3/p + -1-1)) (1-1)++1-7) Ti
Br, - 1,
/VF 3rp (1 +1 Br, - I,
This implies linear rate, i.e, BB41 1, O(r)) + cf 0(1) with sufficient iterations.
Inequality (17) also implics that choosing n = O(c/r), [B - I,lFF S e at a rate O log !). The proof is thus completed.
B.3.4 PROOF LEMMA
Proof. We start with notation. Let
Σ
M,
Σ
4,
(18)
Σ
[,
24

---

Published as a conference paper at ICLR 2025
where Σ₁ R is the learnable eigenvalues, while Σσ (=(a--))((ra-)) are the unlearnable eigenvalues, and M, E IR"x" and N; E R(ra-r)xr, Ideally at global convergence, we hope that
M. || up to rotation; while N; + O.
We consider a scenario with f + oc, i..., é - 0 and B, = L,. Using (18) to rewrite B, = I,, we have that
M2 M. + L, = I.
(19)
The above equation implies that
Tr(M, E M,) Tr(M Σ 1/2 Σ 2/ M,)
(20)
= =|= 1/2 Mcll (a)
S
where (a) is by (19) and Lemma 18.
Since we hope 2; 1/2 M. + I,,, we have that
|Σ 1/2
122 M, - 1
(E) 1/2 M. (E, 1/-1/2M 1,))
Tr
Tr(M, M 1/2 11220 //- M,) + Tr(I,) - 2TT((M 2T 13)
(21)
Tr(M, Σ -/ M, Tr(I,) + 21
M,)
1r 2r + 3/2
where (a) is because that i) for any r x r matrix C, we have that Tr(C) 2 rmnn C₁2 2 -r. ii)
take C M 2, 1/2 and then apply (20); and (b) is by (20).
To bound N,, it can be seen that
(A) TrNN, N.) S TTN (c)
1
S
(22)
where (c) is by applying Lemma 18 on (19). This suggests that |N |l S Vror+1(A).
Lastly, note that X, can be written as X, Q/ To and X, Q Using this fact and combining (21) and (22), we have that
XX x. |
MM
///2 |N
/| 1/2 1/2 I.) |N
(23)
- <> 13// /3 1/2 - I, + ||
063322)
where we used (E) 1 and 0r
Σ < 1. The proof is thus completed.
B.3.5 USEFUL LEMMAS FOR SYMMETRIC AND
PROBLEMS
It is clear that B, symmetric by definition, i.c., B, T. --I--6 1, This enables us give lower bound on o, (B,) using Lemma 15.
Lemma 9. o, (B,) is lower bounded by
o, (B++1) 2 (1 - (1 (1-n))2t4 2)2243 3 (1 2142 or (Bo).
25

---

Published as a conference paper at ICLR 2025
Proof. Given the definition of B,, it is not difficult to see that B, is PSD for all t. We can then apply Lemma 15 on (16) to arrive at
o, (B(11)
2n 11) + or (1 - 1)) B, , 20,)
2n(1 -1)) + - n))²) (B.)
(1 m) 22 or (Bu) + 27y(1 - 11) - (1 - 17) 1))22+2
2mj 172
(b) (1 1) ) o, (Bo) + (1 7) - (1 21+3
where (a) uses Lemma 14 to unroll or (Br); and (b) is because 2n
2n 1.
1
Lemma 10. Let O and B, defined the same as those in Apdx. B.3. It guaranteed to have that
| No, |F o, (B.)
Proof. Using the inequality
||A ||AA < | we have that
O 0 || ||@ / O s //11/2.111..
(24)
Now let E,
1 and F, == Σ - 1/2 Since we have that F, Eg Iy,, we have that
FF E, |||||| VT.
Since we also have that
v== | EcllF 2 or, Erl (b)
(a)
(25)
where (a) holds because E, and F, share the same column space and row space and both of them have rank which implies that (Null(F), [E]],) 0, vi (E,); is the ith column of E,). Note that (a) does hold true for general two matrices E, and F,. (b) is because F, F, B₁, which means that the singular values of F, are just square root of eigenvalues of B, This implies that |ElllF S
(B,). Combining this inequality with (24), we have that
||l NO, S ||0, //2 = E.ll < o, (B.)
r
The proof is thus completed.
B.4 SYMMETRIC AND OVER-PARAMETRIZED SETTING
Nyström initialization for over-parametrization. While the initialization still follows (3), we need to adapt Lemma 1 to the over weer-parameterized setting, i.e., rA-
Lemma 11 (Initialization for over-paramettizzatio)) There exists universal constant T > 0 such that ora (Xp) 2 {T(VT Vra 1)0,, (A) is satisfied with high probability. other words, rank X = FA w.h.p
Proof. Similar to the proof of Lemma 1, let the compact eigenvalue decomposition of A be QEQ where Rmxra and Σ A This implies that X, (QE)(Q ?))
is not hard to verify that the matrix Q E Rea xr is also a Gaussian random matrix, where each entry follows (O ) Applying Lemma 19 (Q (2) and using the fact (Q (2) and (Q ?)) share the same singular values, it can be seen that
P Tr (Q
Vra S ST(Vi -raVi-vr--1) 1ra s (C
Car : 82
E
where C and C2 are universal constants independent of A and r. This inequality shows that with probability least 1 o2, or (Q Ω (r(vr Vra T).
26

---

Published as a conference paper at ICLR 2025
Note that inequality min (C)= 2 min min (C)omia (D) holds given full column rank of C; see Lemma 17. Applying it to (9), we have that
Tra (Xo) 2 Tra r (Q (QT = ora (A)or (2)
(0) ET(Vr - VVA 1r. (A)
where (a) holds with probability at least
82.
Next, we provide additional results of Nyström initialization over- werrppaamtrried setting of problem (I), where we have тл < т. For desirable convergence rate, we need to slightly modify the ScaledGD update to
X = X; (X,X; X.)
(26)
Compared with iteration (2) for exact-paramettization, the modification is on (X, X,) This pseudo- inverse is necessary because (X, X,) is not necessarily invertible in the over-parametrize setting. We note that unlike previous work (Xu al., 2023) which modifies the same term to (X, X, + AI)
(26) does not need the damping parameter AI in the preconditioner. We will observe shortly in Fig. that the quadratic rate not achieved with the damping factor.
Let the compact eigendecomposition of A = QEQ for Q E IRIXTA and E E RTAXTa, We can also establish that X, affords simpler representation.
Lemma 12. Under the Nyström initialization (3) and iteration (26), the variable X, can be writlen as X, Q some D, E Rrakr, Moreover, we have that
Φ (1 1--1)) 1) + +))
(27)
Proof. We prove this by induction. Clearly, our initialization satisfies this because X, = AΩ = QEQ TN, i.e., oo == EQ Ω. Now suppose that X, Q holds for t. We then show that X++1 Qd.+1 to finish the induction. In particular, plugging X, = Qd, into (26), we arrive at
E 2.)²
X Q 2. 2
1+1
Clearly, the term inside the brackets 4.41. The induction is thus finished.
Now we proof the second part of this lemma. Let the SVD of $, == U,E, VT where U, E ReAXPA Σ, E R and V, E rxx We note that U, is unitary for this case. With the SVD, have that 4; o U, U.E.U. U. and ($, TF) = V,E, VV. Plugging these into P defined earlier, we arrive
p = +; U.EEU - V,,,,
Φ (U,E; EJU,, V.
Φ n,U, V + +UU 'V.
= (1 - 1, + (
This completes the proof.
Next, let B, 2 With (27) we have that
B (1 1) Φ + 17(1 - 1)) .),
7 ()11)))((())))
Φ. + Φ/Σ
(a) (1 - + 27(1 - - TT
(28)
2
- 21
where in (a) we used the SVD of क; := U.E.V. where U, E ReAXFA, E, Reaxra and V, E RrxrA, Φ = V, and U, is unitary; and in (b) we assume that B, is full rank. Note that this assumption be easily verified given rank(Bo) r and the iteration B, (28) is
27

---

Published as a conference paper at ICLR 2025
1010
10
E= 4n
10c
10c
f= =
f= 5, =0
102
10
10 &, 0.1
-
10 2
100, 5, =
E 100, & 0.1
10-6
GD
10 10
Scaled-GD(A)
10
Ours
10-14
10-14
10
20
30
40
0
10
20
30
40
(a) over-parametrization
(b) over-parametrization
Figure 4: Convergence of ScaledGD under Nyström initialization (optimality error vs. iteration) on over- parametrrieeed problems detailed in Apdx. E.I. (a) Comparison GD, ScaledGD-(A) with small initialization, and ScaledGD with our initialization. (b) Solid lines show that initialization is not sensitive to magnitude; and dotted lines illustrate that quadratic convergence cannot obtained even with slightly perturbed initialization, i.e., Xa- AΩ N, where [N ij (O,
exactly the same as in exact- caatt-parametrized cases (12). The latter allows us to bound σr (B,) away from in the same way as Lemma 2.
In other words, the over-parametrized case under our initialization reduces to the paatt-parametrized case given the same iteration on B, (28) (cf. (12)). This allows as to use the same argument of Theorem to derive quadratic rate for wer-paramettrize case.
Theorem 5. With Nyström initialization (3), the behavior of update (26) can be described as: Phase (linear convergence). Let 0 - After Ti = Ox*² Volog x) iterations, ScaledGD ensures that Xx;X7; A s O(1/k²).
Phase (quadratic convergence). After Phase ScaledGD converges quadratically with = 0.5. In particular, X A < is ensured after T O (1log log( 1t)) iterations.
Proof. The proof is the same as Theorem given the same iteration on B, in (28). We omit it to avoid redundancy.
Numerical illustration. A numerical illustration for ScaledGID under Nyström initialization in pwer-parametrized case can found in Fig. 4. We adopt ScaledGD-(A) (Xu et al., 2023), the damping version of ScaledGD, as another baseline. It can be seen that only our approach achieves quadratic rate; see Fig. 4(a). We also slightly perturb our initialization with small noise, and it can be seen that the quadratic convergence breaks down immediately. This demonstrate the critical role of initialization: i) it helps to get rid of damping using pseudo- igeudo-invers;; and ii) it ensures quadratic rate.
C MISSING PROOFS FOR ASYMMETRIC SETTINGS
C.1 MISSING PROOFS FOR ASYMMETRIC AND EXACT-PARAMETRIZED SETTING
C.I.1 PROOF OF LEMMA
Proof. The proof is finished by induction. From Nyström initialization, one has that w 0 and Φ ΣV I Ω. Now assume that one can write X, U and Y, VV, for some iteration t.
We will show that X U and Y V 1 under iteration (6). Let us start with X,+1-
28

---

Published as a conference paper at ICLR 2025
Note that if = 0, X U$, is trivial. We only focus on f 2 1, where we have
X = X, x (X,
UΦ: 77 (U v. V UEV VV V V
UΦ n,U V ( .
U Φ 17 Φ E V
Note that the invertible of ( v.) will become clear in the proof of Corollary 1. Using similar argument, it hard to show that Y. V for all t. We do not repeat here.
C.1.2 PROOF OF THEOREM
Proof. Based the initialization (5) and iteration (6), can obtain that
$ Do
(29a)
1 = v = 0 V (0- A)
U $ U
Ub))
V VEU V (
(29b)
This ensures that
Φ V =nE.
Choosing completes the proof.
C.1.3 PROOF COROLLARY 1
Proof. The corollary is proved through an syymmetric-t--symmeett reduction.
Step 1. Positive definiteness of o VTT We will first show that &, V is symmetric and positive definite (PD) for any t 2 From the proof of Theorem 3, it can be seen that Φ Lt n is symmetric and PD. This means that the base case of induction holds. Now suppose that $, v is symmetric and PD) iteration Based on Lemma 6, we can write the iteration as
Φ (1 .1)) 1
(30a)
4+1 = (1 (1- EΙ
(30b)
This gives that
11 T ++ (1 17) P + 2m n) "
(31)
The symmetry of ..+1 v 1+1 directly follows from (31). For the positive definiteness of Φ we can apply Lemma to get
/+11
Amin
(+1) 2 (1 2) Xmin (. + 21y(1 11) Amin (2) + Xumin D( -'E) 0.
This concludes the PD of D 1 V ITI--
Step 2. Define B, = Φ, v then (31) can be rewritten as
B+i (1 " 27 7)
(32)
which is exactly the same iteration as (12) for the symmetric exact- parametreedd case. Based on the results from Step 1, that is, P V [ symmetric and PD, we can apply the analysis steps for symmetric parametzreee problems, ie., Theorem to get the bounds stated this corollary. We do repeat for conciseness.
29

---

Published as a conference paper at ICLR 2025
C.2 MISSING PROOFS FOR ASYMMETRIC AND UNDER-PAREE PARAMETRIZED SETTING
C.2.1 HOW GOOD IS WEAK OPTIMALITY?
Lemma 13. Every global optimum for (4) is also weakly optimal.
Proof. We start with rewriting the SVD of A = -UEV
as
E1 0
V V = U + U2EVV
A = U1, U2]
(33)
Σ
where U1 E RR and U2 Rmx(ra-F) are the first and other columns of U, respectively; Σn Rrxr and Σg ((r-Ta)((o-AA) are diagonal matrices formed by the first and rest diagonal entries of Σ; and V _xxr and V2 E R=x(ra-r) are the first and other columns of V.
It is not hard to see that the optimal solutions of (1) are X. U ,, / Q and Y. Vi 2 QT where Q E Rgrx is any invertible matrix. Using these notation, we have that
A
Q- / VI U. V2 U QQ
(a) I
where in (a) the facts U
U1 U,U,
I, and U, U2 0 -x((ra-))- This concludes the proof.
C.2.2 PROOF OF THEOREM
Proof. The update in (6) ensures that
Φ = 2
(34a)
V V - v/ -
( A) U (U U2))
7/ V UU)
(34b)
T 20)
where in (a) we define θ = Φ ( -1
From the Definition 2, we can see that
Y v T VU--UU-TT Up. VIrID
= 0 ΣΣ ΣΣー = 1,I,
This means that when 7) 1, generalized weak optimality can be achieved in one step for under- parametrized problems.
C.3 ASYMMETRIC AND OVER-PARAMETRIZER SETTING
Next, we establish the one step convergence with Nyström initialization the asymmetric over- parametrized setting, where F' We also need to slightly modify the ScaledGD update to
X, X., and X = X, - (XYY YY, V- Y. Y - A) (X, X.)
(35a)
VI 2 0.
(35b)
Comparing with (6), the difference is that here we use pseudo-invers inverse to bypass the possible non- invertibility of (X, X,) and (Y, Y,) in the over- peeepprraetrizeed case. We also note that to the best of our knowledge, there is no previous result that establishes the convergence of ScaledGD (or its variants) for asymmetric perpparaeereized problems.
30

---

Published as a conference paper at ICLR 2025
Theorem 6. Under Nyström initialization (5), the modified ScaledGD iterations (35) converge globally in a single step, i.e., X = =A if the learning rate chosen as = 1.
Proof. Let the compact eigendeecomposition of UEVT for E Rmxra, E graxra, and V E R
The Nyström initialization ensures that X. = X Uoo where Po E Reaxr and clearly
$o EV f. Using the expression of X1, iteration (35) gives that
Y1 V p Po)
Let the compact SVD of L == PDQ T where P E R' DE R' and Q R Note that P is unitary. With the compact SVD of o have that (%) oo) QD Q which implies that
X Y. = nUPDQ QD 2 EV (a) UEV
where (a) because unitary and the choice of r7
D OTHER USEFUL. LEMMAS
Lemma 14. Let Ac+1 (1- with some a E (0, 1) and 3 2 0, then we have
A++1 = (1- Ao + (1
00)+1
0 (1 -1 Ao + 0
Proof.
The proof can be completed by simply unrolling A.41 and using the fact a +..
T-o'
Lemma 15. A RRxn and B IR nxn positive semi-definite matrices, have Awin
B) Amin (A) + Amin (B).
Proof. The smallest eigenvalue of + B can be expressed as
x (A B)x
X Axi
x2 Bx2
Amin (A+B)
min x
min
(36)
x1
x X1
x3 X2
On the other hand, we also have that
Ax1
X, Bx2
Amin (A) + Amin (B)
min
(37)
00x
x x
X2 X2
Because (36) is a constrained version of the minimization problem (37), they share the same objective, but (36) has shrinked feasible region. is not difficult see that Amnin (A+ Z Amin (A) AAmin (B) The proof is thus completed.
Lemma 16, Consider sequence {At} with A, 2 0, Vt. If there exists such that A++1 S aA? and Ao S 2n A, converges a quadratic rate, i.e.,
1
A < a 22'1T
Proof. Unrolling A we get that
1
1 1
A411 < aAf < a A S a A
(aAA))
a 2
The proof is thus completed.
Lemma 17. Let A Rmxn be matrix with full column rank and B B be non-zero
matrix. Let min(()) (.) be the smallest non-zero singular value. Then holds that mmin (AB) 2 Omin A miin (B).
31

---

Published as a conference paper at ICLR 2025
Proof. Using the min-max principle for singular values,
min (AB)
min
||
Bx Bx
min
A
|
min
|All [Bx
||x 1.lyy CCooSppnn B) (yCColpan(())
min
A|
min
[x
min
Ayll
min
[x
|
x (xCCspiCC)
min (A) o min (B)
where (a) is by changing of variables, i.e., y Bx Bx/
Lemma 18. For PSD matrices A and B, + I, then we have Tr(A) S r and Tr(B) S
Proof. The proof is straightforward and is omitted here.
Lemma 19 (Rudelson & Vershynin (2009)). Let W be an d x matrix with d 2 The entries of W are drawn independently from (0, Then for every T > O, we have that
(W) T(Vd V)- (Cir) e -ad
where C1 and C2 are universal constants independent of d and
E MISSING EXPERIMENTAL DETAILS
E. DETAILS FOR PROBLEMS WITH SYNTHETIC DATA
This subsection contains the detailed setup for the problems with synthetic data in Figs, 1 and 4. Recall that here we focus on symmetric problems under exact-, under-, and over-paramelrriation..
For the panettraraettiized problem in Fig. 1 (a) and (b), we choose the PSD matrix A E mm in the following manner. We set m = 1000 and r = TA = 20. The non-zero singular values are set as (1.0, 0.99, 0.98 .... 0.82, 0.01), where intentionally set σr 0.01 to enlarge the condition number. We choose the step size of GD as 0.01 to avoid divergence. The learning rate for ScaledGI) is 0.5.
For the under- laiter--rrmetrizedd problem in Fig. (c), we choose PSD matrix E mm in the following manner. We set (1.0, 0.99, 0.98,... 0.65, 0.64, 0.05, 0.025, 0.01]. We choose r 20 to ensure the under- parametrized nature of this problem.
1000 and TA 40. The singular values of A
For the over- peemmparaetrrized case in Fig. 4 (a) and (b), we choose PSD matrix E mx in the following manner. We m 1000 and MΛ 20. The non-zero singular values are chosen as (1.0, 0.99, 0.98, ... 0.82, 0.01}. where we intentionally set σr, 0.01 to enlarge the condition number. We X to be over-pare rree-paaaetrizeed by letting r 60. We choose the step size of GD as 0.01. The learning rate of ScaledGD-X À is set as 0.5, and its damping parameter À is chosen as 0.01. The learning rate for ScaledGD with Nyström initialization is 0.5.
E.2 DATASETS
The evaluation of NoRA and NoRA+ carried out commonly adopted datasets in the literature.
GLUE benchmark. GLUE is designed to provide general-purpose evaluation of language under- standing (Wang et al., 2019b). Those adopted in our work include SST-2 (sentiment analysis, (Socher et al., 2013)), RTE* (inference). These datasets are released under different permissive licenses.
32

---

Published as a conference paper at ICLR 2025
Figure 5: The dog dataset.
Figure 6: The cat-toy dataset.
SuperGLUE benchmark. SuperGLUE (Wang et al., 2019a) is another commonly adopted bench- mark for language understanding, and it is more challenging compared with GLUE. The considered datasets include CB (inference, (De Marneffe al., 2019)), ReCoRD (question answering, (Zhang et al., 2018)), WSC (coreference resolution, (Levesque al., 2012)), BoolQ (question answering, (Clark et al., 2019)), and MiltiRC (question answering, (Khashabi et al., 2018)). These datasets are released under different permissive licenses.
Commonsense reasoning. These datasets are a collection tasks that require commonsense reasoning to answer. The considered datasets include WinoGrande (Sakaguchi et al., 2021), PIQA (Bisk et al., 2020), SOCIAL-I-QA (SIQA) (Sap et al., 2019), HellaSwag (Zellers et al., 2019), ARC-easy, ARC- challenge (Chollet, 2019) and OpenbookQA (Mihaylov et al., 2018). These datasets are released under different permissive licenses.
Math. For mathematical problems, we consider GSMSK (Cobbe et al., 2021) dataset that consists of high quality linguistically diverse school math problems created by human problem writers. This dataset is under MIT license. We also adopt MetaMathQA dataset (Yu al., 2024), which is constructed through bootstrapping mathematical questions by rewriting the question from multiple perspectives. This dataset under MIT license.
Additional datasets. We also use SQuAD (question answering, (Rajpurkar et al., 2016)) in our experiments, which released under license CC BY-SA 4.0.
Datasets for DreamBooth. The datasets (dog and cat-toy) used for Sec. 5.2 are obtained directly from Huggingface. The dog dataset' contains dog images; see Fig. 5. The cat-toy dataset has 4 images; see Fig. 6. Both datasets representative examples for the purpose of DreamBooth finetuning with only few images for personalized generalization.
E.3 DETAILS FOR FIG.
The experiment setting and training protocols the same few-shot learning with OPT-1.3B in the following subsection. Here, we are interested in the change of singular values after LoRA finetuning. For each LoRA layer, compare the singular values of W, and W, + YT, where X Y, LoRA weights after training, and find out the indices of r singular values that have the largest change after finetuning. We then count the indices across all LoRA layers. Fig. 2 plots indices counts.
hntrps://huggiiggface. wttp://aaaststt//eo wtdddfffuuusfso/ooeooe df thttps://muggiinggfac..oo http:/aaaa..ccoaaattteteeteeeeee ffusers/cat
33

---

Published as a conference paper at ICLR 2025
E.4 FEW-SHOT LEARNING WITH OPT- 1.3B
For this experiment, we first search for the best batchsizes for LoRA, and the same batchsize is applied for other tested algorithms well. Then we search additionally for the best learning rate for each algorithm. This ensures that different ulgorithms see the same amount of data, while still having their best performed learning rate. The hyperparameters adopted are searched over values in Tab. Adam is adopted for optimization.
Table 5: Hyperparameters used for few-shot learning with OPT-1.3B.
Hyperparameters
Values
LoRA
8
LoRA
16 q proj, v-proj 5
LoRA module epochs batchsize learning rate
2, 4. 8
1x10 5 1x 1x10
NoRA g
0.05, 0.1, 0.2
E.5 DREAMBOOTH WITH -IFFUSION
Stable Diffusion V1.4 (Rombach et al., 2022) adopted base model, where LoRA applied the UNet. The text-encoder is not finetuned. We adopt the default parameter-choie from Huggingface, which is summarized Tab. We adopt AdamW the optimizer with a weight decay of 0.01.
Table 6: Hyperparameters used for DreamBooth with stable-diffusion.
Hyperparameters
Values
LoRA
4
LoRA
4
LoRA module # iterations batchsize
to q. to to v, to out
500
1
learning rate NoRA E
x 10-4
0.1
We provide additional results further support the efficiency of NoRA by finetuning the stable- diffusion-vl .4 model using the same protocol as in Sec. 5.2. Here we adopt dataset with 4 toy-cat images; see Fig. 6. After finetuning 500 steps using prompt "a photo of toy cat", our goal is to generate images "a toy cat wearing glasses." The generated images are shown in Fig. 7. In general, all tested algorithms do not distinguish the hands and the tail toy cat well. However, both LoRA and LoRA-P generate images with less accurate facial details. For example, the glasses not wearing well, or the eyes are not clear. However, the details of faces generated by NoRA and NoRA+ are quite clear.
E.6 COMMONSENSE REASONING WITH LLAMA AND LLAMA2
The base models considered LLaMA-7B and LLaMA2-7B. The experimental setup and choices of hyperparameters follow (Liu et al., 2024). The hyperparameters are summarized Tab. 7.
E.7 MATH REASONING WITH GEMMA-7B
Our last evaluation tackles mathematical reasoning. Gemma-7B (Gemma-team et al., 2024) is finetuned for 2 epochs MetaMathQA- 100K dataset (Yu et al., 2024). LoRA rank is set 32, leading to 100M trainable parameters. The performance assessed on GSM8K (Cobbe et al., 2021), and hyperparameters summarized in Tab. 8.
34

---

Published as a conference paper at ICLR 2025
LoRA
LoRA-P
NoRA
NoRA+
Figure 7: Generated images from NoRA and NoRA+ with stable-diffusion.
Table 7: Hyperparameters used for commonsense reasoning with LLaMA-7B and LLaMA2-7B
Hyper-parameters
Values
LoRA (rank)
32
LoRA a LoRA module epoch learning rate
q-proj, k_proj, v-proj. up-proj, down_proj
3 10-4
batchsize cutoff length NoRA {
16
256
0.02, 0.05, 0.1
The performance of various approaches is summarized in Tab. We also include PiSSA (Meng et al., 2024) into the comparison. Note that PiSSA uses LoRA rank as 64 but is only finetuned for single epoch. Despite this difference, the computational cost on backward passes is the same for PiSSA and NoRA. The results clearly show that NoRA (NoRA+) outperforms LoRA (LoRA-P), highlighting the effectiveness of our Nyström initialization.
35

---

Published as a conference paper at ICLR 2025
Table 8: Hyperparameters used for math reasoning with Gemma-7B.
Values
LoRA r (rank)
32
LoRA
LoRA module
q-proj, k-proj, v-proj, o-proj, up-proj, down.proj, gate-proj
epoch
learning rate
10-4, 4 10 10-4,5x 10
batchsize
128
NoRA
0.02, 0.05, 0.1
Table 9: Performances of different algorithms for math reasoning tasks. The results marked with are taken from (Meng et al., 2024).
GSMSK
LoRA
PiSSA
NoRA
LoRA-P
NoRA+
Gemma-7B
76.72
77.94
78.62
77.03
78.47
36


Reviews:
[{"review_id": "XLwAgr8NC8", "reviewer": "Reviewer_yocf", "summary": "The paper shows that the low-rank matrix factorization problem can be significantly accelerated using a better initialization method. Specifically, the authors introduce the Nyström initialization, which uses a sketching idea to initialize the low-rank factors to be in the appropriate eigenspaces. Then, using Scaled Gradient Descent (ScaledGD), one can obtain quadratic convergence.\n\nThe authors then present Nyström-initialized LoRA (NoRA) and present experimental results that show the practical benefits of using such an initialization compared to using the standard LoRA.", "questions": ".", "limitations": "", "rating": 5, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "On one hand, I feel that the quadratic convergence with the Nyström initialization is significant. I have not directly worked in the area of matrix completion, so I do not have full confidence in this judgment, but this type of quadratic convergence result seems quite important.\n\nAt the same time, however, I'm not quite sure if the quadratic convergence is coming from the scaled GD algorithm or from the Nyström initialization. Since the scaled GD algorithm is basically a Newton update, shouldn't the quadratic convergence happen asymptotically, regardless of the initialization? Is it that the Nyström initialization allows the algorithm to reach the quadratically convergent phase more quickly? Perhaps the authors can clarify this point.", "weaknesses": "On the other hand, I feel that the matrix completion result and the Nyström-initialized LoRA (NoRA) are strongly connected. The theory doesn't apply to the NoRA setting, but I do see that the Nyström initialization is a nice conceptual motivation for a potentially better LoRA initialization.\n\nHowever, now with the flood of empirical LoRA papers, I think the community has a very high bar for recognizing work that purports to improve LoRA in a practical sense. I am not sure if the experimental validations of this work really clear that bar.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Zgwj76TWIM", "reviewer": "Reviewer_FU9i", "summary": "This paper studies the convergence of ScaledGD, a special preconditioned GD for matrix factorization (MF) problems, on symmetric/asymmetric MF problems. The authors show that initializing the factorized model as some random sketching of the target matrix significantly achieves faster convergence. Then, the authors propose to initialize the Low-rank adaptation (LoRA) using some random sketching of the pre-trained weights.", "questions": "See \"Weaknesses\"", "limitations": "", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "Good coverage on matrix factorization problems (symmetric/asymmetric, exact/over/under-parametrization); Writings are clear; Some connection to practical problems.", "weaknesses": "The reviewer has concerns regarding the significance and practical relevance of the theoretical results and the way results are connected to LoRA. Specifically:\n\n1. The matrix factorization problem is not a practical problem to be solved, but rather a problem through which one builds a theoretical understanding of GD and its variants in a nonconvex setting. In this regard, any procedure using the target matrix itself, in the reviewer's opinion, is not allowed: if we know the target matrix, we can directly factorize it (which is why the MF problem is not a practical problem), thus any procedure (other than computing gradient, we are studying GD after all) using some information about the true target matrix is not allowed as it simply moves the factorized model one step closer to the target thus reduce the amount of work GD needs to converge. As such, the crucial role of initialization, as the authors stated, is just taking advantage of knowing the target matrix, which deviates from the original purpose of studying the MF problem: to understand how GD minimizes non-convex objectives even with random initialization. (Disclaimer: This point only pertains to MF problems. For practical problems such as matrix sensing, and matrix completion, the initializations can be special as they are non-trivially improving the convergence of GD)\n\n2. as the reviewer already pointed out in 1., if we know the target matrix, then we can directly factorize it, which is exactly what the one-step modified ScaledGD with Nystrom initialization is doing, so Section 3 is trivial.\n\n3. The connection to LoRA is puzzling in two ways: First, what is proposed is not remotely close to what is theoretically studied, Section 2, 3 studies initialization with the targe matrix sketched. The proposed initialization for LoRA is with the pre-trained weights sketched. Based on this, one should get the conclusion that \"pre-trained weights\" $\\approx$ \"targe matrix\", which is clearly wrong. (Don't get too serious about this argument, the reviewer is just taking the shortcut to make the point). Moreover, the theoretical claims are special initialization accelerates GD, but none of the empirical experiments are about training time. On top of that, the performance improvement from special initialization seems very little to the reviewer.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "GcZ5SrHjCG", "reviewer": "Reviewer_jyg6", "summary": "The current work describes a novel initialization method for matrix factorization problems which accelerates convergence of ScaledGD both theoretically and empirically. The authors also consider extension of Nystrom initialization to LoRA model and shows its superiority compared to different baselines experimentally.", "questions": "1. In Figure 2b, it kind of suggests that smaller $\\xi$ is preferred for quicker convergence? So does it hint that Nystrom initialization benefits from small initializaion as well, which also induces zero saddle point concerns?\n\n2. In NoRA, say we have two pretrained weights $W_0,W_1$ of pretty different magnitudes, does it indicate corresponding NoRA initialization also scales with such magnitudes since $X_\\{0,1\\}=W_\\{0,1\\}\\Omega$? Probably adding certain weight normalization would make the finetuning more stable?\n\n\nminor writing issues:\nline 340: \"modified ScaledGD in (6) have\" should be \"has\"", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The current work studies how initialization affects ScaledGD method in matrix factorization problems, and considers its extension to LoRA model. I personally find the topic valuable. The theoretic bound improvement seems huge for classic matrix factorization problem. For LoRA model, recent work has studied customized optimizers and stepsize scheduler, NoRA proposes a new initialization scheme which has its theoretic grounds. Moreover, compared to PiSSA, NoRA is naturally zero-initialized and is thus a more convenient initialization to LoRA.", "weaknesses": "1. The convergence bound to under-parameterized case involves weak optimality. I'm not very familiar with this notion, the authors show all globally optimal solutions are weakly optimal, is there any intuition of this weak optimality or is it just curated from technical stuff? How larger is the space of weak optimality compared to true optimality?\n\n2. Ideally to apply Nystrom initialization to LoRA, one should learn $\\Delta W$, which suggests that one should know how much weight change is in order to initialize finetuning model, and is thus unrealistic.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "NPUyRIheON", "reviewer": "Reviewer_kgvD", "summary": "This paper considers the matrix factorization problem, where one is given a matrix $A$ and the goal is to compute a rank-$r$ factorization that approximates $A$. It studies the setting when $A$ is PSD and the factorization is also PSD, and when $A$ is not symmetric. Three settings are studied: exact, over and under parametrization, meaning the rank of $A$ is equal, smaller or larger than $r$. Their algorithm is preconditioned gradient, and the key of this paper it show that a good initialization significantly improves convergence rate. The initialization is to set $X_0=A \\Omega$ for a zero-mean Gaussian matrix $\\Omega$. Due to rotational invariance of Gaussian, this initialization has many desired property, such as it aligns with the desired top-$r$ eigenspace. Using this technique, they obtain improved rates for both symmetric matrix factorization and asymmetric variants. They also show a major application for this theory, that is, the initialization for LoRA training. Standard LoRA setting initializes $X_0$ to random Gaussian matrix, and the theory developed in this paper suggests a better alternative is to use $X_0=W_0 \\Omega$ where $W_0$ is the pre-trained weights. Experiments are performed on various few-shot learning tasks on benchmarks to show advantages over LoRA and its variants.", "questions": "What is the role of Gaussian playing in your analysis? To put it in other words, do you think it's possible to replace Gaussian with something that can be applied faster to $A$, or Gaussian is essential for the analysis?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper presents a simple initialization framework for matrix factorization that significantly improves convergence rates, which is to align the principle directions of $X_0$ with $A$ through a rank-$r$ Gaussian. Algorithmically, this does not incur (asymptotically) extra cost as multiplying $A$ with a small matrix is cheap. It also showcases an interesting phenomenon: in the exact parametrization setting, the proposed algorithm has a linear convergence for iterations proportion to $\\kappa^3$, then rapidly switches to quadratic convergence, resembles that of second-order method without explicitly resorting to second-order information. The application to LoRA is nice and natural.", "weaknesses": "I think the paper is overall well-written with no obvious weaknesses. The empirical improvements over LoRA seem rather marginal but I'm not an expert on experiments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)