Practical, Provably-Correct Interactive Learning in the Realizable Setting: The Power of True Believers

Julian Katz-Samuels, Blake Mason, Kevin Jamieson, Robert D. Nowak

Introduction

Interactive learning—encompassing paradigms such as active classification and best-arm identification—revolves around the strategic selection of data points to query. Whether identifying the most effective drug in a clinical trial or labeling images for a computer vision model, the goal is to learn an underlying model with minimal sample complexity. Historically, researchers have faced a dichotomy: utilize agnostic algorithms that are robust to noise but often exponentially slower than necessary, or realizability-based algorithms that are potentially optimal but computationally intractable for complex function classes.

This paper introduces GRAILS (GReedy Algorithm for Interactive Learning using Sampling), a general-purpose framework that bridges this gap. GRAILS is the first computationally efficient algorithm to achieve near-optimal sample complexity across diverse function classes, including kernels and convex functions, by operating under the assumption that the true model exists within a given function class (the realizable setting).

The Problem: The "Agnostic Tax"

In interactive learning, the "Agnostic Tax" refers to the heavy price in sample complexity paid by algorithms designed to be robust to model errors. The authors demonstrate that in certain scenarios, an agnostic algorithm might require $\sqrt{n}$ samples, whereas a realizable algorithm—one that "believes" in its model class—requires only $\log(n)$.

Despite this potential for exponential speedup, realizable algorithms have been difficult to implement. They typically require tracking a "version space"—the set of all functions consistent with observed data. For continuous or high-dimensional function classes, enumerating or even representing this space is often impossible. Consequently, previous practical successes were largely limited to specific cases like linear models.

The GRAILS Framework

GRAILS addresses these challenges through a strategy of greedy volume reduction. At each iteration, the algorithm identifies and queries the point expected to eliminate the largest possible "volume" of the remaining version space.

Key Technical Innovations

  1. Sampling over Enumeration: Rather than attempting to explicitly list every function in the version space, GRAILS utilizes a sampling oracle. By drawing representative functions from the version space, the algorithm can estimate the information gain of potential queries.
  2. Navigating Non-Convexity: Version spaces are frequently non-convex, presenting a significant hurdle for standard sampling techniques. GRAILS overcomes this by decomposing the version space into a union of convex sets and employing "hit-and-run" Monte Carlo algorithms to sample from a mixture distribution.
  3. Discretization for Continuous Outputs: To extend the framework from classification to regression, the authors implement a discretization strategy. This maps continuous regression functions to a discrete set of labels, allowing the algorithm to quantify volume reduction effectively without losing theoretical guarantees.

Theoretical and Empirical Validation

GRAILS is theoretically grounded in the Haystack Dimension, a combinatorial measure that quantifies the difficulty of locating a specific function within a class. The authors prove that GRAILS matches minimax lower bounds—the theoretical limit of performance—up to logarithmic factors for both loss minimization and best-arm identification.

Empirical Performance

The framework was evaluated using synthetic benchmarks designed for interactive environments:

  • RBF Kernel Functions: Testing high-dimensional 2D functions from a Reproducing Kernel Hilbert Space (RKHS).
  • Convex Functions: Identifying the minimum of 1D convex shapes.
  • Prior Knowledge Integration: Testing the algorithm's ability to incorporate side information, such as pairwise constraints (e.g., $f(x) \ge f(x')$).

In these simulations, GRAILS consistently matched or outperformed established baselines like GP-UCB and OFUL. Notably, GRAILS excelled at utilizing prior constraints—such as monotonicity or convexity—which often provide significant speedups that standard methods struggle to exploit.

Limitations and Future Directions

While GRAILS represents a significant step forward, several challenges remain:

  • Computational Scaling: While theoretically efficient, the algorithm's computational burden increases significantly when the pool of potential queries exceeds 10,000 points.
  • Noise Robustness: The current framework is optimized for the noiseless, realizable setting. While repeated sampling can mitigate some noise, a native, high-noise implementation is a priority for future work.
  • Continuous Output Spaces: The reliance on discretization for regression suggests there may be more elegant ways to handle continuous output spaces directly without risking suboptimal sample complexity.

Conclusion

By treating interactive learning as a geometric volume reduction task and leveraging sophisticated sampling techniques, GRAILS provides a practical path toward achieving the theoretical speedups promised by the realizable setting. It demonstrates that "true believers" in a model class can indeed learn faster, provided they have the right tools to navigate the geometry of their uncertainty.

Summary updated

Abstract

We consider interactive learning in the realizable setting and develop a general framework to handle problems ranging from best arm identification to active classification. We begin our investigation with the observation that agnostic algorithms \emph{cannot} be minimax-optimal in the realizable setting. Hence, we design novel computationally efficient algorithms for the realizable setting that match the minimax lower bound up to logarithmic factors and are general-purpose, accommodating a wide variety of function classes including kernel methods, H{\"o}lder smooth functions, and convex functions. The sample complexities of our algorithms can be quantified in terms of well-known quantities like the extended teaching dimension and haystack dimension. However, unlike algorithms based directly on those combinatorial quantities, our algorithms are computationally efficient. To achieve computational efficiency, our algorithms sample from the version space using Monte Carlo "hit-and-run" algorithms instead of maintaining the version space explicitly. Our approach has two key strengths. First, it is simple, consisting of two unifying, greedy algorithms. Second, our algorithms have the capability to seamlessly leverage prior knowledge that is often available and useful in practice. In addition to our new theoretical results, we demonstrate empirically that our algorithms are competitive with Gaussian process UCB methods.
BibTeX
@inproceedings{katzsamuels2021practical,
  author = {Julian Katz-Samuels and Blake Mason and Kevin Jamieson and Robert D. Nowak},
  title = {{Practical, Provably-Correct Interactive Learning in the Realizable Setting: The Power of True Believers}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=wJXWzCsGlZw},
}
Figure