# Using Partial Monotonicity in Submodular Maximization

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 54 references that are in the map.
- First posted on arXiv 7 Feb 2022.

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

- [Lazier Than Lazy Greedy](https://mlsanity.com/paper/1409.7938/) (2014)
- [Guarantees for Greedy Maximization of Non-submodular Functions with Applications](https://mlsanity.com/paper/1703.02100/) (2017)
- [Discrete Adversarial Attacks and Submodular Optimization with Applications to Text Classification](https://mlsanity.com/paper/1812.00151/) (2018)
- [Optimal approximation for submodular and supermodular optimization with bounded curvature](https://mlsanity.com/paper/1311.4728/) (2013)
- [Constrained Submodular Maximization via a Non-symmetric Technique](https://mlsanity.com/paper/1611.03253/) (2016)
- [Regularized Submodular Maximization at Scale](https://mlsanity.com/paper/2002.03503/) (2020)
- [Data Summarization at Scale: A Two-Stage Submodular Approach](https://mlsanity.com/paper/1806.02815/) (2018)
- [Weakly Submodular Maximization Beyond Cardinality Constraints: Does Randomization Help Greedy?](https://mlsanity.com/paper/1707.04347/) (2017)
- [Curvature and Optimal Algorithms for Learning and Minimizing Submodular Functions](https://mlsanity.com/paper/1311.2110/) (2013)
- [Greed is Good: Near-Optimal Submodular Maximization via Greedy Optimization](https://mlsanity.com/paper/1704.01652/) (2017)
- [Beyond 1/2-Approximation for Submodular Maximization on Massive Data Streams](https://mlsanity.com/paper/1808.01842/) (2018)
- [Streaming Weak Submodularity: Interpreting Neural Networks on the Fly](https://mlsanity.com/paper/1703.02647/) (2017)
- [Adaptive Sequence Submodularity](https://mlsanity.com/paper/1902.05981/) (2019)
- [Comparing Apples and Oranges: Query Tradeoff in Submodular Maximization](https://mlsanity.com/paper/1410.0773/) (2014)
- [Constrained Submodular Maximization: Beyond 1/e](https://mlsanity.com/paper/1608.03611/) (2016)
- [Fast Maximization of Non-Submodular, Monotonic Functions on the Integer Lattice](https://mlsanity.com/paper/1805.06990/) (2018)
- [Globally solving Non-Convex Quadratic Programs via Linear Integer Programming techniques](https://mlsanity.com/paper/1511.02423/) (2015)
- [A Parameterized Family of Meta-Submodular Functions](https://mlsanity.com/paper/2006.13754/) (2020)

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

- [Resolving the Approximability of Offline and Online Non-monotone DR-Submodular Maximization over General Convex Sets](https://mlsanity.com/paper/2210.05965/) (2022)
- [Submodular Minimax Optimization: Finding Effective Sets](https://mlsanity.com/paper/2305.16903/) (2023)
- [ORBSLAM3-Enhanced Autonomous Toy Drones: Pioneering Indoor Exploration](https://mlsanity.com/paper/2312.13385/) (2023)
- [G"odel Test: Can Large Language Models Solve Easy Conjectures?](https://mlsanity.com/paper/2509.18383/) (2025)
- [Practical 0.385-Approximation for Submodular Maximization Subject to a Cardinality Constraint](https://mlsanity.com/paper/2405.13994/) (2024)
- [Partial-Monotone Adaptive Submodular Maximization](https://mlsanity.com/paper/2207.12840/) (2022)
- [Bridging the Gap Between General and Down-Closed Convex Sets in Submodular Maximization](https://mlsanity.com/paper/2401.09251/) (2024)
- [Curvature Beyond Positivity: Greedy Guarantees for Arbitrary Submodular Functions](https://mlsanity.com/paper/2605.07902/) (2026)
- [Toward Trustworthy AI: Multi-Target Adversarial Attacks and Robust Defenses for Continuous Data Summarization](https://mlsanity.com/paper/2606.11804/) (2026)

## Abstract (arXiv)

Over the last two decades, submodular function maximization has been the workhorse of many discrete optimization problems in machine learning applications. Traditionally, the study of submodular functions was based on binary function properties. However, such properties have an inherit weakness, namely, if an algorithm assumes functions that have a particular property, then it provides no guarantee for functions that violate this property, even when the violation is very slight. Therefore, recent works began to consider continuous versions of function properties. Probably the most significant among these (so far) are the submodularity ratio and the curvature, which were studied extensively together and separately. The monotonicity property of set functions plays a central role in submodular maximization. Nevertheless, and despite all the above works, no continuous version of this property has been suggested to date (as far as we know). This is unfortunate since submoduar functions that are almost monotone often arise in machine learning applications. In this work we fill this gap by defining the monotonicity ratio, which is a continues version of the monotonicity property. We then show that for many standard submodular maximization algorithms one can prove new approximation guarantees that depend on the monotonicity ratio; leading to improved approximation ratios for the common machine learning applications of movie recommendation, quadratic programming and image summarization.