Monotone closure of relaxed constraints in submodular optimization: connections between minimization and maximization
Rishabh Iyer, Stefanie Jegelka, Jeff Bilmes · 2014
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. 1