0
$\begingroup$

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 ?

$\endgroup$
9
  • $\begingroup$ 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. $\endgroup$
    – dohmatob
    Commented Apr 13, 2017 at 13:29
  • $\begingroup$ I would like to add momentum to the proximal gradient descent and run it with fixed step-size. t_k is step size. $\endgroup$ Commented Apr 13, 2017 at 13:45
  • 1
    $\begingroup$ 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... $\endgroup$
    – dohmatob
    Commented Apr 13, 2017 at 14:05
  • 1
    $\begingroup$ If $t_k = 0.02 > 1 / L_{\nabla g} = 1 / \|X\|_2^2$, then your algorithm might diverge... $\endgroup$
    – dohmatob
    Commented Apr 13, 2017 at 21:25
  • 1
    $\begingroup$ I gave it to so in my previous comment: $L_{\nabla g} = \|X\|_2^2 = \sigma_{\text{max}}^2(X)$. $\endgroup$
    – dohmatob
    Commented Apr 14, 2017 at 13:07

1 Answer 1

0
$\begingroup$

It seems you're trying to employ the FISTA Method (A Fast Iterative Shrinkage Thresholding Algorithm for Linear Inverse Problems). In section 3 of the paper there are the requirements for convergence with constant step size and with line backtracking.

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.

$\endgroup$

You must log in to answer this question.

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