Active-set Methods for Submodular Minimization Problems

K. S. Sesh Kumar 1, 2 Francis Bach 1, 2
2 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 the submodular function minimization~(SFM) and the quadratic minimization problems regularized by the Lovasz extension of the submodular function. These optimization problems are intimately related; for example, min-cut problems and total variation denoising problems, where the cut function is submodular and its Lovasz extension is given by the associated total variation. When a quadratic loss is regularized by the total variation of a cut function, it thus becomes a total variation denoising problem and we use the same terminology in this paper for "general'' submodular functions. We propose a new active-set algorithm for total variation denoising with the assumption of an oracle that solves the corresponding SFM problem. This can be seen as local descent algorithm over ordered partitions with explicit convergence guarantees. It is more flexible than the existing algorithms with the ability for warm-restarts using the solution of a closely related problem. Further, we also consider the case when a submodular function can be decomposed into the sum of two submodular functions F_1 and F_2 and assume SFM oracles for these two functions. We propose a new active-set algorithm for total variation denoising (and hence SFM by thresholding the solution at zero). This algorithm also performs local descent over ordered partitions and its ability to warm start considerably improves the performance of the algorithm. In the experiments, we compare the performance of the proposed algorithms with state-of-the-art algorithms, showing that it reduces the calls to SFM oracles.
Type de document :
Article dans une revue
Journal of Machine Learning Research (JMLR), 2017
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01161759
Contributeur : Ks Seshkumar <>
Soumis le : vendredi 18 novembre 2016 - 12:05:37
Dernière modification le : vendredi 25 mai 2018 - 12:02:06
Document(s) archivé(s) le : mercredi 15 mars 2017 - 04:25:51

Fichiers

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

Identifiants

  • HAL Id : hal-01161759, version 3
  • ARXIV : 1506.02852

Citation

K. S. Sesh Kumar, Francis Bach. Active-set Methods for Submodular Minimization Problems. Journal of Machine Learning Research (JMLR), 2017. 〈hal-01161759v3〉

Partager

Métriques

Consultations de la notice

341

Téléchargements de fichiers

423