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

Authors: A. Guillory and J. A. Bilmes

Abstract

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