A unified perspective on convex structured sparsity: Hierarchical, symmetric, submodular norms and beyond

Guillaume Obozinski 1, 2, 3 Francis Bach 4
4 SIERRA - Statistical Machine Learning and Parsimony
DI-ENS - Département d'informatique de l'École normale supérieure, CNRS - Centre National de la Recherche Scientifique, Inria de Paris
Abstract : In this paper, we propose a unified theory for convex structured sparsity-inducing norms on vectors associated with combinatorial penalty functions. Specifically, we consider the situation of a model simultaneously (a) penalized by a set-function defined on the support of the unknown parameter vector which represents prior knowledge on supports, and (b) regularized in p-norm. We show that each of the obtained combinatorial optimization problems admits a natural relaxation as an optimization problem regularized by a matching sparsity-inducing norm. To characterize the tightness of the relaxation, we introduce a notion of lower combinatorial envelope of a set-function. Symmetrically, a notion of upper combinatorial envelope produces the most concise norm expression. We show that these relaxations take the form of combinatorial latent group Lassos associated with min-cover penalties also known as block-coding schemes. For submodular penalty functions, the associated norm, dual norm and the corresponding proximal operator can be computed efficiently using a generic divide-and-conquer algorithm. Our framework obtains constructive derivations for the Lasso, group Lasso, exclusive Lasso, the OWL, OSCAR and SLOPE penalties, the k-support norm, several hierarchical penalties considered in the literature for chains and tree structures, and produces also new norms. It leads to general efficient algorithms for all these norms, recovering as special cases several algorithms proposed in the literature and yielding improved procedures for some cases. For norms associated with submodular penalties, including a large number of non-decomposable norms, we generalize classical support recovery and fast rates convergence results based respectively on generalization of the irrepresentability condition and the restricted eigenvalue condition .
Type de document :
Pré-publication, Document de travail
Liste complète des métadonnées

Littérature citée [51 références]  Voir  Masquer  Télécharger

Contributeur : Guillaume Obozinski <>
Soumis le : jeudi 8 décembre 2016 - 12:26:30
Dernière modification le : mardi 24 avril 2018 - 17:20:15
Document(s) archivé(s) le : jeudi 23 mars 2017 - 07:03:25


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-01412385, version 1



Guillaume Obozinski, Francis Bach. A unified perspective on convex structured sparsity: Hierarchical, symmetric, submodular norms and beyond. 2016. 〈hal-01412385〉



Consultations de la notice


Téléchargements de fichiers