Non-Smooth Weakly-Convex Finite-sum Coupled Compositional Optimization
Authors: Quanqi Hu
Dixian Zhu
Tianbao Yang
Venue: NeurIPS 2023 poster (2023)
Keywords: non-smooth optimization
weakly-convex optimization
compositional optimization
AUC maximization

Abstract: This paper investigates new families of compositional optimization problems, called non-smooth weakly-convex finite-sum coupled compositional optimization (NSWC FCCO). There has been a growing interest in FCCO due to its wide-ranging applications in machine learning and AI, as well as its ability to address the shortcomings of stochastic algorithms based on empirical risk minimization. However, current research on FCCO presumes that both the inner and outer functions are smooth, limiting their potential to tackle a more diverse set of problems. Our research expands on this area by examining non-smooth weakly-convex FCCO, where the outer function is weakly convex and non-decreasing, and the inner function is weakly-convex. We analyze a single-loop algorithm and establish its complexity for finding an $\epsilon$-stationary point of the Moreau envelop of the objective function. Additionally, we also extend the algorithm for solving novel non-smooth weakly-convex tri-level finite-sum coupled compositional optimization problems,  which feature a nested arrangement of three functions. Lastly, we explore the applications of our algorithms in deep learning for two-way partial AUC maximization and multi-instance two-way partial AUC maximization, using empirical studies to showcase the effectiveness of the proposed algorithms.

Non-Smooth Weakly-Convex Finite-sum Coupled Compositional Optimization
Quanqi Hu
Dixian Zhu Department of Genetics Stanford University Stanford, CA 94305
Department of Computer Science
Texas A&M University
College Station, TX 77843
quangi-hu@tamu.ee
dix dixian-zhu@stanforddd
Tianbao Yang
Department of Computer Science Texas A&M University College Station, TX 77843
-ianbao-yanggtame edu
Abstract
This paper investigates new families of compositional optimization problems, called non-smooth weakly-gonvex finite-sum goupled compositional optimization (NSWC FCCO). There has been growing interest in FCCO due to its wide-ranging applications machine learning and AI, well its ability address the short- comings of stochastic algorithms based on empirical risk minimization. However, current research on FCCO presumes that both the inner and outer functions are smooth, limiting their potential to tackle more diverse set of problems. Our research expands on this area by examining non-smooth weakly-convex FCCO, where the outer function is weakly convex and non-decreasing, and the inner function is weakly-convex. We analyze a single-loop algorithm and establish its complexity for finding e-stationary point of the Moreau envelop of the objective function. Additionally, we also extend the algorithm to solving novel non-smooth weakly-conve tri-level finite-sum coupled compositional optimization problems, which feature nested arrangement of three functions. Lastly, we explore the appli- cations of our algorithms in deep learning for two-way partial AUC maximization and
two-way partial AUC maximization, using empirical studies to showease the effectiveness of the proposed algorithms.
Introduction
In this paper, consider two classes of non-convex compositional optimization problems. The first class formulated as following:
min F(w) ==
-(w)==-->
n. E J((E@ (w:
(1)
weRd
where denotes a finite set of items and D; denotes a distribution that could depend i, The
second class is given by:
min F(w) 1 weRd
E fi (+ (+
jes, (i(EE- lbi.s (w; (w:()))
112
where S denotes finite set of nı items and S₂ denotes a finite set of n2 items and Di, denotes distribution that could depend on (i,j). For simplicity of discussion, we denote by g: g.(w)
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

EgWD, [9 (w: R - R and by (w) = BewD. (w: of problems, we focus our attention on non-convex F with non-smooth non-convex functions f; and Di. which, to the best of our knowledge, has not been studied in any prior works.
E)l R - Re,, For both classes
The first problem with smooth functions fi and gi has been explored in previous works [26 15 21
331. which is known as finite-sum coupled compositional optimization (FCCO). It is subtly different from standard stochastic compositional optimization (SCO) [27] and conditional stochastic optimiza- tion (CSO) 13 FCCO has been successfully applied to optimizing a wide range of X-risks [33
with convergence guarantee, including smooth surrogate losses of areas under the curves 20 and ranking measures (2I), listwise losses [2I], and contrastive losses [36]. The second problem a novel class and referred to as tri-level finite-sum coupled compositional optimization (TCCO).
is
Both problems differ from traditional two-level or multi-level compositional optimization due to the coupling of variables E ① or the coupling of variables i. in (2) at the inner most level.
One limitation of prior works about non-convex FCCO is that their convergence analysis heavily rely on the smoothness conditions of fi and gi [26] [5]. This raises a concern about whether existing techniques can be leveraged for solving non-smooth non-convex FCCO problems with non-asymptotic convergence guarantee. Non-smooth non-convex FCCO and TCCO problems have important applications in ML and AI, e.g., group distributionally robust optimization 4 and two-way partial AUC maximization for deep learning 44]. We defer discussions and formulations of these problems to Section [ The difficulty for solving smooth FCCO lies at high costs of computing a stochastic gradient Vg. f. (w)( for a randomly sampled i and the overall gradient (F(w). To approximate the stochastic gradient, a variance-
variance-reduced reduced estimator of g: (We) denoted by u4, is usually maintained and updated for sampled data in the mini-batch E B, As a result, the stochastic gradient can be approximated by Vg:( (We: &t) V ((,,,)), where & DD is a random sample. The overall gradient can be estimated by averaging the stochastic gradient estimator over the mini-batch or using variance-reduction techniques. A key insight of the convergence analysis for smooth FCCO is to bound the following error using the L-smoothness of fi, which reduces to bounding the error of Wa for estimating 9, (w,):
(w,; V (u(,,)) - (g:(we; & (i < &x)] - (ww3))
central question to be addressed in this paper is "Can these gradient estimators be used in stochastic optimization for solving non-smooth non-convex FCCO with provable convergence guarantee"? To address this question we focus our attention on a specific class of FCCO/TCCO called non-smooth weakly-convex (NSWC) FCCO/TCCO. This approach aligns with many established works on NSWC optimization (6-9). Nevertheless, NSWC FCCO/TCCO is more complex than a standard weakly-convex optimization problem because an unbiased stochastic subgradient is not readily accessible. In addition. the convergence measure in terms of the gradient norm of smooth non- convexx objectives is not applicable weakly convex optimization, which will complicate the analysis involving the biased stochastic gradient estimator (.r |
Contributions. A major contribution of this paper is present novel convergence analysis of single- loop stochastic algorithms for solving NSWC FCCO/TCCO problems, respectively. In particular,
For non-smooth FCCO, we analyze the following single-loop updates:
1 Σ KEB, dg. (we: E.)Of. (ma.)) W w. "
where B, is random mini-batch of B items, and uie is an appropriate variance-reduced estimator of gs (w:)) that is updated only for i E B, at the f-th iteration. To overcome the mon-smoothnsss, we adopt the tool of Moreau envelop of the objective as in previous works (6 7). The key difference of our convergence analysis from previous ones for smooth FCCO is that we bound the inner product (E,0g, (0)g(((@@) (w) (u,,), w, w.). where W, is the solution of the proximal mapping of the objective at w.. To this end, specific conditions of fi, Ii are imposed, i.e., fis is weakly convex and non-decreasing and g:(w) is weakly convex, under which we establish an iteration complexity of T O(e-0) for finding an c-stationary point of the Moreau envelope of F F(.).
For non-smooth TCCO, we analyze the following single-loop updates:
1
Σ SEB
1 JEB; The. (wr: & (.)) (va3e)) Ofi(u..))
Σ
W++1 W. " B
B
Wee use V to denote gradient of a differentiable function and 0 to denote a subgradient of a non-smooth function.

---

Table 1: Comparison with prior works for solving T and 2
In the monotonicity column, notation 1 means the given function required be non-decreasing. not specified, the given function is only required to be monotone.
Method
Objective
Smoothness
Weak Convexity
Monotonicity
Complexity
SOX 26
Ji.9i
none none
none none
(
MSVR 15
ft.9:
O
SONX (Ours)
none
fi.
Si
O
SONT (Ours)
none
f1: Fs.9s. his
ft 1.9: t
(
SONT (Ours)
hij
fi.9h
fi 1,199
O(E
where B, and BR are random mini- bini-batches of B1 and Bg items, respectively, and ui, is an appropriate variance-reduced estimator of L Ejes, gi (We)) that is updated only for i B,, and Di.,, is an uppropriate variance-reduced estimator of (e.((,) that is updated only for E Bl. E B. To prove the convergence, we impose conditions of fi, gt, hig., i.c., f. is weakly convex and non-decreasing and g:(-) is weakly convex and non-decreasing (or monotonic), hij is weakly convex (or smooth), and establish an iteration complexity of T = O (c-t) for finding an e-stationary point of the Moreau envelope of F-)).
nz
We extend the above algorithms to solving deep learning, and conduct extensive experiments to verify the effectiveness of the both algorithms.
two-way partial AUC maximization for
2 Related work
Smooth SCO.
There are many studies about two-level smooth SCO 27 38 10
28 and
multi-level smooth SCO 33
39]. The complexities of finding an e-stationary point for two- level smooth SCO have been improved from O(E (27) to O [9]] and that for multi-level
smooth SCO have been improved from a level-dependent complexity of O 0(c-(7+K)/2)
32 to
level-independent complexity of O(c [2). where K is the number of levels. The improvements mostly come from using advanced variance reduction techniques for estimating each level function or its Jacobian and for estimating the overall gradient. Two stochastic algorithms have been developed in 13 for CSO but suffer limitation of requiring large batch sizes.
Smooth FCCO. FCCO first introduced in 20 for optimizing average precision. Its algorithm and convergence analysis was improved in (26 and [15]. The former work (26) proposed an algorithm named SOX by using moving average (MA) to estimate the inner function values and the overall gradient. In the smooth non-convex setting, SOX is proved to achieve an iteration complexity of O The latter work [15] proposed novel multi-block-single-poi estimator for estimating the inner function values, which helps achieve a lower iteration complexity O(e Recently, [ proposed an extrapolation based estimator for the inner function, which yields method with complexity that matches MSVR when n S 2/3 These techniques have been employed for optimizing various X-risks, including contrastive losses [36), ranking measures and However, all of these prior works assume the smoothness of f; and 9;. Hence, their analysis is not applicable to NSWC FCCO problems. Our novel analysis of a simple algorithm for NSWC FCCO problems yields an iteration complexity of (c--)) for using the MSVR estimators of the inner functions. The comparison with [26] [5] is shown in T
variance reduced (MSVR)
listwise losses (2T), and other objectives (26 15
Non-smooth Weakly Convex Optimization, Analysis of weakly convex optimization with unbiased stochastic subgradients was pioncered by 7. Optimization of compositional functions that are weakly convex have been tackled in earlier works [8]]. where the inner function is deterministic or does not involve coupling between two random variables. A closely related work to our NSWC
FCCO is weakly-convex concave minimax optimization [22] Assuming f; is convex, ① can be written as: minw maX 1
p Eies (T;. 9: (w) f (T,) where f:) is the convex conjugate of
fi. It can be solved using existing methods 12
B1
41
43 17 but with several limitations: (i) the
algorithms in [22 31 41 43 have comparable complexity of (11/E)) but have unnecessary double
loops which require setting the number of iterations for the inner loop; (ii) the algorithm in [17] single loop but has a worse complexity of (11/e); (iii) these existing algorithms and analysis does not account for complexity of updating all coordinates of which could be prohibitive in
3

---

many applications; iv) these approaches are not applicable to NSWC FCCO/TCCO with weakly convex ft. In fact, the double loop algorithm has been leveraged and extended to solving the two-way partial AUC maximization problem, special case of NSWC FCCO A4. by sampling and updating batch of coordinates of π at each iteration. However, is less practical thus not implemented and its analysis did not explicitly show the convergence rate dependency on nl,, n_ and the block batch size.
special case of NSWC SCO problem was considered in [46), which is given by
minsex [xr g(x)), with [(x u) = R [u + x (0, gx;; <) w)]; g(x) - (e(g((;()))
They proposed two methods, SCS for smooth g(x) and SCS with SPIDER for non-smooth g(x). For both proposed methods, they proved sample complexity of (1/ce)) for achieving an c-stationary point of the objective's 's Moreau envelope 2 We would like to remark that the above problem with a non-smooth g(z)) is special case of NSWC FCCO with only convex outer function, one block and no coupled structure. Nevertheless, their algorithm for non-smooth g()) suffers a limitation of requiring large batch size in the order of ((1/c²) for achieving the same convergence.
Finally, we would like to mention that non-smooth convex or strongly convex SCO problems have been considered in 127 42 26). which, however, are out of scope of the present work.
3 Preliminaries
Let || be the Euclidean norm of vector and spectral norm of a matrix. We use Ic(: denote the Euclidean projection onto {u E R" ||||| S C). For vectors, inequality notations including
S. 2.2.,, >, are used to denote element-wise inequality. For expectation function f()) = (x
let f(:
EeEB f(:: E) be its stochastic unbiased estimator evaluated on sample batch B. A | < a². The
stochastic unbiased estimator is said to have bounded variance o² if [I)()) [
Jacobian matrix of function f mR Te is in dimension mR x We recall the definition of general subgradient and subdifferential following 66 24
Definition 3.1 (subgradient and subdifferential). Consider function f R. - R U {oo} and point with (()) finite. A vector U E R. is a general subgradient of ʃ at x; if
f(y)= 2 f(x) + (v,y - z) + o(lly y - æ11), as y + x. The subdifferential 0z is the set of subgradients of f at point
For simplicity, we abuse the notation and also use Of(z) denote one subgradient from the corresponding subgradient set when no confusion could be caused. We use 0f(z: B) to represent a stochastic unbiased estimator of the subgradient (z) that evaluated on sample batch A function is called C'-smooth if it is continuously differentiable. A function ʃ = (fi,..., fmg)) TM - Rm= called monotone if Vi E (1...., m22) Js m -> TR is monotone with respect to each element of the input. Note that if a Lipschitz continuous function f O - R is assumed to be non-increasing (resp. nondeccre,,,ng), where the domain O C T is open, then all subgradients of f are element-wise non-positive (resp. non-negative). We refer the details to Appendix D.I D.I
function f is C-Lipschitz continuous if fz) f(wll S C'I yll. differentiable function is L-smooth if (x)) / L||0 y/|. A function ʃ IRd - R U {oo} is p-weakly-convex
if the function f(.) + & 1|2 is convex. A valued function f : Fd (IR U [oc]]m rm is called p-weakly-convex if it is p-weakly-convex for each output. is difficult sometimes impossible to find an c-stationary point of non-smooth weakly-convex function F, i.e., dist(0, (F)))) S c. For example, an c-stationary point of function f(x) = |ar] does not exist for 0 < c < 1 unless it is the optimal solution. To tackle this issue, (6) proposed use the stationarity of the problem's 's Moreau envelope as the convergence metric, which has become a standard metric for solving weakly-convex problems 22 41 43 17]. Given weakly-convex function y R RR its Moreau envelope and proximal map with X > 0 are constructed as
(x) == min( + 2X Ily - x1)?), prox (T) == arg arggmin + Ily - ==1?
2x
The Moreau envelope is an implicit smoothing of the original problem. Thus it attains continuous differentiation. As a formal statement, the following lemma follows from standard results 6 18).
Lemma 3.2. Given coweakly-convexffee gradient given by (x)(2)= = > -- - x (x)).
ip and À < p the envelope y is -m-mooth with
It is notable that we use slightly different definition of c-stationary point with [[) <

---

Algorithm Stochastic Optimization algorithm for Non-smooth FCCO (SONX)
Initialization: Wo. {ulo 8}.
2: for t = O,..., - do
3: Draw sample batches Bi S. and 2, ~ D; for each Bi. (1 T)us, + (e:gg((;;)) 22 +gg (w:; (3,)) - 9: (: e B3
4: W1,++
Ui i Bi
5: Compute G. 1 Eie dg. (w; (a ((,)) Bi
6: Update W = Wt r/Ct
7:
end for
Moreover, for any point æ E RT the proximal point == prox satisfies [6
6 - -||
X (z))l (()) S (px),, dist(0, 0p(G)) S [Vxx((=)]-
Thus if [x) c, we can say is close to point that is c-stationary, which is called nearly e-stationary solution of pxx).
4 Algorithms and Convergence
4.1 Non-Smooth Weakly-Convex FCCO
In this section, we assume the following conditions hold for the FCCO problem 1 Assumption 4.1. For all i S, we assume that
Ji is w--wellly-coovex Cy-Lipschitz continuous and non-decreasing;
(+)-) is Py- wow-wwallycoveee and g+(:: is Cy-Lipschitz continuous;
Stochastic gradient estimators 9, (w: {) and (g:(w; E) have bounded variance o².
Proposition 4.2. Under Assumption 4.1 F(w) in (7) is pr weakly convex with pr CTipo
P.Cy-
One challenge in solving FCCO is the lack access to unbiased estimation the subgradients Eies ( (g.()) due to the expectation form of g, (w) inside non-linear function fi. A common solution in existing works for solving smooth FCCO is to maintain function value estimators {u, E S} for {g, (w)
S), and approximate the true gradient by stochastic version B1 Eies, ög. [2) 266 13), where B1, B2 are sampled mini-batches. Simply using a mani-batch estimator gi inside fo does not ensure convergence mini-batch size is small.
Inspired by existing algorithms of smooth FCCO, simple method for solving non-smooth FCCO presented Algorithm referred as SONX. key step the step 4, which uses the multi- block-single-pruc prrooe variance reduced (MSVR) estimator proposed in [15] to update {u, : E S} in a block-wise manner. It is an advanced variance reduced update strategy for multi-block variable inspired by STORM (5). In the update of MSVR estimator, for each sampled E B U4, is updated following STORM-liK. rule with specialized parameter y
B[[1 + (1 T) for the error
n-B,
correction term. For the unsampled i g B), no update for w,, is needed. When O, the estimator becomes the moving average estimator analyzed in 266 for smooth FCCO, which is also analyzed in the Appendix. With the function values of {g:( We) : E S} well-estimated, the gradient can be approximated by G, in step 5. Next, directly update w, by subgradient descent using the stochastic gradient estimator Gr. Note that unlike existing works on smooth FCCO that often maintain moving average estimator (26) or a STORM estimator [15] for the overall gradient to attain better rates, this is not possible in the non non-smooth case as those variance reduction techniques for the overall gradient critically rely on the Lipschitz continuity of F., i.e., the smoothness of F.
4.2 Non-Smooth Weakly-Conver TCCO
In this section, we consider non-smooth TCCO problem and aim to extend Algorithm solve it. First all, for convergence analysis and to ensure the weak convexity of F(w) in ( we make the following assumptions.
Assumption 4.3. For all (i.j) Si X S2, we assume that
5

---

Algorithm 2 Stochastic Optimization algorithm for Non-smooth TCCO (SONT)
I: Initialization: Wo, {uco SiJ, vi.,0 ha B,,,,) for all (i,j) E S] x S2.
2: for ( .,..., do
3: Sample batches Bi C S1, B3 C S2, and B C Diy for e Bi and j E Bi
II C [[1 Ti Va.je rahi, B Ba + 7n (ha, (ha,)(We; B3 B3 -as.shhe-sae (Wo-1;
4: vij,+1
(1.j) Bi x B3
Vi.it: (1,5) & Bi x B
(1-T2)ua T2) + 1 E JE Tag (1 + +2 - i B
5: 04,+11
Uitt: i Bi
1 Eier; 6: G Bi
( B3 Eiegg Vh, V (fs)) (f((ur)))
7: Update Wx+1
Wt 10--y nG,
8: end for
Si is Cy-Lipschitzz continuous, -e-wellly-coovee and non-decreasing;
9i is wg-weakly-convex and Cy-Lipschitz continuous. (= {) is C₁ -iisschcttzz continuous.
Either gi is non-decreasing, hisj is LA wn-weakkl-convex or 9i is monotone, h4,j is Ls-smooth.
Stochastic estimators bi. (w, {) and o {) have bounded variance o², and [h),s()) S Ch. (.llg((v) Ejes, De (v) I o² for any v.
The weak convexity F(w) ( is guaranteed by the following Proposition. Proposition 4.4. Under Assumption
4.3 F(w)
in 2 is Pp-weakly-comvex with PF
Vdd(VaL + Ps C, + Ps
We extend SONX to Algorithm for 2 which is referred SONT. For dealing with the extra layer of compositional problem, we maintain another multi-block variable to track the extra layer of function value estimation. To understand this, we first write down the true subgradient:
(F(w) = 1 Σ ies, 11
(- JES, Vhu,(w) 0g. (hs.) (w)) 0f
Σ 122
( (i(hes(w))
E
T12
To approximate this subgradient, we need the estimations of ng
((hh,,(w)) and he (w). E)ss,gr
which can be tracked by using MSVR estimators denoted by {ur, E S1} and {ri (i,j) E S x S2). respectively. As result, stochastic estimation of FF(w)) is computed in step 6 of Algorithm and the model parameter updated similarly as before.
4.3 Convergence Analysis
In this section, we present the proof sketch of the convergence guarantee for Algorithm 1 The analysis for Algorithm follows in a similar manner. The detailed proofs can be found in Appendix A (please refer to the supplement). Before starting the proof, we define a constant M Z C.. so that
under Assumption 4.1 we have E, [] < M22 Then we start by giving the error bound of the MSVR estimator in Algorithm [ The following norm bound of the estimation error follows from the squared-none norm error bound in Lemma 1 from [15), whose proof is given in Appendix D.3
Lemma 4.5, Consider the update for {ui, : E S} in Algorithm
Assume gi is Cg Cipihishitzfoo for all 7
E S. With y =
n (1-) + (1- ), TS 2. we have
| ( (We+1))
< <11
Bi +
)
ge (wo)l
272
4nC
2n
12
B,7
For simplicity, denote by w. = pppxp pyp (wt). Then using the definition of Moreau envelope and the update rule of wt, obtain a bound for the change in the Moreau envelope,
S Fi/)(we) + pn(w; w,, E,(G,)) pMp
F
(5)
2
where [x = Eies, (w, is the subgradient approximation based on the MSVR estimator Ui of the inner function value. This is standard result in weakly-convex optimization [6].

---

To bound the inner product -W, W,,,,( on the sight-hand-ae side of ()) we apply the assumptions that fi is weakly-convex, Lipschitz continuous and non-decreasing, and gi is weakly-convex. Its upper bound is given as follows.
(w,- ww) [E & F(w,) F(wi)+ + -If((o(w))) - f((u,)) - (f(()))) (g:(we) ui.e)
iES
( PgCC
+ prllss((w)) u1.ell +
+ ps p,C)))l w.ll
(6)
2
Due to the Pp-weak convexity of F(w), we have (p- - PF >stong convexity of w + F(w)+ wr
w 1.2 Then it follows F(w,)- F(we) I ( - -p]l[ -o - w.ll Combining this with inequalities 5
and setting P sufficiently large we have
E, [//Fi/a W w - (we)(we) + ?PpM²
2 + PU Σ
_ iES 1-1,- -wrl2
+ fe (w.)) - fu,,)) - 0f.( (g:(w.) u1,s) + Ps (rllg:(ws)) u
3.2 we have l|w, w 72 (VFi)o(w.)l Moreover, the last three terms on the R.H.S of inequality 7 can be bounded using the Lipschitz continuity of f; and the error bound given
Recall Lemma
Lemma 4.5 Then we can conclude the complexity of SONX with the following theorem.
Theorem 4.6. Under Assumption
4.1 with
n-B,
+ + - T), T O(B2c*) < 1 1
BI(I-
0 ( B,B, ) and p + Pg Cj + 2p Algorithm converges to an e-stationary point of the Moreau envelope Fiip in T = 0
6) iterations.
Remark. Similar to the complexity for smooth FCCO problems 26 15]. Theorem (.6 g..agguaatttsss that SONX for NSWC FCCO has a parallel speed-up in terms of the batch size B1 and linear dependency on n. The dependency of the complexity on the batch size Bg is due to the use of MSVR estimator, which matches the results in 15]. If the MSVR estimator in SONX is replaced by moving average estimator, the complexity becomes O B,
c $) (cf. Appendix B
Following a similar proof strategy, the convergence guarantee of Algorithm 2 is given below.
Theorem 4.7. (Informal) Under Assumption 4.3 with appropriate values of 7/ 72, T1, T2, 7 and proper constant p. Algorithm 2 converges to e-stationary point of the Moreau envelope Fitp in
T=O max
ni / B n//41 B
11
1/2
n182 c iterations.
B, B3
Remark. In the worst case, the complexity has a worse dependency on n1/ / B i.e. Onn 3/2 /B//2) This is caused by the layers of block-sampling update for {wi,, i E Si} and {vija (t,j) Si x S2). When nı B, = and B3 S /nz. the complexity of SONT becomes similar as SONX, which is understandable the inner two levels in TCCO the same as FCCO.
5 Applications
NSWC FCCO finds important applications in group distributionally robust optimization (group DRO) and wo-wway partial AUC (TPAUC) maximization.
Consider N groups with different distributions. Each group l has an averaged loss (u( 1 Et {(fur (x/²) vf), where is the the model parameter and (x++ u²²) is data point. It has been Tu
shown in previous study 23 that the group DRO problem can be formulated into
N
min min F(w, 8)
1
Σ
[L (w) - s]+ +
K
This formulation can be mapped into non-smooth weakly-convex FCCO under certain assumptions. Due to space limitation, we defer the comprehensive discussion of group DRO to Appendix The rest of this section focuses TPAUC maximization.
Let denote an input example and (X) denote a prediction of parameterized deep net on data X. Denote by S+ the set of n4 positive examples and by S_. the set of n... negative examples. TPAUC measures the area under ROC curve where the true positive rate (TPR) higher than a and the false positive rate (FPR) is lower than upper bound B. A surrogate loss for optimizing TPAUC
7

---

with FPR B, TPR2 a is given by [3
min 1 T4. E Xies! [111]]
Ex [1,ba]
(X)((X)) - hw (Xi)),
(8)
where ((.) is a convex, monotonically non-decreasing surrogate loss of the indicator function I(hw (X₃) 2 hw (Xi)), St. [1, k1] is the set of positive examples with h = [n+a] smallest scores, and S [1, 12] is the set of negative examples with lo2 = |n largest scores. To tackle the challenge of selecting examples from S.. [1, k1] and S [1. ka], the above problem is cast into the following 44
Ex.es, E(W:(w.. (W.)(. s').
min
w.s' i 1
where S4(g,8') = = 8' (g (9-5)> (w, n x,,ss 8, (e(hw(X) hw (Xx)) si)+ αx
-
B
where s = (S1...., ,,.) We will consider two scenarios, namely regular learning scenario where X, E Re is an instance, and multi-instance learning (MIL) scenario where X, {x!..... x E Rdo contains multiple instances (e.g., one patient has hundreds of high-resolution CT images). A challenge in MIL is that the number of instances m, for each data might be large such that it is difficult to load all instances into the memory for mini-batch training. It becomes more nuanced especially because MIL involves a pooling operation that aggregates the predicted information of individual instances into single prediction, which can be usually written as compositional function with the inner function being an average over instances from X, For simplicity of exposition, below we consider the mean pooling (w(() [X| Exex <(W,;))) Wes where e(We: x) is the encoded feature representation of instance x with a parameter Wa, and w, is the parameter of the classifier. We will map the regular learning problem as NSWC FCCO and the MIL. problem as NSWC TCCO.
The problem (9) is slightly more complicated than (1 (2) due to the presence of s', In order to understand the applicability of our analysis and results to (9). we ignore s', s for a moment. In the regular learning setting when hw (X) el e(We, x)" we can be directly computed,
can map the problem into NSWC FCCO, where fi(g, s') is non-smooth, convex, and non-decreasing in terms of g, and (w,,s))
(w, w, 8;) is non-smooth, and is proved to be weakly when E(-) is convex and hw (X) is smooth in terms of w. In the MIL setting with mean pooling, we can map the problem into NSWC TCCO by defining (w))) = [xT ExEx, (We:)) We. hus (w) = hy (w) - h,(w) and and fi(g,,s) s' (s:-5)= where fi is non-smooth, convex, and non-decreasing in terms of gs- and g (hay (w),&)) is non-smooth, convex, monotonic in terms of (w) when {(-) is convex and monotonically non-decreasing, and gi (heg (w). s;) is weakly convex in terms of w when huy (w) is smooth and Lipchitz continuous in terms of w. Hence, the problem (9) satisfies the conditions in Assumption 4. for the regular learning setting and that in Assumption 4.3 for the MIL. with mean pooling under mild regularity conditions of the neural network. We present full details in Appendix C.T interested readers.
ge (e(h,,()),,
s; (w)),, B
To compute the gradient estimator w.r.t w, U.S, will be maintained for tracking g: (w, s;) in the regular setting or _ Ex,es 9:(hi, (w), s;) in the MIL setting, Us,t will be maintained for tracking h; aー in the MIL setting, which are updated similar to that in SONX and SONT. One difference from is decoupled into Us, and U/es due to that he.j can be decoupled. In terms of the SONT is that L s. the objective function is convex w.r.t both s' and s, which allows us to simply extra variable
update s' by SGD using the stochastic gradient estimator B,, EiEst Oz Ji(wi,t, 66) and we update
s; by SGD using the stochastic gradient estimator Bg jj 0g.g Ue,e, s2,)) (u $)).
1
Detailed updates presented in Algorithm 5 and Algorithm o in Appendix C.2 We extend the convergence analysis of SONX and SONT to the two learning settings of TPAUC maximization, which is included in Appendix C.4 Finally, is worth mentioning that we can also extend the results to other pooling operations, including smoothed max pooling and attention-based pooling 45 Due to limit of space, we include discussions in Appendix as well.
Experimental Results
We justify the effectiveness of the proposed SONX and SONT algorithms for TPAUC Maximization in the regular learning setting and MIL setting [4 45).
8

---

Table 2: Testing TPAUC on molecule datasets (top) and on MIL datasets (bottom). The two numbers in parentheses of the second line refers to the lower bound of TPR and the upper bound of FPR for evaluating TPAUC. The two numbers of each method refers to the mean TPAUC and its std.
moltox21 (1O)
molmuv (t1)
molpcba (10)
Method
(0.6,
(0.5, 0.5)
(0.6, 0.4)
0.5)
(0.6, 0.4)
0.5)
CE
0.067 (0.001)
0.208 (0.001)
0.161 (0.034)
0.469 (0.018)
0.095 (0.001)
0.264 (0.001)
AUC-SH
0.064 (0.008)
0.217 (0.014)
0.260 (0.130)
0.444 (0.128)
0.140 (0.003)
0.312 (0.003)
AUC-M
0.066 (0.009)
0,209 (0.01)
0.114 (0.079)
0.433 (0.053)
0.142 (0.009)
0.313 (0.003)
MB
0.067 (0.015)
0,215 (0.023)
0.173 (0.153)
0.426 (0.118)
0.095 (0.002)
0.262 (0.003)
AW-poly
0.064 (0.01)
0.206 (0.025)
0.172 (0.144)
0.393 (0.123)
0.110 (0.001)
0.281 (0.002)
SOTA-s
0.068 (0.018)
0.23 (0.021)
0.327 (0.1
0.526 (0.1
0.143 (0.001)
0.314 (0.002)
SONX
0.07 (0.035)
0.252 (0.025)
0.347 (0.175)
0.575 (0.122)
0.158 (0.006)
0.335 (0.006)
MUSK2
Fox
Method
0..3.0.5)
0.73
(0.1.0.9)
(0.5, 0.5)
(..3.0.7
(0.1. 0.9)
AUC-M (att)
0.675 (0.1)
0.783 (0.067)
0.867 (0.036)
0.032 (0.03)
0.253 (0.098)
0,444 (0.118)
MIDAM (smx)
0,525 (0.2)
0.667 (0.149)
0.8 (0.097)
0.048 (0.059)
0.265 (0.119)
0.449 (0.113)
MIDAM (att)
0.6 (0.215)
0.717 (0.135)
0.819 (0.092)
0.016 (0.032)
0.249 (0.125)
0.509 (0.065)
SOTAS (att)
0.6 (0.267)
0.683 (0.178)
0.819 (0:097)
0.024 (0.032)
0.278 (0.059)
0.477 (0.046)
SONT (att)
0.7 (0.1)
0.8 (0.067)
0.867 (0.036)
0.12 (0.131)
0.343 (0.176)
0.578 (0.119)
Colon
Lung
Method
0.3)
(.73,
(0.1.
(0.5, 0.5)
(..3.0.7)
(0.1, 0.9)
AUC-M (att)
0.576 (0.1)
0.739 (0.061)
0.803 (0.038)
0.32 (0.181)
0,609 (0.113)
0,744 (0.082)
MIDAM (smx)
0.646 (0.083)
0.787 (0.04)
0.863 (0.026)
0.43 (0. 195)
0.68 (0. (0.128)
0.824 (0.055)
MIDAM (att)
0.548 (0.253)
0.738 (0.149)
0.826 (0.102)
0.544 (0.261)
0.716 (0.189)
0.815 (0.1
SOTAs (att)
0.772 (0.124)
0.862 (0.073)
0.911 (0.045)
0.539 (0.153)
0.745 (0.077)
0,841 (0.049)
SONT (att)
0.8 (0.166)
0.875 (0.099)
0.916 (0.065)
0.639 (0.137)
0.779 (0.041)
0.865 (0.028)
Baselines. For regular TPAUC maximization, we compare SONX with the following competitive methods: 1) Cross Entropy (CE) loss minimization; 2) AUC maximization with squared hinge
loss (AUC-SH); 3) AUC maximization with min-max max margin loss (AUC-M) [37]: 4)
based heuristic loss (MB) [6]: 5) Adhoc- Weighting based method with polynomial function (AW- poly) [35]: 5) single-loop algorithm (SOTAs) for optimizing smooth surrogate for TPAUC [44] For MIL TPAUC maximization, we consider the following baselines: 1) AUC-M with attention-basee
pooling (AUC-M [att]): 2) SOTAs with attention-based pooling, which is a natural combination between advanced TPAUC optimization and MIL pooling technique; 3) the recently proposed provable multi-instance deep AUC maximization methods with stochastic smoothed-mas pooling and attention-based pooling (MIDAM [smx] and MIDAM [att]) 45). The first two baselines use naive mini-batch pooling for computing the loss function in AUC-M and SOTAs. We implement SONT for MIL TPAUC maximization with attention -based pooling, which is referred to as SONT (att).
Datasets. For regular TPAUC maximization, we use three molecule datasets as in 44 namely moltox21 (the No.0 target), molmuv (the 1 target) and molpeba (the No.0 target) (29 For MIL TPAUC maximization, we use four MIL datasets, including two tabular datasets MUSK2 and Fox, and two medical image datasets Colon and Lung. MUSK2 and Fox are two tabular datasets that have been widely adopted for MIL benchmark study [14.. Colon and Lung are two histopathology (medical image) datasets that have large image size (512x512) but local interests for classification (2]. For Colon dataset, the adenocarcinoma is regarded as positive label and benign is negative; for Lung dataset, we treat adenocarcinoma as positive and squamous cell carcinoma as negative F For both of the histopathology datasets, we uniformly randomly sample 100 positive and 1000 negative data for experiments. For all MIL datasets, we uniformly randomly split 10% as the testing and the remaining as the training and validation. The statistics for all used datasets are summarized in Table and Table 4 in Appendix [F)
Experiment Settings. For regular TPAUC maximization, we use the same setting as in 44 The adopted backbone Graph Nueral Network (GNN) model is Graph Isomorphism Network (GIN), which has 5 mean-pooling layers with 64 number of hidden units and dropout rate 0.5 [30] We utilize the sigmoid function for the final output layer to generate the prediction score, and set the surrogate loss E(.) as squared hinge loss with a margin parameter. We follow the setups for model training and tuning exactly the same as the prior work (4). Essentially, the model is trained by 60 epochs and the learning rate is decreased by 10-fold after every 20 epochs. The model is initialized as a pretrained model from CE loss on the training datasets. We fix the learning rate of SONX as le-2 and moving average parameter 7 as 0.9; tune the parameter 7 in {0, 1e-1,1e-2,1c- ). the parameter a, B in (0. J and fix the margin parameter of the surrogate loss as 1.0, which cost the same
Data available: https: httpps//www.xggeee.cco//c///c//a http://wwg....ooaaaaaaaaa/aaaaaa
caaud-oolon-coo cancer

---

Epects
Eooda
Ezacha
Spocts
(a) molmuv (t1)
(b) molpeha (10)
(c) MUSK2
(d) Fox
Figure 1: Training Curves of SONX (left two) and SONT (right two) for TPAUC maximization with different y. The y-axis the TPAUC (0.5, 0.5).
tuning effort as the other baselines. The weight decay is set as the same value (2e-4) with the other baselines. For baselines, we directly use the results reported in 44] since we use the same setting.
For MIL TPAUC maximization, we train a simple Feed Forward Neural Network (FFNN) with one hidden layer (the number of neurons equals data dimension) for the two tabular datasets and ResNet20 for the two medical image datasets. Sigmoid transformation is adopted for the output layer to generate prediction score. The training epoch number is fixed as 100 epochs for all methods; the bag batch size is fixed as 16 (resp. 8) and the number of sampled instances per bag is fixed as 4 (resp. 128) for tabular (resp. medical image) datasets; the learning rate is tuned in ( [1e-2, 1e-3, le-4) and decreased by 10 folds at the end of 50-th and 75-th epoch for all baselines. For SONT (att), we set moving average parameter 71 72 as 0.9; tune the parameter 71 7/2 = y in {0, le-1, 1e-2,ee33) and fix the margin parameter of the surrogate loss l as 0.5, and the parameter a, 3 in (0.1.0.5,0.9). Similar parameters in baselines are set the same or tuned similarly. For all experiments, we utilize soold-ccoss-validatii to evaluate the testing performance based on the best validation performance with possible early stopping choice.
Results. The testing results for the regular and MIL TPUAC maximization with different TPAUC measures are summarized in the Table From Table 2 we observe that our method SONX achieves the best performance for regular TPAUC maximization. It is better than the tate-offtthe-art method SOTAs for TPAUC maximization. We attribute the better performance of SONX to the fact that the objective of SONX is an exact estimator of TPAUC while the smoothed objective of SOTAs is an inexact estimator of TPAUC. We also observe that SONT (att) achieves the best performance in all cases, which is not surprising since it is the only that directly optimizes the TPAUC surrogate. In contrast, other baselines either optimizes a different objective (MIDAM) or does not ensure convergence due to the use of mini-batch pooling (AUC-M, SOTAs).
Ablation Study. We conduct ablation studies demonstrate the effect of the error correction term on the training convergence by varying the 7 value for SONX and SONT, where 2 =/2 = is set as the same value in SONT. The training convergence results are presented in Figure [ We can see that appropriate value of 0 can yield faster convergence than 7 0. which verifies the faster convergence of using MSVR estimators than using moving average estimators. However, we do observe gap between theory and practice, as setting a large value of > 1 as in the theory might not yield convergence. This phenomenon also observed in [12]. We conjecture that the gap could be fixed by considering convex objectives [40], which is left as future work.
7 Conclusions
In this paper, we have considered non-smooth weakly-convex two-level and tri-level finite-sum coupled compositional optimization problems. We presented novel convergence analysis of two stochastic algorithms and established their complexity. Applications in deep learning for two-way partial AUC maximization was considered and great performance of proposed algorithms were demonstrated through experiments on multiple datasets. A future work to prove the convergence of both algorithms for convex objectives.
Acknowledgements
We thank anonymous reviewers for constructive comments. Q. Hu. D. Zhu and T. Yang were partially supported by NSF Career Award 2246753, NSF Grant 2246757, 2246756 and 2306572.
10

---

References
[1] Krishnakumar Balasubramanian, Saeed Ghadimi, and Anthony Nguyen. Stochastic multilevel composition optimization algorithms with level-independent convergence rates. SIAM Journal on Optimization, 32(2):519 194444,442244 2022.
[2] Andrew A Borkowski, Marilyn M Bui, L Brannon Thomas, Catherine P Wilson, Lauren A DeLand, and Stephen M Mastorides. Lung and colon cancer histopathological image dataset (lc25000). arXiv preprint arXiv:1912.12142 2019.
[3] Tianyi Chen, Yuejiao Sun, and Wotao Yin. Solving stochastic compositional optimization nearly as easy as solving stochastic optimization. IEEE Transactions Signal Processing, 19:4937-4948 2021.
[4] Sebastian Curi, Kfir Y. Levy, Stefanic Jegelka, and Andreas Krause. Adaptive sampling for stochastic risk-averse learning. In H. Larochelle, M. Ranzato. R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 1036-1047. Curran Associates, Inc., 2020.
[5] Ashok Cutkosky and Francesco Orabona. Momentum- based variance reduction non-convex sgd. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[6] Damek Davis and Dmitriy Drusvyatskiy. Stochastic model-based minimization of weakly convex functions, 2018.
[7] Damek Davis and Benjamin Grimmer. Proximally guided stochastic subgradient method for nonsmooth, nonconvex problems. SIAM Journal on Optimization, 1983);1908-1930, 2019.
[8] Dmitriy Drusvyatskiy and Courtney Paquette. Efficiency of minimizing compositions convex functions and smooth maps. Math. Program., (78(1-2):503-558 2019.
[9] John C. Duchi and Feng Ruan. Stochastic methods for composite and weakly convex optimiza- tion problems. SIAM Journal on Optimization, 28(4):3229 022599999999999,, 2018
[10] S. Ghadimi, Andrzej Ruszezy' nski, and Mengdi Wang. A single timescale stochastic approxi- mation method for nested stochastic optimization. SIAM J. Optim., 30:960-977 9790099997000 2020.
[11] Lie He and Shiva Prasad Kasiviswanathan. Debiasing conditional stochastic optimization, 2023.
[12] Quanqi Hu, Zi-Hao Qiu, Zhishuai Guo, Lijun Zhang, and Tianbao Yang. Blockwise stochastic veriaede-reduced methods with parallel speedup for multi-block bilevel optimization. In Proceedings of the 39th International Conference Machine Learning, 2023.
[13) Yifan Hu, Siqi Zhang, Xin Chen, and Niao He. Biased stochastic first-order methods for conditional stochastic optimization and applications in meta learning. Advances in Neural Information Processing Systems, 33, 2020.
[14] Maximilian Ilse, Jakub Tomezak, and Max Welling. Attention- based deep multiple instance learning. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 2127-2136. PMLR, 10-15 Jul 2018
[15] Wei Jiang, Gang Li, Yibo Wang, Lijun Zhang, and Tianbao Yang. Multi-block-singlee probe variance reduced estimator for coupled compositional optimization, 2022.
[16] Purushottam Kar, Harikrishna Narasimhan, and Prateek Jain. Online and stochastic gradi- ent 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.

---

[17] Tianyi Lin, Chi Jin, and Michael Jordan. On gradient descent ascent for nonconvex concave minimax problems. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th Inter- national Conference on Machine Learning. volume 119 of Proceedings of Machine Learning Research, pages 6083-6093. PMLR, 13-18 Jul 2020.
[18] J.J. Moreau. Proximité et dualité dans un espace hilbertien. Bulletin de la Société Mathématique de France, 93:273-299, 1965.
[19] Qi Qi, Zhishuai Guo, Yi Xu, Rong Jin, and Tianbao Yang. An online method for class of distributionally robust optimization with non-convex objectives. Advances in Neural Information Processing Systems, 34, 2021.
[20] Qi Qi, Youzhi Luo, Zhao Xu, Shuiwang Ji, and Tianbao Yang. Stochastic optimization of area under precision-recal curve for deep learning with provable convergence. In Advances in neural information processing systems, volume abs/2104.08735 2021.
[21] Zi-Hao Qiu, Quanqi Hu, Yongjian Zhong, Lijun Zhang, and Tianbao Yang. Large-scale stochastic optimization of NDCG surrogates for deep learning with provable convergence. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 18122-18152. PMLR, 17-23 Jul 2022.
[22] Hassan Rafique, Mingrui Liu, Qihang Lin, and Tianbao Yang. Weakly-conver ceaell--covxx-ccneeee concave min-max optimization: provable algorithms and applications in machine learning. Optimization Methods and Software, 37(3): 1087-111, 2022.
[23] R. T. Rockafellar and S. Uryasev. Optimization of conditional valueat-risk. Journal of Risk, 2(3), 1999.
[24] R.T. Rockafellar, M. Wets, and R.J.B. Wets. Variational Analysis. Grundlehren der mathematis- chen Wissenschaften. Springer Berlin Heidelberg, 2009.
[25] Shiori Sagawa, Pang Wei Koh, Tatsunori B. Hashimoto, and Percy Liang. Distributionally robust neural networks for group shifts: On the importance of regularization for worst-case generalization, 2020.
[26] Bokun Wang and Tianbao Yang. Finite-sum coupled compositional stochastic optimization: Theory and applications. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Reseurch, pages 23292- 23317. PMLR, 17-23 Jul 2022.
[27] Mengdi Wang, Ethan X Fang, and Han Liu. Stochastic compositional gradient descent: algo- rithms for minimizing compositions of expected-value functions. Mathematical Programming, 161(1-2):4194444 2017.
[28] Mengdi Wang, Liu, and Ethan X. Fang. Accelerating stochastic composition optimization, 2016.
[29] Zhenqin Wu, Bharath Ramsundar, Evan N Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh Pappu, Karl Leswing, and Vijay Pande. MoleculeNet: benchmark for molecular machine learning. Chemical science, 912):513-530, 2018
[30] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In 7th International Conference on Learning Representations, 2019.
[31] Yan Yan, Yi Xa, Qihang Lin, Wei Liu, and Tianbao Yang. Optimal epoch stochastic gradient de- scent ascent methods for min-max optimization. In Advances in Neural Information Processing Systems 33 (NeurIPS), 2020.
[32] Shuoguang Yang, Mengdi Wang, and Ethan X. Fang. Multi-level stochastic gradient methods for nested composition optimization, 2018.
12

---

[33] Tianbao Yang, Algorithmic foundation of deep x-risk optimization. CoRR, abs/2206.00439,
2022.
[34] Tianbao Yang and Yiming Ying. AUC maximization in the era of big data and AI: A survey. ACM Comput, Surv., 55(8):172:1-172:77 2023.
[35] 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 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 11820-11829. PMLR, 18-24 Jul 2021.
[36] Zhuoning Yuan, Yuexin Wu, Zi-Hao Qiu, Xianzhi Du Lijun Zhang, Denny Zhou, and Tianbao Yang. Provable stochastic optimization for global contrastive learning: Small batch does not harm performance. In Kamalika Chaudhuri. Stefanie Jegelka, Le Song, Csaba Szepesvari. Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Muchine Learning Research, pages 25760-25782. PMLR, 17-23 Jul 2022.
[37] Zhuoning Yuan, Yan Yan, Milan Sonka, and Tianbao Yang. Large-scale robust deep auc maximization: A new surrogate loss and empirical studies on medical image classification, 2021.
[38] Junyu Zhang and Lin Xiao. A stochastic composite gradient method with incremental variance reduction. In Advances in Neural Information Processing Systems, pages 9075-9085, 2019.
[39] Junyu Zhang and Lin Xiao. Multilevel composite stochastic optimization via nested variance reduction. SIAM J. Optim., 31(2):1131-1157, 2021.
[40] Xuan Zhang, Necdet Serhat Aybat, and Mert Gurbuzbalaban. Robust accelerated primal-dual methods for computing saddle points. 2021.
[41] Xuan Zhang, Necdet Serhat Aybat, and Mert Gurbuzbalaban. Sapd+: An accelerated stochastic method for nonconvex- concave minimax problems, 2023.
[42] Zhe Zhang and Guanghui Lan. Optimal algorithms for convex nested stochastic composite optimization, 2022.
[43] Renbo Zhao. A primal-dual smoothing framework for max-structured non-convex optimization, 2022.
[44] Dixian Zhu, Gang Li, Bokun Wang, Xiaodong Wu, and Tianbao Yang. When AUC meets DRO: Optimizing partial AUC for deep learning with non-convex convergence guarantee. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 27548-27573 PMLR, 17-23 Jul 2022.
[45] Dixian Zhu, Bokun Wang. Zhi Chen, Yaxing Wang, Milan Sonka, Xiaodong Wu, and Tianbao Yang. Provable multi-instance deep auc maximization with stochastic pooling. In International Conference Machine Learning. PMLR, 2023.
[46] Landi Zhu, Mert Gürbüüzallbaa,, and Andrzej Ruszczyáski. Distributionally robust learning with weakly convex losses: Convergence rates and saite- guarantees, 2023.
13

---

A Proofs of Theorem and Theorem 4.7
In this section, provide the detailed proofs for Theorem and Theorem 4.7 We first give basic property for weakly-convex functions.
Proposition A.1 (Proposition 2.1 in 77). Suppose function semicontinuous. Then g is p-weakly-convex if and only if
R
-
I U {oo} is lower-
g(y) 2 g(z) + (u, 2) holds for all vectors v E 0g(x)) and x, E Rd.
2 y x|1
P
(10)
2
A.1 Proof of Theorem 4.6
Note that the proof of Lemma 4.5 also implies the following squared-norm error bound,
B1T
4Ta²
16n
C2. M2M²1
||a.411 - (((++)))l
s (1
++1
|lu,o g: ((wo)]l?
2n
B2
BfT
Proof of Theorem 4.6
Define W. = ::::=proxxpp: (()x)))(W.)).
For a given E S, we have
(w:))) - f((ue)
(0)
(f.())))) (g:(wr) - (i,a))
Pf
(lg:(wr)) ui,ell
2
Of ( (g:(Wr)) m1,1) - Ps (w)e) g:((w))l ps ([()) elle
0f((un.)) (gi(w))
((a - ur,e) - ps P,O we well2 -
- ur,ell
- 0. (ur.)) (:(w.) - ui,t + Oy: (w:) Tw.TT(wr -w.) Pg liv will?
-p -w,112 1-lllll un,el?
(f((1),))
(((().))((((())) (wi) - u4,)) + ( (g:(w:)) [(w; -w)
wi) wi)- -Po + P, -wll?
- -plll (w:)) w
where (a) follows from the PJ -e-eek--oovvexi of fr. (b) follows from that f((-) is non-decreasing and the weak convexity of gi, (c) is due to 0 < (fr, < Cy. Then it follows
(s((u)))) (0. (ww. (w. w.) SES
P + p,0)))1 - (ill(()))))) f((u,e) - -f((u)))() -w,)) +(P0
n
+ prl)))(w:) u..ll
(11)
Now we consider the change the Moreau envelope:
(o(F1//(w(4)) E, min F(w) + ww w [2]
< E, ((w))) + P w w
2
= -((w)) + E,
2
||,, - (w, - n7,))
(12)
1 p2p
s F(w)) +
2 | well2 + PI, (n( W., G.)l +
-w,) pn(w. W. H. (.)) 17ppM²
14

---

where
E/G.
Σ dg. w. (.))ff(uz..) iES
and the second inequality uses the bound B|||;; which follows from the Lipschitz continuity and bounded variance assumptions and is denoted by M.
Combining inequality 29 and 30 yields
E2 (F11((W
I Fi/)(we)+ + pPMM
+ pn
Σ
f((a(ww))- - fi(use)
2
n
iE
PgCs
-Ofi(ura) (gi(wi)
(((((W))((((())))) - Ui,r) +
.f. w p wi.1l?
2
(13)
=Fipa(we) + p²pM?
pM
2 +
Fi(wi)) - F.(w))+ fi(a((w))) fe(une)
n
iES
(ff()))))) (g:(w.) (g:( us,e) + (PgCs
+ -,.C,))l will + P psllsi(we)) wasel?
2
Due to the pr-weak convexity of Fi(w), we have (ø- pp)-strong convexity of w + Fi(w) -
2 "ll - w/? Then it follows
(((w)) (w.))) Fi(WW)) [e -walll
Fi(we) + _'lm: -well?
p
|l,, -wel
PF 2
p) |w well
(14)
Plugging incquality
32 into incquality yields
R2 [F(Fi/p( < T (F(1//(w.)) + 1?2p?
pM
PPF
--)l ?)] ww,1?
2
2
iES
+ f.la((w))) - -0f((u,))) ( (g.(we) - u..))
(15)
+ + PoCI + +,,Og)l - well + p5ppp1l1 prll:((ww))) - uss.el?
Set p= = pr + PgC + 2p, C2. We have
1PpM2
B Be(Fi/o(We+a)) S F1/p(w.)
+
Σ
-lw well + [((a)(w))) - Se(s),)
2
n
2
iES
Of((u)))) (g((()) us,e) + pppl9 - ur.1133]
I Fi))(we)+ + nPPM²
17
2 [VF;; pM Σ
2
iES
-fi(uus)) (oass))T((ee (gi(w.) us.e) + (ll)) u
where inequality (a) follows from Lemma 3.2
Using the Lipschitz continuity of Ss. we have
E, < (w.) + pMp
+ P1 Σ
2C 2Cyllo:(w)) u.aell
2
ie
pM Σ (r.) u.
T1
15

---

By Lemma 4.5
the enror bound of the MSVR update gives
E
|uie (:(W))ll
(1-1))
uu.o g:oll Rr.
71
iES
| - 9:(Ws))l?
3 (1 - 11)²
llus,0 - se(wo)l? R2,
n iES
71
iES
where
B
202/20
Mn
4TO²
16m (6n2C2M2r)
1
Ri
R2
2n
B
B/r1/2
B2
B¹T
Then
+ 1PPM²
E BIF2/p
S (w/
[||| V /
2
+ 20m
(1 11= Σ
(la:(wo) - -u,oll + Ri
(16)
iES
+ Cpypn
(1- 119:(w (wo) - 21,011 + R2
XS
Taking summation from 0 yields (wF))
T
(wo) +
7
E
V F1/pp (w.)l]]
2
2
0
+ 20
Σ
u)²
(9:(wo) - us,oll RIT
1=0
iES
(1 (1- 11)² 1
Cpppp
11g: ur.0l1 + R&T
Ti
(a)
Pi/p(wo)
?PPMT +
7
T-1
Σ
E
2
2
1=
20
PsP9
1195 (Wo) -1,ool 2C R
(l:(wo)
u1,0ll2 2p Rp
np
iES
(17)
where (a) uses E1- 5 1
Lower bounding the left-hand-side by minw F(w), we obtain
E E
(
T
t=0
2
P2PMT
20;pm
min
[g:((w)) unoll + 2C
1/T
2 n
Pspp
Σ (lar(wo) u..o1? + PPT
+
iES
$
2A
+ npM² + 4C,0 Σ (la:(wo) uroll + 40, +
2p1p uIn
Σ
(9.(()) - u.oll + 2 pR
1/T'
uI'
iES
iES
C
1
' C(n Ri + R2)
+
where we assume Fi/pl (Wo, So, s6) minw.s.s F(W,8, 5²) < A and
C max(8A, 12pM2 16C'p
[19:(wo) unoll: Sp18
(lg:(wo) 16C,p
iES
16

---

Thus
B
B
V
Fi
//:
7 1=0
C
2n
2-2/20
Mn
4To²
16n²C2M3np
+
C(n +
+
B1
B1T2/2
B2
BiT
|
1
1
11/20
nm
TO²
n²²1²
o
+ (1
!|
B1T
1²2²
B/2
B2
B
Setting
BBIBBPe
T = O(Bee),
9=
n
To reach e-stationary point, we need
T=
B,B,2 6
A.2 Proof of Theorem 4.7
A formal statement in given below.
Theorem A.2. Under Assumption
4.3
with
71
ming- B,B2(1-n)) + +1 11). 72
B1(1-12)
(1
T2).
TI
O
B3
B
Jed
T2 O(
O
min
B n.
/4 n2 m.
1/4
n.
172
B, B2 11
e
and P pr 4p, + Cycc + C,Cyhh
Algorithm
converges to an c-stationary point of the Moreau envelope Fi/D in = iterations.
O max
mana B.
B
B
174
B
172 mg
3C70302 By +
3090 3C90.C2 B, C%++0 so that E/] <
We first define constant 2 2 max
By +
we need the 2 and ||e,,,el| < 2 for all E S1,J E S2 and t. Then to prove Theorem A.2 following Lemmas.
Lemma A.3. Consider MSVR update for v. Assume hig (w: E) is Cn--ipshitz all (i,j) S1 x S2 -,, + +1- and t I 2. we have
and E|||Ge|| & M With 71 Bi B.(-nn)
E
|| (we((W
iES;
JESa
B, B2TI
1
||o hh. 1/ 0 /
Anin2Ch
1+1
+
2nini
Th
T12
BiB
iEs,
jES2
E
|1
VES:
JES2
B, B2 (2(++))
4
16mfn3C3.M22p
<
(1
11 - his (wo))1
+
2n1n12
71
112
B3
B3
EE
jes.
17

---

Lemma A.4. Consider MSVR update for u. Assume gi(-) is Cg Lipshitz for all
St. With
By m2)
(1 T2) and T2 S 1o we have
72
|uiut11
Σ g((
111 VESI
1/2
JES2
T2
1 E E((rooo))
2T2 σ B²
Cen 1/2 1/ TI
C2nl n2 n B2
3/2 1/2
(1
14,00
+
2m1
T1
iES1
TO2
jES2
B n2
1/2 1/2
12
B 3/2
2 1/2
where C2 is constant defined in the proof.
Proof of Theorem A.2
Consider the change in the Moreau envelope:
Ex F 1/p W
(w+1)
R, min F F(w) w
w 112
s E, ((w)) + p
We we+1ll3 113
2
=F(w)) + E,
6 Glli - (w, - n,1
(18)
xPpM2
F(w.)) + (1 will?) + (n We, G.)] +
2
Fa/p(w.) + -Peelr/Wer w., G.)) nPPM²
Note that
m1
1
n2
E,
[G.]
V Tii (w: (g.))g)( Øs (u,,),
n1
17
and the second inequality uses the bound R[[ which follows from the Lipschitz continuity and bounded variance assumptions and is denoted by M.
18

---

Define W. = prox (We). (We)) For given E [l....,m}
m), we have
Lil
1
Σ 9i (((hs(WW)))
Σ
Ji(uez)
R
12
n1
SES
jES2
VES:
(a)
0f: (ULL))
Σ
gi(ha (we)))(W)))))) -1,,))
PS
1 Σ
1
gi(hs,(Wi)) ui,e 11?
11
122
111 iES.
2
1v2
iES1
JESs
jES2
1
af((us)))
T(
Σ
go gi(hi - u,,,))
i
JES²
Pfl
Σ
gi(hin (w:))
Σ
ge gi((ig,))12=
Σ
Psll Σ
gi(1a..)) - ui,e
112
iES1
jES2
jES²
iES
.EE8
af((ur)))
Σ
9: 9:(he, - u;,1)
1 Σ Σ
112
122 jE8z
jES2
iESt
1
Σ
pf
Σ
(i(ia 1i
112
iES1
JES2
(
(fn)))
Σ
gi((1,),e) - u1,
Σ
(g.(v)))))
(ha (Wa)(We) - v.s.t)
122
iES1
JE82
JE
Pg [1hr,((ri) U1l
Σ
2pr 1/ Ui.j.ll?
122 JES2
11
12
iES
jES2
2ps C/ - woll?
pfl
gi - -,,e
71
Y12
it
JES²
(0)
(f(())))
9e (vl - ditt
111
112
IES
JES2
( T (g.(o)s.) (ooisss)(hhss,, (Wr.)((rr) - v1...))
112
iES1
jES²
A1
1
Σ
Σ
CgCs [ -issell
Σ
2p Cpr (gllh, veaj.el
11
112
n1 iES,
n2
IES1
JES2
JESz
C2
well
P$l
g. uu,
us 2
n11
122
jESs
1
2
Ofi(ui.))
T
Miçt
n2
SES
JES2
(ff((un)) 0g. (visi)) ( (bii, ((b.)((we))
v(s..)
112
iES
jES2
A + (pCC))llh, - vi.siel2
Σ
C2pr 9
112
iES
JES.
C2pr + Po C,C,Ch) well
Σ SES
psll
Σ
(v - ui,ell
n1
n22
jES2
(19)
where (a) follows from the convexity of ft. (b) uses the assumption that fe(-) is non-decreasing and is weak convex. (c) is due to 0 S (4.)) S Cy.
19

---

The L₁ smsothhtssssss assumption of hr (w) (or
of has (w), then only the second
inequality holds) for all implies
La
h (w.) S (w.)(W))))))))) + Vhi,g (w.) - we) +
|w,
-.ll?
2
(20)
L
(we) 2 (we) + (hs,((W)) (ive)((ss) (W: - -we)
|wve well?.
2
We first assume that gi(-) is non-increasing. Since @fi(ui,)) 2 0 and 0g. I O, we bound A as following
A = =f((u))))' g: (vVisa))
(hass (hr Uigja)
(a) (0f((u).)) " (Usie))))) (he,(w.) - Vr.s.e) = (hh (we)(we) "w:, we)
+ + (g1(0).))) || 1|ve w La
-C,Cgllbas(w.)) - veslell + (u,,)) T (g((v).se) (Vo (w:: - w.) C,CyLh
(21)
where inequality (a) follows from the first inequality in (00). (b) follows from the Lipschitz continuity
and monotone assumptions on fú. 9i. hg.j. On the other hand, if we assume g:(-) is non-decreasing,
we may use the second inequality in (20) and obtain the same result as (T). Now plugging the new
formulation of A₁ back to inequality 19 yields
Σ
ge (w:)))
fi(uit)
112
S1
JES2
SE
1
as(())))
Σ
Σ 1
Σ
(C/Cgllussw)) v.s.al
R1
n22
n1
12
iES,
JES2
sES,
JESz
+
1
Σ
Σ
(f((u),)) (ou(trss)) (Ve
(ha,(w,) (w. - -w))
CjCOLh
Iw -w,l"
2
VES)
JES²
1
C2 + P 11.;
n2
VES
JES.
1
C2 + Pg C | w.ll
(((U1.3))
Pf
11
12/
iE
JES2
2 Σ c/ 1 Σ
(.(.s..e)) - Uitt
Σ
(CCC
ve.j.ll
T1 JES1
122
JES2
IES:
JES,
Σ 1 Σ
+ Ge), w: - Wi)
C2pr
9 + Pg (we) 1i.
T11
112
SEST
JES2
C2 + CyC + CjCgLh
||
well
1
ΣΦs
ps
1
Σ
(.(o))))) us.0
2
ni VES1
n22
jESz
It follows
(B.[Ga], Wr -w))
1
Σ f( 112
Σ (h.))(W))))
1 Σ
filun)) +
1 Σc,
1 Σ
ge(us.)e) - 24,1
11
71 VES.
n1 iES.
122
ies.
JESz
jESz
C,Cgllhes(we) - Vi.g.ell -W
Σ n2 JES.
C2p1 g
+ Po (r)lilsssss - me.j,el
m1
12
iES,
JES2
ies.
CjCgLn ||(. w. 1
g. (vr.5,))) -ui. 12
+ C2p, + +.,cppcCCC C.Ck
Σ Ps
Σ
2
iES
JES
(22)
20

---

Combining inequality 22 and 18 yields BelFi/p(We+1))
s (w.) TppM1
+ m
1
Σ
(x(hsss(e))) fe(ur,e)
n2
112
1E9,
jES,
+C²
1
9e((),,1) - us.0
+
Σ
C,Cylhbs - o.siell
122
122
jES2
JE82
1
C2p + Pg (g)csl)))(w)))
mijiel?
12
JES2
+ C2 + CyC + C)CoLm)) )l wwel² + +P
1 Σ
(:((5)))) u4,0 17}
n22
,E82
PpM
+ Pm 1
fi( f(( - Σ ((((),)))
S (ii/ +
Fi(w)) Fi(w.) + Fi(we)
2
n2 jES2
RES1
+ fil 122 jES2
1
gi(Ui,je)) fi(uu,t) + +CG
1
Σ gi((...))) wie1
n22
jES2
+
1 Σ
(,C,llhsss..) -i.iell +
Σ
(2p O2 + Po PoCy))llsswwe) - villel??
112 JES²
Y12
JES²
+ C2ps + PoCyCR + CjCOLi
)l/
well? + PP
1
Σ
gi((is,e) miel
171
2
712
jES²
(0)
S Fw/)(wi) + rpMM
+ pn Σ
F((w)) - F((w:) + +20,
Σ
gi(Uisse) 24,1
2
iESt
JESs
+
Σ
20 C0yCgllhss - risiell
+
1
Σ
C2p + Pg
112 JES2
112
jE82
+ C2 + C2 C )[ well + ps 112
1
Σ
jeS²
where (a) follows from the Lipschitz continuity of fú, 9t. hig.
Due to the pe-weak convexity of Fi(w), have (p pr)-strong convexity of w +> Fi(w)
fll w| Then it follows
F...)) F.(w:) = (:(w)) + Ø W: w.ll3
P((w.) + f.... - - I|w, - -wel?
0
2
2
< OF
p)][ W: well
2
(23)
21

---

Plugging inequality 23 back into A.2
we obtain
E, (We/p(We+1))
F1/o(we)+ + T²M
PF D)][ w.ll2 =2,
1 Σ gi(uisit) ui.e
p1
11
122
jE8z
1 Σ
Σ
Co,Collh,, -Vsjeell
+
(2p 9 + tpCC))llie vt.
1/2 jE82
112
JESs
C,CoThn
gi((i,j.)) - -us.s |
+ C2p) + PoC,Ch+ +
ylie - well2 + Ps]
Σ
2
jESz
(
Pw/p(wi) + TPD22
1
Σ
2 l|,, well? + ci
Σ gu(uasse)) - Wist
+ ld
2
12
112
iES1
JES2
Σ
(illhs(wi)) - (w))
+ Cillbs,(we) - =1,,111
112 JE82
jES2
+ C1
1
Σ
Uiee 17}
122
jES
(b)
Fi/p(We)
+ pPp
[Fi/ + Cipa
Σ
1
Σ ge(Us - 21.1
2
2
112
iES:
jESz
Cipp
Σ
([e,((w.) - Visgell + C1pm
([h,)(w.) Di.j,el?
iESi
JES2
IES1
JE82
2
+ C1p
Σ
9.((%,5,)) Uit
112
#ES1
JES2
where in inequality (a)
p = OF 4p + c,, + CjCgLn and C1
max(20, 20,, C2py + pgC ps}. and equality (b) uses Lemma 3.2
With general error bounds
Ellbee - vi.g S S(1 (1-11 -1))
[[w](wo) - vi + Rı,
122
71
122
IES
JES2
EES
JES²
1
Bllkk (wi) - 21. 2 I (1 - v1)²
||/ (wo)
-v1,,012 + R2:
112
iES
jES²
iES:
jES²
S (1 n22 1
E
9e (vV...)))
u4.0
+ Rs:
1122
n22
JES2
iEs
JES2
2
Σ
Σ
(VV.).)) - 44
$ (1 - -22
Σ
g. -4,.0
+ Rg
712
FEST
JES,
YES
jES²
we have
E
E(Fi/p
+
11 pM
"
E
VF 1/ (w:)
+ Cipn(11 mmin)"
Σ
1
Σ
ga(Vi.5,0) 44.0
2
2
11
12 jESz
iES,
1
|
1 Σ
g.((%
u4.0
(ho)(wo) -i.,ooo
71 iES
712
n2
112
jES,
iest
JE
(ha.5(Wo) 0n3,012
+ C1 Rı + R2 + Rs + Rd),
12
IES
JES2
where Jmnin = min
22

---

Taking summation from t 0 to T yields ([T]]
(Wo) TTTMTT T-1
T-1
B|ll /
Capn
Mmin) Moo
+ +TCipn((B) + R2 + Ra Ra)
([Fi//(Woo) TPMM2 11 T
CipnAo TCipp((R + R2 + Rs RA)
/ (wo)ll
Pmin
where we use ΣT-1 (1 - *mmsn* $ Mmin
and define constant Au such that
1
2
g:(Ve.j.)) 44,0
go
(i,0
11
722
11
12
iES
jES2
iES
jES2
Σ
(wo) - -1.00l
+
1
Σ
S S... [wo)(wo) vi.iol??
11
112
711
112
iES,
JES2
:ES1
jESz
Then it follows
T-1
/ (w:)
T
2
TPPMaT
Ciin + (CPpT + R2 + Rs + R4)
Fa/z(wo)
T
2
Pmmn
2A
2C1pAo
?pM?
201p(( R2 + R2 Ra)
TT
Mmin
01 -
1
+ n R1 + R2 + Rs + R4)
'TT
Hemin
where define constant A such that Fi,p( ( Wo, Su. $)) - (FlFi//(Wrr ST, st) < A.
With MSVR updates for Us.ia and ur,t, following from Lemma A.3 and Lemma A.4
we have
B BTT
Bi72 2n1
27 o
111 2n1n2
112
Rí
B1
B B2
R₂ = 4TI0²
2T 1/2 0
C2n 1/2 2 B2
C2n
3/22 1/2
112
Rs
Bs
B² 12
B n2 T2
1/2 1/2
B1 3/2 1/2 1/2
B T2
R4 = 4TZ0²
B2n
Cininen²
B2
Bin2T2
B2
Then
B[[[ F1 (w:)l1
1=0
0
1
(
1
+
1
) b
T1
+
+
T2
+
T2
T
n
Umin
B1S
B3
B
1/
B2
n2n2n²
n1
1/2
B
1/2
TI
n
3/2 1/2
12 n
n1 B2T?
ninz??
ByT1
1/2
B
B3T
B
12
122
1/2
T2
1/2
11/221111
B1
B2
0
_
1
1
1/2
T2
1/2
71
1/2
1/2BB
1/2
T1
3/2 1/2 11. 122 n B 12/22212
7
Jmmn
B1/2
B
B B2T
1/2
1/2 1/2 B
T2
23

---

Algorithm 3 Stochastic Optimization algorithm for Non-smooth FCCO with coordinate moving average
1: Initialization: Wo, {u, E S}.
2: for = O..... T 1 do
3: Draw sample batches Bi ~ S. and B2,, ~ D; for each E Bi.
(1 T) e + (w,; 2,,) i E Bi
4: 01,+1
Ui,t i E Bi
5: Compute Gt 1 Eies 0g. (w;: B (ur(a)))
6: Update Wx+1 Wt n/
7: end for
8: return wi with uniformly sampled E {0, 1}.
Setting
B ///3n
0
min B3:
}ct
O(B2ct)
1/2
17 = 0
min
B1
1/2
2
//
B 11/2
1/2
111722
3/2
1/2
= -0
min
B3
B1/
n1
1/4
R2
1/4
B, B,12
T1
1/2
T02
B1
711
E
then with
1
n1/4
12
1/2
n1
T= 0
max
B
1/4
1/4
B1 12
1/2
B1B²²
n2
we have
T
B
E
F
(w,) S
T
t=0
B Solving Non-smooth FCCO and TCCO with Coordinate Moving Average
In this section we consider solving non-smooth weakly-convex FCCO and TCCO without variance reduction method. To be specific, we use coordinate moving average updates for function values estimations instead of MSVR. This allows us weaken the assumption on the Lipschitz continuity, iee the Lipschitz continuity of the stochastic function value estimation is not required, and can be replaced by the Lipschitz continuity of the function value. Moreover, compared with MSVR, coordinate moving average update does not need the stochastic evaluation from the previous iteration, and thus has a simpler implementation. However, as a result of not using variance reduction technique, the algorithms suffer from worse convergence rates in terms of E.
B.1 Solving Non-smooth FCCO with Coordinate Moving Average
We first assume the followings assumptions hold. Assumption B.1. For E S, we assume that
fa(-) is weekeylyy-, Cy-Lipschitz continuous and non-decreasing:
(.)-) is Pg we-wakly-coonvx and C2- -Liischhit continuous;
Stochastic gradient estimators 9, (w; {) and (w:(w:)) have bounded variance o².
With coordinate moving average update, present the following lemma of error bound.

---

Lemma B.2. Consider the coordinate moving average update for {ut, : i E S1} in Algorithu
assume gi (:(w) Cg Liiiscchitz continuous for all i S and r - 1, then we have
BIT 2+ ) |uu,o - Di (wo)ll 2/ 1/2
4 4v2n Cg
Bllluct+1 - gi (W++)]ll (1
4m1
B2
B17
Bllluc+11 - 9: ge(we+))l1
BIT
(ar)20t1)) 200 |uua - 9:(w))]
8TO²
32n 32
4n
B2
B
Then we have a convergence analysis similar to Theorem 4.6
Theorem B.3. Consider non- non-smooth weakly-convex FCCO problem, under Assumption B. setting = O(2et) S 1, 1] O B, B2 e),, Algorithm 3 converges to e-stationary point of the Moreau envelope Fi/p T 0 B. D2
8) iterations.
Proof of Theorem B.3
Since the only difference between SONX and Algorithm 3 is the update for {un } the proof of Theorem 4.6 still holds with the error bound replaced by Lemma B.2
i.e,
(1- 1
E
11,441 9: (W
||u., g:(wo)ll + R1.
EE
1
E
|1,,++1 gw(w++1)12?
S (11 -2) p1)
1u4,0 gi(wo)l2 + R2,
iES
ES
BIT
1/22
4v2n WV2nCCMM
STO² 32n
R1
Rg
+
4n1
B1T
B2
B2T
Then proof proceeds to
| (w.))1)
5
1 1
+ -) + Rτ + R2
T
1 ( +
n1 + 1)
11/20 12
n1 TO2
+ nîn
=0
+
T n
B17
B1T
B2 BiT2
Setting
B B2
T = O(Ze") )
1) = 01
111
then to reach a nearly c-stationary point, Algorithm nnedd
T = O
71
B1
iterations.
B.2 Solving Non-smooth TCCO with Coordinate Moving Average
We first assume the following assumptions hold.
Assumption B.4. For all (i,j) E S₁ x S2, we assume that
f((+) is weakllyy-coonee C Lipschitz continuous and non-decreasing:
gc(-) is p weakllyy-conve and -ppshitt continuous. h..(.)) is differentiable and Cip-hisschhiz continuous.
Either gi is monotone and ht, Ln -mooth, or gi non-decreasing and hi (+) Ln-weakly- convex.
Stochastic estimators (w,(w,E), Ohi (w, and gi (vi.) have bounded variance o², and [[b])(W)]] & Ön.
With coordinate moving average update, we present the following lemmas of error bounds.
25

---

Algorithm 4 Stochastic Optimization algorithm for Non-smooth TCCO with coordinate moving average
1: Initialization: Wo. {uno E Si vijjo hi B3,, for all (i,j) E Si x S2.
2: for O...., T
do
3: Sample batches Bi S1, B3 S2, and B Diy fori Bi and j e B2
(1 TI ).,5, + Tiha,((We: B,is) (t,5) E Bi x B
4: 0i5
Uiiitt (i,5) & Bi x B2
(1 (1- (1-T2)us +
B2 Σ JiB (2. i Bi
1
5: 04,+1
Wi,tr i Bi
6: G pi DieRy [( B2 EieB, Vhi Vha,(w;;; Ba (w, (gg(()))))) (f(()))))
7: Update Wi+1 We 1/Gr
8: end for
9: return Wy with uniformly sampled é E (0,T-1)
Lemma B.5. Consider the coordinate moving average update for {uyga (i,j) E S₁ x S2} in
Algorithm assume hi.g (w) is Ci-lipschitz continuous for all (i,j) E S1 x S2 and T S then we
have
E
||0,j,441 - he.(
11
iESi JES,
B₁ T2 y+2
2/2n
|1
ha.((w))l+
4n1n2
n1 jES
B
B1B2T1
E
|1ajett1 - hig (w W1+
12
JESIJES
B B2BTT 2((+1)
8TIO²
32n
< (1
Σ
Σ
||:i,0 (wo))))) +
4n1
71
B3
B BBB3T
SESI
JES2
Lemma B.6. Consider the coordinate moving average update for {un i E S1} in Algorithu
assume g-(-) is Lipscchcit continuous for all e S₁ and T2 S 1, then we have
E
|1,111
1
Σ
gi (v(
71
112
1ES1
jES2
(1
Bi
1+1
||u6,0
Σ
+
2V2 1/2 a B² 12
4v2C,, Mn
M 1/2
B
4m1
YES.
n2
JES2
B 1/2 1/2
11.2 T2
1
|14,411
ge (1
711
n2
iES1
jES
< (1
B1
2(++1)
|u0,0
Σ
g.(ors,0)l2
8TZO²
B₂ +
4r1
112
B1
IEST
JES,
Then we have a convergence analysis similar to Theorem A.2
Theorem B.7. Consider non-smooth weakly-convex
TCCO problem, under Assumption B.4
/2 1/1B//1
1)
setting TI = o min Bge
Bze
S S11 = O(B2E*) S
1,
min Bged, B 1/ B;
6
B1 2 [nins
Algorithm 4 converges to an e-stationary point of the
Moreau envelope Fiyp =0 max
R1 B3 Br
iterations.
B3
B 1/2
26

---

Proof of Theorem B.7 Since the only difference between SONT and Algorithm is the update for {uL. E and ( (i.j) Si )2). the proof of Theorem A.2 still holds with the error bound replaced by Lemma B.5 and Lemma B.6 i.e.,
Blllkn (w.)) mas.ell S (1 141
Σ
Σ
[[os)(Wo) -Va..oll R1:
n1
iESi jES2
iES; JES2
Blll/, (w.) Va.j,el1
I (1 - (1)
[14,s(Wo) - vi.,0012 + R2,
11
S JESp
iESi JES2
1
E
g. (va...)) 44
S (1 p2)
(o(1),))) 44,0
+ Rss-
n1
T22
nt
12
iES1
JE82
iES
.1882
E
(((.).)))) - Ui,t
5 (12)
9: (:(()ii)) -4,00
+ R4
11
112
n2+
112
IES,
JESr
YES
JES²
with
B2T
B1T2
R1 2/271/2 2/2
4v2n
M1
422
1/2
4n1
B²
B2
8
32n
2V2T22 1/2
4V2C, M B/
R2 =
Rg R3= =
+
B3
BTT
B B1/2
1/2 1/2 1/2T2 /
8T20²
32C² M2 BeT?
R4
B2
BinuT
Then the proof proceeds to
T-1
V 1/2 (w:))
0
+
+ 4 Rí + R2 + R3 + Rd
Jminn
1
1
1
7
1/2
0²
T2 o
1/2
T
n2
n2n2n?
+
+
1
+
+
11
Umin
B1
B3
B2
B1
B3
1/2
B
TI
11
B2T
+
B 1/2 1/2
BiTu2T2
122
1 - +
1/2
T2
11
n1 1/2 B//2
+
+
T 11
pmin
B 1222
B
1/2
Bi B271
B1 1/2 1/2
112
Setting
B 1/2 1/2
1):
T1 = 0
min
Bge
n2
B
72 O(Bee),
1/2 B 1/2 11.
11 0
min
Bge* 4
B 12 1/2
122
B
B1 B2 22) 111122
1/2 B n1
then to reach nearly e-stationary point, Algorithm 4 need
n 1/2
T =
max
B3
B
1/2
1/2 1/2
B₁
n1
e 10
n2
iterations.
27

---

C Details for TPAUC Maximization
C.1 Assumption Verification
We first present two lemmas about the weak convexity of the objective in the regular learning setting and in the multi-instance learning setting with mean pooling.
Lemma C.1. Consider the formulation in problem ② in the regular learning setting and assume that function {() is non-decreasing, Ct Lipschitz continuous and pr-weakly-convex and function hww (x)) ) is C₁ Lipschitz continuous and Pt. co-eeakyy-coovex. then the following statements are true:
filg, s') is convex and Cy-Lipschitz continuous w.r.t. s'), and non-decreasing w.r.t. 9-
vi(w,ss) is Do-weakly-convex w.E.t. (i, and the stochastic estimator of the finite sum function value v'(Ww, s;) -ipLipschitz continuous w.r.t. (w, 8:).
1. 12 Eies, f((Vi(W,8)) 8)), 8') is op-weally-convex w.r.t (w,s.8).
Lemma C.2. Consider the formulation in problem (9) in the multi-instance learning setting with mean pooling, and assume that function h;(w) X.. Exex, e(We; x) We is La-smooth and is bounded by Ön and he(w; <) = e(we: E) o², l is non-decreasing and Ly-weakly-conve, then the followings are true:
T We is Ct- Chiischhit continuous and has bounded variance
[i(g, 8') convex and Cy-lippshhite-coniimon w.r.f. (g,8"), and non-decreasing w.r.t. gi
gi(v, 82) 8; + (E(v)=as)+
g is Pg-weakly convex and non-decreasing w.E. U, convex W.E.I. St, and Cg Cy-Liphchitz continuous w.r.t. (v,st):
hig(w) (w) h.(w) is La Ln- and hi,j(;;; is C₁ -ipischct continu- ous;
14 Exes, filg,(h,, si), is pr-weakfy-comer w.ntt (w,s,s').
C.1.1 Proof of Lemma
Proof of Lemma C.7 The convexity of Selg, with respect to (g. 8') follows from the convexity
definition. With subgradients 0,, fi(g, 8') E 2. 0,Si(g, s') E [0, 2.. we can see that felg, 8') -Lipschitz continuous w.r.t. (g, s"), and non-decreasing w.r.t. u.
We first show that (X)) - hw (X:)) is weakly-convex w.r.t. w. (X,((X,) - hww (X+))
2 E(1ww(X) (X,) - Now (X:) + (00( (0o00//x(003 (X,) - Aw (X.)), (X;) - Nww (X:)) (lo (X₃) - lo (ow((X (X:)))
+ PE (1hm - hw (X:)) (li (X,) hw (X.))1?
2
(a)
2 ((hw (X,) - hww (X.)) (0E(h (X,) Aw (X.)), (Vhw (hw( w- w))
+ 22 || 2|
where (a) uses the weak-convexity of Aw (X.) and hw hw (X,);
hww hx,) Nw (X,) V No (X,), W w)
Ph | w
2
(xx) Aw (X,) (V/
w)
Ph
w w||
2
Thus E(hw (X₂) hw (X.)) is 4. w.r.t. W.
28

---

By convexity of (f) + 8i + " we have
di (w, 82)
(W, 8;) + (de%) 8:), E(h (X₂) hw (w,)) ((hww(Ww))) hww (x.))) + (dss Vi 8:). -8.)
(o)
2 vi(w, 8:) + Oets w, 86) 0e (e(h)w())) - Nww (X:) (X;) Vlw (Xi)( w)) - -pr -wl?
+ (O., 2/ (w.s:), - 8;)
(6)
2 (w, s;) + Oe w, (l) (w (X₃) - hw (X:) Vhw w))
2pr
+ (O., U/ (w, 8;), 8; s.)
1| w|l
B
where (a) follows from the monotonicity of v/ w.r.. l and weak-convexity of ((h (X2) (o((((())) (Xi)). and (b) is due the Lipschitz continuity of (f, + 8, + (t-a.)+ w.r.t. l. Thus is 4peC3 -weakly- convex w.r.t. (w, s;).
With a similar argument using the convexity and Lipschitz continuity of Silg, 8') w.r.t. (g,8") and the weak-convexity of (w),,, we can show that (w,))(w,)),) is 4pr 3 weakly-convex w.r.t.
(w, 86, s'). Thus, F(w, 84, is PF 4p:Ch 4pxCi weaklyeyy---oee w.r.t. (w,,
Now we show the Lipschitz continuity of (w,, X2). i.e. unbiased stochastic estimator of a/, (w, s:). We have
N w, 81; Xx) 2/ (W, 5x:
(((hw(Xy)) - hw (Xi)) -Bi) -33, + (X)) - hw (Xi)) 8c)+
(s. +
B
(e(hw(X)) 1ow (Xi)) - si)+ (((ha(()))
1ew
1ow (Xi)) 3z)+
S 2/|8; -8,11 2,12+22
13
B
s 2||s; 3.122
2
180 C21 [ w- -:|l2 +|12+22113, ssl13)
32
s (2+ + + 160
)ll
w w| + ||: =3:133.
B2
Thus 1/ 81; X,) (2 +
4+ 160772
1/2 1 Lipschitz continuous w.r.t. (w, 8;).
/²
C.1.2 Proof of Lemma C.2
Proof of Lemma C.2 First of all, the convexity of Se(u, s') w.r.t. (u, and the convexity of ge(Bg, 8;) w.r.t. (t, se) directly follows from the convexity definition. Moreover,
from the formulation that Oy felg s') [1 - 11, Oufilg, s') E [o, 2 (egn( E 4. 1], ( st) E [0, 11. Thus f. is Cy a L-Lisschitz continuous w.r.t. (u, and non-decreasing w.r.t u, Di 1 L-Lisschitz continuous w.r.t. (c) and non-decreasing w.r.t. l. Since {(-) is non- decreasing, gi(0ig, 8;) is non-decreasing w.r.t. Viy- As result of Proposition 4.2 gi (1 s;) is Pg weeeelllyyyconee w.r.t. Viy. Due to the composition structure and the Lipschitz continuity of gi and l, can see that gi (viy, st) is C, C--Lissciitz continuous w.r.t. (Vig, 8:).
The LA. 2Î, wla--wakly-convenn of hw.((w) and C₁ 2 continuity of (w: &, E)C) directly follows from the smooohthssss of (w) and C₁ Lipschitt continuity of h h,(w; Finally,
29

---

we show the ceakly-convexity of (w).
(W)) (0)
Migga 81), + Ji 8' 8))
@0 ()) (i (he,s (w) sc))
+ (w)
-s)
+
(w)) - Elbss (w))3)
+ (w),
5: -si)
& (M): (
(:). ()
his (w))
C.CgLe |1 (w) b. (1)
(w), gilhis (w), ())))))s si)
felgi(ha (w), (
(O.filgi(han) ())
(w)) w) w) CjC,BRLL CjCoLin )| )|
(O.Ji (w), 8.), 8 8'),
82),
w|1
where (a) uses the convexity of fi (b) uses the monotonicity of f. w.r.t. and convexity of gi (c. s;) w.r.t. (l, 81). (c) uses monotonicity fa w.r.t. u, monotonicity of 9i w.r.t. and weakece- of f. (d) uses the smoothness of ha.j. Thus (w)) is Ps (C,C,CRLe C,C weakly-conve w.r.t. (w, St, s').. Therefore, 1 2t Eves+ fe(9:(ha,5 (W),((h,(W),.... s;), s') is weakllyy--ooneex (w)
w.t.t s,
C.2 Algorithms for TPAUC and Multi-instance TPAUC Maximization
Algorithm 5 SONX for TPAUC
1: Initialization: Wo. {uio i E S4), fsi. : $4
2: for O,..., T 1 do
3: Sample batches Bi C S4 and B2 S_.
(1 T)ui, + (rpi:wee 81,1; B5) + (w) 81, i B
4: 01,+1
Ui,t:
i Bi
81,1 B.
1.tb,( st,
i Bi
5:
81,1+1
8i,01 i i Bi
6: 8/41
5/ - 17 p. EiEBi 0, f
7: Compute G; Bi Σieg Ou (we, st,t
8: Update Wt+1 W, 1)Gr
9: end for
10: return w, with uniformly sampled from (O...., T -1..
30

---

Algorithm 6 SONT for Multi-instance TPAUC
Initialization: Wo. {uro : S+ (50.0 : E S+h, s/s (Vi.i0 (i,j) E S+ x XS-}
2: for t 0,..., T "...,,''' do
3: Sample batches Bi C St. B3 S_,, and B3 C X, for Bi UB..
a (1 T1 + (w;; B (h we Bg.)) - h,(we-1;; (
i Bi ie B
4: 01,11
H1 [1 Ti Ti) + (w,; /3 72(h, (w BB,)) h,(w.-1; 33,))
0i,t, E Bi and & B3j
(1 - uuu + B2
+ EjEss [ Ui, 86,1)
5:
011+1
+r Ui 81,1) (( U2 8i,-
i e B
i Φ Bi i B & 8
1
1 Eyess Onglvge - viss 8(e) S ma,a):
8i,t
By 7n Bi
6:
8i,+11
8i,t.
7:
6441 s - 1/2 EieBy Su s))
8:
G.
B. Liest Ous Oul(uins)))
L
1 Ejes; (Vh,(w,;; (Bg)) B3,,) 0,g(U;, v..e. C.3 TPAUC in MIL with smoothed-max pooling and attention-based pooling
9:
B2
10:
Update Wx+1 Wt I/Gr
11:
end for
return W, with uniformly sampled from {O...., T 1}.
We can extend our results smoothed-max pooling and attention-based pooling.
Smoothed-max Pooling, The smoothed maxx max pooling can be written as 445
ww (X) = T log
Σ
exp(o(w;x)/T)
(24)
X
XEX
where - >> 0 is a hyperparameter and <(w; x) = e(we: x) T w. is the prediction score for instance x.
We can see that hw X) itself is compositional function. To map the problem into TCCO, we define
h,(w)= = 1 Exex. xxp()(w;x)/T) + C, where > a constant. Then the objective function
[x.
becomes
min
Σ
(w),,
w.s n2+
X:ES
(g s')
where
figg, 5') = 5
(25)
a
8; + (f(T log hogg,,(()))))))))))))))()) - T log (o(()))))))))) 8:)+
(, si) n1_
Σ
3
X,
In this case we define gi (E(v)), = 8; +
-s)+ and ha. (w) = [h;(w), ((w.,, hy (w)]
We can still prove that (((vv),, 8;) is monotone w.r.t each component of v. It not difficult to prove that É(T log V1 log 1i2) weakly convex w.r. v because 7 log #1 T log 02 is smooth mapping of v due > C' and is convex function [8] As result, since (l, s;) is non-decreasing and convex w.r.t to f, it is easy to prove that ( , s;) is weakly convex w.r.t v and is monotone (either non-decreasing or non-increasing) w.r.t to each component of v. Hence, assuming ha (w) is smooth and Lipchitz continuous function, we can prove that gi (i (w), 8;) is weakly convex w.r.t to w.
bated Pooling, iieetioonbassed pooling was recently introduced for deep MIL [1, which aggregates the feature representations using attention, i.e.,
E(w; = Σ exp(g(w;x) x))
XEX EXEX exp(o(w;x')) <(We:))
(26)
31

---

where g(;:x) is a parametric function, e.g., ((::x) w mmmd and w. E II"". Based on the aggregated feature representation, the bag level prediction can be computed by
+ C, where V e
hw (w, (w,X)= = (w. ((w;
(27)
explo(w:x)))
Σ XEX Exex Exexexp(((w;>))
where 6(w;x) = w c(We:
We that hw (X) itself is compositional function. To map the problem into TCCO, we define h (w) = [X. Exex. explg(we x))6 x), and h? (w) = |x.] Σxex, exp(g (p(gg((;')) x')). Assume
[w
S C. then h((w)) 2 exp(C Cb). Then the objective function becomes min Σ (W,) 8'),
w,s' n4 X,ES+
(e( h (w)
where filg, 8') = s' + B s') (w, =
15 (w)
hr(w)
8i)+
8; +
8
X,ES.
(28)
s; (<( 22 --+++
In this case we define ge(E(v).s)) s;)
and (w,((w
[he (w), (w)),, (w), hw))]. We can still prove that (;(()),, is monotone w.r. to each component of v. It is not difficult to prove that {("h - 21 is weakly convex w.r. v because in is smooth mapping of v when 22 04 are lower bounded and é is a convex function [8] As v4
result, since g: s:) is non-decreasing and convex w.r.t to f, it is easy prove that g; (((v), s;) is weakly convex w.r. v and monotone (either non-decreasing or non-increasing) w.r.t to each component of v. Hence, assuming h (w), h (w) smooth and Lipchitz continuous, that g.(h.,, (w), s;) is weakly convex w.r.. to W.
prove
C.4 Convergence Analysis of TPAUC Maximization
C.4.1 Convergence analysis for Algorithm
We first consider TPAUC maximization in the regular learning setting. Define F(w, s.s) == Exes, f(( s)), s'). Due to the weak-convexity of F F(w, the following Moreau envelope and proximal map defined
s,) ((w,,,s' w.r.t (w, s'), consider
Fx( min F(W,S,8)) w,8.8'
(II
w|| +
$|| 1| s'113),
2A
1
prox (w, s, arg min min F(W,3, + (/W w 1 + ||s =|| +
11 s
W
2X
Following the same proof of Lemma 4.5 we have the following error bound
Lemma C.3. Consider the update for {uit X; S+} in Algorithm
5
Assume
(w 8:) is Cy-Lipshitz continuous for all X, E S4 Assume Bell|G,
M and
E.ll Bi Ex,e, (WW,, B,); F st)e:111 M where 64 is the n. dimensional vector
with at the i-th entry and 0 everywhere else, With Re-B, + (1-7) and T S 3/ we have ((((-))
1
E
Σ
||u,0011
2h (,
n4
X:ESI
(1
BiT
141
|uuio (w st,0)ll
1/2
8n GnAM
2m
"
B/222
B/2
X.ES,
Then we have following convergence guarantee.
32

---

Theorem C... Under the assumptions given in Lemma C.1
with
n-
+ (1- ==
Bi(1-T)
O(B2d) n 0 B. ) and p PF + Pv Pg Algorithm
converges to an c-stationary
point of the Moreau envelope F1/2 in T = (( nt
B3, B,B2 1 9) iterations.
Proof of Theorem C.4
Define (W,, 81) = prox=/p St, s(). For given X; 8t, we have
(w S1,1), 8)) f(( st)
2 0, Si ())( x() + a. (. st) (Be(Wvr 81,e) - -U,,t)
(0)
(6)
Oz Silur, s()(8] - s)) + d.fi 8{) 1/ vi,, 81,1) - uie + (Ou we - w.)
Pe || well + (0c, 2/ (We, St,), 85.0 -s.e) - Pv || st.el??
2
2
(c)
2 02 fi ()) - ( + a., (ut,t $ [Wss -uup]] (Oufi(ur,es s,)0 the st,e), we we)
+ +Oaff(uuL, s)),, 1) (w,. s,,)), 8,, si,e) Os (1 w + ||āi, - si 112)
2
where (a) follows from the convexity of S.. (b) follows from the monotonicity of /e(::8) and weak convexity of th,, (c) is due to 0 S 02 (u,, st)) Cy. Then it follows
1
fl ())( x) + (Oufi(us,e sw) st,e), we - we)
n X,ES,
+ (Ou.f (Qufilur,es s)),s, 10000....ww st.)), 81, shse
(29)
falei(We, S.,). (/) filuse: s/)) Ou Sufi(usse (e) s1,1) 21,e]
n X;ES
C 2 (I (lw:: +| - ss,cl())
Now we consider the change in the Moreau envelope:
Eellipp( (We+1, St+1, s(+1)]
=E, min W
F(w, Se. 5t) 2
P. (ll We+all +|| 1
+ +135 s 113)
p (I|W, - we+1ll2 + +111 - -s 11 + 1186 5 113)
< E. F(W;, St, 87) + 2
p
F(W,, $1, () + Eg
(1 [|W:-(w: -ww:- 7] + ||s: - (s: -n!!)1?
+ ||86 - (s) - n33))131
(30)
Ø < F(w,, Se: (6) + 2 (1) w: +|88:
-sel1 + 11 s/(113)
+ -Belyl (w - we, Gt) + ty(8, - S1, G.) + 1886 8/. G?)] + 37
2
-Fi/ St, 1/1 + ple (n(w - we, G.) + 1/ - s, G.) + - - G?
3n PM
2
where for simplicity we denote G = Bi Σx,es; (. x)), (We, Si,r BB) and G. = B, Ex.es fi st). The second inequality in the above derivation uses the bounds of E|||G,| B[||G [P3] and [ which follow from the Lipschitz continuity and bounded variance
33

---

assumptions and are denoted by M. Moreover, we have
E (n/ W., Gt) + my(s, St. G() 7/3 - 5/c G/yl
n(W, W, R, (G,) + s7(s, - S, [,(])) + -n(8/ s/c, E, (G
and
E,GGi] 1
Σ Oufi(ur, st) (we,
Thet X,ES+
E.GG]] E
Ou. Ouff(ui,t, S (1)
n X,ES+
E|G Σ
fx
X.ES+
Combining inequality
29 and 30
yields
Ey(Fi (W.+1, S141, $
3n12pM
(w/ s/))
pn
fil S4,1), fu(ur,,, 8/)
2
nh+
X;ES+
u.et + CopCs -w.l- 1135, ssell?)
- - si) [We,
37ppM²
(31)
PLip(We,S1,56
+
2 + pm(FF(wr, St, 81) F(w,, b()
pM
Σ
f((vi(We,,s,))) s2,1), fi(ui,,, st) aufelue, (b) ue,]]
nt X:ES
PaCss (1/W,- w. + ||ā -
-st.el3))) stell3)
2
Due to the pF-weak convexity of F(w, s, s'), we have (p (P-Pp)-ssie psttong convexity of (w,s, s')
F(W, s, + (.l(w,, St, +/)) (w, s'1l Then it follows
Si Sw,
F F(W St 8)) +
St, 86)) ['((,,,
(We, Se 1
2
F(w,, St. s + 0 2 [Ww,, St, s()) - (w,, St, s/)l
(32)
[1(,,,
(r,, St. 5/) (w,, S1 8/)11
PF
2 ()),(w,, s/) (W.. Sc.
Plugging inequality 32 into inequality 31 yields
E, ppp (W+1, S441, s111)
31²
E Fi (iFipp(w,,s.... st)] +
+ pnl
AF
p)l((wr. St, (We, Si, 8/]1
2
2
im Σ
f( st) Oafelue,, s6 (we, st,e) meyl
(33)
n4 X:ES,
Cs
(I/w, will + 1| ssel13)
2
Set p= = pF + CsC.. We have
34

---

(W 8/41]]
3rpp
p²n
S Fi 86)
[(w,, s/)) (W,, St, 8t]1?
2
2
pm Σ
(We) Sc,e),
fi(ui,s 51) Quii(uie, - wi.e)
X.ES+
(a)
Fi/p(wa Se, s() +
31p
?
(t.
2
2
pd
(L)), 6/) ((),,,,() Ousi (ib 85,e) unee]
X,ES+
where inequality (a) follows from Lemma 3.2 Using the Lipschitz continuity of f, we have
E, ( $(+1,
31/ D=² 1
(w,, St, s/) + < (w,,
(w,, (w., [ 6/)
2
2
(34)
PT)
2C, 81,1) wi,ell
n
X,ES+
With the error bound from Lemma C.3
we have
E
useell
{1 11) n2+ X,ES,
[wo, st.0) 24s,0l1 + R
n4
X,ES+
with /
B,T
R
1/2
1n-GoMn
4n Myn Then B/r
2n,
B1r1/2
E[Fiip(Wetie 8141,
Fi/p(wwa 84, 81, + 3112pM2
E. [ V St, st)11
(35)
+ +C (1- 1)² n4+ X,ES+
I1o s4,0) -u,0ol +
Taking summation from 1. = t
yields
E (WT s/r1
317² 312PM2T
Fi/p(Wo, So 166)
17
V (i (t,, 8/)11
2
n)² 1
+20mpm
Σ (1
|1vx s1.0)
ws,oll RT
1=0
n
XLES_
(36)
(a)
311² PMT
" T-1
(wo So. s6)
Ell VF (WFFi//(W,.55.. St. s
4C
Σ
1
|/ s2.0) - u.ol 2
14
X,E8
where (a) uses ΣT-1 (1 4)
<
1
n
35

---

Lower bounding the left-hand-side by minw.s.e Fi/a(W,s,s') we obtain
BilVF,
St,
T
min F1, 3nd T
P1/p(wo so, S0, s/)
'/
w,a,s'
2
pM
Σ
leo, 81.0) uooo + 52
T4+
X;ES+
24 nT
+ 3mpp²
,0
Σ
11% u,,oll + 4C
pTn+
X,ES+
C. ( + + C(n + R)
$
T 1
where assume F1/p( Wo: So; s/6) minw.s,s Fisp(w,8,8") A and
= max 1 ,320,
Ie/s(wo, - us,oll, 16C, X,ES,
Σ
Plugging the expression μ and R yields
E E F Fi//F///(WW/.. (WL St, $1,11
t=
1 1 +
+
-1/20
n1
0
(
+
T
1)
BiT
B² 1/2
1/2
B: //
Setting O(Bget) and n 0
with T 0
ntt
iterations, have
B
Σ
B|| V Fiii +1)1 [
S 2.
C.4.2 Convergence analysis for Algorithm
We now consider MIL TPAUC maximization with mean pooling. Define F(w,s, s. = ne.
+ Ex,s,, (W) st), s'). Due the weak-convexity of F'W, 8') w.r.t. (w, 8'), we consider the following Moreau envelope and proximal map defined as
1
Fx s') min F(w.s, 5.5) w.8.8'
(ll
w|| + ||s
s|| || s'l1?),
2A
(w, prox (W, S, 8') arg min F(W, +
w w/l2 ||s
s||² + || s (1²)
W
2X
Following the same proofs of Lemma A.3 and Lemma
A.4 have the following error bounds
Lemma C.5. Consider the update for (ut, : X, E S, US_} in Algorithm Assume h)(
is Ch- Cipsiiz for all X, E S4 U-, and [| s M With
n4 B (1 71),
B.ll
36

---

n2
+ +11 71) and TI S 1 we have
72
B2(1-
B
4n C₁,
E
||0,0011 he(we+1)]l
1o:p0 (ww)))++++++ 1/2
n4
2n
B1 B1T1 1/2
X,ES+
X,ES_
B1T1 j
4n Cn.
10,,0+1 - hw(w
115500 hy(w:))l + 2T
0 0+
2n
BiT
X
X,ES
BITI )2((++1
1
||:0,0 - h.(ws)11 47 + 16n T2M2'r
|| - h: ha(ww+1)ll
n++
2n+
n4
BiT
X,ES+
X,ES+
BITI 21((()
16n² CR,M2
Σ
10,,011 - hy(
<1
Σ
11300 - h,(w,)]l +
47
2n
B
XyEs
X,68
Lemma C.6. Consider update for {ui, X, E S+} in Algorithm Assume gi(Uij s;) is ---isshitzz B3
W.E.t (Vig, s.) for all X, E S+ and X, S_. With 73 B, Pa] + (1 T2) and T2 S 2. we have
E
1
||u,et11
1
Σ
Ii (4441,8111411
n
X.ES+
n1
XyES-
BIT2
1
< (1
ee+1
|ui,0
gi(U3,0 - 12.0 V1,08810011 +2
2n
n
X,ES+
X,ES
1/22
12/22
1/2
1/2
1/2
+ C2 1
TI
+
C2
11.1
n4
+ C2
n1 11
B1
n
1/2
T2
1/2
B
B1
B
22
B T2
1/2
where C2 is constant defined in the proof.
Then we have the following covnergence guarantee.
Theorem C.7. Under assumptions given in Lemma u2
C.2 with
7 =
B1(1
n
T)),
Y22
Bx(1-T:)
+ (1
T)).
%
B1-1-
+ (1 T2). TI
O
min
Bs,
aj
Bi min /2
n
///2
1
1/2
4
1/2,
T2
O(Byrt) $ 1/2,
O
min
min my
Bi Ba min Byy 1/2 n//2
min
1/4
1B2
1/4
Bi
min
1/2 B 1/2
}B3
1/2
(d)
B
n
172
then after
1/2 max
B 1/4 B
1/4
n 1/2
T2 O iterations, Algorithm gives e-stationary point to the Moreau envelope, i.e.,
max
n4 max
B B2
B2/2"
1
n
1/4 1
1/4"
B
1
B
max
B
n4
B 1/2
1
6
Σ
IVPya(Ww, St, &011 5 c?.
-
1=
where p= pF CsC + Cp CyC,Ln.
37

---

Proof of Theorem C.7 Consider the change in the Moreau envelope:
Ee
[ 1/pp Wi++ S141, (111
P (1 -Wwil++lll" +|5 s1+1ll² - + 115 s/y (1²)
= Et
min w.s.3'
F(w, Se, 31)) 2
s E, [(W;, St, 8() + P
(Ilvv - we+1ll² + ||5t - sc+1ll 1|? + 113/ - 5 113
2
-F(,, Sc, 81) - Et 2
p
(Iw: - -(w: -w2 + || - (s. G
2
+ ||8 - (5] - -13))113)
(37)
I F F(W. Se 8/) + P
2 (1 -wel= ||: -s2ll + ||5 s((1²)
pe We, Gi) + n s G.) + 17(56 s/ G + 3n/ 3r PM
2
FWi/ St. 8/) + pE, (n( we, Gt) + 17/ - st. G3) + -n(3/ 5 G
3r/ PM²
2
where for simplicity we denote G? = ग.. EiER 0. fu s(), and G7 a n, n dimensionnl vector whose i-th coordinate is defined as
Ju st) Br Ex,esy On. 81)) 0,
X, E B
Bi
X; g Bi
The second inequality in the above derivation uses the bounds of E|||G, E [P] and B [?]. which follow from the Lipschitz continuity and bounded variance assumptions and are denoted by M.
Note that [Ga]
Σ Sufi(uinss))
1
Σ X,ES_
0.gi(Uz4 81,1 (Vh;(w)- (w))
n4 X.ES+
1
E. [ = n++ X.ES+
anfi(ui,t:())
Oagi(Uj, 81.)
X,ES_
[ n X.ES+
Σ Se
38

---

Define (We. St. 8t) = p/o (W,, s/). For given i fl.....m). we have
Hi Σ (i(h)(Ww)) - hw(ww),, Bs,,,, 81) Silus,e 8))
X,ES-
(0)
1 Σ gi(h)(w)) - h.((W).. us,e)
2 0, fi(u,, ()( - 51) + O. fu sb) n1 XyES-
2 02 O (1) - x1) + Suliluias 81)
Σ
gilUi,t Vi,t, meat
X,ES
1 Σ
+
(0.g)(1je v1,0, (hy((vr)) h,((w:)) - (U0e -4,1)))
11- X,ES_
P (w:) - (www)) (Uze- - 112
n1 XyES-
(38)
Un.gi(U5, 88,11
84,11 8i,
-81,)
Pg ||āt, stell
2
XyES
② Oz Fi (5) 5)) +ufiluuess)) o6)
1
Σ
9:(03,t vi,0, 81.1) -12
a
X,ES_
1 Σ (i)i(uu Uiis vi,,, s1,e), (W,) h:(ww)) - (Ujj - v.,+)))
n
X,ES_
(4 0i, 8i,)), si,1)
X,E8_
Ca
- hw:))) - Ps
||8i,
81,e|1
2
X,ES_
where (a) follows from the convexity of ft. (b) follows from the monotonicity of fel., s') and weak convexity of gr. (c) is due 0 S ( sf) < Cy.
The La- sm-ooootsssss assumption of h:(w) - hy (w) for i, w implies h h,(w:) - (w.))
La 1| well
(39)
2 hw())) - 1 (w,) ((V))(w.) - Vhy(w:)), w; -w) Since (v,,, 81),, 11,1, 82,1) 2 0. we bound A, following
2
A = s (1)0, - Uh,,, s1,1), (W.)) - h.(we)) - (155e - v,2e)))
1a.i 8 0o (Ui.t vi sit), (h: h,((w.) - (U1. vx,)))
Lp
(a.i(uss 3 0.00 - U2,1, 8i,t);
| - woll3)
2
(u..i(uss. (0000 - Uiee, 8i,e) ( (w:)..) ) Vhy (W:)), We we)
C,C,lllh, vael + (w:)(w:) 20lell C,CgLh |/ well2
2
+ (us, $ 0eg (1J,, Ustt 8t, ) (w:)) Vhy we we)
where inequality (a) follows from inequality 3y (b) follows from the Lipschitz continuity and mono-
tone assumptions on fi, gi, h4 hy. Then plugging the new formulation of A back to inequality 38
39

---

yields
1 Σ
fi
gi(hy(We)) - (w..), - s()
X,ES-
2 0. filui (1) 5i) + aufi(us,e;
Σ
gi(Use - V1,1, us
nh-
XyES-
1
Σ
[_ - ruel (We)(we))
23.ell1] (lbb))/))))) -
CjCgLin
1/ -wall
2
X,ES-
E
(uufi s1)0,g Uits (Vh,(((
wi -wa)
n-
X,ES-
+
1
Σ
(0),,.((0 uhs 8t,e), 8i, - -8,z)
n-
X,ES_
1
CsCs
((, h.(w))) (Uz, -22,))1 PoCS
||6r, si,ell?
n
2
2
X,ES
Taking average over i E
S+ gives
Σ f / Σ
(wi) - ((. - fi(ue,,, st)
T4+
X,E
X,ES
(E [.)) 8/ - (t) + (Ey [Gr) w. ww,) + (E, (E, - si)
1 Σ
dufi (ufi(ur,es si)
Σ
(e Ua.es 8i,0) Wiet
n X,ES+
X,ES_
CjCoLı
-C
[[((w,)) - Wi.ell + n
Σ
[1bs(ws) Uzeell
| well2
n+ X.ES+
2
X,ES-
1
Bo (((((()(w))) hh;(w)) -,(((() (ozae
ri,e)1
Σ
PoC1 1|:,, s1,ell?
14 XiES+
2
14 XiES+
XyES-
It follows
(B, 8y - 11) + (Er[Gr), w. - we) + (E, [E - ss))
Σ fil hi-- Σ (w)) - h.,,), 8() - fi(ui,e, st)
n+ X.ES+
n XyES_
- -.uf((u),)st))
21(23, (6,0310)) - 44,1
X,ES-
Σ
PgCt ((()((())) h.(w)) - (U1,4 - v2,))1 + PoCt
|| - st,l?
+
n_
2
2
XyeS-
+CCCg
1
Σ
[1(((w)) ve,ell n X,ES
Σ
[1hy(w,) - usell
C,CyLn ww We 12ll
74
X:ES
(40)
40

---

Combining inequality 37 and 40 yields
E,(Fi/p (W++1, S s(1)
-Fi/p(Wa (We, St, s() pn 1(w, - [.,.) + +S: 10-5 St, E|G!])> + (3% 5/6 1e, (G
3npppM
2
(0)
31ppM²
Fi/p(We. St, 86) +
-pn n4
Σ
P3 We, Bi,)) - Fo We,
2
X,ES+
1 Σ
+C n1 X,ES-
[1]h((w)) - w2,ell + |1/es( (w:)) Ug.ell]
1 Σ
+G$
Σ
gi(Uze- -62, -ui, + +Cp n
9ilUi, Uii, 8(,)) - ueet
X,ES-
X,ES-
+ n1- XyES_
1 Σ
PrCy (I((h(()) vsell? + [[,)((i)) Ugee 12]]
+
PaC1
||8s,e - sq,el1
2
CjCgLin 1 well?
+ C
[1/((w,) - urlel + n X,ES_
[1b)(w,) 2sall]
n4
X.ES+
3n2 2MP
Fii St, s/:)
+ p 81) F(w.,
1
20
Σ [W)e(we) ve,ell + (wh) -.,,ll]
+ +pn
n4
X.ES.
n
X,E8_
Cp
Σ
[1l)((w)) - ui,ell + [[/)(w:)) [hell²] + Cp,l well"
n1
XyE9_
20,
Σ
gi(U3, S1,), und POCs PoCT11ss s1,el1?
CjCoLi | /
wall
n_
X,ES_
(41)
where (a) follows from the Lipschitz continuity of f6 h4 hy and inequality 40
Due to the pe-weak convexity of F(w, S;, s'), we have (p - PF)P -strong convexity of s1, +
F(w, s, 8') + [.l( St, s6) (w, s, Il? ? Then it follows
F S(,,, 82 F((W,,
F. F. St,, 8t)
P
2 (((,,,,,,s)) 8/) - -(w,, 8t, 8/11
Fi Fi(we, 81) " [l(,,, St, 86) - (w 81, +1)1
(42)
[l( Sy, 54) (w,, S1 81)11
$ Pr (),, Sr, 5/) - (We. Se, 81)1
2
41

---

Plugging inequality 42 back into we obtain
E, FFi Wt+1; (4,1,6411
FLyp( (W,, St, 84)
31p pMM pm
1
Σ
( (pr -)]((we, - (Wr, Se, 8211
n+
X,ES+
20
+ n X,ES-
Σ
[w,b - w2,ell + |1/ (We) - -2,,e11
Cp
Σ
[[]b:(w)) - 21 [l1)((()) U321 12
n-
XyE8-
+ +
Σ
Di(Uz, U 81,1) - u1.0
+
PoCt
|| s4,11?? + Cy + CyCobh )| - well?
2
2
XyES-
PM2 + pm 1 Σ
[
S Fiip(We,8t, 81, 81)
Σ
([(W.,s.,)) - (W,, Se, 11)1
n4
X.ES+
C1
[1lb:(w:) - riall + (1b)(w:) rgsell + [1/((w.) - 22,1112 + (1h)(ws)) - -3g.el
X,ES_
gelUz - mi (1.) wa.s |]}
+ Ci
Σ
n- X,ES
(6)
37ppM²
3 Pi/plwe, Sc, 56) +
FIVFii/(Wr: St, s1)11
2
2
+ n+1l
pnC1 Σ
Σ
[1))((w)) - +1,ell+ (11h - Us + (1/,(w.) - reell + +1h)(ww)) - U3 1?2]
XiES+ XyES-
pnC1
1
g. 01,1, S1,)) 4z
nt
X;ES
XyES
where in inequality (a) we use PP poC, max(2C, Cp 2 and inequality (b) uses Lemma 3.2
CyCh + CjCgln and C1
With general error bounds
1
Σ
Bill/((w:) rllelll s (1 m1)²
Σ
[h,(wo)) vt,oll R1,
Th+
X,E8+
nh+ X,ES+
Σ
(wi) 11l S (1 - (12)) 1
Σ
[[h,(wo) -130ll + R2.
n_
n
X,ES_
X,ES_
- ([:)
< (1 - -m1)² 1
Σ
[1/((w)) - -2,,012 + R3.
X,ES,
XieS
13 Σ Bl]lg((w)) - < (1 -122² n X,ES_
- [l:((w))-uoolf + Rs.
n_
X,ES_
Σ
E Σ
gi(Uiet - St,e) - uis
X,ES+
X,ES_
< (1 - (1-1a)²
Σ
( - 41.0
+ Rs,
n4
n_
X,ES+
X,ES_
42

---

we have
E (141,
3r pMP
$ ( St, 8/) +
2[IV St. 81)11
2
+ + (1 (1-11)" 1
[[h((Wo) - vs,oll + (1 - p2)² 1
(1b)(wo) - 2/o0l
nh X,ES+
n X,ES-
(1 m1)² 1
[[ds(wo) 14,0ll + (1 -12)² 1
[Iny(wo) 03,011
n+ X,ES+
n X,ES_
(1 ma)) n X.ES+
Σ
9: - 01,0,8100) - ui,0
+ Ri R2 + R3 + Ra + Rs
n
XyES_
pMM
< ([FFi/((W,, St. st)l +
/ill (wr, Se, $1)11
2
+ mcC (1 (minn"
1
Σ
[l,(wo) - r1 + 1 Σ
[[by(wo) - 29,0
n4+
XiES+
X,ES_
Σ
[[4;(Wo) - n Σ (1hy(wo) - -3.00 1|
R4 X,E4+
XyES_
gi(U60 13,00 u1,0 1) + + Rs + R3 + R4 + Rs
Σ
Σ
T4+ X,ES
X,E8
where Mmin min #2, 133.
Taking summation from t 0 yields E // (WT, s/r
3Tp
T
S (wo so: (6)
E
V ( st)1
2
t=
T-1
+ CnCi
Σ (1
Mminn)
[[h((wo) - vi.oll n
Σ
(1hy(wo) "5.oll
14
XiES+
XyES-
+ n4+ X,ES+
Σ
[1x(wo)
12,012 + n
Σ
(W)) -P;,oll
X,ES_
ge - U9.01 81,0) - uio )) + +T(RI + R2 + Rs + R4 + Rs)
Σ
+ n1
n
X,ES+
X,ES-
3r1² 32T
T
S Fiip( Wo, so: (6)
"
V Piipp(Wwa W,, St,, 81112
2
Au
+ CnC
+ +(RR + Rs + Ra Rs + Rs)
Pmmin
where we use Σ1=
(1 - Mmin) < 1 and define constant Ag such that
Mmin
1
[lh((wo) - eq,ull +
Σ
([h)(wo) - 25,oll
n2
X,ES,
X,ES
1
Σ
[[hi(wo) - 02
1
Σ
(1hj(wo) vg.oll
n4
n
XiES
X;eS
1
Σ
gi(Uro 13.00 81,0) 11.0 1) SAo.
n4
X,ES+
X,ES_
43

---

Then it follows
V F1/p (W,,
10
3r/² pM
Fi/ So, - -B((1//(WT,,8 s/-]
1/T
2
Ao
+
T(R1 + R2 + Ra + R4 + Rs)
Mmmn
2A
(2+
14+
1mM2
Do
+ 12pCi(A + R2 + R3 + R₁ + Rs)
n/T
B1
Umin
o
) R1 + R2 R3
R4 Rs
T
Mman
where we define constant A such that Fizp( Wo, So. s/1) ( ST, s S A.
With MSVR updates for Vi,t and Ma,t, following from Lemma C.5 and Lemma C.6 we have
BITI
BITI
BIT2
1n1 2m+
112
2n
143
2m+
2T 12
4n CRMM
R2 2T 1/2 0
4n Mr
R1
+
B3
BIT1"
1/2
B3¹
B2T1"
1/2
4T10²
16n C 12
47102
16n 1²
R3
R4
+
B3
B7
B3
2T
1/2
12+
B 1/
1/2
T1
11
1/2
n1
1/2
11
1/2
Rs
+
C2
C2
C2
B2
1/2
B1
n
1/2
1/2
72
1/2
B
B 1/2
B
1/2
T2
1/2
B1
1/2
Then we have
(W,, 8611
T
t=
1/2
1/2
1
1
1
T2
0
B 1//2/ Jo
1)
Umin
B3
B 1/
B 1/2
1/2
1/2
17
17
n2+ B1
max
{
+
n4
max
n4
n_
1
B1 B1T1
1/2
B2T
1/2
1/2 n
1/2
T22
1/2
B1
B1
B3
T2
1/2
Setting
1/2
1/2
o
min
B3.
74
B1
min
n
B1/2
11
B
2
1/2
E
T2 O(B2E*)
O min
min
B1
Bg
1/2 min
B/2
B
min
{
1/4
n
1/1
B2/4
B1
min
B1/2
1///2
12/2
Then with n4+
n
1/2
B
1/4
B.//
B
n
n1_
n
n 1/2
B1/4
B B2/4
1/2
1/2
T O max max iterations, we have
11+
n
max
max
n
max
n4.
71
-6
B
B2
B
1/2
1/2
n
1/4
n
1/4
B2
1/4
B
1//2
B
1/2
B 2
|V
St
44

---

D Proofs of Lemmas and Propositions
D.I Additional Proposition
TR is open set. Assume to be non-increasing (resp. non-decreasing) with respect to each element in the input, then all subgradients of f are element-wise non-positive (resp. non-negative).
Proposition D.1. Consider Lipschitz continuous function :: - R. where O C
Proof of Proposition D.7 Let D be the subset of O where f is differentiable. By Theorem 9.60 in [24], a Lipschitz continuous function f + I. where C Rd is an open set, is differentiable almost everywhere, i.e., D is dense in O. Then by Theorem 9.61 in [24), the subdifferential of f at defined as
(z()) confv [v|Baxx x with vE D, V + v),
where con denotes the convex hull. If we assume that is non-increasing with respect to each element in the imput, then fz(z) < 0 (element-wise) for all differentiable points E D. It implies that the all vectors in {u/Brr + with z D, f(z.) - y are element-wise non-positive. Therefore, all subgradients of f are element- weise non- con-positive. On the other hand, if we assume that is non-decreasing, one may follow the same argument and conclude that all subgradients of f are element-wise non-negative.
For functions/ f O + Rm where O C Rd is an open set, one may write f = (m. and apply the above proposition for each fk, h: I....,m.
D.2 Proofs Proposition 4.2 and Proposition 4.4
To prove Proposition 4.2 and Proposition 4.4 we first present the following proposition on the
weak-convexity of composition functions.
Proposition D.2. Assume f Ted + IR is P1 ---weakly-conve and Ci-Lipschitz continuous, g Rd - Rdd is Cz-Lipschitz continuous, and either of the followings holds:
1. f()) is monotone and g(-) is Lz-smooth;
2. f() is non-decreasing and g(-) is L2 Lgg
then f o g is ğ-weakly-conver with ý vdL2C1 P2C2.
Proof of Proposition D.2 The weak convexity of f implies
f f(g(v)) 2 f(g(x)) + (g(y) g(x)) P (la(v) - g(x)]12
2
C2 || - y1l
2 f(g(z)) + T (g(x) g(x))
2
where u E (g(()))) Moreover, due to the smoothness of 9()) (or weakly- of g(.), then only the second inequality holds), we have
L2 y1l
g g(z) S Vg(z) x) +v
(43)
Lg
g(v) g(x) Vg(z) (y 2)
where vee denotes a d-dimensional vector with value e on each dimensions. We first assume that f non-increasing, then we may use the first inequality in (43 and the Lipschitz continuity of g get
L2
CIC
f((())) 2 f((())) T
Vg(x) T (v -0y=x)+
2 |
w/l
2/1²
2
La
C2
f((((z) + Vg(x)) (y x0= T
|z - w/2
v11
2
2
2 f(((())) + (0 Vg(2)) (y x) VdL2C1 + pi C2
|
y11²
45

---

On the other hand, if we assume f is non-decreasing, the same result follows from the second inequality in 43 Thus f o is j-weakly-convex with 0g = vdl2C1 + + PIC2.
L
Proof of Proposition 4.2 Under Assumption 4.1 Proposition
D.2 directly implies the pp-weak-
convexity of F(W) with PF C + C.
Proof of Proposition 4.4 Under Assumption 4.3 we first apply Proposition D.2 to the composite function 9: g:(ha,(-)) and obtain its P3 ddz CnC
S.cg-wea--ooovxxity To show it Lipschitz continuity, we use the Lipschitz continuity of Ji and hasj to obtain
((((h,,()) - g, (ht,, (w) S C w/?
Thus gi(ha,
(w)) (w)) is C3 Cg Ch ----ipcchiir--conimuuuss
Since we assume f-(+) is non-decreasing, P pr-weakly-conve and Cy-Lipschitz continuous, and (-)),((-)) is pj-weakly-convex and Cg-LLpschitz-contimoos we apply Proposition D.2 again to conclude that F-) is OF C + Py weakly--oonn
D.3
Proof of Lemma 4.5
Proof of Lemma
4.5
With
11 11 B (1
+ +11 T
MSVR update gives recursive error bound
E W1 9o (w(++1))l 1
BIT [B[[| - 9: (w:)))1 + 272
8n1 C
S (1
9 B
w.
wot1ll3]
711
n1 B2
Bı
B1T ]B[[] (w:)l1] + 2T²
8n C2
< (1
[
111
n1 B2
B1
B1T ] [4,, 9w
2r 2r² B10²
8n1 M2
< (1
2n1
B2
B1
Applying this inequality recursively, we obtain
B Billugtt+1 g(((++))11
(1 BIT BITyy(e+2)) 1|u,00 (:((w)
BIT 2(1-
Bi0
8n4 C2
>
2n1
2n1
B1B2
B1
j=0
BIT (ert)(+++))1ss 2:(
4T
16n C2 T2
(1
+
2n1
B2
B
where
B1T)2(1-J) < E)=0(1 2n,
2n1
It follows
E Illli,tt1 (:((++1))l) 11l
E Billui,t+1 gi( (W(+1)))l3)
(1 ) (100t))))1000000 (1 +
4TO²
16n
+
2n1
B₂
BsT
(1
BIT
B g++
[0,0 9:
272
4n An
2n1
B/7
Thus
E
Ui,4+1 - g.( g.(We+1)ll
B1T y+1
2/2/20
4n, Cn
< (1
I|ui,0 (wo))
+
2n1
B2/2
1/2
46

---

Taking summation over i E S, we obtain the desired result
EE
|ui,
gi gi(we+1))
71
iES
BIT
[+1 1
1125,0 g:wolll + 2-1/20
4nCg
I (1
2m1
B/7
EE
D.4 Proof of Lemma C.6
Proof of Lemma C.6
With 13
14 - B1
[1(1-12) + +(1 T2) and 72 S J. MSVR update gives the following
recursive error bound
E 11,111
Σ
gi(Uz,011 0i4+1, 11441, 81,441
n
JES_
< (1
T2 |l[|uu,
1
9l1u 11A 8t,))1 + Σ
2T B₁0²
n
n4 B2
jES-
8n4 C2 E [1
U2,03 81,0)
(1j,41 11441 (1,41)111
(44)
Bi
BiT2
1 Σ
2T B10²
< (1
Elllui,
g: Ui, 81,
n
n4 B2
JES-
SC2 12 B1 remains to bound E|| 0 [2]] and [[[l, 13,4+1 1| We bound the former, and the latter's bound naturally follows. Consider the update of 01,++1 and we have
16n
C2
E Blllu, - 01 1| ||u5, 13,+211
B1
01.+1113]]
B
<
E
Uiu - 1 (w,; 71 (w.; (h:) - 12 (w:1;: B3,))1
n
12
2B17 (1((0) (Wr; BB,,) ) - (1) (w 13 B1
<
E
Uiit- 1000 (w,,; BB,))
nh+
n++
[2Bri
2Br |w w 2
E2
(0) (wa; B' .112
n2.
n+
(4)
8 814 12 2
n4
B1
where inequality (a) uses TI S 1/2 and 71 inequality back into inequality 44 gives
21 n (1-)
+11 (1-T)) S
2n1, B,
Plugging the above
Ul 7_
Σ
g( - 11 11,1+1)11
JES_
< (1
B152 n
E uuAt
Σ
9:(0j,e Uite st,))1
2T Bi02
n
n B2
JES-
16n C2
8TfMM2
B1
B2 + 80 22
n4 1ー
By +
8C2
B1
n4
n_
B1
B1
< (1 Bi52
2T Bi02
BBlluuat
Σ
gi (vj, Vi,t: 81, 11
+
n
n JES_
n B2
+ 1288222 M22 n4
Bi +
B2 ソー
+ 1280 C2 222 n4 24 + n )n? +
802 SC2M²'0
Bi n
n_
B
B1
B
B1
47

---

Applying this inequality recursively, we obtain
Billus,+11
1
Σ
9i(1j,t+1 (1,+1,8,,+1111
72- JES-
S (1 T172
Bi 2(1-5))
22 oi
Σ
(: 1300 820)11
+
50
(1
2n+
n
2n+
n4 B2
JES_
j=0
+ 1280 M²
n+
B1
B2 )r + 1280 9 1280, C,.M²
m
n+
1n/
80 802M317
9
B1
n
n
B1
B1
B2
B1
< $1 B172 22((+1)
4T20²
U1,00 |lu,t
De (v - U3 81,0)11+ Σ
2n+
n jES_
B2
+ 2560 M 1
B1
+
B2 -
+ 256C' 2 CP.M2
n1
14+
+
)
n r
16n C2M
9
B7
n1
B
B1
B2
B²TT2
< (1 72
) (2((+1)
4TZ0²
C2 2
B1
B2
|11,00
9: (i(0i,0 1200 81,0)1++
+
+
2n+
n JES
B2
Bi
n
T2
+ C2 n
n
+
n
1²2
+
C2
B
B1
B2 T2
B
where
we
use
E/=0
Bin ) (t-
2n+
2n Bi
and denotes
C2
2 max g M², 2560 norm error bound.
CRMM2 160'M²)
Taking average over E S+ gives the squared-
g
To derive the norm error bound, we derive
E
01,+11
1
Σ
9. 01,41,
n--
JES
S
&B[[uug+1 n
Σ
9: (V - 04,41, (44+11111
JES
S(1
T1 (113)((++))11 ||
||ui,
1
Σ
gi(Ui. 81,011
4720²
+
C2
n²
Bı
+
B2 oी
2n+
n_
B2
B?
n4.
n_
T2
jES_
C2 n
n4+
C2
B
B1
B2
T2
B²
B1 s+1
111,0
1
Σ
ge(T3,0 03,0,
1/2 0
C2
n4.
B 1/2
B
1/2
2n+
n
JES_
B2/²
B
11
1/2
1/2
T2
1/2
1/2
1/2 2
n4
n
n
n
C2
+
+
C2
B1
B1/2
B
1/2
B1T2
1/2
T2
Thus
E U1,41
Σ
g. U 11,1
n JES_
<1
B1 1+1
||ui0
1
Σ
gi(Vi.o - Uj s1,0)]l +
2T 1/2
+
C2
n
B
+
B 1/2
2n
_
B
1/2
1/2
1/2
JES_
12
1/2
1/2
1/2
+ C2 n2+
11
11
+ C2
nt 1)
B
B /2
B
T2
1/2
B1T2
1/2
1/2
48

---

Taking average over i E St, we obtain the norm error bound
E
|iie+1
1
Σ
gi(Uaa41
n
iES+
JES-
(1
T2
1+1
1
||ug,
Σ
gi(ui,o Uj,0, (00081.0)1+
2T2
1/2
2n+
n
B22
V
jES-
B/22
11/2
1/2
1/2
1/2
C2
n2.
T1
+
C
74
11
+
Tt
9
+ C2
n 1]
B1
T1
1/2
YI
1/2
22
B1
B
2
B1
1/2
B B1T²"
1/2
49

---

D.5 Proof of Lemma A.3
Proof of Lemma A.3
With 71
1g Bi Bg (1--11) and S 2. MSVR update has the following
B1
recursive enror bound
15
15
EE ||
w
S (1 B2T1
27 B1 B20²
8ni
(w,)()
+
E Wt - w
R1
B1
B₁B,
$ (1 B, B2T BBll
2T BrB B B2
8n C3
hi. (w))(1))
2n1
R1n2
B2
Applying this inequality recursively, obtain
Bllliga+1 hig (W:.((W-1)) (w.-))113)
(1 Bi B2 12t++1110u. hwo((
Bi B271 j((t-))
27 B1 B20
8n M
+
2n1n2
2m1
n1
B1
j=0
B₁ B2
4
16
< (1
1 - hu.s(wo)ll
2nin2
B₂
B
where we use Σj= By B2T ))(-)))())))))))
2n1n2 B,B
Taking average over (i.j) E S1 x S2 gives the
2ning
squared-norm error bound.
To derive the norm enror bound, we derive
E Blloa, (W
S [E[l Ut,. his (w++1)ll3]
Bi B2 2014)))++))))1) 11u - hi (wo))l
47
16nin203,M30
S (1
2n1n2
B3
B₁B
< (1 By B2T y++ 02.500 (wooll
2////2
4n Am1n2Ch,Mi
2n1
B3
1/2
Bi B2T
Thus
Bl]lvt,,,t1 - Kig (W(+1)l
272//2 2
I (1 B3 B2 1++ ||0.0,00 hwo)()))l
4n1noChMM
+
2n1
B
B, B1
Taking average over (1,5) E S₁ x S2, we obtain the norm error bound
1
E
|lajatt1 hes(W)+))ll
n1
112
JESt
jESa
Bi
27
4n
< (1
Σ
U1 - ha,(( +
+
221112
n1
112
B
B1 1/2
ieS
JES,
D.6 Proof of Lemma A.4
Proof of Lemma A.4 With 72
n1-B B,(1-7a)
+ (1 T2) and < 1, MSVR update has the following
recursive error bound
15
Billui,t41 n2
Σ
JESa
(45)
< (1-
B172
|E
1
Σ
2- (((
2T²
8n C2
E 11 2
n2
n B2
B
jES2
50

---

It remains to bound El [. which is done as following
c1j.+ 1
B1 B2
E
"/ (ha, (we; B3,,.)) (wo (8,,,
R2
2B, B2Ti
2B B271
E
|la.j. his (We; B b )11
Ww; [1ha, (W,; (3,io) - (w,((w
1222
12
[2B, B2Ti
2B, B27 Ch
E
|oa.j ,is (wi; B 3, )112
We wL-1l1
R1
R2
WV
8B, B27
R2
B2
where inequality (a) uses Ti & 1/2 112andd n
n12 Br (1-T(
+11 71) S
2n:n2 B,
Plugging the above
inequality back into inequality 45 gives
B
1
Σ JESS
112
< B1
E
Σ
9e [((()))))))++++
B102
8
8B, B2TAMM
8n1 M2
n1
122
n1 B2
B1
n1722
B₁ B2
JES2
T1
2T BT
6AB2TTM
G
< (1
|B||
711 B2
BBB2
JES2
Applying this inequality recursively, we obtain
1
Σ
T12
JESt
$ (1 T2
B1 2
2TT B102
64B27
22(4+2
Σ
+ Σ
+
2n1
n2
2n1
11
122
JES,
j=0
64n M2
BBB2
T2 (2((+2))|115
4T20²
128n, B2f
128 M²2
< (1
Σ (((U),,0012=
2n1
Bin27
B2
JES2
where we use Σ E/ - error bound.
Bicz (( < 2n1
2n1
Taking average over E S) gives the squared-norm
Big
To derive the norm error bound, we derive
E B1l|u,,41
1
Σ
n22
jES2
< <B[llug,4
Σ ((
112 JES.
B1 220++1
4720²
128n, B2tfM2C.
12 M2
< (1
Σ
g. (.(.,.,))11 +
2n1
B₂
B1u222
B B222
JES,
(1 B1 ++
1
2T
8 8
2m
1/2
B 1/2
T MC
8/2m n2 CnnMC
3/2 1/2
<
|
gn(0i..0)ll +
+
2m1
n2
JES2
1/22
B 1/2 1/2 1/2
f12
T2
1/2 B3¹ 1//22B]/2 T2
51

---

Taking squared root on both sides and taking average over i E S1, we obtain the norm error bound
E
|1,1411
ge
(v(
T1
T22
iES1
,ES2
S (1
T2 6-1 1
11,
1
Σ
gi(v).,))1++ +
2T2 B
1/2
+
C2 1/2
B2 TI
C2n1 2/2 3/2 1/2
12
2n1
iES
n22
JESz
B 1/2 1/2 1/2
12 T2
B 3/2 1/2 1/2
B₂ T2
where C2 = max (8v2MC, MC,)
D.7 Proof of Lemma B.2
Proof of Lemma B.2
Define
Uie = -T)uit + (We( B2,,)
Then we have
E [11 9:(w) (w.))11
EBB, [l](1 - (us, - gi (Ww)) + 7 ((:: (wr: (3,,)) 9: (w())))
Esg, [(1 +)&1lus,e - 9:(w.)) + 1916 (w:; BB, 9s (w
+ 2(1 T( 3i (:(w)) gi
b.::::(Ww (Wr; (w.;BBg,) gi (w:)))
< (1 7)11, (w:))) -²02
B2
It follows
Egg E8s [||us,0+1 [:(w)]
B Egg [l|ãa,e - 9:(w)))]²] + (1 )[ui, - (aatt-gi(ww) g:(2
B1
71
111
B1 (1 - - 9:(w)))?
B1720²
B1
<
+ (1
Iluu g((w))l1
n1
ni B2
n1
B1d )/||u,, 9.(w)))1++
Bi7202
S (1
2n1
Ti B2
where we use
Bi (1 7) (11
B1
B
B
_ (1 2T
+
+
+1
n1
11
711
n1
B1
B1
1 2T T11
+
71
Bi
< 1 T
7/1
1 B1
TB1
)² = (1
TB1 12
71
2n11
2n1
Then
E4[luu,,+1 - gi (we+1))l
BIT |||u,,411 ||lu,,t1-9:iw (ww))) + (1+
4n1 )lgg((w.) - ge (e(we+1)l??
< E,
(1 + 4n1
B1T
< (1 +
B1d )1
BIT
/2||ut, B1T)21|ut,t
99:(w))1 + (1+
BIT 227
4n
2n1
4n1 B1
4m1
+ (1
C9 |W: 3
B1T
BiT T 2 14,1 - g:(w)))
2B,
8n, L.E,l W
< (1
+
4n
B1
BiT
B1T | (2
2B
8m
C2 12
< (1 4n1
+
B1B2
B
52

---

BIT I 1. Applying this inequality recursively, we obtain where we use
An1
B Blllu g. (W(+1)ll
$ (1 BIT ) BBlluue - ((ww))]l
8n 12
4m
7h B1
BIT
(1 B1T (orya(++))1uss -((o))l?
Σ
BIT
22(--)) )
[2B
8m1 122
4m1
4m1
B1B22
B1T
f=
(1 BiT /a((+2) 10.0 111,0 g:(w)]l
STO²
32n 3 C2 12
+
An
B2
B²T²
where we Σj
$m. B ((1-)) I
BiT"
To obtain the absolute bound, we derive
E|||u,,++1 (w(+))))
E u1,+1 9 (((w-1))
B1T (1 - ((1=:c++-)luoo-0((()))) -w(()))??
8TO²
32n
(1
+
An
B2
B²T²
B - (wo)ll
2/2 20
4,
4n
B
BiT
The desired result follows by taking squared root on both sides.
D.8
Proof of Lemma
B.
Proof of Lemma
B.5
The proof of Lemma B.5 is the same as Lemma B.2
D.9
Proof of Lemma B.6
Proof of Lemma B.6 Define
ūs.e = -1 -T2)ui, + T2 B2 jEB
1
Σ
ge(ti.a))
Then we have
Egg [||
Σ gi (11
712 jES2
= =Eg [1l(1 - -ui)
Σ (x(,),)))) + T2(
Σ (1(,),)))
1
Σ
ge (vv.,,)))
B2
n22
jES,
jEBS
jeS²
1
1
Egg [11 -12),
Σ
(x( 11 17+773 7
gi ((((jj)))
n2
B₂
n2
JES,
jEB
JES,
+ +(11 T2)T2(us.
1
gi(Ve,,e), Σ
ge((a.j,))
Σ (((
72 JES,
B2
n2 JESo
jESt
< (1 - 12)3211,,,
1
Σ
T2002
n2
B2
JESz
53

---

It follows
1
BBg, BBy [||,,,111
Σ (
n22
jESa
Bi
B1
BBB [1|
9s (vaa..))) )19] [11]
Σ ge si(
71
71
n1
122
JESr
JEB2
B1
(1 112)
1
9e(1),,))1? +
B1
+
B
1
Σ
9e (v(
11
n22
B1B2
nn
12
jES²
jESa
< (1
B1
1
Σ
2m1
12
B2
jES2
where we use
B1 (1 - r2) +
B1
T2B1
S (1
2m
Then
E.[] (i,11
1
Σ
9: (:(
112 jES²
(1 T2
4n |||
$ Rg
||iitt1
Σ
ge ((( + (1+
Σ g((..,,)))
Σ
g (015,,)+)
4n1
122
B1
11/2
122 JESz
jES
JESz
T2 (1
1 21
BIT2, 3²2
B1
B2
$ (1
ge (( +
An1
2m1
112
4n1
11
B2
JES2
4n1
+ (1+ +
|oigh - 01..
T1
112
jES.
B172 ) uuit
2B17z0²
8C2
$ (1
B1 +
4n1
n22
12272
JES2
where we use
Bin < 1, and 4ng
Bj B2 Egg
B1 B2
E. [[[ wi.j.-ill1 |1
| - This (w:5 b1,
7:1 12
n1
Applying this inequality recursively, we obtain
1
Σ
n22
JES2
< (1
Bi PEll
1
Σ
2B, T30²
8C2M2B2rh
4ni
112 JES,
n1B2
11272
T2 221+1)21111
B1 22(--))
[2B
8C2
S(1
Σ
ge (
+
> (1
4m1
n2
4n1
B1
72222
jeS
1=0
Bi 20+++)
8720²
32C 9
M BTT?
S1
116,0
ge (v
+
4n1
11-2 JES,
B₂
B1n27
where we use E/
Bi 2(1-))
<
4n1
Bi
54

---

To obtain the absolute bound, we derive
01,+11
Σ
T12
JES2
|B|| 01,+1
1
Σ
ge 9e(05,5++1)111)
n2
JES2
<
Bi
2((+1)
|ui,
Σ
g: 0=(Vig,0011++
8T20²
+
32C n, B2T
9
4m1
B2
B1 B1n272
JESZ
B1 2 1
1 Σ
2v2r2 1/2
4v 2C,
g Mn 1/2 11/2 TI
B
1|
12:,0
4n
722
B²2 1/2
B B 112
1/2
JES,
The desired result follows by taking squared root on both sides.
E
Group Distributionally Robust Optimization
NSWC FCCO finds an important application in group distributionally robust optimization (group DRO), particularly valuable in addressing distributional shift (25). Consider N groups with different
distributions. Each group k has an averaged loss (x(w) au Σ ((f(()))) v²") where the
the model parameter and (x ut) is data point. For robust optimization, we assign different weights different groups and form the following robust loss minimization problem:
min I18N PEO
Pa p&La(w).
where C. A and denotes a simplex. common choice for Ω is St = {p E A. S 1/K] where K is integer, resulting in the so-called CVaR losses, i.e., average of top-K group losses. Consequently, the above problem can be equivalently reformulated as [23]
min min F(w,)) s)
(Lx(w) +]+ +
K
This formulation can be mapped into non-smooth weakly-convex FCCO when the loss function E(, )) weakly convex in terms of w. In comparison directly solving the min-max problem, solving the above FCCO problem avoids the need of dealing with the projection onto the constraint Ω and expensive sampling in existing works
F
More Information for Experiments
F.1
Dataset Statistics
Table 3: Datasets Statistics. samples.
The percentage in parenthesis represents the proportion of positive
Dataset
Train
Validation
Test
moltox21(10)
5834 (4.25%)
722 (4.01%)
709 (4.51%)
mtlmuv(t1)
11466 (0.18%)
1559 (0. 10.%)
1709 (0.35%)
molpeba(t0)
120762 (9.32%)
19865 (11.74%)
20397 (11.61%)
Table Data statistics for the MIL datasets. D+/D the positiveenegative bag number.
Data Format
Dataset
D.
D_
average bag size
#features
Tabular
MUSK2
39
63
64.69
166
Fox
100
100
6.6
230
Histopathological
Lung
100
1000
256
32x32x3
Image
Lung
100
1000
256
32x32x3
55

---

F.2
Illustration for Histopathology Dataset on MIL Task
Bag
Bag
Colon Ade.
Colon SCC
Figure 2: Illustration for Histopathology Dataset on MII. Task. Ade. is abbreviated for adenocarci- noma and SCC is short for squamous cell carcinoma. In this work, each RGB image separated by 32x32 non-overlapped patches, which constitute the bag.
56


Reviews:
[{"review_id": "x9omtnPlR9", "reviewer": "Reviewer_SCt1", "summary": "The manuscript studies a class of non-smooth non-convex compositional optimization problems in which the objective function is given in a form of finite-sum composition where the functions are assumed to be weakly convex. The authors present stochastic approximation algorithms to solve this class of problems and establish their sample complexity bounds.", "questions": "1. In Table 1, the authors compare their results with the existing ones for smooth problems. However, dependence on $n$ is hidden and the reader cannot compare this dependency. Moreover, they need to add more existing results (mentioned on page 3) to the table with their assumptions so that there is a clear picture for comparison.\n\n2. The choice of bath sizes appear in the complexity bounds, however, there is a very limited discussion on its role.", "limitations": ".", "rating": 5, "confidence": 5, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The authors provide the sample complexity bound of $O(1/\\epsilon^6)$ for a single-loop algorithm applied to non-smooth weakly convex compositional problems.", "weaknesses": "Given the existing works in the literature and assumptions made in the manuscript, the presented theoretical results are incremental.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer SCt1 for the detailed and insightful review. Here we would like to address your concerns. \n\n**Q1**. Difference from  the existing works in the literature. \n\n**Response**: We politely disagree with the reviewer that our work is incremental in light of existing works. There are fundamental differences between our work and existing works. This is the **first work** studying finite-sum coupled compositional optimization (FCCO) problems in **the nonsmooth setting**, i.e., no smoothness assumption is imposed on neither $f_i$ nor $g_i$. (1)  As discussed in lines 47-51 for previous works on smooth FCCO and lines 65-69 for our work on the analysis of convergence, there is a key difference in the analysis. Previous works heavily reply on the smoothness of the outer function $f_i$ for bounding the error of stochastic gradient estimator, which is not applicable to our setting.  (2) Our assumptions about weak convexity assumptions on $f_i$ and $g_i$ are **weaker** than smoothness assumption made in existing works [13,21], as the latter implies the former. No existing method can solve non-smooth weakly-convex FCCO unless additional assumptions are added. (3) Moreover, our results bring new algorithms for solving  a family of weakly-convex concave min-max problems in the form of $\\min_{x}\\max_y \\frac{1}{n}\\sum_iy_i g(x) - f^*(y_i)$, where $f^*$ is convex conjugate of a convex function $f$. The best existing methods are double loop methods with complexity $O(\\epsilon^{-6})$ [20,26,36,38]. However, our method is single loop with the same complexity.  Last but not least, the considered non-smooth weakly-convex TCCO is novel, which has important applications in ML but no efficient solution is available in existing works.  \n\n\n**Q2**. Regarding the dependence on $n$ and the roles of batch sizes  in the complexity bounds. \n\n**Response**: We will summarize the detailed complexities exhibited in our theorems into Table 5 (can be found in the pdf file from the global response) revealing the dependence on $n$ and the batch sizes as below. We have also discussed the dependence on the batch sizes and $n$ in detail at lines 230-234 for SONX, and lines 239-242 for SONT. Our SONX algorithm for non-smooth FCCO has the same dependence on the batch sizes and $n$ as MSVR [13] for smooth FCCO. The dependence of SONT's complexity on these parameters is more complex than that of SONX. Nevertheless, we have provided some discussions in lines 239-242. Overall, we can see that increasing the batch sizes plays a role of accelerating the convergence. \n\n\n**Q3**. Comparison with more existing results (mentioned on page 3) to the table with their assumptions so that there is a clear picture for comparison.\n\n**Response**: Please see Table 5 (can be found in the pdf file from the global response) for the comparison of more existing results. We will provide Table 1 in the revision.\n\n"}, {"review_id": "mrAhEnMaZ0", "reviewer": "Reviewer_mWSr", "summary": "The purpose of this paper is to introduce a new approach to solving a specific type of optimization problem called non-smooth weakly-convex finite-sum coupled compositional optimization (NSWC FCCO) problems. The authors specifically focus on a variation of FCCO problems where the outer function is weakly convex and non-decreasing, and the inner function is weakly convex.\n\nTo address these problems, the authors propose two new algorithms. The first algorithm is designed for two-level NSWC FCCO problems and operates using a single-loop. The second algorithm is an extension of the first algorithm and is intended for tri-level NSWC FCCO problems. The authors provide a comprehensive analysis. They establish the complexity of the algorithms in terms of finding an $ε$-stationary point of the Moreau envelope of the objective function.", "questions": "I acknowledge and value the authors' dedication in exploring the intricacies of the technical aspects. Nevertheless, I fail to find the application of maximizing two-way partial AUC particularly inspiring. Could you please demonstrate any other compelling applications?", "limitations": "no", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is of high quality as it provides a detailed and rigorous mathematical analysis of the proposed algorithms. The technique of using Moreau envelope is intuitive and interesting. I have not checked the proof line by line but it looks good.  The authors also conduct extensive experiments to validate their theoretical findings. They compare the performance of their algorithms with other competitive methods across multiple datasets, demonstrating the effectiveness of their approach.", "weaknesses": "The authors have presented new convergence analysis for FCCO and TCCO, which I acknowledge. However, it seems that other multistage algorithms have already achieved the optimal rate. Consequently, I would lower my evaluation score for the novelty aspect.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer mWSr for the insightful review. Here we would like to address your concerns.\n\n**Q1**: It seems that other multistage algorithms have already achieved the optimal rate. \n\n**Response**: Thank you for acknowledging  our new convergence analysis.  However, there is some **misunderstanding** of our results. No previous algorithms and analysis of non-convex FCCO (even the broader family of non-convex compositional optimization) are applicable to our considered non-smooth weakly-convex FCCO/TCCO problems as they assume that $f_i$ and $g_i$ are smooth. Our work is the first to study and solve non-smooth weakly-convex FCCO and TCCO problems, i.e., where $f_i$ and $g_i$ are non-smooth weakly-convex. All the possible existing solutions to non-smooth FCCO [20,26,36,38,15] need to reformulate FCCO as a min-max problem assuming  the convexity assumption of $f_i$. \n\n\n\n**Q2**: Could you please demonstrate any other compelling applications?\n\n**Response**: (1) We would like to point out that two-way partial AUC maximization is particularly important in medical domains where it is important to restrict false positive rate to be small and true positive rate to be large (Yang et al. 2019). (2) We would like to provide another important application of NSWC FCCO for regularized group distributionally robust optimization (group DRO), which is useful for addressing distributional shift (Sagawa et al. 2020).  Consider $N$ groups with different distributions. Each group $k$ has an averaged loss $L_k(w)=\\frac{1}{n_k}\\sum_{t=1}^{n_k}\\ell (f_w(x_t^k),y_t^k)$, where $w$ is the the model parameter and $(x_t^k, y_t^k)$ is a data of the $k$-th group. For robust optimization, we assign different weights to different groups and form the following robust loss minimization problem:\n$$\n\\min_w \\max_{p\\in \\Omega} \\sum_{k=1}^N p_k L_k(w),\n$$\nwhere $\\Omega\\subset\\Delta$ and $\\Delta$ denotes a simplex. A common choice for $\\Omega$ is $\\Omega=$\\{ $p\\in\\Delta, p_i\\leq 1/K$\\} where $K\\leq N$ is an integer, which yields the so-called CVaR losses (i.e., average of top-K group losses). As a result, the above problem is equivalent to (Curi et al, 2019):\n$$\n\\min_w \\min_{s} F(w,s)=\\frac{1}{K}\\sum_{k=1}^N [L_k(w)-s]_+ + s.\n$$\nWe can map this problem into non-smooth weakly-convex FCCO when the loss function $\\ell(\\cdot,\\cdot)$ is weakly convex in terms of $w$. Compared with solving the min-max problem, solving the above FCCO problem does not involve dealing with the projection onto the constraint $\\Omega$ and avoid expensive sampling as in existing works (Curi et al, 2019). \n\n\n\nReferences:\n\nYang et al. Two-way partial auc and its properties.Statistical methods in medical research,28(1):184–195,2019.\n\nSagawa et al. Distributionally Robust Neural Networks for Group Shifts: On the Importance of Regularization for Worst-Case Generalization. ICLR, 2020. \n\n\nCuri et al. Adaptive sampling for stochastic risk-averse learning, 2019.\n\n\n"}, {"review_id": "spl667HXl3", "reviewer": "Reviewer_evM3", "summary": "This paper handles the problems of non-smooth weakly-convex compositional optimization. The first problem, referred to as FCCO (Finite-sum coupled compositional minimization), is given by\n\n$$ \\min_{w \\in \\mathbb{R}^d} F(w) \\triangleq \\frac{1}{n} \\sum_{i=1}^n f_i(\\mathbb{E}_{\\xi\\sim \\mathcal{D}_i}[g_i(w; \\xi)])$$\n\nThe second problem, referred to as TCCO (Tri-level coupled compositional minimization), is given by,\n\n$$ \\min_{w \\in \\mathbb{R}^d} F(w) \\triangleq \\frac{1}{n_1} \\sum_{i=1}^{n_1} f_i\\left(\\frac{1}{n_2}\\sum_{j=1}^{n_2} g_i( \\underset{\\xi \\sim \\mathcal{D}{i,j}}{\\mathbb{E}} [h_{i,j}(w; \\xi)])\\right)$$\n\n\nHere, the outer functions $f_i$ and $g_i$ are Lipschitz and weakly convex which has not been considered by previous works and significantly complicates the analysis. \n\nThe authors propose two algorithms, SONX and SONT for the two problems respectively. For the first problem, FCCO, $u_{i,t}$ are the estimates of $g_i(w_t)$, $\\forall i \\in \\{1,2,\\ldots, n\\}$, which are required for an unbiased estimate of the the complete function $F(w)$. In each step, a batch $B$ of coordinates from $\\{1,2,\\ldots, n\\}$ is sampled and only the estimates in this batch, $u_{i,t}, i\\in B$, are updated using a Variance-reduced estimator. Using the estimates, a single gradient step is computed for $w_t$. The estimator has been adapted from [1].\n\nAs the functions are weakly convex, the authors show convergence to an $\\epsilon$-stationary point of the Moreau envelope of $F$ at a rate of $\\mathcal{O}(\\epsilon^{-6})$.\n\nThe authors show that both problems can be mapped exactly to Two-way partial AUC (TPAUC) maximization of a parametrized network, even deep networks, with the TCCO problem mapping to a multi-instance learning version. TPAUC is the area under the ROC curve when False Positive rate $\\leq \\beta$ and True Positive Rate $\\geq \\alpha$. Over a set of medical datasets, the authors show that SONX and SONT out-perform baselines for TPAUC maximization as the baselines use poor approximations of TPAUC.\n\n\n\n**References**\n1. Jiang et al 2022. Multi-block-single-probe variance reduced estimator for coupled compositional optimization\n", "questions": "- Is there a lower bound for this problem setting, which can be used to verify if the rates are optimal and cannot be improved?\n- Why is the dependence on $\\frac{n_1}{B_1}$ worse for SONT as compared to SONT? ", "limitations": "Described in Weaknesses", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- **Easy to Implement**: The algorithms are single-loop and use moderately sized batches which makes it easy to implement. Also, the algorithms can also be parallelized over the coordinates $i$.\n- **Better Rates**: In addition to being easy to implement, the algorithms achieve the best possible rates for this class of functions. Existing works obtain similar  or worse rates under an easier problem setting or with multiple loops or using large batches.\n- **Mapping to TPAUC**: The authors describe the TPAUC problem comprehensively and show the exact mapping with the two optimization problems.\n- **Detailed presentation**: The convergence analysis, the mapping to TPAUC and the related works are very detailed which helps in understanding the paper.", "weaknesses": "- **Experimental and Theoretical Baselines do not match**: For theory, the baselines for comparisons are algorithms for simpler problem settings, for instance with smoothness or convexity. For experiments, the baselines for TPAUC maximization are used which do not match the theoretical baselines. It is unclear, if some theoretical baseline can be applied to TPAUC and perform better. This should not be the case ideally but it has not been verified.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer evM3 for the detailed insightful review. Here we would like to address your concerns.\n\n**Q1**: Regarding mismatch between theoretical baselines and experimental baselines. It is unclear, if some theoretical baseline can be applied to TPAUC and perform better. \n\n**Response**: (1) We would like to point out that the baseline SOTAs is a state-of-the-art method for optimizing TPAUC as demonstrated in [39]. (2) The complexity of the baseline SOTAs for TPAUC maximization [39] matches that of the theoretical baseline SOX in Table 1. SOTAs can be considered as an extension of SOX for solving a smoothed surrogate of TPAUC loss [39].  (3) A theoretical  baseline named SOTA for optimizing the same TPAUC formulation as ours has been pointed out in [39] (as discussed in lines 114-117), which reformulates the problem into a min-max problem by leveraging the convexity of the outer function and adopts an existing double-loop algorithm. In comparison, our algorithm is single loop and has the same iteration complexity. We have implemented SOTA and compared the training convergence on the two molecular datasets.  The training convergence results as shown in Figure 3 in the global response demonstrate that our method has competitive and sometimes even faster convergence though our method does not explore the convexity of the outer function.\n\n**Q2**: Is there a lower bound for this problem setting, which can be used to verify if the rates are optimal and cannot be improved?\n\n**Response**: To the best of our knowledge, there is no known lower bound for NSWC FCCO. However, the complexity of our proposed methods matches the best known complexity for solving weakly-convex concave min-max problems. With additional convexity assumption on $f_i$, NSWC FCCO can be rewritten as a weakly-convex concave min-max problem. Thus we consider the complexity of our proposed methods to be state of the art.\n\n\n**Q3**: Why is the dependence on n1/B1 worse for SONT as compared to SONX?\n\n**Response**: The worse dependence on $\\frac{n_1}{B_1}$ is caused by the two layers of block-sampling in SONT. Since TCCO problem is three-level compositional, we apply block-sampling strategy in the estimation of both the 1st inner function $\\{g_i\\}$ and 2nd inner function $\\{h_{i,j}\\}$. This results in an increasing inaccuracy in the overall gradients and function values estimation, and eventually leads to a worse dependence on $\\frac{n_1}{B_1}$.\n\n"}, {"review_id": "kkJyIytbO6", "reviewer": "Reviewer_GoBV", "summary": "The paper considers a class of finite-sum coupled compositional optimization (FCCO) problems and a class of tri-level finite-sum coupled compositional optimization (TCCO) problems. Under the setting of non-smooth weakly-convex FCCO, the paper establishes the complexity of a single-loop algorithm with the tool of Moreau envelop. The algorithm is then extended to solve the non-smooth weekly-convex TCCO. Numerical results on the two-way partial AUC maximization and multi-instance two-way partial AUC maximization are also reported. ", "questions": "Consider the TPAUC problem in Section 5.The corresponding NSWC FCCO problem of the regular setting and the corresponding NSWC TCCO problem for the MIL setting still have convex $f_i$. Could the complexity of the proposed algorithms be improved if the weakly-convex assumption of $f_i$ is replaced by convexity? ", "limitations": "n.n.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "Convergence analysis of an single-loop stochastic algorithm for solving non-smooth weakly-convex FCCO is a nice contribution of the paper. ", "weaknesses": "1. There lacks motivation for considering non-smooth weakly-convex FCCO and TCCO. Some additional applications other than the two-way partial AUC maximization should be provided.  \n\n2. In the nonconvex setting, definitions need to be rigorously given/referred to. For example, $f$ at line 133 can be nonconvex, which definition of \"subgradient\" and \"subdifferential\" are the paper using? There some ways to define a \"variance-reduced estimator\", which definition is the paper using? \n\n3. The experiments just partially support the theoretical results of the paper. Numerical results on the comparison of the evolution of the objective function over time when using the proposed algorithm and other known algorithms for solving one same non-smooth weakly-convex FCCO problem are expected. It would illustrate the importance of the obtained complexity. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer GoBV for the insightful review. Here we would like to address your concerns.\n\n**Q1**: Additional applications other than the two-way partial AUC maximization should be provided.\n\n**Response**:  We would like to provide another important application of NSWC FCCO for regularized group distributionally robust optimization (group DRO), which is useful for addressing distributional shift  [Sagawa et al. 2020].  Consider $N$ groups with different distributions. Each group $k$ has an averaged loss $L_k(w)=\\frac{1}{n_k}\\sum_{t=1}^{n_k}\\ell (f_w(x_t^k),y_t^k)$, where $w$ is the the model parameter and $(x_t^k, y_t^k)$ is a data. For robust optimization, we assign different weights to different groups and form the following robust loss minimization problem:\n$$\n\\min_w \\max_{p\\in \\Omega} \\sum_{k=1}^N p_k L_k(w),\n$$\nwhere $\\Omega\\subset\\Delta$ and $\\Delta$ denotes a simplex. A common choice for $\\Omega$ is $\\Omega=$\\{$p\\in\\Delta, p_i\\leq 1/K$\\} where $K$ is an integer, which yields the so-called CVaR losses (i.e., average of top-K group losses). As a result, the above problem is equivalent to (Curi et al, 2019):\n$$\n\\min_w \\min_{s} F(w,s)=\\frac{1}{K}\\sum_{k=1}^N [L_k(w)-s]_+ + s.\n$$\nWe can map this problem into non-smooth weakly-convex FCCO when the loss function $\\ell(\\cdot,\\cdot)$ is weakly convex in terms of $w$. Compared with solving the min-max problem, solving the above FCCO problem does not involve dealing with the projection onto the constraint $\\Omega$ and avoid expensive sampling as in existing works (Curi et al, 2019). \n\n**Q2**: In the nonconvex setting, definitions of \"subgradient\" and \"subdifferential\" need to be rigorously given/referred to. \n\n**Response**: Thank you for the comments! We will add these definitions into the revision. In particular, the definitions of subgradient and subdifferential follow from the definition 8.3 in [Rockafellar and Wets, 2009] and section 2.2 of [5]. In section 2.2 of [5], properties of subgradients for weakly-convex functions are discussed. For the class of weakly-convex Lipschitz continuous functions, the definition of Clarke subgradients [Theorem 9.61 Rockafellar and Wets, 2009] coincides with definition 8.3 in [Rockafellar and Wets, 2009] [41]. \n\n**Q3**: Which definition of \"variance-reduced estimator\" is the paper using?\n\n**Response**:  The use of the term “variance-reduced estimator” follows from the line of research on variance reduction techniques in the literature of stochastic optimization for machine learning, including SVRG [Johnson and Zhang, 2013], SARAH [Nguyen et al., 2017], SPIDER [Fang et al., 2018], STORM [4], and MSVR [13]. In our context, “variance-reduced estimator” generally refers to the estimation techniques that ensures the average accumulated estimation error of the gradient estimators decays. We will clarify it in the revision. \n\n**Q4**: Numerical results on the comparison of the evolution of the objective function over time when using the proposed algorithm and other known algorithms for solving one same non-smooth weakly-convex FCCO problem are expected. \n\n**Response**: (1) Please note that this is **the first work** that studies and solves non-smooth weakly-convex FCCO problems. Hence, there is no known algorithms in the same style for solving the same non-smooth weakly-convex FCCO problems that we can compare with. (2) The experimental results serve the purpose of demonstrating the usefulness of our algorithms for solving ML problems. In particular, for TPAUC maximization we compared with the state-of-the-art baseline SOTAs [39] in order to illustrate the generalization performance of our algorithms. (3) We did provide experimental results to justify the impact of different algorithmic choices on the convergence. For example, the results in Figure 3 in global response demonstrate that using the MSVR estimator ($\\gamma>0$) gives faster convergence than using the moving average estimator ($\\gamma=0$), which is implied by our theoretical results. (4) To better address your concern, we have implemented a min-max optimization approach for optimizing the same TPAUC loss as ours, which was proposed in the supplement of [39] and named as SOTA. Please note that SOTA leverages the convexity of the outer function $f_i$ and solves the equivalent min-max problem. The training convergence results shown in Figure 3 in the global response demonstrate that our method has competitive and sometimes even faster convergence though our method does not explore the convexity of the outer function.\n\n**Q5**:  Could the complexity of the proposed algorithms be improved if the weakly-convex assumption of $f_i$ is replaced by convexity?\n\n**Response**: It is unclear to us whether the convexity of $f_i$ can help improve the convergence.  To the best of our knowledge, when $f_i$ is convex the problem is equivalent to a weakly-convex concave min-max problem, whose best complexity is also $O(\\epsilon^{-6})$ [20,26,36,38]. Since there is no known lower bound for this problem, we do not know if it is possible to further improve the complexity.\n\n**References**:\n\nYang et al. Two-way partial auc and its properties.Statistical methods in medical research,28(1):184–195,2019.\n\nSagawa et al. Distributionally Robust Neural Networks for Group Shifts: On the Importance of Regularization for Worst-Case Generalization. ICLR, 2020. \n\nCuri et al. Adaptive sampling for stochastic risk-averse learning, 2019.\n\nRockafellar and Wets. Variational analysis, volume 317. Springer Science & Business Media, 2009.\n\nJohnson and Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In NIPS, 2013.\n\nFang et al. Spider: Near-optimal non-convex optimization via stochastic path-integrated differential estimator. In Advances in Neural Information Processing Systems, 2018.\n\nNguyen et al. SARAH: A novel method for machine learning problems using stochastic recursive gradient. In Proc. of the 34th ICML, 2017."}, {"review_id": "Xva5nerOEi", "reviewer": "Reviewer_FiRa", "summary": "This paper addresses the finite-sum coupled compositional optimization (FCCO) scenario, relaxing the requirement of Lipschitz gradient for the involved functions. Instead, they consider weakly convex functions with certain monotonicity conditions. The paper introduces new algorithms and provides oracle complexity guarantees for computing a point with an epsilon-gradient norm relative to the Moreau envelop. The authors also demonstrate the applicability of these methods to AUC maximization tasks.", "questions": "See weaknesses.", "limitations": "Yes.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "It is always beneficial and sometimes nontrivial to extend the algorithm implementation and analytic technique for gradient Lipschitz functions to that of more general weakly convex functions. The authors also demonstrate practical applicability of the proposed new algorithms.", "weaknesses": "Since I'm not acquainted with the FCCO setting, I will concentrate on the broader technical aspects instead.\n\n* L137: I don't get the idea of the \"monotonic property\" of a multivariate mapping f here. What is the \"input\" referring here? Let the function be f: R^n -> R^m. Is the input here referring to a vector in R^n? If so, how can we define the \"monotonicity\" with respect to such a multivariate function? \n\n* The whole development in this paper is built on the weak convexity of F proved in Proposition 4.2 and 4.4. However, the arguments there are not transparent to me. Let me take the proof of Proposition 4.2 for example.\n\n(a) L809 first inequality: Why do we have v'(g(y) - g(x)) \\geq v'( ... )? It seems that the authors assumed v <= 0 here as f is assumed non-increasing in L808 (though the term \"non-increasing\" is not clearly defined in my opinion). However, it is not clear to me why such a \"monotonicity\" of f will promise the nonnegativity of subgradients v. For a smooth function f, the claim (v <= 0) holds trivially. But for a general non-smooth weakly convex function, even with the \"monotonic assumption\", this is nontrivial and a formal proof is required. \n\n(b) L809 third inequality: should L_2C_1 be L_2C_1*sqrt(n), where n is the input dimension of f? Please check. If that is true, then the weak convexity parameter would be depend on the dimension n of the input to f.\n\nMinor: \n\n* L805: should v'(g(x) - g(y)) be v'(g(y) - g(x))?\n* L145: \\epsilon > 0 should be 1 > \\epsilon >= 0.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer FiRa for the detailed and insightful review. We will fix the minor issues in the future revision. Here we would like to address the remaining concerns.\n\n**Q1**. L137: Regarding the \"monotonic property\" of a multivariate mapping $f$. \n\n**Response**: We apologize for this confusion. Here we present a more detailed definition of monotonicity:\n\nConsider a function $f:\\mathbb{R}^d\\to \\mathbb{R}^m$. For simplicity, we write $f=(f_1,\\dots,f_m)$. We say that $f$ is non-decreasing if for each $k=1,\\dots,m$, $f_k:\\mathbb{R}^d\\to \\mathbb{R}$ is non-decreasing with respect to each element in the input. We will add this into the revision. \n\n**Q2**. Regarding the proof of Proposition 4.2, L809 first inequality: why such a \"monotonicity\" of f will promise the nonnegativity of subgradients v?\n\n**Response**: Thank you for raising this question. Here we present an additional proposition to address this issue. Before stating the proposition, we would like to mention the definition of subgradient we used in this work. For the class of weakly-convex Lipschitz continuous functions, the definition of Clarke subgradients [Theorem 9.61 Rockafellar and Wets, 2009] coincides with the definition of subgradient [definition 8.3 in Rockafellar and Wets, 2009] [41]. Since we assume both weak convexity and Lipschitz continuity for functions in our objectives, the definitions mentioned above are considered to be equivalent. \n\nProposition. Consider a Lipschitz continuous function $f:O\\to\\mathbb{R}$ where $O\\subset \\mathbb{R}^d$ is an open set. Assume $f$ to be non-increasing (resp. non-decreasing) with respect to each element in the input, then all subgradients of $f$ are non-positive (resp. non-negative) element-wise.\n\nProof. Let $D$ be the subset of $O$ where $f$ is differentiable. By Theorem 9.60 in [Rockafellar and Wets, 2009], a Lipschitz continuous function $f:O\\to\\mathbb{R}$, where $O\\subset \\mathbb{R}^d$ is an open set, is differentiable almost everywhere, i.e., $D$ is dense in $O$. Then by Theorem 9.61 in [Rockafellar and Wets, 2009], the subdifferential of $f$ at $x$ is defined as\n$$\n    \\partial f(x) = \\text{con} (v | \\exists x_k\\to x \\text{ with } x_k\\in D, \\nabla f(x_k)\\to v),\n$$\nwhere $\\text{con}(\\cdot)$ denotes the convex hull. If we assume that $f$ is non-increasing with respect to each element in the input, then $\\nabla f(x)\\leq 0$ (element-wise) for all differentiable points $x\\in D$. It implies that the all vectors in $(v | \\exists x_k\\to x \\text{ with } x_k\\in D, \\nabla f(x_k)\\to v)$ are non-positive element-wise. Therefore, all subgradients of $f$ are non-positive element-wise. On the other hand, if we assume that $f$ is non-decreasing, one may follow the same argument and conclude that all subgradients of $f$ are non-negative element-wise.\n\nFor functions $f:O\\to\\mathbb{R}^m$ where $O\\subset \\mathbb{R}^d$ is an open set, one may write $f=(f_1,\\dots,f_m)$ and apply the above proposition for each $f_k:O\\to\\mathbb{R}$, $ k=1,\\dots,m$.\n\n\n\n\n**Q3**. In the proof of Proposition 4.2, L809 third inequality: should $L_2C_1$ be $L_2C_1*\\sqrt{d}$, where $d$ is the input dimension of f? Please check. \n\n**Response**: Thank you for pointing this out! You are correct.  The weak convexity parameter of $F$ should involve the input dimension to the outer  functions. The weak convexity constant in Proposition 4.2 should be $\\rho_F= \\sqrt{d_1}\\rho_gC_f+\\rho_f C_g^2$, where $d_1$ is the input dimension of $f_i$. The weak convexity constant in Proposition 4.4 should be $\\rho_F = \\sqrt{d_1}(\\sqrt{d_2}L_hC_g+\\rho_g C_h^2)C_f+\\rho_f C_g^2C_h^2$, where $d_1$ and $d_2$ are the input dimensions of $f_i$ and $g_i$ respectively.\n\n"}]

Author rebuttal:
We thank all the reviewers from their insightful reviews. Please find Figure 3 and Table 5 in the attached pdf file.

Meta-review: The reviewers generally find that the paper contains good contributions. In particular, it provides new results on the FCCO problem in the weakly convex (thus can be both non-convex and non-smooth) setting. When preparing the camera-ready version, please incorporate the reviewers' comments and clarify issues related to technical rigor.
Decision: Accept (poster)