Perhaps stupid question.



> 
> **Question**: Can "almost supermartingale" theorem be equally applicable to prove the convergence of some algorithms solving non-random optimization problems?
> 
> 
> 


Attempt for a non-random version of "almost supermartingale" theorem (without any proof):



> 
> Let the non-negative sequences be $\{V^k\}$, $\{S^k\}$, and $\{ U^k \}$ for $k=0,1,2,\ldots$. Let $\beta\_0, \beta\_1$ be non-negative scalars satisfying $\sum\_{k=0}^\infty \beta\_k < \infty$. Assume
> $$V^{k+1} \leq \left( 1 + \beta\_k \right) V^k - S^k + U^k$$
> and
> $$\sum\_{i={\color{red}{0 \text{ or } 1?}}}^\infty U^i < \infty.$$
> Then,
> 
> 
> 1. $V^k \rightarrow V^\infty$
> 2. $\sum\_{k=0}^\infty S^k < \infty$.
> 
> 
> 




---


EDIT:


Additionally, let
$V^k := \| x^k - x^\star \|\_P^2$ where $P$ is a positive semidefinite matrix. Then, using the above theorem, can one say for a subsequence $n\_k$ $\lim\_{k \rightarrow \infty} x^{n\_k} = x^\star$? or do we need more information to prove this?




---


For the completeness, I have also copied the "almost supermartingale" theorem from [[Theorem 30, page 300]](https://large-scale-book.mathopt.com/LSCOMO.pdf).



> 
> **Theorem**: Let $V^k$, $S^k$, and $ U^k$ be $\mathcal{F}\_k$-measurable random variables satisfying $V^k \geq 0$, $S^k \geq 0$, and $ U^k\geq 0$ for $k=0,1,2,\ldots$. Let $\beta\_0, \beta\_1$ be non-negative scalars satisfying $\sum\_{k=0}^\infty \beta\_k < \infty$.
> Assume
> $$\mathbb{E}\left[V^{k+1} \mid \mathcal{F}\_k \right] \leq \left( 1 + \beta\_k \right) V^k - S^k + U^k$$
> and
> $$\sum\_{i={\color{red}{0 \text{ or } 1?}}}^\infty U^i < \infty$$
> almost surely. Then,
> 
> 
> 1. $V^k \rightarrow V^\infty$
> 2. $\sum\_{k=0}^\infty S^k < \infty$.
> 
> 
> 



Can we invoke "almost supermartingale" Theorem for deterministic sequences?
For $k=0,1,\dots$, let $v\_k:=V^k$, $s\_k:=S^k$, $u\_k:=U^k$, and $b\_k:=\beta\_k$, so that the $v\_k$'s, $s\_k$'s, $u\_k$'s, and $b\_k$'s are nonnegative real numbers such that $\sum\_{k=0}^\infty b\_k<\infty$,
\begin{equation\*}
 \sum\_{k=0}^\infty u\_k<\infty, \tag{1}
\end{equation\*}
and
\begin{equation\*}
 v\_{k+1}\le c\_k v\_k-s\_k+u\_k \tag{2}
\end{equation\*}
for all $k$, where
\begin{equation\*}
 c\_k:=1+b\_k\ge1,
\end{equation\*}
so that
\begin{equation\*}
 \prod\_{k=0}^\infty c\_k \text{ converges (to a number in $[1,\infty)$).} \tag{3}
\end{equation\*}


It follows by (2) that $v\_{k+1}\le c\_k v\_k+u\_k$ for all $k$ and hence, by induction on $k$,
\begin{equation\*}
 v\_k\le\Big(v\_0+\sum\_{j=0}^{k-1}u\_j\Big)\prod\_{j=0}^{k-1}c\_j \tag{4}
\end{equation\*}
and hence
\begin{equation\*}
 0\le v\_k\le M:=\Big(v\_0+\sum\_{j=0}^\infty u\_j\Big)\prod\_{j=0}^\infty c\_j<\infty. \tag{5}
\end{equation\*}


Similarly to (4),
\begin{equation\*}
 v\_k\le\Big(v\_n+\sum\_{j=n}^{k-1}u\_j\Big)\prod\_{j=n}^{k-1}c\_j \tag{6}
\end{equation\*}
for any natural $k$ and $n$ such that $k>n$. Therefore,
\begin{equation\*}
 \limsup\_{k\to\infty}v\_k\le\Big(v\_n+\sum\_{j=n}^\infty u\_j\Big)\prod\_{j=n}^\infty c\_j 
\end{equation\*}
and hence, in view of (1) and (3),
\begin{equation\*}
 \limsup\_{k\to\infty}v\_k\le\big(\liminf\_{n\to\infty}v\_n+0\big)\times1
 = \liminf\_{n\to\infty}v\_n. 
\end{equation\*}
So, in view of (5), there exists
\begin{equation\*}
 v\_\infty:=\lim\_{k\to\infty}v\_k\in[0,M|\subset[0,\infty). \tag{7}
\end{equation\*}


Similarly to (4), for all $k$
\begin{equation\*}
 v\_k\le\Big(v\_0+\sum\_{j=0}^{k-1}u\_j\Big)\prod\_{j=0}^{k-1}c\_j - \sum\_{j=0}^{k-1}s\_j,
\end{equation\*}
whence
\begin{equation\*}
 \sum\_{j=0}^{k-1}s\_j\le\Big(v\_0+\sum\_{j=0}^{k-1}u\_j\Big)\prod\_{j=0}^{k-1}c\_j.
\end{equation\*}
Letting now $k\to\infty$ and recalling (1) and (3), we see that
\begin{equation\*}
 \sum\_{j=0}^\infty s\_j<\infty. \tag{8}
\end{equation\*}


Relations (7) and (8) are what was desired.


