4
$\begingroup$

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?

$\endgroup$
4
  • 2
    $\begingroup$ 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)$. $\endgroup$
    – littleO
    Aug 1, 2017 at 12:07
  • $\begingroup$ 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. $\endgroup$ Aug 4, 2017 at 12:40
  • $\begingroup$ @littleO the question has been clarified, you're welcome to take a shot at it (my answer wasn't corresponding to the actual question). $\endgroup$ Aug 4, 2017 at 12:45
  • $\begingroup$ 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$ ? $\endgroup$
    – flawr
    Aug 4, 2017 at 12:56

1 Answer 1

1
$\begingroup$

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. $$

$\endgroup$
1
  • $\begingroup$ 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? $\endgroup$
    – flawr
    Aug 8, 2017 at 14:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .