Stochastic Hard Thresholding Algorithms for AUC Maximization

Zhenhuan Yang, Baojian Zhou, Yunwen Lei, Yiming Ying

Optimizing the Area Under the ROC Curve (AUC) is the gold standard for imbalanced classification tasks—think fraud detection, medical diagnosis, or anomaly detection. However, AUC optimization is notoriously difficult because its objective function is based on pairwise losses (comparing every positive sample to every negative one). This leads to a computational bottleneck that makes standard stochastic gradient methods either too slow or too memory-intensive for high-dimensional data.

In this work, researchers introduce SHT-AUC, the first stochastic hard thresholding algorithm designed specifically for AUC maximization. By reformulating the complex pairwise AUC objective into a standard empirical risk minimization (ERM) form, they enable a fast stochastic algorithm with $O(bd)$ per-iteration complexity.

The Challenge of Pairwise Objectives

Most machine learning models minimize "pointwise" loss (error on a single data point). AUC is different; it measures the probability that a randomly chosen positive instance is ranked higher than a negative one. This "pairwise" nature creates a $U$-statistic objective that traditionally requires $O(n^2)$ comparisons.

Existing stochastic methods for AUC often struggle with a trade-off between efficiency and sparsity. In high-dimensional settings (where features $d \gg$ samples $n$), sparse models are essential. While $\ell_1$ regularization (Lasso) is common, it often fails to preserve a truly sparse solution in stochastic settings.

Methodology: SHT-AUC

The core innovation lies in two steps:

  1. Equivalent Reformulation: The authors prove that the pairwise $U$-statistic objective can be rewritten as a single-sum ERM objective. By calculating the global means of positive and negative samples once at the start, they transform the "compare everyone to everyone" problem into a "compare each point to the class means" problem.
  2. SHT-AUC Algorithm: With the ERM form in hand, they apply Stochastic Hard Thresholding. In each iteration, a mini-batch is selected, a gradient descent step is taken, and a Hard Thresholding Operator ($H_k$) is applied to keep only the $k$ largest components of the weight vector.

Theoretical Insights: The Imbalance Penalty

A key contribution of the paper is the rigorous theoretical analysis showing that the convergence rate is tied to the imbalance ratio ($r$). As data becomes more imbalanced (fewer positives), the "restricted condition number" of the problem worsens, leading to slower convergence.

Convergence of SHT-AUC across different sparsity levels ($k_*$) and imbalance ratios ($r$). Lower $r$ values (more imbalance) significantly slow down convergence.

Despite the non-convexity introduced by the hard thresholding step, the authors prove that SHT-AUC enjoys a linear convergence rate up to a specific tolerance error, provided the objective satisfies certain "restricted" convexity and smoothness properties.

Empirical Results

The authors validated SHT-AUC on high-dimensional biological datasets, including the Leukemia dataset (7,129 features) and the Colon Cancer dataset (2,000 features).

AUC performance vs. sparsity level $k$ on the Colon Cancer and Leukemia datasets. SHT-AUC consistently outperforms baselines like SOLAM, FSAUC, and SPAM.

Key findings include:

  • Superior AUC: On the Colon Cancer dataset, SHT-AUC achieved an AUC of 0.8777, outperforming all six baselines.
  • Robust Feature Selection: SHT-AUC identifies "ground truth" features much more accurately than Lasso-based AUC methods, maintaining high F1 scores even under high imbalance.
  • Efficiency: The algorithm maintains a per-iteration cost of $O(bd)$, making it suitable for large-scale, high-dimensional problems.

Conclusion

SHT-AUC provides a powerful framework for sparse AUC maximization. By combining an efficient ERM reformulation with stochastic hard thresholding, it bridges the gap between computational efficiency and model interpretability in imbalanced, high-dimensional domains. Future work may explore extending these theoretical guarantees to non-Gaussian data distributions and alternative surrogate loss functions.

Summary updated

Abstract

In this paper, we aim to develop stochastic hard thresholding algorithms for the important problem of AUC maximization in imbalanced classification. The main challenge is the pairwise loss involved in AUC maximization. We overcome this obstacle by reformulating the U-statistics objective function as an empirical risk minimization (ERM), from which a stochastic hard thresholding algorithm (SHT-AUC) is developed. To our best knowledge, this is the first attempt to provide stochastic hard thresholding algorithms for AUC maximization with a per-iteration cost O(bd) where d and b are the dimension of the data and the minibatch size, respectively. We show that the proposed algorithm enjoys the linear convergence rate up to a tolerance error. In particular, we show, if the data is generated from the Gaussian distribution, then its convergence becomes slower as the data gets more imbalanced. We conduct extensive experiments to show the efficiency and effectiveness of the proposed algorithms.
BibTeX
@inproceedings{yang2020stochastic,
  author = {Zhenhuan Yang and Baojian Zhou and Yunwen Lei and Yiming Ying},
  title = {{Stochastic Hard Thresholding Algorithms for AUC Maximization}},
  booktitle = {ICDM},
  year = {2020},
  url = {https://openreview.net/forum?id=TWp8lb8N5E7},
}
Figure