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
52746146 2177862760 2176867214 2101246692
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. Greedy algorithms are practitioners’ best friends—they are intuitive, are simple to implement, and often lead to very good solutions. However, implementing greedy algorithms in a distributed setting is challenging since the greedy choice is inherently sequential, and it is not clear how to take advantage of the extra processing power. Our main result is a powerful sampling technique that aids in parallelization of sequential algorithms. Armed with this primitive, we then adapt a broad class of greedy algorithms to the MapReduce paradigm; this class includes maximum cover and submodular maximization subject to p-system constraint problems. Our method yields efficient algorithms that run in a logarithmic number of rounds while obtaining solutions that are arbitrarily close to those produced by the standard sequential greedy algorithm. We begin with algorithms for modular maximization subject to a matroid constraint and then extend this approach to obtain approximation algorithms for submodular maximization subject to knapsack or p-system constraints. We consider the problem of @math -class classification ( @math ), where the classifier can choose to abstain from making predictions at a given cost, say, a factor @math of the cost of misclassification. Designing consistent algorithms for such @math -class classification problems with a reject option' is the main goal of this paper, thereby extending and generalizing previously known results for @math . We show that the Crammer-Singer surrogate and the one vs all hinge loss, albeit with a different predictor than the standard argmax, yield consistent algorithms for this problem when @math . More interestingly, we design a new convex surrogate that is also consistent for this problem when @math and operates on a much lower dimensional space ( @math as opposed to @math ). We also generalize all three surrogates to be consistent for any @math . Greedy algorithms are practitioners' best friends - they are intuitive, simple to implement, and often lead to very good solutions. However, implementing greedy algorithms in a distributed setting is challenging since the greedy choice is inherently sequential, and it is not clear how to take advantage of the extra processing power. Our main result is a powerful sampling technique that aids in parallelization of sequential algorithms. We then show how to use this primitive to adapt a broad class of greedy algorithms to the MapReduce paradigm; this class includes maximum cover and submodular maximization subject to p-system constraints. Our method yields efficient algorithms that run in a logarithmic number of rounds, while obtaining solutions that are arbitrarily close to those produced by the standard sequential greedy algorithm. We begin with algorithms for modular maximization subject to a matroid constraint, and then extend this approach to obtain approximation algorithms for submodular maximization subject to knapsack or p-system constraints. Finally, we empirically validate our algorithms, and show that they achieve the same quality of the solution as standard greedy algorithms but run in a substantially fewer number of rounds.