Berechnungslimits der Low-Rank-Anpassung (LoRA) für transformerbasierte Modelle

Wir untersuchen die Berechnungslimits des Low-Rank-Anpassungs (LoRA)-Updates zur Feinabstimmung transformerbasierter Modelle unter Verwendung der feingliedrigen Komplexitätstheorie. Unsere wichtigste Beobachtung ist, dass die Existenz von Low-Rank-Dekompositionen innerhalb der Gradientberechnung der LoRA-Anpassung zu möglichen algorithmischen Beschleunigungen führt. Dies ermöglicht uns (i), ein Phasenübergangsverhalten zu identifizieren, und (ii), die Existenz beinahe linearer Algorithmen zu beweisen, indem wir die LoRA-Updateberechnung stufenweise kontrollieren, vorausgesetzt, die starke exponentielle Zeit-Hypothese (SETH) gilt. Für ersteres identifizieren wir einen deutlichen Übergang in der Effizienz aller möglichen rank-r LoRA-Update-Algorithmen für Transformer, basierend auf spezifischen Normen, die sich aus den Multiplikationen der Eingabesequenz X, vortrainierten Gewichten W^ und Adaptermatrizen B A / r ergeben. Genauer gesagt leiten wir eine gemeinsame obere Schranke für solche Normen ab und zeigen, dass effiziente (unterquadratische) Approximationsalgorithmen von LoRA nur unter dieser Schranke existieren. Für letzteres beweisen wir die Existenz beinahe linearer Approximationsalgorithmen für LoRA-Anpassungen, indem wir die hierarchischen Low-Rank-Strukturen der LoRA-Gradienten nutzen und die Gradienten mit einer Reihe von verketteten Low-Rank-Approximationen annähern. Um unsere Theorie zu veranschaulichen, betrachten wir zwei praktische Szenarien: partielle (z. B. nur WV und WQ) und vollständige Anpassungen (z. B. WQ, WV und WK) der Gewichte in Aufmerksamkeitshorizonten.