{"id":"9524c86d-94de-40eb-a138-a90c0c8e4742","arxiv_id":"2607.21975","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":2,"one_line_summary":"Simultaneous LoRA gradient descent reaches ε-stationary points in O(ε^-4) full-gradient evaluations, and the new stochastic algorithms LoRA-NSGDM and LoRA-STORM achieve O(ε^-8) and O(ε^-6) oracle complexity.","lead":"Low-rank adaptation is a standard way to fine-tune large models, but its convergence behavior was poorly understood. This paper proves polynomial convergence rates for deterministic and stochastic LoRA training, including the first finite-variance stochastic guarantees.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: the polynomial-rate theorems are internally consistent and the quoted descent lemma checks out under independent derivation.","rationale":"The reader's verdict is CONDITIONAL, with Lemma A.1 identified as the weakest assumption. My independent check indicates that Lemma A.1 is correct under Assumption 1, so the conditional status is not forced by a mathematical error there. The more substantive limitation is that Definition 2.1 measures stationarity in factor space, which can be satisfied at points where the original weight-space gradient is not small; however, the paper states this criterion explicitly and compares with prior work under the same measure, so it does not undermine the central claim as formulated. The three main theorems are backed by careful, internally consistent proofs: Theorem 3.1 uses the weighted descent budget and the sharper trajectory bound to obtain T^{-1/4} scaling of the gradient norm; Theorem 4.5 controls the momentum error with a finite-variance oracle whose noise grows like ||V||, bounded by R_T; Theorem 5.2 uses the STORM correction whose second-moment difference is controlled by the mean-square smoothness assumption. I found no hidden reliance on higher moments in the stochastic analysis, and the normalization removes the unbounded step length that caused plain LoRA-SGD to diverge. The minor pseudocode gap concerning zero normalized directions is already handled implicitly in the proofs, and the experimental single-run reporting is a reproducibility weakness rather than a correctness issue. For these reasons, the appropriate verdict remains CONDITIONAL, and my stress-test does not change the reader's recommendation.","tokens_in":20746,"tokens_out":35899,"duration_ms":289344,"concrete_test":"Independently re-derive Lemma A.1 by expanding F(BA + Z) with Z = ΔB·A + B·ΔA + ΔB·ΔA and verify the stated constants, then test the inequality numerically on 10^5 random V and U with ρ = 1. If any violation appears, recompute the constants in Theorems 3.1, 4.5, and 5.2; otherwise the rates stand.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I could not identify a load-bearing flaw in the central argument. The paper's rates are explicitly for the factor-space stationarity measure of Definition 2.1, and all stated theorems deliver exactly that guarantee. The weakest point flagged by the reader is Lemma A.1, quoted from Mu and Klabjan (2026). An independent derivation from Assumption 1 supports it: writing Z = ΔB·A + B·ΔA + ΔB·ΔA, the descent inequality from ρ-smoothness gives a quadratic term bounded by √2ρ||U||²||V||², a cubic term bounded by √2ρ||U||³||V||, a quartic term bounded by (√2ρ/4)||U||⁴, and a cross term bounded by ||H||||U||², so the constants are valid. Lemma A.2 then follows in the same way as in the cited work. The deterministic trajectory bound in Theorem 3.1, the momentum error recursion in Lemma 4.3, the one-step descent in Lemma 4.4, and the STORM tracking lemma E.1 are all internally consistent; the stochastic proofs need only local smoothness on the bounded ball B_RT plus the variance bound of Lemma 2.2, not the higher-order moment control that was the original obstruction. The factor-space criterion is genuinely weaker than stationarity in the original weight space, but this is an explicit scoping choice shared with the prior work and is not an internal inconsistency. The remaining issues are minor: Algorithms 2 and 3 do not specify the update when the normalized direction is zero (the analysis covers it as a zero step), and the STORM oracle count assumes reuse of the initial evaluation; neither affects the asymptotic rates.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper analyzes the convergence of simultaneous two-factor LoRA optimization. It proves that deterministic LoRA-GD finds a point with ||∇J(B,A)||_F ≤ ε using O(ε^{-4}) full-gradient evaluations, improving on the exponential exp{O(ε^{-2})} bound of Mu and Klabjan. For the stochastic setting, it shows that plain LoRA-SGD can fail in expectation under finite variance alone, and it proposes LoRA-NSGDM, with O(ε^{-8}) stochastic oracle complexity under finite variance, and LoRA-STORM, with O(ε^{-6}) under mean-square smoothness. The rates are for the factor-space stationarity measure of Definition 2.1. The paper also reports experiments on logistic regression, ResNet-18, and TinyLlama fine-tuning.","tokens_in":21069,"tokens_out":45062,"duration_ms":373845,"significance":"Subject to the explicit factor-space stationarity criterion, the results are technically sound and constitute a substantial advance: they answer the open problem left by Mu and Klabjan and provide the first polynomial stochastic guarantees for simultaneous LoRA factor updates under standard finite-variance assumptions. I checked the main chains of proof, including the summed trajectory bound in Theorem 3.1, the momentum error recursion in Lemma 4.3, and the STORM tracking inequality in Lemma E.1, and found them internally consistent; in particular, the constant in Lemma E.1 (2q^2/[a(2-a)] ≤ 1/a) is valid. The normalization and STORM correction are natural ways to bypass the higher-moment obstruction identified in prior work, and the theorems state explicit dependencies on the problem parameters. The main caveat, which the paper acknowledges at Definition 2.1, is that ||∇J(V)|| ≤ ε is weaker than smallness of the original weight-space gradient ∇F(BA); this should be stated more prominently.","major_comments":[],"minor_comments":[{"comment":"The paper's complexity statements all use the factor-space criterion ||∇J(V)|| ≤ ε, which is explicit but is not equivalent to ||∇F(BA)|| ≤ ε; a point with A or B aligned with a nullspace of ∇F(BA) can satisfy the former without the latter, so the introduction or Section 2 should carry a remark clarifying the practical scope of the guarantees.","section":"Definition 2.1"},{"comment":"Lemma A.1 is the load-bearing descent inequality used by Theorems 3.1, 4.5, and 5.2, but it is quoted from Mu and Klabjan without proof; please include a short derivation or proof sketch in the appendix so the paper is self-contained.","section":"Appendix A"},{"comment":"Algorithms 2 and 3 divide by s_t, but no update is specified when s_t = 0; the proofs handle that case as a zero step, so the pseudocode should state this convention explicitly.","section":"Algorithms 2 and 3"},{"comment":"The claimed oracle count 1 + 2(T−1) assumes the initial evaluation H_0 is reused at t = 0, whereas line 6 as written evaluates the oracle twice at V_0 = V_{−1}; please clarify the implementation convention in the text or pseudocode.","section":"Algorithm 3"},{"comment":"The display for C in Eq. (23) is garbled, with the term after 4Δ likely intended as 4√Δ · (2ρ)^{1/4} or similar; please restate it in terms of C_0 and C_1 to avoid ambiguity.","section":"Equation (23)"},{"comment":"The experiments report training loss rather than the factor-gradient stationarity measure used in the theorems, so they do not directly verify the predicted convergence rates; a plot of ||∇J(V_t)|| on the small logistic-regression problem would strengthen the connection between theory and practice.","section":"Section 6"}],"recommendation":"minor_revision","confidential_remarks":"The manuscript is a solid theory contribution and is well within the scope of the journal. There is no citation or novelty concern; the relationship to Mu and Klabjan is clearly stated. The only substantive caveat is the factor-space stationarity measure, which is shared with the prior work but should be emphasized in the final version. I would be comfortable seeing a revised version with the minor points addressed."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"I read this one carefully. The main claims are: LoRA-GD needs only O(ε^-4) full-gradient evaluations instead of the previous exp{O(ε^-2)}, and two stochastic methods—LoRA-NSGDM and LoRA-STORM—achieve O(ε^-8) and O(ε^-6) oracle complexity under finite variance, with the latter needing mean-square smoothness. The proofs are the real contribution, and they hold up. I checked the trajectory bound in Theorem 3.1, the momentum error recursion in Lemma 4.3, and the STORM tracking lemma. The argument is internally consistent. The normalized-step trick is a sensible fix for the exploding higher-order moments that killed plain SGD; the counterexample in Proposition 4.1 makes that concrete. This closes an actual gap left by Mu and Klabjan.\n\nThe soft spots are mostly in the presentation and experiments. The experiments are single runs, no error bars, no code link, and LoRA-STORM is only tested on a small logistic regression task. That's not a deal-breaker for the theory, but it undersells the algorithms. The pseudocode should also handle the case where the normalized direction is zero; the analysis covers it as a zero step, but the algorithm as written divides by zero. A minor fix. More substantively, all guarantees are for the factor-space stationarity measure ||∇J(V)|| ≤ ε, which is weaker than weight-space stationarity. The authors are explicit about this and it matches prior work, but readers should keep it in mind.\n\nI don't see a load-bearing flaw. The rates are what they say they are. The citations look right, with the prior work clearly distinguished. The paper is for people working on optimization theory for LoRA and similar factored parameterizations, and for anyone designing optimizers for fine-tuning. It deserves a serious referee. I would send it to peer review; the experiments and some presentation details need work, but the mathematical core is solid and worth publishing.","headline":"Solid theory paper that closes the LoRA convergence gap with polynomial rates; the proofs hold up, and the main weaknesses are experimental and presentational.","tokens_in":21660,"tokens_out":6473,"would_cite":true,"duration_ms":53326,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C26","90C15","68T07"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper establishes that simultaneous two-factor LoRA optimization converges with polynomial oracle complexity—$O(\\epsilon^{-4})$ for deterministic LoRA-GD, $O(\\epsilon^{-8})$ for stochastic LoRA-NSGDM, and $O(\\epsilon^{-6})$ for…","keywords":["low-rank adaptation","LoRA","nonconvex optimization","stochastic gradient methods","momentum","variance reduction","stationarity","convergence analysis"],"falsifier":"Check Lemma A.1 directly: for $F(X)=\\|X\\|_F^2$ ($\\rho=1$) and random $V,U$ of varying norms, compute the left and right sides of the displayed inequality; a single violation shows the descent model on which all three theorems rest is false. Alternatively, run Algorithm 1 on a smooth nonconvex $F$ and plot $\\min_{t<T}\\|\\nabla J(V_t)\\|_F$ against $T$; decay slower than $O(T^{-1/4})$ would contradict Theorem 3.1.","tokens_in":20514,"feed_emoji":"📉","tokens_out":12391,"duration_ms":95243,"temperature":0.7,"pith_summary":"Low-rank adaptation (LoRA) fine-tunes a frozen pretrained matrix by training two small factors, $B$ and $A$, whose product is the only learnable update; the resulting objective $J(B,A)$ is nonconvex and can lack a globally Lipschitz gradient even when the underlying loss is smooth. Prior work on the simultaneous two-factor LoRA gradient method returned only an exponential oracle complexity $\\exp\\{O(\\epsilon^{-2})\\}$ for finding an $\\epsilon$-stationary point, and left the stochastic setting open. This paper proves a polynomial deterministic bound $O(\\epsilon^{-4})$ for LoRA-GD, and constructs two stochastic methods—LoRA-NSGDM with normalized momentum steps and LoRA-STORM with same-sample variance reduction—that reach an $\\epsilon$-stationary point in $O(\\epsilon^{-8})$ and $O(\\epsilon^{-6})$ stochastic oracle evaluations, respectively. Thus, in oracle terms, simultaneous LoRA optimization is no harder than ordinary smooth nonconvex optimization, which matters because LoRA is the standard parameter-efficient fine-tuning tool for large models.","feed_headline":"LoRA fine-tuning converges in polynomial time","feed_subtitle":"New analysis replaces exponential LoRA-GD rate with O(ε⁻⁴) and adds stochastic O(ε⁻⁸)/O(ε⁻⁶) guarantees.","key_machinery":"The load-bearing device is a modified descent inequality (Lemma A.1), which bounds the non-smooth factored objective by a fourth-order polynomial in the update direction: $J(V+U)\\le J(V)+\\langle\\nabla J(V),U\\rangle+\\sqrt{2}\\rho\\|U\\|^2\\|V\\|^2+\\sqrt{2}\\rho\\|U\\|^3\\|V\\|+(\\sqrt{2}\\rho/4)\\|U\\|^4+\\|\\nabla F(BA)\\|\\,\\|U\\|^2$. Every descent step in Theorems 3.1, 4.5, and 5.2 is built on this inequality, which replaces the unavailable global Lipschitz-gradient condition for the factored objective. Around it, the deterministic proof uses a trajectory bound $\\|V_t\\|^2=O(\\sqrt{t})$ obtained by summing before Cauchy–Schwarz, while the stochastic proofs add two algorithmic devices: normalizing each update to a prescribed step length (LoRA-NSGDM) and subtracting a same-sample correction between consecutive iterates (LoRA-STORM) to control the cubic and quartic noise terms that the descent inequality introduces.","core_discovery":"The central claim is that simultaneous two-factor LoRA updates admit polynomial first-order convergence rates. Writing the two factors as a single variable $V=[B;\\,A^\\top]$ and measuring stationarity by $\\|\\nabla J(V)\\|_F\\le\\epsilon$, the paper proves that the standard LoRA-GD algorithm reaches an $\\epsilon$-stationary point in $O(\\epsilon^{-4})$ full-gradient evaluations. The improvement comes from a sharper trajectory estimate: summing the factor-norm recursion before applying Cauchy–Schwarz yields $\\|V_t\\|_F^2=O(\\sqrt{t})$ instead of $O(t)$, so the normalized stepsize $\\eta_t$ decays like $t^{-1/2}$ and the cumulative stepsize grows like $\\sqrt{T}$. For stochastic oracles, the paper first shows that plain LoRA-SGD can fail—with an explicit one-dimensional example where the expected objective and expected gradient norm are infinite—and then proves that LoRA-NSGDM, whose update is normalized to a fixed length and filtered by momentum, finds an $\\epsilon$-stationary point with $O(\\epsilon^{-8})$ oracle calls under unbiasedness and finite variance. Under the additional mean-square smoothness condition, LoRA-STORM reuses each fresh sample at two consecutive iterates to correct the gradient estimator and improves the bound to $O(\\epsilon^{-6})$.","pith_inferences":["The same descent-inequality technique should transfer to other bilinear parameterizations, such as matrix factorization or dictionary learning, whenever stationarity is measured in the factored parameter space; the results are not tied to LoRA's particular architecture choices.","Because the stationarity criterion $\\|\\nabla J(V)\\le\\epsilon$ lives in factor space, it is weaker than stationarity in the original weight space; practitioners who stop on weight-space gradients will need a separate translation of these rates.","The constants in the $O(\\epsilon^{-8})$ and $O(\\epsilon^{-6})$ bounds scale with quantities such as $\\|V_0\\|$, $\\|\\nabla F(0)\\|$, $\\sigma$, and $\\rho$, so a practical next step is to derive adaptive schedules for the momentum and normalization parameters instead of the fixed power-law choices $\\alpha=T^{-1/2}$, $\\gamma=T^{-7/8}$, $a=T^{-2/3}$, $\\eta=T^{-5/6}$.","A natural testable extension is a single-call variance-reduced LoRA method: LoRA-STORM uses $2T-1$ oracle evaluations, and the paper itself notes this makes it less attractive on large models; a single-call variant at a comparable rate would settle the trade-off."],"forward_implications":["Deterministic LoRA-GD moves from exponential to polynomial oracle complexity: $O(\\epsilon^{-4})$ full-gradient evaluations suffice for an $\\epsilon$-stationary point in factor space.","Stochastic LoRA can be made convergent under only unbiasedness and finite variance, via LoRA-NSGDM with $O(\\epsilon^{-8})$ oracle complexity; the paper also proves that plain LoRA-SGD can diverge in expectation under the same assumptions.","Under mean-square smoothness, LoRA-STORM improves the stochastic complexity to $O(\\epsilon^{-6})$, bringing LoRA in line with typical variance-reduced nonconvex rates despite the bilinear factorization.","The paper's experiments on logistic regression, ResNet-18, and TinyLlama indicate that LoRA-NSGDM converges faster and more steadily than adaptive-stepsize LoRA-GD baselines in practice."],"supporting_citations":[{"why":"Supplies the modified descent inequality (Lemma A.1), the one-step descent lemma, the gradient upper bound, and the exponential baseline rate that is sharpened to $O(\\epsilon^{-4})$.","marker":"Mu and Klabjan (2026)"},{"why":"Defines the LoRA parameterization $W=W_{\\mathrm{base}}+sBA$ and the objective $J(B,A)=F(BA)$.","marker":"Hu et al. (2022)"},{"why":"Provides the momentum-based variance-reduction estimator that LoRA-STORM adapts with the correction term $\\hat{G}(V_t;\\xi_t)-\\hat{G}(V_{t-1};\\xi_t)$.","marker":"Cutkosky and Orabona (2019)"},{"why":"Documents that the factored objective generally lacks a globally Lipschitz gradient, motivating the local descent inequality used throughout.","marker":"Malinovsky et al. (2024)"}],"fun_headline_variants":["Polynomial-time convergence for LoRA fine-tuning","LoRA gets polynomial rates, plus stochastic improvements","Stochastic LoRA tamed: O(ε⁻⁸) and O(ε⁻⁶) oracle bounds","LoRA-SGD can fail; new algorithms guarantee convergence"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the modified descent inequality of Lemma A.1—quoted from prior work rather than rederived here—is correct, because every descent step in Theorems 3.1, 4.5, and 5.2 is built on that fourth-order upper bound on $J(V+U)$; if it fails or has different constants, the stated complexity bounds do not follow, and the guarantees are only for the weaker factor-space stationarity notion.","fun_headline_variants_meta":{"raw":{"variants":["Polynomial-time convergence for LoRA fine-tuning","LoRA gets polynomial rates, plus stochastic improvements","Stochastic LoRA tamed: O(ε⁻⁸) and O(ε⁻⁶) oracle bounds","LoRA-SGD can fail; new algorithms guarantee convergence"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000428,"raw_usage":{"total_tokens":2237,"prompt_tokens":1044,"completion_tokens":1193,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":660,"completion_tokens_details":{"reasoning_tokens":1117}},"tokens_in":660,"tokens_out":1193,"duration_ms":10806,"temperature":1.0,"reasoning_tokens":1117,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T15:30:09.426503+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Check Lemma A.1 directly: for $F(X)=\\|X\\|_F^2$ ($\\rho=1$) and random $V,U$ of varying norms, compute the left and right sides of the displayed inequality; a single violation shows the descent model on which all three theorems rest is false. Alternatively, run Algorithm 1 on a smooth nonconvex $F$ and plot $\\min_{t<T}\\|\\nabla J(V_t)\\|_F$ against $T$; decay slower than $O(T^{-1/4})$ would contradict Theorem 3.1.","supporting_citations":[],"review_version":2}