A Single-timescale Analysis for Stochastic Approximation with Multiple Coupled Sequences
Authors: Han Shen
Tianyi Chen
Venue: NeurIPS 2022 Accept (2022)

Abstract: Stochastic approximation (SA) with multiple coupled sequences has found broad applications in machine learning such as bilevel learning and reinforcement learning (RL). In this paper, we study the finite-time convergence of nonlinear SA with multiple coupled sequences. Different from existing multi-timescale analysis, we seek scenarios where a fine-grained analysis can provide a tight performance guarantee for single-timescale multi-sequence SA (STSA). At the heart of our analysis is the smoothness property of the fixed points in multi-sequence SA that holds in many applications. When all sequences have strongly monotone increments, we establish the iteration complexity of $\mathcal{O}(\epsilon^{-1})$ to achieve $\epsilon$-accuracy, which improves the existing $\mathcal{O}(\epsilon^{-1.5})$ complexity for two coupled sequences. When the main sequence does not have a strongly monotone increment, we establish the iteration complexity of $\mathcal{O}(\epsilon^{-2})$. We showcase the power of our result by applying it to stochastic bilevel and compositional optimization problems, as well as RL problems, all of which recover the best known or lead to improvements over their existing guarantees.

A Single-Timescale Analysis for Stochastic Approximation with Multiple Coupled Sequences
Han Shen
Tianyi Chen Rensselaer Polytechnic Institute Troy, NY 12180, United States thentiany119ggmi com
Rensselaer Polytechnic Institute Troy, NY 12180, United States shenh5@rpi.edi
Abstract
Stochastic approximation (SA) with multiple coupled sequences has found broad applications in machine learning such as bilevel learning and reinforcement learning (RL). this paper, we study the finite-time convergence of nonlinear SA with multiple coupled sequences. Different from existing multi-timescale analysis, we seek for scenarios where a fine-grained analysis can provide the tight performance guarantee for single-timescale multi-sequence SA (STSA). At the heart of our analysis is the smoothness property of the fixed points in multi-sequence SA that holds in many applications. When all sequences have strongly monotone increments, we establish the iteration complexity (( to achieve e-aceuracy, which improves the existing O(e 1.5) complexity for two coupled sequences. When the main sequence does not have strongly monotone increment, we establish the iteration complexity of O()-2). We showcase the power of our result by applying it to stochastic bilevel and compositional optimization problems, as well RL problems, all of which lead to improvements over their existing guarantees.
Introduction
Stochastic approximation (SA) an iterative procedure used find the zero of function when only the noisy estimate of the function is observed. Specifically, with the mapping Rd + IRd, the single-sequence SA seeks solve for v(x) 0 with the following iterative update:
Tk+1
xA + (v(x)) + Ex),
(1)
where ag the step size and & is random variable. Since its introduction in 466] single-sequence SA has received great interests because of its broad range of applications to areas including stochastic
optimization and reinforcement learning (RL) G 53). The asymptotic convergence of single-sequence SA can be established by the ordinary differential equation method; see e.g., [4]. To gain more insights into the performance difference of various stochastic optimization algorithms, the hnite-time convergence of SA has been widely studied in recent years; see e.g., 43 42 30
(50 (4 52 [3]
While most of the SA studies focus the single-sequence case, the double-sequence SA was introduced in (3) which has been extensively applied to the RL methods involving double-sequence
stochastic update structure [53 32 10) With mappings v de Rd + Rd and h Rd R41
dd the double-sequence SA seeks to solve v(x, y) = h( 3) = O with the following update:
Jt+1 = IĄ (u( 9k) Ek),
(2a)
3k+1 = + (h( vv) + vx).
(2b)
where o4k Ae are the step sizes, and Ék, the are random variables. In (2) the update of 24. and that of depend on each other and thus the sequences are coupled. To analyze (2) one natural thought stack (Ix. yie into larger variable and then resort to the celebrated single-sequence
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

SA analysis [46]. However, it can be seen later that the assumptions required for convergence of this virtual single sngle-sequence SA will be violated in many applications and the two sequences may be updated in an alternating rather than simultaneous fashion, both of which motivate new analysis for double-sequence SA. Due to the coupling, the double-sequence SA is more challenging to analyze than its single-sequence counterpart.
Prior art on double-sequence SA. Many recent analyses of the double-sequence SA focus on the linear case where v(z, y) and h(z, y) are linear mappings; see e.g., 34
25 29]. The key idea here is to use the so-called two-time-scale (TTS) step sizes: One sequence updated in the faster time scale while the other is updated in the slower time scale; that is lime-+ 0u/ Sxx = O. By doing so, the two sequences are shown to decouple asymptotically, which allows us to leverage the analysis of the single-sequence SA. In particular, [29] proves an iteration complexity of O
to achieve e-accuracy for the TTSS linear SA, which is shown to be tight. With similar choice of the step sizes, the TTS nonlinear SA was analyzed in 39 12.. In [39, the finite-time convergence rate of TTS nonlinear SA was established under an assumption that the two sequences converge asymptotically. Later, this assumption has been relaxed in [22 which shows that TTS nonlinear SA achieves an iteration complexity of (ee--15)) However, this iteration complexity is larger than O ((E-)) of the TTS linear SA. The single time-scale step sizes have also been explored in [37 44), but the enabling factor in those works is the vanishing variance by incorporating variance- variance-reduction reduction update or increasing batch size. While this work and those in Table focus on the case where the variance is non-decreasing.
The gap between the complexities of nonlinear and linear SA motivates an interesting question:
Q1: Is it possible to prove faster rate for the nonlinear SA with two coupled sequences?
We first conduct an experiment to examine the possibility. Experiment. Figure I shows the performance of using the
double-sequence SA 2 solve the following problem
Averaged Optimality Gap
10
1/ ( +
max SE
1 -te-v((x)
2
s.t. y² (x) = arg min (y xT)2. yER 2
10
single time-scale SA
We use the double-sequence SA solve 3).
where
10
10
10'
10"
() - e-+e- (x.y) =
(4)
Iteration k
Figure 1: Solving
with double-
and (R. E are independent Gaussian random variables with mean and standard deviations of 0.15. It is easy to check that (4) satisfies the assumptions in the existing TTS-SA analysis [12). Therefore, we can use the two time-scale step sizes and achieve the iteration complexity of O(E-1.)). However, as suggested by Figure I the iterates still converge with step sizes in a single time-scale
sequence nonlinear SA (2). The single time-scale nonlinear SA converges with a rate of O(k-1), which is faster than the theoretical O(k 3 rate in [1]
(ag: = O ) 8g = of double-sequence linear SA (29]. This suggests that existing analysis of double-seueenc SA might not be tight, at least for the class of updates similar to (4. Indeed, as we will show later, the iterates
O )) In this case, the iteration complexity O(e-1), which the same as that
generated by 4 will converge with the iteration complexity of O(e-1).
Furthermore, existing works TTS SA mainly focus on the double-sequence case. While in cases such as the multi-level stochastic optimization; see e.g., [61], more than two sequences are involved. This necessitates the use of the multi-sequence SA. Specifically, with mappings u RRdo x RRd ... x Rdv + IRdo h²" : 1Rda-1 x Rdn + Rd, we consider
(STSA)
n- vt) + v n = 1,2, ..., N wht1 = yh + BR.n (n"
(5a)
It+1 I + ar (v(zke Vk. 2h.... .......... vx + Ex)
(5b)

---

General result
Application to SBO
Application to multi-level SCO
Ours
TTS SA
Ours
TTSA
ALSET
ALSET-AC
Ours
a-TSCGD
SG-MRL
SM
(
O
16)
(cc-1.3)
O(C*))
O(E
N-SM
O
OiE
O(e O
O
Nis OlE
O
Merit
Rate
Rate
Relax
Relax
Rate
Rate
Table 1: Comparisons with TTS SA 12), TTSA (26], ALSET and ALSET-AC B o-TSCGD
[6] and SG-MRL [14]. Strongly-monotone (SM) and
(N-SM) respectively and non-strongly- mooooooey
represents the case where the main sequence has strongly-monoton increments. Rows of SM/N-SM are for the complexity and the row of Merit is for the improvements of this work over the existing work ("Rate t" stands for faster rate; "Relax" for relaxed assumptions).
where ork. Sk.,, SK.N are the step sizes, and fk: i...... dh are random variables. For conciseness, we have used vh == Ik here. Our goal is find the unique fixed-points x², yyy ,............................... ................................ N,* such that v(x", y ,""""""."""""........... Nr) = 0, h (x", y²-r) = O...., h -,, . ,,) 0.
(6)
Observing that in (5), for every n, the sequence of yo is coupled with that of yr n-1 and is ultimately coupled with the main sequence Ti. Meanwhile the update of iy also depends on {uR J Since all sequences in (5) are coupled, 5 is more challenging to analyze than the double-sequence SA.
Prior art related to multi-sequence SA. The multilevel stochastic optimization problem [49 and the multilevel SCO problem [1 58 63
47 65 are closely related to the multi-sequence SA. To
tackle the multi-level structure, these recent methods have modified the vanilla multi-sequence SA update to achieve the state-of-the-an complexity and thus their updates are no longer in the form of (5) In contrast, we focus on the nulti-sequence SA update in (5). To the best of our knowledge, the only analysis for (5) is [61] where the TTS technique generalized to ceati--tme-ssclll In [61], the iteration complexity will get worse as the number of sequences N increases.
This gives rise to another interesting question:
Q2: Is it possible to establish convergence rate independent of the number of sequences?
In this work, give affirmative answers both Questions Q1 and Q2.
Our contributions. Specially, by exploiting the smooth assumption that can be satisfied in many applications, we show that the vanilla nonlinear SA can run in single time scale! We further prove that the order of the convergence rate is independent of the number sequences N Intuitively, this is possible because when the fixed point y" is smooth in x. the y uupdae converges fast enough such that its fixed-point residual after sne update is at the same order as the drift of y".
In the context of prior art, our contributions can be summarized as follows (see Table TT.
C1) Single-timeseiie analysis for multi-sequence SA. Different from existing two-timescale analysis we establish a unifying Single- Timescal analysis for SA with multiple coupled sequences that term STSA. When all the sequences have strongly-monoton increments, we improve the (c-b.b) iteration complexity for multi-sequence TTS-SA in [2 to Oc-)). When the main sequence does not have the strongly-monotone increment, we provide the Ole 2) iteration complexity.
39 5
C2) STSA for stochastic bilevel optimization (SBO). When applying our generic results to the SBO problem with double-sequence SA, for strongly-concave objective functions, we improve the best-known sample complexity -15) of TTSA in (26) to ")) For the non-concave objective function, we achieve the same sample complexity ( 2) of ALSET while relaxing the bounded upper-level gradient assumption made in [8].
C3) STSA for stochastic compositional optimization (SCO). When applying our results to the multi-
level SCO problems, we improve the level-dependent sample complexities O(E = and O Nes
N+1
of multi-sequence SA based a- a-TSCG method in [61 to the level-independent complexities Ō and Oe) under the strongly-concave and non-concave objective functions, respectively.
C4) STSA for policy optimization in RL problems. Moreover, applying our results to the actor- critic method achieves the same O(e ?) sample complexity of ALSET-AC in [8] while relaxing the unverifiable assumption on the stationary distribution of Markov chains; applying our results to the meta policy gradient improves the O(e-a) sample complexity of SG-MRL in [4] to O -2).
3

---

2 Main Results: Convergence of Single-timescale Multi-sequeene SA
Before introducing the main results, we will first make some standard assumptions. Throughout the discussion, we define [N] == (1,2..., NN. [K] == 2 }} and y = x for conciseness.
Assumption (Smoothness of the fixed points) For any E [M] and yn E R there exists a unique y"x"("""""""""""""" () E IRd= such that htd (1"",, .y" (1"""y²"11) = O. Moreover, there exist constants Lynn and Ly such that for any y" 17" E Rd the following inequalities hold
I1u*"(u"~1)) 1/ (0" || S T.g.nllu" - 11" 11,
(7a)
Vy"" (y" Vy Fy (g" - Ly 11100=11 5-1
(7b)
Due to the change of vk - each iteration, the solution of (y2 y", that is yy* (""""(")) is drifting over consecutive iterations. Given yk 1- since only one-step of y update is performed at each iteration, one can only hope to establish convergence of y if the drift of its optimal solution is controlled in some sense. Assumption I Jensures both the zeroth-order and first-order drifts are controlled the same scale of the change yo fi- This assumption is satisfied in linear SA [29] and other applications which will be shown later.
(1/11 -3" = 0 with respect to (w.r..)
Define v(x)) u(r y (x), 2². (yl.'(x))) (x))).-.,, ...NiNNN (... y...yy.* 22200(""" (y""(()))).))) With y con- cise notation for (y) ,.... y ). we make the following assumption.
Assumption (Lipschitz continuity of increments) For any n E [N] 2 R and y" g" Rda,, there exist constants Teg, Tun. and Lu,n such that the following inequalities hold
N Σ
[|(x)) u(Ti] S Lu Ell. [1((,,
1:N v 1 ( 1:N >| Luy.y
1lv"
5"11
(8a)
n=
"0")"" n-1 3" Li.n
110" 7"11.
(8b)
Define Fs as the o-algebra generated by the random variables in {a,, -:M y and Fh as the a-algebra generated by (2,, (f.. Fi=1 U (1 We make the following assumption on the noises.
Assumption 3 (Bias and variance) Define N++1 = FR. There exist fcn I such that Vk, n, [F < cga,, |E [E(EIIAt+ < PR. [[|GE|1911] S og and E [| o²
Assumption 3 is generalized version of the bias and variance assumption in stochastic programming [1] or the noise assumption in single-sequence SA [30] to multi-sequence case. Similar assumption has also been made in the existing analysis of double-sequence SA (26). As will be shown later, when applying STSA to the stochastic optimization problems, the conditional independence between samples of different levels along with the bias and variance conditions will lead to this assumption.
","" Assumption 4 (Monotonicity of h) For n E [N], (y"1 y)")
is one-point strongly monotone on r1*
y (y" given any -1 that is, there exists constant An > O such that (ef. (y" (y"-1,""*"" = 0)
""""""""""'"">"" "(")="""))))===))"""""))))"")))) -An llv yd 113 Vy" E Rd=
(9)
Assumption 4 is implied by the standard regularity assumptions in the previous works on TTS linear SA 34 29 and has also been exploited in the TTS nonlinear SA works; see e.g. [39 12]
2.1
The strongly-monotone case
We first consider the case when the main sequence I'k has gtoogllymonoter increment.
Assumption 5 (Monotonicity of v) Suppose v(x) is one-point strongly monotone on x"; that is, there exists a positive constant do such that (cf. v(x")= = 0)
{x x2, ,(xx)) ~ -
x11 -x*1
Vx E Ro.
(10)

---

Same as Assumption Assumption iss standard in the previous works on TTS SA [3 12].
This
assumption is a regularity assumption the case of TTS linear SA; see e-g., B4 Assumption 2.3]. Or in the case of bilevel optimization which will be discussed later, this assumption is satisfied when the objective function is strongly-coneate
Due to space limitation, we directly present the result below and defer the proof to Appendix B
Theorem Consider the sequences generated by ( Suppose Assumptions 7 hold. Select step sizes Og = O ) and BR.n n = ( It holds for any k that
E 1
Σ
Elyy 1" 11 -
(11)
where O()) hides constants in the polynomial of N, and we have used yk for convenience. Moreover, for any n E [NV we have
lim 10 - x² 0 almost surely (a.s.), lim 1 y" (1 11 a.s. (12)
k
is worth noting that with 7a).. Theorem aasso implies the same convergence result for the error metric || xx 11² + Σn 1 "0² the formal justification of which is deferred to the proof of Theorem [ It is worth noting that the order of convergence in Theorem I is independent of N, which is in contrast to the convergence rate that gets worse as N increases
Remark (Comparison with prior art in multi-sequence SA) Theorem bridges the gap be- tween the convergence rates of double-sequence linear and nonlinear SA by improving over the O(k-5 $) rate shown in [2] with the additional assumption 7b). As will be shown later, this assump- tion is satisfied in various applications. Theorem also generalizes the O(t) convergence rate in the double-sequence linear SA analysis (e.g.. 22 to the multi-sequence nonlinear SA case.
2.2 The non-strongly-monon case
Some applications of multi-sequence nonlinear SA such as the actor-critic method 322 Assumption 5 does not hold. This motivates to consider more general setting in this subsection where v(x) is non-strongly-monet monotone. Throughout this subsection, we make the following assumption.
Assumption Suppose there exists a mapping F Ro + R. such that VF(x)
v(x). The
sequence of { is contained in an open set over which F(r) is upper bounded; e.g. F(x) S Cr-
As will be shown later, Fxx) can be chosen as the objective function when applying SA to maximiza- tion problems. Then assumption o standard ensure the convergence of zg; see e.g. (6.
The following theorem gives the general finite-time convergence result the nonlinear SA when the main sequence has the wewtrrogggyymoooooooo increment. The proof is deferred to Appendix C
Theorem 2
Consider the sequences generated by 5 for k=[K]. Suppose Assumptions 4 & O(
hold. Select ag O +x) BN.n
1 with properly chosen initial step sizes, then it holds that
VRR
Σ
E VEI
+
Blut yn (" (1 0 VK
1
(13)
K
m=1
where O(-) hides problem dependent constants of polynomial of N, and we have used vl Tk-
Theorem implies finite-time convergence rate of O(K-)), )), which is independent of the number of sequences N. The error metric (xx))l used in Theorem 2 is of interest since it is a general measure the convergence of æx widely adopted in many applications of SA, especially when the increment of xı is not mtrongly-monotone. Moreover, although we have assumed the existence and uniqueness x² in ( the proof of Theorem 2 does not utilize this fact and thus the theorem applies to the more general case where x" is not unique even does not exist.
5

---

Remark 2 (Comparison with stacking all the variables) One naive way to establish the conver- gence of a mulli--seqeent update is to stack all the variables and view it as one sequence. However, the stacked sequence requires stronger assumptions that are violated in the applications to converge. For one, we would need v. 1.2 ,,.""...,hi h2 to be jointly lipschitz continuous w.r.f. the stacked variable (xr, ,...,y"). This condition is violated in, e.g., the application of actor-critic (Section 3.2 The upper-bounded function F can also be difficult to find. As it can be seen later in, e.g. Section that such a F only exists for and might not exist for the stacked variable (z. v).
Next we will showcase how the results can be applied to optimization and RL problems.
3 Applications to Stochastic Bilevel Optimization
With mappings f Rd Rd + IR and g: : 12do R2 IR, consider the following formulation of the bilevel optimization problem:
max F(x) f v (x)) Be [ (x); =ER
s.t.
= arg min g( = E.p [0(2, y:
(14)
yERd
where ( and yp are two random variables.
3.1 Reduction from the generic STSA results
A popular approach to solving (14) is the gradient- based method 21 26 27 8. Under some
conditions that will be specified later, the gradient of F(x) takes the following form (1)
V F())) = V.f y - y (+)) (y,,, VV
(15)
Computing 15 requires y (xx). which is often unknown in practice. Instead, one can iteratively
update y/ to approach y (2x) while using yk in place of y (zx) during the computation of ([5) 26 8) This leads to update same as that in (5) with N == 1, where the mappings are defined as
M[x, u) = - V2g( u), t4 = =-==n( mk) V Veg(( Mes Pk),
(16a)
o(x, y) = vaf(x, - V2 V
vog y)]
V of y),
(16b)
&K --(=, M&) + V.I( u (x) V2 2 E (Zk, Uni HL" y Mes Ck).
(16c)
Since we only have two sequences, that is 1 we omit the index n to simplify notations. (6
Sa is a random variable with the same distribution as that of Ç. and sp.. Po%. have the same distribution as that of sp Here 11 is a stochastic approximation of the Hessian inverse [a ym0] Given Tk, when yı reaches the optimal solution y (arx), follows from (5) that v( y (xx)) = FF(x).
As being discussed below Assumption | the lower-level optimal solution y² (Ix) is drifting at each iteration. Under the Lipschitz continuity assumption of y² (zz), the drifting |1>/ (xx+1) y² (æx) scales with || K&ll which ultimately scales with [[VF(x))) (I. To control the drift scale, former analysis heavily relies the condition that F can be bounded for any k. In SBO, this means to either make a strong assumption on the Lipschitz continuity of f(. y) w.r.t. (I. y). which leads to the Lipschitz continuity of F(x)) and the boundedness of / F*xx)) [8]: to introduce projection in (6) to forcibly confine Ty in a compact set (26). all of which greatly narrow the range of application. We will show that neither of these the conditions is needed by applying our generie results SBO.
Lemma (Verifying assumptions of STSA) Consider the following conditions
(a) For any x TRdd, g(2,, y) is strongly convex w.E.t. y with modulus A > O.
(2, y) is -ip--hit continuous w.r.f. (b) There exist constants Tazy, lay. by such that V Vyg(a,
x; V V2g(2,3) y) is LipLschciitz continuous w.r.. y. V (z y). Veyg(z, (2, y) are respectively lay Lipschicttt and Lyp-schchiitz continuous w.r.t (I,y).
(c) There exist constants Syn,tty- ''y by such that Vaf(I, 8) and (yf(2,8) y) are respectively Lya and ly Lipschitz continuous w.r.t y; V (z, v) is 1',, Lipschitz continuous w.r.. x; f(z, 2) is by Lipsschiitz continuous w.r.t. y.

---

(d) F(x) satisfies the restricted secant inequality: There exists a constant Xo > 0 such that
(VF()),z-=") ~ II?, where x²
== arg max F(z).
(e) For any k. there exist constants Co C1 such that || I chaz and LL Ful -
c Bki there exist constants du, 01 such that 1x S of and E Wh | S o..
(f) There exists a constant Cp such that F(x) S Cr.
We use a = to indicate that a is a sufficient condition of Then we have
a b
Assumption
7
@
Assumption
2
(c)
+ Assumption 3
Assumption
d
Assumption
5
Assumption
The conditions listed above are commonly adopted in the literature 21 26 8 It is worth noting
that Lemma [ does not need the Lay-Lipschitzz continuity condition of f(z, y) w.r.t (z, y). This Lipschitz condition along with the Ly-Lipschitz continuity of (x), which is implied by the standard conditions in Lemma further leads to the Lipschitz continuity of F(x):
FF(z) - F(x') S Lzy(1 æ'1l + lly" (x) y" (z'Il) S Loy(Ly + 1)1l= 2'1l-
(17)
Although it is rather restrictive, this condition has been used in the previous work when F(x) is not
grongly-concave While our analysis does not need this condition. Lastly, condition (e) [e] guaranteed by using independent samples in the upper- and lower-level along with [2I] Algorithm 3] to obtain a
good H which takes (2- log oy.) samples per iteration. With Lemma | we have the following corollary regarding the convergence of (T6).
Corollary (STSA for SBO) Consider the STSA sequences with the update in (T6). Under Condi- holds; that is, with ag = ( and 3x = =( ) we have
tions a ()) Theorem I
E Tk
x" 112
Bllbkk 3² (==))1==-
(18a)
lim
|2g
x 112
and
lim A toc
lluk y (Ik)]1 a.s.
(18b)
k 700
Under Conditions
(a)
(c)
(e)
and
( Theorem
holds; Le., with az = Be = 0 VK ). we have
1 K
E V [2
Elyya o (=w)))) =0 VK
(19)
Remark (Comparison with prior art in SBO) When F(x)) is strongly concave, Corollary 1 im-
plies the sample complexity of lloge 11) which improves over the best-known sample complex-
ity O(c 1.5 1155 log c-1) in [26]. Different from [6],, we do not need the projection of vg to a compact
set. When F(x) is non-concave, corollary suggests sample complexity of O(E log 1)) which
is the same as the state-of-art complexity established in B. Corollary D improves the result in (8) in
two major aspects: 1) it relaxes the Lipschitz continuity assumption on (x, y); and, 2) an alternating update is adopted in g to ensure stability, while some applications of SBO only allow simultaneous updates. Corollary D applies to those cases and thus has broader range of application.
3.2 Application to advantage actor-critic
RL problems are often modeled as a MDP described by M (S, AP,r,,, where S is the state space, A is the action space; P(s'|s, a)) is the probability of transitioning to s' ES given (s, a) E Sx.;; r(s, a) E [0, 1] the reward associated with (s. a); and y E (0, is discount factor. policy ı maps S to a distribution over A, and we use r[ass) to denote the probability of choosing under 8.
Given a policy æ, we define the value functions as (s()) = Em Σi= 7'1(st, ax) 80 60=8_ where
E, is taken over the trajectory (So, ag, $1, ......) generated under policy π and transition kernel P. With p denoting the initial state distribution, the discounted visitation distribution induced by policy и is defined via de (s. a) = (1 7) Ei ''Pr, = so ~ (a)s). s). To overcome the difficulty of learning a function, we parameterize the policy with x E RRd, and solve
max F(x)= = (1 B) (V., (s)) =ERo
(20)
7

---

To solve for 20, popular method is the actor-critic (AC) method [32]. The actor-critic algorithm with linear enitic function is a special case of (5). Specifically, the critic variable y updated with
h(,, y) = ot 4/k - 1l( Uk) ((s)) ((+x)) " y (()s))))0(s5))
o(8)) "I Earpnn a (r,, ()))))
(21)
where Mr, is the stationary distribution of the Markov chain induced by T.. 0(s) E Rd is the feature vector encoding state and the sample (sk, aks 54)) is returned by some sampling protocol. Under some regularity conditions, is known that there exists unique y" (r) such that h(,, y (x)) = 0 22]
The actor variable is then updated with
u(x, v) asd s ((r(s a) (10((5) T V log T.z (a|s)]
& = - (1 wke) + r(Aps ax) + ((((3))) (b+x)) yk V log Tæg (5x
(22)
For the AC update (21) and (22). Assumption 2 and their sufficient conditions have been explored in the RL context by previous works [57 However, the smoothness of y (x:) in Assumption I which the key condition leading to a faster convergence rate, has yet been verified. With the
same conditions those adopted in 577. prove that y" (z)) is indeed smooth.
Lemma Consider the AC update in 21 22
Under the standard conditions specified in Appendix O such that [| (1:) Vy² (x')ll Tuy by x'|]-
y" (ar) is differentiable and there exists
Tay'
As a comparison, the above condition was directly assumed in 8 while we provide formal justification for Lemma 2 in this work. With detailed verification of all assumptions deferred to Appendix E. we then directly present the theorem regarding the convergence of AC
Theorem 3 (Complexity of AC) Consider the AC update specified in Appendix
22
Under the standard conditions
Theorem
holds; that is, with og
and Ba = O 7
( ) we have
K
[IFF(=2)1 Bllba -V (xx))))) o
(23)
K
VK
In 57 the projection step is adopted in the yı update to ensure that ||yx||| < oo, Vk. Since the projection radius unknown practice, adopting the projection essentially assuming that || can be bounded for any k; which is quite strong. Theorem 3 holds without this projection.
4 Applications to Stochastic Compositional Optimization
Define mappings l" Rd + R for 0, 1, .... N with dx+1 1. The multi-level stochastic compositional problem can be formulated as
max F(x) = PM (S (C. with -e (")] = 0,1,..., N (24) #0
where 5 s....., CN are random variables. Here we slightly overload the notation and use (xx( (*)
to represent the stochastic version of the mapping.
4.1 Reduction from the generic STSA results
To solve the problem in 24 natural scheme is to the stochastic gradient descent method with the gradient given by
VF(x)= WWGO= (2).
(25)
where we use (." (()......)))))
estimator of VF(x), we will need to obtain the stochastic estimators for V (() To obtain stochastic for
each n. For example, when 1, one will need the estimator of f (Ero (xx However, due to the possible non- con-iincarity of (-), the natural candidate V (f (z: ( not an unbiased
8

---

estimator of f (E (2; (2;()))) To tackle this issue. popular method is to directly approximate
the mean Ex- (c (")) with a tracking variable y" E Te for n = 0, I, see e.g., [61]
The update of y" is then special case of the SA update in 5 with the generic mapping defined 1K + (vk Sk - yi (26)
"""""=' "v"" -v" y", 4 -h"
(vk (y²
where Shr... Skr..... St have the same distributions as that of . 5 respectively. It is then clear that each yi has unique fixed-point "/x ("/ and thus ye can be viewed as an approximation
of f"'(( (v%))) With these approximations, variable is updated in the form of (5) by defining
o(x,y' ..... y² ( (w')
f==uv(ra uk: -.. yk
V
/ (I 2
VS (VE
(27)
where <e has the same distribution that of ÇD) clear that when every ye reaches its fixed-point Vi n:* it follows from (25) that v( Mk ... M/ Fx*x). which indicates that the expected
update direction of ug in is V (3r2)
Next we provide lemma that summarizes the sufficient conditions of Assumption 6
The listed
conditions are standard in the stochastic compositional optimization literature 161
Lemma 3 (Verifying assumptions of STSA) Consider the following conditions
(g) Given any n [N] U (0}, there exist positive constants Teg.n and Tag' such that the mapping f-) is Lynn -Lipschitz continuous and Ly -m-oooh.
[M] (1" (1 :E) and f" (h) Given FR. for any ("(tt1) and (" with bounded variance; ( (P) and biased estimators of ("
are respectively the un-
V f : ( are respectively the unbiased estimators of (zx) and V (xK) with bounded variance.
(i) Per iteration k. 28 Ske SE are conditionally independent of each other given Fu.
(j) Function F(x) satisfies the restricted secant inequality: There exists constant Ao > 0 such that (VF()), x²) S -
>ol0 1 - x=' 112, where x² == arg max F(x).
(k) There exists a constant Cp such that F(x)= S Cp.
We use a + b to indicate that a is sufficient condition bf Then we have Assumption
g
Assumption 7 and 2
and
Assumption 5
Assumption Assumption
holds for (6)
With Lemma we can directly arrive at the following corollary on the convergence of the stochastic compositional optimization method.
Corollary (STSA for multi-level SCO) Consider the STSA sequences generated by 266 (7
Under Conditions [g] (j]
Theorem holls. Under Conditions g [k] Theorem holds.
Remark 4 (Comparison with prior art in SCO) Corollary establishes the sample complexity of O for the strongly monotone case and the complexity of () the non-monotone case, which are both independent of N. This improves over the O complexity for the strongly concave case and the O(e - complexity for the non-concave case shown [6]]. There are other works that establish the same complexity as that in Corollary but they require modification to the
basic SA update (66 and (27 to achieve acceleration; see e.g..
4.2 Application to model-agnostic meta policy gradient
Consider a set of MDPs [M:JA with M, = (S, Pi, ri, 7) The MDPs model a set of RL tasks that share the same state-action space while having different transition kernels P, and reward functions To better compare with the previous work [14), we consider the finite-horizon objective
function with the policy म parametrized by x E Rdd F((x)
Eçan=
Σ/ rrr,(,,, at at)e,, P.].

---

where H E N+ is the horizon, and Bç-,, is taken over the trajectory Ç (: ($0. Go. 81, 01. H 0.)) generated under policy Zz initial distribution pj and transition kernels P..
The goal of MAMPG is to find an initial policy Ty that can achieve good performance in new tasks by performing& few policy gradient steps [13] 14] In the case where N steps of gradient update performed, the problem of finding an initial policy parameter x can be formulated as
max F(x) EER
1 M
Σ
F. (x)) with 2 = क. (VR(E))
(28)
where I is the shared initial policy parameter, i.e., x. for any task i and 2;" (x) is the parameter after running steps of gradient ascent with respect to F. starting from æ.
Solving (28) with SCO method. The MAMPG problem in (28) can be solved by the stochastic com- positional optimization method introduced before. In order get VF()z), one will need F (z)) for each task Observe that F. (x)) can be written as a compositional function:
E (x)) = f: (UNN ( (x)))...)) with (f) = + v)), n = O,.....--I - (29)
where p (x) = (.))). In order to approximate ( (x))) we can follow the discussion in Section and introduce tracking variables y/² E dRdo for n E [N] which are updated as follows
vk+1,, yk. (VE, f. (3 5k,5 (,,7 )), 0, 1, I..., N
(30)
where we define f. (f(:;]) () stochastic approximation of f-) with random trajectory Ç. Then we estimate (&N (x)) by F... defined as
V V f GZ V (v) (k.)) V. (M (..).
(31)
To obtain an estimation of V (x:), need V Fi, for each i {1, 2, ... M). Thus we do (30 for each i. With F J.M the initial policy is updated as 2x+1 = 2x + a M ΣM F
Reduction from the generic results. Let y" E IRd M be a concatenation 3," for i E {1, 2, M}. With C == ((E.... IM let ("];; (E) be a concatenation of f:" (vf. (E,) for E {1, 2, ..., M J. Then we can write the tracking variable update of all tasks jointly in the form of (5a). that is
h" "y"""" v²)
fy" (yy"") y", w = - ht" (w
vx + f (v 1:
Vk. (32)
The initial policy update is special case of 5b that is
M
0(2 y vM
Σ (.)
(v)) f== yi..... ub
Σ
F (33)
M
M
Due to space limitation, we directly give the result below and defer the proof to Appendix G
Theorem (Complexity of MAMPG) Consider the STSA sequences generated by the MAMPG Theorem 2 holds.
update in 32 and 33
Under some standard conditions specified in Appendix G
Theorem implies sample complexity of O(E ) to achieve the e-stationary initial policy, which improves over the (c==)) sample complexity in [4]. Moreover, Theorem 4 holds for any N 2 1 in
28 while the method in [14 only applies the case N 1.
Conclusions
In this work, we consider the general nonlinear SA with multiple coupled sequences, and study its non-asymptotic performance. Different from the dominating two-timescale SA analysis, we are particularly interested in under which conditions, single-timescall analysis can be applied to nonlinear SA with multiple coupled sequences. When all the sequences have strongly monotone increments, we establish the iteration complexity of O(c When the main sequence is not strongly-monotone we establish the iteration complexity of O(e -2). We then apply our generic SA analysis to stochastic bilevel and compositional optimization and improve their existing results. Specifically, we improve the state-of-the-arr convergence rate of: 1) the SBO method and its application to the AC method; and, 2) the multi-level SCO method and its application to the MAMPG method.
10

---

Acknowledgments
This work was partially supported by National Science Foundation MoDL-SCALE Grant 2134168. Amazon Research Awards, and the Rensselaer-IBM AI Research Collaboration (http://airc edi. part of the IBM Al Horizons Network (http://ibm) biz/ www.eiii/iiiiAi AIHooizzos... We thank anonymous reviewers for their valuable feedback on improving the current paper.
References
[1] K. Balasubramanian, S. Ghadimi, and A. Nguyen. Stochastic multi-level composition opti- mization algorithms with level-independent convergence rates. SIAM Journal Optimization, 32(2):519-555 2022.
[2] J. Bhandari, D. Russo, and R. Singal. finite time analysis of temporal difference learning with linear function approximation. In Proc. of Conference Learning Theory, 2018.
[3] V. Borkar. Stochastic approximation with two time scales. System control letter, 29, 1997.
[4] V. Borkar. Stochastic approximation: dynamical systems viewpoint. Springer, 2009.
[5] V. Borkar and V. Konda. The actor-critic algorithm multi-time-scale stochastic approximation. Sadhana, 22(4):525-543 1997.
[6] L. Bottou, F. Curtis, and J. Nocedal. Optimization methods for large-scale machine learning. SIAM Review, 60(2), 2018.
[7] T. Chen, Y. Sun, and W. Yin. Solving stochastic compositional optimization is nearly easy as solving stochastic optimization. IEEE Transactions on Signal Processing, 69:4937-4948, 2021.
[8] T. Chen, Y. Sun, and W. Yin. Tighter analysis of alternating stochastic gradient method for stochastic nested problems. In Proc. of Advances in Neural Information Processing Systems, 2021.
[9] M. Dagreou, P. Ablin, S. Vaiter, and T. Moreau. A framework for bilevel optimization that enables stochastic and global variance reduction algorithms. arXiv preprint arXiv:2201.13409, 2022.
[10] G. Dalal, B. Szorenyi, and G. Thoppe. A tale of two-timescale reinforcement learning with the tightest finite-time bound. In Proc. of AAAI Conference on Artificial Intelligence, 2020.
[11] G. Dalal, B. Szorenyi, G. Thoppe, and S. Mannor. Finite sample analysis of two-timescale stochastic approximation with applications to reinforcement learning. In Proc. of Conference on Learning Theory, 2018
[12] T. Doan. Nonlinear two-time-scale stochastic approximation: Convergence and finite-time performance. arXiv preprint:201 1.0/88,, 2021.
[13] A. Durmus, E. Moulines, A. Naumov, S. Samsonov, and H. Wai. On the stability of random matrix product with markovian noise: Application to linear stochastic approximation and td learning, 2021.
[14] A. Fallah, K. Georgiev, A. Mokhtari, and A. Ozdaglar. On the convergence theory of debiased agnes-agn meta-reinforremmnt learning. In Proc. of Advances in Neural Information Processing Systems, 2021.
[15] C. Finn, P. Abbeel, and S. Levine. Model-agnostic meta-learning for fast adaptation of deep networks. Proc. of International Conference on Machine Learning, 2017.
[16] I. Franceschi, P. Frasconi, S. Salzo, Grazzi, and M. Pontil. Bilevel programming for hyperparameter optimization and meta-learning In Proc. of International Conference on Machine Learning, 2018.
[17) 7. Fu, Z. Yang, and Z. Wang. Single-timescale actor-critie provably finds globally optimal policy, arXiv 2000:int:208..0044 2008.00483, 2020.

---

[18] S. Gadet. Stochastic optimization algorithms. https://perss: math. univ fr/ http://///00///////orrs......_//
pdf 2017.
[19] S. Ghadimi and G. Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):2341-2368, 2013.
[20] S. Ghadimi, A. Ruszezynski, and M. Wang. A single timescale stochastic approximation method for nested stochastic optimization. SIAM Journal on Optimization, 30(1))960-97)) 2020.
[21] S. Ghadimi and M. Wang. Approximation methods for bilevel programming. arXiv preprint: w000.1000000 preprint:/802.022445 022.02246,.... 2018.
[22] R. Grazzi, Franceschi, M. Pontil, and S. Salzo. On the iteration complexity of hypergradient computation. In Proc. of International Conference Machine Learning, pages 3748-374 -758,, 2020.
[23] R. Grazzi, M. Pontil, and S. Salzo. Bilevel optimization with lower-level contraction: Optimal sample complexity without warm-start. arXiv preprint urXiv:2202.03397, 2022.
[24] Z. Guo and T. Yang. Randomized stochastic variance-reduced methods for stochastic bilevel optimization. arXiv preprint
2021.
[25] H. Gupta, R. Srikant, and L. Ying. Finite-time performance bounds and adaptive learning rate selection for two time-scale reinforcement learning. In Proc. of Advances in Neural Information Processing Systems, 2019.
[26] M. Hong, H.-T. Wai, Z. Wang, and Z. Yang. A two-timescale framework for bilevel optimization: Complexity analysis and application to actor-critic. arXiv preprint:2007.05177, 2020.
[27] K. Ji, J. Yang, and Y. Liang. Provably faster algorithms for bilevel optimization and applications to meta-learning. In Proc. of International Conference on Machine Learning, 2021.
[28] W. Jiang, B. Wang, Y. Wang, L. Zhang, and T. Yang. Optimal algorithms for stochastic multi-level compositional optimization. arXiv preprint arXiv:2202.07530. 2022.
[29] M. Kaledin, E. Moulines, A. Naumov, V. Tadic, and H. Wai. Finite time analysis of linear two-timescale stochastic approximation with markovian noise. Proc. of Conference on Learning Theory, 2020.
[30] B. Karimi, B. Miasojedow, Moulines, and H. Wai. Non-asymptotic analysis biased stochastic approximation scheme. In Proc. of Conference on Learning Theory, 2019.
[31] Khanduri, S. Zeng, M. Hong, H. Wai, Z. Wang, and Z. Yang. A momentum-assiisee single-timescale stochastic approximation algorithm for bilevel optimization. arXiv preprint arXiv:2102.07367, 2021.
[32] V. Konda. Actor-critic algorithmss PhD thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, 2002.
[33] V. Konda and V. Borkar. Actor-critic-type learning algorithms for markov decision processes. SIAM Journal on Control and Optimization, 38(1)944-12,, 1999.
[34] V. Konda and Tsitsiklis. Convergence rate of linear two-time-scale stochastic approximation. The Annals of Applied Probability, 14(2). 2004.
[35] H. Kumar, A. Koppel, and A. Ribeiro. On the sample complexity of actor-critic method for reinforcement learning with function approximation. arXiv 19100084/2 2019.
[36] J. Li, B. Gu, and H. Huang. A fully single loop algorithm for bilevel optimization without hessian inverse. In Proc. of AAAI Conference Artificial Intelligence, 2022.
[37] Lin, C. Jin, and I. Jordan. On gradient descent ascent for nonconvex-conean minimax 2019.
problems. arXiv preprint
12

---

[38] R. Liu, P. Mu, X. Yuan, S. Zeng, and J. Zhang. A generic first-order algorithmic framework for bi-level programming beyond lower-level singleton. In Proc. of International Conference on Machine Learning, 2020.
[39] A. Mokkadem and M. Pelletier. Convergence rate and averaging of nonlinear two-time-scai stochastic approximation algorithms. The Annals of Applied Probability, 16(3), 2006.
[40] H. Moshe and V. Ludo. Perturbation bounds for the stationary probabilities of finite markov chain. Advances in Applied Probability, 16(4):804-818 1984.
[41] W. Mou, J. Li, M. Wainwright, P. Bartlett, and M. Jordan. On linear stochastic approximation: Fine-grained polyak-ruppert and non-asymptoric concentration, 2020.
[42] E. Moulines and F. Bach. Non-asymptotie analysis of stochastic approximation algorithms for machine learning. In Proc. of Advances in Neural Information Processing Systems, 2011.
[43] A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal on Optimization, 19(4):1574-1609 2009.
[44] S. Qiu, Z. Yang, X. Wei, J. Ye, and Z. Wang. Single-timesede stochastic wwwnconvex-coneccee optimization for smooth nonlinear learning. arXiv preprint arXiv:2008. 10103, 2020.
[45] 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.
[46] H. Robbins and S. Monro. A stochastic approximation method. The Annals of Mathematical Statis- tics, 20( 4070000-07,1 1951.
[47] A. Ruszezynski. stochastic subgradient method for nonsmooth nonconvex multilevel compo- sition optimization. SIAM Journal on Control and Optimization, 59(3):3301-2320, 2021.
[48] S. Sabach and S. Shtern. A first order method for solving convex bilevel optimization problems. SIAM Journal on Optimization, 27 2017.
[49] R. Sato, M. Tanaka, and A. Takeda. A gradient method for multilevel optimization. arXiv preprint:2105. 13954, 2021.
[50] R. Srikant and L.. Ying. Finite-time error bounds for linear stochastic approximation and td learning. In Proc. of Conference on Learning Theory, 2019.
[51] H. Stackelberg. The Theory of Market Economy. Oxford University Press, 1952.
[52] Sun, G. Wang, G. B. Giannakis, Q. Yang, and Z. Yang. Finite-time analysis of decentralized learning with linear function approximation. In International Conference on Artificial Intelligence and Statisties, 2020.
[53] R. Sutton, H. Maei, D. Precup, S. Bhatnagar, D. Silver, and F. Szepesvári, C.and Wiewiora. Fast gradient-descent methods for remporal-differenee learning with linear function approximation. In Proc. of International Conference on Machine Learning, 2009.
[54] G. Wang, B. Li, and G. B. Giannakis. A multistep іyарunov approach for finite-time analysis of biased stochastic approximation. arXiv preprint arXiv: /rXiv: (90.. 2019.
[55] M. Wang, E. Fang. and H. Liu. Stochastic compositional gradient descent: Algorithms for mini- mizing compositions of expected-valle functions. Mathematical Programming, 161:419-449, 2017.
[56] M. Wang, J. Liu, and E. Fang. Accelcrating stochastic composition optimization. Journal of Machine Learning Research, 18(1):3721-3743, 2017.
[57] Y. Wu, W. Zhang, Xu, and Q. Gu. finite time analysis of two time-scale actor critic methods. In Proc. of Advances in Neural Information Processing Systems, 2020.
13

---

[58] T. Xiao, K. Balasubramanian, and S. Ghadimi. A projection free algorithm for constrained stochastic multi-level composition optimization. arXiv preprin::2202.04296 2022.
[59] T. Xu, Z. Wang, and Y. Liang. Improving sample complexity bounds for (natural) actor-critic algorithms. In Proc. of Advances in Neural Information Processing Systems, 2020.
[60] Yang, K. Ji, and Y. Liang. Provably faster algorithms for bilevel optimization, arXiv preprint arXiv:2106.04622 046604 2021.
[61] S. Yang. M. Wang. and E. Fang. Multi-level stochastic gradient methods for nested composition optimization. SIAM Journal on Optimization, 29(1), 2018.
[62] Z. Yang, K. Zhang, M. Hong, and T. Başar. A finite sample analysis of the actor-critic algorithm. In Proc. of IEEE Conference on Decision and Control, pages 2759-2764, 2018.
[63] J. Zhang and I.. Xiao. Multilevel composite stochastic optimization via nested variance reduction. SIAM Journal on Optimization, 31(2):1 2021.
[64] K. Zhang, A. Koppel, H. Zhu, and T. Başar. Global convergence of policy gradient methods to (almost) locally optimal policies. SIAM Journal on Control and Optimization, 5866)33586-361, 2019.
[65] Z. Zhang and G. Lan. Optimal algorithms for convex nested stochastic composite optimization. arxiv preprint arXiv:2011.10076 2020.
[66] S. Zou, T. Xu, and Y. Liang. Finite-sample analysis for SARSA with linear function approxima- tion. In Proc. of Advances in Neural Information Processing Systems, 2019.
Checklist
Please do not modify the questions and only use the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below.
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]] This work only considers the strongly-monotone increments for the follower sequences, but it will be interesting to also consider the monotone increments with non-unique fixed point y". Right now the generic result in this work can only be applied to the unconstrained stochastic consider whether it is possible to
optimization, while will be also interesting establish similar result that is applicable to the constrained stochastic optimization problems. We will add discussion on the limitations in the revision.
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e-g., with respect to the random seed after running experi- ments multiple times)? [N/A]
14

---

(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you using existing assets (e.g., code, data, models) curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you'le 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "y--yDJCt1mA", "reviewer": "Reviewer_xK38", "summary": "This paper fomulates the stochastic approximation of multiple coupled sequences and builds the non-asymptotic convergence rate for both strongly monotone and non-monotone case. Multiple applications are introduced after providing the theoretical convergence guarantee, including bilevel optimization and compositional optimization.    ", "questions": "* I agree that the monotonicity assumption (Assumption 4 and Assumption 5) is standard in many existing work. But I am not clear how this assumption is connected to concave or strongly concave function. Are they just different name? ", "limitations": "Since this work is purely theoretical, there is no any negative impact.", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "***Strengths***\n* This work is sufficiently complete and well-written. It gives a clear definition of the multiple sequences stochastic approximation and builds the convergence rate for both of strongly monotone and non-monotone cases. Also, those derived bounds have matches the best known results. \n\n* It is nice to see there is a unifying framework that can include stochastic bilevel optimization and stochastic compositional optimization. I am not sure if this paper is the first work doing so, but this paper reveals the significance of studying the stochastic approximation with multiple coupled sequences.    \n\n* The sngle-time-scale  learning rate scheduling can be better than the standard two-time-scale one. This result is really new.\n\n***Weaknesses***\n* I have not found any major weakness of this work.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "rSNw_JkC-U", "reviewer": "Reviewer_gp8F", "summary": "This work proves the convergence guarantees for SA with double-sequence and also extends to multi-sequence and the results seem tight. Besides, this paper also applies their general results to SBO and SCO problems and show the improvement of their results.", "questions": "see Strengths And Weaknesses", "limitations": "see Strengths And Weaknesses", "rating": 6, "confidence": 1, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "As I'm not an expert in optimization area, I'm only able to give some common issues in this paper. \n\nQuestions:\n1. I think Assumption 3 is a little bit weird because LHS is a random variable while the RHS is a non-random term and without a high probability guarantee. And I think it is not the generalized version of Assumption 2.1 in [30] because the second-order condition in Assumption 3 can induce moment assumption in [30].\n2. I would be appreciated if the author could provide an example of a weak dependent sequence as Assumption 3 describes.\n3. Is $y^n$ arbitrary in Assumption 4? If so, please use more precise language.\n4. Line 169, it is not $\\mathcal{O}(K^{-2})$ but $\\mathcal{O}(\\epsilon^{-2})$ or $\\mathcal{O}(K^{-1/2})$\n\nIn conclusion, in my own opinion, I think this paper provides a solid result. But I will consider changing my score after reading other reviewers' comments and authors' responses.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "eI81sw7wkp-", "reviewer": "Reviewer_qTJ6", "summary": "In this paper, this paper studies the finite-time convergence of nonlinear SA with multiple coupled sequences. Different from existing multi-timescale analysis, the authors seek for scenarios where a fine-grained analysis can provide the tight performance guarantee for single-timescale multi-sequence SA (STSA). When all sequences have strongly monotone increments, they establish the iteration complexity of O(eps^{−1}) to achieve eps-accuracy, which improves the existing O(eps^{−1.5}) complexity for two coupled sequences. When the main sequence does not have strongly monotone increment, they establish the iteration complexity of O(eps^{−2}).", "questions": "1. Can we still get a single-timescale algorithm when \\xi and \\psi are not mutually independent?", "limitations": "According to the submission instructions, the authors need to complete the check list after the reference section. In this paper, the authors did not provide limitations of this work. I think the authors can further discuss the limitation of this theoretical analysis in their submission. ", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. This paper provides an improved rate for the case where all sequences have strongly monotone increments in single-timescale multi-sequence SA.\n2. This paper further provides an analysis for a single-timescale multi-sequence SA when the main sequence does not have strongly monotone increment. \n3. The theoretical analysis is novel, which makes significant contribution to the related area.\n\nWeaknesses:\n\n1. I think this paper lacks sufficient discussions and comparisons on the assumptions, which makes the technical part of this paper not sufficiently clear:\n\nThere is another work studying the single-timescale minimiax optimization [1], which is a special case of the single-timescale two-sequence SA when the main sequence does not have strongly monotone increment. In their Algorithm 1, they show that a momentum updating step is needed in order to obtain a single-timescale algorithm. However, this paper does not need the momentum updates. In my understanding, the main technique for the proof to get rid of momentum is in (57) and (59). And (57) and (59) depends on two important assumptions: \n\na)  \\xi and \\psi are mutually independent. Otherwise, the second equation in (57) does not hold. This means we need to sample twice independently in the application of the algorithm. In [1], they do not have this assumption. I think this mutual independence should be highlighted as a formal assumption and a comparison with the existing work is needed as well.\n\nb) Existing works e.g., [1] [2], only need a Lipchitz assumption for y*, while this work makes a relatively stronger assumption that the gradient of y* exists. Such a comparison is also necessary in the paper to clarify the major difference in the assumptions and the reason why we can obtain a single-timescale algorithm.\n\n[1] Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning\n[2] On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems\n\n2. According to the submission instructions, the authors need to complete the check list after the reference section. In this paper, the authors did not provide limitations of this work.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "K998hbgvd90", "reviewer": "Reviewer_QKd6", "summary": "The paper studies the finite-time convergence of nonlinear stochastic approximation (SA) with multiple coupled sequences. While there are few work on analyzing the performance of SA in this setting, existing analysis all adopt a multi-timescale analysis in the sense that the stepsizes for all the sequences decay at the different rates, which leads to a convergence rate that is slower than that of the single-sequence SA. The focus of this paper is on finding settings where it suffices to using single-timescale updates for multi-sequence SA, leading to the same convergence rate as that of the classic single-sequence SA. The implications of the new results on applications to bilevel, compositional and reinforcement learning have been discussed. ", "questions": "1. If the smoothness assumption does not hold, can the existing complexity of SA be improved using the analysis in this paper?\n2. In addition to stochastic bilevel and compositional optimization, what other new special class of stochastic optimization problems can benefit from this generic results? \n3. It would be interesting to discuss and highlight in the main paper how the new proof improves the existing analysis. Now they are hidden in the supplementary document. \n", "limitations": "NA", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1.\tThis paper presents the ﬁrst $k^{-1}$ and $k^{-1/2}$ convergence rates for nonlinear SA under two settings: a) all sequences have strongly monotone increments; and b) all but the main sequence have strongly monotone increments. These results have been then extended to multiple coupled sequences with the same iteration complexity, which is also new.\n2.\tThe paper presents a unified and new perspective of understanding the recent theoretical advances in stochastic bilevel, compositional optimization and reinforcement learning. Applying the new results of nonlinear SA with multiple coupled sequences to those special cases lead to either improved iteration/sample complexity or relaxed assumptions. \n3.\tThe nice thing about this framework is that the iteration/sample complexity of new SA algorithms developed in these applications can be established by just verifying the assumptions in this paper. If those assumptions are verified, they automatically enjoy the same convergence rate as single-sequence stochastic approximation or SGD. \n4.\tThe simulation, although very simple, gets the key point of this paper – there is a gap between the existing theory and the actual performance of nonlinear SA. \n\nWeaknesses:\n1.\tThe new iteration complexity results for nonlinear SA hold under the smoothness assumption on the fixed point. While the paper has justified it in several applications, it does not improve the existing complexity of SA without this smoothness assumption. \n2.\tThe paper can do a better job on discussing and highlighting in the main paper how the new proof techniques improve the existing analysis.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}]

Author rebuttal:

Decision: Accept