{"id":"82e34d5f-a76c-41b4-a80a-da04d3012d82","arxiv_id":"2501.16815","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"New one-step optimal entry and exit rules for greedy subset selection give consistent empirical gains, but the entry rule overlaps with classical forward selection and with SMP.","lead":"The authors derive replacement rules for greedy feature selection and elimination in best-subset selection by solving the exact one-step least-squares subproblem. Their enhanced OMP, CoSaMP, and ABESS variants beat the originals in experiments, but the selection rule is essentially the classical forward-selection F-statistic.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"CoSaOP convergence proof (Thm 4.9) rests on an unjustified extra assumption (App. I, Assumption 4) that is not implied by RIP and effectively assumes exact support recovery; the claim of preserved theoretical guarantees is therefore not established.","rationale":"I read the paper's central claim as twofold: (i) criteria (8) and (10) are the optimal one-step selection/elimination rules, and (ii) substituting them into existing greedy algorithms preserves the original algorithms' theoretical guarantees while yielding empirical gains at no extra cost. Part (i) is mathematically correct; it is a standard least-squares updating identity, and the paper's Theorems 4.1 and 4.2 are true. This also means the claimed novelty is limited—the paper acknowledges SMP in Remark 3.8, and the criteria are essentially the F-to-enter/F-to-remove statistics. Part (ii) is where the argument breaks. The only preservation proof offered in the main text is for CoSaOP, and its elimination lemma (4.7) requires Assumption 4 in Appendix I. I checked the appendix: this assumption is not a consequence of RIP; under the cardinalities involved it is equivalent to stating that the pruning set equals the true support, which is the very property the iteration is supposed to converge to. The proof of Lemma 4.7 also misstates the decomposition of ||β*−a||, though a valid version with δ=1 follows once Assumption 4 is granted. Without Assumption 4, a true feature with a large coefficient can be dropped by criterion (10) even when a is already accurate, so the linear rate is not established. The computational-cost claim is overstated in the abstract, but the paper's own Appendix O shows only a small overhead and Theorem 4.3's 'same order' claim can be defended with careful implementation that avoids forming the n×n matrix H. The empirical evaluation is extensive and appears to support the practical value of the criteria, so I do not think the paper should be rejected. Rather, the authors should either prove Assumption 4 from the algorithm dynamics, weaken the preservation claim to what is actually proven, or supply an RIP-based argument for the pruning step. This matches the reader's conditional verdict, so no adjustment is needed.","tokens_in":28333,"tokens_out":18042,"duration_ms":145077,"concrete_test":"Use a Gaussian design X of size 200×1000, normalized to satisfy RIP with δ≤0.1 (verified numerically), pick a K-sparse β* with K=5 and a starting support missing one true index, and run CoSaOP (Algorithm 2) with small noise. At every iteration, check whether supp(β*)∩U ⊆ S_k, equivalently whether Assumption 4 holds. If any iteration violates it, record the ratio ||β* − ã_{S_k}||/||β* − a||. If the ratio exceeds 3 while ||β* − a|| is small in any run, Lemma 4.7 fails without Assumption 4, and Theorem 4.9's guarantee cannot hold unconditionally.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The most load-bearing weakness is in the proof that CoSaOP preserves CoSaMP's linear-convergence guarantee. Theorem 4.9 chains Lemmas 4.4–4.8, but Lemma 4.7 relies on Assumption 4 in Appendix I: supp(β*) ⊆ (S_k △ supp(ã_K))^c. This condition is not derived from the stated RIP δ≤0.1, and it is much stronger than Lemma 4.4's energy bound. Since S_k, supp(ã_K), and supp(β*) all have cardinality K, the condition forces S_k = supp(ã_K) and, whenever any true feature is in U, also S_k = supp(β*) (the symmetric difference would otherwise contain a true index). Thus Assumption 4 assumes exactly that the new elimination rule (10) has already recovered the true support. Without it, a true feature with a large coefficient can be dropped by criterion (10) even when a ≈ β*, making the post-pruning error ||β* − ã_{S_k}|| comparable to that large coefficient and violating the bound ||β* − ã_{S_k}|| ≤ (2+δ)||β* − a||. Lemma 4.4's identification guarantee only bounds the energy of β* outside U; it says nothing about whether every true index in U survives the pruning step. Hence Theorem 4.9's linear rate is not proven, and the abstract's claim that the enhanced algorithms 'preserve the theoretical properties of the original algorithms' is unsupported for CoSaOP. The one-step optimality theorems (4.1, 4.2) are correct but classical, so the distinctive claimed contribution is the preservation of guarantees; this is exactly where the proof fails.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript proposes two new criteria for best-subset selection: a selection criterion (8) and an elimination criterion (10), obtained by solving one-entry and one-exit least-squares subproblems exactly via forward and backward matrix-inversion formulas. The paper proves that these criteria give per-step optimal decisions (Theorems 4.1 and 4.2), claims that substituting them into OMP, CoSaMP, and (A)BESS preserves the original algorithms' theoretical guarantees while achieving substantial empirical gains, and reports experiments on compressed sensing, sparse regression, column subset selection, and line-spectrum estimation.","tokens_in":28760,"tokens_out":7539,"duration_ms":68234,"significance":"The algebraic derivations of (8) and (10) are clean, the per-step optimality theorems are correct, and the correlated-feature counterexample in Theorem 4.11 provides a concrete demonstration of a real failure mode of Wald-T-based pruning. The experimental evaluation is extensive, with multiple datasets, metrics, and runtime comparisons, and the authors provide code and detailed appendices. The contribution would be substantial if the guarantee-preservation claim were established. However, as detailed below, the preservation claim currently rests on an extra assumption about the new elimination rule, so the main theoretical selling point is not yet proven.","major_comments":[{"comment":"The convergence proof for CoSaOP is not established because Lemma 4.7 relies on Assumption 4 in Appendix I: supp(β*)⊆(S_k △ supp(ã_K))^c. This assumption is not derived from the RIP condition δ≤0.1 used in Lemma 4.4, nor from any earlier result. In the sparse-recovery setting S_k, supp(ã_K), and supp(β*) all have cardinality K, so in the generic case where a true index lies in S_k, the assumption forces S_k = supp(ã_K) and S_k = supp(β*); that is, it assumes that the new elimination criterion (10) has already recovered the true support and that pruning does not remove any true index. If a true feature with a large coefficient were dropped, then ∥β*−ã_{S_k}∥ could be proportional to that large coefficient even when a≈β*, so the bound ∥β*−ã_{S_k}∥ ≤ (2+δ)∥β*−a∥ of Lemma 4.7 can fail by an arbitrarily large factor. Consequently, Theorem 4.9's linear convergence rate for CoSaOP is not proven, and the Abstract's claim that enhanced algorithms 'preserve the theoretical properties of the original algorithms' is unsupported for CoSaOP, which is the paper's worked example of preservation.","section":"§4, Lemma 4.7 / Appendix I, Assumption 4"},{"comment":"The claim that the enhanced algorithms achieve gains 'without increasing computational cost' overstates what is shown. Theorem 4.3 establishes only that the computational complexity is of the same order of magnitude, and Appendix O explicitly reports that the new criteria result in 'slightly higher computational time'. The abstract and conclusion should be reworded to claim 'same asymptotic order of complexity' rather than 'no increase in computational cost', so that the main text, the abstract, and the runtime data in Figure 5 are mutually consistent.","section":"Abstract / Conclusion / §5.1, Appendix O"},{"comment":"The proof of Theorem 4.11(2) ends with the sentence that criterion (10) 'will always identify Xp by Theorem 4.2'. This is stronger than what is proved. Theorem 4.2 states only that criterion (10) minimizes f(S\\{j}) over j in the current S; it does not by itself guarantee that the minimizer is the pseudo-correlated feature in every configuration satisfying the stated correlation condition. The specific 3×3 counterexample is sufficient to demonstrate the 'could' claim of the theorem, but the 'always' phrasing should be removed or supported by a separate argument.","section":"§4, Theorem 4.11(2) / Appendix M"}],"minor_comments":[{"comment":"Theorems 4.1 and 4.2 are immediate restatements of the derivations of (8) and (10); they should be explicitly described as per-step optimality statements rather than standalone convergence or recovery guarantees, to avoid overstating their role.","section":"§4, Theorems 4.1 and 4.2"},{"comment":"The appendix headings refer to 'Theorem 4.4', 'Theorem 4.5', etc., while the main text labels these results as Lemmas 4.4–4.8; the numbering should be harmonized.","section":"Appendix F / Appendix G / Appendix H / Appendix I"},{"comment":"The caption for Figure 5 should state explicitly whether the reported times are total wall-clock time over 500 runs or per-run averages, and the discussion of CoSaMP's larger runtime should be moved closer to the figure for clarity.","section":"Appendix O, Figure 5"},{"comment":"There is a typo 'signiaficant' in Section 5.1.1 and 'pseudo-correlated' is misspelled in Theorem 4.11(2); these should be corrected in the revision.","section":"§5.1.1, Appendix P"}],"recommendation":"major_revision","confidential_remarks":"The paper is promising: the criteria are cleanly derived, the experiments are thorough, and the empirical meta-gains are consistent across many tasks. The main obstacle is the unproved Assumption 4 in Appendix I, which is load-bearing for the claim that CoSaOP preserves CoSaMP's linear convergence guarantee. If the authors can prove Lemma 4.7 under the stated RIP conditions or alternatively present Theorem 4.9 as conditional on the elimination step being correct, the paper would be publishable after revision. The 'without increasing computational cost' wording should also be aligned with the same-order-of-magnitude claim and the runtime evidence."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: this is a useful paper, but the headline theory claim is not established. The optimization derivation of the selection and elimination criteria is correct, and the experiments are extensive and credible. The proof that CoSaOP preserves CoSaMP's linear convergence has a real gap that the authors do not flag in the main text.\n\nWhat's genuinely new: the unified derivation of criteria (8) and (10) as exact solutions of the entry/exit subproblems, and the meta-substitution framework that upgrades OMP, CoSaMP, and ABESS. The reader is right that (8) is essentially the classical F-to-enter statistic and (10) the backward elimination statistic, and Remark 3.8 concedes near-overlap with SMP. Theorems 4.1 and 4.2 are correct but definitional; they restate what the criteria were built to do. That is a minor issue.\n\nThe stress-test note holds up. Theorem 4.9's chain relies on Lemma 4.7, whose proof uses Assumption 4 in Appendix I: supp(β*) ⊆ (S_k △ supp(ã_K))^c. This is not derived from RIP δ≤0.1, and because all three sets have cardinality K, it effectively forces S_k = supp(ã_K) and, when any true feature lies in U, S_k = supp(β*). That is, the assumption says the new elimination rule has already found the true support. Without it, a true feature in U can be pruned, and the bound ∥β*−ã_{S_k}∥ ≤ (2+δ)∥β*−a∥ fails. So the linear convergence rate for CoSaOP is not proven, and the abstract's 'preserve the theoretical properties' is unsupported for that algorithm. The paper needs to either prove Assumption 4 from RIP or state it as an extra condition and adjust the claim.\n\nSecond concern: 'without increasing computational cost' is overstated. Appendix O shows the new criteria take slightly more time; same order of magnitude, not zero overhead. That is a wording fix, not a deep flaw.\n\nThird: no comparison with SMP. Given Remark 3.8, that is a notable omission.\n\nWho this is for: people working on greedy best-subset selection, compressed sensing, and sparse regression. The algorithm family and experiments are valuable; OP and OP-(A)BESS look genuinely stronger on correlated problems, and the code is public. But the theory section needs work. I'd send it to review, with a request to fix the CoSaOP argument or clearly label Assumption 4 as an additional hypothesis, tone down the cost claim, and add the SMP comparison. I would not build on the CoSaOP theory as it stands.","headline":"Solid greedy-selection upgrade with credible experiments, but the CoSaOP convergence claim rides on an assumption that smuggles in the true support.","tokens_in":29219,"tokens_out":3457,"would_cite":false,"duration_ms":30071,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C27","90C59","62J05"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proposes two objective-based criteria—one for adding features, one for removing them—that are provably optimal for the current support-set update, and shows that substituting them for classical criteria in greedy algorithms…","keywords":["best subset selection","feature selection","feature elimination","greedy algorithms","compressed sensing","sparse regression","optimal pursuit","meta-substitution"],"falsifier":"Take a small design matrix and a sparse vector, enumerate $f(S\\cup\\{j\\})$ for every $j\\notin S$ and $f(S\\setminus\\{j\\})$ for every $j\\in S$ by fitting least squares on each candidate support, and check that the indices selected by criteria (8) and (10) attain the minima; the first violation would refute Theorems 4.1 and 4.2. For the convergence-preservation claim, construct a design matrix with restricted-isometry constant 0.1 where the true support intersects the disagreement set in the CoSaOP proof and run CoSaOP; a residual sequence that fails the claimed linear bound would refute Theorem 4.9 as stated.","tokens_in":28135,"feed_emoji":"📈","tokens_out":11281,"duration_ms":93225,"temperature":0.7,"pith_summary":"This paper is about the two choice points inside every greedy best-subset-selection algorithm: which feature to add and which feature to drop. The paper's central claim is that the classical rules—maximizing correlation with the residual for entry, minimizing a Wald/T-style statistic for exit—solve only a partial version of the update problem, because they ignore the coefficient refit that follows the support change. Solving the full one-entry and one-exit least-squares subproblems produces two new criteria (labeled (8) and (10)) that account for interactions among features, and Theorems 4.1 and 4.2 show that the chosen index truly minimizes the least-squares objective over all possible entries or exits from the current support. Using these criteria in place of the classical ones yields enhanced versions of OMP, CoSaMP, and (A)BESS—named OP, CoSaOP, and OP-(A)BESS—that the paper argues preserve the original convergence guarantees while delivering large gains in signal-recovery success, NMSE, R-squared, and runtime. A sympathetic reader would take the central contribution to be a general 'swap in better criteria' principle for subset selection, not just three improved algorithms.","feed_headline":"Optimal entry/exit rules lift sparse-subset selection at no extra cost","feed_subtitle":"Objective-based pick/drop rules beat correlation and t-statistic rules on recovery and R-squared, at the same cost.","key_machinery":"The load-bearing object is the support-restricted least-squares value $f(S)=\\min_{\\operatorname{supp}(\\beta)=S}\\|y-X\\beta\\|_2^2$, whose one-step behavior the new criteria optimize exactly. The mechanical engine is a pair of matrix-inverse update lemmas: the forward inverse (Lemma 3.2) writes $(X_S^{\\top}X_S)^{-1}$ for $S=S_{k-1}\\cup\\{j\\}$ as a rank-one update of the already-available inverse $C_{k-1}$, converting the exact selection subproblem into the explicit criterion (8); the backward inverse (Lemma 3.10) performs the matching downdate for $S=S_{k-1}\\setminus\\{j\\}$, yielding criterion (10). These lemmas are what keep the new criteria at the same computational order as the classical ones: the required inverse or Cholesky factor was already computed when the coefficients on $S_{k-1}$ were fit, so the criteria add no new factorization cost.","core_discovery":"Stated on the paper's own terms, the discovery is that the classical selection and elimination rules of greedy subset selection are only first steps of block coordinate descent on the support-restricted least-squares objective $f(S)=\\min_{\\beta:\\,\\operatorname{supp}(\\beta)=S}\\|y-X\\beta\\|_2^2$. The classical entry rule (3) maximizes the immediate drop in $\\|y-X\\beta\\|^2$ from adding $j$ with all other coefficients frozen, and the exit rule (4) minimizes the immediate rise from deleting $j$ with other coefficients frozen; the subsequent coefficient refit is invisible to both rules. The paper formulates the exact subproblems (P1) and (Q1), in which coefficients are refit after the support change, solves them in closed form, and obtains criterion (8) for entry and criterion (10) for exit. Theorem 4.1 then states that the index $j^*$ from (8) satisfies $f(S\\cup\\{j^*\\})\\le f(S\\cup\\{j\\})$ for every candidate $j$ outside $S$, and Theorem 4.2 states the symmetric statement for (10) and deletion. Replacing criteria throughout existing algorithms yields OP, CoSaOP, and OP-(A)BESS; Theorem 4.9 gives CoSaOP a CoSaMP-style linear convergence rate under RIP, and Theorems 4.10 and 4.11 quantify advantages over the classical rules when features are correlated.","pith_inferences":["Inference: the entry criterion (8) is effectively correlation with the residual after the current support's contribution is projected out, so the same logic should transfer to matching-pursuit variants beyond the three tested families, such as LARS-style or kernel-based greedy fits; this is a direct extension the paper does not run.","Inference: the elimination criterion (10) is a support-agnostic pruning rule, so it could be used as a generic post-processing or inner-loop step in any local-search subset-selection solver, not only in greedy pipelines; the authors' 'meta-substitution' language suggests this, but the experiments only cover three families.","Inference: the Optimal Gradient Pursuit appendix hints that the exact-subproblem principle extends to non-quadratic objectives; a testable formulation would define entry and exit gains relative to gradient updates with exact line search and compare against current greedy methods on logistic or quantile losses.","Inference: the claimed same-order cost depends on the current-support inverse being available; in ultra-high-dimensional settings where even forming the projection in criterion (8) is prohibitive, the paper's own Optimal Gradient Pursuit version is the practical route, but its one-step optimality is not proved to the same standard as Theorem 4.1."],"forward_implications":["Theorems 4.1 and 4.2 make the one-step choices optimal: at a given support $S$, the selected entry or exit index produces the smallest possible support-restricted least-squares objective among all candidates.","Meta-substitution turns the paper's criteria into a general recipe: any greedy subset-selection algorithm that uses correlation-based entry or T-statistic exit can be upgraded, and the paper demonstrates this for OMP, CoSaMP, and (A)BESS.","Because both new criteria reuse the inverse already computed for the current support, OP, CoSaOP, and OP-(A)BESS stay in the same computational-complexity class as their classical counterparts.","Under restricted-isometry assumptions, CoSaOP inherits a CoSaMP-style linear convergence bound, with the constants the paper computes in Theorem 4.9.","In the correlated-feature regime where RIP fails, criterion (8) has a lower bound that grows as the correlation between two true features approaches one, while the classical criterion's upper bound shrinks to zero; criterion (10) can identify pseudo-correlated spurious features for removal."],"supporting_citations":[{"why":"It supplies CoSaMP and the RIP-based convergence lemmas whose linear-convergence property the CoSaOP proof is built to preserve.","marker":"(Needell & Tropp, 2009)"},{"why":"It introduces ABESS and the forward/backward sacrifice definitions that motivate the paper's optimization-based critique and provide the (A)BESS benchmark.","marker":"(Zhu et al., 2020)"},{"why":"It defines OMP and its correlation-based selection rule, the classical entry criterion being replaced.","marker":"(Pati et al., 1993)"},{"why":"It supplies the RIP-parameter and identification-step arguments underlying the CoSaOP identification lemma.","marker":"(Tropp & Gilbert, 2007)"},{"why":"It defines gradient pursuit, the method that the appendix's Optimal Gradient Pursuit extension upgrades.","marker":"(Blumensath & Davies, 2008)"}],"fun_headline_variants":["Exact entry/exit rules beat correlation and t-stat heuristics","Optimal selection criteria: refit after support change at no extra cost","Greedy rules upgraded: optimal entry/exit with coefficient refit","Refit-based entry/exit criteria: optimal for subset selection","Proof: refitting after support change yields optimal selection rules"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is an extra disjointness condition in the CoSaOP proof—the true support must avoid every index where the elimination rule's output and the best K-sparse approximation to the current fit disagree—and the paper does not show this follows from its stated restricted-isometry bound.","fun_headline_variants_meta":{"raw":{"variants":["Exact entry/exit rules beat correlation and t-stat heuristics","Optimal selection criteria: refit after support change at no extra cost","Greedy rules upgraded: optimal entry/exit with coefficient refit","Refit-based entry/exit criteria: optimal for subset selection","Proof: refitting after support change yields optimal selection rules"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001378,"raw_usage":{"total_tokens":5614,"prompt_tokens":1006,"completion_tokens":4608,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":622,"completion_tokens_details":{"reasoning_tokens":4518}},"tokens_in":622,"tokens_out":4608,"duration_ms":28572,"temperature":1.0,"reasoning_tokens":4518,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T10:29:45.343578+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a small design matrix and a sparse vector, enumerate $f(S\\cup\\{j\\})$ for every $j\\notin S$ and $f(S\\setminus\\{j\\})$ for every $j\\in S$ by fitting least squares on each candidate support, and check that the indices selected by criteria (8) and (10) attain the minima; the first violation would refute Theorems 4.1 and 4.2. For the convergence-preservation claim, construct a design matrix with restricted-isometry constant 0.1 where the true support intersects the disagreement set in the CoSaOP proof and run CoSaOP; a residual sequence that fails the claimed linear bound would refute Theorem 4.9 as stated.","supporting_citations":[{"cited_title":"and Tropp, J","cited_arxiv_id":null,"evidence_quote":"It supplies CoSaMP and the RIP-based convergence lemmas whose linear-convergence property the CoSaOP proof is built to preserve."},{"cited_title":"A polynomial algorithm for best-subset selection problem","cited_arxiv_id":null,"evidence_quote":"It introduces ABESS and the forward/backward sacrifice definitions that motivate the paper's optimization-based critique and provide the (A)BESS benchmark."},{"cited_title":"C., Rezaiifar, R., and Krishnaprasad, P","cited_arxiv_id":null,"evidence_quote":"It defines OMP and its correlation-based selection rule, the classical entry criterion being replaced."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"It supplies the RIP-parameter and identification-step arguments underlying the CoSaOP identification lemma."},{"cited_title":"and Davies, M","cited_arxiv_id":null,"evidence_quote":"It defines gradient pursuit, the method that the appendix's Optimal Gradient Pursuit extension upgrades."}],"review_version":1}