Title: Fast multi-stage submodular maximization: Extended version

Authors: K. Wei, R. Iyer, and J. Bilmes


Motivated by extremely large-scale machine learning problems, we introduce a new multi- stage algorithmic framework for submodular maximization (called MULTGREED), where at each stage we apply an approximate greedy proce- dure to maximize surrogate submodular functions. The surrogates serve as proxies for a target sub- modular function but require less memory and are easy to evaluate. We theoretically analyze the per- formance guarantee of the multi-stage framework and give examples on how to design instances of MULTGREED for a broad range of natural sub- modular functions. We show that MULTGREED performs very closely to the standard greedy algorithm given appropriate surrogate functions and argue how our framework can easily be integrated with distributive algorithms for further optimization. We complement our theory by empirically evaluating on several real-world prob- lems, including data subset selection on millions of speech samples where MULTGREED yields at least a thousand times speedup and superior results over the state-of-the-art selection methods

Full Text: [PDF]

Accessibility at Yale   Inference, Information, and Decision Group at Yale