Trading off Mistakes and Don't-Know Predictions

Amin Sayedi, Morteza Zadimoghaddam, Avrim BlumNeurIPS 2010 · OpenReview

In online learning, algorithms process examples sequentially and predict their labels. Historically, theoretical frameworks have focused on two extremes. The Mistake-Bound Model (Littlestone, 1988) aims to minimize the total number of incorrect predictions. Conversely, the KWIK (Knows What It Knows) Model (Li et al., 2008) strictly forbids mistakes; if the algorithm is uncertain, it must output "I don't know" ($\perp$).

However, the KWIK model is often prohibitively expensive. For many simple concept classes, an algorithm might be forced to output $\perp$ an exponential number of times before successfully learning the target function. This paper, authored by Amin Sayedi, Morteza Zadimoghaddam, and Avrim Blum, explores a practical middle ground: If we tolerate a small, bounded number of mistakes ($k$), can we significantly reduce the number of "I don't know" responses?

The Core Idea: Trading Mistakes for Uncertainty

The authors formalize the intuition that in many high-stakes real-world applications—such as medical diagnosis or autonomous driving—saying "I don't know" is significantly cheaper than making a confident but incorrect prediction. By allowing just a single mistake, the required number of $\perp$ responses can drop dramatically.

The authors elegantly map this tradeoff to the classic "egg-dropping puzzle." They demonstrate that minimizing $\perp$ responses given $k$ allowed mistakes is mathematically equivalent to finding the highest safe floor from which an egg won't break, using a limited number of eggs.

Methodology and Algorithms

The paper introduces both a general theoretical framework and specific, efficient algorithms for distinct concept classes.

General Version-Space Algorithm

For any finite concept class $H$, the authors propose a majority-vote strategy. The algorithm predicts a label if a strong majority of the remaining candidate functions agree; otherwise, it outputs $\perp$. While theoretically sound, this approach requires enumerating all functions in the concept class, making it computationally inefficient for exponentially large classes.

Polynomial-Time Algorithms

To address computational bottlenecks, the authors design efficient algorithms for two specific classes:

  • Monotone Disjunctions: Utilizing a system of "variable pools," the algorithm tracks which features are definitively included, excluded, or uncertain.
  • Linear Separators: For hyperplanes separating data points in $d$-dimensional space with a specific margin $\gamma$, the authors employ a Linear Programming (LP) approach. By estimating the "volume" of the version space using sampling techniques like "Hit-and-run," the algorithm strategically outputs $\perp$ only when neither a positive nor a negative prediction would significantly prune the search space.

Key Theoretical Results

The paper establishes several powerful bounds demonstrating the value of this hybrid model:

  • The Power of One Mistake: In the strict KWIK model, learning a concept class $H$ might require $|H|-1$ "don't know" responses. Allowing just one mistake reduces this bound exponentially to $O(\sqrt{|H|})$.
  • General Bound: For $k$ allowed mistakes, the number of $\perp$ responses can be bounded to roughly $(k+1)|H|^{1/(k+1)}$, providing a clear, quantifiable tradeoff.
  • Specific Class Bounds:
    • For monotone disjunctions (with $n$ variables), the polynomial-time algorithm makes at most $n/2$ mistakes and $n - 2M$ "don't know" responses (where $M$ is the actual number of mistakes made). A more complex variant reduces mistakes to $n/3$.
  • For linear separators, the algorithm achieves $k$ mistakes with $O(R^{1/k} \log R)$ "don't know" responses, where $R$ is a ratio determined by the margin and dimension.

Limitations and Future Directions

While the theoretical bounds are strong, practical implementation remains challenging. The general algorithm is computationally intractable for large concept classes, and the polynomial-time algorithm for linear separators relies on complex volume estimation techniques that are notoriously difficult to implement efficiently in practice.

Future research directions include developing polynomial-time algorithms for other common concept classes, such as general DNF formulas. Additionally, the current model assumes an "adversarial" setting; exploring "average-case" scenarios could yield even tighter bounds and more practical implementations.

Summary updated

Abstract

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.
BibTeX
@inproceedings{sayedi2010trading,
  author = {Amin Sayedi and Morteza Zadimoghaddam and Avrim Blum},
  title = {{Trading off Mistakes and Don't-Know Predictions}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2010},
  url = {https://openreview.net/forum?id=r1-FJwb_-H},
}
Figure