Curvature Beyond Positivity: Greedy Guarantees for Arbitrary Submodular Functions

Yixin Chen, Alan Kuhnle · 2026

Read Curvature Beyond Positivity: Greedy Guarantees for Arbitrary Submodular Functions by Yixin Chen, Alan Kuhnle (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-07902.txt.

Description

Yixin Chen and Alan Kuhnle extend greedy algorithm guarantees to submodular objectives that can go negative. Submodular functions, which capture shrinking returns, sit under many machine learning goals, and the classic greedy guarantee needs monotonicity and non-negativity. Real goals with costs break both, and earlier work patched each flaw only separately, for special cases.

The authors extend the curvature parameter, which measures departure from linearity, to all such functions at once. A greedy algorithm with pruning then achieves a curvature-controlled guarantee for any submodular function. It is the first beyond monotonicity and non-negativity, recovering the classic bound in the monotone case and beating the best known uniform ratio in part of the non-monotone regime. A multilinear variant covers general combinatorial constraints, and experiments on design, coverage, and feature selection support the theory.

Catalog record

CREATORYixin Chen, Alan Kuhnle
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE151 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.07902

Browse the full library · About the Tower of Babel