Problem -
Consider a closed convex set X ⊂ Rd, a function H : X x Ξ ι→ Rd, and a deterministic nonnegative sequence {αn} such that n=0∑∞αn = ∞ and n=0∑∞(αn)2 = ∞. Consider an inner product (·, ·) on Rd, and the associated norm ||x|| := √(x, x). Let ΠX(x) := argmin {||x - y|| : y ∈ X} denote the corresponding projection of x onto X. Consider a discrete time stochastic process {xn, ξn} such that for all n = 1, 2, ...,
xn+1 = ΠX(xn + αnH(xn, ξn+1))
Let Fn denote the σ-algebra generated by x0, ξ1, . . . , ξn. Suppose that for each x ∈ X there is a probability distribution, μx on Ξ such that for any function g : X x Ξ ι→ R,
E[g(xn, ξn+1)|Fn] = ∫Ξ g(xn, ξ)μx^n(dξ)
that is, given the history of the stochastic process up to time n, the distribution of ξn+1 depends only on xn. Let
h(x) := ∫Ξ H (x, ξ) μx(dξ)
that is, h(xn) = E[H(xn, ξn+1)|Fn]. Suppose that there is a constant K such that
∫Ξ||H(x, ξ)||2μx(dξ) < K (1 + ||x||2)
for all x ∈ X. Suppose that there is a x* ∈ X such that, for all ε > 0,
inf{(h(x), x* - x ) : ε ≤ ||x* - x|| ≤ 1/ε} > 0
You can use the supermartingale convergence theorem established in class without having to prove it. You can also use the following result without having to prove it: For any x, y ∈ Rd, it holds that
||ΠX(x) - ΠX(y)|| ≤ ||x - y||
1. Prove or disprove: w.p.1, xn → x* as n → ∞.
2. Prove or disprove: w.p.1, h(xn) → 0 as n → ∞.
Note - Do your own work. Show all calculations.