arXiv:1502.01956v2 [] 9 Oct 2015

Stochastic recursive inclusion in two timescales
with an application to the Lagrangian dual
problem
Arun Selvan. R

1

and Shalabh Bhatnagar

2

1

arunselvan@csa.iisc.ernet.in
2
shalabh@csa.iisc.ernet.in
1,2
Department of Computer Science and Automation, Indian
Institute of Science, Bangalore - 560012, India.

Abstract
In this paper we present a framework to analyze the asymptotic behavior of two timescale stochastic approximation algorithms including those
with set-valued mean fields. This paper builds on the works of Borkar
and Perkins & Leslie. The framework presented herein is more general
as compared to the synchronous two timescale framework of Perkins &
Leslie, however the assumptions involved are easily verifiable. As an application, we use this framework to analyze the two timescale stochastic
approximation algorithm corresponding to the Lagrangian dual problem
in optimization theory.

1

Introduction

The classical dynamical systems approach was developed by Benaı̈m [2, 3] and
Benaı̈m and Hirsch [4]. They showed that the asymptotic behavior of a stochastic approximation algorithm (SA) can be studied by analyzing the asymptotics
of the associated ordinary differential equation (o.d.e.). This method is popularly known as the o.d.e. method and was originally introduced by Ljung [12].
In 2005, Benaı̈m, Hofbauer and Sorin [5] extended the dynamical systems approach to include the situation where the stochastic approximation algorithm
tracks a solution to the associated differential inclusion. Such algorithms are
called stochastic recursive inclusions. For a detailed exposition on SA, the
reader is referred to books by Borkar [8] and Kushner and Yin [11].
There are many applications where the aforementioned paradigms are inadequate. For example, the right hand side of a SA may require further averaging
or an additional recursion to evaluate it. An instance mentioned in Borkar [7]
is the ‘adaptive heuristic critic’ approach to reinforcement learning [10] that
requires a stationary value iteration executed between two policy iterations. To
solve such problems, Borkar [7] analyzed the two timescale SA algorithms. The

1

two timescale paradigm presented in Borkar [7] is inadequate if the coupled iterates are stochastic recursive inclusions. Such iterates arise naturally in many
learning algorithms, see for instance Section 5 of [13]. For another application
from convex optimization the reader is referred to Section 4 of this paper. Such
iterates also arise in applications that involve projections onto non-convex sets.
The first attempt at tackling this problem was made by Perkins and Leslie [13]
in 2012. They extended the two timescale scheme of Borkar [7] to include the
situation when the two iterates track solutions to differential inclusions.
Consider the following coupled recursion:


1
,
xn+1 = xn + a(n) un + Mn+1

(1)

2
yn+1 = yn + b(n) vn + Mn+1 ,

where un ∈ h(xn , yn ), vn ∈ g(xn , yn ), h : Rd+k → subsets of Rd and g :
Rd+k → subsets of Rk . Such iterates were analyzed in [13]. Further, as an
application a Markov decision process (MDP) based actor critic type learning
algorithm was also presented in [13].
In this paper we generalize the synchronous two timescale stochastic approximation scheme presented in [13]. We present sufficient conditions that are mild
and easily verifiable. For a complete list of assumptions used herein, the reader
is referred to Section 2.2 and for the analyses under these conditions the reader is
referred to Section 3. It is worth noting that the analysis of the faster timescale
proceeds in a predictable manner, however, the analysis of the slower timescale
presented herein is new to the literature to the best of our knowledge.
In convex optimization, one is interested in minimizing an objective function
(that is convex) subject to a few constraints. A solution to this optimization
problem is a set of vectors that minimize our objective function. Often this set
is referred to as a minimum set. In Section 4, we analyze the two timescale
SA algorithm corresponding to the Lagrangian dual of a primal problem. As
we shall see later, this analysis considers a family of minimum sets and as a
consequence of our framework these minimum sets are no longer required to be
singleton. In [9], Dantzig, Folkman and Shapiro presented sufficient conditions
for the continuity of minimum sets of continuous functions. We shall use results
from that paper to show that under some standard convexity conditions the
assumptions of Section 2.2 are satisfied. We then conclude from our main result,
Theorem 3, that the two timescale algorithm in question converges to a solution
to the dual problem.

2
2.1

Preliminaries and assumptions
Definitions and notations

The definitions and notations used in this paper are similar to those in Benaı̈m
et. al. [5], Aubin et. al. [1] and Borkar [8]. We present a few for easy reference.

2

Let H be an upper semi-continuous, set-valued map on Rd , where for any
x ∈ Rd , H(x) is compact and convex valued. Note that we say that H is upper
semi-continuous when xn → x, yn → y and yn ∈ H(xn ) ∀n implies y ∈ H(x).
Consider the differential inclusion (DI)
ẋ ∈ H(x).

(2)

P

We say that x ∈
if x is an absolutely continuous map that satisfies (2).
d
The set-valued semiflow
P Φ associated with (2) is defined on k[0, +∞) × R as:
Φt (x) = {x(t) | x ∈ , x(0) = x}. Let T × M ⊂ [0, +∞) × R and define
[
ΦT (M ) =
Φt (x).
t∈T , x∈M

M ⊆ Rd is P
invariant if for every x ∈ M there exists a complete trajectory
in M , say x ∈
with x(0) = x.
Let x ∈ Rd and A ⊆ Rd , then d(x, A) := inf{ka − yk | y ∈ A}. We define
the δ-open neighborhood of A by N δ (A) := {x | d(x, A) < δ}. The δ-closed
neighborhood of A is defined by N δ (A) := {x | d(x, A) ≤ δ}. T
Let M ⊆ Rd , the ω − limit set be given by ωΦ (M ) := t≥0 Φ[t,+∞) (M ).
T
Similarly the limit set of a solution x is given by L(x) = t≥0 x([t, +∞)).
A ⊆ Rd is an attractor if it is compact, invariant and there exists a neighborhood U such that for any ǫ > 0, ∃ T (ǫ) ≥ 0 such that Φ[T (ǫ),+∞) (U ) ⊂ N ǫ (A).
Such a U is called the fundamental neighborhood of A. The basin of attraction
of A is given by B(A) = {x | ωΦ (x) ⊂ A}. If B(A) = Rd , then the set is called
a globally attracting set. It is called Lyapunov stable if for all δ > 0, ∃ ǫ > 0
such that Φ[0,+∞) (N ǫ (A)) ⊆ N δ (A).
A set-valued map h : Rn → {subsets of Rm } is called a Marchaud map if it
satisfies the following properties:
(i) For each z ∈ Rn , h(z) is convex and compact.
(ii) (point-wise boundedness) For each z ∈ Rn , sup kwk < K (1 + kzk) for
w∈h(z)

some K > 0.
(iii) h is an upper semi-continuous map.
The open ball of radius r around 0 is represented by Br (0), while the closed ball
is represented by B r (0).

2.2

Assumptions

Recall that we have the following coupled recursion:


1
,
xn+1 = xn + a(n) un + Mn+1


2
yn+1 = yn + b(n) vn + Mn+1 ,

where un ∈ h(xn , yn ), vn ∈ g(xn , yn ), h : Rd+k → subsets of Rd
Rd+k → subsets of Rk .
We list below our assumptions.
(A1) h and g are Marchaud maps.
3

and g :

(A2) {a(n)}n≥0 and {b(n)}n≥0P
are two scalar sequences

Psuch that:
(a(n) + b(n)) = ∞,
a(n)2 + b(n)2 < ∞
a(n), b(n) > 0, for all n,
n≥0

n≥0

and limn→∞
1.

b(n)
a(n)

= 0. Without loss of generality, we let supn a(n), supn b(n) ≤

(A3) {Mni }n≥1 , i = 1, 2, are square integrable martingale difference sequences

1
2
with respect to the filtration Fn := σ xm , ym , Mm
,M
m : m ≤ n , n ≥ 0,
i
such that E[kMn+1
k2 |Fn ] ≤ K 1 + (kxn k + kyn k)2 , i = 1, 2, for some
constant K > 0. Without loss of generality assume that the same constant, K, works for both (A1) (in the property (ii) of Marchaud maps, see
section 2.1) and (A3).

(A4) supn {kxn k + kyn k} < ∞ a.s.
(A5) For each y ∈ Rk , the differential inclusion ẋ(t) ∈ h(x(t), y) has a globally
attracting set, Ay , that is also Lyapunov stable. Further, sup kxk ≤
x∈Ay

K (1 + kyk). The set-valued map λ : Rk → {subsets of Rd }, where
λ(y) = Ay , is upper semi-continuous.
!
S
g(x, y) . The convex
Define for each y ∈ Rk , a function G(y) := co
x∈λ(y)

closure of a set A ⊆ Rk , denoted by co(A), is closure of the convex hull of A,
i.e., the closure of the smallest convex set containing A. It will be shown later
that G is a Marchaud map.

(A6) ẏ(t) ∈ G(y(t)) has a globally attracting set, A0 , that is also Lyapunov
stable.
With respect to the faster timescale, the slower timescale iterates appear stationary, hence the faster timescale iterates track a solution to ẋ(t) ∈ h(x(t), y0 ),
where y0 is fixed (see Theorem 1). The y iterates track a solution to ẏ(t) ∈
G(y(t)) (see Theorem 2). It is worth noting that Theorems 1 & 2 only require
(A1) − (A5) to hold. Since G(·) is the convex closure of a union of compact
convex sets one can expect the set-valued map to be point-wise bounded and
convex. However, it is unclear why it should be upper semi-continuous (hence
Marchaud). In lemma 2 we prove that G is indeed Marchaud without any
additional assumptions.
Over the course of this paper we shall see that (A5) is the key assumption that
links the asymptotic behaviors of the faster and slower timescale iterates. It may
be noted that (A5) is weaker than the corresponding assumption - (B6)/(B6)′
used in [13]. For example, (B6)′ requires that λ(y) and ∪ g(x, y) be convex
x∈λ(y)

for every y ∈ Rk while (B6) requires that λ(y) be singleton for every y ∈ Rk .
The reader is referred to [13] for more details. Note that λ(y) being a singleton
is a strong requirement in itself since it is the global attractor of some DI. It
is observed in most applications that both λ(y) and ∪ g(x, y) will not be
x∈λ(y)

convex and therefore (B6)/(B6)′ are easily violated. Further, our application
discussed in Section 4 illustrates the same.
4

3

Proof of convergence

Before we start analyzing the coupled recursion given by (1), we prove a bunch
of auxiliary results.
Lemma 1. Consider the differential inclusion ẋ(t) ∈ H(x(t)), where H : Rn →
Rn is a Marchaud map. Let A be the associated globally attracting set that is
also Lyapunov stable. Then A is an attractor and every compact set containing
A is a fundamental neighborhood.
Proof. Since A is compact and invariant, it is left to prove the following: given
a compact set K ⊆ Rn such that A ⊆ K; for each ǫ > 0 there exists T (ǫ) > 0
such that Φt (K) ⊆ N ǫ (A) for all t ≥ T (ǫ).
Since A is Lyapunov stable, corresponding to N ǫ (A) there exists N δ (A),
where δ > 0, such that Φ[0,+∞) (N δ (A)) ⊆ N ǫ (A). Fix x0 ∈ K. Since A is a globally attracting set, ∃t(x0 ) > 0 such that Φt(x0 ) (x0 ) ⊆ N δ/4 (A). Further, from
the upper semi-continuity of flow it follows that Φt(x0 ) (x) ⊆ N δ/4 (Φt(x0 ) (x0 ))
for all x ∈ N δ(x0 ) (x0 ), where δ(x0 ) > 0, see Chapter 2 of Aubin and Cellina [1]. Hence we get Φt(x0 ) (x) ⊆ N δ (A). Further since A is Lyapunov stable,
we get Φ(t(x0 ),+∞] (x) ⊆ N ǫ (A). In this manner for each x ∈ K we calculate

t(x) and δ(x), the collection N δ(x) (x) : x ∈ K is an open cover for K. Since

K is compact, there exists a finite sub-cover N δ(xi ) (xi ) | 1 ≤ i ≤ m . For
T (ǫ) := max{t(xi ) | 1 ≤ i ≤ m}, we have Φ[T (ǫ),+∞) (K) ⊆ N ǫ (A).
In Theorem 2 we prove that the slower timescale trajectory asymptotically
tracks a solution to ẏ(t) ∈ G(y(t)). The following lemma ensures that the
aforementioned DI has at least one solution.
Lemma 2. The map G referred to in (A6) is a Marchaud map.
Proof. Fix an arbitrary y ∈ Rk . For any x ∈ λ(y), it follows from (A1) that
sup kzk ≤ K(1 + kxk + kyk).
z∈g(x,y)

From assumption (A5), we have that kxk ≤ K(1 + kyk). Substituting in the
above equation we may conclude the following:
sup kzk ≤ K (1 + K (1 + kyk) + kyk) = K(K + 1)(1 + kyk) ,
z∈g(x,y)

sup

z∈

S

kzk ≤ K(K + 1)(1 + kyk) ,

g(x,y)

x∈λ(y)

sup kzk ≤ K(K + 1)(1 + kyk).
z∈G(y)

We have thus proven that G is point-wise bounded. From the definition of G,
it follows that G(y) is convex and compact.
It remains to show that G is an upper semi-continuous map. Let zn → z and
yn → y in Rk with zn ∈ G(yn ), ∀ n ≥ 1. We need to show that z ∈ G(y). We
present a proof by contradiction. Since G(y) is convex and compact, z ∈
/ G(y)
5

implies that there exists a linear functional on Rk , say f , such that

sup
w∈G(y)

f (w) ≤ α − ǫ and f (z) ≥ α + ǫ, for some α ∈ R and ǫ > 0. Since zn → z,
there exists N such that for all n ≥ N , f (zn ) ≥ α + 2ǫ . In other words,
G(yn ) ∩ [f ≥ α + 2ǫ ] 6= φ for all n ≥ N . Here the notation [f ≥ a] is used to
denote the set {x | f (x) ≥ a}.
S
For the sake of convenience, we denote the set
g(x, y) by B(y). We
x∈λ(y)

claim that B(yn ) ∩ [f ≥ α + 2ǫ ] 6= φ for all n ≥ N . We prove this claim later,
for now we assume that the claim is true and proceed. Pick wn ∈ g(xn , yn ) ∩
[f ≥ α + 2ǫ ], where xn ∈ λ(yn ) and n ≥ N . It can be shown that {xn }n≥N
and {wn }n≥N are norm bounded sequences and hence contain convergent subsequences. Construct sub-sequences, {wn(k) }k≥1 ⊆ {wn }n≥N and {xn(k) }k≥1 ⊆
{xn }n≥N such that lim wn(k) = w and lim xn(k) = x. It follows from the
k→∞

k→∞

upper semi-continuity of g that w ∈ g(x, y) and from the upper semi-continuity
of λ that x ∈ λ(y), hence w ∈ G(y). Since f is continuous, f (w) ≥ α + 2ǫ . This
is a contradiction.
It remains to prove that B(yn ) ∩ [f ≥ α + 2ǫ ] 6= φ for all n ≥ N . Suppose
this were false, then ∃{m(k)}k≥1 ⊆ {n ≥ N } such that B(ym(k) ) ⊆ [f < α + 2ǫ ]
for each k ≥ 1. It can be shown that co(B(ym(k) )) ⊆ [f ≤ α + 2ǫ ] for each k ≥ 1.
Since zm(k) → z, ∃N1 such that for all m(k) ≥ N1 , f (zm(k) ) ≥ α + 3ǫ
4 . This is
a contradiction. Hence we get B(xn ) ∩ [f ≥ α + 2ǫ ] 6= φ for all n ≥ N .
It is worth noting that (A5) is a key requirement in the above proof. In the
next lemma, we show the convergence of the martingale noise terms.
Pn−1
1
Lemma 3. The sequences {ζn1 } and {ζn2 }, where ζn1 = m=0 a(m)Mm+1
and
P
n−1
2
2
ζn = m=0 b(m)Mm+1 , are convergent almost surely.

Proof. Although a proof of the above statement can be found in [2] or [8],
we provide one for the sake of completeness. We only prove the almost sure
convergence of ζn1 as the convergence of ζn2 can be similarly shown.
It is enough to show that
∞
X

i.e.,

m=0
∞
X

m=0

 1

1 2
a(m)2 E kζm+1
− ζm
k |Fm < ∞ a.s.,



1
a(m)2 E kMm+1
k2 |Fm < ∞ a.s.

From assumption (A3) it follows that
∞
X

m=0

∞
X



1
a(m)2 1 + (kxm k + kym k)2 .
k2 |Fm ≤ K
a(m)2 E kMm+1
m=0

From assumptions (A2) and (A4) it follows that
K

∞
X

m=0


a(m)2 1 + (kxm k + kym k)2 < ∞ a.s.

6

We now prove a couple of technical results that are essential to the proofs
of Theorems 1 and 2.
Lemma 4. Given any y0 ∈ Rk and ǫ > 0, there exists δ > 0 such that for all
x ∈ N δ (λ(y0 )), we have g(x, y0 ) ⊆ N ǫ (G(y0 )).
Proof. Assume the statement is not true. Then, ∃ δn ↓ 0 and xn ∈ N δn (λ(y0 ))
such that g(xn , y0 ) * N ǫ (G(y0 )), n ≥ 1. In other words, ∃γn ∈ g(xn , y0 ) and
γn ∈
/ N ǫ (G(y0 )) for each n ≥ 1. Since {xn } and {γn } are bounded sequences
there exist convergent sub-sequences, lim xn(k) = x and lim γn(k) = γ. Since
k→∞

k→∞

xn(k) ∈ N δn(k) (λ(y0 )) and δn(k) ↓ 0 it follows that x ∈ λ(y0 ) and hence g(x, y0 ) ⊆
G(y0 ). We also have that v ∈
/ N ǫ (G(y0 )) as vn(k) ∈
/ N ǫ (G(y0 )) for all k ≥ 1.
Since g is upper semi-continuous it follows that γ ∈ g(x, y0 ) and hence γ ∈
G(y0 ). This is a contradiction.
Lemma 5. Let x0 ∈ Rd and y0 ∈ Rk be such that the statement of lemma 4
is satisfied (with x0 in place of x). If lim xn = x0 and lim yn = y0 then ∃N
n→∞

such that ∀n ≥ N , g(xn , yn ) ⊆ N ǫ (G(y0 )).

n→∞

Proof. If not, ∃ {n(k)} ⊆ {n} such that lim n(k) = ∞ and g(xn(k) , yn(k) ) *
k→∞

N ǫ (G(y0 )). Without loss of generality assume that {n(k)} = {n}. In other
words, ∃γn ∈ g(xn , yn ) such that γn ∈
/ N ǫ (G(y0 )) for all n ≥ 1. Since {γn } is a
bounded sequence, it has a convergent sub-sequence, i.e., lim γn(m) = γ. Since
m→∞
lim xn(m) = x0 , lim yn(m) = y0 and g is upper semi-continuous it follows that
m→∞

m→∞

γ ∈ g(x0 , y0 ) and finally from lemma 4 we get that γ ∈ N ǫ (G(y0 )). This is a
contradiction.
Before we proceed let us construct trajectories, using (1), with respect to
Pn−1
the faster timescale. Define t(0) := 0, t(n) :=
i=0 a(i), n ≥ 1. The linearly
interpolated trajectory x(t), t ≥ 0, is constructed from the sequence {xn } as
follows: let x(t(n)) := xn and for t ∈ (t(n), t(n + 1)), let




t(n + 1) − t
t − t(n)
x(t) :=
x(t(n)) +
x(t(n + 1)). (3)
t(n + 1) − t(n)
t(n + 1) − t(n)
We construct a piecewise constant trajectory from the sequence {un } as follows:
u(t) := un for t ∈ [t(n), t(n + 1)), n ≥ 0.
Let us construct trajectories with respect
Pn−1 to the slower timescale in a similar
manner. Define s(0) := 0, s(n) :=
e(s(n)) := yn and
i=0 b(i), n ≥ 1. Let y
for s ∈ (s(n), s(n + 1)), let




s − s(n)
s(n + 1) − s
ye(s(n)) +
ye(s(n + 1)). (4)
ye(s) :=
s(n + 1) − s(n)
s(n + 1) − s(n)

Also ve(s) := vn for s ∈ [s(n), s(n + 1)), n ≥ 0, is the corresponding piecewise
constant trajectory.
For s ≥ 0, let xs (t), t ≥ 0, denote the solution to ẋs (t) = u(s + t) with the
initial condition xs (0) = x(s). Similarly, let y s (t), t ≥ 0, denote the solution to
ẏ s (t) = ve(s + t) with the initial condition y s (0) = ye(s).
7

The y iterate in recursion (1) can be re-written as


b(n) 2
b(n)
vn +
Mn+1 .
yn+1 = yn + a(n)
a(n)
a(n)

(5)

b(n)
b(n)
3
2
Define ǫ(n) := a(n)
vn and Mn+1
= a(n)
Mn+1
. It can be shown that the stochas3
tic iteration given by yn+1 = yn + a(n)Mn+1 satisfies the set of assumptions
given in Benaı̈m [2]. From (A1), (A2) and (A4) it follows that ǫ(n) → 0 almost
3
surely. Since ǫ(n) → 0 the recursion given by (5) and yn+1 = yn + a(n)Mn+1
have the same asymptotics. For a precise statement and proof the reader is
referred to lemma 2.1 of [7].
Define y(t(n)) := yn , where n ≥ 0 and y(t) for t ∈ (t(n), t(n + 1)) by




t(n + 1) − t
t − t(n)
y(t) :=
y(t(n)) +
y(t(n + 1)). (6)
t(n + 1) − t(n)
t(n + 1) − t(n)

The trajectory y(· ) can be seen as an evolution of the y iterate with respect to
the faster timescale, {a(n)}.
Lemma 6. Almost surely every limit point, y(· ), of {y(s+· ) | s ≥ 0} in
C([0, ∞), Rk ) as s → ∞ satisfies y(t) = y(0), t ≥ 0.
3
Proof. It can be shown that yn+1 = yn + a(n)Mn+1
satisfies the assumptions of
Benaı̈m [2]. Hence the corresponding linearly interpolated trajectory tracks the
solution to ẏ(t) = 0. The statement of the lemma then follows trivially.

Lemma 7. For any T > 0, lim sup kx(s+t)−xs (t)k = 0 and lim sup ke
y(s+
s→∞t∈[0,T ]

s→∞t∈[0,T ]

s

t) − y (t)k = 0, a.s.
Proof. In order to prove the above lemma, it enough to prove the following:
lim

sup

kx(t(n + m)) − xt(n) (t(n + m) − t(n))k = 0 and

lim

sup

ke
y(s(n + m)) − y s(n) (s(n + m) − s(n))k = 0 a.s.

t(n)→∞ 0≤t(n+m)−t(n)≤T

s(n)→∞ 0≤s(n+m)−s(n)≤T

Note the following:
x(t(n + m)) = x(t(n)) +

m−1
X
k=0



1
,
a(n + k) u(t(n + k)) + Mn+k+1

xt(n) (t(n + m) − t(n)) = x(t(n)) +

Z

t(n+m)−t(n)

u(t(n) + z) dz,

0

xt(n) (t(n + m) − t(n)) = x(t(n)) +

Z

t(n+m)

u(z) dz.

(7)

t(n)

From (7), we get,
kx(t(n + m)) − xt(n) (t(n + m) − t(n))k =
m−1
m−1
m−1
X Z t(n+k+1)
X
X
1
u(z) dz +
a(n + k)Mn+k+1
.
a(n + k)u(t(n + k)) −
k=0

k=0

t(n+k)

8

k=0

The R.H.S. of the above equation equals
m−1
X

a(n + k)u(t(n + k)) =

k=0

Pm−1
k=0

1
as
a(n + k)Mn+k+1

m−1
X Z t(n+k+1)
k=0

u(z) dz.

t(n+k)

Pn−1
1
Since ζn1 := m=0 a(m)Mm+1
, n ≥ 1, converges a.s., the first part of claim
follows.
The second part, for the y iterates, can be similarly proven.
From assumptions (A1) and (A4) it follows that {xr (· ) | r ≥ 0} and {y r (· ) | r ≥
0} are equicontinuous and pointwise bounded families of functions. By the
Arzela-Ascoli theorem they are relatively compact in C([0, ∞), Rd ) and C([0, ∞), Rk )
respectively. From lemma 7 it then follows that {x(r+· ) | r ≥ 0} and {e
y(r+· ) | r ≥
0} are also relatively compact, see (3) and (4) for the definitions of x(· ) and
ye(· ), respectively.

3.1

Convergence in the faster timescale

The following theorem and its proof are similar to Theorem 2 from Chapter 5
of Borkar [8]. We present a proof for the sake of completeness.
Theorem 1. Almost surely, every limit point of {x(r+· ) | r ≥ 0} in C([0, ∞), Rd )
Rt
is of the form x(t) = x(0) + 0 u(z) dz, where u is a measurable function such
that u(t) ∈ h(x(t), y(0)), t ≥ 0, for some fixed y(0) ∈ Rk .
Proof. Fix T > 0, then {u(r + t) | t ∈ [0, T ]}, r ≥ 0 can be viewed as a subset
of L2 ([0, T ], Rd ). From (A1) and (A4) it follows that the above is uniformly
bounded and hence weakly relatively compact. Let {r(n)} be a sequence such
that the following hold:
(i) lim r(n) = ∞.
n→∞

(ii) There exists some x(· ) ∈ C([0, ∞), Rd ) such that x(r(n)+· ) → x(· ) in
C([0, ∞), Rd ). This is because {x(r+· ) | r ≥ 0} is relatively compact in
C([0, ∞), Rd ).
(iii) y(r(n)+· ) → y(· ) in C([0, ∞), Rk ) for some y ∈ C([0, ∞), Rk ). It follows
from lemma 6 that y(t) = y(0) for all t ≥ 0.
(iv) u(r(n)+· ) → u(· ) weakly in L2 ([0, T ], Rd ).
From lemma 7, it follows that xr(n) (· ) → x(· ) in C([0, ∞), Rd ), and we have
Rt
Rt
that 0 u(r(n) + z) dz → 0 u(z) dz for t ∈ [0, T ]. Letting n → ∞ in
Z t
r(n)
r(n)
u(r(n) + z) dz, t ∈ [0, T ],
x
(t) = x
(0) +
0

Rt

we get x(t) = x(0) + 0 u(z) dz, t ∈ [0, T ].
Since u(r(n)+· ) → u(· ) weakly in L2 ([0, T ], Rd), there exists {n(k)} ⊂ {n}
such that n(k) ↑ ∞ and
N
1 X
u(r(n(k))+· ) → u(· )
N
k=1

9

strongly in L2 ([0, T ], Rd ). Further, there exist {N (m)} ⊂ {N } such that N (m) ↑
∞ and
N (m)
X
1
u(r(n(k))+· ) → u(· )
(8)
N (m)
k=1

a.e. in [0, T ].
Define [t] := max{t(n) | t(n) ≤ t}. If we fix t0 ∈ [0, T ] such that (8) holds,
then u(r(n(k)) + t0 ) ∈ h(x([r(n(k)) + t0 ]), y([r(n(k)) + t0 ])) for k ≥ 1. Since
lim kx(r(n(k)) + t0 ) − x([r(n(k)) + t0 ])k = 0, it follows that lim x([r(n(k)) +
k→∞

n(k)→∞

t0 ]) = x(t0 ), and similarly, we have that lim y([r(n(k)) + t0 ]) = y(0). Since h is
k→∞

upper semi-continuous it follows that lim d (u(r(n(k)) + t0 ), h(x(t0 ), y(0))) =
k→∞

0. The set h(x(t0 ), y(0)) is compact and convex, hence it follows from (8) that
u(t0 ) ∈ h(x(t0 ), y(0)).

3.2

Convergence in the slower timescale

Theorem 2. For any ǫ > 0, almost surely any limit point of {e
y(r+· ) | r ≥ 0}
Rt
k
in C([0, ∞), R ) is of the form y(t) = y(0) + 0 v(z) dz, where v is a measurable
function such that v(t) ∈ N ǫ (G(y(t))), t ≥ 0.
Proof. Fix T > 0. As before let {r(n)}n≥1 be a sequence such that the following
hold:
(i) lim r(n) = ∞.
n→∞

(ii) ye(r(n)+· ) → y(· ) in C([0, ∞), Rk ), where y(· ) ∈ C([0, ∞), Rk ).

(iii) e
v (r(n)+· ) → v(· ) weakly in L2 ([0, T ], Rk ).

Also, as before, we have the following:

(i) There exists {n(k)} ⊆ {n} such that
in L2 ([0, T ], Rd ) as N → ∞.

1
N

PN

k=1

ve(r(n(k))+· ) → v(· ) strongly

(ii) There exist {N (m)} ⊂ {N } such that N (m) ↑ ∞ and
N (m)
X
1
ve(r(n(k))+· ) → v(· )
N (m)

(9)

k=1

a.e. on [0, T ].

Define [s]′ := max{s(n) | s(n) ≤ s}. Construct a sequence {m(n)}n≥1 ⊆ N
such that s(m(n)) = [r(n) + t0 ]′ for each n ≥ 1. Observe that y(t(m(n))) =
ye(s(m(n))) and ve(r(n) + t0 ) ∈ g(x(t(m(n))), y(t(m(n)))).
Choose t0 ∈ (0, T ) such that (9) is satisfied. If we show that ∃ N such that
for all n ≥ N , g(x(t(m(n))), y(t(m(n)))) ⊆ N ǫ (G(y(t0 ))) then (9) implies that
v(t0 ) ∈ N ǫ (G(y(t0 ))).
It remains to show the existence of such a N . We present a proof by contradiction. We may assume without loss of generality that for each n ≥ 1,
g(x(t(m(n))), y(t(m(n)))) * N ǫ (G(y(t0 ))), i.e., ∃ γn ∈ g(x(t(m(n))), y(t(m(n))))
such that γn ∈
/ N ǫ (G(y(t0 ))). Let S1 be the set on which (A4) is satisfied
10

and S2 be the set on which lemma 3 holds. Clearly P (S1 ∩ S2 ) = 1. For
each ω ∈ S1 ∩ S2 , ∃ R(ω) < ∞ such that supn kxn (ω) + yn (ω)k ≤ R(ω) and
supn K(1 + kyn (ω)k) ≤ R(ω). In what follows we merely use R and the dependence on ω (sample path) is understood to be implicit. From lemma 1 it
follows that corresponding to ẋ(t) ∈ h(x(t), y(t0 )) and some δ > 0 there exists
T0 , possibly dependent on R, such that for all t ≥ T0 , Φt (x0 ) ∈ N δ (λ(y(t0 )))
for all x0 ∈ B R (0).
We construct a new sequence {l(n)}n≥1 from {m(n)}n≥1 such that t(l(n)) =
min{t(m) | |t(m(n))−t(m)| ≤ T0 }. Since {x(r+· ) | r ≥ 0} is relatively compact
in C([0, ∞), Rd ), it follows that x(t(l(n))+· ) → x(· ) in C([0, T0 ], Rd ). From
lemma 6 we can conclude that y(t(l(n))+· ) → y(· ) in C([0, T0 ], Rk ), where
y(t) = y(t0 ) for all t ∈ [0, T0 ]. lemma 6 only asserts that the limiting function is a constant, we recognize this constant to be y(t0 ) since ky(t(l(n)) +
T0 ) − y(t(m(n)))k → 0 and y(t(l(n)) + T0 ) → y(t0 ). Note that in the foregoing
discussion we can only assert the existence of convergent subsequences, again
for the sake of convenience we assume that the sequences at
R t hand are both
convergent. It follows from Theorem 1 that x(t) = x(0) + 0 u(z) dz, where
u(t) ∈ h(x(t), y(t0 )). Since x(0) ∈ B R (0) it follows that x(T0 ) ∈ N δ (λ(y(t0 ))).
From lemma 4 we get g(x(T0 ), y(t0 )) ⊆ N ǫ (G(y(t0 ))). Since kx(t(m(n))) −
x(t(l(n)) + T0 )k → 0 it follows that x(t(m(n))) → x(T0 ). It follows from lemma
5 that ∃N such that for n ≥ N , g(x(t(m(n))), y(t(m(n)))) ⊆ N ǫ (G(y(t0 ))).
This is a contradiction.
A direct consequence of the above theorem is that almost surelyR any limit
t
point of {e
y(r+· ) | r ≥ 0} in C([0, ∞), Rk ) is of the form y(t) = y(0)+ 0 v(z) dz,
where v is a measurable function such that v(t) ∈ G(y(t)), t ≥ 0.

3.3

Main result

Theorem 3. Under assumptions (A1) − (A6), almost surely the set of accumulation points is given by


[
{(x, y) | x ∈ λ(y)} .
(10)
(x, y) | lim d ((x, y), (xn , yn )) = 0 ⊆
n→∞

y∈A0

Proof. The statement follows directly from Theorems 1 and 2.
Note that assumption (A6) allows us to narrow the set of interest. If
(A6)
S does not hold then we can only conclude that the R.H.S. of (10) is
{(x, y) | x ∈ λ(y)}. On the other hand if (A6) holds and A0 consists of
y∈Rk

a single point, say y0 , then the R.H.S. of (10) is {(x, y0 ) | x ∈ λ(y0 )}. Further,
if λ(y0 ) is of cardinality one then the R.H.S. of (10) is just (λ(y0 ), y0 ).

Remark:It may be noted that all proofs and conclusions in this paper will go
through if (A1) is weakened to let g be upper semi-continuous and g(x, · ) be
Marchaud on Rk for each fixed x ∈ Rd .

11

4

Application: An SA algorithm to solve the
Lagrangian dual problem

Let f : Rd → R and g : Rd → Rk be two given functions. We want to minimize
f (x) subject to the condition that g(x) ≤ 0 (every component of g(x) is nonpositive). This problem can be stated in the following primal form:
inf sup (f (x) + µT g(x)) .

(11)

x∈Rd µ∈Rk
µ≥0

Let us consider the following two timescale SA algorithm to solve the primal
(11):


1
,
µn+1 = µn + a(n) ∇µ (f (xn ) + µTn g(xn )) + Mn+1


(12)
T
2
xn+1 = xn − b(n) ∇x (f (xn ) + µn g(xn )) + Mn+1 .

P
P
P
2
< ∞,
where, a(n), b(n) > 0,
n≥0 a(n)
n≥0 b(n) = ∞,
n≥0 a(n) =
P
b(n)
2
n≥0 b(n) < ∞ and a(n) → 0. Without loss of generality assume that
sup a(n), b(n) ≤ 1. The sequences {Mn1 }n≥1 and {Mn2 }n≥1 are suitable marn

tingale difference noise terms.
Suppose there exists x0 ∈ Rd such that g(x0 ) ≥ 0, then µ = (∞, . . . , ∞)
maximizes f (x0 ) + µT g(x0 ). With respect to the faster timescale (µ) iterates
the slower timescale (x) iterates can be viewed as being “quasi-static”, see [8]
for more details. It then follows from the aforementioned observation that the
µ iterates cannot be guaranteed to be stable. In other words, we cannot use
(12) to solve the primal problem.
If strong duality holds then solving (11) is equivalent to solving its dual given
by:
sup inf (f (x) + µT g(x)) .
(13)
µ∈Rk x∈Rd
µ≥0

Further, the two timescale scheme to solve the dual problem is given by:


2
xn+1 = xn − a(n) ∇x (f (xn ) + µTn g(xn )) + Mn+1
,


(14)
T
1
µn+1 = µn + b(n) ∇µ (f (xn ) + µn g(xn )) + Mn+1 .

Note that (14) is obtained by flipping the timescales of (12). Strong duality can
be enforced if we assume the following:
(S1) f (x) = xT Qx + bT x + c, where Q is a positive semi-definite d × d matrix,
b ∈ Rd and c ∈ R.
(S2) g = A, where A is a k × d matrix.
(S3) f is bounded from below.
The reader is referred to Bertsekas [6] for further details. For the purposes of
this section we assume the following:
12

(S1) − (S3) are satisfied.
P
i
(A3)′
n≥0 a(n)Mn+1 < ∞ a.s., where i = 1, 2.

The sole purpose of (A3) in Section 2.2 is to ensure the convergence of the
martingale noise terms i.e., (A3)′ holds. It is clear that (14) satisfies (A1) since
(S1) − (S3) hold while (A2) is the step size assumption that is enforced.

The stability of the µ iterates in (14) directly follows from strong duality and
(A3)′ . The µ iterates are “quasi-static” with respect to the x iterates. Further,
since f (x) + µT0 g(x) is a convex function (from (S1) and (S2)), for a fixed µ0 ,
f (x) + µT0 g(x) achieves its minimum “inside” Rd . Hence, the stability of the
x iterates will follow from that of the µ iterates and (A3)′ . In other words,
(14) satisfies (A1), (A2), (A3)′ & (A4), see Section 2.2 for the definitions of
(A1), (A2) and (A4).
For a fixed µ0 , the minimizers of f (x) + µT0 g(x) constitute the global attractor
of the o.d.e., ẋ(t) = −∇x (f (x) + µT0 g(x)). Our paradigm comes in handy when
this attractor set is NOT singleton, which is generally the case. In other words,
we can define the following set valued map: λm : Rk → Rd , where λm (µ0 ) is the
global attractor of ẋ(t) = −∇x (f (x) + µT0 g(x)).
Now we check that (14) satisfies (A5). To do so it is enough to ensure that
λm is an upper semi-continuous map. Recall that λm (µ) is the minimum set
of f (x) + µT g(x) for each µ ∈ Rk . Dantzig, Folkman and Shapiro [9] studied
the continuity of minimum sets of continuous functions. A wealth of sufficient
conditions can be found in [9] which when satisfied by the functions guarantee
“continuity” of the corresponding minimum sets. In our case since (S1) − (S3)
are satisfied, Corollary I.2.3 of [9] guarantees upper semi-continuity of λm .
Since (A1)-(A5) are satisfied by (14), it follows from Theorems 1 & 2 that:
(I) Almost surely every limit point of {x(r+· ) | r ≥ 0} in C([0, ∞), Rd ) is of
Rt
the form x(t) = x(0) + 0 ∇x (f (x(t)) + µT0 g(x(t))) dt for some x(0) ∈ Rd
and some µ0 ∈ Rk .
(II) Almost surely, any limit point of {e
µ(r+· ) | r ≥ 0} in C([0, ∞), Rk ) is of the
Rt
form µ(t) = µ(0) + 0 ν(z) dz for some measurable function ν with ν(t) ∈
G(µ(t)), t ≥ 0 and G(µ(t)) = co ({∇µ (f (x) + µ(t)T g(x)) | x ∈ λm (µ(t))}).
For the construction of x(· ) and µ
e(· ) see equations (3) and (4) respectively. If in
addition, (14) satisfies (A6) i.e., ∃ Aµ ⊂ Rk such that it is the global attractor
of µ(t) ∈ G(µ(t)), then it follows from Theorem 3 that: almost surely any accumulation point of {(xn , yn ) | n ≥ 0} belongs to the set A := ∪ {(x, µ) | x ∈
µ∈Am

λm (µ)}. The attractor Aµ is the maximum set of H(µ) := inf (f (x) + µT g(x))
x∈Rd

subject to µ ≥ 0. It may be noted that H is a concave function that is bounded
above as a consequence of strong duality. For any (x∗ , µ∗ ) ∈ A we have that
f (x∗ ) + (µ∗ )T g(x∗ ) = sup inf f (x) + µT g(x).
µ∈Rk x∈Rd
µ≥0

13

In other words, almost surely the two timescale iterates given by (14) converge
to a solution of the dual (13). It follows from strong duality that they almost
surely converge to a solution of the primal (11).

5

Conclusions

In this paper we have presented a framework for the analysis of two timescale
stochastic approximation algorithms with set valued mean fields. Our framework generalizes the one by Perkins and Leslie. We note that the analysis of
the faster timescale proceeds in a predictable manner but the analysis of the
slower timescale is new to the literature to the best of our knowledge. As an application we analyze the two timescale scheme that arises from the Lagrangian
dual problem in optimization using our framework. Our framework is applicable
even when the minimum sets are not singleton.

References
[1] J. Aubin and A. Cellina. Differential Inclusions: Set-Valued Maps and
Viability Theory. Springer, 1984.
[2] M. Benaı̈m. A dynamical system approach to stochastic approximations.
SIAM J. Control Optim., 34(2):437–472, 1996.
[3] M. Benaı̈m. Dynamics of stochastic approximation algorithms. Séminaire
de Probabilités XXXIII, Lecture Notes in Mathematics, Springer, 1709:1–
68, 1999.
[4] M. Benaı̈m and M. W. Hirsch. Asymptotic pseudotrajectories and chain
recurrent flows, with applications. J. Dynam. Differential Equations, 8:141–
176, 1996.
[5] M. Benaı̈m, J. Hofbauer, and S. Sorin. Stochastic approximations and
differential inclusions. SIAM Journal on Control and Optimization, pages
328–348, 2005.
[6] D.P. Bertsekas. Convex Optimization Theory. Athena Scientific optimization and computation series. Athena Scientific, 2009.
[7] V. S. Borkar. Stochastic approximation with two time scales. Syst. Control
Lett., 29(5):291–294, 1997.
[8] V. S. Borkar. Stochastic Approximation: A Dynamical Systems Viewpoint.
Cambridge University Press, 2008.
[9] G. B. Dantzig, J. Folkman, and N. Shapiro. On the continuity of the
minimum set of a continuous function. Journal of Mathematical Analysis
and Applications, 17(3):519 – 548, 1967.
[10] Sathiya S. Keerthi and B. Ravindran. A tutorial survey of reinforcement learning. Indian Academy of Sciences, Proc. in Engineering Sciences,
19:851–889, 1994.

14

[11] H. Kushner and G.G. Yin. Stochastic Approximation and Recursive Algorithms and Applications. Springer, 2003.
[12] L. Ljung. Analysis of recursive stochastic algorithms. Automatic Control,
IEEE Transactions on, 22(4):551–575, 1977.
[13] S. Perkins and D.S. Leslie. Asynchronous stochastic approximation with
differential inclusions. Stochastic Systems, 2(2):409–446, 2012.

15

