Active Learning a Convex Body in Low Dimensions

Abstract

Consider a set $P\subseteq {\Re }^d$ of $n$ points, and a convex body $C$ provided via a separation oracle. The task at hand is to decide for each point of $P$ if it is in $C$ using the fewest number of oracle queries. We show that one can solve this problem in two and three dimensions using $O(h(P)\log n)$ queries, where $h(P)$ is the largest subset of points of $P$ in convex position. Furthermore, we show that in two dimensions one can solve this problem using $O(v(P,C){\log }^{2}n)$ oracle queries, where $v(P,C)$ is a lower bound on the minimum number of queries that any algorithm for this specific instance requires.

Talk based on results in the paper is available here: https://youtu.be/5Epyh2lHrFQ