A Unified Approach to Fast Algorithms for Submodular Optimization based on Continuous Relaxations and Rounding

Rishabh Iyer, Stefanie Jegelka, Jeffrey Bilmes
Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence, PMLR R12:431-440, 2014.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR12-iyer14a, title = {A Unified Approach to Fast Algorithms for Submodular Optimization based on Continuous Relaxations and Rounding}, author = {Iyer, Rishabh and Jegelka, Stefanie and Bilmes, Jeffrey}, booktitle = {Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence}, pages = {431--440}, year = {2014}, editor = {Zhang, Nevin L. and Tian, Jin}, volume = {R12}, series = {Proceedings of Machine Learning Research}, month = {23--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r12/main/assets/iyer14a/iyer14a.pdf}, url = {https://proceedings.mlr.press/r12/iyer14a.html}, 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.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T A Unified Approach to Fast Algorithms for Submodular Optimization based on Continuous Relaxations and Rounding %A Rishabh Iyer %A Stefanie Jegelka %A Jeffrey Bilmes %B Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2014 %E Nevin L. Zhang %E Jin Tian %F pmlr-vR12-iyer14a %I PMLR %P 431--440 %U https://proceedings.mlr.press/r12/iyer14a.html %V R12 %X 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. %Z Reissued by PMLR on 04 October 2026.
APA
Iyer, R., Jegelka, S. & Bilmes, J.. (2014). A Unified Approach to Fast Algorithms for Submodular Optimization based on Continuous Relaxations and Rounding. Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R12:431-440 Available from https://proceedings.mlr.press/r12/iyer14a.html. Reissued by PMLR on 04 October 2026.

Related Material