Closing the Gap: Tighter Analysis of Alternating Stochastic Gradient Methods for Bilevel Problems
Authors: Tianyi Chen
Yuejiao Sun
Wotao Yin
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: Stochastic bilevel optimization
min-max optimization
compositional optimization
convergence analysis

Abstract: Stochastic nested optimization, including stochastic compositional, min-max, and bilevel optimization, is gaining popularity in many machine learning applications. 
While the three problems share a nested structure, existing works often treat them separately, thus developing problem-specific algorithms and analyses. 
Among various exciting developments, simple SGD-type updates (potentially on multiple variables) are still prevalent in solving this class of nested problems, but they are believed to have a slower convergence rate than non-nested problems. 
This paper unifies several SGD-type updates for stochastic nested problems into a single SGD approach that we term ALternating Stochastic gradient dEscenT (ALSET) method. By leveraging the hidden smoothness of the problem, this paper presents a tighter analysis of ALSET for stochastic nested problems. 
Under the new analysis, to achieve an $\epsilon$-stationary point of the nested problem, it requires ${\cal O}(\epsilon^{-2})$ samples in total. 
Under certain regularity conditions, applying our results to stochastic compositional, min-max, and reinforcement learning problems either improves or matches the best-known sample complexity in the respective cases. 
Our results explain why simple SGD-type algorithms in stochastic nested problems all work very well in practice without the need for further modifications. 

where f a'dnd g are differentiable functions; and, & and are random variables. In the optimization is referred to as the stochastic bileve! problem, where the upper-level Closing the Gap: Tighter Analysis of Alternating Stochastic Gradient Methods for Bilevel Problems
Tianyi Chen Rensselaer Polytechnic Institute chentianyil9 @ waaiiniillimmmmommmmmmmmmm gmail.com
Yuejiao Sun
Wotao Yin UCLA wotaoyin math.ucla.edu
UCLA sunyj @ munyjmmath.ucl.cduu
Abstract
Stochastic nested optimization, including stochastic bilevel, min-max, and compo- sitional optimization, is gaining popularity in many machine learning applications. While the three problems share nested structure, existing works often treat them separately, thus developing problem-specie specific algorithms and analyses. Among various exciting developments, simple SGD-type updates (potentially on multiple variables) are still prevalent in solving this class of nested problems, but they are believed to have slower convergence rate than non-nested problems. This paper unifies several SGD-type updates for stochastic nested problems into single SGD approach that we term ALternating Stochastic gradient dEscen'T (ALSET) method. By leveraging the hidden smoothness of the problem, this paper presents tighter analysis of ALSET for stochastic nested problems. Under the new analysis, to achieve e-stationary point of the nested problem, it requires (ce33) samples in total. Under certain regularity conditions, applying our results to stochastic compositional, min max, and reinforcement learning problems either improves matches the best- known sample complexity in the respective cases. Our results explain why simple SGID-type algorithms in stochastic nested problems all work very well in practice without the need for further modifications.
Introduction
Stochastic gradient descent (SGD) methods are prevalent solving large-scale machine learning problems. Often, SGD is applied to solve stochastic problems with a relatively simple structure. Specifically, applying SGD minimize the function Eg [f(:; {)) over the variable xr Rdd we have
the iterative update *++ = x² (x* 5*), where a > 0 is the stepsize and Va( <*) is the stochastic gradient at the iterate =² and the sample e* However, many problems machine learning today, such as meta learning. deep learning, hyper-parameter optimization, and reinforcement learning, go beyond the above simple minimization structure (termed the non-nested problem thereafter). For example, the objective function may be the compositions of multiple functions, where each composition may introduce an additional expectation (2; and, the objective function may depend on the solution of another optimization problem [3]. In these problems, how to apply SGD and the efficiency of running SGD are not fully understood.
(
To answer these questions, in this paper, we consider the following form of stochastic nested optimization problems, which generalization of the non-nested problems, given by
min F(x) = Eg [ (I, y (x):
(upper)
(1a)
DERd
s.t. (² arg min (xl "ER""
(lower)
(1b)
literature 446) the problem ①
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

optimization problem depends on the solution of the lower-level optimization over y E R denoted as y" (z)) which depends on the value of upper-level variable E R
The stochastic bilevel nested problem ① encompasses two popular formulations with the nested structure: stochastic min-max problems and stochastic compositional problems. Therefore, results on the general nested problem ① will also imply the results in the special cases. For example, if the lower-level objective g is the negative of the upper-level objective i.e. g(2, ys Φ) == fxx y3 E) the stochastic bilevel problem ①T reduces to the stochastic min-max problem
If g(x, 6) == ff( E)
min
F(x)=
max Eg [f YE
(2)
FER
Motivated by applications zero-sum games, adversarial learning and training GANs, significant efforts have been recently made for solving the stochastic min-max problem; see e.g., 17.1.
For example, if the upper-level objective f is only a function of y, i.e., [(x, yı E) == (yr E), and the lower-level objective g is a quadratic function of y. i.e. g(æ,, y; () == 11y - hil;; di with smooth
function h of æ, then the variable y (z) admits a closed-fore solution, and thus the stochastic bilevel problem TT) reduces to the stochastic compositional problem [12-14]
If g(z, y: 6) = 11 h(x:
min F(x) := Es (F DER"
(3)
Stochastic compositional problems in the form of (3) have been studied in the applications in model-agnostic meta learning and policy evaluation in reinforcement learning; see e.g. 15
To solve the nested problem ① by SGD, one natural solution is to apply alternating SGD updates on x and based on their stochastic gradients
x+1 - and x²1 = x -
where hg is the unbiased stochastic gradient of Eolg(<* v²i 6)] and ht is the (possibly biased) stochastic gradient of F(z*);; and, 8& and 0g are the stepsizes. A key challenge of rumning 44) for the nested problem is that (stochastic) gradient of the upper-level variable æ prohibitively expensive to compute. As we will show later, computing an unbiased stochastic gradient of F(x) requires solving the lover-level problem exactly to obtain y (z)).
An accurate stochastic gradient ity can be obtained in roughly three ways. One way is to run SGD updates on yd multiple times before updating x², which yields a double-loop algorithm. To guarantee convergence, it typically requires either the increasing number of lower-level y-update or the growing number of batch size to estimate hay see e.g., [16] 17.. The second way is to update y in a timescale
faster than that of x so that x² is relatively static with respect to y²: i.e., lim a 8x = 0; see e.g., [18]. The third way is to modify the direction h of y by incorporating additional correction term, which adds extra computation burden; see e.g., 19.. At a high level, these modifications either deviate from the lightweight implementation of SGD or sacrifice the sample complexity of SGD.
To this end, the main goal of this paper is to study the efficiency of running the vanilla alternating SGD 4 for the nested problem (I) and its implications on the special problem classes -
1.1 Main results
This paper analyzes unifying algorithm for the stochastic bilevel problems that runs SGD on each variable alternatingly. We provide sample complexity that matches the complexity of SGD for single-level stochastic problems. Our results explain why SGD-type algorithms in stochastic bilevel, min-max, and compositional problems work very well in practice without modifications, including correction, increasing batch size, and two-timescale stepsizes.
In the context of existing methods, our contributions can be summarized as follows.
CI) We connect three different classes of stochastic nested optimization problems (stochastic compositional, min-max, and bilevel optimization), and unify three popular SGD-type up- dates for the respective problems into a single SGD-typp method. We call the Al ALternating Stochastic gradient dEscenT (ALSET) method.

---

ALSET
BSA
TTSA
stocBiO
STABLE
SUSTAIVRSVRE
hatch size
((1)
O(1)
((1)
(EE))
O(1)
O(1)
y-update
SGD
OlE SGD steps
SGD
SGD
correction
momentum
samples in samples in &
O(N)E=9)
E Ö(N
O - -)) Ó(N"E
( 3)
O(
O
O
Table I: Sample complexity of stochastic bilevel algorithms (BSA in [6]. TTSA in 18. stocBiO in
[77. STABLE in [19]. SUSTAIN in [25). RSVRB in (26]) to achieve an e-stationary point of F());
the notation O(-) -) hides the terms loge - the notation xP denotes a polynomial function of
since the dependence
is not explicit in [8 19 25 26
C2) Under the same assumptions made in most of the previous work, we discover that the solution of the lower-level problem is smooth a property that is overlooked by the previous analyses. By leveraging the hidden smoothness, we present a tighter analysis of ALSET for the stochastic bilevel problems. Under the new analysis, achieve an e-stationary point of the nested problem, ALSET requires O(--2) samples in total, rather than the O(c sample complexity in the existing literature.
C3)
We further customize the analysis to the two special cases - the compositional and max-max problems, and establish the improved sample complexity relative to that in the literature. We apply a new analysis to the celebrated actor-critic method for reinforcement learning problems. Under some regularity conditions, we show that, achieve e-stationary point, the single-loop actor-critic method requires O(e=²) samples with i.i.d. sampling, which improves the best-known result of O(E=5/() in the literature.
1.2 Other related works
To put our work in context, we review prior art that we group in the following three categories.
Stochastic bilevel optimization. We trace the study of bilevel optimization to the 1950s [20] Many recent efforts have been made to solve the bilevel problems. One successful approach is to reformulate the bilevel problem single-level problem by replacing the lower-level problem by its optimality conditions [3. Recently, gradient-bar based methods for bilevel optimization have gained popularity. They iteratively approximate the (stochastic) gradient of the upper-level problem either
in a forward or backward manner 21 3 22 23 Recent work has also studied the case where the
lower-level problem does not have unique solution
24
The non-asymptotic analysis of bilevel optimization algorithms has been recently studied in some pi- oncering works, e.g., [6 17. just to name a few. In both 17]. bilevel stochastic optimization algorithms have been developed that run in a double-loop manner. To achieve an e-stationary point, they only need the sample complexities O(e-3) and O(c respectively, comparable to that of SGD for the single-level case. Recently, a single-loop two- two-timescale stochastic approximation algorithm has been developed in [18] for the bilevel problem ( Due to the nature of the two-timescale update, it incurs the sub-optimal sample complexity Oee 5/2). A single-loop single- timescli stochastic bilevel optimization method has been recently developed in [1]. While the method can achieve the sample complexity O(e O(e-)), the resultant update y needs extra matrix projection, which can be costly. Very recently, the momentum based acceleration has been incorporated into both the x- and y- y-upaasss in [25] (26] and also in [27] after our submission to the conference, where the new algorithms therein enjoy improved sample complexity
However, these results cannot imply the O sample complexity of the alternating SGD update (4). and are orthogonal to our results. A comparison of our results with prior work can be found in Table I
Stochastic min-max optimization. In the context of min-max problems, the alternating version of the stochastic gradient descent ascent (GDA) method can be viewed as the alternating SGD updates (4) for the special nested problem (2). To mitigate the cycling behavior of GDA for convex-conced min-mas problems, several variants have been developed by incorporating the idea of optimism; 29 The analysis of stochastic GDA in the manconve--stronge concave setting
see e.g., 7
28 Specifically, for stochastic GDA (SGDA), the O(e-2 sample complexity has been established in (8 under an increasing batch size ((e-1). As highlighted in (28), how to achieve the O sample complexity under an ((1) constant batch size
is closely related to this paper; e.g., g 10
30
3

---

remains open. The reduction of our results to the min-max setting will provide an answer to this open question. the same setting, accelerated GDA algorithms have been developed in [31 Going beyond the one-side concave settings, algorithms and their convergence analysis have been studied for conconvex-nonconcayy min-max problems with certain benign structure; see e.g., comparison of our results with prior work can be found in 2
36
Stochastic compositional optimization. Stochastic compositional gradient algorithms developed can be viewed as the alternating SGD updates (4) for the special compositional problem (3 However,
in 12 37
ensure convergence, the algorithms [12 37 use two sequences of variables being updated in two different time scales, and thus the complexity of [2] and [37 is worse than ( ?) of
SGD for the con-coopositional case. While most of existing algorithms rely on either two -reeiimee updates, the single-timen timescale single-loop approaches have been recently developed in [14] 38 [3]]
which achieve the sample complexity O same as SGD for the non-nested problems. However, the algorithms proposed therein are not the vanilla alternating SGD update in the sense of (4) Other
related compositional algorithms also include [40 42
A comparison can be found Table 3
Organization. The basic background of bilevel optimization is reviewed, and the tighter analysis of the unifying ALSET method is presented in Section 2 The reduction of the main results the
special stochastic nested problems is provided in Section 3 and its applications to the actor-critic method are discussed in Section followed by the conclusions in Section 5.
2 Improved Analysis of Alternating Stochastic Gradient Method
In this section, we will first provide background of bilevel problems and then introduce ALSET for stochastic nested problems.
2.1 Preliminaries
We use ||- || to denote the & norm for vectors and Frobenius norm for matrices. For convenience, we define the deterministic functions g(2, y) EEl1( yi o)] and f(x,, v) := Egg/(2, yı E)].
We also define V (z, as the Hessian matrix of with respect to y and define V 2zyg((,, (x,z) as
g v) 02.
0²
/² na. By. g (I.
2
Vayg(z,)) (z, y)
0² Begdy g x,
Segeng g( v)
We make the following assumptions, which are common in the bilevel optimization literature 16 18 26].
Assumption 1 (Lipschitz continuity). Assume that f. f.V.. Vg. V2g are respectively fy.0
lgi:kg,1 2 Lipschitz continuous: that for 21 := [01: v1).
22 := [22; V2l. we have f(1 y1)
f(22. U2)l < f,,0|l=1 22ll. f 31)
ff 42)ll I f,11
22ll. (g(211)1)
Vg(22, w2) || < f z2ll.
V ( v2) < -
-2 =2ll
Assumption (Strong convexity of g in y)- For any fixed a, g y) !lg-strongly convex in y-
Assumptions and 2 together ensure that the first- and second-order derivations of [ax g), y). as well the solution mapping y" (z), are well-behaved. Define the condition number k lg.1 Hgg Assumption (Stochastic derivatives). The stochastic derivatives Vf(x, y: E), Vg(2, ys Φ). V2g(z, y. Φ) are unbiased estimators of f y). Vg(z,y), V2 y), respectively; and their variances are bounded by o² 02.02 2222 respectively.
ALSET
SGDA
SMD
ALSET
SCGD
NASA
batch size
((1)
O(e"))
batch size y-update
O(1)
O(1)
O(1)
y-update
SGD
SGID
subproblem
SGD
SGD
correction
samples
Oks
OKEEE
Okke
samples
(
(
O(E-2)
Table 2: Sample complexity of stochastic min- max algorithms (BSA in [16], GDA in (28). SMD in [ achieve an c-stationary point of F(x).
Table Sample complexity of stochastic compo- sitional algorithms (SCGD in [12), NASA in [14)
achieve an e-stationary point of F(x).

---

Assumptions 2 and 3 together imply that the second moments are bounded by
E fz, yi [ - 1.0 + oj == C3
(5a)
Es || g(,, yr +) - G. + 0= Cg.
(5b)
Assumption 3 is the counterpart of the unbiasedness and bounded variance assumption in the single- level stochastic optimization. In addition, the bounded moments in Assumption ensure the Lipschitz
continuity of the upper-level gradient V2(x).
We first highlight the inherent challenge of directly applying the alternating SGD method to the bilevel problem (T). To illustrate this point, we derive the gradient of the upper-level function F(x) in the next proposition; see the proof in the supplementary document.
Proposition! 1. Under Assumptions 1-3, we have the gradients
V (z)) Vzf y" (z)) - V A y" (x)) y (z))
V (uf
(6)
Furthermore, (()) and y" (x) Lipschitz continuous with constants LF Ly. respectively.
Notice that obtaining unbiased stochastic estimate of F and applying SGD on face two main difficulties: i) the gradient V F Fxx) at x depends on the minimizer of the lower-level problem y" (ar); ii) even if y" (x) is known,
hard to apply the stochastic approximation obtain an unbiased estimate of (x)) since V Fx)) is nonlinear in V ( (x, y (xx).
18 17,, we evaluate FF(x) on a certain Similar to some existing stochastic bilevel algorithms 16
vector y in place of y² (ar). Replacing the y² (ax) in definition
6 by y. define
V (z, v) == V.. (.,((,,)) (x, 2 (x,
V Veg (x, VnJ v.d( (z.
And to reduce the bias in 7 we estimate [ my ( (z, y)]
via
N'
2 b (z, v)
N
II (1 [ - V vi
(8)
n.11
n=1
where N' drawn from {1, N) uniformly at random and {Ø(1) o(N') are i.i.d. samples. It has been shown in [16 that using (8). the estimation bias of [V] 1 u)] exponentially decreases with the number of samples N.
2.2 Main results: Tighter analysis of ALSET
In this subsection, we first describe the general ALSET algorithm for the stochastic bilevel problem, and then present its new convergence result.
Algorithm ALSET for the stochastic bilevel problem (1)
1: initialize: x² y, stepsizes (ax, 3x).
2:
for k= =, 1,..... ..... K - do
3:
for = 0, 1, 1..... T 1 do
This algorithm is very simple to im- plement. At each iteration k, ALSET alternates between the stochastic gra- dient update on I¹ and that on = Al- though is possible that T = 1, for generality, run T steps of SGD on the lower-level variable y before updating upper-level variable x² With ag and Br denoting the stepsizes of a and y² that decrease the same rate SGD, the ALSET update is
4:
update x - Bah
set yh: y set gh+l R.
5:
end for
6:
update 2: 2+41 = x onhy
7:
end for
y yht Bxhg t .....,T TT with R. = y := Y.T k+1 xx -
(9a)
(9b)
where the update direction of y is the stochastic gradient hikt = vgg(a* hhd, o+t");; ;; and, with the Hessian inverse estimator (8). the update direction of is the slightly biased gradient
hy = vv x k+1 5K)
N' II 9.1 n=l
Vayg(zz 8: o(
N
(I
V ga lepllltttttt.r/ ((tt)) yff(tt g+t), (10)
5

---

The alternating update serves as a template for running SGD on stochastic nested problems. As we will show in the subsequent sections, we can generate stochastic algorithms for min-max max, compositional, and even reinforcement learning problems following ( template, but they differ in the particular forms of the stochastic gradients h gg' 7 for the specific upper- and lower-level objective functions. See Algorithm Toor a summary of ALSET for the bilevel problem.
Comparison between ALSET with existing works. Readers who are familiar with recent develop- ments stochastic optimization for bilevel problems may readily recognize the similarities between the general ALSET update (I) that we will analyze and the
updates in BSA [[6,, TTSA 18 and StocBiO [7]. However, the update ① is different from BSA in that the number of y-update, denoted as T, is a constant in (T) that does not grow with the accuracy e e ; the update ①1 is different from StocBiO in that the stochastic gradient k. used in the y-update (9a) is obtained by fixed batch size that does not depend on the accuracy c= and, the update T is different from TTSA in that the stepsizes and 63 in (9) decrease at the same timescale.
We next present the convergence result of ALSET.
Theorem (Bilevel problems). Suppose Assumptions 1-3 hold. Define the constants as 16T (6TppLg.
á1 2Lr + , + 2 Lng7
022
(11)
(Bgg + (gg,+
where 1)
0 is a control constant that will be specified in each special case to achieve the best sample complexity. With > 0 being a control constant that will be specified later, choose the stepsizes as
By L + +2 03nn
a
Og min 01 022
and
O2--
(12)
VK
4T
For any T 2 and N = Oloo K). the iterates {at, ,y²} generated by Algorithm satisfy
1
2 V -0 and 1100-~"00 -10 0
(2
(13)
VK
where y (xx is the minimizer of the lower-level problem in (Tb).
Proposition 2. Under the same assumptions and the choice of parameters of Theorem 7 with
fa.1 being the condition number, select a = (0(==5/2) ) in 12) and then
2g
K-1
E
(14)
K F=D
K
VK
Discussion of Theorem 1 To achieve c-stationary point, we need K = ((n-c=2), and the number of evaluations of hyy had are (xx5E and (2) respectively. Therefore, the sample complexity is on the same order of SGD's sample complexity for the single-level nonconvex problems [43] and
improves the state-of-the-ar single-loop TTSA's sample complexity (522) [88] Compared to
[77, ALSET achieves the same sample complexity in terms of both and without using growing batch size. Importantly, we obtain this tighter bound without introducing additional assumptions.
2.3 Proof sketch
In this subsection, we highlight the key steps of the proof towards Theorem ! and highlight the differences between our analysis and the existing ones.
For simplicity, we define the following Lyapunov function as y : F(x") + Hy 1y* - 3 (x*))|1
We first quantify the difference between two Lyapunov functions as
L Ly
rk+ y = +() F(x*)
+
(11b k+1 - (x**11))) k+ 18 (2
(15)
Lemma
Lemma
The difference in (15) consists of two difference terms: the first term quantifies the descent of the overall objective functions; the second term characterizes the descent of the lower-level errors.
We will first analyze the descent of the upper-level objective in the next lemma.

---

Lemma (Descent of upper level). Suppose Assumptions 1-3 hold. Define h and |1bg f(*h +*+
= Bihy 12 ,
I]| - bg. The sequence of x² generated by Algorithm satisfies
ah E1I
a5
Lro
B[1b
+ + y (ar [13] + on + Leak
2 of
(16)
where constants Lf, Lp. 03 are defined Lemma of the supplementary document.
Lemma] Timplies that the descent of the upper-level objective functions depends on the error of the lower-level variable y². We will next analyze the error of the lower-level variable, which is the key step to improving the existing results.
Before we analyze the error of y², we introduce lemma that characterizes the smoothness of y (x) and the bounded moments of hty. The smoothness and the bounded moments have not been explored by previous analysis such [16. and they play essential role in our improved analysis of y*. Lemma 2 (Smoothness and boundedness). Under Assumptions I and 2, we have
Vy Vy (22)) S Lgnl|z z2l1;
1| b x C7
(17)
where Lyz and O7 depend on the constants defined in Assumptions 1-2.
Building upon Lemma 2 we establish the progress of the lower-level update.
Lemma (Error of lower level). Suppose that Assumptions 1-3 hold, and + is generated by running iteration 9
given æ². we choose Bk S Ny t.11' then y y satisfies
Ellly y" (x*")11
S (1 Bx) ( "Ell 3² (=(==)11)+ 11
T3300
(18a)
Ellly h+1 1f (a S (1 4L Lo0 + nyyn 03
a
B - y 11
2
(L3 4Lyas
Ly L Luz
)
(L2
Lyn 2n
(18b)
2n
where 1) 0 a fixed constant that will be chosen obtain the tighter complexity bound.
The improved analysis of the lower-level problem. Next we explain where we can obtain improved analysis. Plugging (18a) into (1b),, and selecting stepsizes a 3% properly, can show that
Flly y (a * 17 S (1 - 6, 6,)
(+*) 62 6 55Toy + 52σ3 (19)
where the constants are 81 E [0, 62 O(ax), 0633), O(a)). As we will show in our supplementary material, the term 11 will be canceled when combined with (16) in our
analysis. Hence, choosing ag = O(k-1/3)))))) 1/2) and 3g O(k 10(k-1/3) 1/2) makes the variance terms in (19 decrease the same Okk-1/2) 11/2)) rate as the vanilla SGD for stochastic non-nested problems.
As comparison, the progress of the lower-level problem in 18 17 can be summarized as
E|Iyy* 4+1 y" (a ++1 || < (1 - 6, B1) - (2 |1 630²
(20)
where o² is some variance term, and the constant is 6, = 0 - af/3.) or O(L/B²) with B being the batch size iteration k. To balance the two terms in 65 = 0 a two timescales of stepsizes limg-soo 0x/33 = 0 are needed, which will make the variance term of the y-update in (20) and that of the r-uudate (66) decrease two different rates, slower than that of SGD; and to reduce dz- = (11/ (11/Ba), growing batch size Bg (kk) is needed for the yuupate..
3 Applications to Stochastic Min-Max and Compositional Problems
Building upon the general results for the bilevel problems in Section this section will identify special features of the stochastic min-max and stochastic compositional problems, and eustomize the general results to yield ofth-of-the-art convergence results for two special nested problems.
7

---

3.1 Stochastic min-max problems
We first apply our results to the stochastic min-max
max problem 2 In this special case, the lower-level
function is g(x, 6) = ff E), and the bilevel gradient in 6 reduces to
VF(x)= == (I,
+ V Vzy (x) (, V=f(z,v"(T)
(21)
where the second equality follows from the optimality condition of the lower-level problem, i.e., V (x: y" (x)) = O. Similar to Section 2 we again approximate FF()) on certain vector y in
place of V (x). Therefore, the alternating stochastic gradients for this special case are given by
h b g
fx* ( and hy - vff("* y+t1,
(22)
Plugging the stochastic gradient into the general update (9), we summarize the update in Algorithm 2
When the number of y-update is T = the ALSET algorithm reduces to the SGDA method in [88
Proposition 3 (Min-max problems). Choose the same choice of parameters as those in Theorem
and follow the same assumption as those Theorem 7 exceept that f(-, y) is only Lipchitz over x F
but not that f(x,-) -) is Lipschitz continuous over y E R If we select a = O(K 1). T = (1)), 1j in 122 the iterates generated by Algorithm 2 satisfy
Σ
K-1
[|
E
0
K
(23)
K
K
K
Proposition implies that for the min- max problem, the convergence rate
Algorithm 2 ALSET for the min-max problem (2)
of ALSET to the stationary point of F(x) == max B&g [f; E)] is O(K-1/2). To achieve e-stationary point, we need K O(x2E-2). And the number of gradient evaluations for hy* are O(x2E 2) and O(x3 respectively. Comparing with the results in (28), we achieve the same sample com- plexity without an increasing batch size Oc- and improve their sample com- plexity (c-5/22 under fixed batch size. However, it is also worth mentioning that compared with 28 our analysis requires the additional Lipschitz continuity assumption of f(- v) over E Rd, which inherits from the analysis for the general bilevel problem. Therefore, our result complements, rather than improves, the analysis in (28)
1: initialize: x., y, stepsizes {as, 8k)
2:
for k == 0.1,.... K - 11--008 do
3:
set y yb
4: for tort=10 0,
T do
5:
update y v.
yht Br V v fx yht ef
6:
end for
7: set yー = yk.
8: update 2h+1 = x aa
V fz ,
9:
end for
We view our contribution in min-max problems as a supplementary of existing results.
3.2 Stochastic compositional problems
In this section, we apply results to the stochastic compositional problem B In this special case, the upper-level function is f(x, y: E) = fwy: E). and the lower-level function is g( yr Φ) lly h(:;; 12 and the bilevel gradient in (6) reduces
VF(x) : = Vzf(2,
22
(x)) g(,,
Vh(z;)) (V vz)((((x))
(24)
where we use the fact that V2 12, の) Laxar Vayg( = -Vh(:; σ) Similar to
Section 2 we again evaluate V Fzz) on certain vector in place of y" (x:). Therefore, by choosing T = 1, the alternating stochastic gradients h1,, h²t for this special case are much simpler, given by
hitt = h n* h(**; ;(=*:0") 9
o*) and h Vh(a":
(25)
Plugging the stochastic gradient into the general update 9.. we summarize the update in Algorithm 3 When T 1, the AL.SET algorithm reduces SCGD proposed in (12..
In the supplementary document, we have verified that the standard assumptions of stochastic compo- sitional optimization in 12 37
38 are sufficient for Assumptions 1-3 to hold.
8

---

Proposition 4 (Compositional problems), Under the same assumptions and the parameters as those in Theorem if we select T
1, a
1. Lus in 12 the iterates of Algorithm satisfy
K B V 0 K
A Algorithm ALSET for the compositional problem (3)
(26)
VK
1: initialize: x", 3d stepsizes {ak. 3k
2: for k= 0, K do
Since each iteration of ALSET only uses
3: update y² = y² (x* - h1*"; +)
((1) samples (see Algorithm 3.. Propo-
sition implies that the sample complex- 4: update x*+1 = x - ar V /
ity to achieve an c-stationary point of (3)
5: end for
is O Comparing with the results
of the SCGD method [12]. our result improves the sample complexity O under a fixed batch
size. Importantly, our analysis does not introduce additional assumption compared to 12]
4 Applications to Actor-Critic Methods
In this section, we apply our tighter analysis to the actor-critic (AC) method with linear value function approximation 44 which can be viewed as special case of the stochastic bilevel algorithm 45 46
Consider Markov decision process described by .M- AS P, R. 7), where S is the state space, A is the action space, PPs'|s (/, a) is the probability of transitioning to 8 E S given state & E S and action A, and R(ss a, s') is the reward associated with (s, a, 8'), and 7 [0, 1) is discount factor. For policy wo. define the value function V=, (5) that satisfies the Bellman equation 47
VTO (s) = (-1s),
[r(s, a, (V,
(27)
Given the state feature mapping (6)) S + Rd,, approximate the value function linearly as VTT (s) == d(s) y, where y E Rd is the critic parameter. The task of finding the best y such that Va (s) x Vi, (s) is usually addressed by TD learning [48].
Defining the stationary distribution induced by the policy parameter O2 as μay and the kth transition as & (sk= aks Sk+1), which is sampled from 5k ~ M0z: a The Sk+1 the TD-error is
8(E yk) = r(sk, ak. Sk+1) + 70(5u+1) - o(s)) yk
(28)
and the critic gradient (EK,,, yk) == 8(Ex, 3k Vi, (sk). We update the parameter y via
yk+1 = Hz, (yl- +
yk))
(29)
where && is the critic stepsize, and n, is the projection control the norm of the gradient. pre-defined constant R, will be specified in the supplementary document.
The goal of policy optimization is to solve maN F(0) with F(O)= == [Vro the initial distribution. Leveraging the value function approximation and the policy gradient theorem
where 17 is
49 we have the policy gradient (y, 0, v) = ô(g. v)vn(ss (8, a), which gives the policy update 0x+1 = 02 + anhy 0x, 1k+1),
(30)
where og is the stepsize and (8 a) = V log (uls). Note that the sample & = (s'6s ale (641) used in (30) is independent from Ex (29 Specifically, & sampled from s/g do,, dlz ~ Te. k+1 P with da, being the discounted state action visitation measure under 0z.
The alternating AC update 29
is special case of ALSET, where the critic update is the lower-level update, and the actor update is the upper-level update.
2 30
Due to space limitation, sentation of the proof and the corresponding assumptions, which are the counterparts of Assumptions 1-3 in the context of AC, to the supplementary document.
will directly present the results of the alternating AC next, and defer pre-
Theorem (Actor-critic). Under the some regularity conditions that are specified in the supplemen- tary document, selecting step size ag O(
(xR Bk O( }x), holds
1
VKk
+
Eapp
(31)
where Eapp- defined in the supplementary document, captures the richness of the linear function class.

---

Both sides of Theorem 2 As an application of our tighter analysis, Theorem 2 establishes for the first time that the sample complexity of the single-loop alternating actor-critic method is O(E 2). On the positive side, this new result improves the previous complexity ((c-b/2) for the single-loop AC [50], and (cc-2 log ! for the nested-loop AC [5]], and matches (cc-²) ) for AC with an exact critic oracle [52] In addition to using two independent samples, one limitation of our result is that inheriting from the analysis for the general bilevel case, our analysis of AC requires the smoothness of the critic fixed-point y" (0). As shown the supplementary document, this implicitly requires the additional bounded and Lipschitz continuity assumption on the stationary distribution poo The removal of this assumption and the extension to Markovian sampling are left for future research.
Preliminary Experiments
To validate our new theoretical results, we have conducted the simple experiment using the risk- averse portfolio management task on a benchmark dataset- 100 Book-to-Mann Market. This a typical
application of stochastic compositional optimization B that is used in 40 41. We compared the
popular two-timescale SCGD approach [12]
with our single-timescale ALSET approach.
y² We use the same initialization of x,,y" for
both SCGD and ALSET, and tune the step- sizes agg 3x by following the suggested or- der in the original SCGD paper and then using grid search for the multiplicative constant c, that
Iter k
lnk
SCGD
ALSET
ALSET-const
10
2.30
5.32
5.31
5.63
100
4.61
3.78
3.49
3.63
200
5.30
3.40
2.94
3.06
400
5.99
3.04
2.40
2.55
SCGD: 0% = ck-3/44 3x = ck-
1000
6.91
2.57
1.65
2.06
ALSET: ag = ck 1-, BB = 1/2
Table 4: Comparison of In( R Σ F[ among the two-timescale and single-timescale algorithms.
The constant c is chosen from the searching
grid (10-3, 5 x 10-1, 10-1) and is optimized for each algorithm in terms of ergodic average gradient norm versus the number of iterations. In Table 4 we report the logarithmic value of the average gradient norm performance of SCGD, ALSET with both the above decreasing stepsizes and ALSET- const with the constant stepsizes (replacing k with K 1000). Since SCGD and ALSET use the same number of samples and gradient evaluations per iteration, we report the progress in terms of iterations. By calculating the decay rate, we can observe that the empirical convergence rate of ALSET is worse than the theoretical rate D(k-1/3), and ALSET outperforms SCGD thanks its single-timg timesele stepsizes. We will pursue more comprehensive experiments in our future work.
Conclusions
This paper unifies several SGD-type updates for stochastic nested problems into single nested SGD approach that we term ALternating Stochastic gradient dEscen'T (ALSET) method, ALSET runs in the single-timescale and uses fixed batch size. This paper presents tighter analysis for using ALSET to solve stochastic nested problems. Under the new analysis, to achieve an e-stationary point of the nested problem, ALSET requires O(c-2) samples in total. As by- bropruct,,, this general result also improves the existing sample complexity of the min-max and compositional cases. It matches the sample complexity of SGD for single-level stochastic problems. Applying our analysis to an alternating version of the actor-critic algorithm also yields a state-of-the-art sample complexity.
Potential limitations of our results include additional assumptions in the min-max and actor-critic cases, which inherit from the assumptions of general bilevel problems. Nevertheless, our work can also lead to promising future research in understanding the theoretical performance of many successful empirical nested optimization algorithms. To this end, our future work consists of relaxing the regularity conditions needed to achieve our theoretical results and Possible extensions include applying our the tighter analysis in this paper to the existing two-timescale Hessian-frie -ree bilevel optimization algorithms and decentralized stochastic nested optimization algorithms.
Acknowledgements
The work T. Chen was partially supported by NSF Grant 2047177 and the RPI-IBM Artificial Intelligence Research Collaboration (AIRC). The work of Y. Sun was partially supported by ONR
10

---

Grant N000141712162 and AFOSR MURI FA9550-18-1-0500 We thank anonymous reviewers for their valuable feedback on improving the current paper.
References
[1] H. Robbins and S. Monro, "A stochastic approximation method," Annals of Mathematical Statistics, vol. 22, no. 3, pp. 400-407, Sep. 1951.
[2] C. Finn, P. Abbeel, and Levine, "Model-agnostic meta-learning for fast adaptation of deep networks," in Proc. Insl. Conf. Machine Learn.. Sydney, Australia, Jun. 2017, pp. 1126-1135.
[3] L. Franceschi, P. Frasconi, S. Salzo, R. Grazzi, and M. Pontil, "Bilevel programming for hyperparameter optimization and meta-learning." in Proc. Inil. Conf. Machine Learn., Vienna, Austria, Jun. 2018, pp. 1568-1577.
[4] B. Colson, P. Marcotte, and G. Savard, "An overview of bilevel optimization," Annals of operations research, vol. 153, no. 1, pp. 235-256, 2007.
[5] G. Kunapuli, K. P. Bennett, J. Hu, and J.-S. Pang, "Classification model selection via bilevel programming." Optimization Methods Software, vol. 23, no. 4, pp. 475-489, 2008
[6] S. Dempe and A. Zemkoho, Bilevel Optimization. Springer, 2020.
[7] C. Daskalakis and I. Panageas, "The limit points of (optimistic) gradient descent in min-max optimization."" in Proc. Advances in Neural Info. Process. Syst., Montreal, Canada, Dec. 2018, pp. 9256-9266.
[8] G. Gidel, H. Berard, G. Vignoud, P. Vincent, and S. Lacoste-Julien, "A variational inequality perspective on generative adversarial networks," in Proc. Intl. Conf. Learn. Representations, Vancouver, Canada, Apr. 2018.
[9] H. Rafique, M. Liu, Q. Lin, and T. Yang. "Non-convex min-max optimization: Provable algorithms and applications in machine learning," Optimization Methods and Software, Mar. 2021.
[10] K. K. Thekumparampil, P. Jain, P. Netrapalli, and S. Oh, "Efficient algorithms for smooth minimax optimization," in NeurlPS, Vancouver, Canada, Dec. 2019.
[11] A. Mokhtari, A. Ozdaglar, and S. Pattathil, "A unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach," in Proc. Intl. Conf. on Artif. Intell. and Stat., Palermo, Italy, Aug. 2020, pp. 1497-1507.
[12] M. Wang. E. X. Fang, and H. Liu, "Stochastic compositional gradient descent: algorithms for minimizing compositions of expected-value functions," Mathematical Programming, vol. 161, 1-2, pp. 419 449, Jan. 2017.
[13] B. Dai, N. He, Y. Pan, B. Boots, and L. Song, "Learning from conditional distributions via dual embeddings." in Proc. Intl. Conf. on Artif. Intell. and Stat., Fort Lauderdale, FI., Apr. 2017, pp. 1458-144 1467.
[14] S. Ghadimi, A. Ruszczynski, and M. Wang. "A single timescale stochastic approximation method for nested stochastic optimization," SIAM Journal on Optimization, vol. 30, no. 1, pp. 960-979, Mar. 2020.
[15] K. Ji, J. Yang, and Y. Liang "Multi-step model-agnostic meta-learning: Convergence and improved algorithms," arXiv preprin::2002.078366 Feb. 2020.
[16] S. Ghadimi and M. Wang, "Approximation methods for bilevel programming," arXiv preprint:1802.00 022.6000.2222.2222 2018.
[17] K. J. Yang, and Y. Liang, "Provably faster algorithms for bilevel optimization and applications to meta-learning."" in Proc. Intl. Conf. Machine Learn., Virtual, Jul. 2021.
11

---

[18] M. Hong, H.-T. Wai, Z. Wang, and Z. Yang. "A two-timescale framework for bilevel opti- mization: Complexity analysis and application actor-critic," arXiv preprint:2007.05577 057000 2020.
[19] T. Chen, Y. Sun, and W. Yin, "A single-timescale stochastic bilevel optimization method," arXiv preprint arXiv:2102.046) 2021.
[20] H. V. Stackelberg, The Theory of Market Economy. Oxford University Press, 1952.
[21] Sabach and S. Shtern, "A first order method for solving convex bilevel optimization problems." SIAM Journal on Optimization, vol. 27, no. 2, pp. 140-660, 2017.
[22] A. Shaban, C.-A. Cheng, N. Hatch, and B. Boots, "Truncated pack-propagation for bilevel optimization," in Proc. Intl. Conf. on Artif. Intell. and Stat., Naha, Okinawa, Japan, Apr. 2019, pp. 1723-1732.
[23] R. Grazzi, L. Franceschi, M. Pontil, and S. Salzo, "On the iteration complexity of hypergradient computation," in Proc. Intl. Conf. Machine Learn., virtual, Jul. 2020, pp. --5588.
[24] R. Liu, P. Mu, X. Yuan, S. Zeng, and Zhang, "A generie first-order algorithmic framework for bi-level programming beyond lower-level singleton," in Proc. of International Conference Machine Learning, Virtual, July 2020, pp. 6305-6315.
[25] P. Khanduri, S. Zeng, M. Hong, H.-T. Wai, Z. Wang. and Z. Yang. "A momentum-assisted single-timescale stochastic approximation algorithm for bilevel optimization," " arXiv preprint arXiv:2102.07367, Feb. 2021.
[26] Z. Guo and T. Yang, "Randomized stochastic variance-reduced methods for stochastic bilevel optimization." arXiv preprint arXiv:2105.02266 May 2021.
[27] J. Yang, K. Ji, and Y. Liang. "Provably faster algorithms for bilevel optimization." arXiv preprint arXiv:2106. 04692, Jun. 2021.
[28] T. Lin, C. Jin, and M. Jordan, "On gradient descent ascent for nonconvex-concave minimax problems," Proc. Intl. Conf. Machine Learn., virtual, Jul. 2020, pp. 6083-6093.
[29] T. Yoon and E. K. Ryu, "Accelerated algorithms for smooth convex-concave minimax problems with O(1/k²) rate on squared gradient norm," in Proc. Intl. Conf. Machine Learn., Virtual, Jul. 2021.
[30] M. Nouiched, M. Sanjabi, T. Huang, J. D. Lee, and M. Razaviyayn, "Solving class of non- convex min-max games using iterative first order methods," " in Proc. Advances in Neural Info. Process. Syst., Vancouver, Canada, Dec. 2019, pp. 14934-14942.
[31] L. Luo, H. Ye, Z. Huang, and Zhang, "Stochastic recursive gradient descent ascent for stochastic mmmconvex-strongly-coom Process. Syst., Virtual, Dec. 2020.
minimax problems," in Proc. Advances in Neural Info.
[32] Y. Yan, Y. Xu, Q. Lin, W. Liu, and T. Yang, "Optimal epoch stochastic gradient descent ascent methods for min-mat optimization," Proc. Advances in Neural Info. Process. Syst., vol. 33, Dec. 2020.
[33] Q. Tran Dinh, D. Liu, and L. Nguyen, "Hybrid variance-reduced sgd algorithms for minimax problems with nonconvex-lineal function," in Proc. Advances in Neural Info. Process. Syst., Virtual, Dec. 2020.
[34] M. Liu, Y. Mrouch, J. Ross, W. Zhang, X. Cui, P. Das, and T. Yang, "Towards better understand- ing of adaptive gradient algorithms in generative adversarial nets," in Proc. Intl. Conf. Learn. Representations, Virtual, Apr. 2020.
[35] J. Yang, N. Kiyavash, and N. He, "Global convergence and variance reduction for a class of nonconvex--onnconcaee minimax problems," in Proc. Advances Neural Info. Process. Syst., Virtual, Dec. 2020.
12

---

[36] J. Diakonikolas, C. Daskalakis, and M. Jordan, "Efficient methods for structured nonconvex nonconcave min-max optimization," in Proc. Intl. Conf. on Artif. Intell. and Stat., Virtual, Apr. 2021.
[37] M. Wang, J. Liu, and E. Fang, "Accelerating stochastic composition optimization," Journal Machine Learning Research, vol. 18, no. 1. pp. 3721-3743 2017.
[38] T. Chen, Sun, and W. Yin, "Solving stochastic compositional optimization nearly easy as solving stochastic optimization." IEEE Trans. Sig. Proc., vol. 69, Aug. 2021.
[39] A. Ruszezynski, "A stochastic subgradient method for nonsmooth nonconvex multi-level com- position optimization." " arXiv preprint:2001.10669, Jan. 2020.
[40] X. Lian, M. Wang, and Liu, "Finite-sum composition optimization via variance reduced gradient descent," in Proc. Intl. Conf. on Artif. Intell. and Stat., Fort Lauderdale, FL, Apr. 2017.
[41] J. Zhang and L. Xiao, "A stochastic composite gradient method with incremental variance reduction," " in Proc. Advances in Neural Info. Process. Syst., Vancouver, Canada, Dec. 2019.
[42] Q. Tran-Dinh, N. Pham, and Nguyen, "Stochastic gauss-newton algorithms for nonconvex compositional optimization," in Proc. Intl. Conf. Machine Learn., Virtual, Jul. 2020.
[43] S. Ghadimi and G. Lan, "Stochastic first-and zeroth-order methods for nonconvex stochastic programming." SIAM Journal on Optimization, vol. 23, no. pp. 2341-2368, 2013.
[44] V. Konda and V. Borkar, -Actor-critic-tppe learning algorithms for markov decision processes." SIAM Journal on Control and Optimization, vol. 38, no. 1, pp. 94-123, 1999.
[45] J. Wen, S. Kumar, R. Gummadi, and D. Schuurmans, "Characterizing the gap between actor- critic and policy gradient," in Proc. Intl. Conf. Machine Learn., Virtual, 2021.
[46] L. Zheng, T. Fiez, Z. Alumbaugh, B. Chasnov, and L. J. Ratliff, "Stackelberg actor-critic: Game-theoretic reinforcement learning algorithms," arXiv preprint arXiv:2109. 12286, 2021.
[47] R. S. Sutton and A. G. Barto, Reinforcement learning: An introduction. MIT Press, 2018.
[48] R. Sutton, "Learning to predict by the methods of temporal diffcrences." Machine Learning, vol. 3, pp. 9-44, 1988.
[49] R. Sutton, D. McAllester, S. Singh, and Y. Mansour, "Policy gradient methods for reinforcement learning with function approximation." in Proc. Advances in Neural Info. Process. Syst., 2000.
[50] Y. Wu, W. Zhang, P. Xu, and Q. Gu, "A finite time analysis of two time-scale actor critic methods," in Proc. Advances in Neural Info. Process. Syst., 2020.
[51] Xu, Z. Wang, and Y. Liang, "Improving sample complexity bounds for (natural) actor-critic algorithms," in Proc. Advances in Neural Info. Process. Syst., 2020.
[52] Z. Fu, Z. Yang, and Z. Wang, "Single-timescale actor-critic provably finds globally optimal policy," in Proc. Intl. Conf. Learn. Representations, 2020.
[53] Y. Nesterov, Introductory Lectures on Convex Optimization: A basic course. Berlin, Germany: Springer, 2013, vol. 87.
[54] Bhandari, D. Russo, and R. Singal, "A finite time analysis of temporal difference learning with linear function approximation." in COLT, 2018
[55] T. Xu, Z. Wang, Y. Zhou, and Y. Liang, "Reanalysis of variance reduced temporal difference learning," " in Proc. Inil. Conf. Learn. Representations, 2020.
[56] K. Zhang, Koppel, H. Zhu, and T. Başar, "Global convergence of policy gradient methods to (almost) locally optimal policies," arXiv preprint: 190.::t::9900088888. 2019.
[57] A. Agarwal, S. M. Kakade, J. D. Lee, and G. Mahajan, "Optimality and approximation with policy gradient methods in markov decision processes." Proc. Thirty Third Conference on Learning Theory, 2020.
13

---

[58] K. Doya, "Reinforcement learning in continuous time and space." Neural Computation, vol. 12,
no. pp. 219-245, 2000.
[59] Baxter and Bartlett, "Infinite-horizon policy-gradient estimation," J. Artificial Intelligence Res., vol. 15, pp. 319-350, 2001.
[60] A. Y. Mitrophanov, "Sensitivity and convergence of uniformly ergodic markov chains," Journal of Applied Probability, vol. 42, no. 4, pp. 1003-1014, 2005.
[61] S. Qiu, Z. Yang. J. Ye, and Z. Wang, "On the finite-time convergence of actor-critic algorithm." " in Optimization Foundations for Reinforcement Learning Workshop at Advances in Neural Information Processing Systems, 2019.
14


Reviews:
[{"review_id": "p4Nxp6d9dew", "reviewer": "Reviewer_PMym", "summary": "This paper studies the problem of solving a stochastic bilevel optimization problem, where the upper level optimization problem depends on the solution of the lower level optimization problem. The authors show that this stochastic bilevel optimization problem covers three different classes of problems (stochastic compositional, min-max, and bilevel optimization). The authors then unify the three SGD-type methods for the respective problems into a single approach called ALSET. Besides, compared with previous work, they also improve the sample complexity from $\\mathcal{O}(\\epsilon^{-2.5})$ to $\\mathcal{O}(\\epsilon^{-2})$. ", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I found the manuscript to be clearly written and technically sound. The proposed algorithms are also easy to understand. The authors give a detailed comparison between their result and previous results, where the improvement in the sample complexity is clearly stated. The only suggestion I have is can you also provide some numerical experiments to support your theoretical results? ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There is no negative societal impact. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2 hrs"}, "extra_text": {}}, {"review_id": "g801np4l5Wa", "reviewer": "Reviewer_vxWe", "summary": "This paper studies the altenating gradient descent method for stochastic nested problems.  It uses a general framework which contains the compositional gradient descent, the minimax problem, and the actor-critic method. It also provides a tighter analysis of the convergence result and better convergence rates in many cases.", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The contributions of the work is mainly theoretical.  Although the proof technique is fairly standard, it achieves better rates with a simple single-simescale algorithm. This work also points out the importance of the hidden smoothness of the optimizer of the lower level. It can be very important for further works in the field. The general framework allows us to easily generalize different variants of gradient descent methods to different settings. As a result, there are many possible lines of research following this work.\n\nThe paper is clearly written and the results are well-organized. Previous works are cited properly.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors addressed the limitations adequately. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "GQb4uAgxs-", "reviewer": "Reviewer_WgWk", "summary": "The paper proposes a tighter analysis of the complexity of alternating gradient descent on stochastic bilevel optimization problems. The tighter analysis is then applied on several nested optimization problems like min-max optimization, compositional problems as well as actor critic methods for MDP problems. A key step in the analysis is leveraging the smoothness of the lower optimization problem with respect to the decision variables of the upper level problem.", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall I think the paper is well written and the idea of proposing a unified analysis for all the optimization problems discussed in this work can have significant impact. Also closing the gap between the complexity of simple SGD and bilevel optimization is definitely important in the process of delineating which aspects of bilevel optimization are actually hard.\n\nWhile the smoothness of the lower level problem has been used in prior work (e.g. [27]), it is the smoothness of the gradients proved in Lemma 2 that opens the way to the improved rate. While Lemma 2 itself is rather straightforward to prove,  how and why it can be used in the proof is definitely not. Small tweaks to existing approaches are not sufficient for the reasons summarized under Equation 20. I suggest to the authors to expand more on this reasons in the Appendix to make the paper more self contained. \n\nOverall a very strong and well written submission.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations and negative social impact are adequately discussed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "GOPR-O52PAs", "reviewer": "Reviewer_TdaR", "summary": "This paper considers the problem of stochastic nested optimization which unified the stochastic compositional optimization and stochastic min-max optimization. It presents a tighter theoretical analysis for classical algorithm which uses vanilla SGD-type update. The sample complexity of this improved analysis matches those with modifications. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper is well-written. I have some comments below.\n\n1. This paper improves the sample complexity for SGD-type algorithms to solve stochastic nested optimization. The algorithm and some results (like observation (6) and estimation (8)) are already presented in previous literature (e.g., Ghadimi and Wang (2018)). Theorem 1 gives a tighter bound of such algorithm where they utilize the observations in Lemma 2. The authors give a clear presentation of their technique and highlight the key steps of the proof towards Theorem 1. However, it is my understanding that the novelty of this paper is merely the observation of lemma 2 and the tighter analysis following it.\n\n2. Under the unified structure, they extend their theoretical results to stochastic compositional optimization as well as stochastic min-max optimization. They also give an application example of the actor-critic method with linear value approximation.\n\n3. However, this paper is not complete. A conclusion part should be presented.\n\nReferences mentioned above:\n\n1. Ghadimi, Saeed, and Mengdi Wang. \"Approximation methods for bilevel programming.\" *arXiv preprint arXiv:1802.02246* (2018).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "None.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: It is the consensus of the reviewers that this paper makes a worthwhile contribution to stochastic optimization. The analysis of alternating gradient descent is tight. The implications of the analysis on stochastic compositional, min-max, and bilevel optimizations are interesting and useful.
Decision: Accept (Spotlight)