Banach fixed point theorem with partial averaging

Question

Let $X$ be a Banach space, and let $T : X \to X$ be $\alpha$-Lipschitz for $\alpha < 1$. Let $z_*$ be the fixed point of $T$. Suppose $\{\gamma_t\}_{t=1}^\infty$ be such that $0 < \gamma_t < 1$ for all $t$ and $\sum_t \gamma_t = \infty$. Let $x_0 \in X$ be arbitrary, and for $t \geq 1$, let $x_t = (1 - \gamma_t) x_{t-1} + \gamma_t T x_{t-1}$. Does it hold that $x_t \to z_*$?

Answer 1

The condition $\sum_t \gamma_t = \infty$ is both necessary and sufficient. To see necessity, take $Tx = \alpha x$ for $0 < \alpha < 1$.

For sufficiency, first observe that for any $x \in X$, $\|Tx - z_*\| = \|Tx - Tz_*\| \leq \alpha \|x - z_*\|$. Now, for $t \geq 1$, note that $$\|x_t - z_*\| = \|(1 - \gamma_t) x_{t-1} + \gamma_t T x_{t-1} - z_*\| \leq (1 - \gamma_t) \|x_{t-1} - z_*\| + \gamma_t \|T x_{t-1} - z_*\|$$ $$\leq (1 - \gamma_t) \|x_{t-1} - z_*\| + \gamma_t \alpha \|x_{t-1} - z_*\| = {\big (}1 - (1 - \alpha) \gamma_t{\big )} \|x_{t-1} - z_*\|.$$ By induction, we obtain $$\|x_t - z_*\| \leq {\Big (}\prod\limits_{i=1}^t {\big (} 1 - (1 - \alpha) \gamma_i {\big )} {\Big )} \|x_0 - z_*\|.$$ This product converges to $0$ so long as $\sum_i \gamma_i = \infty$.