Efficient Low-rank Backpropagation for Vision Transformer Adaptation
Authors: Yuedong Yang
Hung-Yueh Chiang
Guihong Li
Diana Marculescu
Radu Marculescu
Venue: NeurIPS 2023 poster (2023)
Keywords: Low-rank backpropagation
model adaptation
transfer learning
vision transformer
Edge AI

Abstract: The increasing scale of vision transformers (ViT) has made the efficient fine-tuning of these large models for specific needs a significant challenge in various applications. This issue originates from the computationally demanding matrix multiplications required during the backpropagation process through linear layers in ViT.
In this paper, we tackle this problem by proposing a new Low-rank BackPropagation via Walsh-Hadamard Transformation (LBP-WHT) method. Intuitively, LBP-WHT projects the gradient into a low-rank space and carries out backpropagation. This approach substantially reduces the computation needed for adapting ViT, as matrix multiplication in the low-rank space is far less resource-intensive. We conduct extensive experiments with different models (ViT, hybrid convolution-ViT model) on multiple datasets to demonstrate the effectiveness of our method. For instance, when adapting an EfficientFormer-L1 model on CIFAR100, our LBP-WHT achieves 10.4\% higher accuracy than the state-of-the-art baseline, while requiring 9 MFLOPs less computation.
As the first work to accelerate ViT adaptation with low-rank backpropagation, our LBP-WHT method is complementary to many prior efforts and can be combined with them for better performance.

Efficient Low-rank Backpropagation for Vision Transformer Adaptation
Yuedong Yang Hung-Yuel Chiang Guihong Li Diana Marculescu Radu Marculescu
Chandra Family Department of Electrical and Computer Engineering
The University of Texas at Austin
{al bobeertyoun.huunguuen chiang, 1gh, di diamam, radum) (addummSuuteaaa Suteeattteaeea..ee edu
Abstract
The increasing scale of vision transformers (ViT) has made the efficient fine- tuning of these large models for specific needs significant challenge in various applications. This issue originates from the computationally demanding matrix multiplications required during the backpropagation process through linear layers in ViT. In this paper, tackle this problem by proposing Propagation via Walsh-Hadamard Transformation LLBP-WHT) method. Intuitively, LBP-WHT projects the gradient into low-rank space and carries backpropaga- tion. This approach substantially reduces the computation needed for adapting ViT, matrix multiplication the low-rank space far less resource-intensive. We conduct extensive experiments with different models (VIT, hybrid convolution-Ve model) on multiple datasets demonstrate the effectiveness of our method. For instance, when adapting an EfficientFormer-Li model on CIFARIOR our LBP- WHT achieves 10.4% higher accuracy than the sfate-of-the-ar baseline, while requiring MFLOPs less computation. As the first work to accelerate ViT adapta- tion with low-rank backpropagation, our I.BP- -H' method complementary many prior efforts and can be combined with them for better performance. Code: https::/githhee httpbbbttttuuut/// com comm/SLrrrouppLLP--tti
Low-rank Back-
Introduction
Vision transformers (ViT) have emerged as the latest ofate-of-the-art tool in numerous general computer vision tasks [177] However, tailoring these models to meet specific needs (e.g., new dataset with different distribution) can challenging. Indeed, adapting ViT models via finetuning demands considerable computational resources and is often impractical for most edge applications. For instance, to maintain privacy, federated learning IH model adaptation is limited to users' personal edge devices (e.g., smartphones), where computational power is tightly restricted [1] 12]
The primary computational bottleneck arises from gradient propagation through the dense layers of ViT. Specifically, calculating gradients for layer weights and inputs requires two computationally- intensive matrix multiplications, given the gradient for output [13]. To tackle this issue, 14] tries to simplify matrix multiplications using low-rank reparametrization. However, this method only reduces the gradient computation for weights and not for inputs, thus limiting the overall speedup. This observation raises the following question:
How decrease the computational cost for all operations, including gradient computations for weights and inputs, involved in backpropagation (BP) through any linear layer in the ViT model?
To answer this question, we introduce Tronsformation (LBP-WHT) method. As shown in Figure [ our method intuitively performs BP for gradients w.r.t. inputs and weights in a low-rank space. To achieve this, project the gradient w.r.t.
Low-rank BackPropagation via
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

the output into low-rank space using WHT [1]], then perform low-rank matrix multiplications, and finally project the results back. This way, all matrix multiplications occur in low-rank space, hence the computational cost is significantly reduced. In summary, our contributions are as follows:
We propose LBP-WHT, new approach which greatly reduces the computational cost for adapting VIT while maintaining accuracy; our method lowers the computational barrier and enables adapting large ViT models on resource constrained edge devices.
LBP-WHT is the first work accelerating ViT training by low-rank BP; thus, LBP-WHT is orthogonal to prior works and can be combined with them for better performance. Additionally, LBP-WHT offers abundant flexibility that can provide a good tradeoff between accuracy and cost.
Extensive experiments on multiple datasets demonstrate the effectiveness of our method. Indeed, LBT-WHT consistently outperforms the baseline methods both in accuracy and speed. For instance, LBP-WHT achieves 10.4% higher accuracy, while requiring 9 MFLOPs less computation CIFAR 100 dataset.
than 14 for training EfficientFormer-LI
The paper is organized as follows. Section 2 formulates the problem associated with BP for linear layers. Section 3 presents our method LBP-WHT in detail. Experimental results are presented in Section Section 5 reviews relevant work. Finally, Section summarize our main contributions.
2 Problem Formulation
Naming conventions: In this paper, we treat all feature maps matrices composed of real numbers, with dimensions RCCL, where C represents the number of rows and I. denotes the number of columns. Each row in the matrix is regarded as a "channel" consisting of L. elements, and there are total C' channels in the feature map. We use subscripts to identify specific variables, such as C₂ for the number of channels associated with variable x. Gradients with respect to are denoted by Ja. with the subscript indicating the target variable æ.
Backpropagation for linear layers:
We focus on the BP process for linear layers, a crucial building block for vision transformers. Given an input x E RC,x*. and weights w CBCxxCC, the forward propagation to compute the output E RC xL can be expressed as:
y = w
Therefore, shown in Figure Z. given the gradient with respect to the output y, i.e., By C the back-pu proppprppgtttion for computing the gradient with respect to the weights w, Iw RCxCC, and the gradient with respect to the input x, Ix E CRCx xI, can be represented as two matrix multiplications:
Iw
By x. 9
9y w
The gradient w.r.t the weight (gw) is utilized for updating the weights w. while the gradient w.r.t. the input (g.) is employed for propagating the gradient to other layers. During the BP process, each matrix multiplication incurs a computational cost of ,C,,C,,LL FLOPs, which amounts to C, FLOPs, in total. Given that in VIT models, the number of channels (O, and Cy)) and the length of the input feature map (L) are substantial [17] the computational cost for BP becomes significant.
Low-rank backpropagation: As shown in andd we propose reducing the computational cost for both matrix multiplications by employing low-rank approximations. Specifically, we first project variables into a low-rank space as follows:
Gradient w.r.t.
Low-rank Back Propagation via WHT
output
WHT Low-rank
ir, p(g,), i p(r)
Projection
Mat Mul
Here, By E CR and f xx, represent the low-rank space projections (R << L) for the gradient with respect to the output (gy) and input æ, respectively. The projection function p(-) will be introduced in the next section.
WHT Reverse Projection
Gradient w.rtt input & weights
Next, we execute the BP through the linear layer in the low-rank spaces follows:
Figure 1: Our LBP-WHT. (4)
gw 9y 2r gv
"Mat Mul" is short for "Ma- trix Multiplication..

---

(a) Vanilla BP
X
gw
Full-rank
9y
Matrix Mul
9x
W
(b) LBP-WHT
X
P()
X
gw w
2
9y P()
P
9x
W
Low-rank
Low-rank
Reverse
(c)
Projection
Matrix Mul
Projection
Figure 2: (a-b) Workflows for BP through a linear layer utilizing (a) the conventional method and (b) our LBP-WHT method. The intuition is to reduce the computation cost for BP by performing matrix multiplication in low-rank space. To achieve this, we first project variables into a low-rank space using WHT p(-), then carry out efficient matrix multiplications, and finally project them black using p (-). where both and are implemented with WHT. (c) Bases B for order-4 2D WHT. White and Black represent +1 and -1, respectively. Of note, in the context of ViT, 2D feature maps are flattened into ID, so we utilize a flattened version of these bases.
Finally, we project the low-rank gradient with respect the input (gz) back into its original space. The reverse projection for 9w can be omitted as already exists in the same space I RCxCC= as the target Imu For ÿa. the reverse projection is accomplished using the function p p-), the details of which will be presented later:
fN = Sw.
- D2 p (fw)
Here, fw and JR represent the resulting gradients for weights and input. As these gradients are generated through an approximated proppaaaaatnonn process rather than the standard BP, we denote these variables with tildes.
3 LBP-WHT: Low-rank BackPropagation via WHT
As shown in Figure intuitively, we reduce the computational cost by performing back pack-propagation in low-rank space, as described in Equation T For instance, using rank I approximation, each matrix multiplication requires CC FLOPs, which can be substantially smaller than 2C2C,, when R < L. Nevertheless, this approach necessitates two additional steps, projection and reverse projection (as illustrated in Equation 3 and 5). which introduce some computational overhead. Furthermore, the low-rank projection may add noise and potentially diminish the quality of training. To address these concerns, our method incorporates a low-overhead projection function based on the WHT and tackles the second issue by selecting appropriate set of WHT bases.
WHT is generalized Fourier transformation. Figure P displays the transformation basis for an order-4 WHT. For order-n 2D WHT, there are n bases Bi.j. with each basis being an n a matrix containing only +1 and 1. Of note, the context of ViT, 2D feature maps are flattened into ID maps, i,j n. WHT possesses four properties that make it advantageous for
utilize flattened WHT base-a vector with length of n², i.e.
B E n
The transformation bases are complete.
The transformation bases are orthogonal.
The transformation bases contain only +1 and -1
The transformation cost can be reduced via fast WHT algorithm with O(n log n) complexity.
The first property (completeness) allows WHT to perform transformations ranging from lossy (when few bases are activated) to lossless (when all bases are activated). This grants flexibility in exploring the trade-off between efficiency and accuracy. The second property ensures that any variable has precisely one projection result, obtainable via matrix multiplication. For instance, the projection

---

function for 9y (Equation with basis B. can be expressed as plgy) = 9, B.y. Likewise, the reverse projection can also be implemented using simple matrix multiplication. The third and final properties demonstrate the efficiency of WHT implementation, requiring only O(n log aadittions/uubraacioons and no multiplications [66
3.1 Low-rank Paop-propngttion with WHT
Indeed, these four properties demonstrate that WHT an ideal fit for our needs, offering both low overhead and high flexibility for selecting an appropriate set of bases. Therefore, we employ WHT as the projection function p(-) and reverse projection function p (-) in Equations 3 and More specifically, for order-n WHT with a set of R bases chosen by index set I, the projection function can be written as:
p(x) = - x (Bigh Big ... ...B.R.i) (ix. ju) E EI,1sk5
(6)
where I = [(k 11 S ik. S nn nn k < R} indicates which bases are activated. Similarly, the reverse projection function can be expressed as:
(x) WHT
(Bi Bazd ... Binda) (ik,, EZ,I (7)
7 are presented using the vanilla WHT algorithm with com- putational complexity O(n²), rather than the fast WHT algorithm with complexity O(n log n). Consequently, our LBP-WHT algorithm can be summarized as Algorithm also shown in Figure
For simplicity, both Equations [ and
Algorithm 1 Backpropagation through linear layer with LBP-WHT.
Input: Input I, weight w, gradient w.r.f. output Py- Selected WHT base indices I Output: Approximated gradient w.r.t. input Iz. approximated gradient w.r.t. weight On f <- p(x) WHT
Projection to low-rank space with WHT (Equation
9y + -p(gy) = (HT(
fw < Fy
1..' .
b Efficient matrix multiplication in a low-rank space (Equation 4
ON Jy
GR p ((xx) WHT (gn; I)
Reverse projection to full-rank space (Equation 5) b Skipped reverse projection since I.r is already in full-rank space
Iw + IN
Given input for BP, we first project x and into low-rank space (Equation then we performs matrix multiplication (Equation 4) and lastly project the results back (Equation
3.2
WHT Bases Selection
Here we explore two types of basis selection strategies: low-pass and low- www.issiiiiieerrrr.
Low-pass (LP) Base Selection: Natural images have strong spatial locality, iee. pronounced low- frequency components [8]. We take advantage of this feature and choose bases with stronger low-frequency responses, which have smaller indices as illustrated in Figure D.. More specifically, consider both L1 -bsed and To low-pass basis selection strategies (LPr,, and L. .......:
It f( li + lis S r, < is. S <n), LPL, selection I (().. max(ia. (&) S 1 < ia. Ja S n. }, L.P,, -r selection Ir, and Ir the index sets for selecting WHT bases, described in Section 3.1 For example, with LPr,, base selection, three bases are chosen, i.e., It, = (0, (0, 1), (1, UJ.. and the rank for projection, namely R, is three.
(9)
Low-heuristic-error (LHE) Base Selection: According to Parseval's Theorem 19]. WHT preserves the signal energy, so by selecting the WHT bases with the top-r strongest responses, we can preserve most energy during low-rank projection and minimize the error. Since profiling the energy for all profile the energy for all WHT bases only for
WHT bases all training steps is expensive, small number of training steps and select the bases with the top- R energy.
Considering that the L, -bsed low-pass basis selection has much lower profiling overhead than the now-heuristic-erron basis selection and provides finer granularity balancing accuracy and efficiency, primarily focus on the LPz, selection method and explore the other two in Scction 4.5

---

3.3 Overhead Analysis
Since the computational cost for the fast WHT algorithm depends on the basis selection, we simplify the analysis in this section by considering the matrix multiplication-bast based vanilla WHT algorithm, shown in Equations 6 and 7 Table 1 presents the computation requirements for a linear layer with imput and output channels C₂ and Cy. feature map size L, and the rank for low-rank WHT approxima- tion Our LBP- WHT achieves
FL.PPs 4C,CyL
Vanilla BP
Projection Low-rank MM
CC + CGYLR 4C,C,,R C,LR
Reverse Projection
Table 1:
Computation required by vanilla BP and components in our LBP- WHT. We consider the projection and reverse projection as overhead. "MM" is short for "Matrix Multiplication".
times speedup with an overhead of (2C² + Cy) FLOPs, which is only (2C,+C,)LR CC,C, or J + xC, R of the total computation re- quired by vanilla BP. Given that ViT typically has a large number of channels, the overhead is very small.
For instance, the final linear layer in Swin V2-smal [ consists of 3072 input channels, 768 output channels, and a feature map size of 49, which means C22 = 3072, C, = 768, and L = 49. As per Table D conventional backpropagation (BP) requires 462.3 MFLOPs. In contrast, our Low-Rank Backpropagation with WHT (LBP-WHT) method, assuming rank of 8 (R 8), needs only 78.2 MFLOPs, which is roughly 16.9% of the computation required by vanilla BP.
Breaking down the 78.2 MFLOPs for LBP-WHT, we see that 1.5 MFLOPs are needed for the low-rank projection, 75.5 MFLOPs for BP in the low-rank space, and 1.2 MFLOPs for the reverse projection. The combined overhead 2.7 MFLOPs, accounting for just 0.6% of vanilla BP's computation and 3.5% of LBP-WHT's computation. This demonstrates that with WHT, we can significantly reduce the computation for BP while incurring negligible overhead for low-rank projection.
4 Experimental Results
In this section, we first present our experimental results on image classification and semantic seg- mentation tasks. Then, we explore the impact different ranks for low-rank projection and different base selection strategies. Lastly, present our preliminary results for deploying our methods on real edge devices the supplementary material.
4.1 Experimental Setup
Environment: We setup our environment with PyTorch 1.13, MMClassification v0.25 and MMSeg- mentation vO.30. Models are trained with an NVIDIA-A6000 GPU.
Classification: We conduct experiments for image classification following 20 We Ima-
geNet prettrred ViTs and finetune them on six different datasets, namely, CIFAR100 [22] (CF100), CIFARIO 22 (CF10), Cars (23), Flowers (24), Food (25). and Pets [26]. We standardize
the image resolution across all datasets to 224.224, Each model is finetuned for 50 epochs using the
AdamW W [27 optimizer and a batch size of 64. The learning rate adjusted for each dataset based on
the performance of EfficientFormer-L1
228 with vanilla BP.
Semantic Segmentation: We use the ADE20K 29 -pretrained Segformer-mit-bo 30 model and
(City) and the enhanced Pascal- VOC 2012 32 (VOC12A). The images are downscaled and cropped size of 512x512 pixels for training. Models are finetuned for 20,000 steps using the Adam W optimizer and batch size of 8.
finetune it on two datasets, Cityscapes 31
We primarily report on the results of training the final stage of the ViT using various methods, a common approach in transfer learning to reduce the computational cost [8] 33/.6). More results for full training are included in the supplementary material.
Partial Training:
Baselines Comparisons: We compare our results against three baseline methods: Full BP, "LoRA", and "LoRA-alI". Full BP refers to training the model with standard full-rank backpropagation. "LoRA" and "LoRA A-al" are methods derived from [4]. "LoRA" strictly follows [14), which uses low-rank reparametrization solely in the ViT's attention modules, while method to all linear layers. For hybrid ViT models, where the attention modules are usually only in the final stage, use "LoRA-all" for full training.
applies this
5

---

Partial Training: Training the Last Stage
Model
Method
Speedup
mAce
MFLOPs
CF100
CF10
Cars
Flowers
Food
Pets
Full BP
1.0x
36.66
1685.01
79.28
95.23
84,80
95.50
84.04
93.13
Efficient Former 28
LoRA
8
6.9%
79.59
242.61
65.25
87.40
65.76
90.16
76.46
92.50
LoRA-all
1.7x
85.97
976.50
76.92
94.38
76.84
93.56
81.50
92.64
L1
LP,. 2*
3
7.2%
85.50
235.62
73.61
93.35
76.36
95.07
79.65
92.34
(Hyhrid)
LP,,
10
3,5%
87.76
480.00
78.27
94.60
82,60
95,53
82.37
93.16
LP 88
36
1.2x
88.62
1397.02
79.34
95.31
84.57
95.58
83.98
92.94
Full BP
1.0%
91.91
11071.73
86,40
97.61
87.48
97.19
88.58
94.22
Efficient Former 28
LoRA
8
2.0%
88.45
5520.52 52
81.66
95 44
78. 95
95.82
85.15
93.65
LoRA-all
1.9%
90.36
5973.40
85.09
97.10
83.66
96.16
86.60
93.54
L77
2*
9.2%
89.88
1202.83
83.78
96.73
83.02
96,35
85.38
93.84
(Hyhrid)
LP,, 4
10
3.8%
91.16
2905. 16
85,10
97 22
86.01
97.14
87.48
94.03
LP
1.2%
91.80
9241.53
86.19
87.32
97.40
87.77
94.47
Full BP
1.0%
84.27
454.64
72.37
92.63
75,90
92.73
81.44
90.52
Efficient Former
LoRA
8
2.2x
74.42
206.29
60.74
84.89
$2,99
86.47
72.23
89.18
LolA
1.5x
78.94
313.19
65.51
63.49
76.88
89.89
50
LF,,-
3
4.37
77.35
59,99
63.75
88, 68"
"59.02
89.31
"74.72"
87.45
(Hybrid)
LP,, 4**
10
2.7%
81.29
168. 60
69.03
90.88
68.34
90.73
79:45
89.29
LPL, 8
1.1x
83.7%
405.84
71.90
92.29
74.31
11.07
90.52
Full BP
1.0x
91.03
3605 86
82.26
96.
88.78
96.80
94.60
Efficient Former
LoRA
2.5%
84.74
1469.66
74.35
92.94
70.99
92.97
82.81
94.36
LolA
1.7x
87.94
2092.47
78.97
80.39
84.94
94.03
1.
LP 2*
6.8%
86.88
535.61
78.00
9. 28
766.05
99,36
",,.14"
54,77
(Hybrid)
LPL, 4***
10
3.3x
89.47
1088 06
80.15
95.54
84, 64
95.97
85.85
94.66
LP
36
1.1x
90.79
3150.95
82.24
96.02
87.34
96.68
87.41
95.07
Full BP
1.0x
90.62
3896.51
80.84
96.07
85.35
97.61
88.31
95.53
SwinV2 !
LoRA
2.4%
78.00
1600.19
68.50
89.62
54.15
83.77
79.81
92.15
Small
LoRA-all
2.0x
84.86
1974.72
73.33
92.29
74.78
90,99
84.61
93.16
LP 2**
3
3,3%
90.32
1 1166.98
80.23
95.65
83.30
97.50
88.06
95.15
(VIT)
LPL, ****
10
2.5%
91.43
1535
80.39
95.71
85,30
97.54
88.32
95.34
LPL,-8
36
1.3x
90.60
2932.88 84
$0.80
85.72
97.56
18.19
95.53
Full Training
Effcient
Full BP
1.0x
89.19
2259.99 93
84,06
96. 88
84,80
93.62
84,99
90.79
V2 37
LP 10
LoRA
1.9%%
1.2x
778.56
86.07
7186.88
1899.99
12.93
81.14
92.67
96.27
551.7
76.25
99..8
74.66
90.27
89.34
S0
(Hybrid)
LPL, LPL,-8
28
1.2%
87.86
1833.31
83.14
96.53
80.69
92.21
83.76
90.84
36
T.I
88.56
2116.41
83.42
96.76
83.00
92.75
84.27
91.14
Table 2: Results for image classification. "LPr,,-r" refers to our LBP-WHT method with I.I,, -r base selection
outlined in Equation [ "mAcc" represents the mean accuracy across all datasets. "R" is short for "rank". "Hybrid" represents CNN-VIT -VI--hybrid architecture. Results outperforming both LoRA and LoRA-all in speed and mAcc are underlined and marked with *. Those exceeding all LoRA methods get * Results that have higher speed or mAce are highlighted in bold. More results are included in the supplementary matcrial.
To determine the compu- tational requirements of different models and methods, we run model training on an Intel 11900K CPU and measure the exact FLOPs using the embedded performance tools "perf" the Linux kernel v5.15.87. For preliminary deployment results, we test method on the last two linear layers of EfficientFormer-L. using OpenBLAS and CuBLAS for CPU and GPU testing respectively on an NVIDIA Jetson Nano. The results for deployment are reported in the supplementary material.
Computation Measurements and Preliminary Deployment Results:
4.2 Image Classification Results
Table Somleeddemosttrtte the effectiveness of our LBP-WHT method in adapting ViT for image classifi- cation tasks. Here some more specific observations:
Comparison with LoRA- -ased baselines: Our LBP-WHT method consistently surpasses the LoRA- based method across all cight datasets in both partial and full training modes. For instance, when only training the final stage of EfficientFormer-L. LBP- WHT using LP,, -2 base selection requires 8.9 MFLOPs fewer computations than LoRA, yet achieves 10 % greater accuracy on the CIFAR 100 dataset. When the entire model is trained, the accuracy difference is smaller, but LBP-WH still outperforms the LoRA-based method. For instance, in comparison to LoRA-all, LBP-WHT using LP, r,, 7 base selection requires less computation (66.68 MFLÖPs), but still improves accuracy by 2% on CIFAR 100 when training the EfficientFormerr2-55 model.
Comparison with traditional full-rank BP: With LPI,, -8 base selection, our JBP-WHH method either matches or surpasses the accuracy of full-rank BP while only requiring about 80% of the total

---

EfficientFomer-L1
EfficientFomer--7
86.5
L
LP44
8
LP,
8
Full
BP
86.0
LP,
Full
BP
76
LPr,
1,,-
6
16
85.5
16
32
74
32
LP4. 4
6
84.5
Accuracy [%6]
84.0
LP
200
400
800
1000
1600
2000
4000
10000
EfficientForeer2-550
Efficientoomerr244L
L
70
L
LP1,
Full BP
LP 4
LP
8
LP -2
LP
8
BP
LP,
60
16
Ours
32
16
50
LoRA-all
72.5
70.0
2500
Computation [MFLOPS]
Figure 3: Accuracy and computation for training the last stage of different models with different ranks on CIFAR dataset. Our method consistently outperforms the baseline LoRA-all.
Partial Training:
Training Last Stage
Decoder
Full Training
Method
MFLOPs
City
VOCI2A
Method
MFLOPs
City
VOCI2A
BP
10052.00
62.85
69.30
Full BP
16700.26
67.37
70.84
LoRA
5854.61
51.43
58.18
LoRA
11976.46
62.57
58.18
LoRA-all
6262.01
58.07
66.26
LoRA-all
11971.13
65.74
67.82
T.P,, -2* -2t
1481.94
58.95
67.93
T.P,
3"
5574.554
'61.57
67.93
LP,,-4
10
2725.39
60.97
68.85
LPL,-4*
10
7295.52
64.72
68.85
LP
36
7308.45
62.68
68.95
LP
36
13086.06
66.17
68.95
Table 3: Experimental results for semantic segmentation. Results are highlighted as in Table
computation. When using smaller ranks, LBP-WHT significantly reduces the cost with only minor accuracy costs. For example, when training the final stage of EfficientFormert using LPI, -4 base selection, LBP-WHT achieves 3.5x speedup with just 1% loss in accuracy on CIFAR 10F. With LP,, 8 base selection, LBP- WHT achieves even higher accuracy (79.34%) with a 1.2x speedup.
These results underscore the merits of our method. As shown in Table 2 our method achieves computational savings by systematically reducing the computational cost for all operations during backpropagation, including the gradient computation for both input and weight. Specifically, when we apply a similar rank for L-RA-all and LBP-WHI WHT, we anticipate that both methods will have similar computational costs for computing the weight gradient. However, as LoRA-all camnot speed up the gradient computation for the input while LBP-WHT can, our LBP-WHT method requires only half the total computation of LoRA-all. Consequently, for similar computational budget, LBP-WHT can employ a higher rank for low-rank projection, thus leading to higher accuracy. For example, when training the entire EfficienFormerV23 only requires 187 MFLOPs, which is 62% of the computational cost for LoRA-all. Thus, for similar budget, WHT can use rank 28 projection (LP2, -7) and achieve a higher accuracy.
model, LBP-WHT with LP2, (rank 10)
4.3 Semantic Segmentation
Table 3 presents the experimental results for adapting the pretoo-pretraiiedd Segformer model Cityscapes and augmented Paseal VOC 2012 dataset. Our LBP-WHT has better results most cases. For instance, when partially training the Cityscapes dataset, approach using LP,, -4 base selection achieves a mloU score approximately 0.9% higher than that LoRA-alL. Moreover, it only requires 1481.9 MFLOPs, which 4.2x faster. These findings not only further validate the efficacy of our method, but also demonstrate its broad applicability across key computer vision tasks.
4.4 Exploration 1: Different Ranks for Low-rank Projection in LBP-WHT
Figure 3 shows the accuracy achieved when adapting Irreeeeet-reerraieed VITs for CIFARIOM 100, with varying ranks for low-rank model adaptation. Our observations from this figure are follows:
7

---

WHT Base Index for R..-)
Attontion OKV
Nutthead Projection
Fonward
0
0
Unit Deaiall
-5
-75
WHT Base Index B
Figure 5: The WHT spectrum for gradient w.r.t layer output (gw) collected from the last attention block of EfficienFormer--1.. The brightness for cach pixel (i,j) in the spectrum represents the energy preserved by the WHT base Bt,, during projection. A brighter pixel means larger energy. As shown in Figure Dp. the WHT base with smaller indices corresponds to a lower frequency component.
1. Our LBP-WHT method consistently outperforms the LoRA-all method, ie., for a similar level of computation, LBP-WHT yields higher accuracy.
2. By altering the rank, LBP-WHT provides broader range of cost options than the baseline method.
3. LBP-WHT'S accuracy monotonically improves as more ranks are employed for projection.
4. For all models with our LBP-WHH WTT method, generally concave accuracy-come compuucycoommtttion curve is observed. This indicates strong diminishing returns in using larger ranks.
5. LBP-WHT with LPL, -6 base selection achieves an accuracy very close to that of full BP.
Our first observation further confirms the superior performance of our method. The second obser- vation indicates the broad applicability of our method. For instance, for edge devices with limited computational budgets, like Raspherry Pi, we can employ LBP-WHT with a lower rank to reduce computational cost. On the other hand, for more powerful devices, such as personal desktops equipped with GPUs, larger rank can be chosen to enhance accuracy. This ensures that users with various computational resources and constraints can benefit from our method.
The last three observations offer guidelines for rank selection with our LBP- WHT method.
EfficientForerr.11
Marginal Accuracy [%/[FLLPP]]
With strict computational constraints: Given our third obser- vation above, if there is a hard limit on the maximum number of FLOPss allocated for training, selecting the rank for LBP-WHT straightforward: we simply opt for the largest possible num- ber of ranks, which in most cases yields the highest accuracy.
LP,.-6
2000
6000
8000
10000
EfficientFormer22-500
7.5
5.0
LPsg 4
2.5
LP
Without strict computational constraints: Our final two ob- servations suggest that training efficiency can be character- ized by the marginal accuracy, or the slope of the accuracy- computation curve, As shown in Figure 4 before LPz, -4, the marginal accuracy is significantly greater than zero. However, after I. L, -6, the marginal accuracy is very close to zero. This implies that choosing fewer ranks than LPt, -4 or more than LPt, may not be advantageous, as could either forgo the opportunity for good performance with a small amount of computation or waste computation with little benefit. Thus, good selection empirically lies between LP L, -4 and
1000
1500
2000
2500
Computation [MFLOPs]
Figure 4: Marginal accuracy: the slope of the accuracy computatiio curve in Figure
4.5 Exploration 2: Different Bases Selection Method
Method
Rank
CF100
CF10
Figure 5 shows the WHT spectrum for the gradient w.r.f. layer output (g,,) collected from the last attention block in EfficienfFormer-LL.. We observe that most energy concen- trates in the low-frequency area, i.e., the top-left corner, which supports claim in Section that natural images have strong spatial locality and strong oowfrequency components. Furthermore, Figure demnnsttats that by choosing WHT bases with low-frequency responses- - that is, using the selection methods LP,,, and LP,.... - we can preserve most of the energy and minimize error during the low-rank projection. As indicated in Table 4 both of these low-pass base selection methods yield accuracy levels very similar to those achieved with the now-heuristic-ene (LHE) method. The LHE method profiles the WHT spectrum
LP in LP LHE
10
78,27
94.60
77.64
94.30
10
78.06
94.60
Table 4: Experimental results for adapting EfficientForerr-.I
CIFAR100 and CI- FO with different base selection meth- ods. Accuracy is in percentages (%)
8

---

and selects the WHT bases with the strongest response. Given that the LP,, base selection method eliminates the need for profiling (unlike LHE) and offers a more favorable balance between accuracy and cost compared to I. we have selected I.P,, L, as the standard method for LBP-WHT.
4.6 Limitation and Broader Impacts
Full training with a small number of ranks: As shown in Table 2 we find that the accuracy degradation is not negligible when using a small number of ranks for LBP-WHT full training. We consider this is the issue of accumulating error introduced by low-rank projection during BP. We expect that improved approximation method can perform even better. Of note, even with accuracy degradation, our method still consistently outperforms the baselines, i.e., LoRA-basee methods.
Our method greatly reduced the barrier for training ViTs. As positive feature, our method may push the development of privacy-centriy on-device training methods like federated learning; our method may also enable more researchers to test their ideas with powerful ViTs. On the other hand, our method may lower the barrier for irresponsible customization and use of VIT.
Broader Impact:
5 Related Work
Low-rank Model Adaptation: 14] proposes to speed up transformer training by attaching and training only low-rank branches to the linear layer. More precisely, consider a linear layer with equation y = x w", where x is the input, y is the output, and w is the weight. LoRA adds a branch that contains low-rank weights WA and Wn. forming YLORA = x w" + x (WA- -wy)" " The original weight w is kept frozen, while the appended weights WA and wB are trained. Since the ranks of WA and wB are much smaller than that of w, the computation needed to calculate the gradients with respect to WA and wp is significantly reduced. However, this method does not decrease the computation for calculating the gradient w.r.t. This is because it still needs to propagate the gradient through the weights w to x. which considerably limits the performance of LoRA-based methods. As demonstrated in Figure 3 our LBP-WHT, requires much less computation while having better accuracy than LoRA-based methods; this is because our method reduces the computation for all procedures in BP, including the gradient calculation for both input and weights.
Other Orthogonal Methods for On-device Training: Previous research on efficient on-device model adaptation falls into two main categories. The first category 33
suggests reducing the computational cost of arithmetic operations (addition and multiplication) in BP through quantization. proposes to append smaller neural network to the original model and accelerate adaptation by only training the attachment. To the best of our knowledge, our paper is the first to apply low-rank BP for ViT model adaptation. Therefore, our method, LBP-WHT, is distinct from previous research and can be combined with those methods for enhanced performance.
38 43
The second category (20 44
Conclusion
In this paper, we have addressed the problem of efficient model adaptation for ViT. We have proposed a novel low-rank BP technique designed to reduce the computational load associated with the propagation of gradients through the linear layers of ViT, which significant bottleneck when fine-tuning VIT. In Section [3, we introduced the LBP-WHT method as a solution to accelerate model adaptation. More specifically, LBP-WHT operates by projecting the gradient w.r.t. the output (gy) into a low-rank space, performing matrix multiplications within this low-rank space, and then projecting the results back into the original space. Since all matrix multiplications occur in a low-rank space, the computational cost is significantly reduced. Additionally, thanks to the properties of the Walsh-Hadaman Hadamard Transform (WHT), the overhead for these projections is minimal (as discussed in Section 3.3). Through extensive experiments in Section we have demonstrated the efficiency and broad applicability of our method. Our LBP- -HH approach consistently outperforms existing methods with significant speedup and higher accuracy.
Acknowledgments and Disclosure of Funding
This work was supported in part by the US National Science Foundation (NSF) grant CNS-2007284.

---

References
[1] Ze Liu, Han Hu, Yutong Lin, Zhuliang Yao, Zhenda Xie, Yixuan Wei, Jia Ning, Yue Cao. Zheng Zhang, Li Dong, ct al. Swin Transformer v2: Scaling up Capacity and Resolution. In IEEE conference computer vision and pattern recognition, 2022.
[2] Alexander Kirillov, Eric Mintun, Nikhila Ravi, Hanzi Mao, Chloe Rolland, Laura Gustafson, Tete Xiao. Spencer Whitehead. Alexander Berg. Yen Lo, et al. Segment anything. arXiv preprint arXiv:2304.02644 2023.
[3] 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. In International conference on machine learning, 2021.
[4] Hugo Touvron, Matthieu Cord, Matthijs Douze, Francisco Massa, Alexandre Sablayrolles, and Hervé Jégou. Training data-efficient image transformers & distillation through attention. In International conference on machine learning, 2021.
[5] Chaoqiang Zhao, Youmin Zhang, Mattco Poggi, Fabio Tosi, Xianda Guo, Zheng Zhu, Guan Huang, Yang Tang, and Stefano Mattoccia. Monovit: Self-supervised monocular depth estimation with a vision transformer. In International Conference 3D Vision, 2022.
[6] Ashutosh Agarwal and Chetan Arora. Depthformer: Multiscale vision transformer for monocular depth estimation with local global information fusion. arXiv preprint MxXi::2277.04533 2022.
[7] Kai-En Lin, Yen-Chen Lin, Wei-Sheng Lai, Tsung-Yi Yi Lin, Yi-Chang Shih, and Ravi Ramamoorthi. Vision transformer for nerf-based view synthesis from a single input image. In IEEE Winter Conference on Applications of Computer Vision, pages 806 806-815, 2023.
[8] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-EB -ittumiication-EEfcieett Learning of Deep Networks from Decentralized Data. In Artificial intelligence and statisticy, 2017.
[9] Chen Zhang, Yu Xie, Hang Bai, Bin Yu, Weihong Li, and Yuan Gao. A Survey on Federated Learning. Knowledge- Bused Systems, 2021.
[10] Wei Chen, Kartikeya Bhardwaj. and Radu Marculescu. Fedmax: Mitigating Activation Divergence for Accurate and Communicationn-fiicieen Federated Learning. In Machine Learning and Knowledge Discovery in Databases: Fumpean Conference, ECML PKDD 2020, 2021.
[11] Yuedong Yang, Zihui Xue, and Radu Marculescu. Anytime Depth Estimation with Limited Sensing and Computation Capabilities on Mobile Devices. In Conference on Robot Learning, 2022.
[12] Guihong Li, Sumit K Mandal, Umit Y Ogras, and Radu Marculescu, FLASH: Search with Hardware Optimization, ACM Transactions on Embedded Computing Systems, 2021.
Fast Neural Architecture
[13] Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep Learning. MIT Press, 2016.
[14] Edward J Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, and Weizhu Chen. Lora: Low-rank adaptation of large language models, International Conference on Learning Representations, 2022.
[15] Herbert John Ryser. Combinatorial Matemattcs. Carus Mathematical Monographs. Mathematical Association America, 1963. doi: 10.5948/UPP07881614440177
[16] J.L. Shanks. Computation of the fast vulsh-fourier transform. IEEE Transactions on Computers, C-18(5): 457-459, 1969. doi: 10.1 109/T-C. 1969.222685.
[17] Rafael C. Gonzales and Paul Wintz. Digital Image Processing (2nd Ed.). Addison-Westt Wesley Longman Publishing Co., Inc., USA, 1987. ISBN 0201 I 11261..
[18] Yuedong Yang, Guihong Li, and Radu Marculescu. Efficient On-device Training via Gradient Filtering, In IEEE conference computer vision and pattern recognition, 2023.
[19] Marc-Antoine Parseval. Mémoire sur les séries et sur l'intégration complète d' une équation aux différences partielles linéaires du second ordre, à coefficients constants. Mém. prés. par divers savunts, Acad. des Sciences, Paris.(1), 1:638-648, 1806.
[20] Han Cai, Chuang Gan, Ligeng Zhu, and Song Han. Tinytl: Reduce Memory, not Parameters for Efficient On-device Leaming. In Advances in Neural Information Processing Systems, 2020.
10

---

[21] Olga Russakovsky. Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang. Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei-Fei. ImageNet Large Scale Visual Recognition Challenge. International Journal of Computer Vision, 2015.
[22] Alex Krizhevsky. Learning multiple layers features from tiny images. 2009.
[23] Jonathan Krause, Michael Stark, Jia Deng, and Li Fei-Fei. 3D Object Representations for Fine- fine-grained Categorization. In Proceedings of the IEEE international conference on computer vision workshops, 2013.
[24] Maria-Elena Nilsback and Andrew Zisserman. A Visual Vocabulary for Flower Classification. In IEEE conference computer vision and pattern recognition, 2006.
[25] Lukas Bossard, Matthieu Guillaumin, and Luc Van Gool. Fond-101 101 Mining Discriminative Components with Random Forests. European Conference on Computer Vision, 2014.
[26] Omkar M. Parkhi, Andrea Vedaldi, Andrew Zisserman, and C. V. Jawahar. Cats and Dogs. In IEEE Conference on Computer Vision and Pattern Recognition, 2012.
[27] Ilya Loshchilov and Frank Hutter. arXiv:171..05101.200 2017.
Decoupled
Weight Decay Regularization. arXiv preprint
[28] Yanyu Li. Geng Yuan, Yang Wen, Ju Hu, Georgios Evangelidis, Sergey Tulyakov, Yanzhi Wang, and Jian Ren. Efficienfforme:: Vision transformers mobilenet speed, 2022.
[29] Bolci Zhou, Hang Zhao, Xavier Puig, Sanja Fidler, Adela Barriuso, and Antonio Torralba. Scene parsing through ade20k dataset. In JEEE conference on computer vision and patter recognition, pages 633-641, 2017.
[30] Enze Xie, Wenhai Wang, Zhiding Yu, Anima Anandkumar, Jose M Alvarez, and Ping Luo., Segformer: Simple and efficient design for semantic segmentation with transformers. In Neural Information Processing Systems (NeurIPS), 2021.
[31] Marius Cordts, Mohamed Omran, Sebastian Ramos, Timo Rehfeld, Markus Enzweiler, Rodrigo Benenson, Uwe Franke, Stefan Roth, and Bertt Schiele. The cityscapes dataset for semantic urban scene understanding. In IEEE conference on computer vision and pattern recognition, pages 3213 11/---22,,22 2016.
[32] Liang-Chich Chen, George Papandreou, Florian Schroff,, and Hartwig Adam. Rethinking atrous convolution for semantic image segmentation. arXiv preprint urXiv:1706.0533 055877, 2017.
[33] Ji Lin, Ligeng Zhu, Wei-Ming Chen, Wei-Chen Wang, Chuang Gan, and Song Han. On-device Training under 256kb Memory. In Advances in Neural Information Processing Systems, 2022.
[34] Yunhui Guo, Honghui Shi, Abhishek Kumar, Kristen Grauman, Tajana Rosing, and Rogerio Feris. Spottune: Transfer I. Learning through Adaptive Fine-tuning. In IEFE conference computer vision and pattern recognition, 2019.
[35] Mingsheng Long, Yue Cao, Jianmin Wang, and Michael Jordan. Learning Transferable Features with Deep Adaptation Networks. In International conference on machine learning, 2015.
[36] Jason Yosinski, Jeff Clune, Yoshua Bengio, and Hod Lipson. How Transferable are Features in Deep Neural Networks? In Advances in neural information processing systems, 2014.
[37] Yanyu Li, Ju Hu, Yang Wen, Georgios Evangelidis, Kamyar Salahi, Yanzhi Wang, Sergey Tulyakov, and Jian Ren. Rethinking Vision Transformers for MobileNet Size and Speed. arXiv preprint 22x002221..08059 2022.
[38] Jianfei Chen, Yu Gai, Zhewei Yao, Michael Mahoney, and Joseph Gonzalez. A Statistical Framework for Low-bitwidth Training of Deep Neural Networks. In Advances in Neural Information Processing Systems, 2020.
[39] Ron Banner, Itay Hubara, Elad Hoffer, and Daniel Soudry. Scalable methods for 8-bit training of neural networks. Advances neural information processing systems, 2018.
[40] Xiao Sun, Naigang Wang. Chia- Yu Chen, Jiamin Ni, Ankur Agrawal, Xiaodong Cui, Swagath Venkatara- mani, Kaoutar El Maghraoui, Vijayalakshmi (Viji) Srinivasan, and Kailash Gopalakrishnan. Ultra-Lww Precision 4- bit Training of Deep Neural Networks. In Advances in Neural Information Processing Systems. 2020.
11

---

[41] Iay Hubara, Matthieu Courbariaux, Daniel Soudry, Ran EI- Yaniv, and Yoshua Bengio, Quantized neural networks: Training neural networks with low precision weights and activations. The Journal of Machine Learning Research, 2017.
[42] Kang Zhao, Sida Huang, Pan Pan, Yinghan Li, Yingya Zhang. Zhenyu Gu, and Yinghui Xu. Distribution Adaptive INT8 Quantization Training CNNs. Proceedings of the AAAI Conference on Artificial Intelligence, 2021.
[43] Ziyang Hong and C Patrick Yue. Efficient-grad Efficient training deep convolutional neural networks on edge devices with grad ient optimizations. ACM Transactions on Embedded Computing Systems, 2022.
[44] Yi-Lin Sung, Jaemin Cho, and Mohit Bansal. Lst: Ladder Side-tuning for Parameter Memory Efficient Transfer Learning. In Advances in Neural Information Processing Systems, 2022.
[45] Bolei Zhou, Agata Lapedriza, Aditya Khosla, Aude Oliva, and Antonio Torralba. Places: million image database for scene recognition. IEEE transactions on pattern analysis and machine intelligence, 40 (6):1452-14) 1114442226,,.00 2017.
12


Reviews:
[{"review_id": "EKbl21hWAM", "reviewer": "Reviewer_F5LH", "summary": "The paper proposes a cost-efficient back-propagation method using a low-rank trick for vision transformers. When transferring a huge-size vision transformer to the downstream task, the training cost would be high. The paper tackles the problem using low-rank approximation with Walsh-Hadamard Transformation (WHT). The experiments demonstrate the training efficiency of the proposed low-rank back-propagation.\n", "questions": "- The analysis of computation overhead is in section 3.3., but I could not find the cost of computing the low-rank projection matrix (p). It is neglectable, right? \n- Could you provide more experiments on vanilla vision transformers? \n", "limitations": "The authors addressed limitation in the manuscript. ", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper presents their motivation and method well. \n- Experiments show promising performance. \n- Ablation studies are informative.", "weaknesses": "- The targeting scenario of the paper seems somewhat narrow. The paper focuses on vision transformers and its adaptation (transfer learning scenario). It would be nice to discuss the possibility of the proposed method for the efficient pre-training scenario. Also, a discussion about general transformer (e.g., language modeling transformer) adaptation beyond the vision domain would make the paper stronger. \n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1. > *The targeting scenario of the paper seems somewhat narrow. The paper focuses on vision transformers and its adaptation. It would be nice to discuss the possibility of the proposed method for the efficient pre-training scenario. Also, a discussion about general transformer adaptation beyond the vision domain would make the paper stronger.*\n\n   We plan to extend our work beyond vision applications, *e.g.*, language models, in our future research. However, we note that our current results in the experimental section show already that the LBP-WHT method works very efficiently for a wide class of models, (*e.g.*, pure ViT and hybrid CNN-ViT) and applications (*e.g.*, image classification and segmentation). Hence, we are confident that our LBP-WHT will generalize seamlessly to applications beyond computer vision.\n\n   $~$\n\n   We also want to emphasize the importance of fine-tuning for vision models. ViTs have been deployed in scenarios where data distributions are very different from the datasets used during pretraining. In such cases, efficiently finetuning the model and helping the model adapt to the new domain is both **important and necessary**, thus proving the significance of our work. For instance, ViTs are utilized on smartphones for tasks such as scene comprehension. Training a ViT on a smartphone allows us to utilize the user data while maintaining privacy. In such scenarios, our LBP-WHT is crucial in making ViT training feasible, thus allowing more people to benefit from SoTA computer vision models.\n\n---\n\n\n2. > *The analysis of computation overhead is in section 3.3., but I could not find the cost of computing the low-rank projection matrix (p). It is neglectable, right?*\n\n   Yes, this is negligible. Specifically, the projection matrix is constructed only **once** before the training begins. Moreover, its creation time of 41us on a single-core CPU is negligible when compared to the overall training time.\n\n   $~$\n\n   Furthermore, in practice, generating and storing the WHT bases is **not required** for performing WHT. Similar to the Discrete Fourier Transform (DFT), representing the Walsh-Hadamard Transform (WHT) through matrix multiplication with a base matrix is needed only for the theoretical analysis. In practical applications, WHT is executed using the fast-WHT algorithm, an approach similar to calculating the FFT which does not require generating and storing the projection matrix.\n\n---\n\n\n3. > *Could you provide more experiments on vanilla vision transformers?*\n\n   We will provide such results in the final version of the paper, since running experiments, especially baseline methods, with a vanilla full-scale ViT would take over one week, given our resources; this is not feasible during the limited time of the rebuttal period.\n\n   $~$\n\n   It is worth noting that although EfficientFormer and EfficientFormerV2 used in our evaluations are CNN-ViT-hybrid models, the modules in their CNN part are actually **equivalent** to the feed-forward network in ViT, but implemented with pointwise convolution. Moreover, since the last stage of the large-scale models of EfficientFormer-L7 and EfficientFormerV2-L consist of ViT modules, the partial-training of these models is **similar** to training a vanilla vision transformer. Thus, we are confident that our experimental findings can be seamlessly transferred to other ViT models.\n\n   $~$\n\n   To address your concern regarding our method’s scalability and its compatibility with other training methods, we further test our method with the partial-training experimental setup for EfficientFormer-L1. Below, we discuss these results. \n\n   $~$\n\n   **Experimental results on large-scale datasets**\n\n   We test our method on a large-scale dataset Places365 [45], which contains over 1.8M training images and is more challenging than ImageNet (*i.e.*, models have a lower accuracy on Places365 than ImageNet). Below are our results for EfficientFormer-L1. Meaning of notations \"LoRA\", \"LoRA-all\" and $LP_{L_1}$-r is introduced in the general rebuttal section above [[link]](https://openreview.net/forum?id=NNtsO5L27J&noteId=8YCHi4VqDZ).\n\n   |Method|Speedup|MFLOPs|Accuracy [%]|\n   |-|-|-|-|\n   |Full BP|1.0x|1685.01| 55.30|\n   |LoRA|6.9x|242.61|50.64|\n   |LoRA-all|1.7x| 976.50|53.73|\n   |$LP_{L_1}-2$|7.2x|233.62|52.87|\n   |$LP_{L_1}-4$|3.5x|480.00|55.07|\n   |$LP_{L_1}-6$|2.1x|820.11|55.13|\n   |$LP_{L_1}-8$|1.2x|1397.02|55.39|\n\n   As shown, our method **scales well** on large scale datasets. For example, LBP-WHT with $LP_{L_1}$-2 base selection outperforms LoRA both in speed and accuracy; $LP_{L_1}$-8 has an even higher accuracy than the full-rank BP while achieving a 1.2x speedup.\n\n   $~$\n\n   **Experimental results when combining LBP-WHT with LoRA**\n\n   To show that our method is complementary to other existing methods, we combine our LBP-WHT with LoRA and show the results below.\n\n   |Method|Accuracy CF100 [%]|Accuracy CF10 [%]|Activation [MB]|Gradient [MB]|GFLOPs|\n   |-|-|-|-|-|-|\n   |Full BP|79.28|95.23|141|2352|121|\n   |LoRA-all|76.92|94.38|142|44|62|\n   |$LP_{L_1}-2$|75.61| 93.35|9|2352|8|\n   |$LP_{L_1}-4$|78.27| 94.60|29|2352|25|\n   |$LP_{L_1}-8$|79.34| 95.31|104|2352|91|\n   |$LP_{L_1}-2$+LoRA-all|73.27|92.62|9|44|4|\n   |$LP_{L_1}-4$+LoRA-all|75.48|93.74|29|44|13|\n   |$LP_{L_1}-8$+LoRA-all|76.58|94.33|104|44|48|\n\n   As shown, our method significantly reduces both the storage for the activation map (x) and the computational costs. On the other hand, LoRA efficiently reduces the memory usage needed to store the weights gradient. By combining both methods, we can **systematically reduce** both computation and memory costs, while maintaining the accuracy levels close to using LoRA alone. For instance, when combining LBP-WHT with $LP_{L_1}$-4 base selection and LoRA, we achieve a speedup of 4.7x and memory savings of 2.5x, with only a slight accuracy drop of 1.4% compared to employing LoRA alone. These results confirm the effectiveness of our method."}, {"review_id": "yOc4HJGT45", "reviewer": "Reviewer_j7ix", "summary": "The author discusses the issue of computational complexity during matrix multiplication in the backpropagation of linear layers in the vision transformer architecture. To address this issue, the author proposes a method called Low-rank BackPropagation via Walsh-Hadamard Transformation (LBP-WHT), which projects the gradient into a low-rank space and performs BackPropagation computations. Finally, the author evaluates the proposed method using different models such as ViT and a hybrid convolution-ViT model on multiple datasets. The author claims that LBP-WHT achieves 10.4% higher accuracy than the state-of-the-art baseline, providing SOTA performance on the CIFAR100 dataset with the EfficientFormer-L1 model.", "questions": "Please refer to the weakness section.", "limitations": "Please refer to the weakness section.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "\n1. This paper is well-written and easy to understand.\n\n2. The Low-rank BackPropagation via Walsh-Hadamard Transformation (LBP-WHT) method in the gradient domain is new and effective.\n\n3. The novelty of LBP-WHT as the first work to accelerate ViT training using low-rank BP (Backpropagation). It also demonstrates the ability to lower the computational barrier and enable the adaptation of large ViT models on resource-constrained edge devices.\n\n4. The paper addresses an essential problem in transformer architecture and proposes a novel solution that achieves promising results.\n\n5. The author provides more quantitative results on various tasks, including classification and semantic segmentation. Additionally, the comparison with LoRA, one of the state-of-the-art (SOTA) models, adds value to the evaluation.\n", "weaknesses": "Weaknesses:\n\n1. The literature survey section in this paper is a bit weak. The author should compare related/similar transformer models, particularly QLoRA, and similar work on \"Hadamard product for low-rank bilinear pooling.\" A more thorough literature review is necessary in this regard.\n\n2. It would be beneficial to add a section briefly discussing LoRA, QLoRA, and the proposed method, as well as comparing the results with the proposed method.\n\n3. The author should provide results on larger datasets like the standard ImageNet-1k and evaluate other large datasets such as JFT-Imagenet-21K.\n\n4. Instead of Swin-Transformer, the author should evaluate the proposed method on the SOTA model like WaveViT or SpectFormer to validate the SOTA performance.\n\n5. The paper misses one of the core aspects of machine learning practice: readability and reproducibility of results. It would be more transparent and beneficial if the author could provide source code to reproduce the results, similar to what was done with LoRA.\n\n6. It seems like a minor typo: \"finally project them black\" should be \"finally project them back.\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1. > *The literature survey section in this paper is a bit weak. The author should compare related/similar transformer models, particularly QLoRA, and similar work on \"Hadamard product for low-rank bilinear pooling.\" A more thorough literature review is necessary in this regard. It would be beneficial to add a section briefly discussing LoRA, QLoRA, and the proposed method, as well as comparing the results with the proposed method.*\n\n   We appreciate your suggestions and will certainly expand the related work section, including a more detailed presentation of the LoRA method. \n\n   $~$\n\n   As for QLoRA [46], we note that QLoRA was released on arxiv only on May 23, 2023, which is *after* the NeurIPS 2023 paper submission deadline. Therefore, we were not aware of it at the time of our paper submission. Given our resources, we can’t provide such a comparison within the rebuttal period.\n\n   $~$\n\n   Regarding [47], despite the title similarity, we note that the model and the method used are entirely different than ours; more precisely: \n\n   - The method in [47] can only work with a bilinear model. In contrast, our method is designed for ViTs. Thus, a direct comparison between our method and method in [47] is simply not possible.\n   - The operator “Hadamard product” used in [47], which refers to element-wise multiplication, is fundamentally different from the Walsh-Hadamard Transformation (WHT) utilized in our paper. While the Hadamard product is a method for performing multiplication, the WHT is an orthogonal transformation method.\n\n   Given these fundamental differences, we cannot directly compare our method with methods used in [47].\n\n   ---\n\n   \n\n2. > *The author should provide results on larger datasets like the standard ImageNet-1k and evaluate other large datasets such as JFT-Imagenet-21K.*\n\n   **Experimental results on large-scale dataset**\n\n   We test our method on large-scale dataset Places365 [45], which contains over 1.8M training images with 365 different classes and is a more challenging dataset than ImageNet-1K (the same networks usually have a lower accuracy on Places365 than ImageNet-1K). We present below our experimental results for finetuning the EfficientFormer-l1 with partial training experimental setup (Section 4.1). Meaning of notations \"LoRA\", \"LoRA-all\" and $LP_{L_1}$-r is introduced in the general rebuttal section above [*[link to the notations table]*](https://openreview.net/forum?id=NNtsO5L27J&noteId=8YCHi4VqDZ). \n\n   |Method|R|Speedup|MFLOPs|Accuracy [%]|\n   |-|-|-|-|-|\n   |Full BP|-|1.0x|1685.01|55.30|\n   |LoRA|8|6.9x|242.61|50.64|\n   |LoRA-all|8|1.7x|976.50|53.73|\n   |$LP_{L_1}$-2|3|7.2x|233.62|52.87|\n   |$LP_{L_1}$-4|10|3.5x|480.00|55.07|\n   |$LP_{L_1}$-6|21|2.1x|820.11|55.13|\n   |$LP_{L_1}$-8|36|1.2x|1397.02|55.39|\n\n   As shown in this table, our method **scales well** for such large scale datasets. For example, LBP-WHT with $LP_{L_1}$-2 base selection outperforms LoRA both in speed and accuracy. As another example, $LP_{L_1}$-8 has even a higher accuracy than full-rank BP while achieving a 1.2x speedup.\n\n   $~$\n\n   **Experimental result for combining LBP-WHT with LoRA**\n\n   To support our claim that our method is complementary to other existing methods, we combine our LBP-WHT with LoRA and present below our experimental results for accuracy, computation and memory cost. Meaning of notations \"LoRA\", \"LoRA-all\" and $LP_{L_1}$-r is introduced in the general rebuttal section above [*[link to the notations table]*](https://openreview.net/forum?id=NNtsO5L27J&noteId=8YCHi4VqDZ). \n\n   |Method|Accuracy CF100 [%]|Accuracy CF10 [%]|Activation [MB]|Gradient [MB]|GFLOPs|\n   |-|-|-|-|-|-|\n   |Full BP|79.28|95.23|141|2352|121|\n   |LoRA-all|76.92|94.38|142|44|62|\n   |$LP_{L_1}-2$|75.61| 93.35| 9| 2352|8|\n   |$LP_{L_1}-4$|78.27| 94.60| 29| 2352|25|\n   |$LP_{L_1}-8$|79.34| 95.31| 104| 2352|91|\n   |$LP_{L_1}-2$ + LoRA-all|73.27|92.62|9|44|4|\n   |$LP_{L_1}-4$ + LoRA-all|75.48|93.74|29|44|13|\n   |$LP_{L_1}-8$ + LoRA-all|76.58|94.33|104|44|48|\n\n\n   As shown, our method significantly reduces both the storage size needed for the activation map (x) and the computational costs. On the other hand, LoRA efficiently reduces the memory usage needed to store the weights gradient. By combining both methods, we can **systematically reduce** both computation and memory costs, while maintaining the accuracy levels close to using LoRA alone. For instance, when combining LBP-WHT with $LP_{L_1}$-4 base selection and LoRA, we achieve a speedup of 4.7x and memory savings of 2.5x, with only a slight accuracy drop of 1.4% compared to using LoRA alone. These results confirm the effectiveness of our method.\n\n   ---\n\n   \n\n3. > *Instead of Swin-Transformer, the author should evaluate the proposed method on the SOTA model like WaveViT or SpectFormer to validate the SOTA performance.*\n\n   EfficientFormer [48] and EfficientFormer-V2 [49] were proposed in Oct 2022 and Dec 2022, respectively, and both of them were considered SoTA at the time of our paper submission.\n\n   $~$\n\n   Based on our experimental section, our LBP-WHT method works efficiently with a large range of models, such as pure ViT and hybrid CNN-ViT, and for various applications like classification and segmentation. Hence, we have confidence in generalizing our LBP-WHT approach seamlessly to other models and other applications.\n\n   ---\n\n   \n\n4. > *The paper misses one of the core aspects of machine learning practice: readability and reproducibility of results. It would be more transparent and beneficial if the author could provide source code to reproduce the results, similar to what was done with LoRA.*\n\n   Indeed, all experimental results reported in our paper are fully reproducible. We will open source the code upon acceptance."}, {"review_id": "HyeJhuCvui", "reviewer": "Reviewer_idrd", "summary": "The paper presents to compute the low-rank approximation for the matrices used in back-propagation, and thus it can save the computation in multiplication. The proposed approach is more efficient than LoRA because no need to backpropagate to the original weights, and experiments also support the claims.", "questions": "1. In Table 1, what is the difference between the r in \"LPL1 -r” and R? I thought they both represent rank.\n2. Is the WHT differentiable? How is the model trained with this operation.\n3. I thought WHT^{-1} was not a square matrix, was it? If not, how to compute WHT^{-1}?\n4. How is the \"Speed up\" in table 1 measured?\n\n---\n**Post-rebuttal**\nThank you for the authors' response. I have read it and it addressed my questions.", "limitations": "1. There is no experiment to support whether the approach can work well with other efficient approaches.\n2. The experimental results are only for vision tasks.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The proposed approach is simple and well-motivated.\n2. The experimental results show that the approach is better than LoRA.", "weaknesses": "1. Although the paper claims that the approach is complementary to other efficient approaches (such as quantization), there is no experimental support for it.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1. > *Although the paper claims that the approach is complementary to other efficient approaches (such as quantization), there is no experimental support for it.*\n\n   **Experimental results when combining LBP-WHT with LoRA**\n\n   To show that our method is complementary to other existing methods, we combine LBP-WHT with LoRA and show our results below. Meaning of notations \"LoRA\", \"LoRA-all\" and $LP_{L_1}$-r is introduced in the general rebuttal section [*[link]*](https://openreview.net/forum?id=NNtsO5L27J&noteId=8YCHi4VqDZ).\n\n   |Method|Accuracy CF100 [%]|Accuracy CF10 [%]|Activation [MB]|Gradient [MB]|GFLOPs|\n   |-|-|-|-|-|-|\n   |Full BP|79.28|95.23|141|2352|121|\n   |LoRA-all|76.92|94.38|142|44|62|\n   |$LP_{L_1}-2$|75.61|93.35|9|2352|8|\n   |$LP_{L_1}-4$|78.27|94.60|29|2352|25|\n   |$LP_{L_1}-8$|79.34|95.31|104|2352|91|\n   |$LP_{L_1}-2$+LoRA-all|73.27|92.62|9|44|4|\n   |$LP_{L_1}-4$+LoRA-all|75.48|93.74|29|44|13|\n   |$LP_{L_1}-8$+LoRA-all|76.58|94.33|104|44|48|\n\n   As shown, our method significantly reduces both storage size needed for activation map (x) and computational costs. LoRA reduces the memory usage needed to store the gradients. By combining both methods, we can **systematically reduce** both computation and memory costs, while maintaining the accuracy close to using LoRA alone. For instance, when combining LBP-WHT with $LP_{L_1}$-4 base selection and LoRA, we achieve a speedup of 4.7x and memory savings of 2.5x, with only an accuracy drop of 1.4% compared to using LoRA alone. These results confirm the complementarity and effectiveness of our method.\n\n---\n2. > *In Table 1, what is the difference between the r in \"LPL1 -r” and R? I thought they both represent rank.*\n\n   The \"r\" in $LP_{L_1}$-r is the hyper-parameter associated with $L_1$-based low-pass basis selection in Equation (8). As Figure 2(c) shows, each WHT basis is linked with a 2D coordinate (i, j). A larger i or j value correlates with a higher frequency change in one direction. The $LP_{L_1}$ selection method picks WHT bases with a smaller $L_1$ norm of the coordinate. For instance, $LP_{L_1}$-2 selects bases with the $L_1$ norm of the indices less than 2, that is, $|i| + |j| < 2$, such as (0, 0), (0, 1), and (1, 0).\n\n   $~$\n\n   On the other hand, \"R\" in Table 1 refers to the rank of the low-rank projection. For example, since $LP_{L_1}$-2 selects three WHT bases, the rank for the low-rank projection $LP_{L_1}$-2 is therefore three and R=3.\n\n   We will clarify these notations in the camera-ready version.\n\n---\n3. > *Is the WHT differentiable? How is the model trained with this operation.*\n\n   While the Walsh-Hadamard Transformation (WHT) is differentiable, this property is **not required** for our method, *i.e.*, our method does **not** affect the forward propagation process. Instead, our approach modifies and accelerates the *back propagation*. With our method, the training process goes as follows:\n   - Given the inputs and weights, perform forward propagation as usual\n   - Calculate the loss value as usual\n   - Replace the back propagation (or auto-differentiation) with LBP-WHT and calculate the gradient with our method.\n\n   Since our method only modifies back propagation, LBP-WHT can be applied in a plug-and-play manner for fine-tuning various models. Also, the LBP-WHT does **not** affect the inference performance.\n\n---\n4. > *I thought WHT^{-1} was not a square matrix, was it? If not, how to compute WHT^{-1}?*\n\n   As shown in Equation (2), $WHT^{-1}$ refers to the reverse WHT **function**, *not* the inverse matrix. Similar to reverse Fourier Transformation, the reverse WHT is calculated by multiplying the low-rank gradient ($\\hat g_x$) with a transposed WHT base.\n\n---\n5. > *How is the \"Speed up\" in table 1 measured?*\n\n   The speedup in Table 1 is determined by comparing the #FLOPs required by the baseline method to #FLOPs of our LBP-WHT method. As our primary contribution is on the algorithm side, we use #FLOPs as a measure of performance that is **independent of the implementation**. This enables us to determine the acceleration resulting from proposing a more efficient algorithm, not simply from using an improved implementation.\n\n   $~$\n\n   To demonstrate that the theoretical speedup translates into actual speedup, we profile the linear layers in a feed-forward network with different token dimensions on a RTX3090Ti GPU:\n\n   |Token Dimension|Projection Rank|Theoretical Speedup|Actual Speedup|Baseline Run Time [ms]|LBP-WHT Run time [ms]|\n   |-|-|-|-|-|-|\n   |2048|16|3.94x|3.26x|0.66|0.20|\n   |2048|32|1.97x|1.84x|0.66|0.36|\n   |4096|16|3.97x|3.90x|3.18|0.82|\n   |4096|32|1.98x|1.96x|3.18|1.63|\n\n   As shown, the actual speedup closely mirrors the theoretical speedup; this validates the efficiency of our method.\n\n---\n6. > *The experimental results are only for vision tasks.*\n\n   We plan to extend our work beyond computer vision applications, *e.g.*, language modeling, in our future research. However, our current results in the experimental section show already that our LBP-WHT works very efficiently with a wide class of models, (*e.g.*, pure ViT and hybrid CNN-ViT) and applications (*e.g.*, image classification and segmentation). Hence, we are confident that our LBP-WHT will generalize seamlessly to applications beyond computer vision.\n\n   $~$\n\n   We also want to emphasize the importance of fine-tuning vision models. ViTs have been deployed in scenarios where data distributions are very different from the datasets used to pretrain the model. In such cases, efficiently finetuning the model and helping the model adapt to the new domain is both **important and necessary**, hence the significance of our work. For instance, ViTs are utilized on smartphones for tasks such as scene comprehension. Training a ViT on a smartphone allows us to utilize the user data while maintaining privacy. In these scenarios, our LBP-WHT is crucial in making ViT training feasible, thus allowing everyone benefit from SoTA computer vision models."}, {"review_id": "qEc32Swon2", "reviewer": "Reviewer_EswK", "summary": "This paper introduces a method to efficiently finetune Vision Transformers (ViTs) for specific tasks such as image classification and semantic segmentation. The method, Low-rank Backpropagation via Walsh-Hadamard Transformation (LBP-WHT), reduces the computational cost of backpropagation in ViTs by projecting the gradients (dy/dx and dy/dw) into a low-rank space using WHT basis where the bases are made up of -1's and 1's. Experiments are only shown with EfficientFormer (V1, V2), SwinTransformerV2 and SegFormer models. Proposed method outperforms LoRA in terms of both accuracy and efficiency. The paper also shows actual speed improvements on hardware (GPU/CPU) which is promising.", "questions": "* Do you use your method in all linear layers or only the attention modules (like \"LoRA baseline\")? My guess is all linear layers, but I don't see this explicitly mentioned.", "limitations": "Yes, limitations have been sufficiently addressed.", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "### Simple method with significant speedups and possible efficient implementation\n* The proposed method is simple in design and easy to implement *efficiently* on any target hardware. The authors have already shown speed-ups on CPU and GPU with a naive implementation which I believe can be sped up for commercial deployment\n\n### Good results compared to LoRA\n* The experiments demonstrate strong results on EfficientFormer (V1,V2), SwinTransformer and SegFormer models as compared to LoRA. The proposed method achieves better speed-up than LoRA while also not losing as much accuracy.\n\n### Can be applied to both dy/dw and dy/dx\n* LoRA cannot speed-up the gradient computation for dy/dx but the proposed method can LBP-WHT.", "weaknesses": "### Why only ViTs? That too only smaller scale ViT models?\n* The proposed method is an efficient variant of backpropagation that should work with any architecture that contains linear layers. So, why not evaluate the method with MLP-Mixer models (Tolstikhin, Ilya O., et al. \"Mlp-mixer: An all-mlp architecture for vision.\" NeurIPS 2021) which are full of linear layers? \n* Also, many CNN models (such as all MobileNets, EfficientNets) use pointwise convolution layers and pointwise convolutions are basically linear layers. The authors should show results of the proposed method with such architectures too, not just ViTs.\n* How does it compare with LoRA on Large Language Models? The LoRA paper showed exceptional results with LLMs, but in this paper, the proposed method has been compared with LoRA only on small-scale ViTs.\n\n### Comparison with Gradient Compression\n* The main contribution of this paper is a method to reduce the cost of computing gradients, which they do so by computing low-rank approximations. There is a popular method called Gradient Compression (Lin, Yujun, et al. \"Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Training.\" ICLR 2018) which compresses gradients by 270x to 600x without losing accuracy. Comparison with such a method should be shown in the results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1. > *Why only ViTs? That too only smaller scale ViT models?*\n\n   Yes, LBP-WHT works well with other architectures. In this paper, both EfficientFormer and EfficientFormerV2 are hybrid models of CNN-ViT that incorporate both multi-head attention modules from ViT and convolution layers from CNN. To elaborate, smaller models such as EfficientFormer-L1 and EfficientFormerV2-S0 consist of more convolutional layers than multi-head attention modules. On the other hand, larger models like EfficientFormer-L7 and EfficientFormerV2-L feature more multi-head attention modules. As shown in Table 2 of our paper, the LBP-WHT method works effectively with **all** these hybrid models. This confirms that our technique is efficient in handling both multi-head attention modules and convolutional layers.\n   \n   ---\n   \n2. > *Comparison with Gradient Compression*\n\n   Deep Gradient Compression concentrates on enhancing communication efficiency in multi-node training scenarios and addresses the challenge of aggregating gradients from each device efficiently **after** back propagation. In contrast, our focus is on the efficient execution of the back propagation itself. As these approaches target different optimization goals and are applied at distinct stages of training, a direct comparison between our method and Deep Gradient Compression is not meaningful.\n   \n   ---\n\n3. > *Do you use your method in all linear layers or only the attention modules (like \"LoRA baseline\")? My guess is all linear layers, but I don't see this explicitly mentioned.*\n\n   Yes, our method is applied to **all** layers, including the linear layer for the self-attention module, as well as the linear layers in the subsequent feed-forward network. For the baseline method, LoRA, we conducted two sets of experiments labeled as \"LoRA\" and \"LoRA-all\". The \"LoRA\" experiments apply the LoRA method only to the *self-attention layers*, consistent with the experimental setup proposed in the original LoRA paper. In contrast, \"LoRA-all\" applies the LoRA method to all *linear* *layers*, including those in the self-attention modules and the feed-forward network."}, {"review_id": "9nfWXsgaNs", "reviewer": "Reviewer_Hdqi", "summary": "This paper proposed an efficient training method, called Low-rank Back Propagation via Walsh-Hadamard Transformation (LBP-WHT). Specifically, unlike previous works that target low-rank adaptation for model parameters, LBP-WHT aims to reduce the computational cost during backpropagation by projecting the gradients w.r.t inputs into a low-rank space, thus the overall computation can be done efficiently. Extensive experiments on classification and semantic segmentation have demonstrated that LBP-WHT significantly reduces MFLOPs during partially training.", "questions": "1. In Table 3, why LoRA and LBP-WHT have much more MFLOPs than Full BP on partial training? \n2. Can authors also explain why the proposed method performs better on partial training?", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. To my knowledge, adopting low-rank backpropagation for ViT adaptation is novel.\n2. The method is easy to follow. The visualization of LBP-WHT in Figure 2 clearly presents the proposed framework.\n3. The results are impressive. Based on partially training (Table 2), LBP-WHT achieves great efficiency-accuracy trade-off.", "weaknesses": "1. Theoretical complexity reduction cannot reflect the real speedup for training. It would be better for the authors to report training time (GPU hours) or training throughput (images/s) in main experiments, especially for Table 2. Besides, as shown in Table 5 of the supplementary material, the authors have compared latency across different hardwares. However, the real speedup is only around 1-2x, which is very different from the reduction ratio of MFLOPs (6-7x).\n2. The experiments do not report memory cost. Recent works (especially for LLMs) usually care more about memory cost during adaptation since fully finetuning or low-rank finetuning requires intensive memory. Moreover, on-device training also requires low-memory consumption, see [33]. However , the effect of the propsoed method on memory cost is also unknown.\n3. As this paper aims to reduce the computational cost during backpropagation, it does not have advantages in inference. Actually, it even introduces overhead on model parameters as it is not parameter-efficient on downstream tasks.\n4. Lack ablation study of combining LoRA with LBP-WHT. Since authors have claimed that the proposed technique is complementary to other works, it should have at least one experiment to prove this claim and show the advantage of their method.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1. > *Theoretical complexity reduction cannot reflect the real speedup for training. It would be better for the authors to report training time (GPU hours) or training throughput (images/s) in main experiments, especially for Table 2.*\n\n   As our primary contribution is on the algorithm side, we use #FLOPs as a measure of performance which is **independent of the implementation details**. This approach enables us to determine the acceleration resulting from a more efficient algorithm, not simply from an improved implementation.\n\n   $~$\n\n   As noted in the supplementary material, our current implementation is only meant to be a **proof of concept**, hence it is not fully optimized. As such, we are aware of several limitations:\n\n   - The WHT is carried out using general matrix multiplications. Consequently, none of the properties of WHT are exploited, including the fast WHT algorithm.\n   - There is a high degree of “algorithm-oblivious” overhead. While the baseline method has been integrated into a single CUDA kernel, our method launches multiple CUDA kernels, thus leading to considerable context switching and kernel launching overhead [50].\n\n   $~$\n\n   We found that the above limitations do **not** scale with the problem size. Therefore, to demonstrate the effectiveness of our method, we test it with the linear layers from larger scale models. The results, measured on a RTX3090Ti, are as follows:\n\n   |Token Dimension|Projection Rank|Theoretical Speedup|Actual Speedup|Baseline Run Time [ms]|LBP-WHT Run time [ms]|\n   |-|-|-|-|-|-|\n   |2048|16|3.94x|3.26x|0.66|0.20|\n   |2048|32|1.97x|1.84x|0.66|0.36|\n   |4096|16|3.97x|3.90x|3.18|0.82|\n   |4096|32|1.98x|1.96x|3.18|1.63|\n\n   As shown, the speedup achieved by our method closely aligns with the theoretical speedup; this confirms that our method is practical and can be efficiently implemented.\n   \n   ---\n\n2. > *Does LBP-WHT have benefit in memory savings? Can LBP-WHT be combined with other efficient training methods?*\n\n   Our method offers benefits in memory usage. As shown in Algorithm 1, the activation map 'x' is projected into a low-rank space through the use of WHT. This step notably reduces the memory needed to store the activation map. \n\n   $~$\n\n   Finally, our method can be paired with other techniques for additional memory savings, *e.g.*, we can combine our approach with LoRA to reduce memory consumption for both activations and gradients - table below. Meaning of notations is introduced in the general rebuttal section [*[link]*](https://openreview.net/forum?id=NNtsO5L27J&noteId=8YCHi4VqDZ).\n\n   |Method|Accuracy CF100 [%]|Accuracy CF10 [%]|Activation [MB]|Gradient [MB]|GFLOPs|\n   |-|-|-|-|-|-|\n   |Full BP|79.28|95.23|141|2352|121|\n   |LoRA-all|76.92|94.38|142|44|62|\n   |$LP_{L_1}-2$|75.61|93.35|9|2352|8|\n   |$LP_{L_1}-4$|78.27|94.60|29|2352|25|\n   |$LP_{L_1}-8$|79.34|95.31|104|2352|91|\n   |$LP_{L_1}-2$+LoRA-all|73.27|92.62|9|44|4|\n   |$LP_{L_1}-4$+LoRA-all|75.48|93.74|29|44|13|\n   |$LP_{L_1}-8$+LoRA-all|76.58|94.33|104|44|48|\n\n   As shown, our method significantly reduces both the storage needed for the activation map and the computational costs. By combining with LoRA, our method can **systematically reduce** both computation and memory costs, while maintaining accuracy close to using LoRA alone. For instance, when combining LBP-WHT $LP_{L_1}$-4 and LoRA, we achieve a speedup of 4.7x and memory savings of 2.5x, with only a slight accuracy drop of 1.4% compared to employing LoRA alone. These results confirm the effectiveness of our method.\n   \n   ---\n\n3. > *As this paper aims to reduce the computational cost during backpropagation, it does not have advantages in inference.*\n\n   Our method is designed to improve efficiency during *back-propagation* rather than during inference. This is because, during the training phase, back propagation requires twice as much computation as inference, thus it is the main bottleneck.\n\n   $~$\n\n   Interestingly enough, our focus on backpropagation offers another **advantage**. Modifying the operators involved in inference typically demands re-training the parameters in the modified operator from scratch, which brings about a substantial overhead and minimizes the benefits of efficient model adaptation. In contrast, our method only modifies the back propagation process while leaving the inference process untouched. Hence our method can be directly applied to any pre-trained model, thus enabling immediate model adaptation.\n   \n   ---\n\n4. > *Actually, it even introduces overhead on model parameters as it is not parameter-efficient on downstream tasks.*\n\n   We want to clarify that:\n\n   - Our method introduces **no extra** trainable parameter to the model. WHT base matrix is fixed regardless of the model and dataset.\n   - Although the WHT base matrix might appear as a \"parameter\", it is primarily used for theoretical analysis. For ease of understanding, we cast WHT as the process of multiplying the gradient map with this base matrix. However, in practice, the fast-WHT algorithm is employed. This algorithm integrates the base matrix into a butterfly diagram, thus eliminating the need to store the base matrix separately. This is analogous to the Discrete Fourier Transformation (DFT). While DFT can be theoretically expressed as matrix multiplication, in practical applications, the Fast Fourier Transformation (FFT) is preferred.\n\n   ---\n\n5. > *In Table 3, why LoRA and LBP-WHT have much more MFLOPs than Full BP on partial training?*\n\n   Thank you for pointing this out. We made a mistake when filling this table. The correct computation required by Full BP is 10052.00 MFLOPs. We’ll fix it in the camera ready version.\n   \n   ---\n\n6. > *Can authors also explain why the proposed method performs better on partial training?*\n\n   In model adaptation, freezing some layers is important to solve the overfitting problem [51, 52]. Our experimental results align with the general model adaptation problems. "}]

Author rebuttal:
We genuinely appreciate the reviewer's insightful comments and suggestions in reviewing our paper. Below we include additional references used in the rebuttal for all reviewers.

## Notation for Additional Experiments

We follow the same notation as the manuscript. To be more specific, 

| Notation | Meaning |
|-|-|
| LoRA | Baseline method strictly following [14] which uses low-rank reparametrization solely in the ViT’s attention module. |
| LoRA-all | Baseline method applying [14] on all linear layers. |
|$LP_{L_1}$-r| Our LBP-WHT method with $LP_{L_1}$ base selection detailed in the Section 3.2. The "r" in $LP_{L_1}$-r is the hyper-parameter associated with $L_1$-based low-pass basis selection in Equation (8). As Figure 2(c) shows, each WHT basis is linked with a 2D coordinate (i, j). A larger i or j value correlates with a higher frequency change in one direction. The $LP_{L_1}$ selection method picks WHT bases with a smaller $L_1$ norm of the coordinate. For instance, $LP_{L_1}$-2 selects bases with the $L_1$ norm of the indices less than 2, that is, $|i| + |j| < 2$, such as (0, 0), (0, 1), and (1, 0). |


  $~$




## Additional References for Rebuttal
***These additional references are referred to throughout our responses to reviewer questions. References [1-44] are from the manuscript.***

[45] Zhou, B., et al. "Places: A 10 million image database for scene recognition." IEEE Trans. on Pattern Analysis and Machine Intelligence 40.6 (2017): 1452-1464.

[46] Dettmers, Tim, et al. "Qlora: Efficient finetuning of quantized llms." arXiv preprint arXiv:2305.14314 (2023).

[47] Kim, Jin-Hwa, et al. "Hadamard product for low-rank bilinear pooling." arXiv preprint arXiv:1610.04325 (2016).

[48] Li, Yanyu, et al. "Efficientformer: Vision transformers at mobilenet speed." Advances in Neural Information Processing Systems 35 (2022): 12934-12949.

[49] Li, Yanyu, et al. "Rethinking vision transformers for mobilenet size and speed." arXiv preprint arXiv:2212.08059 (2022).

[50] Kim, S., et al.. "Minimizing GPU kernel launch overhead in deep learning inference on mobile GPUs." Proc.Intl. Workshop on Mobile Computing Systems and Applications. 2021.

[51] Wang, Yiding, et al. "Egeria: Efficient DNN Training with Knowledge-Guided Layer Freezing." arXiv preprint arXiv:2201.06227 (2022).

[52] Lee, Jaejun, Raphael Tang, and Jimmy Lin. "What would elsa do? freezing layers during transformer fine-tuning." arXiv preprint arXiv:1911.03090 (2019).


Meta-review: This paper proposes a low-rank backpropagation algorithm based on Walsh-Hadamart Transformation that is specifically aimed at Vision Transformers (ViT). It demonstrates its effectiveness on pure ViTs and the hybrid ViT-CNN architecture, EfficientFormer. It is competitive with LoRA in terms of memory and FLOPs reduction.
Reviewers recognized that the paper addresses an essential problem with the transformer architecture with a novel solution that achieves promising results. Reviewers raised various points in their review, none of which the AC or SAC viewed as severe. The authors responded to these points, either clarifying or addressing them by additional experiments. The reviewers who responded to author feedback were satisfied by the response. The key recurring theme raised by multiple reviewers was the narrow applicability (claimed ViT-specific). The authors clarified that the approach was applicable to any backprop that employed matrix multiplication, including convolution. The use of EfficientFormer (hybrid ViT-CNN) is an example. Moreover, multiple vision tasks including classification and semantic segmentation were considered.
Less common points were brought up were:
- Insufficient literature review: the authors endeavoured to improve this and acknowledged some requested works were concurrent with the submission.
- Should add larger-scale datasets beyond ImageNet-1k: authors added additional experiments on Places365.
- Should use a SOTA baseline: authors clarified that the baseline was SOTA at the time of submission.
- Should do an open course release: author confirmed that code would be released with acceptance of the paper.
- The method's complementary to other approaches (e.g. LoRA) was claimed but not demonstrated: the authors demonstrated this by showing experiments that showed LBP-WHT with LoRA.
- Needs comparison with Gradient Compression: the authors explained that Gradient Compression was employed after backprop to improve communication while LBP-WHT focused on speeding up backprop.
- Should report GPU hours/memory savings: authors explained why FLOPs had been chosen as the unit of compute. The authors demonstrated memory savings.
- While backprop is sped up, doesn't address inference. This is effectively out-of-scope; the paper was clear about its focus.
The most negative reviewer did not respond to author feedback but it is plausable that they would have increased their score given that their negative points were directly addressed.
We implore the authors to take the promised changes into account in the camera-ready version of the paper and maintain their commitment to release code.
Decision: Accept (poster)