||DISI-Sala Conferenze-3 piano
||Regularizers for Structured Sparsity
||Dott. Massimiliano Pontil
||Dept of Computer Science – University College London, UK
||We study the problem of learning a sparse linear regression vector under
additional conditions on the structure of its sparsity pattern. This problem is relevant
both in machine, statistics and signal processing. It is well known that a linear
regression can benefit from knowledge that the underlying regression vector is sparse.
The combinatorial problem of selecting the nonzero components of this vector can be
“relaxed” by regularizing the squared error with a convex penalty function like the L-1
norm. However, in many applications, additional conditions on the structure of the
regression vector and its sparsity pattern are available. By incorporating this
information into the learning method, may lead to a significant decrease of the
In this talk, we present a family of convex penalty functions, which encode prior
knowledge on the structure of the regression vectors by means of a set of linear
constraints on the absolute values of its components. This family subsumes the L-1
norm and is flexible enough to include different models of sparsity patterns, which are
of practical and theoretical importance. We establish the basic properties of these
penalty functions and discuss some examples where they can be computed explicitly.
Moreover, we present a convergent optimization algorithm for solving regularized
least squares with these penalty functions. Numerical simulations highlight the benefit
of structured sparsity and the advantage offered by our approach over the Lasso
method and other related methods.
(Joint work with Charles Micchelli and Jean Morales).