Efficient Top-K Feature Selection Using Coordinate Descent Method

Lei Xu, Rong Wang, Feiping Nie, Xuelong Li

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.

Simplification of the objective function for efficient coordinate descent updates.

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).

Classification accuracy on the Isolet dataset compared to state-of-the-art methods.

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

Abstract

Sparse learning based feature selection has been widely investigated in recent years. In this study, we focus on the l2,0-norm based feature selection, which is effective for exact top-k feature selection but challenging to optimize. To solve the general l2,0-norm constrained problems, we novelly develop a parameter-free optimization framework based on the coordinate descend (CD) method, termed CD-LSR. Specifically, we devise a skillful conversion from the original problem to solving one continuous matrix and one discrete selection matrix. Then the nontrivial l2,0-norm constraint can be solved efficiently by solving the selection matrix with CD method. We impose the l2,0-norm on a vanilla least square regression (LSR) model for feature selection and optimize it with CD-LSR. Extensive experiments exhibit the efficiency of CD-LSR, as well as the discrimination ability of l2,0-norm to identify informative features. More importantly, the versatility of CD-LSR facilitates the applications of the l2,0-norm in more sophisticated models. Based on the competitive performance of l2,0-norm on the baseline LSR model, the satisfactory performance of its applications is reasonably expected. The source MATLAB code are available at: https://github.com/solerxl/Code_For_AAAI_2023.
BibTeX
@inproceedings{xu2023efficient,
  author = {Lei Xu and Rong Wang and Feiping Nie and Xuelong Li},
  title = {{Efficient Top-K Feature Selection Using Coordinate Descent Method}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.1609/aaai.v37i9.26258},
}
Figure