Noisy Generalized Binary Search

Robert D. NowakNeurIPS 2009 · OpenReview

Introduction

Binary search is a classic tool for finding a value in a sorted list, but what if you are searching for a complex "hypothesis" (like a classification rule) in a high-dimensional space? This is the domain of Generalized Binary Search (GBS). GBS is a greedy algorithm that selects queries to split the remaining pool of possible hypotheses as evenly as possible. It is widely used in active learning, disease diagnosis, machine diagnostics, and computer vision.

The major hurdle in these real-world applications is noise—the answers to our queries are often incorrect. Previous attempts to make GBS noise-tolerant usually involved repeating the same query multiple times to "average out" the noise. However, this approach is mathematically suboptimal. This paper introduces an optimal, noise-tolerant version of GBS that employs a Bayesian update strategy and a clever randomized query selection to achieve exponential error decay and optimal query complexity.

Methods: A Bayesian Approach to GBS

To overcome the limitations of query repetition, the authors propose a Bayesian framework called Noisy Generalized Binary Search (NGBS).

Comparison of standard Generalized Binary Search (a) and the proposed Noisy Generalized Binary Search (b).

The core innovations of this method include:

  1. Bayesian Weighting: Instead of simply keeping or discarding hypotheses based on binary answers (as seen in standard GBS), NGBS maintains a probability distribution over the entire hypothesis space. After each query, it boosts the weights of hypotheses that agree with the observed (noisy) answer and penalizes those that do not.
  2. The "Modified" Selection Rule: A standard greedy approach can get "stuck" if one hypothesis gains too much probability mass, making all future queries feel certain and uninformative. To resolve this, the authors introduce a Modified NGBS. If the algorithm detects it is in a state where two "neighboring" regions of the search space have very strong, opposing predictions, it randomly chooses between them.
  3. The Neighborly Condition: The paper defines a geometric property of hypothesis spaces called being "neighborly," meaning hypotheses are locally distinguishable. This property bridges the gap between simple 1D binary search and complex multidimensional problems, providing a formal way to ensure the search space is structured enough to be searched efficiently.

Key Insights and Results

As a theoretical machine learning paper, this work focuses on mathematical proofs and evaluations within specific hypothesis classes, such as multidimensional threshold functions (linear decision surfaces in $d$-dimensional Euclidean space). The analysis reveals several critical insights:

  • Query Repetition is Wasteful: The paper mathematically proves that the common "repeat-the-query" strategy is a logarithmic factor worse than the optimal complexity. It is significantly more efficient to move on to new, informative queries than to obsess over the correctness of a single data point.
  • Randomization as a Catalyst: Surprisingly, injecting a degree of randomness into the query selection—specifically when the algorithm is overly confident—is exactly what enables exponential convergence.
  • Optimal Query Complexity: The NGBS algorithm achieves a query complexity of $O(\log(|H|/\delta))$, where $|H|$ is the number of hypotheses and $\delta$ is the confidence parameter. This represents the theoretical information-theoretic limit for any such algorithm.
  • Exponential Convergence: The probability of selecting the incorrect hypothesis decays exponentially ($e^{-\lambda n}$) with the number of queries $n$.

Limitations and Future Work

While the query complexity is optimal, the computational complexity per step depends on the number of polytopes created by the intersection of all hypotheses. In very high dimensions ($d$), this can scale poorly ($O(|H|^d)$).

Additionally, the current model assumes independent binary noise. Exploring how the algorithm handles "adversarial" noise or noise that depends on the query location remains an open challenge for future research. Finally, while the paper touches on an "agnostic" version (where the true hypothesis might not be in our set $H$), the primary focus remains on the "realizable" case where the true hypothesis is assumed to exist within the search space.

Summary updated

Abstract

This paper addresses the problem of noisy Generalized Binary Search (GBS). GBS is a well-known greedy algorithm for determining a binary-valued hypothesis through a sequence of strategically selected queries. At each step, a query is selected that most evenly splits the hypotheses under consideration into two disjoint subsets, a natural generalization of the idea underlying classic binary search. GBS is used in many applications, including fault testing, machine diagnostics, disease diagnosis, job scheduling, image processing, computer vision, and active learning. In most of these cases, the responses to queries can be noisy. Past work has provided a partial characterization of GBS, but existing noise-tolerant versions of GBS are suboptimal in terms of sample complexity. This paper presents the first optimal algorithm for noisy GBS and demonstrates its application to learning multidimensional threshold functions.
BibTeX
@inproceedings{nowak2009noisy,
  author = {Robert D. Nowak},
  title = {{Noisy Generalized Binary Search}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2009},
  url = {https://openreview.net/forum?id=Hy-8tvbubB},
}
Figure