Convex Relaxation for Combinatorial Penalties
arXiv:1205.1240
Abstract
In this paper, we propose an unifying view of several recently proposed structured sparsity-inducing norms. We consider the situation of a model simultaneously (a) penalized by a set- function de ned on the support of the unknown parameter vector which represents prior knowledge on supports, and (b) regularized in Lp-norm. We show that the natural combinatorial optimization problems obtained may be relaxed into convex optimization problems and introduce a notion, the lower combinatorial envelope of a set-function, that characterizes the tightness of our relaxations. We moreover establish links with norms based on latent representations including the latent group Lasso and block-coding, and with norms obtained from submodular functions.
35 page
References in corpus (7)
- Simultaneous analysis of Lasso and Dantzig selector
- Structured Variable Selection with Sparsity-Inducing Norms
- Learning with Structured Sparsity
- Proximal Methods for Hierarchical Sparse Coding
- Group Lasso with Overlaps: the Latent Group Lasso approach
- Supervised Feature Selection in Graphs with Path Coding Penalties and Network Flows
- Regularizers for Structured Sparsity
Cited by in corpus (9)
- Group Lasso with Overlaps: the Latent Group Lasso approach
- Robust Group Sparse Beamforming for Multicast Green Cloud-RAN with Imperfect CSI
- Learning the Structure for Structured Sparsity
- Asymptotic Confidence Regions for High-dimensional Structured Sparsity
- A totally unimodular view of structured sparsity
- Differentially Private Empirical Risk Minimization with Sparsity-Inducing Norms
- New Perspectives on k-Support and Cluster Norms
- Group Sparse Beamforming for Green Cloud-RAN
- Parametric Maxflows for Structured Sparse Learning with Convex Relaxations of Submodular Functions