Trading off Mistakes and Don't-Know Predictions

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

Bibtex »Metadata »Paper »


Amin Sayedi, Morteza Zadimoghaddam, Avrim Blum


<p>We discuss an online learning framework in which the agent is allowed to say <code>I don't know'' as well as making incorrect predictions on given examples. We analyze the trade off between saying</code>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.</p>