Stochastic Primal-Dual Double Block-Coordinate for Two-way Partial AUC Maximization
Linli Zhou [email protected], Bokun Wang [email protected], My T. Thai [email protected], Tianbao Yang [email protected] · 2025
Read Stochastic Primal-Dual Double Block-Coordinate for Two-way Partial AUC Maximization by Linli Zhou [email protected], Bokun Wang [email protected], My T. Thai [email protected], Tianbao Yang [email protected] (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-21944.txt.
Introduction
Linli Zhou, Bokun Wang, My Thai, and Tianbao Yang made optimization algorithms in twenty twenty-five for two-way partial AUC. It is a classifier metric made for data that is not balanced. Plain accuracy hides how a model does in the ranges that count. Those are high true positive rates at low false positive rates. Partial AUC grades just those windows. But stochastic optimizers for it lagged. They leaned on approximations or had poor complexity.
Their two algorithms update primal and dual variables. They do so in stochastic block-coordinate style. One is for convex losses and one is for non-convex ones. Study of convergence shows better rates than past methods. On many benchmark data sets the new pair converged faster. They generalized better too. The work gives sharper tools for tasks such as screening and diagnosis. In such tasks, not all errors cost the same.
Catalog record
| CREATOR | Linli Zhou [email protected], Bokun Wang [email protected], My T. Thai [email protected], Tianbao Yang [email protected] |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 131 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-21944
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Stochastic Primal-Dual Double Block-Coordinate for Two-way Partial AUC Maximization Linli Zhou [email protected], Bokun Wang [email protected], My T. Thai [email protected], Tianbao Yang [email protected] Abstract Two-way partial AUC (TPAUC) is a critical performance metric for binary classification with imbalanced data, as it focuses on specific ranges of the true positive rate (TPR) and false positive rate (FPR). However, stochastic algorithms for TPAUC optimization remain under-explored, with existing methods either limited to approximated TPAUC loss functions or burdened by sub-optimal complexities. To overcome these limitations, we introduce two innovative stochastic primal-dual double block-coordinate algorithms for TPAUC maximization. These algorithms utilize stochastic block-coordinate updates for both the primal and dual variables, catering to both convex and non-convex settings. We provide theoretical convergence rate analyses, demonstrating significant improvements over prior approaches. Our experimental results, based on multiple benchmark datasets, validate the superior performance of our algorithms, showcasing faster convergence and better generalization. This work advances the state of the art in TPAUC optimization and offers practical tools for real-world machine learning applications. Reviewed on OpenReview: https://openreview.net/forum?id=M3kibBFP4q 1 Introduction The area under the ROC curve, commonly referred to as AUC, is frequently utilized as a measure of the model’s classification ability, without the explicit setting of a threshold. With a long history dating back to the late 90s ( Herbrich et al., 1999 ) , AUC is acknowledged as a more informative metric than accuracy for assessing the performance of binary classifiers in the context of imbalanced data and widely used in machine learning. In many applications, there are large monetary costs due to high false positive rates (FPR) and low true positive rates (TPR), e.g., in medical diagnosis. Hence, a measure of primary interest is the region of the ROC curve corresponding to low FPR and high TPR, i.e., TPR \geq 1-\theta_{0} , FPR \leq\theta_{1} , for some \theta_{0},\theta_{1}\in(0,1) , which is referred to as two-way partial AUC (TPAUC). Nevertheless, research on efficient optimization algorithms to optimize TPAUC for learning a classifier remains underdeveloped. Compared with standard AUC maximization, optimizing TPAUC presents several unique technical challenges. First, the estimator of TPAUC requires selecting subsets of positives and negatives in the top and bottom ranks. Some earlier works have proposed heuristic approaches for TPAUC maximization, including selecting examples based on their ranks in the mini-batch or converting data selection into ad-hoc data weighting ( Yang et al., 2021 ; Kar et al., 2014 ) , which do not provide a guarantee of optimizing TPAUC losses. Table 1 : Comparison with prior works for optimizing the TPAUC loss, where n_{+} is the number of positive examples, S is the mini-batch size of positive examples, B is the mini-batch size of negative examples, and d is the dimension of the model parameter Method Convexity Loop Iteration Complexity Total Complexity SONX ( Hu et al., 2023 ) non-convex Single \order{(B+S)d} \order{\frac{n_+}{B^{1/2}S\epsilon^6}} SOTA ( Zhu et al., 2022 ) non-convex Double \order{(B+S)d+n_+} \order{\frac{n_+}{\epsilon^6}} STACO1 (Ours) convex Single \order{(B+S)d} \order{\frac{n_+}{S\epsilon^2}} STACO2 (Ours) non-convex Double \order{(B+S)d} \order{\frac{n_+}{BS\epsilon^6}} Recently, Zhu et al. (2022) have initiated rigorous optimization of TPAUC losses. They converted data selection in top/bottom ranks into pairwise loss selection and reformulated it using the tool of distributionally robust optimization. They have proposed two algorithms for two different formulations: SOTAs for solving a smooth coupled compositional objective that corresponds to a soft TPAUC loss and SOTA for solving a non-smooth min-max objective that corresponds to an exact TPAUC loss. Nevertheless, SOTAs is not for optimizing the exact TPAUC loss, and SOTA is inefficient for large datasets as it requires updating all coordinates of an auxiliary variable corresponding to all positive examples at every iteration. Additionally, its convergence rate analysis fails to demonstrate any mini-batch speedup. Hu et al. (2023) has developed an algorithm for solving non-convex non-smooth coupled compositional objective of the exact TPAUC loss as formulated in ( Zhu et al., 2022 ) . However, their method cannot achieve linear speedup in terms of the mini-batch size of negative examples. In addition, since their method does not exploit convexity, its convergence guarantee still exhibits a complexity of O(1/\epsilon^{6}) even in the convex setting. To overcome these difficulties, this paper proposes improved algorithms and analysis over SOTA for solving the non-smooth min-max objective of the exact TPAUC loss. Our key idea is to design stochastic double block-coordinate updates that simultaneously act on both primal and dual variables. We propose two methods: STACO1 for convex objectives and STACO2 for non-convex objectives. Our convergence analysis introduces novel techniques for handling non-bilinear min-max objectives with stochastic block-coordinate updates, establishing state-of-the-art complexity bounds. Our algorithms enable scalable updates and provable mini-batch parallel speedup. We compare our results with prior works in Table 1 . We summarize the main contributions of our work below: • We propose novel primal-dual double block-coordinate algorithms STACO ( S tochastic T wo-way partial A UC block- C ordinate O ptimizer) designed for convex functions (STACO1) and non-convex functions (STACO2). These algorithms leverage double block-coordinate updates for both the primal and dual variables. • We provide a novel convergence analysis of STACO1 for convex functions. To the best of our knowledge, this is the first work to analyze double block-coordinate updates for both primal and dual variables for min-max optimization without a bilinear structure. We extend this analysis to STACO2 for non-convex cases, demonstrating its ability to find (nearly) stationary solutions. We demonstrate our algorithm enjoys better convergence rate than existing results Hu et al. (2023) ; Zhu et al. (2022) by improving the block-size dependency, achieving full mini-batch speedup and time efficiency. • We conduct comprehensive experiments on both linear and deep models for image classification and graph classification tasks involving imbalanced data. Our algorithms consistently demonstrate better performance compared to existing TPAUC maximization methods and various baselines. Additionally, we perform ablation studies to verify the improved convergence rates of our methods. 2 Related Work Two-way Partial AUC (TPAUC). AUC has been studied for more than two decades ( Hanley & McNeil, 1982 ) , and a huge amount of work has been devoted to AUC maximization ( Yang & Ying, 2022 ) . Compared to AUC maximization, two-way partial AUC (TPAUC) maximization is much more challenging due to that it involves the selection of examples whose prediction scores are in a certain range. Recently, studies on TPAUC have emerged, as researchers have argued that for certain tasks, only the TPR or FPR within a specific range is of interest ( Narasimhan & Agarwal, 2013 ; Yang et al., 2019 ; Yuan et al., 2021a ; Zhu et al., 2022 ; Xie et al., 2024 ) . In particular, by replacing TPR and FPR with surrogate losses, TPAUC maximization problem can be further transformed into coupled compositional optimization and min-max optimization ( Zhu et al., 2022 ) . Some other works are also focusing on TPAUC ( Zhang et al., 2023 ; Shao et al., 2023 ; Yang et al., 2023b ; Yang et al., 2022 ; Shao et al., 2022 ) . Zhang et al. (2023) focuses on optimizing a compositional formulation for AUC maximization, Shao et al. (2023) considers a weighted AUC formulation for cost-sensitive learning, and Yang et al. (2023b) considers AUC maximization with certified robustness. Yang et