Julian Katz-Samuels

Bio: I am a Postdoc working with Robert Nowak at the University of Wisconsin. Previously, I was a Postdoc at the Paul G. Allen School of Computer Science & Engineering at the University of Washington under Kevin Jamieson. I completed my PhD in the Electrical Engineering and Computer Science Department at the University of Michigan where my advisor was Clayton Scott. Prior to that, I double-majored in mathematics and philosophy at the University of Chicago. My research focuses on pure exploration multi-armed bandits, recommender systems, and nonparametric estimation. I am also interested in applications of machine learning that promote the social good. As a Data Science for Social Good fellow at the University of Chicago in 2015, I helped develop the Legislative Influence Detector.

Talk Title: Practical Algorithms for Interactive Learning with Generic Function Classes

Talk 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 cannot be minimax-optimal in the realizable setting. Hence, we design novel algorithms for the realizable setting that are nearly minimax optimal, computationally efficient, and general-purpose, accommodating a wide variety of function classes including kernel methods, Holder 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 and in some cases outperform Gaussian process UCB methods. This talk is based on work to appear in NeurIPS 2021.