We propose a new random pruning method (called "submodular sparsification (SS)") to reduce the cost of submodular maximization. The pruning is applied via a "submodularity graph" over the @math ground elements, where each directed edge is associated with a pairwise dependency defined by the submodular function. In each step, SS prunes a @math (for @math ) fraction of the nodes using weights on edges computed based on only a small number ( @math ) of randomly sampled nodes. The algorithm requires @math steps with a small and highly parallelizable per-step computation. An accuracy-speed tradeoff parameter @math , set as @math , leads to a fast shrink rate @math and small iteration complexity @math . Analysis shows that w.h.p., the greedy algorithm on the pruned set of size @math can achieve a guarantee similar to that of processing the original dataset. In news and video summarization tasks, SS is able to substantially reduce both computational costs and memory usage, while maintaining (or even slightly exceeding) the quality of the original (and much more costly) greedy algorithm.
Another class of methods @cite_5 @cite_11 accelerates the greedy algorithm by maximizing a surrogate function whose evaluation is faster and cheaper than the original objective. The surrogate can be either a tight modular lower bound or a simpler submodular function. It can also be adaptively changed in each step to better approach the original objective. @cite_15 , a simple pruning method is used to reduce @math by exploiting @math , a lower bound of @math for @math . E.g., element @math whose singleton gain @math is less than the @math largest @math over all @math can be safely removed. Besides exploiting the global redundancy of @math via @math , the weight @math used in SS further takes the pairwise relationship @math into account. This can result in further ground set reduction.
@cite_5 @cite_15 @cite_11
2951977866 52746146
We present a practical and powerful new framework for both unconstrained and constrained submodular function optimization based on discrete semidifferentials (sub- and super-differentials). The resulting algorithms, which repeatedly compute and then efficiently optimize submodular semigradients, offer new and generalize many old methods for submodular optimization. Our approach, moreover, takes steps towards providing a unifying paradigm applicable to both submodular min- imization and maximization, problems that historically have been treated quite distinctly. The practicality of our algorithms is important since interest in submodularity, owing to its natural and wide applicability, has recently been in ascendance within machine learning. We analyze theoretical properties of our algorithms for minimization and maximization, and show that many state-of-the-art maximization algorithms are special cases. Lastly, we complement our theoretical analyses with supporting empirical experiments. 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 procedure 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 performance guarantee of the multi-stage framework and give examples on how to design instances of MULTGREED for a broad range of natural submodular 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 problems, 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.