{"id":"ce10f1ac-8c88-4c74-910c-291c295b66ee","arxiv_id":"2505.00221","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"high","formal_verification":"none","parameter_count":4,"one_line_summary":"Under smoothness, strong convexity, and the Kurdyka-Lojasiewicz property, the greedy Frank-Wolfe sequence converges to a critical point, with rates that depend on the KL exponent.","lead":"This paper proves that the greedy Frank-Wolfe algorithm converges last-iterate when the objective is strongly convex and the problem satisfies the Kurdyka-Lojasiewicz inequality. The result is applied to sparse PCA, compressed sensing, and a parallel algorithm for the Max-Cut semidefinite relaxation.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: Eq. (26) is valid for arbitrary compact sets via the limiting normal cone; the V-graph counterexample fails.","rationale":"The reader's weakest_assumption identifies a supposed failure of Lemma 3.1 for nonconvex X. That failure is not real: global optimality of a linear function over a closed set always yields a limiting normal cone condition, because the global supporting directions belong to the regular normal cone, which is a subset of the limiting normal cone. The V-graph example is thus not a counterexample; the limit point satisfies the stationarity condition. The central proof of Theorem 3.2 is sound. The remaining issues are a minor constant typo in Lemma 3.1 (α versus α/2) and the Max-Cut section's use of σ values outside the strong-convexity regime, which the authors explicitly acknowledge. These do not undermine the central claim and can be fixed in revision. I therefore disagree with the reader's stated load-bearing concern, but I do not see a compelling reason to change the overall disposition of the paper: the existing conditional verdict remains defensible on the basis of the minor presentation and application-regime issues.","tokens_in":20025,"tokens_out":35484,"duration_ms":357349,"concrete_test":"Analytically verify the disputed step on the V-graph counterexample: take X = {(t, |t|): |t| ≤ 1} and g(x,y) = x^2 + y^2. From any initial point, the GFW sequence converges to (1,1). Compute the limiting normal cone N_X(1,1) = {v : v_1 + v_2 ≥ 0} and check that -∇g(1,1) = (-2,-2) belongs to N_X(1,1), so (1,1) is in crit F. This directly falsifies the reader's claim that the theorem fails on this example. Independently, re-derive Eq. (26) from the definition of the limiting normal cone; the regular normal cone is always a subset of the limiting normal cone, so no regularity of X is needed.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The reader's central concern about Lemma 3.1, Eq. (26), does not land. For any closed set X, if x_{k+1} is a global minimizer of the linear function y -> ∇f(x_k)^T y over X, then -∇f(x_k) lies in the regular normal cone \\hat N_X(x_{k+1}); since the regular normal cone is always contained in the limiting normal cone N_X(x_{k+1}) = ∂I_X(x_{k+1}), Eq. (26) holds for arbitrary compact X without any convexity, prox-regularity, or manifold assumption. The V-graph example does not produce a non-critical limit: at the potential limit point (1,1) of X = {(t, |t|): |t| ≤ 1}, the limiting normal cone is {v : v_1 + v_2 ≥ 0}, which contains -∇g(1,1) for, e.g., g(x,y) = x^2 + y^2. The proof of Theorem 3.2 is therefore sound. The only genuine issues are minor: Lemma 3.1 drops a factor 1/2 in the strong-convexity inequality, so the constant should be ρ1 = α/2 rather than α, and the Max-Cut numerical experiments use σ values that do not guarantee strong convexity, although the paper itself notes this in the discussion surrounding Figure 5. Neither issue threatens the central convergence claim.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper studies the greedy Frank-Wolfe (GFW) algorithm with unit step size for maximizing a smooth, strongly convex function g over a compact set X that is not assumed convex. The authors reformulate the problem as the minimization of F = -g + I_X and prove that the GFW iterates form a gradient-like descent sequence in the sense of Bolte et al. [30]. Their main result (Theorem 3.2) states that if F satisfies the Kurdyka-Łojasiewicz property, then the whole sequence converges to a critical point of F; Theorem 3.3 gives convergence rates depending on the desingularizing exponent. The paper also contributes three applications: a split reweighted ℓ1 minimization algorithm for compressed sensing with a convergence guarantee that survives noisy constraints, a sparse PCA convergence result, and a parallel GFW algorithm for the Max-Cut SDP relaxation, accompanied by numerical experiments on Gaussian data.","tokens_in":20324,"tokens_out":22863,"duration_ms":223499,"significance":"If correct, the main theorem provides the first last-iterate convergence guarantee for this unit-step greedy Frank-Wolfe variant outside the polyhedral setting, which is a meaningful advance for the algorithm and for the applications considered. The proof is a clean verification of the three conditions of the gradient-like descent framework; the subgradient lower bound (C2) is verified directly from the subproblem optimality and smoothness, and the KL machinery is imported from existing nonconvex optimization theory. The paper is careful to acknowledge the limitations of the rates (unknown constants) and to note which numerical experiments fall outside the assumptions. The applications are relevant, and the numerical studies support the theoretical results without overclaiming. The central objection raised in the review process about the validity of the optimality condition in Lemma 3.1 does not survive scrutiny: the limiting normal cone is the appropriate object for arbitrary closed sets, and the condition is valid.","major_comments":[{"comment":"A natural concern is that Eq. (26) uses an optimality condition for a global maximizer over a nonconvex set. This concern does not hold: for any closed set X, if x_{k+1} is a global minimizer of y ↦ ∇f(x_k)^T y on X, then -∇f(x_k) lies in the regular normal cone \\hat N_X(x_{k+1}), and since \\hat N_X(x) ⊆ N_X(x) = ∂I_X(x), the inclusion 0 ∈ ∇f(x_k) + ∂I_X(x_{k+1}) follows. Equivalently, Fermat's rule applied to the lsc function ∇f(x_k)^T(·) + I_X(·) at its global minimizer gives the same condition. The V-shaped counterexample proposed in the review process does not produce a non-critical limit: for g(x,y)=x^2+y^2 on X = {(t,|t|): |t|≤1}, the limit (1,1) satisfies ∇g(1,1)=(2,2) ∈ N_X(1,1) = {w : w_1+w_2 ≥ 0}, so 0 ∈ ∂F(1,1). The proof of Lemma 3.1 is sound.","section":"§3, Lemma 3.1, Eq. (26)"}],"minor_comments":[{"comment":"In verifying (C1), the inequality (24) carries a factor 1/2 from strong convexity, so the correct constant is ρ1 = α/2, not ρ1 = α as written. The claim remains true with this correction, but the text should be made consistent.","section":"§3, Lemma 3.1"},{"comment":"The statement that the GFW algorithm applied to X and to conv(X) 'produces identical iterates' is not justified under arbitrary tie-breaking: when the linear subproblem has multiple maxima, a chosen maximizer in conv(X) may not belong to X, and the subsequent iterates can diverge. Please rephrase to assert existence of a selection of extreme-point maximizers for which the iterates coincide, or restrict the claim to cases where the linearized subproblem has a unique maximizer.","section":"§2.1, Proposition 2.2"},{"comment":"In the sum in (11), the index k appears inside the summand; it should be i. Also, the phrase 'Every limit point of the sequence converges to a stationary point' should be 'Every limit point of the sequence is a stationary point.'","section":"§2.2, Theorem 2.4, Eq. (11)"},{"comment":"The bounded reformulation of the RWL1 Split model uses an unspecified constant M. It would help the reader to state explicitly that a sufficiently large M exists because the objective value is monotonically nondecreasing and its superlevel sets on X are bounded, and to note that the linear subproblem over the original unbounded polyhedron has a finite optimum since the weights in (38) are positive.","section":"§4.1"},{"comment":"Algorithm 3 computes B_{k+1} by normalizing each row of G_{k+1}; if a row of G_{k+1} is zero, the update is undefined. A short remark on this degenerate case would make the algorithm well-posed.","section":"§4.3, Algorithm 3"}],"recommendation":"minor_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this paper proves a genuine last-iterate convergence theorem for the greedy Frank-Wolfe algorithm with unit step size on strongly convex maximization over a compact (not necessarily convex) set, under the KL property. That is the real contribution, and the core proof is correct. The applications—RWL1 Split, SPCA, and a parallel Burer-Monteiro-style Max-Cut SDP solver—are a useful bonus.\n\nThe main worry in the review you sent—that Lemma 3.1's Eq. (26) assumes a convexity-like optimality condition—does not survive contact. If x_{k+1} is a global maximizer of the linear subproblem, then -∇f(x_k) lies in the regular normal cone at x_{k+1}, and the regular normal cone is always contained in the limiting normal cone ∂I_X(x_{k+1}). So Eq. (26) holds for arbitrary compact X. The V-graph example is not a counterexample: at (1,1), ∇g=(2,2) lies in the normal cone of that set, so (1,1) is critical for F=-g+I_X. The soundness score of 4 is too harsh.\n\nReal soft spots:\n\n1. Algorithm 3 is written with G^{k+1}=A B^k. That is the GFW step for the unshifted objective ⟨A,BB^T⟩. The convergence theory applies to the shifted objective ⟨A+σI,BB^T⟩, whose Euclidean gradient is 2(A+σI)B. The shift is constant on the product of spheres, so the optimization problem is unchanged, but the algorithm as pseudocoded is not the algorithm the theorem covers. The fix is trivial (write G=(A+σI)B), but as written it is a gap in the Max-Cut application.\n\n2. Lemma 3.1 takes ρ1=α; the strong convexity inequality gives α/2. Constant only, no effect on the result.\n\n3. The Max-Cut experiments use σ2=10^{-3} and σ3=25e-4, which the paper admits do not guarantee strong convexity. That's fine as a numerical study, but Figure 5 is not evidence for Theorem 3.2 in those regimes.\n\nThe citation pattern is honest: the KL machinery is imported from Bolte et al. and the rates are quoted, and the paper says so. No circularity.\n\nWho this is for: anyone working on projection-free methods for nonconvex sets or on KL-based analysis of first-order methods. The RWL1 Split result for the noisy compressed sensing case is a neat finding.\n\nRecommendation: yes, send it to peer review. The central theorem is correct and the flaws are fixable. A good referee will ask for the Algorithm 3 clarification and the ρ1 correction.","headline":"The KL-based last-iterate convergence proof for greedy FW is sound; the paper's real warts are a missing factor 1/2 in a constant and a mismatch between the theory and the Max-Cut pseudocode.","tokens_in":20864,"tokens_out":13646,"would_cite":true,"duration_ms":135305,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C26","90C30","49M37","65K05"],"pacs":[],"model":"deepseek-v4-flash","headline":"The greedy Frank-Wolfe algorithm provably converges to a critical point when the objective satisfies the Kurdyka-Łojasiewicz inequality.","keywords":["Frank-Wolfe algorithm","conditional gradient","convex maximization","Kurdyka-Łojasiewicz inequality","last-iterate convergence","sparse PCA","reweighted l1 minimization","Max-Cut SDP"],"falsifier":"Take $g(x,y)=x^2+y^2$ and $X=\\{(t,|t|):t\\in[-1,1]\\}$, a compact semialgebraic set. Starting from $(0.5,0.5)$, GFW jumps to $(1,1)$ and repeats it, but $-\\nabla g(1,1)=(-2,-2)$ is not in the normal cone of $X$ at $(1,1)$, so $(1,1)\\notin\\mathrm{crit}\\,F$; this instance satisfies all stated assumptions, including KL.","tokens_in":19776,"feed_emoji":"📈","tokens_out":10524,"duration_ms":100961,"temperature":0.7,"pith_summary":"The paper studies the greedy Frank-Wolfe algorithm with a unit step size, applied to maximizing a smooth and strongly convex function over a compact feasible set that is not assumed convex. The central claim is that, once the objective-plus-indicator function $F=-g+I_X$ satisfies the Kurdyka-Łojasiewicz (KL) inequality, the full iterate sequence converges to a critical point of $F$, with finite, linear, or sublinear rates depending on the KL exponent. If correct, this is the first last-iterate convergence guarantee for this linear-oracle algorithm beyond polyhedral feasible sets. The result is then applied to prove convergence of a sparse PCA method, to construct a reweighted $\\ell_1$ compressed-sensing algorithm whose guarantees survive noisy constraints, and to design a parallel GFW algorithm for the Max-Cut semidefinite relaxation.","feed_headline":"Greedy Frank-Wolfe iterates converge on convex maximization","feed_subtitle":"With the Kurdyka-Łojasiewicz inequality, the last iterate provably lands on a critical point.","key_machinery":"The mechanism is the reformulation $F=-g+I_X$ together with the gradient-like descent sequence verification. Strong convexity gives sufficient decrease $f(x_k)-f(x_{k+1})\\ge (\\alpha/2)\\|x_{k+1}-x_k\\|^2$; smoothness lets $w_{k+1}=\\nabla f(x_{k+1})-\\nabla f(x_k)$ serve as a subgradient of $F$ at $x_{k+1}$ with $\\|w_{k+1}\\|\\le L\\|x_{k+1}-x_k\\|$; and continuity supplies the limit-point energy condition. The KL property—a concave desingularizing function $\\varphi$ controlling $F(x)-F(x^*)$ by $\\mathrm{dist}(0,\\partial F(x))$—then forces finite length of the iterates and convergence to a critical point.","core_discovery":"The paper's strongest assertion is Theorem 3.2: under smoothness and strong convexity of $g$, compactness of $X$, and the KL property of $F=-g+I_X$, the sequence $x_{k+1}\\in\\arg\\max\\{\\nabla g(x_k)^T x:x\\in X\\}$ converges to some $x^*\\in\\mathrm{crit}\\,F$. The proof shows the GFW sequence is a gradient-like descent sequence for $F$, so standard KL theory applies; Theorem 3.3 attaches rates from the desingularizing exponent $\\theta$. Replacing $X$ by its convex hull only sharpens the limit to an extreme point, and the stationarity condition becomes a normal-cone condition for $\\mathrm{conv}(X)$.","pith_inferences":["An implicit requirement in Lemma 3.1 is that the maximizer $x_{k+1}$ of the linear subproblem satisfy the normal-cone optimality condition for $F$; this holds for prox-regular, convex, or smooth-manifold feasible sets, and a repaired theorem would need to state such regularity explicitly.","The $\\sigma I$ shift used to force strong convexity in the sparse PCA and Max-Cut applications is a general modeling trick: any smooth convex maximization over a compact semialgebraic set can be shifted to satisfy Assumption 1.1, so the same KL convergence template should extend to other low-rank and sparsity-constrained models.","A natural testable extension replaces the exact linear oracle by an approximate one: if the linear maximization is solved only to tolerance $\\epsilon_k$, the gradient-like descent inequalities should hold with a slack term, and KL arguments should yield convergence whenever $\\sum\\epsilon_k<\\infty$."],"forward_implications":["The sparse PCA GFW algorithm converges in the last iterate under the sphere-plus-cardinality constraint, where previously only subsequential stationarity was known.","The proposed RWL1 Split reweighted $\\ell_1$ algorithm keeps a convergence guarantee even when the linear equality constraint is replaced by a noisy norm-ball constraint, a case where polyhedral finite convergence fails.","The Max-Cut SDP algorithm updates all rows of $B$ in parallel and still converges to a first-order stationary point; the reported experiments show it overtakes block-coordinate and Riemannian-gradient methods in wall-clock time.","When the KL desingularizing exponent $\\theta$ is known, the GFW convergence rate is finite for $\\theta=0$, linear for $\\theta\\le 1/2$, and sublinear for $\\theta>1/2$."],"supporting_citations":[{"why":"Provides the gradient-like descent sequence framework and the KL-based global convergence and rate theorems that the paper invokes directly.","marker":"[30]"},{"why":"Gives the conditional-gradient unit-step algorithm and the base convergence results (Theorem 2.4) that the paper extends to last-iterate convergence.","marker":"[18]"},{"why":"Defines the gradient-like descent sequence conditions used to connect GFW to KL theory.","marker":"[33]"},{"why":"Establishes finite convergence for unit-step FW over polytopes, the polyhedral result that the non-polyhedral theorem generalizes.","marker":"[2]"},{"why":"Supplies the KL property for nonsmooth subanalytic functions, covering the semialgebraic objectives and sets used in the applications.","marker":"[42]"},{"why":"The reweighted $\\ell_1$ minimization algorithm that the paper recognizes as GFW and modifies into RWL1 Split.","marker":"[5]"},{"why":"The Max-Cut SDP relaxation whose low-rank factorized form is the target of the new parallel GFW algorithm.","marker":"[8]"},{"why":"Introduces the low-rank factorization used to convert the SDP into the sphere-constrained nonconvex model.","marker":"[55]"}],"fun_headline_variants":["Frank-Wolfe iterates converge for strongly convex maximization","KL property ensures Frank-Wolfe convergence on convex maximization","Unit-step Frank-Wolfe: global convergence via KL inequality","Greedy Frank-Wolfe provably converges with KL and strong convexity","New Frank-Wolfe convergence result for Max-Cut and sparse PCA"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof relies on the chosen maximizer of the linear step counting as a stationary candidate through the normal cone of the feasible set; that is automatic for convex or smooth feasible sets, but not for every compact set.","fun_headline_variants_meta":{"raw":{"variants":["Frank-Wolfe iterates converge for strongly convex maximization","KL property ensures Frank-Wolfe convergence on convex maximization","Unit-step Frank-Wolfe: global convergence via KL inequality","Greedy Frank-Wolfe provably converges with KL and strong convexity","New Frank-Wolfe convergence result for Max-Cut and sparse PCA"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000419,"raw_usage":{"total_tokens":2105,"prompt_tokens":843,"completion_tokens":1262,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":459,"completion_tokens_details":{"reasoning_tokens":1170}},"tokens_in":459,"tokens_out":1262,"duration_ms":11708,"temperature":1.0,"reasoning_tokens":1170,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T04:52:32.495686+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take $g(x,y)=x^2+y^2$ and $X=\\{(t,|t|):t\\in[-1,1]\\}$, a compact semialgebraic set. Starting from $(0.5,0.5)$, GFW jumps to $(1,1)$ and repeats it, but $-\\nabla g(1,1)=(-2,-2)$ is not in the normal cone of $X$ at $(1,1)$, so $(1,1)\\notin\\mathrm{crit}\\,F$; this instance satisfies all stated assumptions, including KL.","supporting_citations":[{"cited_title":"First order methods beyond convexity and lipschitz gradient continuity with applications to quadratic inverse problems,","cited_arxiv_id":null,"evidence_quote":"Provides the gradient-like descent sequence framework and the KL-based global convergence and rate theorems that the paper invokes directly."},{"cited_title":"Conditional gradient algorithmsfor rank-one matrix approximations with a sparsity constraint,","cited_arxiv_id":null,"evidence_quote":"Gives the conditional-gradient unit-step algorithm and the base convergence results (Theorem 2.4) that the paper extends to last-iterate convergence."},{"cited_title":"Proximal alternating linearized minimization for nonconvex and nonsmooth problems,","cited_arxiv_id":null,"evidence_quote":"Defines the gradient-like descent sequence conditions used to connect GFW to KL theory."},{"cited_title":"Machine learning via polyhedral concave minimization,","cited_arxiv_id":null,"evidence_quote":"Establishes finite convergence for unit-step FW over polytopes, the polyhedral result that the non-polyhedral theorem generalizes."},{"cited_title":"The łojasiewicz inequality for nons- mooth subanalytic functions with applications to subgradient dynamical systems,","cited_arxiv_id":null,"evidence_quote":"Supplies the KL property for nonsmooth subanalytic functions, covering the semialgebraic objectives and sets used in the applications."},{"cited_title":"Enhancing sparsity by reweightedℓ1 minimization,","cited_arxiv_id":null,"evidence_quote":"The reweighted $\\ell_1$ minimization algorithm that the paper recognizes as GFW and modifies into RWL1 Split."},{"cited_title":"Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite program- ming,","cited_arxiv_id":null,"evidence_quote":"The Max-Cut SDP relaxation whose low-rank factorized form is the target of the new parallel GFW algorithm."},{"cited_title":"A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization,","cited_arxiv_id":null,"evidence_quote":"Introduces the low-rank factorization used to convert the SDP into the sphere-constrained nonconvex model."}],"review_version":1}