arXiv CSopen access

AdaPaD: Adaptive Parallel Deflation for PEFT with Self-Correcting Rank Discovery

arXiv:2605.10741v1 [cs.LG] 11 May 2026

A DA PA D: Adaptive Parallel Deflation for PEFT with Self-Correcting Rank Discovery

Barbara Su Fangshuo Liao Anastasios Kyrillidis Department of Computer Science Rice University {bs82, Fangshuo.Liao, anastasios}@rice.edu

Abstract Fine-tuning large language models with LoRA [Hu et al., 2022] requires choosing a rank r before training starts. Existing approaches either extract rank-1 components sequentially [Liao et al., 2024, Vandchali et al., 2025], freezing each component’s error permanently into every subsequent residual, or optimize the full low-rank factorization jointly [Zangrando et al., 2025, Shinwari and Usama, 2025] with guarantees that describe only the joint update, not individual rank-1 directions. We present A DA PA D (Adaptive Parallel Deflation), which trains all rank-1 components simultaneously: each worker refines its component against a deflation target built from the latest estimates of all predecessors, and as those estimates improve, the targets improve too. We call this property self-correction: deflation errors converge to zero over rounds rather than persisting as fixed residuals. On top of this backbone, A DA PA D adds advance learning (private pre-training before activation) and permodule dynamic rank discovery (importance-based growth until a shared budget is exhausted), making the rank distribution an output rather than an input. We prove that every component’s error decays exponentially after a warm-up period, with a generalization bound that splits into a vanishing algorithmic term and an irreducible statistical floor. Empirically, A DA PA D is competitive with adaptive-rank LoRA baselines on GLUE with DeBERTaV3-base at matched parameter budgets, and competitive with fixed-rank LoRA on Qwen3-0.6B SQuAD/SQuAD v2 while deploying an adapter that is on average 30.7% smaller. §

1

Introduction

Parameter-efficient fine-tuning (PEFT) is the standard way to adapt large pretrained models to downstream tasks. Among the many approaches [Houlsby et al., 2019, Li and Liang, 2021, Ben Zaken et al., 2022], Low-Rank Adaptation (LoRA) [Hu et al., 2022] stands out for its simplicity: for a pretrained weight W ∈ Rm×d , LoRA freezes W and trains a low-rank update ∆W = BA⊤ with B ∈ Rm×r , A ∈ Rd×r and rank r ≪ min(m, d) a hyperparameter. LoRA is effective in practice, but leaves a fundamental design choice unresolved: how should r be chosen? In practice r is set by hand and applied uniformly to every layer [Hu et al., 2022, Hayou et al., 2024, Liu et al., 2024], yet the appropriate rank varies across modules, tasks, and training stages. Adaptive-rank methods address this in different ways: AdaLoRA [Zhang et al., 2023b] prunes from high rank using SVD importance, IncreLoRA [Zhang et al., 2023a] grows from low rank by activating reserve components, DyLoRA [Valipour et al., 2023] trains across a range of ranks, and SoRA [Ding et al., 2023] learns sparse gates. Recent theoretical work analyzes the joint BA⊤ update: dEBORA [Zangrando et al., 2025] uses bilevel Frank-Wolfe with rank-identifiability guarantees, and ARD-LoRA [Shinwari and Usama, 2025] adds learnable per-head scaling with a stationary-point theorem. Both treat the full low-rank matrix as one object; we instead decompose the problem into independent rank-1 subproblems trained in parallel and analyze each separately, yielding a guarantee Preprint.

joint optimization cannot express: self-correction, where the deflation mismatch in each rank-1 worker provably vanishes over rounds, so individual rank-1 directions can be certified correct rather than only their joint sum. Key insight: parallel deflation with self-correction. In sequential deflation, errors in early components are permanently frozen and compound multiplicatively through the spectral gap [Vandchali et al., 2025]. We remove this dependency by training all rank-1 components simultaneously: each is assigned to a dedicated worker that, at every communication round, rebuilds its deflation target from the latest predecessor estimates, so early mistakes are progressively corrected rather than locked in. We call this property self-correction and prove that the deflation mismatch ∥Yk,ℓ − Yk⋆ ∥F vanishes as ℓ grows (Proposition 2), in contrast to sequential deflation [Vandchali et al., 2025, Liao et al., 2024] where the mismatch is fixed and generically nonzero. The bilinear setting differs from symmetric eigendecomposition [Liao et al., 2025]: the asymmetric structure ba⊤ X calls for Wedin perturbation theory [Wedin, 1972] and a data-dependent recovery scale. Two further mechanisms make parallel deflation practical for LoRA: advance learning (private warm-up of dormant components against improving targets) and per-module dynamic rank discovery (importance-driven growth under a global budget). Contributions. C1. A DA PA D algorithm (Algorithms 1 and 2). Parallel rank-1 deflation with advance learning (private pre-training before activation) and per-module dynamic rank discovery (importancebased growth under a shared budget); the rank distribution is an output, not an input. C2. Theoretical guarantees. Exponential convergence with vanishing deflation mismatch (Theorem 1 and Proposition 2) and a weight-recovery bound that splits into a vanishing algorithmic term plus an irreducible statistical floor (Theorems 3 and 4); to our knowledge, the first selfcorrecting guarantee for parallel rank-1 deflation in bilinear regression, structurally distinct from the joint-update guarantees of [Zangrando et al., 2025, Shinwari and Usama, 2025]. C3. Empirical evaluation. At approximately matched budgets (0.32–0.47 M) on GLUE with DeBERTaV3-base, A DA PA D is competitive with IncreLoRA, AdaLoRA, SoRA, and dEBORA across all eight tasks (Section 5.1); on Qwen3-0.6B SQuAD/SQuAD v2 it matches fixed-rank LoRA on F1/EM with adapters 30.7% smaller on average (Section 5.2); component-parallel sharding delivers up to 2.66× speedup on 4×H200 (Section 5.3). Related work. Deflation-based methods. Hotelling’s deflation [Hotelling, 1933] is the classical approach for extracting principal components; Mackey [2008] extended it to sparse PCA. Error propagation in inexact sequential deflation was analyzed by Liao et al. [2024] and Vandchali et al. [2025]. The model-parallel perspective was introduced by EigenGame [Gemp et al., 2021, 2022], which casts top-K PCA as a multi-player game. Liao et al. [2025] gave the first provable parallel deflation algorithm for PCA; we develop parallel deflation for the bilinear regression setting, where the asymmetric structure ba⊤ X requires Wedin-type perturbation analysis and the self-correction guarantee is tied to a data-dependent recovery scale. ReLoRA [Lialin et al., 2024] trains a sequence of low-rank updates that sum to a high-rank result, which is sequential deflation under a different name; our approach differs by running all components in parallel with provable self-correction. Low-rank optimization. Problem (1) has been attacked via nuclear norm minimization [Candès and Recht, 2009, Recht et al., 2010], projected gradient descent [Jain et al., 2010, Kyrillidis and Cevher, 2014], and factored methods [Burer and Monteiro, 2003, Tu et al., 2016b, Kyrillidis et al., 2018, Park et al., 2017, Bhojanapalli et al., 2016, Park et al., 2018, Kim et al., 2023, Geyer et al., 2020, Hsieh et al., 2018]. These optimize the full low-rank matrix jointly but do not decompose into independent rank-1 subproblems. Kim et al. [2025] show that fixed-rank LoRA training converges to a low-rank global minimum or diverges detectably, but this addresses the fixed-rank setting without rank adaptation. Adaptive-rank methods with convergence theory. dEBORA [Zangrando et al., 2025] formulates rank selection as bilevel optimization: an upper-level Frank-Wolfe on an ℓ1 -constrained simplex selects singular-value scaling factors while a lower-level solver trains the basis matrices. dEBORA √ proves O(1/ T ) convergence of the upper level and, notably, finite-time rank identification (the algorithm provably discovers which singular values are zero). As a joint optimization method, dEBORA does not decompose into rank-1 subproblems and therefore does not face the deflation error 2

propagation problem; its convergence guarantee applies to the upper-level simplex variable, not to the bilinear BA⊤ factorization itself. ARD-LoRA [Shinwari and Usama, 2025] introduces learnable per-head scaling factors with O(1/T ) convergence to a stationary point via a standard descent lemma; the guarantee is generic smooth optimization and does not exploit the bilinear structure. Neither decomposes into rank-1 subproblems nor exhibits self-correction (Proposition 2).

2

Background and Problem Setup

Low-Rank Regression and LoRA. We study the linear model Y = W⋆ X + E, where W⋆ ∈ Rm×d has rank r⋆ , X ∈ Rd×n collects input features, Y ∈ Rm×n is the response, and E is noise (E = 0 in the noiseless case; Eij ∼ N (0, ε2 ) in the noisy case). The goal is to solve min

A∈Rr×d ,B∈Rm×r

1 2 ∥Y − BAX∥F . 2

(1)

This directly models LoRA: for a pretrained layer with weight W0 , taking X as the input activations and Y = ∆W · X reduces LoRA training to (1) with W⋆ = ∆W = BA⊤ . Sequential vs. Parallel Deflation. Sequential deflation extracts components one at a time: set ⊤ Y1 = Y, compute (ak , bk ) = PRank1(Yk , X, Tk ) with budget Tk , then Yk+1 = Yk − bk ak X. Two defects: wall-clock time k Tk , and frozen errors that compound multiplicatively [Vandchali et al., 2025]. Parallel deflation assigns each component to its own worker and indexes rounds by ℓ = 1, . . . , L. At round ℓ,Pworker k holds (ak,ℓ , bk,ℓ ) and uses the latest predecessor estimates to ⋆ ⋆ recompute Yk,ℓ := Y − k′ <k bk′ ,ℓ−1 a⊤ k′ ,ℓ−1 X. The starred quantities (ak , bk ) denote the ideal components of the clean target (Section 2). Table 1 contrasts the three regimes: the parallel target Yk,ℓ improves over rounds rather than being fixed. Table 1: Deflation targets for component k under three deflation regimes. Exact sequential [Hotelling, 1933, Mackey, 2008] uses ideal predecessor outputs (unavailable in practice, since they require ground-truth singular vectors); inexact sequential [Liao et al., 2024, Vandchali et al., 2025] freezes approximate predecessors; parallel deflation refreshes the target every round with the latest predecessor estimates, so the target itself converges as ℓ → ∞. Method Exact Sequential Inexact Sequential Parallel (Ours)

Deflation target for component k P Yk⋆ = Y − k′ <k b⋆k′ a⋆⊤ k′ X P Yk = Y − k′ <k bk′ a⊤ k′ X P Yk,ℓ = Y − k′ <k bk′ ,ℓ−1 a⊤ k′ ,ℓ−1 X

Property Fixed, ideal Fixed, approximate Improves over rounds

Ideal Rank-1 Fit and Error Decomposition. Fix k ∈ [r] and round ℓ. The ideal rank-1 fit of Yk,ℓ is its best rank-1 Frobenius approximation, (āk,ℓ , b̄k,ℓ ) ∈ arg min a∈Rd ,b∈Rm

Yk,ℓ − ba⊤ X F ,

(2)

satisfying b̄k,ℓ ā⊤ X = σ1k ,ℓ u1k ,ℓ v1⊤k ,ℓ when the top triplet is unique. Define the clean deflation k,ℓP target Yk⋆ = Y − k′ <k b⋆k′ a⋆⊤ k′ X (exact sequential, top row of Table 1); its best rank-1 fit defines ⋆ ⋆ ⋆⊤ the ideal k-th component (a⋆k , b⋆k ) with b⋆k a⋆⊤ k X = σk uk vk via Eckart–Young–Mirsky [Eckart and Young, 1936, Mirsky, 1960]. Following the numerical-vs.-mismatch split of [Liao et al., 2024, Vandchali et al., 2025, Liao et al., 2025], we decompose worker k’s error at round ℓ into the numerical error, deflation mismatch, and total error: ⊤ Dk,ℓ ≜ bk,ℓ a⊤ k,ℓ X − b̄k,ℓ āk,ℓ X F ,

Bk,ℓ ≜ Gk,ℓ ≜

⋆ ⋆⊤ b̄k,ℓ ā⊤ k,ℓ X − bk ak X F , ⋆ ⋆⊤ bk,ℓ a⊤ k,ℓ X − bk ak X F .

(Numerical error)

(3)

(Deflation mismatch)

(4)

(Total error)

(5)

The triangle inequality gives Gk,ℓ ≤ Dk,ℓ + Bk,ℓ : Dk,ℓ vanishes as the subroutine iterates, Bk,ℓ shrinks as predecessors improve, and our proof shows both vanish as ℓ → ∞. 3

Algorithm 1 Parallel Rank-1 Deflation for Low-Rank Regression Require: X ∈ Rd×n , Y ∈ Rm×n , rank r, local iterations T , rounds L ≥ r, projection radius Q ≥ σ1⋆ Ensure: Components {(ak,L , bk,L )}rk=1 1: for k = 1, . . . , r do 2: Randomly initialize (ak,0 , bk,0 ) 3: end for 4: for ℓ = 1, . . . , L do 5: parfor k = 1, . . . , r do ▷ All r workers in parallel 6: if k ≤ ℓ then ▷ Staggered activation ′ ,ℓ−1 )}k ′ <k 7: Receive {(ak′ ,ℓ−1 , b k P 8: Yk,ℓ ← Y − k′ <k bk′ ,ℓ−1 a⊤ ▷ Deflate with latest estimates k′ ,ℓ−1 X 9: (ak,ℓ , bk,ℓ ) ← Rank1(Yk,ℓ , X, T, a , b ) ▷ Warm-started k,ℓ−1 k,ℓ−1
⊤ 10: bk,ℓ a⊤ X ← Π b a X ▷ Project onto Frobenius ball of radius Q Q k,ℓ k,ℓ k,ℓ 11: Broadcast (ak,ℓ , bk,ℓ ) 12: else 13: (ak,ℓ , bk,ℓ ) ← (ak,ℓ−1 , bk,ℓ−1 ) 14: end if 15: end parfor 16: end for 2.1

Assumptions

Assumption 1 (Rank-1 Subroutine Contraction). For each component k, there exists a contraction factor Fk ∈ (0, 1) such that the rank-1 subroutine, warm-started from (ak,ℓ−1 , bk,ℓ−1 ), satisfies for ⊤ ⊤ ≤ Fk bk,ℓ−1 a⊤ all ℓ ≥ k: bk,ℓ a⊤ , where (āk,ℓ , b̄k,ℓ ) k,ℓ X − b̄k,ℓ āk,ℓ X k,ℓ−1 X − b̄k,ℓ āk,ℓ X F F is the ideal rank-1 fit defined in (2). Assumption 2 (Spectral Gap). Y = W⋆ X has distinct singular values σ1⋆ > σ2⋆ > · · · > σr⋆ > 0 with gaps Tk⋆ := min{minj>k |σk⋆ − σj⋆ |, σk⋆ } > 0. We normalize σ1⋆ = 1. Assumption 3 (Bounded Rank-1 Recovery via Projection). Parameter Q in Algorithm 1 satisfies Q ≥ 2σ1⋆ .

The projection in Algorithm 1 together with the assumption above implies the per-component magnitude bound Gk,ℓ ≤ Rk := Q + σk⋆ used throughout the proofs (Lemma 7 in Section D). All three assumptions are standard: Assumption 1 is the rank-1 subroutine regularity condition [Liao et al., 2025], holding for ALS (Fk controlled by the local spectral ratio) and factored GD at small step size [Jain et al., 2013, Zheng and Lafferty, 2015, Kyrillidis et al., 2018, Park et al., 2017, Bhojanapalli et al., 2016, Park et al., 2018, Kim et al., 2023, Geyer et al., 2020, Hsieh et al., 2018] (pseudocode in Section A); Assumption 2 is the spectral-gap condition for deflation [Liao et al., 2024, Vandchali et al., 2025, Liao et al., 2025] (σ1⋆ = 1 is a rescaling); Assumption 3 is automatic given the projection step in Algorithm 1, and the resulting magnitude bound (Lemma 7) is in the same spirit as bounded-iterate constructions in nonconvex factor recovery [Tu et al., 2016a, Bhojanapalli et al., 2016, Park et al., 2018, Ge et al., 2017]. In practice, Assumption 1 only needs to hold for ℓ ≥ sk (the warm-up round in Theorem 1 via Equation (32)), by which point predecessor errors preserve the top-triplet structure of Yk,ℓ . Background perturbation results (Weyl, Wedin) are in Section B.

3

A DA PA D: The Algorithm

Base Algorithm: Parallel Rank-1 Deflation. Algorithm 1 parallelizes inexact sequential deflation [Liao et al., 2024, Vandchali et al., 2025, Liao et al., 2025] for the bilinear model; we assume one worker per component for exposition (when P < r, components are sharded round-robin via a single all gather per round). Three mechanisms drive convergence: staggered activation (worker k begins at ℓ = k), warm-starting from (ak,ℓ−1 , bk,ℓ−1 ), and deflation with current estimates. The projection on Algorithm 1 caps each rank-1 estimate’s Frobenius norm at Q ≥ σ1⋆ , making the bounded-recovery bound Lemma 7 automatic without affecting fixed points (the ideal estimate has 4

Algorithm 2 A DA PA D: Parallel Deflation with Per-Module Rank Discovery Require: Model with M adapter modules, max rank rmax , budget B, growth interval ∆, top-h, projection radius Q ≥ σ1⋆ (inherited by per-component updates as in Algorithm 1) i Ensure: Per-module components {(ai,k , bi,k )}rk=1 for i = 1, . . . , M 1: ri ← 1 for all i; R ← M ▷ Total active rank 2: for round = 1, . . . , ⌈Ttotal /∆⌉ do 3: Cache ∆ mini-batches B = {B1 , . . . , B∆ } 4: Snapshot committed components for all modules ▷ Self-correction 5: for each batch Bj ∈ B do 6: parfor component k owned by this worker do 7: Forward with snapshot prefix [0, k) + current component k 8: Backward; update (ai,k , bi,k ) 9: end parfor 10: end for 11: Update importance EMAs S̄i , Ui via (7) 12: if R < B then 13: Select top-h modules by S̄i · Ui (among those with ri < rmax ) 14: for each selected module i do 15: Activate reserve → committed; ri ← ri + 1; R ← R + 1 16: Spawn new reserve (advance learning) 17: end for 18: end if 19: end for

norm σk⋆ ≤ Q). The projection in Algorithm 1 prevents the recovered component bk,ℓ a⊤ k,ℓ X from blowing up while the deflated target Yk,ℓ has not yet tightened around Yk⋆ enough for the rank-1 subroutine to begin contracting. In practice we find that taking Q = ∞ (i.e., skipping the projection) suffices. Two extensions, advance learning and dynamic rank discovery, follow. Advance Learning. In Algorithm 1, worker k is idle for rounds 1, . . . , k−1. Inspired by IncreLoRA’s reserve components [Zhang et al., 2023a], we use this idle time: before activation, worker k privately runs the rank-1 subroutine against its current deflation target without broadcasting, accumulating a good initialization. Unlike IncreLoRA’s reserves, the warming component trains against the correct target Yk,ℓ , which itself improves over rounds via self-correction. Theoretically, advance learning tightens the convergence constant: the worst-case leading factor 3Rk in Theorem 1 is replaced by Rk (Fksk −1 + 2) when pre-activation contraction yields Dk,sk −1 ≪ Rk . Dynamic Rank Discovery. Attention and FFN sub-layers need different capacity, and the right allocation varies with depth and task [Zhang et al., 2023b,a, Ding et al., 2023], motivating per-module rank assignment. A DA PA D (Algorithm 2) maintains a per-module active rank ri (initially 1, capped at rmax ), a shared budget B, and one private reserve per module via advance learning. Every ∆ mini-batches (one global round, after a one-round warm-up), the top-h eligible modules (ri < rmax ) promote their Preserve to a committed component and start advance learning on a new reserve; growth stops when i ri ≥ B. Importance scoring. We adopt the importance-uncertainty product from IncreLoRA [Zhang et al., 2023a]: a module deserves capacity if its parameters are both large in magnitude and still receiving large gradient updates. With θ i the committed (a, b) entries of module i, the raw importance at step t is X 1 (t) Si = p |p| · |∇p L|, (6) ∥θ i ∥2 p∈θi normalized for comparability across module sizes. Two EMAs (β1 =β2 =0.85) track signal and (t) (t) volatility, and the allocation score is their product S̄i Ui : (t)

S̄i

(t−1)

= β1 S̄i

(t)

+ (1−β1 )Si ,

(t)

Ui

5

(t−1)

= β2 Ui

(t)

(t)

+ (1−β2 )|Si − S̄i |.

(7)

This per-module allocation is analogous to IncreLoRA’s incremental growth but combined with parallel deflation and self-correction: committed components are snapshotted every ∆ mini-batches, and new components train against improving deflation targets.

4

Theoretical Guarantees

Scope. Our analysis is formulated for the bilinear regression model Y = W⋆ X + E (Equation (1)), the exact structure of a single LoRA adapter layer; assumptions hold for ALS and factored GD [Jain et al., 2013, Zheng and Lafferty, 2015]. We treat each layer’s subproblem in isolation and do not model the end-to-end nonlinear loss, as in dEBORA [Zangrando et al., 2025] and ARD-LoRA [Shinwari and Usama, 2025]; the gap to nonlinear practice is bridged empirically in Section 5.1, with NTK [Jacot et al., 2018, Arora et al., 2019] or local-linearization [Lee et al., 2019, Malladi et al., 2023] extensions deferred (Section 6). Proofs are in Section D; recall Gk,ℓ ≤ Dk,ℓ + Bk,ℓ from Section 2. Main Convergence Result. After a component-dependent warm-up, every component’s total error decays nearly-linearly (exponential decay modulated by a mild linear prefactor). Theorem 1 (Convergence of Parallel Rank-1 Deflation). Under Assumptions 1 to 3, where Fk ∈ (0, 1) is the per-component contraction factor of Assumption 1 and Rk > 0 is the magnitude bound of Lemma 7, define effective rates m1 = F1 and n o 1 k−1 mk = max Fk , + mk−1 for k ≥ 2, (8) k k and starting rounds s1 = 1 with sk+1 chosen per-predecessor (i.e., as a maximum over k ′ ≤ k) so that
! ⋆ log k Ck+1 Rk′ /Tk+1 (k + 1) mk e sk+1 = max sk′ + O + (9) k′ ≤k 1 − mk 1 − mk (full Lambert-W form and proof in Section D.2, Corollary 11). Then for all k ∈ [r] and ℓ ≥ sk − 1: Gk,ℓ ≤ 3Rk (ℓ − sk + 2)mkℓ−sk +1 .

(10)

Remark 1 (Interpretation of (10)). Each mk ∈ (0, 1) (Section D.7), so the geometric factor dominates the linear prefactor and the bound vanishes exponentially. Proof by strong induction on k (Section D.2); empirical validation in Figures 2, 5 and 6. Self-Correction. The defining advantage of parallel over sequential deflation: errors are transient, not permanent. Proposition 2 (Self-Correction). Under the conditions of Theorem 1, for all ℓ ≥ sk : ∥Yk,ℓ − Yk⋆ ∥F ≤ 3

k−1 X

ℓ−s

ℓ→∞

Rk′ (ℓ − sk′ + 1)mk′ k′ −−−→ 0.

(11)

k′ =1

In sequential deflation, ∥Yk − Yk⋆ ∥F is fixed after step k and generically nonzero. P The proof bounds ∥Yk,ℓ − Yk⋆ ∥F ≤ k′ <k Gk′ ,ℓ−1 via Lemma 9 and applies Theorem 1 to force each Gk′ ,ℓ−1 → 0 (Section D). Table 2 summarizes the differences; see Figure 3. Estimation Bounds. The self-correction advantage propagates to weight estimation. Theorem 3 (Noiseless estimation). If Y = W⋆ X with rank(W⋆ ) = r⋆ and σmin (X) > 0, then after L rounds: ⋆

W −

Pr

⊤ k=1 bk,L ak,L

r⋆

r

k=r+1

k=1

 X  X 1 ≤ σk⋆ + Gk,L , σmin (X) F

(12)

where σk⋆ denotes the k-th singular value of Y = W⋆ X. The second term vanishes as L → ∞ by Theorem 1; in the sequential baseline [Vandchali et al., 2025] the corresponding term is permanently positive. 6

Table 2: Sequential vs. parallel rank-1 deflation. “Front-loaded compute” means a disproportionate share of iterations Tk must be spent on the first few components, since their errors propagate to all later ones; under parallel deflation a uniform per-component budget suffices because predecessor errors are corrected over rounds. Property Wall-clock time Deflation mismatch Error propagation Compute allocation Estimation error

Sequential [Vandchali et al., 2025] Pr k=1 Tk Fixed, generally nonzero Accumulates and persists Front-loaded compute essential Fixed algorithmic term

Parallel (ours) LT (up to r× faster) Vanishes as ℓ → ∞ Self-corrects over rounds Uniform per-component budget suffices Vanishes as L → ∞

p √ ⋆ Theorem 4 (Noisy estimation). Under Eij ∼ N (0, ε2 ) with ε ≤ O(Tmin /( n + log(1/γ))), with probability ≥ 1 − γ: P  P P ⋆ −1 W⋆ − k bk,L a⊤ ≤ κ(X) k,L k>r σk (W ) + σmax (X) k Gk,L F {z } | algorithmic (vanishes)

+O |

 εpn log(1/γ)  σmin (X) {z

r r+

statistical (irreducible)

r  ⋆ Tmin

(13) .

}

P The algorithmic term vanishes via k Gk,L → 0 (Theorem 1); the statistical floor matches the Gaussian-perturbation bound for deflation-based recovery [Vandchali et al., 2025, Thm. 3], so parallelization adds no new noise penalty (the sequential analogue’s algorithmic term stays positive; here it decays in L; floor matches Figure 4). Advance learning tightens the leading constant 3Rk in (10) via sk − 1 rounds of private refinement.

5

Experiments

We evaluate A DA PA D along three axes. Section 5.1 compares it against four adaptive-rank LoRA baselines on GLUE classification with DeBERTaV3-base. Section 5.2 measures its parameter efficiency against fixed-rank LoRA on Qwen3-0.6B SQuAD/SQuAD v2 reading comprehension. Section 5.3 measures multi-GPU wall-clock scaling of component-parallel sharding (assigning disjoint subsets of A DA PA D’s rank-1 components to different workers, each holding a private copy of the backbone) on the same Qwen3-0.6B + SQuAD workload. All experiments run on 4×H200 NVLink; settings in Section G. 5.1

GLUE Classification

Setup. We fine-tune DeBERTaV3-base on the eight GLUE tasks [Wang et al., 2019] and compare A DA PA D against fixed-rank LoRA and three adaptive-rank baselines: (i) LoRA (r=2); (ii) A DA PA D (rmax =4, dynamic) at total rank budget B=144, matching IncreLoRA’s parameter budget; (iii) IncreLoRA [Zhang et al., 2023a], reproduced with the authors’ code and published hyperparameters; (iv) AdaLoRA [Zhang et al., 2023b], SoRA [Ding et al., 2023], and dEBORA [Zangrando et al., 2025] from their published numbers. Parameter budgets are approximately matched (0.32–0.47 M trainable parameters across methods); rank-1 adapters attach to all 72 encoder linear layers (six per layer × 12 layers: Wq , Wk , Wv , Wo , Wf 1 , Wf 2 ), matching IncreLoRA. In practice we use Q = ∞ (no projection) as the simplest design choice and find this is sufficient for empirical convergence in all our experiments. Main results. A DA PA D achieves the highest GLUE average (89.34) in Table 3, ahead of AdaLoRA (89.03) and our IncreLoRA reproduction (88.99). On the five small- and medium-scale tasks (CoLA, RTE, MRPC, STS-B, SST-2; ≤ 67k training examples) A DA PA D wins four outright and loses RTE by 1.08 points, three examples on the 276-example dev set. On the three large-scale tasks (QNLI, QQP, MNLI; ≥ 105k training examples), A DA PA D stays within 0.6 points of the best baseline (each below 0.6% relative loss): −0.13 on QNLI, −0.51 on QQP, −0.29 on MNLI. 7

Table 3: GLUE development-set results with DeBERTaV3-base at matched parameter budgets. A DA PA D discovers rank dynamically (rmax =4). Published results are cited from the respective papers; ∗ denotes our reproduction with the authors’ code. Bold: best in column. Avg. is the unweighted mean across the eight tasks. Method

#Params

CoLA (MCC)

RTE MRPC (Acc) (Acc)

STS-B (Pear.)

SST-2 (Acc)

QNLI (Acc)

QQP MNLI (Acc) (Acc)

Avg.

LoRA (r=2) A DA PA D

0.34M 0.34M

63.56 72.26

79.06 86.28

78.86 91.67

90.47 91.86

94.95 96.33

94.03 94.36

91.61 91.55

90.30 90.37

85.36 89.34

IncreLoRA∗ AdaLoRA SoRA (rmax =4) dEBORA

0.34M 0.32M 0.47M 0.40M

71.85 70.04 71.05 68.72

85.92 87.36 86.04 83.75

90.20 90.44 90.20 90.16

91.68 91.63 91.76 90.84

96.22 95.80 95.57 95.29

93.50 94.49 93.92 93.42

91.94 91.78 92.06 91.88

90.59 90.66 90.38 90.01

88.99 89.03 88.87 88.01

Table 4: Ablation on CoLA and MRPC. Each row removes one component from the full A DA PA D algorithm. ∆: change from the full model. CoLA (MCC)

MRPC (Acc)

Variant

Score

∆

Score

∆

A DA PA D w/o advance learning w/o dynamic rank (fixed r=2) w/o importance scoring (uniform)

72.26 71.05 63.56 69.57

— −1.21 −8.70 −2.69

91.67 90.44 78.86 89.95

— −1.23 −12.81 −1.72

Discovered rank distribution. Figure 1 shows per-module rank on CoLA at convergence: of 72 modules, 16/44/8/4 sit at rank 1/2/3/4. FFN intermediate Wf 1 averages 2.67 and attention output Wo averages 2.17, while Wf 2 stays lowest (1.58); layer 11 averages 3.67, consistent with last-layer task-specificity [Zhang et al., 2023b]. Forcing fixed rank costs 8.70 MCC (Table 4).

2 2 2 2 2 2 0

2 2 2 2 3 2 1

2 1 2 2 3 1 2

2 2 1 2 2 1 3

1 2 1 2 3 1

2 2 2 2 3 1

2 1 2 2 3 2

1 1 2 2 3 1

4 5 6 7 Transformer Layer

1 2 2 2 2 1 8

2 2 2 2 2 2 9

2 2 1 2 2 1

10

3 3 4 4 4 4

4 3

Rank

Module

Wq Wk Wv Wo Wf1 Wf2

2 1

11

Figure 1: Per-module rank discovered by A DA PA D on CoLA (avg = 2.0); 72 modules (6 types × 12 layers). Higher rank concentrates in the last layer and FFN intermediate projections. Ablation study. Table 4 isolates A DA PA D’s three ingredients on CoLA and MRPC: dynamic rank discovery is the largest contributor (−8.70 MCC, −12.81 Acc when replaced by fixed r=2), then importance scoring (−2.69, −1.72 vs. uniform), then advance learning (−1.21, −1.23). 5.2

Parameter Efficiency on Reading Comprehension

We test A DA PA D on Qwen3-0.6B fine-tuned for QA on SQuAD v1.1 and SQuAD v2 [Rajpurkar et al., 2016, 2018] (generative decoder, adapters on seven projections Wq , Wk , Wv , Wo , Wgate , Wup , Wdown ; 196 modules). LoRA uses uniform rank r ∈ {4, 6}; A DA PA D uses average-rank budget r̄ ∈ {4, 6} with rmax =8 (full settings in Section G.2). For each cell we report the smallest A DA PA D adapter that matches or beats same-budget LoRA on F1, with parameter reduction ∆Par. Across the four cells (Table 5), A DA PA D yields adapters 15.9–44.3% smaller than fixed-rank LoRA (mean 30.7%) while remaining competitive on F1/EM; a complementary view to GLUE, which fixes the budget and reads off quality. 8

Table 5: Matched-budget head-to-head on Qwen3-0.6B SQuAD/SQuAD v2 (seed=43; bf16; identical recipe across all cells; full settings in Section G.2). Bold: A DA PA D matches or beats LoRA at the cell. LoRA (fixed-rank r) Task

b Params

EM

∆Par

EM

Params

F1

4 SQuAD v1.1 6

2.52M 3.79M

88.48 80.65 88.93 81.42

2.12M 2.11M

88.83 80.77 −15.9% 89.02 81.09 −44.3%

4 6

2.52M 3.79M

73.45 70.33 73.91 70.66

1.93M 2.30M

73.63 70.70 −23.4% 73.99 70.91 −39.3%

SQuAD v2

F1

A DA PA D (r̄)

Table 6: Component-parallel scaling on Qwen3-0.6B + SQuAD v1.1. Per-batch wall-clock cost (mean ± std over five global rounds) and speedup vs. P =1 at the same rank. Bold: best speedup in each rank column. rmax =4

5.3

rmax =8

#GPUs

per-batch (s)

speedup

1 2 3 4

0.986 ± 0.011 1.00× 0.532 ± 0.006 1.85 ± 0.03× 0.487 ± 0.006 2.03 ± 0.03× 0.403 ± 0.047 2.45 ± 0.29×

per-batch (s)

speedup

2.039 ± 0.015 1.00× 1.062 ± 0.008 1.92 ± 0.02× 0.806 ± 0.009 2.53 ± 0.04× 0.768 ± 0.074 2.66 ± 0.26×

Multi-GPU Scaling on Qwen3-0.6B

A DA PA D admits component-parallel sharding: each worker holds a disjoint subset of the rank-1 components and trains them independently between syncs, predicting near-linear speedup. We measure this on the SQuAD v1.1 workload of Section 5.2, disabling per-module growth and pinning every module at rmax to fix the total at 196 × rmax across P ∈ {1, 2, 3, 4} at each rmax ∈ {4, 8}. We report mean ± std over five global rounds (hyperparameters in Section G.2). The 1-3 GPU cells are highly stable (rel. std < 1.5%): three workers deliver 2.03× at rmax =4 and 2.53× at rmax =8. At P =4 we see 2.45× and 2.66× with higher variance (rel. std ≈10%), as the 4-way NVLink all-reduce makes NCCL latency dominate when per-worker compute shrinks; overlap-friendly schedules [Li et al., 2020, Sergeev and Del Balso, 2018] and bandwidth-aware placement [Rajbhandari et al., 2020, Shoeybi et al., 2019] are future work.

6

Discussion and Conclusion

A DA PA D addresses two LoRA design questions: parallel training keeps early rank-1 components from corrupting later ones, and per-module dynamic rank discovery makes the rank distribution an output of importance scores rather than a fixed input. We prove nearly-linear convergence with a selfcorrecting deflation mismatch and an estimation bound that splits into a vanishing algorithmic term plus an irreducible statistical floor. Empirically, A DA PA D achieves the highest GLUE average against four adaptive-rank baselines (Section 5.1), produces Qwen3-0.6B SQuAD/SQuAD v2 adapters 30.7% smaller than fixed-rank LoRA at competitive F1/EM (Section 5.2), and component-parallel sharding delivers up to 2.66× speedup on 4×H200 (Section 5.3). Limitations and future work. The theory covers the bilinear model (1); extension to nonlinear LoRA losses is empirical, bounds degrade as Tk⋆ → 0, and synchronous O(r2 (d + m)) communication can offset the speedup at very large r. Validation at 7B+ scale, NTK [Jacot et al., 2018, Arora et al., 2019] or local-linearization [Lee et al., 2019, Malladi et al., 2023] extensions, asynchronous communication, and richer importance scores are future work.

References Sanjeev Arora, Simon S. Du, Wei Hu, Zhiyuan Li, Russ Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. In Advances in Neural Information Processing 9

Systems (NeurIPS), 2019. Elad Ben Zaken, Shauli Ravfogel, and Yoav Goldberg. BitFit: Simple parameter-efficient fine-tuning for transformer-based masked language-models. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pages 1–9, 2022. Srinadh Bhojanapalli, Anastasios Kyrillidis, and Sujay Sanghavi. Dropping convexity for faster semi-definite optimization. In Conference on Learning Theory, pages 530–582. PMLR, 2016. Samuel Burer and Renato D. C. Monteiro. A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization. Mathematical Programming, 95(2):329–357, 2003. Emmanuel J. Candès and Benjamin Recht. Exact matrix completion via convex optimization. Foundations of Computational Mathematics, 9(6):717–772, 2009. Ning Ding, Xingtai Lv, Qiaosen Wang, Yulin Chen, Bowen Zhou, Zhiyuan Liu, and Maosong Sun. Sparse low-rank adaptation of pre-trained language models. In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 4133–4145, 2023. Carl Eckart and Gale Young. The approximation of one matrix by another of lower rank. Psychometrika, 1(3):211–218, 1936. Rong Ge, Chi Jin, and Yi Zheng. No spurious local minima in nonconvex low rank problems: A unified geometric analysis. In Proceedings of the 34th International Conference on Machine Learning (ICML), pages 1233–1242, 2017. Ian Gemp, Brian McWilliams, Tuomas Sandholm, and Claire Vernade. EigenGame: PCA as a Nash equilibrium. In International Conference on Learning Representations, 2021. Ian Gemp, Brian McWilliams, Tuomas Sandholm, and Claire Vernade. EigenGame unloaded: When playing games is better than optimizing. In International Conference on Learning Representations, 2022. Kelly Geyer, Anastasios Kyrillidis, and Amir Kalev. Low-rank regularization and solution uniqueness in over-parameterized matrix sensing. In International Conference on Artificial Intelligence and Statistics, pages 930–940. PMLR, 2020. Soufiane Hayou, Nikhil Ghosh, and Bin Yu. LoRA+: Efficient low rank adaptation of large models. In Proceedings of the 41st International Conference on Machine Learning (ICML), 2024. Pengcheng He, Jianfeng Gao, and Weizhu Chen. DeBERTaV3: Improving DeBERTa using ELECTRA-style pre-training with gradient-disentangled embedding sharing. In International Conference on Learning Representations (ICLR), 2023. Harold Hotelling. Analysis of a complex of statistical variables into principal components. Journal of Educational Psychology, 24(6):417, 1933. Neil Houlsby, Andrei Giurgiu, Stanislaw Jastrzebski, Bruna Morrone, Quentin de Laroussilhe, Andrea Gesmundo, Mona Attariyan, and Sylvain Gelly. Parameter-efficient transfer learning for NLP. In Proceedings of the 36th International Conference on Machine Learning (ICML), pages 2790–2799, 2019. Ya-Ping Hsieh, Yu-Chun Kao, Rabeeh Karimi Mahabadi, Alp Yurtsever, Anastasios Kyrillidis, and Volkan Cevher. A non-euclidean gradient descent framework for non-convex matrix factorization. IEEE Transactions on Signal Processing, 66(22):5917–5926, 2018. 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. In International Conference on Learning Representations, 2022. Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In Advances in Neural Information Processing Systems (NeurIPS), 2018. 10

Prateek Jain, Raghu Meka, and Inderjit Dhillon. Guaranteed rank minimization via singular value projection. In Advances in Neural Information Processing Systems, 2010. Prateek Jain, Praneeth Netrapalli, and Sujay Sanghavi. Low-rank matrix completion using alternating minimization. In Proceedings of the 45th Annual ACM Symposium on Theory of Computing (STOC), pages 665–674, 2013. Junhyung Lyle Kim, George Kollias, Amir Kalev, Ken X Wei, and Anastasios Kyrillidis. Fast quantum state reconstruction via accelerated non-convex programming. Photonics, 10(2):116, 2023. Junsu Kim, Jaeyeon Kim, and Ernest K. Ryu. LoRA training provably converges to a low-rank global minimum or it fails loudly (but it probably won’t fail). In International Conference on Machine Learning (ICML), 2025. Anastasios Kyrillidis and Volkan Cevher. Matrix recipes for hard thresholding methods. Journal of Mathematical Imaging and Vision, 48(2):235–265, 2014. Anastasios Kyrillidis, Amir Kalev, Daniel Park, Srinadh Bhojanapalli, Constantine Caramanis, and Sujay Sanghavi. Provable compressed sensing quantum state tomography via non-convex methods. npj Quantum Information, 4(1):36, 2018. Jaehoon Lee, Lechao Xiao, Samuel S. Schoenholz, Yasaman Bahri, Roman Novak, Jascha SohlDickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. In Advances in Neural Information Processing Systems (NeurIPS), 2019. Shen Li, Yanli Zhao, Rohan Varma, Omkar Salpekar, Pieter Noordhuis, Teng Li, Adam Paszke, Jeff Smith, Brian Vaughan, Pritam Damania, and Soumith Chintala. PyTorch distributed: Experiences on accelerating data parallel training. Proceedings of the VLDB Endowment, 13(12):3005–3018, 2020. Xiang Lisa Li and Percy Liang. Prefix-tuning: Optimizing continuous prompts for generation. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (ACL-IJCNLP), pages 4582–4597, 2021. Vladislav Lialin, Namrata Shivagunde, Sherin Muckatira, and Anna Rumshisky. ReLoRA: High-rank training through low-rank updates. In International Conference on Learning Representations (ICLR), 2024. Fangshuo Liao, Junhyung Lyle Kim, Cruz Barnum, and Anastasios Kyrillidis. On the errorpropagation of inexact Hotelling’s deflation for principal component analysis. In Proceedings of the 41st International Conference on Machine Learning (ICML), pages 29720–29747, 2024. Fangshuo Liao, Wenyi Su, and Anastasios Kyrillidis. Provable model-parallel distributed principal component analysis with parallel deflation. In Proceedings of the Conference on Parsimony and Learning (CPAL), 2025. Shih-Yang Liu, Chien-Yi Wang, Hongxu Yin, Pavlo Molchanov, Yu-Chiang Frank Wang, Kwang-Ting Cheng, and Min-Hung Chen. DoRA: Weight-decomposed low-rank adaptation. In Proceedings of the 41st International Conference on Machine Learning (ICML), 2024. Lester Mackey. Deflation methods for sparse PCA. In Advances in Neural Information Processing Systems, 2008. Sadhika Malladi, Alexander Wettig, Dingli Yu, Danqi Chen, and Sanjeev Arora. A kernel-based view of language model fine-tuning. In International Conference on Machine Learning (ICML), 2023. Leon Mirsky. Symmetric gauge functions and unitarily invariant norms. The Quarterly Journal of Mathematics, 11(1):50–59, 1960. Dohyung Park, Anastasios Kyrillidis, Constantine Carmanis, and Sujay Sanghavi. Non-square matrix sensing without spurious local minima via the burer-monteiro approach. In Artificial intelligence and statistics, pages 65–74. PMLR, 2017. 11

Dohyung Park, Anastasios Kyrillidis, Constantine Caramanis, and Sujay Sanghavi. Finding low-rank solutions via nonconvex matrix factorization, efficiently and provably. SIAM Journal on Imaging Sciences, 11(4):2165–2204, 2018. Qwen Team. Qwen3 technical report. arXiv preprint arXiv:2505.09388, 2025. Samyam Rajbhandari, Jeff Rasley, Olatunji Ruwase, and Yuxiong He. ZeRO: Memory optimizations toward training trillion parameter models. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC), 2020. Pranav Rajpurkar, Jian Zhang, Konstantin Lopyrev, and Percy Liang. SQuAD: 100,000+ questions for machine comprehension of text. In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing (EMNLP), 2016. Pranav Rajpurkar, Robin Jia, and Percy Liang. Know what you don’t know: Unanswerable questions for SQuAD. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (ACL), 2018. Benjamin Recht, Maryam Fazel, and Pablo A. Parrilo. Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM Review, 52(3):471–501, 2010. Alexander Sergeev and Mike Del Balso. Horovod: Fast and easy distributed deep learning in TensorFlow. arXiv preprint arXiv:1802.05799, 2018. Abdul Rafay Shinwari and Muhammad Usama. ARD-LoRA: Dynamic rank allocation for parameterefficient fine-tuning of foundation models with heterogeneous adaptation needs. IEEE Transactions on Artificial Intelligence, 2025. Mohammad Shoeybi, Mostofa Patwary, Raul Puri, Patrick LeGresley, Jared Casper, and Bryan Catanzaro. Megatron-LM: Training multi-billion parameter language models using model parallelism. arXiv preprint arXiv:1909.08053, 2019. Stephen Tu, Ross Boczar, Max Simchowitz, Mahdi Soltanolkotabi, and Benjamin Recht. Low-rank solutions of linear matrix equations via procrustes flow. In Proceedings of the 33rd International Conference on Machine Learning (ICML), pages 964–973, 2016a. Stephen Tu, Ross Boczar, Max Simchowitz, Mahdi Soltanolkotabi, and Benjamin Recht. Low-rank solutions of linear matrix equations via Procrustes flow. In International Conference on Machine Learning, 2016b. Mojtaba Valipour, Mehdi Rezagholizadeh, Ivan Kobyzev, and Ali Ghodsi. DyLoRA: Parameterefficient tuning of pre-trained models using dynamic search-free low-rank adaptation. In Proceedings of the 17th Conference of the European Chapter of the Association for Computational Linguistics (EACL), pages 3274–3287, 2023. Mahtab Alizadeh Vandchali, Fangshuo Liao, and Anastasios Kyrillidis. One rank at a time: Cascading error dynamics in sequential learning. arXiv preprint arXiv:2505.22602, 2025. Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel R. Bowman. GLUE: A multi-task benchmark and analysis platform for natural language understanding. In International Conference on Learning Representations (ICLR), 2019. Per-Åke Wedin. Perturbation bounds in connection with singular value decomposition. BIT Numerical Mathematics, 12(1):99–111, 1972. Hermann Weyl. Das asymptotische verteilungsgesetz der eigenwerte linearer partieller differentialgleichungen. Mathematische Annalen, 71(4):441–479, 1912. Emanuele Zangrando, Sara Venturini, Francesco Rinaldi, and Francesco Tudisco. dEBORA: Efficient bilevel optimization-based low-rank adaptation. In International Conference on Learning Representations (ICLR), 2025. Feiyu Zhang, Liangzhi Li, Junhao Chen, Zhouqiang Jiang, Bowen Wang, and Yiming Qian. IncreLoRA: Incremental parameter allocation method for parameter-efficient fine-tuning. arXiv preprint arXiv:2308.12043, 2023a. 12

Qingru Zhang, Minshuo Chen, Alexander Bukharin, Pengcheng He, Yu Cheng, Weizhu Chen, and Tuo Zhao. AdaLoRA: Adaptive budget allocation for parameter-efficient fine-tuning. In International Conference on Learning Representations, 2023b. Qinqing Zheng and John Lafferty. A convergent gradient descent algorithm for rank minimization and semidefinite programming from random linear measurements. In Advances in Neural Information Processing Systems, 2015.

13

A

Rank-1 Subroutines

We provide pseudocode for two rank-1 subroutines that satisfy Assumption 1. Algorithm 3 Rank1 via Alternating Least Squares Require: Yk ∈ Rm×n , X ∈ Rd×n , iterations T , warm-start (a(0) , b(0) ) 1: M ← XX⊤ ; N ← Yk X⊤ 2: for t = 0, . . . , T −1 do 3: b(t+1) ← Na(t) /(a(t)⊤ Ma(t) ) 4: a(t+1) ← (∥b(t+1) ∥2 M)−1 N⊤ b(t+1) 5: end for 6: return (a(T ) , b(T ) )

Algorithm 4 Rank1 via Factored Gradient Descent Require: Yk , X, T , warm-start (a(0) , b(0) ), learning rates ηa , ηb 1: M ← XX⊤ ; N ← Yk X⊤ 2: for t = 0, . . . , T −1 do 3: ∇a ← Ma(t) ∥b(t) ∥2 − N⊤ b(t) 4: ∇b ← b(t) (a(t)⊤ Ma(t) ) − Na(t) 5: a(t+1) ← a(t) − ηa ∇a ; b(t+1) ← b(t) − ηb ∇b 6: end for 7: return (a(T ) , b(T ) )

B

Background Perturbation Results

Theorem 5 (Weyl’s Inequality [Weyl, 1912]). For M, ∆ ∈ Rm×n , define M̃ = M + ∆. Then |σ̃i − σi | ≤ ∥∆∥2 for all i. Theorem 6 (Wedin’s Theorem [Wedin, 1972]). Let M and M̃ = M + ∆ have top singular triplets (σ1 , u1 , v1 ) and (σ̃1 , ũ1 , ṽ1 ). If δ := min{minj̸=1 |σ1 − σ̃j |, σ1 } > 0, then sin2 ∠(u1 , ũ1 ) + sin2 ∠(v1 , ṽ1 ) ≤ (∥∆⊤ u1 ∥22 + ∥∆v1 ∥22 )/δ 2 .

C

Notation Index Table 7: Summary of notation. Symbol ak,ℓ a⋆k Bk,ℓ bk,ℓ Ck Dk,ℓ Gk,ℓ Fk mk Rk sk ŝk Tk⋆ Ŵ

Type d

R Rd R≥0 Rm R>0 R≥0 R≥0 (0, 1) (0, 1) R>0 N N R>0 –

Defined in

Meaning

Algorithm 1 Section 2 Section 2, (4) Algorithm 1 Lemma 10 Section 2, (3) Section 2, (5) Assumption 1 Theorem 1 Lemma 7 Theorem 1 Lemma 14 Assumption 2 Theorem 1

Worker k’s right factor at round ℓ Ideal right factor for component k ⋆ ⋆⊤ Deflation mismatch b̄k,ℓ ā⊤ k,ℓ X − bk ak X F Worker k’s left factor at round ℓ 3σk⋆ /Tk⋆ + 1 ⊤ Numerical error bk,ℓ a⊤ k,ℓ X − b̄k,ℓ āk,ℓ X F ⊤ ⋆ ⋆⊤ Total error bk,ℓ ak,ℓ X − bk ak X F Subroutine contraction factor Effective convergence rate Magnitude bound on the rank-1 recovery Warm-up round Earliest round at which the Wedin gap activates Singular-value gap max{1, −W−1 (−·)}

14

D

Complete Proofs

Recall the following definitions: ⊤ Dk,ℓ ≜ bk,ℓ a⊤ k,ℓ X − b̄k,ℓ āk,ℓ X F ,

(Numerical error)

(14)

⋆ ⋆⊤ Bk,ℓ ≜ b̄k,ℓ ā⊤ (Deflation mismatch) (15) k,ℓ X − bk ak X F , ⊤ ⋆ ⋆⊤ (Total error) (16) Gk,ℓ ≜ bk,ℓ ak,ℓ X − bk ak X F . where the ideal fit (āk,ℓ , b̄k,ℓ ) is defined in (2); and (a⋆k , b⋆k ) denotes the ideal k-th component of the clean target Yk⋆ .

D.1

Supporting Lemmas

The following lemmas control how these three quantities interact across rounds. [Moved from background.tex per Jasper:] Lemma 7 (Bounded Rank-1 Recovery). Under Assumption 3, the per-component recovery error satisfies Gk,ℓ ≤ Rk := Q + σk⋆ for every round ℓ ≥ 0, (17) and the same bound transfers to Dk,ℓ and Bk,ℓ . Proof. By the projection in Algorithm 1, bk,ℓ a⊤ k,ℓ X

≤ Q, and the ideal k-th component satisfies

F ⋆ b⋆k a⋆⊤ k X F = σk . The triangle inequality gives ⋆ ⋆⊤ Gk,ℓ ≤ bk,ℓ a⊤ k,ℓ X F + bk ak X F

≤ Q + σk⋆ = Rk .

The corresponding ceilings for Dk,ℓ and Bk,ℓ follow by the same triangle-inequality argument using the ideal-fit norm b̄k,ℓ ā⊤ k,ℓ X

= σ1k ,ℓ ≤ ∥Yk,ℓ ∥2 , which is bounded by Q whenever F ⋆ ⋆ ⋆ ∥Yk,ℓ − Yk ∥2 ≤ σ1 (using Q ≥ 2σ1 ); this is the regime in which the proofs invoke these ceilings. Lemma 8 (Numerical Error Recurrence). Under Assumption 1 and Assumption 3, for all ℓ ≥ k if ∥Yk,ℓ − Yk⋆ ∥ ≤ σk⋆ , then we have that Dk,ℓ ≤ Fk (Dk,ℓ−1 + Bk,ℓ + Bk,ℓ−1 ). Proof. Let the output of Line 9 be denoted by ãk,ℓ , b̃k,ℓ . If b̃k,ℓ ã⊤ k,ℓ X

≤ Q, then ãk,ℓ =

ak,ℓ , b̃k,ℓ = bk,ℓ . Therefore, by Assumption 1: ⊤ Dk,ℓ ≤ Fk bk,ℓ−1 a⊤ k,ℓ−1 X − b̄k,ℓ āk,ℓ X F ⋆ ⋆⊤ ⋆ ⋆⊤ ⊤ ≤ Fk ( bk,ℓ−1 a⊤ k,ℓ−1 X − bk ak X F + bk ak X − b̄k,ℓ āk,ℓ X F )

= Fk (Gk,ℓ−1 + Bk,ℓ ) ≤ Fk (Dk,ℓ−1 + Bk,ℓ−1 + Bk,ℓ ). On the other hand, if b̃k,ℓ ã⊤ k,ℓ X ≥ Q, we then notice that ∥Yk,ℓ ∥2 ≤ ∥Yk⋆ ∥2 + ∥Yk,ℓ − Yk⋆ ∥2 ≤ σk⋆ + σ1⋆ ≤ Q Therefore, b̄k,ℓ ā⊤ k,ℓ X

F

≤ Q. By the property of projection onto convex sets, we have that

⊤ ⊤ ⊤ bk,ℓ a⊤ k,ℓ X − b̄k,ℓ āk,ℓ X ≤ b̃k,ℓ ãk,ℓ X − b̄k,ℓ āk,ℓ X

Therefore, by Assumption 1 we have that ⊤ Dk,ℓ ≤ b̃k,ℓ ã⊤ k,ℓ X − b̄k,ℓ āk,ℓ X ⊤ ≤ Fk bk,ℓ−1 a⊤ k,ℓ−1 X − b̄k,ℓ āk,ℓ X F ⋆ ⋆⊤ ⋆ ⋆⊤ ⊤ ≤ Fk ( bk,ℓ−1 a⊤ k,ℓ−1 X − bk ak X F + bk ak X − b̄k,ℓ āk,ℓ X F )

= Fk (Gk,ℓ−1 + Bk,ℓ ) ≤ Fk (Dk,ℓ−1 + Bk,ℓ−1 + Bk,ℓ ).

15

Lemma 9 (Deflated Target Mismatch). For Algorithm 1: ∥Yk,ℓ − Yk⋆ ∥F ≤ P ⋆ ⋆⊤ ⊤ ′ Proof. Yk,ℓ − Yk⋆ = k′ <k (bk′ ak′ − bk ,ℓ−1 ak′ ,ℓ−1 )X. P ⋆ ∥Yk,ℓ − Yk ∥F ≤ k′ <k Gk′ ,ℓ−1 .

Pk−1

k′ =1 Gk′ ,ℓ−1 .

Taking Frobenius norms:

Lemma 10 (Deflation Mismatch Bound). Under Assumption 2, define Ck := 3σk⋆ /Tk⋆ + 1. If ∥Yk,ℓ − Yk⋆ ∥2 < 12 minj>k |σk⋆ − σj⋆ |, then Bk,ℓ ≤ Ck ∥Yk,ℓ − Yk⋆ ∥F . Proof. The deflation mismatch Bk,ℓ measures the gap between the best rank-1 fit of the actual target Yk,ℓ and the ideal k-th component of the clean target Yk⋆ . We bound this gap by decomposing it into a singular-vector error and a singular-value error, then control each via the two perturbation results in Section B: Wedin’s theorem for the singular vectors and Weyl’s inequality for the singular values. Step 1 (Rank-1 SVD expressions). By the Eckart-Young-Mirsky theorem, P ideal sequential deflation removes exactly the first k − 1 singular components of Y, so Yk⋆ = j≥k σj⋆ u⋆j vj⋆⊤ has leading singular triplet (σk⋆ , u⋆k , vk⋆ ) with gap Tk⋆ [Vandchali et al., 2025, Lemma 1]. The hypothesis ∥Yk,ℓ − Yk⋆ ∥2 < 21 Tk⋆ together with Assumption 2 (distinct singular values of Yk⋆ ) ensures that Yk,ℓ has a unique top singular triplet (σ1k ,ℓ , u1k ,ℓ , v1k ,ℓ ), so the ideal fit (2) is well-defined. By definition of the ideal fit and the ideal component, ⊤ b̄k,ℓ ā⊤ k,ℓ X = σ1k ,ℓ u1k ,ℓ v1k ,ℓ ,

⋆ ⋆ ⋆⊤ b⋆k a⋆⊤ k X = σk uk vk .

(18)

Step 2 (Decomposition into singular-vector and singular-value errors). Using (18) and the definition of Bk,ℓ in (4), we add and subtract σk⋆ u1k ,ℓ v1⊤k ,ℓ and apply the triangle inequality: Bk,ℓ = σ1k ,ℓ u1k ,ℓ v1⊤k ,ℓ − σk⋆ u⋆k vk⋆⊤ F = (σ1k ,ℓ − σk⋆ )u1k ,ℓ v1⊤k ,ℓ + σk⋆ (u1k ,ℓ v1⊤k ,ℓ − u⋆k vk⋆⊤ ) F ≤ |σk⋆ − σ1k ,ℓ | +σk⋆ u⋆k vk⋆⊤ − u1k ,ℓ v1⊤k ,ℓ F , | {z } | {z } singular-value error

(19)

singular-vector error

using u1k ,ℓ v1⊤k ,ℓ = 1. The decomposition is natural because the actual and ideal objects in (18) F are each a scalar times a unit-Frobenius rank-1 term, so the discrepancy decomposes cleanly into a scale mismatch and a direction mismatch. Step 3 (Singular-value error via Weyl). By Theorem 5, |σk⋆ − σ1k ,ℓ | ≤ ∥Yk⋆ − Yk,ℓ ∥2 ≤ ∥Yk⋆ − Yk,ℓ ∥F . Step 4 (Singular-vector error via Wedin). Insert ± u⋆k v1⊤k ,ℓ and apply the triangle inequality: √ q (20) u⋆k vk⋆⊤ − u1k ,ℓ v1⊤k ,ℓ F ≤ ∥vk⋆ − v1k ,ℓ ∥2 + ∥u⋆k − u1k ,ℓ ∥2 ≤ 2 sin2 α + sin2 β, √ where α := ∠(u⋆k , u1k ,ℓ ), β := ∠(vk⋆ , v1k ,ℓ ), and we used ∥u − ũ∥2 ≤ 2 sin ∠(u, ũ) for unit vectors. To apply Wedin’s theorem (Theorem 6) we first verify the gap condition: by Weyl’s inequality, |σj (Yk,ℓ ) − σj (Yk⋆ )| ≤ ∥Yk,ℓ − Yk⋆ ∥2 for every j, which combined with the hypothesis ∥Yk,ℓ − Yk⋆ ∥2 < 21 minj>k |σk⋆ − σj⋆ | yields δk := min{minj≥2 |σ1 (Yk,ℓ ) − σj (Yk,ℓ )|, σ1 (Yk,ℓ )} ≥ Tk⋆ /2 > 0. Theorem 6 then gives sin2 α + sin2 β ≤ √ 2 ⋆ ⋆ 2 2 ∥Yk − Yk,ℓ ∥F /(Tk ) . Plugging back into (20) and using 2 2 < 3, √ 2 2 3 ⋆ ⋆⊤ ⊤ uk vk − u1k ,ℓ v1k ,ℓ F ≤ ⋆ ∥Yk⋆ − Yk,ℓ ∥F ≤ ⋆ ∥Yk⋆ − Yk,ℓ ∥F . (21) Tk Tk Step 5 (Combine). Substituting Steps 3 and (21) into (19): Bk,ℓ ≤

3σk⋆ ∥Yk⋆ − Yk,ℓ ∥F + ∥Yk⋆ − Yk,ℓ ∥F = Ck ∥Yk⋆ − Yk,ℓ ∥F , Tk⋆

16

3σ ⋆

Ck := T ⋆k + 1. k

(22)

D.2

Proof of Theorem 1

For the reader’s convenience, we restate the theorem before giving the proof. Theorem 1 (Restated). Under Assumptions 1 to 3, define m1 = F1 and mk = max{Fk , k1 + k−1 k mk−1 } for k ≥ 2, and let s1 = 1 with sk+1 chosen via (32). Then for all k ∈ [r] and all k +1 ℓ ≥ sk − 1, Gk,ℓ ≤ 3Rk (ℓ − sk + 2) mℓ−s . k Proof. We proceed by strong induction on the component index k. We first establish a coupled triple recursion on the numerical error, deflation mismatch, and total error; then construct upper-bounding surrogate sequences that admit closed-form decay; finally, verify the five warm-up conditions on sk that make the surrogates valid. To start, let sk satisfy the property that ∥Yk,ℓ − Yk⋆ ∥F ≤ σ1⋆ . Base case (k = 1). Y1,ℓ = Y for all ℓ, so the first deflation target is exact and B1,ℓ = 0. Then G1,ℓ = D1,ℓ ≤ F1ℓ D1,0 ≤ R1 F1ℓ by Assumption 1 and Lemma 7. Since m1 = F1 and s1 = 1, G1,ℓ ≤ R1 mℓ1 ≤ 3R1 (ℓ + 1)mℓ1 , which satisfies (10). The tighter factor 1 for the base case is loosened to 3 once deflation enters at k ≥ 2, because the surrogate initialization Ĝk,sk −1 = Dk,sk −1 + B̂k,sk −1 + B̂k,sk −2 ≤ 3Rk via Lemma 7. Inductive step: triple recursion. Fix k ≥ 2 and assume (10) holds for every k ′ < k. We collect the three error recursions used below. (i) Numerical error. Lemma 8 gives, for ℓ ≥ sk ,
Dk,ℓ ≤ Fk Dk,ℓ−1 + Bk,ℓ + Bk,ℓ−1 .

(23)

(ii) Deflation mismatch. Combining Lemma 9 with Lemma 10, X Bk,ℓ ≤ Ck ∥Yk,ℓ − Yk⋆ ∥F ≤ Ck Gk′ ,ℓ−1 .

(24)

k′ <k

The key structural observation is that Bk,ℓ depends only on the earlier components’ total errors Gk′ ,ℓ−1 with k ′ < k: predecessor convergence automatically forces Bk,ℓ → 0. (iii) Total error. Unrolling (23) from round sk − 1 up to round ℓ and using Gk,ℓ ≤ Dk,ℓ + Bk,ℓ , Gk,ℓ ≤ Fkℓ−sk +1 Dk,sk −1 +

ℓ−1 X

′ Fkℓ−ℓ Bk,ℓ′ + Bk,ℓ′ −1 + Bk,ℓ .

(25)

ℓ′ =sk −1

The three recursions (23)–(25) are the natural triple-recursion structure for parallel deflation, with the mismatch bound supplied by our Wedin-based Lemma 10. Surrogate sequences. Because the right-hand sides of (24)–(25) are coupled through {Gk′ ,· }k′ <k , we replace the actual sequences with explicit upper-bounding surrogates. Let ŝk denote the earliest round at which the Wedin gap condition in Lemma 10 holds; ŝk ≤ sk . Following Lemma 14, define the surrogate mismatch and surrogate total error piecewise:  Rk if ℓ < ŝk ,  B̂k,ℓ = (26) k min Rk , mℓ−ŝ (ℓ − ŝ + 1) B̂ if ℓ ≥ ŝk , k k,ŝk k−1 P with boundary value B̂k,ŝk := Ck k′ <k Ĝk′ ,ŝk −1 , and ( Ĝk,sk −1 if ℓ < sk , Ĝk,ℓ = (27) k +1 mℓ−s (ℓ − s + 2) Ĝ k k,sk −1 if ℓ ≥ sk , k with initialization Ĝk,sk −1 = Dk,sk −1 + B̂k,sk −1 + B̂k,sk −2 . Note Ĝk,sk −1 ≤ 3Rk by Lemma 7 and the B̂k,· ≤ Rk ceiling in (26). By Lemma 14, applying the surrogate domination directly, k +1 k +1 Gk,ℓ ≤ Ĝk,ℓ ≤ mℓ−s (ℓ − sk + 2) Ĝk,sk −1 ≤ 3Rk (ℓ − sk + 2) mℓ−s k k

It remains to exhibit the conditions on sk+1 under which Lemma 14 applies. 17

for all ℓ ≥ sk .

Conditions arising in the proof of Lemma 14. The proof of Lemma 14 (given below) requires five inequalities; we collect them here so that the present theorem can secure them via the choice of sk+1 . For each condition we identify the proof step at which it is invoked. (C1) Predecessor envelope folding (per-predecessor form). For every k ′ ≤ k, ŝ

mkk+1 ′

−sk′

(ŝk+1 − sk′ + 1) ≤ k1 .

Origin: used in the bound on Bk+1,ℓ in Lemma 14 (case ℓ ≥ ŝk+1 ) to fold the polynomial factor (ŝk+1 −sk′ +1) inherited from each predecessor surrogate Ĝk′ ,· into the target geometric envelope and then average the resulting sum of k terms back to a single B̂k+1,ŝk+1 value. The per-predecessor form (with mk′ rather than the global mk ) is no looser than the corresponding global statement, since mk ≥ mk′ for k ′ ≤ k (proved below). ⋆ ⋆ (C2) Wedin-gap activation: Yk+1,ℓ − Yk+1 < 12 Tk+1 for all ℓ ≥ ŝk+1 , equivalently ŝk+1 ≥ 2 P gap gap ⋆ /(2Ck+1 ). Origin: sk+1 where sk+1 is the smallest round such that k′ ≤k Gk′ ,ℓ−1 ≤ Tk+1 the hypothesis of Lemma 10; without it, Bk+1,ℓ has no usable upper bound. 1 k (C3) Coupling compatibility: γk := k+1 + k+1 mk ≤ mk+1 . Origin: structural; required when invoking Lemma 13 to re-anchor B̂k+1,· to a pure-geometric envelope at rate γk and then absorb that rate into mk+1 . This holds automatically because mk+1 = max{Fk+1 , γk } by (8). (C4) Contraction compatibility: Fk+1 ≤ mk+1 . Origin: used to absorb the factor Fk+1 from Lemma 8 into the target rate mk+1 when bounding Dk+1,ℓ . This holds automatically because mk+1 = max{Fk+1 , γk } by (8). (C5) Re-anchor warm-up offset: the offset between the Wedin-activation index ŝk+1 and the warm-up index sk+1 satisfies both (k + 1)mk s −ŝ −2 and mkk+1 k+1 (sk+1 − ŝk+1 − 1) ≤ 1. (28) 1 − mk Origin: the two warm-up requirements of Lemma 13 (with the second instance s = sk+1 − 2 ℓ−ŝ giving the tightest case): together they convert the linear-times-geometric form mk k+1 (ℓ − ℓ−sk+1 +1 ŝk+1 + 1)B̂k+1,ŝk+1 into the pure-geometric form γk B̂k+1,sk+1 −1 used to majorize the forcing sum in the unrolled D-recurrence at rate mk+1 without incurring an additional polynomial factor. sk+1 − ŝk+1 − 2 ≥

Conditions (C3) and (C4) are automatic structural facts (no constraint on sk+1 ); (C1), (C2), and (C5) translate, via Lemma 12(ii) (for the first two) or directly (28) (for the third), into explicit per-predecessor lower bounds on sk+1 . Before proceeding, record once that mk is non-decreasing in k: by (8), k1 + k−1 k mk−1 is a convex combination of 1 and mk−1 , hence ≥ mk−1 , so mk = max{Fk , γk−1 } ≥ mk−1 . Deriving (32) from (C1) and (C2). We compute the per-predecessor lower bound on sk+1 that simultaneously secures the two non-trivial conditions. ŝ

−s

k′ From (C1). For each k ′ ≤ k, we seek the smallest ŝk+1 such that mkk+1 (ŝk+1 − sk′ + 1) ≤ ′ x 1/k. Applying Lemma 12(ii) to g(x) = mk′ (x + 1) with x = ŝk+1 − sk′ and ϵ = 1/k yields mk ′ ) − 1. Using the wrapper Ŵ (a) := max{1, −W−1 (−a)}, the ŝk+1 − sk′ ≥ log 1m ′ W−1 ( mk′ log k k

trailing −1 is absorbed (since Ŵ (a) ≥ 1 for a ∈ (0, 1/e) and the wrapper bounds −W−1 (−a) − 1 ≤ Ŵ (a) − 1 + 1 = Ŵ (a) once we pass to the inverse-sign convention ϵ 7→ −ϵm log m):   mk ′ | Ŵ mk′ | log k ŝk+1 − sk′ ≥ , ∀k ′ ≤ k. (29) log(1/mk′ ) ℓ−s

From (C2). By Lemma 9 and the inductive hypothesis Gk′ ,ℓ−1 ≤ 3Rk′ (ℓ − sk′ + 1)mk′ k′ , X X ℓ−s ⋆ ≤ Gk′ ,ℓ−1 ≤ 3 Rk′ (ℓ − sk′ + 1)mk′ k′ . Yk+1,ℓ − Yk+1 F k′ ≤k

(30)

k′ ≤k

⋆ A sufficient condition for the Wedin gap is that each summand is at most Tk+1 /(6kCk+1 ), i.e., ℓ−s

T⋆

for each k ′ ≤ k, (ℓ − sk′ + 1)mk′ k′ ≤ 6kR k+1 (the constant 6 = 3 × 2 comes from Ĝk′ ,· ≤ ′ Ck+1 k

18

3Rk′ ·m·k′ (·+1) post-warm-up and the factor-of-two slack in Lemma 10’s gap hypothesis). Applying T⋆

Lemma 12(ii) with ϵk′ := 6kR k+1 and the same Ŵ -absorption, ′ Ck+1 k

ℓ − sk ′ ≥

Ŵ (ϵk′ mk′ | log mk′ |) , log(1/mk′ )

∀k ′ ≤ k.

(31)

From (C5). The first inequality in (28) is an offset between sk+1 and ŝk+1 that does not depend on k ′ ; s −ŝ −2 it contributes the additive term (k+1)mk /(1−mk )+2. The second inequality mkk+1 k+1 (sk+1 − ŝk+1 − 1) ≤ 1 is a Lambert-W condition of the same form as (29) (applied to g(x) = mxk (x + 1) with ϵ = 1), so it contributes an additional offset Ŵ (mk | log mk |)/ log(1/mk ) between ŝk+1 and sk+1 − 2. Combining. The bounds (29) and (31) are per-predecessor lower bounds on the gap from anchor sk′ , while (28) adds a uniform offset between ŝk+1 and sk+1 , so a sufficient choice of sk+1 is   ⋆   ( Tk+1 mk′ | log mk′ | ) mk′ | Ŵ Ŵ mk′ | log k 6kRk′ Ck+1 + sk+1 ≥ max sk′ + k′ ≤k log(1/mk′ ) log(1/mk′ ) {z } {z } | | from (C1), (29) from (C2), (31) (32)
Ŵ mk | log mk | (k + 1)mk + . +2 + 1 − mk log(1/mk ) {z } | from (C5), (28)

By Lemma 12 the wrapper Ŵ (·) is well-defined and Ŵ (a) = O(max{1, log(1/a)}), and the re-anchor offset is bounded for any fixed mk < 1, so (32) produces a finite, polynomial-in-log-and1/(1 − mk ) requirement. Simplified bound on sk+1 . The three nested Ŵ terms in (32) can be folded into a single logarithmic expression by applying the standard Lambert-W upper bound (sharpening the asymptotic of Lemma 12) Ŵ (a) ≤ log(1/a) + log log(1/a) + 1 for a ∈ (0, 1/e), (33) together with the elementary bound log(1/m) ≥ 1 − m for m ∈ (0, 1) (so that 1/ log(1/mk′ ) ≤ 1/(1 − mk′ )). For each predecessor k ′ ≤ k, applying (33) to a = mk′ | log mk′ |/k gives

mk ′ |
k k Ŵ mk′ | log ≤ log m ′ | log k m ′ | + log log m ′ | log m ′ | + 1, and the same expansion applied k

k

k

k

⋆ to the (C2)-term Ŵ replaces k by 6kCk+1 Rk′ /Tk+1 . Absorbing the log log and +1 remainders into e a generic O(·) symbol, (32) simplifies to:

Corollary 11 (Simplified warm-up bound). There exist absolute constants C1 , C2 , C3 > 0 such that the per-predecessor lower bound (32) on sk+1 is implied by ( )
⋆ C1 log k Ck+1 Rk′ /Tk+1 + C2 (k + 1)mk C3 sk+1 ≥ max sk′ + + + . (34) k′ ≤k 1 − mk ′ 1 − mk 1 − mk e Equivalently, in O-form (suppressing constants and log log factors),
! ⋆ log k Ck+1 Rk′ /Tk+1 (k + 1)mk e sk+1 = max sk′ + O + . k′ ≤k 1 − mk 1 − mk

(35)

Proof. Each Ŵ term in (32) is bounded via (33). The denominator log(1/mk′ ) is replaced by its lower bound 1 − mk′ , which is uniformly bounded above by 1 − mk since mk′ ≤ mk (Equation (8)). The two Ŵ contributions inside the max each yield a log(k/(mk′ | log mk′ |)) piece ⋆ and a log(Ck+1 Rk′ /Tk+1 ) piece (the latter only from the (C2)-term); both are absorbed into ⋆ C1 log(k Ck+1 Rk′ /Tk+1 ). The remaining log log and +1 terms are bounded by a constant C2 , while the third (re-anchor) Ŵ contributes a constant C3 once 1/ log(1/mk ) ≤ 1/(1 − mk ) is applied. Combining yields (34); (35) is the same statement with constants and log log factors hidden. 19

The simplified form (34) is the version referenced in the main-text statement of Theorem 1; it makes explicit the three drivers of the warm-up cost: the predecessor-anchor offset sk′ , a logarithmic ⋆ dependence on the spectral-gap-to-magnitude ratio Ck+1 Rk′ /Tk+1 , and the geometric 1/(1 − mk ) slowdown as the effective rate approaches one. Conclusion. With sk+1 chosen per (32), conditions (C1), (C2), and (C5) are secured; (C3) and (C4) are automatic from (8). Lemma 14 then yields Gk,ℓ ≤ Ĝk,ℓ for all ℓ ≥ sk − 1, and substituting (27) together with Ĝk,sk −1 ≤ 3Rk gives k +1 k +1 Gk,ℓ ≤ mℓ−s (ℓ − sk + 2) Ĝk,sk −1 ≤ 3Rk (ℓ − sk + 2) mℓ−s , k k

which is the bound (10). This the proof. D.3

Auxiliary Lemmas

Lemma 12 (Lambert-W Bound). Let m ∈ (0, 1) and g(x) = mx (x + 1). (i) If ϵ ≥ −(em log m)−1 , then g(x) ≤ ϵ for all x ≥ 0. (ii) If ϵ < −(em log m)−1 , then g(x) ≤ ϵ whenever x ≥ log1 m W−1 (ϵm log m) − 1. Moreover, the wrapper Ŵ (a) := max{1, −W−1 (−a)} satisfies Ŵ (a) = O(max{1, log(1/a)}), and admits the explicit upper bound Ŵ (a) ≤ log(1/a) + log log(1/a) + 1 for a ∈ (0, 1/e).
Proof. Differentiating g(x) = mx (x + 1) gives g ′ (x) = mx 1 + (x + 1) log m , so g attains its maximum at x⋆ = (log(1/m))−1 − 1 with value g(x⋆ ) = −(em log m)−1 . Case (i). If ϵ ≥ g(x⋆ ), then g(x) ≤ g(x⋆ ) ≤ ϵ for every x ≥ 0, and any non-negative x satisfies the bound. Case (ii). Suppose ϵ < g(x⋆ ). On (x⋆ , ∞), g is strictly decreasing, so the equation g(x) = ϵ has a unique solution xϵ > x⋆ . Taking logarithms and substituting y = (x + 1) log m transforms g(x) = ϵ into yey = ϵm log m, which is solved by y = W−1 (ϵm log m) on the decreasing branch (since ϵm log m ∈ (−1/e, 0)). Hence xϵ = log1 m W−1 (ϵm log m) − 1, and every x ≥ xϵ satisfies g(x) ≤ ϵ. Asymptotic statement. By the standard expansion −W−1 (−a) = log(1/a) + log log(1/a) + o(1) as a → 0+ , we get Ŵ (a) = O(max{1, log(1/a)}). The explicit non-asymptotic bound Ŵ (a) ≤ log(1/a) + log log(1/a) + 1 for a ∈ (0, 1/e) follows from the standard Lambert-W inequality −W−1 (−e−u−1 ) ≤ u + log u + 1 for u ≥ 1 (substitute u = log(1/a) − 1). Lemma 13 (Geometric Re-anchoring of B̂). Fix k ≥ 1. Suppose the surrogate sequence B̂k+1,ℓ is given by (38) with B̂k+1,ŝk+1 ≤ Rk+1 and rate mk ∈ (0, 1). If an integer s satisfies s ≥ ŝk+1 , s−ŝ mk k+1 (s − ŝk+1 + 1) ≤ 1, and s − ŝk+1 ≥

(k + 1)mk , 1 − mk

(36)

then for every ℓ ≥ s, B̂k+1,ℓ ≤ γkℓ−s B̂k+1,s ,

k 1 γk = k+1 + k+1 mk .

(37)

s−ŝ

Proof. At index s, the conditions B̂k+1,ŝk+1 ≤ Rk+1 and mk k+1 (s − ŝk+1 + 1) ≤ 1 together s−ŝ imply mk k+1 (s − ŝk+1 + 1)B̂k+1,ŝk+1 ≤ Rk+1 , so the min{·, Rk+1 } ceiling is inactive at s and s−ŝk+1

B̂k+1,s = mk

(s−ŝk+1 +1)B̂k+1,ŝk+1 ,

 s−ŝ −1 so B̂k+1,ŝk+1 = mk k+1 (s−ŝk+1 +1) B̂k+1,s . 20

For any ℓ ≥ s, the post-warm-up clause of (38) gives ℓ−ŝk+1

B̂k+1,ℓ ≤ mk

(ℓ − ŝk+1 + 1)B̂k+1,ŝk+1 ℓ − ŝk+1 + 1 B̂k+1,s = mℓ−s · k s − ŝk+1 + 1

= mℓ−s B̂k+1,s k

ℓ−s  ℓ Y ℓ′ − ŝk+1 + 1 ℓ−s s − ŝk+1 + 1 ≤ m B̂k+1,s , k ℓ′ − ŝk+1 s − ŝk+1 ′

ℓ =s+1

where the last inequality bounds each of the ℓ − s factors by its largest value at ℓ′ = s + 1 (the ratio (ℓ′ − ŝk+1 + 1)/(ℓ′ − ŝk+1 ) is decreasing in ℓ′ ). The warm-up condition (36), equivalent to s−ŝk+1 +1 (k+1)mk +1−mk kmk +1 1 = (k+1)m , then yields s−ŝk+1 ≤ 1 + (k+1)mk /(1−mk ) = (k+1)mk k s − ŝk+1 + 1 kmk + 1 1 k ≤ = k+1 + k+1 mk = γk , s − ŝk+1 k+1 which combined with the displayed bound gives (37). mk ·

Lemma 14 (Surrogate Sequence Domination). Under Assumptions 1 to 3, let ŝk denote the earliest round at which the Wedin gap condition of Lemma 10 holds for component k, and let sk be the warm-up round chosen via (32). The choice (32) ensures ŝk ≤ sk for every k ≥ 2 via the additive offset (k + 1)mk /(1 − mk ) + 2 + Ŵ (mk | log mk |)/ log(1/mk ) contributed by (C5); for indices j < ŝk we adopt the convention B̂k,j := Rk . Define the surrogate sequences piecewise:  Rk if ℓ < ŝk ,  (38) B̂k,ℓ = k min Rk , mℓ−ŝ (ℓ − ŝ + 1) B̂ if ℓ ≥ ŝk , k k,ŝ k k−1 ( Ĝk,sk −1 if ℓ < sk , Ĝk,ℓ = (39) mkℓ−sk +1 (ℓ − sk + 2) Ĝk,sk −1 if ℓ ≥ sk , P with boundary values B̂k,ŝk := Ck k′ <k Ĝk′ ,ŝk −1 and Ĝk,sk −1 := Dk,sk −1 + B̂k,sk −1 + B̂k,sk −2 . If sk+1 is chosen via (32), then B̂k,ℓ ≥ Bk,ℓ for every k ∈ [r] and every ℓ ≥ 0, and Ĝk,ℓ ≥ Gk,ℓ for every ℓ ≥ sk − 1. Proof. We proceed by strong induction on k. At each inequality below we identify which of the conditions (C1)–(C4) (collected in the proof of Theorem 1) is being invoked. Base case (k = 1). Since Y1,ℓ = Y, the first target is exact, so B1,ℓ = 0 by (4); combined with B1,ℓ ≤ R1 from Lemma 7, the surrogate B̂1,ℓ = R1 dominates trivially. For the total error, 1 +1 Lemma 8 unrolls to G1,ℓ = D1,ℓ ≤ F1ℓ−s1 +1 D1,s1 −1 , which is upper-bounded by mℓ−s (ℓ − s1 + 1 2)Ĝ1,s1 −1 = Ĝ1,ℓ since m1 = F1 and (ℓ − s1 + 2) ≥ 1. Inductive step. Fix k ≥ 1 and assume the inductive hypothesis: for every k ′ ≤ k, B̂k′ ,ℓ ≥ Bk′ ,ℓ for every ℓ ≥ 0 and Ĝk′ ,ℓ ≥ Gk′ ,ℓ for every ℓ ≥ sk′ − 1. We show B̂k+1,ℓ ≥ Bk+1,ℓ for every ℓ ≥ 0, and then Ĝk+1,ℓ ≥ Gk+1,ℓ for every ℓ ≥ sk+1 − 1. We bound Bk+1,ℓ first. If ℓ < ŝk+1 , then by Lemma 7, Bk+1,ℓ ≤ Rk+1 = B̂k+1,ℓ . If ℓ ≥ ŝk+1 , then the Wedin-gap hypothesis of Lemma 10 is active by condition (C2), and by definition of ŝk+1 , ŝk+1 − 1 ≥ sk′ for every k ′ ≤ k, so each predecessor surrogate lies on the post-warm-up branch of (39). Combining Lemma 9 and Lemma 10 with the inductive hypothesis Gk′ ,ℓ−1 ≤ Ĝk′ ,ℓ−1 , X Bk+1,ℓ ≤ Ck+1 Ĝk′ ,ℓ−1 k′ ≤k

= Ck+1

X

ℓ−s

mk′ k′ (ℓ − sk′ + 1) Ĝk′ ,sk′ −1

k′ ≤k

≤ Ck+1

X

ℓ−ŝ

ŝ

mk′ k+1 mkk+1 ′

−sk′

(ℓ − ŝk+1 + 1)(ŝk+1 − sk′ + 1) Ĝk′ ,sk′ −1

k′ ≤k ℓ−ŝk+1

≤ Ck+1 mk

(ℓ − ŝk+1 + 1) · k1

X k′ ≤k

21

Ĝk′ ,sk′ −1 ,

where the third inequality applies a + b − 1 ≤ ab for a, b ≥ 1 (with a = ℓ − ŝk+1 + 1 and b = ŝk+1 − sk′ + 1) to split the polynomial factor along ŝk+1 , and the fourth uses condition (C1) ŝ −sk′ (mkk+1 (ŝk+1 − sk′ + 1) ≤ 1/k) together with the monotonicity mk′ ≤ mk for k ′ ≤ k ′ ŝ −sk′ (from (8)). By (C1) again, Ĝk′ ,ŝk+1 −1 = mkk+1 (ŝk+1 − sk′ + 1)Ĝk′ ,sk′ −1 ≤ (1/k)Ĝk′ ,sk′ −1 , ′ P P so B̂k+1,ŝk+1 := Ck+1 k′ ≤k Ĝk′ ,ŝk+1 −1 ≤ (Ck+1 /k) k′ ≤k Ĝk′ ,sk′ −1 , and combining with Bk+1,ℓ ≤ Rk+1 from Lemma 7,  ℓ−ŝ Bk+1,ℓ ≤ min Rk+1 , mk k+1 (ℓ − ŝk+1 + 1) B̂k+1,ŝk+1 = B̂k+1,ℓ , (40) which is the post-warm-up branch of (38). The min-ceiling enforces B̂k+1,ŝk+1 ≤ Rk+1 , which we use when invoking Lemma 13. This establishes B̂k+1,ℓ ≥ Bk+1,ℓ for every ℓ ≥ 0. We now bound Gk+1,ℓ , starting with ℓ ≥ sk+1 . Iterating Lemma 8 from round sk+1 − 1 up to round ℓ and using (40), Dk+1,ℓ ≤

ℓ X

ℓ−s +1 Fk+1k+1 Dk+1,sk+1 −1 +

ℓ−ℓ′ Fk+1 B̂k+1,ℓ′ + B̂k+1,ℓ′ −1 ,

(41)

ℓ′ =sk+1 −1

where we re-indexed the sum to start at sk+1 − 1 (the dropped earlier summand Bk+1,sk+1 −2 is non-negative). To collapse this sum into a clean envelope at rate mk+1 , we re-anchor B̂k+1,· from ŝk+1 to sk+1 − 1 via Lemma 13. Apply that lemma twice, at s = sk+1 − 1 and at s = sk+1 − 2: ℓ′ −(sk+1 −1)

B̂k+1,ℓ′ ≤ γk B̂k+1,ℓ′ −1 ≤

B̂k+1,sk+1 −1 ,

′

ℓ −(sk+1 −1) γk B̂k+1,sk+1 −2 ,

∀ ℓ′ ≥ sk+1 − 1,

(42)

′

∀ ℓ ≥ sk+1 − 1,

(43)

where the second display has matching exponent (ℓ′ − 1) − (sk+1 − 2) = ℓ′ − sk+1 + 1. The two s −ŝ −2 preconditions of Lemma 13 at s = sk+1 − 2, namely mkk+1 k+1 (sk+1 − ŝk+1 − 1) ≤ 1 and sk+1 − ŝk+1 − 2 ≥ (k + 1)mk /(1 − mk ), are exactly the two clauses of (C5) secured by (32); at s = sk+1 − 1 the offset is one larger and so no looser, and g(x) = mxk (x + 1) is decreasing past its peak at x = 1/ log(1/mk ) − 1, which lies below (C5)’s offset (using 1/ log(1/mk ) ≤ 1/(1 − mk )). Substituting (42) and (43) into (41), ℓ−s

Dk+1,ℓ ≤ mk+1k+1

+1

Dk+1,sk+1 −1 +

ℓ X

′

ℓ′ −sk+1 +1

mℓ−ℓ k+1 γk

B̂k+1,sk+1 −1 + B̂k+1,sk+1 −2

ℓ′ =sk+1 −1

ℓ−s +1 ℓ−s +1 ≤ mk+1k+1 Dk+1,sk+1 −1 + mk+1k+1 (ℓ − sk+1 + 2) B̂k+1,sk+1 −1 + B̂k+1,sk+1 −2
ℓ−s +1 ≤ mk+1k+1 (ℓ − sk+1 + 2) Dk+1,sk+1 −1 + B̂k+1,sk+1 −1 + B̂k+1,sk+1 −2 , where the first inequality uses (C4) (Fk+1 ≤ mk+1 ), and the second bounds the inner sum by ℓ−s +1 (ℓ − sk+1 + 2) copies of mk+1k+1 via (C3) (γk ≤ mk+1 ) over ℓ − sk+1 + 2 consecutive indices. By ℓ−s

(40), (42), and γk ≤ mk+1 , we also have Bk+1,ℓ ≤ B̂k+1,ℓ ≤ mk+1k+1 Combining via Gk+1,ℓ ≤ Dk+1,ℓ + Bk+1,ℓ ,

+1

(ℓ−sk+1 +2) B̂k+1,sk+1 −1 .

ℓ−s

+1

(ℓ − sk+1 + 2) Dk+1,sk+1 −1 + B̂k+1,sk+1 −1 + B̂k+1,sk+1 −2

ℓ−s

+1

(ℓ − sk+1 + 2) Ĝk+1,sk+1 −1 = Ĝk+1,ℓ .

Gk+1,ℓ ≤ mk+1k+1 = mk+1k+1

For the boundary case ℓ = sk+1 − 1, the surrogate is held constant: Ĝk+1,sk+1 −1 = Dk+1,sk+1 −1 + B̂k+1,sk+1 −1 + B̂k+1,sk+1 −2 , so by the just-established B̂k+1,j ≥ Bk+1,j and B̂k+1,sk+1 −2 ≥ 0, Ĝk+1,sk+1 −1 ≥ Dk+1,sk+1 −1 + Bk+1,sk+1 −1 ≥ Gk+1,sk+1 −1 , where the last step is Gk+1,· ≤ Dk+1,· + Bk+1,· . The size bound Ĝk+1,sk+1 −1 ≤ 3Rk+1 used in (10) follows from Lemma 7 applied to each of the three summands (Dk+1,sk+1 −1 ≤ Rk+1 and B̂k+1,j ≤ Rk+1 by the min-ceiling in (38)). This completes the inductive step. 22

D.4

Proof of Proposition 2

P Proof. By Lemma 9: ∥Yk,ℓ − Yk⋆ ∥F ≤ k′ <k Gk′ ,ℓ−1 . Substituting Theorem 1: each term is ℓ−s 3Rk′ (ℓ − sk′ + 1) mk′ k′ → 0 since mk′ < 1. D.5

Proof of Theorem 3

Proof. Since σmin (X) > 0, for any W we have ∥W∥F ≤ σmin (X)−1 ∥WX∥F . Applying this P P ⋆ ⊤ with W = W⋆ − k bk,L a⊤ ≤ k,L and using the triangle inequality: W X − k bk,L ak,L X F ⋆ Pr Pr Pr Pr ⋆ ⋆⊤ ⋆ ⋆⊤ ⊤ ⋆ Y − k=1 bk ak X F + k=1 bk ak X − bk,L ak,L X = k=r+1 σk + k=1 Gk,L , where F the first equalityPuses Eckart-Young-Mirsky: the best rank-r approximation of Y in Frobenius norm leaves residual k>r σk⋆ . Dividing by σmin (X) yields the stated bound. D.6

Proof of Theorem 4

Proof. Decompose into T1 (truncation, bounded by Eckart-Young-Mirsky), T2 (noise perturbation, bounded by Weyl/Wedin and PGaussian concentration following [Vandchali et al., 2025, Lemma C.1]), and T3 (algorithmic error k Gk,L ). The algorithmic term inherits self-correction; the statistical term matches the sequential baseline. Dividing by σmin (X) yields the stated bound. The key observation is that parallelization does not affect the noise term T2 . The noise E enters through the data model Y = W⋆ X + E, which is identical for both sequential and parallel algorithms. The ⋆ T2 bound depends only on the spectral perturbation √ √ ∥Y − W X∥2 = ∥E∥2 , controlled by standard Gaussian concentration (e.g., ∥E∥2 ≤ ε( m + n) with high probability). This perturbation is a property of the data, not the algorithm, so the parallel and P sequential statistical terms are the same. The only difference is in T3 : for the parallel algorithm, k Gk,L → 0 by Theorem 1, while for the sequential baseline, the corresponding sum involves permanently fixed numerical errors. D.7

Verification that mk < 1

We show by induction on k that the effective rate mk defined in (8) satisfies mk ∈ (0, 1) for every k ∈ [r]. Base case (k = 1). By definition, m1 = F1 , and Assumption 1 requires Fk ∈ (0, 1) for every k. Hence m1 ∈ (0, 1). Inductive step (k ≥ 2). Assume mk−1 ∈ (0, 1). The auxiliary quantity γk−1 = k1 + k−1 k mk−1 is a convex combination of 1 and mk−1 , so γk−1 ∈ (mk−1 , 1) ⊂ (0, 1) whenever mk−1 < 1. By Assumption 1, Fk ∈ (0, 1). Therefore mk = max{Fk , γk−1 } ∈ (0, 1), completing the induction.

E

Game-Theoretic Interpretation

Proposition 15 (Nash equilibrium). 2, define player k’s utility as Vk (a, b | P Under Assumption ⊤ 2 ⋆ ⋆ r {(ak′ , bk′ )}k′ <k ) = − 12 ∥Y − k′ <k bk′ a⊤ X − ba X∥ ′ F . Then {(ak , bk )}k=1 is the unique k strict Nash equilibrium up to sign. Proof. By induction: given optimal predecessors, player k maximizes utility by finding the best rank-1 approximation of Yk⋆ , which is unique under the strict spectral gap (Assumption 2).

F

Theory-Validation Experiments

We evaluate the predictions of Theorems 1 and 4 and Proposition 2 on the bilinear regression model Y = W⋆ X + E from (1). The synthetic instances use a ground-truth weight W⋆ ∈ Rm×d of rank r⋆ , an input matrix X ∈ Rd×n with i.i.d. standard Gaussian entries, and Gaussian noise Eij ∼ N (0, ε2 ) entrywise, with ε = 0 in the noiseless experiments. Three singular-value profiles for W⋆ are ⋆ considered, each normalised so that σ1⋆ = 1: exponential σk⋆ = 2r −k (geometric decay, large gaps), power-law σk⋆ = k −1.5 (algebraic decay), and uniform σk⋆ = 1 for all k (no spectral gap, 23

Parallel (ALS)

Parallel (GD)

Sequential (ALS)

Sequential (GD)

10 1

10 1

10 2

10 2

10 4

RelErr(W)

10 1 101

102

103

104

101

102 103 Total Work

104

101

102

Joint GD

103

104

Figure 2: Convergence under equal total work. Relative weight error vs. total work for exponential, power-law, and uniform spectra. Parallel ALS matches sequential on the well-separated exponential spectrum and degrades gracefully as spectral gaps shrink. so Assumption 2 is degenerate). Each setting is repeated over five random seeds; figures plot the per-round median across seeds with shaded bands giving the seed-to-seed minimum-to-maximum envelope. F.1

Synthetic Validation

We first verify the qualitative predictions of Theorems 1 and 4 and Proposition 2: the per-round convergence of total reconstruction error, the self-correction of deflation targets, and the matching of the parallel and sequential noise floors. For the convergence comparison of Figure 2 we set m = 100, d = 200, n = 500, r⋆ = 10, and run each method with T = 10 inner iterations per round and L = 10 communication rounds across the three spectral profiles. Parallel ALS matches sequential ALS on the exponential spectrum, with both reaching a relative weight error of about 2.1 × 10−3 . On the power-law spectrum parallel reaches 3.6 × 10−3 against 2.1 × 10−3 for sequential, so the two stay within a small constant factor; on the uniform spectrum both methods degrade together because the spectral gap vanishes, consistent with Assumption 2. For reference we also include two factored gradient-descent variants (parallel and sequential, using the rank-1 solver of Section A in place of ALS) and a joint gradient-descent baseline that updates all r⋆ rank-1 factor pairs simultaneously without deflation. To isolate self-correction (Figure 3) we shrink the problem to m = 50, d = 80, n = 200, r⋆ = 5 on the exponential spectrum, with T = 10 and L = 30, so that workers k = 2, . . . , 5 activate round by round under the staggered schedule sk = k of Theorem 1. The left panel shows the normalised deflation mismatch ∥Yk,ℓ − Yk⋆ ∥F / ∥Yk⋆ ∥F for each worker, where Yk,ℓ is the worker’s current P target and Yk⋆ = Y − k′ <k b⋆k′ a⋆⊤ k′ X is the clean target built from the ideal rank-1 components (a⋆k′ , b⋆k′ ) of Section 2. The mismatch decreases by roughly 5× for workers 2 to 4 between activation and convergence. The right panel decomposes the error of worker 3 into the three quantities G3,ℓ , D3,ℓ , and B3,ℓ defined in (3), (4), and (5). Both D3,ℓ and B3,ℓ decay to a small common floor, exactly the behaviour predicted by Proposition 2. The noise-robustness experiment of Figure 4 keeps the same problem dimensions and exponential profile, sets T = 10 and L = 15, and adds entrywise Gaussian noise Eij ∼ N (0, ε2 ) at ε ∈ {0.01, 0.1, 0.5, 1.0}. Across all four noise levels parallel and sequential deflation converge to the same noise floor, and the per-seed final-round parallel-to-sequential ratio stays within [1.000, 1.014] across all four noise settings, so parallelization incurs no statistical penalty relative to sequential deflation, as predicted by Theorem 4. The reference floor in each panel is the theoretical scale p ε r⋆ d/n from the same theorem. F.2

Theoretical-Bound Validation

This experiment tests the quantitative form of Theorem 1: each worker’s total error Gk,ℓ (defined in (5)) decays geometrically once the warm-up round sk from Theorem 1 is reached, and the empirical per-worker contraction rate matches the recurrence (8) for mk . We fix m = 50, d = 80, n = 200, r⋆ = 5 on the exponential spectrum and run Algorithm 1 with T = 10 ALS iterations per round and L = 40 communication rounds. For every seed and every worker k we record the empirical bk m trajectory Gk,ℓ and fit Gk,ℓ ≈ C b kℓ by least-squares regression on log Gk,ℓ , restricted to rounds at 24

Worker 4 Worker 5

G3, D3, B3,

10 5 G3, , D3, , B3,

Worker 2 Worker 3

Mismatchk,

10 5

10 6

10 6 10 20 Communication round

30

10 20 Communication round

30

Figure 3: Self-correction. Left: normalized deflation mismatch per worker, decreasing over rounds. Right: error decomposition for worker 3 (G, D, B all decay).

Parallel

RecErr(W)

101

noise = 0.01

100

Sequential noise = 0.1

Noise floor noise = 0.5

noise = 1.0

10 1 10 2

5

10

15

5

10 15 5 Communication round

10

15

5

10

15

Figure 4: Noise robustness. Reconstruction error vs. rounds at four noise levels ε. Parallel and sequential converge to the same noise floor.

which Gk,ℓ has fallen below half of its value at worker activation. Here mk denotes the per-worker contraction factor of the recurrence (8), and Fk denotes the per-component contraction factor of the rank-1 subroutine from Assumption 1. The empirical warm-up sbk is taken as the first round after which Gk,ℓ decays monotonically over the next five rounds, and m b k is the fitted slope; we use sbk and m b k as the empirical estimates of the theoretical sk and mk . Figure 5 compares these estimates to the theoretical predictions. Panel (A) overlays the fitted exponentials on the empirical Gk,ℓ curves and shows that every worker enters geometric decay after a brief warm-up. Panel (B) plots sbk together with the staggered-activation prediction sk = k and the Lambert-W upper bound from (32): the observed warm-up tracks sk = k, while the Lambert-W bound is conservative on this well-separated spectrum, as expected of a worst-case bound (for visual clarity, the displayed curve uses the looser global-mk form of (32), while the proof states a tighter per-predecessor maximum over k ′ ≤ k; both are valid upper bounds on sk ). Panel (C) places the fitted m b k next to the recurrence mk = max{Fk , 1/k + (k − 1)mk−1 /k} from (8), and the two agree within seed-to-seed noise. Together the three panels confirm that the convergence rate predicted by Theorem 1 is attained empirically and that the fitted contraction rate m b k matches the recurrence (8) for mk within seed-to-seed variability. F.3

Spectral-Gap Sensitivity

The third experiment probes Assumption 2 directly by sweeping the spectral gap and tracking how convergence degrades as it closes. We use a linear profile σk⋆ = 1 − (k − 1)g for k = 1, . . . , r⋆ , clamped at a floor of 0.01 so the problem stays well-posed when g is small. Here g is the spectral-gap step parameter for this experiment, distinct from the growth interval ∆ used in the main text (Table 8). The remaining settings match Section F.2: m = 50, d = 80, n = 200, r⋆ = 5, T = 10,
L = 30. On this profile the per-worker gap from Assumption 2, Tk⋆ = min minj>k |σk⋆ − σj⋆ |, σk⋆ , equals min(g, σk⋆ ) for k < r⋆ , so over the swept range the ratio g/σ1⋆ directly controls mink Tk⋆ /σ1⋆ . We sweep g/σ1⋆ ∈ {0.01, 0.05, 0.1, 0.25, 0.5}. Figure 6 reports the outcome. Panel (a) shows that all five gap settings converge and that the per-round rate degrades smoothly as the gap shrinks: at g/σ1⋆ = 0.5 the reconstruction error reaches its floor within roughly five communication rounds ℓ, while at g/σ1⋆ = 0.01 it takes about twenty-five rounds. 25

k=4 k=5

Gk,

10 5

6000

Predicted (sk = k) Observed Thm 1 (Lambert-W)

4000 2000

10 6

0

0 20 40 Communication round

1 2 3 4 5 Worker index k

1.0 0.8 0.6 0.4 0.2 Thm 1 recurrence Fitted m 0.0 1 2 3 4 5 Worker index k

Contraction rate mk

k=1 k=2 k=3

Warm-up period sk

10 4

k

Figure 5: Theoretical-bound validation for Theorem 1. (A) Empirical Gk,ℓ per worker (solid) with fitted exponential decay (dashed) and observed warm-up marker. (B) Predicted (sk = k) vs. observed warm-up period, with the Lambert-W bound from (32) shown for reference. (C) Fitted contraction rate m b k vs. the recurrence (8).

10 4

Final W *

W* W F

10 3

W F

/ 1 = 0.5 / 1 = 0.25 / 1 = 0.1 / 1 = 0.05 / 1 = 0.01

10 1

10 5

10 5 0

10 20 Communication round

10 6 0.0

30

0.2 0.4 Spectral gap ratio min/ 1

Figure 6: Spectral-gap sensitivity (validates Assumption 2). (a) Convergence curves for five gap ratios g/σ1⋆ ; smaller gaps require more rounds but still converge. (b) Final reconstruction error vs. gap ratio decays to a floor below 10−4 even at g/σ1⋆ = 0.01.

Panel (b) plots the across-seed median of the final-round error against the gap ratio on a log scale; even at g/σ1⋆ = 0.01 the error drops below 10−4 , so the algorithm degrades gracefully rather than failing as the gap closes. A positive spectral gap is therefore sufficient for convergence on this profile, and shrinking the gap inflates the warm-up period sk (Theorem 1) smoothly rather than triggering a sharp phase transition, consistent with the role Tk⋆ plays in Assumption 2.

G

Additional Experimental Details

G.1

GLUE Training Details

Model and tokenizer. All GLUE experiments use DeBERTaV3-base [He et al., 2023] (microsoft/deberta-v3-base), a 12-layer, 768-hidden, 12-head transformer with ∼184M parameters. We freeze all pretrained weights and train only the rank-1 adapter parameters. Inputs are tokenized with the DeBERTaV3 SentencePiece tokenizer at maximum sequence length 128. Adapter configuration. We attach parallel rank-1 adapters to all 72 encoder linear layers (six per layer × 12 layers): Wq , Wk , Wv , Wo (attention) and Wf 1 , Wf 2 (FFN). Each adapter has rmax = 4 components and both ak and bk vectors are initialized from N (0, 0.02). We use the standard LoRA scaling α [Hu et al., 2022], with the per-task values reported in Table 8. Per-task hyperparameters. Table 8 lists the hyperparameters used for each task on the GLUE benchmark [Wang et al., 2019]; LoRA’s scaling convention follows Hu et al. [2022]. 26

Table 8: Per-task hyperparameters for A DA PA D on GLUE (seed=43). CoLA

RTE

MRPC

STS-B

SST-2

QNLI

QQP

MNLI

Epochs 10 50 30 25 24 5 7 9 Batch size 32 32 32 32 64 64 128 256 Learning rate 8×10−4 1.2×10−3 1×10−3 1.97×10−3 1×10−3 1×10−3 7×10−4 1.5×10−3 α 32 24 24 32 8 32 48 24 Weight decay 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 Warmup steps 100 100 100 100 1000 500 500 500 Grad clip 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 Top-h 3 3 6 1 5 3 5 2 ∆ (growth interval) 100 200 100 100 100 50 300 100 Orth reg coef λorth 0.3 0.3 0 0.5 0.2 0.2 0.15 0.1 Adapter dropout 0.0 0.0 0.3 0.0 0.1 0.0 0.1 0.2 Cls dropout 0.0 0.0 0.0 0.2 0.0 0.0 0.15 0.15 Adapter weight decay 0.0 0.01 0.01 0.0 0.0 0.0 0.0 0.0 LR schedule linear linear linear linear linear linear linear cosine Rank budget B 144 144 144 144 144 144 144 144

Orthogonal regularization. We optionally include the orthogonal
regularization term from IncreLoRA [Zhang et al., 2023a], λorth ∥A⊤ A − I∥F + ∥BB⊤ − I∥F /(2nlayers ), which pushes each module’s component vectors toward an orthonormal frame. We adopt it on GLUE with the per-task values in Table 8 and disable it on SQuAD. Baseline reproduction. We reproduce IncreLoRA as the primary comparison baseline because it is the closest method to A DA PA D: both grow rank incrementally from rank-1 components via importance-based allocation with EMA scoring. We use the authors’ official loralib (SVDLinear + RankAllocator) and their published hyperparameters, ported to our software environment (Python 3.11, PyTorch 2.6, Transformers 5.2, CUDA 12.9). For the remaining baselines (AdaLoRA, SoRA, dEBORA) we cite published results from their respective papers [Zhang et al., 2023b, Ding et al., 2023, Zangrando et al., 2025]. G.2

SQuAD/SQuAD v2 Training Details

Model and tokenizer. We fine-tune Qwen/Qwen3-0.6B [Qwen Team, 2025] with the standard AutoModelForQuestionAnswering span-prediction head. The backbone has 28 transformer blocks with hidden size 1024, FFN dim 3072, and grouped-query attention with 16 query heads and 8 KV heads. Inputs are tokenized at sequence length 384 with doc-stride 128, following the HuggingFace canonical preprocessing for both SQuAD v1.1 [Rajpurkar et al., 2016] and SQuAD v2 [Rajpurkar et al., 2018]. Adapter configuration. Both A DA PA D and the fixed-rank LoRA [Hu et al., 2022] baseline adapt all seven projection matrices in every transformer block: Wq , Wk , Wv , Wo , Wgate , Wup , Wdown , for a total of 7 × 28=196 adapted modules. A DA PA D’s rank-1 components initialise both ak and bk vectors from N (0, 0.02). We set rmax =8 and allocate the remaining budget by EMA importance scoring with the top-10 modules per growth round. Per-task hyperparameters. Table 9 lists the single A DA PA D recipe used across all four (task, r̄) cells. Only the rank budget changes between cells, driven by the average-rank target; all other hyperparameters are shared. G.3

Hardware and Software

Unless otherwise stated, all experiments run on 4× NVIDIA H200 80 GB GPUs connected by NVLink on a single node. Software: Python 3.11, PyTorch 2.6, Transformers 5.2, CUDA 12.9.

27

Table 9: A DA PA D hyperparameters on SQuAD/SQuAD v2 (seed=43). A single recipe is used for all four cells; only the rank budget B changes between r̄=4 and r̄=6. Epochs Batch size Max sequence length Doc-stride Total optimiser steps Learning rate α Weight decay Warmup steps Grad clip Top-h ∆ (batches per growth round) Orth reg coef Adapter dropout LR schedule rmax Rank budget B (r̄=4 / r̄=6) Optimiser

SQuAD v1.1

SQuAD v2

3 16 384 128 16,650 1×10−3 16 0.0 1,000 1.0 10 400 0.0 0.0 linear 8 784 / 1,176 AdamW (bf16)

3 16 384 128 24,777 1×10−3 16 0.0 1,000 1.0 10 400 0.0 0.0 linear 8 784 / 1,176 AdamW (bf16)

28