# Prove $O(\frac{1}{T})$ convergence rate

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.

• 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. – Matt Apr 19 at 20:13
• 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. – Dushyant Sahoo Apr 19 at 20:16
• 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? – Alex Ravsky Apr 25 at 10:51
• Yes, you are right – Dushyant Sahoo Apr 25 at 17:58
• It is for all $T \geq 0$ – 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$$.