ActiveHedge: Hedge meets Active Learning

Bhuvesh Kumar, Jacob D Abernethy, Venkatesh Saligrama
Proceedings of the 39th International Conference on Machine Learning, PMLR 162:11694-11709, 2022.

Abstract

We consider the classical problem of multi-class prediction with expert advice, but with an active learning twist. In this new setting the learner will only query the labels of a small number of examples, but still aims to minimize regret to the best expert as usual; the learner is also allowed a very short "burn-in" phase where it can fast-forward and query certain highly-informative examples. We design an algorithm that utilizes Hedge (aka Exponential Weights) as a subroutine, 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, or just 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v162-kumar22a, title = {{A}ctive{H}edge: Hedge meets Active Learning}, author = {Kumar, Bhuvesh and Abernethy, Jacob D and Saligrama, Venkatesh}, booktitle = {Proceedings of the 39th International Conference on Machine Learning}, pages = {11694--11709}, year = {2022}, editor = {Chaudhuri, Kamalika and Jegelka, Stefanie and Song, Le and Szepesvari, Csaba and Niu, Gang and Sabato, Sivan}, volume = {162}, series = {Proceedings of Machine Learning Research}, month = {17--23 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v162/kumar22a/kumar22a.pdf}, url = {https://proceedings.mlr.press/v162/kumar22a.html}, abstract = {We consider the classical problem of multi-class prediction with expert advice, but with an active learning twist. In this new setting the learner will only query the labels of a small number of examples, but still aims to minimize regret to the best expert as usual; the learner is also allowed a very short "burn-in" phase where it can fast-forward and query certain highly-informative examples. We design an algorithm that utilizes Hedge (aka Exponential Weights) as a subroutine, 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, or just 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.} }
Endnote
%0 Conference Paper %T ActiveHedge: Hedge meets Active Learning %A Bhuvesh Kumar %A Jacob D Abernethy %A Venkatesh Saligrama %B Proceedings of the 39th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2022 %E Kamalika Chaudhuri %E Stefanie Jegelka %E Le Song %E Csaba Szepesvari %E Gang Niu %E Sivan Sabato %F pmlr-v162-kumar22a %I PMLR %P 11694--11709 %U https://proceedings.mlr.press/v162/kumar22a.html %V 162 %X We consider the classical problem of multi-class prediction with expert advice, but with an active learning twist. In this new setting the learner will only query the labels of a small number of examples, but still aims to minimize regret to the best expert as usual; the learner is also allowed a very short "burn-in" phase where it can fast-forward and query certain highly-informative examples. We design an algorithm that utilizes Hedge (aka Exponential Weights) as a subroutine, 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, or just 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.
APA
Kumar, B., Abernethy, J.D. & Saligrama, V.. (2022). ActiveHedge: Hedge meets Active Learning. Proceedings of the 39th International Conference on Machine Learning, in Proceedings of Machine Learning Research 162:11694-11709 Available from https://proceedings.mlr.press/v162/kumar22a.html.

Related Material