Sequential Attention for Feature Selection
Authors: Taisuke Yasuda
Mohammadhossein Bateni
Lin Chen
Matthew Fahrbach
Gang Fu
Vahab Mirrokni
Venue: ICLR 2023 poster (2023)
Keywords: feature selection
attention

Abstract: Feature selection is the problem of selecting a subset of features for a machine learning model that maximizes model quality subject to a budget constraint. For neural networks, prior methods, including those based on $\ell_1$ regularization, attention, and other techniques, typically select the entire feature subset in one evaluation round, ignoring the residual value of features during selection, i.e., the marginal contribution of a feature given that other features have already been selected. We propose a feature selection algorithm called Sequential Attention that achieves state-of-the-art empirical results for neural networks. This algorithm is based on an efficient one-pass implementation of greedy forward selection and uses attention weights at each step as a proxy for feature importance. We give theoretical insights into our algorithm for linear regression by showing that an adaptation to this setting is equivalent to the classical Orthogonal Matching Pursuit (OMP) algorithm, and thus inherits all of its provable guarantees. Our theoretical and empirical analyses offer new explanations towards the effectiveness of attention and its connections to overparameterization, which may be of independent interest.

Published as a conference paper at ICLR 2023
SEQUENTIAL ATTENTION FOR FEATURE SELECTION
Taisuke Yasuda" Carnegie Mellon University taisukeyêcs. cmu. edu
MossmmadHossein Bateni, Lin Chen, Matthew Fahrbach, Gang Fu, and Vahab Mirrokni
Google Research
(bateni, , inche,, fahrbach, miroronimmiirrkiiieeee wowp::kennnnegooee...ooooo
ABSTRACT
Feature selection is the problem of selecting subset of features for a machine learn- ing model that maximizes model quality subject budget constraint. For neural networks, prior methods, including those based on l regularization, attention, and other techniques, typically select the entire feature subset in one evaluation round, ignoring the residual value of features during selection, i.e., the marginal contribution of feature given that other features have already been selected. We propose a feature selection algorithm called Sequential Attention that achieves state-of-the-art empirical results for neural networks. This algorithm is based on an efficient one-pass, implementation of greedy forward selection and uses attention weights each step as a proxy for feature importance. We give theoretical insights into our algorithm for linear regression by showing that an adaptation to this setting is equivalent to classical Orthogonal Matching Pursuit (OMP) algorithm, and thus inherits all of its provable guarantees. Our theoretical and empirical analyses offer new explanations towards the effectiveness attention and its connections to overparamcteriizaion,, which may be of independent interest.
INTRODUCTION
Feature selection classic problem in machine learning and statistics where one is asked to find subset of l features from larger set of d features, such that the prediction quality of the model trained using the subset of features is maximized. Finding small and high-quality feature subset desirable for many reasons: improving model interpretability. reducing inference latency, decreasing model size, regularization, and removing redundant or noisy features to improve generalization. We direct the reader to Li et al. (2017b) for survey the role of feature selection in machine learning.
The widespread success deep learning has prompted an intense study of feature selection algorithms for neural networks, especially in the supervised setting. While many methods have been proposed, we focus on line of work that studies the use of attention for feature selection. The attention mechanism in machine learning roughly refers to applying trainable softmax mask to given layer. This allows the model to "focus" on certain important signals during training. Attention has recently led major breakthroughs in computer vision, natural language processing, and several other areas of machine learning (Vaswani et al., 2017). For feature selection, the works of Wang et al. (2014) 4); Gui al. (2019); Skrlj al. (2020); Wojtas & Chen (2020); Liao al. (2021) all present new approaches for feature attribution, ranking, and selection that are inspired by attention.
One problem with naively using attention for feature selection is that it can ignore the residual values of features, i.c., the marginal contribution a feature has on the loss conditioned on previously features being in the model. This can lead several problems such selecting redundant features or ignoring features that are uninformative in isolation but valuable in the presence of others.
"Corresponding authors This work done while T.Y. an intern Google Research.

---

Published as a conference paper at ICLR 2023
((;0)
1000)
softnax(w.55
Hadamard product
Inpul vectur
Original model
Sequential Atiention model: S Ø
Sequentil Attention model: S (1.2)
Sequential attention applied to model [(: 0). At each step, the selected features i S used as direct inputs to the model and the unselected features i & S are downscaled by the scalar value softmax, (w, 5), where w E Ie is the vector of learned attention weights and S [d] \ S.
Figure I:
This work introduces the Sequential Attention algorithm for supervised feature selection. Our algo- rithm addresses the shortcomings above by using intention-based selection adaptively over multiple rounds. Further, Sequential Attention simplifies earlier attention-based approaches by directly training one global feature mask instead of aggregating many instance-wise feature masks. This technique reduces the overhead of our algorithm. eliminates the toil of tuning unnecessary hyperparameters. works directly with any differentiable model architecture, and offers efficient streaming implemen- tation. Empirically, Sequential Attention achieves state-of-the-ar feature selection results for neural networks on standard benchmarks. The code for our algorithm and experiments is publicly available."
Sequential Attention. Our starting point for Sequential Attention is the well-known greedy forward selection algorithm, which repeatedly selects the feature with the largest marginal improvement in model loss when added to the set of currently selected features (see, e.g., Das & Kempe (2011) I) and Elenberg et al. (2018)). Greedy forward selection is known to select high-quality features, but requires training (kd) models and is thus impractical for many modern machine learning problems. To reduce this cost, one natural idea is to only train i models, where the model trained in each step approximates the marginal gains of all ((d) unselected features. Said another way, we can relax the greedy algorithm to fractionally consider all (dd) feature candidates simultaneously rather than computing their exact marginal gains one-by-one with separate models. We implement this idea by introducing a new set trainable variables w E Rd that represent feature importance, or attention logits. In each step, we select the feature with maximum importance and add it to the selected set. To ensure the score-augee srore-augmented models (1) have differentiable architectures and (2) are encouraged to hone in on the best unselected feature, take the sofimax of the importance scores and multiply each input feature value by its corresponding softmax value as illustrated in Figure 1.
Formally, given dataset X E Raxd represented matrix with columns, suppose we want to select l: features. Let (:; 9) be a differentiable model, e.g., a neural network, that outputs the predictions f(; 0). Let y E E be the labels, (X; 0), be the loss between the model's predictions and the labels, and o be the Hadamard product. Sequential Attention outputs subset
of examples and d feature
C [d] := (1,2....,d d} of le feature indices, and is presented below in Algorithm 1.
Theoretical guarantees. We give provable guarantees for Sequential Attention for least squares linear regression by analyzing variant of the algorithm called regularized linear Sequential Attention. This variant (1) uses Hadamard product overparameterization directly between the attention weights and feature values without normalizing the attention weights via soft S), and (2) adds &a regularization to the objective, hence the "linear" and "regularized" terms. Note that & regularization, weight decay, is common practice when using gradient-basee optimizers (Tibshirani, 2021). We give theoretical and empirical evidence that replacing the softmax by different overparameterizzatio schemes leads similar results (Section 4.2) while offering more tractable analysis. In particular, our main result shows that regularized linear Sequential Attention has the same provable guarantees as the celebrated Orthogonal Matching Pursuit (OMP) algorithm of Pati al. (1993) for sparse linear regression, without making any assumptions on the design matrix or response vector.
Theorem 1.1. For linear regression, regularized linear Sequential Attention is equivalent to OMP.
'The code is available at: aht.ahannttoeeecccoooooooooooeee attention
2

---

Published as a conference paper at ICLR 2023
Algorithm 1 Sequential Attention for feature selection.
1: function STOUTANTAALYYTTTNTTNNNEES E Ruud labels y E R," model f, loss e, size k)
2: Initialize S <- Ø
3: fort = to do
4: Let (0", w*) arg minl,w l(f(X w: where W = 1, Insoftmax(w,5) 3) for
i
softmax;(w,5) =
exp(w,) jes exp(w;)
i S \
5: Set 1" arg max W
> unselected feature with largest attention weight
6:
Update S + SU((')
7:
return
We prove this equivalence using a novel two-step argument. First, we show that regularized linear Sequential Attention is equivalent to a greedy version of LASSO (Tibshirani, 1996), which Luo & Chen (2014) call Sequential LASSO. Prior to our work, however, Sequential LASSO was only analyzed in a restricted "sparse signal plus noise" setting, offering limited insight into its success in practice. Second, prove that Sequential LASSO is equivalent to OMP in the fully general setting for linear regression by analyzing the geometry of the associated polyhedra. This ultimately allows us transfer the guarantees of OMP to Sequential Attention.
Theorem 1.2. For linear regression, Sequential LASSO (Luo & Chen, 2014) is equivalent OMP.
We present the full argument for our results in Section 3. This analysis takes significant steps towards explaining the success of attention in feature selection and the various theoretical phenomena at play.
Towards understanding attention. An important property of OMP is that it provably approximates the marginal gains of features -Dauu & Kempe (2011) showed that for any subset of features, the gradient of the least squares loss at its sparse minimizer approximates the marginal gains up to a factor that depends the sparse condition numbers of the design matrix. This suggests that Sequential Attention could also approximate some notion of the marginal gains for more sophisticated models when selecting the next-best feature. We observe this phenomenon empirically our marginal gain experiments in Appendix B.6. These results also help refine the hisely-assumed conjecture that attention weights correlate with feature importances by specifying an exact measure of "importance" at play, Since a countless number of feature importance definitions are used in practice, it is important to understand which best explains how the attention mechanism works.
Connections to overparameterizatton. In our analysis of regularized linear Sequential Attention for linear regression, we do not use the presence of the softmax in the attention the crucial ingredient in our analysis is the Hadamard product parameterization of the learned weights. We conjecture that the empirical success of attention- based feature selection is primarily due to the explicit overparameterization? 2 Indeed, our experiments in Section 4.2 verify this claim by showing that if we substitute the softmax in Sequential Attention with number of different (normalized) overparamterized expressions, we achieve nearly identical performance. This line of reasoning is also supported in the recent work of Ye et al. (2021), who claim that attention largely owes its success to the "smoother and stable [loss] landscapes" induced by Hadamard product overparameterizztion.
1.1 RELATED WORK
Here we discuss recent advances in supervised feature selection for deep neural networks (DNNs) that are the most related to our empirical results. particular, we omit a discussion of large body of works unsupervised feature selection (Zou al., 2015; Altschuler et al., 2016; Balm et al., 2019).
2 Note that overparameterization here refers to the addition of d trainable variables in the Hadamard product overparameterizzaton,, not the other use of the term that refers to the use of massive number of parameters in neural networks, e.g., in Bubeck & Sellke (2021).
3

---

Published as a conference paper at ICLR 2023
The gnoup LASSO method has been applied DNNs achieve structured sparsity by pruning neurons (Alvarez & Salzmann, 2016) and even filters or channels in convolutional neural networks (Lebedev & Lempitsky, 2016; Wen et al., 2016; Li et al., 2017a). It has also be applied for feature selection (Zhao et al., 2015; Li et al., 201 6; Scardapane et al., 2017; Lemhadri et al., 2021).
While the LASSO is the most widely-used method for relaxing the Eo sparsity constraint in feature selection, several recent works have proposed new relaxations based on stochastic gates (Srinivas al., 2017; Louizos al., 2018; Balm al., 2019; Trelin & Procházka, 2020; Yamada et al.. 2020). This approach introduces (learnable) Bernoulli random variables for each feature during training, and minimizes the expected loss over realizations of the 0-1 variables (accepting or rejecting features).
There are several other recent approaches for DNN feature selection. Roy et al. (2015) explore using the magnitudes of weights in the first hidden layer to select features. Lu al. (2018) designed the DeepPINK architecture, extending the idea of knockoff's (Benjamini et al., 2001) to neural networks. Here, each feature competes with a "knockoff" version of the original feature; if the knockoff wins, the feature is removed. Borisov et al. (2019) introduced the CancelOut layer, which suppresses irrelevant features via independent per-feature activation functions that act as (soft) bitmasks.
In contrast to these differentiable approaches, the combinatorial optimization literature is rich with greedy algorithms that have applications in machine learning (Zadeh et al., 2017; Fahrbach et al., 2019b;a; Chen al., 2021; Halabi et al., 2022; Bilmes, 2022). In fact, most influential feature selection algorithms from this literature are sequential, c.g., greedy forward and backward selection (Ye & Sun, 2018; Das et al., 2022). Orthogonal Matching Pursuit (Pati et al., 1993). and several information- theoretic methods (Fleuret, 2004; Ding & Peng, 2005; Bennasar et al., 2015). These approaches, however, are normally tailored to neural networks, and can suffer from quality, efficiency, both.
Lastly, this paper studies global feature selection, i.e., selecting the same subset of features across all training examples, whereas many works consider local (or instance-wist feature selection. This problem is more related to model interpretability, and is better known as feature attribution or saliency maps. These methods naturally lead to global feature selection methods by aggregating their instance-wise scores (Cancela et al., 2020). Instance-wise feature selection has been explored using a variety of techniques, including gradients (Smilkov et al., 2017: Sundararajan et al., 2017; Srinivas & Fleuret, 2019), attention (Arik & Pfister, 2021; Ye et al., 2021), mutual information (Chen et al., 2018), and Shapley values from cooperative game theory (Lundberg & Lee, 2017).
PRELIMINARIES
Before discussing our theoretical guarantees for Sequential Attention in Section 3, we present several known results about feature selection for linear regression, also called sparse linear regression. Recall that in the least squares linear regression problem, we have
(( 0). [X 0) y1l = x0 x0-1112
(2)
We work in the most challenging setting for obtaining relative error guarantees for this objective by making distributional assumptions X paxd, i.c., we seek 0 E Rd such that
X6
yll
min BER
|XO -y1
for some k = x(X) 0, where X is not assumed to follow any particular input distribution. This far more applicable in practice than assuming the entries of X are i.i.d. Gaussian. In large-scale applications, the number of examples often greatly exceeds the number of features d, resulting in an optimal loss that is nonzero. Thus, we focus on the overdetermined regime and refer to Price et al. (2022) for an excellent discussion on the long history of this problem.
Ruxd be the design matrix with Eg unit columns and let y E R be the response vector, also assumed to be an &g unit vector. 3 For S C [d]. let X denote the [S] matrix consisting of the columns of X indexed by S. For singleton sets 5 {i}. we write X, for X1))- Let P denote the projection matrix onto the column span colspan (Xs) of Xs. where x denotes the pseudoinverse of Xs. Let P I, - Ps denote the projection matrix onto the orthogonal complement of colspan s))
Notation.
Let X
'These assumptions are without loss of generality by scaling.
4

---

Published as a conference paper at ICLR 2023
Feature selection algorithms for linear regression. Perhaps the most natural algorithm for sparse linear regression is greedy forward selection, which was shown to have guarantees the form of (3) in the breakthrough works of Das & Kempe (2011); Elenberg et al. (2018), where A x(X) depends on sparse condition numbers X, i.e., the spectrum of restricted to a subset of its columns. Greedy forward selection be expensive practice, but these works also prove analogous guarantees for the more efficient Orthogonal Matching Pursuit algorithm, which we present formally in Algorithm 2.
Algorithm 2 Orthogonal Matching Pursuit (Pati al., 1993).
1: function OMP(de matrix E RRadd response y E RR, size constraint k))
2: Initialize S Ø
3: for t = 1 k do
4: Set 33 < arg mingass X
5: Let & maximize
maximum correlation with residual
- (X,.y Psy) = (x,, Psy)2
6:
Update S + SU
7:
return S
The LASSO algorithm (Tibshirani, 1996) is another popular feature selection method, which simply adds i -regularization to the objective in Equation (2). Theoretical guarantees for LASSO are known the underteterm regime (Donoho Flad, 2003; Candes & Tao, 2006), but it an open problem whether LASSO has the guarantees of Equation (3). Sequential LASSO is related algorithm that uses LASSO to select features one by one. Luo & Chen (2014) analyzed this algorithm in a specific parameter regime, but until our work, no relative error guarantees were known in full generality (e.g.. the overdetermined regime). We present the Sequential LASSO in Algorithm
Algorithm 3 Sequential LASSO (Luo & Chen, 2014).
1: function SEQUENTALLASSSOOea
matrix X Raxd response y R size constraint k:)
2: Initialize S + Ø
3: for ? 1 do
4: Let 3 (A, S) denote the optimal solution to
arg min BER
X33 2
y1 A|1
5:
Set X²( + $t 0
largest with nonzero LASSO on 3
6: Let A(S) = lim, (1E5: -,,)) #0}
7: Select any i" A(S)
non-empty by Lemma 3.5
8:
Update S + {
9: return S
Note that Sequential LASSO as stated requires a search for the optimal X in each step. In practice, can simply be set large enough value to obtain similar results, since beyond critical value of the feature ranking according to LASSO coefficients does not change (Efron et al., 2004).
3 EQUIVALENCE FOR LEAST SQUARES: OMP AND SEQUENTIAL ATTENTION
In this section, we show that the following algorithms are equivalent for least squares linear regression: regularized linear Sequential Attention, Sequential LASSO, and Orthogonal Matching Pursuit.
3.1 REGULARIZED LINEAR SEQUENTIAL ATTENTION AND SEQUENTIAL LASSO
We start by formalizing a modification to Sequential Attention that admits provable guarantees. Definition 3.1 (Regularized linear Sequential Attention). Let S C [d] be the set of currently se- lected features. We define the regularized linear Sequential Attention objective by removing the
5

---

Published as a conference paper at ICLR 2023
20
66
15
1/
64
Figure 2: Contour plot of (* (Bo,3) for
B E R2 at different zoom-levels [..].
40
00
softmax w, S) normalization in Algorithm 1 and introducing l2 regularization the importance weights w E R and model parameters 0 E Rd restricted to S. That is, we consider the objective
X (|00)))0s))))
min WERL DER
((s(w)= 0) -11 2
(5)
where s(w) o f denotes the Hadamard product, 0g E IRS is 0 restricted to indices in S, and
i s (w. = W if
By simple argument due to Hoff (2017), the objective function in (5) is equivalent to X0 - y112 + 1103111
min OERd
(6)
It follows that attention (or more generally overparameterization by trainable weights w) can be seen as way to implement & regularization for least squares linear regression, i.e., the LASSO (Tibshirani, 1996). This connection between overparameterization and f regularization has also been observed in several other recent works (Vaskevicius et al., 2019; Zhao et al., 2022; Tibshirani, 2021).
By this transformation and reasoning, regularized linear Sequential Attention be seen iteratively using the LASSO with & regularization applied only to the unselected features- is precisely the Sequential LASSO algorithm in Luo & Chen (2014). If we instead use softmax (w, S) as in (1), then this only changes the choice of regularization, as shown in Lemma 3.2 (proof in Appendix A.3).
Lemma 3.2. Let D : Rd + R be the function defined by D(w): = 1/softmaxx (w, for E B.
Denote its range and preimage by ran (D) S R and D D- (.) C Rd., respectively. Moreover, define the functions Q ran(D) R and Q' R + R by
Exx++Q(a)))
Q(q) = inf
w and (x(x)= inf qEran(D)
wED (q)
iES
Then, the following two optimization problems with respect B Rd equivalent:
|| x11 + ( [|w12 + +10111)=
> y113 Q² (7)
inf
inf BEk
XB
BERd (essootmax(w.3)ooomm WER" ,EE""
2
We present contour plots of ( o }3 for B E R² in Figure 2. These plots suggest that Q* (B o 3
a concave regularizer when |31| + [,2z] > which would thus approximate the la regularizer and induce sparse solution of / (Zhang & Zhang, 2012), as & regularization does (Tibshirani, 1996).
3.2 SEQUENTIAL LASSO AND OMP
This connection between Sequential Attention and Sequential LASSO gives us a new perspective about how Sequential Attention works. The only known guarantee for Sequential LASSO, the best of our knowledge, is a statistical recovery result when the input is a sparse linear combination with Gaussian noise in the ultra sigh--immnsional setting (Luo & Chen, 2014). This does not, however, fully explain why Sequential Attention is such an effective feature selection algorithm.
To bridge main results, we prove novel equivalence between Sequential LASSO and OMP.

---

Published as a conference paper at ICLR 2023
Theorem 3.3. Let X Baxd be design matrix with &g unit vector columns, and let R denote the response, also an l2 unit vector. The Sequential LASSO algorithm maintains a set of features S S [d] such that, each feature selection step, it selects feature i E S such that
(X, X
where Xs is the n x |S] matrix given formed by the columns of X indexed by S, and Ps is the projection matrix onto the orthogonal complement of the span of X.s.
Note that this is extremely close to saying that Sequential LASSO and OMP select the exact same set of features. The only difference appears when there are multiple features with norm |X P Iloe. In this case, it is possible that Sequential LASSO chooses the next feature from a set of features that is strictly smaller than the set of features from which OMP chooses, so the "tie-breaking" can differ between the two algorithms. In practice, however, this rarely happens. For instance, if only one feature selected at each step, which is the case with probability 1 random continuous noise added to the data, then Sequential LASSO and OMP will select the exact same set of features.
Remark 3.4. It was shown in (Luo & Chen, 2014) that Sequential LASSO is equivalent to OMP in the statistical recovery regime, i.e., when y X,3 + e for some sparse weight vector 3 and i..dd Gaussian noise & ~ (O, II,), under an ultra high-dimensional regime where the dimension d exponential in the number of examples n. We prove this equivalence the fully general setting.
The argument below shows that Sequential LASSO and OMP are equivalent, thus establishing that regularized linear Sequential Attention and Sequential LASSO have the same approximation guarantees OMP.
Geometry of Sequential LASSO. We first study the geometry of optimal solutions to Equation (4). Let S S [d] be the set of currently selected features. Following work the LASSO in Tibshirani & Taylor (201 1), we rewrite (4) as the following constrained optimization problem:
1 2 -11 1113,11
min EER" BER
2
(8)
subject to
= X33.
can then be shown that the dual problem is equivalent to finding the projection, i.e., closest point in Euclidean distance, E IR" of Psy onto the polyhedral section C3 O colspan (Xs)+ where
C {u's R x S _}}
and colspan(X33 { denotes the orthogonal complement of colspan(Xs). See Appendix A.1 for the full details. The primal and dual variables are related through z by
X = 11
Selection of features in Sequential LASSO. Next, we analyze how Sequential LASSO selects its features. Let 3%g = X the optimal solution for features restricted in S. Then, subtracting X x from both sides of (9) gives
X X = y- X - u
(10)
= -P u.
Note that if A 2 X T Plyylooc
then the projection of Ps onto Cx is just u Psy. so by (10),
X X P P 0,
meaning that /3 is zero outside of S. We now show that for À slightly smaller than X P the residual P.y- - u is in the span of features X; that maximize the correlation with Ply.
Lemma 3.5 (Projection residuals of the Sequential LASSO). Let denote the projection of P onto CA colspan (Xs)= There exists No < || Pssll such that for all X E (No, | P (oo) the residual p p lies colspan for
T T= {i [d] (x,, Psy = TTPxylll..
7

---

Published as a conference paper at ICLR 2023
We defer the proof of Lemma 3.5 to Appendix A.2.
By Lemma 3.5 and (10), the optimal / when selecting the next feature has the following properties:
1. i E S, then B, is equal to the i-th value in the previous solution gg: and
2. if i E S, then P1 can be nonzero only if i T.
It follows that Sequential LASSO selects feature that maximizes the correlation (X P. as OMP does. Thus, we have shown an equivalence between Sequential LASSO and OMP without any additional assumptions.
EXPERIMENTS
4.1 FEATURE SELECTION FOR NEURAL NETWORKS
Small-scale experiments. We investigate the performance of Sequential Attention, as presented in Algorithm 1, through experiments standard feature selection benchmarks for neural networks. In these experiments, we consider six datasets used in experiments in Lemhadri et al. (2021); Balm et al. (2019), and select k 50 features using one-layer neural network with hidden width 67 and ReLU activation (just as in these previous works). For more points of comparison, we also implement the attention-basee feature selection algorithms of Balm al. (2019); Liao al. (2021) and the Group LASSO, which has been considered in many works that aim to sparisfly neural networks as discussed in Section 1.I. We also implement natural adaptations of the Sequential LASSO and OMP for neural networks and evaluate their performance.
we see that Sequential Attention competitive with or outperforms all feature selection algorithms on this benchmark suite. For each algorithm, we report the mean of the prediction accuracies averaged over five feature selection trials. We provide more details about the experimental setup in Appendix B.2, including specifications about each dataset in Table and the mean prediction accuracies with their standard deviations in Table 2. We also visualize the selected features on MNIST (i.e., pixels) in Figure 5.
In Figure 3,
Mice Protein
MINIST
MNIST.Fashion
1.00
Predictio Accuncc
0.96
0.86
Prodicton
6.99
0.94
0.98
0.97
5A
LLY
GL
SL
ONP
CAE
0.90
5A
LLY
GL
SL
GMP
CAE
0.82
5A
LEY
GL
SL
OMP
CAE
ISOLET
Pred Prediction Accursyy
1.00
Acquracy
0.925
0.98
0.92
Prediction
0.900
0.30
0.96
0.875
0.850
0MP CAE
0.94
5A
Figure 3: Feature selection results for small-scale neural network experiments. Here, SA = Sequential Attention, LLY = (Liao et al., 2021), GL = Group LASSO, SL = Sequential LASSO, OMP = OMP, and CAE = Concrete Autoencoder (Balin al., 2019).
We note that our algorithm is considerably more efficient compared to prior feature selection algo- rithms, especially those designed for neural networks. This is because many of these prior algorithms introduce entire subnetworks to train (Balın et al., 2019; Gui et al., 2019; Wojtas & Chen, 2020; Liao al., 2021). whereas Sequential Attention only adds d additional trainable variables. Furthermore, in these experiments, we implement an optimized version of Algorithm that only trains one model rather than à models, by partitioning the training epochs into & parts and selecting one feature in each of these k parts. Combining these two aspects makes for an extremely efficient algorithm. We provide evaluation of the running time efficiency of Sequential Attention in Appendix B.2.3.
Large-scale experiments. To demonstrate the scalability of our algorithm, we perform large-scale feature selection experiments the Criteo click dataset, which consists of 39 features and over three
8

---

Published as a conference paper at ICLR 2023
billion examples for predicting click-through rates (Diemert Eustache, Meynet Julien et al., 2017). Our results in Figure 4 show that Sequential Attention outperforms other methods when at least 15 features selected. In particular, these plots highlight the fact that Sequential Attention excels at finding valuable features once a few features are already in the model, and that has substantially less variance than LASSO-based feature selection algorithms. See Appendix B.3 for further discussion.
5,7800
Sequential Ameniton
CHI
8.7125
Group LASSO,
9,7275
0.330
Sequeriil
[L322923)
03395
5.700
0.350
57175
20
0.3353
Number Selecie Fostures
Number Selecred Features
Figure 4: AUC and log loss when selecting & E {10, 15, 20, 30,35) features for Criteo dataset.
4.2
THE ROLE OF HADAMARD PRODUCT OVERPARAMETERIZZAIE IN ATTENTION
In Section 1, we argued that Sequential Attention has provable guarantees for least squares linear regression by showing that version that removes the softmax and introduces &g regularization results in an algorithm that is equivalent OMP. Thus, there a gap between the implementation of Sequential Attention in Algorithm 1 and our theoretical analysis. We empirically bridge this gap by showing that regularized linear Sequential Attention yields results that are almost indistinguishable to the original version. In Figure 10 (Appendix B.5), we compare the following Hadamard product overparameterization schemes:
softmax: as described in Section
f (w) w, for S, which captures the provable variant discussed in Section
bg s,(w) w for 5
& normalized: s; s((w) w E55 for E
f2 normalized: s:(w) = w.13 / ww] for E
Further, for each of the benchmark datasets, all of these variants outperform LassoNet and the other baselines considered in Lemhadri al. (2021). See Appendix B.5 for more details.
5 CONCLUSION
This work introduces Sequential Attention, an adaptive attention-basee feature selection algorithm designed in part for neural networks. Empirically, Sequential Attention improves significantly upon previous methods on widely-used benchmarks. Theoretically, we show that a relaxed variant of Sequential Attention equivalent to Sequential LASSO (Luo Chen, 2014). In turn, we prove novel connection between Sequential LASSO and Orthogonal Matching Pursuit, thus transferring the provable guarantees of OMP Sequential Attention and shedding light on our empirical results. This analysis also provides new insights into the the role of attention for feature selection via adaptivity. overparameterizztion, and connections to marginal gains.
We conclude with a number of open questions that stem from this work. The first question concerns the generalization of our theoretical results for Sequential LASSO to other models. OMP admits provable guarantees for a wide class of generalized linear models (Elenberg et al., 201 8), so is the same true for Sequential LASSO? Our second question concerns the role of softmax in Algorithm I. Our experimental results suggest that using softmax for overparametrization may not be necessary, and that a wide variety of alternative expressions can be used. On the other hand, our provable guarantees only hold for the overparameterization scheme in the regularized linear Sequential Attention algorithm (see Definition 3. Can we obtain a deeper understanding about the pros and cons of the softmax and other overparameterization patterns, both theoretically and empirically?

---

Published as a conference paper at ICLR 2023
BIBLIOGRAPHY
Jason M. Altschuler, Aditya Bhaskara, Gang Fu, Vahab S. Mirrokni, Afshin Rostamizadeh, and Morteza Zadimoghaddam. Greedy column subset selection: New bounds and distributed algorithms. In Proceedings of the 33nd International Conference on Machine Learning, volume 48, pp. 2539- 2548. JMLR, 2016.
Jose M Alvarez and Mathicu Salzmann. Learning the number of neurons in deep networks. Advances in neural information processing systems, 29, 2016.
Sercan Ö Arik and Tomas Pfister. TabNet:
Attentive interpretable tabular learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 6679-6687, 2021.
Muhammed Fatih Balm, Abubakar Abid, and James Zou. Concrete autoencoders: Differentiable feature selection and reconstruction. In International conference machine learning, pp- 444 453. PMLR, 2019.
Yoav Benjamini, Dan Drai, Greg Elmer, Neri Kafkafi, and Ilan Golani. Controlling the false discovery rate in behavior genetics research. Behavioural Brain Research, 125(1-2):279-284, 2001.
Mohamed Bennasar, Yulia Hicks, and Rossitza Setchi. Feature selection using joint mutual informa- tion maximisation. Expert Systems with Applications, 42(22):8520-8532) 2015.
Jeff Bilmes. Submodularity in machine learning and artificial intelligence. arXiv preprint arXiv:2202.001122, 2022.
Vadim Borisov, Johannes Haug, and Gjergji Kasneci. CancelOut: layer for feature selection deep neural networks. In International conference on artificial neurul networks, pp. 72-83. Springer, 2019.
Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge University Press, 2004.
Sébastien Bubeck and Mark Sellke. A universal law of robustness via isoperimetry. Advances in Neural Information Processing Systems, pp.
2021.
Brais Cancela, Verónica Bolón-Canedo, Amparo saliency-based feature selection method with instance-level information. Knowl. Based Syst., 192: 105326, 2020.
and João Gama. A scalable
Emmanuel Candes and Terence Tao. Near-optimal signal recovery from random projections: Universal encoding strategies? IEEE Transactions on Information Theory, 52(12):5406-5444 2006.
Jianbo Chen, Le Song, Martin Wainwright, and Michael Jordan. Learning to explain: An information- theoretic perspective model interpretation. In International Conference Machine Learning, pp. 883-892 PMLR, 2018
Lin Chen, Hossein Esfandiari, Gang Fu, Vahab S. Mirrokni, and Qian Yu. Feature Cross Search via Submodular Optimization. In 29th Annual European Symposium Algorithms (ESA 2021), pp. 31:1-31:16, 2021.
Abhimanyu Das and David Kempe. Submodular meets spectral: Greedy algorithms for subset selection, sparse approximation and dictionary selection. Proceedings of the 28th International Conference on Machine Learning, pp. 1057-1064, 2011.
Sandipan Das, Alireza M Javid, Prakash Borpatra Gohain, Yonina C Eldar, and Saikat Chatterjee. Neural greedy pursuit for feature selection. arXiv preprint arXiv:2207.00 09390, 2022.
Diemert Eustache, Meynet Julien, Pierre Galland, and Damien Lefortier. Attribution modeling increases efficiency of bidding in display advertising. In Proceedings of the AdKDD and TargetAd Workshop, KDD, Halifax, NS, Canada, August, 14, 2017. ACM, 2017.
Chris H. Q. Ding and Hanchuan Peng. Minimum redundancy feature selection from microarray gene expression data. Bioinform. Comput. Biol., 3(2):185-206, 2005.
10

---

Published as a conference paper at ICLR 2023
David L Donoho and Michael Elad. Optimally sparse representation in general (nonorthogonal) dictionaries via & minimization. Proceedings of the National Academy of Sciences, 100(5): 2197-2202, 2003.
Bradley Efron, Trevor Hastie, lain Johnstone, and Robert Tibshirani. Least angle regression. The Annals of Statistics, 32(2):407-499, 2004.
Ethan R Elenberg, Rajiv Khanna, Alexandros G Dimakis, and Sahand Negahban. Restricted strong convexity implies weak submodularity. The Annals of Statistics, 46(6B):3539-3566 2018.
Matthew Fahrbach, Vahab Mirrokni, and Morteza Zadimoghaddam, Non- -on-monotone submodular maximization with nearly optimal adaptivity and query complexity. International Conference on Machine Learning, pp. 1833-1842. PMLR, 2019a.
Matthew Fahrbach, Vahab Mirrokni, and Morteza Zadimoghaddam. Submodular maximization with nearly optimal approximation, adaptivity and query complexity. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 255-273. SIAM, 2019b.
François Fleuret. Fast binary feature selection with conditional mutual information. Journal of Machine learning research, 5(9), 2004.
Ning Gui, Danni Ge, and Ziyin Hu. AFS: An attention-based mechanism for supervised feature selection. Proceedings of the AAAI conference on artificial intelligence, volume 33, pp. 3705- 3713, 2019.
Marwa El Halabi, Suraj Srinivas, and Simon Lacoste-Julien. Data-efficient structured pruning via submodular optimization. arXiv preprint arXiv:2203.04944 2022.
Peter D Hoff. Lasso, fractional norm and structured sparse estimation using a Hadamard product parametrization. Computational Statisties & Data Analysis, 115:186-198, 2017.
Vadim Lebedev and Victor Lempitsky. Fast convnets using group-wise brain damage. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 2554-2566 2016.
Ismael Lemhadri, Feng Ruan, and Rob Tibshirani. Lassonet: Neural networks with feature sparsity. In International Conference on Artificial Intelligence and Statistics, pp. 10-18. PMLR, 2021.
Hao Li, Asim Kadav, Igor Durdanovic, Hanan Samet, and Hans Peter Graf. Pruning filters for efficient convnets. Sth International Conference on Learning Representations (ICLR), 2017a.
Jundong Li, Kewei Cheng, Suhang Wang, Fred Morstatter, Robert P Trevino, Jiliang Tang, and Huan Liu. Feature selection: A data perspective. ACM Computing Surveys (CSUR), 50(6):1-45 2017b.
Yifeng Li, Chih- Yu Chen, and Wyeth W Wasserman. Deep feature selection: Theory and application to identify enhancers and promoters. Journal of Computational Biology, 23(5):322-336, 2016.
Yiwen Liao, Raphaël Latty, and Bin Yang. Feature selection using batch-wise attenuation and feature mask normalization. In 2021 International Joint Conference on Neural Networks (IJCNN), pp. 1-9. IEEE, 2021.
Christos Louizos, Max Welling, and Diederik P. Kingma. Learning sparse neural networks through Lo regularization. In 6th International Conference on Learning Representations (ICLR), 2018.
Yang Lu, Yingying Fan, Jinchi Lv, and William Stafford Noble. DeepPINK: Reproducible feature selection in deep neural networks. Advances Neural Information Processing Systems, 31, 2018
Scott M Lundberg and Su-In Lee. A unified approach to interpreting model predictions. Advances in Neural Information Processing Systems, 30, 2017.
Shan Luo and Zehua Chen. Sequential lasso cum EBIC for feature selection with ultra-high di- mensional feature space. Journal of the American Statistical Association, (292 -1240, 2014.
11

---

Published as a conference paper at ICLR 2023
Yagyensh Chandra Pati, Ramin Rezaifarr and Perinkulam Sambamurthy Krishnaprasad. Orthogonal matching pursuit: Recursive function approximation with applications to wavelet decomposition. In Proceedings of 27th Asilomar conference signals, systems and computers, pp. 40-44. 44. IEEE, 1993.
Eric Price, Sandeep Silwal, and Samson Zhou. Hardness and algorithms for robust and sparse optimization. In International Conference on Machine Learning, pp. 17926-17944. PMLR, 2022.
Debaditya Roy. K Sri Rama Murty, and C Krishna Mohan. Feature selection using deep neural networks. In 2015 International Joint Conference on Neural Networks (ICNN), pp. 1-6. IEEE, 2015.
Simone Scardapane, Danilo Comminiello, Amir Hussain, and Aurelio Uncini. Group sparse regular- ization for deep neural networks. Neurocomputiing 241:81-89, 2017.
Blaz Skrlj, Saso Dzeroski, Nada Lavrac, and Matej Petkovic. Feature importance estimation with self-attention networks. In 24th European Conference on Artificial Intelligence (ECAI), volume 325 of Frontiers in Artificial Intelligence and Applications, pp. 1491-1498. IOS Press, 2020.
Daniel Smilkov, Nikhil Thorat, Been Kim, Fernanda Viégas, and Martin Wattenberg. SmoothGrad: Removing noise by adding noise. arXiv preprint arXiv: (rxXiv:706.03880 007006600....... 2017.
Suraj Srinivas and François Fleuret. Full-gradient representation for neural network visualization. Advances in Neural Information Processing Systems, 32, 2019.
Suraj Srinivas, Akshayvarun Subramanya, and R Venkatesh Babu. Training sparse neural networks. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition workshops, pp. 138-145, 2017.
Mukund Sundararajan, Ankur Taly, and Qiqi Yan. Axiomatic attribution for deep networks. In International Conference on Machine Learning, pp. 3319-3328. PMLR, 2017.
Robert Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society: Series B (Methodological), 58(1):267-288, 1996.
Ryan Tibshirani. Equivalences between sparse models and neural networks. Working Notes. URL https:///www. stat. cmu. edu/" ryantis/ppppers/ppasstttyyn pdf. 2021.
Ryan J. Tibshirani and Jonathan Taylor. The solution path of the generalized lasso. The Annals of Statistics, (115))333-11777 2011.
Andrii Trelin and Ales Procházka. Binary stochastic filtering: Feature selection and beyond. arXiv preprint arXiv:2007.03920, 2020.
Tomas Vaskevicius, Varun Kanade, and Patrick Rebeschini. Implicit regularization for optimal sparse recovery. Advances in Neural Information Processing Systems, 32, 2019.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin, Attention is all you need. Advances in Neural Information Processing Systems, 30, 2017.
Qian Wang, Jiaxing Zhang, Sen Song, and Zheng Zhang. Attentional neural network: Feature selection using cognitive feedback. Advances in Neural Information Processing Systems, 27, 2014.
Wei Wen, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Learning structured sparsity in deep neural networks. Advances in Neural Information Processing Systems, 29, 2016.
Maksymilian Wojtas and Ke Chen. Feature importance ranking for deep learning. Advances in Neural Information Processing Systems, 33:5105-5114, 2020.
Yutaro Yamada, Ofir Lindenbaum, Sahand Negahban, and Yuval Kluger. Feature selection using stochastic gates. In International Conference on Machine Learning, pp. 10648-10659, PMLR, 2020.
12

---

Published as a conference paper at ICLR 2023
Mao Ye and Yan Sun. Variable selection via penalized neural network: A drop-out-one loss approach. In International Conference on Machine Learning, pp. 5620-5629. PMLR, 2018
Xiang Ye, Zihang He, Heng Wang, and Yong Li. Towards understanding the effectiveness of attention mechanism. arXiv preprint arXiv:2106. / 15067, 2021.
Sepehr Abbasi Zadeh, Mehrdad Ghadiri, Vahab Mirrokni, and Morteza Zadimoghaddam, Scalable feature selection via distributed diversity maximization. In Proceedings of the ThirttyFirst AAAI Conference on Artificial Intelligence, pp. 2876-28833 AAAI Press, 2017.
Cun-Hui Zhang and Tong Zhang. A general theory of concave regularization for high- high-dimensional sparse estimation problems. Statist. Sci., 27(4):576-593, 2012.
Lei Zhao, Qinghua Hu, and Wenwu Wang. Heterogeneous feature selection with multi-modal deep neural networks and sparse group lasso. IEEE Transactions on Multimedia, 17(11)199361998, 2015.
Peng Zhao, Yun Yang. and Qiao-Chu He. High-dimensional linear regression via implicit regulariza- tion. Biometrika, 2022.
Qin Zou, Lihao Ni, Tong Zhang, and Qian Wang. Deep learning based feature selection for remote sensing scene classification. IEEE Geosci. Remote, Sens. Lett., (2(11):2321-233 2015.
13

---

Published as a conference paper at ICLR 2023
A MISSING PROOFS FROM SECTION 3
A.1 LAGRANGIAN DUAL OF SEQUENTIAL LASSO
We first show that the Lagrangian dual of (8) is equivalent to the following problem:
1 y ul
min wER"
2
subject to
X u 1l10000 SA
(11)
xJ u 0, VjES
We then use the Pythagorean theorem to replace y by Psy.
First consider the Lagrangian dual problem:
max min uER"
|| - --112 + A11B)sl1 + u (2 X(3).
(12)
BER 3ER
Note that the primal problem is strictly feasible and convex, so strong duality holds (see, e.g., Section 5.2.3 of Boyd & Vandenberghe (2004)). Considering just the terms involving the variable in (12), we have that
1
1
5 || - y12 + uu z
2 | (y - u) z +
2 ||y
2 || (y 1)) + - ||yا|
1
1 lly n 11/:
which is minimized at z = y - 11 as z varies over R". On the other hand, consider just the terms involving the variable (3 (12), that is,
A 1 T X,3.
(13)
Note that if X T u is nonzero on any coordinate in S, then (13) can be made arbitrarily negative by setting Bg to be zero and As appropriately. Similarly, if ||X ulloo > X, then (13) can also be
made to be arbitrarily negative. On the other hand, if (X T u)ss and X uu ull.o S X, then (13) is minimized at O. This gives the dual in Equation (11).
We now show that by the Pythagorean theorem, we can project Pšy in (1I) rather than y. In (11), recall that u is constrained to be in colspan X Then, by the Pythagorean theorem, we have
2 y
2 ly P + P&y - u
2 yy p 112 |
u 2
Psy is orthogonal colspan (X)) and both P and in colspan(X,g (Xs) The first term in the above does not depend on u and thus we may discard it. Our problem therefore reduces projecting y onto Cx O colspan(X, (Xx)+ rather than y.
since -
y y
A.2 PROOF OF LEMMA 3.5
Proof of Lemma 3.5. Our approach is to reduce the projection of Psy onto the polytope defined by Cx n colspan to projection onto affine space.
We first argue that it suffices to project onto the faces of Cx specified by set T. For X > 0, feature indices i [d], and signs +, define the faces
Fx {u R +(,,, u) A}
of C₁. Let A = (1-5) P lc. for = > 0 to be chosen sufficiently small. Then clearly
8 Cs A coolpan(Xss)+
14

---

Published as a conference paper at ICLR 2023
min uc CcCoooooppau {s) Psy u112 |p (
= Pay
In fact, (1 -1-Ee P1-EPP yy lies on the intersection of faces Fx for appropriate choice of signs and i T. Without loss of generality, we assume that these faces are just Fx,,+ for i E T. Note also that for any i & T.
min 1
Psy 11 min
(X,,
Psy -u)
(Cauchy-Schwarc) |X 1)
u.fx.
min
X P Psy - -X.u²
u
(x. Psy - A)²
(u E Fx,1.)
2 (1
P 1100 X sy 12)²
For all Eu, for Eu small enough, this is larger than E² e Thus, for small enough, P Psy is closer to the faces Fx,,, for i 'T' than any other face. Therefore, set Åo (1-Ea) Psyll
Now, by the complementary slackness of the KKT conditions for the projection of P&y onto Cx. for each face of CA we either have that u lies on the face or that the projection does not change if we remove the face. For & T, note that by the above calculation, the projection cannot lie on Fx,, so u is simply the projection onto
C'= X A1r]
By reversing the dual problem reasoning from before, the residual of the projection onto C" must lie on the column span of XT.
A.3 PARAMETERIZATION PATTERNS AND REGULARIZATION
Proof of Lemma 3.2. The optimization problem on the left-hand side of Equation (7) with respect
to 3 is equivalent to
))
3 (w)
inf BERd
X y112+
inf well
||w|22
+
(14)
S:
iES
If we define
(x
inf wERd
Σ
X;
S, (w))
EES
then the LHS of (7) and (14) are equivalent to inf Be (1) X 1- + (880"((80 (Bo,3)). Re-parameterizing
the minimization problem in the definition of (xx(x) (by setting q D(w)). we obtain Q Q- I
B ADDITIONAL EXPERIMENTS
B. VISUALIZATION SELECTED MNIST FEATURES
In Figure 5, we present visualizations of the features (i.e., pixels) selected by Sequential Attention and the baseline algorithms. This provides some intuition on the nature of the features that these algorithms select. Similar visualizations for MNIST can be found in works such as Balm et al. (2019); Gui et al. (2019); Wojtas & Chen (2020); Lemhadri et al. (2021); Liao et al. (2021). Note that these visualizations serve basic sanity check about the kinds of pixels that these algorithms select. For instance, the degree to which the selected pixels are "clustered" can be used to informally assess the redundancy of features selected for image datasets, since neighboring pixels tend to represent
15

---

Published as a conference paper at ICLR 2023
redundant information. It is also useful at time assess which regions of the image selected. For example, the central regions of the MNIST images are more informative than the edges.
Sequential Attention selects highly diverse set of pixels due to its adaptivity. Sequential LASSO also selects a very similar set of pixels, as suggested by our theoretical analysis in Section 3. Curiously, OMP does not yield competitive of pixels, which demonstrates that OMP does not generalize well from least squares regression and generalized linear models to deep neural networks.
Sequential
L'so-Latty-Ynng
Group
Figure 5: Visualizations of the k = 50 pixels selected by the feature selection algorithms on MNIST.
B.2 ADDITIONAL DETAILS ON SMALL- SCALE EXPERIMENTS
We start by presenting details about each of the datasets used for neural network feature selection in Balı et al. (2019) and Lemhadri et al. (2021) in Table 1.
Table 1: Statistics about benchmark datasets.
Dataset
# Examples
# Features
# Classes
Type
Mice Protein
1,080
77
8
Biology
MNIST
60,000
784
10
Image
MNIST-Fashion
60,000
784
10
Image
ISOLET 7,797
617
26
Speech
COIL-20
1,440
400
20
Image
Activity
5,744
561
6
Sensor
In Figure 3, the error bars computed using the standard deviation over five runs of the algorithm with different random seeds. The values used to generate these plots are provided below in Table 2.
Table 2:
Feature selection results for small-scale datasets (see Figure 3 for key). These values the average prediction accuracies on the test data and their standard deviations.
Dataset
SA
L.Y
GL.
ST.
OMP
CAF
Mice Protein
0.993 1. 0.008
0.981 1 0.005
0.985 1 0.005
0.984 1: 0.008
0.994 1. 0.008
0.956 1. 0.012
MNIST
0.956 1: 0.002
0.944 1 0.001
0.937 1 0.003
0.959 1: 0.001
0.912 1: 0.004
0.909
1: 0.007
MNIST-
0.854 + 0.003
0.843 + 0.005
0.834 + 0.004
0.854 + 0.003
0.829 + 0.008
0.839 + 0.003
ISOLET
0.920 1: 0.006
0.866 1 0.012
0.906 1 0.006
0.920
1: 0.003
0.727 1 0.026
0.893 1 0.011
COIL-20
0.997
0.001
0.994 0.002
0.997 1 0.004
0.988
1 0.005
0.967
1 0.014
0.972
0.007
Activity
0.004
0.897
0.002
0.931
0.003
0.905 0.013
0.921 0.001
B.2.1 MODEL ACCURACIES WITH ALL FEATURES
To adjust for the differences between the values reported in Lemhadri et al. (2021) and ours due (e.g.. due to factors such as the implementation framework), we list accuracies obtained by training the models with all of the available features in Table 3.
B.2.2 GENERALIZING OMP TO NEURAL NETWORKS
As stated in Algorithm 2, it may be difficult to see exactly how OMP generalizes from a linear regression model neural networks. To do this, first observe that OMP naturally generalizes to
16

---

Published as a conference paper at ICLR 2023
Table 3: Model accuracies when trained using all available features.
Dataset
Lemhadri et al. (2021)
This paper
Mice Protein
0.990
0.963
MNIST
0.928
0.953
MNIST-Fashion
0.833
0.869
ISOLET
0,953
0,961
COIL-20
0.996
0,986
Activity
0.853
0.954
generalized linear models (GLMs) via the gradient of the link function, as shown in Elenberg et al. (2018). Then, to extend this to neural networks, we view the neural network as GLM for any fixing of the hidden layer weights, and then we use the gradient this GLM with respect to the inputs as the feature importance scores.
B.2.3 EFFICIENCY EVALUATION
In this subsection, we evaluate the efficiency of the Sequential Attention algorithm against our other baseline algorithms. We do so by fixing the number of epochs and batch size for all of the algorithms, and then evaluating the accuracy as well as the wall clock time of each algorithm. Figures 6 and 7 provide visualization the accuracy and wall clock time of feature selection, while Tables and provide the average and standard deviations. Table provides the epochs and batch size settings that were fixed these experiments.
Protein
MNIST-fashion
1,000
Prediction Accursyy
Prediction Prediction Accurscy
Prediction Accuracy
0.950
0.84
0.925
0.900
0.83
0.94
5A
LLY
GL
SL
OMP CAC
SA
LLY
GL
SL
OMP
CAE
LLY SA
SL OMP CAE Activity
GL
ISOLET
COIL-20
Prediction Accuracy
Presiction Accuracy
Prediction Accuracy
0.95
0.92
0.98
0.90
0.86
0.80
5A
LLY
GL
OMP
CAE
5A
LY
GL
OMP
CAE
SA
GL
OMP CAE
Figure 6: Feature selection accuracy for efficiency evaluation.
MNIST-Fashion
600
Selection Time 63)
Selection Time 13)
Selection Time (s1
300
100
200
2000
100
5A
LIY
S1.
GMP
CAF
5A
LLY
5L
OMP
CAF
5A
LIY
51.
OMP CAE
ISOLET
COIL-20
Activity
Selection Time [3)
600
Selecton Time (s)
300
Selection Time (s)
1000
400
500
200
100
5A
LLY
GL
SL
OMP
CAC
5A
LLY
GL
5L
OMP
CAC
5A
LLY
GL
5L
OMP
CAE
Figure 7: Feature selection wall clock time in seconds for efficiency evaluation.
17

---

Published as a conference paper at ICLR 2023
Table 4: Epochs and batch size used compare the efficiency of feature selection algorithms.
Dataset
Epochs
Batch Size
Mice Protein
2000
256
MNIST
50
256
MNIST-Fashion
250
128
ISOLET
500
256
COIL-20
1000
256
Activity
1000
512
Table 5: Feature selection accuracy for efficiency evaluation. We report the mean accuracy on the test dataset and the the standard deviation across five trials.
Dataset
SA
GL
SL
OMP
CAE
Mice Protein
0.984 = 0.012
0.907
0.042
0.968 + 0.028
0.961 = 0.025
0.556 + 0.032
0.956 = 0.012
MNIST
0,958
0.001
0.932
0.0099
0.930 = 0.001
0.957
0.001
0.912 0.000
0.909 0.007
MNIST-Fashion
0.852
0.001
0.833 = 00.004
0.834 = 0.001
0.852 = 0.003
0.722 0.029
0.839 = 0.003
ISOLET
0.931
0.001
0.853
0.016
0.885 + 0.000
0.921 + 0.002
0.580 0.025
0.893 + 0.011
COIL-20
0.993
0.004
0.976
0.014
0.997 = 0.000
0.993 0.004
0.988
0.002
0.972 = 0.007
Activity
0.002
0.881 0.013
0.002
0.927 0.006
0.909 0.000
0.921 0.001
Table Feature selection wall clock time in seconds for efficiency evaluations. These values are the mean wall clock time on the test dataset and their standard deviation across five trials.
Dataset
SA
LLY
GL
SL
OMP
CAE
Mice Protein
57.5 = 1.5
90.5 = 3.5
49.0 1.0
46.5 1.5
50.5 1.5
375.0 = 16.0
MNIST
54.5 + 2.5
80.0 1..0+55.0 5.0
53.0+
1.0
51.5 2.5
55.5
119.0 1.0
ANIISTFFashion
279.5 = 0.5
2.0
265.0
=.0.0110 1.0
2.6.0
3.5
583.5
ISOLET
61.0=00
0.0
1.0
56.5
62.0
611.5 21.5
COIL-20
52.0 0.0
5.0
4.00
48.5
5.00
304.5 7.5
Activity
123.0 = 1.0
159.5
113.5 0.5
116.0
1.1.5
1260.5 2.5
B.2.4 NOTES ON THE ONE-PASS IMPLEMENTATION
We make several remarks about the one-pass implementation of Sequential Attention. First, as noted in Section I, our practical implementation of Sequential Attention only trains one model instead of & models. We do this by partitioning the training epochs into À parts and selecting part in each phase. This clearly gives more efficient running time than training separate models. Similarly, allow for "warm-up" period prior to the feature selection phase, in which small fraction of the training epochs are allotted to training just the neural network weights. When we do this one-pass implementation, observe that is important reset the attention weights after each of the sequential feature selection phases, but resetting the neural network weights is not crucial for good performance.
Second, we note that when there is a large number of candidate features d, the softmax mask severely scales down the gradient updates to the model weights, which can lead inefficient training. In these cases, it becomes important to prevent this by either using a temperature parameter in the softmax to counteract the small softmax values by adjusting the learning rate to be high enough. Note that these two approaches can be considered to be equivalent.
B.3 LARGE-SCARE EXPERIMENTS
In this section, we provide more details and discussion on our Criteo large dataset results. For this experiment, we use dense neural network with 768, 256, and 128 neurons in each of the three hidden layers with ReLU activations. In Figure 4, the error bars are generated as the standard deviation over running the algorithm three times with different random seeds, and the shadowed regions linearly interpolate between these error bars. The values used to generate the plot are provided in Table 7 and Table 8.
18

---

Published as a conference paper at ICLR 2023
We first note that this dataset is large that it is expensive make multiple passes through the dataset. Therefore. we modify the algorithms (both Sequential Attention and the other baselines) to make only one pass through the data by using disjoint fractions of the data for different "steps" of the algorithm. Hence, we select & features while only "training" one model.
Table 7: AUC of Criteo large experiments. SA is Sequential Attention, GL is generalized LASSO, and SL is Sequential LASSO. The values in the header for the LASSO methods are the & regularization strengths used for each method.
CMIM
GL 10-1)
GL
10
SL 10
SL 10
Lia al. 12021)
0.612322
0.00076
0.005855
0.50161
0.07710
000873
0.05300
10
0.70167
000000
0,69402
0.00052
0.719:2
0.00059
0.64282
0.00187
0.62263
1 0.09087
0.70964
0.00385
0.68103 0.00337
15
0.72669 = 0.0009
0.720114
# 0.00067
0.722992
= 0.00027
0.G3977
0.00022
0.82200 # 0.02319
0.72264 0.0213
0.637662 # 0.00G54
20
0.72997
0.00000
0.72231 4: 0.00103
0.72624 = 0.0033n
0.72085
2 0.00005
0.20232
4: 0.01985
0.72808
0.0307
0.71396 4: 0.00467
25
0.73281
0.00000
0.72339 + 0.00342
0.79072
0.00193
0.73263
0.0000
0.71761
+ 0.00987
0.73084
0.00070
0.72067 + 0.03144
0.73420 0.0004
0.72222
00.00149
0.73425
0.00081
0.73200
0.000225
0.00663
0.72988
0.00424
0.00223
0.73226
0.000424
0.73058 0.00350
0.73512
0.0005
0.00509
0.73361
0.00037
0.73078
0.00002
Table 8: Log-loss of Criteo experiments. SA is Sequential Attention, GL is generalized LASSO, and SL. is Sequential LASSO. The values in the header for the LASSO methods are the & regularization strengths used for each method.
GL 10-1
(A 10-11
10-1
(A 10
Lise (2021)
0.13125
0,00005
0.1452
0.00000
0.12033
0.00038
0114519
0.00000
0.14575
1 0.00163
0.13075 000061
0.14115 00001
10
0.19883 = 0.0000
0.132465
+: 0.0000S
0.13747 = 0.00015
0.143319
0.00019
0.14263
+ 0.00204
8.19826
0000022
0.14082 =: 0.00011
15
0,16671 00001110000000 0.00007
0,13745
1: 0.9000
0.13693 1 0.00005
0.14227
0.00021
0.14106 1 0.00022
0.13713
0.00021
0.13944 1: 0.00090
19635 00008
0.13726
0.00010
0.13695
0.00057
0,13718
0.00001
0.13891
1 0.001187
0.15672
0.00055
0.13800
0.00048
0.13613 0.00013
0.13718
0000000
0.13658
0.00051
0.13604
0.00005
0.13700
0.0099
0.13628
0.00010
0.13756
0.00043
0.12506-4
0.13685
0..0000
0.13594
0.13751
0.12670
0.00080
0.13685
0.00002
0.13617
0.00306
0.13686
0.00073
0.13680
0.00011
0.13651 0.00096
0.13603
0.00010
1313635
0.00000
B.4 THE ROLE OF ADAPTIVITY
We show in this section the effect of varying adaptivity on the quality of selected features in Sequential Attention. In the following experiments, we select 64 features on six datasets by selecting 2 features at a time over a fixed number of epochs of training. for i {0, 1, 2, 3, 4, 5, 6]. That is, we investigate the following question: for fixed budget of training epochs, what the best way to allocate the training epochs over the rounds of the feature selection process? For most datasets, we find that feature selection quality decreases as we select more features at once. An exception is the mice protein dataset, which exhibits the opposite trend, perhaps indicating that the features in the mice protein dataset are less redundant than in other datasets. Our results are summarized in Table 8 and Table 9. We also illustrate the effect of adaptivity for Sequential Attention on MNIST in Figure 9. One observes that the selected pixels "clump together" as i increases, indicating a greater degree of redundancy.
Our empirical results in this section suggest that adaptivity greatly enhances the quality of features selected by Sequential Attention, and in feature selection algorithms more broadly.
Peddtton Acaracy
0.955
Mice Protain
Poedenter Arouee
p.96
MNIST
Pedeciion Acaraacy
0.08
MNIST: MNIST-Fashlon
0:95
0.85
0.985
0:93
Log Number of Features Selected amm
Log Number of Features Selected a Time
Log Number of Reatures Selected at Time
ISOLET
COIL-20
Protictin Accurs))
Predetion Accurary
1.00
0.94
0.50
0.98
0.92
0.50
0.90
Log Number of Features Sclected a Tma
Log Number of Features Selected a Time
Log Number of Reatures Selected at Time
Figure& 8: Sequential Attention with varying levels of adaptivity. We select 64 features for each model, and take 2' features in each round for increasing values of i. We plot accuracy as a function of i.
19

---

Published as a conference paper at ICLR 2023
Table 9: Sequential Attention with varying levels of adaptivity. We select 64 features for each model,
and take 2 features in each round for increasing values of i. We give the accuracy as a function of
Dalasel
4
==5
0.900
0.390
0.008
0.369
0.000
01:00
0.005
0.302
0.007
MNIST
0.963
0.001
0.961
0.001
0.956
1 0.001
0.950
0.003
0.940
1 0.007
0.936
1 0.001
0.932 1 0.004
MNIST-Fashion
0.002
0.000
ISOLET
0.934
0.005
0.930
0.003
0.927
1 0.005
0.919
0.004
0.893
1 0.022
0.845
1 0.021
0.752
0.022
COIL-20
Activity
0.938
0.008
0.931 = 0.007
0.928 : 0.010
0.930
0.008
0.915 = 0.001
0.898
0.010
0.913 2 0.010
i= O
i=1
i=
1=3
i= 4
i=5
i= 6
Figure 9: Sequential Attention with varying levels of adaptivity on the MNIST dataset. We select 64 features for each model, and select 2 features in each round for increasing values of i.
B.5 VARIATIONS ON HADAMARD PRODUCT PARAMETERIZATION
We provide evaluations for different variations of the Hadamard product parameterization pattern as described in Section 4.2. In Table 10, provide the numerical values of the accuracies achieved.
Table 10: Accuracies of Sequential Attention for different Hadamard product parameterizations.
Dataset
Softmax
f
82
& normalized
f2 normalized
Mice Protein
0.990 0.006
0.993
0.010
0.993 + 0.010
0.994 + 0.006
0.988 0.008
MNIST
0.958 + 0.002
0.957 + 0.001
0.958 + 0.002
0.958 + 0.001
0.957 0.001
MNIST-Fushion
0.850 + 0.002
0.843 0.004
0.850 0.003
0.853 + 0.001
0.852 + 0.002
ISOLET
0.920 0.003
1894+0.00
0.908 0.009
0.921 + 0.003
0.921 0.003
COIL-20
0.997 + 0.004
0.997
0.004
0.995 + 0.006
0.996 + 0.005
0.996
0.004
Activity
0.922 + 0.005
0.906 + 0.015
0.908 + 0.012
0.933 + 0.010
0.935 + 0.007
Mice Protein
MNIST
NNIST-Fashion
0.855
Prdiction Acorncy
Prediction Accunccy
0.960
Pedictue Acorag
0.945
0.840
ISOLET
COIL-20
Activity
1.002
Predicien Aucareay
0.42
0.91
1.000
Tndirtiem Armureyy
0.93
0.50
0.996
0.92
0.994
0.91
0.88
0.50
0.87
LIN
LIN
L.N
12N
L2N
Figure 10: Accuracies of Sequential Attention for different Hadamard product parameterization patterns. Here, SM = softmax, LI E1, L2 fz, LIN l normalized, and L2N lg normalized.
20

---

Published as a conference paper at ICLR 2023
B.6 APPROXIMATION OF MARGINAL GAINS
Finally, we present our experimental results that show the correlations between weights computed by Sequential Attention and traditional feature selection marginal gains.
Definition B.1 (Marginal gains), Let é :244 - R be loss function defined on the ground set [d].
Then, for a set S C [n] and i & S, the marginal gain of with respect to S is E(S) E(S u {i)).
In the setting of feature selection, marginal gains are often considered for measuring the importance of candidate features i given a set S of features that have already be selected by using the set function f, which corresponds to the model loss when trained selecting features based on their marginal gains performs well in both theory (Das & Kempe, 2011; I; Elenberg al., 2018) and practice (Das et al., 2022). These scores, however, can be extremely expensive to compute since they require training model for every feature considered.
subset of features. It is known that greedily
In this experiment, we first compute the top k features selected by Sequential Attention for k E {0. 9. }9} on the MNIST dataset. Then we compute (1) the true marginal gains and (2) the attention weights according Sequential Attention, conditioned on these features being in the model. The Sequential Attention weights are computed by only applying the attention softmax mask over the d-k k unselected features, while the marginal gains are computed by explicitly training model for each candidate feature to be added to the preselected & features. Because Sequential Attention algorithm is motivated by an efficient implementation of the greedy selection algorithm that uses marginal gains (see Section 1), one might expect that these two sets of scores are correlated in some sense. We show this by plotting the top scores according to the two sets of scores and by computing the Spearman correlation coefficient between the marginal gains and attention logits.
In the first and second rows of Figure 11, we see that the top 50 pixels according to the marginal gains and attention weights visually similar, avoiding previously selected regions and finding new areas which are now important. In the third row, we quantify their similarity via the Spearman correlation between these feature rankings. While the correlations degrade we select more features (which is to be expected), the marginal gains become similar among the remaining features after removing the most important features.
Top 50 Marginal Gain Pixels, Selected
Top 50 Marginal Gain Pixels, Selecctd
Top 50 Marginal Gain Pixels, 49 Selected
5-
10-
30-
10
15-
15-
15
20
20
20
25
25-
25
Top 50
Attention Logit Pixels, 0 Selected
Top 50 Attention Logit Pixels, 9 Selected
Top 50 Attention n Logit Fixels, 49 Selected
10
10-
10
35
15
15
20
20
20
25
25
25
800
Sp Spoarman: 0.8268
Spcarthah 2.2877
Weights
600
600
Actantionn weights
8000
400
400
200
Spectmmnn
200
400
600
800
200
400
500
800
200
400
600
Marginal Gains
Manginal Gains
Margiaal Gaiins
Figure 11: Marginal gain experiments. The first and second rows show that top 50 features chosen using the true marginal gains (top) and Sequential Attention (middle). The bottom row shows the Spearman correlation between these two computed sets of scores.
21


Reviews:
[{"review_id": "ppFLJoS_SyN", "reviewer": "Reviewer_tvep", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper proposes a method to perform feature selection by learning to weigh the input features with probabilities given by a softmax transformation. Given the similarity to attention methods, the method is called Sequential Attention. It consists of running the model with the reminiscent non-selected features and then greedly selecting the features associated with the highest softmax weight. The authors provide a large body of theoretical guarantees, linking an adapted (regularized) version of Sequential Attention to the classical Sequential LASSO algorithm. Results on 7 datasets showcase the predictive performance of the proposed approach.", "summary_of_the_review": "Overall this paper provides a great theoretical contribution to attention-based feature selection. It also presents solid empirical results on several datasets, outperforming related approaches. However, I believe it has room for improvement, especially regarding the clarity of the experimental setup.", "strength_and_weaknesses": "Things that I liked in this paper:\n- The paper has a strong math foundation and excels at theoretical contributions. \n- The proposed method outperforms related approaches despite being very simple.\n- On top of this, this paper shows empirically and theoretically that \"attention\" is, in fact, a suitable approach to selecting a good subset of features.\n\nHowever, I think the paper can be improved, especially regarding clarity. The paper focuses significantly on the theoretical aspect, while the experimental section is very short, with several important experiments left in the appendix. For example, it was not until section 4.2 that I realized that the previous results were achieved using the standard Sequential Attention shown in Algorithm 1. Finally, I believe that Algorithm 1, in its current form, is very inefficient since it requires training at least $k$ models. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "bFNa1wJ73Lz", "reviewer": "Reviewer_ABqs", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper is proposing a forward feature selection algorithm with the use of attention mechanism for assessing the feature relevance of currently not selected features. Since attention mechanism consider all unselected features at once, there is computational saving, compared to the common greedy forward selection algorithm. A specific instance of the Sequential attention feature selection framework, was shown to be equivalent to Orthogonal Matching Pursuit, thus inheriting theoretical guarantees on the quality of approximation. ", "summary_of_the_review": "Based on the perceived novelty and theoretical results, this paper seems like it could be accepted.", "strength_and_weaknesses": "Strengths\nWhile equivalence of Sequential LASSO and OMP was shown under several assumptions before, this work shows the equivalence holds for more general settings. \nClever use of attention to achieve computational savings by evaluating unselected features all at once, at every step (until the prespecified number of features are selected).\n\nWeaknesses\nEmpirical evaluation is not as extensive, however it is performed against relevant feature selection like competitor attention-based feature selection, as well as sequential LASSO and OMP (with neural networks).\nIt is encouraging that the regularized linear Sequential attention version had indistinguishable performance from the softmax based Sequential attention one, on benchmark data, but it is still not “bridging the gap”, but just leaves a chance that it might enjoy theoretical guarantees too. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "ZWUQQjSB-HQ", "reviewer": "Reviewer_vzVg", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "The authors propose a sequential algorithm for feature selection, where a feature is selected in each step. The intuition behind the idea is to minimize the selection of redundant features. A theoretical study is also presented, matching the proposed algorithm with other state-of-the-art methods like OMP or Sequential LASSO. The experimental results show promising accuracy scores when compared against other incremental Feature Selection methods.", "summary_of_the_review": "Overall, I think it is an interesting solution, but more work has to be done before publishing it. More comparisons against other FS algorithms have to be performed. Besides that, I think the novel contribution of this algorithm is questionable, as the solution is extremely similar to the mentioned OMP and sequential LASSO.\n\n", "strength_and_weaknesses": "Strengths:\n* The idea is easy to implement\n* The theoretical explanation is interesting\n* The spatial complexity of the algorithm is low\n\nWeaknesses:\n* The idea is somehow trivial\n* The algorithm time complexity is extremely high\n* The experimental results only cover other incremental Feature Selection methods.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "OZggcxrQt0", "reviewer": "Reviewer_FwQ2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "This work introduces the Sequential Attention algorithm for supervised feature selection. This algorithm is based on an efficient implementation of greedy forward selection and uses attention weights at each step as a proxy for marginal feature importance. \nThe authors provide theoretical insights into the Sequential Attention algorithm for linear regression models by showing that its regularized linear Sequential Attention model is equivalent to sequential LASSO and Orthogonal Matching Pursuit, and thus inherits all of their provable guarantees. Their theoretical and empirical analyses provide new explanations towards the effectiveness of attention and its connections to overparameterization.", "summary_of_the_review": "The novelty mainly lies in theoretical analysis. The theoretical and experiments both suggest the proposed approach is similar to the existing approach and the benefits are not clear.", "strength_and_weaknesses": "Strength\n- The paper is well written and organized.\n- The paper proposes efficient sequential feature selection methods with attention, which reduces the complexity of greedy forward based feature selection.\n- The authors provide provable guarantees for Sequential Attention for least squares linear regression by analyzing its variation called regularized linear Sequential Attention. They show the connection between Sequential LASSO and Orthogonal Matching Pursuit. \n\nWeakness\n- The authors claimed a lot of merits for the proposed algorithms, such as “this technique reduces the overhead of our algorithm, removes the need to tune unnecessary hyperparameters, works directly with any model architecture,…achieves state-of-the-art feature selection results for neural networks on standard benchmarks”. However, the experiments seem not quite complete to support the claim. For example, there is no experiment demonstrating the approach works on all model architectures.\n- The advantages over existing methods are not clear or significant. The results in Figure 3 on DNNs seems to suggest there is limited advantage over SL, GL or OMP for these datasets. \n- The scale of the experiment on DNN is quite small and limited. The experiments on neural networks are done with only a one-layer neural network with hidden width 67 and ReLU activation.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster