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

arXiv: https://arxiv.org/abs/2111.04915 · HTML: https://mlsanity.com/paper/2111.04915/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 38 references that are in the map.
- First posted on arXiv 9 Nov 2021.

## Builds on (most cited first, 16 of 16)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Optimal Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1602.04589/) (2016)
- [lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits](https://mlsanity.com/paper/1312.7308/) (2013)
- [Best-Arm Identification in Linear Bandits](https://mlsanity.com/paper/1409.6110/) (2014)
- [Sequential Experimental Design for Transductive Linear Bandits](https://mlsanity.com/paper/1906.08399/) (2019)
- [High-Dimensional Experimental Design and Kernel Bandits](https://mlsanity.com/paper/2105.05806/) (2021)
- [A Survey of Constrained Gaussian Process Regression: Approaches and Implementation Challenges](https://mlsanity.com/paper/2006.09319/) (2020)
- [The End of Optimism? An Asymptotic Analysis of Finite-Armed Linear Bandits](https://mlsanity.com/paper/1610.04491/) (2016)
- [An Empirical Process Approach to the Union Bound: Practical Algorithms for Combinatorial and Linear Bandits](https://mlsanity.com/paper/2006.11685/) (2020)
- [The True Sample Complexity of Identifying Good Arms](https://mlsanity.com/paper/1906.06594/) (2019)
- [Improved Algorithms for Agnostic Pool-based Active Classification](https://mlsanity.com/paper/2105.06499/) (2021)
- [A New Perspective on Pool-Based Active Classification and False-Discovery Control](https://mlsanity.com/paper/2008.06555/) (2020)
- [Diameter-Based Active Learning](https://mlsanity.com/paper/1702.08553/) (2017)
- [A Bandit Approach to Multiple Testing with False Discovery Control](https://mlsanity.com/paper/1809.02235/) (2018)
- [Diameter-based Interactive Structure Discovery](https://mlsanity.com/paper/1906.02101/) (2019)

## Abstract (arXiv)

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 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"older 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.