Non-Convex Feature Learning via L_{p, inf} Operator

Deguang Kong, Chris H. Q. Ding

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.

Visualization of the $\ell_p$ norm for various values of $p$. As $p$ approaches 0, the function increasingly mimics the $\ell_0$ "counting" norm, facilitating sharper feature selection.

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.

Classification accuracy on biological datasets (ALLAML, GLIOMAML, LUNGML) using kNN and SVM. The non-convex $p < 1$ models consistently outperform the convex $p=1$ and other baseline methods.

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

BibTeX
@inproceedings{kong2014non,
  author = {Deguang Kong and Chris H. Q. Ding},
  title = {{Non-Convex Feature Learning via L\_\{p, inf\} Operator}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2014},
}
Figure