Online Learning with Costly Features and Labels
Full Text:
Navid-OnleLearning-nips2013_short.pdf 
This paper introduces the online probing problem: In each round, the learner is able to purchase the values of a subset of feature values. After the learner uses this information to come up with a prediction for the given round, he then has the option of paying to see the loss function that he is evaluated against. Either way, the learner pays for both the errors of his predictions and also whatever he chooses to observe, including the cost of observing the loss function for the given round and the cost of the observed features. We consider two variations of this problem, depending on whether the learner can observe the label for free or not. We provide algorithms and upper and lower bounds on the regret for both variants. We show that a positive cost for observing the label significantly increases the regret of the problem.
Citation
N. Zolghadr,
G. Bartok,
R. Greiner,
C. Szepesvari,
A. Gyorgy.
"Online Learning with Costly Features and Labels".
Neural Information Processing Systems (NIPS), (ed: Christopher J. C. Burges, Léon Bottou, Zoubin Ghahramani, Kilian Q. Weinberger), pp 1241-1249, December 2013.
| Keywords: |
machine learning, on-line learning, probe, lower bounds, costly observations |
| Category: |
In Conference |
| Web Links: |
NeurIPS |
BibTeX
@incollection{Zolghadr+al:NIPS13,
author = {Navid Zolghadr and Garbor Bartok and Russ Greiner and Csaba
Szepesvari and Andras Gyorgy},
title = {Online Learning with Costly Features and Labels},
Editor = {Christopher J. C. Burges, Léon Bottou, Zoubin Ghahramani, Kilian
Q. Weinberger},
Pages = {1241-1249},
booktitle = {Neural Information Processing Systems (NIPS)},
year = 2013,
}Last Updated: February 12, 2020
Submitted by Sabina P 
