PaperlayerView exact revision on arXiv

Source-linked AI summary

Distributed Submodular Maximization

Baharan Mirzasoleiman, Amin Karbasi, Rik Sarkar, Andreas Krause

arXiv:1411.0541v2cs.LGcs.AIcs.DCcs.IR

TL;DR

Large-scale subset-selection problems can be expressed as submodular maximization, yet centralized methods are impractical for massive datasets. The paper develops GreeDi, a low-communication distributed protocol for MapReduce, and reports competitive theoretical and empirical performance, including applications with tens of millions of examples.

  • Problem

    Centralized submodular maximization is impractical for massive datasets, while standard greedy methods are difficult to parallelize because they are sequential.

  • Method

    GreeDi partitions data across machines, processes partitions in parallel, and merges local solutions through a simple distributed protocol.

  • Results

    98% in exemplar based clustering, 97% in active set selection, and 90% in finding cuts are reported relative performance levels versus centralized methods.

  • Takeaways & Limitations

    GreeDi supports constrained submodular maximization on very large datasets, including sparse GP inference on 45 million examples and image summarization on 80 million images.

  • Takeaways & Limitations

    Theoretical competitiveness depends on natural additional assumptions, and worst-case distributed performance can retain dependence on min(k, m).

Abstract

from arXiv · show

Many large-scale machine learning problems--clustering, non-parametric learning, kernel machines, etc.--require selecting a small yet representative subset from a large dataset. Such problems can often be reduced to maximizing a submodular set function subject to various constraints. Classical approaches to submodular optimization require centralized access to the full dataset, which is impractical for truly large-scale problems. In this paper, we consider the problem of submodular function maximization in a distributed fashion. We develop a simple, two-stage protocol GreeDi, that is easily implemented using MapReduce style computations. We theoretically analyze our approach, and show that under certain natural conditions, performance close to the centralized approach can be achieved. We begin with monotone submodular maximization subject to a cardinality constraint, and then extend this approach to obtain approximation guarantees for (not necessarily monotone) submodular maximization subject to more general constraints including matroid or knapsack constraints. In our extensive experiments, we demonstrate the effectiveness of our approach on several applications, including sparse Gaussian process inference and exemplar based clustering on tens of millions of examples using Hadoop.

1. Introduction

Large-scale machine-learning tasks often reduce to submodular maximization, but centralized greedy methods become impractical as datasets grow. The paper introduces GreeDi, a MapReduce-friendly distributed protocol with competitive theoretical and empirical performance.

  • Submodular objectives capture representative-subset selection in clustering, non-parametric learning, viral marketing, and complex-model training.
  • Centralized greedy algorithms provide strong approximations but scale poorly because massive datasets exceed individual computers’ processing capabilities.
  • Greedy optimization is difficult to parallelize because each marginal gain depends on elements selected in earlier iterations.
  • GreeDi is a simple cardinality-constrained protocol requiring minimal communication and supporting MapReduce-style computation.
  • The approach extends to non-monotone objectives and matroid or knapsack constraints, while scaling applications to tens of millions of points.
  • 98% in exemplar based clustering, 97% in active set selection, and 90% in finding cuts are reported relative performance levels versus centralized methods.

2. Background and Related Work

Prior distributed submodular methods address specific problems or impose costly communication and data-stream assumptions. GreeDi is positioned as a broader framework for characterizing when distributed performance can remain competitive with centralized optimization.

  • MapReduce emerged as a prominent model for large-scale machine learning because it combines resiliency, expressivity, and programming ease.
  • Earlier distributed approaches include online methods requiring k communication stages, which is unrealistic for large k in MapReduce settings.
  • Streaming methods either impose strong data-generation assumptions or provide approximation guarantees for narrower cardinality-constrained settings.
  • Other work improves greedy running time, while distributed graph methods target specific problems through repeated passes or input filtering.
  • GreeDi provides a more general distributed framework and characterizes settings where performance competitive with centralized optimization can be obtained.

3. Submodular Maximization

The paper formulates large-scale subset selection as submodular maximization and reviews greedy and distributed solution strategies. It motivates distributed computation through nonparametric learning and contrasts synchronization-heavy or redundant naive approaches with GreeDi.

  • Exemplar-based clustering: For image summarization, k-medoid selects at most k exemplars minimizing total dissimilarity to assigned cluster centers.
  • Submodular functions: Submodular functions encode diminishing returns, and monotone nonnegative objectives are commonly maximized under cardinality or other feasibility constraints.
  • Centralized greedy maximization: Greedy selection repeatedly adds the element with maximum incremental value and achieves a (1 −1/e) approximation for non-negative monotone submodular functions.
  • Distributed formulation: Centralized greedy methods become infeasible on datasets too large for one computer, while their sequential dependence complicates parallelization.
  • Naive distributed approaches: A synchronized distributed implementation reproduces centralized greedy exactly but requires communication after each of k rounds, which is impractical when k is large.
  • Naive distributed approaches: Unsynchronized local selection needs only two rounds but can select redundant elements, producing solutions Ω(m) worse than centralized optimization.
  • GreeDi: GreeDi uses little communication and is designed to remain competitive with centralized optimization under additional natural assumptions.

4. The GreeDi Approach for Distributed Submodular Maximization

GreeDi distributes submodular maximization across machines and combines local solutions with limited communication. Its guarantees improve under geometric or decomposable structure, while experiments show strong performance relative to centralized methods.

  • Core protocol: GreeDi partitions the ground set across machines, computes local solutions in parallel, and combines them in a second round.The protocol is designed for MapReduce-style computation with minimal communication.
  • Worst-case guarantees: 1/min(m,k) is the tight worst-case approximation factor for the intractable two-round distributed protocol under monotone submodularity.The centralized solution is always at least as valuable as the distributed solution, and the bound is tight.
  • Worst-case guarantees: (1−1/e)min(m,k) is the GreeDi guarantee when the relaxed cardinality constraint satisfies κ = k.The approximate local selections replace the optimal local subsets used by the intractable protocol.
  • Geometric structure: Dense neighborhoods and Lipschitz objectives can make GreeDi approach the centralized optimum on very large datasets.As α → 0, the distributed solution is guaranteed to be within a 1−eκ/k factor of the optimal centralized solution.
  • Geometric structure: For Gaussian-process mutual information, Lipschitz continuity follows from a Lipschitz kernel, while k-medoid and k-means losses have λ = 1 and λ = 2R, respectively.These results instantiate the geometric conditions for practical objectives.
  • Random partitioning: (1−1/e)/2 is the average-case approximation guarantee when elements are randomly assigned to machines and κ = k.Random partitioning yields a constant-factor guarantee independent of m and k; geometric structure can provide sharper bounds.

5. (Non-Monotone) Submodular Functions with General Constraints

The paper extends GreeDi beyond monotone cardinality-constrained maximization to non-monotone submodular objectives under hereditary constraints, including matroids, p-systems, and knapsacks. It provides generalized approximation results under structural assumptions and evaluates relevant constraint settings.

  • General framework: GreeDi is extended to maximize non-monotone submodular functions subject to more general hereditary constraints.The framework assumes feasible solutions are closed under taking subsets.
  • Matroid constraints: Matroid constraints require hereditary and augmentation properties, supporting applications in content aggregation, viral marketing, and online advertising.The generalized greedy approach provides a 1/2-approximation for monotone submodular maximization under a single matroid.
  • Generalized independence constraints: Intersections of p matroids model settings such as rankings and multi-product viral marketing, while p-systems generalize these constraints.For p-systems, greedy gives a 1/(p+1)-approximation for monotone objectives, with separate bounds known for non-monotone objectives.
  • Knapsack constraints: Knapsack and combined p-system–knapsack constraints capture non-uniform resource budgets and applications including procurement, e-commerce, and viral marketing.Prior work summarized in the paper gives approximation guarantees that depend on the number of knapsacks and the p-system parameter.

6. Experiments

The experiments evaluate GreeDi against centralized and distributed benchmarks across clustering, active-set selection, graph cuts, and submodular coverage. Results show strong comparative performance and scalability, while speedup becomes sublinear when the second-stage computation dominates.

  • Experimental setup: GreeDi is evaluated against four naive distributed benchmarks across several submodular maximization scenarios.The benchmarks are random/random, random/greedy, greedy/merge, and greedy/max.
  • Experimental setup: GreeDi selects αk elements per machine, then greedily chooses k elements from their union, yielding the reported distributed-to-centralized ratio.The final candidate pool contains αkm elements.
  • Exemplar-based clustering: On 10,000 Tiny Images, GreeDi is compared across global and local objectives while varying partitions and budget.Figure 4 uses k = 50 with varying m, and m = 5 with varying k.
  • Active-set selection: On Parkinsons Telemonitoring and Yahoo! Webscope data, experiments vary partitions and budget to assess GreeDi against competing benchmarks.The Yahoo! experiment uses m = 32; the Parkinsons experiment uses 5,875 measurements and 22 attributes.
  • Scalability: For Yahoo! Webscope, GreeDi scales well, with reducer workloads selecting local active sets before a second-stage merge and selection.With m = 32, each reducer processes approximately 1,431,621 vectors and selects up to 256 elements.
  • Scalability: Speedup is nearly linear for few machines but declines as m grows because GreeDi’s second stage increasingly dominates runtime.Larger k produces higher speedup on fewer machines but causes a faster decline as m increases.
  • Maximum cuts: On Facebook-like graph data, GreeDi significantly outperforms distributed benchmarks despite the cut function being non-monotone and non-additively decomposable.The local evaluation disconnects links between partitions, and RandomGreedy is used within partitions.
  • Comparison with GreedyScaling: For submodular coverage, GreeDi outperforms GreedyScaling on Accidents and performs comparably on Kosarak.These comparisons use the datasets reported for GreedyScaling.

7. Conclusion

The paper concludes that GreeDi is an efficient distributed protocol for constrained submodular maximization. Its theoretical analysis and large-scale experiments show performance close to centralized optimization under certain conditions.

  • Conclusion: GreeDi is an efficient distributed protocol for constrained submodular function maximization.The paper combines theoretical analysis with experiments on large datasets, including 45 million examples for active-set selection.
  • Conclusion: Under certain natural conditions, GreeDi performs very close to the centralized solution.The centralized method is described as impractical for massive datasets.
  • Conclusion: Experiments demonstrate effectiveness in active-set selection for Gaussian processes and exemplar-based clustering.The reported applications include datasets with tens of millions of examples.

Appendix A. Proofs

The appendix provides the complete proofs of the theorems presented in the article.

  • Appendix: The appendix contains complete proofs for the article’s theorems.It serves as the paper’s proof section.

A.1 Proof of Theorem 3

The proof of Theorem 3 combines lemmas based on submodularity with an entropy-based construction. It establishes a lower bound relating distributed and centralized solutions.

  • Proof structure: The proof derives its forward direction from previously established lemmas.The passage explicitly states that the direction follows easily from those lemmas.
  • Partition bound: Submodularity bounds the centralized optimum by the sum of optimal contributions available within the partitions.For the optimal solution’s elements B_i, f(Ac[k]) ≤ f(B_1) + ... + f(B_m).
  • Partition bound: The proof bounds the centralized value using the best element’s marginal gain and the partition containing that element.It begins from f(Ac[k]) ≤ kf(u*) and considers the partition V_j containing u*.
  • Theorem result: The resulting theorem gives f(Ad[m,k]) ≥ 1/min(m,k) f(Ac[k]).The bound compares the distributed solution with the centralized cardinality-k solution.
  • Tightness construction: An entropy construction supplies a tightness example using independent Bernoulli variables and a monotone submodular entropy function.The construction yields H(Ad[m,k]) = k and H(Ac[k]) equal to km when m ≥ k, or k^2 otherwise.

A.2 Proof of Theorem 4

This section invokes a generalized performance bound for the standard greedy algorithm, based on the argument of Nemhauser et al. (1978).

  • The resulting generalization follows directly from the standard greedy performance argument.The section explicitly attributes the argument to Nemhauser et al. (1978).
  • Lemma 18 concerns a non-negative submodular function and the greedy set Agc[q] of cardinality q.The lemma is presented as the basis for the subsequent bound.
  • The proof applies Lemma 18 to the greedy-selected set and an auxiliary maximizer ˜A[κ] over subsets of Bgc with size at most κ.The auxiliary set is defined as ˜A[κ] = arg maxS⊆Bgc&|S|≤κf(S).

A.3 Proof of Proposition 6

This proof bounds how replacing one selected point changes the Gaussian-process differential entropy, using kernel Lipschitzness and eigenvalue-based determinant bounds. It concludes that the entropy is Lk^3-Lipschitz.

  • Replacing an element e1 in S with e′ changes the kernel matrix only through the corresponding row and column.The proof represents the change as ∆K = K′ − K with non-zero entries only on the first row and first column.
  • Kernel Lipschitz continuity bounds the perturbation entries by |ai| ≤ Ld(e1, e′).The proof also uses unit-norm vectors to bound their coordinates by one.
  • The proof bounds eigenvalues of ∆K and ∆K(I + K)−1 before substituting them into the log-determinant expression.Positive definiteness makes I + K invertible, while determinant changes are evaluated through eigenvalues.
  • Applying log(1 + x) ≤ x and summing replacements extends the one-point perturbation bound to replacing all k points in S.The objective difference is expressed through 1/2 log det(I + K′) − 1/2 log det(I + K).
  • The differential entropy of the Gaussian process is λ-Lipschitz with λ = Lk^3.This is the section’s stated final bound.

A.4 Proof of Proposition 7

This proof shows that the exemplar-based clustering loss changes in a controlled way when a set of k exemplars is replaced by another set of the same size. Under the metric-space assumptions, the loss is αR^(α−1)-Lipschitz.

  • For a set of k exemplars, the proof replaces exemplars one at a time and tracks how each data point’s assignment and loss may change.The intermediate sets are Si, obtained by swapping ei with e′i.
  • Four assignment cases cover whether a point’s exemplar assignment changes before, after, or during each replacement.The cases include unchanged assignments, reassignment to the new exemplar, and reassignment from or to another exemplar.
  • Unchanged assignments contribute no change to the loss function.This is the explicit conclusion for Case 1.
  • Distance differences are bounded using the triangle inequality and the assumption that data points lie in a metric-space ball of diameter R.The proof also uses the algebraic factorization of a^α − b^α.
  • The loss function is λ-Lipschitz with λ = αR^(α−1) for l = d^α.The bound follows after averaging the per-point inequality and extending it across all k replacements.

A.5 Proof of Theorem 8

This section establishes probabilistic conditions under which a randomly partitioned dataset contains a machine whose local solution is close to the centralized optimum. The argument extends to general non-negative submodular maximization under hereditary constraints and black-box approximation algorithms.

  • With probability at least 1 − δ, at least one random partition contains α-neighborhood elements near every element of Ac[k].The condition requires sufficiently many neighbors around each selected element, enabling a partition to represent the candidate solution.
  • A sufficiently large sample contains at least 4km log(k/δ^(1/m)) α-neighbors of each ei ∈ Ac[k] with probability at least 1 − δ.The result is obtained from expected neighborhood size, a Chernoff bound, and a union bound.
  • Under ε/λk ≤ α*, a random partition contains a subset near Ac[k] with sufficiently high probability.The proof combines the dense-neighborhood and partition-coverage lemmas.
  • For sufficiently large machines, some local candidate satisfies |f(Ac[k]) − f(Aci[κ])| ≤ ε with probability 1 − δ.The proof controls empirical objective deviations over candidate sets using Hoeffding bounds and a union bound.
  • Restricting objective evaluation to points on machine i incurs another ε under Theorem 9, while the solution remains ε away from optimum before that additional loss.The result combines Theorems 4 and 9.
  • For a black-box algorithm X with τ-approximation guarantee, the constrained analysis uses the feasible-set rank ρ([ζ]) and local replaceability assumptions.The corresponding neighborhood and approximation arguments yield bounds analogous to Theorem 12.
  • The same framework applies to non-negative submodular functions without monotonicity, under hereditary constraints such as those represented by ζ.The proof partitions an optimal feasible solution into feasible subsets and uses submodularity to relate their values.
  • A sufficiently large sample provides at least 4ρ([ζ])m log(ρ([ζ])/δ^(1/m)) neighbors around each optimal element with probability at least 1 − δ.For ε ≤ αλρ([ζ]), an ε-close feasible solution is also feasible under local replaceability.
Loading 1411.0541v2…