Suppose we have the following first-order non-homogeneous recurrence relation $$z_{t+1} \leq \frac{1}{(1+b_1c_t)^2}\big(\left(1+b_2c_t^2 \right)z_t + b_3c_t^2\big) $$

where $t$ is an integer which varies from 0 to $T$, and $b_1$, $b_2$ and $b_3$ are constants which are greater than 0. In the above equation $z_t = \|w_{t+1} - w^{\star}\|$ i.e. above equation shows a relation about how fast is $w_t$ decreasing and will reach to $w^{\star}$. I am trying that the I wanted to solve for $z_T$ such that convergence of $w$ to $w^{\star}$ is $O(\frac{1}{T})$ which can be also written as- $$z_T \leq \frac{d}{T}z_0 + e $$ where $d$ and $e$ are some constants. Is there a way to bound $c_t, b_1, b_2$ and $b_3$ such that the above equation becomes true? I am not sure how to solve the above equation, any pointers would be really helpful.

  • $\begingroup$ Do you get to choose $c_t$, $b_1$, $b_2$, and $b_3$? Or are they given? If $c_t$ is constant in time, then the convergence is exponential, so it is not clear why you are considering $O(\frac{1}{T})$ convergence. $\endgroup$ – Matt Apr 19 at 20:13
  • $\begingroup$ I get to choose $c_t$. I was thinking of choosing $c_t$ such that it decreases exponentially in time, but that didn't help. $\endgroup$ – Dushyant Sahoo Apr 19 at 20:16
  • $\begingroup$ So we have a freedom to choose any sequence $\{c_t\}$ of positive reals but then we need to show that for any given positive $z_0$, we have $z_T \leq \frac{d}{T}z_0 + e $, right? $\endgroup$ – Alex Ravsky Apr 25 at 10:51
  • $\begingroup$ Yes, you are right $\endgroup$ – Dushyant Sahoo Apr 25 at 17:58
  • 1
    $\begingroup$ It is for all $T \geq 0$ $\endgroup$ – Dushyant Sahoo Apr 27 at 6:44

The answer is positive. Given $b_i$, for simplicity put $c_t=\tfrac 1{b_1t}$ for each $t>0$. Pick any $t\ge\tfrac{2b_2}{b_1^2}$ and any $A\ge \frac{2b_3}{b_1^2}$ such that $z_t\le\tfrac At$. Now it suffices to show that $z_{t+1}\le\tfrac A{t+1}$ and then conclude by induction. It remains to check that $$\frac A{t+1}\ge \frac 1{\left(1+\tfrac 1t\right)^2}\left(\left(1+\frac {b_2}{b_1^2t^2}\right)\frac At+\frac {b_3}{b_1^2t^2}\right)$$ $$\frac A{t+1}\ge \frac 1{t(1+t)^2}\left(At^2+\frac {b_2A}{b_1^2}+\frac{b_3}{b_1^2}t\right)$$

$$At(t+1)\ge At^2+\frac {b_2A}{b_1^2}+\frac{b_3}{b_1^2}t$$

$$At\ge \frac t2A+\frac A2t \ge \frac {b_2}{b_1^2}A+\frac{b_3}{b_1^2}t,$$

which holds by our choice of $t$ and $A$.


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.