GreeDi Two-Stage Distributed Greedy Submodular Maximization

For any monotone submodular function f under an arbitrary partition of V into m sets, the intractable local-optimum merge protocol (Algorithm 1) satisfies the tight bound f(A^d[m, k]) >= (1 / min(m, k))*f(A^c[k]) with a matching entropy upper bound f(A^c[k]) = min(m, k)*f(A^d[m, k]) (Theorem 3, Appendix A.1), while two-stage GreeDi (Algorithm 2) with local budget kappa >= k guarantees f(A^{gd}[m, kappa]) >= ((1 - e^{-kappa/k}) / min(m, k))*f(A^c[k]) (Theorem 4), generalizes to f(A^{Xd}[m, zeta]) >= (tau / min(m, rho([zeta])))*f(A^c[zeta]) for any tau-approximate solver X over hereditary constraints zeta of maximum independent size rho([zeta]) (Algorithm 3, Theorem 12), and achieves average-case E[f(A^{gd}[m, k])] >= ((1 - 1/e)/2)*f(A^c[k]) under uniform random partitioning without geometric assumptions (Theorem 11).

For set functions that are lambda-Lipschitz with respect to a metric d on V under equal-size element matchings, |f(S) - f(S')| <= lambda * sum_{i=1}^k d(e_i, e_i') (Definition 5)—including Gaussian process mutual information with lambda = L*k^3 for L-Lipschitz kernels (Proposition 6) and d^alpha-dissimilarity clustering utility with lambda = alpha*R^{alpha-1} (Proposition 7)—if elements are randomly partitioned onto m machines and each optimal element e_i in A^c[k] has an alpha-neighborhood N_alpha(e_i) of size at least k*m*log(k / delta^{1/m}), then with probability at least 1 - delta, GreeDi achieves f(A^{gd}[m, kappa]) >= (1 - e^{-kappa/k})*(f(A^c[k]) - lambda*alpha*k) (Theorem 8, and Theorem 13 for locally replaceable constraints zeta).

When V consists of n >= 8*k*m*log(k/delta^{1/m}) / (beta * g(varepsilon / (lambda*k))) i.i.d. samples from a metric space with probability density >= beta and ball-volume growth function g(alpha), GreeDi achieves f(A^{gd}[m, kappa]) >= (1 - e^{-kappa/k})*(f(A^c[k]) - varepsilon) with probability at least 1 - delta (Theorem 9); furthermore, for decomposable submodular functions f(S) = (1/|V|)*sum_{i in V} f_i(S) evaluated purely locally on each machine's partition V_i, when n >= max(n_0, m*log(delta/(4m))/varepsilon^2) with ln(n)/n <= varepsilon^2/(m*k), GreeDi achieves f(A^{gd}[m, kappa]) >= (1 - e^{-kappa/k})*(f(A^c[k]) - 2*varepsilon) (Theorem 10, and Theorem 15 for general hereditary constraints).