Debiasing Conditional Stochastic Optimization
Authors: Lie He
Shiva Kasiviswanathan
Venue: NeurIPS 2023 poster (2023)
Keywords: Optimization
Bilevel Optimization
Stochastic Optimization
TL;DR: We present improved sample complexity bounds for the conditional stochastic optimization problem and its finite counterpart through a new bias reduction idea

Abstract: In this paper, we study the conditional stochastic optimization (CSO) problem which  covers a variety of applications including  portfolio selection, reinforcement learning, robust learning, causal inference, etc. The sample-averaged gradient of the CSO objective is biased due to its nested structure, and therefore requires a high sample complexity for convergence. We introduce a general stochastic extrapolation technique that effectively reduces the bias. We show that for nonconvex smooth objectives, combining this extrapolation with variance reduction techniques can achieve a significantly better sample complexity than the existing bounds. Additionally, we  develop new algorithms for the  finite-sum variant of the CSO problem that also significantly improve upon existing results. Finally, we believe that our debiasing technique has the potential to be a useful tool for addressing similar challenges in other stochastic optimization problems.

Debiasing Conditional Stochastic Optimization
Lie He EPFL 1ie. he@epfl.ch
Shiva Prasad Kasiviswanathan
Amazon kasivisw@gmail.cmm com
Abstract
this paper, we study the conditional stochastic optimization (CSO) problem which covers variety of applications including portfolio selection, reinforcement learning, robust learning, causal inference, etc. The sample-averaged gradient of the CSO objective biased due to its nested structure, and therefore requires a high sample complexity for convergence. We introduce a general stochastic extrapolation technique that effectively reduces the bias. We show that for non- convex smooth objectives, combining this extrapolation with variance reduction techniques can achieve significantly better sample complexity than the existing bounds. Additionally, we develop new algorithms for the finite-sum variant the CSO problem that also significantly improve upon existing results. Finally, we believe that our debiasing technique has the potential to be useful tool for addressing similar challenges in other stochastic optimization problems.
1
Introduction
In this paper, we investigate the conditional stochastic optimization (CSO) problem as presented by Hu et al. [16], which is formulated as follows:
min F(x) ( E))., agR
(CSO)
where & and represent two random variables, with 7) conditioned on g. The fg Rp + and
Gn Rd + Rº denote a stochastic function and a mapping respectively. The inner expectation is calculated with respect to the conditional distribution of 7/.. In line with the established CSO framework [16] throughout this paper, we assume access to samples from the distribution P())
and the conditional distribution P()]().
Many machine learning tasks can be formulated and control in reinforcement learning (6 24), and linearly-solvable Markov decision process (5). Other examples of the CSO problem include instrumental variable regression (23) and invariant
CSO problem. such as policy evaluation
learning [16]. Moreover, the widely-used Model-Agnoste Meta-Learning (MAML) framework, which seeks determine meta-initialization parameter using metadata for related learning tasks that are trained through gradient-basee algorithms. is another example of a (CSOOprobler In this context, tasks & are drawn randomly, followed by the drawing of samples 7/ from the specified task [II. It is noteworthy that the standard stochastic optimization problem min, [[ (a:) represents degenerate case of the CSO problem, achieved by setting In as an identity function.
In numerous Drevalen/CSOOpp problems, such as first-order MAML (FO-MAML) [I], the outer random variable & only takes value finite set (say in {1,.... n2))) These problems can be reformulated to have a finite-sum structure in the outer loop and referred to as Finite-sum Coupled Compositional Optimization (FCCO) problem in 333 19). In this paper, we also study this problem, formulated as:
min -x) ZE
(FCCO)
The FCCO problem also has broad applications in machine learning for optimizing average precision, listwise ranking losses, neighborhood component analysis, deep survival analysis, deep latent variable models [3
Work initiated during internship at Amazon.
37th Conference Neural Information Processing Systems (NeurIPS 2023).

---

Although the CSO and FCCO problems are widespread, they present challenges for optimization algorithms. Based the special composition structure of [SOO using chain rule, under mild conditions, the full gradient of CSO is given by
VF(x) = Ee (Enns ((
(1;
Constructing an unbiased stochastic estimator for the gradient is generally computationally expensive (and even impossible). A straightforward estimation of V (xx) is to estimate Fg with 1 sample of &. estimate (yy) with set Hg of m independent and identically distributed (i.i.d)) samples drawn from the conditional distribution P (()((), and Engs! (-) with different set fgg of m i.i.d. samples drawn from the same conditional distribution, I.e.,
V (m) == t Eiei ())( T (e Enjer, u (,( E)).
Note that VF consists of two terms. The first term, (1/m) E (gg(x; E), is an unbiased estimate of Eyte (x; E)]. However, the second term is generally biased, i.e..
( E. (n; # f (E((
Consequently, F. (ax) is a biased estimator of F To reach the e-stationary point of F(x)) (Definition]] D the bias has to be sufficiently small.
Optimization with biased gradients converges only to neighborhood of the stationary point. While the bias diminishes with increasing batch size, it also introduces additional sample complexity. For nonconvex objectives, Biased Stochastic Gradient Descent (BSGD) requires a total sample complexity of O0)=)) 9) to reach an e-stationary point [66] This contrasts with standard stochastic optimization, where cumple-averaeee
gradients are unbiased with a sample complexity of O( 12 31. This discrepancy has spurred multitude of proposals aimed at reducing the sample complexities of both CSO and FCCO problems. Hu al. (16) introduced Biased SpiderBoost (BSpiderBoost), which, based on the variance reduction technique SpiderBoost from Wang et al. (38). reduces the variance of C to achieve a sample complexity of ()=-5) for the the proppeee.....
problem. Hu et al. [7] proposed multi-level
Monte Carlo (MLMC) gradient methods V-MLMC and RT-MLMC to further enhance the sample
complexity to O(s-1). The SOX (33 and MSVR-V2 [9 algorithms concentrated on the FCCO problem and improved the sample complexity to Onn 1) and Onne=3) respectively.
Our Contributions, In this paper, we improve the sample complexities for both the CSO FCCO problems (see [. To facilitate a clear and concise presentation, we will suppress the dependence on specific problem parameters throughout the ensuing discussion.
(a) Our main technical tool in this paper is an extrapolation- based scheme that mitigates. bias in gradient estimations. Considering suitably differentiable function g(-) and random variable D, we show that we can approximate the value of (E(()) via extrapolation from limited number evaluations of (6)), while maintaining a minimal bias. In the context of CSO and FCCO problems, this scheme is used in gradient estimation, where the function g corresponds to V and the random variable corresponds 9n-
(b) For the CSO problem, we present novel algorithms that integrate the above extrapolation- based scheme with BSGD and BSpiderBoost algorithms of Hu et al. [16]. Our algorithms, referred to as E-BSGD and E-BSpiderBoost, achieve sample complexity of ( 4.5) and -355) respectively, in order to attain an e-stationary point for nonconvex smooth objectives. Notably, the sample complexity of F-BSpiderBoost improves the best-known sample complexity of O(ne-)) for the CSO problem from Hu et al. [17).
(c) For the FCCO problenf we propose new algorithm that again combines the extrapolation- based scheme with a multi-level variance reduction applied to both inner and outer parts of the problem. Our algorithm, referred to E-NestedVR, achieves sample complexity of O(ne if S E -2/3 and ((mxx{ Vh= 2.5 *V//]) if n > E- 2/3 for nonconvex smooth objectives and second-order extrapolation scheme. Our bound is never worse than the O(ns bound of MSVR- V2 algorithm of Jiang et al. [19 and is in fact better if n 2(== 2/3). As an illustration,
when n = ( 1.5), our bound of (( 3.25) ) is significantly better than the MSVR-VV V2 bound of O(E 4.5)
2 For the FCCO problem we focus on n = ( case, for n = (2 we can just treat the FCCO problem as CSO problem and get an (3.53) sample complexity bound via our E-BSpiderBoost algorithm.

---

Problem
Old Bounds
Our Bounds
Algorithm
Bound
Algorithm
Bound
CSO
BSGD [I6]
O
E-BSGD
Ole 4.b)
CSO
BSpiderBoost [16
O
E- BSBpiderBoost
O
CSO
RT-MLMC 17
(E
Onne O Ommxx
if Ennc 2/3
FCCO
MSVR-V2 19
O(ne
E-NestedVR
Vncc }),
if m 2/3
Table I: Sample complexities needed to reach e-stationary point for FCCO and CSO problems with nonconvex smooth objectives. Assumptions comparable, but results require additional mild regularity Ja and 91y FCCOF also also see Footnote 2 Note that (?(=5)) is a sample complexity lower bound for standard stochastic nonconvex optimization [3) and hence, also for the problems considered in this paper.
In terms of proof techniques, our approach diverges from conventional analyses for the CSO and FCCO problems in that we focus on explicitly bounding the bias and variance terms of the gradient estimator to establish the convergence guarantee. Compared to previous results, our im- provements do require an additional mild regularity assumption on fg and 9, mainly that fe 4th order differentiable. Firstly, as we discuss Remark (2 most common instantiations of C/OFCCCCC framework such 1) invariant logistic regression [16], 2) instrumental variable regression (23]. 3) first-order MAML for sine-wave few shot regression [T] and other problems. 4) deep average precision maximization [26 R4], tend to satisfy this assumption. Secondly, we highlight that the bounds derived from previous studies do not improve when incorporating this additional regularity assumption. Thirdly, ((e-)) remains the lower bound for stochastic optimization even under the arbitrary smoothness constraint [2], demonstrating that our improvement is non- non-trivial. Our results show that, this regularity assumption, which seems to practically valid, can be exploited through novel atrapolation-basee bias reduction technique to provide substantial improvements in sample complexity
We defer some additional related work to Appendix B and conclude with some preliminaries.
Notation. Vectors are denoted by boldface letters. For vector æ, ||a]| denotes f--norm. function with & continuous derivatives is called a C* function. We X b denote that a < Cb for some constant C > O. We consider expectation over various randomness: Eş[-] denotes expectation over the random variable Ş. |E.ig|l [-] denotes expectation over the conditional distribution of r) Unless otherwise specified, for random variable X. [[ denotes expectation over the randomness in X. We focus nonconvex objectives in this paper and use the following standard convergence criterion for nonconvex optimization [8]]
Definition (s-stationary point) For differentiable function F()), we say that æ is a a.first-odder E-stationary point if [[F[)=) E
For notational convenience, in the rest of this paper, we omit the dependence on & (or i in the FCCO context) in the function y and 9n (x)) to represent gr (ar; E).
2 Stochastic Extrapolation as a Tool for Bias Correction
In this section, we present an approach for tackling the bias problem as appears in optimization procedures such BSGD, BSpiderBoost, etc. Importantly, our approach addresses general problem appearing in optimization settings and could be of independent interest. All missing details from this section are presented in Appendix C
For ease of presentation, we start by considering the 1-dimensional case and assume function q: IR + IR, a constant
R. Let ó be random variable drawn from an arbitrary distribution D over R. In Sections 3 and [4] we apply these ideas to the CSO and FCCO problems where the random variable d is played by (c) and function y is played by V Informally stated, our goal in this section will be
Efficiently approximate q(s + E(6]) with few evaluations of {q(s + 8)1aDD
Higher-order smoothness conditions have also been exploited in standard stochastic optimization for performance gains (
3

---

An interesting case is when = 0, where we are approximating ({E(6) with evaluations of {q(0) S-D. 8-DD. Now, q an affine function, then g(s + [ [ Elg(s + 6)} However, the equality does not hold true for general q, and there exists a bias, i.e.. q(( + E[6] - Elg(s + 6)]l > 0. In this
section, we introduce stochastic sstrapolation-base method, where we use an affine combination of biased stochastic estimates, achieve better approximation.
Suppose E C is a continuous differentiable up to 2k-th derivative and let h E[o]. We expand q(8 + 6), the most straightforward approximation of q(s + [())), using Taylor series + h, and take expectation,
Fla(s 6)] [ + h) + o' + 11) E h)] + (++h)
[( h)) ( F h)
2
(2)
+...+ glak ha+ E[(6 (2) (2kj!
(66) h) 1,
(2k (2k-1)
where Φs between 8 and s h. While E + 5) matches q(s h)) in the first terms, the third term is no longer zero. The approximation error (bias) is
| (1(( + 5)] g(* + h) = 9 (+++))
(2k) F h)]] + + 12 (2kk (6s) h)
In order to analyze the upper bound, we make the following assumption on D and q.
Assumption (Bounded moments) For all ~ 'D has bounded higher-order moments: 0t = [E E[8))*] < 00 for 2.3....2
Assumption (Bounded derivatives) The q E C²k and has bounded derivatives, i.e., at sUPxedom(g) (s)) 3o for 1,2,..., 2k.
In addition, we consider sample averaged distribution D,, derived from DD follows.
Definition Given a distribution satissfyig Assumption and m N+, we define the distribution Dm that outputs â where 8 = - 8; with 6; ltd. D.
The moments of such distribution Dm decrease with batch size m as k: 2 2, [[(8 E[ =
O(m - (see Lemma D. Our desiderata would be to construct a scheme that uses some samples from the distribution P,,. construct an approximation of g(s E[ő]) that satisfies the following
requirement.
Definition 3 (ktth-order Extrapolation Operator) Given function q IR R satisfying Assump- tion 2 and distribution Dm, satisfying Assumption | we define kth-order extrapolation operator [K)
as an operator from C²k - 2 that given N = ((k) i.i.d. samples 8,....,5x from Dmn.
satisfies Vs E R: E[TT (k) q[s)] - q(s + [[oo)| 0(m
We now propose a sequence of operators </) : F. ((3) ......... that satisfy the above definition. The cl q(s) is designed to ensure its Taylor expansion at s has a form of q + (EE(( 21)
The remainder OEE((6 2*) is bounded by O(m -k) due to Lemma
A First-order Extrapolation Operator. We define the simplest operator
(1) C q: (a(s + 5)] where 8 i.id. DDm-
In Proposition (Appendix we show that c() is first-order extrapolation operator
Second-order Extrapolation Operator. We define the following linear operator c which transforms g E C# into c(3 q which has lesser bias (but similar variance, as shown later).
Definition
(c Operator) Given Dm and q, define the following operator.
c q: s 2 q(s + ))+)2)= ((o+6;))=(++d2)
where 8 82 1.1.d. Dmn
'Note that if the function is only L, Lipschict continuous, then |E [g(s 8)] q(s + E(])) Luy/r L _ m173" Therefore, this case, q(s 8) does not satisfy the first-order guarantee.
<

---

10"
q(s)
[qls + #(61) - 11 |[s)]و
FI g(s)]
10"
Ftc q(s))
10'
D2, q(s)
la(s E(
10
Burn-in
2 q(s) g(s)
10
16
16'
10" Number of estimates
10"
10
10
10
10
(b) g(s) 84 .(6) = 8/2 where E [0, 2]. Figure 1: The Fig. la investigates the estimation errors of g())) with their number of observations.
(a) ((s) = $ 5 ~ (10, 100), m 1.
The Fig. lb compares the biases of E q(}) with increasing inner batch size m.
Note that 5u442 is same sampling from D2m- The absolute difference in the Taylor expansion of ((2) DD.. at + differs from q( + h) as,
EE [2( ( h)² ((5 h)3 (62 h)) ((((E((8 1) for 8 Lid. D
(3)
The bias error of this scheme can be bounded through the following proposition.
Proposition 1 (Second-order Guarantee) Assume that distribution Dm and q(:) satisfies Assump-
tion
and
respectively with
Then, for all s [
cB a(s) q(( E100)
40.07 90402
5m4 303
48m
96
m
Remark 1 While extrapolation is motivated by Taylor expansion which requires smoothness, higher order derivatives are not explicitly computed. Appendix emepirriaal shows that applying extrapo- lation to non-smooth functions achieves similar bias correction. Relaxing the smoothness conditions is direction for future work.
The above proposition shows that ( is in fact a second-order extrapolation operator with k = under Definition 3 We will use this operator when we consider the CSO and FCCO problems later.
Now, focusing on variance, we can relate the variance of c() 4(s) in terms of the variance of g(s 6). In particular, a consequence of Lemma is that
[[BE ((s) F(C (()))) [O(F(((( + 5) - -F(((s d)))))-
Extension of 2 to Higher-dimensional Case. If q RP + RC is a vector-valued function, Now, for distribution over Rº and
then there is a straightforward extension Definition corresponding sampled averaged distribution Dm and 8 RP
C q: s [2 q(s 61+8)) (((+o))+((e++o)
Lid. ~ D.n-
where 8,, 52
(4)
Higher-order Extrapolation Operators. The idea behind the construction of C can be general- ized to higher k's. For example, in Proposition 3 we construct a third-order extrapolation operator ((3) through higher degree Taylor series approximation
(3) q sesssti (- 38 ( 5 c Dam -
c
+ (s())
While this idea of expressing the k-th order operator as an affine combination of lower-order operators works for every k, explicit constructions soon become tedious.
In Fig.
we empirically demonstrate the effectiveness of extrapolation in stochastic estimation. In
we choose (s)) ()) = 3//2, (V000, 100). For both c(2) q(s) and ( q(x). their estimation
Fig.
la
emror converge to with increasing number of estimates. This coincides with Proposition T as 03
'e use (D) [ ((3) ensure that each estimate
amount of samples (12m).
5

---

and = 0 for quadratic 9. In contrast, biased first order method only converges to neighborhood. In Fig. lb. consider g(s) s and p(6) 6/2 where å E [0, 2]. All three methods are biased and their biases decrease with m, i... O(m *) for keth order method. Depending the constants (c.g. as, Ø²), a higher-order extrapolation method may need decently large (burn-in phase) to outperform lower-order methods.
3 Applying Stochastic Extrapolation in the CSO Problem
In this section, we apply the extrapolation-basee scheme from the previous section to reduce the bias in the [CSO] problem. We focus variants of BSGD and their accelerated version BSpiderBoost based second-order approximation operator (Definition 4.. Let Hg. Hg. and H'S indicate different sets, each of which contains m i.i.d. random varialles/samples drawn from the conditional distribution ((nlE). Remember that, as mentioned earlier, we use 9y(x)) to represent (z;
Extrapolated BSGD. At time f, BSGD constructs a biased estimator of FF(x") using one sample and 2m i.id. samples from the conditional distribution as in (I)
G++1 BSGD
(+) Enjnñ Vog(ø'))
+ En gn(2'))
(5)
To reduce this bias, we apply the second-order extrapolation operator from (4). At time t, we define Di+11 to be the distribution of the random variable 1. En 9r (a')) Then apply ( by setting to Ve and 0, i.e.
m
fee = fe 2m EnEH, (1(2") + 1
2m EnERy 94 (x*)))
2.c
(ife(H Eneh, (x())) ff E Em By (x1)))
(6)
where Eneh, (x') and 1 Eveny Iy (x') are i..d. drawn from Dt+1 In Algorithm (Appendix A we present our extrapolated BSGD (E-BSGD) scheme, where we replace W EnEh, (x(x))) in 5 by < (0) resulting in this following gradient estimate: n.t
G E-BSGD
= ( Eneh, Von(="))
C
Di+1 ff((O). 0.c
Extrapolated BSpiderBoost. BSpiderBoost, proposed by Hu al. (16) uses the variance reduction methods for nonconvex smooth stochastic optimization developed by Fang et al. [10,, Wang et al.
38, BSpiderBoost builds upon BSGD and has two kinds of updates: large batch and small batch update. In each step, decides which update apply based on random coin. With probability Pour- selects large batch update with B1 outer samples of E. With remaining probability
Paut=
selects small batch update where the gradient estimator will be updated with gradient information in the current iteration generated with Bg outer samples of & and the information from the last iteration. Formally, constructs a gradient estimate as follows,
GRsS= + 1 EEEB. BBGD
B2 LEEB,,1831-Rs (G G
G GBSDD)
with prob. 1 P with prob. Pout-
c+++1 nsn
(8)
Bi
We propose our extrapolated BSpiderBoost scheme (formally defined in Algorithm by replacing the BSGD gradient estimates in 8 with E-BSGD.
3 Appendix A
{
[GeBS + B. LEEB,.1B,I=-8 (G D LEEB,, GE.DGD
G GEASSGD)
with prob. - Pout with prob. Pour-
GEBSB
Sample Complexity Analyses of E-BSGD and E-BSpiderBoost. We adopt the standard assump- tions used in the literature 277 35
33
41. All proofs are deferred to Appendix D
Assumption (Lower bound) F is lower bounded by F*

---

Assumption 4 (Bounded variance) Assume that 9n, and Vgn have bounded variances, i.e., for all & in the support of P(E) and x E IR, o2 == E (n - (n E)]l)] < do and C3 == Enelll Von E) E ( e) e) < oc.
Assumption 5 (Lipschitz continuityysmoootnness of Je and 9r) For all E in the support of P(E) fc(+) is Ci-Liscchitz continuous (i.e., (l.f(()) fe(x'))l Il S Cy || -x'1l Vz, x' RP) and Ls- Lipschitz smooth (i.e., f(())) -V((=))
L, || x' 2'122. Vx, x'' E for any &. Similarly. for all & in the support of (Pg) and yj in the support of (()))) 9n(:E) is Cg- -g-ipsschitz continuous and Lipsschhi smooth.
The smoothness of fe and Oo naturally implies the smoothness of F. Zhang and Xiao 44 Lemma 4.2] show that Assumption ensures F is: 1) Cp-Lipschitz continuous with CF = CyCgi and 2) -L-isschitzz smooth with Lp = C + CzL,. We denote LF = C,C + t,yCgLg More- over, Assumption 5 also guarantees that f& and 9n have bounded gradients. In addition, f& and On are assumed to satisfy the following regularity condition in order to apply our extrapolation- based scheme from Section 2
Assumption (Regularity) For all & in the support P()), fe is 4th-order differentiable with bounded derivatives (i.e., := supgERr [[(((((()))))))))) < 00 for = 1,2,3, 4. Vx E R2) and gn has bounded moments upto 4th-order (i.e., d% = supzeR4 sup, Enge Σ [9,, (x) E. (0ne,,,(x)]] <
00, k = 1, 2,2,3.4) 4).
Remark The core piece of Assumption is the 4th order differentiability of V Se as other parts can be easily satisfied through appropriate boundedness assumptions. This condition though is satisfied by common instantiations of CCC We discuss some examples including invariant logistic regression, instrumental variable regression, first-order MAML for sine-wave few-shot regression task, deep average precision maximization in Section S Therefore, our improvements in sample complexity apply to all these problems.
Consider some time <> 0. Let G be a stochastic estimate of F()')) where xf is the current iterate. The next iterate ==1 := a.º - Let F(:] denote the conditional expectation, where we condition on all the randomness until time t. We consider the bias and variance terms coming from our gradient estimate. Formally, define the following two quantities
et-1 bias
(VF(=*) - 1
ELt = E F[G
Our idea of getting to an e-stationary point (Definition will to ensure that gt+1 and Et+1 are bounded. The main technical component of our analyses is in fact analyzing these bias and variance terms for the various gradient estimates considered. For this purpose, first analyze the bias and variance terms for the (original) BSGD (Lemma(5) and BSpiderBoost (Lemma 7 algorithms, which are then used to get the corresponding bounds for our E-BSGD (Lemma (6) and E-BSpiderBoost (Lemma 8) algorithms. Through these bias and variance bounds, establish the following main results of This section.
Theorem 3 [E-BSGD Convergence] Consider the CCO problem. Suppose Assumptions 96
3
hold true and LF, CF, LF, Cg, F+ are constants and C.(fi) == $19 1 +5a.0
defined in Corollary D are associated with second order extrapolation in the CSO problem. Let step size
S 1/(2Tr). Then the output x² of E-BSGI (Algorithm 2 satisfies: F[I]VF((*))]3 < for nonconvex F, if the inner batch size m ((C.CCy-111 and the number of iterations
T - (m
The E-BSGD takes O(s-1) iterations converge and compute O gradients per iteration. Therefore, its resulting sample complexity is (15-1.5) which is more efficient than ( of BSGD. Similar improvements can be observed for E-BSpiderBoost in Theorem
Theorem [E- Be-BSpiddeBBost Convergence] Consider the (CSO) problem under the same assump- tions as Theorem 3 Let step size " 11((LF))) Then the output x² of E- E-BSpiderBoost (Algorithm)
7

---

satisfies: E[IVF(>")Il) S E nonconvex F, if the inner batch size m OG
the hyperparameters of the outer loop E- E-BSpiderBoost B1 (L2//m Cz)e B2 vB1, Pow 12 and the number of iterations
T= ((((p((((z)) P -
The resulting sample complexity of E-BSpiderBoost is O 3.5, which improves O( bound of BSpiderBoost [16 and () bound of V-MLMC/RT-MLM
4 Applying Stochastic Extrapolation in the FCCO Problem
In this section, we apply the extrapolation-base scheme from Section 2 to the problem. We focus on case where ()-2). For larger n, we can treat the FCCO problem as a CSO problem and get an ( 3.5) bound from Theorem 4
(s=33.))
All missing details are presented in Appendix E
Now, straightforward algorithm for FCCO is
the finite-sum variant of SpiderBoost (or 38) in Algorithm S this case, if we choose the outer batch sizes to be B1 n,
SPIDER) [T]
B2 v and the inner batch size to be m max(s-? //n,e-//)). The resulting sample complexity of B-BSpiderBoost now becomes, O(max(////22)) 1//ne*)), which recovers ((=-3.6) bound as in Theorem
4 for = () However, when n is small, such as O the sample complexity degenerates to (s which is worse than the (2(=5)) lower bound of stochastic optimization (3). We leave the details to Theorem 8 We still use Assumptions 3 6 for the analysis of FCCO problem, replacing the role of ç with
Algorithm 1 E-NestedVR
1: Input: x0) E Rd. step-size y, batch sizes S1, S2, B1, B2, Probability Pin: Pout
2: for = 0, 1...., T 1 do
3:
if 0) or (with prob. Pout) then
b Large outer batch
4: for i E B, ~ [n] with [ = B, do draw y from distribution D defined in (TO)
5:
6:
compute xt+1 using (11) and define of x²
7:
end for 8: GE-NVR EieB, (2.+1) (2) D (((
9:
else
D Small outer batch
10:
for i E B2 with [B2] = Bg do
11:
draw y: 1+1 and y from distribution Di++1 and D y. y.i compute xf+1 using (II) and define of x² end for GFNNVR GENVR n2 Eieo, ( TT [C
defined in 10
12:
14:
(C D V.((0) -/2 Vf(())
end if
17: end for -
16:
x+1 x - 1
18: Output: xx picked uniformly random from (x') )-
Extrapolated NRstedVR. We now introduce nested variance reduction algorithm E-Nested which reaches low sample complexity for all choices of n. Missing proofs from this section are presented in Appendix [ For the stochasticities in the SpiderBoost variance reduction components:
our idea is to use two nested for the outer random variable and the other for the inner random variable n/.. In each outer (resp. inner) SpiderBoost step, we choose large batch B (resp. S1) with probability Pour (resp. Pin); otherwise we choose small batch. Let H, denote set of m i.i.d. samples drawn from the conditional distribution P(n]i).. Similarly, let H, denote another set of i.i.d. samples drawn from the same conditional distribution. For each given i, we approximate E (x,, with y ++1 from distribution D where,
ΣmEH, (x=") ΣnEH, (x,) (o))
with prob. Pio t with prob. - Pin-
y M
+ 55
Σ
(10)
Similarly, we approximate Eşja (og((())) with 2 defined as follows
Ceen; (z)(
with prob. Pin or l t= 0 with prob. 1 Pmn:
(11)
85 Enen, (Vg((x)) - Vgg((!))
8

---

Sub-ogtimali
10
Sub. caab-ppttmlllly
10"
E-BSCD DSpiderBoast V-MLMC
30
BSGD
BSpideBBoost E E-BppeerBoost
NestadVR E N-NestedVR
10
E E-BSGD
10
265
465
2 Samples
465
265
465
166 # Samples
266
(a) CSO: Large n = 50000
(h) FCCO: small n 50
Figure Performances algorithms and their extrapolated versions on the invariant logistic regression task. Algorithms each subplot use the same amount of inner batch size in each iteration. The shaded region represents the 95%--cnffidnce interval computed over 10 runs.
where Φ is the last time is visited before time t. If is not selected at time t, then y y and 1+1 2/. Note that we use independent samples for yf and 2
Finally, we present E-Nested in Algorithm where second-order extrapolation operator C!2) is applied to each occurrence of ft- We now analyze its convergence guarantee. Our analysis works by first looking at the effect of multi-level variance reduction without the extrapolation (that we refer as NestedVR, Theorem TO Appendix [..), and then showing how extrapolation could further help to drive down the sample complexity.
Theorem [E-NestedVR Convergence] Consider the FFCO) problem. Under the same assump- tions as Theorem 3
If n ( (2-3),), then we choose the hyperaparameters of E-NestedVR (Algorithm 7 as
Bi = B2 = n. Pont = S1 = -iee-,
LLe Pm. = L = O (
If n = S2 2/3), then we choose the hyperaparameters of E-NestedVR as B1 = n2, Bg
Ti, Pow = 1/ S = S2 max CC 1/2 "e,C===),, Pin = 1,7 (
Then the output x" of E-NestedVR satisfies: E[[[F[(**)] s E2, for nonconvex F' with iterations T 2 (LL - ?))
From Theorem E-NestedVR has a sample complexity of O(ne 3)) in the small n regime (n O(e-2/( 2) and (max /v 1/ (n)r)))) in the large regime (n Qi ((33). Therefore, in the large n regime, this improves the Onne-3 sample complexity of MSVR-V2 V2 19
5 Applications
In this section, demonstrate the numerical performance of our proposed algorithms. We focus the application of invariant logistic regression here. Appendix F we discuss performance of our proposed algorithms on other common FCCO applicatoos.........
5.1
Application of Invariant Risk Minimization
Invariant learning has wide applications in machine learning and related areas 22 Invariant logistic regression [66 is formulated as follows:
min
[log(1 + exp(- [v]] x)),
where a and represent a sample and its corresponding label, and is a noisy observation of the sample This first part be considered as CSO objective, with fe(v) = log(1 exp(-by)) and (,; {) :) æ. As the loss f& E C is smooth, results from Sections and 4 are applicable.
An ferregulrrizer added ensure the existence of an unique minimizer. Since the gradient of the penalization term is unbiased, we only have to consider the bias of the data-dependent term. We generate a synthetic dataset with d = 10 dimensions. The minimizer is drawn from Gaussian distribution x* ~ (0 1) Rd. We draw invariant samples {aa b.)); where a; ~ W/ 1) e Rd and compute b, = sgn(a, x²) and its perturbed observation 77 ~ Na(a, 100) E Rd.
We consider drawing & from a large set (n = 50000) and a small set (n = 50) as CSO and FCCO problems respectively. As basclines, we implemented the BSGD and BSpiderBoost methods

---

10"
Sub-optimallyy
NestadVR E-NesledV
Subggptrigality
1e-1
BSBSG DSpiderBoast
10"
80-
1o-2
V-MLMC
NestedVR
BSGD
BSoiderBonst BSpiderBoost
0-
E-BSGD
10
0.0
1.0 0.0
0.5
0.0
1.0
0.0
0.5
1.0
1e8
Samples 1e6
1e6
# Samples
1e6
(a) CSO: Large 10000
(b) FCCO: small n
Figure 3: Performances of algorithms and their extrapolated versions the instrumental variable regression task. The shaded region represents the 95%-<confidence interval.
from [16.. V-MLMC approach from 177, and Ne approach from Appendix E.2 which achieves the same complexity as MSVR-V2 V2 [19] for the FCCO problem. RT-MLMC shares the same sample complexity as V-MLMC, and is thus omitted from the experiment [17]. The results are shown in Fig. 2 In the CSO setting, we compare biased gradient methods with their extrapolated variants (BSGD vs. E-BSGD, BSpiderBoost vs. E-BSpiderBoost, and NestedVR vs. E-Nested The extrapolated versions of BSGD, BSpiderBoost, and NestedVR consistently reach lower error than their -xneaatrapol counterparts, as evident Figure 2a this case, the performance of BSpiderBoost is similar to BSGD as also noted by the authors of these techniques [[6], and drawback of BSpiderBoost seems to be that it is much harder tune in practice. However, it is clear that E-BSGD outperforms BSGD, and E-BSpiderBoost outperforms BSpiderBoost, respectively. In the FCCO setting, we compare extrapolation based methods and MLMC based methods. Figure [2a shows that E-Nested outperforms all other extrapolated algorithms, including the V-MLMC approach [7], matching our theoretical findings.
5.2 Application of Instrumental Variable Regression
Instrumental variable regression is a popular technique in econometrics that aims to estimate the causal effect of input X on a confounded outcome Y with an instrument variable Z, which, for given X, is conditionally independent of Y. As noted by (23). the instrumental variable regression is a special case of the CSO problem. The instrumental variable regression problem is phrased as:
min (iinEE Ex2,Exx2lxx(x))
where & (Y, X. This can be viewed in the CSO framework with fe(-) = E(Y, :). We choose fly, g) log cosh(y 9) regression loss function and (x(w) w X to be linear regressor. In this case, Je E C with V [e = tanh(ý - YY, and our results from Sections and apply. We generate the data similar to 31
Z ~ Uniform(1-10)000 3
1O,1),, 8 00,,00, 7 Exponential(10)
X= 21 + 2 Y x
where 21 is the first dimension of Z, is the confounding variable and 8, 7 are noises. In this experiment, we solve the instrumental variable regression using BSGD, BSpiderBoost, Ve and their extrapolated variants described in Sections 3 and 4 In each pair of experiments, the samples used per iteration are fixed same, i.e.: 1) BSGD uses m 2 and E-BSGD uses m = 1; 2) For BSpiderBoost and E-BSpiderBoost. we use cycle length of 10, small batch and large batch in Spider to be 10 and 1 100 respectively, and we choose inner batch sizes m = for BSpiderBoost and m = 1 for E-BSpiderBoost; 3) For NestedVR and E-NestedVR, we fix the outer batch size 10 and 5 respectively, and choose fix the inner Spider Cycle be 10 with large batch 100 and small batch 10. The results are presented in Figure 3 As is quite evident, the extrapolation variants achieve faster convergence in all 3 cases, confirming theoretical findings.
6 Concluding Remarks
In this paper, we consider the conditional stochastic optimization CSO problem and its finite-sum variant FCCO) Due to the interplay between nested structure and stochasticity, most of the existing gradient estimates suffer from large biases and have large sample complexity of O(E-5) We propose stochastic extrapolation based algorithms that tackle this bias problem and improve the sample complexities for both these problems. While we focus nonconvex objectives. our proposed algorithms can also be beneficial when used with strongly convex, convex objectives. We also believe that similar ideas could also prove helpful for multi-level stochastic optimization problems (41 with nested dependency.
10

---

Acknowledgements
We would like to thank Caner Turkmen, Sai Praneeth Karimireddy, and Martin Jaggi for helpful initial discussions surrounding this project.
References
[1] Fabio Anselmi, Joel Z Leibo, Lorenzo Rosasco, Jim Mutch, Andrea Tacchetti, and Tomaso Poggio. Unsupervised learning of invariant representations. Theoretical Computer Science, 633:112-121, 2016.
[2] Yossi Arjevani, Yair Carmon, John C. Duchi, Dylan J. Foster, Ayush Sekhari, and Karthik Sridharan. Second-order information in non-convex stochastic optimization: Power and limitations. In Jacob D. Abernethy and Shivani Agarwal, editors, Conference on Learn- ing Theory, COLT 2020, 9-12 July 2020, Virtual Event [Graz. Austria]. volume 125 of Proceedings of Muchine Learning Reseurch, pages 242-299.. PMLR, 2020. URL http //proceedings. mlr atress/v125/// www.neeannia..... /0aae///a/////aaaaa2aa. html
[3] Yossi Arjevani, Yair Carmon, John C Duchi, Dylan J Foster, Nathan Srebro, and Blake Wood- worth. Lower bounds for non-convex stochastic optimization. Mathematical Programming, pages 1-50, 2022.
[4] Sébastien Bubeck, Qijia Jiang, Yin Tat Lee, Yuanzhi Li, and Aaron Sidford. Near-optimal method for highly smooth convex optimization. In Alina Beygelzimer and Daniel Hsu, editors, Conference on Learning Theory, COLT 2019, 25-28 June 2019, Phoenix, AZ, USA, volume 99 of Proceedings of Machine Learning Research, pages 592-507. PMLR, 2019. URL http: //proceedings. mlr .ress////////... w999b99bcc1999990 html
[5] Bo Dai. Niao He, Yunpeng Pan, Byron Boots, and Le Song. Learning from conditional distributions via dual embeddings. In Aarti Singh and Xiaojin (Jerry) Zhu, editors, Proceedings of the 20th International Conference Artificial Intelligence and Statistics, AISTATS 2017, 20-22 April 2017, Fort Lauderdale, FL, USA, volume 54 of Proceedings of Machine Learning Research, pages 1458-1467. PMLR, 2017. URL http::/ mlr press grress/56. v54/ dail7a. html
[6] Bo Dai, Albert Shaw, Lihong Li, Lin Xiao, Niao He, Zhen Liu, Jianshu Chen, and Le Song. SBEED: convergent reinforcement learning with nonlinear function approximation. In Jen- nifer G. Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmüssson, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pages 1133-1142. PMLR, 2018. URL http:tttt//rcceedinggg
mlr press/ http///v0///a///// dww.8c..11.... html
[7] Aaron Defazio, Francis R. Bach, and Simon Lacoste-Julien. SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives. In Zoubin Ghahramani, Max Welling, Corinna Cortes, Neil D. Lawrence, and Kilian Q. Weinberger, editors, Advances in Neural Information Processing Systems 27: Annual Conference on Neu- ral Information Processing Systems 2014, December 8-13 2014, Montreal, Quebec, Canada. paper / 2014/hash/ neurips cc/ wttppccccppp///cceeeee/e
pages 1646-1654, 2014. URL wwteer3777-bbttaacee Abstract.
[8] Bradley Efron. Bootstrap methods: another look at the jackknife. Springer, 1992.
[9] Yuri M Ermoliev and Vladimir I Norkin. Sample average approximation method for compound stochastic optimization problems. SIAM Journal on Optimization, (3(4):2231-2266 2013.
[10] Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. SPIDER: near-optimal non- convex optimization via stochastic path-integrated differential estimator. Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò
and Roman Garnett, editors, Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018 December 3-8, 2018, Montréal, Canada, pages 687-697, 2018. URL https: httpce////ooceodeeeeeeeee hash http:/68884444222222222222182333 www.sedddddb--bbtbat.ccaoac Abstract.hta

---

[11] Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnosten meta-learning for fast adapta- tion of deep networks. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning, ICML 2017. Sydney, NSW, Australia, 6-11 August 2017, volume 70 of Proceedings of Machine Learning Research, pages 1126-1135. PMLR, 2017. URL httphttt///poooeeding.... mlr hta.a/prree/////fiinn//aa html
[12] Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):2341-2366 2013.
[13] Takashi Goda and Wataru Kitade. Constructing unbiased gradient estimators with finite variance for conditional stochastic optimization. ArXiv preprint, abs/2206.01991, 2022. URL https
//arxiv. www./////////////oeo/.oooee.eee/ /206. 01991
[14) Yanjun Han, Jiantao Jiao, and Tsachy Weissman. Minimax estimation of divergences between discrete distributions. IEEE Journal on Selected Areas in Information Theory, 1(3):814 823, 2020.
[15] Yifan Hu, Xin Chen, and Niao He. Sample complexity of sample average approximation for conditional stochastic optimization. SIAM Journal on Optimization, 30(3): 2020.
[16] Yifan Hu, Siqi Zhang, Xin Chen, and Niao He. Biased stochastic first-order meth- ods for conditional stochastic optimization and applications in meta learning. In Hugo Larochelle, Mare Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Con- ference Neural Information Processing Systems 2020. NeurIPS 2020, December 6- 12, 2020, virtual, 2020. URL. hhtpss: http:::://pocceddings. htwp:ooeeddinng.nnuriip..p. wttpppppp.cppppp/ppppppppppppeep (apper/2020/asiii of 1cdf 1 441ee6699d1d22371 7 76c c2dca Abstract. html
[17] Yifan Hu, Xin Chen, and Niao He. On the bias-variance-cost tradeoff of stochastic optimization. Advances in Neural Information Processing Systems, 34:22119-22133 2021.
[18] Prateek Jain, Purushottam Kar, al. Non-convex optimization for machine learning. Founda- tions and Trends& in Machine Learning (033-4):142-363 2017.
[19] Wei Jiang, Gang Li, Yibo Wang, Lijun Zhang, and Tianbao Yang. Multi-block-single- vari- ance reduced estimator for coupled compositional optimization. ArXiv preprint, abs/2207.08540, 2022. URL /tttps://arrt
org/ /b800200.085400 08540)
[20] Jiantao Jiao and Yanjun Han. Bias correction with jackknife, bootstrap, and taylor series. IEEE Transactions on Information Theory, 66(7):4392-4418 2020.
[21] Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predic- tive variance reduction. In Christopher J. C. Burges, Léon Bottou, Zoubin Ghahra- mani, and Kilian Q. Weinberger, editors, Advances in Neural Information Processing Sys- tems 26: 27th Annual Conference on Neural Information Processing Systems 2013. Pro- ceedings of meeting held December 5-8, 2013, Lake Tahoe, Nevada, United States. pages 315-323, 2013. URL https: httpss//proceeding: iew.eeddinngg.euripp...... neurips cc/ htt//aappr////// 2013/hash/ ac (aaa2296ccceeed11666886666666863
Abstract .tml
[22] Youssef Mroueh, Stephen Voinea, and Tomaso A. Poggio. Learning with group invariant features: A kernel perspective. In Corinna Cortes, Neil D. Lawrence, Daniel D. Lee, Masashi Sugiyama, and Roman Garnett, editors, Advances in Neurul Information Processing Systems Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada, pages 1558-1 156,, 2015. URR/httss:/pproceddiii www.:eeeeednnnnnnuiiii.i.r.. .neurips /ttppeer//0/////a/t////222222222 /11///60000099101111133330011600 www.:3/4444771884444444444444444 Awstract..ttt..........aa.
28: Annual Conference
cc/ cc/paper/200 20110/ashhhhheeeeee.
[23] Krikamol Muandet, Arash Mehrjou, Si Kai Lee, and Anant Raj. Dual instrumental variable regression. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florin Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6- 12, 2020, virtual, 2020. URL https:: htttpp::/pproceedingg neuripu http://7tt--Atttattttto html
[24] Ofir Nachum and Bo Dai. Reinforcement learning via fonchel-rockafellla duality. ArXiv preprint, abs/2001.01866 2020. URL https://axxxii...... org/ abs/201 01866
12

---

[25] Lam M. Nguyen, Jie Liu, Katya Scheinberg, and Martin Takác. SARAH: A novel method for machine learning problems using stochastic recursive gradient. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, volume 70 of Proceedings of Machine Learn- ing Research, pages 2613 PMLR, 2017. URL http: httt:://proceedingss mll presa/ /70/nguyen17b. html
[26] Qi Qi, Youzhi Luo, Zhao Xu, Shuiwang Ji, and Tianbao Yang. Stochastic optimization of areas under precision-recall curves with provable convergence. In Marc' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, edi- tors, Advances in Neural Information Processing Systems 34: Annual Conference on Neu- ral Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pages 1752-1765, 2021. URL p hew.eeeddinnnnn.nniisssse. neurips ceourpp..c/ppppeeeee cc/paper///cppccppcpcccccc /aeeer//22///hhh//// 0ddi1bc63aa1160cccccc/// 72232223522722222252222 Abstract.hir
[27] Qi Qi, Youzhi Luo, Zhao Xu, Shuiwang Ji, and Tianbao Yang. Stochastic optimization of areas under precision-recall curves with provable convergence. Advances in Neural Information Processing Systems, 34:1752-1765. 2021.
(28) Sashank J. Reddi, Ahmed Hefny, Suvrit Sra, Barnahás Póezos, and Alexander J. Smola. Stochastic variance reduction for nonconvex optimization. In Maria-Florina Balcan and Kilian Q Weinberger, editors. Proceedings of the 33nd International Conference on Ma- chine Learning, ICML. 2016, New York City, NY, USA, June 19-24, 2016, volume 48 of JMLR Workshop and Conference Proceedings, pages 314-323. JMLR.org. 2016. URL html
http: http:///proceedings. mlr, /ttp://iiinn.......rsss/////////
[29] Sashank J Reddi, Suvrit Sra, Barnabás P6ezos, and Alex Smola. Fast incremental method for nonconvex optimization. ArXiv preprint, abs/1603.06 (1166000.19,,,0 2016. (tttp:/::///aat org/ abs/1603, 06159
[30] Mark Schmidt, Nicolas Le Roux, and Francis Bach. Minimizing finite sums with the stochastic average gradient. Mathematical Programming, 162(1))83-112, 2017.
[31] Rahul Singh, Maneesh Sahani, and Arthur Gretton. Kernel instrumental variable regression. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer. Florence d'Alché-Buc, Emily B. Fox, and Roman Garnett, editors, Advances Neural Infor- mation Processing Systems 32: Anmual Conference on Neural Information Process- ing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 4595-4607, 2019, URL http:///ccceeege...o.o
e22b3 Abstract.htm
[32] John Tukey. Bias and confidence in not quite large samples. Ann. Math. Statist., 29:614, 1958.
[33] Bokun Wang and Tianbao Yang. Finite-sum coupled compositional stochastic optimization: Theory and applications. In International Conference on Machine Learning, pages 23292- 23317. PMLR, 2022.
[34] Guanghui Wang, Ming Yang, Lijun Zhang, and Tianbao Yang. Momentum accelerates the convergence of stochastic AUPRC maximization. In Gustau Camps- Valls. Francisco J. R. Ruiz, and Isabel Valera, editors, International Conference Artificial Intelligence and Statistics, AISTATS 2022, 28-30 March 2022, Virtual Event, volume 151 of Proceedings of Machine Learning Research, pages 3753-3771. PMLR, 2022. URL htttt:::/proceeeeeeeee .ml. press/v151.. wttp////11w//22bbbbmm html
[35] Guanghui Wang, Ming Yang, Lijun Zhang, and Tianbao Yang. Momentum accelerates the convergence of stochastic aupre maximization. In International Conference on Artificial Intelligence and Statistics, pages 3753-3771. PMLR, 2022.
[36] Mengdi Wang, Ji Liu, and Ethan X. Fang. Accelerating stochastic composition optimization. In Daniel D. Lee, Masashi Sugiyama, Ulrike von Luxburg, Isabelle Guyon, and Roman Gar- nett, editors, Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain. pages 1714-1722, 2016. URL httpps:///rrooeedingg neurips cc/ wwtpc//ppppppp//eeeeeee 92262bf907 af 0122 wtt.://33333330000000oeeee Abstract.htm)
13

---

[37] Mengdi Wang, Ethan X Fang, and Han Liu. Stochastic compositional gradient descent: algo- rithms for minimizing compositions of expected-value functions. Mathematical Programmiing. 161:419 449, 2017.
[38]
Zhe Wang. Kaiyi Ji, Yi Zhou, Yingbin Liang, and Vahid Tarokh. Spiderboost and momen- tum: Faster variance reduction algorithms. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-Buc, Emily B. Fox, and Roman Gareet, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 2403-2413, 2019. URL httttp:://prrceeednng nee..nnurippe httpp/pppp.cccpppp///////////// Abstract. html
[39] Christopher Stroude Withers. Bias reduction by taylor series. Communications in Statistics- Theory and Methods, 16(8):2369-23) -3333,9-33,,, 1987.
[40] Yu M Yer. A general stochastic programming problem. 1971.
[41] Junyu Zhang and Lin Xiao. Multilevel composite stochastic optimization via nested variance reduction. SIAM Journal on Optimizaaiion, 131-11177 2021.
14

---

Appendix
Missing Pseudocodes
15
Missing Details from Section
15
1
Other Related Work
15
Missing Details from Section 2
17
Stationary Point Convergence Proofs from Section 3 (CSO)
D.I
Helpful Lemmas
D.2
Convergence of BSGD
23
D.3
Convergence of E-BSGD
25
D.4
Convergence of BSpiderBoosi
26
D.5
Convergence of E- E-BSpiderBoost
30
Stationary Point Convergence Proofs from Section (FCCO)
E-BSpiderBoost for FCCO problem
Convergence of NestedVR
32
E.3
Convergence of E-NestedVR
41
Missing Details from Section
46
Application of First-order MAML
46
Application of Deep Average Precision Maximization
Necessity Additional Smoothness Conditions
47
A Missing Pseudocodes
We present pseudocodes of F-BSGD and E-BSpiderBoost scheme in Algorithms 2 and
respectively.
Algorithm E-BSGD
1: Input: x E Rd, step-size batch sizes m
2: for 0, 1,.,,
do
3: Draw one sample & and compute extrapolated gradient G
BE from
4: x=+1 x² G
E-BSDD
5: end for
6: Output: x" picked uniformly at random from {x* Ja
B Missing Details from Section 1
B.1 Other Related Work
CSO. Dai et al. (5] proposed primal-dual stochastic approximation algorithm to solve min-max reformulation of CSO employing the kernel embedding techniques. However, this method requires convexity of ft and linearity of 9n, which are not satisfied by general applications when neural networks involved. Goda and Kitade [13] showed that special class PCCSSpppoolenn can be
15

---

Algorithm 3 EE-SpiderBooss
Input: x. Rd. step-size y, batch sizes B1, B2, Probability Pout
2: for = 0, 0.1,...,7
do Draw Xout from Bernoulli (Pom)
3:
4:
if' (t 0) (Xout = then Draw Bj outer samples (EI,-..,$B, }
Large batch
5:
6:
Compute extrapolated gradient G++1 with (
BEBBBB B.
1
DEES,
G++1 B-BDGD
7:
else
Small batch
8:
Draw Bg outer samples f }
9:
Compute extrapolated gradient GFBSGD with 7
GL+1 CEBBSBB = GE + 1
B2 EgeB, E-BSGD - GEBBSGD)
10:
end if
11: x² x² 7
12:
end for
13:
Output: x" picked uniformly random from {x*} T-1 1==0
unbiased, e.g., when f& measures the squared error between some u(E) and En (æ;; E giving rise this objective function Eg [((({E) E, [9, E.) However, they did not show any improvement over the sample complexity of BSGD (i.e.. O( ((=-)), Hu et al. [16] also analyzed lower bounds on the minimax error for the CSO problem and showed that for a specific class of biased gradients with (E)) bias (same bias BSGD) and variance (11) the bound achieved by BSpiderBoost is tight. where the
probeele
However, these lower bounds are not applicable in settings such as ours (and also 17
bias is smaller than the BSGD bias.
Variance Reduction. The reduction of variance in stochastic optimization is a crucial approach decrease sample complexity, partieularly when dealing with finite-sum formulations of the form min, Σd fi()). Pioneering works such as Stochastic Average Gradient (SAG) (30), Stochastic Variance Reduced Gradient (SVRG) [21 28) and SAGA 77 29 improved the iteration complexity from ((s 4 in Stochastic Gradient Descent (SGD) to (
Subsequent research, including Stochastic Fath-Integrated Differential Estimator (SPIDER) I0O and Stochastic Recursive Gradient Algorithm (SARAH) (25), expanded the application of these techniques both finite-sum and online scenarios, where n is large or possibly infinite. These methods boast an improved sample complexity of minnv/ne-22 3). SpiderBoost (38), achieves the same near-optimal complexity performance as SPIDER, but allows much larger step size and hence runs faster in practice than SPIDER. In this paper, we use probabilistic variant of SpiderBoost as the variance reduction module for CSO and |CCO problems. We highlight that alternative techniques, such as SARAH, can also be applied and offer similar guarantees.
Bias Correction. One of the classic problems in statistics is to design procedures to reduce the bias of estimators. Well-established general bias correction techniques, such as the jackknife [32] bootstrap (8), Taylor series [39 14), have been extensively studied and applied in various contexts (20]
However, these methods are predominantly examined in relation to standard statistical distributions, with limited emphasis on their adaptability to optimization problems. Our proposed extrapolation- based approach is derived from samplc-splitting methods [14], specifically tailored and analyzed for optimization problems involving unknown distributions.
Stochastic Composition Optimization. Finally, closely related class of problems, called stochastic composition optimization, has been extensively studied (e.g., 44 the goal is:
36 37) in the literature where
min RERd
(E,
(12)
Despite having nested expectations in their formulations CSO and 12 are fundamentally different: a) in stochastic composite optimization the inner randomness 1) conditionally dependent on the outer randomness & and b) in CSO the inner random function (x, {) depends on both and r). These differences lead to quite different sample complexity bounds for these problems, as explored in Hu al. [15]. In fact, Zhang and Xiao [1 presented near optimal complexity of O(min(s- vnns" -2))
16

---

for stochastic composite optimization problems using nested variance reduction. While Wang et al. 36) also use the "extrapolation" technique, their motivation and formula significantly different from ours and cannot reduce the bias in the CSO problem.
C Missing Details from Section 2
Lemma (Moments of Dm) The moments of 8 E Dm are bounded as follows
E[(ó [[ = 22
[[( - - n E[(6 [[]])*] = th + 3(m 1)
m
m
More generally, for k 2 2,
E [[5) O (m- 14/21).
Proof: Define = 5 - E [0] as the centered random variable. Now
[[(6 [ El0²).
So we focus on E(8a] in the remainder of the proof. For A: = 2,
[[ =
E| m
8 =
+
E
Σ 6 +
8,83 m
m
For 3,
m |E
EE> 8,131
E
8755 + EiErsfe
m3
For = 4,
[E[8*]
1, E|E m 1,111
E
Σ, 8 + + +4Σ
+68 8383 + + Ei 8.8,6,6.]
m
m El ((8 + (6mmmm))) E E(39)
m.
2
3(m 3(m-1)03 1)03
24 m3
m
For k = 5,
IF
m [=
i==
m
8,151
1
E
Σ, 88 10 10E44 83358888) 8883]
m
m
[ + 10m (m ((83)
10(m-1 D0302
For general & > 0, we expand the following term as function of 1
E
E &.1.1. me
As E[ō.] = 0 and 6, and 8, are independent for different i and j. the outcome has the following form
E|5a1 = m O
Σ 202 202+303-44 d.... kag
m m
0220 ag ...
02 0g
4k k
(13)
0,20
where Σ a; is the count of independent (8)) used in 0 og
0 .
Among the terms in
the dominating one in terms of m is one with largest Et= a4 i.c.
E = mE
Omm )o k/2
if even,
m² Om L4/2) )o! 18/2|-1
03
if odd.
Then, we can simplify the upper right-hand side with
[EE5*1 = Om k++
which gives all the desired results.
17

---

Proposition 2 (First-order Guarantee) Assume that Dn and q(-) satisfy Assumption 7 and re-
spectively with k = 1. Then, Vs E IR, E Din a(t) g(s + [[]]] S 0202/(2m).
Proof: Let h = E[o]. If the function q E C², then the Taylor expansion at + h with remainders
leads to
Elg(s + 6)] = g(s + h) + (s h) hj + Ely" h)
where Φ1 between + h and s + 5. Then the error of extrapolation becomes
E[g(s + 6]] - <(s - 1)] = 1/ (6)) h) - / [[(6 - 1.
By Assumption 2 and Lemma 1 we have that
Elg(s + +6] - (ss + +h)l - 3 E[( h) = 2 El(6 h) =
2202
'.
This completes the proof.
Proposition 1 (Second-order Guarantee) Assume that distribution Dm and q(-) satisfies Assump-
respectively with k = 2. Then, for all 8 E R. E [ a(>) - 4(( - -[6)) s
tion
and
40g07 1
Sas aa 04-302
48m
96
m
Proof:
Let = E(8). If the function q E C2, then the Taylor expansion at + h with remainders
leads to
Elg(s + 81)] hh) +
ht] + y (((++)) El(81 - -h) + (a+h) E[(8] h)
(o)) - -]]*]
Elg(s + 02)] (q + h) + + h)) Fl5 h] + (((++)) El(62 - h)) + (x+h)) F( h))]
+ 24 Elg (02) - -])*]
Elg(s + S - (s + h) + ((s + h) E[ E h] + q ((tth
E[( Ti
h)
1 (a+h) hl El( - - I1 1t2 Elg ((ss) (ميك h1 1
where Φ1, d2. 03 between s and + 81, + 82. + 63 respectively.
As E18 h] = 0, the error of extrapolation becomes
E E D.m [(s) q(s h)1
E
(:0) (s+h))
662 - h)
[ (ctt))))
(81 h) + E E (82 h1)11)
+
E
(dx))
(51+662
h)²] 1
[E]T (d))
(81 h>*1 El
E (4) (62)
(52 n))a))
24
2
24
24
4a
2
E
62
11)
(E[(6) h19 + E[ - h))1)]
+
2
(dba)
(5i
h) h)]] - 1/2 [E]" ( (d))
(81 h)*1 + El "
((22) (122) (52 h))+)
24
24
24
09
2
61
h))]
(E( h + E El - h) 1))1)]
+ 2
9
(4) (da))
404 - h)) + [L] 10 (di)) (6) h)* + E
(do)) (62 - -1)²1)
24
24
24
<
E ( (1 - 11)
(E[(ō) h) + El(s, - h) 1)
( (bu+t2 - 1n) 1 (E((s) 1 + E((62 h) 4D
2
24
where the second inequality uses the upper bound on (-) (Assumption 2b and the third inequality uses (6 - h)2 is non-negative and the last inequality uses the uniform bound on (.) (Assumption 2
18

---

Then
[E[E [6)) g(s + 1:)l
68 [(6]
11)3 + 44 2 61+62 - -h)* + E(d1 - h1)*)
+
3
1)02
+ my +
3(m- 1)03
12m
Am
m
0377
90
3(a1-3o3)
12m 2
2m
4m
4030s + 99.m2
3m
48m
96
we first that E[(ó) - h) E[(d2
- h)
= h) and the uses the bound on moments
Lemma Note that ( h) can be seen the 4th order moments of batch size of 2m.
Proposition 3 Assume q C5 Then ( defined below a thirl-order extrapolation operator.
(3) D q : 36 D + 3 - -3 16 ((2) + +33 )g(s)
(2)
Proof: Let h = E[j]. If q E C²k, then has the following Taylor expansion
Elg(s + 8)] q(s hh) +o'(s + h)) L ht] L (eth) El - +
+...
secoad order term
(2k-)) (2k-1)1
El 1
(l) h) 1))
2
Eliminate the third order term in the Taylor expansion. Consider the following affine combination which
F 33)
F q 1 ai g(s) a
We determine 0n and ar by expanding (/2 ((5) and c ((s) and analyze the coefficients of terms:
(33 (Affine). Taylor expansion of D. g(s) at + h should have zero order term g(s + h), i.e.
aig(s + h) + a2g(s + h) = g(s + h).
(Eliminate third term). Taylor expansion of F(() D ((s) at s + h should have third order
term E((A 3) That is,
a E - 11) az E ( - -1)9| = O.
This is equivalent to
a1 E[(61 h) + 2
(81 h)*
Therefore, 0j and a2 can be determined through the following linear system
01 + = 01 + 102 = 0.
The solution is 01 = - 3 and 02 =
For l = 3 order extrapolation, consider the following
(3)
q: at af g(s) + o(y Dam. y (s) + a5 De... g (s).
We determine af, al and al by satisfying the following two conditions
(3) (Affine). Taylor expansion of C g(s) at + h should have zero order term q(x + h), ie.
(a + oa + als (x + h) g(x + h)-
19

---

of + a + ag =1 a 0/ + 2 =0 a 2 + Jag O. Taylor expansion of L g(s) at 8 + h should have 4th order term E[[6 [.) That is
a This equivalent to
- - a² E ( n))
+ +as
( 11) = 0.
ai + क gg (ab)) (E((ō) 1))1)) 0.
# 27
El(6: - 11) =
Therefore, 01, a22 and ol can be determined through the following linear system
The solution is a 1 a22 - and ag 4' Then consider the Taylor expansion of 2 q(s) at + h with (2).
IE(C2 {(s)] ( + h)1 S (5) + h) [[ 1)) + |lg (og n)) z O(aas + am)m 3)
where the first inequality uses the fact that <Bn is affine mapping and the last inequality uses Lemma Therefore, </0 is 3rd-order extrapolation operator. We can expand it into
D 8 +
1 12
Dm q(s) D2m
g
4 3 (-3c ((s) + 1 a (s)
+
1
9
3 Dam
1 (2)
((8) + + _ (6))
(- 36
+ $ (2) 3 3
16
9 P + +cc
Dam )a(8).
g
Lemma (Variance Bound) Assume that q : RP IR in Ca and Dm is the distribution in Assumption 7 Suppose that the variance of q(s + 8) is bounded as
E[]a(( + +6) Elg(s 8)]1 v2 +C.
Then the variance of extrapolation </3) q(s) is upper bounded by
[||c8, g(s) E[C {($) 2
E
S 14( V2 +C).
Proof: Let us use the definition of cB3 (()):
E cle ((s) E(C {(s)
2
<
E
12q(s
g( (((+8))+(0+t62))
E 22((s B1462)
g( )=((+t))))
2
S 3F
[ + 8L482)
-F [2q(s + 5. )] 111 +3F (((+))))
F
(1)
2
+ +3E
(2)
(((++22)
< 12(
V2
+ CC)
+ 2 m
V2
+ C) + ( 1 V2
C)
2m
m
15V2
27C 2
2m
This completes the proof.
20

---

D Stationary Point Convergence Proofs from Section 3 (CSO)
In this section, we provide the convergence proofs for the CSO problem. We start by establishing some helpful lemmas in Appendix D. In Appendix D.2] we reanalyze the BSGD algorithm obtain
explicit bias and variance bounds, which then usetul when analyze E-BSGD in Appendix [D.3 Similarly, we reanalyze BSpiderBoost Appendix D.4 and use the resulting bias and variance bounds for the analysis of E-BSpiderBoost in Appendix D.5
Note that throughout our analyses, we define conditioning on the randomness until time L. When there is no ambiguity, we use E[|] instead of
[.tt] as the expectation randomness at time + 1
[-t).
D.I Helpful Lemmas
Lemma (Sufficient Decrease) Suppose Assumption 5 holds true and 7y S
2bF 1 then
VF(2>)] 2 L + &
where El-] denote conditional expectation over the randomness at time t conditioned on all of the past randomness until time t.
Proof:
In this proof, use E|-] denote conditional expectation over the randomness at time t conditioned on all the past randomness until time
Let us expand F1 and apply the -m-smothsness F
E[F + S ((())))))))))))))
Le 2
E|
G [
Since |||| = ||] G - E|G + 1| ||E| gt+1 + ||E[ |1|2 then
[[F(x*+) - F(x²) F((VF(x F( (x'), G + Le (Et + ||[|
Expand the middle term with
-y E(VE(('), = = VF (=') 11
|E || + =+/l(=((²)) E[G
- VF 11 |[[G*+]]]] 111 -
Combine with the inequality
[[F(x*+ + S F(*") - // [(1 LFr) ||[[G~1||| E + Lox gt+
By taking y I 2L. we have that
E[F(x < F(x')
VF(x'))] ||2 ||E|
+ Leg gt+1 var
2 bias
Re-arranging the terms we get the desired inequality.
A consequence of Lemma 3 is the following result.
Lemma (Descent Lemma) Suppose Assumption holds true. By taking ? S 1 we have, 2LF
ET= [IVF(=))
+11 Σ ||E
2(F(m9) + ET-I E(gttl| Lez ΣT-1 ElEtt
where the expectation taken over all randomness from = 0 to T.
We denote the conditional expectation at time in the descent lemma (Lemma 3 as E [-|t] which conditions on all past randomness until time L. Then the descent lemma can be written as
Proof:
El+1 (F( + 14 & F(x')- ||
||E |
|411 + F ( + Lez E (et
2
21

---

If we additionally consider the randomness at time t - 1, and apply E'[ - 1] to both sides
E* [[ Hd|lt 1] <E(FF("
|| It 1]
- Ex || [G+ |0 || + 3 Et
[ (
[8]le 1]
Lي [
|E |
|e|lt - 1].
By the law of iterative expectations, have |
E H 1]
E'(E'*1 [F(x' +1 - 1]] [E'(F(a')
-
1 E' 1 G 11 |+ - 2
|
E
E
s It 1]]
+ 2 [E' [ | - 1]]-
Similarly, we can apply [- [-|t- - 2]. 2
1.1t - 3) .. E2|-11] and finally E
F!... [ [F ||| - [Fx')) []] E [F'[] 1|2]
-E' ... [E'1 | |0]|||1
[4]
+ 3 [ [E biis
L L ... [L' |
Now that both sides of the inequality have no randomness, we can simplify the notation by applying E++1
[E'|-] to both sides and by denoting
E[] = [ H
Then the descent lemma becomes
E[F(=*+)) < E(F(z') - : Fi (z)) - - E [
E
11 + Ei
LP?
Elstt
2
Now sum the descent lemmas from t 0 T -
ELS E[F(x*+))) - E E(F(("))
- [VFF(=')1
3 Σーー E I |1
+ D
El c + LEg2
ElE
After simplification and division by T', we get
+ D E |VF || 1 - E ||| | G
2(E[F( E[F((==)) 11)
E|sttl1
+ 2 T LT [(EN
Le2
71
[[ 11FF)) + + E E E
LE T
-T-1 E(Ett
71
The following corollary is consequence of Proposition ! Corollary Assume fe in CSO satisfies
04 = supsup 1 fe(x))l2 <0, 1= 1,2,344
Let's further assume that the higher order moments of 9.(()) are bounded.
supsupp
(E En
[9)(2)) E,, elon( <0,,
k= 1,4
x
where [)) refers to the i-th coordinate of a vector. Consider the c.0)) 2.
Vee (0) defined in 6 then
[ VSe(O) D
(E
C2 mt
34
where (e( =
(8agoa + 188, ; +5
2
96
22

---

Proof: The Proposition !
gives the following upper bound
E
(2)
(0)
(. -
(1ags 18m
5a4
04
30
D
96
172"
For simplicity, we can relax the upper bound to
c
D
Vf((O)
V (E((Enlel
-
m
Sagga+ 180405 +.aggr 2
96
D.2
Convergence of BSGD
In this section, reanalyze the BSGD algorithm [16 obtain bounds on bias and variance of its gradient estimates. Theorem shows that BSGD achieves an (f sample complexity.
Lemma (Bias and Variance of BSGD) The bias and variance of BSGD are
blas
et+1
S
The m
gtt
out
m
where = + o2 da = Cp, and o = og
Denote G++1 GRSD 5 and denote E.|:] as the conditional expectation [-(] which conditions on all past randomness until time t. Note that the Vin can be estimated without bias, i.e.
Proof:
Ei Vor(a))
Eal (g (x)]]
m
Then let's first look the bias of BSGD
ef+11 bias
/+ - -[G
[ce ((EnslV T
(Vle((Enell, - En (e Ener go
s c0 Eg || [ (Evleeloo IVIe E
EnE In (n(2 1111
< 1 Fe
n (neel, - 1 Enen Io (x.))
G. Fe
[Fmls
|| e (x)) sn(aa)))
a. C 1
m
For the first inequality, take the expectation outside the norm and bound Vgg with Cg- On the other hand, the variance of BSGD can be decomposed into inner variance and outer variance
g++1 Eg(Ente G ([EEmeeeee(
F FF( (G++1 F E G + (I nE.. | Fg(F ( +
EE(Enns.. G EnIs. 111311 EE.. L
[E mls G |
Inner variance
Outer variance
23

---

The inner variance is bounded as follows
EglE, s.mell/
G++ e -
|| Enei Vgg(2') - Enje gyy V En Iy (n((x1))
EE
T || [[aie (v Enett (n(2))) E VV Ener, gy (z(()))))
E
(e
C gg
Eñis
m Enci: (gn( - a Vgr (z+))
0g E
Enle fe Σ En 9n (a²)) E, V Enem In (n((")))
C2 3g
1 Ened: (gn( - E V (z))) |
0g Es
E,
fe Enen 9n (x')) v (E,
C F3
V (Fn,, ml (V fe Ene Iy (1 (z=') }1]
G99
Ene 9r 91(xx)) - E nl (x)") [-]
Cg Eg
En
m
CiS
En
[1))(x²)) - (lan 2112]]
m
The outer variance is independent of the inner batch size and can be bounded by
Ecll [ F5| Ff me [C*+ < E Fl 1 - 070g = C7. = =
Therefore, the variance is bounded as follows
gt++1 var
0 + -au
This completes the proof.
Theorem (BSGD Convergence) Consider the CSO) problem. Suppose Assumptions
3 4 5 holds true. Let step size y S 1/(2F Then for BSGD, x² picked uniformly at random among x T-1
satisfies: F x )1(] E for nonconvex F, the inner batch size m = (a -) and the number of iterations T = Q ((F(x") F*) LF (f + ) -4,, where o² C20 + 0 Lg
d CC, and oi L2.
Proof: Denote G++1 G
Using descent lemma (Lemma 4 and bias variance bounds of
BSGD (Lemma
+ 1 E [F
+ 27 E
(
2(T 1 72'
+ T oh + + + oi
Then we can minimize the right-hand size by optimizing 7 to
2(F((")-F") Ly Lr("//mtoa.
which is smaller than the bound of step size 7 S which does not rely on the target precision
1 if T is greater than the following constant 2F
T > 8L (F(#)))))
24

---

Then the upper bound of gradient becomes
hea
T
By taking inner batch size of least
and iteration greater than we have that
T> 2( ((F("))-F ) FF L
+
E | < 2
By picking æ uniformly random among (ar ft=0
(==) get the desired guarantee.
The resulting sample complexity of BSGD to get to an e-stationary point is (s=
D.3 Convergence of F-BSGD
In this section, we analyze the sample complexity of Algorithm ( (E-BSGD) for the CSO problem.
Lemma (Bias and Variance E-BSGD) The bias and variance of E-BSGD are
bies I Lim.
E+
S 14( o dda))
where on = 2, + C2 02 C2., and o2 bias C2 C2 with C² defined in Corollary i
Proof: Denote G
G1+1
BSSGD Like previously (Lemma 5). let E[:] denote the conditional
expectation E [++] which conditions all past randomness until time t. In E-BSGD, apply
extrapolation fee(-) The bias can be estimated with the help Corollary
VF(x*+1) E|G*+11l1
bias
2
< C2
(e -E
c
fe
D
C.02 m
Since the variance of BSGD in Lemma
is upper bounded by _ + o then Lemma gives
c++1 14(22/m + ton)).
This proves the claimed bounds.
Theorem 3 [E-BSGD Convergence] Consider the CSO problem. Suppose Assumptions 96
3
hold true and Lep Cr, L.r,Cg F are constants and C.(Jig) == 88gdy+18a +5 defined in Corollary I are associated with second order extrapolation in the CSO problem. Let step size y 1/(2Lp). Then the output x of E-BSGD (Algorithm) 2 satisfies: F[ < E for nonconvex F, the inner batch size m (CC.C.C and the number of iterations
Cg.
T ((L F*) (f2 CA-E=
Proof: The proof is very similar Theorem Denote GL+1 (Lemma 4 and bias-variance bounds of E-BSGD (Lemmal
G++1
Using descent lemma
EBSUD
$ ELO [IVF(>))) 11 E. E
|||
IG |t]l
2(E F( pt)
14I r
o2 + 2 +
cao2
7
m
25

---

Then we optimize to
(F(#")-FY (orlo lo om)
which is smaller than the bound of step size S which does not rely on the target precision
1 if T is greater than the following constant 2Lp
(Fx(F(())=F))
T
7(*2/mcooa))
Then the gradient norm has the following upper bound.
+ E VF(x')) - 4v
+
T
In order to reach E-stationary point, i.e.
E VF(x')1 SE
we can enforce
4V
7(F(x") F*) Ho /
S E²,
mi S E
T
By taking inner batch size of least
m = 1(01// -1/2).
biss
and iteration greater than we have that
T 1=2(((=))=F)) +o
+ E F(**)) 3E.
By picking x" uniformly at random among {x" ' Tt=0 we get the desired guarantee.
D.4 Convergence of BSpiderBoost
In this section, we reanalyze the BSpiderBoost algorithm of [66 to obtain bounds on bias and variance of its gradient estimates. Theorem 6 shows that BSpiderBoost achieves an ((=-5) sample complexity.
Let G the BSpiderBoost gradient estimate
BSB BSB + 1 Eces, GG BSGD) with prob. 1 1 Pout Bi EeEB, GBSGD
G&al
with prob. Pout
Ba }. then the bias and vari- Lemma' 7 (Bias and Variance of BSpiderBoost) If < minf 2h GLF ance of BSpiderBoost are
+ -T- [[gtt]] < 20 (I-Pa)) 56
Ein E [0ll + (Ipp + 11111 paal1-pan pmn) 1
o
+ )
Ba
T
B,
m
+ -TD L(Ett < 28(1-pm)) Lin
2
T-
Elll (G + ( + Pou)) 2 o2 +Zu))
T
where oh = 2,09 + o 02 aon = C.., and oz = I.
Like previously (Lemma 5) let E[-] denote the conditional expectation [ which conditions all past randomness until time t. Denote G++ and G as the large batch and small batch in BSpiderBoost separately, i.e.,
Proof: Denote G++I G
BSB
[-[t]
G++L EeeB, G++1 G 1+
with prob. Pout with prob. Pout
B
ΣeeB, (G GBsGn)
B3
26

---

The bias of BSpiderBoost can be decomposed to its distance to BSGD and the distance from BSGD the full gradient, i.e.,
ct+11 bias
VF(x 11
2 (ax (11) - [C
[|[
F[G++)]l2
(14)
20 m
+ 2 G E|G
where the last inequality uses the bias of BSGD from Lemma as follows
Then the second term can be bounded
IE B
E[G++ = - Pout
||
- E [E
Pout 2
||
G [|
By taking the expectation of randomness of G
[ E[G* '11 (1 Poun)
(|E[GGsco E|G*|l12 + EEI| -[G")]))))))
(1 Pomn2 [E[Gas
E|G* + E
1| = 0 as the first iteration always chooses the large batch. Then as we always use large batch at 0 we know that
Note that ||E[G
E E.G S [1-Pou) 1 T Σt=
et-1
(15)
t=
Therefore combine
14 and 15
upper bound the bias
gt++1 bias
2eni m
2(1 Port 12 1 ET-1
&var
(16)
Pon
Variance. Now we consider the variance,
ge+1 var
= |||GH11 E|G [1[]]
I (1 - )Pou)
E || - EIG's 11[2]] + Pour |G
E[G 11 2
(1-pan) Danl
B2
E
||| G
BSGD
GESSDD
E|G
CBscDlll2
+ Bi
E ||o
E(G
BSGD
1
E
BSGD
GRISDD
B|G
Ghicall
?
+ B,
c + oin)
(17)
where the last equality is because the large batch in BSpiderBoost is similar to BSGD.
E =E E E E [[[]] [[GLIl 3, E [|CCssD E[G
< 1 +o
(18)
Finally, we expand the variance at small batch size epoch
E BSGD
GRSCDD
E|Ghtt GBsCD
[1
E BSSD
BSGD
GBSGD
F Eng.. C
G C
Inner variance Ti
Eg [|Emeleeee((At
G
BSGD
G 1|
Outer variance Tor
27

---

The outer variance Tour can be upper bounded as
Tom F5 (i (BEED [Bscooll2]
[| ([ F Ve EnEHs (an]) (e (x())) F Fl V EnEHe
=F&
s L2 ((( DD)" T Enge [V EH I (n(2())1] [
+2 ||( Van
Vanla E EmER, mn(xx)) - (. En An(ott1))] 1))
$2L,09 || - - 122 20 |0'-=""'11
=2L || -x'-111 112
= - 2|
The inner variance can be bounded by
[| m Enene (Vgn(x²)) - Vog(x'-1)) - -Ejlel [gn(=') - ()) Σn meg 9n((x"))
27
Im S 4E
+ 4E
VV - Vos(at=1)) T (V m Enen - [ ( Ener, In
+ 4
( LnEfe Vo)( V E nE (z(x")) - ( E.HEE, In (x((x-1))
E
fe ( Ene "n(2²)) fe + En ( (2) (-
[ [ Ejetie Vgg(x - La V gh xx' 1)) fe H. ΣnEne In (xx))) - (e Σn In sn(xt111)) [
4
403 E [gg("a) - Vog(==-1)~ - -Eile ( - (Z |||2] + 41z03 || || - x²-111
# E
(e Ener, ,y((")) - VSE( EnEtt 1)(
- E 1 m E 9n(2²)) - V.fcH V EnEH, (y(
|
x
Then we have that
c2 Ti S
| - 1|2
42307 - 1
m
m
+ +42
V fg ( E ne (,())))) (e Enen, (1)) - (V - (at
+ 4C
(o
V E EnEn (2xt-11)) 22
- m EnE H1 (z(1)))
-
|00"
x
C
100"
x²
SC m
|0" x
|
1 m
x² - 1 2
m
2
2
12L
112
2
||G912 2
28

---

To sum up, the variance is bounded by
gt+1
2
Peul 2
(1 + m
| 12 +
Du
ci
+ )un)
Ba
Bi
m
<
14/1 fall-Paall Pru) 3
||o²13 11 +
Bur
Cit + )u))
B2
Bi
14(1 pur)
['[|[" || |
11 + Bi c. + o cam)
B2
Then averaging over time and now we redefine E[:] E ...[[EI-I]
# Eo [( < 14(1- ?
E||| [[||G++] [2] + S + Ruse m
o
B2
i=u
14(1
Pm.)
2
T ( + E||| [0]] + Eig + B,
Pes ( ( + o
B2
T
1=
If we take
7 1
2 GhF
then
14(1-Pall
1.2
< z. therefore
Ba
1
T-1 E|ET
28(1
D
Pan
Σ
T-1
|0ll +
Eyr
2
( oh
+ )um))
T 1==
B3
t=0
T
B1
m
28(1
Σ [ |4]
|1 + (
Poun )
B2
B3
m
Then with (16),
we can bound the bias by
+ Ei=
F
1
S
2 m
(1-Pan)² 13t
56
Ei
E| 1111 ( (Them + 1) 1(1 -pm))
2
)aa)
Pas B2
B1
Theorem 7 (BSpiderBoost Convergence) Consider the (SO)) problem. Suppose Assump- tions 3 5 holds true. Let step size & S. 1/(13Lp). Then for BSpiderBoost, x² picked uni- formly at random among (1=) satisfies: E[IV (x*)) S E nonconvex F, if the in- ner batch size m = Mo e the hyperparameters of the outer loop of BSpiderBoost are
B, = (f + oem)e=
B2 = O OE--)), Pon = =1/B2, and the number of iterations )-m))-)) where o 2209 9 Lg o Cg, and bias = og.
T T= (LF((F(
Proof: Denote G CBB 8
Using descent lemma (Lemma and bias- Variinae bounds of
BSpiderBoost (Lemma|)
D E
+
E|||
+ (1
27
2( 2(F(z²) F*)
I LF T Ei= (
7 Ei= F(ghtt))
Yf
)1 F*) + LF7 T Σ 1t=0 E
20 + 2
T En E(
Par
2(F(=")-1 F*)
+ 201
+
3 Σí E(
YT
m
Pun
where the last inequality use y I 2LF
Use the variance estimation of G+1 and choose B2Pout = 1
+ ETD EIIVE((*))
Eto Eill E||
(01l
27
< 77'
2(F(=")-F") F²)
20 8
2
1
T ETD E|||E'G** 11]l2] + (Tpe
+ 1) 6 (
+ oou))
Bi
Now can let S 13 such that 84T.272 S }
1 ETD EIIVFF(>)11 < 2(F(x) 1= F*) yT
20 + (T + 1) 6.
(
+ oam).
By
m
In order for the right- hand side to be =2, the inner batch size
2
and the outer batch size
B
Tn m Fan
B2 = BB. Pou
1
B3
The step size is upper bounded by min ( we need iteration T greater than
BB
}. As B₂ 2 1, we can take y 132,
1 So
2L
6LF 13LF
T> 26L (FL((F()
=²
By picking x uniformly at random among {x 1-11
we get the desired guarantee.
The resulting sample complexity of BSpiderBoost to get to e-stationary point is (c-
29

---

D.5
Convergence of E-BSpiderBoost
In this section, we analyze the sample complexity of Algorithm (E-BSpiderBoost) for the CSO problem.
Lemma (Bias and Variance of E-BSpiderBoost) The bias and variance of E-BSpiderBoost are
T D-'1 F 1
28(1
28(1-Pac)Liy
T-1
E|| 14112] + (Tp... +
28paar
Ba
T t=
B1
Et= [ ( v
28
(1 (1-Bw))
Et E( J
Pos
where oi. == 22 + o C2 13. Oon Cp, and Bius
C2 with C2 defined in Corollary
Proof:
Denote G
G
9 Like previously (Lemma let E[-] denote the conditional
expectation [1] which conditions on all past randomness until time Let G G++1 be the E-BSpiderBoost update. We expand the bias as follows
gi+l = /|VF((**)) - E|G 11
hias
S VF - E[G 1121 + || E|G*+1|||
From Lemma 6 we know that
V FV + E 11 oa
The distance between E[GL+1
E-BSOD and E[G++1] be bounded follows.
[[| E-BSGD
E[G++1]] (1 Poun)
EBsGal) (G* E|G G BsGDl)
(1 Pout) [[E - G²1l
Taking expectation with respect to G
E-Bsal E[G*+1 1/2 (1 Poul )ou)) { - E[G']|
|| E
where
[E[G
E[G') O. By averaging over time we have
E B E|G*+111
S
(1-Pae)²
Σ E E
Peu
Then the bias is bounded by
E[ 1
252
2 (1 (1- Bunl
E T-1
ElEt+1).
Puu
Variance. Since the extrapolation only gives constant overhead given Lemma 2
+ IT= L [ L' E ||]]]
28(1 1 ETD E|
[t] [ + ( + Pour)
28 on
(
BSB
B,
Then the variance is bounded
IT- El
28(1 par)
ET-
E|| + + (Tr...
1)
28p
+ o 2
B2
Par
B1 m2
Theorem 4 [E- JE-BSpiderBoost Convergence] Consider the (CSO) problem under the same assump-
tions Theorem Let step size
? 1/((1)))) Then the output x² of BE-BSpiderBoos/ (Algorithm
satisfies: E[][ x: )13] < e2, for nonconvex F, if the inner batch size m OCC.Cye 0.0
the hyperparameters of the outer loop of E- B-BSpiderBoost B (Iz/m + C+)== 2, Bg =
/ BB, Pow 1/ B2, and the number of iterations
T ((F((F(2)) -F*)=-?).
30

---

Proof: Denote G*+
G++1
BSB
9
Using descent lemma (Lemma and bias-variance bounds of
E-BSpiderBoost (Lemma
EL E
Et=
El|
EI|
[
2(F(=")-F") LF Σ -
72
+
Σt=
hias
2(F(a))- F*)
+ LF E
1|
26
2 T
ET-
E
0=
((F(w=)
F*)
20 m
Σi
+
72
Bun
where the last inequality use
7 S
Use the variance estimation of G and choose BaPont
2LF
T- EIIV E 1==
E E |+]l(]]
2T
2(F( 78
SAL
E 1 E||| 10]1 + (Tree 1)
G + o
Now can let y
such that 7 S
132
D ElIVF(>> N 2(F(m))-r) r*)
72' +
28
(Tpm
1 Puu.
+ 1)
84
+ o oar))
(19)
B1
In order to make the right-hand side 2² the inner batch size
Mo 0.5),
and the outer batch size
B
(ch/m+touu)
B2 = VBI, B1,
Poul B2
The step size is upper bounded by min we need iteration T greater than
1.
GLF 13LF }. As B2 2 1, we can take y 13LF So
BB
(FL((F()
T>
52
By picking x" uniformly at random among {x" TT we get the desired guarantee.
E Stationary Point Convergence Proofs from Section (FCCO)
In this section, we provide the convergence proofs for the FCCO problem. We start by analyzing a variant of BSpiderBoost (Algorithm 3 for this case in Appendix E. In Appendix E.2 we present multi-level variance reduction approach (called NestedVR) that applies variance reduction in both outer (over the random variable i) and inner (over the random variable 77) i) loops. In Appendix (E.3 we analyze E- E-NestedVR. As in the case of CSO analyses, our proofs go via bounds on bias and variance terms of these algorithms.
E.1 E-BSpiderBoost for FCCO problem
Theorem Consider the (CCO) problem. Suppose Assumptions 3 holds true. Let step size O(1/LF) Then the output of E- E-BSpiderBoost (Algorithm) satisfies: Elll ([II < for nonconvex F, if the inner batch size m = 12(max(C,C, 1/2 - =)=))), the hyperparameters of the outer loop of E- B-BSpiderBoost B = n, B, = Vn. Pour = =1/By, F*)e=2) The resulting sample complexity
B2, and the number of iterations
= Ω
o (LF(F(x))) FF) -F)
J.C. 22
}).
Vne
Remark 9 The sample complexity depends the relation between and
When n = O(1), we have complexity of Og--A) This happens because we did not apply variance reduction for the inner loop.
31

---

When = ( 2/3), E- E-BSpiderBoost has same performance as MSVR-V2 19 of O(ne = 11-1))
When ( (..).)). E-BSpiderBoost achieves better sample complexity of ((2-3.25) than O 4.5) from MSVR-V2 [19].
When = ( )), recover O O(e-3.5 sample complexity in Theorem
Denote G++1 outer loop of the 4S00per we only need to change the (17) and (88 to reflect that the outer
Proof:
F.
D As are using the finite-sum variant of SpiderBoost for the
variance is 0 now instead of da B1
the general
CSO case. More concretely, we update (17 to
Ex = ||| G+
E|
- (1 Paul
[ G
E[G
Pou
E[|| E
(1-paa)
E| & || + B, El G
E 112
B2
BSBGD
C-BSGD
B2
El|
G
E-BSGD
BE
E
B 2
Peu em B1 m
(20)
and change (88
E E[|| -
-
E[|[] -
E[C*)]]]
E[GLIl - El| G E-BSGD
ElG Easalll
S
Bi an
(21)
Then our analysis only has to start from the updated version of (T9)
+ O E[IVF(="')I) s 2(F(=))-F)
28
+
1) Bi
77
T'p
We would like all terms on the right-hand side to be bounded by 2?. From
25 m
S g2 know that
1/2 Nic
12
From
+ 1)
on Bi
S e2, we know that
Tpea
m S2
L. ne
From
2(F(*)) 72
< s², we can choose that
7= ( T= [
Now the total sample complexity for E-BSpiderBoost for the FCCO
problem becomes
BymT =0 (2((T())) F*)
max
Vne
By picking x uniformly random among {x (
1 we get the desired guarantee.
E.2
Convergence of Ve
NR Algorithm. We start by describing the NestedVR construction. We maintain states (+11 and 2 ++1 to approximate
y 1+1 (nj1(9n()))),
2/+1 Mlr (V)((a"))
In iteration /. + 1, if is selected, then the state y! is updated as follows
EnEh, 9n(xx))
with prob. Pin with prob. 1 - Pin
y ++1
[y) 55 ΣnEH, (gn (x+') (n,())
32

---

where of is the last time node is visited. If is not selected, then
y ++1 y
In this case, y + never used to compute use the following quantities
ff(( because is not selected at the time t 1.
z++1 = (zn)),
++1 1 Lije. Vgn(2*).
(22)
We use GNVR as the actual updates,
B. Eieo, (z ( GKv + B2 (EE8(((F
with prob. Pout
G++1 NNR
(2)
with prob. 1 Pout-
We can also the following quantity NVR auxiliary
L Eies, (2 V )
with prob. Pour with prob. 1 - Pout
G++1
B. GAvR + B. Eies, ((2, VV - TV((((
Here use 5 to represent i.idd copy of y where is selected at time t. The iterate x1+ is therefore updated
x=+11 = x' -7GNVR
Lemma The error between NVR and NVR can be upper bounded follows
+ C
12 O7o NNRR 2 Bi
S
+
4[1-Pau)
T Et- -[IIG++-G.1]3
Proof: In this proof, we ignore the subscript in GNVR and GNVR: bound the error between G and associated (++11 where
G = ( G = V9 (=))) ( V
Let's only consider the expectation over the randomness of Vga.
Eg,
||
G
2
S Eai
th EnEn,
Vgy(x)) Eng [z [tll/
Si Enji
[[V [
c7a
m
Then can bound the error follows
En. ||
-
G
Pau Bi
EH. || - Ge+1
27
2
[2
+ (1 - Powi) (1(0- Ge
| G -G,t1 6:!((])
+
En.
B2
Pau C9a²
-Pou) |
101
+ (1 Poul)
B1
2
[E ||G - G G/ -
B2m
Pas
C9o² 2
+ (1 Pou)
G² Oe 0012
(1-par Puu) Bgm
(EIlIG G (2)
B1
m
Unroll the recursion gives
+ -ΣT
e
|
27
<
Bi
1 Cia
+
4/1 ΣT=
Bampon
T
Ei||Gh+1 13
33

---

Lemma 10 (Staleness) Define the staleness of iterates at time t as =² let G++1 be the gradient estimate, then
Σ}= |
03112 and
+ E
Gn 2 E B
E[|| E[||
(23)
Proof:
Like previously (Lemma let [.) denote the expectation conditioned on all previous
randomness until f It is clear that 0, so we only consider t > 0. We upper bound E|="] as follows.
L| (1 Pout Σ El| xt ا51l
Pout ΣEIl El| 03
if time ttakes B2
time takes Bi (06)=z
Then expand [ as follows
Pout
El 05112 +
Pout
El x' 11-
n
1=1
==1
Pout
(1 + FF [-=1|==-111- F=
33 + (1 + 33 1|x
x. x2(1()) + Pouly F
==1
(1
- -10)) El| G*
where we use Cauchy-Schwand inequality with coefficient | > O. By the definition of Ø)..
B2
B2 | x 21-1 +(1+ El {
EE1 S E(1
(1+ 1)
-
11- +
= (1 + )1 E' + (1 + 2 F|| 1
By taking 8 = 2n/ B2, we have that (1 )1
B2)
S
1
B2 2n
and thus
[ S (1
L
G
11
2n
Note that [[3*] = 0.
+ EΣー E|3]
(1+
)
E[| G +
Gn
E||
B
The following lemma describes how the inner variable changes inside the variance.
be the error from inner variance and Lemma 11 Denote g++1 == E [|I/ En (=")]
DoutT T S 1. Then
ETD ex+1 <
(1-p)C PhiS2
ET-
20a
T
Meanwhile, E = El - En):(1((2")11 31
Proof:
1143 < Pin o²
+ (1 pin) E, |E Enilan
+ 1 1-pa E. (x²') - (o( (01
$ (11 - Pm E + (1- [1-pa E.[E.]:l| - $511331 + Pm 5
S2
34

---

-
As t = 0 always uses the large batch, Eg = [E Filly! - En (x1(0n(00)11
Then
+ +
(1 (1-Ba)
pn
T -===
=0=
1--1
E:(En|elllet oil:11
St
PsT
+
E' +
202.
Pn
1==
B1
Lemma 12 The error Ei(E [E [lle - 5 ||1] satisfies
+ E p. 1 m/ 011|ا.11 S 2 Σ El||
2
+
4(1 4(1-p.)02
S2
T
-T-1 10+1
g++1
+ 6(1 6(1-pa)
Σ/= Egt!.
T
Note that when Pin = and S = S2 = m, we recover the following
+ E E,
T-1
pE [E o 1|, أt 111111 = -==1 [E
m1 En "n(2x)) 0,((a'1))
p..
1 10 T-1 E|||@*+1| 123
Proof: For t 2 2. pE EE, [| y +1 - 3 ||21| can be upper bounded as follows
(F Mo (F (Fmillll ++1 - 5/ 201] = Pin F3& Mf ||
उ.. EmEn, (0)((²) - (ry(a=-)) 11) 27 22
+ (1 - Pin) Ei En
+ 1/2 -t
Ln (9)((²)) ()( - (2) In (o!
S Og || - -0"-1
1/2 + 82
Ei [E [|(99n (x') - ()()))) - (0) 0,(0k-1))1
+ +3(1- - -Pm))
(E: [ll| - 1 ( [|]] + E [| 1-1 - (0) (ot-)))))) 2 + c/ ||a2 -
-x--1= x--111 112)
S <pin 110' x0-11 112 2(1-
(E' (-'+E-1)) + 3(1 pin) (E) + Ey C/ o0' x²' -112)
S2
$ (Pmn + 3(1 - Pin) Pim))( 02 g || ---=x"" x 11- + 20
( + - + 3(1 - pm)) (E) + g
S2
Fort = 1, we choose 8! = =
E pu [ 7. 1111111 = Pm E, Enje
1
Σ EnEr, (0n(((²)) - 9, (2)(a)))) [|]]
+ (1 - Pin) Es Enli
|
1 32
EnEh, (gn( - g2()))) -8/
S C || x 2=112.
Then for summing up t to T -
Σ E pm. [F 1 y
1+1
Øf |ل1ا0 + E. [F (E [E 3r // |1210
02 3 Dو= ||a. - x:' -11 + 2(1-pn) (E + EE'
S (pin + 3(1 - pm)
52
+ +3 - Pmn) EE= Eg + ΣT= et-1) ) + 09 x - =0012
S <40 3 ΣT=1 x x111 1|2 + 4(1 P.) # ΣT- g+ 6(1 pmn) Σ - - g++l.
Σt= cy
S²
Finally, the error has the following upper bound
T -= (,E,,. (E.::./E///l/ee of - 인ी 1111
1 TT-
< 10222 2 E E||| ||31 101-p
- Eth + (سماا Dd- c g+tl
+
Sz
35

---

Lemma 13 (Bias and Variance of NestedVR) If the step size 7 satisfies.
L max
(1-pa) 18
1 1-poor
(1-pu)
18n²
(1-Par)
1 1
B2²
f2
Pa52
B9
B2
then the variance and bias of NestedVR are
+ Σー gt+1 S 32
Run Bi
+
18n²
+
22
D
[[G++1]|
2
Bg
P4
B2
B2
T
+ 96
Post
+
(1 Pmi
Pmnl Pare
1.3
+ (1-Baw)
B1
B2
31
7
B1
T 00
gt+1 bias
<
12(1 pad ? L2ng2
Piesa
B3
1
2010 ||[|++1|122
+
123
+ (2()) n²
Lig? + 2(1=Pan)²)
)
T Et= gt+1
1
B3
Proof: Notations. Let us define the following terms,
G (V
: V((()))
Note that the &¹ computed at time i. + 1 has same expectation as G
E - [ = E' l|.
(24)
Computing the bias. First consider the two cases in the outer loop
VF((=' - E+ [G
bias
< 2 VF(x') - E |G +2 E G [) E G [t|
A2
We expand A7"
follows
Ah+1
L |G 14- - [0]1
16]2
L' [G [1] Pou E E++1 |G (1 -G + E++
(1 pom) )
--- - E E+
Pow! )3 - E'IG 111|
where we use 24 in the last equality. Now we take expectation with respect to randomness at & such that Go is a random variable, then
12t1 (1 Pow) 2
|||'- - - -1]| [t-1]] -1] [/ -11112 -[]/--1]]3
(1 Pout )2
EV
(1 Powt (A2 E
while at initialization we always use large batch
1 [G E' [G -E
E 0.
Therefore, when we average over time
T Σ A5+1 < (L-pw)²
1 T ΣTO gt+]
(25)
Pio
On the other hand, let us consider the upper bound on Ap+1
Att1 s C9L3 E| - Eniilg, (x 111 C217,,t1
From Lemma D we know that
$ + Aft S C3
(1-pw)(2 ET- ' +
20
pr.
St
s (-اm)L ST--E g +
214 3
P=3
T
36

---

From Lemma 10 we know that
E Aft
(1-pa)ti
Gn
21
T T E|I + 2
Sn
B2
7
St
6(1 6(1-pm)
n² L
||| + 263
+ 6(1-pa) n² Li
Et=0
gt+1
Sa
B3
81
Ra Bi
T
Therefore, the bias has the following bound
D gt+1
hias
_
12(1-Pu) n² L P2
B3
Dtz || ||]H++] 11 +
1L2
31
(26)
(12() (2((1-pa) n² L2 + 2(1 2Pa-)
+
El=
gt+]
82 B3
Pun
Note that when Pin and S S2 m, then this bias recovers BSpiderBoost in (16
T-1 ci+1 biss
4b3 m
2(1-p
T-
2t=
I
+
var
Pun
Computing the variance. Let us decompose the variance into parts:
Et+1
E
|| +1G+
E
Gttl + G++1
EnliG
E; EE 2
E
|
Ge+1
2 [
E
|nj
- Ei [i[Enne mle II+
+ + -
| [G++ 1112
2
c1++1
ct+1
where varout and Et+1 are the variance of outer loop and inner loop.
Inner Variance. For t 2 1, we expand the inner variance
gt+1 varinn
= Pour E
| (V)))=)))))
(V) E +1
+ - (1-pe F
1 B3 E (9 - F)
|9
69]
(27)
Pou 2
B. L ( - En
f( |||
+
Bun B2
II
Enle
G
G
< Pur CC L2
+
1- E, Epm
B2
Enji
c++1 - 6
2
We bound the outer variance as
E,
Epa
= E;
Epn
G + (o ///i 6
< 2 IC;
[ppn
||
(E
+ 2E,
Epp
Enli
{) 6
< 22 |r
x²' 112 + =20 7.7 F2 m.
[F
1
(28)
For t = 0, as we only use large and small batch in the
|| -
E = E
< 02 V((
[. |||
< ,) 1C
(29)
< Bi L
Al7
BLST
37

---

Therefore, average over time t = 0,... T 1 gives
+ - Evarii S E. 1C T- E/t + B2 2im1 E, En c
L-nut
|ل11| 4
Sigu
Em Enje ||0 0: [1] + (1 Pon 1
BC Σ 1=0 Ey
1-asa
El= Es
Ba
s
pm
121
Σr-
E/1
11- Purn
B1
9
T
1
T
|000 x² x-1111 + Er
R2
2(=1
S Pou 4C 2
12
T-1 ge+l y
(1 (1-pae)
B1
9 T
T
2( 31--aal Paa)
T-1
E||| 12
21=
B2
2( Ponl
C 1
Di=l
E, En M - 1:1:111 2111
13
Let us first apply Lemma
12
1 IT-1 Eyathn
I
Ron
ge+l + oy
(1 (1-Am]E
+
2(1- 03
Ei= El| 1|
T
Bi
1=0
T
B2
T
2(1
Pan) 12
/10222
- El||
[|2] + 1(1-pa)
-T- E + سسداا
Ltn ext2)
B2
82
Bon B1
Pn Rum!
12C
g T
Σ
T
+
8(1
1 T
ET T-1 E||| |
B2
t=
y
B2
+
8(1 Pan (1- Pia JC
T --1
E +
(1 (1-Pa)
1=
T
Then we apply Lemma
11 on the bound of T
g1+1
-1=0
y
+
E
T-1
gt+l
S 24
Bue B1
+ (1-Ph) PPn)
-T-EE'+
E' 12
B2
Sa
T
St
+
8(1 8(1-Pw)) LL 333
G+++|
||
B2
T
(=0
2
8(1 Pan Pan) (1 (1-Pa) Pa
T-1 =
(1
Pon )
E1=0
Σ 24
Pas
+
(1 Pio (11 -Pan)
pull Poon
Pon)
(L-Pn) 1
Pn T 1T=
B3
B2
+
8(1 (1--an))e M.3g7
TT-1
[[|
|
[|
Ba
T
+ 24
Post
+
(1 (1-pa)(1 (1 )ras)
133
81 +
(1 (1-Pan)
B1
13
T
S 24
Pas
+
I-Pae
(1 L.
-1 =
B.
B2
Pa.92
T
+ 8(1 Pun)
T-1
E|
G ||2]
B2
T 7
+ 24 Patl + (1-pa) [1 -
L
[1 [1-puu) e1
B₂
St
+
var.in
From Lemma 10 we plug in the upper bound of $ DT-1-
=²
$
T
s 24
Pus
1 1-paa
B2
(I-pa) Pn.S2
Gn² 21
B
?
T
ETD G++1 (2)
8(1 Bun ). 3
Ei=o T-
E||l G++ ||
B2
+ 24
Post Bi
+ (1-Pha(1 Pus!
+
(I-Peu) c T
B2
St
$ 8
((
Pou 1i
+
1-pust
Pust
(1-pa) 18n²
(1 (I-pmn)
?21B
ET 1|
Sa
B3
A2
T
+ 24
Post
B,
+ (1- (1-pp) Ppee)
B2
L3
St
+
(1 (1-pmn) el
T evarin
Finally, we add the upper bound on with E1
varinn with 29
T Er Et
((
Puue B,
+
1-Pon: Bz
(1-pa)
18n²
+ (--Po))
2 T
ΣT-1 E|||
[
Sn
13
Ba
(30)
+ 24
Run
p1 Poee)
La
+
4L2
Bi
B2
B1
T
B,
38

---

Outer Variance. Now we consider the outer variance for 2 1
varrout
(1-paa)
E
(Gt - E [G 2
Ba
c 07 2
(1 Poaz
Ei
Enjk
B2
Compared to 27 we know that the upper bound of is smaller than that of gt+ Besides, whereas varin"
E3
0 use large batch t 0. Therefore, the upper bound of g is upper bounded by
2*0
Variance of Vgn- From Lemma
we know that
+ E E|
1 $
G7
1(1-Baul 1 T-1 [E|loctt
-
B1
Bampon T
c702
1 gl+1
Finally, we use [|||
||E|G++|||| 1|
- gt+1 s 16
((
Pun Bi
+
1-Pat
Pha)
18n
Ponl
Ei=0
||(
B2
Pn
B3
B2
+ 16
((
Duss
Dunt
[1-pu)
18x
+
(1-Pou)
22
Σn=
gt+1
Pb
Bo
PanS22
Ba
T
+ 48
Peu
+
(1-pal(1-Aaa Pea)
+
(1-pan)
paa)
B1
B2
Si
T
81
By taking step size y satisfy
y L3 max
Bun (1-Pu)) 18n.
1-pou
(1-Pia)
18n
(1-Pea)
1
B1 Pa
B3
Bg
Pa
B3
B2
16
which can be simplified to Then the coefficient of T Ex1 ct+1 is bounded by 1
2 max
[1-pul 18
1 Post
18n2 13
(1-pee)
< To
Pa.2
B2
Pas
16
1-
18n B
[1 (1-pae)
2 S
B3
Sa
132
The the variance has the following bound
EED ct+1
< 32
Pun Bi
+
1-Pest B2
(1 (1-Pa)
Pn
18n²
13
2
+
(1 (1-Pma)
B2
2
T
Σ
[
+ 96
Pun
+
Pa P1 (Pa)
122
Ponl
8
152
S1
T
B,
Theorem 10 Consider the (FCCO) problem. Suppose Assumptions 3 4
holds true. Let step T-I
size 7 = 0 ((LbL))) Then for NestedVR. x² picked uniformly at random among {T
satisfies: El[[ (x)))
52, for nonconvex F, if the hyperparameters of the inner loop S = -[i 2), S2 = (T.ppe Pm (11/22), the hyperparameters of the outer loop
B, n, B2 Vt. Pour 1/B2, and the number of iterations
(Fbp(F(2")-FF FF
T Ω
The resulting sample complexity is
o 0
(nLoLo(r(a))FT
In fact, it reaches this sample complexity for all
PaPaa VI-pa
S
39

---

Proof: Using descent lemma (Lemma and bias- bounds of VestedVR (Lemma 13
11
Ei=
||[ 11
7
27
-[F("")-F"
Lea T-1
et+1
+ T Ei= gt+1 bins
77
T
var
2 F(x")) 1 F*)
4
12
n² -
Di ||
78
Si
Pa
B2 T
To
T2
12(1 ((11-pu) puo n²
Li?
2
2(1 2(1-Por))
LLFF)
I 2 Eh+
Pn
Pon
Compute To. In order to let To I =?, require that
YT 2
(31)
Compute Ti. In order to let Ti to be smaller than e², we need
81 = aig
Compute Tz. In order let the coefficient of + EE ||[[
in To be less than 2 i.e.
n² L
Li 1'
(32)
Pn B3
which requires y
S
Bav
PonPaLy TeLpvI-Pa
(33)
FLenvl1Pp
Compute Tg. Let now focus on Ts and notice that the middle term
2 X(n-
Pea
2(1-Pon)² 1 T gt+1
T
Using Lemma 13 have that
2(1 -Pa)2²
T-1 ct++1
Pou:
evar
< 32 2(1 puel? ?
Pau Bi
1-pree Pice
(1 Pio)
18n
+ (1-pue)
Prse)
2/ Ei=
|| |[
Ba
So
B3
Ba
T3.1
+ 96
2(1 262 -Bu)²²
Peu Bi
+ (1 P1-paa(11 (1-Pan))
2(1 2(1-Pon))
(1-par) 8.2 T
Pis
B2
Si
Puu
B1S1
T3.2
T5.3
Compute Ta.3: As we already know that S1 = ((=-2) and T 2 1 and Bi 2 1. This imposes no more constraints, i.c.
1 g2
S - 0
Compute Ta.:: As S (s=-2) and B and B2
Pi then it requires
[1
n.
Compute Ta.1: In order to satisfy the following
32 2(1 (p-))
((
Pont B1
1 1-paa
(1-ph) 18p
+
(1 (1-pau)
2 - T2 B3
Prss
Pn82
B3
we need to enforce
PanPout LF
5 b (1
(34)
Pmn) 1/2 Peul 13/2
40

---

Now we back to T3 and compare the other two coefficients
12(1-Pu1 n² +
1.2
2(1-Pta)
7.p
Pn B3
Pon
As Thy S 2 pm)) can safely ignore 7Ip On the other hand, from 32 know that the first term is also have
Peu
12(1-Pa) n²
1 S 115
2(1-Pon)²
Pa B3
Constraints from the Vias-Variance Lemma (Lemma 13 By setting B1 and S O this constraint translates
T max
(1-pu) Pin
1 1-Pou
(1 pia
(1-Pur)
Pur!
S
B2
B2
Pin
Piae"
13
which is weaker than 33
Summary on the Limit on 7,. Combine sizer y
(33 and (44 and S 2L.
1
we have final limit on step
S min
Pus Lr
(355
sLevI-Pa Lp
Then the total sample complexity of NestedVR can be computed as (# of iters T) x (Avg. outer batch size BN = B1Pou) (Avg. inner batch size S2 S1Pm)
This sample complexity has the following requirement
BaS,T (282(TT)
B2S2 E2ry
nE-
7
The lower bound 3
n is reached when (35
we have
PopaLE ELVII-P
Lt
That is, PunPia VI-Pu S E.
In particular, we can choose the following hyperparameters to reach O(ne 33 sample complexity
Bi n, B2 nT,
Pour = t
Si - 3), S2 O(LFE Pin O(L7'e)
The step size y can be chosen as
7 VaLo
and the iteration complexity
T=Ω (((
Putting these together gives the claimed sample complexity bound. By picking x uniformly random among {x+)T=) T-
Jt=0 we get the desired guarantee.
E.3
Convergence of E-NestedVR
In this section, we analyze the sample complexity of Algorithm I problem with
(E-NesteVVR) for the FCCO
1 B. Ex (2 (2) (f((0) D441 yi
with prob. Pout
GL+1 GENVR
GENVR + Br Σ. (2 D.+.
Vf.(0) (x))T=)) V&((0)
with prob. - Pout
(36)
41

---

Lemma 14 (Bias and Variance of E-NesteeVRR If the step size 7 satisfies
22 max
[1-Pa]
18
1 1-Pau
(1-Pa)
18n²
[1 (1-Pes)
1
Pm.92
B2
Pa
B2
B2
16
then the variance and bias of E-NestedVR are
E
T-1
var
S 14 32
B1
+
1 1-Bout
B2
(1-pu)
Sn
18n²
B2
+ (1 (1-par)
B2
2/
El
|E|]*+1]]]
1|
+ 14 96
(1
Pa Parl
Li
Den)
8L
B3
81
B1
Et=0
et+1 bias
(1 P.. E.p 6n
Sa
B2
7
Et=
T-1
|||| +1G++1111
112
+
2(1
p L
81
C²
S
+
pa )
Gn
(1-Por)*
=1=
T
Evar
SaSa
B2
Poi
Note that this proof is very similar NestedVR highlight the differences. Let G++1 = =G GENR (36) be the E-NestedVR update and define
Proof:
Gf+1
G )T T (22)
((())
We expand the bias by inserting pi. n/t [G
et-1 bias = | (2 (1) - L[G++1]] ||
2 VF(x+t)) Eip (. [G 1112+ +2 pi G EEI 111
Aft1
Consider Aft1 The term A captures the difference between full gradient and extrapolated gradient
A
E, EEi (gg((()))) (E(((,)())))) Epnooois
(En)
((2)
(
27
< CC E,
V V.i(EE (x'))) Epa.nts
< (oi
< 20 F
(F (x))))))))
Ep.. (V (B. 1211
=:Aif
+ 20 E
Epm (F Eppindi
c ppu f((
The first term A can be upper bounded through smoothness of fç, for t 2 1
1 F; [|V
Pm V..
(1 Pin) Vi. (x)))))()))) 9y (b(())))
(1 pmm) L; ([[ Vi + Enjilln, 9o (x))
< (1 pm.) 2 E [E (xx)) ") (vf + E,)),,, 9r -=)
(1 Pma) 2 Eallls/ - E. E, (l,
(1 pmn) 2 e.
Fort = 0, A = 0, then
ITO Att < LL,C0 ET- gtt1.
(37)
42

---

On the other hand, with Lemma 6
A
Pin Ei
V.i(En -Ele ( v11(0)]
(1 (1-Pinl Pin) Ei
Viily! - -g((()))) (10( -Eyls
[ vi((
Ca
(1-pa]C2
51
82
where D
y.S. is the distribution of s, Enes, 9n(x²) and D s. is the distribution of
y + 55 EEnss (l))(
Thus the Af has the following upper bound
T ET= Att S (1 Pm)) ET Ey s
(38)
Consider 12t1. Let us expand
+++1 through recursion A
A511 El | E[G*+ '1
(1 Pout) 2 G - F, n.j [F [3:] 2
(1 )ou) ) ||E|ET) - F, M. [c:]] 2 + E
= (1 )om) 2 (Ag + E
For t = 0, we have that A = 0, then average over time gives
+ Σーー A < (1-Pw)²2
7 Ei-
glt
Pat
Therefore, the bias has the following bound
T
1
t=
gt+1 bias
I (1 - Pmm) P
gT ET
Ey
0²
8
(1- Pan) Pon
1 T-1 ce+1
21=0
evar
Using Lemma
T-1 et+1 bias
S
Pin) Li,02
(1-Pa) +
E'
20
PnS2
3i
C²
(1-Dmn)²
T-
5
Pan
21= var
(1 - pb) 2t
I1-1 =l +
2(1 - Pay)
)
C²
(I-Pan)²
Er' gt+1
Sa
S1
Pun
7
Using Lemma 10
we have that
+ Et
T et+1 hias
[1 L.
8a
2n
B3
?
2
T
T 11
[|||
+ 2(1 10l--p.'''
Si
Ca
5
(1- Don) g(+1
Pusx
T 2tm
(I - pn) i.
2n
Σ(=
T
||[
2 1
Ce
Sa
B
S1
St
(1 L
Gn
B
?
2
+
Pur
E
&
Variance. Combine the variance of NestedVR in Lemma 13
and Lemma 2 gives
T-1 gt+l
s 14 14-32
Pun Bi
+
P-pa
(1- Piul
18n²
+
(1-paa)
ΣT
||
T
B2
Pn
B5
B2
T
+ 14 96
Pon Bi
(1 Pe, (1
Pas)
L
+
Pon) 8Lg
B2
S1
B19
43

---

Using descent lemma (Lemma and bias-variance of Theorem [E-NestedVR Convergence] Consider the (FCC)) problem. Under the same assump- lions as Theorem 3
If ((33) then we choose the typeraparaaeters of E-NestedVR (Algorithm i as .m
B = B2 n., Pont = 1, S1 = 2 = Lps- , - L 8,7 (
If = 52 2/3),, then we choose the hyperaparameters of E-NestedVR as B1 = n, B2 =
nu, Powa = 1/ 1/ = S2 = max (CCCge 1/2 (22,,1//(( Pin = 1,7 1 (
Then the ouiput x² of E-NestedVR satisfies: [[[[F[(=*)] 8², for nonconvex F' with iterations = (L)(()(()))) FT)==
Proof: Denote. G
G++1 E-NVR
36
E-NestedVR (Lemmal
VF I| 2(F((=))FF) F*)
|||
1=0
27
1==
7T
Lpz
T
Ei=
T-1
var
c1+1
+ T -1=0
II-1 gt+11 bias
2( ) F*)
+ (1-pa) Li Gn
11 ETS |E| 2 21-P.) P
C² +
77
Sn
B
81
S2
(1-pm) Li on
2
(l-par)² Tpp>) 7 D gt+1.
PanS22
B
Pou.
As we would like the right-hand side to be bounded by either 1 ET= |E ="
Bound on 2(F(m)) F*)
with E² i.e.
78
rT ž (F(x") - F*)
(39)
Coefficient of + ETT
[[ / is bounded by i.e.
(1-Pat 1 F Gn S
S2
which can be achieved by choosing the following step size
PamPay /S 5l (1-Puu)) 3/2
7 S
(40)
2(1 P with g2
Bound
81
2(1 Puy) 22
< E.
(41)
81
Boound
with 22. This leads
S₂ 2 Cn
(42)
Bound on the variance. First notice from
(40) and
7 S 2L
11 1-pm) 1-p=PP2
(1 Deul 1
Pn
B
Post
L
(1 1 Peu)?
Post
Therefore, we only need consider the upper bound on
(I-Peu)² + +
vvar
Pou
< 14 32 (1-
((5
Pest
+ 1mpae Past
(1)
18n
(1-Pree)
L2 T-1
||E|+++1||
Pese
B
Sa
B3
Hg
F
2i=
+ 14 96 (1 ppu))
Pass B.
(1 Pho (1 Pon)
1.
+
(1 Peu) 8i.
Pen
B2
Pau
B,S,"
44

---

We impose the constraints for each term
(1 (1-pe pou)"
Pos (1 (1-Pa)
18n
7. 2
Poa
B3
(1-Pom) 1 Pue (1-Bm) Bnn) 18n
p.p7? <
B2
Sa
B3
pan)"
1-pue 7 2
122
[1 Pou)
L2 S 6² Pou
Pog )
Pla Poue) Fg 2
Bg
81
[1 [1-pu 1 857
2 52
Peu
B1S1
These can be simplified as
Y S
PaPon v By v91
(43)
(I Pea)) VI Pm Ly
Popi /B, /
(44)
[I P// VI 11-1-1p LF
S
BBr
(45)
(1-Pa) 372 LF
(1 (1-pen) 7/
B1 2
(46)
Rou (1 Pao L.
B 2
(47)
plu
Paul 2
B
(48)
Te
Constraints from Lemma 14
72 Lp max
(1-Pu) Sn
1 Pest
(1- 18n.
(1-Pea)
<
B2 B2
PaSa
B
B2
which can be translated
7 S
PAVSiVB. LFVI-Mi Piu
(49)
7/ S PaRai / B5g
(50)
LevI-Pon/l Put
? E LevT-
VBa
(51)
Constraint from sufficient decrease lemma:
I 25
(52)
We simplify the conditions noticing that 1) (48)
is weaker than (46):
2) (45)
and (51) are weaker than
52) Combine all the constraints on y, i.e. 43
49
50
2 1. min min
{1,
PinPor V
min 1, vI-
Pav B5
Pac V
Pon
(I Dou) / I-poo LF
VI 11-P0 Pie
5L (1 ppo.3/3
This can be simplified as upper bound
PaPua Vs, VT-
PaDon S.VB. PaPi STVB.
7 S
Lr min
VT
Pay
Now we consider sets of hyperparameters depending the size of Case 1: For n we choose the following set of hyperparameters
B B2 =
Pout
1,
S = -ipee²
S2 = -1 Pin = i
Then we have 7 S LF
min Pay3i VI-Pm
1)
we have the total sample complexity of LF
BrSTT B.S,T=
F(x F SySa
45

---

BSGD
E-BSGD
m=1
m=1
1.25
m= 10
m=10
Suboptimality
m=100
m=100
1.20
1.15
1.10
1.05
25000
50000 75000
25000
50000
75000
Figure 4: Performance of BSGD vs. E-BSGD on the few-shot sinsuoid regression task.
Case 2: For n = (0-00(((2))) we choose the following set of hyperparameters
B Tb
B2 = vi,
Pont Vn
L. n²2
In this case, 446 is stronger than 47 which requires S1 2
S = S2 = max
{
[1/2 T
1/2 -1/2
ne
Pin =
Then have 7 S LF
min
Pau TAySS
1} Lr we have the total sample complexity of
vI 71-Paut Post
B2STT PaS.Ty
F(x ( F BaSa (F(x*") - F*) max
1/2
dp
Vnne
By picking æ uniformly random among (m') we get the desired guarantee.
F
Missing Details from Section 5
F1
Application of First-order MAMI
Over the past few years, the MAML framework [T] has become quite popular for few-shot supervised learning and meta reinforcement learning tasks. The first-order -odee--Agnottcc Meta- Learnne (MAML) can be formulated mathematically as follows:
min Einp.D; (uery
lg (ED; (xc Vlie, Di )) D query))
where is the step size, Supp and Dí query are meta-training and meta-testing data respectively and being the loss function of task i. Stated in the CSO framework, fe( = (, Di Diuery) and (x, {) == x - aV4(x, Disp)) where & = (i, query) and = Dí Diupp
In this context, lots of popular choices for fş are smooth. For illustration purposes, widely used sine-wave few-shot regression task as appearing from the work of Finn et al. [Л]. where the goal is to do few-shot learning of a sine wave, A sin(t - Φ). using neural network (t,(t) with smooth activations, where A and @ represent the unknown amplitude and phase, and denotes the model weight. Each task i is characterized by (A', 0², D Diuery). ). In the first-order MAML training process, randomly select task and draw training data rj D Daupo- Define the loss function for given dataset D as E, (:(:::)) D) ELED A sin(t o²) (t)( We then establish the outer function fx) ( 2 Diuerry) and inner function 9, (x) smooth, results applicable.
discuss
aaV a Diupp)) As f; is
In Figure 4 we show the results of BSGD and E-BSGD applied this problem. In this experiment, the amplitude A is drawn from a uniform distribution 2/(0.1, 5) and the phase ø drawn from u(0 r). Both Ssupp and D Dquary are independently drawn from u(-5.5). 5).. The step size is set to
46

---

= 0.01. The batch size is fixed to 10. The performances of BSGD and E-BSGD are very close. This is not surprising because finetuning step size is chosen be small which significantly reduces the variance of 9n> making the bias of meta gradient to be very small (O(a²)), Therefore, we observe similar performance of BSGD and E-BSGD. Similar trend also holds for BSpiderBoost and NestedVR compared their extrapolated variants.
F.2 Application of Deep Average Precision Maximization
The areas under precision-recall curve (AUPRC) has an unbiased point estimator that maximizes average precision (AP) [26] 34]. Let S+ and S- be the set of positive and negative samples and S= S_ S Let (-) (-) be classifier parameterized with w and l be surrogate function, such as logistic sigmoid. A smooth surrogate objective for maximizing average precision can be formulated as 33
Exesy (()w(x)) hw (x:))
F(w)
1 [4 2,ES+ Enes e(hwo hww (x;))
Σ
This problem can be seen as a conditional stochastic optimization problem with gi g(()) = [ExEs_ ((h (x) hw (x,)), ExEs ((hw(x) (w))) and fi R R - R is defined y/ where [y]x denotes the kth coordinate of vector y E R R R((0). During the stochastic optimization of this objective, we draw uniformly at random { := z; (drawn from the set where set 2 is drawn uniformly at random from S,
f((y) vi2
S4) as positive sample and n/ { S and functional (w) == (() hw Note and 22 is drawn uniformly random from
that fi E C is smooth with gradient
ff (y)
y ( =
Therefore, results from Sections] 3 and again apply.
F.3 Necessity of Additional Smoothness Conditions
Throughout the paper, assume bounded moments (Assumption 1 and smoothness condition (Assumption 2 to derive our extrapolation technique. However, it worth noting that the technique itself does not explicitly depend on higher-order derivatives. Our theoretical framework does not address the behavior of extrapolation in the absence of these smoothness constraints. In this section, we investigate the application extrapolation to two non-smooth functions:
ReLU function given by g(x) max {x, 0):
Perturbed quadratics represented as g(z) x² 2 Trien))eWave(x) The function has period of 2 and spans the range [-1,1], defined as:
Wave(x) (avee)))aave(z))
TrvvngleWave(z) = 2
x
2
We set s and consider random variable ~ A(10,, 100) with m = 1. We then apply first-, second-, and third-order extrapolation. The outcomes depicted in Figure Remarkably, both the ReLU and the perturbed quadratic functions do not conform to the differentiability assumptions inherent to our stochastic extrapolation schemes. Nonetheless, as indicated by Figure Saladd and Figure 5b our proposed second- and third-order extrapolation techniques yield a superior approximation of (())
Visual representations of these functions can found in Figure 5
47

---

ReLU
Perturbed quadratics
15
[0(s+E(61) Avgic!
[ Avgle (igtclltt)ll
Perturbed quad.
cll op gls;
Db. ((s)
Quadratic ReLU
10
10
cll q(s)
C (ss)
c(ssss)
eBl q(s)
10
10"
10
10 Number of estimates
10"
10
10 Number of estimates
10
10"
5.0
2.5
0.0
2.5
5.0
Figure 5c Figure 5: (a) Fig. 5a: Error in estimating g(s + [5) for our proposed first- second,, and third-order
Figure 5a
Figure 5b
extrapolation schemes applied to ReLU q(x) = max fx, 8 0, 8 ~N(10 100). m = 1. (b) Fig
5b: Error in estimating q(s + [(]) for our proposed first-, second-, and third-order extrapolation
schemes applied to perturbed quadratic ((x) = / Trirangleeaav(())+ 6 100).
m 1. The Triangle
Wave(z) TriangleWave(r) has a period 2 and spans the range [-1.1], i.e. 2/2 2 +
(c) Fig 5c: The ReLU and perturbed quadratic used in the Fig. 5a and 5b along with quadratic curves.
48


Reviews:
[{"review_id": "Tkp15q0S34", "reviewer": "Reviewer_VftD", "summary": "The paper addresses the conditional stochastic optimization (CSO) problem. A noted drawback in CSO is the bias in its sample-averaged gradient, an offshoot of its nested structure, which necessitates an extensive sample complexity to achieve convergence.\nThe authors introduces a new stochastic extrapolation technique address this bias effectively. They propose that by merging this extrapolation with variance reduction techniques, improvements in sample complexity can be realized compared to existing results for non-convex smooth objectives. The authors claim that the proposed methods improve the sample complexities for both the CSO and FCCO under some reguarlity.", "questions": "Please see the comment in the weakness section.", "limitations": "Please see the comment in the weakness section.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- Overall writing is clear, and organization is well-structured.\n- The paper introduces an extrapolation-based scheme to alleviate bias in gradient estimations. The proposed method is used for gradient estimations for CSO and FCCO problems.\n- For CSO problem, the authors claim that the proposed methods, E-BSGD and E-BSpiderBoost, achieve an improved sample complexity compared to the existing bounds under some additional reguarlity.\nFor FCCO problem, the authors proposed an algorithm, E-NestedVR, combining the extrapolation-based scheme with a multi-level variance reduction which achieves an improved (or at least matching) sample complexity compared to the existing results. \n- The techniques of the anlysis are interesting, and worth credit.", "weaknesses": "- While the new bounds show improved rates, the results are based on additional regularity assumptions. The authors acknowledge the discrepancy in the set of assumptions used in the current paper and those in the existing results. They state that \"the bounds derived from previous studies do not improve when incorporating this additional regularity assumption\" of the 3rd-order differentiability, and hence argue that their results present an improved bound. \nHowever, I am not sure whether such an assertion is valid. The new regularity condition imposed by this paper is used for the authors' technical convenience, not required by the existing methods. Hence, it is very possible and often obvious that the existing methods do not improve even with the new additional regularity assumption because these methods did not even need such regularity. \n- So I am not sure whether the claim of the \"improved\" rate is valid. Aren't they rather apples and oranges? For example, can you precisely pinpoint where Assumtpino 6 is needed? What rate (just a ballpark) would you get if you do not have this assumption?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for appreciating our work. Please find below our responses to the specific weaknesses that you mention. \n\n>**While the new bounds show improved rates, the results are based on additional regularity assumptions ...**\n\nWe agree that the regularity assumptions are for technical convenience and apologize if our phrasing was unclear. This regularity condition allows us to use Taylor expansion to derive extrapolation schemes, but none of our algorithms (E-BSGD, E-BSpiderBoost, and E-NestedVR) explicitly use the high order derivatives. \n\nIn Lines 88-89, we only wanted to clarify that if we add our additional 3rd-order differentiability on $\\nabla f_\\xi$ assumption to existing methods, they do not automatically yield better rates. We will rephrase the discussion here to be clear. Btw, one of the reasons why we brought this up is because we conjecture that with even stronger differentiability assumption, our bounds automatically improve. The reason here being that then we can construct higher-order (> 2) extrapolation operators and use them in our proposed algorithms. So this might be a case where stronger assumptions directly improve the results.\n\n>**So I am not sure whether the claim of the \"improved\" rate is valid. Aren't they rather apples and oranges?**\n\nWe again agree with the reviewer that because of additional assumption, a fair comparison is hard. However, we would like to point out two things:\n1) As we point out in the paper for many common CSO/FCCO problems our additional assumption is satisfied. This includes invariant logistic regression, instrumental variable regression, first-order MAML for sine-wave few shot regression considered by Hu et al. [15] (see https://arxiv.org/pdf/2002.10790.pdf) while proposing BSGD/BSpiderBoost, and similarly, deep average precision maximization considered by Wang et al. [31] while proposing SOX. So in these cases there is a direct improvement. \n2) Beyond CSO/FCCO rates, we also introduce a novel bias reduction technique, that we believe is of independent interest.\n\n>**For example, can you precisely pinpoint where Assumtpino 6 is needed? What rate (just a ballpark) would you get if you do not have this assumption?..** \n\nThroughout our analysis, we provide bias bounds (e.g., Lemma 6)  for various algorithms, which use Corollary 1 which in turn is built on Proposition 1 under the Assumption 6. Now, as an extension, we give an experimental result (see the global response and attached pdf) that might indicate that our proposed stochastic extrapolation technique also corrects biases for even non-smooth objectives. We leave it as future work to theoretically weaken the regularity assumption.\n"}, {"review_id": "o8z1lFtlMA", "reviewer": "Reviewer_eDyu", "summary": "The authors study stochastic optimization problems with nested conditional expectations, with access to first-order samples from the involved functions. With such an oracle access, it is non-trivial to build unbiased estimates of the gradient, hence normal stochastic optimization methods don't work. \n\nThey authors show that under a third-order differentiability assumption, which they argue to be \"mild\", one could adapt existing extrapolation techniques to this problem and obtain an estimate of the gradient with a reduced bias. This in turn results in substantial improvement in the convergence rate of algorithm fed with this bias-reduced estimate. The authors demonstrate this using state-of-the-art algorithms, both with and without finite-sum variance reduction.", "questions": "Please add any comments you may have about the points raised under \"Weaknesses\", including the relationship to the work on accelerated stochastic composition optimization, as well as the issue with Eq (2).", "limitations": "The paper can be improved in terms of clarifying the limitations of its results, as explained under \"Weaknesses\" above.\n\nThis is a theoretical paper. As such, greater societal impact is not addressable at this level.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The claimed improvements are substantial. The paper is modular, in the sense that there is one clear goal: reducing the bias of the gradient estimate, and that is carried out separately. Then, the result is fed into existing best algorithms. This makes the contribution very clear.", "weaknesses": "There seems to be some issue in the last term of Eq (2): since $\\phi_\\delta$ depends on $\\delta$, we cannot take it outside expectation, neither can we decompose the resulting expectation in such a way that $E[(\\delta - h)^{2k-1}]$ comes out and multiplies the expectation of the term involving $\\phi_\\delta$. I am not sure if this will have a major adverse effect on the rest of the results in this section, but I will keep looking deeper in the proofs.\n\nIn terms of related work, I am surprised that the use of extrapolation for bias reduction in Stochastic Composite Optimization is missed. The central work here is:\nM. Wang and J. Liu. Accelerating Stochastic Composition Optimization. 2016\nThe authors need to discuss the relationship between the techniques.\n\nI also find it problematic that the authors call the assumption of third-order differentiability a \"mild assumption\". Whether this is mild or not has to be left to the reader to decide. Currently, the introduction and Table 1 give an incorrect impression. This needs to be made clear way earlier in the introduction, and also laid out clearly in the caption of Table 1. Also, the assumption $n = O(\\epsilon^{-2})$ is certainly worth more explanation that the footnote given.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your encouraging comments and valuable feedback. Please find below our responses to the specific weaknesses that you mention. \n    \n>**last term of Eq (2)**\n\nThe reviewer is correct, there is a typo in Eq. (2), $\\phi_\\delta$ should be inside the expectation, and we will fix this. To clarify, the idea behind our extrapolation scheme is that  we cancel out the lower order terms and keep the remainder small. The lower order terms cancel out, while the remainder is upper bounded by the uniform bound on $q^{(\\cdot)}$ and the moments of $\\delta$. By construction, the moments decrease with increasing $m$ of $\\delta$, c.f., Lemma 1 in Appendix C.\n\n>**Reference: M. Wang and J. Liu. Accelerating Stochastic Composition Optimization. 2016** \n\nThis is a very interesting paper, and we thank the reviewer for pointing it out. The problem they considered is the same as considered by Zhang et al. \"Multilevel composite stochastic optimization via nested variance reduction\" [38]. Both of them try to estimate the inner stochastic function $g_\\eta(x)$ with no bias. This paper use extrapolation to estimate $g_\\eta(x)$ with an iteration complexity of $O(T^{-4/9})$ while Zhang et al. use variance reduction and yield a better $O(T^{-1/2})$. However, both methods cannot be applied to conditional stochastic optimization, considered here, because the inner variable $\\eta$ depends on the outer, which makes their estimation biased.\n\nRegarding the similarities and differences between our extrapolation technique and [Wang and Liu, 2016].\n- Similarities: Both these papers use affine combinations in the construction where some coefficients are negative. That is why both methods are termed extrapolation.\n- Differences:\n    - Wang and Liu apply extrapolation to iterates to help estimate the inner function, while we apply extrapolation to the outer function to reduce the bias in CSO problem.\n    - Our affine combination coefficients are constants while their coefficients depend on iteration (e.g. $\\beta_k=2k^{-b}$ in their Theorem 1).\n    - Different motivations behind picking the affine combination coefficients. We choose coefficients based on the motivation to cancel out lower order terms in Taylor series while they don't.\n    - As explained in Lines 160-164, our extrapolation technique naturally generalizes to higher orders, while [Wang and Liu, 2016] does not.\n\nWe will add this to our discussion in Appendix B.\n\n>**problematic that the authors call the assumption of third-order differentiability a \"mild assumption\".**\n\nWe meant to say that even with this assumption we still cover lots of known application of CSO/FCCO problems appeared in the closely related CSO/FCCO works [15,31], including invariant logistic regression, instrumental variable regression, first-order MAML for sine-wave few-shot regression task, deep average precision maximization etc. We will rephrase this discussion.\n"}, {"review_id": "Q38kRvZk2w", "reviewer": "Reviewer_me2Y", "summary": "The paper highlights that optimizing conditional stochastic optimization problems is challenging as the sample-averaged gradient is biased. The biased gradient increases the sample complexity needed to achieve convergence. To account for the bias, the paper proposes stochastic extrapolation. The method shows that the bias can be expressed as a sum of Taylor series expansion terms and the bias can be estimated by constructing estimates for each of the terms in the expansion. The key insight is that the size of the $k^{th}$ order term of the series is of size $O(1/m^k)$ where $m$ is the batch size. They propose the $k^{th}$ order extrapolation operator which computes up to the $k^{th}$ order term in the Taylor series and uses the terms to correct for the bias. The paper then uses the the stochastic extrapolation technique to bias correct the gradients for the conditional stochastic optimization problem and finite-sum coupled compositional optimization problem. They then prove convergence guarantees for optimization algorithms applied on the two problem types, showing stochastic extrapolation improves the sample complexity of the algorithms. Finally, they perform a numeric experiment on invariant logistic regression and show the extrapolated version of the algorithms achieves lower sub-optimality. \n", "questions": "1. The paper mentions a burn-in rate for higher order extrapolation. Is there any intuition of controls the burn-in rate or if the burn-in rate is theoretically quantifiable?\n2. Does the stochastic extrapolation perform better or worse when the number of samples is small? The numerics seem to indicate the performance is the same for BSGD and BSpiderBoost when the # of samples is small.", "limitations": "From a technical perspective, the authors do note that their proposed approach requires the target optimization problem to satisfy certain regularity conditions. However, it is unclear what is the cost of applying the stochastic extrapolation and if there is any trade-offs. \n", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper proposes a fairly novel approach to address the issue of biased sub-gradients. The problem and approach are described clearly and intuitively. The paper is also able to highlight some important optimization problems that satisfy the regularity conditions leveraged by the paper. The paper’s significance is being able to leverage these regularity assumptions in order to prove stronger sample complexity bounds. ", "weaknesses": "The paper is hard to read since authors i) often reference the appendix with limited context, ii) do not point out if the reference is in the appendix or not, and iii) do not define notation. \n\t- As an example for the first point, Lemma 1, Lemma 2, and Theorem 7 are all in the appendix but it is not noted. \n\t- For the second point, Lemma 2 also is referenced in line 155 to quantify the variance of the operator applied to the function, but it’s unclear what Lemma 2 shows precisely. In most cases, it seems that the authors are trying to make a statement and reference the proof, however, the language is not clear that is the case. As evidence, when referencing Lemma 2, the authors state “a consequence of Lemma 2 is that” when it could be more clear by stating “Lemma 2 (in Appendix Section B) proves”. \n\t-For the third point, it is hard to find a definition for V in Lemma 2. \nThe above three points make reading and verifying the statements in the paper challenging. \n\nThe paper has minimal numeric studies. For example, it would be interesting to see how the approach performs for problems that do not satisfy the regularity conditions. It may also be interesting to see the improvement as the level of bias varies due to underlying problem parameters. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive feedback. We also thank the reviewer for the suggestions on the writing and readability. We will incorporate the suggestions accordingly. Please find below our responses to the specific questions and weaknesses that you mention.\n\n\n>**The paper has minimal numeric studies. For example, it would be interesting to see how the approach performs for problems that do not satisfy the regularity conditions. It may also be interesting to see the improvement as the level of bias varies due to underlying problem parameters.**\n\nWe have provided a pdf in the rebuttal that explore other dimensions of the extrapolation as suggested by the reviewer. In global response, we discuss the case where the differentiability assumption fails. We now discuss Fig. 6 in the attached pdf where we vary the level of bias.\n\n**Description of Attached Fig. 6**: We vary the magnitude of the second order moment ($\\sigma_2$) of the random variable. The function being estimated is $q(x)=x^2/2$. In this setting, both second- and third-order extrapolation schemes yield unbiased estimates. On the other hand, the bias of first-order method grows with $\\sigma_2$ according to Proposition 2 in the Appendix C. The experiment results confirm that with increasing second moments, our proposed second- and third-order extrapolation schemes still enjoy the same convergence rate. \n\n> **burn-in rate for higher order extrapolation**\n\nThe burn-in phase depends on the constants in the problem (i.e., smoothness constants ($a_k$) and magnitude of moments ($\\sigma_k$)). If resources permit, we can estimate these constants to roughly draw the burn-in region and rate.\n\n>**numerics seem to indicate the performance is the same for BSGD and BSpiderBoost when the # of samples is small.**\n\nThis is also empirically observed in the previous work [15]. The BSpiderBoost is much harder to tune in practice, and for some tasks the advantage of BSpiderBoost over BSGD can be marginal. So in this paper, we pay more attention to the improvements of extrapolation rather non-extrapolation version (e.g., BSGD vs. E-BSGD, BSpiderBoost vs. E-BSpiderBoost).\n\n"}, {"review_id": "qqZ02nnCKB", "reviewer": "Reviewer_STJD", "summary": "This paper presents a stochastic extrapolation technique with variance reduction to obtain improved sample complexity bounds for conditional stochastic optimization problem. Numerical study also support the effectiveness of the proposed algorithm.", "questions": "N/A", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The stochastic extrapolation is a useful tool for CSO problem. The technique is new for solving the CSO problem, though it requires higher-order smoothness assumption of the loss function. I think it could be potentially useful for other stochastic optimization formulations. I am also curious about how the authors come up with this approach? Do authors inspired from any existing literature?\n- The overall presentation is very clear and the theoretical results with technique assumptions are presented in detail.\n- Numerical study is very strong to support the effectiveness of the algorithm.", "weaknesses": "- From my perspective, some notations could be confusing. For example, in Theorem 2 the authors use $\\Omega(\\cdot)$ notation for batch size $m$ and number of iterations $T$, but in line 235 the authors use $\\mathcal{O}$ instead. I would encourage the authors check those notations throughout the paper to make it consistent.\n- Please check and revise the first sentence in line 287.\n- In the theoretical analysis, the authors present iteration complexity together with sample compelxity per-iteration. However, in related work comparison, the authors only compare the overall total sample complexity of baseline methods. I encourage the authors also check and compare iteration complexity together with sample compelxity per-iteration. \n- In Table 1, I think the authors should also add V-MLMC method (from [16]) for comparison. Also, in numerical study, I am confusing why the authors do not compare with RT-MLMC method but only V-MLMC method?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for careful proofreading and suggestions. We will add the iteration complexities in the revision.\n\n>**I am also curious about how the authors come up with this approach? Do authors inspired from any existing literature?**\n\nWe independently came up with this stochastic extrapolation approach. The closest to our approach in statistics is the idea of sample splitting. Generally, the techniques in statistics are designed to be applicable to certain statistical models, while our approach seems more general. Besides, compared to previous bias correction approaches, ours is significantly different in terms of both setup and analysis. We have briefly discussed these differences in Appendix B. We fully agree with the reviewer that these techniques could be potentially used in other stochastic optimization problems.\n\n>**why the authors do not compare with RT-MLMC method but only V-MLMC method?**\n\nAccording to analysis in the previous work [16], when applied to CSO problem, V-MLMC and RT-MLMC enjoy same sample complexity (Table 3 in [16]). Experimentally too, [16] observed V-MLMC behaves better than RT-MLMC with a smaller variance, therefore, we choose to compare against the more robust V-MLMC approach. However, we will be happy to add RT-MLMC as a baseline."}, {"review_id": "wE6wxpbO8T", "reviewer": "Reviewer_B49C", "summary": "This paper considers CSO problems and its finite-sum variant FCCO, and proposed new algorithms incorporating extrapolation and variance reduction. The proposed algorithms are shown to enjoy a better sample size in the inner layer which induces an improved sample complexity compared to existing CSO literature. The authors also furthered their study in the FCCO regime, the proposed algorithm enjoys a better complexity in moderately large $n$ regime.", "questions": "1. For clarification, with the extrapolation framework you need the constant term $s$, but when applied to CSO, you just set $s=0$, I am not sure why it is important to include the $s$ into your framework if there is no nontrivial instantiation. Could you please comment more on it?\n2. For clarification, in Theorem 3, you set $m=O(\\epsilon^{-0.5})$, but in Line 247, you mentioned the straightforward extension of E-BSpiderBoost requires a different $m$ by taking a maximum, I am wondering why the setting of $m$ in Theorem 3 does not directly apply here.", "limitations": "N/A.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. Improved sample complexities for CSO and FCCO problems\n2. The algorithm design incorporates extrapolation which is new to the CSO literature I think, and it brings an improvement in the sample complexity in the inner layer, which reveals some innovation.", "weaknesses": "1. The additional regularity assumption (compared to [15]) on the bounded higher-order gradients/moments, even though authors tried to rationalize it, reduces the significance of the result.\n2. You mentioned \"... $\\Omega(\\epsilon^{-3})$ is a sample complexity lower bound for standard stochastic nonconvex optimization [2]...\" in Table 1, but as far as I can see, with your higher-order Lipschitz condition, the statement may not hold. Your function class is more restricted compared to the setting in [2]. I think authors may refer to  Could you please comment more on it?\n   - Carmon, Yair, et al. \"Lower bounds for finding stationary points ii: first-order methods.\" Mathematical Programming 185.1-2 (2021): 315-355.\n   - Arjevani, Yossi, et al. \"Second-order information in non-convex stochastic optimization: Power and limitations.\" Conference on Learning Theory. PMLR, 2020.\n3. Some writing issues, I believe the paper's writing style could benefit from a few adjustments to enhance its readability, there .\n   - Line 141, $T_m$ (vs. $T_{D_m}$)\n   - Line 148, \"lesser\"\n   - Line 173, \"to (be) $\\nabla$...\"\n   - Line 224, \"... some time $t$...\", I think such statements can be further revised and formalized.\n\nWith that, I think the paper provides some interesting results, especially in terms of the algorithm design, but I am not that convinced on the significance of the results (regarding the a bit unfair comparison) and feel that the writing can be further revised for a better flow.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for careful proofreading and suggestions. We will incorporate the suggestions about writing. Please find below our responses to the specific questions and weaknesses that you mention. \n\n\n>**The additional regularity assumption (compared to [15]) on the bounded higher-order gradients/moments, even though authors tried to rationalize it, reduces the significance of the result.**\n\nWe agree with the reviewer that it will be great to remove the regularity assumption. We would like to point out:\n1) For all the CSO/FCCO examples considered by Hu et al. [15] (see https://arxiv.org/pdf/2002.10790.pdf) including invariant logistic regression, instrumental variable regression, first-order MAML for sine-wave few shot regression considered, our additional assumption is satisfied. Hence, our results are widely applicable and could still be considered significant.\n2) Beyond CSO/FCCO rates, we also introduce a novel bias reduction technique, that we believe is of independent interest.\n3) Our bias reduction technique seems to have promise even the regularity conditions fail (e.g., for non-smooth functions) as suggested by our attached experiments (see global response).  We leave it as future work to theoretically weaken the regularity assumption.\n\n>**You mentioned $\\Omega(\\varepsilon^{-3})$ is a sample complexity lower bound for standard stochastic nonconvex optimization [2]...\" in Table 1, but as far as I can see, with your higher-order Lipschitz condition, the statement may not hold. Your function class is more restricted compared to the setting in [2].**\n\n\nWe thank reviewer for these references. Your second reference [Arjevani et al., 2020] gives a highly non-trivial result that even when stochastic higher-order oracles are available, $\\Omega(\\epsilon^{-3})$ remains a lower bound in sample complexity for nonconvex optimization. Because of this, the $\\Omega(\\epsilon^{-3})$ lower bound result also applies to our setting with the restricted function class (note that stochastic optimization is just a special case of conditional stochastic optimization). This in contrast with the situation in the deterministic setting where Carmon et al. \"Lower bounds for finding stationary points I\", 2019, show that sample complexity upper bound improves with access to the $p$th-order oracles with Lipschitz derivatives to $\\Theta(\\epsilon^{-(1+1/p)})$. We will add these references in the main text.\n \n\n>**For clarification, with the extrapolation framework you need the constant term, but when applied to CSO, you just set $s=0$, I am not sure why it is important to include the into your framework if there is no nontrivial instantiation. Could you please comment more on it?**\n\nYes, in Section 2, we introduce a constant $s$ to emphasize the generality of our scheme. We do use $s=0$ in the subsequent invocations, and would clarify this. \n\n\n>**For clarification, in Theorem 3, you set $m=O(\\epsilon^{-0.5})$, but in Line 247, you mentioned the straightforward extension of E-BSpiderBoost requires a different  by taking a maximum $m$, I am wondering why the setting of  in Theorem 3 does not directly apply here.**\n\n \nFCCO is a special case of CSO where the outer random variable is discrete and takes value in a finite set. Compared to CSO, there is an extra hyperparameter $n$ (the number of outer samples), when $n$ is large, then we recover the choice of Theorem 3. But when $n$ is small, for example, there is only 1 outer sample, then there is better choice of $m$ than the choice from Theorem 3.\n\n"}]

Author rebuttal:
We thank all the reviewers for constructive and actionable feedback on the paper. We have additional experimental results, in particular, addressing the question of what happens if the regularity  assumption gets violated.


**Description of Fig. 5 in the attached pdf**: We consider an experimental  setting similar to Fig. 1, but where the differentiability assumption is violated. The goal again, for a fixed $s$, is to draw samples of $q(s+\delta)$ to estimate $q(s+\mathbb{E}[\delta])$. 


1. Relu function ($q(x)=\max(x,0)$). This function is Lipschitz continuous but does not satisfy the smoothness condition as it is not differentiable at $0$. The Fig. 5a shows that with more estimates, both second- and third-order extrapolation outperform first-order extrapolation.
2. Quadratic function perturbed by triangle waveform ($q(x)=x^2/2+$TriangleWave$(x)+1$). The resulting function $q$ is non-convex and Lipschitz continuous. As noticed in Fig. 5b, despite the fact that this function violates the differentiability assumption, applying extrapolation to this problem still exhibits similar curve as the quadratic one (Fig. 1a in the paper). 
    
In Fig. 5c, we plot the above considered $q$ functions (Relu, perturbed quadratic). 

We gave a possible explanation to the above observations without rigorous mathematical proof. Given a non-smooth function $q$, if there exists a smooth function (say $\tilde{q}$) which is close to $q$ with an approximation error much smaller than the magnitude of bias, then the bias of higher-order extrapolation applied to $q$ can be decomposed into the bias of applying higher-order extrapolation applied to $\tilde{q}$ plus approximation errors. As the bias dominates approximation error, the bias correction on non-smooth $q$ look similar to that on smooth $\tilde{q}$.

In our paper, the differentiability assumption is only used to ensure the existence of Taylor series, which motivates the extrapolation scheme. But higher order derivatives are not explicitly used in the extrapolation. The above experiments indicate that the Assumption 6 may be further relaxed while extrapolation still work.  We will add these experimental results to the paper. We leave the formalization of this argument and relaxation of Assumption 6 as future work.


Meta-review: This paper proposes stochastic extrapolation schemes to address bias in gradient estimates in conditional stochastic optimization. The paper makes meaningful theoretical contributions by assuming smoothness conditions. Reviewers raised concerns about the clarity of exposition, especially regarding the mathematical framework. I recommend carefully addressing the comments on better contextualizing the additional assumptions used in the paper, and discussing the limitations of the framework more.
Decision: Accept (poster)