Momentum step size - Githubissues

DataSlingers / MoMA

MoMA: Modern Multivariate Analysis in R

https://DataSlingers.github.io/MoMA

GNU General Public License v2.0

22 stars 4 forks source link

Momentum step size #20

Open Banana1530 opened 6 years ago

Banana1530 commented 6 years ago

I notice there are two different versions of FISTA algorithm. To minimize g+h, where h is non-smooth and g smooth, FISTA update goes like this

$y = x ^ { ( k - 1 ) } +\beta_k \left( x ^ { ( k - 1 ) } - x ^ { ( k - 2 ) } \right)$

$x ^ { ( k ) } = \operatorname { prox } _ { t _ { k } h } \left( y - t _ { k } \nabla g ( y ) \right)$

where \beta_k is the momentum stepsize.

[1] uses

$\beta_k = \frac{k-2}{k+1}$

For the original paper [2]

$\beta_k = \frac{t_k-1}{t_k}$

where

$t_1=1,t _ { k + 1 } = \frac { 1 + \sqrt { 1 + 4 t _ { k } ^ { 2 } } } { 2 }$

[1] http://www.seas.ucla.edu/~vandenbe/236C/lectures/fista.pdf Page 3 [2] https://people.rennes.inria.fr/Cedric.Herzet/Cedric.Herzet/Sparse_Seminar/Entrees/2012/11/12_A_Fast_Iterative_Shrinkage-Thresholding_Algorithmfor_Linear_Inverse_Problems_(A._Beck,_M._Teboulle)_files/Breck_2009.pdf