Robust supervised classification and feature selection using a primal-dual method

Michel Barlaud, Antonin Chambolle, Jean-Baptiste CaillauarXiv 2019 · arXiv

Introduction

In modern genomics and image recognition, researchers frequently encounter high-dimensional datasets where the number of features (e.g., tens of thousands of genes) vastly exceeds the number of samples. Effective classification in these domains requires simultaneous dimensionality reduction and feature selection. Traditional methods often rely on quadratic cost functions and sparsity penalties like LASSO. However, these approaches struggle with outlier sensitivity, slow hyperparameter tuning, and rigid clustering assumptions.

This paper presents a robust, highly scalable primal-dual algorithm designed to overcome these limitations. By integrating Huber loss, dynamic cluster centers, and hard constraints, the proposed method achieves significant accuracy improvements and computational speedups, particularly in noisy biological contexts such as single-cell RNA sequencing (scRNA-seq).

Methodology

The core of the proposed approach is a constrained formulation solved via a primal-dual splitting algorithm. This framework introduces several key innovations:

1. Robust Huber Loss

Standard methods often use the Frobenius norm, which is highly sensitive to outliers. The authors replace this with a Huber loss function. This function behaves quadratically for small deviations but scales linearly for larger ones, offering robustness against data noise (such as "dropouts" in scRNA-seq) while maintaining smooth convergence properties.

2. Dynamic Cluster Centers

Unlike traditional methods that project data onto fixed, pre-determined centers, this algorithm optimizes a matrix of centers ($\mu$) simultaneously with the projection matrix ($W$). This adaptability allows the model to better capture complex data distributions.

3. Hard Constraints for Structured Sparsity

Instead of using Lagrangian penalties that require exhaustive tuning, sparsity is enforced through hard constraints (e.g., bounding the norm of weights within a radius $\eta$). This enables the use of efficient mathematical projections, significantly reducing computational overhead.

Key Insights: Stability and Convergence

A major finding is that the Huber loss effectively mitigates the optimization oscillations typically seen with pure $\ell_1$ loss. As shown in Figure 1, the transition to a Huber loss ($\delta=1$) results in a much smoother convergence path compared to the $\ell_1$ variant ($\delta=0$).

Figure 1: Convergence comparison showing how Huber loss ($\delta=1$, green) stabilizes the optimization path compared to the oscillating behavior of pure $\ell_1$ loss ($\delta=0$, blue).

Furthermore, the algorithm's convergence behavior remains robust across different parameter settings, as illustrated in Figure 2. This stability is crucial for scaling to datasets with thousands of features.

Figure 2: Loss convergence over iterations for various $\beta$ parameter values, demonstrating the algorithm's consistent performance and rapid convergence.

Results and Performance

The method was evaluated on synthetic and real-world biological datasets, including Ovarian cancer mass-spectra and Tabula Muris lung transcriptome data.

  • Massive Accuracy Boosts: The introduction of adaptive centers ($\mu$) led to dramatic improvements. For instance, classification accuracy on the Ovarian dataset rose from 82.4% to 94.4%, and on the Thyroid dataset from 70% to 92%.
  • Superior Scalability: The primal-dual algorithm demonstrated superior scalability compared to standard solvers. In a test with 4,000 features, it completed in 397 milliseconds, whereas the standard ADMM solver required 32.7 seconds. ADMM failed to process larger feature sets (8,000+), while the proposed method continued to scale linearly.
  • Clear Feature Selection: The method identifies a clear "break" in the accuracy curve relative to the number of selected genes, aiding researchers in identifying minimal biological signatures.

Conclusion

The proposed primal-dual framework offers a modular and efficient solution for robust classification and feature selection. By replacing rigid penalties with flexible constraints and robust loss functions, it provides a powerful tool for analyzing high-dimensional, noisy biological data. Future work may extend this framework to include additional regularization terms or alternative loss criteria.

Summary updated

Abstract

This paper deals with supervised classification and feature selection in high dimensional space. A classical approach is to project data on a low dimensional space and classify by minimizing an appropriate quadratic cost. A strict control on sparsity is moreover obtained by adding an $\ell_1$ constraint, here on the matrix of weights used for projecting the data. Tuning the sparsity bound results in selecting the relevant features for supervised classification. It is well known that using a quadratic cost is not robust to outliers. We cope with this problem by using an $\ell_1$ norm both for the constraint and for the loss function. In this case, the criterion is convex but not gradient Lipschitz anymore. Another second issue is that we optimize simultaneously the projection matrix and the centers used for classification. In this paper, we provide a novel tailored constrained primal-dual method to compute jointly selected features and classifiers. Extending our primal-dual method to other criteria is easy provided that efficient projection (on the dual ball for the loss data term) and prox (for the regularization term) algorithms are available. We illustrate such an extension in the case of a Frobenius norm for the loss term. We provide a convergence proof of our primal-dual method, and demonstrate its effectiveness on three datasets (one synthetic, two from biological data) on which we compare $\ell_1$ and $\ell_2$ costs.
BibTeX
@misc{barlaud2019robust,
  author = {Michel Barlaud and Antonin Chambolle and Jean-Baptiste Caillau},
  title = {{Robust supervised classification and feature selection using a primal-dual method}},
  year = {2019},
  eprint = {1902.01600},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1902.01600},
}
Figure