La suavidad de Lipschitz y el gradiente acelerado de Nesterov descienden

Question

Estoy leyendo acerca de Nesterov Acelerada de Gradiente de Descender, y tratando de aplicarlo a mi aplicación (Tomografía computarizada), que esencialmente significa que yo soy la solución de un problema lineal de la forma

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

Independientemente de la complejidad de la prueba, en última instancia, el algoritmo parece bastante fácil de implementar, ya que es tan sólo una ligera modificación de la clásica gradiente de descender con algunos parámetros específicos de las actualizaciones. Nesterov, la aceleración termina en una actualización que parece:

$$ 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 $$ para la iteración número$s$$\gamma_s=\frac{1-\lambda_s}{\lambda_{s+1}}$, siendo la $\lambda_S=\frac{1+\sqrt{1+4{\lambda_{s-1}^2}}}{2}$.

Sin embargo, se basa en el $\beta$-la suavidad de la función $f$, e $\beta$ se utiliza como un parámetro.

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

Qué valor debo de dar a $\beta$? ¿Cómo puedo saber cómo $\beta$-suave mi función es?

Answer 1

El gradiente de$f$ es$\nabla f(x) = 2 A^T(Ax-b)$. Para usar el método de Nesterov, necesitamos una constante de Lipschitz para$\nabla f$ (no$f$). Tenga en cuenta que \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} Entonces una constante de Lipschitz para$\nabla f$ es $$ \ beta = 2 \ | A \ | ^ 2. $$