Proving convergence of projected subgradient descent

Question

Any idea how to sum the series $\sum_{t=1}^T \frac{1}{\sqrt{t}} (\|x_t -a\|^2 -\|x_{t+1}-a\|^2) $, where $a$ is any constant and you can assume $\|x_{T+1}-a\|=0$. This sum occured in proving convergence of projected subgradient descent with time-varying step size.

Answer 1

I have used such things before in work I've done. We get: \begin{align} &\sum_{t=1}^T \frac{1}{\sqrt{t}}(||x_t-a||^2 - ||x_{t+1}-a||^2) \\ &= ||x_1-a||^2 - \frac{1}{\sqrt{T}}||x_{T+1}-a||^2 + \sum_{t=2}^{T}||x_t-a||^2\left(\frac{1}{\sqrt{t}}-\frac{1}{\sqrt{t-1}}\right) \\ &\leq ||x_1-a||^2 - \frac{1}{\sqrt{T}}||x_{T+1}-a||^2 \end{align}