A Near-Optimal Single-Loop Stochastic Algorithm for Convex Finite-Sum Coupled Compositional Optimization
Authors: Bokun Wang
Tianbao Yang
Venue: ICML 2025 poster (2025)
Keywords: Finite-Sum Coupled Compositional Optimization
Primal-Dual Algorithm
Block-Coordinate Algorithm
Primary area: optimization->stochastic

Abstract: This paper studies a class of convex Finite-sum Coupled Compositional Optimization (cFCCO) problems with applications including group distributionally robust optimization (GDRO) and learning with imbalanced data. To better address these problems, we introduce an efficient single-loop primal-dual block-coordinate stochastic algorithm called ALEXR. The algorithm employs block-coordinate stochastic mirror ascent with extrapolation for the dual variable and stochastic proximal gradient descent updates for the primal variable. We establish the convergence rates of ALEXR in both convex and strongly convex cases under smoothness and non-smoothness conditions of involved functions, which not only improve the best rates in previous works on smooth cFCCO problems but also expand the realm of cFCCO for solving more challenging non-smooth problems such as the dual form of GDRO.  Finally, we derive lower complexity bounds, demonstrating the (near-)optimality of ALEXR within a broad class of stochastic algorithms for cFCCO. Experimental results on GDRO and partial Area Under the ROC Curve (pAUC) maximization demonstrate the promising performance of our algorithm.

A Near-Optimal Single-Loop Stochastic Algorithm for Convex Finite-Sum Coupled Compositional Optimization
Bokun Wang' Tianbao Yang'
Abstract
where X' C Rd is convex and closed set, the inner function gi(x)) = E (x; (i) is in expectation form, and the objective function F(x) is convex.
This paper studies a class of convex Finite-sum Coupled Compositional Optimization (cFCCO) problems for empirical X-risk minimization with applications including group distribution- ally robust optimization (GDRO) and learning with imbalanced data. To better address these problems, we introduce an efficient single-loop primal-dual block-coordinate stochastic algorithm called ALEXR. The algorithm employs block- coordinate stochastic mirror ascent with extrapola- tion for the dual variable and stochastic proximal gradient descent updates for the primal variable. We establish the convergence rates of ALEXR in both convex and strongly convex cases under smoothness and non-smoothness conditions of involved functions, which not only improve the best rates in previous works on smooth cFCCO problems but also expand the realm of cFCCO for solving more challenging non-smooth problems such as the dual form of GDRO. Finally, we de- rive lower complexity bounds, demonstrating the (near- Jostimaltt of ALEXR within a broad class of stochastic algorithms for cFCCO. Experimen- tal results on GDRO and partial Area Under the ROC Curve (pAUC) maximization demonstrate the promising performance of our algorithm.
In this paper, we study a special class of convex FCCO problems, termed cFCCO, which has a specific structure: The inner function gi : X E is convex and accessible via stochastic oracles (typically loss function), while the outer function f: R - I is convex and determinis- tic simple function (transformation) that is monotonically non-decreasing! Besides, the regularizer r is also convex. Although the above condition is sufficient but not necessary for the convexity of F, fully exploiting it allows us to design single-loop algorithm that achieves better complexity than previous algorithms and applies non-smooth problems with convergence guarantees. Moreover, we can prove its (near-)optimally by establishing lower complexity bounds.
Notably, the special structure of cFCCO arises in various machine learning applications, including group distribu- tionally robust optimization (GDRO) (Sagawa et al., 2019; Soma et al., 2022; Zhang et al., 2023), sub-population fair- ness (Martinez et al., 2021). partial area under the ROC curve (pAUC) maximization (Zhu et al., 2022), and bipartite ranking (Rudin, 2009). We postpone detailed descriptions of some of these problems to Section 5 and Appendix B.
While several algorithms have been developed to solve the convex FCCO problem in (1) with theoretical guarantees of global convergence (Wang & Yang. 2022; Jiang al., 2022), these methods are limited by critical drawbacks: First, these algorithms only have convergence guarantees under the strong assumption that f. and 9i are both smooth and Lipschitz continuous. Second, their convergence rates have poor dependence on the target optimization error e, batch sizes, and, in the strongly convex case, the condi- tion number. Third, these algorithms rely on nested inner loops where the number of iterations in each loop depends problem-specific constants, increasing the difficulty of implementation.
1. Introduction
We revisit the following regularized finite-sum coupled com- positional optimization problem (Wang & Yang, 2022):
x F(x) = n Σ M(((()) + +r(x), (1)
min F(x), #EX
'Department of Computer Science and Engineering, Texas A&M University, College Station, TX, USA. Correspondence to: Tianbao Yang <tianbao-yana yang @ @tamu.cdu>.
To address these limitations, we leverage the structure of the problem. Using the convex conjugate of fi denoted
Proceedings of the 4nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
!w.It. each coordinate of its input. Note that we only need the monotonicity of f. when is nonlinear.

---

(e for the j-strongly convex problem and O BS&33 for the merely convex problem, where S is the outer batch size and B is the inner batch size. Jiang algorithm MSVR for the A Near-Optimal Single-Loop Stochastic Algorithm for Convex Finite-Sum Coupled Compositional Optimization
by Hr the cFCCO problem can be reformulated (1) into convex-concave min-max problem:
jue ) for strongly convex SCO. When is convex and monotonically non- decreasing and g is convex, Zhang & Lan (2020) reformu- lated the convex SCO problem as a min min-max maa-mmaaaa-------- max problem and proposed the stochastic sequential dual (SSD) method to obtain the optimal O(2) ) rate in the merely convex case and O jue rate in the j-strongly convex and smooth case. They also showed that the O(+) rate is optimal when fi is mon-smooth. even if F is strongly convex. However, these algorithms for SCO are inapplicable to cFCCO. In fact, FCCO introduces challenges beyond those in SCO: both the inner function 9i and the distribution P, in FCCO depend on the outer index i, whereas in SCO & and Ç are mutually inde- pendent and the inner function Eg[g< (xr] does not depend &.
O plas
for merely convex SCO and O
m
+ rlt) }. (2)
min max oEd wEY
E Vi S RT is the i-th block of y. and y = ---1x x...... x C B. This reformulation is motivated by tha primal-dual methods for empirical risk minimization (ERM) (Alacaoglu et al., 2022) and the gen- eral convex-concave min-max optimization problem (Zhang et al., 2024). However, the problem in (2) presents unique challenges: (i) (z)) may be neither linear nor deterministic, unlike that assumed in Alacaoglu et al. (2022); (ii) When n is large, updating the entire dual variable y in each iter- ation as in Zhang et al. (2024) becomes computationally prohibitive, motivating the block-coordinate dual update in our approach.
where y(
Conditional stochastic optimization and FCCO. Hu et al. (2020) studied a more general class of problems called conditional stochastic optimization: gingex x F(x) == (T<sss E)])] They proposed biased SGD (BSGD) with large batch sizes. For convex and smooth F. BSGD re- quires ( iterations and large batch size of B O per iteration to find an e-accurate solution. For p-strongly convex F, BSGD requires O( ((pre) iterations and large batch size of B = ( per iteration to find an e-cccuraee solu- tion. For the FCCO problem with convex F, Wang & Yang (2022) used the moving-average estimator and the restarting trick to find e-accurate solution with only O(1) batch size per iteration. In particular, restarted SOX has an iteration complexity of O (010((8:
Our contributions can be summarized as follows:
We propose a primal-dual block-coordinate stochastic algorithm named ALEXR to efficiently solve the cFCCO problems, which only requires (11) batch size per iteration.
both merely and strongly convex cases, the iteration complexities of ALEXR improve upon the iteration com- plexities in previous works (Wang & Yang, 2022; Jiang et al., 2022) on cFCCO problems with smooth fi and 9i (See Table 1 for a detailed comparison). Besides, we also provide the convergence analysis of ALEXR for cFCCO problems with non-smooth f. and gi in convex and strongly convex cases.
For cFCCO problems with smooth and non-smooth f., we prove lower complexity bounds for an abstract first-order update scheme, which covers our ALEXR and previous al- gorithms as special cases. These lower bounds demonstrate the near-optimality of our proposed algorithm.
et al. (2022) proposed a variance- that has improved iteration complexities O p-strongly convex problem and O Sv for the convex problem. However, the theoretical guarantees of MSVR have several limitations such as poor dependence on the batch size B, reliance on restrictive assumptions, and subop- timality for the u-strongly cFCCO problem with smooth outer function fs (as we will demonstrate in Section 4).
n ( Sy/Bue
2. Related Work
The cFCCO problem in (1) is related to several well-studied optimization problems. In Appendix A, we discuss the literature related to the min-max reformulation in (2).
Applications. FCCO serves as the algorithmic framework for optimizing a broad range of risk functions coined as empirical X-risk minimization (Yang, 2022). It has been applied to many machine learning problems, including opti- mizing listwise losses for learning to rank (Qiu et al., 2022), optimizing partial area under the ROC curve (pAUC) for imbalanced data classification (Zhu et al., 2022), group DRO (Hu et al., 2023b) and optimizing global contrastive losses for self-supervised learning (Yuan et al., 2022; Qiu et al., 2023). The proposed algorithm ALEXR for cFCCO is applicable to PAUC maximization and group DRO.
Convex Stochastic Compositional Optimization. Sev- eral papers have studied the convex stochastic compo- sitional optimization (SCO) problem millaxx F(x) := Belfe (E<(9(())) where & and ( are mutually independent. When F is merely convex and f is smooth, the SCGD al- gorithm in Wang et al. (2017a) requires an O iterations to find an Lout s.t. ([F(roa)) min, F(x) S e. When F is p-strongly convex with unique minimizer x., SCGD I requires O( (....s))) iterations to make " || - 11. S c. Further exploiting the smoothness of gç. Wang et al. (2017b) proposed ASC-PG, which improves the convergence rate to
2

---

A Near-Optimal Single-Loop Stochastic Algorithm for Convex Finite-Sum Coupled Compositional Optimization
Table 1. Comparison of iteration complexities to achieve e-optimal solution of (1) in terms of [B[F (Toa)) - F(x.)) S in the merely convex case and / ||ou 2-11 S in the u-strongly convex case, where Zou is the output of each algorithm. Ô hides poly (1e() factors. S denotes the size of a batch S C [r] and B denotes the size of batch B, sampled from P. for each i E S. In the "Monotonicity" column, t means the function is monotonically -ecceacc... "N/A" means not applicable not available. The gray parts are
implications of Thcorems 2 and 3.
Method
Iteration Complexity
Inner Batch Size B
Outer Batch Size 9
Loops
Smoothness
Monotonicity
Convexity!
Strongly Convex
Merely Convex
BSGD (Hu et ol., 2020)
O (1)
(
((1)
Single
ft.
None
F
(())
O(1)
Single
None
F
SOX-Boost
0 0
(T57)
0(1)
0(1)
Double
None
F
(Wang& & Yang, 2022)
SOX
N/A"
0(1)
0(1)
Single
f1.9
fc 1
(Wang& & Yang, 2023)
MSVR
(Jiang al., 2022)
0 2r
VD
0(1)
0(1)
Duuble
None
F
Ô max { jurt nuzz w3r)
(max
gg 2. n
0(1)
0(1)
Single
f.
set
Theorem (i)
ALEXR (This Work)
Ô max { [ RSr Theorem (ii)
(max) T5S B)
0(1)
0(1)
Single
f.
f.t
(maxf g:2. ng.a 1) Theorem O (uax) 11. 7557
0 [maxxl Zे. B37 1)²
0(1)
0(1)
Single
fct
(maxl L. xr.r)) ))
0(1)
0(1)
Single
None
f.1 fu
Theorem
The sufficient condition (convexity fi. r monotonicity f for the convexity
met applications interest described Section 5 and Appendix
The unalysis the merely convex case in Wang & Yang (2023) under weaker convergence measure that cunnot be converted to the objective gop.
As shows in our lower complexity bound in Section 4, strong convesity does not yield faster rate due the compositional structure when the outer function, f. is non-smooth. In Zhung
& Lan (2020), a similar result has been established for convex stochastic compositional optimization.
3. Algorithm and Convergence Analysis
Convex conexce problem (2) with a convex and compact Y = V1 x .... x Yn. Note that f. of all applications in Section 5 and Appendix B satisfy the assumption above.
Notations. For vector y E Ram, we use y E I to represent the i-th coordinate (block) of y, i.e., y = (o(",... (()) We denote the Bregman divergence as-
Although the smoothness of fi and gi are not neces- sary in our work, incorporating them leads to better con- vergence rates. We say that 9; X' + R" is Lg" smooth if it is differentiable and there exists Lg > O such that (1g) - (1(2)) - (gi(=2) - x2))l. S Ly
sociated with v/ : Rm + IR for any u,v E RT as (v,(u, = (u) - ()(()) (v)(() (u 1 v) and define Up (v1. = >E Un (vl" U222
(3) for 3/ E Rum. For a function (x) = Bg.-e, (g(: (.). we define the stochas- tic estimator based on the mini-batch B, as (x; == B. EGEB, (z Gt). Let X be a normed vector space with 1122. For each i E [ni]. let V; C " be normed vector space with a general norm |I-|| and ||-Ile be its dual norm. See Table 3 in the appendix for the full list of notations.
2 || 22112- Vz1, z2 E Xx; Besides, we say that fi RT + R is -mooth if it is differentiable and there exists
Lf > 0 such that ( (u2) (V f1(2)), u1 u2) S
4 1l11- 221... Vu,, u2 E 2/
Lastly, we assume that the variances of the zeroth-order and first-order stochastic oracles are bounded.
We make the following assumptions throughout the paper. Assumption 1. The domain X C Rdd in (1) is a convex and closed set. Besides, the regularizatoin term r is proper, lower-semicontinuous, and yr-covvx on X, 1 2 O.
Assumption 4. There exists finite og of, 82 such that
Be, 119 - gi(a;; S où
Assumption 2. 9i is convex. Besides, there exists C, > O such that [z) - (x(x)) S C,2 || - x' x'1lg. Vx, x' E X. Assumption 3. fx m + R is convex. Besides, there exists Cj > 0 such that [f) fa(x() S Cy ||u 1 u' Il. Yu, u' E Jr. If g, is nonlinear, we assume that fi is mono- tonically non non-decreasing w.r.t. each coordinate of its input.
E, [[](((())] - Lo((2: 4)) 11pp S of
[1)] gr,) 1 Σ [d(((=) (0) 1 - 8",
for any x E X, g) E (g)(()), and y y.
Assumption 3 implies that [I < Cy for all (0) E V and )/+ C Rim Vi E [n]. Thus, (1) is equivalent to the
Under Assumptions 3. the existence of 62 is ensured since n - [od g(و [E)=))(()) y s C2Cs
1
3

---

A Near-Optimal Single-Loop Stochastic Algorithm for Convex Finite-Sum Coupled Compositional Optimization
Algorithm 1 ALEXR
yi (8)
= Vii(u:))
1: Initialize: zo E X' C R2, 1/0 EY C R
2: fort= 1rrt=0,1, 0,
0......,,TT T do
9t
if E S O.W.
11+1
1+1
1+7
(4)
3: Sample a batch St C (1.....,n.. m). Stll = S
4: for each i E St do
5: Sample batches B,Sh B of size-B from I.:
For a non-smooth outer function fi, we can choose th to be the quadratic function v/x(.) = 1--12- This choice requires that the proximal mapping of J can be efficiently computed, a condition that holds for many simple func- tions (See Chapters 4 and 6 in Beck, 2017), e.g., the non- smooth function fi(-) = + max(-,0) in the GDRO problem with Conditional Value at Risk (CVaR) divergence and the PAUC maximization problem described in Section 5.
6: Compute stochastic estimator g." = gi( BB +
O(gi (I+; b8()) - gi BB
7:
Update the i-th block of the dual variable ye+1
(1)
arg max (uot)) (1) (v) - TU (v,VV {)
8:
end for
9:
For each i E St. Vit1 = yt
(6)
10:
Compute the stochastic gradient estimator G.
S &Eies, (x( 1T ye41 based on the stochastic
Then, ALEXR updates the primal variable x based on stochastic proximal gradient descent update, where
partial gradient ( B(O) E 0g:(2z; )
11: Fe+1 arg min (Gr, z) +r(z)+ || xxl12)
G2 is a (sub)gradient estimator of the coupling term (14191(31) using an independent mini-batch B(()
1 E. (i)
12: end for
3.2. Relation to Existing Algorithms
3.1. A Primal-Dual MloodCCood Algorithm
Relation to SOX (Wang & Yang. 2022). By setting O. 4 = fe in ALEXR, the dual update and the gradient esti- mator become similar to that used in SOX. In particular, the update of u 2 in (3) becomes the moving average estimator, i.e., u (1 -))u + (g B("),, ) where 7 I+ Hence, the updates of ALEXR with @ = 0, v, f/ reduces to SOX without gradient momentum, whose convergence is analyzed in Wang & Yang (2023) for strongly convex FCCO. However, establishing its convergence guarantee for the merely convex problem is still an open problem.
We propose a stochastic algorithm, ALEXR (refer to Algo- rithm 1), to efficiently solve the cFCCO problem defined in (I) by leveraging its reformulation in (2). Due to the structure of (1), ALEXR begins each iteration by sampling mini-batch S, of size S from (1,...,n} n and, for each i E St, sampling two i.ddd mini-batches Bi, BJ of size B from IP..
(2)
Since stochastic oracles 9, (.) are only available for those blocks i E St, ALEXR employs a block-coordinate stochas- tic update for the dual variable y, which occurs between line 5 and line 9 in Algorithm For a sampled block i e St, the update of ()) is based on the extrapolated stochastic gradient estimator gf") of the linear coupling term y(0) g, (I²) in Step with E [0, 1], and a mirror-pros prox mapping w.r.t. to some strongly convex distance-generating function vi; To ensure the proximal mapping in line of Algorithm can be efficiently computed, it is crucial to carefully select w/;:
Relation to MSVR (Jiang et al., 2022). By setting th; St there is only subtle difference between MSVR and ALEXR. which gives ALEXR an advantage. In particu- lar, the update of u in (3) of ALEXR can be written as (6)
(6)
w = 7)-7)u(" (5) + 79: (x,; B( + (1x;;
( (itt)1:B())) B(2)) with 7 = + < 1, vi E S. This esti- mator is similar to the one used in MSVR except that the scaling factor before the correction term (gx ((²))
R-S +1 Y, which (1r-1::: B("))) in MSVR is 5 = 5(1
For any smooth outer function fú, we can select v/; = f(- (4) E -fff ))) we can show that (see Lemma 1 in
could be much larger than 1. Notably, several existing works have reported better empirical performance using a y less than one (Jiang et al., 2022; Hu et al., 2023a;b), which is consistent with our setting and theory. Another difference between ALEXR and MSVR is that ALEXR does not use the variance-redductoon technique (Cutkosky & Orabona, 2019) to compute the gradient estimator of the primal variable, which demands more memory and compu- tational costs, albeit resulting in worse oracle complexity compared to that of ALEXR for cFCCO.
For ut Appendix C):
(8)
(2) + 9r
(0) 1/+1 = v/((()))
(
Tu
Vi S, (3)
1 1+7
If Ji is a Legendre-type (proper, closed, strictly convex, and essentially smooth) function, ALEXR has a primal-only implementation similar to SOX (Wang& & Yang, 2022) and MSVR (Jiang et al., 2022). To be specific, we can derive the following equivalent update of u sequence such that
Relation to SAPD (Zhang et al., 2024). When n = 1, the reformulation in (2) is a convex-concave saddle point prob-
4

---

A Near-Optimal Single-Loop Stochastic Algorithm for Convex Finite-Sum Coupled Compositional Optimization
lem, where SAPD is a representative stochastic algorithm. Both SAPD and ALEXR use an extrapolated estimator to update the dual variable y. The key difference is that SAPD updates the entire y without assuming block separability of the dual domain, whereas ALEXR leverages this property to update only y for those sampled blocks E St. This design addresses the challenge of cFCCO: when n is large, sampling from P3 and computing stochastic gradient estima- tor for each E [nx] is computationally expensive. Although ALEXR can be viewed as a block-coordinate variant of SAPD, its convergence analysis introduces several new chal- lenges that are not present in the analysis of SAPD: (i) The block-coordinate updates of ALEXR lead to new challenges in convergence analysis, such as the dependence issue dis- cussed in Section 3.3; (ii) ALEXR provides more flexibility to choose distance- gennrraing functions 4) other than the quadratic one in SAPD for the dual step; (iii) ALEXR and its convergence guarantees also apply to non-smooth problems, whereas SAPD focuses on smooth problems.
we choose Up De) (y We) as part of the potential function. It is worth noting that the issue above does not arise in the analysis of min-max optimization algorithms without coork-co updates such as that in Zhang et al. (2024), because ÿt-1 = yt+1 if the whole y is updated.
3.3.1. SMOOTH AND STRONGLY CONVEX CASE
When the outer function f. is smooth, we show that ALEXR can achieve the fast O(e-t) rate for a strongly convex cFCCO problem. min-max problem in (2) is stoongly-oovvex-sttonngyy concave (SCSC) and a unique saddle point (I., v.) ex- ists for the unique minimizer I. of the original prob- lem in (I), We define that G. is the o-algebra generated by {Ba, So...., ......,...I.. S. B.} and F, is the o-algebra generated by (Bo,Su.... Su...., B, St). Note that Gr c F. and y is Fe-measurable. Since Fa, are inde- pendent of the randomness in the algorithm, we have
Under this setting, the
B(Up(V,) Bo+1) [.]] = - (v Ic+1) + n n- S
Up (ye, vt).
3.3. Convergence Analysis
For the convenience of analyzing the block-coordinate up- dates of the dual variable y, we define an auxiliary sequence:
= y. into (6) can es- Plug the equation above and x J. yy tablish the contraction needed for potentialffunction-be convergence analysis. This leads to the following results, which holds for ALEXR with any strongly convex vi, in- cluding (hx()) = 11ll 11 and t); = f;" for a smooth fi.
arg max { Dgg (() - (v. (5)
Theorem 1. Suppose that Assumptions 1, 2, 3, 4 hold with / > 0 and L smoohh outer function ft.
where St- - (g! ..... St Vi [n]. Note that only g. for those blocks i E S, are computed in the 1-th iteration of Algorithm while / for those & S, are virtual. The reason we introduce the sequence (we)22 is to decouple the dependence between y/+1 and S.. Besides, for the options of the listed in Section 3.1, we have y (u, 2 pU (u, 2) for some p 2 0 and any u, E }ı: For example, p = 1 for a smooth fi and d/-- = f while
(i) g: is smooth, ALEXR with vi = 1-0 T n11-0] o7
8
and 0 1 O(e) makes 5E - 21 S e in
Ó(max{ uS* 4B* B9 1) iterations;
* (ii) If is non-smooth, ALEXR with the same setting n, T, and 0 = 1- Oc) leads to iteration complexity Ó(max{ 1, n BS )1))
0 for a non-smooth ft.
We define the objective function in (2) to be L(x, y) = 1 E (xx (())) - S (v( + r(x). After the 1-th iter-
Remark 1. On strongly convex cFCCO with smooth fi and 9i. ALEXR achieves Ó(max { pse: TBe BSe }) itera- tion complexity, which improves upon the previously best- known O uV ) achieved by MSVR (Jiang et al., 2022). Besides, also provide the oracle complexity of ALEXR when the inner function gi is non-smooth, which is absent in previous work.
n
ation of ALEXR, for any x E X,y y E Y' we can obtain
n | T1+1
12 + a TtU 1o+1) S
(6)
1
|| xel12 + (v. (I(x441,8) - [xx, M++1))
2
+ Rs
where RS captures the remaining terms in (15). Notably, the term L(z++1.v) L(x, M++1) can be converted into the objective gap F( - F(x) in ergodic sense. In standard convergence analysis based on potential func- tions (Bansal& & Gupta, 2019), all terms in the potential function are expected to be non-expansive after a single iteration. However, it is not immediately clear whether the shaded part in (6) is non-expansive, regardless of whether
3.3.2. CONVEX CASE WITH POSSIBLY NON-SMOOTH fo
Now we shift our focus to the cFCCO problem with possibly non-smooth outer function fi. In this case, we require d/2 |||l -
To derive bound of the objective gap E[F(aT) - F(x.) )}
TT = 1 ETs It. we will plug r = 2,, and y = o7 e arg max (v (((r)) - ft)) E (f(()))))) into (6).
5

---

A Near-Optimal Single-Loop Stochastic Algorithm for Convex Finite-Sum Coupled Compositional Optimization
Unfortunately, the technique outlined in Section 3.3.1 does not address this issue because ür also depends on St. We address this issue by introducing multiple virtual sequences to transform the shaded part in (6) into telescoping sums of several potential functions of these virtual sequences (See Lemma 9), a technique we extended from Nemirovski et al. (2009); Juditsky et al. (2011); Alacaoglu et al. (2022).
rithms (Zhang et al., 2024; Wang & Yang, 2022; Jiang et al., 2022)².
The abstract scheme starts with the initial spaces Xo- = Go = {0u}, Do = {O,}, 9o = {0m} and progresses as follows in the t-th iteration: First, it samples a batch S, C [m] and G ? i.i.d from IP,, For those i E S..
9 = dr (2) + span (9: ((2) | E
When gi is non-smooth, ALEXR achieves the same conver- gence rate for 0 {0, 1), but choosing 0 saves S inner function evaluations at 11-11-
Dit = w + span (MP(0: 9:) I de E D 9 E 2
Theorem 2. Suppose Assumptions 1, 2, 3, 4 hold and 9. is non-smooth. ALEXR with d/ = l| 12 8 = 0, 7 = O(2), and T = (
where "+" refers to the Minkowski sum, 0
2) are
the i-th slices of the spaces ge, tr, and MP MP 9:) = arg m - f (v) - TU (v, 0.) For those i E S., the corresponding slices remain unchanged, i.e,, 01+1
1 can make (T)
Be
) iterations, where 0g = (UT, uo]] = Σx_ U. (UT .yo )²
F (x.)) )1 S c in O(max(1, (1, BB
(0) , Di6 26 The spaces 6r X, are updated as
When 9i is smooth, setting the parameter 0 = 1 leverages the extrapolation term and yields better convergence rate.
G.+1 = G, + (pan 9) | l E 2, E Dc+th
*t+1 = X, + span (Q G) & E &, G 6.41)
Theorem 3. Suppose Assumptions 1, 2. 3, 4 hold and gi is smooth. ALEXR with the = Ill 12 0 = 1, 7 = O and T = =O+)) can make E[F(ZT) - F(I.]] S E in 0(maxt 1 a
where we define G(ă, 9) = Eies, VV. (1 )1 g() and ( = arg min (x [x + r(z) + 1| i (2
3. BS ) iterations, where
For the problem with smooth outer function fi, we con- struct a hard instance of (1) by setting fi to a variant of the Huber function and inner function Ji to a linear func- tion with some Bernoulli distributed noise. For the problem with non-smooth outer function fi. we construct hard in- stance by replacing the smooth Huber function f; with monotonically non-decragiing hinge function. Details of the constructions and the proof are provided in Appendix E.
03 = (UT, y0)] = E.= ElU (o )))
Remark 2. The radius 22 (n)) in the worst case, but it can be much smaller than O(n) when ÿT and yo hibit some sparsity structure (an example is provided in Appendix F.I).
We compare the above results with that of MSVR. For non-smooth ft. MSVR is not applicable. Theorem 2 im- plies that ALEXR can achieve the ( = }) it- eration complexity for the merely convex problem even ft is non-smooth. Furthermore, Theorem also indicates that when both fa and gi are smooth, ALEXR achieves the Omax { 522. B$2)) }) iteration complexity for the merely convex problem, improving upon the O O <BS==) iteration complexity in (Jiang et al., 2022) of the double-loop algo- rithm MSVR.
The construction of the noise and the hinge function fi for the non-smooth problem is adapted from Zhang & Lan (2020). Our contributions are twofold: First, we design an abstract scheme that supports block-coordinate updates and characterize how the optimal oracle complexity depends on the total number of blocks nı Second, we also construct hard instance to prove the lower bound for the strongly con- vex cFCCO problem with a smooth outer function fi, which highlights the optimalti of our ALEXR in this setting and its significant improvement over previous algorithms.
When fi is non-smooth, the strong convexity of the objec- tive does not result in a better rate compared to the merely convex case, as we will demonstrate in Section 4.
Theorem 4. For the fu-strongly cFCCO problem in (1) with a smooth outer function fo any algorithm within the abstract scheme described above requires at least 2mmax
4. Lower Complexity Bounds
g f.1 1)) oracles calls to find an F. such that
- S 6; Besides, For the cFCCO problem in (1) (whether merely convex or strongly convex) with a non- smooth outer function fú, any algorithu within the abstract scheme described above requires at least Dine oracles calls to find an such that FF -
In the previous section, we introduced the ALEXR algo- rithm and established the upper bounds of its iteration com- plexity and oracle complexity (i.e., the number of calls of stochastic oracles). In order to examine whether these bounds of ALEXR are (near-)optimal for the problem in (I), we examine the lower bounds by constructing "hard" in- stances of 1 for the following abstract first-order update scheme that subsumes ALEXR as well as previous algo-
( F(x S.c.
'It covers SOX (Wang & Yang. 2022) and MSVR (Jiang et al., 2022) when 1h = f². Besides, it also covers SAPD (Zhang et al.,
2024) when = n and s/: = 11-11-
6

---

A Near-Optimal Single-Loop Stochastic Algorithm for Convex Finite-Sum Coupled Compositional Optimization
Theorem 4 demonstrates that ALEXR is near-optimal in both cases. Furthermore, it also shows that the upper bounds established in Theorem I and Theorem 3 are tight.
their paper). When R((w) is convex, can solve the problem in (8) by viewing it cFCCO problem with convex outer function fi(-) XΦ (-) and an inner function gx) = (R (w) c) / that is jointly convex to z (w, c). In Appendix F, we compare the convergence rates and per- iteration costs of ALEXR with previous GDRO algorithms.
5. Experiments
In this section, we present two main applications of the eFCCO problem: Group Distributionally Robust Optimiza- tion (GDRO) and Partial AUC Maximization (pAUC) with restricted True Positive Rate (TPR). We then evaluate the empirical performance of our proposed ALEXR algorithm against previous baselines in these applications. More appli- cations are discussed in Appendix B while additional details and experimental results can be found in Appendix G.
First, we empirically compare our proposed ALEXR with baseline methods on the GDRO problem in (7) with the CVaR divergence for the binary classification task. We con- sider the linear model wo and the logistic loss (ww;)
Datasets. We perform experiments on two datasets: a tab- ular dataset Adult (Becker & Kohavi, 1996) and an image dataset CelebA (Liu et al., 2015). For the Adult dataset, we construct 83 groups according to features such as race and the task is predict the income. For the CelebA dataset, we constructed 160 groups based on binary attributes such as sex and the task is to determine whether person possesses blonde hair. Please see Appendix G.I for more details.
5.1. Group Distributionally Robust Optimization
The Group Distributionally Robust Optimization (GDRO) framework aims to train machine learning models that are robust across predefined subgroups (Sagawa et al., 2019). Suppose that there are n predefined groups and the data dis- tribution of the i-th group is P,. The ø-divergence penalized GDRO can be formulated as
Baselines. We compare ALEXR with previous algorithms on the FCCO problem including BSGD (Hu et al., 2020), SOX (Wang & Yang. 2022), and MSVR (Jiang et al., 2022y²,
Besides, we also compare ALEXR with previous algorithms for the GDRO problem, which include OOA (Sagawa et al., 2019) and SGD with up-weighting (SGD-UW) (Buda et al., 2018). OOA was originally proposed for the GDRO prob- lem without a penalty term and we extend it to the CVaR- penalized GDRO based on an efficient algorithm for pro- jection onto the capped simplex (Lim Wright, 2016), where we use the implementation in Blondel (2019). To show the benefit of GDRO, we also include SGD based on empirical risk minimization (ERM) as a baseline, which neglects the group information. We do not compare with some other GDRO algorithms (Zhang et al., 2023; Soma et al., 2022) that do not support group sampling or do not apply to the CCVRR-penaliie problem. Moreover, algo- rithms for distributionally robust optimization (DRO) (Levy et al., 2020; Meng & Gower, 2023) are not applicable to the GDRO problem due to the stochastic oracles of per-group risk R2 (w). We execute all algorithms for 5 runs with dif- ferent random seeds. For a fair comparison, each algorithm samples 64 data points in each iteration. For SGD, these data points are sampled from the entire training dataset, whereas for other algorithms, we sample 8 groups and 8 data points per group. We tune the step sizes of all algo- rithms in the range {2, 5, 10) x 106-3,-2.-1, For SOX and MSVR, we also tune the momentum parameter in the range {0.1, 0.5, 0.9). For ALEXR, we choose the extrapo- lation parameter 0 E {0.1, 1.0} and (-x()) = {.) For all algorithms, we choose the weight decay parameter 0.05 on
A (() - - oomm)) }} n
min max rEAR
+ r(w), (7)
where A. is the (n - 1)-dmmensinnal probability simplex, w is the model parameter, R;(w) == E.-,, [l(w; 2)] is the risk of the i-th group, and Φ : RR, + R [U (11 = O.
Prior work (Sagawa et al., 2019; Zhang et al., 2023) dis- carded the g-divergence penalty, i.e., À = 0 in (7), and con- sider the problem min,, max4e[m] (w), which minimizes the risk of the worst group. However, the model trained through worst-group risk minimization may be vacuous if the worst group an outlier. Moreover, the sizes of groups may follow long-tailed distribution such that multiple rare groups exist. To resolve these issues, we choose À > 0 and consider the penalized GDRO problem with CVaR diver- gence o= = -o. or x2 diveergeee @(t)= = (t 1)??
The challenges of directly solving (7) using stochastic min- max algorithms lie in estimating the stochastic gradient of q and controlling its variance when n is large (Zhang et al., 2023). Alternatively, we can transform the above problem into an equivalent problem by duality (Levy et al., 2020):
(w) c) X + +c+ r(w),
min W. n
+(w),
where o² is monotonically non-decreasing, e.g., di (w) = 1 [()+ for CVaR divergence and (u) = 1 [ - for
x² divverggee The dual formulation in (8) is recognized as a difficult open problem in Sagawa et al. (2019) due
MMSVR was designed for FCCO problems with smooth f.. We replace the gradient V.A in MSVR with a subgradient to make it applicable to this GDRO problem with a non- smothh f.
to the biased stochastic estimator (refer to footnote in
7

---

A Near-Optimal Single-Loop Stochastic Algorithm for Convex Finite-Sum Coupled Compositional Optimization
0.75
Adult (a=0.1)
0.73
Adult (a=0.15)
CelebA (e=0.1)
0.50
CalebA (c=0.15)
0.34
2000
201
0.72
0.54
2500 NGAR
A,50
Mork
0.72
0.52
0.00
0.43
0.71
0.50
0.64
0.70
0.00
0.60
0.40
0.45
0.00
0:46
0.4
1.0
0.7
0.4
#Oracles
@Oracles
@Oracles
Tel.
aOracles
Figure 1. GDRO loss curves evaluated on the validation datasets during the training process with = 0.1 and 0.15.
Table 2. Test accuracy (%) on the (orst-(an) groups with a = 0.1 and 0.15. The best accuracy is highlighted in black.
Adult
CelebA
Mcan
Methods
0.1
0.15
0.1
0.15
SGD
0.71+0.20
1.87+0.25
2.75+0.08
4.89-0.10
2.56
SGD-UW
23.70+1.01
26.26+1.066
73.70-0.13
74.18+0..3
49.46
O0A
51.46112.21
54.12:1..04
66.40=6.37
73.43 0.79
61.35
BSGD
55.8110.70
58.5811.61
75.30=0.27
76.1610.12
66.46
SOX
56.34
58.36110.44
75.04=0.20
76.10=1.300
66.46
MSVR
47.7811.06
49.4910.95
75.34=0.28
76.17=0.09
62.20
ALEXR
56.58:10.69
58.52
7.07
76.29
66.80
the Adult dataset and 0.1 on the CelebA dataset.
notes the prediction score for data dg. Additionally, S1, [1, k] the bottom-k positive data based on the prediction scores. In particular, is convex and monotonically non-decreasing function, ensuring the consistency of the surrogate objec- tive (Gao & Zhou, 2015). Based on the duality (Levy et al., 2020), the problem (9) is equivalent to
Results. In Table 2, we report test accuracy for all algo- rithms on the worst-(an) groups with a = 0.1 and 0.15. Besides, we plot the validation loss curves for FCCO algo- rithms sharing the same objective function (8) in Figure First, we notice that the vanilla SGD performs poorly on the worst-(an) groups' data. While the up-weighting trick of- fers some improvement for SGD, its effectiveness still falls short of Group DRO algorithms. Among GDRO algorithms, our proposed ALEXX exhibits faster convergence compared to baseline methods. ALEXR also achieves superior test accuracy compared to baseline methods in most cases.
min W.SER n (1
Σ a:ES
Σ
L(w;
a;ES
+ 8,
which a cFCCO problem with f. = (-)+ and g, s) n=_ Eojes L(w; a,, 0z) 8 jointly convex to (w, 8).
5.2. Partial AUC Maximization with Restricted TPR
In our experiments, we consider linear prediction model w and two different lower bounds a of TPR: 0.5 and 0.75.
The Area Under the ROC Curve (AUC) is a more informa- tive metric than accuracy for assessing the performance of binary classifiers in the context of imbalanced data (Yang & Ying, 2022). In scenarios influenced by diagnostic or monetary considerations, the primary objective may be to maximize the partial AUC (pAUC) with specified lower bound for the true positive rate (TPR). As shown in Zhu et al. (2022), a surrogate objective for maximizing pAUC with restricted TPR is formulated as
Baselines. Apart from BSGD, SOX, and MSVR, also include SGD with over-sampling for the cross-entropy (CE) loss and the SOTA algorithm (Zhu et al., 2022) baselines. In each iteration, each algorithm samples an equal number of positive and negative data points (16 for each), which is based on the convergence theory in Zhu et al. (2022).
Datasets. We perform experiments on four datasets: Cov- type, Cardiomegaly, Lung- mass, and Higgs. The Covtype and Higgs datasets are from the LibSVM repository (Chang & Lin, 201 1). To create imbalanced datasets, we randomly remove 99.5% positive data from Covtype and 99, 99.9% posi- tive data from Higgs. For Covtype, we randomly allocate 75% of the data for training and 25% for validation. For Higgs, we randomly select 500,000 data points for vali-
min WER" T4
Σ
Σ
L(w; ai a5),
(9)
aES 11,4 (1 (1-a)) RyES
Here S, S_ are the sets of positive/negaaive data, w refers to the model and L(w; a, a,) = (ay) - Aw (a:)) repre- sents a continuous pairwise surrogate loss, where hag (a;) de-
8

---

A Near-Optimal Single-Loop Stochastic Algorithm for Convex Finite-Sum Coupled Compositional Optimization
Coviype (TPR: 0.5)
Covtype (TPR 0.75)
Higgs (TPR > 0.5)
Higgs (TPR 0.75)
0.73
0.36
0.40
0.31
0.70
0.33
0.69
0.37
0.42
504
50%
509
50%
0.85
0.42
0.29
0.5
0.46
0660
0.28
2003
0.04
0.40
0.27
#Oracies
106
#Oracles
10k
#Oractes
104
#Oracies
104
Cardiomegaly (TPR (TPR:00) 0.5)
Cardiomegaly (TPR:0077)
Lung-mass (TPR:003)
Lung-mass (TPR 1PPR-0.25
0.64
0.52
0.38
0.22
0.51
0.63
0.50
0.20
0.622
0.99
0.30
0.00
M. 6540
0.35
SOX
500
HOA 54T4
0.17
0.50
0.0
0.5
1.0
3.5
2.0
7.5
0.45
0.0
0.5
1.0
3.5
2.0
2,5
0.0
0.5
1.0
3.5
200
7.5
0.
0.5
1.0
7.5
2.0
25
#Oracles
#Oracles
#Oracles
Figure 2. Partial AUC evaluated on the validation datasets during the training process under TPR2 0.5 and TPR2 0.75.
dation and the rest as training data. Cardiomegaly and Lung-mas mass are two imbalanced datasets that share the same collection of Chest X-ray images and different label annota- tions from the MedMNIST repository (Yang et al., 2023), where we use the default splits. We vectorize each 28 28 image in Cardiomegaly/LLun saroommmeglyyLL--mmaaass mass datasets as a data point. Statistics of datasets are listed in Table 5 of the appendix.
Acknowledgments
We are deeply grateful to Guanghui Lan for his invaluable feedback on this paper. We are also thankful to Stephen J. Wright for bringing the analysis of the duality gap for PureCD to attention. We thank Guanghui Wang for the initial discussion of the problem. We also thank anony- mous reviewers for their comments. BW and TY were par- tially supported by by National Science Foundation Award #2306572 and #2147253.
Results. In Figure 2, we compare the PAUC curves dur- ing training. First, the results suggest that optimizing the surrogate loss in (9) outperforms optimizing the CE loss for maximizing pAUC with restricted TPR. Moreover, ALEXR demonstrates overall superior performance when compared to other basclines including the SOTA algorithm specifically designed for PAUC maximization.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.
6. Conclusion and Discussion
In this paper, we study a class of convex FCCO problems, called cFCCO, via its min-max reformulation (2). We pro- pose a single-loop primal-dual block-coordinate stochastic algorithm called ALEXR, which achieves improved iter- ation complexities compared to previous works on both merely and strongly convex eFCCO problems with smooth f and 9:- We also establish the iteration complexities of ALEXR when either Ji or yi is non-smooth. Furthermore, we present lower complexity bounds to show that the con- vergence rate of ALEXR is npar-optimal among first-order stochastic methods for cFCCO problems. Finally, we note that it remains an open problem to prove similar complexi- ties as in this work for cFCCO with concave outer functions fi such as the logarithmic function, which has broad appli- cations in machine learning.
References
Agarwal, A., Wainwright, M. J., Bartlett, P., and Raviku- mar, P. Information-thheretii lower bounds on the oracle complexity of convex optimization. Advances Neural Information Processing Systems, 22, 2009.
Alacaoglu, A., Fercoq, O., and Cevher, V. Random extrapo- lation for primal-dual coordinate descent. In International conference on machine learning, pp. 191-201 PMLR, 2020.
Alacaoglu, A.,, Cevher, V., and Wright, S. J. On the complex- ity of a practical primal-dual coordinate method. arXiv preprint arXiv:2201.07684, 2022.
Bansal, N. and Gupta, A. Potential-functie proofs for

---

A Near-Optimal Single-Loop Stochastic Algorithm for Convex Finite-Sum Coupled Compositional Optimization
gradient methods. Theory of Computing, 15(1):1-32, 2019.
Hu, Y., Zhang, S., Chen, X., and He, N. Biased stochastic first-order methods for conditional stochastic optimiza- tion and applications in meta learning. Advances in Neu- ral Information Processing Systems, 33, 2020.
Beck, A. First-order methods in optimization. SIAM, 2017.
Becker, B. and Kohavi, R. Adult.
UCI Ma- DOI:
Jalilzadeh, A., Hamedani, E. Y., and Aybat, N. A houbly-randomize coordccor primal-dual method for large-scale saddle point problems. arXiv preprint arXiv: 1907.03886 2019.
chine Learning Repository. 1996.
http:///bi.ogg/1.2244///Xxxx
Blondel, M. Python implementation of "structured pre- diction with projection oracles". https::/gittee
Jiang. W., Li, G., Wang, Y., Zhang, L., and Yang, Multi-block multi-block-single-nnoe -ingle-probe variance reduced estimator for coupled compositional optimization. arXiv preprint arXiv:2207.08540 2022.
comm/mbbl.nddel//poojetttt on- losses/blob/ naster/polytogees.pp 2019.
Buda, M., Maki, A., and Mazurowski, M. A. A systematic study of the class imbalance problem in convolutional neural networks. Neural networks, 106:249-233 259,,, 2018.
Juditsky, A., Nemirovski, A., and Tauvel, C. Solving varia- tional inequalities with stochastic mirror-pros prox algorithm. Stochastic Systems, 1(1):17-58, 2011.
Chang, C.-C. and Lin, C.-J. Libsvm: library for support vector machines. TIST, 2(3):27, 2011.
Lan, G. First-order and stochastic optimization methods for machine learning, volume 1. Springer, 2020.
Cutkosky, A. and Orabona, F. Momentum-based variance reduction in non-conver SGD. Advances in Neural Information Processing Systems 32 (NeurlPS), pp. 15236 15245, 2019.
Levy, D., Carmon, Y., Duchi, C., and Sidford, Large- scale methods for distributionally robust optimization. Advances in Neural Information Processing Systems, 33: 8847-8860) 2020.
Gao, W. and Zhou, Z.-H. On the consistency of AUC pair- wise optimization. In International Joint Conferences Artificial Intelligence (IJCAI), pp. 939-945, 2015.
Lim, C. H. and Wright, S. J. Efficient bregman projections onto the permutahedron and related polytopes. In Artifi- cial Intelligence and Statistics, pp. 1205-1213. PMLR, 2016.
Hamedani, E. Y. and Aybat, N. S. A primal-dual algorithm with line search for general convex-concave saddle point problems. SIAM Journal on Optimization, 31(2): 1329, 2021.
Liu, Z., Luo, P., Wang, X., and Tang, X. Deep learning face attributes the wild. In Proceedings of International Conference on Computer Vision (ICCV), December 2015.
Hamedani, Y., Jalilzadeh, A., and Aybat, N. S. Random- ized primal-dual methods with adaptive step sizes. In International Conference Artificial Intelligence and Statistics, pp. 11185-11212. PMLR, 2023.
Martinez, N. L., Bertran, M. A., Papadaki, A., Rodrigues, M., and Sapiro, G. Blind pareto faimess and subgroup ro- bustness. In International Conference on Machine Learn- ing. pp. 7492-7501. PMLR, 2021.
Hsieh, Y.GG,, lutzeler, F., Malick, J., and Mertikopoulos, P. On the convergence of single-call stochastic extra- gradient methods. arXiv preprint arXiv: 1998.08866.. 2019.
Meng, S. Y. and Gower, R. M. A model-based method for minimizing evar and beyond. In International Conference on Machine Learning, pp. 24436 2246622446.. PMLR, 2023.
Nemirovski, A., Juditsky, A., Lan, G., and Shapiro, A. Ro- bust stochastic approximation approach stochastic pro- gramming. SIAM Journal optimization, 19(4):1574 1609, 2009.
Hu, Q., Qiu, Z., Guo, Z., Zhang, L., and Yang. T. Block- wise stochastic variance- reduued methods with parallel speedup for multi-block bilevel optimization. In Interna- tional Conference Machine Learning, 2023a.
Nguyen, P. H., Nguyen, L., and van Dijk, M. Tight dimen- sion independent lower bound on the expected conver- gence rate for diminishing step sizes sgd. Advances in Neural Information Processing Systems, 32, 2019.
Hu, Q. Zhu, D., and Yang, T. Non-smooth weakly- convex finite-sum coupled compositional optimization. In NewrIPS, 2023b.
Hu, Q., Zhu, D., and Yang, T. Non-smooth weakly-convex fnite-sum coupled compositional optimization. Ad- vances Neural Information Processing Systems, 2023c.
Platt, C. Fast training of support vector machines using sequential minimal optimization. Advances in kernel methods, pp. 185-208, 1999.
10

---

A Near-Optimal Single-Loop Stochastic Algorithm for Convex Finite-Sum Coupled Compositional Optimization
Qiu, Z.,, Hu, Q. Yuan, Z., Zhou, D., Zhang, L., and Yang, T. Not all semantics are created equal: Contrastive self- supervised learning with automatic temperature individu- alization. In International Conference on Machine Learn- ing, Proceedings of Machine Learning Research, 2023.
Yuan, Z., Wu, Y., Qiu, Z.-H., Du, X., Zhang, L., Zhou, D., and Yang. T. Provable stochastic optimization for global contrastive learning: Small batch does not harm performance. In International Conference on Machine Learning, pp. 25760-25782. PMLR, 2022.
Qiu, Z.-H., Hu, Q.. Zhong, Y., Zhang, L., and Yang, T. Lcrge-scale stochastic optimization of ndeg surrogates for deep learning with provable convergence. In Inter- national Conference on Machine Learning, pp. 18122- 18152. PMLR, 2022.
Zhang, L.., Zhao, P., Yang, T., and Zhou, Z.-H. Stochas- tic approximation approaches group distributionally robust optimization. arXiv preprint arXiv:2302.09267 2023.
Zhang, X., Aybat, N. S., and Gürbüzbalaban, M. Robust accelerated primal-dual methods for computing saddle points. SIAM Journal on Optimization, 34(1):1097-1130) 2024.
Rudin, C. The p-norm push: A simple convex ranking algo- rithm that concentrates at the top of the list. Journal of Machine Learning Research, 10(Oct):2233- 2223-221,, 2009.
Sagawa, S., Koh, P. W., Hashimoto, T. B., and Liang, P. Distributionally robust neural networks for group shifts: On the importance of regularization for worst-case gener- alization. arXiv preprint arXiv: /9/ /.08731, 2019.
Zhang, Y. and Xiao, L. Stochastic primal-dual coordinate method for regularized empirical risk minimization. In ICMI, pp- 353-361, 2015.
Zhang, Z. and Lan, G. Optimal algorithms for convex nested stochastic composite optimization. arXiv preprint arXiv:2011.10077 2020.
Soma, T., Gatmiry, K., and Jegelka, Optimal algorithms for group distributionally robust optimization and beyond. arXiv preprint ar 2rXiv:22/2./3666 2022.
Zhu, D., Li, G., Wang, B., Wu, X., and Yang, When AUC meets DRO: optimizing partial AUC for deep learning with non-convex convergence guarantee. In International Conference on Machine Learning, 2022.
Wang, B. and Yang. T. Finite-sum coupled compositional stochastic optimization: Theory and applications. In In- terntiionll Conference on Machine Learning, pp. 23292- 23317. PMLR, 2022.
Wang, B. and Yang, T. (extended version) finite-sum cou- pled compositional stochastic optimization: Theory and applications. arXiv preprint arXiv: /2396, 2023.
Wang, M., Fang, F. X., and Liu, H. Stochastic composi- tional gradient descent: algorithms for minimizing com- positions of expected-valus value functions. Mathematical Pro-
gramming, (61(1-2):419
2017a
Wang, M., Liu, J., and Fang, E. X. Accelerating stochastic composition optimization. Journal of Machine Learning Research, 18:1-23, 2017b.
Yan, Y., Xu, Y., Lin, Q., Liu, W., and Yang, T. Optimal epoch stochastic gradient descent ascent methods for min- max optimization. In Advances in Neural Information Processing Systems 33 (NeurIPS), 2020.
Yang, J.. Shi, R., Wei, D., Liu, Z., Zhao, L., Ke, B., Pfister, H., and Ni, B. Medmnist v2-a large-scale lightweight benchmark for and 3d biomedical image classification. Scientific Data, 10(1):41, 2023.
Yang, T. Algorithmic foundations of empirical x-risk mini- mization. arXiv preprint urXiv:2206.00 00439, 2022.
Yang, T. and Ying, Y. Auc maximization the era of big data and ai: A survey. ACM Computing Surveys, 55(8): 1-37, 2022.

---

A Near-Optimal Single-Loop Stochastic Algorithm for Convex Finite-Sum Coupled Compositional Optimization
Table Notations we throughout the paper.
Basic
d
Number of the model parameters
7
Number summands in cFCCO
(I) Below (2)
R+
Set of non-negative real numbers
(z)+
max 0}
[1
Set (1.
The i-th block of size in the vector y E R
V
max(a, b) for a, E R
A b
min(a, b) for a, 6 E I
axx
There exists c, C > 0 such that ob S Cb for aera
Lx
1 if the event is true and 0 otherwise
Appendix E
Standard
fz
The convex conjugate of a function f
4
The strong convexity constant
Assumption
Strictly convex and differentiable 4h: R.
R
X
Convex and closed domain of the model
y
The decomposable domain the dual variable y. y V1 x ... x Vnn 31 CR. A normed vector space in RT with norm ||-]
y4
The i-th size-m block a vector y E R
Vrr
Dual space of V. with norm [[
(v, v)
Bregman divergence (u) (v) (Vir(v), 1) for u. E RM associated with d/s
Up(11 V2)
Defined > 0v (y) (3)
"/ for yl. V2 Rum
The diameter m (2(w) min.gy di (v)) of set w.r.t dis
Dy
Defined as |Σ - D W. 1122
Dx
D with 4/x
$ -1.11
|TTillap
Operator supzex
||
for linear operator T: X 3/2
| lo
Operator norm supxax
|
the adjoint operator T? Va + X
(S)
Linear span of set 5 of vectors
An
The (n di-dinensional probability simplex An C R
Cg
Lipschitz constant inner function gl
Assumption
Cf
Lipschitz constant of outer function ft
Assumption
og. of
Variance upper bounds of zero-th and first order oracles of gi
Assumption
8"
Variance upper bound of compositional stochastic gradient
Assumption 4
Algorithm
Batch S C [n] of size S sampled the t-th iteration
Algorithm
Two i.i.d. batches of size- sampled from P. the 1-th iteration. Batches (B(") Jass, are actually sampled Algorithm Batches (B(") Jags, are virtual and only for analysis
B(C) B
(x; B
Stochastic estimator R Ege g(2; (.) based on the mini-batch ( sampled from P. Hyperparameters of ALEXR
for (z) in (1)
n) T
Algorithm
(8)
Extrapolated stochastic estimator for the inner function value
Line 6 in Algorithm 1
Analysis
F(x)
Objective function of cFCCO
Li,,, y)
Objective function of the min-max reformulation
(2)
A minimizer of F F(x) in (1)
(Ia, y/))
Unique saddle point T. y) in (2) when fa is smooth and r is strongly convex
Dual auxiliary sequence defined for the convenience of convergence analysis
(5)
ZT
primal iterate r 7T-1 #c+1
M7
E arg ma (v (TTr) f (w)) E (fr())
V1
Virtual sequence delined in the proofs of Lemma and Lemma 10
Below (20) and (34)
T,
Defined 5 (0:(..) g. (xx-1)) (1)) v
Lemma 6
Ti
Defined as E [x_ 2
Section D.1.2
Y7
Defined as $ (UU+(++) (4)
Section D.1.2
Virtual sequence constructed in Lemma 9
Below (6)
91. 14
Virtual sequences constructed in Lemma 10
Below (33)
Time-average dual auxiliary iterate 7 Ex- Det1
Below (39)
12

---

A Near-Optimal Single-Loop Stochastic Algorithm for Convex Finite-Sum Coupled Compositional Optimization
A. Other Related Work
The min-max reformulation of cFCCO in (2) is closely related to the following prior work.
Convex-Concave Saddle Point (SP) Problem. The saddle point (SP) problem mingex maXzey ((z, y) that is -o-coe in and Hy-concave in y (Mzz My 2 0) has been thoroughly studied. refer to the SP problem with flz, My > 0 strongly- convex-ttrongly-concal (SCSC) problem while those with Mas My = 0 as convex-concave (CC) problem. A saddle point (Ir, ). if it exists, satisfies the condition [(xr,,) v) S L. V.) S T. v.), Var, y) E X x y Besides, the SP problem is closely related to the more general monotone variational inequalities (VI) which involve finding point 2, = (x=, Vv) such that ($(z), 2 - 2.) 2 0, ((2) = (o, y), - -8, (zz, y)). V22 E X X'. To assess the optimality of any point (Tot you) E X' x V, we can employ the concept of the duality gap, defined as Gap Mous) == max { y) - L(xr, Your ). and for SCSC problems, we can also use (F Mowi := _/2 || - 2 ==112 112 - || y- 11.. The convergence rate is quantified by measuring the number of iterations required to find an e-approximate saddle point or an e-approximate solution to the VI, satisfying one of the following conditions: (i) Gap(Foun: you) S e; (ii) ( Yomr) I <; (iii) (o (Z(ott) Rout 2) S c.
Accessing exact oracles such as L and V may not be feasible in many real-world scenarios. Instead, the available resources provide only unbiased stochastic estimators, denoted as L and VgL. with variances bounded by o². This limitation has prompted the development of numerous algorithms tailored for addressing the stochastic saddle point problem (SPP) and the more general stochastic variational inequalities (SVIs). For instance, the stochastic mirror descent (SMD) method (Nemirovski et al., 2009) achieves the optimal convergence rate of ( for non-Lipschitz SVIs. For Lipschitz monotone SVIs, the stochastic mirror-prox (SMP) method (Juditsky et al., 2011) attains the optimal rate of O + 2 For SCSC and non-smooth SP problems, Yan et al. (2020) establish the Ö - V pl,e) rate with probability 1 p. Hsich puz
et al. (2019) propose a single-call stochastic extragradient (SSEG) method that achieves a rate of O + _a, p,,e) for Lipschitz and strongly monotone SVIs. More recently, several works have devised stochastic algorithms for both the SSP and SVI problems, achieving (near-)optimal deterministic and stochastic convergence rates simultaneously. Zhang et al. (2024) introduce the SAPD algorithm, which reaches a convergence rate of Ô(1
o² V _²
for the SCSC Myy
Pr
Py
problem and O + ) for the CC problem. These algorithms cannot be directly applied to the min-max reformulation of cFCCO in (2) because the dual variable y could be very digh-dimensional, making it computationally infeasible to update the entire y. This challenge motivates the block-coordinate stochastic update in our algorithm ALEXR.
Coordinate Methods for the Block-Separable Deterministic SP Problem. A special class of bilinearly-coupled SP problem is in the form min, maxy [(r v) == Σi= (v x ())) + r(z)), where L(x, y) is block-separable w.r.t. the dual variable y. One illustrative example is the primal-dual reformulation of the (regularized) empirical risk minimization (ERM) problem, denoted as min, F(z). where F(x) is defined as F(x) == 2 Σi= E(a, x) + r(z). This reformulation applies to data-label pairs (a:, bi) in the context of a linear model. Particularly in scenarios with a significantly large value of n, the computational overhead of computing VyL(x, y) and updating y can become prohibitively expensive. In such cases, randomized coordinate methods offer a viable solution by reducing the per-iteration oracle cost from ((n) to (1)) The SPDC method (Zhang & Xiao, 2015) leads to Ö(n+ +
a
convergence rate to make E[D(E, (z, 7)] S for
MaHly
the SCSC problem and Ō Ö(n + v/n.) rate to make
F(x.) S e for the CC problem. Recently, Alacaoglu et al. (2022) extended the Pure-CD originally proposed in Alacaoglu et al. (2020) to incorporate importance sampling and exploit the potential sparsity in A. For the CC problem with dense A, Pure-CD not only achieves an improved rate of O(n + X to guarantee (T)) - F(x.)) S E but also attains a rate of Ō(#) ) to ensure E[Gap( 7) S <. It is worth noting that G[Gap(z, 7)] < E serves as a sufficient but not necessary condition for E[F(T) - ((xx))(<<
In addition to addressing the bilinearly-couple block-separaie saddle point (SP) problem, Hamedani et al. (2023) have extended their focus the more general Convex-Concave (CC) problem, defined as T. v) Φ(z, v) ovy) + (z Their work establishes a convergence rate of O m2) for randomized block-coordinate primal-dual method, ensuring that E 2'Gappa 2. 7)] < c. Furthermore, Jalilzadeh et al. (2019) have delved into scenarios where L(x, y) exhibits Mock-ssparrbiiityy to both x and y. In this context, L(x, y) is defined as L(x, y) = 4(z, y) - - ø, (1 ) hy (x.0). block-coording
They introduce a the works mentioned in this section (Zhang & Xiao, 2015; Alacaoglu et al., 2020; 2022; Jalilzadeh et al., 2019) rely on the assumption of having access to the exact 22 y) and V, v fxx, y). In contrast, our work addresses the more challenging problem where only stochastic oracles are available.
method to address such problems. It is worth emphasizing that all
13

---

A Near-Optimal Single-Loop Stochastic Algorithm for Convex Finite-Sum Coupled Compositional Optimization
B. Others Applications of cFCCO
In Section 5, we introduce two applications of cFCCO: Group Distributionally Robust Optimization (GDRO) and Partial AUC (pAUC) Maximization with a Restricted TPR. Here we provide more applications of cFCCO in machine learning.
Robust Logistic Regression. Consider collection of data-label pairs, denoted as (ai, bs) We can formulate the robust logistic regression problem mintgex : E'= log(1 + exp (, x a.)) + (xr). In this formulation, A(a,) represents the perturbed data generated from an underlying distribution P., This is special case of (1), where the functions fi(-) are convex and monotonically non-decreasing given by ft(-) = log(1 + exp(b;-)), and g: (z) = _B(aa)),,L [A(a;) x].
Bellman Residual Minimization. The task of approximating the value function, denoted as (*(s), for each state s under +7-0]=))) In this formulation, d. and o.' are feature vectors representing states & and s', respectively. Additionally, Ta,s' represents the random reward obtained during the transition from state s to s', 7 < is the discount factor, π denotes the policy, and P represents the probability of transitioning from state s to s' under policy æ. This problem can be formulated as (1), where the functions (+) are convex and given by f=(+) = (-), and the affine function g = $ -E PTT,sr ITa.s' + 7 o5.r).
policy x using a linear mapping can be expressed as minsex Eo= x - - PT (ra.s
Bipartite Ranking, Imbalanced data classification is usually tackled in the context of the bipartite ranking problem. There is often a desire to penalize those positive examples with lower scores. One approach is the p-norm push, introduced
by Rudin (2009). It formulates the problem as min 1 EateD, ( EojeD ((sx(ag) - s2 (ax))) + +r(x), p 2 1. i Here, D_ and DD_ represent positive and negative data sets. The function sa(a) denotes the ranking score of data point a, which is determined by a linear model parameterized by x. The loss function &' is non-negative, convex, and monotonically non-decreasing, for instance, E(-) = exp(-). The p-norm push method is in a special case of (1), where the functions f((-) are convex and monotonically non-decreasing and given by f((-) (-)², and the convex function (x))) 1 EoyED_ (()=(a)) su (a))). One popular approach for retrieval problems is maximizing the precision or recall at top 1 positions (prec/rec@ k)) Yang (2022) has formulated the problem as minzex 1 EasED, Ei(EaEeDuun (az)
ni
sy sx(o,) - x)) + r(z), where f,, l are monotonically non-decreasing convex surrogate losses of the zero-one loss. Hence, maximizing precision recall at top k positions with a convex model 8, (a) is covered by (1).
Multi-Task GDRO. GDRO can be extended to the multi-task setting. Consider a scenario with n tasks and m groups We represent the data distribution for the i-th task and the j-th group as Pt.j Additionally, let f(x;)) be the loss function associated with parameter x on data point 2. The Multi-Tasn GDRO, with a regularization term r, is formulated as minzgx 1 E max maxje]m] B[((x; zag)] + r(z). In this formulation, the functions f((.) are defined as [1g))= = ][m] (9t)); and giy (z) = R[[(r; ziy)], where (x()) = [ga (z)..... (.m (x)]. Alternatively, we may consider the smooth fi(g:) = log Eje(m) exp(g.)) This problem is particularly relevant for the scenario featuring a substantial number of tasks, such identity prediction in human faces, with a limited number m of groups (e.g., lightning conditions).
C. Basic Lemmas
Lemma 1.
Suppose that yo (0) = f((ub)) E 0f((u!)) for some up E R and u
I 4
+
i S.
(2)
$ St.
Algorithm I with vi = f satisfies that vi = M(()(") E 0f(((( for all i E (I....,,)) and 1 12 0.
Proof. We prove it by induction. The base case follows from the premise. Assume that vi fl( ( 0f((ul))
Case (i & S:): Note that ( = yi and u w = u, Thus, 1141 = fí (((lffi) E O.f((()11)
Case II (i Si): This part resembles Lemma 2 in Zhang & Lan (2020). Based on the update rule and the premise
ut E (f(()))) (8)), we have
{ y g0
- (1) - - (0)))
v = arg max g(o)
arg max y
(1+-5""
1
gt
+ T T- (1)
ui (())
-00) m
E 0f: 11
(
1 (1) + 11
(0) (00
1 - =0f((u(1))
1+T
14

---

A Near-Optimal Single-Loop Stochastic Algorithm for Convex Finite-Sum Coupled Compositional Optimization
The following lemma is well-known and similar ideas have been used in Nemirovski al. (2009); Juditsky al. (2011).
Lemma 2. Consider a martingale difference sequence D adapted to Ft. Define a sequence (
to = O, Mt+1 arg migg (aimm-iiiaa.. Dc, 8) + aUs(e,
where we also assume that vb is pey-stoongly convex W.t. |1-11 (ap > 0). For any v (that possibly depends on Ar) we have
E (A b\] - (aU #t) - (U, #[+1)]+ +
E E
2aquo
Proof. Use the three-point inequality:
(- #111-11 S aUs(v, m2) aUp((, aU (Up((t+1,))))
Add (-As, me - 1 to both sides and use Young's 's inequality.
1)
(-Ar, tt v) S (v, #t) - atp(v, #t+1) - mt) + (Ai; Mt+1 - :tt)
s at fte) aUp(v, Ae+1) aUp (# At) + Offha
| - -Hell
||
2
20/4
If pe--trongly convex, we have- -U (ft+1, me) S | #e|l" Lastly, EclAe, #t]
The following lemma combines Lemma 4 in Juditsky et al. (2011) and Lemma 7 in Zhang & Lan (2020).
Lemma 3. Let 11 C. I.m be a non-empty closed and convex set and function u(T)) be u-strongly convex on 11 w.t.. II-Il- Let it be generated via prox-mapping with the argument 9 + 8, â arg min ( (T.g + 8 u (x)) u(T)) for some I IL, where 8 denotes a noise term with E[ő] and B[[[@][]] S oz. Then, for 9 generated via a prox-mapping with the argument 9. ã + arg min (T.g ut (m)) + u. we have
|| न| S | /P,
(10)
E (R. 8) S d
(11)
For completeness, we present the proof of the lemma above. We do not claim any novelty here.
Proof. By the optimality condition of prox- prox-mapping. we have
(u'(#) v' (m) + + 8 x) S0, 0, VT E II,
(12)
(u' (7) v' (m) + g. T) S 0,
VT E IT.
(13)
Choose ग = ग in (12) and क = à in (13). By combining (12) and (13), we have
|| || म|| 2 (ō, मे क) 2 (u (i) u' d(( n - 8).
Since u is j-sttrogly convex, we have (u'(#) - u' (5), म お) 2 | - न Thus, || - #|| S |1 /p.
Moreover, the triangle inequality leads to [E (#. 8) < [E (# - म, 6) + E (M. 5) J. Note that E (n, 8) = 0. Moreover, Cauchy-Schwand inequality and (10) leads to
IE (R.
8)
<
IE
(A
< E|| म [| < 1 / 000p म. 5)
Next, we present a basic inequality about the mirror proximal update. Similar results have been widely used in the literature, e.g., Lemma 3.8 in Lan (2020) and Lemma 7.1 in Hamedani & Aybat (2021).
15

---

A Near-Optimal Single-Loop Stochastic Algorithm for Convex Finite-Sum Coupled Compositional Optimization
Lemma 4. Suppose that the function Φ X + R is on a convex closed domain X and p-convex (μr 0) with respect to a prox-function Ugp (z; y) = (0x)) vb(y) (v'(v), x y) for any x. y E X with generating function 4/, Lee, <(x) 2 p(y) + (o' (y), y) + p0 2) Va,y X. For t = arg min mix + nV (z, x)}, we have
((3) - ((z) - (1, - (n + (z, (2,
E E X.
(14)
Proof. By the definition of the prox-function Up (2r, y). we have
U,(2,zz) (z 2) (t, = (xx) - (2) (w) - 22) - (x) + (2)) + (B)) 2) - (()) + ((x) + (V()), - x
= (+) - 1/ (z), x it)
(z. 8). The optimality condition of the prox-mapping implies that (d' (0) (() (1))), 8) 0 for any E X. Thus, we obtain
By the strong convexity of & with respect v. we have Φ(x) 6(0) 2 ( + ut 5z
(d'(2), x 2) N - (+) (z),, x 2) such that
((x) x(t) 2 (0())) 8) + (x, (t)((() - v'()), x 8) + (x, - + (
U 2) + (.)
D. Convergence Analysis
The following lemma is the complete version of (6), which is the starting point for the convergence analysis of ALEXR.
Recall that in all cases we have Uz; (u, v) 2 pU (u, v) for some p 2 O and any u, u E y/-
Lemma 5. Under Assumption 1, the following holds for any E X2 y E y after the t-th iteration of Algorithm I.
(( L(x, 36+1)
(15)
a > (1(())))) -((0) - -b/41) +
U s I Uv((. v.) T+P P (N. D(+1) n
(
||
xx 11
n
n
n
2
17 + 1 II
22t1l12-
1 | 2
xel12 (I.()))))) (=)) (G1, 1 -x).
2
Remark 3. Note that Algorithm 1 only samples B.( 9 for those E S, and computes the extrapolated stochastic estimator g (8) for those E S in the t-th iteration. For those i & St, the stochastic estimators {ā(() (3) higs, and the batches (b5 (t) hiss, virtual and introduced solely for the convenience of analysis. They are not required in the actual execution of Algorithm 1.
Proof. According to Lemma 4, the primal update rule implies that
" - -G,, x - 2(41) + r(0411) - r(z) - 2 2
|| xx
112
n
17
1
||
x141
12
17
| - 2z
(16)
2
2
Similarly, for all i [n]] the dual update rule implies that
(g thth T
T oe ( + (7 - ft (1 < -U (y
2220 (r
-Us, (2
Average this equation over i I,...,n.
a
(1()) 1 ) Di
(
((((0))))))) < n
[v((.m)) T+ Uv - - Ue(e41)) (17)
16

---

A Near-Optimal Single-Loop Stochastic Algorithm for Convex Finite-Sum Coupled Compositional Optimization
By the definition of [(x; y) in (2), have
((I++1.8) (xx, 1c+1)
1
(x(11+1) y/() Σ f1 +1(+411) 1
Σ
(1(
91+1
(0)
+
1 Σ
(1(0))) -x(x)
n
1=1
1
(0((22+1 (v vltz) + ( f1((()) (9) (2)41) 9x(x)) (((=))][(+)) bit1) + -((041)--((1)
Combine the equation above with (16) and (17).
M( v) L(x, Ie+1)
$ I Uv. y1) I+ P U (y. De+1) T U (Be+1,3 3+++ - - -iit1 + " || xx
a
n
n
n
11 + 11
1| 12+1l12 | - x2al (g.(x)))) -x(x)) Pe41 (Gr, - -x)-
(18)
2
D.1. Convergence Analysis of the Smooth and Strongly Convex Case (Section 3.3.1)
First, present several lemmas that upper-bound different terms in (15) with (x. (I., y.), where (Ixx, y=) is the unique saddle point of the smooth. We present our result with general str-nlyyggyy convex Distance-generatiin function s);, For example, we have Mo +, for smoothh and th ff; Besides, we have py for non-smooth f; and th: 2 11-112
objective L(r of (2) when (1) is strongly convex and Si is
D.1.1. SUPPORTING LEMMAS
Lemma 6. Under Assumptions 2 and 4, the the following inequality holds for Algorithm with 0 and any X2 As >
B(gi(1+1)) - ((())((())))))))))))))))
-Dtt1)
(19)
<T4 - 0r, + C2 |1a-1 22
OC2 11r
xt 2
(A2 + >a0)U Mc)
2(1 + 20)
2h2
2)g
py
Bus +
where r, = 1 (g:( - (0 (T)T)))( y/ ))
Proof. The 1 Ei= B(gi(Te=1) - g: T (y. (2)
9141)
term can be decomposed as
0 1 Σ (0.())))) -. ) T Tyy (
(20)
n
1 0
(g.(2)) - (z B(())) (y
n ( (zy 2
7
0
- - (xx))) (2
(1)
0 n
(a(=)=1: - g((x)-1)) (g) v(h)
11
m
IV
Taking conditional expectations of terms I and IV leads to [x(g;((x) - (ze; () y Fi-1l - and (((,(())))))
Ty
(:( B(()) 1) (3)
Fe-1] = Vi [m]. define 1141 = arg max (r) Dt (v) -U, v: ( and gr
(8)
(i)
17

---

A Near-Optimal Single-Loop Stochastic Algorithm for Convex Finite-Sum Coupled Compositional Optimization
ge(2s) + Oggi (xre) - 9i (x)-))) Note that 1/41 independent of B, such that I8 [[g B(2) - (xx)) Det1 Fi-1]
(6)
( B [oo(( B(²) (i(()e)
Dit1 E (or( B(²) - 9 (x())) (Tif1 -1221
Lemma 3
pulp+ + (x)) g2(2 B [11 + (g)(()) gi BB ((g:(((-1)))))) gi 1,
(1+ (z))) (z B, )1 |13 (x))) (1 B, ||1- (1)(())))))) - 9;(
-
(p +
(1+ (.50
0.50
(1 + 1200000
polp + E (x)) ( BB ||2
Mplp + T) (19((00-1) 91 (2 B! )1
Bug (p+ TT)
(1 1-+20008
(9:( (()) gi(xx--)) sit1 = (0i( B(0)) - gi (x)= ( (0611 v(th)) S
Bu TT)
Define r=== (o(())) - 1 (v.-0)
11 (
III in (20) can be rewritten as
I III 1 a
(((2+11) (g/h)
(1) (0)
1
1 n
Σ
g (z+) T (gL 91-1)
0 "
- (v) -b(f1)
-i(+1)
71
71
n
= =T 0T,
1 Σ
(x((1)+))))))))))))))))(())))( -g(t)) (We+1
(xx))
(10
0
(gi - (xx)) (x6 -
(1)
n
<T - 1001-0r++ +
1
Σ
(1x(( - (11e)]l-1111
(8)
wef1 || +
Σ
(1)(( (100))l= - vitall
1=1
:=1
C2 | xell2
0C? |0g - 22-1 11
(A2 + >a0)U (11+1,
STa+1 1 or, +
2d2
2da
pay
Lemma 7. When gi is -m--tooth and Assumptions 1, 2, 3, 4 hold, the following holds for Algorithm 1.
EE
(0) T - EE (G,, - -xa) <
C7a7
B
+
62
S
L.gCs
| - xell.-
(21)
11
+
1
2
Proof. We define A = 1/ (Vi(a Vi+1 (V))))
(1)
- -
Di+1 (G1, - xaa)
(1)
1 (ai(Fe11) - g((x)) Dit1 + E(e((t)) - 9x(x))) 01t + + (o(x))) 1. + (1)TT(Z - -
1
n
n
n i=1
i=1
1
(((1++1)-9(1))))
De41 +
n
(xx)) ((
21-1) T (z. - x.)
1 n
(2x)) T 0. AA) - I141)
T2
n
n
n -((==)))-(((=))))
1
Ve+1
(i)
1
V (xx)) 212 3141) (A., x(41),
(22)
n
where @ is due to the convexity of 9i and 31+ S R.. The first two terms in (22) can be bounded by the Lipschitz continuity
18

---

A Near-Optimal Single-Loop Stochastic Algorithm for Convex Finite-Sum Coupled Compositional Optimization
of Sa and Vg--
(0.(2)41) -; De41 + ( E [xe() Bi+1) ( (xt xz+1)
(0e(11411) ( Vge(zr) sz)) (0)
Det1
Vgi( -oll:a-)--aa)---oootote--------- xe)ll. C1
Det1
- ( - 2:)1..
Due to the T-g-smoothness of gi, we have
(0(( ( 2:)ll. S Lg
| 1
Thus, the first two terms in (22) can be upper bounded by
" Det1 + ( Σ Vg( 11 T (#x)) S | - xell2 n
Cg
(o:(x141) - (x+))) (2))))
(23)
72
Besides, we have II, Fi-1] By the Lipschitz continuity of fa and the definition of the operator norm. we have (((Vgs(x)) [ )] > & [[+] - [V I1opll < (x)) [Vgs(m B(O)]] > llop. According to Lemma and Assumption 4, we can derive that
Cj B
82 リ+
EEl 1 ([Va:)))) - (a, T0(2
-[((2)1,, A.)
g
(24)
J μ+ 7
S
+ 11
iES.
Then, combining (22), (23) and (24) leads
8a + S
L,C
(9.(2141) - gxxx)) 1 (G. (1.11111
x) S
||2211
xxel2
n2
++
2
Lemma 8. When ga non-smooth and Assumptions 1, hold, the following holds for Algorithm
c7o
8² 5 + +4C40g
n #
E (0.(=++1)))) - (xx)))) 0:21 - -E (G2, x)
|| - xel12
(25)
4
Proof. Note that (22) and (24) still hold. Since 9i is non-smooth, we need to bound the left-hand side of (23) in a different way. Based on the definition of the operator norm and the Lipschitz continuity of gr, we have (1.) x141) S (x:))l || - ret1ll2 I Cy I| 24+1ll2 such that
(g((4))) - (zx))) De41
T +
1 Σ
(Lo((x))) ((2)) (xt I141)
72
n 1=1
(
Met1
(1)
+ n
Σ (o) - x241)) slf
7
lofl2 99 + (
-1+11)ll.
1C702
< 200,0, || - -eell-
+
a 1
|| - xel133
(26)
4 p
19

---

A Near-Optimal Single-Loop Stochastic Algorithm for Convex Finite-Sum Coupled Compositional Optimization
where (1(x1e) E (gg( Merge (22), (24), and (26).
0907 B
8 g +
+
1
E
- U E (Gi, 24+1 -2) 2)
+ +0.25(n + (b) || - xell2.
71
p +1
D.1.2. PROOF OF THEOREM
Proof. If 9: is smooth, we combine (15), (19), and (21).
T p1 =)
E [ ((x,,0t+11
E
I+
(++tt E 11., =xel22
P BlU |t+1)] +
S
8
+ P 111 x2+1112
(T
A2 + Aao
E [ (JC(1111))1)
11
g
E | - 2ell2
n
Mon
2
2
+ 2
8C2
2 E || - xz-1 112 + E[[T++1 0T,] +
2(1 + (1++2)oo Bub + 7)
+
B
+
8²
(27)
11 +
Define r. E |,,, - zt || and r =
(y.. we). Note that L( y.) L(z.. 0e+1) 2 Multiply both sides of
(27) by 0-1 and do telescoping sum from i t T - 1. Add -y both sides.
S )) ,ET,) ((n + +) + +
n/ r 5
(6 + (T p(1
ET+11)
7
+
no
TT
2(1 11++2000 20)
c707 + 8²
3
T-1
Σ 0-
T-1
Σ g-t
T
(A2 + )g0)
B(U v (To+1.8))))
Bp +
n
T-1
LgC1
C2
C
Σ
11
B| - x
2
2)2
2\g
1=0
p (where J > 0if0 > 1 - - such that 0= =+p(1-
Let 17
such that 0 ==
and
Ps
Then,
1-9
7+P
x(1-0)
TtP
S )) , ((7 + n) (T - p) ET1+))
Σ 0 (( (r + p(1
n
S 1)r - OET - T+1 ((1 + h + + + -
= प + (T + p(1
By setting x-1 Zo. we have To- = O. Besides, we have -IT < 1 Σ (xT)
11y (0) - - 5
Co | -T-1 1|2 y/ - yr||. Thus,
n T S 1/ (T + p(1 -
(r+ p) r
Cg
| XT- 11 vlll)
n
n
T-1
Σ
( + (T +
BT
7 rx + (T + xl
S
1)/o77 ET,))
n
2(1 20)0
cio 8²
T-1
T-1
(12 + \g6)
+
+
B
S.
Σ 1=0
g
g-t
v(]
M
7+
nn
1=0
T-1
8-1
1)
L,C,
C2
C2
E ||
xel12
(28)
2
2
2A2
2
1=
20

---

A Near-Optimal Single-Loop Stochastic Algorithm for Convex Finite-Sum Coupled Compositional Optimization
Note that 1) 1 3
0
- such that (n + T g
0 and C2 | - xT-1ll2 11 Vrll S
C2 2A
C. Copsp vnp
IT - IT- 112
do (v VT). To make the 4 terms in (28) be non-negative, we choose X2 x
2ppn
C. / while ensuring that vap
A x
VSpuy A Covmp LgCs) 1,0,)
1
1/750
1//50
(29)
CgVSp)
Since ==
0 ml1-8)
p - 0
we have T + (1-))
()) = =0(T + p) and (T + p) - 0)
r+p
(T ( () (1 0)
2(1 2(1 + 20)08
0907 8a
nT S To +
0T T +
Bipt( +T)
1
C7 6a g
2(1 + +20000
- + (T + p)(1 - rg
+
Mb B(p +
Cloi 8a
=uO
ps
r
2(1 + 20)08
B
3
n
By (y +T)
n+ p
We select 0 1
# bgCy
A
H C
BpSe 6/n
Bue C
Sue g
to make (29) hold and
2(1+ 201000)00
C7al
B
+
2(1 + 20) 0) 0)
(1 (1- 0)
Ciof
B
5
Se
Hy Bpp T)
17 + μ
Hy BpS
p
Since E, = Hop when fo is Ly smooth,, the number of iterations needed by Algorithm to make μ S e is
T Ō
n S
LgCs + CoynLs
nL
Cjoi
8²
VSp
BSc
pBc
U.cc
where Ō(-) hides the polylog(1/e) factor. In the case that gi is non-smooth, we utilize (25) instead of (21). Correspondingly,
Cr in (27) by 0.25(n + v1). Additionally, there a 4030% we need to replace the blue term 2
term on the right-hand side of (27). Following similar steps, we can get the iteration complexity make pTz S <eis *+
n 5
CoynLy VSp
nLjoo
c7o7
8²
970
+
+
+
BSc
nBe
USe
D.2. Convergence Analysis of the Convex Case with Possibly Non-smooth f; (Section 3.3.2)
As discussed in Section 3.1, we can choose vi = 111 113 for the cFCCO problem with non-smooth f:. We present our result with general pty-strongly convex and L Lg-smooth listance-generatie function vh., which subsumes the quadratic one. The following lemma extends Lemma A.2 in Alacaoglu et al. (2022) mini-batch sampling and general smooth and strongly convex distance-genen generating function tht.
Lemma 9. The following holds for Algorithm with L-y-smooth and pts-strongly convex 1/s and any A > 0 satisfies that
T (Up(u.we) (v. I -U (0((4111 n
E
(30)
< (Us(y. vz) Uply. ((.1)) Tλ (Up( (c) Uply, 00.1))++))
T [(-
L2 Xines
E(Up((e+1 80ll
11
where 9/41 = arg wig, f-o + nd Usi (v, (v. ) and 1 = -=V-obsu(()) +V + "V
21

---

A Near-Optimal Single-Loop Stochastic Algorithm for Convex Finite-Sum Coupled Compositional Optimization
Proof. First, we can make the following decomposition.
Uv(, Uw 11 - _ U (T)++11,31) -5 vi) - s
(31)
T UV. Be+1)+ + (S - ()r (v(.))).
Uv(u 20+1) - - U ve) + 5 Ue - n
n
ns
We rewrite the last three terms above as follows.
_ (142)) + (S n)T VV.
(V.
5
n
ns
()) (s(v(21) (y(0) vit1) VoL - I n
Σ (1)011))~:1011111 (y(0) offi)) ( V(((O(11))
S
(S - n)T
Σ (1) - )x(()))) -w(() - ))( T (o) ))
+
nS
1=1
(1(0H+1))
n
(1.01111) + n S velur())
- Σ
(elvett) + veulolfi) + n S
s (vu(o(")) ()
12
s
s
s
i=1
n
n
(8)
1 0it1
(S - n)T
VV (1))
+
nS
Note that both 1 and yi (
(i)
are independent of St such that
E (1:1)) 1) Gel = S
+ n S = S n
(0) v/: (1(11)
))(()"))
n
ViL with) ) C
(1)
(Ve) (o(f1) De+1/ / + n-S S
(1)
(.))))))).))))) (0)
E
n
E ( &i] S Vvi( + n S (ei(ul (7)).
n
n
Apply Lemma 2 to i with A (0) == V.s (1 + Veb + " Vet((.))) 0221 ain, ( + aUs, (v. )} } (a to be determined) such that
E (4
(0) (0)
S E |Ul,, (v (( al ()) [.6t11 + 2p
||
E
Sum both sides from 1 to n and divide n on both sides
ب 11:
E + < E n
(U+ 0c) (o(s,0++1)) + 2m1u E
Σ
Note that (((V (6) ) Vot (0) Gi] = (V(Vi - vol((ul such that
E
1 3
=
EE
(Vo.Cl - Vo)(((')) S (Vico(ff)) - verco 1[,
n -
-V
|.-
Thus, we have
at (U (v. 01) - Uvly 0c+1 + Tn Σ E
-
?
< E
(32)
2
The last term above can be upper bounded as
n
(V.(o - Ves(ee )| v
T
2 E
|
uit1
- v
S
240 S
Choose 2d1 for some A > O. According to (31) and (32) and Ell 25 Up (Wt+1, Mr), we can finish the proof.
Ge]
- 11 1 -v
22

---

A Near-Optimal Single-Loop Stochastic Algorithm for Convex Finite-Sum Coupled Compositional Optimization
D.2.1. A SUPPORTING LEMMA
Lemma 10. Under Assumptions and the following holds for Algorithm with 0 1 and any X2, A3, X1, As > 0, y EV.
n n
((g((1)+1)= - ) 5
(33)
-[[T++ 1+1 Tı] + 222 (v.br) Uw (c..) As BU, Ue)
Uv Øt+1)]
n
(A3 + 1A) (Bt+1, ve]l
C2 - sell? Rz 10te- - 112
90d
oi
o 275Ju B
Hun
2d3
2dx
THe B
Aap
where Pt. = +. --=,(((())) - (:(x)-1))) (y - ) (dch2o tiet220 are virtual sequences constructed as
0/41 = arg mingey, to (gi( B, (x())) + >ZUUp (v, )3 Mh4t = arg min to (g((x)-1: gi (x( +
(v, vl)) for each E [n].
Proof. The term + Ei= -i=1 (1:((4+))) - -
(10 lit1) can be decomposed as
(x) -
9. (x)( -
(34)
1 + 8
(gr( (51 (1) -
Σ
22
9e ge( (Ty() - 1 (1(0)-171
1 n
Σ
9e (3t) (( Ty(()
(1)
Veti)
yit1)
n
0 n +
0 n (g. - (1) -z))) n
(0(( -
82-1)
71
mII
Note that our ALEXR (Algorithm 1) only samples B.d for those i E S in the t-th iteration. For those i E St, the batches (B(") higs, are virtual and introduced solely for the convenience of analysis, which are not required in the actual
execution of Algorithm 1. For each i E (n]. define (.()) == arg max {v 9t [1( - -U (v, (v) and ge =
(1)
(x,)) + (xx( (I(-))) We decompose the term in (34) as
I 1+ 0
Σ
( - (((r::(())) (T (g v
n
1+0 0
Σ
- 9 )) (1221 vli (0:(2x) (: BT T -9x((x.) ( (=(=r:B0))) bif1
Since fir + -U,, w/ is T strongly convex, Lemma 3 implies that
E
1 (xr) (x 1) (3171 D(41) n
(0)
E (I:()) - gi(xe; 1o..B,))11) |||~ l1 Det1ll
E (1or((t))) (1
- gi Bl I|- + 01gg((xe-1) ge (: (,:)), )1.)
1 n
-x E (1 + 1.500) (x)(())))) - (,:; B,o) )
(x. - g (1 1,0 M13]
(1 (1+ 20)0z 7 BBp
TT
Apply Lemma 2 to the term (o - (z (10 (1)) For any X2 > O and the auxiliary sequence (0x) constructed as
(()) = arg min {u (gi(x;; B(a)) g (xx)) + >2U (v, )(")) for each i E [n], we have
71 Σ (g)( (( y0) < 22 BU bn) Vv(uveer)) 2xzuen
n
Ellg(1e) 2 g( g(x;;;(()))) )1.
1
n
23

---

A Near-Optimal Single-Loop Stochastic Algorithm for Convex Finite-Sum Coupled Compositional Optimization
Lastly, B[(g)( - (:(2;;
1) Diー1 Ft-1] = 0. Choose 0 1. Then, the term in (34) can be bounded as
222 BlUp(U.DDe) D.) (o((.De41)) X2 B
ob
6o
B v n
(35)
Define re == 1 Σi= (Tx( - gi ( )) (1/() - v1²)) For any d3, > 0, Il + III can be rewritten as
I1 III+
1
( (g/0) -9(+1
(6)
1 n
Σ
( (g - -iif
- (v) De+1)
n
n
= =1++1 - Pe +
(g.(xc(1) (((1))) (wi+1 - Dettl
(8)
)+ + Σ
(0(-)) g((x))) (vl - Ditt)
1=1
1=1
02 |
21
As -
02
||,, - xc- 112 +
da 1lve M++1ll
- P +
+
+ g
2d3
2n
2\
2n
Note that Mi+1 Dit1 if E St and Mi41
Vi
otherwise. Then, ||ve+1 - Dt++11 S 11 - -b++lll 11 such that
Cg |1++1 - 2e112
Cg 1aa - Ft 12-1112
(As us) (1++,,))
Il III S l-1 Te+
(36)
2X3
2
Pvn
We decompose the IV term in (34) as
n IV
((((0)11:B)))) -)) 81121
1((0) ( ()_ (Vif1 -bfh1)
n
+(1.(111::(9)) (xx y0) (0((x.-1::())) 1)( (T) }
By the [9((0111:())) - ()( - v(41)) S [[()(0)-1::())) - - v2fil]]
we have
Since (1) + -UN; ((()),1()) is Tup- convex to y()) Lemma 3 implies that
1i 1 < (1+ (119)11(( - g: B())) I|I + 011g((1(11) - (; ||
Jpp
Similar to (35), the following holds for any As > O and the auxiliary sequence (ūo h2o that is constructed as of
arg migmin,,x mx fu T (0((F1-1: - ()) + (v, (()) for each E [n].
1 E (11(11a1111²)))) (x 1)) (0)
I As ElU (.) Uw D+ + 2 B
o
n
n
Consider that 1 Σ
E((g (z+ 11: )( - g. 1)) 110 = 0.
E[IV I As El u (3. i)) Uvl de+1)l +
of
301
(37)
2A T
n
Combine (35), (36), and (37).
n n (()(()))))) - 0t ((y v(41)
< ETT.. 1 [t] + 2 (w.
Up(v. AB B.) Uv kt+1)
A
n
m
(As + XE) v (1c+1, v13l
C2 - 22l
Cy |, - 112 112
90
oi
o
Myn
2d3
2
T
dap
2 B
24

---

A Near-Optimal Single-Loop Stochastic Algorithm for Convex Finite-Sum Coupled Compositional Optimization
D.2.2. PROOF OF THEOREM? 3
Proof. If 9: is smooth, we combine (15), (21). (30), (33). Set x = 2, and 2g = I-1
((+1) (F.,DD+t))
I s SEUU v1) - Up(V, 9c+1)l + TA
B(U - UV. 0(+1)] + " ||,,, -xell2 - 11+ 12+1112
5
222
As BlU k1) Up (v. +1++1l
+ E[T++1 - -To]+ +
B(U (V, 21) dc+1)] +
n
n
d A d
E [(U+((++1.()]]
11
C
Cs
E ||2211 mell
g
E
|
Pon
2
2X3
2
90
ob
o B
O7 nB
82
+
+
+
+
(38)
THuB
B
Ss
Do telescoping sum from t = to T 1 for the equation above.
E [[((x++1.8) L( N4+1)
BB ||a:- - ru rull2
B(UUp(U.BO)
I
+ Tr S
B(U 00)]
2
21z
As BUU.U bo)l +
B o (v. do)l
2
s
n
T
d
T-1 Σ
B vk)]
( 17
C
T-1
Σ E
|
2211
n
Hun
2
2
2X3
2
C7o7
8²
g0
o TT
T
+
[T]
3 (IU
+
T
5
Bn
Sn
TH B
22ply B
2 B
Note that To = 0, S Σー (xT) g gx(TT-))1 1)1 (1()) y/
S
|
21-1
As
(g. vr). Choose
2xg
2npe
13 Xi Spo
x2 5 A3
C.V3 A4 x
C.V3
As x 15 and let T/T = 0
Vill
and 1/11 1/1=
=y=00 0
v5
Since L(x,
vn
vn
CSVS
Covn
is convex x and linear in y, we have
T-1
E Emax[L(Tr.a) v) L(x., br)] S E max
[[ - ([(t,,,,))((,,,,))))) I(I=,
(39)
y
T
where 2y = ET= Te+1, Wr ET= Ve+1. Now work on the LHS.
L(FT.V) y) ((x,,rr)=
1 n n Σ - + +r(ār)
n Σ
1
(0) Fr -(xx)))((("")))) (i1) - r((x))
Choose y(t) = (10 E arg max max, (ug:(TT) - (v)} & gi(Tr) E ", + (0 E (f(()(TT) such
that /1 g.(()))) fí (16))) f(()( By Fenchel- Young, - (x.) + f: 2 (x()(())) Thus,
( F(x:.) S (Lax,(L(TT.a) v) ((),,T)).. Thus, we can make E(F(TT)
- F(x.)) S e after T
L2 Dx
C,(1+13 ((S D2g
Set +
D303 aau (555(5)))))) BC
iterations by setting 0 1,
USc
noVnSe
Me BSc
0
VBCg
V
2
,1 0 (L,C, V
VnC, vS
v 8
V ofot
Be
Se
Be
25

---

A Near-Optimal Single-Loop Stochastic Algorithm for Convex Finite-Sum Coupled Compositional Optimization
D.2.3. PROOF OF THEOREM? 2
Proof. If gi non-smooth, we can use ALEXR with 0 where g.th gi(2r;; B( Then, for any À > 0 we have
I (s (14+1) N..y /
(1)
1
Σ
E
(3 (1++1)
1e(sos; ), y, -bif1)
n
i=1
ge - 96 (xx), (x))
- }}
a
slof1 }
E
E
72
11
E
119. (10+1) - (i(22))l.
(1(00 (1) ||
1
E
{ ot (zx))
g2 B, y, - -b(21)
C
1o+1 - xell2
1 n
+ +21
Σ
Billy (0 + |
(1)
E
( gi (1ze B, 10) ),0²)) -b(it) >
211
==1
C
||:2
+ C2 +
Σ (1x)
slif1) )
2
The last term above can be decomposed as
9b (are) - 9s ni; Bb()) -0 v(tl)) }
E
n
1
Σ
Ee (xx))) 9i (01: -000= v1 {62)]] + 1
(21)
E (9 (2x) - ( 1899-111 -
(40)
n
Note that E (9i - (i (B(F1
v1 v.)
Fe-]]
O. Besides, Lemma (9) implies that for some X2 >> 0 and sequence
3e
gi( E (())) ).)) s (1 (v [6hh)] +
9i (2re) gx
(x(::: 1/
2222u
such that
n n
E (o (2x)) - 9: (m B(o)), ),(()))
d2 A Up (v. - Up (v. 0v.0 +
of 22g
S
For any da O, the second term in (40) can be bounded as
E
11 Fe+ 11?
1
E (as (2re)
(r B(") (2) w/f1)
A
EE
99 (are)
9s (1 )13
n
2n
22gm
A3a
E [U (Te41, wcl1
2B
AsHan
Thus, we have
CE
||0141 - xell2
Di (1141)- Hc, (0) - Beti) )
(1))
4x103 + A2 E D.) - Us (v.
E
<
2
Bosy
E UU (1++1.
2BA2
2B
2aauyn
The other parts are the same as as the proof of Theorem 3.
26

---

A Near-Optimal Single-Loop Stochastic Algorithm for Convex Finite-Sum Coupled Compositional Optimization
E. Proof of Theorem 4
consider a special instance of problem (1) that separable over the coordinates and P; = P.
min F(x), F(x) 1 Σ f(a((x)) + -h ||0||
(41)
ze| SEI-D.DI-
(xxx) Re (arrlli O), gi(2; () = x00) + C,
where the additive noise Ç follows
-= VV w.p. 1-p. P.
v²
where p = σ² E (0,1).
u(1 p)/p
w.p. p.
We construct the hard problems for (i) smooth fú: and (ii) non-smooth Si separately.
(i) Smooth fi: First, we can consider the special instance that fi is the identity mapping and 5 = 0 (e.g., all ft's are identical), do = O. Then, the cFCCO problem (1) becomes the standard strongly convex minimization problem. Then, we can apply the information-theores scheme requires least Q( jec
lower bounds (Agarwal et al., 2009; Nguyen al., 2019): Any algorithm in the abstract iterations to find an such that / || z. S c.
0.4
1.0
0.3
100
0.2
0.5
0.1
0
f(-))
0.0
(a) Visualization of f (42)
(b) Convex conjugate f in (43) Note that (y)
+ in grey areas.
Next, we construct another "hard" instance to derive the second half of the lower bound in this case. Consider the following strongly convex FCCO problem
minF(x) xEX
Σ f()(())) rr(x),
n
(v- 1y--1u++: (v- 1)2 + -- 1- mE (-,,--1)
f(u) =
2) 2 (1+ [[1+v} -
uE [-11] 2 u M (1,
r(x) = 4n ||
(42)
where X' [-1, 1)a, the outer function f - is smooth and Lipschitz continuous for v < 1. As stated in Assumption do not require ff be monotonically non-decreasing when g; is affine. Choose a that (z) = (z)) + H (1 such that F(x) = Σ (.( Thus, the problem min, F(x) is equivalent to the problems min,.c ((( on all coordinates E [m]. Since the problem is separable over the coordinates, we have y = arg min F (x) for x. arg min (xx). Thus, we have (1))) and (x( -/- By the
(41). We define
27

---

A Near-Optimal Single-Loop Stochastic Algorithm for Convex Finite-Sum Coupled Compositional Optimization
convex conjugate, for any y()) E R we have
wy(" - 1) 1)- 1)² + - -1- (/2
}
1²²
ugy (3) 3 (u + 2)² + n²
()((0) = max
sup au--1
sup -IsuSi
2
2
uy (1+ (1+ + 1 2 (1+ 1²
sup u>1
2
+00, (0(
y E (-00, - (1
(43)
u) y E -u--1,0 1,,+,++11 l].
Since PP = IP in the "hard" problem (41), the abstract scheme only needs to sample shared Ce: &e IP for all coordinates
i E St in the t-th iteration. For an i E [n]] suppose that of" = {0} or [-v), " = {0), x!x = {0} for all T S t. Then,
If & St. the abstract scheme leads to
9 {0} or {-v),
2i4 = {0).
x = (0}.
if E St and S. = -v, the abstract scheme proceeds as
0++1 9i + span {000 + Ge $0 E xx,")
(1)
2if, = (0 + span
y (0 - 1 -1
(1r // E ( 0 00) E 2
arg max 11,
2
x = x/ + span
arg min E [111]
10000000
+ - (2)) + " (1(00) - =(0)ee] g(0 E 2i11 20 E x
2
(6) (-v such that y yd (g - v) = 0 for g(D E i vi E S. Since 1 (1)00) +
(0)
In this case, we can derive that Di+1
TUp, (v(0) g()) is strongly convex to (()) and non-negative, we have 2(4 = {0} for i E S. Then, x/f = {0} for i E S..
To sum up, given the event n (oft = {0} or {-v}. / = (0). xLn' = {0}}, we can make sure that {off1 =
{0) or [- A D = {0} x 1-1 {0}} when one of the following mutually exclusive events happens:
Event I: E Ss;
Event II: i E St and G. -v.
Note that the random variable & is independent of S.. Thus, the probability of the event Eti = (0/f1 = 0 0r (-v) A
2 2+1 (1) = {0} x = {0}} conditioned on N'=n Et can be bounded as
P
E
E
{ (6) g = {0) or (-1) A 222 = (0) A xxll = [03) n E(()
2 (i & 8.) + Pif E 8.) A (G = =11}
PP i( & S + Pii E S. H[G = --}] = [
S
S
Sp
+
-111- - p) = 1
n
n
Since S, and & in different iterations are mutually independent, we have
P
PPPP
T-1
II
P
E 11
(1
Sp
T
3/4
TSp
(=0
n
n
Thus, letting T <<< n
can make P(E())
z. Choose v = 3 and a = oo such that
3
18c o
For any i E [m]] and
15p
σz
any output 27
x+( we have
B( x ===)))]==
= E[ pl
(5 (1)
x 12 +1
(x/7)) - xz [ 2 ET
ptu
(5
x )
E
= = ا (I. [ = P
(6)
2v²
4e.
28

---

A Near-Optimal Single-Loop Stochastic Algorithm for Convex Finite-Sum Coupled Compositional Optimization
Since the derivations above hold for arbitrary i [S] and the r(x) in (42) is 2n -troongyy convex (n- ) we have
"
E B x.112 = 4n
E |
F= 11
- x. -
)
2
4n
Thus, to find an output रy such that ş ||
x.112 S e, the abstract scheme requires at least T 2
n 15p
ngg 728t
iterations.
(ii) Non-smooth fiz We borrow the construction fi(.) = 8 max(::-0) from Zhang & Lan (2020). We define that (xx(0) == [(g (x)) + [[=(0)2 = 3 max(x!)) - + / [x.10]2 such that F(x) = E R (xx()). Let the domain X' be [-2v, 20) Since the problem is separable over the coordinates, we have w. arg zel Fi(x!() arg 2 {.3 max(x("),
-v} + (z) for x. arg minzex F(I). We have
{ - 3/a a > B/v
R(x!)) - 1 (2a) if > 3/v
U if E 1]
-Bu/2 if 0.
[. By the convex conjugate, we have Since (O) = 0, we can derive that F,(0) (f(x) N min min /2/aa.
(( max _0,)
g0"g0))) v(3 y ()
Due to similar reason as in the smooth fi case, the probability of the event Ef" = {00 = {0] or
{-1} A 22
{0) A x {0}} can be lower bounded as
T-- P
Sp
TSp
P
P
P1+1
P
E
F
(8)
1
3/4
n
n
1=1
Thus, letting T <
n
can make P [E
> 2-
Choose 3 = Cy. v =
de c,,
and o = ou such that p = 0²
.2
16c² C703 .
For any
4Sp
i e [n] and any output oi E 2 we have
E (()) (z( (8)
E
T E
(R(E F((o.)) + FXG
(F((F()) F(CE"))
[ (Fi(E()) Fc(c:())]
2 R [Tp
Fx(x!") (8) })] = = (F(0)- (Fi(0)- P.((E min 8 (x) /4
E
((t))
(:(0)
Since the derivations above hold for arbitrary i E {S), we can derive that
B[F(ār) - [(xx)) = 1 n Σ B[F((E1)) - - >e.
nCia
Thus, to find a ïт such that ([F - F(xx)] S e, the abstract scheme requires at least T 2
iterations.
45p
645
F. Application to GDRO with o-divergence
We discuss two examples of the GDRO problem with d-divergence: CVaR divergence with a hyper-parameter a E (0, 1) and x² -dvveeegeee with apper-parameter À > 0. We compare ALEXR to the following baselines:
SMD (Nemirovski et al., 2009; Zhang et al., 2023): It can be applied to the GDRO problem in (7) with CVaR divergence, where the dual mirror step with the entropy gennerae-gnnerating function can be efficiently solved by projection onto the permutahedron (Lim & Wright, 2016). Moreover, SMI) can also be applied to the worst-group DRO problem (Sagawa et al., 2019) (i.e., À = 0 in (7) or a = 1 in CVaR). The iteration complexity of SMD is T = O Log ). Besides, it requires Onn log n) computational cost for performing the dual projection and On)) oracles in each iteration. Note that SMD cannot be applied to the GDRO problem in (7) with =divieegee due the non-linear penalty term.
OOA (Sagawa et al., 2019): This algorithm can be viewed as variant of the SMD algorithm with the dual gradient né
)......) O] for some i E [n] such that it only requires O(1) oracles per iteration. But the dual estimator [o....,nl(w;, (wi; =t (6.).
29

---

A Near-Optimal Single-Loop Stochastic Algorithm for Convex Finite-Sum Coupled Compositional Optimization
Table Comparison of iteration complexities, dual projection cost, and per-iteration #oracles for achieving e-optimal salution of the GDRO problem in (7) in terms of [B|F (weu)) F [ww)] I é in the merely convex case and & || w. 112 I с in the je-ttrongly convex case, where Four the output of each algorithm. We hide other constant quantities except for n. variances oū of 8", and batch
sizes S. Besides, O hides poly log(1/e) factors.
Diveereenece
Algorithm
Per-Iter #Oracles
Dual Proj.
Iteration Complexity
SMD
O(n)
O(n n)
CVaRR
00A
Q(1)
O(n no)
ALEXR
O(1)
((1)
0 (
BS
Merely Convex
Strongly Convex
x²
ALEXR
O(1)
O(1)
ngd
62 uSe
Ay.c
Ay/S
The worst-case estimate of f2) is zuz. but could be much smaller than I=
in practice, as explained in Remark F.I.
projection cost in each iteration is still (n log n). The iteration complexity of SMD is T = 0 log n which is also independent of a. OOA is not applicable to the GDRO problem in (7) with ---divergence either.
comes to our attention that the NOL algorithm (Zhang et al., 2023) designed for the worst-group DRO problem, i.e., A
in (7), can achieve T O 2 =l iteration complexity in high probability with per-iteration O(1) oracles. However, this result cannot be extended to the GDRO problem with CVaR or x "ddivergence,, since their proof technique relies powerful tools for multi-armed bandits. Besides, Soma et al. (2022) also consider the GDRO problem with CVaR divergence but their convergence analysis suffers from dependency issues, as pointed out in Zhang et al. (2023). Recently, Hu et al. (2023c) studied non-smooth weakly convex FCCO problems and proposed an algorithm SONX, which can be applied to solving GDRO with CVaR divergence. However, their algorithm does not leverage the convexity of the inner function and hence suffers from a worse complexity of O SyBea
F1. GDRO with CVaR divergence
GDRO with CVaR divergence can be formulated (1) with f.()) aa) E (0,1) and gi(w,c) = R:(w) such that Cf and Cg CR + 1, where CR is the Lipschitz constant of Rg. The dual update (7) of ALEXR with (6) Projp -ylb + (1/T)g("', S. (
(6) (-)() [ (.) has the closed-form expression Ve+1
1/
i S
The worst-case estimate of the 22 term in Theorem is 29 S " = 2σ5 when vh (.) However, it could be much smaller than z in practice since g(+) = 0 for those coordinates that satisfy R((w)= S ē, i.e., the ALEXR algorithm can benefit from the "sparsity" of g()) E (g 2)), where (w, é) is the output of the algorithm. In particular, when (w, 2) is close to the optimal solution, then roughly about an number of groups such that [R( - d+ > 0. As a result, maC?
26. = E
1 Up. (g())
Za
E2. GDRO with x divergence
GDRO with x- divergence can be formulated as (1) with fa(-) = A (: 1) and giw, c) = (R((w) - c)/A such that C, = max Bg Bate) and Cg- = Ca+1 where BR == max,, [R((w) and valid choice of 7 -X, Br (See Appendix A.3 in Levy et al. 2020). In this case, the proximal mapping of f; (1 20 with vi(+) = { can also be efficiently solved. We can also consider the GDRO problem with a convex regularization term r(z). We can choose either v, = f or (.)-)) = ())
F.3. Comparison with Baselines
In Table 4, we compare our ALEXR to the baseline algorithms OOA and SMD. is notable that although SMD has a better iteration complexity for CVaR divergence, requires (nz) oracles at each iteration. In contrast, ALEXR and OOA only require O(1) oracles in each iteration. the worst case, we have D2 On/aa2 for CVaR -enalizdd GDRO, then ALEXR
30

---

A Near-Optimal Single-Loop Stochastic Algorithm for Convex Finite-Sum Coupled Compositional Optimization
has better complexity than OOA when 1 o(vn n). In practice, we have ?2 = (O(/a) for CVaR-penalized GDRO, then ALEXR has a better complexity than OOA when o(n log n). In addition, OOA cannot enjoy the parallel speedup with respect to the inner batch size B due to its scaled dual gradient estimator. Moreover, we also provide the iteration complexity of ALEXR on this the GDRO problem with x² -iveerggee,, with or without a strongly convex regularizer.
G. More Details of Experiments
All algorithms are implemented using the PyTorch framework. Experiments are conducted on a workstation with the 12th Gen Intel(R) Core(TM) i7- 1--1200KK CPU with 20 logical cores.
G.1. Group Distributionally Robust Optimization
G.1.1. DATA PREPROCESSING
Adult dataset: We construct 83 groups for the Adult dataset according to income (">50K", "=50K"), race ("white"" "black", "other"), sex ("female", "male"), age ("S30", "30-45", "><5"), relationship ("single", "nno_single"), and education ("higher", "others"), where discard those groups with less than 50 data points. Following Platt (1999), transform both continuous and categorical features into binary features, resulting in 122-dimensional feature vector for each data.
We construct 160 groups for this dataset according to 4 binary attributes ("blond hair", "male", "mouth slightly open". "smiling") and 10 types of additive Gaussian noises (means -0.08:0.02:0.1 and variance 0.08) to the images. Each image of the CelebA dataset is resized to 224x224x3, normalized, and center-cropped. Then, we extract 512-dim feature vectors for those preprocessed images from the last convolutional layer of a ResNet18 pre-trained on ImageNet.
CelebA dataset:
G.1.2. ADDITIONAL RESULTS
The first two columns of Figure show the existence of rare groups in the datasets. The last two columns of Figure 3 demonstrate that the actual value of 22: is indeed much smaller than its worst-case estimate 2az which verifies the claims in the remark below Theorem 3 and Section F.1.
Adult
ColabA
((2) V.S. a-0.15)
CelebA (1% V.S. T. a=0.155)
2000
30
32000
500
730
1750
ALEAS
2000
Populations
1509
Aapellettonn
1500
2300
3000
Aetiicia HEREA
1000
15000
10000
750
5000
500
500
Groups
Groups
Iterations
Iteratiion
Figure 3. Group populations and the computed values of 129.
G.2. Partial AUC Maximization with Restricted TPR
Table 5. Statistics of datasets used in the partial AUC maximization experiments. Here n4 and n.. refer to the numbers of positive and negative data the train and validation splits.
Train
Validation
Datasets
n2
n_
n4.
n_
Covtype
889
178,587
252
59,573
Higgs
4,676
4,172,030
582
499,418
Cardiomegaly
1,950
76,518
240
10,979
Lung-mass
3,988
74,480
625
10,594
31


Reviews:
[{"review_id": "FjHRSV8CeO", "reviewer": "Reviewer_7wWG", "summary": "This work studied convex FCCO problems, by reformulating into a convex-concave min-max problem, this work proposed ALEXR algorithm by incorporating coordinate descent and SAPD, the convergence guarantees are provided, also the lower bound analysis show that the complexity of proposed algorithm is near-optimal.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for taking the time to read our paper and greatly appreciate your valuable feedback.\n\n> **Q1:** For the lower bound part, there seems to be no clear definition of the oracle, regarding the layer-wise structure, you need to access $\\nabla f_i$ and $\\nabla g_i$ separately, also you further need to compute the proximal operator, I expect you can explicitly state the definition of the oracle, with the corresponding input and query output, similar to Zhang & Lan (2020) as you cited.\n\n**A:** The oracle complexity in lower bound corresponds to the total number of calls of $g_i(x;\\zeta^{(i)})$ and $\\nabla g_i(x;\\tilde{\\zeta}^{(i)})$ required by any algorithm within the abstract scheme to achieve an $\\epsilon$-accurate solution. In addition, we assume the proximal mapping of $f_i^*$ can be computed when $f_i$ is non-smooth similar to Zhang & Lan (2020). Nevertheless, the number of proximal mappings of $f_i^*$ is bounded by the number of calls of $g_i(x;\\zeta^{(i)})$.  We will include this clarification in the next version of our draft.\n\n> **Q2:** The lower bound result $\\Omega(\\max(S/\\mu,n)\\epsilon^{-1})$ looks weird to me, I think lower bound should be problem-intrinsic and depends on the function behavior, so the dependence on $n$ and $\\mu$ (intrinsic problem parameters) looks fine to me; but $S$ should be a user-specified parameter, if $\\mu$ is small enough, then you can choose $S$ to have a varing lower bound, which looks weird to me.\n\n**A:** Thanks for your insightful question. While the lower bound naturally depends on important problem parameters such as $n$ and $\\mu$, it is also tied to an abstract update scheme that describes how the space of the iterate evolves across the iterations.  Please note that $S$ is a parameter of our abstract scheme presented in pg.6, which covers the typical setting $S=1$ for lower bound analysis of randomized coordinate algorithms (e.g., Ch. 5.1.4 in [1]). We intended to be general so that the abstract scheme covers our ALEXR and some baselines listed in Table 1.  Our lower bound $\\Omega(\\max(S/\\mu,n)\\epsilon^{-1})$ characterizes the different behaviors of the abstract scheme in two different configurations of the problem-dependent parameters $n$, $\\mu$:\n- Case I ($\\frac{n}{S}>\\frac{1}{\\mu}$): In this case, the problem's hardness primarily arises from the high dimension of the dual variable $y$. Here, the block-coordinate update of $y$ makes the term $\\frac{n}{S\\epsilon}$ dominate the iteration complexity, resulting in an oracle complexity bound of $\\Omega(n\\epsilon^{-1})$. Increasing $S$ makes more coordinates of $y$ are updated per iteration, thereby reducing the number of required iterations to find an $\\epsilon$-accurate solution of the whole problem.\n- Case II ($\\frac{n}{S}\\leq \\frac{1}{\\mu}$): In this case, the main hardness of the problem is from the ill-conditioning of the stochastic proximal update of primal variable $x$. Thus, increasing $S$ (i.e., updating more coordinates of the dual variable $y$) does not improve the leading term $\\frac{1}{\\mu\\epsilon}$ of the iteration complexity, leading to a higher oracle complexity.\n\n> **Q3:** The algorithm for nonsmooth case works for simple $f$ only to compute the proximal mapping. Even though authors provided some examples for illustration, but the restriction may still hinder the applicability of the algorithm in general nonsmooth functions, compared to existing works.\n\n**A:** We agree with the reviewer. However, existing works on cFCCO that only require computing the gradient of $f_i$, either focus on smooth problems (e.g., SOX and MSVR) or require a gigantic batch size to converge (e.g., BSGD). All of them have suboptimal complexities. Our work is the first to study the more challenging non-smooth cFCCO problem and achieve the optimal rates. In cases where the the proximal mapping of $f_i^*$ is not easily computed, our algorithm can be combined with an approach that solves the proximal sub-problems inexactly (e.g., [2]). Then, the convergence guarantee can be still established.\n\n> **Q4:** What is the potential obstacles if you extend your cFCCO problem from finite-sum to stochastic problem ($\\frac{1}{n}\\sum_{i=1}^n f_i$ to $\\mathbb{E}_i f_i$), or you just intentionally choose the finite-sum problem in the study?\n\n**A:** If there are an infinite number of $f_i$, our reformulation and algorithm cannot be applied directly, because the dual variable $y$ becomes infinite-dimensional. Hu et al. (2020) considered a more general setting that covers the stochastic problem, but their algorithm requires a large batch size to converge (in both finite-sum and stochastic settings). Given the broad applicability of the finite-sum structure in machine learning, we believe this is an important class to study.\n\n**Refs:**\n\n[1] Lan, 2020. First-order and Stochastic Optimization Methods for Machine Learning.\n\n[2] Wang et al., 2017. Inexact proximal stochastic gradient method for convex composite optimization.", "claims_and_evidence": "The claims come with convincing evidence in general. Here are some questions or comments:\n\n1. For the lower bound part, there seems to be no clear definition of the oracle, regarding the layer-wise structure, you need to access $\\nabla f_i$ and $\\nabla g_i$ separately, also you further need to compute the proximal operator, I expect you can explicitly state the definition of the oracle, with the corresponding input and query output, similar to Zhang & Lan (2020) as you cited.\n2. The lower bound result $\\Omega(\\max(S/\\mu,n)\\epsilon^{-1})$ looks weird to me, I think lower bound should be problem-intrinsic and depends on the function behavior, so the dependence on $n$ and $\\mu$ (intrinsic problem parameters) looks fine to me; but $S$ should be a user-specified parameter, if $\\mu$ is small enough, then you can choose $S$ to have a varing lower bound, which looks weird to me.\n3. The algorithm for nonsmooth case works for simple $f$ only to compute the proximal mapping. Even though authors provided some examples for illustration, but the restriction may still hinder the applicability of the algorithm in general nonsmooth functions, compared to existing works.\n4. What is the potential obstacles if you extend your cFCCO problem from finite-sum to stochastic problem ($\\frac{1}{n}\\sum_{i=1}^nf_i$ to $\\mathbb{E}_if_i$), or you just intentionally choose the finite-sum problem in the study?\n\nWith that I think the work provided some interesting results for cFCCO, while some novel contribution should be further clarified to enhance the significance. I am open for further discussion.", "methods_and_evaluation_criteria": "Make sense in general.", "theoretical_claims": "See above", "experimental_designs_or_analyses": "See above", "relation_to_broader_scientific_literature": "This work will advance the theoretical understanding of the algorithms for coupled compositional optimization problem.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "/", "other_comments_or_suggestions": "/", "questions_for_authors": "/", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "vph9sxASAY", "reviewer": "Reviewer_Zg46", "summary": "This paper studies a regularized convex finite-sum coupled compositional optimization (cFCCO) problems: $\\min F(x),  \\text{  where  } F(x) := \\frac{1}{n}\\sum_{i = 1}^n f_i(g_i(x)) + r(x)$. Here, all functions ($f_i, g_i, r, F$) are convex, and each inner function $g_i(x) = E_{\\xi_i \\sim P_i} [g_i(x; \\xi_i)]$ for distinct distributions and is accessed via stochastic oracle queries. The authors also assume that $g_i, f_i$ are Lipschitz continuous (and possibly smooth), and when $g_i$ nonlinear $f_i$ is assumed monotonically non-decreasing, and the variances of the zeroth-order and first-order stochastic oracles are bounded. This kind of problems find applications in group distributionally robust optimization and learning with imbalanced data, which later their experiments study.\n\nThe authors reformulate the problem into a convex-concave min-max problem using the conjugacy of $f_i$ and propose a single-loop primal-dual algorithm, namely ALEXER, which can viewed as a randomized extrapolated coordinate algorithm on the dual side and a proximal stochastic gradient method on the primal side. Convergence analysis and nonasymptotic guarantees are provided for the proposed algorithm, under both strongly convex and convex settings, with improved dependence on the number of components $n$ and the strong convexity parameter $\\mu$. The authors also include certain worst-case examples to show the tightness of their complexity results.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for taking the time to read our paper and greatly appreciate your valuable feedback.\n\n> **Q1:** Assumption 4 looks strong to me: the authors assume the bounded variance for both zeroth- and first-order oracles. What are the assumption (cf Assumption 4 here) the prior work on stochastic compositional optimization made? Do they also require the bounded variance for both zeroth- and first-order oracles?\n\n**A:** All prior works on stochastic compositional optimization make the same or stronger assumptions. For example, the seminal works [1, 2]  assume both of the following hold: (1) The variance of the zeroth-order oracle is bounded, which is the same as ours. (2) The first-order oracle is either almost surely bounded or has a bounded 2nd moment, which are stronger than the bounded variance assumption in our work. Recent works such as SOX and MSVR all assume the same conditions as ours. \n\n[1] Wang et al., 2017. Stochastic compositional gradient descent: algorithms for minimizing compositions of expected-value functions. Math. Program.\n\n[2] Wang et al., 2017. Accelerating stochastic composition optimization. JMLR.\n\n> **Q2:** It seems that the analysis mainly relies on the Lipschitzness of the functions, and the smoothness only helps improve the batch size requirements.\n\n**A:** That is partially true. First, the smoothness of $f_i$ also allows us to derive the optimal complexity of $O(1/\\epsilon)$ for strongly convex problems, which is **better** than $O(1/\\epsilon^2)$ for non-smooth $f_i$. While it is true that the smoothness of the inner functions $g_i$ only affects the batch size scaling in iteration complexity, this is expected, as standard SGD exhibits a similar distinction between smooth and non-smooth problems.\n\n> **Q3:** What is the notation $u_t$ appearing in Section 3.1-3.2 and in the proofs in the appendix? Seems that the authors have refactored the writeup but are not careful to unify the notation.\n\n**A:** Sorry for the confusion, but $u_t$ is not a notation inconsistency. Eq. (3) in our paper shows that if we set $\\psi_i=f_i^*$, Lines 4–8 of our ALEXR algorithm can be rewritten in a form similar to the previous algorithms SOX and MSVR. To be specific, the updated $y_{t+1}^{(i)}$ can be expressed as the gradient $\\nabla f_i$ evaluated at a moving-average estimator $u_{t+1}^{(i)} = \\frac{\\tau}{1+\\tau}u_t^{(i)} + \\frac{1}{1+\\tau}\\tilde{g}_t^{(i)}$. The form in (3) based on $u_t$ facilitates the discussion of relationship to SOX and MSVR in Section 3.2.\n\n>**Q4:** In Eq. (5), it seems that there should be $L(x,\\bar{y}\\_{t+1}) - L(x\\_{t+1},y)$ instead of $L(x\\_{t+1},y) - L(x,\\bar{y}\\_{t+1})$ on the right-hand side, based on the discussion and Lemma 5 in the appendix.\n\n**A:** Thank you for pointing out this typo! We will fix it in the next version of our draft.\n\n> **Q5:** Could the authors explain why they need the extrapolation (Line 6 of Algorithm 1) on the dual side?\n\n**A:** The extrapolation allows us to enjoy the batch size scaling in the iteration complexity by leveraging the smoothness of $g_i$. Without extrapolation (i.e., $\\theta=0$), there is an additional term $\\Gamma_{t+1}= \\frac{1}{n} \\sum_{i=1}^n (g_i(x_{t+1}) - g_i(x_t))^\\top (y_*^{(i)}-y_{t+1}^{(i)})$ on the R.H.S. of (18) in Lemma 6. Directly bound this term leads to a worse rate when $g_i$ is smooth. With extrapolation, we can form a telescoping sum of $\\Gamma_t$ and cancel it out. Similar idea is used in Lemma 10 for the merely convex case. We have the results in the full version of our paper and will include the discussions in the revision. \n\n> **Q6:** I do not quite get how the authors derive $B,S=O(1)$ from the main body. Could the authors explain their choice of $B$ and $S$?\n\n**A:** $B,S=O(1)$ in Table 1 means that our algorithm only requires a constant mini-batch size to converge (c.f. impractically large batch size of $O(\\epsilon^{-1})$ or $O(\\epsilon^{-1})$ in previous work BSGD) and enjoys a parallel speedup using mini-batches. \n\n> **Q7:** For the challenge the authors discussed in Eq. (5), it is usual that the analysis of the algorithm with full updates can be adapted because here one only have randomized coordinate updates to deal with (in contrast to cyclic coordinate methods). Could the authors explain the additional technical challenges here?\n\n**A:** There are two additional technical challenges here:\n- First, our algorithm includes the randomized coordinate stochastic updates for the dual variable, which cause the **dependence issue** discussed above Theorem 2, making it difficult to directly apply standard convergence analyses used in full-update methods. \n- The second challenge comes from the **stochastic** mirror ascent update for the sampled $y_i$, which make it more involved to derive a batch size scaled convergence rate when the inner functions are smooth. \n\n> **Q8:** Suggestions on citing prior works.\n\n**A:** Thank you! We will add these references in the next version of our draft.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "I do not have time to check the proofs in the appendix, but the theoretical claims in the main body look reasonable to me.", "experimental_designs_or_analyses": "This paper provides quite substantial experiments.", "relation_to_broader_scientific_literature": "This work should relate to prior work on (stochastic) compositional optimization, primal dual algorithms, and coordinate algorithms.", "essential_references_not_discussed": "- It would be helpful to cite the seminal works [Chambolle & Pock (2011); Chambolle et al. (2018)] when the authors introduce the min-max reformulation for the original minimization problem.\n- It is helpful to discuss the prior work on cyclic coordinate methods, such as Song & Diakonikolas, 2021.\n- For the min-max reformulation and the perspective of coordinates methods on the dual side, it is helpful to cite the prior work on shuffled SGD.\n\n\nChambolle, A. and Pock, T. A first-order primal-dual algorithm for convex problems with applications to\nimaging. Journal of Mathematical Imaging and Vision, 40(1):120–145, 2011.\n\nChambolle, A., Ehrhardt, M. J., Richtárik, P., and Schonlieb, C.-B. Stochastic primal-dual hybrid gradient\nalgorithm with arbitrary sampling and imaging applications. SIAM Journal on Optimization, 28(4):2783–2808,\n2018.\n\nChaobing Song and Jelena Diakonikolas. Cyclic coordinate dual averaging with extrapolation. SIAM\nJournal on Optimization, 33(4):2935–2961, 2023. doi: 10.1137/22M1470104.\n\nXufeng Cai, Cheuk Yin Lin, and Jelena Diakonikolas. Tighter convergence bounds for shuffled SGD\nvia primal-dual perspective. In Proc. NeurIPS’24, 2024.", "other_strengths_and_weaknesses": "**Strengths**\n- It is interesting to see the viewpoint and the analysis of block coordinate updates on the dual side, though it is natural from the min-max reformulation and the stochastic design on the primal side. \n- The convergence analysis is substantial under convex settings, including both smooth and nonsmooth cases. The authors also include lower bound results.\n\n**Weaknesses**\n- Assumption 4 looks strong to me: the authors assume the bounded variance for both zeroth- and first-order oracles.\n- It seems that the analysis mainly relies on the Lipschitzness of the functions, and the smoothness only helps improve the batch size requirements.", "other_comments_or_suggestions": "- What is the notation $u_t$ appearing in Section 3.1-3.2 and in the proofs in the appendix? Seems that the authors have refactored the writeup but are not careful to unify the notation.\n- In Eq. (5), it seems that there should be $L(x, \\bar y_{t + 1}) - L(x_{t + 1}, y)$ instead of $L(x_{t + 1}, y) - L(x, \\bar y_{t + 1})$ on the right-hand side, based on the discussion and Lemma 5 in the appendix.\n\n## Update after rebuttal\n\nI appreciate author's responses, and they addressd my concerns.\n\nI found this paper is interesting, from the aspects of (cf) nested stochastic optimization or bilevel optimization, though the complexity results appear to be a bit hard to parse. Possibly other dependece besides $epsilon$ can be improved.\n\nI also suggest:\n\n1. Make the notation more clearly defined, such as $u_t$.\n\n2. Have the batch sizes explicitly stated in the main body and the comparison table\n\n\nOverall, I recommend acceptance.", "questions_for_authors": "- Could the authors explain why they need the extrapolation (Line 6 of Algorithm 1) on the dual side?\n- I do not quite get how the authors derive $B, S = O(1)$ from the main body. Could the authors explain their choice of $B$ and $S$?\n- For the challenge the authors discussed in Eq. (5), it is usual that the analysis of the algorithm with full updates can be adapted because here one only have randomized coordinate updates to deal with (in contrast to cyclic coordinate methods). Could the authors explain the additional technical challenges here?\n- For Theorem 2, what is the step size constraints for the algorithm for smooth $g_i$ and $f_i$? Do they still require $O(1/\\epsilon)$ small step sizes, or they only depend on the smoothness constants?\n- What are the assumption (cf Assumption 4 here) the prior work on stochastic compositional optimization made? Do they also require the bounded variance for both zeroth- and first-order oracles?\n- What is the key challenge of removing the monotonicity assumption of $f_i$?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "SmFlx6UEZF", "reviewer": "Reviewer_tEp6", "summary": "The paper presents ALEXR, a novel stochastic algorithm for convex Finite-sum Coupled Compositional Optimization (cFCCO). It reformulates cFCCO as a convex-concave min-max problem and introduces a single-loop primal-dual block-coordinate stochastic approach. ALEXR applies mirror ascent for the dual variable and proximal gradient descent for the primal variable. The authors establish convergence rates under various smoothness conditions and derive lower complexity bounds, proving ALEXR’s near-optimality. Experiments on GDRO and pAUC maximization highlight its strong performance.\n\n## update after rebuttal\n\nThe authors' response addressed my concern. I’m keeping my score—not because the paper lacks merit, but because there's no option for 3.5. I recommend for accept in general.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for taking the time to read our paper and greatly appreciate your valuable feedback.\n\n> **Q1:** The paper provides strong theoretical results, but there is limited discussion on the sensitivity of ALEXR to hyperparameter choices. How sensitive is ALEXR’s performance to those choices? \n\n**A:** ALEXR has three hyperparameters: $\\eta$, $\\tau$, and $\\theta$. Although $\\eta$ and $\\tau$ need to be tuned, the sensitivity analysis below shows that ALEXR is not highly sensitive to small variations of their values. Fixing $\\theta = 0.1$ seems to work well across all of our experiments and datasets. Thus, the tuning effort of ALEXR is similar to baselines SOX, MSVR, and OOA. \n\n### i) Sensitivity to step sizes\nNote that in ALEXR, $1/\\eta$ is the step size for the primal variable $x$, while $1/\\tau$ is step size for the dual variable $y$. We sweep over different values of step sizes in the Group DRO experiments. The top-tier choices of step sizes are highlighted. \n\n(Adult Dataset, $\\alpha=0.1$)\n\n|Primal/dual stepsizes|$\\frac{1}{\\eta}=$  0.02 \t          | 0.05            | 0.1 | 0.2 | 0.5 | 1.0\n:-----:|:-----:|:-----:|:-----:|:-----:|:-----:|:-----:\n**$\\frac{1}{\\tau}=$ 0.02** |0.776 | 0.804| 0.789|0.782 | 0.770|0.773\n**0.05** | 0.739| 0.716| 0.721| 0.703| 0.719|0.737\n**0.1** | 0.694| 0.691| 0.682| 0.688| 0.704|0.704\n**0.2** | **0.681** | **0.675**| **0.678**| 0.687|0.684 |0.707\n**0.5** | **0.677**|**0.678**| **0.680**| **0.677**| 0.689|0.762\n**1.0** |**0.679**| **0.679**| **0.676**| **0.680**| 0.695|1.074\n\n(CelebA Dataset, $\\alpha=0.1$, '-' refers to divergence)\n|Primal/dual stepsizes|$\\frac{1}{\\eta}=$  0.002 | 0.005 | 0.01 | 0.02 \t          | 0.05 | 0.1\n:-----:|:-----:|:-----:|:-----:|:-----:|:-----:|:-----:\n**$\\frac{1}{\\tau}=$ 0.002**|0.501 | 0.501| 0.501 | 0.500| 0.506|0.670\n**0.005** | 0.497 | 0.487 | 0.490 | 0.486 | 0.493|0.721\n**0.01**| 0.486 | 0.482 | 0.477 | 0.477 | 0.481|0.785\n**0.02** | 0.479| **0.470**| **0.468**|**0.467** |**0.470** |-\n**0.05** | 0.474| **0.467** | **0.461** | **0.459**| 0.484| -\n**0.1** | 0.475 | **0.467** | **0.464** | **0.464**|0.495| -\n\nAs shown in the results above, while the step sizes require tuning for each dataset, they are **not** highly sensitive to small variations. \n\n### ii) Choice of $\\psi_i$\n\nSince the GDRO problem with the CVaR divergence has a non-smooth $f_i$, we report the experimental results of ALEXR with the choice quadratic choice $\\psi_i(u)=\\frac{1}{2}\\||u\\||_2^2$, as discussed in Line 199 of our paper. Next, we empirically compare the results under the quadratic choice with those under another choice $\\psi_i=f_i^*$. We separately tune the step sizes for the choice $\\psi_i=f_i^*$.\n\n| Choice of $\\psi_i$| Adult ($\\alpha=0.1$) | Adult ($\\alpha=0.15$) | CelebA ($\\alpha=0.1$) | CelebA ($\\alpha=0.15$)\n:-----:|:-----:|:-----:|:-----:|:-----:\n$\\psi_i=f_i^*$| 0.7165| 0.6866 | 0.5139|0.4746\n**Quadratic** (chosen in our paper) | 0.6763 | 0.6646 | 0.4593| 0.4521\n\nThe results show that $\\psi_i(u)=\\frac{1}{2}\\\\||u\\\\||_2^2$ is indeed a better choice than $\\psi_i=f_i^*$ for the non-smooth GDRO problem.\n\n> **Q2:** It would be helpful to present and discuss runtime performance across different algorithms, not just convergence speed in terms of oracle complexity. How does the wall-clock runtime of ALEXR compare to baselines like SOX and MSVR?\n\n**A:** Next, we report the total wall-clock runtime for the GDRO experiment on the larger dataset CelebA. \n \n| Algorithms| OOA | SOX | MSVR| ALEXR (Ours)\n:-----:|:-----:|:-----:|:-----:|:-----:\nTotal Runtime (s) | 45.31 | 44.56 | 47.88|45.89\n\nThe result above shows that runtime of ALEXR is comparable to the baselines while achieving a faster convergence rate.\n\n> **Q3:** Some hyperparameter settings are not explicitly stated (e.g., specific learning rates, batch sizes for all algorithms). A table summarizing the experimental setup would improve reproducibility.\n\nThank you for the suggestion! The tuned algorithm-specific hyperparameter settings for the GDRO experiments are:  \n\n|| SGD | SGD-UW | OOA | BSGD | SOX | MSVR | ALEXR\n:-----:|:-----:|:-----:|:-----:|:-----:|:-----:|:-----:|:-----:\n**Adult** | lr=0.1 | lr=0.1 | lr=1.0, lr\\_dual=0.001 | lr=0.01|lr=0.01,$\\gamma$=0.1 |lr=0.01,$\\gamma$=0.9|$\\frac{1}{\\eta}$=0.1,$\\frac{1}{\\tau}$=1.0, $\\theta$=0.1 \n**CelebA** | lr=0.05 | lr=0.05|lr=0.01, lr\\_dual=0.05 | lr=0.01 | lr=0.01, $\\gamma$=0.5 | lr=0.01, $\\gamma$=0.5| $\\frac{1}{\\eta}$=0.02,$\\frac{1}{\\tau}$=0.05, $\\theta$=0.1 \n\nThe shared settings for all algorithms in the GDRO experiments are: \n|| Batch sizes | \\#Iterations | Quantile $\\alpha$\n:-----:|:-----:|:-----:|:-----:\n**Adult** |64 (B=8 from each S=8)|2500|10\\%, 15\\%\n**CelebA**| 64 (B=8 from each S=8) |15000 |10\\%, 15\\%\n\nDue to character limitations, we will also include settings for the pAUC experiments in the next version of our draft.", "claims_and_evidence": "The claims made in the paper are generally well-supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria are appropriate for the problem at hand. The authors focus on cFCCO problems, which have applications in machine learning tasks such as GDRO and pAUC maximization. The use of benchmark datasets like Adult and CelebA for GDRO, and Covtype, Cardiomegaly, Lung-mass, and Higgs for pAUC maximization, aligns with the problem domains. The evaluation metrics, such as test accuracy and pAUC, are relevant and provide meaningful insights into the performance of the algorithms.", "theoretical_claims": "The theoretical claims in the paper are supported by detailed proofs provided in the appendices. I didn't carefully check proofs in the appendix, but they appear to be right based on my previous understanding of existing literature.", "experimental_designs_or_analyses": "The experimental designs and analyses are sound and valid. The authors compare ALEXR against several baseline algorithms on GDRO and pAUC maximization tasks, using appropriate datasets and evaluation metrics. The results show that ALEXR outperforms the baselines in most cases, demonstrating its effectiveness. However, the paper could benefit from more extensive ablation studies to understand the impact of different hyperparameters and algorithmic components on the performance of ALEXR.", "relation_to_broader_scientific_literature": "The key contributions of the paper are well-aligned with the broader scientific literature on stochastic optimization and machine learning. The authors build on prior work in convex stochastic compositional optimization, coupled compositional optimization, and primal-dual methods for empirical risk minimization. They extend these ideas to the cFCCO setting and propose a novel algorithm that improves upon existing methods in terms of oracle complexity and applicability to non-smooth problems.", "essential_references_not_discussed": "Not that I am aware of", "other_strengths_and_weaknesses": "### Strengths\n1. **Originality:** The proposed ALEXR algorithm is a novel single-loop stochastic method for convex finite-sum coupled compositional optimization (cFCCO). It improves upon prior methods by removing the nested inner loop that make previous approaches computationally complex. The algorithm incorporates a primal-dual block-coordinate approach, motivated by the literature.\n\n2. **Significance:** The study has theoretical and practical relevance, proving lower bounds that confirm the near-optimality of ALEXR. It expands the application of cFCCO to non-smooth problems, including GDRO and partial AUC maximization. The algorithm demonstrates superior performance in real-world ML applications.\n\n3. **Clarity:**  The paper is well-written.The comparisons to previous algorithms are well-structured in tables and thoroughly discussed.\n\n### Weaknesses\n1. While ALEXR performs well in theoretical benchmarks, the paper does not discuss practical constraints such as hyperparameter sensitivity and tuning difficulty.\n\n 2. There is no in-depth ablation study on how different components of ALEXR (e.g., choice of $\\psi$ functions, step size schedules) affect performance.", "other_comments_or_suggestions": "1. Some hyperparameter settings are not explicitly stated (e.g., specific learning rates, batch sizes for all algorithms). A table summarizing the experimental setup would improve reproducibility.\n\n2. It would be helpful to present and discuss runtime performance across different algorithms, not just convergence speed in terms of oracle complexity.", "questions_for_authors": "1.  The paper provides strong theoretical results, but there is limited discussion on the sensitivity of ALEXR to hyperparameter choices (e.g., extrapolation parameter $\\theta$, step sizes, and choice of $\\psi_i$).  How sensitive is ALEXR’s performance to those choices? \n\n\n2.  How does the wall-clock runtime of ALEXR compare to baselines like SOX and MSVR?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "6YYAmjzb0T", "reviewer": "Reviewer_J4zJ", "summary": "This paper introduces ALEXR, a single-loop, primal-dual block-coordinate algorithm aimed at convex finite-sum coupled compositional problems (both strongly convex and merely convex, even if nonsmooth). By carefully interleaving primal updates with an extrapolated dual variable, the authors achieve improved or near-optimal oracle complexities, bolstered by new lower complexity bounds that highlight the theoretical tightness of their approach. Empirical demonstrations on distributionally robust optimization and partial AUC show consistent performance gains, underscoring the method’s practicality.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for taking the time to read our paper and greatly appreciate your valuable feedback.", "claims_and_evidence": "The paper’s primary strength lies in its near-optimal theoretical guarantees, achieved through a novel single-loop, primal-dual algorithmic design that replaces more conventional nested structures. This not only simplifies analysis but also clarifies step-by-step convergence arguments, particularly under nonsmooth convex conditions. The authors further bolster the method’s theoretical significance by establishing new lower complexity bounds, underscoring the algorithm’s tightness and rigor. Additionally, they demonstrate clear empirical benefits on group distributionally robust optimization and partial AUC tasks, showing that their approach is both grounded in strong theory and relevant to practical ML scenarios.", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "No", "experimental_designs_or_analyses": "The reviewer briefly looked over the numerical experiments to verify their design but did not check the details.", "relation_to_broader_scientific_literature": "The paper builds on and extends prior work on coupled compositional optimization – notably approaches like those by Wang et al. (2022) and Jiang et al. (2022) – by providing a single-loop alternative to the previously more common nested-loop frameworks. \n\nThe main motivation is the dual formulation (2) of the primal problem (1), inspired by the duality result of Levy et al. (2020). This duality applies to both GDRO and partial AUC. The applications in GDRO and partial AUC are in line with the growing interest in robust and fair optimization problems.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "No", "other_comments_or_suggestions": "No", "questions_for_authors": "No", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "m3Nf3nQlBY", "reviewer": "Reviewer_EbXm", "summary": "The authors study a convex compositional problem with a particular structure and propose a new algorithm called Alexr.\n\n## update after rebuttal\nI think the paper deserves to be accepted and I am confident that the authors will make the recommended changes to make the paper even better.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for taking the time to read our paper and greatly appreciate your valuable feedback.\n\n> **Q1:** Can you tell me if the following papers are relevant? (1) Alacaoglu et al. \"Forward‑reflected‑backward method with variance reduction\", 2021; (2) Alacaoglu and Malitsky \"Stochastic Variance Reduction for Variational Inequality Methods\" 2022; (3) Zhu et al. \"Accelerated Primal-Dual Algorithms for a Class of Convex-Concave Saddle-Point Problems with Non-Bilinear Coupling Term,\" 2020.\n\n**A:** Thanks for bring these interesting works to our attention. \n\n- Zhu et al. study the convex-concave min-max optimization problem with a non-bilinear coupling term, which is similar to the reformulation (2) in our work. However, there are key differences in our problem setting: \n    - i) In our formulation (2), the problem is separable with respect to each coordinate of the dual variable $y$, whereas the problem in Zhu et al. is not; \n    - ii) Zhu et al. focus on the deterministic setting, while our work focuses on the stochastic setting.\n- Both Alacaoglu et al. and Alacaoglu and Malitsky study the monotone variational inequality problem with a finite-sum structure, which includes the concave min-max optimization problem with a finite-sum structure as a special case. Although our problem in (2) also has a finite-sum structure, there are two differences: \n    - i) Our problem (2) is separable with respect to each coordinate of the dual variable $y$, whereas the problems considered in Alacaoglu et al. and Alacaoglu and Malitsky are not;\n    - ii) Alacaoglu et al. and Alacaoglu and Malitsky assume that each summand in the finite sum of losses is directly available. In contrast, our work only requires that each summand be accessible through stochastic oracles.\n\nWe will add these discussions in the revision. \n\n> **Q2:** Line 60: \"By the convex conjugate\" do you mean that this follows from some duality framework? Can you give some references on this?\n\n**A:** Sorry for the confusion. We refer to that the value of a convex and and lower semi-continuous function $f_i$ on any $u$ in its domain can be represented as $f_i(u) = \\max_{y^{(i)}\\in\\mathcal{Y}_i}\\{u^\\top y^{(i)} - f_i^*(y^{(i)})\\}$, where $f_i^*$ is the convex conjugate of $f_i. The formal definition can be found in Section 12 of Rockafellar (1997).\n\nRockafellar, R.T., 1997. Convex analysis (Vol. 28). Princeton university press.\n\n> **Q3:** typos: regularizatoin; line 1362: minF(x)\n\n**A:** Thanks for pointing these out. We will fix them in the next version of our draft.", "claims_and_evidence": "The claims are convincing. But my confidence with respect to the novelty and state of the art is low, as this topic is far from my expertise area.", "methods_and_evaluation_criteria": "The evaluation setups are good.", "theoretical_claims": "I did not check the correctness of the proofs.", "experimental_designs_or_analyses": "The experiments look sound.", "relation_to_broader_scientific_literature": "The literature review seems good to me. Some papers I had in mind on saddle point problems are cited.", "essential_references_not_discussed": "I am not an expert of this class of problems. (2) is a convex-concave saddle-point problem with non-bilinear coupling. The function $g_i$ in the coupling is accessed via a stochastic oracle, and I am not familiar with this setting. \n\nCan you tell me if the following papers are relevant?\n\n* Alacaoglu et al. \"Forward‑reflected‑backward method with variance reduction\", 2021\n* Alacaoglu and Malitsky \"Stochastic Variance Reduction for Variational Inequality Methods\" 2022\n* Zhu et al. \"Accelerated Primal-Dual Algorithms for a Class of Convex-Concave Saddle-Point Problems with Non-Bilinear Coupling Term,\" 2020", "other_strengths_and_weaknesses": "Again, this topic is not in my expertise area, but this class of optimization problems seems to have interesting applications in machine learning.", "other_comments_or_suggestions": "typos:\n* regularizatoin\n* line 1362: minF(x)", "questions_for_authors": "Line 60: \"By the convex conjugate\" do you mean that this follows from some duality framework? Can you give some references on this?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This submission proposes a new algorithm for solving finite sum compositional convex optimization problem. The authors also provide a lower bound to certify near-optimality of their algorithm.

The reviewers are in agreement in their acceptance recommendation. In my reading, the work can improve its positioning with respect to the literature and provide clearer comparisons with the related work.
Decision: Accept (poster)