hal-00613125, version 1

Optimization with Sparsity-Inducing Penalties

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

• 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 : Documents sans référence de publication (Preprint)
• 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

Liste des fichiers attachés à ce document :

TEX

abstract.tex(858 B)

conclusion.tex(1.6 KB)

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(17.7 KB)

exp_structured.tex(8.5 KB)

extensions.tex(2.3 KB)

intro_a.tex(6.2 KB)

intro_b.tex(1.3 KB)

intro_bb.tex(19.3 KB)

intro_c.tex(28.7 KB)

intro_c_new_version.tex(4 KB)

intro_nonconvex.tex(175 B)

intro_working_homotopy.tex(159 B)

L1_algorithms_bcd.bib(4.2 KB)

macros.tex(11.9 KB)

mkl.tex(17.2 KB)

opt_bayesian.tex(2.1 KB)

opt_greedy_algorithms.tex(5.9 KB)

opt_methods_activeset.tex(8.7 KB)

opt_methods_bcd.tex(11.3 KB)

opt_methods_classical.tex(3.2 KB)

opt_methods_dcprogramming.tex(5.8 KB)

opt_methods_dictionary_learning.tex(3.8 KB)

opt_methods_etatrick.tex(11.9 KB)

opt_methods_lars.tex(7.7 KB)

opt_methods_prox.tex(25.4 KB)

optsparse.bbl(26.8 KB)

optsparse.bib(47.8 KB)

optsparse.tex(5 KB)

bach

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_mediumscale_0.01sparsity.eps(10.9 KB)

biodata_mediumscale_0.1sparsity.eps(10.8 KB)

biodata_mediumscale_0.5sparsity.eps(10.8 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)

ellipsoid_1.eps(3.4 KB)

ellipsoid_2.eps(3.5 KB)

ellipsoid_3.eps(3.5 KB)

figure_full_axis_aligned_boxes.eps(14 KB)

figure_sequence.eps(14.9 KB)

graph_group_arrow.eps(146.7 KB)

im_dict.eps(92.1 KB)

l1l2H.eps(14 KB)

l1l2.eps(15.3 KB)

l2.eps(13.7 KB)

lasso_piecewise.eps(13.6 KB)

n100_p1000.eps(13.3 KB)

n1024_p10000.eps(12.1 KB)

n1024_p100000.eps(10.8 KB)

n2000_p10000_highcorrelation_0.01sparsity.eps(12 KB)

n2000_p10000_highcorrelation_0.1sparsity.eps(12.6 KB)

n2000_p10000_highcorrelation_0.5sparsity.eps(12.9 KB)

n2000_p10000_lowcorrelation_0.01sparsity.eps(11.5 KB)

n2000_p10000_lowcorrelation_0.1sparsity.eps(11.7 KB)

n2000_p10000_lowcorrelation_0.5sparsity.eps(11.9 KB)

n2000_p10000_mediumcorrelation_0.01sparsity.eps(12.4 KB)

n2000_p10000_mediumcorrelation_0.1sparsity.eps(12.4 KB)

n2000_p10000_mediumcorrelation_0.5sparsity.eps(12.7 KB)

n2000_p10000_vhighcorrelation_0.01sparsity.eps(12.5 KB)

n2000_p10000_vhighcorrelation_0.1sparsity.eps(12.9 KB)

n2000_p10000_vhighcorrelation_0.5sparsity.eps(13.3 KB)

n200_p200_highcorrelation_0.01sparsity.eps(13.3 KB)

n200_p200_highcorrelation_0.1sparsity.eps(13.2 KB)

n200_p200_highcorrelation_0.5sparsity.eps(13.7 KB)

n200_p200_lowcorrelation_0.01sparsity.eps(12 KB)

n200_p200_lowcorrelation_0.1sparsity.eps(12.2 KB)

n200_p200_lowcorrelation_0.5sparsity.eps(12.7 KB)

n200_p200_mediumcorrelation_0.01sparsity.eps(12.7 KB)

n200_p200_mediumcorrelation_0.1sparsity.eps(12.7 KB)

n200_p200_mediumcorrelation_0.5sparsity.eps(13.4 KB)

n200_p200_vhighcorrelation_0.01sparsity.eps(13.2 KB)

n200_p200_vhighcorrelation_0.1sparsity.eps(13.3 KB)

n200_p200_vhighcorrelation_0.5sparsity.eps(13.8 KB)

topo_dict_3.eps(81.7 KB)

l1.eps(13.5 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)

PDF

optsparse.pdf(972.3 KB)

PS

optsparse.ps(2.1 MB)

• hal-00613125, version 1
• http://hal.archives-ouvertes.fr/hal-00613125
• oai:hal.archives-ouvertes.fr:hal-00613125
• Contributeur : Francis Bach <>
• Soumis le : Mardi 2 Août 2011, 21:48:05
• Dernière modification le : Mercredi 3 Août 2011, 09:55:23