Problem: Consider the unconstrained optimization problem $\min _{\mathbf{x} \in \mathbb{R}^d} f(\mathbf{x})$, where $f$ is an $L$-smooth convex function. Assume that $\left\|\mathbf{x}_0-\mathbf{x}^*\right\|_2 \leq R$, for some $R \in(0, \infty)$, and let $f_\epsilon(\mathbf{x})=f(\mathbf{x})+\frac{\epsilon}{2 R^2}\left\|\mathbf{x}-\mathbf{x}_0\right\|_2^2$. Let $\mathbf{x}^*=\operatorname{argmin}_{\mathbf{x} \in \mathbb{R}^d} f(\mathbf{x})$ and $\mathbf{x}_\epsilon^*=\operatorname{argmin}_{\mathbf{x} \in \mathbb{R}^d} f_\epsilon(\mathbf{x})$. Prove that: $$ \left(\forall \mathbf{x} \in \mathbb{R}^d\right): f(\mathbf{x})-f\left(\mathbf{x}^*\right) \leq f_\epsilon(\mathbf{x})-f_\epsilon\left(\mathbf{x}_\epsilon^*\right)+\frac{\epsilon}{2} . $$
Prove that standard gradient descent applied to function $f_\epsilon$ finds a point $\mathbf{x}_k$ with $f\left(\mathbf{x}_k\right)-f\left(\mathbf{x}^*\right) \leq \epsilon$ in $O\left(\frac{L}{\epsilon} R^2 \log \left(\frac{L R^2}{\epsilon}\right)\right)$ iterations. How does this compare to applying gradient descent directly to $f$ ?
Here is an answer for the first part.
From the definition we have $f_\epsilon(x)-f(x) = {\epsilon \over 2R^2} \|x-x_0\|^2 $ and since $f_\epsilon(x_\epsilon^*) \le f_\epsilon(x)$ we have $f_\epsilon(x_\epsilon^*) - f(x^*) \le {\epsilon \over 2R^2} \|x^*-x_0\|^2 \le {\epsilon \over 2}$.
Hence \begin{eqnarray} f_\epsilon(x_\epsilon^*) - f(x^*) &\le& f_\epsilon(x_\epsilon^*) - f(x^*) + {\epsilon \over 2R^2} \|x-x_0\|^2 \\ &=& f_\epsilon(x_\epsilon^*) - f(x^*) + f_\epsilon(x)-f(x) \\ &\le& f_\epsilon(x)-f(x) + {\epsilon \over 2} \end{eqnarray} and rearranging yields the desired result.
For the second part, note that $f_\epsilon$ is $L+ {\epsilon \over R^2}$-smooth and ${\epsilon \over R^2}$ strongly convex. A bit of grind shows that $f_\epsilon(x_0) - f_\epsilon(x_\epsilon^*) \le {L \over 2} R^2$.