Structured sparsity via alternating direction methods

zbMATH Open1303.68108arXiv1105.0728MaRDI QIDQ5405166FDOQ5405166

Donald Goldfarb, Zhiwei (Tony) Qin

Publication date: 1 April 2014

Abstract: We consider a class of sparse learning problems in high dimensional feature space regularized by a structured sparsity-inducing norm which incorporates prior knowledge of the group structure of the features. Such problems often pose a considerable challenge to optimization algorithms due to the non-smoothness and non-separability of the regularization term. In this paper, we focus on two commonly adopted sparsity-inducing regularization terms, the overlapping Group Lasso penalty $l_1/l_2$-norm and the $l_1/l_{i}nfty$-norm. We propose a unified framework based on the augmented Lagrangian method, under which problems with both types of regularization and their variants can be efficiently solved. As the core building-block of this framework, we develop new algorithms using an alternating partial-linearization/splitting technique, and we prove that the accelerated versions of these algorithms require $O(frac1sqrtepsilon)$ iterations to obtain an $epsilon$-optimal solution. To demonstrate the efficiency and relevance of our algorithms, we test them on a collection of data sets and apply them to two real-world problems to compare the relative merits of the two norms.

Full work available at URL: https://arxiv.org/abs/1105.0728

Recommendations

• scientific article; zbMATH DE number 6253954
• Efficient inexact proximal gradient algorithms for structured sparsity-inducing norm
• Structured sparsity through convex optimization
• Smoothing proximal gradient method for general structured sparse regression
• Regularizers for structured sparsity

zbMATH Keywords

augmented Lagrangianstructured sparsityalternating direction methodsvariable splittingoverlapping group lasso

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05)

Cited In (15)

• Title not available (Why is that?)
• An FFT-based fast gradient method for elastic and inelastic unit cell homogenization problems
• Title not available (Why is that?)
• [HDDA] sparse subspace constrained partial least squares
• Weakly decomposable regularization penalties and structured sparsity
• Learning the Structure for Structured Sparsity
• Detecting clusters in multivariate response regression
• Title not available (Why is that?)
• Learning with Structured Sparsity
• Proximal methods for the latent group lasso penalty
• Title not available (Why is that?)
• On the strong convergence of forward-backward splitting in reconstructing jointly sparse signals
• Mirror Prox algorithm for multi-term composite minimization and semi-separable problems
• Title not available (Why is that?)
• Iteratively Reweighted Group Lasso Based on Log-Composite Regularization

This page was built for publication: Structured sparsity via alternating direction methods

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5405166)