Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper proposes an unsupervised feature selection method. The paper provides theoretical analysis of selection performance when the underlying dataset is perturbed. It provides experimental results on multiple datasets, comparing the performance of the proposed approach with that of the methods in the literature.
main_review: -Originality: The paper seems novel.
-Quality: Quality could be significantly improved. (see below)
-Clarity: Clarity is significantly below the acceptable level. (see below)
-Significance: Low (see below)

I think the paper has two significant flaws:

1) 
- Experiments appear highly biased against deep feature selection methods: reconstruction and classification experiments use linear approaches whereas those methods, such as AEFS, operate under the assumption that deep feature selection is allowed. Indeed, for instance on the ISOLET dataset, Ref. 14 reports a classification accuracy of 89.2% (Table 2). The corresponding linear performance reported in this manuscript (Table 3) is only 57.6%. Similarly, while f and g can be nonlinear in Eq. 2, they are *tailored* for the linear performance metrics by virtue of restricting them to the linear case.
- Related to this point, how do the authors explain the huge performance jump for AEFS between tasks 1-5 and tasks 6-10?
- Related to this point, it is concerning that the proposed method performs much better in tasks 1-5 compared to tasks 6-10 in terms of the recon. error. (Table 2) The manuscript mentions that comparison results for tasks 1-5 were imported from the CAE paper.

2) Theoretical development is not careful enough, making it very hard to follow the paper.

a. Notation is inconsistent and cumbersome. I point out a few examples here:
- line 116: The definition of S^i is not clear because the inputs are S, i, and the new value x_i’.
- line 112: The definition of \Delta^t requires 3 arguments; f, x, x’ because the right hand side evaluates f at x+t\Delta x.
- line 172: L^{\text selec} is not defined.
- line 119: \ell is defined on \cal{X}x\cal{X}. But, A_S is a function.
- x’ denotes a (different) sample whereas X’ denotes matrix transposition. Would the authors consider a different notation for either one?

b. I have similar concerns about the theoretical results. I point out a few examples here:
- (Lemma C) \ell^{score} and \ell_{selec} have two arguments. Def. D considers functions of a single argument.
- (Lemma C) Def. D requires the inequality to hold for any arguments in its domain, but Lemma C specifies these arguments.
- (Lemma D) How Prop. 1 is used in Lemma D is not clear at all.
- (Lemma E) In the proof, please add more details showing the second equality involving limits.

c. Small lambda_1 corresponds to little regularization, so it makes sense that the bound in Eq. 4 is not meaningful. However, when lambda_1 is large, the first term on the right hand side of Eq. 4 will produce a lambda_1-independent term. Is this term small enough to produce a meaningful bound?


**UPDATE:** After a long discussion with the authors, I decided to increase my score from 4 to 5.
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors address the problem of unsupervised feature selection. They combine an autoencoder reconstruction loss with an additional term which only uses the k most informative features to reconstruct the input data. The k most informative features are identified by sorting the absolute values of a diagonal matrix whose weights are multiplied by the input features. The authors prove that the method is algorithmically stable and find its generalization error bound. The method demonstrates superior capabilities compared with several feature selection baselines.
main_review: The problem of unsupervised feature selection is important and has several applications in ML. The method proposed by the authors is simple but seems to work very well on a diverse set of datasets. The theoretical analysis provided by the authors is novel and sheds light on the stability and generalization capabilities of the method. The paper is well written and the presentation is clear. Overall I recommend accepting the paper, however, I have several comments which could improve the clarity of the results. 
-P1L10 show our-> show that our
-P1L32 none -> no
-P2L44 an extra space appears before the word “It”
-Notation: You are using X’ from transpose but then you use x’ again to denote something else. 
P3L131 the sentence is poorly written, do you mean: The goal of feature selection is…?
P7 Design of experiments: the reasoning for initializing the selection layer from the very narrow uniform distribution is not clear. Why not just initialize all of them as 1? 
The selection of \lambda_1 is also not clear, did this value lead to optimal results on one dataset or on the average/median of all of them? 
What is the batch size used?
How are the parameters of Extremely randomized trees tuned?
The relation between the method and Agnos-S (and perhaps other methods) should be clearly explained in a related work section.
 Was the linear regression (used for evaluating the MSE) also trained on the train and evaluated on the test?

limitations_and_societal_impact: The proposed method could help reduce the computational burden of training ML algorithms. The main challenge in the proposed method is to tune the additional hyperparameters, namely k and \lambda_1.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors propose a novel methodology for unsupervised feature selection. Their procedure is based on simultaneously training a feature importance scorer neural network and a feature selector neural network; both are embedded inside an encoder in an autoencoder. The overall network is trained by optimizing a regularized estimator, where the regularization parameter induces some algorithmic stability. The authors provide theoretical guarantees of the estimator in the form of upper-bounds for the algorithmic stability and generalization. Further, they demonstrate the effectiveness of their approach on multiple real datasets and empirically understand various features of their algorithm (e.g. sensitivity to choices of parameters) via demonstrations on synthetic data. 
main_review: Originality: yes, to be the best of my knowledge, the methods seem novel!

Quality: In general, I found the paper interesting to read and the technical/methodological contributions to have some potential with good empirical performance. Below I state some questions/comments/concerns (some of which may be naive)

 --- The regularization term in equation (2) is motivated by the need for algorithmic stability. Looking at Theorem 1, it appears than when lambda is set to 0, the bound is vacuous and hence asymptotically \lambda must be chosen as 1/sublinear(n). This leads me to have the following remarks:

a) is the source of instability the non-continuous max_k operation? this to me seems like the major issue? 

b) related to a, would then a potential alleviation be to consider simply the second term and impose an $\ell_1$ penalty on the elements of \Phi(W_I)? Do you think this would also makes sense as an estimator? What are the advantages of your proposed method of the potentially naive procedure I just outlined? 

c) I appreciate the authors description that the combination of the two terms does something global and local but their framework does deviate from standard inverse problems where there is fidelity to data and a complexity controlling regularization. 

d) I recognize that this is very hard, but is there any sense of the existence of lower bounds for the algorithmic stability? 

e) understanding algorithmic stability as a function of lambda: the authors look at test error as a function of lambda. I am curious to see the same plot for algorithmic stability. I suppose due to the connection between generalization and algorithmic stability, we expect the same behavior

---- As denoted in Figure 1,  the method is perhaps useful for highlighting key attributes of the image in pixel domain. Sometimes the interesting attributes are concepts that are not well characterized purely by just pixels. What do you propose in this setting? Somehow there it makes sense to look at XW where W is reduces to a particular subspace. It would be good for the authors to comment on the utility of their framework in a "discovery" type aspect for imaging data.

---- in addition to k, \lambda_1, the bottleneck dimension d must be chosen. How sensitive is the method to this?

----- How exactly do the two neural networks (scorer and selector interact) other than combining together to map to the latent space?  I am sure I'm missing something simple here. 

Clarity: the writing is reasonable although there is much room for improvement as I outline:
-- "To address these issues, we propose a novel unsupervised feature selection algorithm with a proven
35 algorithmic stability guarantee in this paper." --> sounds less awkward if "in this paper" appears after the comma
-- "It comprises a NN" -> it comprises of a NN
-- "evaluate the representation ability of the highly scored features locally." -> "locally evaluate the representation...."
-- "revealed by theoretical analysis and the stability of the selected features by our algorithm" -> sounds awkward. rephrase.
-- lines 54--60, remove the numbers as they make the structure awkward. 
-- "be linked with the generalization" -> linked with generalization
-- "proves the stability" -> prove stability
-- "the role of the regularization" -> "the role of regularization"
-- Line 134: do not start a sentence with a symbol.
--- Line 139: good to specify dimension of $\Phi$ and introduce the quantity. It also appears that \Phi(W) can just be combined into one symbol? 
-- "Our new algorithm is to use NN for the optimization of" -> awkward phrase
-- What is the difference between X(\Phi(W)) and X\Phi(W)? seems like both are used and this seems confusing.
-- "we obtain the feature selector and use it to make feature selection on new samples during testing" ->> seems ambiguous. please be more precise here.
-- "manifested in our experiments." -> "demonstrated in our experiments"
-- "There has been neither a clue about the role of the regulation in the uniform stability." -> grammatically incorrect with spelling error
--- line 155-159: could appear right after equation (2)?
--- line 178: missing a star below \Phi
--- Experimental section: it would be good to get a short and clear description of the architecture. I was unclear about this even after reading supplementary.
--- Line 240, the weights are sampled between two very strange numbers. Is there a reason for this?
--- "We set \lambda to be 1/2^7" -> this appears very small?
-- "the uniform stability" -> remove the
--- "meanwhile, the selected features by the proposed algorithm show comparable performance to the original features." -> use additionally instead of meanwhile.
--- "with respect to the training sample size, the regularization, the number of selected features, and the uniform stability" -> "with respect to sample size,  regularization levels, the number of selected features, and uniform stability"


Significance: Yes, I think the methodology could be interesting given its superior performance empirically over other methods and favorable theoretical properties. 
limitations_and_societal_impact: The authors could do a better job pointing out some limitations of their approach and furture work. No negative societal impact that I can foresee.
review_title: null

Meta-review: This paper proposes an unsupervised feature selection algorithm motivated by _algorithmic stability_, in the sense that the algorithm should not be overly sensitive to changes in the dataset. The algorithm consists of a feature _scorer_ and a feature _selector_, which uses the scorer to select features. These components can be instantiated as neural nets and trained jointly. The paper analyzes the algorithm's _uniform stability_ (the strongest notion of stability), proving that it is $O(1/n)$, which is sufficient for generalization. Experiments show that the algorithm performs well on multiple datasets, and confirms the theoretical claims about stability.

The reviews were mixed, but after much discussion, and back-and-forth with the authors, **I believe the correct decision is to accept.**

Let me first address some concerns raised by Reviewer 4y4c (paraphrased for brevity).

1. _The stability bound is uninformative because it is not fully controlled by the regularization parameter, $\lambda_1$; in particular, if over-regularized ($\lambda_1 \to \infty$), the bound does not go to zero._

Since the stability bound is $O(\frac{1}{n} + \frac{1}{\lambda_1 n})$, over-regularizing does not make it vanish. However, $O(1/n)$-uniform stability is sufficient for generalization, so I don't see this as an issue. Another reviewer also made a good point about this: "I have to remind myself that the role of the regularizer is not to control complexity. In particular, if the regularization term penalized the complexity of the model, then taking $\lambda_1 \to \infty$ should have vanishing stability, independent of $n$. But in their formulation, taking $\lambda_1$ to infinity would mean that only the feature score is effectively minimized and it is not surprising that $O(1/n)$ is what you might expect in this setting."

2. _According to the stability bound, $\lambda_1$ can be any constant (w.r.t. $n$) and guarantee stability. So why not just take $\lambda_1$ as small as possible? How then should one choose $\lambda_1$?_

While it is true that any constant $\lambda_1$ ensures $O(1/n)$ stability, and that this bound vanishes as $n \to \infty$, it is important to remember that what we ultimately care about is generalization error, and that we always have a finite amount of data. Given a certain data size, $n$, we want a value of $\lambda_1$ that balances stability (hence, generalization) with our ability to fit the data (i.e., reduce empirical risk). Determining this optimal value analytically is likely infeasible, so most people do it empirically via cross-validation (like you would any other hyper-parameter). Indeed, this is precisely what the authors do.

3. _The experiments borrow some results from prior work, and in doing so give the proposed method an advantage over some baselines. In particular, the baselines were optimized for a nonlinear decoder, while the proposed method uses a linear decoder, and the evaluation metrics involve linear decoders._

I believe this is simply a misunderstanding. The authors clarified in the discussion period that, "our decoder is linear and shallow, and it is the same as the baseline methods, such as CAE and AEFS, for which we used the original implementation in Ref. [1]." Thus, I think the comparison is fair.

Having settled these concerns, I don't see anything particularly wrong with the paper. The theory is sound; the experiments are sound; and the results are positive.

That said, why am I not making a stronger Accept recommendation?
1. For starters, the paper could use some polishing. The fact that there were so many misunderstandings indicates that the presentation could be improved. I myself find the notation used in the stability analysis to be a little overwhelming at times. But this can be fixed.
2. I don't find it all that surprising that the algorithm is uniformly stable, given that its objective function is strongly convex (under certain conditions on the hypothesis class). This is not to say that every paper must come to an unexpected conclusion, but that it seems straightforward to prove uniform stability in this case; you just need to make the right assumptions and then follow the proof techniques laid out in prior work. That being said, the main insight of the theory is that just optimizing a selector alone is insufficient to guarantee stability (and generalization); one must also optimize the scoring function for stability. That takeaway is valuable, even if the proof follows from prior work.
3. None of the reviews seemed all that excited about the paper. Not every paper has to be revolutionary, but at a competitive conference, such as NeurIPS, it helps to have at least one high-scoring review.

So, consider my recommendation "accept if possible."

Note for the authors: In Assumptions 1 & 2, the order of quantifiers seems off. They go, roughly, "$\forall x$, $\exists$ ..." This means that for any given $x$, there exists something (either a subset of the data or a constant) such that some property holds. But I think for the bound to hold uniformly what they really want is, "$\exists$ ... such that $\forall x$ ..."

Decision: Accept (Poster)