Online Submodular Minimization

Elad Hazan and Satyen Kale
In Journal of Machine Learning Research (JMLR), 2012. Also in proceedings of 23rd Annual Conference on Neural Information Processing Systems (NeurIPS), 2009

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.