# Greedy Minimization of Weakly Supermodular Set Functions

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Feb 2015.

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

- [Iterative Hard Thresholding with Adaptive Regularization: Sparser Solutions Without Sacrificing Runtime](https://mlsanity.com/paper/2204.08274/) (2022)
- [Online Subset Selection using α-Core with no Augmented Regret](https://mlsanity.com/paper/2209.14222/) (2022)
- [Performance of ℓ1 Regularization for Sparse Convex Optimization](https://mlsanity.com/paper/2307.07405/) (2023)
- [Greedy PIG: Adaptive Integrated Gradients](https://mlsanity.com/paper/2311.06192/) (2023)
- [SequentialAttention++ for Block Sparsification: Differentiable Pruning Meets Combinatorial Optimization](https://mlsanity.com/paper/2402.17902/) (2024)
- [A Greedy PDE Router for Blending Neural Operators and Classical Methods](https://mlsanity.com/paper/2509.24814/) (2025)

## Abstract (arXiv)

This paper defines weak-α-supermodularity for set functions. Many optimization objectives in machine learning and data mining seek to minimize such functions under cardinality constrains. We prove that such problems benefit from a greedy extension phase. Explicitly, let S^* be the optimal set of cardinality k that minimizes f and let S0 be an initial solution such that f(S0)/f(S^*) ≤ ρ. Then, a greedy extension S supset S0 of size |S| ≤ |S0| + lceil α k ln(ρ/varepsilon) rceil yields f(S)/f(S^*) ≤ 1+varepsilon. As example usages of this framework we give new bicriteria results for k-means, sparse regression, and columns subset selection.