Convex and Network Flow Optimization for Structured Sparsity

Julien Mairal 1, * Rodolphe Jenatton 2, 3 Guillaume Obozinski 2, 3 Francis Bach 2, 3
* Auteur correspondant
3 SIERRA - Statistical Machine Learning and Parsimony
DI-ENS - Département d'informatique de l'École normale supérieure, ENS Paris - École normale supérieure - Paris, Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR8548
Abstract : We consider a class of learning problems regularized by a structured sparsity-inducing norm defined as the sum of l_2- or l_infinity-norms over groups of variables. Whereas much effort has been put in developing fast optimization techniques when the groups are disjoint or embedded in a hierarchy, we address here the case of general overlapping groups. To this end, we present two different strategies: On the one hand, we show that the proximal operator associated with a sum of l_infinity-norms can be computed exactly in polynomial time by solving a quadratic min-cost flow problem, allowing the use of accelerated proximal gradient methods. On the other hand, we use proximal splitting techniques, and address an equivalent formulation with non-overlapping groups, but in higher dimension and with additional constraints. We propose efficient and scalable algorithms exploiting these two strategies, which are significantly faster than alternative approaches. We illustrate these methods with several problems such as CUR matrix factorization, multi-task learning of tree-structured dictionaries, background subtraction in video sequences, image denoising with wavelets, and topographic dictionary learning of natural image patches.
Type de document :
Article dans une revue
Journal of Machine Learning Research, Journal of Machine Learning Research, 2011, 12, pp.2681−2720
Liste complète des métadonnées

Littérature citée [84 références]  Voir  Masquer  Télécharger
Contributeur : Julien Mairal <>
Soumis le : jeudi 15 septembre 2011 - 21:14:40
Dernière modification le : jeudi 11 janvier 2018 - 06:23:26
Document(s) archivé(s) le : vendredi 16 décembre 2011 - 02:30:37


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


  • HAL Id : inria-00584817, version 3
  • ARXIV : 1104.1872



Julien Mairal, Rodolphe Jenatton, Guillaume Obozinski, Francis Bach. Convex and Network Flow Optimization for Structured Sparsity. Journal of Machine Learning Research, Journal of Machine Learning Research, 2011, 12, pp.2681−2720. 〈inria-00584817v3〉



Consultations de la notice


Téléchargements de fichiers