University COVID-19 update

The University of Waterloo is constantly updating our most Frequently Asked Questions.

Questions about buildings and services? Visit the list of Modified Services.

Please note: The University of Waterloo is closed for all events until further notice.

Tutte Colloquium - Shachar LovettExport this event to calendar

Friday, July 17, 2020 — 3:30 PM EDT

Title: Point Location and Active Learning - Learning Halfspaces Almost Optimally

Speaker: Shachar Lovett
Affiliation: UC San Diego
Zoom: Please email Emma Watson

Abstract:

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.

S M T W T F S
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
1
2
3
  1. 2021 (58)
    1. June (11)
    2. May (7)
    3. April (9)
    4. March (13)
    5. February (8)
    6. January (10)
  2. 2020 (119)
    1. December (5)
    2. November (12)
    3. October (12)
    4. September (12)
    5. August (11)
    6. July (17)
    7. June (11)
    8. May (6)
    9. March (11)
    10. February (11)
    11. January (11)
  3. 2019 (167)
  4. 2018 (136)
  5. 2017 (103)
  6. 2016 (137)
  7. 2015 (136)
  8. 2014 (88)
  9. 2013 (48)
  10. 2012 (39)
  11. 2011 (36)
  12. 2010 (40)
  13. 2009 (40)
  14. 2008 (39)
  15. 2007 (15)