Jeff A. Bilmes's Publications

• Sorted by Date • Classified by Publication Type • Classified by Research Category • Sorted by First Author Last Name • Classified by Author Last Name •

Concave Aspects of Submodular Functions

Rishabh Iyer and Jeff Bilmes. Concave Aspects of Submodular Functions. In IEEE International Symposium on Information Theory, June 2020.

Download

(unavailable)

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.

@InProceedings{iyer-concave-submod-isit-2020,
  author = 	 {Rishabh Iyer and Jeff Bilmes},
  title = 	 {Concave Aspects of Submodular Functions},
  booktitle =  "IEEE International Symposium on Information Theory",
  year = 	 {2020},
  month = 	 {June},
  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.},
}

Share

Generated by bib2html.pl (written by Patrick Riley ) on Wed Dec 13, 2023 01:42:17