Jeff A. Bilmes's Publications

Sorted by DateClassified by Publication TypeClassified by Research CategorySorted by First Author Last NameClassified 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.

BibTeX

@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 Sep 02, 2020 22:18:48