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

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}

• With $\alpha_k$ and $\gamma_k$ being unspecified nonnegative real numbers, you have $v_k$ and $t_k$ as unspecified nonnegative real numbers, except that they are related by ($\clubsuit$). So, hardly anything can be said about $v_k$ and $t_k$. Some additional conditions on $\alpha_k$ and $\gamma_k$ may be useful. Jan 13 at 13:48
• @IosifPinelis Thank you very much for your reply. I am sorry for missing out some details on $\alpha_k$ and $\gamma_k$. I can say that $\alpha_k$ and $\gamma_k$ is monotonically decreasing over increasing $k$, i.e., $\alpha_{k+1} \leq \alpha_{k}$ and $\gamma_{k+1} \leq \gamma_{k}$. The supremum of both $\{\alpha_k\}$ and $\{ \gamma_k\}$ is less than infinity. Please let me know what additional assumption would be needed on $\alpha_k$ and $\gamma_k$. Jan 13 at 15:06
• Also, what are $x_k$, $x^*$, $\|\cdot\|$? Jan 13 at 17:57
• Oops, $\{x_k\}$ are the sequences generated by a convex optimization algorithm and $x^{*}$ is an optimal solution. We can assume Euclidean norm $\| \cdot \|_2$. Is that enough information or am I still goofing up? Jan 13 at 18:09
• So, a priori $(x_k)$ can be any sequence in $\mathbb R^d$ (?) and $x^*$ any vector in $\mathbb R^d$, right? Jan 13 at 18:16

$$\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} • Thank you very much for your reply, Iosif! I see your point, but now I realized that the initialization of $x_0$ should be 'appropriate'. Additionally, most of the papers have proved the convergence of their optimization algorithms using such type of inequalities after summing it to infinity. Then, they argue about "cluster point"... Jan 14 at 7:24
• See, example optimization-online.org/DB_FILE/2017/09/6228.pdf (page 12), arxiv.org/pdf/1504.01032.pdf on page 29 equation (A.3). What am I missing? Jan 14 at 7:33