Scaling Up ROC-Optimizing Support Vector Machines

• URL: http://arxiv.org/abs/2511.04979v1
• Date: Fri, 07 Nov 2025 04:38:25 GMT
• Title: Scaling Up ROC-Optimizing Support Vector Machines
• Authors: Gimun Bae, Seung Jun Shin,
• Abstract summary: The ROC-SVM directly maximizes the area under the ROC curve (AUC) and has become an attractive alternative of the conventional binary classification under the presence of class imbalance.<n>We develop a scalable variant of the ROC-SVM that leverages incomplete U-statistics, thereby substantially reducing computational complexity.<n>We extend the framework to nonlinear classification through a low-rank kernel approximation, enabling efficient training in reproducing kernel Hilbert spaces.
• Score: 3.1941554288428198
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The ROC-SVM, originally proposed by Rakotomamonjy, directly maximizes the area under the ROC curve (AUC) and has become an attractive alternative of the conventional binary classification under the presence of class imbalance. However, its practical use is limited by high computational cost, as training involves evaluating all $O(n^2)$. To overcome this limitation, we develop a scalable variant of the ROC-SVM that leverages incomplete U-statistics, thereby substantially reducing computational complexity. We further extend the framework to nonlinear classification through a low-rank kernel approximation, enabling efficient training in reproducing kernel Hilbert spaces. Theoretical analysis establishes an error bound that justifies the proposed approximation, and empirical results on both synthetic and real datasets demonstrate that the proposed method achieves comparable AUC performance to the original ROC-SVM with drastically reduced training time.

Related papers

• Scalable Analytic Classifiers with Associative Drift Compensation for Class-Incremental Learning of Vision Transformers [26.771319566121708]
  Class-incremental learning with Vision Transformers (ViTs) faces a major computational bottleneck during the reconstruction phase.<n>Regularized Gaussian Discriminant Analysis (RGDA) provides a Bayes-optimal alternative with accuracy comparable to SGD-based classifiers.<n>We propose Low-Rank Factorized RGDA (LR-RGDA), a scalable classifier that combines RGDA's expressivity with the efficiency of linear classifiers.
  arXiv  Detail & Related papers  (2026-01-29T06:42:20Z)
• Robust low-rank estimation with multiple binary responses using pairwise AUC loss [0.0]
  Multiple binary responses arise in many modern data-analytic problems.<n>Low-rank models offer a natural way to encode latent dependence across tasks.<n>Existing methods for binary data are largely likelihood-based and focus on pointwise classification.
  arXiv  Detail & Related papers  (2026-01-13T15:00:10Z)
• Binary Kernel Logistic Regression: a sparsity-inducing formulation and a convergent decomposition training algorithm [0.5680416078423551]
  Kernel logistic regression (KLR) is a widely used supervised learning method for binary and multi-class classification.<n>Previous attempts to deal with sparsity in KLR include a method referred to as the Vector Import Machine (IVM)<n>We propose an extension of the training formulation proposed by Keerthi et al., which is able to induce sparsity in the trained model.
  arXiv  Detail & Related papers  (2025-12-22T14:40:30Z)
• Closing the Approximation Gap of Partial AUC Optimization: A Tale of Two Formulations [121.39938773554523]
  The Area Under the ROC Curve (AUC) is a pivotal evaluation metric in real-world scenarios with both class imbalance and decision constraints.<n>We present two simple instance-wise minimax reformulations to close the approximation gap of PAUC optimization.<n>The resulting algorithms enjoy a linear per-iteration computational complexity w.r.t. the sample size and a convergence rate of $O(-2/3)$ for typical one-way and two-way PAUCs.
  arXiv  Detail & Related papers  (2025-12-01T02:52:33Z)
• Graph-based Clustering Revisited: A Relaxation of Kernel $k$-Means Perspective [73.18641268511318]
  We propose a graph-based clustering algorithm that only relaxes the orthonormal constraint to derive clustering results.<n>To ensure a doubly constraint into a gradient, we transform the non-negative constraint into a class probability parameter.
  arXiv  Detail & Related papers  (2025-09-23T09:14:39Z)
• Learnable Scaled Gradient Descent for Guaranteed Robust Tensor PCA [39.084456109467204]
  We propose an efficient scaled gradient descent (SGD) approach within the t-SVD framework for the first time.<n>We show that RTPCA-SGD achieves linear convergence to the true low-rank tensor at a constant rate, independent of the condition number.
  arXiv  Detail & Related papers  (2025-01-08T15:25:19Z)
• DRAUC: An Instance-wise Distributionally Robust AUC Optimization Framework [133.26230331320963]
  Area Under the ROC Curve (AUC) is a widely employed metric in long-tailed classification scenarios. We propose an instance-wise surrogate loss of Distributionally Robust AUC (DRAUC) and build our optimization framework on top of it.
  arXiv  Detail & Related papers  (2023-11-06T12:15:57Z)
• Robust Long-Tailed Learning via Label-Aware Bounded CVaR [36.26100472960534]
  We propose two novel approaches to improve the performance of long-tailed learning with a solid theoretical ground. Specifically, we introduce a Label-Aware Bounded CVaR loss to overcome the pessimistic result of the original CVaR. We additionally propose a LAB-CVaR with logit adjustment to stabilize the optimization process.
  arXiv  Detail & Related papers  (2023-08-29T16:07:18Z)
• Asymptotically Unbiased Instance-wise Regularized Partial AUC Optimization: Theory and Algorithm [101.44676036551537]
  One-way Partial AUC (OPAUC) and Two-way Partial AUC (TPAUC) measures the average performance of a binary classifier. Most of the existing methods could only optimize PAUC approximately, leading to inevitable biases that are not controllable. We present a simpler reformulation of the PAUC problem via distributional robust optimization AUC.
  arXiv  Detail & Related papers  (2022-10-08T08:26:22Z)
• Learning with Multiclass AUC: Theory and Algorithms [141.63211412386283]
  Area under the ROC curve (AUC) is a well-known ranking metric for problems such as imbalanced learning and recommender systems. In this paper, we start an early trial to consider the problem of learning multiclass scoring functions via optimizing multiclass AUC metrics.
  arXiv  Detail & Related papers  (2021-07-28T05:18:10Z)
• Stochastic Optimization of Areas Under Precision-Recall Curves with Provable Convergence [66.83161885378192]
  Area under ROC (AUROC) and precision-recall curves (AUPRC) are common metrics for evaluating classification performance for imbalanced problems. We propose a technical method to optimize AUPRC for deep learning.
  arXiv  Detail & Related papers  (2021-04-18T06:22:21Z)
• Label-Imbalanced and Group-Sensitive Classification under Overparameterization [32.923780772605596]
  Label-imbalanced and group-sensitive classification seeks to appropriately modify standard training algorithms to optimize relevant metrics. We show that a logit-adjusted loss modification to standard empirical risk minimization might be ineffective in general. We show that our results extend naturally to binary classification with sensitive groups, thus treating the two common types of imbalances (label/group) in a unifying way.
  arXiv  Detail & Related papers  (2021-03-02T08:09:43Z)
• Estimating Average Treatment Effects with Support Vector Machines [77.34726150561087]
  Support vector machine (SVM) is one of the most popular classification algorithms in the machine learning literature. We adapt SVM as a kernel-based weighting procedure that minimizes the maximum mean discrepancy between the treatment and control groups. We characterize the bias of causal effect estimation arising from this trade-off, connecting the proposed SVM procedure to the existing kernel balancing methods.
  arXiv  Detail & Related papers  (2021-02-23T20:22:56Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.