ActiveHedge: Hedge meets Active Learning

Abstract

We consider the classical problem of prediction with expert advice, but with an active learning twist. In this new setting, the algorithm may reorder the sequence of examples on which a prediction is made, it aims to minimize regret as usual, but it can observe only a small fraction of the true labels along the way. We consider a variant of the Hedge algorithm for this setting, and we show that under a very particular combinatorial constraint on the matrix of expert predictions we can obtain a very strong regret guarantee while querying very few labels. This constraint, which we refer to as $\zeta $-compactness, can be viewed as a non-stochastic variant of the disagreement coefficient, another popular parameter used to reason about the sample complexity of active learning in the IID setting. We also give a polynomial time algorithm to calculate the $\zeta $-compactness of a matrix up to an approximation factor of 3.

Publication
International Conference on Machine Learning (ICML) 2022
Also selected as oral talk at Complex Feedback in Online Learning Workshop, ICML 2022
Also presented at Adaptive experimental Design and Active Learning in the Real World Workshop, ICML 2022
Date