Best Subset Selection: Optimal Pursuit for Feature Selection and Elimination
Authors: Zhihan Zhu
Yanhao Zhang
Yong Xia
Venue: ICML 2025 poster (2025)
Keywords: Best Subset Selection
Feature Selection and Elimination
Optimal Criteria
Compressed Sensing
Sparse Regression
Primary area: general_machine_learning

Abstract: This paper introduces two novel criteria: one for feature selection and another for feature elimination in the context of best subset selection, which is a benchmark problem in statistics and machine learning. From the perspective of optimization, we revisit the classical selection and elimination criteria in traditional best subset selection algorithms, revealing that these classical criteria capture only partial variations of the objective function after the entry or exit of features. By formulating and solving optimization subproblems for feature entry and exit exactly, new selection and elimination criteria are proposed, proved as the optimal decisions for the current entry-and-exit process compared to classical criteria. Replacing the classical selection and elimination criteria with the proposed ones generates a series of enhanced best subset selection algorithms. These generated algorithms not only preserve the theoretical properties of the original algorithms but also achieve significant meta-gains without increasing computational cost across various scenarios and evaluation metrics on multiple tasks such as compressed sensing and sparse regression.

Best Subset Selection: Optimal Pursuit for Feature Selection and Elimination
Zhihan Zhu Yanhao Zhang'
Yong Xia
Abstract
coefficient vector B E Rexi is expressed as follows:
This paper introduces two novel criteria: one for feature selection and another for feature elimina- tion in the context of best subset selection, which is benchmark problem in statistics and machine learning. From the perspective of optimization, we revisit the classical selection and elimination criteria in traditional best subset selection algo- rithms, revealing that these classical criteria cap- ture only partial variations of the objective func- tion after the entry or exit of features. By formu- lating and solving optimization subproblems for feature entry and exit exactly, new selection and elimination criteria are proposed, proved as the optimal decisions for the current entry-and-exit process compared to classical criteria. Replac- ing the classical selection and elimination criteria with the proposed ones generates a series of en- hanced best subset selection algorithms. These generated algorithms not only preserve the the- oretical properties of the original algorithms but also achieve significant meta-gains without in- creasing computational cost across various sce- narios and evaluation metrics multiple tasks such as compressed sensing and sparse regression.
y X, +
(I)
where y E R represents the response vector, X E Rxxp is the design matrix, and E 1 denotes the measure- ment noise. In subset selection, simpler models with fewer predictors are often favored. The goal is to select a subset of features by identifying nonzero coefficients (i.e., Active Support Set S) in 33 that achieves balance between ac- curacy and model simplicity. This leads to the best-subset selection problem, which can be formulated as follows:
min L.p (3) - ly X,313 BERP
8. s. 11 K, (2)
2n
where K is maximum allowed sparsity level. Since problem (2) NP-hard (Davis et al., 1997), significant efforts have been directed toward developing polynomial-time approxi- mation algorithms (Dy & Brodley, 2000; Qian et al., 2015; Wei et al., 2015; Qian et al., 2017; Zhu et al., 2020).
Relaxation methods have been proposed to approx- imately solve (2) by replacing 4n penalty with smooth ap- proximations. Examples include Least Absolute Shrink- age and Selection Operator (LASSO) (Tibshirani, 1996), Adaptive LASSO (Zou, 2006), Smoothly Clipped Abso- lute Deviation (SCAD) (Fan & L.,, 2001), Minimax Con- cave Penalty (MCP) (Zhang, 2010), etc. However, these methods could be computational burdensome (Hazimeh & Mazumder, 2020; Needell & Tropp, 2009) and are also difficult to control the number of selected features.
1. Introduction
Subset selection is a classic topic in statistics and machine learning, with significant applications in feature selection (Kohavi& & John, 1997; Das & Kempe, 2011), sparse regres- sion (Miller, 2002; Das & Kempe, 2018), compressed sens- ing (Chen et al., 2001), maximum coverage (Feige, 1998) etc. Even in the era of large models, subset selection can effectively reduce training costs and enhance the instruction- following ability of large language models (LLMs) by se- lecting high-quality features (Wang et al., 2024).
Another widely used class of methods is greedy algorithms, known for their high computational efficiency and simplic- ity. These methods perform subset selection directly by selecting and eliminating basis based on feature importance. Notably, the criteria for feature selection and elimination in this category are generally consistent, differing only in the underlying combination strategies.
Correlation- Selection. Greedy algorithms typically select features based on their correlation with residuals, calculated as follows:
The fundamental multivariate linear regression model with
'Scoool of Mathematical Sciences, Beihang University, Beijing, China (Email: (zhihanzhu, yanhaozhang, yxia) @ eduaa.cdu.cn) Correspondence to: Yong Xia <yxia@buaa.ccuu.c.> buaa.cdu.cn>.
X,1
y ----33-111 5 argmax JES
(3)
1X,
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
where X, is the j-th column of X, S is the complement of support S, - denotes the updated coefficient on S, and

---

Best Subset Selection: Optimal Pursuit for Feature Selection and Elimination
r represents the residual step k. Representative methods include Matching Pursuit (MP) (Mallat & Zhang, 1993), Orthogonal Matching Pursuit (OMP) (Pati et al., 1993), CoSaMP (Needell & Tropp 2009), Least Angle Regres- sion (LARS) (Efron et al., 2004) and Adaptive Best-Subset Selection (ABESS) (Zhu et al., 2020), commonly used in compressed sensing and sparse regression.
2. Revisit Two Classical Criteria
In this chapter, we revisit two classical criteria (3) (4) from an optimization perspective and develop a unified optimiza- tion model to uncover their f'nddaeenaal characteristics.
The following viewpoints originate from ABESS (Zhu et al., 2020; 2022), which defined two types of sacrifices to mea- sure the variation of objective C, (3) _ 2n lly x
Wald-T Test Maaistics--asee Elimination. Feature elim- ination often relies the absolute value of Wald-T test statisties, defined as (here we assume the columns of X are centralized with zero mean for convenience):
1) Forward Sacrifice: For any j E S", the magnitude of adding variable j is defined as:
7 = C, (3) - C3 + D
1
18)- M M
|| Vl
(INY
X,312 - -1 -V-X3-X,i,18)
[T]]
where M Ma--1
j jES, (4)
2n
x
Xj
), X d 3/n
2
(5)
2n
where df serves as degree of freedom. Elimination often based on minimizing the T-statistic setting threshold for deletion. Algorithms such as Iterative Hard Thresholding (IHT) (Blumensath& & Davies, 2009). Hard Thresholding Pursuit (HTP) (Foucart, 2011). CoSaMP (Needell & Tropp, 2009) and Adaptive Best-Subser Selection (ABESS) (Zhu et al., 2020) employ this criterion to remove features.
where D is defined as a diagonal matrix with at the (j.j)-th entry, while all other entries are 0, d x() and f = argmin, ( + D't). It evaluates which features outside active set are significant.
2) Backward Sacrifice: For any j E S, the magnitude of removing variable j is defined as:
In general. greedy methods can be regarded as combi- nation of correlation-based selection and T-statistic-based elimination, with different strategies integrated to perform subset selection. However, criteria (3) and (4), according to their formulas, focus solely on the individual significance of features, neglecting their interaction with other features. A feature that appears important within the current active set might become less significant when the active set changes, and conversely, feature deemed less critical could gain im- portance under different active set configuration. However, the current criteria fail to capture these dynamic properties.
E = (3 - -D1(3) L. (3)
= 2n (1lY
x.3+ + +x,3,118 - -11y-1311
X (3,)²
(6)
2n
which quantifies the irrelevant features in the support set.
Intuitively, for j E S (or j E S²), a large value of & (or nj) suggests that the j-th variable is potentially important. Formally, we demonstrate the connection between (5) (6) and (3) (4) in the following remark. This equivalence can be immediately verified by substituting r* in d.
In this paper, we revisit two classical criteria from an opti- mization perspective. By precisely modeling the selection and elimination subproblems, we reveal that the existing classical criteria (3) and (4) merely represent partial (one- step) variation of objective function after the entry or exit of features, arising from solving the subproblems by block co- ordinate descent method. Under this perspective, two novel importance criteria are proposed by solving the subproblems exactly. The new criteria consider both the significance of the features and their interactions with other features in the current active set simultaneously. with which the feature entry-exit strategies are proved as optimal decisions in the current subset selection process. Substituting the traditional criteria (3) and (4) with the proposed ones generates series of enhanced best subset selection algorithms, which pre- serves their desirable theoretical properties (or even better) while achieving significant meta- veeas across a variety of tasks, scenarios and evaluation metrics.
Remark 2.1. The criteria in (5) and (6) are strictly equiva- lent (up to constant factor) to those in (3) and (4).
From an optimization standpoint, the existing criteria can be interpreted as the variation of objective function achieved by updating the support set with fixed coefficients in the first step of block coordinate descent. Specifically:
Step (Support update with fixed coefficient): Maximize the correlation in (3) (or minimize the T-statistics in (4)) for support set updating is equivalent to solving (PO) (or (Q0)). The classical criteria (3) and (4) corresponds to the variation of objective function value in this part.
Step 2 (Coefficient update with fixed support): It is fol- lowed by refining the coefficients on the updated support set. This step also leads to a change in the function value, which, however, is not captured by the classical criteria.
2

---

Best Subset Selection: Optimal Pursuit for Feature Selection and Elimination
SUBSET SELECTION
SUBSET ELIMINATION
A1. The old correlation- based criterion corresponds to the partial decrement of the objective function
B1. The old Wald-T statistics- based criterion corresponds the partial
increment of the objective function
Old Criterion Corviation lo Namall Decmenett
supp update
Old Criterion
New
cosf update
Maximum furetion decnaas..
Criterion
Oesechredeeed
Rirtal Inclarsen
update
Selection
coef update
Elimination
New Criterion digecterlssed
Minimam
angniny
y sippids J0
by API
1,
argitity
lb Aol expp(h1) mep(ptns)
Arrdee /
eappli
by 2P13 rppprt 10lls
[0t01
senciie
faation
1v x011 Sapp c sapo 1s 1, +b
A2. The propased objective based criterion corresponds the complete decrement of the objective function
B2. The proposed new objective- criterion corresponds the complete increment of the objective function
Old New
Selected by Old Criterton
Selected by Ciiteiio
Basis
Basis
Basis
Basis
Miniuum function Increex.
Selection
Masimum function
Elimination
DMjechv
Objeche bedtie/
f
Figure 1. (B) illustrates subset selection (elimination), with A1 (B1) comparing objectives and optimization problems of the old and new criteria, and A2 (B2) comparing function decreases (incrcases).
argmin
lly -x,3
(PO)
one step of block coordinate descent, rather than an objective that takes into account the overall descent.
113 - 38 1lo S 1, supp( c supp (B).
8. t.
This issue will be addressed the new model we develop in Section which ensures an optimal solution each step.
argmin g
lly - x,3113
(Q0)
3. Optimal Selection and Elimination Statistics
3 110 < 1, supp( C supp(
8. t.
3.1. Optimal Selection and Elimination Problem
As the model evolves to (PO) and (Q0), the limitations of classic criteria become more apparent. Specifically, it is ob- served that the constraints in (PO) and (Q0) (or equivalently, criteria (3) and (4)) only allows one change in the support set of B3 while the coefficients on the remaining support set are fixed. In the next step when coefficients are updated on newly selected support set, the influence of newly chosen feature on the remaining coefficients is not considered. The variation of function value in the first part measures the individual significance of the features, while the change in the second part assesses the interaction between features, where classical criteria fail to capture.
As analyzed in Section 2, to obtain the optimal solution at each step, we consider the following optimization problems:
argmin B
lly
X
(P1)
s. |13110 = =113-111 110 + 1, supp( c supp (3),
argmin
|yy - x,31|
(Q1)
3
t. ||1|| = ||g* '11o - 1, supp( C supp
Therefore, the update strategy in (PO) and (Q0) (or criteria (3) and (4)) can be understood as the objective of performing
where (PI) and (Q1) correspond to selection and elimination subproblems for each step exactly. Unlike the constraint in
3

---

Best Subset Selection: Optimal Pursuit for Feature Selection and Elimination
(PO), the constraint in (P1) does not require the coefficients fixed the remaining support set. Thus, compared to the incomplete descent obtained by one step of block coordinate descent with the classic criterion, the new optimization prob- lem consider a complete descent (including both step 1&2), providing the optimal feature selection criterion. Same ar- gument holds for the subset elimination problem in (Q1).
Lemma 3.2 can be obtained through simple matrix block operations. We can derive the following optimal feature selection criterion by applying Lemma 3.2.
Theorem 3.3. Problem (P2) is equivalens (in the sense of identifying the true subset) to:
(Ih2 X,)
)
argmax JESE x3
Figure provides an intuitive comparison between the later- derived new criteria (from (P1) (Q1)) and the classic criteria (3) (4) (from (PO) (Q0)), highlighting their differences in terms of objectives. In the selection subproblem, the goal is to select a feature that maximizes the overall decrease in the objective function, as illustrated in A1. However, the clas- sic criterion focuses solely on maximizing the immediate decrease after updating the support set, without account- ing for the impact of subsequent coefficient updates. This limitation is evident in A2, where the feature i, selected by classic criterion, achieves the largest initial decrease f2z but its subsequent updates result in less favorable outcomes.
1 1- -S-
X Sy Xse..) X Sk
X
(8)
where Sk-1 = -supp(ak-1)
The proof of Theorem 3.3 is provided in Appendix B. Definition 3.4 (Objective-based Selection). By Theorem 3.3, the new criterion for feature importance outside the support set could be formulated as criterion (8).
Remark 3.5. When X, is orthogonal to Xs.- the jejective-based selection criterion (8) degenerates into the correlation-base criterion (3).
Remark 3.6 (Comprehensive Combination Effect). It is ob- served that the numerator of the objective-based selection criterion (8) is identical to that of the classic criterion (3). However, the denominator in (8) incorporates a projection matrix, which accounts for the interaction between the cur- rently selected feature j and the remaining features in Sk-1- Specifically, new criterion (8) can be interpreted as the cor- relation between X, and r in the noise subspace of X As result, the new criterion captures a comprehensive "combination effect' in reducing the objective function.
Similarly, in the climination subproblem. the objective is to eliminate a feature that minimizes the overall increase in the objective function. As shown in B2, the classic criterion selects basis i because it results in the smallest immediate increase in the first step. However, after coefficient updates, the overall increase is much larger than that achieved by basis j. selected by new criterion.
3.2. Optimal Selection and Elimination Criteria
In this section, we solve (PI) and (Q1) to derive the optimal criteria for subset selection and elimination.
Remark 3.7 (Computational Efficiency). Theorem 3.3 trans- forms the large matrix (X]Xs) in (P2) into a smaller
3.2.1. OPTIMAL SELECTION CRITERION
matrix X Xss..) in (8). In fact, when we update the coefficients on the support set Sk-1 at step k - 1 using
We begin with deriving the optimal selection criterion. Lemma 3.1. Problem (PI) is equivalent to
least squares (X Xs... X .. this procedure St Xs._, or solving
argmax 3
y' Xx) X
(P2)
involves either matrix inversion of XT the corresponding linear system via Cholesky decomposi- tion. Notably, the inversion or Cholesky decomposition is required only once. Thus, despite the presence of an inver- sion term in the denominator of the new criterion (8), it does not incur additional magnitude of computational cost. We also perform runtime comparison between the algorithms using the classical criteria and the new criteria in Section 5, with only a slight difference, see Appendix O.
S. t. (U CS supp (B), 11 = 113
11o + 1,
where S is the support set of B, and Xs represents the X corresponding to the subset S.
columns X
The proof of Lemma 3.1 is detailed in Appendix A. Thus, problem (P1) is reformulated as (P2). A major challenge in solving (P2) is computing the inversion term (XfXs)
Remark 3.8. While writing this paper, we coincidentally came across the algorithm (SMP) with very similar criterion to (8) in (Tohidi al., 2025). We independently derived the criterion with the completely different approaches taken. In that paper, submodular perspective is used to derive replacement algorithm for OMP, whereas our derivation is grounded in an unified optimization framework, with a specific focus on both optimal feature selection and elimina- tion criteria. Moreover, in Section 3.3, we demonstrate that
To address this, we first introduce the following lemma.
Lemma 3.2 (Forward Inverse). Let t a - 'u +0 0,
B (Ain-L)x(n-1
where A is known in nxn advance. Then the inverse of B is given by:
V
B B-1 = ( A- +
-A-1+A-' ut A-A
- A utt
1- -1
1-1
4

---

Best Subset Selection: Optimal Pursuit for Feature Selection and Elimination
our criteria can be applied as a meta-heuristic method to all heuristic best subset selection algorithms.
coefficients on the support set Sk-1, so the inversion term in criterion (10) does not incur additional magnitude of com- putational cost. See Appendix O for comparison in runtime.
3.2.2. OPTIMAL ELIMINATION CRITERION
Similar to the selection problem, we make the following equivalent transformation to the original problem (Q1) in Lemma 3.9 and introduce Lemma 3.10 assist in deriving the optimal elimination criterion.
3.3. Enhanced Algorithms for Best Subset Selection
As mentioned in the Introduction, heuristic subset selection algorithms generally determine selection and elimination based on (3) and (4), with different algorithms arising from various combination strategies of these criteria. By lever- aging the optimal criteria in Section 3.2, we can perform Meta-Substitution of the objective- -baeed criteria (8) and (10) into classical algorithms like MP, OMP, CoSaMP, IHT, and (A)BESS, resulting in an enhanced algorithm family, as shown in Figure 2.
Lemma 3.9. Problem (QI) is equivalent to
argmax 3
Xs (x X5y
(Q2)
8. t. = supp (B) C supp(33-1), ), |181|0 = |1
llo 1.
Lemma 3.10 (Backward Inverse). Suppose B is known,
G ((n-1)x(--I)
w
The Old Algorithms
The Enhonced Algorithms
where B
z"
B
=
Iean uaver searly haarotic auttect aslection elpantters inclding MP OMP, Nr,, ARESS etc.
-Ape cnd gpeesh Aegeehhs sock mwwdeweing DMP OZ AMRST ARRES, et
axn
( (1-1))x( (1--))x(m-1)
Then the inverse of A could nxn
PRoporos wetery Stopping Citterion
Dhiighh maire.
Reupormec vestory Strpping Citenton
-Doign mudatr.
be updated as:
Select
Ellmination
Select Objactiv burtee
Elmiiettio
A- = G wwz /-
(9)
Corrizaiinn based
Criwdin [2]
Erieviin (4)
besed
>>>> >>>
Substitute
Catediin (2)
Objective desed
(10)
Lemma 3.10 is straightforward corollary of Lemma 3.2. We can derive the following optimal feature elimination criterion by applying Lemma 3.10.
Updato
Upditts
Support 5
Cootfcione,) 3
Support
Confidaars
Theorem 3.11. Let Ck-1 = (X Xs...) cj
Dutput
Output
Support 5
11)TT E R5 11, where j repre- (815, 82i,... ,,s.. ,,/5, .6ss sents the i-th element of Sk-1 f 1,2 1S The Kronecker delta function dab is defined as dab if b,
Figure 2. Left: The original algorithmic workflow based on heuris- tic subset selection criteria. Right: By replacing the classic criteria with optimal objective-based criteria, the original heuristic algo- rithms can he updated to yield new algorithms accordingly.
and dab = 0 otherwise. Then, problem (Q2) is equivalent (in the sense of identifying the true subset) to
We classify subset selection algorithms into three categories based on their combination strategies for feature selection and elimination, providing one representative for each to show how NetatSuustitution generates new algorithms:
argmax y" X'S. (I -e,ee,,) (C--1- jES
Cx-10,0, Cx-1) (I=))))) X X (10) e/ Ce-ee
Select-Only: This type of algorithm greedily selects feature at each step. Examples include MP, OMP, etc. For instance, OMP can be upgraded to Optimal Pursuit (OP) algorithm, as described in Algorithm 1 in Appendix E.
The proof of Theorem 3.11 is provided in Appendix C. Definition 3.12 (Objective-based Elimination). By The- orem 3.11, I, the new criterion for feature importance inside the support set could be formulated as criterion (10).
Select-First, Eliminate-Next: selects the features and then removes the irrelevant ones. Examples include CoSaMP, IHT, HTP, etc. For instance, CoSaMP can be enhanced to CoSaOP, as detailed in Algo- rithm in Appendix E.
This type of algorithms first
Remark 3.13. When X, and Xsx Ma) are orthogonal, the objective-based elimination criterion (10) degenerates into the Wald-T based criterion (4). A detailed proof is provided in Appendix D.
This class of algorithms performs sub- set selection by swapping irrelevant features in the active set with significant features outside the active set. Notably, (A)BESS (Zhu et al., 2020), currently serving as bench- mark method in the subset selection field, belongs to this category. It can be upgraded to the (P)(A)S algorithm, as outlined in Algorithm 3 and 4 in Appendix E.
Exchange- Based:
Remark 3.14 (Comprehensive Combination Effect). The new criterion (10) takes into account the impact on the other features in Sk-1 resulting from the elimination of feature j. Remark 3.15 (Computational Efficiency). The matrix Cg-1 or Cholesky decomposition of XT X_ss,, has been al- ready computed in the previous step when updating the
5

---

Best Subset Selection: Optimal Pursuit for Feature Selection and Elimination
Beyond these examples, other greedy subset selection al- gorithms can also be enhanced through meta substitution scheme. We will demonstrate that these enhanced algo- rithms not only retain the original theoretical properties but also achieve significant meta-gains across various tasks, scenarios and evaluation metrics.
Lemma 4.6 (Estimation). Let U be a set containing most 3K indices. The least-square. estimate a is formulated as
alv (x]xx)=
alu- =0.
Then, the following bound holds:
|1 -all2 S 1.112 1.112 1o e.02|
4. Theory of Optimal Subset Selection Criteria
Lemma 4.7 (Elimination). Let Sy. be the index set selected by CoSaOP from U according to criterion (10). Then,
In this section, we establish theory of optimal subset selec- tion criteria (8) and (10). Define the function fS) as:
11B
-as - (2 -al1
f(S) min lyy - X,31
/
where a = aj for E Sr. ās..j = 0 for j E S and 0 < is a constant related to the orthogonality of Xu- Lemma 4.8 (Least square estimation). Let 3 denote the least-square estimation on Sy obtained by CoSaOP. We huve
8. t. supp((3) = S.
With this definition, we present the following theorems. Theorem 4.1. For index jr selected by criterion (8).
|| 30 1.106 | - -as, l12 + 2.100999// |c|l2.
f(Su s f S..
Theorem 4.2. For index j" selected by criterion (10),
Therefore, based on Lemmas 4.4-4.8, we arrive at the fol- lowing theorem.
(
Vjes.
Theorem 4.9 (CoSaOP). When the approximation error large in comparison with the noise, the CoSaOP algorithm achieves linear convergence rule, expressed as
Theorems 4.1 and 4.2 summarize the previous discussion, demonstrating that criteria (8) and (10) serve as the optimal decisions in the current subset selection process.
113 - 3- S (- + 14.482||
Theorem 4.3. The computational complexities of OMP and OP, CoSaMP and CoSaOP, as well as (A)BESS and OP- (A)BESS, are of the same order of magnitude.
In real-world scenarios, features are often highly correlated, making the RIP assumption, commonly used in classical best subset selection algorithms, invalid. Theorems 4.10 and 4. further demonstrate the significant advantages of criteria (8) and (10) over classical criteria (3) and (4) in the presence of high feature correlation. For the proofs and further explanations, please refer to the Appendices L-N.
Theorem 4.3 follows from Remark 3.7 and Remark 3.15, and it indicates that the enhanced algorithms have the same computational complexity as the original algorithms. Now, we take the CoSaOP algorithm (Select-First, Eliminate- Next) as an example to illustrate how the enhanced algo- rithms retain the theoretical properties of the original algo- rithm. The subsequent Lemmas 4.4 and Theorem 4.9 correspond directly to theoretical results of CoSaMP in (Needell Tropp. 2009).
Theorem 4.10. Suppose the true subset S contains indices (i.j), where the correlation between feature X; and X X
is p ||x. ||X||||||,,l Assuming the current support set S already includes feature i, then the classical correlation- based criterion for feature j satisfies:
The basic assumption and proofs of Lemmas 4.4-4.8 4.8 are pro- vided in Appendices F-J. And the proof of convergence prop- erty of CoSaOP (Theorem 4.9) is presented in Appendix K. Lemma 4.4 (Identificationn) The set Ω selected by CoSaOP during identification stage (Step 6 in Algorithm 2) at itera- tion l satisfies
T
X, SV1-
12-12111") 12,
(11)
1X
while the objective-based criterion (8) satisfies
( x
X
(8r - 3r) la 0.2353
- +2.4 |ellz-
| 1
X I I-
X3 X-X
(XFXs)
X, 1 p2
(12)
Lemma 4.5 (Support merger). Lei Q be a set containing at most 2K indices. Then, the set U = Q U supp( contains at most 3K indices, and it holds that
Theorem 4.11. (1) The upper bound of the objective- based criterion (10) is I If the true subset S is contained within the current subset S, then for all jm E S*
|| 1u-ll2 < 31(33 (²- 1ar
11yl12 - ||c|1 < (criterion (10) for Jm) S 11y112.
6

---

Best Subset Selection: Optimal Pursuit for Feature Selection and Elimination
And in noiseless scenario.
CoSaMP by at least 4x in all scenarios, with maximum improvement of nearly 7x under SNR 21, as shown in subplot (e), While (A)BESS, as the state-of-the-art algo- rithm for this task, demonstrates great performance across various settings, OP-(A) still manages to achieve ob- servable meta-gaing beyond it. Even in near-saturation sce- narios where (A)BESS achieves almost complete recovery, the meta-gain remains evident. Thus, the proposed algo- rithms (blue bars) consistently outperform their classical counterparts (green bars) across all experimental conditions, delivering significant improvements in recovery rates.
Im E argmaxjes objective-based criterion (10).
(2) Suppose a feature Xp in the current subset is pesudo- correlated with an important feature X, in the true sub- set (with correlation 1 - p)). When μu is sufficiently small, classical T-statistics based criteria (4) could erroneousty discard true features even in simple cases like S = S u {p), whereas proposed criterion (10) could correctly identify and remove the spurious feature Xp.
We also evaluate the algorithm's performance under high feature correlations to validate the theories through their marked improvements. See Appendix P for details.
We also compare the computational time in Appendix O. In Appendix P. we conduct further experiment under high fea- ture correlations with small sample sizes, high-dimensional features, and high noise levels. The experimental results further highlight the signiaficant advantages of the Optimal Pursuit-enhanced algorithms in extreme scenarios.
5. Experiments
We conducted experiments on two typical subset selection problems: compressed sensing and sparse regression, to demonstrate the meta-gains achieved by the new algorithms developed through meta-substitution. The comparison in- volves representative algorithms' from the three categories introduced in Section 3.3: OP, CoSaOP, and OP-(A)BESS, evaluated against classical subset selection methods: OMP, CoSaMP, and BESS Their performance is evaluated across multiple metrics, including the number of successful recoveries, NMSE, n², and runtime, highlighting the superi- ority of the enhanced algorithms from various perspectives.
5.1.2. SIGNALS FROM AudioSet
After transforming audio signals into the DCT domain, they exhibit transform sparsity (Donoho, 2006). There- fore, we test our method using real-world audio data. The data presented here is randomly sampled from the AudioSet dataset (Gemmeke al., 2017), consisting of 4 audio sig- nals with full dimensionality p = 480. These signals have approximately 20-40 non-zero entries (K) in the DCT do- main, with the number of observations fixed at = 150. The normalized mean squared error (NMSE), defined as NMSE = | - ||2/11 /|///|11113 1|2 is used to quantify the recov- ery performance. We conducted 100 random experiments, and the results are summarized in Table 1.
5.1. Compressed Sensing
In this task, there is a ground truth signal for B. The goal is to recover the high-dimensional sparse vector /3 E Rxx1 given the noisy low-dimensional observation y E Rox1 and design matrix X E RTxp
p (n < p).
The proposed algorithms consistently exhibit significant per- formance improvements. In particular, OP shows observable meta-gain compared to OMP. Although CoSaMP algorithm already performs well on this task (with small NMSE and std), CoSaOP still achieves provement. Similarly, OP-(A)BESS achieves near-order-of- magnitude improvements in both mean and std of NMSE in multiple trials, indicating that the algorithm's 's accuracy and stability have been significantly enhanced.
5.1.1. SYNTHETIC SPARSE DATA
In this experiment, we randomly generate 3 with a dimen- sionality of p 200 and sparsity level of K 10. The design matrix X is a X random Gaussian matrix. Let S" represent the true support set of the signal and Š the esti- mated support set, recovery is deemed successful if S = S*. For each algorithm, we conduct 500 independent runs and record the number of successful recoveries as shown in Fig- ure 3. The first row illustrates the variation in the number of successful recoveries for three groups of algorithms as the sampling rate increases from 25% to 50% under fixed SNR of 15. The second row, in contrast, fixes the sampling rate at 25% and shows how the number of successful recoveries changes as the SNR increases from 15 to 25.
-f--orddrrof-mgnitude- im-
5.2. Sparse Regression
In sparse regression tasks, / does not have a ground truth. The goal is to select sparse features that provide better explanation of target variable y. Therefore, similar to the metric used in sparse regression evaluations in (Qian et al., 2017; Das & Kempe, 2018), we quantify the explanatory ability of the features using Coefficient of Determination: R² = 1 Em / Ei ?.
As result, in the most extreme compressed scenario with measurement rate of 0.25, OP achieves nearly 3x im- provement over OMP. CoSaOP consistently outperforms
We utilize six real-world datasets in our experiments: (1) Boston Housing Data (Pedregosa et al., 2011), (2) California Housing Data (Pedregosa et al., 201 1), (3) Superconduc-
com/ Matlab codes are available at perrsuit_publice Zhi hannhu-maataa matarahhhttimaaa iaamaaarasiaaaaaaaa
7

---

Best Subset Selection: Optimal Pursuit for Feature Selection and Elimination
Owe
OP
Cubulii
Codace
(Aless
Compartaon and
Compattinn of Codalii and GodaOP
Comparteon JAJIESS and OP-A/BESS
500
540
590
400
440
403
304
500
314
300
Narn of Succanitu
300
200
500
288
144
100
Nure
Mare
Messurament Rarte
Rata
(a)
500
Nam Bercoestu Recoveree
540
Nim of Succouruu Rtacoertae
690
200
200
240
100
1X2
100
Num
27
15
17
19
21
23
23
15
19
21
23
25
17
10
21
23
25
(d)
(c)
(f)
Figure 3. Meta-gain comparison three kinds of subset selection algorithms. Row one: different sampling rates (SNR 15), Row two: Varying SNRs (measurement rate = 0.25).
Table Reconstruction NMSE (mean + std) for Signals from AudioSet. Meta-gains are highlighted in red, with the best in bold and the sccond- best underlined. (Audio 1-4: -SddVVK99g wav, wwxglqlluA.wwoooom. 5L wav, _00d66eeyJ4..aa
(OMP& OP)
NMSE (CoSaMP & CoSaOP)
((A)BESS & OP-(A)BESS)
Audio Set
OMP
OP
Gains
CoSaMP
CoSaOP
Gains
(A)BESS
OP-(AJBESS
Gains
Audio
9.45E-04 (1.35E-03)
7.69E-04
(8,784004)
19%
2.36E-03 (2E22))3)
1.64E-03 (1.36E-03)
31%
1.41E-03 (7.89E-33)
6.22E-04 (2.64E-04)
56%
Audio
5.79F-03 (7 03)
5,49I.00 03 (8.87E-03)
5%
1.87F.03 (6.05T-04) 04)
6.36E-04 (2.01E-04)
66%
6.71E-03 (6.07E 02)
6.36F.04 (2.01E-04)
91%
Audio 3
1.46E-03 (3.13E-03)
1.18E-03 (2.14E-03)
19%
1.545-03 (5.86E-04)
5.52E-04 (2.03E-04)
64%
2.84B-03
(2.29E-02)
5.52E-04 (2.03E-04)
81%
Audio 4
4.05E-02 (1 (..0-03-0)
3.55E-02 (9.70E-02)
12%
2.85E-03 (9. (48-4-0)4
8.22E-04 (2.22E-04)
71%
2.65E-02 (1.07E-01) 1.86E-02 (1.12E-01)
30%
tivity Data (Hamidich, 2018), (4) House 16H (Vanschoren,
6.1. Best Subset Selection with Ultra-high Dimensions: Optimal Gradient Pursuit
2014), (5) Prostate.ve Prostate.v..egee v8.egen (Lin & Pan, 2024; Hastic al., 2017), and (6) Spectra (The MathWorks, Inc., 2025). For the first five datasets, which have relatively small number of features, we augment the feature space by constructing polynomial features. The dimensions of the six datasets are as follows: n = 506, P1 = 104; n2 = 500 (randomly sam- pled). P2 = 164; n3 = 500 (randomly sampled), P3 = 80; n4 = 500 (randomly sampled), P4 153; ns 500 (ran- domly sampled), P5 253; and nıg 60, Pa 401.
As noted in Remark 3.7 and Remark 3.15, the algorith- mic complexity of the original methods and optimal pursuit-enhanced algorithm remains at the same order of magnitude, since both rely on solving the least squares problem over a given subset S, which involves a linear system solved via Cholesky decomposition. However, in Autra-high-dimensionn
settings, solving the least squares problem over a given subset, i.e., solving a linear system, can be computationally prohibitive, affecting both the origi- nal and enhanced algorithms. In fact, updating coefficients via least squares within a given subset is equivalent to using the Newton method for updates. (Blumensath & Davies, 2008) proposed Gradient Pursuit, which follows the same correlation- based selection strategy in the basis selection step. However, in the coefficient update step, instead of Newton's 's method, employs gradient-based updates within given support set, significantly reducing computational overhead in setra-highdiimmnsste
The experimental results in Figure 4 demonstrate the hanced algorithms driven by new criteria consistently yield significant meta-gains across different datasets and varying numbers of selected features K. The enhanced algorithms outperform the original algorithms, achieving gains equiv- alent to selecting 10 more features. Notably, OP and OP- (A (A)SSSS demonstrate approximately 0.1 improvement in R². And even though CoSaMP fails in this regression task (see Appendix Q for detailed reasons), the enhanced CoSaOP remains effective and delivers strong performance.
scenarios.
6. Discussion
Here, we want to emphasize that our proposed optimal pur- suit idea can also be applied to Gradient Pursuit, which we refer to as Optimal Gradient Pursuit. Optimal Gradient Pur- suit simultaneously considers both support set updates (fea-
In this section, we discuss the potential applications of the optimal pursuit idea in a broader range of machine learning tasks and scenarios.
8

---

Best Subset Selection: Optimal Pursuit for Feature Selection and Elimination
Boaton Housing
Califonnaa Housing
Supercondactivty
House
Prostate.
Spectra
0.85
0.5
0.0
0.75
OP OM
0.5
OP
04
OF Dki
0.2
13
8 CP
2M4
0.0
13
15
OP CH
044
F. OP
Housing
Culiforii Housing
Guperonsbucttty
Proviato viegones
Spectro
0.4
0.4
0.
0.0
FAI
CoBJOP Codlaee
D4
02
12 0.1
- CobaCC
027
PAIL
---1"" Cobaarr
10
13
10
Boaton Housing
0.75
0J
California Housing
Superconductivvy
0.6
House 101
0.0
Prestste.0d sgenss
Spectro
"t: out
20
0.4
R= CP GP-VAESS 1 (UBESS
0.0
R 148659
JURESS R" INDees
(VeeSs
0.7
R2 (ULESS
---R2 OP--00E666
Figure 4. Rows 1-3 present the meta-gains in feature representation capability (R², closer to is better) for the Boston Housing, California Housing, Superconductivity datasets, House 16H, Prostate. v8. egenes, and Spectra datasets, respectively, across three algorithms as the number of selected fcatures K varies. See Appendix R for cross validation performance in prediction.
ture individual significance) and coefficient updates (feature interaction), while maintaining the same order of computa- tional complexity as Gradient Pursuit.
selection, where the features are continuous in the fre- quency domain and exhibit a specific structure: v(f) (1, (1,e-12t 120e,,, , - , e ==)2x(=11)/)" The goal is to de- compose a given complex signal into its frequency compo- nents, a problem widely applied in modern wireless com- munications (Mamandipoor et al., 2016). For the numerical experiments of Optimal Pursuit in complex signal process- ing, please refer to the Appendix W.
For the derivation of the Optimal Gradient Pursuit crite- ria, the proof of its theoretical properties and the numerical experiments, please refer to the Appendices S-U. Optimal Gradient Pursuit serves an acceleration scheme for Opti- mal Pursuit, which is applicable to ultra-high dimensional settings, and the gradient-based updates is practical for best subset selection problems with general objective functions.
7. Conclusion
This paper proposed two novel objective-based criteria for feature selection and elimination in best subset selection. By revisiting classical criteria in traditional algorithms through the lens of block coordinate descent, we revealed that they only reflect one-step variation of the objective function. Building on this, we formulated exact optimization subprob- lems for feature selection and elimination, deriving explicit solutions using forward and backward matrix inversion. The proposed criteria account for both individual feature signif- icance and interactions, proving optimal for subset selec- tion. Replacing classical criteria with the proposed ones, we developed enhanced algorithms that retain the original theoretical guarantees while achieving notable performance gains across various tasks, such as compressed sensing and sparse regression, all without added computational cost.
6.2. Unsupervised Learning: Column Subset Selection
Column Subset Selection (CSS) and PCA are both important dimensionality reduction methods with widespread applica- tions in unsupervised learning (Belhadji et al., 2020). The goal of CSS is to select a subset of important columns (fea- tures) from dataset that can better represent the entire dataset, formulated as:
min X - X
B
S. t. |S| S K.
In fact, this problem can also be viewed as a special case of best subset selection problem. We have extended the optimal pursuit criterion to the CSS task, demonstrating the advantages of our proposed criteria over classical criteria in this setting. For the derivation of the criteria and numerical experiments, please refer to the Appendix V.
The results affirm the advantages of the new criteria both theoretically and practically, opening new avenues for im- proving best subset selection algorithms. Future work may consider: (1) integrating the proposed criteria into arbitrary greedy subset selection algorithms to develop en- hanced methods and application on structured sparse learn- ing (Huang et al., 2009), (2) developing optimal selection and elimination criteria for general objective functions, (3) investigating statistical inference theories of the new criteria.
6.3. Complex Signal Processing
Although our paper primarily discusses these theories and methods in the real domain, they can be directly ex- tended to the complex domain. A classic example in complex signal processing is line spectrum estimation. This problem can be viewed as special case of feature

---

Best Subset Selection: Optimal Pursuit for Feature Selection and Elimination
Acknowledgements
Efron, B., Hastie, T., Johnstone, I., and Tibshirani, R. Least angle regression. The Annals of Statisties, 32(2):407-451, 2004.
This research was supported by National Key R&D Program of China under grant 2021 YFA1003303.
Fan, and Li, R. Variable selection via nonconcave pe- nalized likelihood and its oracle properties. Journal of the American Statistical Association, 96(456):1348-1333 2001.
The authors would like to thank all the reviewers for their helpful comments. Their suggestions have helped us en- hance our theories and experiments to present a more com- prehensive demonstration of the effectiveness of our work.
Feige, U. threshold of for approximating set cover.
Impact Statement
Journal of the ACM (JACM), 45(4):6344-5 1998.
This paper presents work whose goal advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be
Foucart, S. Hard thresholding pursuit: An algorithm for
compressive sensing. SIAM Journal on Numerical Analy- sis, 496)):2533-2533, 2011.
specifically highlighted here.
Gemmeke, F., Ellis, D. P., Freedman, D., Jansen, A., Lawrence, W., Moore, R. C., Plakal, M., and Ritter, M. Audio set: An ontology and human-labeled dataset for audio events. In 2017 IEEE International Conference Acoustics, Speech and Signal Processing (ICASSP), pp. 776-780. IEEE, 2017.
References
Belhadji, A., Bardenet, R., and Chainais, P. A determinantal point process for column subset selection. Journal of Machine Learning Research, 21(197):1-62, 2020.
Hamidieh, K.
Superconductivty Data.
UCI
Blumensath, and Davies, M. E. Gradient pursuits. IEEE Transactions on Signal Processing, 56(6):2370-2382, 2008.
Machine Learning Repository. 2018.
DOI:
http://0i.or//1022433///333
Hastie, T., Tibshirani, R., and Friedman, J. The elements of statistical learning: data mining, inference, and predic- tion, 2017.
Blumensath, T. and Davies, M. E. Iterative hard thresholding for compressed sensing. Applied and Computational Harmonic Analysis, 27(3):265-22) 224, 2009.
Hazimeh, H. and Mazumder, R. Fast best subset selec- tion: Coordinate descent and local combinatorial opti- mization algorithms. Operations Research, 68(5):1517-
Chen, S. S., Donoho, D. L., and Saunders, M. A. Atomic decomposition by basis pursuit. SIAM Review, 43(1): 129-159, 2001.
1537, 2020.
Das, A. and Kempe, D. Submodular meets spectral: greedy algorithms for subset selection, sparse approximation and dictionary selection. In Proceedings of the 28th International Conference International Conference on Machine Learning, pp. 1057-1064, 2011.
Huang. J., Zhang, T., and Metaxas, D. Learning with struc- tured sparsity. In Proceedings of the 26th Annual Inter- national Conference Machine Learning pp. 417-424, 2009.
Kohavi, R. and John, G. H. Wrappers for feature subset selection. Artificial Intelligence, (7(12)) 324, 1997.
Das, A. and Kempe, D. Approximate submodularity and its applications: Subset selection, sparse approximation and dictionary selection. Journal of Machine Learning Research, 1933)11334, 2018
Lin, Z. and Pan, W. robust cis-mendelian randomization method with application to drug target discovery. Nature Communications, 15(1):6072. 2024.
Davis, G., Mallat, S., and Avellaneda, M. Adaptive greedy approximations. Constructive Approximation, 13:57-98, 1997.
Mallat, S. G. and Zhang, Z. Matching pursuits with time- frequency dictionaries. IEEE Transactions on Signal Processing, 41(12):339733115 1993.
Donoho, D. L. Compressed sensing. IEEE Transactions Information Theory, 129- 2006.
Mamandipoor, B., Ramasamy, D., and Madhow, U. New- tonized orthogonal matching pursuit: Frequency estima- tion over the continuum. JEEE Transactions on Signal Processing, 64(119:5066-5081, 2016.
Dy. J. and Brodley, C. Feature subset selection and order identification for unsupervised learning. Proceedings of the Seventeenth International Conference on Machine Learning, 2000.
Miller, A. Subset selection in regression. Chapman and Hal//CRC, 2002.
10

---

Best Subset Selection: Optimal Pursuit for Feature Selection and Elimination
Needell, D. and Tropp, J. Cosamp: Iterative signal recovery from incomplete and inaccurate samples. Applied and Computational Harmonic Analysis, 26(3):001-32,, 2009.
Zhu, J., Wang, X., Hu, L., Huang, Jiang, K., Zhang, Y., Lin, S., and Zhu, abess: A fast best-subset selection library in python and R. Journal of Machine Learning Research, 23(202):1-7, 2022.
Pati, Y. C.,, Rezaifar, R., and Krishnaprasad, P. S. Orthogo- nal matching pursuit: Recursive function approximation with applications to wavelet decomposition. In Proceed- ings of 27th Asilomar Conference on Signals, Systems and Computers, pp. 40-44, IEEE, 1993.
Zou, H. The adaptive lasso and its oracle properties. Journal of the American Statistical Association, 141 1418 1429, 2006.
Pedregosa, F,, Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V., Vanderplas, J., Passos, A., Cour- napeau, D., Brucher, M., Perrot, M., and Duchesnay, E. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2833 2011.
Qian, C., Yu, Y., and Zhou, 7.-H. Subset selection by pareto optimization. Advances in Neural Information Processing Systems, 28, 2015.
Qian, C., Shi, J.-.., Yu, Y., Tang, K., and Zhou, Z.-H. Subset selection under noise. Advances in Neural Information Processing Systems, 30, 2017.
The Math Works, Inc. Statistics and Machine Learning Toolbox, 2025.
Tibshirani, R. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society Series B: Statistical Methodology, 58(1):267-22) 1996.
Tohidi, E.,, Coutino, M., and Gesbert, D. Revisiting match-
ing pursuit: Beyond approximate submodularity. Signal Processing. 226:1 109638, 2025.
Tropp, A. and Gilbert, A. C. Signal recovery from random measurements via orthogonal matching pursuit. IEEE Transactions on Information Theory, 53(12))465
2007.
Vansehoren, J. OpenML Dataset 574: House 16H, 2014.
Wang, J., Zhang, B., Du, Q.. Zhang, J., and Chu, D. sur- vey on data selection for LLM instruction tuning. arXiv preprint arXiv:2402.05123. 2024.
Wei, K., Iyer, R., and Bilmes, J. Submodularity in data subset selection and active learning. In Proceedings of the 32nd International Conference Machine Learning, pp. 1954-1963. PMLR, 2015.
Zhang, C.-H. Nearly unbiased variable selection under minimax concave penalty. The Annals of Statistics, 38 (2):894-23) - 942, 2010.
Zhu, J., Wen, C., Zhu, J., Zhang, H., and Wang, X. A polynomial algorithm for best-subset selection problem. Proceedings of the National Academy of Sciences, 117 (52):33117-33123, 2020.

---

Best Subset Selection: Optimal Pursuit for Feature Selection and Elimination
A. Proof of Lemma 3.1
Proof. Let supp(3). Since the solution 3 of (PI) obtained via least squares on S, i.e.
B3 = (x X gg =
(13)
Then, substituting (13) into (P1) directly yields (P2).
B. Proof of Theorem 3.3
Proof. Denoting Sk-1 supp(B"-t) and S supp(33, can rewrite (P2) follows:
argmax Xs (XXXs) X
(14)
A
8. Sk S, |S| S + 1,
where the inverse term (X)Xs) can be expressed as
X Spmt ) (XS..1
X Xs.-1
X X, X/X,
(XfXs)
-1
X,)
X
X 8k-1
According to Lemma 3.2,
Xx
- -v- -1
A A A ut T
A-1
-A-'ut-1)
1-1
where = X S - s._,, and A-1 [X] =(X7, Xs...)
which computed in step k and is already
known. Additionally, t is given by
t t= -
Xs.
(B._,Xs..)
"x__,,,. X,.
X
Then, Xs Xx
X can be reformulated as
Xs (x(55s))
X (Xs. X,)
A AA + A ut V
-1
-A-
XT
s
-t -T'
t-
X
=Xsc-, (A-1+ -1
+ A - ul -u
XT
X
-XTT
S +XX
-1
X
X X
X X,X?
X
X
X X X
X X
=XS--1 (X] (8.,))
Xs.- +
X.X, X/XSA-1
TT
S XS
XT
S/-1 X,
-1
-1
X
X 8k
X
X
St.
X + XX X
XT. Sk-1
-X,X7
XfX; XfXxs
Xsx ) (XH_,xXs,
X X X;
-X
X X
Xsy-1
-1
- X
X
X
X7 X?._, X,X!
I-X
XX Se-1
XT_,,Xii Xs.-.)
X
96-1
S4-1
-1
x7
1 1-
1-Xs
XI Xs.-1)
X
XT
X
12

---

Best Subset Selection: Optimal Pursuit for Feature Selection and Elimination
Therefore, problem (P2) is equivalent
yd I - Xs..
(3 Xse..)
X
X
(-XSx-1
I-
( XSe..)
X X3mm1 y
argmax /E%
x
I S-X
X
Sk-1 Xsn-1
X
Xj
Sk-1
(n""x) X,)
argmax JES
(15)
X5
I I-S
X X Xse-1) X7 Sk-1
X
where pdb = y Xss B represents the residual obtained from the (k 1)-th update, and g
[3 (X%__, XS.-1)
X y y the coefficient estimate from step k 1.
C. Proof of Theorem 3.11
Proof. Denoting Sk-1 supp( and supp(33, we can rewrite (Q2) as follows:
argmax
Xs (xxXs) x
(16)
B
s. S Sk-1, |||
SS - 1,
where the inverse term Xx)
is already known, as it was computed in step k 1. Let e; (61s, 82., ... 8ús, ... 1(i) E IR Sc-s1, for all = 1,2, ... defined as
, where the Kronecker delta function dij
1.
if if
8.g
0,
otherwise.
Let P, = (c1, (. ,1-1, ,ise .1) E R S 1|x[s| Then, by Lemma 3.10, when = Sk-1 Mf7)
we have
PJ S4 X
Xsa_.
e,ey X (
P
(x = PP7 [X[
(x(x Xs [
'P, P,
of X (iS_,,Xss Cj
and X5 = Ss Pj. Therefore, problem (Q2) is equivalent
y''Xs.,,PP P,Pp' (X), Xs...) P,P, y
argmax jESt-1
yTXs St P,Py (XT Xs
) ejog
eeje [X] 1 Xsm
-1
"pppfx! x!
eς (T (. 0j
XT K3Je,Kas e,e, X3 [3,_,Xaen1
X S P.P."
(xX (X3_,,ssm))
X x
argmax jESE-1
of
(T__. Xsm.,) Cj
0
arggax jESt-1
yd ' [I - e,,o)
Ch-1
0f Ck-10j
(I (I-
X X. (since P.P. =I- =I-
13

---

Best Subset Selection: Optimal Pursuit for Feature Sclection and Elimination
D. Proof of Remark 3.13
) Proof. When X, and S VG3 are orthogonal, we have P, (xL. x -1 8j =0 Therefore, the abjective-baser elimination criterion (10) can be reformulated as
p,pp (10) - - P,Pp (XS (8sx)) 'PPP))p N
(18)
Noticing that P.P.. = e,eg, we can rewrite (18) as
(I (I- X (18)
--,e,,)) (X'__, ) (I-
(I- (I- X S
-1
y Sh (I e5eÿ) (x XSa-1) x )
( Xs..))
X
Sk-1
Xs., ) (I e),,) x X3m.N)
(1
(19)
It's also observed that XSe..) (I (I- X )
,
(I (I-e,e)) (x Xs...)
x X =
(I (I-e e,ee)) gh-1, where (+) holds because Xj orthogonal 11))) Therefore, (19) can be further expressed as follows:
(19) (st-1)" T (I (I- (x (I -,ee,) e
gh- = -c- (D 2
(20)
argmax C' C- (X)x,) (8)-1)²
(xfxx) (8)-
Therefore, we have (10)
argmin JES,-1
when X, 1
JESx-1
\1) Vj 1,... |
Thus, when Xs.., column- matrix, the new criterion (10) reduces to
minimizing the Wald-T statisties (4).
E. Enhanced Algorithms
E.1. Optimal Pursuit
This subsection presents the algorithmic workflow Optimal Pursuit (OP).
Algorithm OP: Optimal Pursuit
I: Input: Design matrix X, response vector y. sparsity level K, and residual tolerance
2: Output: Support set Š and sparse solution 3.
3: Initialize residual r' = y, support So 0, 5 Ho Onxn, and iteration counter k 1. repeat
5:
Compute the objective-based criterion (8) using & H and identify the optimal index j. objective reduction.
If Find the basis maximizing the
6:
Update support set: S. = S U (i}.
7:
Update C2 (x], x and H. Xs. C Solve least squares problem using S C.X,,y y
I/ To be used in step k 1 as explained in Remark 3.7.
8:
// Estimate coefficients active set.
9:
Update g = = S..uss. where 83 0. Update residual: A+1
10:
x
11:
Update counter: lo = k: + 1.
12:
until ||r5 < or k K +1 S4-1. and 3 3²_
13:
E.2. Compressive Sampling Optimal Pursuit
This subsection presents the algorithmic workflow Compressive Sampling Optimal Pursuit (CoSaOP).
14

---

Best Subset Selection: Optimal Pursuit for Feature Selection and Elimination
Algorithm 2 CoSaOP: Compressive Sampling Optimal Pursuit
1: Input: Design matrix X. response vector y. sparsity level K, residual tolerance variation tolerance c2, and maximum iteration
count Maxiter.
2: Output: Support set S and sparse solution B.
3: Initialize residual = y. support set Su = 0. 3 0, Ho Opxn, and iteration counter A = 0.
4: repeat
5: Update counter: & = k 1.
6: Compute the objective-based criterion (8) using r Hg-1 and identify the optimal 2K indexes f2
7: Update support set: U2 = S U..
Update C (Xt, Xu,)
9:
Compute the objective-based criterion (10) using C and identify the minimum K indexes Sx.
10:
Update C2 (x3, )x and H. Xs. C.
I/ To be used in step le + 1 as explained in Remark 3.7.
11:
Solve least-s problem using SS C GxX3syy
12:
Update 3
Sis where g5
O.
13:
Update residual: rh+1 y X
14:
until ||r***|12 S or || 8 Sx. and B = 3"
S E2 or k = Maxitr
15:
5
E.3. Optimal
Selection
This subsection presents the algorithmic workflow of Optimal sub-function, OP-Splicing.
Selection (OP-BESS) along with its
Algorithm 3 OP-BESS (Main Function): Optimal Pursuit-Best-Suuee Selection
1: Input: Design matrix X, response vector a positive integer kimax and a threshold т.
Output: Support set S. sparse solution B, and dual vector cl
3: Initialize S = = E I(I
x y
S K) I
(S S.90 04 0, and d² 0.
4: Let Co 50 )
#I To be used in the next step as explained in Remark 3.7.
5: Compute initial 3o = Co X so and do X (y x/8
6: repeat
7: Update (3 d gm++1 Im+t Cm+1) Splicing( mh d , Sm I Cm, Rimaxy 7)-
8: until (5th 1m (Smh Im)
9: Return: (8,3,)) d) (5m+1 3m+ dm++)).
Algorithm OP-Splicing Sub-Function of OP-BESS): Update Model Parameters and Support Sets
1: Input: Current parameters obtained in step m: 33 d. support sets S, I, Co., maximum iterations keax, and threshold т.
2: Output: Updated parameters in iteration m + 1: B, å, S, 2 and Cm+1.
3: Initialize loss La L = X,3
4: Compute the objective- based criteria Ey = (10) and C = (8) using C., for = 1,...,P.
5: for k = 1, i,,, kmx do
6: Update support sets:
Ss = E E S: Σ T(S (6) S k)),
Is (jEI: Σ
I(4 $ $G) k).
EET
7: Let S. = (S) - Sd and Ō=
T X ) (x
I/ To be used in the next step as explained
Remark 3.7.
8: Solve least-squares problem for Ag. and compute d:
33. CX BI, =0
à = x" (y -x3/11
9: Update loss: (3) = 1ly xx8l1/(2m).
15

---

Best Subset Selection: Optimal Pursuit for Feature Selection and Elimination
10:
if (3) then
11: Update (n(3). 8=
= Sx. Ix. B B. and Cm411 C.
end
13:
end for
14: Lo fo-AA -- then
15:
Return current parameters without updates.
16: end if
F. Proof of Lemma 4.4
Assumption. (Align with similar those (Tropp & Gilbert, 2007; Needell & Tropp, 2009; Zhu et al., 2020).)
1. 3 is --sparse.
2. X satisfies Restricted Isometry Property (RIP) as in (Needell & Tropp, 2009). For definition of restricted isometry constant 8y, please refer to (Needell & Tropp, 2009).
3. X is column-normalizz i.e., X]X;= =.
Proof. The elements selected in Ω can be viewed as the 2K largest entries (in magnitude) of the vector DX r where D is diagonal matrix satisfying:
j E S
x 1-Xo (1X6L- (Xb,
xx
X% .)x,
D35 =
1,
j E Sk-1-
Notation: X
I Xs 18S,iXsh..
X X
X, -x I (-- (XSm. Xsn.1)
-1
2 X3.m1 )²
Xj. When
jE 15 X3
I- 1sx K
X
S6-1
X, 0. Therefore, D is well-defined.
Let R supp (gh-1
According to CoSaOP algorithm, the set R contains at most 2K nonzero elements. By the definition of Ω it holds that |q/lll2 I ||q/ol2- Then, we have
3¹). -3"
|| S ||
By (Needell & Tropp. 2009) (Proposition 3.1 and 3.2), for j S it holds that
XfXs, s--1
(X X
x Sh X, <
x S
x |11
[ ( Xs
)
x Se- X,
< 6Ktl -1- -k
Therefore,
8K+1
< <X,
I- 1-X
X ( Xsu
-1 x2 X
X, S1,
V1- 8k
i..,
15 15D, Djj <
ók+
v1-8x
which implies
DDI|2 5
(21)
5x
/1 6x
16

---

Best Subset Selection: Optimal Pursuit for Feature Selection and Elimination
Let DlayR denote the submatrix of D restricted to the index set R, with dimensions |S2] R [22/ Therefore, by (Needell & Tropp, 2009) (Proposition 3.1 and Corollary 3.3) and (21), it holds that
||lavell22 = Dlay - Xhx 1/
- [Dlavell dell X
mt 112
| (x (8---1111 +5)l12
8
V1-6x
(|x (3r -80--3p 1/-1)111 + || R (b)
6x+1
VI-0k
1
Jokk ||0 - -4 + VI+ 62k
62+ (ell2)
8K+1
V1-6k
By the definition of the matrix D and D jj 2 1, for E Sk-1. it follows that for any E R"
Dulp = DD
u 2 L DJ
-
(22)
j=l
Similarly, according to (Needell & Tropp, 2009) (Proposition 3.1 and Corollary 3.3) and (22),
| Ro
X D DIRAO
Mork
2 X a
2
a (x (B* -1hh1) - =,)112
x m X
(3- - 3x-11) |R/0
x XTan X (Br 18--30 -1h-11
l0 12 X mel
2
(88 - 3r 11 RIA
82K 8 -3"--1 ||, -VI+ d2k |c|12-
(1 )2
Based on the definition of R, holds that (5r - 3 31-1)
(3r 13h )) Inc Therefore, we have
RR
(1 82x) || (0r - 31-1)) 1) 1as ||- - 82x 133 - gh -V + dox (||1
-3h
(dax 3r 3
|| + /1 02x [||ll)
6k+1
VI-ōx
Then, it follows:
+
82K
-
3h-1| 112 +
V1+62x
+
V1
+ d2k
||l/2
8g-1
5x+1
(33 -1h 1an 2
Vi-šk
Vi-
5
82K
By assumption ōx 58x+1 S 62x S dsx S 0.1, Lemma 4.4 is proved.
G. Proof of Lemma 4.5
Proof. The proof follows from Lemma 4.3 in (Needell & Tropp. 2009). Since supp(33-1) U, we find that
3 ue ll = (1(88 - -²--1)
10 11 $ <B(BB
-g-1))
1ac 11.
17

---

Best Subset Selection: Optimal Pursuit for Feature Selection and Elimination
H. Proof of Lemma 4.6
Proof. The proof follows from Lemma 4.4 (Needell & Tropp, 2009).
I. Proof of Lemma 4.7
Assumption. (Following the three assumptions in Appendix F.) Let äs, be defined as follows:
aj.
if E Sk.
0, ifj E St.
and let äg denote the best K- K-sparse approximation afa. a. supp((") S (Sx A supp(āx)) where A A B = (B(A)
Proof.
|| äs l2 I 1 åxl2 + lâx āsæl12.
3 xxl1 S 3 all2 + llallaa åxl12 S 21113 - -all2
lxx- às 112 = |áupp(ā M 112 - 011 -allz (by Assumption 4).
Since || all2 [ 112 |10 a) (()pp(()))S)))))) [| when Xy is orthogonal,
(upp(äx)/AS)) 0,5 0. When the orthogonality of Xu is weak, supp(āx) n Sk 0,8 1. Therefore, ||3" -as,112 I (2 + 6) 11," aal2-
J. Proof of Lemma 4.8
Proof. The properties of least squares imply that Ily X,31112 S Ily Xās, ll..
Therefore, it holds that
x (0r - 3t) + +c// s s|x (0" äs.) ) + +cll2
which leads
x (8r 18--130 3/ -
-||ll2 S |x (B' as.)l12 + -|E1l22
i.e.,
| x (3 -
3t) |111= XX (B - -asall2 + 21|E/12
Suppose E = -supp (3") U Sc. EE < 2K, then
x (8r - 3t) /3) = X (B- - -B+) LE ||3
= -(3 - -3²) T LE X (8'
-* (B-
lE
Amin (XEXE: 118-
3/|12
Similarly, have
XX (3* ās.)112 < Amax (XfXE) 11 - ās,
18

---

Best Subset Selection: Optimal Pursuit for Feature Selection and Elimination
Therefore,
|| 18
-30 -3//1/ -
Amax (X
1|3" - 1 +
|
Amnin (X E Xx)
Amin Xx)
+ 62K
113" - -as2l2++ + V1 62K
|||12
(by Proposition 3.1 in (Needell & Tropp, 2009))
82K
< 1.106 113 -ss 112 + 2.1109/ee|2-
K. Proof of Theorem 4.9
Proof. Based on Lemma 4.4-4.8, we can derive the linear convergence rate of CoSaOP as follows:
1 - .b| s 1.106 | ās 22 + 2.109/|c||2
(Lemma 4.8)
< 1.106(2 6) |0 a|l2 + 2/1 (Lemma 4.7)
< 1.106(2 + 6) (1.112 | 10-122 + [.06 + 2.109|/<l12 (Lemmaa 4.6)
< 1.106(2 8)
1.112 (8' -1"h
p- || +106||e||2] 2.109]/e||2 (Lemma 4.5)
1.23(2 6)
(8- -
+ (2.109 + 1.173(2 + 6)[[<[12)
10 2
< 1.23322 + 8) (1.2353 8 3
3h-11
+ +2,4/<<122
+ (2.109- 1.173(2 + 6)](c(2)
(Lemma 4.4)
< 0.869 0r 3" 1-1
+ 14.442/|c//2
L. Proof of Theorem 4.10
[XTx, XX, we have
Proof. When i E S.p-
(X5X5)
X X,
/I 1|X,
(23)
Hence, for classical correlation-base selection criterion (3),
1 T
x,1
x T
I (--xs Xs (X X3) X,
|2,122
11,
|2 X,, 1/21112 / pz
|,,1|2
/ ا²م |/-
While for proposed criterion,
p x,) 2
)²
(,²"X,)
x,, )²
f x
2
1
(24)
xJ I
Xs
(xXXs -x,) X, Xy¹ I Xs
x?
(x5Xs) -1 X3²
X,
p2
||x
19

---

Best Subset Selection: Optimal Pursuit for Feature Selection and Elimination
M. Proof of Theorem 4.11
Proof. The proof of Theorem 4.11 (I) and (2) will be given below.
(1) Since
objeclive-bused crilerion crilerio (10) y Xs (X2Xs) X5yy
=-yyy x s 1/ + 11y1
(25)
- |
the upper bound of the Abjective-based criterion (10) is 11y12.
Now consider that
y =X +c= xc= tc.
(26)
If S S, then for all jm 8 S* {.imm. By (25),
-1 objective-based crilerion (10) or jm y² xxx XsSmml (X5((m)) Xs(mmm)) X (
= Xs(lmm (im.)
112 (()()))))))))))
|1yl12
2 -lyy X 1lyl
= 11yl -|e11
Hence, for all jm E SS,5", the lower bound of the objective-based based criterion (10) for jm is |lyl -|6||2- In noiseless scenario, for all jm E S'S the objective-based criterion (10) for jm achieves the upper bound. Hence,
Jm argmaxjes objective-based criterion (10).
(2) Consider a simple counterexample where the T-statistic fails in the presence of highly correlated features.
Let
0.2
0
X
0.8
0.9
0.1
0.1)
and y (0.2, 0.85, 0.1)". Consider the best subset selection with K The ground truth follows:
Table A simple counterexample.
Subset
Feature 1 & 2
Feature 2 & 3
Feature &
Residual Norm
0.0062
0.2 No
0.0055
Best Subset
No
Yes
Hence, when = 2, feature X₁ and X3 are the true features, and feature X₂ is the spurious feature.
However, given S (,, 2, 3), the classic criterion (4) (VX/ (3,1) for the features are: Ti 0.2, 0.403, 0.453. By minimizing classic criterion (4), feature X; is eliminated.
The core issue lies in the fact that the spurious feature X, is highly correlated with the important feature X3 in the true subset. Since classic criterion (4) considers only the individual significance of features while ignoring their interactions, the true feature X, is erroneously discarded by the classic criterion (4).
However, for objective-bass -ased criterion (10), it will always identify X, by Theorem 4.2 in the paper. The proof is complete.
20

---

Best Subset Selection: Optimal Pursuit for Feature Selection and Elimination
N. Explanations on Theorem 4.10 and Theorem 4.11
Explanations on Theorem 4.10:
Theorem 4.10 demonstrates that if features and j in the true subset are correlated (violating the RIP condition), inequality (11) implies that as their correlation P approaches 1, feature j becomes increasingly unidentifiable under traditional correlation-basse criterion (3) once feature i has been selected. In contrast, (12) shows that when is large, since the first term's s coefficient in RHS 1 1/(1 p²) is large, the proposed criterion (8) exists stable lower bound. The larger the correlation P the stronger discrepancy between traditional vorrelation-basee criterion (3) and proposed criterion (8). This significantly mitigates the impact of feature correlations on identifying j, making true features more reliably detectable.
Explanations on Theorem 4.11:
(I) The upper bound of the objective-based criterion (10) is | Theorem 4.11 (1) shows that when the current subset S contains the true subset S all features outside the true subset have stable lower bound for their criterion (10), which is related to noise level. When the noise is relatively weak compared to the signal, this lower bound becomes larger, indicating that features outside the true subset are more easily identified by maximizing criterion (10) (ideally, larger values of criterion (10) for irrelevant features are preferred). In the noiseless case, all features outside the true subset can be identified by maximizing criterion (10). This result does not rely on any assumptions about feature correlations, and therefore remains valid even scenarios with highly correlated features.
In Figure 3, all enhanced algorithms that incorporate the feature elimination criterion (10) show a clear improvement in performance as the SNR increases. This is also consistent with the theoretical results.
(2) In the best subset selection problem, a speudo-correlation phenomenon may arise. Pseudo-correlated features refer to those features Xp that are highly correlated with critical features X; in the true subset 5 yet X, itself does not belong to S*. Once such features are selected, they are difficult to detect and remove by classical T-statistics based feature elimination criterion (4) but may be reliably identified by the proposed criterion (10). See Appendix M for example.
Theorem 4. 4.10 and 4.11 demonstrate that our proposed criterion (8) effectively identifies truly important features even when they are strongly correlated, and criterion ( (10) reliably removes pseudo-correlated features that mimic true features. These theoretical insights are further validated by the experimental results in Appendix P. which confirm the superior performance of our criteria in high-correlation scenarios.
O. Experiment on Computational Time
In this section, we report the computational time of each algorithm over 500 independent runs. While the new criteria introduce additional multiplication operations, resulting in slightly higher computational time compare the original criteria it remains within the same order of magnitude, as shown in Figure 5.
0.1
Running Time
0.08
30.06
0.00
0.04
OMP
OP
CoSaMP
CoBwOP
(ABESS
OP-JAJBESS
Figure 5. Running time for each algorithm over 500 independent runs.
"In Figure 5. CoSaMP requires more time than CoSaOP, since in this sparse recovery scenario, although CoSaOP performs additional matrix multiplications in single iteration, it generally converges to the stopping criterion within just few iterations. In contrast, CoSaMP requires significantly more iterations to converge, often reaching the maximum number of iterations before stopping, which results in longer runtime.
21

---

Best Subset Selection: Optimal Pursuit for Feature Selection and Elimination
P. Experiment with High-dimensional Correlated Features and Small Noisy Samples
In this experiment, we conduct additional comparisons of the algorithm under extreme scenarios:
(a) Smaple rate and high-dimensional vectors: p = 2000, with n/p varying from 0.05 0.1.
(b) High noise: SNR² varies from 5 to 15.
(c) Highly correlated features (RIP violated); The covariance matrix of the row vectors of X follows Toeplitz structure, where the correlation between position j is corri = pli->l, with p = 0.7.
We generated sparse vectors with a sparsity level K = 10 for testing. Specifically, the sparse signal is block-sparse, comprising two blocks of five adjacent non-zero entries each. Combined with the Toeplitz covariance structure (where features closer in position exhibit higher correlations), this configuration ensures:
(1) High correlation features within the true subset (as stated in Theorem 4.10).
(2) Many pseudo-features outside the true subset highly correlated with those in the true subset (as in Theorem 4.11).
Phase transition diagrams illustrate the combined impact of varying sampling rates and SNR on algorithm performance (using NMSE as evaluation metric), where larger blue areas indicate stronger algorithm performance. The experimental results show that all algorithms enhanced with the new criteria exhibit significant improvements in phase transition capabilities compared to their original versions. This only demonstrates the robust advantages of the new criteria in high-dimensional, low-SNR extreme scenarios but also validates the theories established in Theorem 4.10 and 4.11 through their marked improvements under high feature correlations.
OP
CoSaOP
OP-(AJBESS
16
15
15
13
13
13
0.9
SNR
11
SNR
11
11
9
9
9
7
7
5
0.05
0.06
0.07
0.08
0.09
0.1
0.0s
0.06
0.07
0.08
0.09
0.1
0.05
0.96
0.07
0.08
0.09
0.1
0.6
n/b
n/p
n/p
0.5
OMP
CoSaMP
(AJBESS
15
15
15
0.4
0.3
SNR
11
SNR
11
11
9
9
9
0.2
7
0.1
5
5
6
0.06
0.06
0.07
0.08
0.09
0.1
0.05
0.06
0.07
0.08
0.09
0.1
0.05
0.06
0.07
0.08
0.00
0.1
n/b
n/b
n/b
Figure 6. Phase transition with correlated features.
Q. Reasons Why CoSaMP Fails in Sparse Regression
The main algorithmic flow of CoSaMP as follows: it iteratively (1) selects 2K features, (2) solves a least squares problem on a large subset, and (3) prunes K coefficients. However, high feature correlation can cause significant errors in the final estimate from steps (2) and (3). We visualize the impact of feature correlation on CoSaMP's iterative process here.
*SNR log
|X]]|/|||||-
22

---

Best Subset Selection: Optimal Pursuit for Feature Selection and Elimination
CodaMe
Sumn Suppert
.0055
bauston
Recstion
baatton
KA
Rectiond
Dant
(a) CoSaMP fails when features are highly correlated
(b) CoSaMP succeeds when features are weakly correlated
Figure 7. Reasons why CoSaMP fails in sparse regression.
As shown in Figure 7a, on a regression dataset (Boston Housing) with highly correlated features, the pruned support set's direct coefficients (column 2) differ significantly from those after least squares estimation (column 3), with substantial residuals. CoSaMP, lacking least squares refinement, fails as the residuals grow with each iteration due to high feature correlation. This is evident in the residual curve evolution in Figure 8a.
Residual Norm Evolution of CoSaMP
Residual Norm Evolution of CoSaMP (Features satisfying RIP condition in Audioset)
(Highly correlated festures in Boston Honsing datasct)
2000
1.5
Residual
Residual
MMM M
0.5
500
20
40
60
80
100
20
40
60
80
100
Iteaaiio
Iveration
(a) Residual evolution of CoSaMP for highly-correlated features (b) Residual evolution of CoSaMP for weakly-correlatd features
Figure Residual evolution of CoSaMP with different feature correlation cases.
In contrast, when features are weakly correlated (as shown in Figure 7b), the coefficients and residuals after pruning the large support set (column 2) and performing least squares (column 3) are nearly identical, leading to algorithm convergence, as shown in Figure 8b.
Therefore, CoSaMP less suitable for scenarios where features are highly correlated or when p is close to 3K. The theoretical properties of this algorithm, as established in (Needell & Tropp, 2009), are also based on the assumption of weak feature correlation.
However, CoSaMP performs well in compressed sensing scenarios, particularly when using NMSE as the evaluation metric for audio data, where it can almost achieve the best results among classical algorithms.
R. Cross- Validation Performance in Prediction
We evaluated the best subset selection (BSS) algorithm's 's predictive performance on the six datasets using 5-fold cross- validation, where 4 folds were for training and for validation. The prediction error is defined as:
1 n
Σ (w: 22) 7
errofpred
(27)
The cross-validation score, averaged across the folds, is shown in Figure 9. The enhanced algorithms demonstrate superior generalization and highlighting the advantage of the new criteria selecting key features for predictive tasks.
23

---

Best Subset Selection: Optimal Pursuit for Feature Selection and Elimination
Boston Nousin
Califorii Housin
Expareenductttyy
House 18H
Prostate vdl
OMP
Preduttion Ere
-K-OVP)
Prddiion
Predition
Oh/
Hossing
Califenii
Seperstndactitt
House
Prostate
Protecoo Errer (Dn
Prodection Pagicta Droe
Error
500
Codlao
Emer
Protide
8
FAR.
FAI
FAL
FAIL
FAIL
6.0
OP JUEE55
on LURESS
LALBESS
PRODUCAT 320
Prodroon
100
Figure 9. Rows 1-3 present the meta-gains in cross-validation performance in prediction (errorpeed smaller is better) for the Boston
Housing, California Housing. Superconductivity datasets, House 16H, Prostate. v8.egenes, and Spectra datasets, respectively, across three algorithms as the number of selected features K varies.
S. The Optimal Gradient Pursuit Criteria The Optimal Gradient Pursuit Criteria:
X r* 11 + x,²xx,)
j" argmaxjest
(28)
X X7 X7 rk XxXXr=*12
where the underlined part only needs to be computed once and its overall computational complexity is at the same magnitude as the correlation-based selection criterion in Gradient Pursuit. The idea of optimal gradient pursuit can be illustrated Figure 10.
Comparison Between Gradient Pursuit and Optimal Gradient Pursuit
f1
Old Criterion Correlation-based Gradient Pursuit
supp update
New
Maximum function / decrease.
Criterion
Objective Optimal Gradient Pursult
Selection
coef update (Gradlent)
1 X,1
Selection
argmax,
Objective function f
I x 1²
Selection
angmak
x P + xxx
JEST
Figure 10. idea Optimal Gradient Pursuit. Remark S.1. The criterion (28) is the OGP version of the OP feature selection criterion (8). Similarly, by applying techniques analogous to those in the Appendix T, we can derive the OGP version of the feature climination criterion (10), which we omit here for brevity.
24

---

Best Subset Selection: Optimal Pursuit for Feature Sclection and Elimination
Remark S.2. The criterion (28) does repeatedly select features that have already been chosen. In practice, if adding new feature every iteration is not desired, one may consider using
t x,)
S x
XX
r rt
x
j" = argmax,
(29)
|x
+ lllla TT.jES.
Here, T is chosen threshold. In other words, when the effect of selecting new feature is not sufficiently significant, the algorithm can instead continue performing gradient updates the current support set S. Remark S.3. Naturally, the algorithms discussed the paper have corresponding OGP-accelerated versions.
Remark S.4. The conjugate gradient pursuit and other direction pursuit methods mentioned in (Blumensath & Davies, 2008) can also be updated using the idea of Optimal Pursuit.
T. Derivation of Optimal Gradient Pursuit Criteria
Proof. Considering the algorithmic procedure of gradient pursuit in (Blumensath & Davies, 2008), it necessary to take the effect of gradient updates into account, which leads to the derivation of the Optimal Gradient Pursuit criterion. The gradient the subset S S 1 U {i} is:
gss
(30)
The exact line search step size along the gradient direction on the support S is given by:
gggs
(31)
85 X sgs
Hence, considering the gradient update into account, we have:
++l = y-Xs (34 a gs
=r" - + t
And k+1 k+11 1 Xsgs since
1+1 Xggs 62 Xsgs + +a ag x sgs
gggs + g x X X
Hence, ||~1 || = ||aaX Xsgs|]
The goal is maximize the gradient update gains:
g gs
xxssslll2=
Xsgs
g
sgs
X X
X X
X
X X
X 1g
pk (1 x,x )²
|X
X X r X,X r211
The underlined part only needs be computed once. The proof complete.
25

---

Best Subset Selection: Optimal Pursuit for Feature Selection and Elimination
U. Theoretical Results and Experiments of Optimal Gradient Pursuit
The algorithmic procedure feature selection algorithm guided by criterion (28): Optimal Gradient Pursuit, follows similar structure as gradient pursuit in (Blumensath & Davies, 2008), with the selection criterion in gradient pursuit being meta-substituted by criterion (28). We first show that Optimal Gradient Pursuit possesses similarly strong theoretical properties Gradient Pursuit. The following theorem corresponds Theorem 3 in (Blumensath & Davies, 2008).
Theorem U.1. There exists constant < 1, which only depends X. such that the residual calculated with Optimal
Gradient Pursuit decays as
2 || 1 S c ||| 11
(32)
Proof. For the same R-1 the residual at step lo of OGP and GP satisfies:
| 2| | l
by the derivation of OGP criterion (28) in Appendix T. By Theorem in (Blumensath & Davies, 2008),
Gr 2 v c -||r~~11 1|
The derivation of this theorem is independent of the historical iteration steps. Hence for Optimal Gradient Pursuit,
||. 1| S c -||2-~1112-
The proof is complete.
Experiment on Residual Convergence:
Experimental result residual convergence of Optimal Gradient Pursuit and Gradient Pursuit is shown in Figure 11. Optimal Gradient Pursuit exhibits better residual convergence compared to Gradient Pursuit on different test cases. This is also consistent with the results presented in the Appendix T and Theorem U.I.
Residual Convergence of Gradient Pursuit and Optimal Gradient Pursuit on Different Test Cases
Residual Convergence
Residual Convergence
gradient pursuit
10a
gradient pursuit
optimal gradient pursuit
optimal gradient pursuit
10a
Residual Norm
Residual Norm
10a
10a
1
10-1
2.5
7.5
10.0
15.0
17.5
20.0
50
75
100
125
150
200
Iteration
Iteration
Figure 11. Residual convergence of Optimal Gradient Pursuit and Gradient Pursuit.
Experiment on Computation Time:
We further compared the runtime of GP and OGP, as shown in Figure 12.
Both methods achieve an ordgr-of-mannitude speedup compared to the least squares-basee subset selection approach. For features, OGP provides an efficient acceleration scheme for the optimal pursuit strategy. Specifically, since gradients can casily computed for general functions, the OGP method can be extended to general objective functions, offering promising direction for further expanding the applicability of optimal pursuit in future research.
26

---

Best Subset Selection: Optimal Pursuit for Feature Sclection and Elimination
0.12
0.1
0.08
Running Time
0.06
0.04
0.02
GP
0GP
OMP
OP
CoSaMP
CoSaOp
(AIBESS
OP OP-VAJBESS
Figure 12. Running time for cach algorithm over 500 independent runs.
V. Optimal Pursuit for Column Subset Selection
Optimal Pursuit Criteria for Column Subset Selection:
We follow the procedure in Section to construct the feature selection and elimination subproblems for column subset selection. By solving them using approaches as those in Appendices A-C, we obtain the Optimal Pursuit feature selection and elimination criteria for the column subset selection problem as follows:
111
Selection:
argmax JESS
X
I 1-XS.-1
XT Se-,
XSm-i
X7
Se-)
X,
- (I- e,,e x X
Ce-10,o, of Ck-1c
Elimination: argmax trace X (I (I- JESt-1
(C--1-
where R = X B serves as the current residual. The definitions of e, and Ck-1 are the same those in Theorem 3.11.
Classic Criteria for Column Subset Selection:
The classic criteria can also be similarly generalized to column subset selection problem by constructing subproblems as (PO) and (Q0) in Section 2. Specifically:
R
112
Selection:
argmax
X
X;
JES
Elimination: argmin JES
X 12
|
kB p..11
where B*-1 [1,
the i-th row of B and (in elimination) represents the i-th element of St-1 for 1,2,,..... 1,,,..,, Remark V.1. is important note that the results discussed in the main remain valid for the criteria column subset selection problem. The computational complexity of the Optimal Pursuit feature selection and elimination criteria is of the same order as that of the classical criteria.
Experiment on Column Subset Selection:
The experiment setting is:
27

---

Best Subset Selection: Optimal Pursuit for Feature Selection and Elimination
Datasets: We conduct experiments on eight standard grayscale 256x256 image datasets compiled from two sources
Baselines: We select baseline algorithm for CSS the leverage score method. This approach relies on the right singular vectors from SVD decomposition; the more singular vectors used, the better the selection performance, but at the cost of more redundant SVD computations.
Evaluation Metrics: We use |X X the evaluation metrics.
The experimental results is shown in Table 3. In the table, SVD-128/256 refers to CSS based on leverage scores computed using 128/256 singular vectors. In the last column of the table, we provide the bound given by the optimal rank- K approximation from SVD.
x are shown below, with the best bold and the second-best underlined. refers CSS based on leverage scores computed using 128/256 singular vectors (the more singular vectors used, the hetter the selection performance, but at the cost of more redundant SVD computations.). the last column of the table, we provide the bound given by the optimal rank-K approximation from SVD.
Table Column Subset Selection. ||
Dataset
K
OMP
OP
CoSaMP
CoSaOP
(A)BESS
Leverage Score (SVD-128)
Leverage Score (SVD-256)
Bound by
(A)BESS
SVD
0.3881
0.3794
0.3945
0.3979
0.3884
0.4262
11,4000
0.3330
0.3521
0.3422
0.4193
0.3820
0.3662
0.3399
0,3966
0,3814
0.2971
Mornach
10
0.2953
0.2758
0.4246
0.3275
0.3436
0.2771
0,3459
0.3079
0.2268
15
0,2466
0.2330
0.3951
0.2468
0.3285
0,2318
0.2845
0.2770
0,1804
20
0,2074
0.1999
0,3781
0,2150
0.2769
0.1981
0,2648
0,2419
0,1495
3
0,2823
0.2520
0.3256
0.2571
0,2831
0,2505
0.3284
0.2981
0.2296
5
0,2403
0.2173
0.3331
0.2303
0.2560
0,2179
0,3146
0,2610
0.1882
Barbara
10
0,1831
0.1743
0.3152
0,1896
0.2437
0.1730
0,2622
0.2197
0.1431
15
0,1577
0.1458
0,3023
0,1576
0.2306
0, 0,1468
0,2321
0,1847
0.1147
20
0.1337
0.1273
0.2871
0,1405
0.2242
0.1263
0,2156
0,1585
0.0983
3
0,2589
0,2453
0,3333
0.2589
0.2741
0.2435
0,3139
0.2995
0.2077
5
0,2219
0.2062
0.3149
0,2176
0,2676
0.2045
0,2725
0,2640
0.1688
Boats
10
0,1602
0.1575
0.2961
0,1747
0.2327
0.1578
0,2159
0,2004
0.1293
15
0.1336
0.1330
0.2779
0.1527
0.2187
0.1311
0.2015
0.1625
0.1050
20
0.1148
0.1148
0,2460
0.1262
0.1549
0.1131
0,1810
0.1436
0.0878
3
0,1983
0.1940
0.2658
0,2072
0,2097
0.1940
0,2418
0,2014
0,1677
5
0.1671
0.1618
0.2581
0.1988
0.2020
0.1617
0.2311
0.1335
0.1378
House
10
0.1286
0.1219
0.2564
0.1386
0.1878
0.1195
0,1927
0.1552
0.0977
15
0.1019
0
0,2067
0.1086
0.1793
0.0963
0,1502
0.1331
0.0762
20
0.0785
0.0785
0.2331
0.0968
0.1740
0.0774
0.1332
0.1158
0.0606
0.2629
0.2936
0.2951
0.2675
0.2575
0.3748
0.3722
0.2368
5
0.2328
0.2835
0,2430
0.2616
0.2255
0,3511
0.2977
0,1987
Lena
10
0.1830
0.2592
0.1925
0.2313
0.1695
0,3362
0,2330
0.1414
15
0,1457
0.1445
0.2430
0.1496
0.1821
0.1592
0.3147
0.1795
0.1170
20
0.1301
0.1257
0.2306
0.1321
0.1867
0.1256
0.3072
0.1710
0.0986
0.2460
0.2383
0.2953
0.2634
0.2524
0,2411
0.4502
0,3177
0.2000
0.2109
0.2049
0.2914
0.1978
0,2498
0.1965
0.3146
0.2546
0.1660
Parrot
10
0.1598
0.1547
0.2645
0,1609
0,2452
0.1502
0,2682
0,2163
0.1237
15
0,1377
0.1239
0.2551
0.1362
0.2334
0.1239
0,2606
0,1657
0.0980
20
0.1163
0.1054
0.2485
0.1239
0.2213
O. 10606
0.2186
0.1507
0.0812
3
0.2749
0.2767
0.3727
0.2825
0.3041
0,2747
0.4385
0.5908
0.2433
5
0,2456
0.2443
0,3684
0.2567
0.3019
0,2449
0,3730
0,3494
0.2091
Cameraman
10
0,2017
0.1953
0.3596
0,2282
0.2958
0.1945
0,3298
0.2348
0.1639
15
0.1729
0.1691
0.3527
0.1799
0.1835
0.1680
0,3035
0.2231
0.1347
20
0.1548
0. 1488
0,3449
0.1732
0.1805
0.1480
0,2922
0,1966
0.1143
3
0.1923
0.1911
0.2751
0,2154
0.2203
0.1892
0.2870
0.2363
0.1465
5
0,1473
0.1457
0.2675
0,2183
0.2190
0.1438
0.2578
0,1683
0.1154
Foreman
10
0.1060
0.1000
0.2564
0.1140
0.2059
0.1017
0.2273
0.1419
0.0771
15
0.0792
0.0805
0.2484
0.1009
0.1966
0.0792
0.2221
0.1293
0.0593
20
0.0669
0.0667
0.2463
0.1025
0.1874
0.0658
0.2175
0.0866
0.0501
*Available http://dap htm
and http:/
en/ ctcdu..c//aacltttt. faculty/
wadong/NIAR /ttp//iNR.._....e htm
28

---

Best Subset Selection: Optimal Pursuit for Feature Selection and Elimination
The experimental results show that the enhanced algorithm achieves significantly better performance than the original algorithm in the CSS task. The original algorithm generally outperforms the leverage score methods (SVD-128), while the enhanced algorithm consistently surpasses the leverage score method (SVD-256).
Notably, OP-(A)BESS achieves SOTA performance on this task, with approximation errors approaching the optimal bound given by SVD. This further highlights the substantial advantage of the new criteria on the CSS task.
W. Complex Signal Processing
In this task, we tested 1 22-diienniionl complex signal with 20 frequency components, applying the BSS algorithm to estimate the frequency components on an 2x oversampled Fourier domain. We used two evaluation metrics: cosine similarity (Corr) to assess the accuracy of amplitude recovery (higher is better) and Complementary Cumulative Distribution Function (CCDF) to measure frequency estimation error probability (lower is better).
By the high correlation between nearby frequency components, this also constitutes test scenario with highly correlated features. To evaluate algorithm performance, the target signal is constructed with closely spaced frequency components, resulting in high correlation among features in the true subset. The frequency domain visualization, radar plot, and the performance of these two metries are shown in Figure 13.
CoSaOP Spactral Eathnation on the Frequency Domath
OP-(AJBESS
Spactrol Dedmattion on the Ers Erequency Domain
Spectral Catimatiin en the Frequtncy Boeath
Eddimaoon (OP)
Ealrakie (CetacP)
Calmolion (OP-0N))
Oues 8315
Gan 2008
Davos 1980
do vs. Frequency
Magnttude va. Phose
vitue yu, Frequecy
Mage Ru en. Phose
Magattudl vs, Faequncty
Maggitado vs Phoae
120
up
DNY
OMP
CoSaMP
[AJBESS
Spectrol Gedimationn Frequency
Spectral Extimation Frequency Domain
Spectral Satination Frequency Domain
Specturs
Thu Speckarr
Specture
Calimatoon (DMP)
Exiredon (Codalir)
02211.000 1002
ccon 1100
da Frequency
Magnitude Phate
Magnittde Frequency
Magnitude dudd Phaas
Mag stude Faquancy
Mageitldd
Lonatie
Figure 13, Comparison of Optimal Pursuit enhanced algorithms and classic algorithms on complex signal processing.
From the experimental results, it evident that the enhanced algorithm achieves significantly lower frequency estimation error probability and higher correlation in the line spectrum estimation task. Notably, OP-(A)BESS and CoSaOP achieve perfect estimation in this task.
Since features in the line spectrum estimation problem are also highly correlated, these results further validate the substantial advantage of our proposed criteria in scenarios with high feature correlation.
29


Reviews:
[{"review_id": "J79biQ0Wcz", "reviewer": "Reviewer_uuYf", "summary": "The paper presents two novel criteria for feature selection, which are refinements on well studied approaches for identifying features which maximally improve (or reduce) prediction accuracy. By more rigorously considering the impact of features selected as a subset, rather than just individually, similar efficiency guarantees remain while improvements and learning are made.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your deep understanding and kind words on our work. We have carefully addressed your comments below and will incorporate this rebuttal into the revised version of the paper.\n\n---\n**Q1 (Why CoSaMP Fails):**\n\nThank you for your question. We implemented Algorithm 1 of CoSaMP [1] strictly and tested it alongside several example codes from MathWorks, obtaining consistent results. We will now provide a deeper analysis of the reasons behind CoSaMP's inefficiency in sparse regression tasks.\n\nAs discussed in Appendix M, CoSaMP iteratively (1) selects $2K$ features, (2) solves a least squares problem on a large subset, and (3) prunes to $K$ coefficients. However, high feature correlation can cause significant errors in the final estimate from steps (2) and (3). We visualize the impact of feature correlation on CoSaMP's iterative process here: [Fig: CoSaMP Visualization 1](https://drive.google.com/file/d/1Zs1C0Bp3NVnu0RqriajYSfJkcHyeWNYI/view?usp=sharing).\n\nAs shown, on a regression dataset with highly correlated features, the pruned support set’s direct coefficients (column 2) differ significantly from those after least squares estimation (column 3), with substantial residuals. CoSaMP, lacking least squares refinement, fails as the residuals grow with each iteration due to high feature correlation. This is evident in the residual curve evolution in (a): [Fig: Residual Curve](https://drive.google.com/file/d/1xp34dLCafqFV3tSvEHjkvsqEFTx_ehoM/view?usp=sharing).\n\nIn contrast, when features are weakly correlated (as in the Audioset [Fig: Audioset Example](https://drive.google.com/file/d/1vJiWa-jqo4NNSPAbRU2Ew6XXSBmDHyY7/view?usp=share_link)), the coefficients and residuals after pruning the large support set (column 2) and performing least squares (column 3) are nearly identical, leading to algorithm convergence, as shown in curve (b): [Fig: Residual Curve](https://drive.google.com/file/d/1xp34dLCafqFV3tSvEHjkvsqEFTx_ehoM/view?usp=sharing).\n\nIn summary, as noted in [1], CoSaMP's theoretical guarantees rely on weak feature correlation, leading to failure when this assumption is violated. In contrast, our CoSaOP algorithm remains effective. We further establish its theoretical foundation (**see Reviewer aZmj, Q1, Theorems 1, 2**), demonstrating how the new criteria enable algorithms that overcome high feature correlation challenges.\n\n---\n**Q2 (Difference from Tohidi et al 2025):**\n\nThank you for your question.\nTohidi et al. (2025) use submodularity and preconditioning, applicable only to the selection process. Our contribution, however, re-examines the foundational criteria in best subset selection from an optimization perspective. By modeling feature independence and interactions through block coordinate descent, we clarified the optimization essence of classical criteria and proposed a unified feature selection and elimination model. Using forward and backward matrix inversion, we derived new explicit criteria, providing a foundation for future algorithm design in best subset selection.\n\nIn this paper and rebuttal, we analyzed: (1) the criteria's theory under high feature correlations, (2) complexity and convergence, (3) empirical performance gains, and (4) performance across various tasks and metrics. These findings highlight the potential to relax theoretical assumptions and enable future engineering applications.\n\nMoreover, the optimal pursuit idea can be extended to other greedy metrics and algorithms, opening new directions for further research (**see Reviewer g7tw Q1**).\n\n---\n**References:**\n\n[1] Needell D, Tropp J A. CoSaMP: Iterative signal recovery from incomplete and inaccurate samples[J]. *Applied and computational harmonic analysis*, 2009, 26(3): 301-321.\n\n[2] Hastie, T., Tibshirani, R. and Friedman, J. (2017) *The Elements of Statistical Learning: Data Mining, Inference, and Prediction*. 2nd Edition, Springer, Berlin.\n\n[3] Belhadji A, Bardenet R, Chainais P. A determinantal point process for column subset selection[J]. *Journal of machine learning research*, 2020, 21(197): 1-62.\n\n[4] Blumensath T, Davies M E. Gradient pursuits[J]. *IEEE Transactions on Signal Processing*, 2008, 56(6): 2370-2382.\n\n[5] [OpenML Data](https://www.openml.org/search?type=data&sort=runs&id=574&status=active)\n\n[6] Lin Z, Pan W. A robust cis-Mendelian randomization method with application to drug target discovery[J]. *Nature communications*, 2024, 15(1): 6072.\n\n[7] Hastie, T., Tibshirani, R. and Friedman, J. (2017) *The Elements of Statistical Learning: Data Mining, Inference, and Prediction*. 2nd Edition, Springer, Berlin.\n\n[8] MATLAB and Statistics and Machine Learning Toolbox, \"Spectra Data,\" The MathWorks, Inc.", "claims_and_evidence": "Yes, all claims are supported with theoretical proofs and experimental results.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "I verified the proofs of Theorem 3.3 and 3.11 in the appendix.", "experimental_designs_or_analyses": "I reviewed the experimental results. I think a more thorough discussion of CoSaMP's failure is needed, both in terms of why the failure occurs and more experimental validation that this result is not in error.", "relation_to_broader_scientific_literature": "Yes, the authors well situate their results as they compare to prior feature selection methods.", "essential_references_not_discussed": "na", "other_strengths_and_weaknesses": "The paper is very well written, with helpful illustrations to hammer home the nuance in the idea for improving prior formalizations of the problem. Performance gains are further made abundantly clear by the provided experimental results. Moreover, the generality of these results is what's most intriguing to me--the methods take a fundamentally new approach to well studied solutions.", "other_comments_or_suggestions": "na", "questions_for_authors": "How does this paper differ from Tohidi et al 2025? The submodularity and matching pursuit approach their seem to overlap significantly with this work and she be discussed in more depth.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "L3ccOeXXNw", "reviewer": "Reviewer_aDws", "summary": "The paper proposes a new criterion for selecting and rejecting features in the context of the best subset selection problem. While previous methods primarily focused on the significance of individual features, the proposed approach offers the flexibility to capture interactions between features.\n\n## update after rebuttal\nThank you for addressing my concerns. However, in light of the comments made by other reviewers, I have decided to maintain my score.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful feedback on our theoretical foundation and flexibility. We have incorporated further explanations and experiments accordingly, and this rebuttal will be integrated into revised paper. For the references [1-8] in the rebuttal, please refer to **Reviewer uuYf**.\n\n---\n**Q1 (SOTA in BSS):**  \nWe appreciate your question, which prompted us to review the literature further. The state-of-the-art algorithm in Best Subset Selection (BSS) is ABESS, as confirmed by recent works [11]–[14], recognizing it as a leading or benchmark method.  \n\nWhile BSS and Feature Selection (FS) are related, they are not synonymous. BSS is a subset of FS, typically in a linear framework, while FS methods like neural networks and random forests employ nonlinear models. BSS addresses the NP-hard problem (equation (2) in the original paper) with efficient polynomial-time solutions.  \n\nTo highlight BSS’s contributions in FS, we conducted additional experiments on larger datasets and FS tasks.  \n\n---\n**Q2 (Larger dataset, various tasks, and task-specific metrics):**  \nWe expanded our tests to five tasks, ten more datasets, and six task-specific metrics.  \n\n1. **Phase Transition in Extreme Scenarios:**  \n   Experimental setting is detailed in Reviewer aZmj Q2, with results in: [Phase Transition](https://drive.google.com/file/d/1HY6-6XzeVTq-LUtehvQS1hZgjVvNSu7k/view).  \n\n   In cases with small samples, high-dimensional features, and high noise, BSS excels in identifying the true subset, whereas other FS methods struggle.  \n\n2. **Sparse Regression Tasks on Diverse Datasets:**  \n   We added three widely used BSS datasets: (1) House 16H [5], (2) Prostate.v8.egens [6-7], (3) Spectra [8]. The $R^2$ curves as a function of selected features are available here: [Fig: R2](https://drive.google.com/file/d/1v5Vz0lyVADuo2KVaUOr2ernVcSncC_t0/view?usp=sharing).  \n\n   Across all datasets, the enhanced algorithms outperform the original, achieving gains equivalent to selecting ten additional features.  \n\n3. **Cross-Validation in Prediction:**  \n   We evaluated BSS on six datasets using 5-fold cross-validation, where 4 folds were for training and 1 for validation. Prediction error is defined as:  $error_{pred} = \\frac{1}{n} \\sum_{i=1}^{n} (y_i - \\hat{y}_i)^2$. Cross-validation scores are shown here:  [Fig:CV](https://drive.google.com/file/d/1xQvgSCXXpgq4nqOlkJRxJw5dUgcCbrEV/view?usp=sharing).  \n\n   Enhanced algorithms exhibit superior generalization, validating the new metric’s effectiveness in predictive tasks.  \n\n4. **Column Subset Selection (CSS) in Unsupervised Learning:**  \n   CSS and PCA are key dimensionality reduction methods. While PCA forms linear combinations, reducing interpretability, CSS selects important features while better preserving the dataset’s structure.  \n\n   We tested eight 256×256 image datasets, using $||X - X(:,S)C||_F/||X||_F$ as the evaluation metric, with the leverage score method as a baseline. Optimal selection and deletion criteria, along with results, are here:  [Table:CCS](https://drive.google.com/file/d/1L3w-GHO9elAk4LKlhEjiDiWtR9vypUYA/view?usp=sharing).  \n\n   The enhanced algorithm outperforms the original, which surpasses SVD-128, while the enhanced version consistently beats SVD-256. OP-(A)BESS achieves SOTA performance, nearing the optimal SVD bound.  \n\n5. **Line Spectrum Estimation (Complex Signal Processing):**  \n   Our methods extend naturally to the complex domain. A key example is line spectrum estimation, a structured feature selection problem where features are continuous in the frequency domain:  $v(f) = [ 1, e^{-j 2\\pi f}, e^{-j 2\\pi 2f}, \\dots, e^{-j 2\\pi (N-1)f}]^T.$ This problem, crucial in modern wireless communications, involves decomposing a complex signal into its frequency components.  \n\n   We tested a 128-dimensional complex signal with 20 frequency components, applying BSS on an oversampled Fourier domain. Evaluation metrics included CCDF (lower is better) for frequency estimation error and cosine similarity (higher is better) for amplitude recovery. Frequency domain visualization, radar plot, and metric performance are available here:  [Fig:LSE](https://drive.google.com/file/d/1zr1tc-udPEttYkyViwom7zZy5WbvYp4j/view?usp=sharing).  \n\n   The enhanced algorithm significantly reduces frequency estimation errors and improves correlation. OP-(A)BESS and CoSaOP achieve perfect estimation, reinforcing our metric’s advantage in highly correlated feature settings.  \n\n---\n**References:**  \n\n[11] Wang, Zezhi, et al. \"skscope: Fast Sparsity-Constrained Optimization in Python.\" JMLR (2024). \n \n[12] Roy, Saptarshi, et al. \"On the Computational Complexity of Private High-dimensional Model Selection.\" NeurIPS (2024). \n \n[13] Lin, Zhaotong, et al. \"A robust cis-Mendelian randomization method with application to drug target discovery.\" Nature Communications (2024).  \n[14] Gregory C. Reinsel, et al. Multivariate Reduced-Rank Regression: Theory, Methods and Applications. Springer (2022).", "claims_and_evidence": "The proposed method offers the flexibility to account for the significance of individual features and the interactions among feature sets. Authors attribute the performance gains of their approach to the new modification made in the training objective. Experimental results demonstrate a significant improvement in model performance. However, I am curious about the choice of housing and superconductivity datasets for the experiments. A more comprehensive evaluation on a wider range of datasets is needed to fully validate the paper’s claims.", "methods_and_evaluation_criteria": "While the modification to the overall objective appears minor, the flexibility provided by the proposed approach is interesting. However, I am curious whether methods like ABESS represent the current state-of-the-art in the field. Additionally, many of the baselines used by the authors seem outdated. A comparison with more recent methods would strengthen the evaluation.", "theoretical_claims": "N/A", "experimental_designs_or_analyses": "As mentioned previously, a more comprehensive comparison across a larger set of datasets and recent baselines such as [1, 2] would provide better clarity on the usability and effectiveness of the proposed method.\n\n[1] Cherepanova, Valeriia, et al. \"A performance-driven benchmark for feature selection in tabular deep learning.\" Advances in Neural Information Processing Systems 36 (2023): 41956-41979.\n\n[2] Cohen, David, et al. \"Few-sample feature selection via feature manifold learning.\" International Conference on Machine Learning. PMLR, 2023.", "relation_to_broader_scientific_literature": "N/A", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Strength : \n1. The proposed method is well-grounded in theory and offers a strong intuitive justification for the flexibility it provides over previous methods. \n\n2. Paper is well written. \n\n3. A simple modification in the objective function clearly leads to substantial improvements over the baselines\n\nWeakness : \n1.  I am concerned with the relevance of the proposed method with the current literature around the optimal feature selection. The author should clarify the benefits of using the proposed method over the existing state of the art or compare the performance of their method with them.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "a8zWYJyjpc", "reviewer": "Reviewer_aZmJ", "summary": "This paper proposes two criteria for feature selection and feature elimination in the context of solving the best subset selection problem. The authors approach these criteria from an optimization perspective. These criteria can be incorporated into various heuristic subset selection algorithms. Additionally, the authors establish convergence guarantees for one such algorithm, CoSaOP. Numerical experiments are reported to demonstrate the effectiveness of new criteria against classical feature selection and elimination approaches. In particular, Sections 2 and 3 develop an optimization-based framework for feature selection and elimination. The authors highlight the limitations of classical criteria, which partially capture variations in the objective function due to feature addition or removal, and subsequently propose refined criteria to address these shortcomings. Furthermore, the two sub-problems are reformulated to enhance computational efficiency. Section 4 provides convergence guarantees for the CoSaOP algorithm. Section 5 presents numerical experiments on synthetic and real-world datasets, demonstrating the practical advantages of the proposed approach over existing heuristic methods.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your insightful question, which has driven us to further theoretical advancements. In this rebuttal, we address concerns raised in the reviews. For references [1-8], please refer to Reviewer uuYf.\n\n**Q1 (Theoretical Assumptions):** \nThank you for your question. The theoretical assumptions about algorithmic convergence in our work align with Section 2.3 of the CoSaMP paper [1]. Other best subset selection algorithms also rely on assumptions like the Restricted Isometry Property (RIP) due to the NP-hard nature of the problem. Without such assumptions, proving convergence for any polynomial-time algorithm would be intractable unless P = NP.\n\nHowever, your question led us to reflect further. Empirical observations reveal that even when theoretical assumptions are violated (e.g., correlated features), our proposed algorithm family performs well. This stems from our criteria’s explicit focus on feature interaction, motivating new theoretical frameworks under violated RIP conditions.\n\n**Theorem 1** Suppose the true subset $S^*$ contains indices $(i, j)$, where feature correlation is $\\rho$. Assuming $S$ includes $i$, then for the classical criterion:\n\\begin{equation}\n  \\frac{|{r^k}^T X_j|}{||X_j||_2} \\le \\sqrt{1-\\rho^2}||r^k||_2,\\tag{C1}\n\\end{equation}\nwhile our objective-based criterion (8) satisfies\n\\begin{equation}\n  \\frac{({r^k}^T X_j)^2}{X_j^T(I-X_S(X_S^TX_S)^{-1}X_S^T)X_j} \\ge \\frac{1}{1-\\rho^2}\\left(\\frac{{r^k}^TX_j}{||X_j||_2}\\right)^2.\\tag{C2}\n\\end{equation}\n\nTheorem 1 shows that under strong feature correlation, traditional criteria struggle to identify true features, while our criterion (8) provides a stable lower bound, mitigating correlation effects. If equality holds in (C1), substituting into (C2) eliminates dependence on $\\rho$, fully removing correlation influence. Additionally, (C2) connects our criterion (8) to classical ones.\n\nPseudo-correlation may arise in best subset selection. Pseudo-correlated features $X_p$ are highly correlated with important features $X_i$ in $S^*$ but do not belong to $S^*$. Classical T-statistics-based criteria struggle to remove such features, while our criterion (10) reliably identifies them.\n\n**Theorem 2**\n1) In noiseless cases, if $S^* \\subset S$, then for all $j_m \\in S \\setminus S^*$,\n\\begin{equation*}\nj_m \\in \\arg\\max_{j \\in S}~\\text{objective-based criterion (10)},\n\\end{equation*}\nwhereas classical criterion (4) lacks this guarantee.\n2) If $X_p \\in S$ is pseudo-correlated with $X_i \\in S^*$ (correlation $1 - \\epsilon$), when $\\epsilon$ is small, classical criteria (4) may discard true features, while our criterion (10) correctly removes $X_p$.\n\nThese theorems show our criterion (8) effectively identifies key features under strong correlation, and criterion (10) removes pseudo-correlated features. Experimental results in Q2 confirm superior performance. Theorems 1 and 2 pave the way for research on algorithm convergence under weakened RIP conditions. The detailed proof is provided in [The detailed proof](https://drive.google.com/file/d/1r7Y-2DZ07TD7ORxU72hwJi73dOFtIo29/view?usp=sharing)\n\n**Q2 (Experimental Design)**\nThank you for your suggestions. Due to character limits, we will include details on sparse vector and random Gaussian matrix generation, along with SNR definitions, in the revised paper. Additional comparisons were conducted under extreme conditions:\n\n1. Small sample rate, high-dimensional vectors: $p = 2000$, with $n/p$ varying from 0.05 to 0.1.\n2. High noise: SNR from 5 to 15.\n3. Highly correlated features (RIP violated): The covariance matrix of $X$ follows a Toeplitz structure, where $\\text{corr}_{ij} = \\rho^{|i-j|}$ with $\\rho = 0.7$.\n\nSparse vectors with sparsity level $K = 10$ were used. Phase transition diagrams illustrate how varying sampling rates and SNR impact performance. Larger blue areas indicate stronger performance.\n[Phase Transition](https://drive.google.com/file/d/1HY6-6XzeVTq-LUtehvQS1hZgjVvNSu7k/view)\n\nResults show that all algorithms enhanced with our criteria exhibit major improvements in phase transition capabilities, validating both theoretical insights from Q1 and advantages in high-dimensional, low-SNR cases.\n\nAdditional tests included sparse regression datasets, cross-validation, column subset selection, line spectral estimation, and other machine learning problems where feature correlation is prevalent. Enhanced algorithms consistently outperformed others.\n\n**Q3 (RHS of Eq.(19))**:\nThank you for your question. The matrix 2-norm used is: $\\text{norm}(D,2)= \\\\sqrt{\\\\lambda_{\\\\max}(D^TD)}.$\n\nSince $D$ is diagonal, $\\text{norm}(D,2) = \\\\max |D_{jj}|$. This justifies why Eq.(19) holds.\n\n**Q4 (Contributions and Other Greedy Criteria)**\nThank you for your question. Due to space constraints: For the contribution of this paper, see Reviewer g7tW (Q3). For other greedy criteria, we extend the optimal pursuit idea to Gradient Pursuit (Reviewer g7tW, Q1) and Column Subset Selection (Reviewer aDws, Q2, 4).", "claims_and_evidence": "The claims made in the submission are clear and also supported by their numerical experiments.", "methods_and_evaluation_criteria": "The proposed methods, i.e., CoSaOP, partially make sense under the assumptions provided in Appendix F. \n\nThe benchmark instances used in Section 5.1.1 are okay. However, the instances used in Sections 5.1.2 & 5.2 might not ensure the assumptions provided in Appendix F.", "theoretical_claims": "The proofs for theoretical results look correct on my side. However, the theoretical results provided in Section 4 need further assumptions and conditions, which may weaken the main contributions.", "experimental_designs_or_analyses": "Experimental designs are sound. \n\nThe experimental setup for the synthetic datasets would benefit from additional details. In Section 5.1.1, the generation procedures for the sparse vector $\\beta$ and the random Gaussian matrix $X$ are not clearly specified. Furthermore, the definition of the signal-to-noise ratio (SNR) is absent from the main text. To enhance the rigor of the study, the authors are encouraged to conduct further experiments with higher-dimensional settings and under conditions where the SNR values are low.", "relation_to_broader_scientific_literature": "NA", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "Weakness: \n\nThe paper is well-organized. However, the clarity of writing could be improved, and some key assumptions are omitted from the main content, which may significantly impact or weaken the theoretical results.\n\nThe originality is incremental. The proposed selection and elimination method follows a similar idea from vanilla local search, where the term \"optimal\" is based on maximizing over all possible single selection/elimination index. It is better to demonstrate whether the convergence results for the proposed optimal criteria would also hold for other greedy criteria.", "other_comments_or_suggestions": "Here are some minor comments for the authors to consider:\n\n1. Following the introduction, it would be beneficial to include a notation convention section to clarify the terminology used throughout the main text.\n\n2. In Remark 3.7, the authors assert that the proposed criteria do not introduce significant additional computational costs. An algorithmic complexity analysis should be provided to substantiate this claim.", "questions_for_authors": "NA", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "4vzaappKfW", "reviewer": "Reviewer_g7tW", "summary": "This paper introduces optimal pursuit strategies for feature selection and elimination in best subset selection problems. It challenges classical feature selection methods by offering new selection and elimination criteria, which focus on feature interactions as opposed to individual significance alone. The authors revisit the classic greedy algorithms, such as Matching Pursuit and Orthogonal Matching Pursuit, and propose enhanced algorithms by substituting their classical feature importance criteria with the new optimal pursuit criteria. The results demonstrate that these new methods outperform traditional approaches.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your feedback and constructive suggestions on our paper, which will help enrich the original content. In this rebuttal, we address the concerns raised in the reviews. For references [1-8] in the rebuttal, please refer to Reviewer uuYf.\n\n**Q1: (Complexity)**  Thank you for your excellent question, which has driven us to further our advancements.  \n\nFirst, the algorithmic complexity of our proposed criteria-enhanced algorithm remains at the same order as the original methods. Both rely on solving the least squares problem over a given subset $S$, which involves a linear system solved via Cholesky decomposition. As noted in Remark 3.7 and 3.15 of our paper, given the Cholesky decomposition, computing the matrix inverse requires only $O(K^2)$ complexity. Thus, despite the presence of inverse terms in our new metric, its computational complexity remains fundamentally equivalent to that of the original algorithm.  \n\nHowever, in ultra-high-dimensional settings, solving least squares over a subset can be prohibitive, affecting both the original and enhanced algorithms. Updating coefficients via least squares is equivalent to Newton’s method. [4] proposed Gradient Pursuit, which follows the same correlation-based selection strategy but replaces Newton’s method with gradient-based updates, significantly reducing computational overhead.  \n\nOur optimal pursuit idea extends to Gradient Pursuit, forming Optimal Gradient Pursuit (OGP), which simultaneously considers support set updates and coefficient updates while maintaining the same computational complexity as Gradient Pursuit.  \n\nIn this rebuttal, we explicitly derive the selection criterion for OGP:\n\\begin{equation}\\arg\\max_{j} \\begin{cases}\n\\frac{\\underline{||X_S^Tr^k||^2}+({r^k}^TX_j)^2}{||\\underline{X_SX_S^Tr^k} +X_jX_j^Tr^k||}, & j \\in S^c \\\\\\\\\n\\frac{\\underline{||X_S^Tr^k||^2}}{||\\underline{X_SX_S^Tr^k}||}, & j \\in S\n\\end{cases}\\end{equation}\nwhere the underlined part only needs to be computed once, keeping the overall complexity comparable to correlation-based selection in Gradient Pursuit. We establish OGP’s convergence theory and validate it with numerical experiments, demonstrating superior performance both theoretically and empirically.\n[FigOGP](https://drive.google.com/file/d/1kx7exKHUYToPS3wYuG4yTsVowCtkv92e/view?usp=sharing)\n\nWe compared GP and OGP runtime on numerical examples from our paper:\n[FigTime](https://drive.google.com/file/d/1RJ8yreuaGvReU2svoT-OrXCY4ILEZlMv/view?usp=sharing)\n\nBoth methods achieve an order-of-magnitude speedup over least squares-based subset selection. OGP provides an efficient acceleration scheme for the optimal pursuit strategy, extending its applicability to general objective functions in future research.\n\n**Q2 (Diverse datasets, machine learning tasks, and metrics evaluation)**  Thank you for your suggestion. We have conducted additional tests across five tasks, ten more datasets, and six metrics. Due to space constraints, please refer to Reviewer sDws (Q2) for details.\n\n**Q3 (Contributions)**  Thanks for your question. As stated in [2] (Section 3.3.2, pp. 59–60), best subset selection is built on forward feature selection and backward elimination. Greedy algorithms combine these criteria, with classical criteria based on correlation and T-statistics.  \n\nOur contribution lies in re-examining these foundational criteria from an optimization perspective. By modeling feature significance and interaction through a block coordinate descent framework, we clarified the optimization essence of classical criteria and proposed new selection and elimination models. Using forward and backward matrix inversion techniques, we derived explicit new criteria, providing a foundation for future best subset selection algorithms.  \n\nAdditionally, we further analyzed:  \n(1) Theoretical behavior under high feature correlations (Reviewer aZmj, Theorem 1\\&2).  \n(2) Complexity and algorithmic convergence.  \n(3) Empirical performance gains.  \n(4) Performance across various machine learning tasks and metrics.  \n\nOur work has significant potential:\n\n(1) Theoretically, our convergence results suggest the possibility of breaking existing RIP assumptions, advancing algorithmic study in this NP-hard problem.  \n(2) Practically, our new criteria significantly improve performance across machine learning tasks, datasets, and evaluation metrics, laying a foundation for future algorithm design.  \n\nFurthermore, our optimal pursuit idea extends to other greedy methods, such as Optimal Gradient Pursuit.\n\n**Q4 (Implementation)** Thank you for your suggestion. We recognize the importance of practical implementation and plan to open-source all code, covering the original algorithm, extensions, and accelerated optimal gradient pursuit, along with detailed workflow guidance.\n\nWe will also provide tutorials on applying the algorithm to best subset selection, column subset selection, line spectrum estimation, and other machine learning applications.", "claims_and_evidence": "Please refer to **Questions For Authors**.", "methods_and_evaluation_criteria": "Please refer to **Questions For Authors**.", "theoretical_claims": "Please refer to **Questions For Authors**.", "experimental_designs_or_analyses": "Please refer to **Questions For Authors**.", "relation_to_broader_scientific_literature": "Please refer to **Other Strengths And Weaknesses**.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "**Strengths:**\n\n1. The paper challenges existing greedy algorithms by proposing a more holistic method to evaluate feature importance, accounting for interactions between features, leading to more optimal feature selection.\n\n2. The paper is mathematically rigorous and builds a strong theoretical foundation for the proposed optimal selection and elimination criteria.\n\n3. The algorithms are experimentally validated across tasks like compressed sensing and sparse regression, showing clear improvements in performance metrics such as recovery rates and computational time efficiency.\n\n4. Despite the added complexity of the new criteria, the algorithms maintain the computational efficiency of the classical greedy methods.\n\n**Weaknesses:**\n\nPlease refer to **Questions For Authors**.", "other_comments_or_suggestions": "Please refer to **Questions For Authors**.", "questions_for_authors": "**Weaknesses:**\n﻿\n1. The proposed optimal pursuit strategy involves solving optimization subproblems for feature selection and elimination in a more detailed manner, incorporating interactions between features. While mathematically elegant, this additional complexity can make the algorithms harder to implement and computationally expensive for practitioners. The algorithms also involve matrix inversions, which could potentially increase the time complexity and make them unsuitable for high-dimensional problems where feature selection is crucial.\n﻿\n2. Although the paper demonstrates the effectiveness of the proposed algorithms in compressed sensing and sparse regression tasks, these are relatively specific domains. The algorithms are not evaluated on a wider variety of machine learning tasks or diverse datasets. \n﻿\n3. While the authors present important optimizations to classical feature selection algorithms, the core contribution seems to build upon existing algorithms. Many of the proposed algorithms can be seen as modifications of existing approaches rather than a completely novel class of algorithms. This lack of a breakthrough contribution might limit the paper’s impact and novelty compared to other works in the field.\n﻿\n4. While the paper is mathematically thorough, it lacks detailed practical insights or step-by-step implementation guidelines for those who might want to apply these new algorithms. There is minimal discussion on potential limitations or challenges in applying these methods in real-world machine learning systems. \n﻿\n5. The paper uses standard metrics like NMSE and $R^2$ for evaluation, which are common in compressed sensing and sparse regression tasks. However, the paper does not explore a wider variety of evaluation criteria, such as cross-validation performance or other task-specific metrics. \n\n﻿**Conclusion:**\n\nThe weaknesses primarily stem from the increased complexity and limited generalization of the proposed methods, along with an incremental contribution that builds upon existing techniques. While the proposed algorithms are a meaningful enhancement for specific tasks like compressed sensing, they may not significantly advance the field of feature selection in a broad sense. Furthermore, the lack of a deep dive into practical implementation challenges and a broader experimental validation means that the paper may not be as impactful or widely applicable in its current form. I hope the author can address my concerns and change my expected rating.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper proposed two criteria for feature selection and feature elimination for the best subset selection problem, which are motivated from optimization perspective and incorporated into various subset selection algorithms. Convergence guarantees for CoSaOP is established. Reviewers raised some concerns regarding the assumptions of the theoretical results, the incremental contribution to existing work, outdated baselines, and the simulation data in experimental design. Authors made great efforts on addressing these concerns with more theoretical results and experiments. However, some critical concerns remain unsolved: the presented theoretical results are not explicitly supporting for strong correlation even though the additionally presented experimental results empirically demonstrated that; outdated baselines can be improved by including more recent works. As a result, weak accept is recommended.
Decision: Accept (poster)