CaltechAUTHORS
  A Caltech Library Service

Efficient Minimization of Decomposable Submodular Functions

Stobbe, Peter and Krause, Andreas (2010) Efficient Minimization of Decomposable Submodular Functions. In: Advances in Neural Information Processing Systems 23. Neural Information Processing Systems , La Jolla, CA. ISBN 9781617823800. https://resolver.caltech.edu/CaltechAUTHORS:20160331-164338717

[img] PDF - Published Version
See Usage Policy.

339Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20160331-164338717

Abstract

Many combinatorial problems arising in machine learning can be reduced to the problem of minimizing a submodular function. Submodular functions are a natural discrete analog of convex functions, and can be minimized in strongly polynomial time. Unfortunately, state-of-the-art algorithms for general submodular minimization are intractable for larger problems. In this paper, we introduce a novel subclass of submodular minimization problems that we call decomposable. Decomposable submodular functions are those that can be represented as sums of concave functions applied to modular functions. We develop an algorithm, SLG, that can efficiently minimize decomposable submodular functions with tens of thousands of variables. Our algorithm exploits recent results in smoothed convex minimization. We apply SLG to synthetic benchmarks and a joint classification-and-segmentation task, and show that it outperforms the state-of-the-art general purpose submodular minimization algorithms by several orders of magnitude.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
https://papers.nips.cc/paper/4028-efficient-minimization-of-decomposable-submodular-functionsOrganizationPaper
Additional Information:©2010 Neural Information Processing Systems. This research was partially supported by NSF grant IIS-0953413, a gift from Microsoft Corporation and an Okawa Foundation Research Grant. Thanks to Alex Gittens and Michael McCoy for use of their TextonBoost implementation.
Funders:
Funding AgencyGrant Number
NSFIIS-0953413
Microsoft CorporationUNSPECIFIED
Okawa FoundationUNSPECIFIED
Record Number:CaltechAUTHORS:20160331-164338717
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20160331-164338717
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:65823
Collection:CaltechAUTHORS
Deposited By: Kristin Buxton
Deposited On:31 Mar 2016 23:48
Last Modified:03 Oct 2019 09:50

Repository Staff Only: item control page