Convergence analysis of Optimisation algorithms using Regret Bound.

Question

I was reading a research paper https://arxiv.org/pdf/1707.01647.pdf which talked about the convergence analysis of different Machine learning optimisation algorithms (in convex domain). i am not able to understand how finding an upper bound for the Regret bound guarantees that the algorithm will converge?

Answer 1

Let $\{d_k\}_{k=1}^{\infty} = f(x^k)-f(x^*)$. Then if $\sum_{k=1}^{\infty}d_k$ is bounded, the tail of the sequence must have value of zero. That is, as $k\to\infty$ we have $\{f(x^k)- f(x^*)\}\to 0$.

Detailed proof on the last statement can be found here: If a series converges, then the sequence of terms converges to 0.