# Extended Deep Submodular Functions

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 24 references that are in the map.
- First posted on arXiv 18 Sep 2024.

## Builds on (most cited first, 9 of 9)

- [Deep Sets](https://mlsanity.com/paper/1703.06114/) (2017)
- [Melding the Data-Decisions Pipeline: Decision-Focused Learning for Combinatorial Optimization](https://mlsanity.com/paper/1809.05504/) (2018)
- [On the Limitations of Representing Functions on Sets](https://mlsanity.com/paper/1901.09006/) (2019)
- [Stochastic Conditional Gradient Methods: From Convex Minimization to Submodular Maximization](https://mlsanity.com/paper/1804.09554/) (2018)
- [Deep Submodular Functions](https://mlsanity.com/paper/1701.08939/) (2017)
- [Monotone-Value Neural Networks: Exploiting Preference Monotonicity in Combinatorial Assignment](https://mlsanity.com/paper/2109.15117/) (2021)
- [Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas](https://mlsanity.com/paper/1307.3301/) (2013)
- [Neural Estimation of Submodular Functions with Applications to Differentiable Subset Selection](https://mlsanity.com/paper/2210.11033/) (2022)
- [Learning Coverage Functions and Private Release of Marginals](https://mlsanity.com/paper/1304.2079/) (2013)

## Abstract (arXiv)

We introduce a novel category of set functions called Extended Deep Submodular functions (EDSFs), which are neural network-representable. EDSFs serve as an extension of Deep Submodular Functions (DSFs), inheriting crucial properties from DSFs while addressing innate limitations. It is known that DSFs can represent a limiting subset of submodular functions. In contrast, through an analysis of polymatroid properties, we establish that EDSFs possess the capability to represent all monotone submodular functions, a notable enhancement compared to DSFs. Furthermore, our findings demonstrate that EDSFs can represent any monotone set function, indicating the family of EDSFs is equivalent to the family of all monotone set functions. Additionally, we prove that EDSFs maintain the concavity inherent in DSFs when the components of the input vector are non-negative real numbers-an essential feature in certain combinatorial optimization problems. Through extensive experiments, we illustrate that EDSFs exhibit significantly lower empirical generalization error than DSFs in the learning of coverage functions. This suggests that EDSFs present a promising advancement in the representation and learning of set functions with improved generalization capabilities.