www-ai.cs.tu-dortmund.de/LEHRE/VORLESUNGEN/LOPT/SS16/papers/NemJ09.pdf
P:\TEX\SIOPT\19-4\70427\70427.dvi
> 1/(2c). Then, by (2.8), we have
aj+1 ≤ (1 − 2cθ/j)aj + 1 2 θ2M2/j2.
It follows by induction that
(2.9) E [‖xj − x∗‖2
2
] = 2aj ≤ Q(θ)/j,
where
(2.10) Q(θ) = max { θ2M2(2cθ − 1)−1, ‖x1 − x∗‖2
2
} .
Suppose [...] y)‖ =
√ ‖x‖2
x
2R2 x
+ ‖y‖2
1
2R2 y
,
and hence
‖(ζ, η)‖∗ = √
2R2 x‖ζ‖2∗,x + 2R2
y‖η‖2∞.
Let us assume uniform bounds:
max 1≤i≤m
E [‖Gi(x, ξ)‖2
∗,x
] ≤ M2 ∗,x, E
[ max
1≤i≤m |Fi(x, ξ)|2
] ≤ M2
∗,y, i = 1 [...] ex ≤ x + ex2
) E[exp{γζt}|ξ[t−1]] ≤ E[exp
{ γ2ζ2
t
} |ξ[t−1]]
≤ E
[( exp { ζ2 t /σ2
t
})γ2σ2 t |ξ[t−1]
] ≤ exp
{ γ2σ2
t
} ;
γσt > 1 ⇒ E[exp{γζt}|ξ[t−1]] ≤ E
[ exp { [ 1 2 γ2σ2
t + 1 2 ζ2 t /σ2
t
} |ξ[t−1] …
