{"id":"cc02a527-71e2-4c6e-bdfd-bd03131f5f6e","arxiv_id":"2411.19256","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Nonmonotone proximal gradient methods with average or max line search converge, with rates, under local gradient Lipschitz continuity and the Kurdyka-Lojasiewicz property, without boundedness of iterates.","lead":"This paper proves that two nonmonotone proximal gradient algorithms, using average line search and max line search, converge to stationary points of composite nonsmooth optimization problems when only local Lipschitz continuity of the gradient and the Kurdyka-Lojasiewicz property are assumed, without requiring bounded iterates.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 3.6 asserts k0 lies in a specific index set without proof; in the monotone limit p_k=1 the asserted S-membership fails, so the index-splitting bound behind Theorem 3.8 is unproven.","rationale":"The reader's weakest_assumption identifies the same load-bearing defect: Lemma 3.6 asserts a membership of k0 in an index set needed for the summation argument in Theorem 3.8, but the proof never establishes that membership. My reading of the manuscript confirms this. In the monotone limit p_k=1, the set S defined in (3.14) is empty for the allowed parameter range, directly refuting Lemma 3.6 as stated; if the authors intended the complement, the proof is still incomplete because no argument shows that all sufficiently large indices cannot lie in S. This is the central point on which global convergence depends: the induction in Theorem 3.8 proves (b) by splitting indices according to S and S^c, and the transition (3.21)-(3.27) uses the special role of k0 in this split. Without a valid k0 membership, the finite-length inequality (3.19) does not follow, so the Cauchy property and thus convergence of the entire sequence are unsupported. The theorem may be true and patchable, but as written the gap is load-bearing. I therefore keep the reader's CONDITIONAL verdict: the work is plausible and likely fixable, but the proof as it stands is incomplete. My agreement is 'agree' because the reader and I pinpoint the same unverified selection of k0, even if the set name may be ambiguous between S and its complement.","tokens_in":24006,"tokens_out":11699,"duration_ms":88640,"concrete_test":"Run Algorithm 1 on f(x)=x^2/2, g=0 with p_k=1, delta=1/2, gamma_min=1, x0=2. The subproblem yields x_{k+1}=x_k(1-1/gamma_k) with gamma_k>=1, so Phi_{k+1}=q(x_{k+1}) and q(x_k)-Phi_{k+1}=x_k^2(2/gamma_k-1/gamma_k^2)/2, while (mu/2)||x_{k+1}-x_k||^2=mu*x_k^2/(2*gamma_k^2). For mu<=delta*gamma_min/2=1/4, the S-membership inequality q(x_k)-Phi_{k+1} <= mu/2*||x_{k+1}-x_k||^2 is equivalent to 2*gamma_k-1 <= mu, impossible for gamma_k>=1. Hence S is empty and Lemma 3.6's asserted k0 in S fails. If the intended claim is k0 in the complement of S, perform the symmetric check with a nonmonotone realization, e.g. p_k=1/2 and a small discontinuous perturbation of g, and verify whether q(x_k)-Phi_{k+1} <= mu/2*||x_{k+1}-x_k||^2 holds for all large k, which would place all sufficiently large indices in S and contradict the complement membership.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The convergence proof of Theorem 3.8 hinges on Lemma 3.6, which must produce an index k0 in K and in the set used to split summation in (3.21)-(3.27). The proof only chooses k0 in K sufficiently large to make alpha<1/2 and never verifies the required membership. This gap is not cosmetic. In the monotone limit p_k=1, which is permitted since pmin <= 1, Phi_{k+1}=q(x_{k+1}), and the acceptance criterion (3.2) gives q(x_k)-Phi_{k+1}=q(x_k)-q(x_{k+1}) >= delta*gamma_k/2*||x_{k+1}-x_k||^2 >= delta*gamma_min/2*||x_{k+1}-x_k||^2. For mu <= delta*gamma_min/2, every index satisfies q(x_k)-Phi_{k+1} > mu/2*||x_{k+1}-x_k||^2, so the set S defined in (3.14) is empty and no k0 in S exists. Conversely, if Lemma 3.6 intended k0 to lie in the complement of S, as the equality in (3.21) suggests, nothing in the argument rules out all sufficiently large indices belonging to S: q(x_k)-Phi_{k+1} can be negative or decay faster than ||x_{k+1}-x_k||^2. Under either reading, the membership assertion is unsupported. Equation (3.21) explicitly uses the membership of k0 to drop or retain the first summation term, and adding (3.21) with (3.27) is what produces the finite-length bound (3.19). Without a valid k0 in the prescribed set, the Cauchy-sum argument of Theorem 3.8 is not established, and Theorem 3.9 inherits this gap since it relies on the same convergence framework while referring to [18] for rates with a different partition.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies two nonmonotone proximal gradient methods for composite minimization: Algorithm 1 with the Zhang--Hager average line search and Algorithm 2 with the Grippo--Lampariello--Lucidi max line search. Under a local Lipschitz continuity assumption on the gradient of the smooth part, a coercivity/lower-boundedness condition, and the Kurdyka--Łojasiewicz (KL) property at an accumulation point, the authors claim global convergence of the entire iterate sequence and Q-/R-linear or sublinear rates depending on the KL exponent (Theorems 3.8, 3.9, 4.8, 4.9). The proofs proceed by partitioning the iteration indices into two sets, one of which is meant to provide a sufficient decrease, and then deriving a finite-length (Cauchy) bound. The paper explicitly positions its index-partitioning strategy as an alternative to the concurrent work [18] and claims the convergence theory is independent of the specific partitioning.","tokens_in":24410,"tokens_out":7617,"duration_ms":62301,"significance":"If the claims were fully established, they would significantly extend the recent theory of proximal gradient methods without global Lipschitz assumptions to nonmonotone variants, and would remove the auxiliary-sequence and bounded-subdifferential requirements of earlier work in [26]. The observation that different index partitionings can lead to the same convergence conclusions is conceptually valuable. However, the main convergence proof relies on an existence assertion in Lemma 3.6 that is not proved and is in fact false in a permitted limiting case; a similar unverified membership appears in Lemma 4.5 for the max line search. Several key lemmas and the rate theorem are also deferred to the concurrent reference [18], leaving the central claims not fully self-contained. The manuscript is therefore not yet acceptable in its present form.","major_comments":[{"comment":"Lemma 3.6 asserts the existence of a sufficiently large k0 ∈ K ∩ S with α < 1/2, where S is defined in (3.14). The proof only selects k0 ∈ K large enough to make the right-hand side of (3.15) small; it never verifies that k0 belongs to S. This is not a cosmetic omission: in the permissible monotone limit p_k = 1, the acceptance criterion (3.2) gives q(x_k) − Φ_{k+1} = q(x_k) − q(x_{k+1}) ≥ δγ_k/2 ‖x_{k+1} − x_k‖² ≥ δγ_min/2 ‖x_{k+1} − x_k‖². Since µ ∈ (0, δp_minγ_min/2] and p_min = 1, any µ < δγ_min/2 makes the defining inequality of S fail for every k, so S is empty; even for µ = δγ_min/2, S is empty whenever γ_k > γ_min infinitely often. The membership of k0 in S is load-bearing: the summation identities in (3.21) and (3.27) explicitly use 'k0 ∈ S' to combine the index sums, and the finite-length bound (3.19) and the induction in Theorem 3.8 depend on that combination. Without a valid k0 ∈ S, the proof of Theorem 3.8 is not established, and Theorem 3.9 inherits the gap.","section":"Lemma 3.6, eqs. (3.14)--(3.15)"},{"comment":"Lemma 4.5 for the max line search displays the same structural gap as Lemma 3.6. The lemma states that there is a sufficiently large k0 ∈ K ∩ K with α < 1/2, where K is the set defined in (4.4). The proof only argues that a sufficiently large index in the subsequence K makes ‖x_{k0} − x̄‖, q(x_{l(k0)}) − q(x̄), and q(x_{l(k0−m−1)}) − q(x̄) small, and concludes α < 1/2. It never proves that k0 lies in the set K of (4.4). This membership is used later in Theorem 4.8: the base case of the induction relies on 'k0 ∈ K' to derive the inequality displayed after (4.14), and the subsequent case analysis splits on K. As written, Lemma 4.5 does not support that use, so the proof of Theorem 4.8 is incomplete.","section":"Lemma 4.5, eqs. (4.4) and (4.8)"},{"comment":"Several central proof components are omitted or deferred to the concurrent reference [18]. Lemma 3.7, which provides the subdifferential bound dist(0, ∂q(x_{k+1})) ≤ (γ̄_ρ + L_ρ)‖x_{k+1} − x_k‖, is stated with 'The proof is omitted because it is similar to [18, Lemma 4.3]'. Theorem 3.9, the advertised rate-of-convergence result for the average line search, is stated with 'Readers may find more details for the proof in [18, Theorem 4.6]'. A journal submission should be verifiable on its own; citing a concurrently posted preprint for a central rate theorem is not a substitute for a complete proof, especially because the partitioning in [18] differs from the one in (3.14), so it is not automatic that the rate argument transfers. The same concern applies to Lemma 3.4, whose proof is also omitted. This makes the paper non-self-contained at precisely the points that support the main claims.","section":"Lemma 3.7 and Theorem 3.9"}],"minor_comments":[{"comment":"There are several typographical errors, for example 'Cauthy' at the end of the proof of Theorem 4.8 should be 'Cauchy', 'disingularizatioon' in the proof of Lemma 3.6 should be 'desingularization', 'replies heavily' in the Introduction should be 'relies heavily', and 'imediately' in the proof of Theorem 3.5 should be 'immediately'.","section":"Throughout"},{"comment":"The symbol K is overloaded: it denotes the index set of a converging subsequence, e.g., {x_k}_{k∈K}, and also the newly defined set in (4.4). In Lemma 4.5 and Theorem 4.8 this double use is confusing, especially in expressions such as k0 ∈ K ∩ K; a different symbol for at least one of the two index sets would improve readability.","section":"Section 4, eq. (4.4)"},{"comment":"The proof of Proposition 4.4 sets c := 1/‖x_{l(k̄+1)} − x_{l(k̄+1)−1}‖ without addressing the possibility that the denominator is zero; the argument should either rule out that case or handle it separately.","section":"Proposition 4.4"}],"recommendation":"major_revision","confidential_remarks":"The paper's central convergence theorems for the average-line-search method rely on an existence claim about the index set S that is unproven and fails in the monotone limit, and the corresponding max-line-search lemma has the same deficiency. These are fixable in principle—for example by redefining the partition or choosing µ differently—but the current text does not support the main theorem. The paper also leans heavily on the concurrent preprint [18] for proof details, which weakens its archival independence. The max-line-search section appears to be the more novel contribution; the average-line-search section largely overlaps with [18]."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know: the max line search full-sequence convergence under local Lipschitz continuity and KL is the genuinely new part, and the paper is honest about its overlap with Kanzow–Lehmann [18]. The main proof, however, has an unsupported index-selection step in Lemma 3.6 that the Cauchy argument depends on.\n\nThe Section 4 analysis is a real contribution. It covers the max line search case that [18] left open, avoids auxiliary-sequence assumptions, and does not need bounded subdifferentials. The rate results are standard once convergence is established, and the paper's structure is clear. I also credit the authors for explicitly discussing the concurrent work and the different index partition.\n\nThe soft spot is in Section 3. Lemma 3.6 asserts that a large k0 can be chosen in K and in the required index set (as used in the proof, the complement of S from (3.14)), but the proof only chooses k0 in K large enough to make alpha < 1/2. It never verifies the required membership. The printed statement even says k0 in S, which is false in the monotone limit p_k=1 where S is empty. The later summation steps (3.21) and (3.27) explicitly rely on k0 being outside S to split off or retain the first term. Without a valid choice of k0, the finite-length bound (3.19) is not established. This looks patchable—one could handle the extra term or argue the required set is infinite in the nondegenerate case—but as written it is a genuine gap, not a typo. The paper also defers several lemmas and the rate theorem to [18], which makes it less self-contained, but that is a lesser issue.\n\nThe paper is for people working on KL-based nonmonotone proximal gradient theory. The max line search result is worth refereeing. I would send it out, and I would expect the referee to ask for a fix of Lemma 3.6 and a self-contained proof of the rate theorem.","headline":"Real new result for the max line search case, but the average line search proof has a load-bearing gap in Lemma 3.6 that looks patchable.","tokens_in":144,"tokens_out":7355,"would_cite":true,"duration_ms":99955,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["49J52","90C26","90C30"],"pacs":[],"model":"deepseek-v4-flash","headline":"Two nonmonotone proximal gradient methods converge as whole sequences under local Lipschitz continuity plus the Kurdyka–Łojasiewicz property, without global Lipschitz or bounded iterates.","keywords":["Nonmonotone proximal gradient method","Average line search","Max line search","Kurdyka–Łojasiewicz property","Local Lipschitz continuity","Composite optimization","Convergence rates","M-stationary point"],"falsifier":"Run Algorithm 1 with $p_k=1$ (the monotone limit) and $\\mu\\le\\delta\\gamma_{\\min}/2$ on a problem satisfying Assumption 3.1 whose iterates are not eventually constant; the acceptance criterion then yields $q(x_k)-\\Phi_{k+1}\\ge\\frac{\\delta\\gamma_k}{2}\\|x_{k+1}-x_k\\|^2$, so the inequality defining $S$ in (3.14) can hold only in the boundary equality case, making $S$ empty for typical runs. A direct inspection of the set $S\\cap K$ for a large $k_0$ in any such run would therefore test whether the selection step on which Theorem 3.8's summation (3.21) relies is actually satisfied.","tokens_in":23781,"feed_emoji":"📉","tokens_out":13263,"duration_ms":106383,"temperature":0.7,"pith_summary":"The paper establishes global convergence for two nonmonotone proximal gradient methods — the average-line-search variant and the max-line-search variant — applied to composite optimization problems $\\min f+g$ where $f$ is continuously differentiable, $g$ is merely lower semicontinuous, and the objective need not be convex. The central claim is that the classical global Lipschitz assumption on $\\nabla f$ can be replaced by local Lipschitz continuity together with the Kurdyka–Łojasiewicz property: the entire sequence of iterates then converges to an M-stationary point, without assuming boundedness of the iterates and without any auxiliary sequence. The proof partitions iteration indices into a set on which the objective decreases sufficiently and its complement, allowing the KL inequality to compensate for the nonmonotonicity of the functional values. Rate estimates follow from the KL exponent: finite termination for exponent $1$, linear convergence for exponents in $[1/2,1)$, and sublinear rates for exponents below $1/2$. A concurrent independent work [18] proves the average-search case with a different partition, and the authors read the two results together as showing that the convergence theory is independent of the specific index-partitioning choice.","feed_headline":"Nonmonotone proximal gradient methods: local Lipschitz suffices","feed_subtitle":"Under the Kurdyka–Łojasiewicz property, whole iterates converge to stationary points with explicit rates.","key_machinery":"The load-bearing object is the partition of the iteration index set into good and bad subsets — $S$ and its complement for the average line search, $K$ and its complement for the max line search — together with the merit sequences $\\Phi_{k+1}=(1-p_k)\\Phi_k+p_k q(x_{k+1})$ and $q(x_{l(k)})=\\max_{0\\le j\\le \\min\\{m,k\\}} q(x_{k-j})$. The KL inequality $\\chi'(q(x)-q(\\bar x))\\,\\operatorname{dist}(0,\\partial q(x))\\ge1$ converts small subgradients into quantitative control of functional gaps, and the local Lipschitz continuity of $\\nabla f$ on a compact ball supplies the bound $\\operatorname{dist}(0,\\partial q(x_{k+1}))\\le(\\bar\\gamma_\\rho+L_\\rho)\\|x_{k+1}-x_k\\|$, with $\\bar\\gamma_\\rho$ a uniform upper bound on accepted step sizes near an accumulation point. The parameter condition $p_{\\min}>4/5$ keeps the ratio $\\sqrt{(1-p_{\\min})/p_{\\min}}$ small enough that the geometric sums arising in the two cases can be absorbed into the common finite-length bound.","core_discovery":"On the paper's own terms, the discovery is that nonmonotone line search does not need to be repaired by enforcing descent everywhere; it can be repaired by separating indices. For Algorithm 1, the good set is $S=\\{k: q(x_k)-\\Phi_{k+1}\\le \\frac{\\mu}{2}\\|x_{k+1}-x_k\\|^2\\}$, where $\\Phi_{k+1}=(1-p_k)\\Phi_k+p_k q(x_{k+1})$ is the averaged merit value. On $S$ the acceptance rule implies the usual sufficient decrease and controls $\\Phi_k-\\Phi_{k+1}$ from below; on the complement, the KL inequality together with the local Lipschitz bound $\\operatorname{dist}(0,\\partial q(x_{k+1}))\\le(\\bar\\gamma_\\rho+L_\\rho)\\|x_{k+1}-x_k\\|$ forces the functional gaps to be summable. The two cases are added to obtain a finite-length bound $\\sum\\|x_{i+1}-x_i\\|<\\infty$, so the whole sequence is Cauchy and converges to the accumulation point, which is M-stationary. The max-search algorithm is handled by the analogous partition $K=\\{k: q(x_{l(k+1)})-q(x_{k+1})>\\frac{\\mu}{2}\\|x_{k+1}-x_k\\|^2\\}$, using the maximal recent value $q(x_{l(k)})$ and an additional continuity assumption on $q$. The rates in Theorem 3.9 and Theorem 4.9 are then derived from a desingularization function of the form $\\chi(t)=c t^\\theta$.","pith_inferences":["A natural extension, not made in the paper, is to test whether the same good/bad partition controls other nonmonotone schemes such as spectral or Barzilai–Borwein step sizes, since the proof only uses the acceptance inequality and the KL machinery.","One could numerically audit the size of $S$ and $K$ along actual runs; the outcome would reveal whether the 'good' indices dominate the finite-length bound or whether the complement does most of the work, which could lead to shorter proofs with only one case.","The 'independence of partitioning' observation suggests a meta-theorem: any partition that makes the good set nonempty near the limit and lets the KL inequality control the bad indices would give the same convergence conclusions.","The rate formulas imply a directly testable prediction for applications: if the KL exponent $\\theta$ can be estimated from the structure of $q$, the observed error decay of the iterates should scale as $k^{-\\theta/(1-2\\theta)}$ in the sublinear regime."],"forward_implications":["The whole sequence generated by either algorithm converges to an accumulation point under local Lipschitz continuity and the KL property, extending the subsequential convergence already known from [19].","Convergence rates are governed by the KL exponent: finite termination at $\\theta=1$, Q-linear on $\\Phi_k$ (or $q(x_{l(k)})$) and R-linear on the iterates for $\\theta\\in[1/2,1)$, and sublinear with exponents $1/(1-2\\theta)$ and $\\theta/(1-2\\theta)$ for $\\theta\\in(0,1/2)$.","The max-line-search analysis removes the auxiliary-sequence requirement and the bounded-subdifferential requirement that appeared in earlier KL-based nonmonotone convergence results.","Because [18] covers the average-line-search algorithm with a different partition, the two works together support the conclusion that the convergence theory of the NPG method does not depend on how the index partition is chosen.","No global Lipschitz condition and no boundedness of the iterates are needed, so the methods carry convergence certificates for problems whose gradients are only locally smooth."],"supporting_citations":[{"why":"supplies the base result: monotone proximal gradient converges under local Lipschitz continuity and the KL property, and contributes the subdifferential-bound technique.","marker":"[16]"},{"why":"provides the algorithms and subsequential convergence results under local Lipschitz continuity that this paper upgrades to full-sequence convergence.","marker":"[19]"},{"why":"establishes the basic functional inequalities and well-definedness for the averaged nonmonotone scheme used in Algorithm 1.","marker":"[13]"},{"why":"concurrent work with the same average-search convergence result under a different index partition; together with this paper it motivates the partition-independence claim.","marker":"[18]"},{"why":"introduces the average nonmonotone line search whose merit sequence $\\Phi_k$ drives Algorithm 1.","marker":"[29]"},{"why":"introduces the max-type nonmonotone line search that defines the merit values $q(x_{l(k)})$ in Algorithm 2.","marker":"[14]"},{"why":"supplies the Kurdyka–Łojasiewicz convergence framework and desingularization-function formalism used to turn functional gaps into step-length bounds.","marker":"[3]"},{"why":"prior KL-based analysis of nonmonotone descent methods that required an auxiliary sequence and bounded subdifferentials, which this paper removes.","marker":"[26]"},{"why":"provides the lemma converting KL-exponent bounds into finite-step, linear, or sublinear convergence rates.","marker":"[15]"}],"fun_headline_variants":["Nonmonotone proximal gradient: local Lipschitz suffices","Index splitting unlocks NPG convergence without global Lipschitz","Convergence for nonmonotone proximal methods under KL and local Lipschitz","Proximal gradient: nonmonotone search converges with local bounds only"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing step is the selection of an index $k_0$ that is both late in the convergent subsequence and inside the 'good' index set where the gap between the objective value and the merit value is controlled by the squared step length; the proof establishes the smallness condition on $k_0$ but never verifies the good-set membership, which in the monotone limit may be the empty set.","fun_headline_variants_meta":{"raw":{"variants":["Nonmonotone proximal gradient: local Lipschitz suffices","Index splitting unlocks NPG convergence without global Lipschitz","Convergence for nonmonotone proximal methods under KL and local Lipschitz","Proximal gradient: nonmonotone search converges with local bounds only"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00026,"raw_usage":{"total_tokens":1696,"prompt_tokens":1159,"completion_tokens":537,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":775,"completion_tokens_details":{"reasoning_tokens":458}},"tokens_in":775,"tokens_out":537,"duration_ms":4795,"temperature":1.0,"reasoning_tokens":458,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T10:22:41.163367+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Algorithm 1 with $p_k=1$ (the monotone limit) and $\\mu\\le\\delta\\gamma_{\\min}/2$ on a problem satisfying Assumption 3.1 whose iterates are not eventually constant; the acceptance criterion then yields $q(x_k)-\\Phi_{k+1}\\ge\\frac{\\delta\\gamma_k}{2}\\|x_{k+1}-x_k\\|^2$, so the inequality defining $S$ in (3.14) can hold only in the boundary equality case, making $S$ empty for typical runs. A direct inspection of the set $S\\cap K$ for a large $k_0$ in any such run would therefore test whether the selection step on which Theorem 3.8's summation (3.21) relies is actually satisfied.","supporting_citations":[{"cited_title":"Grippo, F","cited_arxiv_id":null,"evidence_quote":"introduces the max-type nonmonotone line search that defines the merit values $q(x_{l(k)})$ in Algorithm 2."},{"cited_title":"Qian and S","cited_arxiv_id":null,"evidence_quote":"prior KL-based analysis of nonmonotone descent methods that required an auxiliary sequence and bounded subdifferentials, which this paper removes."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"provides the lemma converting KL-exponent bounds into finite-step, linear, or sublinear convergence rates."}],"review_version":1}