Proximal gradient (forward backward splitting) methods for learning is an area of research in
optimization
Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. It is generally divided into two subfi ...
and
statistical learning theory
Statistical learning theory is a framework for machine learning drawing from the fields of statistics and functional analysis. Statistical learning theory deals with the statistical inference problem of finding a predictive function based on dat ...
which studies algorithms for a general class of
convex
Convex or convexity may refer to:
Science and technology
* Convex lens, in optics
Mathematics
* Convex set, containing the whole line segment that joins points
** Convex polygon, a polygon which encloses a convex set of points
** Convex polytope ...
regularization
Regularization may refer to:
* Regularization (linguistics)
* Regularization (mathematics)
* Regularization (physics)
In physics, especially quantum field theory, regularization is a method of modifying observables which have singularities in ...
problems where the regularization penalty may not be
differentiable
In mathematics, a differentiable function of one real variable is a function whose derivative exists at each point in its domain. In other words, the graph of a differentiable function has a non-vertical tangent line at each interior point in its ...
. 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
A lasso ( or ), also called lariat, riata, or reata (all from Castilian, la reata 're-tied rope'), is a loop of rope designed as a restraint to be thrown around a target and tightened when pulled. It is a well-known tool of the Spanish an ...
) or ''group structure'' (in the case of
group lasso).
Relevant background
Proximal gradient method
Proximal gradient methods are a generalized form of projection used to solve non-differentiable convex optimization problems.
Many interesting problems can be formulated as convex optimization problems of the form
\operatorname\limits_ \sum_^n ...
s are applicable in a wide variety of scenarios for solving
convex optimization
Convex optimization is a subfield of mathematical optimization that studies the problem of minimizing convex functions over convex sets (or, equivalently, maximizing concave functions over convex sets). Many classes of convex optimization probl ...
problems of the form
:
where
is
convex
Convex or convexity may refer to:
Science and technology
* Convex lens, in optics
Mathematics
* Convex set, containing the whole line segment that joins points
** Convex polygon, a polygon which encloses a convex set of points
** Convex polytope ...
and differentiable with
Lipschitz continuous
In mathematical analysis, Lipschitz continuity, named after German mathematician Rudolf Lipschitz, is a strong form of uniform continuity for functions. Intuitively, a Lipschitz continuous function is limited in how fast it can change: there e ...
gradient
In vector calculus, the gradient of a scalar-valued differentiable function of several variables is the vector field (or vector-valued function) \nabla f whose value at a point p is the "direction and rate of fastest increase". If the gradi ...
,
is a
convex
Convex or convexity may refer to:
Science and technology
* Convex lens, in optics
Mathematics
* Convex set, containing the whole line segment that joins points
** Convex polygon, a polygon which encloses a convex set of points
** Convex polytope ...
,
lower semicontinuous
In mathematical analysis, semicontinuity (or semi-continuity) is a property of extended real-valued functions that is weaker than continuity. An extended real-valued function f is upper (respectively, lower) semicontinuous at a point x_0 if, r ...
function which is possibly nondifferentiable, and
is some set, typically a
Hilbert space
In mathematics, Hilbert spaces (named after David Hilbert) allow generalizing the methods of linear algebra and calculus from (finite-dimensional) Euclidean vector spaces to spaces that may be infinite-dimensional. Hilbert spaces arise natural ...
. The usual criterion of
minimizes
if and only if
in the convex, differentiable setting is now replaced by
:
where
denotes the
subdifferential
In mathematics, the subderivative, subgradient, and subdifferential generalize the derivative to convex functions which are not necessarily differentiable. Subderivatives arise in convex analysis, the study of convex functions, often in connect ...
of a real-valued, convex function
.
Given a convex function
an important operator to consider is its
proximal operator In mathematical optimization, the proximal operator is an operator associated with a proper,An (extended) real-valued function ''f'' on a Hilbert space is said to be ''proper'' if it is not identically equal to +\infty, and -\infty is not in its ...
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
Projection, projections or projective may refer to:
Physics
* Projection (physics), the action/process of light, heat, or sound reflecting from a surface to another in a different direction
* The display of images by a projector
Optics, graphic ...
.
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
In mathematical analysis, semicontinuity (or semi-continuity) is a property of extended real-valued functions that is weaker than continuity. An extended real-valued function f is upper (respectively, lower) semicontinuous at a point x_0 if, r ...
, convex function on a vector space
. We define its
Fenchel conjugate
In mathematics and mathematical optimization, the convex conjugate of a function is a generalization of the Legendre transformation which applies to non-convex functions. It is also known as Legendre–Fenchel transformation, Fenchel transformati ...
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
Empirical risk minimization (ERM) is a principle in statistical learning theory which defines a family of learning algorithms and is used to give theoretical bounds on their performance. The core idea is that we cannot know exactly how well an al ...
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
In statistics and machine learning, lasso (least absolute shrinkage and selection operator; also Lasso or LASSO) is a regression analysis method that performs both variable selection and regularization in order to enhance the prediction accuracy ...
).
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
).
Convergence of this fixed point scheme is well-studied in the literature
and is guaranteed under appropriate choice of step size
and loss function (such as the square loss taken here).
Accelerated methods were introduced by Nesterov in 1983 which improve the rate of convergence under certain regularity assumptions on
.
Such methods have been studied extensively in previous years.
For more general learning problems where the proximity operator cannot be computed explicitly for some regularization term
, such fixed point schemes can still be carried out using approximations to both the gradient and the proximity operator.
Practical considerations
There have been numerous developments within the past decade in
convex optimization
Convex optimization is a subfield of mathematical optimization that studies the problem of minimizing convex functions over convex sets (or, equivalently, maximizing concave functions over convex sets). Many classes of convex optimization probl ...
techniques which have influenced the application of proximal gradient methods in statistical learning theory. Here we survey a few important topics which can greatly improve practical algorithmic performance of these methods.
Adaptive step size
In the fixed point iteration scheme
:
one can allow variable step size
instead of a constant
. Numerous adaptive step size schemes have been proposed throughout the literature.
Applications of these schemes
suggest that these can offer substantial improvement in number of iterations required for fixed point convergence.
Elastic net (mixed norm regularization)
Elastic net regularization
In statistics and, in particular, in the fitting of linear or logistic regression models, the elastic net is a regularized regression method that linearly combines the L1 and L2 penalties of the lasso and ridge methods.
Specification
The elas ...
offers an alternative to pure
regularization. The problem of lasso (
) regularization involves the penalty term
, which is not strictly convex. Hence, solutions to
where
is some empirical loss function, need not be unique. This is often avoided by the inclusion of an additional strictly convex term, such as an
norm regularization penalty. For example, one can consider the problem
:
where
For
the penalty term
is now strictly convex, and hence the minimization problem now admits a unique solution. It has been observed that for sufficiently small
, the additional penalty term
acts as a preconditioner and can substantially improve convergence while not adversely affecting the sparsity of solutions.
Exploiting group structure
Proximal gradient methods provide a general framework which is applicable to a wide variety of problems in
statistical learning theory
Statistical learning theory is a framework for machine learning drawing from the fields of statistics and functional analysis. Statistical learning theory deals with the statistical inference problem of finding a predictive function based on dat ...
. Certain problems in learning can often involve data which has additional structure that is known '' a priori''. In the past several years there have been new developments which incorporate information about group structure to provide methods which are tailored to different applications. Here we survey a few such methods.
Group lasso
Group lasso is a generalization of the
lasso method when features are grouped into disjoint blocks.
Suppose the features are grouped into blocks
. Here we take as a regularization penalty
:
which is the sum of the
norm on corresponding feature vectors for the different groups. A similar proximity operator analysis as above can be used to compute the proximity operator for this penalty. Where the lasso penalty has a proximity operator which is soft thresholding on each individual component, the proximity operator for the group lasso is soft thresholding on each group. For the group
we have that proximity operator of
is given by
:
where
is the
th group.
In contrast to lasso, the derivation of the proximity operator for group lasso relies on the
Moreau decomposition
Moreau may refer to:
People
*Moreau (surname)
Places
* Moreau, New York
*Moreau River (disambiguation)
Music
*An alternate name for the band Cousteau, used for the album ''Nova Scotia'' in the United States for legal reasons
In fiction
*Dr. M ...
. Here the proximity operator of the conjugate of the group lasso penalty becomes a projection onto the
ball
A ball is a round object (usually spherical, but can sometimes be ovoid) with several uses. It is used in ball games, where the play of the game follows the state of the ball as it is hit, kicked or thrown by players. Balls can also be used f ...
of a
dual norm
In functional analysis, the dual norm is a measure of size for a continuous linear function defined on a normed vector space.
Definition
Let X be a normed vector space with norm \, \cdot\, and let X^* denote its continuous dual space. The dual ...
.
Other group structures
In contrast to the group lasso problem, where features are grouped into disjoint blocks, it may be the case that grouped features are overlapping or have a nested structure. Such generalizations of group lasso have been considered in a variety of contexts.
For overlapping groups one common approach is known as ''latent group lasso'' which introduces latent variables to account for overlap.
Nested group structures are studied in ''hierarchical structure prediction'' and with
directed acyclic graph
In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles. That is, it consists of vertices and edges (also called ''arcs''), with each edge directed from one ve ...
s.
See also
*
Convex analysis
Convex analysis is the branch of mathematics devoted to the study of properties of convex functions and convex sets, often with applications in convex minimization, a subdomain of optimization theory.
Convex sets
A subset C \subseteq X of som ...
*
Proximal gradient method
Proximal gradient methods are a generalized form of projection used to solve non-differentiable convex optimization problems.
Many interesting problems can be formulated as convex optimization problems of the form
\operatorname\limits_ \sum_^n ...
*
Regularization
Regularization may refer to:
* Regularization (linguistics)
* Regularization (mathematics)
* Regularization (physics)
In physics, especially quantum field theory, regularization is a method of modifying observables which have singularities in ...
*
Statistical learning theory
Statistical learning theory is a framework for machine learning drawing from the fields of statistics and functional analysis. Statistical learning theory deals with the statistical inference problem of finding a predictive function based on dat ...
References
{{reflist
First order methods
First or 1st is the ordinal form of the number one (#1).
First or 1st may also refer to:
*World record, specifically the first instance of a particular achievement
Arts and media Music
* 1$T, American rapper, singer-songwriter, DJ, and rec ...
Convex optimization
Machine learning