Proximal Gradient MethodIt is a kind of gradient descent method, which is mainly used to solve optimization problems with non-differentiable objective functions. If the objective function is not differentiable at some points, the gradient of that point cannot be solved and the traditional gradient descent method cannot be used.

The proximal gradient method uses neighboring points as approximate gradients and performs gradient descent based on them. It is usually used to solve L1 regularization.

Related concepts

Assume $latex {f{ \left( {x} \right) }\text{ }=\text{ }f\mathop{{}}\nolimits\_{{0}}{ \left( {x} \right) }\text{ }+\text{ }f\mathop{{}}\nolimits\_{{1}}{ \left( {x} \right) }}$latexf(x) = f_0(x) + f_1(x) , where $latex {f\mathop{{}}\nolimits\_{{0}},f\mathop{{}}\nolimits\_{{1}}}$latexf_0,f_1 are convex functions and $latex {f\mathop{{}}\nolimits\_{{1}}}$latexf_1 is a smooth function, then the proximal gradient

$latex {\mathop{{ \nabla }}\limits^{ \sim }f{ \left( {x} \right) }\text{ }=\text{ }x\text{ }-\text{ }prox\mathop{{}}\nolimits\_{{f\mathop{{}}\nolimits\_{{0}}}}{ \left( {x\text{ }-\text{ } \nabla f\mathop{{}}\nolimits\_{{1}}{ \left( {x} \right) }} \right) }}$latex∇∼f(x) = x − prox_f_0(x − ∇f_1(x))

Among them are

$latex {prox\mathop{{}}\nolimits\_{{f\mathop{{}}\nolimits\_{{0}}}}{ \left( {z} \right) }\text{ }=\text{ }arg\text{ }\mathop{{min}}\limits\_{{y \in X}}\text{ }f\mathop{{}}\nolimits\_{{0}}{ \left( {y} \right) }\text{ }+\text{ }\frac{{1}}{{2}}{ \left\Vert {z\text{ }-\text{ }y} \right\Vert }\mathop{{}}\nolimits^{{2}}}$latexprox_f_0(z) = arg min_y∈X f_0(y) + 21​∥z − y∥2

Proximal Gradient Method Process

For the objective function $latex {min\mathop{{}}\nolimits\_{{x \in R\mathop{{}}\nolimits^{{n}}}}f{ \left( {x} \right) }\text{ }=\text{ }f\mathop{{}}\nolimits\_{{0}}{ \left( {x} \right) }\text{ }+\text{ }f\mathop{{}}\nolimits\_{{1}}{ \left( {x} \right) }}$latexmin_x∈Rnf(x) = f_0(x) + f_1(x) , where f0 is non-smooth and f1 is smooth, it is defined as follows:

Iteration r = 0, 1, 2, …

latex {x\mathop{{}}\nolimits^{{r+1}}\text{ }=\text{ }prox\mathop{{}}\nolimits\_{{ \alpha \mathop{{}}\nolimits^{{r}}f\mathop{{}}\nolimits\_{{0}}}}{ \left\[ {x\mathop{{}}\nolimits^{{r}}\text{ }-\text{ } \alpha \mathop{{}}\nolimits^{{r}} \nabla f\mathop{{}}\nolimits\_{{1}}{ \left( {x\mathop{{}}\nolimits^{{r}}} \right) }} \right\] }}

• When $latex {f\mathop{{}}\nolimits\_{{0}} \text{ }=\text{ } 0}$latexf_0 = 0, the formula is the gradient descent method
• When $latex {f\mathop{{}}\nolimits\_{{1}} \text{ }=\text{ } 0}$latexf_1 = 0, the formula is the proximal endpoint method

Special case of proximal gradient method

• Landweber is expected;
• Alternating projection;
• Alternating direction method of multipliers;
• Fast Iterative Shrinkage Thresholding Algorithm (FISTA).