{'fraction_non_alphanumeric': 0.033298008812538346, 'fraction_numerical': 0.015254615427519661, 'mean_word_length': 4.8184325815349665, 'pattern_counts': {'":': 4, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Where to Pay Attention in Sparse Training for Feature Selection?

A new line of research for feature selection based on neural networks has recently emerged. Despite its superiority to classical methods, it requires many training iterations to converge and detect informative features. The computational time becomes prohibitively long for datasets with a large number of samples or a very high dimensional feature space. In this paper, we present a new efficient unsupervised method for feature selection based on sparse autoencoders. In particular, we propose a new sparse training algorithm that optimizes a model's sparse topology during training to pay attention to informative features quickly. The attention-based adaptation of the sparse topology enables fast detection of informative features after a few training iterations. We performed extensive experiments on 10 datasets of different types, including image, speech, text, artificial, and biological. They cover a wide range of characteristics, such as low and high-dimensional feature spaces, and few and large training samples. Our proposed approach outperforms the state-of-the-art methods in terms of selecting informative features while reducing training iterations and computational costs substantially. Moreover, the experiments show the robustness of our method in extremely noisy environments.


Introduction
Feature selection plays a crucial role in data mining and machine learning tasks with the explosion in the size and dimensionality of real-world data [68,10,30,44,23]. It aims to efficiently select a subset of the features that are most informative and remove the irrelevant or redundant ones. It is useful for alleviating the curse of dimensionality, interpretability of model-driven decisions, generalization of downstream tasks, reducing the prohibitive memory and computational costs, and avoiding the expensive costs of collecting the full set of features as in biological studies [11,38,31,52].
Many methods have been proposed for feature selection in supervised, semi-supervised, and unsupervised settings [75,10,60,51,19,1]. Recently, using neural networks for feature selection has received increasing attention due to its power to learn non-linear dependencies among input features [39]. One limitation of current neural network-based methods is that they are computationally expensive. The computational costs result from training dense models for many training iterations until informative features are recognized. The costs increase for datasets with a very large number of training samples or high dimensional feature space. This limitation is recently addressed in [4] by utilizing sparse networks with dynamic sparsity for feature selection. An autoencoder is trained with the sparse training algorithm SET [54], which explores different sparse topologies during training by dropping a portion of the connections and growing the same portion randomly. The importance of an input feature is estimated after convergence based on its outgoing sparse connections. Training sparse networks from scratch decreases memory and computational costs compared to previous dense-based methods. Yet, the random exploration of sparse topologies requires many training iterations to identify informative features.
In this paper, we propose an efficient unsupervised method for feature selection. We introduce a new sparse training algorithm for autoencoders that quickly detects the informative input features. Specifically, we optimize the sparse topology to learn Where to pay Attention during Sparse Training. We named our method WAST. WAST exploits the information from the reconstruction loss and the weights of sparse connections to guide the topological search. It redistributes the sparse connections to spot informative features quickly. We evaluate our proposed approach on ten datasets from various domains, including image, speech, text, artificial, and biological. Through extensive experiments, we find that WAST identifies the informative features after a few training iterations and outperforms state-of-the-art unsupervised feature selection methods. Our main contributions are: • We propose a new efficient unsupervised method for feature selection, named WAST. WAST optimizes the sparse topology of an autoencoder to detect the informative features quickly. • We perform extensive experiments on 10 benchmarks that cover various types and characteristics. Experimental results show the effectiveness of our method over the state-of-the-art methods in terms of selecting the informative features. • WAST reduces the computational time compared to neural network-based methods substantially by reducing training iterations and employing highly sparse neural networks. • We illustrate the robustness of our method in extremely noisy environments and its effectiveness for datasets with very high dimensional feature space and a few training samples.
2 Related Work

Feature Selection
Many feature selection methods were introduced for the supervised, semi-supervised, and unsupervised settings depending on whether the data is labeled, partially labeled, or unlabeled, respectively [75,10,60,1]. Typically, feature selection methods are divided into three categories: filter, wrapper, and embedded methods. Filter methods are independent of the learning algorithms. They use ranking techniques for providing scores to the features, such as Laplacian score [26]. Despite being fast, they do not consider the relationship between the features, which may result in the selection of redundant features [11]. In the supervised setting, filter methods consider the relation between the feature and the class label, such as fisher_score [22], CIEF [41], and ICAP [33]. Wrapper methods exploit the performance of a predictive model to evaluate the quality of a subset of the features [70,12,74]. They are more effective than filter methods, yet they are computationally expensive [39]. Embedded methods incorporate feature selection into the learning phase of another algorithm. Multi-Cluster Feature Selection (MCFS) [9] uses regularization to select the best features that keep the multi-cluster structure of the data. Unsupervised Discriminative Feature Selection (UDFS) [72] uses l 2,1 regularization and discriminative analysis to select the most discriminative features. Similarly, in the supervised setting, RFS [56] and L1_L21 [45] exploit l 2,1 -norm to introduce feature sparsity.
Another direction under the embedded category has recently emerged. It uses neural networks to perform feature selection by learning the non-linear dependencies among input features [40].  Figure 1: An overview of our proposed method WAST for unsupervised feature selection. A sparse autoencoder is initialized with uniformly distributed sparse connections. During sparse training, the connections are redistributed in the most important neurons at iteration t during the "drop-and-grow" cycle. After convergence, neurons with the highest importance are selected as the most informative features.
is randomly regrown. Few works based on multi-layer perceptron networks are proposed for the supervised setting [37,61,71]. In section 4, we denote non Neural Network-based (NN-based) methods as classical methods.

Sparse Training
Sparse training with dynamic sparsity, also known as Dynamic Sparse Training (DST), is a recent research direction that aims at accelerating the training of neural networks without sacrificing performance [27, 54,47]. A neural network is initialized with a random sparse topology from scratch. The sparse topology (connectivity) and the weights are jointly optimized during training. During training, the sparse topology is changed periodically through a drop-and-grow cycle, where a fraction of the parameters are dropped, and the same portion is regrown among different neurons. An update schedule determines the frequency of topology updates. Many works have been proposed, focusing on improving the performance of sparse training for supervised image classification tasks by introducing different criteria for connection regrowth [20,34,59,49,73,50]. DST demonstrated its success in other fields as well, such as continual learning [62], feature selection [4], ensembling [46], federated learning [77,8], adversarial training [57], and deep reinforcement learning [63].
3 Where to pay Attention in Sparse Training (WAST)?
Problem Formulation. Let D be a dataset with samples {x (j) } n 1 , where x (j) ∈ R m , and m and n are the number of features and samples, respectively. The goal is to select a subset of the features of a size K in an unsupervised manner, which is most representative of the whole feature space m.
WAST is a new sparse training method for neural network-based unsupervised feature selection. The basic idea of WAST is to pay attention to input features based on their estimated importance during training to detect the most informative features quickly. An overview of WAST is shown in Figure  1. We use a sparse autoencoder with a single hidden layer of h neurons. Let f W be an autoencoder model parameterized by sparse weights W ={W (1) , W (2) }. The network is initialized with a certain sparsity level s = 1 − W (1) 0 m×h , where . 0 is the L 0 norm. The sparsity level is kept fixed during training. Initially, the sparse weights are uniformly distributed on the neurons. During training, besides weights optimization, the sparse topology is optimized such that the sparse connections are gradually redistributed on the most informative features. To achieve this goal, we propose new criteria to update the sparse topology and a new update schedule, as we will explain next.
Training. An autoencoder model is trained to minimize the reconstruction loss. We use mean squared error to measure the loss between an input sample x and the reconstructed onex as follows: , and σ is a non-linear activation function. After each weight update using a batch of the data, we adapt the sparse topology. The effect of the update schedule on performance is shown in Appendix E. The sparse topology is updated through a drop-and-grow cycle.
ki | ∀i ∈ {1, ..., m} 12: , where the connections are randomly regrown, we optimize the topology to pay fast attention to informative features during training. To this end, we measure the importance of each neuron in the input and output layers by leveraging the information available during training. The importance of a neuron is estimated by its impact on the reconstructed loss and the magnitude of its connected weights.
Specifically, we measure how sensitive the reconstruction loss L is to changes in the reconstructed outputx. The first-order approximation for the change in loss with respect to a small perturbation δ = {δ i } in the outputx = {x i } can be written as a sum of its individual components as follows: where ∂L ∂xi is the gradient of the loss with respect to the output neuronx i . We define the importance of a neuron i in the output layer at training iteration t as: where |W (2) ji | is the magnitude of the incoming connection from neuron j to neuron i and λ is a hyperparameter coefficient to balance the two components (See Appendix A). The same criterion is applied for the input neurons (I is the set of remaining weights after the drop phase, and r is the number of regrown connections based on the fraction α. We consider the neurons in the hidden layer to be equally important. During the drop phase, the importance of a connection w in the input (output) layer is estimated by its magnitude and the importance of its connected input (output) neuron (I (t) i ) as follows: where I    [42]) for unsupervised feature selection. On top of that, we include comparisons with seven state-of-the-art supervised feature selection methods. Although the latter is not the focus of this paper and not a typical comparison in the literature, we prefer to show that WAST performs competitively also with the supervised methods while being computationally efficient and applicable for cases where labels are not available or expensive to collect.

Datasets
We evaluate our method on 10 publicly available datasets, including image, speech, text, time series, biological, and artificial data. They have a variety of characteristics, such as low and high-dimensional features and a small and large number of training samples. Details are in Table 1.

Experimental Settings
Evaluation Metrics. An efficient feature selection method should have high learning accuracy with less memory and computational costs [10]. Hence, we evaluate multiple metrics. (1) Classification Accuracy: It is typically evaluated by a machine learning model [10]. We trained a classifier using the K selected features by the studied methods. Here, we use one of the most popular classifiers, support vector machines (SVM) [14]. Other classifiers could be used. Yet, we choose to use a non-NN-based classifier for evaluation to avoid any biased advantages towards the NN-based baselines over the others. We studied the performance of 6 different values of the number of selected features (K). We report the average accuracy of the test data over 5 seeds.   [42], LassoNet [37], and STG [71], we used the official codes with MIT license 3,4,5 . For classical baselines, we used the Scikit-Feature library with GNU General Public license [39] 6 . NN-based and classical methods are trained on Nvidia GPUs and CPUs, respectively. We consider a 12 hours limit on the running time of each experiment. Experiments that exceed this limit are not considered.
Implementation Details. For all NN-based methods except CAE [5], we use a single hidden layer of 200 neurons. The architecture of CAE consists of two layers. The size of the hidden layers is dependent on the chosen K; [K, 3 2 K]. For WAST and QS, we use a sparsity level of 0.8. Following [4], we report the accuracy of NN-based baselines after 100 epochs unless stated otherwise. Note that some baselines reported a higher number of epochs (e.g., CAE [5] uses 200 epochs for some datasets). Yet, we keep 100 epochs for all cases for a fair comparison. For WAST, we train the model for 10 epochs. Following [4], we add a Gaussian noise with a factor of 0.2 to the input in WAST and QS [4]. Details of the hyperparameters are in Appendix A.1.

Results
Accuracy. Table 2 shows the classification accuracy of the studied datasets. Here, we report the challenging case where a few best informative features have to be selected. We use a K of 50 for all datasets except for Madelon, where a K of 20 is used as the remaining 480 features are pure noise. Experiments with various values for K ∈ {25, 50, 75, 100, 150, 200} can be found in Appendix B, with a summary provided next.
Unsupervised NN-based methods outperform the classical ones on all datasets except one, where the performance difference is marginal. WAST outperforms unsupervised NN-based methods on  all datasets except MNIST and Fashion MNIST, where CAE is the best performer. It is worth emphasizing that the superior performance of WAST is achieved with a 90% reduction in the number of training iterations. Supervised baselines outperform the classical supervised ones in 6 cases. Interestingly, WAST achieves a competitive performance to the supervised baselines. It outperforms the best-supervised performer in 5 cases.
Memory and Computational Costs. Table 3 shows the memory and computational costs consumed by each unsupervised NN-based method. The high memory and computational costs are caused by the high number of training samples, as in MNIST, or the high-dimensional feature space, as in GLA. Training a sparse model from scratch, as in WAST and QS, reduces these costs substantially. QS reduces the computational cost by 80%. Interestingly, besides the reduction resulting from using sparse neural networks, WAST reduces the computational cost further to 98% due to the fast identification of the informative features. Both WAST and QS reduce the network size by 80%.
The network size of CAE is dependent on the target value of K. This has two limitations: training the model for every target K and the increase of the memory and computational costs with higher values for K. On the other hand, WAST derives the importance of each feature with a single training run independently of the target K. This is illustrated in Figure 2. The figure shows the accumulated FLOPs for all datasets except Madelon at each value of the studied K.
Overall Performance. To give a holistic view of the performance of each method across all dimensions (accuracy, memory cost, and computational cost) on all datasets and all studied values of K, we calculate the performance in each case. Figure 3 illustrates the normalized performance using min-max scaling for all cases. The "score" metric represents the number of times a method is the best performer in terms of accuracy. Details are provided in Appendix A.2. CAE has a higher score than AEFS, while the former is the best only for image datasets with a large number of samples (i.e., MNIST and Fashion MNIST), as shown in Figure 4. AEFS has the highest memory and computational costs. QS improves the memory and computational costs but has a lower score. WAST has the highest score and spans more dataset types with different characteristics (e.g., high dimensional data) than the baselines (Figure 4). The performance gain is accompanied by a significant improvement in memory and computational efficiency. Detailed results are provided in Appendix B. (c) COIL-20.

Effect of Fast Attention During Training
To analyze the impact of attention to the informative features in WAST during training, we study the learning behavior of all unsupervised NN-based methods on the test data for the first 10 epochs. Since CAE has a parameter that is dependent on the max number of epochs, we performed ten separate runs and varied the max number of epochs each time. Figure 5 shows the accuracy using K of 50 for all datasets except Madelon, where K of 20 is used. The analysis reveals the following findings: (1) Robustness to noisy environments: The results on Madelon illustrate the robustness of WAST against the noisy features (480 out of 500). The figure shows the performance gap between WAST and the baseline methods starting from epoch 1. After 10 epochs, WAST outperforms the second-best performer by 22%. More experiments on noisy enviroments can be found in Appendix G.
(2) Performance on datasets with a large number of samples: WAST outperforms CAE by 3.6% and 1.6% on MNIST and FashionMNIST, respectively, although CAE was the best performer on these datasets after training it for a larger number of epochs (Table 2). (3) Consistency across different dataset types and characteristics: We observe that some baselines achieve high performance in some domains while being worse in others. WAST has the highest consistency on different dataset types and characteristics, outperforming all baselines after 10 epochs (Appendix C). (4) Stability: WAST is more stable at the early stage of the training. This is represented by the standard deviation across different training runs (shaded region).   epoch. On the other hand, the random growth of the connections in QS requires more training epochs. The effect of increasing the frequency of topological exploration in QS is studied in Appendix F.

Ablation Study
We performed an ablation study to assess the contribution of each component in the proposed criteria of neuron and connection importance in the performance of WAST.
Neuron Importance. (#1) "w/o | ∂L ∂x |": Using only the magnitude of connected weights to determine the importance of a neuron (i.e., λ = 0), (#2) "w/o |W|": Using only the sensitivity of the neuron to the change in the loss (i.e., λ = 1), and (#3) "w/o momentum": The importance of a neuron is based only on the current estimate of its sensitivity to the loss and currently connected weights.
Connection Importance. (#4) "w/o I i ": The importance of a connection is estimated by its magnitude without considering the importance of its connected neuron I i .
We performed this analysis on datasets of different types. The results are summarized in Table 4. We observe that removing the sensitivity of a neuron to the loss (#1) has the biggest effect on performance. It has the highest impact on noisy environments, where it reduces the performance by 27.77% on Madelon. On the other datasets, it results in a 0.53 − 4.93% reduction in the performance. Excluding the magnitude of the weights (#2) affects mainly the datasets with few training samples (e.g., SMK). Neglecting the neuron importance in the previous training iterations (#3) reduces the performance by 0.09 − 5.79%. Aligned with many prior works [20, 54,27], we find that the weight magnitude is an effective metric for estimating the connection importance (#4). Moreover, our results show that enhancing it with the importance of its connected neuron improves the performance even further on some datasets without diminishing it on the others. (c) HAR. Figure 7: The performance of WAST using different sparsity levels for the autoencoder model. The test accuracy is reported using K of 50 except on Madelon, where K = 20.

Effect of the Sparsity Level
We further study the effect of the sparsity level of the auto-encoder model on the performance of WAST. We evaluated 5 different sparsity levels {20%, 40%, 60%, 80%, 90%}. All other settings are the same as the ones stated in Appendix A. Figure 7 illustrates the classification accuracy using K = 20 for Madelon and K=50 for other datasets. We observe the performance of WAST is robust to the sparsity level. Yet, we mostly care about the performance at high sparsity levels, as the goal is to achieve high performance at a low computational cost.

Discussion
Conclusion. In this paper, we propose WAST, a new efficient neural network-based method for unsupervised feature selection. We train a sparse autoencoder from scratch and optimize the sparse topology during training to detect the informative features quickly. We performed extensive experiments in which we evaluated 55 cases on various datasets and different values of the number of selected features. WAST achieves the best performance on 19 cases, while the second-best unsupervised performer has a score of 11 cases. More interestingly, the superior performance is achieved with a few training iterations. WAST reduces the memory and computational costs by 80% and 98%, respectively. Moreover, we show the robustness of WAST towards very noisy environments, outperforming the state-of-the-art methods by 22% with limited training iterations. Finally, we show that WAST performs competitively with supervised-based methods, outperforming them on image datasets. This demonstrates the promise of adapting WAST in the supervised setting and motivates new sparse training algorithms for supervised and unsupervised feature selection.
Limitations. This work is a step toward exploiting the power of neural networks for feature selection in a computationally efficient manner. Besides the improvement in the accuracy of selecting the informative feature, fast attention to the important features during training reduces the number of training iterations substantially. Yet, like most sparse training methods in the literature, this proof-ofconcept does not fully utilize the memory and computational advantages of sparse neural networks. This is due to the lack of hardware support for sparsity and the higher focus of the community on the algorithmic side [27]. Nevertheless, there is recent growing attention to hardware and software support for sparsity [28, 76, 66, 48, 15, 3, 13] (See Appendix H for discussion). This enables the pure sparse implementation of the method in the future.
Societal Impacts. With the emergence of big data, systems that can quickly select informative features and remove redundant ones become crucial. Besides the performance gain that could be achieved in the downstream tasks by removing irrelevant features, reducing the number of features improves memory and computational efficiency significantly. This enables providing energy-efficient systems. Moreover, it is useful for improving the interpretability of model-driven decisions. The unsupervised selection of the informative features is effective in cases where labeled data is limited or very expensive to collect. We do not expect that there is a negative societal impact.

A.1 Implementation Details
For all datasets, we used standard normalization that scales the features to have zero mean and standard deviation of one. The architecture of the autoencoder consists of one hidden layer with sigmoid activation. A linear activation is used for the output layer. We use a hidden layer of 200 neurons for all datasets. We trained each dataset for 10 epochs using stochastic gradient descent with a momentum of 0.9 and a batch size of 128. We used a learning rate of 0.1 for all datasets except for the datasets with very few samples. We used a learning rate of 0.01 and 0.001 for SMK and GLA, respectively. For sparse-based methods, WAST and QS, we used a sparsity level s of 0.8. The factor of dropped and regrown connections, α, in the two methods is 0.3. We used λ of 0.4 for all datasets of type image, and λ of 0.9 for all other types except the biological data. For SMK and GLA, we used λ of 0.01 and 0.001, respectively. The selection of the value of λ is guided by the magnitude of the gradient of the loss with respect to the reconstructed sample compared to the magnitude of the weights. This is illustrated in Figure 8. We use λ to control the balance between the two components of the neuron importance in Equation 3. For instance, for biological data (SMK and GLA), where the absolute gradient is higher than the average sum of absolute weights connected to a neuron, we use a small value for λ. The other hyperparameters are selected using a random search. For Madelon, we evaluate the performance of K = 20. For all other datasets, we test 6 different values K ∈ {25, 50, 75, 100, 150, 200}.

A.2 Evaluation Metrics
Accuracy. To assess how informative are the selected features by each method, we train a support vector machine classifier on the selected features and report the classification accuracy.
Score. To summarize the results for all datasets and various values of the selected features K, we calculate a score for each studied method. The score of a method increases by one when it is the best performer in terms of classification accuracy for a certain dataset and a certain value of K.
Network size (#params). To estimate the memory cost of a network, the network size is calculated by the summation of the number of connections allocated in its layers as follows:  where W (l) is the weights in layer l, . 0 is the standard L 0 norm, and L is the number of layers in the model. For sparse neural networks, W (l) 0 is controlled by the defined sparsity level for the model. FLOPs is the typical used metric in the literature to compare the computational cost of a sparse model against its dense counterpart [27]. The main motivation is that current sparse training methods are prototyped using masks over dense weights to simulate sparsity [27]. This is because most deep learning specialized hardware is optimized for dense matrix operations. Therefore, the running time using these prototypes would not reflect the actual gain in memory and speed using a truly sparse network. See Appendix H for further discussion.
Performance. To assess the efficiency of a method across different dimensions (accuracy, memory cost, and computational cost) on various types of datasets with different characteristics, we include a comparison that gives a holistic view of all datasets and the studied values for K. We study 55 cases ((9 datasets × 6 values for K)+ Madelon dataset). We calculate the total score for all cases and memory and computational costs. Since the memory and computational costs for CAE [5] are dependent on the value of K, we report the average costs across the 6 studied values. The memory and computational efficiency are equivalent to (1− cost). Normalized values, using min-max scaling, are illustrated in Figure 3.

B Additional Experiments
In this appendix, we evaluate the accuracy of the studied unsupervised and supervised methods for various values of the selected features K ∈ {25, 50, 75, 100, 150, 200}.
Tables 5 and 6 show the accuracy in each case. Consistent with the observations for K of 50 in Section 4.4, we find that unsupervised neural network-based methods outperform the classical ones in most cases. CAE is the best performer for image datasets with a large number of samples (i.e., MNIST and Fashion MNIST) for all values of K except one. WAST is the best performer in 19 cases, while the second-best performer is the best in 11 cases.
Similarly, the supervised neural network-based methods outperform the classical supervised methods in most cases. Yet, for text and high dimensional datasets, classical methods are competitive with the NN-based ones, outperforming them in 5 values for K on SMK and PCMAC.
Interestingly, WAST outperforms the best supervised performer on the image datasets in 14 cases of 24. On the other types of datasets, supervised methods achieve higher performance in most cases. Figure 9 summarizes the performance of unsupervised methods across various dimensions. We report the score (i.e., how many times the method is the best performer) on different values of K (Figure  9a), the memory cost estimated by the number of required network parameters (Figure 9b), and the computational cost (Figure 9c). Since the network architecture is dependent on K in CAE [5], we Table 5: Classification accuracy (%) using unsupervised and supervised feature selection methods for different K selected features. The best performer from the unsupervised methods is in bold font, while the best performer from the supervised methods is in blue.

C Effect of Fast Attention During Training
We studied the performance of unsupervised NN-based methods during the first 10 epochs in Section 5.1. In this appendix, we report the accuracy after performing the 10 epochs.
As illustrated in Table 7, on different dataset types (artificial, image, speech, time series, text, and biological) and different characteristics (high/low dimensional features and few-shot/large data), WAST consistently outperforms other NN-based unsupervised methods. Table 6: Classification accuracy (%) using unsupervised and supervised feature selection methods for different K selected features. The best performer from the unsupervised methods is indicated in bold font, while the best performer from the supervised methods is indicated in blue color.

D Performance Evaluation on Music Dataset
In this appendix, we perform additional experiments on a recent music dataset, Free Music Archive (FMA) [16,17]. FMA includes a collection of 106574 audio tracks with artist and album information categorized into 161 genres. We use FMA-small, which consists of 6400 training samples and 800 testing samples with 140 pre-extracted features. We focus on the genre classification task that categorizes the data into eight classes. We use the same setting defined in Appendix A. For WAST, we use λ of 0.4. We evaluate the classification accuracy of unsupervised NN-based methods using K = {25, 50, 75}.
The results are reported in Table 8. Consistent with our results on other benchmarks, WAST outperforms other unsupervised NN-based methods in two cases out of three, with a marginal performance difference in the third case. The performance gain is accompanied by a reduction of the number of epochs by 90%.

E Effect of the Frequency of Topology Update
In this section, we analyze the effect of the schedule used to update the sparse topology. In WAST, the topology is updated after each weight update using a batch of the data. We named this schedule "batch update". We compare this schedule with the one used in the QS baseline, in which the sparse topology is updated after each training epoch (i.e., one pass on the whole data). We denote this schedule as "epoch update".   Updating the topology more frequently increases the speed of detecting the informative features. Table 9 shows the accuracy on datasets from different types. Updating the topology more frequently by the batch update schedule improves the performance in most of the cases and helps in finding the informative features quicker (Appendix F). The accuracy increases by 0.52 − 3.5% in the studied cases.

F Visualizing the Effect of the Frequency of Topology Update
In this appendix, we visualize the effect of different update schedules of the sparse topology. We analyzed two schedules: "epoch update" and "batch update" (Appendix E). We performed this analysis on MNIST. Figure 10 illustrates the effect of different topological update schedules in WAST and QS. The less frequent update of the topology decreases the speed of identifying the informative features. After 1 epoch, the distribution of connections by QS is still almost uniform across different input neurons (Figure 10a). On the other hand, WAST starts to identify the important neurons (Figure 10c). Updating the topology after each batch update increases the speed of identification in the random exploration setting (Figure 10b) and enables very fast detection in WAST after 1 epoch (Figure 10d).

G Robustness to Noisy Environments
Our experiments on the Madelon dataset illustrate the robustness of WAST to noisy features. In this appendix, we study the robustness of the unsupervised NN-based methods on noisy samples. To this end, we created noisy versions of the datasets by adding Gaussian noise with zero mean to the training data. To assess the robustness of different noise levels, we evaluated 4 different values of standard deviation {0.2, 0.4, 0.6, 0.8}. We performed this analysis on datasets of different types. We use the same experimental setting described in Section 4.3 and Appendix A. Figure 11 illustrates the classification accuracy using K = 50. We observe that across different dataset types, methods that are based on sparse models (i.e., WAST and QS) are more robust to noise. As expected, the accuracy decreases when the level of noise increases in all methods. Yet, sparse-based methods have the least decrease. Moreover, WAST outperforms QS in all cases.

H Advance in Sparsity
Most of the efforts in previous years are devoted to the algorithmic side of sparse training. The aim is to achieve the same or higher performance than the dense models with highly sparse counterparts, as discussed in Section 2.2.
Existing sparse training methods in the literature simulate sparsity using masks over dense weights since most deep learning specialized hardware is optimized for dense matrix operations. Yet, recently, research on the software and hardware that support sparsity has received growing attention. NVIDIA (e) SMK. Figure 11: The performance of different methods on noisy datasets where Gaussian noise is added. We assess the performance on different noise levels by varying the standard deviation of the Gaussian noise. The test accuracy is reported using K of 50.
released NVIDIA A100, which supports a 50% fixed sparsity level [76], and many other efforts on the hardware side are proposed [66,3,13,43]. On the software side, libraries that support truly sparse implementations have been started for supervised learning [48,15]. With a joint community effort in the algorithmic, software, and hardware directions, we would be able to actually provide faster, memory-efficient, and energy-efficient deep neural networks. Further discussion can be found in [29,53].