text: STOCHASTIC APPROXIMATION FOR QUASI-STATIONARY DISTRIBUTIONS IN FINITE DIMENSIONS 14 an algorithm for estimating the quasi-stationary distribution of this process. The diﬃculty is that the state space is exponential in size save for a few special cases. Here we simulate the contact process on a complete graph. If the infection rate is changed to 1.5, then each iteration of the algorithm would take an extreme long time. We applied the version of the algorithm designed for continuous-time Markov chains and Doeblinized the Markov chain by subtracting 0.5I from the transition rate matrix. The eigenvalue condition fails resulting in a slow rate of convergence for the vanilla algorithm. The Polyak’s averaging algorithm signiﬁcantly outperforms the vanilla algorithm. See Figure 3. 8. Discussion and Conclusion In summary, we have improved upon the algorithm of [7] by recognizing it as a stochastic approximation algorithm as opposed to an urn process. In doing so, we were able to prove its law of large number and CLT. The result is stronger than the results given in the urn process literature[2]. Furthermore, we provided a counterexample that strongly suggests that the suﬃcient eigenvalues condition for the CLT is also necessary and fails in many common applications. An improved algorithm that uses projection and iterate averaging signiﬁcantly improves rate of convergence. ∞ We have tested our algorithm on countable state space processes such as the M/M/1/ queue with success. Proving the convergence of this algorithm in this countable state space setting is currently an open problem. We’re also working on a version of the algorithm for estimating the quasi-stationary distribution of diﬀusion processes using stochastic approximation. Another open issue is how to pick the best Doeblinization constant. When E[τ] is large you’re more likely to satisfy the condition for the CLT but that’s when run-time of the algorithm increases proportionally. There must be a balance between the run-time of each tour and the rate of convergence of µ . It is also not n clear what the optimal step size should be for the projected algorithm. Finally, it would be very interesting to investigate the connection between the phase transition critical point of contact processes and its CLT critical point. Unfortunately, preliminary work seems to suggest that those two are unconnected. Acknowledgments Support from the NSF foundation through the grants CMMI-0846816 and CMMI-1069064 is gratefully acknowledged. Proof of Main Results We ﬁrst restate a series of assumptions & notations that is used by Theorem 5.2.1 from [16] which we will invoke. Again the form of the recursion is θ = θ + (cid:15) W where W is a martingale diﬀerence n+1 n n n ≤n sequence with respect to the ﬁltration F that at least contains σ(θ , W − , i n). Recall that for us, W n i i 1 n consists of the t(cid:80)wo compone(cid:80)nts W (the probability vector) and Z (and added time dimension) deﬁned in n n Equation 5 and θ consists of µ and T . n n n ↓ ∞ ∞ (1) (cid:15) 0, (cid:15) = , (cid:15)2 < . This is trivially satisﬁed for our (cid:15) = 1 . (2) Tnhe observned responsesnhave to have uniformly bounded variancne: sunp E|W |2 < ∞. See Lemma n n 10. (3) (A local-averaging condition) Let g (µ , T ) (cid:44) E[W |F ]. The functions g (µ, T) need to be n n n n n n continuous uniformly in n, and there needs to exist a continuous function g¯(µ, T) such that for each ##LTLine##

text: STOCHASTIC

text: APPROXIMATION

text: FOR

text: QUASI-STATIONARY

text: DISTRIBUTIONS

text: IN

text: FINITE

text: DIMENSIONS

text: an

text: algorithm

text: for

text: estimating

text: the

text: quasi-stationary

text: distribution

text: of

text: this

text: process.

text: The

text: diﬃculty

text: is

text: that

text: the

text: state

text: space

text: is

text: exponential

text: in

text: size

text: save

text: for

text: a

text: few

text: special

text: cases.

text: Here

text: we

text: simulate

text: the

text: contact

text: process

text: on

text: a

text: complete

text: graph.

text: If

text: the

text: infection

text: rate

text: is

text: changed

text: to

text: then

text: each

text: iteration

text: of

text: the

text: algorithm

text: would

text: take

text: an

text: extreme

text: long

text: time.

text: We

text: applied

text: the

text: version

text: of

text: the

text: algorithm

text: designed

text: for

text: continuous-time

text: Markov

text: chains

text: and

text: Doeblinized

text: the

text: Markov

text: chain

text: by

text: subtracting

text: from

text: the

text: transition

text: rate

text: matrix.

text: The

text: eigenvalue

text: condition

text: fails

text: resulting

text: in

text: a

text: slow

text: rate

text: of

text: convergence

text: for

text: the

text: vanilla

text: algorithm.

text: The

text: Polyak’s

text: averaging

text: algorithm

text: signiﬁcantly

text: outperforms

text: the

text: vanilla

text: algorithm.

text: See

text: Figure

text: Discussion

text: and

text: Conclusion

text: In

text: summary,

text: we

text: have

text: improved

text: upon

text: the

text: algorithm

text: of

text: by

text: recognizing

text: it

text: as

text: a

text: stochastic

text: approximation

text: algorithm

text: as

text: opposed

text: to

text: an

text: urn

text: process.

text: In

text: doing

text: so,

text: we

text: were

text: able

text: to

text: prove

text: its

text: law

text: of

text: large

text: number

text: and

text: CLT.

text: The

text: result

text: is

text: stronger

text: than

text: the

text: results

text: given

text: in

text: the

text: urn

text: process

text: Furthermore,

text: we

text: provided

text: a

text: counterexample

text: that

text: strongly

text: suggests

text: that

text: the

text: suﬃcient

text: eigenvalues

text: condition

text: for

text: the

text: CLT

text: is

text: also

text: necessary

text: and

text: fails

text: in

text: many

text: common

text: applications.

text: An

text: improved

text: algorithm

text: that

text: uses

text: projection

text: and

text: iterate

text: averaging

text: signiﬁcantly

text: improves

text: rate

text: of

text: convergence.

text: We

text: have

text: tested

text: our

text: algorithm

text: on

text: countable

text: state

text: space

text: processes

text: such

text: as

text: the

text: queue

text: with

text: success.

text: Proving

text: the

text: convergence

text: of

text: this

text: algorithm

text: in

text: this

text: countable

text: state

text: space

text: setting

text: is

text: currently

text: an

text: open

text: problem.

text: We’re

text: also

text: working

text: on

text: a

text: version

text: of

text: the

text: algorithm

text: for

text: estimating

text: the

text: quasi-stationary

text: distribution

text: of

text: diﬀusion

text: processes

text: using

text: stochastic

text: approximation.

text: Another

text: open

text: issue

text: is

text: how

text: to

text: pick

text: the

text: best

text: Doeblinization

text: constant.

text: When

text: E[τ]

text: is

text: large

text: you’re

text: more

text: likely

text: to

text: satisfy

text: the

text: condition

text: for

text: the

text: CLT

text: but

text: that’s

text: when

text: run-time

text: of

text: the

text: algorithm

text: increases

text: proportionally.

text: There

text: must

text: be

text: a

text: balance

text: between

text: the

text: run-time

text: of

text: each

text: tour

text: and

text: the

text: rate

text: of

text: convergence

text: of

text: µ

text: It

text: is

text: also

text: not

text: n

text: clear

text: what

text: the

text: optimal

text: step

text: size

text: should

text: be

text: for

text: the

text: projected

text: algorithm.

text: Finally,

text: it

text: would

text: be

text: very

text: interesting

text: to

text: investigate

text: the

text: connection

text: between

text: the

text: phase

text: transition

text: critical

text: point

text: of

text: contact

text: processes

text: and

text: its

text: CLT

text: critical

text: point.

text: Unfortunately,

text: preliminary

text: work

text: seems

text: to

text: suggest

text: that

text: those

text: two

text: are

text: unconnected.

text: Acknowledgments

text: Support

text: from

text: the

text: NSF

text: foundation

text: through

text: the

text: grants

text: and

text: is

text: gratefully

text: acknowledged.

text: Proof

text: of

text: Main

text: Results

text: We

text: ﬁrst

text: restate

text: a

text: series

text: of

text: assumptions

text: notations

text: that

text: is

text: used

text: by

text: Theorem

text: from

text: which

text: we

text: will

text: invoke.

text: Again

text: the

text: form

text: of

text: the

text: recursion

text: is

text: θ

text: θ

text: W

text: where

text: W

text: is

text: a

text: martingale

text: diﬀerence

text: n

text: n

text: n

text: ≤n

text: sequence

text: with

text: respect

text: to

text: the

text: ﬁltration

text: F

text: that

text: at

text: least

text: contains

text: σ(θ

text: W

text: i

text: n).

text: Recall

text: that

text: for

text: us,

text: W

text: n

text: i

text: i

text: n

text: consists

text: of

text: the

text: W

text: (the

text: probability

text: vector)

text: and

text: Z

text: (and

text: added

text: time

text: dimension)

text: deﬁned

text: in

text: n

text: n

text: Equation

text: and

text: θ

text: consists

text: of

text: µ

text: and

text: T

text: n

text: n

text: n

text: This

text: is

text: trivially

text: satisﬁed

text: for

text: our

text: Tnhe

text: observned

text: responsesnhave

text: to

text: have

text: uniformly

text: bounded

text: variancne:

text: sunp

text: E|W

text: See

text: Lemma

text: n

text: n

text: (A

text: local-averaging

text: condition)

text: Let

text: g

text: (µ

text: T

text: E[W

text: |F

text: The

text: functions

text: g

text: (µ,

text: T)

text: need

text: to

text: be

text: n

text: n

text: n

text: n

text: n

text: n

text: continuous

text: uniformly

text: in

text: n,

text: and

text: there

text: needs

text: to

text: exist

text: a

text: continuous

text: function

text: g¯(µ,

text: T)

text: such

text: that

text: for

text: each

text: ##LTLine##


text: STOCHASTIC APPROXIMATION FOR QUASI-STATIONARY DISTRIBUTIONS IN FINITE DIMENSIONS 21 (cid:12) (cid:12) Lemma 16. E(W |F ) = g (θ ) can be expanded as (cid:12) (cid:12) n n n n − − g (θ) = g (θ¯) + (Dg )(θ¯)(θ θ¯) + o( θ θ¯ ) n n n where the error o is uniform in n. Proof. Refer to proof of 9 for the components of g . Again, the h component causes no problem because −n | it is independent of n. (cid:34)B(cid:90)y deﬁning v(x, s(cid:32)) = E[e sτ X = x], f(cid:33)(µ,(cid:35)T), the µ component of g , can be (cid:88) 0 n n expanded as ∞ − fn(µ, T)(x) = E(cid:90)µ,T (cid:34)e−(T+n+τ 1)u (cid:88)τ 1(I(Xk = x) − µ(x)) du (cid:35) 0 k=0 ∞ ∞ = (cid:90) Eµ,T (cid:88)e−((cid:16)T+n+τ 1)u (cid:104)(I(τ > k, Xk = x) − I(τ > k)µ(x)) du (cid:105)(cid:17) 0 k=0 ∞ ∞ = (cid:90) e−Tu (cid:88) (cid:18)e−knu+1 Eµ (cid:20)e−(τ−k)nu+1 (I(τ > k, Xk = x) − I(τ > k)µ(x)) (cid:21)d(cid:19)u 0 k=0 ∞ ∞ = (cid:90) e−Tu (cid:88) (cid:18)e−knu+1 E(cid:20)µ v(Xk, n +u 1)(I(τ > k, Xk = x) − I(τ > k)(cid:21)µ(cid:19)(x)) du 0 k=0 ∞ ∞ = (cid:90) e−Tu (cid:20) e−knu+1 v(x, n +u 1)µ(cid:48)Qkδx − (µ(cid:48)Qkv(·, n +u 1))µ(x) du (cid:21) 0 k=0 ∞ − u (cid:48) − − − − (cid:48) − − − · u = e Tu v(x, n + 1)µ (I e nu+1 Q) 1δx µ (I e nu+1 Q) 1v( , n + 1))µ(x) du. 0 It is easy to see that integration and (partial) diﬀerentiation can be interchanged in this case because of the ≥ integrand’s smoothness and integrability. v(x, s) is bounded by 1 and 0 for s 0. The integrand consists − of a second-order expression in µ multiplied by an exponential damping factor e Tu. It is now clear that all the mixed second partial derivatives of f will be bounded uniformly in n in a neighborhood around the n (cid:3) stationary point θ¯ = (µ¯, T¯) since T¯ > 0. (cid:110) (cid:111) In order for the CLT to hold, the no(cid:110)rmaliz(cid:111)ed iterates θ√n−θ¯ has to be tight. (cid:15)n Lemma 17. The normalized iterates θ√n−θ¯ is tight. (cid:15)n Proof. Here make a slight modiﬁcation to the proof of Theorem 10.4.1 in [16]. We let A = (Dg)(θ¯). For any positive deﬁnite matrix C, there exists a positive deﬁnite solution P to the equation (cid:48) − A P + PA = C. We take this P and for each A = (Dg )(θ¯), we obtain a sequence of matrices C via n n n (cid:48) − A P + PA = C . n n n ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: STOCHASTIC

label: paragraph

text: APPROXIMATION

text: FOR

text: QUASI-STATIONARY

text: DISTRIBUTIONS

text: IN

text: FINITE

text: DIMENSIONS

text: Lemma

text: E(W

text: |F

text: g

text: (θ

text: can

text: be

text: expanded

text: as

text: n

text: n

text: n

text: n

text: g

text: (θ)

text: g

text: (θ¯)

text: (Dg

text: )(θ¯)(θ

text: θ¯)

text: o(

text: θ

text: θ¯

text: n

text: n

text: n

text: where

text: the

text: error

text: o

text: is

text: uniform

text: in

text: n.

text: Proof.

text: Refer

text: to

text: proof

text: of

text: for

text: the

text: components

text: of

text: g

text: Again,

text: the

text: h

text: component

text: causes

text: no

text: problem

text: because

text: −n

text: it

text: is

text: independent

text: of

text: n.

text: deﬁning

text: v(x,

text: E[e

text: sτ

text: X

text: x],

text: the

text: µ

text: component

text: of

text: g

text: can

text: be

text: n

text: n

text: expanded

text: as

text: fn(µ,

text: T)(x)

text: x)

text: µ(x))

text: du

text: Eµ,T

text: k,

text: Xk

text: x)

text: I(τ

text: k)µ(x))

text: du

text: e−Tu

text: Eµ

text: (I(τ

text: k,

text: Xk

text: x)

text: I(τ

text: k)µ(x))

text: e−Tu

text: v(Xk,

text: n

text: +u

text: k,

text: Xk

text: x)

text: I(τ

text: du

text: e−Tu

text: v(x,

text: n

text: +u

text: n

text: +u

text: du

text: u

text: u

text: e

text: Tu

text: v(x,

text: n

text: (I

text: e

text: Q)

text: µ

text: (I

text: e

text: Q)

text: n

text: du.

text: It

text: is

text: easy

text: to

text: see

text: that

text: integration

text: and

text: (partial)

text: diﬀerentiation

text: can

text: be

text: interchanged

text: in

text: this

text: case

text: because

text: of

text: the

text: integrand’s

text: smoothness

text: and

text: integrability.

text: v(x,

text: s)

text: is

text: bounded

text: by

text: and

text: for

text: s

text: The

text: integrand

text: consists

text: of

text: a

text: second-order

text: expression

text: in

text: µ

text: multiplied

text: by

text: an

text: exponential

text: damping

text: factor

text: e

text: Tu.

text: It

text: is

text: now

text: clear

text: that

text: all

text: the

text: mixed

text: second

text: partial

text: derivatives

text: of

text: f

text: will

text: be

text: bounded

text: uniformly

text: in

text: n

text: in

text: a

text: neighborhood

text: around

text: the

text: n

text: stationary

text: point

text: θ¯

text: (µ¯,

text: T¯)

text: since

text: T¯

text: In

text: order

text: for

text: the

text: CLT

text: to

text: hold,

text: the

text: iterates

text: θ√n−θ¯

text: has

text: to

text: be

text: tight.

text: Lemma

text: The

text: normalized

text: iterates

text: θ√n−θ¯

text: is

text: tight.

text: Proof.

text: Here

text: make

text: a

text: slight

text: modiﬁcation

text: to

text: the

text: proof

text: of

text: Theorem

text: in

text: We

text: let

text: A

text: (Dg)(θ¯).

text: For

text: any

text: positive

text: deﬁnite

text: matrix

text: C,

text: there

text: exists

text: a

text: positive

text: deﬁnite

text: solution

text: P

text: to

text: the

text: equation

text: A

text: P

text: PA

text: C.

text: We

text: take

text: this

text: P

text: and

text: for

text: each

text: A

text: (Dg

text: )(θ¯),

text: we

text: obtain

text: a

text: sequence

text: of

text: matrices

text: C

text: via

text: n

text: n

text: n

text: A

text: P

text: PA

text: C

text: n

text: n

text: n

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: STOCHASTIC APPROXIMATION FOR QUASI-STATIONARY DISTRIBUTIONS IN FINITE DIMENSIONS 23 (cid:34)(cid:80) (cid:35) (cid:34)(cid:32)(cid:88) T1¯E(cid:33)µ¯,(cid:18)T¯ τk=−01 (I((1X+k =τ ·)) − µ¯(·(cid:19)))I(τ ≤ √n)(cid:35) = (cid:46) nT¯ − √ 1 E τ 1 I · − · − τ 2 τ2 I ≤ (cid:46) T¯ µ¯,T¯ ( (Xk = ) µ¯( )) 1 nT¯ + (1 − c)3 n2T¯2 (τ n) = k=0 (cid:80) (1) + (2) + (3) where (1), (2), and (3) are obtained by multiplying τ−1 (I(X = ·) − µ¯(·)) through the second bracket. k=0 k c is a numbe(cid:34)r(cid:32)between 0 and τ . To(cid:33)get a bound(cid:35)on (1), we h(cid:34)a(cid:32)ve (cid:33)(cid:35) (cid:88) nT¯ (cid:88) − √ − E τ 1 I · − · I ≤ E (cid:34)(cid:32)τ 1 I · − · (cid:33) (cid:35) µ¯,T¯ ( (Xk = ) µ¯( )) (τ n) = µ¯,T¯ (cid:88) ( (Xk = ) µ¯( )) k=0 k=0 − √ − E τ 1 I · − · I µ¯,T¯ ( (Xk = ) µ¯( )) (τ > n) k=√0 − − = 0 O(e c n). (cid:12) (cid:12) Modulus of (2) becomes boun(cid:12)(cid:12)d(cid:88)ed by (cid:12)(cid:12) (cid:18) (cid:19) (cid:12) (cid:12) (cid:12) − (cid:12) √ E τ 1 I · − · τ I ≤ 1 µ¯,T¯ ( (Xk = ) µ¯( )) nT¯ (τ n) = O n . Modulus of (3) becomes bound(cid:12)(cid:12)(cid:12)e(cid:88)dk=b0y (cid:12)(cid:12)(cid:12) (cid:18) (cid:19) (cid:12) (cid:12) (cid:12) − (cid:12) √ E τ 1 I · − · 4τ2 I ≤ 1 µ¯,T¯ ( (Xk = ) µ¯( )) n2T¯2 (τ n) = O n . k=0 (cid:3) (cid:80) − Lemma 19. lim √1 n+mt 1 g (θ¯) = 0 uniformly in each small t-interval. n,m m i=n i (cid:80) (cid:0) (cid:1) − − − Proof. By Lemma 18, the expression becomes √1 n+mt 1 O 1 = √1 O(log(n + mt 1) log n). If we m i=n i m maximize n for every m, we ﬁnd that the log diﬀerence is maximized when n = 1. Hence the limit becomes bounded by √1 → O(log(mt)) 0 m (cid:3) uniformly on a small t-interval. ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: STOCHASTIC

text: APPROXIMATION

text: FOR

text: QUASI-STATIONARY

text: DISTRIBUTIONS

text: IN

text: FINITE

text: DIMENSIONS

label: equation

text: =τ

text: nT¯

text: E

text: τ

text: I

text: τ

text: τ2

text: I

text: T¯

text: µ¯,T¯

text: (Xk

text: µ¯(

text: nT¯

text: (τ

text: n)

text: where

text: and

text: are

text: obtained

text: by

text: multiplying

text: τ−1

text: (I(X

text: µ¯(·))

text: through

text: the

text: second

text: bracket.

text: k

text: c

text: is

text: a

text: and

text: τ

text: a

text: we

text: nT¯

text: E

text: τ

text: I

text: I

text: E

text: I

text: µ¯,T¯

text: (Xk

text: µ¯(

text: (τ

text: n)

text: µ¯,T¯

text: (Xk

text: µ¯(

text: E

text: τ

text: I

text: I

text: µ¯,T¯

text: (Xk

text: µ¯(

text: (τ

text: n)

text: O(e

text: c

text: n).

text: Modulus

text: of

text: becomes

text: by

text: E

text: τ

text: I

text: τ

text: I

text: µ¯,T¯

text: (Xk

text: µ¯(

text: nT¯

text: (τ

text: n)

text: O

text: n

text: Modulus

text: of

text: becomes

text: E

text: τ

text: I

text: I

text: µ¯,T¯

text: (Xk

text: µ¯(

text: (τ

text: n)

text: O

text: n

text: Lemma

text: lim

text: √1

text: n+mt

text: g

text: (θ¯)

text: uniformly

text: in

text: each

text: small

text: t-interval.

text: n,m

text: m

text: i=n

text: i

text: Proof.

text: By

text: Lemma

text: the

text: expression

text: becomes

text: √1

text: n+mt

text: O

text: √1

text: O(log(n

text: mt

text: log

text: n).

text: If

text: we

text: m

text: i=n

text: i

text: m

text: maximize

text: n

text: for

text: every

text: m,

text: we

text: ﬁnd

text: that

text: the

text: log

text: diﬀerence

text: is

text: maximized

text: when

text: n

text: Hence

text: the

text: limit

text: becomes

text: bounded

text: by

text: √1

text: O(log(mt))

text: m

text: uniformly

text: on

text: a

text: small

text: t-interval.

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: STOCHASTIC APPROXIMATION FOR QUASI-STATIONARY DISTRIBUTIONS IN FINITE DIMENSIONS 28 − − Lemma 25. Given a transition rate matrix Q, exp( Q) 1 is a matrix of non-negative entries (cid:2) (cid:0) (cid:1)(cid:3) (cid:80) Proof. Let α be the maximum of the diagonal element of −Q. Notice that −Q−1 = α I − 1 Q + I −1 = α α ≥ ( 1 Q + I)k for α large enough. 1 Q + I is a non-negative irreducible matrix hence the inﬁnite sum is k 0 α α (cid:3) also a positive matrix. Lemma 26. The principal eigenvalue of Q is real and smaller than 0, and also the left and right principal eigenspaces are one-dimensional. (cid:107) (cid:107) ≤ Proof. The spectral radius is bounded above by Q ∞ 0. Q + cI can be made into a irreducible non- (cid:3) negative matrix for some large c. All the properties follow after applying Perron-Frobenius to that. Analogous to Lemma 15, we need to show that T is bounded above and below almost surely. n Lemma 27. The T sequence in the continuous-time case is bounded above and below almost surely by ﬁnite n random variables. Proof. The upper bound is identical to the discrete-time case (Lemma 15). For the lower bound, we consider a random variable s˜ that is an exponential rate corresponding to the slowest holding rate of the Markov chain. This way, s˜(k) can be coupled to the ﬁrst holding time of the Markov chain during the k-th iteration. This way, τ(k) ≥ s˜(k). Hence lim T ≥ E(s˜) implying that its bounded below by a ﬁnite random variable. (cid:3) a.s. n n Figures ##LTLine## ##LTLine## ##LTLine##

text: STOCHASTIC

text: APPROXIMATION

text: FOR

text: QUASI-STATIONARY

text: DISTRIBUTIONS

text: IN

text: FINITE

text: DIMENSIONS

text: Lemma

text: Given

text: a

text: transition

text: rate

text: matrix

text: Q,

text: exp(

text: Q)

text: is

text: a

text: matrix

text: of

text: non-negative

text: entries

text: Proof.

text: Let

text: α

text: be

text: the

text: maximum

text: of

text: the

text: diagonal

text: element

text: of

text: −Q.

text: Notice

text: that

text: −Q−1

text: α

text: I

text: Q

text: I

text: −1

text: α

text: α

text: Q

text: I)k

text: for

text: α

text: large

text: enough.

text: Q

text: I

text: is

text: a

text: non-negative

text: irreducible

text: matrix

text: hence

text: the

text: inﬁnite

text: sum

text: is

text: k

text: α

text: α

text: also

text: a

text: positive

text: matrix.

text: Lemma

text: The

text: principal

text: eigenvalue

text: of

text: Q

text: is

text: real

text: and

text: smaller

text: than

text: and

text: also

text: the

text: left

text: and

text: right

text: principal

text: eigenspaces

text: are

text: one-dimensional.

text: Proof.

text: The

text: spectral

text: radius

text: is

text: bounded

text: above

text: by

text: Q

text: Q

text: cI

text: can

text: be

text: made

text: into

text: a

text: irreducible

text: non-

text: negative

text: matrix

text: for

text: some

text: large

text: c.

text: All

text: the

text: properties

text: follow

text: after

text: applying

text: Perron-Frobenius

text: to

text: that.

text: Analogous

text: to

text: Lemma

text: we

text: need

text: to

text: show

text: that

text: T

text: is

text: bounded

text: above

text: and

text: below

text: almost

text: surely.

text: n

text: Lemma

text: The

text: T

text: sequence

text: in

text: the

text: continuous-time

text: case

text: is

text: bounded

text: above

text: and

text: below

text: almost

text: surely

text: by

text: ﬁnite

text: n

text: random

text: variables.

text: Proof.

text: The

text: upper

text: bound

text: is

text: identical

text: to

text: the

text: discrete-time

text: case

text: (Lemma

text: For

text: the

text: lower

text: bound,

text: we

text: consider

text: a

text: random

text: variable

text: s˜

text: that

text: is

text: an

text: exponential

text: rate

text: corresponding

text: to

text: the

text: slowest

text: holding

text: rate

text: of

text: the

text: Markov

text: chain.

text: This

text: way,

text: s˜(k)

text: can

text: be

text: coupled

text: to

text: the

text: ﬁrst

text: holding

text: time

text: of

text: the

text: Markov

text: chain

text: during

text: the

text: k-th

text: iteration.

text: This

text: way,

text: τ(k)

text: s˜(k).

text: Hence

text: lim

text: T

text: E(s˜)

text: implying

text: that

text: its

text: bounded

text: below

text: by

text: a

text: ﬁnite

text: random

text: variable.

text: a.s.

text: n

text: n

text: Figures

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: STOCHASTIC APPROXIMATION FOR QUASI-STATIONARY DISTRIBUTIONS IN FINITE DIMENSIONS 8 (cid:88) (cid:48) (cid:48) µ Q = ρµ µ = 1 i ≥ µ 0 i − and ρ = 1 1 . By TheoremE5µ.2(τ.1) from [16], we can conclude that µ converges to the quasi-stationary distribution for n all initial conﬁgurations (µ , T ). 0 0 Equation (4) can be analyzed for its rate of convergence. Here we invoke the Theorem 10.2.1 of [16]. Because our algorithm uses a step size of O( 1 ), we eventually conclude that a CLT exists as long as the n − Jacobian matrix of the ODE vector ﬁeld has spectral radius less than 1. This is equivalent to requiring that (cid:18) (cid:19) (cid:18) (cid:19) 2 1 1 1 ∀ (6) Re − < − λ non-principal eigenvalues 1 λ 2 1 λ NPV NPV PV (cid:3) where the λ’s are the eigenvalues of the Q matrix. 5. Variations on the Existing Algorithm with Improved Rate of Convergence One interesting question to ask is what happens when the suﬃcient conditions for CLT are not met. We will study a simple example consisting of two states.   { } Imagine we have a Markov chain with three states 0, 1, 2 and transition matrix   1 0 0 − − (cid:15) 1 (cid:15) 1 (cid:15) . −2 −2 (cid:15) 1 (cid:15) 1 (cid:15) 2 2 { } Obviously the state 0 is the absorbing state. In this setup, because of symmetry, our Algorithm 1 reduces to − (1) With probability 1 (cid:15) sample either the state 1 or 2 (without knowing the previous state. This is 2 OK by symmetry) and add to the empirical distribution. (2) With probability (cid:15), sample from either 1 or 2 according to the empirical distribution up until this point. We recognize this as a self-interacting Markov chain. { } A self-interacting Markov chain (SIMC) [9] is a stochastic process X such that n P ∈ |F (X dx ) = Φ(S )(dx) n+1 n n where Φ is a function that transforms one measure into another measure and S is the empirical measure { } n generated by X n . k k=0 (cid:90) Our Algorithm 1 for the above “loopy Markov chain” reduces to the empirical process of a SIMC X n governed by the functional P |F (X = dz ) = K(x, dz)dS (dx) n+1 n n ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: STOCHASTIC

text: APPROXIMATION

text: FOR

text: QUASI-STATIONARY

text: DISTRIBUTIONS

text: IN

text: FINITE

text: DIMENSIONS

text: µ

text: Q

text: ρµ

text: µ

text: i

text: µ

text: i

text: and

text: ρ

text: By

text: from

text: we

text: can

text: conclude

text: that

text: µ

text: converges

text: to

text: the

text: quasi-stationary

text: distribution

text: for

text: n

text: all

text: initial

text: conﬁgurations

text: (µ

text: T

text: Equation

text: can

text: be

text: analyzed

text: for

text: its

text: rate

text: of

text: convergence.

text: Here

text: we

text: invoke

text: the

text: Theorem

text: of

text: Because

text: our

text: algorithm

text: uses

text: a

text: step

text: size

text: of

text: O(

text: we

text: eventually

text: conclude

text: that

text: a

text: CLT

text: exists

text: as

text: long

text: as

text: the

text: n

text: Jacobian

text: matrix

text: of

text: the

text: ODE

text: vector

text: ﬁeld

text: has

text: spectral

text: radius

text: less

text: than

text: This

text: is

text: equivalent

text: to

text: requiring

text: that

text: Re

text: λ

text: non-principal

text: eigenvalues

text: λ

text: λ

text: NPV

text: NPV

text: PV

text: where

text: the

text: λ’s

text: are

text: the

text: eigenvalues

text: of

text: the

text: Q

text: matrix.

text: Variations

text: on

text: the

text: Existing

text: Algorithm

text: with

text: Improved

text: Rate

text: of

text: Convergence

text: One

text: interesting

text: question

text: to

text: ask

text: is

text: what

text: happens

text: when

text: the

text: suﬃcient

text: conditions

text: for

text: CLT

text: are

text: not

text: met.

text: We

text: will

text: study

text: a

text: simple

text: example

text: consisting

text: of

text: two

text: states.

text: Imagine

text: we

text: have

text: a

text: Markov

text: chain

text: with

text: three

text: states

text: and

text: transition

text: matrix

text: −2

text: −2

text: Obviously

text: the

text: state

text: is

text: the

text: absorbing

text: state.

text: In

text: this

text: setup,

text: because

text: of

text: symmetry,

text: our

text: Algorithm

text: reduces

text: to

text: With

text: probability

text: sample

text: either

text: the

text: state

text: or

text: (without

text: knowing

text: the

text: previous

text: state.

text: This

text: is

text: OK

text: by

text: symmetry)

text: and

text: add

text: to

text: the

text: empirical

text: distribution.

text: With

text: probability

text: sample

text: from

text: either

text: or

text: according

text: to

text: the

text: empirical

text: distribution

text: up

text: until

text: this

text: point.

text: We

text: recognize

text: this

text: as

text: a

text: self-interacting

text: Markov

text: chain.

text: A

text: self-interacting

text: Markov

text: chain

text: (SIMC)

text: is

text: a

text: stochastic

text: process

text: X

text: such

text: that

text: n

text: P

text: |F

text: (X

text: dx

text: Φ(S

text: )(dx)

text: n

text: n

text: where

text: Φ

text: is

text: a

text: function

text: that

text: transforms

text: one

text: measure

text: into

text: another

text: measure

text: and

text: S

text: is

text: the

text: empirical

text: measure

text: n

text: generated

text: by

text: X

text: n

text: k

text: Our

text: Algorithm

text: for

text: the

text: above

text: “loopy

text: Markov

text: chain”

text: reduces

text: to

text: the

text: empirical

text: process

text: of

text: a

text: SIMC

text: X

text: n

text: governed

text: by

text: the

text: functional

text: P

text: |F

text: (X

text: dz

text: K(x,

text: dz)dS

text: (dx)

text: n

text: n

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: ∗ † Han Wang,1 Yingying Dai,1 Teng Yang,1 Weijun Ren,1 and Zhidong Zhang1, (Dated: May 26, 2020) We study nonlinear dynamics of coupled Skyrmions and present a method for manipulating topo- logical resonant excitations by a dual-frequency microwave ﬁeld. Thiele’s equation is extended by introducing a new eﬀective mass associated with time derivative of topological density. Two cou- pled resonant modes endowed with the new eﬀective mass are found in the coupled Skyrmions. Polygon-like resonant excitations are observed and modulated when the two modes are activated simultaneously by microwave ﬁeld with commensurate frequency ratio. Quasiperiodic behavior of excitations are related to an incommensurate ratio. Numerical solutions based on the extended Thiele’s equation for Skyrmion under a dual-frequency ﬁeld agree well with the micromagnetic sim- ulation results and clarify the importance of frequency value, frequency ratio of an external ﬁeld and the eﬀective mass to the polygon-like dynamics of Skyrmion. We also show the coupling between two Skyrmions can dominate their topological resonant excitations. PACS numbers: 52.55.-s, 75.78.Cd, 12.39.Dc, 75.50.Ss INTRODUCTION associated with topological density distribution is intro- duced into Thiele’s equation to describe the dynamics Resonant excitations of topological objects have aroused of coupled Skyrmions with nonlocal deformation. We a great deal of attention owe to both fundamental physics ﬁnd two resonant modes with opposite sense of rotation and potential application as microwave devices.[1, 2] Res- under single-frequency microwave ﬁeld. The two modes onant excitations of vortices, which are always treated have dynamically coupled phase under a dual-frequency as massless particles with charges due to their small and ﬁeld, which has not been discovered before. By mod- local deformations,[3–5] show only circular or elliptical ulating the commensurate ratio of the dual-frequencies, trajectories in linear regime and stadium-like orbits in we obtain polygon-like resonant excitation and are able nonlinear regime.[4, 6] For dynamics of bubble, an iner- to controllably change it. Quasiperiodic behavior is ob- tial mass is considered due to the local deformation of served when the frequency ratio is incommensurate. Nu- one-dimensional (1D) domain wall.[7] merical solutions to the extended Thiele’s equation are in best agreement with the micromagnetic simulation re- Skrymion is another nontrivial topological object, sults and veriﬁes that the eﬀective mass is vital to the which was recently observed experimentally in helical polygon-like resonant excitations of Skyrmion as well as magnets,[8–14] and also predicted to exist in coupled the value of frequency and the frequency ratio of the ex- ordinary magnets.[15, 16] In contrast to vortices and ternal ﬁeld. We also show the perpendicular coupling bubbles, Skyrmions have the smooth global spin tex- between two Skyrmions is crucial to their dynamics. tures. Their deformations under resonant excitation will be nonlocal and so large that they can’t be treated as METHODS particles or 1D domain walls, and the nonlinear dynamic equation has to include higher-order gyrotropic terms. Resonance excitation of two coupled Skyrmions in The resonant excitation behavior are diﬀerent from that Co/Ru/Co nanodisks under in-plane microwave mag- of other topological objects with very local deformation. netic ﬁelds was studied using OOMMF code.[25] The ma- Skyrmions are envisioned promising candidate for terial parameters of hexagonal-close-packed (hcp) cobalt × applications in spintronics, magnetic storage and mi- chosen include the saturation magnetization M =1.4 106 × − s crowave devices,[17–20] because of their nanoscale size, A/m, the exchange stiﬀness A =3 10 11 J/m and the ex × high structural stability, low threshold current den- uniaxial anisotropy constant K =5.2 105 J/m3 with the u sity to drive their motion, and intriguing magnetoelec- direction perpendicular to the nanodisk plane. The in- tric eﬀect.[9, 20–22] Therefore, besides spin-polarized terfacial coupling constant of the adjacent surfaces was × − current,[23, 24] searching other methods of eﬃciently ma- -5 10 5 J/m2 according to Ref. 26. A dimensionless nipulating Skyrmions embedded in magnetic conductor damping α was 0.02. The radius R of a Co/Ru/Co and insulator is an important subject. The investigations nanodisk was 100 nm. The thickness L of Co was 18 of resonant excitation of Skyrmion or coupled Skyrmions nm, while that of Ru was 2 nm. The cell size was × × have great signiﬁcance to the Skyrmion dynamics and is 2 2 2 nm3, which is smaller than the exchange length crucial for their practical application. of cobalt (about 4.94 nm). The in-plane microwave In this work, we present an approach for manipulating ﬁeld was applied in x-direction to drive Skyrmion mo- topological resonant excitations of coupled Skyrmions by tion. The frequency of external ﬁeld is equal or close a dual-frequency microwave ﬁeld. A new eﬀective mass to the eigenfrequency of system to make Skyrmion

text: Han

label: author

text: Yingying

text: Teng

text: Weijun

text: and

text: Zhidong

text: (Dated:

text: May

label: date

text: We

label: abstract

text: study

text: nonlinear

text: dynamics

text: of

text: coupled

text: Skyrmions

text: and

text: present

text: a

text: method

text: for

text: manipulating

text: topo-

text: logical

text: resonant

text: excitations

text: by

text: a

text: dual-frequency

text: microwave

text: ﬁeld.

text: Thiele’s

text: equation

text: is

text: extended

text: by

text: introducing

text: a

text: new

text: eﬀective

text: mass

text: associated

text: with

text: time

text: derivative

text: of

text: topological

text: density.

text: Two

text: cou-

text: pled

text: resonant

text: modes

text: endowed

text: with

text: the

text: new

text: eﬀective

text: mass

text: are

text: found

text: in

text: the

text: coupled

text: Skyrmions.

text: Polygon-like

text: resonant

text: excitations

text: are

text: observed

text: and

text: modulated

text: when

text: the

text: two

text: modes

text: are

text: activated

text: simultaneously

text: by

text: microwave

text: ﬁeld

text: with

text: commensurate

text: frequency

text: ratio.

text: Quasiperiodic

text: behavior

text: of

text: excitations

text: are

text: related

text: to

text: an

text: incommensurate

text: ratio.

text: Numerical

text: solutions

text: based

text: on

text: the

text: extended

text: Thiele’s

text: equation

text: for

text: Skyrmion

text: under

text: a

text: dual-frequency

text: ﬁeld

text: agree

text: well

text: with

text: the

text: micromagnetic

text: sim-

text: ulation

text: results

text: and

text: clarify

text: the

text: importance

text: of

text: frequency

text: value,

text: frequency

text: ratio

text: of

text: an

text: external

text: ﬁeld

text: and

text: the

text: eﬀective

text: mass

text: to

text: the

text: polygon-like

text: dynamics

text: of

text: Skyrmion.

text: We

text: also

text: show

text: the

text: coupling

text: between

text: two

text: Skyrmions

text: can

text: dominate

text: their

text: topological

text: resonant

text: excitations.

text: PACS

text: numbers:

text: INTRODUCTION

text: associated

text: with

text: topological

text: density

text: distribution

text: is

text: intro-

text: duced

text: into

text: Thiele’s

text: equation

text: to

text: describe

text: the

text: dynamics

text: Resonant

text: excitations

text: of

text: topological

text: objects

text: have

text: aroused

text: of

text: coupled

text: Skyrmions

text: with

text: nonlocal

text: deformation.

text: We

text: a

text: great

text: deal

text: of

text: attention

text: owe

text: to

text: both

text: fundamental

text: physics

text: ﬁnd

text: two

text: resonant

text: modes

text: with

text: opposite

text: sense

text: of

text: rotation

text: and

text: potential

text: application

text: as

text: microwave

text: Res-

text: under

text: single-frequency

text: microwave

text: ﬁeld.

text: The

text: two

text: modes

text: onant

text: excitations

text: of

text: vortices,

text: which

text: are

text: always

text: treated

text: have

text: dynamically

text: coupled

text: phase

text: under

text: a

text: dual-frequency

text: as

text: massless

text: particles

text: with

text: charges

text: due

text: to

text: their

text: small

text: and

text: ﬁeld,

text: which

text: has

text: not

text: been

text: discovered

text: before.

text: By

text: mod-

text: local

text: show

text: only

text: circular

text: or

text: elliptical

text: ulating

text: the

text: commensurate

text: ratio

text: of

text: the

text: dual-frequencies,

text: trajectories

text: in

text: linear

text: regime

text: and

text: stadium-like

text: orbits

text: in

text: we

text: obtain

text: polygon-like

text: resonant

text: excitation

text: and

text: are

text: able

text: nonlinear

text: For

text: dynamics

text: of

text: bubble,

text: an

text: iner-

text: to

text: controllably

text: change

text: it.

text: Quasiperiodic

text: behavior

text: is

text: ob-

text: tial

text: mass

text: is

text: considered

text: due

text: to

text: the

text: local

text: deformation

text: of

text: served

text: when

text: the

text: frequency

text: ratio

text: is

text: incommensurate.

text: Nu-

text: one-dimensional

text: domain

text: merical

text: solutions

text: to

text: the

text: extended

text: Thiele’s

text: equation

text: are

text: in

text: best

text: agreement

text: with

text: the

text: micromagnetic

text: simulation

text: re-

text: Skrymion

text: is

text: another

text: nontrivial

text: topological

text: object,

text: sults

text: and

text: veriﬁes

text: that

text: the

text: eﬀective

text: mass

text: is

text: vital

text: to

text: the

text: which

text: was

text: recently

text: observed

text: experimentally

text: in

text: helical

text: polygon-like

text: resonant

text: excitations

text: of

text: Skyrmion

text: as

text: well

text: as

text: and

text: also

text: predicted

text: to

text: exist

text: in

text: coupled

text: the

text: value

text: of

text: frequency

text: and

text: the

text: frequency

text: ratio

text: of

text: the

text: ex-

text: ordinary

text: In

text: contrast

text: to

text: vortices

text: and

text: ternal

text: ﬁeld.

text: We

text: also

text: show

text: the

text: perpendicular

text: coupling

text: bubbles,

text: Skyrmions

text: have

text: the

text: smooth

text: global

text: spin

text: tex-

text: between

text: two

text: Skyrmions

text: is

text: crucial

text: to

text: their

text: dynamics.

text: tures.

text: Their

text: deformations

text: under

text: resonant

text: excitation

text: will

text: be

text: nonlocal

text: and

text: so

text: large

text: that

text: they

text: can’t

text: be

text: treated

text: as

text: METHODS

text: particles

text: or

text: domain

text: walls,

text: and

text: the

text: nonlinear

text: dynamic

text: equation

text: has

text: to

text: include

text: higher-order

text: gyrotropic

text: terms.

text: Resonance

text: excitation

text: of

text: two

text: coupled

text: Skyrmions

text: in

text: The

text: resonant

text: excitation

text: behavior

text: are

text: diﬀerent

text: from

text: that

text: Co/Ru/Co

text: nanodisks

text: under

text: in-plane

text: microwave

text: mag-

text: of

text: other

text: topological

text: objects

text: with

text: very

text: local

text: deformation.

text: netic

text: ﬁelds

text: was

text: studied

text: using

text: OOMMF

text: The

text: ma-

text: Skyrmions

text: are

text: envisioned

text: promising

text: candidate

text: for

text: terial

text: parameters

text: of

text: hexagonal-close-packed

text: (hcp)

text: cobalt

text: applications

text: in

text: spintronics,

text: magnetic

text: storage

text: and

text: mi-

text: chosen

text: include

text: the

text: saturation

text: magnetization

text: M

text: s

text: crowave

text: because

text: of

text: their

text: nanoscale

text: size,

text: A/m,

text: the

text: exchange

text: stiﬀness

text: A

text: J/m

text: and

text: the

text: ex

text: high

text: structural

text: stability,

text: low

text: threshold

text: current

text: den-

text: uniaxial

text: anisotropy

text: constant

text: K

text: with

text: the

text: u

text: sity

text: to

text: drive

text: their

text: motion,

text: and

text: intriguing

text: magnetoelec-

text: direction

text: perpendicular

text: to

text: the

text: nanodisk

text: plane.

text: The

text: in-

text: tric

text: Therefore,

text: besides

text: spin-polarized

text: terfacial

text: coupling

text: constant

text: of

text: the

text: adjacent

text: surfaces

text: was

text: searching

text: other

text: methods

text: of

text: eﬃciently

text: ma-

text: according

text: to

text: Ref.

text: A

text: dimensionless

text: nipulating

text: Skyrmions

text: embedded

text: in

text: magnetic

text: conductor

text: damping

text: α

text: was

text: The

text: radius

text: R

text: of

text: a

text: Co/Ru/Co

text: and

text: insulator

text: is

text: an

text: important

text: subject.

text: The

text: investigations

text: nanodisk

text: was

text: nm.

text: The

text: thickness

text: L

text: of

text: Co

text: was

text: of

text: resonant

text: excitation

text: of

text: Skyrmion

text: or

text: coupled

text: Skyrmions

text: nm,

text: while

text: that

text: of

text: Ru

text: was

text: nm.

text: The

text: cell

text: size

text: was

text: have

text: great

text: signiﬁcance

text: to

text: the

text: Skyrmion

text: dynamics

text: and

text: is

text: which

text: is

text: smaller

text: than

text: the

text: exchange

text: length

text: crucial

text: for

text: their

text: practical

text: application.

text: of

text: cobalt

text: (about

text: nm).

text: The

text: in-plane

text: microwave

text: In

text: this

text: work,

text: we

text: present

text: an

text: approach

text: for

text: manipulating

text: ﬁeld

text: was

text: applied

text: in

text: x-direction

text: to

text: drive

text: Skyrmion

text: mo-

text: topological

text: resonant

text: excitations

text: of

text: coupled

text: Skyrmions

text: by

text: tion.

text: The

text: frequency

text: of

text: external

text: ﬁeld

text: is

text: equal

text: or

text: close

text: a

text: dual-frequency

text: microwave

text: ﬁeld.

text: A

text: new

text: eﬀective

text: mass

text: to

text: the

text: eigenfrequency

text: of

text: system

text: to

text: make

text: Skyrmion


text: (cid:40) (cid:41) (cid:40) (cid:41) (cid:18) (cid:19) (cid:12) (cid:12) (cid:16) (cid:88) (cid:17) (cid:12) (cid:12) (cid:48) K − ≤ N F (cid:48) ξ Pr sup Eτ f E(T)f > ξ 8 w,τ( , ξ /8, 2N) exp N + N Γ − , (23) ∈F w 1 T k (b a) f k=1 − (cid:12) where Γ(x) := x (x + 1) ln(x + 1). (cid:12) (cid:12) (cid:12) − In the above theorem, we show that the probability that the generalization bound sup ∈F Eτ f f w − E(T)f is larger than a certain number ξ > (1 τ)DF(w)(S, T ) can be bounded by the right-hand side of (23). Compared with the Hoeﬀding-type result (20), there are two limitations in this result: • this generalization bound is actually the minimum value with respect to w and τ, and does not reﬂect how the two parameters aﬀect the bound. The result presented in the above theorem is not completely satisfactory because it is hard to obtain the analytical expression of the inverse − − function of A(eax 1) + B(ebx 1) for any non-trivial A, B, a, b > 0 (see Proof of(cid:12)Theorem A.2)(cid:12); (cid:12) (cid:12) • − since it is also hard to obtain the analytical expression of the inverse function of Γ(x) = x (x + − 1) ln(x + 1), the result (23) cannot directly lead to the upper bound of sup ∈F Eτ f E(T)f , f w − while the Hoeﬀding-type result (20) does. Instead, one generally uses x2 to approximate the 2+(2x/3) function Γ(x), which leads to Bernstein-type alternative expression of the bound (23): (cid:0) (cid:1) (cid:12) (cid:12) (cid:12) (cid:12) (cid:80) − N F (cid:48) − − ≤ − (cid:113) 4(b a) ln w,τ( , ξ /8, 2N) ln((cid:15)/8) sup E f Ef (1 τ)DF(w)(S(cid:0), T ) + 1 (cid:1) f∈F N (cid:113) 3(NT + Kk=1 Nk) − N F(cid:80) (cid:48) − (b a) 2 ln w,τ( , ξ /8, 2N) ln((cid:15)/8) 1 + . (24) N + K N T k=1 k Compared to the Hoeﬀding-type result (20), the alternative expression (24) implies that the Bennett- type bound (23) does not provide stronger bounds for representative domain adaptation. First, the bound (24) does not reﬂect how the parameters w and τ aﬀect the performance of representative domain adaptation. Second, according to the Bernstein-type alternative expression (24), its rate of convergence is the same as that of the Hoeﬀding-type result (20). Next, we present a new alternative expression of (23), which shows that the Bennett-type results can provide a faster rate of convergence than the Hoeﬀding-type bounds in addition to a more detailed description of the asymptotical behavior of the learning process. 5.3 Alternative Expression of Bennett-type Generalization Bound Diﬀerent from the Bernstein-type result (24), we introduce a new technique to deal with the term (cid:0) (cid:1) Γ(x) and the details of the technique are referred to Zhang [31]. Consider a function − ln ((x + 1) ln(x + 1) x)/c 1 η(c ; x) := , (25) 1 ln(x) (cid:101) (cid:101) − ≤ − − ≤ ∈and there hold∈s that Γ(x) = c1xη(c1,x) c1xη < c−1x2 for any 0 < η(c1; x) η < 2 with x (0, 1/8] and c (0.0075, 0.4804). By replacing Γ(x) with c xη, we then obtain another alternative 1 1 expression of the Bennett-type bound (23) as follows: 12 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: K

text: N

text: F

text: ξ

text: Pr

text: sup

text: Eτ

text: f

text: E(T)f

text: ξ

text: w,τ(

text: ξ

text: exp

text: N

text: N

text: Γ

text: ∈F

text: w

text: T

text: k

text: (b

text: a)

text: f

text: where

text: Γ(x)

text: x

text: (x

text: ln(x

text: In

text: the

text: above

text: theorem,

text: we

text: show

text: that

text: the

text: probability

text: that

text: the

text: generalization

text: bound

text: sup

text: ∈F

text: Eτ

text: f

text: f

text: w

text: E(T)f

text: is

text: larger

text: than

text: a

text: certain

text: number

text: ξ

text: τ)DF(w)(S,

text: T

text: can

text: be

text: bounded

text: by

text: the

text: right-hand

text: side

text: of

text: Compared

text: with

text: the

text: Hoeﬀding-type

text: result

text: there

text: are

text: two

text: limitations

text: in

text: this

text: result:

text: this

text: generalization

text: bound

text: is

text: actually

text: the

text: minimum

text: value

text: with

text: respect

text: to

text: w

text: and

text: τ,

text: and

text: does

text: not

text: reﬂect

text: how

text: the

text: two

text: parameters

text: aﬀect

text: the

text: bound.

text: The

text: result

text: presented

text: in

text: the

text: above

text: theorem

text: is

text: not

text: completely

text: satisfactory

text: because

text: it

text: is

text: hard

text: to

text: obtain

text: the

text: analytical

text: expression

text: of

text: the

text: inverse

text: function

text: of

text: A(eax

text: B(ebx

text: for

text: any

text: non-trivial

text: A,

text: B,

text: a,

text: b

text: (see

text: Proof

text: since

text: it

text: is

text: also

text: hard

text: to

text: obtain

text: the

text: analytical

text: expression

text: of

text: the

text: inverse

text: function

text: of

text: Γ(x)

text: x

text: (x

text: ln(x

text: the

text: result

text: cannot

text: directly

text: lead

text: to

text: the

text: upper

text: bound

text: of

text: sup

text: ∈F

text: Eτ

text: f

text: E(T)f

text: f

text: w

text: while

text: the

text: Hoeﬀding-type

text: result

text: does.

text: Instead,

text: one

text: generally

text: uses

text: to

text: approximate

text: the

text: function

text: Γ(x),

text: which

text: leads

text: to

text: Bernstein-type

text: alternative

text: expression

text: of

text: the

text: bound

text: N

text: F

text: a)

text: ln

text: w,τ(

text: ξ

text: sup

text: E

text: f

text: Ef

text: T

text: f∈F

text: N

text: Nk)

text: N

text: (b

text: a)

text: ln

text: w,τ(

text: ξ

text: N

text: K

text: N

text: T

text: k

text: Compared

text: to

text: the

text: Hoeﬀding-type

text: result

text: the

text: alternative

text: expression

text: implies

text: that

text: the

text: Bennett-

text: type

text: bound

text: does

text: not

text: provide

text: stronger

text: bounds

text: for

text: representative

text: domain

text: adaptation.

text: First,

text: the

text: bound

text: does

text: not

text: reﬂect

text: how

text: the

text: parameters

text: w

text: and

text: τ

text: aﬀect

text: the

text: performance

text: of

text: representative

text: domain

text: adaptation.

text: Second,

text: according

text: to

text: the

text: Bernstein-type

text: alternative

text: expression

text: its

text: rate

text: of

text: convergence

text: is

text: the

text: same

text: as

text: that

text: of

text: the

text: Hoeﬀding-type

text: result

text: Next,

text: we

text: present

text: a

text: new

text: alternative

text: expression

text: of

text: which

text: shows

text: that

text: the

text: Bennett-type

text: results

text: can

text: provide

text: a

text: faster

text: rate

text: of

text: convergence

text: than

text: the

text: Hoeﬀding-type

text: bounds

text: in

text: addition

text: to

text: a

text: more

text: detailed

text: description

text: of

text: the

text: asymptotical

text: behavior

text: of

text: the

text: learning

text: process.

text: Alternative

text: Expression

text: of

text: Bennett-type

text: Generalization

text: Bound

text: Diﬀerent

text: from

text: the

text: Bernstein-type

text: result

text: we

text: introduce

text: a

text: new

text: technique

text: to

text: deal

text: with

text: the

text: term

text: Γ(x)

text: and

text: the

text: details

text: of

text: the

text: technique

text: are

text: referred

text: to

text: Zhang

text: Consider

text: a

text: function

text: ln

text: ((x

text: ln(x

text: x)/c

text: η(c

text: x)

text: ln(x)

text: ∈and

text: there

text: hold∈s

text: that

text: Γ(x)

text: for

text: any

text: x)

text: η

text: with

text: x

text: and

text: c

text: By

text: replacing

text: Γ(x)

text: with

text: c

text: xη,

text: we

text: then

text: obtain

text: another

text: alternative

text: expression

text: of

text: the

text: Bennett-type

text: bound

text: as

text: follows:

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: (cid:80) (cid:80) ≤ ≤ Theorem 5.3 Under the notations of Theorem 5.1, set w = N / K N (1 k K) and τ = N /(N + K N ). Then, given any ξ > ((cid:88)1 − τ)DF(w)(S,kT ), wek havke=f1or kany N , N , · · · , N ∈ N T T k=1 k T 1 K such that − K ≥ (b a)2 N + N (cid:48) T k 8(ξ )2 k=1 − with probability at least 1 (cid:15), (cid:32) (cid:33) (cid:12) (cid:12) (cid:12) (cid:12) (cid:80) N F (cid:48) − 1 − ≤ − − ln w,τ( , ξ , 2N) ln( (cid:15) ) η sup Eτ f E(T)f (1 τ)DF(w)(S, T ) + (b a) 1 8 8 , (26) f∈F w N(cid:80)T + Kk=1 Nk (cid:48) − − N F (cid:48) ∈ where ξ ≤:= ξ (1 τ)DF(w)(S, T ), (cid:15) := 8 1w,τ( , ξ /8, 2N)e(NT+ Kk=1 Nk)Γ(x) with x (0, 1/8] and 0 < η(c ; x) η < 2. 1 − 1 This result shows that the Bennett-type bounds have a faster rate o(N 2 ) of convergence than − 1 O(N 2 ) of the Hoeﬀding-type results. Moreover, we can observe from the numerical simulation that − ∈ ∈ 1 the rate O(N η ) varies w.r.t. x for any c1 (0.0075, 0.4804) and es∈pecially, for any c1 (0.0075, 0.4434], the function η(c ; x) is monotonically decreasing in the interval x (0, 1/8], which implies that the rate 1 will become faster as the discrepancy between the expected risk and the empirical quantity becomes ∈ − 1 bigger when c1 (0.0075, 0.4434]. In contrast, the Hoeﬀding-type results have a consistent rate O(N 2 ) regardless of the discrepancy. Therefore, although the Bennett-type bounds (23) and (26) do not reﬂect how the parameters w and τ aﬀect the performance of the representative domain adaptation, they pro- vide a more detailed description of the asymptotical behavior of the learning process for representative domain adaptation. 5.4 Generalization Bounds Based on Rademacher Complexity Based on the Rademacher complexity, we obtain the following generalization bounds for represen- (cid:80) tative domain adaptation. Its proof is given in Appendix . F Theorem 5.4 Assume that is a function class consisting of bounded functions with the range [a, b]. ∈ · · · ∈ Then, given any τ [0, 1) and any w = (w , , w ) [0, 1]K with K w = 1, we have with − 1 K k=1 k probability at least 1 (cid:15), (cid:12) (cid:12) (cid:88) (cid:12) (cid:12) K sup Eτ f − E(T)f ≤(1 − τ(cid:115))DF(w)(S, T ) + 2(1 −(cid:118)(cid:117)τ) w R(k)(F) +(cid:32) 2τR(T)(F) (cid:33) (27) ∈F w (cid:117) k NT(cid:88) f (cid:116) k=1 − − − (b a)2 ln(4/(cid:15)) (b a)2 ln(2/(cid:15)) τ2 K (1 τ)2w2 + 2τ + + k , 2N 2 N N T T k k=1 R (w) (T) where DF (S, T ) is deﬁned in (21), is the empirical Rademacher complexity on the target Z R F ≤ ≤ NT Z domain (T), and (k)( ) (1 k K) are the Rademacher complexities on the source domains (Sk). R F (T) Note that in the derived bound (27), we adopt an empirical Rademacher complexity ( ) that is Z Z NT based on the data drawn from the target domain (T), because the distribution of (T) is unknown in the situation of domain adaptation. Similarly, the derived bound (27) coincides with the related 13 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Theorem

text: Under

text: the

text: notations

text: of

text: Theorem

text: set

text: w

text: N

text: K

text: N

text: k

text: K)

text: and

text: τ

text: N

text: /(N

text: K

text: N

text: Then,

text: given

text: any

text: ξ

text: τ)DF(w)(S,kT

text: wek

text: kany

text: N

text: N

text: N

text: N

text: T

text: T

text: k

text: T

text: K

text: such

text: that

text: K

text: (b

text: N

text: N

text: T

text: k

text: with

text: probability

text: at

text: least

text: N

text: F

text: ln

text: w,τ(

text: ξ

text: ln(

text: η

text: sup

text: Eτ

text: f

text: E(T)f

text: τ)DF(w)(S,

text: T

text: (b

text: a)

text: f∈F

text: w

text: Nk

text: N

text: F

text: where

text: ξ

text: ξ

text: τ)DF(w)(S,

text: T

text: ξ

text: Nk)Γ(x)

text: with

text: x

text: and

text: η(c

text: x)

text: η

text: This

text: result

text: shows

text: that

text: the

text: Bennett-type

text: bounds

text: have

text: a

text: faster

text: rate

text: o(N

text: of

text: convergence

text: than

text: O(N

text: of

text: the

text: Hoeﬀding-type

text: results.

text: Moreover,

text: we

text: can

text: observe

text: from

text: the

text: numerical

text: simulation

text: that

text: the

text: rate

text: O(N

text: η

text: varies

text: w.r.t.

text: x

text: for

text: any

text: and

text: es∈pecially,

text: for

text: any

text: the

text: function

text: η(c

text: x)

text: is

text: monotonically

text: decreasing

text: in

text: the

text: interval

text: x

text: which

text: implies

text: that

text: the

text: rate

text: will

text: become

text: faster

text: as

text: the

text: discrepancy

text: between

text: the

text: expected

text: risk

text: and

text: the

text: empirical

text: quantity

text: becomes

text: bigger

text: when

text: In

text: contrast,

text: the

text: Hoeﬀding-type

text: results

text: have

text: a

text: consistent

text: rate

text: O(N

text: regardless

text: of

text: the

text: discrepancy.

text: Therefore,

text: although

text: the

text: Bennett-type

text: bounds

text: and

text: do

text: not

text: reﬂect

text: how

text: the

text: parameters

text: w

text: and

text: τ

text: aﬀect

text: the

text: performance

text: of

text: the

text: representative

text: domain

text: adaptation,

text: they

text: pro-

text: vide

text: a

text: more

text: detailed

text: description

text: of

text: the

text: asymptotical

text: behavior

text: of

text: the

text: learning

text: process

text: for

text: representative

text: domain

text: adaptation.

text: Generalization

text: Bounds

text: Based

text: on

text: Rademacher

text: Complexity

text: Based

text: on

text: the

text: Rademacher

text: complexity,

text: we

text: obtain

text: the

text: following

text: generalization

text: bounds

text: for

text: represen-

text: tative

text: domain

text: adaptation.

text: Its

text: proof

text: is

text: given

text: in

text: Appendix

text: F

text: Theorem

text: Assume

text: that

text: is

text: a

text: function

text: class

text: consisting

text: of

text: bounded

text: functions

text: with

text: the

text: range

text: [a,

text: b].

text: Then,

text: given

text: any

text: τ

text: and

text: any

text: w

text: (w

text: w

text: with

text: K

text: w

text: we

text: have

text: with

text: K

text: k

text: probability

text: at

text: least

text: K

text: sup

text: Eτ

text: f

text: E(T)f

text: T

text: w

text: R(k)(F)

text: ∈F

text: w

text: k

text: f

text: (b

text: (b

text: τ2

text: K

text: 2τ

text: k

text: N

text: N

text: T

text: T

text: k

text: R

text: (w)

text: (T)

text: where

text: DF

text: (S,

text: T

text: is

text: deﬁned

text: in

text: is

text: the

text: empirical

text: Rademacher

text: complexity

text: on

text: the

text: target

text: Z

text: R

text: F

text: NT

text: Z

text: domain

text: (T),

text: and

text: (k)(

text: k

text: K)

text: are

text: the

text: Rademacher

text: complexities

text: on

text: the

text: source

text: domains

text: (Sk).

text: R

text: F

text: (T)

text: Note

text: that

text: in

text: the

text: derived

text: bound

text: we

text: adopt

text: an

text: empirical

text: Rademacher

text: complexity

text: that

text: is

text: Z

text: Z

text: NT

text: based

text: on

text: the

text: data

text: drawn

text: from

text: the

text: target

text: domain

text: (T),

text: because

text: the

text: distribution

text: of

text: (T)

text: is

text: unknown

text: in

text: the

text: situation

text: of

text: domain

text: adaptation.

text: Similarly,

text: the

text: derived

text: bound

text: coincides

text: with

text: the

text: related

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: classical result under the assumption of same distribution [see 12, Theorem 5], when any source domain {Z } Z of≤ (≤Sk) Kk=1 and the target domain (T) match, that is, DF(w)(S, T ) = DF(Sk, T ) = 0 holds for any 1 k K. Similar to the result (26), we adopt the technique mentioned in Zhang [31] again and replace the − term Γ(x) with cxη in the derived Bennett-type deviation inequality (41) (see Appendix ). Then, we obtain the Bennett-type generalization bounds based on the Rademacher complexity as follows: − Theorem 5.5 Under notations in Theorem 5.4, we have with probability at least 1 (cid:15), (cid:12) (cid:12) (cid:88) (cid:12) (cid:12) K sup Eτ f − E(T)f ≤(1 − τ)DF(w)(S,(cid:115)T ) + 2(1 − τ(cid:118)(cid:117)) w R((cid:32)k)(F) + 2τR(T)(F) (cid:33) (28) ∈F w (cid:117) k (cid:88) NT f  (cid:116)k=1  − − ln(4/(cid:15)) ln(2/(cid:15)) τ2 K (1 τ)2w2 + (b a) 2τ η + η + k , c N c (cid:8) N (cid:9) N (cid:0) (cid:1) 2 T 2 T k k=1 ≤ where c is taken from the interval (0.0075, 0.3863), (cid:15) := exp NΓ(x) and 0 < η c ; x η < 2 ∈ 2 2 (x (0, 1]) with η(c ; x) deﬁned in (25). 2 The results in the above theorem match with the Bennett-type bounds of the i.i.d. learning process {Z } shown in Theorem 4.3 of Zhang [31], when any source domain of (Sk) K and the target domain Z ≤ ≤ k=1 (T) match, that is, DF(w)(S, T ) = DF(S , T ) = 0 holds for any 1 k K. The proof of this theorem k is similar to that of Theorem 5.4, so we omit it. In addition, it is noteworthy that the Hoeﬀding-type results (20) and (27) exhibit a tradeoﬀ between ≤ ≤ the sample numbers N (1 k K) and N , which is associated with the choice of τ. Although such k T a tradeoﬀ has been discussed in some previous works [7, 2, 32], the next section will show a rigorous theoretical analysis of the tradeoﬀ in the situation of representative domain adaptation. Remark 5.1 We have shown that DF(S, T ) can be bounded by the summation of the discrepancy dis- D D tance disc ( (S), (T)) and the quantity Q(GT)(g∗(S), g∗(T)), which measure the diﬀerence between distri- (cid:96) D D butions (S) and (T) and the diﬀerence between labeling functions g∗(S) and g∗(T), respectively. Thus, the presented generalization results (20), (23), (24), (26), (27) and (28) can also be achieved by using H the discrepancy distance (or -divergency) and the quantity Q(GT)(g∗(S), g∗(T)) [see 2, 20]. In fact, one D D can directly replace DF(S, T ) with disc ( (S), (T))+Q(GT)(g∗(S), g∗(T)) and the derived results are similar (cid:96) to Theorem 9 of Mansour et al. [20]. Alternatively, under the condition of “λ-close” in classiﬁcation D D setting, one can also replace DF(S, T ) with dH(cid:52)H( (S), (T)) + cλ (c > 0), and the derived bounds are similar to the results given by Ben-David et al. [2]. Thus, our results include previous works as special cases. 6 Asymptotic Behavior for Representative Domain Adap- tation In this section, we discuss the asymptotical convergence and the rate of convergence of the learning process for representative domain adaptation. We also give a comparison with the related results under the same-distribution assumption and the existing results for domain adaptation. 14 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: classical

text: result

text: under

text: the

text: assumption

text: of

text: same

text: distribution

text: [see

text: Theorem

text: when

text: any

text: source

text: domain

text: {Z

text: Z

text: of≤

text: (≤Sk)

text: and

text: the

text: target

text: domain

text: (T)

text: match,

text: that

text: is,

text: DF(w)(S,

text: T

text: DF(Sk,

text: T

text: holds

text: for

text: any

text: k

text: K.

text: Similar

text: to

text: the

text: result

text: we

text: adopt

text: the

text: technique

text: mentioned

text: in

text: Zhang

text: again

text: and

text: replace

text: the

text: term

text: Γ(x)

text: with

text: cxη

text: in

text: the

text: derived

text: Bennett-type

text: deviation

text: inequality

text: (see

text: Appendix

text: Then,

text: we

text: obtain

text: the

text: Bennett-type

text: generalization

text: bounds

text: based

text: on

text: the

text: Rademacher

text: complexity

text: as

text: follows:

text: Theorem

text: Under

text: notations

text: in

text: Theorem

text: we

text: have

text: with

text: probability

text: at

text: least

text: K

text: sup

text: Eτ

text: f

text: E(T)f

text: w

text: ∈F

text: w

text: k

text: NT

text: f

text: τ2

text: K

text: (b

text: a)

text: 2τ

text: η

text: η

text: k

text: c

text: N

text: c

text: N

text: N

text: T

text: T

text: k

text: where

text: c

text: is

text: taken

text: from

text: the

text: interval

text: exp

text: NΓ(x)

text: and

text: η

text: c

text: x

text: η

text: (x

text: with

text: η(c

text: x)

text: deﬁned

text: in

text: The

text: results

text: in

text: the

text: above

text: theorem

text: match

text: with

text: the

text: Bennett-type

text: bounds

text: of

text: the

text: i.i.d.

text: learning

text: process

text: {Z

text: shown

text: in

text: Theorem

text: of

text: Zhang

text: when

text: any

text: source

text: domain

text: of

text: (Sk)

text: K

text: and

text: the

text: target

text: domain

text: Z

text: (T)

text: match,

text: that

text: is,

text: DF(w)(S,

text: T

text: DF(S

text: T

text: holds

text: for

text: any

text: k

text: K.

text: The

text: proof

text: of

text: this

text: theorem

text: k

text: is

text: similar

text: to

text: that

text: of

text: Theorem

text: so

text: we

text: omit

text: it.

text: In

text: addition,

text: it

text: is

text: noteworthy

text: that

text: the

text: Hoeﬀding-type

text: results

text: and

text: exhibit

text: a

text: tradeoﬀ

text: between

text: the

text: sample

text: numbers

text: N

text: k

text: K)

text: and

text: N

text: which

text: is

text: associated

text: with

text: the

text: choice

text: of

text: τ.

text: Although

text: such

text: k

text: T

text: a

text: tradeoﬀ

text: has

text: been

text: discussed

text: in

text: some

text: previous

text: works

text: the

text: next

text: section

text: will

text: show

text: a

text: rigorous

text: theoretical

text: analysis

text: of

text: the

text: tradeoﬀ

text: in

text: the

text: situation

text: of

text: representative

text: domain

text: adaptation.

text: Remark

text: We

text: have

text: shown

text: that

text: DF(S,

text: T

text: can

text: be

text: bounded

text: by

text: the

text: summation

text: of

text: the

text: discrepancy

text: dis-

text: D

text: D

text: tance

text: disc

text: (S),

text: (T))

text: and

text: the

text: quantity

text: Q(GT)(g∗(S),

text: g∗(T)),

text: which

text: measure

text: the

text: diﬀerence

text: between

text: distri-

text: D

text: D

text: butions

text: (S)

text: and

text: (T)

text: and

text: the

text: diﬀerence

text: between

text: labeling

text: functions

text: g∗(S)

text: and

text: g∗(T),

text: respectively.

text: Thus,

text: the

text: presented

text: generalization

text: results

text: and

text: can

text: also

text: be

text: achieved

text: by

text: using

text: H

text: the

text: discrepancy

text: distance

text: (or

text: -divergency)

text: and

text: the

text: quantity

text: Q(GT)(g∗(S),

text: g∗(T))

text: [see

text: In

text: fact,

text: one

text: D

text: D

text: can

text: directly

text: replace

text: DF(S,

text: T

text: with

text: disc

text: (S),

text: (T))+Q(GT)(g∗(S),

text: g∗(T))

text: and

text: the

text: derived

text: results

text: are

text: similar

text: to

text: Theorem

text: of

text: Mansour

text: et

text: al.

text: Alternatively,

text: under

text: the

text: condition

text: of

text: “λ-close”

text: in

text: classiﬁcation

text: D

text: D

text: setting,

text: one

text: can

text: also

text: replace

text: DF(S,

text: T

text: with

text: (S),

text: (T))

text: cλ

text: (c

text: and

text: the

text: derived

text: bounds

text: are

text: similar

text: to

text: the

text: results

text: given

text: by

text: Ben-David

text: et

text: al.

text: Thus,

text: our

text: results

text: include

text: previous

text: works

text: as

text: special

text: cases.

text: Asymptotic

text: Behavior

text: for

text: Representative

text: Domain

text: Adap-

text: tation

text: In

text: this

text: section,

text: we

text: discuss

text: the

text: asymptotical

text: convergence

text: and

text: the

text: rate

text: of

text: convergence

text: of

text: the

text: learning

text: process

text: for

text: representative

text: domain

text: adaptation.

text: We

text: also

text: give

text: a

text: comparison

text: with

text: the

text: related

text: results

text: under

text: the

text: same-distribution

text: assumption

text: and

text: the

text: existing

text: results

text: for

text: domain

text: adaptation.

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: This result implies that the fastest rate of convergence for the representative domain adaptation is − 1 up to O(N 2 ) which is the same as the classical result (22) of the learning process under the same- (w) distribution assumption, if the discrepancy term DF (S, T ) = 0. On the other hand, the choice of τ is not only one of essential factors to the rate of convergence { } but also is associated with the tradeoﬀ between the sample numbers N K and N . As sh(cid:80)own in N F (cid:48) k k=1 T (32), provided that the value of ln w,τ( , ξ /8, 2N) is ﬁxed, we can ﬁnd that setting τ = NT 1 NT+ Kk=1 Nk can result in the fastest rate of convergence, while it can also cause the relatively larger discrepancy be(cid:80)tween the empirical risk Eτwf and the expected risk E((cid:28)T)f, because th≤e sit≤uation of representative dom(cid:80)ain adaptation is set up under the condition that N N for any 1 k K, which implies that T k K N ≈ k=1 k 1. NT+ Kk=1 Nk From Theorem 5.2, such a setting of w and τ leads to the Bennett-type result (23) as well. It is noteworthy that the value τ = NT has been mentioned in the section of “Experimental Results” NT+NS in Blitzer et al. [7]. Moreover, a similar trade-oﬀ strategy was also discussed in Section 5 of Lazaric and Restelli [18]. It is in accordance with our theoretical analysis of τ and the following numerical experiments support the theoretical ﬁndings as well. 7 Numerical Experiments We have performed numerical experiments to verify the theoretical analysis of the asymptotic be- havior of the learning process for representative domain adaptation. Without loss of generality, we only consider the case of K = 2, i.e., there are two source domains and one target domain. The experiment data are generated in the following way. Z X × Y ⊂ R × R X For the target domain (T) = (T) (T) 100 , we consider (T) as a Gaussian distribution N(0, 1) and draw {x(T)}NT (N = 4000) from X (T) randomly and independently. Let β ∈ R100 be a n n=1 T ∈ R random vector of a Gaussian distribution N(1, 5), and let the random vector R 100 be a noise term ∼ ≤ ≤ with R N(0, 0.5). For any 1 n N , we randomly draw β and R from N(1, 5) and N(0, 0.01) T ∈ Y (T) respectively, and then generate y as follows: n (cid:104) (cid:105) y(T) = x(T), β + R. n n { } Z The derived (x(T), y(T)) NT (N = 4000) are the samples of the target domain (T) and will be used n n n=1 T (cid:48) as the test data. We randomly pick N = 100 samples from them to form the objective function (33) (cid:48)(cid:48) T and the rest N = 3900 are used for testing. T { } Z X S×imYilarly⊂, wRe ge×neRrate the sam≤ple s≤et (x(n1), yn(1)) Nn=11 (N1 = 2000) of the source domain (S1) = (1) (1) 100 : for any 1 n N , 1 (cid:104) (cid:105) y(1) = x(1), β + R, n n ∼ ∼ ∼ (1) where x N(0.2, 0.9), β N(1, 5) and R N(0, 0.5). n For the source domain Z(S2) = X (2) × Y(2≤) ⊂ ≤R100 × R, the samples {(x(n2), yn(2))}Nn=21 (N2 = 2000) are generated in the following way: for any 1 n N , 2 (cid:104) (cid:105) y(2) = x(2), β + R, n n ∼ − ∼ ∼ (2) where x N( 0.2, 1.2), β N(1, 5) and R N(0, 0.5). n In this experiment, we use the method of Least Square Regression [19] to minimize the empirical risk 16 ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: This

text: result

text: implies

text: that

text: the

text: fastest

text: rate

text: of

text: convergence

text: for

text: the

text: representative

text: domain

text: adaptation

text: is

text: up

text: to

text: O(N

text: which

text: is

text: the

text: same

text: as

text: the

text: classical

text: result

text: of

text: the

text: learning

text: process

text: under

text: the

text: same-

text: (w)

text: distribution

text: assumption,

text: if

text: the

text: discrepancy

text: term

text: DF

text: (S,

text: T

text: On

text: the

text: other

text: hand,

text: the

text: choice

text: of

text: τ

text: is

text: not

text: only

text: one

text: of

text: essential

text: factors

text: to

text: the

text: rate

text: of

text: convergence

text: but

text: also

text: is

text: associated

text: with

text: the

text: tradeoﬀ

text: between

text: the

text: sample

text: numbers

text: N

text: K

text: and

text: N

text: As

text: in

text: N

text: F

text: k

text: T

text: provided

text: that

text: the

text: value

text: of

text: ln

text: w,τ(

text: ξ

text: is

text: ﬁxed,

text: we

text: can

text: ﬁnd

text: that

text: setting

text: τ

text: NT

text: NT+

text: Nk

text: can

text: result

text: in

text: the

text: fastest

text: rate

text: of

text: convergence,

text: while

text: it

text: can

text: also

text: cause

text: the

text: relatively

text: larger

text: discrepancy

text: the

text: empirical

text: risk

text: Eτwf

text: and

text: the

text: expected

text: risk

text: because

text: th≤e

text: sit≤uation

text: of

text: representative

text: adaptation

text: is

text: set

text: up

text: under

text: the

text: condition

text: that

text: N

text: N

text: for

text: any

text: k

text: K,

text: which

text: implies

text: that

text: T

text: k

text: K

text: N

text: k

text: NT+

text: Nk

text: From

text: Theorem

text: such

text: a

text: setting

text: of

text: w

text: and

text: τ

text: leads

text: to

text: the

text: Bennett-type

text: result

text: as

text: well.

text: It

text: is

text: noteworthy

text: that

text: the

text: value

text: τ

text: NT

text: has

text: been

text: mentioned

text: in

text: the

text: section

text: of

text: “Experimental

text: Results”

text: NT+NS

text: in

text: Blitzer

text: et

text: al.

text: Moreover,

text: a

text: similar

text: trade-oﬀ

text: strategy

text: was

text: also

text: discussed

text: in

text: Section

text: of

text: Lazaric

text: and

text: Restelli

text: It

text: is

text: in

text: accordance

text: with

text: our

text: theoretical

text: analysis

text: of

text: τ

text: and

text: the

text: following

text: numerical

text: experiments

text: support

text: the

text: theoretical

text: ﬁndings

text: as

text: well.

text: Numerical

text: Experiments

text: We

text: have

text: performed

text: numerical

text: experiments

text: to

text: verify

text: the

text: theoretical

text: analysis

text: of

text: the

text: asymptotic

text: be-

text: havior

text: of

text: the

text: learning

text: process

text: for

text: representative

text: domain

text: adaptation.

text: Without

text: loss

text: of

text: generality,

text: we

text: only

text: consider

text: the

text: case

text: of

text: K

text: i.e.,

text: there

text: are

text: two

text: source

text: domains

text: and

text: one

text: target

text: domain.

text: The

text: experiment

text: data

text: are

text: generated

text: in

text: the

text: following

text: way.

text: Z

text: X

text: Y

text: R

text: R

text: X

text: For

text: the

text: target

text: domain

text: (T)

text: (T)

text: (T)

text: we

text: consider

text: (T)

text: as

text: a

text: Gaussian

text: distribution

text: and

text: draw

text: {x(T)}NT

text: (N

text: from

text: X

text: (T)

text: randomly

text: and

text: independently.

text: Let

text: β

text: be

text: a

text: n

text: T

text: R

text: random

text: vector

text: of

text: a

text: Gaussian

text: distribution

text: and

text: let

text: the

text: random

text: vector

text: R

text: be

text: a

text: noise

text: term

text: with

text: R

text: For

text: any

text: n

text: N

text: we

text: randomly

text: draw

text: β

text: and

text: R

text: from

text: and

text: T

text: Y

text: (T)

text: respectively,

text: and

text: then

text: generate

text: y

text: as

text: follows:

text: n

text: y(T)

text: x(T),

text: β

text: R.

text: n

text: n

text: Z

text: The

text: derived

text: (x(T),

text: y(T))

text: NT

text: (N

text: are

text: the

text: samples

text: of

text: the

text: target

text: domain

text: (T)

text: and

text: will

text: be

text: used

text: n

text: n

text: T

text: as

text: the

text: test

text: data.

text: We

text: randomly

text: pick

text: N

text: samples

text: from

text: them

text: to

text: form

text: the

text: objective

text: function

text: T

text: and

text: the

text: rest

text: N

text: are

text: used

text: for

text: testing.

text: T

text: Z

text: X

text: S×imYilarly⊂,

text: wRe

text: ge×neRrate

text: the

text: sam≤ple

text: s≤et

text: of

text: the

text: source

text: domain

text: for

text: any

text: n

text: N

text: β

text: R,

text: n

text: n

text: where

text: x

text: β

text: and

text: R

text: n

text: For

text: the

text: source

text: domain

text: X

text: R,

text: the

text: samples

text: are

text: generated

text: in

text: the

text: following

text: way:

text: for

text: any

text: n

text: N

text: β

text: R,

text: n

text: n

text: where

text: x

text: N(

text: β

text: and

text: R

text: n

text: In

text: this

text: experiment,

text: we

text: use

text: the

text: method

text: of

text: Least

text: Square

text: Regression

text: to

text: minimize

text: the

text: empirical

text: risk

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: (cid:88) (cid:88) (cid:48) ◦ τ NT (1 − τ)w N1 Eτw((cid:96) g) =N(cid:48) (cid:96)(g(x(nT)), y(cid:88)n(T)) + N (cid:96)(g(x(n1)), yn(1)) T n=1 1 n=1 − − (1 τ)(1 w) N2 + (cid:96)(g(x(2)), y(2)) (33) N n n 2 n=1 ∈ { } ∈ { } for diﬀerent combination coeﬃcients w 0.1, 0.25, 0.5, 0.8 and τ 0.025, 0.3, 0.5, 0.8 , respec- | − | (cid:29) (cid:48) tively. Then, we compute the discrepancy Eτ f E(T(cid:48)(cid:48))f for each N + N . Since N N , the initial w N 1 2 S T T N and N both equal to 200. Each test is repeated 100 times and the ﬁnal result is the average of 1 2 the 100 results. After each test, we increment both N and N by 200 until N = N = 2000. The 1 2 1 2 experimental results are shown in Fig. 1 and Fig. 2. τ=0.025 τ=0.3 τ=0.5 τ=0.8 2 w=0.1 |Eτf−E(T)f| w=0.25 w N’’ T w=0.5 w=0.8 1.5 0.5 0.5 0.5 1 0.5 0 0 0 0 0 2000 4000 0 2000 4000 0 2000 4000 0 2000 4000 N +N N +N N +N N +N 1 2 1 2 1 2 1 2 ∈ { } ∈ { } Figure 1: Given τ 0.025, 0.3, 0.5, 0.8 , the curves for diﬀerent w 0.1, 0.25, 0.5, 0.8 . w=0.1 w=0.25 w=0.5 w=0.8 2 2 2 2 τ=0.025 |Eτwf−E(NT’’)f| τ=0.3 T τ=0.5 1.5 τ=0.8 1.5 1.5 1.5 1 1 1 1 0.5 0.5 0.5 0.5 0 0 0 0 0 2000 4000 0 2000 4000 0 2000 4000 0 2000 4000 N +N N +N N +N N +N 1 2 1 2 1 2 1 2 ∈ { } ∈ { } Figure 2: Given w 0.1, 0.25, 0.5, 0.8 , the curves for diﬀerent τ 0.025, 0.3, 0.5, 0.8 . 17 ##LTFigure## ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: τ

text: NT

text: τ)w

text: g)

text: N

text: T

text: w)

text: N

text: n

text: n

text: for

text: diﬀerent

text: combination

text: coeﬃcients

text: w

text: and

text: τ

text: respec-

text: tively.

text: Then,

text: we

text: compute

text: the

text: discrepancy

text: Eτ

text: f

text: for

text: each

text: N

text: N

text: Since

text: N

text: N

text: the

text: initial

text: w

text: N

text: S

text: T

text: T

text: N

text: and

text: N

text: both

text: equal

text: to

text: Each

text: test

text: is

text: repeated

text: times

text: and

text: the

text: ﬁnal

text: result

text: is

text: the

text: average

text: of

text: the

text: results.

text: After

text: each

text: test,

text: we

text: increment

text: both

text: N

text: and

text: N

text: by

text: until

text: N

text: N

text: The

text: experimental

text: results

text: are

text: shown

text: in

text: Fig.

text: and

text: Fig.

text: |Eτf−E(T)f|

text: w

text: N’’

text: T

text: N

text: +N

text: N

text: +N

text: N

text: +N

text: N

text: +N

text: Figure

text: Given

text: τ

text: the

text: curves

text: for

text: diﬀerent

text: w

text: |Eτwf−E(NT’’)f|

text: T

text: N

text: +N

text: N

text: +N

text: N

text: +N

text: N

text: +N

text: Figure

text: Given

text: w

text: the

text: curves

text: for

text: diﬀerent

text: τ

text: ##LTFigure##

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: (cid:98) (S) (cid:88) where the expectation E f is deﬁned as (cid:98) (cid:98) K E(S)f := w E(Sk)f. k k=1 Let (cid:48) − − (w) ξ := ξ (1 τ)DF (S, T ), (72) ∧ (cid:16)(cid:12) (cid:12) (cid:12) (cid:98) (cid:98) (cid:98) (cid:98) (cid:12) and denote as the conjunction of two events. According to the triangle inequality, we have (cid:12) (cid:12)(cid:17) − − − τ(cid:12)(E(T)f (cid:98) E(T)f)(cid:98)+ (1 τ)(E(S)f (cid:98) E(S)f) (cid:98) (cid:12) NT w (cid:12) (cid:12) (cid:12)− τ(E(T(cid:98))f − E(cid:48)((cid:98)T)f) + (1 − τ)(E(S(cid:98))f − E(cid:48)((cid:98)S)(cid:12)f) NT w ≤ (cid:48) − − (cid:48) − (T) (T) (S) (S) τ(E f E f) + (1 τ)(E f E f) , (cid:18) NT NT (cid:19) (cid:18) w w (cid:19) (cid:48) and thus for any ξ > 0, (cid:98) (cid:98) (cid:98) (cid:98) (cid:98) (cid:98) (cid:98) (cid:98) (cid:110)1|τ(E(T)(cid:98)f−E(NTT)(cid:98)f)+(1−τ)(E(S)(cid:98)f−E(wS)(cid:98)f)|>ξ(cid:111)(cid:48) (cid:110) 1|τ(E(T(cid:98))f−E(cid:48)(NT(cid:98)T)f)+(1−τ)(E(S(cid:98))f−E(cid:48)(wS(cid:98))f)|<(cid:111)ξ2(cid:48) =≤1 |τ(E(T)(cid:98)f−E(NTT)(cid:98)f)+(1−τ)(E(S)f(cid:98)−E(wS)f(cid:98))|>ξ(cid:48) ∧ |τ(E(T)f−E(cid:48)(NTT)f)+(1−τ)(E(S)f−E(cid:48)(wS)f)|<ξ2(cid:48) 1|τ(E(cid:48)(NTT)f−E(NTT)f)+(1−τ)(E(cid:48)(wS)f−E(wS)f)|>ξ2(cid:48) . Then, taking the expec(cid:18)tation with respect to {Z(cid:48)Nk}K and(cid:19)Z(cid:48)NT gives 1 k=1 1 (cid:26) (cid:98) (cid:98) (cid:98) (cid:98) (cid:27) (cid:12) (cid:12) 1|τ(E(T(cid:12))f−E(NTT)f(cid:98))+(1−τ)(E(cid:98)(S)f−E(wS)f)|>ξ(cid:48) (cid:98) (cid:98) (cid:12) (cid:48) × P(cid:26)r(cid:12)(cid:12)(cid:48) τ(E(T(cid:98))f − E(cid:48)(N(cid:98)TT)f) + (1 − τ)(E(S(cid:98))f − E(cid:48)(w(cid:98)S)(cid:12)(cid:12)f) <(cid:27)ξ2 (cid:48) ≤ (cid:48) (cid:48) − − (cid:48) − ξ (T) (T) (S) (S) Pr τ(E f E f) + (1 τ)(E f E f) > . (73) NT NT w w 2 By Chebyshev(cid:26)’s inequality, since {Z(cid:48)Nk}K and Z(cid:48)NT are the sets(cid:27)of i.i.d. samples drawn from the {Z(cid:12) } 1 Zk=1 1 (cid:12) (cid:48) multiple sources (cid:12)(Sk) K (cid:98) and the(cid:98)target (T) resp(cid:98)ectively, w(cid:98)e(cid:12) have for any ξ > 0, k=1 (cid:48) (cid:48) (cid:40) − (cid:48) − − (cid:48) ≥ ξ (cid:41) Pr τ(E(cid:88)(T)f E (T)f) + (1 τ)(cid:88)(E(S)f E (S)f(cid:88)) (cid:98)NT (cid:98) w 2 (cid:98) (cid:98) − (cid:48) ≤Pr(cid:48) (cid:40)Nτ(cid:16) (cid:89)NT |E(cid:17)(T(cid:88))f − f(z(cid:48)(nT))| + K (1 Nτ)wk Nk |E(Sk)f − f(z(cid:48)(nk))| ≥ ξ2 T (cid:98) (cid:98) k n=1 k=1 n=1 (cid:48) K NT | − (cid:48) |  =Pr τ (cid:88)Nk (cid:16)E(cid:89)(T)f (cid:17) (cid:88)f(z (nT)) (cid:81)  k=1 n=1 (cid:98) (cid:98)  (cid:48) − K Nk | − (cid:48) | ≥ ξ N K N +(1 τ) w N N E(Sk)f f(z (k)) T k=1 k k T (cid:54) i n 2 k=1 i=k n=1 35 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: (S)

text: where

text: the

text: expectation

text: E

text: f

text: is

text: deﬁned

text: as

text: K

text: E(S)f

text: w

text: E(Sk)f.

text: k

text: Let

text: (w)

text: ξ

text: ξ

text: τ)DF

text: (S,

text: T

text: and

text: denote

text: as

text: the

text: conjunction

text: of

text: two

text: events.

text: According

text: to

text: the

text: triangle

text: inequality,

text: we

text: have

text: τ)(E(S)f

text: E(S)f)

text: NT

text: w

text: NT

text: w

text: (T)

text: (T)

text: (S)

text: (S)

text: τ(E

text: f

text: E

text: f)

text: τ)(E

text: f

text: E

text: f)

text: NT

text: NT

text: w

text: w

text: and

text: thus

text: for

text: any

text: ξ

text: Then,

text: taking

text: the

text: with

text: respect

text: to

text: gives

text: ξ

text: (T)

text: (T)

text: (S)

text: (S)

text: Pr

text: τ(E

text: f

text: E

text: f)

text: τ)(E

text: f

text: E

text: f)

text: NT

text: NT

text: w

text: w

text: By

text: inequality,

text: since

text: and

text: are

text: the

text: i.i.d.

text: samples

text: drawn

text: from

text: the

text: multiple

text: sources

text: K

text: and

text: (T)

text: have

text: for

text: any

text: ξ

text: ξ

text: Pr

text: E

text: (T)f)

text: E

text: w

text: K

text: Nτ)wk

text: Nk

text: |E(Sk)f

text: ξ2

text: T

text: k

text: K

text: NT

text: =Pr

text: τ

text: (nT))

text: K

text: Nk

text: ξ

text: N

text: K

text: N

text: τ)

text: w

text: N

text: N

text: E(Sk)f

text: f(z

text: (k))

text: T

text: k

text: k

text: T

text: i

text: n

text: i=k

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##