Computational Limits of Low-Rank Adaptation (LoRA) for Transformer-Based Models

我们使用细致的复杂性理论研究了基于Transformer的模型微调中低秩适应（LoRA）更新的计算限制。我们的关键观察是，在LoRA适应的梯度计算中存在低秩分解，这可能导致算法加速。这使我们能够（i）确定相变行为，并（ii）通过逐项控制LoRA更新计算项，假设强指数时间假设（SETH），证明几乎线性算法的存在。对于前者，我们基于从输入序列$\mathbf{X}$、预训练权重$\mathbf{W^\star}$和适配器矩阵$\alpha \mathbf{B} \mathbf{A} / r$相乘得到的特定范数，确定了所有可能的秩-$r$ LoRA更新算法的效率存在尖锐的转变，并推导出这些范数的共享上限阈值，表明仅在该阈值以下存在高效（次二次）的LoRA近似算法。对于后者，我们利用LoRA梯度的层次低秩结构，并将梯度近似为一系列链接的低秩近似，证明了LoRA适应的几乎线性近似算法的存在。为了展示我们的理论，我们考虑了两种实际情况：对注意力头中的权重进行部分调整（例如仅$\mathbf{W}_V$和$\mathbf{W}_Q$），以及对权重进行全面调整（例如$\mathbf{W}_Q$、$\mathbf{W}_V$和$\mathbf{W}_K$）。

本文旨在通过细粒度复杂度理论研究，探讨基于低秩适应（LoRA）更新的Transformer模型微调的计算限制。具体而言，研究低秩分解在LoRA梯度计算中的存在，如何实现算法加速，以及推导出控制LoRA更新计算项的近似线性算法。

本文的关键思路是通过控制LoRA更新的计算项，利用LoRA梯度的分层低秩结构，实现近似线性算法，从而提高Transformer模型微调的效率。

本文通过细粒度复杂度理论，研究了基于低秩适应（LoRA）更新的Transformer模型微调的计算限制，并证明了控制LoRA更新计算项的近似线性算法的存在。实验结果表明，LoRA算法在部分微调和全微调的情况下均取得了良好的效果。值得关注的是，本文提出的算法可以通过控制特定范数来实现算法效率的提高，这一思路具有一定的新意。

最近的相关研究包括：《On the Power of Truncated SVD for General High-rank Matrix Estimation Problems》、《Low-Rank Matrix Approximation in Linear Time》等。