0
$\begingroup$

Maybe my question is obvious but i cannot find any good source which answers it

I trying to learn about proximal gradient. One thing which is not clear for me is particular algorithm for line search. According to this presentation (slide 20) and some other sources backtracking line search with previous step length as initialization is good choice.

I implemented simple version of LASSO with proximal gradient and it looks like that increasing step from time to time can make convergence significantly faster.

So my question is: Is it good idea to use bracketing in proximal gradient?

(Accoring to "Numerical optimization by Nocedal and Wright" i use term "bracketing" in meaning "finding initial interval for backtracking")

My second question is: Which is best line search algorithm for LASSO/general proximal gradient?

Sorry for my English

$\endgroup$
1
$\begingroup$

For LASSO Case you probably can estimate $ L $ pretty good and the best would be using FISTA for acceleration of the Proximal Gradient Method.

In general you can use the Line Search as above (Neal Parikh and Stephen Boyd - Proximal Algorithms Page 20):

enter image description here

Or (L. Vandenberghe - Proximal Gradient Method Page 6-20):

enter image description here

I expect them to be equivalent, Though it seems Boyd's is easier computationally.

Better and more robust choice would be Alternating Direction Method of Multipliers (ADMM).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.