# Weakly Submodular Function Maximization Using Local Submodularity Ratio

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Apr 2020.

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

- [Efficient Adversarial Contrastive Learning via Robustness-Aware Coreset Selection](https://mlsanity.com/paper/2302.03857/) (2023)
- [FilFL: Client Filtering for Optimized Client Participation in Federated Learning](https://mlsanity.com/paper/2302.06599/) (2023)
- [Combatting Dimensional Collapse in LLM Pre-Training Data via Diversified File Selection](https://mlsanity.com/paper/2504.20644/) (2025)
- [G"odel Test: Can Large Language Models Solve Easy Conjectures?](https://mlsanity.com/paper/2509.18383/) (2025)
- [Unifying and Optimizing Data Values for Selection via Sequential Decision-Making](https://mlsanity.com/paper/2502.04554/) (2025)
- [COMRECGC: Global Graph Counterfactual Explainer through Common Recourse](https://mlsanity.com/paper/2505.07081/) (2025)
- [Online Subset Selection using α-Core with no Augmented Regret](https://mlsanity.com/paper/2209.14222/) (2022)

## Abstract (arXiv)

Weak submodularity is a natural relaxation of the diminishing return property, which is equivalent to submodularity. Weak submodularity has been used to show that many (monotone) functions that arise in practice can be efficiently maximized with provable guarantees. In this work we introduce two natural generalizations of weak submodularity for non-monotone functions. We show that an efficient randomized greedy algorithm has provable approximation guarantees for maximizing these functions subject to a cardinality constraint. We then provide a more refined analysis that takes into account that the weak submodularity parameter may change (sometimes improving) throughout the execution of the algorithm. This leads to improved approximation guarantees in some settings. We provide applications of our results for monotone and non-monotone maximization problems.