Home Bookmarks Papers Blog

Active Learning a Convex Body in Low Dimensions

$ \newcommand{\PS}{\Mh{P}}% \newcommand{\body}{\Mh{C}}% \newcommand{\priceY}[2]{\priceC\pth{#1, #2}}% \newcommand{\priceC}{\Mh{C}}% \newcommand{\indexX}[1]{\text{H}^{}_{#1}}% \newcommand{\Re}{\mathbb{R}} \newcommand{\reals}{\mathbb{R}} \newcommand{\SetX}{\mathsf{X}} \newcommand{\rad}{r} \newcommand{\Mh}[1]{#1} \newcommand{\query}{q} \newcommand{\eps}{\varepsilon} \newcommand{\VorX}[1]{\mathcal{V} \pth{#1}} \newcommand{\Polygon}{\mathsf{P}} \newcommand{\IntRange}[1]{[ #1 ]} \newcommand{\Space}{\overline{\mathsf{m}}} \newcommand{\pth}[2][\!]{#1\left({#2}\right)} \newcommand{\polylog}{\mathrm{polylog}} \newcommand{\N}{\mathbb N} \newcommand{\Z}{\mathbb Z} \newcommand{\pt}{p} \newcommand{\distY}[2]{\left\| {#1} - {#2} \right\|} \newcommand{\ptq}{q} \newcommand{\pts}{s}$
Sariel Har-Peled, Mitchell Jones, and Saladi Rahul.
Consider a set $\PS \subseteq \Re^d$ of $n$ points, and a convex body $\body$ provided via a separation oracle. The task at hand is to decide for each point of $\PS$ if it is in $\body$ using the fewest number of oracle queries. We show that one can solve this problem in two and three dimensions using $O( \indexX{\PS} \log n)$ queries, where $\indexX{\PS}$ is the largest subset of points of $\PS$ in convex position. Furthermore, we show that in two dimensions one can solve this problem using $O( \priceY{\PS}{\body} \log^2 n )$ oracle queries, where $\priceY{\PS}{\body}$ is a lower bound on the minimum number of queries that any algorithm for this specific instance requires.
PDF. : arXiv : DBLP.
Last modified: Mon 2022-07-25 15:17:49 UTC 2022 by Sariel Har-Peled