On fast approximate submodular minimization

Stefanie Jegelka; Hui Lin; Jeff Bilmes

On fast approximate submodular minimization

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

35 Scopus citations

Abstract

We are motivated by an application to extract a representative subset of machine learning training data and by the poor empirical performance we observe of the popular minimum norm algorithm. In fact, for our application, minimum norm can have a running time of about O(n⁷) (O(n⁵) oracle calls). We therefore propose a fast approximate method to minimize arbitrary submodular functions. For a large sub-class of submodular functions, the algorithm is exact. Other submodular functions are iteratively approximated by tight submodular upper bounds, and then repeatedly optimized. We show theoretical properties, and empirical results suggest significant speedups over minimum norm while retaining higher accuracies.

Original language	English
Title of host publication	Advances in Neural Information Processing Systems 24
Subtitle of host publication	25th Annual Conference on Neural Information Processing Systems 2011, NIPS 2011
Publisher	Neural Information Processing Systems
ISBN (Print)	9781618395993
State	Published - 2011
Externally published	Yes
Event	25th Annual Conference on Neural Information Processing Systems 2011, NIPS 2011 - Granada, Spain Duration: 12 Dec 2011 → 14 Dec 2011

Publication series

Name	Advances in Neural Information Processing Systems 24: 25th Annual Conference on Neural Information Processing Systems 2011, NIPS 2011

Conference

Conference	25th Annual Conference on Neural Information Processing Systems 2011, NIPS 2011
Country/Territory	Spain
City	Granada
Period	12/12/11 → 14/12/11

Cite this

Jegelka, S., Lin, H., & Bilmes, J. (2011). On fast approximate submodular minimization. In Advances in Neural Information Processing Systems 24: 25th Annual Conference on Neural Information Processing Systems 2011, NIPS 2011 (Advances in Neural Information Processing Systems 24: 25th Annual Conference on Neural Information Processing Systems 2011, NIPS 2011). Neural Information Processing Systems.

Jegelka, Stefanie ; Lin, Hui ; Bilmes, Jeff. / On fast approximate submodular minimization. Advances in Neural Information Processing Systems 24: 25th Annual Conference on Neural Information Processing Systems 2011, NIPS 2011. Neural Information Processing Systems, 2011. (Advances in Neural Information Processing Systems 24: 25th Annual Conference on Neural Information Processing Systems 2011, NIPS 2011).

@inproceedings{acff7175617247b19ad1c7bc8b5a946c,

title = "On fast approximate submodular minimization",

abstract = "We are motivated by an application to extract a representative subset of machine learning training data and by the poor empirical performance we observe of the popular minimum norm algorithm. In fact, for our application, minimum norm can have a running time of about O(n7) (O(n5) oracle calls). We therefore propose a fast approximate method to minimize arbitrary submodular functions. For a large sub-class of submodular functions, the algorithm is exact. Other submodular functions are iteratively approximated by tight submodular upper bounds, and then repeatedly optimized. We show theoretical properties, and empirical results suggest significant speedups over minimum norm while retaining higher accuracies.",

author = "Stefanie Jegelka and Hui Lin and Jeff Bilmes",

year = "2011",

language = "English",

isbn = "9781618395993",

series = "Advances in Neural Information Processing Systems 24: 25th Annual Conference on Neural Information Processing Systems 2011, NIPS 2011",

publisher = "Neural Information Processing Systems",

booktitle = "Advances in Neural Information Processing Systems 24",

note = "25th Annual Conference on Neural Information Processing Systems 2011, NIPS 2011 ; Conference date: 12-12-2011 Through 14-12-2011",

}

Jegelka, S, Lin, H & Bilmes, J 2011, On fast approximate submodular minimization. in Advances in Neural Information Processing Systems 24: 25th Annual Conference on Neural Information Processing Systems 2011, NIPS 2011. Advances in Neural Information Processing Systems 24: 25th Annual Conference on Neural Information Processing Systems 2011, NIPS 2011, Neural Information Processing Systems, 25th Annual Conference on Neural Information Processing Systems 2011, NIPS 2011, Granada, Spain, 12/12/11.

On fast approximate submodular minimization. / Jegelka, Stefanie; Lin, Hui; Bilmes, Jeff.
Advances in Neural Information Processing Systems 24: 25th Annual Conference on Neural Information Processing Systems 2011, NIPS 2011. Neural Information Processing Systems, 2011. (Advances in Neural Information Processing Systems 24: 25th Annual Conference on Neural Information Processing Systems 2011, NIPS 2011).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - On fast approximate submodular minimization

AU - Jegelka, Stefanie

AU - Lin, Hui

AU - Bilmes, Jeff

PY - 2011

Y1 - 2011

N2 - We are motivated by an application to extract a representative subset of machine learning training data and by the poor empirical performance we observe of the popular minimum norm algorithm. In fact, for our application, minimum norm can have a running time of about O(n7) (O(n5) oracle calls). We therefore propose a fast approximate method to minimize arbitrary submodular functions. For a large sub-class of submodular functions, the algorithm is exact. Other submodular functions are iteratively approximated by tight submodular upper bounds, and then repeatedly optimized. We show theoretical properties, and empirical results suggest significant speedups over minimum norm while retaining higher accuracies.

AB - We are motivated by an application to extract a representative subset of machine learning training data and by the poor empirical performance we observe of the popular minimum norm algorithm. In fact, for our application, minimum norm can have a running time of about O(n7) (O(n5) oracle calls). We therefore propose a fast approximate method to minimize arbitrary submodular functions. For a large sub-class of submodular functions, the algorithm is exact. Other submodular functions are iteratively approximated by tight submodular upper bounds, and then repeatedly optimized. We show theoretical properties, and empirical results suggest significant speedups over minimum norm while retaining higher accuracies.

UR - http://www.scopus.com/inward/record.url?scp=85162526249&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85162526249

SN - 9781618395993

T3 - Advances in Neural Information Processing Systems 24: 25th Annual Conference on Neural Information Processing Systems 2011, NIPS 2011

BT - Advances in Neural Information Processing Systems 24

PB - Neural Information Processing Systems

T2 - 25th Annual Conference on Neural Information Processing Systems 2011, NIPS 2011

Y2 - 12 December 2011 through 14 December 2011

ER -

Jegelka S, Lin H, Bilmes J. On fast approximate submodular minimization. In Advances in Neural Information Processing Systems 24: 25th Annual Conference on Neural Information Processing Systems 2011, NIPS 2011. Neural Information Processing Systems. 2011. (Advances in Neural Information Processing Systems 24: 25th Annual Conference on Neural Information Processing Systems 2011, NIPS 2011).

On fast approximate submodular minimization

Abstract

Publication series

Conference

Other files and links

Fingerprint

Cite this