# Lipschitz Smoothness and Nesterov's Accelerated Gradient Descend

I am reading about Nesterov's Accelerated Gradient Descend, and trying to apply it to my application (Computerised Tomography), which essentially means I am solving a linear problem of the form

$$\hat{x}=\underset{x}{\text{argmin}}\left\{ \lVert Ax-b\rVert^2\right\}$$

Regardless of the complexity of the proof, ultimately the algorithm seems fairly easy to implement, as it is just a slight modification from the classic gradient descend with some specific parameter updates. Nesterov's acceleration ends in an update that looks like:

$$y_{s+1}=x_{x}-\frac{1}{\beta}\nabla f(x_s)\\ x_{s+1}=(1-\gamma_s)y_{s+1}+\gamma_s y_s$$ for iteration number $s$ and $\gamma_s=\frac{1-\lambda_s}{\lambda_{s+1}}$, being $\lambda_S=\frac{1+\sqrt{1+4{\lambda_{s-1}^2}}}{2}$.

However it relies in the $\beta$-smoothness of the function $f$, and $\beta$ is used in as a parameter.

$f$ is $\lVert Ax-b\rVert^2$

What value should I give to $\beta$? How can I know how $\beta$-smooth my function is?

• If you're minimizing $\|Ax-b\|^2$, then isn't $f(x)=\|Ax-b\|^2$ in your case? And $\nabla f(x) = 2 A^T(Ax-b)$. Aug 1, 2017 at 12:07
• As a no-answer to my question: pretty much everyone just uses $\beta=1$ or some similar value. It apparently is not too important what value is given to that variable when doing numerical stuff. Aug 4, 2017 at 12:40
• @littleO the question has been clarified, you're welcome to take a shot at it (my answer wasn't corresponding to the actual question). Aug 4, 2017 at 12:45
• So you want know whether you can choose $\beta=1$ as an upper bound for the $\beta$ that satisfy $\Vert \nabla f(x) - \nabla f(y) \Vert = \Vert 2 A^t A (x-y) \Vert \leq \beta \Vert x-y\Vert \forall x,y$ ? Aug 4, 2017 at 12:56

The gradient of $f$ is $\nabla f(x) = 2 A^T(Ax-b)$. To use Nesterov's method we need a Lipschitz constant for $\nabla f$ (not $f$). Notice that \begin{align} \| \nabla f(x)-\nabla f(y) \| &= \|2 A^T A(x-y) \| \\ &\leq 2 \| A^T A \| \|x-y\| \\ &= 2 \| A\|^2 \|x-y\|^2. \end{align} So a Lipschitz constant for $\nabla f$ is $$\beta= 2 \|A\|^2.$$
• So this $\beta = 2\Vert A \Vert^2$ is an upper bound could it be that there might actually be a lower $\beta$ than your suggested one? Aug 8, 2017 at 14:28