{"id":"d7bc595a-9f02-404e-8584-212528e3a965","arxiv_id":"2506.00521","paper_version":6,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"Under the Kurdyka-Lojasiewicz property, regularized SR1 quasi-Newton methods achieve non-asymptotic superlinear convergence without strong convexity.","lead":"This paper proves explicit convergence rates for two regularized quasi-Newton methods on problems that satisfy a Kurdyka-Lojasiewicz condition instead of strong convexity. It is the first such non-asymptotic result for SR1 variants, showing superlinear convergence after enough iterations when the KL exponent is at most 1/2.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The superlinear rates for nonsmooth composite problems depend on exact global minimization of cubic-regularized subproblems; the paper's Remark 4.5 relaxation is unproved and no solver is given, so the nonsmooth claim remains an oracle result.","rationale":"The reader identified the exact global minimization of the cubic-regularized subproblem as the weakest assumption, and my review reaches the same conclusion after checking the proof structure. The descent bounds in Lemma 5.7 are obtained from the global optimality of x_{k+1}, and no inexact or easily verifiable condition is proven to yield the same bounds. The paper's own Remark 4.5 gestures at a relaxation but gives no proof, and Section 6 confines experiments to smooth problems. This is the most load-bearing concern because it determines whether the stated nonsmooth composite setting is actually covered by the theorems or only a smooth-case result. I do not find a separate internal inconsistency that overturns the mathematics for the smooth case; the trace potential argument and the SR1 update ordering appear coherent, and the main rate derivations are plausible aside from minor constant typos. Therefore the appropriate verdict remains conditional, as the reader concluded.","tokens_in":33343,"tokens_out":8800,"duration_ms":82260,"concrete_test":"Re-derive Lemma 5.7 and the proof of Theorem 4.2 under only the sufficient-decrease condition (12) from Remark 4.5, replacing the global-minimizer assumption in Algorithm 1 step 1a. If any descent or KL-summation inequality in the proof fails under (12) alone, then the nonsmooth rates require an exact global oracle; if the proof goes through, the lack of an exact subproblem solver is less damaging.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central rates in Theorems 4.2 and 4.9 are proven for Algorithms 1 and 2, whose update steps require a global minimizer of a cubic-regularized composite subproblem (Algorithm 1, step 1a, equation (6); Algorithm 2, step 1, equation (15)). The proofs of the sufficient-decrease inequalities (Lemma 5.7, inequality (46), and Lemma 5.17) use global optimality of x_{k+1} to obtain the descent bounds that drive the KL-based sum estimates. For general nonsmooth g, this subproblem is nonconvex when g is nonconvex; even for convex g, exact global minimization is generally not achievable in finite time for typical nonsmooth terms such as the ℓ1 norm or an indicator function. Remark 4.5 asserts that a stationary point satisfying inequality (12) suffices, but no proof is supplied that (12) preserves the descent, sumability, and rate arguments of Section 5. Section 6 explicitly tests only smooth problems and states that solving the nonsmooth subproblems is left to future work. Consequently, the paper's advertised non-asymptotic superlinear rates for nonsmooth composite problems apply to an oracle algorithm rather than to any currently implementable method; the smooth (g=0) case remains a valid and nontrivial contribution.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript studies non-asymptotic convergence rates for two regularized SR1 quasi-Newton methods: Cubic SR1 PQN (Algorithm 1) for possibly nonconvex nonsmooth composite objectives F = g + f satisfying the Kurdyka-Łojasiewicz property, and Grad SR1 PQN (Algorithm 2) for convex composite objectives. Under Assumptions 1-2 (Lipschitz-smooth f with Lipschitz Hessian, KL property of F), Theorems 4.2 and 4.9 establish global subsequential convergence and explicit rates for the subgradient norm, with last-iterate superlinear rates when the desingularizing function is φ(t)=ct^{1-θ} for θ≤1/2 and window-minimum sublinear rates for θ∈(1/2,1). Theorem 4.13 and Appendix A add global non-asymptotic rates under a gradient-domination (Łojasiewicz) inequality. The proof relies on a trace potential V(G)=tr G and rank-one SR1 update identities, following the framework of [54]. Section 6 reports experiments on smooth quadratic, logistic-regression, and image-deblurring problems.","tokens_in":33642,"tokens_out":9939,"duration_ms":91921,"significance":"If the main theorems are read as conditional mathematical statements, the trace-potential argument is a genuine and nontrivial extension of the strongly convex analysis in [54] to KL functions, and the explicit rates for smooth nonconvex objectives appear novel. The paper also deliberately avoids line search, trust regions, the Dennis-Moré condition, and strong convexity, which are standard assumptions in quasi-Newton theory. The numerical experiments confirm the expected superlinear behavior on smooth problems. However, the advertised nonsmooth composite results currently rely on an exact global-minimization oracle for the subproblem, and Remark 4.5, which claims an inexact relaxation, is unproved; the practical contribution is therefore weaker than the abstract suggests.","major_comments":[{"comment":"The nonsmooth composite rates in Theorems 4.2 and 4.9 apply to an oracle algorithm. Algorithm 1, Step 1a, Eq. (6), and Algorithm 2, Step 1, Eq. (15), require a global minimizer of a cubic-regularized composite subproblem. For general nonconvex g this subproblem is nonconvex, and even for nonsmooth convex g exact global minimization is not generally implementable. Remark 4.5 asserts that a stationary point satisfying Eq. (12) suffices, but no proof is given that Eq. (12) preserves the sufficient-decrease, sumability, and rate arguments of Section 5. Section 6 explicitly tests only smooth problems and states that nonsmooth subproblem solving is left to future work. To support the abstract's nonsmooth composite claim, the authors should either provide an implementable (possibly inexact) subproblem solver together with a proof that the rates survive, prove the relaxation in Remark 4.5, or restrict the theoretical claims to an exact-oracle setting and reword the abstract and introduction accordingly.","section":"Section 4.2.1, Eq. (6) and (15); Remark 4.5; Section 6"},{"comment":"The abstract states that 'after a number of iterations k0, Cubic SR1 PQN exhibits non-asymptotic explicit super-linear convergence rates', but this overstates the theorem. For a general desingularizing function φ, Theorem 4.2, Eq. (8), gives a window-minimum rate with exponent N/(N+1), which is sublinear, not superlinear. Last-iterate superlinear rates are proven only for φ(t)=ct^{1-θ} with θ∈(0,1/2] (Eqs. (9) and (10)). For θ∈(1/2,1), Eq. (11) is again a window-minimum sublinear rate. The abstract and the introductory summary should qualify the superlinearity claim by the class of desingularizing functions.","section":"Abstract; Theorem 4.2, Eqs. (8), (9), (10), (11)"},{"comment":"The global rate in Theorem 4.13, Eq. (21), states ∥∇f(x_N)∥ ≤ (c^2 C_G D/(2N))^{N/2} ∥∇f(x_0)∥^{2/(N+1)}, but the proof in Eq. (176) derives the same bound with ∥∇f(x_0)∥ to the first power and no extra factor. The telescoping product in the proof does not produce the exponent 2/(N+1). The theorem statement and the proof therefore disagree, and the printed global-rate claim is not established as written. This should be corrected before the result can be used.","section":"Theorem 4.13, Eq. (21), and Proof of Theorem 4.13, Eq. (176)"}],"minor_comments":[{"comment":"The proof of Theorem 4.2 ends with an exponent 2/(N+1) on g_{k0}, while the theorem statement in Eq. (8) and the intervening derivation give 1/(N+1). This is likely a typographical error, but it should be aligned.","section":"Proof of Theorem 4.2, Eq. (87)"},{"comment":"The displayed rate in Remark 4.6, Eq. (14), appears as '≤ μ 6 (...)' and should read '≤ (6/μ) (...)' as in Theorem A.2. Please correct the notation.","section":"Remark 4.6 and Appendix A, Theorem A.2"},{"comment":"Lemma 5.19 states ∥F'(x_k)∥ ≤ λ_k^2/L_H for k ≥ k0, but Algorithm 2 defines λ_{k+1} = sqrt(L_H ∥F'(x_{k+1})∥) + L_H r_k, so the inequality is valid for indices shifted by one and not for k=0 with λ_0=0. The index convention should be stated explicitly.","section":"Algorithm 2, Step 3, and Lemma 5.19, Eq. (109)"},{"comment":"The text says the Lipschitz constant of the Hessian is L_H = 4 max_i ∥a_i∥, but the experiment sets L_H = 4 heuristically. If the theoretical rates are to be compared to the experiment, the authors should report whether the heuristic value is actually a valid upper bound for the chosen data set and parameters.","section":"Section 6.1.1, logistic regression"},{"comment":"The constant C_CR1 in the theorem statement is (n+1)L + nκ̄ + 2nL_H R, while in the proof of Eq. (82) it is defined as (n+1)L + 2nκ̄ + 2L_H R. These should be reconciled, including the factor of n on κ̄.","section":"Theorem 4.2 and proof, constants"}],"recommendation":"major_revision","confidential_remarks":"The core trace-potential argument appears sound for the exact-oracle algorithm, and the smooth-case results are a credible contribution. The main obstacle to acceptance is the gap between the advertised nonsmooth composite rates and the implementable algorithm: the paper needs either a proof of the Remark 4.5 relaxation or an explicit inexact/implementable subproblem solver with rates, plus a corrected abstract. The paper depends heavily on [54], but the dependence is transparent and the KL extension is substantial. I would be willing to review a revised version."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nRead this one. The genuinely new result is the smooth case: Theorem 4.2 with g=0 gives the first explicit non-asymptotic superlinear convergence rates for cubic-regularized SR1 quasi-Newton without strong convexity, and Theorem 4.13/Appendix A cover gradient-dominated smooth objectives. The machinery—trace potential plus KL-based sum estimates—is coherent, and I checked the descent arguments in Section 5.2; they hold. The extension from [54]'s strong convexity assumption to KL is the right conceptual move, and the rates for θ ∈ (0,1/2] are new even for smooth nonconvex problems. That alone justifies a serious referee.\n\nThe soft spot is the nonsmooth composite story. Theorems 4.2 and 4.9 as stated apply to Algorithms 1–2, whose update steps require a global minimizer of a cubic-regularized proximal subproblem. For general nonsmooth g, that subproblem is not solvable in finite time by any known algorithm, and the paper's own Section 6 says only smooth problems are tested because nonsmooth solvers are future work. Remark 4.5 asserts that a stationary point satisfying inequality (12) suffices, but no proof is given that (12) preserves the descent and trace-potential arguments. The stress-test note is correct: without a proof of Remark 4.5, the nonsmooth rates are oracle results, not rates for an implementable method. The abstract and introduction do not make this distinction clearly enough; they should.\n\nOther issues are minor by comparison: some constant mismatches between statements and proofs, heuristic parameter choices in the experiments (LH set to 4 in logistic regression, restart counts, no code), and the abstract's superlinear claim is too broad for θ ∈ (1/2,1), where Theorem 4.2 gives window-minimum sublinear rates. These are fixable and don't undermine the smooth analysis.\n\nThis paper deserves peer review, not a desk reject. A good referee can separate the solid smooth-core result from the unsupported nonsmooth claims. I'd send it out, with a request that the authors either prove Remark 4.5 or reframe the nonsmooth rates as conditional on an oracle and move the implementable contribution to the smooth setting. That would be an honest and still substantial paper.\n\nI'd cite the smooth-case rates.","headline":"Smooth-case rates are a real advance; the nonsmooth composite claim is an oracle result that needs either a proof of Remark 4.5 or an honest caveat.","tokens_in":34149,"tokens_out":1965,"would_cite":true,"duration_ms":18442,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C53","90C26","90C25","49J52"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that regularized SR1 quasi-Newton methods enjoy explicit non-asymptotic superlinear convergence rates on nonconvex nonsmooth problems satisfying a Kurdyka–Łojasiewicz inequality, without strong convexity, line search, or…","keywords":["quasi-Newton methods","SR1 update","Kurdyka–Łojasiewicz property","non-asymptotic convergence rates","cubic regularization","gradient regularization","nonconvex nonsmooth optimization","superlinear convergence"],"falsifier":"Take a KL function $F=g+f$ with $g=\\|x\\|_1$ and smooth $f$ satisfying Assumptions 1–2 with $\\phi(t)=ct^{1/2}$, run the Cubic SR1 PQN update (6) using a standard proximal gradient solver with a fixed tolerance for the cubic subproblem, and check whether $\\|F'(x_k)\\|$ obeys the bound (10) for all $k\\ge k_0$. A violation, or the need to solve the subproblem to machine precision to observe the bound, would show the theorem depends on exact subproblem minimization rather than on the structure analyzed.","tokens_in":33127,"feed_emoji":"⚡","tokens_out":6214,"duration_ms":58672,"temperature":0.7,"pith_summary":"Strong convexity is the usual engine behind fast quasi-Newton convergence; this paper shows the Kurdyka–Łojasiewicz (KL) property can play that role instead. It analyzes two regularized SR1 proximal quasi-Newton methods—a cubic-regularized one for general nonconvex nonsmooth composite objectives and a gradient-regularized one for convex objectives—and derives explicit non-asymptotic bounds on the subgradient norm after an initial number of iterations. The headline result is a superlinear rate of order $\\left(\\frac{C}{(k-k_0)^{1/2}}\\right)^{(k-k_0)/2}$ when the KL desingularizing function is $\\phi(t)=ct^{1/2}$. These are the first such rates for regularized proximal SR1 methods without strong convexity, and they require no line search, trust region, Dennis–Moré condition, or assumptions on the quasi-Newton metrics.","feed_headline":"KL property yields explicit superlinear quasi-Newton rates","feed_subtitle":"Regularized SR1 methods get strong-convexity-style rates on nonsmooth nonconvex problems, no line search needed.","key_machinery":"The trace potential $V(G)=\\operatorname{tr} G$ together with the SR1 update formula (5) is the central object. Each SR1 step decreases the trace by $\\nu(A,G,u)=\\frac{u^\\top(G-A)^2u}{u^\\top(G-A)u}$, which measures how much closer the metric $G$ gets to the average Hessian $J_k$; cubic or gradient regularization adds enough curvature to keep $J_k\\preceq G_{k+1}\\preceq\\tilde G_{k+1}$ and to control the trace. The KL inequality then converts the guaranteed function decrease into control of $\\|F'(x_k)\\|$, and summing the trace decreases over iterations yields a geometric-mean contraction that becomes superlinear.","core_discovery":"The central claim is that the KL inequality with a desingularizing function $\\phi$ replaces strong convexity as the driver of superlinear convergence. Under Assumptions 1 and 2 (Lipschitz smoothness plus KL) and boundedness of the generated sequence, both algorithms have $\\|F'(x_k)\\|\to 0$, and for $k\\ge k_0$ explicit rates hold; for example, when $\\phi(t)=ct^{1/2}$, Cubic SR1 PQN satisfies $\\|F'(x_{N+k_0})\\| \\le \\left(\\frac{3c^2}{4}\\left(\\frac{C^{\\mathrm{CR}}_1}{N}+\\frac{C^{\\mathrm{CR}}_2}{N^{1/2}}\\right)\\right)^{N/2}\\|F'(x_{k_0})\\|$. The convex counterpart Grad SR1 PQN achieves an analogous bound with gradient regularization instead of cubic terms. The paper presents this as the first non-asymptotic explicit superlinear convergence result for regularized proximal SR1 methods on nonconvex nonsmooth KL objectives, and notes the rates are new even for smooth nonconvex problems.","pith_inferences":["The practical bottleneck is the cubic subproblem: the theorems assume an exact global minimizer, and the experiments solve only smooth problems; if inexact solvers are used, the rates may need a tolerance-dependent correction to remain valid.","The trace-restart mechanism looks transferable: any quasi-Newton update that preserves $J_k\\preceq G_{k+1}\\preceq\\tilde G_{k+1}$ and decreases the trace could inherit the same superlinear argument under KL, so other metric updates may admit similar bounds.","For the $\\theta=1/2$ case, the KL exponent coincides with gradient domination conditions, suggesting the result applies to overparameterized models where strong convexity fails but such domination often holds."],"forward_implications":["For any nonconvex nonsmooth KL objective with desingularizer $\\phi(t)=ct^{1/2}$, Cubic SR1 PQN attains a subgradient-norm rate of order $\\left(\\frac{C}{(k-k_0)^{1/2}}\\right)^{(k-k_0)/2}$ for all $k\\ge k_0$, which is superlinear.","The same type of guarantee holds for Grad SR1 PQN on convex KL objectives, with gradient regularization instead of cubic terms, at lower per-iteration cost.","No line search, trust region, Dennis–Moré condition, or strong convexity is needed for these rates; the only global mechanism is the restarting rule that resets the metric to $LI$ when its trace exceeds $n\\bar\\kappa$.","When $F$ satisfies a global Łojasiewicz inequality, the rates become global, holding from the first iteration rather than after an initial $k_0$.","The analysis covers nonsmooth additive composite problems $F=g+f$ with nonconvex $g$, so the result applies beyond smooth objectives."],"supporting_citations":[{"why":"Supplies the two regularized SR1 proximal quasi-Newton algorithms whose strongly convex analysis is here transferred to the KL setting.","marker":"[54]"},{"why":"Provides cubic regularization and the Taylor-type bounds used in the descent estimates.","marker":"[42]"},{"why":"Gives the uniformized KL property that turns the local KL inequality into a global tool for non-asymptotic rates.","marker":"[10]"},{"why":"Provides the explicit SR1 superlinear analysis and the matrix-order lemmas that control the quasi-Newton metrics.","marker":"[49]"},{"why":"Established the first local explicit superlinear rate for SR1, the baseline this paper extends to the KL case.","marker":"[56]"},{"why":"Defines the nonsmooth KL inequality with desingularizing functions, the core assumption replacing strong convexity.","marker":"[6]"},{"why":"Introduces gradient-regularized Newton methods that motivate the Grad SR1 PQN variant.","marker":"[41]"}],"fun_headline_variants":["KL property speeds quasi-Newton to superlinear without convexity","First superlinear rates for regularized SR1 on nonconvex problems","Non-smooth nonconvex? KL property gives explicit superlinear rates","Quasi-Newton superlinear rates without strong convexity or line search","Regularized SR1 achieves superlinear rates via KL, no convexity"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"Each iteration must compute an exact global minimizer of a cubic-regularized proximal subproblem; for general nonsmooth $g$ no algorithm is supplied that can do this, so the non-asymptotic rates are not established for any implementable inexact version.","fun_headline_variants_meta":{"raw":{"variants":["KL property speeds quasi-Newton to superlinear without convexity","First superlinear rates for regularized SR1 on nonconvex problems","Non-smooth nonconvex? KL property gives explicit superlinear rates","Quasi-Newton superlinear rates without strong convexity or line search","Regularized SR1 achieves superlinear rates via KL, no convexity"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000816,"raw_usage":{"total_tokens":3674,"prompt_tokens":1144,"completion_tokens":2530,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":760,"completion_tokens_details":{"reasoning_tokens":2436}},"tokens_in":760,"tokens_out":2530,"duration_ms":17535,"temperature":1.0,"reasoning_tokens":2436,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T12:05:11.968272+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a KL function $F=g+f$ with $g=\\|x\\|_1$ and smooth $f$ satisfying Assumptions 1–2 with $\\phi(t)=ct^{1/2}$, run the Cubic SR1 PQN update (6) using a standard proximal gradient solver with a fixed tolerance for the cubic subproblem, and check whether $\\|F'(x_k)\\|$ obeys the bound (10) for all $k\\ge k_0$. A violation, or the need to solve the subproblem to machine precision to observe the bound, would show the theorem depends on exact subproblem minimization rather than on the structure analyzed.","supporting_citations":[{"cited_title":"Nesterov and B","cited_arxiv_id":null,"evidence_quote":"Provides cubic regularization and the Taylor-type bounds used in the descent estimates."},{"cited_title":"Bolte, S","cited_arxiv_id":null,"evidence_quote":"Gives the uniformized KL property that turns the local KL inequality into a global tool for non-asymptotic rates."},{"cited_title":"Rodomanov and Y","cited_arxiv_id":null,"evidence_quote":"Provides the explicit SR1 superlinear analysis and the matrix-order lemmas that control the quasi-Newton metrics."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Established the first local explicit superlinear rate for SR1, the baseline this paper extends to the KL case."},{"cited_title":"Bolte, A","cited_arxiv_id":null,"evidence_quote":"Defines the nonsmooth KL inequality with desingularizing functions, the core assumption replacing strong convexity."},{"cited_title":"Mishchenko, Regularized Newton method with global convergence, SIAM Journal on Op- timization, 33 (2023), pp","cited_arxiv_id":null,"evidence_quote":"Introduces gradient-regularized Newton methods that motivate the Grad SR1 PQN variant."}],"review_version":1}