{"id":"6ac26829-197b-475c-a56f-1de66e4c17c3","arxiv_id":"2511.10414","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"Descent methods obeying f(x_{k+1}) ≤ f(x_k) − ρ‖∇f(x_k)‖^θ converge linearly when θ equals the inverse KL exponent, with a unified rate/complexity analysis.","lead":"This paper analyzes a broad family of descent algorithms for nonconvex problems, where each step must decrease the objective by at least a constant times a power of the gradient norm. It shows convergence rates—including linear convergence when the exponent is matched to the Kurdyka–Łojasiewicz exponent—and gives iteration-complexity bounds.","discovery_kind":"unification","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Linear convergence for arbitrary KL exponents rests on unproved KL-exponent preservation and C^1 regularity of high-order Moreau envelopes imported from unpublished [21, Thm 3.9].","rationale":"The core DEAL analysis (Theorems 3.2–3.6) is internally coherent: the recurrence s_k^ς≤κ(s_k−s_{k+1}) with ς=ϑθ is applied correctly, the q>0 condition is forced by the existence of positive s_k, and the rate formulas follow from Fact 2.2. The numerical experiments are simple but not load-bearing. The central commercial claim—Boosted HiPPA attains linear convergence for arbitrary KL exponents—is, however, exactly as strong as [21, Theorem 3.9] plus the unstated displacement condition. The manuscript itself flags the C^1 assumption as a technicality and gives no proof of KL-exponent preservation; Corollary 4.11's one-line citation makes the dependency explicit. This is not an internal contradiction, and it is likely fixable by importing or proving the envelope calculus, so CONDITIONAL is the right verdict rather than REJECT. Since the reader's weakest assumption already identifies the KL-exponent/C^1 inheritance as the crux, my stress-test agrees and does not move the verdict.","tokens_in":21190,"tokens_out":19802,"duration_ms":201458,"concrete_test":"Independently re-derive the missing implication: for a proper lsc φ bounded below and satisfying KL at x̄ with exponent ϑ, prove from the definitions in §4.3 that for p=1/(1−ϑ) the high-order Moreau envelope φ_pγ is C^1 near x̄ and satisfies (φ_pγ(x)−φ_pγ(x̄))^ϑ ≤ τ_γ∥∇φ_pγ(x)∥ with finite τ_γ and some γ>0, and that q=1−σγ^{1/(p−1)}/(pτ_γ^θ)>0. Do not cite [21]. If the proof requires extra assumptions not present in Corollary 4.11, test a candidate outside them (e.g., φ(x)=−|x|^q, q∈(0,1), or a non-prox-regular lsc φ) to see whether the envelope's KL exponent changes or C^1 fails. Also check whether the line-search displacement bound in Theorem 3.3 follows for the κ_k selected by Algorithm 4; if not, the convergence-rate conclusion is not yet established.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Corollary 4.11 is the only result that delivers the paper's headline: Boosted HiPPA with p=1/(1−ϑ) converges linearly for arbitrary ϑ∈(0,1). Its proof is a single citation: 'The claim follows from Lemma 4.10 and [21, Theorem 3.9].' That citation is the sole source for the two properties Theorem 3.3 needs from f=φ_pγ: (i) φ_pγ ∈ C^1, and (ii) φ_pγ satisfies KL at the cluster point with exponent ϑ. The paper explicitly says (Section 4.3) 'To avoid technicalities, we assume φ_pγ ∈ C1 whenever differentiability is needed', and Fact 4.8 is also cited from [21,23]. Thus the main new result is not proved in this manuscript; it is delegated to an unpublished companion preprint, with no statement of the extra hypotheses (prox-regularity? weak convexity? small γ? bounded level sets?) or of how the KL constant τ_γ depends on γ and p. If the envelope's KL exponent is not exactly ϑ, or if C^1 requires γ so small that q=1−σγ^{1/(p−1)}/(pτ_γ^θ) is not positive, the choice p=1/(1−ϑ) does not yield θ=1/ϑ for the function actually being minimized, and the arbitrary-ϑ linear claim collapses to a conditional statement. A secondary unclosed step: the displacement condition ∥x_{k+1}−x_k∥≤c∥∇φ_pγ∥^{θ−1} assumed in Theorem 3.3 is not verified for Boosted HiPPA's line search with arbitrary d_k. The primary gap, however, is the imported envelope calculus.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces a generalized descent framework (DEAL), defined by the sufficient-decrease inequality f(x_{k+1}) ≤ f(x_k) − ρ‖∇f(x_k)‖^θ with θ > 1, and analyzes convergence, rates, and complexity under the Kurdyka–Łojasiewicz (KL) property. Section 3 proves, under explicit structural assumptions, that the sequence of gradients is summable, cluster points are critical, and—when the KL exponent ϑ and descent order θ are related—function values, gradient norms, and iterates converge linearly (θ = 1/ϑ) or sublinearly (θ > 1/ϑ); global KL is used to obtain global convergence to minimizers and iteration-complexity bounds. Section 4 instantiates DEAL with constant-step and Armijo line-search versions, and with boosted proximal-gradient and boosted high-order proximal-point methods. The headline claim is that Boosted HiPPA, with regularization order p = 1/(1−ϑ), achieves linear convergence for arbitrary KL exponent ϑ∈(0,1). Numerical experiments on inverse problems and LASSO illustrate the methods.","tokens_in":21713,"tokens_out":15169,"duration_ms":148829,"significance":"If fully established, the paper would provide a clean and reasonably general unification of several descent methods under a single KL-based rate theorem. The core Section 3 arguments are simple, mostly correct, and genuinely useful: the summability of gradient powers, the KL recurrence, and the explicit complexity bounds under global KL are valuable. The paper also gives explicit constants for many of the rates, which is helpful for reproducibility. However, the paper's distinguishing new result—linear convergence of Boosted HiPPA for arbitrary KL exponents—is not proved in this manuscript. It rests on unpublished companion-preprint results about high-order Moreau envelopes that are cited without hypotheses or proof, and the structural hypotheses needed to apply the main theorem to Boosted HiPPA are not verified. The general framework is a solid contribution, but the headline application needs substantial additional justification.","major_comments":[{"comment":"The headline claim—Boosted HiPPA converges linearly for arbitrary KL exponent ϑ—is not proved in this manuscript. The proof of Corollary 4.11 is a single citation to [21, Theorem 3.9], an unpublished same-author preprint. To apply Theorem 3.3 to f = φ_γ^p, one needs (i) φ_γ^p ∈ C^1 and (ii) φ_γ^p satisfies the KL inequality at the relevant cluster point with the same exponent ϑ and a usable constant τ_γ. Neither is established here; the paper explicitly says in Section 4.3 'To avoid technicalities, we assume φ_γ^p ∈ C1 whenever differentiability is needed', and Fact 4.8 also cites [21, 23]. No hypotheses on prox-regularity, weak convexity, admissible range of γ, or bounded level sets are stated, and the dependence of τ_γ on γ and p is not given. This is load-bearing because p = 1/(1−ϑ) is chosen exactly so that θ = p/(p−1) = 1/ϑ; if the envelope's KL exponent is not ϑ, or if C^1 regulari","section":"§4.3, Corollary 4.11"},{"comment":"Even granting the envelope calculus, Corollary 4.11 does not verify the structural hypotheses needed to invoke Theorems 3.2(d) and 3.3. First, Assumption II (existence of a convergent subsequence) is not implied by the DEAL descent inequality or by the KL property; without coercivity or bounded level sets, an unbounded sequence can have decreasing function values and vanishing gradients. Second, the displacement condition ‖x_{k+1}−x_k‖ ≤ c‖∇φ_γ^p(x_k)‖^{θ−1} is never checked for the Boosted HiPPA line search. With x_{k+1} = (1−κ_k)prox^p_{γφ}(x_k) + κ_k(x_k + d_k), we get ‖x_{k+1}−x_k‖ ≤ γ^{1/(p−1)}‖∇φ_γ^p(x_k)‖^{θ−1} + κ_k‖d_k‖; for arbitrary d_k and the 'largest κ' acceptance rule, the extra term κ_k‖d_k‖ need not be dominated by a multiple of ‖∇φ_γ^p(x_k)‖^{θ−1}. Corollary 4.11 therefore overclaims that all DEAL theorems hold for Boosted HiPPA without additional assumptions on d_k or","section":"§4.3, Algorithm 4 / Corollary 4.11"},{"comment":"Assumption II is nontrivial and should be highlighted as a limitation. Algorithm 1, as stated, can generate divergent sequences: inequality (11) only controls the decrease of f and the sum of ‖∇f(x_k)‖^θ; it does not imply boundedness of the iterates unless f has bounded sublevel sets or some coercivity is assumed. Thus Theorems 3.2(c)–(d), 3.3, 3.4(c), 3.6, and the corollaries inherit an unverified boundedness/continuity condition. For DEAL-C and DEAL-A the bounded-step structure makes this condition plausible under mild assumptions, but for Boosted HiPPA and Boosted PGA no argument is supplied. The phrase 'global convergence' should be qualified accordingly, or an explicit coercivity/level-set condition should be added to the instances where it is needed.","section":"§3, Assumption II and Theorem 3.2"},{"comment":"The acceptance inequality preceding Algorithm 4 requires σ < 1. Indeed, the exact decrease at the prox point is φ_γ^p(prox) = φ_γ^p(x_k) − (1/(pγ))‖x_k−prox‖^p = φ_γ^p(x_k) − (1/p)γ^{1/(p−1)}‖∇φ_γ^p(x_k)‖^{p/(p−1)}, so the claimed inequality with coefficient σγ^{1/(p−1)}/p is valid only if σ < 1. Algorithm 4 states σ ∈ (0, 1/(pγ)); if pγ < 1, this interval includes values of σ ≥ 1, for which the displayed descent inequality cannot hold and the backtracking loop may never terminate. The parameter range should be σ ∈ (0,1), or an equivalent condition ensuring σ < 1, and the statement of Lemma 4.10 should be updated accordingly.","section":"§4.3, Algorithm 4 initialization"}],"minor_comments":[{"comment":"The proof refers to 'from (40)', but at that point (40) is not yet defined; (40) is later used for BPGA. The reference should be to the line-search inequality introduced just above Algorithm 4, or a new equation number should be assigned.","section":"§4.3, Lemma 4.10 proof"},{"comment":"The bounds in (15) and (16) use f(x_0)−f(x̄) even though the linear-rate inequality is proved only for k ≥ k_0. This is harmless if one replaces x_0 by x_{k_0} or absorbs the finite initial segment into the constant, but the text should say so.","section":"§3, Theorem 3.3 proof"},{"comment":"The KL property for the Moreau envelope is asserted on {x : φ(x) ≤ φ(x_0)}, but the natural level set for the envelope is {x : φ_γ(x) ≤ φ_γ(x_0)}. The cited result [43, Remark 5.1] should be stated with its actual hypotheses, since the inclusion of level sets may require justification.","section":"§5.3, Remark 5.2"},{"comment":"The blanket statement 'To avoid technicalities, we assume φ_γ^p ∈ C1 whenever differentiability is needed' is too vague. The paper should specify whether C^1 regularity is global or on a neighborhood of the level set, and how γ is chosen relative to the problem data (e.g., weak-convexity constant).","section":"§4.3, general"},{"comment":"Reference [45] appears to contain a typo in the arXiv identifier ('1803.002259'); please verify. Some other references to unpublished arXiv preprints by the same authors ([21], [22], [23]) are used for crucial facts; if these remain unpublished, the main text should include the precise statements used.","section":"References"}],"recommendation":"major_revision","confidential_remarks":"The main risk is that the paper's distinguishing result is delegated to [21], an unpublished preprint by the same research group, and I could not verify the KL-exponent preservation and C^1 regularity of high-order Moreau envelopes. I would ask the authors either to include a self-contained proof or to restate the result as conditional on explicit hypotheses, and to verify the displacement condition for Boosted HiPPA. The general DEAL framework in Section 3 is sound and valuable; the revision should focus on the gap between that framework and the claimed arbitrary-ϑ linear convergence."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The one thing to know: the DEAL framework in Section 3 is a clean, correct unification of many descent methods under a single inequality, and the θ = 1/ϑ matching condition is the right way to state when linear convergence happens. The second: the paper's headline — Boosted HiPPA achieving linear convergence for arbitrary KL exponents — is not proved in this manuscript. Corollary 4.11's proof is one line: \"follows from Lemma 4.10 and [21, Theorem 3.9].\" That theorem lives in an unpublished same-author preprint, and the manuscript itself says, in Section 4.3, \"To avoid technicalities, we assume φ_γ^p ∈ C^1.\"\n\nI recomputed the core of Section 3. Theorem 3.3 is the standard KL recurrence from Fact 2.2 ([7, Lemma 1]) with ς = ϑθ; the linear case forces q > 0 for any non-terminating sequence, so the q-positivity sub-worry from the stress test does not bite. The sublinear exponents (17)–(19) and the complexity formulas in Theorem 3.6 check out. DEAL-C and DEAL-A are properly verified from the Hölder descent lemma with θ = 1 + 1/ν, and Remark 4.2 covers the displacement condition. As a unifying framework, the paper earns its place.\n\nThe soft spots, in proportion. (1) The load-bearing step for Corollary 4.11 is that the high-order Moreau envelope φ_γ^p is C^1 and inherits KL exponent ϑ from φ. Both come from [21, Theorem 3.9], with no statement here of the hypotheses (range of γ, prox-regularity or weak convexity, how the KL constant τ scales with γ and p). If the envelope's exponent is not exactly ϑ, then p = 1/(1−ϑ) does not give θ = 1/ϑ for the function actually minimized, and the \"arbitrary ϑ\" claim degrades to a conditional. The abstract and conclusion present it unconditionally. (2) The displacement condition in Theorem 3.3 is automatic for DEAL-C/A but not verified for Boosted HiPPA: only the prox term satisfies it, and the κ_k d_k term is unconstrained for arbitrary d_k. (3) Assumption II is disclosed but never derived; coercivity or bounded level sets would close that, minor. (4) The numerics are plots with no seeds, code, or data; fine as preliminary, but they do not validate the theory.\n\nThe stress-test concern lands on reading the paper. Not fatal: the fix is to prove or precisely import the envelope calculus and restrict the claims accordingly. Send it to referees — Section 3 deserves the time — and expect a heavy-revision report centered on Section 4.3.","headline":"The DEAL framework is a clean, correct unification with rates that check out; the 'linear for any KL exponent' headline is a one-line citation to an unpublished companion preprint.","tokens_in":22118,"tokens_out":17140,"would_cite":true,"duration_ms":162274,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C26","90C30","65K05"],"pacs":[],"model":"deepseek-v4-flash","headline":"Generalized descent converges linearly exactly when the descent order θ equals the reciprocal of the Kurdyka–Łojasiewicz exponent ϑ, and a boosted high-order proximal-point method achieves this for every ϑ.","keywords":["generalized descent","Kurdyka-Łojasiewicz inequality","linear convergence","KL exponent","Moreau envelope","high-order proximal point","iteration complexity","nonconvex optimization"],"falsifier":"Find a concrete semialgebraic KL function with known exponent ϑ whose high-order Moreau envelope φ_γ^p (with p = 1/(1−ϑ)) has a strictly smaller KL exponent, or where C^1 differentiability forces γ so small that the global descent inequality (11) fails; either observation would disprove the claim that boosted HiPPA converges linearly for all ϑ.","tokens_in":21119,"feed_emoji":"📉","tokens_out":6224,"duration_ms":60416,"temperature":0.7,"pith_summary":"This paper analyzes a broad family of 'generalized descent' methods that reduce a smooth, possibly nonconvex objective by at least ρ times the θ-th power of the gradient norm at each step. Its central result is a sharp threshold: such a method converges linearly if and only if the descent order θ equals the reciprocal of the Kurdyka–Łojasiewicz (KL) exponent ϑ of the objective; when θ exceeds 1/ϑ, convergence is sublinear with explicit polynomial rates. The authors show that several classical algorithms — constant step-size gradient descent, Armijo line search, proximal gradient, and high-order proximal-point — all fit this one inequality, so one theorem governs their rates. In particular, by choosing the regularization power p = 1/(1−ϑ), the boosted high-order proximal-point method converges linearly for arbitrary KL exponents, a result the paper says is new even in the smooth setting. Under a global KL inequality the same framework yields convergence to global minimizers and O(log(1/ε)) iteration complexity.","feed_headline":"Descent order 1/ϑ unlocks linear convergence for KL functions","feed_subtitle":"For any Kurdyka–Łojasiewicz exponent, the right regularization power makes high-order proximal point contract linearly.","key_machinery":"The DEAL framework is built on a single sufficient-decrease inequality, f(x_{k+1}) ≤ f(x_k) − ρ‖∇f(x_k)‖^θ, together with the step-size control ‖x_{k+1}−x_k‖ ≤ c‖∇f(x_k)‖^{θ−1}. The KL inequality (f(x)−f(x̄))^ϑ ≤ τ‖∇f(x)‖ converts these into the scalar recurrence (s_k)^{ϑθ} ≤ (τ^θ/ρ)(s_k − s_{k+1}) for the function gap s_k; a known lemma (Fact 2.2) then turns this recurrence into linear or sublinear estimates depending on whether ϑθ equals or exceeds 1. The high-order Moreau envelope and its gradient formula (33) are the bridge that lets nonsmooth objectives and high-order proximal-point methods enter the same framework.","core_discovery":"The central claim is Theorem 3.3: for a sequence satisfying the generalized descent inequality f(x_{k+1}) ≤ f(x_k) − ρ‖∇f(x_k)‖^θ together with the relative-error bound ‖x_{k+1}−x_k‖ ≤ c‖∇f(x_k)‖^{θ−1}, if the objective satisfies the KL inequality at a cluster point with exponent ϑ, then θ = 1/ϑ gives linear convergence of the function gap, the gradient norm, and the iterate distance to 0, with rate q = 1 − ρ/τ^θ; while θ > 1/ϑ gives sublinear rates with explicit polynomial exponents. The paper further claims that the boosted high-order proximal-point method, by setting p = 1/(1−ϑ), achieves linear convergence for arbitrary KL exponent ϑ ∈ (0,1) — a result the authors state is new even in th","pith_inferences":["A testable extension: for any problem where the KL exponent and Hölder smoothness satisfy ϑ = ν/(1+ν) — as the paper proves for least-p inverse problems — both DEAL-C and DEAL-A automatically sit at the linear-convergence threshold θ = 1/ϑ; checking this identity on other Hölder-smooth KL functions would show whether it is a general design principle.","If the envelope-inheritance result is confirmed, the same θ–ϑ matching could guide the design of inexact or stochastic variants of DEAL: keeping the effective descent order matched to the smoothed surrogate's exponent should preserve linear convergence.","The numerical experiments show heuristic choices of the generalized-descent parameter β (e.g., −0.2) outperforming the theoretically motivated value; a systematic study of the rate behavior away from the exact threshold θ = 1/ϑ could explain this gap and yield better practical parameter rules."],"forward_implications":["For any DEAL instance — constant step-size, Armijo line search, proximal gradient, or high-order proximal-point — global convergence, convergence rates, and complexity are all governed by the same θ–ϑ relation, so no per-algorithm rate analysis is needed.","Linear convergence is achievable for KL exponents beyond the classical ϑ = 1/2 case; the identity θ = 1/ϑ extends linear rates to all ϑ ∈ (0,1).","Boosted HiPPA with p = 1/(1−ϑ) is claimed to be the first high-order proximal-point scheme with linear convergence for arbitrary KL exponent, a result the paper says holds even for smooth objectives.","Under a global KL inequality, DEAL converges to a global minimizer and reaches ε-accuracy in function value, gradient norm, or iterate distance within O(log(1/ε)) iterations; without the KL property, the gradient-norm complexity is only O(ε^{−θ}).","The framework applies to nonsmooth objectives through smoothing (forward-backward and Moreau envelopes), with the smooth surrogate inheriting the KL exponent in the analyzed cases."],"fun_headline_variants":["θ = 1/ϑ: the precise condition for linear KL convergence","Boosted prox point: linear convergence for all KL exponents","One descent order rule unifies KL convergence rates","New result: arbitrary KL exponent now admits linear rates","Set descent order to 1/ϑ for linear speed on KL"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The headline result that boosted high-order proximal-point converges linearly for any KL exponent rests on the paper's assumption — deferred to a companion preprint — that the high-order Moreau envelope is C^1 and inherits exactly the same KL exponent ϑ as the original function.","fun_headline_variants_meta":{"raw":{"variants":["θ = 1/ϑ: the precise condition for linear KL convergence","Boosted prox point: linear convergence for all KL exponents","One descent order rule unifies KL convergence rates","New result: arbitrary KL exponent now admits linear rates","Set descent order to 1/ϑ for linear speed on KL"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000325,"raw_usage":{"total_tokens":1693,"prompt_tokens":813,"completion_tokens":880,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":557,"completion_tokens_details":{"reasoning_tokens":795}},"tokens_in":557,"tokens_out":880,"duration_ms":8845,"temperature":1.0,"reasoning_tokens":795,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-03T22:26:10.619132+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Find a concrete semialgebraic KL function with known exponent ϑ whose high-order Moreau envelope φ_γ^p (with p = 1/(1−ϑ)) has a strictly smaller KL exponent, or where C^1 differentiability forces γ so small that the global descent inequality (11) fails; either observation would disprove the claim that boosted HiPPA converges linearly for all ϑ.","supporting_citations":[],"review_version":1}