# Requirements for Proximal Gradient Descent Algorithm to Converge When Using Momentum (Accelerated Descent)

I'm trying to solve following convex optimization function: $min_W g(W) + h(W)$, where the $g$ is convex and differentiable and $h$ in convex an non-smooth. $g(W)=||Y-WX||_F^2$ is square loss function.

Note that,$X,W,Y$ all are matrices. $h(W)$ is non-smooth function with known proximal operator (shoft-tresholding(shirnkage(W))). I use fixed step size (t_k=0.02). I tried to do backtracking line search, but I was not sure how to extend it to the case where $Y and W$ are matrices (when they are both vectors, it's pretty easy to do it)

Unfortunately when I use momentum (Nestrove acceleration approach), my algorithm does not converge. Here how I compute momentum:

$W^{(0)}=W^{(-1)} \in R^n$, we repeat:

$v=W^{(W-1)} + \frac{k-2}{k-1}(W^{(k-1)}-W^{(k-1)})$

$W^{(k)}=prox_{tk}(v-t_k\nabla g(v))$

for k=1,2,3,....

Does anybody have some hints regarding computing momentum for accelerared proximal gradient descent method ? second, is it possible to adapt back-tracking line search for the case where $Y and W$ are matrices ?

• You're probably referring to a work by Nesterov. Please provide all info: which paper are you referring to precisely ? What is $t_k$ provide the exact expression you're using) ?, etc. Commented Apr 13, 2017 at 13:29
• I would like to add momentum to the proximal gradient descent and run it with fixed step-size. t_k is step size. Commented Apr 13, 2017 at 13:45
• What is the value of $t_k$ you're using ? How's it computed ? As your question stands it ap,pears you're trying ad hac amendments to an unknown algorithm. Talking about momentum, what paper are you referring to ? The more details you provide, the more help you'll get here. Nobody will invest more effort answering your question than the effort you invest writing it down properly in the first place... Commented Apr 13, 2017 at 14:05
• If $t_k = 0.02 > 1 / L_{\nabla g} = 1 / \|X\|_2^2$, then your algorithm might diverge... Commented Apr 13, 2017 at 21:25
• I gave it to so in my previous comment: $L_{\nabla g} = \|X\|_2^2 = \sigma_{\text{max}}^2(X)$. Commented Apr 14, 2017 at 13:07

For fixed step size the step size $$t < \frac{1}{L}$$ where $$L$$ is the Lipschitz continuous parameter of $$\nabla g \left( \cdot \right)$$ (The smooth function).
In your case, the function is quadratic hence $${L}_{g \left( \cdot \right)} = {\left\| X \right\|}_{2} = {\sigma}_{\max} \left( X \right)$$.
In MATLAB you can set stepSize = 0.99 * (1 / norm(mX, 2)); - Namely a number smaller the the $${L}_{2}$$ norm of the matrix.