# Structured Unrestricted-Rank Matrices for
Parameter Efficient Fine-tuning

Arijit Sehanobish$1$*, Avinava Dubey$2$*, Krzysztof Choromanski$3,4$*,
Somnath Basu Roy Chowdhury$5$, Deepali Jain$3$, Vikas Sindhwani$3$, Snigdha
Chaturvedi$5$
$1$Independent, $2$ Google Research, $3$Google DeepMind, $4$Columbia
University, $5$UNC Chapel Hill

###### Abstract

Recent efforts to scale Transformer models have demonstrated rapid progress
across a wide range of tasks [74]. However, fine-tuning these models for
downstream tasks is expensive due to their large parameter counts. Parameter-
efficient fine-tuning (PEFT) approaches have emerged as a viable alternative
by 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 provides 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
$\mathbf{5}$-$\mathbf{7}\%$ accuracy gains on various image classification
tasks while replacing low-rank matrices in LoRA. It also results in up to
$\mathbf{12x}$ reduction of the number of parameters in adapters (with
virtually no loss in quality) on the GLUE benchmark.

**footnotetext: Equal Contribution

##  1 Introduction

In recent years, large-scale Transformer models have demonstrated impressive
performance across a wide range of domains, including natural language
processing (NLP) [20, 8], vision [35], robotics [7], and even multi-modal
settings [78]. For many applications, a single large pre-trained model is
adapted for several downstream problems. Fine-tuning, where all the model
parameters are updated, is a popular way to adapt a pre-trained model to a new
task or domain. However, fine-tuning large models on specific downstream tasks
requires significant computational resources and involves a massive memory
footprint, as each task necessitates storing its own set of parameters.

Figure 1: Left: Approximating a PSD matrix using a low rank matrix, Kronecker
product of matrices, circulant matrix, and Toeplitz matrix. We repeat our
experiment $\mathbf{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 5 image datasets using Clip-
ViT. Our methods appear in the top right corner (in blue) and achieve the best
performance among various strong baseline methods.

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 on par with full fine-tuning while
training only a small number of parameters [77, 44]. PEFT techniques involve
either training a small subset of the model’s parameters [80, 41] or
integrating small modular layers while freezing the base model’s weights [26,
25]. There are two popular classes of methods to inject additional parameters:
(a) using small modular layers inside Transformers called adapter layers [57],
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
models [1, 68]. These low-rank methods primarily aim to approximate updates,
which, in general, are 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 are
characterized by a linear number of parameters while exhibiting impressive
approximations across various matrix classes. We present Fig. 1 as a preview
of the motivating results. In Fig. 1 (left), we show that structured matrices
(SURM) can approximate any random matrix better than low rank matrices. In
Fig. 1 (right), we show that when SURMs are used for parameter efficient fine-
tuning it outperforms existing PEFT methods (see more details in Sec. 4).

We propose a novel paradigm of parameter efficient fine-tuning that leverages
Structured Unrestricted-Rank matrices (or SURMs). SURMs provide efficiency
gains obtained in prior works, but their less rigid structure is a gateway to
quality improvements. We focus on the two sub-classes of SURMs: (1) Kronecker
product of matrices [3] and (2) low displacement rank matrices (LDRMs) [64, 6,
56, 53, 70]. In this work, we extensively test the two following classes of
LDRMs : circulant and Toeplitz matrices (see: Sec. 3). Our proposal is to
perform PEFT by introducing additional weights parameterized as structured
matrices. To summarize, our primary contributions are:

  1. 1.

We demonstrate strong matrix approximation capabilities inherent in Low
Displacement Rank Matrices, with a specific focus on circulant and Toeplitz
matrices (Fig. 1 left, Fig. 4 and Sec. 4).

  2. 2.

We propose the class of Structured Unrestricted-Rank matrices (SURMs) (Sec.
3), for parameter efficient fine-tuning of Transformers. SURMs include low-
rank matrices used in LoRA, as special cases. To the best of our knowledge, we
are the first to apply LDRMs in this context.

  3. 3.

We achieve $\mathbf{5}$-$\mathbf{7}$% accuracy gains over LoRA on a wide
variety of image datasets as well as in low resource setting (VTAB-1k
benchmark). In some cases SURMs outperform full fine-tuning, while using only
$\mathbf{55}$k training parameters (Fig. 1, right).

  4. 4.

We introduce a new class of adapter-layers using SURMs, achieving a
$\mathbf{12x}$ reduction in parameters compared to adapters, with virtually no
loss in quality on the GLUE benchmark (Sec. 6).

##  2 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 [62] with up to 20B parameters [65], and a range of
auto-regressive decoder models like Llama [67], Pythia [4], Mistral [28],
among others, varying in size from a few million to 180B parameters [2]. These
models have demonstrated general capabilities and can be easily adapted to
downstream tasks by fine-tuning on task-specific data, resulting in state-of-
the-art performance across a 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 ways 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 [47].

Consequently, many works have proposed various PEFT techniques. One of the
earliest methods involves inserting the so-called adapter layers between
existing layers in a neural network [25, 57]. A standard implementation of an
adapter is an MLP with input-, output- and a smaller middle-layer, effectively
encoded by two lower-rank matrices, and thus with a compact set of parameters.
An extension of the adapter is Compacter [50], 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 [52, 24, 31, 51, 63]. Another popular PEFT
technique is differentiable prompt-tuning (DPT), which can be thought of as
optimizing special tokens in the prompt [84]. 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 [79, 12, 27, 24].

One of the most popular PEFT methods is Low Rank Adaptation [26], which
imposes a low-rank constraint on the weight updates. The primary difference
between the two approaches is that the learned LoRA weights can be merged with
the frozen model weights during inference, thus not introducing any additional
latency. This is not the case for the adapters. Given the popularity of LoRA,
there has been a plethora of works on extending it to different contexts like
long-range modeling [13], multi-tasking [10] or further improving its
efficiency [19, 69, 45, 36, 30] among many others.

Low-rank matrices are studied extensively within various ML problems [55, 83,
43, 59]. The research on low displacement rank matrices (LDRMs) for ML is more
narrow [85, 66, 40, 64, 15, 34, 60]. The application of Kronecker matrices in
the context of PEFT is not new and has already been investigated in previous
works [21, 24, 50], but in all the above cases the constituent matrices in the
Kronecker product have low rank. In this work, we impose no such condition,
while keeping a fixed parameter budget. To the best of our knowledge, we are
the first to systematically explore the effectiveness of different structured
matrices and introduce LDRMs for PEFT, extending beyond previous works.

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 (Sec
3), (b) We motivate the usage of SURM by empirically showing the approximation
qualities of these matrices (Sec 4), (c) We use SURM as drop-in replacement
for popular approaches such as Adapters and LoRA (Sec 5), (d) We validate our
approach across a wide range of vision and NLP tasks (Sec 6).

##  3 Structured Unrestricted-Rank Matrices

In this section, we will define the matrices that are used in this work. A
Structured matrix is a generic term for a matrix
$\mathbf{A}\in\mathbb{R}^{m\times n}$ that can be represented by fewer than
$mn$ parameters. This implies space (and often also time) complexity savings.

A trivial example is a matrix of the form
$\mathbf{W}=\mathbf{A}\mathbf{B}^{\top}\in\mathbb{R}^{m\times n}$ for
$\mathbf{A}\in\mathbb{R}^{m\times r}$, $\mathbf{B}\in\mathbb{R}^{n\times r}$
with $r\ll\min(m,n)$. However, our main focus in this work 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).

Low Displacement Rank Matrices : Our first class of SURMs is low displacement
rank matrices (LDRMs). A matrix $\mathbf{W}\in\mathbb{C}^{m\times n}$ is said
to have $(\mathbf{A},\mathbf{B})$-displacement structure if:

$\nabla_{\mathbf{A},\mathbf{B}}(\mathbf{W})\overset{\mathrm{def}}{=}\mathbf{AW}-\mathbf{WB}=\mathbf{F},$
(1)

where $\mathbf{A}\in\mathbb{C}^{m\times m},\mathbf{B}\in\mathbb{C}^{n\times
n},\mathbf{F}\in\mathbb{C}^{m\times n}$ and $\mathbf{F}$ has low rank $r$ (as
compared to $\min(m,n)$). We call $\nabla_{\mathbf{A},\mathbf{B}}$ the
displacement rank operator, parameterized by $\mathbf{A}$ and $\mathbf{B}$.

There exist several pairs of $(\mathbf{A},\mathbf{B})$ matrices $\mathbf{W}$
satisfying Eq. 1 with low-rank $\mathbf{F}$ that support fast (sub-quadratic)
matrix-vector multiplication (as well as more efficient performance of other
matrix-operations such as taking inversions, etc.). Some examples of such
pairs include:
$(\mathbf{Z},\mathbf{Z}),(\mathbf{Z},\mathbf{Z}^{\top}),(\mathbf{D}_{x},\mathbf{Z}^{\top}),(\mathbf{D}_{x},\mathbf{D}_{y})$
(for $x\neq y$). Here $\mathbf{Z}$ stands for the circulant-shift matrix and
$\mathbf{D}_{z}$ is a diagonal matrix with nonzero entries equal to $z$. By
choosing more complicated $(\mathbf{A},\mathbf{B})$-pairs, e.g. using general
Jordan form matrices, one can consider more unstructured $\mathbf{W}$, yet
still possessing compact representations and supporting efficient matrix
operations [54, 64]. In this paper, we focus on classic LDRMs: circulant and
toeplitz matrices described below.

  1. 1.

Circulant Matrices : A circulant matrix $\mathbf{C}\in\mathbb{C}^{m\times n}$
can be parameterized by its first row, with next row obtained from the
previous one by the right circulant shift. A schematic visualization is
provided in Fig 2 (a). Circulant matrices can be trivially encoded in $O(n)$
space and support fast $O((n+m)\log(n+m))$ matrix-vector multiplication via
Fast Fourier Transform (FFT).

  2. 2.

Toeplitz Matrices : A Toeplitz matrix $\mathbf{T}\in\mathbb{C}^{m\times n}$,
shown in Fig 2 (b), are constant along each diagonal. They can be
parameterized using only their first row and column and can be encoded in
$O(n+m)$ space. Like circulant matrices, they support fast $O((n+m)\log(n+m))$
matrix-vector multiplication via FFT.

Figure 2: A Schematic Diagram of Circulant, Toeplitz and Kronecker product of
2 matrices. Figure 3: A circulant matrix with the first column given by a
vector $(c_{0},c_{1},c_{2},c_{3},c_{4})$ can be re-written as a linear
combination of the orthogonal base circulant matrices (5 matrices with orange-
entries corresponding to one and other to zero). Such a closed-form
decomposition is in general not possible for matrices
$\mathbf{W}(\mathbf{G},\mathbf{H})$ and thus optimal approximators are found
by gradient-descent.

Kronecker Product of Matrices. These matrices are not necessarily LDRMs, but
they also enjoy low storage complexity and admit efficient matrix-vector
multiplication. A schematic diagram showing the Kronecker product of two
matrices is provided in Fig 2 (c). In our experiments, we apply Kronecker
product of two matrices. We provide more details about these matrices in
Appendix A.2.

##  4 LDR-SURMs as General Approximators

In this section, we motivate the usage of structured unrestricted-rank
matrices (SURMs) for parameter efficient fine-tuning by showcasing their role
as approximators of various classes of matrices. Without loss of generality,
we assume that all our matrices have real entries and $n=m$ ( square
matrices). We denote the rank of $\mathbf{F}$ from Eq. 1 as $r$.

It is shown in [64] that a large class of LDRMs, including (a) circulant,
Toeplitz and inverse-Toeplitz matrices as well as: (b) linear combinations of
the products of the form: $\mathbf{M}_{1}\cdot...\cdot\mathbf{M}_{t}$ for
$r\geq 2t$ and where each $\mathbf{M}_{i}$ is a Toeplitz matrix or its
inverse, can be parameterized as follows for
$\mathbf{g}_{1},...,\mathbf{g}_{r},\mathbf{h}_{1},...,\mathbf{h}_{r}\in\mathbb{R}^{n}$:

$\mathbf{W}(\mathbf{G},\mathbf{H})=\sum_{i=1}^{r}\mathbf{Z}_{1}(\mathbf{g}_{i})\mathbf{Z}_{-1}(\mathbf{h}_{i}).$
(2)

Here: $\mathbf{Z}_{f}(\mathbf{v})$, for $f\in\mathbb{R}$ and
$v\in\mathbb{R}^{n}$, is defined as:

$\scriptstyle{{\displaystyle\mathbf{Z}_{f}(\mathbf{v})={\begin{bmatrix}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}v_{0}}&{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}fv_{n-1}}&\cdots&{\color[rgb]{.75,.5,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,.5,.25}fv_{1}}\\\
{\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}v_{1}}&{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}v_{0}}&\cdots&{\color[rgb]{0,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,1}\pgfsys@color@cmyk@stroke{1}{0}{0}{0}\pgfsys@color@cmyk@fill{1}{0}{0}{0}fv_{2}}\\\
\vdots&\vdots&\vdots&{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}fv_{n-1}}\\\
{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}v_{n-1}}&\cdots&{\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}v_{1}}&{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}v_{0}}\\\
\end{bmatrix}}}}$ (3)

Besides, $\mathbf{F}$ can be decomposed as follows:
$\mathbf{F}=\mathbf{G}\mathbf{H}^{\top}$ for
$\mathbf{G}=[\mathbf{g}_{1},...,\mathbf{g}_{r}],\mathbf{H}=[\mathbf{h}_{1},...,\mathbf{h}_{r}]\in\mathbb{R}^{n\times
r}$. One can think about rank $r$ of $\mathbf{F}$ of controlling how
“structured” $\mathbf{W}$ is.

We conduct the approximation in two settings: (a) comparing the approximation
qualities of $\mathbf{W}(\mathbf{G},\mathbf{H})$ with circulant and Toeplitz
matrices, and (b) comparing circulant and Toeplitz matrices with low-rank
matrices.

###  4.1 $\mathbf{W}(\mathbf{G},\mathbf{H})$ versus circulant and Toeplitz
matrices

We test the approximation capabilities of matrices
$\mathbf{W}(\mathbf{G},\mathbf{H})$ from Eq. 2 as well as circulant and
Toeplitz matrices to approximate three classes of matrices: (a) random, (b)
near-low-rank, and (c) near-low-intrinsic-rank. Matrices $\mathbf{M}$ from all
the classes are taken from $\mathbb{R}^{100\times 100}$. Detailed description
of these matrices are presented in Appendix A.5.

The approximating structured matrix is obtained via gradient descent on the
loss function $\|\mathbf{A}-\mathbf{M}\|_{\mathrm{F}}^{2}$, where $\mathbf{A}$
and $\mathbf{M}$ are: the approximating and ground truth matrix and
$\|\cdot\|_{\mathrm{F}}$ is the Frobenius norm. However, for circulant and
Toeplitz matrices closed-form formula for the optimal approximating matrix is
available (see Fig 3 and Appendix A.4).

$\mathbf{W}(\mathbf{G},\mathbf{H})$ with different $r$ is used to approximate
random matrices (Fig 5 (Top Left)). While the best approximations are achieved
for larger values of $r$ (specifically, $r=20$), it’s interesting to note that
the final accuracy does not exhibit a monotonic increase with $r$.
Consequently, for the second class of matrices, which are easier to
approximate and are close to low-rank, we experiment with smaller values of
$r$ (Fig 5 (Left Column Middle and Bottom)). In this case, the three top-
performing approximators were trained with $r=2$, $r=1$, and $r=4$. These
results clearly show that for more structured ground truth matrices (even
though not necessarily low-rank !), LDRMs with very low rank of the
corresponding $\mathbf{F}$ are sufficient.

For that reason, we focus our attention on circulant and Toeplitz matrices. In
the next three plots in Fig. 5 (Right Column), we compare their approximation
capabilities for near-to-low-rank matrices as well as low-intrinsic-rank
matrices. We conclude that the gains coming from Toeplitz matrices (that use
two times as many parameters as circulant matrices) are negligible and present
only in the near-low-rank case. For the low-intrinsic case, circulant matrices
outperform Toeplitz ones.

###  4.2 Low-rank versus Circulant and Toeplitz matrices

Figure 4: Fitting the pinwheel dataset with a frozen embedding layer using
various SURM-based PEFT methods and LoRA.

In this section, we focus on the difference in approximation qualities between
low rank matrices and the circulant and Toeplitz matrices by using a fixed
parameter budget. We use the following two settings:

Approximating Symmetric Positive Definite Matrices.
$\mathbf{M}\in\mathbb{R}^{n\times n}$ ($n=50$) with $L^{2}$-normalized rows is
used for this experiment. We compare the errors to approximate $\mathbf{M}$
using circulant, (symmetric) Toeplitz, low-rank matrices, and Kronecker
product of $2$ matrices. A fixed parameter budget of $n=50$ is chosen and this
experiment is repeated $10$ times. Our results are presented in Fig. 1, Left.
For each of these $10$ trials, we observe that the low rank matrix has the
highest approximation error followed by the Kronecker product of two matrices,
the circulant, and the Toeplitz matrices (see more details in Appendix A.5).

Figure 5: The approximation capabilities of different LDRMs. The $y$-axis
depicts the relative Frobenius norm error
${\|\mathbf{A}-\mathbf{M}\|_{\mathrm{F}}}{/\|\mathbf{M}\|_{\mathrm{F}}}$
between the groundtruth matrix $\mathbf{M}\in\mathbb{R}^{100\times 100}$ and
the approximator $\mathbf{A}$. Left Column Top: Approximating random Gaussian
matrix $\mathbf{M}$ with matrices $\mathbf{W}(\mathbf{G},\mathbf{H})$ with
different $r$ (LDR: $r$). Left Column Middle: Approximating near-low-rank
matrices $\mathbf{M}$ replacing random Gaussian matrices and smaller values of
$r$. Left Column bottom: Similar setup to approximate near-low-intrinsic-rank
matrices $\mathbf{M}$. Right Column: We perform analogous studies with
circulant and Toeplitz matrices, where the ground truth has low rank or low-
intrinsic rank.

Fitting a simple toy dataset : We create a pinwheel dataset with 5 spokes
(adding a little Gaussian noise) (Fig : 8 Left). Then we try to fit a simple
neural network with one hidden layer with the matrix of size $64\times 64$. We
then replace this matrix with a rank $1$ LoRA layer, a circulant layer, a
symmetric Toeplitz and a Toeplitz layer making sure that all of these models
have the same number of training parameters. We observe that the LoRA layer
struggles to fit the data whereas the low displacement rank matrices show
similar performance to that of the baseline (Fig 4). These results show the
impressive expressive power of these matrices. Additional details are
presented in Appendix B and additional experiments are presented in the
Appendix B.2 (see Fig 8).

We thus conclude that LDRMs with particularly low displacement rank serve as
good approximators for various matrices. This power translates well to various
downstream tasks as will be confirmed by our experimental results, with
circulant matrices performing especially well (see: Sec. 6).

##  5 Integration of SURMs with PEFT

Motivated by the results of the previous section, we are now ready to use
SURMs as drop-in replacements for various PEFT methods. In this section, we
discuss the integration of SURMs in LoRA and relegate the discussion about
SURMs in Adapters to the Appendix. A.3. Our design choices take into account
the trade-off between expressivity and training efficiency.

###  5.1 Transforming LoRA with SURMs

LoRA [26] proposes an adaptation of the weight matrix via low rank updates.
More concretely, if $\mathbf{W}$ is the pretrained weight, then the updated
$\widehat{\mathbf{W}}=\mathbf{W}+\alpha\Delta\mathbf{W}$, where
$\Delta\mathbf{W}=\mathbf{AB}^{\top}$ and $\mathbf{A}\in\mathbb{R}^{m\times
r},\mathbf{B}\in\mathbb{R}^{n\times r}$ for $r\ll\text{min}(m,n)$ and $\alpha$
is a fixed scaling parameter. For efficient training, $\Delta\mathbf{W}$ needs
to be initialized as a zero-matrix. Importantly, in LoRA it is done by
choosing $\mathbf{B}$ to be a random matrix and initializing $\mathbf{A}$ to
be the zero matrix. In this work, we propose learnable SURMs as
$\mathbf{AB}$-replacements for $\Delta\mathbf{W}$. For simplicity of notation,
we will assume $m=n$.

Circulant Matrices : Let $\mathbf{C}\in\mathbb{R}^{n\times n}$ be a circulant
matrix which we parameterize by an $n$-dimensional vector $\mathbf{r}$
encoding its first row. Instead of assigning: $\Delta\mathbf{W}=\mathbf{C}$,
we instead take: $\Delta\mathbf{W}=\mathbf{C}_{1}\odot\mathbf{C}_{2}$ with the
corresponding vectors $\mathbf{r}_{1}\odot\mathbf{r}_{2}$, where $\odot$ is
the Hadamard product (element-wise multiplication). Following the strategy
applied in LoRA, we initialize $\mathbf{C}_{1}$ as a zero-vector and
$\mathbf{C}_{2}$ as a random-vector. Opting for Hadamard products over
conventional matrix products is primarily driven by the advantage of utilizing
efficient multiplication only once. The construction of Hadamard products
which is O($n$) is quicker than the process involved in efficient
multiplication (which is O$(n\text{log}(n))$. Additionally, this approach does
not compromise the expressiveness of the network. In both scenarios, the
result is a circulant matrix, as the product of two circulant matrices yields
another circulant matrix.

Toeplitz Matrices : Let $\mathbf{T}\in\mathbb{R}^{n\times n}$ be a Toeplitz
matrix which we parameterize by an $n$-dimensional vector $\mathbf{r}$
encoding its first row and an $n$-dimensional vector $\mathbf{c}$ encoding its
first column (thus in total $2n-1$ parameters). To address the initialization
challenge, we apply two Toeplitz matrices where one is initialized randomly
while the other is the zero matrix (same strategy as before).

Table 1: 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 | ViT-B | CLIP
---|---|---|---
$\left(\times 10^{6}\right)$ | CIF-10 | CIF-100 | SUN397 | DTD | STL10 | CIF-10 | CIF-100 | SUN397 | 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
Attn. 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 | 98.8
Adapter | 1.505 | 98.4 | 90.6 | 74.2 | 71.0 | 99.3 | 94.7 | 81.4 | 77.1 | 78.0 | 99.0
AdapterDrop | 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 | 96.2 | 88.3 | 72.0 | 65.5 | 99.0 | 92.5 | 77.1 | 60.0 | 77.7 | 88.6
LN 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 (Toeplitz) | 0.055 | 98.5 | 90.2 | 79.1 | 75.6 | 99.7 | 97.1 | 84.5 | 80.9 | 77.9 | 99.0
SURM (Circulant) | 0.055 | 98.0 | 90.7 | 80.5 | 75.7 | 99.8 | 97.0 | 84.6 | 81.1 | 78.6 | 99.3

Note that the product of two Toeplitz matrices may not be Toeplitz. We define
$\Delta\mathbf{W}=g(\mathbf{T_{2}},g(\mathbf{T_{1}},\mathbf{x}))$, where
$\mathbf{T_{1}},\mathbf{T_{2}}$ are two Toeplitz matrices, and $g$ is the
operator that allows efficient matrix-vector multiplication with Toeplitz
matrices (see Appendix A.2 ). This formulation leads to the $4n-2$ trainable
parameters. To further reduce this number, we constrain the
$\mathbf{T_{1}},\mathbf{T_{2}}$ to be symmetric, reducing the total number of
trainable parameters to $2n$.

Kronecker Product of Matrices : In this case, we write
$\Delta\mathbf{W}=\mathbf{A}\otimes\mathbf{B}$, where
$\mathbf{A}\in\mathbb{R}^{r_{1}\times
r_{2}},\mathbf{B}\in\mathbb{R}^{\frac{n}{r_{1}}\times\frac{n}{r_{2}}}$. The
hyperparameters $r_{1},r_{2}$ allow us to control not only the number of
trainable parameters but also the rank of $\Delta\mathbf{W}$. In contrast to
low-rank matrix updates, one can create matrices $\Delta\mathbf{W}$ of fairly
large ranks while keeping the number of trainable parameters small (see
Appendix A.1) We follow the same initialization strategy as before.

Table 2: Results on the VTAB-1k benchmark. Baseline numbers are taken from
[29] and [49]. Best numbers are highlighted in bold and the second-best
numbers are underlined.

Method | # Params |  |  |  |  |  |  |  |  |  |  |
---|---|---|---|---|---|---|---|---|---|---|---|---
$\left(\times 10^{6}\right)$ | CIF-100 | Cal-101 | DTD | F-102 | Pets | SVHN | Sun397 | Cam. | EuroSAT | Res-45 | Retino.
Fine-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
BitFit | 0.013 | 72.8 | 87.0 | 59.2 | 97.5 | 85.3 | 59.9 | 51.4 | 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
AdaptFormer | 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 | 54.0 | 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≤32 | 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 (Kronecker) | 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

Figure 6: Low Resource Training. Accuracy of SURM Clip-ViT models as a
function of the fraction of the training data. The results show that SURM can
achieve comparable accuracy with as low as $\sim 2\%$ of the training data for
easier tasks like CIFAR10 and $\sim 20\%$ for harder tasks like SUN397.

In all the mentioned scenarios, it is possible to increase the number of
training parameters by relaxing the matrix structure. This can involve
incorporating more circulant or Toeplitz 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 to experiment with combinations of different LDRMs,
such as a mix of circulant and skew-circulant matrices. We leave this
exploration for future investigation.

Figure 7: Left: Average tradeoff between accuracy and parameter numbers of
various PEFT methods. Results are measured across 5 image datasets using
ViT-B. SURMs appear in the top right corner and perform best among various
strong baseline methods. The complete result is shown in Table 1. Right:
Average performance reported across GLUE benchmark task (8 tasks). SURMs
appears at the top right corner indicating SURM achieves better performance
with a fraction of trainable parameters. The detailed results for individual
tasks are reported in Appendix B.2 (Table 5).

##  6 Experiments

In this section, we show the effectiveness of our proposed methods in a wide
range of vision and NLP tasks through extensive empirical studies.

###  6.1 Vision Experiments

We test SURM on several vision datasets: CIFAR10, CIFAR100 [38], SUN397 [76],
DTD [16] and STL10 [17]. We focus on the LoRA setting and adapt
$\mathbf{Q},\mathbf{K},$ and $\mathbf{V}$ matrices. ViT-B/16 [35] and Clip-
ViT-B/16 [61] are used as base models. Results using ViT-base are presented in
Table 1 (left). SURM consistently outperform $\mathbf{12}$ baseline methods
that use up to 10 times as many parameters. On three out of the five tasks
under consideration, SURMs emerge as the top performers, surpassing LoRA by a
margin as substantial as 5-$\textbf{7}\%$. Meanwhile, SURMs maintain
competitiveness on the remaining two tasks. Results using Clip-ViT are
presented in Table 1 (right). In this setting, our methods are one of the top
two methods among all $\mathbf{12}$ baselines on all 5 tasks. Furthermore, our
method is characterized by an exceptionally small number of trainable
parameters, resulting in 3.65x reduction compared to LoRA, and a 2.4x
reduction compared to LoRA-Fix.

Next, we evaluate SURM in low resource setting using VTAB-1k datasets [81]
using the ViT as the base model against $12$ strong baselines (Table 2).
VTAB-1k is a diverse collection of vision datasets with only $1000$ examples
for training, and in this work we focus on the NATURAL and SPECIALIZED subsets
of VTAB. Among the $11$ tasks examined, our approaches are one of the top 2
methods on $\mathbf{10}$ datasets, competitive on $2$ others. Additional
results on ImageNet can be found in Appendix B.2.

Finally, we evaluate the efficacy of SURM in low data regime. We use the Clip-
ViT model and train on a fraction of training data, showing the results in
Figure 6. We find that among our three proposed SURM methods, Circulant works
best in low data regime. Moreover, we match the full fine-tuning accuracy on
the entire training set with only a small fraction of the data. For more
challenging datasets such as Sun397, we achieve comparable accuracy using
approximately $\sim 20\%$ of the training data, while for datasets like
CIFAR10 and STL10, only about $2\%$ of the training data is required.

As mentioned earlier, contrary to our work, all the previous Kronecker-based
methods constrain the Kronecker adaptations to be low rank. For a detailed
discussion about the difference between our Kronecker adaptation and existing
methods, see Appendix B.3.

NLP Experiments. We exhaustively evaluate our SURM models on the GLUE
benchmark [71]. We compare with different adapter baselines and 11 other PEFT
techniques. These include Bert-base-uncased [20] full finetuning, Adapter
(Houlsby) and Adapter (Pfeiffer) whose numbers are taken from [57]. BiTFit
results are taken from [80] (except QQP numbers which are obtained from [9])
and the numbers for $AA$-adapters from [52]. Prefix, Serial, AdaMix, UniPELT,
Parallel, MAM, and AutoPEFT numbers are taken from [86]. The results for the
remaining baselines are replicated by us. More experimental details can be
found in Appendix B.

Image Segmentation. Next, we focus on the extremely challenging task of
medical image segmentation by using the Synapse multi-organ segmentation
dataset 111https://www.synapse.org/#!Synapse:syn3193805/wiki/217789. Details
of the dataset is presented in Appendix B. The Segment-Anything-Model (SAM)
[33] is used as the foundation model for this task. We follow the training
details in [82]. and adapt the $\mathbf{Q},\mathbf{V}$ in ViT-B image encoder
in the SAM. Finally, in this small data regime, we use the Circulant variant
as it is our most performant variant (Fig. 6). We report the Dice similarity
coefficient (DSC) metric for each of the $8$ organ segmentations as well as
the average DSC score for all (higher is better). For a fair comparison, we
include LoRA with rank $\mathbf{1}$, matching the exact parameter count of
Circulant. The results are presented in Table 3. We report the baseline
performance from [82]. SURMs compare favorably with specialized architectures
developed for medical imaging like U-Net, Attention U-Net, Transformer-based
U-Net, and the Swin U-Net even though they have significantly higher number of
training parameters than our method.

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
Att-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

The full results for all the SURM methods are shown in Appendix Table 5. For
brevity, we summarize the average performance across 8 tasks for SURM-
adapters, as compared to all 11 baselines, in Fig 7 Right. SURM achieve much
better performance at a fraction of the parameters.

Our SURM-LoRA method outperforms the baseline LoRA. For a fair comparison, we
select the ranks in LoRA such that the total number of trainable parameters is
consistent across all methods (Table 5). We perform additional ablations in
Appendix 14(a). Finally, we analyze the representations learnt by SURMs
(Appendix B.4). Our main finding is that the LoRA learnt weights are very
similar to the pre-trained weights whereas SURMs explore a larger space (an
observation similar to [87]).

##  7 Conclusion

We introduce structured unrestricted-rank matrices (SURMs) as an alternative
to low-rank matrices for the parameter efficient fine-tuning (PEFT) of large
Transformer models. In this setting, structured matrices form the cornerstone
of a comprehensive framework, offering a solid base for various PEFT
methodologies, 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).

##  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 on Natural Language Processing (Volume 1: Long Papers), pages 7319–7328, Online, August 2021. Association for Computational Linguistics.
  * [2] Ebtesam Almazrouei, Hamza Alobeidli, Abdulaziz Alshamsi, Alessandro Cappelli, Ruxandra Cojocaru, Mérouane Debbah, Étienne Goffinet, Daniel Hesslow, Julien Launay, Quentin Malartic, Daniele Mazzotta, Badreddine Noune, Baptiste Pannier, and Guilherme Penedo.  The falcon series of open language models, 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 Anthony, Herbie Bradley, Kyle O’Brien, Eric Hallahan, Mohammad Aflah Khan, Shivanshu Purohit, USVSN Sai Prashanth, Edward Raff, Aviya Skowron, Lintang Sutawika, and Oskar van der Wal.  Pythia: A suite for analyzing large language models across training and scaling, 2023.
  * [5] James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman-Milne, and Qiao Zhang.  JAX: composable transformations of Python+NumPy programs, 2018.
  * [6] Richard P. Brent.  Stability of fast algorithms for structured linear systems.  CoRR, abs/1005.0671, 2010.
  * [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 J Joshi, Ryan Julian, Dmitry Kalashnikov, Yuheng Kuang, Isabel Leal, Kuang-Huei Lee, Sergey Levine, Yao Lu, Utsav Malla, Deeksha 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, 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, 2020.
  * [9] Jin Cao, Chandana Satya Prakash, and Wael Hamza.  Attention fusion: a light yet efficient late fusion mechanism for task adaptation in NLU.  In Marine Carpuat, Marie-Catherine de Marneffe, and Ivan Vladimir Meza Ruiz, editors, Findings of the Association for Computational Linguistics: NAACL 2022, pages 857–866, Seattle, United States, July 2022. Association for Computational Linguistics.
  * [10] Arnav Chavan, Zhuang Liu, Deepak Gupta, Eric Xing, and Zhiqiang Shen.  One-for-all: Generalized lora for parameter-efficient fine-tuning, 2023.
  * [11] Banghao Chen, Zhaofeng Zhang, Nicolas Langrené, and Shengxin Zhu.  Unleashing the potential of prompt engineering in large language models: a comprehensive review, 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 arXiv:2205.13535, 2022.
  * [13] Yukang Chen, Shengju Qian, Haotian Tang, Xin Lai, Zhijian Liu, Song Han, and Jiaya Jia.  Longlora: Efficient fine-tuning of long-context large language models, 2023.
  * [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 IEEE 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 Pattern 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/papers/coatesleeng_aistats_2011.pdf.
  * [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 finetuning of quantized llms, 2023.
  * [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 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers), pages 4171–4186, Minneapolis, Minnesota, June 2019. Association for Computational Linguistics.
  * [21] Ali Edalati, Marzieh Tahaei, Ivan Kobyzev, Vahid Partovi Nia, James J. Clark, and Mehdi Rezagholizadeh.  Krona: Parameter efficient tuning with kronecker adapter, 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 on vision-language foundation models, 2023.
  * [23] Junxian He, Chunting Zhou, Xuezhe Ma, Taylor Berg-Kirkpatrick, and Graham Neubig.  Towards a 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:2203.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 NLP.  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.
  * [26] Edward J Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, and Weizhu Chen.  LoRA: Low-rank adaptation of large language models.  In International 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 on 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, Lélio Renard Lavaud, Marie-Anne Lachaux, Pierre Stock, Teven Le Scao, Thibaut Lavril, Thomas Wang, Timothée Lacroix, and William El Sayed.  Mistral 7b, 2023.
  * [29] Shibo Jie and Zhi-Hong Deng.  Fact: Factor-tuning for lightweight adaptation on vision transformer.  In Proceedings of AAAI Conference on Artificial Intelligence (AAAI), 2023.
  * [30] Damjan Kalajdzievski.  A rank stabilization scaling factor for fine-tuning with lora, 2023.
  * [31] Rabeeh Karimi Mahabadi, Sebastian Ruder, Mostafa Dehghani, and James Henderson.  Parameter-efficient multi-task fine-tuning for transformers via shared hypernetworks.  In Annual Meeting of the Association for Computational Linguistics, 2021.
  * [32] Diederik P. Kingma and Jimmy Ba.  Adam: A method for stochastic optimization, 2017.
  * [33] Alexander Kirillov, Eric Mintun, Nikhila Ravi, Hanzi Mao, Chloe Rolland, Laura Gustafson, Tete Xiao, Spencer Whitehead, Alexander C. Berg, Wan-Yen Lo, Piotr Dollár, and Ross Girshick.  Segment anything, 2023.
  * [34] Matthias Kissel and Klaus Diepold.  Structured matrices and their application in neural networks: A survey.  New Generation Computing, 41(3):697–722, Sep 2023.
  * [35] 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 at scale.  In Ninth International Conference on Learning Representations. ICLR, 2021.
  * [36] 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.
  * [37] Simon Kornblith, Mohammad Norouzi, Honglak Lee, and Geoffrey Hinton.  Similarity of neural network representations revisited, 2019.
  * [38] Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton.  Cifar-10 (canadian institute for advanced research), 2009.
  * [39] George Labahn and Tamir Shalom.  Inversion of toeplitz matrices with only two standard equations.  Linear Algebra and its Applications, 175:143–158, 1992.
  * [40] Damiana Lazzaro and Serena Morigi.  Matrix completion for matrices with low-rank displacement.  2020\.
  * [41] Jaejun Lee, Raphael Tang, and Jimmy Lin.  What would elsa do? freezing layers during transformer fine-tuning, 2019.
  * [42] 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 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), pages 4582–4597, Online, August 2021. Association for Computational Linguistics.
  * [43] 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.
  * [44] Vladislav Lialin, Vijeta Deshpande, and Anna Rumshisky.  Scaling down to scale up: A guide to parameter-efficient fine-tuning, 2023.
  * [45] 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, 2024.
  * [46] Ilya Loshchilov and Frank Hutter.  Decoupled weight decay regularization, 2019.
  * [47] 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, 2022.
  * [48] Yuchen Lu, Zhen Liu, Aristide Baratin, Romain Laroche, Aaron Courville, and Alessandro Sordoni.  Using representation expressiveness and learnability to evaluate self-supervised learning methods, 2023.
  * [49] 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.
  * [50] Rabeeh Karimi Mahabadi, James Henderson, and Sebastian Ruder.  Compacter: Efficient low-rank hypercomplex adapter layers, 2021.
  * [51] Yuning Mao, Lambert Mathias, Rui Hou, Amjad Almahairi, Hao Ma, Jiawei Han, Wen-tau Yih, and Madian Khabsa.  Unipelt: A unified framework for parameter-efficient language model tuning, 2022.
  * [52] 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.
  * [53] Bernard Mourrain and Victor Y. Pan.  Multivariate polynomials, duality, and structured matrices.  J. Complex., 16(1):110–180, 2000.
  * [54] 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-Second Annual ACM Symposium on Theory of Computing, May 21-23, 2000, Portland, OR, USA, pages 573–581. ACM, 2000.
  * [55] Samet Oymak, Zalan Fabian, Mingchen Li, and Mahdi Soltanolkotabi.  Generalization guarantees for neural networks via harnessing the low-rank structure of the jacobian, 2019.
  * [56] Victor Y. Pan.  Structured matrices and polynomials: Unified superfast algorithms.  2001\.
  * [57] 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 Processing (EMNLP 2020): Systems Demonstrations, pages 46–54, Online, 2020. Association for Computational Linguistics.
  * [58] Phillip Pope, Chen Zhu, Ahmed Abdelkader, Micah Goldblum, and Tom Goldstein.  The intrinsic dimension of images and its impact on learning, 2021.
  * [59] 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.
  * [60] Shikai Qiu, Andres Potapczynski, Marc Finzi, Micah Goldblum, and Andrew Gordon Wilson.  Compute better spent: Replacing dense layers with structured matrices, 2024.
  * [61] Alec Radford, Jong Wook Kim, Chris Hallacy, A. Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, Gretchen Krueger, and Ilya Sutskever.  Learning transferable visual models from natural language supervision.  In ICML, 2021.
  * [62] 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 a unified text-to-text transformer.  Journal of Machine Learning Research, 21(140):1–67, 2020.
  * [63] Andreas Rücklé, Gregor Geigle, Max Glockner, Tilman Beck, Jonas Pfeiffer, Nils Reimers, and Iryna Gurevych.  Adapterdrop: On the efficiency of adapters in transformers, 2021.
  * [64] Vikas Sindhwani, Tara Sainath, and Sanjiv Kumar.  Structured transforms for small-footprint deep learning.  In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 28. Curran Associates, Inc., 2015.
  * [65] Yi Tay, Mostafa Dehghani, Vinh Q. Tran, Xavier Garcia, Jason Wei, Xuezhi Wang, Hyung Won Chung, Siamak Shakeri, Dara Bahri, Tal Schuster, Huaixiu Steven Zheng, Denny Zhou, Neil Houlsby, and Donald Metzler.  Ul2: Unifying language learning paradigms, 2023.
  * [66] Anna T. Thomas, Albert Gu, Tri Dao, Atri Rudra, and Christopher Ré.  Learning compressed transforms with low displacement rank, 2019.
  * [67] Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, Aurelien Rodriguez, Armand Joulin, Edouard Grave, and Guillaume Lample.  Llama: Open and efficient foundation language models, 2023.
  * [68] Lucrezia Valeriani, Diego Doimo, Francesca Cuturello, Alessandro Laio, Alessio Ansuini, and Alberto Cazzaniga.  The geometry of hidden representations of large transformer models, 2023.
  * [69] 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.
  * [70] 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.
  * [71] Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel Bowman.  GLUE: A multi-task benchmark and analysis platform for natural language understanding.  In 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.
  * [72] Qizhou Wang, Sarah M. Erfani, Christopher Leckie, and Michael E. Houle.  A Dimensionality-Driven Approach for Unsupervised Out-of-distribution Detection, pages 118–126.
  * [73] Yaqing Wang, Sahaj Agarwal, Subhabrata Mukherjee, Xiaodong Liu, Jing Gao, Ahmed Hassan Awadallah, and Jianfeng Gao.  AdaMix: Mixture-of-adaptations 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 5744–5760, Abu Dhabi, United Arab Emirates, December 2022. Association for Computational Linguistics.
  * [74] 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.
  * [75] 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: State-of-the-art natural language processing.  In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations, pages 38–45, Online, October 2020. Association for Computational Linguistics.
  * [76] J. Xiao, J. 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 3485–3492, June 2010.
  * [77] 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, 2023.
  * [78] Peng Xu, Xiatian Zhu, and David A. Clifton.  Multimodal learning with transformers: A survey, 2023.
  * [79] Bruce X. B. Yu, Jianlong Chang, Lin Liu, Qi Tian, and Changan Chen.  Towards a unified view on visual parameter-efficient transfer learning.  ArXiv, abs/2210.00788, 2022.
  * [80] Elad Ben Zaken, Shauli Ravfogel, and Yoav Goldberg.  Bitfit: Simple parameter-efficient fine-tuning for transformer-based masked language-models, 2022.
  * [81] Xiaohua Zhai, Joan Puigcerver, Alexander Kolesnikov, Pierre Ruyssen, Carlos Riquelme, Mario Lucic, Josip Djolonga, Andre Susano Pinto, Maxim Neumann, Alexey Dosovitskiy, Lucas Beyer, Olivier Bachem, Michael Tschannen, Marcin Michalski, Olivier Bousquet, Sylvain Gelly, and Neil Houlsby.  A large-scale study of representation learning with the visual task adaptation benchmark, 2020.
  * [82] Kaidong Zhang and Dong Liu.  Customized segment anything model for medical image segmentation, 2023.
  * [83] Meng Zhang, Fei Liu, and Dongpeng Weng.  Speeding-up and compression convolutional neural networks by low-rank decomposition without fine-tuning.  J. Real-Time Image Process., 20(4), may 2023.
  * [84] 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, 2022.
  * [85] 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 on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 4082–4090. PMLR, 06–11 Aug 2017.
  * [86] Han Zhou, Xingchen Wan, Ivan Vulić, and Anna Korhonen.  Autopeft: Automatic configuration search for parameter-efficient fine-tuning.  arXiv preprint arXiv:2301.12132, 2023.
  * [87] 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, 2023.

##  Appendix A Implementation Details

In this section, we discuss the details of various algorithms and workflows
within SURM.

###  A.1 Finding the Smallest Number of Training Parameters for Kronecker
Layers

Let $\mathbf{W}$ be a $d\times d$ matrix that can be written as
$\mathbf{W}=\mathbf{A}\otimes\mathbf{B}$, where
$\mathbf{A}\in\mathbb{R}^{m_{1}\times
n_{1}},\mathbf{B}\in\mathbb{R}^{m_{2}\times n_{2}}$. We want to minimize the
following objective:

$~{}m_{1}n_{1}+m_{2}n_{2},\text{ subject to }m_{1}m_{2}=n_{1}n_{2}=d.$ (4)

We can rewrite the above as : $m_{1}={d}{/m_{2}}$ and $n_{1}={d}{/n_{2}}$.
Plugging these back in Eq. 4, we get:

$\begin{split}m_{1}n_{1}+m_{2}n_{2}&=\frac{d^{2}}{m_{2}n_{2}}+m_{2}n_{2}\\\
&=\frac{d^{2}}{m_{2}n_{2}}+m_{2}n_{2}-2d+2d\\\
&=\left(\sqrt{m_{2}n_{2}}-\frac{d}{\sqrt{m_{2}n_{2}}}\right)^{2}+2d\\\ &\geq
2d.\end{split}$ (5)

The equality is obtained when $\sqrt{m_{2}n_{2}}={d}{/\sqrt{m_{2}n_{2}}}$,
thereby satisfying the constraint $m_{2}n_{2}=m_{1}n_{1}=d$. Essentially this
result shows that we can minimize the number of training parameters when the
matrices $\mathbf{A}$ and $\mathbf{B}$ are similarly sized. Furthermore, since
both $\mathbf{A}$ (and $\mathbf{B}$) have $d$ training parameters, we can
maximize the rank of the matrix if we can make it close to a square matrix
(i.e. we choose 2 factors $a,b$ of $d$, such $ab=d$ and $a$ is as close to $b$
as possible). Note that
$\text{rank}(\mathbf{A}\otimes\mathbf{B})=\text{rank}(\mathbf{A})\text{rank}(\mathbf{B})$.
Thus, for our experiments with BERT and ViT models, we take $\mathbf{A}$ to be
a matrix of size $32\times 24$ and $\mathbf{B}$ to be of size $24\times 32$.
This choice of matrix shapes allows us to substantially reduce the
computational complexity of matrix-vector multiplication (see Section A.2).

###  A.2 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 $O(n\log n)$ time. This is
done by the following steps : (a) take the FFT of the input vector
$\mathbf{v}$ and the vector representation of the circulant matrix
$\mathbf{c}$, and call them $\mathbf{V}$ and $\mathbf{C}$ respectively. (b)
Take the inverse Fourier transform of the Hadamard (element-wise) product of
$\mathbf{V}$ and $\mathbf{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 in the time domain corresponds to element-wise multiplication in
the frequency domain after FFT. By leveraging FFT, the time complexity of the
multiplication is reduced from $O(n^{2})$ to $O(n\log n)$.

The same ideas extend to the case of Toeplitz matrices, where one can embed
the Toeplitz matrix into a circulant matrix and use FFT as 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.

For the case of a matrix $\mathbf{W}=\mathbf{AB}$, where
$\mathbf{W}\in\mathbb{R}^{m\times n},\mathbf{A}\in\mathbb{R}^{m\times r}$ and
$\mathbf{B}\in\mathbb{R}^{r\times n}$, then multiplication by $\mathbf{v}$
takes $O(r(m+n))$ and one gets computation gains when
$r\ll\text{min}\\{m,n\\}$. Finally, for a Hadamard product of matrices
$\mathbf{A}\in\mathbb{R}^{r_{1}\times
r_{2}},\mathbf{B}\in\mathbb{R}^{k_{1}\times
k_{2}},\mathbf{v}\in\mathbb{R}^{r_{2}k_{2}}$,
$(\mathbf{A}\otimes\mathbf{B})\mathbf{v}=\text{vec}(\mathbf{B}r(\mathbf{v})^{\top}\mathbf{A}^{\top})$,
where $\text{vec}(\cdot)$ is the vectorization operator that takes a matrix
$\mathbf{M}\in\mathbb{R}^{m\times n}$ and converts it to $\mathbb{R}^{mn\times
1}$ column vector by stacking the columns of $\mathbf{M}$ on top of each other
and $r$ is the PyTorch style reshape operator that reshapes the vector
$\mathbf{v}$ to a matrix of shape $r_{2}\times k_{2}$. Choosing
$\text{max}\\{r_{i},k_{i}\\}\ll r_{i}k_{i}$, for $i=1,2$, one can
substantially reduce the computational complexity.

###  A.3 Integration of SURMs in Adapters

The adapter method [25] proposes injecting small bottleneck networks into
Transformer layers, usually after feed-forward layers. The main equation of an
adapter block is given by:

$~{}\mathbf{Y}=\mathbf{X}+\sigma(\mathbf{XB})\mathbf{A},$ (6)

where $\sigma(\cdot)$ is a non-linear activation function applied point-wise,
$\mathbf{X}\in\mathbb{R}^{b\times s\times n}$ represents input to the layer
($b$ is the batch size and $s$ is the sequence length),
$\mathbf{A}\in\mathbb{R}^{r\times n},\mathbf{B}\in\mathbb{R}^{n\times r}$ are
two low-rank matrices ($r\ll n$) and $\mathbf{Y}$ is the output of the layer.
Similar to LoRA, matrix $\mathbf{B}$ is initialized randomly, whereas
$\mathbf{A}$ is initialized as a zero-matrix. For convenience, layer norms and
bias terms are not included in the equation.

SURMs can be used in place of low rank $\mathbf{A}$ and $\mathbf{B}$. The
integration and design choices of various LDRs in this setting mimic that of
LoRA. We will now provide a detailed explanation of the integration of
circulant matrices within the adapter setting.

Circulant Matrices. Similar to the LoRA setting, we apply two circulant
matrices $\mathbf{C}_{1},\mathbf{C}_{2}$, resulting in the following equation
of the adapter block:

$~{}\mathbf{Y}=\mathbf{X}+\sigma(f(\mathbf{r_{1}}\odot\mathbf{r_{2}},\mathbf{X}))+\mathbf{b},$
(7)

where $f$ is an operator multiplying input matrix $\mathbf{X}$ with the
circulant matrix obtained by multiplying two circulant matrices encoded by
$\mathbf{r}_{1}$ and $\mathbf{r}_{2}$ (Appendix A.2). The vector
$\mathbf{r}_{1}$ is initialized randomly while $\mathbf{r}_{2}$ and
$\mathbf{b}$ are initialized as zero vectors. Note that we apply the non-
linearity after we multiply $\mathbf{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 a circulant matrix and not both: $\mathbf{r}_{1}$ and $\mathbf{r}_{2}$.
This results in lower storage costs and faster deployment.

Toeplitz Matrices. Similar to the case of Toeplitz matrices within LoRA, we
use two symmetric Toeplitz matrices $\mathbf{T_{1}},\mathbf{T_{2}}$, where
$\mathbf{T_{1}}$ and $\mathbf{b}$ is initialized as a zero vector and
$\mathbf{T_{2}}$ is initialized randomly. We then define the adapter layer to
be:

$~{}\mathbf{Y}=\mathbf{X}+\sigma(g(\mathbf{T_{1}},g(\mathbf{T_{2}},\mathbf{X})))+\mathbf{b}.$
(8)

The position of the non-linear mapping $\sigma$ is chosen such that we can
merge the two trained matrices resulting in smaller storage costs and fast
deployment.

Kronecker Product of Matrices. In this case, we rewrite Equation 6 as:

$~{}\mathbf{Y}=\mathbf{X}+\sigma(\mathbf{X}(\mathbf{B}\otimes\mathbf{A}))+\mathbf{b},$
(9)

where $\mathbf{B}\otimes\mathbf{A}$ is the Kronecker product. In this case,
$\mathbf{B}$ is initialized randomly and $\mathbf{A}$ and $\mathbf{b}$ are
initialized by zeros. In all experiments using SURM-adapters, $\sigma(\cdot)$
is the GeLU non-linearity.

###  A.4 Computing Approximations by LDR Matrices

In this section, we show how we can approximate any matrix
$\mathbf{D}\in\mathbb{R}^{n\times n}$ 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
$\\{\mathbf{e_{1}},\cdots,\mathbf{e_{n}}\\}$ are a set of orthogonal vectors
spanning a subspace $\mathbf{W}$, then the closest vector to $\mathbf{v}$ in
$\mathbf{W}$ is given by

$\hat{\mathbf{v}}=\frac{(\mathbf{v},\mathbf{e_{1}})}{\|\mathbf{e_{1}}\|^{2}}\mathbf{e_{1}}+\ldots+\frac{(\mathbf{v},\mathbf{e_{n}})}{\|\mathbf{e_{n}}\|^{2}}\mathbf{e_{n}}.$
(10)

The space of circulant matrices has dim $n$, so spanned by the orthogonal set
$\\{(1,\cdots,\cdots 0),(0,\cdots 1,\cdots 0),(0,\cdots,\cdots 1)\\}$. Using
the above formula, one can write down a simplified expression of the circulant
matrix as$\hat{\mathbf{C}}:=(\hat{c_{1}},\cdots\hat{c_{n}})$ that approximates
$\mathbf{D}$

$\hat{c}_{1}={}\frac{1}{n}\sum_{j=1}^{n}d_{jj},\quad\hat{c}_{k}=\frac{1}{n}\left\\{\sum_{j=1}^{k-1}d_{j(1+j+n-k)}\right.\left.+\sum_{j=k}^{n}d_{j(j-k+1)}\right\\},\text{
where }k=\\{2,\ldots,n\\}.$

Note that the same set as before spans the space of symmetric Toeplitz
matrices. This yields a compact formula for the approximating Toeplitz matrix:

$\hat{\mathbf{T}}:=\left(\dfrac{1}{n}\displaystyle\sum_{i=1}^{n}a_{i,i}\right)\mathbf{I}_{n}+\left(\dfrac{1}{n-1}\displaystyle\sum_{i=1}^{n-1}a_{i,i+1}\right)\mathbf{M}_{2}+\\\
\left(\dfrac{1}{n-2}\displaystyle\sum_{i=1}^{n-2}a_{i,i+2}\right)\mathbf{M}_{3}+\cdots+a_{1,n}\mathbf{M}_{n},$

where $\mathbf{M}_{i}$ is the symmetric Toeplitz matrix generated by the
$i$-th element in the set above. Finally the set
{$((1,0,\cdots,0),(0,\cdots,0)),\cdots((0,\cdots,1,\cdots,0),(0,\cdots,0)),((0,\cdots,0),(0,\cdots,1,\cdots,0)$
} spans all Toeplitz matrices where the first element in each tuple denotes
the first row and the second element the first column. Note that since the
$a_{1}1$ entry is shared by both first row and column we treat the first
vector as $n$-dimensional vector and the second as $n-1$ dimensional vector.
Thus the dimension of the space is $2n-1$. Using FFT and the projection
formula, one can compute the approximation by a Toeplitz matrix.

###  A.5 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 at random from
$\mathcal{N}(0,1)$, represents a completely unstructured family.

  * •

Near-low rank: Each matrix from the second class was chosen from the
distribution: $\mathbf{G}\mathbf{H}^{\top}+\epsilon\mathbf{R}$, where
$\mathbf{G},\mathbf{H}\in\mathbb{R}^{n\times r}$ for $r\ll n$,
$\mathbf{R}\in\mathbb{R}^{n\times n}$, $\epsilon=0.05$, and the entries of
$\mathbf{G},\mathbf{H},\mathbf{R}$ are taken independently at random from
$\mathcal{N}(0,1)$.

  * •

Near-low intrinsic rank: Matrices from the third class are constructed as
follows. First we sample:
$t_{0},...,t_{n-1}\overset{\mathrm{iid}}{\sim}\mathcal{N}(0,1)$. The $i$-th
row of the resulting matrix is of the form: $(\sin(1\cdot t_{i}),\sin(2\cdot
t_{i}),...,\sin(n\cdot t_{i}))+\mathbf{g}_{i}$, wheare either all
$\mathbf{g}_{i}$ are zero-vectors or they are taken independently at random
from $\epsilon*\mathcal{N}(0,\mathbf{I}_{n})$. Note that even though that
matrix is not necessarily low-rank, it is taken from the vicinity of the
$n$-dimensional manifold, since it is fully determined by the sampled tuple
$(t_{0},...,t_{n-1})$. Matrices from all the classes are taken from
$\mathbb{R}^{100\times 100}$.

Optimizing Circulant and Toeplitz Matrices. In general, an optimal
approximation (e.g. with respect to the Frobenius norm as a distance) of a
given matrix by a matrix $\mathbf{W}(\mathbf{G},\mathbf{H})$ is not given by
the closed-form expression. Thus we will thus construct good-quality
approximators via gradient-based optimization (see: Sec. 4.1).

Details on Approximation Experiments in Section 4.2. Now we provide additional
details on the experiments that explicitly compare LDRMs with low-rank
matrices. For these experiments, we construct a PSD matrices
$\mathbf{M}\in\mathbb{R}^{50\times 50}$ with $L^{2}$ normalized rows. We fix a
parameter budget of $n=50$. The low-rank approximation, in that case, becomes
an outer product by a vector $\mathbf{v}$. For the Kronecker product, we
choose a factor $\mathbf{A}\in\mathbb{R}^{10\times 5}$. To maintain the
parameter budget, the other factor becomes $\mathbf{A}^{\top}$. If
$\hat{\mathbf{M}}$ is the approximating matrix, then we define error =
$||\hat{\mathbf{M}}-\mathbf{M}||_{F}$, where $||\cdot||_{F}$ is the Frobenius
norm.

We use the closed-form formula for the optimal circulant and symmetric
Toeplitz matrices approximating $\mathbf{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.6 Invertible Toeplitz Matrices

Inverses of Toeplitz matrices can be effectively found [39]. We recall the
celebrated result of Gohberg and Semencul.

######  Theorem A.1.

Let $\mathbf{A}:=(a_{p-q})_{p,q=1}^{n}$ be a Toeplitz matrix. If the following
systems of equations

$\displaystyle\sum_{q=1}^{n}a_{p-q}x_{q}=\delta_{p,1},\sum_{q=1}^{n}a_{p-q}y_{q}=\delta_{p,n},\text{
where }p=\\{1,2\ldots n\\}$

is solvable and $x_{1}\neq 0$, then $\mathbf{A}$ is invertible.

In our case, we consider only symmetric Toeplitz matrices. Thus the above
equation really boils down to solving the first system of equations as the
next system can be solved by using the first, i.e. by setting
$x_{n-i+1}=y_{i}~{}~{}~{}i=1,2,\cdots n$. The first system of equations can be
efficiently solved by Gaussian elimination.

##  Appendix B Experiments

In this section, we describe our experimental setup and present additional
analysis experiments to evaluate the functioning of SURM.

###  B.1 Hyperparameters

In this section, we provide the details of the hyperparameters used in our
experiments. For GLUE tasks, we use the LORA hyperparameters that are used in
the original LoRA paper except we use $r=1$ to parameter match our methods as
well as $\alpha=1$.

For all the experiments, we use AdamW optimizer [46] with a warmup ratio of
$0.06$, a linear learning rate scheduler, and a sequence length of $128$. For
our methods and the Compacter baseline, we use a batch size of $64$. We report
the rest of the hyperparameters in Table 4. The code to run NLP experiments is
developed using PyTorch using Huggingface, Adapter-transformer, PEFT
libraries, and the original LoRA codebase.

Table 4: Hyperparameters used for our GLUE experiments

Method | Hyperparameters | RTE | MRPC | QNLI | QQP | SST-2 | MNLI | STSB | COLA
---|---|---|---|---|---|---|---|---|---
LoRA | Batch Size | 32 | 16 | 32 | 16 | 16 | 16 | 16 | 32
# Epochs | 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
Kronecker-LoRA | Weight Decay | 0.0 | 0.25 | 0.1 | 0.1 | 0.1 | 1e-3 | 0.25 | 0.1
# 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
Circulant-LoRA | Weight Decay | .25 | .15 | .1 | .1 | .1 | .1 | .25 | .1
# Epochs | 70 | 60 | 80 | 80 | 60 | 80 | 80 | 70
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
Toeplitz-LoRA | Weight Decay | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0
# Epochs | 70 | 60 | 80 | 80 | 60 | 80 | 70 | 60
Learning Rate | 7e-4 | 5e-4 | 7e-4 | 7e-4 | 7e-4 | 7e-4 | 7e-4 | 7e-4
| Dropout | 0.1 | 0.1 | 0.1 | 0.1 | 0.1 | 0.1 | 0.1 | 0.1
Kronecker-Adapter | Weight Decay | 0.2 | 0.2 | 0.2 | 0.2 | 0.2 | 0.2 | 0.2 | 0.2
# Epochs | 70 | 70 | 80 | 80 | 60 | 80 | 70 | 60
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
Circulant-Adapter | Weight Decay | 1e-4 | 0.0 | 1e-4 | 1e-4 | 1e-4 | 1e-4 | 0.2 | 0.0
# Epochs | 70 | 70 | 80 | 80 | 60 | 80 | 70 | 60
Learning Rate | 2e-3 | 2e-3 | 2e-3 | 2e-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
Toeplitz-Adapter | Weight Decay | 0.2 | 0.2 | 0.1 | 0.1 | 0.2 | 0.1 | 0.2 | 0.2
# Epochs | 70 | 70 | 80 | 80 | 60 | 80 | 70 | 60
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
Compacter | # Epochs | 70 | 70 | 80 | 80 | 60 | 80 | 70 | 60
Learning Rate | 3e-3 | 3e-3 | 3e-3 | 3e-3 | 3e-3 | 3e-3 | 3e-3 | 3e-3

For ViT experiments, we use JaX [5] and the open-sourced JAX implementation of
ViT.

Additional Details on the Pinwheel Experiment. 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 is frozen
and the rest of the network is trained for 2000 epochs. This can be thought of
fitting a feature extractor on top of a randomized projection. The setting (b)
is presented in the main paper while setting (a) is presented in Appendix B.2.
Next, we provide additional details for our text and vision experiments.

Figure 8: Left : Representation of the pinwheel dataset., Right : Fitting the
same dataset with regular training.

NLP Experiments. We train the LoRA-BERT using PEFT library from Huggingface
[75]. The hyperparameters used by the original authors are used in this
setting. For experiments comparing with the LoRA baseline, we parameter match
the LoRA updates with our SURMs, thus the LoRA updates are given by rank $1$
matrices. we 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, we apply the GeLU non-linearity. Kronecker-based
adapter, though similar to various other methods, was never tested in the
BERT-setting 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 adapter-transformers library [57].
For the compacter parameters, we use $n=4$ (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 of training parameters $2d$
(excluding bias terms), which gives the reader a 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 use a batch
size of $64$. AdamW [46] optimizer is used for all experiments.

Image Classification Experiments. For the image experiments, we use Adam
optimizer [32] with 20k max iterations per dataset with a batch size of $64$.
The learning rate used is 5e-5 except for SVHN where we use a learning rate of
5e-4. The experiments are run on TPUv4 $4\times 2$ compute resources.

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\sim 198$ slices and each slice includes $512\times 512$
pixels with a spatial resolution of ($[0.54\sim 0.54]\times[0.98\sim
0.98]\times[2.5\times 5.0]$mm3 ). We use the Segment-Anything-Model (SAM) [33]
as the foundation model for this task. There has been a number of works in
adapting various PEFT methods to fine tuning SAM. We follow the training
details in [82]. More specifically, we adapt the $\mathbf{Q},\mathbf{V}$ in
ViT-B image encoder in the SAM and normally finetune the small decoder head.
Finally, in this small data regime, we use the Circulant variant as it is our
most performant variant in this case (see Fig. 6). We report the Dice
similarity coefficient (DSC) metric for each of the $8$ organ segmentation as
well as the average DSC score for all (higher is better). The SAMed model uses
a LoRA rank $\mathbf{4}$ in $\mathbf{Q},\mathbf{V}$. For a fair comparison, we
include LoRA rank $\mathbf{1}$, matching the exact parameter count of
Circulant. We use an A100 40GB GPU for this experiment.

Table 5: Performance of SURM and other baselines on GLUE benchmark. We report
the MCC score CoLA, F1 score for MRPC, Spearman correlation for STSB, and
accuracy scores for the other tasks. All results are obtained by averaging
over 3 seeds. Best numbers are highlighted in bold and the second best numbers
is underline.

Method | # Params | RTE | MRPC | QNLI | QQP | SST-2 | MNLI | STSB | COLA
---|---|---|---|---|---|---|---|---|---
$\left(\times 10^{6}\right)$ | 2.5k | 3.7k | 105k | 364k | 67k | 393k | 7k | 8.5k
BERT-baseline [20] | 110 | $66.2$ | $90.5$ | $\underline{91.3}$ | $\mathbf{91.4}$ | $92.6$ | $84.1$ | $88.8$ | $59.5$
Adapter (Houlsby) [57] | 1.8 | $69.8$ | ${\underline{91.5}}$ | $91.2$ | ${\underline{90.8}}$ | ${\underline{92.8}}$ | $84.1$ | $\mathbf{89.2}$ | $59.1$
Adapter (Pfeiffer) [57] | 0.9 | $70.8$ | $89.7$ | $\underline{91.3}$ | $90.5$ | $92.2$ | $84.1$ | $89.0$ | $58.9$
$AA$ [52] | 0.7 | $64.25$ | $85.09$ | $89.96$ | $88.09$ | $91.31$ | $82.89$ | $88.25$ | $51.44$
BitFit [80] | $\underline{0.1}$ | $72.3$ | $90.4$ | $90.2$ | $85.6$ | $92.1$ | $81.4$ | $\mathbf{89.2}$ | $58.8$
Compacter [50] | 0.11 | $72.84$ | $90.18$ | $91.08$ | $90.6$ | $92.1$ | $83.26$ | $88.64$ | $59.6$
LORA [26] | $\mathbf{0.06}$ | $71.12$ | $90.43$ | $90.45$ | $90.1$ | $92.66$ | $83.06$ | $88.69$ | $57.83$
Prefix [42] | 0.19 | $70.54$ | $89.93$ | $90.76$ | $89.12$ | $91.93$ | $82.78$ | $85.93$ | $58.86$
Serial [86] | 0.89 | $68.01$ | $88.65$ | $91.06$ | $90.52$ | $91.93$ | $84.18$ | $84.75$ | $59.73$
AdaMix [73] | 0.89 | $70.11$ | $90.91$ | $\mathbf{91.52}$ | $90.22$ | $92.06$ | $\underline{84.25}$ | $86.86$ | $59.11$
UniPELT [51] | 1.38 | $67.07$ | $88.72$ | $91.09$ | $90.69$ | $92.52$ | $\mathbf{84.28}$ | $84.22$ | $60.13$
Parallel [86] | 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 [86] | 1.54 | $72.35$ | $\underline{91.5}$ | $91.12$ | $90.64$ | $92.22$ | $84.01$ | $89.17$ | $\mathbf{60.92}$
SURM (Kronecker-Adapter) | $\mathbf{0.06}$ | $\mathbf{72.96}$ | $91.11$ | $90.53$ | $89.86$ | $92.66$ | $83.01$ | $88.94$ | $58.77$
SURM (Toeplitz-Adapter) | $\mathbf{0.06}$ | ${\underline{72.92}}$ | $91.08$ | $90.47$ | $89.54$ | $92.55$ | $83.04$ | $89.08$ | $59.56$
SURM (Circulant-Adapter) | $\mathbf{0.06}$ | $72.12$ | $\mathbf{91.55}$ | $91.24$ | $89.97$ | $\mathbf{93.0}$ | $83.45$ | $88.78$ | $59.2$
SURM (Kronecker-LoRA) | $\mathbf{0.06}$ | $71.35$ | $90.08$ | $90.87$ | $90.0$ | $92.78$ | $83.02$ | $88.91$ | $\underline{60.35}$
SURM (Toeplitz-LoRA) | $\mathbf{0.06}$ | $71.4$ | $90.96$ | $90.56$ | $89.95$ | $92.4$ | $82.54$ | $88.74$ | $58.83$
SURM (Circulant-LoRA) | $\mathbf{0.06}$ | $71.84$ | $91.02$ | $90.64$ | $90.15$ | $92.68$ | $82.87$ | ${\underline{89.18}}$ | $59.97$

###  B.2 Additional Experiments

First, we provide a figure of the pinwheel dataset used to showcase the
approximation qualities to LDRMs (see Fig 8 left). Next, we conduct additional
experiments on the ImageNet-1k 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 to the full fine-tuning results.

Table 6: Comparison of the performance of SURM and baseline PEFT methods on
ImageNet-1k

|  SURM (Kronecker) |  SURM (Toeplitz) |  SURM (Circulant) | Linear Prob. | VPT-Shallow | VPT-Deep | Fine-tuning | SSF
---|---|---|---|---|---|---|---|---
# Params (M) | 0.055 | 0.055 | 0.055 | 0.049 | 0.063 | 0.531 | 86.63 | 0.240
Accuracy | 83.14 | 80.17 | 82.67 | 82.04 | 82.08 | 82.45 | 84.1 | 83.10

Ablation Experiments. Here, we show the effect of various design choices.
Figure LABEL:fig:bias_ablates 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 $\mathbf{.04}$M, providing an even
lightweight but still capable method. Therefore, if there are concerns
regarding storage and latency, opting for adapters without bias is a viable
option. Moreover, we show the effect on only adapting $\mathbf{Q},\mathbf{V}$
instead of $\mathbf{Q},\mathbf{K},\mathbf{V}$ as shown in the main paper.
Table 7 shows that on GLUE tasks, there is a minimal effect for not adapting
the $\mathbf{K}$ matrix.

Table 7: LoRA ablation experiments on 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 3 seeds. The best results are in bold and the
second best results are underlined.

| # Params ($\times 10^{6}$) | RTE | MRPC | QNLI | QQP | SST-2 | MNLI | STSB | COLA
---|---|---|---|---|---|---|---|---|---
Bert-baseline [20] | 110 | $66.2$ | $90.5$ | $\mathbf{91.3}$ | $\mathbf{91.4}$ | $\mathbf{92.6}$ | $\mathbf{84.1}$ | $88.8$ | $59.5$
LoRA [26] | 0.04 | $70.76$ | $89.02$ | $89.4$ | $89.27$ | $92.2$ | $80.27$ | $\mathbf{88.89}$ | $59.08$
SURM (Kronecker) | 0.04 | $70.04$ | $89.06$ | $90.54$ | $89.35$ | $91.74$ | $80.41$ | $88.74$ | $\mathbf{59.6}$
SURM (Toeplitz) | 0.04 | $\mathbf{72.56}$ | $\mathbf{91.04}$ | $89.65$ | $89.67$ | $92.14$ | $80.93$ | $88.77$ | $58.05$
SURM (Circulant) | 0.04 | $71.14$ | $90.48$ | $89.91$ | $89.83$ | $92.2$ | $80.6$ | $88.76$ | $59.16$

###  B.3 Comparison of SURM Kronecker Adaptations with Baselines

As mentioned earlier, adaptation using Kronecker product is not new and has
been investigated in several works [50, 21, 24]. In both [50] and [24], the
authors use the Kronecker decomposition of the weight matrix (in the first
case, the weight matrix belongs to an adapter layer and in the second case the
weight matrix refers to updates as in the case of LoRA). Write
$\mathbf{W}=\sum_{i=1}^{n}\mathbf{A_{i}}\otimes\mathbf{B_{i}}$. Furthermore,
the authors assume that $\mathbf{B_{i}}$ is low rank and can be written as
$\mathbf{B_{i}}:=\mathbf{u}_{ij}\mathbf{v}^{\top}_{ij}$. The weights
$\mathbf{A_{i}}$ can also be assumed to low weights or be shared among various
layers leading to substantial efficiency gains. Our method is a simplified
version of the above where $n=1$. Other main difference between the above
methods and ours are : the matrices considered in the above works are square
matrices whereas they are almost never square unless the dimension of the
transformer is a perfect square and is set up such that the number of
parameters are reduced while the rank is as high as possible, contrary to the
above. Similar considerations of low rank factors in tensor decomposition are
also used in [29]. 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 versatility across both vision and language. Moreover, we present
this approach as an example of a 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 of 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 as ViT models fine-tuned on CIFAR10, CIFAR100, and ImageNet. Moreover, we
simulate a high-rank LoRA setting on GLUE where we freeze all the weights
excepts except for $\mathbf{Q},\mathbf{K},\mathbf{V}$. In that scenario, we
manage to 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 [58]. 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 [48]
studies the intrinsic dimensions of various self-supervised image models.
Comparing their results with that of fully supervised ViT models, we observe
that the self-supervised models exhibit slightly higher IDs. This is not
surprising as the SSL encourages the representations to 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) [72].

Figure 14: Left: Cosine similarity between the query matrices and Right:
cosine similarity between value matrices for the BERT model on MRPC dataset.

Encouraged by this analysis, we next 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 our trained
matrices are of rank 576. For rational circulant matrices $\mathbf{C}$, the
non-singularity of such matrices is related to divisibility by cyclotomic
polynomials. More generally, if we denote by $\mathbf{c}=(c_{0},..c_{n-1})$
the first column of $\mathbf{C}$, then:

$\mathrm{det}(\mathbf{C})=\prod_{j=0}^{n-1}\left(c_{0}+c_{1}\omega_{j}+c_{2}\omega_{j}^{2}+\cdots\
c_{n-1}\omega_{j}^{n-1}\right),$

where $\omega_{j}=e^{\frac{2\pi\mathbf{i}j}{n}}$ and $\mathbf{i}^{2}=-1$ (for
more details see [14]). This fact allows us to efficiently test for the non-
singularity of the circulant matrices. In all our cases, we found our matrices
to be non-singular. Regarding Toeplitz matrices, there is a large body of
literature that discusses the inversion of such matrices (see Appendix A.6).
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 ($\hat{\mathbf{W}}=\mathbf{W}+\alpha\Delta\mathbf{W}$) and
$\mathbf{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 ($\mathbf{W}$).

We test our hypothesis on the BERT model finetuned on the MRPC dataset by
SURMas well as by LoRA. We report the (1-cosine
similarity($\hat{\mathbf{W}},\mathbf{W}$)) for both query and key across
multiple layers (see Fig 14). We see that LoRA-learnt 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 [87].

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?

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

We evaluate the CKA similarity [37] 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 1, 2, 3). Moreover, in the low data regime,
it 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 a factor of 2. The gradients allow for a very
simple formula, which is computed in sub-quadratic time (see eq 14 in [15] for
the circulant matrix and Proposition 3.6 in [64] for the Toeplitz matrix).
Therefore, our general recommendation to practitioners is to use the circulant
variant of SURM. It is relatively fast and our most accurate variant.

##  Appendix C Broader Impact & Limitations

Fine-tuning large pre-trained Transformers for downstream tasks requires
substantial computational resources. We hope that this work addresses this
important problem by reducing the overall computational 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 methods. Despite their theoretical speed advantage, popular methods like
LoRA have been extensively optimized by the machine learning community for
efficient execution on hardware.