# Concave Aspects of Submodular Functions

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Jun 2020.

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

- [Submodlib: A Submodular Optimization Library](https://mlsanity.com/paper/2202.10680/) (2022)
- [Improving Attribution Methods by Learning Submodular Functions](https://mlsanity.com/paper/2104.09073/) (2021)

## Abstract (arXiv)

Submodular Functions are a special class of set functions, which generalize several information-theoretic quantities such as entropy and mutual information [1]. Submodular functions have subgradients and subdifferentials [2] and admit polynomial-time algorithms for minimization, both of which are fundamental characteristics of convex functions. Submodular functions also show signs similar to concavity. Submodular function maximization, though NP-hard, admits constant-factor approximation guarantees, and concave functions composed with modular functions are submodular. In this paper, we try to provide a more complete picture of the relationship between submodularity with concavity. We characterize the super-differentials and polyhedra associated with upper bounds and provide optimality conditions for submodular maximization using the-super differentials. This paper is a concise and shorter version of our longer preprint [3].