text: which satisﬁes the iterative relationship given in (10). By an induction argument, (22) can then be proved. S → S (cid:104) (cid:105) ∀ ∈ Let : H L2(H, ρ ) be the linear map deﬁned by ( ω)(x) = ω, x , ω, x H. We ρ X ρ H have the following error decomposition. Proposition 1 We have E E − E ≤ (cid:107)S − (cid:107) (cid:107)S − S (cid:107) E (cid:107)S − S (cid:107) [ (ω )] inf 2 µ fH 2 + 2 ν µ 2 + [ ω ν 2]. (23) J t ρ t ρ ρ t ρ t ρ J ρ t ρ t ρ H ∈ Proof For any ω H, we have (Rosasco and Villa, 2015) E − E (cid:107)S − (cid:107) (ω) inf (ω) = ω fH 2. ∈ ρ ρ ω H E − E (cid:107)S − (cid:107) Thus, (ω ) inf = ω fH 2, and t H ρ t ρ E (cid:107)S − (cid:107) E (cid:107)S − S S − (cid:107) [ ω fH 2] = [ ω ν + ν fH 2] J ρ t ρ J ρ t ρ t ρ t ρ E (cid:107)S − S (cid:107) (cid:107)S − (cid:107) E (cid:104)S − S S − (cid:105) = [ ω ν 2 + ν fH 2] + 2 ω ν , ν fH . J ρ t ρ t ρ ρ t ρ J ρ t ρ t ρ t ρ Using (22) in the above equality, we get, E (cid:107)S − (cid:107) E (cid:107)S − S (cid:107) (cid:107)S − (cid:107) [ ω fH 2] = [ ω ν 2 + ν fH 2]. J ρ t ρ J ρ t ρ t ρ ρ t ρ The proof is ﬁnished by considering, (cid:107)S − (cid:107) (cid:107)S − S S − (cid:107) ≤ (cid:107)S − S (cid:107) (cid:107)S − S (cid:107) ν fH 2 = ν µ + µ fH 2 2 ν µ 2 + 2 µ fH 2. ρ t ρ ρ t ρ t ρ t ρ ρ t ρ t ρ ρ t ρ ρ There are three terms in the upper bound of the error decomposition (23). We refer to the (cid:107)S − (cid:107) (cid:107)S − S (cid:107) deterministic term µ fH 2 as the bias, the term ν µ 2 depending on z as the Eρ t(cid:107)S −ρ S (cid:107) ρ t ρ t ρ sample variance, and [ ω ν 2] as the computational variance. The bias term, which J ρ t ρ t ρ is deterministic, has been well studied in the literature, see e.g., (Yao et al., 2007) and also (Rosasco and Villa, 2015). The main novelties of this paper are the estimate of the sample and computational variances and the diﬃcult part is the estimate of the computational variances. The proof of these results is quite lengthy and makes use of some ideas from (Yao et al., 2007; Smale and Zhou, 2007; Bauer et al., 2007; Ying and Pontil, 2008; Tarres and Yao, 2014; Rudi et al., 2015). These three error terms will be estimated in Sections and . The bounds in Theorems 1 and 3 thus follow plugging these estimations in the error decomposition, see Section for more details. The proof for Theorem 2 is similar, see Section for the details. 4. Preliminary Analysis In this section, we introduce some notation and preliminary lemmas that are necessary to our proofs. (cid:81) 4.1 Notation ∈ N − ∈ − We ﬁrst introduce some notations. For t , ΠT (L) = T (I η L) for t [T 1] H → Ht+1 H k=t+1 k and ΠT (L) = I, for any operator L : , where is a Hilbert space and I de- T+1 H E notes the identity operator on . [ξ] denotes the expectation of a random variable ξ. For → (cid:107) (cid:107) a given boun(cid:81)ded operator L(cid:80): L2(H, ρ ) H, L denotes the operator norm of L, i.e., (cid:107) (cid:107) (cid:107) (cid:107) X L = sup ∈ (cid:107) (cid:107) Lf . We will use the conventional notations on summation and f L2(H,ρX), f ρ=1 H production: t = 1 and t = 0. i=t+1 i=t+1 14

text: which

text: satisﬁes

text: the

text: iterative

text: relationship

text: given

text: in

text: By

text: an

text: induction

text: argument,

text: can

text: then

text: be

text: proved.

text: S

text: S

text: Let

text: H

text: ρ

text: be

text: the

text: linear

text: map

text: deﬁned

text: by

text: ω)(x)

text: ω,

text: x

text: ω,

text: x

text: H.

text: We

text: ρ

text: X

text: ρ

text: H

text: have

text: the

text: following

text: error

text: decomposition.

text: Proposition

text: We

text: have

text: E

text: E

text: E

text: S

text: E

text: S

text: (ω

text: inf

text: µ

text: fH

text: ν

text: µ

text: ω

text: ν

text: J

text: t

text: ρ

text: t

text: ρ

text: ρ

text: t

text: ρ

text: t

text: ρ

text: J

text: ρ

text: t

text: ρ

text: t

text: ρ

text: H

text: Proof

text: For

text: any

text: ω

text: H,

text: we

text: have

text: (Rosasco

text: and

text: Villa,

text: E

text: E

text: (ω)

text: inf

text: (ω)

text: ω

text: fH

text: ρ

text: ρ

text: ω

text: H

text: E

text: E

text: Thus,

text: (ω

text: inf

text: ω

text: fH

text: and

text: t

text: H

text: ρ

text: t

text: ρ

text: E

text: E

text: S

text: S

text: ω

text: fH

text: ω

text: ν

text: ν

text: fH

text: J

text: ρ

text: t

text: ρ

text: J

text: ρ

text: t

text: ρ

text: t

text: ρ

text: t

text: ρ

text: E

text: S

text: E

text: S

text: S

text: ω

text: ν

text: ν

text: fH

text: ω

text: ν

text: ν

text: fH

text: J

text: ρ

text: t

text: ρ

text: t

text: ρ

text: ρ

text: t

text: ρ

text: J

text: ρ

text: t

text: ρ

text: t

text: ρ

text: t

text: ρ

text: Using

text: in

text: the

text: above

text: equality,

text: we

text: get,

text: E

text: E

text: S

text: ω

text: fH

text: ω

text: ν

text: ν

text: fH

text: J

text: ρ

text: t

text: ρ

text: J

text: ρ

text: t

text: ρ

text: t

text: ρ

text: ρ

text: t

text: ρ

text: The

text: proof

text: is

text: ﬁnished

text: by

text: considering,

text: S

text: S

text: S

text: S

text: ν

text: fH

text: ν

text: µ

text: µ

text: fH

text: ν

text: µ

text: µ

text: fH

text: ρ

text: t

text: ρ

text: ρ

text: t

text: ρ

text: t

text: ρ

text: t

text: ρ

text: ρ

text: t

text: ρ

text: t

text: ρ

text: ρ

text: t

text: ρ

text: ρ

text: There

text: are

text: three

text: terms

text: in

text: the

text: upper

text: bound

text: of

text: the

text: error

text: decomposition

text: We

text: refer

text: to

text: the

text: S

text: deterministic

text: term

text: µ

text: fH

text: as

text: the

text: bias,

text: the

text: term

text: ν

text: µ

text: depending

text: on

text: z

text: as

text: the

text: Eρ

text: −ρ

text: S

text: ρ

text: t

text: ρ

text: t

text: ρ

text: sample

text: variance,

text: and

text: ω

text: ν

text: as

text: the

text: computational

text: variance.

text: The

text: bias

text: term,

text: which

text: J

text: ρ

text: t

text: ρ

text: t

text: ρ

text: is

text: deterministic,

text: has

text: been

text: well

text: studied

text: in

text: the

text: literature,

text: see

text: e.g.,

text: (Yao

text: et

text: al.,

text: and

text: also

text: (Rosasco

text: and

text: Villa,

text: The

text: main

text: novelties

text: of

text: this

text: paper

text: are

text: the

text: estimate

text: of

text: the

text: sample

text: and

text: computational

text: variances

text: and

text: the

text: diﬃcult

text: part

text: is

text: the

text: estimate

text: of

text: the

text: computational

text: variances.

text: The

text: proof

text: of

text: these

text: results

text: is

text: quite

text: lengthy

text: and

text: makes

text: use

text: of

text: some

text: ideas

text: from

text: (Yao

text: et

text: al.,

text: Smale

text: and

text: Zhou,

text: Bauer

text: et

text: al.,

text: Ying

text: and

text: Pontil,

text: Tarres

text: and

text: Yao,

text: Rudi

text: et

text: al.,

text: These

text: three

text: error

text: terms

text: will

text: be

text: estimated

text: in

text: Sections

text: and

text: The

text: bounds

text: in

text: Theorems

text: and

text: thus

text: follow

text: plugging

text: these

text: estimations

text: in

text: the

text: error

text: decomposition,

text: see

text: Section

text: for

text: more

text: details.

text: The

text: proof

text: for

text: Theorem

text: is

text: similar,

text: see

text: Section

text: for

text: the

text: details.

text: Preliminary

text: Analysis

text: In

text: this

text: section,

text: we

text: introduce

text: some

text: notation

text: and

text: preliminary

text: lemmas

text: that

text: are

text: necessary

text: to

text: our

text: proofs.

text: Notation

text: N

text: We

text: ﬁrst

text: introduce

text: some

text: notations.

text: For

text: t

text: ΠT

text: (L)

text: T

text: (I

text: η

text: L)

text: for

text: t

text: [T

text: H

text: H

text: k

text: and

text: ΠT

text: (L)

text: I,

text: for

text: any

text: operator

text: L

text: where

text: is

text: a

text: Hilbert

text: space

text: and

text: I

text: de-

text: H

text: E

text: notes

text: the

text: identity

text: operator

text: on

text: [ξ]

text: denotes

text: the

text: expectation

text: of

text: a

text: random

text: variable

text: ξ.

text: For

text: a

text: given

text: operator

text: ρ

text: H,

text: L

text: denotes

text: the

text: operator

text: norm

text: of

text: L,

text: i.e.,

text: X

text: L

text: sup

text: Lf

text: We

text: will

text: use

text: the

text: conventional

text: notations

text: on

text: summation

text: and

text: f

text: f

text: H

text: production:

text: t

text: and

text: t


text: 4.3 Basic Estimates Finally, we introduce the following three basic estimates, whose proofs can be found in Appendix . ∈ ∈ N Lemma 12 Let θ [0, 1[, and t . Then(cid:88) − − t1 θ ≤ t − ≤ t1 θ k θ − . 2 1 θ k=1 ∈ R ∈ N(cid:88) Lemma 13 Let θ and t . Then t − ≤ − k θ tmax(1 θ,0)(1 + log t). k=1 ∈ R ∈ N ≥ Lemma 14 Let q and(cid:88)t with t 3. Then − t 1 1 − ≤ − − k q 2t min(q,1)(1 + log t). t k k=1 In the next sections, we begin proving the main results. The proofs are quite lengthy and they are divided into several steps. For the ease of readability, we list some of the notations and deﬁnitions in Appendix . We also remark that we are particularly interested in developing error − bounds in terms of the stepsize η (= η t θ), the number of iterations t or T , the ‘regularization’ t 1 parameter λ > 0, the sample size m, the minibatch size b, and the failing proﬁtability δ. Other (cid:107)T (cid:107) (cid:107) (cid:107) parameters such as κ2, , M, v, R, c and fH ∞ can be always viewed as some constants, ρ γ which are less important in our error bounds. 5. Estimating Bias and Sample Variance In this section, we estimate the bias and the sample variance. 5.1 Bias (cid:107)S − (cid:107) In this subsection, we develop upper bounds for the bias, i.e., µ fH 2. Towards this ρ t ρ end, we introduce the following lemma, whose proof borrows idea from (Ying and Pontil, 2008; Tarres and Yao, 2014). Lemma 15 Let L be a compact, positive operator on a separable Hilbert space H. Assume that (cid:107) (cid:107) ≤ ∈ N (cid:32) ≤(cid:33) − η L 1. Then for t and any non-negative integer k t 1, 1 (cid:80) ζ (cid:107) (cid:107) ≤ ζ Πt (L)Lζ . (30) k+1 e t η j=k+1 j { } Proof Let σ be the sequence of eigenvalues (cid:89)of L. We have i t (cid:107) (cid:107) − Πt (L)Lζ = sup (1 η σ )σζ. k+1 l i i i l=k+1 Using the basic inequality ≤ ≥ − 1 + x ex for all x 1, (31) 16 ##LTLine## ##LTLine## ##LTLine## ##LTLine##

label: section

text: Basic

text: Estimates

text: Finally,

label: paragraph

text: we

text: introduce

text: the

text: following

text: three

text: basic

text: estimates,

text: whose

text: proofs

text: can

text: be

text: found

text: in

text: Appendix

text: N

text: Lemma

text: Let

text: θ

text: and

text: t

text: θ

text: t

text: θ

text: k

text: θ

text: θ

text: R

text: Lemma

text: Let

text: θ

text: and

text: t

text: Then

text: t

text: k

text: θ

text: log

text: t).

text: R

text: N

text: Lemma

text: Let

text: q

text: with

text: t

text: Then

text: t

text: k

text: q

text: log

text: t).

text: t

text: k

text: In

text: the

text: next

text: sections,

text: we

text: begin

text: proving

text: the

text: main

text: results.

text: The

text: proofs

text: are

text: quite

text: lengthy

text: and

text: they

text: are

text: divided

text: into

text: several

text: steps.

text: For

text: the

text: ease

text: of

text: readability,

text: we

text: list

text: some

text: of

text: the

text: notations

text: and

text: deﬁnitions

text: in

text: Appendix

text: We

text: also

text: remark

text: that

text: we

text: are

text: particularly

text: interested

text: in

text: developing

text: error

text: bounds

text: in

text: terms

text: of

text: the

text: stepsize

text: η

text: η

text: t

text: θ),

text: the

text: number

text: of

text: iterations

text: t

text: or

text: T

text: the

text: ‘regularization’

text: t

text: parameter

text: λ

text: the

text: sample

text: size

text: m,

text: the

text: minibatch

text: size

text: b,

text: and

text: the

text: failing

text: proﬁtability

text: δ.

text: Other

text: parameters

text: such

text: as

text: M,

text: v,

text: R,

text: c

text: and

text: fH

text: can

text: be

text: always

text: viewed

text: as

text: some

text: constants,

text: ρ

text: γ

text: which

text: are

text: less

text: important

text: in

text: our

text: error

text: bounds.

text: Estimating

text: Bias

text: and

text: Sample

text: Variance

text: In

text: this

text: section,

text: we

text: estimate

text: the

text: bias

text: and

text: the

text: sample

text: variance.

text: Bias

text: In

text: this

text: subsection,

text: we

text: develop

text: upper

text: bounds

text: for

text: the

text: bias,

text: i.e.,

text: µ

text: fH

text: Towards

text: this

text: ρ

text: t

text: ρ

text: end,

text: we

text: introduce

text: the

text: following

text: lemma,

text: whose

text: proof

text: borrows

text: idea

text: from

text: (Ying

text: and

text: Pontil,

text: Tarres

text: and

text: Yao,

text: Lemma

text: Let

text: L

text: be

text: a

text: compact,

text: positive

text: operator

text: on

text: a

text: separable

text: Hilbert

text: space

text: H.

text: Assume

text: that

text: N

text: η

text: L

text: Then

text: for

text: t

text: and

text: any

text: non-negative

text: integer

text: k

text: t

text: ζ

text: ζ

text: Πt

text: (L)Lζ

text: e

text: t

text: η

text: j

text: Proof

text: Let

text: σ

text: be

text: the

text: sequence

text: of

text: eigenvalues

text: L.

text: We

text: have

text: i

text: t

text: Πt

text: (L)Lζ

text: sup

text: η

text: σ

text: )σζ.

text: l

text: i

text: i

text: i

text: Using

text: the

text: basic

text: inequality

text: x

text: ex

text: for

text: all

text: x

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: rates, for both the attainable and non-attainable cases, and consider more general step-size choices. The extension from the attainable case to the non-attainable case is non-trivial. As will be seen from the proof, in contrast to the attainable case, a diﬀerent and reﬁned estimation is needed for the non-attainable case. Interestingly, as a byproduct of this paper, we also derived optimal rates for the batch gradient descent methods in the non-attainable case. To the best of our knowledge, such a result may be the ﬁrst kind for batch gradient methods, without requiring any extra unlabeled data as that in (Caponnetto and Yao, 2010). Finally, we also add novel convergence results for the iterates showing that they converge to the minimal norm solution of the expected risk with optimal rates. The rest of this paper is organized as follows. Section introduces the learning setting and the SGM algorithm. Main results with discussions and proof sketches are presented in Section . Preliminary lemmas necessary for the proofs will be given in Section while detailed proofs will be conducted in Sections to . Finally, simple numerical simulations are given in Section to complement our theoretical results. ∈ R ∨ N Notation For any a, b , a b denotes the maximum of a and b. is the set of all positive ∈ N { · · · } { } integers. For any T , [T ] denotes the set 1, , T . For any two positive sequences a ∈ { } (cid:46) ∈ t t [T] and b ∈ , the notation a b for all t [T ] means that there exists a positive constant ≥ t t [T] t t ≤ ∈ C 0 such that C is independent of t and that a Cb for all t [T ]. t t 2. Learning with SGM We begin by introducing the learning setting we consider, and then describe the SGM learning algorithm. Following (Rosasco and Villa, 2015), the formulation we consider is close to the setting of functional regression, and covers the reproducing kernel Hilbert space (RKHS) setting as a special case, see Appendix . In particular, it reduces to standard linear regression for ﬁnite dimensions. 2.1 Learning Problems (cid:104)· ·(cid:105) Let H be a separable Hilbert space, with inner product and induced norm denoted by , (cid:107) · (cid:107) ⊆ ⊆ R H and , respectively. Let the input space X H and the output space Y . Let ρ be an H × · unknown probability measure on Z = X Y, ρ ( ) the induced marginal measure on X, and ·| X ∈ ρ( x) the conditional probability measure on Y with respect to x X and ρ. (cid:90) Considering the square loss function, the problem under study is the minimization of the risk, E E (cid:104) (cid:105) − inf (ω), (ω) = ( ω, x y)2dρ(x, y), (1) ∈ × H ω H X Y { } ∈ N when the measure ρ is known only through a sample z = z = (x , y ) m of size m , i i i i=1 independently and identically distributed (i.i.d.) according to ρ. In the following, we measure ∈ the quality of an approximate solution ωˆ H (an estimator) considering the excess risk, i.e., E − E (ωˆ) inf (ω). (2) ∈ ω H ∈ ∞ Throughout this paper, we assume that there exists a constant κ [1, [, such that (cid:104) (cid:48)(cid:105) ≤ ∀ (cid:48) ∈ x, x κ2, x, x X. (3) H 2.2 Stochastic Gradient Method 3

text: rates,

text: for

text: both

text: the

text: attainable

text: and

text: non-attainable

text: cases,

text: and

text: consider

text: more

text: general

text: step-size

text: choices.

text: The

text: extension

text: from

text: the

text: attainable

text: case

text: to

text: the

text: non-attainable

text: case

text: is

text: non-trivial.

text: As

text: will

text: be

text: seen

text: from

text: the

text: proof,

text: in

text: contrast

text: to

text: the

text: attainable

text: case,

text: a

text: diﬀerent

text: and

text: reﬁned

text: estimation

text: is

text: needed

text: for

text: the

text: non-attainable

text: case.

text: Interestingly,

text: as

text: a

text: byproduct

text: of

text: this

text: paper,

text: we

text: also

text: derived

text: optimal

text: rates

text: for

text: the

text: batch

text: gradient

text: descent

text: methods

text: in

text: the

text: non-attainable

text: case.

text: To

text: the

text: best

text: of

text: our

text: knowledge,

text: such

text: a

text: result

text: may

text: be

text: the

text: ﬁrst

text: kind

text: for

text: batch

text: gradient

text: methods,

text: without

text: requiring

text: any

text: extra

text: unlabeled

text: data

text: as

text: that

text: in

text: (Caponnetto

text: and

text: Yao,

text: Finally,

text: we

text: also

text: add

text: novel

text: convergence

text: results

text: for

text: the

text: iterates

text: showing

text: that

text: they

text: converge

text: to

text: the

text: minimal

text: norm

text: solution

text: of

text: the

text: expected

text: risk

text: with

text: optimal

text: rates.

text: The

text: rest

text: of

text: this

text: paper

text: is

text: organized

text: as

text: follows.

text: Section

text: introduces

text: the

text: learning

text: setting

text: and

text: the

text: SGM

text: algorithm.

text: Main

text: results

text: with

text: discussions

text: and

text: proof

text: sketches

text: are

text: presented

text: in

text: Section

text: Preliminary

text: lemmas

text: necessary

text: for

text: the

text: proofs

text: will

text: be

text: given

text: in

text: Section

text: while

text: detailed

text: proofs

text: will

text: be

text: conducted

text: in

text: Sections

text: to

text: Finally,

text: simple

text: numerical

text: simulations

text: are

text: given

text: in

text: Section

text: to

text: complement

text: our

text: theoretical

text: results.

text: R

text: N

text: Notation

text: For

text: any

text: a,

text: b

text: a

text: b

text: denotes

text: the

text: maximum

text: of

text: a

text: and

text: b.

text: is

text: the

text: set

text: of

text: all

text: positive

text: N

text: integers.

text: For

text: any

text: T

text: [T

text: denotes

text: the

text: set

text: T

text: For

text: any

text: two

text: positive

text: sequences

text: a

text: t

text: t

text: [T]

text: and

text: b

text: the

text: notation

text: a

text: b

text: for

text: all

text: t

text: [T

text: means

text: that

text: there

text: exists

text: a

text: positive

text: constant

text: t

text: t

text: [T]

text: t

text: t

text: C

text: such

text: that

text: C

text: is

text: independent

text: of

text: t

text: and

text: that

text: a

text: Cb

text: for

text: all

text: t

text: [T

text: t

text: t

text: Learning

text: with

text: SGM

text: We

text: begin

text: by

text: introducing

text: the

text: learning

text: setting

text: we

text: consider,

text: and

text: then

text: describe

text: the

text: SGM

text: learning

text: algorithm.

text: Following

text: (Rosasco

text: and

text: Villa,

text: the

text: formulation

text: we

text: consider

text: is

text: close

text: to

text: the

text: setting

text: of

text: functional

text: regression,

text: and

text: covers

text: the

text: reproducing

text: kernel

text: Hilbert

text: space

text: (RKHS)

text: setting

text: as

text: a

text: special

text: case,

text: see

text: Appendix

text: In

text: particular,

text: it

text: reduces

text: to

text: standard

text: linear

text: regression

text: for

text: ﬁnite

text: dimensions.

text: Learning

text: Problems

text: Let

text: H

text: be

text: a

text: separable

text: Hilbert

text: space,

text: with

text: inner

text: product

text: and

text: induced

text: norm

text: denoted

text: by

text: R

text: H

text: and

text: respectively.

text: Let

text: the

text: input

text: space

text: X

text: H

text: and

text: the

text: output

text: space

text: Y

text: Let

text: ρ

text: be

text: an

text: H

text: unknown

text: probability

text: measure

text: on

text: Z

text: X

text: Y,

text: ρ

text: the

text: induced

text: marginal

text: measure

text: on

text: X,

text: and

text: X

text: ρ(

text: x)

text: the

text: conditional

text: probability

text: measure

text: on

text: Y

text: with

text: respect

text: to

text: x

text: X

text: and

text: ρ.

text: Considering

text: the

text: square

text: loss

text: function,

text: the

text: problem

text: under

text: study

text: is

text: the

text: minimization

text: of

text: the

text: risk,

text: E

text: E

text: inf

text: (ω),

text: (ω)

text: ω,

text: x

text: y),

text: H

text: ω

text: H

text: X

text: Y

text: N

text: when

text: the

text: measure

text: ρ

text: is

text: known

text: only

text: through

text: a

text: sample

text: z

text: z

text: (x

text: y

text: m

text: of

text: size

text: m

text: i

text: i

text: i

text: independently

text: and

text: identically

text: distributed

text: (i.i.d.)

text: according

text: to

text: ρ.

text: In

text: the

text: following,

text: we

text: measure

text: the

text: quality

text: of

text: an

text: approximate

text: solution

text: ωˆ

text: H

text: (an

text: estimator)

text: considering

text: the

text: excess

text: risk,

text: i.e.,

text: E

text: E

text: (ωˆ)

text: inf

text: (ω).

text: ω

text: H

text: Throughout

text: this

text: paper,

text: we

text: assume

text: that

text: there

text: exists

text: a

text: constant

text: κ

text: such

text: that

text: x,

text: x

text: x,

text: x

text: X.

text: H

text: Stochastic

text: Gradient

text: Method


text: (cid:18) ∈ (cid:19) 2) If ζ < 1/2, and (41) holds for all t [T ], − √ (cid:32)(cid:107)S − S (cid:107) ≤ 8λη (cid:32)t1 θ (cid:112) (cid:33) (cid:32) (cid:114)3T (cid:33) (cid:33) (cid:16)ν µ (cid:17)−1 + 4 log t + 4 + 2η κ2 log ρ t+1 ρ t+1 ρ 1 1 θ √ δ1 √ − × (cid:107) (cid:107) κ√ √2 vc κ η t1 θ √4κR 1 2 3 fH ∞ + 3 M + κR + γ + − 1 + 1 − . m λ mλγ 1 θ m mλ (η1t1 θ)ζ (51) Proof By Propositi(cid:88)on 3, we have (48(cid:88)) or (49). Note th(cid:88)at (cid:80) (cid:80) − − − − − t 1 η t 1 k θ ≤ t 1 k θ k = − − − . t η t i θ (t k)t θ k=1 i=k+1 i k=1 i=k+1 k=1 Applying Lemma 14, we get (cid:88) (cid:80) − t 1 η ≤ k 2 + 2 log t, t η k=1 i=k+1 i and by Lemma 12, (cid:88) (cid:88) − − − t 1 t 1 − ≤ 2η t1 θ η = η k θ 1− . k 1 1 θ k=1 k=1 (cid:18) (cid:19) Introducing the last two estimates into (48) and (49), one can get (50) and that − √ (cid:107)S ν − (cid:16)S µ (cid:107) ≤ 8λη−1t1 θ +(cid:17) (cid:32)4 log t + 4 +(cid:112) 2η κ2(cid:33) (cid:0) (cid:1)  ρ t+1 ρ t+1 ρ 1  1 θ  √ × (cid:107) (cid:107) √ κ√ √2 vc 4κ2R η t1−√θ 12−ζ 3T 2 3 fH ∞ + 3 M + κR + γ + − 1 log  (cid:88) m λ mλγ (cid:88) (1 θ)m λ δ1    − (cid:16)(cid:80) (cid:17) (cid:80) − (cid:16)(cid:80) (cid:17) (cid:0)(cid:80)√ (cid:1)  √2κR 3T t 1 2η t 1 η 2κ2η k k t + log + 4λ + . mλ δ1 k=1 ki=1 ηi ζ ti=k+1 ηi k=1 ki=1 ηi ζ ti=1 ηi ζ To prove (51), it remains to estimate the last term of the above. Again, using Lemmas 12, 13 and 14, we get (cid:88) (cid:88) (cid:16) (cid:17) (cid:16) (cid:17) − (cid:80) (cid:80) − (cid:80) −(cid:80) t 1 η 1 t 1 k θ k = k=1(cid:88) ki=1 ηi ζ ti=k+1 ηi η1ζ k=1(cid:88) ki=1 i−θ ζ ti=k+1 i−θ − − − − − ≤ 1 t 1 k θ 2ζ t 1 k (θ+ζ(1 θ)) − − − = tθ − ηζ (k1 θ/2)ζ(t k)t θ ηζ t k 1 k=1 1 k=1 ≤ 2ζ − − ≤ 4(1 + log t) tθ2t (θ+ζ(1 θ))(1 + log t) − , ηζ (η1t1 θ)ζ 1 23 ##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: If

text: ζ

text: and

text: holds

text: for

text: all

text: t

text: [T

text: S

text: 8λη

text: θ

text: µ

text: log

text: t

text: 2η

text: κ2

text: log

text: ρ

text: ρ

text: ρ

text: θ

text: δ1

text: κ√

text: √2

text: vc

text: κ

text: η

text: θ

text: √4κR

text: fH

text: M

text: κR

text: γ

text: m

text: λ

text: mλγ

text: θ

text: m

text: mλ

text: θ)ζ

text: Proof

text: By

text: we

text: have

text: or

text: Note

text: t

text: η

text: t

text: k

text: θ

text: t

text: k

text: θ

text: k

text: t

text: η

text: t

text: i

text: θ

text: (t

text: k)t

text: θ

text: i

text: Applying

text: Lemma

text: we

text: get

text: t

text: η

text: k

text: log

text: t,

text: t

text: η

text: i

text: and

text: by

text: Lemma

text: t

text: t

text: 2η

text: θ

text: η

text: η

text: k

text: θ

text: 1−

text: k

text: θ

text: Introducing

text: the

text: last

text: two

text: estimates

text: into

text: and

text: one

text: can

text: get

text: and

text: that

text: ν

text: µ

text: θ

text: log

text: t

text: 2η

text: ρ

text: ρ

text: ρ

text: θ

text: κ√

text: √2

text: vc

text: η

text: t1−√θ

text: 12−ζ

text: fH

text: M

text: κR

text: γ

text: log

text: m

text: λ

text: mλγ

text: θ)m

text: λ

text: δ1

text: √2κR

text: t

text: 2η

text: t

text: η

text: 2κ2η

text: k

text: k

text: t

text: log

text: 4λ

text: mλ

text: δ1

text: ηi

text: ζ

text: ηi

text: ηi

text: ζ

text: ηi

text: ζ

text: To

text: prove

text: it

text: remains

text: to

text: estimate

text: the

text: last

text: term

text: of

text: the

text: above.

text: Again,

text: using

text: Lemmas

text: and

text: we

text: get

text: t

text: η

text: t

text: k

text: θ

text: k

text: ηi

text: ζ

text: ηi

text: η1ζ

text: i−θ

text: ζ

text: i−θ

text: t

text: k

text: θ

text: 2ζ

text: t

text: k

text: θ))

text: tθ

text: ηζ

text: k)t

text: θ

text: ηζ

text: t

text: k

text: 2ζ

text: log

text: t)

text: log

text: t)

text: ηζ

text: θ)ζ

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: Using (47), we can relax the above as (cid:107)Tρ12 Πtk+1(Tx)(cid:107) ≤ 2(cid:107)(Tx + λI)12 Πtk+1(Tx)(cid:107), which leads to (cid:107)Tρ12 Πtk+1(Tx)(cid:107)2 ≤ 4(cid:107)(Tx + λI)12 Πtk+1(Tx)(cid:107)2. Since (cid:107) T T (cid:107) (cid:107) T T T (cid:107) ( x + λI)12 Πtk+1( x) 2 = ( x + λI)Πtk+1( x)Πtk+1( x) ≤ (cid:107)T T T (cid:107) Πt ( )Πt ( ) + λ x k+1 x k+1 x (cid:107)T 1 T (cid:107) = 2 Πt ( ) 2 + λ, x k+1 x ≤ (cid:107)T (cid:107) ≤ T ≤ and with ηtκ2 1, x tr( x) κ2, by L(cid:80)emma 15, (cid:80) (cid:107)T 1 T (cid:107) ≤ 1 ≤ 1 2 Πt ( ) 2 , x k+1 x 2e t η 4 t η i=k+1 i i=k+1 i we thus derive the desired result. The proof is complete. 6.4 Deriving Error Bounds E (cid:107)S − With Lemmas 20–26, we are ready to estimate the computational variance , ω S (cid:107) J ρ t+1 ν 2, as follows. ρ t+1 ρ ≤ Proposition 5 Under Assum∈ption 1, ass(cid:40)ume (47) h(cid:41)old(cid:32)s for some λ > 0, η1κ2 1/2, (61)(cid:33)and (cid:88) (cid:88) (cid:88) (63). Then, we have for all t [T ], (cid:80) − − E (cid:107)S − S (cid:107) ≤ 16Mvκ2 1 k t 1 η2 t 1 ω ν 2 sup η k + 4λ η2 + η2κ2 . J ρ t+1 ρ t+1 ρ b k∈[t] ηkk l=1 l k=1 ti=k+1 ηi k=1 k t (64) (cid:40) (cid:41) (cid:13) (cid:13) Proof According to Lemmas 20 and 24, we have (5(cid:88)2) and ((cid:88)62). It(cid:13) thus follows (cid:13)that (cid:13) (cid:13) (cid:13) (cid:13) E E (cid:107)S ω − S ν (cid:107)2 ≤ 8 z(0)κ2 sup 1 k η t η2 T 12 Πt (T ) 2 . J ρ t+1 ρ t+1 ρ b ∈ η k l k ρ k+1 x k [t] k l=1 k=1 (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:88) (cid:13) (cid:13) (cid:88) (cid:13) (cid:13) (cid:13) (cid:13) Now the proof can be ﬁnished by applying Lemma 26 which tells us that (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) − t T 1 T 2 t 1 T 1 T 2 T 1 2 ηk2 ρ2 Πtk+1( x) = (cid:88) ηk2 ρ2 Πtk+1( x)(cid:88)+ ηt2 ρ2 k=1 k=1 (cid:80) − − ≤ t 1 η2 t 1 k + 4λ η2 + η2κ2, t η k t k=1 i=k+1 i k=1 and (63) to the above inequality. The proof is complete. − Setting η = η t θ for some appropriate η and θ in the above proposition, we get the following t 1 E (cid:107)S − S 1 (cid:107) explicitly upper bounds for ω ω 2. J ρ t ρ t ρ 31 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Using

text: we

text: can

text: relax

text: the

text: above

text: as

text: which

text: leads

text: to

text: Since

text: T

text: T

text: T

text: T

text: T

text: x

text: x)

text: x

text: x)

text: T

text: T

text: Πt

text: )Πt

text: λ

text: x

text: x

text: x

text: T

text: Πt

text: λ,

text: x

text: x

text: T

text: and

text: with

text: ηtκ2

text: x

text: tr(

text: x)

text: by

text: T

text: Πt

text: x

text: x

text: t

text: η

text: t

text: η

text: i

text: i

text: we

text: thus

text: derive

text: the

text: desired

text: result.

text: The

text: proof

text: is

text: complete.

text: Deriving

text: Error

text: Bounds

text: E

text: With

text: Lemmas

text: we

text: are

text: ready

text: to

text: estimate

text: the

text: computational

text: variance

text: ω

text: S

text: J

text: ρ

text: ν

text: as

text: follows.

text: ρ

text: ρ

text: Proposition

text: Under

text: Assum∈ption

text: for

text: some

text: λ

text: η1κ2

text: Then,

text: we

text: have

text: for

text: all

text: t

text: [T

text: E

text: S

text: k

text: t

text: η2

text: t

text: ω

text: ν

text: sup

text: η

text: k

text: 4λ

text: η2

text: η2κ2

text: J

text: ρ

text: ρ

text: ρ

text: b

text: k∈[t]

text: ηkk

text: l

text: ηi

text: k

text: t

text: Proof

text: According

text: to

text: Lemmas

text: and

text: we

text: have

text: and

text: thus

text: follows

text: E

text: E

text: ω

text: S

text: ν

text: sup

text: k

text: η

text: t

text: η2

text: T

text: Πt

text: (T

text: J

text: ρ

text: ρ

text: ρ

text: b

text: η

text: k

text: l

text: k

text: ρ

text: x

text: k

text: [t]

text: k

text: Now

text: the

text: proof

text: can

text: be

text: ﬁnished

text: by

text: applying

text: Lemma

text: which

text: tells

text: us

text: that

text: t

text: T

text: T

text: t

text: T

text: T

text: T

text: ρ2

text: x)

text: ρ2

text: ρ2

text: t

text: η2

text: t

text: k

text: 4λ

text: η2

text: t

text: η

text: k

text: t

text: i

text: and

text: to

text: the

text: above

text: inequality.

text: The

text: proof

text: is

text: complete.

text: Setting

text: η

text: η

text: t

text: θ

text: for

text: some

text: appropriate

text: η

text: and

text: θ

text: in

text: the

text: above

text: proposition,

text: we

text: get

text: the

text: following

text: t

text: E

text: S

text: explicitly

text: upper

text: bounds

text: for

text: ω

text: ω

text: J

text: ρ

text: t

text: ρ

text: t

text: ρ

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: L (cid:82) Under Assumption (3), can be proved to be positive trace class operators (Cucker and Zhou, ρ 2007), and hence Lζ with ζ ∈ R can be deﬁned by using the spectral theory. ρ − It is well known (see e.g., Cucker an(cid:90)d Zho→u,R2007) that the function minimizing Z(f(x) y)2dρ(z) over all measurable functions f : H is the regression function, given by | ∈ f (x) = ydρ(y x), x X. (6) ρ Y { → R|∃ ∈ (cid:104) (cid:105) } Deﬁne another Hilbert space H = f : X ω H with f(x) = ω, x , ρ -almost surely . ρ H X Under Assumption (3), it is easy to see that H is a subspace of L2(H, ρ ). Let fH be the ρ X projection of the regression function f onto the closure of H in L2(H, ρ ). It is easy to see ρ ρ X that the search for a solution of Problem (1) is equivalent to the search of a linear function in H ρ to approximate fH. From this point of view, bounds on the excess risk of a learning algorithm on H or H, naturally depend on the following assumption, which quantiﬁes how well, the target ρ function fH can be approximated by H . ρ (cid:107)L− (cid:107) ≤ Assumption 2 There exist ζ > 0 and R > 0, such that ζfH R. ρ ρ The above assumption is fairly standard in non-parametric regression (Cucker and Zhou, 2007; Rosasco and Villa, 2015). The bigger ζ is, the more stringent the assumption is, since L ⊆ L ≥ ζ1(L2(H, ρ )) ζ2(L2(H, ρ )) when ζ ζ . ρ X ρ X 1 2 In particular, for ζ = 0, we are making no assumption, while for ζ = 1/2, we are requiring ∈ fH H , since (Rosasco and Villa, 2015) ρ L H = 1/2(L2(H, ρ )). (7) ρ ρ X ≥ ∈ In the case of ζ 1/2, fH H , which implies Problem (1) has at least one solution in the ρ † space H. In this case, we denote ω as the solution with the minimal H-norm. Finally, the last assumption relates to the capacity of the hypothesis space. ∈ L Assumption 3 For some γ ]0, 1] and c > 0, satisﬁes γ ρ L L − ≤ − tr( ( + λI) 1) c λ γ, for all λ > 0. (8) ρ ρ γ The left hand-side of of (8) is called as the eﬀective dimension (Caponnetto and De Vito, 2007), or the degrees of freedom (Zhang, 2005). It can be related to covering/entropy number conditions, (cid:80) see (Steinwart and Christmann, 2008) for further details. Assumption 3 is always true for γ = 1 L L and c = κ2, since is a trace class operator which implies the eigenvalues of , denoted as σ , γ L ρ ≤ ρ i satisfy tr( ) = σ κ2. This is referred to as the capacity independent setting. Assumption ∈ ρ i i L 3 with γ ]0, 1] allows to derive better error rates. It is satisﬁed, e.g., if the eigenvalues of ∼ − L ρ satisfy a polynomial decaying condition σ i 1/γ, or with γ = 0 if is ﬁnite rank. i ρ 3.2 Optimal Rates for SGM and Batch GM: Simpliﬁed Versions We start with the following corollaries, which are the simpliﬁed versions of our main results stated in the next subsections. | | ≤ Corollary 1 (Optimal Rate for SGM) Under Assumptions 2 and 3, let y M almost surely for some M > 0. Let p∗ = (cid:100)m2ζ1+γ (cid:101) if 2ζ + γ > 1, or p∗ = (cid:100)m1−(cid:15)(cid:101) with (cid:15) ∈]0, 1[ otherwise. 5 ##LTLine##

text: L

text: Under

text: Assumption

text: can

text: be

text: proved

text: to

text: be

text: positive

text: trace

text: class

text: operators

text: (Cucker

text: and

text: Zhou,

text: ρ

text: and

text: hence

text: Lζ

text: with

text: ζ

text: R

text: can

text: be

text: deﬁned

text: by

text: using

text: the

text: spectral

text: theory.

text: ρ

text: It

text: is

text: well

text: known

text: (see

text: e.g.,

text: Cucker

text: that

text: the

text: function

text: minimizing

text: Z(f(x)

text: over

text: all

text: measurable

text: functions

text: f

text: H

text: is

text: the

text: regression

text: function,

text: given

text: by

text: f

text: (x)

text: ydρ(y

text: x),

text: x

text: X.

text: ρ

text: Y

text: R|∃

text: Deﬁne

text: another

text: Hilbert

text: space

text: H

text: f

text: X

text: ω

text: H

text: with

text: f(x)

text: ω,

text: x

text: ρ

text: -almost

text: surely

text: ρ

text: H

text: X

text: Under

text: Assumption

text: it

text: is

text: easy

text: to

text: see

text: that

text: H

text: is

text: a

text: subspace

text: of

text: ρ

text: Let

text: fH

text: be

text: the

text: ρ

text: X

text: projection

text: of

text: the

text: regression

text: function

text: f

text: onto

text: the

text: closure

text: of

text: H

text: in

text: ρ

text: It

text: is

text: easy

text: to

text: see

text: ρ

text: ρ

text: X

text: that

text: the

text: search

text: for

text: a

text: solution

text: of

text: Problem

text: is

text: equivalent

text: to

text: the

text: search

text: of

text: a

text: linear

text: function

text: in

text: H

text: ρ

text: to

text: approximate

text: fH.

text: From

text: this

text: point

text: of

text: view,

text: bounds

text: on

text: the

text: excess

text: risk

text: of

text: a

text: learning

text: algorithm

text: on

text: H

text: or

text: H,

text: naturally

text: depend

text: on

text: the

text: following

text: assumption,

text: which

text: quantiﬁes

text: how

text: well,

text: the

text: target

text: ρ

text: function

text: fH

text: can

text: be

text: approximated

text: by

text: H

text: ρ

text: Assumption

text: There

text: exist

text: ζ

text: and

text: R

text: such

text: that

text: ζfH

text: R.

text: ρ

text: ρ

text: The

text: above

text: assumption

text: is

text: fairly

text: standard

text: in

text: non-parametric

text: regression

text: (Cucker

text: and

text: Zhou,

text: Rosasco

text: and

text: Villa,

text: The

text: bigger

text: ζ

text: is,

text: the

text: more

text: stringent

text: the

text: assumption

text: is,

text: since

text: L

text: L

text: ρ

text: ρ

text: when

text: ζ

text: ζ

text: ρ

text: X

text: ρ

text: X

text: In

text: particular,

text: for

text: ζ

text: we

text: are

text: making

text: no

text: assumption,

text: while

text: for

text: ζ

text: we

text: are

text: requiring

text: fH

text: H

text: since

text: (Rosasco

text: and

text: Villa,

text: ρ

text: L

text: H

text: ρ

text: ρ

text: ρ

text: X

text: In

text: the

text: case

text: of

text: ζ

text: fH

text: H

text: which

text: implies

text: Problem

text: has

text: at

text: least

text: one

text: solution

text: in

text: the

text: ρ

text: space

text: H.

text: In

text: this

text: case,

text: we

text: denote

text: ω

text: as

text: the

text: solution

text: with

text: the

text: minimal

text: H-norm.

text: Finally,

text: the

text: last

text: assumption

text: relates

text: to

text: the

text: capacity

text: of

text: the

text: hypothesis

text: space.

text: L

text: Assumption

text: For

text: some

text: γ

text: and

text: c

text: satisﬁes

text: γ

text: ρ

text: L

text: L

text: tr(

text: λI)

text: c

text: λ

text: γ,

text: for

text: all

text: λ

text: ρ

text: ρ

text: γ

text: The

text: left

text: hand-side

text: of

text: of

text: is

text: called

text: as

text: the

text: eﬀective

text: dimension

text: (Caponnetto

text: and

text: De

text: Vito,

text: or

text: the

text: degrees

text: of

text: freedom

text: (Zhang,

text: It

text: can

text: be

text: related

text: to

text: covering/entropy

text: number

text: conditions,

text: see

text: (Steinwart

text: and

text: Christmann,

text: for

text: further

text: details.

text: Assumption

text: is

text: always

text: true

text: for

text: γ

text: L

text: L

text: and

text: c

text: since

text: is

text: a

text: trace

text: class

text: operator

text: which

text: implies

text: the

text: eigenvalues

text: of

text: denoted

text: as

text: σ

text: γ

text: L

text: ρ

text: ρ

text: i

text: satisfy

text: tr(

text: σ

text: This

text: is

text: referred

text: to

text: as

text: the

text: capacity

text: independent

text: setting.

text: Assumption

text: ρ

text: i

text: i

text: L

text: with

text: γ

text: allows

text: to

text: derive

text: better

text: error

text: rates.

text: It

text: is

text: satisﬁed,

text: e.g.,

text: if

text: the

text: eigenvalues

text: of

text: L

text: ρ

text: satisfy

text: a

text: polynomial

text: decaying

text: condition

text: σ

text: i

text: or

text: with

text: γ

text: if

text: is

text: ﬁnite

text: rank.

text: i

text: ρ

text: Optimal

text: Rates

text: for

text: SGM

text: and

text: Batch

text: GM:

text: Simpliﬁed

text: Versions

text: We

text: start

text: with

text: the

text: following

text: corollaries,

text: which

text: are

text: the

text: simpliﬁed

text: versions

text: of

text: our

text: main

text: results

text: stated

text: in

text: the

text: next

text: subsections.

text: Corollary

text: (Optimal

text: Rate

text: for

text: SGM)

text: Under

text: Assumptions

text: and

text: let

text: y

text: M

text: almost

text: surely

text: for

text: some

text: M

text: Let

text: p∗

text: if

text: 2ζ

text: γ

text: or

text: p∗

text: with

text: otherwise.

text: ##LTLine##


text: (cid:80) ≤ − ≤ Case ζ < 1/2. If t η κ(cid:88)2, then for any σ κ2(cid:88), k=1 k t t ≤ ≤ − (cid:80) σ1/2+ζ η Πt(cid:80) (σ) σ1/2+ζ η κ2ζ 1. k k+1 k k=1 k=1 − ≤ − (cid:32) (cid:33) If t η > κ 2, then f(cid:88)or any σ ( t η ) 1(cid:88), (cid:88) k=1 k k=1 k − t t t 1/2 ζ ≤ ≤ σ1/(cid:80)2+ζ η Πt (σ) σ1/2+ζ η η , k k+1 k k k=1 k=1 k=1 ≥ ≥ − (cid:32) (cid:33) while for κ2 σ(cid:88) ( t η ) 1, by (80(cid:88)), (cid:88) k=1 k − t t t 1/2 ζ − ≤ − ≤ σ1/2+ζ η Πt (σ) = σζ 1/2 η σΠt (σ) σζ 1/2 η . k k+1 k k+1 k k=1 k=1 k=1 (cid:32) (cid:33) From the above analysis, we get(cid:88)that (cid:88) − t t 1/2 ζ ≤ − ∨ max σ1/2+ζ η Πt (σ) κ2ζ 1 η , ∈ k k+1 k σ ]0,κ2] k=1  k=1  (cid:32) (cid:33)  (cid:88)  and thus  −  t 1/2 ζ (cid:107) (cid:107) ≤ − ∨ µ R κ2ζ 1 η . t+1 H k k=1 (cid:13) (cid:13) The proof is complete. (cid:13) (cid:0) (cid:1)(cid:13) (cid:13) (cid:13) T − S∗ − S∗ 1 Proof [of Lemma 18 (1)] Bounding ( ρ + λ) 2 ρfρ xy : ∈ T − H S 1 For all i [m], let wi = yi( ρ + λI) 2 xi. Obviously, from the deﬁnitions of fρ (see (6)) and ρ, E E T −1 T −1 S∗ [w1] = x1[fρ(x1)( ρ + λI) 2 x1] = ( ρ + λI) 2 ρfρ. (cid:0) (cid:1) (cid:88) Thus, m T −1 S∗ − S∗ 1 E − ( ρ + λ) 2 ρfρ xy = m ( [wi] wi). i=1 ≥ We next estimate the constants B and σ2(w ) in (28). Note that for any l 2, 1 E (cid:107) − E (cid:107) ≤ E (cid:107) (cid:107) E (cid:107) (cid:107) [ w [w ] l ] [( w + [ w ])l]. 1 1 H 1 H 1 H By using H¨older’s inequality twice, E (cid:107) − E (cid:107) ≤ − E (cid:107) (cid:107) E (cid:107) (cid:107) ≤ − E (cid:107) (cid:107) E (cid:107) (cid:107) [ w [w ] l ] 2l 1 [ w l + ( [ w ])l] 2l 1 [ w l + [ w l ]]. 1 1 H 1 H 1 H 1 H 1 H E (cid:107) (cid:107) The right-hand side is exactly 2l [ w(cid:90) l ]. Therefore, by(cid:90)recalling the deﬁnition of w and 1 H 1 expanding the integration, E[(cid:107)w1 − E[w1](cid:107)lH] ≤ 2l (cid:107)(Tρ + λI)−12 x(cid:107)lH yldρ(y|x)dρX(x). (81) X Y 41 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Case

text: ζ

text: If

text: t

text: η

text: then

text: for

text: any

text: σ

text: k

text: t

text: t

text: η

text: (σ)

text: η

text: κ2ζ

text: k

text: k

text: If

text: t

text: η

text: κ

text: then

text: any

text: σ

text: t

text: η

text: k

text: k

text: t

text: t

text: t

text: ζ

text: η

text: Πt

text: (σ)

text: η

text: η

text: k

text: k

text: k

text: while

text: for

text: κ2

text: t

text: η

text: by

text: k

text: t

text: t

text: t

text: ζ

text: η

text: Πt

text: (σ)

text: σζ

text: η

text: σΠt

text: (σ)

text: σζ

text: η

text: k

text: k

text: k

text: From

text: the

text: above

text: analysis,

text: we

text: t

text: t

text: ζ

text: max

text: η

text: Πt

text: (σ)

text: κ2ζ

text: η

text: k

text: k

text: σ

text: and

text: thus

text: t

text: ζ

text: µ

text: R

text: κ2ζ

text: η

text: H

text: k

text: The

text: proof

text: is

text: complete.

text: T

text: S∗

text: S∗

text: Proof

text: [of

text: Lemma

text: Bounding

text: ρ

text: λ)

text: ρfρ

text: xy

text: T

text: H

text: S

text: For

text: all

text: i

text: [m],

text: let

text: wi

text: yi(

text: ρ

text: λI)

text: xi.

text: Obviously,

text: from

text: the

text: deﬁnitions

text: of

text: fρ

text: (see

text: and

text: ρ,

text: E

text: E

text: T

text: −1

text: T

text: −1

text: S∗

text: ρ

text: λI)

text: ρ

text: λI)

text: ρfρ.

text: Thus,

text: m

text: T

text: −1

text: S∗

text: S∗

text: E

text: ρ

text: λ)

text: ρfρ

text: xy

text: m

text: [wi]

text: wi).

text: We

text: next

text: estimate

text: the

text: constants

text: B

text: and

text: in

text: Note

text: that

text: for

text: any

text: l

text: E

text: E

text: E

text: E

text: w

text: [w

text: l

text: w

text: w

text: ])l].

text: H

text: H

text: H

text: By

text: using

text: H¨older’s

text: inequality

text: twice,

text: E

text: E

text: E

text: E

text: E

text: E

text: w

text: [w

text: l

text: w

text: l

text: w

text: ])l]

text: w

text: l

text: w

text: l

text: H

text: H

text: H

text: H

text: H

text: E

text: The

text: right-hand

text: side

text: is

text: exactly

text: l

text: Therefore,

text: the

text: deﬁnition

text: of

text: w

text: and

text: H

text: expanding

text: the

text: integration,

text: yldρ(y|x)dρX(x).

text: X

text: Y

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: D. List of Some Notations Notation Meaning H the hypothesis space × X, Y, Z the input space, the output space and the sample space (Z = X Y ) ρ the ﬁxed probability measure on Z ρ the induced marginal measure of ρ on X ·X| ∈ ρ( x) the conditional probability measure on Y w.r.t. x X and ρ { } ∈ N z the sample z = (x , y ) m of size m , where each z is i.i.d. according to ρ. i i i i=1 i m the sample size of the sample z E the expected risk deﬁned by (1) E the empirical risk w.r.t the sample z deﬁned by (20) z κ2 the constant from the bounded assumption (3) on the hypothesis space H { } ω the sequence generated by the SGM t t θ the decaying rate on step-sizes b the minibatch size of the SGM T the maximal number of iterations for the SGM j (j etc.) the random index from the uniform distribution on [m] for the SGM i t J the set of random indices at t-th iteration of the SGM t J the set of all random indices for the SGM after T iterations E the expectation with respect to the random variables J (conditional on z) { J} η the sequence of step-sizes t t M, v the positive constants from the moment (bounded) assumption on the output R L2(H, ρ ) the Hilbert space of square integral functions from H to with respect to ρ X X f the regression function deﬁned (6) ρ { → R|∃ ∈ (cid:104) (cid:105) } H f : X ω H with f(x) = ω, x , ρ -almost surely ρ H X ζ, R the parameters related to the ‘regularity’ of fH (see Assumption 2) † ω the solution of Problem (1) with the minimal norm in the attainable case γ, c the parameters related to the eﬀective dimension (see Assumption 3) { }γ L σ the sequence of eigenvalues of { i}i ρ ν the sequence generated by the batch GM (10) { t}t (cid:82) µ the sequence deﬁned by the population iteration (21) Sk k → S (cid:104) ·(cid:105) (cid:82) the linear map from H L2(H, ρ ) deﬁned by ω = ω, Sρ∗ S S∗ X ρ (cid:82) the adjoint operator of , f = f(x)xdρ (x) Lρ ρ ρ X LX S S∗ (cid:104) ·(cid:105) the operator from L2(H, ρ ) to L2(H, ρ ), (f) = f = x, f(x)ρ (x) Tρ X (cid:80)TX Sρ∗S ρ(cid:104)·ρ (cid:105) X H X the covariance operator from H to H, = = , x xdρ (x) Sρ R Sρ ρ ρ(cid:104) (cid:80)X(cid:105) ∈ X the sampling operator from H to m, ( ω) = ω, x , i [m] Sx∗ S S∗ x i i H the adjoint operator of , y = 1 m y x (cid:80) Tx x x Tm i=S1∗Si i (cid:104)· (cid:105) the empirical covariance operator, = = 1 m , x x x − ∈ − x x x m i=1 i i ΠT (L) = Π (I η L) when t [T 1] and ΠT = I t+1 k=t+1 k T+1 t η = 0 i=t+1 i λ a ‘regularization’ parameter, λ > 0 T T T , = + λ Tρ,λ Tρ,λ Tρ , = + λ { x,λ} x,λ x N the sequence deﬁned by (38). k k M deﬁned by (53) k,i 44 ##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: D.

text: List

text: of

text: Some

text: Notations

text: Notation

text: Meaning

text: H

text: the

text: hypothesis

text: space

text: X,

text: Y,

text: Z

text: the

text: input

text: space,

text: the

text: output

text: space

text: and

text: the

text: sample

text: space

text: (Z

text: X

text: Y

text: ρ

text: the

text: ﬁxed

text: probability

text: measure

text: on

text: Z

text: ρ

text: the

text: induced

text: marginal

text: measure

text: of

text: ρ

text: on

text: X

text: ·X|

text: ρ(

text: x)

text: the

text: conditional

text: probability

text: measure

text: on

text: Y

text: w.r.t.

text: x

text: X

text: and

text: ρ

text: N

text: z

text: the

text: sample

text: z

text: (x

text: y

text: m

text: of

text: size

text: m

text: where

text: each

text: z

text: is

text: i.i.d.

text: according

text: to

text: ρ.

text: i

text: i

text: i

text: i

text: m

text: the

text: sample

text: size

text: of

text: the

text: sample

text: z

text: E

text: the

text: expected

text: risk

text: deﬁned

text: by

text: E

text: the

text: empirical

text: risk

text: w.r.t

text: the

text: sample

text: z

text: deﬁned

text: by

text: z

text: κ2

text: the

text: constant

text: from

text: the

text: bounded

text: assumption

text: on

text: the

text: hypothesis

text: space

text: H

text: ω

text: the

text: sequence

text: generated

text: by

text: the

text: SGM

text: t

text: t

text: θ

text: the

text: decaying

text: rate

text: on

text: step-sizes

text: b

text: the

text: minibatch

text: size

text: of

text: the

text: SGM

text: T

text: the

text: maximal

text: number

text: of

text: iterations

text: for

text: the

text: SGM

text: j

text: (j

text: etc.)

text: the

text: random

text: index

text: from

text: the

text: uniform

text: distribution

text: on

text: [m]

text: for

text: the

text: SGM

text: i

text: t

text: J

text: the

text: set

text: of

text: random

text: indices

text: at

text: t-th

text: iteration

text: of

text: the

text: SGM

text: t

text: J

text: the

text: set

text: of

text: all

text: random

text: indices

text: for

text: the

text: SGM

text: after

text: T

text: iterations

text: E

text: the

text: expectation

text: with

text: respect

text: to

text: the

text: random

text: variables

text: J

text: (conditional

text: on

text: z)

text: J}

text: η

text: the

text: sequence

text: of

text: step-sizes

text: t

text: t

text: M,

text: v

text: the

text: positive

text: constants

text: from

text: the

text: moment

text: (bounded)

text: assumption

text: on

text: the

text: output

text: R

text: ρ

text: the

text: Hilbert

text: space

text: of

text: square

text: integral

text: functions

text: from

text: H

text: to

text: with

text: respect

text: to

text: ρ

text: X

text: X

text: f

text: the

text: regression

text: function

text: deﬁned

text: ρ

text: R|∃

text: H

text: f

text: X

text: ω

text: H

text: with

text: f(x)

text: ω,

text: x

text: ρ

text: -almost

text: surely

text: ρ

text: H

text: X

text: ζ,

text: R

text: the

text: parameters

text: related

text: to

text: the

text: ‘regularity’

text: of

text: fH

text: (see

text: Assumption

text: ω

text: the

text: solution

text: of

text: Problem

text: with

text: the

text: minimal

text: norm

text: in

text: the

text: attainable

text: case

text: γ,

text: c

text: the

text: parameters

text: related

text: to

text: the

text: eﬀective

text: dimension

text: (see

text: Assumption

text: }γ

text: L

text: σ

text: the

text: sequence

text: of

text: eigenvalues

text: of

text: i}i

text: ρ

text: ν

text: the

text: sequence

text: generated

text: by

text: the

text: batch

text: GM

text: t}t

text: µ

text: the

text: sequence

text: deﬁned

text: by

text: the

text: population

text: iteration

text: Sk

text: k

text: S

text: the

text: linear

text: map

text: from

text: H

text: ρ

text: deﬁned

text: by

text: ω

text: ω,

text: Sρ∗

text: S

text: S∗

text: X

text: ρ

text: the

text: adjoint

text: operator

text: of

text: f

text: f(x)xdρ

text: (x)

text: Lρ

text: ρ

text: ρ

text: X

text: LX

text: S

text: S∗

text: the

text: operator

text: from

text: ρ

text: to

text: ρ

text: (f)

text: f

text: x,

text: f(x)ρ

text: (x)

text: Tρ

text: X

text: Sρ∗S

text: X

text: H

text: X

text: the

text: covariance

text: operator

text: from

text: H

text: to

text: H,

text: x

text: xdρ

text: (x)

text: Sρ

text: R

text: Sρ

text: ρ

text: X

text: the

text: sampling

text: operator

text: from

text: H

text: to

text: m,

text: ω)

text: ω,

text: x

text: i

text: [m]

text: Sx∗

text: S

text: S∗

text: x

text: i

text: i

text: H

text: the

text: adjoint

text: operator

text: of

text: y

text: m

text: y

text: x

text: Tx

text: x

text: x

text: Tm

text: i

text: the

text: empirical

text: covariance

text: operator,

text: m

text: x

text: x

text: x

text: x

text: x

text: x

text: m

text: i

text: i

text: ΠT

text: (L)

text: Π

text: (I

text: η

text: L)

text: when

text: t

text: [T

text: and

text: ΠT

text: I

text: k

text: t

text: η

text: i

text: λ

text: a

text: ‘regularization’

text: parameter,

text: λ

text: T

text: T

text: T

text: λ

text: Tρ,λ

text: Tρ,λ

text: Tρ

text: λ

text: x,λ}

text: x,λ

text: x

text: N

text: the

text: sequence

text: deﬁned

text: by

text: k

text: k

text: M

text: deﬁned

text: by

text: k,i

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: 2 Bike-sharing Agent-based Modeling have been questioned and transposed to diﬀerent potential countries such as China ([4, 5]) or the United States ([6]). The understanding of system mechanisms is essential for its optimal exploita- tion. That can be done through statistical analysis with predictive statistical models ([7–10]) or data-mining techniques ([3, 11]), and can give broader results such as structure of urban mobility patterns. Concerning the implementation, a crucial point in the design of the system is an optimal location of stations. That problem have been extensively studied from an Operational Research point of view ([12, 13] for example). The next step is a good exploitation of the system. By nature, strong asymmetries appear in the distribution of bikes: docking sta- tions in residential areas are emptied during the day contrary to working areas. That causes in most cases a strong decrease in the level of service (no parking places or no available bikes for example). To counter such phenomena, operators have redistribution strategies that have also been well studied and for which optimal plans have been proposed ([14–16]). However, all these studies always approach the problem from a top-down point of view, in the sense of a centralized and global approach of the issues, whereas bottom-up strategies (i. e. local actions that would allow the emergence of desired patterns) have been to our knowledge not much considered in the literature. User-based methods have been considered in [17, 18] in the case of a car-sharing system, but the problem stays quite far from a behavioral model of the agents using the system, since it explores the possibility of implication of users in the redistribution process, or of shared travels what is not relevant in the case of bikes. Indeed the question of a precise determination of the inﬂu- ence of users behaviors and parameters on the level of service of a bike-sharing systems remains open. We propose an agent-based model of simulation in order to represent and simulate the system from a bottom-up approach, considering bikers and parking as stations as agents and representing their interactions and evolutions in time. That allows to explore user-targeted strategies for an increase of the level of service, as the incitation to use online information media or to be more ﬂexible on the destination point. Note that our work aims to explore eﬀects of user-based policies, but does not pretend to give recommendations to system managers, since our approach stays technical and eludes crucial political and human aspects that one should take into account in a broader system design or management context. The rest of the paper is organized as follows. The model and indicator used to quantify its behavior are described in Section 2. Next, Section 3 presents the implementation and results, including internal and external validations of the model by sensitivity analysis and simpliﬁed calibration on real data, and also exploration of possible bottom-up strategies for system management. We conclude by a discussion on the applicability of results and on possible develop- ments. 2 Presentation of the model Introduction The granularity of the model is the scale of the individual biker and of the stations where bikes are parked. A more integrated view such as

text: Bike-sharing

text: Agent-based

text: Modeling

text: have

text: been

text: questioned

text: and

text: transposed

text: to

text: diﬀerent

text: potential

text: countries

text: such

text: as

text: China

text: or

text: the

text: United

text: States

text: The

text: understanding

text: of

text: system

text: mechanisms

text: is

text: essential

text: for

text: its

text: optimal

text: exploita-

text: tion.

text: That

text: can

text: be

text: done

text: through

text: statistical

text: analysis

text: with

text: predictive

text: statistical

text: models

text: or

text: data-mining

text: techniques

text: and

text: can

text: give

text: broader

text: results

text: such

text: as

text: structure

text: of

text: urban

text: mobility

text: patterns.

text: Concerning

text: the

text: implementation,

text: a

text: crucial

text: point

text: in

text: the

text: design

text: of

text: the

text: system

text: is

text: an

text: optimal

text: location

text: of

text: stations.

text: That

text: problem

text: have

text: been

text: extensively

text: studied

text: from

text: an

text: Operational

text: Research

text: point

text: of

text: view

text: for

text: example).

text: The

text: next

text: step

text: is

text: a

text: good

text: exploitation

text: of

text: the

text: system.

text: By

text: nature,

text: strong

text: asymmetries

text: appear

text: in

text: the

text: distribution

text: of

text: bikes:

text: docking

text: sta-

text: tions

text: in

text: residential

text: areas

text: are

text: emptied

text: during

text: the

text: day

text: contrary

text: to

text: working

text: areas.

text: That

text: causes

text: in

text: most

text: cases

text: a

text: strong

text: decrease

text: in

text: the

text: level

text: of

text: service

text: (no

text: parking

text: places

text: or

text: no

text: available

text: bikes

text: for

text: example).

text: To

text: counter

text: such

text: phenomena,

text: operators

text: have

text: redistribution

text: strategies

text: that

text: have

text: also

text: been

text: well

text: studied

text: and

text: for

text: which

text: optimal

text: plans

text: have

text: been

text: proposed

text: However,

text: all

text: these

text: studies

text: always

text: approach

text: the

text: problem

text: from

text: a

text: top-down

text: point

text: of

text: view,

text: in

text: the

text: sense

text: of

text: a

text: centralized

text: and

text: global

text: approach

text: of

text: the

text: issues,

text: whereas

text: bottom-up

text: strategies

text: (i.

text: e.

text: local

text: actions

text: that

text: would

text: allow

text: the

text: emergence

text: of

text: desired

text: patterns)

text: have

text: been

text: to

text: our

text: knowledge

text: not

text: much

text: considered

text: in

text: the

text: literature.

text: User-based

text: methods

text: have

text: been

text: considered

text: in

text: in

text: the

text: case

text: of

text: a

text: car-sharing

text: system,

text: but

text: the

text: problem

text: stays

text: quite

text: far

text: from

text: a

text: behavioral

text: model

text: of

text: the

text: agents

text: using

text: the

text: system,

text: since

text: it

text: explores

text: the

text: possibility

text: of

text: implication

text: of

text: users

text: in

text: the

text: redistribution

text: process,

text: or

text: of

text: shared

text: travels

text: what

text: is

text: not

text: relevant

text: in

text: the

text: case

text: of

text: bikes.

text: Indeed

text: the

text: question

text: of

text: a

text: precise

text: determination

text: of

text: the

text: inﬂu-

text: ence

text: of

text: users

text: behaviors

text: and

text: parameters

text: on

text: the

text: level

text: of

text: service

text: of

text: a

text: bike-sharing

text: systems

text: remains

text: open.

text: We

text: propose

text: an

text: agent-based

text: model

text: of

text: simulation

text: in

text: order

text: to

text: represent

text: and

text: simulate

text: the

text: system

text: from

text: a

text: bottom-up

text: approach,

text: considering

text: bikers

text: and

text: parking

text: as

text: stations

text: as

text: agents

text: and

text: representing

text: their

text: interactions

text: and

text: evolutions

text: in

text: time.

text: That

text: allows

text: to

text: explore

text: user-targeted

text: strategies

text: for

text: an

text: increase

text: of

text: the

text: level

text: of

text: service,

text: as

text: the

text: incitation

text: to

text: use

text: online

text: information

text: media

text: or

text: to

text: be

text: more

text: ﬂexible

text: on

text: the

text: destination

text: point.

text: Note

text: that

text: our

text: work

text: aims

text: to

text: explore

text: eﬀects

text: of

text: user-based

text: policies,

text: but

text: does

text: not

text: pretend

text: to

text: give

text: recommendations

text: to

text: system

text: managers,

text: since

text: our

text: approach

text: stays

text: technical

text: and

text: eludes

text: crucial

text: political

text: and

text: human

text: aspects

text: that

text: one

text: should

text: take

text: into

text: account

text: in

text: a

text: broader

text: system

text: design

text: or

text: management

text: context.

text: The

text: rest

text: of

text: the

text: paper

text: is

text: organized

text: as

text: follows.

text: The

text: model

text: and

text: indicator

text: used

text: to

text: quantify

text: its

text: behavior

text: are

text: described

text: in

text: Section

text: Next,

text: Section

text: presents

text: the

text: implementation

text: and

text: results,

text: including

text: internal

text: and

text: external

text: validations

text: of

text: the

text: model

text: by

text: sensitivity

text: analysis

text: and

text: simpliﬁed

text: calibration

text: on

text: real

text: data,

text: and

text: also

text: exploration

text: of

text: possible

text: bottom-up

text: strategies

text: for

text: system

text: management.

text: We

text: conclude

text: by

text: a

text: discussion

text: on

text: the

text: applicability

text: of

text: results

text: and

text: on

text: possible

text: develop-

text: ments.

text: Presentation

text: of

text: the

text: model

text: Introduction

text: The

text: granularity

text: of

text: the

text: model

text: is

text: the

text: scale

text: of

text: the

text: individual

text: biker

text: and

text: of

text: the

text: stations

text: where

text: bikes

text: are

text: parked.

text: A

text: more

text: integrated

text: view

text: such

text: as


text: Bike-sharing Agent-based Modeling 13 10. Pierre Borgnat, Patrice Abry, Patrick Flandrin, C´eline Robardet, Jean-Baptiste Rouquier, and Eric Fleury. Shared bicycles in a city: A signal processing and data analysis perspective. Advances in Complex Systems, 14(03):415–438, 2011. 11. Andreas Kaltenbrunner, Rodrigo Meza, Jens Grivolla, Joan Codina, and Rafael Banchs. Urban cycles and mobility patterns: Exploring and predicting trends in a bicycle-based public transport system. Pervasive and Mobile Computing, 6(4):455– 466, 2010. 12. Jenn-Rong Lin, Ta-Hui Yang, and Yu-Chung Chang. A hub location inventory model for bicycle sharing system design: Formulation and solution. Computers & Industrial Engineering, 2011. 13. Jenn-Rong Lin and Ta-Hui Yang. Strategic design of public bicycle sharing sys- tems with service level constraints. Transportation research part E: logistics and transportation review, 47(2):284–294, 2011. 14. Alvina GH Kek, Ruey Long Cheu, and Miaw Ling Chor. Relocation simulation model for multiple-station shared-use vehicle systems. Transportation Research Record: Journal of the Transportation Research Board, 1986(1):81–88, 2006. 15. Rahul Nair and Elise Miller-Hooks. Fleet management for vehicle sharing opera- tions. Transportation Science, 45(4):524–540, 2011. 16. Rahul Nair, Elise Miller-Hooks, Robert C Hampshire, and Ana Buˇsi´c. Large-scale vehicle sharing systems: Analysis of v´elib’. International Journal of Sustainable Transportation, 7(1):85–106, 2013. 17. Matthew Barth and Michael Todd. Simulation model performance analysis of a multiple station shared vehicle system. Transportation Research Part C: Emerging Technologies, 7(4):237–259, 1999. 18. Matthew Barth, Michael Todd, and Lei Xue. User-based vehicle relocation tech- niques for multiple-station shared-use vehicle systems. TRB Paper No. 04-4161, 2004. 19. Arnaud Banos, Annabelle Boﬀet-Mas, Sonia Chardonnel, Christophe Lang, Nicolas Marilleau, Thomas Th´evenin, et al. Simuler la mobilit´e urbaine quotidienne: le projet miro. Mobilit´es urbaines et risques des transports, 2011. 20. Patrick Vogel, Torsten Greiser, and Dirk Christian Mattfeld. Understanding bike- sharing systems using data mining: Exploring activity patterns. Procedia-Social and Behavioral Sciences, 20:514–523, 2011. 21. U. Wilensky. Netlogo. Center for Connected Learning and Computer-Based Mod- eling, Northwestern University, Evanston, IL., 1999. 22. QGIS Development Team. QGIS Geographic Information System. Open Source Geospatial Foundation, 2009. 23. R Core Team. R: A Language and Environment for Statistical Computing. R Foundation for Statistical Computing, Vienna, Austria, 2013. 24. Jan C Thiele, Winfried Kurth, and Volker Grimm. Agent-based modelling: Tools for linking netlogo and r. Journal of Artiﬁcial Societies and Social Simulation, 15(3):8, 2012. 25. Arnaud Banos. Pour des pratiques de mod´elisation et de simulation lib´er´ees en G´eographie et SHS. PhD thesis, UMR CNRS G´eographie-Cit´es, ISCPIF, D´ecembre 2013. 26. Jonathan Bennett. OpenStreetMap. Packt Publishing, 2010. 27. Alex Couture-Beil. rjson: Json for r. R package version 0.2, 13, 2013. 28. Timothy H Keitt, Roger Bivand, Edzer Pebesma, and Barry Rowlingson. rgdal: bindings for the geospatial data abstraction library. R package version 0.7-1, URL http://CRAN. R-project. org/package= rgdal, 2011.

text: Bike-sharing

text: Agent-based

text: Modeling

label: reference

text: Pierre

text: Borgnat,

text: Patrice

text: Abry,

text: Patrick

text: Flandrin,

text: C´eline

text: Robardet,

text: Jean-Baptiste

text: Rouquier,

text: and

text: Eric

text: Fleury.

text: Shared

text: bicycles

text: in

text: a

text: city:

text: A

text: signal

text: processing

text: and

text: data

text: analysis

text: perspective.

text: Advances

text: in

text: Complex

text: Systems,

text: Andreas

text: Kaltenbrunner,

text: Rodrigo

text: Meza,

text: Jens

text: Grivolla,

text: Joan

text: Codina,

text: and

text: Rafael

text: Banchs.

text: Urban

text: cycles

text: and

text: mobility

text: patterns:

text: Exploring

text: and

text: predicting

text: trends

text: in

text: a

text: bicycle-based

text: public

text: transport

text: system.

text: Pervasive

text: and

text: Mobile

text: Computing,

text: Jenn-Rong

text: Lin,

text: Ta-Hui

text: Yang,

text: and

text: Yu-Chung

text: Chang.

text: A

text: hub

text: location

text: inventory

text: model

text: for

text: bicycle

text: sharing

text: system

text: design:

text: Formulation

text: and

text: solution.

text: Computers

text: Industrial

text: Engineering,

text: Jenn-Rong

text: Lin

text: and

text: Ta-Hui

text: Yang.

text: Strategic

text: design

text: of

text: public

text: bicycle

text: sharing

text: sys-

text: tems

text: with

text: service

text: level

text: constraints.

text: Transportation

text: research

text: part

text: E:

text: logistics

text: and

text: transportation

text: review,

text: Alvina

text: GH

text: Kek,

text: Ruey

text: Long

text: Cheu,

text: and

text: Miaw

text: Ling

text: Chor.

text: Relocation

text: simulation

text: model

text: for

text: multiple-station

text: shared-use

text: vehicle

text: systems.

text: Transportation

text: Research

text: Record:

text: Journal

text: of

text: the

text: Transportation

text: Research

text: Board,

text: Rahul

text: Nair

text: and

text: Elise

text: Miller-Hooks.

text: Fleet

text: management

text: for

text: vehicle

text: sharing

text: opera-

text: tions.

text: Transportation

text: Science,

text: Rahul

text: Nair,

text: Elise

text: Miller-Hooks,

text: Robert

text: C

text: Hampshire,

text: and

text: Ana

text: Buˇsi´c.

text: Large-scale

text: vehicle

text: sharing

text: systems:

text: Analysis

text: of

text: v´elib’.

text: International

text: Journal

text: of

text: Sustainable

text: Transportation,

text: Matthew

text: Barth

text: and

text: Michael

text: Todd.

text: Simulation

text: model

text: performance

text: analysis

text: of

text: a

text: multiple

text: station

text: shared

text: vehicle

text: system.

text: Transportation

text: Research

text: Part

text: C:

text: Emerging

text: Technologies,

text: Matthew

text: Barth,

text: Michael

text: Todd,

text: and

text: Lei

text: Xue.

text: User-based

text: vehicle

text: relocation

text: tech-

text: niques

text: for

text: multiple-station

text: shared-use

text: vehicle

text: systems.

text: TRB

text: Paper

text: No.

text: Arnaud

text: Banos,

text: Annabelle

text: Boﬀet-Mas,

text: Sonia

text: Chardonnel,

text: Christophe

text: Lang,

text: Nicolas

text: Marilleau,

text: Thomas

text: Th´evenin,

text: et

text: al.

text: Simuler

text: la

text: mobilit´e

text: urbaine

text: quotidienne:

text: le

text: projet

text: miro.

text: Mobilit´es

text: urbaines

text: et

text: risques

text: des

text: transports,

text: Patrick

text: Vogel,

text: Torsten

text: Greiser,

text: and

text: Dirk

text: Christian

text: Mattfeld.

text: Understanding

text: bike-

text: sharing

text: systems

text: using

text: data

text: mining:

text: Exploring

text: activity

text: patterns.

text: Procedia-Social

text: and

text: Behavioral

text: Sciences,

text: U.

text: Wilensky.

text: Netlogo.

text: Center

text: for

text: Connected

text: Learning

text: and

text: Computer-Based

text: Mod-

text: eling,

text: Northwestern

text: University,

text: Evanston,

text: IL.,

text: QGIS

text: Development

text: Team.

text: QGIS

text: Geographic

text: Information

text: System.

text: Open

text: Source

text: Geospatial

text: Foundation,

text: R

text: Core

text: Team.

text: R:

text: A

text: Language

text: and

text: Environment

text: for

text: Statistical

text: Computing.

text: R

text: Foundation

text: for

text: Statistical

text: Computing,

text: Vienna,

text: Austria,

text: Jan

text: C

text: Thiele,

text: Winfried

text: Kurth,

text: and

text: Volker

text: Grimm.

text: Agent-based

text: modelling:

text: Tools

text: for

text: linking

text: netlogo

text: and

text: r.

text: Journal

text: of

text: Artiﬁcial

text: Societies

text: and

text: Social

text: Simulation,

text: Arnaud

text: Banos.

text: Pour

text: des

text: pratiques

text: de

text: mod´elisation

text: et

text: de

text: simulation

text: lib´er´ees

text: en

text: G´eographie

text: et

text: SHS.

text: PhD

text: thesis,

text: UMR

text: CNRS

text: G´eographie-Cit´es,

text: ISCPIF,

text: D´ecembre

text: Jonathan

text: Bennett.

text: OpenStreetMap.

text: Packt

text: Publishing,

text: Alex

text: Couture-Beil.

text: rjson:

text: Json

text: for

text: r.

text: R

text: package

text: version

text: Timothy

text: H

text: Keitt,

text: Roger

text: Bivand,

text: Edzer

text: Pebesma,

text: and

text: Barry

text: Rowlingson.

text: rgdal:

text: bindings

text: for

text: the

text: geospatial

text: data

text: abstraction

text: library.

text: R

text: package

text: version

text: URL

text: R-project.

text: org/package=

text: rgdal,


text: 4GS 5GS Overall Fleiss’ κ 4GS 5GS Bowman et al. 2015 Pairs with majority 95.6% 96.7% 96.1% Contradiction 0.37 0.59 0.77 agreement Entailment 0.48 0.63 0.72 Pairs with superma- 61.1% 82.2% 71.7% Neutral 0.41 0.54 0.6 jority agreement Overall 0.43 0.6 0.7 Table 2: Summary statistics from the AMT HITs. Table 3: Comparison of Fleiss’ κ scores with scores from SNLI quality control sentence pairs. factor 3PL models to conﬁrm our assumption and the unidimensional structure underlying these items, We believe that the items selected for analysis assuming the possible presence of guessing in peo- are appropriate for our task in that we chose high- ple’s responses. We further tested the guessing pa- quality items, where at least 4 annotators selected rameter of each item in the one factor 3PL model. If the same label, indicating a strong level of agree- the guessing parameter was not signiﬁcantly differ- ment (Section ). We argue that our sample is a ent from 0, a 2PL ICC was used for that particular high-quality portion of the dataset, and further anal- item. ysis of items where the gold-standard label was only Once an appropriate model structure was deter- selected by 3 annotators originally would result in mined, individual items were evaluated for goodness § lower levels of agreement. of ﬁt within the model ( ). If an item was deemed Table 3 shows that the level of agreement as mea- to ﬁt the ICC poorly or to give rise to local depen- dence, it was removed for violating model assump- sured by the Fleiss’ κ score is much lower when the number of annotators is increased, particularly for tions. Furthermore, if the ICC of an item was too the 4GS set of sentence pairs, as compared to scores ﬂat, it was removed for low discriminating power noted in Bowman et al. (2015). The decrease in between ability levels. The model was then reﬁt with agreement is particularly large with regard to con- the remaining items. This iterative process contin- tradiction. This could occur for a number of rea- ued until no item could be removed (2 to 6 iterations sons. Recognizing entailment is an inherently dif- depending on how many items were removed from ﬁcult task, and classifying a correct label, particu- each set). larly for contradiction and neutral, can be difﬁcult The remaining items make up our ﬁnal test set due to an individual’s interpretation of the sentences (GS ), which is a calibrated scale of ability to IRT and assumptions that an individual makes about the correctly identify the relationship between the two key facts of each sentence (e.g. coreference). It may sentence pairs. Parameters of these items were esti- also be the case that the individuals tasked with cre- mated as part of the IRT model and the set of items ating the sentence pairs on AMT created sentences can be used as an evaluation scale to estimate ability that appeared to contradict a premise text, but can be of test-takers or RTE systems. We used the mirt R interpreted differently given a different context. package (Chalmers et al., 2015) for our analyses. 4 Results Before ﬁtting the IRT models we performed a vi- sual inspection of the 180 sentence pairs and re- 4.1 Response Statistics moved items clearly not suitable for an evaluation Table 2 lists key statistics from the AMT HITs. scale due to syntactic or semantic discrepancies. For Most of the sampled sentence pairs resulted in a gold example item 10 in Table 1 was removed from the standard label being identiﬁed via a majority vote. 5GS contradiction set for semantic reasons. While Due to the large number of individuals providing la- many people would agree that the statement is a con- bels during the HIT, we also wanted to see if a gold tradiction due to the difference between football and standard label could be determined via a two-thirds soccer, individuals from outside the U.S. would pos- supermajority vote. We found that 28.3% of the sen- sibly consider the two to be synonyms and classify tence pairs did not have a supermajority gold label. this as entailment. Six such pairs were identiﬁed This highlights the ambiguity associated with iden- and removed from the set of 180 items, leaving 174 tifying entailment. items for IRT model-ﬁtting. ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

label: table

text: Overall

text: Fleiss’

text: κ

text: Bowman

text: et

text: al.

text: Pairs

text: with

text: majority

text: Contradiction

text: agreement

text: Entailment

text: Pairs

text: with

text: superma-

text: Neutral

text: jority

text: agreement

text: Overall

text: Table

text: Summary

label: caption

text: statistics

text: from

text: the

text: AMT

text: HITs.

text: Table

text: Comparison

text: of

text: Fleiss’

text: κ

text: scores

text: with

text: scores

text: from

text: SNLI

text: quality

text: control

text: sentence

text: pairs.

text: factor

text: models

text: to

text: conﬁrm

text: our

text: assumption

text: and

text: the

text: unidimensional

text: structure

text: underlying

text: these

text: items,

text: We

text: believe

text: that

text: the

text: items

text: selected

text: for

text: analysis

text: assuming

text: the

text: possible

text: presence

text: of

text: guessing

text: in

text: peo-

text: are

text: appropriate

text: for

text: our

text: task

text: in

text: that

text: we

text: chose

text: high-

text: ple’s

text: responses.

text: We

text: further

text: tested

text: the

text: guessing

text: pa-

text: quality

text: items,

text: where

text: at

text: least

text: annotators

text: selected

text: rameter

text: of

text: each

text: item

text: in

text: the

text: one

text: factor

text: model.

text: If

text: the

text: same

text: label,

text: indicating

text: a

text: strong

text: level

text: of

text: agree-

text: the

text: guessing

text: parameter

text: was

text: not

text: signiﬁcantly

text: differ-

text: ment

text: (Section

text: We

text: argue

text: that

text: our

text: sample

text: is

text: a

text: ent

text: from

text: a

text: ICC

text: was

text: used

text: for

text: that

text: particular

text: high-quality

text: portion

text: of

text: the

text: dataset,

text: and

text: further

text: anal-

text: item.

text: ysis

text: of

text: items

text: where

text: the

text: gold-standard

text: label

text: was

text: only

text: Once

text: an

text: appropriate

text: model

text: structure

text: was

text: deter-

text: selected

text: by

text: annotators

text: originally

text: would

text: result

text: in

text: mined,

text: individual

text: items

text: were

text: evaluated

text: for

text: goodness

text: lower

text: levels

text: of

text: agreement.

text: of

text: ﬁt

text: within

text: the

text: model

text: If

text: an

text: item

text: was

text: deemed

text: Table

text: shows

text: that

text: the

text: level

text: of

text: agreement

text: as

text: mea-

text: to

text: ﬁt

text: the

text: ICC

text: poorly

text: or

text: to

text: give

text: rise

text: to

text: local

text: depen-

text: dence,

text: it

text: was

text: removed

text: for

text: violating

text: model

text: assump-

text: sured

text: by

text: the

text: Fleiss’

text: κ

text: score

text: is

text: much

text: lower

text: when

text: the

text: number

text: of

text: annotators

text: is

text: increased,

text: particularly

text: for

text: tions.

text: Furthermore,

text: if

text: the

text: ICC

text: of

text: an

text: item

text: was

text: too

text: the

text: set

text: of

text: sentence

text: pairs,

text: as

text: compared

text: to

text: scores

text: ﬂat,

text: it

text: was

text: removed

text: for

text: low

text: discriminating

text: power

text: noted

text: in

text: Bowman

text: et

text: al.

text: The

text: decrease

text: in

text: between

text: ability

text: levels.

text: The

text: model

text: was

text: then

text: reﬁt

text: with

text: agreement

text: is

text: particularly

text: large

text: with

text: regard

text: to

text: con-

text: the

text: remaining

text: items.

text: This

text: iterative

text: process

text: contin-

text: tradiction.

text: This

text: could

text: occur

text: for

text: a

text: number

text: of

text: rea-

text: ued

text: until

text: no

text: item

text: could

text: be

text: removed

text: to

text: iterations

text: sons.

text: Recognizing

text: entailment

text: is

text: an

text: inherently

text: dif-

text: depending

text: on

text: how

text: many

text: items

text: were

text: removed

text: from

text: ﬁcult

text: task,

text: and

text: classifying

text: a

text: correct

text: label,

text: particu-

text: each

text: set).

text: larly

text: for

text: contradiction

text: and

text: neutral,

text: can

text: be

text: difﬁcult

text: The

text: remaining

text: items

text: make

text: up

text: our

text: ﬁnal

text: test

text: set

text: due

text: to

text: an

text: individual’s

text: interpretation

text: of

text: the

text: sentences

text: (GS

text: which

text: is

text: a

text: calibrated

text: scale

text: of

text: ability

text: to

text: IRT

text: and

text: assumptions

text: that

text: an

text: individual

text: makes

text: about

text: the

text: correctly

text: identify

text: the

text: relationship

text: between

text: the

text: two

text: key

text: facts

text: of

text: each

text: sentence

text: (e.g.

text: coreference).

text: It

text: may

text: sentence

text: pairs.

text: Parameters

text: of

text: these

text: items

text: were

text: esti-

text: also

text: be

text: the

text: case

text: that

text: the

text: individuals

text: tasked

text: with

text: cre-

text: mated

text: as

text: part

text: of

text: the

text: IRT

text: model

text: and

text: the

text: set

text: of

text: items

text: ating

text: the

text: sentence

text: pairs

text: on

text: AMT

text: created

text: sentences

text: can

text: be

text: used

text: as

text: an

text: evaluation

text: scale

text: to

text: estimate

text: ability

text: that

text: appeared

text: to

text: contradict

text: a

text: premise

text: text,

text: but

text: can

text: be

text: of

text: test-takers

text: or

text: RTE

text: systems.

text: We

text: used

text: the

text: mirt

text: R

text: interpreted

text: differently

text: given

text: a

text: different

text: context.

text: package

text: (Chalmers

text: et

text: al.,

text: for

text: our

text: analyses.

text: Results

text: Before

text: ﬁtting

text: the

text: IRT

text: models

text: we

text: performed

text: a

text: vi-

text: sual

text: inspection

text: of

text: the

text: sentence

text: pairs

text: and

text: re-

text: Response

text: Statistics

text: moved

text: items

text: clearly

text: not

text: suitable

text: for

text: an

text: evaluation

text: Table

text: lists

text: key

text: statistics

text: from

text: the

text: AMT

text: HITs.

text: scale

text: due

text: to

text: syntactic

text: or

text: semantic

text: discrepancies.

text: For

text: Most

text: of

text: the

text: sampled

text: sentence

text: pairs

text: resulted

text: in

text: a

text: gold

text: example

text: item

text: in

text: Table

text: was

text: removed

text: from

text: the

text: standard

text: label

text: being

text: identiﬁed

text: via

text: a

text: majority

text: vote.

text: contradiction

text: set

text: for

text: semantic

text: reasons.

text: While

text: Due

text: to

text: the

text: large

text: number

text: of

text: individuals

text: providing

text: la-

text: many

text: people

text: would

text: agree

text: that

text: the

text: statement

text: is

text: a

text: con-

text: bels

text: during

text: the

text: HIT,

text: we

text: also

text: wanted

text: to

text: see

text: if

text: a

text: gold

text: tradiction

text: due

text: to

text: the

text: difference

text: between

text: football

text: and

text: standard

text: label

text: could

text: be

text: determined

text: via

text: a

text: two-thirds

text: soccer,

text: individuals

text: from

text: outside

text: the

text: U.S.

text: would

text: pos-

text: supermajority

text: vote.

text: We

text: found

text: that

text: of

text: the

text: sen-

text: sibly

text: consider

text: the

text: two

text: to

text: be

text: synonyms

text: and

text: classify

text: tence

text: pairs

text: did

text: not

text: have

text: a

text: supermajority

text: gold

text: label.

text: this

text: as

text: entailment.

text: Six

text: such

text: pairs

text: were

text: identiﬁed

text: This

text: highlights

text: the

text: ambiguity

text: associated

text: with

text: iden-

text: and

text: removed

text: from

text: the

text: set

text: of

text: items,

text: leaving

text: tifying

text: entailment.

text: items

text: for

text: IRT

text: model-ﬁtting.

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##