Title: Online submodular set cover, ranking, and repeated active learning

Authors: A. Guillory and J. A. Bilmes


We propose an online prediction version of submodular set cover with connections to ranking and repeated active learning. In each round, the learning algorithm chooses a sequence of items. The algorithm then receives a monotone submodu- lar function and suffers loss equal to the cover time of the function: the number of items needed, when items are selected in order of the chosen sequence, to achieve a coverage constraint. We develop an online learning algorithm whose loss con- verges to approximately that of the best sequence in hindsight. Our proposed algorithm is readily extended to a setting where multiple functions are revealed at each round and to bandit and contextual bandit settings.

Full Text: [PDF]

Accessibility at Yale   Inference, Information, and Decision Group at Yale