The Power of Randomization: Distributed Submodular Maximization on Massive Datasets

A wide variety of problems in machine learning, including exemplar clustering, document summarization, and sensor placement, can be cast as constrained submodular maximization problems. Unfortunately, the resulting submodular optimization problems are often too large to be solved on a single machine. We consider a distributed, greedy algorithm that combines previous approaches with randomization. The result is an algorithm that is embarrassingly parallel and achieves provable, constant factor, worstcase approximation guarantees. In our experiments, we demonstrate its efficiency in large problems with different kinds of constraints with objective values always close to what is achievable in the centralized setting.

• Publication year

  2015

• Venue

  International Conference on Machine Learning

• Publication date

  2015-02-09

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 1502.02606
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Composable core-sets for diversity and coverage maximization

  2014cited by this paper
• Fast greedy algorithms in mapreduce and streaming

  2013cited by this paper
• A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization

  2012cited by this paper
• Constrained Non-monotone Submodular Maximization: Offline and Secretary Algorithms

  2010influential reference
• How to select a good training-data subset for transcription: submodular active selection for sequences

  2009cited by this paper
• 80 Million Tiny Images: A Large Data Set for Nonparametric Object and Scene Recognition

  2008cited by this paper
• MapReduce: simplified data processing on large clusters

  2008influential reference
• Finding Groups in Data: An Introduction to Cluster Analysis

  1990cited by this paper
• Maximising Real-Valued Submodular Functions: Primal and Dual Heuristics for Location Problems

  1982cited by this paper
• An analysis of approximations for maximizing submodular set functions—I

  1978cited by this paper

• Submodular Maximization Subject to Uniform and Partition Matroids: From Theory to Practical Applications and Distributed Solutions

  2025cites this paper
• MUSS: Multilevel Subset Selection for Relevance and Diversity

  2025cites this paper
• New Trends in Data Forgetting for Sustainable Data Management

  2025influential citation
• Federated Combinatorial Multi-Agent Multi-Armed Bandits

  2024cites this paper
• GreedyML: A Parallel Algorithm for Maximizing Constrained Submodular Functions

  2024cites this paper
• GIST: Greedy Independent Set Thresholding for Max-Min Diversification with Submodular Utility

  2024cites this paper
• Decomposable Submodular Maximization in Federated Setting

  2024cites this paper
• On Distributed Larger-Than-Memory Subset Selection With Pairwise Submodular Functions

  2024cites this paper
• Federated Submodular Maximization With Differential Privacy

  2024cites this paper
• Deterministic Algorithm and Faster Algorithm for Submodular Maximization Subject to a Matroid Constraint

  2024cites this paper
• Practical Parallel Algorithms for Non-Monotone Submodular Maximization

  2023cites this paper
• The One-Way Communication Complexity of Submodular Maximization with Applications to Streaming and Robustness

  2023cites this paper
• Algorithms for Cardinality-Constrained Monotone DR-Submodular Maximization with Low Adaptivity and Query Complexity

  2023cites this paper
• DASH: A Distributed and Parallelizable Algorithm for Size-Constrained Submodular Maximization

  2023influential citation
• Massively Parallel Computation: Algorithms and Applications

  2023cites this paper
• Composable Coresets for Determinant Maximization: Greedy is Almost Optimal

  2023cites this paper
• Practical Parallel Algorithms for Submodular Maximization Subject to a Knapsack Constraint with Nearly Optimal Adaptivity

  2023cites this paper
• Optimal Data Selection: An Online Distributed View

  2022cites this paper
• An Optimal Streaming Algorithm for Submodular Maximization with a Cardinality Constraint

  2022influential citation
• Scalable Distributed Algorithms for Size-Constrained Submodular Maximization in the MapReduce and Adaptive Complexity Models

  2022influential citation
• Composable Coresets for Constrained Determinant Maximization and Beyond

  2022cites this paper
• Distributed Influence Maximization for Large-Scale Online Social Networks

  2022cites this paper
• DASH: Distributed Adaptive Sequencing Heuristic for Submodular Maximization

  2022influential citation
• Online Active Learning with Dynamic Marginal Gain Thresholding

  2022cites this paper
• Extreme k-Center Clustering

  2021cites this paper
• Improved Streaming Algorithms for Maximizing Monotone Submodular Functions under a Knapsack Constraint

  2021cites this paper
• Best of Both Worlds: Practical and Theoretically Optimal Submodular Maximization in Parallel

  2021cites this paper
• On the complexity of dynamic submodular maximization

  2021cites this paper
• Learning to Sample: Data-Driven Sampling and Reconstruction of FRI Signals

  2021cites this paper
• Sensor Planning for Large Numbers of Robots

  2021cites this paper
• Decentralized algorithms for distributed integer programming problems with a coupling cardinality constraint

  2020cites this paper
• Distributed Pareto Optimization for Large-Scale Noisy Subset Selection

  2020cites this paper
• Regularized Submodular Maximization at Scale

  2020cites this paper
• Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model

  2020cites this paper
• A polynomial lower bound on adaptive complexity of submodular maximization

  2020cites this paper
• Simple and sharp analysis of k-means||

  2020cites this paper
• The one-way communication complexity of submodular maximization with applications to streaming and robustness

  2020cites this paper
• Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint

  2020cites this paper
• Submodular Meta-Learning

  2020cites this paper
• Active Learning for Estimating Reachable Sets for Systems With Unknown Dynamics

  2020influential citation
• Parallelized Maximization of Nonsubmodular Function Subject to a Cardinality Constraint

  2020cites this paper
• Sensitivity Analysis of Submodular Function Maximization

  2020cites this paper
• Online Non-Monotone DR-submodular Maximization

  2019cites this paper
• Optimal Algorithms for Submodular Maximization with Distributed Constraints

  2019cites this paper
• "Bring Your Own Greedy"+Max: Near-Optimal 1/2-Approximations for Submodular Knapsack

  2019cites this paper
• An Optimal Streaming Algorithm for Non-monotone Submodular Maximization

  2019cites this paper
• Decentralized Gradient Tracking for Continuous DR-Submodular Maximization

  2019cites this paper
• Distributed Maximization of "Submodular plus Diversity" Functions for Multi-label Feature Selection on Huge Datasets

  2019cites this paper
• Categorical Feature Compression via Submodular Optimization

  2019cites this paper
• Submodular Streaming in All its Glory: Tight Approximation, Minimum Memory and Low Adaptive Complexity

  2019cites this paper
• Adaptive Sequence Submodularity

  2019cites this paper
• Distributed Weighted Matching via Randomized Composable Coresets

  2019influential citation
• Composable Core-sets for Determinant Maximization: A Simple Near-Optimal Algorithm

  2019cites this paper
• Optimal Streaming Algorithms for Submodular Maximization with Cardinality Constraints

  2019cites this paper
• Non-submodular maximization on massive data streams

  2019cites this paper
• Approximation Guarantees of Stochastic Greedy Algorithms for Non-monotone Submodular Maximization with a Size Constraint

  2019cites this paper
• Parallelizing greedy for submodular set function maximization in matroids and beyond

  2018cites this paper
• Combinatorial Optimization On Massive Datasets: Streaming, Distributed, And Massively Parallel Computation

  2018influential citation
• Submodular Maximization with Optimal Approximation, Adaptivity and Query Complexity

  2018cites this paper
• Non-monotone Submodular Maximization with Nearly Optimal Adaptivity and Query Complexity

  2018cites this paper
• Multi-Pass Streaming Algorithms for Monotone Submodular Function Maximization

  2018cites this paper
• The adaptive complexity of maximizing a submodular function

  2018cites this paper
• Submodular Function Maximization in Parallel via the Multilinear Relaxation

  2018cites this paper
• Distributed Pareto Optimization for Subset Selection

  2018influential citation
• Optimal Distributed Submodular Optimization via Sketching

  2018cites this paper
• Approximation Guarantees for Adaptive Sampling

  2018cites this paper
• Data Summarization at Scale: A Two-Stage Submodular Approach

  2018cites this paper
• Tight Bounds on the Round Complexity of the Distributed Maximum Coverage Problem

  2018cites this paper
• An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation

  2018influential citation
• Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time

  2018cites this paper
• Beyond 1/2-Approximation for Submodular Maximization on Massive Data Streams

  2018cites this paper
• Scalable Deletion-Robust Submodular Maximization: Data Summarization with Privacy and Fairness Constraints

  2018influential citation
• Decentralized Submodular Maximization: Bridging Discrete and Continuous Settings

  2018cites this paper
• Composable Core-sets for Determinant Maximization Problems via Spectral Spanners

  2018cites this paper
• Non-monotone Submodular Maximization with Nearly Optimal Adaptivity Complexity

  2018cites this paper
• Distributed Submodular Maximization for Large Vocabulary Continuous Speech Recognition

  2018cites this paper
• Submodular Maximization with Nearly Optimal Approximation, Adaptivity and Query Complexity

  2018cites this paper
• Submodular maximization with matroid and packing constraints in parallel

  2018cites this paper
• Unconstrained submodular maximization with constant adaptive complexity

  2018cites this paper
• Distributed control and game design: From strategic agents to programmable machines

  2018cites this paper
• Bicriteria Distributed Submodular Maximization in a Few Rounds

  2017influential citation
• Streaming Weak Submodularity: Interpreting Neural Networks on the Fly

  2017cites this paper
• Deep Submodular Functions

  2017cites this paper
• Streaming Algorithms for Maximizing Monotone Submodular Functions Under a Knapsack Constraint

  2017cites this paper
• New algorithms for distributed submodular maximization

  2017influential citation
• A distributed algorithm for partitioned robust submodular maximization

  2017influential citation
• Submitted to the Annals of Statistics RESTRICTED STRONG CONVEXITY IMPLIES WEAK SUBMODULARITY By

  2017cites this paper
• Big Data Summarization Using Submodular Functions

  2017cites this paper
• Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs

  2017cites this paper
• Scalable Greedy Feature Selection via Weak Submodularity

  2017influential citation
• Leveraging Sparsity for Efficient Submodular Data Summarization

  2017cites this paper
• Cooperative Set Function Optimization Without Communication or Coordination

  2017cites this paper
• Deletion-Robust Submodular Maximization at Scale

  2017influential citation
• Robust submodular data partitioning for distributed speech recognition

  2016cites this paper
• Distributed Coverage Maximization via Sketching

  2016cites this paper
• Horizontally Scalable Submodular Maximization

  2016influential citation
• Scaling Submodular Maximization via Pruned Submodularity Graphs

  2016cites this paper
• Restricted Strong Convexity Implies Weak Submodularity

  2016cites this paper
• Greedy Column Subset Selection: New Bounds and Distributed Algorithms

  2016cites this paper
• Fast Distributed k-Center Clustering with Outliers on Massive Data

  2015cites this paper