Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings         Authors   Author's Info   Article details         Search    
Monotone Closure of Relaxed Constraints in Submodular Optimization: Connections Between Minimization and Maximization
Rishabh Iyer, Stefanie Jegelka, Jeff Bilmes
Abstract:
It is becoming increasingly evident that many ma- chine learning problems may be reduced to sub- modular optimization. Previous work addresses generic discrete approaches and specific relax- ations. 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 con- straints, 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 relax- ation approaches have been proposed. A critical challenge for the practical applicability of these techniques, however, is the complexity of evaluat- ing the multilinear extension. We show that this extension can be efficiently evaluated for a num- ber of useful submodular functions, thus making these otherwise impractical algorithms viable for real-world machine learning problems.
Keywords:
Pages: 360-369
PS Link:
PDF Link: /papers/14/p360-iyer.pdf
BibTex:
@INPROCEEDINGS{Iyer14,
AUTHOR = "Rishabh Iyer and Stefanie Jegelka and Jeff Bilmes",
TITLE = "Monotone Closure of Relaxed Constraints in Submodular Optimization: Connections Between Minimization and Maximization",
BOOKTITLE = "Proceedings of the Thirtieth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-14)",
PUBLISHER = "AUAI Press",
ADDRESS = "Corvallis, Oregon",
YEAR = "2014",
PAGES = "360--369"
}


hosted by DSL   •   site info   •   help