Timezone: »

 
Poster
Practical, Provably-Correct Interactive Learning in the Realizable Setting: The Power of True Believers
Julian Katz-Samuels · Blake Mason · Kevin Jamieson · Rob Nowak

Wed Dec 08 04:30 PM -- 06:00 PM (PST) @
in Poster Session 4 »

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.

Keywords: Theory · Machine Learning · Bandits · Kernel Methods · Active Learning

Author Information

Julian Katz-Samuels (University of Wisconsin)
Blake Mason (University of Wisconsin - Madison)

Blake Mason is Doctoral Student at the University of Wisconsin-Madison studying Electrical and Computer Engineering under the advisement of Professor Robert Nowak. Prior to his graduate studies, he completed his bachelors in electrical engineering at the University of Southern California.

Kevin Jamieson (U Washington)
Rob Nowak

More from the Same Authors