The Expressive Power of Low-Rank Adaptation
Authors: Yuchen Zeng
Kangwook Lee
Venue: ICLR 2024 poster (2024)
Keywords: LoRA
expressive power
parameter-efficient fine-tuning
adaptation
neural networks
transformer
Primary area: learning theory
TL;DR: This paper takes the first step to theoretically analyzing the expressive power of Low-Rank Adaptation (LoRA).

Abstract: *Low-Rank Adaptation* (LoRA), a parameter-efficient fine-tuning method that leverages low-rank adaptation of weight matrices, has emerged as a prevalent technique for fine-tuning pre-trained models such as large language models and diffusion models.
Despite its huge success in practice, the theoretical underpinnings of LoRA have largely remained unexplored. 
This paper takes the first step to bridge this gap by theoretically analyzing the expressive power of LoRA. 
We prove that, for fully connected neural networks, LoRA can adapt any model $f$ to accurately represent any smaller target model $\bar{f}$ if LoRA-rank $\geq(\text{width of }f) \times \frac{\text{depth of }\bar{f}}{\text{depth of }f}$, under a mild assumption. 
We also quantify the approximation error when the LoRA-rank is lower than the threshold. 
For Transformer networks, we show any model can be adapted to a target model of the same size with rank-$(\frac{\text{embedding size}}{2})$ LoRA adapters.
All our theoretical insights are validated by numerical experiments.

Published as a conference paper at ICLR 2024
THE EXPRESSIVE POWER OF LOW-RANK ADAPTATION
Yuchen Zeng
Kangwook Lee
Department of Computer Science University of Wisconsin-Madison yzeng58@wiss edu
Department of Electrical and Computer Engineering University of Wisconsin-Madison kangwook. Lee@wisc.edu:
ABSTRACT
Low-Rank Adaptation (LoRA), parameter-efficieet fine-tuning method that leverages low-rank adaptation of weight matrices, has emerged as prevalent tech- nique for fine-tuning pre-trained models such large language models and diffu- sion models. Despite its huge success in practice, the theoretical underpinnings of LoRA have largely remained unexplored. This paper takes the first step bridge this gap by theoretically analyzing the expressive power of LoRA. We prove that, for fully connected neural networks, LoRA can adapt any model f accurately
represent any smaller target model f if LoRA-rank (width of f) depth of f under a mild assumption. We quantify the approximation error when the LoRÅ- rank is lower than the threshold. For Transformer networks, we show any model can he adapted to target model of the same size with rank-( embeddiing size LoRA adapters. Our study reveals numerous theoretical insights on hyperparameter tun- ing and algorithm development for LoRA, all of which are empirically validated.
depth
2
INTRODUCTION
Recent foundation models, such large language models (OpenAI, 2023; Liu et al., 2019; Touvron et al., 2023), have achieved remarkable success in a wide range of applications. Due to their sub- stantial size, the standard full fine-tuning approach-where all the model's parameters for specialized tasks-is becoming increasingly difficult and inefficient. This leads to the growing popularity of parameter-efffcient fine-tuning approaches (Hu al., 2022a; Liu et al., 2022b; Ben Za- ken et al., 2022; Hu et al., 2022b). Instead of updating all parameters, these approaches selectively update smaller subsets of weights or introduce lightweight adapters, thereby greatly decreasing the computational and storage costs.
updated
The most dominant approach along this line is Low-Rank Adaptation (LoRA) (Hu et al., 2022a), which employs lightweight low-rank adapters to pre-trained weight matrices. Far from merely en- hancing computational efficiency, empirical evidence has shown that LoRA can match or even ex- ceed the performance of full fine-tuning (Hu et al., 2022a). To date, LoRA has been widely used and achieved considerable success in adapting large language models (Hu et al., 2022a; Dinh et al., 2022b) and image generation models (Ryu, 2023; Fan et al., 2023) for various downstream tasks.
Despite the empirical success of LoRA, little is known in theory about how it works. A notable exception (Malladi et al., 2023) showed that LoRA finetuning is approximately equivalent full fine-tuning in the lazy regime. However, many theoretical questions remain open, such as: What is the minimum rank of the LoRA adapters required to adapt (pre-trained) model match the functionality of the target model f? How does the model architecture (i.e., depth, width) affect the minimal rank? If the adapter rank is lower than this threshold, what is the resulting approximation error? Answering such questions will provide important theoretical insights into when and why LoRA achieves effective adaptation.
Our Contributions. In this paper, we present the first set of theoretical results that character- ize the expressive power of Low-Rank Adaptation (LoRA) for Fully Connected Neural Networks (FNN) and Transformer Networks (TFN). In particular, we identify the necessary LoRA-rank for adapting a frozen model to exactly match a target model. For FNN cases, we also establish the required LoRA-rank for closely approximating the target model when a small approximation error is allowed. Our work focuses solely on the expressive power of the model with low-rank adapters, i.., we show that under which conditions, effective low-rank adapters exist for the given adaptation task. This excludes other aspects such as optimization and generalization.
We now present the essence of our main theoretical findings in the following informal statement.

---

Published as a conference paper at ICLR 2024
Theorem 1 (Informal). Let f be target FNN and fu be arbitarr frozen FNN. Under mild conditions on ranks and network architectures, there exist low-rank adapters such that a low-rank adapted version of fo is exactly equal to J.
We present the detailed formulations of Theorem under two scenarios: (i) applying a uni- form rank across all LoRA adapters, as detailed in Theorem and the specialized instance Corollary 4 for randomly drawn frozen and target models; and (ii) allowing different ranks ap- plied to each LoRA adapter, as described in Theorem 6. To the best of our knowledge, this is the first known theoretical results on the expressive power of LoRA. While this informal theorem is for exact approximation, we also derive the approximation bounds as well, i.e., we characterize the approximation error between the finetuned model and the target model function of the LoRA- rank, as provided in Theorem 5 for the uniform LoRA-rank scenario and Theorem 6 for general cases. Furthermore, within the same framework, final layers for randomly generated frozen models, as described in Lemma 4. This result allows us to contrast LoRA and final layer tuning, thereby providing insights for future algorithm development.
investigate the expressive power of tuning the
We summarize our main findings on TFN in the following informal theorem.
Theorem (Informal). Let i be the target TFN and fo be the frozen TFN. Under mild conditions on ranks and network architectures, there exist low-rank adapters for attention weight matrices such that a low-rank adapted version of fo is exactly equal f.
The formal statement Theorem 2 is provided in Theorem 7, with specialized version in Corol- lary 10 tailored for randomly generated frozen and target models.
In Sec. and G. we perform experiments on both synthetic and real datasets to substantiate our theoretical results, demonstrating the practical applicability of our theoretical findings in algorithm development and hyperparameter tuning.
1.1 RELATED WORKS
Expressive Power of Neural Networks Theoretical study of the expressive power of unfrozen neural networks has progressed since the first universal approximation theorem (Hornik al., 1989), showing that sufficient network width and depth can guarantee function approximation (Bengio & Delalleau, 2011; Eldan & Shamir, 2016; 6; Liang & Srikant, 2017). Many recent studies obtained sim- ilar results for deep neural networks with modern twists such ReLU activations and Transformer networks (Yun et al., 2020a; Raghu et al., 2017; Telgarsky, 2016; 2015; Bietti Bach, 2021; Oy- mak et al., 2023; Lee al., 2017; Shen & Zhang, 2020; Likhosherstov et al., 2021; ; Hsu al., 2021; Park et al., 2021; Yun et al., 2020b; Giannou et al., 2023b). Metrics like
Chervonenkiss and Rademacher complexities (Vapnik & Chervonenkis, 2015; Bartlett & Mendelson, 2001) assess clas- sification capacity. However, these theories cannot fully explain the performance of frozen neural networks they generally cannot factor in pre-trained model parameters and adaptation methods.
Expressive Power of Adaptation Methods In stark contrast to the flourishing research on the expressive power of neural networks, there exists a limited number of works investigating the ex- pressive power of adaptation methods. A notable exception is Giannou et al. (2023a), investigating the expressive power of normalization parameter fine-tuning. They demonstrate that fine-tuning the normalization layers alone can adapt a randomly initialized ReLU network to match any target net- work that is (wwitth) times smaller. We borrow some proof techniques from this work, including techniques for extending results from linear neural networks to ReLU neural networks. In another recent work (Englert & Lazic, 2022), the authors show that neural reprogramming (Elsayed al., 2019; Engel et al., 2018; 8; Lee et al., 2020; Dinh et al., 2022a; Chen, 2022), a technique that modifies only the inputs while keeping the pretrained network frozen, can adapt any random two-layer ReLU network to achieve arbitrarily high accuracy on a Bernoulli data model over hypercube vertices. Despite these early attempts, no existing study has yet explored the expressive power of LoRA, the current leading adaptation method.
more detailed discussion of related works is provided in Sec. B.
1.2 NOTATIONS
Define [N] := (1, NJ.. Let the operators A and V denote the minimum function and the maximum function, respectively. We use I to represent the identity matrix.
2

---

Published as a conference paper at ICLR 2024
For sequence of L matrices (Wi) we simplify the product of these matrices WL W L-11 Wi as Il Wi, with matrices multiplied in descending order from Wt to WI. When m > n, we define Di=m a, and IT a; for sealars (a+) and Σ i=mm W; O and I W; for square matrices (W.) W.).=m.
Singular Value Decomposition (SVD) of the matrix W can be expressed W UDVT where U.V E D are orthonormal matrices and D E PxD is a diagonal matrix. The singular values, sorted in descending sequence, are represented on the diagonal of D, denoted as 01 (W): 2 (2(W)= 2 ... 2 DD (W) 2 O, where (a) denotes the d-th largest singular value for all d E [D]. When d D. aa W) is defined as zero. The best rank-r approximation (in the Frobenius norm the 2-norm) of W is Ei= d,u.s, where u, and e; are the i-th column of U and V, respectively (Eckart & Young. 1936; Mirsky, 1960). We denote this best rank-r approximation by (W), where LR is shorthand for "Low-Rank". When 2 rank(W), it is clear that (W) = W. Occasionally, the subscript r may be omitted to indicate a general low-rank approximation without specifying the rank.
2
WARM UP: EXPRESSIVE POWER OF LINEAR MODELS WITH LORA
Before delving into the expressive power of LoRA for FNN and TFN, we begin by investigating the simplest scenario: both the target model [ and the frozen model fo are linear, i.e.,
Target Model
f(x))
Wa
Frozen Model fo(x) = WL Wix (II' Wi) x.
This problem serves a simplified version of approximating target FNN, where the target model J has a single layer, the frozen model So has I. layers, all bias vectors in both two models are zero, and the activation functions are linear. Throughout this paper, for the sake of simplicity, we will assume that both models have the same number of neurons in each layer, i.e., W, W ..... W. DDDD Nevertheless, our results are readily extendable to situations where the frozen model wider than the target model, which is a more natural setting the frozen models are often overparameterized to ensure high capacity and good performance across diverse tasks in practice. See the discussion in Sec. H for more details.
The objective here is to incorporate low-rank adapters into the frozen model so that the adapted model can effectively approximate the target model. Unless otherwise specified, we always consider a uniform LoRA-rank for all low-rank adapters throughout this paper. For a given LoRA-rank R E [D). we apply LoRA adapters AW 1W..... AWL L to the frozen model, and the adapted model can be represented
Adapted Model f(x) (WL AW -Wi 1W1)
where rank( (A)) < R for all I E [L].
Since the frozen model and adpated model are all linear, we focus quantifying the discrepancy between the linear coefficients, i.e., (W;
W. In the subsequent lemma, we establish the minimal achievable norm, and identify the smallest LoRA-ram required for the adapted model to exactly represent the target model, i.c.. f = F. under a non non-singularity assumption. We will demonstrate Sec. 3.3 that this non-singularity assumption is mild, as can be satisfied even by randomly generated weight matrices.
Lemma 1. Define error matrix E == w - Wi, and denote its rank by Rg = rank(B) E). For a given LoRA-rank It E [D], assume that all the weight matrices of the frozen model (Wif and IH' W. IR, are non-singular for all R(L 1). Then, we have the following:
IT' AWW W =ORL+1(E).
min
AW preak((WW.// (SSR
Thus, when R [x the optimal solution satisfies II (Wr AW,) () W, implying f
Proof Sketch. We start the proof by noting that the distance between the adapted and target models
(WW+AW)) w = ( + AW))
[[
I
wi
W
Wi
1=1
1=1

---

Published as a conference paper at ICLR 2024
The remaining proof aims to minimize the right-hand side under the constraint rank( R for all E [L]. The basic idea here is match I (Wi+ AW - - W/ with the best rank-r approximation of W II W.. The key steps to solve this problem are as follows.
1. Demonstrate that I ( + A W 1) II Wi can be decomposed into L terms:
Il (W: + 1W1) II Wi = Σラ= (1i-. w:) AW, (II (W; + AW.).
Since rank(AW) WW) < R, it follows that rank
[TI (W AW)) - II Wi) S RL.
2. Consider the rank- approximation of W -II Wi. Decompose this low-rank approxima-
tion into L terms Σ/= E, such that rank E1) S R. where Ej's will be determined later.
3. To match II + AW,) M = W with the rank-RL ML approximation of W (W, AW.) = E, by choosing A AW,
Ih Wi, we let (II W.) AW,
(TT-41 E (II + AW.)
4. Select appropriate (Ei)=1 such that W. AW; are invertible for i [Z].
The complete proof and the explicit construction of optimal LoRA adapters, are detailed in Sec. D.
In fact, this lemma delivers a crucial insight. When we consider L and R D, the lemma becomes strikingly similar to the Eckart Eckart-Young- Young-Mirsky theorem (Eckart & Young. 1936; Mirsky, 1960). However, there is a sigmificant difference from the classical theorem on the optimal low-rank approximation, which involves single target matrix and single matrix Our lemma demonstrates that comparable result can be achieved for a "product of matrices," where each matrix is optimized subject to a low-rank constraint. That being said, even though each matrix is constrained by a low rank, the "effective rank" is the sum of these low ranks, i.e., in this scenario, is LR. Consequently, once the low-rank adapters are optimally configured, one can make the product equal to the best rank LR- -.R-apprxximation of the target matrix. This can be viewed as an extension of the matrix approximation theorem to a product of matrices, each subject low-rank constraints. Our main theoretical results on the expressive power of LoRA, which we will present in the subsequent sections, will build upon this core matrix approximation result.
optimization variable.
EXPRESSIVE POWER OF FNNs WITH LORA
3.1 PROBLEM SETTING
We use FN ( to denote I-llaee width-D fully connected ReLU neural
network with weight matrices Wi E RDD and biases by E RRP, where E [Z]. The target FNN F and frozen FNN fo can be represented as follows:
Target FNN F = FNN (: ( Frozen FNN fo = FNNL.D(=: (W))
where W, E DXD and b. E IR represent the weight matrix and bias vector for the (-th layer of the target model f. respectively. Likewise, Wi DDD b, E IRD are those for fo. for layer 1 e [Z]. Given specified LoRA-rank R E [D), we adapt the frozen FNN So into new model f via LoRA. The adapted model is defined as
Adapted FNN ʃ == FNN (Wr + AW (b)
where the weight matrix for the low-rank adapter AW, E RDD satisfies specified rank constraints, updated bias vector b, E TR. for E [.
As noted in Sec. 2, is common for the pretrained model to larger than necessary. Therefore, we focus on a setting where the frozen model is deeper than the target model, i.e., L > L. Furthermore, this section, we let the input space X' IR. DxD bounded.
We consider the case where the bias parameters can also he updated, suggested by Hu et al. (2022a). Experiments investigating the impact of updating hias parameters are presented in See. G.5.
4

---

Published as a conference paper at ICLR 2024
3.2 ONE-LAYER RELU FNN APPROXIMATION
We start with investigating the expressive power of LoRA on one-layer FNN. In this setting, our aim is to identify LoRA adapters (AW)) and bias vectors (br) such that the adapted model
ReLu((W, AW ReLU(WE AW 1-1) ReLU(-... b bz)
closely approximates the target one-layer ReLU FNN model ReLU W +b1))
This differs from the setting described Sec. 2, where a multi-layer FNN with linear activation functions and zero biases was used to approximate a one-layer FNN with the same properties. In the current setting, we introduce non-linearity through the use of ReLU activation functions in the frozen model and also take biases into account. Consequently, to generalize the findings to this new setting, addressing the introduced non-linearity due to the ReLU activation functions in the frozen model is the main challenge.
We employ the following two steps to extend the results Sec. the current setting.
1. (Linearization) We eliminate the nonlinearity in the first L L-1 layers of the adapted model, mak- ing it equivalent to a one-layer ReLU FNN. This can be readily achieved by choosing sufficiently large bias vectors for the first I, 1 layers to ensure that all ReLUS in these layers are activated. This technique of eliminating non-linearity is inspired by Giannou et al. (2023a).
2. (Weight Matrix Alignment) We update the bias vectors of the last layer by. to align with that of the target model J. and apply the linear model approximation results (i.e., Lemma 1) to identify the low-rank adapters that match the weight matrix ʃ.
Following the steps above, we arrive at the subsequent lemma, which demonstrates that any one- layer FNN can be closely approximated by multi-layer FNN finetuned via LoRA. The complete proof is provided in Sec. E.1.
Lemma 2. Define error matrix E : W W W., with its rank represented by RØ = rank E). Consider a LoRA-rank R E [D]. Assume that the weight matrices Wi.... W, E DxD and are non-singular. Let x be a random imput sampled
Il'm W: (E) for all S from a distribution with bounded support X and les E Exx T Then, there exists rank- R or lower matrices AW 1...... AWL L E DDD and bias vectors b..... by E RR such that the expected squared error can be bounded as
fx]f(x) - f(x) s |1 o (E).
Moreover; when R 2 L1 we have (ax (x) for all æ E X.
3.3 MULTI-LAYER RELU FNN APPROXIMATION
We now generalize our discussion to the approximation of multi-layer ReLU FNNs. The key strategy for extending the results to approximating multi-layer ReLU FNNs under LoRA is model partition, inspired from Giannou et al. (2023a). To elucidate this, we start with specific example.
Example 1. Consider the case where L = 2 and L = 4. We view a two-layer target model f as a partition the four-layer adapted model
composition of two lne-layer ReLU FNNs. Accordingly, into two submodels, each consisting of two layers. For each layer in the target model, we utilize two corresponding layers in the frozen/adapted model for approximation. This problem then simplifies into a one-layer FNN approximation problem, which has already been addressed in Lemma 2.
PI} to partition the layers in Based on this example, we introduce ordered partition P {P.....,
the adapted model f. where _._1 P. LL]. Each element P: E P consists of consecutive integers. Given a partition P. each element P. specifies that the layers with index E P. in the adapted model will be used to approximate the i-th layer in the target model. Example 1, which uses every two layers in the adapted model to approximate each layer in the target model, can be considered as partition represented as {(1, 2) (3,4)). Similarly, we extend this simple uniform partition into general cases for Layer target FNN and L-layer frozen FNN:
pa = {P....., ph] = {(1,..,,A M). {M +1 1,.... 2M {(I 1)M + +1, +1...,,I)] I.).
5

---

Published as a conference paper at ICLR 2024
where M := [L/L]. The uniform partition indicates that every M layers in the adapted model are employed to approximate each layer in the target model. We use II. Wi to denote the product of the weight matrices from the layers E P,, with the later layer positioned to the left and the carlier
layer to the right in the matrix product. For example, her W M Wi WM W1.
We first extend Lemma 2 to multi-layer FNN approximation setting using this uniform partition.
Uniform Model Partition. Given a specified LoRA-rank R E [D], to derive our results, we intro- duce a mild -onniigullar assumption on the weight matrices of the target model and frozen model for the feasibility of our analysis. This assumption is mild, supported by Lemma 3 that even weight matrices initialized at random can meet this requirement.
Assumption 1 Non-Singularityy For fixed LoRA-rank R E [D], the weight matrices of the frozen model (Wi)=z and matrices (Thirr + LR, W; - Ihhp Wi) are non-singular for
all r S R(M - 1) and E (L].
Lemma 3. Let (W (Wi) from arbitrary contimoous distributions. Then, with probability 1, Assumption I holds VR E [D).
DxD be matrices whose elements are drawn independently
Given this assumption, here we present our first main result, which shows that any frozen FNN can be adapted to exactly approximate the target FNN via LoRA.
Theorem 3. Under Assumption if LoRA-rank R Z
[max rank(W, -.WW.-neee there exists rank-R R or lower matrices AW W...... AW L E DxD and bias vectors b,.... by Rd such that the low-rank adapted model f can exactly approximate the target model F. i.e., f(x) = [(x),, Va E X.
-IEr Wi)/M/ then
Moreover, combining Lemma and Theorem 3 gives the following corollary.
Corollary 4. Assume that the elements of (W (Wi) (Wi)t= are independently drawn from ar- bitrary continuous distributions. When R 2 D/M, with probability 1, there exists rank- R or lower matrices AW AW1.... AW E R DxD and bias vectors by...., by R. such that low-rank adapted model f can exactly approximate the target model f on X, i.e. f(x) = f(x). Vx E X.
To understand the implications of this corollary, let us consider L > L. this scenario, the required LoRA-ramh is sufficiently small such that the dimension of the rank- R matrix is approximately 2RD. This corollary suggests that with 2RDL 2 2 L/M 2s 2D2 T, learnable parameters, even a random FNN can be adapted into the target model F. It is noteworthy that the total number of parameters of the target model is D. This indicates that even though the learnable parameters under LoRA finetuning appear to be highly constrained (low-rank constrained learnable parameters distributed across many layers), the effective expressive power of LoRA is nearly optimal up constant factor of Our discovery provides the first theoretical insights into the practical success of LoRA. Furthermore, Theorem 3 indicates that if the model / 'close' to f such that max rank W;
Ihr Wi) is small, the number of learnable parameters used by LoRA can be lower than D²T.
Meanwhile, when the employed LoRA-ram is lower than the critical threshold, the following theo- rem provides an upper bound for the approximation error.
Theorem Define the approximation error of i-th layer as E, G (W; HHE Wi). and the magnitude of the parameters and the input as B
max (V +
W [B,ll2) V VIST.. Under Assumption 1, there exists rank-R R or lower matrices (AWi), with AW, RXD and bias vectors (bi)zn with E RD such that for input x E X' with Exx" E,
W 1 Ex) T- E.
E f[((x) - F(x) <
max L
Theorem 5 provides an upper bound on the approximation error for the adapted model. This bound influenced by several factors: (i) magnitude of the target model's parameters and the input, which

---

Published as a conference paper at ICLR 2024
is captured by & and [ |||| (ii) the rank of the adapter R. and the discrepancy between the frozen model and the target model (W; -lw.lleee Iher E both of which contribute to the term E,, (iii) the depth of the frozen model I., reflected in M and consequenly F4z-
All the proofs of the results derived for uniform partition are provided Sec. E.2.
General Model Partition. We note that employing this uniform partition strategy for approxi- mating the target model may not always yield optimal results. To illustrate this, we revisit the case considered by Example 1, where == 2 and I. 4. Consider scenario where the first layer of the frozen model has been pretrained to match the first layer of the target model. In this case, we can use just the first layer in to approximate the first layer in f. and a zero LoRA-rank is sufficient for the exact representation of the first layer. The remaining three layers in f can then be used to approximate the second layer f. Compared to uniform partition, this partition leverages more layers approximate the second layer in f. allowing to achieve the desired performance with a lower LoRA-rank, as per Lemma 2. This suggests that our approximation error bounds could be further optimized by considering partitioning schemes tailored to specific scenarios.
We now extend our results to a more general setting, where we do not assume a uniform parti- tion. Concurrently, recent research by Zhang et al. (2023) has shown that the application of varying LoRA-ranks leads to improved results. Consequently, we permit each layer in the frozen model to utilize adapters with different LoRA-ranks. The rank of the LoRA adapter associated with the 1-th layer in the frozen model is denoted by R₁, where E [Z]. This result relies on Assumption 2, an analog of Assumption but revised to include general model partition, More details, including the proofs, are provided in Sec. E.3.
Theorem 6. Consider partition P for the frozen model. Let Assumption 2 hold. If EiEP, R 2 rank( W. -ILEP, Wi) all E [L], there exists LoRA adapters (AWi) with rank (an)) Ri and biases (bi) such that the adapted model can exactly approximate the target model.
Moreover, define the approximation error of the i-th layer as E, = HIEP. Wi). and the magnitude of the parameters and the imput as B ||silll Ej= I [ (6,11)) V VISTT
Eier, R (W;
max IL
Then, there exists LoRA adapters (AW (/ with rank(AW,)) S R4 and biases (bi)t such that for any input x E X with Exx E, the approximation error can be bounded
I
E [xx) F(x) 11 S 8
max (1 W| k + Ex) I-i E,. kE
Comparison to Tuning Final Layers. Updating the final layers and keeping the initial layers frozen (Chatfield et al., 2014; Donahue et al., 2014; Sharif Razavian et al., 2014; Rahimi & Recht, 2007) is another popular model adaptation method. However, unlike LoRA, which can adapt even randomly generated networks to match a target model, empirical studies (Kornblith et al., 2019) suggest that the effectiveness of final layers tuning heavily depends the quality of the initial layers. This indicates that merely tuning the final layers of randomly generated networks may not yield desirable performance. The following lemma rigorously supports this assertion, demonstrating that regardless of how the final layers are tuned, it is impossible to adapt a randomly generated model into even a one-layer FNN, a model of very low complexity.
Lemma 4. Let 2 2 and F be a one- one-layer target FNN. Assume that the elements of weight matrices (Wi)f= are independently drawn from arbitrary continuous distributions. With probability 1, for any tuning of the last L layers, + f.
In Corollary 4, we demonstrate that LoRA can adapt any randomly generated models match the target model, using at most twice the number learnable parameters as the target model. However, this lemma reveals that final layers tuning, even with L 1 times the learnable parameters of the target model, cannot achieve performance comparable to LoRA. In other words, LoRA requires at most 2RDL < 2 learnable parameters to achieve exact approximation, while final layers
7

---

Published as a conference paper at ICLR 2024
tuning fails to approximate the target model even with (L 1)D² learnable parameters. Therefore, when L 2 3, LoRA can deliver strictly superior performance than final layers tuning with the same or fewer parameters. This provides insights into the empirical observation that LoRA outperforms final layers tuning (Kaplun et al., 2023; Ding et al., 2023).
4 EXPRESSIVE POWER OF TRANSFORMER NETWORKS WITH LORA
4.1 PROBLEM SETTING
Transformer network, denoted as D. is composition of L. Transformer blocks and an output layer, parameterized by weight W. RR DxD Each transformer block comprises a H-head self- attention layer, parameterized by weight ((W), wise feedforward layer, parameterized by weight (W1t, W2 and bias (b b2) We assume that all weight matrices have a dimension of D x D, while the bias vectors are of dimension D.
Ob W W Kis W @i) followed by token-
We employ the same formulations of transformer blocks as Yun et al. (2020a), with one exception: exclude skip connections for analytical feasibility. As before, we use (e.g.. W 1)) represent the corresponding parameters for the target model, and A. (e.g., AW to represent the corre- sponding low-rank update. For TFN cases,we consider scenarios where both the frozen model and the target model have L Transformer blocks. For explicit formulation, please refer to Sec. F.2.
4.2 MAIN RESULTS ON TRANSFORMER NETWORKS
We now present main findings TFNs. The first result relies non-singularity assumption (Assumption 4) tailored for TFN. This assumption is mild, and models with randomly generated weights satisfy its criteria (Lemma 14). Further details are deferred to Sec. F.2.
The following theorem shows that adding LoRA adapters primarily to the self-attention layers en- ables the adapted model f to exactly approximate the target model f. This finding is consistent with recent observation made by Hu et al. (2022a), which indicates that a good performance can be achieved by adapting only the attention layers when applying LoRA to TFNs.
Theorem 7. Consider a given LoRA-rank R [D]. Let Assumption 4 hold. Let G, be the rank- based functionality gap to i-th transformer block (i E [L] output layer (i = L+ 1) defined in
(23). If R Z max{g[L+1] 2
Gt], then there exists low-rank adapters with rank lower than R E [D] vI. A... VH -H ;; 21,, AW, a with other low-rank adapters set to O,
((AW)) kI: AWA Qr. AW and updated bias vectors (bu,, ba))= such that for any X DxN, the adapted model exactly
approximates target model F, i.e., f(X) F(x).
Proof Sketch. The primary challenge for extending our analysis TFNs, similar FNN cases, is the nonlinearity introduced by softmax and ReLU. To manage this, we segment a sequence of transformer blocks based on the softmax and ReLU functions. Specifically, we align the output of attention scores before the softmax is applied, and then match the output of the first feedforward layer before ReLU applied.
The complete proof of Theorem 7 and results for randomly generated models can be found in Sec. F22 Mcanwhile, our results here are specifically for TFNs with multi-head attention layers. For TFNs with single-head attention layers, the construction of LoRA adapters differs due to the absence of Wh... Ös. Since the results are similar, we defer the problem setting and results for TFNs with single-head attention layers to Sec. F.I.
EXPERIMENTS
Recall that all our theoretical statements are based on our construction of the LoRA adapters pre- sented in their corresponding proofs. To validate these results, here empirically examine the relationship between approximation error and rank by integrating the LoRA adapters, which are constructed with the uniform partition in our proof, into the frozen model.
8

---

Published as a conference paper at ICLR 2024
Validation of Our LoRA Adapter Construction. We employ the Mean Squared Error (MSE) to assess the approximation error, comparing the MSE of the LoRA adapter as derived from the gradient update method with that from our construction. We consider linear models and FNNs with model dimension D = 16. For linear model cases, we set = 1, I. = 2, while for FNN cases, we set 7. = 2, I. = 4. We include two variants of the frozen model for fine-tuning: one with randomly initialized parameters (Random) and another pretrained on the target distribution (Pretrained).
Our results for linear model approximation and FNN ap- proximation via LoRA are depicted in Fig. 1a and 1b, re- spectively. Firstly, we observe that the MSE of both two cases is close to zero when R 2 D = 8, which cor-
Random
Preaained
Geadient Updat
0.2
MSE
L/L
roborates our claims. Meanwhile, a comparison between the left and right columns of Fig. Ia suggests that pre- training can further reduce the required rank to achieve near-zero approximation error. Furthermore, the curves of our construction align well with those of the gradient update method in linear model approximation cases, con- firming the optimality claimed Lemma 1. However, for FNN approximation cases, the gradient update method outperforms our construction in the small rank region. We conjecture that the suboptimality of our construction for this multi-layer FNN case could arise from unnecessar- ily matching the intermediate outputs of the frozen model with those of the target model during adapter construc-
0.0
12
16
12
16
Rank
(a) Linear model approximation.
Random
Presruined
0.02
Gradient Update
Our Casenntto
MSR
0.00
12
16 Rank
12
16
(b) FNN approximation.
Figure I: Approximation error (mea- sured by MSE) versus LoRA-rank.
tion. Additionally, the uniform partition could also be one contributing factor.
Findings
Empirical Observation
Theoretical Insights
For a fixed downstream task. larger models require lower LoRA-rank to achieve the desired performance.
Sec. G.9
Lemma 2. and Theo- rem 6,
When the frozen model is closer the target model. lower LoRA-rank is sufficient to attain the desired per-
Sec. G.9 and 6-th footnote Hu et al. (2022a)
Lemma and Theo- rem 5. 6.
formance.
LoRA outperforms final layers tuning if the quality of shared representation is nol good.
Sec. G.4 and observations by Kaplun et al. (2023) and Ding el al. (2023)
Lemma 4
addition to applying low-rank updates to weight matri- ces, it is crucial to also update the bias.
Sec. G.5 and 2-nd foutnote Hu et al. (2022n)
Proofs Sec. 3.2 and E.1
Tuning attention weights sufficient for achieving good performance on TINs.
Sec. Hu et (2022a)
Theorem 7
Current optimization algorithms for LoRA training might be suboptimal.
Fig. 4. and
Table I: Summary of our findings, supported by empirical evidence and theoretical results.
Detailed Experimental Setup and Additional Experiments in the Appendix. Further experi- ment details and a series of additional experiments, including simulations FNNs and TFNs at different depths, evaluation of classification tasks, empirical comparison between LoRA and the final layers tuning, investigation of the importance of updatable bias, LoRA's generalization and optimization properties, and experiments on GLUE benchmark (Wang et al., 2018), are provided in Sec. G. Table summarizes all the empirical findings and aligns them with theoretical insights.
6 CONCLUSIONS
This work pioneers the theoretical analysis of LoRA fine-tuning's expressive capabilities in FNNs and TFNs, offering novel insights into how rank, model depth. and proximity to the target model influence LoRA's effectiveness. Our theoretical findings are validated by empirical evidence. Future work includes quantifying approximation errors for TENs when the LoRA-ranks are lower than required and refining LoRA adapter update algorithms based our construction of LoRA adapters.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENT
This work was supported by NSF Award DMS-2023239, NSF/Intel Partnership on Machine Learn- ing for Wireless Networking Program under Grant No. CNS-2003129, and a grant by FuriosaAI. We extend our heartfelt gratitude to Angeliki Giannou, Kartik Sreenivasan, Tuan Dinh, Jy-yong Sohn, Jingpeng Liu, and anonymous reviewers for their insightful comments that significantly enhanced the quality of our paper.
REPRODUCIBILITY STATEMENT
The code for all experiments reported in this paper is publicly accessible. For the purpose of producibility, the code can be found at the following anonymized GitHub repository: https: //github. com Mand-ooddo-----o Leee-Lab/Eapeessiveeeeeeee
REFERENCES
Kwangjun Ahn, Xiang Cheng, Hadi Daneshmand, and Suvrit Sra. Transformers learn to implement preconditioned gradient descent for in-context learning. arXiv preprint arXiv:2306. 00297, 2023,
Ekin Akyürek, Dale Schuurmans, Jacob Andreas, Tengyu Ma, and Denny Zhou. What learning algorithm is in-context learning? Investigations with linear models. In International Conference on Learning Representations (ICLR), 2023.
Yu Bai, Fan Chen, Huan Wang, Caiming Xiong, and Song Mei. Transformers statisticians: Prov- able in-context learning with in-context algorithm selection. arXiv preprint arXiv:2306.04637 2023.
Peter L Bartlett and Shahar Mendelson. Rademacher and Gaussian complexities Risk bounds and structural results. In Computational Learning Theory (COLT), volume 2111, pp. 224-240, 2001.
Elad Ben Zaken, Yoav Goldberg, and Shauli Ravfogel. BitFit: Simple parameter-effiee fine- tuning for Transformer-based masked language-models. In Annual Meeting of the Association for Computational Linguistics (ACL), pp. 1-9, 2022.
Yoshua Bengio and Olivier Delalleau. On the expressive power of deep architectures. In Algorithmic Learning Theory, pp. 18-36, 2011.
Alberto Bietti and Francis Bach. Deep equals shallow for ReLU networks in kernel regimes. 2021.
Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhari- wal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert- Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
Richard Caron and Tim Traynor. The zero set of polynomial. WSMR Report, 2005.
Ken Chatfield, Karen Simonyan, Andrea Vedaldi, and Andrew Zisserman. Return of the devil in the details: Delving deep into convolutional nets. arXiv preprint arXiv: 1405.3:405.353/ 2014.
Pin-Yu Chen. Model reprogramming: Resource-efficient cross-domain machine learning. arXiv
preprint arXiv:2202. 10629, 2022.
George Cybenko. Approximation by superpositions sigmoidal function. Mathematics of control, signals and systems, 2:303-314, 1989.
Tim Dettmers, Artidoro Pagnoni, Ari Holtzman, and Luke Zettlemoyer. QLoRA: Efficient finetuning of quantized Ilms. arXiv preprint arXiv:2305.1433 14314, 2023.
10

---

Published as a conference paper at ICLR 2024
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of deep bidirectional Transformers for language understanding. In North American Chapter of the Asso- 2019.
ciation for Computational Linguistics (NAACL), pp.
Ning Ding, Yujia Qin, Guang Yang, Fuchao Wei, Zonghan Yang. Yusheng Su, Shengding Hu, Yulin Chen, Chi-Min Chan, Weize Chen, Jing Yi, Weilin Zhao, Xiaozhi Wang, Zhiyuan Liu, Hai-Tao Zheng, Jianfei Chen, Yang Liu, Jie Tang, Juanzi Li, and Maosong Sun. Parameter-efficient fine- tuning of large-scale pre-trained language models. Nature Machine Intelligence, 5(3):220-235, 2023.
Tuan Dinh, Daewon Seo, Zhixu Du, Liang Shang, and Kangwook Lee. Improved input reprogram- ming for GAN conditioning. arXiv preprint arXiv:2201. 026920 2022a.
Tuan Dinh, Yuchen Zeng, Ruisu Zhang, Ziqian Lin, Michael Gira, Shashank Rajput, Jy-yong Sohn, Dimitris Papailiopoulos, and Kangwook Lec. LIFT: Language-imterfaced fine-tuning for non- language machine learning tasks. Advances in Neural Information Processing Systems (NeurIPS), 35:1 1763-77331774, 2022b.
Jeff Donahue, Yangqing Jia, Oriol Vinyals, Judy Hoffman, Ning Zhang, Eric Tzeng, and Trevor Darrel. DeCAF: A deep convolutional activation feature for generic visual recognition. In Inter- national Conference on Machine Learning (ICML), pp. 647-655, 2014.
Simon S Du, Wei Hu, Sham M Kakade, Jason D Lee, and Qi Lei. Few-shot learning via learning the representation, provably. In International Conference on Learning Representations (ICLR), 2021.
Carl Eckart and Gale Young. The approximation of one matrix by another of lower rank. Psychome- trika, 1936.
Ronen Eldan and Ohad Shamir. The power of depth for feedforward neural networks. In Anmual Conference on Learning Theory, volume 49, pp. 907-940, 2016.
Gamaleldin F Elsayed, Ian Goodfellow, and Jascha Sohl-Dickstein. Adversarial Reprogramming of neural networks. In International Conference on Learning Representations (ICLR), 2019.
Jesse Engel, Matthew Hoffman, and Adam Roberts. Latent constraints: Learning to generate condi- tionally from unconditional generative models. In International Conference Learning Repre- sentations (ICLR), 2018
Matthias Englert and Ranko Lazic, Adversarial Reprogramming revisited. In Advances in Neural Information Processing Systems (NeurIPS), volume 35, pp. 28588-28600, 2022.
Ying Fan, Olivia Watkins, Yuqing Du, Hao Liu, Moonkyung Ryu, Craig Boutilier, Picter Abbeel, Mohammad Ghavamzadeh, Kangwook Lee, and Kimin Lee. DPOK: Reinforcement learning for fine-tuning text-to-image diffusion models. arXiv preprint arXiv:2305. 16381, 2023.
Angeliki Giannou, Shashank Rajput, and Dimitris Papailiopoulos. The expressive power of tuning only the Norm layers. arXiv preprint arXiv:2302.07937, 2023a.
Angeliki Giannou, Shashank Rajput, Yong Sohn, Kangwook Lee, Jason D. Lee, and Dimitris Papailiopoulos. Looped Transformers as programmable computers. In International Conference on Machine Learning (ICML), volume 202, pp. 11398-11442, 2023b.
Michael Gira, Ruisu Zhang, and Kangwook Lee. Debiasing pre-trained language models via effi- cient fine-tuning. In Workshop on Language Technology for Equality, Diversity and Inclusion, pp. 59-69, 2022.
Moritz Hardt and Tengyu Ma. Identity matters in deep learning. In International Conference on Learning Representations, 2017.
Pengcheng He, Xiaodong Liu, Jianfeng Gao, and Weizhu Chen. DeBERTa: Decoding encande BERT with disentangled attention. In International Conference on Learning Representations, 2021.
11

---

Published as a conference paper at ICLR 2024
Kurt Homik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks are uni- versal approximators. Neural Networks, 2:359-366, 1989.
Daniel Hsu, Clayton H Sanford, Rocco Servedio, and Emmanouil Vasileios Vlatakis Vlatakis-Gkaragkee Gkaragkounis. On the approximation power of two-layer networks of random ReLUs. In Conference on Learning Theory, volume 134, pp. 2423-2461, 2021.
Edward J 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 International Con- ference on Learning Representations (ICLR), 2022a.
Shengding Hu, Zhen Zhang, Ning Ding, Yadao Wang, Yasheng Wang, Zhiyuan Liu, and Maosong Sun. Sparse structure search for delta tuning. In Advances in Neural Information Processing Systems (NeurIPS), volume 35, pp. 9853-9865, 2022b.
Like Hui and Mikhail Belkin. Evaluation of neural architectures trained with square loss vs cross- entropy classification tasks. In International Conference on Learning Representations, 2021.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and gen- eralization in neural networks. Advances neural information processing systems, 31, 2018.
Gal Kaplun, Andrey Gurevich, Tal Swisa, Mazor David, Shai Shalev-Shwartz, and Eran Malach. SubTuning: Efficient finetuning for multi-task learning. arXiv preprint arXiv:2302.06335 2023.
Kenji Kawaguchi. Deep learning without poor local minima. Advances in neural information pro-
cessing systems, 29, 2016.
Simon Kornblith, Jonathon Shlens, and Quoc V Le. Do better ImageNet models transfer better? In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, 2019.
Thomas Laurent and James von Brecht. Deep linear networks with arbitrary loss: All local minima are global. In Proceedings of the 35th International Conference on Machine Learning, volume 80, 2018
pp.
Holden Lee, Rong Ge, Tengyu Ma, Andrej Risteski, and Sanjeev Arora. On the ability of neural nets to express distributions. In Conference on Learning Theory, pp. 1271-1296, 2017.
Kangwook Lee, Changho Suh, and Kannan Ramchandran. Reprogramming GANs via input noise design. In Machine Learning and Knowledge Discovery in Databases European Conference, (ECML PKDD), volume 12458, pp. 256-271, 2020.
Brian Lester, Rami Al-Rfou, and Noah Constant. The power of scale for parameter-efffiient prompt tuning. In Empirical Methods in Natural Language Processing (EMNLP), pp. 3045-3059, 2021.
Xiang Lisa Li and Percy Liang. Prefix-tuning: Optimizing continuous prompts for generation. In As- sociation for Computational Linguistics and International Joint Conference on Natural Language Processing (ACL/ICCNLP), pp. 4582 4597, 2021.
Shiyu Liang and R. Srikant. Why deep neural networks for function approximation? In International Conference on Learning Representations (ICLR), 2017.
Valerii Likhosherstov, Krzysztof Choromanski, and Adrian Weller. On the expressive power of self-attention matrices. 2021.
Chaoyue Liu, Libin Zhu, and Mikhail Belkin. Loss landscapes and optimization in over- parameterized non-linear systems and neural networks. Applied and Computational Harmonic Analysis, 59:85-1185 116, 2022a.
Haokun Liu, Derek Tam, Mohammed Muqeeth, Jay Mohta, Tenghao Huang, Mohit Bansal, and Colin A Raffel. Few-shot efffmeter-efffcient fine-tuning is better and cheaper than in-context learning. In Advances Neural Information Processing Systems (NeurIPS), volume 35, pp- 1950-1965, 2022b.
12

---

Published as a conference paper at ICLR 2024
Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer. and Veselin Stoyanov, RoBERTa: A robustly optimized bert pretraining approach. arXiv preprint 1tXiv:1907.116999 2019.
Haihao Lu and Kenji Kawaguchi.
Depth creates no bad local minima. arXiv preprint
arXiv:/702.08580 2017.
Zhou Lu, Hongming Pu, Feicheng Wang, Zhiqiang Hu, and Liwei Wang. The expressive power of neural networks: A view from the width. Advances in neural information processing systems, 30, 2017.
Sadhika Malladi, Alexander Wettig, Dingli Yu, Danqi Chen, and Sanjeev Arora. A kernel-based view of language model fine-tuning. In International Conference on Machine Learning, pp- 23610 23641,, 2023.
Andreas Maurer, Massimiliano Pontil, and Bernardino Romera-Paredes. The benefit of multitask representation learning. Journal of Machine Learning Research, 17(81):1-32, 2016.
Leon Mirsky. Symmetric gauge functions and unitarily invariant norms. The quarterty journal of mathematics, 1960.
OpenAl. GPT-4 technical report. 2023.
Samet Oymak, Ankit Singh Rawat, Mahdi Soltanolkotabi, and Christos Thrampoulidis. On the role of attention in prompt-tuning. In International Conference on Machine Learning (ICML), 2023.
Sejun Park, Chulhee Yun, Jacho Lee, and Jinwoo Shin. Minimum width for universal approximation. In International Conference on Learning Representations (ICLR), 2021.
Jorge Pérez, Javier Marinković, and Pablo Barceló. On the turing completeness of modern neural network architectures. arXiv preprint arXiv: 1901.09990. 2019.
Aleksandar Petrov, Philip HS Torr, and Adel Bibi. When do prompting and prefix-tuning work? A theory of capabilities and limitations. arXiv preprint arXiv:2310. 19698, 2023.
Maithra Raghu, Ben Poole, Jon Kleinberg, Surya Ganguli, and Jascha Sohl-Dickstein. On the expressive power of deep neural networks. International Conference on Machine Learning (ICML), pp. 2847-2854, 2017.
Rahimi and Benjamin Recht. Random features for large-scale kernel machines. Advances in Neural Information Processing Systems (NeurIPS), volume 3, pp. 5, 2007.
Simo Ryu. Low-rank adaptation for fast text-to-image diffusion fine-tuning. https://giste
com/ cl oneofs im /lora, 2023.
Andrew M Saxe, James L McClelland, and Surya Ganguli. Exact solutions to the nonlinear dynam- learning in deep linear neural networks. 2014.
Daewon Seo, Hongyi Wang, Dimitris Papailiopoulos, and Kangwook Lee. Empirical study on the effective VC dimension of low-rank neural networks. In ICML Workshop Overparaneteriza- tion: Pitfalls & Opportunities, 2021.
Ali Sharif Razavian, Hossein Azizpour, Josephine Sullivan, and Stefan Carlsson. CNN features off-the-shelf: An astounding baseline for recognition. Proceedings of the IEEE conference on computer vision and pattern recognition workshops, pp. 806-813, 2014.
Haizhao Shen, Zuowei Yang and Shijun Zhang. Deep network approximation characterized by num- ber of neurons. Communications in Computational Physics, (5); 176-118818 2020.
Matus Telgarsky. Representation benefits of deep feedforward networks.
arXiv preprint
/509. 1011, 2015.
Matus Telgarsky. Benefits of depth in neural networks. Conference on Learning Theory, pp- 1517-1539, 2016.
13

---

Published as a conference paper at ICLR 2024
Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, Aurélien Rodriguez, Ar- mand Joulin, Edouard Grave, and Guillaume Lample. LLaMA: Open and efficient foundation language models. arXiv preprint 2r0iv:2302. 13971, 2023.
Nilesh Tripuraneni, Michael Jordan, and Chi Jin. On the theory of transfer learning: The importance of task diversity. In Advances in neural information processing systems (NeurIPS), volume 33, pp. 7852-7862, 2020.
Rasul Tutunov, Antoine Grosnit, Juliusz Ziomek, Jun Wang, and Haitham Bou-Ammar, Why can large language models generate correct chain-of-thoughts? arXiv preprint 1XXi:23300.13571 2023.
Vladimir N Vapnik and A Ya Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. In Measures of Complexity: Festschrift for Alexey Chervonenkis, pp. 11-30. 2015.
Johannes von Oswald, Eyvind Niklasson, Ettore Randazzo, João Sacramento, Alexander Mordy- intsev, Andrey Zhmoginov, and Max Vladymyrov. Transformers learn in-context by gradient descent. arXiv preprint arXiv:2212.07677 2022.
Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel Bowman. GLUE: A multi-task benchmark and analysis platform for natural language understanding. In EMNLP Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP, pp. 353-355, 2018.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, brian ichter, Fei Xia, Ed H. Chi, Quoe V Le, and Denny Zhou. Chain of thought prompting elicits reasoning in large language models. In Advances Neural Information Processing Systems (NeurIPS), 2022.
Noam Wies, Yoav Levine, and Amnon Shashua. The learnability of in-context learning. arXiv preprint arXiv:2303.07899 2023.
Sang Michael Xie, Aditi Raghunathan, Percy Liang, and Tengyu Ma. An explanation of in-context learning as implicit bayesian inference. In International Conference on Learning Representations (ICLR), 2022.
Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank Reddi, and Sanjiv Kumar. Are Transformers universal approximators of sequence-to-sequene functions? In International Con- ference on Learning Representations (ICLR), 2020a.
Chulhee Yun, Yin-Wen Chang, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank Reddi, and San- jiv Kumar. O(n) connections expressive enough: Universal approximability of sparse trans- formers. 33:13783-13794, 2020b.
Qingru Zhang, Minshuo Chen, Alexander Bukharin, Pengcheng He, Yu Cheng, Weizhu Chen, and Tuo Zhao. Adaptive budget allocation for darameter-efficite fine-tuning In The Eleventh Inter- national Conference on Learning Representations, 2023.
14

---

Published as a conference paper at ICLR 2024
Appendix
This appendix encompasses more discussions, experiments, and proofs of the results presented in the main body. Given the extensive use of notations in our paper, we begin by presenting list of common notations in Sec. for the reader's convenience. We then delve into a more detailed discussion of related works in Sec. B. Following this, present the proofs of results from the main body and auxiliary results Sec. C, D, E,, and F. Specifically, we provide additional results for TFN with single-head attention layers, and TFN with multi-head attention layers under random model cases in Sec. F. Further experimental details and interesting experiment findings are provided in Sec. G. Finally, we discuss how to extend our results to cases with varying model dimensions in Sec. H, while this work primarily focuses on instances where both the target model and the frozen model possess the same model width D. More potential future works outlined in Sec. I.
A List of Common Notations
17
B Expanded Related Works
18
C Proofs Related to Linear Algebra
19
C.I Common Matrix Inequalities
19
C.2 Non-Singularity of Randomly Generated Matrices
19
Proofs for Linear Model Approximation
20
Proofs for FNN Approximation
25
E.1
Approximating One-Layer ReLU FNN via LoRA
25
E,2
Approximating Multi-Layer ReLU FNN via LoRA with Uniform Model Parition
27
E.3 Approximating Multi-Layer ReLU FNN via LoRA with General Model Parition
31
E,4
Approximating Multi-Layer ReLU FNN via Final Layers Tuning
32
F Proofs for TEN Approximation
33
F.I Approximating Transformer Network with Single-Head Attention Layers
33
F2 Approximating Transformer Network with Multi-Head Attention Layers
36
G Experiments
39
G.I Additional Details of Experiment Setup
40
G.2 Additional Details on Gradient Update Method
40
G.3 Validation of Our LoRA Adapter Construction
40
G.3.1 FNN Approximation
40
G.3.2 TFN Approximation
G.4 Comparison to Tuning Final Layers
42
G.5 Benefits of Tuning Biases
42
G.6 Training Curves
42
G.7 Generalization Performances
43
G.8 Evaluation on Classification Tasks
43
G.9 Evaluation on Real Datasets
44
15

---

Published as a conference paper at ICLR 2024
H Extension to Cases with Different Model Dimensions
45
Extended Future Works
46
16

---

Published as a conference paper at ICLR 2024
A LIST OF COMMON NOTATIONS
We first give a list of common notations that are used in the main body and appendix for reference.
f: LoRA-adapted model.
target model.
fo: frozen/pretrained model.
R: rank of LoRA adapters.
D: dimensionality of the model, representing the number of neurons in each layer for FNNs and the embedding size for TFNs.
L: depth of the (frozen) model, representing the number of layers for FNNs and the number of transformer blocks for TFNs.
N: sequence length of the input for TFNs.
x: input.
x: random input.
X: matrix input.
X: input space.
Σ: ExxT.
W: a weight matrix associated with (frozen) model. Subscripts and superscripts may be added for specificity.
b: bias vector associated with the (frozen) model. Subscripts may be added for specificity.
žj: the output of the first / layers in the (frozen) FNN.
Z the output of the first / transformer blocks in (frozen) TFN.
W: weight matrix associated with the target model. Subscripts and superscripts may be added for specificity.
b: bias vector associated with the target model. Subscripts may be added for specificity.
Z: the intermediate output of the first / layers in target FNN given the random input
Z₁ the output of the first I transformer blocks in target TFN.
L: depth of the target model, representing the number of layers for FNNs and the number of transformer blocks for TFNs.
W: the weight matrix of LoRA adapter.
b: bias vector associated with the LoRA-adapted model.
ū the output of the first layers in the LoRA-adapted model given the random input
Zi: the output of the first transformer blocks in the LoRA-adapted model.
M: the ratio of the depth of the frozen model to that of the target model, i.e., L/L.
P: partition p = .PI,.... P each element P; specifies that the layers with index E P; in the adapted model will be used approximate the i-th layer in the target model.
P:: the i-th element in partition P.
pu: uniform partition pD ff1. M). {M + +,. 1,.... 2M The uniform partition indicates that every M layers in the adapted model are employed to approx- imate each layer in the target model.
{(L 1)M 11.... L }.
Pa. the i-th element in uniform partition pu
Ip: the D x D identity matrix. When the context permits, the subscript D of Ip may be omitted, simplifying the notation to I.
La a diagonal matrix where the diagonal entries from the ath to öth position are set to 1, while Os.
all remaining entries
17

---

Published as a conference paper at ICLR 2024
(a(:): :: the d-th largest singular value for the given square matrix. When d is greater than the width of the matrix, oa(-) = O.
best rank-r approximation of square matrix in Frobenuis norm and spectral norm. The subscript may be omitted to indicate a general low-rank approximation without specifying the rank.
(:)(:):
Her, Wi: product of the weight matrices from the layers / E P., with the later layer positioned to the left and the earlier layer to the right in the matrix product. For example, Ihery Wi =
M Wi = WM .. W1.
B EXPANDED RELATED WORKS
Expressive Power of Fully Connected Neural Networks The theoretical exploration of the ex- pressive power of unfrozen fully connected neural networks has advanced since the introduction of the first universal approximation theorem (Hornik al., 1989; Cybenko, 1989). Subsequent studies have demonstrated the benefits of depth, asserting that sufficient depth can ensure function approxi- mation (Bengio & Delalleau, 2011; Eldan & Shamir, 2016; Liang & Srikant, 2017; Telgarsky, 2016; 2015). There are also works that have examined the expressive power of FNN from a view of width (Lu et al., 2017; Park al., 2021: Bietti & Bach, 2021) and the number of neurons (Shen & Zhang, 2020). While these results assume that weight matrices can be arbitrarily adjusted for optimal performance, Hsu et al. (2021) examined the expressive power of randomly generated two- layer FNNs. Our work shares similarities with this direction, as we also delve into scenarios with randomly generated models. Beyond characterizing expressive power by approximation error, alter- native metrics have been proposed. Metrics such as
(Vapnik & Chervonenkis, 2015; Sco et al., 2021) and Rademacher complexities (Bartlett & Mendelson, 2001) are utilized to assess classification capacity. Furthermore, Raghu et al. (2017) introduced novel metric that cap- tures the structural properties of an FNN, and Lee et al. (2017) investigated the ability of FNNs to express distributions.
Expressive Power of Transformers As TFNs have grown increasingly popular, a few studies have been conducted to investigate their expressive power. Yun et al. (2020a) established the universal approximation theorem for TFNs in approximating sequence-to-sequee et al. (2021) characterized the self-attention layer as a matrix and demonstrated that this matrix can approximate any sparse matrices. Beyond approximation, further research has delved into other facets of TFNs' expressive power. For instance. Giannou et al. (2023b) found that looped transform- ers can emulate instruction-set computer, while Pérez al. (2019) demonstrated that TFNs attain Turing completeness when operating with infinite precision.
functions. Likhosherstov
However, all these theories above cannot fully explain the performance of frozen neural networks as they generally cannot factor in pre-trained model parameters and adaptation methods.
Expressive Power of Adaptation Methods Our work focuses on investigating the expressive power of adaptation methods. In stark contrast to the flourishing research on the expressive power of neural networks, there exists a limited number of works investigating the expressive power of adap- tation methods. A notable exception is Giannou et al. (2023a), investigating the expressive power of normalization parameter fine-tuning. They demonstrate that fine-tuning the normalization layers alone can adapt a randomly initialized ReLU network to match any target network that is O(width) times smaller. We borrow some proof techniques from this work, including techniques for extending results from linear neural networks to ReLU neural networks. In another recent work (Englert & Lazic, 2022), the authors show that neural reprogramming (Elsayed et al., 2019; Engel et al., 2018; Lee al., 2020; Dinh al., 2022a; Chen, 2022), technique that modifies only the inputs while keeping the pretrained network frozen, can adapt any random two-layer ReLU network to achieve arbitrarily high accuracy on a Bernoulli data model over hypercube vertices. Oymak et al. (2023) explores prompt-tuning within one-layer attention architecture, revealing that the model result- ing from prompt tuning (Lester et al., 2021) is more expressive than the naive self-attention model. Petrov et al. (2023) shows that prompt-tuning and prefix tuning (Li & Liang, 2021) are strictly less expressive than full fine-tuning. Despite these early attempts, no existing study has yet explored the expressive power of LoRA, the current leading adaptation method.
18

---

Published as a conference paper at ICLR 2024
Other Theoretical Analysis of Adaptation Methods Lots of efforts have been taken to theoret- ically analyze other properties of adaptation methods such as generalization. Maurer et al. (2016) provides the generalization bounds for transfer learning, particularly for final layers tuning, demon- strating that the estimation error reduces as the pretrained task diversity and the number of samples for the target task increase. Tripuraneni et al. (2020) further refines this bound by studying the effect of the number of samples in the pre-trained tasks. Interestingly, the estimation error of the final layers tuning provided in Tripuraneni al. (2020) heavily depends on the quality of the shared rep- resentation. This insight aligns with our finding on final layers tuning (Lemma 4), which implies that tuning the final layers fails to adapt an L-layer randomly generated FNN approximate any one-layer target FNN if the first layer remains frozen. This failure is attributed to the poor qual- ity of the shared random representation. Du et al. (2021) further investigates final layers tuning in few-shot cases, i.e., when there are only few samples for the target task. A recent study by Malladi et al. (2023), which examined LoRA and full fine-tuning through the lens of the Neural Tangent Kernel (Jacot et al., 2018), suggested that if the kernel view describes full fine-tuning, then LoRA approximates full fine-tuning. However, their theoretical analysis of LoRA is based on linear models, thus limiting its applicabiliity. In contrast, study considers more general setting.
With the rapid advancement of large language models, new adaptation methods such as in-context learning (Brown al., 2020), prefix tuning, and prompt-tuning (Lester al., 2021) gaining increasing attention. A particular focus of research the exploration of the theoretical underpinnings of in-context learning (Akyürek et al., 2023; Bai al., 2023; Wies al., 2023; Xie et al., 2022: von Oswald et al., 2022: Ahn et al., 2023). Akyürek et al. (2023) demonstrates that transformer-basee context learners implicitly implement standard learning algorithms, while Bai al. (2023) presents a similar finding and posits that in-context learning performs algorithm selection like statistician. Wies et al. (2023) delves into the analysis of the sample complexity of in-context learning. Other works find that in-context learning is equivalent to gradient descent (von Oswald et al., 2022: Ahn et al., 2023), and Bayesian inference (Xie et al., 2022). Beyond in-context learning, a recent research by Tutunov al. (2023) developed a theoretical framework elucidating how LLMs can accurately generate chain-of-thouuht reasoning (Wei et al., 2022).
in-
C PROOFS RELATED TO LINEAR ALGEBRA
In this section, we present a collection of commonly used matrix inequalities and the basic properties of randomly generated matrices.
C. COMMON MATRIX INEQUALITIES
Here, present some commonly used basic properties for matrix multiplication including rank computation, norm incqualities, as well as key results involving the trace and Frobenius norm of matrices for reference:
rank (AB) < rank( A) A rank BB);
| || S || A 2 ||=:|2
(I)
Ex Ax = Lr(ACov(x) (x)) + (Ex) T (Ex) = Ir(AExx]) T);
tr( TAAB) tr(BA);
tr(AB & tr(A)tr( B);
|||||p / /Ir(AAT):
||A]]] tr( for symmetric A;
||||| Σ (A).
C.2 NON-SINGULARITY OF RANDOMLY GENERATED MATRICES
Although the non singuuagul of randomly generated matrices is already established, we include a proof for completeness.
19

---

Published as a conference paper at ICLR 2024
To facilitate the proof, we introduce lemma which states that if polynomial is non-zero, then the set of roots corresponding to a zero value of the polynomial has a Lebesgue measure of zero.
Lemma (Caron & Traynor (2005)). Let p(æ) be a polynomial of degree d, R.. !fp is not the zero polynomial, then the set S == {x R" p(z) 0} is of Lebesgue measure zero.
We note that the determinant of matrix can be viewed as polynomial function of its vectorized version. Based on this insight, we proceed with our proof.
Lemma 6. Let X DxD be a random matrix that follows arbitrary continuous distribution with support having non-zero Lebesgue measure on TR. DxD. Then, X is non-singular with probability I.
Proof of Lemma 6. The result is a direct consequence of Lemma Let x veo(X). Then, x is random vector following arbitrary continuous distribution with support having non-zero Lebesgue measure on IR DxD.
First, we establish the relationship:
IP (X) = 0) = IP (p(x) 0)
for some polynomial function p. We denote the support of random vector x by X' C R and the probability density function (PDF) of x by q. Then,
(p(x) 0) = / (p(x) =0 g(x))dx= Jx (xx)dxx.
By Lemma 5, the Lebesgue measure of fxr p(xx) 0} is zero. Hence,
Jxntepttezo ((x) dx = 0.
By combining all the equations above, we conclude that ("det(() = 0) = 0, which implies X is non-singular with probability 1.
D PROOFS FOR LINEAR MODEL APPROXIMATION
In this section, we present the results and corresponding proofs for the linear model approximation problem introduced in Sec. The deep linear model common technique in theoretical deep learning research, which offers valuable insights into deep nonlinear models, and has been employed many notable studies, including those by Saxe et al. (2014); Kawaguchi (2016); Lu & Kawaguchi (2017); Hardt & Ma (2017) and Laurent & von Brecht (2018). We employ this toy model as preliminary model, which serves as foundation for extending our results to nonlinear models (i.e.. FNN and TFN).
We first provide slightly more detailed version of Lemma along with its proof. Then, we present variant of it that allows for different LoRA-ranks for each low-rank adapter. The proof for this variant involves only a minor modification of the proof for Lemma 7.
Lemma 7. [Detailed version of Lemma 1] Define error matrix E = W - Wi. and denote its rank by Rg = rank ()). For a given LoRA-rank R E [D], assume that all the weight matrices of the frozen model (Wi) and I W. LR, (E) are non-singular for all S R(L 1). Then, the approximation error
L [[ + AW,) W =ORL+1
L
min AWRRRRR
W
II
W
Error matrix
and the optimal solution to the matrix approximation problem satisfies I (W. + AWW)
The W. + LRRLARE (E). (E). Therefore, when R [RE] we have ITE (W, + AW)) W.
implying
20

---

Published as a conference paper at ICLR 2024
Proof of Lemma 7. Our goal is to find matrices AW 1: 1..... AWL of rank R lower such that the product of the adapted matrices approximates the target matrix well, i.e., we aim to solve the following constrained optimization problem:
L
I[w [[w++Ww)> W
min
W Frank( WIR
By subtracting I
Wi from both terms, the constrain optimization problem becomes
min Wiin
[I + AWD
II
W
W
W
1=1
[=1
E
To perform analysis on (2), we start with the analysis of A as follows:
L
A
II AW
Wi)
II W
1=1
T-1
T-1 II [=1
A
II (AW Wi)
WE
(AW,
Wi)
II W.. 1=1
Here, we have separated the first term in the product IT (AW, + Wi), breaking it into two parts: one involving AW, and the other W.. We can further expand the part involving Wz:
L-1
A AW L
II (AW,- + W))
1=1
L-2
L-2 (AW, + wi)
+ W.
AW L-1 II
(AW, W)) + W
II
I..
1=1
[=1
1=1
At this point, it becomes clear that this expression can iteratively decomposed. Following this pattern, we express A
L-1
L-2
AWW II (AW W)) + WLAW L-1 1=1
II
(AW Wi
(3)
Wi Wi)
II Wi
[=1
W.AA (W. AW,
=
In this final form, A is decomposed as A Σ rank(AW,) < R. Consequently, rank(A) S Σ rank(Ai) RL.
1=1 A. It is important to note that rank(A,)
Then, the optimization problem (2) can be relaxed into low-rank approximation problem
(2) min
|A
(4)
2
Arrak((A) SRL
where the optimal solution is A LR (E) = E.. Therefore, if we can identify rank- Rt or lower matrices (A (AWi)f such that
[W, AW
II
W. LR W
WT).
(5)
E=1
21

---

Published as a conference paper at ICLR 2024
then effectively solve the matrix approximation problem defined in (2). Moreover, it is straightforward to verify that (5) directly implies all statements in this lemma. Therefore, our re- maining proof focuses proving (5).
Denote Rg = RL A Rg. To derive the explicit form of E', we first refer to the SVD of E as
E EUUDV
where U and V are orthonormal matrices and the first RØ diagonal entries of D are non-zero, with all remaining entries being zero. Based on this, E' expressed as
E' = -UDDDDDV
Having already derived the decomposition A - A., we next aim to decompose E' as E'
Σ E' E'Q,, where Qi...... Q E DxD The goal now shifts to identifying AW Qi such that A E for each E [7.]. Achieving this would complete the proof of (5).
Therefore, our goal becomes finding AW that
L...., AW, & with rank (an((WW)) S R for all / e [Z] such
A II W.)AW (W AW,)) = E'Q,, for all I [Z]. 1=1+1
(6)
One sufficient condition for achieving (6) that the decomposed matrices Q1. Qu and low-rank adapters A AW1 1...... AW L meet the following conditions:
Σ E'Q E
1-1 (w. AW.))
AW = II
for all E [4]
(8)
(=|+1
(=1
rank Lank(AV) (AW,) < R for all / E [Z] rank(W;- AW,) D, for all | []-1].
(9)
(10)
Here (7) describes decomposition of E', (8) provides one simple solution (6) when (10) holds, and (9) is the rank constraint the low-rank adapter. In particular, the (10) is used to ensure the invertibility of I (W, + ;W) for / E [L 1]. This condition is not necessary for / L the inverse of Wz + AW, & is not required for computing any low-rank adapters.
We will show that the matrices (Qi)fz defined by
(( V for all / [Z].
(11)
and AW, defined by (8) for all E [L] satisfies the all four conditions (7), (8), (9), and (10). We note that the definition of (Qi/=, clearly satisfies condition (7). For the remaining conditions, namely (8), (9), (10), we proceed the proof by induction.
When / 1. We begin by examining the three conditions (8), (9) and (10) under the base case I 1. We first determine Q1 and AW, based on (11) and (8):
AW
①I w.) -E Q Q II:R, 1=2
(12)
By the choice AW,, 1, we satisfy the condition (8). Moreover, it directly follows that rank( (Qn) = R, thereby fulfilling the rank constraint in (9).
22

---

Published as a conference paper at ICLR 2024
Therefore, we just need to prove that W + A is full-rank, required by condition (10). To
compute rank( W1 + AW 1). we proceed as follows:
rank 1 + 1
L
(12)
rank
W
E')-1
(Substituting for AW1)
2=2
rrank( II W. E'Q1)
(Left multiplying with invertible II W
I.
-rank(( II Wi) LRRAR (E)).
(Simplifying)
Given the assumption that IT Wi (E) is full rank for all S R(I. - 1), rank W1 +
1 = rank(([[ W;) + LA Rg (E)) D, satisfying the last condition (10).
When 1 > 1. Consider == 2, L. We assume that for i E [t- 17-1]. Q: and AW; based on (11) and (8), respectively, and we assume that they satisfy the conditions
1]. we have determined matrices
(8), (9), and (10).
First, under the induction assumption that W; + AW, is invertible for all [ - 1], to achieve A, = E' Qi,, we set AW, based (8). This definition ensures (ank(AW,) I rank(Qu) R. thereby satisfying the condition (9). To prove that Wi+ AWW is full-rank (condition (10)), we focus computing rank Wi + AW1). We proceed as follows:
rank W/ AW,)
(8)
rank(W; II W.)-'E'Q (
(W AAW))-
(Substituting for AW;)
i=1+1
1-1
rank(Ip + ( W.) (
(w. -
(Left multiplying invertible W,
f=1
rank [w, AW II W,) -W))-EE'Q)) Q:)
(Right multiplying invertible I AW,)
1-2
L
rank WWi-+AWW
(W AW +
II
W.) (..)''''Qi) E'Q.))
(Rearranging terms)
1=1
[=1
1-2
rank
(Wi-i+ [I
-
[[ ( + AW
[
1=1
+ [I (T.:)-''Q.) E'Qi)
(Substituting for A I-))
i=1
1-2
rank
II 11-1
W; + E'Q [ ( AW.)) II
(w: AW.)
1=1
L (Left multiplying II
+ +E'Qi)
W. i=l
rank
Il
w. w. [... + AW. + E -E'II
(Rearranging terms)
-=-1
1=1
23

---

Published as a conference paper at ICLR 2024
=rank( I W.
E' Σ Q1)
(Taking similar steps)
i=1
rank(
I W, LRRIAR E)).
(Simplifying)
1=1
By the assumption that Ih Wi + (R) is full-rank for r S R(L 1) and consequently, rank(W; IW rank W. + LRRAAR (E)) D, satisfying the last condition (10).
Conclusion of Inductive Proof. Thus, by induction, we show that the definitions of (AW)) in (8) and (Qi) in (11) ensure that A, E"Q; for all / [L]. Summing over from to L satisfies condition (5), thereby completing the proof.
The following lemma extends the results to more general setting where different LoRA-ranks can be employed across layers.
Lemma 8. Define error matrix == W I W. and denote its rank by Rø = rank( E). For a sequence of LaRA-ranks for all layers (Ri) assume that all the weight matrices of the frozen model (Wi) and I1 Wi LR, (E) are non-singular for all v S SEE R4. Then, the approximation error
I.
min AW Awaaaak(AWWJSS.. [[ W = =0
W W
R+1
1=1
Error matrix E
and the optimal solution to the matrix approximation problem satisfies I ( + AW)) =
I Wi LL B.)Ang (E). Therefore, when Σ Ri 2 Rg. have II (W:+WW W. implying f =
Proof of Lemma 8, The proof follows the same steps of Lemma with only minor modifications.
In the current setting, we target the following constrained optimization problem:
min AW ww..snk(AW.)ss
[[ + AW,
W
1=1
where we allow each LoRA adapter AW; can possess different LoRA-ranks Ri, i.c., rank(AW,) < Rr l E [L]. Subtracting II Wi from both terms leads us similar constrained optimization problem as (2). The only distinction lies the rank constraint:
min AW Cww.
(w. + AW
II wi 1=1
W
I I=1
W
(13)
Following the same steps, we decompose A into (3), Given that rank(A,) S rank(AW,) < Rs we deduce that rank A)) < Σl= rank(A)) s Ele Rj. Consequently, the optimization problem above can be eased into low-rank approximation problem analogous (4):
(13) >
min Arran(
||A 1A-E/l
R
where the optimal solution A LR RJARS EE) = E'. Therefore, we can identify the LoRA adapters (AW, e with rank Monk(WW) W, < RS such that
(W. AW))
II 1=1
W Wi). w, LR EL RIARE
1=1
24

---

Published as a conference paper at ICLR 2024
the proof is completed.
The remaining part the proof adheres to the steps outlined in the proof of Lemma deriving (5). The only difference that we consider a different selection of (Qi)l 1 that satisfies (9) here:
Q: = -I ( R.)ARgr R.)ARR. R.).Rgr. V
Applying the same steps with this change yields the desired outcomes.
This lemma illustrates that in linear cases, the total number of parameters needed to achieve an exact approximation is constant, regardless of LoRA-rank assignment. It suggests that applying LoRA-rank of R per layer is equivalent to applying LoRA-rank of RL at the final layer. As result, fine-tuning only the last layer, which involves assigning a LoRA-rant of to the last layer, is equivalent implementing LoRA where each adapter is constrained to have rank of L.. Both methods can achieve an exact approximation and maintain the same parameter efficiency.
E PROOFS FOR FNN APPROXIMATION
In this section, we provide full proof for deriving the main results outlined in Sec. 3. For sake of completeness, restate results from the main body before presenting the proof.
E. APPROXIMATING ONE-LAYER RELU FNN VIA LORA
We first provide a slightly more detailed result on the one-layer ReLU FNN approximation (Lemma 9) along with its corresponding proof. Then, present variant of this lemma by al- lowing for different LoRA-ranks for each low-rank adapter. The proof for this variant involves only minor modification of the proof for Lemma
Lemma 9 (Detailed version of Lemma 2). Define error matrix E == W - Wi, with its rank represented by Rg = rank(P E). Consider LoRA-ran rank R E [D]. Assume that the weight matrices W....,, Wz E DxD and I Wi (R, (E) for all r S R(L-1 1) are non-singular, Let x be random input sampled from distribution with bounded support X and let Σ = Exx T. Then, there exists rank-R lower matrices such that for any input x X.
AW, E RDXD and bias vectors b b....., dr E RDD
(IRRLLATE W
f(x) =(ar)=ReLid ReLU
II Wi 1=1
W
II Wi) )x)) 1=1
Therefore, when R 2 [R [], the adapted model exactly approximates the target model, i.e., f(x) = F(xx for all x E X.
Furthermore, let be a random input sampled from a distribution with bounded support X and let Σ = TxxT Then, the expected squared error is bounded
E [lf((x) - F(x))12 & |E RLABE W
II Wi).
Proof of Lemma 9. This proof consists of three main steps: (i) linearize the first L 1 layers of the adapted model f to reduce it to single-layer FNN, (ii) align the weight matrices and bias vectors of this simplified if with those of the target model J, (iii) derive an upper bound of the error -[x f(x) f(x))
The main challenge here stems from the non-linearities introduced by the ReLU activation function. To remove the non-linearities in the first L 1 layers of updated model f. since the input space X' is bounded,
Linearization.
all the entries of b,,. b,...., bay...,b.- b sufficiently large, thereby
25

---

Published as a conference paper at ICLR 2024
activating all ReLUs in the first L 1 layers of f. Consequently, have f())
ReLu((WE AW z)=(-1+ by)
ReLU
(WL (WL+ +
(WW.:-///BBLLLWLLL--AAA AW AW 62-1) + b1)
by-1) + bl.)
ReLU
ReLU
(W, (W.
(Wr AW i. 2,)0,-1 by.
1- 1 [[w + E II (W. (W, + +61 1=1 =1+
L
= ReLU
which is equivalent single-layer ReLU neural network with weight matrix I (Wi AW,) and bias vector (E L-1 II 1-44 (W; + AW, (.) + b2.
Parameter Alignment. To match the updated model f()) and target model f(z), we proceed as follows. For weight matrix, Lemma 7 guarantees the existence of rank-R lower matrices AW I...., AW, AW....,AW,
DxD such that
[I AW) II Wi LRRLARE W II wi).
(14)
For the bias vector, we set Dr. = = b II WW++AW, , such that AW,) .)bi + by. = bb, Therefore, we obtain
1==1
L-1
I1
(W,+
L [RRILLARE W - II Wi) (W, II
L
f(x)) - F(xr) = ReLU
Wi)
x
1=1
1=1
Error Derivation.
We compute the expected squared error as follows:
E fx) F(x))12
E
LRRIARE W
Wi)
(W
II
Wi)
(ReLU is 1-Lipschitz)
[=1
[=1
())
LRRLARE
W1
II 1=1
Wi
W
Wi
E ||x
1=1
= >| R W,
Wi).
(By the definition of LRRLARg (-))
1=1
This completes the proof.
Lemma is extended to cases where different LoRA-ranks can be used for different low-rank adapters, as detailed the following lemma.
Lemma 10. Define error matrix E W, ITE Wi, and denote its rank by RØ rank E). Consider sequence of LoRA-ranks (Ri) Assume that the weight matrices W...., Wi. DDD and I'= WR, for all Σ'=! R4 are non-singular. Then, there LoRA adapters (AW))_ satisfying the rank constraints rank(AW,) s RA for all I [L] and bias vectors
b by E IRD such that for any input E X.
W (AEREZ (IREEE, ROARE
L
L
f(x) - f(x:) = RELU
II WT - (W,
II Wi)
x
26

---

Published as a conference paper at ICLR 2024
Therefore, when Σi=1 R4 2 Rg, the adapted model exactly approximates the target model, i.e., f()) f(x) for all X.
Furthermore, for random input x drawn from a distribution supported on X, and with E = Exx the expected squared error is bounded by:
f[]f(x) ((fxx)-F(xx)))) F(x))1 = | 1 ROJRE+1
(W1 II Wi).
[=1
Proof of Lemma 10. This proof closely adheres to the steps detailed in the proof of Lemma 9.
The primary change implemented here that, when we draw the analogy (14), we apply Lemma instead of Lemma 7. This results in
[ + AW) = III Wi (LL, ROAAR 1m1
W
Wi).
1=1
Utilizing the steps from the proof of Lemma and integrating the modification specified above, we can establish the desired result.
E.2 APPROXIMATING MULTI-LAYER RELU FNN VIA LORA WITH UNIFORM MODEL PARITION
In this part, we restate the results considering uniform model partition from Sec. 3.3, along with their corresponding proofs, presented in the same order.
Assumption 1 (Non-Singularity). For fixed LoRA-rank R E [D]. the weight matrices of the frozen model (Wi) and matrices (TIieP: Wi) + LR, - Ihep; Wi) are non-singular for all r S R(M 1) and i (D).
Lemma 3. Let (W (iife (Wi) DxD be matrices whose elements are drawn independently from arbitrary continuous distributions. Then, with probability 1, Assumption I holds VR (D).
Proof of Lemma 3. We first use Lemma 6 to establish that W I...., W T WI...., WL
singular with probability 1. The goal of the remaining proof is to demonstrate that (IhEry Wi) + (R, ; HI Wi) is full-rank with probability 1. this proof, use p. denote the proba- bility density function, where the subscript indicates the associated random variable.
Fix
arbitrary i
[L] and
R Then probability of the (Theryy wi) +
LR,
(:: - IliEP Wi)
being full-rank be computed as
P
det
II Wi 1er
LRR
W
W
#
IEP
f
P
det
II (EP:
Wi
LR,(E)
# 0
W
W: E
Pw. - W. (E)dE.
LEP:
If the conditional random matrix (IIEE w. (E) W. -1--lee Wi E has continuous
distribution with support of non-zero Lebesgue measure on R DxD then
IP det (II Wi
+ LR,(E)
* 0
W
II
W E =1
IEM:
LEPS
ensuring (Ihrr Wi) + LR,
(W: W.-Ilre -herr Wi) is full-rank with probability 1.
27

---

Published as a conference paper at ICLR 2024
Consequently, the remaining part of the proof aims show that the conditional random matrix (IIIEPy Wi) (E) W; - P Wi E follows arbitrary continuous distribution with support having non-zero Lebesgue measure on R DxD, Denote W = I[ W. Now, consider the conditional distribution of ph Wi W; I W = E, which can be written as
Pwiw:- - w w W) Pw; (E W).
Since Pw, is continuous with support of non-zero Lebesgue measure on IE DxD, the same holds for I; Wr W. I Wi E. Furthermore, adding a constant matrix (R,(E) this conditional distribution preserves the desired properties, thus completing the proof.
Theorem 3. Under Assumption I, there exists rank-R or lower matrices (AW with AW; RDDD and bias vectors (bi)f-1 with by E RDD when the rank of the low-rank adapter R 2 [ma rank( W; IIEEP; W the low-rank adapted model f can exactly approximate the target model J. ie., f(x:) ) = [(x)) for all input a E EX
Proof of Theorem 3. The key to this proof lies in simple idea: for each layer E [L] in the target model, we can update M layers (i.e., (i 1)M + 1-th layer iM-th layer) in the frozen model to approximate it as guaranteed by Lemma 9, Hence, all layers of the target model can be approximated by the adapted model.
Model Decomposition.
We partition the adapted model into L sub-models, each defined as fi(-) = F: (W)), (b))) (()))
E [L].
In similar manner, we break down f into L sub-models, each is one-layer FNN:
f.(-) FNNI.D(;; W b.), i e [Z].
We can then express fxx and f(xx as compositions of their respective sub-models.
f(.) = fr ................................ f1(,), f(-) J e .... .... F.())
To analyze the error E [x] f(x)]l E [[] [x)]x 2اا
consider the error caused by each submodel. Let R2 rank W; ITer Wi) denote the rank of the discrepancy between the target weight matrix and the frozen weight matrices, where i E [L]. By Lemma 9, we can select
AW 1...., 1...... AW A Di,...... by such that
II Wi) 2 2)
(IARREAR (. (W
[(2)) - J((z) = RRLU
II Wi) (W,
(15)
LEP,
LEP"
E ([f)(())
Ezz
|| 02 +LAR
(
II Wi).
(16)
1=1
Given these selected parameters, fs functionally equivalent to a one-layer FNN:
(IRR
f1(2) ReLU
RLRA
W
II
W
W
1E
IE!"
R. ]. it follows that fa 9, for all E [T], which implies f g. Clearly, when R 2 max,
Corollary 4. Assume that the elements of matrices (W (Wi)ff are independently drawn from arbitrary continuous distributions. When Z D/M, there exists rank-R R lower matrices
AW I,..., AW, E RDDD and bias vectors bi...., br. E RD such that low-rank adapted model can functionally cover the target model on X, iee. f(x) = F(x) for all input x E X, with probability 1.
28

---

Published as a conference paper at ICLR 2024
Proof of Corollary 4. To prove the statement, start by noting that combining Lemma 3 and The- orem 3 directly gives us f(x) = f(xz) on X' when R 2 [e [rank W I Wi)/M]. Therefore, the only thing left is to show that rank W; - I Wi) D for i E [L] with prob- ability 1.
In this proof, we p. denote the probability density function, where the subscript indicates the associated random variable.
To establish this, consider the following probability expression:
P
det
W.
II W
# 0
PT
P det (W: w) +
II KEP
Wi W
PPlicey w. (W)dW.
Since W is independent of ThEp
Wi, we have
P f det (W. - W) *
II SEP
W. = W
PP (del (W, - W) + #0} Lemma 6
Therefore, conclude that IP dct
W. -her Wi) + 0} 1, which completes the proof.
Theorem 5. Define the approximation error of i-th layer as Es ORM+ (W; He Wi). and the magnitude of the parameters and the input as 3 max (E( IT E [ V VIEIT
Under Assumption 1, there exists rank-R R or lower matrices (AW with AW, DxD and bias vectors (bi)tz with by E RDP such that for input E X with Exx = E,
E f(() F(x)]1 S 8
W Ex) Ex) E..
max kE(L.
Proof of Theorem 5. This proof is a continuation of the proof of Theorem 3. In this proof, we will consider a more general case, without enforeing any constraints on the rank of the adapters R. We
use W; to denote the corresponding weight matrix, i.e., W: = LR RLAR, (W1 - Iher Wi) + Hhe Wi.
Error Decomposition. For submodel = 2,.... ...,,, L, we calculate the expected error of the compo- sition of the first i sub-models,
2 2ill2 = [ (2+-1) - [((2-1))12
(17)
E 1 + (fi(z-1) 1()
(Rearranging terms)
(f(( - ||| -o.FFF.ee
E [[(=)))
F((2.-1)l
(Applying triangle inequality)
A
B,
Here A, represents the enror resulting from the discrepancy between the first submodels, while B, represents the error arising from the mismatch between the i-th submodel.
29

---

Published as a conference paper at ICLR 2024
Computing A, We start by computing the error introduced by the first i 1 submodels, denoted
by A,:
A (Z fi(2i-1 1l12 = IE ReLU( (W.(Z:1 21-1))
Wi,2 - -21-1)
(ReLU I-Lipschitz)
W.
E 12,-1 21-1/12
(18)
Here,
W
Wi + LR RMAR (W;
II Wi) LEPT
IEPT
W
II Wi W; + LR RMAR. (W;
II Wi)
(Rearranging terms)
(EP:
tEP
W l|e
II TEP:
Wi W, + +LR RMAR. (W,
W
TEP
(Applying triangle inequality)
D
= W l|
Σ
(
II W) LEP
(19)
j=RMAR,+1
(By the definition of W; and LR,
+i (-))
RMAR
< max kE(L]
W &
F.j) = a.
By combining (18) and (19), we get
A S max kE[L]
W : || + E
Zi-1 S aB 2 21-1l12-
(20)
Computing B,. We proceed compute the error associated with the i-th submodel, which denote as B; It can be evaluated as follows:
B, E (Z F.(2:-1)11
ReLU (IE
(15)
[RRRMAR W
II Wi)
(W,
II Wi)
2
LE
LE
2
<
LR LRRMAR
RMAR W
Wi)
(W. Wi)
2
(ReLU is I-Lipschitz)
JE
JE
LR LRRRMAR
W. II Wi
(W.
II W:)
E 1 1|121112
IEP:
IEP:
-6 =MMMRR W II
W
LEP
We can further simplify E -| as:
2 1 ll
= E ReLUU W.-, W.-IZ:22 + b 1) 1
E
Wi- Wi-12,22 b ||
(ReLU is 1-Lipschitz)
30

---

Published as a conference paper at ICLR 2024
W 2|,2222222 +
6
(Applying triangle inequality and (1))
(|) 122
122,-112
(| + ||6.-1112
(Following the same steps)
All R | + Σ
II
W & Ip b0112
(Repeating the same steps)
k=
2-1
Σ
II
W 1b112 s.
F
1=1 k=j+1
Therefore, obtain
B, S 30 RM +1 W. II WT). PEP
Error Composition. Having established upper bounds for A; and Bi, we next evaluate the ex- pected error for the composition of the first adapted submodels.
(17)
(20)
E E
2:12
A + Bi
I aE 1 2 + B; S 22,2-- + BB-1)) + B,
2 1,,2 8: 2 + aB B, S S - b1 21 21112 +
Σ i- B 2
(21)
To compute the overall approximation error of f. which is the composite of all submodels, we have
E f(x) f(x) || = E f[(x) F(xx) 112 = 2 2r11
(21)
I a TT- -11l12 + Σ
I
a
---- Bi
i=2
I
(16)
I a
I-
RMAAR, 1 W
II
Wi)
+ 8
RaSAR
W
Wi
LEP"
1=2
LEP
L
3
RM
Wi)
i=1
IEP
T
3
RRM+ (W; II Wi).
IEP
Substituting a with max ma W x Ex) concludes the proof.
E.3 APPROXIMATING MULTI-LAYER RELU FNN VIA LORA WITH GENERAL MODEL PARITION
Firstly, we provide the required non-singular assumption and the lemma demonstrating the mildness of this assumption for the general model partition cases after introducing necessary notations.
Assumption 2. For the given LoRA-rank sequence (Ri) and partition P, the weight matrices of the frozen model WI,..., Wr and (ILE,, Wi) + LR, II P. Wi) are non-singular mmx P:-1 R₁ and i e [Z].
P.-
for all < Eiapp
Note that max P; and min P; here represent the maximum and minimum elements in the set P.. respectively.
Lemma 11. Let (WDL., (Wi) DxD be matrices whose elements drawn independently from arbitrary continuous distributions. Then, with probability 1, Assumption holds for all R. e (D).
31

---

Published as a conference paper at ICLR 2024
Proof of Lemma 11. Following the same steps in the proof of Lemma 3 but replacing the uniform partition with the general partition completes the proof.
We now restate Theorem 6 and provide its proof.
Theorem 6. Consider partition P for the frozen model. Let Assumption 2 hold. If EiEP, R rank W; ;- -.ee. for all E [L], there exists LoRA adapters (AWi)) with rank( Rí and biases (bi)k= such that the adapted model can exactly approximate the target model. Moreover, define the approximation ervor of the i-th layer as E, Eier, R (W; IE Wi). and the magnitude of the parameters and the imput as B [[L) (VIE ( Ej- I [R (b,111) V VIEII
Then, there exists LoRA adapters (WWi) with rank () & R& and biases (bi)f such that for any imput x E X with Exx = E, the approximation error can be bounded as
max E f())(x) F(x)1l2 S
([[ Ex) L- E..
kE[l]
Proof of Theorem 6. This proof follows the same steps as the proofs of Theorem 3 and Theorem 5, substituting the uniform partition pu with the general partition and applying Lemma 10 in place of Lemma 2 to derive the desired outcome.
E.4 APPROXIMATING MULTI-LAYER RELU FNN VIA FINAL LAYERS TUNING
We now aim to examine another commonly used model adaptation method, the final layers tuning, within the same theoretical framework.
The main limitation of this method, as compared to LoRA, is that while LoRA can update all layers, the tuning of final layers keeps the initial layers frozen. Consequently, clear limitation arises when the initial layers of the frozen model are less discriminative than the target model f. That is, if there exist two input vectors 21,
IR DxD such that the output of the initial layers of the frozen model fo is the same, but the output of the target model is different, then no matter how the final layers are tuned, it is impossible for the adapted model f to exactly approximate the target model f.
To formalize this, observe that for the first layer of the frozen model, the outputs of the inputs in the non-ace antiviiivaiion region are always zero. In other words, when I1, 32 E {x: Wi + b1 S 0}, we have ReLU( W Wi0+++ +bi)
0. Therefore, no matter how the subsequent layers are tuned, we still have f(x) = f (w2)) When we fix the first / - layers, the non-activation region becomes (x W2 b1) b2 S 0}. Similarly, we define the non-active region of the first /
I[ W. + Σl= IT W,b, 0). Correspondingly,
layer in the frozen model as I
define 1; { x II: W. c0 Σ 11 W,b,50,
The following lemma is provided based on these definitions.
Lemma 12. Ifl [L - 1] such that I \ U. I, # 0 and the weight matrices of the target model (W are non-singular, then for any tuning of the last L - layers, f f.
Proof of Lemma 12. For the simplicity of the presentation, we let T - T, to denote the non-
activation region of the target model. Then, the condition T \ U.T. I + 0 can be written as 4 I 0. Clearly, both and I are closed convex sets.
Condition I, \ II # 0. The condition I \ I A 0 indicates that there exists region in I where the ReLUs are deactivated in the 1-th layer the frozen model, but activated the entire target model. Therefore, for any æ,, 22 \ T, we have f(x) f(x2)) regardless of how the final | + layers
32

---

Published as a conference paper at ICLR 2024
tumed. If these æ1; D2 E 4 \ I satisfies f(x1) # f(æ2), this proof is completed. The remaining proof is showing the existence of such I1, 22
Existence of 31, 22. Firstly, we show that there exists two 21, 22 E 4 \ / such that #1 + 22. Let 21 E J \ T. Since I is a closed set, there exists sequence (2:) where 2; E 1 and 2; + an satisfying lim 2i 21- Note that at least one element 2, must not belong I, otherwise æ1 would be in I due to the closed property of I, contradicting the selection of Φ1. Let 22 Therefore, we have two distinct & 22 4 with # + 222
Then, given 1 22 E Jt 7 such that æ1 * 22, both 2, 22 activate all the ReLUS in the target model. Since æ1. 22 & I and the weight matrices of the target model 12) all are non-singular, we have
f(a1) - f(x2) = W I W Wa( T2) + 0,
Meanwhile, since 11 02 E 4t the output of the initial layers of the frozen model are equal, thus we have f(x1) f(x2) matter how tune the last L layers. This completes the proof.
implying f(x11) * f(x22).
The following lemma reduces the assumptions to the assumption of randomly generated mod- els. This assumption aligns with that of Corollary 4, thereby facilitating a more effective comparison between the expressive power of LoRA and the adaptation of the final layers.
Wor + b,
Lemma 4. Let D 2 2 and f be a one-layer target FNN. Assume that the elements of weight matrices (Wi) are independently drawn from arbitrary continuous distributions. With probability 1, for any tuning of the last L layers. f F.
I
W,r b
Proof of Lemma 4. If we can show that 1 \ T1 * 0, by Lemma 12, we obtain the desired results. Therefore, the remaining proof aims to show that / \ * 0 with probability 1.
Figure 2: An example of and /, when =
Note that 7, \ 7, 0 holds only when W W, (not that this is necessary condition not sufficient condition). as demonstrated in Figure 2. However, since the elements of matrices W1 are indepen- dently drawn from arbitrary continuous distributions, we have P(W; * W₂) for all [L]
Therefore, I \ I = 0 holds with probability 1. By Lemma 12, we complete the proof.
F PROOFS FOR TFN APPROXIMATION
In this section, we not only provide the proof for the results outlined Sec. 4, but also introduce the problem setting for TENs with single-head attention layers and present the corresponding results.
F.1 APPROXIMATING TRANSFORMER NETWORK WITH SANGLE-HEAD ATTENTION LAYERS
In this part, outline the problem setting to investigate the expressive power of LoRA in TFNs that utilize single-head attention layers. The primary distinction between this setting and that of TFNs with multi-head attention layers lies in the weight matrices. Specifically, the W matrices for combining different attention heads are absent in this case. Despite this difference, the derived results are consistent, albeit under slightly modified assumptions regarding the weight matrices and a different LoRA adaptation strategy.
We start by introducing necessary notations. For an input matrix X RDxN where D is the dimension of the token embeddings and N is the number of tokens, the 1-th Transformer block using single-head self-attention can expressed as:
At ny (Z-11) = Zv softmax ((Wr) WQiZ(-1, (
Z Wz ReLU Wi. Attn: (Z-1)) + 1, byll
33

---

Published as a conference paper at ICLR 2024
where the weight matrices WK.. WQi. Wv,, Wu, W2 RDDD bias vectors b1i. D2ER Zi is the output of 1-th transformer block, with Zo = X. The output of the first L Transformer blocks are subsequently fed into the output layer. This produces the final output of the TFN, given by softmax W. Zr., where W. E DxD represents the weight matrix of the output layer.
For single-head self-attention layers, the target model f, frozen model f. and the adapted model f can be formally represented as:
g = TFNLD (5 ((W VL, W KI, W Qr. W 21, W WI)ED Wo). (bu. bas) Frozen TFN fo TF (: ((Wv:, WKI, Woi Wt.. Wi) W.). bx)==))
Target TFN
Adapted TFN f -TNNL : ((Wv
AW VI, WKI KT + AW Kb. WQi + AWWQ. Qi.
W2 AW 21, WT + AW WILL: W. + AW ,), (bu. ba)t
Here, W KI, WQU W. are the weight matrices for generating key, query, and values in the th transformer block of the target TEN; W W2 and bus by serve as the weight matrices and bias vectors, respectively, for the feedforward layer in the same block; W. is the weight ma- trix for the output layer. For the frozen TFN, the same roles are played by WKI, WQr, Wvi, WI,, W2.. and b bys for all E [L] and W. For the adapted model, low-rank adapters AW KI, AW Qt, AW vi, AW ii, AW 21; AW, with rank constraint R E [D] are added each weight matrix, and the bias vectors are updated to bu, by for all E [Z].
Given the problem setting outlined above, give the non-singularity assumption for TFNs with single-heat head attention layers.
Assumption 3 (Non- Non-Singularity). All the weight matrices of both the target model and the frozen model, as well as the following matrices for all E [D).
WK WoI + LR,
W Wai
- W Woi). where 1= = 1,
WkI + LR, 21-1 W 211-1 W K W W 2111 W21-1W W - WkiWoy) for E (M))
Wn LR, (W W VI Wwi forl=1
WiWWi+ WWWwWWW 21 W W 21-1 -WuWv)) for all l [4] (1),
W.W2L LR,(W, W W.W2L),
are non-singular.
Lemma 13. Let the elements of all weight matrices in target model F and the frozen model f be independently sampled from continuous distributions. Then, Assumption 3 holds with probability 1.
Proof of Lemma 13. The results can be obtained by replicating the same steps outlined in the proof of Lemma 3.
Theorem 8. Consider the rank of the adapter weight matrices R E (D.. Let Assumption 3 hold.
Define the rank-based functionality gap G₁ to i-th transformer block (i E [L]) or output layer L + 1) as
WAT W V max, (rank(W,, W Wh vi Wi.W -i=1 Ki
max
rank
Ki
Qi
G =
max
rank W
21-1
Wh Ki Q: W 2, W 2.1- W.T-IWH W W W2,-1)
Wh
V Vmax
rrank( W is W 22:-1- WT, W.:W W...Wi..
25isL,
rank W. W. 2L
W.W,)),
i+1+1.
If R Z max G there exists rank-R or lower weight matrices for low-rank adapters (AW KI, AW Qt, AW vI, AW WW 21,, AW, with other low-rank adapters set to O, and updated bias vectors: (bı baa)t such that for any X DxN the adapted model f exactly approximates J. i.e. f(X) f(X), with probability I.
34

---

Published as a conference paper at ICLR 2024
Proof of Theorem 8. Let H R and Zi R denote the intermediate and final outputs of the 1-th transformer block in the target model f. respectively. Specifically, Hi represents the output from the first feedforward layer in the I-th transformer block. They are defined as
H ReLU
W 11 W vi Z softmax ZZ_1 W KI
Wi W WiI 211) bull).
Z
W 21 H + bu
where e [L]. For the adapted model f. introduce Hi and Zi to denote the corresponding intermediate output of the first feedforward layer and the final output of the /-th transformer block for the adapted model, respectively:
H. = ReLU ( (Wir+ AW (W Wl)++An)((Wr)) vW Ž
softmax [ + AW (Wor + AW AW o1) bril))
2. (W21 + AW 21 Hi bb:1
where / E [4]. We note that Zo = Zo X.
In this proof, we AW 21 O for all E [L]. Our goal is show that adding low-rank adapters to self-attention layers and the first feedforward layers in all transformer blocks enables the adapted model to be functionally equivalent to the target model f of the same dimensions. We start by inductively constructing the adapter weight matrices (AW AW vI, AW KI, AW Ql. bu, ba) such that H, H. for all I [T.] We then select the low-rank adapters for W2. and the W. to approximate the output of the target model. For unmentioned low-rank adapters, we set them as O.
When / 1. To achieve H1 with Hi for all X, the following conditions must be satisfied:
Bias Vector: bu bis
Query and Key: (WKi + AW Ki) (Wor + AW Q:) W KI
Wa Q
Value and First Feedforward Layer: (Wn + AW (. AW = W W..
To achieve this, we set by by to achieve (24), and select rank-R or lower matrices AW KI, AW Qu. AW AW vi suggested by Lemma 7. This ensures Hi H, for | =.
When / > Now we focus on the cases where 2, ..., Assume the induction hypothesis holds for - 1, which is H Hi-1. This implies
H W 2, Z b2,1-11) W W2 b21-117)- H.-1.
Using this assumption, express 2 1 in terms of Zi-1:
2 W2,11 W 21-
(Z-11 2
b2, + b
Let 12 W2.11 W 2,1 b then we have
Ż W2,1 W 2 Zi-1.
(22)
To achieve H. Hi, we express both H, and H. in terms of Z,-1i
H = ReLU
W W. Z,-1 softmax T W W Qi Z + bbrb))
H. ReLU (Wnr + AW (W AW vi) 2
35

---

Published as a conference paper at ICLR 2024
softmax ( + AWk) AW qi) 2111) + b111,).
(22) ReIu (Wi++ +W (w))(Wrrs vi) W2:-1 21-1 21-1
Z W -IT 21-1 2 + AW Ki)
ssotmaa
(Wqr + AW
+b11l)
Therefore, we need to align the following three components:
Bias Vector: bu by
Query and Key: (WK) + AW KI) (Wa: + AW W W 2 W KI W W 2 2 W 2//-1'
Value and First Feedforward Layer: (Wn + AW w.)(W:: + AW v\) W W W 21 1,,11 2
By setting بy based on (26) and adjusting AW KI, AW QI AW 11, AW vi based on Lemma satisfy all three conditions above, thereby obtaining Hi = Hi for I E [L] \ (1}.
Output Layer Analysis. By the induction method, have established Hi H. for all [4]. We will complete the proof by showing that f(()) f(X) for all X E X.
The final output distribution of the target TFN f can be written
f(x) = softmax L)) = softmax (Wo (W21. H + b by)1
We can similarly formulate the final output distribution the adapted model f f(X) softmax (W. + ZZ)
softmax (Wo + (W.+AWA (W22 + AW AWa HL + d2
To align these two expressions, we select AW 22 and AWo based on Lemma 7, and let b2t = (Wo + AW.) - W .bLL, where W. + AW, is invertible as shown in the proof of Lemma 7. -
Thus, the proof is complete.
The following corollary identifies the specific LoRA-rank required to achieve exact representation for random model cases in the current setting.
Corollary 9. Assume that the elements of all the weight matrices of both the target TEN and the frozen TFN are independently drawn from arbitrary continuous distributions. If R 2 [ adding low-rank adapters of rank at most Rt to weight matrices in (AW AW Qt, AW vi, vW,,WW WW),,,,, 2L, AW, and tuning the bias vectors, enables the adapted model f to exactly approximate the target model f. i.e., = f(X) all X E RDN,
Proof of Corollary 9. By combining Lemma 13 and Theorem 8, and following the same steps in the proof of Corollary 4 which yields max, G; D, can obtain the desired outcome.
F.2 APPROXIMATING TRANSFORMER NETWORK WITH MULTI-HEAN ATTENTION LAYERS
In this section, we first provide the explicit formulation of TFN with multi-head attention layers. Consider input matrix X DxN where D is the dimension of the token embeddings and N is the number of tokens. The output of the I-th transformer block is denoted as Zi, which can be computed as follows:
Attn Attni(Zi-)))
Zi-1) = Σ wh why Z. softmax (W w
h=1
Z Wz ReLU Wi. Attn: + 1 byl
36

---

Published as a conference paper at ICLR 2024
where define Zo X. Here, H. is the number of attention heads. The weight matrices for each head h E [H] in the 1-th transformer block are Wo Wh1. W 1 QI E R RDD,, The softmax operator softmax(() is applied column-wise to the matrix. Further, W2., Wu E ERDxD are the weight matrices and bit, 62r RDD are the bias vectors in the feedforward layers.
A Transformer network, denoted T., is composition of L Transformer blocks, followed by an softmax output layer softmax W. -), where W. E Dx The final output of the TFN is given by softmax W. ).). To study the expressive power LoRA within TENs featuring multi-head attention layers, we next specify the parameters of the target model J. frozen model fo. and the adapted model f, each with L transformer blocks and a dimension D.
To study the expressive power of LoRA within TENs featuring multi-head attention lay- ers, we next specify the parameters of the target model J. frozen model fo. and the adapted model f. each with L transformer blocks and dimension D. For ease presentation, we drop the subscript in TFN,,D, referring to it simply as TEN. Given specified rank R E [D] for LoRA, these models are defined as follows:
Target TFN f TFN (:((W))) W VI W W
KI QUI-I, Wa, 21 W WItEE,W W.) (bL,, (bu,,bb) ba)tta).
Frozen TFN fo TFN (s((( W W KI W WT, WilNEE W.). (bii, bu)
Adapted TFN f TFN (((W)) + AWW W + AWW, VI: W Ki AW KI. W A AW QWQ
W2 + AWW WT + AW WED W. + AW .), (bn, bu)
where the weight matrices E IR DxD and the bias vectors E RDD. Moreover, the weight matrices of the low-rank adapters AW A AW VI: AW KL. AW Q AW AW i for all h E [H] and / E [4] of rank R or lower.
We next introduce non-singularity Assumption 4 for TEN with multi-head attention layers scenar- ios, which is then validated by Lemma 14. We then provide proof of our main results for TFNs
Theorem 7. Additionally, we introduce a supplementary theorem that amalgamates results for TFNs with both single-head and multi-head attention layers when the weight matrices are randomly initialized. This is articulated in Corollary 10.
Assumption (Non- Non--ingulaarty). For a fixed E [D]. all the weight matrices of both the target model and the frozen model and the following matrices for all
[R].
W W KI Q LR,
W
W
W Wh)) for all he [H] and I == 1,
KI
Q
WAT + LR, WT W
2,1-1
W
KI
W
Qr
W
2,-1 W. W W for all h E [H] and [L] (1),
w + LR, Wi7 W W
W
W wt.). for all h E [H] and 1,
W LR, (WT W W. Or W
21 WTl W& for E [H] and l e [M] (1),
W. + (R, W W.W21),
are nin-singular.
Lemma 14. Let the elements of all weight matrices the target model J. and frozen model fo be independently sampled from continuous distributions. Then, Assumption 4 holds with probability 1.
Proof of Lemma 14. The results can be obtained by replicating the same steps outlined the proof of Lemma 3.
For the reader's reference, we restate Theorem 7 here integrated with the explicit formulation of the rank-based functionality gap G,,
Theorem 7. Consider a given LoRA-rank R E [D]. Let Assumption hold. Define the rank-based functionality gap G; to i-th transformer block (i (T.] or output layer I + 1) as
37

---

Published as a conference paper at ICLR 2024
maxA
rank( W
Ki W
Wi w
max, (rank W W. W Wo:)),
G
maxi
rank(
W
2 WR Wi 22.-1)) 1) W
2
Mmxx
rank
W 2.-1
Wi, W..--i)))
2 2 L. i- L+1
rank W. War W2W)2..
(23)
If R 2 m 2
1. then there exists low-rank adapters with rank lower than R E
[D]
((AW)) KI. AW and updated bias vectors (b11, b2) such that for any DxN, the adapted model f exactly approximates target model f, i.e., f(X) = f(x).
Qu. AW VI. AW oi 11) AW 22, AW with other low-rank adapters set to O,
Proof of Theorem 7. The key idea of this proof is the same as the proof of Theorem 8: our first step to ensure that, for each transformer block, the output from the first feedforward layer in the target model matches that in the adapted model. Once this is established, we select an appropriate output layer weight matrix to complete the proof.
Similar to the proof of Theorem 8, we define H, E IR DxN and Z E IR DxN as the intermediate and final outputs of the I-th transformer block in the target model f, respectively. In particular, H; corresponds to the output of the first feedforward layer in the (-th transformer block. They are formulated
H = ReLU
W 11
Σ
W. vi Z softmax 7 WiiWii Kl Worz.1) +bull)
Z: = W 2: H by V-
For the adapted model f, we introduce Hi and 2 accordingly to denote the intermediate output of the first feedforward layer and the final output of the 1-th transformer block for the adapted model, respectively:
H (w + (WW 8
H = ReLU Wi
Σ h=1
softmma (W + T + AW + b1r1))
2, W2 21 H + b 1
Note that Zo 2g X.
We aim to demonstrate that adding low-rank adapters to the weight matrices allows the adapted TFN
to be functionally equivalent to the target TFN of identical dimen- sions. We will initiate our proof by inductively constructing the adapter weight matrices ((AW), oz: AWh vı: AW kI: A 11) AW by. b2)(_11 such that Hi Hi for all e [L], and then select the AW 2L and the low-rank adapter for the output layer AW, o to approximate the output of the target model. For unmentioned low-rank adapters, we set them as O.
When 1 1. To achieve H, with H, for all X, we must satisfy the following conditions:
Bias Vector: by: =bu-
(24)
Query and Key: (WAr + AWA ka) T (W Aw Q1) w W Q
Value and Output Projection: (Wh, + AWA A W VI AW = W W. W W
To achieve this, we set 6y by to achieve (24), and select rank-R or lower matrices A h KIs AWA Qi AWh. b WWA, for all h e [H] as suggested by Lemma This ensures H, = H, for 1.
38

---

Published as a conference paper at ICLR 2024
When / >> 1. Now we focus the cases where 1 = ., L. Assume the induction hypothesis holds for which is Hi-1 - Following the same steps in the proof of Theorem let 12 W2,- W 2, b2.-1. thereby obtaining,
2 = 22, W 21- Zi-1-
(25)
To achieve H Hi we express both H, and H, in terms of Z
H
H = ReLU WH
11
oi W
Z1-1 softmax Z W
T W
Kl Qi (11)) + +b111()
h=1
H = ReLU
Wil
(Wo) + AW o.)
( AW/) 2
4=1
softmax
7 ( + +AW (W + AW 22-11) (
+ )111)))
(25)
o.) AW)) W2,11 W -1 2/ Z1-1
ReLU
W1
softmax
Z
W IT
2111 2,1 - ( AW
(W Aw Qt W. + +bul%)
Therefore, need to align the following three components:
Bias Vector: bi bu,
(26)
Query and Key: (W + AWk)
ki) (a)T)(WW) (Wa:: + AW W W W w W 211 21 W2
Value and Output Projection:
(W AW AW Wi
W 2 W 2/-1'
By setting du based on (26) and adjusting AW on Lemma 7, we satisfy all three conditions above, thereby obtaining Hi Hi for I [4] {1).
K7: AW AW
Q on AW Vi for all h [H] based
Output Layer Analysis. By applying the induction method, we have established H. H, for all I E [L]. Lastly, we choose the AW.. AW 2L and the bias vector Pyg using the same approach as in the proof of Theorem 8. This concludes the proof.
The following corollary identifies the specific LoRA-rank required to achieve exact representation for random model cases in the current setting.
Corollary 10. Assume that the elements of all the weight matrices of both the tar- ger TFN and the frozen TFN are independently drawn from arbitrary continuous distribu- tions. If R
2 [2], adding low-rank adapters of rank most R to weight matrices in Vi: AWh if 21, AW, and tuning the bias vectors, enables the adapted model f exactly approximate the target model J. ie, S(X) =(X) for all X DDNN
((AW),
Ki: AW Qu: AW
Proof of Corollary 10. By combining Lemma 14 and Theorem and following the same steps in the proof of Corollary which yields max, G; = D, we can obtain the desired outcome.
G EXPERIMENTS
In this section, we perform experiments on both synthetic and real datasets to corroborate our the- oretical results. Firstly, focus validating the construction of the LoRA adapter in proof.
39

---

Published as a conference paper at ICLR 2024
Subsequently, extend our experimental validation to encompass the effects of tuning final lay- ers and the significance of updatable bias. Additionally, we offer visual representations of training curves, assess the generalization performance of LoRA, and evaluate its efficacy classification tasks. We also conduct experiments on real datasets to further support our theoretical insights in real-world scenarios.
G.1 ADDITIONAL. DETAILS OF EXPERIMENT SETUP
We implement LoRA adapter AW by reparamcterizing it as AW AB" where A, B E R RDx, and we use the same initialization scheme proposed by Hu et al. (2022a). For experiments pre- sented in Sec. 5, G.3.1, G.3.2, G.4, and G.5, we consider two variants of frozen models:
(Random) The first method involves randomly generating all the weight matrices using the Xavier uniform distribution, which is the default weight initialization method used in PyTorc..
(Pretrained) The second method aims to simulate scenarios where the pretrained model is rel- atively closer to the target model. We achieve this by initially creating the target model and the frozen model in the same way as the first method and then performing full-rank updates on the frozen model via gradient descent approximate the target model until the approximation error is reduced by 1/3.
For other experiments on synthetic datasets, we default to the randomly parameterized frozen model unless specified otherwise.
G.2 ADDITIONAL DETAILS ON GRADIENT UPDATE METHOD
In our experiments, we utilize the Adam optimizer. We tune the learning rate E {10-2, 3,
and the weight decay E {0, 10 10 10-4). The optimal configuration is determined based on the validation loss set of 256 samples independently drawn from standard normal distribution.
We run 5,000 iterations for each hyperparameter setting, where at each step 256 fresh standard Gaussian samples are generated for loss and gradient computation.
G.3 VALIDATION OF OUR LORA ADAPTER CONSTRUCTION
Recall that all our theoretical statements are based on our construction of the LoRA adapters pre- sented in their corresponding proofs. To validate these results, here we empirically examine the relationship between approximation error and rank by integrating the LoRA adapters, which are constructed with the uniform partition in our proof, into the frozen model. Furthermore, we evaluate the effectiveness of our constructed LoRA adapters by comparing their performance against adapters updated through gradient descent and optimized by Adam. All simulations are conducted five times using different seeds, and the reported values represent the median computed across different runs.
G.3.1
FNN APPROXIMATION
=111
=1=1
=2 T.
0.10
Grodient Update
Gradimtt Updao Our Construction
Our Crestruction
0.02
MSE
0.05
MSE
0.01
0.00
0.00
16
8
16
Rank
Rank
(a) Frozen model is randomly generated.
(b) Frozen model is pretrained.
Figure 3: Approximation error (measured by MSE) versus LoRA-rank on FNNs.
In this experiment, we assess the effectiveness of our low-rank adapter construction for FNN ap- proximation, which detailed the proof of Theorem 5.
40

---

Published as a conference paper at ICLR 2024
1=1.22
Setup. We consider two scenarios: one with L and 2 and the other one with L = and should be noted that for both these cases, have M [T/L.] = here. We employ the gradient update method and the construction outlined in the proof of Theorem 5 to update the LoRA adapters.
It
log(MSE)
(0-l
Godaas: Uptiat
Our Conimatse
12
16
Rank
Figure 4: Log-scale MSE versus LoRA- rank randomly initialized FNNs.
Results. Fig. 3 presents the results for FNN approxima- tion. Consistent with the implications drawn in Sec. 5, the limit changes from Fig. 3a to Fig. 3b suggest that the pretrained frozen model results in less ap- proximation error. Additionally, we observe that our construction's performance aligns closely with the gradient update method when the target model depth L = 1. However, this alignment is not observed when = on low-rank region (i.e., S 4), This further underscores the limitation of our LoRA adapter construction, which inherently assumes that the intermediate outputs of the frozen model and the target model need to align.
To facilitate more effective comparison between our construction and the gradient update method the higher-rank region (i.e., 2 6), we present the curves on a logarithmic scale, as depicted in Fig. 4. While the gradient update appears reach the optimal performance achieved by LoRA construction in FNNs, a gap is still discernible when viewed on a logarithmic scale. The MSE the gradient update method is approximately 10 while for LoRA construction, it's around 10 for sufficiently large rank.
G.3.2 TFN APPROXIMATION
We assess the effectiveness of our LoRA adapter construction in approximating TFN, as detailed in the proof of Theorem 7.
Setup. We examine target model F and frozen model f. both featuring the same architecture with transformer blocks, single output layer, two attention heads, and embedding size D 16. We focus on two scenarios: L = and L = 2. The weight matrices for the attention layers follow standard Gaussian distribution, while those for the linear layers initialized using the Xavier uniform distribution, which is PyTorch's 's default scheme for linear layer initialization.
L
10
log(MSE)
log(ME))
10
10-1
Gradbar Updize
Gradient Update
Consrrutio
16
12
Rank
Rank
(a) Frozen model is randomly generated.
(b) Frozen model is pretrained.
Figure 5: Approximation error (measured by MSE) versus LoRA-rank on TFNs.
Results. The observations here align with those from the experiments FNN approximation. We note that the gradient update method outperforms our approach when the rank is relatively small but lags behind as the rank increases. This advantage the gradient update method minimal ranks arises from the inherent complexity of TFNs, which allows for more flexible low-rank adapter con- struction. Meanwhile, the gradient update method's performance does not significantly improve as the rank increases. This arises from the inherent complexity involved in optimizing TFNs. Nonethe- less, our results corroborate the claims made Theorem 7, as the approximation error must be eradicated when the rank reaches [21 =
41

---

Published as a conference paper at ICLR 2024
Random
Pretzained
Random
Pretrsined
LoRA
0.10
Fioed Binees
0.10
Final Layer
Updistaiio Risas
MSE
0.05
MSE
0.05
0.00
0.00
2000
4000
4000
10
# Tunable Parameters
# Tunable Parameters
(a) Comparison between LoRA and tuning final layers.
(b) Comparison between LoRA with fixed biases and LoRA with updatable biases.
Figure 6: Approximation error (measured by MSE) versus the number of tunable parameters when various methods are employed. The analyses are conducted FNN models.
G.4 COMPARISON TO TUNING FINAL LAYERS
Tuning adding the final layers only is also common adaptation method used in various domains, including computer vision (Chatfield et al., 2014; Donahue et al., 2014; Sharif Razavian et al., 2014), and natural language processing (Devlin al., 2019; Gira al., 2022). Recall that Corollary 4 and Lemma 12 demonstrate that tuning final layers does not perform as well as LoRA for randomly generated models, provided the LoRA-ram satisfies the rank constraints shown Corollary 4. In this experiment, we aim to validate this assertion and compare the performance of tuning final layers and LoRA in more general scenarios, such as when the frozen model has been pretrained, and when the LoRA-rank is smaller than required.
Setup. We consider FNN models with D 16, =, I, In this experiment, we employ two baselines: LoRA and tuning final layers. The LoRA adapters and the final layers updated using the gradient update method.
Results. Figure 6a compares the MSE of LoRA and final layer tuning when the same number of tunable parameters are used. In the case of randomly generated models, we observe that final layer tuning yields significantly higher MSE when using the same number of tunable parameters, corroborating our results in Lemma 12. However, when the frozen model has been pretrained, the performance of final layer tuning improves considerably, though it still falls short of LoRA. This aligns with conclusions drawn from previous theoretical studies such as Tripuraneni et al. (2020), which asserts that the performance of final layer tuning heavily depends on the quality of the shared representations.
G.5 BENEFITS OF TUNING BIASES
In our proof, as detailed in Sec. 3.2 and E. the updatable biases the FNN play a crucial role in eliminating the nonlinearity of ReLUs. In this experiment, we investigate the importance of updatable biases in ensuring the success of LoRA in FNN cases.
Setup. We consider FNN models with parameters D 16, 1, 2, and examine the performance of LoRA both with and without biases tuning for adapting to match the target FNN. The LoRA adapters and biases updated using the gradient update method.
Results. The performance of LoRA with and without updatable biases is presented in Figure 6b. We observe that in both random and pretrained model cases, LoRA with updatable biases outper- forms LoRA with fixed biases when the number of tunable parameters is relatively small. However, the performance gap not significant and diminishes as the number of tunable parameters increases. This suggests that while tuning biases in conjunction with the low-rank adapters does enhance per- formance, the gain is not substantial. In other words, even without bias tuning, LoRA's performance remains competitive.
G.6 TRAINING CURVES
42

---

Published as a conference paper at ICLR 2024
6-1,622
Although our theoretical study does not incorporate any training process, we present the training curves of the LoRA gradient update method to illuminate the optimiza- tion aspects of LoRA.
1123
10-3
log(Taain (oaaii Losd
2000
4000
Setup We depict the training curves of LoRA fine- tuning on randomly generated FNNs for R 1,4, 8, 13, 16. Unless stated otherwise, all settings strictly adhere to the FNN experiments described in Sec. 5.
T 2,
111"2
10-5
Results The training curves visualized in Fig. reveal that models with smaller ranks (e.g., R=1,4) converge swiftly due to their limited search space, but they settle at a relatively high training loss. Medium rank models (e.g.. R==) converge more slowly. Highly overparameterized models (g. R=13,18) appear to converge faster, aligning with recent advancements in optimization theory, which suggest that overparameterized models are easier to optimize (Liu al., 2022a).
2000
0000
Epoch
Figure 7: Training curves of LoRA with varying LoRA-ranks when D
G.7 GENERALIZATION PERFORMANCES
While our theoretical study only establishes the upper bound of LoRA's performance with infinite data samples, it does not consider LoRA's generalization performance in practice. Although this is beyond the current scope of our paper, we empirically investigate LoRA's generalization perfor- mance in this experiment.
Setup. We include a training set of 400 samples for the cases where L = L, 2, and 800 training samples for the cases where L L 4. We evaluate how well LoRA's training performance transfers to the test set.
Results. Fig. presents the training and test MSE sus LoRA-ranks. However, no clear pattern is observed in the variation of the gap between the training and test MSE with respect to the LoRA-ranks. This could be due Adam not precisely finding the minimum (see Fig. 4), potentially avoiding overfitting.
I I, L
T 2.
Toi
10-2
MSE
16
12
To assess LoRA's generalization performance, we fine- tuned the frozen model on the training set and reported the training and test MSE. We notice an increasing gen- eralization gap (test MSE train MSE) the LoRA rank increases- - this is very evident with L=2, and less so with L=4. This is intuitive as larger LoRA ranks imply larger hypothesis class (e.g., g.g., the Rademacher complexity), so it is expected. We defer a detailed analysis of LoRA's generalization performance to future work but believe our simulation results provide valuable starting point for further discussion and investigation.
Rank
Figure 8: Assessment of LoRA's A's gener- alization performance on FNNs.
G.8 EVALUATION ON CLASSIFICATION TASKS
Our theory and previous experiments all focus on regression cases. In this experiment, we consider binary and multi-class classification tasks to optimize the LoRA adapter vias cross-entropy and report the performance of LoRA using accuracy.
Multi-class Classification. As shown in Fig. 9a, consistent with theoretical results, struction achieves 100% accuracy when R > 8. The performance gradient update also similar our observation when MSE is employed as the metric, particularly when MSE is plotted log- arithmic scale (Fig. 4). This observation echoes the findings of Hui & Belkin (2021), which indicate that optimizing MSE is fundamentally equivalent to optimizing cross-entropy.
Binary Classification. We have conducted binary classification tasks. We use the same setup as before but add one more output layer E R22DD which is block diagonal matrix, with the first
43

---

Published as a conference paper at ICLR 2024
I
12
I 2, A=
L 1.
I
1.0
1.0
Accuracy
Accurwcy
0.8
0.5
Geadiet Updatee
0.6
- Godlint Updatt
4
16
12
Rank
Rank
(a) Multi-class classification tasks with 16 classes.
(b) Binary classification task.
Figure 9: Accuracy versus the rank on classification tasks. The analyses are conducted on FNN models.
elements in the first rows and the last elements in the second row are 1 and all remaining elements are We fix this output layer, optimize the cross entropy on the LoRA adapters, and report the test accuracy.
As shown in Fig. 9b, we observe that this binary classification scenario, even with a very low LoRA-rank R = 1, the accuracy has been significantly improved, comparable to the results achieved by higher ranks. the region of higher ranks, our construction significantly outperforms the gradi- ent update method. The suboptimal performance of the gradient update method in this simulation suggests that, despite LoRA's current impressive performance practical applications, there is po- tential for further refinement.
G.9 EVALUATION ON REAL DATASETS
In our theoretical analysis, we demonstrate how the sizes of frozen models and the distance between the frozen and target models influence the necessary LoRA-ranks to achieve the desired performance (see Lemma 2, and Theorem 5, 6, 7). Specifically, our results suggest that larger models require fewer LoRA-ranks to reach the desired performance. Similarly, when the frozen model is closer to the target model, lower LoRA-rank is sufficient to achieve the same performance. We validate these theoretical insights through experiments on the GLUE benchmark (Wang et al., 2018).
Setup Our experiments are conducted using Tesla V100-PCIE-1G6 80GB, NVIDIA A A100-SXM4-40GB, and NVIDIA L40 GPUs. For each run, a single GPU is uti- lized. Unless otherwise specified, all our settings align with those established by Hu al. (2022a).
NVIDIA A A100-SXM4-
Impact of Model Size on LoRA Rank practice, most existing studies on LoRA use the same LoRA-rank for models of varying sizes, For instance, in the original LoRA paper (Hu et al., 2022a), Tables and 10 demonstrate the use of the same LoRA-rank for RoBERTa-base (Liu et al., 2019), RoBERTa-large (Liu et al., 2019), and DeBERTa-XXX XXL (He et al., 2021). Similarly, in the QLoRA paper (Dettmers et al., 2023), a LoRA Arank of 64 set for different models ranging from 13B to 65B parameters (see their Appendix B.2). To validate our theoretical findings, we evaluated the per- formance of LoRA on models of differrnnt sizes, specifically RoBERTa- with 110M parameters and RoBERTa-laut with 340M parameters. The results presented in Table 2.
Initially, we observe that, in the absence of fine-tuning (LoRA-rank = 0), there is no consistent trend RoBERTa-base performs better 3 datasets, while RoBERTa-large performs better on datasets. However, after LoRA fine-tuning, we observe that RoBERTa-large outperforms in most cases. In fact, even when the base model trained with LoRA-rank three times larger, RoBERTa- large still performs better on 6 out datasets. Given that the pretrained RoBERTa-large model was performing differently from the base model, this observation supports our theoretical findings that deeper models are more expressive with LoRA training.
Impact of Model Proximity on LoRA Rank While our theoretical results (Lemma 1, 2, and Theorem 5, 6, 7) imply that the frozen model that is closer to the target model achieves better results for a fixed LoRA-rank. To validate this, we compare the performance pretrained RoBERTa base with the randomly initialized RoBERTa-base fine-tuned using the same LoR A-RA-ranks.
44

---

Published as a conference paper at ICLR 2024
Model
MNLI
SST-2
MRPC
CoLA
QNLI
QQP
RTE
STS-B
RoBERTa
0
.330
.491
.316
.495
.682
.527
.024
RoBERTagage
.318
.505
.684
.505
.369
.473
.032
RoBERTapase
2
.861
.950
.892
.632
.928
.891
.780
.907
RoBERTabase
6
.870
.948
.892
.629
.31
.900
.773
.909
RoBERTagare
2
.904
.956
.917
.631
.466
.887
.884
.966
Table 2: Comparison the fine-tuned performance RoBERTa-base and RoBERTa-large using LoRA with different LoRA-ranks on the GLUE benchmark. Following Hu et al. (2022a), we report the overall (matched and mismatched) accuracy for MNLI, Matthew's correlation for CoLA, Pearson correlation for STS-B, and accuracy for other tasks. Higher is better for all metrics. Despite the absence of a clear pattern indicating which pretrained model is generally superior, after fine-tuning using LoRA, observe that RoBERTa-large (340M) fine-tuned with LoRA-rank R outperforms BaBERTa-base (110M) with LoRA-rank = 6 in 7 out of tasks. This observation aligns with our theoretical conclusion that larger models require lower LoRA-ranks achieve the desired performance.
Model
R
MNLI
SST-2
MRPC
CoLA
QNLI
QQP
RTE
STS-B
Random
.523
.775
.691
.154
.627
.761
.542
.213
Pretrained
.861
.950
.892
.632
.988
.891
.780
.907
Random
.535
.788
.696
.145
.625
.768
.542
.224
Pretrained
.868
.950
.890
.634
.929
.898
.805
.910
Random
.544
.799
.696
.154
.632
.768
.542
.210
Pretrained .868
.948
.892
.629
.931
.900
.773
.909
Table 3: Comparison the fine-tuned performance of randomly initialized and pretrained RoBERTa-base. Following Hu et al. (2022a), we report the overall (matched and mismatched) accuracy for MNLI, Matthew's correlation for CoLAA, Pearson correlation for STS-B, and accuracy for other tasks. Higher is better for all metrics. We observe that the performance of the pretrained RoBERTa- base significantly surpasses that the randomly initialized RoBERTa-base given the same LoRA-rank. This observation is consistent with theoretical findings, which suggest that frozen model closer to the target model yields better performance given the same LoRA-rank.
The results in Table 3 demonstrate that the pretrained RoBERTa-baad significantly surpasses the randomly initialized RoBERTa-base This observation is consistent with our theoretical findings, suggesting that the pretrained model requires lower LoRA-ranks achieve the desired performance.
H EXTENSION TO CASES WITH DIFFERENT MODEL DIMENSIONS
This discussion only applies to linear model approximation and FNN approximation. As highlighted in Sec. 2, our results can be easily extended to scenarios where the target model, J. and the frozen model, f. have different model dimensions. Specifically, for linear model or FNN approximation, D to represent the number of hidden neurons per layer in the target model and D for the frozen model. We particularly consider the cases where the frozen model is wider than the target model, i.e., D D. This is because the frozen model is typically overparameterized in practical applications.
The key idea for extending analysis to scenarios with different model dimensions is expanding the dimension of the target model. For the sake of simplicity, we focus on the simplest case, the linear model approximation, example. In this setting, the difference between the output of the
45

---

Published as a conference paper at ICLR 2024
adapted model and the target model can be measured by
22 0
F(x)
II (Wi AWW)
W 0
(27)
where E RDD Consequently, the last (T (1- D) columns and rows of II (W AW) does not affect the results at all. Denote the submatrix consisting of the first d rows and columns of a matrix W by [W],- Then, approximate the target model, we aim solve the following constrained optimization problem for a given LoRA-rank R E [D]:
min rank(AW,))) iS
I1 (wi AW))
W
F
To solve this problem, we first define an expanded target matrix, denoted by W RDDD The expanded target matrix W is constructed such that W W. while the remaining entries matches the corresponding entries in II w. Then, the error matrix E = w W -I W consists entirely of zeros except for the first D rows and D columns. Therefore, we obtain Rg rank( (E) S D.
Given the expanded target matrix, we consider the updated constrained optimization problem as follows:
min
(w: + AW, W
(28)
rank rank(A AIRR
By Lemma 1. we obtain that when the LoRA-rank
P.. the optimal solution to (28) satisfies
IL (Wi + AW1) = given that D 2 Rg. This result implics that II (Wi + AW:), W and therefore the approximation error defined in (27) is 0 for all input æ.
=
similar analysis can be conducted for FNN approximation.
EXTENDED FUTURE WORKS
To the best of our knowledge, this paper is the first offer a theoretical understanding of LoRA fine-tuning on both FNN and TFN. Our work delivers insightful results, elucidating the impact of rank, depth of the pre-trained model, and the distance between the pre-trained model and the target model on the expressive power of LoRA. Those theoretical results further corroborated via experiments. Despite these advancements, several intriguing questions still remain open. First, as observed in the numerical experiments, not be always optimal. Given that more complex models offer increased flexibility, an open ques- tion is whether we can devise more parameter-efficient scheme to construct the LoRA adapters, thereby deriving a tighter bound on approximation error. Second, for TFN, we have only identi- fied the conditions under which the LoRA-adapted model exactly matches the target model, due to the analytical complexity of TFN. It would be interesting to quantify the approximation error when the rank lower than required. Furthermore, for TFN, we constrain the target model and the frozen model to have identical embedding size and depth, and we omit the skip connections and layer norms for simplicity. Another intriguing direction would be to study the expressive power of LoRA under TFN cases with more general settings on TFN architectures. While our analysis does not involve any training process, an interesting direction for future research would be to consider gradient-based optimization algorithms and examine how efficiently LoRA can be optimized. Finally, theoretical questions about LoRA's generalization to unseen data also remain unresolved.
construction of LoRA adapters for FNN and TFN may
46


Reviews:
[{"review_id": "xVnxK4MQJK", "reviewer": "Reviewer_YxPR", "summary": "While conventional fine-tuning updates all model parameters for specialized tasks, full weight updating would be prohibitive for large language models (LLMs). Many methods were proposed to selectively update smaller parameter subsets or introduce lightweight adapters, significantly reducing computational and storage costs. The dominant method in this context is Low-Rank Adaptation (LoRA), which employs low-rank adapters to pre-trained weight matrices. Empirical evidence shows that LoRA can match or surpass the performance of full fine-tuning. However, there is a lack of theoretical understanding regarding how LoRA works, including questions about the minimum rank of adapters required for effective adaptation and how model architecture influences this threshold. Addressing these theoretical questions will provide valuable insights into the effectiveness and principles behind LoRA's adaptation of LLMs.", "questions": "Please see the above weaknesses.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper claims that they are the first to study the expressive power of Low-Rank Adaptation (LoRA) for different model architectures. So, if this is true (I do not have sufficient knowledge to check), the novel of this paper is significant. \n\n2.  Their theoretical results align well with the recent advances of LoRA on LLMs. \n\n3.  Not only FNN but TFN is explored with the both theoretical and emperical study.", "weaknesses": "(1) From Figure 1, I can see that LoRA of FNN performs on par with gradient update, whereas LoRA of TFNs significantly outperform gradient updates. Could the author explain this performance difference?\n\n(2) It is impressive that LoRA with rank=1 can match the performance of gradient update in Figure 3. Does this mean the gradient update does not actually learn well?", "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": "haxSKhZ6Ru", "reviewer": "Reviewer_F9Xm", "summary": "This paper presents a theoretical analysis of Low-Rank Adaptation (LoRA), a technique for efficiently fine-tuning pre-trained models, including large language and diffusion models. It establishes that LoRA can effectively adapt a fully connected neural network to represent a smaller target model if the LoRA-rank is sufficiently high. Specifically, the required rank is at least the product of the model's width and depth. For Transformer networks, the study demonstrates that a model can be fine-tuned to match a target of the same size using LoRA adapters of a particular rank. These theoretical assertions are underpinned by practical numerical experiments.\n\nThe paper concludes by highlighting the importance of LoRA's rank and the pre-trained model's depth in achieving close approximation to the target model. Despite these advances, it points out that the construction method for LoRA adapters might not be fully optimized and that better parameter efficiency could be achieved with more refined techniques. The paper also calls for additional research to measure approximation errors when LoRA-rank is not ideal, especially in the context of Transformer networks, and to further explore the application of LoRA in more complex network architectures.", "questions": "Please refer to Weakness comments", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- The study conducts a thorough analysis of the expressive capabilities of LoRA, underpinned by a set of well-founded assumptions.\n\n- The findings from this research offer a theoretical foundation for applying LoRA to a diverse range of models, including Transformers and Diffusion models, and furnish insights on how to select hyper-parameters for designing LoRA effectively.\n\n- The insights provided by this work can streamline the design process for LoRA, especially when the depth and width of the model in question are specified.", "weaknesses": "The experimental approach raises significant concerns. Given the widespread application of LoRA to various large language models (LLMs), such as LLaMA, there's an opportunity for the authors to substantiate their findings using models tasked with different challenges. Considering the availability of various model sizes in LLaMA and the comprehensive range of results provided by the original LoRA study, a comparison between the proposed theoretical analysis and empirical observations of LoRA would be insightful.\n\nThe use of Mean Squared Error (MSE) as a metric in the authors' presentation is questionable. Performance scores for LLMs typically exhibit a weak correlation with perplexity (PPL) or loss values. Therefore, relying solely on MSE for validation, particularly in the context of generative AI, may not adequately address the nuances of expressive capability. A multifaceted evaluation, including different performance metrics, would offer a more robust validation of the claims made in this work.\n\nAdditionally, it is acknowledged within the community that even very low ranks (such as 4, 2, or even 1) can yield satisfactory fine-tuning results. Readers would benefit from an exploration into how low-rank adjustments are able to achieve effective fine-tuning. The experimental outcomes presented in the paper currently do not offer practical insights for practitioners working with LoRA-based tuning, who would be looking for such guidance.\n\nThe authors are urged to establish a clearer connection between their theoretical discoveries and the empirical results previously reported for LoRA. Doing so could significantly streamline the hyper-parameter selection process for LoRA, reducing the effort required to fine-tune models effectively.", "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": "BL4DrjFLmn", "reviewer": "Reviewer_U2Yh", "summary": "The paper provides an initial theoretical exploration of the popular parameter-efficient finetuning method LoRA. It proves for fully connected models, LoRA should be sufficient to finetune any base model for a smaller target model with a certain LoRA rank (threshold). They further provide approximation errors for the case when the rank is smaller than the threshold.", "questions": "See above.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "This is a theoretically strong paper, studying a very timely topic. While empirically, LoRA has been shown to do surprisingly well, a theoretical explanation for why has been missing. This paper is a good starting point in understanding how/why/when LoRA works.", "weaknesses": "While it is okay to not have them in this paper, I think it would be interesting to study other effects of LoRA theoretically. For example, how does LoRA affect generalization? What can we say about how fast LoRA can converge even if the target model can eventually be found by LoRA exactly.", "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": "UgAr4SkjsO", "reviewer": "Reviewer_SRgL", "summary": "The authors conduct theoretical analysis for LoRA, a popular PEFT method for LLMs. For linear models with LoRA,  the “effective rank” is the sum of these low ranks. For multi-layer ReLU FNN, the effective expressive power of LoRA is nearly optimal up to a constant factor of 2. For transformer networks, adding LoRA adapters primarily to the self-attention layers enables the adapted model to exactly represent the target model.", "questions": "In section 2, why a L-layer (instead of one-layer) linear model is considered, which is still a linear model?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "+ The first theoretical analysis to understand the expressive power of LoRA. The first known results on the expressive power of LoRA\n+ Linear models, FFNs, and transforms with LoRA are analyzed, providing comprehensive theoretical results.\n+ Empirical results matches the rank requirements in theoretical analysis.", "weaknesses": "+ A notation table would help understand all the notations, since the paper is mostly about theoretical proof.", "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)