Beyond Convexity: Online Submodular Minimization

Part of Advances in Neural Information Processing Systems 22 (NIPS 2009)

Bibtex »Metadata »Paper »

Authors

Elad Hazan, Satyen Kale

Abstract

<p>We consider an online decision problem over a discrete space in which the loss function is submodular. We give algorithms which are computationally efficient and are Hannan-consistent in both the full information and bandit settings.</p>