{"id":"e3c75364-03c3-4f7d-ad49-515091e3663b","arxiv_id":"2505.01092","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Two linesearch-based generalized conditional gradient methods, including a parameter-free variant from Ito et al., are proven to converge to stationary points without any Lipschitz or Hölder gradient assumption.","lead":"This paper proves that two linesearch-based generalized conditional gradient methods still converge to stationary points when the gradient of the smooth part is not Hölder or Lipschitz continuous, including a parameter-free variant that adapts to unknown smoothness. The result is a safety guarantee for an algorithm that is already used when gradient smoothness is difficult to verify in advance.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 3.2 is false when x_k is stationary and the subproblem solver returns a nonzero minimizer; Algorithm 1 needs an explicit termination at G(x_k)=0.","rationale":"The reader identified continuous differentiability as the weakest assumption; that is a valid observation but not a flaw. My stress-test found a different, concrete gap: Lemma 3.2 claims the Armijo linesearch in Algorithm 1 always terminates, but it fails at stationary points when the subproblem has multiple minimizers and the oracle returns a nonzero direction. The one-dimensional counterexample satisfies every stated assumption and shows that the inner loop can reject every finite trial step. This does not disprove the theorem's subsequential stationarity claim for sequences that are actually generated, but it does mean the algorithm as written is not fully well-defined and the proof of Lemma 3.2 is incorrect. The fix is trivial: terminate when G(x_k)=0, or include a tie-breaking rule that returns v_k=x_k when x_k is a minimizer of the subproblem. With that patch, the main convergence argument appears sound. Therefore I recommend CONDITIONAL acceptance rather than unconditional acceptance.","tokens_in":9317,"tokens_out":23244,"duration_ms":243241,"concrete_test":"Run Algorithm 1 on the one-dimensional instance f(x)=x^2, g(x)=max(0,|x|−1)^2, x0=0, β=0.5, σ=0.5, p=1, with a subproblem oracle that returns v=1 at x=0. If the linesearch terminates in finitely many steps, the counterexample fails; otherwise Lemma 3.2 is false as stated. After patching Algorithm 1 to terminate when G(x_k)=0, rerun the proof of Lemma 3.2 to confirm that the only needed modification is this stopping rule.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Lemma 3.2 (well-definedness of Algorithm 1) is false as stated. The proof uses Lemma 3.1 to assert F(x_k+β^i d_k) ≤ F(x_k)−σβ^i G(x_k) for all sufficiently large i. For nonstationary points the o(t) error is dominated by the linear −tG(x_k) term, so this is fine. But when G(x_k)=0, the asserted inequality becomes F(x_k+β^i d_k) ≤ F(x_k), which need not hold for any finite i because the o(t) term can be positive (e.g., quadratic growth). Concretely, take E=R, f(x)=x^2, g(x)=max(0,|x|−1)^2, and x_0=0. All standing assumptions hold: g is closed convex and supercoercive, f is C^1, and F is bounded below. The point x_0 is stationary with G(x_0)=0, and the subproblem min_v g(v) has minimizers [−1,1]. If the subproblem oracle returns v=1, then d=1, and for every finite i the trial point β^i satisfies F(β^i)=β^{2i}>0=F_0, so the Armijo condition (4) fails for all finite i and the inner loop never terminates. Thus Algorithm 1 is not well-defined at stationary points unless one adds an explicit stopping rule such as 'if G(x_k)=0, stop' or forces d_k=0 when x_k is already a subproblem minimizer. The subsequential stationarity conclusion for sequences that are actually generated is not affected, but the proof of Lemma 3.2 and the pseudocode require a small patch.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper analyzes two linesearch-based generalized conditional gradient methods for the composite problem min F(x)=f(x)+g(x), where f is continuously differentiable on dom g (but not assumed to have a Lipschitz or Hölder continuous gradient) and g is proper, closed, convex, and supercoercive. The main results are Theorem 3.1, asserting that every accumulation point of the iterates of a nonmonotone Armijo-type method (Algorithm 1) is stationary, and Theorem 3.2, asserting that under a bounded-level-set condition the parameter-free variant of Ito, Lu, and He (Algorithm 2) has at least one stationary accumulation point and its running minimum Frank-Wolfe gap tends to zero. The key new ingredient is Lemma 3.1, which derives the o(t) descent estimate F(x+td) <= F(x)-tG(x)+o(t) using only continuous differentiability of f and convexity of g.","tokens_in":9661,"tokens_out":10701,"duration_ms":109246,"significance":"If the technical gaps identified below are fixed, this is a worthwhile contribution: it removes global Lipschitz/Hölder smoothness assumptions that are standard in essentially all existing convergence analyses of generalized conditional gradient methods, and it shows that a practically attractive parameter-free backtracking variant remains convergent even when the Hölder condition is unknown or absent. The proofs are short, elementary, and mostly self-contained, and Lemma 3.1 is a clean reusable tool. The extension of Bertsekas-style subsequential convergence from constrained smooth problems to the composite, nonconvex, supercoercive setting is a genuine advance. However, the well-definedness of Algorithm 1 has a real gap at stationary points, so the paper is not yet fully sound as written.","major_comments":[{"comment":"Lemma 3.2 is false when G(x_k)=0 and the subproblem oracle returns a minimizer v_k different from x_k. The proof applies Lemma 3.1 and concludes F(x_{k,i}) <= F(x_k) - sigma beta^i G(x_k) for all sufficiently large i, but when G(x_k)=0 this reduces to F(x_{k,i}) <= F(x_k)+o(beta^i), which does not force the Armijo condition (4) to hold because o(beta^i) may be positive. Concretely, take E=R, f(x)=x^2, g(x)=max(0,|x|-1)^2, x_0=0; then all standing assumptions hold and x_0 is stationary with G(x_0)=0, but the subproblem minimizer v=1 gives d=1 and F(beta^i)=beta^{2i}>0=F(x_0), so (4) fails for every finite i. The algorithm therefore may never produce an infinite sequence from a stationary point. The convergence theorems would still hold for sequences that are actually generated, but the well-definedness claim in Lemma 3.2 and the pseudocode need a patch, such as an explicit stopping rule 'if G(x_k)=0, stop' or a tie-breaking rule that selects d_k=0 at stationary points.","section":"Section 3, Lemma 3.2"},{"comment":"The definition of the trial step size in Algorithm 2 is incomplete when d_k=0. The formula tau_k^(i)=min{1, G(x_k)/(2L_k^(i)||d_k||^2)} involves division by ||d_k||^2, and d_k=0 occurs exactly when v_k=x_k, i.e., when x_k is a minimizer of the linearized subproblem. Since -grad f(x_k) in partial g(x_k) is equivalent to G(x_k)=0 by Lemma 2.1, this is precisely the stationary case. The algorithm needs an explicit convention for d_k=0, e.g., tau_k^(i)=1 or termination when G(x_k)=0. Without this, the statement of Proposition 3.2 and Lemma 3.3 do not formally cover all admissible outputs of a subproblem solver.","section":"Section 3.1, Algorithm 2"}],"minor_comments":[{"comment":"The abstract and introduction say the methods 'guarantee convergence' even without Hölder continuity, but the theorems establish subsequential convergence and convergence of the running minimum of the Frank-Wolfe gap, not convergence of the whole sequence. Please make this distinction explicit in the abstract.","section":"Abstract and Introduction"},{"comment":"In the displayed inequality (5), the exponent on beta appears to be i_{k-1}, but the notation is easy to misread as i_k - 1. Please add brackets or a clarifying sentence so that the index is unambiguous.","section":"Section 3, Lemma 3.2 proof, Eq. (5)"},{"comment":"The footnote defining uniform convex structure states 'rho >= 21' near the end of Section 3; this is presumably rho >= 2 and should be corrected.","section":"Footnote, uniform convex structure"},{"comment":"Reference [18] contains the odd text 'Kurdyka–/suppress Lojasiewicz'; this should read 'Kurdyka–Łojasiewicz property'.","section":"References"}],"recommendation":"major_revision","confidential_remarks":"The paper is close to acceptable after a small but genuine patch. The false statement in Lemma 3.2 is a load-bearing issue for well-definedness, but the remedy is straightforward and does not affect the convergence argument itself. The skeptical counterexample is correct and should be addressed explicitly. I recommend major revision rather than rejection because the central results are defensible and the required changes are local."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: the paper is a genuinely useful contribution to the convergence theory of generalized conditional gradient methods. It proves subsequential stationarity for two linesearch variants under only C^1 smoothness of the smooth part — no Lipschitz or Hölder gradient. That is a real extension of Bertsekas and of Ito et al. The o(t) descent lemma (Lemma 3.1) is the key, and it is valid under mere continuous differentiability. The proofs are complete and careful, including the vanishing-step cases and the parameter-free adaptive backtracking in Algorithm 2. The comparison with prior work is accurate, and the self-citations are not inflated.\n\nThe one soft spot is real but small. Lemma 3.2 asserts the linesearch in Algorithm 1 always terminates. The proof uses Lemma 3.1 to claim F(x_k + β^i d_k) ≤ F(x_k) − σ β^i G(x_k) for all large i. That is correct when G(x_k) > 0, because the linear term dominates the o(t). But the lemma is stated for all x_k, including stationary points where G(x_k) = 0. Then the inequality becomes F ≤ F(x_k) + o(t), and o(t) can be positive. Concretely, take f(x) = x^2, g(x) = max(0, |x|−1)^2, x_0 = 0. All assumptions hold, G(0) = 0, but the subproblem oracle may return v = 1, d = 1, and then F(β^i) > F(0) for every finite i. The loop never terminates. The well-definedness proof needs an explicit “if G(x_k) = 0, stop” in Algorithm 1, or a requirement that the oracle returns d_k = 0 when x_k is already a subproblem minimizer. This does not damage the main convergence theorems for sequences that actually run, since those would only be produced when G(x_k) > 0, but as written Lemma 3.2 is false and the pseudocode is incomplete. A referee should ask for this patch.\n\nAlso worth noting: the continuous differentiability of ∇f is load-bearing in the vanishing-step argument. That is fine; it is the intended weakening and it is stated clearly.\n\nBottom line: this is a competent, honest paper that deserves peer review. After the Lemma 3.2 fix it would be publishable. I would not cite it myself because it is not my subfield, but anyone working on conditional gradient methods should read it. I would send it to review, with the patch requested.","headline":"Useful convergence proofs for generalized conditional gradient methods without gradient smoothness; the main theorems hold, but Lemma 3.2's termination claim needs a small patch at stationary points.","tokens_in":10169,"tokens_out":4289,"would_cite":false,"duration_ms":41054,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C30","90C25","65K05"],"pacs":[],"model":"deepseek-v4-flash","headline":"Two linesearch-based generalized conditional gradient methods converge to stationary points of a composite objective even when the gradient of the smooth part is merely continuous, with no Lipschitz or Hölder condition assumed.","keywords":["generalized conditional gradient method","composite optimization","nonmonotone linesearch","parameter-free algorithm","Hölder continuity","Frank-Wolfe gap","stationary point","convergence without smoothness"],"falsifier":"Concrete test: with g the indicator of [−1,1] and f(x) = x + x² sin(1/x²), the smooth part is differentiable everywhere with f'(0) = 1 while f' is discontinuous and unbounded at 0, so 0 is a non-stationary point. Run Algorithms 1 and 2 from several starting points and record the Frank-Wolfe gap G(x_k); iterates accumulating at 0 with a gap bounded away from zero would show where the continuous-gradient hypothesis is doing its work, while a gap that always tends to zero would suggest the theorem survives weaker assumptions. Independently, verifying inequality (7) numerically during a run on an ordinary C¹ but non-Lipschitz objective would confirm the proof's load-bearing estimate holds as claimed.","tokens_in":9121,"feed_emoji":"📉","tokens_out":18662,"duration_ms":160050,"temperature":0.7,"pith_summary":"Convergence analyses of the generalized conditional gradient method — the composite-problem solver that at each step minimizes a linearized smooth part plus an unchanged nonsmooth convex term — almost always assume the gradient of the smooth part is Lipschitz or Hölder continuous. This paper proves that two linesearch-based variants need no such assumption: with only continuous differentiability of the smooth part and convexity plus supercoercivity of the nonsmooth part, every accumulation point of the nonmonotone Armijo variant is a stationary point of the composite objective, and the parameter-free variant (Algorithm 2) converges to a stationary point under an additional bounded-level-set condition. The practical upshot is that both algorithms can be run without first certifying any Hölder exponent; the parameter-free method still yields an approximate stationary point in finitely many iterations even when no Hölder condition holds. The proof operates through the Frank-Wolfe gap, which the linesearch rejection inequality forces to zero using only continuity of the gradient.","feed_headline":"Conditional gradient still converges with no Lipschitz assumption","feed_subtitle":"Both nonmonotone and parameter-free variants only need the smooth part to have a continuous gradient.","key_machinery":"The central object is the Frank-Wolfe gap, G(x) := max_v {⟨∇f(x), x − v⟩ + g(x) − g(v)}, a nonnegative, lower-semicontinuous optimality measure that vanishes exactly at stationary points of (1). The mechanism carrying both proofs is the descent estimate of Lemma 3.1, F(x + td) ≤ F(x) − tG(x) + o(t) for t ∈ [0,1] and d a subproblem solution direction, which follows from continuous differentiability of f and convexity of g alone. Armijo-type backtracking then guarantees a function decrease proportional to the gap at every iteration — for Algorithm 1, F_{k+1} ≤ F_k − $pσβ^{{i_k}}$G(x_k), and for Algorithm 2, F(x_{k+1}) ≤ F(x_k) − (1/4)τ_k G(x_k) — so the gap is driven to zero along any subsequence where the stepsize does not degenerate. In the vanishing-stepsize case, rejection of the trial point forces inequalities (7) and (10), which bound the gap by ‖∇f(ξ_k) − ∇f(x_k)‖‖d_k‖ with ξ_k a mean-value point converging to the same limit as x_k; continuity of ∇f, rather than any quantitative modulus, sends that bound to zero, while boundedness of the directions d_k is secured by supercoercivity of g.","core_discovery":"The paper's central claim is a pair of subsequential convergence theorems. Theorem 3.1: for the composite problem min F = f + g with g proper, closed, convex, and supercoercive and f continuously differentiable on dom g, any accumulation point of the sequence generated by the generalized conditional gradient method with average-type nonmonotone Armijo linesearch (Algorithm 1) is stationary; no Lipschitz or Hölder assumption on ∇f appears anywhere in the hypotheses. Theorem 3.2: the same conclusion holds for the parameter-free backtracking variant of [16] (Algorithm 2), giving an accumulation point that is stationary and min_{0≤l≤k} G(x_l) → 0 as k → ∞, under the sole added assumption that the lower level set {x : F(x) ≤ F(x0)} is bounded — a condition automatic when f is convex or dom g is bounded. In the delicate regime where backtracking stepsizes shrink to zero, the mean-value theorem produces a point ξ_k between x_k and the rejected trial point, and the linesearch rejection inequality yields (1−σ)G(x_k) ≤ ‖∇f(ξ_k) − ∇f(x_k)‖ ‖d_k‖; because ξ_k and x_k converge to the same limit and ∇f is continuous, the gap must vanish. The paper thus establishes convergence under a mere continuity condition on the gradient, where the prior literature required quantitative smoothness.","pith_inferences":["The proofs appear to consume only continuity of ∇f at the accumulation point and boundedness of the directions d_k, so the hypothesis 'continuously differentiable on dom g' could likely be weakened to differentiability with locally continuous gradient on the lower level set.","If ∇f is known only through a modulus of continuity ω(δ), the same inequalities should yield a quantitative gap decay that interpolates between the O(ε^{−1−1/ν}) rate for ω(δ) = Cδ^ν and the purely asymptotic guarantee when no modulus exists.","Because every accumulation point must be stationary, any counterexample to whole-sequence convergence under Armijo stepsizes would have to unwind along the stationary set itself, which constrains the search left open by the divergence counterexamples the paper cites.","The mean-value-plus-linesearch-rejection mechanism should transfer to linesearch-based proximal gradient methods, producing a common smoothness-free convergence theory for the two principal composite solvers."],"forward_implications":["Corollary 3.1: if an accumulation point exists — e.g. when dom g is bounded — the minimum Frank-Wolfe gap over the first k iterates tends to zero, so an ε-approximate stationary point is obtained in finitely many iterations.","Theorem 3.2: the parameter-free variant converges as soon as the lower level set is bounded, a condition that holds automatically when f is convex or when dom g is bounded.","The nonmonotone Armijo result extends the smoothness-free analysis of [2] beyond compact convex constraint sets, and the monotone backtracking method of [22] (p = 1, σ ≤ 1/2) is covered as a special case.","Because the parameter-free method's Hölder-adaptive rate remains valid when ∇f is Hölder continuous, skipping a Hölder check loses the rate only in cases where no Hölder exponent actually exists."],"supporting_citations":[{"why":"Supplies the Frank-Wolfe gap characterization used as the target guarantee in both theorems (G(x) = 0 if and only if x is stationary).","marker":"[1]"},{"why":"The smoothness-free subsequential convergence result for the case p = 1 with g a compact convex indicator, which Theorem 3.1 extends to general composite problems with a nonmonotone linesearch.","marker":"[2]"},{"why":"Earlier convergence analysis of the generalized conditional gradient method without smoothness assumptions, but relying on exact linesearch that the backtracking procedures here replace.","marker":"[6]"},{"why":"Introduces the parameter-free generalized conditional gradient method (Algorithm 2) and its Hölder-exponent-adaptive rates; Theorem 3.2 extends its convergence beyond the Hölder setting.","marker":"[16]"},{"why":"Defines the backtracking GCG variant that Algorithm 1 coincides with in the monotone case (p = 1, σ ≤ 1/2), under smoothness assumptions the paper removes.","marker":"[22]"},{"why":"Proposes the original generalized conditional gradient method for composite problems, the algorithmic template both theorems analyze.","marker":"[25]"},{"why":"Provides the average-type nonmonotone Armijo linesearch whose acceptance criterion (4) drives Algorithm 1's backtracking and descent accounting.","marker":"[30]"}],"fun_headline_variants":["No Lipschitz needed: GCG linesearch converges with continuous gradient","Smoothness assumptions dropped: conditional gradient converges","GCG linesearch works with just continuous gradients","Parameter-free GCG: no Holder, no Lipschitz, converges","Generalized conditional gradient converges without smoothness"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is continuity of the gradient ∇f of the smooth part at the accumulation point, used to conclude that ‖∇f(ξ_k) − ∇f(x_k)‖ shrinks to zero when the trial point ξ_k and the iterate x_k approach the same limit, and, for the parameter-free variant, boundedness of the lower level set {x : F(x) ≤ F(x0)}.","fun_headline_variants_meta":{"raw":{"variants":["No Lipschitz needed: GCG linesearch converges with continuous gradient","Smoothness assumptions dropped: conditional gradient converges","GCG linesearch works with just continuous gradients","Parameter-free GCG: no Holder, no Lipschitz, converges","Generalized conditional gradient converges without smoothness"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000746,"raw_usage":{"total_tokens":3316,"prompt_tokens":930,"completion_tokens":2386,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":546,"completion_tokens_details":{"reasoning_tokens":2306}},"tokens_in":546,"tokens_out":2386,"duration_ms":18945,"temperature":1.0,"reasoning_tokens":2306,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T04:26:21.901551+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Concrete test: with g the indicator of [−1,1] and f(x) = x + x² sin(1/x²), the smooth part is differentiable everywhere with f'(0) = 1 while f' is discontinuous and unbounded at 0, so 0 is a non-stationary point. Run Algorithms 1 and 2 from several starting points and record the Frank-Wolfe gap G(x_k); iterates accumulating at 0 with a gap bounded away from zero would show where the continuous-gradient hypothesis is doing its work, while a gap that always tends to zero would suggest the theorem survives weaker assumptions. Independently, verifying inequality (7) numerically during a run on an ordinary C¹ but non-Lipschitz objective would confirm the proof's load-bearing estimate holds as claimed.","supporting_citations":[{"cited_title":"Nonlinear Programming","cited_arxiv_id":null,"evidence_quote":"The smoothness-free subsequential convergence result for the case p = 1 with g a compact convex indicator, which Theorem 3.1 extends to general composite problems with a nonmonotone linesearch."},{"cited_title":"A generalized c onditional gradient method and its connection to an iterative shrinkage method","cited_arxiv_id":null,"evidence_quote":"Earlier convergence analysis of the generalized conditional gradient method without smoothness assumptions, but relying on exact linesearch that the backtracking procedures here replace."},{"cited_title":"A parameter-free c onditional gradient method for composite minimization under h¨ older condition.Journal of Machine Learning Research , 24(166):1–34, 2023","cited_arxiv_id":null,"evidence_quote":"Introduces the parameter-free generalized conditional gradient method (Algorithm 2) and its Hölder-exponent-adaptive rates; Theorem 3.2 extends its convergence beyond the Hölder setting."},{"cited_title":"On fast convergence rates for generalized conditional gradient methods with backtracking stepsize","cited_arxiv_id":null,"evidence_quote":"Defines the backtracking GCG variant that Algorithm 1 coincides with in the monotone case (p = 1, σ ≤ 1/2), under smoothness assumptions the paper removes."},{"cited_title":"A minimization method for the s um of a convex function and a continuously differentiable function","cited_arxiv_id":null,"evidence_quote":"Proposes the original generalized conditional gradient method for composite problems, the algorithmic template both theorems analyze."},{"cited_title":"A nonmonotone line search te chnique and its application to unconstrained optimization","cited_arxiv_id":null,"evidence_quote":"Provides the average-type nonmonotone Armijo linesearch whose acceptance criterion (4) drives Algorithm 1's backtracking and descent accounting."}],"review_version":1}