2020 IEEE International Symposium
on Information Theory
21-26 June 2020 • Los Angeles, California, USA
| Paper ID | A.3.1 | ||
| Paper Title | Concave Aspects of Submodular Functions | ||
| Authors | Rishabh Iyer, University of Texas Dallas, United States; Jeff Bilmes, University of Washington, United States | ||
| Session | A.3: Combinatorics and Information Theory | ||
| Presentation | Lecture | ||
| Track | Algebraic and Combinatorial Coding Theory | ||
| Manuscript | Click here to download the manuscript | ||
| Virtual Presentation | Click here to watch in the Virtual Symposium | ||
| Abstract | 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. | ||
Plan Ahead
2021 IEEE International Symposium on Information Theory
11-16 July 2021 | Melbourne, Victoria, Australia
