Analysis of stochastic approximation schemes with set-valued maps in the absence of a stability guarantee and their stabilization
Vinayaka G. Yaji Shalabh Bhatnagar

















 


shapes.geometric, arrows,calc


theoremTheorem[section]
lemma[theorem]Lemma
proposition[theorem]Proposition
corollary[theorem]Corollary

proof[1][Proof]

  #1
definition[1][Definition]

  #1
example[1][Example]

  #1
remark[1][Remark]

  #1


      
startstop = [rectangle, rounded corners, minimum width=3cm, minimum height=1cm,text centered, draw=black, fill=red!30]
io = [trapezium, trapezium left angle=70, trapezium right angle=110, minimum width=3cm, minimum height=1cm, text centered,draw=black, fill=blue!30]
process = [rectangle, minimum width=3cm, minimum height=1cm, text centered, draw=black, fill=orange!30]
decision = [diamond, minimum width=3cm, minimum height=1cm, draw=black, fill=green!30]
arrow = [thick,->,>=stealth]









Analysis of stochastic approximation schemes with set-valued maps in the absence of a stability guarantee and their stabilization
    Vinayaka G. Yaji and Shalabh Bhatnagar,
 Department of Computer Science and Automation,
        
 Indian Institute of Science, Bangalore.

        vgyaji@gmail.com, shalabh@csa.iisc.ernet.in
    December 30, 2023
==================================================================================================================================================================================================


In this paper, we analyze the behavior of stochastic approximation schemes with set-valued maps in the absence of a stability guarantee. We prove that after a large number of iterations if the stochastic approximation process enters the domain of attraction of an attracting set it gets locked into the attracting set with high probability. We demonstrate that the above result is an effective instrument for analyzing stochastic approximation schemes in the absence of a stability guarantee, by using it obtain an alternate criteria for convergence in the presence of a locally attracting set for the mean field and by using it to show that a feedback mechanism, which involves resetting the iterates at regular time intervals, stabilizes the scheme when the mean field possesses a globally attracting set, thereby guaranteeing convergence. The results in this paper build on the works of V.S. Borkar, C. Andrieu and H. F. Chen , by allowing for the presence of set-valued drift functions.   




§ INTRODUCTION


It is well known that several optimization and control tasks can be cast as a root finding problem. That is, given f:ℝ^d→ℝ^d, one needs to find x^*∈ℝ^d, such that f(x^*)=0 (given such a point exists). Due to practical considerations, one usually has access to noisy measurements/estimations of the function whose root needs to be determined. An approach to solving such a problem with noisy measurements of f, is given by the recursion,

    X_n+1-X_n-a(n)M_n+1=a(n)f(X_n),

where  {M_n}_n≥1, denotes the noise arising in the measurement of f and having fixed an initial condition (X_0∈ℝ^d), the iterates {X_n}_n≥1 are generated according to recursion (<ref>). <cit.> under certain assumptions which include the Lipschitz continuity of the function f, boundedness of the iterates along almost every sample path (that is ℙ(sup_n≥0X_n<∞)=1) and a condition which ensures that the eventual contribution of the additive noise terms is negligible, showed that the linearly interpolated trajectory of recursion (<ref>) tracks the flow of the ordinary differential equation (o.d.e.) given by,

    dx/dt=f(x).

Such a trajectory is called an asymptotic pseudotrajectory for the flow of  o.d.e.(<ref>) (for a precise definition see <cit.>). Suppose the set of zeros of f is a globally asymptotically stable set for the flow of o.d.e. (<ref>), then it was shown that the limit set of an asymptotic pseudotrajectory was contained in such a set and hence the iterates {X_n}_n≥0 converge in the limit to a root of the function f.

 In order to analyze recursion (<ref>) when the function f is no longer Lipschitz continuous or even continuous, but is just measurable satisfying the linear growth property, that is for every x∈ℝ^d, f(x)≤ K(1+x) for some K>0, or when there is a non-additive noise/control component taking values in a compact set whose law is not known 
(in which case the recursion (<ref>) takes the form X_n+1-X_n-a(n)M_n+1=a(n)f(X_n,U_n), where U_n denotes the noise/control), the above mentioned o.d.e. method needed to be extended to recursions with much weaker requirements on the function f. This was accomplished in <cit.>, where the asymptotic behavior of the recursion given by,

    X_n+1-X_n-a(n)M_n+1∈ a(n)F(X_n),

was studied, where F is a set-valued map satisfying some conditions (while the other quantities have same interpretation as in (<ref>)). Under the assumption of stability of iterates (that is ℙ(sup_n≥0X_n<∞)=1) and appropriate conditions on the additive noise terms, in <cit.>, it was shown that the linearly interpolated trajectory of recursion (<ref>) tracks the flow of the differential inclusion (d.i.) given by, 

    dx/dt∈ F(x).

We refer the reader to <cit.> for a detailed argument as to how the measurable case and the case with unknown noise/control be recast in the form of recursion (<ref>). For a brief summary of the convergence analysis of recursion (<ref>) we refer the reader to section <ref> of this paper. 

Common to the analysis of both recursion (<ref>) and (<ref>) is the assumption on the stability of the iterates, that is ℙ(sup_n≥0X_n<∞)=1. The condition of stability is highly non-trivial and difficult to verify. Over the years significant effort has gone into providing sufficient conditions for stability (see <cit.>, <cit.>). In <cit.>, it was shown that for recursion (<ref>), in the absence of stability guarantee, the probability of converging to an attracting set of o.d.e. (<ref>) given that the iterates lie in a neighborhood of it converged to one as the index (n) in which the iterate entered the neighborhood of the attracting set increased to infinity. This probability of the iterates converging to an attracting set given that the iterate lies in a neighborhood of it is called the lock-in probability and in <cit.> a lower bound for the same was used to obtain sample complexity bounds for recursion (<ref>). Further a tighter lower bound for the lock-in probability was derived in <cit.> under a slightly stronger noise assumption and used to obtain convergence guarantee when the law of the iterates are tight. In this paper we extend the results in <cit.> to the case of stochastic approximation schemes with set-valued maps as in recursion (<ref>).



 §.§ Contributions and organization of the paper
   
We first provide a lower bound for the lock-in probability of stochastic approximation schemes with set-valued maps as in recursion (<ref>). The bound is derived under an assumption on the additive noise terms which is stronger than the corresponding in <cit.>, which is necessitated due to the lack of Lipschitz continuity of the drift function F. We establish that,

    ℙ(X_n→ A as n→∞|X_n_0∈𝒪')≥ 1-2de^-K̃/b(n_0),

for n_0 large, where, A⊆ℝ^d, denotes an attracting set of DI <ref>, 𝒪' is an open neighborhood of A with compact closure, K̃ is some positive constant and {b(n)}_n≥0 is a sequence of reals converging to zero, which are step size dependent. 

Having summarized the convergence analysis under stability in section <ref>, we state the lock-in probability bound in section <ref> and provide a few implications of the same. Using the lock-in probability result we provide an alternate criteria for convergence in the presence of a locally attracting set which removes the need to verify stability. A detailed comparison between the obtained convergence guarantee and the corresponding in the presence of stability is also provided. 

Proof of the lock-in probability result is presented in section <ref>. The proof relies heavily on the insights obtained from the analysis in <cit.> for single-valued maps. From the analysis in <cit.>, it is evident that the Lipschitz continuity of the drift function f plays a crucial role in obtaining events and decoupling error contributions which in turn are necessary to obtain the bound in the inequality above. But in the recursion studied in this paper (that is recursion (<ref>)), the drift function F is set-valued and the assumptions under which we study the said recursion (which are summarized in section <ref>), the drift function F is not even continuous. We overcome this problem by first obtaining a sequence of locally Lipschitz continuous set-valued maps which approximate the drift function F from above and then parameterizing them using the Stiener selection procedure. The associated results are summarized in section <ref>. This enables us to write recursion (<ref>) in the form of recursion (<ref>), but with locally Lipschitz continuous drift functions. Further the relation between the solutions of differential inclusions with the approximating set-valued maps as their vector field and those of DI (<ref>), is established in section <ref>. Having written recursion (<ref>) in the form of recursion (<ref>), we then collect sample paths of interest in section <ref>. Along the sample paths that are collected the iterates are such that, having entered a neighborhood of the attracting set at iteration n_0, the iterates will infinitely often enter the said neighborhood and the time elapsed between successive visits to the neighborhood of the attracting set can be upper bounded by a constant which is mean field dependent. Further we show that the probability of occurrence of such sample paths can be lower bounded by error contributions due to additive noise terms alone after a large number of iterations. Using the concentration inequality for martingale sequences we obtain the lock-in probability bound in section <ref>. 

Using the lock-in probability result we design a feedback mechanism which enables us to stabilize the stochastic approximation scheme in the presence of a globally attracting set for DI (<ref>). The feedback mechanism involves resetting the iterates at regular time intervals if they are found to be lying outside a certain compact set. This approach to stabilization has been studied in various forms for stochastic approximation schemes with single-valued drift functions as in recursion (<ref>), in <cit.>, <cit.>, <cit.> and <cit.> to name a few. We extend the same to the case of set-valued drift functions. The main idea in the analysis of such a scheme is to show that along almost every sample path of the modified recursion, the number of resets that are performed is finite, thereby guaranteeing that eventually the iterates lie within a compact set. We observe that the lock-in probability result (to be precise the approach adopted to obtain the lock-in probability result) plays a central role in showing that the number of resets performed remain finite. Having shown that the iterates eventually lie within a compact set, we use the convergence arguments from <cit.> to argue that the iterates generated by the modified scheme converge to the globally attracting set of DI (<ref>). The modified scheme is presented and explained in detail in section <ref>. The proof of the finite resets theorem is presented in section <ref>. The procedure employed to collect sample paths in the proof of the lock-in probability result can be used to collect sample paths where only finite number of resets have occurred in the modified scheme and this in turn enables  us show that the number of resets are finite almost surely.

Finally, we conclude by providing a few directions for future work in section <ref>.


§ RECURSION AND ASSUMPTIONS


Let (Ω,ℱ,ℙ) be a probability space and {X_n}_n≥0 be a sequence of ℝ^d-valued 
random variables on Ω, such that for every n≥0,

    X_n+1-X_n-a(n)M_n+1∈ a(n)F(X_n),

where, 

 
  (A1) F:ℝ^d→{subsets of ℝ^d} is a set-valued map which for every x∈ℝ^d 
 satisfies the following:
 
 
  (i) F(x) is a convex and compact subset of ℝ^d,
 
  (ii) there exists K>0 (independent of x) such that sup_y∈ F(x)y≤ K(1+x),
 
  (iii) for every ℝ^d-valued sequence {x_n}_n≥1 converging to x and for every sequence {y_n∈ F(x_n)}_n≥1 
 converging to y∈ℝ^d, we have that y∈ F(x).
 
 
  (A2) {a(n)}_n≥0 is a sequence of positive real numbers satisfying,
 
 
  (i) ∑_n=0^∞a(n)=∞,
 
  (ii) ∑_n=0^∞(a(n))^2<∞.
 
 
  (A3) {M_n}_n≥1 is a ℝ^d-valued, martingale difference sequence with respect to the filtration {ℱ_n:=σ(X_m,M_m, m≤ n)}. Furthermore, {M_n}_n≥1 are  such that, 
 
    M_n+1≤ K(1+x_n) a.s.,

 for every n≥0, for some constant K>0.


Assumption (A1) ensures that the set-valued map F is a Marchaud map. The condition (A1)(ii) is called the linear growth property since it ensures that the size of the sets F(x) grow linearly with respect to the distance from the origin. The condition (A1)(iii) is called the closed graph property since it states that the graph of the set-valued map F, defined as, 

    {(x,y)∈ℝ^2d:x∈ℝ^d, y∈ F(x)},

is a closed subset of ℝ^2d. The map F being a Marchaud map ensures that the differential inclusion (DI) given by,

    dx/dt∈ F(x),

possesses at least one solution through every initial condition. By a solution of DI (<ref>) with initial condition x_0∈ℝ^d, we mean an absolutely continuous function x:ℝ→ℝ^d such that x(0)=x_0 and for almost every t∈ℝ, dx(t)/dt∈ F(x(t)). DI (<ref>) is the mean field of recursion (<ref>) and its dynamics play an important role in describing the asymptotic behavior of recursion (<ref>). 

Assumption (A2) states the conditions to be satisfied by the step size sequence {a(n)}_n≥0. Square summability (that is (A2)(ii)) is needed later in the analysis for obtaining a probability bound on certain tail events associated with the additive noise terms {M_n}_n≥1. 

 Assumption (A3),  defines the martingale noise model. These terms denote the noise arising in the measurement of F(·). This condition holds in several reinforcement learning applications (see <cit.>)
 
Clearly when {M_n}_n≥1 are i.i.d. zero mean and bounded, assumption (A3) is satisfied. Further, since the drift function in recursion (<ref>) is a set-valued map, scenarios where the measurement noise terms possess a bounded bias can be recast in the form of recursion (<ref>) as explained below.

Consider the recursion given by,

    X_n+1-X_n-a(n)M_n+1-a(n)η_n+1=a(n) f(X_n), n≥0,

where f:ℝ^d→ℝ^d is a single-valued Lipschitz continuous map, for every n≥0, η_n+1 denotes the bias in the measurement noise. Let the bias terms {η_n}_n≥1 be bounded by a positive constant, say ϵ>0 (that is, for every n≥1, η_n≤ϵ). Then, recursion (<ref>) can be written in the form of recursion (<ref>) with set-valued map F, given by, F(x)={f(x)+η: η≤ϵ}, for every x∈ℝ^d. We refer the reader to <cit.> for several other variants of the standard stochastic approximation scheme which can be analyzed with the help of recursion (<ref>).
 
  




§ LOCK-IN PROBABILITY FOR STOCHASTIC RECURSIVE INCLUSIONS


In order to state the main result of this paper, definition of the flow of  a DI,  an attracting set for such a dynamical system are needed. We recall these notions below and we state them with respect to the mean field of recursion (<ref>) (for a detailed description and associated results see <cit.>).

The  flow of DI (<ref>) is given by the set-valued map Φ:ℝ×ℝ^d→{subsets of ℝ^d}, where for every (t,x)∈ℝ×ℝ^d, 

    Φ(t,x):={x(t)∈ℝ^d:x(·) is a solution of DI (<ref>) with x(0)=x}.


A compact set A⊂ℝ^d is an attracting set for the flow of DI (<ref>), if there exists an open  neighborhood of A, say 𝒪, with the property that for every ϵ>0, there exists a time T>0 (depending on ϵ and 𝒪) such that for every t≥ T and for every x∈ U, Φ(t,x)∈ N^ϵ(A), where N^ϵ(A) denotes the ϵ-neighborhood of A. Such a neighborhood 𝒪 of an attracting set A is called the fundamental neighborhood of A. 

The set of initial conditions in ℝ^d from which the flow is attracted to an attracting set A is called the basin of attraction and is denoted by B(A). Formally, 

    B(A):={x∈ℝ^d: ∩_t≥0{Φ(q,x):q≥ t}⊆ A}.

An attracting set A is said to be globally attracting if, B(A)=ℝ^d. 




 §.§ Summary of the asymptotic analysis under stability



Let t(0):=0 and for every n≥1, t(n):=∑_k=0^n-1a(k). The linearly interpolated trajectory of recursion (<ref>), is given by the stochastic process X̅:Ω×ℝ→ℝ^d, where for every (ω,t)∈Ω×[0,∞),

    X̅(ω,t):=(t-t(n)/t(n+1)-t(n))X_n+1(ω)+(t(n+1)-t/t(n+1)-t(n))X_n(ω),

where n is such that t∈[t(n),t(n+1)) and for every (ω,t)∈Ω×(-∞,0), X̅(ω,t):=X_0(ω). 

For ω∈Ω, the limit set map of X̅ is given by, λ:Ω→{subsets of ℝ^d} where for every ω∈Ω,

    λ(ω):=∩_t≥0{X̅(ω,q):q≥ t}.

In <cit.>, under assumptions (A1)-(A3) along with the additional assumption of stability of the iterates (that is ℙ(sup_n≥0X_n<∞)=1), it was shown that for almost every ω∈Ω, the linearly interpolated trajectory of recursion (<ref>), X̅(ω,·), is an asymptotic pseudotrajectory for the flow of DI (<ref>). More precisely, for almost every ω∈Ω, X̅(ω,·) was shown to satisfy the following:


  (a) The family of shifted trajectories given by {X̅(ω,·+t)}_t≥0 is relatively compact in 𝒞(ℝ,ℝ^d) where 𝒞(ℝ,ℝ^d) denotes the metric space  of all continuous functions on ℝ taking values in ℝ^d with  metric D, which for every z, z'∈𝒞(ℝ,ℝ^d) is given by

    D(z,z')=∑_k=1^∞1/2^kmin{z-z'_[-k,k],1},

where z-z'_[-k,k]:=sup_t∈[-k,k]z(t)-z'(t).

  (b) Every limit point of the shifted trajectories {X̅(ω,·+t)}_t≥0 is a solution of the DI (<ref>).

From <cit.>, it follows that for almost every ω∈Ω, the limit set of the linearly interpolated trajectory X̅(ω,·), λ(ω), is a non-empty, compact and an internally chain transitive (ICT) set for the flow of DI (<ref>) (see <cit.> for definition of an ICT set). Now using <cit.> the main convergence result of <cit.> follows and is stated below.


Let A⊆ℝ^d be an attracting set for the flow of DI (<ref>).
Under assumptions (A1)-(A3), 


  (a) for almost every ω∈{ω∈Ω:sup_n≥0X_n(ω)<∞}∩{ω∈Ω:λ(ω)∩ B(A)≠∅}, λ(ω)⊆ A and therefore as n→∞, X_n(ω)→ A.

  (b) if B(A)=ℝ^d (that is A is a globally attracting set), then for almost every ω∈{ω∈Ω:sup_n≥0X_n(ω)<∞}, λ(ω)⊆ A and therefore as n→∞, X_n(ω)→ A. 



The assumption of stability of the iterates used to obtain the above convergence result is highly non-trivial and difficult to verify. Moreover the proof method used to prove the above convergence result cannot be modified in a straight forward manner to obtain a similar convergence guarantee. This warrants an alternate approach to study the behavior of recursion (<ref>) in the absence of stability guarantee and we accomplish this by extending the lock-in probability result from <cit.> to the set-valued case. Using the obtained lock-in probability bound we recover convergence guarantee similar to Theorem <ref> while eliminating the need to verify stability.   






 §.§ Main result and its implications

 

Before we state the main result, we state an assumption which fixes the attracting set of interest.


  (A4) Let A⊆ℝ^d, be an attracting set of DI (<ref>) (the mean field of recursion (<ref>)) with 𝒪⊆ℝ^d as its fundamental neighborhood of attraction. 


Let 𝒪' be an open neighborhood of the attracting set A (as in (A4)) such that 𝒪̅'̅ is compact and 𝒪̅'̅⊆𝒪. Then the main result of the paper can be stated as follows.



(Lock-in probability)
Under assumptions (A1)-(A4), there exists a constant K̃>0 (depending on the attracting set A and 𝒪') and an N_0≥1 such that, for every n_0≥ N_0, for every E∈ℱ_n_0 satisfying E⊆{ω∈Ω:X_n_0(ω)∈𝒪'} and ℙ(E)>0, we have that,

    ℙ(X_n→ A as n→∞| E)≥ 1-2de^-K̃/b(n_0),

where, for every n≥0, b(n):=∑_k=n^∞(a(k))^2.

There are two immediate implications of the above result and are stated below, one of which serves as an alternate convergence result in the absence of stability guarantees, that is it allows us to obtain the convergence guarantee in Theorem <ref>(a) without the need to verify whether a given sample path satisfies sup_n≥0X_n(ω)<∞.


  (1) As a consequence of assumption (A2)(ii), we have that lim_n→∞b(n)=0. Therefore from Theorem <ref>, if the observation that iterate lies in a neighborhood of the attracting set is made later in time (n_0), the probability of converging to the attracting set increases and converges to one as n_0→∞. Formally,

    lim_n_0→∞ℙ(X_n→ A as n→∞|X_n_0∈𝒪')=1.


  (2) Suppose ℙ(∩_N≥0∪_n≥ N{X_n∈𝒪'})>0 (if ℙ(∩_N≥0∪_n≥ N{X_n∈𝒪'})=0 then the iterates almost surely do not converge to the attracting set A). Then for every N≥0, ℙ(∪_n≥ N{X_n∈𝒪'})>0 and 

    ∪_n≥ N{X_n∈𝒪'}={X_N∈𝒪'}∪(∪_n>N{X_k∉𝒪', for N≤ k≤ n-1, X_n∈𝒪'}),

where, the union in the R.H.S. is disjoint. Then by Theorem <ref>, for every N≥ N_0,

    ℙ({X_n→ A as n→∞}   ∩(∩_N≥0∪_n≥ N{X_n∈𝒪'}))
       ≥∑_n≥ Nℙ({X_n→ A as n→∞}∩{X_k∉𝒪', for N≤ k≤ n-1, X_n∈𝒪'})
       =∑_n≥ N[ℙ({X_n→ A as n→∞|{X_k∉𝒪', for N≤ k≤ n-1, X_n∈𝒪'})
                   ℙ({X_k∉𝒪', for N≤ k≤ n-1, X_n∈𝒪'})]
       ≥∑_n≥ N(1-2de^-K̃/b(n))ℙ({X_k∉𝒪', for N≤ k≤ n-1, X_n∈𝒪'})
       ≥(1-2de^-K̃/b(N))∑_n≥ Nℙ({X_k∉𝒪', for N≤ k≤ n-1, X_n∈𝒪'})
       =(1-2de^-K̃/b(N))ℙ(∪_n≥ N{X_n∈𝒪'})
       ≥(1-2de^-K̃/b(N))ℙ(∩_N≥ 0∪_n≥ N{X_n∈𝒪'}).

The above inequality is true for every N≥ N_0. Taking limit and using the fact that lim_n→∞b(n)=0, we get that,

    ℙ({X_n→ A as n→∞}∩(∩_N≥0∪_n≥ N{X_n∈𝒪'}))=ℙ(∩_N≥ 0∪_n≥ N{X_n∈𝒪'}).

Therefore from the above we can conclude that,


Under assumptions (A1)-(A4), for almost every ω∈∩_N≥0∪_n≥ N{X_n∈𝒪'}, X_n(ω)→ A as n→∞.


In comparison with Theorem <ref>(a), the condition that ω∈∩_N≥0∪_n≥ N{X_n∈𝒪'} is stronger than the requirement that ω∈{λ(ω)∩ B(A)≠∅} because the former requires the iterate sequence to enter an open neighborhood of A with compact closure infinitely often while the latter requires the iterates to enter the basin of attraction of A infinitely often which is larger than 𝒪'. But in the presence of stability we have that, 

    {sup_n≥0X_n<∞}∩{λ(·)∩ B(A)≠∅}⊆∩_N≥0∪_n≥ N{X_n∈𝒪'}.
 
Further, as a consequence of Corollary <ref>, we have that,

    ℙ({sup_n≥0X_n<∞}∩{λ(·)∩ B(A)≠∅})=ℙ(∩_N≥0∪_n≥ N{X_n∈𝒪'}),

 or in other words, the sample paths which visit 𝒪' infinitely often and are unstable, occur with zero probability.

 


§ APPLICATION: STABILIZATION VIA RESETTING


In this section we modify recursion (<ref>) in such a way that the modified procedure yields sample paths which are stable (that is lie in a compact set almost surely) which in turn allows us to recover the convergence result as in Theorem <ref>(b) without the need to verify stability, in the presence of a globally attracting set for the mean field. That is, we replace assumption (A4) with the following stronger requirement.



  (A4)' Let A⊆ℝ^d be a globally attracting set for the flow of DI (<ref>).


The modification that we propose involves resetting the iterates at regular time intervals if they are found to be lying outside a certain compact set. Let the initial condition X_0(ω)=x_0∈ℝ^d for every ω∈Ω and {r_n∈ (0,∞)}_n≥0 be such that, 


  (1) x_0<r_0,

  (2) for every n≥0, r_n<r_n+1,

  (3) lim_n→∞r_n=∞.

The modified scheme, henceforth referred to as stabilized stochastic recursive inclusion (SSRI) is where every sample path is generated as outlined in Algorithm <ref>.




A flowchart depicting the flow of control in Algorithm <ref> is presented in Figure <ref>. In order to understand the algorithm let us consider the scenario where the k^th reset has been performed at iteration index n_0. Then the algorithm checks whether the iterate lies in the compact set r_kU ( closed ball of radius r_k centered at the origin) after approximately 2^kT_W amount of time has elapsed (for the relation between time and iteration index see section <ref>). Now either a reset occurs or the iterate is left unchanged. 


  (a) If the iterate is left unchanged then the next reset check is performed after 2^kT_W amount of time has elapsed.

  (b) If the iterate is reset, then, the next check is performed after 2^k+1T_W amount of time has elapsed.

In fact it would suffice if the time between successive reset checks were set to be greater than a certain threshold which is determined by the minimum time needed by the flow of the mean field (that is DI (<ref>)) to reach the attracting set A from any initial condition in a compact neighborhood of it. But in practical scenarios one may not be able to compute such a time and hence may not be able to determine the required threshold. This approach of increasing time duration between successive reset checks with increasing reset count allows us to bypass this problem. The choice of exponentially increasing durations is one of convenience as it simplifies notations involved in proving certain results later.



For every n≥1, define the indicator random variable χ_n:Ω→{0,1} such that, for every ω∈Ω, 

    χ_n(ω)= 
                                0    if  X_n(ω)=X_n'(ω), 
    
                                1    if  X_n(ω)≠ X_n'(ω).

We assume that the noise terms {M_n}_n≥1 satisfy the following version of assumption (A3). 


  (A3)' {M_n} is a martingale difference sequence with respect to the filtration {ℱ_n}_n≥1, where, for every n≥1, ℱ_n denotes the smallest σ-algebra generated by the iterates X_m (that is the iterates before the reset operation) and noise terms M_m, for 0≤ m≤ n (then it is easy to show that for every n≥1, X_n'  and hence χ_n are ℱ_n measurable). Since for every n≥1, M_n denotes the noise arising in the estimation (or measurement) of F at X_n-1', we assume that the energy of the noise depends on X_n-1'. That is for every n≥0, M_n+1≤ K(1+X_n') a.s.. 


The next theorem says that, for almost every sample path generated by Algorithm <ref>, the total number of resets is finite, thereby guaranteeing stability. The proof of this theorem (provided in section <ref>) crucially hinges on a lower bound for the probability of the event that there are no future resets given that there are a certain number of resets up until iteration n_0 for some large n_0. Specifically it requires the probability of the above mentioned event to converge to one as n_0 tends to infinity and this is guaranteed by Theorem <ref>.


(Finite resets)
Under assumptions (A1), (A2), (A3)' and (A4)', ℙ({ω∈Ω: ∑_n=1^∞χ_n(ω)<∞})
=1.


As a consequence of the above theorem, we have the following.
   

  (a) Let ω∈{ω∈Ω: ∑_n=1^∞χ_n(ω)<∞}. Then there exists an N≥1 and R>0 (depending on ω) such that, for every n≥ N, X_n(ω)=X_n'(ω) and sup_n≥ NX_n(ω)≤ R. Therefore ∑_n≥ N𝔼[(a(n))^2M_n+1^2|ℱ_n](ω)≤∑_n≥ N(a(n))^2K^2(1+X_n'(ω))^2≤ K^2(1+R)^2∑_n≥ N(a(n))^2
<∞, where the last inequality follows from assumption (A2)(ii). Therefore,

    {ω∈Ω:∑_n≥1χ_n(ω)<∞}⊆{ω∈Ω:∑_n=0^∞𝔼[(a(n))^2M_n+1^2|ℱ_n](ω)<∞}.

Therefore by Theorem <ref>, we have that the ℙ(∑_n=0^∞𝔼[(a(n))^2M_n+1^2|ℱ_n]<∞)=1 and by martingale convergence theorem (see <cit.>) we have that, the square integrable martingale {∑_m=0^n-1a(m)M_m+1,ℱ_n}_n≥1 converges almost surely. 

  (b) Thus for ω lying in a probability one set, there exists N≥1 and R>0 (depending on ω) such that along this sample path the iterates {X_n(ω)}_n≥ N, can be viewed as being generated by recursion (<ref>) with initial condition X_N(ω), their norms are bounded by R uniformly and the additive noise terms {M_n(ω)}_n≥ N satisfy the hypothesis of <cit.>. Then by arguments similar to those of Theorem <ref>(b) we have that,

Under assumptions (A1)-(A3) and (A4)', for almost every ω, the iterates generated by Algorithm <ref>, {X_n'(ω)}_n≥0, are such that X_n'(ω)→ A as n→∞.






§ PROOF OF THE LOCK-IN PROBABILITY THEOREM (THM. <REF>)


Proof of the lock-in probability result follows as a consequence of a series of lemmas. The overall structure can be summarized as follows.


  (a) Our first aim is to replace the set-valued map in recursion (<ref>) with an equivalent single-valued locally Lipschitz continuous function with an additional parameter. In order to accomplish this, we first embed the graph of the set-valued map F in the graph of a sequence of locally Lipschitz continuous set-valued maps. These maps are then parametrized using the Stiener selection procedure which preserves the modulus of continuity.

  (b) The relation between the solutions of DI (<ref>) and that of differential inclusions with continuous set-valued maps which approximate F (as in (a) above) is established. 
  (c) An ordinary differential equation(o.d.e) is defined using an appropriate single-valued parametrization of F (as in (a) above). The existence of solutions to such an o.d.e. and further its uniqueness follow from Caratheodary's existence theorem and locally Lipschitz nature of the vector field respectively. The solutions of this o.d.e. aide in separating the probability contributions due to the additive noise terms and the set-valued nature of the drift function. Using the results from part (b) above, we conclude that after a large number of iterations, the probability contribution is only due to the additive noise terms.

  (d) We finally review the standard probability lower bounding procedure for the additive noise terms from <cit.>. Using this bound in the result obtained in part (c) 
above gives us the desired lock-in probability bound.

Throughout, we use U to denote the closed unit ball in ℝ^d centered at the origin. Further, for every Y_1,Y_2⊆ℝ^d and r∈ℝ, define,


  * Y_1+Y_2:={y_1+y_2:y_1∈ Y_1 and y_2∈ Y_2},

  * rY_1:={ry_1:y_1∈ Y_1}.





 §.§ Upper semicontinuous set-valued maps and their approximation


First we recall definitions of continuous set-valued maps and locally Lipschitz continuous set-valued maps. These notions are taken from <cit.>.

A set-valued map F:ℝ^d→{compact subsets of ℝ^d} is,


  * upper semicontinuous (u.s.c.) if, for every x∈ℝ^d, for every ϵ>0, there exists a δ>0 (depending on x and ϵ) such that, for every x'∈ℝ^d satisfying x'-x<δ, we have that F(x')⊆ F(x)+ϵ U, where F(x)+ϵ U:={y+ϵ u: y∈ F(x), u∈ U}.

  * lower semicontinuous (l.s.c.) if, for every x∈ℝ^d, for every ℝ^d-valued sequence {x_n}_n≥1 converging to x, for every y∈ F(x), there exists a sequence {y_n∈ F(x_n)}_n≥1 converging to y.

  * continuous if, it is both u.s.c. and l.s.c.

  * locally Lipschitz continuous if, for every x_0∈ℝ^d, there exists δ>0 and L>0 (depending on x_0) such that for every x,x'∈ x_0+δ U, we have that 
F(x)⊆ F(x')+Lx-x'U.
 
 

Let 𝒦(ℝ^d) denote the family of all non-empty compact subsets of ℝ^d. Let H:𝒦(ℝ^d)×𝒦(ℝ^d)→[0,∞) be defined such that, for every S_1, S_2∈𝒦(ℝ^d), 

    H(S_1,S_2):=max{sup_s_1∈ S_1inf_s_2∈ S_2s_1-s_2, sup_s_2∈ S_2inf_s_1∈ S_1s_1-s_2}.


With H as defined above, (𝒦(ℝ^d),H) is a complete metric space (for a proof see <cit.>). The notions of continuity and local Lipschitz continuity of a set-valued map can be restated using the metric defined above and is stated as a lemma below for easy reference (for a proof see <cit.>).

A set-valued map F:ℝ^d→𝒦(ℝ^d) is


  (a) Continuous, if and only if, for every x_0∈ℝ^d, for every ϵ>0, there exists δ>0 (depending on x_0 and ϵ), such that for every x∈ x_0+δ U, H(F(x),F(x_0))<ϵ.

  (b) locally Lipschitz continuous, if and only if, for every x_0∈ℝ^d, there exists δ>0 and L>0 (depending on x_0), such that for every x, x'∈ x_0+δ U, 
H(F(x),F(x'))≤ Lx-x'.
 


Before we proceed further we look at a certain form of locally Lipschitz continuous set-valued maps that arise later. The next lemma defines such maps and also states that the sum of two locally Lipschitz continuous set-valued maps is again a locally Lipschitz continuous set-valued map, a result needed later to obtain locally Lipschitz continuous single-valued parametrization of map F in recursion (<ref>).





  (a) If f:ℝ^d→ℝ is a locally Lipschitz continuous map and C∈𝒦(ℝ^d), then the set-valued map F:ℝ^d→𝒦(ℝ^d), given by F(x):=f(x)C for every x∈ℝ^d, is a locally Lipschitz continuous set-valued map. 

  (b) If for every i∈{1,2}, F_i:ℝ^d→𝒦(ℝ^d) is a locally Lipschitz continuous set-valued map, then the set-valued map F:ℝ^d→𝒦(ℝ^d), given by F(x):=F_1(x)+F_2(x) for every x∈ℝ^d, is a locally Lipschitz continuous set-valued map.





  (a) Fix x_0∈ℝ^d and let r:=sup_c∈ Cc. Since f is locally Lipschitz continuous, there exists δ^f_x_0>0 and L^f_x_0>0 such that for every x,x'∈ x_0+δ^f_x_0U, |f(x)-f(x')|≤ L^f_x_0x-x'. Let x,x'∈ x_0+δ^f_x_0U. Then for any c∈ C, 

    f(x)c-f(x')c   =|f(x)-f(x')|c
       ≤ rL^f_x_0x-x'.

Therefore for every x,x'∈ x_0+δ^f_x_0U, for every c∈ C, f(x')c-f(x)c∈ rL^f_x_0x-x'U. Thus for every x,x'∈ x_0+δ^f_x_0U, F(x')⊆ F(x)+rL^f_x_0x-x'U, from which it follows that the set-valued map F is locally Lipschitz continuous at x_0 with δ:=δ^f_x_0 and L:=rL^f_x_0. Since x_0∈ℝ^d is arbitrary, the above argument gives us that F is locally Lipschitz continuous at every x_0.


  (b) Fix x_0∈ℝ^d. Since for every i∈{1,2}, F_i are locally Lipschitz continuous, there exists δ_i>0 and L_i>0 such that for every x,x'∈ x_0+δ_i U, F_i(x)⊆ F_i(x')+L_ix-x' U. Let δ:=min{δ_1,δ_2}, L:=L_1+L_2 and x,x'∈ x_0+δ U. For any y∈ F(x), there exists y_1∈ F_1(x) and y_2∈ F_2(x) such that y=y_1+y_2 . By our choice of δ, we have y'_1∈ F_1(x'), y'_2∈ F_2(x') and u_1, u_2∈ U, such that for every i∈{1,2}, y_i=y'_i+L_ix-x'u_i. Therefore,

    y   =y_1+y_2
       =y'_1+L_1x-x'u_1 +y'_2+L_2x-x'u_2
       =y'_1+y'_2+(L_1+L_2)x-x'(L_1u_1+L_2u_2/L_1+L_2).

Clearly y'_1+y'_2∈ F(x') and since U is a convex subset of ℝ^d, L_1u_1+L_2u_2/L_1+L_2∈ U. From (<ref>) we get that, F(x)⊆ F(x')+(L_1+L_2)x-x' U, for every x,x' ∈ x_0+δ U. Therefore F is locally Lipschitz continuous at x_0. Since x_0 is arbitrary, the above argument gives us that F is locally Lipschitz continuous.
  

Consider a set-valued map F satisfying assumption (A1). A simple contradiction argument gives us that F is u.s.c. It is not possible to represent such u.s.c. set-valued maps with a single-valued continuous map with an additional parameter. But instead one can approximate them from above as explained next. The first step is to embed the graph of the map F in that of a sequence of continuous set-valued maps as stated in the lemma below. For the proof of the lemma below notions of a paracompact topological space, an open covering, its locally finite refinement and partition of unity subordinated to a locally finite covering are needed, which are summarized in Appendix <ref> for easy reference.



Let F:ℝ^d→𝒦(ℝ^d) be a set-valued map satisfying (A1). Then, there exists a sequence of continuous set-valued maps {F^(l):ℝ^d→𝒦(ℝ^d)}_l≥1, such that for every l≥1,


  (a) for every x∈ℝ^d, F^(l)(x) is a non-empty, convex and compact subset of ℝ^d,

  (b) for every x∈ℝ^d, F(x)⊆ F^(l+1)(x)⊆ F^(l)(x),

  (c) there exists K^(l)>0, such that for every x∈ℝ^d, sup_y∈ F^(l)(x)y≤ K^(l)(1+x),

  (d) F^(l) is a locally Lipschitz continuous set valued map.

Furthermore, 


  (e) for every x∈ℝ^d, F(x)=∩_l≥1 F^(l)(x).

 

For any ϵ>0, for every x_0∈ℝ^d, let B(ϵ,x_0):={x: ∥ x-x_0∥<ϵ}. Let {ϵ_l:=1/3^l}_l≥1. Then for every l≥1, 𝒞_l:={B(ϵ_l,x_0):x_0∈ℝ^d} is an open covering of ℝ^d. Since ℝ^d is a metric space, it is paracompact (see <cit.>). Therefore for every l≥1, there exists a locally finite open refinement of the covering 𝒞_l and let it be denoted by 𝒞̃_l:={C_i^l}_i∈ I^l where I^l is an arbitrary index set. By <cit.>, there exists a locally Lipschitz continuous partition of unity, {ψ_i^l}_i∈ I^l, subordinated to the covering 𝒞̃_l. Therefore, 
for every l≥1, for every i∈ I^l, there exists x_i^l, such that support(ψ_i^l)⊆ C_i^l⊆ B(ϵ_l,x_i^l). For every l≥1, for every x∈ℝ^d, let I^l(x):={i∈ I^l:ψ_i^l(x)>0} and by definition of ψ_i^l, we have that 0<|I^l(x)|<∞ and ∑_i∈ I^l(x)ψ_i^l(x)=1.

For every l≥1, define the set valued map F^(l):ℝ^d→{subsets of ℝ^d}, 
such that for every x∈ℝ^d, F^(l)(x):=∑_i∈ I^l(x)ψ_i^l(x)A_i^l, where A_i^l:=c̅o̅(F(B(2ϵ_l,x_i^l))). 

The proofs of parts (a), (b), (c) and (e) of the lemma are exactly the same as that of <cit.>. We shall provide a proof of part (d) of the lemma above from which continuity of the set-valued maps F^(l) follows.


  (d) Fix l≥1 and x∈ℝ^d. Since 𝒞̃_l is a locally finite open covering of ℝ^d, there exists δ>0 (depending on x), such that 
I^l(x,δ):={i∈ I^l: B(x,δ)∩ C^l_i≠∅} is finite. Since {ψ_i^l}_i∈ I^l is a locally Lipschitz continuous partition of unity subordinated to the covering 𝒞̃_l, we have that for every i∈ I^l, support(ψ_i^l)⊆ C_i^l. Therefore, for every x'∈ B(x,δ), F^(l)(x')=∑_i∈ I^l(x,δ)ψ^l_i(x')A_i^l.

From the proof of part (a) of this lemma we know that for every i∈ I^l, A_i^l is a compact and convex subset of ℝ^d. Therefore from Lemma <ref>(a), we get that , for every i∈ I^l(x,δ), the set-valued map given by y→ψ_i^l(y)A_i^l is locally Lipschitz continuous. Further since |I^l(x,δ)|<∞, from Lemma <ref>(b), we get that the set-valued map given by y→∑_i∈ I^l(x,δ)ψ^l(y)A_i^l is locally Lipschitz continuous. Since the set-valued map y→∑_i∈ I^l(x,δ)ψ^l_i(y)A_i^l restricted to B(x,δ) is the same as F^(l) on B(x,δ), we get that F^(l) is locally Lipschitz continuous at x. Since x is arbitrary, the above argument gives us that F^(l) is a locally Lipschitz continuous set-valued map.


The continuous set-valued maps F^(l) as obtained above can be now parametrized (that is represented with a single-valued continuous function with an additional parameter). Key to parametrization is a continuous selection procedure by which we mean a function σ:𝒦(ℝ^d)→ℝ^d which is continuous and is such that for every Y∈𝒦(ℝ^d), σ(Y)∈ Y. Since the maps F^(l) are convex set-valued, it suffices to look for a selection procedure which is continuous restricted to the family of compact and convex subsets of ℝ^d. Further we want a selection procedure which would preserve the local Lipschitz continuity of the set-valued map F^(l) in the parametrization as well. In order to accomplish this we shall use the Stiener selection procedure (for a definition see <cit.>). The next lemma summarizes some properties of the Stiener selection procedure and an intersection lemma which form the central tools for parameterizing the set-valued maps F^(l) (for a proof we refer the reader to <cit.> and <cit.>). Before we state the lemma we introduce some notation needed. Let 𝒦_c(ℝ^d) denote the family of all non-empty compact and convex subsets of ℝ^d. For any set Y⊆ℝ^d and for any x∈ℝ^d, define d(x,Y):=inf_y∈ Yx-y.





  (a) There exists a function σ:𝒦_c(ℝ^d)→ℝ^d, such that for every Y,Y_1, Y_2∈𝒦_c(ℝ^d), 

    σ(Y)∈ Y and σ(Y_1)-σ(Y_2)≤ d H(Y_1,Y_2).


  (b) The map Π:𝒦_c(ℝ^d)×ℝ^d→𝒦_c(ℝ^d), defined such that for every Y∈𝒦_c(ℝ^d) and x∈ℝ^d, Π(Y,u):=Y∩(x+2d(x,Y)U), is such that for every Y_1,Y_2∈𝒦_c(ℝ^d) and for every x_1,x_2∈ℝ^d, 

    H(Π(Y_1,x_1),Π(Y_2,x_2))≤5(H(Y_1,Y_2)+x_1-x_2).




We now use the results stated in the above lemma to parametrize the set-valued maps F^(l).



Let {F^(l)}_l≥1 be as in Lemma <ref>. For every l≥1, there exists a continuous function f^(l):ℝ^d× U→ℝ^d such that, 


  (a) for every x∈ℝ^d, f^(l)(x,U)=F^(l)(x) where f^(l)(x,U):={f^(l)(x,u): u∈ U}.

  (b) for K^(l)>0 as in Lemma <ref>, for every (x,u)∈ℝ^d× U, f^(l)(x,u)≤ K^(l)(1+x).

  (c) for every x_0∈ℝ^d, there exists δ^(l)>0 and L^(l)>0 (depending on x_0), such that for every x,x'∈ x_0+δ^(l) U, for every u∈ U, 

    f^(l)(x,u)-f^(l)(x',u)≤ L^(l)x-x'.

 


Fix l≥1. Let the map f^(l):ℝ^d× U→ℝ^d be defined such that, for every (x,u)∈ℝ^d× U, 

    f^(l)(x,u):=σ(Π(F^(l)(x),K^(l)(1+x)u)),

where σ and Π are as in Lemma <ref>.


  (a) By definition of f^(l), σ and Π, for every (x,u)∈ℝ^d× U, we have that,

    f^(l)(x,u)∈Π(F^(l)(x),K^(l)(1+x)u)⊆ F^(l)(x).
 
Therefore, for every x∈ℝ^d, f^(l)(x,U)⊆ F^(l)(x). By Lemma <ref>(c), we know that for every x∈ℝ^d, sup_y∈ F^(l)(x)y≤ K^(l)(1+x). Thus for every x∈ℝ^d,  for any y∈ F^(l)(x), there exists u∈ U, such that y=K^(l)(1+x)u. For such a u∈ U, by definition of Π, we have that Π(F^(l)(x),K^(l)(1+x)u)=y and hence f^(l)(x,u)=σ(Π(F^(l)(x),K^(l)(1+x)u))=y. Therefore for every x∈ℝ^d, F^(l)(x)⊆ f^(l)(x,U) from which it follows that f^(l)(x,U)=F^(l)(x), for every x∈ℝ^d.

  (b) Follows from part (a) of this lemma and Lemma <ref>(c).

  (c) Fix x_0∈ℝ^d. Since F^(l) is a locally Lipschitz continuous set-valued map (see Lemma <ref>(d)), we obtain δ_F^(l)>0 and L_F^(l)>0 (depending on x_0) such that for every x,x'∈ x_0+δ_F^(l)U, H(F^(l)(x),F^(l)(x'))≤ L_F^(l)x-x'. Set δ^(l):=δ_F^(l) and L^(l):=5d(L_F^(l)+K^(l)). Then, for any x,x'∈ x_0+δ^(l)U, for every u∈ U,

    f^(l)(x,u)-f^(l)(x',u)   =σ(Π(F^(l)(x),K^(l)(1+x)u))-σ(Π(F^(l)(x'),K^(l)(1+x')u))
       ≤ d H(Π(F^(l)(x),K^(l)(1+x)u),Π(F^(l)(x'),K^(l)(1+x')u))
       ≤ 5d  (H( F^(l)(x),F^(l)(x') ) +K^(l)( 1+x)u-K^(l)( 1+x')u )
       = 5d ( H( F^(l)(x),F^(l)(x') )+K^(l)|x-x'|u)
       ≤ 5d ( H( F^(l)(x),F^(l)(x') )+K^(l)x-x')
       ≤ 5d (L_F^(l)x-x'+K^(l)x-x')
       = L^(l)x-x',

where, (<ref>) follows from Lemma <ref>(a), (<ref>) follows from Lemma <ref>(b) and (<ref>) follows from our choice of δ^(l) and local Lipschitz continuity of F^(l).


The set-valued map in recursion (<ref>) can be replaced with the parametrization obtained in the lemma above as explained below.


  (1) For every l≥ 1, by Lemma <ref>(b), we know that for every x∈ℝ^d, F(x)⊆ F^(l)(x). Therefore for every l≥1, for every n≥0, 

    X_n+1-X_n-a(n)M_n+1∈ a(n)F^(l)(X_n).


  (2) For every l≥1, by Lemma <ref>(a), we know that for every x∈ℝ^d, F^(l)(x)=f^(l)(x,U). It can now be shown that for every n≥0, there exists a U-valued random variable on Ω, say U^(l)_n, such that for every ω∈Ω, for every n≥0, 

    X_n+1(ω)-X_n(ω)-a(n)M_n+1(ω)= a(n)f^(l)(X_n(ω),U^(l)_n(ω))

(for a proof see <cit.>).





 §.§ Solutions of the mean field and their approximation


In this section, we shall approximate the solutions of mean field (that is DI (<ref>)) with the solutions of DI given by,

    dx/dt∈ F^(l)(x),

for some l≥1. In order to accomplish this we need some notations which are introduced next. 

For every T>0 and for every x∈ℝ^d,  let S(T,x) denote the set of solutions of DI (<ref>) on [0,T]. Formally, 


    S(T,x):={x:[0,T]→ℝ^d : x is absolutely continuous with x(0)=x and for a.e. t∈[0,T], dx(t)/dt∈ F(x(t))}.


Since F is a Marchaud map, we have that for every T>0 and for every x∈ℝ^d, S(T,x)≠∅. Similarly for every l≥1, for every T>0 and for every x∈ℝ^d, let S^(l)(T,x) denote the set of solutions of DI (<ref>) on [0,T]. Formally,


    S^(l)(T,x):={x:[0,T]→ℝ^d : x is absolutely continuous with x(0)=x and for a.e. t∈[0,T], dx(t)/dt∈ F^(l)(x(t))}.


From Lemma <ref>, we know that for every l≥1, F^(l) is a Marchaud map and hence for every T>0 and for every x∈ℝ^d, S^(l)(T,x)≠∅. 

For any Y⊆ℝ^d, for any T>0, define S(T,Y):=∪_y∈ YS(T,y). Similarly, for every l≥1, S^(l)(T,Y):=∪_y∈ YS^(l)(T,y). 

The next lemma summarizes some important relationships between the solutions of DI (<ref>) and those of DI (<ref>) needed later. It also states that for large enough l≥1, the solutions of DI (<ref>)  are within an ϵ-neighborhood of the solutions of DI (<ref>) for every initial condition lying in a compact subset of ℝ^d.



For every T>0,


  (a) for every l≥1, for every x∈ℝ^d, S(T,x)⊆ S^(l+1)(T,x)⊆ S^(l)(T,x).

  (b) for every x∈ℝ^d, S(T,x)=∩_l≥1S^(l)(T,x).

  (c) for any Y⊆ℝ^d, S(T,Y)=∩_l≥1S^(l)(T,Y).

  (d) for every Y⊆ℝ^d compact, S(T,Y) is a compact subset of 𝒞([0,T],ℝ^d) (the vector space of ℝ^d-valued continuous functions on [0,T]).

  (e) for every Y⊆ℝ^d compact, for every l≥1, S^(l)(T,Y) is a compact subset of 𝒞([0,T],ℝ^d).

  (f) for every Y⊆ℝ^d compact, for every ϵ>0, there exists l'≥1, such that for every l≥ l', for every x^(l)∈ S^(l)(T,Y), there exists x∈ S(T,Y), such that sup_t∈[0,T]x(t)-x^(l)(t)< ϵ.



Fix T>0.


  (a) Fix l≥1 and x∈ℝ^d. Let x∈ S(T,x). Then we have that x is absolutely continuous with x(0)=x and for a.e. t∈[0,T], dx(t)/dt∈ F(x(t)). By Lemma <ref>(b), we know that for every t∈ [0,T], F(x(t))⊆ F^(l+1)(x(t)). Therefore for a.e. t∈[0,T], dx(t)/dt∈ F^(l+1)(x(t)), from which we get that x∈ S^(l+1)(T,x).
Hence S(T,x)⊆ S^(l+1)(T,x). Using the fact that for every x'∈ℝ^d, F^(l+1)(x')⊆ F^(l)(x') (see Lemma <ref>(b)), a similar argument gives us that S^(l+1)(T,x)⊆ S^(l)(T,x).

  (b) Fix x∈ℝ^d. From part (a) of this lemma we have that S(T,x)⊆∩_l≥1S^(l)(T,x). Let x∈∩_l≥1S^(l)(T,x). Then x is absolutely continuous with x(0)=x and for every l≥1, for a.e. t∈[0,T], dx(t)/dt∈ F^(l)(x(t)). 
Thus for a.e. t∈[0,T], for every l≥1, dx(t)/dt∈ F^(l)(x(t)). Hence for a.e t∈[0,T], dx(t)/dt∈∩_l≥1F^(l)(x(t))=F(x(t)), where the equality follows from Lemma <ref>(e). Therefore x∈ S(T,x), from which we get that ∩_l≥1S^(l)(T,x)⊆ S(T,x).

  (c) Follows from part (a) and (b) of this lemma.

  (d) & (e) Follows from <cit.>.

  (f) Suppose not. Then there exists Y⊆ℝ^d compact and ϵ>0, such that for every l'≥1, there exists l≥ l' and x^(l)∈ S^(l)(T,Y), such that d(x^(l),S(T,Y))≥ϵ, where d(x^(l),S(T,Y)):=inf_x∈ S(T,Y)sup_t∈[0,T]x^(l)(t)-x(t). Thus we can obtain a sequence of solutions, say {x^(l_k)}_k≥1, such that for every k≥1, 1≤ l_k<l_k+1 and x^(l_k)∈ S^(l_k)(T,Y) with d(x^(l_k),S(T,Y))≥ϵ. From part (a) of this lemma, we have that for every k≥1, S^(l_k)(T,Y)⊆ S^(1)(T,Y) and hence {x^(l_k)}_k≥1⊆ S^(1)(T,Y). Since Y⊆ℝ^d is compact, by part (e) of this lemma we know that S^(1)(T,Y) is a compact subset of 𝒞([0,T],ℝ^d). Thus there exists a subsequence of {x^(l_k)}_k≥1, say {x^(l_k_j)}_j≥1 such that x^(l_k_j)→x^* as j→∞ in 𝒞([0,T],ℝ^d) and x^*∈ S^(1)(T,Y). Since for every j≥1, d(x^(l_k_j),S(T,Y))≥ϵ, we get that d(x^*,S(T,Y))≥ϵ and hence x^*∉ S(T,Y). 
From part (a) of this lemma, we get that for every l≥1, for J:=min{j≥1:l_k_j≥ l}, {x^(l_k_j)}_j≥ J⊆ S^(l)(T,Y). Further by part (e) of this lemma we have that for every l≥ 1, S^(l)(T,Y) is a compact subset of 𝒞([0,T],ℝ^d). Thus for every l≥1, x^*∈ S^(l)(T,Y) and hence x^*∈∩_l≥1S^(l)(T,Y)=S(T,Y) (see part (c) of this lemma). This leads to a contradiction.


The part (f) of the above lemma provides the necessary approximation result. Further since the set-valued maps F^(l) admit a single-valued parametrization (f^(l) as in Lemma <ref>), a solution of DI (<ref>) can be viewed as a solution of the ordinary differential equation (o.d.e.) given by,

    dx/dt=f^(l)(x,u(t)),

 for some u:[0,∞)→ U measurable and vice versa. The lemma below summarizes some useful results on the solutions of o.d.e. (<ref>) and its vector field.
 
  For every l≥1,
 
 
  (a)  for every T>0, for any u:[0,T]→ U measurable, for every initial condition, the set of solutions of o.d.e. (<ref>) is non-empty. That is, for every x_0∈ℝ^d, there exists x:[0,T]→ℝ^d such that, x is absolutely continuous, x(0)=x_0 and for a.e. t∈ [0,T], dx(t)/dt=f^(l)(x(t),u(t)).
 
 
  (b) for every T>0, for every Y⊆ℝ^d compact, there exists C_1(Y,T,l)>0, such that for every u:[0,T]→ U measurable, every solution of o.d.e. (<ref>) with initial condition in Y, say x:[0,T]→ℝ^d, satisfies,
 
    sup_t∈[0,T]x(t)≤ C_1(Y,T,l).
 
 
 
  (c) for any Y⊆ℝ^d compact, there exists L(Y,l)>0, such that for every T>0, for every u:[0,T]→ U, the map h:Y×[0,T]→ℝ^d, given by h(x,t):=f^(l)(x,u(t)) for every (x,t)∈ Y× [0,T], satisfies,
 
    h(x,t)-h(x',t)≤ L(Y,l)x-x',
      
 for every x, x'∈ Y and for every t∈[0,T].
 
  (d) for every T>0, for every u:[0,T]→ U, for every initial condition, o.d.e. (<ref>) admits a unique solution.


 Fix l≥1.


  (a) Fix T>0 and u:[0,T]→ U measurable. The proof of this part is a direct application of <cit.>. We show here that the sufficient conditions required to apply the said theorem are satisfied by the vector field of the o.d.e. (<ref>). First, we show that f^(l)(·,u(·)) is a Caratheodary function (see <cit.>). By Lemma <ref>, it is clear that for every t∈[0,T], the map x→ f^(l)(x,u(t)) is continuous and for every x∈ℝ^d, the map t→ f^(l)(x,u(t)) is measurable. Further by Lemma <ref>(b), we have that for any c>0, for every x∈ℝ^d with x≤ c, for every t∈[0,T], f^(l)(x,t)≤ K^(l)(1+c). Thus f^(l)(·,u(·)) is a Caratheodary function. Final condition to verify is on the rate of growth of solutions. By Lemma <ref>(b), f^(l)(x,u(t))≤ψ(x):=K^(l)(1+x). The function ψ:[0,∞)→ [0,∞), is clearly positive everywhere and the function 1/ψ is locally integrable on [0,∞). A simple argument gives us that  for every r>0, the integral ∫_r^∞dr̃/ψ(r̃) can be lower bounded by the tail of 1/K^(l)∑_n=1^∞1/n. Hence for every r>0, ∫_r^∞dr̃/ψ(r̃)=∞. Now <cit.> can be applied to obtain the required result.

  (b) Fix T>0 and Y⊆ℝ^d compact. Since Y is compact, there exists r>0 such that sup_y∈ Yy≤ r. Set C_1(Y,T,l):=(r+K^(l)T)e^K^(l)T, where K^(l)>0 is as in Lemma <ref>(b). For some u:[0,T]→ U measurable and for some x_0∈ Y, let x:[0,T]→ℝ^d be a solution of o.d.e. (<ref>) with initial condition x_0. Then, for every t∈[0,T], x(t)=x_0+∫_0^tf^(l)(x(s),u(s))ds and hence for every t∈[0,T]

    x(t)   ≤x_0+∫_0^tf^(l)(x(s),u(s))ds
       ≤ r+K^(l)T+K^(l)∫_0^tx(s)ds

where, (<ref>) follows from the fact that x_0∈ Y and Lemma <ref>(b). The required bound follows from (<ref>) and Gronwall's result (see <cit.>).                                   

  (c) Fix Y⊆ℝ^d compact. It is enough to show that there exists L(Y,l)>0, such that for every y_1, y_2∈ Y, sup_u∈ Uf^(l)(y_1,u)-f^(l)(y_2,u)≤ L(Y,l)y_1-y_2. From Lemma <ref>(c), we know that for every x_0∈ Y, there exists δ(x_0,l)>0 and L(x_0,l)>0, such that for every x,x'∈ x_0+δ(x_0,l)U, for every u∈ U, f^(l)(y_1,u)-f^(l)(y_2,u)≤ L(Y,l)y_1-y_2. Let 𝒢:={x_0+δ(x_0,l)/2U:x_0∈ Y}, where, U denotes the interior of U. Since Y is compact and 𝒢 is an open cover of Y, there exists {x_1,x_2,…,x_k}⊆ Y, such that Y⊆∪_i=1^k(x_i+δ(x_i,l)/2U). Set δ(Y,l):=min_1≤ i≤ kδ(x_i,l)/2 and L_0(Y,l):=max_1≤ i≤ kL(x_i,l).  

Let y_1,y_2∈ (Y× Y)∩{(y_1,y_2): y_1-y_2<δ(Y,l)}. Then we know that there exists i∈{1,…,k}, such that y_1∈ x_i+δ(x_i,l)/2U. Further since y_1-y_2<δ(Y,l)≤δ(x_i,l)/2, we have that y_2∈ x_i +δ(x_i,l)U. Therefore y_1,y_2∈ x_i+δ(x_i,l)U and hence, for every u∈ U, f^(l)(y_1,u)-f^(l)(y_2,u)≤ L(x_i,l)y_1-y_2≤ L_0(Y,l)y_1-y_2. Thus for every y_1,y_2∈ (Y× Y)∩{(y_1,y_2): y_1-y_2<δ(Y,l)}, sup_u∈ Uf^(l)(y_1,u)-f^(l)(y_2,u)≤ L_0(Y,l)y_1-y_2.     

Let E:=(Y× Y)∩{(y_1,y_2):y_1-y_2≥δ(Y,l)}. By Lemma <ref>(b), the map (y_1,y_2)∈ Y× Y→sup_u∈ Uf^(l)(y_1,u)-f^(l)(y_2,u) is well defined. Further using the fact that for every (y_1,y_2), (y_1',y_2')∈ Y× Y, |sup_u∈ Uf^(l)(y_1,u)-f^(l)(y_2,u)-sup_u∈ Uf^(l)(y_1',u)-f^(l)(y_2',u)|≤sup_u∈ Uf^(l)(y_1,u)-f^(l)(y_1',u)+sup_u∈ Uf^(l)(y_2,u)-f^(l)(y_2',u) and Lemma <ref>(c), we have that the map (y_1,y_2)→sup_u∈ Uf^(l)(y_1,u)-f^(l)(y_2,u) is continuous. Thus the map (y_1,y_2)∈ E→sup_u∈ Uf^(l)(y_1,u)-f^(l)(y_2,u)/y_1-y_2 is a continuous function on a compact set E and hence achieves a maximum, say L_1(Y,l)≥0. Therefore for every (y_1,y_2)∈ (Y× Y)∩{(y_1,y_2):y_1-y_2≥δ(Y,l)}, sup_u∈ Uf^(l)(y_1,u)-f^(l)(y_2,u)≤ L_1(y,l)y_1-y_2.

Thus from the arguments in the two preceding paragraphs we have that there exists L(Y,l):=max{L_0(Y,l),L_1(Y,l)}, such that, for every y_1,y_2∈ Y, sup_u∈ Uf^(l)(y_1,u)-f^(l)(y_2,u)≤ L(Y,l)y_1-y_2.  

  (d) Using parts (b) and (c) of this lemma, the proof of uniqueness follows from arguments similar to that of <cit.>.





 §.§ Bounding procedure


In this section we show that the lower bound on the probability of the event that the iterates converge to an attracting set given that after a large number of iterations the iterates lies in a neighborhood of it depends mainly on the additive noise terms. 

In order to accomplish this we first define some terms which are a measure of the distance of the linearly interpolated trajectory of recursion (<ref>), that is X̅ (see (<ref>)) to the solutions of the DI (<ref>) over a T>0 length time interval, among others. Recall from section <ref> that 𝒪'⊆ℝ^d, is an open neighborhood of the attracting set A (as in assumption (A4)) with compact closure, such that A⊆𝒪'⊆𝒪̅'̅⊆𝒪, where 𝒪 denotes the fundamental neighborhood of A. Thus we can find an ϵ_0>0, such that N^ϵ_0(𝒪̅'̅)⊆𝒪 and N^2ϵ_0(A)⊆𝒪', where for any ϵ>0, N^ϵ(·) denotes the ϵ-neighborhood of a set. Further, since A is an attracting set for the flow of DI (<ref>), for ϵ_0>0 as obtained above, there exists T_A>0, such that for every x∈𝒪, for every t≥ T_A, Φ(t,x)∈ N^ϵ_0(A.
Throughout the rest of this paper ϵ_0 and T_A will denote the constants as obtained above.

For every T>0, for every n≥0, 


  *  : let τ(n,T):=min{k≥ n: t(k)≥ t(n)+T}, where t(n), for every n≥0 are as defined in section <ref>. That is τ(n,T) denotes the first iterate such that, at least time T has elapsed since the n^th iteration. Further the time elapsed from iteration n to iteration τ(n,T), be denoted by Δ(n,T), that is Δ(n,T):=t(τ(n,T))-t(n). Then by the choice of our step sizes we have that T≤Δ(n,T)≤ T+1.

  *  : for every ω∈Ω,  ρ(ω,n,T):=inf_x∈ S(T,𝒪̅'̅)sup_t∈[0,T]X̅(ω,t+t(n))-x(t), where S(T,𝒪̅'̅) denotes the set of solutions of DI (<ref>) as defined in equation (<ref>).

  *  : for every ω∈Ω, for every l≥1, let x̅^(l)(·;n,T,ω):[0,T]→ℝ^d denote the unique solution of the  o.d.e. 

    dx/dt=f^(l)(x,u(t;n,T,ω)),

with initial condition x̅^(l)(0;n,T,ω)=X_n(ω), where u(·;n,T,ω):[0,T]→ U is defined such that, for every t∈[0,T], u(t;n,T,ω):=U_k^(l)(ω), where U_k^(l) is as in equation (<ref>) and k is such that t+t(n)∈ [t(k),t(k+1)) (for a proof of existence and uniqueness of solutions to o.d.e. (<ref>), see Lemma <ref>).  It is easy to see that for every l≥1, x̅^(l)(·;n,T,ω)∈ S^(l)(T,X_n(ω)), where S^(l)(T,X_n(ω)) denotes the set of solutions of DI (<ref>), as defined in (<ref>).

  *  : for every ω∈Ω, for every l≥1, ρ^(l)_1(ω,n,T):=sup_t∈[0,T]X̅(ω,t+t(n))-x̅^(l)(t;n,T,ω) and ρ^(l)_2(ω,n,T):=inf_x∈ S(T,𝒪̅'̅)sup_t∈[0,T]x̅^(l)(t;n,T,ω)-x(t).

  *  : for any T_u≥ T_A, for any n_0≥0, let {n_m}_m≥1 denote a subsequence of natural numbers defined such that for every m≥0, T_A≤ T_m:= t(n_m+1)-t(n_m)≤ T_u.   
  

Now we collect sample paths of interest using the quantities ρ, ρ_1^(l) and ρ_2^(l). The next lemma summarizes results in this regard.


For every T_u≥ T_A, for every n_0≥0, for every l≥1, for every event E∈ℱ_n_0, such that E⊆{ω : X_n_0(ω)∈𝒪'}, for every {n_m}_m≥1 as in <ref>,


  (a) for every M≥0,
 

    E ∩(∩_m=0^M{ω∈Ω:ρ_1^(l)(ω,n_m,T_m)+ρ_2^(l)(ω,n_m,T_m)<ϵ_0})   ⊆ E ∩(∩_m=0^M{ω∈Ω:ρ(ω,n_m,T_m)<ϵ_0})
       ⊆{ω∈Ω: X_n_M+1(ω)∈𝒪'},



  (b)


    ℙ(E ∩(∩_m≥0{ω∈Ω:ρ_1^(l)(ω,n_m,T_m)+ρ_2^(l)(ω,n_m,T_m)<ϵ_0}))   ≤ℙ(E ∩(∩_m≥0{ω∈Ω:ρ(ω,n_m,T_m)<ϵ_0}))
       ≤ℙ(E∩{ω∈Ω: X_n(ω)→ A as n→∞}),




where, {T_m}_m≥0 is as in <ref>.


Fix n_0≥0, l≥1 and E∈ℱ_n_0, such that E⊆{ω∈Ω:X_n_0(ω)∈𝒪'}.


  (a) For every m≥0, for every ω∈Ω, from <ref> and <ref>, it is clear that,

    ρ(ω,n_m,T_m)≤ρ_1^(l)(ω,n_m,T_m)+ρ_2^(l)(ω,n_m,T_m),

from which we get that for every m≥0, 

    {ω∈Ω:ρ_1^(l)(ω,n_m,T_m)+ρ_2^(l)(ω,n_m,T_m)<ϵ_0}⊆{ω∈Ω:ρ(ω,n_m,T_m)<ϵ_0}.

Therefore,


    E ∩(∩_m=0^M{ω∈Ω:ρ_1^(l)(ω,n_m,T_m)+ρ_2^(l)(ω,n_m,T_m)<ϵ_0})⊆ E ∩(∩_m=0^M{ω∈Ω:ρ(ω,n_m,T_m)<ϵ_0}).


The proof of the second inclusion follows from induction. Fix M=0 and ω∈ E∩{ω∈Ω:ρ(ω,n_0,T_0)<ϵ_0}. Then X_n_0(ω)∈𝒪'. Since T_0≥ T_A, we have that for every x∈ S(T_0,𝒪̅'̅), x(T_0)∈ N^ϵ_0(A). Further, since ρ(ω,n,T_0)<ϵ_0 and by Lemma <ref>(d), we get that there exists x∈ S(T_0,𝒪̅'̅), such that X̅(ω,t(n_1))-x(T_0)=X_n_1(ω)-x(T_0)<ϵ_0 and hence X_n_1(ω)∈ N^2ϵ_0(A)⊆𝒪'. Therefore ω∈{ω∈Ω: X_n_1(ω)∈𝒪'}. Thus the inclusion is true for M=0. Suppose the inclusion is true for some M>0. Let ω∈ E ∩(∩_m=0^M+1{ω∈Ω:ρ(ω,n_m,T_m)<ϵ_0}). Since the inclusion is true for M, we have that X_n_M+1(ω)∈𝒪'. Now by arguments exactly same as those for the base case (that is for M=0) we get that X_n_M+2(ω)∈𝒪'. Therefore the inclusion is true for M+1.

  (b) The first inequality follows from part (a) of this lemma. We shall provide a proof of the second inequality. Let ω∈ E ∩(∩_m≥0{ω∈Ω:ρ(ω,n_m,T_m)<ϵ_0}). Then by part (a) of this lemma we have that for every m≥0, X_n_m(ω)∈𝒪'. Since 𝒪̅'̅ is compact, by Lemma <ref>(d), we have that, S(T_u,𝒪̅'̅) is a compact subset of 𝒞([0,T_u],ℝ^d), and hence there exists C(𝒪̅'̅,T_m)>0 such that, sup_x∈ S(T_u,𝒪̅'̅)sup_t∈[0,T_u]x(t)≤ C(𝒪̅'̅,T_m). Further since for every m≥0, T_m≤ T_u, we get that sup_x∈ S(T_m,𝒪̅'̅)sup_t∈[0,T_m]x(t)≤sup_x∈ S(T_u,𝒪̅'̅)sup_t∈[0,T_u]x(t)≤ C(𝒪̅'̅,T_m). By our choice of ω, we have that for every m≥0, ρ(ω,n_m,T_m)<ϵ_0 and by <ref>, we get that for every m≥0, sup_t∈ [0,T_m]X̅(ω,t+t(n_m))≤ C(𝒪̅'̅,T_m)+ϵ_0. Therefore ω, is such that sup_n≥0X_n(ω)<∞ and for every m≥0, X_n_m(ω)∈𝒪'. Thus λ(ω) (see equation (<ref>) for definition), is non-empty, compact and λ(ω)∩𝒪̅'̅⊆λ(ω)∩ B(A)≠∅, where B(A) denotes the basin of attraction of the attracting set A. By  Theorem <ref>(a), we have that for almost every ω in E ∩(∩_m≥0{ω∈Ω:ρ(ω,n_m,T_m)<ϵ_0}) the iterates converge to the attracting set A. Therefore we get that ℙ( E ∩(∩_m≥0{ω∈Ω:ρ(ω,n_m,T_m)<ϵ_0}))≤ℙ(E∩{ω∈Ω: X_n(ω)→ A as n→∞)}).
   

The quantity ρ_1^(l) as in <ref>, captures the difference between the linearly interpolated trajectory of recursion (<ref>) and the solution of the o.d.e. (<ref>) over a T>0 length time interval. This difference can be shown to comprise of two components namely, the error due to discretization and the error due to additive noise terms. By the step size assumption, that is (A2), we know that the step sizes are converging to zero. Hence intuition suggests that after a large number of iterations have elapsed the discretization error must be negligible and the contribution to the difference term ρ_1^(l) is mainly due to the additive noise terms. The following is made precise in the lemma below. A brief outline of the proof of this lemma which follows from Lemma <ref>(c) and <cit.>, is presented in Appendix <ref>.



For every l≥1, for every T_u≥ T_A, there exists N_0'≥1, such that for every n_0≥ N_0', for every E∈ℱ_n_0 such that, E⊆{ω∈Ω:X_n_0(ω)∈𝒪'}, for every sequence {n_m}_m≥0 as in <ref>, for every m≥0, we have,


    ℙ(ℬ_m-1^(l)∩{ω∈Ω:ρ_1^(l)(ω,n_m,T_m)≥ϵ_0/2})≤ℙ({ω∈Ω:max_n_m≤ j≤ n_m+1ζ_j(ω)-ζ_n_m(ω)≥ϵ_0/4K_0(T_u)}∩ℬ^(l)_m-1),


where,


  * ℬ_-1^(l_0):=E and for every M≥0, ℬ_M^(l_0):=E∩(∩_m=0^M{ω∈Ω:ρ_1^(l_0)(ω,n_m,T_m)+ρ_2^(l_0)(ω,n_m,T_m)<ϵ_0}), 

  * for every j≥1, ζ_j:=∑_n=0^j-1a(n)M_n+1, where {M_n}_n≥1 denote the additive noise terms as defined in assumption (A3),

  * {T_m}_m≥0 is as in <ref> and K_0(T_u)>0 is a positive constant increasing in T_u



Suppose event E as in the lemma above occurs with some positive probability. Then the next lemma says that the lower bound of ℙ({ω∈Ω : X_n(ω)→ A as n→∞}|E) depends mainly on the additive noise terms for n_0 large. 



For every T_u≥ T_A, there exists l_0≥1 and N_0'≥1, such that for every n_0≥ N_0', for every E∈ℱ_n_0 such that, E⊆{ω∈Ω:X_n_0(ω)∈𝒪'} and ℙ(E)>0, for every sequence {n_m}_m≥0 as in <ref>, we have,

    ℙ({ω∈Ω : X_n(ω)→ A as n→∞}|E)≥1-∑_m=0^∞ℙ(max_n_m≤ j≤ n_m+1ζ_j-ζ_n_m≥ϵ_0/4K_0(T_u)|ℬ^(l_0)_m-1),

where, the sequence of events {ℬ_m^(l_0)}_m≥-1, the sequence of random vectors {ζ_j}_j≥1 and the constant K_0(T_u) are as defined in Lemma <ref>.

 By Lemma <ref>(f), we get that there exists l_0≥1 (depending on 𝒪̅'̅, T_u and ϵ_0) such that for every x^(l_0)∈ S^(l_0)(T_u,𝒪̅'̅), there exists x∈ S(T_u,𝒪̅'̅) such that sup_t∈[0,T_u]x^(l_0)(t)-x(t)<ϵ_0/2. Further by Lemma <ref>(a) and definition of E, we get that for every m≥0, ℬ_m-1^(l_0)⊆{ω∈Ω:X_n_m(ω)∈𝒪'}. Therefore, for every ω∈ℬ_m-1^(l_0), x̅^(l_0)(·;n_m,T_m,ω)∈ S^(l_0)(T_m,𝒪̅'̅) and

    ρ_2^(l_0)(ω,n_m,T_m)   =inf_x∈ S(T_m,𝒪̅'̅)sup_t∈[0,T_m]x̅^(l_0)(t;n_m,T_m, 							ω)-x(t)
       ≤inf_x∈ S(T_u,𝒪̅'̅)sup_t∈[0,T_u]x̅^(l_0)(t;n,T_u,ω)-                                                         					x(t)
       <ϵ_0/2,
 
where (<ref>) follows from the fact that T_m≤ T_u and (<ref>) follows from our choice of l_0 and <ref>. Therefore for every m≥-1,

    ℬ_m^(l_0)∩{ω∈Ω:ρ_1^(l_0)(ω,n_m+1,T_m)+ρ_2^(l_0)(ω,n_m+1,T_m)≥ϵ_0}⊆ℬ_m^(l_0)∩{ω∈Ω:ρ_1^(l_0)(ω,n_m+1,T_m)≥ϵ_0/2},

and hence, 


    ℙ({ω∈Ω:ρ_1^(l_0)(ω,n_m+1,T_m)+ρ_2^(l_0)(ω,n_m+1,T_m)≥ϵ_0}|ℬ_m^(l_0))≤ℙ({ω∈Ω:ρ_1^(l_0)(ω,n_m+1,T_m)≥ϵ_0/2}|ℬ_m^(l_0)).
 

By Lemma <ref>, we know that there exists N_0'≥1 such that, for every n_0≥ N_0', for every m≥0, 

    ℙ(ℬ_m-1^(l_0)∩{ω∈Ω:ρ_1^(l_0)(ω,n_m,T_m)≥ϵ_0/2})≤ℙ(ℬ_m-1^(l_0)∩{ω∈Ω:max_n_m≤ j≤ n_m+1ζ_j(ω)-ζ_n_m(ω)≥ϵ_0/4K_0(T_u)}),
 
from which it follows that,

    ℙ({ω∈Ω:ρ_1^(l_0)(ω,n_m,T_m)≥ϵ_0/2}|ℬ_m-1^(l_0))≤ℙ({ω∈Ω:max_n_m≤ j≤ n_m+1ζ_j(ω)-ζ_n_m(ω)≥ϵ_0/4K_0(T_u)}|ℬ_m-1^(l_0)).

For l_0≥1 as obtained above and for n_0≥ N_0', we have that,

    ℙ(X_n→ A as n→∞|E)   ≥ℙ(∩_m≥0{ω∈Ω:ρ_1^(l_0)(ω,n_m,T_m)+ρ_2^(l_0)(ω,n_m,T_m)< 										   ϵ_0}|E)
       =1-ℙ(∪_m≥0{ω∈Ω:ρ_1^(l_0)(ω,n_m,T_m)+ρ_2^(l_0)(ω,n_m,T_m)≥ϵ_0}|E)
       =1-ℙ({ω∈Ω:ρ_1^(l_0)(ω,n_0,T_m)+ρ_2^(l_0)(ω,n_0,T_m)≥ϵ_0}|ℬ^(l_0)_-1)
    
                                                                                           -∑_m=1^∞   ℙ({ω∈Ω:ρ_1^(l_0)(ω,n_m,T_m)+ρ_2^(l_0)(ω,n_m,T_m)≥ϵ_0}|ℬ_m-1^(l_0))ℙ(ℬ_m-1^(l_0)|ℬ_-1^(l_0))
       ≥1- ∑_m=0^∞ℙ({ω∈Ω:ρ_1^(l_0)(ω,n_m,T_m)+ρ_2^(l_0)(ω,n_m,T_m)									≥ϵ_0}|ℬ_m-1^(l_0)),
 
where, (<ref>) follows from Lemma <ref>(b), (<ref>) follows from the observation that,

    (∪_m≥0{ω∈Ω:ρ_1^(l_0)(ω,n_m,T_m)   +ρ_2^(l_0)(ω,n_m,T_m)≥ϵ_0})∩ E=
       ∪_m≥0({ω∈Ω:ρ_1^(l_0)(ω,n_m,T_m)+ρ_2^(l_0)(ω,n_m,T_m)≥ϵ_0}∩ℬ_m-1^(l_0)),
 
(where the union in R.H.S. is disjoint) and (<ref>) follows from the fact that for every m≥0, ℙ(ℬ_m-1^(l_0)|ℬ_-1^(l_0))≤ 1. Using (<ref>) and (<ref>) in (<ref>), we get that there exists l_0≥1 and N_0'≥1, such that for every n_0≥ N_0', for every E∈ℱ_n_0 such that E⊆{ω∈Ω: X_n_0(ω)∈𝒪'} and ℙ(E)>0,

    ℙ(X_n→ A as n→∞|E)    ≥1- ∑_m=0^∞ℙ({ω∈Ω:ρ_1^(l_0)(ω,n_m,T_m)+ρ_2^(l_0)         											   (ω,n_m,T_m)≥ϵ_0}|ℬ_m-1^(l_0))
       ≥1-∑_m=0^∞ℙ({ω∈Ω:ρ_1^(l_0)(ω,n_m,T_m)≥ϵ_0/2}|              								    ℬ_m-1^(l_0))
       ≥ 1-∑_m=0^∞ℙ({ω∈Ω:max_n_m≤ j≤ n_m+1ζ_j(ω)-ζ_n_m										    (ω)≥ϵ_0/4K_0(T_u)}|ℬ_m-1^(l_0)).






 §.§ Review of the probability bounding procedure for the additive noise terms


In this section we fix l_0 and n_0≥ N_0, where l_0 and N_0 are as in Lemma <ref> and provide an upper bound for ℙ({ω∈Ω:max_n_m≤ j≤ n_m+1ζ_j(ω)-ζ_n_m(ω)≥ϵ_0/4K_0(T_u)}|ℬ_m-1^(l_0)), for every m≥0. The proof of the bounding procedure is similar to that of <cit.> and we provide a brief outline here for the sake of completeness.


  (a) From recursion (<ref>), we have that for every m≥0, for every n_m≤ j≤ n_m+1-1, for every ω∈Ω, there exists V_j(ω)∈ F(X_j(ω)), such that,

    X_j+1(ω)-X_j(ω)-a(n)M_j+1(ω)=a(n)V_j(ω).

By assumption (A1)(ii), we know that V_j(ω)≤ K(1+X_j(ω)) and hence for n_m≤ j≤ n_m+1-1,

    X_j+1(ω)≤X_j(ω)(1+a(j)K)+a(j)K+a(j)M_j+1.

Further by assumption (A3), we get that, for every m≥0, for almost every ω∈Ω, for n_m≤ j≤ n_m+1-1, 

    X_j+1(ω)≤X_j(ω)(1+2a(j)K)+2a(j)K.

Now by arguments as in <cit.>, we get that, for every m≥0, for almost every ω∈Ω, for n_m≤ j≤ n_m+1,

    X_j(ω)≤ e^2K T_u(X_n_m(ω)+2KT_u).


  (b) Clearly {ζ_j-ζ_n_m,ℱ_j}_n_m≤ j≤ n_m+1 is a martingale. By (<ref>) and (A3), we get that for n_m≤ j<n_m+1,
ζ_j+1-ζ_j=a(j)M_j+1≤ a(j)K(1+X_j)≤ a(j) K(1+e^2KT_u(1+2KT_uX_n_m)). Since for every ω∈ℬ^(l_0)_m-1, X_n_m(ω)∈𝒪' (whose closure is compact), there exists a C>0, such that X_n_m(ω)≤ C. Therefore for every m≥0, for every ω∈ℬ^(l_0)_m-1, 
for every n_m≤ j<n_m+1, ζ_j+1-ζ_j≤ a(j)K(1+e^2KT_u(1+2KT_uC)). Thus applying the concentration inequality for martingales, by arguments exactly the same as in the proof of <cit.>, we get that for every m≥0,

    ℙ({ω∈Ω:max_n_m≤ j≤ n_m+1ζ_j(ω)-ζ_n_m(ω)≥ϵ_0/4K_0(T_u)}|ℬ_m-1^(l_0))≤ 2de^-K̃/(b(n_m)-b(n_m+1))

where, K̃:=ϵ_0^2/(32(K_0(T_u))^2dK(1+e^2KT_u(1+2KT_uC))).
                               


of Theorem <ref>:
Let l_0≥1 and N_0' be as in Lemma <ref>. By definition of b(·), we get that there exists N_0”≥1, such that for every n≥ N_0”, b(n)<K̃. Define N_0:=max{N_0',N_0”}. Let n_0≥ N_0 and {n_m:=τ(n_m-1,T_A)}_m≥1. {n_m}_m≥1 as defined satisfies the conditions mentioned in <ref>. Then by Lemma <ref> and (<ref>), we get that for n_0≥ N_0, 

    ℙ(X_n→ A as n→∞|E)≥ 1-2d∑_m=0^∞e^-K̃/(b(n_m)-b(n_m+1)).

We know that e^-K̃/x/x→0 as x→0 and increases with x for 0<x<K̃. Therefore by our choice of n_0, we get that, 

    e^-K̃/(b(n_m)-b(n_m+1))/b(n_m)-b(n_m+1)≤e^-K̃/b(n_0)/b(n_0),

from which it follows that for every m≥0, e^-K̃/b(n_m)-b(n_m+1)≤ (b(n_m)-b(n_m+1))e^-K̃/b(n_0)/b(n_0).
Substituting the above in (<ref>), we get that for every n_0≥ N_0,

    ℙ(X_n→ A as n→∞|E)    ≥ 1-2d∑_m=0^∞e^-K̃/b(n_m)-b(n_m+1)
       ≥ 1-2d∑_m=0^∞ (b(n_m)-b(n_m+1))e^-K̃/b(n_0)/b(n_0)
       =1-2de^-K̃/b(n_0)/b(n_0)∑_m=0^∞ (b(n_m)-b(n_m+1))
       =1-2de^-K̃/b(n_0).




§ PROOF OF FINITE RESETS THEOREM (THM. <REF>)



From the definition of χ_n in equation (<ref>), we know that the χ_n takes the value one if there is a reset of the n^th iterate and is zero otherwise. Therefore ∑_n=1^∞χ_n denotes the total number of resets. 

Suppose the event {∑_n=1^∞χ_n≥ k} has zero probability for some k≥1. Then for k≥1, such that ℙ(∑_n=1^∞χ_n≥ k)=0, we have ℙ(∑_n=1^∞χ_n< k)=1, from which Theorem <ref> trivially follows. Therefore without loss of generality assume ℙ(∑_n=1^∞χ_n≥ k)>0, for every k≥1.

 For every k≥0, let G_k denote the event that there are at most k resets and G_∞ denote the event that there are finitely many resets. That is, for every k≥0, G_k:={∑_n=1^∞χ_n≤ k} and G_∞:={∑_n=1^∞χ_n<∞}. Then it is clear that, for every k≥ 1, G_k⊆ G_k+1 and G_∞=∪_k≥0G_k. Therefore lim_k→∞ℙ(G_k) exists and ℙ(G_∞)=lim_k→∞ℙ(G_k). For any k≥1,
 
    ℙ(G_k)=ℙ(∑_n=1^∞χ_n≤ k)
                                 =ℙ({∑_n=1^∞χ_n≤ k-1}∪{∑_n=1^∞χ_n = k})
                                 =ℙ(G_k-1)+ℙ(∑_n=1^∞χ_n =k).

The event {∑_n=1^∞χ_n=k} can be written as a disjoint union of events as below. For every k≥1

    {∑_n=1^∞χ_n=k}=∪_n_0≥1[{∑_n=1^n_0-1χ_n=k-1}∩{χ_n_0=1}∩{∑_n=n_0+1^∞χ_n=0}],

where, {∑_n=1^0χ_n=k-1}:=Ω. Let J(k):={n_0≥ 1: ℙ({∑_n=1^n_0-1χ_n=k-1}∩{χ_n_0=1})>0}. Then for every k≥1,


  (a) By arguments in the second paragraph of this section we have that ℙ(G_k-1^c)=ℙ(∑_n=1^∞χ_n≥ k)>0. Further the event {∑_n=1^∞χ_n≥ k} can be written as a disjoint union of events as below.

    {∑_n=1^∞χ_n≥ k}=∪_n_0≥1[{∑_n=1^n_0-1χ_n=k-1}∩{χ_n_0=1}],
  
from which it follows that,

    0<ℙ({∑_n=1^∞χ_n≥ k})=∑_n_0=1^∞ℙ({∑_n=1^n_0-1χ_n=k-1}∩{χ_n_0=1}).

Therefore J(k)≠∅.

  (b) min{n_0∈ J(k)}≥ k, since there cannot be k resets in less than k iterations.

From (<ref>) and definition of J(k), we have that for every k≥1,

    ℙ(∑_n=1^∞χ_n=k)=∑_n_0∈ J(k)ℙ(∑_n=n_0+1^∞χ_n=0|∑_n=1^n_0-1χ_n=k-1,χ_n_0=1)
    ℙ(∑_n=1^n_0-1χ_n=k-1,χ_n_0=1).


Step 1 (Obtaining 𝒪', ϵ_0 and T_A) :  By (A4)', we have that A is a globally attracting set of DI (<ref>). Let r̃>0 be such that A⊆r̃U. By definition of a globally attracting set and <cit.>, we get that for any r≥r̃, rU is a fundamental neighborhood of A. Let k_1≥1 be such that r_k_1≥r̃. Set the fundamental neighborhood 𝒪:=r_k_1+1U and 𝒪':=r_k_1U. Obtain ϵ_0>0 and T_A>0 as in section <ref>. That is ϵ_0>0 is such that N^2ϵ_0(A)⊆𝒪'⊆ N^ϵ_0(𝒪̅'̅)⊆𝒪 and T_A>0, is such that for every x∈𝒪, for every t≥ T_A, Φ(t,x)∈ N^ϵ_0(A). 

Step 2 (Obtaining {n_m}_m≥1 as in <ref>) :  Clearly there exists k_2≥1, such that for every k≥ k_2, T_A≤2^kT_W. For any n_0≥1, for every m≥1, define n_m:=n_2^k_2,m-1, where for every 1≤ j≤ 2^k_2, n_j,m-1:=τ(n_j-1,m-1,T_W) with n_0,m-1:=n_m-1 and τ(·,·) is as defined in <ref>. Therefore for every m≥1, T_m-1:=t(n_m)-t(n_m-1)=∑_j=0^2^k_2-1Δ(n_j,m-1,T_W), where Δ(·,·) is as defined in <ref>. Thus for every m≥0, T_A≤ 2^k_2T_W≤ T_m≤ 2^k_2T_W+2^k_2 and hence T_u=2^k_2T_W+2^k_2.

Step 3 (Redefining trajectories) :   Define X̅, as defined in (<ref>), with the iterates {X_n}_n≥0 (iterates before reset check) generated by Algorithm <ref>. For every n≥1, define X̃(·,·;n):Ω×[t(n),∞)→ℝ^d such that for every (ω,t)∈Ω×[t(n),t(n+1)), 

    X̃(ω,t;n):=(t-t(n)/t(n+1)-t(n))X_n+1(ω)+(t(n+1)-t/t(n+1)-t(n))X'_n(ω),

and for every (ω,t)∈[t(n+1),∞), X̃(ω,t;n)=X̅(ω,t). 

Step 4 (Obtaining parameters) :  By arguments exactly same as the ones used to obtain (<ref>), we get that, for every l≥1, for every n≥0, there exists a U-valued random variable on Ω, say Ũ^(l)_n such that,  for every ω∈Ω,

    X_n+1(ω)-X_n'(ω)-a(n)M_n+1(ω)= a(n)f^(l)(X_n'(ω),Ũ^(l)_n(ω)).


Step 5 (Redefining distance measures) : 
For every ω∈Ω, for every n≥ n'≥1, for every T>0, for every l≥1,


  (a) let x̃^(l)(·;n,n',T,ω):[0,T]→ℝ^d denote the unique solution of the o.d.e. 

    dx/dt=f^(l)(x,ũ(t;n,n',T,ω)),

with initial condition x̃^(l)(0;n,n',T,ω)=X_n''(ω), where ũ(·;n,n',T,ω):[0,T]→ U is defined such that, for every t∈[0,T], ũ(t;n,n',T,ω):=Ũ_k^(l)(ω), where Ũ_k^(l) is as in equation (<ref>) and k is such that t+t(n)∈ [t(k),t(k+1)) (for a proof of existence and uniqueness of solutions to o.d.e. (<ref>), see Lemma <ref>).  It is easy to see that for every l≥1, x̃^(l)(·;n,n',T,ω)∈ S^(l)(T,X_n''(ω)), the set of solutions of DI (<ref>), as defined in (<ref>).

  (b) define,
 

  (1) ρ̃(ω,n,n',T):=inf_x∈ S(T,𝒪̅'̅)sup_t∈[0,T]X̃(ω,t+t(n);n')-x(t),  

  (2)ρ̃^(l)_1(ω,n,n',T):=sup_t∈[0,T]X̃(ω,t+t(n);n')-x̃^(l)(t;n,n',T,ω), 

  (3)ρ̃^(l)_2(ω,n,n',T):=inf_x∈ S(T,𝒪̅'̅)sup_t∈[0,T]x̃^(l)(t;n,n',T,ω)-x(t). 



Step 6 (Collecting sample paths) :  Fix k> max{k_1,k_2} and n_0∈ J(k). By our definition of ℱ_n_0 (see section <ref>), we have that E(k,n_0):={∑_n=1^n_0-1χ_n=k-1,χ_n_0=1}∈ℱ_n_0 and is contained in {X_n_0'(ω)∈𝒪'}. Given that there has been a reset at index n_0, the next reset check is performed by Algorithm <ref> at the iteration index n_2^k-k_2. So for n_0+1≤ j< n_2^k-k_2, X_j(ω)=X_j'(ω). From arguments exactly the same as Lemma <ref>(a), we get that,  

    E(k,n_0)∩(∩_m=0^2^k-k_2-1{ρ̃^(l)_1(ω,n_m,n_0,T_m)+ρ̃^(l)_2   (ω,n_m,n_0,T_m)<ϵ_0})
       ⊆ E(k,n_0)∩(∩_m=0^2^k-k_2-1{ρ̃(ω,n_m,n_0,T_m)<ϵ_0})
       ⊆{ω∈Ω:X_n_2^k-k_2(ω)∈𝒪'}
       ⊆{ω∈Ω: X_n_2^k-k_2(ω)=X_n_2^k-k_2'(ω)}
       ⊆{∑_n=n_0+1^n_2^k-k_2χ_n=0}

where, (<ref>) follows from the fact that k≥ k_1 and hence 𝒪'= r_k_1U⊆ r_kU. It is also worth mentioning here that the proof of Lemma <ref>(a) holds irrespective of how the iterates are generated. Given that ω∈ E(k,n_0)∩(∩_m=0^2^k-k_2-1{ρ̃^(l)_1(ω,n_m,n_0,T_m)+ρ̃^(l)_2(ω,n_m,n_0,T_m)<ϵ_0}), along this sample path there has been a reset at n_0 and at the next check performed at n_2^k-k_2 there has been no reset. Hence the next check for reset is performed by Algorithm <ref> at n_2^(k-k_2)+1. Again from arguments from Lemma <ref>(a), we get that,

    E(k,n_0)∩(∩_m=0^2^(k-k_2)+1-1{ρ̃^(l)_1(ω,n_m,n_0,T_m)+ρ̃^(l)_2(ω,n_m,n_0,T_m)<ϵ_0})   ⊆{ω∈Ω:X_2^(k-k_2)+1(ω)∈𝒪'}
       ⊆{∑_n=n_0+1^n_2^(k-k_2)+1χ_n=0}.

Repeating the above for the third reset check after n_0 and so on, we obtain that,

    E(k,n_0)∩(∩_m≥0{ρ̃^(l)_1(ω,n_m,n_0,T_m)+ρ̃^(l)_2(ω,n_m,n_0,T_m)<ϵ_0})
    ⊆{∑_n=n_0+1^∞χ_n=0}.


Step 7 (Bounding) :  Define ℬ̃^(l)_-1:=E(k,n_0) and for every M≥1 define, 

    ℬ̃^(l)_M:=E(k,n_0)∩(∩_m=0^M{ρ̃^(l)_1(·,n_m,n_0,T_m)+ρ^(l)_2(·,n_m,n_0,T_m)<ϵ_0}).

Note that as in Lemma <ref>, we can obtain l_0≥1, such that for every m≥0, for every ω∈B̃^(l_0)_m-1 we have that ρ̃^(l_0)_2(ω,n_m,n_0,T_m)<ϵ_0/2, since for every ω∈ℬ̃^(l_0)_m-1, X_n_m(ω)∈𝒪' and whether or not a reset check is performed at this index, we have that X_n_m(ω)=X_n_m'(ω). Thus for such an l_0, mimicking the proof of Lemma <ref>, we obtain that,

    ℙ(∩_m=0^M{ρ̃^(l)_1(·,n_m,n_0,T_m)+ρ^(l)_2(·,n_m,n_0,T_m)<ϵ_0}|ℬ̃^(l_0)_-1)≥ 1-∑_m=0^∞ℙ(ρ̃^(l_0)_1(·,n_m,n_0,T_m)≥ϵ_0/2|ℬ̃^(l_0)_m-1).


From Lemma <ref>, we have that for k> max{k_1,k_2,N_0'}, for every n_0∈ J(k), 


    ℙ(∩_m=0^M{ρ̃^(l)_1(·,n_m,n_0,T_m)+ρ^(l)_2(·,n_m,n_0,T_m)<ϵ_0}|ℬ̃^(l_0)_-1)≥ 1-∑_m=0^∞ℙ(max_n_m≤ j≤ n_m+1ζ_j-ζ_n_m≥ϵ_0/4K_0(T_u)|ℬ̃^(l_0)_m-1).



Step 8 (Noise bound) Similar to item (a) in section <ref>, from Algorithm (<ref>), we have that for every m≥0, for every n_m≤ n_m+1-1, X_j+1≤X_j'(1+a(j)K)+a(j)K+a(j)M_j+1 and since X_j+1'≤X_j+1, we get that for every n_m≤ j≤ n_m+1-1,

    X'_j+1≤X_j'(1+a(j)K)+a(j)K+a(j)M_j+1.

Now by arguments exactly same as those item (a) of section <ref>, we get that for every m≥0, for every n_m≤ j≤ n_m+1-1, X_j+1'≤ e^2K T_u(X_n_m+2KT_u). Now by using concentration inequality as in item (b) of section <ref>, we get that for every m≥0,

    ℙ(max_n_m≤ j≤ n_m+1ζ_j-ζ_n_m≥ϵ_0/4K_0(T_u)|ℬ̃_m-1^(l_0))≤2de^-K̃/(b(n_m)-b(n_m+1)).
 

Using (<ref>), (<ref>) and (<ref>) we get that, for every k≥max{k_1,k_2,N_0} (where N_0 is as defined in the proof of Theorem <ref>), for every n_0∈ J(k), 

    ℙ(∑_n=n_0+1^∞χ_n=0|∑_n=1^n_0-1χ_n=k-1,χ_n_0=1)≥ 1-2d∑_m=0^∞e^-K̃/(b(n_m)-b(n_m+1))≥1-2de^-K̃/b(n_0).
 
Substituting the above in (<ref>) and using the fact that for n≤ n', b(n')≤ b(n), we get that, for every k≥max{k_1,k_2,N_0},

    ℙ(∑_n=1^∞χ_n=k)   ≥(1-2de^-K̃/b(k))∑_n_0=1^∞ℙ({∑_n=1^n_0-1χ_n=k-1}∩{χ_n_0=1})
       =(1-2de^-K̃/b(k))ℙ({∑_n=1^∞χ_n≥ k})

 Substituting (<ref>) in (<ref>), we get that for every k≥max{k_1,k_2,N_0},
 
    ℙ(G_k)≥ℙ(G_k-1)+(1-2de^-K̃/b(k))ℙ(G_k-1^c)
                                ≥ 1-2de^-K̃/b(k).

Letting k→∞ in the above equation and using the fact that ℙ(G_∞)=lim_k→∞ℙ(G_k), we get that ℙ(G_∞)=1.


§ CONCLUSIONS AND DIRECTIONS FOR FUTURE WORK


We have extended the lock-in probability result (Theorem <ref>) in <cit.> to stochastic approximation schemes with set-valued drift functions which serves as an important tool for analyzing recursions when their stability is not guaranteed. The extension to set-valued map allows one to obtain lock-in probability for stochastic approximation schemes with measurable drift functions and schemes where the drift function itself possess a non-additive unknown noise component (see <cit.>). Further using Theorem <ref>, in the presence of a locally attracting set for the mean field, we have provided an alternate condition for verification of convergence in the absence of stability guarantee which involves verifying whether the iterates are entering infinitely often, an open neighborhood of the attractor with a compact closure.  In the presence of a globally attracting set our modified recursion as in Algorithm <ref>, converges almost surely to the globally attracting set, the proof of which relies on the method used to obtain the lock-in probability result.
 
In future we wish to consider other applications of the lock-in probability result such as sample complexity (see <cit.>) and almost sure convergence under tightness of the iterates (see <cit.>). Another interesting direction, is to explore various additive noise models where the above result can be extended for the case of set-valued drift functions.  






§ DEFINITIONS OF SOME TOPOLOGICAL CONCEPTS


Let (ℳ,Γ) be a topological space. {O_i}_i∈ I is an covering of ℳ if, for every i∈ I, O_i⊆ℳ and ∪_i∈ IO_i=ℳ. Further a covering {O_i}_i∈ I is said to be locally finite if for every p∈ℳ, there exists an O∈Γ, such O_i∩ O≠∅ for only finitely many i∈ I. Given any two coverings 𝒞:={O_i}_i∈ I and 𝒞':={O_j'}_j∈ J, 𝒞' is said to be a refinement of 𝒞 if, for every i∈ I, there exists a j∈ J such that, O_i⊆ O_j'. 𝒞' is said to be a locally finite refinement of 𝒞, if 𝒞' is a refinement of 𝒞 and is locally finite. The topological space (ℳ,Γ) is paracompact if it is a Hausdorff space and if every open covering has a locally finite open refinement.

A family of functions {ψ_i}_i∈ I is called a locally Lipschitz partition of unity if for all i∈ I,


  * ψ_i is locally Lipschitz continuous and non negative,

  * the supports of ψ_i, defined as {p∈ℳ:ψ_i(p)≠0}, are a closed locally finite covering of ℳ,

  * for each p∈ℳ, ∑_i∈ Iψ_i(p)=1.

A partition of unity {ψ_i}_i∈ I is said to be subordinated to the covering {O_i}_i∈ I, if for every i∈ I, {p∈ℳ:ψ_i(p)≠0}⊆ O_i.



§ PROOF OF LEMMA <REF>

 
Fix l≥1 and T_u≥ T_A. Fix n_0≥ 1 and {n_m}_m≥0 as in <ref>. Fix m≥0. Let ω∈{ω∈Ω:ρ_1^(l)(ω,n_m,T_m)≥ϵ_0/2}∩ℬ_m-1^(l). Then, by Lemma <ref>(a) we have that, X_n_m(ω)∈𝒪'. By (<ref>) and <ref>, we have that for every 0≤ t≤ T_m, there exists n_m≤ k≤ n_m+1-1 such that t∈ [t(k),t(k+1)], and 

    X̅(ω,t+t(n_m))=α X_n_k(ω)+(1-α)X_n_k+1(ω),
 
for some α∈ [0,1] and

    x̃^(l)(t;n_m,T_m,ω)= X_n_m(ω)+∫_0^qf^(l)(x̃^(l)(q;n_m,T_m,ω),u(q;n_m,T_m,ω))dq.

Therefore for any t∈ [0,T_m], 

    X̅(ω,t+t(n_m))-x̃^(l)(t;n_m,T_m,ω)   ≤αX_k(ω)-X̃^(l)(t(k);n_m,T_m,ω)
        +αX̃^(l)(t(k);n_m,T_m,ω)-X̃^(l)(t;n_m,T_m,ω)
       +(1-α)X̃^(l)(t(k+1);n_m,T_m,ω)-X̃^(l)(t;n_m,T_m,ω)
       +(1-α)X_k+1(ω)-X̃^(l)(t(k+1);n_m,T_m,ω)

Now the aim is to provide an upper bound for each terms in the R.H.S. of the above inequality which is independent of m and t. In order to apply <cit.> the only additional condition needed is the Lipschitz continuity of f^(l)(·,·) uniformly over u and this is obtained using local Lipschitz continuity as follows. Let M_1>0 be such that, for every x∈𝒪', x≤ M_1. By Lemma <ref>(b) and item (a) in section <ref>, we have that for r:=max{C_1(𝒪̅'̅,T_u,l), e^2KT_u(M_1+2KT_u)}, 

    sup_t∈[0,T_m]X̅(ω,t+t(n_m))≤ r and sup_t∈ [0,T_u]x̃^(l)(t;n_m,T_m,ω)≤ r.

Further by Lemma <ref>(c), we know that there exists L(r,l)>0, such that for every x,x'∈ r U, for every t∈ [0, T_m]

    f^(l)(x,u(t;n_m,T_m,ω))-f^(l)(x',u(t;n_m,T_m,ω))≤ L(r,l)x-x'.

The rest of the bounding procedure is exactly the same as <cit.>. We obtain that, for every t∈ [0,T_m], 

    sup_t∈ [0,T_m]X̅(ω,t+t(n_m))-x̃^(l)(t;n_m,T_m,ω)≤ (   M_1+KT_u)e^2L(r,l)T_uL(r,l)∑_j≥0a(n_0+j)^2
       +e^L(r,l)T_umax_n_m≤ j≤ n_m+1ζ_j(ω)-ζ_n_m(ω)
       +(M_1+KT_u)e^L(r,l)T_ua(n_0).


Now set N_0' such that (M_1+KT_u)e^2L(r,l)T_uL(r,l)∑_j≥0a(n_0+j)^2+(M_1+KT_u)e^L(r,l)T_ua(n_0)<ϵ_0/2 and define K_0(T_u):=e^L(r,l)T_u. Then, for every n_0≥ N_0', we have that ω∈{ω∈Ω:max_n_m≤ j≤ n_m+1ζ_j(ω)-ζ_n_m(ω)≥ϵ_0/4K_0(T_u)}∩ℬ^(l)_m-1, from which Lemma <ref> follows.
IEEEtran






