Proof of extended version of non-random "almost supermartingale"

Question

In this question, a non-random version of "almost supermartingale" theorem is proved.

Here, I would like to extend/apply the non-random version to the slightly different situation. I wonder whether the theorem holds under this extended version case, does it?

Let me define some non-negative variables

\begin{align} v_k &:= \alpha_k\|x_k - x^\star \|_2^2 \\ t_k &:= \gamma_k \|x_k - x_{k-1} \|_2^2 \end{align} where $\alpha_k, \gamma_k \in \mathbb{R}_{+}$.

ADDENDUM1: $\{x_k \!\in \mathbb{R}^d\!\}$ are the sequences generated by a convex optimization algorithm and $x^{\star} \!\in \mathbb{R}^d$ is an optimal solution.

ADDENDUM2: {Both $\alpha_k$ and $\gamma_k$ are monotonically decreasing over increasing $k$, i.e., $\alpha_{k+1} \leq \alpha_{k}$ and $\gamma_{k+1} \leq \gamma_{k}$ forall $k$. The supremum of both $\{\alpha_k\}$ and $\{ \gamma_k\}$ is less than infinity.}}

Let $\beta_k \geq 0$, which satisfy $\sum_{k=0}^\infty \beta_k < \infty$. Also, let $\{s_k\}$ be another non-negative variable.

Assume \begin{align} v_{k+1} + t_{k+1} \leq \left( 1 + \beta_k \right) v_{k} + t_{k} - s_k \tag{$\clubsuit$}, \end{align}

Question: Then, can we extend or/and apply non-random version of "almost supermartingale" theorem (or some other theorem?) to $(\clubsuit)$ such that \begin{align} v_k &\rightarrow v^{\infty} \ \text{or} \ x_k \rightarrow x^{\star} ? \end{align} and \begin{align} t_k &\rightarrow 0 ? \end{align}

Answer 1

$\newcommand\R{\mathbb R}$The answer to each of your three questions is no.

Indeed, suppose that $\alpha_k=\gamma_k=1$ and $\beta_k=s_k=0$ for all $k$. Suppose that the dimension $d$ is $1$ (then the counterexample presented below can be obviously "imbedded" into $\R^d$ for any natural $d$).

Let $x^\star:=0$. Let \begin{equation} (x_0, x_1, x_2, x_3):=(2-\sqrt{5},-1,\sqrt{5}-2,1) \end{equation} and then let \begin{equation} x_k:=x_{k-4} \end{equation} for natural $k\ge4$, so that the sequence $(x_k)_{k\ge0}$ is periodic with period $4$. Hence, the sequences $(v_k)_{k\ge0}=(x_k^2)_{k\ge0}$ and $(t_k)_{k\ge1}=((x_k-x_{k-1})^2)_{k\ge1}$ are also periodic with period $4$, with \begin{equation} (v_1, v_2, v_3,v_4)=(v_1, v_0, v_1,v_0), \end{equation} \begin{equation} (t_1, t_2, t_3,t_4)=(t_1,t_0, t_1,t_0), \end{equation} \begin{equation} v_0=9 - 4\sqrt5,\quad v_1=1,\quad t_0:=6-2\sqrt5,\quad t_1=14 - 6\sqrt5, \end{equation} so that $ v_1+t_1=v_0+t_0$ and hence \begin{equation} v_{k+1} + t_{k+1}=v_k+t_k \tag{$\clubsuit\clubsuit$} \end{equation} for all natural $k$. So, recalling that $\beta_k=s_k=0$ for all $k$, we see that your condition ($\clubsuit$) holds.

However, since each of the sequences $(v_k)_{k\ge0}$, $(x_k)_{k\ge0}$, and $(t_k)_{k\ge1}$ is non-constant and periodic, we see that none of the conditions $v_k\to v^{\infty}$, $x_k \to x^{\star}$, $t_k\to0$ holds.

Remark: If we want the sequence $(v_k)_{k\ge0}$ to be alternating between two different values and if we want $(\clubsuit\clubsuit)$ to hold for all natural $k$, then the sequence $(x_k)_{k\ge0}$ in the above example is uniquely determined up to rescaling (that is, replacing the sequence $(x_k)_{k\ge0}$ by the rescaled sequence $(cx_k)_{k\ge0}$ for some nonzero real $c$) and/or the swapping $x_{2j}$ with $x_{2j+1}$ for all $j=0,1,\dots$, to get the sequence $(x_1,x_0,x_3,x_2,\dots)$.

---

The picture below shows the oscillatory behavior of the periodic sequence $$ \begin{aligned} (x_k)_{k\ge0}&=(x_0, x_1, x_2, x_3, x_0, x_1, x_2, x_3,\dots) \\ &=(x_0, x_1, -x_0, -x_1, x_0, x_1, -x_0, -x_1,\dots)\,: \end{aligned} $$