Problem $3$

Given a dataset $S_n=\{z_1,$dots,$z_n\}subZ$ and a sequence of indices $\{i_0,i_1,$dots,$i_{T-1}\}sub\{1,$dots,$n\},$

define the sequence of iterates $\{{}_t{\}}_t=0^{T}sub{R}^d$ by the update rule:

${}_{t+1}=G({}_t,z_{i_t}),{}_0=0.$

Here, $G$:$R^{d}Z|R^d$ is an abstract update rule obeying two properties:

$($a$)$ There exists an $in(0,1)$ such that for all $u,vin{R}^d$ and zinZ,

$||G(u,z)-G(v,z)||(1-)||u-v||,$

$($b$)$ There exists an $M>0$ such that for all $uin{R}^d$ and $z_1,z_2$inZ,

$||G(u,z_1)-G(u,z_2)||M.$

Let $A(S_n,)$:$={}_T.$ Show that, if $=\{i_t{\}}_t=0^{T-1}$ is sampled with each $i_t$ drawn independently from

Unif$(\{1,$dots,$n\}),$ then:

$su{p}_{S_n,S_n^{\text{'}}}{E}_{}||A(S_n,)-A(S_n^{\text{'}},)||\frac{M}{n},$

where the supremum over $S_n,S_n^{\text{'}}$subZ is over datasets of length $n$ which differ in one example.