Proof of bound an optimal solution of minimum problem with strong convexity and smoothness

Question

I am studying this set of notes. In 1.2 they proof the creation of a ball with the optimal solution (x*) inside. I am having difficulties to undertsand how the betha-strong convexity of f implies the first ball and how the alpha-smoothness implies te second one.

Answer 1

The first result is obtained by completing the square technique. Consider the definition of strong convexity: $$f(y)\geq f(x) + \nabla f(x)^T(y - x) + \frac{\alpha}{2}\|y-x\|^2, \qquad \forall x,y.$$ If you move the inner product inside the norm, you get $$f(y)\geq f(x) + \frac{\alpha}{2}\|y-x + \frac{1}{\alpha}\nabla f(x)\|^2 - \frac{\|\nabla f(x)\|^2}{2\alpha}, \qquad \forall x,y.$$ Rearrangement of terms yields $$\frac{\|\nabla f(x)\|^2}{\alpha^2} -\frac{2}{\alpha}(f(x) - f(y))\geq \|y-x + \frac{1}{\alpha}\nabla f(x)\|^2, \qquad \forall x,y.$$ Now substitution of $y = x^\star$ and $x^{++} = x - \frac{1}{\alpha}\nabla f(x)$ gives $$\frac{\|\nabla f(x)\|^2}{\alpha^2} -\frac{2}{\alpha}(f(x) - f(x^\star))\geq \|x^\star-x^{++}\|^2, \qquad \forall x$$ which implies $$x^\star \in \mathbb{B}\left(x^{++}, \frac{\|\nabla f(x)\|^2}{\alpha^2} -\frac{2}{\alpha}(f(x) - f(x^\star))\right).$$ To obtain the second identity, you need to replace $f(x)$ with its lower bound given in the note.