Active Online Learning with Hidden Shifting Domains

Yining Chen, Haipeng Luo, Tengyu Ma, Chicheng Zhang
Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, PMLR 130:2053-2061, 2021.

Abstract

Online machine learning systems need to adapt to domain shifts. Meanwhile, acquiring label at every timestep is expensive. We propose a surprisingly simple algorithm that adaptively balances its regret and its number of label queries in settings where the data streams are from a mixture of hidden domains. For online linear regression with oblivious adversaries, we provide a tight tradeoff that depends on the durations and dimensionalities of the hidden domains. Our algorithm can adaptively deal with interleaving spans of inputs from different domains. We also generalize our results to non-linear regression for hypothesis classes with bounded eluder dimension and adaptive adversaries. Experiments on synthetic and realistic datasets demonstrate that our algorithm achieves lower regret than uniform queries and greedy queries with equal labeling budget.

Cite this Paper

BibTeX
@InProceedings{pmlr-v130-chen21d, title = { Active Online Learning with Hidden Shifting Domains }, author = {Chen, Yining and Luo, Haipeng and Ma, Tengyu and Zhang, Chicheng}, booktitle = {Proceedings of The 24th International Conference on Artificial Intelligence and Statistics}, pages = {2053--2061}, year = {2021}, editor = {Banerjee, Arindam and Fukumizu, Kenji}, volume = {130}, series = {Proceedings of Machine Learning Research}, month = {13--15 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v130/chen21d/chen21d.pdf}, url = {https://proceedings.mlr.press/v130/chen21d.html}, abstract = { Online machine learning systems need to adapt to domain shifts. Meanwhile, acquiring label at every timestep is expensive. We propose a surprisingly simple algorithm that adaptively balances its regret and its number of label queries in settings where the data streams are from a mixture of hidden domains. For online linear regression with oblivious adversaries, we provide a tight tradeoff that depends on the durations and dimensionalities of the hidden domains. Our algorithm can adaptively deal with interleaving spans of inputs from different domains. We also generalize our results to non-linear regression for hypothesis classes with bounded eluder dimension and adaptive adversaries. Experiments on synthetic and realistic datasets demonstrate that our algorithm achieves lower regret than uniform queries and greedy queries with equal labeling budget. } }
Endnote
%0 Conference Paper %T Active Online Learning with Hidden Shifting Domains %A Yining Chen %A Haipeng Luo %A Tengyu Ma %A Chicheng Zhang %B Proceedings of The 24th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2021 %E Arindam Banerjee %E Kenji Fukumizu %F pmlr-v130-chen21d %I PMLR %P 2053--2061 %U https://proceedings.mlr.press/v130/chen21d.html %V 130 %X Online machine learning systems need to adapt to domain shifts. Meanwhile, acquiring label at every timestep is expensive. We propose a surprisingly simple algorithm that adaptively balances its regret and its number of label queries in settings where the data streams are from a mixture of hidden domains. For online linear regression with oblivious adversaries, we provide a tight tradeoff that depends on the durations and dimensionalities of the hidden domains. Our algorithm can adaptively deal with interleaving spans of inputs from different domains. We also generalize our results to non-linear regression for hypothesis classes with bounded eluder dimension and adaptive adversaries. Experiments on synthetic and realistic datasets demonstrate that our algorithm achieves lower regret than uniform queries and greedy queries with equal labeling budget.
APA
Chen, Y., Luo, H., Ma, T. & Zhang, C.. (2021). Active Online Learning with Hidden Shifting Domains . Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 130:2053-2061 Available from https://proceedings.mlr.press/v130/chen21d.html.

Related Material