{"id":"c45d8d7e-8d4a-4270-be2d-811f7fa4688c","arxiv_id":"2411.12376","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":1,"one_line_summary":"Mean-type nonmonotone proximal gradient methods converge globally with Kurdyka-Lojasiewicz rates under only local Lipschitz continuity of the smooth gradient.","lead":"An optimization method that deliberately allows the objective value to rise temporarily is proved to converge to a solution of challenging nonsmooth problems, without requiring the usual global smoothness bound. The proof gives the first global convergence and speed guarantees for this method that match the safer monotone version.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified; proof chain is internally consistent and the conditional subsequence assumption is explicit, not a hidden gap.","rationale":"I checked the main proof chain. Lemma 4.1 is valid: the contradiction argument with trial stepsizes gamma_k/beta_k correctly uses local Lipschitz continuity of f' and boundedness of f on B_rho(x*). Lemma 4.2 works because l(k)-k=m-1 is a fixed constant, so all terms in alpha can be driven to zero as k0 -> infinity. Lemma 4.4's two cases are correctly handled; the stated hypotheses are slightly weaker than what Case 2 needs (x_k in B_alpha is required to apply KL), but the induction in Theorem 4.5 supplies x_j in B_alpha at every application, so the proof as used is sound. The induction in Theorem 4.5 jointly proves x_k in B_alpha and summability of the distances, yielding a Cauchy sequence; the algebra with the constant m is consistent. Theorem 4.6 correctly transfers rates from R_k to x_k using the Cauchy-sum bound and Lemma 2.2, with the stated exponents. The only real caveats are the explicit conditional nature of the subsequence assumption and the external Theorem 3.4, both of which the reader flagged. Neither invalidates the central claim as stated, so the verdict should remain ACCEPT.","tokens_in":19031,"tokens_out":20148,"duration_ms":188261,"concrete_test":"Verify Theorem 3.4 by an independent proof: starting from Assumption 3.1 and the Algorithm 3.2 update rules, show directly that R_k is monotonically decreasing to psi(x*) for every accumulation point x*, without invoking any global Lipschitz condition or boundedness of iterates. If such a proof cannot be reconstructed from [14], the paper should include it as a lemma; this check settles whether the imported result is sound in the stated generality.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I found no internal inconsistency in the proof chain. Theorems 4.5 and 4.6 deliver exactly what they state: whole-sequence convergence and rates conditional on a given convergent subsequence {x_k}_K and KL at its limit. Assumption 3.1 does not by itself guarantee such a subsequence, so the advertised removal of 'a priori boundedness' is a weakening of the hypothesis, not a proof of boundedness; this is explicitly acknowledged in the theorem statements. The only genuinely external load-bearing ingredient is Theorem 3.4(c) from [14] (monotone convergence of R_k to psi(x*)), which is imported without proof; the subsequent Lemmas 4.2-4.6 and Theorem 4.5 all use R_k -> psi(x*) and R_k - psi(x*) >= 0. If the proof of that statement in [14] required a global Lipschitz condition or bounded iterates, the present proof would inherit an unstated assumption. I see no evidence of that in the text, but the dependency is real and unverified here.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the composite minimization problem min ψ=f+φ with f continuously differentiable and φ proper lower semicontinuous extended-valued, using a nonmonotone proximal gradient method with the Zhang–Hager mean-type reference rule (Algorithm 3.2). Under Assumption 3.1 (ψ bounded below on dom(φ), φ bounded below by an affine function, and f' locally Lipschitz), the method has a finite stepsize inner loop and the iterate gaps satisfy ‖x_{k+1}−x_k‖→0. The main results, Theorems 4.5 and 4.6, state that if a subsequence {x_k}_K converges to some x* and ψ satisfies the Kurdyka–Łojasiewicz property at x*, then the entire sequence converges to x*; moreover, for desingularization χ(t)=ct^κ, the reference values R_k converge Q-linearly and the iterates x_k R-linearly when κ∈[1/2,1), and both converge polynomially at the stated rates when κ∈(0,1/2). The proof develops a stepsize lower-bound lemma (Lemma 4.1) using only local Lipschitz continuity, a limiting-subgradient bound (Lemma 4.3), and a nonmonotone adaptation of the summable-distance argument from [30].","tokens_in":19128,"tokens_out":10331,"duration_ms":91983,"significance":"If the results hold, they represent a meaningful advance in the convergence theory of nonmonotone proximal gradient methods: they show that the mean-type nonmonotone rule inherits essentially the same global and rate-of-convergence properties as its monotone counterpart without a global Lipschitz assumption and without an a priori bound on the iterates. The proofs are detailed and transparent, with no fitted constants or tuned parameters; all algorithmic parameters are interval-constrained inputs. The paper is honest about the conditional nature of its main theorems: convergence is not asserted unconditionally, but explicitly conditioned on the existence of a convergent subsequence and on the KL property at its limit. The rate results match the known monotone theory, which further supports the plausibility of the claims. The only external load-bearing ingredient is Theorem 3.4(c) imported from [14], whose exact hypotheses should be made explicit.","major_comments":[],"minor_comments":[{"comment":"Theorem 3.4(c), the monotone convergence of {R_k} to ψ(x*), is imported from [14] and is used in Lemmas 4.2, 4.4, and Theorem 4.6. Please state the precise result in [14] that implies this, and explicitly confirm that it holds under exactly Assumption 3.1 without additional hypotheses such as an a priori bound on the iterates or a global Lipschitz condition.","section":"Section 4, Theorem 3.4"},{"comment":"In the proof of Lemma 4.1, the phrase 'the boundedness condition from Assumption 3.1 for φ' is imprecise: Assumption 3.1(b) states that φ is bounded below by an affine function, not that φ is bounded. This wording should be changed to avoid confusion.","section":"Section 4, proof of Lemma 4.1"},{"comment":"In the proof of Lemma 4.4, after applying the inequality √(x+y) ≤ √x + √y, the expression √(R_k − R_{k+n}) appears; this is a typo and should read √(R_k − R_{k+m}), consistent with the definition of m.","section":"Section 4, proof of Lemma 4.4"},{"comment":"The step from s_{k+1} ≤ (1−p_min)s_k + p_min a (s_k−s_{k+1})^{1/(2(1−κ))} to s_k ≤ (1/p_min + a)(s_k−s_{k+1})^{min{1,1/(2(1−κ))}} is presented as 'This implies'; expanding this rearrangement would improve readability, since the exponent manipulation is central to the subsequent application of Lemma 2.2.","section":"Section 4, proof of Theorem 4.6"},{"comment":"The abstract and introduction state that the results are obtained 'without an a priori knowledge of the boundedness of the iterates'; this is accurate, but readers should be reminded that the theorems are conditional on the existence of a convergent subsequence. The theorem statements are clear, but an explicit sentence in the abstract would prevent an overstrong reading.","section":"Abstract and Introduction"}],"recommendation":"minor_revision","confidential_remarks":"This is a carefully written theoretical paper whose central proofs appear sound. The main concern is the unverified dependency on Theorem 3.4(c) from [14]; the authors should add a precise statement or short proof so that no hidden assumption is inherited. The paper contains no numerical experiments, which is appropriate for a pure convergence-theory contribution. I recommend minor revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper does what it says: it gives the first KL-based whole-sequence convergence and rate results for the mean-type nonmonotone proximal gradient method when f' is only locally Lipschitz and the iterates are not assumed bounded in advance. That is a genuine gap, and the proof is a careful adaptation of the monotone machinery from Jia–Kanzow–Mehlitz and the recent framework of Qian et al. The main ingredients are Lemma 4.1, which shows accepted stepsizes stay bounded away from zero near an accumulation point using only local Lipschitzness, and Lemma 4.3, which bounds the limiting subgradient by the step norm. The induction argument in Theorem 4.5 is intricate but readable, and the rate results in Theorem 4.6 match what one would expect from the monotone theory. I followed the proof through the key steps and did not find an internal contradiction. Credit is due for stating the assumptions explicitly and for not hiding the conditional nature of the result.\n\nThe soft spots are real but not disqualifying. First, the whole-sequence convergence is conditional on the existence of a convergent subsequence with limit x*; the paper does not prove boundedness. That is clearly stated in Theorem 4.5, so it is not a hidden gap, but it does mean the headline “no a priori boundedness” should be read as “boundedness replaced by a subsequential convergence assumption.” Second, Theorem 3.4(c) from De Marchi, that R_k converges monotonically to psi(x*), is load-bearing and imported without proof. The authors note it follows from [14], and I see no evidence of a hidden global Lipschitz requirement there, but the dependency is substantial. Third, Lemma 4.4's stated hypotheses are slightly weaker than what Case 2 uses; the applications in Theorem 4.5 do supply the needed condition, so this is a minor presentation issue, not a mathematical flaw.\n\nThis paper is for researchers working on nonconvex, nonsmooth optimization and KL-based convergence theory. It deserves a serious referee: the claims are precise, the proof is detailed, and the result closes a known gap. I would send it out rather than desk reject, and I would expect acceptance after minor revisions to clarify the conditional nature of the main theorem and the reliance on [14].","headline":"Solid theory paper: proves KL-based whole-sequence convergence and rates for mean-type nonmonotone proximal gradient without global Lipschitz or bounded iterates; main caveat is the conditional subsequence assumption and an imported lemma.","tokens_in":19751,"tokens_out":1254,"would_cite":true,"duration_ms":14208,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["49J52","90C30"],"pacs":[],"model":"deepseek-v4-flash","headline":"A nonmonotone proximal gradient method converges with KL rates without global Lipschitz assumptions.","keywords":["composite optimization","nonsmooth optimization","proximal gradient method","Kurdyka–Łojasiewicz property","nonmonotone line search","global convergence","linear convergence","rate of convergence"],"falsifier":"Run Algorithm 3.2 with $f(x)=e^x+x^4/4$, $\\varphi(x)=|x|^{1/2}$, and parameters chosen inside the allowed ranges, watching whether the iterates with one finite accumulation point ever split toward a second accumulation point. Observing two distinct accumulation points would falsify Theorem 4.5, while observing convergence in all such runs would support it.","tokens_in":18714,"feed_emoji":"📉","tokens_out":9041,"duration_ms":85636,"temperature":0.7,"pith_summary":"This paper proves that the mean-type nonmonotone proximal gradient method, applied to a composite objective $\\psi=f+\\varphi$, converges to a single limit point whenever one accumulation point satisfies the Kurdyka--Lojasiewicz property, and it does so without requiring the gradient of $f$ to be globally Lipschitz or the iterates to be bounded in advance. Previously, whole-sequence convergence and rate guarantees of this kind were available only for monotone stepsize rules or under stronger assumptions. The proof shows that the nonmonotone reference values $R_k$ decrease monotonically and control the inter-iterate gaps, and that the KL property at an accumulation point forces the whole sequence to be a Cauchy sequence. With a power desingularization $\\chi(t)=ct^\\kappa$, the method then converges Q-linearly for the reference values and R-linearly for the iterates when $\\kappa\\in[1/2,1)$, and polynomially when $\\kappa\\in(0,1/2)$. If correct, nonmonotone proximal gradient methods inherit the same global convergence guarantees as their monotone counterparts, which matters because nonmonotone stepsizes often take larger steps.","feed_headline":"Nonmonotone proximal gradient now gets full convergence under KL","feed_subtitle":"No global Lipschitz or bounded iterates needed; a single KL point forces full convergence with rates.","key_machinery":"The mean-type nonmonotone rule maintains reference values $R_{k+1}=(1-p_{k+1})R_k+p_{k+1}\\psi(x_{k+1})$ with $p_{k+1}\\ge p_{\\min}>0$, so that $\\{R_k\\}$ is monotonically decreasing even though $\\{\\psi(x_k)\\}$ is not. The gap $\\Xi_{k-1}=\\sqrt{R_{k-1}-R_k}$ bounds the step length $\\|x_k-x_{k-1}\\|$ up to a constant, and a fixed memory window of length $m$ chosen from $p_{\\min}$ keeps the KL-based recursion finite. The KL inequality, applied to the reference values rather than directly to the function values, yields a telescoping bound on sums of $\\Xi_j$; that bound makes the iterates a Cauchy sequence without any global Lipschitz constant. A separate local argument keeps the stepsizes $\\gamma_k$ bounded away from zero near the accumulation point using only local Lipschitz continuity of $f'$.","core_discovery":"The central claim is Theorem 4.5 and Theorem 4.6: under Assumption 3.1 (the objective is bounded below, $\\varphi$ is bounded below by an affine function, and $f'$ is locally Lipschitz), if a subsequence of iterates generated by Algorithm 3.2 converges to $x^*$ and $\\psi$ satisfies the Kurdyka--Lojasiewicz property at $x^*$, then the whole sequence $\\{x_k\\}$ converges to $x^*$. Moreover, when the desingularization function is $\\chi(t)=ct^\\kappa$, the reference values $R_k$ converge Q-linearly to $\\psi(x^*)$ and the iterates converge R-linearly to $x^*$ for $\\kappa\\in[1/2,1)$, while for $\\kappa\\in(0,1/2)$ the stated polynomial bounds $R_k-\\psi(x^*)\\le\\eta_1 k^{-1/(1-2\\kappa)}$ and $\\|x_k-x^*\\|\\le\\eta_2 k^{-\\kappa/(1-2\\kappa)}$ hold. This is the first whole-sequence and rate result for a nonmonotone proximal gradient method that does not assume a global Lipschitz gradient or an a priori bound on the iterates.","pith_inferences":["A natural extension outside the paper's scope is to add coercivity or bounded-level-set conditions that guarantee the existence of a convergent subsequence, since the theorem itself only applies once such a subsequence exists.","The fixed memory length $m$ grows as $p_{\\min}$ shrinks, so tuning $p_{\\min}$ may trade off larger nonmonotone steps against longer KL windows; this is a quantitative prediction that could be tested numerically on sparse-regression problems.","The same reference-value recursion may extend to other nonmonotone first-order algorithms, such as inertial or Bregman proximal variants, whenever their reference values decrease monotonically; this is an extrapolation the paper does not make."],"forward_implications":["Nonmonotone proximal gradient methods with the mean-type rule now carry the same whole-sequence convergence guarantee as monotone methods once the KL property holds at one accumulation point.","The rate dichotomy is explicit: $\\kappa\\in[1/2,1)$ gives Q-linear convergence of $R_k$ and R-linear convergence of $x_k$, while $\\kappa\\in(0,1/2)$ gives the polynomial estimates $k^{-1/(1-2\\kappa)}$ and $k^{-\\kappa/(1-2\\kappa)}$.","No global Lipschitz constant of $f'$ has to be known or estimated; only local Lipschitz continuity is used, so the theory covers objectives like exponentials and higher-degree polynomials.","The result applies to the generalized projected gradient method for minimization over a nonempty closed set $S$ that is not necessarily convex, with the projection possibly set-valued.","If a generated sequence has any accumulation point satisfying KL, the whole sequence converges to that point; in particular, two distinct accumulation points cannot both carry the KL property."],"supporting_citations":[{"why":"Supplies the mean-type nonmonotone proximal gradient method in Algorithm 3.2 and the subsequential convergence theorem that the paper's whole-sequence argument builds on.","marker":"[14]"},{"why":"Gives the monotone proximal gradient rate-of-convergence analysis under the KL property without global Lipschitz assumptions, which Theorem 4.6 adapts to the nonmonotone setting.","marker":"[19]"},{"why":"Establishes the local-Lipschitz-based stepsize lower bound and stationarity tools for nonmonotone proximal gradient methods used in Lemma 4.1.","marker":"[21]"},{"why":"Provides the fixed-window nonmonotone convergence technique based on sums of $\\Xi_j$ that is refined here to avoid boundedness assumptions.","marker":"[30]"},{"why":"Introduces the mean-type nonmonotone line search and the recursion for the reference value $R_k$ used throughout the method.","marker":"[33]"},{"why":"Supplies Lemma 2.2, the elementary rate lemma that converts the recursion inequality into linear or polynomial convergence rates.","marker":"[1]"}],"fun_headline_variants":["Nonmonotone proximal gradient converges without global Lipschitz","KL property alone suffices for nonmonotone proximal gradient convergence","No global Lipschitz needed: nonmonotone proximal gradient converges","First full convergence result for nonmonotone proximal gradient under KL","Nonmonotone proximal gradient matches monotone convergence under KL"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The argument assumes that some subsequence of the iterates already converges to a finite limit point $x^*$ at which the Kurdyka--Lojasiewicz property holds; if the iterates drift to infinity without an accumulation point, the theorem says nothing and the paper does not prove boundedness.","fun_headline_variants_meta":{"raw":{"variants":["Nonmonotone proximal gradient converges without global Lipschitz","KL property alone suffices for nonmonotone proximal gradient convergence","No global Lipschitz needed: nonmonotone proximal gradient converges","First full convergence result for nonmonotone proximal gradient under KL","Nonmonotone proximal gradient matches monotone convergence under KL"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000745,"raw_usage":{"total_tokens":3360,"prompt_tokens":1024,"completion_tokens":2336,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":640,"completion_tokens_details":{"reasoning_tokens":2246}},"tokens_in":640,"tokens_out":2336,"duration_ms":13769,"temperature":1.0,"reasoning_tokens":2246,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T17:38:33.477828+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Algorithm 3.2 with $f(x)=e^x+x^4/4$, $\\varphi(x)=|x|^{1/2}$, and parameters chosen inside the allowed ranges, watching whether the iterates with one finite accumulation point ever split toward a second accumulation point. Observing two distinct accumulation points would falsify Theorem 4.5, while observing convergence in all such runs would support it.","supporting_citations":[{"cited_title":"Proximal gradient methods beyond monoto ny","cited_arxiv_id":null,"evidence_quote":"Supplies the mean-type nonmonotone proximal gradient method in Algorithm 3.2 and the subsequential convergence theorem that the paper's whole-sequence argument builds on."},{"cited_title":"A nonmonotone line search tech nique and its ap- plication to unconstrained optimization","cited_arxiv_id":null,"evidence_quote":"Introduces the mean-type nonmonotone line search and the recursion for the reference value $R_k$ used throughout the method."},{"cited_title":"Ac celerating the DC al- gorithm for smooth functions","cited_arxiv_id":null,"evidence_quote":"Supplies Lemma 2.2, the elementary rate lemma that converts the recursion inequality into linear or polynomial convergence rates."}],"review_version":1}