# Curvature and Optimal Algorithms for Learning and Minimizing Submodular Functions

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Nov 2013.

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

- [Submodularity In Machine Learning and Artificial Intelligence](https://mlsanity.com/paper/2202.00132/) (2022)
- [Training Data Subset Selection for Regression with Controlled Generalization Error](https://mlsanity.com/paper/2106.12491/) (2021)
- [Using Partial Monotonicity in Submodular Maximization](https://mlsanity.com/paper/2202.03051/) (2022)
- [Resource-Aware Distributed Submodular Maximization: A Paradigm for Multi-Robot Decision-Making](https://mlsanity.com/paper/2204.07520/) (2022)
- [Difference of Submodular Minimization via DC Programming](https://mlsanity.com/paper/2305.11046/) (2023)
- [Nonlinear Bayesian optimal experimental design using logarithmic Sobolev inequalities](https://mlsanity.com/paper/2402.15053/) (2024)
- [Communication- and Computation-Efficient Distributed Submodular Optimization in Robot Mesh Networks](https://mlsanity.com/paper/2407.10382/) (2024)
- [Online Nonsubmodular Minimization with Delayed Costs: From Full Information to Bandit Feedback](https://mlsanity.com/paper/2205.07217/) (2022)
- [Geometry-Aware Dataset Condensation for Diffusion Model Training](https://mlsanity.com/paper/2606.05883/) (2026)
- [Lazy FSCA for Unsupervised Variable Selection](https://mlsanity.com/paper/2103.02687/) (2021)
- [Performance-Aware Self-Configurable Multi-Agent Networks: A Distributed Submodular Approach for Simultaneous Coordination and Network Design](https://mlsanity.com/paper/2409.01411/) (2024)
- [Complement Submodular Information Measures for Balanced and Robust Data Selection](https://mlsanity.com/paper/2605.24779/) (2026)

## Abstract (arXiv)

We investigate three related and important problems connected to machine learning: approximating a submodular function everywhere, learning a submodular function (in a PAC-like setting [53]), and constrained minimization of submodular functions. We show that the complexity of all three problems depends on the 'curvature' of the submodular function, and provide lower and upper bounds that refine and improve previous results [3, 16, 18, 52]. Our proof techniques are fairly generic. We either use a black-box transformation of the function (for approximation and learning), or a transformation of algorithms to use an appropriate surrogate function (for minimization). Curiously, curvature has been known to influence approximations for submodular maximization [7, 55], but its effect on minimization, approximation and learning has hitherto been open. We complete this picture, and also support our theoretical claims by empirical results.