Many datasets have far more input variables than useful ones. Gene-expression arrays and sensor streams are typical: most variables are noise, and each one costs money or compute to measure. Feature selection means picking the few inputs a model actually needs. The cleanest statistical tool for this is row-sparse regularization. It penalizes the sum of the lengths of the rows of the first weight matrix (the $\ell_{2,1}$ norm), and that penalty pushes whole rows, and therefore whole input features, to exactly zero. Existing neural versions of this idea train a fully dense network and only discover at the end which features were unnecessary. Sparse-to-sparse training (also called dynamic sparse training) keeps a network sparse from the first step, and periodically deletes weak connections while regrowing new ones. It avoids the dense cost, but it chooses which connections to regrow with heuristics that have no link to any feature-selection objective.
This note proposes making the unit of sparse training an entire input row and choosing which rows to regrow with the optimality test of group lasso. For a row that is currently absent, the question "would group lasso switch this feature on?" has an exact answer: switch it on if the length of that row's loss gradient exceeds the penalty weight. We use that test, plus an exploration bonus for features rarely tried, as the grow rule. Shrinking rows until they reach zero serves as the drop rule. The network then only ever reads and updates a small, changing working set of features. When no absent feature fails the test, training has reached a stationary point of the full row-penalized objective, not merely of a heuristic. Put simply: treat the sparse-training mask as the active set of a group-lasso solver, and you get feature selection that never trains a dense model, has a checkable stopping condition, and runs as a small dense matrix multiply.
Core Claim
Row-level drop-and-grow, guided by group-lasso screening, selects features that are at least as good as dense $\ell_{2,1}$ training, and it touches a small fraction of the input features at each step. It should also beat element-wise sparse training for feature selection on noisy, high-dimensional benchmarks. The mechanism predicts one specific advantage: fewer features eliminated too early. Features whose usefulness appears only after other features have been learned should survive better, because the screening test is re-run as the representation changes, and an exploration bonus keeps rarely-tried rows in the candidate pool.
The setup is as follows. Let $W \in \mathbb{R}^{d \times m}$ be the first-layer weights of an autoencoder or classifier, with row $W_i$ attached to input feature $i$. Let $\mathcal{L}$ be the training loss and let $\mathcal{A}$ be the active set of rows, with $|\mathcal{A}| \le k'$ for a feature budget $k'$. We minimize
$$\min_{W}\; \mathcal{L}(W) + \lambda \sum_{i=1}^{d} \|W_i\|_2 \quad \text{subject to } W_i = 0 \text{ for } i \notin \mathcal{A},$$
where $\lambda$ is the penalty weight. A row outside $\mathcal{A}$ is optimal at zero exactly when $\|G_i\|_2 \le \lambda$, where $G_i$ is the gradient of $\mathcal{L}$ with respect to $W_i$; this is the standard subgradient condition for the group norm. At each mask update we score a candidate pool of inactive rows by
$$S_i^t = \|G_i^t\|_2 - \lambda + c\,\frac{\ln t}{N_i^t + \epsilon},$$
where $t$ is the update index, $N_i^t$ counts how many past updates feature $i$ was active, and $c$ sets the strength of exploration. We grow the highest-scoring rows with positive score. Active rows receive a proximal group-shrinkage step after each gradient step. A row that reaches zero is dropped, and if the budget is exceeded, the shortest rows are dropped first.
The exploration term is borrowed directly from Dynamic Sparse Training via Balancing the Exploration-Exploitation Trade-off. That paper adds an upper-confidence bonus to weight-level regrowth and reports up to 8.2% over RigL and MEST on ImageNet. Our change is to lift the bonus to feature level and pair it with the group-lasso test rather than the raw gradient magnitude. Deeper layers can stay sparse under any existing scheme. We use the constant-fan-in design of Dynamic Sparse Training with Structured Sparsity, so the whole network is sparse from initialization.
Relation to Prior Work
The closest prior work is Where to Pay Attention in Sparse Training for Feature Selection? (WAST). WAST trains a sparse autoencoder from a random 20%-dense mask, prunes individual low-magnitude weights, and regrows connections preferentially on input neurons with a high combined gradient-plus-magnitude importance score. It reports a 98% reduction in floating-point operations relative to dense networks and a 22% relative accuracy gain on Madelon. It motivates this proposal because it shows sparse training can find informative inputs quickly. It differs from our method in three ways. First, WAST's masks stay element-wise, so a feature remains "in use" whenever any single edge survives. Second, its score has a hand-tuned balance between gradient and magnitude and corresponds to no objective. Third, it commits to features after very little training. Our method makes rows the unit of the mask. Its score is derived from the objective and has a single interpretable threshold $\lambda$. It also carries a stopping certificate.
AutoEncoder Inspired Unsupervised Feature Selection (AEFS) supplies the objective. It puts exactly this $\ell_{2,1}$ penalty on a dense autoencoder's first layer and solves it by proximal gradient. AEFS is the dense-to-sparse version of what we propose: same penalty, but every row is trained at every step. The linear predecessors, Joint Feature Selection and Subspace Learning and Embedded Unsupervised Feature Selection, justify joint rather than two-stage selection. FSSL reaches 98.77% on Extended Yale-B against 81.19% for standard LDA, and EUFS beats the all-features COIL-20 clustering baseline. Both use fixed-point or ADMM solvers that the file flags as scaling poorly, and both are linear.
On the sparse-training side, Do We Actually Need Dense Over-Parameterization? In-Time Over-Parameterization in Sparse Training shows that sparse networks match dense ones when they visit enough distinct parameters over time. We use that finding as a constraint. The feature-level visit rate, the fraction of all $d$ features ever activated, becomes a quantity we measure and control. An Efficient Row-Based Sparse Fine-Tuning shows that restricting updates to selected rows yields a dense sub-matrix, which runs efficiently on ordinary hardware. That paper does this only for fine-tuning pretrained language models with a static row choice. We use the same computational fact during training from scratch, with rows changing over time. Why Random Pruning Is All We Need to Start Sparse justifies starting the hidden layers from a random sparse mask.
Research Program
The first component is the algorithm with a controlled scoring cost. Computing $G_i$ for an inactive row requires reading feature $i$ on a minibatch: $G_i = x_{:,i}^\top \Delta$, where $x_{:,i}$ is that feature's column and $\Delta$ is the backpropagated signal at the first hidden layer. A full scan costs a read of all $d$ features once per mask update, which is still far cheaper than dense training. We also study a partial scan over a random candidate pool of size $r \ll d$, with the pool weighted toward low-$N_i$ features. This setting matters when reading a feature is itself expensive.
The second component is analysis. In the linear, convex case, the full-scan variant is an active-set group-lasso solver, so it should reach the same solution as a dense proximal solver. We verify this numerically as a correctness check. In the nonconvex case, we prove only the weaker statement: if the loop terminates with no row failing screening, the result is a stationary point of the full penalized objective. We also characterize the partial scan's failure probability as a function of $r$ and the number of violating rows.
The third component is a controlled study of early elimination. We use synthetic data in which some features matter only through interactions with others. Such features have near-zero marginal gradient early in training, and we test whether they are recovered under WAST-style early commitment, pure screening, and screening with exploration.
Baselines
The naive reference points are all features with the same downstream evaluator, and random selection of $k$ features. Any method that fails to beat random selection on Madelon is broken.
The strongest dense competitor is AEFS: the same $\ell_{2,1}$-penalized autoencoder trained densely with proximal gradient. It is the right comparison because it optimizes the identical objective without any sparsity budget, so it bounds what our method could achieve if exploration were free. We run it with the same architecture, the same $\lambda$ grid, and the same number of epochs. We report its training cost in floating-point operations and in features read per step. The file's reported figures for AEFS are clustering accuracy of 73.1% on Prostate_GE and 96.2% classification accuracy on MNIST using selected features, both from AutoEncoder Inspired Unsupervised Feature Selection. We rerun it rather than rely on these numbers, because the selected-feature counts must match. Our method beats AEFS if it matches AEFS's downstream accuracy within seed noise at equal $k$ while using a small fraction of its training compute. On the synthetic interaction task, it beats AEFS if it recovers equal or more of the truly relevant features.
The strongest sparse competitor is WAST, run from its published description at the same density and epoch budget. It receives the same tuning budget for its gradient/magnitude balance as we give to $\lambda$ and $c$. The file gives no absolute accuracy for WAST on any dataset. It reports only the relative 22% Madelon gain and the reduction in floating-point operations, so there is no reported result found on Lacuna for WAST's absolute accuracy. We will reproduce it on all shared benchmarks. Our method beats WAST if it gives higher downstream accuracy at equal $k$ on the noisy and high-dimensional sets (Madelon, SMK-CAN-187, GLA-BRA-180, PCMAC). It also beats WAST if it reads strictly fewer features over training at equal accuracy.
Two ablations isolate the key ingredients. The first is WAST's score applied to row-level masks. It keeps row granularity but removes the screening rule, which tells us whether the gain comes from the unit of the mask or from the criterion. The second removes the exploration bonus ($c=0$) and, separately, replaces screening with random row regrowth. Together these measure what the screening test and the exploration term each contribute.
Why not just…?
Why not just take WAST and rank features by their row norm at the end? WAST's importance score already aggregates magnitudes per input neuron, so this is the most serious threat. If row-norm ranking of WAST's model matches our selections, then row-level masks and screening add little for accuracy. The remaining advantage would be computational: WAST still keeps edges on many features during training. The row-granular WAST ablation above tests exactly this. We also report the number of features with at least one live edge during WAST training, which measures how much of the input it keeps reading.
Why not just train densely with $\ell_{2,1}$ like AEFS and prune? On small benchmarks this may be perfectly adequate, and we expect AEFS to be competitive there in accuracy. The case for our method rests on cost and on datasets where $d$ is large relative to samples, where dense training is also the most prone to fitting noise. WAST's Madelon result is suggestive but not proof of that effect. If AEFS matches us on accuracy everywhere, the contribution reduces to compute savings, and we will report it that way.
Why not just select features first with a classical filter, then sparse-train on them? FSSL and EUFS both report that decoupled pipelines lose accuracy against joint optimization, for example 81.19% versus 98.77% on Yale-B for FSSL. Those comparisons are linear, however. We include a filter-then-train baseline that picks features by variance and by per-feature correlation with the reconstruction target. This checks directly whether the non-linear joint criterion matters.
Proposed Experiments
We evaluate on the feature-selection benchmarks shared by WAST, AEFS and EUFS: Madelon, MNIST, FashionMNIST, USPS, COIL-20, Isolet, HAR, PCMAC, Prostate_GE, SMK-CAN-187 and GLA-BRA-180. We use selected-feature budgets $k \in \{25, 50, 100, 200\}$ and follow the downstream protocol of an external classifier trained on the selected features, plus clustering accuracy for the unsupervised comparison with EUFS on COIL-20. For Madelon we also report precision at recovering the 20 informative features. We add the synthetic interaction dataset described above.
For each method we report four quantities: downstream accuracy, cumulative features read during training, training floating-point operations, and wall-clock time. For our method, wall-clock uses a gather-then-dense-multiply implementation; for WAST, it uses masked dense and compressed-sparse-row variants.
Three checks are decisive. First, in the linear case the full-scan variant must reproduce the dense proximal solution's active set. Failure means the implementation or the theory is wrong. Second, on the interaction task, screening with exploration must recover interaction features that the early-commitment and $c=0$ variants lose. If it does not, the claim about early elimination fails. Third, on the high-dimensional biological sets, our method must match or beat AEFS at equal $k$ while reading well under the full feature count per step. If partial scans with small $r$ also hold accuracy, that establishes the cheaper regime where features are costly to acquire.
References
- Dynamic Sparse Training via Balancing the Exploration-Exploitation Trade-off
- Dynamic Sparse Training with Structured Sparsity
- Where to Pay Attention in Sparse Training for Feature Selection?
- Autoencoder Inspired Unsupervised Feature Selection
- Joint Feature Selection and Subspace Learning
- Embedded Unsupervised Feature Selection
- Do We Actually Need Dense Over-Parameterization? In-Time Over-Parameterization in Sparse Training
- An Efficient Row-Based Sparse Fine-Tuning
- Why Random Pruning Is All We Need to Start Sparse