Introduction
Feature selection is a foundational process in machine learning, designed to identify a subset of relevant features to improve model interpretability and reduce noise. Traditional methods often rely on the $\ell_{1, \infty}$ norm for structured sparsity, which encourages entire rows of a weight matrix to become zero. However, as a convex relaxation of the $\ell_0$ norm, the $\ell_{1, \infty}$ norm frequently fails to suppress irrelevant features as aggressively as needed. This paper introduces a non-convex approach using the $\ell_{p, \infty}$ penalty ($0 \le p < 1$), which more closely approximates the ideal sparsity of the $\ell_0$ norm.
Methodology
The authors propose a framework for multi-class sparse regression utilizing the $\ell_{p, \infty}$ operator. The penalty is defined as: $$\phi_\lambda(W) = \lambda \sum_{j=1}^d (\max_{1 \le k \le c} |W_{jk}|)^p$$ This function takes the maximum absolute value in each row and applies a $p$-norm across the rows. As shown in Figure 1, smaller values of $p$ create a sharper penalty near zero, which more effectively drives irrelevant feature weights to zero compared to the convex $p=1$ case.
To solve this non-convex optimization problem, the authors developed an efficient proximal gradient algorithm. The key innovation is a "Maximum Set" strategy that decomposes the proximal step into independent sub-problems for each row. By characterizing the structure of the optimal solution, the problem is reduced to finding a single shared maximum value for a specific subset of indices, which is achieved via an iterative Newton's method. Despite the non-convexity, the algorithm maintains a time complexity of $O(d \log d)$ or $O(d)$ per iteration, ensuring scalability for high-dimensional data.
Experimental Results
The researchers evaluated the $\ell_{p, \infty}$ method across diverse high-dimensional datasets, including biological multi-class data and multi-label image/video data.
Biological Multi-class Datasets
On datasets such as ALLAML (leukemia) and LUNGML (lung cancer), which feature thousands of genes but few samples, the non-convex approach consistently outperformed standard filter methods (e.g., F-statistic, ReliefF) and the convex $\ell_{2,1}$ method. As illustrated in Figure 6, smaller values of $p$ (0.25 and 0.5) generally yielded higher classification accuracy across both kNN and SVM classifiers.
Multi-label Performance
In multi-label tasks involving datasets like MSRC and Trevid, the method showed significant gains in Macro-F1 scores. This demonstrates the robustness of the non-convex approach in domains where multiple tags must be assigned simultaneously, such as image and video annotation.
Conclusion
The $\ell_{p, \infty}$ operator offers a mathematically rigorous way to bridge the gap between convex relaxations and the ideal $\ell_0$ norm for feature selection. By utilizing a non-convex penalty and an efficient proximal gradient algorithm, the proposed method achieves superior accuracy and sharper sparsity across a variety of complex datasets. Future research may explore automated parameter selection for $p$ and further theoretical convergence guarantees for this non-convex objective.
Summary updated