Multi-block Min-max Bilevel Optimization with Applications in Multi-task Deep AUC Maximization
Authors: Quanqi Hu
YONGJIAN ZHONG
Tianbao Yang
Venue: NeurIPS 2022 Accept (2022)

Abstract: In this paper, we study multi-block min-max bilevel optimization problems, where the upper level is non-convex strongly-concave minimax objective and the lower level is a strongly convex objective, and there are multiple blocks of dual variables and lower level problems. Due to the intertwined  multi-block min-max bilevel structure, the computational cost at each iteration could be prohibitively high, especially with a large number of blocks. To tackle this challenge, we present two single-loop randomized stochastic algorithms, which require updates for only a constant number of blocks at each iteration. Under some mild assumptions on the problem, we establish their sample complexity of $\mathcal{O}(1/\epsilon^4)$ for finding an $\epsilon$-stationary point. This matches the optimal complexity order for solving stochastic nonconvex optimization under a general unbiased stochastic oracle model. Moreover, we provide two applications of the proposed method in multi-task deep AUC (area under ROC curve) maximization. Experimental results validate our theory and demonstrate the effectiveness of our method.

Multi-block Min-max Bilevel Optimization with Applications in Multi-task Deep AUC Maximization
Quanqi Hu
Yongjian Zhong
Department of Computer Science Texas A&M University College Station, TX 77843 quanqi hetiiihhhttmueeeee
Department of Computer Science
University of Iowa Towa City, IA 52242 yong nongjiannzhorg edu
Tianbao Yang
Department of Computer Science
Texas A&M University
College Station, TX 77843
-ianbao-yang@tane edu
Abstract
In this paper, we study multi-block min-max bilevel optimization problems, where the upper level is non-convex strongly-concave minimax objective and the lower level is strongly convex objective, and there are multiple blocks of dual variables and lower level problems. Due to the intertwined multi-block min-max bilevel structure, the computational cost at each iteration could be prohibitively high, especially with large number of blocks. To tackle this challenge, present two single-loop randomized stochastic algorithms, which require updates for only constant number of blocks at each iteration. Under some mild assumptions on the problem, we establish their sample complexity of ((1/e)) for finding an e-stationary point. This matches the optimal complexity for solving stochastie convex optimization under a general unbiased stochastic oracle model. Moreover, we provide two applications of the proposed method in multi-task deep AUC (area under ROC curve) maximization and multi-task deep partial AUC maximization. Experimental results validate our theory and demonstrate the effectiveness of our method on problems with hundreds of tasks.
Introduction
We consider multi-block min-max bilevel optimization problem of the following formulation
min F(x, a) Σ ==1
a5, EgEp, [f((x, 0z (x):
(upper)
NERds am
S.t. (x) = arg min 9i (x,y;) =
for i = 1,......
(lower)
.....
where fr and 9, smooth functions and A dd is convex set. In particular, in this paper we assume that for each é E (1...., m). fx a,,y,) is strongly concave in the dual variable a but can be nonconvex in the primal variable x, and (x. is strongly convex in yę- The upper problem mingeR<s ma F(x, a) is a min-max optimization problem where the lower problems (x) arg min (x(x,y)))
involved variables. For each block the upper-level objective (x Y;) and the lower-level objective (x. y:) depend only on its corresponding block
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

of variables a and y, i.e. a; and Y:- This problem has important applications in machine learning, e.g., multi-task deep AUC maximization as presented in section 3
Tackling problem (T is challenging as it involves solving a min-max problem with coupled multiple minimization problems simultaneously. The naive way for solving it is to do multiple gradient ascents and descents for a and y. respectively, to ensure a good estimation of the gradient for updating x. However, this approach has two major drawbacks. As the algorithm involves double loop structure, it can be computationally expensive and give suboptimal theoretical complexity. On the other hand, the multi-block structure requires data sampling from distributions Ps. 2, for all blocks, which may lead to an impractical demand for memory.
1.1 Related work
Min-max Bilevel optimization. To the best of our knowledge, the only existing work that provides a stochastic algorithm with provable convergence guarantee on min-max bilevel problems (9] They propose a single loop bi-time scale stochastic algorithm based on gradient descent ascent, and prove that it converges to an e-stationary point with an oracle complexity of Ole P). Nevertheless, this convergence result is established for special case where f(x, y)) is linear function.
Stochastic Nonconvex Strongly Concave Min-max Problems. The considered problem is also closely related to non-convex strongly concave min-max problems, which have been studied ex- tensively recently. To the best of our knowledge, 30 establishes the first result on non-smooth nonconvex concave min-max problems. They prove a convergence to nearly stationary point of the primal objective function with an oracle complexity in the order of O 4) for non-convex strongly concave min-max problems with a certain special structure. The same order of oracle complexity is achieved in [36] without relying on any special structure. These two works use two-loop algorithms.
There are some studies focusing on single-loop algorithms. (25] analyzes single-loop stochastic gradient descent ascent (SGDA) method for smooth nonconvex strongly concave problem, which achieves O(e complexity but with a large mini-batch size. In [12, the same order of complexity is achieved without large mini-batch by employing the stochastic moving average estimator. Some recent works improve the sample complexity to O(e under the Lipschitz continuous oracle model for the stochastic gradient using less practical variance reduction techniques [66 28, 31]. [41
establishes lower complexity bounds for non-concex strongly concave min-max problem under both general and finite-sum setting and proposes accelerated algorithms that nearly match the lower bounds.
Stochastic Nonconvex Bilevel optimization. The considered problem belongs a general family of non-convex bilevel optimization problems. Non-asymptotic convergence results for nonconvex stochastic bilevel optimization (SBO) with strongly convex lower problem has been established 8
in several recent studies 4
12 14 19]. As the one who gives the first results for this problem, [8 proposes a double-loop algorithm with O(E-6) oracle complexity for finding an e-stationary point of the objective function. [19 improves the complexity order to O(e but suffers from a large mini-batch size. 14 proposes single-loop algorithm with two time-scale updates that achieves an oracle complexity of Ö(e-)). Recently, 12 improves the oracle complexity to the
state-of-the-art oracle complexity Ō(e-t) by proposing single-loop algorithm based on moving- average estimator. (5] presents a new analysis for (double-loop) SGD-type updates showing that an improved sample complexity Oee-²) can be achieved. There are studies that further improve the complexity to 3 by leveraging the Lipschitz continuous conditions of stochastic oracles 4. [0 21. [24] considers bilevel optimization under distributed setting and proposed algorithms achieving state-of-the-art complexities. However, none of these works tackle multi-block min-max bilevel optimization problems directly.
Multi-block Bilevel Optimization. There are some recent studies considering bilevel optimization with multi-block structure. (10] extends their single-block bilevel optimization algorithm to multi- block structure. Their algorithm requires two independently sampled block batches and for all sampled blocks, each variable needs update using variance reduction technique STORM (6]. For unsampled blocks, an update involving constant factor multiplication is also required. Under Lipschitz continuous conditions on stochastic oracles, the complexity is no worse than Om e²) with m blocks. A more recent work 22 considers top-K NDCG optimization, which is formulated
compositional bilevel optimization with multi-block structure. Their method simplifies the updates by sampling only one block batch in each iteration and requires updates only for the sampled blocks. Their method achieves complexity of (mm/et). We use a similar approach as the latter work for estimating the hessian inverse in a block-wise manner. However, this paper differs from 29 in that we tackle more general bolti--lockkaee min-max max bilevel problems without assuming particular form of the objective.
2

---

1.2 Our Contributions
In Section we present two simple single loop single timescale stochastic methods with randomized block-sampling for solving general form of multi-block min-max bilevel optimization problem under the nonconvex strongly concave (upper) strongly convex (lower) setting. Both methods employ SGD for updating selected y; for their corresponding lower-level problems, employs SGA for updating the selected ax, and employs a momentum update for the primal variable x based on the sampled a; y,- Then we show in Section 2.2 theoretically, that they converge to e-stationary point with complexity Occ=f) under a general unbiased stochastic oracle model. Our result for the single- blogk--book setting matches the lower bound for solving smooth, potentially nonconvex optimization through queries to an unbiased stochastic gradient oracle under a bounded variance condition [. Finally, in section we present two applications of multi-block min-max bilevel optimization in deep AUC maximization: multi-task deep AUC maximization and multi-task deep partial AUC maximization. In section 4 empirical results show the effectiveness of the proposed methods.
2 Proposed Algorithms and convergence Analysis
Notations. Let || For a twice differentiable function f : X x Y + R, Vzf(x, v) (resp. Vuf (z, y)) denotes its partial gradient taken w.r.t x (resp. y). and V2 zz Zy [Ir y) (resp. [ y)) denotes the Jacobian of (x. y) w.r.t x (resp. Vyf(a, y) w.r.t y). We let f(: B)) represent the unbiased stochastic oracle of f(-) with a sample batch B as the input. The unbiased stochastic oracle is said to have bounded variance 2² if [- [+]] f() S 0². A mapping f X - I is C-Lipschitz continuous if (x)) - [(x') )ll S Cllx x' Vx, X. Function is L-smooth if its gradient VS(-) is L-Lipschitz continuous. A function g : X + R is X-strongly convex if Va, x' E X, g(x) 2 g(x') + Vg(a')²(z
denote the Euclidean norm of vector the spectral norm of matrix.
(z,
x')- + 11 - x²112. function g: X + IR is A-strongly concave -g(z) is X-strongly convex. Let II denote projection function onto convex set A. For notation simplicity, we use S to denote the set of all block indices, ie. S = [l....,m} We state the definition of e-stationary point as following.
Definition 2.1. Consider differentiable function F(x), point x is called c-stationary if [x)( < e. A stochastic algorithm said to achieve an e-stationary point if [E] P (xx)]ll S e, where X, is the algorithm output at the t-th iteration and the expectation is taken over the randomness of the algorithm until the iteration i.
Assumptions. Before presenting our algorithm, we make the following well-hehaving assumptions. Assumption 2.2. For functions fú and 9t. we assume that the following conditions hold for all i S
fe(x, v,) ) is ju--Stronlly concave in terms of a; (x) is M4 -tronggy convex in terms of y,- ft is Cy-Lipschitz continuous in terms of both x and y,, and fi. 9: are I,,, T respectively.
2x v.)1 S C2 gay- De v6.5 ž Mg
V (x, V (x),) are Ligays Luy Lipschitz continuous respectively.
We remark that the Lipschitz continuity condition of fi in terms of x can be removed when there is only one block. Other Lipschitz continuity conditions are stadnard in bilevel optimization literature. Moreover, the gradients of functions f; and di can only be accessed through unbiased oracles with bounded variance.
Assumption 2.3. The unbiased stochastic oracles
oi, (,; VaJi(x, 0i, N, B) o
Vyf((x, (x. y;: for all i E S, where [B] denotes the size of the sampled batch B.
(x, (x,; V (x, y;; B3) have variances bounded by jis
These assumptions
similar to those made in many existing works for SBO
19
Moving average gradient estimator. Algorithms based on moving average estimators have achieved the state-of-the-arr oracle complexity in both min-max and bilevel optimizations (II. Here we give brief introduction to the moving average estimator. For solving a nonconvex minimization problem min Fxx) through an unbiased oracle (x),), i.e. E (x) Fx)), the stochastic momentum method (stochastic heavy-ball method) that employs moving average updates is given by
V4+ (1 9)v, + px,),
X x, 11+11
3

---

Algorithm A Stochastic Algorithm for Multi-block Min-max Bilevel Optimization (v1)
Require: a. ,,,"" y0 H 2o, Xo
1: 0, .,..., do
2: Sample tasks 1, C S. Sample data batches B C Pi. B Q, of batch size B for each i E 4.-
3: for sampled blocks E T do
4:
0; [+1 [[ + 71 V f (X;, af,y::; B[]]
5:
y; = y 1/2 V 9i Nr. y BB)
6:
end for
7:
Update estimator - [ vn (Xt, y by 2
8:
Update gradient estimator A 4+1 of V (x,) by
9: Ze+1 (1 Bo)zz + 3
10: Xt+1 Xx 1/0
end for
where B and 7 are momentum parameter and learning rate, respectively. As moving average of the historical gradient estimator, the sequence of Ve+1 could achieve an effect of variance diminishing across a long run (32)).
2.1 The Proposed Algorithms
First, propose simple single loop stochastic algorithm solve the multi-block min-max bilevel optimization problem. At the beginning of each iteration, we first sample a set of blocks 7, and data batches B, B for each selected block E I.. Then we update estimators of (x(x,) and y, (xe) for all selected blocks i J using one step of SGA and SGD. Then, we compute estimator of the hessian inverse H1+ of the lower-level objective and compute a gradient estimator A 4--1 of the upper-level objective. Finally, we compute the moving average estimator Z of FX)x)) and update X 1. Note that the design of our algorithm on the min-max bilevel optimization part is inspired by [T. and it is similar their momentum-based algorithms PDSM (for min-max problem) and SMB (for bilevel problem) in their paper. In fact, if we set the number of blocks to be one and remove and the lower level problems, then Algorithm i the same as PDSM. Similarly, if the number of blocks one and the dual variables in the upper level problem are removed, then the proposed algorithm becomes similar as SMB except for the hessian inverse update with reasons explain shortly. In other words, our proposed method is generalized form of noasentum-based algorithm for min-max and bilevel optimization problems. Additionally, Algorithm I only updates (11) blocks of dual variables a, and the variables y, of the lower-level problems. These make the analysis of Algorithm I much more involved.
To further understand Algorithm we first define the objective function F(x) 1 Eies fi(x, ar xx where (x)x) [1] can be rewritten as ming F(x). The up- dates for af is and y are intuitive since the gradient estimations of (afi(xe, y!) and Vy y!)
argmin,, (x. and (;(x) ==
mn arg max,, fi(x, as (x)), so that the Problem
directly available from the unbiased stochastic oracles. However, since functions (x) and a (x) are implicit, estimating the gradient F is difficult. In fact, one may apply the get:
corollary of Theorem [
1 Σ (V.. m iES
VF(x)
+ V (x
standard approach in bilevel optimization literature g for computing Vy, (x) is to derive Vy, = - -Vyy (x, (x)) V2 y (x))] from the optimality condition of y, (x). Therefore, the gradient we are looking for is given by
1 Σ V.fi(x F = m
V
iES
All components in this gradient can be easily obtained from unbiased stochastic oracles except for the inverse of hessian (x for all blocks. This could be problematic in the sense of theory and practical implementation. For practical implementation, we do not want to update the hessian inverse estimators for all blocks, which is prohibitive when the number of

---

blocks is large. A common approach used in the literature of SBO is to use Neumann series g
H Ny Caun -i (1 -I- 1 Vi Viyyi (x ft) where is chosen from {1...., ,.....,,,)] k2) randomly Cosn
and k is the number of samples { ke for estimating the hessian inverse. This estimator is a biased [51
one and its error w.r.t to (i (x,, y is controlled by the number of samples ke [8]. However, is problematic to employ the above estimator for only the sampled blocks I because the error for those not sampled cannot be controlled. To address this issue, we use a different approach for estimating the hessian inverse by only updating the estimators for those sampled blocks [29]. The idea is to maintain a momentum term of+1 for each block that stores historical information on the hessian estimator bu (x., y B.). And the hessian inverse is approximated by directly compuring the inverse of of st+1, i.e., for sampled E IT
-1 31)s + 31 V Sy B,; H [s] [s]
(2)
In terms of theoretical analysis, we are not bounding the individual error H V 9: (x, for all blocks, but the cumulative error for all blocks across all iterations. This is exhibited in Lemma 2.6 As the conclusion of the above discussion, the gradient estimator of V F (w.)) is given by
A 1-1
1 4
Σ IEL.
V=fi(x,, of v;: V Vaggi B: H Ji (x. v.:
(3)
We maintain moving average estimator Zz+1 for A 1+1 and finally update x,+1 using ze+1- The detailed steps are presented in Algorithm |
Nevertheless, such method is not suitable for problems with high dimensionality of y,, since computing the Hessian inverse could be computationally expensive. To this end, we propose the second method, Algorithm for problems with high dimensionality of y,, The main idea is to treat [V2 Ve by (x. y+)] - (,,(xx, 0ss; Yz) as the solution to a quadratic function minimization problem. As a result, ? wy. (x. y,)] V
v.) can be approximated by SGD. Such method for Hassian inverse computation has been studied for solving single-block bilevel optimization problems in some previous works 7 23). However, none of them has applied this method in multi-block scenario.
Define quadratic function 71 and its minimum point as following
(x at. == arg min (r x, V.) = Lou TV 2
be v² V'V V a.)
vER"y
Then we have the gradient Von plies that the unique solution is given by Vx(X, y.) = [ " that due to the smoothness of g and Lipschitz continuity of f with respect y in Assump- tion 2.2. one may define constant
= (x - V,li(x,,
which im-
Note
C₁ so that [/, a, r1 S r Considering the Ma
updates in Algorithm 2 have || < I for all i,t. Define the stochastic estimator V.7a(v, x, as, Vú B,, B.) = Veg y,5 )v- V,,i(x, oi, y;; then it has bounded vari- ance, of which the proof is deferred to Appendix B Here we enlarge the value of a so that Eg [l Xr, yf; B B (v x < T It is worth to note that the projection
in the updates of v is necessary in order to bound the variance of V x,,y; B B²). Instead y:: of taking projection, previous works 7 (23 treat the variance boundedness an assumption, which is not guaranteed without using projection.
2.2 Convergence Analysis
In this section, we present brief convergence analysis of Algorithm and Algorithm theorems and proofs are deferred to the appendix.
2 The detailed
2.2.1
Convergence analysis of Algorithm I
The key point of this analysis is the gap between the true gradient V (xx) and its estimator z z To this end, we define
1 Σ (Vaf((x.. Vi Wf
F a², y') == m
iES
5

---

Algorithm 2 A Stochastic Algorithm for Multi-block Min-max Bilevel Optimization (v2)
Require: a. , x0, 2o. No
1: for (or-=0 1, 1,, T do
2: Sample tasks 1, E S. Sample data batches BY C Pi, B C 2 of batch size B for each E 4
3: for sampled blocks E 1 do
4: ag ++1 [[ + m1 V Nt. yt: B[]]
5:
y 1/2 9
Nr. y BB)
6:
++ Mr v 13
yy
Ne, y B:)x Vyli(x,, BB]]
7:
end for
8: Update gradient estimator A Tu Eiel, Vali(Ne, yx (0)zz z4 + A A (+1
9: 7++1
10: Xt+1 = Xt 7/o
11:
end for
One may notice that the estimator
++1 A++1 is in fact approximating F a', y²) instead of V F F(x)).
We exploit the moving average formulation of z and decompose the gap into two parts, || ++] Fx,,,, a², , y1 and F|V, a', well y", a and Hi approximate y(x:), (xx)) and [V ny yx)) -1, respectively. In other words,
V (x,,) ][l These two gaps are determined by how
aim to bound the following three errors, (xx
dy.t, ||a(xx) a² 8a, and
V Wa (xe, y.)] 12
We first bound the variance [[ by proving the following lemma.
Lemma 2.4. Consider the updates for y in Algorithm under Assumption 2.2 and 2.3 with
7/2 < min 2m we have
T
2m
4mmpTo²
8m Cm T-1
El
5y,0 +
E[
BB
11
1
One may also bound the second variance [[ based on the previous variance E[,y,e) following similar strategy.
Lemma 2.5. Consider the updates for at in Algorithm 7
under Assumption 2.2
2.3
with m S
min
Ayll.] p we have
4m
my
4m
24I.3 3
Bldy.e] + 8mpymoo7 2
32m 32m3Ca B B[|
E, (oat)] S
80 +
Σ
Σ
1,
Due the lower bound assumption V (x in Assumption
2.2 the error in Hessian V (x.)))) We prove
approximation can be bounded by bounding 8gyn. := Eies ||s| the following lemma.
Lemma 2.6. Under Assumption 2.3 hessian, with B₃ we have
considering the momentum method (2 for the update of
4m0ggy. [1,
T
E[5 + 8m3,To2
32m L2 ygy (1 Cg
Σ g(ggy) S
32T,2 "ayy
|+ 112).
1
It then follows the convergence theorem for Algorithm
Theorem 2.7. Under Assumption 2.2 2.3 and with proper settings of parameters T1, 72, Br O (Be), 8o = O (min (TT,, B) and no = O min min((T)), B)e2 BlI, }). Algorithm ensures that after T = O max solution of Fxx), i.e., E[|[ (xx,)
m
T. min BTe.BB iterations we can find an e-stationary
m
& 2 for randomly selected T E (O....,)).

---

2.2.2 Convergence analysis of Algorithm 2
Similarly, bound the gap between the true gradient VF(xx) and its estimator z in Algorithm 2 we aim to bound the following three errors, ōy,t, o,, and Eies llv! (y (x, y, V (x,
=: 6y. We follow the same strategy for 6y.e and da, what has been discussed in the previous section. To deal with &,,, we first note that by its construction, (w, y,) is M4 -S-trongly convex and Ly -moothh with respect to t. At result, similarly Lemma 2.5 one may bound the error of the estimators v/. Then follows the convergence theorem
for Algorithm? 2
Theorem 2.8. Considering Algorithm
under Assumption
2.2
2.3 and with O
proper settings of parameters 1h1 72, 7J3
O (Be),
3o
and 71
O 0min min ( (1l, BJe.
BLLE) Algorithm
ensures that after T
B miu([I.].BBe..)) iterations we can find an e-stationary solution of F(x), Le., E V[ S e for randomly selected r E (0....,
O max [1 m
Remark. In Theorem 2.7 and Theorem 2.8 there is no condition on the sizes of data batches B B nor block batch I for the algorithm to converge. Hence, their sizes can be as small as one. The order of complexity is (11/c),, which matches the optimal complexity for nonconvex optimization under a general unbiased stochastic oracle model. In addition, there is parallel speed up by increasing batch sizes for data samples and task samples due to the scaling in terms of |T,] and B in the iteration complexity.
3 Applications in Multi-task Deep (Partial) AUC Maximization
In this section, we present two applications of multi-block min-max bilevel optimization: multi-task deep AUC maximization and deep partial AUC maximization. (partial) AUC is a performance measure of classifiers for imbalanced data. Recent studies have shown great success deep AUC maximization in various domains (e.g., medical image classification and molecular property prediction) [26] 33 40).
However, efficient algorithms for multi-task deep (partial) AUC maximization have not been well developed. For multi-task deep AUC maximization, we solve an existing formulation by our algorithm. For multi-task deep partial AUC maximization, we propose new bilevel formulation and solve it by our algorithm.
3.1 Muti-task Deep AUC maximization
Following the previous work [26 40] deep AUC maximization problem can be formulated as non-convex strongly concave min-max optimization problem min max LAuc(W, a, b, a).. However, training a deep neural network from scratch by optimizing AUC loss does not necessarily lead to a good performance 339. address this issue, 39 proposed a compositional training strategy for deep AUC maximization:
min max LAUc(w LcL a, w.a,boER,
where LCE denotes the cross-entropy loss. The outer objective remains be the AUC loss, while the inner objective is a gradient descent step of minimizing the traditional cross-entropy loss. This method has shown superior performance on various datasets [39.. We extend this formulation to multi-task problems and reformulate it into multi-block min-mat max bilevel optimization:
Σ
(u a' aaa
min W...
max
DER 1=1
S.t. n (Wi Wh) = arg min
Iu'- 1 ((w,, i/ LVVLCEWWW x
where w, denotes the weight for the encoder network that is shared for all tasks, and w/. = (w)..... wx)) denote the task-owned classification heads. The upper objective is strongly con- cave terms of dual variables a and the lower level objective is strongly convex in terms of u' The hessian of the lower-level objective is the identity matrix. Hence, there is no need to track and estimate the hessian matrix.
7

---

3.2 Multi-task Deep Partial AUC Maximization
Some real-world applications (e.g., medical diagnosis 22 cannot tolerate model with high False Positive Rate (FPR) even though it has significant performance in AUC. Hence, a measure of interest is one-way partial AUC (pAUC), which puts a restriction
the range of FPR (i.e., FPRE [pt, p). where 0 S S S 1). Below, we focus on the case Pt = 0. However, our method can be easily extended for handling pt O. Let 4. D_ denote the set of positive and negative data for binary classification task, respectively. Let D [K] denote the top-K negative examples according to their prediction scores. Let n4, n denote the number of positive and negative samples respectively, Then we have partial AUC optimization with pairwise square loss formulated as following [37
min 7 XEED+ T-P
3 Σ XJED-[K]
(lw(X,) lew (x.) + c)),
where K= nt- is constant and (.) denotes the prediction score on data. A key challenge for solving the above problem is to deal with the non-differentiable top-K selector x, E D [K] which depends on the model parameters w. This challenge has been recently tackled in 33 42 We focus on the comparison with the first work as it is optimization oriented similar to ours and also has the sfate-of-the-arr performance. They formulate the problem into either a weakly convex minimization or approximate it by smooth objective in a compositional form. A caveat of their algorithms (named SOPA, SOPA-s) is that they need to maintain and update n4 auxiliary variables with one for each positive data. If we apply their algorithms for multi-tast -tsk problems, one needs to maintain and update Ex=1 n4 auxiliary variables, which could dramatically slow down the convergence.
To address this problem, we first transform it into a min-max optimization problem. Let a(w) = 1 1 Ex,ED, (x:) and b(w) R-p ExjeD [K] (x,). Then we can write the problem as (cf. ne
Appendix B for a derivation)
1
min w,o,b n2 X.ED
Σ (x,((x)) a)²
Σ I(x, E (K](()() b)) + (b(w) a(w) + c)?.
n_P X,ED_
To tackle non-continuous non-differentiable indicator function T(.) we can replace it by a sigmoid
function. To tackle non-differentiability of the top-K selector x; E D_]K], we follow (29 and
formulate it as lower-level optimization problem, i.c., Xj E DD[ is equivalent to fw (x,) > X(w).
where A(w) represents the K + 1-th largest scores among all negative examples, which can be approximated by a solution from a smooth strongly convex minimization problem as following:
X(w) arg min L(A, w) XER
K +
X+
2 22 2
1
Σ In(1 + exp((h) A)/T)),, XED_
where e, TI, 72 are small constants. Based on above, the multi-task deep partial AUC minimization problem can be formulated as multi-block min-max bilevel optimization problem give by:
min max w,a.b oERm
(hw(x;)) -2
+
1 nk
Σ X,ED*
(x;((x;;)) -
-bb)
1=
E.E
20
Σ X;ED
Hlbn (x,: (v(())/
(x;:k; +c a
p
n
X.D
>x(w)= = arg min (A, w) = K+ x NER
2 n_ 2
Σ ti In(1 + (wwp((tw(xxxxtkktecce -)/
n_
X,ED*
where D* D/,/- denote the positive/negative data set of the k-th task, (x; k) denote the prediction score for the k-th classifier, and ((s) L+exp!-s) is the sigmoid function. The upper-level objective strongly concave in terms of ar and the lower-level objective is strongly convex in terms of A
We develop tailored algorithm based on Algorithm forr solving the above formulation of multi-task PAUC maximization as shown in Algorithm 3 in Appendix C For the hessian update, the momentum
8

---

Table 1: The testing AUC scores on four datasets.
MatSet
CIFAR 100
CheXpert
CelebA
ogbg-molpeba
mAUC (baseline)
0.9044 (0.0015)
0.8084( 0. 1455)
0.9062 (0.0042)
0.7793(0.0028)
mAUC-CT (ours)
0.9272 (0.0014) 0.8198(0.1495)
0.9192 (0.0004) 0.8406(0.0044))
update 2 is efficient due to that the each lower-level problem is only one-dimensional. For simplicity of implementation, we define a loss G 38 in the Appendix C on which auto-diffcrentiation can be directly applied for computing a gradient estimator. We refer readers Appendix [ for detailed explanation and derivation of G++1
4
Experiments
4.1
Multi-task Deep AUC Maximization with Compositional Training
Data. We use four datasets, namely CIFAR 100, CheXpert, CelebA and ogbg-molpeba. CIFAR-100 [22] is an image dataset consisting of 60, 000 32 color images in 100 classes. Hence, there are 100 tasks for CIFAR 100. We follow 45, 000/5, 000/10, 000 split to construct training/validationnessts datasets. CelebA (27] is a large-scale face attributes dataset with more than 200K celebrity images, each with 40 attribute annotations (i.c.. 40 tasks). We use the recommended training/validation/tssst split as 162, 770/19 19, 166/19, 961. CheXpert [18) is a dataset that contains 224,316 chest radiographs with 14 observations. Since the official testing dataset is not open to public, we take the official validation set as the testing data, and take the last 1000 images in the training dataset for validation. Due to the absence of positive samples for the observation Fracture in the testing dataset, ignore is molecular property prediction graph dataset [15). It consists of 437,922 ,999 graphs with 128 labels (i.e.. 128 tasks). We follow scaffold splitting procedure as recommended in (34)
this label and only consider the rest 13 observations (i.e., 13 tasks). The last dataset
Models. We use ResNet18 L3 for CIFAR-I00 and CelebA, and ImageNet pretrained DenseNet121 17 for CheXpert. For ogbg-molpeba, we use Graph Isomorphism Network (GIN) 35
Setup. We compare our method for optimizing the multi-task AUC maximization with compositional training denoted by mAUC-CT (ours) with a baseline that directly optimizes multi-task min-max AUC denoted by mAUC (baseline). We do not compare with other straightforward baselines (e.g.. optimizing the CE loss and the focal loss) since they have been shown to be inferior than AUC maximization methods for imbalanced data in many previous works 40 42 For both methods, the learning rates 72, 71, 7o are set to be the same and tuned in {0.01, 0.03, 0.05, 0.07, 0.13. The learning rates decay by a factor of 10 at the 4th and 30th epoch for Chert and CelebA, respectively. No learning rate decay is applied for CIFAR- 100 and ogbg-molpeba. The moving average parameter 3o and ij in the lower level problem of mAUC-CT (ours) are tuned in 10.1, 0.5, 0.9]. Regarding the task sampling, for datasets CIFAR- 100 and ogbg-molpeba, 10 tasks sampled to be updated in each iteration, and for each sampled task, we independently sample a data batch of size 128. For the other two datasets with fewer tasks, CheXpert and CelebA, we sample one task each iteration. The batch size for data samples is 32 for CheXpert, and 128 for CelebA. We run both methods the same number of epochs which varies on different data, 2000 epochs for CIFARI00, 6 epochs for CheXpert, 40 epochs for CelebA and 100 epochs for obgb-molpeba.
Results. In Table D we report the testing AUC score with the model selected according to the best performance on validation datasets. Comparing with optimizing AUC loss directly, mAUC-CT (ours) achieves better performance on all tested datasets. We show the results of an ablation study in Figure 3 which verifies convergence has parallel speed-up effect on both the batch sizes of data samples and task samples. The algorithm converges faster as either the data or task sample batch size increases. In Figure 2
(left two), we compare speed on the training data of two datasets, which demonstrate that our method converges faster. More results on training convergence are included in the appendix.
method with the baseline in terms of convergence
4.2 Multi-task Deep Partial AUC Maximization
Sctup. For this task, we use the same datasets and the same networks for the image datasets and graph datasets as in the previous subsection. For baselines, we compare with a naive mini-batch based method (MB) for PAUC maximization 20) and state-of-the-ar pAUC maximization method SOPA-
s 42). Following previous works 44 for pAUC maximization methods use pretrained

---

CRAR100
ColobA
Traning soore
Trap o00 soore
2000 200 1000
Bl00s ane Damiia
3:
B:32
9-54
10
B-64
0-8
20
B-128
8-2
B-256
Number of terations
Number of iteraaionn
Number iterations
Number iltrations
(a) Varying B
(b) Varying
(c) Varying
(d) Varying
Figure 1: Convergence of our method vs data sample batch sizes B and vs task sample batch size
== [ for multi-task deep AUC maximization.
CelebA
eghg-melpebe
Colatin
pebe
Taining aue sooe
Taloio D 2000
(PFCCFFFCCC PAMIC (FFR
PALII
MAUC-CT (ours)
(saseline;
MAUC-CT (ours)
[haseline]
MMB PAUC
MMM MMME-AAUIC
Number of eoochs
Numoer of eoochs
Number Epochs
Numibrr Epocht
Figure 2: Comparison of Convergence training data for multi-task deep AUC maximization (left two) and multi-task deep PAUC maximization (right two) on the CelebA and ogbg-molpcba datasets.
encoder network by optimizing the CE loss as the initial encoder and learn the whole network by maximizing pAUC. We also report the performance of optimizing the CE loss for refernece. For all methods. the learning rate is tuned in {0.0001, 0.0005, 0.001, 0.005, 0.01 }. The hyperparameters selection of MMB-pAUC are: 771 and 1/2 E {0.5. 0.1, 0.01). 81 {0.99, 0.9, 0.5, 0.1, 0.01] and So E (0.9, 0.99]. For Focal loss we select gamma from {1,2,4 4} and alpha from {0.25, 0.5, 0.75). The momentum parameters in SOPA-S are tuned in the same range and their parameter in {0.1, 10} as in 42 The margin parameter in the surrogate loss (e.g., c) is set to be 1. Regarding the task sampling, we sample one task at each iteration for oghg-molpcha and CheXpert, sample 10 tasks for CIFAR and sample 4 tasks for CelebA. The data sample batch size is 32 for CheXpert, and 64 for others. For smaller datasets (CIFAR 100 and ogbg-molpcba), we run 100 epochs for each, and we decay the learning rate by factor of 10 at the 50-th epoch. For larger datasets (CelebA, CheXpert), we run 50 and 5 epochs respectively.
Results. The partial AUC scores with FPR 0.1 on the testing data of different methods are shown in Table From the results, can see that methods perform better than baseline methods with a significant margin. In Figure 2 (right two), we compare our method with the baselines in terms of convergence speed on the training data of two datasets, which demonstrate that our method converges faster. More results on training convergence are included in the appendix.
Table 2: The testing partial AUC scores on the four datasets.
Mataod
CIFARI00
CelebA
Che
ogbg- molppha
CE
0.8895 (0.0009)
0.8024 (0.0026)
0.6606 (0.0159)
0.6576 (0.0010)
Focal
0.8966 (0.0007)
0.8064 (0.0011)
0.6646 (0.0132)
0.6453 (0.0021)
MB
0.9188 (0.0006)
0.8304 (0.0005)
0.6759 (0.0160)
0.7213 (0.00T8)
SOPA-8
0.9251 (0.0003)
0.8336 (0.0001)
0.6682 (0.0156)
0.7290 (0.0019)
Ours 0.9262 (0,0005) 0.8360 (0.0003)
0.6827 (0.0183)
0.7374 (0.0015)
5
Conclusion and Future Work
We have developed two simple single loop randomized stochastic algorithms for solving multi-block min-max bilevel optimization problems. These algorithms require updates for only constant number of blocks in each iteration. We showed that both of them achieve an oracle complexity of O(e which matches the optimal complexity order for solving stochastic nonconvex optimization under general unbiased stochastic oracle model. At the same time, we hope our work inspires others to find more novel applications of our idea.
Acknowledgments and Disclosure of Funding
This work is partially supported by NSF awards 2147253, 21 2110545, 1844403, and Amazon research
award.
10

---

References
[1] Yossi Arjevani, Yair Carmon, John C Duchi, Dylan J Foster, Nathan Srebro, and Blake Wood- worth. Lower bounds for non-convex stochastic optimization. arXiv preprint 1rX1v:111..02365. 2019.
[2] Stuart G. Baker and Paul F. Pinsky. A proposed design and analysis for comparing digital and analog mammography: Special receiver operating characteristic methods for cancer screening. Journal of the American Statistical Association, 96(454):421-428, 2001.
[3] Pierre Bernhard and Alain Rapaport. On theorem of danskin with an application to a theorem of von neumann-sion Nonlinear Analysis: Theory, Methods & Applications, 24(8):1163-111 1181, 1995.
[4] Tianyi Chen, Yuejiao Sun, and Wotao Yin. A single-timescale stochastic bilevel optimization method. arXiv preprint arXiv:2102.04611 2021.
[5] Tianyi Chen, Yuejiao Sun, and Wotao Yin. Tighter analysis of alternating stochastic gradient method for stochastic nested problems, 2021.
[6] Ashok Cutkosky and Francesco Orabona. Momentum-based variance reduction in non-convex SGD. In Advances in Neural Information Processing Systems 32 (NeurIPS), pages 15236-15245, 2019.
[7] Mathieu Dagréou, Pierre Ablin, Samuel Vaiter, and Thomas Moreau. A framework for bilevel optimization that enables stochastic and global variance reduction algorithms, 2022.
[8] Saeed Ghadimi and Mengdi Wang. Approximation methods for bilevel programming. arXiv preprint 1802.0800 2018.
[9] Alex Gu, Songtao Lu, Parikshit Ram, and Lily Weng. Min-max bilevel multi-objective opti- mization with applications machine learning, 2022.
[10] Zhishuai Guo, Quanqi Hu, Lijun Zhang, and Tianbao Yang. Randomized stochastic variance-reduced methods for multi-task stochastic bilevel optimization. arXiv preprint arXiv:2105.02266. 2021.
[11] Zhishuai Guo, Yi Xu, Wotao Yin, Rong Jin, and Tianbao Yang. A novel convergence analysis for algorithms of the adam family and beyond, 2021.
[12] Zhishuai Guo, Yi Xu, Wotao Yin, Rong Jin, and Tianbao Yang. On stochastic moving-average estimators for non-convex optimization. CoRR, abs/2104.14840, 2021.
[13] Kaiming He, Xiangyu Zhang, Shaoging Ren, and Jian Sun. Deep residual learning for image recognition. In CVPR, pages 770-778. IEEE Computer Society, 2016.
[14] Mingyi Hong. Hoi-To Wai, Zhaoran Wang. and Zhuoran Yang. A two-timescale framework for bilevel optimization: Complexity analysis and application to actor-critic, arXiv preprint arXiv:2007.05170, 2020.
[15] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs, 2020.
[16] Feihu Huang, Shangqian Gao, Jian Pei, and Heng Huang. Accelerated zeroth-order momentum methods from mini to minimax optimization. arXiv preprint 10XX::2008.08/700 2020.
[17] Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger. Densely connected convolutional networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 4700-4708, 2017.
[18] Jeremy Irvin, Pranav Rajpurkar, Michael Ko, Yifan Yu, Silviana Ciurea-Ileus, Chris Chute, Henrik Marklund, Behzad Haghgoo, Robyn Ball, Katie Shpanskaya, et al. Chexpert: A large chest radiograph dataset with uncertainty labels and expert comparison. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 590-597, 2019.
11

---

[19] Kaiyi Ji, Junjie Yang, and Yingbin Liang. Provably faster algorithms for bilevel optimization and applications meta-learning. arXiv preprint arXiv:2010.07962, 2020.
[20] Purushottam Kar, Harikrishna Narasimhan, and Prateek Jain. Online and stochastic gradi- methods for non-decomposable loss functions. In Proceedings of the 27th International
Conference on Neural Information Processing Systems Volume 1, NIPS' 14, page 694-702, Cambridge, MA, USA, 2014. MIT Press.
[21] Prashant Khanduri, Siliang Zeng, Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. A near-optimal algorithm for stochastic bilevel optimization via double-momentum. 2021.
[22] Alex Krizhevsky. Learning multiple layers of features from tiny images. 2009.
[23] Junyi Li, Bin Gu, and Heng Huang. A fully single loop algorithm for bilevel optimization without hessian inverse, 2021.
[24] Junyi Li, Feihu Huang, and Heng Huang. Local stochastic bilevel optimization with momentum- based variance reduction, 2022.
[25] Tianyi Lin, Chi Jin, and Michael I Jordan. On gradient descent ascent for nonconvex-concave minimax problems. arXiv preprint arXiv:1906.00331, 2019.
[26] Mingrui Liu, Zhuoning Yuan, Yiming Ying, and Tianbao Yang. Stochastic AUC maximization with deep neural networks. In 8th International Conference on Learning Representations (ICLR), 2020.
[27] Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang. Deep learning face attributes in the wild. In Proceedings of International Conference Computer Vision (ICCV), December 2015.
(28) Luo Luo, Haishan Ye, and Tong Zhang. Stochastic recursive gradient descent ascent for stochastic nonconver-strongyyycooave minimax problems. CoRR, abs/2001.03724, 2020.
[29] Zi-Hao Qiu, Quanqi Hu, Yongjian Zhong. Lijun Zhang, and Tianbao Yang. Large-scale stochastic optimization of ndeg surrogates for deep learning with provable convergence, 2022.
[30] Hassan Rafique, Mingrui Liu, Qihang Lin, and Tianbao Yang. Non-convex min-max opti- mization: Provable algorithms and applications in machine learning. CoRR, abs/1810.02060, 2018.
[31] Quoc Tran-Dinh, Deyi Liu, and Lam M. Nguyen. Hybrid variance-reduced sgd algorithms for minimax problems with nonconvex-linear function. In Advances in Neural Information Processing Systems 33 (NeurIPS), 2020.
[32] Mengdi Wang, Ethan X Fang, and Han Liu. Stochastic compositional gradient descent: algo- rithms for minimizing compositions of expected-value functions. Mathematical Programming, 161(4-2):419-44,, 2017.
[33] Zhengyang Wang. Meng Liu, Youzhi Luo, Zhao Xu, Yaochen Xie, Limei Wang. Lei Cai, Qi Qi, Zhuoning Yuan, Tianbao Yang, and Shuiwang Ji. Advanced graph and sequence neural networks for molecular property prediction and drug discovery. 2020.
[34] Zhenqin Wu, Bharath Ramsundar, Evan N. Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh Pappu, Karl Leswing, and Vijay Pande. Moleculenet: A benchmark for molecular machine learning, 2017.
[35] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks?, 2018.
[36] Yan Yan, Yi Xu. Qihang Lin, Wei Liu, and Tianbao Yang. Optimal epoch stochastic gradient de- scent ascent methods for mix-max optimization. In Advances in Neural Information Processing Systems 33 (NeurIPS), 2020.
[37] Tianbao Yang and Yiming Ying. AUC maximization in the era of big data and AI: A survey. CoRR, abs/2203, 15046, 2022.
12

---

[38] Zhiyong Yang, Qianqian Xu, Shilong Bao, Yuan He, Xiaochun Cao, and Qingming Huang. When all we need piece of the pie: A generic framework for optimizing two-way partial auc. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 1 11820-1889, PMLR, 18-24 Jul 2021.
[39] Zhuoning Yuan, Zhishuai Guo, Nitesh Chawla, and Tianbao Yang. Compositional training for end-to-end deep AUC maximization. International Conference on Learning Representations, 2022.
[40] Zhuoning Yuan, Yan Yan, Milan Sonka, and Tianbao Yang. Robust deep auc maximization: new surrogate loss and empirical studies on medical image classification. arXiv preprini arXiv:2012.03175 2020.
[41] Siqi Zhang, Junchi Yang, Cristóbal Guzmán, Negar Kiyavash, and Niao He. The complexity of nonconvex-strongee strongly-concav minimax optimization. In Cassio de Campos and Marloes H. Maathuis, editors, Proceedings of the Thirly-Sevene Seventh Conference on Uncertainty Artificial Intelligence, volume 161 of Proceedings of Machine Learning Research, pages 482-492. PMLR, 27-30 Jul 2021.
[42] Dixian Zhu, Gang Li, Bokun Wang, Xiaodong Wu, and Tianboo Yang. When AUC meets DRO: optimizing partial AUC for deep learning with non-convex convergence guarantee. CoRR, 0bs/2203.00117,, 2022.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits. hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either the supplemental material or as URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "z7V3YQxlkcw", "reviewer": "Reviewer_hKcV", "summary": "This paper studies a bilevel multi-block (multi-objective), where the inner level is a per-block convex minimization problem, while the outer level is a min-max problem involving multiple blocks. The paper proposes a novel algorithm which contains existing algorithms for min-max optimization and single-block bilevel optimization as special cases. This algorithm makes use of non-standard technique to obtain the implicit gradient for the outer level variable, and enhances the outer level optimization with a momentum based updated. This algorithm is then analyzed in terms of the convergence to a stationary point, and key aspects of this novel analysis is highlighted and discussed. The main convergence rate matches the optimal convergence rate for stochastic nonconvex min-max and bilevel optimization separately, highlighting the tightness of the result. The paper then proposes two related applications of this multi-block bilevel problem -- multi-task (partial) AUC maximization for training neural networks. One non-trivial contribution in the application of the multi-block bilevel problem to partial AUC maximization is a novel formulation of partial AUC maximization as a min-max bilevel problem. Empirical evaluation of the proposed algorithm on these applications with data from different domains (images, graphs) and different neural network architectures highlight the improved performance of the proposed scheme against various baselines.\n", "questions": "- Regarding [8] considering \"a special case where $f(\\mathbf{x}, \\cdot, \\mathbf{y})$ is a linear function\", this is infact true. But there is an assumption (Assumption 2.2)  on strong concavity w.r.t. $\\alpha$, and I think the linear form of [8] does not satisfy that assumption. So does this mean that the $\\min_{\\mathbf{x}} \\max_{i \\in [1, \\ldots, m]} f_i(\\mathbf{x}, y_i(x))$ $\\equiv$ $\\min_{\\mathbf{x}} \\max_{\\alpha \\in \\Delta_m \\subset \\mathbb{R}^m} \\alpha_i \\cdot f_i(\\mathbf{x}, y_i(x))$ does not fit in the version of problem (1) studied in this paper? Note that $\\Delta_m$ is the $m$-dimensional simplex implying $\\alpha_i \\geq 0 \\forall i \\in [1, \\ldots m]$ and $\\sum_{i = 1}^m \\alpha_i = 1$.\n\n- The $\\max_\\alpha$ in AUC maximization is there even for the single block problem so it is not clear what is the effect of this $\\max_{\\boldsymbol{\\alpha}}$ in the multi-task setting. It does not appear that the $\\boldsymbol{\\alpha}$ is forcing some form of robustness across the tasks as something like the $\\min_{\\mathbf{x}} max_i$ of [8] would have. Is that a correct assessment? Can you please elaborate of the effect (if any) of the $\\max_{\\boldsymbol{\\alpha}}$ in the multi-block setting?\n\n- Is the main contribution in subsection 4.3 the formulation of multi-task pAUC maximization as problem (1)?\n", "limitations": "The authors do explicitly discuss one limitation of their work. I do not think there are any potential negative societal impact of this work.\n", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths:\n\n- This paper studies a novel generalization of the (recently well-studied in machine learning literature) bilevel problem to multiple objectives. The problem (1) is infact a more general form of recent problem studied in [8]. Beyond the more general problem, the proposed algorithm also makes use of a momentum enhanced gradient update that is yet another novelty over the recently proposed [8] for the min-max multi-block bilevel problem.\n\n\n- The authors do a great job at positioning the problem and the novel results against existing literature on bilevel, min-max, multi-block bilevel problem. This level of clarity makes it easy to understand the originality in the paper.\n\n- The discussion of the main theoretical results clearly highlights the various strengths of the analysis. One such strength is that the convergence does not require a minimal data batch or block-batch size. Furthermore, the result shows that the algorithm can benefit from increasing both the data batch and task batch size. This is very nice property of the algorithm and analysis, and this property was empirically demonstrated with experiments.\n\n\n- The empirical evaluation considers various datasets from different domains and different neural network architectures, highlighting the generality of the proposed problem and algorithm.\n\n\n### Weaknesses:\n\n- It is not clear with no common application such as those in [8] of representation learning or hyperparameter optimization (which are multi-task extensions of the well-studied bilevel problems) are considered in this paper to evaluate the proposed general algorithm.\n\n- One aspect of the proposed algorithm that estimates the outer level gradient with equations (2) and (3) is that it is not clear how feasible this scheme is for practical problems without a special structure (like the hessian $\\nabla_{yy}^2 g_i$  is the Identity matrix). The Neumann series allows one to approximate the matrix inversion with a series of more practically efficient matrix-vector product. But the proposed scheme requires one to take the full inverse for each iteration. The authors mention this weakness as one of the limitations. \n\n- Various aspects of the formulation of the partial AUC maximization as problem (1) is unclear. First, in the vanilla AUC maximization problem, there is a positive $\\alpha$ even for the single-task (or single-block) problem. However, in the reformulation of the partial AUC maximization problem in the equations between lines 253-254 and 258-259, there is no $\\alpha$ present in the single-task problem. Then, in the multi-task extension in equation after line 260 on page 7, $\\boldsymbol{\\alpha}$ and $\\alpha_k, k \\in [1, \\ldots, m]$ are introduced without any context, and the problem itself appears to have various typographical errors since the $\\max_{\\boldsymbol{\\alpha} \\in \\mathbb{R}^m}$ appears to be outside the $\\sum_{k = 1}^m$. Moreover, it is not clear why we dont need  $\\max_{\\boldsymbol{\\alpha} \\in \\mathbb{R}_+^m}$ (implying positive $\\alpha_k$s).\n\n\n- Given the decoupled nature of the $\\alpha_k$s in the (partial) AUC maximimization problem, and the assumptions on problem (1), it is not clear why the problem cannot be formulated a standard min-max bilevel optimization problem:\n\n\n$$\n\\min_{\\mathbf{x}} \\max_{\\boldsymbol{\\alpha} \\in \\mathcal{A}} F(\\mathbf{x}, \\boldsymbol{\\alpha}, \\mathbf{y}(\\mathbf{x})) := \\sum_{i = 1}^m f_i(\\mathbf{x}, \\alpha_i, \\mathbf{y}_i(\\mathbf{x})\n$$\nwith\n\n$$\n\\mathbf{y}(\\mathbf{x}) = \\arg \\min_{\\mathbf{y}:= \\lbrace y_i , i \\in [1, \\ldots, m] \\rbrace } \\sum_{i = 1}^m g_i(\\mathbf{x}, y_i).\n$$\n\nOne difference is in the proposed algorithm is that only a subset of the blocks are chosen, but in the extreme where all the blocks are chosen in each iteration, this is just a standard min-max bilevel solver such as the one that might be used to solve the single-task version of the AUC maximization problem listed in the equation between lines 223-224. If this assessment is true, I think it would be good to understand what improvement the proposed problem formulation and algorithm brings over just looking at the multi-block problem as a single min-max bilevel optimization problem and solving it thusly. \n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "yVKfsWG-AYr", "reviewer": "Reviewer_h3Nq", "summary": "In this paper, the authors study a multi-block min-max optimization problem and propose a single-loop randomized stochastic algorithm to solve this class of problems with provable convergence rate guarantees. It is shown that the achieved convergence rate is in the same order as solving stochastic nonconvex optimization problems. Multiple numerical results show the effectiveness of the method on multi-task AUC problems.", "questions": "Besides the above comments, there are also several questions:\n\n1, it seems that the main motivation for having this model was from [37]. Why is the lower-level problem importantly incorporated in this model?\n\n2, the paper focuses on the multi-block model. Why does only $\\alpha$ have multi-blocks? how about $x$?\n\n3, the algorithm uses the momentum term. Will this should give a faster convergence rate？ or which step (min, max, or lower-level problem) restricts the final convergence rate?\n\n4, In theorem 2.7, if $\\eta_1$ and $\\eta_2$ are chosen according to lemma 2.4 and lemma 2.5, then the algorithm should not converge to an $\\epsilon$-stationary point unless they are decreasing or proportional $\\epsilon$? (because there is a $T$ in front of  $\\eta_1$ and $\\eta_2$).\n\n5, I am confused that how the lower-level problem is formulated between lines 258 and 259.\n\n6, is there an optimal solution for the lower level optimization problem because it is just an unconstrained quadratic problem?\n\n7, the authors claimed that $1/\\epsilon^4$ is the optimal complexity for nonconvex optimization under a general unbiased stochastic oracle model. Which reference showed the lower bound in this case so that we can claim this is the optimal complexity? To my understanding, variance reduction or accelerated technique, in general, can have a better complexity, especially I suppose that the authors should clarify the conditions under which the algorithm can achieve the optimal complexity.\n\n ", "limitations": "Yes.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": " The strengths of this paper:\n\n1, this work considers a very general bilevel optimization problem, which covers a wide range of machine learning problems as special cases.\n\n2, a stochastic multi-block minmax bilevel optimization algorithm is proposed, which takes the block structure of the problem, stochasticity of data samples, and variance reduction into account.\n\n3, this paper also provides the theoretical convergence rate analysis of the proposed algorithm and shows that the achieved rate matches the optimal complexity of nonconvex optimization under a general unbiased stochastic oracle model.\n\nThe weaknesses of this work are\n\n1,  (originality) the problem seems a combination of minmax optimization and bilevel optimization, especially under the conditions that the subproblem w.r.t. maximization is strongly convex and the lower-level problem is also strongly convex. How to position the novelty of this problem and algorithms among the existing work is not clear.\n\n2, (quality) The major contribution is the theoretical convergence rate analysis, but what are the challenges of showing this rate was not discussed technically \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "PzQEYwU3Ywb", "reviewer": "Reviewer_6MPu", "summary": "This paper studies the problem of multi-block min-max bilevel optimization, where the dual variables and the associated lower problem are divided into blocks. To reduce the computational expense, this paper proposes to sample a batch of blocks at each iteration and perform update only for those blocks. In theory, the sample complexity of the proposed algorithm matches the optimal order for stochastic nonconvex optimization. The proposed method is then applied to multi-task deep (partial) AUC maximization, which can be formulated as a multi-block min-max bilevel optimization problem. Extensive experiments also verify the effectiveness of the proposed method in this scenario.", "questions": "This paper have briefly compared the use of block sampling with previous work [27]. However, I wonder whether it will bring anything new to the algorithm design or theoretical analysis, or it is just a direct application.\n\nTypo: line 254, sigmod -> sigmoid", "limitations": "Limitations of this work have been properly discussed.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n\n\\+ This paper provides an interesting perspective of viewing the multi-task AUC maximization as a multi-block bilevel optimization problem. Such a generalization may inspire future research on this important area.\n\n\\+ This paper is technically sound, supported by non-trivial theoretical analysis and extensive experiments.\n\nWeakness:\n\n\\- The block sampling and moving averaging gradient estimator have some overlap with previous work, which somehow affects the novelty of the algorithm design.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "AifE_ENayp9", "reviewer": "Reviewer_Z9r5", "summary": "This paper investigated how to optimize multi-task deep auc maximization problems. In particular, this paper proposed a novel efficient algorithm for multi-block min-max bilevel optimization problems. The theoretical analysis demonstrated that this algorithm can achieve $O(1/\\epsilon^4)$ convergence rate, matching the optimal complexity for nonconvex optimization. The empirical results confirm the efficacy of the proposed algorithm. \n\nOverall, this algorithm is novel and it is well reasoned with practical applications. The theoretical analysis is also solid.  Thus, this is a strong submission with significant theoretical and empirical contributions.", "questions": "- In the experiment, is a class viewed as a task?\n- It would be good if Section 3 could be moved before Section 2.1. Then, it will be much clear what applications belong to this kind of problem. \n- It looks like there is a typo in Line 526: Assumption ??\n\n\n====post rebuttal=====\n\nThanks for your answers. \n\nThis is a novel method for the important AUC maximization problem. It can benefit a lot of real-world applications. Thus, I am raising my rating and suggest acceptance.", "limitations": "NA", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The proposed algorithm is novel. It provides an efficient solution for optimizing the important AUC maximization problem. It should have wide applications in real-world data analysis tasks because the dataset in real-world applications is typically imbalanced. \n- The technical contributions are solid. The authors provide a rigorous analysis for the convergence rate. And the convergence rate can match the optimal complexity of standard nonconvex optimization problems. \n- The extensive experiments with different datasets and models have shown better performance than existing methods. This confirms the efficacy of the proposed algorithm. \n\n\nWeaknesses:\n- In the experiment, is a class viewed as a task?\n- It would be good if Section 3 could be moved before Section 2.1. Then, it will be much clear what applications belong to this kind of problem. \n- It looks like there is a typo in Line 526: Assumption ??", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept