Practical, Provably-Correct Interactive Learning in the Realizable Setting: The Power of True Believers
This work addresses the need for efficient and provably correct algorithms in interactive learning for realizable scenarios, offering a general-purpose framework applicable to various function classes.
The paper tackles the problem of interactive learning in the realizable setting by developing computationally efficient algorithms that match minimax lower bounds up to logarithmic factors, achieving sample complexities quantified by dimensions like extended teaching dimension and demonstrating empirical competitiveness with Gaussian process UCB methods.
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{ö}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.