Abstract
Feature selection is a critical task in high-dimensional data analysis to mitigate overfitting and enhance computational efficiency. While the $l_{2,1}$-norm is widely used due to its convexity, it requires tedious hyperparameter tuning to achieve a specific number of features. The $l_{2,0}$-norm offers a more direct "top-k" selection but presents a non-convex, NP-hard optimization challenge. This paper introduces CD-LSR (Coordinate Descent Least Square Regression), an efficient, parameter-free framework that identifies the exact top-$k$ features by decomposing the weight matrix and employing a simplified coordinate descent approach. Experimental results across various benchmarks demonstrate that CD-LSR achieves superior accuracy and faster convergence compared to existing state-of-the-art methods.
Introduction
In modern machine learning, datasets often contain thousands of features, many of which are redundant or noisy. Feature selection aims to identify the most informative subset of variables to improve model performance and interpretability. Traditional sparse learning often relies on the $l_{2,1}$-norm, which uses a regularization parameter $\lambda$ to induce sparsity. However, finding the right $\lambda$ to obtain exactly $k$ features is a trial-and-error process that can be computationally expensive.
The $l_{2,0}$-norm constraint directly specifies the desired number of features $k$, making it highly intuitive for practitioners. Yet, solving $l_{2,0}$-norm problems is computationally demanding due to their non-convex nature. Existing solvers like Augmented Lagrangian Methods (ALM) or Projection Gradient Descent (PGD) often suffer from instability or require extensive hyperparameter tuning. CD-LSR addresses these issues by providing a stable, efficient, and parameter-free optimization path.
Methodology
The CD-LSR framework introduces several key innovations to solve the $l_{2,0}$-norm feature selection problem efficiently.
Matrix Decomposition and Coordinate Descent
The core idea is the decomposition of the weight matrix $W$ into $W = SV$, where $S$ is a discrete selection matrix and $V$ is a continuous weight matrix. The matrix $S$ acts as a set of binary switches, effectively selecting the $i$-th feature if the corresponding entry is non-zero. This transformation converts the $l_{2,0}$ constraint into a more manageable discrete selection problem. Rather than updating the entire selection matrix simultaneously, CD-LSR employs a coordinate descent (CD) strategy, updating $S$ column-by-column.
Computational Simplification
To maintain efficiency as the feature count grows, the authors derived a simplified objective function. By eliminating terms that remain constant during single-feature updates, the computational complexity of evaluating candidate features is significantly reduced. This allows the algorithm to evaluate updates in $O(k + c)$ time, where $c$ is the number of classes, rather than performing massive matrix multiplications at every step.
Crucially, the method is parameter-free; the user only needs to specify the target number of features $k$, avoiding the need to tune learning rates or penalty terms.
Experimental Evaluation
The performance of CD-LSR was evaluated on six benchmark datasets: SRBCT (bioinformatics), USPS & UMIST (handwritten digits), JAFFE (facial expressions), COIL20 (object recognition), and Isolet (audio/speech). These datasets provide a rigorous test for scalability and robustness across different domains.
Results and Discussion
CD-LSR consistently outperformed or matched 11 state-of-the-art feature selection methods, including deep learning-based approaches like Concrete AutoEncoders (CAE).
As shown in the results for the Isolet dataset, CD-LSR (represented by the red star line) achieves high accuracy even with a small number of features and maintains a competitive edge as $k$ increases. Beyond accuracy, the algorithm exhibits excellent convergence properties, typically reaching an optimal solution in fewer than 10 iterations. In terms of speed, CD-LSR proved significantly faster than competitors like PGD on high-dimensional data such as SRBCT, maintaining a "top-2" speed profile while providing better feature sets.
Conclusion
CD-LSR provides a robust and efficient solution for top-$k$ feature selection by leveraging matrix decomposition and simplified coordinate descent. By bypassing the need for abstract regularization parameters, it offers a more practical and interpretable tool for researchers. While the computational cost scales with the number of features $k$, the method's stability and accuracy make it a superior choice for many high-dimensional applications. Future work will explore extending this framework to unsupervised learning and more sophisticated models beyond simple least-squares regression.
Summary updated