{"id":"b23ddac6-377e-432a-b569-5db3159e32dd","arxiv_id":"2506.08558","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"An iterative hard-thresholding variant with a two-step projection offers global objective-value guarantees for sparse optimization with support-preserving convex constraints, including the first zeroth-order hard-thresholding bound without system error.","lead":"This paper gives a sparse optimization algorithm that combines top-k truncation with a projection onto an extra convex constraint, and proves global convergence bounds for it. The bounds cover deterministic, stochastic, and zeroth-order settings, and the zeroth-order result removes an error term left by previous work.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3.7 omits the necessary condition wbar in Gamma; as printed it is false, so the central guarantee needs a feasibility fix before acceptance.","rationale":"The paper's real contribution is a global objective-value guarantee for IHT with support-preserving constraints, and the technical engine, Lemma 3.6, is elegant and appears internally consistent under the intended feasible-comparator reading. However, the theorem statements as written are stronger than what is proved, and are actually false in a simple example. This is more decisive than the restrictiveness of Definition 2.3: support-preservation is a scope limitation, whereas the omitted wbar in Gamma is a correctness defect. The reader noted this issue in the rationale but selected support-preservation as the weakest assumption, so my agreement is partial. A concrete two-dimensional counterexample settles the point, and the repair is to add wbar in Gamma cap B0(kbar) to Theorems 3.7, 4.3, and 4.8, and to remove the 'without loss of generality' claim about nonnegativity, which is invalid for multiplicative objective bounds. With that repair, the proof structure appears sound, so the correct outcome remains conditional acceptance rather than rejection.","tokens_in":63350,"tokens_out":10952,"duration_ms":134629,"concrete_test":"Construct the two-dimensional quadratic R(w) = ||w - e_1||^2 with Gamma = {0}; set k = 4, kbar = 1, rho = 0.5, eta = 1/2, and wbar = e_1. Run Algorithm 1 from any w0 for T satisfying the theorem's bound. Since every iterate is 0 and R(0) = 1, the printed guarantee min_t R(w_t) <= eps fails for eps < 1. Re-running the same test with wbar = 0 in Gamma shows the claimed bound holds, isolating wbar in Gamma as the missing hypothesis.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central theorem 3.7, and its stochastic and zeroth-order analogues, are stated for 'wbar an arbitrary kbar-sparse vector', but Lemma 3.6 and the proof's non-expansiveness step require wbar in Gamma. Without this hypothesis the theorem is not merely missing a phrase, it is false. Take R(w) = ||w - e_1||^2, Gamma = {0}, kbar = 1, k = 4, rho = 0.5, and L_s = nu_s = 2. Gamma is support-preserving (every projection is 0), and R is nonnegative and satisfies RSC/RSS. Algorithm 1 projects every iterate onto {0}, so R(w_t) = 1 for all t, while wbar = e_1 is 1-sparse with R(wbar) = 0. The printed theorem predicts min_{t<=T} R(w_t) <= eps for arbitrarily small eps after T = O(log(1/eps)) iterations, which is false. The 'further, if wbar is a global minimizer of R over B0(k)' claim fails identically, since e_1 is a global minimizer. The fix is to state all bounds for wbar in Gamma cap B0(kbar), as Table 1 does; under that intended reading the proof is coherent. A secondary statement issue: 'R non-negative (without loss of generality)' is not WLOG for multiplicative bounds: shifting R by a constant c changes the right-hand side by 2*rho*c.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies sparse optimization with an additional convex 'support-preserving' constraint set Γ, proposing an iterative hard-thresholding algorithm whose projection step first hard-thresholds to k-sparsity and then projects onto Γ. The main theoretical contribution is a constrained three-point lemma (Lemma 3.6) and its use in proving global objective-value guarantees for deterministic, stochastic, and zeroth-order variants under restricted strong convexity/smoothness assumptions. The headline results are Theorems 3.7, 4.3, and 4.8, which give bounds of the form R(ŵ) ≤ (1+2ρ)R(w̄)+ε with sparsity level k = O(κ²k̄/ρ²), and, in the zeroth-order case, a claimed removal of the non-vanishing system error present in de Vazelhes et al. (2022).","tokens_in":63634,"tokens_out":7626,"duration_ms":92811,"significance":"If the theorem statements are corrected, the paper makes a genuinely useful contribution: it provides a proof framework that unifies and simplifies existing IHT analyses, extends global sub-optimality guarantees to a natural class of mixed ℓ0-plus-convex constraints, and improves the zeroth-order IHT literature by eliminating a non-vanishing system error. The core three-point lemma (Lemma 3.6) is a real technical innovation, and the proofs are well structured and largely self-contained, importing known relative-concavity and zeroth-order estimator results from the literature rather than introducing fitted constants. The paper also ships reproducible code and useful experimental illustrations, and its Table 1 gives a clear comparison with prior work. The main caveat is that the theorem statements, as printed, omit a required feasibility hypothesis, and one 'without loss of generality' assertion is not valid for the multiplicative bound being proved; both issues are fixable without changing the proof strategy.","major_comments":[{"comment":"As stated, Theorem 3.7 asserts a bound for 'an arbitrary k̄-sparse vector w̄', but the proof (Lemma 3.6, and the non-expansiveness step in App. E.2.2, Eq. (12)) requires w̄ ∈ Γ. Without this hypothesis the theorem is false. For example, take R(w)=‖w−e₁‖², Γ={0}, k̄=1, k=4, ρ=0.5, L_s=ν_s=2. Γ is support-preserving, R is non-negative and satisfies (2,8)-RSC/RSS, Algorithm 1 projects every iterate onto {0}, so R(w_t)=1 for all t, while w̄=e₁ is 1-sparse with R(w̄)=0. The printed bound min_{t≤T} R(w_t) ≤ ε for arbitrarily small ε is therefore false, and the 'further' global-minimizer claim fails identically since e₁ is a global minimizer of R over B0(4). The fix is to state all bounds for w̄ ∈ Γ ∩ B0(k̄), exactly as Table 1 does; under that intended reading the proof is coherent. The same missing hypothesis appears in Theorems 4.3 and 4.8, whose proofs use Lemma 3.6 and the same non-expansiveness argument.","section":"Theorem 3.7 and Theorems 4.3, 4.8"},{"comment":"The phrase 'R is non-negative (without loss of generality)' is not a valid WLOG reduction for the multiplicative bound R(w_t) ≤ (1+2ρ)R(w̄)+ε. If one shifts R to R+c, the right-hand side becomes (1+2ρ)(R(w̄)+c)+ε, which is not equivalent to the original target inequality; the residual 2ρc does not vanish when translating back. Non-negativity is used only to drop the term ρR(v_t) in the proofs, so it should be stated as an explicit assumption on the original R (or the proof should be modified to handle a lower-bound assumption directly).","section":"Theorems 3.7, 4.3, 4.8 and proofs (App. E.2.2, F.2.3, F.4.3)"},{"comment":"The 'further' claim in Theorem 3.7 (and its analogues in Theorems 4.3 and 4.8) assumes that w̄ is a global minimizer of R over B0(k) while w̄ was introduced as an arbitrary k̄-sparse vector. This is internally inconsistent: an arbitrary vector cannot be assumed to be a global minimizer. The intended meaning is presumably 'if the comparator w̄ in the preceding bound happens to be a global minimizer over B0(k)', but as written the statement invites the counterexample above, where e₁ is a global minimizer and the claimed conclusion fails. This should be reworded and the hypothesis w̄ ∈ Γ should be carried through.","section":"Theorem 3.7, 'Further' claim"}],"minor_comments":[{"comment":"The notation list in Appendix A states that ∥·∥ denotes the ℓ0 pseudo-norm, while Section 2 defines ∥·∥ as the ℓ2 norm; this is inconsistent and should be corrected.","section":"Appendix A"},{"comment":"Theorem 4.8 lists 'Assumption 2.3' among its hypotheses, but there is no Assumption 2.3 in the paper; the intended reference is Definition 2.3 (support-preserving set).","section":"Theorem 4.8 and Appendix F.4.3"},{"comment":"The proof of Lemma 3.6 would be easier to follow if it explicitly stated that v_k−w is zero on supp(v_k) and that Π_Γ(v_k)−v_k is supported inside supp(v_k); the current sentence 'which imply that ... have disjoint supporting sets' is correct but terse.","section":"Lemma 3.6 proof (App. E.1.4)"},{"comment":"In the multiclass logistic regression experiment description, the text reads 'We set set all other hyperparameters'; this is a typo and should be 'We set all other hyperparameters'.","section":"Section H.3"}],"recommendation":"major_revision","confidential_remarks":"The missing-feasibility counterexample in my report is decisive for the theorem statements as printed, but the intended proof is coherent once w̄ ∈ Γ ∩ B0(k̄) is added; this is a fixable statement-level error rather than a fundamental flaw. The non-negativity WLOG claim also needs a genuine correction in all three main theorems. I would not reject on either point, but they must be addressed before the paper can be accepted. The zeroth-order contribution and the three-point lemma are substantial enough to merit publication after revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: the paper has a real contribution—an extension of the three-point lemma to hard-thresholding plus a support-preserving convex constraint, with clean global objective-value bounds in deterministic, stochastic, and zeroth-order settings, and removal of the system error from de Vazelhes et al. (2022). But the central theorems as printed are false. Theorem 3.7 and its analogues assert the bound for any kbar-sparse wbar; they need wbar in Gamma. The stress-test counterexample is exactly right: take R(w)=||w-e_1||^2, Gamma={0}, k=4, kbar=1, rho=0.5. The two-step projection fixes every iterate at 0, so R(w_t)=1, yet R(e_1)=0. The theorem predicts convergence to eps arbitrarily small. It doesn't. Adding \"wbar in Gamma cap B0(kbar)\" fixes the statement, and that is what the proofs already assume in Lemma 3.6 and in the non-expansiveness step. The \"further, if wbar is a global minimizer over B0(k)\" claims inherit the same problem, since such a minimizer need not lie in Gamma.\n\nWhat's genuinely good: Lemma 3.6 is a neat and useful extension. It gives the first global objective-value guarantees for IHT with mixed sparse plus convex support-preserving constraints, and the rho-parameterized sparsity/sub-optimality trade-off is a nice addition. The zeroth-order result without system error is a genuine advance over de Vazelhes et al. (2022), even with Gamma = R^d. The proofs are concise; the paper is well-written and cites the relevant literature appropriately. Code is released and experiments are reproducible.\n\nThe soft spots are real but repairable. Besides the feasibility assumption, \"R non-negative (WLOG)\" is not WLOG for the multiplicative (1+2rho)R(wbar) bound; shifting R by a constant shifts the right-hand side by 2*rho*c. Either assume non-negativity unconditionally or state the additive-correction form. The support-preserving condition is restrictive—the probability simplex is a natural exception—but the paper is explicit about that limitation.\n\nWho should read this: people working on iterative hard-thresholding, sparse constrained optimization, or zeroth-order sparse methods.\n\nRecommendation: send it to peer review. The proof technique is sound under the intended feasibility hypothesis, and the fix is a small amendment, not a rewrite. As printed, though, the main theorems should not be accepted; the referee needs to insist on the corrected hypothesis.","headline":"Real technique and a real zeroth-order advance, but the central theorems as printed are false because they omit the condition wbar in Gamma; with that hypothesis added, the paper is conditionally acceptable.","tokens_in":64220,"tokens_out":3761,"would_cite":true,"duration_ms":43481,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C26","90C30"],"pacs":[],"model":"deepseek-v4-flash","headline":"Iterative hard thresholding with an extra convex constraint converges globally in objective value, at rate $O(\\kappa \\log 1/\\epsilon)$, when the constraint is support-preserving; the same proof removes the zeroth-order system error of…","keywords":["iterative hard thresholding","support-preserving set","two-step projection","three-point lemma","restricted strong convexity","zeroth-order optimization","stochastic optimization","sparse optimization"],"falsifier":"Run the deterministic algorithm on an RSC/RSS quadratic in dimension at least 3 with $k=1$ and $\\Gamma$ the standard simplex $\\{z: z\\ge 0, \\sum_i z_i=1\\}$. After one gradient step, hard-thresholding can select a single negative coordinate, and the simplex projection then assigns positive mass to several coordinates that $H_1$ had zeroed, so the two-step iterate leaves $B_0(1)$; if such an iterate appears under the theorem's parameter regime, the claimed guarantee cannot hold as stated.","tokens_in":63102,"feed_emoji":"🎯","tokens_out":12252,"duration_ms":121672,"temperature":0.7,"pith_summary":"Many sparse-optimization problems come with extra convex constraints—budget limits in portfolios, norm bounds in non-negative matrix factorization—and iterative hard thresholding (IHT) had no global sub-optimality guarantees for that mixed setting. This paper proposes a two-step projection that first hard-thresholds a gradient iterate to $k$ nonzero coordinates and then projects onto the convex set, and proves that the iterates converge in objective value to within $(1+2\\rho)R(\\bar{w})+\\epsilon$ in $O(\\kappa_s \\log(1/\\epsilon))$ iterations, provided the convex set is support-preserving. The same guarantee is extended to stochastic and zeroth-order versions, and the zeroth-order result removes a non-vanishing system error present in earlier work. The engine is a new three-point lemma for the non-convex two-step projection, which lets the proof telescope under restricted strong convexity and smoothness.","feed_headline":"Hard thresholding converges globally under extra constraints","feed_subtitle":"A support-preserving two-step projection reaches (1+2ρ)R(w̄)+ε in O(κ log 1/ε) steps, stochastic and zeroth-order included.","key_machinery":"The machinery is the two-step projection $\\bar{\\Pi}_\\Gamma^k(w)=\\Pi_\\Gamma(H_k(w))$: first keep the $k$ largest-magnitude coordinates (the hard-thresholding operator $H_k$), then take the Euclidean projection onto the convex set $\\Gamma$. When $\\Gamma$ is $k$-support-preserving, meaning the projection of any $k$-sparse vector never creates nonzeros outside its support, this two-step output lies in $B_0(k)\\cap\\Gamma$. The load-bearing identity is Lemma 3.6, the constrained $\\ell_0$ three-point inequality $$\\|\\bar{\\Pi}_\\Gamma^k(w)-w\\|^2 \\le \\|w-\\bar{w}\\|^2 - \\|\\bar{\\Pi}_\\Gamma^k(w)-\\bar{w}\\|^2 + \\sqrt{\\$\\beta$}\\|H_k(w)-\\bar{w}\\|^2, \\quad \\$\\beta$=\\bar{k}/k,$$ which extends the convex three-point lemma through the relative-concavity coefficient $\\sqrt{\\bar{k}/k}$ of hard thresholding and is what makes the telescoping convergence proof work.","core_discovery":"The central claim is Theorem 3.7: suppose $R$ is $(\\nu_s,s)$-restricted strongly convex and $(L_s,s)$-restricted smooth with $s=2k$, $\\Gamma$ is $k$-support-preserving, and $\\bar{w}$ is any $\\bar{k}$-sparse point in $\\Gamma$. For any $\\rho\\in(0,1/2]$ and $k\\ge 4(1-\\rho)^2 L_s^2/(\\rho^2\\nu_s^2)\\bar{k}$, Algorithm 1 with step size $1/L_s$ satisfies $\\min_{t\\le T}R(w_t)\\le(1+2\\rho)R(\\bar{w})+\\epsilon$ after $T=O(\\kappa_s\\log(1/\\epsilon))$ iterations, with $\\kappa_s=L_s/\\nu_s$. Theorem 4.3 proves the stochastic analogue with exponentially growing batch sizes, and Theorem 4.8 proves the zeroth-order analogue with exponentially growing numbers of random directions. In the zeroth-order case the paper claims the first convergence-in-risk guarantee without system error for a hard-thresholding algorithm, even when no extra constraint is present, improving on the result from (de Vazelhes et al., 2022).","pith_inferences":["The support-preserving condition silently excludes many natural constraints—for example the standard probability simplex, whose projection can turn zero coordinates positive—so the theorems should not be read as covering them; a support-expansion allowance would be needed.","The same three-point proof is likely to transfer to other non-convex projection operators such as group-sparse or low-rank hard thresholding, where comparable relative-concavity coefficients exist; that is the paper's own suggested but undeveloped direction.","A direct experiment can isolate the role of the assumption: on a non-support-preserving constraint, the two-step iterate may leave $B_0(k)\\cap\\Gamma$, and the objective gap should visibly fail to follow the predicted $(1+2\\rho)R(\\bar{w})+\\epsilon$ envelope."],"forward_implications":["Deterministic IHT-2SP reaches $\\min_{t\\le T}R(w_t)\\le(1+2\\rho)R(\\bar{w})+\\epsilon$ in $O(\\kappa_s\\log(1/\\epsilon))$ iterations whenever $k\\ge 4(1-\\rho)^2L_s^2/(\\rho^2\\nu_s^2)\\bar{k}$, so no closed-form projection onto the mixed constraint is needed.","The stochastic variant matches the same rate with exponentially increasing batch sizes; the number of gradient calls to reach $\\epsilon$ is $O(\\kappa_s/(\\nu_s\\epsilon))$.","The zeroth-order variant delivers a convergence-in-risk bound without system error, with query complexity that is dimension-independent when the random directions sample the full space.","A small $\\rho$ gives a tighter factor $(1+2\\rho)$ but demands a larger sparsity relaxation $k\\propto 1/\\rho^2$; this explicit trade-off is the paper's mechanism for balancing sub-optimality against iterate sparsity.","For sign-free sets such as $\\ell_p$ balls, the two-step projection equals the Euclidean projection onto the mixed constraint, so the theorems also globalize the guarantees of projected gradient descent in this mixed setting."],"supporting_citations":[{"why":"Supplies the relative-concavity coefficient $\\sqrt{\\bar{k}/k}$ for hard thresholding (their Lemma 4.1) on which the paper's two three-point lemmas are built.","marker":"(Liu & Foygel Barber, 2020)"},{"why":"Defines the RSC/RSS framework and the deterministic IHT convergence result that Theorem 3.4 re-proves and Theorem 3.7 extends.","marker":"(Jain et al., 2014)"},{"why":"Provides the zeroth-order gradient estimator and the earlier hard-thresholding guarantee with a non-vanishing system error that Theorems 4.7 and 4.8 remove.","marker":"(de Vazelhes et al., 2022)"},{"why":"Gives the stochastic gradient hard-thresholding result that Theorem 4.2 recovers with a simpler proof relying on the new three-point lemma.","marker":"(Zhou et al., 2018)"},{"why":"Defines sign-free symmetric convex sets, for which the two-step projection coincides with the Euclidean projection onto the mixed constraint.","marker":"(Lu, 2015)"},{"why":"Supplies Lemma F.3, the variance bound for minibatch gradient estimators with exponentially growing batch sizes used in the stochastic proofs.","marker":"(Mishchenko et al., 2020)"}],"fun_headline_variants":["Two-step projection achieves global sub-optimality for sparse sets","Hard-thresholding with global guarantees under extra constraints","New proof technique for two-step non-convex projections","Zeroth-order sparse optimization without system error","Stochastic and deterministic sparse optimization with global bounds"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The analysis collapses if the extra constraint ever turns a zero coordinate into a nonzero one when a sparse vector is projected onto it—the key inequality needs those supports to stay disjoint—and the theorem statements also silently require the reference point $\\bar{w}$ to lie in $\\Gamma$.","fun_headline_variants_meta":{"raw":{"variants":["Two-step projection achieves global sub-optimality for sparse sets","Hard-thresholding with global guarantees under extra constraints","New proof technique for two-step non-convex projections","Zeroth-order sparse optimization without system error","Stochastic and deterministic sparse optimization with global bounds"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000398,"raw_usage":{"total_tokens":2177,"prompt_tokens":1132,"completion_tokens":1045,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":748,"completion_tokens_details":{"reasoning_tokens":969}},"tokens_in":748,"tokens_out":1045,"duration_ms":11541,"temperature":1.0,"reasoning_tokens":969,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T05:09:03.386163+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the deterministic algorithm on an RSC/RSS quadratic in dimension at least 3 with $k=1$ and $\\Gamma$ the standard simplex $\\{z: z\\ge 0, \\sum_i z_i=1\\}$. After one gradient step, hard-thresholding can select a single negative coordinate, and the simplex projection then assigns positive mass to several coordinates that $H_1$ had zeroed, so the two-step iterate leaves $B_0(1)$; if such an iterate appears under the theorem's parameter regime, the claimed guarantee cannot hold as stated.","supporting_citations":[{"cited_title":"On iterative hard thresholding methods for high-dimensional m-estimation","cited_arxiv_id":null,"evidence_quote":"Defines the RSC/RSS framework and the deterministic IHT convergence result that Theorem 3.4 re-proves and Theorem 3.7 extends."},{"cited_title":"Zeroth-order hard-thresholding: Gradient error vs","cited_arxiv_id":null,"evidence_quote":"Provides the zeroth-order gradient estimator and the earlier hard-thresholding guarantee with a non-vanishing system error that Theorems 4.7 and 4.8 remove."},{"cited_title":"Efficient stochastic gradient hard thresholding","cited_arxiv_id":null,"evidence_quote":"Gives the stochastic gradient hard-thresholding result that Theorem 4.2 recovers with a simpler proof relying on the new three-point lemma."},{"cited_title":"Random reshuffling: Simple analysis with vast improvements","cited_arxiv_id":null,"evidence_quote":"Supplies Lemma F.3, the variance bound for minibatch gradient estimators with exponentially growing batch sizes used in the stochastic proofs."}],"review_version":1}