Curvature Beyond Positivity: Greedy Guarantees for Arbitrary Submodular Functions

Yixin Chen, Alan Kuhnle

Submodular functions -- functions exhibiting diminishing returns -- are central to machine learning. When the objective is monotone and non-negative, the greedy algorithm achieves…