Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a greedy-based approach for online feature selection.  This paper defines greedy online feature selection and also provides an iterative procedure to implement the greedy approach with a deep learning approach. 

strength_and_weaknesses: Strengths:
+ The problem is interesting and meaningful. Feature selection, especially online feature selection, could be used in various application scenarios in practice. 
+ The empirical evaluation is comprehensive and overall convincing. The paper conduct extensive experiments on several datasets including tabular datasets and image classification datasets, and the proposed method outperforms both RL-based and offline feature selection methods. The authors will release the source code as mentioned in Section 6. 

Weaknesses:
- The novelty is limited. Though the framework is novel, the individual models are not. 
- The diagram in Figure 1 is interesting. However, the key point of the proposed method is not reflected in Figure 1.  More information could be added to the diagram. 
- Some typos should be modified. For example, in Subsection 2.1, “X_{\hat{s}} is the set complement X_{[d]\s}” -> “X_{\hat{s}} is the set complement to X_{s}”. 
- Some details could be improved. For example, the “eq.”  could be changed to “Equation”  in order to be consistent with the description “Figure”, “Table”, etc. 
clarity,_quality,_novelty_and_reproducibility: The organization is good and the logic is clear. There should not be many issues with reproducibility.
summary_of_the_review: The paper proposes a new greedy-based method to address online feature selection. The technical novelty in the individual parts is limited.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper introduces a new greedy method for the online feature selection problem. The method is locally optimal in selecting features that maximize the conditional mutual information with the response variable. The authors propose a deep learning-based approach to learning a selection policy network, which is trained by amortized optimization. The new method is of low complexity compared to other RL-based methods and has good performance compared to online and offline methods on tabular and image data.
strength_and_weaknesses: Strengths:
- The method is novel based on its description. The solution is interesting.
- The writing is of high quality 
- Experiments well demonstrated the proposed method.

Weaknesses:
- One weakness is the clarity of the notations. Although the author defined the notations at the beginning of section 2. I found I still got lost while reading the paper, especially when trying to distinguish between an index set and a single index. This could be due to the redefinition of the bold type and the normal type.
- About the clarity of the problem definition: I’m not familiar with this task, but when people refer to “online,” they usually will indicate the data distribution changes or is stationary. I guess here the problem assumes a stationary distribution, and “online” indicates the sequential nature of the selection, right? If so, there is no adaptive part of the problem, and the method sounds like a sequential version of the offline counterpart.
- For the theoretical results, I feel Eq. 8 and thm 1,2 may require more explanations or assumptions. (But these impressions could also be due to my misunderstanding.) I had the following questions while I was reading the paper
  1. Does p(s) depend on $\phi$ or $\theta$? 
  2. In the proof of Thm 1, what are the mild conditions mentioned in the main paper? I didn’t follow how Eq. 8 simplifies to Proposition 1.
- It seems the practical objective function of the experiments has a gap with Eq. 8. I.e., I didn’t see how to sample from $p(s)$ from Alg. 1. It would be great to state the objective function in experiments (with monte carlo estimates of the expectations).
- Should Eq. 7 have a reverse inequality sign because $v$ is the expected loss? This is the same for the gap definition below.
- I felt some parts of section 3 (mainly sec. 3.2) are pretty technical but didn’t help me understand the main method in section 4. Perhaps leaving more space in section 4 to explain the training procedure is more rewarding to the audience. (Maybe it’s only a personal taste.)

clarity,_quality,_novelty_and_reproducibility: The majority of the paper is well-written, and I like the idea of the proposed method. However, I didn’t clearly see where this method is “adaptive” from its theory and experiments, alleged in the abstract. I still need more details to understand part of the equations and proof (which could be due to my misunderstanding). The notations can be improved especially in distinguishing between sets and scalars.
summary_of_the_review: This work presents a smart way to make online feature selection, which is novel given the literature. The paper is also well-written, and the experiments demonstrated the method well. But as I mentioned above, I’m still curious about the adaptive part of the problem definition. The main results may require more explanations or assumptions.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper proposes a greedy strategy to feature selection based on information maximization criterion.
strength_and_weaknesses: Strengths:
--- Clear and easy to read
--- Empirical evaluations are interesting and useful. 


Weaknesses:
--- The paper lacks solid theoretical justification. They cite Das/Kempe 2011 who analyze linear regression functions, but miss citing some other relevant literature that very likely covers their cost functions. 

General cost functions: 
Restricted strong convexity implies weak submodularity. Elenberg et al. Annals of Stats

Streaming feature selection: 
Streaming Weak Submodularity: Interpreting Neural Networks on the Fly. Elenberg et al. Neurips 2017
Online Streaming Feature Selection. Wu et al. ICML 2010

--- While the authors have tried to cite many relevant works, the citations on feature selection are still limited. For example, gradient 
based feature selection is also covered in Elenberg et al works above and other works such as: 
Fast Feature Selection with Fairness Constraints. Quinzan et al. 

--- I am not sure why modeling p(x_i | x_s) as explained in Sec 3.2 is even important. Sec 4 onwards the authors explain ways to circumvent it. But many other methods (some of which are listed above) only care about the correlation with y when selecting features (along with iterative strategies that ensure the selected features are uncorrelated amongst themselves). This also obviates the development in Sec 4. 



--- Other than the above point, I am not sure why E_s in the cost function is a good idea, especially in a greedy strategy. Why would one want to take an expectation over ALL subsets of size s when we care only about a particular set as formed by the greedy strategy? Is that not a gross overkill ? It seems it is done for a theoretical justification, but again, it seems unfounded and not really required given theoretical justification based on weak submodularity. 

--- The section on greedy suboptimality is interesting, but I think it is also superseded by the weak submodularity papers.



clarity,_quality,_novelty_and_reproducibility: The paper is clearly written. 

Greedy strategy is very often used in practice. So the suggestion to use it to maximize the info gain is not really novel. Plus i have concerns in the foundational aspects that the authors use to motivate their method as listed in the weakness section. 

No concerns about reproducibility

The empirical results are promising, and add to the quality of the paper. However I would argue overall the quality is below this conference's standards.
summary_of_the_review: I think there are concerns about theoretical justifications and the authors missing relevant works when motivating their method. The empirical results are interesting, but not surprising given the generally strong performance of the greedy method. The paper is not ready to be published at a conference like this one.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This work studies an RL-based greedy feature selection algorithm that uses
conditional mutual information with the label as the scoring criteria. The
authors propose using a differentiable method in each greedy step by combining
the true model and the "concrete distribution" (for feature masking) to learn
the best policy given the current set of features, i.e., to identify the next
best feature. They provide some theoretical justification for their approach,
and give a diverse set of feature selection experiments that suggest their
method is both effective and practical.
strength_and_weaknesses: **Strengths:**
- Example 3 is a nice instance that shows the difficulty of feature
  selection, especially when using pairwise feature information.
- The experiments look *very strong*. Other methods seem somewhat noisy and
  "less monotonic". How many trials were used for the different methods -- both
  feature selection and model trainings?

**Weaknesses:**
- The paper bounces back and forth between "combinatorial" and RL-based feature
  selection.  It would be beneficial to present the main algorithm as directly
  as possible (possibly by just explaining all the details of Figure 1): how
  exactly do you use RL, what is the differentiable masking expression, is the
  criteria ultimately that of the downstream model, etc. There are many more
  details and asides that take away from the empirical results.
- Is Theorem 1 actually true? In the hidden XOR case if $y = x_1 \otimes x_2
  \otimes x_3$ and $d = 10$, then in the second step of feature selection, all
  candidates are equally good (i.e., we don't need to put all the mass on one
  feature). Maybe say "a global optimum" in the event of ties.
- This work isn't really about "online feature selection" -- it's just adaptive
  and "normal" supervised feature selection.
- In Section 6.1, you have "In each of these problems, gathering all possible
  inputs is impractical due to time and resource constraints, thus making
  online feature selection a natural solution." How do you learn the RL policy
  then? It seems that you need all of the features since you learn a mask on the
  unselected features via RL and the downstream model.
- Table 1: Why is the mean loss for different feature set sizes a meaningful
  quantity? It carries some signal, but these values are better understood when
  plotted as a Pareto curve as in Figure 2.
- It would be valuable to compare your RL-based greedy algorithm to the true
  greedy algorithm that compute the conditional mutual information in each step
  (relative to set $s$). Of course, this can be too expensive to compute in
  practice, but it would be valuable to know ``what is achievable'' as an upper
  bound and how close your algorithm comes to that.

**Suggestions:**
- [page 2] Suggestion: The conventional notation is to use $S \subseteq [d]$ for
  a subset of features (i.e., capital $S$).
- [page 4] It would be worthwhile to discuss how $I_i^n$ in Equation (5) is
  related to the empirical conditional mutual information on the training data.
- [page 7] Suggestion: The related works section would go better at the end of
  the introduction. 
- [page 7] In the related works when discussing "iterative feature scoring
  methods", it would be good to cite the landmark paper "Fast binary feature
  selection with conditional mutual information" (Fleuret JMLLR, 2004) for the
  CMIM algorithm, since this is a strictly combinatorial version of the (binary)
  cross entropy algorithm you propose.
- [page 7] How do you differentiate online feature selection vs "offline
  feature selection". As far as I can tell, these problems are equivalent and
  best described as "feature selection" or "supervised feature selection".
- [page 8] Suggestion: Include the standard deviation of each value in Table 1.
clarity,_quality,_novelty_and_reproducibility: The paper is written somewhat clearly -- the algorithm used in the experiments
is somewhat hard to parse given the semi-related theorems in Section 3 and the
relaxation in Section 4.2 that alters the "ideal" greedy step in Equation (8).
The main ideas could be delivered more directly.
The novelty of this work seems limited since conditional mutual information is
known to work well for feature selection. The main contribution of this work is
using RL and differentiable masking to find the unselected feature in a greedy
manner. The experiments appear to be reproducible (I checked the supplementary
material).
summary_of_the_review: This paper is on to something, especially if the experiments are dominant
across many averaged trials and model trainings. That said, I think the paper's
message could be greatly simplified by very directly presenting the algorithm
and not justifying all of the decisions with lemmas about mutual information,
since most these ideas are reasonably well-known. I recommend the paper be
rejected from ICLR 2023, but encourage the authors to refine the work and
resubmit to a comparable venue in the future.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: In this paper, the author(s) considered the problem of online feature selection which was different from the standard feature selection with fixed feature subsets (i.e., offline feature selection). The author(s) proposed a deep learning-based algorithm to process the greedy information maximization for online feature selection. Then, the author(s) demonstrated that empirical experiments showed the advantage of the proposed algorithm.

---

strength_and_weaknesses: ### Strength:

Feature selection is a significant branch of machine learning, and most of the existing feature selection studies mainly focus on offline feature selection. In practice, online feature selection is more challenging and more important.

---

### Weaknesses:

1. The novelty of this proposed algorithm is limited.

2. The review and comparison with online/offline feature selection are insufficient.

3. There are potential issues in the calculation of experimental results (especially the lack of stability analysis for selected features, which is necessary for deep model-based feature selection).

4. Some descriptions in this paper are not clear.

For more details, please see the section of "Clarity, Quality, Novelty And Reproducibility"

---



clarity,_quality,_novelty_and_reproducibility: After initially reading the title and abstract of this paper, I thought this paper presented an interesting method for online feature selection. However, after reading the main text, I felt a little disappointed.

I have the following comments/questions. I look forward to the response/clarification from the author(s). Thanks.

---

### Clarity:

1. Some of the descriptions in this paper are not so clear. Especially the description of mathematical notations, many places in the paper are not clearly explained at the beginning. To understand the meaning of mathematical notions, one must read the following content first. I don't think this is the way a normal/good paper should be presented. For example, on Page 2, Section 2.1, Line 2 in the 1st Paragraph, maybe it needs to explain "$\mathcal{X}_i$"; on Page 2, Section 2.1, Line 2 in 2nd Paragraph, maybe it needs to explain "$\pi(\cdot)$"; The last sentence in 1st Paragraph of Section 2.2, for $k$, it is better to explain the relationship between $k$ and $d$; and so on.

2. For the statement below Eq. (1), "...goal in designing a policy is to minimize... or to maximize our final predictive accuracy". Are these two descriptions equivalent in terms of classification?

3. On Page 1, the 1st Paragraph of Section 1, the last sentence, "...We refer to this problem as online feature selection, and it has been considered by several works in the last decade...". A quick Google search can find that the review of the current online feature selection methods is insufficient. There are many new developments in online feature selection (including 2021 and 2022). Some works are even more advanced than the work in this paper, such as dealing with online feature selection for multiple sources. In addition, the review of the offline feature selection methods is also insufficient.

4. When comparing offline feature selection methods, why use "a supervised version of CAE" (which is itself unsupervised learning) for comparing offline feature selection methods instead of the STG method (which is itself supervised learning)?

5. I do not quite agree with the processing of calculation results in this paper. For example, in Table 1, "the mean AUROC across k = 1... 10 features", in fact, for feature selection based on deep neural networks, the stability of selected features is one of the major potential issues (In Figure 5 of the STG paper [1], the authors specially analyzed the stability of selected features). So, the author(s) should present (multiple) cross-validation results with a fixed $k$ value (mean +/-standard error). Also, the curves in Figures 2 and 3 should be the result of multiple cross-validations with a fixed $k$ value (mean +/-stance error). In this way, it can reflect the stability of the selected features.

---

### Novelty

I think the novelty of this proposed algorithm in this paper is quite limited. 

(1) Although the topic of this paper is online feature selection, the main idea of this paper, in my opinion, it only replaces the feature selection layer in STG [1] with the feature selection layer in concrete auto-encoders (CAEs) [2]. 

(2) When CAEs appeared, the concrete distribution was combined with feature selection for the first time, which was novel and eye-catching. But since then, several studies have used this method for feature selection. So, now it is better to simplify Section 4.2 "CONTINUOUS RELAXATION" and move the superfluous/cumbersome content to the Supplementary Materials.

In addition, some other tiny issues/typos

(1) In general, the first time an abbreviation appears, it needs to go with the full name. So, please give the full name of "RL" in the Abstract.

(2) The format of the references is quite inconsistent. Please check carefully and correct it.

---

[1] Yamada Y, Lindenbaum O, Negahban S, Kluger Y. Feature selection using stochastic gates. In International Conference on Machine Learning 2020 Nov 21 (pp. 10648-10659). PMLR.

[2] Balın MF, Abid A, Zou J. Concrete autoencoders: Differentiable feature selection and reconstruction. In International conference on machine learning 2019 May 24 (pp. 444-453). PMLR.

---




summary_of_the_review: The work in this paper is interesting; However, there are many unclear aspects in the description (including experiments) of this paper, and the innovation also needs to be further discussed. In addition, the work largely ignores existing works.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper focus on the online feature selection problem which mainly viewed as a reinforcement learning problem by traditional methods. Authors introduced a greedy approach to online feature selection that selects features according to their conditional mutual information with the response variable and then proposed a deep learning approach to learn the greedy policy.  Experiments on numerous datasets show that the proposed method outperforms a variety of existing feature selection methods.
strength_and_weaknesses: Strength:
1. Starting from the greedy algorithm, the author continuously analyzed the algorithm from the theoretical and strategic levels, so as to get their proposed algorithm, which I think is very reasonable.
2. The effectiveness of the proposed method was demonstrated on various datasets. The authors also provide their codes of experiments.
Weaknesses:
1. I think the explanation of eq.(8) is far from sufficient. It's better to restate how far it differs from eq.(1) and how do you derive this formula from the greedy algorithm in more detail.
2. In section 3, authors say that 'The third example illustrates the perils of following a greedy approach: it fails to account for each
selection’s impact later in the selection procedure. In contrast, a non-greedy policy can make suboptimal selections that yield large improvements in later steps.' Does that show up in the experimental section? If not, can you design it?
3. In Figure 3, a visualization of the selected features is given, which I think is very good. But I think it would be better if there was a reasonable explanation for the chosen features.






 
clarity,_quality,_novelty_and_reproducibility: In general, the paper has a complete structure, clear thinking and some innovation.


summary_of_the_review: Overall, the article has a complete structure and clear thinking. But the content needs to be further improved, if authors can solve my problems, I think this paper is a very good article.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: Summary
---
The paper presents a method for online feature selection, which is different from the standard feature selection problem where the feature subset is fixed. The proposed method is a greedy strategy that selects features based on their conditional mutual information with the response variable, and uses a deep learning approach to learn the greedy policy. The authors demonstrate through empirical experiments that the proposed method performs well compared to other existing feature selection methods.

Strengths
---
- The proposed method addresses an important and practical problem, namely online feature selection, which has numerous potential applications. The solution is interesting. The writing is clear and easy to read.
- The empirical evaluation is comprehensive, with experiments conducted on multiple datasets and comparisons made against multiple existing methods. The authors also provide their codes for the experiments.

Weaknesses
---
- The paper lacks strong theoretical justification and does not adequately cite relevant literature, including works on gradient-based feature selection and weak submodularity. The section on greedy suboptimality may also be superseded by weak submodularity papers. The authors’ response argued that submodularity doesn’t apply because feasible solutions are represented by policies rather than subsets. However, submodularity is widely used in designing feature selection algorithms and establishing their theoretical guarantees. Even if submodularity may belong to a different family of approaches, since it is one of the most important methods in feature selection, it is reasonable to include discussions and comparisons to submodularity, especially in experiments. 
- There are questions about the clarity and validity of the main algorithm and Theorem 1.
- The authors' approach of modeling p(x_i | x_s) is not well-justified and is later bypassed.
- The use of E_s in the cost function as part of the greedy strategy is questionable. The authors’ response did not address this concern adequately. 



justification_for_why_not_higher_score: I would recommend rejection for this paper based on the following reasons:

- The paper lacks strong theoretical justification and does not adequately cite and compare relevant literature, including works on gradient-based feature selection and weak submodularity. Since submodularity is one of the most important methods in feature selection, it is reasonable to include discussions and comparisons to submodularity, especially in experiments. 
- There are questions about the clarity and validity of the main algorithm and Theorem 1 which were not addressed adequately in the authors' response.
Decision: Reject