# Guarantees for Greedy Maximization of Non-submodular Functions with Applications

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

## Key facts

- Cited by 35 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Mar 2017.

## Built on by (most cited first, 30 of 35)

- [Data-Efficient Structured Pruning via Submodular Optimization](https://mlsanity.com/paper/2203.04940/) (2022)
- [Submodular Reinforcement Learning](https://mlsanity.com/paper/2307.13372/) (2023)
- [Training Data Subset Selection for Regression with Controlled Generalization Error](https://mlsanity.com/paper/2106.12491/) (2021)
- [Resolving the Approximability of Offline and Online Non-monotone DR-Submodular Maximization over General Convex Sets](https://mlsanity.com/paper/2210.05965/) (2022)
- [Learning Neural Set Functions Under the Optimal Subset Oracle](https://mlsanity.com/paper/2203.01693/) (2022)
- [Using Partial Monotonicity in Submodular Maximization](https://mlsanity.com/paper/2202.03051/) (2022)
- [Nearly Minimax Optimal Submodular Maximization with Bandit Feedback](https://mlsanity.com/paper/2310.18465/) (2023)
- [Batch Bayesian Optimization on Permutations using the Acquisition Weighted Kernel](https://mlsanity.com/paper/2102.13382/) (2021)
- [Maximizing approximately k-submodular functions](https://mlsanity.com/paper/2101.07157/) (2021)
- [METAM: Goal-Oriented Data Discovery](https://mlsanity.com/paper/2304.09068/) (2023)
- [EXACT: Explicit Attribute-Guided Decoding-Time Personalization](https://mlsanity.com/paper/2602.17695/) (2026)
- [Difference of Submodular Minimization via DC Programming](https://mlsanity.com/paper/2305.11046/) (2023)
- [A Fast Algorithm for Moderating Critical Nodes via Edge Removal](https://mlsanity.com/paper/2309.06392/) (2023)
- [Distributionally Robust Active Learning for Gaussian Process Regression](https://mlsanity.com/paper/2502.16870/) (2025)
- [Online MAP Inference and Learning for Nonsymmetric Determinantal Point Processes](https://mlsanity.com/paper/2111.14674/) (2021)
- [Scalable Sampling for Nonsymmetric Determinantal Point Processes](https://mlsanity.com/paper/2201.08417/) (2022)
- [Resource Allocation to Agents with Restrictions: Maximizing Likelihood with Minimum Compromise](https://mlsanity.com/paper/2209.05170/) (2022)
- [Nonlinear Bayesian optimal experimental design using logarithmic Sobolev inequalities](https://mlsanity.com/paper/2402.15053/) (2024)
- [Demarcating Endogenous and Exogenous Opinion Dynamics: An Experimental Design Approach](https://mlsanity.com/paper/2102.05954/) (2021)
- [Online Nonsubmodular Minimization with Delayed Costs: From Full Information to Bandit Feedback](https://mlsanity.com/paper/2205.07217/) (2022)
- [Online SuBmodular + SuPermodular (BP) Maximization with Bandit Feedback](https://mlsanity.com/paper/2207.03091/) (2022)
- [Lazy FSCA for Unsupervised Variable Selection](https://mlsanity.com/paper/2103.02687/) (2021)
- [Parallel Quasi-concave set optimization: A new frontier that scales without needing submodularity](https://mlsanity.com/paper/2108.08758/) (2021)
- [Online Subset Selection using α-Core with no Augmented Regret](https://mlsanity.com/paper/2209.14222/) (2022)
- [RELS-DQN: A Robust and Efficient Local Search Framework for Combinatorial Optimization](https://mlsanity.com/paper/2304.06048/) (2023)
- [Supermodular Rank: Set Function Decomposition and Optimization](https://mlsanity.com/paper/2305.14632/) (2023)
- [Score-Based Methods for Discrete Optimization in Deep Learning](https://mlsanity.com/paper/2310.09890/) (2023)
- [Theoretically Grounded Pruning of Large Ground Sets for Constrained, Discrete Optimization](https://mlsanity.com/paper/2410.17945/) (2024)
- [Automatic Rank Determination for Low-Rank Adaptation via Submodular Function Maximization](https://mlsanity.com/paper/2507.01841/) (2025)
- [A Greedy PDE Router for Blending Neural Operators and Classical Methods](https://mlsanity.com/paper/2509.24814/) (2025)

## Abstract (arXiv)

We investigate the performance of the standard Greedy algorithm for cardinality constrained maximization of non-submodular nondecreasing set functions. While there are strong theoretical guarantees on the performance of Greedy for maximizing submodular functions, there are few guarantees for non-submodular ones. However, Greedy enjoys strong empirical performance for many important non-submodular functions, e.g., the Bayesian A-optimality objective in experimental design. We prove theoretical guarantees supporting the empirical performance. Our guarantees are characterized by a combination of the (generalized) curvature α and the submodularity ratio γ. In particular, we prove that Greedy enjoys a tight approximation guarantee of frac1α(1- e-γα) for cardinality constrained maximization. In addition, we bound the submodularity ratio and curvature for several important real-world objectives, including the Bayesian A-optimality objective, the determinantal function of a square submatrix and certain linear programs with combinatorial constraints. We experimentally validate our theoretical findings for both synthetic and real-world applications.