{"id":"7e161cac-9430-43e0-8277-6ec5ed328bc2","arxiv_id":"2412.08561","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"Reusing the Gram matrix for m iterations in a Levenberg-Marquardt method yields global convergence with O(d^3/epsilon + d^2/epsilon^2) total cost and local superlinear rate.","lead":"This paper introduces a Levenberg-Marquardt variant that reuses the same Gram matrix for m consecutive steps instead of recomputing it every iteration. The method is claimed to solve nonlinear equations with lower total computation than standard LM, plus a fast local convergence rate.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 15's proof cannot apply Lemma 18: the transformed recurrence has α2/√η>1/2 for admissible parameters (e.g., L1=L2=μ=1,c=1) and the stated initialization gives s0≤1/16, not the required ≤1/24.","rationale":"The global complexity proof is largely self-consistent under Assumption 7, and the flop-counting for SVD reuse is coherent; that part plausibly supports the O(d^3ε^-1 + d^2ε^-2) claim. The reader is right that Assumption 7 is a genuine restriction and should be foregrounded, but the more decisive problem is internal to the local analysis: the step in Theorem 15 that converts Lemma 14 into the recurrence required by Lemma 18 is not justified, and the initialization does not meet the lemma's stated hypothesis. This is an internal gap, not merely a scope limitation. I therefore keep the reader's CONDITIONAL verdict: the global result may stand, but the local superlinear claim needs a repaired proof, and the experiments need more rigor.","tokens_in":15223,"tokens_out":30706,"duration_ms":301637,"concrete_test":"Re-derive the coefficient conversion in Theorem 15 with η=2(α1+α2^2). For a parameter set satisfying Assumptions 2 and 12, e.g., L1=L2=μ=1 and c=1, compute α1=1, α2=2, η=10 and check whether the inequality s_{t+1}≤0.5(s_t^2+s_t^{1.5})+s_{π(t)}s_t is actually implied by Lemma 14; the coefficient α2/√η≈0.632>0.5 shows the derivation is invalid. Also evaluate s0 from (19): s0≤1/16, not ≤1/24. If these checks reproduce, Theorem 15's proof must be repaired (e.g., strengthen (19) or change η) before the superlinear claim is accepted.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The local superlinear claim (Theorem 15) is not established as written. Lemma 14 yields ∥x_{t+1}-x*∥ ≤ α1 e_t^2 + α2 e_t^{1.5} + 2α1 e_{π(t)} e_t. With η=2(α1+α2^2) and s_t=η e_t, this becomes s_{t+1} ≤ (α1/η)s_t^2 + (α2/√η)s_t^{1.5} + (2α1/η)s_{π(t)}s_t. To match Lemma 18's recurrence one needs α2/√η ≤ 1/2, i.e., α2^2 ≤ α1; this is not assumed and fails for L1=L2=μ=1, c=1, where α1=1, α2=2, η=10, so α2/√η≈0.632. The first and third coefficients are bounded as needed, but the middle one is not. Additionally, the stated initial condition (19) gives s0 = η∥x0-x*∥ ≤ 2(α1+α2^2)/(32(α1+α2^2)) = 1/16, which does not satisfy the s0 ≤ 1/24 hypothesis of Lemma 18; the proof asserts s0≤1/24 without justification. Since the superlinear-rate conclusion is derived solely by invoking Lemma 18, the local theorem is unsupported. The global complexity result may still be correct, but the paper's advertised local guarantee needs a repaired proof.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes the Gram-Reduced Levenberg–Marquardt (GRLM) method for solving square nonlinear systems F(x)=0. The method reuses the Gram matrix J(x_pi(t))^T J(x_pi(t)) at snapshot points for m iterations and sets the regularization parameter lambda_t = sqrt(c ||J(x_t)^T F(x_t)||), requiring no line search or subproblem solves. Under a Lipschitz Jacobian assumption (Assumption 2) and a cubic-growth condition (Assumption 7), the authors prove an iteration complexity of O(m^2 + m^{-0.5} epsilon^{-2.5}) to reach an epsilon-stationary point, which with m = Theta(epsilon^{-1}) gives a total flop count of O(d^3 epsilon^{-1} + d^2 epsilon^{-2}), improving on the O(d^3 epsilon^{-2}) of prior LM methods. Under a non-degenerate Jacobian at the solution (Assumption 12), the paper claims an explicit local superlinear rate. Experiments on the Chandrasekhar H-equation and non-convex logistic regression compare GRLM with gradient descent and the regularized LM of Mishchenko.","tokens_in":15585,"tokens_out":17965,"duration_ms":155058,"significance":"If the proofs are repaired, the global complexity result is a genuine advance: it is, to my knowledge, the first LM-type method that avoids both line search and subproblem solves while achieving a total flop count better than O(d^3 epsilon^{-2}), and the flop analysis with reused Gram matrices is clean and plausible. The local superlinear rate is a desirable property that would also extend Mishchenko's method. The paper is commendable for including a complete global proof, the AM-GM-based tuning of m, and experiments on real-world datasets. However, the local convergence theorem, which is advertised in the abstract and in Table 1, is not proven as written; the recurrence used to invoke the external sequence lemma does not match what Lemma 14 actually provides, and the initial condition does not satisfy the lemma's hypothesis.","major_comments":[{"comment":"The proof of Theorem 15 does not establish the hypotheses of Lemma 18. Substituting s_t = eta e_t with eta = 2(alpha1 + alpha2^2) into inequality (18) yields s_{t+1} <= (alpha1/eta) s_t^2 + (alpha2/sqrt(eta)) s_t^{1.5} + (2 alpha1/eta) s_{pi(t)} s_t. The claimed recurrence s_{t+1} <= 1/2(s_t^2 + s_t^{1.5}) + s_{pi(t)} s_t requires alpha2/sqrt(eta) <= 1/2, i.e., alpha2^2 <= alpha1, which is not assumed and fails for admissible parameters (for example, L1 = L2 = mu = 1 and c = 1 give alpha1 = 1, alpha2 = 2, and alpha2/sqrt(eta) = 2/sqrt(10) approximately 0.632 > 1/2). Moreover, condition (19) gives s0 = eta ||x0 - x*|| <= eta/(32(alpha1 + alpha2^2)) = 1/16, whereas Lemma 18 requires s0 <= 1/24; the proof asserts s0 <= 1/24 without justification. Since the superlinear-rate conclusion is derived solely from Lemma 18, Theorem 15 is currently unsupported and needs a repaired argument.","section":"Section 4.2, proof of Theorem 15 (Appendix H)"}],"minor_comments":[{"comment":"In the I1 sum, the denominator should be L1^4, not L1^2: when lambda_t < L1^2, (L1^2 + lambda_t)^2 < 4 L1^4, so lambda_t^5/(6c^2(L1^2+lambda_t)^2) >= lambda_t^5/(24 c^2 L1^4). The printed L1^2 makes the inequality dimensionally inconsistent. The asymptotic iteration bound is unaffected after the constant is corrected.","section":"Proof of Theorem 9, inequality (27)"},{"comment":"The inner sum in the bound for ||x_t - z_t|| should be sum_{i=0}^{t-1} r_i, not sum_{i=0}^t r_i. With the printed sum_{i=0}^t r_i, the subsequent application of Lemma 17 to t = 0,...,m-1 is invalid; for example, with m = 2 and r_0 = r_1 = 1, sum_{t=0}^1 (sum_{i=0}^t r_i)^3 = 9 > (2^3/3)(1+1) = 16/3. The intended inequality holds with the corrected upper index t-1.","section":"Proof of Lemma 8 (Appendix E)"},{"comment":"The AM-GM lower bound for the third and fourth summands should be d^{2+0.75 alpha} epsilon^{-1.25-0.75 beta}, not d^{2+1.25 alpha} epsilon^{-1.25-0.75 beta}. The final conclusion m = Theta(epsilon^{-1}) and the resulting flop count are unaffected by this typo.","section":"Corollary 11, flop minimization"},{"comment":"In the induction, z_t = x_{pi(t)} belongs to {x_0,...,x_t}, not {x_1,...,x_t} as stated; the base case x_0 is needed when t < m.","section":"Proof of Theorem 15, induction step"},{"comment":"In line 4, the expression ||J(x_t)^T \\nabla f(x_t)|| should be ||J(x_t)^T F(x_t)|| (or ||\\nabla phi(x_t)|| with phi = 1/2||F||^2); the symbol f is otherwise undefined.","section":"Algorithm 1"},{"comment":"There are several spelling errors in method names (e.g., 'Levernberg' and 'Mardquardt' in Table 1 and Figure captions) and a misreferenced equation number in the proof of Lemma 14 where the bound on lambda_t is cited as (12); these should be corrected.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The global convergence analysis appears sound in structure and likely correct after small repairs (the L1^4 constant and the index shift in Lemma 8). The main obstacle to acceptance is the local superlinear theorem: as written, the proof invokes Lemma 18 with unmatching coefficients and an unverified initial condition. I would ask for a full rewrite of the local analysis, either by proving a suitable sequence lemma directly or by adding a condition on c (e.g., c <= mu^2 L2/(4 L1)) that makes the coefficient comparison go through, and by checking the initial condition accordingly. The experimental section is reasonable but does not test the superlinear regime; adding such a test would help verify the repaired theorem."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Xi—\n\nYou should know two things about this paper. First, the global complexity result looks real: reusing the Gram matrix for m iterations with Mishchenko's gradient-norm regularization actually buys you O(d^3 ε^{-1} + d^2 ε^{-2}) total flops, which beats the standard O(d^3 ε^{-2}) for LM methods. The proof in Lemmas 5–9 is mostly self-consistent, and the flop-counting through SVD reuse is sound. Second, the local superlinear claim in Theorem 15 is not established as written. The recurrence from Lemma 14 does not satisfy the external lemma they invoke, and the initialization is off by a factor. So the paper overclaims.\n\nWhat's genuinely new: Algorithm 1, the period-m Gram reuse with λ_t = sqrt(c||J(x_t)^T F(x_t)||), and the global flop analysis. The combination is not in the cited literature. The global proof is a real contribution: Lemma 8's descent over snapshots works with c = max{4L1L2m, M}, and the I1/I2 split in Theorem 9 is clean. The related work is honest; they clearly cite Shamanskii and Doikov et al. for lazy reuse and Mishchenko for the regularization.\n\nNow the soft spots, in proportion. The cubic-growth assumption (Assumption 7) is inherited from Mishchenko and is genuinely restrictive; it is not implied by Lipschitz Jacobians, and the paper should foreground that more than it does. The local proof: from (18), with η = 2(α1+α2^2) and s_t = η e_t, the recurrence becomes s_{t+1} ≤ (α1/η)s_t^2 + (α2/√η)s_t^{1.5} + (2α1/η)s_{π(t)}s_t. To apply Lemma 18 you need α2/√η ≤ 1/2, i.e. α2^2 ≤ α1, which is not assumed. For L1=L2=μ=1, c=1, α1=1, α2=2, and α2/√η ≈ 0.632. And the initial condition (19) gives s_0 = η||x0-x*|| ≤ 1/16, while Lemma 18 requires s_0 ≤ 1/24. So Theorem 15 is unsupported. This doesn't damage the global result, but it means the advertised superlinear rate is a claim without a proof.\n\nExperiments are indicative only: one random start, no repeated runs or error bars. They are fine as a sanity check, no more.\n\nWho should read this: anyone working on global complexity of second-order methods for nonlinear equations. The global contribution deserves referee time. I'd send it to peer review with a clear note that Theorem 15 needs a repaired proof or the local claim should be removed. The global part is solid enough that the paper should not be desk-rejected.","headline":"The global complexity result is a genuine improvement and mostly provable; the local superlinear theorem has a concrete proof gap and should not be cited in its current form.","tokens_in":16153,"tokens_out":6753,"would_cite":false,"duration_ms":60713,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["65H10","90C53","49M15"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims that reusing the Gram matrix every m iterations lowers the Levenberg–Marquardt cost to O(d^3 ε^{-1}+d^2 ε^{-2}) while preserving global and local superlinear convergence.","keywords":["nonlinear equations","Levenberg–Marquardt method","Gram matrix reuse","global convergence","local superlinear convergence","cubic-growth condition","nonconvex least squares"],"falsifier":"Construct a smooth $F$ with known $L_1,L_2,M$ that satisfies Assumptions 2 and 7 (for instance a mildly nonlinear trigonometric map), simulate Algorithm 1 with $m=\\Theta(\\epsilon^{-1})$, and check whether the decrease $\\|F(x_{km})\\|^2-\\|F(x_{(k+1)m})\\|^2$ is always at least $\\sum_{t=km}^{(k+1)m-1} r_t^2\\lambda_t/6$; if not, Lemma 8 and the complexity claim collapse.","tokens_in":15007,"feed_emoji":"⚡","tokens_out":9278,"duration_ms":81563,"temperature":0.7,"pith_summary":"The paper proposes Gram-Reduced Levenberg–Marquardt (GRLM), a method for solving nonlinear systems $F(x)=0$ that recomputes the Gram matrix $G(z_t)=J(z_t)^\\top J(z_t)$ only once every $m$ iterations and reuses it in between. It claims that, under a cubic-growth condition on $F$, this reuse preserves global convergence and yields a total cost of $O(d^3\\epsilon^{-1}+d^2\\epsilon^{-2})$ flops to reach an $\\epsilon$-stationary point, strictly better than the $O(d^3\\epsilon^{-2})$ of existing Levenberg–Marquardt methods. It also claims local superlinear convergence near a solution with non-degenerate Jacobian, with no line search or subproblem solver. The paper matters because it decouples the expensive Gram computation from the iteration count, giving LM methods a per-step cost comparable to quasi-Newton methods while keeping global guarantees.","feed_headline":"A Gram-reuse trick beats O(d^3/ε^2) for nonlinear equations","feed_subtitle":"Updating the Jacobian Gram matrix every m steps keeps convergence guarantees and cuts total flops to O(d^3/ε + d^2/ε^2).","key_machinery":"The Gram-reused update $x_{t+1}=x_t-(G(z_t)+\\lambda_t I)^{-1}J(x_t)^\\top F(x_t)$, where $z_t=x_{m\\lfloor t/m\\rfloor}$ is the snapshot and $\\lambda_t=\\sqrt{c\\|J(x_t)^\\top F(x_t)\\|}$. The analysis couples a two-sided step-size bound $\\lambda_t^2/(c(L_1^2+\\lambda_t))\\le r_t\\le\\lambda_t/c$ with a block-wise descent lemma that accumulates $\\sum r_t^2\\lambda_t/6$ over each $m$-step block; the cubic-growth condition forces the residual norm to drop across blocks. The local analysis uses the non-degeneracy $\\sigma_{\\min}(J(x^*))=\\mu>0$ to bound $(G(z_t)+\\lambda_t I)^{-1}$ and feed a sequence recurrence from lazy-Hessian Newton theory.","core_discovery":"The load-bearing claim is Corollary 11: running Algorithm 1 with $m=\\Theta(\\epsilon^{-1})$ finds a point with $\\|J(x)^\\top F(x)\\|\\le\\epsilon$ in $O(d^3\\epsilon^{-1}+d^2\\epsilon^{-2})$ total flops, improving on the $O(d^3\\epsilon^{-2})$ of prior LM analyses. The algorithm alternates between computing the SVD of the Jacobian at snapshot points $z_t = x_{m\\lfloor t/m\\rfloor}$ and taking cheap $O(d^2)$ steps that invert the reused matrix $(G(z_t)+\\lambda_t I)^{-1}$ applied to $J(x_t)^\\top F(x_t)$, with $\\lambda_t=\\sqrt{c\\|J(x_t)^\\top F(x_t)\\|}$. Under the additional assumption of a non-degenerate Jacobian at the solution, the iterates converge superlinearly with an explicit per-iteration rate stated in Theorem 15.","pith_inferences":["The cubic-growth condition is not implied by Lipschitz continuity of the Jacobian; for residuals whose quadratic model error grows faster than $\\|y-x\\|^3$, the stated global complexity has no support, and the method may still work in practice but without this guarantee.","The reuse idea is orthogonal to the choice of regularization; combining it with sketched or randomized Gram approximations could lower the $O(d^3)$ snapshot SVD cost and push the per-block cost toward $O(d^2)$, which would be a natural next step.","The local superlinear rate relies on a sequence lemma imported from lazy-Hessian theory; a self-contained proof of that recurrence would make the local result independent of that framework and clarify whether the factor $(1+m/2)$ is tight.","The optimal worst-case choice $m=\\Theta(\\epsilon^{-1})$ suggests an adaptive schedule in which $m$ grows as the iterate approaches stationarity could reduce the practical number of snapshots while preserving the asymptotic bound."],"forward_implications":["Choosing $m=\\Theta(\\epsilon^{-1})$ gives total flops $O(d^3\\epsilon^{-1}+d^2\\epsilon^{-2})$, strictly better than the $O(d^3\\epsilon^{-2})$ bound for existing LM methods.","After a snapshot SVD, each iteration costs $O(d^2)$ flops, matching the per-iteration cost of quasi-Newton methods while retaining global convergence.","The method requires no line search and no trust-region subproblem, so the implementation reduces to one reused matrix inverse per step.","For $m=1$, GRLM recovers Mishchenko's LM and improves its iteration bound from $O(\\epsilon^{-2.5}\\log(1/\\epsilon))$ to $O(\\epsilon^{-2.5})$.","Under non-degenerate Jacobian at the solution, the iterates converge superlinearly with the explicit rate $(1/2)^{2(1+(1+m/2)\\pi(t))(1+(t\\bmod m)/2)}$."],"supporting_citations":[{"why":"Supplies the adaptive regularization $\\lambda_t\\propto\\sqrt{\\|J(x_t)^\\top F(x_t)\\|}$ and the cubic-growth condition that GRLM inherits; also the baseline whose $O(d^3\\epsilon^{-2.5}\\log(1/\\epsilon))$ complexity is improved.","marker":"[35]"},{"why":"Provides the positive-sequence lemmas (Lemma B.1 and Theorem D.3) used to prove block-wise residual descent and the local superlinear rate.","marker":"[14]"},{"why":"Provides Proposition 2.3, used to show the Gram matrix stays uniformly positive definite in a neighborhood of a non-degenerate solution.","marker":"[31]"},{"why":"Representative existing LM global complexity bound $O(d^3\\epsilon^{-2})$ that GRLM claims to strictly improve.","marker":"[6]"},{"why":"Introduces the Shamanskii-style periodic reuse of Jacobian/Gram information that motivates the snapshot mechanism in GRLM.","marker":"[17]"}],"fun_headline_variants":["Gram-reduced LM beats O(d^3/ε^2) with O(d^3/ε) cost","Levenberg–Marquardt with reused Gram matrix cuts flops","Skipping Jacobian updates speeds up nonlinear solving","Better complexity for nonlinear equations via Gram reuse"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The global complexity result holds only under the cubic-growth condition $\\|F(y)\\|^2\\le\\|F(x)+J(x)(y-x)\\|^2+M\\|y-x\\|^3$ for all $x,y$, which is not a consequence of a Lipschitz-continuous Jacobian; the local superlinear rate additionally depends on a sequence recurrence that the paper cites rather than proves.","fun_headline_variants_meta":{"raw":{"variants":["Gram-reduced LM beats O(d^3/ε^2) with O(d^3/ε) cost","Levenberg–Marquardt with reused Gram matrix cuts flops","Skipping Jacobian updates speeds up nonlinear solving","Better complexity for nonlinear equations via Gram reuse"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000163,"raw_usage":{"total_tokens":1281,"prompt_tokens":1023,"completion_tokens":258,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":639,"completion_tokens_details":{"reasoning_tokens":180}},"tokens_in":639,"tokens_out":258,"duration_ms":4980,"temperature":1.0,"reasoning_tokens":180,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T17:46:01.023336+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct a smooth $F$ with known $L_1,L_2,M$ that satisfies Assumptions 2 and 7 (for instance a mildly nonlinear trigonometric map), simulate Algorithm 1 with $m=\\Theta(\\epsilon^{-1})$, and check whether the decrease $\\|F(x_{km})\\|^2-\\|F(x_{(k+1)m})\\|^2$ is always at least $\\sum_{t=km}^{(k+1)m-1} r_t^2\\lambda_t/6$; if not, Lemma 8 and the complexity claim collapse.","supporting_citations":[{"cited_title":"Second-order optimization with lazy Hessians","cited_arxiv_id":null,"evidence_quote":"Provides the positive-sequence lemmas (Lemma B.1 and Theorem D.3) used to prove block-wise residual descent and the local superlinear rate."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides Proposition 2.3, used to show the Gram matrix stays uniformly positive definite in a neighborhood of a non-degenerate solution."},{"cited_title":"Convergence and complexity analysis of a Levenberg–Marquardt algorithm for inverse problems","cited_arxiv_id":null,"evidence_quote":"Representative existing LM global complexity bound $O(d^3\\epsilon^{-2})$ that GRLM claims to strictly improve."},{"cited_title":"A shamanskii-like levenberg-marquardt method for nonlinear equations","cited_arxiv_id":null,"evidence_quote":"Introduces the Shamanskii-style periodic reuse of Jacobian/Gram information that motivates the snapshot mechanism in GRLM."}],"review_version":1}