Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization
Authors: Wei Jiang
Gang Li
Yibo Wang
Lijun Zhang
Tianbao Yang
Venue: NeurIPS 2022 Accept (2022)
Keywords: variance reduction
stochastic non-convex optimization
coupled compositional optimization
sample complexity

Abstract: Variance reduction techniques such as SPIDER/SARAH/STORM have been extensively studied to improve the convergence rates of stochastic non-convex optimization, which usually maintain and update a sequence of estimators for a single function across iterations.  What if we need to track multiple functional mappings across iterations but only with access to stochastic samples of $\mathcal{O}(1)$ functional mappings at each iteration? There is an important application in solving an emerging family of coupled compositional optimization problems in the form of $\sum_{i=1}^m f_i(g_i(\mathbf{w}))$, where $g_i$ is accessible through a stochastic oracle. The key issue is to track and estimate a sequence of $\mathbf g(\mathbf{w})=(g_1(\mathbf{w}), \ldots, g_m(\mathbf{w}))$ across iterations, where $\mathbf g(\mathbf{w})$ has $m$ blocks and it is only allowed to probe $\mathcal{O}(1)$ blocks to attain their stochastic values and Jacobians.  To improve the complexity for solving these problems, we propose a novel stochastic method named Multi-block-Single-probe Variance Reduced (MSVR) estimator to track the sequence of $\mathbf g(\mathbf{w})$. It is inspired by STORM but introduces a customized error correction term to alleviate the noise not only in stochastic samples for the selected blocks but also in those blocks that are not sampled. With the help of the MSVR estimator, we develop several algorithms for solving the aforementioned compositional problems with improved complexities across a spectrum of settings with non-convex/convex/strongly convex/Polyak-Lojasiewicz (PL) objectives. Our results improve upon prior ones in several aspects, including the order of sample complexities and dependence on the  strong convexity parameter. Empirical studies on multi-task deep AUC maximization demonstrate the better performance of using the new estimator. 

Multi-block-Singl--pooo Variance Reduced Estimator for Coupled Compositional Optimization
Wei Jiang', Gang Li2, Yibo Wang', Lijun Zhang Tianbao Yang".
National Key Laboratory for Novel Software Technology, Nanjing University, Nanjing, China Department Computer Science, the University of lowa, Iowa City, USA
8 Department of Computer Science and Engineering, Texas A&M University, College Station, USA jiangw @ lamda.nju.edu....mmmm duduucnnnec gang- wwwwa.edu.ccm. wangyb @ lamda.nju.edu.. Zhanglj @ law.a.nju.edu..ommmmm. tianbao- yang lamu.edu
Abstract
Variance reduction techniques such as SPIDER/SARAHISTORM have been ex- tensively studied improve the convergence rates of stochastic non-convex op- timization, which usually maintain and update sequence of estimators for a single function across iterations. What we need track multiple functional mappings across iterations but only with access to stochastic samples of (1) functional mappings at each iteration? There is an important application solving an emerging family of coupled compositional optimization problems in the form Σm ((gg(w)) where Zi is accessible through stochastic oracle. The key issue is to track and estimate sequence of g(w) (91 (w). 9m (w)) across iterations, where g(w) has m blocks and it is only allowed to probe O(1) blocks attain their stochastic values and Jacobians. To improve the complexity for solving these problems, we propose a novel stochastic method named Salti-block-Singlle probe Variance Reduced (MSVR) estimator to track the sequence of g( g(w). It is inspired by STORM but introduces customized error correction term to alleviate the noise not only in stochastic samples for the selected blocks but also in those blocks that are not sampled. With the help of the MSVR estimator, we develop several algorithms for solving the aforementioned compositional problems with im- proved complexities across spectrum settings with wann--ovve/ooove//strnnnn convex/Polyak Panee//Pllak-Lojasieiiizzz (PL) objectives. Our results improve upon prior ones in several aspects, including the order of sample complexities and dependence the strong convexity parameter. Empirical studies multi-task deep AUC maximization demonstrate the better performance of using the new estimator.
1 Introduction
This paper is motivated by solving the following Finite-sum Coupled Compositional Optimization (FCCO) problem that has broad applications machine learning [Wang and Yang 2022]:
min F(w) = m wERd
Σ f((a(w)), 1=1
(I)
where Si RR + I is a simple deterministic function. We assume that only noisy estimations of gi(-) and its Jacobian Vg.(-) can be accessed, denoted as gi(;;)) and Vgi(::)) where & represents the random sample(s) drawn from a stochastic oracle such that E [g) g: 9a(:) and
"Corresponding author
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

E [+) = V.)()). A special case to be considered separately is when each & has a finite support and uniformly distributed. In this case, the problem can be represented as:
min F(w): == 1 ft WER
g:(w; Ees) j=1
Σ
(2)
These problems are different from classical stochastic compositional optimization (SCO) problems (I (w: E)) and its finite-sum variant 1/m Ei= fi(1/n ((; [Wang et al. 2017 because the inner function is coupled with the outer index in FCCO.
A striking difference in solving FCCO problems is that we need to deal with multiple functional mappings of (w) for i 1.... m. A challenge emerges when it is not possible draw data sam- plcs for all blocks i = 1...., m at each iteration due to some restrictions (c.g., limited memory and computational budget per-iteration). Wang and Yang 2022] studied this problem comprehensively and proposed an algorithm named as SOX. A key to their algorithmic design is to maintain and selec- tively update sequence of estimators u = (u' (u.,..., u for tracking g( (g1 ( Im(w)) by exponential moving average, i.e.,
{ (1 (1- B) + 8g, (we: u
E B E B
u
(3)
where Ei and Bi (1, (I....,m,) m) denote a of sampled blocks. With u, the gradient estimator is computed by exponential moving average as well. As a result, they establish a sample complexity of (mm for non-convex objectives. O for convex objectives and O(mp= sampleecoplesxinn for μ strongly convex objectives. However, there are several caveats of these results: (i) the sample complexities (e.g., + for non-convex objective) are no better than probing all blocks at each iteration, for which Ghadimi et al. 2020) have established an O ((= iteration complexity and an O(me sample complexity; (ii) when m = [B]] 1, the problem reduces to a special case of classic SCO problems; however, the complexities are worse than the state-of-the
(SOTA) sample complexities for non-convex, convex and strongly convex objectives, which are O 3). O 2) and 0 respectively [Zhang and Xiao 2019 Jiang et al. 2022). A useful technique for achieving these complexities in prior works is by using variance reduction techniques, so straightforward approach is to change the update of už by using variance reduced estimator and do similarly for the gradient estimator. In particular, one can change the update for u, according to STORM CCutkosky and Orabona 2019]
(1 - 3)u + Bg: (wr:t)) + (1 (1-8)) (gi (wri - gs (w:-1;
E B
u
(4)
correction
1
i c 1
However, this simple change does not improve the complexities over that obtained by Wang and Yang [022). The reason is that the standard error correction term marked above in STORM only accounts for the randomness in gi (W:: Et) but not in the randomness caused by sampling i E B4. So, major question remains:
How can we further improve the complexities for solving FCCO to match the SOTA results of SCO by using variance reduction techniques via probing only (1) blocks at each iteration?
To address this issue, we propose a novel variance reduction technique by selectively updating un for tracking g( (.)) to which we refer as Multi-block- -oib-l---o-iigge-robbbee variance-reduced (MSVR) estimator. It employs similar update STORM for selected un but with a different customized error correction term to deal with the randomness in both gi (w;; and that in Bi. Based on MSVR, we develop several algorithms for FCCO problems with different ways to compute the gradients, and analyze the sample complexities across a spectrum of settings with non-coovex/coonve//trroo convex/PL objectives and finite/infinite support of & We summarize our contributions and our results below:
We develop a novel MSVR estimator for tracking a sequence of multiple blocks of functional mappings by only probing ((1) blocks via random samples at each iteration.

---

Table I: Sample complexities needed find c-stationary point c-optimal point. Here NC means non-convex, means convex, SC indicates μ--strongyy convex, PL means the p-PL condition. B1 denotes the outer batch size, Le., B1 |B:|| and B2 denotes the inner batch size. f assumes that is convex and monotone, and is convex but possibly not smooth. applies when inner function is in the form of the finite-sum. (-) hides logarithmic factors. In all results, we assume m S (OEE))
Method
NC
SC/PL 2 (a-le-) (SC)
BI. B2 0(1). Ole P)(NC) (.)O(C")iCSC))) ((-1),0(()
BSGD
O (<=")
(e-))
[Hu et al.
2020
BSpiderBoost
2 (e-9)
[Hu et al. 2020
SOX SOX (1)
0 (mme
0 (me-))
o (mp 16-1
0(1).
O (mB2e 9)²
001, 0(1
Wang and Yang
2022
MSVR-v1
(max B,, BB)e
[max( B
O (max) B,, Bo)l=
0(1). O(1)
MSVR-v2
O (my/Bae"
O [myyBBja (-)
O(1). O(1)
MSVR-v3'
(mynBBje
① (my/nBge
O (my/BBaa
0(1). 0(1)
By applying the MSVR estimator, we develop three algorithms for FCCO by using different methods for computing the gradients, and establish improved complexities for non-convex, convex, strongly convex, and PL objectives. A comparison between algorithms and existing methods is shown in Table where we also exhibit the dependence on B3, which is the size of the inner batch for estimating each (ww).
The complexity of our first method (i.e., MSVR-v1) enjoys the same order does not depend on m: MSVR- v2 improves the dependence on c, and its complexities match the SOTA results for SCO when m 1; our MSVR-v3 further reduces the dependence for the finite support of E, and also attains the SOTA complexities when m 1.
SOX, but
We conduct experiments on multi-task deep AUC maximization to verify the theory and demonstrate the advantage of the proposed algorithms.
2
Related work
This section briefly reviews related work on variance-reduced methods and stochastic compositional optimization (SCO) problems.
Variance-reducciion (VR) techniques for improving the convergence of stochastic optimization orig- inate from Roux et al. (2012) for solving convex finite-sum empirical risk minimization (ERM) problems. Since then, different VR techniques have been proposed for convex finite-sum ERM, c.g.. SVRG [Johnson and Zhang 2013 Zhang et al. 20013 and SAGA [Defazio et al. [014]]. These works have improved the complexity for solving smooth and strongly convex problems to a logarithmic complexity. For non-convex ERM problems, Fang et al. 2018 invents the SPIDER estimator similar to its predecessor SARAH (Nguyen et al.) [017]. and improve the complexity of standard SGD from O(c-)) to O and O )) in stochastic and finite-sune sum settings, respectively, where n the number of components in the finite-sum. Algorithmic improvements have been made to SPIDER by using a constant step size in SpiderBoost [Wang et al., 2018 and using a constant batch size in STORM [Cutkosky and Orabona 2019)
Several classes of SCO have been studied. The first class is the two-level SCO whose objective is given by EEg [ffe (I.,. [g. (w))), where & and w are random variables. While the study of two-level compositional functions dates back the 70s, the most recent comprehensive study was initiated by Wang et al. (017). They proposed two time-scale classic algorithm named SCGD and establish its asymptotic guarantee and -on-smymtooiic convergence rates. Following this work, many studies have been devoted to improving the convergence rates or algorithmic design of two-level SCO (Wang jt al. 2016 Ghadimi et al.) 2020 Zhang and Lan 2021 In particular, recent works have used variance-reduction techniques based on SPIDER/SAR SEIDER/SARATSSTORR
to estimate the inner values and
the gradients [Liu et al. 2018 Yuan et al.] 2019a| Zhang and Xiao 2019 Chen et al. 2021 Qi et al. 202 Similar efforts have been extended to the second class of SCO, i.c., multi-level SCO with an
3

---

objective Be,lfg. (E,,If2, (... (Eex If (w))l ...)]] Yang et al.
2019 Recent studies have been focused on further improving the sample complexity and reducing the dependence on the number of levels K [Balasubramanian
al., 2021 Chen al. 202 Zhang and Lan 2021 Zhang and Xiao 2021 Jiang et al.) 2022]. These works also employed variance reduction techniques to design their own methods. However, directly applying these algorithms of two-level and multi-level SCO to FCCO requires probing all m blocks in g( (w) which is prohibitive in many applications.
The third class of SCO is the Conditional Stochastic Optimization (CSO) whose objective is in the form of Eg fe [e ( (w]) (Hu et al., 2020]. where w|fe means that the distribution of w might depend on ç. The FCCO problem can be considered
special case of CSO. The key difference from the first class of SCO discussed above is that the inner function g depends on the random variable { of the outer level. For CSO. Hu et al. (2020) proposed two algorithms with and without using technique (SpiderBoost) named BSGD and BSpiderboost, and established
the variance-reduction complexities for non-convex, convex and strongly convex functions, which are shown in Table [ However, their algorithms require a large batch size for estimating the inner functions.
Recently, a novel class (the fourth class) of SCO was studied, which is referred to the finite-sum coupled compositional optimization (FCCO) [Wang and Yang. 2022). The finite-sum structure makes it possible to develop more practical algorithms without relying on huge batch size per-iteratin per-iteration. It was first studied by QQ et al. [022bb] for maximizing the point-estimator of the area under the precision-recall curve. Recently, it was comprehensively investigated by Wann and Yang 2022] and more applications of FCCO have been demonstrated in machine learning. Nevertheless, their algorithm-SOX does not use variance reduction techniques and hence suffers from the limitations discussed in the previous section.
Proposed Algorithms and Convergence
First, we introduce the notations and assumptions used in this paper. Then we describe the MSVR estimator detail and develop algorithms based on the proposed estimator.
3.1 Notations and Assumptions
Let [m] (1..... m]. The definition of sample complexity is given below, which is widely used to measure the efficiency of stochastic algorithms.
Definition 1 The sample complexity is the number of samples needed find a point satisfying [[I]F(())ll S (c-stationary) or E [F(w) inf F(w)] I e ((-optimall.
Next, we make following assumptions throughout the paper, which are commonly used in the studies of SCO [Wang al., 2016 2017 Yuan et al., [211aa] Zhang and Xiao 2019, [02I].
Assumption (Smoothness and Lipschitz continuity) We assume that each fi is Ly-smooth and Cy -Lppchittz continuous, each gi is Lg -smooth and C Lipsschhit continuous.
Remark: This implies F(w) is Cy--Lipchizz continuous and Lp-smooth, where CF C.Cgg LF - CbL + CgL, (Zhang and Xiao 2021
Assumption (Bounded variance) E [x { (x):
E [x: Vgi(x); Vxx(x))
E [199: (x: (xx S /²/B2;
E V (x:
|||
S o²/BB /B2:
where the random variable Et denotes a batch of samples with batch size B₂ 2 1. Assumption (Average Lipchitz continuity of gi and its Jacobian)
E 119. (x:: gs (y: (11) < Cg]Ix 1 y1
E g (x:
Vg (y: [1 < T/y y
Remark: Although this assumption seems strong at the first sight, it is quite standard and widely used in the recent compositional optimization literature (Yuan al. 201 9a, Zhang and Xiao 2019 2021 Jiang et al. 2022
Assumption 4 F, inf F(w)= 2 -oo and F (W1) F., I AF for the initial solution Wi.

---

3.2 Mulli-block-Singll-pbbee Variance Reduced (MSVR) Estimator
Assume that we have a budget to probe only B1 out of m mappings in g(w). To this end, at the t-th iteration we sample set of blocks Bi S [ma]. where B = B1, and probe the corresponding ((()) by accessing the noisy estimates g. (W,;; {,) for i Bi. Then, we just update the corresponding block in our estimator Specifically, we update ii for i E Bi in a new way and keep other blocks unchanged. The whole estimator shown below:
3c)uk-1 Begs (Wrs + Ttt (g: (Weit)) - 9: (5
i B3
(5)
af
4 B
The first line of our estimator is inspired by STORM [Cutkosky and Orabona 2019]. The difference vı- that the STORM estimator sets "/ = (1 - 3t). while for MSVR, 7t is set as B.(I-D) + (1 B))
according to our analysis. We name equation (5) as www.-bbooo--iii--prrrae (MSVR) estimator. By multi-block,
Variance Reduced
mean the estimator can track multiple functional mappings (91, 92. ..... Im,, simultaneously; by single-probe, we indicate the number of sampled blocks B1 for probing can be as small as one. It is notable that when B, m, i.e., all blocks are probed at each iteration, 7t = 1 - 3r and MSVR reduces to STORM applied to g( w). The additional factor in Tt. i.e., 7/ = m B is to account for the randomness in the sampled blocks and noise in those B1 5.)
blocks that are not updated. To briefly understand the additional factor ye we consider bounding l|u g g(w))l1 = Exs ||u - g (w,))l Let us focus on a fixed i E [ma]]. Then we have Bi
B1 m
E I - g: (w.)))
E [| gi (w:))l +(1
E [
- 9: (w.)))]))
m
Note that the first term A₁ in the R.H.S. can be bounded similarly as STORM by building recurrence with ||už_1 9i( (w.,,)) I)l2. However, there exists the second term due to the randomness of Bi, which can be decomposed as || 1 - gi (w: + g:::: (w.-1) - g((w))ll= |u/1 (W (w: 1) - (w()))l?
Au1
Ag2
+ 2( gi((: (I) (g: (we (w:))
A23
The first two terms in R.H.S. (Agı and A22) can be easily handled. The difficulty comes from the third term, which cannot be simply bounded by using Young's inequality. If doing so, it will end up with non-diminishing error of u². To combat this difficulty, we use the additional factor brought by 78 (g: (W,; D: (w)=1<()) in Ai to cancel A23. This is more clear by the following decomposition of A1.
A =E (1 8.)(ui 9: (w))) 2 (ow(e)) (w()
An
A12
+ (g: ( - (w)) + (W g.( (w:))) + 9: (w())))) [|9
A1a
A14
<E|IIAn A1a 12 +
E |l|A13 + Aral
In light of the above decomposition, we can bound A[ + A < Bn + ||1 21 and E1IlA13 + A11ll < a negative sign as A23. Hence, by carefully choosing 7/ we can cancel both terms. The remaining terms can be organized similarly building the recurrence of MSVR's 's error below. All the proofs are deferred to the supplementary material due space limitations.
| 2El][A The resulting term 1[2A,AA11 has
in the analysis for STORM. We give a technical lemma for
Lemma 1
By setting 7/-
m m-B + (1 - for 3r < 1. we have:
B,(1-3.)
[|u - g (w.))l²) S (1
B1 E
2B 2B18002
| - (wc-1))
m
B₂
8m2
+
B1 E
||w: wl 112
5

---

Algorithm 1 MSVR-vI and MSVR-v2 method
Input: time step T. parameters Ctt, Sr, Tt. learning rate The and initial points (Wi, u1, U1,
2: for time step t = to I" do
3: Sample subset Bi from (1,2....,,, mm
4: Compute estimator u, according to equation (5) or 6
Use MSVR or MSVR-SP update Use moving average update o Use STORM update
5: (v1) Compute estimator z, according to equation
6: (v2) Compute estimator z, according to equation
7: Wt+1 W₁ 10-- 7/
8: end for
9: Choose r uniformly at random from (1...., T}
10: Return W,
The above recursion is similar to that of STORM for tracking a sequence of single-block functional mapping. Since the last term ||w; - w,- 2 can be offset in the future analysis, intuitively the estimation error ||u g (we)ll would reduce after each iteration.
Remark:
Single Point Version. A limitation of the MSVR estimator is that it needs to probe selected blocks
at two different points, i.e., 9: (W:; {)) and gi (w-1;; {t). With a more careful analysis, we can probe selected block single point similar to that used by [Balasubramanian et al. [2021] and Chen et al.
2021 Specifically, we replace gi (Wr; {t) gi (i) with V (Wa: Ei (w: -w,-1) i). As
result, we propose single-point version of MSVR (named MSVR-SP) estimator below:
u = (1 n
1. + B.9: (wa: () + 7/ Vg. (w: (w, w.-1)
i B
(6)
i B
The MSVR-SP estimator enjoys the similar recurrence for the estimation error.
Lemma Set 7/2- = B.(1- Re]
m-
+ (1 Bt). If [w+1 - w. 2 S nf and T/e S /B. we have:
B1 m
+ 2B $702
|lue - o(w,))l² S E
E ||u - g(Ww-1))l
B₂
802
m²
+
41203 + -02 +
E
We
wt-1
B2
B1
Remark: If there is constraint on the range of gi, we can add a projection to the update of u, such that it always resides in the range, which will not affect the analysis of Lemma I and Lemma
3.3 Leveraging the MSVR Estimator for solving the FCCO Problem
Now, we are ready to present our proposed algorithms for solving problem algorithms (named MSVR-v1 and MSVR-v2) are presented in Algorithm These two methods differ how to estimate the gradient.
The first two
Let us first consider MSVR-v1. At each time step f, we first use the proposed MSVR or MSVR-SP estimator u, to estimate the inner function value. Then, following the previous literature WWag et al. 2021 Wang and Yang 2022], we use the moving average estimator z, to estimate the gradient as:
2, = llrr (1 (1-aa)z(-1 +
at Σ B
Vfllui-)Va(wwsst
EE
where IIrr denotes the projection onto the ball with radius CF. This projection is optional for using MSVR, but is required for using MSVR-SP to ensure | -w,l' nf as used in Lemma 2 Since the true gradient F is also in this ball, i.e., |VI < Cr, the projection will not affect the future analysis. Also note that when computing the estimator Z,, we use fi( instead of
(((( to avoid the dependence on the random variable E; which may lead to dependent issues
otherwise. Finally, we use the estimated gradient 2, to update the parameter W Now, we provide the theoretical guarantee for the MSVR-v1 method.

---

Theorem Our MSVR-vI algorithm with ar+1 (Te)). Bt+1 O O
mB Bi
and
=min
BiyB2
2/3
} can find e-stationary point (a (a+t) 1)-13, V min B1, B2) t)-
m
}) iterations.
in O max
Bi Bz
min BB
Remark: This complexity is strictly better than previous SOTA method SOX, which enjoys an me 2 B, min(B,, 1,, })- The sample complexity can be ob- tained by multiplying the iteration complexity with B B2. We can see that larger B₁ or B2 yields smaller iteration complexity, which means that from the computational perspective, if samples can be processed parallel (e.g.. in GPU), there benefit of using large B₁ and/or B2. However, from the sample complexity perspective, using B1 = B2 = is the best. The same discussion holds for other theorems below.
iteration complexity of O max
me
However, the complexity of MSVR-vI is still on the order of ((e Due to the biased nature of the estimated gradient, using the moving average update is not enough for achieving the SOTA complexity of O( ()) So, we use the technique of STORM [Cutkosky and Orabona 2019 to update Z; as follows:
(1 - (1-a,) az) + 1
2, Ilrr
B
iE
(8)
+ (1 (1)
Σ (V - Vo.
B1
KEB
where the projection operation is needed using the MSVR estimator. Now, we prove this new method (i.e., MSVR-v2) can obtain the optimal complexity of ())-)).
Theorem Our MSVR-v2 algorithm with a4+1 = O( mmn
(0mm) Bt+1 = O
m m
and iterations.
O (m
Bf
// (a 1)-1/5). can find an e-stationary point in O Th O (B /
B.vBa
Remark: When m = 1 and f is the identity function, problem ① reduces to the standard stochastic non-convex optimization, whose lower bound is Ω (E (E-3) Arjevani al. 2019], indicating our MSVR-v2 is optimal.
Next, show that the complexity can be further improved when the objective function is convex strongly convex. We note that Polyak-L.jassewiicz (PL. [Karimi et al. 2016) objectives are more general than strongly convex functions, since jı-strong convexity implies the p-PL condition. So, will consider the PL. condition and introduce its definition below.
Definition 2 F(w) satisfies the p-PL condition if there exists >> 0 such that:
24 (F(w) F.) [VF(w)]
Then, we derive improved rates for convex or PL objectives by using the stage-wise design given in Algorithm 3 in the supplement.
Theorem If the objective function satisfies the convexity or μt-PI. condition, MSVR-vl derives sample complexity of O ( -3) O B,, -2)))-2(11) separately. For MSVR-v2, the complexity can be further improved to O (myBBc Bage or O hnn/Bap-lee
Remark: The complexities for MSVR-v2 are optimal, since they match the Ω (c- 2) and Ω (u=
lower bound for stochastic convex and strongly convex optimization [Agarwll et al. 2012).
Remark: The algorithms proposed in this paper can also use adaptive (Adam-style) learning rates and obtain the same complexity using the techniques proposed by Guo et 2021] The details are provided in the supplementary.
7

---

Algorithm 2 MSVR-v3 method
Input: time step T. parameters a, 8,7, 1, learning rate 7 and initial points (W1, U1 21).
2:
for time step t = to I' do
3: if mod = then
4: Set 7 =
5: Compute and save go (w+), (.f((u())) for every and Ei= V. (g
6:
end if
7:
Sample subset Bi from 11,2,... m
8: Compute function value estimator according to equation
9: Compute gradient estimator 2, according to equation (TO)
10: Wt+1
1/2
11: end for
12:
Choose uniformly at random from (I....,77 ,
13:
Return W,
4 An Improved Rate for the Finite-sum Case
In this section, we consider the case that inner function Ji is in the form of the finite-sum, i.e., g: (:()) 2j=1 Di (w: Sij). so that we can compute the exact value of g:(w) in some iterations. We first modify our MSVR estimator to utilize the finite-sum structure. Inspired by SVRG [Jonnson and Zhang 2013, Zhang et al.,
2013), we compute a full version of the inner function value for every iterations at w,, I.e., (W+ Ej= 9: ( (w+: for 1, where T mod I = 0. Then, in each step, we use
(w.i 5 = gi (w ge(wri g: (w())
to replace gı (W., {f) in the origin estimator. In this way, MSVR estimator is changed to:
1 { (1 B) 8g. (we:t) (gi (wa:t) (wi-1:gf)
i B
(9)
u
i Φ B
For this estimator, we have the following guarantee.
Lemma B $ and BI S m. B. by setting y =
m- B1(1-3) + (1 - 3), we have:
E |1 - 9 g (w++1)ll?) s <11- B13
10m?
E I g (w:))l]
[We+1 (ww+1-wwll? will
+
B1
Bg 8"a term, which the key to reduce the
Remark:
Compared with Lemma we remove the
complexity since we can now use a larger parameter 3.
To attain the optimal complexity, we modify the gradient estimator in a similar way:
2, (1 -)) + ah;
1 + (1- Bi
Σ iEB!
(VAlul)))a(w:s)) VV
(10)
where h, involves both the full gradient and the stochastic gradient (we also need to save each (f, and calculate the full version of 1 >"h
m x ( (w.. at those steps 7)
h, 1
Σ iEB
Vf (g:
Vfllut-
B1
The whole method is summarized in Algorithm 2 (named as MSVR-v3). Next, we show that MSVR-v3 is equipped with an optimal complexity of ( -2).
Theorem Our MSVR-v3 with B, B a = B,
B ( Bg and rj 0
BBiBBa myn
mn
can oblain an e-stationary point in T O
m Bi v Br
iterations.

---

1.50
0.9
SUN
0.8
SOX
Touiiin less
MSVR-e
MSVR x2
Thainin loss
0.7-
MSVR-<2
MSVR.v1
Training loss
0.7
MSVR x2
MSVR-v1
MSVR.v3
0.5
0.75
0.5
0.4
0.50
0.3
0.0
0.5
1.0
1.5
2.0
2.5
0.2
0.5
1.5
2.0
2.5
0.1
0.00
0.25
0.50
0.75
1.00
of samples
X10
of samples
10
of samples
X10
(a) STL10
(b) CIFARIO
(c) CIFARI00
0.9
0.9
0.9
0.8
MSVR-vi
0.8
MSVR-v1
0.8
MSVR-1
Thaining loss
Training less
Thininn
0.6
MSVR.12
00.6
MSVR-v3
00.6
MSVR-v3
0.5
0.5
0.5
0.4
0.4
0.0
0.5
1.0
2.5
0.0
0.5
1.0
0.5
1.0
# of samples
100'
# of samples
x10
# of samples
x10*
(d) MNIST
(e) Fashion-MNIST
(i) SVHN
Figure Results for Multi-task AUC Optimization.
Remark:
When and is the identity function, problem reduces to the stochastic finite-sum
optimization, whose optimal complexity is (vnc" [Fang et al. 2018 Li et 2021 indicating complexity is optimal in terms of and n.
Similarly, better complexity can be obtained under the convexity or PI. condition.
Theorem 5 If the objective function satisfies the convexity Ju-L condition, the sample complexity can be improved to O
my/e
log 1 or O mm/ap"
log 1 respectively.
BiVB2
B.V
Remark: It is notable that we achieve linear convergence rate O (log under the PL condition,
matching the current result in the single-level finite-sum problem [Li et 2021
Experiments
In this section, we conduct experiments on the multi-task deep AUC maximization to evaluate the proposed methods and will consider more applications the long version of the paper. For binary classification (label = or
1), AUC maximization can be formulated as minimizing the
following composite loss [Zhu et al. 2022]:
min Ex|y== [h (x) - a)
+ Exe[s'=-1 (hw (x') b)²] [(a(w)- B(w)),
b.
where a(w) = E ww (x)
1). b(w) = E (x)) |y 1]] and E(-) is surrogate function. The above objective recovers the pairwise square loss and the min-max margin loss proposed by Yuan et al.. (2020) for deep AUC maximization by setting E(-) the square function squared hinge function, respectively. When applied to multi-task classification (e.g., multiple classes), we can optimize the averaged AUC losses over all tasks, i.e., AUC = Di AUC(i). The nested structure only comes from the term ((a(w) b(w)). and we can rewrite it as the form of FCCO problem, where
g. (:ww)
Σ x
Now (x)
Σ (x),,,
f (g:(w)) ((g:(w))
D
D
XED
where Di denots the positive/negative datasets the i-th task.
Configurations. the experiment, we follow the setup in Zhu et 2022 and set the surrogate func-
tion & squared hinge {(x) (maxfc++ æ, 0.)2. We use ResNet18 8 backbone network, and train

---

on six datasets: STLIO Coates et al. 2011 CIFARIO Krizhessky 2009], CIFARI00 Krizhevsky
2009
MNIST LeCun al. 1998]. Fashion-MNIST
Xiao et 2017 and SVHN Netzer et al.
2011 We compare our methods with previous SOTA algorithm SOX [Wang and Yang 2022 J. For our methods, parameters a and 9 are searched from (0.1, 0.5,0.0,.0.3 0.9, 1.0). For SOX algorithm, its parameters 3 and 7 are searched from the same set. B₁ is set as 50 for CIFARI00 and 5 for other datasets. Inner batch size B2 is chosen as 128 for all methods. We tune the learning rate from the set {le - 4, le 3, 2e 3, 5e 3, le- 2} and pick the best one for each method. The experiments conducted on single NVIDIA Tesla M40 GPU.
Results. Figure D shows the loss against the number of samples drawn by different methods, and all curves are averaged over runs. We observe that MSVR-VI better than SOX on the CIFAR 100 dataset, and close to it on other datasets. MSVR-v2 converges faster than SOX and MSVR-v1, and the loss of MSVR-v3 decreases most rapidly, demonstrating low sample complexity.
Conclusion and Future Work
In this paper, we develop a novel MSVR estimator for tracking multiple functional mappings by probing only (1) blocks. Equipped with this estimator, we design three algorithms for FCCO problems and obtain improved complexities across a spectrum of settings. Experimental results on multi-task deep AUC maximization also verify the effectiveness of our methods. In future work, we will investigate other applications that can be solved by using the proposed estimator.
Acknowledgments and Disclosure of Funding
W. Jiang, Y. Wang and I.. Zhang were partially supported by NSFC (62122037, 61921006). G. Li and T. Yang were partially supported by Amazon research award. The authors would like to thank the anonymous reviewers for their helpful comment.
References
A. Agarwal, P. L. Bartlett, P. Ravikumar, and M. J. Wainwright. Information-theores lower bounds on the oracle complexity of stochastic convex optimization. IEEE Transactions on Information Theory, 5855 2012.
Y. Arjevani, Y. Carmon, J. C. Duchi, J. Foster, N. Srebro, and B. E. Woodworth. Lower bounds for non-convex stochastic optimization. ArXiv e-prints, arXiv:1912.0236. 2019.
K. Balasubramanian, S. Ghadimi, and A. Nguyen. Stochastic multi-level composition optimization algorithms with level-independent convergence rates. ArXiv e-prints, arXiv:2008. 10526, 2021.
T. Chen, Y. Sun, and W. Yin. Solving stochastic compositional optimization is nearly easy as solving stochastic optimization. IEEE Transactions on Signal Processing, 69:4937 4948, 2021.
A. Coates, A. Ng, and H. Lee. An analysis of single-layer networks in unsupervised feature learning. In Proceedings of the 14th International Conference on Artificial Intelligence and Statistics, pages 213-223, 2011.
A. Cutkosky and Orabona. Momentum- based variance reduction in non-convex SGD. In Advances in Neural Information Processing Systems 32, pages 15210-15211 2019.
A. Defazio, F. R. Bach, and S. Lacoste-Julien. SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives. In Advances in Neural Information Processing Systems 27, pages 1646-1654, 2014.
C. Fang, J. Li, Z. Lin, and T. Zhang. Spider: Near-optimal non-convex optimization via stochastic path integrated differential estimator. ArXiv e-prints, arXiv: 01699,, 2018.
Ghadimi, A. Ruszezynski, and M. Wang. single timescale stochastic approximation method for nested stochastic optimization. SIAM Journal on Optimization, 30(1):960-979, 2020.
10

---

Z. Guo, Y. Xu, W. Yin, R. Jin, and T. Yang. On stochastic moving- average estimators for non non-convex optimization. ArXiv e-prints, arXiv:2104.14844 2021.
Y. Hu, S. Zhang, X. Chen, and N. He. Biased stochastic first-order methods for conditional stochastic optimization and applications in meta learning. In Advances in Neural Information Processing Systems 33, 2020.
W. Jiang, B. Wang, Y. Wang. L. Zhang, and T. Yang. Optimal algorithms for stochastic multi-level compositional optimization. ArXiv e-prints, arXiv:2202.07530, 2022.
R. Johnson and Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In Advances in Neural Information Processing Systems 26, 2013.
H. Karimi, J. Nutini, and M. Schmidt. Linear convergence of gradient and proximal-gradient methods under the Polyak-t.ojasiewicz condition. In Machine Learning and Knowledge Discovery in Databases, pages 795-811 2016.
A. Krizhevsky. Learning multiple layers features from tiny images. Masters Thesis, Deptartment of Computer Science, University of Toronto, 2009.
Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner. Gradient- Bradient-based learning applied to document recognition. In Proceedings of the IEEE, pages 2278-2324, 1998.
Z. Li, H. Bao, X. Zhang, and P. Richtarik. Page: A simple and optimal probabilistic gradient estimator for nonconvex optimization. In Proceedings of the 38th International Conference on Machine Learning, pages 6286-6295 2021.
L. Liu, J. Liu, C. Hsieh, and D. Tao. Stochastically controlled stochastic gradient for the convex and non-convex composition problem. ArXiv e-prints, arXiv: 1.XY: 020000 2018.
Y. Netzer, T. Wang, A. Coates, A. Bissacco, B. Wu, and A. Y. Ng. Reading digits in natural images with unsupervised feature learning. In Advances in Neural Information Processing Systems Workshop on Deep Learning and Unsupervised Feature Learning, 2011.
L. M. Nguyen, J. Liu, K. Scheinberg, and M. Takac. SARAH: A novel method for machine learning problems using stochastic recursive gradient. In Proceedings of the 34th International Conference on Machine Learning, pages 2613-20011 22322621,11 2017.
Q. Qi. Z. Guo, Y. Xu, R. Jin, and T. Yang. An online method for class of distributionally robust optimization with non-convex objectives. ArXiv e-prints, arXiv:2006. 10138, 2021a.
Q. Qi, Y. Luo, Z. Xu, S. Ji, and T. Yang. Stochastic optimization of areas under precision-recall curves with provable convergence. In Advances in Neural Information Processing Systems 34, pages 1752-1765, 2021b.
N. L. Roux, M. Schmidr, and F. R. Bach. A stochastic gradient method with an exponential convergence rate for finite training sets. In Advances in Neural Information Processing Systems 25, pages 2672-26800 2012.
B. Wang and T. Yang- Finite-sum coupled compositional stochastic optimization: Theory and applications. ArXiv e-prints, arXiv:2202. 2022.
G. Wang, M. Yang, L. Zhang, and T. Yang. Momentum accelerates the convergence of stochastic AUPRC maximization. ArXiv e-prints, arXiv:2107.01173 2021.
M. Wang, J. Liu, and Fang. Accelerating stochastic composition optimization. In Advances in Neural Information Processing Systems 29, pages 1714-1722, 2016.
M. Wang, E. X. Fang, and H. Liu. Stochastic compositional gradient descent: algorithms for minimizing compositions of expected-value functions. Mathematical Programming, 161(1-2): 419-449, 2017.
Z. Wang, K. Ji, Zhou, Liang, and V. Tarokh. Spiderboost: A class of faster variance-reduced algorithms for nonconvex optimization. ArXiv e-prints, arXiv: 181.v11810.10690, 2018
11

---

H. Xiao, K. Rasul, and R. Vollgraf. Fashion-MNIST: A novel image dataset for benchmarking machine learning algorithms. ArXiv e-prints arXiv: 2017.
Yang, M. Wang, and E. Fang. Multilevel stochastic gradient methods for nested composition optimization. SIAM Journal Optimization, 29(1);616-659) 2019.
H. Yuan, X. Lian, C. J. Li, J. Liu, and W. Hu. Efficient smooth non-convex stochastic composi- tional optimization via stochastic recursive gradient descent. In Advances in Neural Information Processing Systems 33, pages 14905-14916, 2019a.
Z. Yuan, Y. Yan, Jin, and Yang. Stagewise training accelerates convergence of testing error over sgd. In Advances in Neural Information Processing Systems, pages 2604-2614, 2019b.
7. Yuan, Y. Yan, M. Sonka, and T. Yang. Robust deep auc maximization: A new surrogate loss and empirical studies on medical image classification. ArXiv e-prints, arXiv:201 2020.
Zhang and L. Xiao. A stochastic composite gradient method with incremental variance reduction. In Advances in Neural Information Processing Systems 33, pages 9075-9085. 2019.
J. Zhang and L. Xiao. Multilevel composite stochastic optimization via nested variance reduction. SIAM Journal on Optimization, 31(2):111111577 2021.
L. Zhang, M. Mahdavi, and R. Jin. Linear convergence with condition number independent access of full gradients. In Advance in Neural Information Processing Systems 26, pages 980-988, 2013.
Zhang and Lan, Optimal algorithms for convex nested stochastic composite optimization. ArXiv e-prints, arXiv:2011. 0:::2011.10070 10076, 2021.
D. Zhu, X. Wu, and T. Yang. Benchmarking deep AUROC optimization: Loss functions and algorithmic choices. ArXiv e-prints, arXiv:220..1417, 2022.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [No]
(c) Did you discuss any potential negative societal impacts of your work? [N/A] This work
is mainly theoretical.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions of all theoretical results? [Yes] See Section 3.1
(b) Did you include complete proofs of all theoretical results? [Yes] The complete proofs are provided in the supplementary.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [No]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes] See Section
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes]
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
12

---

(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you' 're using/curating? [N/A] We use the public benchmark datasets.
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A] We use the public benchmark datasets.
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you deseribe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "cG-6bcvTPXj", "reviewer": "Reviewer_v4Z6", "summary": "This paper introduces a novel stochastic method named Multi-block-Single-probe Variance Reduced (MSVR) estimator to track multiple functional mappings across iterations. Based on MSVR, the authors develop several algorithms for solving the finite-sum coupled compositional optimization (FCCO) problem. Theoretical analysis shows that the proposed algorithms obtain optimal complexities across a spectrum of settings.  Experiment results on multi-task deep AUC maximization to demonstrate the advantage of the proposed algorithms.", "questions": "1. In Theorem 3, the authors obtain better sample complexities under the $\\mu$-PL condition. When considering the $\\mu$-PL condition, do we need the convexity condition?\n\n2. There seems an inconsistency in the writing. The authors introduce the concept of PL condition on Page 7, but use strong convexity in other places.\n\n2. The sample complexities in Table 1 increase with $B_2$. It seems that we should use a small value of $B_2$. Is there any benefit of using a large $B_2$? \n", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. The FCCO problem has a broad spectrum of applications in machine learning and may have a high impact in this area. The proposed algorithms have a major improvement in complexities.  \n\n2. The proposed MSVR estimator is novel and quite efficient. It successfully reduces the tracking error with only a constant number of stochastic accesses to functional mappings at each iteration. \n\n3. The sample complexities are much better than existing works, and optimal in many cases. The experimental results are also convincing.\n\nWeaknesses:\n1. Besides multi-task deep AUC maximization, more experiments on others problems could be added to evaluate the proposed algorithms.\n\n2. The MSVR estimator seems incremental with respect to STORM, although the parameter is set in a different way.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "_c-0v9zaNwY", "reviewer": "Reviewer_YMmz", "summary": "In this paper, the authors study the problem of finite-sum coupled compositional optimization (FCCO), in which the inner function may depend on the outer function. When designing stochastic algorithms for FCCO, the main challenge is how to keep track of multiple (inner) functions efficiently. To solve this, the authors propose a new stochastic method named Multi-block-Single-probe Variance Reduced (MSVR) estimator, which could track a sequence of multiple blocks of functions by only probing $O(1)$ blocks. Based on the MSVR estimator, they develop three stochastic algorithms for FCCO, and establish improved complexities for non-convex, convex and strongly convex objectives. Experiments on the multi-task deep AUC maximization show the effectiveness of the proposed methods.", "questions": "1. In line 55, the authors claim that “However, this simple change does not improve the complexities over that obtained by Wang and Yang [2022]”. Do you mean that with Eq.4 the complexity is the same complexities as Wang and Yang [2022]?\n\n2. I am confused with the last column of Table 1. Does it denote the ratio between $B_1$ and $B_2$? For BSGD and BSpiderBoost, there are two Big O notations, but for other methods, there is only one Big O notation. What is the exact meaning?\n\n3. After presenting the main theorems, the authors should discuss how to set the values of $B_1$ and $B_2$.\n", "limitations": "Since this paper study an optimization problem, I think that there is no potential negative societal impact of this work.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1.  In the design of MSVR, the authors propose a customized error correction term, which is novel and powerful. Moreover, based on the MSVR, the authors develop three stochastic algorithms and establish optimal sample complexities.\n2.  The paper is generally well-written. In particular, the motivation in Section 3.2 is convincing.\n\n\nWeaknesses:\n1. In the experiments, the authors only compare with SOX. I think it is better to add more baselines.\n2. Experiments are conducted on only one network (ResNet-18), it is expected to provide more experiments with different models. Moreover,  the parameter analysis and ablation study are required to show the effectiveness of the proposed method. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Msems-vxL5x", "reviewer": "Reviewer_9gCU", "summary": "The paper considers a scheme in coupled compositional optimization where oracles of inner functions are only available at $\\mathcal{O}(1)$ blocks of functions each time. The paper proposes a new estimator called MSVR for inner function values leveraging the idea of variance reduction techniques such as STORM and SVRG. The authors establish the convergence rates of proposed algorithms in the (non)-convex and PL setting. Experimental results on the multi-task deep AUC maximization demonstrate their effectiveness and superiority over SOX - the algorithm proposed previously for solving this problem.\n", "questions": "As stated above I have two **major** questions for this paper: \n\n1. For the Coupled Compositional Optimization (CCO) problem considered, one can treat it as a general compositional optimization problem where a unified outer function $f$ can be defined to operate on $[g_1, g_2, \\dots, g_m]$. Moreover, since the outer function considered $f$ is deterministic, one can think of this problem from the perspective of block coordinate updates. It would be much more clear if the authors can elaborate more on their contributions and distinguish them from other existing works on variance reduction and block coordinate updates.\n\n2. The experiments results presented fail to capture the differences between sample complexities of SOX ($\\mathcal{O}(\\epsilon^{-4})$) and MSVR ($\\mathcal{O}(\\epsilon^{-2})$) in the finite-sum non-convex setting. The paper should include more experimental results to demonstrate the dependency of $\\epsilon, n, B_1, B_2$ instead of simply presenting results when fixing $B_1, B_2$.\n\nIn addition, I have a few **minor** comments for this paper:\n\n1. Line 30: Eq. (2) is valid only if each $\\xi_{i}$ **uniformly** distributed over a finite support.\n2. Line 31: As demonstrated above, I don’t think these problems are different from classical stochastic compositional optimization problems.\n3. Table 1: Please indentify $B_1 = |\\mathcal{B}_1^t|$ \n4. Section 2: Please add related works on the variance-reduced block coordinate updates.\n5. Line 182: How to ensure that the linearized update in Eq. (6) can obtain an $\\mathbf{u}_t^i$ within the range of $g_i$? For example, if $g_i$ is nonnegative given its structure, the linearized update may obtain a negative $\\mathbf{u}_t^i$. Would this be a significant issue?\n6. Theorem 3: The authors should at least mention the stage-wise design and refer readers to Reference.\n7. Line 254: Please cite reference papers discussing the convergence rate under the PL condition.\n8. Section 5: It would be more convincing if the authors can further motivate their presented examples. I didn’t see any merit in probing only one task in CIFAR-10 and MNIST datasets.\n", "limitations": "The theoretical and experimental limitations are clearly stated in the previous section.\n\nThe paper doesn’t have any potential negative societal impact due to the theoretical nature of the work.\n", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strength**: The paper is well-organized and well-written. They leverage the idea of the STORM estimator [1] to obtain better convergence rates compared to [2]. All the results are clearly stated and the proof (although I didn’t check carefully for convex and PL objectives) is sound and consistent with existing literature.\n\n**Weaknesses**: On the theoretical side, the considered problem and proposed algorithms in this paper can be viewed as variance-reduced block coordinate update methods in stochastic compositional optimation. I partially doubt the novelty of this paper though I did not find any related work in this regime. From the practical point of view, the paper needs more experimental results to support the effectiveness and superiority of the proposed algorithm; see comments below.\n\nReference:\n\n[1] A. Cutkosky and F. Orabona. Momentum-based variance reduction in non-convex SGD. In Advances in Neural Information Processing Systems 32, pages 15210–15219, 2019.\n\n[2] B. Wang and T. Yang. Finite-sum coupled compositional stochastic optimization: Theory and applications. ArXiv e-prints, arXiv:2202.12396, 2022.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "6QICfl0PKE9", "reviewer": "Reviewer_qGar", "summary": "This paper considers a general problem: tracking multiple mappings with only O(1) mappings available. An important application investigated in the paper is the Finite-sum Coupled Compositional Optimization (FCCO) problem. By using the proposed Multi-block-Single-probe Variance Reduced (MSVR) estimator, the authors obtain improved complexities for the FCCO problem under different settings. The proposed methods also enjoy better performance in experiments.", "questions": "1. Could the analysis also be used in contrastive learning, whose loss function can also be written in the form of FCCO? \n2. For the inequality in Lemma1 on page 5 line 174, should it be $\\beta_{t+1}$ rather than $\\beta_{t}$ ?\n", "limitations": "No problems here.", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Overall, the paper is well-written and the contribution is solid.\nStrengths: \n1. The proposed algorithms have better complexities than the previous best-known method for the FCCO problem, which covers wide applications in ML. The authors investigate the complexities under different settings, i.e., non-convex/convex/strongly-convex/finite-sum. Their theoretical guarantees match the lower bound in terms of $\\epsilon$ and $\\mu$ in many settings.\n2. The authors clearly show the intuition of the proposed method and how to determine the value of the parameter $\\gamma_t$. The proposed MSVR estimator is of interest and may inspire the algorithm design for other ML problems.\n3. The writing and explanations are clear. The algorithm is simple and the theoretical analysis looks sound to me.\n\nWeakness:\n1. The proofs in the supplementary are not very clear-written and more explanations about each lemma are recommended.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept