Structured Unrestricted-Rank Matrices for Parameter Efficient Finetuning

We would like to sincerely thank the Reviewer for their very valuable feedback and comments.

Studies on larger tasks:

One of the key things that we showed in our experiments was the improved performance in the low data regime. Specifically across a plethora of low-resource image experiments (VTAB-1K) we have shown the improved performance of SURMs (circulant). The NLP experiment on Glue was provided to showcase the ability of SURMs to extend to other modalities (text) and another class of small parameter models (adapters). We will make it more clear in the paper.

Choice of hyperparameters:

Datasplit: For vit-image experiments (table 1) we used the standard dataset split in tensorflow tfds datasets (https://www.tensorflow.org/datasets). VTAB-1K provides its own split and code which we used (github). For image segmentation we used the same split as the Segment-Anything-Model (SAM) [33]. For Glue we used the standard train/dev split (https://gluebenchmark.com/).

How the hyperparameters are chosen

All hyperparameters are tuned on training/val set and numbers are reported on separate test set. We will update the manuscript with this information.

Thanks for pointing out the typo in the caption of Figure 1. We will fix them.

Significance of Section 4.1: motivation, comparisons and conclusion

We apologize for the confusion. Our motivations for the two separate parts (left and right column of figure 4) are different. To save space we put these two experimental results together. Our motivation for the left column is to showcase the ability of general LDRs (defined in eq 2) to approximate various matrices i.e. random, low rank and low intrinsic rank and motivate our choice of LDRs with r=1. From the bottom two figures on the left (i.e. approximating low rank and low intrinsic rank with LDRs) we learn that LDRs (with r=1 and r=2) are great at reducing the approximation error (They are in the top 3 best approximating errors (lowest error)). This further provides motivation and empirical justification that LDRs with (r=1) may be well suited to approximate matrices with some structure.

The motivation for the right column is to compare and contrast the two variants of LDRs that we proposed i.e. circulant and Toeplitz.

Hence we should not be comparing the right with the left column. Please see the left and the right as its own set of experiments. In each figure, all techniques approximate the same matrix. The first set of results shown are after a single iteration hence the difference within the same figure. We can provide the left column experiments with a higher number of iterations but the objective is to discriminate among all the LDRs.

What is the pretraining data and task for the base ViT?

We used the vit-base model and the clip-base model from HuggingFace (https://huggingface.co/google/vit-base-patch16-224)

How is the data split into train, validation and test splits, and on which split are the results reported?

For vit-image experiments (table 1) we used the standard dataset split in tensorflow tfds datasets (https://www.tensorflow.org/datasets). VTAB-1K provides its own train/dev/test split and code for the same, which we used (github). For image segmentation, we used the same split as the Segment-Anything-Model (SAM) [33]. For Glue we used the standard train/dev split (https://gluebenchmark.com/). All numbers are reported on the test set (no hyperparameters were trained on. Thanks for pointing this out, we will update it in the manuscript

How and on which split are the hyperparameters tuned? Section E, lines 699-700 mention that the experiments use a learning rate of 5e-5, but SVHN uses 5e-4. How is this chosen?

For image classification experiments we used the same setup for all datasets except for SVHN where the training accuracy didn’t move much when using 5e-5 as the learning rate. All hyperparameters have been turned on the training/dev set while reported results are on the test set.

What is the difference between SURM (Circular) and SURM (Circular-LoRA/Adapter) (similarly Toeplitz and Kronecker) used in GLUE?

In the interest of saving space our detailed discussion regarding how SURMs can be used as Adapters has been moved to Appendix C. The difference between SURM(-LoRA) and SURM(-Adapters) is the setting under which low displacement rank matrices can be used. For example, circular-LoRa refers to using circulant matrices for lora style update ie $\hat{W} = W + \alpha \Delta W$ where $\Delta W$ is circulant (please see 5.1 for Lora style PEFT method). circular-Adapter implies using the adapter method for updating the model (please see equation 7 in section C in the Appendix). Our objective was to elaborate that both these styles of training can benefit from SURMs.

[33] Customized Segment Anything Model for Medical Image Segmentation, Zhang et al 2023.

[80] A large-scale study of representation learning with the visual task adaptation benchmark, Zhai et al. 2020.

Large data Regime

We investigate the performance of SURM in a large data regime using the iNat2021 [1] dataset. iNat2021 has over 2.7 million training images, 100K validation images, and 500K test images, representing a wide array of 10,000 species (classes).

Full fine-tuning: 69.98% vs SURM (circulant): 69.01%

We observe that SURM achieves similar results to full-finetuning using only 55K parameters as opposed to 86M in full fine-tuning. We will add these details to the manuscript.

[1] Benchmarking Representation Learning for Natural World Image Collections, Horn et al. 2021..

Large Model regime/Small data Regime

Thank you for the excellent comment. We present an example below where methods like LoRA and MoRA struggle to learn a complex task in a low data regime with a large-scale model.

Following the suggestion reviewer o41z, we created 10k pairs of UUIDs and tested the memorization capability of LLMs. We use the large-scale Llama-2-7B model [2]. The goal of this experiment is to show that models struggle to learn out-of-distribution data when using low-rank updates. Since the pdf can not be updated, the results are presented below:

We observe that LoRA and MoRA struggle to fit the data (cross-entropy loss around 2.3) whereas our circulant variant achieves a loss of 0.97. In this experiment, we used a high rank=256 for both LoRA and MoRA, and modified the $Q, K, V$ parameters for all methods.

Furthermore, we show the effect of increasing the number of training parameters by using sums of products of circulant and skew-circulant matrices. A skew circulant matrix $S = (s\_{jk})\_{j,k=0}^{n-1}$ is said to be skew-circulant if $s\_{jk} = s\_{j−k}$ and $s\_{−l} = −s\_{n−l}$ for $1 \leq l \leq n − 1$. The motivation for using this particular sum of products comes from the approximation quality of such matrices (see Theorem 1 in [3]). This is evident in practice as circulant+skew-circulant variant obtains a loss=0 and converges much faster.

This result and our toy experiment (Figure 5) consistently show that low rank updates may struggle to fit various data regimes and that unrestricted-rank matrices may be required to alleviate this issue. SURMs solve this problem using structured matrices (keeping the parameter budget low) while allowing for arbitrary ranks.

We will add this result to the manuscript.

[2] MoRA: High-Rank Updating for Parameter-Efficient Fine-Tuning Jiang et al. 2024

[3] Structured Transforms for Small-Footprint Deep Learning Sindhwani et al. 2015

We would like to sincerely thank the reviewer for their valuable feedback and comments.

Structured matrices for low rank adaptation has previously, as noted in the paper Knoecker products have been in previous literature, while Circulant and Toeplitz structures are, to my knowledge, have not. Nevertheless, Structured matrix adaptation has been explored in several prior papers.

To the best of our knowledge, the entire class of low displacement rank matrices (LDRMs), a subclass of Structured Unrestricted-Rank Matrices (SURMs) have not been explored in the context of PEFT. This includes instantiation of LDRMs including Circulant and Toeplitz matrices. As described in line 131 in section 3, Kronecker is not necessarily an LDRM but admits to efficient matrix-vector multiplication and does fall under the general umbrella of SURMs. The key novelty is our proposal of LDR-SURMs as general approximators that are not restricted to low rank. This is further supported by our experimental results.

Motivation / Intuition / Justification for our proposed LDRMs

After intuitively noting the inability of LowRank approximation to capture higher order updates, we have explicitly (empirically) shown in Introduction Figure 1 (right) that Toeplitz and Circulant matrices do a better job of approximating a PSD matrix as compared to LowRank matrices. It is well known that finetuning updates are full rank. Our motivation is further supported by section 4.1 which clearly shows the higher approximation ability of circulant and Toeplitz matrices. Moreover in section 4.2 we have specifically focused on the approximation quality of low rank matrices vs SURM and clearly show the advantages of LDRMs.

We believe that we have provided sufficient intuition and motivation (empirically) for the use of LDRMs in particular and SURMs in general.

Experimental evidence in support of LDRMs We would like to emphasize that we've presented extensive experimental evidence showcasing the efficacy of SURMs.

First, we compared SURMs on 6 datasets and compared our methods against 12 strong baselines. There are several analyses in the small data regime.

Second, we have included results for CLIP models and a comparison on the VTAB-1K [80] benchmark, which is designed to evaluate models on diverse tasks using few examples.

Third, we further have applied our work on Image segmentation and shown that we are comparable with specialized architectures developed for SOTA on image segmentation.

Overall, these sets of experiments demonstrate the utility of LDRMs especially in the low data regime.

SoTa baselines for low resource setting/smaller vision datasets.

We would like to point out that VTAB-1k datasets [80], which is designed to evaluate models in the low-resource regime. We report the baseline numbers from [29] and [49], which are the current state-of-the-art. Similarly for image segmentation tasks (table 3) SAMed[33] is a dedicated SoTa model trained for image segmentation tasks. These results show that SURM-based finetuning obtains the SOTA performance on several benchmarks.

What are the ranks of the other adapters used?

We report the adapter baseline performances from their respective papers and their rank is 48.

Why do you only test against rank 1 lora in Table 3?

SAMed [33] is an adaptation of Lora with higher rank (rank 4, the details are mentioned in Appendix E)

What how does the technique's performance change with rank?

Our Circulant/Toeplitz matrices are not parameterized by rank. We have explored two ways in which the number of parameters can be increased for circulant matrices. a) $C = \sum_i a_i C_i$ where each $C_i$ are circulant and b) $M = \prod_i M_i$ where $M_i$ are Toeplitz (line 140.) with a modest boost in performance but at the cost of speed. We will add these details in the supplementary.

Interestingly we found that the circulant and Toeplitz updates to be full rank and that the Kronecker updates to the maximum possible rank (see Appendix A)

Why might we expect these structures to perform better than other structured matrices?

We have motivated the use of structured matrices other than low rank by showcasing how certain structures like PSD are better approximated by LDRs. Moreover, in section 4 we have empirically shown that in multiple scenarios LDRs perform better than low rank matrices.

results on larger datasets

ImageNet results are presented in Table 7 (appendix H). In that case, our method compares favorably to full finetuning where we use only a negligible fraction of training parameters.

[29] Fact: Factor-tuning for lightweight adaptation on vision transformer. Jie et al 2023

[33] Customized Segment Anything Model for Medical Image Segmentation, Zhang et al 2023.

[49] Towards efficient visual adaption via structural re-parameterization. Luo et al 2023

[80] A large-scale study of representation learning with the visual task adaptation benchmark, Zhai et al. 2020.

Large Model regime/ UUID Experiments

Thank you for suggesting the UUID experiment and revising your score. Following [1], we created 10k pairs of UUIDs and we tested the memorization capability of the Llama-2-7b model. the results are presented below:

We observe that LoRA and MoRA struggle to fit the data (cross-entropy loss around 2.3) whereas our circulant variant achieves a loss of 0.97. In this experiment, we used a high rank=256 for both LoRA and MoRA, and modified the $Q, K, V$ parameters for all methods.

Furthermore, we show the effect of increasing the number of training parameters by using sums of products of circulant and skew-circulant matrices. A skew circulant matrix $S = (s\_{jk})\_{j,k=0}^{n-1}$ is said to be skew-circulant if $s\_{jk} = s\_{j−k}$ and $s\_{−l} = −s\_{n−l}$ for $1 \leq l \leq n − 1$. The motivation for using this particular sum of products comes from the approximation quality of such matrices (see Theorem 1 in [2]). This is evident in practice as circulant+skew-circulant variant obtains a loss=0 and converges much faster.

This result and our toy experiment (Figure 5) consistently show that low rank updates may struggle to fit various data regimes and that unrestricted-rank matrices may be required to alleviate this issue. SURMs solve this problem using structured matrices (keeping the parameter budget low) while allowing for arbitrary ranks.

We will add this result to the manuscript.

[1] MoRA: High-Rank Updating for Parameter-Efficient Fine-Tuning Jiang et al. 2024

[2] Structured Transforms for Small-Footprint Deep Learning Sindhwani et al. 2015

Large data Regime

We investigate the performance of SURM in a large data regime using the iNat2021 [3] dataset. iNat2021 has over 2.7 million training images, 100K validation images, and 500K test images, representing a wide array of 10,000 species (classes).

Full fine-tuning: 69.98% vs SURM (circulant): 69.01%

We observe that SURM achieves similar results to full-finetuning using only 55K parameters. We will add these details to the manuscript.

[3] Benchmarking Representation Learning for Natural World Image Collections, Horn et al. 2021.

Please let us know if you have any questions.

Thank you to the authors for the follow-up experiments and the detailed conversations. I believe that with the new experiments added to the paper and the following, the paper should be accepted.

1. Please add a sentence more information on how we change the number of parameters in this formulation (Skew-Circulant etc...)
2. Please discuss, as a hypothesis which lends itself to future work, why it is that this method seems to perform well at both low data and high data regimes. This is a bit counterintuitive to me.
3. Please address the limitations of this technique a bit more in-depth and when we expect this technique to perform worse than others.

With the changes already presented, and the integration of the above points. I have raised my score to a 6 due to the strong cooperation of the authors towards providing additional information, experiments etc.. and the additional strong results and recommend acceptance.

We would like to sincerely thank the Reviewer for their very valuable feedback and comments.

NLP experiments:

We'd like to emphasize the breadth and depth of experimental evidence we have provided for SURMs. First, we compared SURMs on 6 image classification datasets and compared our methods against 12 strong baselines. Furthermore, we have evaluated on the VTAB-1K[80] benchmark. VTAB-1K is designed for low resource settings to evaluate models on “diverse, unseen tasks with few examples”, see abstract from [80]. Across multiple low resource settings we find that circulant works better than all prior proposed methods. This is a key contribution of our work. We further have applied our work on Image segmentation and shown that SURM is comparable with specialized architectures developed for SoTa on image segmentation. Thus our experiments demonstrate the effectiveness of LDRMs especially in the low data regime. The results on GLUE are to showcase that SURMs can be extended to other modalities (text) and different modeling regimes (adapters). We will make this more clear in the manuscript.

[80] A large-scale study of representation learning with the visual task adaptation benchmark, Zhai et al. 2020.

Large data Regime

We investigate the performance of SURM in a large data regime using the iNat2021 [1] dataset. iNat2021 has over 2.7 million training images, 100K validation images, and 500K test images, representing a wide array of 10,000 species (classes).

Full fine-tuning: 69.98% vs SURM (circulant): 69.01%

We observe that SURM achieves similar results to full-finetuning using only 55K parameters as opposed to 86M in full fine-tuning.. We will add these details to the manuscript.

[1] Benchmarking Representation Learning for Natural World Image Collections, Horn et al. 2021..

Large Model regime

Following the suggestion reviewer o41z, we created 10k pairs of UUIDs and tested the memorization capability of LLMs. We use the large-scale Llama-2-7B model [2]. The goal of this experiment is to show that models struggle to learn out-of-distribution data when using low-rank updates. Since the pdf can not be updated, the results are presented below:

We observe that LoRA and MoRA struggle to fit the data (cross-entropy loss around 2.3) whereas our circulant variant achieves a loss of 0.97. In this experiment, we used a high rank=256 for both LoRA and MoRA, and modified the $Q, K, V$ parameters for all methods.

Furthermore, we show the effect of increasing the number of training parameters by using sums of products of circulant and skew-circulant matrices. A skew circulant matrix $S = (s\_{jk})\_{j,k=0}^{n-1}$ is said to be skew-circulant if $s\_{jk} = s\_{j−k}$ and $s\_{−l} = −s\_{n−l}$ for $1 \leq l \leq n − 1$. The motivation for using this particular sum of products comes from the approximation quality of such matrices (see Theorem 1 in [3]). This is evident in practice as circulant+skew-circulant variant obtains a loss=0 and converges much faster.

This result and our toy experiment (Figure 5) consistently show that low rank updates may struggle to fit various data regimes and that unrestricted-rank matrices may be required to alleviate this issue. SURMs solve this problem using structured matrices (keeping the parameter budget low) while allowing for arbitrary ranks.

We will add this result to the manuscript.

[2] MoRA: High-Rank Updating for Parameter-Efficient Fine-Tuning Jiang et al. 2024

[3] Structured Transforms for Small-Footprint Deep Learning Sindhwani et al. 2015

Dear Reviewer GJ7U,

We would like to once more sincerely thank you for all the comments and very useful feedback. We think that we have addressed in depth all Reviewer's questions. Please let us know. If the Reviewer has any additional questions, we would be more than happy to answer them.

Yours sincerely,

The Authors

We sincerely thank the Reviewer for their valuable feedback and comments.

Any reasons why the proposed version w/ the Kronecker product outperforms the previous works, such as Kadaptation?

Kadaptation approximates the gradient update using: $\Delta W = \sum_{i=1}^n A_i \bigotimes B_i$ where $B_i$ is the outer product of two vectors (thereby is low rank) and $\bigotimes$ is the Kronecker product. In our case, we consider $n=1$ and do not require $A_i, B_i$ to be low rank. The uplift in accuracy also showcases the need to move away from low rank constraints on the $\Delta W$. These differences are more elaborated in Appendix F.

Why is PSD approximation accuracy a good proxy task? is the weight delta during finetuning close to PSD by any chance?

The update $\delta W$ weights are close to full rank and thus we used PSD as a proxy for it. Across multiple applications we find that the $\delta W$ after finetuning is full rank. We will add details regarding the rank of the update matrix for general finetuning.

As the author mentioned in the limitation section, there are many fancy accelerated implementations of LoRA. How slow is the proposed method compared to those LoRA implementations?

Theoretically (please see lines 122-130) we are faster with $O(n \log n)$ whereas LoRa is $O(n d)$. Practically the Circulant variant of SURM is at par with LoRA whereas Toeplitz is slower.

Large data Regime

We investigate the performance of SURM in a large data regime using the iNat2021 [1] dataset. iNat2021 has over 2.7 million training images, 100K validation images, and 500K test images, representing a wide array of 10,000 species (classes).

Full fine-tuning: 69.98% vs SURM (circulant): 69.01%

We observe that SURM achieves similar results to full-finetuning using only 55K parameters as opposed to 86M in full fine-tuning. We will add these details to the manuscript.

[1] Benchmarking Representation Learning for Natural World Image Collections, Horn et al. 2021..

Large Model regime

Following the suggestion reviewer o41z, we created 10k pairs of UUIDs and tested the memorization capability of LLMs. We use the large-scale Llama-2-7B model [2]. The goal of this experiment is to show that models struggle to learn out-of-distribution data when using low-rank updates. Since the pdf can not be updated, the results are presented below:

We observe that LoRA and MoRA struggle to fit the data (cross-entropy loss around 2.3) whereas our circulant variant achieves a loss of 0.97. In this experiment, we used a high rank=256 for both LoRA and MoRA, and modified the $Q, K, V$ parameters for all methods.

Furthermore, we show the effect of increasing the number of training parameters by using sums of products of circulant and skew-circulant matrices. A skew circulant matrix $S = (s\_{jk})\_{j,k=0}^{n-1}$ is said to be skew-circulant if $s\_{jk} = s\_{j−k}$ and $s\_{−l} = −s\_{n−l}$ for $1 \leq l \leq n − 1$. The motivation for using this particular sum of products comes from the approximation quality of such matrices (see Theorem 1 in [3]). This is evident in practice as circulant+skew-circulant variant obtains a loss=0 and converges much faster.

This result and our toy experiment (Figure 5) consistently show that low rank updates may struggle to fit various data regimes and that unrestricted-rank matrices may be required to alleviate this issue. SURMs solve this problem using structured matrices (keeping the parameter budget low) while allowing for arbitrary ranks.

We will add this result to the manuscript.

[2] MoRA: High-Rank Updating for Parameter-Efficient Fine-Tuning Jiang et al. 2024

[3] Structured Transforms for Small-Footprint Deep Learning Sindhwani et al. 2015

Dear Reviewer aa5x,

We would like to once more sincerely thank you for all the comments and very useful feedback. We think that we have addressed in depth all Reviewer's questions. Please let us know. If the Reviewer has any additional questions, we would be more than happy to answer them.

Yours sincerely,

The Authors