Proximal gradient (forward backward splitting) methods for learning is an area of research in optimization and statistical learning theory which studies algorithms for a general class of convex regularization problems where the regularization penalty may not be differentiable. One such example is regularization (also known as Lasso) of the form
Proximal gradient methods offer a general framework for solving regularization problems from statistical learning theory with penalties that are tailored to a specific problem application. Such customized penalties can help to induce certain structure in problem solutions, such as sparsity (in the case of lasso) or group structure (in the case of group lasso).
Relevant background
Proximal gradient methods are applicable in a wide variety of scenarios for solving convex optimization problems of the form
where is convex and differentiable with Lipschitz continuous gradient, is a convex, lower semicontinuous function which is possibly nondifferentiable, and is some set, typically a Hilbert space. The usual criterion of minimizes if and only if in the convex, differentiable setting is now replaced by
where denotes the subdifferential of a real-valued, convex function .
Given a convex function an important operator to consider is its proximal operator defined by
which is well-defined because of the strict convexity of the norm. The proximal operator can be seen as a generalization of a projection. We see that the proximity operator is important because is a minimizer to the problem if and only if where is any positive real number.
Moreau decomposition
One important technique related to proximal gradient methods is the Moreau decomposition, which decomposes the identity operator as the sum of two proximity operators. Namely, let be a lower semicontinuous, convex function on a vector space . We define its Fenchel conjugate to be the function
The general form of Moreau's decomposition states that for any and any that
which for implies that . The Moreau decomposition can be seen to be a generalization of the usual orthogonal decomposition of a vector space, analogous with the fact that proximity operators are generalizations of projections.
In certain situations it may be easier to compute the proximity operator for the conjugate instead of the function , and therefore the Moreau decomposition can be applied. This is the case for group lasso.
Lasso regularization
Consider the regularized empirical risk minimization problem with square loss and with the norm as the regularization penalty:
where The regularization problem is sometimes referred to as lasso (least absolute shrinkage and selection operator). Such regularization problems are interesting because they induce sparse solutions, that is, solutions to the minimization problem have relatively few nonzero components. Lasso can be seen to be a convex relaxation of the non-convex problem
where denotes the "norm", which is the number of nonzero entries of the vector . Sparse solutions are of particular interest in learning theory for interpretability of results: a sparse solution can identify a small number of important factors.
Solving for L1 proximity operator
For simplicity we restrict our attention to the problem where . To solve the problem
we consider our objective function in two parts: a convex, differentiable term and a convex function . Note that is not strictly convex.
Let us compute the proximity operator for . First we find an alternative characterization of the proximity operator as follows:
For it is easy to compute : the th entry of is precisely
Using the recharacterization of the proximity operator given above, for the choice of and we have that is defined entrywise by
which is known as the soft thresholding operator .
Fixed point iterative schemes
To finally solve the lasso problem we consider the fixed point equation shown earlier:
Given that we have computed the form of the proximity operator explicitly, then we can define a standard fixed point iteration procedure. Namely, fix some initial , and for define
Note here the effective trade-off between the empirical error term and the regularization penalty . This fixed point method has decoupled the effect of the two different convex functions which comprise the objective function into a gradient descent step () and a soft thresholding step (via ).