🤖 machine learning

Curvature Beyond Positivity: Greedy Guarantees for Arbitrary Submodular Functions

This paper extends the concept of curvature to all submodular functions, including non-monotone and negative-valued ones, to provide the first multiplicative greedy approximation guarantees that unify and improve upon existing bounds for arbitrary submodular optimization.

Original authors: Yixin Chen, Alan Kuhnle

Published 2026-05-11

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Yixin Chen, Alan Kuhnle

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a chef trying to create the perfect salad. You have a basket of ingredients (the "ground set"), and you want to pick the best combination of $k$ ingredients to maximize the flavor (the "objective function").

In the world of computer science, this is called submodular optimization. The special rule here is "diminishing returns": the first slice of tomato adds a huge burst of flavor, but the tenth slice adds very little.

For decades, if your salad was guaranteed to taste good (positive flavor) and adding more ingredients never made it worse (monotone), a simple strategy called Greedy worked perfectly. You just kept adding the single ingredient that gave the biggest immediate flavor boost. This strategy was mathematically proven to get you about 63% of the best possible flavor.

The Problem: Salads That Can Taste Bad

In the real world, things aren't so simple.

Costs: Ingredients cost money. If you pick a very expensive truffle, the "net value" of your salad might actually go down because the cost outweighs the flavor.
Negative Outcomes: Sometimes, adding an ingredient makes the whole dish worse (e.g., too much salt ruins the soup).

When the total value can be negative, or when adding things can hurt the result, the old "Greedy" strategy breaks down. The math that guaranteed the 63% success rate collapses. Previous attempts to fix this were like patching a leaky boat with two different buckets: one bucket handled the "costs" (additive math), and another handled the "bad additions" (partial monotonicity). Neither bucket could fix the whole boat at once.

The Solution: A New Ruler Called "Curvature"

This paper introduces a single, elegant concept called Curvature to fix the whole problem.

Think of Curvature as a measure of how "bent" your flavor curve is.

Low Curvature (Straight Line): The flavor grows steadily. Adding ingredients is easy and predictable.
High Curvature (Steep Hill): The flavor grows fast at first but flattens out quickly (diminishing returns).
Negative Curvature (The Cliff): Adding ingredients eventually makes the salad taste terrible.

The authors realized that the old math failed because it assumed the curve was always straight or gently bending upward. They extended the definition of Curvature to handle any shape, even those that dip into negative territory (costs) or go up and down (non-monotone).

The New Strategy: "Greedy with Pruning"

The paper proposes a simple tweak to the classic Greedy algorithm. Instead of just adding ingredients, the new algorithm Greedy with Pruning works like this:

Add: Pick the ingredient that gives the biggest immediate boost.
Check: Look at all the ingredients currently in your bowl.
Prune: If any ingredient is now dragging the total value down (its "marginal contribution" is negative or zero), throw it out.

It's like cooking: you add a spice, taste it, and if you realize you added too much salt earlier, you scoop some of it out before adding the next ingredient. This "pruning" keeps the salad in a state where every remaining ingredient is still helping, even if the total value is negative.

What This Achieves

The paper proves that this "Greedy with Pruning" approach comes with a new mathematical guarantee based on the Curvature of the problem:

The Formula: The success rate is roughly $(1 - e^{-c}) / c$ , where $c$ is the curvature.
The Magic:
- If the problem is "nice" (monotone, low curvature), it recovers the classic 63% guarantee.
- If the problem is "messy" (negative values, high costs), it still provides a solid guarantee.
- Beating the Record: For certain types of messy problems (where the curvature is between 1 and 2.2), this new method actually beats the previous best-known success rate of 40.1% for non-negative problems.

Real-World Tests

The authors tested this on several real-world scenarios:

Sensor Placement: Deciding where to put sensors to monitor the environment, accounting for the cost of buying and installing them.
Feature Selection: Choosing the best data points for a machine learning model, balancing the model's accuracy against the cost of collecting data.
News Summarization: Picking the best news passages to summarize a story, balancing how much new information they add (relevance) against how much they repeat (redundancy).

In these tests, the "Pruning" method consistently performed better than older methods, especially when costs were high. It didn't just work; it provided a "certificate" (a mathematical proof) of how good the solution was, even without knowing the perfect solution in advance.

The Big Picture

This paper takes a classic, rigid mathematical tool (the Greedy algorithm) and makes it flexible enough to handle the messy, negative, and costly realities of the real world. By introducing Curvature as a universal ruler and adding a simple Pruning step, they created a method that works for almost any submodular problem, ensuring we can still find high-quality solutions even when the math gets complicated.

Technical Summary: Curvature Beyond Positivity: Greedy Guarantees for Arbitrary Submodular Functions

Problem Statement

Submodular optimization is a cornerstone of machine learning, addressing tasks such as sensor placement, data summarization, and feature selection. The canonical problem involves selecting a subset of size at most $k$ to maximize a submodular objective function $f$ . While the greedy algorithm provides a tight $(1 - 1/e) \approx 0.632$ approximation for monotone and non-negative functions, many practical objectives involve costs (e.g., deployment expenses, retrieval overhead, or regularization penalties) that render the objective function negative on certain inputs.

Existing literature has addressed two distinct challenges in isolation:

Negativity: Harshaw et al. [11] and subsequent works handle cost-penalized objectives ( $f = g - \ell$ ) via additive guarantees (e.g., $E[f(S)] \ge (1-1/e)g(OPT) - \ell(OPT)$ ). These bounds become vacuous when the cost ratio $\ell(OPT)/g(OPT)$ exceeds a threshold ( $\approx 0.632$ ) and fail to provide a multiplicative approximation ratio for $f$ itself.
Non-monotonicity: For non-monotone but non-negative functions, the best known approximation ratio is $0.401$ [3], achieved by sophisticated algorithms, while the hardness ceiling is $0.478$. However, these results strictly require $f(S) \ge 0$ for all $S$ .

The central gap addressed by this paper is the lack of a multiplicative approximation guarantee for submodular functions that are both non-monotone and potentially negative. Prior structural parameters, such as partial monotonicity [17], do not handle negativity, and classical curvature definitions diverge when marginals become negative.

Methodology: Extended Curvature and Pruning

The authors propose extending the concept of curvature—a parameter measuring deviation from linearity—to arbitrary submodular functions, handling both non-monotonicity and negativity through a single framework.

1. Generalized Curvature Definition

The paper redefines curvature $c_f$ for any submodular function $f$ (normalized with $f(\emptyset)=0$ ) as:
$c_f = 1 - \min_{\substack{X, Y \subseteq N \\ f(Y \setminus X) - f(\emptyset) > 0}} \frac{f(X \cup Y) - f(X)}{f(Y \setminus X) - f(\emptyset)}$
Key properties of this definition include:

Monotonicity Characterization: A submodular function is monotone if and only if $c_f \le 1$ . Thus, $c_f > 1$ captures the degree of non-monotonicity.
Handling Negativity: When $c_f > 1$ , the function can degrade in value upon adding elements, but the curvature parameter quantifies this degradation.
Trajectory-Restricted Curvature: To avoid worst-case bounds that may never occur during execution, the authors define a greedy curvature $c_g$ restricted to the specific trajectory of the algorithm.

2. Algorithmic Innovations

The paper introduces two primary algorithms leveraging pruning:

Discrete Greedy with Pruning (Algorithm 1):
- Mechanism: In each step, the algorithm greedily adds the element with the largest marginal gain. Crucially, after each addition, it prunes (removes) any element from the current set whose marginal contribution to the remaining elements has become non-positive.
- Invariant: This pruning ensures that the active set maintains a "local monotonicity" property: every non-empty subset of the active set has a positive value, and the function behaves monotonically within the active set.
- Applicability: Designed for cardinality constraints ( $|S| \le k$ ).
DMCG-P (Discretized Measured Continuous Greedy with Pruning):
- Motivation: Standard multilinear extensions for functions taking negative values have infinite global curvature ( $c_F = \infty$ ), breaking classical continuous greedy analysis.
- Mechanism: A discretized version of the measured continuous greedy algorithm that operates on the multilinear extension. It selects integral feasible directions, takes small steps, and prunes coordinates with non-positive slopes.
- Fractional Curvature: It utilizes a trajectory-restricted fractional curvature $c^F_g$ to bypass the obstruction of infinite global curvature.
- Applicability: Handles general combinatorial constraints (matroids, knapsacks) via convex relaxation.

Key Contributions

Unified Curvature Framework: The paper extends the classical Conforti–Cornuéjols curvature to all submodular functions. It provides a continuous characterization where $c_f \le 1$ corresponds exactly to the monotone regime, and $c_f > 1$ quantifies non-monotonicity and potential negativity.
First Multiplicative Guarantees for Negative Functions: The authors prove that Greedy with Pruning achieves a multiplicative approximation ratio of:
$\frac{1 - e^{-\bar{c}_g}}{\bar{c}_g}$
where $\bar{c}_g = \max\{1, c_g\}$ $\overset{c}{ˉ}_{g} = max {1, c_{g}}$ . This is the first such guarantee for submodular functions that take negative values.
- For monotone functions ( $c_g \le 1$ ), it recovers the classical $(1 - e^{-c_g})/c_g$ bound.
- For non-monotone functions, it strictly beats the best known uniform ratio of $0.401$ for non-negative functions when $1 \le c_g < c^* \approx 2.2$ .
General Constraints via DMCG-P: The framework is extended to general constraints using DMCG-P, achieving the same curvature-controlled ratio (minus a vanishing discretization error) for arbitrary submodular functions with finite trajectory curvature.
OPT-Free Certificates: For decomposable objectives ( $f = g - \ell$ ), the paper provides a closed-form, OPT-free certificate to bound the curvature from the pruned trajectory alone. This allows for a post-hoc verification of the approximation guarantee without knowing the optimal solution.

Experimental Results

The paper validates the theory through experiments on three application classes:

Symmetric Submodular Functions (MaxCut): For symmetric functions (e.g., graph cuts), the curvature is exactly $c_f = 2$ . The greedy-with-pruning algorithm achieves a ratio of $(1 - e^{-2})/2 \approx 0.432$ , recovering the known specialized bound for this class without explicitly using symmetry in the algorithm.
Decomposable Objectives (Cost-Penalized): In experimental design, coverage, and feature selection tasks with costs, the pruning algorithm matches or exceeds the performance of "distorted greedy" [11]. Crucially, while the additive guarantees of prior work become vacuous at moderate-to-high cost ratios, the curvature-based multiplicative guarantee remains positive and informative.
- Observation: At a cost ratio where the observed performance was 94%, the curvature guarantee was 58%, demonstrating the bound is conservative but valid.
GCLin Diversity (Multi-News Summarization): For relevance-minus-redundancy objectives, the trajectory curvature was observed to follow the theoretical reference curve ( $2\lambda$ ). The curvature-based guarantee was tighter than the partial-monotonicity bound (which vanishes for high redundancy) and provided meaningful diagnostics even when the optimal solution was intractable.

Significance and Claims

The paper claims to provide the first curvature-parameterized multiplicative guarantee that extends beyond monotonicity to negative-valued objectives. Its significance lies in:

Unification: It unifies the treatment of non-monotonicity and negativity under a single classical concept (curvature), whereas prior work treated them as separate, isolated difficulties.
Beyond Additive Bounds: It moves away from additive guarantees (which mix incommensurable benefit and cost terms and fail at high costs) to multiplicative guarantees that scale with the optimal value of the objective itself.
Structural Insight: It demonstrates that the performance of greedy algorithms is not solely determined by monotonicity but can be precisely characterized by how far the function deviates from linearity and monotonicity, even in the presence of negative values.
Practical Utility: The introduction of pruning allows simple greedy algorithms to achieve strong theoretical guarantees on complex, cost-penalized objectives, supported by post-hoc certificates that do not require access to the optimal solution.

The authors note that curvature is trajectory-specific (certifying the realized path rather than a pre-computed input parameter) and that extending these guarantees to streaming or distributed settings remains an open direction. However, for offline settings with cardinality or general combinatorial constraints, the framework offers a robust, instance-dependent refinement of submodular optimization theory.