Convex and Network Flow Optimization for Structured Sparsity

Julien Mairal; Rodolphe Jenatton; Guillaume Obozinski; Francis Bach

inria-00584817, version 2

Convex and Network Flow Optimization for Structured Sparsity

Julien Mairal ( Author to contact preferably )^a^, 1, Rodolphe Jenatton () ^2, 3, Guillaume Obozinski () ^2, 3, Francis Bach () ^2, 3

(2011)

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.

a – University of California, Berkeley
1: Department of Statistics
University of California, Berkeley
2: Laboratoire d'informatique de l'école normale supérieure (LIENS)
CNRS : UMR8548 – Ecole normale supérieure de Paris - ENS Paris
3: SIERRA (INRIA Paris - Rocquencourt)
INRIA : PARIS - ROCQUENCOURT – Ecole normale supérieure de Paris - ENS Paris – CNRS : UMR8548

Collaboration : University of California, Berkeley, Department of Statistics

inria-00584817, version 2
http://hal.inria.fr/inria-00584817
oai:hal.inria.fr:inria-00584817
From: Julien Mairal <>
Submitted on: Wednesday, 31 August 2011 18:45:28
Updated on: Thursday, 1 September 2011 07:29:46

See detailed view

Associated documents

PDF :

PS :

arXiv: 1104.1872

Export

Bibtex EndNote TEI RefWorks

%% inria-00584817, version 2
%% http://hal.inria.fr/inria-00584817
@techreport{mairal:inria-00584817,
    hal_id = {inria-00584817},
    url = {http://hal.inria.fr/inria-00584817},
    title = {{Convex and Network Flow Optimization for Structured Sparsity}},
    author = {Mairal, Julien and Jenatton, Rodolphe and Obozinski, Guillaume and Bach, Francis},
    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.}},
    keywords = {Convex optimization; proximal methods; sparse coding; structured sparsity; matrix factorization; network flow optimization; alternating direction method of multipliers},
    language = {English},
    affiliation = {Department of Statistics , Laboratoire d'informatique de l'{\'e}cole normale sup{\'e}rieure - LIENS , SIERRA - INRIA Paris - Rocquencourt},
    pages = {40},
    type = {Research Report},
    note = {the previous version was accepted for publication with minor revision to the Journal of Machine Learning Research. This is a revised version, currently under submission.},
    collaboration = {University of California, Berkeley, Department of Statistics },
    year = {2011},
    month = Aug,
    pdf = {http://hal.inria.fr/inria-00584817/PDF/mairal11a\_arxiv.pdf},
}

%F inria-00584817, version 2
%0 Report
%U http://hal.inria.fr/inria-00584817
%2 MATH:MATH_OC;STAT:OT;INFO:INFO_LG
%T Convex and Network Flow Optimization for Structured Sparsity
%A Mairal, Julien
%A Jenatton, Rodolphe
%A Obozinski, Guillaume
%A Bach, Francis
%+ Department of Statistics , Laboratoire d'informatique de l'école normale supérieure - LIENS , SIERRA - INRIA Paris - Rocquencourt
%X 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.
%G English
%2 Research Report
%P 40
%8 2011-08-00
%K Convex optimization; proximal methods; sparse coding; structured sparsity; matrix factorization; network flow optimization; alternating direction method of multipliers
%Z the previous version was accepted for publication with minor revision to the Journal of Machine Learning Research. This is a revised version, currently under submission.
%Z Julien Mairal was supported by the NSF grant SES-0835531 and NSF award CCF-0939370
%2 3408
%2 13849
%Z University of California, Berkeley, Department of Statistics

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="report"><head>Research reports</head>
<biblStruct type="report" xml:id="inria-00584817"><monogr>
<author><persName><forename>Julien</forename><surname>Mairal</surname></persName>
<affiliation>
<orgName type="team">Department of Statistics</orgName>
<country>US</country>
<orgName type="institution">University of California, Berkeley</orgName>
</affiliation>
</author>
<author><persName><forename>Rodolphe</forename><surname>Jenatton</surname></persName>
<affiliation>
<orgName type="laboratory">LIENS</orgName>
<orgName type="team">Laboratoire d'informatique de l'école normale supérieure</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR8548</orgName>
<orgName type="institution">Ecole normale supérieure de Paris - ENS Paris</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">INRIA Paris - Rocquencourt</orgName>
<orgName type="team">SIERRA</orgName>
<country>FR</country>
<orgName type="institution">INRIA : PARIS - ROCQUENCOURT</orgName>
<orgName type="institution">Ecole normale supérieure de Paris - ENS Paris</orgName>
<orgName type="institution">CNRS : UMR8548</orgName>
</affiliation>
</author>
<author><persName><forename>Guillaume</forename><surname>Obozinski</surname></persName>
<affiliation>
<orgName type="laboratory">LIENS</orgName>
<orgName type="team">Laboratoire d'informatique de l'école normale supérieure</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR8548</orgName>
<orgName type="institution">Ecole normale supérieure de Paris - ENS Paris</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">INRIA Paris - Rocquencourt</orgName>
<orgName type="team">SIERRA</orgName>
<country>FR</country>
<orgName type="institution">INRIA : PARIS - ROCQUENCOURT</orgName>
<orgName type="institution">Ecole normale supérieure de Paris - ENS Paris</orgName>
<orgName type="institution">CNRS : UMR8548</orgName>
</affiliation>
</author>
<author><persName><forename>Francis</forename><surname>Bach</surname></persName>
<affiliation>
<orgName type="laboratory">LIENS</orgName>
<orgName type="team">Laboratoire d'informatique de l'école normale supérieure</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR8548</orgName>
<orgName type="institution">Ecole normale supérieure de Paris - ENS Paris</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">INRIA Paris - Rocquencourt</orgName>
<orgName type="team">SIERRA</orgName>
<country>FR</country>
<orgName type="institution">INRIA : PARIS - ROCQUENCOURT</orgName>
<orgName type="institution">Ecole normale supérieure de Paris - ENS Paris</orgName>
<orgName type="institution">CNRS : UMR8548</orgName>
</affiliation>
</author>
<title type="main" level="m">Convex and Network Flow Optimization for Structured Sparsity</title><title type="main" level="m">Convex and Network Flow Optimization for Structured Sparsity</title><imprint><biblScope type="publicationDate">2011-08-00</biblScope><biblScope type="pp">40</biblScope></imprint></monogr><idno type="HALid">http://hal.inria.fr/inria-00584817</idno><idno type="HALFile">http://hal.inria.fr/inria-00584817/PDF/mairal11a_arxiv.pdf</idno></biblStruct>
</listBibl>
</listBibl>