Part of Advances in Neural Information Processing Systems 23 (NIPS 2010)

*Amin Sayedi, Morteza Zadimoghaddam, Avrim Blum*

We discuss an online learning framework in which the agent is allowed to say `I don't know'' as well as making incorrect predictions on given examples. We analyze the trade off between saying`

I don't know'' and making mistakes. If the number of don't know predictions is forced to be zero, the model reduces to the well-known mistake-bound model introduced by Littlestone [Lit88]. On the other hand, if no mistakes are allowed, the model reduces to KWIK framework introduced by Li et. al. [LLW08]. We propose a general, though inefficient, algorithm for general finite concept classes that minimizes the number of don't-know predictions if a certain number of mistakes are allowed. We then present specific polynomial-time algorithms for the concept classes of monotone disjunctions and linear separators.

Do not remove: This comment is monitored to verify that the site is working properly