hal-00613125, version 2

Optimization with Sparsity-Inducing Penalties

Francis Bach () ^1, 2, Rodolphe Jenatton () ^1, 2, Julien Mairal () ³, Guillaume Obozinski () ^1, 2

Foundations and Trends in Machine Learning (2011) -

• 1 :  Laboratoire d'informatique de l'école normale supérieure (LIENS)
• http://www.di.ens.fr
  CNRS : UMR8548 – Ecole normale supérieure de Paris - ENS Paris 45 Rue d'Ulm 75230 PARIS CEDEX 05 France
• 2 :  SIERRA (INRIA Paris - Rocquencourt)
• 
  INRIA : PARIS - ROCQUENCOURT – Ecole normale supérieure de Paris - ENS Paris – CNRS : UMR8548 INRIA 23 avenue d'Italie 75013 Paris France
• 3 :  Department of Statistics
• http://www.stat.berkeley.edu/
  University of California, Berkeley 367 Evans Hall Berkeley, CA 94720-3860 États-Unis

Références bibliographiques

• Type de publication : Articles dans des revues avec comité de lecture
• Domaine :

  Informatique/Apprentissage

  Mathématiques/Optimisation et contrôle

  Statistiques/Autres

• Titre : Optimization with Sparsity-Inducing Penalties
• Résumé : Sparse estimation methods are aimed at using or obtaining parsimonious representations of data or models. They were first dedicated to linear variable selection but numerous extensions have now emerged such as structured sparsity or kernel selection. It turns out that many of the related estimation problems can be cast as convex optimization problems by regularizing the empirical risk with appropriate non-smooth norms. The goal of this paper is to present from a general perspective optimization tools and techniques dedicated to such sparsity-inducing penalties. We cover proximal methods, block-coordinate descent, reweighted $\ell_2$-penalized techniques, working-set and homotopy methods, as well as non-convex formulations and extensions, and provide an extensive set of experiments to compare various algorithms from a computational point of view.
• Langue du texte
  intégral : Anglais
• Journal : Foundations and Trends in Machine Learning
• Audience : internationale
• Date de publication : 2011
• Page, identifiant, ... : -
• Mots Clés : Convex optimization – sparsity
• Projet européen :

  Numéro Cordis	239993
  Acronyme	SIERRA
  Titre	Sparse Structured Methods for Machine Learning
  Financé par	ERC
  Début	2009-12-01
  Date de fin	2014-11-30
  Identifiant de l'appel	ERC-2009-StG

Liste des fichiers attachés à ce document :

TEX

algmatlab.sty(2.2 KB)

algorithm.sty(2.2 KB)

algorithm2e.sty(88.2 KB)

algorithmicx.sty(26.1 KB)

algpseudocode.sty(3.4 KB)

Bach-Jenatton-Mairal-Obozinski-HAL.bbl(32.6 KB)

Bach-Jenatton-Mairal-Obozinski-HAL.tex(5.9 KB)

Bach-Jenatton-Mairal-Obozinski.bib(53.3 KB)

essence_logo.eps(183.4 KB)

essence_logo.pdf(11.6 KB)

macros.tex(12 KB)

now11.clo(5.3 KB)

now_arxiv.cls(44.2 KB)

now_logo.eps(192.6 KB)

now_logo.pdf(11.4 KB)

sample.jtl(3.2 KB)

smallcaptions.sty(995 B)

bach

abstract.tex(858 B)

biodata_largescale_0.01sparsity.eps(11.6 KB)

biodata_largescale_0.01sparsity_l1l2reg.eps(12.2 KB)

biodata_largescale_0.01sparsity_l1linfreg.eps(11.6 KB)

biodata_largescale_0.1sparsity.eps(11.7 KB)

biodata_largescale_0.1sparsity_l1l2reg.eps(12.4 KB)

biodata_largescale_0.1sparsity_l1linfreg.eps(11.6 KB)

biodata_largescale_0.5sparsity.eps(11.8 KB)

biodata_largescale_0.5sparsity_l1l2reg.eps(12.2 KB)

biodata_largescale_0.5sparsity_l1linfreg.eps(12.2 KB)

biodata_smallscale_0.01sparsity.eps(11.3 KB)

biodata_smallscale_0.01sparsity_l1l2reg.eps(11.2 KB)

biodata_smallscale_0.01sparsity_l1linfreg.eps(11 KB)

biodata_smallscale_0.1sparsity.eps(11.7 KB)

biodata_smallscale_0.1sparsity_l1l2reg.eps(12.2 KB)

biodata_smallscale_0.1sparsity_l1linfreg.eps(12.3 KB)

biodata_smallscale_0.5sparsity.eps(11.7 KB)

biodata_smallscale_0.5sparsity_l1l2reg.eps(12.4 KB)

biodata_smallscale_0.5sparsity_l1linfreg.eps(12.3 KB)

boule_lgl3.eps(2.5 MB)

l1.eps(2.8 MB)

conclusion.tex(4.1 KB)

ellipsoid_1.eps(3.4 KB)

ellipsoid_1.fig(380 B)

ellipsoid_2.eps(3.5 KB)

ellipsoid_2.fig(423 B)

ellipsoid_3.eps(3.5 KB)

ellipsoid_3.fig(415 B)

exp_finalremarks.tex(1.2 KB)

exp_flow.tex(3.4 KB)

exp_intro.tex(2.1 KB)

exp_multitask.tex(5.1 KB)

exp_speed.tex(7.9 KB)

exp_structured.tex(6.5 KB)

extensions.tex(3.6 KB)

figure_full_axis_aligned_boxes.eps(14 KB)

figure_sequence.eps(14.9 KB)

graph_group_arrow.eps(111.5 KB)

im_dict.eps(92.1 KB)

intro_a.tex(11.4 KB)

intro_b.tex(3.6 KB)

intro_bb.tex(19.8 KB)

intro_c.tex(34.9 KB)

intro_nonconvex.tex(176 B)

intro_working_homotopy.tex(159 B)

l1l2H.eps(2.8 MB)

L1_algorithms_bcd.bib(4.2 KB)

l1l2.eps(2.8 MB)

l2.eps(2.8 MB)

lasso_piecewise.eps(13.6 KB)

mkl.tex(13.7 KB)

n100_p1000.eps(13.3 KB)

n1024_p10000.eps(12.1 KB)

n1024_p100000.eps(10.8 KB)

n2000_p10000_lowcorrelation_0.01sparsity.eps(11.5 KB)

n2000_p10000_lowcorrelation_0.5sparsity.eps(11.9 KB)

n2000_p10000_vhighcorrelation_0.01sparsity.eps(12.5 KB)

n2000_p10000_vhighcorrelation_0.5sparsity.eps(13.3 KB)

n200_p200_lowcorrelation_0.01sparsity.eps(12 KB)

n200_p200_lowcorrelation_0.5sparsity.eps(12.7 KB)

n200_p200_vhighcorrelation_0.01sparsity.eps(13.2 KB)

n200_p200_vhighcorrelation_0.5sparsity.eps(13.8 KB)

opt_bayesian.tex(3.5 KB)

opt_greedy_algorithms.tex(5.8 KB)

opt_methods_activeset.tex(5.4 KB)

opt_methods_bcd.tex(10.3 KB)

opt_methods_classical.tex(4.3 KB)

opt_methods_dcprogramming.tex(8.1 KB)

opt_methods_dictionary_learning.tex(4.1 KB)

opt_methods_etatrick.tex(11.6 KB)

opt_methods_lars.tex(7.5 KB)

opt_methods_prox.tex(27.9 KB)

patchesdata_smallscale_0.01sparsity.eps(11.9 KB)

patchesdata_smallscale_0.1sparsity.eps(11.9 KB)

patchesdata_smallscale_0.5sparsity.eps(12.2 KB)

topo_dict_3.eps(81.7 KB)

boule_lgl2.eps(2.5 MB)

PDF

Bach-Jenatton-Mairal-Obozinski-HAL.pdf(1.1 MB)

PS

Bach-Jenatton-Mairal-Obozinski-HAL.ps(2.2 MB)

• hal-00613125, version 2
• http://hal.archives-ouvertes.fr/hal-00613125
• oai:hal.archives-ouvertes.fr:hal-00613125
• Contributeur : Francis Bach <>
• Soumis le : Dimanche 20 Novembre 2011, 14:56:23
• Dernière modification le : Dimanche 4 Décembre 2011, 14:20:16