Title: Point Location and Active Learning - Learning Halfspaces Almost Optimally
|Affiliation:||UC San Diego|
|Zoom:||Please email Emma Watson|
The point location problem is a central problem in computational geometry. It asks, given a known partition of R^d by n hyperplanes, and an unknown input point, to find the cell in the partition to which the input point belongs. The access to the input is via linear queries. A linear query is specified by an hyperplane, and the result of the query is which side of the hyperplane the input point lies in.
A dual problem is active learning of half-spaces, a well-studied problem in machine learning. Here, there are n known points in R^d, and an unknown input hyperplane. Each point is labeled by the side of the input hyperplane it lies in. The goal is to find the labels of all n given points, by making a few linear queries, where a linear query amounts to querying the label of an arbitrary point.
There is a simple lower bound that shows that Omega(d log n) queries may be needed. In a series of works spanning the last 40 years, the best upper bound has been O(d^2 log d log n), leaving a quadratic gap between the lower and upper bounds dependence on the dimension d. In this work, we improve this to a near-linear dependency. The proof combines previous geometric and combinatorial techniques combined with a new structural decomposition.
Joint work with Max Hopkins, Daniel Kane and Gaurav Mahajan.