proximal gradient methods

A great many objectives split into two pieces: a smooth, differentiable loss plus a non-smooth penalty, such as an L1 term that encourages sparsity or an indicator function that enforces a constraint. You cannot simply take a gradient through the kink of the non-smooth part. Proximal gradient methods handle this by alternating: take an ordinary gradient step on the smooth part, then apply a proximal operator that deals with the non-smooth part exactly, in closed form.

To minimize f plus g with f smooth and g non-smooth, each step is x_{t+1} = prox_{eta g}(x_t - eta grad f(x_t)), where prox_{eta g}(v) is the argmin over x of g(x) plus one-over-two-eta times the squared distance to v. When g is the L1 norm the proximal operator is soft-thresholding, giving the ISTA algorithm; its accelerated form, FISTA, adds Nesterov momentum. When g is the indicator of a constraint set the proximal operator is simply Euclidean projection, recovering projected gradient descent.

These methods are the backbone of sparse learning, compressed sensing, and constrained training. They inherit the convergence rates of gradient methods, order one over t in general and one over t squared when accelerated, but they only pay off when the proximal operator has a cheap closed form. If computing the prox is itself hard, the splitting buys you nothing.