← All setups

Locally Initialized LoRA Gradient Descent

Descriptions may be stale. Consult the linked Lean sources.

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.

Results

Let f:Rm×n→R be differentiable, globally μ-strongly convex and ρ-smooth, with exact gradient access and minimizer X⋆=B¯A¯ of rank 0<r<min(m,n). Assume 0<μ≤ρ, 0<s≤R, σr(B¯),σr(A¯⊤)≥s, ∥Dπ(B¯,A¯)∥op≤R, and ∥(B0,A0)−(B¯,A¯)∥F≤μs2/(256ρR). The setup restricts algorithms to simultaneous positive scalar-step factor GD, queried at BA, returning their final factors. Target: f(BA)−f(X⋆)≤ε, ε>0, deterministically.

Local scalar-step LoRA-GD under LocalSmoothStronglyConvexLora.
Result Oracle complexity Novelty Limitations
(1) SilverLoraLocalConvergence (Ours) (review) O(κ^ℓ(κ^)+κ^αℓ(ρR4ε))
(2) Constant-step LoRA-GD (LongTails, n.d.). Derived bound (in-repo). O(κ^ℓ(μ2s4ρε)) (1): Accuracy coefficient κ^α instead of κ^; up to κ^1−α speedup when ℓ(μ2s4/(ρε))≫ℓ(κ^). New local silver-step analysis for nonconvex factors. (1): Worse at moderate accuracy: O(κ^ℓ(κ^)) warmup, with large constants.
(3) Ambient AGD (Bubeck 2015, Thm. 3.18) plus rank-r SVD truncation. Derived bound. O(1+ρμℓ(μs4ε))
Same gradient oracle and target; outside scalar-step factor GD.
(1): Method-specific local silver-step guarantee within scalar LoRA-GD; no established complexity improvement. (1): Never a smaller bound; polynomially worse as ρ/μ or R/s grows. Same order only when ρ/μ,R/s=O(1).
(4) Factored AGD (Li and Lin 2019, Thm. 4, §7). Local initialization and index-set constraints of Thm. 4. O(ρμ∥U⋆∥22σr(U⋆)τℓ(ρ∥U⋆∥22d02ε))
Restricted strong convexity; balancing regularizer, momentum and restarts.
(1): Rates not comparable in (ρ,μ,R,s): these parameters do not control the chosen row-block singular values τ. (1): Requires global rather than restricted strong convexity.

Abbr: Costs count full-gradient calls. π(B,A)=BA; Dπ(B¯,A¯)[HB,HA]=HBA¯+B¯HA. Factor-pair norms are Frobenius norms; ∥⋅∥2 is the matrix spectral norm. κ^=ρR2/(μs2), α=log1+2⁡2≈0.786, ℓ(t)=1+log⁡(1+t). In (4), U⋆ stacks balanced optimal factors, d0=∥U0,0−U⋆∥F, and τ=mini=1,2σr((U⋆)Si) for the selected row sets Si.

Bubeck, Sébastien. 2015. “Convex Optimization: Algorithms and Complexity.” Foundations and Trends in Machine Learning 8 (3–4): 231–358. https://doi.org/10.1561/2200000050.
Li, Huan, and Zhouchen Lin. 2019. Provable Accelerated Gradient Method for Nonconvex Low Rank Optimization. https://doi.org/10.48550/arXiv.1702.04959.
LongTails: LoraWarmup. n.d. Repository source, lemma trajectory. https://github.com/k3nfalt/longtails/blob/main/LongTails/Proofs/LoraWarmup.lean.

Lean setup