Stochastic Primal-Dual Double Block-Coordinate for Two- way Partial AUC Maximization
Authors: Linli Zhou
Bokun Wang
My T. Thai
Tianbao Yang
Venue: Accepted by TMLR ()

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.

Published in Transactions on Machine Learning Research (09/2025)
Stochastic Primal-Dual Double Block-Coordinate for Two- way Partial AUC Maximization
Linli Zhou
lynn94874 Stamm.44ttmm.dl edu
Deportment of Computer Science and Engineering Teaas ABM University
Bokun Wang
bokum, wong Cuteras. edu
Department of Electricol and Computer Engineering University of Tezas, Austin
My T. Thai Department of Computer and Information Science and Engineering University of Florida
mythai@@cie. edu
Tianbao Yang
Baabbooyyangtorne edu
Deportment of Computer Science and Engineering Texas A AGM University
Reviewed OpenReview: https: openreview. net/ forum? id= M3kibBFFP
Abstract
Two-way partial AUC (TPAUC) 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-oxplored, with existing methods either limited to approximated TPAUC loss functions or burdened by sub-optinal complexilies. 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.
1 Introduction
The area under the ROC curve, commonly referred as AUC, frequently utilized as a measure of the model's classification ability, without the explicit setting of a threshold. With a long history dating back the late 90s (Herbrich al. 1999), AUC acknowledged as 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 primary interest the region of the ROC curve corresponding low FPR and high TPR, i.c., TPR 1 - 6g. FPR f,, for some A, 0, e (0, 1), which is referred as woo-way partial AUC (TPAUC). Nevertheless, research on efficient optimization algorithms to optimize TPAUC for learning classifier remains underdeveloped.

---

Published in Transactions on Machine Learning Research (09/2025)
Table 1: Comparison with prior works for optimizing the TPAUC loss, where n, is the number of positive examples, is the mini-batch size of positive examples, 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
O( + ()d)
0
B
a
SOTA
Zhu et al.
2022
non-convex
Double
O(B 5)
STACOL (Ours)
convex
Single
O( S)d)
S2
STACO2 (Ours)
non-convex
Double
O( SSd)
B9g3
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 carlier works have proposed hcuristic 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
2021 Kar et al. 2014), which do not provide a guarantee of optimizing TPAUC losses. et al.
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 smooth coupled compositional objective that corresponds to soft TPAUC loss and SOTA for solving non-smooth min-max objective that corresponds to an exact TPAUC loss. Nevertheless, SOTAs is not for optímizing 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/e") even in the convex setting,
To overcome these difficulties, this paper proposes improved algorithms and analysis over SOTA for solving the non-smooth min-maa objective of the exact TPAUC loss. Our key idea is to design stochastic double block 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-arl complexity bounds. Our algorithms enable scalable updates and provable mini-batch parallel speedup. We compare our results with prior works in Table
We summarize the main contributions of our work below:
We propose novel primal-dual double clordicoo algorithms STACO (Stochastic Two-way partial AUC ClockeCordinte Optimizer) designed for convex functions (STACO1) and non-convex functions (STACO2). These algorithms leverage double block-coordinatee 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. 22022 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

---

Published in Transactions on Machine Learning Research (09/2025)
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 Comparod 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 certain range. Recently, studies on TPAUC
have emerged, as researchers have argued that for certain tasks, only the TPR or FPR within 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.
b022)- Some other works are also locusing on TPAUC (Zhang el al., 2023; Shao et al., 2023
Yang
eet al.
2023b 2022 Shao et al.] 2022)) Zhang et al. (2023) focuses on optimizing a compositional formulation
for
AUC maximization, Shao ct al. (2023) considers weighted AUC formulation for cost-sensitive learning,
and
Yang el al. (2023b) considers AUC maximization with certified robustness. Yang el al. 2022 Shao
et al.
(2022) focus on TPAUC maximization with the following differences: Yang et al. (2022) tackles the
data selection challenge by a weighting scheme, which does not yield the exact TPAUC surrogate objective;
(022) considers TPAUC maximization with a special square loss. In contrast, we directly tackle solving the exact TPAUC surrogate objective without further approximation and our result. applies to any non-docreasing loss function.
Shao et al.
Compositional Optimization. Compositional optimization has gained substantial attention in recent years. This area of optimization deals with objective functions that are composed of multiple nested functions, leading to challenges in efficient evaluation and optimization. Several papers (Wang et al. 2017a b Zhang & Lan
2020 Zhang & Xiao, 2022) have considered standard compositional oplimization, where the inner function does not depend on the random variable of the outer level. However, simply applying these algorithms to
TPAUC maximization would suffer a high cost (Qi et al. 2021]. To address this issue, [Zhu et al. (2022) have formulated TPAUC maximization as FCCO (Finite-Sum Coupled Compositional Optimization) as introduced in (Qi et al. )- Hu et al.] (2023) have proposed an algorithm termed SONX for solving a non-smooth FCCO optimization where the outer function is non-smooth and applied it to TPAUC maximization.
Min-Max Optimization. Many stochastic primal-dual algorithms have been proposed to solve non-convex min-max optimization since the seminal work [Rafique et al. 2022). Built on their proximal-uiide algorithmic framework, Zhu et al. (2022) developed SOTA for solving the min-max formulation of TPAUC loss. However, their algorithm suffers from the limitations mentioned before. To address its limitations, we have to consider double block-coordinate updates for both primal and dual variables and develop advanced techniques to derive complexity that has a parallel speed-up, which means complexity is linearly dependent both positive and negative mini-batch size. Several works (Zhang & Xiao 2015 Alacaoglu et al. 2022 have considered stochastic primal-dual block-coordinate algorithms for solving finite-sum min- max problems with bilinear structure, where the block-coordinate update is only applied to the dual variable. Hamedani et al. (2023); Jalilzadeh et al. (2019) have considered more general min-max probloms using block-coordinate updates for the primal variable only or for both primal and dual variables. However, their algorithm and analysis require the coupled function to be smooth in terms of both the primal and dual variables, which is not applicable to TPAUC maximization. In addition, Li et al. (2025) propose Smoothed Proximal Linear Descent-Ascent (Smoothed PLDA) algorithm for deterministic nonsmooth nonconvex-nonconeee convergence guarantees under the KT, property. However, PI.DA is not directly applicable to large-scale stochastic problems with composite structure, where full dual updates and deterministic computations are infeasible. Recently, Wang & Yang proposed a novel stochastic primal-dual cook--oord algorithm to solve convex finite-sum compositional optimization problems, which only employs the block-coordinate update on the dual variable.
minimax problems with
2.1 Notations and Definitions
We present notations in this section. For any w W, the subdifferential fw)(w) is the set of subgradients of f at point w. For vector y e R.", y()) IR represents the i-th coordinate (block) of y, i.e., y= (y(1), ,", (())T
3

---

Published in Transactions on Machine Learning Research (09/2025)
We use f to denote the convex conjugate of ft. For function g(x) Eg-r [g-r[9(x: we define the stochastic estimator based on the mini-batch B as g(x:B) Esa (x:: g)-
3 Primal-dual Double Block-Coordinate Algorithms for TPAUC Maximization
Let x denote an input example and (x) denote prediction of parameterized model such as deep neural network or linear model on data x. Denote by S, the set of n, positive examples and by S- the set of n- negative examples. TPAUC measures the area under the ROC curve where the TPR is higher than
1 0o and the FPR is lower than an upper bound 01. A surrogate loss for optimizing TPAUC with TPR.
2 1 1.. FPRs 0 given by:
min weR"
Σ E
(()w(x))) - hww (x.)),
(1)
x,68![1,k] [x,6S[[1,ka]
where {(-) is convex, monotonically non-decreasing surrogate loss of the indicator function ((hw(()) 2 hw (x;)), [1] the set positive examples with lą [n_ smallest scores, and [t [2] is the set of negative examples with k2 = [n_0, largest scores. To tackle the challenge of selecting examples for S1[1, ki and St [111ka] kg], we use the following lemma to reformulate (1) (Zhu et al. 2022..
Lemma 3.1. If E(-) is non-decreasing, then the TPAUC loss minimization problem
is equivalend to the
following:
min 1 Σ (((
(2)
w. .5 14+ x,55,
where s= (s(() ((0)),..,((.)))) [(g, 6') - 8'),, and ys (, (w,s(1) = - Exjes s(i) + (ll The reformulation above uses equivalent form of the conditional-valne-ttriii (CVaR) loss, mt E (.)(t))
01
ming 8 1 -)(((() - s],, where y == k/n for some integer E [n]] (tg(() denotes the i-th largest value in my (l1,".,,n) (n). (Ogryzzak & Tamir 2003 Lemma 1). Since [t]- = maxye[0,1] ty, we cast (2 into an equivalent
min-max problem:
gi( ((( - +s'
Σ y()). y 14 x;eS,
min weldd
3
Bu
This problem presents unique challenges that make existing algorithms unsuitable for direct application: (i) the objective function is non-smooth with respect to and due to the hinge function in 9i (ii) both the primal variable and the dual variable are high-dimensional and depend on all positive examples, preventing their full coordinate updates in each iteration; and (iii) the coupled term is not bilinear with respect to the primal and dual variables.
3.1 Algorithms
Now we present our efficient algorithms designed to solve the min-max problem 3 in convex and non-convex settings.
lw (x:)) is a convex function of w. This is true when we learn linear model such that h (x) w x. Hence, gi (w, 8) convex w.r.t. (w,s) for any i [n], and (3) is convex-concand min-max problem.
STACO1 for convex functions. We first consider the convex case when ((hw - hw
A challenge of solving
3 is that updating all coordinates for s,y would require computing (w, ()) and its gradient for all positive examples x; e S.,, which is prohibited when the nunber of positive examples is large. Hence, we have to use block-coordinate updates for both and y. Let us consider how to update y(0) and s(t) for sampled coordinate i. A simple method is use gradient ascent to update y(t) and use gradient descent update s(i), which require computing gi g.(,,(()) and ( (()) However, this would require processing all negative examples S_ as gil (w,)()) depends on all negative examples. To reduce this cost,
4

---

Published in Transactions on Machine Learning Research (09/2025)
Algorithm STACO1
Initialize Wo W. Yo 1 " So 1 56 1,
2: for == 0, 1
3: Sample a batch S. with |Si] S
4: Sample independent mini-batches B,, B, c.
5: for each i S,,, do
Update y according to Update 111 according to 55) 8: end for
9: For each i St, yt+l y; and (5) -
(4)
10: Update Wi+1 according to
11: Update 8/m1 according to
12:
end for
13: T Ei=o W= T EToo 8.1.8 7 Elo 6/1
14: Return w,s,3'
need to stochastic estimators of their gradients. For a random mini-batch of negative samples B S_, we let
[x,) - hw (x,)) -s(() s())
9: (W,wsS (w,s()))))))))))) (0;
s(() x,eB
Σ
B
01
At the t-th iteration, we sample a mini-batch of positive examples St c S, and mini-batch of B negative examples B, c.. We update yee1 according to
(1) ( B.) s
y+1
(1) arg max
()) Ji W., 8
(y -y()))(0)/
Vx, e.
(4)
y0e[o.1]
2a
where a a step size parameter. Then we update s i S, and Wa1 using stochastic gradient descent:
3
y 0 2 sw,, (1) (.) Vx, S.
(5)
4+1
0o
W
(1) Yit 8 (w,, (.) KS.
Σ
(6)
0g
444 = 5/ B1(1
on ie., (1)
where 3, 8" are step size parameters, and we use another mini- batch of negative samples B, independent of B, to decouple the dependence between (1) and B, The detailed steps of STACO1 are presented in Algorithm 1
STACO2 for non-convex functions. Next we consider the non-convex case. We assumee (x;) (x; is weakly-convex with respect to w, which holds true when é convex non-smooth function and how x is a smooth function of (Hu al. 2023). Hence, ge ge(w, w, weakly-convex with respect to (w, and 3 a weakly-convex concave min-max problem. Inspired by the proximal-guided algorithm (Rafique al. 2022 for non-smooth weakly-convex concave problems, propose double-loop algorithm STACO2 for solving problem 3.. The inner loop updates apply STACO1 to solve the following problem approximately at the f-th outer iteration:
1 Σ y(),
(i(w,s())
1 s
min
max 10
|w 2"
www- 2n.7 is st,ol
wo
(8)
74 x.a5,
On
where W.,,, Stu are initial value of w,s s at t-th stage, ? > is a proper parameter. The addition of quadratic functions to ensure the function becomes convex in terms of w.s. At k-th iteration in I-th stage, utilize

---

Published in Transactions on Machine Learning Research (09/2025)
Algorithm STACO2
Initialize Wo W, , 50 =1
2: for == ....... 7- do
3: Initialize Yr.0 1
4: Set wrO = wr $r,0 St, $1,0 - do
5: for k=
Sample a batch St, c St, where |St, = Sample independent mini-batches Br B S_ for each e St,k do
9:
Update y1 according to 9
10:
Update s (t) end for
1,k=1 according to 100
11:
(1)
12:
For cach i St,k, Vr,k1
=Y,k and s 1,411
13:
Update We+1 according to (11 Update 1//1 according to end for
14:
12
15:
16:
(W,, Sr, 31) Ke Ek=0 (Wi,k+1, St
17:
Set We+1 = S4,8 8,, s/11 = 8,
18: end for
19: Return WT. ST, 1/7
following updates:
(1) arg max y(e[(,11]
(() De(We,
( (.. Se
().
1 (y(0) -x(2))
Vx, e Si,
(9)
1,6+1
d0
2a
s 1,K+1
(1)
(1)
8o
3t
y
(,k-1
(i)
Oatgg Be,k)
1 (5( s(1b) Vxx e Scn
(i)
(10)
Wr.++1
We,k
1/8
1
Σ
Yi Owg.:wwwwww..... (w,,
(2)
(1 Br,k) + - -( wcol
(11)
80
s
ieS..k
6,,111 8/, 81(1
Σ
(12)
0o.
16Sr,
where Oet, Bi, Me, B are step size parameters.
We would like to highlight the difference between STACO2 and SOTA (Zhu et al. 2022 where we use block-coordinate update for s RR In contrast, SOTA needs to update all coordinates of s. This difference is caused by different techniques for handling all coordinates: they compute an unbiased sparse stochastic gradient for s by sampling and then update s using a stochastic proximal gradient method. The unbiased sparse stochastic gradient used in SOTA cannot enjoy variance bound that scales with the mini-batch size. In contrast, we just compute unbiased stochastic gradient for the sampled coordinate of s, and perform stochastic gradient descent sampled coordinates and leave other coordinates unchanged. It is this difference that makes analysis more involved and leads to parallel speed-up.
4 Analysis
In this section, we present the convergence results for our algorithms. We emphasize the contributions of our convergence analysis for both convex and non-convex seltings compared to Zhu et al. (202 (i) our convergence analysis for the convex case is more refined, leading to an optimal convergence rate which implies a parallel speed-up terms of mini-batch size; (ii) our analysis for the non-convex case also improved, which not only enjoys a parallel speed-up but also removes strong boundedness assumptions of st,k, s and the pairwise loss values at all iterations.

---

Published in Transactions on Machine Learning Research (09/2025)
For analysis, consider the following optimization problem:
1 Σ (i n
min F(u,s) uell.se5
(13)
where RR R is closed proper convex and lower-semicontinuous, 9; (u, - R is possibly non-convex, and U are convex closed sets, 9: (u, (()) = Es, (() It is equivalent to the following min-max problem:
R min max (u,,,,y) = () well yey
(14)
s=1
Compared to problem analysis for solving
excludes parameter s'. Since the update of 5 almost the same as w, our 13 can be easily extended to STACO1 and STACO2.
13
4.1 Assumptions
We first outline assumptions underlying our analysis. Notably, these assumptions are easily satisfied for TPAUC maximization when the loss function is Lipchitz continuous.
Assumption 4.1. For any ie [n], suppose fi Lipschitz continuous, i.e. there exists Cj, Cg 0 such that
[f(2)) - Cylu- (.(u,s()) g: (ū, (0)) s C, (Ilu u/2 + -s(0-s(0))
for any uE R, u 2 and ,(),s())) S, Assumption 4.2. For any i [m]. there exists finite of of. of such that
Eg, (u, a (u, ( ( s sog
Eg. 600 G(o (G) - c || 1| cof Eg, G (G) c. c soz $
for stochastic subgradients (G) (Gi) (1, (G) Besides, there exists 5² such that
(G) 0
0 (u, at any e el,, and s(1) S,.
Ej
1
0 c
502.
m
for any Gf (,,s u ( e,, and y V. Note that under Assumption 4.1 have 82 s CgC2
4.2 Convex Case
We first analyze the Algorithm 3 which aims to solve the problem Q14 when both fi and gi convex for any i [n]] The analysis is motivated by techniques proposed in Waan & Yang However, the problem they considered is 1 E. (u)) which excludes the primal parameter s. Notably, the analysis of convergence of primal paramoter u more tricky than w since its updating only lics in selected coordinates each itcration.
Theorem 4.3. Under Assumptions 4.1 and 4.2 when (; (()) conver w.r.t s, let r = Oc)), B -O(),, and
O(Be), STACO1 can make E[F(u,s) F(u",s*) S e after T iteralions, where u= T-1 U ElD St+1
of c Cio nCfaz
se Be BSc Sez BSE
Remark. The proof is included in Appendix C.2.2 The above convergence rate implies a parallel speed-up in terms of the positive batch size S and negative batch size B. When we use full information at each iteration, which mcans do 0,0, 0,02 = 0, 0,5 n., the above complexity reduces to 0(1/2),, which is a standard complexity for non-smooth convex optimization (Nesterov al. 2018). In addition, the dominating term ((n((e)) matches the lower bound proved in Wang & Vang
7

---

Published in Transactions on Machine Learning Research (09/2025)
4.3 Non-convex Case
Now we consider the non-convex case when ga is weakly convex stated in the following assumption. Assumption 4.4 (weakly convexity of 9:). For any i [n], we suppose that s(,,s(() is p-weakly convex to and g(1) for any u E and g(t) E Si ie., 9.(+) & 1-12 is convex, where is positive number.
It is sometimes difficult to find an e-stationary point (u,s) of the non-smooth function F, i.e., dOs (F,, e. For example, an e-stationary point of function f(x) = |x| does not exist for 0 s < unless it the optimal solution. To address this problem, (Davis & Drusvyatskiy 2018) proposed using the stationarity of the Moreau envelope of the problem as the convergence metric, which has become a standard metric for solving weakly convex problems.
Given p-weakly convex function f F:R R, its Moreau envelope is constructed as
[((w)
1 w x12] 27
(x)
= min we'd
(15)
where ry is a positive constant. For a p-weakly convex function f, it can be shown that fy is smooth when $ > p (Davis Grimmer 2019) and its gradient is
(xx()) (x- f(x)).
(16)
7
where
prox,,((x) == mrg] |w -x(2)-
(17)
27
w
Notice that when $ > p. the minimization in problem strongly convex, which ensures frox,f(x) is uniquely defined. Morcover, for any point e Rd, the proximal point x == f(ox,,(x) satisfics (Hu et al.
2023
| - =
( (ist(0,0f(x)) (
(18)
Thus if (x) e,, we can say is close to a point xi that is e-stationary, which is called nearly e-stationary solution of (x). Given an iterate Xt, a common idea is using the stochastic subgradient method (SSG) to approximately solve 15 with x Xx, namely, to compute a solution X such that
1 | x
X++1 s prox, (x,) )= arg min f(x)
+
(19)
2
Then X returned by the SSG method will then be used in the next iterate. Inspired by Ralique et. al. 2022 we consider the following update according to equation
(uH11, a arg min arg max {L., su; yey
where L, (u,
(y gi gi (())
f7 ()))
1 |u 1-'1- 2
||s ss112.
(20)
n
2ny
Theorem 4.5. Under Assumptions
2.2 and 4.4 STACO2 with 7 20,0' 1T = 0 3r O
1
a: = O(Be), and K, O
converge to e-stationary point of (u, s)
in
n iterationn, where (u, minas F(ū,)) | u
of Cioi 8 nCRc2 nCGa3 Be Set
na BSel
2 2mm
Set
BSet
is a Moreau envelope of F(,,s).
Remark The proof included Appendix C.3.4 We compare the above result with the complexity of SOTA and SONX. In particular, SOTA has a complexity of ((#) result, which cannot show any mini-batch
n speedup. SONX has an iteration complexity of O T3 in Theorem C.4 (Hu et al. 2023). In comparison,
our complexity 0 B has better dependence B.
8

---

Published in Transactions on Machine Learning Research (09/2025)
5
Experiments
We evaluate the empirical performance of our proposed algorithm against baselines for Two-way Partial AUC Maximization (TPAUC) in a convex setting for learning lincar models and a non-convex setting for learning deep models.
5.1 Settings
Datasets. For linear model experiments, we use three datasets in (Chang & Lin 2011), namely HIGGS, SUSY, and ijennl. For SUSY and HIGGS, we use the first 80% of the data the training dataset and the remaining 20% as the testing dataset. For ijennl, we follow the existing split. in (Chang & Ling 2011 1011). To create imbalanced datasets for HIGGS and SUSY (ijennl itself is imbalanced), we randomly remove 99.5% positive data. For deep learning model experiments, we use two molecule datasets from the Stanford Open Graph Benchmark (OGB) website (Hu et al. 2020) and two biomedical image datasets from MedMNIST (Yang et al. 2023a), namely moltox21 (the No.0 target), molmuv (the No.1 target), nodulemmist:dd, and adrenalmmist3d. Those four datasets are naturally imbalanced. The task in molecular datasets is to predict certain properties of molecules, and the task in biomedical image datasets is binary classification. The statistics of datasets are presented in Table 5 in Appendix B
Models. For linear model experiments, we let (x) w datasets moltox21 and molmuv, we use Graph Isomorphism Network (GIN) (Xu et al.) 2018) as the backbone model, which has 5 mean- mean-pooling layers with 64 hidden units and 0.5 dropout rate. For image datasets nodulemnist3d and adrenalmnist3d, we learn a convolutional neural network (CNN) and use ResNet18 (He ee al. 2016). We utilize the sigmoid function for the final output layer to generate the prediction score and set the surrogate loss f(-) as the squared hinge loss with a margin parameter (Zhu et al. 2022
x. In deep model experiments, for molecule
Basclines. We evaluate our algorithms, STACO1 and STACO2, by comparing their training and testing performance against various baselines, while STACO1 is for linear model and STACO2 is for deep model. Specifically, we benchmark our methods against other approaches that optimizes different objectives, including CE for optimizing the cross-entropy loss, AUCM for optimizing an AUC min-max margin loss (Yuan et al. 2021b), SOTAs for optimizing a soft TPAUC loss (Zhu et al. 2022), SOTA (Zhu et al.) 2022). and SONX for optimizing the same TPAUC loss ours (Hu et al.) 2023 and PAUCT for optimizing instance-wise TPAUC loss (Sao et al. )
Evaluation Metrics. For linear and deep learning model experiments, we evaluate TPAUC with two settings, i.e., TPR 2 0.5 and FPR s 0.5, and TPR 2 0.25 and FPR s 0.75.
Hyperparameter Tuning. In linear model experiments, the model is trained by 3000 iterations, and the learning rate is decreased by 10-fold on the 500th, 1500th, and 2500th iterations for all methods. For deep learning experiments, the model is trained by 60 epochs and the learning rate decreased by 10-fold after every 20 epochs for all methods. In addition, previous studies (Yuan et al. 2021b Zhu et al.] 2022). The pre-trained model is trained for 60 epochs using CE loss with an Adam optimizer on the training datasets, and the initial learning rate is 1e-3 which is decreased by 10-fold on the 30th and 45th epochs. We tune the step sizes of STACO1, STACO2, SOTA, PAUCI, and AUCM in the range {le-2, 1e-1, 5e-1}, and tune the step sizes of SONX, SOTAs, and CE in the range (1e-3, 1e-2, 1c-1]. For STACO1, STACO2, SOTA, and SONX, we fix the margin parameter of the surrogate loss 0.5, and tune the rate parameter 0n, O, in (0.4, 0.5,0.75) for reporting testing performance. For SONX, we fix the moving average parameter as 0.9 and tune the momentum parameter in the range {0, 1e-3, 1e-2, le-1}. For AUCM, we choose the momentum parameter as 0.9, the margin parameter of the surrogate loss as 0.5, and tune the hyperparameter y that controls consecutive opoch-regularization in {100, 500, 1000}. For SOTAs, we fix 70 = 71 = 0.9 and tune X, X' in {0.1, 1.0, 10). For PAUCI, we lune l in [1, 10), C1 02, μ, in [0, 1), m in [10, 100] and x in [2, 6]. For all algorithms, we choose the weight decay parameter as 2c-4. Without specific statements, cach algorithm samples 64 data points in each itcration. We exccute all experiments using golld-coos--valdaatinn performance and report the average and standard deviation over multiple runs.
pre-train the model for deep learning experiments following
evaluate testing performance based on the best validation
9

---

Published in Transactions on Machine Learning Research (09/2025)
5.2 Results
1600 0200000
SONA
SUNK
SUM
S18001
S1AC0L
S
S
Teaal huinng Tine bcales)
Tetal Tuini Time (cclee) (b) SUSY
Bea Training Time basaedd) (c) HIGGS
Toaa Training Time tocaled) (d) SUSY
(a) HIGGS
Figure 1: Training TPAUC Curves of STACO1 and SONX on two different datasets. TPAUC (0.5, 0.5) results, and the last two shows the TPAUC (0.75, 0.75) results.
The first two shows the
8
S01A
4.0
SONA
3
32
SONE
431
SONE
SONX
SON STAC02
STA002
STA002
03
STAC02
g 4m
(a) mtlmuv(t1)
(b) (1))
(c)
adrenalmnist3d
(d) nodulemnist3d
474
507a
SOTA
SOTA
507A STACO2
12000775 0.70
STA002
430
SONo
STAC02
SDNX
STACO2
2ete hain Time Ocstec)
Tetal Thin ng Time ocsted)
Too Training Time (eowed)
Tta Trainin Time (eoled)
(e) molmuv(t1)
moltox21(t0)
(g) adrenalmnist3d
(h) nodulemnist3d
Figure 2: Training Loss Curves of STACO2, SOTA, and SONX on four different datasets. The first row shows the Loss (0.5, 0.5) results, and the second row shows the Loss (0.75, 0.75) results.
0003
SOMK
SONY
0.05
STAC02
STAC02
STACO2
5300
8425
0300
G12
Teaal Trckiing Stece bookel
Boid Traliing Stap Dedket
Rdd Tari1g Stegs Octlld
(a) Batch Size=16 16
(b) Batch Size= 64
(c) Batch Size= 256
Figure 3: Negative sample batch size (B) benefits of STACO2 over SONX for training on ogbg-molmuv (t1) at 16, 64, and 256 batch size.
Training Results. Under two different metrics, we compare the training performance of the linear model between STACO1 and SONX in Figure [ and the deep learning model among STACO2, SOTA, and SONX in Figure 2 We exclude SOTA from linear model experiments since SOTA is designed for optimizing deep learning models. In the lincar model experiments as shown in Figure 1 we plot the TPAUC values throughout the training process. The results demonstrate that STACO1 exhibits strong and stable performance, consistently outperforming SONX on both the HIGGS and SUSY datasets in the (0.5, 0.5) and (0.75, 0.75) settings. These findings indicate that STACO1 is more efficient than SONX in maximizing TPAUC. We also observed across all datasets, there is an abrupt drop and subsequent rise in performance. This is due to the excessively large step size. Once the step size is reduced, training returns to normal.
that in Figure [
10

---

Published in Transactions on Machine Learning Research (09/2025)
Table 2: TPAUC on the test data of linear and deep models. (0o, 01) represents TPR 2 1 1-00, 0o, FPR s 01.
Results are reported as mean(std).
Linear Model
Deep Model
Metries
Methods
HIGGS
SUSY
geunn
molhmuy (11)
mu1lux21(10)
uodulemmistt.3
adrenalmmiss 3cd
CE
(.001().001)
0.300(0.010)
0.207(
0.715(0.166)
0.267(0.042)
0.657(0.037)
(.507(
AUCM
0.122(0.001)
0.512(0.015)
0.487(0.008)
(.114)
0.279(0.038)
0.672(0.021)
(0.52))
SOTAs
0.108(0.001)
0.484(0.001)
0.637(0.030)
(0.
0.325(0.030)
(.089())119)
(.495(0.090)
00.5,0.5)
PAUCI
0.138(0.002)
0.519(0.001)
0.661(0.018)
0.820(
0.253(0.032)
(0.01)
(0.01(
SONX
0.110(0.009)
0.516(0.001)
(..33))
(.865)
0.256(0.023)
(.655(0.0355
0.310(0.012)
STACO
0.520(0.00 0.158(0.003)
(0.02))
(0904)0.048)
0.325(0.023)
0.707 (0.00))
0.546(0.047)
CE
0.354(0.002)
0.612[0.000)
0.581().014)
(.871(
(.037)
0.825(0.016)
0.750(0.066)
AUCM
0.435(0.004) 0.726(0.002)
0.728(0.061)
(0.51(0.066)
0.630(0.027)
(0.016)
0.772(0.014)
SOTAs
(0.00().0002
0.746(0.009)
0.813(0.016)
0.821 (0.070)
0.614(0.056)
0.838())012)
0.763(0.054)
(0.75,0.73)
PAUCI
0.4742(0.003)
0.749(0.007)
0.830(0.030)
0.883)
0.616(0.030)
(.804().014)
0.7642(0.015
SONX
(..07)
0.748(0.000)
0..10().049)
(0.029)
0.626(0.026)
(0.033
0.772(0.021)
STACO
0.752(0.000) 00.84().000)
0 0.839 (0.024)
0.945(0.024)
0.638(0.041)
0.856 0.856 (0.003)
00.80().013)
TRUUII 0.50
1=262
7=502
y=1e3
y=267
Epoch
(a) moltox21(t0)
(b) nodulemnist3d
(c) moltox21(10)
(d) nodulemnist3d
Figure 4: First two figures shows the TPAUC (0.5,0.5) training curves STACO2 with different 7; last two
figures shows the TPAUC (0.5, 0.5) testing results of STACO2 with different y, The experiment is conducted datasets ogbg-moltox21 (t0) and nodulemnist3d.
In the nonlinear model experiments as shown in Figure 2 STACO2 demonstrates competitive performance in terms of training loss reduction across all four datasets compared to SONX and SOTA. In both the (0.5, 0.5) and (0.75, 0.75) settings, STACO2 achieves lower comparable loss values while maintaining stable training trajectory. These results indicate that STACO2 is effective in minimizing loss and optimizing model performance, further supporting its advanlage over SONX and SOTA.
Due to space limit, we present more training results in Figure 5 in Appendix B
Testing Results. Under two different metrics, we present the testing results for linear and deep learning models in Table [2] For the linear model, STACO1 consistently outperforms the baseline methods across various datasets, demonstrating its robustness and strong generalization capability across different datasets and evaluation criteria. Similarly, for the nonlinear model, STACO2 achieves significant improvements over existing methods. Notably, compared to SONX, STACO2 exhibits a more pronounced advantage in testing performance than in training, suggesting superior generalization when optimizing the exact TPAUC loss.
We do not include SOTA (Zhu et al. 2022 in the above comparison, since SOTA quite similar to STACO2 thus they have similar testing results. However, we must point out that the convergence of SOTA much slower than STACO2 since it has to update all the coordinates of in problem (2) As shown in Figure STACO2 significantly faster than SOTA.
5.3 Ablation Study
Effect of Batch Size. We examine the impact of negative batch size B on the performance STACO2 and SONX to verify the mini-batch speedup of STACO2 over SONX. Specifically, we tune the negative batch size in [16, 64, 256]. In Figure 3 we present the training loss curve for STACO2 and SONX on dataset ogbg-molmuv (L1). Our results show that as batch size increases, STACO2 exhibits greater convergence
11

---

Published in Transactions on Machine Learning Research (09/2025)
improvement compared to SONX, indicating that it benefits more from a larger batch size. This observation
is consistent with Theorem 4.5 i.e., STACO2 can achieve full mini-batch speedup than SONX.
Effect of Epoch Decay Factor. We examine the impact of epoch decay parameter y on the training performance of STACO2. In Theorem 4.5 must be less or equal than 2Cyp' 1 where Cy is the Lipschitz
constant for function fi and is the weakll-convexity parameter for function Ji. In TPAUC maximization problem, Cy is 1. However, P in practice is difficult to determine. Therefore, we tune in the range {300, 500, 1000) in the experiment. Additionally, we conduct 7 =1e7 case for our ablation study. Notably, STACO2 reduces to STACO1 if y equals an infinitely large number. The results are presented in Figure ! We observe that an appropriate value of y can yield better training results, verifying Theorem 4.5 and demonstrating the importance of the epoch decay parameter y for primal-dual algorithms in deep learning.
Effect of Surrogate Loss L. We investigate how the choice of surrogate loss function é influences the final experimental results. Specifically, we consider three common losses: square hinge loss, square loss, and hinge loss, and evaluate their performance across various datasets. The results show that our algorithm STACO performs consistently well and remains stable across different surrogate losses, indicating that the choice of has limited impact on the final performance.
Table 3: Comparison of performance metrics using different nonsmooth losses across datasets. Each entry is reported as mean(std).
Methods
HIGGS
SUSY
ijeunl
linge square
square
hinge
hinge square
squaaee
hange
Einge square
squaze
linge
CB
0.354(0.002)
0.376(0.083)
(.341(0.004)
0.612(0.004)
0.599)(0.004)
0.639(0.00))
0.581(0.008)
0.560(0.D04)
0.604(0.0083)
AUCM
(:435(0.002)
0.162(0.008)
0.111(0.900)
0.726(0.088)
0.748/0.004)
0.699(0.004)
0.725(0.00) (01)
0.752(0.003)
(0.00(0.005)
SOTAs
(0.000)
0.467(0.004)
0.415(0.004)
0.7.6(0.008)
0.773(0.063)
0.719(0.002)
0.813/0.002)
0.800)
(1.87(0.004)
PAUCI
0.474(0.003) 0.500(0.004)
0..50(
(0.44())004)
0.724(0.003)
0.777(0.004)
.000))0.002)
(.807(0.003)
00800(0.003)
SONX
(.447700.0133 0.472(0.003)
0.420(0.004)
0.748(0.008)
0.773(0.003)
0.723(0.0033
0.810(0.0022
0.786(0.0033
(1804))
STACO
0.981(0.0001)
(.500(
0.158(0.004)
(0.000
0.779(0.003)
0.725(0.004)
0.839(0.024)
0.866(0.004)
0.812(0.001)
5.4 Training Efficiency
To demonstrate the training efficiency of our algorithm, we compare the per-iteration runtime of STACO, PAUCI, SONX, and SOTA across four benchmark datasets, as shown in Table 4 STACO consistently achieves the lowest runtime per iteration across all datasets. Notably, it surpasses the second-best method, SONX, by a substantial margin, particularly larger datasets such as molmuv and moltox21. These results highlight the superior computational efficiency of STACO, making it compelling choice for large-scale or time-sensitive applications.
6 Conclusion
In this paper, we proposed Iwo novel stochastic primal-dual double block-coordinatee algorithms for optimizing two-way partial AUC (TPAUC), effectively addressing imbalanced data classification. By leveraging stochastic updates for both primal and dual variables, our methods achieve improved convergence rates in both convex and non-convex settings. Empirical results demonstrate faster convergence and superior generalization across benchmark datasets, establishing new state-of-the-art in TPAUC optimization for real-world applications.
Table 4: Training time per itcration (in scconds) on different datascts.
Methods
molmuv
moltox21
nodulemnist3d
adrenalmnist3d
SOTA 14.80
8.01
2.02
2.23
SONX 9.78
4.54
1.62
1.76
PAUCI
12.54
5.72
2.51
2.74
STACO
8.72
3.96
1.40
1.48
12

---

Published in Transactions on Machine Learning Research (09/2025)
Acknowledgments
We are grateful to the reviewers' comments. LZ, BW, TY were partially supported by NSF grants 2306572 and 2147253.
References
Ahmet Alacaoglu, Volkan Cevher, and Stephen J Wright. On the complexity of practical primal-dual coordinate method. arXiv preprint arXiv:2201.0768, 2022.
C.-C. Chang and C.J.. Lin. Libsvm: a library for support vector machines. TIST, 2(3):27, 2011.
Damek Davis and Dmitriy Drusvyatskiy. Stochastic subgradient method converges the rate o -14{1//4) weakly convex functions. arXiv preprint or arXiv:180.002885 2018.
Damek Davis and Benjamin Grimmer. Proximally guided stochastic subgradient method for nonsmooth, nonconvex problems. SIAM Journal on Oplimization, 29(3):1908 1930, 2019.
Erfan Yazdandoost Hamedani, Afrooz Jalilzadeh, and Needet Aybat. Randomized primal-dual methods with adaptive step sizes. In International Conference Artificial Intelligence and Stotislics, pp. PMLR, 2023.
James A Hanley and Barbara J McNeil. The meaning and use of the area under a receiver operating characteristic (roc) curve. Radiology, 143(1): 1982.
Kaiming Hc, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual lcarning for image recognition. In Proceedings of the IEEE conference on computer vision and pottern recognition, pp. 770-778, 2016.
R. Herbrich, T. Graepel, and K.: Obermayer. Support vector learning for ordinal re- gression. In International Conference on Neural Networks, 1999.
Quanqi Hu, Dixian Zhu, and Tianbao Yang. Non-smooth weakly-conver, finite-sum coupled compositional optimization. Xiviv preprint arXiv:2310.002: 2023.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovee. Open graph benchmark: Datasets for machine learning on graphs. Advonces in neural information processing systems, 33:22118 112211122213,,, 2020.
Afrooz Jalikzadeh, Erfan Yazdandoost Hamedani, and Needet Aybat. A doubly-randomized block-coordinate primal-dual method for large-scale saddle point problems. arXiv preprint arXiv:1907.03880 2019.
Anatoli Juditsky, Arkadi Nemirovski, and Claire Tauvel. Solving variational inequalities with stochastic mirror-prox algorithm. Stochastic Systems, 1(1):17 58, 2011.
Purushottam Kar, Harikrishna Narasimhan, and Prateck Jain. Online and stochastic gradient methods for non-decomposable loss functions. Advances in Neural Information Processing Systems, 27, 2014.
Harikrishna Narasimhan and Shivani Agarwal. Sympauctight: new support vector method for optimizing partial auc based tight convex upper bound. In Proceedings of the 19th ACM SIGKDD internalional conference on Knowledge discovery and data mining, pp. 167-175 175, 2013.
Yurii Nesterov al. Lectures on conver optimization, volume 137. Springer, 2018.
W. Ogryczak and A. Tamir. Minimizing the sum of the k largest functions in linear time. Information Processing Letters, 85(3):117-122, 2003.
Qi Qi, Youzhi Luo, Zhao Xu, Shuiwang Ji, and Tianbao Yang. Stochastic optimization of areas under precision-recall curves with provable convergence. Advances in neural information processing systems, 34: 1752-1768 2021.
13

---

Published in Transactions on Machine Learning Research (09/2025)
Hassan Rafique, Mingrui Liu, Qihang Lin, and Tianbao Yang. Weakly-convex concave min max optimization: provable algorithms and applications in machine learning. Oplimizalion Methods and Software, 37(3): 1087 1121, 2022.
Huiyang Shao, Qianqian Xu, Zhiyong Yang, Shilong Bao, and Qingming Huang. Asymptotically unbiased instance-wise regularized partial auc optimization: Theory and algorithm. Advances in Newral Information Processing Systems, 0888667-336673 2022.
Huiyang Shao, Qianqian Xu, Zhiyong Yang, Peisong Wen, Gao Peifeng, and Qingming Huang. Weighted roc curve in cost space: Extending auc to cost-sensitive learning. Advonces in Neural Information Processing Systems, 36:17357-17368, 2023.
Bokun Wang and Tianbao Yang. A near-optimal single-loop stochastic algorithm for convex finite-sum coupled compositional optimization. In Forty-second International Conference on Machine Learning.
Mengdi Wang, Ethan X Fang, and Han Liu. Stochastic compositional gradient descent: algorithms for minimizing compositions of expected-valut functions. Mathematical Programming, 161 161(1-2):419444 449, 2017a.
Mengdi Wang, Ji Liu, and Ethan X Fang. Accelerating stochastic composition optimization. Journal of Machine Learning Research, 18:1-23, 2017b.
Zheng Xie, Yu Liu, Huo-Yuan He, Ming Li, and Zhi-Hua Zhou. Weakly supervised auc optimization: a unified partial auc approach. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2024.
Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanic Jegelka. How powerful are graph neural networks? arxiv preprinl ar arx: 310000826, 2018.
Hanfang Yang, Kun Lu, Xiang Lyu, and Feifang Hu Two-way partial auc and its properties. Statistical methods in medical research, 28(1):188-19)) 2019.
Jiancheng Yang, Rui Shi, Donglai Wei, Zequan Liu, Lin Zhao, Bilian Ke, Hanspeter Pfister, and Bingbing Ni. Medmnist v2-a largo-scale lightweight benchmark for 2d and 3d biomedical image classification. Scientific Dala, 10(1):41, 2023a.
Tianbao Yang and Yiming Ying. Auc maximization in the era of big data and ai: A survey, ACM Computing Surveys, 55(1): 37, 2022.
Zhiyong Yang, Qianqian Xu, Shilong Bao, Yuan He, Xiaochun Cao, and Qingming Huang. When all we need is a piece of the pie: A generic framework for optimizing Lwo-way partial auc. In International Conference Machine Learning, pp. 11820- 11829. PMLR, 2021.
Zhiyong Yang, Qianqian Xu, Shilong Bao, Yuan He, Xiaochun Cao, and Qingming Huang. Optimizing two-way partial auc with an end-to-end framework. IEEE Transactions on Pottern Analysis and Machine Intelligence, 45(8):10228- 11110222-12666,,, 2022.
Zhiyong Yang, Qianqian Xu, Shilong Bao, Peisong Wen, Yuan He, Xiaochun Cao, and Qingming Huang- Auc-oriented domain adaptation: From theory algorithm. IEEE Tronsactions on Pottern Analysis and Machine Intelligence, 45(11):14611-1417 2023b.
Zhuoning Yuan, Zhishuai Guo, Nitesh Chawla, and Tianbao Yang. Compositional training for end-to-end deep auc maximization. In International Conference on Learning Represenlations, 2021a
Zhuoning Yuan, Zhishuai Guo, Yi Xu, Yiming Ying, and Tianbao Yang. Federated deep auc maximization for hetergencous data with a constant communication complexity. In International Conference on Machine Learning, pp. 12219 12229. PMLR, 2021b.
Junyu Zhang and Lin Xiao. Stochastic varianco-reduced prox-linear algorithms for nonconvex composite optimization. Mathematical Programming, pp. 1 1-43, 2022.
14

---

Published in Transactions on Machine Learning Research (09/2025)
Xinwen Zhang, Yihan Zhang, Tianbao Yang, Richard Souvenir, and Hongchang Gao. Federated compositional deep auc maximization. Advances in Newral Information Processing Systems, 11:9648-9660) 2023.
Yuchen Zhang and Lin Xiao. Stochastic primal-dual coordinate method for regularized empirical risk minimization. In ICML, pp- 353 -33-361, 2015.
Zhe Zhang and Guanghui Tan. Optimal algorithms for convex nested stochastic composite optimization. arXiv preprint 10111:201..0007, 2020.
Dixian Zhu, Gang Li, Bokun Wang, Xiaodong Wu, and Tianbao Yang. When aue meets dro: Optimizing partial auc for deep learning with non-convex convergence guarantee. In International Conference on Machine Learning, pp. 27548 27573. PMLR, 2022.
15

---

Published in Transactions on Machine Learning Research (09/202))
A Vanilla Algorithm
Algorithm Simplified STACO1
Initialize Ug E L1 Su S, Yo e do 3: Sample a batch S:
2: for L= 0,.....,77
m.. 1
4: for each e St do
5: Sample independent size-Bt B mini batches , from P.
Compute of0 (B.") s, B
Compute G()) (B augi (()) 6 (((()) E ( (()(())) f. (y 2/2 (y(() - -y. (1))
7:
(0) arg max maxy Yey
8:
9:
1
5t 3 Ens,
10: end for
11: For each i St yi+1 = =y Sp =s
(1)
(1)
(1) (0)
12:
U1+1 75 Eks. yol (
13: end for
14: ú= T Σ,-0 & S= = T Σi-n S
1
15: Return 0,S
Algorithm 4 Simplified STACO2
1: Initialize ug U, So 6 S
2: for t= 1, 7-1 do
3: Initialize yt,0 y
4: Set u1 Ur Sr,0 = St
for k= 0. 1 do
Sample batch St, (1....,,n, n), |S S for each i Sr, do
Sample independent size-B mini-batches B B(2 from P.
8:
Compute ( (11)) gu (1). B(1)
9:
Compute g())
(,6,1 (B(1) Ou.giuu. s,,t (.k)
g(1)
Gt. (B!)) E (u (0) (())
10:
Yt,k+1 arg maxy (r00()) (1) (1(1) () ب (y - -y (1)
(6)
11:
(i)
(((0), 3 Ens, Vek.1 (0)
(B [ |(0) 23, (5 (s (
12:
1t,+1 arg min
13:
end for
14:
For each i St,k, 31,411 Yekk 6k++1 1
(1) (i)
(1)
15:
U1 arg mig u, 5 Ens., Nt,k+1 11 end for
(1) (1)
(B(1) ( -u,o)) the Iu u 12]
16:
Compute U; = 1 kk-1
K. 2k=0 Ug = 1 Ex-r S1
17:
Ki
18:
Set U U,,81+1 S;
19:
end for
20:
Return sT
16

---

Published in Transactions on Machine Learning Research (09/2025)
Table 5: Datasets Statistics (for nodulemnist3d and adrenalmnist3d, we follow the given training, validation and testing split). The percentage in parenthesis represents the proportion of positive samples.
Dataset
Train (Validation)
Test
HIGGS
4157561 (0.5%)
1039299 (0.5%)
SUSY
2181312 (0.5%)
544489 (0.5%)
ijennl
49990 (9.71%)
91701 (9.5%)
ogbg-moltox21 (t0)
6556 (4.2%)
709 (4.5%)
ogbg-molmmv (t1)
13025 (0.17%)
1709 (0.35%
nodulemnist3d
1,158
(25.4%) / 165 (25.4%)
310 (20.6%)
adrenalmnist3d
1,188
(21.8%) 98 (22.4%)
298 (23.1%)
1x
SONX
SONK STACO1
SONX STACO1
STACO1
Looi3. 0.5)
Iotal training Time (sceled]
lotal traning Time (scalec)
ttail Trairing Time (scaled)
(a) ijennl
(b) SUSY
(c) higgs
SONK STACO1
SONX STACO1
SONO STAC01
Look0 75, 0.751
0.75)
023
Total Triiiing Time Iscaled!
Total Taning Time (scalec)
Total Training Time (scaled)
(d) ijennl
(c) SUSY
(f) higgs
Figure 5: Training loss Curves of STACO1 and SONX on three different datasets. The first row shows the Loss (0.5, 0.5) results, and the second row shows the Loss (0.75, 0.75) results.
109
50TA
SOTA
537A SOHX
Soncs
SDNX
STA002
STA002
STAC02
SIA002
Roinin Time
Rriniing
Traiiing Time
(a) molmuv(t1)
(b) moltox21(10))
(c) nodulemnist3d
(d) adrenalmnistt33
0.0 22 100oo0
Thtal Time Oeatte)
Tetal Time
Tea Training Time tecelet) (g) nodulemnist:d
CS0
Tht Time tecales)
C30
(0) molmuv(t1)
moltox21(11)
(h) adrenalmmist33
Figure 6: Training TPAUC Curves of STACO2, SOTA, and SONX four different datasets. The first shows the TPAUC (0.5, 0.5) results, and the second shows the TPAUC (0.75, 0.75) results.
17

---

Published in Transactions on Machine Learning Research (09/2025)
B More Experiment Results
B.1 Additional plots for training loss curves
Figure presents the training loss curves of STACOL and SONX across three different datasets under two evaluation settings, (0.5, 0.5) and (0.75, 0.75). The results indicate that STACO1 consistently achieves lower and more stable loss values compared to SONX across all datasets. Notably, the variance in training loss is lower for STACO1, suggesting improved stability during optimization. The only exception is Figure 5c, which corresponds to optimizing the loss with (0.5, 0.5) weights. We believe this is a limitation of the primal-dual algorithm, which involves two learning rates. In practical applications, improper tuning of these rates may lead to training instability. Besides, it is important to note that the loss curve is less stable compared to deep learning experiments, primarily due to the absence of pretraining for the linear model.
B.2 Additional plots for training TPAUC curves
Figure D presents the training TPAUC curves for STACO2, SOTA, and SONX across the four datascts. In both TPAUC (0.5, 0.5) and TPAUC (0.75, 0.75) settings, STACO2 demonstrates competitive performance compared to SOTA and SONX, with better stability and faster convergence speed. Specifically, in some cases, STACO2 achieves superior results, particularly later training stages, indicating its effectiveness optimizing TPAUC objectives.
C Proof
C.1
Preliminary Lemmas
Throughout the proof, for a space X, we define its diameter with respect to the measure v0() 2 11-12 as Dx [maxxex (xx) minxex (x)]11/ Besides, a b means that there exists c, such that cb s s Cb. We first present a lemma here that will be useful in our later analysis.
Lemma C.1 (Lemma 4 in Wang & Yang). Suppose that the function o: + E is convez, closed domain X and é u-conver with respect to Euclidean distance function d(x,y) ||x yll for any x, x' e X, i.e., (x(x) + nd(x. x)), we obtain
(xx) 2 (xx') (x'(x), x x')= pd(xxx') Vx,x's E X. For & =
((x) (xx)= nd(xx x) (1 p)d(x nd((t. V
(21)
C.2
Convex Case
In this section, we present the proof of the convex case. We begin by defining virtual sequences for Algorithm The virtual sequences y and s are calculated with full coordinates, which is casier to bound analyze.
Thus, we also hope to bound the difference between true sequences and virtual sequences.
Definition C.2 (virtual sequence). In Algorithm 3 virtual sequence {y.) is defined follows:
arg max y g. (B()) ()
1
-x(0--(()) -/)) ie [n].
(22)
F+1
y
2a
Additionally, a virtual sequence } is defined as follows:
5 arg min
(1 ((()
(5() -000
ie [n].
(23)
23
Next, we present a useful lemma, which is helpful in bounding y related error term.
18

---

Published in Transactions on Machine Learning Research (09/2025)
Lemma C.3 (Lemma. 9 in Wang & Yang]. Suppose (51), { are virtual sequences for any t 0 in Algorithm
Then, for any A 0, V, it follows that:
1 2ncx
1 (ly yrl2 ly 3ell2 18. -v-ll)
(Iy yel22 1 ly 1y-yy+1 (y-ve118)+ A1 (Ily ---1-12-- ly S
2a.
20.5
1 (1
18c+1 - vella-
(24)
2om
A1S'
We define that G. is the o-algebra generated by St and Fi is the o-algebra generated by Se, Note that G, c Fr and V4+1 is F--mcasuralle. Now we proceed to show the descent lemma.
Lemma C.4 (Descent Lemma). Under Assumption 4.1 and 4.2 suppose (5.), (8e)) ( are virtual sequences for Algorithm 3 Then, for any [0, I], laking expectation over Fr, it holds that:
[[
S,
[ uell
- E EElu- u (12)
-
1
IIs s:112
Ells 12)
as (ILY -vell E Ely yeta 12)
1
2n
238
1 -1y-8:12 ly 8t-1
1
+ as
(Iy 8el12 by S1.13
as
Soog
aod
309
n
30302
+ +640070z+
(25)
2Bn
2B
B
S
B
where Ω max max(11 B)
Proof. See Appendix C.2.1
C.2.1 Proof of Lemma C.4 Proof. By Definition, we have
- ((u,s,ye.))
1
Σ (1(1))
(1L-1,) -y:
Σ (1) -f (+(2))
n
1
(y)
Σ
"
f/ (y
Σ (7
n
El
Σ 41 (g: (1, s()
Σ l (g: (u.
(26)
n m1
1=1
Using the convexity of Hi, obtain the following upper bound:
L( L(u,),ytt))
(1)
v(1) ( 1
Σ - ()()))
1
6
n
n
H-1 (ge( - go (u: st))
+
Σ
2
(0)
((C() u. - u) (s: (({;-s))
(27)
11
==1
We now analyze terms I and II separately. For term I, we decompose as follows:
I=
Σ
yy
y
--1
n
(+)
(t)
(0)
(B()) + Σ (y (0)
(12) ( -00 (B()))
19

---

Published in Transactions on Machine Learning Research (09/2025)
For term II, by decomposition we obtain:
II
1
(
1 E u 1
Σ
u1+1
5
SES
-
611
Σ 1+1
(B -
y
(i) G (B(0)) 8-
Sc-1
2
n F1
3 12 G
st 5
(28)
Combining all terms above, we arrive at the key inequality:
U( - L(u,,,
$ 1
(y 14 (b(
()) 1 E
ml
1
(y( - (9:(1)), - (
Σ s (411 - -::--gguu,, (1,
n
-
n
1-1
Σ
141
(8)
21 (B(
1 Σ
( (1)
( Uc+1
5
Σ
11)
G (B(0))
SS
n
ieS,
C2
1
G - u
11
H+1
(6(9)) - G(.2) s St+1
Σ
n
y
l+1 1,2
20 (B()))
Set1
1=1
Ca
1
- Σ 2.2 St -
(29)
n
We now analyze the upper bounds of C1, C2, and C3 in turn. For C₁, invoking Lemma C.1 and Lemma holds that
C.3 it
C1 Lemma
[|ly yyll- 22- lyy 1y--re Ny-F4ill 11 - vell))
2na
d1 (Ily- Sell2 - Ily -
(ly yellz lly yy-ill)) + 2as
Lemnu
20.5
|ye-1 vella.
(30)
2am
X
For Cz, noticing here we have
Σ C0 u).
(u
(31)
S
and (b-) is convex in Lemina C.1 it follows that
1
C2 Lemmna 27
(Iu- uell Iu ue+1 12)
U uell?
(32)
2n
For C3, in similar manner, we can obtain
C3 Lemma
(I|s -s1l22
14+112)
|S sell2-
(33)
CTI
2n
2nB
20

---

Published in Transactions on Machine Learning Research (09/2025)
Substituting the above incquality into (29 and taking expectation over Fi, we can get
E [[
I.) L(u,s, S.++1)
1
[ly --elll2 E y Y [
A1
(Iy-
9x12
E ly St411 2am (1
1
E
Ye.1 -eell2
2a.5
2a5
A1
+ 21
(|u ue 1 E u us- (2)
1
|Ur11 uel12
+ 2n
(Is - sel2 E Is Sea 13)1))
1
B - 8t
20
2n
+
1 n
E
(y (1) s((21) (1)1 ( (B.)))
Σ
n
s (g: (U++1, 8811) - gi gi( (u,,
F=1
1=1
D2
Da
1
n
+ E
U U1+1
+ E
1+1 1.2
8t
Stt1
i-1
D.
+
E
S
1
Σ
(+1
u U1-1
R + Σ
Fill (G)2 - -G,2) , s-S
(34)
mll
D6
For D1, noticing that E [(((t) ((0)) )²]
= =5((()) -50 )²+ 2=((1(0) (1) for any i [n], then we obtain
D1 s 253 [|s ||s-s: 1: E ||s S 22)
E B sal12.
(35)
2n3
Inspired by Lemma 10 in Wang & Yang we bound D2 as following.
D2 - Σ
n
E - ->(())(())) (g: (U(11))) a60 (((())
:=1
Σ
n
E -{(())))(()))
9: -
1
Σ E (y(0) - -0)
71 i=1
n: 1-1
Σ 1=
n
(00000 - 5/0
|| 2 (1e11, - 9: u4 $4) #)]l
1 n
Σ (y (t) -((h (i (u - 0. (B! ]] i=1
$
C
E
u nan?
SC2
B.+1 s12 + C7aC7
1 n
Σ E (y(0) (t) - -)(ii) (9:(1), - 0. (BB (36)
The last term in 36 is bounded
R
E
n
1
v (si(uen, 06 (B( E (y((t)
]]]
1 Σ
[v. (1) -y(hh) (a( - E
260 (B{
n
n
(37)
To bound the first term in (37) we have E y (g. (111),ta) o(9 (1{(6) Fr = -. Besides, according to Corollary 12 in Juditsky et al. (211)) for some dg > 0, we have
E e[y() Swn) (B())) A2 y 560 -0000 X²
(())
(1)
E
2X2
such that
1 E (:(0) (1
(B( (b]
-9.
A E E
(0)
((())
2
2 E
y
-
1
oñ
(38)
-
2
2
21

---

Published in Transactions on Machine Learning Research (09/2025)
where (8r) is also virtual sequence for Algorithm 3 For any Ag O, the second term can be bounded as:
1 E
Agee
E F -vell
Σ
(39)
71
2B
4)gn
Put
36
37
38
and 39
together,
SC2
X2
D2
E
u411 uell
5t-1 S 4Ma07+
yyy - Ely 1-+1111))
A
Aan2
2n
2
Aa
2
V - vull
(40)
2B\₂
2B
423n
For D3, under Assumption
for some As Ao > O, we have
SC,Co
D3 s C
U - uull2 +
n
E
[+1
As
n
C2 9
SAB
S30
E
u
E
2|St - sell2 +
(41)
2n
2n
2nd6
For D4, similar to the derivations on Ds, it holds that
As
10900
3C702
D S
u411 - -ul
+
E S141
-sel2+
(42)
2n
2
2n33
2
Finally invoking Lemma 4 in Juditsky et al. Do, we have
2011 (as well as Lemma in Zhang & Lan 2020 on Dj and
D3 E
1
Σ
Y
(B) G1-1
200
Σx
y
(1)
G
Ue+1
S
19999
no²
S
StS.
71 :=1
Do = E
1.2
(B())
Σ yu1
n
S
S
3C702
B
(43)
i=1
Supposing d 11=1+
5: A2= = So A3 a.v= = 8C2 max B. n), As = Ao = and substituting D1, D1, Ds. Do
into equation
yields desired result.
C.2.2 Proof of Theorem 4.3
Proof. Fix any / 0. Applying Lemma C.4 with (u,s) (u", (u",s"), where (u', == arg min ueu, ssS F(u,5) and summing from t 0 to T taking expectation on Fo. we obtain
Σ
E (1 I.(1", (1", ([=1)]
00
1
1
< Iu"
uol2
||5 soll2 -
as Aly-oolz- Ily -8olo11 lly -
2n
25B
Sag
ao
1122
BC303
+ +T
(44)
2Bn
2
B
S
B
Since y(,,s,y) is convex on u.s and linear on y, we have
1 T-1
ma,,,u, L(u", ,'")) S max
Σ (um L("" ven))
(45)
"
T
where u + ET- u..1. + ΣTo Stt1i ý + ΣT-1 ya.. Next, consider the left-hand side (LHS):
I(ū,8,y) - L(u", s',)) -
Σ ( (ū, (y
1 - g s s0)) f (5()))
(46)
22

---

Published in Transactions on Machine Learning Research (09/2025)
Choose y(0) =5(1) arg max, (v()) ()((()) [a (ū, By Fenchel- inequality, it holds that g: ss(()) 13 (1() &
By the definition of conjugate, we have y(1) ((.)
(oo(("ss""))) Combining the above F(ū,)) F(u' "s',,"") maxy + Eis S(UcH..SH1,)) -o'--uu'ee ((1))
it follows that
(F F(u', ,s*)
1
Iu" - uo 2
|s so
aST 64
3D3
2nyT
253T
a
n190f
no²
3C702
(47)
B
S
Choose a .7 min C.07 Cfof 3 B x min 0
Be
Be C7ps
and T x max G3 p3 cfof D& Sea B BS Se
8a
Dig
completes the proof.
BS
C.3 Non-convex Case
In this section, we present the proof of the non-convex case. The key to the analysis is to apply the convergence analysis of STACO1 for the regularized problem each stage. However, there is gap as STACO1 requires 9:(w,s(0) to be convex. To address this gap, reformulate the problem in (S) as the following:
L,(,,,,) 1
2 Σ1 Fl
(q((us(())
50)+ (-( Iu u
2-(1) (s - -s =
ff (x(())
1
||u u.o 2nyy
1 Is st,0 s
2n _ 7(1) (s))) (.0)
Σ
n y())
(48)
24
2n
where 7(1) is a proper constant. By carefully choosing the value of -(1, we can make (i s())
+
अτ0 Iu un 0 अウ (s() =(0))² (s() to be convex in terms of s such that
leverage the con- vergence analysis of STACO1. Nevertheless, algorithm does not depend 7(1) computing the gradient of and s(1) will remove 7(), We now introduce some definitions and notations for our later analysis.
1 l 11=u'12++ Is - -s-2'11
p (',,; F(u.s)+ + 27
2n7
u, Ut,0
S, = S.u
(u st) arg min F(,,s) 1 |u Ur 5
1 ||s s:122]
(49)
2%
2ny
Since is convex and 9: is non-convex, the function F(:.)) is non-convex with respect to E l and e S. Lemma C.5. Under Assumption 4.1 and 4-4 F(..) is Cyp-weakly convex on e U and Cip " se S.
-we-ky conver
Proof. See Appendix C.3.1
Now we define the virtual sequence for inner loop update in STACO2. Definition C.6 (virtual sequence). In Algorithm 4 for any I, virtual sequence (yrA)E defined as follows:
g0 (B()) fc (y(0)) 201 (y(0) ((0) (x()) ie [m], v
f,k+1 arg max
yidey;
(
yr i [n].
(i)
(50)
and a virtual sequence { is defined as follows:
s skt+1 = mig
Vikko (
60 (6.2) + - -.())(()))
=(00) ((() +
1 (5()) - s
( ie [n]. Vk 2 0
stesS
7
23,
$ $ ie [m].
(51)
23

---

Published in Transactions on Machine Learning Research (09/2025)
Lemma C.7
is similar Lemma C.3 but this is for the inner loop in STACO2.
Lemma C.7
(Lemma 9 in Wang & Yang). Suppose (ye,e)ks (5r,)* are virtual sequences for any in Then, for any d 0, y.ye) L [0, T 1], the following holds:
Algorithm
E
(lly Yt,k 12 ll y1, 12 11, -Ycxl)))
2nay
2a, S (Ily- Ny-,,, Ily Yr..o1 12)
22is
A1
(Ix- - Scul2 -Illyy S1.0112)
$
2a,5
(1
A1 1 - yeulg. -
(52)
20y
There are two loops update in Algorithm We first present the descent lemma of the inner loop. Its analysis is similar that of Lemma C.4 However, since Ii is not convex on (u,s), we cannot directly apply Lemma C.4 By carefully reformulating the regularized problem, we can leverage the convergence analysis from the convex case. For the inner loop, define that Gr is the o-algebra generated by (B,,,,,,,0.. BL,,,, Br,x) and FLA is the o-algebra generated by St.0, ",,,B,,,1, St,, St,k). Note that Gr c Fr,e and yt,+11 is Fla-measurabl..
Lemma C.8 (Descent Lemma for Inner Loop). Under Assumption 4. 4.2 and 4.4 suppose that
(K, (Rt,kkR (Sr,) (Br,)) are virtual sequences for Algorithm and lel s 20yp and Ti Br s
Then, for any t [0, TO,TT11 1] and ls Kr -K4-221 2], the following holds:
E [T,, (Ur.t S1,4+1, (1,41 U1.08 St.0)
8. F.,+1: 81,08
(lu- (lu-ur 11 - EElu ur (
253: (Is (|s- 2 El SLA+11 12)
arS (Iv yeull - -Ely yr,
$ 2m
a (ly- (ly-St.tte 1--S E Ely st.t+1 (2)
(ly -
E Ely F1,t112
a
Sajo ano
MC79f
m
n²
3,C303
+ +349,0303
(53)
2Bn
2B
B
s
B
where Ω4 max Bt).
Proof. See Appendix C33.2
Lemma C.9 (Proximal Error Bound). Under Assumption 4.1 and 4-4 the following holds:
letting S 20,p
and nt, Br s
for any in Algorithm
S41i ue st) s 2 (u,, s/ st)
1
|u u
|// -8:
27,Ki
253,
3D3
Sargg
a.do
C70
B,C
SKS + +642,0907
(54)
2Bn
2B
B
B
S
where Ω4 max((1, Bt).
Proof. See Appendix C.3.3
C.3.1 Proof of Lemma C.5
Proof. We first show F(u,s) 1 En (()(((,))())) is weakly convex on u. For convenience, we denote
n
())) as ge(.). Then Vie [m]] and x, El, we want to establish: Aλ [0,
+ f((g.(xx (1-A)y)) +1 = Pax11 - X) ||x yl?
(55)
24

---

Published in Transactions on Machine Learning Research (09/2025)
for some μ 0. Since (x(x) is p-weakly convex, for any x. é U and A [0, 1], have
9x (1- (x) (1 (1 (1-)) + 22(1 - A) ||x -y12
(56)
2-
Noticing fi()) is monotone non-dccreasing, it holds that
fi(gi()x (1- (1-()x))1)))))) s fi +1 ()-y));(y)+ (2 - 2) x) y13)
(57)
By the Cy-Lipschitz continuity of fi, have:
f(a+))=f(()++(bb
(58)
- where a - >gi(x) + (1- -y) and 8 22 x) |x y1l..
Applying above inequality into 57 we can
obtain:
(Q- L. ||-x|xylp
s (x)((((x))+ + (1-))))(((()) Cf M2 - -) y12.
(59)
where the last inequality holds due to the convexity of fa- Therefore, Se(g (1,)) Cyp-weakly convex Summing above inequality from i= to and averaging, obtain that F(u,s) is Cyp-weakly convex Next, we show that su, is weakly convex on By denoting (u. as gi(+) and following the similar approach, for any é [n]] and x, é S we have
(( (1 a)R)) (1-N)))))++()))))))))))))))))) ()(1-)(2-2))) ()
+ (1
(60)
Noticing (1, is weakly-convex to each coordinate of s, F(u,s) is Cie -eakly convex on s.
C.3.2 Proof of Lemma C.8
Proof. For analysis, we introduce two auxiliary variables Ti, and Pekk, where (1)
== vy for any i St,k c, x(() for any e [n]. Before delving into the formal proof of Lemma C.8 we briefly highlight its The
=(1) ==
role: it provides a variation bound for stochastic gradients under coordiate updates, which is the central technical novelty enabling us prove parallel mini-batch speedup. The proof proceeds in three steps: (i) decomposing the variation of block-coordinate updates, and (ii) bounding the dependence on different batches.
25

---

Published in Transactions on Machine Learning Research (09/2025)
Step 1: Decomposing the variation of block-coordinate updates. By definition, we have
(1, 14,0;81.00 St.0)
1
(u ( 17 (x))))
1
|u,k+1 uu.0l2+
||
n
2
2ny
1
lik+ (i ( (((((k)))
I1-
11.0
1
2
1
||s s1,0112
n2
27
2ny
1 22
(6)
2
1
1,k+1 -5:0) -
(1)
=
gi
Ut,k+1
U1,0
(s
2T
2T
1
y(1)
(u,
11
11,0
2
(s(1)
<(0))
-5 - 15
71
2-(1)
27(1)
t
y((
((1)
1
Ur,k+1 -1.0012
1
|t,,++1 u1.0
1
11 u1,0112
1 Σ
1.++1
u1,0l
27
11 2-(1)
27
n1 i=1
27(0)
1,k
1
|8 -2.0012
Σ y()
(5
5/,0 2
1
|s -t,01,
1 Σ
y t,k+1 (s()) (0)
2nry
11 1=1 27(1))
2n1y
11 :=1 27
1 12
E(y" (y (1) - -((1)) Je (,(
| - u1,0
(s
[1k+] - (000
2-(1)
2-(1)
12 1-1
r,k
1
(i)
(6)
1
2
1
(1k+1 (0))
(3)
Σ
y 1,++1
Ut,k+1
2
n
2-((
25
(u
(1))
|u.k - un.0l2 2
$
27
27
1.6
1,
+
n
1 (i)
1,b+1
si
s
2-(1)
Ur.k
u0
2
2
2-
(81,
(
gi
(u, (())
1
Iu ur
1 (s(1)
(1))
2x((1)
(7(()
L,k
1 y(()
1 (1)
+
1
[r,k+11
12
| un.0l
1
Iu un,ol
1
Σ 12k+1
u 2
24
71 i-
2+(1)
2y
n1 i-1 (=(()
1,k
+
2ny
1
St.k+1
-t,00
12
1 Σ
2-1
2- (i)
y(i
S (2)
1,,+1
500)
2ny
1
Is st,0
2
n i-
1 Σ
y 1,k+1 (s( -s())
27 ii)
s(00)2
1 n
Σ
())
+ (y
1 "
(0)
(61)
Observe that for any (, E SU, the function gi (u,
+
1 2
||u u'12 +
1 (s(()) - 5((0) is convex
2
with respect to u and s(1), for any fixed (u', s') E SU, since
2 p. This convexity enables us to
26

---

Published in Transactions on Machine Learning Research (09/2025)
apply first-order approximation and derive the following bound:
St,0)
Σ (y
-((1 1) (0(
1
|
u.o0
1
(5 (()))
27(4)
27(()
" 1=1
I,k
(1)
(1)
||
u1,0
(1,k+1 =(,0)2
t,k+l
27((0)
27
(1)
1-1
111
gi (u
(2)
Ur.k
ur
2
(5
(3)
2-(())
27
III
(((
y i,k+1
(1)
1,k,1
(0)
1
(ut ur,o), Ue u
(1)
1,k2
(1)
1
(5 $(0) (5 5()
2,
Tek
1 (1)
1 (1)
1 y
Ur, ur.0
1
+-
1
uu ur
2002
2
1
Ur,k+1
ur 2
1 2T (1)
71
1 2- (i)
F= 2
(
(t)
(i)
(i)
y 1
|
ur,0
2
n
yt,+1
|
u0 - Σ
y (,ktl
| -0
2- (i)
2T (i)
27 2T
2.k
1=1
irk
(1)
1 (
1 y(i)
(1)
2,6+1
(0)
Σ
y
1,tt1
(
-
(1)
Σ f,k+] (6)
2- (1)
1,k+1
(0)
1= 27
1=1 2-
2
71 1
(2)
(
(i)
1=1
n y 2,b+1
(²((1)
st,++1 - (0)
(1)
1
1=1
Σ 1,k+1 (8) (1)
2= (i)
s
(,0)
2
+ Σ
1=1
n
y 1
2 (t)
t.k
s f.k (00)
III
1
1
U - u0,0l3
||u
|s,,41
St,0
Is
St 0
27
24
2ny
2n7
22
1 2
Σ
Ji (1) (x)
(62)
27

---

Published in Transactions on Machine Learning Research (09/2025)
Noticing
1 =
1
(y
-y,k+1 g9: (U. (1)
())
n
[ly
n
(1)
- Do.k
(1)
+ -
1
E (y(0) 510 s (s(U s - 2. (B
n E=
E=1
===
S
1 Σ
Yik-1
t,k, (B
20)
1,k
(1)
(u, - -1,0)
1 Σ
sml
(i)
G(f)
1,k,1
=(6)
1
(u, up,0)) u- ue
(i)
(1k.11 (B(.)
1
(Ur,a un.0) ). u ur
1ik+1
(1)
1,k
(())
c(
( un,o)
1,k++1
[
+
[()
1,k
(G()
f (1(1)
1
1
((1)
1,,0,2 t,k
(B(t))
1
(5
5/,0) (s(0) -s(2rr)
f,++1
1,k
1 n 1=1
(i)
1,++1
((1)
1,k,
+
=(1)
(5
(i)
((,0
(8
(2)
$(2.1)
1,k
III
1 1
1 ==1
Σ
(0)
(gi Cu (()) (11 (11)))
(63)
n1
and replacing
+Y (1) iik
(1)
(.k+ and =(1) T, = 7y 1, it follows that
(1)
(M - L,, uu,s, Vr,R+1; U 81,0)
U1,0,
1
( (1)
-0000000 1 (1) 1 Σ (0
n
n Σ 1=
(y(()=
(1)
-5(0 (0((4) 062 (B(2))
Σ 500
n
1,,0-1 (I. ))- go (ue (()))
F=
1
Σ
yi,kt1 Gel ((0211((9)
(i)
(B(:) (uu. (.,))
Σ
yic-11 G. + -u m.o)) u uc
(1)
1
S
ieStk
n
S
1
1
Σ
11,+1 G.k.
(1) (0)
6k,,
(B(())
7
-urx -u,o), u- Ur,k+l
1
C2
Σ
(G
(G.
c
(1()
71
Σ
(0)
1k2
+
(s
-
1
(s(:) ((.211)
7
C2
1,bel
c.(1)
+-
1
( un,0), u - U1,k-=1
Σ
y
((0
(s (10) (5(0)
(0)
(
n
7
71 1=1
2nty
1
Σ
| - u2.0112
2ny 11
1 n
u2
2nr
n
8 1
(10)2²
2ny
1 Σ
(s
t.
(1)
(64)
1
v=1
1=l
28

---

Published in Transactions on Machine Learning Research (09/2025)
For C1. by applying Lemma C.1
followed by Lemma C.7
obtain:
[1y-Yt.he Nr.kl2 1-2 ly y D--ER++122 12- |1 -e.tl2))
Lemma [AT
2na
(ly- Ve.k1l2 Ily Ye.u. 111)
A1
(Iy S2.all2 11 Se 112)
Lemma Cbtr
20y5
2ay5
(1-11 215
1
(1
|1FeRE1 - Nr
(65)
2am
For C22 we define the auxiliary function:
(00)
+ ( (u mco) m.s))
(uu) = 5 #eS.
Σ yikkol
(66)
2
Substituting (0) = 71,,11 this becomes
1 Σ ylinn
60) (B(2) + 1 (u,, uno), u
(uu)
(67)
S se5
Since (6-) is convex, applying Lemma
C.I
yields:
1 (Ilu 11,, -Iu 11, 21/. 27/.
1
C2
|
(68)
For Ca, following the similar manner with C2, for any i in St,k, can get
C3 Lemma C. 2n,3. (Is s ||s Sc, 12)
1
St,
(69)
2n,3
29

---

Published in Transactions on Machine Learning Research (09/2025)
Substituting the above inequalities into 64 and taking expectation with respect to Fix yields:
E
TTy
(1,,
0. S1,0) L (u, F1,4+1 14,00 (.,,8,,))
$
1
(ly
||y
-r,
E 11
A
(ly- -Pr,all - Elly S1,411
2
2ay5
1
1
(1
E 117.-11-rr.ll
2amn
21S
1
(lu-ue,hk
E ur,,-113 -1,
E
Ur
6+1 ue
21)
2m)
(Is [|s-St.A
St.
E Iss S1,4+1 l12
E |t,k+1
S1, 1
2m/3
2n,3,
Σ
(y( - s(km) -2-1
1=1
(i)
gi u ((,)
1,
17
D3
1,k+1
(1) (())
Me 1
Σ
E
(5(1)
r,ke!
(())
2.k,2 s
-
(1)
i=1
E
Ur, Ur
U uc
E
|urk--1
un.022
||ur, ur,01
27
D.
E
(8t,k Sc,0, St,k s,,K+1)
+ E
|1 - -8,,012
||8t.A s8.00 12)
2nzy
Dr
1
Σ ye 60) (B.)
1
Σ
(0)
f,k+1 1,K,1 u1,441
S
icSt,k
11
1= t,k+1 t,k,2 (,kk)
12
y
(1)
(G(1) (B(1)
(G())
(()
12
(s (
(70)
Ds
Step 2: Bounding the dependence on different batches. For D1, notice that E
k,,k-1 )
(1)
9 (s(() (1)
)22 n-8 (s(1) (( for any i [n]. Then, it holds that
1k+11
D
(Is St E Elis- st, (2)
E Br,k11 st,
(71)
25
2n
For D2, following a similar manner we show in 40 for some
Xe, As. ds > O, we have
C2 D2 S
SC2 1
A2
2
E u u1
B
Se,t 12 4x,07
E yly
Se.k 12
E ly
Ne.k 112)
X
2n
of
E
1
y1,el22
(72)
2B
2B
4Az
30

---

Published in Transactions on Machine Learning Research (09/2025)
For D3, by invoking Assumption 4.1 for some As As 0, have
Un,+1 - u - + SC,C,
D3 s CyCyE
E
Σ
(1) c,t+1
n²
Li=1
As E
n1 C u
SA6 2n²33e
S.3.
-
E
E - -2.l22+
(73)
2t
2ds
2nd6
For 11, same to the derivations for D3, it holds that
As El u
1/e C
A 2n3:
3.O.
Da S
E
(74)
24
2ds
2Ao
For Ds, noticing
ur - -|| uc,011))
--u,,k-1 u1,0 U ur,6+1),
(75)
then we have
1
D3 (ur Ur uek u.,k+1) (u upo0 4r uc
E Ur,k 11,k+1122 l12
(76)
In the same manner as for Ds, we obtain D6 1 E |tt -1,4+122-- Next, applying Lemma in Juditsky et al.
2011 (as well Lemma in Zhang & Lan (2020))
D7, have
D7 E
{ 3 K
Σ
(
(0) (B..
(ur uc,o)
1 Σ n
((() [1k.1
1 1-_-uua (ue, un.0) ) ueaus
Te.k
Te.
ne 9o9 02:52
$
(77)
B S
Finally, for Ds, similar to Dy, it follows that
D3
n Σ E
(1) 1,ke1
(G.., - G(1) -G(()) s(() ((0
-(,,22 ((01))
1-1
Σ
E
(1)
(G()
2, (5(1) - -G(1) -(,.2) -8
2,k+1
11 i=1
3,C702
(78)
B
By setting d1 = 1 3 A2
n
Ag = Ctt; \4= = 8C2 max(me 3,), and As = Ag t.2 and substituting the bounds
Sa.
of Dj through Dg into incquality 70
we obtain the desired result.
C.3.3 Proof of Lemma C.9
Proof. For any 1 2 0, by invoking Lemma C.8 choosing u u/,s s si and summing from k= 0 to K, while taking expectation over Fe,0, it holds that
K-l
L. (Ur,k+1. St.+t1, y: St.0) L., (1 [c,0.
k=U
|uu
1
|| s
(ly
-roooolll + |ly 1ly- ly +1y--o013
2n
253,
a
(010.C503+
Sara
ano
n
3.0
1
+ Ki
(79)
2Bn
2B
B
B
S
31

---

Published in Transactions on Machine Learning Research (09/2025)
Since L, (u. is convex and s, and linear y, we have
max Liy (ūr Yi 8r.0) s Fe; 8..0
ye
Kr-1
max
Σ
V1,611 (r,
(80)
yey Kt k=0
where u, 1 DK-l
1r,, Re 2k=0 S1,4+1,.7+= 7 Ek-t Vr.+1- Next, for the left-hand side (LHS), we
1
K,
have
St. L, (u s1. Ur,,
( g: (i (0)) -5: m1((00) + 27
üū - u0
||s:
8t.0
2nr
n
u S 1(1)) - fi (F()))
1
||u - u.ol1
1
|| 52.
2
(81)
2
2n0
Choose y( yt arg (v()) gi (u. s fi (v(1)), then we have y (u, s. fi (y(1))
(i, )). By Fenchel- Young inequality, it holds that Yr (u/.s, 1(0)) ) fi (s. S fl (u) (1)
Thus, have S,; u4,0, (u, s/; ue,0, st,0) maxy 1 Σk-i (U, y; S1.0
Li (ul s/, Mr, Dividing both sides by Ke completes the proof.
C.3.4 Proof of Theorem 4.5
Proof. We begin by invoking Lemma
C.9
which yiclds:
EF 8t-1) s(!
E
U6-1
us 0e12-
E [ - -sil2 (
1 1 ||u -uel(
mell
27
2ny
211
27
||s| -sell
-lyo0,,l2++ -ly-
Sc.0112 11 11y - 8c013)
+
+
28
2ny
a,SK,
Saro
m OnJ30
B.C902 m=52
Cf
(82)
2Bn
2B
B
Based on inequality (6) from Rafique et al.
2022 the following estimate holds:
1 |s|
1
u
U1
|1 uell2
Sc.1 -sell2
2
71
n
2
||
8x
4
u |u]
4 ||st
s
11
3n
n
then
EF(u
s((u)ss)
1
_
1
||u|
-ull,
_
|u. u++1 2
27
65
7
1
1
1
|||
stll2=
2
||s
Stt 112
28
6ny
ny
3D3
Sa,e
Goto
ne
8,C302 9102
649,
020
(83)
a,SK,
2Bn
2B
B
B
S
Next, we apply the strong convexity of the auxiliary potential function by, as established Lemma
C.5
Since (,, is ( Czp)-strongly convex with respect to and
Cre ) convex with 87
32

---

Published in Transactions on Machine Learning Research (09/2025)
respect to s, it follows that:
1 Cgp E uul -u+tuu u0t1l12 + ( 2ny
1 CiP
) |s| S l1
27
2
2n
Eωy (
S ue, - (u, s/; 8s)
$
E
B||u? uellz
1
E
||s
s0ll2= +
3D3
21;Ki
Kt
25
a,SK:
Sarod
0.00
2
3,C303
1/.0²
62
(84)
2Bn
2B
B
B
S
Furthermore, using the assumption 7
/ the final descent bound simplifies to:
S(1) s F(ul,s))
s/)
9
1
u/ - -u
9
1
|s] -
km
+
B7
2S
+
6nzy
27D3
9
9a
On.Cof
98,C3003
9n:02
57662,2207
+
(85)
a,Sk:
2Bn
2B
B
B
s
Since s(u S F Si)
1
u/
u: 1
2
s St 2' it follows that 2n7
27
S(( ((,, St)
1
|uf
ur
1112
|ul u
1
||
-:
9
|s
St
$112
37
21 K
3m0
25
K
27D3 a,SK,
95a,0
9a,00 2
On.Cfot
98,C300
9m.02
+ 5769,
(86)
2Bn
2B
B
B
S
Summing both sides over t= 0,1, ...,.... T and taking expectation with respect to Fo,o, we conclude:
E lu!
ur/
1- 3ny
1
9
s
T t-0
37
2np Kr
253,K,
F F(u,, So)
EFFu,, 27D3
+5762,
T
a
o8aro
On..
93,0903 9n.62
+
(87)
2Bn
2B
B
B
s
Finally, choosing the step sizes and inner-loop iteration numbers appropriately as:
Be
Se²
7/ min
82 ne)
C2
Cjof"
2
B
3g x min(
C2O C707 76
76"1
Be²
0n x of
Di02 2
7 n7 }
K₂ x max
(88)
BSa
S3
we arrive at the desired convergence rate:
E [diist (0.
1 2-11
Σ
E
[u] ue 11-
1 1|ss s:112]
7 2T 1=
n
6
[ (uo, So) - EEF EF(uT, ST)] +07 122) -12)
<
(89)
IT
33

---

Published in Transactions on Machine Learning Research (09/2025)
where is uniformly sampled from
1}. Then can make E {(dist(,,0F(u).s))) s by choosing
T 0 Fo P(u.)). P(u.)) ). The total iteration complexity would be
6²
T-1
K; 0
29 c
Gjo
8²
C2
n0303 BSc
Di
Σ
(90)
Bc
Sc
Sct
BSc
34


Reviews:
[{"review_id": "H2WDDIotMJ", "reviewer": "Reviewer_YBcz", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths.**\n\nIt is notable that the proposed algorithms implement block coordinate updates for both the primal and dual variables.\n\n**Weaknesses.**\n\n1. **Connection to existing works.** The discussion of connections to existing work appears to be insufficient. Although related work is cited, the discussion remains superficial.\n    - On p. 9, it is stated that “SOTA is quite similar to STACO2.” Is the difference merely that the latter adopts block coordinate updates on both the primal and dual variables? If so, is the analysis of STACO2 an extension of that of SOTA? Is the extension straightforward, or does it involve addressing non-trivial challenges?\n    - The proofs in the appendix rely heavily on the analyses of Wang & Yang (2023), citing their work frequently. However, the paper lacks a discussion of the technical novelty in light of that prior work. It merely states that the formulation considered by Wang & Yang (2023) does not involve the parameter $s$, but it remains unclear whether this difference introduces any non-trivial challenges.\n2. **Presentation.** \n    - The English needs improvement. For example, there are phrases such as “convexity *to* $u$ and $s^{(i)}$” and “weak*ly* convexity.”\n    - It would be beneficial if the authors could provide some high-level explanations, rather than simply presenting equations directly from their calculation sheets. In particular, since the work of Wang & Yang (2023) is cited several times, it would suffice to include a high-level explanation such as: “the proof essentially follows Wang & Yang (2023), with necessary modifications.”\n    - The submission appears to have been completed several years ago and has not been revised since. For example, the paper by Wang & Yang (2023) has had five versions on arXiv, the latest of which was uploaded in 2025, but the authors cited only the first version from 2023.\n    - The authors cited Rafique et al. (2018) and Rafique et al. (2022) separately, but according to the arXiv records, these are simply the first and most recent versions of the same work. Are there any essential differences between the two?\n    - The proofs are nearly as readable as the authors’ raw calculation sheets. Please reorganize and revise them to improve clarity and readability.\n    - “Parallel speed-up” is not a widely accepted or well-defined term. It should be introduced before being used.\n    - Are the constraints on the parameters in Equation 2 the same as those in Equation 3? \n    - The first equation in Section 4.3 is not a “regularized problem” but simply a function. \n    - I don’t get the following statement: \n        > Nevertheless, our algorithm does not depend on $τ_{(i)}$ as computing the gradient of $u$ and $s_{(i)}$ will remove $τ_{(i)}$.\n    - Some explanations in Section C.3 regarding why an approximate stationary point of the Moreau envelope is meaningful should be moved to Section 4.3.\n    - Equation 41 needs a citation. \n    - The filtration $\\mathcal{F}_t$ in Lemma C.4 is not defined. \n    - The proof of Lemma C.4 cites Lemma 13 of Wang & Yang (2023), but that lemma is not proved by them; they, in turn, cite other works. It would be more appropriate to cite the original sources directly.\n3. **Analysis.**\n    - In Section 4, the authors do not analyze the algorithms for the original problem, but rather for a similar one that omits the parameter $s’$, stating that “the update of $s’$ is almost the same as $w$.” This is quite confusing, and it remains unclear whether there are any gaps in applying the analysis results to the original problem.\n    - What is the purpose of defining the virtual sequences in Definition C.2? In particular, isn’t $\\bar{y}_{t + 1}^{(i)}$ exactly $y_{t + 1}$? \n    - The proof of Lemma C.4 cites Theorem 22 of Wang & Yang (2023) to bound $\\mathcal{D}_2$, but the statement of that theorem provides an iteration complexity bound rather than a bound on $\\mathcal{D}_2$.\n4. **Some other issues.**\n    - The reformulation of Equation 2 into Equation 3 in Lemma 3.1 is not analogous to the reformulation of Equation 13 into Equation 14, which is confusing. \n    - Moreover, the equivalence between Equation 2 and Equation 3 appears to follow directly from the definition of $[x]_+$, rather than from the convexity of $f_i$.\n    - On p. 2, it is claimed that the algorithm of Hu et al. (2023) is designed for the non-convex case and does not apply to the convex case. Their algorithm assumes weak convexity, and standard convexity is an extreme case of weak convexity, so it appears strange that their algorithm does not apply to the convex case. Explanations are needed. \n    - What is the purpose of showing the first two results in Equation 41? Doesn’t the third inequality suffice?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "Consider the problem of optimizing the two-way partial AUC (TPAUC). This paper adopts a surrogate loss approach and formulates it as a variant of a finite-sum coupled compositional stochastic optimization problem. Two algorithms are then proposed based on a primal-dual approach: STACO1 for the convex case and STACO2 for the non-convex case. Notably, the algorithms implement block coordinate updates for both the primal and dual variables. Convergence analyses for both algorithms are provided.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I do not believe this work is publishable after only one minor revision. The presentation of the submission does not appear to be ready for publication. True connections with existing work are neither adequately discussed nor clearly established. There are several gaps and points of confusion in the analysis, and the proofs are difficult to read. Therefore, rather than requesting a minor revision, I believe it would be more appropriate for the authors to withdraw the submission and resubmit it after making substantial revisions.\n\nHowever, if the authors believe that the work can be made satisfactory with a minor revision, then I encourage them to address the weaknesses outlined above.", "broader_impact_concerns": "This is a theoretical work, and I believe there are no significant concerns of this kind.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "HHxhOZPpxQ", "reviewer": "Reviewer_3nWQ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n\n+ Improved theoretical rates of both STACO1 and STACO2 relative to prior work, that are achieved via analysis that as far as I could tell is meaningfully different/improved relative to past work. In particular, the nontrivial 1/B vs. 1/\\sqrt{B} improvement is made, and some of the stronger boundedness assumptions from prior work are shaved off, in the non-convex case. And in the convex case, the improved technique helps tease out a bound whose leading term that matches an existing lower bound.\n\n+ As one might expect from carefully designed block-coordinate methods, their improved empirical properties appear significant on the whole: as demonstrated in different comparisons in the experimental section, the proposed methods win out on one or more of the following, relative to prior methods, ---  training performance; generalization properties; speed/stability of convergence. \n\n(Relatively minor) Weaknesses: \n\n- The empirical section could use some beefing up in terms of the datasets/tasks tested, as well as testing with other surrogate losses and with other (\\theta_0, \\theta_1); see Requested Changes below. Furthermore (as a minor point), if one were to nitpick, one could say that in certain aspects, the performance advantage of the new methods over some of the older methods is not always as large: for instance, in the linear case, apparently PAUCI performs quite on par with STACO in Table 2.\n\n- The presentation writing, as a reader from outside the AUC/TPAUC optimization area, is something that I found less clear, especially in terms of setting the stage at the beginning of the paper. To keep readers engaged, I would consider adding more details early on in the manuscript such as: Conceptually, what ideas are some of the previous state-of-the-art methods based on (current indications are a bit too brief)? For the cited state-of-the-art rates, which dependencies could one hope to improve and by how much, discussing relevant parallels/lower bounds from the general optimization literature whenever possible (e.g. B^{1/2} vs B; the \\epsilon^{-6} rate in the non-convex setting)? More on this in Requested Changes.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This manuscript presents two novel algorithms, STACO1 and STACO2, for TPAUC (two-way partial AUC) optimization. TPAUC has emerged as a useful alternative to AUC but has relatively fewer optimization methods in the literature especially on the stochastic front, and this paper aims to fill that gap by developing block-coordinate optimization methods. Both methods, one for the convex case and the other for the weakly convex case, are based on a recent min-max reformulation of the original TPAUC optimization problem, and improve on the respective theoretical state-of-the-art rates of prior algorithms. Some of the techniques used for the analysis could be useful in their own right. Finally, a substantial empirical evaluation of both proposed methods is given (for the both cases of linear/nonlinear predictors, on several datasets in either case), which showcases a variety of performance advantages that new methods offer over prior state-of-the-art.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Overall, I am reasonably satisfied with the manuscript, but I believe the following modifications would strengthen the work in nontrivial ways and so I would like to ask the authors to implement most/all of these:\n\n--- Larger-scale very imbalanced datasets: While the current dataset lineup appears to be consistent with some prior works in the AUC/TPAUC literature, the empirical section left me wondering as to why some of the well-established large-scale settings with imbalanced classes such as the click-through rate prediction task in e-commerce were not experimented with. The degree of imbalance in CTR prediction tasks is such that the motivation for TPAUC optimization is very strong. Further, the very large scale of several existing such datasets gives an opportunity to possibly showcase even greater efficiency advantage of the proposed block coordinate approach. So unless there is something that I'm missing here, I would request to add such an evaluation to further strengthen the paper --- e.g. I'd propose a dataset like Criteo.\n\n--- Experimental ablation: It appears important, from the perspective of the theory of surrogate losses, to look into how the empirical results would change as a result of choosing a different \\ell than squared hinge loss --- testing other nonlinearities as \\ell would not only lead to different Lipschitz parameters etc, but might also conceivably result in distinct optimization dynamics. Again, if there is something that I'm missing in terms of background, e.g. if the squared hinge loss has been established as the clear winner among possible choices of \\ell and other choices are somehow empirically less sensible for TPAUC optimization, please let me know --- but from a purely optimization standpoint, it is natural to wonder about this ablation. As another useful thing to try, different pairs of \\theta_0, \\theta_1 would be good to see: e.g. in the above-suggested Criteo dataset's case, the imbalance could be large enough to where more extreme values of \\theta_0, \\theta_1 than 50 or 75 would be the interesting ones.\n\n--- Clarity: It would be good to improve the exposition at the beginning of Section 3, where relevant background (such as the reformulation of the problem in a min-max form) is given. In this case, only a brief recap of the reformulations of Zhu et al (2022) is given, which for a less-familiar reader may be too terse. Some further background would be good to briefly discuss right there for intuition such as: Any other reformulations that may have been used in the literature (and their relative advantages)? What's the role of \\ell in theory and in practice wrt. the optimization methods in prior work?", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "rQQET4TURB", "reviewer": "Reviewer_4bQu", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n* The paper is clearly written and well-structured, making the main contributions easy to understand.\n\n* The proposed algorithms are novel and tailored to the structure of the TPAUC problem. They make clever use of primal-dual and block-coordinate techniques, which enable a parallel speed-up and are supported by solid theoretical analysis.\n\n* The authors provide both theoretical convergence results and empirical evaluations, offering a comprehensive view of the method's performance.\n \nWeaknesses:\n\n* The main algorithmic design appears to be inspired by the proximal-point framework used in Rafique et al.'s work. It would strengthen the contribution to discuss and compare with other recent minimax algorithms, such as [1]. How would the modification of algorithms in [1] perform when applying to TPAUC?\n\n* In Figure 1, across all datasets, there is an abrupt drop and subsequent rise in performance. This behavior is not discussed in the main text and warrants explanation—what causes such sharp changes?\n\n* The comparison in terms of runtime is missing. Reporting the total optimization time would provide a clearer picture of practical efficiency.\n\n* In Appendix, the authors claim that STACO-1 shows lower variance in training loss based on Figure 5. However, this claim is not convincingly supported by the plots, especially Figure 5(c), where STACO-1 seems to exhibit higher variance. Would you please clarify this observation?\n\n[1] Li, J., Zhu, L., & So, A. M. C. (2025). Nonsmooth nonconvex–nonconcave minimax optimization: Primal–dual balancing and iteration complexity analysis. Mathematical Programming, 1-51.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes two stochastic primal-dual double block-coordinate algorithms (STACO-1 and STACO-2) for solving the two-way partial AUC (TPAUC) maximization problem. The authors reformulate the original  objective as a minimax problem, allowing the use of primal-dual methods with alternating updates on blocks of primal and dual variables. The paper provides convergence guarantees for both convex and nonconvex settings, and empirical evaluations on multiple benchmark datasets demonstrate the effectiveness of the proposed approaches.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see above.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)