Monotone closure of relaxed constraints in submodular optimization: Connections between minimization and maximization

Rishabh Iyer, Stefanie Jegelka, Jeff Bilmes

Publikation: Beitrag in Buch/Bericht/KonferenzbandKonferenzbeitragBegutachtung

17 Zitate (Scopus)

Abstract

It is becoming increasingly evident that many machine learning problems may be reduced to submodular optimization. Previous work addresses generic discrete approaches and specific relaxations. In this work, we take a generic view from a relaxation perspective. We show a relaxation formulation and simple rounding strategy that, based on the monotone closure of relaxed constraints, reveals analogies between minimization and maximization problems, and includes known results as special cases and extends to a wider range of settings. Our resulting approximation factors match the corresponding integrality gaps. For submodular maximization, a number of relaxation approaches have been proposed. A critical challenge for the practical applicability of these techniques, however, is the complexity of evaluating the multilinear extension. We show that this extension can be efficiently evaluated for a number of useful submodular functions, thus making these otherwise impractical algorithms viable for real-world machine learning problems.

OriginalspracheEnglisch
TitelUncertainty in Artificial Intelligence - Proceedings of the 30th Conference, UAI 2014
Redakteure/-innenNevin L. Zhang, Jin Tian
Herausgeber (Verlag)AUAI Press
Seiten360-369
Seitenumfang10
ISBN (elektronisch)9780974903910
PublikationsstatusVeröffentlicht - 2014
Extern publiziertJa
Veranstaltung30th Conference on Uncertainty in Artificial Intelligence, UAI 2014 - Quebec City, Kanada
Dauer: 23 Juli 201427 Juli 2014

Publikationsreihe

NameUncertainty in Artificial Intelligence - Proceedings of the 30th Conference, UAI 2014

Konferenz

Konferenz30th Conference on Uncertainty in Artificial Intelligence, UAI 2014
Land/GebietKanada
OrtQuebec City
Zeitraum23/07/1427/07/14

Fingerprint

Untersuchen Sie die Forschungsthemen von „Monotone closure of relaxed constraints in submodular optimization: Connections between minimization and maximization“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren