← All setups

Silver Lora Local Convergence — Locally Initialized LoRA Gradient Descent

Descriptions may be stale. Consult the linked Lean sources.

Locally Initialized LoRA Gradient Descent · Lean proof

Locally Initialized LoRA Gradient Descent

We consider minimizing a differentiable, strongly convex function f:Rm×n→R with Lipschitz gradient through LoRA factors x=(A,B)∈Rm×r×Rr×n, where m,n,r are positive integers and r<min{m,n}. A global minimizer X⋆ admits full-rank factors with controlled conditioning, and the given starting factors lie in a prescribed neighborhood of those factors. The oracle returns ∇f(X) at X. For ε>0, the goal is final factors x¯=(A¯,B¯) satisfying f(A¯B¯)−f(X⋆)≤ε almost surely under P, the law of the algorithm’s randomness.

Write E=Rm×n and F=Rm×r×Rr×n. We study min(A,B)∈Ff(AB). Matrix spaces carry the Frobenius inner product and norm. The factor space carries the product norm ∥(A,B)∥2=∥A∥F2+∥B∥F2. Vector norms are Euclidean, and ∥⋅∥op denotes the induced operator norm. The algorithm receives m,n,r, the parameters μ,ρ,s,R,ε, and the starting factors x0=(A0,B0), with 0<μ≤ρ,0<s≤R,ε>0.

Our assumptions:

Assumption 1 (Strong convexity and smoothness). The function f is differentiable everywhere on E. For all X,Y∈E, f(Y)≥f(X)+⟨∇f(X),Y−X⟩F+μ2∥Y−X∥F2,∥∇f(X)−∇f(Y)∥F≤ρ∥X−Y∥F.

Assumption 2 (Minimizing factors and local initialization). There exist factors x⋆=(A⋆,B⋆)∈F such that X⋆=A⋆B⋆ is a global minimizer of f on E: f(X⋆)≤f(X)for every X∈E. Define the linear map J⋆:F→E by J⋆(HA,HB)=HAB⋆+A⋆HB. These same factors satisfy ∥J⋆∥op≤R,∥A⋆w∥≥s∥w∥for every w∈Rr,∥(B⋆)⊤w∥≥s∥w∥for every w∈Rr,∥x0−x⋆∥≤μs2256ρR.

Our result is algorithm-specific: we analyze LoRA gradient descent with simultaneous updates of both factors. Starting from the given x0, each iteration queries the product AkBk and uses the returned matrix Gk in Gk=∇f(AkBk),Ak+1=Ak−ηkGk(Bk)⊤,Bk+1=Bk−ηk(Ak)⊤Gk. The scalar step size ηk must be strictly positive for every history and every oracle reply; it may depend on the algorithm’s randomness, its accumulated information, and the current reply. After K≥0 oracle calls, the output is the final factor pair x¯=xK, and it must satisfy f(A¯B¯)−f(X⋆)≤εP-a.s.

Proved result

128⋅⌈64⋅ρ⋅R2μ⋅s2⌉+⋅(⌈log⁡(1+512⋅ρ⋅R2μ⋅s2)log⁡(1+2)⌉++1)+(2⌈log⁡(1+512⋅ρ⋅R2μ⋅s2)log⁡(1+2)⌉+−1)⋅⌈log⁡(1+32⋅ρ⋅R4ε)log⁡(4)⌉+

OracleTemplate.Convergence LongTails.Setups.LocalSmoothStronglyConvexLora.spec
  LongTails.Theorems.SilverLoraLocalConvergence.budget

Relevant previous results

No qualifying prior reference verified; this is not a proof of novelty.