Parameter-Efficient Orthogonal Finetuning via Butterfly Factorization
Authors: Weiyang Liu
Zeju Qiu
Yao Feng
Yuliang Xiu
Yuxuan Xue
Longhui Yu
Haiwen Feng
Zhen Liu
Juyeon Heo
Songyou Peng
Yandong Wen
Michael J. Black
Adrian Weller
Bernhard Schölkopf
Venue: ICLR 2024 poster (2024)
Keywords: Parameter-efficient finetuning
orthogonal
Butterfly matrix
Primary area: transfer learning, meta learning, and lifelong learning
TL;DR: A simple yet effective finetuning method for the adaptation of foundation models

Abstract: Large foundation models are becoming ubiquitous, but training them from scratch is prohibitively expensive. Thus, efficiently adapting these powerful models to downstream tasks is increasingly important. In this paper, we study a principled finetuning paradigm -- Orthogonal Finetuning (OFT) -- for downstream task adaptation. Despite demonstrating good generalizability, OFT still uses a fairly large number of trainable parameters due to the high dimensionality of orthogonal matrices. To address this, we start by examining OFT from an information transmission perspective, and then identify a few key desiderata that enable better parameter-efficiency. Inspired by how the Cooley-Tukey fast Fourier transform algorithm enables efficient information transmission, we propose an efficient orthogonal parameterization using  butterfly structures. We apply this parameterization to OFT, creating  a novel parameter-efficient finetuning method, called Orthogonal Butterfly (BOFT). By subsuming OFT as a special case, BOFT introduces a generalized orthogonal finetuning framework. Finally, we conduct an extensive empirical study of adapting large vision transformers, large language models, and text-to-image diffusion models to various downstream tasks in computer vision and natural language. The results validate the effectiveness of BOFT as a generic finetuning method.

Published as a conference paper at ICLR 2024
PARAMETER-EFFICIENE ORTHOGONAL FINETUNING VIA BUTTERFLY FACTORIZATION
Weiyang Liu! Zeju Qiu" Yao FenglAt Yuliang Xiu Zhen Liu Juyeon Heo Songyou Peng Yandong Wen'
Yuxuan Xue
Longhui Yu
Haiwen Feng'
Michael Black'
Adrian Weller2# Bernhard Schölkopf'
Max Planck Institure for Intelligent Systems- Tübingen University of Tübingen 'Mila, Université de Montréal
University of Cambridge
'ETH Zürich
"The Alan Turing Institute
boft boft.wyliu. com
ABSTRACT
Large foundation models are becoming ubiquitous, but training them from scratch is prohibitively expensive. Thus, efficiently adapting these powerful models downstream tasks is increasingly important. In this paper, we study a principled finetuning paradigm Orthogonal Finetuning (OFT) - for downstream task adap- tation. Despite demonstrating good generalizability. OFT still uses a fairly large number of trainable parameters due to the high dimensionality of orthogonal matri- ces. To address this, we start by examining OFT from an information transmission perspective, and then identify few key desiderata that enable better parameter- efficiency. Inspired by how the Cooley-Tukey fast Fourier transform algorithm enables efficient information transmission, we propose an efficient orthogonal parameterization using butterfly structures. We apply this parameterization to OFT, creating a novel parameter-effice fly (BOFT). By subsuming OFT special case, BOFT introduces generalized orthogonal finetuning framework. Finally, we conduct an extensive empirical study of adapting large vision transformers, large language models, and text-to-image diffusion models to various downstream tasks in vision and language.
finetuming method, called Orthogonal Butter-
INTRODUCTION
Recent models such as ChatGPT [4, 9] and Stable Diffusion [73], demonstrate the remarkable generalization ability of large foundation models. The rapid increase in the performance of such models is paired with dramatic increase in the number of parameters (e.g., GPT-3 has around 175B parameters). As a result, it has become increasingly challenging for researchers to train a foundation model from scratch. Broad progress in the field therefore requires the ability to adapt such models without retraining them from scratch. That is, we must be able to efficiently adapt existing foundation models to downstream tasks. There are primarily three ways to perform efficient task adaptation: model finetuning [6, 23, 29, 67, 69, 92, 97], where the model architecture remains unchanged and a subset of the model parameters gets finetuned; adapter tuning [24, 28, 48, 65, 71], where additional
trainable parameters are added to the original model; and prompt tuning [39, 42], where additional trainable prefix tokens are attached to the input. Among these methods, model finetuning distinguishes itself as a simple yet powerful approach, and more importantly. introduces no inference latency.
The fundamental principle behind model finetuning is to ensure that the pretrained model and the finetuned model are similar based on certain measurements, such that the pretraining knowledge is preserved. For instance, current model finetuming methods often adopt a small learning rate. This ad hoc approach encourages a small discrepancy between the pretrained and the finetuned model. Given the structured nature of weight matrices, more principled approach tries to preserve the relational information of the weight matrices, i.e. the pairwise angles between neurons. This insight leads to a novel model finetuning framework, known Orthogonal Finetuning (OFT) [67], where neurons in the same layer are transformed by the same orthogonal matrix such that pairwise angles between neurons provably preserved throughout the finetuning process. Although OFT has demonstrated promising generalizability and convergence for finetuning text-to-image diffusion models [67], the number of trainable parameters in OFT can be quite large due to the high dimensionality of orthogonal matrices. To address this, OFT introduces a block-diagonal structure to reduce the number of parameters. However, the parameter efficiency also comes a price the orthogonal matrix has fixed sparsity pattern and the orthogonal transformation is applied independently in different blocks. This block-
"qqual first author contribution. 'Equal second author contribution. Equal contributors are listed alphahetically.

---

Published as a conference paper at ICLR 2024
diagonal sparsity pattern, despite saving parameters, may introduce some undesirable inductive biases (e.g., the diogo-liagonal orthogonal matrix reduces expressiveness and cannot approximate classic linear transforms), and more importantly, how to find good sparsity pattern remains mystery.
The key to addressing this problem is to generate dense orthogonal matrix. while still being parameter-efficient. While this may seem infeasible at first glance since a d-dimensional dense orthogonal matrix requires (c22) parameters, matrix with multiple factorized sparse matrices. This approach is guided by the insight that the number of trainable parameters can be reduced by trading computation time for space. Since we represent the orthogonal matrix with the multiplication of sparse matrices, the multiplication has to be performed repeatedly in each training iteration. To put the matrix factorization into perspective, we interpret the generation of a dense orthogonal matrix as an information transmission problem. Under this problem formulation, generating dense orthogonal matrix by multiplying sparse matrices can be understood as transmitting information on grid-structured graph. This information transmission framework enables us to design many possible ways to perform sparse matrix factorization that limit the number of trainable parameters while still being expressive enough to generate dense matrices.
take novel route to compose dense orthogonal
To achieve parameter efficiency in our information transmission framework, we draw inspiration from the butterfly structures in the Cooley-Tuke Tukey fast Fourier transform algorithm [12] in which information from different nodes can be exchanged efficiently [36]. Specifically, the butterfly graph in the Cooley-Tukey algorithm inherently induces a way to perform sparse matrix factorization, called butterfly factorization. With butterfly factorization, we able to generate d-dimensional dense matrix with a product of (log d) sparse matrices, each with (d) non-zero entries. By ensuring that each sparse matrix is orthogonal, only (dl log d) parameters, which is a significant reduction from the original parameterization. By leveraging such efficient orthogonal parameterization, we propose novel parameter-efffciient finetuning method- - Orthogonal Butterfly (BOFT). BOFT subsumes OFT as a special case and provides a general orthogonal finetuning framework. There a shared characteristic for the block- diagonal structure and the butterfly structure sparsity. Both structures introduce data sparsity into orthogonal matrices reduce the effective number of trainable parameters. is interesting to contrast our approach with the low-rank structure in LoRA [29]; both low-rank matrices and sparse matrices are major families of structured matrices [5] that achieve parameter efficiency.
arrive at an efficient orthogonal parameterization with
Compared the block-diagonal structure that OFT uses to trade off expressivity and regularity, BOFT uses the butterfly structure to construct smoother interpolation between matrices from the full orthogonal group (expressivity) and identity matrices (regularity). This enables us to find smaller hypothesis class within the orthogonal group for downstream tasks. Given the widespread use of the butterfly structure in many fast lincar transforms, such as the discrete Fourier and discrete cosine transforms, we argue that our structured approach parameter efficiency will introduce an implicit inductive bias that benefits generalizability and prevents overfitting. Our intuition comes from the property that the butterfly structure can easily recover many classic linear transforms while it is impossible for the block-diagonal structure in OFT to recover any. Our contributions are listed below:
We study the problem of parameter efficiency in orthogonal finetuning with a novel information transmission framework. This framework transforms the task of crafting a parameter-effiiien dense orthogonal matrix into an information transmission problem within a grid-structured graph.
Inspired by the butterfly structures in the Cooley-Tukke algorithm, we propose Orthogonal Butterfly, efrfiette-effficiettt orthogonal finetuming method, within the information transmission framework.
We provide few theoretical insights for why BOFT is able to significantly reduce the number of trainable parameters while still yielding a good expressivity and training stability. Thanks to the matrix factorization, BOFT also comes with an intriguing weight interpolation (see Figure 10).
For the very first time, we apply orthogonal finetuning to various tasks beyond controllable text- to-image generation [67]. showing its great potential as a generic model finetuning method. To this end, we apply BOFT to number of adaptation applications ranging from computer vision to natural language processing. BOFT outperforms current ofate-of-the-art methods by a considerable margin, validating its superior parameter-effiienccy and generalization ability.
2 RELATED WORK
Parameter-efficient finetuning (PEFT). As foundation models (e.g.. [4, 35, 68, 73]) become increasingly large and powerful, finetunig these models for downstream tasks in a parameter-effiiient
2

---

Published as a conference paper at ICLR 2024
way has sparked considerable interest [18, 45, 82]. Among many PEFT methods [1, 3, 8, 10, 19, 21, 23, 24, 28-31, 33, 39, 42, 46, 49, 54, 56, 78, 79, 86, 88, 92, 98]. reparameterizztion based methods [1, 19, 29] are the most relevant to our work. LoRA [29] updates the pretrained weight matrix by adding a product of two low-rank matrices, achieving promising performance on natural language tasks. Since the rank of all added matrices is set to constant in LoRA, several methods [84, 95, 97] dynamically adjust the rank for different layers such that the parameter budget is adequately allocated. Due to its simplicity, such low-rank weight reparameterization has gained great popularity [6, 16, 102]. Inspired by how hyperspherical energy characterizes generalization [50, 52], [67] proposes orthogonal finetuning, an alternative yet effective method to finetune text-to-image diffusion models. Specifically, OFT learns an orthogonal matrix to transform the neurons of the same layer, and it achieves stronger generalization and consistently more stable training than LoRA. Despite strong performance, OFT generally has more trainable parameters than LoRA. Therefore, making OFT more parameter-efficient is a useful goal. Moreover, whether OFT is applicable to wider spectrum of adaptation tasks (beyond controlling text-to-image diffusion models [67]) is unknown. BOFT improves the parameter efficiency of OFT via butterfly factorization. Thanks to this, are now able demonstrate the power of orthogonal finetuning in general adaptation tasks.
Butterfly structures. The radix-2 Cooley-Tuker algorithm recursively reduces the N N-point discrete Fourier transform to two N1 -point discrete Fourier transforms, and this process induces a butterfly structure that can be written as a product of multiple sparse matrices (the product is also called a butterfly matrix). Butterfly matrices have already been used to parameterize orthogonal matrices to avoid pivoting in Gaussian elimination and improve efficiency [63]. to stabilize the training of recurrent neural networks [32] and in kernel approximation [60]. [13, 14] learn fast linear transforms with butterfly parameterizations. [7, 15] utilize butterfly matrices to enable the efficient training of neural networks. Butterfly structures are also found useful in fast matrix-vector multiplication [57, 61], data-sparse matrix approximation [43], and network transmission [36, 40, 70J. In contrast to previous work, we focus on harnessing butterfly structures to enhance the parameter efficiency of OFT.
3 AN INFORMATION TRANSMISSION VIEW ON ORTHOGONAL FINETUNING
We start with some preliminaries of OFT. To finetune the pretrained weight matrix, OFT reparameter- izes the new weight matrix as the product of a learnable orthogonal matrix and the frozen pretrained weight matrix. Compared to LoRA which updates the weights with an additive low-rank matrix, OFT uses a multiplicative orthogonal matrix to update the weights. To achieve parameter-efficienng LoRA uses a low-rank structure, and in contrast, the original OFT uses a block-diagonal orthogonal structure [67] (the smaller the size of diagonal blocks is, the more parameter-efficiee
Pretrained Weight Matrix 1*
B
X
Pretminedd Weight Matris N
Orthogonal Matrx
Low-rank Matrix
AB
(a) Low-rank Structure in LoRA
(b) Orthogonal Structure in OFT
Figure I: compurison of reparameterization between LoRA and OFT.
OFT is). An intuitive comparison is given in Figure 1. The motivation for applying orthogonal transformation to finetune the weight matrix is to preserve the pair-wise angles of neurons [50, 52, 67], such that the semantic knowledge from pretraining can be largely preserved. Concretely, OFT optimizes an orthogonal matrix R E Rdxd for a pretrained linear layer W E Rdxn, and modifies the forward pass from z (W") x to where æ E Rd and x E R" are the input and output vector, respectively. To achieve zero initialization, OFT initializes R as identity matrix. To ensure the orthogonality of R throughout the finetuning process, we follow [52, 67] to employ Caylcy parameterization, i.e., R = (I + Q) - Q) the block-diagonal
(RW') x.
where Q is skew-symmetric matrix with Q QQ For parameter-efficienet structure is introduced by parameterizing the orthogonal matrix R as diag( R, R2,... R..) where R; Rxxb Vi is a small orthogonal matrix and br d. The parameter-efficienge brought by the block-diagonal structure comes at a price - it introduces an assumption that the dimensions of a neuron (i.e., a column vector of the weight matrix Wo) are divided by groups and dimensions in different groups are transformed separately using different orthogonal matrices. Despite the empirical effectiveness of the block-diagonal structure, makes no sense to divide the dimensions of a neuron into r groups based on their indices, which makes dense orthogonal matrices desirable. A natural question arises: Can we construct dense orthogonal matrix without losing the parameter-efficiencyy
To address this question, we propose to compose a dense orthogonal matrix with product of multiple sparse orthogonal matrices. To provide a unified yet intuitive perspective to study the sparsity pattern
3

---

Published as a conference paper at ICLR 2024
of orthogonal matrix factorization, frame the
6
Level
Level
Level
Level
problem of generating a dense orthogonal matrix in
OFT an information transmission problem. Specif- ically, generating a dense matrix R E Rdxd by a product of m square matrices R B,,. B can be viewed as transmitting information in a grid with d (m-+1) nodes, as illustrated in Figure 2. The motivation behind the information transmission view comes from the observation that a d-dimensional dense square matrix can be interpreted as a dense connectivity from d nodes to another nodes. For the matrix R. if the element Ray is zero, then it indicates that information from the j-th node can- not flow to the i-th node. If Rig is non-zero, then the information can be transmitted. Therefore, rep- resenting the dense matrix R with multiple matrices Bm. Bn- Bj can also be interpreted as perform- ing sequential information exchange based on the graphs induced by B,, Vi. The information flows following B, first and B., in the end. As a concrete example in Figure 2, we consider the factorization R B3 whose sparsity patterns and induced graph are visualized. The graph in Fig- ure 2 is the result of unrolling the matrix multiplication. In the induced graph, the matrix B, is viewed as the connectivity matrix from the i-th level nodes to the (i 1- level nodes. More specifically, the (2) element of B; denotes whether there is a directed edge from the f2-th node in the i-th level to the ji-th node in the (i + 1) level (zero means no edge). For B; Bg Bg By to be a dense matrix, every node in the first level should be able to transmit information to all the nodes in the 6-th level. If we only consider R = B, By which corresponds to the source nodes in the first level and the receiver nodes in 5-th level, then find that information from the node cannot be transmitted to the node 3. Therefore, the sparsity pattern of B B,BB has a zero element at the (3, 1) position. Considering R B3B, B1 and R B₂B,, the same correspondence holds between the induced graph and the sparsity pattern. Generally, for a matrix R e IRdx to be dense, the m factorization matrices Bm.-.. B₁ needs to correspond one directed edge can only connect two nodes between adjacent levels (i.e., columns), such that information from every node in the first level can be transmitted to every node in the (m + 1)-th level.
B
B
B
8
B
B.B.B.B.B.
B.B.B.B.
B.B.B.
B-B.
Zero
Non-2ero
Figure An illustration the information transmission view on generating dense matrices. This example uses 4 and
set of directed edges on d (m + 1) grid where
The information transmission view can help us gain better understanding of the sparsity pattern of factorization matrices OFT. Figure 3 visualizes the block-diagona, structure of R in the original OFT. Despite reducing the number of trainable parameters, the block-diagonal structure cannot construct dense matrix R. Our goal is to compose dense orthogonal matrix with m sparse orthogonal matrices, using as few effective trainable parameters as possible. Under the information transmission view, the general desiderata towards our goal are (i) dense connectivity: every node in the first level has at least one path to every node in the last level, and (ii) minimum free edges: the total number of edges should be as small as possible under the orthogonality constraint. We note that orthogonality injects a delicate constraint the edges between adjacent levels. For example, for each matrix B, to be full-rank (a necessary condition of orthogonality), we need to have d edges to form a bijection between all the nodes in the i-th level and all the nodes in the (i = 1)-th level, which makes the number of edges between adjacent levels at least d (e.g.. 4 for the example in Figure 2). These d edges is necessary for orthogonality and should not be counted into the number of edges, because these elements are not trainable (e.g., for d x d orthogonal with d non-zero entries, these entries can only be +)). Because orthogonal matrices require less number of parameters than full matrices, the orthogonality constraint will bring in additional dependency among edges. As an example, for a 2 x 2 orthogonal matrix, one zero at the (1, 1) position will imply another zero at the (2, position (i.e., one missing edge could imply another missing edge). Therefore, for each feasible set of edge connections, the orthogonality may sometimes add or remove some edges. By visualizing the non-zero pattern of the composed orthogonal matrix, the information transmission framework is particularly useful in OFT, because only care about the non-zero trainable elements of R and their specific values do not matter.
Figure 3: An example of block- diugonal structure in OPT.
A naive dense connection between two levels takes (dd)) edges (i.e., single dense orthogonal matrix), yielding d² - dl edges (for d = 4, it is 12 edges). Figure 2 gives an example of feasible matrix
4

---

Published as a conference paper at ICLR 2024
factorization and it takes 10 edges in total, which is actually less than a single dense orthogonal matrix. This framework enables us to study the parameter-efficien efficiincfcfyyf of OFT from a graphical perspective, and easily come up with feasible factorizations with this framework. We draw inspiration from an interesting topology from the Cooley-Tuke
algorithm, called butterfly graphs [12], which can densely connect d source nodes and d receiver nodes efficiently with Od d) edges. For example, the topology in Figure 2 takes 10 edges to achieve dense connectivity, while the butterfly network only takes 8 edges. Next, we introduce how the butterfly structure can improve parameter efficiency.
4 ORTHOGONAL PARAMETERIZATION BY BUTTERFLY FACTORIZATION
The butterfly structure is originally used in the Cooley-Tukey al- gorithm to perform fast Fourier transform. In Fourier transform, a local change in the frequency domain can cause a global change in the spatial domain, which is conceptually similar to our information transmission problem every node in the first level can transmit information to all the nodes in the last level. The butterfly structure also becomes popular computer network topology [41, 75] used for efficient information exchange. Assuming that & 2 2 is power of 2, we start by defining the butterfly factor BF (ks) as
Level
Level 3
Level 2
Level
B f (1+
(iag(d1) diag(de (2)) (dag
E B.
(1)
diag(da)
where d, E 2 Vi are some vectors. With d = 2%N, we then define the d-dimensional butterfly matrix Bdd)= E Rdxd recursively as
Br8,8)
R(8,4)
Br8,2)
B1( (2( B(d, B)d, 2 B(d,2), (2)
((d) B(d,d)
O
where B, (g) and (5( are two & 4-dimensional butterfly matrices.
Figure 4: The butterfly strueture (d 8).
We then define the butterfly component as B k) diag (k), (k),..... ,B diagonal matrix of size d x d with the block size k, where B. (ke), vi are butterfly factors defined in Equation 1. Now we are ready to use the butterfly matrix to parameterize an orthogonal matrix. To achieve this, we only need to ensure that all multiplicative factors (d, k), Vk in the butterfly matrix (d)) are orthogonal. We first look into the block-diagonal matrix Bdd, 2) with the block size 2, and we can easily guarantee (dd, 2) to be orthogonal with Cayley transform (or 2-dimensional rotation) parameterize each block, same as [52, 67]. The non-zero pattern of every butterfly component can be viewed a permutation of the non-zero pattern of B (d. 2), all the butterfly components can be easily parameterized as orthogonal matrices. This gives us an efficient parameterization of orthogonal matrices built upon many 2 orthogonal matrices. We generalize the butterfly matrices following [7], and define block butterfly component (d,d, k) where each entry in d;, Vi becomes b x matrix. To guarantee the block butterfly component B (d. 2) to be orthogonal, we parameterize each 2b x 2b block matrix to be orthogonal. The non-zero pattern of the other butterfly components
that is block-
B¹ (d, k), k > 2 are the bisek-wise permutation of the non-zero pattern of B² 2) and therefore can be similarly turned into orthogonal matrices. Combining pieces, the forward pass in BOFT
m
(R(mm)) WO) xx s.t. R((, b) = II Blao & (Bia.)) Bia.) Bla,)
[jE[1.m)
Bia.,) for simplicity, and I is an identity matrix of size d. The orthogonal matrix R(m, b) Bdxd is composed of a product of multiple orthogonal butterfly components. For convenience, we denote BOFT with R(m, $) as BOFT(m,,), where b > 2. When m=1, then BOFT(1.)) reduces to the block diagonal OFT [67] with the block size b. BOFT(1.d) reduces to the original OFT [67] with an unconstrained full orthogonal matrix. BOFT 2d .b)
where denote
uses the block butterfly matrix B (d) as R, and yields a dense orthogonal matrix R. In general, BOFT(m,)) takes 1 (b- 1)dm effective trainable parameters for finetuning a linear layer of size d If we use the butterffy matrix, i.e., m = log d, b = 2, BOFT uses Odd d) parameters. In contrast, the original OFT with full dense orthogonal matrix uses (d2) parameters, and the block olockadiagonal OFT with the block number r uses (bd). Therefore, the original OFT has to use the block size b = d to generate dense orthogonal matrix, while BOFT can use any b to achieve this.
5

---

Published as a conference paper at ICLR 2024
Identity initialization for BOFT. Finetuning methods usually start with the exact pretrained model such that the finetuned model will not deviate too much from the pretrained one. For example, LoRA uses zero initialization for the low-rank weights. In BOFT, we initialize all the butterfly components with identity matrices (i.e., the skew-symmetrie matrix is initialized as zeros in Cayley transform).
Multiplicative Dropout for BOFT. LoRA [29] further implements a Dropout layer for the low-rank weight update to prevent overfitting. The conventional Dropout [77] naturally works for LoRA, but not for BOFT due to our multiplicative weight update. To address this, we propose a multiplicative Dropout for BOFT. Because the orthogonal matrix R(m, b) is composed of m orthogonal butterfly components which can be easily permuted to 26 x 2b block-diagonal orthogonal matrices. The multiplicative Dropout first randomly picks P1 percent of the butterfly components and p2 percent of the diagonal blocks in each butterfly component, and then replaces these blocks as identity matrices.
5 INTRIGUING INSIGHTS AND DISCUSSIONS
Expressivity of BOFT. The butterfly structure along with permutations can perfectly recover many classic fast linear transform [13, 14] (e.g.,
Scaled aapprese ee insttion crter
BOFTLLA
MO
fast Fourier transform, Hadamard transform), but how well our orthogo- nal butterfly matrix can approximate a general orthogonal matrix remains unknown. We start by conducting simulation approximate random dense orthogonal matrix [2] with size 512 x 512. The results in Figure 5 averaged over 10 random seeds. The y-axis denotes the approxi- mation error, and the x-axis denotes the number of effective trainable parameters. Each curve with the same color denotes BOFT with the same block size, and the leftmost point is the error of BOFT(1,)) (i.e., the original block-diagonal OFT with block size b). BOFT generally yields better parameter efficiency than OFT. For example, the expressiveness of (9,)( is better than that of B0FT(1,16) but has much less parameters, BOFT with smaller and larger m is generally more parameter-efficient. For example, ( uses much less parameters but yields a similar approximation error to BOFT(2, 16)). In general, the butterfly matrix represents a more structured subset of the orthogonal group (compared to the diagonal structure), which makes BOFT provably more expressive than OFT with the same block size.
0.5
SCF 209
ROFTH 9.2:
RORTERIT
0.
BOFFULS-)
0.5
1I
Number trainable parameters
Figure 5: Expressiveness of BOFF
Theorem (Expressivity of BOFT). BOFT is more expressive than OFT with the same block size. For the butterfly matrix to approximate all orthogonal matrices of size d, we can multiply butterfly matrices with B (d) B ( ... (1, B (d)), where (d), Vi, Vj are butterfly matrices.
(d),
Theorem suggests simple generalization for BOFT the final orthogonal matrix is generalized to (m,, b, M2, b2. 1) = Ra, (mn, bn) ) b2) ... R1, (m1, bn ) (m2, b2) where R R2,,( (m,,)) b) denotes the orthogonal matrix used in BOFT. When mn = m2 = log d, bj = b2 = and / = d 1. then RC(m1, b2, m2, 1) 1) can represent the entire orthogonal group. Such matrix composition is also called kaleidoscope hierarchy [14]. However, we note that better expressiveness does not always lead to better performance in finetuning, as full finetuning, despite its universal expressiveness, often yields unsatisfactory performance. The trade-off between expressivity and regularity is the key to the generalizability of model finetuning. BOFT enlarges the finetuning parameter space with structural priors, which enables us to find a better trade-off between expressivity and regularity.
Spectral properties. Orthogonal finetuning generally yiclds better spectral property than LoRA, because it perfectly preserves the spectral norm of the pretrained weight matrix W We can see this by singular value decomposition: W = UEV where U, V are orthogonal matrice and Σ is a singular value diagonal matrix. Both OFT and BOFT multiply an orthogonal matrix R to the left and obtain the finetuned weights RU VVT, which does not affect the largest singular value (i.e., the spectral norm of W Such a preservation has been shown to greatly benefit training stability and generalization [58, 90]. We introduce more interesting mathematical properties in Appendix G.
Orthogonal finetuning as learning bilinear similarity. BOFT can be written as learning the bilinear similarity oi Ra where wi is the i-th neuron (i.e., column vector) of the weight matrix W BOFT can be viewed as learning the bilinear similarity matrix R with strong regularity (i.e., R needs to be orthogonal), which intrinsically connects to distance metric learning [89] and bilinear form [72].
Inductive bias and generalization in BOFT. Since R(m, b) in BOFT usually represents structured subset of the orthogonal group which constrains the hypothesis class, BOFT will naturally induce an inductive bias. We argue that the structured inductive bias induced by butterfly factorization is

---

Published as a conference paper at ICLR 2024
beneficial to generalization, as it has shared structured pattern of many classic linear transforms [14], such as discrete Fourier transform, discrete sine/cosine transform and Hadamard transform. Moreover, the sparse matrix factorization in BOFT may also bring some implicit inductive bias [22, 44, 51].
Comparison to butterfly-basee sparse training. There are quite a few works [7, 13-15] that study sparse training with the butterfly parameterization. They typically foeus reparameterizing the weight matrices directly with the butterfly parameterization and training neural networks from scratch. [15] considers finetuning the pretrained weights by first projecting the weights on variant of butterfly matrices and then optimizing the projected components for downstream tasks. BOFT proposes a very different finetuning strategy that transforms the weights with layer-shared weight matrices.
6 APPLICATIONS AND EMPIRICAL RESULTS
We apply BOFT to finetune large language models (DeBERTaV3 [25], Llama-2 [81], vision founda- tion models (DINOv2 [62], SAM [35]), and text-to-image generative models (Stable Diffusion [73] on various downstream tasks. To ensure a fair comparison, we use exactly the same settings for all the compared baselines. The results are averaged over 5 random seeds, and the gains have passed significant tests with p < 0.05. Experimental details and more results are provided in the appendices.
6.1 ADAPTATION OF LARGE LANGUAGE MODELS (LLMs)
Natural language under- standing. To evaluate the per- formance of BOFT on LLM adaptation, we first finetune a pretrained DeBERTaV3- model [25] on the GLUE benchmark [87]. which con- sists of some representative sentence classification tasks and is widely used for assess- ing the natural language un-
Method
Param
MNLI
SST-2
CoI.A
QQP
QNLI
RTE
MRPC
STS-B
All
Full Finetuning
184M
89.90
95.63
69.19
92.40
94.03
83.75
89.46
91.60
88.25
RitFir [92]
0.IM
89.37
94.84
66.96
88.41
92.24
78.70
87.75
91.35
86.20
H-Adupter [28]
1,22M
90.13
95.53
68.64
91.91
94.11
84.48
89.95
91.48
88.28
P-Adapter [65]
1.1MM
90.33
95.61
68.77
92.04
94.29
85.20
89:46
91.54
88.41
LoRA,-s [29]
1.33M
90.65
94.95
69.82
91.99
93.87
85.20
89.95
88.50
AdaLoRA [97]
1.27M
90.76
90
71.45
92.23
94.55
88.09
90.69
91 84
89.46
OFT h=
0.79M
90.33
96.33
73.91
92.10
94.07
87.36
92.16
91.91
89.77
0.75M
90.25
96.44
72.95
92.10
88.81
91.92
89.89
Table I: Results on the GLUE development set. We report the matched accuracy for MNLI, Matthew's correlation for CoL.A, avernge correlation for STS-B and accuracy for other tasks.
derstanding ability [17, 25, 53]. Results are presented in Table 1. "# Param" in the table denotes the total number of effective trainable parameters for each method. We note that OFT [67] with the block size 16 is BOFT(1,16). One can observe that orthogonal finetuning performs better than current state-of-the-an art methods. More importantly, BOFT outperforms OFT while still using less parameters.
Massive multitask language un- derstanding. We use Alpaca [80] as our finetuning dataset and
MMLU (5 shot)
MMLU (D shot)
Method
Param
Hums.
Social
Avg.
Hums.
STEM
Social Avg.
Llama-2-77
43.0
36.9
51.6
52.1
45.7
38.8
33.3
46.8
45.0
40.8
Lo
0.125%
42,9
38.5
54.5
53.8
47.0
42.5
37.1
51.5
52.3
45.5
evaluate both zero-shot and few- shot performance on the MMLU dataset [27] which consists of
LoRA..
0.25%
42,9
54.6
47.3
42.5
36.7
52.8
45,9
OFT km
0.13%
44.0
38.9
54.2
54.3
47.5
44.0
36.7
52.9
52.0
46.2
BOFT m== 0.12%
44,5
39.0
54.4
55.1
47.9
44.3
37.4
53.1
52.8
46.7
57 language tasks. All methods use the pretrained Llama-2-7B model [81]. Results in Table show a consistent improvement over LoRA, but BOFT uses fewer parameters. Notably, BOFT(2,8) produces ddick-diagonal orthogonal matrix with the block size 16, and yet still outperforms OFT with the same block size (i.e., BOFT(I,16)) by a considerable margin.
Table 2: Accuracy (%) MMLU. "# Param" denotes the percentage of finetuned parametens.
This result implies that the butterfly structure incorporate generalizable inductive bias.
Mathematical question answering. We also evaluate our method in mathematical question answering using two challenging benchmarks: GSM8K [11] and MATH [27]. For all the finetuning methods, we MetaMathQA-40x [91] as the finetuning dataset, and the Ilama- 2-7B model [81] as the pretrained backbone. As can be observed in Table BOFT excels in mathematical reasoning on both datasets. We note that even though improvement on the MATH dataset is in fact quite challenging, BOFT achieves more than 10% relative improvement over LoRA while only using half of the number of trainable parameters for LoRA. Moreover, BOFT outperforms OFT even with the same effective block number, again verifying that the butterfly structure can introduce a generalizable inductive bias. We also provide a case study of a few questions in Appendix E.
Method
# Param GSM8K
MATH
Llama-2-7B
14.6
LoR LoRA,-s2
0.25%
50.2
7.8
OFT 6=16
0.13%
50.1
8.4
BOFT m=2
0.12%
50.6
Table 3: Results on GSMKK and MATII
7

---

Published as a conference paper at ICLR 2024
Natural
Specialized
Structured
param (M)
Cifac100
Caltech1
DTD
Flowert 02
Pots
SVHN
Sun397
Camelyon
FamSAT
Resine45
Reinopatly
Clev--Cor Count
Clevr-Ditt
DMLab
KITTI-Dit
dSpr-Loe
dSpr-Oni
SNORB- Azim
SNORB-EL Ele
Avenge
Full Finetuning
304.4
67.6
91.7
77.9
99.7
93.7
92.8
52.3
88.1
96.1
90.9
27.2
67.2
59.8
58.1
82.8
83.6
62.0
36.9
39.4
74.6
Linear Probing
0
73.2
90.9
78.1
99.7
95.2
40.3
59.3
84.2
92.9
86.8
75.6
48.1
44.4
45.9
65.4
25.5
37.0
18.5
30.9
62.7
Bura [92]
0.27
78.5
91.7
80.4
99.7
95.0
67.3
60.2
85.2
96.1
90.7
75.7
84.1
63.0
52.7
78.9
83.8
61.9
28.0
37.7
74.2
1o [1]
0.12
76.2
89.4
77.
99.7
94.7
89.6
58.9
87.1
94.3
88.7
74.0
83.1
63.3
56.2
83.1
61.7
37
23.3
32.6
72.1
=ak [31]
0.12
75.0
89.1
78.6
99.7
95.0
92.1
58.9
86,1
94.6
89.5
74.2
84.3
62.0
57.7
85.2
68.4
38
31.2
44.
73.9
LoRA,=4 [29]
1.77
77.2
92.8
80.3
99.7
94,8
92.7
59.5
88.3
96.4
91.4 77.4
74.7
62.4
58.1
85.2
85.8
57.2
31.
37.2
76.6
GLoRAy=4 [6]
4.87
80.1
93.7
89.6
59.9
76.2
61.8
57.2
37.0
414
OFT 1m
2.10
77.7
91.9
80.1
99.7
94.7
92.9
59.3
88.4
96.4
91.5
27.2
81.0
64.7
60.5
84.0
92.2
61.1
34.8
40.3
77.3
BOFT Am8
1.99
78.1
92.5 80.6
99.7
95.0
93.0
59.9
188.9
96.6
91.6
27.3
84.5 64.9
61.4
84,1
93.9
62.0
36.2
40.0
77.9
BOFT had
1.77
78.2
91.4 79.6
92.8
59.4
188.1
96.4
76.2
81.9
65.4
92.9
61.1
37.1
39.3
77.4
BOFT
1.11
78.3
91.5 79.9 99.7 95.0
92.0
60.2
188.2
96.5
91.4
77.2
80.5
64.1 61.4
85.0
91.6
60.8
34.0
38.5 77.1
Tahle 4: Results (%) on the VTAB-IK IK benchmark. "# param" specifies the numher of trainable parameters of each method. The average accurncy is obtained by avoraging over all 19 tasks. The best results are marked with "bold", and the sccondrthird best results are marked with "underline"
6.2 ADAPTATION OF VISION FOUNDATION MODELS
Transfer learning on VTAB-1K.
Model
Param
COIFT
HRSOD
ThinOhject
Average
We evaluate the finetuning perfor-
mloU
mBIoU miol mBloll mloU mBtol mloU mDIoU mloU mBlltt
mance of BOFT on the VTAB- IK benchmark [94], which has been extensively used to evaluate parameter-efficient transfer learn- ing algorithms. VTAB-IK con- sists of 19 image classification tasks that are divided into three categories: natural images, specialized tasks (e.g., remote sensing and medical images), and structured tasks (c.g., depth and orientation prediction). In II,, each dataset provides 800 labeled training set samples, a subset of their original training set. We use them to fine-tune our base model and the Top-1 classification accuracy on their respective original test set is used as the performance measure. Notably, all compared methods introduce no inference latency, so they have the same inference speed. Because the final classification layer will always get retrained and the trainable parameters of that linear classification layer vary across different tasks, we follow the common practice and do not take them into account when reporting the total trainable parameters for each method. Different from [6]. we use a much larger pretrained vision transformer [62] (DINOv2- rameters. The accuracies are given in Table We observe that orthogonal finetuning achieves the best overall testing accuracy on the VTAB- K benchmark, and BOFT with m 4, b = 4 again achieves the best performance. Remarkably, BOFT's performance enhancement both stable and consistent across tasks, almost all our results outperform the simplest full finetuning baseline. BOFT is marginally worse than full finetuning on three tasks: dSpr-Ori (-0.7%), Caltech 101 (-0.3%) and sNORB- Ele 0.1).. In contrast, LoRA is significantly worse than full finetuning on sNORB-AZi and dSpr-Ori by 5%. These results validate the effectiveness of BOFT for vision transformers.
SAM (baseline)
62.0
52.8
90.2
83.1
73.6
71.1
Finetune SAM
4.0GM
78,9
70,3
93.9
89.3
91.8
83.4
89.4
79.0
88.5
80.5
IIQ SAM [34]
1.33M
78.6
70.4
94.8
90.1
93,6
86,9
89.5
79.9
89.1
81.8
SAT 16
0.07M
77.8
69.1
94.9
90.3
92.6
85.5
91.2
80.6
88.9
81.4
BOFT-SAM 8-4
0.04M
78.2
69.7
94.9
90.5
93.1
86,0
91.7
80.1
89.5
81.6
BOFT-SAM bime
0.06M
78.4
70.3
94.7
90.1
93.0
86.5
91.7
81.8
89.5
82.2
Table Results on HQSeg (4K(44444111 [34] (DI5 [66]. COIFT [47], HRSOD [93], ThinGhject [47].
with more than 300M pa-
High-quality segmentation with SAM. The Seg- ment Anything Model (SAM) [35] is a vision foundation model for promptable image segmen- tation, demonstrating impressive zero-shot capa- bilities. SAM consists of three main components: a pre-trained image encoder to generate a fea- ture embedding of the input image, a prompt en- coder to embed prompts, and a mask decoder to map these input embeddings to a segmenta- tion mask. Despite its impressive performance in general image segmentation, SAM lacks the ability to perform highly accurate segmentation in challenging situations. To address this, HQ- SAM [34] proposes train additional HQ-Output Token and global-local feature fusion module on a high-quality segmentation dataset, HQSeg-448 [34], to improve the mask quality, achieving state-of-the-ar performance in high-quality segmentation. Using the same dataset and loss function
SAM
IOFFT-AM
Figure Qualitative comparison of between SAM and BOFT-SAM.
8

---

Published as a conference paper at ICLR 2024
prompt: blonde bair
prompt: wearing
signal
LoRA
Control signal
BUFT
Text prompt: woman with her mouth
Text prompt woman with long black hair
G
Control signal
LoRA
OFT
DOFT
Control signal
LoRA
OFF
DOFT
Figure 7: Qualitative comparison of controllable generation. The figure is best viewed digitally, in color and significantly zoomed in.
as HQ-SAM, we finetune the original SAM with BOFT for 10 epochs. Specifically, we only apply BOFT all linear layers of the mask decoder of SAM, while keeping the other part of SAM frozen. We compare to finetuning the entire mask decoder, training the HQ-SAM modules [34] and finetuning linear layers with BOFT. Table shows that BOFT-SAM uses only 3% of trainable parameters used in HQ-SAM, and yet matches its performance. Moreover, since the multiplicative weights learned by BOFT can be combined back to the weights of SAM, BOFT-SAM has exactly the same inference speed as SAM, while, in contrast, HQ-SAM has additional modules that affect its inference speed.
6.3 CONTROLLING TEXT-TO-IMAGE DIFFUSION MODELS
Since OFT is originally used to control text-to-image diffusion mod- els [67], we also evaluate BOFT with the same task for better compar- ison. We finetune the pretrained Stable Diffusion [73] for two tasks: controllable generation (e.g., [59, 96]) and subject-driven generation (e.g.. [74]). Controllable generation enables adding spatial control sig- nals to the -aaa- diffusion models. Subject-driven generation aims synthesize images of subject in novel contexts by finetuning on a few images that subject to learn unique identifier. We follow the same setting [67] for evaluating controllable generation. To be easily comparable to OFT, where the block structure is characterized by the number of blocks r, we also use the number of blocks char- acterize BOFT (instead of the block size b). Because rd = b. larger indicates less number of parameters. For example, for BOFT with r == 32 to generate dense orthogonal matrix, we need to have = 6.
Method
Param
Error 1
LoRAr=16
2.52M
LoRA,
10.08M
8.062
LoRA,
20. 17M
8.038
OFT
2.71M
8.876
10.50M
OFT
20.89M
6.407
BOFT
2.66M
8.070
m--6
7.69M
6.731
BOFT 1-
12.93M
6.387
BOFT F=
20.76M
5.667
Tahle 6: Face landmark hetween control signal and prediction.
We start by comparing LoRA, OFT and BOFT with a small parameter budget (less than 3M parame- ters). We see from Table 6 that BOFT with = 32, = 2 yields significantly better performance than both LoRA and OFT with the block number 16 under the 3M parameter budget. Under this small budget setting. we also provide a qualitative comparison among LoRA (r 16), OFT (r 16) and BOFT (r = 32, m = 2) in Figure 7. We also evaluate how BOFT performs with a dense orthogonal matrix using r 16, the best performance and significantly outperforms LoRA with a similar number of parameters.
4 and 8, m 4. We observe that BOFT with 8, = 4 achieves
Finally, we conduct ablation study on how the number of butterfly components m affects the performance of controllable generation. We first fix the block number as r 32, and then vary the number of butterfly components in BOFT from 0 (i.e., OFT with the block number 32) (BOFT with dense orthogonal matrix). Figure 8 shows that BOFT with larger m yields better control performance for Stable Diffusion finetuning. More interestingly, we also find that, with the same number of blocks, an increased number of butterfly components generally leads to faster and more stable convergence. This implies that orthogonal finetuning with denser orthogonal matrix converges faster in finetuning text-to-image diffusion models. This also matches our intuition that a dense orthogonal matrix can transform neurons more effectively due to its more efficient information transmission.
DFT 1wd2 BOFT, Burr..it
-5 30
Landmark
10
15
Number of epachs
Figure How m affects coutrollability
BOFT also performs consistently better than both LoRA and the original OFT subject-driven generation. A qualitative comparison is given in Figure and Appendix C. For all the compared methods, we use the best possible hyperparameters. We empirically observe that BOFT can generally capture more intrinsic identity characteristics of the input subject, and therefore, the generated images

---

Published as a conference paper at ICLR 2024
Imput images
[V] bont with whear fiedd bodigraued
Ispui images
shing harkgackk
[
bockground
[V] backpack sop pink fabric
LoRA
OFF
BOFT
LoRA
OFF
BOFF
Ingut images
cabe skaped say
Erpui images
[V] saraker with the Kiffet Fawer is the background
bockgr
LoKA
OFT
BUFT
LoRA
OFT
BOFT
Figure 9: Qualitative comparison of subject driven generation. The figure is best viewed digitally, in color and significamll zoomed in.
Control
matrioes)
matrices
miiri))
Figure 10: Model weight interpolation by setting the trained buttertly components finetune Stable Diffusion (SD). No retraining performed when we gradually set each trained orthogonal matrix ( (B.) to an identity. The number in the figure denotes number of remaining orthogonal butterfly components has not been set identity. Text prompt: a man of SD with learned control head.
ideatity matrix. We use BOFT(m 5, 16)
with beard smiling (for the first row) and smiling woman (for the second row). "0 matrix
visually more plausible in terms of the subject identity preservation. We can see from Figure that the original OFT also shows good performance in preserving subject identity while LoRA has better text prompt following ability. In sharp contrast, BOFT can achieve the best of both worlds by simultaneously demonstrating good subject identity preservation as well as accurate text prompt following ability. Notably, for the bottom-left toy duck case Figure 9, we observe that BOFT can capture the essence of the toy and generate a cubed shaped toy with a conceptually similar color.
BOFT comes with free weight interpolation. We have a surprising yet interesting discovery that uniquely distinguishes BOFT from existing methods in controllable generation. BOFT consists of multiple orthogonal matrices (i.e., multiple butterfly components), and the product of these matrices gives the complete finetuned model. However, what will happen if set the trained orthogonal butterfly components to identity matrix one by one without retraining? If we set all the butterfly components identity, the model reduces Stable Diffusion. If butterfly components are set to identity, then we have the full BOFT-finetuned model. After the BOFT training, the structure of multiple butterfly components provides us with a free weight interpolation on the orthogonal manifold. We perform the weight interpolation for all the BOFT-finetuned layers in Stable Diffusion. Specifically, we use BOFT with butterfly components one by one to identity matrix, starting from left-hand side. The results are given in Figure 10. Surprisingly, although these interpolated weights have not been retrained, they can still generate plausible images. In fact, as we set more butterfly components to identity, the interpolated model produces smooth interpolated result, from a mndmarr--cnnrrolle Stable Diffusion image. These results well validate that the hypothesis weight space (i.e., model space) in BOFT can well preserve the semantics and effectively climinate many bad local minima.
5, r 16, so we have 6 butterfly components. We set the
image to an uncontrolled
7 CONCLUDING REMARKS AND LIMITATIONS
Our paper proposes Orthogonal Butterfly, a generic parameter-efficient finetuning method for foun- dation models based the butterfly structure. The key insight better parameter-effiiiency is to
10

---

Published as a conference paper at ICLR 2024
parameterize a dense orthogonal matrix with the product multiple sparse orthogonal matrices. To easily find feasible matrix factorizations, we propose a graphical information transmission framework. find that the butterfly structure
Under this framework, of sparse orthogonal matrix factorization. We demonstrate the empirical effectiveness of BOFT in finetuning large language models, large vision models and text-to-image generative models. Our experiments also validate the superiority of BOFT as a generic mode finetuning method.
effectively achieve our desiderata
Despite empirical effectiveness, BOFT is by no means perfect. Since the final orthogonal matrix in BOFT'R is the product of multiple orthogonal matrix, the training runtime overhead is slightly larger than OFT. How to improve BOFT's training runtime remains an open problem. Fortunately, after the finetuming stage, the BOFT-learned orthogonal matrices can be directly multiplied into the pretrained model and there no additional inference latency. Moreover, whether the butterfly network the most efficient way to transmit information is also unknown. Our information transmission framework further enables us to draw inspiration from a distinct research discipline computer networking, where the efficiency of network topology for transmitting information is heavily studied. We expect that more efficient network structures can be used for composing dense orthogonal matrices.
ACKNOWLEDGMENT AND AUTHOR CONTRIBUTION
The authors would like to sincerely thank Peter Kulits for careful proofreading, Tim Z. Xiao and many other colleagues at Max Planck Institute for Intelligent Systems for countless helpful suggestions. This work was supported by the German Federal Ministry of Education and Research (BMBF): Tubingen AI Center, FKZ: OIIS 18039B, and by the Machine Learning Cluster of Excellence, EXC number 2064/1 Project number 390727645. WL was supported by the German Research Foundation (DFG): SFB 1233, Robust Vision: Inference Principles and Neural Mechanisms, TP XX, project number: 276693517 YF and SP are partially supported by the Max Planck ETH Center for Learning Systems. Yuliang Xiu is funded by the European Union's 's Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie grant agreement No. 860768 (CLIPE). AW acknowl- edges support from Turing AI Fellowship under grant EP/V025279/1, The Alan Turing Institute, and the Leverhulme Trust via CFI. MJB has received research gift funds from Adobe, Intel, Nvidia, Meta/Facebook, and Amazon. MJB has financial interests in Amazon, Datagen Technologies, and Meshcapade GmbH. While MJB is a consultant for Meshcapade, his research in this project was performed solely at, and funded solely by, the Max Planck Society.
Weiyang Liu and Zeju Qiu contributed equally the joint first author. Yao Feng, Yuliang Xiu, Yuxuan Xue and Longhui Yu contributed equally as the joint second author. Authors with equal contributions are listed in alphabetical order and allowed to change their orders freely on their resume and website. Michael J. Black, Adrian Weller and Bernhard Schölkopf jointly supervised the project, provided generous computing support and contributed significantly to the project (including but not limit to idea discussion, direction suggestion and paper writing).
Weiyang Liu initialized the core idea, organized the project, co-developed the current method, co- supervised the experiments, and wrote the draft. Zeju Qiu co-initialized the core idea, co-developed the current method, implemented most of the prototypes, conducted the GLUE, VTAB- -K and SAM finetuning experiments, co-supervised the experiments and contributed to the draft writing. Yao Feng implemented fast version of BOFT in CUDA, contributed to the method development, and conducted the experiments of multi-modal finetuning. Yuliang Xiu led the experimental efforts in controlling eext-to-image diffusion models, conducted the experiments of both controllable (ControlNet) and subject-driven (DreamBooth) generation, contributed to the method development and paper writing. Yuxuan Xue contributed the method development and the experiments of vision foundation models. Longhui Yu led the experimental efforts in MMLU and mathematical question answering and contributed to the method development. Haiwen Feng contributed to the method development and the experiments of text-to-image generation. Juyeon Heo conducted the robustness experiments. All the team members made necessary contributions to the method development and paper writing.
Large language models: the experiments are jointly led by Zeju Qiu and Longhui Yu. Weiyang Liu contributed to the model debugging.
the experiments are led by Zeju Qiu. Yuxuan Xue contributed to the baseline experiments and model debugging. Weiyang Liu contributed to the model debugging. Text-to-image diffusion models: the experiments are led by Yuliang Xiu. Zeju Qiu, Weiyang Liu and Haiwen Feng contributed to the model debugging.
Vision foundation models:

---

Published as a conference paper at ICLR 2024
REFERENCES
[1] Armen Aghajanyan, Luke Zettlemoyer, and Sonal Gupta. Intrinsic dimensionality explains the effectiveness of language model fine-tuning, arXiv preprint arXiv:2012.13255, 2020. 3
[2] Theodore Anderson, Ingram Olkin, and Les G Underhill. Generation of random orthogonal matrices. SIAM Journal on Scientific and Statistical Computing, 1987. 6
Alan Ansell, Edoardo Ponti, Anna Korhonen, and Ivan Vulić. Composable sparse fine-tuning for cross-lingual transfer. In ACI, 2022. 3
[4] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhari- wal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. In NeurIPS, 2020. 1,2
[5] Emmanuel J Candès, Xiaodong Li, Yi Ma, and John Wright. Robust principal component analysis? Journal of the ACM, 2011. 2
[6] Arnav Chavan, Zhuang Liu, Deepak Gupta, Eric Xing, and Zhiqiang Shen. One-for-all: Generalized lora for parameter-efficien fine-tuning. arXiv preprint arXiv:2306.07967, 2023.
1,3, 8, 19
[7] Beidi Chen, Tri Dao, Kaizhao Liang, Jiaming Yang, Zhao Song, Atri Rudra, and Christopher Re. Pixelated butterfly: Simple and efficient sparse training for neural network models. In ICLR, 2022. 5,
[8] Jiaao Chen, Aston Zhang. Xingjian Shi, Mu Li, Alex Smola, and Diyi Yang. Parameter-efficient fine-tuning design spaces. In ICLR, 2023.
[9] Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, et al. Evaluating large language models trained on code. arXiv preprint arXiv:2 2021. 1
[10] Shoufa Chen, Chongjian Ge, Zhan Tong. Jiangliu Wang. Yibing Song, Jue Wang, and Ping Luo. Adaptformer: Adapting vision transformers for scalable visual recognition. In NeurIPS, 2022. 3
[11] Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reicchro Nakano, et al. Training verifiers to solve math word problems. arXiv preprint arXiv:2110.14166 2021.
[12] James W Cooley and John W Tukey. An algorithm for the machine calculation of complex fourier series. Mathematics of computation, 19(90):297-301, 1965. 2,5
[13] Tri Dao, Albert Gu, Matthew Eichhorn, Atri Rudra, and Christopher Ré. Learning fast algorithms for linear transforms using butterfly factorizations. In ICML, 2019. 3, 6,
[14] Tri Dao, Nimit Sohoni, Albert Gu, Matthew Eichhor,, Amit Blonder, Megan Leszezynski, Atri Rudra, and Christopher Ré. Kaleidoscope: An efficient, learnable representation for all structured linear maps. In ICLR, 2020. 3, 29
[15] Tri Dao, Beidi Chen, Nimit S Sohoni, Arjun Desai, Michael Poli, Jessica Grogan, Alexander Liu, Aniruddh Rao, Atri Rudra, and Christopher Ré. Monarch: Expressive structured matrices for efficient and accurate training. In ICML, 2022. 3.7
[16] Tim Dettmers, Artidoro Pagnoni, Ari Holtzman, and Luke Zettlemoyer. Qlora: Efficient finetuning of quantized 1lms. arXiv preprint 2rXiv:2305.13311 2023.
[17] Jacob Devlin, Ming-Wa Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding, 2019. 7
[18] Ning Ding, Yujia Qin, Guang Yang, Fuchao Wei, Zonghan Yang, Yusheng Su, Shengding Hu, Yulin Chen, Chi-Min Chan, Weize Chen, et al. Parametee-efficient fine-tuning of large-scale pre-trained language models. Nature Machine Intelligence, 2023. 3
12

---

Published as a conference paper at ICLR 2024
[19] Ali Edalati, Marzich Tahaci, Ivan Kobyzev, Vahid Partovi Nia, James J Clark, and Mehdi Rezagholizadch, Krona: Parameter efficient tuning with kronecker adapter. arXiv preprint arXiv:2212.10650, 2022. 3
[20] Rinon Gal, Yuval Alaluf, Yuval Atzmon, Or Patashnik, Amit H Bermano, Gal Chechik, and Daniel Cohen-Or. An image is worth one word: Personalizing text-to-image generation using textual inversion. arXiv preprint arXiv:2208.01622 2022. 20
[21] Mozhdeh Gheini, Xiang Ren, and Jonathan May. Cross-attention is all you need: Adapting pretrained transformers for machine translation. In EMNLP, 2021.
[22] Suriya Gunasekar, Blake E Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Srebro. Implicit regularization matrix factorization. In NeurIPS, 2017. 7
[23] Demi Guo, Alexander M Rush, and Yoon Kim. Parameter-efficient transfer learning with diff pruning. arXiv preprint arXiv:2012.07463, 2020. 1.3
[24] Junxian He, Chunting Zhou, Xuezhe Ma, Taylor Berg- King-Kikatarrck, and Graham Neubig. To- wards unified view of parameter-efficies transfer learning. arXiv preprint ar arivv22110043666 2021. 1,3
[25] Pengcheng He, Jianfeng Gao, and Weizhu Chen. Debertav3: Improving deberta using electra-
style pre-training with gradient-disentangled embedding sharing. In ICLR, 2022. 7, 19
[26] Wu Hecong. ControlLoRA: A Lightweight Neural Network To Control Stable Diffusion Spatial Information. https://github..omm/ffe https//////coiiiiiooooooooo...o. 2023. 20
[27] Dan Hendrycks, Collin Burns, Steven Basart, Andy Zou, Mantas Mazeika, Dawn Song, and Jacob Steinhardt. Measuring massive multitask language understanding. In ICLR, 2021.
[28] Neil Houlsby, Andrei Giurgiu, Stanislaw Jastrzebski, Bruna Morrone, Quentin De Laroussilhe, Andrea Gesmundo, Mona Attariyan, and Sylvain Gelly. Parameter-efffcient transfer learning for nlp. In JCML, 2019. 1, 3,
[29] Edward Hu, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, Weizhu Chen, et al. Lora: Low-rank adaptation of large language models. In ICLR, 2022. 1, 2, 3, 6, 7,
8
[30] Menglin Jia, Luming Tang. Bor- Mor-Chun Chen, Claire Cardie, Serge Belongie, Bharath Hariharan, and Ser-Nam Lim. Visual prompt tuning. In ECCV, 2022.
[31] Shibo Jie and Zhi-Hong Deng. Fact: Factor-tuning for lightweight adaptation on vision transformer. In AAAI, 2023. 3,
[32] Li Jing, Yichen Shen, Tena Dubcek, John Peurifoy, Scott Skirlo, Yann LeCun, Max Tegmark, and Marin Soljačić. Tunable efficient unitary neural networks (eunn) and their application to mns. In /CML, 2017.
[33] Rabech Karimi Mahabadi, James Henderson, and Sebastian Ruder. Compacter: low-rank hypercomplex adapter layers. In NeurlPS, 2021. 3
Efficient
[34] Lei Ke, Mingqiao Ye, Martin Danelljan, Yifan Liu, Yu- Wing Tai, Chi-Keung Tang, and Fisher
Yu. Segment anything in high quality. In NeurIPS, 2023. 8, 9, 20
[35] Alexander Kirillov, Eric Mintun, Nikhila Ravi, Hanzi Mao, Chloe Rolland, Laura Gustafson, Tete Xiao, Spencer Whitehead, Alexander C Berg, Wan-Yen Lo, et al. Segment anything. arXiv preprint arXiv:2304.0 02643, 2023. 2, 7, 8, 20
[36] Ralf Klasing, Burkhard Monien. Regine Peine, and Elena A Stöhr. Broadcasting in butterfly and debruijn networks. Discrete Applied Mathematics, 53(1-9):183-117, 1994. 2,
[37] Nupur Kumari, Bingliang Zhang, Richard Zhang, Eli Shechtman, and Jun-Yan Zhu. Multi- concept customization of text-to-image diffusion. In CVPR, 2023. 20
13

---

Published as a conference paper at ICLR 2024
[38] Benjamin Lefaudeux, Francisco Massa, Diana Liskovich. Wenhan Xiong, Vittorio Caggiano, Sean Naren, Min Xu, Jieru Hu, Marta Tintore, Susan Zhang, Patrick Labatut, and Daniel Haziza. xformers: A modular and hackable transformer modelling library. https///gtthub.com/
watpoookreseaccc/ffoneeee 2022. 20
[39] Brian Lester, Rami Al-Rfou, and Noah Constant. The power of scale for parameter-efficient prompt tuning. arXiv preprint 1xXiv2200408622 2021. 1,3
[40] S-YR Li, Raymond W Yeung, and Ning Cai. Linear network coding. IEEE transactions on information theory, 2003. 3
[41] Shuo-Yen Robert Li, Qifu Tyler Sun, and Ziyu Shao. Linear network coding: Theory and algorithms. Proceedings of the IEEE, 2011. 1.
[42] Xiang Lisa Li and Percy Liang. Prefix-tune frefix-tuning: Optimizing continuous prompts for generation. In ACI., 2021. 1,
[43] Yingzhou Li, Haizhao Yang, Eileen R Martin, Kenneth L Ho, and Lexing Ying. Butterfly factorization. Multiscale Modeling & Simulation, 13(2):714-73,, 2015. 3
[44] Yuanzhi Li, Tengyu Ma, and Hongyang Zhang. Algorithmic regularization in over- parameterized matrix sensing and neural networks with quadratic activations. In COLT, 2018. 7
[45] Vladislav Lialin, Vijeta Deshpande, and Anna Rumshisky. Scaling down to scale up: A guide to parameter-efficient fine-tuning, arXiv preprint arXiv:2303. 2.01::2303.156477, 2023. 3
[46] Dongze Lian, Daquan Zhou, Jiashi Feng, and Xinchao Wang. Scaling & shifting your features:
A new baseline for efficient model tuning. In NeurIPS, 2022.
[47] Jun Hao Liew, Scott Cohen, Brian Price, Long Mai, and Jiashi Feng. Deep interactive thin object selection. WACV, 2021. 8
[48] Zhaojiang Lin, Andrea Madotto, and Pascale Fung. Exploring versatile generative language model via parameter-efficient transfer learning. arXiv preprint arXhv:2004.03829 2020.
[49] Haokun Liu, Derek Tam, Mohammed Mugeeth, Jay Mohta, Tenghao Huang, Mohit Bansal, and Colin A Raffel. Few-shot parameter-efficien fine-tuning is better and cheaper than in-context learning. In NeurlPS, 2022. 3
[50] Weiyang Liu, Rongmei Lin, Zhen Liu, Lixin Liu, Zhiding Yu, Bo Dai, and Le Song. Learning towards minimum hyperspherical energy. In NeurIPS, 2018. 3
[51] Weiyang Liu, Zhen Liu, James M Rebg, and Le Song. Neural similarity learning. In NeurIPS, 2019. 7
[52] Weiyang Liu, Rongmei Lin, Zhen Liu, James M Rebg. Liam Paull, Li Xiong, Le Song, and Adrian Weller. Orthogonal over-parameterized training. In CVPR, 2021. 5,5
[53] Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. Roberta: A robustly optimized bert pretraining approach, 2019.
[54) 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 23Xi::2302.081066 2023. 3
[55] Sourab Mangrulkar, Sylvain Gugger, Lysandre Debut, Younes Belkada, and Sayak Paul. Peft: State-of-the-art parameter-efficient fine-tuning methods. http:///gthub..oo/ngggggggeee/ 2022. 20
[56] Yuming Mao, Lambert Mathias, Rui Hou, Amjad Almahairi, Hao Ma, Jiawei Han, Wen-tau Yih, and Madian Khabsa. Unipelt: A unified framework for parameter-efficiem language model uning. arXiv preprint 1 2021.
14

---

Published as a conference paper at ICLR 2024
[57] Eric Michielssen and Amir Boag. A multilevel matrix decomposition algorithm for analyzing scattering from large structures. IEEE Transactions on Antennas and Propagation, 1996.
[58] Takeru Miyato, Toshiki Kataoka, Masanori Koyama, and Yuichi Yoshida. Spectral normaliza- tion for generative adversarial networks. ICLR, 2018.
[59] Chong Mou, Xintao Wang, Liangbin Xie, Jian Zhang, Zhongang Qi, Ying Shan, and Xiaohu Qie. -ai-ar Learning adapters dig out more controllable ability for text-to-image diffusion models. arXiv preprint arXiv:23302.08453 2023. 9
[60] Marina Munkhoeva, Yermek Kapushev, Evgeny Burnaev, and Ivan Oseledets. Quadrature- based features for kernel approximation. In NeurlPS, 2018. 3
[61] Michael O'Neil, Franco Woolfe, and Vladimir Rokhlin. An algorithm for the rapid evaluation of special function transforms. Applied and Computational Harmonic Analysis, 2010.
[62] Maxime Oquab, Timothée Darcet, Théo Moutakanni, Huy Vo. Marc Szafraniec, Vasil Khalidov, Pierre Fernandez, Daniel Haziza, Francisco Massa, Alaaeldin El-Nouby, et al. Dinov2: Learning robust visual features without supervision. arXiv preprint arXiv:2304.07193. 2023.
7, 8, 19
[63] Douglass Stott Parker. Random butterfly transformations with applications in computational linear algebra. UCLA Computer Science Department, 1995. 3,
[64] John Peca-Medlin. Numerical, spectral, and group properties of random butterfly matrices. University of California, Irvine, 2021. 30, 31, 32
[65] Jonas Pfeiffer, Aishwarya Kamath, Andreas Rücklé, Kyunghyun Cho, and Iryna Gurevych. Adapterfusion: Non-destructive task composition for transfer learning. arXiv preprint arXiv:2005.00244 2020. 1,7
[66] Xuebin Qin, Hang Dai, Xiaobin Hu, Deng-Ping Fan, Ling Shao, and Lue Van Gool. Highly accurate dichotomous image segmentation. In ECCV, 2022. 8
[67] Zeju Qiu, Weiyang Liu, Haiwen Feng, Yuxuan Xue, Yao Feng, Zhen Liu, Dan Zhang, Adrian Weller, and Bernhard Schölkopf. Controlling text-to-image diffusion by orthogonal finetuning. In NeurlPS, 2023. 1, 3, 9,
[68] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. Learning transferable visual models from natural language supervision. ICML, 2021. 2
[69] 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. JMLR, 2020.
[70] Indra Rajasingh, Paul Manuel, N Parthiban, Azubha Jemilet, and R Sundara Rajan. Trans- mission in butterfly networks. The Computer Journal, 2016. 3
[71]
Sylvestre-Alvise Rebuffi, Hakan Bilen, and Andrea Vedaldi. Learning multiple visual domains with residual adapters. In NeurlPS, 2017.
[72] Steven Roman, S Axler, and FW Gehring. Advanced linear algebra, volume 3. Springer, 2005.
6
[73] Robin Rombach, Andreas Blattmann, Dominik Lorenz, Patrick Esser, and Björn Ommer. High-resolution image synthesis with latent diffusion models. In CVPR, 2022. 1, 2, 7, 9, 20
[74] Nataniel Ruiz, Yuanzhen Li, Varun Jampani, Yacl Pritch, Michael Rubinstein, and Kfir Aber- man. Dreambooth: Fine tuning text-to-image diffusion models for subject-driven generation. In CVPR, 2023. 20
[75] Yan Solihin. Fundamentals of parallel multicore architecture. CRC Press, 2015. 5
15

---

Published as a conference paper at ICLR 2024
[76] Jiaming Song, Chenlin Meng, and Stefano Ermon. Denoising diffusion implicit models. In ICLR, 2021. 20
[77] Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: a simple way to prevent neural networks from overfitting. JMLR, 2014.
[78] Yi-Lin Sung, Varun Nair, and Colin A Raffel. Training neural networks with fixed sparse masks. Neur/PS, 20
[79] Yi-Lin Sung, Jaemin Cho, and Mohit Bansal. Lst: Ladder side-tuning for parameter and memory efficient transfer learning. In NeurlPS, 2022. 3
[80] Rohan Taori, Ishaan Gulrajani, Tianyi Zhang. Yann Dubois, Xuechen Li, Carlos Guestrin, Percy Liang, and Tatsunori B. Hashimoto. Stanford alpaca: An instraction-followingg llama model. https://github..c www.oattoootttttmootaaa labbstaaforddalpacco 2023. 7, 20
[81] Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. Llama 2: Open foundation and fine-tuned chat models. arXiv preprint arXiv2230..09288, 2023. 7
[82] Marcos Treviso, Ji-Ung Lee, Tianchu Ji, Betty van Aken, Qingqing Cao. Manuel R Ciosici, Michael Hassid, Kenneth Heafield, Sara Hooker, Colin Raffel, et al. Efficient methods for natural language processing: A survey. Transactions of the Association for Computational Linguistics, 2023. 3
[83] Thomas Trogdon On spectral and numerical properties of random butterfly matrices. Applied Mathematics Letters, 95:48-58, 2019. 30
[84] Mojtaba Valipour, Mehdi Rezagholizadch, Ivan Kobyzev, and Ali Ghodsi. Dylora: Parameter efficient tuning of pre-trained models using dynamic search-free low-rank adaptation. arXiv preprint wxxiv:2210.07555. 2022.
[85] Patrick von Platen, Suraj Patil, Anton Lozhkov, Pedro Cuenca, Nathan Lambert, Kashif Rasul, Mishig Davaadorj, and Thomas Wolf. Diffusers: State-of-the-art diffusion models.
2022. 20
[86] Tu Vu, Brian Lester, Noah Constant, Rami Al-Rfou, and Daniel Cer. Spot: Better frozen model adaptation through soft prompt transfer. In ACL, 2022.
[87] Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel R. Bowman. Glue: A multi-task benchmark and analysis platform for natural language understanding. 2019.
7, 19
[88] Yaqing Wang, Subhabrata Mukherjee, Xiaodong Liu, Jing Gao, Ahmed Hassan Awadallah, and Jianfeng Gao. Adamix: Mixture-of-adaee adapter for carameter-efffiicee tuning of large language models. EMNLP, 2022. 3
[89] Eric Xing, Michael Jordan, Stuart J Russell, and Andrew Ng. Distance metric learning with application to clustering with side-information. In NewriPS, 2002.
[90] Yuichi Yoshida and Takeru Miyato. Spectral norm regularization for improving the generaliz- ability of deep learning. arXiv preprint 1705: 2017.
[91] Longhui Yu, Weisen Jiang, Han Shi, Jincheng Yu, Zhengying Liu, Yu Zhang, James T Kwok, Zhenguo Li, Adrian Weller, and Weiyang Liu. Metamath: Bootstrap your own mathematical questions for large language models. arXiv preprint arXiv:2309. 12284, 2023. 7, 20
[92] Elad Ben Zaken, Yoav Goldberg, and Shauli Ravfogel. BitFit: Simple Parameter-efficiie Fine-tuning for Transformer-hased Masked I. Language-models. In ACI, 2022. 1, 7,8
[93] Yi Zeng. Pingping Zhang, Jiamming Zhang, Zhe Lin, and Huchuan Lu. Towards high-resolution salient object detection. In ICCV, 2019. 8
16

---

Published as a conference paper at ICLR 2024
[94] Xiaohua Zhai, Joan Puigcerver, Alexander Kolesnikov, Pierre Ruyssen, Carlos Riquelme, Mario Lucic, Josip Djolonga, Andre Susano Pinto, Maxim Neumann, Alexey Dosovitskiy, et al. A large-scale study of representation learning with the visual task adaptation benchmark. arXiv preprint 19Xiv:/900.44800 2019.
[95] Feiyu Zhang, Liangzhi Li, Junhao Chen, Zhouqiang Jiang, Bowen Wang, and Yiming Qian. Increlora: Incremental parameter allocation method for parameter-effiiiet fine-tuning, arXiv preprint arXiv:2308. 12043, 2023. 3
[96] Lvmin Zhang, Anyi Rao, and Maneesh Agrawala. Adding conditional control to text-to-image diffusion models. In ICCV, 2023. 20
[97] Qingru Zhang, Minshuo Chen, Alexander Bukharin, Pengcheng He, Yu Cheng, Weizhu Chen, and Tuo Zhao. Adaptive budget allocation for parameter-efficient fine-tuning. In ICLR, 2023.
1, 3, 7, 19
[98] Yuanhan Zhang, Kaiyang Zhou, and Ziwei Liu. Neural prompt search. arXiv preprint arXiv:2206.0467. 2022.
[99] Bolei Zhou, Hang Zhao, Xavier Puig, Sanja Fidler, Adela Barriuso, and Antonio Torralba. Scene parsing through ade20k dataset. In CVPR, 2017. 20
[100] Bolei Zhou, Hang Zhao, Xavier Puig, Tete Xiao, Sanja Fidler, Adela Barriuso, and Antonio Torralba. Semantic understanding of scenes through the ade20k dataset. International Journal of Computer Vision 2019. 20
[101] Hao Zhu, Wayne Wu, Wentao Zhu, Liming Jiang, Siwei Tang, Li Zhang, Ziwei Liu, and Chen Change Loy. CelebV-HQ, A large-scale video facial attributes dataset. In ECCV, 2022. 20
[102] Bojia Zi, Xianbiao Qi, Lingzhi Wang, Jianan Wang, Kam-Fai Wong, and Lei Zhang. Delta- lora: Fine-tuning high-rank parameters with the delta of low-rank matrices. arXiv preprint arXiv:2309.0244 0,411, 2023.
17

---

Published as a conference paper at ICLR 2024
Appendix
Table of Contents
A Experimental Details
19
A.1
Natural Language Understanding
19
A.2
Transfer Learning on VTAB-IK
19
A.3
Experimental Details Llama Finetuning
A.4
Experimental Details in SAM Finetuning
Experimental Details in ControlNet and DrcamBooth ................................
20
A.5
20
B More Qualitative Results High-quality Segmentation
21
C More Qualitative Results in Subject-driven Generation
22
D More Qualitative Results in Controllable Generation
26
E Mathematical Question-Answering Case Study
28
F Proof of Theorem
G Mathematical Properties of Butterfly Matrices
30
G.I Balanced Entry-wise Learning Rate
G.2 An Alternative Definition of Orthogonal Butterfly Matrices ................................
30
G.3 Topological Properties
31
G.4 Input Sensitivity
32
G.5 Random Orthogonal Butterfly Matrices
32
H Illustration of Block Butterfly Matrices
33
More Results Expressiveness of BOFT
34
18

---

Published as a conference paper at ICLR 2024
A EXPERIMENTAL DETAILS
A.1 NATURAL LANGUAGE UNDERSTANDING
For our experiments on the GLUE benchmark [87], we follow the setting of [97] and only tune the learning rate, the multiplicative dropout rate, and the number of training epochs. We use the pre- pre-trained DeBERTaV3 [25]' as our base model and apply the OFT and BOFT to every linear layer every transformer blocks. All runs can be trained on a single NVIDIA A100-SXM4-80GB GPU. See the hyperparameters used in our runs in Table 7.
Method
Dotaset
MNLI
SST-2
MRPC
CoLA
QNLI
QQP
RTE
STS-B
Batch Size
32
32
32
32
32
32
32
32
# Epochs
5
14
5
4
9
11
DeBERRTV hase
(16)
Learning Rate
8E-05
2E-04
9E-04
4E-04
2B-04
3E-04
3B-04
7E-04
OFT Dropout
1E-01
1E-01
1E-01
SE-02
1B-01
1E-01
SB-02
1E-01
Max Seq. Len.
256
128
320
64
512
320
320
128
Batch Size
32
32
32
32
32
32
32
32
Epochs
4
D
OFT (8,1)
Learning Rate
7E-05
5E-05
8F-04
5E-04
2F-04
3F-04
4E-04
7F-04
OFT Dropout
15E-02
15E-02
IE-01
15E-02
SE-02
SE-02
5E-02
SE-02
Max Soq. Len.
256
128
320
64
512
320
320
128
Table Hyperpuramettrr selup used for DeBERITaV3 base on the GLUE benchmarkk.
A.2 TRANSFER LEARNING ON VTAB-IK
In our VTAB-IK experiments, employ the DINOv2-large [62] Our architecture design aligns with GLoRA [6]. injecting trainable OFT and BOFT weights into every linear layer in all multihead self-attention (MSA) and MLP blocks. To ensure fair comparison, maintain the identical training setups for our and the baseline methods: a total number 30 training epochs, fixed training batch size of 64, AdamW optimizer, and cosine learning rate scheduler with a warmup ratio of 0.1. Notably, due to the supernet structure of GLoRA [6], we tested both training for 30 and 100 epochs. We conduct a grid search on the learning rate for both our method and baseline methods and report the best final test set's 's Top-1 classification accuracy after the final epoch. For BOFT and OFT, we additionally adopt multíplicative dropout rate of 0. and apply weight decay rate of 0.02. All methods are trained on a single NVIDIA A100-SXM4-80CH GPU. The exact learning rate details for OFT and BOFT can be found Table
base model for fine-tuning.
NORD Azim
Cibetoo
Caltechii
DTD
Flowers/02
Pas
SVHN
Sunge
Camolyon
EurSAT
Resiee45
Rotinopalty
Clev-Coont
Clev-
Dist
DMLab
KITT--NsI
dSpeLoc
uSyr
SNORH-Ele
Datasel
OFT 16
Sc-1
5c-4
6c-1
20-3
36-1
3e-3
Je3
9c-1
9c-4
5o-1
1e.3
2e-4
16-1
20-3
1e:3
20-3
3e-1
1e-3
6c-4
BOFT N
Ne-4
5o-4
6c-4
26-3
36-3
16-3
1e-3
6e-4
96-4
26-4
36-4
36-3
9e-4
5o-4
5e-1
Xo-4
y-2
9c-4
16.3
4e-3
9c-4
Table 8: [lpeerprraeeterr setup (i.c., learning used for DINOv2 Iargge the VTAB IK benchmark.
A.3 EXPERIMENTAL DETAILS IN LLAMA FINETUNING
In the Llama-related finetuning experiments, language understanding and mathematical question answering, fixed the batch size 64 and the training epoch 2. For all the Lora, OFT, and BOFT experiments, we use the cosine learning scheduler and the warmup of the first 100 learning steps. We finetune the Llama model the first generated 512 tokens, which is sufficient for these two tasks. We use the AdamW W optimizer with a le-4 learning rate and 8e-4 learning rate for the language understanding task and mathematical question-answering task, respectively. The multiplicative dropout used for language understanding and mathematical question answering is 0.1 and 0.05,
'httss//hugginnffccccom http:///huggingaac..oovrcoooooot www..ecosssof//cccrrttaaaaaaaee
19

---

Published as a conference paper at ICLR 2024
respectively, For language understanding, evaluate the performance MMLU with both zero- shot and 5-shot evaluation. For mathematical question answering, we basically follow the evaluation tools in MetaMathQQ [91], where they use the Alpaca [80] prompt and evaluate the model in zero-shot. The generation temperature set as O for both tasks.
A.4 EXPERIMENTAL DETAILS IN SAM FINETUNING
We generally follow the training and evaluation settings HQ-SAM [34]. Specifically, we use learning rate of 0.0005, a cosine annealing learning rate scheduler, Adam optimizer with weight decay rate of 0.01 and multiplicative dropout rate of 0.005. During fine-tuning, we keep the SAM model [35] frozen.
A.5 EXPERIMENTAL DETAILS IN CONTROLNET AND DREAMBOOTH
For our experiments on the ControlNet [96] and DreamBooth [74], we mainly follow the setting of OFT [67] but re-implement them using HuggingFace's Diffusers [85] and Parameter-Efficient Fine- TaninT (PEFT) [55]'. Specifically, we use Stable Diffusion [73] (v2.1)² as our pretrained model, and DDIMScheduler [76] our scheduler function. The attached fine-tuned PEFT layers within UNet are fto_g, to-v, to_k, query, value, key). Both training and testing are conducted on NVIDIA A100-SXM4 80GB, memory efficient attention from xFormers [38] is employed. Some specific settings for ControlNet and DreamBooth are follows:
ControlNet We train ControlNet image encoder (lightweight 8-conv-layer network same as Con- trolLoRA [26]) and the attached PEFT layers within UNet, with the learning rate of 1e-5. Regarding the optimizer, we use Adam W with a weight decay as le-2, adam epsilon as le-8, and a constant learn- ing rate scheduler. For datasets, we train Segmentation-to-Imagg (S2I) task ADE20K [99, 100], and Landmark-to-Faan (L2F) task on CelebV-HQ [101], both for 20 epochs, with 16 batch size. Specifically, we employ dropout (p2 0.1) and [PEFT]_on]] bias type on PEFT layers (BOFT, OFT, LoRA).
DreamBooth Instead of fine-tuning text transformer [20, 37J, we exclusively fine-tune the cross- attention layers (K, V. Q) of UNet with a learning rate of 3e-5, batch size of 4 for 2000 steps. Regarding the optimizer, we use AdamW with a weight decay as le-2 and Adam epsilon as 1e-8, constant learning rate scheduler. Furthermore, we pre-generate 200 images conditioned on each class of input images, for prior preservation training weighted by 1.0. We use the same dataset as DreamBooth [74] with the resolution of 512. Same ControlNet, employ dropout (p2 0.1)
and [ -only bias type on PEFT layers (BOFT, OFT, LoRA).
More Results For ControlNet, apart from Landmark-to- -oo Face (I.2F) generation, we also benchmark different fine- tuning methods on Segmentation-Be -oaamiioo------eeeeeeeee (S21) generation. The quantitative results are given in Table 9. Notably, these reported numbers represent the best possible results achieved by methods, across all variations of parameter configurations (#Param spans from 2M to 20M), trained for 20 epochs. We observe that different control task requires different finetun- ing flexbility and some control task may be easier than the other. We find that the S2I task is generally easier than the I.2F task and does not require strong finetuning flexibility. In the S2I task, the best performance of BOFT from 2M to 20M is similar to that of OFT. However, BOFT can still achieve better control performance than OFT given less amount of parameter budget, demonstrating its parameter efficiency.
Task
Metric
LaRA
OFT
BOFT
8 Params
2.52M
20.89M
20.76M
mioUU 1
24.72
29.44
28.83
S21
mAce f
37.88
42.12
41.24
aAce f
60.43
67.53
67.74
1,2F
Emor
8.038
6.407
5.667
Table Quantitative evaluation of 521 and 1.2.. The best results are marked with "bold", and the second best are marked "underline"
More qualitative results of ControlNet are shown in Figure 17 and Figure 16. Regarding DreamBooth, more subject-driven generations are shown from Figure 9 to Figure 15.
'htps://github..c httpss//gihuub..o//fteeeeee http://hww....ooooooooo////////p
"htpss//huggingffcc. co/docs/peft http:///www.........iii////aaaaa
20

---

Published as a conference paper at ICLR 2024
B MORE QUALITATIVE RESULTS ON HIGH-QUALITY SEGMENTATION
SAM
BOFTSAM
SAM
BOFT-SMM
NAM
BOFT ESM
SAM
ROFT:SMM
Figure Il: More qualitative comparison of mask prediction between SAM and BOFT-SAM.
21

---

Published as a conference paper at ICLR 2024
C
MORE QUALITATIVE ReSULTS IN SUBJECT-DRIVEN GENERATION
Text prompt: [V] backpack floating top of water
Text prompt: [V] buckpuck in the snow
Text prompt backpack top of dirt road
Text prompt: [V] lespot with tree and autumn leaves in the background
Text prompt: [V] teapot on top of wooden floor
Text prompt: [V] teapot top of dirt road
Input images
LoRA
OFT
BOFT
Figure 12: Qualitative compurison Subject-driven Generation.
22

---

Published as a conference paper at ICLR 2024
Text prompt: a [V] vase on cobblestone street
Text prompt: [V] vase top sidewalk crowded
Text prompt: a [V vase on of white
Text prompt: [V] sneaker top of dirt road
Text prompt: [V] sneaker top green grass with sunflowers around
a
Text prompt: [V] sneaker with city in the background
Input images
LoRA
OFT
BOFT
Figure Qualitative comparison Subject-driven Generation.
23

---

Published as a conference paper at ICLR 2024
Text prompt: [V] glasses with blue house in the background
prompt: [V] glasses
background
Text prompt [V] glasses on top of a white
Text prompt: a [V] toy the beach
Text prompt: shiny [V] toy
Text prompt: [V] toy with a wheat field in the background
Input images
LoRA
OFT
BOFT
Figure Qualitative comparison Subject-driven Generation.
24

---

Published as a conference paper at ICLR 2024
Text prompt: [V] dog with blue house in the background
prompt: [V] dog wearing
Text prompt: a [V] dog top of purple forest
Text prompt: [V] stuffed animal in the jungle
Text prompt: [V] stuffed animal floating on top
Text prompt: wet [V] stuffed animal
Input images
LoRA
OFT
BOFT
Figure Qualitative comparison Subject-driven Generation.
25

---

Published as a conference paper at ICLR 2024
D
MORE QUALITATIVE RESULTS IN CONTROLLABLE GENERATION
Text prompt: man with beard
AIR
GT
Cuntrol signal
LoRA
OFT
BOFT
Text prompt: with beard
P
signal
prompt: sunglosses
Mn2
GT
Control signal
LoRA
OFT
BOFT
Text prompt: a mun with grey hair and beards
GT
Cuntrol signal
LoRA
OFT
BOFT
Text prompt: with long bair
signal
BOFT
Text prompé:
Control signal
LoRA
OFT
BOFT
Text prompt: a woman wearing sunglasses and holding a rose
GT
Control signal
LeRA
OFT
BOFT
Text prompt: sunglasses and holding
d
Control signal
LaRA
BOFT
Figure qualitative landmark- generation.
26

---

Published as a conference paper at ICLR 2024
Text prompt: house
Control signal
LoRA
OFF
BOFT
Text prompt: brick building
Control signal
LoRA
BOFT
Text prompt: buildinng with stairs leading up to it
Control signal
LoRA
OFT
BOFT
Text prompt thomas train lisneyland wurld
Control
LoRA
OFT
BOFT
Text prompt: man with board
Control signal
LeRA
OFF
BOFT
Text prompt: people looking
Control signal
LoRA
OFT
BOFT
Text prompi: an empty room
Control signal
LeRA
OFT
BOFT
conference
Control
Figure 17: More qualitative results in seginnntation map to image generation.
27

---

Published as a conference paper at ICLR 2024
E MATHEMATICAL -HESTION-ANSWERIGG CASE STUDY
Example E.1:
Case Study
James buys packs beef that are pounds each. The price of beef $5.50 per pound. How much did he pay? (Ground-trut answer is 110)
Question:
Llama-2 Answer: James bought 5 packs of hcef that are 4 pounds each. The price of beef is $5.50 per pound.
So he paid 5 * 4 5.50 137.50 doilars. The answer is 137.50.
BOFT Answer: James bought 5 packs of beef, and each pack is pounds, he bought total of 5 4 20 pounds beef. The price of beef $5.50 per pound, so James paid 20 $5.50 $110. The answer 110
Example E.2:
Case Study 2
James decides to run sprints 3 times week. He runs 60 meters cach sprint. How many total meters does he run week? (Ground-truth answer is 540)
Question:
Llama-2 Answer: James runs 60 meters each sprint. So runs 60 180 meters each week. The answer
180.
BOFT Answer: James runs 3 sprints 3 times a week, so he runs 3 sprints x 3 times 9 sprints in week.
Each sprint is 60 meters, so James runs 9 sprints 60 meters 540 meters in week. Therefore, James runs total of 540 meters in week. The answer is: 540
Example E.3: Case Study 3
Carl buys packs of cookies. Each pack of cookies has six cookies inside. Each cookie cost $0.10. How much change does Carl receive if he pay with $10 bill? (Ground-truth answer
Question:
Llama-2 Answer: Carl buys ten packs of cnokies. Each pack cookies has six cookies inside. Fach cookie cost $0. 10. So he pays $10 for 60 cnokies. Now he gets 60 0.10 = $6 change. The answer $6.
BOFT Answer: Carl buys ten packs of cookies, he buys 10 60 cookies.The total cost of the cookies
is 60 * $0.10 $6. Carl pays with $10 bill. he receives $10 $6 S4 in change. The answer is:
Example E.4: Case Study 4
Miguel uses 2 pads of paper a week for his drawing. If there are 30 sheets of paper on a pad paper, how many sheets of paper does he use every month? (Ground-truth answer is 240)
Question:
Llama-2 Answer: Miguel uses pads of paper week. There 30 sheets of paper pad of paper. So he 2 * 30 60 sheets of paper every week. Now he uses 60 * 4 240 sheets of paper every month. The
answer is 240.
BOFT Answer: Miguel uses 2 pads of paper week, and there are 30 sheets of paper on a pad, so he uses 2 x 30 = 60 sheets of paper every week. Since there are 4 weeks in a month, Miguel uses 60 x 4 = 240 sheets of paper every month. Therefore, Miguel uses 240 sheets of paper every month. The answer is: 240
Example E.5: Case Study 5
Question: After transferring to new school, Amy made 20 more friends than Lily, Lily made 50 friends, how many friends do Lily and Amy have together? (Ground-truth answer is 120)
Llama-2 Answer: Amy made 20 more friends than Lily. So Lily had 50 20 30 friends. Amy had 30 + 20 50 friends. So Lily and Amy have 50 + 50 100 friends together. The answer is 100.
BOFT Answer: Lily made friends, and Amy made more friends Lily, then Amy made + 20
= 70 friends. Together, Lily and Amy have 50 + 70 120 friends. The answer is: 120
Example E.6: Case Study 6
Question: After Andrea saved some money, she then spent the of her money an $11 sweater and gave the beginning. how much did Andrea save? (Ground-truth answer 21) Llama-2 Answer: Andrea started with 36 dollars. She then saved some money. Then she spent the rest her money on an $11 sweater and gave her brother $4. So she spent 36 (saved money)- (sweater price)
her brother If she
(brother price) 36 10 11 4 11 dollars. The answer is 11.
BOFT Answer: After Andrea saved some money, she then spent the rest of her money on $11 sweater and gave her brother $4. she had $36 the beginning, how much did Andrea Save?Andrea saved $36 S11 $4 = Therrfreo,,,, Andrea saved $21. The answer is: 21
28

---

Published as a conference paper at ICLR 2024
F PROOF OF THEOREM 1
We first show that BOFT is always more expressive than OFT with the same block size. We write down the final orthogonal matrix BOFT with block size 2b:
RBOFr (,. b) II 1=1
(d, (d.2
(3)
=d, (d. (dd
where we can let (d, 2nm), m E m] to be identity matrices. Then we have
RBoFr(m, b) ....2"")..B(... 22) (d,2))
(d, 2)
which is orthogonal matrix with the block size 2b. This is exactly the orthogonal matrix used in OFT with the block size 26. Therefore, BOFT with m > 1 is always more expressive than OFT with the same block size. When m 1. BOFT reduces to OFT.
Then we proceed to prove that the following expression can represent any orthogonal matrix:
RE Ba- (dd) (d)
(5)
where (d) Vi, Vj are butterfly matrices. REst fall into the category of kaleidoscope matrices [14] (with the diagonal matrix being an identity). [14] has shown that the orthogonal kaleidoscope matrix can represent any orthogonal matrices. The overall proof idea is simple and be given by the following two results from [14]:
Any orthogonal matrix can be represented by QR factorization which can be decomposed by n Householder reflections.
All Householder reflections can be represented by B,) (d).
Then we can easily arrive the conclusion that RE can represent any orthogonal matrix.
29

---

Published as a conference paper at ICLR 2024
G MATHEMATICAL PROPERTIES OF BUTTERFLY MATRICES
Due to its nice spectral and numerical properties, butterfly structures (especially random butterfly matrices) are introduced by [63] to remove the need of pivoting in Gaussian elimination. In this section, discuss few intriguing mathematical properties of butterfly matrices. Because orthogonal butterfly matrices are a special subset of the orthogonal matrices, they introduce additional inductive biases that help further regularize the finetuned model. To gain deeper understanding of the induced inductive biases, we delve into the mathematical properties of orthogonal butterfly matrices with the hope to understand the effect of such additional inductive biases. We note that these properties are natural and direct consequences of the established results in [64, 83]. For our results to be self- contained, we also provide the brief proof of the results here.
G.1 BALANCED ENTRY-WIS LEARNING RATE
Butterfly matrices also have interesting balanced learning rate property. We take 8-dimensional butterfly matrix as an example. Assume that we fill all the entries in each butterfly component with
0
1
0
0
0
1
0
0
1
0
0
0
0
0
1
1
0
1
0
0
0
0
0
0
0
1
0
0
1
10090
000
0
1
0
0
1
0
0
0
1
0
1
0
1000
20010
0
1
1
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
1
O
0
0
0
0
0
0
0
0
1
1
1
1
which means that the butterfly matrix preserves the learning rate in each entry of the butterfly component. For block butterfly matrices, we consider the following example:
1
0
0
1
1
0
1
0
0
2
2
2
2
2
2
2
0
2
2
2
0
0
1
1
0
0
1
1
1
1
1
0
0
0000000
2
2
2
2
2
2
2
2
1
0
1
0
2
2
2
1
0
0
1
0
0
0
0
1
1
2
2
2
2
2
2
2
0
0
1
0
0
1
2
2
2
2
0
1
0
0
0
0
1
2
2
2
2
2
0
1
1
0
0
1
2
2
2
2
which shows that the product of all-one block butterfly components still have the balanced learning rate property. However, we also note that whenever we initialize butterfly component, the elements not the same (Each butterfly component is initialized as an identity matrix). While butterfly matrices have the property of balanced entry-wise learning rate, we note that the same property does necessarily exist for general sparse matrix factorization.
G.2 AN ALTERNATIVE DEFINITION OF ORTHOOGNNAL BUTTERFLY MATRICES
In the main paper, we define the butterfly matrices by first constructing the pattern of non-zero elements each butterfly component and then constraining each block matrix as an orthogonal matrix. Alternatively, orthogonal butterfly matrices also be defined in reverse order by first constructing orthogonal matrices and then build the butterfly matrix from ground up.
30

---

Published as a conference paper at ICLR 2024
Definition (Generalized Rotation Matrix), A generalized rotation matrix is a N x N matrix (N is even) of the following form:
C ş - d.
(6)
N where C and S are commuting, symmetric real matrices of the size 2 x 2, The scalar rotation matrices use scalar matrices C, C. The diagonal rotation matrices use diagonal matrices C.S.
N and C² + S I.
Definition (Orthogonal Butterfly Matrix), An orthogonal butterfly matrix, denoted collectively as OB(N), iteratively defined matrix of order N 2"
CA1 -SA1
SA₂
C -
s C
A 0
CA
A
where A2, E OB ), and [-s
S
is generalized rotation matrix. An orthogonal butterffy matrix is simple if A = A each iteration step, and is non-simple otherwise. When = 1, the orthogonal butterfly matrix is defined as 1.
C
Definition (Diagonal and Scalar Butterfly Matrix), The diagonal and scalar butterfly matrices are the orthogonal butterfly matrices constructed iteratively with diagonal and scalar rotation matrices, respectively. We denote the order-N simple scalar butterfly matrices as OB, For B (B,(N,, (
we define B OB(A,0) 0) where A OB, (
if B is of the following form:
(O) sin (0) A
(OS
sin(0)
A
0
sin( cos( A =
(
cos cos(0)
(0)
A
(8)
A
cos(O)
(0)
sin
A
(0)
cOs
(0)
We use OB(N) to denote the non-simple scalar butterfly matrices.
We also define that
7
OB(O)
OB(n 18(n-i+11 =B(0)) ... OB(O))
where & denotes the Kronecker product and OB((,)) E SO(2).
Remark 1. We note that the butterfly matrices considered in the main paper is what define as non-simple diagonal butterfly matrices here. Despite not directly discussing the properties of such family of butterfly matrices, aim to provide some useful insights through few necessary simplifications.
G.3 TOPOLOGICAL PROPERTIES
Proposition ([64]). OB(N) and OB, (N) are compact spaces in SO(N), which are homeomorphic quotients of higher dimensional tori T and T- where N 2n.
Proposition 2 ([64]). The diagonal simple and non-simple butterfly matrices are compact spaces in SO(N), which are homeomorphic to quotients of higher dimensional tori N and T Nn (N 2*). respectively.
These two propositions characterize the topological properties of orthogonal butterfly matrices. There also many interesting group properties. For example, OB, (N) is compact abelian subgroup of SO(N). These topological and group structures and connections provide many unique inductive biases for the orthogonal finetuning.
31

---

Published as a conference paper at ICLR 2024
G.4 INPUT SENSITIVITY
One interesting property to study for the butterfly matrices how the input parameter changes the output matrix norm. Specifically, can upper bound the difference between the input-perturbed butterfly matrix and the original butterfly matrix. Specifically, we have the following result from [64]:
Proposition (Upper Bound for Simple Scalar Butterfly Matrices). Let OB(O) (B,((N) and E R" where N = 2", Then have that
IIO((0) OB + +)]l S V [|l|]
(10)
Proposition 4 (Upper Bound for General Scalar Butterfly Matrices), Let OB(O) E OB(N) and ERN-1 -Thn have that
OOB(0) OB(( + +)llp S VN
||||2
(11)
The above two propositions show that the map 0 - OB(() is Lipshitz continuous.
G.5 RANDOM ORTHOGONAL BUTTERFLY MATRICES
Definition 4 (Random Orthogonal Butterfly Matrix). A random orthogonal butterfly matrix is butterfly matrix that is generated by random generalized rotation matrices with
Σ == { S3h221
(12)
which is an independent sequence of pairs of matrices. Each pair {C,, generates a random generalized rotation matrix of order 2
32

---

Published as a conference paper at ICLR 2024
H ILLUSTRATION OF BLOCK BUTTERFLY MATRICES
We provide an illustration for block butterfly components and matrices Figure 18.
6(1
B(16,8)
B(16,4)
B(16,2)
(a) 16-dimensional butterfly matrix with the block size
1-88,8)
(8
(b) 8-dimensional butterfly matrix with the block size 2
844444
B4442)
(c) 4-dimensional butterfly matrix with block size
Figure butterfly components black
33

---

Published as a conference paper at ICLR 2024
I MORE RESULTS ON EXPRESSIVENESS OF BOFT
We use full dense orthogonal matrix to finetune DINOv2 on downstream tasks and then obtain such dense orthogonal matrix (with 10 random seeds). We finally obtain 10 finetuned 1024 x 1024 dense orthogonal matrices and conduct the same experiment as Figure 5. The results in Figure 19 still validate that BOFT yields better expressiveness under the same number of parameters.
1,8
1.75
BOFT (1:10,2
Rescaled
1.7
BOFT (1:7. 16) (1:5,6))
(1:944 4)
1.6
Number of trainable parameters
Figure 19: Expressiveness of BOFT for learned dense orthogonal matrices (10 random seeds).
34


Reviews:
[{"review_id": "W7Abo1TuzB", "reviewer": "Reviewer_mHgj", "summary": "This paper is an extension to [Orthogonal Finetuning (OFT)][oft], which involves modulating a pretrained weight matrix by multiplying it with an orthogonal matrix during finetuning; updating only the orthogonal matrix during finetuning. OFT, for efficiency reasons, parameterise the orthogonal matrix with a block-diagonal structure, with each block using a Cayley parameterization:\n$$\nR = (I+Q)(I-Q)^{-1}\n$$\nwhere $Q$ is a skew-symmetric matrix. The complete orthogonal matrix therefore becomes $\\text{diag}(R_1, R_2, ..., R_r)$.\n\nBecause this orthogonal matrix is an arbitrary choice, the authors state that \"it makes no sense to divide the dimensions of a neuron into $r$ groups based on their indices\". This paper aims to produce a dense orthogonal matrix parameterization.\n\nTo that end they suggest a butterfly parameterisation, where each stage connects each unit to itself and another unit, through which information may flow from any two units after enough stages; inspired by the Cooley-Tukey Fast Fourier Transform. \n\nThis improvement to OFT is tested by experiment on large language model finetuning for natural language understanding (GLUE), multitask language understanding (MMLU) and mathematical question answering (GSM8K and MATH). It is tested on a vision foundation model (SAM) classification (VTAB-1K) and segmentation (HQSeg-44K). Adapting a diffusion model (stable diffusion) was tested on controllable generation and subject-driven generation. BOFT performed better in most comparisons, except for some results on VTAB-1K and was outperformed by LoRA on some GLUE and MMLU benchmarks.\n\nIn general it was demonstrated as a competitive method for finetuning and a definite improvement over OFT.\n\n[oft]: https://neurips.cc/virtual/2023/poster/72033", "questions": "I would expect that one of the main motivations for a butterfly parameterisation would be the reduced memory usage at inference time. Unfortunately, I'm not sure this method allows that, as it still requires that the original weight matrix is multiplied with the butterfly factorized matrix before being applied to the inputs. Is there any way this method provides some inference time savings?\n\nIn Section 5 when approximating random dense matrices, what distribution are the matrices drawn from, and is that distribution a good choice for modeling the types of matrices found in deep neural networks or orthogonal deep neural network adapters?\n\nIs there any significant extra computational cost to matrix multiplying the original parameters with the orthogonal matrix adapter? I realise this would be the same issue OFT would have.\n\nHow do you train the butterfly parameterisation in practice? In most autograd frameworks a naive implementation would have a massive memory cost because each layer of the butterfly transform would require it's own cached activations.\n\nDo the spectral properties of LoRA mean it should systematically fail in some way? Can you demonstrate that experimentally and show how BOFT doe not?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "The paper provides a good review of other methods employing butterfly parameterisations in the literature and the relative benefits such a parameterisation provides. The description of the parameterisation in Section 3 is thorough and well paced. This appears to be an original and valuable way to apply the parameterisation in deep learning.\n\nExpressivity analysis in Section 5 is a valuable contribution, identifying an advantage over OFT and making a strong argument for better performance over LoRA. This is supported by the experiments in Section 6.\n\nFinetuning large pretrained models is a valuable area of research, it has become neither necessary nor practical to train a model from scratch on new problems. This method extends the work on orthogonal finetuning in a valuable direction and demonstrates that it is effective.", "weaknesses": "The information transmission framework listed as the first contribution of the paper is described as novel but I would argue this is connectivism. A similar figure can be found in every book on deep learning, for example opening Goodfellow's [Deep Learning book][goodfellow] there is a figure on page 170 that describes a bipartite connectivist diagram like this. It's possible I am missing something though.\n\nOFT is described well, but it appears too late. It is mentioned early in the paper but a quick description of it comes much later, on page 3. This could be easily fixed by putting Figure 1 earlier. The entire premise of the paper could also be introduced early in that case by putting an illustration of the butterfly parameterisation along with Figure 1 and referencing it on the first page.\n\nTable 5 is in the wrong place, it sits next to a description of the VTAB-1K task, but presents results on the next task. Wrapped figures and tables are used extensively in the paper, which can work well because the results are close to the text referencing them but they need to be placed correctly in that case.\n\nThe paper extends OFT but the improvement appears to be incremental, with minor performance gains on competing methods. The authors mention the spectral benefits of this method over LoRA but do not explore this in detail in experiments, looking only at benchmark results.\n\n[goodfellow]: https://www.deeplearningbook.org/", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "UTEuV8Gprl", "reviewer": "Reviewer_oVSz", "summary": "The authors tailor Orthogonal Fine-tuning to a parameter-efficient fine-tuning (PEFT) technique called Orthogonal Butterfly (BOFT) that is motivated from the Cooley-Tukey algorithm to perform fast Fourier transform, showing convincing potential as a PEFT approach.", "questions": "I just wonder whether or not BOFT can outperform LoRA (r=64) in Table 2 and 3 as well.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper for the first time proposes BOFT, a PEFT method inspired by orthogonal fine-tuning and the Cooley-Tukey algorithm, and shows the performance of BOFT on various applications from computer vision to natural language processing.", "weaknesses": "The ability to switch different tasks efficiently would be lost in BOFT due to the fact that BOFT is based on multiplication whereas LoRA is based on addition.\n \n\nFor the MMLU dataset, the performance of Llama 2 13B and/or Llama 2 70B should be given, because PEFT methods are designed for fine-tuning large language models. The performance comparison of Llama 2 7B seems not to be enough.\n \n\nThe ablation study of $b$ and $m$ of BOFT seems to be necessary because all different $b$ and $m$ of BOFT are chosen in Table 2, 4, and 5, ,which implies that BOFT seems not to be practical compared to LoRA.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "8VDC1kZgfe", "reviewer": "Reviewer_CCPY", "summary": "The paper attempts to analyze Orthogonal Finetuning from an information transmission perspective and proposes an efficient orthogonal\nparameterization using butterfly structures. Their framework transforms the task of crafting a parameter-efficient dense orthogonal matrix into an information transmission problem within a grid-structured graph and also provides theoretical insights. Very interestingly, with similar block size, the authors have demonstrated better performance of BOFT in comparison with OFT.", "questions": "See above.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "Firstly, I appreciate the work including a good amount of experiments to show the effectiveness of BOFT. The paper is well written and the appendix provides significant experimental details. Application to SAM is interesting and useful. The motivation behind Orthogonal Butterfly technique is nicely explained.", "weaknesses": "One major concern I have is, in comparison with LoRA, I can immediately see the benefit due to a reduction in #Params but with OFT with comparable params, I see a marginal performance gain. I am not sure if OFT will be able to outperform the proposed method with some hyperparameter fine-tuning. OFT-SAM is missing in Table 5, and I would recommend authors to add the results for completion. I also have some novelty concerns with the work considering OFT, since the proposed method doesn't provide a noticeable gain over OFT. One question to authors, if there exists some b for OFT that can outperform BOFT with some m, b with similar #params, or BOFT always beats OFT with comparable params.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)