Introduction

In recent years, there has been a growing interest within the realm of deep learning in overparameterization, which refers to employing a greater number of model parameters than necessary to interpolate the training data. While this may appear counterintuitive initially due to the risk of overfitting, it has been demonstrated to be an effective modeling approach (Zhang et al., 2021;Wu et al., 2017;Allen-Zhu et al., 2019a;Buhai et al., 2020;Xu et al., 2018), primarily attributed to improved optimization landscape and implicit algorithmic regularization. In the context of large language models (LLMs) (Radford et al., 2019;Brown et al., 2020), empirical scaling laws (Kaplan et al., 2020) suggest that larger models are more sample efficient, often requiring fewer samples to reach the same test loss.

Taking the problem of low-rank matrix recovery as an illustrative example, the seminal work of Arora et al. (2019) showed that deeper factorizations better promote low-rank solutions as a function of depth, consequently mitigating overfitting in the overparameterized regime compared to a classical two-layer factorization approach; see Figure 1 (left). On the other hand, increasing the width of each layer substantially reduces the number of iterations to reach the same training error; see Figure 1 (right).

While overparameterization offers remarkable benefits, it also comes with its computational challenges. The significantly increased number of parameters inevitably results in dramatically higher computational costs. This naturally raises a fundamental question: can we attain the benefits of Figure 2. Invariant low-dimensional subspaces in deep overparameterized adaptation of language models. Fine-tuning BERT (Devlin et al., 2019) with deep overparameterized adaptation on the STS-B dataset (Cer et al., 2017). Left: Singular value spectra across all adapted layers at the end of fine-tuning. Middle: Alignment of subspaces formed by top 8 right singular vectors between current adapted weights and final adapted weights throughout training. Right: Training loss continues to decrease in iterations after subspace alignment with final adapted weights. See Section 4 for more details.

overparameterization with a substantial reduction in computational costs?

In this work, we show that we can achieve this by exploiting low-dimensional structures of data and compressible learning dynamics in the model weights. In the context of low-rank matrix recovery via deep overparameterized factorizations, we discover an interesting phenomenon that for each weight matrix, the learning dynamics only happen within an approximately invariant low-dimensional subspace throughout all iterations. We rigorously prove this for deep matrix factorization, which also allows us to compress the number of training parameters significantly when dealing with deep matrix completion. Consequently, we can construct and train a nearly equivalent, yet much smaller, compressed factorization without sacrificing the advantages of its overparameterized counterpart.

Interestingly, we empirically find that the above phenomenon can also be observed when employing deep overparameterized weight updates for fine-tuning language models; see Figure 2 for an illustration. Therefore, we can adapt our idea of compressing deep matrix factorization to improve language model fine-tuning. For fine-tuning large-scale pretrained language models, recently low-rank adaptation (LoRA) stands out as the most commonly-used technique due to its effectiveness and efficiency (Hu et al., 2021). The basic idea of LoRA is to freeze the pretrained weights and adapt each one to new tasks by adding and optimizing an update in the form of a two-layer low-rank decomposition. Nonetheless, in practical scenarios, selecting the optimal rank of the decomposition can pose a significant challenge. If the rank is not chosen properly, it may lead to overfitting, particularly when we overestimate the rank or when there is limited downstream data available.

We deal with this drawback of LoRA by employing a deep (three-layer) overparameterized factorization for the trainable update, which is constructed and optimized via the compression technique used for deep matrix completion. As such, our new method, which we term as Deep LoRA, enjoys notable advantages over the original LoRA method, namely (i) less overfitting by exploiting depth, and (ii) fewer hyperparameters without rank r and scale α having to be carefully tuned across all layers, all while having a comparable parameter efficiency due to compression.

Contributions. We summarize our contributions below.

• Practical contributions. We develop efficient compression methods by exploring compressible learning dynamics in overparameterized factorizations. Our method enjoys the benefits of overparameterization while significantly improving its efficiency. We demonstrate the effectiveness not only on deep matrix completion, but also for improving LoRA for language model fine-tuning.

• Theoretical contributions. Our methods are inspired by our theoretical results for deep matrix factorization. Mathematically, we rigorously prove the existence of invariant low-dimensional subspaces throughout gradient descent for each weight matrix, and show how they can constructed in practice.

Related Works There is a great deal of literature on implicit regularization in the setting of matrix factorization/linear networks (Neyshabur et al., 2015;Gunasekar et al., 2017;Arora et al., 2019;Moroshko et al., 2020;Timor et al., 2023;Ji & Telgarsky, 2019;Gidel et al., 2019;You et al., 2020;Liu et al., 2022), as well as low-rank learning in deep networks (Jaderberg et al., 2014;Sainath et al., 2013;Denil et al., 2013;Khodak et al., 2020;Oymak et al., 2019;Min Kwon et al., 2024;Tarzanagh et al., 2023). Similarly, there is an abundance of work discussing the benefits of overparameterization (Du & Hu, 2019;Arora et al., 2018b;Allen-Zhu et al., 2019b;Arpit & Bengio, 2019).

Following the advent of LoRA (Hu et al., 2021), there have been many follow-up works (Zhang et al., 2022;Chavan et al., 2023;Kopiczko et al., 2024). Importantly, no existing work (to the best of our knowledge) explicitly deals with overfitting, particularly in the limited sample regime. A more detailed discussion of related works can be found in Appendix A.

Notation. Given any L ∈ N, we use [L] to denote the index set {1, . . . , L}. We use t ∈ Z ≥0 to index a countable set of objects, such as W (t). We denote by I n the identity matrix of size n × n, and by 1 n a vector of length n with all entries equal to 1. We denote by ∥A∥ 2 F the squared Frobenius norm of matrix A, i.e., the sum of squares of all entries of A. We denote by N (A) the nullspace of the matrix A. We denote by O m×n the set of m × n matrices with either orthogonal rows or columns. We denote by ⊙ the Hadamard product, i.e., entry-wise multiplication. For convenience, whenever j > i we adopt the abbreviations

Warm-up Study: Deep Matrix Factorization

Towards gaining theoretical insights into the phenomena in Figure 2, we first build some intuition based on the problem of deep matrix factorization. Under simplified settings, we rigorously unveil the emergence of low-dimensionality and compressibility in gradient descent learning dynamics.

Basic Setup

Given a low-rank matrix Φ ∈ R dx×dy with rank(Φ) = r * , we approximate the matrix Φ by an L-layer deep overparameterized factorization

where Θ = (W l ) L l=1 are the parameters with weights W l ∈ R d l ×d l-1 for l ∈ [L]. We consider the case where the weights are all square

and learn the parameters Θ by solving

via gradient descent (GD) from scaled orthogonal initialization, i.e., we initialize parameters Θ(0) such that

(3) where ϵ l > 0. We assume this for ease of analysis, and believe that our results could hold for arbitrary small initial-ization. For each weight matrix, the GD iterations can be written as

for t = 0, 1, 2, . . . , where η > 0 is the learning rate and λ ≥ 0 is an optional weight decay parameter.

Main Theorem

We show that learning only occurs within an invariant lowdimensional subspace of the weight matrices, whose dimensionality depends on rank(Φ).

Theorem 2.1. Let W l (t) satisfy the initialization scheme (3) and updates (4), and suppose Φ ∈ R d×d is at most rank r and let m := d -2r > 0. Then there exist orthogonal matrices

for all l ∈ [L] and t ≥ 0, where W l (t) ∈ R 2r×2r with W l (0) = ϵ l I 2r , and

for all l ∈ [L] and t ≥ 1 with ρ l (0) = ϵ l .

In the following, we discuss several implications of our result and its relationship to previous work.

• SVD dynamics of weight matrices. The decomposition (5) is closely related to the singular value decomposition (SVD) of W l (t). Specifically, let d-2r) . Let W l (t) = U l (t) Σ l (t) V ⊤ l (t) be an SVD of W l (t), where U l (t), V l (t) ∈ O 2r and Σ l (t) ∈ R 2r×2r is a diagonal matrix. Then, by (5) we can write W l (t) as

⊤ which is essentially an SVD of W l (t) (besides the ordering of singular values). According to this, we can verify that ρ(t) is a (repeated) singular value undergoing minimal changes across iterations illustrated in Figure 3 (left). Additionally, these repeated singular values correspond to invariant subspaces U l,2 , V l,2 that are stationary throughout GD, as seen in Figure 3 (middle and right).

• Low-rank bias. From (6), we can show under mild assumptions that the GD trajectory for each weight matrix either remains or tends towards a solution with rank at most 2r. This is true whether we employ implicit or explicit regularization. Indeed, if we use small initialization ϵ l ≈ 0 with no weight decay λ = 0, then the fact that ρ l is a decreasing sequence (w.r.t. iteration) implies that the approximate rank of W l (t) can be no more than 2r throughout the entire trajectory. On the other hand, if we use weight decay with λ > 0, then we have ρ l (t) → 0 as t → ∞. This forces W l (t) towards a solution of rank at most 2r when the training converges. See Appendix E.2 for a formal statement and proof. This result is consistent with previous findings on low-rank and simplicity bias in deep networks (Huh et al., 2022;Galanti & Poggio, 2022;Li et al., 2020;Chou et al., 2024).

• Comparison to prior arts. In contrast to existing work studying implicit bias of GD towards low-rank solutions (Gunasekar et al., 2017;Arora et al., 2019), our result explicitly shows how GD finds these solutions. Moreover, unlike previous work on implicit bias (Min et al., 2021;Gissin et al., 2019;Arora et al., 2019;Vardi & Shamir, 2021), we also examine the effect of weight decay, which is commonly employed during the training of deep networks. Our analysis is distinct from that of (Saxe et al., 2014;2019), which studied continuous time dynamics under the special (separable) setting

In comparison, our result applies to discrete time dynamics and holds for initialization that is agnostic to the target matrix. It should also be noted that our result does not depend on balanced initialization like those in (Arora et al., 2018a), as the initialization scale ϵ l for each layer can be arbitrarily different from one another.

A sketch of analysis. We now provide a rough sketch for the beginning of the proof of Theorem 2.1 in the special case of small initialization ϵ l = ϵ ≈ 0 for all l ∈ [L] and λ = 0, highlighting the construction of the invariant subspace at initialization. The full proof can be found in Appendix E.1.

Proof sketch. Since ϵ L ≈ 0, from the gradient of ℓ(Θ) (see Appendix E), we have

implying that the rank of G 1 is (approximately) at most r. Now consider the subspace

), where we have dim S ≥ d -2r. Then, there exist orthonormal sets {v i } d-2r

i=1 and

form singular vector pairs of both W 1 (0) and W 1 (1) simultaneously as they remain unchanged by the gradient update G 1 , giving the last d -2r columns of V 1 and U 1 respectively. To see that we can take V 2 = U 1 , for instance, we note that

showing that u i are invariant under gradient updates in the second layer.

Compression of Overparameterized Factorization

We now show that, as a consequence of Theorem 2.1 and the proof sketch, we can run GD on dramatically fewer parameters to achieve a near identical end-to-end trajectory as the original (full-width) factorization; see Figure 4.

Constructing the "equivalent" compressed factorization. More specifically, given that Φ is at most rank r and d -2r > 0, from Theorem 2.1 we observe that

when we use initialization of small scale (i.e., (ϵ l ) L l=1 are small). Here,

) denotes the compressed function with compressed parameters Θ = ( W l ) L l=1 . As such, we can expect that solving

will approximately give the same solution as (2).

Constructing the factors (U l , V l ) L l=1 . As Theorem 2.1 only showed the existence of (U l , V l ) L l=1 , to solve (9) via GD, we need a practical recipe for constructing (U l , V l ) L l=1 efficiently at initialization of small scale ϵ l . This can be achieved based upon our proof sketch in Section 2.2: we compute

), and complete to an orthonormal basis to yield V 1 . The remaining U l , V l can then be iteratively constructed via

It should be noted that these compressed factors are related to, yet distinct from, spectral initialization, which is wellstudied in the literature (Chi et al., 2019;Khodak et al., 2020;Stöger & Soltanolkotabi, 2021). Since U l,1 , V l,1 are constructed via orthogonal complements to nullspaces involving the gradient, these directions do indeed correlate with the top singular subspaces of Φ in the deep matrix factorization case (although we do not use the singular value information). On the other hand, our approach is more general through the lens of compression, as it can be applied to a given deep overparameterized factorization trained on an arbitrary loss.

Optimization, complexity, and approximation error. In summary, we can approximately solve the original problem by solving (9) via GD for the compressed parameters Θ = ( W l ) L l=1 , starting from small initialization (ϵ l ≈ 0). The factors U L,1 , V 1,1 can be efficiently constructed based upon an iterative scheme that we discussed above from the initial weights.

Comparing the parameter counts of the compressed

Since r ≪ d, our approach leads to significant improvement in efficiency during GD; see Figure 4 (right). On the other hand, compression requires some additional computation to construct the factors U L,1 and V 1,1 prior to training, which involves taking a gradient of the first weight in the original factorization followed by an SVD or QR decomposition to compute an orthonormal basis for S. While this requires an additional O(d 3 ) compute, this has the same complexity as a single iteration of GD for the original factorization and is therefore a negligible overhead when comparing the two. Finally, the following result demonstrates that our compression method can achieve an almost identical end-to-end trajectory when we use small initializations; see Figure 4 (left).

Proposition 2.2. For r such that m := d -2r > 0, if we run GD on the compressed weights Θ as described above for the loss (9), we have

Here, ϵ l is the initialization scale for the weight W l (0).

The key idea of Proposition 2.2 is that GD is invariant under orthogonal transformations, and each factor W l in the endto-end factorization in (9) is the result of an orthogonal transformation of W l . Then, the approximation error m • L l=1 ϵ 2 l is only due to the approximation we showed in (8). We defer the full proof to Appendix E.3.

Application I: Deep Matrix Completion

In this section, we show that we can generalize our method in Section 2 from vanilla matrix factorization to solving low-rank matrix completion problems (Candes & Recht, 2012;Candès & Tao, 2010;Davenport & Romberg, 2016) via compressed deep factorizations. Given a ground-truth Φ ∈ R d×d with rank r * ≪ d, the goal of low-rank matrix completion is to recover Φ from only a few number of observations encoded by a mask Ω ∈ {0, 1} d×d . Adopting a matrix factorization approach, we minimize the objective

where f (Θ) is the deep overparameterized factorization introduced in (1). The problem simplifies to deep matrix factorization (2) that we studied earlier when Ω = 1 d 1 ⊤ d in the full observation case. Additionally, (10) reduces to vanilla (shallow) matrix factorization when L = 2, whose global optimality and convergence have been widely studied under various settings (Jain et al., 2013;Zheng & Lafferty, 2016;Sun & Luo, 2016;Ge et al., 2016;Bhojanapalli et al., 2016;Ge et al., 2017;Gunasekar et al., 2017;Li et al., 2019;Chi et al., 2019;Li et al., 2018b;Soltanolkotabi et al., 2023;Sun et al., 2018;Zhang et al., 2020;Ding et al., 2021).

A double-edged sword of overparameterization. In practice, the true rank r * is not known -instead, we assume to have an upper bound r of the same order as r * , i.e., r * ≤ r ≪ d. Surprisingly, overparameterization has advantages in terms of both depth L and width r:

• Benefits of depth: mitigating overfitting. When r > r * , it has been demonstrated (Arora et al., 2019) that optimizing deeper factorizations (i.e., L ≥ 3) generalize better in the low sample regime, while their shallow counterparts overfit; see Figure 1 (left).

• Benefits of width: improving convergence. On the other hand, increasing the width r of the deep factorization beyond r * results in accelerated convergence in terms of iterations, see Figure 1 (right).

However, the advantages of overparameterization come with the challenges of much higher computational costs. For an L-layer factorization of (full)-width d, we require O(L • d 3 ) multiplications per iteration to evaluate gradients and need to store O(L • d 2 ) parameters, where d is often very large.

Using ideas from Section 2, however, we can obtain the benefits of overparameterization without the extra computational costs.

Compression for deep matrix completion. Given the similarity between deep matrix factorization and completion (i.e., Ω = 1 d 1 ⊤ d vs arbitrary Ω), it seems straightforward to generalize our compression methods in Section 2.3 to deep matrix completion. However, as shown by the orange trace in Figure 5, direct application does not work well, as the compressed factorization's trajectory diverges from that of the original. This is because the compressed subspaces

] can be misaligned with the true subspace due to the perturbation by the mask Ω.

Nonetheless, this issue can be mitigated by slowly updating U L,1 , V 1,1 during training. Specifically, compared to (9), we minimize min

via GD by updating Θ, U L,1 , V 1,1 simultaneously every iteration, with a learning rate η on Θ along with a discrepant learning rate γη on U L,1 , V 1,1 . Because we update U L,1 , V 1,1 slower than updating Θ, we generally choose γ > 0 to be small and tuned accordingly for the given problem.

As a result, we reduce computational costs to O((L+d)•r 2 ) multiplications per iteration for computing gradients, and O(d • r + L • r 2 ) parameters. Yet still the trajectory of the deep compressed factorization ultimately aligns with that of the original, while converging roughly 5× faster w.r.t. wall-time, as demonstrated in Figure 5. Moreover, the accelerated convergence induced by the full-width trajectory results in the compressed factorization being 3× faster than randomly initialized factorizations of similar width -see Appendix D.1 for more details.

Application II: Model Fine-tuning

In this section, we show that our compression idea can be further extended to parameter-efficient fine-tuning of For each choice of rank r, we draw 16 samples at random from STS-B over 5 trials with different seeds, and measure performance on the validation split of each method using the same train set.

pretrained language models, specifically via low-rank adaptation (LoRA) (Hu et al., 2021). In particular, inspired by our approach for deep matrix completion, we propose Deep Low-Rank Adaptation (Deep LoRA), which consistently outperforms vanilla LoRA in the limited sample regime.

Deep Low-Rank Adaptation (Deep LoRA)

Background on LoRA. With the ever-growing size of pretrained models and countless downstream tasks, full model fine-tuning is often computationally infeasible. Given a pretrained model whose parameters consist of a collection of dense weight matrices {W 0k } m k=1 ⊂ R d×d (e.g., the query/key/value projections of a transformer (Vaswani et al., 2017)), LoRA seeks to adapt each layer to a given task by freezing the pretrained weight {W 0k } m k=1 and optimizing an extra trainable low-rank factorization on top. In other words, the fine-tuned weight W k is given by

where α > 0 is a tunable scale parameter and

∈ R r×d with r ≪ d, thereby substantially reducing the number of trainable parameters during finetuning.

Proposed method: Deep LoRA. For vanilla LoRA, if we view adapting each weight matrix of model as an individual low-rank factorization problem, we have demonstrated in previous sections that overparameterization and subsequently compressing factorizations improves generalization with minimal extra computational costs. With this in mind, we can employ a deep overparameterized adaptation of each pretrained weight as

where each

Here, L > 0 is the depth, and typically we choose L = 3, which is precisely the setting of Figure 2. From the figure, we can see that (i) all the converged weights {∆W k } m k=1 are very low-rank (left panel), (ii) the learning dynamics each for each weight approximately stay within the same invariant subspace throughout the iterations (middle panel), and (iii) this happens independent of the training loss decreasing (right panel).

These observations imply that deep overparameterized factorizations in Deep LoRA are highly compressible, so we can apply the compression method from deep matrix completion in Section 3 to compress the learning dynamics for each individual weight for model fine-tuning. Here, the major differences of our compression approach for deep LoRA from that of deep matrix completion is that (i) we have a separate compressed factorization for each layer to be adapted, and (ii) the fine-tuned loss function can be tailored for specific tasks (e.g., the cross-entropy) besides the ℓ 2 loss.

Advantages of Deep LoRA. Compared to vanilla LoRA, Deep LoRA has clear advantages that we highlight below. More details are provided in Section 4.2.

• Less overfitting in limited data regime. Fine-tuning overparameterized models using LoRA can still result in overfitting in few shot or limited data regime (Sebastian Raschka, 2023). In comparison, the extra depth in (12) of Deep LoRA can help prevent overfitting (see Fig- ure 6), which is similar to deep matrix completion in Figure 1.

• Robustness to the hyperparameter r. As shown in Figure 8, by exploiting the intrinsic low-dimensional dynamics in GD via overparameterization in width, our approach is robust to the choice of the rank r in fine-tuning.

Deep LoRA only requires 3r 2 additional trainable parameters for each adapted layer compared to vanilla LoRA, where r is relatively small (e.g., r = 8).

More Experimental Details

To evaluate our approach, we use a pretrained BERT (Devlin et al., 2019) base model and apply adaptation on all attention and feedforward weights in the transformer, resulting in 72 adapted layers in total. Unless stated otherwise, we use r = 8 for both vanilla and Deep LoRA throughout all experiments, in which case Deep LoRA has roughly 0.01% more parameters (with respect to BERT) than vanilla LoRA. We utilize Adam (Kingma & Ba, 2014) as an optimizer for both methods. See Appendix B for more details on the experimental setup.

Advantage I: Better generalization with limited data.

We first evaluate our approach on tasks in the GLUE benchmark (Wang et al., 2018), which is a standard benchmark for natural language understanding. To test the performance in a limited data setting, for one given trial of a single task, we randomly sample 1024 examples from the task data for fine-tuning, and compare the difference in performance on the same train set between Deep LoRA and vanilla LoRA on the entire validation split. From the results shown in Table 1, we can see that Deep LoRA delivers significant improvements across most tasks compared to vanilla LoRA, and on average improves performance by nearly 3 points, a notable margin.

This improvement in performance becomes more pronounced in scenarios with severely limited data, such as few-shot settings. Applying the same sampling procedure as in the prior study to the STS-B dataset, we assess both approaches using only n ∈ {16, 64, 256} training instances.

Experiments in Figure 6 illustrate that Deep LoRA consistently surpasses vanilla LoRA across all sample sizes, with the most significant difference observed when n = 16.

Deep LoRA finds lower rank solutions. We find that at the end of fine-tuning, Deep LoRA finds lower rank solutions for ∆W k than vanilla LoRA, as shown in Figure 7.

In the limited data setting (256 samples), we see that all adapted layers in the vanilla LoRA saturate the constrained numerical rank r = 8, while most layers in Deep LoRA are perturbed by matrices with numerical ranks between 0 and 4.foot_1 This suggests that Deep LoRA can adaptively select the appropriate rank for each layer depending on the task. This low-rank bias induces implicit regularization during the fine-tuning process and ultimately prevents overfitting to the task, particularly when only few training samples are available. As a practical consideration, Deep LoRA also requires a fraction of the memory cost to store compared to vanilla LoRA due to the parsimony in adapted weights.

Advantage II: Robustness to choice of rank r. Due to the scarcity of the target training data, choosing the rank r in LoRA is a delicate process -it needs to be large enough to capture the complexity in modeling the downstream task, while small enough to prevent overfitting. The proposed Deep LoRA, on the other hand, avoids catastrophic overfitting as we increase r, as demonstrated in Figure 8. This observation mirrors the behavior seen in deep matrix completion, as illustrated in Figure 1. For shallow factorizations, an overestimation of rank r leads to an increase in the generalization error. In contrast, deep factorizations remain resilient to overfitting.

Finally, we show that Deep LoRA outperforms vanilla LoRA for few-shot natural language generation fine-tuning in Appendix C. We also provide an ablation study in Appendix D.2 on the compression mechanism for Deep LoRA and show that it is crucial for accelerating training.

Conclusion & Future Directions

In this work, we have provided an in-depth exploration of low-dimensionality and compressibility in the dynamics of deep overparameterized learning, providing theoretical understandings in the setting of deep matrix factorization and applications to efficient deep matrix completion and language model adaptation. Finally, we outline a couple potential future directions following this work.

Compressibility in non-linear settings. Although the results on network compression in Section 2 exploit the specific gradient structure of deep matrix factorizations, we believe that our analysis can provide meaningful direction for analyzing the fully non-linear case.

To sketch an idea, consider the setting of Section 2.1 except with a non-linear factorization, i.e., (1) becomes

where σ is (for example) the entry-wise ReLU activation. For concreteness, consider the L = 3 case. The gradient of the loss with respect to, e.g., W 2 in ( 2) is given by

) ⊤ where h is the entry-wise unit step function and E = f (Θ) -Φ. Comparing this to the gradient in the linear setting ( 14), there is a great deal of shared structure, with the two main differences being the non-linearity applied to W 1 in the post factor and a projection on the inner term via h(W 2 σ(W 1 )). However, we still have the lowrank structure of W ⊤ 3 E, and the zeroing out of certain entries preserves approximate spectral properties of the matrix (Chatterjee, 2015). Moreover, this projection is akin to the masking via Ω as in deep matrix completion from Section 3, for which we do find compressible dynamics. In Figure 9, we plot the singular value spectrum of the above gradient at small initialization, finding that the top r * singular values separate from the rest of the spectrum. This suggests that we may be able to identify a low-dimensional subspace along which we can achieve similar dynamics to the full parameter space.

Extensions to Deep LoRA. We have demonstrated the efficacy of Deep LoRA for natural language understanding and generation in Section 4 and Appendix C respectively. However, it would be meaningful to evaluate Deep LoRA in other modalities, e.g., diffusion models, where fine-tuning on limited data is commonplace. Moreover, the high degree of alignment at initialization to the final adapted subspaces shown in Figure 2 suggests that SGD (rather than Adam) can be used for the outer factors of Deep LoRA, further reducing memory costs. Finally, exploring the use of second-order methods to accelerate fine-tuning along the rank-r subspace could be a potential improvement. Implications for representation learning. The low-rank bias in the end-to-end features of deep networks may have important connections to emergent phenomena in representation learning, such as deep neural collapse (Zhai et al., 2024;Zhou et al., 2022b;Yaras et al., 2022;Wang et al., 2022;Zhou et al., 2022a;Zhu et al., 2021;Beaglehole et al., 2024;Li et al., 2024), whereby the last-layer representations exhibit surprisingly simple structures. Moreover, by uncovering the low-rank evolution of individual weights, we could shed light on more intricate phenomena such as progressive neural collapse (He & Su, 2023;Wang et al., 2023).

Impact Statement

This paper presents work on training and fine-tuning large language models (LLMs), the consequences of which include (but are not limited to) the propagation of biases, privacy violations from data misuse, and significant environmental costs due to high energy consumption. results in faster convergence. However, increasing the width alone also increases computational costs -by employing compression, we can achieve the best of both worlds. We verify that compression is crucial for the efficiency of Deep LoRA. We compare the performance of three different approaches: (i) Original, where we use a three-layer full-width factorization as in ( 12), (ii) Compressed, which is the rank-r compression of (12) (a.k.a. Deep LoRA), and (iii) Random, where the W (i) k in ( 12) are initialized randomly with W

D.2. Deep LoRA

(2) k ∈ R r×r . We can see that via compression, Deep LoRA can achieve similar convergence behavior to the original overparameterized factorization with much fewer parameters, while the randomly initialized version takes much longer to train, similar to the result for deep matrix completion in Appendix D.1.

E. Proofs

The analytic form of the gradient ∇ Θ ℓ(Θ) is given by

where E = f (Θ) -Φ, which when substituted into (4) gives the update rules

/ϵ k+1 . This implies that W k+1 (0)v

. Moreover, we have

i /ϵ k+1 = 0, where the first two equalities follow from orthogonality and u

/ϵ k+1 , and the last equality is due to v

where the second equality follows from v

and the third equality is due to

i . Therefore E(k + 1) holds, so we have E(l) for all l ∈ [L]. As a result, we have shown the base cases A(0), B(0), C(0), and D(0). Now we proceed by induction on t ≥ 0. Suppose that A(t), B(t), C(t), and D(t) hold for some t ≥ 0. First, we show A(t + 1) and B(t + 1). We have

where the first equality follows from (15), the second equality follows from definition of E(t), the third equality follows from D(t), and the fourth equality follows from A(t) and B(t) applied repeatedly along with v

proving A(t + 1). Similarly, we have

where the third equality follows from C(t), and the fourth equality follows from A(t) and B(t) applied repeatedly along with v

Repeatedly applying the above equality for k = l, l + 1, . . . , L -1, we obtain

which follows from C(t), proving C(t + 1). Finally, we show D(t + 1). For any k ∈ {2, . . . , L}, it follows from v

Repeatedly applying the above equality for k = l, l -1, . . . , 2, we obtain

which follows from D(t). Thus we have proven D(t + 1), concluding the proof.

Proof of Theorem 2.1. By A(t) and B(t) of Lemma E.1, there exists orthonormal matrices {U l,2 } L l=1 ⊂ R d×m and {V l,2 } L l=1 ⊂ R d×m for l ∈ [L] satisfying V l+1,2 = U l,2 for all l ∈ [L -1] as well as W l (t)V l,2 = ρ l (t)U l,2 and W l (t) ⊤ U l,2 = ρ l (t)V l,2

for all l ∈ [L] and t ≥ 0, where ρ l (t) satisfies (6) for t ≥ 1 with ρ l (0) = ϵ l . First, complete V 1,2 to an orthonormal basis for

Then for each l ∈ [L -1], set U l = [U l,1 U l,2 ] where U l,1 = W l (0)V l,1 /ϵ l and V l+1 = [V l+1,1 V l+1,2 ] where V l+1,1 = U l,1 , and finally set U L = [U L,1 U L,2 ] where U L,1 = W L (0)V L,1 /ϵ L . We note that V l+1 = U l for each l ∈ [L -1] and U l , V l are orthogonal since W l (0)/ϵ l is orthogonal for all l ∈ [L]. Then we have

for all l ∈ [L] and t ≥ 0, where the first equality follows from ( 16). Similarly, we also have

for all l ∈ [L] and t ≥ 0, where the first equality also follows from ( 16). Therefore, combining ( 16), (17), and (18) yields

for all l ∈ [L], where W l (0) = ϵ l I 2r by construction of U l,1 . This directly implies (5), completing the proof.

E.2. Low-rank bias in Theorem 2.1

Here, we verify the claims following Theorem 2.1 and give a precise characterization of the rate of decay of ρ l as given by ( 6) and the conditions on learning rate η needed to achieve such behavior. These are given in the following lemma.

Lemma E.2. In the setting of Theorem 2.1, suppose 0 < ϵ l = ϵ ≤ 1 for all l ∈ [L] and 0 < η ≤ 1 λ+ϵ . Then for all t ≥ 0, the updates of ρ l (t) in (6) satisfy ρ l (t) = ρ(t) for some ρ, and

Since λ and ϵ are often chose to be small, the above lemma implies that a small learning rate is not required to achieve a low-rank solution. Moreover, by choice of η, when weight decay is employed (i.e., λ > 0) the above inequality implies that ρ(t) → 0 as t → ∞. When λ = 0, we instead have that ρ is bounded by ϵ.

Proof of Lemma E.2. If ρ l (0) = ϵ for all l ∈ [L], it is clear that ρ l (t) = ρ(t) for some ρ for all t ≥ 0, and the updates take the form

for each t ≥ 0. We proceed by induction. For t = 0, since ρ(0) = ϵ, the claim holds trivially. Now suppose (19) holds for some t ≥ 0. By choice of η, we have that 1 -η • (λ + ϵ) ≥ 0, so ρ(t) ≥ 0. It then follows that

by the fact that ρ(t) ≤ ϵ • (1 -ηλ) t . Next, by choice of η and initial condition, we have that ρ(t) ≤ ϵ, so that ρ(t + 1) = ρ(t) • 1 -η • λ + ρ(t) 2(L-1) ≥ ρ(t)

since ϵ 2(L-1) ≤ ϵ by ϵ ≤ 1. The claim follows.

E.3. Proof of Proposition 2.2

Proof. First, it follows from Theorem 2.1 that for any 1 ≤ i ≤ j ≤ L we have

for all t ≥ 0, where U l,1 , V l,1 ∈ R d×2r and U l,2 , V l,2 ∈ R d×m are the first 2r and last m columns of U l , V l ∈ R d×d respectively.

The key claim to be shown here is that W l (t) = W l (t) for all l ∈ [L] and t ≥ 0. Afterwards, it follows straightforwardly from (20) that