Algorithmic stability and generalization of an unsupervised feature selection algorithm
Authors: Xinxing Wu
Qiang Cheng
Venue: NeurIPS 2021 Poster (2021)
Keywords: Feature selection
Algorithmic stability
generalization
neural network

Abstract: Feature selection, as a vital dimension reduction technique, reduces data dimension by identifying an essential subset of input features, which can facilitate interpretable insights into learning and inference processes. Algorithmic stability is a key characteristic of an algorithm regarding its sensitivity to perturbations of input samples. In this paper, we propose an innovative unsupervised feature selection algorithm attaining this stability with provable guarantees. The architecture of our algorithm consists of a feature scorer and a feature selector. The scorer trains a neural network (NN) to globally score all the features, and the selector adopts a dependent sub-NN to locally evaluate the representation abilities for selecting features. Further, we present algorithmic stability analysis and show that our algorithm has a performance guarantee via a generalization error bound. Extensive experimental results on real-world datasets demonstrate superior generalization performance of our proposed algorithm to strong baseline methods. Also, the properties revealed by our theoretical analysis and the stability of our algorithm-selected features are empirically confirmed.

Algorithmic Stability and Generalization of an Unsupervised Feature Selection Algorithm
Xinxing Wu, Qiang Cheng" University of Kentucky, Lexington, Kentucky, USA
Abstract
Feature selection, as a vital dimension reduction technique, reduces data dimension by identifying an essential subset of input features, which can facilitate interpretable insights into learning and inference processes. Algorithmic stability is key characteristic of an algorithm regarding its sensitivity to perturbations of input samples. In this paper, propose an innovative unsupervised feature selection algorithm attaining this stability with provable guarantees. The architecture our algorithm consists of feature scorer and a feature selector. The scorer trains a neural network (NN) to globally score all the features, and the selector adopts dependent sub-NN to locally evaluate the representation abilities for selecting features. Further, we present algorithmic stability analysis and show that our algorithm has performance guarantee via generalization error bound. Extensive experimental results on real-world datasets demonstrate superior generalization performance of our proposed algorithm to strong baseline methods. Also, the properties revealed by our theoretical analysis and the stability of our algorithm- selected features are empirically confirmed.
1 Introduction
nigh-diimessioal data is challenging due to the curse dimensionality [ Dimensionality reduction an important technique for dealing with such data, comprising two typical approaches: feature extraction and feature selection. The former, including principal component analysis (PCA) (35] and autoencoder (AE) [41] 5), widely used in various fields such as biology [3] and computer vision [49 18 38 Nonetheless, new features produced by feature extraction form a new space and, in general, do not have direct correspondence original features, leading difficulty in deriving interpretable insights for the domain problems, such as biomarker identification and drug discovery. Alternatively, feature selection identifies essential features from the original feature space, providing critical interpretations and insights in many tasks [T0 45 e.g., gene functional enrichment analysis, biomarker detection, and tigh-throughhut screening for drug discovery 22
27
Stability is an important characteristic an algorithm, which quantifies the sensitivity of the output the perturbation of its training samples [12 19]. The current stability analyses of feature selection algorithms mainly focus on similarity- based and frequency-based stability measures for practical assessment, e.g., 16 21 3d] rather than the algorithms themselves, leaving feature selection with proper algorithmic stability S an unmet need. Especially, existing unsupervised feature selection algorithms use the empirical error, or its proxy, represent generalization error but provide no theoretical guarantee of such use, leaving their ability to generalize to new data unclear.
To address these issues, in this paper propose novel unsupervised feature selection algorithm with a proven algorithmic stability guarantee. Our approach trains a neural network (NN) to globally score all features and dependent sub-NN select the features with the highest scores to reconstruct the
Coorespondence should be addressed to: giang.chenge... whrneehhhnyyyyny @uky.edu.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

original data. Mathematically, we analyze our new algorithm and provide generalization error upper bound. ensuring its algorithmic stability for guaranteed learning performance. Our contributions are summarized in the following:
We propose an innovative approach for feature selection. constructs a NN with a feature scorer to globally score all the features and dependent sub-NN with feature selector to locally evaluate the representation ability of highly scored features. Thus, our algorithm capable of both globally exploring and locally excavating essential features.
We establish performance guarantees for our algorithm, including a proven conver- gence rate O (1/ (n minf Ait) + 1/n) to ensure uniform stability and a rate O (1/ (Vimint (iii,, X13) +1/Vn) for generalization error. Here, n is the number of training samples, and λι is regularization parameter.
We confirm the effectiveness of our proposed algorithm with extensive experiments on 10 real datasets. It achieves more competitive performance for data reconstruction and down- stream classification tasks than -fac-of--the-rr methods. Notably, the features selected by our algorithm have performance comparable to the original features. Further, the properties revealed by our theoretical analysis and the stability of our algorithm-selected features are empirically verified.
The remainder of the paper is organized as follows. We first discuss the related work, then present our proposed algorithm. Next, we show that our proposed algorithm is uniformly stable and has a guaranteed generalization bound. Finally, we conduct extensive experiments to validate our proposed new algorithm and the properties related our proved generalization bound.
2 Related work
In the literature, the approaches for bounding generalization error can be generally grouped into two categories: One by controlling the complexity of hypothesis spaces and the other by focusing on the property of learning algorithms. The former usually need to define an additional complexity measure on the hypothesis space, such as the Chnnkk-Chrrvoneniss dimension [44] and the Rademacher complexity [6;; the latter mainly include algorithmic stability [8] and robustness-baat analysis (50]. In this paper, we focus on algorithmic stability to analyze the stability and generalization of our proposed new algorithm.
Algorithmic stability in learning theory. Algorithmic stability is an important tool for analyzing the generalization of algorithms in learning theory. It characterizes the sensitivity of the loss when the inputs to an algorithm are changed. Simply speaking, if an algorithm is stable, then its loss does not change significantly when the training samples are modified slightly, such deleting and replacing a sample. Since the inception of the notion 44 43), the concepts and properties of stability have become a significant learning theory topic. Bousquet and Elisseeff (8) have shown that stability has a direct connection with generalization in that the uniform stability of a learning algorithm implies tight generalization error bound. Thanks to this connection, algorithmic stability has been widely used for generalization analysis of learning algorithms, including regularized least squares regression [8], multi-class support-vector- vector--c---nniinneeeee classification [39], multi-task learning (28). supervised autoencoders 233, and distributed learning [6).. Especially in (28). the auxiliary tasks
are used for regularization, and so is the reconstruction (3 It noted that all these studies are on
supervised learning. For unsupervised learning, stability analysis of algorithms is yet to be developed; particularly, the role of regularization in the stability bound remains elusive.
Stability studies of feature selection algorithms. A few existing studies about the stability of feature selection algorithms are mainly on stability measures for quantifying the sensitivity input changes. In [21] Shannon bbased stability measure is proposed for evaluating the stability of selected features. In [16] the stability of feature selection algorithm is assessed by comparing the average pairwise similarity of all feature subsets obtained from different subsamples by the algorithm. The recent work (34) generalizes the requirements of stability measures into five properties and proposes a statistical estimator for stability to satisfy these properties. Although able to provide relevant assessment information about the selected features to some extent, most stability measures have no essential connection with the corresponding feature selection algorithms. In addition, they

---

are demonstrated empirically in general, without theoretical insights and generalization guarantees. The only exception uppears to be the theoretical proof for uniform weighting stability [25]. This work builds an algorithm called feature weighting regularized energy-based learning (FREL., proves stability, and extends to a further ensemble version. FREL is for supervised feature selection, and the uniform weighting stability does not appear to be linked with generalization. In brief, despite the wide use of algorithmic stability in analyzing many learning algorithms, its use and analysis for unsupervised feature selection algorithms are still unmet needs.
Unsupervised feature selection algorithms. Many unsupervised feature selection algorithms have been proposed in recent years to meet the demand for effectively handling large-scale and high- dimensional data. They can be generally classified into four categories: filter, wrapper, embedder. and hybrid approaches [2) [2]]_ In this paper, we will mainly compare our algorithm with ten typical unsupervised feature selection algorithms, including Laplacian score (LS) [17], principal feature anal- ysis (PFA) B3J SPEC [52), multi-cluster feature selection (MCFS) 19, unsupervised discriminative feature selection (UDFS) [11], nonnegative discriminative feature selection (NDFS) (26], Autoen- coder feature selector (AEFS) [15]. agnostic feature selection with slack variables (AgnoS-S) S) M.. graph-based infinite feature selection (Inf-FS) [40], and concrete autoencoders (CAE) M. LS, SPEC, and Inf-FS are filter approaches; PFA can be classified as a wrapper approach: the other six are embedded algorithms. Among them, AEFS, AgnoS-S, and CAE are AE-based feature selection methods: AEFS combines AE regression and f,, regularization on the weights of the encoder to obtain a subset of useful features; AgnoS-S adopts AE with the L norm on slack variables in the first layer of AE to implement feature selection; CAE replaces the first hidden layer of AE with concrete selector layer [31], and then it selects the features with a high probability of connection to the nodes of the concrete selection layer. While frequently used, these methods have no theoretical analysis of their algorithmic stability and leave their generalization abilities to new data unclear. Indeed, they generally lack such needed abilities, as demonstrated in our experiments (see Table 3).
3 Notations and preliminary
Let n. m, k. and d be the numbers of training samples, features, selected features, and reduced dimensions. Let X E " be a sample matrix, and X be its transposition. A lowercase capital letter like Wm. denotes a vector; Diag(w,, represents a diagonal matrix with the diagonal Wm. w w-fnax, stands for the operation to keep the & largest entries of wm while making the other entries 0. Let 6: 1R + RMM be an demeent-wise operation. ||. ||r. || 1l2. I1- and || llee respectively denote the Frobenius, ég, f1. and infinity norms. The sample space of data is denoted as X. We assume all samples are bounded, i.e., Vx E X, 3xg 0, such that ||x||2 & K1- Besides, Vz, x' E [0, oo), for a function f. (f x²) A f(x) f( + tdr),, where Ar x' x and i E [0.
Let S A {xx E X.i = 1, .......)) n) be finite set of training samples which are independently and identically distributed according to an unknown distribution P. We denote the sets after removing and replacing the i-th element from S by Si & X X,+1, { and S (xi...., X,-1, X X,+1...., }, respectively. Let A be an algorithm, and As be a func- tion picked by A from the hypothesis space based on S. A is assumed to be deterministic and symmetric with respect to S. Let é X x X - [0, +00) be a loss function. The generalization error
/ ((As,x)dP,
L(A,S) A Ex [((Assx)]
and the empirical error is
Lemp (A 3 1 n 71
Σ {(As,x)),
where x; E S, i 1,2....,
To study the stability of A, the leave-one-out error is used,
1 Σ ((Ass,)))
Lioo (A, S)
In [1I, three variants of based agnostic feature selection algorithms are proposed. AgnoS-S is generally the best among the three; thus, in this paper will compare our algorithm with AgnoS-S.
3

---

By the empirical and leave-one-out errors, uniform stability is defined as follows:
Definition (Uniform Stability 8 An algorithm A has uniform stability 3 with respect to E if SS E X", == 1,2,
[(s)) ((Ag,,))) )lo & 3
where 3 is a function of n. Generally, for a uniformly stable algorithm, B decreases as (1/nn).
4 Method
Now we will present our novel AE-based feature selection algorithm.
Revisit of AF. For AE, we formalize as follows:
min f.g
X f((())
where g is encoder, and f is decoder. g(X) embeds the input data into latent space 1Rx where d denotes the dimension the bottleneck layer.
Formalization of unsupervised feature selection. The goal of feature selection is identify subset of important features in the original feature space, and it can be formalized as follows:
min (Xs())) - S(K).
where S(k) denotes a subset of k features of X with h: m. X is the resulting dataset by restricting X to the selected subset. We use H to represent a mapping on the k-dimensional space, and it selects subset of the features of X preserve the information of as much as possible. The
optimization problem of evaluating the subset of features is typically NP-hard [32 14]. This paper will develop efficient algorithm effectively approximate the solution of
A AE-based new algorithm for feature selection.
Our model is constructed as follows:
min
|X - f(o(X(((W))) max: + \1 - ((((X((((i))))I
Wiffa
where ((w)) & Diag(o(wm)) E Rmxm, & ((W))
Diag(( (((wm)) maxx) E Rmxm and
A is regularization parameter. We NN for the optimization of 2 and the network architecture is shown in Supplementary Figure 1. For the convenience of later discussions, (WW))aas,, ||x ((((x((WWi))))l
Vx E X, let goelec (eelec(((W)) (#, jmaxt, .x) - ||x (()(((((W,))))))) m))))) and gecore (Dor)) x) &
The operators & ((W) and (W1)))mm are called feature scorer and feature selector, respectively." & (Wi) and & (WWi)maxx will iteratively interact through the NN and sub-NN. Specifically, (2) can be regarded as an extension
common NN, with the main difference being the sub-NN, i.c., the first term of (2) During training, & (D(Wi)max, will select the top-k features (from the scorer weights, ie.. ((Wi) 1 by ensuring these selected features to well reconstruct the original input X with the NN. On the other hand, the NN, as constraint, will ensure the selected features for & maxx to have the largest importances globally. After training, we obtain the trained + W,) maxx, and then we make feature selection and USPS as examples, for k = 50 and &max, = (W?) maxi,
samples during testing. Taking MNIST-Fashion, COIL--00, (W?)maxx, we visualize the feature selection and reconstruction results MNIST demonstrated in Figure T and we give the selected features original samples of USPS in Figure
5 Algorithmic stability and generalization
As previously reviewed, existing feature selection methods have not considered algorithmic stability. Generally, they lack this property or generalization ability, as demonstrated in our experiments. Moreover, there has been no clue about the role of regulation uniform stability. Our algorithm is built to address these issues and, here, it will be shown to possess these desirable properties. For (2)
For simplicity, we will the shorthand notations & and maxx denote @(W1) and & (WW))max

---

Figure I: Original testing samples (row 1), 50 selected features (row 2), and reconstruction based on the 50 selected features (row 3) for MNIST-Fashion (left panel) and COIL-20 (right panel). More results are illustrated in Supplementary Material.
Figure 2: Key features with original samples for USPS.
the first term implies that the original samples are well represented by the selected features. The second term scores all the features by their reconstruction ability and ensures that the selected features have high scores among all features. It will used as a regularizer to promote the stability of the feature selection. It requires that all features be explored globally for high representation ability before being further excavated locally by the selector. The role of the scorer will be empirically demonstrated in the experiments (see Figure (b)).
is worth noting that, contrast existing models, such as NNs, which require nonlinear activation functions to capture the nonlinearity, the first term in ( naturally facilitates nonlinear model even when the scorer is linear model. Such a nonlinearity intrinsically comes from ranking the feature weights and selecting the & informative features during the iterative optimization. For simplicity, in the following discussion, we only consider the linear version of f and g in (2) that is, gXX) = XWF. E, WE I mxd and (X)) W,, WD E Rdxm The experimental section will show that such a concise linear version already achieves superior performance.
Formalization of stability and generalization. Let (#mmax, 4.) and (( .D)) corre- spond to the optimal feature selectors and feature scorers for the errors
RLemp
gelee Tiaax x;) + A eecore ( x;)
and
R. R.Lemp ()
Σ
gellec ( xi) + Y eecure d1, xi),
i=1,is)
(Tmmax, .) goolne ) ymax, :), which will be used where E (1,...,, nn.. Our goal is to bound (
for the analysis of uniform stability. Further, we intend to bound 1, selec mmmxa ,S) T.eelec ( (Tpmaxa S),
or L seeec (qmaxx, S) Lgelec qmmaxe, S), to be used in the analysis of generalization errors.
Assumptions. To determine the stability and generalization bounds, the following assumptions will be needed:
mmax) Assumption 1. 3xg > O, such that, Vx X. [[x (Φ) maxx WEl < K2 (x((x.
This assumption is reasonable, because the null space of o. -.y is smaller than mmxxe - (Φ) / maxe. that is, we generally have
WE WD < ((0.- x).) Wi.W,) WeWW)").
I-aNN - (Φ) )
maxi
where r(-) denotes the rank of matrix. So. it is more likely that the column vector (( o. WED)" will have m non-zero elements. Consequently, it is more likely that the row vector (x(2., - - WWWW will have non-zero elements.
5

---

Assumption 2. 32 = (z1.22. 22......... ; C S, such that, Vx E X, X can be reconstructed by Z, i.e. x Ei= a,Z; + 7), where o7 small reconstruction error that satisfies 1|zl22 & K3/n, and ag is scalar that satisfies V of & R4. with Fig and R4 being positive constants.
This assumption mild and implies that any sample x can be reconstructed by Z with a small construction error that decreases with n." Theoretically speaking, when the samples all reside manifold, it obviously holds. Practically, is related to the self expressiveness of samples exploited in many subspace learning algorithms, e.g., [29] 36 37
Assumption 3. Let Lemp.
V/ (D,
(1/n) Dini (ocore xi) and L Lmmp, ())
(1/u) Ei=1 pucore ( z.). Vt E [0, 1].
A L emp.e
( (0.) A ( Lecor ()) P.)
score, A (Lmmp S). 2. + A ( S), 2.)
scoro,
(n 1)/n
The implication of this assumption is clear: it requires that, at 4 and 1 the perturbations of score can be controlled by those of Leeope and the left-hand side of (3) is related to Z in Assumption 2 makes similar assumption; however, we enhance the factor t into n/ 1) on the right-hand 3 much weaker and more reasonable than that 23 since
22
side of (3. which makes Assumption
L Lacore (T) = (n/(n- - 1)) Leupp (Φ) 5) when Z = SVM Further, the perturbations of L Lemp ( S)
and score, ($.) are implicitly related to λ (see Proposition
below).
Proposition 1. Let Ammax
( maxi Tmaa. vt E [0, 11, the following inequality holds:
soore (Lmmp
S).
A' (Lemp V S), x2-)
maxe
[x? $
1 maxx
WE 2 +2) ((AAmaxx WE) WDll2)
Proposition T reveals the relationship of the regularization represented by X with the perturbation of Lemp 4 5) and Lecage ($.,, S).
As discussed above, we will mainly verify Assumption 2 For this purpose, we develop a core- subspace learning procedure. More details about the verification are given in Supplementary Material.
Uniform stability. We establish bound on uniform stability of our algorithm for (
Theorem (Uniform Stability). Under Assumptions
2 and 3
we have, Vn > 2.
paclec (Tinax),
gocter (( (T)))
max
:)
! 11=0 = (mminn(VA.. A1 n
(
(4)
This theorem quantifies the insensitivity of our algorithm to the perturbation of its input, and the optimal feature selector k-maa would not change significantly with the change of one sample. The upper bound in (4) is mainly about the approximate behavior of n, and it is theoretically more meaningful when A is much larger than 1/n. If X is very large, i.e., with over-regulariiztion, then essentially the second term of (2) works, which will make the feature selector underfit training samples and incur large test error. Theoretically, may still be sufficient for generalization, and the bound in (4) will reduce to O (1/n); in practice, however, the corresponding validation error should be large. Thus, such large A would never be practically chosen. How analytically determine the optimal value of X is out of the scope of this paper and will be an interesting future research topic. In this paper, we empirically choose a positive value of X by using cross-validatte (see Experiments for details). If A is set to 0, then the second term of (2) will vanish; in this case, the stability with only the first term of warrants further study in the future.
"Luu al 28 and Le al 26 have made similar assumption.

---

Generalization error bound. Now we will bound L Lamp [ S) Ladeo ( .S).
Theorem (Generalization Error), 3ss > O and ê E (0, 1), Vx E X' and S, as long as {(As,x) & K5, the following inequality holds with probability least 8,
Viamin VA + In (t)
V In (t)
L sellec ( (Buaass 5) Lompp (Tmmas, - =0 =
This theorem shows that, besides the uniform stability bound in Theorem I there an upper bound for the generalization error of our proposed algorithm. By this theorem, as long as our feature selection algorithm stable, the empirical error has a proven guarantee to approximate generalization error. The convergence rate of generalization error is O (1/ (vn min / A1. A13) + 1// It is noted that, when X > 1, the convergence rate is O (1/vn), which is different from the rate under the l regularization; when A & 1, the convergence rate is O (1/ (vπdz)), the same as that under the & regularization [8]. When the reconstruction error from the feature scorer is made small with large \1 > the scorer will play a more important role than the selector, and the selector might be underfitted (see Figure 3 (b)); and vice versa for A < 1. Additionally, if we fix λ1, the bound will reduce to O (1/vm), which decays similarly to the bound under the & regularization g when À fixed.
The proof's of Proposition Theorems and the bound of s (Imaxx, ,S) L golee (1 S).
and more discussions are provided in Supplementary Material.
Experiments
In this section, we will perform extensive experiments to validate new algorithm.
Table Statistics of datasets.
No.
Dataset
#Samples
#icatures
#Classes
No.
Dataset
#Samples
#Fcatures
HClasses
Mice Protein
1,080
77
USPS
9,298
256
2
COIL--20 33
1,440
400
20
GLIOMA
50
4,434
Activity
5,744
561
Prostate
102
5,966
ISOLET
7.797
617
26
SMK_ SMK_CAN_IL
CAN_187
187
19,993
MNIST-Fashion
A8
10,000
784
10
10
arceme
200
10,000
Datasets to be used. The benchmarking datasets and their statistics are summarized in Table Following CAE [1] and considering the long runtime of UDFS, for dataset 5, we randomly choose 6, 000 samples from the training set for training and validating and 4, 000 samples from the test set for testing. We then randomly split 6, 000 samples into training and validation sets by a ratio of 90: 10. For other datasets,
randomly split the samples into training. validation, and test sets by ratio of 72:8:20, and we tune hyperparameters on the validation set. More details about these datasets are provided in Supplementary Material.
Design of experiments. In all experiments, for our model, we use the same linear decoder as that in [I] For the encoder, for a fair comparison, our algorithm uses the structure from an AE having one hidden layer with the same number of neurons as other AE-based baselines in comparison. We use the linear activation function for the encoder in the same way as CAE and AEFS in [1] For feature selection, the first layer of the encoder in our NN uses the slack variables the same way as AgnoS-$ S in [1I. We set the maximum number of epochs to 200. We initialize the weights of the feature selection layer by sampling uniformly from U 999999999, 0.9999999]] and the other layers with the Xavier normal initializer. We adopt the Adam optimizer (20) with a learning rate of 0.001. set \ to 1/2 We take k = 10 for dataset and 50 for datasets 2-6 following CAE and
Datasets and are downloaded from scikit-feature feature selection repository (2]]
Datasets 6- 10 are from the
'This distribution makes initial values of the weights in the selection layer close 1 but still different break the potential ties.
We tune A by searching in {2, //.2,,...,,/............ 1/2 on the validation set of MNIST-Fashion, then choose the optimal one and use on other datasets.
7

---

k = 64 for -igh-dinnniioall datasets 7-10. The dimension of the latent space is consistently set to k. The main codes related to our proposed algorithm are publicly available, and the implementation details of baseline algorithms are provided in Supplementary Material.
Two metrics used for evaluating the performance of algorithms: 1) reconstruction error, which is measured in mean squared error (MSE); 2) accuracy, which is measured by passing the selected features to downstream classifier viable means to benchmark the quality selected features. For fair comparison, following CAE [T. after selecting the features, we train an ordinary linear regression model reconstruct the original features, and the resulting linear reconstruction error is used as metric 1),² for metric 2) we adopt extremely randomized trees [3] as the classifier.
Results on 10 datasets. Our experimental results on reconstruction and classification with the selected features are displayed in Tables and 3 10 and [Wr] and W are shorthands for feature selectors m = |Wimmxx maxx and max (W7 (Wf)maxs maxi We followed the way of CAE [] to split samples and to report the final results the hold-out test set. For fair comparison, adopt the published results for reconstruction and classification by LS, AEFS, UDFS, MCFS, PFA, and CAE on datasets 1-5 from [.] From Table 2 it is seen that algorithm gives smaller linear reconstruction erross than baseline methods on majority datasets, indicating a stronger ability to select subset of representative features. From Table 3 it is evident that algorithm exhibits almost consistently superior performance in the downstream classification task on diverse datasets.
directly
Table Linear reconstruction error with selected features by different algorithms.
Dataset
LS
SPEC
NDFS
AEFS
UDFS
MCFS
PFA
Inf-FS
AgnoS-S
CAE
No.
[W]]
W-
I
0.603
0.051
0.041
0.783
0.867
0.695
0.871
0.601
0.013
0.372
0.009
0.008
2
0.126
0.413
0.134
0.061
0.116
0.085
0.061
0.130
0.038
0.093
0.015
0.016
3
0.139
0,127
144.353
0.112
0,173
0.170
0.010
0.282
0.010
0.108
0.005
0.005
4 0.344
0.119
0.129
0.301
0.375
0.471
0.316
0.098
0.042
0.299
0.016
0.018
5
0.107
0.127
0.043
0.024
0.041
0.022
0.023
6 3,528
1.120
0.918
0.025
0.034
1,050
0.022
5.245
0.017
0.010
0.018
0.018
0.173
8 1.694
0.605
4,506
0.280
0,228
1.929
08180
0.187
0.387
0.048
0.1
0.144
9
7.344
0.118
3.005
0.102
5,492
0.089
8.725
0.096
0.077
0.093
0.100
10
0.328
0.045
1335.029
0.025
4.826
0.042
329.50)
0,031
0.029
0.025
0,024
Table 3: Classification accuracy (%) with selected features by different algorithms.
Datasel
No.
L.S
SPEC
NDFS
AEFS
UDFS
MCFS
PEA
Inf-FS
AgnoS. S
CAE
[W
W
13.4
24.5
8.3
12.5
13.9
13.9
13.0
42.6
51.9
13.4
97.2
99.1
58.0
64.2
28.0
20.3
18.8
24.0
28.7
29.5
36.4
18.1
56.1
42.0
87.7
87.6
40.7
7.3
57.6
45.5
52.2
62.2
13.7
18.1
68.5
82.4
51.7
27.6
13.8
58.0
54.7
51.3
68.3
23.5
79.1
67.7
80.8
80.5
36.3
46.3
11.9
94.2
94.4
12.6
96.0
21.0
95.6
95.5
96.1
95.4
50.0
52.4
47.6
47.6
85.7
90.5
57.1
90.5
61.9
76.2
85.7
95.2
90.5
42.1
50.0
65.8
73.7
57.9
10
62.5
32.5
70.0
75.0
62.5
77.5
67.5
77.5
77.5
82.5
75.0
Average
43.2
17.
19.1
39.5
56.742262
42.7
65.4:23355
35.4-18.1
70.02213
63.3 87.9
84 11.
Further, we compare the behavior of our algorithm with contemporary algorithms over different By varying i on ISOLET obtain the corresponding linear reconstruction enrors and classification accuracy rates as the outputs from different algorithms. We plot the linear reconstruction errors in MSE and classification accuracy rates in Supplementary Figure 8. It can be observed that algorithm demonstrates almost consistently better and more stable performance than feature selection algorithms in comparison.
'They can be found at http://iccbu..ooooiiiixngwuuuau/
9 Here, reconstruction error denotes the error from the first term of 2 T0 "{" mark denotes the case with prohibitive running time, where the algorithm ran for more than a week without getting result and thus stopped.
8

---

Also, we take D [iimaxx and we compare the variation of classification accuracy with the reduction of original features. The results are shown in Supplementary Table and Supplementary Figure 9. It is observed that all the reduction in the number of features is more than 80%, while the corresponding reduction in classification accuracy is less than 10% with the exception of ISOLET (which is 11.2% 11.%).. It shows that our algorithm can effectively reduce the number of features but still maintain the classification performance comparable to the original data.
7 Discussion
In this section, we will empirically verify the properties related to uniform stability bound and generalization bound in Theorems [ and 2 Further, we will empirically discuss the algorithmic stability and the stability of selected features and also analyze the time complexity of our algorithm
Effect of n. We plot the curves of error difference L,elee (Tmaxe, S) - I.selec (omaxx, .S) and test emmp
error versus in Figure (a). It is observed that n has direct effect on the error difference and test error: 1) The more training samples, generally the smaller the test error. This observation verifies that small training sets cause overfitting and, by increasing the training set size, the generalization of our algorithm becomes improved with the test error decreased. 2) The error difference decreases in n. This phenomenon is well in line with the theoretical result in Theorem
Effeet of λ₁ We plot the curves of the error difference and test error versus A in Figure (b). Two observations can be made: 1) The larger λ1. the smaller the error difference. Such an experimental result aligns well with Theorem 2] 2) The test error decreases at first and then increases with A1- The reason may be as follows: by increasing Å from zero to about 0.01, the feature scorer will play an increasingly important role and facilitate finding appropriate scores for features to reduce the reconstruction error, which helps decrease the test error. The regularization role of the scorer is evident: when A increases from 0 to a small value, the test error decreases. But if a increases too much, it would over-emphasize the scorer and the minimization of the reconstruction error, making the feature selector underfit training samples and thus incurring larger test errors. These empirical curves offer informative clues for understanding the role of regularization in the generalization bound and choosing a proper X in our experiments.
Effect of k. We plot the curves of the error difference and test error versus i in Figure 3 (c). It is seen that the larger k. the larger the error difference. This observation is in line with Theorem 2 (see Supplementary Material for the detailed expression of upper bound). As discussed below this theorem, the generalization error bound of our algorithm has a similar convergence rate to that under the & regularization. To see how the selection affects the error difference, we plot the curves of Frobenius norms of WF. e. WD and Wo WF Wn in Figure 3 (d). 1I Note that they have a similar increase tendency to the error difference. The reason may be that, by selecting more features, - ($mmax, SS and more variables and be more easily affected by the perturbations
Temmp (Tpaax._ S)) would depend from the variables; as a result, the feature selector would be more difficult to fit. From Figure B (c). also observe that the larger k the smaller the test error, which is sensible because more selected features mean less loss of original data and the reconstruction would be better. In addition, from Figure 3 (a)-(c), different 4. scorers, such as [Wr] and Wi, have similar behaviors, which reflects the tendency implied in Theorem 2
Algorithmic stability analysis. Adopting the same experiment design on MNIST-Fashion in Sec- tion we vary n from 3, 000 to 6, 000 with a step size of 1, 000 to obtain different S: meanwhile, we delete a sample for each S to get the corresponding S and then calculate the left-hand side of (4) on the testing set for these trained models. From the plots in 3 increase of n, the curve of uniform stability bound presents a downward tendency, which is consistent with our theoretical analysis.
it is seen that with the
Overall, the above four experiments for interpreting the generalization bound are related to the training sample size the regularization parameter λ₁ and the number of selected features k and the stability bound, showing different aspects or behaviors of our algorithm. Taken together, these experiments verify the properties revealed by Theorems I andd]
l' Here, Wo denotes the entries of W are except le ones its diagonal.

---

[Wl error difference
Wi error difference
[Wa] test
W9 test
[Wl:: [WW.WlWlllll
wi [[WoW.Woll-
Wal: WWlllllWWlll-
Wi: WWWWlll
2.85-2
9E-4
3.6E-2
11E-4
4.2E-2
8E-4
3.4b-2
2.4E-2
5E.4
2.8E-2
5E-4
2.6E-2
SE-410
1E-4
5E-41E.7
15
26-2
26-4
10
25
40
55
85
1.8E-2
Percentage training semples
(a)
(b)
(C)
Frobenuu norm
310
0.45
Random splits: 1-10
210
0.30
0.12
110
0.15
1010
40
55
10
85
3000
4000 5000
6000
3000
4000
5000
6000
(d)
(e) [w]
(1) W?
(g) |Wil
(h) W?
Figure 3: Empirical interpretation of generalization bound and stability analysis on MNIST-Fashion. (a)-(c) show the curves of error difference and test error versus n Å1. and k, respectively; (d) plots the overall size of network weights versus k; (c)-(f) are for algorithmic stability; (g)-(h) for the stability analysis of 10 selected features. each (a)-(c), the left vertical axis represents error difference, and the right vertical axis represents test error.
Stability analysis of selected features. We empirically analyze the stability of features selected by (2). We randomly split the samples of MNIST-Fashion into the training and testing sets and then use (2) to perform feature selection. We repeat this procedure 10 times with different random seeds and plot the selection results in Figure (g)-()) Note that the selected features almost overlap for different splits and are stable. More results are provided in Supplementary Material.
(g)-(h)
Computational complexity. Experimentally. the computational time of our algorithm is about twice that of AE. Our algorithm has only an additional sub-NN compared to AE and shares parameters with the NN. Also, the fitting term of sub-NN is quadratic and similar that of AE Therefore, the overall computational complexity of (2) is of the same order as AE.
Ethical statement. This paper focuses on feature selection, which is a dimensionality reduction approach. To our best knowledge, there are no ethical issues and negative societal impacts of the proposed technique in this paper.
Conclusions
In this paper, propose an innovative unsupervised feature selection algorithm with provable perfor- mance guarantees, which consists of a feature scorer and a feature selector. Theoretically, we prove uniform stability and provide the generalization error upper bound for algorithm. Empirically, show that our algorithm achieves performance better than the contemporary algorithms on various real-world datasets; additionally, the selected features by the proposed algorithm show comparable performance to the original features. Moreover, we experimentally verify the properties revealed by theoretical analysis with respect sample size, regularization levels, the number of selected features, and uniform stability. Additionally, this new algorithm may be applied to other tasks, such selecting important patterns of image data beyond pixels, which we will extend in future work.
9 Funding
This work was partially supported by the NIH grants RG17000,,,,, R56NS1 17587, R01HD101508.
and ARO 1911NF-17-1-00M
10

---

Acknowledgment
We sincerely thank the anonymous reviewers and AC for their valuable comments.
References
[1] A. Abid, M. F. Balin, and J. Zou. Concrete autoencoders: Differentiable feature selection and reconstruction. In International Conference on Machine Learning, pages 444-453, Long Beach, California, United States, June 2019. [page] [page]] [page
[2] S. Alelyani, J. Tang, and H. Liu. Feature selection for clustering: A review In C. C. Aggarwal and C. K. Reddy, editors, Data Clustering: Algorithms and Applications, chapter pages 29 20- CRC Press, 1st edition, August 2013. [page 3
[3] R. C. Anafi, L. Francey, J. B. Hogenesch, and J. Kim. CYCLOPS reveals human transcriptional rhythms in health and disease. The Proceedings of the National Academy of Sciences, 14(20))
5312-5317, April 2017. [page [
[4] D. Anguita, A. Ghio, L. Oneto, X. Parra, and J. L. Reyes-Ortiz. A public domain dataset for human activity recognition using smartphones. In European Symposium Artificial Neural Networks, Computational Intelligence And Machine Learning, pages 437-442, Bruges, Belgium, April 2013. [page 7
[5] D. H. Ballard. Modular learning in neural networks. National Conference on Artificial Intelligence, pages 279-284, Seattle, Washington, United States, July 1987. [page]]
[6] L. Bartlett and S. Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3:463-482, November 2002. [page
[7] R. Bellman. Dynamic Programming. Princeton University Press, Princeton, New Jersey, United States, 1st edition, 1957. [page]]
[8] O. Bousquet and A. Elisseeff. Stability and generalization. Journal of Machine Learning Research, 2:499-526, March 2002. [page [page 2 [page [page]]
[9] D. Cai, C. Zhang, and X. He. Unsupervised feature selection for multi-cluster data. In Inter- national Conference on Knowledge Discovery and Data Mining, pages 333-342, Washington, District of Columbia, United States, July 2010. [page 3
[10] Q. Cheng. H. Zhou, and J. Cheng. The fisher-markov selector: Fast selecting maximally separable feature subset for multiclass classification with applications to high-dimensional data. IEEE Transactions on Pattern Analysis and Machine Intelligence, 33(6):1217-1233, June 2011. [page
[11] G. Doquet and M. Sebag. Agnostic feature selection. In Joint European Conference on Ma- chine Learning and Knowledge Discovery in Databases, pages 343-358, Würzburg, Germany, September 2019. [page]] 3) [page]
[12] K. Dunne, P. Cunningham, and F. Azuaje. Solutions to instability problems with sequential wrapper-based approaches to feature selection. Technical Report TCD- CS 2002-28 School of Computer Science, Trinity College Dublin, Dublin, Ireland, July 2002. [page
[13] P. Geurts, D. Ernst, and L. Wehenkel. Extremely randomized trees. Machine Learning, 63(1):
3-42, March 2006. Ipage g
[14] Y. Hamo and S. Markovitch. The COMPSET algorithm for subset selection. In Interna- tional Joint Conference on Artificial Intelligence, pages 728-733, Edinburgh, Scotland, United Kingdom, July-August 2005. Ipage
[15] K. Han, Y. Wang, C. Zhang, C. Li, and C. Xu. Autoencoder inspired unsupervised feature selection. In International Conference on Acousties, Speech and Signal Processing, pages 2941-2945, Calgary, Alberta, Canada, April 2018. [page]

---

[16] Y. Han and L. Yu. A variance reduction framework for stable feature selection. In IEEE International Conference on Data Mining, pages 206-215, Sydney, Australia, December 2010. [page D. Ipage
[17] X. He, D. Cai, and P. Niyogi. Laplacian score for feature selection. In Advances in Neural Infor- mation Processing Systems, pages 507-514, Vancouver, British Columbia, Canada, December 2005. [page
[18] P. Ji, T. Zhang, H. Li, M. Salzmann, and I. Reid. Deep subspace clustering networks. In Advances in Neural Information Processing Systems, pages 23-32, Long Beach, California, United States, December 2017. [page
[19] A. Kalousis, J. Prados, and M. Hilario. Stability of feature selection algorithms. In FEEE International Conference on Data Mining, pages 218-225, Texas, USA, November 2005, Ipage
D
[20] D. P. Kingma and J. L.. Ba. Adam: A method for stochastic optimization. In International Conference for Learning Representations, San Diego, California, USA, May 2015. [page 7
[21] P. Krizek. Feature selection: stability, algorithms, and evaluation. PhD thesis, Czech Technical University, June 2008. [page|] [. Ipage 2
[22] A. P. Kumar and P. Valsala. Feature selection for high dimensional DNA microarray data using
hybrid approaches. Bioinformation, 9(16:824-828 September 2013. [page !
[23] L. Le, A. Patterson, and M. White. Supervised autoencoders: Improving generalization performance with unsupervised regularizers. In Advances Neural Information Processing Systems, pages 107-117, Montreal, Canada, December 2018.
[page] 2] [page
[24] J. Li, K. Cheng, S. Wang, F. Morstatter, R. P. Trevino, J. Tang, and H. Liu. Feature selection: A data perspective. ACM Computing Surveys, 50(6): 1-45, December 2017. [page 3] [page 7
[25] Y. J. Si, G. Zhou, S. Huang, and Chen. FREL: stable feature selection algorithm. IEEE Transactions on Neural Networks and Learning Systems, (6(7))1388-11) July 2015. [page]
[26] Z. Li, Y. Yang, J. Liu, X. Zhou, and H. Lu. Unsupervised feature selection using nonnegative spectral analysis. In AAAI Conference on Artificial Intelligence, pages 1026-1032. Toronto, Ontario, Canada, July 2012. [page]
[27] S. Liang, A. Ma. S. Yang, Y. Wang, and Q. Ma. A review of matched-pairs feature selection methods for gene expression data analysis. Computational and Structural Biotechnology Journal, 16:88-97, February 2018. [page
[28] T. Liu, D. Tao, M. Song, and S. J. Maybank. Algorithm-deppnnent generalization bounds for multi-task learning. IEEE Transactions on Pattern Analysis and Machine Intelligence, 39()): 227-241, February 2017. [page 2 [page 6)
[29] C.-Y. Lu, H. Min, 7.-Q. Zhao, I.. Zhu, D.-S. Huang, and S. Yan. Robust and efficient subspace segmentation via least squares regressio. In European Conference on Computer Vision pages 347-360, Florence, Italy, October 2012. [page]6]
[30] Y. Lu, I. Cohen, X. S. Zhou, and Q. Tian. Feature selection using principal feature analysis. In International Conference Multimedia, pages 301-304, Augsburg, Bavaria, Germany, September 2007. Ipage 3
[31] C. J. Maddison, A. Mnih, and Y. W. Teh. The concrete distribution: A contimuous relaxation of discrete random variables. arXiv: 1611.0072 http://aarthoor//as//61....12222 March 2017. [page 3
[32] B. K. Natarajan. Sparse approximate solutions to linear systems. SIAM Journal on Computing, 24(2):227-234, April 1995. [page 4
[33] S. A. Nene, S. K. Nayar, and H. Murase. Columbia object image library (COIL-20). Technical Report CUCS-005-96, Department of Computer Science, Columbia University, New York, United States, February 1996. Ipage
12

---

[34] S. S.Nouuer,, K. Sechidis, and G. Brown. On the stability of feature selection algorithms. Journal of Machine Learning Research, 18(174):1-54, April 2018. Ipage Ipage
[35] K. Pearson. LIII. On lines and planes of closest fit to systems of points in space. The London, Edinburgh, and Dublin Philoxophical Magazine and Journal of Science, 2(11))559- 572, November 1901. [page]]
[36] C. Peng, Z. Kang, H. Li, and Q. Cheng. Subspace clustering using dog-determinant rank approximation. In the 21th ACM SIGKDD international conference on Knowledge Discovery and Data Mining, pages 925-934, Sydney, Australia, August 2015. [page 6
[37] C. Peng, Z. Kang, and Q Cheng, Subspace clustering via variance regularized ridge regression. In IEEE Conference on Computer Vision and Pattern Recognition, pages 2931-294999 -9900, Honolulu, Hawaii, United States, July 2017. Ipage 6
[38] C. Peng, C. Chen, Z. Kang. J. Li, and Q. Cheng. RES-PCA: A scalable approach to recovering low-rank matrices. In IEEE Conference on Computer Vision and Pattern Recognition, pages 7317-7325, Long Beach, California, United States, June 2019. [page]] I
[39] R. M. Rifkin. Everything old is new again: : fresh look at historical approaches in machine learning. PhD thesis, Massachusetts Institute of Technology, September 2002. Ipage 2
[40] G. Roffo, S. Melzi, and M. Cristani. Infinite feature selection. In International Conference on Computer Vision. pages 4202-4210 Santiago, Chile, December 2015. [page]
[41] D. E. Rumelhart, G. Hinton, and Williams. Learning internal representations by error propagation. ICS Report 8506, Institute for Cognitive Science, University of California, San Diego, La Jolla, California, United States, September 1985. [page [
[42] A. N. Tikhonov. On the stability of inverse problems (in Russian). Doklady Akademii Nauk SSSR, 1955)1995-198, 1943. [page 2
[43] A. N. Tikhonov, A. V. Goncharsky, V. V. Stepanov, and A. G. Yagola. Numerical Methods for the Solution of Ill-Posed Problems. Springer Netherlands, Moscow, Russia, 1st edition, 1995. [page
[44] V. N. Vapnik. An overview of statistical learning theory. IEEE Transactions on Neural Networks, 10(5):988 9998,,99999998 September 1999. [page
[45] X. Wu and Q. Cheng. Fractal autoencoders for feature selection. In AAAI Conference Artificial Intelligence, pages 10370-10378, Virtual Conference, February 2021. [page]
[46] X. Wu, J. Zhang, and F.-Y. Wang. Stability generalization analysis of distributed learning algorithms for big data. JEEE Transactions on Neural Networks and Learning Systems, 31)):: 801-812, March 2020. [page
[47] X. Wu, C. Peng, P. T. Nelson, and Q. Cheng. Random forest- intes-iintegrated analysis in AD and LATE brain transcriptome-wit wide data to identify disease disease-specific gene expression. PLOS One, 16(9):e0256648, September 2021. [page []
[48] H. Xiao, K. Rasul, and R. Vollgraf. Fashion-MNIST: A novel image dataset for benchmarking machine learning algorithms. arXiv: 1708.07747v2, https://arxix:org/ddf// http:///////780077777.77.7 September 2017. [page 7
[49] J. Xie, R. Girshick, and A. Farhadi. Unsupervised deep embedding for clustering analysis. In International Conference on Machine Learning, pages 478-487, New York, United States, June 2016. [page
[50] H. Xu and S. Mannor. Robustness and generalization. Machine Learning, 86(3):391-44 March 2012. [page[]
[51] Y. Yang, H. T. Shen, Z. Ma. Z. Huang, and X. Zhou. -nom regularized discriminative feature selection for unsupervised learning. In International Joint Conference on Artificial Intelligence, pages 1589-1594 Barcelona, Catalonia, Spain, July 2011. [page]] 3
13

---

[52] Z. Zhao and H. Liu. Spectral feature selection for supervised and unsupervised learning. In International Conference on Machine Learning, pages 1151-1157, Corvallis, Oregon, United States, June 2007. [page] 3
14

---

Checklist
For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Supplementary Material. Comparing with the existing NN architectures, our algorithm has two more hyperpa- rameters, namely & and For k, it is subject to the practical problem, which is somewhat similar to the number of clusters in k-means clustering. addition, if a set to O, then the second term of (2) will vanish; in this case, the stability with only the first term of 2 warrants further study.
(2. In fact, for A we can
it the validation set.
(c) Did you discuss any potential negative societal impacts of your work? [No] Our paper is about feature selection, which is a dimensionality reduction approach. To our best knowledge, we do not know or expect any ethical issues and negative societal impacts of the proposed technique in this paper.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes] We have read and ensured.
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section 5 in the main text. And more details also can be found in Supplementary Material.
(b) Did you include complete proofs of all theoretical results? [Yes] See Supplementary Material.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed reproduce the main ex- perimental results (either in the supplemental material or as a URL)? [Yes] See Supplementary Material and the link https://gituub.com//innt wwt...ooowiiiiigg---UUSSS..
(b) Did you specify all the training details (c.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section in the main text and Section 4 in Supplementary Material.
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes] We provided the random seeds used in experiments of our paper, see Section 4 in Supplementary Material.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [No] The methods discussed in our paper do require too much computational resources. For example, Intel Core i5 and 16GB RAM, are sufficient to run our algorithm, so we do not specifically explain the computing resources used in our paper.
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] See Section 6 in the main text and Section 3 in Supplementary Material.
(b) Did you mention the license of the assets? [No] We were unable to find the license for the dataset we used, but we provided/cited the web links or related papers all datasets
we used. See Section 6 in the main text and Section in Supplementary Material.
(c) Did you include any new assets either in the supplemental material or as a URL? [Yes] We provided our main codes related to the main experiments in our paper.
(d) Did you discuss whether and how consent using/curating? [No] The datasets used in our paper are public datasets which are widely used by researchers in the machine learning field to verify the performance of their proposed algorithms. The datasets are freely accessible.
obtained from people whose data you're
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [No] The datasets used in our paper not contain personally identifiable information offensive content.
5. If you used crowdsourcing conducted research with human subjects...
15

---

(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
16


Reviews:
[{"review_id": "rx5nzejovGn", "reviewer": "Reviewer_4y4c", "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.", "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": "-Originality: The paper seems novel.\n-Quality: Quality could be significantly improved. (see below)\n-Clarity: Clarity is significantly below the acceptable level. (see below)\n-Significance: Low (see below)\n\nI think the paper has two significant flaws:\n\n1) \n- 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.\n- Related to this point, how do the authors explain the huge performance jump for AEFS between tasks 1-5 and tasks 6-10?\n- 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.\n\n2) Theoretical development is not careful enough, making it very hard to follow the paper.\n\na. Notation is inconsistent and cumbersome. I point out a few examples here:\n- line 116: The definition of S^i is not clear because the inputs are S, i, and the new value x_i’.\n- 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.\n- line 172: L^{\\text selec} is not defined.\n- line 119: \\ell is defined on \\cal{X}x\\cal{X}. But, A_S is a function.\n- x’ denotes a (different) sample whereas X’ denotes matrix transposition. Would the authors consider a different notation for either one?\n\nb. I have similar concerns about the theoretical results. I point out a few examples here:\n- (Lemma C) \\ell^{score} and \\ell_{selec} have two arguments. Def. D considers functions of a single argument.\n- (Lemma C) Def. D requires the inequality to hold for any arguments in its domain, but Lemma C specifies these arguments.\n- (Lemma D) How Prop. 1 is used in Lemma D is not clear at all.\n- (Lemma E) In the proof, please add more details showing the second equality involving limits.\n\nc. 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?\n\n\n**UPDATE:** After a long discussion with the authors, I decided to increase my score from 4 to 5.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "~8 hours"}, "extra_text": {}}, {"review_id": "64ZYsRE3ZMn", "reviewer": "Reviewer_LsED", "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. ", "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": "Originality: yes, to be the best of my knowledge, the methods seem novel!\n\nQuality: 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)\n\n --- 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:\n\na) is the source of instability the non-continuous max_k operation? this to me seems like the major issue? \n\nb) 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? \n\nc) 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. \n\nd) I recognize that this is very hard, but is there any sense of the existence of lower bounds for the algorithmic stability? \n\ne) 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\n\n---- 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.\n\n---- in addition to k, \\lambda_1, the bottleneck dimension d must be chosen. How sensitive is the method to this?\n\n----- 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. \n\nClarity: the writing is reasonable although there is much room for improvement as I outline:\n-- \"To address these issues, we propose a novel unsupervised feature selection algorithm with a proven\n35 algorithmic stability guarantee in this paper.\" --> sounds less awkward if \"in this paper\" appears after the comma\n-- \"It comprises a NN\" -> it comprises of a NN\n-- \"evaluate the representation ability of the highly scored features locally.\" -> \"locally evaluate the representation....\"\n-- \"revealed by theoretical analysis and the stability of the selected features by our algorithm\" -> sounds awkward. rephrase.\n-- lines 54--60, remove the numbers as they make the structure awkward. \n-- \"be linked with the generalization\" -> linked with generalization\n-- \"proves the stability\" -> prove stability\n-- \"the role of the regularization\" -> \"the role of regularization\"\n-- Line 134: do not start a sentence with a symbol.\n--- 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? \n-- \"Our new algorithm is to use NN for the optimization of\" -> awkward phrase\n-- What is the difference between X(\\Phi(W)) and X\\Phi(W)? seems like both are used and this seems confusing.\n-- \"we obtain the feature selector and use it to make feature selection on new samples during testing\" ->> seems ambiguous. please be more precise here.\n-- \"manifested in our experiments.\" -> \"demonstrated in our experiments\"\n-- \"There has been neither a clue about the role of the regulation in the uniform stability.\" -> grammatically incorrect with spelling error\n--- line 155-159: could appear right after equation (2)?\n--- line 178: missing a star below \\Phi\n--- 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.\n--- Line 240, the weights are sampled between two very strange numbers. Is there a reason for this?\n--- \"We set \u0015\\lambda to be 1/2^7\" -> this appears very small?\n-- \"the uniform stability\" -> remove the\n--- \"meanwhile, the selected features by the proposed algorithm show comparable performance to the original features.\" -> use additionally instead of meanwhile.\n--- \"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\"\n\n\nSignificance: Yes, I think the methodology could be interesting given its superior performance empirically over other methods and favorable theoretical properties. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "53KKrlaYj4U", "reviewer": "Reviewer_Fihd", "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.", "questions": "", "limitations": "", "rating": 7, "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": "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. \n-P1L10 show our-> show that our\n-P1L32 none -> no\n-P2L44 an extra space appears before the word “It”\n-Notation: You are using X’ from transpose but then you use x’ again to denote something else. \nP3L131 the sentence is poorly written, do you mean: The goal of feature selection is…?\nP7 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? \nThe 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? \nWhat is the batch size used?\nHow are the parameters of Extremely randomized trees tuned?\nThe relation between the method and Agnos-S (and perhaps other methods) should be clearly explained in a related work section.\n Was the linear regression (used for evaluating the MSE) also trained on the train and evaluated on the test?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10-20"}, "extra_text": {}}]

Author rebuttal:

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)