|Concave Aspects of Submodular Functions
|Rishabh Iyer, University of Texas Dallas, United States; Jeff Bilmes, University of Washington, United States
|A.3: Combinatorics and Information Theory
|Algebraic and Combinatorial Coding Theory
|Click here to download the manuscript
|Click here to watch in the Virtual Symposium
|Submodular Functions are a special class of Set Functions, which generalize several Information-Theoretic quantities such as Entropy and Mutual Information . Submodular functions have subgradients and subdifferentials  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.