# Assumption on Mirror Descent convergence?

I am studying Mirror descent and nonlinear projected subgradient methods. At page 171 Theorem 4.1., the author claims that the method converges provided $$\sum_s t_s= \infty , \,\,\,t_k \rightarrow 0 \,\,\,\,\,\text{as} \,\,\,\ k \rightarrow \infty$$ beacuse the right hand side of the following goes to zero:

$$\min_{1\leq s \leq k} f(x^s) - \min_{x \in X} f(x) \leq \frac{B_{\psi(x^*,x^1)}+(2\sigma)^{-1}\sum_{s=1}^kt_s^2\|f'(x^k)\|_*^2}{\sum_{k=1}^s t_s}$$

My question is that how we know $$\sum_{s=1}^kt_s^2\|f'(x^k)\|_*^2$$ is bounded provided aforementioned assumption? Although $$t_k \rightarrow 0$$ does not guarantee that $$\sum_{s=1}^kt_s^2\|f'(x^k)\|_*^2$$ is bounded.

Section (b) of Assumption A states that $$f$$ is $$L_f$$-Lipschitz. A standard result of optimization asserts that if $$f'(x)\in \partial f(x)$$, then $$\|f'(x)\|_*\leq L_f$$ where $$\|\cdot\|_*$$ denotes the dual norm of $$\|\cdot\|$$.

Thus $$\displaystyle \frac{\sum_{k=1}^n t_k^2\|f'(x^k)\|_*^2}{\sum_{k=1}^n t_k}\leq L_f\frac{\sum_{k=1}^n t_k^2}{\sum_{k=1}^n t_k}$$.

Let us show that $$\displaystyle \frac{\sum_{k=1}^n t_k^2}{\sum_{k=1}^n t_k} \to 0$$. Remember that the $$t_n$$ are $$\geq 0$$.

Let $$\epsilon >0$$. There exists $$N$$ such that $$n\geq N\implies t_n\leq \epsilon$$. For $$n\geq N$$, $$\sum_{k=1}^n t_k^2\leq \sum_{k=1}^N t_k^2 + \epsilon \sum_{k=N+1}^n t_k$$ The sequence $$\displaystyle \epsilon \sum_{k=N+1}^n t_k$$ (indexed by $$n$$) diverges to $$\infty$$, so there exists some $$N'>N$$ such that $$n\geq N' \implies \sum_{k=1}^N t_k^2\leq\epsilon \sum_{k=N+1}^n t_k$$ For $$n\geq N'$$, $$\sum_{k=1}^n t_k^2\leq 2\epsilon \sum_{k=N+1}^n t_k\leq 2\epsilon \sum_{k=1}^n t_k$$ and we're done.

• Thank you so much. It was very instructive. – Saeed May 17 at 23:37

You don't have that $$\sum_{s=1}^k t_s^2 \lVert f'(x^k)\rVert^2$$ is bounded. However, for any series $$\sum_{s=1}^\infty a_s$$ that diverges, but the summands converge to zero, you have that $$\frac{\sum_{s=1}^k a_s^2}{\sum_{s=1}^k a_s} \to 0, \quad \text{for k\to\infty}.$$ You can find this for example here.

So in fact, it doesn't really have anything to do with optimization (and just as a comment: it's not really relevant for the paper).

• I do not have $\frac{\sum_{s=1}^k a_s^2}{\sum_{s=1}^k a_s}$, I have $\frac{\sum_{s=1}^k a_s^2b_k^2}{\sum_{s=1}^k a_s}$ where $b_k^2$ is the dual norm of the gradient. How would you handle that? – Saeed May 16 at 2:29
• Also, on the cited question, we have have sum of the $a_n$ at the denominator. – Saeed May 16 at 2:34
• The gradient is bounded though so you effectively do have the series they posted... – Tony S.F. May 16 at 8:17