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": "yRaUucka9JF", "reviewer": "Reviewer_r5Xc", "summary": "The author derives a general algorithm framework applicable to minmax, composition, and bi-level optimization. The convergence rates are improved for different classes by leveraging the hidden smoothness of the problem. This paper is well organized and easy to understand. The author illustrates the difficulty of the problem, and the proof sketch is clear enough. The author also applies the algorithm to the policy gradient reinforcement method and provides its convergence.\n\n", "questions": "", "limitations": "", "rating": 6, "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": "Strengthens:\n   Please refer to the summary.\n\nWeakness:\n   1) Compared with STABLE, the inner loop for updating $y$ can not be ignored for ALSET as the $\\kappa$ is large.\n   2) Also the author doesn't mention the gradient evaluation complexity comparison between STABLE and ALSET in terms of $\\kappa$ which can usually not be ignored.\n   3) Even simple linear experimentation in terms of the sample complexity/gradient evaluation vs loss would be helpful to better understanding the benefits of ALSET.\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3-4"}, "extra_text": {}}, {"review_id": "xVmjM4xtJ8y", "reviewer": "Reviewer_tqUa", "summary": "This paper presents an improved sample complexity analysis for a stochastic bilevel (or nested) optimization algorithm. \n\nBilevel optimization consists in two nested optimization problems: the upper-level aims at minimizing an objective function where some of the variables are a solution of the lower-level problem. In the stochastic setting, upper and lower-level objectives are not accessible and are instead replaced by unbiased estimators. In addition to several smoothness assumptions, this work and several recent others consider the case when the lower-level problem is strongly-convex, which guarantees that the lower-level solution is unique, the existence of the upper-level gradient, and allows to provide convergence guarantees to stationary points even when the lower-level solution is not computed exactly. \n\nThis work studies a double loop algorithm which applies the vanilla stochastic gradient method at the upper and lower levels for $K$ and $T$ steps respectively. In addition, to compute the upper-level gradient, the lower-level hessian inverse is computed with an estimator whose bias decreases exponentially with the number ($N$)  of stochastic hessian samples and the lower-level starting point for the stochastic gradient method is the lower-level approximate solution at the previous upper-level iteration (warm-start). This algorithm is quite simple and is commonly used in practice.\n\nThe improved analysis yields a sample complexity of $O(\\epsilon^{-2})$ even when $T=1$ without using momentum, variance reduction, exact hessian inversion, or big batch sizes, which are instead needed by previous work to achieve the same or better complexity (the best-known complexity is $O(\\epsilon^{1.5})$ using variance reduction and additional assumptions). The authors further show that using their analysis one can recover the best-known complexity in 3 special bilevel problems: stochastic min-max, compositional and actor-critic.", "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": "Since the authors included the main paper in the supplementary I will refer to the line numbers of the supplementary throughout the whole review.\n\n#### **Originality**\n1. Several works have recently tackled the complexity of (stochastic) bilevel optimization with smooth objectives and strongly convex lower-level problem. This work demonstrates $\\tilde{O}(\\epsilon^{-2})$ sample complexity for a widely used algorithm consisting in stochastic gradient descent applied to solve both the upper and the lower level problems and is the first to do so with $O(1)$ batch size. The authors state clearly the contributions of the work and how they differ from previous ones (see e.g. line 195). The authors also specialize their theoretical results to 3 particular bilevel problems: stochastic min-max, compositional and actor-critic, recovering the best-known complexity, which is something that I have not seen in recent related work.\n\n#### **Quality**\n2. The theoretical claims are well supported: the proofs for the bilevel optimization part seem sound except for one issue which can probably easily be solved (see the first major comment). \n3. This work and related ones lack a more detailed discussion on the assumptions which it looks like they can be too restrictive in some cases unless the optimization problem(s) is over a convex compact set, a setting which this work does not cover. \n4. An additional limitation of the work (and of other related works) which is not emphasized by the authors is that the step-sizes ($\\alpha_k$ and $\\beta_k$) suggested by theory have to be tailored carefully based on the total number of iterations, on the unknown constants of the problem, and may be too small in practice. Comments on this, experiments showing how to choose step-sizes in practice and a comparison between the single timescale step sizes of this work and the two-timescale ones of the previous analysis could add value to the paper.\n5. I did not check the supplementary material relative to the 3 special cases but the claims in the main paper seem correct except for one problem for the min-max setting (see point 8 in the main review).\n\n#### **Clarity**\n6. The paper is clearly written and the proofs are easy to follow for someone acquainted with recent works in bilevel optimization theory. However, the work could benefit from simple examples of bilevel optimization problems that could make it more accessible to people less familiar with the topic.\n\n#### **Significance**\n7. Bilevel optimization is becoming more and more relevant in machine learning since many problems like instances of meta-learning and hyperparameter optimization can be cast into this framework. This work shows that an algorithm which is commonly used in practice matches the best known complexity. This result theoretically justifies the use of such an algorithm and thus is of great significance to the machine learning community.\n\n#### **Major comments**\n8. RHS of eq. (48)  should be multiplied by 2. Consequently RHS of (51) is also multiplied by 2 and the final bound in Lemma 3 changes. I think this breaks the proof of Theorem 1 but the Young inequality at line 580 can be changed to make things work again. Constants will change but the all claims will remain valid.\n\n9. Line 276: I think the assumption that $f(x, \\cdot)$ is lipschitz continuous breaks the theory for the min-max case. Since the theory does not deal with  constrained optimization on the lower-level variable $y$, $g = - f$ and $g(x, \\cdot)$ is strongly convex then $f(x, \\cdot)$ is strongly concave and lipschitz smooth over all $\\mathbb{R}^{d'}$ although no such function exists. It could be interesting to consider constrained optimization (where these properties are only required in a limited domain) either in the lower-level or upper-level problem to tackle this issue.\n\n10. I believe that the complexity for bilevel optimization should be up to logarithmic terms since to compute the hessian estimator $N = O(\\log(1/\\epsilon^2))$ samples are used for each upper-level iteration. The authors report the big O complexity without tilde instead.\n\n#### **Minor Comments**\n11. Line 102: the cited work [16] has a higher $O(\\epsilon^{-3})$ sample complexity.\n12. $N$ is not set in the statement of Theorem 1\n13. $\\alpha$ not defined in the definition of $\\alpha_k$ in eq. (12).\n14. Probably $\\alpha$  in line 6 of algorithm 1 should be $\\alpha_k$\n\n#### **Post Rebuttal**\nI am satisfied with the author response and keeping my positive score.\n\n#### **References**\n[16] S. Ghadimi and M. Wang, “Approximation methods for bilevel programming,” arXiv preprint:1802.02246, 2018.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The author discuss a limitation of the work in the conclusion. I pointed out other limitations that I think should be addressed at point 3 and 4 of the main review.\n\nThe authors justify the absence of a discussion about potential negative societal impact writing in the checklist that the nature of the work is theoretical. I agree with the authors.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "12"}, "extra_text": {}}, {"review_id": "k86xAmPqJA", "reviewer": "Reviewer_wdT9", "summary": "The paper introduces a new analysis of a stochastic gradient method, ALSET, for bilevel problems. It shows the convergence rate $O(\\epsilon^{-2})$ for finding an approximate stationary point. The results further implies the same convergence rate in minimax, compositional optimization and actor-critic method. ", "questions": "", "limitations": "", "rating": 6, "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": "$\\textbf{Originality}$: The analysis of this algorithm is new and original. \n\n$\\textbf{Quality}$: All claims are supported by sound proofs. Please see the questions and concerns below. \n\n$\\textbf{Clarity}$: The paper is clear and well organized. I suggest the author to mention the assumptions (such as strong-convexity in the lower level) in the abstract or early stage of the introduction. \n\n$\\textbf{Significance}$: Since stochastic gradient methods are simple and popular, I believe that this work will have some impacts by providing the theoretical ground to this method in the bilevel optimization. \n\n$\\textbf{Concerns}$: \n1. I think one of the drawback of the algorithm is that it still needs two loops. Only in the compositional problem, it can be reduced to one-loop algorithm, since the lower level is well-conditioned. The sentence in line 58 might be a little misleading. The algorithm in this paper can get rid of large batch size and increasing inner loop number, but not two loop structure. It still remains an open question what would happen if we only do one step for the lower level in each iteration. \n2. The algorithm requires to prefix the total number of iterations $K$. Is there anyway to use decreasing stepsize so that we do not need to pre-set $K$?\n3. The analysis in the paper is neat due to the discovery of smoothness of $y^*(x)$. However, in the discussion of actor-critic method, the authors directly assuming $y*(\\theta)$ to smooth, which a limitation. Also, in the minimax optimization, compared with other work, it additionally assumes the Lipchitz of the function, which might reduce the difficulty of the question greatly. \n4. In line 6 of Algorithm 1, $\\alpha$ should be $\\alpha_k$. \n\n\n=============after rebuttal===============\nThanks the authors for replying my questions. I am satisfied with the answer. I realize the authors use two-loops to achieve better dependency in the condition number. Would it be better if the author can also provide comparison of dependency of $\\kappa$ in the table for bilevel problems?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "DL4KJLoSkn6", "reviewer": "Reviewer_b2gP", "summary": "The paper improves the sample complexity of alternating SGD in the classes of stochastic nested optimization and show that the new complexity results are better than existing methods in the three settings. The new results rely on a smoothness property on the smoothness of  $y^*(x)$.", "questions": "", "limitations": "", "rating": 6, "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": "The paper is well-written and easy to follow. The comparison with related methods in Table 1-3 help clarify the significance of the improved results. The techniques used to improve the convergence results are new.\n\nI have the following comments on the theoretical results in the paper:\n- The advantage in min-max problem is unclear since ALSET require additional Lipschits continuity while two-time-scale GDA use increasing batch size.\n- Can the results on for other function other than quadratic in the compositional setting? Claiming advantages in this results compared with SCGD and NASA is not really fair since SCGD and NASA consider general g function.\n\nTherefore, the advantages of the new analysis can be mostly seen in the bilevel setting which reduce the significance of the paper.\n\n\n=======================Update==========================\n\nAfter reviewing the authors response, I have updated my score.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have adequately mentioned the limitation of the work. It would be better to emphasize the difference in analysis of ALSET in compositional problems since it considers a special case rather than the more general case in existing methods.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "20"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper unifies several SGD-type updates for stochastic nested problems into a single nested SGD approach and presents a tighter sample complexity analysis that improves or matches the existing results. All reviewers give positive evaluation on this paper. So do I. Please update the final version according to the reviewers’ feedback. For example, I think it is necessary to provide comparison of dependency of kappa in the table for bilevel problems.
Decision: Accept (Spotlight)