Point Location and Active Learning: Learning Halfspaces Almost Optimally

Max Hopkins, Daniel M. Kane, Shachar Lovett +1

Given a finite set $X\subset {\mathbb{R}}^d$ and a binary linear classifier $c:{\mathbb{R}}^d\to \{0,1\}$, how many queries of the form $c(x)$ are required to learn the label of eve…