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

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
2016
Liste complète des métadonnées

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

https://hal-enpc.archives-ouvertes.fr/hal-01412385
Contributeur : Guillaume Obozinski <>
Soumis le : jeudi 8 décembre 2016 - 12:26:30
Dernière modification le : jeudi 11 janvier 2018 - 06:20:23
Document(s) archivé(s) le : jeudi 23 mars 2017 - 07:03:25

Fichier

hal_submodlp_2016_final.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01412385, version 1

Collections

Citation

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

Partager

Métriques

Consultations de la notice

398

Téléchargements de fichiers

789