Structured Unrestricted-Rank Matrices for Parameter Efficient Finetuning
Authors: Arijit Sehanobish
Kumar Avinava Dubey
Krzysztof Marcin Choromanski
Somnath Basu Roy Chowdhury
Deepali Jain
Vikas Sindhwani
Snigdha Chaturvedi
Venue: NeurIPS 2024 poster (2024)
Keywords: Low Displacement Rank
Structured Matrices
Transformers
Vision Transformers
Fine-tuning
Primary area: deep_learning_architectures
TL;DR: We propose a new class of structured unrestricted-rank matrices, including low displacement rank matrices, for the parameter efficient fine-tuning of Transformers.

Abstract: Recent efforts to scale Transformer models have demonstrated rapid progress across a wide range of tasks (Wei at. al 2022). However, fine-tuning these models for downstream tasks is quite expensive due to their large parameter counts. Parameter-efficient fine-tuning (PEFT) approaches have emerged as a viable alternative, allowing us to fine-tune models by updating only a small number of parameters.
 In this work, we propose a general framework for parameter efficient fine-tuning (PEFT), based on *structured unrestricted-rank matrices* (SURM)  which can serve as a drop-in replacement for popular approaches such as Adapters and LoRA. Unlike other methods like LoRA, SURMs give us more flexibility in finding the right balance between compactness and expressiveness. This is achieved by using *low displacement rank matrices* (LDRMs), which hasn't been used in this context before. SURMs remain competitive with baselines, often providing significant quality improvements while using a smaller parameter budget. SURMs achieve: **5**-**7**% accuracy gains on various image classification tasks while replacing low-rank matrices in LoRA and: up to **12x** reduction of the number of parameters in adapters (with virtually no loss in quality) on the GLUE benchmark.

Structured Unrestricted-Rank Matrices for Parameter Efficient Fine-tuning
Arijit Sehanobish" !+ Somnath Basu Roy Chowdhury
Avinava Dubey?
Krzysztof Choromanski
Deepali Jain
Vikas Sindhwani
Snigdha Chaturvedi
IIdeependent
Google Research
GGoogle DeepMind
*Columbia University
SUNC Chapel Hill
Abstract
Recent efforts to scale Transformer models have been successful across a wide range of tasks [77]. However, fine-tuning these models for downstream tasks can be expensive, requires updating large number of parameters in the Transformer model. Parameter-efficien fine-tuning (PEFT) approaches have emerged as viable alternative that allow us to fine-tune models by updating only a small number of parameters. In this work, we propose general framework for parameter efficient fine-tuning using structured unrestricted-ret
matrices (SURM), which can serve drop-in replacement for popular approaches such as Adapters and LoRA. Unlike other methods like LoRA, SURMs provides more flexibility in finding the right balance between compactness and expressiveness. This is achieved by using low displacement rank matrices (LDRMs), which has not been used in this context before. SURMs remain competitive with baselines, often providing significant quality improvements while using smaller parameter budget. SURMs achieve 5-7% accuracy gains various image classification tasks while replacing low- rank matrices in LoRA. also results in up to 12x reduction of the number parameters in adapters (with virtually loss in quality) on the GLUE benchmark.
Introduction
In recent years, large-scale Transformer models have demonstrated impressive performance across wide range of domains, including natural language processing (NLP) [20, 8J, vision [36], robotics [7]. and even multi-modal settings [81]. For many applications. single large pre-trained model is adapted for several downstream problems. Fine-tuning, where all the model parameters are updated, a popular way to adapt pre-trained model new task domain. However, fine-tuning large models specific downstream tasks requires significant computational resources and involves massive memory footprint, as each task necessitates storing its own set of parameters.
Parameter-efficient fine-tuning (PEFT) methods have emerged as the preferred methodology to adapt pre-trained Transformers to different downstream tasks. PEFT methods often achieve performance par with full fine-tuning while training only a small number of parameters [80, 45]. PEFT techniques involve either training a small subset of the model's parameters [84, 42] integrating small modular layers while freezing the base model's weights [26, 25J. There are two popular classes of methods to inject additional parameters: (a) using small modular layers inside Transformers called adapter layers [59], and (b) constraining the updates as low-rank matrices (LoRA) [26].
Although adapters and LoRA (including their variants) differ architecturally and conceptually, they share a common reliance on low-rank matrices. The success of these methods has been attributed to the low intrinsic dimensionality of the hidden representations in the pre-trained Transformer
Equal Contribution
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

SURM
Full Fun-unng
LoKA
Acieptor
KAdiptition
Approximation Error
0.75
Accuracy
Lin, Prodinn
84-
Transfomer
Tuning
Probing
0.70
DITII
LePE
82-
0.65
80-
LN Tunnng
0.60
10a
107 10f
LowRank Kronecker Circulant Toeplitz
Number of Perameters
Figure I: Left: Approximating PSD matrix using low rank matrix, Kronecker product of matrices, circulant matrix, and Toeplitz matrix. We repeat our experiment 10 times and for each trial, we observe that low rank matrix is the worst approximator followed by Kronecker product, circulant, and Toeplitz. Right:
The tradeoff between accuracy and parameter numbers of various PEFT methods. Results are measured across image datasets using CLIP-VIL VIT. Our methods appear in the top right corner (in blue) and achieve the best performance among various strong baseline methods.
models [1, 70]. These low-rank methods primarily aim approximate updates, which, in general, not low rank. Hence, there's no justification for imposing low-rank constraints on them. Motivated by this insight, we explore alternative classes of matrices-ones that aren't necessarily low rank but characterized by linear number of parameters while exhibiting impressive approximations across various matrix classes. We present Fig. 1 as preview of the motivating results. In Fig. I (left), we show that structured matrices (SURM) can approximate any random matrix better than low rank matrices. In Fig. (right), we show that when SURMs are used for parameter efficient fine-tuning outperforms existing PEFT methods (see more details in Sec. 4).
We propose novel paradigm of parameter efficient fine-tuning that leverages Structured Unrestricted- Rank matrices (or SURMs). SURMs provide similar efficiency gains as previous works in efficient fine-tuning, but their more expressive structure paves the way for quality improvements. In this work, we propose to perform parameter-efficient fine-tuning by parameterizing learnable weights as structured matrices. We focus on the sub-classes of SURMs: (1) Kronecker product of matrices
[3] and (2) low displacement rank matrices (LDRMs) [66, 6, 58, 54, 73]. To summarize, our primary contributions are:
We propose the class Structured Unrestricted- Rank matrices (SURMs) (Section 3), for parameter efficient fine-tuning of Transformers. SURMs include low-rank matrices used in LoRA, special cases. To the best of our knowledge, we are the first to apply LDRMs this context.
We demonstrate strong matrix approximation capabilities inherent in Low Displacement Rank Matrices, with a specific focus on circulant and Toeplitz matrices (Section 4).
We introduce class of alapter-layers using SURMs. achieving 12x reduction in parameters compared to adapters, with virtually no loss in quality on the GLUE benchmark (Section 6).
We achieve 5-7% accuracy gains over LoRA A on a wide variety of image datasets well as in low resource setting (VTAB-IL 1k benchmark). In some cases SURMs outperform full fine-tuning, while using only 55k training parameters (as shown in Fig. (right)).
Related Work
With the introduction of BERT [20] and GPT-2 [8], Transformer models trained on general text corpora have revolutionized the field of machine learning (ML). Since then, these models have continued to increase in size, with open-source variants adopting various architectures. Examples include encoder-decoder models such as T5 [64] with up to 20B parameters [67], and a range of auto-regressive decoder models like Llama [69], Pythia [4], Mistral [28], among others, varying in size from a few million 180B parameters [2]. These models can be easily adapted to downstream
tasks by fine-tuning on task-specific data, resulting in state-of-the-an performance across broad

---

spectrum of downstream tasks. Due to the computational infeasibility of fine-tuning all the parameters of these models, in-context learning [8] and prompt engineering [11, 22] have emerged as attractive alternatives to adapt models to downstream tasks. However, such adaptation results depend heavily on the design of the input prompt and tend to vary greatly with small perturbations of the prompts [48].
Consequently, many works have proposed various PEFT techniques. One of the earliest methods involves inserting the so-called adapter layers between existing layers a neural network [25, 59]. An adapter is typically an MLP with input, output, and a smaller middle layer, encoded by two low-rank matrices, making compact in terms of parameters. An extension of the adapter is Compacter [51]] which uses Tucker decomposition to parameterize the adapter layers and weight-sharing to reduce the number of trainable parameters. Various modifications and extensions of the above methods have been proposed [53, 24, 32, 52, 65]. Another popular PEFT technique is differentiable prompt-tune -tuming (DPT), which can be thought of as optimizing special tokens in the prompt [88]. However, these methods are limited by the sequence length of the underlying models. Even though DPT was originally developed for NLP, several works have extended it for computer vision tasks as well [83, 12, 27, 24].
One of the most popular PEFT methods is Low-Rank Adaptation (LoRA) [26], which imposes a low-rank constraint on the weight updates. The main difference between adapters and LoRA is that the learned LoRA weights can be merged with the frozen model weights during inference without adding any latency. Given the popularity of LoRA, there have been many works on extending it to different contexts like long-range modeling [13], multi-tasking [10] or improving its efficiency [19, 71, 46, 37, 31] among many others.
In general, low-rank matrices are studied extensively in various MI. applications [57, 87, 44, 61]. The research low displacement rank matrices (LDRMss) for ML is more narrow [89, 68, 41, 66, 15, 35, 62]. Although Kronecker matrices (a class of LDRMs) have been explored in the context of LDRMs [21, 24, 51J, the constituent matrices in the Kronecker product have low rank even in these work. In this work, we use fixed parameter budget but do not impose any rank-based condition. To the best of our knowledge, we are the first systematically explore the effectiveness of different structured matrices and introduce LDRMs for parameter-effictee
fine-tuming.
The rest of the paper is organized as follows: (a) We introduce the notion of Structured Unrestricted- Rank Matrices (SURM) that are used in this work (Section 3), (b) We motivate the usage of SURM by empirically showing the approximation qualities of these matrices (Section 4), (c) We use SURM as drop-in replacement for popular approaches such as Adapters and LoRA (Section 5), (d) We validate our approach across wide range of vision and NLP tasks (Section 6).
3 Structured irrestricted-Raant Matrices (SURM)
In this section, we will define the matrices that are used for parameter efficient fine-tuning, First, we define the concept of a structured matrix, which is generic term for matrix A E mm that can be represented by fewer than mn parameters. These matrices are useful because they reduce both space and time complexity when performing matrix multiplications.
A simple example of a structured matrix is a low rank matrix of the form W = ABT E R where A Rmxx, B E Raxr with r & min(m,n). n). In this work, our main focus is on those classes of structured matrices that are not restricted to be low-rank, which we refer to as Structured Unrestricted- Rank Matrices (SURM). Next, we present two classes of SURM matrices that we use for parameter efficient fine-tuning.
Low Displacement Rank Matrices. Our first class of SURMs is low displacement rank matrices (LDRMs). A matrix W E Cmxn is said to have (A, displlcceen structure if:
(A.((W) del AW WB = F.
(1)
where A E CraxI B E Cu F E C and F has low rank r (as compared to min(m, n)). We call V A, the displacement rank operator, parameterized by A and B.
For a given W, there can exist several pairs of (A,B) matrices satisfying Eq. that produce a low- rank matrix, F. Some examples of such (A, B) pairs include: (Z, Z), (Z, Z TT), (D,, Z ZT), (D,, D,)) (for x + y). Here Z is circulant-shift matrix and D is a diagonal matrix with nonzero entries equal to z. Low displacement rank matrices (W in Eq. 1) enable fast (sub-quadratic) matrix-vector multiplication and enhance the efficiency of other matrix operations, such as inversion. By selecting
3

---

co
Gp-1
2
a_1
Co
G-11
C2
d1
dg
a-1
dn B
C1
dg
Cm-
a_1
am
B
Cm-1
9m-2
Cm
d1
dg
(a) Circulant
(b) Toeplitz
(c) Kronecker
Figure 2: A schematic diagram illustrate the structure (a) Circulant, (b) Toeplitz, and (c) Kronecker product two matrices and B.
more complex (A, B) pairs, such as those involving general Jordan form matrices, it possible to consider more unstructured W that still have compact representations and support efficient matrix operations [56, 66). In this paper, we focus on classic low displacement rank matrices: circulant and toeplitz matrices, which are described below.
Circulant Matrices: A circulant matrix Ce Cm can be parameterized by its first row. The following rows are obtained from the previous one by applying right circulant shift. A schematic visualization of a circulant matrix is shown in Fig (a). Since we only need to store the first row, circulant matrices can be trivially encoded in (n)) space. They also support fast matrix-vector multiplication ((nn + m) log(n + m)) time using Fast Fourier Transform (FFT) [55].
2. Toeplitz Matrices: A toeplitz matrix T E Cm is matrix whose entries are constant along each diagonal. A schematic visualization of a toeplitz matrix is shown in Fig (b)). They can be parameterized using only their first row and column, allowing them to be encoded in O(n + m) space. Similar to circulant matrices, they support fast (( + m) log(n + m)) matrix-vector multiplication via FFT.
Kronecker Product of Matrices. Kronecker products are another class of structured unrestricted rank matrices that have low storage complexity and admit efficient matrix-vector multiplication. These matrices are obtained using a Kronecker product & of two matrices and B, as shown in Fig 2 (c). We provide more details about these matrices in Appendix A.3.
4 LDR-SURMs as General Approximators
In this section, we motivate the usage of structured unrestricted-rank matrices (SURMs) for parameter- efficient fine-tuning. In general, the parameter updates AW can be arbitrary matrices, and an effective parameterization of A AW should be sufficiently expressive to approximate them. Since we use structured update rank matrices (SURMs) to parameterize AW, we demonstrate that SURMs can approximate various classes of matrices. Without loss of generality, in this section, we assume that all our matrices have real entries and that weight matrices are square (n = m).
First, we recall the result from [66], which states that broad class of low displacement rank matrices, as well linear combinations Toeplitz (or their inverses) products?, can be parameterized as:
W(G. = Σ Z (g 1=1
where G [g1,... Br]. H [h..... hr] E Rur, and (v) (for any f E R, R*) is defined as:
V0
fea
fu
U1
Un
f0²
Zy(v)=
fun-1
Up
When f Zy(v) is a circulant matrix and when f f= -1 refer Zv(v) as siewacireulant matrix. Moreover, F can be decomposed follows: F GH for G = [gi.... .., gr]. [h,..., hr] E 12axr, One can think about rank r of F of controlling how "structured" W is.
MM..... M. for 2t and where each M, Toeplitz matrix or its inverse.

---

X C1
Co
C4
Figure 3: A circulant matrix with the first column given by vector (co, C1 C2; C3, C3,C4) be re-written as a linear combination of the orthogonal base circulant matrices (5 matrices with orange-entries corresponding one and other to zero). Such a closed-form decomposition is in general not possible for matrices W(G, H) and thus optimal approximators are found by gradient-descent.
From the above result, we see that W(G, H) the most expressive parameterization among the ones discussed far. To understand how they fare with SURMs in practice, evaluate their approximation qualities in two settings: (a) comparing (G, H) with circulant and Toeplitz matrices, and (b) comparing circulant and Toeplitz matrices with low-rank matrices.
4.1 Comparing W(G, H) with Circulant and Toeplitz. Matrices
We test the approximation capabilities of matrices ((G, H) (Eq. 2) and compare it with popular
classes of SURMs: circulant and Toeplitz matrices (Section 3). Specificallyy we use these structured matrices to approximate three broad classes of matrices: (a) random, (b) near-low-rank and (c) near- low-intrinsic-rank We denote the ground-truth matrix that we try to approximate as M E TR. 18.00x 100 and parameterized structured matrix as A (see more details about the setup in Appendix A.7). For all matrices, we obtain the parameters A using gradient descent on the loss function: || M
In Figure 5, we report the relative Frobenius norm error during training for different settings. In Fig 5 (top left), we use W(G, H) with different: r (rank of F in Eq. 1) is used to approximate random matri- ces. While the best approximations are achieved for larger values of (specifically. r 20), it is inter- esting to note that the final error does not decrease monotonically with increasing r. For the remaining class of matrices M, which are close to low-rank and therefore easier to approximate, we experiment with smaller values of r and report the results in Figure 5 (left column, middle and bottom). In this case, we observe that the three top-performing approximators W(G, H) were trained with r = 1,2, 4. These re- sults indicate that for more structured ground truth matrices (even if they are not necessarily low-rank),
LoRA
SURM (Circulant)
SURM (Toeplit2)
SURM [Symm. Taeplitz)
Training Loss
Full tuning
10c
10
16a
10a
10
Steps
Figure 4: Fitting the pinwheel dataset with frozen embedding layer using various SURM- based PEFT methods and LoRA. LDRMs with very low rank for the corresponding F are sufficient.
Motivated by the results showing that LDRMs with low r' can serve as effective approximators, we use circulant and Toeplitz matrices to approximate wear-to-low-rand and www-intrinsic-rat matrices. In the three plots shown Fig. 5 (right column), we observe that approximations using Toeplitz matrices (using twice as many parameters as circulant matrices) offer negligible gains and are only beneficial the near-low-rank case. For the low-intrinsic case, circulant matrices outperform Toeplitz ones. Overall, circulant matrices with few parameters achieve strong performance in this setting.
4.2 Comparing Low Rank with Circulant and Toeplitz Matrices
In this section, we focus on the difference in approximation qualities between low rank matrices and the circulant and Toeplitz matrices under a fixed parameter budget. We use the following settings:
Pleass note that for circulant and Toeplitz matrices, it is also possible to obtain closed-fon solution for the matrix (see Fig 3 & Appendix A.6).
5

---

random
10
10R.15
1:10
low-rank]I-5) epsilen
crcolant Toepitt
LDR:20
LDR:30
1.0
error
1.06
1.00
50
75
100
125
150
175
200
0
250
500
750
1000
1250
1500
1750
2009
iterations
iterations
low-rank(1=20) + epailen
LON:
1.05
low-rank(==10) + epallon
drouant Toeplit
100:
6-
LON:
1.01
3.03
erTor
1.02
2-
1.00
25
300
125
150
175
200
750
1750
Iterations
iterations
low-intrinsic-ank +
epsioon
low-irtrinsc-rank
Toephts
1.0
1.5
error
1.4
20-
12-
3.0
500
750
1000
1500
1750
2000
iterations
iterations
Figure 5: Illustration of the approximation capabilities of different LDRMs. The y-axis depicts the relative Frobenius norm error ||A - / between the groundtruth M and the approximator A. (Left Column Top): We approximate a random Gaussian matrix M with matrices W(G. H) using different r (LDR: r). (Left Column Middle) We approximate near-low- matrices M using smaller values r. (Left Column Bottom): Similar setup to approximate near-low-intrinsicraall matrices M. (Right Column): We perform analogous studies with circulant and Toeplitz matrices, where the ground truth has low rank or low-intrinsic rank.
Approximating Symmetric Positive Definite Matrices. We use a PSD matrix M E 500x50 with L -nrrmalized rows in this experiment. We compare the errors to approximate M using circulant, (symmetric) Toeplitz, low-rank matrices, and Kronecker product of two matrices. We use fixed parameter budget and repeat this experiment 10 times. We report the results Figure I (left). For each of these 10 trials, we observe that the circulant and Toeplitz achieve the lowest error, therefore the best approximation quality (see more details in Appendix A.7).
Fitting Toy Dataset. We create a synthetic pinwheel dataset with 5 spokes as shown in Figure 9 (left). We fit this dataset using a simple neural network with one hidden layer with a matrix W E 644 In this experiment, we replace W with a rank 1 LoRA, a circulant, a symmetric Toeplitz, and Toeplitz matrix with all parameterizations having the same number of training parameters). In Fig 4), we report the training loss curves of this experiment. We observe that the LoRA layer struggles to fit the data whereas the LDRMs show similar performance to full fine-tuning (Fig 4). These results show the impressive expressive power of these matrices. Therefore, we conclude that LDRMs with particularly low displacement rank serve as good approximators for various matrices. We perform additional experiments and provide more details in Appendix B.

---

Table ViT-experiments: Baseline numbers are taken from [24]. The best numbers are highlighted in bold and the second-best numbers are underlined. Hyperparameter settings are followed from [24]. We find that SURM consistently outperform very strong baselines with 2-3x reduction in parameters.
Method
# Param
(x10")
CIF-10
CIF-100
SUN397
DID
STL10
CIF-10
CIF-100
SUX397
DTD
STL10
Fine-tuning
86.6
99.0
92.4
75.0
72.4
99.6
97.7
85.4
73.8
79.0
99.7
Alin. Tuning
28.4
93.9
85.7
73.8
69.2
99.2
96.8
81.8
73.1
75.0
97.6
Trans. Probing
3.2
86.9
86.9
76.7
72.0
99.0
95.6
80.1
74.3
75.9
98.5
Linear Probing
0.049
96.3
87.7
70.1
72.7
98.7
94.8
80.1
72.4
75.4
98.4
BitFit
0.358
92.3
81.0
71.8
72.6
99.0
92.1
76.0
70.8
75.9
Adapter
1,505
98.4
90.6
74.2
71.0
99.3
94.7
81.4
77.1
78.0
99.0
DrapterDropp
0.174
96.8
88.4
72.3
70.2
99.6
93.3
78.3
71.4
77.1
98.0
LORA
0.219
98.7
90.6
73.6
70.4
99.4
95.1
78.1
80.8
78.1
99.2
LORA-FIX
0.148
88.3
72.0
65.5
99.0
77.1
IN Tuning
0.075
92.2
71.7
72.0
69.0
98.8
82.5
76.6
66.7
72.4
99.1
LEPE
0.167
93.7
90.8
73.2
69.8
99.1
95.1
78.9
68.0
75.4
98.0
RPB
0.145
96.7
87.0
72.4
70.4
98.9
94.7
77.1
68.4
75.2
97.9
KAdaptation
0.114
97.9
91.2
75.1
71.4
99.4
95.9
84.8
74.0
78.1
99.2
SURM (Kronecker)
0.055
98.3
89.9
78.6
75.4
99.6
97.1
85.0
80.7
79.0
99.2
SURM (Toeplirz)
0.055
90.2
79.1
75.6
99.7
97.1
84.5
77.9
SURM (Circulant)
0.055
98.0
90.7
80.5
75.7
99.8
97.0
84.6
81.1
78.6
99.3
Integration of SURMs with PEFT
Motivated by the results from the previous section, use SURMs as drop-in replacements for various PEFT methods. In this section, we present the integration of SURMs in two popular classes of PEFT methods: LoRA and Adapters.
5.1 Integration of SURMs in LoRA
LoRA [26] uses a low rank matrix to parameterize the weight matrix updates. Formally, given a pre-trained weight matrix W. then the updated matrix is W W + adW, where AW = AB and A E Rmxr B E Raxr for r & min(m,n)) and a is fixed scaling parameter. For efficient training, A W needs to be initialized as zero-matrix. LoRA performs this by choosing initializing A to be the zero matrix and B to be a random matrix. In this work, we propose to parameterize AW using structured unrestricted rank matrices. Next, provide the details of parameterizing A W using different SURM matrices (assuming m = n for simplicity).
Circulant Matrices. In this setting, we parameterize the updates as: W = C₁ ② C2. where C, E axx are circulant matrices encoded using n-dimensional vector, r; R". We use Hadamard products (C₁ C C2) instead of conventional matrix products as it can be computed efficiently. The construction of Hadamard products which is O(n) is quicker than the process involved in efficient multiplication (which is O O(nlog(n)). To enable vero-initialization, we initialize C₁ as a zero-vector and C2 as random-vector Additionally, this approach does not compromise the expressiveness of the network, as the result of the Hadamard product is also circulant matrix.
Toeplitz Matrices. Similar the previous setting, we use two Toeplitz matrices to parameterize: AW TT2,, g (T),x)), where Tı, T2 E are Toeplitz matrices, and is the operator that allows veccoor multiplication with Toeplitz matrices (see Appendix A.3 ). Each Toeplitz matrix T R is parameterized using an n-dimensional vector encoding its first row and an n-dimensional vector с encoding its first column (2n total parameters). This formulation leads to the 4n 2 trainable parameters. To further reduce this number, we constrain the T,, T2 to be symmetric, reducing the total number of trainable parameters to 2n. To enable rero-initialization. we initialize T₁ as zero matrix and T2 is randomly initialized.
efficient matrix -ector
Kronecker Product of Matrices. In this setting, we parameterize: AW x B, where A Rrixre E R A 2. The hyperparameters f1,72 allow us to control the trainable parameter count and the rank of AW. In contrast to low-rank matrix updates, we can create matrices AW of fairly large ranks while keeping the number trainable parameters small (see Appendix A.2). To enable zero-initian aero-initialization, set A as zero matrix and B as random matrix.
7

---

Table 2: Results the VTAB-1k benchmark. Baseline numbers taken from [30] and [50]. Best numbers are highlighted in bold and the second numbers are underlined. We observe that SURM one of the oop-prformnin PEFT methods on almost all datasets.
# Params (x10*)
Method
CTF-100
Cal-101
DTD
F-102
Pets
SVHY Sun397
Cam.
EuroSAT
Res-45 Retino.
Finc-tuning
86.6
68.9
87.7
64.3
97.2
86.9
87.4
38.8
79.7
95.7
84.2
73.9
Linear
0.049
64.4
85.0
63.2
97.0
86.3
36.6
51.0
78.5
87.5
68.5
74.0
BidFit
0.013
72.8
87.0
97.5
85.3
78.7
91.6
72.9
69.8
VPT-Shallow
0.063
77.7
86.9
62.6
97.5
87.3
74.5
51.2
78.2
92.0
75.6
72.9
VPT-Deep
0.531
78.8
90.8
65.8
98.0
88,3
78.1
49.6
81.8
96.1
83.4
68.4
Adapter
0.157
69.2
90.1
68.0
98.8
89.9
82.8
54.3
84.0
94.9
81.9
75.5
AdaptFonner
0.157
70.8
91.2
70.5
99.1
90.9
86.6
54.8
83.0
95.8
84.4
76.3
LoRA
0.295
67.1
91.4
69.4
98.8
90.4
85.3
84,9
95.3
84.4
73.6
NOAH
0.361
69.6
92.7
70.2
99.1
90.4
86.1
53.7
84.4
95.4
83.9
75.8
Fact-TK
0.069
70.6
90.6
70.8
99.1
90.7
88.6
54.1
84.8
96.2
84.5
75.7
SSF
0.240
69.0
92.6
75.1
99.4
91.8
90.2
52.9
87.4
95.9
87.4
75.5
RepAdapter
0.110
70,7
91.6
72.5
99.1
91.3
88.5
54.2
84.1
95.7
85.1
74.6
SURM (Kroneoker)
0.055
79.6
88.7
73.1
99.1
92.5
74.8
54.7
82.2
94.3
81.9
75.4
SURM (Toeplitz)
0.055
79.5
88.9
72.7
99.1
91.5
74.7
55.8
83.6
96.2
82.2
76.0
SURM (Circulant)
0.055
80.6
87.5
74.7
99.5
93.3
74.9
57.1
85.3
96.0
83.7
75.4
CIFAR-10
CIFAR-100
SUN397
DTD
STL10
Accuracy (%)
SJN (ecencier)
[Canedeer)
(Rronedor)
SJ8 (Rooecter) S.RM (Gimu andl S.NV (leept
S-NN (Kereedee)
S.in (C/ou ant] 5.002 (leppi (3)
Sune (Canctont)
SURN (CHOAAN
S.NM (Cioane)) S.NN D'eppit
SUaM (lees
SUMM (Tkeppi2
Fraction of Training Data
Figure 6: Low Resource Training. Accuracy of SURM CLIP-VIT models as function of the training data fraction. The results show that SURM can achieve comparable accuracy with as low as ~ 2% of the training data for easier tasks like CIFAR 10 and ~ 20% for harder tasks like SUN397.
In all the above settings, it is possible to increase the number of training parameters by relaxing the structure of the matrix, AW. This can be performed by introducing more matrices in the product chains, utilizing asymmetric Toeplitz matrices, adjusting the sizes of factors in the Kronecker product, or employing sums of such matrices. Another way to enhance layer expressiveness is by experimenting with combinations of different LDRMs, such as mixing circulant and skew-circulant matrices. broad class matrices, including low-rank ones, can be represented as sums these matrices (see Theorem A.2 and the subsequent discussion).
5.2 Integration of SURMs in Adapters
Adapters [25] are small bottleneck networks into Transformer layers as shown below:
== + a (XB)A,
where a-)) is a non-linear activation function, X E Rxxax represents input to the layer (b: batch size, sequence length), A R*** E Rx are low-rank matrices (r < n) and Y is the output of the layer. For simplicity, layer norms and bias terms are not included in the equation. We use SURMs drop-in replacement for matrices A and B. Next, we will provide details of integrating SURMs within the adapter setting. Additional details are provided in Appendix A.5.
Circulant Matrices. In this setting, apply two circulant matrices C1, C2 (encoded by F 12), resulting in the adapter block: Y= X+o 012 X)) + b. where f is an operator that efficiently computes the matrix multiplication between input X and the circulant matrix encoded by the vector I1 o r2 (Appendix A.3). To enable zero pero-initialization, the vector rj is initialized randomly while ra and b are initialized zero vectors.
Toeplitz Matrices. this setting, we use two symmetric Toeplitz matrices T1, T2, where Tr and b is initialized as a zero vector and T2 is initialized randomly. We then define the adapter layer as: Y = X + (T,, (T2, X))) + b, where g an operator that efficiently computes the matrix multiplication between input X and Toeplitz matrix.
8

---

Vision
GLUE
SURM (Adapter)
88
SURM
FLI Fncruninng
83.5
Actaonor
Phirter
Performance
Adoplet
KAdeptation
83.0
Fulline-tuning
AdaMi
Compoccee
LORA
Lin Prokiig
82.5
84
UnFEFT
Prefix
luning
Proning
87.0
Serial
81.5
81.0
80
LN Tuning
80.5
MAM
LoRA-Fix
AA
10f
10'
10
10
80.0
10a
10
10"
20
Number of Parameters
Figure 7: Left: Tradeoff between performance and parameter count for various PEFT methods. We report the average results across image datasets using ViT-B (complete results in Table 1). Right: Average performance across GLUE benchmark (see complete results in Table 5). SURMs appear in the top right corner and perform best among various strong baseline methods in both settings.
Kronecker Product of Matrices. In this case, we rewrite Equation 4 as: Y = X (B)AA)) where @ is the Kronecker product. In this case, B initialized randomly and A and are initialized by zeros. In all experiments using SURM-adapters, (-) is the GeLU non-linearity.
6 Experiments
In this section, show the effectiveness of our proposed methods in a wide range of vision and NLP tasks through extensive empirical studies.
Image Classification Experiments. We evaluate SURM on several vision datasets: CIFAR 10,
CIFARI00 [39]. SUN397 [79]. DTD [16] and STL10 [17]. We experiment using ViT-B/16 [36] & CIT--ViT- [63] as base models and inject trainable parameters Q K, V matrices in the LoRA setting. We report the results using biT are presented in Table (left). We observe that SURM consistently outperforms 12 baseline methods (that use up to 10x parameters). On three out of the five tasks, SURMs emerge as the top performers, surpassing LoRA by a margin of up to 5-7% while achieving competitive performance on the remaining tasks. We report the results using Clip-ViT in Table (right). In this setting, SURM among the top two methods across all 5 tasks. SURM also uses fewer trainable parameters, reducing them by 3.65x compared to LoRA and 2.4x compared to LoRA-Fix.
Low Data Regime. We evaluate SURM in low data regime using VTAB-Ik datasets [85] and the ViT model. VTAB-Ik focus on the NATURAL and SPECIALIZED subsets of VTAB. In Table 2, we observe that SURMs are among the top methods on 10 datasets while being competitive on the remaining tasks.
diverse collection of vision datasets with only 1000 training examples. We
We evaluate different variants SURM and train on a varying fraction of data on 5 datasets using Clip-ViT ViT model. We report the results in Figure 6. We observe that the circulant SURM works best in low data regime. Furthermore, SURM achieves the performance of full fine-tuning trained on the entire dataset with only small fraction of the data. For more challenging datasets like SUN397, achieve comparable accuracy using approximately 20% of the training data, while for datasets such as CIFAR 10 and STL10, only about 2% is needed.
Large Data Regime. We perform experiments to show that SURM generalizes well in large data regimes. On ImageNet [18] and iNat2021 [72]. SURM achieves performance comparable to full fine-tuning while using only 0.06% of the training parameters (see detailed results in Appendix B.2).
NLP Experiments. We extensively evaluate SURM models on the GLUE benchmark [74] using BERT [20]. We compare with different adapter baselines and other PEFT techniques. These include full-finetuning. Adapter (Houlsby) and Adapter (Pfeiffer), among others (we report the corresponding results from [59]). BiTFit results are taken from [84] (except QQP numbers which are obtained from [9]) and the numbers for AA-adapters from [53]. Prefix, Serial, AdaMix, UniPELT,

---

Table 3: Image Segmentation results on the Synapse multi-organ segmentation dataset. SURMs achieve comparable performance with specialized architectures developed for medical imaging while being more parameter efficient.
Methods
DSC
Aorta
Gallblad.
Kid. (L)
Kid. (R)
Liver
Pancreas
Spleen
Stomach
U-Net
76.85
89.07
69.72
77.77
68.60
93.43
53.98
86.67
75.58
Alt-UNet
77.77
89,55
68,88
77.98
71.11
93.57
58.04
87.30
75.75
TransUnet
77.48
87.23
63.13
81.87
77.02
94.08
55.86
85.08
75.62
SwinUnet
79.13
85.47
66,53
83.28
79.61
94.29
56.58
90.66
76.60
SAMed
81.88
87.77
69.11
80.45
79.95
94.80
72.17
88.72
82.06
LORA (rank=1)
78.26
81.86
64.54
81.97
81.18
93.79
60.80
88.33
73.64
SURM (Circulant)
80.11
83.04
64.92
81.37
80.96
94.21
69.11
88.15
79.06
Parallel, MAM, and AutoPEFT numbers are taken from [90]. The results for the remaining baselines are replicated by us. More experimental details can be found in Appendix B.
For brevity, we summarize the average performance across 8 tasks for SURM-adapters and compare it to 11 baselines, in Fig (right). We observe that SURM achieve much better performance while using a fraction of the parameters (the complete results are reported in Appendix Table 5). We also observe that SURM (integrated into LoRA) outperforms the baseline LoRA, under the same parameter budget. This shows the effectiveness of using structured matrices as a drop-in replacement for low rank matrices used in LoRA. We further analyze the representations learnt by SURMs and LoRAs (Appendix B.4). We find that LoRA learns weights that are very similar to the pre-trained weights whereas SURM is able to explore a larger parameter space (an observation similar to [91]).
Large-scale Experiments. In this setting, we inte- grate SURMs in LLMs. Specifically, we use matrices of the form W(G. G,, H) (as described in Eqn 2) to in- crease the number of training parameters. We the experimental setup introduced in [29], where the
MoRA
3.5
LoRA
3.0
SURM (W/ Circulant)
9
2.5
SURM (w/ W(G H))
LLM tries to fit dataset of UUID pairs using the
g
Training
2.0
Llama-2-7B model [69]. This was shown to be a challenging task (UUID prediction is significantly different from the pre-training tasks) that requires higher rank values in LoRA. We report the results in Fig. 8, demonstrating that SURMs is able to fit the data, whereas other methods struggle to do so (see more details in Appendix B.
1.5
1.0
0.5
0.0
20
40
60
100
120
Iterations
Figure 8: Fitting the UUID dataset using Llama-2-7b. We fit the data using various SURM-based PEFT methods and LoRA. (SAM) [34] is used as the foundation model for this task. We follow [86] and adapt the Q V in ViT base image encoder in SAM. Finally, in this low data regime, we use Circulant variant of SURM as it is the best performing variant (Fig. 6). We report the Dice similarity coefficient (DSC) metric for each of the organ segmentations and their average (higher is better). For a fair comparison, we include LoRA with rank 1, matching the exact parameter count of Circulant. The results are presented in Table 3. We report the baseline performance from [86]. SURMs compare favorably with specialized architectures developed for medical imaging like U-Net, Attention U-Net, Transformer-bate U-Net, and the Swin U-Net even though they have significantly higher number of training parameters than our method (see details in Appendix B.
Image Segmentation. Next, we focus on the ex- tremely challenging task of medical image seg-
mentation using Synapse multi-organ segmentation
dataset [82].
Anything
7 Conclusion
We introduce structured unrestricted-rat matrices (SURMs) as an alternative to low-rank matrices for the parameter-efficient fine-tuning of large Transformer models. In this setting, structured matrices form the comeessonn of comprehensive framework, offering a solid base for various parameter efficient fine-tuning methods, such as adapters and LoRA, with enhanced efficiency. SURMs improve the overall effectiveness of PEFT, contributing to its efficient integration into diverse models and domains. Based on extensive numerical experiments and theoretical insights, we conclude that the Circulant variant is our most performing variant (in terms of speed and accuracy).
10

---

8 Author Contributions
AS designed the integration of SURM in Adapters and LoRA and ran the GLUE experiments. AD helped in developing the integration and ran all image experiments. KC came up with the idea of using LDRMs in the context of PEFT. SBRC helped in running various large-scale experiments and writing the manuscript. All authors contributed to the writing of this manuscript.
References
[1] Armen Aghajanyan, Sonal Gupta, and Luke Zettlemoyer. Intrinsic dimensionality explains the effectiveness of language model fine-tuning. In Chengqing Zong, Fei Xia, Wenjie Li, and Roberto Navigli, editors, Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference Natural Language Processing (Volume I: Long Papers), pages 7319-7328, Online, August 2021. Association for Computational Linguisties.
[2] Ebtesam Almazrouei, Hamza Alobeidli, Abdulaziz Alshamsi, Alessandro Cappelli, Ruxan- dra Cojocaru, Mérouane Debbah, Étienne Goffinet, Daniel Hesslow, Julien Launay, Quentin Malartic, et al. The falcon series of open language models. arXiv preprint arXiv:2311.1686,, 2023.
[3] Michele Benzi and Valeria Simoncini. Approximation of functions of large matrices with kronecker structure. Numerische Mathematik, 135(1):1-26, 2017.
[4] Stella Biderman, Hailey Schoelkopf, Quentin Gregory Anthony, Herbie Bradley, Kyle O' O'Brien, Eric Hallahan, Mohammad Aflah Khan, Shivanshu Purohit, USVSN Sai Prashanth, Edward Raff, et al. Pythia: A suite for analyzing large language models across training and scaling. In International Conference on Machine Learning, pages 2397-2430. PMLR, 2023.
[5] James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman- MMine,, and Qiao Zhang. JAX: composable transformations of Python+NumPy programs, 2018.
[6] Richard P Brent. Stability of fast algorithms for structured linear systems. Fast reliable algorithms for matrices with structure, pages 103-116 1999.
[7] Anthony Brohan, Noah Brown, Justice Carbajal, Yevgen Chebotar, Joseph Dabis, Chelsea Finn, Keerthana Gopalakrishnan, Karol Hausman, Alex Herzog, Jasmine Hsu, Julian Ibarz, Brian Ichter, Alex Irpan, Tomas Jackson, Sally Jesmonth, Nikhil Joshi, Ryan Julian, Dmitry Kalashnikov, Yuheng Kuang, Isabel Leal, Kuang-Huei Lee, Sergey Levine, Yao Lu, Utsav Malla, Decksha Manjunath, Igor Mordatch, Ofir Nachum, Carolina Parada, Jodilyn Peralta, Emily Perez, Karl Pertsch, Jornell Quiambao, Kanishka Rao, Michael Ryoo, Grecia Salazar, Pannag Sanketi, Kevin Sayed, Jaspiar Singh, Sumedh Sontakke, Austin Stone, Clayton Tan, Huong Tran, Vincent Vanhoucke, Steve Vega, Quan Vuong, Fei Xia, Ted Xiao, Peng Xu, Sichun Xu, Tianhe Yu, and Brianna Zitkovich. Rt-1: Robotics transformer for real-world control at scale. arXiv preprint arXiv:2212.0688 2023.
[8] Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, 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. arXiv preprint arXiv:2005. 14165, 2020.
[9]
Jin Cao, Chandana Satya Prakash, and Wael Hamza. Attention fusion: light yet efficient late fusion mechanism for task adaptation in NLU. In Marine Carpuat, Marie-Catherine Marn- effe, and Ivan Vladimir Meza Ruiz, editors, Findings of the Association for Computational Linguistics: NAACI. 2022, pages 857-866, Seattle, United States, July 2022. Association for Computational Linguistics.
11

---

[10] Arnay Chavan, Zhuang Liu, Deepak Gupta, Eric Xing, and Zhiqiang Shen. One-for-all: Generalized lora for parameter-efficient fine-tuning, arXiv preprint arXiv: 2306.07966 2023.
[11] Banghao Chen, Zhaofeng Zhang, Nicolas Langrené, and Shengxin Zhu. Unleashing the potential of prompt engineering in large language models: comprehensive review. arXiv preprini arXiv:2310. 14735, 2023.
[12] Shoufa Chen, Chongjian Ge, Zhan Tong, Jiangliu Wang, Yibing Song, Jue Wang, and Ping Luo. Adaptformer: Adapting vision transformers for scalable visual recognition. arXiv preprint ar0iv:2205. 13535, 2022.
[13] Yukang Chen, Shengju Qian, Haotian Tang, Xin Lai, Zhijian Liu, Song Han, and Jiaya Jia. Lon- glora: Efficient fine-tuning of long-context large language models. In The Twelfth International Conference on Learning Representations, 2024.
[14] Zhangchi Chen. On nonsingularity of circulant matrices. Linear Algebra and its Applications, 612:162-176, March 2021.
[15] Y. Cheng, F. X. Yu, R. S. Feris, S. Kumar, A. Choudhary, and S. Chang. An exploration of parameter redundancy in deep networks with circulant projections. In 2015 JEEE International Conference on Computer Vision (ICCV), pages 2857-2865, Los Alamitos, CA, USA, dec 2015, IEEE Computer Society.
[16] M. Cimpoi, S. Maji, I. Kokkinos, S. Mohamed, and A. Vedaldi. Describing textures in the wild. In Proceedings of the IEEE Conf. on Computer Vision and Puttern Recognition (CVPR), 2014.
[17] Adam Coates, Andrew Ng, and Honglak Lee. An Analysis of Single Layer Networks in Unsupervised Feature Learning In AISTATS, 2011. https://cs. stanford. edu/-acoates/ paperrs/coatesslengg..iii aistats 2011002111011 .df.
[18] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large- scale hierarchical image database. In 2009 IEEE Conference on Computer Vision and Pattern Recognition, pages 248-255, 2009.
[19] Tim Dettmers, Artidoro Pagnoni, Ari Holtzman, and Luke Zettlemoyer. Qlora: Efficient finetuming of quantized llms. Advances in Neural Information Processing Systems, 36, 2024.
[20] Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Confer- ence of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume (Long and Short Papers), pages 4171-4186, Minncapolis, Minnesota, June 2019. Association for Computational Linguistics.
[21] Ali Edalati, Marzich Tahaci, Ivan Kobyzev, Vahid Partovi Nia, James J Clark, and Mehdi Rezagholizadeh. Krona: Parameter efficient tuning with kronecker adapter. arXiv preprint arXiv:2212. 10650, 2022.
[22] Jindong Gu, Zhen Han, Shuo Chen, Ahmad Beirami, Bailan He, Gengyuan Zhang, Ruotong Liao, Yao Qin, Volker Tresp, and Philip Torr. A systematic survey of prompt engineering vision-language foundation models. arXiv preprint 2rxiv:2307.12988. 2023.
[23] Junxian He, Chunting Zhou, Xuezhe Ma. Taylor Berg- mirn-KKikkatrkk. and Graham Neubig. To- wards unified view of parameter-efficient transfer learning. In International Conference on Learning Representations 2022.
[24] Xuehai He, Chunyuan Li, Pengchuan Zhang, Jianwei Yang, and Xin Eric Wang. Parameter- efficient model adaptation for vision transformers. arXiv preprint arXiv: 16329, 2022.
[25] Neil Houlsby, Andrei Giurgiu, Stanislaw Jastrzebski, Bruna Morrone, Quentin De Laroussilhe, Andrea Gesmundo, Mona Attariyan, and Sylvain Gelly. Parameter-efficient transfer learning for NL.. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 2790-2799. PMLR, 09-15 Jun 2019.
12

---

[26] Edward Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li. Shean Wang, Lu Wang, and Weizhu Chen. LoRA: Low-rank adaptation of large language models. In International Conference on Learning Representations, 2022.
[27] Menglin Jia, Luming Tang, Bor-Chun Chen, Claire Cardie, Serge Belongie, Bharath Hariharan, and Ser-Nam Lim. Visual prompt tuning. In European Conference Computer Vision (ECCV), 2022.
[28] Albert Q Jiang, Alexandre Sablayrolles, Arthur Mensch, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Florian Bressand, Gianna Lengyel, Guillaume Lample, Lucile Saulnier, et al. Mistral 7b. arXiv preprint ar arXiv:2310.06825, 2023.
[29] Ting Jiang, Shaohan Huang, Shengyue Luo, Zihan Zhang, Haizhen Huang, Furu Wei, Weiwei Deng, Feng Sun, Qi Zhang, Deqing Wang, and Fuzhen Zhuang. Mora: High-rank updating for parameter-efficient fine-tuning, arXiv preprint vrXiv:2405.12136 2024.
[30] Shibo Jie and Zhi-Hong Deng. Fact: Factor-tuning for lightweight adaptation vision transformer. In Proceedings of AAAI Conference on Artificial Intelligence (AAAT), 2023,
[31] Damjan Kalajdzievski. A rank stabilization scaling factor for fine-tuning with lora. arXiv preprint arXiv:2311.03372. 2023.
[32] Rabech Karimi Mahabadi, Sebastian Ruder, Mostafa Dehghami, and James Henderson. Parameter-effcieent multi-task fine-tuning for transformers via shared hypernetworks. In Annual Meeting of the Association for Computational Linguistics, 2021.
[33] Diederik P Kingma. Adam: method for stochastic optimization. arXiv preprint 1421v:1412.6980, 2014.
[34] Alexander Kirillov, Eric Mintun, Nikhila Ravi, Hanzi Mao, Chloe Rolland, Laura Gustafson, Tete Xiao, Spencer Whitehead, Alexander C Berg, Wan-Yen Lo, et al. Segment anything. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 2023.
[35] Matthias Kissel and Klaus Diepold. Structured matrices and their application in neural networks: survey, New Generation Computing, (13766977- Sep 2023.
[36] Alexander Kolesnikov, Alexey Dosovitskiy, Dirk Weissenborn, Georg Heigold, Jakob Uszkoreit, Lucas Beyer, Matthias Minderer, Mostafa Dehghani, Neil Houlsby, Sylvain Gelly, Thomas Unterthiner, and Xiaohua Zhai. An image is worth 16x16 words: Transformers for image recognition scale. In Ninth International Conference on Learning Representations. ICLR, 2021.
[37] Soroush Abbasi Koohpayegani, Navaneet K L, Parsa Nooralinejad, Soheil Kolouri, and Hamed Pirsiavash. NOLA: Compressing loRA using linear combination of random basis. In The Twelfth International Conference on Learning Representations, 2024.
[38] Simon Kornblith, Mohammad Norouzi, Honglak Lee, and Geoffrey Hinton. Similarity of neural network representations revisited. In International conference on machine learning, pages 3519-3529. PMLR, 2019.
[39] Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. Cifar- (canadian institute for advanced research). URI. http://www. cs. toronto. edu/kriz/cifar himl, 5(4):1, 2010.
[40] George Labahn and Tamir Shalom. Inversion of toeplitz matrices with only two standard equations. Linear Algebra and its Applications, 175:143-158, 1992.
[41] Daniele Lazzaro and Stefania Morigi. Matrix completion for matrices with low-rank displace- ment. Electronic Transactions on Numerical Analysis, 53:481 4999, 2020.
[42] Jaejun Lee, Raphael Tang, and Jimmy Lin. What would elsa do? freezing layers during transformer fine-tuning. arXiv preprint arXiv:1911.03090, 2019.
13

---

[43] Xiang Lisa Li and Percy Liang, Prefix-tuning: Optimizing continuous prompts for generation. In Chengqing Zong, Fei Xia, Wenjie Li, and Roberto Navigli. editors, Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the I Ith International Joint Conference on Natural Language Processing (Volume I: Long Papers), pages 4582-4597 Online, August 2021. Association for Computational Linguistics.
[44] Yuanzhi Li, Yingyu Liang, and Andrej Risteski. Recovery guarantee of weighted low-rank approximation via alternating minimization. In Maria Florina Balcan and Kilian Q Weinberger, editors, Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pages 2358-2367, New York, New York, USA, 20-22 Jun 2016. PMLR.
[45] Vladislav Lialin, Vijeta Deshpande, and Anna Rumshisky. Scaling down to scale up: A guide to parameter-efficient fine-tuning, arXiv preprint arXiv: 2303, 2023,
[46] Shih-yang Liu, Chien-Yi Wang, Hongxu Yin, Pavlo Molchanov, Yu-Chiang Frank Wang, Kwang- Ting Cheng, and Min-Hung Chen. Dora: Weight-decomposed low-rank adaptation. In Forty-first International Conference on Machine Learning. 2024.
[47] I Loshchilov. Decoupled weight decay regularization. arXiv preprint arXiv:1711.05101, 2017.
[48] Yao Lu, Max Bartolo, Alastair Moore, Sebastian Riedel, and Pontus Stenetorp. Fantastically ordered prompts and where to find them: Overcoming few-shot prompt order sensitivity. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 8086-8098 2022.
[49] Yuchen Lu, Zhen Liu, Aristide Baratin, Romain Laroche, Aaron Courville, and Alessandro Sordoni. Using representation expressiveness and learnability to evaluate self-supervised learning methods. Transactions on Machine Learning Research, 2023.
[50] Gen Luo, Minglang Huang, Yiyi Zhou, Xiaoshuai Sun, Guannan Jiang, Zhiyu Wang, and Rongrong Ji. Towards efficient visual adaption via structural re- parameterization, arXiv preprint arXiv:2302.08106. 2023.
[51] Rabeeh Karimi Mahabadi, James Henderson, and Sebastian Ruder. Compacter: Efficient low-rank hypercomplex adapter layers. arXiv preprint arXiv: 2106.046477 2021.
[52] Yuning Mao, Lambert Mathias, Rui Hou, Amjad Almahairi, Hao Ma, Jiawei Han, Scott Yih, and Madian Khabsa. UniPELT: A unified framework for parameter-efficien language model tuning. In Proceedings of the 60th Anmual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 6253-6264, 6264, 2022.
[53] Nafise Moosavi, Quentin Delfosse, Kristian Kersting, and Iryna Gurevych. Adaptable adapters. In Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 3742-3753, Seattle, United States, July 2022. Association for Computational Linguistics.
[54] Bernard Mourrain and Victor Pan. Multivariate polynomials, duality, and structured matrices.
J. Complex., (6(1):110-180 2000.
[55] Henri J Nussbaumer and Henri J Nussbaumer. The fast Fourier transform. Springer, 1982.
[56) Vadim Olshevsky and Mohammad Amin Shokrollahi. Matrix-vector product for confluent cauchy-like matrices with application to confluent rational interpolation. In F. Frances Yao and Eugene M. Luks editors, Proceedings of the Thirty-Secone Annual ACM Symposium on Theory of Computing, May 21-23, 2000, Portland, OR, USA, pages 573-581, ACM, 2000.
[57] Samet Oymak, Zalan Fabian, Mingchen Li, and Mahdi Soltanolkotabi. Generalization guaran- tees for neural networks via harnessing the low-rank structure of the jacobian. arXiv preprint arXiv:190k 003922 2019.
[58] Victor Y. Pan. Structured matrices and polynomials: unified superfast algorithms. Springer- Verlag, Berlin, Heidelberg, 2001.
14

---

[59] Jonas Pfeiffer, Andreas Rücklé, Clifton Poth, Aishwarya Kamath, Ivan Vulić, Sebastian Ruder, Kyunghyun Cho, and Iryna Gurevych. Adapterhub: A framework for adapting transformers. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Process- ing (EMNLP 2020): Systems Demonstrations, pages 46 46-54, Online, 2020. Association for Computational Linguistics.
[60] Phil Pope. Chen Zhu, Ahmed Abdelkader, Micah Goldblum, and Tom Goldstein. The intrinsic dimension of images and its impact on learning, In International Conference on Learning Representations, 2021.
[61] Daniel Povey, Gaofeng Cheng, Yiming Wang, Ke Li, Hainan Xu, Mahsa Yarmohammadi, and Sanjeev Khudanpur. Semi-orthogonal low-rank matrix factorization for deep neural networks. In Proc. Interspeech 2018, pages 3743-3747, 2018.
[62] Shikai Qiu, Andres Potapczynski, Marc Anton Finzi, Micah Goldblum, and Andrew Gordon Wilson, Compute better spent: Replacing dense layers with structured matrices. In Forty-first International Conference Machine Learning, 2024.
[63] Alec Radford, Jong Wook Kim, Chris Hallacy, A. Ramesh, Gabriel Goh, Sandhini Agar- wal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, Gretchen Krueger, and Ilya Sutskever. Learning transferable visual models from natural language supervision. In ICML, 2021.
[64] Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. Exploring the limits of transfer learning with unified text-lo-text transformer. Journal of Machine Learning Research, 21(140): 2020.
[65] Andreas Rücklé, Gregor Geigle, Max Gloekner, Tilman Beck, Jonas Pfeiffer, Nils Reimers, and Iryna Gurevych. Adapterdrop: On the efficiency of adapters in transformers. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pages 7930-7946. 2021.
[66] Vikas Sindhwani, Tara Sainath, and Sanjiv Kumar. Structured transforms for small-footprint deep learning. In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and Garnett, editors, Advances in Neural Information Processing Systems, volume 28. Curran Associates, Inc., 2015.
[67] Yi Tay, Mostafa Dehghani, Vinh Q Tran, Xavier Garcia, Jason Wei, Xuezhi Wang, Hyung Won Chung, Dara Bahri, Tal Schuster, Steven Zheng, et al. UL2: Unifying language learning paradigms. In The Eleventh International Conference on Learning Representations, 2023.
[68] Anna Thomas, Albert Gu, Tri Dao, Atri Rudra, and Christopher Ré. Learning compressed transforms with low displacement rank. Advances in neural information processing systems, 31, 2018.
[69] Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timo- thée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al. Llama: Open and efficient foundation language models. arXiv preprint arXiv:2302.13977, 2023.
[70] Lucrezia Valeriani, Diego Doimo, Francesca Cuturello, Alessandro Laio, Alessio Ansuini, and Alberto Cazzaniga. The geometry of hidden representations of large transformer models. arXiv preprint arXivv2302.00299, 2023.
[71] Mojtaba Valipour, Mehdi Rezagholizadeh, Ivan Kobyzev, and Ali Ghodsi. DyLoRA: Parameter- efficient tuning of pre-trained models using dynamic search-free low-rank adaptation. In Andreas Vlachos and Isabelle Augenstein, editors, Proceedings of the 17th Conference of the European Chapter of the Association for Computational Linguistics, pages 3274-3287, Dubrovnik, Croatia, May 2023, Association for Computational Linguistics.
[72] Grant Van Horn, Elijah Cole, Sara Beery, Kimberly Wilber, Serge Belongie, and Oisin Mac Aodha. Benchmarking representation learning for natural world image collections. In Proceedings of the IEFF/CVF conference on computer vision and pattern recognition, pages I 12884-12899 2021.
15

---

[73] Ailong Zheng Victor Y. Pan. Superfast algorithms for cauchy-like matrix computations and extensions. Linear Algebra and its Applications. 310(1-3):83-108, 2000.
[74] Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel Bowman. GLUE: A muulti-task benchmark and analysis platform for natural language understanding. In Proceedings of the 2018 EMNLP Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP, pages 353-355, Brussels, Belgium, November 2018. Association for Computational Linguistics.
[75] Qizhou Wang, Sarah M Erfani, Christopher Leckie, and Michael Houle. dimensionality- driven approach for unsupervised out-of out-of-distribue difdrriiibution detection. In Proceedings of the 2021 SIAM International Conference on Data Mining (SDM). pages 118-126. SIAM, 2021.
[76] Yaqing Wang. Sahaj Agarwal, Subhabrata Mukherjee, Xiaodong Liu, Jing Gao. Ahmed Hassan Awadallah, and Jianfeng Gao. AdaMix: -odaattto--aaaptatttinn for parameter-efficient model tuning. In Yoav Goldberg, Zornitsa Kozareva, and Yue Zhang, editors, Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pages 1744-5766 Abu Dhabi, United Arab Emirates, December 2022. Association for Computational Linguistics.
[77] Jason Wei, Yi Tay, Rishi Bommasani, Colin Raffel, Barret Zoph, Sebastian Borgeaud, Dani Yogatama, Maarten Bosma, Denny Zhou, Donald Metzler, et al. Emergent abilities of large language models. Transactions on Machine Learning Research, 2022.
[78] Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, Joe Davison, Sam Shleifer, Patrick von Platen, Clara Ma. Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gugger, Mariama Drame, Quentin Lhoest, and Alexander M. Rush. Transformers: Statc-of-the- art natural language processing. Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations, pages 38 45, Online, October 2020. Association for Computational Linguistics.
[79] Xiao, Hays, K. A. Ehinger, A. Oliva, and A. Torralba. Sun database: Large-scale scene recognition from abbey to zoo. In 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, pages 1485-3492, June 2010.
[80] Lingling Xu, Haoran Xie, Si-Zhao Joe Qin, Xiaohui Tao, and Fu Lee Wang. Parameter-efficient fine-tuning methods for pretrained language models: A critical review and assessment. arXiv preprint arXiv:2312.12145 2023.
[81] Peng Xu, Xiatian Zhu, and David A Clifton. Multimodal learning with transformers: A survey. IEEE Transactions on Pattern Analysis and Machine Intelligence, 15110): 2023.
[82] Z. Xu. Multi-atlas labeling beyond the cranial vault-workshop and challenge. Synapse website, 2016.
[83] Bruce X. B. Yu, Jianlong Chang. Lin Liu, Qi Tian, and Changan Chen. Towards unified view on visual parameter-efficiee transfer learning. ArXiv, abs/2210.007 2022.
[84] Elad Ben Zaken, Yoav Goldberg, and Shauli Ravfogel. Bitfit: Simple parameter-efficient fine-tuning for transformer-bat based masked language-modes models. In Proceedings of the 60th Anmual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pages 1-9, 2022.
[85] Xiaohua Zhai, Joan Puigcerver, Alexander Kolesnikov, Pierre Ruyssen, Carlos Riquelme, Mario Lucic, Josip Djolonga, Andre Susano Pinto, Maxim Neumann, Alexey Dosovitskiy, et al. A large-scale study of representation learning with the visual task adaptation benchmark. arXiv preprint arXiv: 19100.4967,,7 2019.
[86] Kaidong Zhang and Dong Liu. Customized segment anything model for medical image segmentation. arXiv preprint arXiv:2304.1372 13785, 2023.
[87] Meng Zhang, Fei Liu, and Dongpeng Weng. Speeding-up up and compression convolutional neural networks by low-rank decomposition without fine-tuning. J. Real-Time Image Process., 20(4), may 2023,
16

---

[88] Ningyu Zhang, Luoqiu Li, Xiang Chen, Shumin Deng, Zhen Bi, Chuanqi Tan, Fei Huang, and Huajun Chen. Differentiable prompt makes pre-trained language models better few-shot learners. In International Conference on Learning Representations, 2022.
[89] Liang Zhao, Siyu Liao, Yanzhi Wang. Zhe Li, Jian Tang, and Bo Yuan. Theoretical properties for neural networks with weight matrices of low displacement rank. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference Machine Learning, volume 70 Proceedings of Machine Learning Research, pages 4082-4090. PMLR, 06-11 Aug 2017.
[90] Han Zhou, Xingchen Wan, Ivan Vulić, and Anna Korhonen. Autopeft: Automatic configuration search for parameter-effiiien fine-tuning. arXiv preprint arXiv:2301. 12/32, 2023.
[91] Bojia Zi, Xianbiao Qi, Lingzhi Wang, Jianan Wang, Kam-Fai Wong, and Lei Zhang. Delta- lora: Fine-tuning high-rank parameters with the delta of low-rank matrices. arXiv preprint arXin:2309.02411,222 2023.
17

---

A
Implementation Details
In this section, we discuss the details of various algorithms and workflows within SURM.
Contents
A.I Skew-Circulant Matrices
18
A.2 Finding the Smallest Number of Training Parameters for Kronecker Layers
18
A.3 Efficient Matrix Vector Multiplication by Structured Matrices
19
A.4 Increasing Number of Training Parameters
19
A.5 Integration of SURMs in Adapters
20
A.6 Computing Approximations Using LDR Matrices
20
A.7 Additional Details on Approximation Errors by LDR
A.8 Invertible Toeplitz Matrices
A.1
Skew-Circulant Matrices
In this section, we introduce another type structured matrix that characterized by linear number of parameters.
Definition A.1 (Skew-Circule .ircul-Cir,.,,t,.. A matrix S = ($5k) and - -nn-t for S < 1
) j.k=u is said to be skew-circulant if syk = S
n-1
This matrix can be represented visually as shown below:
Un
Up-
V1
00
S
=
(5)
Un-1
Li--1
10
This matrix parameterized by a linear number of parameters and also enjoy sub-quadratic time complexity matrix-vector multiplications (see Appendix A.3).
A.2 Finding the Smallest Number of Training Parameters for Kronecker Layers
Let W be a d matrix that can be written as W A 69 B, where A E R xns, B E R2 We want to minimize the following objective:
mi + m2 subject to m2 Ri d.
(6)
We can rewrite the above as : my d/m2 and nı = d/n2 Plugging these back in Eq. 6, we get:
d²
min1 + m2n2
+ m2n2
12712 d²
+
m222g
2d +
m2n12
d
/m2n2
+ 2d
M2z22
2 2d.
The equality is obtained when M2222 d/ Migflz thereby satisfying the constraint m2l2 min1 d. Essentially this result shows that we can minimize the number of training parameters when the matrices A and B are similarly sized. Furthermore, since both A (and B) have d training parameters, we can maximize the rank of the matrix if we can make it close to square matrix (i.e. we choose factors a, of d, such rank(A A & B) rank( A Jrank(B). (B). Thus, for our experiments with BERT and ViT models, we take A be matrix of size x 24 and B to of size 24 32. This choice of matrix shapes allows us to substantially reduce the computational complexity of matrix-vector multiplication (see Section A.3).
and a is as close
as possible). Note that
18

---

A.3 Efficient Matrix Vector Multiplication by Structured Matrices
One of our main advantages of using structured matrices is that they allow for sub-quadratic vector- matrix multiplications. Matrix vector multiplication by a circulant matrix can be efficiently done via FFT in On log n) time. This is done by the following steps (a) take the FFT of the input vector and the vector representation of the circulant matrix and call them V and C respectively. (b) Take the inverse Fourier transform of the Hadamard (element-wise) product of V and C.
For the sake of convenience, let us define this efficient multiplication operator to be f. The key insight behind this approach is that the circular convolution the time domain corresponds element-wise multiplication in the frequency domain after FFT. By leveraging FFT, the time complexity of the multiplication is reduced from (nn²) On log
The same ideas extend to the case of Toeplitz matrices, where one can embed the Toeplitz matrix into circulant matrix and use FFT before for efficient matrix- vector multiplication. For ease of reference, let us call the function g that embeds the Toeplitz matrix into a circulant matrix and use the function f as described above to compute the matrix-vector product.
Next, we describe how vector multiplication by skew-circulant matrices can be efficiently performed in On log r)) time. If the skew-cireulant matrix S is parameterized by the vector then the multiplication given by
y= -(v(x) = 17 iffi((ft(n) o v) o fft(
(8)
where 77 [1, 1/, r/ ", and 1) (-1)= exp(ix/n)) the root of negative unity.
For the case of matrix W = AB, where W mxxx E Raxr and B Rexx, then multiplication by takes O(r(m + n)) and one gets computation gains when < min(m, n). Finally, for Hadamard product of matrices A E Rrixra, B E xglix&,,v v E Riz4a, (A @ B)v = ver(Br(v) AT), where vec(.) is the vectorization operator that takes a matrix M E lkmxn and converts it to Rmix1 column vector by stacking the columns of M top of each other and r is the PyTorch style reshape operator that reshapes the vector v to a matrix of shape 12 x k2. Choosing max ] r,ki, for 1, 2, one can substantially reduce the computational complexity.
A.4 Increasing Number of Training Parameters
In this section, we explain an elegant way to increase the number of training parameters. We use sum of product of circulant and skew-cireulant matrices of the form
M
A.B. 1=1
where Ar and B; is circulant and skew-circulant matrix respectively. Each factor of M has 2n parameters thus M. has 2nr parameters.
The class of X n matrices M which can be written via Equation 9 is rich and contains many important classes of matrices.
Theorem A.2 (Expressivity).
The of matrices M which can be written in Equation 9 contains:
All n X n Circulant and Skew-Circulan matrices for Z
All n Toeplitz and Inverses of Toeplitz matrices for 2
All n matrices for 71.
All linear combinations of the form D ... A.. where 2 2tp, and A is either
Toeplitz or the inverse of a Toeplitz matrix.
This is Theorem 3.1 in [66]. Efficient multiplication by matrices of this form be done in sub-quadratic time by simply combining the results from See A.3.
Moreover, we note that by choosing slightly different parameterization of displacement operators, one can obtain low rank matrices and orthogonal polynomial transforms, including the Discrete Fourier and Cosine Transforms (see Proposition 2 in [68]).
19

---

Thus our framework encompasses many important classes of matrices including low rank matrices and thus generalizes LoRA.
A.5 Integration of SURMs in Adapters
In this section, we provide additional details about SURMintegration in Adapters.
For simplicity, we follow the Houlsby configuration [25], but our work is also readily applicable in Pfeiffer configuration as well [59]. Recall the definition of Adapter layers:
Y X + o (XB)A,
(10)
where a-) is a non-linear activation function applied point-wise X E Rbxsxn represents input to the layer (b is the batch size and is the sequence length), E Rrxx i B E RRar are two low-rank matrices (r < n) and Y is the output of the layer. Similar to LoRA, matrix B is initialized randomly, whereas is initialized as a zero-matrix. For convenience, layer norms and bias terms are not included the equation.
SURMs can be used in place low rank and B. The integration and design choices of various LDRs in this setting mimic that of LoRA.
Cireulant Matrices. Similar to the LoRA setting, we apply two circulant matrices C1, C2. resulting in the following equation of the adapter block:
Y= + (f(r x)) bb
(1I)
where f is an operator multiplying input matrix X with the circulant matrix obtained by multiplying two circulant matrices encoded by Fj and r2 (Appendix A.3). The vector rj is initialized randomly while r2 and are initialized as zero vectors. Note that we apply the non-linearity after we multiply X with both the circulant matrices. This may hurt the expressiveness of the network but improves computational complexity. Moreover, we only need to save one vector defining the first row of circulant matrix and not both: F1 and r2. This results in lower storage costs and faster deployment. This design choice works well in practice as evidenced from the results on the GLUE benchmark (see Table 5).
two symmetric Toeplitz Matrices. Similar to the of Toeplitz matrices within LoRA, Toeplitz. matrices T1, T2, where T1 and b is initialized as zero vector and T2 is initialized randomly. We then define the adapter layer to be:
+ o ( (T2, X))) + b.
(12)
The position of the non-linear mapping a is chosen such that we can merge the two trained matrices resulting in smaller storage costs and fast deployment.
Finally, note that the Toeplitz variant is slower than the circulant variant, requires two applications of the fast vecrox operator, whereas the circulant variant requires only one.
A.6 Computing Approximations Using LDR Matrices
In this section, we show how we can approximate any matrix E Rexn using Circulant, Toeplitz matrices, and symmetric Toeplitz matrices. We note that each class of structured matrices forms a vector space. Therefore, finding the closest point in the appropriate subspace becomes a convex optimization problem and is given by the orthogonal projection onto the basis vectors of the subspace. More explicitly, if (e1,... ... en) are set of orthogonal vectors spanning a subspace W, then the closest vector to in W is given by
e1 (v. |el 1
(v, en) ||e,l" Cn.
C1 +
(13)
The space of circulant matrices has dim n, so spanned by the orthogonal set {(1,... ((............. 0), (0, ......... .......0000... 0), (O...., ....1)). Using the above formula, can write down simplified expression of the circulant matrix Č = (G)) that approximates D
é = n1
djgs
2 = n
d + Σ d k+1) d Ø=
where k = n2).
20

---

Note that the same set as before spans the space of symmetric Toeplitz matrices. This yields compact formula for the approximating Toeplitz matrix:
n-1 Σ
n Σ - 1=1
T =
Σ 1=1
Ia
M2 +
02,i+2
M3 + ......... + Mn,
n2
1=1
where M; is the symmetric Toeplitz matrix generated by the i-th element in the set above. Finally the ((O,... 1,... 0), (O.... 0)), ((O,.... 0), (0,...
set { {((1,0, 0, (..,,,,..... ,0), (0.... ,0), -(0, spans all Toeplitz. matrices where the first element each tuple denotes the first row and the second element the first column. Note that since the a I entry is shared by both first row and column we
0)
treat the first vector as n-dimeensionll vector and the second as - dimensional vector. Thus the dimension of the space is 2n 1. Using FFT and the projection formula, one can compute the approximation by Toeplitz matrix.
A.7 Additional Details on Approximation Errors by LDR
In this section, we present additional details on the various experiments on approximation by LDR matrices presented in Section 4.1.
Random: The first class, with entries taken independently random from W/ 1), represents completely unstructured family.
Near-low rank: Each matrix from the second class was chosen from the distribution: GH T + eR, where G, H Raxr for r < nI, R Raxx, 0.05, and the entries of G, H, R taken independently at random from (O0 1).
Near-low intrinsic rank: Matrices from the third class are constructed as follows. First we sample:
M(0, 1). The i-th row of the resulting matrix is of the form: (sin(1 . t2), sin(2- to.....to fn-1 lid
sin(n + t()) + gi. wheare either all are zero-vectors or they are taken independently at random from < (0, I.). Note that even though that matrix is not necessarily low-rank, it is taken from the vicinity of the ne-dimensional manifold, since it is fully determined by the sampled tuple (lo:.., 11) Matrices from all the classes are taken from R 1100x100
Optimizing Circulant and Toeplitz Matrices. In general, an optimal approximation (c.g. with respect the Frobenius norm distance) of given matrix by matrix W(G, H) is not given by the closed-form expression. Thus we will thus construct good-quality approximators via gradient- based optimization (see: Sec. 1)..
Details on Approximation Experiments Section 4.2. Now we provide additional details on the experiments that explicitly compare LDRMs with low-rank matrices. For these experiments, construct a PSD matrices M E 500000 with 1 normalized rows. We fix a parameter budget of 50. The low-rank approximation, in that case, becomes outer product by vector v. For the Kronecker product, we choose a factor A E R1005 To maintain the parameter budget, the other factor becomes A If M is the approximating matrix, then we define error || -1- is the Frobenius norm.
M where
We use the closed-fone formula for the optimal circulant and symmetric Toeplitz matrices approx- imating M and use gradient descent to find the optimal low-rank matrix and Kronecker product of matrices. We use a learning rate of 0.1 while computing the optimal low-rank matrix and the Kronecker product of matrices.
A.8 Invertible Toeplitz Matrices
Inverses of Toeplitz matrices can be effectively found [40]. We recall the celebrated result of Gohberg and Semencul.
Theorem A.3. Let A = ((p-a))..=1 be Toeplitz matrix. Ifthe the following systems of equations
7
aI-qIa- = 6p.11
Σ
Op-aWl = 6pmn, where p = (1,2...n)
9=1
is solvable and 2 # 0, then A is invertible.
21

---

10
Groulant
Toep E2
Symmeetic The
10
-12-
-15
-20
750 600
760
1000
1290
1503
1750
2050
Figure 9: Experiment on fitting the pinwheel dataset. Left: Visualization of pinwheel dataset. Right: Results of fitting the pinwheel dataset using regular training, where all network parameters are trained. network with low-rank hidden layer matrix struggles to fit the data, while those with SURMmatrices achieve successful fit.
In our case, we consider only symmetric Toeplitz matrices. Thus the above equation really boils down solving the first system of equations the next system can be solved by using the first, i.c. by setting _ Æn-i41 = yı = 1, 2, The first system of equations can be efficiently solved by Gaussian elimination.
B Experiments
In this section, we describe our experimental setup and present additional analysis experiments to eval- uate the functioning of SURM. Our code is available at https: //gtthbb.tttttt//g//gg com sun/aarijittheamme mauctured-matrccss
Contents
B.1
Hyperparameters
22
B.2
Additional Experiments
24
B.3 Comparison of SURM Kronecker Adaptations with Baselines
25
B.4 Analysis of Weight Matrices Fine-tuned Models
26
B.5 Guidance for Practitioners
27
B.1
Hyperparameters
In this section, we provide the details the hyperparameters used in our experiments. For GLUE the LORA hyperparameters that are used in the original LoRA paper except r = 1 to parameter match our methods as well as a 1.
tasks,
For all the experiments, we use AdamW optimizer [47] with warmup ratio of 0.06, linear learning rate scheduler, and a sequence length of 128. For our methods and Compacter baseline, we use batch size of 64. We report the rest of the hyperparameters in Table 4. The code to run NL.P experiments is developed using Py Torch using Huggingface, Adapter-transffrmmer PEFT libraries, and the original LoRA codebase. For ViT experiments, use JaX [5] and the open-sourced JAX implementation of VIT.
Additional Details on the Pinwheel Experiment. First, we provide figure of the pinwheel dataset used to showease the approximation qualities to LDRMs (see Fig left). We provide additional details on the pinwheel experiment. We tried out 2 settings (a) simple neural network training for 2000 epochs, (b) the embedding (bottom) layer frozen and the rest of the network is trained for 2000 epochs. This can be thought of fitting feature extractor on top of randomized projection. The setting (b) presented in the main paper while setting (a) is presented Appendix B.2. Next, provide additional details for our text and vision experiments.
22

---

Table 4: Hyperparameters used for GLUE experiments
Method
Hyperparameters
RTE
MRPC
QNLI
QQP
SST-2
MNLI
STSB
COLA
Batch Size
32
16
32
16
16
16
16
32
LoRA
Epuchs
80
30
25
25
60
30
40
80
Learning Rate
5e-4
4e-4
4e-4
5e-4
5e-4
5e-4
4e-4
4e-4
Weight Decay
0.0
0.25
0.1
0.1
0.1
le-3
0.25
0.1
Kronecker- LoRA
# Epochs
60
70
60
80
60
80
70
70
Learning Rate
7e-4
2e-3
2e-3
2e-3
2e-3
2e-3
2e-3
2e-3
Dropout
0.1
0.1
0.1
0.1
0.1
0.1
0.15
0.1
Weight Decay
.25
.1
.25
Circulant- LoRA
Epochs
70
80
60
80
Learning Rate
2e-3
2e-3
2e-3
2e-3
2e-3
2e-3
2e-3
2e-3
Dropout
0.15
0.0
0.1
0.1
0.1
0.1
0.1
0.0
Weight Decay
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
Toeplitz-
Epochs
70
80
60
80
70
LoRA
Learning Rate
7e-4
5e-4
7c-4
7e-4
7c-4
7e-4
7e-4
7e-4
Dropout
0.1
0.1
Weight Decay
0.2
0.2
0.2
0.2
0.2
0.2
0.2
0.2
Kronecker-
# Epochs
70
70
80
80
60
80
70
60
Adapter
Learning Rate
2e-3
2e-3
3e-3
3e-3
3e-3
3e-3
3e-3
3e-3
Dropout
0.1
0.1
0.1
0.1
0.1
0.1
0.1
0.1
Weight Decay
le-4
lc-4
le-4
lc-4
le-4
0.2
Circulant- Adapter
Epochs
70
80
60
80
70
Learning Rate
2c-3
2e-3
2c-3
2+-3
2e-3
2e-3
3e-3
2e-3
Dropout
0.1
0.1
0.1
0.1
0.1
0.1
0.1
0.1
Weight Decay
0.2
0.2
0.1
0.1
0.2
0.2
0.2
Toeplitz-
Epochs
70
80
60
70
Adapter
Learning Rate
2e-3
2e-3
3e-3
3e-3
3e-3
3e-3
3e-3
3e-3
Dropout
0.1
0.1
0.1
Epochs
70
70
80
80
60
80
70
60
Compacter
Learning Rate
3e-3
3e-3
3e-3
3e-3
3e-3
3e-3
3e-3
3e-3
NLP Experiments. We train the LoRA-BERT using PEFT library from Huggingface [78]. The hyperparameters used by the original authors used in this setting. For experiments comparing with the LoRA baseline, we parameter match the LoRA updates with our SURMs, thus the LoRA updates given by rank matrices. inject the LoRA modules in query, key, value projection matrices and also show ablations where we remove the adaptation from the key matrix.
For the adapter setting, apply the GeLU non- -oneeiica,, Kronecker-based adapter, though similar to various other methods, was never tested in the BERT-sctting and thus we implement it here, And in all cases, we add an (optional) dropout on the representations coming from these adaptive layers. We train the compacter baseline using the parameters,
library [59]. For the compacter (number of terms in the Tucker decomposition) and the reduction factor to create the low rank matrices to be 16. All our methods have the same number training parameters 2d (excluding bias terms), which gives the reader holistic overview of how these matrices perform when injected into different PEFT paradigms. All the baseline methods use a batch size of 32, whereas our methods batch size of 64. AdamW [47) optimizer is used for all experiments.
Image Classification Experiments. For the image experiments, we use Adam optimizer [33] with 20k max iterations per dataset with batch size of 64. The learning rate used is 5e-5 except for SVHN where we use learning rate of 5c-4. The experiments are run on TPUv4 4 x compute resources.
Large Scale Experiments. In this experiment, we investigate if large ranks are needed for learning new tasks. To circumvent the pre-trained knowledge in the Transformers, following [29], we generate random 10K pairs of Universally Unique Identifiers (UUIDs), each pair comprising two UUIDs with 32 hexadecimal values. The task requires input UUID. We use LLaMA-2 7B as base model [69] for this experiment. For the LoRA setting, we apply rank 256 matrices only the linear layers the attention layer. For MoRA, we use the same setting as in [29]. However, note that in [29], the authors apply adaptation all linear layers.
LLM to generate the corresponding UUID based on the
23

---

Table 5: Performance of SURM and other baselines GLUE benchmark. We report the MCC score CoLA, Fl score for MRPC, Spearman correlation for STSB, and accuracy scores for the other tasks. All results are obtained by averaging over seeds. Best numbers are highlighted in bold and the second best numbers is underline.
# Params (x10%)
RTE
MRPC 3.7k
QNLI 105k
QQP
SST-2 67k
MNLI 393k
STSB
COLA
Method
2.5k
364k
8.5k
BERT baseline [20]
110
66.2
90.5
91.3
91.4
92.6
84.1
88.8
59.5
Adapter (Houlsby) [59]
1.8
69.8
91.5
91.2
90.8
92.8
84.1
89.2
59.1
Adapter (Pfeiffer) [59]
0.9
70.8
89.7
91.3
90.5
92.2
84..
89.0
58.9
AA [53]
0.7
64.25
85.09
89.96
88.09
91.31
82.89
88.25
51.44
BitFit [84]
72.3
90.4
90.2
85.6
92.1
81.4
89.2
58.8
Compacter [5]]
0.11
72.84
90.18
91.08
90.6
92.1
83.26
88.64
59.6
LORA [26]
0.06
71.12
90.43
90.45
90.1
92.66
83.06
88.69
57.83
Prefix [43]
0.19
70.54
89.93
90.76
89.12
91.93
82.78
85.93
58.86
Serial [90]
0.89
68.01
88.65
91.06
90.52
91.93
84.18
84.75
59.73
AdaMix [76]
0.89
70.11
90.91
91.52
90.22
92.06
84,25
86.86
59.11
UniPHLT [52]
1,38
67.07
88.72
91.09
90.69
92.52
84.28
84,22
60.13
Parallel [90]
7.67
68.52
90.72
90.83
90.74
92.13
73.93
86.52
58.72
MAM [23]
7.67
69.10
91.46
90.85
90.76
83.94
83.31
89.01
47.87
AUTOPEFT [90]
1.54
72.35
91.5
91.12
90.64
92.22
84.01
89.17
60.92
SURM (Kroeccer-Adapter)
0.06
72.96
91.11
90.53
89.86
92.66
83.01
88.94
58.77
SURM (Toeplitz-Adapte)
0.06
72.92
91.08
90.47
89.54
92.55
83.04
89.08
59.56
SURM (Crculant-Adapter)
0.06
72.12
91.55
91.24
89.97
93.0
83.45
88.78
59.2
SURM (Kronecke--LoRA)
0.06
71.35
90.08
90.87
90.0
92.78
83.02
88.91
60.35
SURM (Toeplitz-LoRA)
0.06
71.4
90.96
90.56
89.95
92.4
82.54
88.74
58.83
SURM (CirallantLoRA)
0.06
71.84
91.02
90.64
90.15
92.68
82.87
89.18
59.97
For the SURM methods, we follow the same setting applying the adaptation to only the attention layers. The number of factors of W(G. ,, H) is chosen to be 4 (i.e. same number of parameters as a rank 4 matrix). This experiment also highlights that for effective transfer learning LoRA needs to be applied to all linear layers (which is well-known in the LLM community). In Fig. 8, we observe that LoRA and MoRA struggles to fit the data whereas our method converges.
Image Segmentation Experiments. For this experiment, we use Synapse multi-organ segmentation dataset. 30 abdominal CT scans in the MICCAI 2015 Multi-Atlas Abdomen Labeling Challenge are divided into 18 training cases and 12 test cases. There are 3779 axial contrast-enhanced abdominal CT images in total and the training set contains 2212 axial slices. All the CT volumes contain 85 ~ 198 slices and each slice includes 512 x 512 pixels with a spatial resolution of ((0.54 0.54] [0.98 0.98] x [2.5 x 5. 5.0]mm3) ). We use the Begment-Anything. Model (SAM) [34] as the foundation model for this task. There has been number of works in adapting various PEFT methods to fine tuning SAM. We follow the training details in [86]. More specifically, we adapt the Q, V in ViT-B image encoder the SAM and normally finetune the small decoder head. Finally, in this small data regime, we use the Circulant variant it is our most performant variant in this case (see Fig. 6). We report the Dice similarity coefficient (DSC) metric for each the 8 organ segmentation as well as the average DSC score for all (higher is better). The SAMed model uses a LoRA rank 4 in Q, V. For fair comparison, we include LoRA rank 1, matching the exact parameter count of Circulant. We use an A100 40GB GPU for this experiment.
B.2 Additional Experiments
In this section, we provide additional experiments showcase the efficacy of SURMs.
Experiments on Large Scale Data Next, we conduct additional experiments on the ImageNet- dataset [18]. The goal is to show how our methods can scale up to extremely large datasets. We observe that SURM achieves comparable performance to other PEFT methods and even achieving comparable performance the full fine-tuning tne-tuning results (see Table 6).
We further evaluate the performance of SURM in a large-scale setting using the iNat2021 dataset [72], which contains over 2.7 million training images, 100K validation images, and 500K test images, spanning 10, 000 species (classes). Fine-tuning a ViT model on this dataset achieves an accuracy of 69.98%, while SURM (circulant) achieves 69.01 %. Notably, our method requires only 55K
24

---

Table 6: Comparison the performance of SURM and baseline PEFT methods on ImageNet- 1k
SURM (Kronecker)
SURM (Toeplitt)
SURM (Cirullan))
Linear Prob.
VPT Shallow
VPT VPe-Deep
Fine tuning
SSF
0.055
Accurncy
83.14
80.17
82.67
82.04
82.08
82.45
84.1
83.10
95-
blss
tras
bias
55
ciroolant
(b)
(c)
SST2
STSB
no bibs
no blas
95
no blas
bius
b/as
blas
70-
90
85-
eiculant
loegiRz
sirollntt
Ironecter
teepiitz
dirulent
krcnecker
toepliz
(d)
(c)
Figure 10: Figures showing the effect of using bias on various adapters on the GLUE tasks. The red dashed line is the full fine-tuning baseline which is almost 2000x larger than our adapters.
parameters, compared 86M for full fine-tuning, demonstrating its efficiency in parameter usage while maintaining comparable accuracy.
Ablation Experiments. Here, we show the effect of various design choices. Figure 10 illustrates the impact of incorporating the bias term in our adapters. Bias term provides a boost across all tasks and the adapters, the boost being smaller on the Kronecker adapter. Without the bias terms, the sizes of the adapters are around .04M, providing an even lightweight but still capable method. Therefore, if there are concerns regarding storage and latency, opting for adapters without bias is viable option. Moreover, we show the effect on only adapting Q, V instead of Q, K, V as shown in the main paper. Table 7 shows that on GLUE tasks, there minimal effect for not adapting the K matrix.
B.3 Comparison SURM Kronecker Adaptations with Baselines
As mentioned earlier, adaptation using Kronecker product is not new and has been investigated in several works [51, 21, 24]. both [51] and [24], the authors the Kronecker decomposition weight matrix (in the first case, the weight matrix belongs to an adapter layer and in the second case the weight matrix refers updates as in the case of LoRA). Write W > Ai 8 B, Furthermore, the authors assume that B, low rank and can be written as B; == Viy. The weights Ai can also be assumed to low weights or be shared among various layers leading to substantial efficiency gains. Our method is simplified version of the above where n above methods and ours are the matrices considered in the above works are square matrices whereas they are almost never square unless the dimension the transformer up such that the number of parameters are reduced while the rank is as high as possible, contrary to above. Similar considerations of low rank factors in tensor decomposition are also used in [30]. Our Kronecker adaptation is same as that of [21] in the LoRA setting. In the adapter setting, our implementation follows closely the Houlsby architecture and is a little different than that of [21]. Thus, we implement the Kronecker adaptation in both LoRA and adapter settings and showcase its
the
Other main difference between the
perfect square and is set
25

---

Table 7: LoRA ablation experiments GLUE benchmarks. MCC score is reported for CoLA, F1 score is reported for MRPC, and Spearman correlation is reported for STSB. Accuracy scores are reported for the other tasks. All results are obtained by averaging over seeds. The best results are in bold and the second best results are underlined.
Params (x10)
RTE
MRPC
QNLI
QQP
SST-2
MNLI
STSB
COLA
Bert- bert-baseline [20]
110
66.2
90.5
91.3
91.4 4
92.6
84.1
88.8
59.5
LoRA [26]
0.04
70.76
89.02
89.4
89.27
92.2
80.27
88.89
59.08
SURM (Kronecker)
0.04
70.04
89.06
90.54
89.35
91.74
80.41
88.74
59.6
SURM (Toeplitz)
0.04
72.56
91.04
89.65
89.67
92.14
80.93
88.77
58.05
SURM (Circulant)
71.14
90.48
89.91
89.83
92.2
80.6
88.76
59.16
0.23
6.55
Simmllartty
Similantty
Circulant Teeplitz
Circllnt
0.33
Kronecker
0.2
Teeplitz
Kronecker
IORA
IORA
Layer Number
Layer Number
Figure 11: Left: Cosine similarity between the query matrices and Right: cosine similarity between value matrices for the BERT model on MRPC dataset.
versatility across both vision and language. Moreover, we present this approach as an example of principled approach to tackle the problem of PEFT.
B.4 Analysis of Weight Matrices in Fine-tuned Models
In this section, we analyze the weights of various fine-tuned models. Even though prior works have found the updates the weight matrices to have low intrinsic dimension [1] (ID), the updates themselves are of high rank. This is confirmed by looking at the fine-tuned BERT models on various GLUE tasks as well VIT models fine-tuned on CIFAR10, CIFARI00, and ImageNet. Moreover, we simulate a high-rank LoRA setting on GLUE where we freeze all the weights excepts except for Q, K, V. that scenario, we manage replicate the full fine-tuning performance using fewer training epochs than that of LoRA. A quick analysis of the updates reveal that they have full rank.
Many works have delved into intrinsic dimensionality for well-known image classification datasets [60]. These works show that the images have low intrinsic dimensionality compared to the pixel spaces but the dimensionality increases when augmentations like Gaussian noise is added. Recent work [49] studies the intrinsic dimensions of various self-supervised image models. Comparing their results with that of fully supervised ViT models, we observe that the ouffsuuer models exhibit slightly higher IDs. This is not surprising as the SSL encourages the representations be spread over an unit hyper sphere. Thus, we believe that various low rank adaptations may fail in situations where the IDs might be high (in case of OOD data) [75].
Encouraged by this analysis, we investigate the trained weights emerging from our methods. We observe that they have high rank across all vision and text tasks and various fine-tuning strategies. The largest possible rank of the Kronecker matrices considered in this work is 576 and all of trained matrices are of rank 576. For rational circulant matrices C, the non-singularity of such matrices is related divisibility by cyclotomic polynomials. More generally, if we denote by (C- the first column of C, then:
カ-1
det II
(co + ewwy + ozw3 + .... Cn-1w; (1
26

---

Table 8: CKA between full finetuned weights and the SURM weights
LoRA
Circulant
Symmetric Toeplitz
Toeplitz
CKA
0.014
0.1821
0.1343
0.1618
where W/ = e and 1 = -1 (for more details see [14]). This fact allows us to efficiently test for the sinn-luuul of the circulant matrices. all our cases, we found our matrices to be non- singular. Regarding Toeplitz matrices, there is large body of literature that discusses the inversion of such matrices (see Appendix A.8). Using the methods discussed above, we find that the Toeplitz adaptations are invertible, thus full-rank. Therefore, we hypothesize that the high rank compensates for the deficiency of training parameters.
To further explore the differences between the parameters learned by LoRA vs. that learned by SURM methods we performed another set of experiments. We calculate the cosine similarity between the weights learned by the PEFT methods (W- W + a W) and W (pre-trained weights). A smaller cosine similarity would tell us that SURMs help us in exploring parameters further away from the pre-trained weights (W).
We test our hypothesis on the BERT model finetuned on the MRPC dataset by SURMas well as by LoRA. We report the (I-cosine similarity W, W)) for both query and key across multiple layers (see Fig 11). We that LoR weights are very similar to the pretrained weights whereas SURMs explore a larger space (as shown by higher dissimilarity). This observation is not too dissimilar to that of [91].
Analysis of trained weight matrices for Pinwheel data. We also want to answer the question: Q: How similar are the representations learned by networks with the SURM layers compared to the full finetuned networks?
We evaluate the CKA similarity [38] between the full fine-tuned network and the network with the LDR layers, CKA is a widely used metric to compare representations coming from different neural networks. We observe that LDR networks have higher CKA similarity with fully finetuned networks than their LoRA counterparts.
B.5 Guidance for Practitioners
To translate our framework into actionable insights, we aim to highlight several key properties of the various classes of SURMs that help us in making the final recommendation. In all our experiments, we found that on average that circulant variant achieves the largest number of best performances across multiple datasets (Figure 1, Table 2, 3). Moreover, in the low data regime, is clear that the circulant is the most performant variant as well (Figure 6).
The time complexity of LDR matrices is sub-quadratic, in particular, time complexity for both: the circulant and the Toeplitz variant is the same but the Toeplitz one is slower by factor of 2. The gradients allow for very simple formula, which is computed in sub-quadratic time (see eq 14 in [15] for the circulant matrix and Proposition 3.6 in [66] for the Toeplitz matrix). Therefore, our general recommendation to practitioners is to use the circulant variant of SURM. It relatively fast and our most accurate variant.
C Broader Impact & Limitations
Fine-tuning large pre- pre-trained Transformers for downstream tasks requires substantial computational resources. We hope that this work addresses this important problem by reducing the overall compu- tational budget while maintaining high accuracy. We believe that SURMs will make Transformers accessible to researchers and academics world wide and also reduce the carbon footprint associated with training these models. While democratizing powerful Transformers' technologies with those methods, one must still be cautious of the potential harmful biases, inherent to models pre-trained on the internet-scale data. One of the main limitations is the absence of custom kernels for our meth- ods. Despite their theoretical speed advantage, popular methods like LoRA have been extensively optimized by the machine learning community for efficient execution on hardware.
27

---

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

---

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

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We provide access to the code on building the adapter layers using SURM and their integration into pretrained transformers.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (uttps://nips. cc/
onPolicy) for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
//nips. cttpps.cc//pee mablicc/uidess//ee CoodeSubmissionooli oollcc for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts reproduce all experimental results for the proposed method and baselines. If only a subset of experiments are reproducible, they should state which are omitted from the script and why.
submission time, to preserve anonymity, the authors should release anonymized ver- sions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/eetails
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We provide the hyperparameters to replicate the experiments in Appendix B. and B.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Given the sheer volume of experiments along with the baselines that we had to replicate, was too expensive for run these experiments for multiple seeds. However, we report error bars for the smaller toy experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
30

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1 I-sigma error bars, but one should state it. The authors should preferably report 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We provide this information in Appendix B.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: //t////nuuree /nerrps..s..p// cc cccppblic////ecccccccccccccccccl ctwcichhhhcleeeeneceec
Answer: [Yes]
Justification: All authors have reviewed NeurIPS Code of Ethics and the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics
The authors should make sure preserve anonymity (e.g., g., if there is special consideration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
The broader impacts of our work is detailed in Appendix C.
Guidelines:
The answer NA means that there is societal impact of the work performed.
31

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g.. deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release models, providing defenses addition to attacks, mecha- nisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We are not releasing any new data or models.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We have cited the authors who created the original data and algorithms that are used in this work.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from particular source (e.g., website), the copyright and terms of service of that source should be provided.
32

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. www.coo//caaao /atassts has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is available online, the authors encouraged reach out the asset's creators.
13. New Assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We release the main code detailing the creation of the SURM layers leveraging fast matrix-vector multiplication and their integration in pretrained Transformers.
Guidelines:
The answer NA means that the paper does not release new assets. Researchers should communicate the details of the dataset/code/mooel as part of their sub- missions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsoureing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
The paper does not use any crowd sourcing and human subjects. The multi- organ segmentation downloaded from synapse and we adhere to the rules of the usage of this data.
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: We do not IRB approval for the use of the multi-organ segmentation dataset. This can be freely downloaded from the internet once one signs up on synpase. We strictly adhere to the rules of the usage of data.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
33

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
34


Reviews:
[{"review_id": "BMxlXUMmky", "reviewer": "Reviewer_aa5x", "summary": "This paper explores structured unrestricted-rank matrices (SURM) for parameter-efficient fine-tuning (PEFT) of large-scale Transformer models. This method (SURM) was the first to apply low displacement rank matrices (LDRM) which could support fast matrix-vector multiplication and showed flexibility in finding a balance between compactness and expressiveness. What they used were Circulant, Toeplitz (LDRM), also Kronecker matrix (not LDRM). The authors demonstrated improved accuracy in various data sets while replacing low-rank matrices in LoRA and showed a reduction in the number of parameters in the adapter.", "questions": "see the weakness section.", "limitations": "I do not see any serious societal impact of the paper.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Using Circulant and Toeplitz for PEFT seems to be a novel technique and also very effective on many standard benchmarks.\n\n2. Extensive experiments have been provided, which support the authors’ claim.\n\n3. The writing is clear, and comprehensive supplementary material would be very helpful for the readers.", "weaknesses": "1. Any reasons why the proposed version w/ the Kronecker product outperforms the previous works, such as Kadaptation?\n\n2. Why is PSD approximation accuracy a good proxy task? is the weight delta during finetuning close to PSD by any chance?\n\n3. As the author mentioned in the limitation section, there are many fancy accelerated implementations of LoRA. How slow is the proposed method compared to those LoRA implementations?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the Reviewer for their valuable feedback and comments.\n\n> Any reasons why the proposed version w/ the Kronecker product outperforms the previous works, such as Kadaptation?\n\nKadaptation approximates the gradient update using: $\\Delta W = \\sum_{i=1}^n A_i \\bigotimes B_i$ where $B_i$ is the outer product of two vectors (thereby is low rank) and $\\bigotimes$ is the Kronecker product. In our case, we consider $n=1$ and do not require $A_i, B_i$ to be low rank. The uplift in accuracy also showcases the need to move away from low rank constraints on the $\\Delta W$. These differences are more elaborated in Appendix F. \n\n> Why is PSD approximation accuracy a good proxy task? is the weight delta during finetuning close to PSD by any chance?\n\nThe update $\\delta W$ weights are close to full rank and thus we used PSD as a proxy for it. Across multiple applications we find that the $\\delta W$ after finetuning is full rank. We will add details regarding the rank of the update matrix for general finetuning.\n\n> As the author mentioned in the limitation section, there are many fancy accelerated implementations of LoRA. How slow is the proposed method compared to those LoRA implementations?\n\nTheoretically (please see lines 122-130) we are faster with $O(n \\log n)$ whereas LoRa is $O(n d)$. Practically the Circulant variant of SURM is at par with LoRA whereas Toeplitz is slower.", "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": "SLI7EZCbvi", "reviewer": "Reviewer_GJ7U", "summary": "The paper proposed a general framework for parameter-efficient fine-tuning, based on structured unrestricted-rank matrices (SURMs) to substitute LoRA or other parameter-efficient finetuning methods. Three variants of SURMs are included, named Kronecker, Toeplitz, and Circulant, based on the matrix type. The proposed SURM method generally achieves performance comparable with LoRA/adaptors with 50% or less parameters on vision datasets like CIFAR10, SUN397, and DTD. SURM can also be incorporated into adaptors.", "questions": "Please see the weaknesses.", "limitations": "N/A", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The authors introduced a novel approach to substitute LoRA. The proposed SURM method provides us with a novel view of how the matrix of the LoRA can be initialized and interacted with.\n2. Integration experiments with adaptors show the possibility that this method may also be applied in other modules of models, only if they have low intrinsic ranks.", "weaknesses": "1. The tasks include GLUE benchmarks, but the improvements are not convincing. Most of the tasks are in trade-off with other methods. Why not increase the trainable parameter up to the same level as other methods, for example, 0.9, to examine the upper bound performance? This could be part of the ablation studies, showing the scaling relationship between the performance and trainable parameters.\n2. Experiments conducted in NLP should contain new architectures, such as LLaMa.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to sincerely thank the Reviewer for their very valuable feedback and comments.\n\n> NLP experiments:\n\nWe'd like to emphasize the breadth and depth of experimental evidence we have provided for SURMs. First, we compared SURMs on 6 image classification datasets and compared our methods against **12** strong baselines. Furthermore, we have evaluated on the VTAB-1K[80] benchmark. VTAB-1K is designed for low resource settings to evaluate models on “diverse, unseen tasks with few examples”, see abstract from [80]. Across multiple low resource settings we find that circulant works better than all prior proposed methods. This is a key contribution of our work. We further have applied our work on Image segmentation and shown that SURM is comparable with specialized architectures developed for SoTa on image segmentation. Thus our experiments demonstrate the effectiveness of LDRMs especially in the low data regime. The results on GLUE are to showcase that SURMs can be extended to other modalities (text) and different modeling regimes (adapters). We will make this more clear in the manuscript.\n\n\n[80] A large-scale study of representation learning with the visual task adaptation benchmark, Zhai et al. 2020.", "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": "QIwfc3nnMG", "reviewer": "Reviewer_o41Z", "summary": "The paper introduces a new technique called SURMs which aim to use structured matrices for PEFT. The technique is tested against many different adapter variants in Vision Adaptation and Natural Language. The unique structure of the matrices allow for efficient computation of the products", "questions": "What are the ranks of the other adapters used?\n\nWhy do you only test against rank 1 lora in Table 3?\n\nWhat how does the techniques performance change with rank?\n\nWhy might we expect these structures to perform better than other structured matrices?", "limitations": "The paper should address limitations more directly", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The idea of structured matrices compared to low rank ones as avenue of exploration is interesting.\n- Many different adapters are used during evaluation\n- The figures are clear well thought out", "weaknesses": "The bar for a new variant of LoRA to be substantial contribution to me is fairly high, just due to how crowded the space is.\n\nStructured matrices for low rank adaptation has previously, as noted in the paper Knoecker products have been in previous literature, while Circulant and Toeplitz structures are, to my knowledge, have not. Nevertheless, Structured matrix adaptation has been explored in several prior papers.\n\nThe change in structure of the matrix or rank alone to me is not sufficient unless there is substantial evidence it provides benefit, both empirically and intuitively/theoretically.\n\nThe intuition and/or theory as why we might expect this class of matrices to be a useful, in terms of improved adaptation, is lacking (beyond the FFT-based efficiency). As stated previously, the space is fairly crowded for this line of research and every new modification cannot be considered significant without substantial evidence and careful reasoning behind exploration.\n\nThe empirical evidence for this change also needs to be improved upon. \nPEFT experiments need to largely be conducted in regimes where full-finetuning represents a soft upper bound on the achievable performance. The most common use case for PEFT techniques is improving finetuning compute/memory efficiency, while retaining as much performance as possible. In contrast, for regimes where we don't have sufficient data for full fine-tuning to perform best, it seems that we mainly end up measuring the ability of the technique to reduce overfitting, rather than the techniques ability to retain the learning capacity of the original model at lower compute levels. This is still useful, of course, but there are many other techniques to do this outside of PEFT, and it misses evaluation for the primary use case of PEFT.\n\nAs a reference, I think the [MoRa](https://arxiv.org/pdf/2405.12130) paper does a decent job at this. The original LoRA paper doesn't do a great job with this and oversells, as the community knows from countless experiments with it. To effectively prove out which techniques hold up best its very important to conduct detailed evaluations at scale with models which can achieve SoTA on a particular dataset.\n\nThe following would make the paper much stronger:\n- Stronger intuitive/theoretical justification for why we might expect this class of adaptations to perform better (with some small scale experiments or ablations proving the intuition)\n\n- Experiments with models in NLP and Vision, where we full finetuning generally performs best (the UUID memorization from MoRa is a good example). Imagenet seems like a good candidate assuming techniques have not pertained on that data. Larger NLP datasets seem like another good candidate (extra AR pretraining, adaptation to larger downstream tasks).\n\nFrom my perspective, if I actually wanted to train on the the many of the small vision datasets for example, there are many different alternate fine-tuning techniques or different models I can use to improve performance for data-starved cases, especially since those cited perform worse than other fine-tuning techniques on these datasets. (Cifar-100, DTD, SUN for example, even using the same model arches). \n\nThe paper needs to do a more careful job of picking SoTA finetunings on larger datasets and using PEFT on those.\n\n**Only PEFT can really target the case where I have large amount of fine-tuning data, but not necessarily the compute/memory to target it with a very large model well, so this regime should be emphasized in the experiments.**", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to sincerely thank the reviewer for their valuable feedback and comments.\n\n> Structured matrices for low rank adaptation has previously, as noted in the paper Knoecker products have been in previous literature, while Circulant and Toeplitz structures are, to my knowledge, have not. Nevertheless, Structured matrix adaptation has been explored in several prior papers.\n\nTo the best of our knowledge, the entire class of low displacement rank matrices (LDRMs), a subclass of Structured Unrestricted-Rank Matrices (SURMs) have not been explored in the context of PEFT. This includes instantiation of LDRMs including Circulant and Toeplitz matrices. As described in line 131 in section 3, Kronecker is not necessarily an LDRM but admits to efficient matrix-vector multiplication and does fall under the general umbrella of SURMs. The key novelty is our proposal of LDR-SURMs as general approximators that are not restricted to low rank. This is further supported by our experimental results.\n\n\n> Motivation / Intuition / Justification for our proposed LDRMs\n\nAfter intuitively noting the inability of LowRank approximation to capture higher order updates, we have explicitly (empirically) shown in Introduction Figure 1 (right)  that Toeplitz and Circulant matrices do a better job of approximating a PSD matrix as compared to LowRank matrices. *It is well known that finetuning updates are full rank*.  Our motivation is further supported by section 4.1 which clearly shows the higher approximation ability of circulant and Toeplitz matrices. Moreover in section 4.2 we have specifically focused on the approximation quality of low rank matrices vs SURM and clearly show the advantages of LDRMs.\n\nWe believe that we have provided sufficient intuition and motivation (empirically) for the use of LDRMs in particular and SURMs in general.\n\n> Experimental evidence in support of LDRMs\nWe would like to emphasize that we've presented extensive experimental evidence showcasing the efficacy of SURMs. \n\nFirst, we compared SURMs on 6 datasets and compared our methods against **12** strong baselines. There are several analyses in the small data regime. \n\nSecond, we have included results for CLIP models and a comparison on the VTAB-1K [80] benchmark, which is designed to evaluate models on diverse tasks using few examples. \n\nThird, we further have applied our work on Image segmentation and shown that we are comparable with specialized architectures developed for SOTA on image segmentation. \n\nOverall, these sets of experiments demonstrate the utility of LDRMs especially in  the low data regime. \n\n> SoTa baselines for low resource setting/smaller vision datasets.\n\nWe would like to point out that VTAB-1k datasets [80], which is designed to evaluate models in the low-resource regime.  We report the baseline numbers from [29] and [49], which are the current state-of-the-art. Similarly for image segmentation tasks (table 3) SAMed[33] is a dedicated SoTa model trained for image segmentation tasks. These results show that SURM-based finetuning obtains the SOTA performance on several benchmarks.\n\n\n> What are the ranks of the other adapters used?\n\nWe report the adapter baseline performances from their respective papers and their rank is 48.\n\n> Why do you only test against rank 1 lora in Table 3?\n\nSAMed [33] is an adaptation of Lora with higher rank (rank 4, the details are mentioned in Appendix E) \n\n> What how does the technique's performance change with rank?\n\nOur Circulant/Toeplitz matrices are not parameterized by rank. We have explored two ways in which the number of parameters can be increased for circulant matrices. a) $ C = \\sum_i a_i C_i $ where each $C_i$ are circulant and b) $ M = \\prod_i M_i $ where $M_i$ are Toeplitz (line 140.) with a modest boost in performance but at the cost of speed. We will add these details in the supplementary.\n\nInterestingly we found that the circulant and Toeplitz updates to be full rank and that the Kronecker updates to the maximum possible rank (see Appendix A)\n\n\n\n> Why might we expect these structures to perform better than other structured matrices?\n\nWe have motivated the use of structured matrices other than low rank by showcasing how certain structures like PSD are better approximated by LDRs. Moreover, in section 4 we have empirically shown that in multiple scenarios LDRs perform better than low rank matrices. \n\n> results on larger datasets\n\nImageNet results are presented in Table 7 (appendix H). In that case, our method compares favorably to full finetuning where we use only a negligible fraction of training parameters.\n\n[29] Fact: Factor-tuning for lightweight adaptation on vision transformer. Jie et al 2023\n\n[33] Customized Segment Anything Model for Medical Image Segmentation,  Zhang et al 2023.\n\n[49] Towards efficient visual adaption via structural re-parameterization. Luo et al 2023\n\n[80] A large-scale study of representation learning with the visual task adaptation benchmark, Zhai et al. 2020.", "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": "F8hOa5ZrqA", "reviewer": "Reviewer_Kv7A", "summary": "The paper explores the use of structured matrices instead of low-rank matrices for approximating the finetuning updates for Transformer models. The sturcture imposed on the approximation matrices determines the number of trainable parameters. The paper explores use of two structured matrices: Circulant and Toeplitz matrices, and Kronecker product of Matrices for finetuning language models and vision models. The paper shows that structured matrices are better at approximating various class of matrices like random (full rank), near-low-rank and near-low-intrinsic-rank than low-rank matrices, and this translates to better performance when using them for finetuning at a lower parameter cost.", "questions": "1. **Section 4.1**:\n- What is the significance of Section 4.1? What does the comparison between Circulant and Toeplitz matrices with W(G,H) convey? Could the authors provide more explanation about why this comparison is done, especially since the final PEFT algorithm uses only Circulant and Toeplitz matrices?\n- Do all the methods in this study approximate the exact same matrix? Why do the initial errors vary by such a large margin across W(G,H), and Circular and Toeplits matrices?\n- Why do Circulant and Toeplitz matrices use more iterations than W(G,H) (200 vs. 2000)? If the number of iterations is the same (i.e., W(G,H) is optimized for 2000 iterations), do the results change?\n- Why is there no study for approximation of random matrix using Toeplitz Circular matrices?\n- Why is low-rank(I=20) + epsilon not considered for Circular and Toeplitz matrices?\n\n2. **Experiments on image classification using ViTs**:\n- What is the pretraining data and task for the base ViT?\n- How is the data split into train, validation and test splits, and on which split is are the results reported?\n- How and on which split are the hyperparameters tuned? Section E, lines 699-700 mention that the experiments use a learning rate of 5e-5, but SVHN uses 5e-4. How is this chosen?\n\n3. **Experiments on GLUE**:\n- What is the difference bewteen SURM (Circular) and SURM (Circular-LoRA/Adapter) (similarly Toeplitz and Kronecker)?", "limitations": "Authors have addressed the limitations.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "- Use of structured matrices for finetuning achieves on-par/better performance than prior works at a lower parameter cost.\n- The toy experiments show that structured matrices can approximate matrices better than low-rank matrices (controlling for the number of parameters). The authors verifiy this through two experiments:\n    - Approximating Symmetric Positive Definite Matrices\n    - Fitting a toy dataset (pinwheel with Gaussian noise) using a neural net with layers composed of structured and low rank matrices.", "weaknesses": "1. **No studies on more difficult tasks**:\n- While I understand that the authors have shown the effectiveness of the proposed method on smaller models, it would be interesting to see how the proposed method performs on larger models for more difficult tasks like language generation (for e.g., insturction tuning) or math/commonsense reasoning which are commonly used to study PEFT methods on large language models.\n2. **Lack of details on choice of hyperparameters**:\n- The paper does not provide sufficient details about how the data is split, if all the methods are compared by training and evaluating on the same data splits.\n- Moreover, the paper does not provide details on how the hyperparameters are chosen, but only the final values are mentioned. (Section E in the appendix.)\n3. **Minor presentation details**:\n- Figure 1: caption says the presented methods are in top left (in green), but appear to be in the top right in the plots, and also do not apprear to be in green.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to sincerely thank the Reviewer for their very valuable feedback and comments.\n\n> Studies on larger tasks:\n\nOne of the key things that we showed in our experiments was the improved performance in the low data regime. Specifically across a plethora of low-resource image experiments (VTAB-1K) we have shown the improved performance of SURMs (circulant). The NLP experiment on Glue was provided to showcase the ability of SURMs to extend to other modalities (text) and another class of small parameter models (adapters). We will make it more clear in the paper. \n\n> Choice of hyperparameters:\n\nDatasplit: For vit-image experiments (table 1) we used the standard dataset split in tensorflow tfds datasets (https://www.tensorflow.org/datasets). VTAB-1K provides its own split and code which we used (github). For image segmentation we used the same split as the Segment-Anything-Model (SAM) [33]. For Glue we used the standard train/dev split (https://gluebenchmark.com/). \n\n> How the hyperparameters are chosen\n\nAll hyperparameters are tuned on training/val set and numbers are reported on separate test set. We will update the manuscript with this information.\n\nThanks for pointing out the typo in the caption of Figure 1. We will fix them.\n\n\n> Significance of Section 4.1: motivation, comparisons and conclusion\n\nWe apologize for the confusion. Our motivations for the two separate parts (left and right column of figure 4) are different. To save space we put these two experimental results together. Our motivation for the left column is to showcase the ability of general LDRs (defined in eq 2) to approximate various matrices i.e. random, low rank and low intrinsic rank and motivate our choice of LDRs with r=1. From the bottom two figures on the left (i.e. approximating low rank and low intrinsic rank with LDRs) we learn that LDRs (with r=1 and r=2) are great at reducing the approximation error (They are in the top 3 best approximating errors (lowest error)). This further provides motivation and empirical justification that LDRs with (r=1) may be well suited to approximate matrices with some structure.\n\nThe motivation for the right column is to compare and contrast the two variants of LDRs that we proposed i.e. circulant and Toeplitz. \n\nHence we should not be comparing the right with the left column. Please see the left and the right as its own set of experiments. In each figure, all techniques approximate the same matrix. The first set of results shown are after a single iteration hence the difference within the same figure. We can provide the left column experiments with a higher number of iterations but the objective is to discriminate among all the LDRs. \n\n\n\n> What is the pretraining data and task for the base ViT?\n\nWe used the vit-base model and the clip-base model from HuggingFace (https://huggingface.co/google/vit-base-patch16-224)\n\n> How is the data split into train, validation and test splits, and on which split are the results reported?\n\nFor vit-image experiments (table 1) we used the standard dataset split in tensorflow tfds datasets (https://www.tensorflow.org/datasets). VTAB-1K provides its own train/dev/test split and code for the same, which we used (github). For image segmentation, we used the same split as the Segment-Anything-Model (SAM) [33]. For Glue we used the standard train/dev split (https://gluebenchmark.com/). All numbers are reported on the test set (no hyperparameters were trained on. Thanks for pointing this out, we will update it in the manuscript \n\n> How and on which split are the hyperparameters tuned? Section E, lines 699-700 mention that the experiments use a learning rate of 5e-5, but SVHN uses 5e-4. How is this chosen?\n\nFor image classification experiments we used the same setup for all datasets except for SVHN where the training accuracy didn’t move much when using 5e-5 as the learning rate. All hyperparameters have been turned on the training/dev set while reported results are on the test set.\n\n\n\n> What is the difference between SURM (Circular) and SURM (Circular-LoRA/Adapter) (similarly Toeplitz and Kronecker) used in GLUE?\n\nIn the interest of saving space our detailed discussion regarding how SURMs can be used as Adapters has been moved to Appendix C. The difference between SURM(*-LoRA) and SURM(*-Adapters) is the setting under which low displacement rank matrices can be used. For example, circular-LoRa refers to using circulant matrices for lora style update ie $\\hat{W} = W + \\alpha \\Delta W$ where $\\Delta W$ is circulant (please see 5.1 for Lora style PEFT method). circular-Adapter implies using the adapter method for updating the model (please see equation 7 in section C in the Appendix). Our objective was to elaborate that both these styles of training can benefit from SURMs. \n\n[33] Customized Segment Anything Model for Medical Image Segmentation,  Zhang et al 2023.\n\n[80] A large-scale study of representation learning with the visual task adaptation benchmark, Zhai et al. 2020.", "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:

Meta-review: The paper proposes a general framework for parameter-efficient fine-tuning, based on structured unrestricted-rank matrices (SURMs) to substitute LoRA or other parameter-efficient finetuning methods. 

Three variants of SURMs are included, named Kronecker, Toeplitz, and Circulant, based on the matrix type. The use of Circulant and Toeplitz structures in adaptors is novel.

The extensive experiments show that the SURM method generally achieves performance comparable with LoRA/adaptors with 50% or less parameters on vision datasets like CIFAR10, SUN397, and DTD. SURM can also be incorporated into adaptors.

The rebuttal includes results on larger LLM models such as LLaMa-2 7B, where existing methods such as LoRA struggle, while SURM does better, by allowing higher ranks without higher computational load.

The bibliography is poorly constructed and needs to be fixed. Many of the entries are missing information, such as journal or conference name, or even arxiv numbers.

The authors will have a challenge to fit in all the new material (e.g. the results on the LLaMa experiments) into the final version if accepted.

The low-rank adaptors and approximations space is becoming very crowded and hard for new methods to stand out as significant contributions. This is the case for this paper. While the contribution is clear, and makes a good addition to the current PEFT methods, it might not stand out as particularly exciting in comparison with other accepted papers. Hence it is suited more for a poster or spotlight than an oral talk.
Decision: Accept (poster)