# Curvature Beyond Positivity: Greedy Guarantees for Arbitrary Submodular Functions

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 24 references that are in the map.
- First posted on arXiv 8 May 2026.

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

- [Multi-News: a Large-Scale Multi-Document Summarization Dataset and Abstractive Hierarchical Model](https://mlsanity.com/paper/1906.01749/) (2019)
- [Optimal approximation for submodular and supermodular optimization with bounded curvature](https://mlsanity.com/paper/1311.4728/) (2013)
- [Continuous DR-submodular Maximization: Structure and Algorithms](https://mlsanity.com/paper/1711.02515/) (2017)
- [Submodular Maximization Beyond Non-negativity: Guarantees, Fast Algorithms, and Applications](https://mlsanity.com/paper/1904.09354/) (2019)
- [Regularized Submodular Maximization at Scale](https://mlsanity.com/paper/2002.03503/) (2020)
- [Constrained Submodular Maximization via New Bounds for DR-Submodular Functions](https://mlsanity.com/paper/2311.01129/) (2023)
- [Weakly Submodular Maximization Beyond Cardinality Constraints: Does Randomization Help Greedy?](https://mlsanity.com/paper/1707.04347/) (2017)
- [Using Partial Monotonicity in Submodular Maximization](https://mlsanity.com/paper/2202.03051/) (2022)
- [An Efficient Framework for Balancing Submodularity and Cost](https://mlsanity.com/paper/2002.07782/) (2020)
- [On Maximizing Sums of Non-monotone Submodular and Linear Functions](https://mlsanity.com/paper/2205.15874/) (2022)
- [Maximizing Symmetric Submodular Functions](https://mlsanity.com/paper/1409.5900/) (2014)
- [Regularized Non-monotone Submodular Maximization](https://mlsanity.com/paper/2103.10008/) (2021)
- [Maximizing Sums of Non-monotone Submodular and Linear Functions: Understanding the Unconstrained Case](https://mlsanity.com/paper/2204.03412/) (2022)

## Abstract (arXiv)

Submodular functions -- functions exhibiting diminishing returns -- are central to machine learning. When the objective is monotone and non-negative, the greedy algorithm achieves a tight 63% approximation. But many practical objectives incorporate costs that make them negative on some inputs, and all existing multiplicative guarantees require non-negativity. Prior work handles negativity through additive bounds for the special class of decomposable functions and non-monotonicity through partial-monotonicity parameters, but these address each difficulty in isolation and neither extends the classical structural theory. We extend curvature -- a parameter measuring how far a function deviates from linearity -- to all submodular functions, handling both non-monotonicity and negativity through a single classical concept. A greedy algorithm with pruning achieves a curvature-controlled multiplicative ratio for any submodular function, including those taking negative values -- the first such guarantee beyond monotonicity and non-negativity. In the non-monotone regime 1 ≤ cg < 2.2, the bound strictly beats the best known uniform ratio of 0.401 (for non-negative f), and it recovers the classical (1-e-cg)/cg guarantee for monotone functions. A multilinear-extension variant extends the framework to general combinatorial constraints via multilinear relaxation. Experiments on cost-penalized experimental design, coverage, feature selection, and a curvature sweep on Multi-News passage selection support the theory.