# Instance Specific Approximations for Submodular Maximization

arXiv: https://arxiv.org/abs/2102.11911 · HTML: https://mlsanity.com/paper/2102.11911/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 63 references that are in the map.
- First posted on arXiv 23 Feb 2021.

## Builds on (most cited first, 24 of 24)

- [Lazier Than Lazy Greedy](https://mlsanity.com/paper/1409.7938/) (2014)
- [Restricted Strong Convexity Implies Weak Submodularity](https://mlsanity.com/paper/1612.00804/) (2016)
- [Robust Optimization for Non-Convex Objectives](https://mlsanity.com/paper/1707.01047/) (2017)
- [Randomized Composable Core-sets for Distributed Submodular Maximization](https://mlsanity.com/paper/1506.06715/) (2015)
- [Robust Submodular Maximization: A Non-Uniform Partitioning Approach](https://mlsanity.com/paper/1706.04918/) (2017)
- [Submodular Streaming in All its Glory: Tight Approximation, Minimum Memory and Low Adaptive Complexity](https://mlsanity.com/paper/1905.00948/) (2019)
- [The Limitations of Optimization from Samples](https://mlsanity.com/paper/1512.06238/) (2015)
- [Streaming Robust Submodular Maximization: A Partitioned Thresholding Approach](https://mlsanity.com/paper/1711.02598/) (2017)
- [An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation](https://mlsanity.com/paper/1804.06355/) (2018)
- [The FAST Algorithm for Submodular Maximization](https://mlsanity.com/paper/1907.06173/) (2019)
- [Do Less, Get More: Streaming Submodular Maximization with Subsampling](https://mlsanity.com/paper/1802.07098/) (2018)
- [Submodular Optimization under Noise](https://mlsanity.com/paper/1601.03095/) (2016)
- [Non-monotone Submodular Maximization in Exponentially Fewer Iterations](https://mlsanity.com/paper/1807.11462/) (2018)
- [Submodular Maximization with Matroid and Packing Constraints in Parallel](https://mlsanity.com/paper/1808.09987/) (2018)
- [A New Framework for Distributed Submodular Maximization](https://mlsanity.com/paper/1507.03719/) (2015)
- [Leveraging Sparsity for Efficient Submodular Data Summarization](https://mlsanity.com/paper/1703.02690/) (2017)
- [Submodular Function Maximization in Parallel via the Multilinear Relaxation](https://mlsanity.com/paper/1807.08678/) (2018)
- [Submodular Optimization in the MapReduce Model](https://mlsanity.com/paper/1810.01489/) (2018)
- [Unconstrained Submodular Maximization with Constant Adaptive Complexity](https://mlsanity.com/paper/1811.06603/) (2018)
- [Streaming Algorithms for Submodular Function Maximization](https://mlsanity.com/paper/1504.08024/) (2015)
- [On the Unreasonable Effectiveness of the Greedy Algorithm: Greedy Adapts to Sharpness](https://mlsanity.com/paper/2002.04063/) (2020)
- [Budget-Smoothed Analysis for Submodular Maximization](https://mlsanity.com/paper/2102.05782/) (2021)
- [Stability and Recovery for Independence Systems](https://mlsanity.com/paper/1705.00127/) (2017)
- [A New Approximation Guarantee for Monotone Submodular Function Maximization via Discrete Convexity](https://mlsanity.com/paper/1709.02910/) (2017)

## Built on by (most cited first, 2 of 2)

- [Robust Approximation Algorithms for Non-monotone k-Submodular Maximization under a Knapsack Constraint](https://mlsanity.com/paper/2309.12025/) (2023)
- [Data-dependent Evaluations for Budgeted Submodular Maximization](https://mlsanity.com/paper/2607.05759/) (2026)

## Abstract (arXiv)

For many optimization problems in machine learning, finding an optimal solution is computationally intractable and we seek algorithms that perform well in practice. Since computational intractability often results from pathological instances, we look for methods to benchmark the performance of algorithms against optimal solutions on real-world instances. The main challenge is that an optimal solution cannot be efficiently computed for intractable problems, and we therefore often do not know how far a solution is from being optimal. A major question is therefore how to measure the performance of an algorithm in comparison to an optimal solution on instances we encounter in practice. In this paper, we address this question in the context of submodular optimization problems. For the canonical problem of submodular maximization under a cardinality constraint, it is intractable to compute a solution that is better than a 1-1/e ≈ 0.63 fraction of the optimum. Algorithms like the celebrated greedy algorithm are guaranteed to achieve this 1-1/e bound on any instance and are used in practice. Our main contribution is not a new algorithm for submodular maximization but an analytical method that measures how close an algorithm for submodular maximization is to optimal on a given problem instance. We use this method to show that on a wide variety of real-world datasets and objectives, the approximation of the solution found by greedy goes well beyond 1-1/e and is often at least 0.95. We develop this method using a novel technique that lower bounds the objective of a dual minimization problem to obtain an upper bound on the value of an optimal solution to the primal maximization problem.