# Fast Semidifferential-based Submodular Function Optimization

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Aug 2013.

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

- [Submodular Reinforcement Learning](https://mlsanity.com/paper/2307.13372/) (2023)
- [Global Reinforcement Learning: Beyond Linear and Convex Rewards via Submodular Semi-gradient Methods](https://mlsanity.com/paper/2407.09905/) (2024)
- [TrimCaching: Parameter-sharing AI Model Caching in Wireless Edge Networks](https://mlsanity.com/paper/2405.03990/) (2024)
- [Nonlinear Bayesian optimal experimental design using logarithmic Sobolev inequalities](https://mlsanity.com/paper/2402.15053/) (2024)
- [A Family of Distributions of Random Subsets for Controlling Positive and Negative Dependence](https://mlsanity.com/paper/2408.01022/) (2024)
- [Deep Submodular Peripteral Networks](https://mlsanity.com/paper/2403.08199/) (2024)
- [SubZeroCore: A Submodular Approach with Zero Training for Coreset Selection](https://mlsanity.com/paper/2509.21748/) (2025)

## Abstract (arXiv)

We present a practical and powerful new framework for both unconstrained and constrained submodular function optimization based on discrete semidifferentials (sub- and super-differentials). The resulting algorithms, which repeatedly compute and then efficiently optimize submodular semigradients, offer new and generalize many old methods for submodular optimization. Our approach, moreover, takes steps towards providing a unifying paradigm applicable to both submodular min- imization and maximization, problems that historically have been treated quite distinctly. The practicality of our algorithms is important since interest in submodularity, owing to its natural and wide applicability, has recently been in ascendance within machine learning. We analyze theoretical properties of our algorithms for minimization and maximization, and show that many state-of-the-art maximization algorithms are special cases. Lastly, we complement our theoretical analyses with supporting empirical experiments.