1
$\begingroup$

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}

$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$ Jan 13 at 13:48
  • $\begingroup$ @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$. $\endgroup$
    – user550103
    Jan 13 at 15:06
  • $\begingroup$ Also, what are $x_k$, $x^*$, $\|\cdot\|$? $\endgroup$ Jan 13 at 17:57
  • $\begingroup$ 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? $\endgroup$
    – user550103
    Jan 13 at 18:09
  • 1
    $\begingroup$ So, a priori $(x_k)$ can be any sequence in $\mathbb R^d$ (?) and $x^*$ any vector in $\mathbb R^d$, right? $\endgroup$ Jan 13 at 18:16

1 Answer 1

1
+100
$\begingroup$

$\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} $$

enter image description here

$\endgroup$
9
  • $\begingroup$ 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"... $\endgroup$
    – user550103
    Jan 14 at 7:24
  • $\begingroup$ 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? $\endgroup$
    – user550103
    Jan 14 at 7:33
  • 1
    $\begingroup$ @user550103 : I certainly understand your frustration, especially after sacrificing 100 points of your reputation but getting a no-no-no answer. It was to be expected that some condition(s) are missing in your post. In my comments to your post, I did try (thrice) to help you add obviously missing conditions. After that, I spent a substantial amount of time to come up with the above answer, which points out to the neeed in some further, less obviously missing conditions. As such, this answer to your questions is complete. So, let us have a closure here. $\endgroup$ Jan 14 at 14:01
  • $\begingroup$ Previous comment continued: After that, you may want to further research literature and come up with working additional conditions. $\endgroup$ Jan 14 at 14:01
  • 1
    $\begingroup$ @user550103 : The conditions in those papers probably do not explicitly exclude such oscillations. However, perhaps you can check which of those conditions fail to hold in the above counterexample. Then you can add such conditions or similar ones, hopefully to rule out oscillations. This may be a specific way to utilize the counterexample. $\endgroup$ Jan 14 at 16:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.