Home Research
Home Research
A primal-dual algorithm for group sparse regularization with overlapping groups
Year: 2010  
Authors: Sofia Mosci, Silvia Villa, Alessandro Verri, Lorenzo Rosasco  
Editor: J. Lafferty and C. K. I. Williams and J. Shawe-Taylor and R.S. Zemel and A. Culotta
Book title: Advances in Neural Information Processing Systems 23
Pages: 2604-2612
Month: December
We deal with the problem of variable selection when the features must be selected group-wise, with possibly overlapping groups defined a priori. In particular we propose a new optimization procedure for solving the problem proposed in Jacob et al. (2009), where the group lasso penalty is generalized to the case of overlapping groups of covariates. While in Jacob et al. (2009), the proposed algorithm requires explicit replication of the variables belonging to more than one group, our iterative algorithm, based on a combination of proximal methods and constrained Newton method in the dual space, provides a scalable alternative with no need for data duplication, and thus allows dealing with high dimensional problems without pre-processing for dimensionality reduction. We study the computational advantages of our algorithm with respect to state-of-the-art algorithms with duplication, and show that it has a relatively short running time also in high dimensional problems with significant group overlaps.